基于能量的EBAPC分簇网络拓扑控制算法_崔可想

第38卷第23期Vol.38 No.23·网络与通信·

计算机工程Computer Engineering

文章编号：1000—3428(2012)23—0104—05

文献标识码：A

2012年12月December2012

中图分类号：TP393

基于能量的EBAPC分簇网络拓扑控制算法

崔可想1,2，李志华1,3

(1.江南大学物联网工程学院轻工过程先进控制教育部重点实验室，江苏无锡214122；

2.无锡华御信息技术有限公司，江苏无锡214122；3.物联网应用技术教育部工程研究中心，江苏无锡214122)

摘要：低功耗自适应集簇分层型协议LEACH算法对簇头的选择具有随机性，并且没有综合考虑节点的剩余能量、分布位置。为此，提出一种基于能量的仿射传播聚类EBAPC分簇拓扑控制算法。对适应度因子重新进行定义，借鉴仿射传播AP聚类算法中聚类中心的选择策略，簇头选择综合考虑无线传感器网络节点的剩余能量和节点之间的距离因素。仿真实验结果表明，EBAPC算法较LEACH算法分簇更均匀，簇头选择更合理，网络中能量的消耗更均衡，从而延长网络寿命。

关键词：无线传感器网络；分簇拓扑控制；分簇；LEACH算法；EBAPC算法；适应度因子

Clustering Network TopologyControlAlgorithmfor EBAPC

Based onEnergy

CUI Ke-xiang1,2,LI Zhi-hua1,3

(1.Key Laboratory of Advanced Process Control for Light Industry ofMinistry of Education,

School ofInternet of ThingsEngineering, Jiangnan University,Wuxi 214122, China;

2.Wuxi Cinsec Information Technology Co., Ltd., Wuxi 214122, China;

3.Engineering Research Center ofInternet of Things Technology Application ofMinistry of Education,Wuxi 214122, China)

【Abstract】Aiming at thedisadvantages ofLow Energy Adaptive Clustering Hierarchy(LEACH)algorithm that cluster head selection is random,without considering the residual energy and the location of node, this paper proposes analgorithm calledEnergy-basedAffinity PropagationClustering(EBAPC)topology control algorithm, which is based on energy affinity propagation clustering. InEBAPC algorithm, a new definitioncalled fitnessfactor is presented, and the cluster center selection strategy inaffinity propagationclustering algorithm is borrowed.Experimentalresults show thatin EBAPC algorithm,thecluster head selection isbetter reasonable, and extends the network lifetimecompared withLEACHalgorithm.

【Key words】Wireless Sensor Network(WSN);clusteringtopology control;clustering;LEACHalgorithm;EBAPCalgorithm;fitnessfactorDOI:10.3969/j.issn.1000-3428.2012.23.025

1概述

无线传感器网络(Wireless Sensor Network,WSN)拓扑

素，这种情况容易造成簇头分布不均匀，局部节点能耗过大，从而造成一些重要的节点因为能量原因而过早死亡，严重影响网络的生存时间。文献[2]对LEACH算法进行了改进，提出了LEACH-C(LEACH-Centralized)算法。该算法克服了LEACH算法中通过随机方式决定节点是否当选为簇头以及每轮产生的新簇头没有考虑簇头的数量和位置等因素，显著地提高了簇的生成质量。但是由于每个节点都需要周期性地向基站报告各自的能量、位置等信息，因此簇开销大。文献[3]在LEACH算法的基础上，提出了数据聚合的精确与近似(Data Aggregation-Exact andApproximate,DAEA)算法，算法的基本思想是：首先对整个网络分簇，选择簇头，然后在已经成为簇头的节点中选出第2层簇头，最后的数据由第2层簇头再转发给基站，

控制是研究传感器节点能量分配策略、网络路由协议、智能节点布局的基础，也是决定网络生存时间的重要因素之一。低功耗自适应集簇分层型(Low Energy AdaptiveClustering Hierarchy, LEACH)协议[1]是最具有代表性的、以分簇为基础的层次型拓扑控制算法。LEACH算法将网络节点划分成“簇”，簇中各节点独立地按照随机概率决定自己是否充当簇头，并通过周期性的簇头选择和网络自组织过程避免簇头节点能耗过多问题，平衡网络负载，节约节点间通信的能量消耗，延长网络生存周期。但是LEACH算法也存在着一些不足，如对簇头的选择具有随机性，并且没有综合考虑节点的剩余能量、分布位置等因

