基于网络分区和路径能耗的深井无线传感器网络多簇 首路由算法*

余修武，梁北孔，周利兴，谢晓永，范思柔，王宇琴，刘 琴

(1.南华大学 环境与安全工程学院，湖南 衡阳 421001；2.金属矿山安全与健康国家重点实验室，安徽 马鞍山 243000)

0 引言

矿物资源消耗的增长使得浅部矿物逐步殆尽，导致地下采矿向更深水平推进[1]。深部矿井因高温高湿、高地应力、供电线路长及人员设备密集等因素造成复合型灾害事故频发[2]，对深井开采的安全工作造成巨大威胁。由于现有的有线矿井安全监测系统不能满足深井的安全需求[3]，有必要把无线传感网络引入深井生产中。传感器网络的应用相关性强，随着应用环境的不同，路由算法差距或许会很大，尚不存在通用的路由算法[4]，且目前适用深部矿井应用环境的路由算法较少。因此，开展深部矿井无线传感器网络路由算法的研究意义重大。

无线传感器网络是1个由大量节点构成的，具有数据采集、融合与传输的自组织网络[5]。为解决无线传感器网络能耗低效及“热区”问题，许多路由算法被提出。其中，LEACH算法[6]簇首节点的选择是随机的，且以单跳方式传输数据，会产生簇首节点不均匀地分布和当前能量较少的节点也成为簇首等问题；钱开国等针对路由算法中簇首节点分布不均问题提出HNDCRA[7]算法，均衡了簇首分布，但其算法的簇首竞选机制未加入节点当前能量，导致部分簇首节点能量被过快地消耗；张文梅等提出改进的无线传感器网络非均匀分簇路由算法[8]，把节点当前能量引入簇首竞选机制中，使簇首能量均衡地消耗，该算法一定程度上能减少并均衡节点能量消耗，但没有对“热区”问题提出解决方案；彭铎等针对无线传感网“热区”问题提出EUCP[9]算法，能在一定程度上改善“热区”问题。然而，上述路由算法多适用于典型大面积监控领域，在深部矿井特殊的应用环境中，狭长的带状巷道使其具有局限性。为此，王伟等针对带状网“热区”的出现提出CRLDB[10]算法，引入非均匀分簇概念，使用候选簇首竞争策略；刘佳针对矿井下巷道应用环境提出CHPBN[11]算法，仅分簇1次，数据多跳转发；林启中等提出HEED-EELD(Dual-cluster-head routing algorithm based on location information)[12]算法，以单跳距离构建层次，采用双簇首并将节点位置及其当前能量引入路由选择机制。然而，以上算法大多运用非均匀分簇思想，竞选簇首并以多跳方式传输簇间数据，但均未考虑数据传输过程中路径通信代价及跳数问题。因此，本文提出1种基于网络分区和路径能耗的带状无线传感器网络多簇首簇路由算法(NPPEC)，算法采用跳数泛洪方式建立带状网络分区结构，将节点分布密度加入簇首竞选机制中，通过主簇首和副簇首的分工配合，使簇首能量更均衡地消耗；依据路径能耗、节点当前能量及位置计算路径选择概率，并通过控制跳数改善数据传输的实时性。

1 系统模型

1.1 无线通信模型

采用无线通信模型First order radio model[13]获取某节点发送和接收数据包的能量消耗值。假设从节点A发送lbit的数据到节点B，A和B之间的距离为d，则其能量消耗值求解如下：

(1)

节点B接收lbit数据所消耗的能量求解如下：

ERx(l,d)=l×Eelec

(2)

式(1)中的限值d0为：

(3)

式中：Eelec表示节点发送或接收1 bit数据的能量消耗值；εfs表示在自由空间模型下1 bit数据的能耗；εamp表示在多路径模型下发送1 bit数据的能耗；d0表示通信距离限值;d小于d0时，r=2；当d大于或等于d0时，r=4。传感器节点有传感器模块、处理器模块及无线通信模块，其中无线通信模块消耗了绝大部分能量，如图1所示。

