煤矿巷道中无线传感器网络的可靠路由算法

胡长俊，洪炎，唐超礼，钟鸣宇，姚善化

安徽理工大学电气与信息工程学院，安徽淮南 232001

煤矿巷道中无线传感器网络的可靠路由算法

胡长俊，洪炎，唐超礼，钟鸣宇，姚善化

安徽理工大学电气与信息工程学院，安徽淮南 232001

1 引言

可靠有效的井下监测系统对我国的煤矿生产安全有重要意义。无线传感器网络（WSN）具有灵活、廉价、低功耗、自组织的特点，在煤矿井下空间有着广阔的应用前景[1-2]。

路由是WSN的重要技术之一，对网络性能影响很大[3]。目前针对井下通信环境中无线传感器网络的路由技术已经有了一定的研究。文献[4]采用非均匀分簇策略，提出一个簇规模自适应调节的能量均匀分簇路由协议。文献[5]提出一种基于位置估计的多跳路由协议，选择恰当的移动节点作为转发节点，延长信标节点的生存时间。文献[6]提出一种综合优化的分簇路由协议，采用“局部协商”策略减少路由重叠，改善了簇头分布及热区问题。文献[7]提出一种基于位置信息和网络梯度的贪婪型路由算法，解决了节点走出空洞及如何选择下一跳节点的问题，算法有较好扩展性。文献[8]分析了LEACH协议应用于井下环境的优势与不足，提出了适合于井下的LEACH-I协议。李辉等[9]将煤矿井下监测节点分布简化为链式2层拓扑结构，利用无线信号模型寻找使每回合能耗最小的最优簇数，同时利用设备排列的有序性引入虚拟地址的方法来分簇，提出了基于虚拟地址的能量有效路由协议。梁莹等[10]根据井下通信环境较差的情况，提出多路径的传输方式。文献[11]在传统的AODV路由思想基础上提出了一种基于最小跳数的相交多路径路由算法，均衡了网络能耗。文献[12]提出一种基于信标路由协议；文献[13]提出的CWU MSN用于监测井下环境和矿工位置，文中还讨论了一种最少密度簇头节点布置策略。TEEN[14]采用了一定措施提高路由效率，延长网络寿命。

以上算法分别从路由的可靠，减少节点能耗，延长网络的生存期等某方面考虑而不能兼顾其他因素。井下通信环境要求传感器网络必须在满足实时、可靠的同时，兼顾网络的使用寿命。本文在对以上路由算法和数据可靠传输方法分析基础上，针对井下巷道的环境特点，提出了一种多跳可靠路由算法。和其他同类算法相比，本文的算法具有传递时延小，路由可靠性强，容易实现等特点。

2 问题描述与系统模型

本文把井下巷道空间近似看成长方体区域，假设传感器节点等距离部署在井下巷道的两侧等高的两条水平线上，每个节点与另一侧与其位置对应节点的连线与巷道侧壁垂直，sink节点位于巷道的一头，信息源节点通过巷道两边的节点以多跳的方式传递信息到sink节点。在井下巷道环境中，当电磁波沿着巷道的一边侧壁传递时，受巷道表面的结构和材质影响，信号衰减较大，传播距离有限，为了减少能耗，本文采用不同侧节点交替传递的方式，如图1所示。节点电磁波传递模型与自由空间模型类似。同时，为了减少节点转发次数和到达sink节点的时间，降低信息传输的平均能耗，发送节点尽可能和通信范围内较远的接收节点通信。

图1 巷道内节点部署及消息传递

假设DIS(Va，Vb)表示节点a，b的距离，DIS(Va，sink)表示节点Va到sink的距离，节点的通信半径为R，给出以下定义。

定义1节点的有效接收节点，对节点Vi而言，其有效接受节点为集合{Vj|DIS(Vi，Vj)＜R且DIS(Vj，sink)＜DIS(Vi，sink)，且Vj与Vi不在巷道同一侧}。

每个节点往往有多个有效接受节点，为了防止多个节点转发相同的信息，造成后续节点接收信息冲突以及无谓的能量损耗，本文采取节点屏蔽措施，即每个节点接收到信息后根据自己的位置信息和剩余能量确定一个等待时间T，在等待时间后再发送信息；如果在等待时间T之内收到其他节点的信息，则表示信息已经被其他节点转发，节点放弃发送。接收节点收到信息后，按照公式（1）确定自己的等待时间T：

