L5、负载均衡的无线传感器网络自适应分组成簇算法

1、收稿日期：20110114；修回日期：20110308。作者简介：胡亚明（1982），男，湖北黄梅人，硕士研究生，主要研究方向：计算机网络与通信；邓亚平（1948），男，重庆人，教授，主要研究方向：计算机网络与通信、信息安全；杨佳（1984），男，河南洛阳人，硕士研究生，主要研究方向：计算机网络、信息安全。文章编号：10019081（2011）080205603doi：103724/SPJ1087201102056负载均衡的无线传感器网络自适应分组成簇算法胡亚明，邓亚平，杨佳（重庆邮电大学计算机科学与技术学院，重庆400065）(all_the_same126com)摘要：分析了分簇路由协议中

2、的经典低功耗自适应集簇分层型协议（LEACH）算法与分组成簇算法SGCH的不足，提出了一种分布式分组成簇算法AGCH。首先分布式随机生成候选组首，然后通过距离竞争将所有节点分为固定的分组；各分组选取簇首时，综合考虑节点的剩余能量及其簇内通信代价。仿真实验表明，该算法能有效均衡网络能耗，延长网络的稳定期。关键词：无线传感器网络；负载均衡；自适应分组成簇；距离竞争中图分类号：TP393027文献标志码：ALoad-balancedadaptivegroupclusteringalgorithmforwirelesssensornetworkHUYa-ming，DENGYa-ping，YANGJia

3、(SchoolofComputerScienceandTechnology，ChongqingUniversityofPostsandTelecommunications，Chongqing400065，China)Abstract:Incluster-basedroutingalgorithms，thedrawbacksofclassicalLowEnergyAdaptiveClusteringHierarchy(LEACH)algorithmandSteadyGroupClusteringHierarchy(SGCH)algorithmwereanalyzedtoproposeanewad

4、aptivegroupclusteringhierarchy(AGCH)algorithmDuringthegroupstage，thegroupheadscandidatewerefirstlyrandomlyselected，andthenallthenetworknodesweredividedintofixedgroupsthroughrangecompetitionamongtheheadsWhenselectingclusterhead，eachgroupconsiderednotonlytheresidentialenergyofnodes，butalsotheirintergr

5、oupcommunicationcostThesimulationresultsshowthattheproposedalgorithmcaneffectivelybalancethenetworkenergyconsumptionandprolongthestabilityperiodofsensornetworksKeywords:WirelessSensorNetwork(WSN);loadbalance;adaptivegroupclustering;rangecompetition0引言无线传感器网络（WirelessSensorNetwork，WSN）是由部署在监测区域内大量具有微

6、处理能力的微型传感器节点组成，并通过无线通信方式形成的一种自组织网络。传感器网络以其低成本、低功耗、快速展开等特点，在军事、环境监测、工商业及医疗等领域都具有巨大的实用价值1。路由协议是无线传感器网络的主要研究方向之一。其中，基于簇的路由协议因能有效降低网络能耗和增强网络的可扩展性，已得到广泛的研究。分簇路由协议的主要思想是根据某种策略将网络划分为若干子区域，称之为“簇”。各区域（一个簇）通常包含一个簇首节点和其他簇成员节点。成员节点向簇首发送所收集的数据，簇首负责数据融合及压缩并将其传送至基站。文献23比较并总结了一些典型分簇路由算法的特点和适用性。其中低功耗自适应集簇分层型协议（LowEn

7、ergyAdaptiveClusteringHierarchy，LEACH）4是最早提出且比较成熟的分布式分簇路由协议，很多分簇算法都是在它的基础上发展而来。1问题描述LEACH的基本思想是以循环的方式等概率随机选择簇首，将网络的能耗均匀分配到每个传感器节点，从而延长网络的生命周期。但随机性簇首选择易导致如下问题：1）簇首分布不均，导致分簇不均匀，进而使簇首负载不均衡，缩短了网络稳定期（第一个节点死亡时间）；2）簇首数目波动大，难以达到理论最优值；3）簇首选择未考虑能量因素，导致网络负载不均衡。为此，文献5提出了一种分组成簇算法SGCH（SteadyGroupClusteringHierarc