图1 网络节点能耗情况Fig.1 Energy consumption of network nodes

1.2 深井巷道带状网络分区模型

节点布置在深井巷道里面，区域长度L一般远大于宽度W，构成带状无线传感网。假设有nall个节点组成此网络，第i个节点为Si，则节点集S={S1,S2,,Snall}。此带状网络存在如下特点：①网络中所有节点均已完成定位算法，位置坐标已知，忽略定位误差对路由算法的影响；②除了汇聚节点的能量不受限制之外，其余节点能量有限并存在相同属性及功能；③因节点的无线通信模块消耗了大部分能量，忽略其余模块的能耗；④普通节点数据传播延迟远小于数据采集周期，不会造成网络拥堵；⑤因深井环境复杂多变，节点能根据实际情况调节信号发射强度；⑥信息接收节点能基于接收信号强度计算与发射节点之间的距离。

采用跳数泛洪方式建立网络分区结构，其主要步骤如下：

1)汇聚节点广播1个初始消息PA给其邻居节点，初值为0。

2)收到该PA信号的节点就将自己的分区值设置为PA+ 1，接着该节点将自身分区值PA(PA=PA+1)再广播给其邻居节点。

3) 收到新PA消息的节点再把自己的分区值设置为PA+1，因为可能会收到来自前1分区多个节点的PA值，这里规定PA值只设置1次。

消息依照这样的规律在监测区域扩散，区域内节点随机分布，且都能获得对应的分区值，即全网建成了分区结构，如图2所示。

图2 深井巷道网络分区结构Fig.2 Deep mine tunnel network partition structure

2 NPPEC算法

节点根据网络分区结构获得与自身位置对应的分区值，该值可应用于簇首竞选及数据转发过程。数据按分区值减少的方向逐跳转发，路由按分区值增加的方向依次建立，构成带状网络分区结构。该算法分为3阶段：簇首竞选、簇的形成、能量多路径路由。

2.1 簇首竞选

簇首竞选分为主簇首竞选和副簇首竞选。其中，主簇首负责簇内数据的收集与融合；副簇首负责簇间数据转发，包括转发来自其主簇首的数据。

2.1.1 主簇首竞选

以文献[4]的阈值公式为基础，将节点当前能量、节点分布密度以及节点到汇聚节点的距离引入该阈值公式中，如式(4)所示。

(4)

(5)

式中：n表示第r轮中没有担任主簇首的某1节点；T(n)表示节点n的阈值；P指主簇首在全网节点中所占比例，P=n/nall；r是选举轮数；rmod(1/P)指第r轮中担任过主簇首节点的个数；G是第r轮中没有担任过主簇首的节点集合；α,β,γ是参数，且α+β+γ=1；Ecur是在第r轮中某节点的当前能量值，该值在式(4)中影响较大；Et表示第r轮网络能量总和；di指节点到汇聚节点的距离；dave指第r轮中所有存活节点到汇聚节点的平均距离；dmax指第r轮中范围的最大距离值；Qn指节点分布密度，第r轮初始阶段，以R为半径的范围中，节点进行信息交互并采集存活节点信息，由此可得Nei(n)a；Na表示网络存活节点数量，由汇聚节点获取并向全网广播。节点随机产生1个0～1范围内的数，当该数值小于T(n)时，节点成为候选主簇首；候选主簇首向同1分区内的所有节点广播其当前能量信息，并将自身的当前能量与同1分区其余候选主簇首的当前能量相比较，假如该候选主簇首的当前能量比同分区的其余任1候选主簇首的当前能量都要大，则该候选主簇首当选该分区的主簇首，反之则竞选失败。最后，当选分区主簇首的节点向整个分区内的所有节点广播其竞选成功的消息。