其中Er为节点剩余能量。本文规定当节点剩余能量Er达到初始能量Eo的5%时，发出告警信息提示更换节点，同时不再转发其他节点信息，对其他节点视为失效。c1、c2两个因子分别表示节点的接收角度和剩余能量在决定等待时间T中所占的比重，具体取值要在实际环境下通过仿真实验测试得出。一般在网络初始阶段，节点剩余的能量相对充足，主要考虑节点的位置因素，而随着系统的运行，节点能量因素所占比例越来越大。由于发射节点对面的节点接收角度为90°，规定对面节点的等待时间为有效接收节点等待时间的最大值Tmax。

从式（1）可知，对于那些接收角度较小，剩余能量多的节点，等待时间T较短，优先被确定为转发节点发送信息，算法兼顾了消息传递时延和节点的能耗均衡。

如图1所示，b、c、d是节点a的有效接收节点，收到a的信息后，b节点由于接收角度较小，等待时间短，优先转发信息，c、d节点在各自的等待时间T内收到b的信息后放弃发送，a收到b的信息则确定信息已经被b转发。

由于井下通信环境的特殊性，为了保证节点通信路由的可靠，当接收节点失效时，算法采用路由切换的方式继续路由过程。

如图1所示，当节点m转发信息后，其有效接收节点（图中阴影表示）都已失效，其对面的节点n收到m的转发消息后，启动一个定时器Tmax，如果在Tmax内没有收到其他节点转发的有效信号时，则节点b将信息转发给自己的有效接收节点，继续多跳传递过程。节点a收到对面节点b的转发信息后即知道自己的有效接收节点都已失效，立即发出告警，提示替换失效节点，在新节点补充前临时增大发射半径为NR(N=2，3)以保证路由功能。如果节点b也没有有效的接收节点（在b的有效接收节点等待时间T内没有收到回应），也采取临时增大发射半径、告警提示替换失效节点等措施。新的节点部署后，立即向周围发送广播信息，通知以新节点为有效接收节点的节点恢复原来的发射半径R，即图1中替换失效节点的新节点会通知m节点恢复原来的发射半径R。

3 路由算法过程

节点部署完成后进行初始化，每个节点获得左右相邻和正对面位置节点的信息，包括节点ID和坐标。检测到信息的源节点以半径R向周边发送信息，根据上文中的描述，接受到信息的节点处理过程为：

步骤1首先判断信息是否来自对面的节点的消息，如果不是，转步骤2；否则进一步判断信息是否是重复信息，如果不是设置等待时间Tmax，并转步骤5；否则发出告警提示补充节点，转步骤7。

步骤2如果自己不是消息的有效接收节点，直接转步骤7；否则转步骤3。

步骤3根据收到信息计算接收角度θ和等待时间T。

步骤4如果在T内收到其他节点转发的相同信息则丢弃，转步骤7；否则转步骤6。

步骤5如果在Tmax内收到其他节点转发的信息则丢弃信息，转步骤7；否则转步骤6。

步骤6以半径R发送信息。

步骤7结束。

节点发送消息的格式为：

（节点ID，节点坐标，发射半径，消息ID，消息内容）

每个节点在转发消息前会在消息内加入自己的ID、坐标信息即发射半径。接收节点用这些内容判断有效接收节点和计算等待时间。一个信息源节点产生的消息ID在整个传递过程不变，这样既可以把不同的消息区别开，也能防止对重复消息处理。

4 算法性能分析

4.1 单次消息传递跳数分析

消息传递跳数和节点的部署密度及节点的位置都有直接关系，在实际应用时，可以采用平均等距的节点部署方式，假设节点的传递模型为自由空间模型，在事先确定节点通信半径R的前提下，可以将节点的有效接收节点置于节点通信半径位置处，如图2所示。

图2 节点等距部署时消息传递过程

设源节点S距离sink节点的距离为L，巷道宽为W，则消息从源节点传递到sink节点经过的跳数H为：

当有效接收节点失效时，启动路由切换过程，消息传递跳数加1，在最坏情况下单次消息传递跳数为O(H)。

4.2 单次消息的路由时间分析

由4.1节分析知，在一般情况下，巷道中没有失效节点时，单次消息路由时间由跳数H决定。由公式（1）知，在节点能量差别不大的情况下，由于有效接收节点位置固定（如图2），节点转发的时间T也是固定的。

