摘  要： 无线传感器网络由大量能量有限的传感器节点组成，这些节点一般都是靠电池供电。如何在这种情况下，尽量延长网络的生存周期是研究的热点问题。基于分簇的无线传感器网络路由算法不论是在网路生存周期方面，还是在数据融合方面都比自组织算法表现出了很大的优势。文中提出了一种基于能量和距离的ED-LEACH(Energy and Distance-LEACH)改进算法，在簇头的选举和簇的生成两个阶段都综合考虑了能量和距离这两个因素。仿真表明该算法较LEACH算法显著地延长了网络的生存期。
　

　关键词： 无线传感器网络；ED-LEACH；分簇；能量；距离

     随着微机电系统、无线通信等技术的发展，无线传感器网络在军事国防、医疗卫生、工农业控制、空间和海洋资源勘探等诸多领域发挥了越来越重要的作用。无线传感器网络由大量靠电池供电的传感器节点组成，由于电池不能更换，因此对该种网络协议及传输机制的研究中，均衡网络中传感器节点的能量消耗成为延长网络生命周期的关键因素。LEACH(Low Energy Adaptive Clustering Hierachy)算法是一种可以随机选择簇头，动态成簇的能耗低、载荷均衡且易于实现的算法。
　　尽管如此，LEACH算法还是存在很多需要改进的地方。本文基于对能量、距离两方面的综合考虑，提出了一种改进的ED-LEACH算法。仿真表明该算法减少了传感器节点的能量消耗，均衡了网络负载，从而延长了网络的生命周期。
1 LEACH算法
　　Heinzelman等提出的LEACH^[1]算法是无线传感器网络成簇的经典算法。算法中引入了“轮”的概念，每一轮由初始化和稳定工作两个阶段组成。其中，初始化阶段又可以分为簇头选举和成簇两个阶段。在选举簇头时，节点产生一个0～1之间的随机数，如果该随机数小于阈值T(n)，则广播自己是簇头的消息。T(n)可表示为：
　　
　　其中，p是簇头数量的百分比，r是选举的轮数，r mod(1/p)代表这一轮循环中当选过簇头的节点个数，G是这一轮循环中未当选过簇头的节点集合。成簇阶段，接收到簇头广播消息的非簇头节点根据所收到的信号的强弱加入就近的簇。在稳定阶段，簇头节点将接收到的该簇成员节点的数据融合并发送给基站。
　　虽然LEACH算法比较容易实现，也初步解决了负载平衡的问题，但是还有很多值得改进的地方。簇头选举时，各节点随机自行决定是否成为簇头，导致簇头的位置和簇内包含的节点个数很不均匀，并且也没有考虑到节点的剩余能量。在成簇阶段，非簇头节点采用就近原则，加入离自己最近的簇头，也没有考虑到簇头的剩余能量。本文基于对能量和距离的综合考虑，对初始化阶段的簇头选举和成簇两个子阶段进行改进。
2 改进的算法
2.1 网络模型
　　由N个随机部署的传感器节点组成的网络，其方形监测区域的大小为M×M。对网络作如下假设：
    (1)网络中的节点是静止的，且初始能量相同，并且有唯一的ID号，且节点的坐标由定位算法可得，并且已知。
    (2)基站处于固定的位置，并可以认为其能量是无限的(不靠电池供电)。
    (3)根据通信距离的远近，节点的发射功率动态可调。节点间的通信链路可靠且双向连通。
2.2 无线电能耗模型^[2]
　　传感器节点的能量主要消耗在无线传输的过程中，而且随着通信距离的增加，节点能耗呈指数增长。发送和接收1 bit数据且传输距离为d，节点消耗的能量分别为:
　　

其中：d_toBS为节点到基站的平均距离；E_DA为簇头执行数据融合的功耗；k为簇头节点数目。
　　定义E_i和E_i(r)分别为传感器节点的初始能量和在第r轮簇头选举时的剩余能量，E_total(r)为网络当前的总能量，则有:
　　
2.3 簇头的选举
　　从LEACH协议可知，簇头节点的数目对网络的生存期有一定的影响。若簇头节点过少，那么一个簇所覆盖的区域会过大，成员节点到簇头的距离会较远，传输数据能耗会很大；若簇头数目过多，由于簇头节点的能耗远大于非簇头节点，会导致整个网络节点在每轮路由中总的能耗增大，并且还会导致数据融合^[2]效率降低，产生过多不必要的数据融合。
　　通过选举产生的最优簇头节点数，应使网络在每一轮的簇重构中消耗能量最小^[3]，即使式(4)中E_round达到极小值的k值点。由(4)式可知，在其他网络参数设定的前提下，当k>0时Eround是关于k的连续函数。

　　根据极值定理可得k₀为最小值。k₀由计算能力很强的基站完成，并且每经过事先设定的若干个周期重新计算一次，因为通信中将不断有节点因能量耗尽而死亡。
　　本文在簇头选举时综合考虑能量和距离两个因素，为每个节点分配一个权值表示其适合充当簇头的程度。某个节点i在第r轮簇头选举中的竞选权值为：