8、hy）算法，基本思想是：先根据距离把网络节点等分为若干组，然后选择各组中剩余能量最多的节点作为簇首。其余节点加入最近的簇首，形成分布均匀的簇结构，从而克服了LEACH原有的不足，延长了网络稳定期。其具体算法过程如下。SGCH中簇的建立分为分组与成簇两个阶段。在分组阶段，基站向所有节点广播分组请求（group_request_msg）消息，接收到的节点返回确认（ACK）。基站选择最后一个响应节点作为第一组组首（GH1）并向其发送组首通知（GH_inform_msg），内容包含分组标识（GID）、分组数k与分组规模阈值Nalive/k（Nalive为当前存活节点数）。类似于基站，GH1继续广播成组

9、请求，当接收到的响应消息个数超过分组阈值时，GH1选择下一个响应节点作为下组组头GH2并向其发送组首通知，同时向之前的响应节点发送成组协定（groupagreement_msg）以召集为组成员。此过程依次进行直至第k个组首，GHk将广播最终成组（last_group_msg）消息，召集所有未分组节点加入第k组。当基站接收到最终成组消息，将通知所有节点分组过程结束。在成簇阶段，各组中选择剩余能量最多的节点作为簇首，剩余节点选择最近的簇首加入。第31卷第8期2011年8月计算机应用JournalofComputerApplicationsVol31No8Aug2011从以上过程可以看出，SGCH中

10、的分组以扩散的方式串行进行，不仅过程较慢，且组首需向全网广播分组消息，导致算法可扩展性不好，不适合较大规模网络。其次，SGCH在组内选择簇首时仅考虑节点剩余能量，使得簇首分布仍具有较大随机性，易导致簇首相距过近，增加了通信干扰和分簇的不均匀性。本文提出一种分布式分组成簇算法AGCH（AdaptiveGroupClusteringHierarchy），克服了SGCH的不足。基本思想如下：1）通过分布式并行竞争算法快速完成分组过程；2）簇首选择考虑节点的簇内通信代价，且同组节点直接成为簇成员，以减少成簇成本。2AGCH算法21网络模型本文假定传感器节点均匀散布在一个方形区域内，且：1）所有传感器节

11、点相同，部署后不再发生移动。每个节点具有唯一标识（ID）。2）通信信道对称。节点可根据接收信号强度估算出发送者到自身的距离6。3）节点可根据自身与接收者的距离远近，自由调节发射功率以节约能量。根据文献5中的能量模型，节点发送L比特数据到距离为d的接收方，消耗的能量：ETX（L，d）=LEelec+Lfsd2，ddoLEelec+Lmpd4，ddo（1）其中：Eelec表示无线收发电路每比特所消耗能量，fs和mp取决于收发放大器，do为距离阈值。节点接收L比特数据所消耗能量为：ERX（L）=LEelec（2）将m个L比特长数据包融合所耗能量为：EF=mLEDA（3）其中EDA表示融合1比特数据所

12、消耗的能量。22算法描述算法分为分组和成簇两个阶段。1）在分组阶段，网络节点根据相互距离被划分为若干组。经过一个较长分组周期后，网络将重新分组。2）在成簇阶段，每组选举其中通信代价较小节点作为簇首。在采用分簇算法的传感器网络中，簇首负担较重，故AGCH算法在每个数据收集周期的开始重新成簇。AGCH算法将时间划分为轮（round），一个数据收集周期对应一轮。如图1所示，首先是分组期（groupstage），节点被划分成组；其次是成簇期（clusterstage），由各组选出簇首并成簇；最后是稳定传输期（steadystage），各个簇将收集的数据发送给基站。图1AGCH算法的时间划分221分组阶

13、段组首通过分布式的距离竞争算法生成，并以节点ID作为比较依据。具体分组过程如下。每个节点产生一个01的随机数，如果这个数小于概率阈值T，则该节点成为候选组首，参与竞争。设传感器节点总数为N，监测区域面积为A，最优分簇数为k，则候选组首的竞争区域半径为u*R，其中u1，2，为距离调节因子。R按式（4）计算：R=Ak槡（4）候选组首i的竞争节点集合Scp定义为：iScp=j|j是候选组首，且distance（i，j）u*R各候选组首在其竞争区域内广播竞选消息（GH_compete_msg），并根据收到的广播消息构建其相邻竞争节点集合Scp。当Scp构建完毕，节点根据以下规则进行组首的竞选：节点i需

