一种能量均衡化分层式分簇单跳和多跳混合的WSN路由算法研究

史振兴，范秀娟，姜 莹，赵 婧

(1. 北京服装学院，北京 100029；2. 北京交通大学，北京 100044)

0 引言

现在大部分无线传感器网路路由算法都是从能量消耗的角度来进行研究的。在多数多跳路由算法中，大量节点所采集的数据通过多跳的方式流向少数基站，会造成距离基站较近的节点较早的“死亡”，并且由于节点分布不均匀，也会导致一些节点由于转发数据次数过多而过早的“死亡”。同样，在一些单跳分簇算法中，由于簇头融合数据之后直接与基站进行通信，在小范围内能保证大部分簇头和节点间的通信满足自由空间模型。当范围变大时，由于簇头节点间单次通信的能耗差别变得很大，造成距离基站较远的节点过早的“死亡”同样影响网络的性能[1,2]。

在无线传感器网络中，数据通信是系统最重要的操作之一，并占用很大一部分的能量消耗。事实上，在传感器网络中数据通信需要的能量远大于数据处理所需要的能量[3]。通过对各种无线传感器网络路由算法的研究，本文提出一种能量均衡化分层式分簇单跳+多跳路由算法（LEACH_C），引入了平均能量因素。该路由算法分为两级结构，底层为传感器数据采集网络，上层为数据融合转发网络。网络簇头分级结构如图1所示。

图1 分级式网络簇头结构

1 无线通信能量消耗模型

本文采用如图2所示的一种无线通信能量消耗模型。节点发送K比特的数据到距离为d的位置，消耗的能量由发射电路的损耗和发射部分的功率放大器的损耗，即：

其中Eelect表示发射电路的功耗，当节点于节点之间传输数据时，若传输距离小于阀值d0时，采用自由空间传输模型；若传输距离大于d0时，采用多路径衰减传输模型。εfs、εmp分别为两种数据传输模型中发射数据时功率放大器的功耗。

图2 无线通信能量消耗模型

由式（1）可以看出，在传感器节点之间进行无线通信时，各节点之间的距离d是影响网络通信能耗的最主要的因素。

2 LEACH_C算法能耗模型分析

LEACH_C算法根据无线传感器网络的网络拓扑结构把网络分成两个层次，传感器节点到路由转发节点和路由转发节点到基站。传感器节点到路由转发节点作为底层数据采集网络，主要负责采集融合各个传感器节点收集到的信息；路由转发节点到基站为上层网络，负责把底层网络收集到的信息转发到基站，该过程由于信息量比较大，转发次数比较多，因此该层网络能量消耗占整个网络能耗的比重比较大。

2.1 传感器节点到路由节点

传感器节点到路由节点作为底层网络负责把传感器采集到的数据集中到路由设备。由于该层网络负责采集融合各传感器收集到的信息，且分布比较均匀，各节点之间的距离也比较小，因此底层网络采用单跳固定分簇路由算法。路由转发节点作为底层网络的簇头，负责融合数据并转发到上层网络，各传感器采集节点通过单跳的方式把采集到的数据直接发送到路由转发节点。假设该簇的传感器节点的个数为i，则底层网络的一轮数据传输的能量消耗为：

其中ETX，ERX分别为单个节点发送和接收k比特数据消耗的能量。d为各传感器到路由节点的平均距离。由于底层网络各节点之间的距离比较小，因此采用自由空间传输模型，ETX，ERX分别为：

把式（3）带入到式（2）中，则底层网络一轮数据传输的能耗为：

2.2 路由节点到基站

路由节点到基站作为上层网络负责把采集到的数据转发到基站，由于路由节点的位置的不确定性，也就是各路由节点间的距离d随机性比较大，若简单的采用单跳分簇路由算法，当网络范围变大时，远离基站的节点能量消耗变大，并且各簇头之间单次通信的能量消耗差别也会变大。其他LEACH相关多跳算法中，由于每个簇成员个数不同就造成网络中能量消耗不均匀，并且各簇头与基站进行通信时，也没有限制多跳的次数，这就使得基站周围的簇头由于参与较多的数据转发而能量消耗过快，存在严重的“热点问题”。

综合以上各种问题，LEACH_C算法中采用不定长帧间隔的方式，让簇成员比较少的簇内节点发送数据的间隔增大，反之，簇成员比较多的簇向基站发送数据的间隔减小，这样在相同的时间内，网络中大小不同的簇向基站发送数据的次数就基本一致，很好的解决了网络中能耗不均的问题。同时，LEACH_C算法根据簇节点距离基站的距离d以及自己的平均剩余能量E(i)residual来决定该区域内的最优转发跳数，并且在选择下一跳路由时，充分考虑到路由节点的剩余能量状况，这样不仅均衡了全网的能量，同时也减少“热点问题”对网络生命周期的影响。

LEACH_C算法中最重要的是各路由转发节点多跳次数的确定，不仅要考虑到各路由节点簇中簇头和簇内节点的平均剩余能量，同时还要考虑各路由节点到基站的距离。现在我们假设有N个路由节点随机分配在半径为R的一个区域内，基站位于该区域的中心，根据路由节点到基站的距离远近把节点分成不同的区域，分别为r1，r2，r3，.....rn，如图3所示。

图3 节点分布区域划分

