刘智珺，李腊元，，杨少华

（1.武汉生物工程学院 计算机与信息工程系，湖北 武汉430415；2.武汉理工大学 计算机科学与技术学院，湖北 武汉430063）

0 引 言

在无线传感器网络中，路由算法的性能在很大程度上决定了网络的整体性能［1－2］。作为无线传感器网络核心技术之一，无线传感器网络研究的热点LEACH协议是第一个基于多簇结构的层次型路由算法［3］，也是一种低功耗自适应聚类路由算法［4］。

由于LEACH协议是基于多簇结构的路由算法，在协议中引入了 “轮”的概念，在通信过程中，将通信过程划分成轮，将簇的建立和信息的稳定通信作为每轮的两个阶段。为了降低网络能耗，稳定通信阶段时间一般比簇建立阶段要长［5］。在传感器网络中，节点通过自组织方式生成簇，采用一定的方法随机选择网络内某些节点担任簇头［6］。在簇头的选择策略上LEACH协议采取对所有节点进行随机选取的方式即轮换思想，这样很大程度的提高了节点能量使用效率。但是网络节点的分布随机、不均衡，因而无线传感器网络中的各簇内部节点的数量也不均衡，文献通过的实验结果正是证明了这一问题［7－8］，因此对于LEACH协议的能耗问题可以从这点上进行考虑。

基于LEACH协议的问题，LEACH－C［9］是在 LEACH协议的基础的一个改进协议。协议采用中心控制的机制，在建立簇的时候，对于簇头的选取由中心控制生成，通过此方法来形成簇，其簇内节点数量相对比较均衡。有了中心控制后簇头和非簇头节点的通信距离缩短了，从而降低了由簇内节点与簇头节点相互通信而产生的能量消耗，来达到降低网路能耗的目的［10］。

在LEACH－C协议中，选择簇头由中心控制，基站对所有节点的物理地址以及能量相关信息必须十分清楚，这样对于完全自组织网络不适用，因此LEACH－C协议的应用有局限。以LEACH协议作为基础，以非均匀分簇和双簇头路由作为改进思路，提出了新的降低网络总能耗控制的LEACH－DC路由协议。

1 LEACH－DC路由协议的设计

双簇头传送数据协议LEACH－DC （LEACH doublecluster）是以LEACH协议作为基础进行改进得到的协议，基本改进思想是：在簇头选择时引入双簇头 （即簇头与备选簇头节点），在簇头选择时以控制能量作为出发点采取一定措施进行限制。对于簇头节点的选择采用周期选择的方式，由于非均匀分簇，因而对簇内节点、成簇规模有一定的限定，但从整体的网络能耗角度上达到了均衡的效果，相应的也就延长了整体网络的生存时间，对于整个无线传感器网络的稳定起到较好的效果。LEACH－DC协议整个工作过程仍然使用了LEACH协议的分轮思想，对于每轮将其分成簇头的选择和簇的稳定两个阶段。由于采用双簇头思想，在簇头选择阶段中增加备选簇头。备选簇头是当前簇头的传送数据的辅助节点，通过备选簇头的引入减轻了簇头传递数据的能耗，延长了簇的生存时间提高了传送数据的效率。

1.1 簇头节点的选择

双簇头传送协议LEACH－DC对于簇头节点的选择方式是：在传感器网络节点中，对簇头的候选节点提出一定的能量要求，同时对整个网络的成簇数量也作出调整，提出簇头和备选簇头的概念。

在每轮的簇的稳定阶段，也就是传递数据阶段，网络节点向簇头节点传送最后一数据的同时将本节点目前的剩余能量的信息同步传送。簇头节点收到能量信息后计算出本簇的剩余能量的平均值。基站则由接收到的各簇平均能量值可计算得出这个无线传感器网络的平均剩余能量值。由sink广播通知，在下一轮的簇头选择时，将把能量值作为选择的参考依据，在能量超过平均能量值的节点中，对应每个节点随机的生成一个介于0－1之间的数据，再增加一个阈值T （n），若某个节点的随机数小于阈值，则将其选定为新的簇头节点［11］。阀值T （n）计算公式如下

式中：p——无线传感器网络中簇头所占的比例，r——选择簇头时网络已经进行的轮数，G′——节点能量值不超过平均能量值的集合。使用上述方式选择簇头节点后，使用广播的方式来通知网络中的其它传感器节点，节点在接受到消息以后可以根据接收信号的强弱程度判断出与簇头节点的距离，从而决定所属簇。节点向簇头节点通信确定选择，簇头节点确定本簇的节点后将会为其分配一个数据传递的时间点，为信息传递做准备［12］。

