图1 煤矿WMSN系统模型
王慧1， 杨维1， 刘俊波2
(1.北京交通大学 电子信息工程学院， 北京 100044；2.中煤科工集团常州研究院有限公司， 江苏 常州 213015)
摘要：针对煤矿井下多媒体信息采集需求及巷道带状空间与传感器网络中节点能量受限的特点，构建了煤矿无线多媒体传感器网络(WMSN)系统模型，提出了一种由基于位置与剩余能量的虚拟网格中层次分簇 (PREHCVG) 算法及基于能量与距离的蚁群路由(EDACR)算法构成的煤矿WMSN能量均衡路由方法。该方法中，PREHCVG算法根据网络中节点的通信半径对节点进行虚拟网格划分来实现分簇管理，并结合节点的剩余能量及所处位置信息选取簇头节点；EDACR算法根据节点的剩余能量及节点间距离信息，从簇头节点及备选簇头节点中选出路由节点。仿真结果表明，与经典LEACH算法相比，煤矿WMSN能量均衡路由方法能够有效均衡WMSN中节点的能量消耗，减少WMSN中能量耗尽的节点数，延长WMSN生命周期。
关键词：煤矿井下； 无线多媒体传感器网络； 分簇算法； 路由算法； 能量均衡
传统的无线传感器网络(Wireless Sensor Network, WSN)在井下环境监控和人员定位等方面得到了广泛研究与应用[1-3]。相比于传统WSN，无线多媒体传感器网络(Wireless Multimedia Sensor Network, WMSN)能感知信息量更丰富的视频、音频、图像等多媒体信息[4-6]，从而实现更加细粒度且精准的环境信息监控，是实现煤矿环境多媒体信息监测、保障煤矿生产安全的有效方式[7-8]。
煤矿WMSN传感器节点由自带电池供电，能量十分有限，并且WMSN通信方式以数据为中心[9]，在感知数据的同时还要为邻居节点承担路由功能，这将消耗大量能量。因此，如何设计有效的路由方法，节约各节点有限的电池能量，并且尽可能地延长整个网络的生命周期，成为煤矿WMSN发展待解决的关键问题。煤矿井下巷道狭长的受限空间特性使WMSN节点呈带状分布，且巷道壁对电磁波的散射、衍射等导致的多径效应造成频率选择性衰落，使得单跳链路传输无法适应这样复杂的环境。分簇多跳网络比平面网络结构更适应井下网络传输需求[10]。
在分簇多跳网络中，若簇头节点存在位于边缘区域、分布不均匀或距离簇内节点较远等问题，将无法完全覆盖煤矿井下长直巷道区域，不利于通信。另外，簇头节点在整个传输过程中消耗大量能量，若选取不合理，部分节点将出现过早“死亡”的现象，导致在多跳传输过程中出现网络拓扑断裂，即“能量空洞”问题。文献[11]提出了基于LEACH的改进WSN路由协议，利用粒子群算法良好的收敛性和全局优化能力，将整个网络区域合理分割成多个子区域，并改进了簇头选取方法，降低了网络能耗，但该路由协议不适用于节点呈带状分布的煤矿井下狭长巷道内，并且没有考虑节点间有效的通信距离。文献[12]对煤矿井下传感器节点的有效传输距离加以考虑，提出了基于虚拟网格的多跳路由协议，适用于煤矿井下狭长的矩形巷道空间，并且避免了每一轮簇重组过程中节点的能量消耗，但在数据传输过程中没有对节点的“能量空洞”问题进行有效改进。
针对煤矿WMSN的复杂性、多点性及煤矿井下狭长结构造成的多跳传输过程中节点能耗不均衡问题，提出了一种煤矿WMSN能量均衡路由方法。该方法由基于位置与剩余能量的虚拟网格中层次分簇 (Position and Residual Energy based Hierarchy Clustering in Virtual Grids，PREHCVG) 算法及基于能量与距离的蚁群路由 (Energy and Distance based Ant Colony Routing，EDACR) 算法2个部分组成。实验验证了该方法能够有效均衡煤矿巷道带状区域中的节点能量消耗。
煤矿WMSN系统模型主要由地面监控中心、监控总线及井下WMSN 3层体系结构组成，如图1所示。多媒体传感器节点将各种监测信息传送至簇头节点，簇头节点将数据按照多跳方式传输至Sink节点，Sink节点将监控信息传送至地面监控中心，从而实现对煤矿井下环境的全面监测。
图1 煤矿WMSN系统模型
假设图1中井下巷道宽为a，高为b，长为L。煤矿WMSN区域由1个Sink节点、多个簇头节点和多个普通多媒体传感器节点构成，Sink节点位于WMSN区域中靠近地面监控中心的位置，多媒体传感器节点和簇头节点随机散布在整个矿井巷道内。以Sink节点为原点建立坐标系[13]，巷道宽度方向为x轴，巷道高度方向为y轴，巷道长度方向为z轴。
为了解决煤矿WMSN中节点通信时数据丢失或通信路由受限等问题，为节点选取有效的通信半径。以GAF分簇算法[14-15]为基础，提出PREHCVG算法。
2.1 煤矿WMSN虚拟网格划分
假设煤矿WMSN中节点的有效通信半径为R，根据节点通信半径和位置信息，整个传感器网络被划分为多个长度为s的虚拟网格。为确保相邻虚拟网格中的所有节点之间能够相互访问，需满足关系式：
a2+(2s)2+b2≤R2
(1)
(2)
矩形巷道可以划分为[L/s]([]表示向上取整，如[3.5]=4)个虚拟网格。
2.2 簇头选取过程
以虚拟网格为单位选取簇头节点。LEACH算法选取簇头的随机性导致簇头存在位于边缘区域或过于密集等问题。PREHCVG算法中簇头节点的选取过程要评估虚拟网格内每个节点的能量情况及本节点与其余节点间距离信息。假设图1中所考虑虚拟网格内所有节点为S1,S2，…，Sn(n为节点数)，这些节点均可感知其余节点的能量、位置信息，并能够计算自身与其余节点间的距离。引入权值参数：
(3)
式中: ξ为节点剩余能量因子；Ei为节点Si当前剩余能量，i=1,2,…,n；
为同一虚拟网格内节点的平均剩余能量；ζ为节点距离因子，一般情况下ξ+ζ=1；
为节点Si与同一虚拟网格内其余节点间的平均距离。
从式(3)可看出，权值fi由2个部分组成：第1部分考虑了平均能量因素，使能量消耗低的节点成为簇头节点的概率增大；第2部分表示网络的均衡度，使与所有其余节点间距离小的节点成为簇头节点的概率增大。因此，传统LEACH算法中的阈值公式[11]可修改为
(4)
式中：p为簇头节点占所有节点的比例；g为已经完成的选取簇头节点的轮数；G为多轮选取簇头节点后仍未被选为簇头节点的节点集合。
在选取簇头节点时，节点S1,S2,…,Sn各自产生1个[0,1]间的随机数P1,P2,…,Pn，并根据式(4)计算阈值Ti。将Pi比各自Ti小的节点作为该虚拟网格内备选簇头节点，记为C1,C2,…,Cm(m为备选簇头节点数)。节点C1,C2,…,Cm在该虚拟网格内宣布自己成为备选簇头节点，之后以广播的方式向该虚拟网格内节点发送自己的能量信息、ID标志和位置信息。各备选簇头节点将自身的能量信息与接收到的其他备选簇头节点的能量信息进行比较，若自身能量小于其他备选簇头节点的能量，则自身依然作为备选簇头节点。经过一轮比较后，最终确定剩余能量最多的一个备选簇头节点为该虚拟网格内本轮的簇头节点，记为Cmax。Cmax将确定的簇头身份、位置信息、能量信息广播至虚拟网格内其他节点。其余Pi比各自Ti小的节点作为下一轮的备选簇头节点，记为C1,C2,…,Cm-1，并按照剩余能量大小编制备选ID，作为簇头节点能量消耗至自身能量70%时的备用选项。Pi比各自Ti大的节点作为该虚拟网格内普通多媒体传感器节点，记为S1,S2,…,Sn-m，与簇头节点进行数据传输。
PREHCVG算法簇头选取流程如图2所示。
图2 簇头选取流程
各普通多媒体传感器节点S1,S2,…,Sn-m收到簇头节点Cmax广播后，将自身信息返回至簇头节点。待簇头节点收集所有传感器节点信息后，建立簇内传感器节点通信的时分多址(Time Division Multiple Access，TDMA)列表，并将该表信息广播至普通多媒体传感器节点S1,S2,…,Sn-m。TDMA列表建立流程如图3所示。
2.3 簇内数据传输
图1中所考虑虚拟网格内的普通多媒体传感器节点S1,S2,…,Sn-m以TDMA列表时隙为标准，未到本节点时隙时处于休眠状态，到达本节点时隙就将自身收集的数据传输至簇头节点Cmax。簇头节点收集信息后，对其进行融合并发送至各备选簇头节点C1,C2,…,Cm-1。各虚拟网格内的数据传输均按照上述方式进行。
采用煤矿WMSN EDACR算法在各簇头节点与备选簇头节点间选出路由节点，数据通过路由节点以多跳方式发送至Sink节点。EDACR算法主要由以下5个部分组成。
(1) 搜索范围。WMSN中节点众多，为避免传感器节点在计算、路由存储等过程中消耗大量能量，以相邻虚拟网格内簇头节点及备选簇头节点作为EDACR算法中当前路由节点的下一跳路由节点搜索范围。如图1所示，所考虑虚拟网格内节点C1,
图3 TDMA列表建立流程
C2,…,Cm-1及Cmax为上一个虚拟网格内已选路由节点C′的搜索范围。
(2) 判定能量表。各路由节点开始选择路径前，记录搜索范围内所有节点的剩余能量，建立各自的判定能量表。该表反映了路由节点对某一路径进行选择后，对搜索范围内其余节点路径选择的影响，并对判定能量表中信息进行实时更新。图1中，所考虑虚拟网格的上一个虚拟网格内所选取的路由节点C′确定下一目的地前，记录所考虑虚拟网格内m个簇头节点与备选簇头节点的剩余能量，记为E1,E2,…,Em。节点C′每转移1次，判定能量表中E1,E2,…,Em的值都会更新1次。判定能量表中节点发送、接收及融合数据的能量采用第一顺序无线电能量模型进行计算。
(3) 转移概率公式。在转移过程中考虑下一跳节点剩余能量因素，避免总体能量较高时某些节点过快“死亡”，即尽量降低低能量节点与远距离节点通信及融合数据的概率，使低能量节点趋向于选择节约自身能耗的路径，高能量节点消耗较高能量，从而实现网络整体最优。煤矿WMSN节点转移概率为
(5)
式中：τC′Cj(t)为t时刻上一虚拟网格内路由节点C′与所考虑虚拟网格内备选簇头节点Cj(j=1,2,…,m)之间路径上的剩余信息素；α为剩余信息素系数；ηC′Cj(t)为t时刻节点C′与节点Cj的启发因子；β为启发因子系数；ECj为节点Cj当前剩余能量。
(6)
式中：λ1，λ2为距离因子；dC′Cj，dCjSink分别为节点C′与节点Cj、节点Cj与Sink节点间的通信距离。
EDACR算法与传统的蚁群算法相比，不仅考虑了下一跳节点的剩余能量，还考虑了当前节点到下一跳节点、下一跳节点到Sink节点的距离，并且用距离因子λ1，λ2来约束节点C′与节点Cj、节点Cj与Sink节点间的通信距离。适当设置λ1，λ2能够进一步对全局路径进行优化。
(4) 信息素更新。为避免剩余信息素的累积造成路径选择错误，每完成一次或全部下一跳路由节点的选取后，要更新每条路径上的剩余信息素。t+1时刻(C′,Cj)路径上的剩余信息素τC′Cj(t+1)可按式(7)—式(9)处理。
τC′Cj(t+1)=(1-ρ)τC′Cj(t)+ΔτC′Cj(t)
(7)
(8)
(9)
式中：ρ为信息素挥发系数，为防止信息无限积累，ρ取值为[0,1]，1-ρ表示信息素的剩余系数；w为蚂蚁总数；
为[t,t+1]内第k只蚂蚁在(C′，Cj)路径上的累加信息素；Q为常量，表示完成任务后在经过的路径上所释放的信息素总量。
(5) 最优函数。第k只蚂蚁通过所选路径到达Sink节点后，统计最优函数：
(10)
式中
为第k只蚂蚁所经路径上节点的平均剩余能量；lk为第k只蚂蚁所经路径的总长度。
从每一个节点的k只蚂蚁中选取拥有最优函数Fk的蚂蚁，将其路径作为本次迭代的最优路径。
基于PREHCVG算法和EDACR算法的煤矿WMSN数据传输流程如图4所示。
为验证PREHCVG算法及EDACR算法在煤矿井下巷道狭长空间的有效性，采用Matlab对其进行仿真。图1中，设L=150 m，a=3 m，b=3 m，巷道内随机布置100个传感器节点，以Sink节点为原点建立坐标系。具体仿真参数见表1。
煤矿WMSN采用PREHCVG算法与经典
图4 煤矿WMSN数据传输流程
表1 煤矿WMSN仿真参数
LEACH算法进行节点分簇时，网络生命周期如图5所示。可看出随着轮数增加，网络中存活的节点逐渐减少。采用LEACH算法时，当轮数达到约770时，煤矿WMSN存活的节点数开始减少；而采用PREHCVG算法时，存活节点在轮数达到约1 780时才开始减少，可见PREHCVG算法降低了网络中存活节点减少的轮数。
图5 采用不同分簇算法时煤矿WMSN生命周期
煤矿WMSN采用PREHCVG算法与经典LEACH算法进行节点分簇时，全网剩余能量如图6所示。可看出采用PREHCVG算法时，煤矿WMSN全网剩余能量曲线较采用LEACH算法时斜率低，即采用PREHCVG算法时全网能量消耗更加平均，算法作用时间更持久。对照图5可知，采用LEACH算法时，在约1 200轮后WMSN全网节点能量耗尽，而采用PREHCVG算法时在1 870轮左右全网节点能量耗尽。
图6 采用不同分簇算法时煤矿WMSN全网剩余能量
在煤矿WMSN中采用PREHCVG算法能够有效均衡网络中节点能量，延长网络生命周期。这是因为PREHCVG算法采用划分虚拟网格思想，减少了簇内普通传感器节点加入簇时能量的消耗，且在选取簇头时考虑了节点剩余能量与节点间距离信息，使能量较大的节点成为簇头的概率增大，优化了全网能量消耗。
设置煤矿WMSN中节点个数以30为步长增至300，每种情况重复50次实验。分别采用经典LEACH算法、文献[12]提出的矿井巷道层次性路由协议——MRPBVG算法及本文所提EDACR算法对煤矿WMSN数据进行传输，测试网络中出现节点“死亡”的平均轮数，结果如图7所示。可看出在节点数相同的情况下，采用EDACR算法时煤矿WMSN中节点存活的轮数最多。从图7(c)可以看出， EDACR算法减少了网络中“死亡”节点数目，当节点个数为240时， EDACR算法相较于LEACH算法延长网络生命周期约900轮，相较于MRPBVG算法延长网络生命周期约400轮。
煤矿WMSN采用EDACR算法可有效减少“死亡”节点数，延长网络生命周期。这是因为EDACR算法在选取下一跳路由时，添加了对下一跳路由节点能量及其与Sink节点间距离的考量，同时引入备选节点，均衡了网络中能量消耗，避免了网络拓扑断裂，即“能量空洞”问题的发生。
煤矿WMSN能量均衡路由方法在普通节点成簇管理过程中采用PREHCVG算法，在簇头节点与Sink节点通信路径选取过程中采用EDACR算法，有效均衡了网络节点的能量，减少网络中能量耗尽的节点数，延长网络生命周期，适用于煤矿狭长区域内密集部署的节点数据传输。
(a) 第一个节点“死亡”
(b) 半数节点“死亡”
(c) 全部节点“死亡”
图7 采用不同路由算法时煤矿WMSN出现节点“死亡”的平均轮数
参考文献：
[1] 胡青松,吴立新,张申,等.煤矿工作面定位WSN的部署与能耗分析[J].中国矿业大学学报,2014,43(2):351-355.
[2] 张然,李菲菲,张申,等.一种矿震监测的WSNs按需分层时间同步算法[J].中国矿业大学学报,2014,
43(6):1046-1050.
[3] SUN Yanjing,HE Yanjun,ZHANG Beibei,et al.An energy efficiency clustering routing protocol for WSNs in confined area[J].Mining Science and Technology,2011,21(6):845-850.
[4] MOWAFI M,AWAD F,ALJOBY W.Spatial correlation model for herogeneous cameras in wireless multimedia sensor netorks[C]// IEEE the 14th International Symposium and Workshops on "A World of Wireless, Mobile and Multimedia Networks", Madrid, 2013:1-6.
[5] WANG P, DAI R, AKYILDIZ I F. A differential coding-based scheduling framework for wireless multimedia sensor networks[J]. IEEE Transactions on Multimedia, 2013, 15(3):684-697.
[6] COLONNESE S, CUOMO F, MELODIA T.An empirical model of multiview video coding efficiency for wireless multimedia sensor networks[J].IEEE Transactions on Multimedia,2013,15(8):1800-1814.
[7] HOLMAN R, STANLEY J, OZKAN-HALLER T. Applying video sensor networks to nearshore environment monitoring[J]. IEEE Pervasive Computing, 2003, 2(4):14-21.
[8] 杨维,冯锡生,程时昕,等.新一代全矿井无线信息系统理论与关键技术[J].煤炭学报,2004,29(4):506-509.
[9] 周灵,王建新.无线多媒体传感器网络路由协议研究[J].电子学报,2011,39(1):149-156.
[10] 周公博,朱真才,陈光柱,等.矿井巷道无线传感器网络分层拓扑控制策略[J].煤炭学报,2010,35(2):333-337.
[11] 陈晓娟,王卓,吴洁.一种基于LEACH的改进WSNs路由算法[J].传感技术学报,2013,26(1):116-121.
[12] 王珊珊.LEACH路由协议的改进与基于矿井环境下的无线传感器网络路由协议的研究[D].南京：南京理工大学,2011.
[13] YUAN Fei,ZHAN Yiju,WANG Yonghua. Data density correlation degree clustering method for data aggregation in WSN[J].IEEE Sensors Journal,2014, 14:1089-1098.
[14] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[C]//Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, 2001:70-84.
[15] GROVER J,SHIKHA,SHARMA M.Optimized GAF in wireless sensor network[C]//The 3rd IEEE International Conference on Reliability,NFOCOM Technologies and Optimization,Noida,2014:1-6.
Energy balancing routing method for coal mine wireless multimedia sensor network
WANG Hui1, YANG Wei1, LIU Junbo2
(1.School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China; 2.CCTEG Changzhou Automation Research Institute, Changzhou 213015, China)
Abstract：According to multimedia information collection requirements and characteristics of confined band space in coal mine tunnel and limited energy of sensor nodes, a wireless multimedia sensor network (WMSN) system model of coal mine was built, and an energy balancing routing method for coal mine WMSN was proposed, which included a position and residual energy based hierarchy clustering in virtual grids (PREHCVG) algorithm and an energy and distance based ant colony routing (EDACR) algorithm. In the method, PREHCVG algorithm divides nodes into different virtual grid for cluster management based on communication radius of the nodes in the network, and selects cluster head nodes according to residual energy and location information of the nodes. EDACR algorithm selects routing nodes from cluster head nodes and alternative cluster head nodes according to residual energy and distance information of the nodes. The simulation results show that the energy balancing routing method for coal mine WMSN can effectively balance energy consumption of WMSN nodes, reduce the number of energy-exhausted nodes and prolong life cycle of WMSN compared to traditional LEACH algorithm.
Key words：coal mine underground; wireless multimedia sensor network; clustering algorithm; routing algorithm; energy balancing
文章编号：1671-251X(2017)05-0031-06
DOI：10.13272/j.issn.1671-251x.2017.05.008
收稿日期：2017-01-21；
修回日期：2017-03-20；责任编辑：李明。
基金项目：国家重点研发计划资助项目(2016YFC0801800)；国家自然科学基金资助项目(51474015，51274018)。
作者简介：王慧(1992-)，女，山东高密人，硕士研究生，研究方向为煤矿通信，E-mail:14120127@bjtu.edu.cn。
中图分类号：TD67
文献标志码：A
网络出版：时间：2017-04-25 17:52
网络出版地址：http://kns.cnki.net/kcms/detail/32.1627.TP.20170425.1752.008.html
王慧，杨维，刘俊波.煤矿无线多媒体传感器网络能量均衡路由方法[J].工矿自动化，2017,43(5)：31-36.