WSN中基于负载均衡的EAMCT-G优化算法

阎新芳，张 汉，李 良，古晓辉

(1. 郑州大学信息工程学院，郑州 450001；2. 河南省机械设计研究院有限公司，郑州 450052)

无线传感网(wireless sensor network，WSN)具有低成本、低功耗、准静态、自组织等特点，网络节点一次性播撒后，节点能量通常不可再生．因此降低网络能量消耗、延长网络生存期成为传感网路由协议的首要设计目标[1-2]．而分簇路由算法由于其能量高效和易于维护扩展等特点被广泛研究和应用[3-6]．文献[6]提出了一种基于能量感知的有网关的多级簇树(energy-aware multilevel clustering tree with gateway，EAMCT-G)算法，它利用图论中具有极大权的极大独立集概念，让剩余能量较大的节点优先作为簇头，并在簇成员中选择一些网关节点作为中继转发，有效避免了因簇头节点之间距离过大而导致能耗增加的问题，降低了节点间通信的能耗，从而延长了整个网络的寿命．

但 EAMCT-G算法中某些簇头会因成员过多而过早死亡．为解决这个问题，笔者在 EAMCT-G算法的基础上，基于负载均衡的思想对簇成员加入簇的选择策略进行改进，使得各簇头负载比较均衡，从而能进一步延长网络的生存期，同时也能提高传送数据的效率，使算法可以应用于规模较大的传感网．

1 EAMCT-G算法

根据图论中独立集的概念，以剩余能量作为节点权值，选用权值大的一组节点构成一个具有极大权的极大独立集，同时这个极大独立集中的节点也构成了极小支配集，以这样一组支配节点作为簇头，并形成相应的簇，就可保证全网的覆盖性；分簇后，利用图论中根树的概念，先将传感器网络中的基站作为树根加入簇树集合，再将某些簇成员节点作为连接相邻 2个簇头节点的网关节点，然后利用这些网关节点逐级将所有簇头都加入到簇树中，就生成了有网关的多级簇树结构．EAMCT-G 算法[6-8]在保证全网覆盖的基础上使簇头的选择更加合理，并且通过引入网关节点弥补了簇头间通信距离过大增加传输能耗的问题；它还是一种分布式、异步并行算法，只需局域信息，便于维护更新．文献[6]中已通过仿真验证了该算法具有有效的消息和时间复杂度．

但 EAMCT-G算法存在如下问题：若是节点的能量大于所有邻居节点，它就会首先被选举为簇头，同时其一跳范围内的所有节点就会都加入以该节点为簇头的簇中，这样就会造成该节点的簇成员数量过大，形成热节点(hot spots)[9]．过重的负载压力会严重增加热节点在数据融合和路由转发方面的能量消耗，致使热节点提前死亡，缩短网络寿命．本文基于这方面考虑提出 EAMCT-G优化算法，即分簇结束后，热节点的簇成员要经过一个“挑选”的过程．在新的簇成员选择策略中，通过引入距离和能量的权值来精简热节点的成员数目，从而减轻热节点的负载压力，使网络内各簇负载均衡，有效避免某些簇头节点因能量损耗过快而较早死亡的情况．

2 基于负载均衡的EAMCT-G优化算法

2.1 综合权值和双优化阈值的引入

假设无线传感网所有节点都是同构的，根据文献[3]所示的能量模型可知每采集一轮数据簇头节点 i的能量损耗为

式中：ECH(i)包括接收簇成员信息、数据融合以及发送已融合信号至上级 3部分的耗能；nmember(i)为簇头i的簇成员总数；l为数据包长度；Eelec为发送或接受单位bit数据的能耗；EDA为簇头融合单位bit数据的能耗；d为簇头i与上级节点的距离；ε为信号放大器的放大倍数；k为常数，由选择的无线信道决定取值.相对距离短时，采用自由空间信道，取ε＝10 pJ/(bit·m-2)，k＝2；距离较远时可采用多径衰落信道，取ε＝0.001,3,pJ/(bit·m-2)，k＝4．因 EAMCT-G算法采用多跳方式传输数据，传输距离较近，采用自由空间信道．

每一轮每个簇成员节点的能量损耗为