1.2 备选簇头的选择

LEACH－DC协议在簇头选择中，引入备选簇头的概念，即当前簇头传送数据的辅助节点。

备选簇头的选取方式是：确定簇头节点后，在进行分簇的过程中，无线传感器网络节点使用广播消息的方式向簇头节点提出加入请求。在提出请求的同时，对于比平均能量值高的节点可以在发送请求消息的同时附加一个申请备选簇头的信息。当簇头节点接受信息后采用时间优先的策略确定当前簇内的备选簇头，同时把备选簇头的确定消息通知给簇内的传感器网络节点。

在备选簇头的选取以及消息广播的过程中，由于传递申请成为备选簇头消息时需要消耗能量，所以对于网络节点而言此部分的能耗比LEACH协议要大，但是簇内的消息传递信息量很小并且通信距离短，因此能耗不大。对于整个备选簇头的方案而言存在额外消耗的这部分能量，在很大程度上可以避免由于个别簇头节点过早耗尽自身能量而导致的簇稳定时间减少的情况，因此对于无线传感器网络，从整体上延长了通信的时间、增加了网络的稳定。

1.3 传感器网络成簇规模的限定

1.3.1 传感器网络的最优成簇数

簇内节点个数关系着簇内节点的能量消耗。假设N为无线传感器网络中节点的总数目，若网络内的节点是被随机分布，限定其区域为矩形区域设定为M×M，为确定出最优成簇数，设定簇数为K。对于每个簇的簇头节点，其能量消耗分为3个部分：接收簇内的各个网络节点信息所消耗的能量、簇首节点自身进行信息融合所消耗的能量、簇头首节点向基站传送信息所消耗的能量。考虑到簇头节点能耗衰减为多路衰减模型，因此在一个帧内簇头节点能量消耗为

式中：l——每个消息的比特数，dtoBS——簇首节点至基站的距离。普通节点单位帧内只传输一次信息给簇首，假定将传感器网络分成K个簇，则单个簇的区域面积约为M2／K，同时假定在簇内簇头节点处于中心点，则通过计算得到ρ（x，y）是网络节点在簇内分布的概率密度。将设簇内节点是均匀分布，簇的作用区域是半径为R的圆，则簇首节点与簇内普通节点间的距离平方期望为

由普通节点的能量消耗以及簇首节点与簇内普通节点间的距离平方期望公式推导可得在单位帧内每个簇的总能量消耗为

单位帧内网络总能量消耗为

把E对k求一阶导数，并令其等于0，可求出最优簇首数为

由公式能明显看出，若优簇首数k的取值取决于基站与传感器网络节点之间的距离dtoBS。假设令传感器网络面积定为：100×100，同时节点的分布方式是均匀分布，为方便计算假定基站的位置是位于平面坐标 （50，175）处，通过计算可以得基站与传感器网络节点距离的取值范围是：75—185，由式 （6）可得出网络生成的最优簇数的范围为1＜kopt＜6。因此在LEACH－DC协议中，为了网络节点的能耗最优，在确定簇头节点后建立簇的过程中，对网络的簇内节点数目进行严格的限定，簇头占传感器网络节点总数的5%时为最优。

1.3.2 簇内节点数目的限定

在进入簇的稳定阶段之前，一旦确定了簇头节点，传感器网络中的其它节点根据接受簇头节点广播时信号的强弱程度，自由选择其加入的簇。簇内节点的数量需要进行相应的控制。对于同一个簇，当簇内节点数太多时，节点间接收数据的相关性会变差，降低数据的融合度。随着簇头节点需要转发的信息量增多，相应地其能量消耗也会增多。在簇的稳定阶段，进行信息传递时，若簇内节点较多，那么簇头节点分配给簇内网络节点传送数据的时间段相应就会减少，随之而来的簇的内部节点通信的数据量也相应减少，那么形成了簇头节点能耗过大，而簇内节点能耗小的不平衡的情况。所以在最优成簇数确定的前提下，通过簇头对簇内节点数目进行一定的限定。簇内节点的数目依据簇头节点与基站的距离而进行灵活的调整，在与基站节点距离较远的簇中限定其簇内节点数目少些，反之亦然。

2 LEACH－DC协议路由算法

确定了最优成簇数以及最优成簇的簇内节点个数后，簇的规模基本形成。以能量作为选择标准确定簇头节点以及选出备选节点后，网络路由算法思想是将簇的通信分成阶段：

