基于ga和leach的wsn引入交通层路径优化算法-李玉霞.pdf

《基于ga和leach的wsn引入交通层路径优化算法-李玉霞.pdf》由会员分享，可在线阅读，更多相关《基于ga和leach的wsn引入交通层路径优化算法-李玉霞.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第46卷第3期2017年5月电子科技大学学报Journal ofUniversity ofElectronic Science and Technology ofChinaV0146 NO3Mav 2017基于GA和LEACH的WSN引入交通层路径优化算法李玉霞1，一，徐永鑫3，何 磊4，张向秀3(1电子科技大学自动化工程学院成都611731；2成都理工大学国土资源部地学空间信息技术重点实验室成都6100593电子科技大学光电信息学院成都610054；4成都信息工程大学软件工程学院成都610225)【摘要】针对WSN节点中分层分簇路由算法存在能耗不均衡、簇首能耗高的问题，提出了一种基于GA和L

2、EACH的WSN引入交通层路径优化算法。该算法基于zigBee协议引入了新的拓扑结构，并优化了基于距离和能量因素的阈值函数，从而对WSN进行优化。仿真结果表明，在增加9整体耗能的前提下，减少了关键簇首95的通信能耗，有效地提高了wsN能耗均匀性，并延长了wsN 13倍的整体工作寿命。关键词遗传算法；交通层；无线传感网络； ZigBee协议中图分类号TP2741 文献标志码A doi：103969jissn10010548201703012Path Optimization Method in Transportation Layer of WSN Based onGenetic Algorit

3、hm and LEACHLI Yuxial，一，XU Yongxin3，HE Lei4，and ZHANG Xiangxiu3(1School ofAutomation Engineering，University ofElectronic Science and Technology ofChina Chengdu 611731；2Key Laboratory ofGeoscience Spatial Information Technology ofMinistry ofLand and Resources，Chengdu University ofTechnology Chengdu 6

4、10059；3School ofOptoeIectronic Information，University ofElectronic Science and Technology ofChina Chengdu 6100544College ofSoftware Engineering，Chengdu University ofInformation Technology Chengdu 610225)Abstract To solve the problems of unbalanced energy consumption and the high energy consumption o

5、fheader cluster effectively in the wireless sensor networks(WSN)，the Pa驴er proposes an optimized transportationlayer algorithm which is based on the genetic algorithm(GA)，low energy adaptive clustering hierarchy(LEACH)algorithmand ZigBee protoc01The algorithm introduces a new type of topological str

6、ucture and improves thethreshold function based on distance and ener州consumption for WSNThe simulation results show that theproposed algorithm can achieve a 95reduction of communication energy consumption of key cluster head with9increase of overall energy consumption，thus effectively improving the

7、uniformity of the energy consumption ofWSNand extending 13 times working life of the whole WSNKev words genetic algorithm；transportation layer； wireless sensor networks(WSN)； ZigBee protocol无线传感网络(WSN)是目前国内外的前沿和热门研究方向，在工业监测和控制、家居自动化和安全、军事监控和追踪等方面有着广泛的应用。因WSN节点有效运行的时间有限，所以如何减少能耗是WSN应用和研究中的关键难题。ZigBee

8、是一套常用、白适应、减少能耗的WSN路由协议【2J，它主要使用Cluster-tree协议【j矛NAODV(Ad hock ondemanddistance vector)协议【41来构建系统。在Cluster-tree协议中通过分簇选取簇首的方式收集簇内信息，簇首间用ADOV协议相互搜索自适应基站通信。Cluster-tree的问题在于簇首的能耗远远高于普通节点，使簇首的寿命大大减少，而簇首节点失效将导致该簇上的所有节点与基站失去联系。AODV的缺陷主要有根据自适应路由协议寻找的路径可能不是最优路径、实时性不足、能耗高、系统能耗均匀性差等。针对上述存在的问题，文献5在LEACH协议中考虑了能

9、耗因子，从而有效延长了WSN的运行周期，但没有探讨距离因素。文献6研究表明了遗传算法在WSN路径优化中的有效性，找到了优化路径并成功避开了能耗低的节点，但未对具体能耗情况进行深入分析，并且在距离方面也讨论不足。文献7在WSN中引入了中间层从而达到了均匀能耗的收稿日期：20160316；修回日期：20161206基金项目：国家自然科学基金(60841006，4157133)；国土资源部地学空间信息技术重点实验室开放基金(KLGSIT201608)作者简介：李玉霞(1979一)，女，副教授，主要从事定量遥感及其应用、无人机图像处理、空间信息提取等方面的研究万方数据550 电子科技大学学报 第46卷

