通风网络拓扑理论及通路算法研究.pdf

第33卷第8期煤 炭 学 报Vol . 33 No. 8 2008年8月JOURNAL OF CH I NA COAL SOCIETYAug . 2008 文章编号 0253 - 9993 2008 08 - 0926 - 05 通风网络拓扑理论及通路算法研究 魏连江 1, 2 ,周福宝 1, 2 ,朱华新 1 1 1中国矿业大学 安全工程学院,江苏 徐州 221116; 21中国矿业大学 煤炭资源与安全开采国家重点实验室,江苏 徐州 221116 摘 要在深入研究通风网络拓扑理论的基础上,提出假拓扑通风网络和真拓扑通风网络的概 念,从通风网络拓扑理论方面解释了风网解算后出现反向分支的原因,并实现了拓扑关系的自动 生成.在拓扑关系自动生成的基础上,通过模拟树的生长规律,提出了确定通风网络任意两节点 间所有通路的 “ 通路树深度优先生长 ”法. 关键词通风网络;拓扑理论;通路算法 中图分类号TD725 文献标识码 A 收稿日期 2008-04-23 责任编辑毕永华 基金项目国家自然科学基金资助项目50604014 ;中国矿业大学煤炭资源与安全开采国家重点实验室开放基金资助项目07KF07 作者简介魏连江1976 , 男,江苏赣榆人,讲师,博士.E - mailcumtvb1261com Topology theory of ventilation network and path algorithm WEILian2jiang 1, 2 ,ZHOU Fu2bao 1, 2 ,ZHU Hua2xin 1 11Faculty of Safety Engineering, China University of M ining 21State Key Laboratory of Coal Resource and M ine Safety,China University of M ining topology theory; path algorithm 通风网络拓扑理论及通路算法是矿井通风仿真系统在矿井通风中进行推广应用的关键技术,是矿井通 风可视化仿真系统的基础 [1 - 4]. 通风网络的拓扑关系是进行通风网络解算、分析和优化通风网络的基础. 尽管矿井通风系统拓扑关系的概念已提出多年,但在通风方面,对拓扑关系的研究还不够深入,如没有用 通风网络拓扑理论来解释网络解算过程中出现风流反向 [5]的原因等. 在深入研究通风网络拓扑理论的基础上,提出了假拓扑和真拓扑通风网络的概念,并给出了假拓扑和 真拓扑通风网络的自动生成思路以及基于真拓扑通风网络自动生成通风网络图的解决办法,从理论上解释 了风网解算后会出现反向分支的原因,对于通风网络拓扑的认识又深入了一步.在真拓扑通风网络的基础 上对通路确定方法进行了研究,通过模拟树的生长规律,提出了理论简单、便于使用、计算复杂度更小的 确定通风网络任意两节点间所有通路的 “ 通路树深度优先生长 ”法PTDFG.对于通风仿真系统的推广 应用具有重要意义. 第8期魏连江等通风网络拓扑理论及通路算法研究 1 通风网络拓扑理论研究与探讨 在通风仿真或通风网络优化时都要使用通风网络的拓扑关系,传统的做法是手工维护,工作量大,而 且容易出错 [2 - 3 ] ,故许多学者研究并实现了通风网络拓扑关系的自动生成 [1, 3, 6 - 7 ] ,但自动生成的通风网络 拓扑关系真的能够正确反映通风网络的拓扑关系吗为何网络解算过程中会出现风流反向在建立通风网 络拓扑关系时,需要建立风流方向的拓扑关系吗下面将用拓扑理论来对这些问题进行研究与探讨. 拓扑反映了空间实体之间不随实体的连续变形而改变的与量度和方向无关的一种空间关系,这种空间 关系叫做拓扑关系.通风系统中拓扑元素较多,如节点、巷道、通风动力装置、通风构筑物等.通风系统 主要包括2类元素点状要素和线状要素,即节点、通风动力装置、通风构筑物和分支.节点是指分支的 端点,分支是指2个节点间的有序折线段. 111 矿井通风系统中的拓扑关系及其表示 11111 通风系统中的拓扑关系 [7 ] 矿井通风网络的模型反映的是各巷道之间的拓扑连接关系.在逻辑上把通风网络视为巷道在节点处连 接而成,每条巷道对应始末2个节点,如果2条巷道共有1个节点则表示这2条巷道在共有节点处连接, 多条巷道可以共有1个节点.其基本拓扑关系可分为关联、邻接、相交和相离等4种基本拓扑关系. 11112 矿井通风系统拓扑关系的特点 1分支与节点的拓扑关系.1条分支对应始末节点,分支的方向由始节点指向末节点, 2条分支相 交处均设置节点.在矿井通风系统中,不存在孤立的节点,同时也不存在孤立的分支.节点将整个矿井通 风系统中分支连接在一起,如果分支方向发生改变,则拓扑关系也随之发生改变. 2分支与构筑物、通风动力装置的拓扑关系.构筑物或通风动力装置只属于1条分支,如果1条分 支被删除,和其对应的构筑物和通风动力装置将会被删除,若删除1个构筑物或者通风动力装置时,相应 的分支要与被删除对象解除关系. 112 通风网络拓扑关系的自动生成 [2 ] 节点与分支是空间中点要素和线要素在拓扑意义上的表示,建立节点与分支的过程也就是建立两者之 间拓扑关系的过程.节点与分支的拓扑关系体现在它们间的关联关系上.每条分支都有相应的属性来记录 分支的始节点和末节点;每个节点都有1个流入和流出分支的动态数组,记录流入流出该节点的分支. 在存储通风系统数据的时候并不存储拓扑关系,而是打开图形时自动生成拓扑关系,在发生变化的时 候,要求能实时维护拓扑关系.通风网络拓扑关系的自动建立与维护具体实现方法如下 1建立矿井通风系统单线图数据可以从CAD图导入,点坐标包括X,Y,Z坐标 . 2遍历所有巷道,如果一条巷道与其他巷道相交在三维空间里判断是否相交 , 并且交点不与该 巷道的始、末节点重合,如果该交点处无风桥,则该巷道从交点处分割为2条巷道,建立相应的假节点, 除了与长度相关的属性外,其他所有的巷道特征和属性都可从原巷道继承.使用最小外接矩形Mini mum Bounding Rectangle进行相交等关系的快速判断, 可大大减少处理的时间.相互跨越的巷道可以不做任何 处理. 3节点匹配,建立节点、分支关系,进行邻近节点的合并.在建立分支拓扑关系时需使用统一节 点,因此要进行节点匹配.遍历所有巷道的始、末点,如果节点集合为空,则往节点集合加入该点并对所 加节点进行编号,否则将该点与集合中所有的节点比较,如果该点与集合中所有的节点的距离都不小于一 个规定的距离,那么就将该点加入节点集合并对所加节点进行编号,最后所有巷道的首、末节点都获取节 点的编号,即建立了节点和巷道的拓扑关系. 4根据构筑物和通风动力装置与巷道的空间位置自动判断它属于哪一条巷道,即建立构筑物和通 风动力装置和巷道的拓扑关系. 729 煤 炭 学 报 2008年第33卷 113 定义通风网络拓扑相关概念 为研究方便,提出和定义以下几个概念. 1假拓扑分支如果不能确定某条分支的风流方向,可以暂且假定1个风流方向,但可以确定它 与通风网络的连接关系,像这样的分支称之为假拓扑分支. 2真拓扑分支如果可以正确确定某条分支的风流方向,并且可以确定它与通风网络的连接关系, 像这样的分支称之为真拓扑分支. 3假拓扑通风网络含有假拓扑分支的通风网络,称之为假拓扑通风网络. 4真拓扑通风网络不含有假拓扑分支的通风网络称之为真拓扑通风网络. 5虚拓扑通风网络基于复合分支将串联和并联子网简化为复合分支和参数等效变换简化后 的通风网络与真实模型不同称之为虚拓扑通风网络.虚拓扑是对风网的操作,忽略通风网络的细节 和不重要的特征,可以提高风网的解算效率. 由于自动生成的拓扑通风网络一般都含有假拓扑通风网络,含有假拓扑分支没有正确反映分支风 流方向 , 在风流解算时会出现风流反向,因此不能反映真实的通风网络拓扑关系.通过网络解算后,修 正假拓扑分支的始、末节点,可以确定与通风网络的真正拓扑关系主要指风流方向,含连接关系 , 那 么假拓扑分支就转为真拓扑分支,假拓扑通风网络就可以转为真拓扑通风网络. 114 各种拓扑通风网络的作用 假拓扑通风网络反映了分支的连接关系,但没有真正反映风流方向,可以用来进行风网解算,但不能 用来生成通风网络图和找通路.假拓扑通风网络通过网络解算,将假拓扑分支都转为真拓扑分支后,假拓 扑通风网络可以转为真拓扑通风网络. 真拓扑通风网络正确反映了分支间的连接关系和分支的风流方向,可以作为风网解算的基础.基于真 拓扑通风网络,可以采用最长通路法自动生成通风网络图 [8 ]. 虚拓扑通风网络是基于复合分支和参数等效变换对通风网络进行了简化,与真实模型不同,基于虚拓 扑通风网络可以进行通风网络解算,并且可以大大提高解算的效率,降低计算复杂度. 有的学者在研究通风网络拓扑关系的自动生成时,提出将风流方向作为拓扑元素,也就是说通风网络 的拓扑元素包含风流方向.笔者认为,风流方向实际上是不会独立存在的,它与井巷的始、末节点位置有 关,因此风流方向拓扑是多余的,将风流方向作为拓扑元素参与通风网络拓扑不妥,而且还容易导致风流 方向与井巷的始、末节点关系不一致. 2 通路算法研究与实现 前面介绍的真拓扑通风网络已包含了分支与节点的正确的拓扑关系,下面基于真拓扑通风网络对通路 算法进行研究.为了增加算法的适应性,将多源多汇型通风网络通过加虚分支和虚节点变为单源单汇型通 风网络,以后提到的通风网络都指单源单汇型通风网络. 211 通风网络通路算法研究现状 通风网络拓扑关系的自动建立为矿井通风系统的风网解算、风量调节等奠定了基础,尤其是基于真拓 扑通风网络可以为自动生成通风网络图,确定通路提供真实的基础数据. 通路在通风网络的研究与分析中有着广泛的用途 [9 - 13 ] ,如利用通路法对通风网络进行优化调节, 通路法绘制通风网络图等等,目前通路算法主要有矩阵法和搜索法. 当通风网络中出现循环风,也就是网络中存在单向回路时,通路矩阵法将失效.辽宁工程技术大学提 出的深度优先搜索法,按照普通的搜索策略也不能解决含有单向回路的通风网络查找通路的问题,通过修 改寻边策略也可以适应含有单向回路的通风网络. 212 “ 通路树深度优先生长 ”法确定通路的原理 为了增加算法的适应性,将多源多汇型通风网络通过加虚分支和虚节点变为单源单汇型通风网络,后 829 第8期魏连江等通风网络拓扑理论及通路算法研究 面提到的通风网络都指单源单汇型通风网络. 通风网络中任意两通路的交集非空, 1棵树从树根到树叶的路径的交集也非空,根据这些相似性质, 若把所有的节点通路相同的部分合并在一起作为树干枝,就形成了1棵节点通路树,但是,这是1棵特殊 的树,树根均为通风网络的进风节点,树叶均为回风节点,树枝与树枝的交点对应着通路的节点,这棵树 有别于图GE, V的1棵生成树,这样就可以模拟树的生长,“ 搜索 ”通路. 节点树的生长过程是 “ 同胚深度优先生长 ”的过程.设定树生长从树根及干枝开始,然后,遵循 “ 先枝后叶 ”原则,也就是说,树根生成后,再生成一干枝,树干枝生成后,总是从末端树枝节点朝一方 向生长出新的若干树枝,再生长树叶,树叶生长后,再从末端树枝节点朝另一方向生长,若不能生长,再 朝其余方向生长,若各方向均不能生长,后退一枝节点开始枝叶生长,⋯⋯,退到树根时开始另一干枝生 长,再重复前述生长过程,若不能生长出干枝,生长终止.从节点树的叶节点开始向根部寻找,即可找出 所有通路. 下面分析含有单向回路的通风网络中任意两节点间所有通路的确定过程.当图中存在单向回路时,如 图1所示,节点v3, v4, v7,v5,v3之间存在单向回路,PTDFG法将无法工作,为了解决这个问题,对PT2 DFG法进行了改进.从图2中可以看出,由于存在单向回路,节点v3与其自己的祖先节点v3重复.针对 这一特点,在实现寻找每个节点的子节点时,都将该子节点与其祖先节点进行比较,如果有重复,证明该 通风网络图中存在单向回路,那么这条路径就到此重复节点停止寻找其子节点.如果没有重复,证明该通 风网络图中不存在单向回路.如图2所示,终止节点为v3的通路,而非要求通路终止节点v8,所以不是 符合要求的通路,因而在图2中只能确定e1→e5→e9,e1→e6→e9,e2→e3→e7→e10三条通路. 213 “ 通路树深度优先生长 ”法的特点 “ 通路树深度优先生长 ”法可以计算通风网络任意2节点间的所有通路,该方法模拟树的生长规律找 出所有的通路,理论简单,便于实现,计算复杂度较小,效率较高,可靠性和适应性非常强,不仅适用于 无单向回路的通风网络和有单向回路的通风网络,还适用于单源单汇型的通风网络和多源多汇型通风网 络. 3 结 论 1提出了假拓扑通风网络、真拓扑通风网络和虚拓扑通风网络的概念,从通风网络拓扑理论方面 解释了风网解算后会出现反向分支的原因. 2给出了假拓扑通风网络、真拓扑通风网络的自动生成思路和基于真拓扑通风网络自动生成通风 网络图的解决办法,对通风网络拓扑理论及其应用有一定意义. 3基于真拓扑通风网络提出了确定通风网络任意两节点间所有通路的 “ 通路树深度优先生长 ”法, 该法根据矿井通风网络的特点,模拟树的生长规律找出所有的节点通路,理论简单,计算复杂度较小,可 靠性和适应性强,对于理论研究及程序设计有很好的借鉴作用. 929 煤 炭 学 报 2008年第33卷 参考文献 [1] 苏清政,刘 剑.矿井通风仿真系统理论与实践[M ].北京煤炭工业出版社, 2006. Su Qingzheng, Liu Jian.Theory and practice of mine ventilation simulation system [M ].China Coal Industry Publishing House, 2006. [2] 魏连江,王德明,王 琪,等.构建矿井通风可视化仿真系统的关键问题研究[J ].煤矿安全, 2007 7 6 - 9. WeiLianjiang, WangDeming, Wang Qi, et al .Study on some key issues of constructing visual mine ventilation simulation system [J ].Safety in CoalMines, 2007 7 6 - 9. [3] 倪景峰.矿井通风仿真系统可视化研究[D ].阜新辽宁工程技术大学, 2004. Ni Jingfeng .The study on visualization ofmine ventilation simulation [D ].Fuxin Liaoning TechnicalUniversity, 2004. [4] 魏连江,王德明.基于构件的矿井通风安全管理系统的开发研究[J ].中国矿业, 2006, 15 12 25 - 27. WeiLianjiang, WangDeming .Study on the mine ventilation and safety management system developments base on component [J ]. ChinaMiningMagazine, 2006, 15 12 25 - 27. [5] 周福宝,王德明.网络解算分支反向原因剖析及调节[J ].矿业安全与环保, 2000, 27 4 37 - 38. Zhou Fubao, WangDeming . Analysison reversing cause of network resolution branch and its adjust ment [J ]. Mining Safety Environmental Protection, 2000, 27 4 37 - 38. [6] 倪景峰,刘 剑,李雨成.矿井通风网络可视化拓扑关系建立和维护[ J ].辽宁工程技术大学学报, 2004, 23 12 724 - 726. Ni Jingfeng, Liu Jian, Li Yucheng .Establishment of topology relationships and maintenance of visualization of mine ventila2 tion network [J ]. Journal ofLiaoning TechnicalUniversity, 2004, 23 12 724 - 726. [7] 段 东.矿井通风系统拓扑关系自动生成的研究及风网解算[D ].阜新辽宁工程技术大学, 2005. Duan Dong .The automatic establishment ofmine ventilation system topology relation and ventilation network calculation [D ]. Fuxin Liaoning TechnicalUniversity, 2005. [8] 吴 兵,卢本陶,水林娜.用最长路径法自动生成通风网络图[J ].煤矿安全, 2006 6 1 - 3. Wu Bing, Lu Bentao, ShuiLinna. Automatic generation of ventilation network graph by longest path algorithm [J ].Safety in CoalMines, 2006 6 1 - 3. [9] 贾进章,郑 丹,刘 剑.通风网络中通路总数确定方法的改进[J ].辽宁工程技术大学学报, 2003, 22 1 4 - 6. Jia Jinzhang, ZhengDan, Liu Jian.I mprovementof determination ofpath quantity in ventilation net work [J ]. Journal ofLiaoning TechnicalUniversity, 2003, 22 1 4 - 6. [10 ] 刘 剑,贾进章,刘 新.用独立通路法确定矿井通风网络的极值流[J ].辽宁工程技术大学学报, 2003, 22 4 433 - 435. Liu Jian, Jia Jinzhang, Liu Xin. Determination ofmine ventilation networkmax2flow based on independentpaths [J ]. Jour2 nal ofLiaoning TechnicalUniversity, 2003, 22 4 433 - 435. [11 ] 陈长华.用通路法确定通风网络最优断面与风压[J ].辽宁工程技术大学学报, 2003, 22 4 448 - 449. Chen Changhua. Applying path to deter mine optimal cross section and ventilation press in ventilation net work [J ]. Journal ofLiaoning TechnicalUniversity, 2003, 22 4 448 - 449. [12 ] 刘 剑,贾进章,郑 丹.基于独立通路思想的风网平衡图绘制数学模型研究[J ].煤炭学报, 2003, 28 2 153 - 156. Liu Jian, Jia Jinzhang, ZhengDan. Study ofmathematicalmodelof plotting of equilibrium of ventilation network based on in2 dependent path idea [J ]. Journal of China Coal Society, 2003, 28 2 153 - 156. [13 ] 刘 剑,贾进章,于 斌.通风网络含有单向回路时的通路算法[J ].辽宁工程技术大学学报, 2003, 22 6 721 - 724. Liu Jian, Jia Jinzhang, YuBin. Algorithm of ventilation net workwith unidirectional circuit [J ]. JournalofLiaoning Techni2 calUniversity, 2003, 22 6 721 - 724. 039