————————————

基金项目：中央高校基本科研业务费专项基金资助项目(JUSRP211A41)

作者简介：崔可想(1985－)，男，硕士研究生，主研方向：嵌入式系统开发，无线传感器网络；李志华，副教授、博士收稿日期：2012-02-13

修回日期：2012-04-12

E-mail：wxxkc2010@http://wendang.chazidian.com

第38卷第23期崔可想，李志华：基于能量的EBAPC分簇网络拓扑控制算法105

这一实现路线有效地解决了LEACH算法在簇头选择方面的不足，但算法的实现比较复杂，数据在传输过程中存在不必要的时间延迟，降低了整个网络的性能。

本文通过引进适应度因子的新定义，通过适应度因子来确定节点在多大程度上适合做网络簇头。适应度因子综合考虑了节点的剩余能量和节点之间的距离等因素，因为节点之间的距离是引起网络传输延迟的主要因素之一，同时在计算适应度因子时，融合了仿射传播(AffinityPropagation, AP)算法中责任性、可用性在数据样本中传播的重要思想，通过分别对责任性、可用性累加求和，选取“和”最大的数据样本作为聚类中心。因为满足相关条件的聚类中心就相当于网络拓扑控制中的簇头，所以两者之间本身就具有类同性。这样，本文针对LEACH算法中簇头选择不合理、分布不均匀、选择簇头时没有综合考虑节点本身的剩余能量、节点与节点之间的距离等因素的问题，提出了基于能量的仿射传播聚类(Energy-basedAffinity Propagation Clustering, EBAPC)算法。EBAPC算法在选择簇头时，综合考虑了每一个非死亡节点的剩余能量，不仅考虑了簇头与簇内节点之间的距离，而且考虑了簇头与簇头之间的距离，所以，EBAPC算法能使簇内簇头的分布位置比较合理，较好地平衡簇内节点往簇头发送数据时的能量消耗。

[4]

r(i,k)和a?i,k?越大，说明样本点k作为最终聚类中心的可

能性越大。这样，通过每次的迭代循环进行消息的传递，不断更新样本点的责任性和可用性，最终形成高质量的聚类中心[4,8]。

AP算法最显著的特点是能给出比较准确的聚类结果，且运算速度快。AP算法中满足相关条件的聚类中心就相当于网络拓扑控制中的簇头，所以，两者之间本身就具有类同性。

3基于能量的分簇网络拓扑控制方法

本文借鉴AP算法对样本点进行聚类的策略思想，对

传感网络节点中的簇头进行选择，同时，在簇头选择时，综合考虑了簇内节点与本簇簇头之间、簇头与簇头之间的距离和各个节点的剩余能量。

文献[9]在LEACH算法中引入了新的无线通信能量传播损耗模型，如式(1)所示，是发射lbit数据所消耗的能量，由发射电路损耗和功率放大损耗两部分构成，功率放大损耗则根据发送者和接收者之间的距离分别采用自由空间模型和多路径衰减模型：εεddd

?lEelec?lfs?

???lEelec?lamp

24

dd

ETX?l,d??ETX_elec?l??ETX_amp?l,d??

?≥

00

(1)

其中，Eelec为发射电路的损耗能量；εfs、εamp分别为自由空间传播模型和多径衰减模型功率放大所需要的能量；d0为Friss自由空间传播模型和多径衰减模型的临界距离，

在此取d0?

2

2.1

LEACH算法和AP算法简介

LEACH算法

LEACH[1,5-7]算法是一种自适应分簇拓扑控制算法，以

迭代方式进行，每轮迭代都分为簇的建立、数据通信2个阶段。其基本工作过程是，开始时相邻节点动态地形成簇，随机产生簇头；然后簇内节点把数据发送给簇头，由簇头进行数据转发并把结果发送给汇聚节点[1,5-7]。簇头的主要作用是融合数据以及与汇聚节点通信，能量消耗比较大。LEACH算法最显著的特点是能够保证各节点等概率地担任簇头，使网络中的节点相对均衡地消耗能量。2.2

AP算法