假如网络中各簇负载均衡，则各簇簇成员数趋于相同，各簇头消耗能量也趋于相等，可得到每一轮簇头总耗能和所有节点总耗能分别为

式中：N为节点总数；CHn 为所形成的簇头总数．如果N和nCH已经确定，可得

式中 Er为剩余能量．V随 Er的增大而增大，随 Σ d2的增大而减小，相比单一权值，综合权值能更精确地反映能量的消耗情况．在对EAMCT-G算法的优化中，使用综合权值 V兼顾按剩余能量大小进行分簇的初衷，同时既可平衡各簇负载，又使离簇头较远的簇成员优先进行优化，进一步减小 Σ d2，降低能量消耗．

在引入综合权值后出现了另一个问题：某些原簇成员较多的簇头在优化后可能簇成员变得很少，而另一些原簇成员较少的簇头由于新接收的簇成员个数太多而使簇变得臃肿．上述情况可以通过设定双优化阈值来避免．假设 2个阈值 T1和 T2，规定只有nmember( i)＞T1的簇才进行优化；同时只有nmember(i) ≤T2的簇才接收新的簇成员．通过设定双优化阈值，可以有效避免优化后可能出现的新的负载不均衡的情况(仿真中取 T1= 0 .9 N / nCH，T2= 0 .6 N / nCH)．

2.2 EAMCT-G优化算法描述

在初始阶段，仍采用文献[6]中成簇 CH(v)消息和入簇 member(v，u)2个消息来完成．在开始分簇的时候，各节点首先与自己周围的节点交互 hello信息，包括权值信息、ID号和根据能量损耗计算出相邻节点间的距离，并进行相应的存储．之后根据EAMCT-G算法进行分簇，将簇头存储在CH集合中.

待分簇结束后，每个簇头发消息通报自己的簇成员，根据所给定的优化阈值 T1、T2，成员节点设定临时集合 CHtemp，并将所有 nmember( i)＞T2的簇头节点存入 CHtemp中．然后簇头进行判断：①如果 nmember(i)≤T1，则该簇不进行优化；②如果 nmember(i)＞T1，则该簇进行如下优化操作．

簇成员节点到自身的平均距离和当前所有成员节点的平均能量分别为式中：(,)d j i为节点 j到节点 i间的距离；r()E j为节点j的剩余能量．进而得到簇内所有成员节点的综合权值为

簇头节点 i向其簇成员节点 j广播 Vaverage信息．成员节点 j在得到 Vaverage信息后判断：如果节点 j的Vj≥Vaverage，则该成员仍保留在原簇中；否则，设leader(j) = 0 (leader(j) = 0 ,1,2分别代表节点 j状态为未确定、簇头、簇成员)，并在自己一跳范围内，搜索邻居节点中的簇头节点并进行如下操作．

(1)若邻居节点中没有除CHtemp外的其他簇头节点，则该成员仍保留在原簇中，并设置节点的状态leader() 2j= ．

(2)若邻居节点中有除 CHtemp外的其他簇头节点，则节点j就将除CHtemp外距离自己最近的簇头节点 k作为自己的簇头，并发送入簇信息 member(j，k)，同时设置节点的状态leader()2j= ；若出现两簇头距离相同的情况，则选择剩余能量较大者加入；剩余能量也相同时，加入ID号小的簇头．

结束分簇优化阶段，进入第2阶段有网关的簇树生成，此后按照EAMCT-G算法进行．

2.3 特例说明

假设在一个100 m× 100 m的区域内随机抛洒100个传感器节点，采用文献[3]所示能量模型，设参数l= 1 28bit/packet ，Eelec= 5 0 nJ/bit ，EDA= 5 nJ/bit，最大通信半径 R = 2 0 m．假定节点发出的消息都能被其邻居节点正确收到，不考虑重传问题且节点间不存在单向链路．优化前后的分簇效果如图1所示．