10、效果，但是只根据距离因素采用动态路由方式对路径进行构建，一定程度上忽略了能量因素以及拓扑结构的优化研究。本文针对ZigBee的Cluster-tree及AODV路由协议现有的不足，通过引入新的拓扑和中问节点(下面称为交通层)，及与之匹配的综合考虑能量与距离因素的优化算法，来均匀簇首能耗，从根本上解决簇首能耗大的问题以及WSN整体能耗均匀性问题。1 GA算法禾ILEACH算法11 GA算法遗传算法(GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法。在GA算法中，染色体某一位置上具有相同位值的染色体的子集合通常称为基因模式(schemata)。在遗传算法中，模式阶次指基因模式中定义位置

11、(10为0或1)的个数，而模式定义长度则为基因模式中两个最外定义位置之间的距离。模式阶次0和定义长度cr(H)是量化基因模式。基于此定义，由已知的第n代群体中基因模式日的数目m(E以)，可得至ln+l代群体中基因模式罔拘期望数下界为：历(咖+1)m(脚)华l 1一只箬一PmO(H)l，av L ll J(1)式中，f(H)为基因模式H的适应度；，为染色体C的位串长度；、，为群体所有染色体的平均适应度；只为杂交概率；己为突变概率。那么，实现GA算法基本流程为：1)初始群体的产生；2)求每一个个体的适应度；3)根据适者生存的原则，选择优良个体；4)被选出的优良个体两两配对；5)通过随机交叉和变异某

12、些染色体的基因，生成下一代群体。按此方法使群体一代代的进化，直到满足进化的终止条件。具体实现方法：根据具体问题确定可行解域和编码方法，用字符串或数值串表示可行解域的每一个解。选取适应度函数为每一个解的度量依据。适应度函数为非负函数，本文选取GA的适应度函数为：。譬min厂(巧，死，死)2屯确 (2)i=l式中，妫节点间的距离；，z为选择的节点个数；7为编码方法。确定进化参数群体规模M、交叉概率P、变异概率只、进化终止条件。本文选用自适应方法选取杂交概率，有：Pc=厂厂(3)本文采取自适应方法选取变异概率，有：I竺!盘兰2 厂，7Pm=厶。一厂 。 。(4)a4 其他式中，厶。)=maxf(rc

13、l，乃，瓦)1 N7()=寺，(巧，乃，乃)1n=lf7=max厂(乃，死，死)，f(z1，乃，乃)q，为随机数，且aI，口2，a3，a40，1。12 LEACH算法LEACH算法采用随机方式选取簇首，在LEACH协议中，WSN执行过程是周期的，系统更新一次称为一轮，一轮包括簇的建立和稳定运行阶段。在簇的建立阶段，簇首会换届选举，即对节点n随机选择一个值，若该值小于一个阈值，则节点n成为本轮的簇首节点。阈值的表达式为：m)2可P习 1一p，mod二| (5)式中，P是簇首节点占总节点的百分比；，是当前轮次。本文根据式(5)选举簇首。2 WSN引入交通层路径优化算法通过本文设计的如图1所示算法流

14、程对wSN引入交通层路径进行算法优化：1)WSN的初始分簇WSN在工作后首先建立网络，各节点用浮点编码表示81，根据相互距离通过GA算法进行分簇91，得到一个最优的初始簇首情况。2)WSN选举出簇首在同一簇的WSN中，本文在LEACH算法中引入能量与距离因素，每一轮中通过一个优化的阈值对同簇的WSN进行选举，选出最合适的簇首。在LEACH算法中式(6)的，为当前轮次，为一固定的值。本文用剩余能量值和与交通层的距离删r值进行修正。节点剩余能量的计算为：RemEng=InitEng一(PktT木TEng)+(PktR木REng)(6)式中，RemEng代表节点剩余能量；PktT代表发送数万方数据第

15、3期 李玉霞，等：基于GA和LEACH的WSN弓I入交通层路径优化算法 551据包数量；TEng代表发送一次数据包所消耗的能量；PktR代表接收数据包的数量；REng代表接收一次数据包需要的能量。最终r修正的表达式为：r-：rdRemEng f71InitEng、。式中，d为簇首与待选交通层的距离。WSN网络建立网络建立优化LEACH函数选取簇首簇内节点加入簇首更新剩图1 引入交通层的总程序流程图3)WSN引入交通层簇首选举完后，簇首收集一轮簇内数据10q2】，并对簇首与基站之间建立交通层，即引入中间节点与基站通信。根据簇首节点的实际分布情况，可以利用GA算法对其进行最优的初始化设计，这使路径

