图1 UCERP非均匀分簇机制
黎望怀1, 夏旭1,2
(1.湖南安全技术职业学院 电气与信息工程系， 湖南 长沙 410151；2.中南大学 软件学院， 湖南 长沙 410075)
摘要：针对传统的单Sink节点无线传感器网络应用于煤矿安全监控系统中时，远离巷道口的传感器节点无法及时、准确地将巷道深处的监测数据传输到巷道口Sink节点的问题，提出一种适用于长带状结构煤矿巷道的基于多Sink节点的无线传感器网络路由协议。该协议引入多Sink节点的无线传感器网络结构和非均匀成簇的思想，采用基于多Sink节点的功率控制算法和非均匀成簇算法，对各个Sink节点的最优通信半径、发射功率、簇首的选择和非均匀竞争半径的计算进行优化。仿真结果表明，该路由协议在连通度、延时和网络生存期上具有优势，可有效降低无线传感器网络整体能耗,延长网络生存期。
关键词：煤矿巷道； 无线传感器网络； 多Sink节点； 路由协议； 功率控制； 非均匀成簇
网络出版地址：http://www.cnki.net/kcms/detail/32.1627.TP.20160601.1028.012.html
为避免煤矿井下有线通信线缆在事故中受到破坏而造成监控中断，井下无线通信技术研究具有重要意义[1]。将无线传感器网络应用于煤矿安全监控系统成为煤矿安全生产的发展趋势[2]。
通过研究煤矿巷道特征可发现，巷道呈长带状结构，因此，应用于煤矿巷道的无线传感器网络具有不同于一般应用的特点：① 煤矿巷道环境复杂，存在易爆气体，传感器节点电池的更换非常困难，需要优先考虑延长网络生存期；② 无线传感器网络单Sink节点的结构无法保证远离Sink节点的簇首将数据传送给巷道口的Sink节点，同时远离Sink节点的簇首为了能将数据传送给Sink节点，必须工作在大功耗状态，导致簇首需要更大的能耗，影响网络生存期；③ 在分簇的设计上，为了达到能耗均衡，需要对簇首的选择、非均匀竞争半径进行合理计算，保证簇首不会由于负担重而过早死亡，保证距离Sink节点较近且具有较高能量的传感器节点优先成为簇首。
已有的针对煤矿无线传感器网络的研究以单Sink节点的网络结构为主，该种网络结构无法保证巷道深处的传感器节点及时将数据传送给巷道口的Sink节点，如参考文献[3]提出的EEUC非均匀成簇算法。部分基于多Sink节点的路由算法研究则没有针对煤矿特殊的长带状结构，如参考文献[4]提出了一种多Sink节点部署位置优化算法(MSGA)，该算法在网络模型的选择上并没有针对煤矿巷道的特殊结构；参考文献[5]提出了一种基于多Sink节点的长链状无线传感器网络功率控制算法，但是在非均匀成簇的方法上没有采用适合巷道特殊结构的算法，存在一定的局限性。
本文在煤矿巷道的特殊结构基础上，提出在煤矿巷道使用多Sink节点的网络结构，并利用非均匀成簇的思想，提出一种基于多Sink节点的非均匀分簇的能量均衡路由协议(Unequal Clustering and Energy-balanced Routing Protocol Based on Multi-Sink，UCERP)。该协议的基本思想：在煤矿巷道内的中央位置每隔一段随机距离部署Sink节点，Sink节点之间通过对发射功率进行控制来保证对网络的覆盖率，同时各个Sink节点的覆盖范围内部作为一个独立的区域，利用非均匀成簇的思想，对簇首的选择、非均匀竞争半径的计算进行优化，从而实现能耗均衡。仿真实验证明，UCERP符合煤矿巷道的长带状结构特点，能保证网络覆盖率，并有效延长网络生存期。
基于UCERP的煤矿巷道无线传感器网络结构是在巷道的中央位置部署多个Sink节点，各Sink节点可以获得自身位置信息，并通过功率控制消息(Power Control Message，PCM)获得邻居Sink节点的工作功率情况。
为了方便研究，假设网络中传感器节点个数为N，分布在一个狭长的L×W区域内，且L≫W，传感器节点和Sink节点一旦部署完毕，位置将固定；传感器节点和Sink节点的发射功率可控，并且可根据接收信号强度推算出节点之间的距离和接收功率；传感器节点同构，初始能量相同，具有数据融合和自我剩余能量感知功能，Sink节点能量不受限制。
根据煤矿巷道的特点，UCERP协议包括多Sink节点的功率控制算法(Multi-Sink Power Control Algorithm，MSPC)和各Sink节点内部区域的非均匀成簇算法(Unequal Clustering and Energy-Balanced Algorithm，UCEB)2个部分。
MSPC主要是对相邻Sink节点的功率进行调节，保证多Sink节点对网络的整体覆盖率；UCEB主要包括簇首的选择、非均匀竞选半径的计算及最终簇首的产生，对于2个Sink节点重叠覆盖的区域，传感器节点将选择距离较近的Sink节点，加入其所在区域的簇。具体的分簇机制如图1所示，离Sink1节点较近的簇半径小，离Sink1节点较远的簇半径大。
图1 UCERP非均匀分簇机制
2.1 MSPC
2.1.1 功率控制模型
为了保证网络的覆盖率及连通度，需要各个Sink节点之间协商运行时的工作功率。在参考文献[6]和参考文献[7]中描述了如何利用Friis公式计算节点的接收功率，如式(1)所示：
(1)
式中：Pr为节点的接收功率；Pt为节点的发射功率；gt，gr分别为发送天线和接收天线的增益；λ为由载波频率所决定的载波波长；d为发送节点和接收节点之间的距离；n为信道衰落系数，通常取2。
由式(1)可得到节点的发射功率：
(2)
式(2)中，λ，n，gt，gr在无线传感器网络中都是确定值，参考文献[8]研究表明，可根据所接收信号的强度推算接收功率，因此，当d值为Sink节点的最佳通信半径时，可通过式(2)计算最优发射功率，从而将发射功率的控制问题转换为通信半径的控制问题。
2.1.2 网络覆盖率
在长为a、宽为b的矩形区域内部署2个Sink节点S1，S2，如图2所示。Sink节点位于该矩形区域的中央位置，如果2个Sink节点的无线通信半径相交且交点(即E，F)位于该矩形区域之外，同时该矩形区域的4个顶点(即A，B，C，D)都位于2个Sink节点的无线通信半径之内，则可以保证2个Sink节点对该矩形区域的覆盖率为100%。
图2 具有2个Sink节点的无线传感器网络
根据上述分析，网络中存在2个Sink节点时，其无线射程需要满足式(3)：
(3)
式中：(x,y)为位于Sink节点通信范围内的任意传感器节点坐标；(xS1，yS1)，(xS2，yS2)分别为2个Sink节点在矩形区域内的坐标；rS1，rS2分别为2个Sink节点的无线射程。
为了实现覆盖率为100%，且每个Sink节点的发射功率最小，可定义函数：
(4)
s.t.
xE>0,xF<a
yE≥b,yF≤0
式中：(xA，yA)，(xC，yC)，(xE，yE)，(xF，yF)分别为点A，C，E，F的坐标。
以上分析了Sink节点个数为2的情况。当Sink节点超过2个时，分析方法类似。
2.1.3 分布式功率控制算法
在MSPC中，为了保证不同的Sink节点之间正常通信，首先需要定义一种握手数据包，如图3所示。
图3 MSPC握手数据包的帧格式
该握手数据包包括3个数据域：Header，表示握手数据包头；Sink ID，全网唯一，用于标识各个Sink节点，按升序排列；Sink Location，表示初始状态Sink节点的位置。网络初始化时，通过该握手数据包实现各Sink节点之间信息的交互。
将k个Sink节点部署在L×W的网络中，其坐标为(xSj,ySj)，j=1,2，…，k。为方便说明，令P(a,b)为一矩形区域，C(xSj,ySj,rSj)表示以(xSj,ySj)为圆心、以rSj为半径的圆形区域。为了保证Sink节点对网络的整体覆盖，须满足式(5)：
⊂
(5)
根据功率控制模型中的结论，Sink节点发射功率的计算问题实际上是最优通信半径的求解问题。
根据参考文献[5]，为了保证所有Sink节点覆盖整个网络，从第2个Sink节点开始的无线射程rSj(j=2,3,…,k)必须满足式(6)：
a⊂
(6)
由此可得如图4所示的3种无线射程情况。通过计算可使各Sink节点获得最佳的无线射程，从而使每个Sink节点获得最优的发射功率。
各Sink节点的无线射程为
(7)
(c) 射程偏小
图4 网络中有3个Sink节点时无线射程选择
在各Sink节点的发射功率调整完毕后，即可使用UCEB进行分簇。MSPC流程如图5所示。
图5 MSPC流程
2.2 Sink节点覆盖区域内的UCEB
MSPC执行完后，在各Sink节点覆盖的区域内根据UCEB进行分簇和数据传送。UCEB包括候选簇首的选择、非均匀竞争半径的计算、最终簇首选取和簇的形成3个部分。
2.2.1 候选簇首选择
各Sink节点在完成功率的调校后，将获得各自的覆盖区域，并在其覆盖区域内广播Sink ID，接收到相同Sink ID的传感器节点被认为位于同一个区域内，然后在该区域进行分簇处理。
采用参考文献[2]提出的方法选择候选簇首。预设一个阈值T，首先传感器节点随机产生一个值u，u∈[0,1],利用式(8)计算：
(8)
式中：E0，E分别为某一个传感器节点的初始能量和剩余能量。
将各个传感器节点的u0和阈值T进行比较，选择满足关系u0≤T的传感器节点成为候选簇首，其他传感器节点则作为普通节点进入睡眠状态。
对式(8)进行分析可知，具有较大剩余能量的传感器节点更容易成为候选簇首节点。
2.2.2 非均匀竞争半径的计算
为了减少各Sink节点覆盖区域内的簇间干扰，控制簇的规模，从候选簇首中确定最终簇首，需要获得一个合适的非均匀竞争半径。参考文献[3]提出一种非均匀竞争半径计算公式，但未考虑传感器节点的剩余能量。本文提出的非均匀竞争半径计算公式为
(9)
式中：ω1，ω2为调整系数,ω1,ω2∈[0,1]；
分别为某候选簇首的剩余能量和初始能量；dtoSK为该候选簇首到其所属Sink节点的距离；dmax为该Sink节点所覆盖区域内所有候选簇首到该Sink节点的最大距离；rmax为最大的簇半径。
对式(9)进行分析可发现，竞争半径的大小和候选簇首与Sink节点距离、剩余能量均存在正向关系，即距离和剩余能量越小，竞争半径也越小，从而实现能耗均衡。
2.2.3 最终簇首选取和簇的形成
UCEB中每个传感器节点需要保存一张邻居节点表，表中存储其邻居传感器节点的相关信息，所有收到相同Sink ID的传感器节点位于同一区域内，同时接收到2个Sink ID的传感器节点则计算自身到Sink节点的距离，选择较为靠近的Sink节点所覆盖区域并加入簇。表1为某候选簇首的邻居节点表，其由候选簇首ID、状态、剩余能量和到Sink节点的距离构成。
表1 某候选簇首的邻居节点表
以下为UCEB算法流程。
(1) 收到相同Sink ID的传感器节点组成一个区域，重叠区域的传感器节点将获得2个Sink ID，此时分别计算传感器节点到2个Sink节点的距离，将传感器节点加入距离较近的簇中。
(2) 每个传感器节点计算u0，并与阈值T进行比较，小于阈值T则成为候选簇首，否则成为普通传感器节点，并计算非均匀竞争半径rra。
(3) 每个候选簇首以rra为半径广播竞选信息。
(4) 每个候选簇首启动定时器。
(5) 若某候选簇首在其定时器时间结束前没有收到邻居候选簇首的消息，表明该候选簇首竞选成功，转向步骤(7)，否则转向步骤(6)。
(6) 该候选簇首竞选失败并退出竞选，成为普通传感器节点。
(7) 该候选簇首竞选成功，成为簇首，发送竞选成功消息给其所有邻居候选簇首。
(8) 簇首以rra为半径广播竞选成功消息给普通传感器节点。
(9) 普通传感器节点发送加入消息通知簇首，成为簇成员，并向簇首传送数据。
为方便说明，将候选簇首Vq的邻居节点表记为Neitab(Vq)。该邻居节点表可表示为
Neitab(Vq)={Vl| Vl 为候选簇首，且
range(Vq,Vl)<max(rraq,rral)}
range(Vq,Vl)表示候选簇首Vq与Vl之间的距离；rraq,rral分别为候选簇首Vq，Vl的非均匀竞争半径。定时器时间t可利用式(10)计算。
(10)
式中：h为一随机产生的实数，其取值范围为[0,1]；t0为事先约定的候选簇首竞选持续时间；Ea，Da分别为竞争半径内所有传感器节点的平均剩余能量和平均距离，可参考文献[9]进行计算。
(11)
(12)
式中
q为候选簇首Vq的剩余能量;dtoSKq为候选簇首Vq到其所属Sink节点的距离；m为邻居传感器节点数量。
3.1 UCERP分析
对UCERP中涉及到的参数T，ω1，ω2，rmax取值进行分析和说明。
T的取值直接影响候选簇首数量，ω1和ω2的取值则体现了传感器节点剩余能量和传感器节点到Sink节点的距离对簇竞争半径的影响程度，这3个值的选取必须适当，否则会对网络生存期造成较大影响。实验证明，T，ω1，ω2取值分别为0.4，0.6，0.2可获得最佳效果。
rmax的取值直接影响到非均匀竞争半径rra的大小。由于分簇发生在各Sink节点通信半径调节完成后，因此rmax不可能大于rSj。而在一些大型煤矿井下的试验证明，rmax=75 m[10]。因此在计算过程中，当rSj>75 m时，rmax=75 m；当rSj<75 m时，rmax=rSj。
3.2 算法仿真
为了验证UCERP适用于煤矿巷道的长带状结构，在连通度、延时和网络生存期上，将UCERP和MSGA进行对比分析。采用Java语言，利用OMNET++4.2作为仿真工具搭建仿真平台，试验参数见表2。
表2 试验参数
连通度是指被Sink节点覆盖的传感器节点占全部传感器节点的比例。当Sink节点数量达到一定值时，连通度为100%，意味着所有的传感器节点都被网络覆盖到。所有试验结果都是对1 000次仿真结果求平均值。图6为Sink节点数量变化时，采用UCERP与MSGA的平均连通度对比。可见随着网络中Sink节点的增加，采用UCERP时网络平均连通度更有优势，如Sink节点数量为12时，MSGA的连通度为74%，UCERP为98%。
图6 采用UCERP与MSGA的平均连通度对比
延时是指数据包从簇首节点到Sink节点的传输时间。主要对不同数量Sink节点的延时情况进行对比。图7为Sink节点数量变化时数据包延时对比，可看出Sink节点数量为4时，数据包延时最小。可见多Sink节点网络环境下，数据延时将大大减小。
图7 Sink节点数量变化时数据包延时对比
图8为Sink节点数量变化时，采用UCERP与MSGA的网络生存期对比，分别进行50次仿真，对其生存期取平均值。可看出采用UCERP时较采用MSGA的网络生存期提高14%左右，即UCERP具有更好的能耗均衡性能。
图8 采用UCERP与MSGA的网络生存期对比
在分析煤矿巷道长带状结构的基础上，提出了一种适用于煤矿巷道的基于多Sink节点的无线传感器网络路由协议，并在仿真工具OMNET++环境下实现了建模和仿真。仿真结果证明该路由协议在连通度、延时和网络生存期上符合煤矿巷道多Sink节点的网络环境，能有效降低能耗、延长网络生存期。
参考文献：
[1] 孙继平.煤矿监控新技术与新装备[J].工矿自动化，2015,41(1):1-5.
[2] 夏旭，黎望怀，李登，等．煤矿采空区无线传感器网络路由协议研究[J]．工矿自动化，2014，40(4)：32-37．
[3] 李成法，陈贵海，叶懋，等．一种基于非均匀分簇的无线传感器网络路由协议[J].计算机学报，2007，30(1)：27-36.
[4] DAI S, TANG C, QIAO S, et al. Optimal multiple sink nodes deployment in wireless sensor networks based on gene expression programming[C]//International Conference on Communication Software and Networks, Singapore,2010:355-359.
[5] 夏旭，陈志刚，曾锋，等．基于多Sink的长链状无线传感器网络功率控制算法[J]．传感技术学报，2015,28(6)：920-926.
[6] CHEN W, JIANG X, LI X, et al. Wireless sensor network nodes correlation method in coal mine tunnel based on Bayesian decision[J]. Measurement, 2013, 46(8): 2335-2340.
[7] ZHOU G, HUANG L, ZHU Z, et al. A zoning strategy for uniform deployed chain-type wireless sensor network in underground coal mine tunnel[C]//IEEE Internation Conference on High Performance Computing and Communications and IEEE International Conference on Embedded and Ubiquitous Computing, Zhangjiajie,2013: 1135-1138.
[8] WOO A, TONG T, CULLER D. Taming the underlying challenges of reliable multihop routing in sensor networks[C]//Proceedings of International Conference on Embedded Networked Sensor Systems, New York, 2003:14-27.
[9] 刘明，曹建农，陈贵海，等．EADEEG：能量感知的无线传感器网络数据收集协议[J]．软件学报，2007，18(5)：1092-1109.
[10] 刘晓文，闫静杰，苗锦，等．矿井无线传感器网络LEACH协议的改进[J].煤炭科学技术，2009，37(4)：46-49.
LI Wanghuai1, XIA Xu1,2
(1.Department of Electrical and Information Engineering, Hunan Vocational College of Security Technology, Changsha 410151, China; 2.School of Software, Central South University,Changsha 410075, China)
Abstract：When traditional wireless sensor network based on single sink node is applied in coal mine monitoring system, the sensors far away from tunnel crossing cannot transmit monitoring data to sink nodes in the tunnel crossing real timely and exactly. In order to solve above problem, a routing protocol for wireless sensor network based on multi sink nodes was proposed which was suitable for long strip structure of coal mine tunnel. The protocol introduces wireless sensor network structure based on multi sink nodes and unequal clustering thought, and adopts a power control algorithm based on multi sink nodes and an unequal clustering algorithm to optimize the optimal communication radius, transmit power, cluster head selection and calculation method of unequal radius of each sink node. The simulation results show that the protocol has advantages in connectivity, delay and network lifetime, and can reduce the whole network energy consumption effectively and prolong network survival time.
Key words：coal mine tunnel; wireless sensor network; multi sink nodes; routing protocol; power control; unequal clustering
文章编号：1671-251X(2016)06-0046-06
DOI：10.13272/j.issn.1671-251x.2016.06.012
收稿日期：2016-02-02；
修回日期：2016-04-15；责任编辑：李明。
基金项目：国家自然科学基金资助项目(61272149)；国家安全生产监督管理总局安全生产重大事故防治关键技术科技项目(hunan-0012-2015AQ)；中南大学博士生自主探索创新项目(2014zzts043)。
作者简介：黎望怀(1973-)，男，湖南汨罗人，副教授，主要研究方向为应用电子技术、无线传感器网络、煤矿安全技术，E-mail:672703649@qq.com。通信作者:夏旭(1980-),女,湖南益阳人,副教授,博士研究生,研究方向为无线传感器网络、煤矿安全监控技术，E-mail:wuwuxuxu@163.com。
中图分类号：TD67
文献标志码：A 网络出版时间：2016-06-01 10:28
黎望怀, 夏旭.基于多Sink节点的煤矿巷道无线传感器网络路由协议[J].工矿自动化，2016,42(6)：46-51.