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

收稿日期:2011-01-14;修回日期:2011-03-08。

作者简介:胡亚明（1982-），男，湖北黄梅人，硕士研究生，主要研究方向：计算机网络与通信； 邓亚平（1948-），男，重庆人，教授，主要研究方向：计算机网络与通信、信息安全； 杨佳（1984-），男，河南洛阳人，硕士研究生，主要研究方向：计算机网络、信息安全。

文章编号:1001-9081（2011）08-02056-03doi:10.3724/SP.J.1087.2011.02056

（重庆邮电大学 计算机科学与技术学院，重庆400065）

（）

摘 要:分析了分簇路由协议中的经典低功耗自适应集簇分层型协议（LEACH）算法与分组成簇算法――SGCH的不足，提出了一种分布式分组成簇算法――AGCH。首先分布式随机生成候选组首，然后通过距离竞争将所有节点分为固定的分组；各分组选取簇首时，综合考虑节点的剩余能量及其簇内通信代价。仿真实验表明，该算法能有效均衡网络能耗，延长网络的稳定期。

关键词:无线传感器网络；负载均衡；自适应分组成簇；距离竞争

中图分类号: TP393.027文献标志码:A

Load-balanced adaptive group clustering algorithm for wireless sensor network

HU Ya-ming, DENG Ya-ping, YANG Jia

（School of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China）

Abstract: In cluster-based routing algorithms, the drawbacks of classical Low Energy Adaptive Clustering Hierarchy （LEACH） algorithm and Steady Group Clustering Hierarchy （SGCH） algorithm were analyzed to propose a new adaptive group clustering hierarchy （AGCH） algorithm. During the group stage, the group heads candidate were firstly randomly selected, and then all the network nodes were divided into fixed groups through range competition among the heads. When selecting cluster head, each group considered not only the residential energy of nodes, but also their intergroup communication cost. The simulation results show that the proposed algorithm can effectively balance the network energy consumption and prolong the stability period of sensor networks.

Key words: Wireless Sensor Network （WSN）; load balance; adaptive group clustering; range competition

0 引言

无线传感器网络（Wireless Sensor Network， WSN）是由部署在监测区域内大量具有微处理能力的微型传感器节点组成，并通过无线通信方式形成的一种自组织网络。传感器网络以其低成本、低功耗、快速展开等特点，在军事、环境监测、工商业及医疗等领域都具有巨大的实用价值［1］。

路由协议是无线传感器网络的主要研究方向之一。其中，基于簇的路由协议因能有效降低网络能耗和增强网络的可扩展性，已得到广泛的研究。分簇路由协议的主要思想是根据某种策略将网络划分为若干子区域，称之为“簇”。各区域（一个簇）通常包含一个簇首节点和其他簇成员节点。成员节点向簇首发送所收集的数据，簇首负责数据融合及压缩并将其传送至基站。

文献［2-3］比较并总结了一些典型分簇路由算法的特点和适用性。其中低功耗自适应集簇分层型协议（Low Energy Adaptive Clustering Hierarchy, LEACH）［4］是最早提出且比较成熟的分布式分簇路由协议，很多分簇算法都是在它的基础上发展而来。

1 问题描述

LEACH的基本思想是以循环的方式等概率随机选择簇首，将网络的能耗均匀分配到每个传感器节点，从而延长网络的生命周期。但随机性簇首选择易导致如下问题：

1）簇首分布不均，导致分簇不均匀，进而使簇首负载不均衡，缩短了网络稳定期（第一个节点死亡时间）；

2）簇首数目波动大，难以达到理论最优值；

3）簇首选择未考虑能量因素，导致网络负载不均衡。

为此，文献［5］提出了一种分组成簇算法――SGCH（Steady Group Clustering Hierarchy）算法，基本思想是：先根据距离把网络节点等分为若干组，然后选择各组中剩余能量最多的节点作为簇首。其余节点加入最近的簇首，形成分布均匀的簇结构，从而克服了LEACH原有的不足，延长了网络稳定期。其具体算法过程如下。

SGCH中簇的建立分为分组与成簇两个阶段。在分组阶段，基站向所有节点广播分组请求（group_request_msg）消息，接收到的节点返回确认（ACK）。基站选择最后一个响应节点作为第一组组首（GH1）并向其发送组首通知（GH_inform_msg），内容包含分组标识（GID）、分组数k与分组规模阈值Nalive/k（Nalive为当前存活节点数）。类似于基站，GH1继续广播成组请求，当接收到的响应消息个数超过分组阈值时，GH1选择下一个响应节点作为下组组头GH2并向其发送组首通知，同时向之前的响应节点发送成组协定（group agreement_msg）以召集为组成员。此过程依次进行直至第k个组首，GHk将广播最终成组（last_group_msg）消息，召集所有未分组节点加入第k组。当基站接收到最终成组消息，将通知所有节点分组过程结束。在成簇阶段，各组中选择剩余能量最多的节点作为簇首，剩余节点选择最近的簇首加入。