该阈值公式的理论依据论述如下：首先，节点当前能量是主簇首竞选机制中的重要因素，如果竞选主簇首时不考虑节点当前能量，则可能发生当前能量过少的节点担任主簇首的情况，会导致部分节点因能耗过快而失效，节点当前能量越高，成为主簇首的概率就应越高；相反，节点当前能量越低，被选举为主簇首节点的概率也就越低。其次，在深部矿井中，各工作区域的环境及功能存在差异，节点分布密度是不同的，节点分布密度大的区域，增加其节点担任主簇首的概率；反之，节点分布密度小的区域，减少其节点成为主簇首的概率。最后，从能耗角度来说，节点到汇聚节点的距离对主簇首竞选有直接关联，如果距汇聚节点较远的节点成为主簇首，网络的能耗就会比距汇聚节点较近的节点更大，假如网络中经常出现这种情况，则会使网络生命周期更早地结束。

2.1.2 副簇首选取

文献[14]论证了簇首节点数量占比k为5%左右时，网络的能量消耗最为理想。在主簇首竞争范围内，基于能量情况选取副簇首。首先，计算某簇所需副簇首的数量，计算方法如下：

nv=(nall×k-n)×f

(6)

f=aPA{0

(7)

其中，a满足式(8)：

a1+a2++an=1

(8)

式中：nv表示某簇副簇首的数量；nall表示全网节点总数量；k指簇首在全网节点中所占比例；n表示分簇数量，即主簇首数量，等于最大分区值；f是以PA为因变量的函数，表示越靠近汇聚节点的簇，其副簇首数量越多，数据转发能力越强，能在一定程度上解决“热区”问题。

同时，改进文献[15]的簇内节点阈值公式后，进行副簇首的竞选。

(9)

2.2 簇的形成

NPPEC算法主簇首的竞争半径为R，由系统设置。则NPPEC算法成簇结构如图3所示。

图3 NPPEC算法成簇结构Fig.3 NPPEC algorithm cluster structure

2.3 能量多路径路由

簇内所有节点都在其主簇首的竞争范围内，采用单跳方式进行簇内数据传输可减少网络能耗。多路径数据转发，指各副簇首之间的转发过程，按分区值减小的方向传输，采用能量多路径路由机制，使网络能量更均衡地消耗。多路径转发过程描述如下：

1)NPPEC算法成簇结构建立完成后，各簇的副簇首节点按分区值增加的方向逐层建立路由，其中建立消息包括1个代价域和1个跳数域，分别指消息发出节点到汇聚节点的能量信息和跳数信息，2者初始值都设为0。

2)副簇首Ni发送路径建立消息给邻居副簇首Nj，当在Nj位于源节点和Ni之间时，副簇首Nj才转发此消息，否则不转发。

3)数据从副簇首Nj发出，经副簇首Ni转发到汇聚节点，路径能耗值指副簇首Ni的代价值与Nj到Ni间的通信能耗之和，如式(10)所示：

CNj,Ni=Ct(Ni)+Met(Nj,Ni)

(10)

式中：CNj,Ni指数据从副簇首Nj发出，经副簇首Ni转发到达汇聚节点的代价；Met(Nj,Ni)表示Nj到Ni的通信能耗，计算方法如式(11)所示：

(11)

式中：eNj,Ni指Nj和Ni间直接进行数据转发的能耗；ENi指Ni的当前能量；x，y是常量。

4)根据式(12)，符合条件的邻居副簇首被选进副簇首Nj的路由表FTj内。

(12)

式中：hNj,Ni指数据从副簇首Nj发出，经副簇首Ni转发到汇聚节点所需要的平均跳数；λ，μ基于实际情况设定，均大于1。

5)根据式(13)和(14)计算FTj内的副簇首被选为下1跳的概率。

(13)

(14)

式中：PNj,Ni指FTj内的副簇首被选作下1跳的概率；YNj,Ni是以副簇首Nj当前能量及到汇聚节点距离为因变量的函数；Er是第r轮中能量总和；ENj为副簇首Nj的当前能量；dNi,s，dNj,s分别为副簇首Ni到汇聚节点的距离以及相邻副簇首Nj到汇聚节点的距离；dNj,Ni为副簇首Nj与相邻副簇首Ni的间距；ω1，ω2为参数控制因子。