　　由于ED-LEACH算法在簇头选举阶段需要知道当前网络的平均剩余能量，采用的方法是簇内节点将自身剩余能量信息嵌入每轮最后要发送的数据分组中，捎带给簇头；簇头对簇内剩余能量进行汇总，并随同融合后的数据信息发送给基站；最终由基站完成网络平均剩余能量的计算，并嵌入在新一轮的簇重构命令中，广播至所有节点。由此，在没有引入额外分组交换的条件下，完成了对网络平均剩余能量的计算^[4]。
    在初始化阶段，基站广播竞选簇头开始消息，该消息包含当前网络的平均剩余能量。节点首先判断自身剩余能量是否大于当前网络的平均剩余能量，若小于则直接放弃竞选，并在接下来的时间内加入某一簇；若大于则向基站发送竞选簇头消息，该消息包括本节点的ID和剩余能量等信息。基站收到所有参加竞选节点发送的竞选簇头消息后，根据(8)式确定的竞选权值选择最大的k0个节点作为簇头，并广播任命簇头消息，该消息包括选出的k0个簇头节点的ID。接收到此消息的节点如果发现任命的簇头中有自己，就当选为簇头。
2.4 簇的形成
　　在LEACH算法中，当非簇头节点收到多个簇头的广播消息后，仅考虑距离因素，加入离自己距离最近的簇。但是其并没有考虑簇头的当前的剩余能量，即使离自己稍微远一点的簇头当前剩余能量很多时，该节点也不会选择加入该簇，而会选择加入离自己最近的簇。这样就会造成网络的负载很不平衡，不利于延长网络的生命周期。
　　本文在非簇头节点加入簇时，综合考虑了簇头的当前剩余能量和到该簇头的距离两个因素。假设某个非簇头节点收到了n个簇头的广播消息，该消息包括簇头的ID和当前的剩余能量。定义选择加入簇的权值为：
　　　　

　　其中：E_i(r)为第i个簇头的当前剩余能量，E_i为第i个簇头的初始能量；d_i为该非簇头节点到第i个簇头的距离；d_max为网络中任意两个节点间的最远距离；α为加权系数，可以根据实际需要动态调节能量和距离所占的比重。
    由(9)式可得非簇头节点会综合考虑能量和距离两个因素，选择当前剩余能量多且距离近的簇头加入，即使W取得最大值的簇头。接下来非簇头节点向选定的簇头节点发送请求加入簇的消息，该消息包括本节点的ID和簇头节点的ID。簇头节点收到各成员节点的请求信息后，为成员建立TDMA时隙表，并把该时隙表发送给其成员节点。在簇内所有成员收到TDMA时隙表后，建立簇阶段完成，开始进入稳定阶段，各成员节点在分配的时间槽内向簇头发送数据，簇头节点融合各成员节点的数据后，发送到基站。
3 仿真实验
    利用Matlab和C++对本文提出的ED-LEACH算法和LEACH算法进行仿真比较。我们对第1个节点死亡，10个、20个、30个、40个、50个、60个、70个、80个、90个、全部节点死亡的轮数进行比较。
　　在100 m×100 m的网络中随机分布了100个节点，每个节点的初始能量为0.5 J，基站的坐标(50，50)。网络中任意两个节点的最远距离为×100 m。根据参考文献[5]可得在通常情况下，无线传输的参数为E_elec=50 nJ/bit，ε_fs=10 pJ/bit/m²，ε_mp=0.0013 pJ/bit/m⁴，数据融合消耗的能量系数E_DA=5 nJ/bit/signal。
　　对(9)式中权重因子α=0.6、0.5、0.4时ED-LEACH和LEACH算法比较结果如表1所示。

参考文献
[1] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications.2002(1)：660-670.
[2] KARL H， WILLING A. Protocols and Architectures for Wireless Sensor Networks[M].Wiley，2005.
[3] SMARAGDAKIS G， BESTAVROS I M A. A Stable Election Protocol for clustered heterogeneous Wireless Sensor　Networks.
[4] 苏莹.无线传感器网络能量有效的分簇优化算法研究.武汉：华中师范大学，2008.
[5] WANG A，HEINZELMAN W，CHANDRAKASAN A.Energy-Scalable Protocols for Battery-operated Microsensors Networks[C]//Proc. 1999 IEEE Workshop Singnal Processing Systems(SiPS’99)，Oct.1999：483-492.
[6] 俞黎阳.无线传感器网络网格状分簇路由协议和数据融合算法研究.上海：华东师范大学，2008.

    由表1可得，ED-LEACH算法不论取0.6、0.5、还是0.4时，第一个节点、一半节点、全部节点死亡所经过的轮数均比LEACH算法多。当α=0.5时算法的性能最优，第一个节点、一半节点、全部节点死亡轮数分别延长了65.69%、86.15%、50.70%。将ED-LEACH算法(α=0.5)和LEACH算法利用matlab比较结果如图1所示。

　　  本文在LEACH算法的基础上，提出了一种改进的无线传感器网络分簇算法ED-LEACH。由于本文在簇头的选举和非簇头节点加入簇时都综合考虑了能量和距离两个因素，使网络的负载比较均衡。理论分析和仿真实验一致表明ED-LEACH算法显著延长了无线传感器网络的生存周期。
　　  本文还有待改进的地方，比如在考虑数据融合时，默认为簇头节点的数据融合能力是无限的，即无论该簇中非簇头节点发送给簇头节点多少数据，都能够一次融合完成。但是实际情况是传感器节点一次数据融合的能力是有限的^[6]，如果数据量比较大，不可能一次融合全部数据，必须多次融合多次发送，这样才和现实比较接近。