14、要等待其竞争集合中ID先于它的所有节点先做出决策，然后才能确定自身是否担任组首。若节点i发现自身ID先于其竞争集合中的节点，则它赢得竞争，并在以2R为半径的范围内广播分组请求消息（group_request_msg）。如果候选节点j收到来自i的分组请求，且i在其竞争集合中，则j退出竞争，成为普通节点，并广播Quit_Elect消息以通知其竞争集合中的节点。若候选节点m收到来自j的退出消息，且jmScp，则m将j从其竞争邻节点集合中删除。最终，收到分组请求的节点（包括已退出竞选的节点），若还未加入任何分组，则向发出请求的组首返回确认消息ACK。组首选择前Nalive/k个响应节点作为其分组成员，

15、并通知基站分组成功（group_success_msg）。当基站收到k个成功通知，将广播最终成组消息（last_group_msg）。若节点收到last_group消息，且仍未加入任何分组，则选择最近组首，发送加入消息（join_group_msg）通知该组首。此过程结束后，网络中的节点被分为k个组。222成簇阶段成簇阶段首先要在组内选择簇首。根据21节的网络能量模型，簇内能耗可分为两部分：1）成员节点向簇首发送数据所耗能量；2）簇首接收并融合数据所耗能量。其中：2）中能耗只与簇规模和接收数据长度有关；而1）中能耗取决于簇首位置，若要减少此部分能耗，必须使簇首到各成员节点的传输距离平方和尽量小

16、。由此定义节点i的簇内通信代价：cost（i）=jG（i），jid（i，j）槡2（5）其中：G（i）表示节点i所在分组的节点集；d（i，j）表示节点i、j间的距离。图2簇内通信代价为减少通信与计算开销，本文使用节点到组内其他节点的最大与最小距离来估算其通信代价。图2为某个半径为2R的分组，组首位于圆心，某成员节点i与组首的距离为h。因为网络节点分布密度均匀，故使用2R+h和2Rh来估计节点i与组内其他节点的最大与最小距离，可得最终算式（6）：7502第8期胡亚明等：负载均衡的无线传感器网络自适应分组成簇算法cost（i）=（2R+h）2+（2Rh）槡2=2（4R2+h2槡）（6）本文以EV作为

17、组内簇首的选择依据，如式（7）：EV（i）=RE（i）*cost（i）cost均值（7）组内每个节点向组首发送竞选消息（EV_msg），内容包含节点剩余能量RE。组首根据式（7）计算并选择EV值最大的组员作为簇首。并在组内广播DEC_msg（declaringanewclusterhead）消息，内容包括簇首ID和其分组ID，同组节点自动成为其簇成员8。在数据稳定传输阶段，簇首会向基站周期性捎带报告簇内的存活节点数，基站汇总后得出Nalive以便下次分组时通知各节点。3实验结果及分析同文献5，本文的仿真实验基于Matlab。实验使用的具体配置参数见表1。表1网络配置参数参数取值监测区域100m

18、×100m基站位置(0，0)m节点数量100节点初始能量05JEelec50nJ/bfs10pJ/(b·m2)mp00013pJ/(b·m4)do87mEDA5nJ/bMessagesize50bDatasize4000b本文算法的其他参数设置为T=04，u=15，其他算法中的参数通过多次实验来找出其最优取值。为了评估算法对网络性能的影响，仿真实验测定了以下4个指标9：1）簇规模方差。用来评价分簇的均匀程度，直接相关簇首负载均衡。2）节点能量方差10。反映整个网络的能耗均匀程度。3）网络稳定期。第一个节点死亡时间。4）存活节点数。网络运行中存活的节点数目。为了比较

19、算法在平衡各个簇规模方面的作用，在网络稳定期内平均抽取了算法运行过程中的分簇，如图3所示。图3簇规模方差比较可以看出，SGCH的簇规模波动较大，各个簇的规模差距在39，显示出SGCH所采用的成簇策略仍有较大随机性，不能很好地控制簇规模；而AGCH的波动较为平稳，规模差距集中在25，说明AGCH能有效保持分簇的均匀性。此外，在网络运行过程中，统计了全网节点的能量方差，节点的能量方差越小，全网能耗分布越均匀，如图4所示。图4节点能量方差比较由图4可知，SGCH的方差呈递增趋势，且幅度较大，而AGCH则呈稳定递减趋势，幅度小且稳定，这也进一步说明AGCH可以有效平衡网络负载。图5显示的是网络稳定期和

