一种基于负载均衡的无线传感器网络节能分簇算法

1、一种基于负载均衡的无线传感器网络节能分簇算法姬宁,崔晓燕北京邮电大学自动化系,北京(100876E-mail:saysee2000摘要:由于无线传感器节点的能量是有限的,如何延长节点和网络的工作寿命成为一个很关键的问题。LEACH算法采用本地簇头随机轮转机制将能量负载分担给网络中的所有传感器节点,但是,簇头选举的随机性和簇内节点数目的不均衡可能导致某些节点过快耗尽能量而死亡。本文提出了一种基于负载均衡的簇头选举方案,采用粒子群优化(PSO算法先行分簇,然后考虑能量和距离再推举出簇头。仿真结果表明,该算法比LEACH更有效地平衡了能量消耗,并显著延长了网络的存活时间。关键词:传感器网络,粒子群优

2、化,负载均衡,分簇中图分类号:TN929.51. 引言无线传感器网络是由大量传感器节点通过无线通信技术自组织构成的网络,它可以广泛地应用于军事、工业控制、环境监测等诸多领域,尤其适合部署在环境恶劣和人员不易到达的场所。与传统网络不同,构成无线传感器网络的节点能量是有限的,且耗尽之后难以补充,所以,高效的利用节点能量,尽可能延长网络的存活时间成为网络协议设计的重要目标之一。研究表明,对于大规模的无线传感器网络,层次型分簇路由算法比平面路由算法具有更好的适应性和节能性1。近年来,研究人员提出了多种传感器网络的分簇算法7,其中比较典型的是W. Heinzelma等人提出的一种低功耗自适应分簇算法LE

3、ACH2。LEACH算法将各个节点进行分簇,每个簇中有一个簇头节点专门负责收集其成员的数据进行融合后发送给基站,由于簇头必须消耗更多的能量来进行数据的处理和转发,LEACH通过随机簇头轮转的方法使得各个节点轮流担任簇头的职责。尽管LEACH有效的节省了能量消耗,并充分考虑了数据的相关性,但是仍然存在一些不足:首先,它没有考虑到节点分布的拓扑结构,可能距离很近的两个节点同时成为簇头,这样,密集区域就被拆分为多个簇;其次,簇头选举的过程没有考虑节点的能量问题,可能能量较低的节点被选为簇头,会导致该节点过早的耗尽能量而死亡;第三,没有考虑节点之间的距离,这种情况下簇内的能量消耗并不是最优值。本文提出

4、了一种基于负载均衡的分簇算法,利用粒子群优化算法(PSO进行分簇,使得每个簇内包含的节点数目相同,然后充分考虑距离和能量的因素选举出簇头,该算法能够使各节点均衡地分担负载,并有效降低了系统的能量消耗。2. 问题描述在实际的网络环境中,节点并不是平均分布在整个区域的,随机簇头选举算法的结果可能导致各个簇的规模相差很大,这就意味着节点密集区域的簇头要承担更多的数据处理和转发任务,比稀疏节点区域的簇头能量消耗要大得多,也就有可能因能量耗尽而过早的死亡。出于均衡负载的考虑,我们希望能将整个区域划分成规模相等的若干个簇,每个簇内的节点数目相等。首先,我们作出以下假设:1 所有传感器节点随机分布在二维平面

5、上,节点的各项参数均相同且能量有限; 2 节点具有GPS 定位功能,能够获得自己的位置信息;3 节点控制器支持状态切换功能,当节点空闲时可以转入休眠状态以节省能量; 4 为了避免多跳通信产生的延时和过多的能耗,这里采用单跳通信方式,即簇头节点与基站之间直接通信。当区域划分确定之后,我们希望能找到一个最合适的节点作为簇头,使得簇内通信的能量消耗和簇头基站之间通信的能量消耗之和最小。本文采用文献2的通信模型。设两节点间距离为d ,短距离通信情况即两节点都在节点通信距离r 内的时候,能量消耗与2d 成正比。在节点通信距离r 以外的时候,能量消耗与4d 成正比。节点传送l bit 数据到与之距离为d

6、的另一个节点所消耗能量表示为:24,(,elec fs Tx elec mp lE l d d r E l d lE l d d r+<=+(1其中第一项lEelec 表示数据编码、调制解调等过程消耗的能量,第二项则根据通信距离远近选择对应的无线发送方式消耗的能量。节点接收l bit 长度数据所消耗能量为:(Rx elec E l lE =(23. 基于PSO 优化的分簇算法该算法分为两大步骤,首先是利用PSO 算法进行区域划分,将整个区域划分成若干个相同规模的簇;第二步是在已划分好的簇内根据节点的信息和能量选举出最合适的节点作为簇头节点。下面进行详细介绍。3.1应用PSO 算法进行分簇

7、文献4提出了一种使用粒子群优化算法(PSO 来解决异构无线传感器网络分簇问题的方案,本文基于同样原理针作了一些改动,解决了同构传感器网络均匀分簇的问题。假设共有N 个传感器节点,准备将整个网络划分为M 个簇,则每个簇包含的节点数目为N/M。首先,我们使用PSO 优化算法来确定一条区域分割线,使得分割线两端的区域包含了相等的节点数目。分割线以如下形式表示:(,P x y =(3其中,(x,y表示位于分割线上的点的横纵坐标,表示分割线与x 轴的夹角。 定义fitness 函数为如下形式:221122(Fitness c f N c f N =+(4其中,(1,2i c i =表示区域i 中的节点总

8、数,i f 由(5式决定,(1,2ii M f i M= (5其中,i M 表示区域i 期望的簇头节点数目,即希望通过分割使得该区域保留多少个簇头节点。显然,如果M 是偶数,当区域1和2包含的簇头节点数目相等时,121/2f f =。分簇算法描述:Step1:所有节点向基站发送ADV 报文,广播自己的位置信息和能量信息;Step2:基站收到节点的ADV 报文,开始定义Q 个粒子用来执行PSO 算法进行分簇; Step3:为Q 个粒子的参数,x y 赋予随机选取的值,由(3式可以确定各自代表的分割线,他们将整个区域分割成Q x 2个不同的子区域。由于基站得到了各个节点的位置信息,可以确定它们是否

9、在某个区域内,也就可以得到相应的(1,2i c i =值;Step4:将(1,2i c i =代入(4式可以得到Q 个不同的fitness 值,比较这Q 个值和上次搜索得到的最小fitness ,取最小值对应的粒子作为全局极值gd p ;比较单个粒子在之前的搜索过程中得到的fitness 值取最小的作为个体极值id p ,然后通过下式更新,x y :xid xid xid yid yid yid id id idX X v X X v X X v =+=+=+(6其中,xid yid X X 表示粒子的位置,id X 表示分割线的倾角,xid v ,yid v ,id v 分别表示粒子在,x

10、y 三个维度上的搜索速度,它们由下列等式决定,121212*(*(*(*(*(*(xid xid id xid gd xid yid yid id yid gd yid id id id id gd id v wv c rand p X c rand p X v wv c rand p X c rand p X v wv c rand p X c rand p X =+=+=+(7其中,rand(是介于(0,1之间的随机数。1c ,2c 是学习因子,通常1c =2c =2。w 是权重因子,较大的权重因子使得粒子搜索新区域的力度更大,较小的权重因子使得粒子在当前区域进行细微的搜索。Step5:粒

11、子得到新的,x y 后,代入(3式转入Step3的搜索过程,直至满足fitness 值为0或者达到最大搜索次数时退出。理想情况下,当划分结果达到最优时,1122,c f N c f N =,(2式的值为0。也就是说,使得fitness 函数值近似为0的分割线将整个区域分割成两个规模相等的子区域。Step6:当第一条区域分割线确定后,转入Step2对两个子区域再次分割,直到M 个簇被划分完毕为止。3.2 基于能量和距离考虑的簇头选举算法文献5研究了通信模型为(1(2时,单个簇与基站通信总能量消耗最小的满足条件,即基站、簇头、簇的质心在同一直线上。假设基站位置为(0,0,理想簇头位置为(,CH C

12、H x y ,簇内节点的位置为(,i i x y ,簇内节点总数为n (包括簇头,则有下列等式:11(,(,nniii i CH CH xyx y nn=(8其中,满足下面关系:22113(1,2n ni i mp i i fs x y n n n =+= (9经过PSO 算法均匀分簇后,我们很容易得到簇内的节点数量,各节点的位置均可获得,由(6、(7两式可以计算出理想簇头节点的位置(,CH CH x y ,那么,距离该点最近的节点应该被选为簇头。但是,纯粹的依靠位置信息来选举簇头存在着很大的弊病,某些位置的节点被选举为簇头的次数会远远高于其他节点,而位置比较偏僻的节点几乎不可能成为簇头节点,

13、这就导致了一些节点很快死亡,与负载均衡的目标背道而驰。所以,我们需要考虑节点剩余能量的因素,能量越小的节点成为簇头的可能性应该越低3。假设节点i 的剩余能量为i E ,它与簇内总剩余能量的比值为1/ni i ii r E E=,设i d 为节点i 与理想簇头节点的距离,则i d = ,定义函数 1(,ir i i i T d r d e =(10(,i i T d r 最小时对应的节点i 将被选举为簇头。由上式可以看出,0i r 时T ,这就避免了节点因为距离理想簇头太近而被多次选举为簇头的情况。同时,T 与i d 成正比,各节点剩余能量相差不大时,距离理想簇头节点较近的节点成为簇头的几率更大

14、。当基站确定各个簇的区域范围和簇头的选举后,向节点广播INFO 报文,告知他们所属簇以及簇头ID 的信息,然后簇间通信开始,该过程与LEACH 相同,不再赘述。4. 仿真实验4.1仿真环境在仿真实验中,无线传感器网络由N=100个具有GPS 定位功能的节点构成,节点随机分布在(0,0至(100,100的方形区域内,基站的位置坐标是(0,0,每个节点的初始能量为2J 。这里采用(1(2式的通信模型,其中,发送和接收电路的功耗elec E = 50 nJ/bit ,无线覆盖半径r=25m ,fs =10pJ ,mp =0.0013pJ ,簇头与节点总数的比值取5%,即M=5。本文采用ns2网络仿真

15、平台6,PSO 算法中的相关参数值分别为:学习因子1c =2c =2,最大迭代次数MAXITER=100,权重因子w 初始值为0.9,随着迭代次数的增加随下式而变化,(0.4*(/0.4w w MAXITER iter MAXITER =+(11其中,iter 是当前的迭代次数。为了测试算法的性能,将该算法与LEACH 进行比较,并使用以下两种性能评价参数:1网络存活时间,从仿真开始到一定比例的节点死亡(存活节点数小于期望的簇头数为止所经过的时间;2每单位能耗基站接收到的数据量。4.2仿真结果与分析图1给出了使用PSO算法进行分簇的效果图,很明显,整个区域被分成了5个簇,每个簇内包含的节点数基

16、本相同,很好的满足了我们的预计目标。 图1 经过PSO算法得到的分簇结果图2给出了两种算法的网络存活时间比较,可以看出,本文提出的分簇算法比LEACH 具有更长的网络生存时间。由于LEACH没有考虑到节点能量和负载均衡的问题,导致了一些节点因过度消耗而很快死亡,而本文提出的算法则较好的平衡了各节点间的能耗,所以能有效的延长网络生存期。图3对两种算法的能耗效率做了比较,在耗能相同的情况下,本算法与LEACH相比能够传递更多的分组,这说明本算法具有更高的耗能效率。 图2 存活的节点数/轮图3 基站接收到的数据量/J5. 结论由于无线传感器网络节点能量有限的限制,如何在保障路由协议性能的前提下尽量减

17、少节点能耗成为该领域一个研究热点。针对LEACH算法的不足,本文提出了一种使用PSO优化的分簇算法,并充分考虑了节点能量和距离的因素,仿真结果表明,该算法能有效地平衡节点的能耗负载,明显延长了网络的生存时间,从而提高了基站接收的数据量,使网络具有更好的稳健性和更高的通信效率。 参考文献 1Heinzelman W, Chandrakasan A , Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networksC. Proceedings of the 33rd Annual H

18、awaii International Conference on System Sciences , Maui , HI , 2000 :1210 2Heinzelman W, Chandrakasan A, Balakrishnan H. An Application-specific Protocol Architecture for Wireless Microsensor Networks J. IEEE Transactions on Wireless Communications, 2002,1(4 :6602670. 3 Younis O, Fahmy S. HEED: A H

19、ybrid, Energy-efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks J. IEEE Trans on Mobile Computing, 2004, 3 (4 :660-669. 4Tillett J, Rao R, Sahin F. Cluster-head Identification in Ad Hoc Sensor Networks Using Particle Swarm OptimizationC. Personal Wireless Communications, 2002 IEE

20、E International Conference, 2002.201-205. 5 Gurpreet Singh, GaoXi Xiao. Algorithms for Energy-efficient Clustering in Wireless Sensor NetworksC. Communication systems, 2006 10th IEEE Singapore International Conference, Oct. 2006. 1-5. 6The network simulator - ns2. /nsnam/ns/ 7邱天爽等译.

21、 无线传感器网络协议与体系结构M. 电子工业出版社, 2007. A load-balanced energy efficient Clustering Algorithm for Wireless Sensor Networks Ji Ning，Cui Xiaoyan Department of Automation， Beijing University of Posts and Telecommunications，Beijing (100876 Abstract Nodes in Wireless sensor networks have very limited battery power, so its very significant to study how to prolong the network lifetime. In the LEACH protocol, the cluster heads are determined randomly each round. The distributed selection of cluster