在簇的稳定阶段，无线传感器网络中的各个簇的簇内节点，在簇头所分配的时间段内将其采集到的信息数据传递给簇头节点，簇头节点通过对所接收到的数据进行融合后再传送给基站节点。在此传递数据的过程中，将先设定的簇头节点最低能量阈值作为警戒线，若簇头节点的能量下降到这一阈值，表示不适合继续向基站发送数据，那么簇头节点将未传递给的基站的数据传送给备选簇头节点。备选簇头开始执行本簇内的簇头任务，负责承担数据传送，以此减轻簇头负担，降低簇头能耗。

在簇的稳定阶段持续一段时间后，整个传感器网络将进行新一轮的簇头节点的选择以及簇的重构。重新选择簇头、重新构造簇、选择备选簇头，然后进入稳定阶段实现信息传递，依此方式，不断循环。路由算法的具体流程图如图1所示。

图1 LEACH－DC协议路由算法描述

簇内节点向簇头传递信息以及簇头向基站传递信息时，采用不同的CDMA代码，使用此方式可以降低本簇内通信对其它簇的影响。

3 LEACH－DC协议仿真及结果分析

NS2是一个的网络环境仿真器，它采用的是面向对象、同时离散事件驱动的方式［13－14］，使用NS2可以完整的模拟整个无线传感器网络环境［15］。LEACH－DC协议在 NS2 2.27软件平台进行仿真实验。

协议仿真的环境系数分别是：WSNs面积为100m×100m，节点数量100，传感器网络中各节点初始能量为2J。在正常工作过程中，无线传感器网络的节点平均每一次发送信息的时间为1.2s，为了保证无线传感器网络节点在试验中的一段时间内能有信息发送，设置发送数据的时间间隔为15s，即△T＝15s；传感器网络内部数据冗余的范围值为1.2；簇头节点发送的数据包长度为L：500bit＋25bit，其具体的数据包内数据的格式如图2所示。

图2 数据包的格式

在仿真过程中，使用随机生成区间 ［1，10］内的数据来模拟传感器网络节点所采集到的信息。节点随机分布图如图3所示，在LEACH－DC协议的设计中由于簇头节点的确定使用了双簇头的方式，并且通过分析计算得到最优成簇数，然后对簇内节点数量进行相应的限定，同时对簇头节点采用了融合数据技术，降低了发送的数据量。

图3 仿真实验节点分布

图4 是每轮节点能量总消耗。由于LEACH－DC协议通过分析节点的能耗，在一定程度上限定了成簇规模，那么簇内节点的位置，虽然是随机分布但离sink节点远的簇节点较少。因此，簇内节点传送信息的能耗较小，图4能显示出每轮消耗能量LEACH－DC要低于LEACH，并且衰减情况较平稳。

图4 每轮能量总消耗

图5 比较了网络总消耗能量与时间的关系，网络仿真的能耗与时间比的分析图，反馈出LEACH－DC协议消耗的总能量要低于LEACH协议。LEACH－DC协议通过分析节点能耗，一定程度上限定了成簇规模，那么簇内节点的位置，虽然是随机分布但离sink节点远的簇节点较少。因此，簇内节点传送信息的能耗较小，每轮消耗能量要低于LEACH，并且衰减情况较平稳。

图5 传感器网络的总体能耗

图6 反馈的是网络时间与发送的数据包总数据量之间的关系。由于LEACH－DC协议在簇头选择以及簇内节点数目反面做了均衡处理，延长了簇的生存时间，因此在簇的稳定阶段网络发送数据包的数目比改进前的协议要多。但是从总体看，LEACH－DC协议由于在网络能耗方面进行了均衡，延长了整个网络的生存时间，传递的信息量比LEACH协议多。

图6 网络发送的数据包总量与时间的关系

4 结束语

以均衡能量控制作为目的，以双簇头和非均匀分簇作为手段设计的LEACH－DC协议是对LEACH协议的一种改进方法。LEACH－DC算法将节点剩余能量考虑进来，采用了新的簇头首选择方法，对网络成簇数目以及簇内节点数进行了一定的限制，采用双簇头通信预防机制。通过仿真实验以及对结果的分析，验证了改进后的路由协议从成簇优化方面、簇内网络节点生存时间等方面都得到了较有效的改善，因而提高了网络能耗的均衡性，达到延长网络生命周期的目的。当然本协议对于簇头担任时间还没有做到精确测算，在此方面还能进一步完善研究。

［1］SUN Liming，LI Jianzhong，CHEN Yu.Wireless sensor networks［M］.Beijing：Tsinghua University Press，2005：3－24（in Chinese）.［孙利民，李建中，陈渝.无线传感器网络［M］.北京：清华大学出版社，2005：3－24.］