AP算法[4]是一个适宜大规模数据聚类的高效、无监督学习的算法，其主要思想是通过样本的责任性、可用性在数据样本中传播，并分别对责任性、可用性累加求和，选取“和”值最大的数据样本作为聚类中心。

AP算法以所用样本的相似度组成的样本相似性矩阵S?N?N?为基础，N为样本个数，其基本工作过程是，首先将数据的全部样本点都视为候选聚类中心；然后在循环迭代过程中，各样本点相互竞争最终的聚类中心[4,8]。处于聚类中心的样本点对于其他样本点的吸引力之和比较大，在竞争中胜出的可能性比较大；反之，处于边缘位置的样本点，其吸引度之和较小且胜出的可能性也较小。用r(i,k)表示点k对样本点i的责任性，即样本点k是否适合做样本点i的聚类中心，a?i,k?表示样本点i对样本点k的可用性，即表示样本点i是否选择样本点k作为聚类中心

[4,8]

，不难看出，当簇内所有节点到簇头

的距离越小时，簇内通信所消耗的能量也就越小。由于LEACH算法在选取簇头时具有随机性，并没有考虑节点的能量因素，而根据文献[9]的能量损耗模型可知，剩余能量越多的节点按理应该成为簇头节点，因此剩余能量可以成为选择簇头节点的一个重要指标。本文引进一个适应度因子的概念，用于帮助簇头节点的选择。

定义用FF?i,j?表示节点i和节点j之间的适应度因子，它表明节点j在多大程度上适合做节点i的簇头。适应度因子按式(2)计算：

???

FF(i,j)?????p

j_current

wheni?jwheni?j

(2)

其中，?xi,yi?为点i的坐标；?xj,yj?为点j的坐标；Ej_current为点j当前的剩余能量值；p为参考度，取FF?i,j?所组成矩阵的平均值；FF?i,j?的大小表示节点j对节点i吸引程度的大小，即节点j可作为节点i簇头的程度。为了找到合适的簇头，需要不断搜集相关证据，本文采用文献[4]中AP算法的责任性和可用性的和r?i,j??a(i,j)当作最终确定为簇头的证据，即r?i,j??a(i,j)越大，证据越强，节点j成为簇头的可能性越大，反之，则不能选作为簇头。

r?i,j?和a(i,j)的迭代过程如式(3)、式(4)所示：

。

106

r?i,k??FF?i,k??max?a?i,k???FF?i,k???

计算机工程2012年12月5日

(Sink节点)，完成1个簇周期。

(3)

Step7当前循环轮数i?i?1。

EBAPC算法是在LEACH算法基础上的改进。由于算法在簇头选择时综合考虑了簇内节点与簇头之间的距离和节点的剩余能量，因此簇内簇头的分布位置比较合理，较好地平衡了簇内节点发送数据的能量消耗，而且能使能量大的节点有更大的概率成为簇头，使每个节点的能耗趋于均衡。另外，随着节点充当簇头次数的增加，节点真正能成为簇头的概率变小，起到保存能量的作用，从而延长网络的生存期。

在EBAPC算法中，Step1初始化节点的能量，时间复杂度为O?n?；Step3构建FF?i,j?组成的矩阵，时间复杂

?k???1,2,?,N,但k??k??

a?i,k??min0,r?k,k????0,r?i?,k??

i?

??

(4)

在此r?i,k?和a?i,k?被赋予了新的含义，r?i,k?表示节点i和节点k之间的责任性，视节点k为潜在的簇头节点，则责任性从节点i发送给节点k，责任性是指节点k作为节点i的簇头的累积证据。a?i,k?表示节点i和节点k之间的可用性，它由节点k发送给节点i。在根据式(3)更新r?i,k?后，再更新a?i,k?，可用性反映节点i选择节点k作为簇头的累积证据，即经过多轮循环后k最终能否成为真正的簇头。

而新证据分别按式(5)、式(6)更新：

(5)?i,k???1???r(i,k)??r?i,k?

(6)anew?i,k???1???a?i,k???aold?i,k?

其中，?是r?i,k?和a?i,k?迭代的阻尼因子，调整?可以

r

new

old

?i???1,2,?,N,但i??i且i??k??