从以上过程可以看出，SGCH中的分组以扩散的方式串行进行，不仅过程较慢，且组首需向全网广播分组消息，导致算法可扩展性不好，不适合较大规模网络。其次，SGCH在组内选择簇首时仅考虑节点剩余能量，使得簇首分布仍具有较大随机性，易导致簇首相距过近，增加了通信干扰和分簇的不均匀性。本文提出一种分布式分组成簇算法――AGCH（Adaptive Group Clustering Hierarchy），克服了SGCH的不足。基本思想如下：

1）通过分布式并行竞争算法快速完成分组过程；

2）簇首选择考虑节点的簇内通信代价，且同组节点直接成为簇成员，以减少成簇成本。

2 AGCH算法

2.1 网络模型

本文假定传感器节点均匀散布在一个方形区域内，且：

1）所有传感器节点相同，部署后不再发生移动。每个节点具有唯一标识（ID）。

2）通信信道对称。节点可根据接收信号强度估算出发送者到自身的距离［6］。

3）节点可根据自身与接收者的距离远近，自由调节发射功率以节约能量。

根据文献［5］中的能量模型，节点发送L比特数据到距离为d的接收方，消耗的能量：

ETX（L,d）LEelec+Lεfsd2, d

LEelec+Lεmpd4, d≥do （1）

其中：Eelec表示无线收发电路每比特所消耗能量，εfs和εmp取决于收发放大器，do为距离阈值。

节点接收L比特数据所消耗能量为：

ERX（L）LEelec（2）

将m个L比特长数据包融合所耗能量为：

EFmLEDA（3）

其中EDA表示融合1比特数据所消耗的能量。

2.2 算法描述

算法分为分组和成簇两个阶段。1）在分组阶段，网络节点根据相互距离被划分为若干组。经过一个较长分组周期后，网络将重新分组。2）在成簇阶段，每组选举其中通信代价较小节点作为簇首。在采用分簇算法的传感器网络中，簇首负担较重，故AGCH算法在每个数据收集周期的开始重新成簇。

AGCH算法将时间划分为轮（round）,一个数据收集周期对应一轮。如图1所示，首先是分组期（group stage），节点被划分成组；其次是成簇期（cluster stage），由各组选出簇首并成簇；最后是稳定传输期（steady stage），各个簇将收集的数据发送给基站。

图1 AGCH算法的时间划分

2.2.1 分组阶段

组首通过分布式的距离竞争算法生成，并以节点ID作为比较依据。具体分组过程如下。

每个节点产生一个0～1的随机数，如果这个数小于概率阈值T，则该节点成为候选组首，参与竞争。

设传感器节点总数为N，监测区域面积为A，最优分簇数为k，则候选组首的竞争区域半径为u*R，其中u∈［1,2］，为距离调节因子。R按式（4）计算：

R（4）

候选组首i的竞争节点集合Scp定义为：