16、设计最优化。通过调整交通层的个数，便可以根据需求获得所需的WSN的工作距离，具有很好的适应性。图2为交通层拓扑图。根据WSN簇首的分布情况，结合能量和距离因素式(7)对不同的情况采用不同的拓扑设计，分别为共用拓扑、平行拓扑以及复合拓扑。共用拓扑：多个簇首节点共享一个交通层与基站进行通信。在工作量较少、信息传输要求较低的区域，这种设计有利于提高资源利用率。平行拓扑：单个簇首节点通过特定的交通层与基站进行通信。在工作量较高、信息传输要求较高的区域，这种设计有助于增强WSN传输的实时性。复合拓扑：簇首与交通层之间综合使用共用拓扑和平行拓扑结构，形成一对多、多对一、多对多的复杂结构来满足实际应用中的需

17、求。节点簇首图2交通层的拓扑结构网络复杂程度越高，交通层的设计越精细，WSN的性能也就更接近实际的需求。本文利用GA算法对簇首接入交通层的拓扑进行基于能耗与距离情况的实时优化更新，其具体操作方式如图3所示。节点簇首簇首簇a共用拓扑结构b平行拓扑结构图3共用拓扑结构在每一轮簇的建立阶段之后，要对簇首接入交通层的拓扑形式进行更新，本文对GA算法的初始适应度函数进行了优化，其中初始适应度函数为：_Lminf(x,，92，死)=屯 (8)i=1式中，d为簇首与待选交通层的距离。根据WSN簇首在实际运用中簇首工作量的不同，引入一个实时变化的权值77描述各个节点的忙碌程度，其表达式为： r：hlitEng

18、-RemEngf9)=一 lyInitEng万方数据552 电子科技大学学报 第46卷式中，RemEng为节点剩余的能量；InitEngN初始总能量。系统会优先对77值较高的簇首进行分配。同理引入值对交通层忙碌程度进行描述，有：，k以=芝r； (10)I=l式中，k为交通层中第Ji个节点；胛代表共有n个簇首接入这个节点中；ri对应第i个接入交通层的当前能耗大小。最终GA算法的适应度函数优化为：minf(刀-,，t2，死)=芝。Atdk (11)百由式(7)、式(8)和式(10)可知，节点能耗越高，距离交通层越远，被选为簇首的概率越小。4)簇首换届交换交通层钥匙在簇首换届选举之后，上届簇首发送一

19、个数据包给下届簇首告知对应的交通层节点的地址，而本身遗忘交通层地址，这种设计相对于AODV协议的自适应找寻方式的优势在于只需要发送一次数据包便可以完成路径的建立，有效减少了AODV自适应过程的通信能耗和延迟时间。同时这种密匙交换的方法，降低了WSN节点记忆性能要求，可以减少能耗和降低成本。3算法仿真结果与分析aAODV协议 b引入爻通层图4仿真程序流程图本文基于MATLAB，首先使用GA算法对WSN的节点进行初始分布的最优化设计，使用LEACH算法选举第一届簇首，然后对没有引入交通层和引入交通层分别进行了仿真和研究，仿真程序流程如图4所示，并对结果进行了可视化显示。其中对于优化LEACH算法式

20、(9)，仿真数值由表1所示。表1仿真模拟参数模拟参数 仿真值区域大小m2节点数量基站位置控制数据包长度数据包长度初始化能量InitEngJ发送数据功率TEngmW接收数据功率REngmW簇首节点占总节点的百分LLp31 可视化分布结果00908070 2U 41) 6U 苎U j UU物理空间mb引入交通层图5 WSN分布可视化显示WSN分布可视化显示结果如图5所示，对其耗能情况进行了显示，图中的图例代表了产生的能耗大小。本文发现簇首能量远大于普通节点，簇首内部耗能也不均匀，同时耗能最多的为AODV协议中比较重要的节点。而引入交通层后普通节点和簇首之间能耗差别减小，簇首内部也相对均衡，且分布m

21、m一。，。加咖咖搬姒似渤伽瑚万方数据第3期 李玉霞，等：基于GA和LEACH的wSN引入交通层路径优化算法 553情况也优于AODV路由协议。32簇首能耗情况簇首能耗情况在实际应用中尤为关键，本文对每个簇首的能耗进行了跟踪记录，结果如图6所示。aAODV协议中能耗图b引入交通层后能耗图图6各个簇首耗能情况仿真图仿真数据表明，AODV协议中能耗最多的节点在本文算法仿真结果中减少了约95的通信能耗，其他关键节点也有较大的减少。少部分节点对整体能耗有9左右增加。33簇首能耗均匀性情况对比图6中的仿真结果可知，在AODV协议中，簇首之间的能耗随着时间增加而呈现发散关系，簇首之间耗能也极为不均，关键节点