假设在区域R中有M个簇头，平均分布在整个区域中，位于rn区域的簇头节点和基站的通信需要rn-1区域内的簇头节点进行转发，并且每次通信的距离都在自由衰减通信模型的范围d0内。为了便于研究，假设每个簇头节点都位于各自区域的中部，并且每个区域的环宽度都是r，即r1区域的簇头处于r/2处，r2区域的簇头位于3r/2处，r2区域的簇头与基站进行通信时时通过r1区域的簇头进行转发的，以此类推，则当处于rj区域的簇头向基站发送k bit数据时，网络中单个簇头节点的能耗为：

其中l是区域rj内簇头与基站通信时经过的跳数，则经过一轮数据传输网络的整体能量消耗为：

把式(4)，(5)代入式(6)中有：

因此最优跳数即为使式(7)取得最小值时l的值，这样就可以通过对Eall求关于l的导数来得出：

由式(8)可得：

由式(9)可知，当(i-1/2)r小于d0时，也就是路由转发节点到基站的距离处于自由衰减模型范围内时，采用单跳的方式进行数据传输，反之，则采用多跳的传输方式进行数据传输，多跳的次数通过式(9)可以得出。这样，上层网络的整体能量消耗就达到了最小状态，但是一些“热点问题”还是没有得到很好的解决。

2.3 剩余能量均衡化

由以上分析可知，单跳+多跳的路由方式虽然使整个网络的能耗降到了最低状态，可是还是存在一定的“热点问题”会导致某些路由节点过早的“死亡”。LEACH_C算法中引入了节点剩余能量的因素，即每个路由节点在向基站进行通信时，把自身剩余能量同样发送给基站，由基站进行分析统计出剩余能量比较大的路由节点作为簇头节点或者作为多跳路由的中间转发节点。

假设每个路由转发节点的初始能量为E0，则一轮数据传输结束之后，每个节点的剩余能量为：

其中m，n分别为节点i接收和发送k比特数据次数。每个路由转发节点在最后一次发送数据时根据式(10)计算出自己的剩余能量Ei，和数据一起发送出去，基站接收到各个节点的能量信息之后进行分析，统计出各个区域内Ei的最大值，然后根据LEACH_C路由算法对各区域广播信息。这就很好的解决了一些转发节点的受到“热点问题”的影响而过早死亡的问题。

3 LEACH_C算法仿真

如图4所示，通过MATLAB进行LEACH_C算法的仿真，并同LEACH以及DEEC算法从网络生命周期以及数据传输数量上进行了比较。仿真场景为100*100的环境中，基站位于（50,50），节点个数为100个。通过时间周期轮数和死亡的节点数量来描述网络的生命周期。图4显示了LEACH_C算法和LEACH算法网络生命周期的对比。

图4 LEACH_C算法和LEACH算法生命周期比较

同样，把LEACH_C算法和DEEC算法也进行比较，如图5所示。

图5 LEACH_C算法和DEEC算法生命周期比较

由图4，图5可以看出，LEACH_C算法生命周期明显优于LEACH算法和DEEC算法。其第一个死亡节点出现在800轮数据传输之后，说明整个网络的能量均衡性能取得了比较理想的效果。LEACH_C算法仿真到1200轮左右时，其死亡节点分布如图6所示。其中红色节点表示死亡的节点，由图中可以看到死亡节点的分布还是比较均匀的，并没有出现死亡节点扎堆的情况，这就说明LEACH_C算法对“热点问题”的解决也是比较理想的。

图6 LEACH_C算法仿真1200轮左右死亡节点的分布情况

4 结论

综上所述，LEACH_C算法中传感器节点到路由节点网络通过固定的单跳分簇结构进行传感器信息采集；路由节点到基站网络根据他们与基站的距离划分为不同的区域，根据式(9)以及式(10)的策略确定数据转发的次数，以减轻基站周围区域的节点能量的负载。并且LEACH_C算法使用不定长帧间隔，进行每轮数据收集时，单个路由转发数据的次数大致相同，解决了因簇成员不同引起的负载分布不均衡的问题；另外，在路由选择过程中，也充分考虑路由下一跳的节点能量消耗和剩余能量的情况。因此，LEACH_C算法能够使网络中的簇头节点的负载趋于均衡，有效的减弱了“热点问题”，同时也降低了离基站较远的簇头的通信能耗；同时该算法还限制路由转发时的距离，降低了中间节点的电路开销，使离基站较近的区域的路由簇头节点和基站通信，再由基站将路由信息传递给紧邻的下一区域的簇头节点，避免了路由选择时产生的能量浪费。LEACH_C算法很适合应用于智能服装、智能环境监测，矿井下监测等低能耗分层网络，具有很好的研究价值。

[1] W.Heinzelman,A.P.Chand rakasan,H.Balak rishnan.Application-specific protocol architecture for w ire-less microsensor networks[J]. IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[2] G.Pottie and W.Kaiser, W ireless integrated netw ork sensors, Communications of the ACM,43,(2000),51-58.

[3] J.C.Zhao, A.T.Erdogan, T.A rslan. A Novel Application Specific Network Protocol for Wireless Sensor Network[J].Circuits and Systems, 2005:5894-5897.

[4] 任东海,尚凤军,王寅.一种基于时间延迟机制的无线传感器网络分簇算法[J].传感技术学报,2009,22(11)：1645-1649.

[5] 刘志,裘正定.基于分环多跳的无线传感器网络分簇路由算法[J].通信学报，2008,29(3):104-112.