［2］GENG Xiaoyi，CHAI Qiaolin，ZHANG Qin.A kind of energy balance of wireless sensor network clustering algorithm ［J］.Computer Engineering and Application，2007，43 （33）：141－143（in Chinese）.［耿晓义，柴乔林，张擎.一种能量均衡的无线传感器网络分簇算法 ［J］.计算机工程与应用，2007，43（33）：141－143.］

［3］ZHENG Zengwei.Some wireless sensor network routing protocols in the comparative study［J］.Computer Engineering and Design，2003，24 （9）：28－31 （in Chinese）.［郑增威，吴朝晖.若干无线传感器网络路由协议比较研究 ［J］.计算机工程与设计，2003，24 （9）：28－31.］

［4］SHENG Bo，ZHANG Shiyong.Wireless sensor network clumping routing protocol［J］.Journal of Software，2006，17 （7）：1588－1600（in Chinese）.［沈波，张世永.无线传感器网络分簇路由协议 ［J］.软件学报，2006，17 （7）：1588－1600.］

［5］REN Biao，LIU Lifeng，MA Jiang.In wireless sensor networks improved algorithm of directional diffusion agreement［J］.Journal of Electronic and Information，2006，28 （3）：562－566 （in Chinese）.［任彪，柳立峰，马建.无线传感器网络中定向扩散协议的改进算法 ［J］.电子与信息学报，2006，28 （3）：562－566.］

［6］GU Xiangpin，SUN Yanjing，QIAN Jiansheng.An improvement in wireless sensor network LEACH－ED algorithm ［J］.Sensing Technology Journal，2008，21 （10）：1770－1774 （in Chinese）.［顾相平，孙彦景，钱建生.一种改进的无线传感器网络 LEACH－ED算法 ［J］.传感 技术学 报，2008，21（10）：1770－1774.］

［7］YANG Mian，QIN Qianqin.Based on wireless sensor network routing protocol［J］.Computer Engineering and Application，2004，40 （32）：130－132 （in Chinese）.［杨冕，秦前清.基于无线传感器网络的路由协议 ［J］.计算机工程与应用，2004，40 （32）：130－132.］

［8］ WANG Ying，XIONG Mudi.Monte carlo simulation of leach protocol for wireless sensor networks ［C］.Dalian：Proceedings of the Sixth International Conference on Parallel and Distributed Computing，2005：85－88.

［9］Muruganathan S D，MA DCF，Bhasin PI，et al，A centralized energy－efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43 （3）：8－13.

［10］JIANG Hua，YUAN Xiaobin，SHEN Jie.Channel access in wireless sensor networks clustering algorithm research ［J］.Computer Engineering and Application，2006，42 （7）：22－27（in Chinese）.［姜华，袁晓兵，沈杰，等.无线传感器网络中信道接入分簇算法的研究 ［J］.计算机工程与应用，2006，42 （7）：22－27.］

［11］ZHAN Qiang，LIN Yaping.Based on grid clumps and routing algorithm ［J］.Zhongnan University of Forestry Science and Technology，2010，30 （4）：166－169 （in Chinese）.［占强，林亚平.一种基于网格的分簇路由算法 ［J］.中南林业科技大学学报，2010，30 （4）：166－169.］

［12］SUN Yugeng，ZHOU Yin，BIAN Guinian，et al.Wireless sensor network of an energy efficient clustering networking algorithm ［J］.Sensing Technology Journal，2007，20 （2）：377－381（in Chinese）.［孙雨耕，周寅，边桂年，等.无线传感器网络中一种能量有效的分簇组网算法 ［J］.传感技术学报，2007，20 （2）：377－381.］

［13］JI Yingying，ZHANG Jianwu.Based on cluster of wireless sensor network routing protocol improvement plan ［J］.Sensing Technology Journal，2008，21 （6）：1052－1054 （in Chinese）.［季莹莹，章坚武.基于簇的无线传感器网络路由协议改进方案［J］.传感技术学报，2008，21 （6）：1052－1054.］

［14］TAO Xiaolin，WANG Guifeng，WANG Yong.Based on the wireless sensor network Dijkstra clumps and routing algorithms［J］.Computer Engineering and Design，2010，31 （17）：3807－3811（in Chinese）.［陶晓玲，王桂凤，王勇.基于Dijkstra的无线传感器网络分簇路由算法 ［J］.计算机工程与设计，2010，31 （17）：3807－3811.］

［15］YU Lijuan，LI Simin.Wireless sensor network of LEACH improved algorithm design and simulation［J］.Optical Communication Research，2008，32 （5）：67－70 （in Chinese）.［于立娟，李思敏.无线传感器网络LEACH改进算法的设计与仿真 ［J］.光通信研究，2008，32 （5）：67－70.］