22、耗能过大。在100轮后，簇首通信能耗的最高和最低值相差10倍。这是AODV协议设计所决定的必然现象，离基站较近簇首的能耗远大于离基站较远簇首的能耗，并且两者随着时间的增加而差距越来越大，使得能耗高的簇首寿命大大降低。在引入交通层拓扑的优化算法中，簇首只需负责收集簇内节点信息与交通层通信，节省了AODV算法自适应的通信能耗。距离基站的远近对簇首能耗情况不再有影响，能耗均匀性相对AODV协议有了很大程度上的提高。仿真结果显示，簇首之间能耗虽然略有差距，但在100轮内，已无明显的发散现象，发现簇首之间能耗几乎相等，均匀性十分理想。34簇首寿命情况引入交通层的优化协议相对于AODV协议，簇首提高13倍

23、的寿命。在AODV协议中能耗越高的节点，其在引入交通层之后寿命提高得越多。4结论与探讨本文研究通过引入交通层对AODV自适应算法进行优化，利用GA算法完成簇首与交通层的复杂拓扑的实时设计，发现对完全自适应的整体加入复杂实时的固定的优化因素，会将其整体性能向所期望的优化方向转化。本文所研究的新型WSN拓扑结构以及根据能耗与距离因素的分配方法有效提升了WSN总体寿命，减少了大部分WSN簇首的能耗(往往这些簇首处于比较关键的位置)，对WSN的性能进行了很大的提升。而本文的优化设计不足在于新节点的引入增加了WSN的整体的一定能耗，也使WSN之间的协议关系相对比较复杂。所以在不引入新的节点的情况下，对W

24、SN整体性能进行优化是一个非常有价值的命题，讨论也更加的复杂而有意义。本文的研究工作得到了成都市科技局项目f2014一HM0100122一SF)的资助，在此表示感谢!参考文献f11 HESHAM A，YANG S HDynamic cluster head for lifetimeefficiency in WSNrJlInternational Journal of Automationand Computing，2009，6f1)：4854r21 YOUNIS 0，R蛆MY SDistributed clustering in Adhocsensor networks：a hybrd，en

25、ergy-efficient approachCProc 13th Joint Conf on IEEE Computer andCommunications SocietiesfS11：IEEE Computer andCommunications Societies。20043】李剑，景博自适应遗传算法在多边议题协商中的应用J】北京邮电大学学报，2008，31(6)：6770LI JianJING BoAdaptive genetic algorithm and itsapplication in multilateral multi-issue negotiationJJournal o

26、f Beijing University of Posts andTelecommunications，2008，3 1 f6)：6770f41 SHARMA R，LOBIYAL D KProficiency analysis ofAODV DSR and TORA Adhoc routing protocols forenergy holes problem in wireless sensor networksJProcedia Computer Science。2015，57：10571066万方数据554 电子科技大学学报 第46卷【5饶皓，袁健基于节点生存时间的WSN节能路由算法J计

27、算机工程，2012，38(10)：99101RAO Hao，YUAN JianEnergy efficient routing algorithmin WSN based on node survival timeJComputerEngineering，2012，38(10)：991016雷霖，李伟峰，王厚军基于遗传算法的无线传感器网络路径优化J】电子科技大学学报，2009，38(2)：227230LEI LinLI WeifengWANG Hou-junPath optimization ofwireless sensor network based on genetic algorith

28、mJJournal of University of Electronic Science and Technologyof China，2009，38(21：227-23071吕林涛，范永林能量均衡的wsN非均匀分簇路由算法J计算机工程，2009，35(21)：117119LU LintaoFAN Yong1inEnergybalanced WSN unevenclustering zouting algorithmJComputer Engineering，200935(21)：117-1198杨挺，孙雨耕，杨郁，等无线传感器网络中一种节省资源的快速重路由算法J传感技术学报，2005，18

29、(3)：445448YANG Ting，SUN Yu-geng，YANG Yu，et a1A resource-efficient fast rerouting for wireless sensor networksJChinese Journal of Sensors and Actuators，2005，1 8(3)：4454489】YI Y K，融M HAgent-based geometry optimization withgenetic algorithm(GA)for tall apartmentS solar rightJSolar Energy,2015，113：236-2

30、5010陈拥军，袁慎芳无线传感器网络最小能耗拓扑控制研究J电子科技大学学报，2012，41(4)：568573CHEN Yong-jun，YUAN ShenfangMinimum energyconsumption topology control for wireless sensor networksJJournal of University of Electronic Science andTechnology ofChina2012，41(4)：568573111 MEDAGLIANI P，MARTALO M，FERRARI G Clusteredzigbee networks wi

31、th data fusion：characterization andperformance analysisJAd Hoc Networks，2011，9：10831 10312】王瑞锦，秦志光，王佳昊无线传感器网络分簇路由协议分析J电子科技大学学报，2013，42(3)：400405WANG Rui-jin，QIN Zhi-guang，WANG JiahaoAnalysisof wireless sensor network cluter routing protocolJJournal of University of Electronic Science andTechnology ofChina，2013，42f3)：400405编辑漆蓉万方数据