度为O?n2?，初始化r?i,j?和a(i,j)时间复杂度为O?n2?；在Step5中，更新证据矩阵要迭代IterMax次，时间复杂度为O?n2?；在Step7中，簇头判断时间复杂度为O?n2?，点数目，同LEACH算法的时间复杂度O?n?相比[6]，时间复杂度增加了；EBAPC算法的空间复杂度与LEACH算法相当。

因此，EBAPC算法的时间复杂度为O?n2?，其中，n为节

1之间，?越大，迭代改变迭代的快慢。?一般取值在0～

越慢，?越小，迭代越快。

责任性和可用性在传感网络节点之间传递，直到达到规定的迭代次数或能量消耗殆尽。迭代过程结束后，对于

节点i，选取a?i,k??r?i,k?值最大的k，如果i?k，则i为簇头，如果i?k，则k是i的簇头。可把上述过程概括为如下EBAPC拓扑控制算法：

Step1随机生成100个传感器节点，初始化节点的初始能量E0和最大循环轮数rmax等参数，每个节点把自己的位置发送给基站，基站保存每个节点的位置信息。

Step2在当前循环轮数i?rmax时，每个节点把自己当前状态下的能量发送给基站。然后基站利用收集到的信息，根据以下步骤开始进行簇头的选择以及非簇头节点分配到相应的簇头节点的判断。

Step3根据式(2)计算适应度因子FF?i,j?，设置参数p和阻尼系数λ等。初始化r?i,j?和a(i,j)，设置最大迭代次数IterMax为100。

Step4在当前迭代次数Iter?IterMax时，根据式(3)和式(5)更新r?i,j?，根据式(4)和式(6)更新a(i,j)。

Step5当前迭代次数Iter?Iter?1。

Step6对于每个节点i，求使得max?a?i,k??r?i,k??的节点k，如果i?k，则i为簇头，如果i?k，则k是i的簇头。一旦所有簇头节点选择完毕及所有非簇头节点被分配到相应的簇头节点后，基站广播一个消息，其中包含每个节点的簇头ID。簇的建立阶段结束，网络进入稳定的数据通信阶段。

EBAPC算法的执行是周期性的，一个周期也称为一“轮”，每一轮分为簇形成阶段和稳定的数据传输2个阶段。算法第1阶段完成簇的建立后，簇内节点将监测到的数据发送给簇头，簇头进行数据融合后将数据发送给基站

4仿真实验及分析

为了验证EBAPC分簇拓扑控制算法的整体性能、有

效性和实用性，本节从簇头在网络节点中的分布情况、网络总能量的消耗情况、网络节点存活率和网络的生存期4个方面评价EBAPC算法，并与LEACH算法作了比较。

本文采用的网络模型如下：传感器节点随机分布在一个正方形区域内；传感器节点具有全网唯一的id号，能量受限，节点静止；基站固定，能量不受限制；在MatlabR2009环境下进行仿真，仿真场景设置的主要参数如表1所示，节点的初始拓扑分布如图1所示。

表 1

参数类型节点分布区域基站位置节点总数

传感器节点的初始能量E0电子发射消耗能量ETX电子接收消耗能量ERX

数据包长度控制包长度信号放大器能耗εfs信号放大器能耗εamp数据融合能量消耗数据融合率总轮数节点成为簇头的概率

阻尼系数λ

仿真场景参数设置

参数值100 m×100 m

中央1000.3J50nJ/bit50nJ/bit2000bit32bit100pJ/bit/m20.0013pJ/bit/m45nJ/bit/signal

0.610000.050.9

