基于粒子群优化的非均匀分簇路由算法

文章编号:1001-9081(2012)01-0131-03 doi:10.3724/SP.J.1087.2012.00131

摘 要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与LEACH算法和EEUC算法相比，所提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。

关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化算法；能量消耗；生存期

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

Abstract: To deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of Wireless Sensor Network (WSN), the paper designed an uneven clustering routing algorithm based on adaptive Particle Swarm Optimization (PSO). Firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. Then this paper introduced the PSO according to the cluster size. The PSO was used to select the final cluster heads by evaluating factors such as residual energy of nodes and distance between nodes. The cluster heads with more residual energy were chosen as the next hop to form multi-top route in which the sink node is the root. The simulation results show that compared with other two similar algorithms, LEACH and EUCC, the proposed algorithm extends 34% and 16% of survival time of network separately, reduces 22% and 12% of average energy consumption respectively, and effectively decreases the network nodes energy consumption.

Key words: Wireless Sensor Network (WSN); uneven clustering routing algorithm; Particle Swarm Optimization (PSO) algorithm; energy consumption; survival time

0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由部署在监测区域内的大量微型传感器节点形成的一种自组织网络［1］。由于传感节点通过自带电池供电且难以更新，因此，设计出一种能够高效地利用节点的能量且延长网络生存期的路由算法成为无线传感器网络路由研究的首要目标［2-3］。

经典的低能量自适应分簇路由算法(Low-Energy Adaptive Clustering Hierarch, LEACH)［4］每个周期由分簇和数据传输两个阶段构成，但是簇头以随机概率选取且簇头与汇聚节点单跳通信，容易造成簇头能量耗尽过早死亡。文献［5-7］引入了粒子群优化（Particle Swarm Optimization, PSO）算法优化簇头选举，但簇头与汇聚节点单跳通信的方式仍然会造成簇头节点能量的快速消耗。文献［8-10］在簇头与汇聚节点之间采取多跳的通信方式，有利于节约簇头能量。但是，崔莉等［11］认为距离汇聚节点较近的簇头须转发大量其他簇头发送的数据而消耗过多能量，形成“热区”。针对文献［11］的问题，李成法等提出了非均匀分簇(Energy-Efficient Uneven Clustering, EEUC)算法［12］，构造不同规模的簇来改善多跳路由的“热区”问题。但是当簇规模较大时，簇头选取不当更容易造成距离其较远的簇成员节点能量快速地消耗。

针对这些算法存在的不足，本文提出了一种自适应粒子群优化的非均匀分簇路由算法，用以缓解“热区”问题并延长簇内节点的生存期。采用与EEUC算法相同的成簇方案，不同的是本文根据节点与簇头的距离来判断簇规模大小，并在规模较大的簇中使用自适应粒子群优化算法重新选举簇头，当最终簇头选取完成后，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。

1 PSO算法

PSO算法是通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。假设在D维搜索空间中，群体规模为n，群体中每个粒子i（1≤i≤n）有如下属性：在D维空间，第t步迭代时的位置表示为向量xi(t)=(xi1,xi2,…,xid)，飞行速度为vi(t)=(vi1,vi2,…,vid)。粒子i经历过的最好位置为pi=(pi1,pi2,…,pid)，在整个群体中，所有粒子经历的最好位置为pg=(pg1,pg2,…,pgd)。每个粒子根据式(1)和式(2)来更新自身的位置和速度：

xid(t)=xid(t－1)+vid(t)(1)

vid(t)=wvid(t－1)+c1r1(pid－xid(t－1))+c2r2(pgd－xid(t－1))(2)

其中：w为惯性权重；c1和c2为学习因子；r1和r2为区间［0,1］内的随机数。

2 基于PSO的非均匀分簇算法

为了延长簇内节点的生存期并缓解由于簇头转发大量数据而消耗过多能量形成的“热区”问题，本文提出了一种基于PSO的非均匀分簇路由算法。本算法包括三个阶段，分别为解决“热区”问题的非均匀分簇阶段、减少簇内节点能量消耗的PSO优化簇头选取阶段及多跳通信阶段。

2.1 非均匀分簇阶段