由图 1(a)和(b)对比可以看出：簇头 91、28、29、35、56、61的簇成员数大于 T1值，要进行优化；而簇头 91、28、29、35、56、59、61、64、3 的簇成员数大于T2值，不再接受新的簇成员．图1(b)中的黑色圆形节点 16、30、36、37、82、33、74、90、53、4、7、49、69、12、41、76按照优化规则重新选择了簇头节点，而灰色圆形节点 8、22、40、57、80、81、97 尽管需要进行优化，但由于邻居节点中没有簇成员数不大于 T2的簇头节点，所以依然保留在原来的簇中．特例中 18个簇优化后各簇情况与原算法对比如图2所示．

图1 优化前后的分簇效果Fig.1 Clustering results before and after optimization

图2 优化前后各簇内负载和能量分布情况Fig.2 Load and energy in each cluster before and after optimization

经过比较可以看出，无论是簇头负载还是簇成员平均能量，优化后线形的波动幅度都比优化前更小．这说明在特例这种情况下，通过综合权值对簇成员较多的簇进行优化，让一些权值小的节点分散到其他簇的策略可以减小各簇头的负载压力，各簇间能量分布也更加均衡．

3 EAMCT-G优化算法性能分析

3.1 负载平衡因子

负载平衡因子(load balance factor，LBF)[10]定义为簇内成员节点数(不包括簇头)的方差的倒数，即

式中 u = ( N - nCH) /nCH为网络中每个簇的平均成员数．使用 LBF可以量化簇的负载平衡度，LBF越大负载平衡度越好．

按特例假定场景将节点随机抛洒 100次，LBF的分布如图3所示．

经计算可得优化前和优化后的 LBF平均值分别为 0.057,4和 0.069,5，经过优化的 LBF为未优化时的1.2倍．这说明优化算法能够有效平均各簇头的负载压力，使热节点出现的几率大大降低，从而避免了原算法出现的个别簇头节点因簇成员过多能量消耗过快的情况．

图3 优化前后的LBF分布Fig.3 LBF before and after optimization

3.2 簇头轮换频率对生存期的影响

定义从算法开始运行到第1个节点死亡之间的时间为网络生存期，网络生存期同样可以以数据采集总轮数表示．图 4为节点初始能量 E = 0 .5 J 时，EAMCT-G及其优化算法定期轮换簇头对网络生存期所产生的影响．可以看出，不进行轮换的情况下，优化后生存期为 4,710轮，与优化前的 4,235轮相比提高了10%；当簇头轮换频率在 1～2,200轮/次之间时，优化后的生存期明显比优化前数值更高，平均提高10%左右，这是因为优化算法所引入的综合权值和双优化阈值能有效平衡各簇能量消耗，避免了因某些簇头负载过大导致能量消耗过快而过早死亡情况的发生；当簇头轮换频率在2,200～4,500轮/次之间时，优化后的生存期与优化前相比没有明显优势，这说明合理设定簇头轮换频率也可达到延长网络生存期的目的；之后，当轮换频率大于不轮换情况下的生存期时，轮换机制不再起作用，2条生存期曲线都呈直线状态．

图4 优化前后簇头轮换对生存期的影响Fig.4 Effects of cluster-head rotation frequency on lifetime before and after optimization

3.3 最大通信半径对生存期的影响

已知当前网络连通所需最小的 R＝18,m，簇头轮换频率设定为1,500轮/次，图5为节点最大通信半径R变化对网络生存期的影响．

图5 优化前后最大通信半径对生存期的影响Fig.5 Effects of maximal communication radius on lifetime before and after optimization

可以看到当18 m ≤ R ≤ 3 5 m 时，优化后的生存期较优化前保持相对的稳定高值，生存期平均提高了15%左右；当 R ＞3 5 m时，优化后的生存期较优化前没有明显优势且两者都减小后趋于平缓，这是因为随着 R增大，d的上限增大，节点间交互信息的能耗必然增加[3]，且形成簇数也会减少，此时进行优化不但效果不好，甚至还可能耗费更多的能量，同时簇数减少还会造成簇成员数增加，簇头能量消耗更大．由此可知在保持网络连通的前提下，减小节点发射功率可以延长网络寿命．

3.4 优化算法复杂度

优化算法的消息复杂度为 O(n)，时间复杂度为O(n)．

证明 设网络中有n个节点，BS首先向邻居节点中的簇头节点作为启动节点．当某节点簇成员数大于 T时，才会运行优化算法，并且发送的消息只是增加一个综合权值V，消息的复杂度仍然是O(n)．