为聚类中心。 AP 算法以所用样本的相似度组成的样本相似性矩阵 S ? N ? N ? 为基础， N 为样本个数，其基本工作过程是，首 先将数据的全部样本点都视为候选聚类中心；然后在循环 迭代过程中， 各样本点相互竞争最终的聚类中心 [4,8]。处于 聚类中心的样本点对于其他样本点的吸引力之和比较大， 在竞争中胜出的可能性比较大；反之，处于边缘位置的样 本点， 其吸引度之和较小且胜出的可能性也较小。 用 r (i,k ) 表示点 k 对样本点 i 的责任性，即样本点 k 是否适合做样 本点 i 的聚类中心， a ? i,k ? 表示样本点 i 对样本点 k 的可用 性，即表示样本点 i 是否选择样本点 k 作为聚类中心 [4,8]。 ，不难看出，当簇内所有节点到簇头 的距离越小时，簇内通信所消耗的能量也就越小。由于 LEACH 算法在选取簇头时具有随机性，并没有考虑节点 的能量因素，而根据文献 [9]的能量损耗模型可知，剩余能 量越多的节点按理应该成为簇头节点，因此剩余能量可以 成为选择簇头节点的一个重要指标。本文引进一个适应度 因子的概念，用于帮助簇头节点的选择。 定义 用 FF ? i, j ? 表示节点 i 和节点 j 之间的适应度因 子，它表明节点 j 在多大程度上适合做节点 i 的簇头。适 应度因子按式 (2)计算： ? ? ? FF (i, j ) ? ?? ? ? ?p ?x ? x ? ?? y ? y ? 2 i j i j 2 E j_current when i ? j when i ? j (2) 其中，? xi , yi ? 为点 i 的坐标；? x j , y j ? 为点 j 的坐标；E j_current 为点 j 当前的剩余能量值； p 为参考度，取 FF ? i, j ? 所组 成矩阵的平均值； FF ? i, j ? 的大小表示节点 j 对节点 i 吸引 程度的大小，即节点 j 可作为节点 i 簇头的程度。为了找 到合适的簇头，需要不断搜集相关证据，本文采用文献 [4] 中 AP 算法的责任性和可用性的和 r ? i, j ? ? a(i, j ) 当作最终 确定为簇头的证据，即 r ? i, j ? ? a(i, j ) 越大，证据越强，节 点 j 成为簇头的可能性越大，反之，则不能选作为簇头。 r ? i, j ? 和 a(i, j ) 的迭代过程如式 (3) 、式 (4)所示： 106 r ? i, k ? ? FF ? i, k ? ? max ?a ? i, k ? ? ? FF ? i , k ? ?? 计 算 机 工 程 2012 年 12 月 5 日 ? k ? ? ?1, 2,?, N , 但k ? ? k?? (Sink 节点 )，完成 1 个簇周期。 (3) Step7 当前循环轮数 i ? i ? 1 。 EBAPC 算法是在 LEACH 算法基础上的改进。 由于算 法在簇头选择时综合考虑了簇内节点与簇头之间的距离 和节点的剩余能量，因此簇内簇头的分布位置比较合理， 较好地平衡了簇内节点发送数据的能量消耗，而且能使能 量大的节点有更大的概率成为簇头，使每个节点的能耗趋 于均衡。

108计算机工程

参考文献

[1]孙利民,李建中,陈

清华大学出版社,2005.

2012年12月5日

开始死亡到节点全部死亡，EBAPC算法的每轮平均死亡节点数目较少，节点存活率明显高于LEACH算法，可见，EBAPC算法同LEACH算法相比延长了网络的寿命。这是因为EBAPC算法在簇头选择时，节点的剩余能量能使能量大的节点有更大的概率成为簇头，能量较小的节点因为避免了成为簇头的可能，从而节省能量，较大地减缓了死亡速度，所以，在同样的初始能量下，循环次数增加了，网络的存活周期得到明显延长。

渝,等.无线传感器网络[M].北京:

[2]Heinzelman W,Chandrakasan A,Balakrishnan H.AnApplication-specific Protocol Architecture for2002, 1(4):660-670.

[3]AI-KarakiJN, UI-MustafaR,KamalAE.DataAggregation in

Wireless Sensor Networks——Exactand Approximate Algorithms,High Performance Switchingand Routing[C]//Proc. ofHPSR’04.Cambridge, UK: Cambridge University Press,2004:241-245.[4]Frey B J, Dueck D.Clustering byPassing Messages Between Data

Points[J].Science,2007,315(5814):972-976.

[5]YanDongmei,Wang Jinkuan,LiuLi,et al.Topology Control

Algorithm Based on Overlapping Clustering[C]//Proc. of2010International Conference on Sensing and Control.[S. l.]: IEEEPress,2010:737-741.

[6]张伟华,李腊元.无线传感网络LEACH协议能耗均衡改进[J].

传感技术学报, 2008, 21(11):1918-1922.

[7]KatiyarV, ChandN, GautamGC,et al.Improvement inLEACH