为了构造不同规模的簇，首先需要选出候选节点并计算其竞争半径。在网络初始化时，每个传感节点生成一个随机数μ(0

Rc=(1－cdmax－d(Si,DS)dmax－dmin)R0c(3)

其中:c为控制Rc取值范围的参数，且c∈［0,1］；dmax和dmin分别表示全网节点到汇聚节点距离的最大值和最小值；d(Si,DS)表示候选节点Si到汇聚节点的距离；R0c为竞争半径的最大值。候选节点Si以R0c为半径广播消息，消息的主要内容为节点ID，竞争半径Rc以及自身当前的剩余能量。每个候选节点根据收到的广播消息，构建其邻候选节点集SCH。若候选节点Si的邻候选节点集表示为Si•SCH，则Si•SCH={SjSj为候选节点，且d(Si,Sj)

2.2 PSO优化簇头选取阶段

非均匀分簇阶段完毕后，根据簇规模引入自适应PSO算法选取最终簇头以减少算法复杂度。设定一个阈值k，当簇半径大于k时，将PSO应用到簇内选取最终簇头。为了使PSO适合本问题域，需对原PSO算法的式(1)和(2)进行改进，并给出一个合适的适值函数fit(x)。

假设n个网络节点处于平面坐标内，节点i位置xid(t)由x和y分量决定：

xxid(t)=xxid(t－1)+vxid(t)(4)

xyid(t)=xyid(t－1)+vyid(t)(5)

同理，速度也由x和y分量决定：

vxid(t)=wvxid(t－1)+c1r1(pid－xxid(t－1))+c2r2(pgd－xxid(t－1))(6)

vyid(t)=wvyid(t－1)+c1r1(pid－xyid(t－1))+c2r2(pgd－xyid(t－1))(7)

网络节点的分布是离散的，由式(4)和(5)得出的位置与实际节点位置不能一一对应，因此求出的节点位置需要进行调整，使得xxid(t)∈{px1,px2,…,pxn}，xyid(t)∈{py1,py2,…,pyn}，其中pxi和pyi为簇内节点位置的x和y分量。

设Δpxi为xxid(t)与i节点x分量差的绝对值，Δpyi为xyid(t)与i节点y分量差的绝对值，即：

Δpxi=xxid(t)－pxi(8)

Δpyi=xyid(t)－pyi(9)

令

Δpi=(Δpxi)2+(Δpyi)2(10)

Δpk=min(Δp1,Δp2,…,Δpn)(11)

则可得出k节点的位置与xid(t)最接近，因此对vxid(t)和vyid(t)进行调整，即：

xxid(t)≈pxk(12)

xyid(t)≈pyk(13)

在粒子群优化算法应用到本问题域的情况下，适值函数设定是否理想直接决定着选取出的最终簇头的优劣。由于簇头的选取需要考虑自身剩余能量的多少和周围节点的能量情况以避免剩余能量较少的节点距离簇头较远，因此适值函数可构造为：

fit(x)=αEx+βE(14)

其中：α和β分别为节点能量影响因子和周围节点能量影响因子，α, β∈［0,1］且α+β=1；Ex为x节点的剩余能量；E为其他节点的等效平均剩余能量，其计算公式如式(15)所示：

E=1n－1∑ni=1,i≠xEi(15)

其中Ei为第i个节点的等效剩余能量。Ei的确定综合考虑了节点i的剩余能量ei和到节点x的距离di。根据文献［2］的无线通信能量消耗模型中节点发射l比特的数据到距离为d的位置消耗的能量计算公式可以得知，距离d对于能量消耗的影响较大，从而可构造：

Ei=ei/d2i(16)

因此得出的适值函数为：

fit(x)=αEx+β1n－1∑ni=1,i≠xeid2i(17)

在簇内应用PSO优化簇头选取的具体步骤如下。

1)初始化粒子群的规模为n，n为簇内节点个数。

2)初始化每个粒子i：

①初始化粒子i的xxid(t)和xyid(t)，并按式(8)~(13)对粒子位置进行调整；

②初始化粒子i的vxid(t)和vyid(t)；

③利用式(17)计算出适值fiti(x)；

④令pgd为最大适值fitmax(x)，pid为fiti(x)。

3)重复执行下列操作直到达到最大迭代次数：

①利用式(4)~(7)更新每个粒子i的xxid(t)和xyid(t)以及vxid(t)和vyid(t)，并按式(8)~(13)调整粒子位置；

②利用式(17)计算各个粒子i的适值fiti(x)；

③设pgd=fitmax(x)，pid=fiti(x)。

4)当达到最大迭代次数时，选取适值fit(x)最大的节点作为最终簇头。最终簇头向簇内节点消息，实现簇头对簇内节点数据的收集和融合。

2.3 多跳通信阶段

簇头融合簇内节点的数据后，将数据直接或者通过中继簇头发送给汇聚节点。本文假设中继簇头接受其他簇的数据时，不同簇的数据不能进一步融合，因此转发其他簇头信息即可。其多跳通信过程如图1所示，其中A~H为簇头。

