树型链式非均匀分簇混合多跳路由算法*

胡中栋， 张 康， 王振东

(江西理工大学 信息工程学院，江西 赣州 341000)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)是一种集传感器技术、信息处理技术、通信技术等于一体的新型网络，现已广泛应用于环境监测[1]、智能家居、国防军事[2]等多个领域[3]。由于节点初始能量有限[4]，且后期无法补充，因此，充分利用节点有限能量、延长网络整体寿命成为WSNs的重点研究方向。

层次路由协议中的分簇思想能有效聚合数据，提高网络连通率[5]，实现负载均衡。文献[6,7]中簇头随机选取未考虑位置分布，簇内节点与簇头、簇头与簇头间均以单跳方式通信，易产生远距离传输；文献[8]中算法获取所有节点相关信息会消耗大量能量、占用大量的带宽；文献[9]中静态划分成链区域，有可能使用原本相邻的节点因划分区域不同而成链不同，造成能耗浪费；文献[10]中算法如果距离Sink较远的簇密度较大，就会导致其簇头负载不均，其在大面积网络中的表现也较一般。

本文通过引入候选簇头之间的角度控制优化簇头选取，构建树型链式非均匀簇结构优化成簇策略，利用混合层次网络拓扑结构，结合改进后的蚁群算法提出一种树型链式非均匀分簇混合多跳路由算法(a tree-chain uneven cluster hybrid multi-hop routing algorithm,TUCHM)。

1 相关研究

1.1 能耗模型

本文文献[8]中的无线通信能耗模型[11]，假设每个数据包有kbit的数据，则发送端消耗的能量为

(1)

(2)

接收端消耗的能量为

ERX=KEelec

(3)

数据汇聚融合消耗的能量为

EDA=kEda

(4)

式中Eelec=50 nJ/bit，为收发电路能耗；Eda=5 nJ/bit，为单位数据融合能耗；Efs=10 pJ/bit/m2，Eamp=0.001 3 pJ/bit/m4，d0为能量损耗的界限值。

1.2 蚁群算法

基本蚁群算法[13]路径选择概率模型未能考虑节点的剩余能量和位置等因素，会导致位于路径上的节点因频繁传递数据而过快死亡信息素更新缓慢，且不断挥发，所以,基本蚁群算法路径搜索时间长，易出现“停滞”现象。Dorigo M提出的Ant-Cycle模型利用全局信息更新路径上信息素，运算量大，时间复杂度高，寻找最优路径的收敛速度较慢。Stutzle T等人提出了最大最小[14]蚁群系统，其每一次循环只对本次循环最优解或到目前为止找出最优解的路径进行信息素更新，导致较长时间内多条路径上信息素浓度相同。

2 TUCHM算法

2.1 簇头选取

为了均衡网络能耗，TUCHM算法在簇头选择时综合考虑了当前节点的剩余能量和簇头之间的位置关系，提出了新的阈值函数计算公式

(5)

(6)

式中p为存活节点中簇头占比；r为当前循环轮数；G为最近1/p轮中未被选为簇头的节点集合[15]；Ei为当前节点i的剩余能量；Eavg为所有节点的平均剩余能量；χ1，χ2为式(6)两项的权重值且χ1+χ2=1。

如图1，以Sink节点为原点建立二维直角坐标系，各簇头与Sink节点连线，当其中的BS和CS为候选簇头a与Sink节点连线aS的左右邻线时，射线l为的角平分线，θ为aS和l的夹角；当网络中还没有选取出簇头时，θ=0°；当a′S只有一侧存在簇头与Sink的连线，另一侧为坐标轴时，射线l′为坐标轴X或Y与AS形成的较小夹角的角平分线，θ′为a′S和l′的夹角。

图1 θ角示意

2.2 构建簇结构

设全网共N个节点，构建簇结构的步骤如下：

Di=φi

(7)

式中φ为长距离系数。根据文献[15]可知，φ初始值一般取1.5，但当遇到以下两种情况时，长距离系数的取值应该适当增大：WSNs稀疏、节点密度低时，长距离较多，此时应增大长距离系数以适应TUCHM算法;在WSNs运行的中后期，由于出现了大量节点死亡，导致网络节点间距增大，此时应适当增大长距离系数以加快TUCHM算法收敛速度。

2)以簇头CHi为簇中心，半径在Di内的邻居节点以单跳形式加入簇，若同一邻居节点在多个簇头的成簇范围内，则选择距离最近的簇头加入。

δ用来控制建簇阶段的收敛速度，如图2，节点d,e和f各自寻找到距离自身最近的已成簇节点b和c，但节点e和f并不位于以b或c为中心、D4为半径的范围内，则节点d首先加入簇4；然后节点e，f再次寻找到距离自身最近的已成簇节点d，但只有节点f位于以d为中心、D4为半径的范围内，所以节点f加入簇4；经过多次循环，节点e连续δ次寻找到距离自身最近的已成簇节点d，却仍然没有加入簇4，此时令节点e直接以单跳方式与节点d建立连接加入簇4。δ定义为

(8)

式中Nalive为当前存活节点数，成簇完成后，确定一个T时隙，以降低数据冗余和传输冲突，簇内节点根据T时隙将数据传输到簇头节点。如图2所示，簇内产生树型链式结构，距离簇头较远的节点通过链中其它节点中转，降低了数据传递路径长度。

图2 混合层次网络多跳路由

2.3 路径选择概率模型