20、存活节点数的比较。由于AGCH算法较好地均衡了网络中各节点的能量消耗，因此网络具有更长的稳定期，且稳定期占总生命期比例较高。其次，由于SGCH算法中网络能耗不均匀，导致在网络生命末期仍有少量残余节点在无效运行，而AGCH则大大缩短了网络不稳定期，有效利用了网络能量。图5生存节点数随轮数变化情况4结语本文分析了LEACH及分组成簇算法SGCH，针对它们网络负载不均衡的不足，通过分布式距离竞争加快了分组过程，提高了算法的可扩展性，同时保持了分簇的均匀性与稳定性，并结合通信代价估计改进了簇首选择策略，减少了簇内传输能耗。实验表明，AGCH算法能有效均衡网络负载到各节点，从而延长了网络的稳定期。参考文

21、献：1AKYILDIZIF，SUWEILIAN，SANKARASUBRAMANIAMY，etalASurveyonsensornetworksJIEEECommunicationsMagazine，2002，40(8):1021142沈波，张世永，钟亦平无线传感器网络分簇路由协议J软件学报，2006，17(7):158816003陈闻杰，陈迅，高丽强，等无线传感器网络成簇算法研究J小型微型计算机系统，2008，29(2):2192254HEINZELMANW，CHANDRAKASANA，BALAKRISHNANHEnergy-efficientcommunicationprotocolforw

22、irelessmicrosensornet-workC/Proceedingsofthe33rdAnnualHawaiiInternationalConferenceonSystemSciencesWashington，DC:IEEEComputerSociety，2000:30053014(下转第2061页)8502计算机应用第31卷的结果是104次实验的平均。图24分别是g（t）自相关函数的协方差曲线，gc（t）自相关函数的协方差曲线，gc（t）和gs（t）之间互相关函数的协方差曲线。图2g（t）自相关函数的协方差曲线图3gc（t）自相关函数的协方差曲线图4gc（t）和gs（t）之间相关函

23、数的协方差曲线从图2、3中，可以明显地注意到改进模型自相关函数的协方差明显小于Clarke模型。因为改进模型中入射波到达角n的协方差小于Clarke模型中入射波到达角n的协方差。这一结果也说明对于给定N改进模型比Clarke模型的收敛速度快，并且更接近理想二阶统计特性。图4中Clarke模型中复信号中实虚部之间相关函数的协方差比改进模型的大。改进模型中复信号的实虚部相互独立，所以它们互不相关，这也是产生Rayleigh衰落信道模型需要满足的重要特性。4结语本文对模拟Rayleigh衰落信道的几个模型进行了性能分析。从仿真结果和分析中可以看出，AR模型不适合产生Rayleigh衰落信道。因为当A

24、R模型阶数升高时，Yule-Walker等式中的自相关矩阵会不稳定并由此带来数值计算上的缺陷。同时，在Clarke模型的基础上提出了它的改进模型。仿真结果表明：改进模型的相关统计特性优于Clarke模型。因此，改进模型是一种较好的、可用于产生Rayleigh衰落信道的仿真模型。参考文献：1HAYKINSAdaptivefiltertheoryM3rdedNewYork:Pren-ticeHall，19962CLARKERHAstatisticaltheoryofmobile-radioreceptionJBellSystemTechnologyJournal，1968，47(6):957100

25、03JAKESWC，COXDCMicrowavemobilecommunicationsMNewYork:Wiley，19944BADDOURKE，BEAULIEUNCAutoregressivemodelsforfadingchannelsimulationC/GLOBECOM'01:IEEEGlobalTelecom-municationsConferenceWashington，DC:IEEEComputerSociety，2001:118711925BEAULIEUNC，POPMFDesignofwide-sensestationarysum-of-sinusoidsfadin

26、gchannelsimulatorsC/ICC2002:IEEEInterna-tionalConferenceonCommunicationsWashington，DC:IEEEComputerSociety，2001:6997086XIAOC，ZHENGYR，BEAULIEUNStatisticalsimulationmod-elsforRayleighandRicianfadingC/ICC'03:IEEEInternation-alConferenceonCommunicationsWashington，DC:IEEEComput-erSociety，2003:352435297XIAOCHENGSHAN，ZHENGYR，XIAOCSNovelsum-of-sinu-soidssimulationmodelsforRayleighandRicianfadingchannelsJIEEETr