基于模拟退火算法的无线传感网 PEGASIS算法.doc

基于模拟退火算法的无线传感网 PEGASIS算法 第7卷第4期xx年8月江南大学学报(自然科学版)Journa lof Jiangnan University(Na tural Science Edition)Vol.7No.4Aug.xx:1671-7147 (xx)04-0438-05:xx-09-10;修订日期:xx-10-20.基金项目:浙江省科技计划项目(xxC31001).作者简介:吴联芳(1985-),男,浙江温州人,电路与系统专业硕士研究生.3通讯联系人:金心宇(1958-),男,上海人,教授,硕士生导师.主要从事网络通信与智能仪器等研究.Email:jinxyzju.基于模拟退火算法的无线传感网PEGAS IS算法吴联芳,张昱,金心宇(浙江大学信息科学与工程学院,浙江杭州310027)3摘要:在PEGASIS算法基础上,采用模拟退火算法进行簇的形成,同时利用能量因素来选择每一轮的簇头.采用模拟退火算法后链路的长度平方与比原来采用贪婪算法的相比,降低了一半左右,从而减小了整个网络能量的消耗,大大延长了第1个节点的死亡时间.第1个节点的死亡时间为原算法的1.83倍以上,20%、50%和80%的节点死亡时间也都比原算法的要长,由此提高了整个网络的生存周期.关键词:无线传感器网络;路由协议;模拟退火算法;节能;生存周期:TP393:APEGAS ISA lgorithmin W SN Basedon Sim ulatedAnnea lingA lgorithmWUL ian2fang,ZHANG Yu,J INGXin2yu(College ofScience andEngineering,Zhejiang University,Hangzhou310027,China)3Abstract:In thispaper,based onPEGASIS algorithm,we useSA forcluster formationand selecteachhead clusterby meansof energyfactor.After usingsimulated annealing algorithm(SA),thetotal lengthof theroute isreduced byhalf paredwith thatusing greedyalgorithm.O therwisethedeath timeof the first node is greatlyextended.The death time for the firstnodeis1.8times oreventhree timesmore thanthat of the original algorithm,and thedeathtimeforthe20%,50%and80%nodes isalso longerthan theoriginalalgorithm,whereby improving thesurvival of the wholeworkof cycle.Key words:wireless sensor works;routing protocol;simulated annealingalgorithm(SA);energy saving;lifetime无线传感器网络节点的能量都是有限的,因此提高网络生存时间已成为一个重要的课题.无线传感器网络(W irelessSensor Network,W SN)是由成千上万的传感器节点遍布在大规模的地域而形成的,网络中各个节点能够协同进行实时监测、感知并采集网络分布区域内的各种环境或监测对象的信息,并对这些信息进行处理,进而获得详尽而准确的信息,然后传送给需要这些信息的用户.该传感器网络综合了传感器、嵌入式、分布式信息处理1.等技术和无线通信技术由于无线传感器网络中各节点仅携带能量有限的电池,故其生存时间有限,计算、通信等能力也有限.因此,必须设计合理的路由协议以尽可能合理地分配能量,以节约W SN的能量消耗,达到提高网络生存时间的目的.随着W SN的发展,国内外目前有许多路由协议被提了出来.从网络拓扑结构的角度考虑可大体把其分为2类:平面路由协议和分簇路由协议PEGASIS(Power2Efficient2.GA theringinSensorInformationSystems)就是一种典型的分簇路由协议,它的簇是1条基于地理位置的链,而在这条链的形成过程中采用了贪婪算法.贪婪算法虽可很快地找到近似最优解,但其只是一种局部优化算法,而且使得找寻到的链的路径较长,增加了数据传送所消耗的能量.同时,由于选择簇头时未考虑节点的能量分布状况,可能导致某些节点过早死亡,从而使网络状况和性能下降.文中主要针对这两方面的缺点提出了基于模拟退火算法的PEGASIS算法,以此来改进原有的PEGASIS算法.1PEGASIS算法1.1PEGAS IS算法的过程描述PEGASIS算法可以分成2个过程,一是链(即簇)的形成;二是在第1步构造链的基础上进行通信,在每一轮中,只选择1个节点为簇头负责与基站通信.PEGASIS成簇的基本思想是:假设所有节点都是静止的,根据节点的地理位置形成1条相邻节2.这类似于旅行商问题,是1个经典的NP问题.PEGASIS成簇采用贪婪算法,从距离基站最远的节点开始,通过定位装置或者通过发点间距离最短的链送能量递减的测试信号来发现距离自己最近的邻居节点,然后依此类推,直到访问完最后1个节点为止.在通信的过程中,当有节点死亡时,在所有活着的节点中再次通过相同方式来重新构造链.1.2PEGAS IS算法簇头的选择以及通信方式在每一轮通信中,PEGASIS算法采用轮流当选的方法.设共有N个节点,从第0个节点开始到第(N-1)个节点轮流当选为簇头,则在第i轮中,第i%N(%即取模)个节点当选为簇头.从链上看,簇头左边的节点和簇头右边的节点都向簇头发送数据.假设簇头在链上的位置为k,在簇头左边的链上,即(j0表示为当新解对应的目标函数较小时,接受新解;当新解对应的目标函数比原来大时,则以一定的概5,即若e前路径Si=Sj,其他情况时Si不变;7)算法结束温度:将算法结束温度设为1个常量,判断条件为:Ti0.01.2.2能量模型节点的能量消耗主要有3种,分别为发送数据i=0d2ij为Si到Sj距离的平方,由P=e,其中Ti为当前温度,P=1率接受新解(-f/Ti)random(0,1),则当消耗的能量、接收数据消耗的能量和数据融合所消耗的能量.在该算法中,当节点在链的端点,为普通节点时只需要发送数据1次;为簇头时,需要融合数据1次,接收数据1次,发送数据1次(发送给基站);当节点不在链的端点,为普通节点时需要融合数据1次,接收数据1次,发送数据1次,为簇头时,需要融合数据2次,接收数据2次,发送数据1次(发送给基站).文中传输数据所消耗的能量为ETx(k,d)=Eeleck+ampkd接收数据所消耗的能量为:ERx=Eeleck;数据融合所消耗的能量为:Ef(k)其中,k为传输数据比特数(单位bit),Eelec2=Efusionk.=50nJ/bit,amp=100pJ/bit/m2.d2为数据传输距离的平方,Efusion=5nJ/bit3.3仿真结果及讨论文中采用C+进行仿真,所有节点的位置都是固定不动的,且每个节点的初始能量皆相同,能量模型也相同.所传输的每1个数据包的大小k=2000bit3,基站的位置和这些节点的位置都处于同一个平面上.为了与原先PEGASIS算法更好地进行比较,文中分别对以下情形做了仿真:1)100m100m的范围里随机分布100个节点,基站位置坐标为(50,300),节点初始能量分别为0.25J,0.5J;2)50m50m的范围里随机分布100个节点,基站位置坐标为(25,150),节点初始能量分别为0.25J,0.5J;以在100m100m的范围里随机分布50个节点为例,产生的随机节点见图2.图2100100范围内随机产生50个节点分布F ig.2Position of50nodes in100100将这些节点分别按照贪婪算法和模拟退火算法形成链,模拟退火算法的参数设置见算法模型,用模拟退火算法产生链的目标函数值为10894.7916,而用贪婪算法求解的目标函数值为23169.5642,由此可见模拟退火算法产生的目标函数值的大小仅为贪婪算法求解生成的目标函数值的0.47左右.将这些节点信息用模拟退火算法计算30次,并求平均值,再与贪婪算法所求得的目标函数值相比较,结果见表1.表1贪婪算法和模拟退火算法各运行30次的结果比较Tab.1Com parison of theaverage resultwhen runningGreedy algorithm and SAeach for30ti m es目标函数值比较所用算法贪婪算法模拟退火算法最好23169.564210894.7916最差23169.564213562.6238平均23169.564211940.4917044江南大学学报(自然科学版)第7卷由表1可以看出,模拟退火算法算出路径平方的总和大小,仅为用贪婪算法求得的路径平方总和的50%左右,大大减小了数据传输所消耗的能量.用模拟退火算法产生的最优路径,用贪婪算法产生的最优路径见图3(b).其中,基站的位置坐标为(50,300),而贪婪算法的头节点选为距离基站最远的节点.从图3(a),(b)两图的比较中可以看出,贪婪算法作为1种局部最优算法,虽然能够很快地找到近似最优解,但是它并不能像模拟退火算法一样具有寻找全局最优的能力,因此形成链的长度要比采用模拟退火算法形成的链长度长得多.而且采用模拟退火算法不会形成1条特别长的路径,而贪婪算法则有这种可能.当区域中共有100个节点,节点初始能量为0.25J和0.5J的情况下,原算法和改进算法的生存轮数的比较见表2.图3100100范围内50个节点2种算法构造的链对比F ig.3Com parisonof theroute formed by using SAand greedyalgorithm,50nodes in100100表2总共有100个节点时,第 1、 20、 50、100个节点死亡时,2种算法的生存轮数对比Tab.2Com parisonofthelifeti me whenthefirst,20th,50th,100thnodes usingdifferent algorithm初始能量/J不同仿真情况算法节点位置/第N个120501000.25100100PEGASIS151613678761100个节点改进后算法6907087187375050PEGASIS5099279971025100个节点改进后算法10131018102310300.50100100PEGASIS307123813491460100个节点改进后算法14021423143614545050PEGASIS1018185319952050100个节点改进后算法2025203420432056以仿真情况为100100,节点个数为100,初始能量为0.5J的情况为例,用柱状图(见图4)比较2种算法的生存周期.图42种算法节点存活时间的比较Fig.4Com parisonof lifetimebyusingdifferent algorithm从表1和表2的数据对比以及图4的柱状图对比中可以发现,改进后算法中第1个节点的死亡时间大大推迟,而且由于每次均选取能量最多的节点作为簇头节点与基站通信,所以整体的节点生存时间也更为均衡.第1个节点的生存时间是原来算法的1.8倍以上,有些情况甚至还达到3倍以上,例如初始能量为0.5J,仿真情况为5050,50个节点的情况.另外,从2个表的数据对比中还可以发现,改进后算法的最后一个节点的生存时间通常比原算法略短,因为贪婪算法是一种寻找局部最优的算法,没有考虑到能量因素用于选择簇头.因此,可能会存在一些节点,其两边的节点距离它们很近,故消144第4期吴联芳等:基于模拟退火算法的无线传感网PEGASIS算法耗的能量会很少,从而这些节点的生存时间较长.衡量一个网络的性能,并不能以最后一个节点的生存时间来衡量.改进后的算法在前20%,50%和前80%节点的生存时间都比原算法要长.以图4为例,对于前面80个节点的生存时间而言,改进算法比原算法要略长一些,而剩余20个节点就难以完成监测任务,也难得以达到更好的网络指标.而在这个性能指标上,改进算法比原PEGASIS算法要好得多.从表3中的数据对比可以看出,当采用改进算法的第一个节点死亡时,而采用原PEGASIS算法已有50%70%的节点死亡.表3各种情况下改进算法第一个节点死亡时PEGAS IS算法的死亡节点数Tab.3Num berofthenodes die inPEGAS ISwhen thefirstnode dieuse thePEGASISbased onSA各种情况改进算法的节点死亡数PEGASIS算法的节点死亡数100100100个节点,初始能量为0.25J1595050100个节点,初始能量为0.25节点,初始能量为0.25J135505050个节点,初始能量为0.25J132两种算法的节点死亡时间对比仿真曲线见图5.由图5可以看出,在100100范围内,50个节点及初始能量为0.25J的情况下,前40个节点的死亡时间均长于PEGASIS算法,而后面20%的节点可能是由于PEGASIS算法中节点能量消耗不均匀,会使个别节点的生存时间较长.但是由于剩余节点过少,在实际应用中已无太大意义,由此更加证明了文中提出的改进PEGASIS算法中节点的能耗更为均衡.图5两种算法的节点死亡时间对比仿真曲线Fig.5The parisonoflifetim ecurves byusing twodifferentalgorithm4结语在无线传感器网络中,由于每个节点的能量均为有限,因此设计合适的路由协议使得节点的总体生命周期得以延长,对无线传感器网络来说意义重大.在模拟退火算法的基础上,通过节点剩余能量因素来选择簇头,均衡了网络内各节点的能量消耗,使得第一个节点的生存周期达到改进前的1.8倍以上,前80%节点的死亡时间均长于原有算法,从而提高了WSN的整体性能.参考文献(References):1戴世瑾,张翼德,李乐民.无线传感器网络的路由协议研究与分析J.计算机应用研究,xx,23 (12):2942297.DA IShi2jin,ZHANG Yi2de,L ILe2min.Research andparison onrouting protocols for wireless sensor worksJ.Application Researchof Computers,xx,23 (12):2942297.(in Chinese)2沈波,张世永,钟亦平.无线传感器网络分簇路由协议J.软件学报,xx,7 (7):158821600.SHEN Bo,ZHANG Shi2yong,ZHONG Yi2ping.Cluster2based routingprotocolsforwireless sensorworksJ.Software,xx,17 (7):158821600.(in Chinese)3Lindsey S,Raghavendra CS.PEGASIS:Power2efficient gatheringin sensorinformation systemsCIEEE AerospaceandElectronic SystemsSociety,Proc ofthe IEEEAerospace Conf.Montana:xx:112521130.4邢文训,谢金星.现代优化计算方法M.北京:清华大学出版社,1999:1162128.5张建航,李国.模拟退火算法及其在求解TSP中的应用J.现代电子技术,xx,29 (22):1572158.ZHANG Jian2hang,L IGuo.Simulated annealingalgorithmandthe applicationfor solvingTS