节点的接收角度为：

在最坏情况下，消息每经过一次转发就启动路由切换过程，即一半节点通过路由切换转发消息，则路由的总时间Trout_time为：

当失效节点数更多时，可能会使有些节点增加通信半径，路由时间减少；也可能造成路由失败。

5 仿真与结果分析

为了检验算法的效果，在上文所述网络模型基础上使用NS2仿真工具对算法进行了仿真。节点通信模型采用自由空间模型，不考虑节点传输中的相互干扰及时间同步问题，MAC层采用802.15.4协议，信道使用的参数如表1所示，主要考察算法的消息成功传递的概率、路由平均时延等方面的性能，并与文献[4-5，8，13]提出的路由算法在同等环境下分别做了比较。

表1中的发射数据能耗和接收数据能耗是在半径R内的能耗值，当发射距离和接受距离超过半径R时，节点能耗的计算采用文献[15]描述的方法。公式（1）中c1、c2参数都取0.5。

表1 节点参数设置表

5.1 路由的平均时间

本文用源节点的信息到达sink节点经过中间节点转发的次数来表示路由的时间。仿真环境中节点数取50～100，从监测区域中随机设10个信息源点，取形成的10个路由上节点转发次数的平均值作为分析对象，结果如图3所示。

图3 路由转发次数比较

由图3中所示，本文提出的算法平均转发次数基本在25次以下，这是由于算法倾向选择通信距离较远的节点，当点数较少时，节点的有效接收节点相对偏少，会出现借助于对面的节点转发及增加通信半径转发的情况，转发次数增加。而文献[4]的分区算法的转发次数和分区数直接相关，而分区数是按照节点的能耗、节点数目及巷道长度确定的，与节点的通信半径无直接关系，当节点密度达到一定要求，路由平均次数变化不大。其他三种算法更多考虑节点能耗的均衡，平均转发次数明显多于本文算法的转发次数。

5.2 成功传递率

传感器节点数取50～100，在监测区域中随机取50个信息源点，分别在几种算法运行过程中统计50个源点产生的消息成功传递到sink节点的次数（每个源点成功传递次数取10次运行的平均值），结果如图4所示。

图4 成功传递率比较

从图4可以看出，随着节点数的增加，文献[4]的分区算法中，节点数较少时，路由容易出现中断，成功传递次数偏低；随着节点数增加，成功传递次数也相应增加。文献[5]使用了移动节点作为中转，带有一定随机性，成功传递的次数低于其他算法。文献[8]选择路由节点主要考虑转发所消耗的能量及节点的剩余能量因素，节点数较少时成功传递率与文献[4]接近。文献[13]提出的方法得到的成功传递率总体介于以上三种方法之间。而本文算法中的消息成功传递次数则基本在45次以上，与节点数无关，原因是提出的算法采用了路由切换和增加通信半径等手段保证了成功传递概率，对不同节点数目的网络有很好的适应性，能满足井下通信可靠性的要求。

6 结束语

本文结合井下巷道的实际环境提出了一种无线传感器网络路由方法。节点在巷道两侧等距部署，采用对边节点多跳的通信方式传递信息到sink节点。按照节点的位置和能量确定下一跳转发节点，减少了传递能耗和时间，在节点失效时利用路由切换技术增加路由的可靠性。仿真结果说明了算法的有效性，其更适用于井下巷道环境对信息的实时传递和可靠性的要求。今后，将在本文算法基础上进一步均衡节点的能耗，延长网络的生存期。

[1]孙利民，李建中，陈渝.无线传感器网络[M].北京：清华大学出版社，2005.

[2]周公博.面向窄长空间的无线传感器网络可靠性关键技术研究[D].徐州：中国矿业大学机电工程学院，2010.

[3]沈波，张世永，钟亦平.无线传感网网络分簇路由协议[J].软件学报，2006，17（7）：1588-1600．

[4]吴华君，张自力，李卫.一种适用于煤矿井下无线传感网的能量均衡路由协议[J].计算机科学，2011，38（4）：145-150．

[5]乔刚柱，曾建潮，赵明.基于位置估计的井下无线传感器网络路由算法[J].系统工程理论与实践，2011，31（10）：175-180.