6)路由表FTj中的某1节点，被副簇首Nj依据概率选出，并接收来自Nj的数据。

能量多路径路由进行数据传输的流程如图4所示。

图4 能量多路径路由过程Fig.4 Energy multi-path routing process

3 仿真及结果分析

3.1 参数设置

模拟深部矿井巷道应用环境，运用MATLAB软件对NPPEC算法、经典的LEACH算法和近年来新提出的HEED-EELD算法进行仿真比较。仿真参数如表1所示。

表1 网络仿真参数Table 1 Network simulation parameters

3.2 仿真结果分析

随机地选取10轮实验数据，比较3种算法的簇首在单轮周期中的能耗情况，如图5所示。依据图5，NPPEC算法和HEED-EELD算法单轮簇首的能耗比LEACH算法低，前2者采用多跳通信方式，而LEACH则使用单跳方式传输数据，这表明多跳通信比单跳通信更能降低网络能耗。此外，可观察到NPPEC算法比HEED-EELD算法单轮簇首的能耗更低，且波动幅度更小，这是因为NPPEC算法在主簇首竞选中考虑了节点分布密度，并把簇首数量控制在全网节点的5%左右，能有效降低和均衡网络簇首的能耗。

图5 单轮簇首消耗总能量Fig.5 Total energy consumption of Single-cycle cluster head

图6比较了3种算法的网络能耗的总和随网络运行轮数的增长而上升的情况。由表1可知，该带状网络的总能量为200 J。观察图6发现，LEACH的总能耗相比较其他2个算法更早稳定在某数值，说明网络因部分节点死亡而丧失了数据传输能力，此时轮数约为498轮；其次是HEED-EELD，约为751轮；最后才是NPPEC，约为900轮。在498轮时，LEACH算法构建的网络能耗为63 J，HEED-EELD算法为55 J，NPPEC算法为50 J。此时，NPPEC比LEACH、HEED-EELD的能量消耗分别减少了20.63%和9.09%。相比其他2种算法，NPPEC算法能更高效地运用有限能量。这是因为该算法副簇首的竞选充分考虑了节点能量因素和距离因素，同时在数据收集传输阶段，主、副簇首高效配合，并依据路径通信代价优化传输路径。仿真数据说明，NPPEC算法能较好地提高网络的能量效率。

图6 网络节点总能耗Fig.6 Total energy consumption of network nodes

网络不稳定期指从网络第1个节点死亡到整个网络失效的时间段，其值越小网络能耗的均衡性越好。图7对比了3种算法的存活节点数量随网络运行轮数增长而减少的情况，观察图7可知，LEACH算法网络的第1个节点能量殆尽的轮数约为48轮，HEED-EELD算法约为350轮，NPPEC算法约为531轮；另外，LEACH算法在整个网络失效时的轮数约为498轮，HEED-EELD算法约为751轮，NPPEC算法约为900轮。经计算，LEACH算法的不稳定周期约为450轮，HEED-EELD算法约为401轮，NPPEC算法约为369轮；所以NPPEC算法的网络能耗均衡性更好。此外，NPPEC算法网络失效时间较LEACH算法和HEED-EELD算法分别延迟了80.72% 和19.84%，NPPEC算法使全网能量更均衡地被消耗。

图7 网络节点存活数量Fig.7 The number of alive network nodes

4 结论

1)针对深井无线传感网因节点能量受限导致网络生存时间短与多跳传输引起的“热区”问题，提出1种基于分区和能量多路径的带状无线传感器网络多簇首路由算法(NPPEC)。

2)NPPEC算法面向深井带状环境，采用多簇首算法改善“热区”问题；将能量多路径路由思想应用到非均匀分簇算法中，控制路径通信代价和路径跳数，降低网络能耗。

3)经仿真比较，NPPEC算法网络生存时间约为LEACH算法的1.807 2倍、HEED-EELD算法的1.198 4倍，网络能量更均衡地被消耗，“热区”问题得到改善，网络寿命也得以延长。