如图2，TUCHM算法采用平面网络结构与层次网络结构相结合的混合层次网络拓扑结构，普通节点间可以直接进行通信，不需要通过簇头节点转发数据，因此，稳定性更好，鲁棒性更高[16]；结合改进后的蚁群算法，将簇头的数据通过其它簇头或普通节点多跳传递至Sink节点。算法首先修改路径选择概率模型，当蚂蚁k位于节点i时，计算到下一跳节点j的概率

(9)

式中τ为信息素浓度；η，ψ为启发式因子

(10)

(11)

式中α和β分别为信息素和期望启发式因子的相对重要程度；Jk(t)为蚂蚁还未经过的节点集合。

可以看出，启发式因子η主要考虑当前节点i的剩余能量Ei、向下一跳节点j发送数据需要的能量Ecost(i,j)、节点间距离dij与传感器节点通信半径R的比值等参数；启发式因子ψ主要考虑下一跳节点j的剩余能量Ej与节点初始能量Einit的比值、dij与节点j到Sink的距离diS之和以γ角等参数。γ表示当前节点到Sink的连线与当前节点到下一节点的连线的夹角，夹角越小，下一节点越有可能在当前节点到Sink的传输路径上，启发式因子ψ通过γ角引导蚂蚁方向以降低经过的节点数量。通过设置合理的权重值ξ1,ξ2,ξ3和ξ4可有效降低传输路径长度和节点能耗。

2.4 信息素更新

TUCHM算法在路径信息素更新前，蚂蚁先按照信息传递路径长度进行排名，排名靠前的蚂蚁在每次循环中额外释放更多的信息素，给予已知最优路径最强的正反馈，加快路径寻找速度，根据式(12)、式(13)更新路径ij的信息素浓度值

τij(t+n)=(1-ρ)·τij(t)+Δτij

(12)

(13)

(14)

3 算法仿真与分析

3.1 仿真参数设置

为了验证TUCHM算法的性能，应用MATLAB软件与LEACH和DEEC算法进行仿真实验。假设100个同构无线传感器节点在仿真区域内随机分布且不能移动，当节点剩余能量低于1 %后,则认为该节点死亡，每个节点的初始能量为0.5 J，广播包大小为25 bit，数据包大小为4 000 bit，Sink节点坐标位于(0,0)m处。

3.2 仿真结果分析

图3(a)～(d)给出了在不同大小的正方形仿真区域下存活节点数的对比，其边长分别为100,200,300,400 m。随着仿真区域的不断变大，LEACH算法越来越早出现断崖式的节点死亡，这是因为其簇内节点到簇头、簇头到Sink节点皆以单跳形式传递数据，DEEC算法由于在簇头层采用路由树多跳传输数据而比LEACH算法节约能量，但随着仿真面积的加大，簇头间的距离越来越远。由图3(c)、(d)可知在大面积仿真环境下，网络后期LEACH算法存在许多节点未完全死亡，只有个别节点在收集数据，但此时网络已经失效。

图3 不同仿真区域下存活节点曲线对比

可以看出TUCHM算法可以在更长的时间内保证所有的节点都存活，这是由于非簇头层的节点参与中转数据。

从WSNs开始运行到第一个节点死亡时所经历的轮数称为网络的稳定周期。如图4(a)所示，TUCHM算法的稳定周期在边长100,200,300,400 m的正方形仿真区域下比LEACH算法分别提升大约32 %,63 %,193 %,286 %，比DEEC算法分别提升大约14 %,17 %,27 %,39 %。设网络开始运行到50 %的节点死亡所经历的轮数称为网络的生命周期。如图4(b)所示，TUCHM算法的生命周期在边长100～400 m的正方形仿真区域下比LEACH算法分别提升大约66 %，67 %，86 %，197 %，比DEEC算法分别提升大约14 %，15 %，46 %，123 %。这是因为TUCHM算法簇内远距离节点借助链内节点中转传递数据，簇头到Sink节点借助普通节点多跳传递数据，有效避免了部分节点因远距离单跳传递能耗过高而失效过快。

图4 不同仿真区域下网络的稳定周期和生命周期

图5为网络在200 m×200 m的仿真区域下消耗总能量以及网络节点剩余能量方差随轮数变化的对比图。

图5 网络消耗总能量与节点剩余能量方差曲线

由图5(a)可知，LEACH和DEEC算法的曲线斜率均比TUCHM算法高，说明LEACH和DEEC算法每轮传输数据消耗能量要比TUCHM高，TUCHM算法借助改进的蚁群算法多跳传递数据，优化各簇头到Sink节点之间的路径因此更加节约能量。由图5(b)看出：LEACH算法剩余能量方差变化幅度较大，DEEC算法剩余能量方差比较稳定但整体比TUCHM高，TUCHM算法剩余能量方差一直较低且稳定，表明TUCHM算法能够更好地均衡网络能量，这是因为簇头选取同时考虑了节点剩余能量和节点之间的位置关系，避免了蚂蚁路径重叠过多。

4 结束语

TUCHM算法在以下三点进行改进：1)在选取簇头时，综合考虑了候选节点的剩余能量及其位置对传输阶段网络能耗均衡的影响，使剩余能量大和蚂蚁路径重合率低的节点更容易当选为簇头；2)优化了成簇策略，由原来的簇内单跳、均匀分簇变为树型链式多跳、非均匀分簇，合理定义了成簇区域半径，减少了远距离单跳传递的能量浪费；3)采用混合层次网络拓扑结构，打通网络下层节点之间的联系，改进路径选择概率模型和信息素更新模型，更好发挥蚁群算法优化路径的优势，消除了簇头直接与Sink节点单跳传递的缺点。仿真结果表明：TUCHM算法在节点存活数量、网络的稳定周期和生命周期、均衡网络能量消耗等方面有明显的提升。