Protocol forLarge-scaleWireless Sensor Networks[C]//Proc.ofIEEE International Conference on Emerging Trends in Electricaland Computer Technology.[S. l.]: IEEE Press,2011:1070-1075.[8]董[9]刘

俊,王锁萍,熊范纶.可变相似性度量的近邻传播聚类[J].志,裘正定.基于分环多跳的无线传感器网络分簇路由算电子与信息学报,2010,32(3):509-514.法[J].通信学报,2008,29(3):104-112.

Wireless Microsensor

Networks[J].IEEE Transactions on Wireless Communications,

5结束语

本文分析了LEACH算法的特点和不足，针对LEACH

算法在分簇和簇头选择存在随机性、没有考虑节点的剩余能量及节点之间的距离因素而导致能量消耗较多的问题，提出了基于能量的EBAPC分簇网络拓扑控制方法，EBAPC算法在选择簇头节点时，充分考虑了节点的剩余能量及节点与簇头之间的距离等因素，使网络中剩余能量较多的节点有更大的机会成为簇头，从而有效地避免了LEACH算法对簇头的选择随机性强从而导致功耗过多的问题，使得簇头更加均匀地分布在规定的区域内。

通过实验仿真，从簇头在网络节点中的分布情况、网络总能量的消耗情况和网络节点存活率3个方面对LEACH和EBAPC进行比较，结果表明：在时间复杂度没有提高的同时，EBAPC方法较LEACH有效地延长了网络寿命并提高了网络能量的利用率。EBAPC方法在分簇的初始阶段，需要进行比较多的迭代，消耗部分能量和算法执行时间，这是下一步的研究重点。

编辑张正兴

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(上接第103页)

参考文献

[1]Haykin

S.

Cognitive Radio: Brain-empowered Wireless

IEEE Journal on Selected Areas in

Communications[J].

with Application to Cognitive Radio[J]. IEEE Transactions onWireless Communications, 2009, 8(12): 5996-6007.

[8]KushwahaH, XingYiping, ChandramouliR,et al.Reliable

Multimedia Transmission over Cognitive Radio Networks UsingFountain Codes[J]. Proceedings oftheIEEE, 2008, 96(1): 155-165.[9]YueGuosen, WangXiaodong.Efficient ARQ Protocols with Anti-jamming Coding for Cognitive Radios[J]. Wireless Communica-tions and Mobile Computing, 2009, 9(11): 1472-1486.

[10]YueGuosen, WangXiaodong.Design of Efficient ARQ Schemes

with Anti-jamming Coding for Cognitive Radios[C]//Proc. of 2009IEEE Wireless Communications and Networking Conference.Budapest, Hungary: [s. n.],2009: 1-6.

[11]许晓荣.新一代无线网络中多载波调制与资源分配若干关键技

术研究[D].南京:南京邮电大学, 2010: 100-105.

[12]XuXiaorong, Zheng Baoyu, Zhang Jianwu, et al. AnEfficient

Anti-jamming Piecewise Coding inCognitive OFDM[C]//Proc. ofthe 12th International Conference on Communication Technology.Nanjing, China, [s. n.], 2010: 1-4.

Communications, 2005, 23(2): 201-220.

[2]Fette B A.认知无线电技术[M].赵知劲,郑仕链,尚俊娜,译.

北京:科学出版社, 2008.

[3]YueGuosen, WangXiaodong,MadihianM. Design of Anti-jamming Coding for Cognitive Radio[C]//Proc. of 2007 IEEEGlobal Communications Conference.Washington D.C., USA:IEEE Press,2007: 4190-4194.

[4]YueGuosen.Anti-jamming Coding Techniques[J]. IEEE Signal

Processing Magazine, 2008, 25(6): 35-45.

[5]PlankJ S, BuchsbaumA L,Collins R L, et al.Small Parity-check

Erasure Codes——Exploration and Observations[C]//Proc. ofIEEE International Conference on Dependable Systems andNetworks.Yokohama, Japan: [s. n.],2005: 326-335.

[6]郭彩丽,冯春燕,曾志民.认知无线电网络技术及应用[M].

北京:电子工业出版社, 2010.

[7]YueGuosen, WangXiaodong.Anti-jamming Coding Techniques

编辑张正兴