i.Scp{j|j是候选组首，且distance（i, j）

各候选组首在其竞争区域内广播竞选消息（GH_compete_msg），并根据收到的广播消息构建其相邻竞争节点集合Scp。当Scp构建完毕，节点根据以下规则进行组首的竞选：节点i需要等待其竞争集合中ID先于它的所有节点先做出决策，然后才能确定自身是否担任组首。

若节点i发现自身ID先于其竞争集合中的节点，则它赢得竞争，并在以2R为半径的范围内广播分组请求消息（group_request_msg）。如果候选节点j收到来自i的分组请求，且i在其竞争集合中，则j退出竞争，成为普通节点，并广播Quit_Elect消息以通知其竞争集合中的节点。若候选节点m收到来自j的退出消息，且j∈m.Scp，则m将j从其竞争邻节点集合中删除。

最终，收到分组请求的节点（包括已退出竞选的节点），若还未加入任何分组，则向发出请求的组首返回确认消息ACK。组首选择前Nalive/k个响应节点作为其分组成员，并通知基站分组成功（group_success_msg）。当基站收到k个成功通知，将广播最终成组消息（last_group_msg）。

若节点收到last_group消息，且仍未加入任何分组，则选择最近组首，发送加入消息（join_group_msg）通知该组首。

此过程结束后，网络中的节点被分为k个组。

2.2.2 成簇阶段

成簇阶段首先要在组内选择簇首。根据2.1节的网络能量模型，簇内能耗可分为两部分：

1）成员节点向簇首发送数据所耗能量；

2）簇首接收并融合数据所耗能量。

其中：2）中能耗只与簇规模和接收数据长度有关；而1）中能耗取决于簇首位置，若要减少此部分能耗，必须使簇首到各成员节点的传输距离平方和尽量小。由此定义节点i的簇内通信代价：

cost（i）（5）

其中：G（i）表示节点i所在分组的节点集；d（i, j）表示节点i、 j间的距离。

图2 簇内通信代价

为减少通信与计算开销，本文使用节点到组内其他节点的最大与最小距离来估算其通信代价。图2为某个半径为2R的分组，组首位于圆心，某成员节点i与组首的距离为h。因为网络节点分布密度均匀，故使用2R+h和2R-h来估计节点i与组内其他节点的最大与最小距离，可得最终算式（6）：

cost（i）（6）

本文以EV作为组内簇首的选择依据，如式（7）：

EV（i）（7）

组内每个节点向组首发送竞选消息（EV_msg），内容包含节点剩余能量RE。组首根据式（7）计算并选择EV值最大的组员作为簇首。并在组内广播DEC_msg（declaring a new cluster head）消息，内容包括簇首ID和其分组ID，同组节点自动成为其簇成员［8］。

在数据稳定传输阶段，簇首会向基站周期性捎带报告簇内的存活节点数，基站汇总后得出Nalive以便下次分组时通知各节点。

3 实验结果及分析

同文献［5］，本文的仿真实验基于Matlab。实验使用的具体配置参数见表1。

表1 网络配置参数

Message size50bData size4000b

本文算法的其他参数设置为T0.4,u1.5，其他算法中的参数通过多次实验来找出其最优取值。

为了评估算法对网络性能的影响，仿真实验测定了以下4个指标［9］：1）簇规模方差。用来评价分簇的均匀程度，直接相关簇首负载均衡。2）节点能量方差［10］。反映整个网络的能耗均匀程度。3）网络稳定期。第一个节点死亡时间。4）存活节点数。网络运行中存活的节点数目。

为了比较算法在平衡各个簇规模方面的作用，在网络稳定期内平均抽取了算法运行过程中的分簇，如图3所示。

图3 簇规模方差比较

可以看出，SGCH的簇规模波动较大，各个簇的规模差距在3～9，显示出SGCH所采用的成簇策略仍有较大随机性，不能很好地控制簇规模；而AGCH的波动较为平稳，规模差距集中在2～5，说明AGCH能有效保持分簇的均匀性。此外，在网络运行过程中，统计了全网节点的能量方差，节点的能量方差越小，全网能耗分布越均匀，如图4所示。

图4 节点能量方差比较

由图4可知，SGCH的方差呈递增趋势，且幅度较大，而AGCH则呈稳定递减趋势，幅度小且稳定，这也进一步说明AGCH可以有效平衡网络负载。

图5显示的是网络稳定期和存活节点数的比较。由于AGCH算法较好地均衡了网络中各节点的能量消耗，因此网络具有更长的稳定期，且稳定期占总生命期比例较高。其次，由于SGCH算法中网络能耗不均匀，导致在网络生命末期仍有少量残余节点在无效运行，而AGCH则大大缩短了网络不稳定期，有效利用了网络能量。。

图5 生存节点数随轮数变化情况

4 结语

本文分析了LEACH及分组成簇算法――SGCH，针对它们网络负载不均衡的不足，通过分布式距离竞争加快了分组过程，提高了算法的可扩展性，同时保持了分簇的均匀性与稳定性，并结合通信代价估计改进了簇首选择策略，减少了簇内传输能耗。实验表明，AGCH算法能有效均衡网络负载到各节点，从而延长了网络的稳定期。

参考文献:

[1] AKYILDIZ I F, SU WEILIAN, SANKARASUBRAMANIAM Y, et al. A Survey on sensor networks ［J］. IEEE Communications Magazine, 2002, 40（8）: 102-114.

［2］ 沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报,2006,17（7）:1588-1600.

［3］ 陈闻杰，陈迅，高丽强,等.无线传感器网络成簇算法研究［J］.小型微型计算机系统,2008,29（2）:219-225.

［4］ HEINZELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor network ［C］// Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Washington, DC: IEEE Computer Society, 2000: 3005-3014.

［5］ WANG Y J, LIAW J J. The group clustering algorithm for LEACH ［C］// NSSSE 2008: 2008 National Symposium on System Science and Engineering Conference. Ilan, Taiwan, China: ［s.n.］, 2008: 0447.

［6］ 王B，曹涌涛，糜正琨.一种无线传感器网络异构分簇模型的簇头调度方案［J］.南京邮电大学学报:自然科学版,2008,28（2）:47-52.

［7］ 李成法，陈贵海，叶懋,等.一种基于非均匀分簇的无线传感器网络路由协议［J］.计算机学报,2007,30（1）:27-36.

［8］ 马玉刚，周群彪.基于LEACH的无线传感器网络节能算法［J］.计算机应用,2009,29（6）:1514-1516.

［9］ 乔俊峰，刘三阳，曹祥宇.无线传感器网络中基于节点密度的簇算法［J］.计算机科学,2009,36（12）:46-49.

［10］ 王青正，王晓婷，郭拯危，等.一种能量有效的WSN分簇路由算法［J］.计算机工程,2010,36（15）:120-122.

［11］ 秦华标，肖志勇.一种负载均衡的分簇路由协议［J］.小型微型计算机系统,2010,31（2）:225-229.