为了进一步减少簇头节点的能量开销，引入阈值L，当簇头与汇聚节点间的距离小于L时，则直接把数据传输给汇聚节点；当簇头与汇聚节点间的距离大于或等于L时，则选择剩余能量较多的簇头作为下一跳，以多跳通信的方式将数据转发给汇聚节点。

3 实验结果及分析

为了对本文算法的可用性和有效性进行评估，引入经典的LEACH算法和多跳路由表现较优的EEUC算法，与本文算法进行对比。采用通用的无线通信能量消耗模型，并利用Matlab平台进行仿真实验，以节点的平均能量消耗和网络生存期作为评价标准。仿真实验区域及所用参数如表1所示。

在仿真过程中，运行100次取计算所得的平均网络生存周期和平均能量消耗来进行比较，仿真结果如图2~3所示。

从图2可以得出，LEACH算法、EEUC算法与本文算法分别在423轮、712轮和965轮出现第一个节点死亡。本文算法分别延长了542轮和253轮，相对于实验总轮数（1600轮），分别延长了34%和16%。如何计算的，正文中未予以说明，请补充。LEACH算法和EEUC算法分别在1010轮和1413轮节点全部死亡，而本文算法在1600轮时节点仍有节点存活，这说明了本文算法更好地减少了节点的能量消耗。

从图3可以得出，1010轮时，相对于总能量，本文算法平均能量消耗分别减少了22%和12%。LEACH算法和EEUC算法的节点平均能量消耗都要比本文算法快，并较早出现全部节点死亡的情况。由以上实验结果分析可以得出，LEACH算法由于按随机概率选举簇头且采用单跳通信方式，导致簇头消耗过多能量而过早死亡；而EEUC算法在簇规模较大时，簇头选举不合理造成簇内节点过早死亡。本文算法使用非均匀分簇减少了簇头能量消耗，并在规模较大的簇内应用粒子群优化算法使簇头选举更为合理，减少了簇内节点能量消耗，延长了网络生存期。

4 结语

针对现有分簇路由算法的不足，本文提出了一种自适应粒子群优化的非均匀分簇路由算法。与其他同类算法相比，本算法较好地解决了“热区”问题和簇内节点过早死亡问题，有效地延长了网络的生存期。但是本文在数据通信阶段根据剩余能量选择下一跳簇头，容易造成部分簇头负载过重，因此，如何优化数据转发路径将作为下一步的研究方向。

参考文献:

[1]

任丰原,黄海宁,林闯.无线传感器网络［J］.软件学报,2003,14(7):1282-1291.

[2]

唐勇,周明天,张欣.无线传感器网络路由协议研究进展［J］.软件学报,2006,17(3):410-421.

[3]

孙利民,李建中,陈渝.无线传感器网络［M］.北京:清华大学出版社,2005.

[4]

HEINZELMAN W. Application-specific protocol architectures for wireless networks ［D］. Cambridge: Massachusetts Institute of Technology, 2000.

[5]

蒋畅江,石为人,向敏,等.基于PSO的无线传感器网络节能分簇协议［J］.计算机工程,2010,36(8):15-17.

[6]

苏炳均,李林.粒子群优化的无线传感器网络仿真研究［J］.计算机仿真,2010,27(9):150-152.

[7]

梁英,于海斌,曾鹏.应用PSO优化基于分簇的无线传感器网络路由协议［J］.控制与决策,2006,21(4):454-462.

[8]

刘庆,王培康.无线传感器网络的安全分簇路由协议［J］.计算机仿真,2009,26(4):167-171.

[9]

陆立芳,闫建国.无线传感器网络路由协议的优化设计［J］.计算机仿真,2010,27(12):125-128.

[10]

张文祥,马银花,郭继坤.无线传感器网络路由算法的研究［J］.计算机测量与控制,2009,17(3):617-619.

[11]

崔莉,鞠海玲,苗勇,等.无线传感器网络研究进展［J］.计算机研究与发展,2005,42(1):163-174.

[12]

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

收稿日期:2011-07-25;修回日期:2011-09-20。

基金项目:

湖南省自然科学基金资助项目（09JJ6094）；湖南省2011科技计划项目（2011FJ3082）。

作者简介:

邹杰（1986-），男，湖南长沙人，硕士研究生，主要研究方向：无线传感器网络； 史长琼（1968-），女，湖南衡阳人，副教授，博士研究生，CCF高级会员，主要研究方向：计算机网络、信息安全、人工智能； 姬文燕（1988-），女，河南洛阳人，硕士研究生，主要研究方向：无线传感器网络。