[6]吕振，孙延飞，李亚杰，等.一种综合优化的矿用无线传感器网络路由协议[J].传感器与微系统，2010，29（4）：74-77.

[7]童敏明，杨礼现，刘晓文，等.矿井无线传感器检测网络路由改进算法的研究[J].传感技术学报，2008，21（11）：1892-1895.

[8]吴青，张申，李曙俏，等.一种应用于煤矿井下LEACH路由协议的改进[J].传感器与微系统，2012，31（4）：23-25.

[9]李辉，张晓光，刘颖.基于煤矿设备有序拓扑的能量有效路由协议[J].中国矿业大学学报，2011，40（5）：774-780.

[10]梁莹，李晓，张记龙，等.井下无线通信网络路由快速建立的方法[J].煤炭科学技术，2011，39（8）：93-96.

[11]高莺.矿山井下无线传感器网络多径路由协议的研究[D].北京：北京交通大学，2010.

[12]Sun Zheng，Zhang Xiaoguang，Li Hui，et al.The application of TinyOS beaconing WSN routing protocol in mine safety monitoring[C]//Proceedings of 2008 IEEE/ASME International ConferenceonMechtronicandEmbeddedSystemsand Applications（MESA）.Piscataway：IEEE Press，2008：415-419.

[13]Chen Guangzhu，Zhu Zhencai，Zhou Gongbo，et al.Sensor deployment strategy for chain-type wireless underground mine sensor network[J].Journal of China University of Mining and Technology，2008，18（4）：561-566.

[14]Manjeshwar A，Agrawal D P.TEEN：a routing protocol forenhanced efficiency in wireless sensor networks[C]//Proc of the 15th International Parallel and Distributed Symposium，San Francisco，CA，USA，2001：2009-2015.

[15]杨光松，肖明波，程恩.水声传感网中节省能量的寻路机制[J].北京邮电大学学报，2009，32（4）：88-92.

HU Changjun,HONG Yan,TANG Chaoli,ZHONG Mingyu,YAO Shanhua

School of Electric and Information Engineering,Anhui University of Science and Technology,Huainan,Anhui 232001,China

A routing algorithm of Wireless Sensor Network（WSN）is proposed for roadway in coal mines according to its working environment.Firstly,the algorithm determines the optimal forwarding node based on the location and remaining energy of the node,which shortens the time to deliver the message in the multi-hop route and balances the node energy consumption.When nodes fail in the routing process,the algorithm,using routing switching technology,generates complementary route to continue the routing procedure through the opposite side of the node,greatly increases the reliability of routing.Simulation and analysis show that,compared with other typical partitioning algorithm for the roadway,the route generated from the algorithm has a shorter latency and a higher data transfer rate and is more suitable for the coal mines environment.

Wireless Sensor Network（WSN）;routing;multi-hop delivery;switch

根据井下巷道的实际工作环境，提出了一种适用于井下巷道的无线传感器网络路由算法。算法根据接收节点的位置和剩余能量来确定最优转发节点，既减少了多跳路由传递的时间又均衡了节点能耗；算法在路由过程中节点失效时利用路由切换技术，通过对侧的节点形成互补路由来继续路由过程，大大增加路由的可靠性。仿真实验及分析表明，与其他典型的井下巷道分区算法相比，该算法生成的路由有更短的时延和更高的数据传递率，适合于井下巷道环境。

无线传感器网络；路由；多跳传递；切换

A

TP393

10.3778/j.issn.1002-8331.1305-0498

HU Changjun,HONG Yan,TANG Chaoli,et al.Reliable routing protocol of wireless sensor networks for roadway in coal mines.Computer Engineering and Applications,2013,49（19）：96-99.

国家自然科学基金（No.51274011，No.51104003）；安徽高校省级自然科学研究重点项目（No.KL2011A077）；安徽高校省级自然科学研究项目（No.KJ2012Z083）。

胡长俊（1973—），男，讲师，主要研究方向为无线传感器网络；洪炎（1979—），男，副教授，主要研究方向为计算机监控技术；唐超礼（1980—），男，副教授，主要研究方向为井下通信技术；钟鸣宇（1982—），男，讲师，主要研究方向为信号处理；姚善化（1967—），男，博士，教授，主要研究方向为井下通信技术。E-mail：601254090@qq.com

2013-06-04

2013-08-01

1002-8331（2013）19-0096-04

◎数据库、数据挖掘、机器学习◎