由于该算法是分布式、异步、并行的算法，基站邻居中的簇头节点都可以作为启动节点，因此算法可以并行运算，最终的反馈时间也只和生成簇树的高度有关，从终端的叶子节点反馈到基站结束算法的运行时间为树高H(0＜H＜n)．另外，在运行算法前，相邻节点已经通过相互交换信息得到自己邻居的权值信息，所以，每一个节点在选择簇头的时候只需进行简单比较，不再需要进行额外的运算．这样，n+1就是算法的最大运行时间，因此，O(n)仍然是不变的．

4 结 语

通过分析 EAMCT-G算法中个别簇头负载过重的原因，引入兼顾剩余能量和距离的综合权值对簇成员选择策略进行进一步改进，一旦出现簇成员数目臃肿的簇，就对该簇的成员进行优化，使某些综合权值小的簇成员节点加入离自己最近的其他簇头，从而使各簇负载均衡；同时引入双优化阈值，分别对要优化的簇和要接收新成员的簇进行相应限制，避免优化后可能出现的新的负载不均衡情况．仿真实验表明，优化算法能有效提高网络的负载平衡度，在簇头轮换和最大通信半径不同的情况下，与原算法相比在相当大的范围能有效提高网络的生存期．EAMCT-G优化算法属于分布式、异步并行算法，具有与原算法相同的消息复杂度和时间复杂度，可适用于较大规模的无线传感网络．

［1］Akkaya K，Younis M. A survey on routing protocols for wireless sensor networks [J]. Ad Hoc Networks，2005，3(3)：325-349.

［2］Al-karaki J N，Kamal A E. Routing techniques in wireless sensor networks：A survey [J]．IEEE Wireless Communication，2004，11(6)：6-28.

［3］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application- specific protocol architecture for wireless microsensor network [J].Wireless Communications，2002，1(4)：660-670.

［4］Manjeshwar A，Agrawal D P. TEEN：A routing protocol for enhanced efficiency in wireless sensor networks[C]//IEEE International Proceedings of 15,th Parallel and Distributed Processing Symposium.California，USA，2001：2009-2015.

［5］Lindsey S，Raghavendra C S. PEGASIS：Powerefficient gathering in sensor information systems [C]//IEEE International Conference on Communications，New York，USA，2002：1125-1130.

［6］An Na，Yan Xinfang，Zhu Yufang，et al. A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks[C]//Proceedings of the IET International Communication Conference on Wireless Mobile and Sensor Networks.Shanghai，China，2007：462-465．

［7］阎新芳，刘爱琴，杨 挺. 基于极小独立支配集的MANET虚拟骨干网算法[J]. 电子学报，2007，35(6)：1134-1138.

Yan Xinfang，Liu Aiqin，Yang Ting. A virtual backbone network algorithm based on a minimal independent dominating set for MANETs [J].Acta Electronica Sinica，2007，35(6)：1134-1138(in Chinese).

［8］阎新芳，张永琦，王志龙，等. 无线传感器网络中基于网关的多级簇树维护更新算法[J]. 传感技术学报，2010，23(2)：260-264.

Yan Xinfang，Zhang Yongqi，Wang Zhilong，et al.Maintenance and update algorithm of hierarchical clustering with gateway for wireless sensor network [J].Chinese Journal of Sensors and Actuators，2010，23(2)：260-264(in Chinese).

［9］唐云建，石为人，易 军，等. 面向 WSN 数据汇集应用的动态负载均衡算法[J]. 计算机工程与应用，2011，47(6)：122-126.

Tang Yunjian，Shi Weiren，Yi Jun，et al. Dynamic load-balancing algorithm of WSN for data gathering application [J].Computer Engineering and Applications，2011，47(6)：122-126(in Chinese).

［10］张 擎，柴乔林. 基于最大连通度分簇的负载均衡分簇算法[J]. 计算机工程与设计，2008，29(2)：340-343.

Zhang Qing，Chai Qiaolin. Load balance clustering algorithm based on maximum link degree clustering [J].Computer Engineering and Design，2008，29(2)：340-343(in Chinese).