基于改进蚁群算法的无线传感器网络路由的优化-戴天虹.pdf

《基于改进蚁群算法的无线传感器网络路由的优化-戴天虹.pdf》由会员分享，可在线阅读，更多相关《基于改进蚁群算法的无线传感器网络路由的优化-戴天虹.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、謦畿仪器每传感技术 计算机测量与控制201 624(2)Computer Me嬲urement&Contr01 321 文章编号：16714598(2016)02一032104 DoI：1016526jcn ki114762tp201602089 中圈分类号：TN926 文献标识码：A基于改进蚁群算法的无线传感器网络路由的优化戴天虹，李 昊(东北林业大学机电工程学院，哈尔滨 150040)摘要：为了延长无线传感器网络(wireless sensor network，wsN)的生命周期，均衡各个节点间能量消耗，针对现有的wsN路由优化算法存在的问题，提出了一种基于改进蚁群算法的路由优化算法；首先

2、通过对蚁群算法和遗传算法的优劣性比较，在蚁群算法的基础上，结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力；最优路径评价函数综合考虑节点能耗及节点的剩余能量，使剩余能量多的节点优先参与数据转发，均衡节点间的能量消耗；通过与经典蚁群算法及遗传算法的对比实验表明，随着数据转发轮数增加，改进的蚁群算法能耗小，剩余能量多，网络生命周期明显延长；随着整个网络运行时间的增长，改进的蚁群算法，节点均衡能耗性好，最优路径搜索的成功率也明显优于其他两种算法。关键词：无线传感器网络；路由优化；蚁群算法；遗传算法optimization of Wireless Sensor Network

3、 Routing Based onImproVed Ant Colony AlgorithmDai Tianhong，Li Hao(School of Mechanical and Electrical Engineering，Northeast Forestry University，Harbin 150040，China)Abst憎ct：In order to extend wireless sensor networks(WSN)1ife cycle，to keep each node balance between energy consumption，to optimize exis

4、ting WSN routing algo rithm，we propose a routing optimization algo rithm based on improved ant colony algorithmFirstly，the antcolony algo rithm and genetic algorithm comparison of the merits，on the basis of ant colony algo rithm based on the combination of genetic algo rithm selection，crossover and

5、mutation operation，ant colony algo rithm to improve search speed and optimization capabilities 0ptimalroute evaluation function considering the residual energy of nodes and node energy，the remaining energy of many nodes participate in fo卜warding prio“ty，energy consumption balanced between the nodes

6、With the cIassical ant colony algorithm and genetic algorithms comparative experiments show that the number of rounds increases data transfer，improved ant colony algorithm energy consumption，surplus energyand more significantly prolong the network life cycle；with the growth of the entire network upt

7、ime，improved ant colony algorithm，node energy balance is good，the success rate of the optimal path search is also significantly better than the other two algo“thmsKeywords：wireless sensor network；route optimization；ant coIony algorithm；genetic algorithmsO 引言无线传感器网络(wireless sensor network，wSN)11是由分布

8、在需要监测范围内的大量微型传感器通过无线通信的方式来传输数据所组成的一种网络，被广泛应用在环境比较复杂、人员不能到达的区域。传感器节点小，数量多，能量大多数由电池来提供，经过部署之后，很难再补充能量2。设计一个好的路由协议对减少能量消耗并且延长整个网络的生命周期有着重要的意义。针对现有的wSN路由优化算法，国内外学者进行了大量的研究，文献3Kassabalidis等人首次提出AntNet算法，该算法可以很快的建立好网络路由，对变化的网络拓扑结构有着很强的适应能力；但没有考虑网络节点的能耗，导致整个网络生命周期缩短。文献4提出了一种称之为ACRA的路由协议，这个路由算法，采用了主路径和备用路由相

9、结合收稿日期：2015一0829；修回日期：201510一11。基金项目：哈尔滨市科技创新人才(优秀学科带头人计划类)基金项目2014RFXXJ086。作者简介：戴天虹(1963一)，男，黑龙江哈尔滨人，博士，教授，主要从事自动化等方面的教学与科研工作。的方式，同时根据网络中节点状态更新路由表，从而使得整个网络的时延和能量消耗的性能有了很大的提高。文献5提出了一种基于地理位置信息的路由协议POSANT算法，按照邻居节点间的距离汇聚节点的远近程度划分区域，蚂蚁分组使用不同信息素更新策略来寻找下一跳路由。上述路由算法中，大部分是使网络的某一性能有所改善提高，并没有综合考虑多种性能参数，无法应对意外

10、状况的发生。如何综合考虑多种网络性能参数，改进蚁群算法使该算法适应wSN随机的网络拓扑环境?本文提出了一种基于改进蚁群算法的路由优化算法，在蚁群算法的基础上，结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力。最优路径评价函数综合考虑节点能耗及节点的剩余能量，使剩余能量多的节点优先参与数据转发，均衡节点间的能量消耗，达到延长网络生命周期的目的。1 无线传感器网络体系结构无线传感器网络是由传感器、感知对象和观察者3个要素所构成的。在无线传感器网络中，所有的传感器节点都是通过互相协调合作的方式来对该区域进行监测，并且通过无线信号来进行数据的传输和处理，最后将结果反馈给用户6

11、。万方数据322 计算机测量与控制 第24卷无线传感器网络有以下几个特点： 离。卢表示的是蚂蚁在寻找路径时所释放信息素的损耗，它是1)每一个传感器节点在工作时不仅要进行数据的采集和 一个常数，有着非常重要的作用。Jx(i)表示的是所有相邻节发送，而且还要进行数据的转发。 点的位置的集合9。2)每个传感器的节点都是以单跳或者多跳的方式来进行 4)蚂蚁在整个觅食过程中，一直在释放信息素。每条路数据的传输，最终将信息发送到汇聚节点处。 径上的信息素浓度一直在发生着变化1。信息素浓度的变化3)汇聚节点与管理终端的数据发送方式有很多种，比如 过程可以用公式(3)来表示：r(i，j)一(1一lD)r(i，

12、j)+陋rt(i，互联网、局域网、卫星通信等。 i)图l 无线传感器网络的体系结构2 蚁群算法21基本的蚁群算法蚁群算法是意大利学者MDorigo通过对自然界中蚂蚁的行为进行研究所提出的一种新型的模拟进化算法7。研究发现：蚂蚁在觅食过程中，会释放出一种信息素，该信息素会引导蚂蚁选择从洞穴到食物之间的最优路径。蚂蚁寻找到食物返回洞穴的过程中，会在返回的路径上留下信息素，后面的蚂蚁不但可以检测到该信息素的存在，还可以检测出信息素的浓度大小8。蚂蚁会选择信息素浓度较高的路径来进行觅食。同时，信息素还具有挥发的特性，随着时间的推移，路程较远的路径上的信息素会慢慢地挥发，浓度降低，那么蚂蚁选择该路径的概

13、率会大大减少。路程较近的路径留下的信息素浓度增加，蚂蚁选择该路径的概率会增加，这种信息素浓度的增加会使后面的蚂蚁更高概率地选择该路径，这一现象就是正反馈。通过这种正反馈，蚂蚁总能选择到食物与洞穴之间的最优路径L。22蚁群算法通过对蚂蚁觅食的基本原理进行研究，科学家们设计了能够寻找最优路径的蚁群算法，算法的主要步骤为：1)设外出寻找食物的蚂蚁数量为研只，并且该m只蚂蚁是随机出发的。2)蚂蚁在觅食的过程中会在路径上留下信息素。设经过时间之后，在路径(i，j)上留下的信息素的浓度为r州(f)。并且在初始时刻的时候各个路径上的信息素的浓度是相同的，并且rh，(o)一C，C为常数。3)蚂蚁从洞穴出发寻找

14、食物，通过对每条路径上的信息素的浓度进行比较，最终决定转移的方向。由以下的公式来定义蚂蚁的选择概率：f竽越江虹业，jMi)R，一j，蚤，j)支一i可“(1)o，j，K(i)刚，j)一寿 (2)公式(1)中，P，表示第女只蚂蚁从节点i向节点j转移的概率，女一l，2，3，m。d。表示的是节点i与节点j之间的距觚j)：ji瓦万未瓣lo，其他(3)式中，lD表示的是信息素在挥发时的参数。L表示的是第女只蚂蚁所爬行的总路程。23改进的蚁群算法基本的蚁群算法在寻找最优路径的过程中，局部寻优能力比较强，但是全局搜索能力比较弱。当寻找路径到达一定程度时，就会停滞不前，搜索能力会大大减慢。为了提高无线传感器网络

15、的路径优化的效率，提出了一种改进的蚁群算法1“。该改进是将遗传算法中的交叉、选择和变异等遗传算子引入到蚁群算法中，来提高寻找最优路径过程中的收敛速度和全局搜索的能力。231路径编码改进的蚁群算法在寻找最优路径之前需要对路径进行编码。编码方式采用实数方式，假如整个传感器网络中的传感器的数量为”，则将传感器节点分别编码为l，2，3，行。传感器最终需要将数据发送到汇聚节点上，那么将最终的汇聚节点编码为0。每经过一次循环，即传感器采集数据，经过各个节点的接收和发送，最终传输到汇聚节点的过程，就会得到一组路径编码。比如，获得的一组编码是：1，2，4，6，10，O，那么数据传输的路径是经过编码为1，2，4

16、，6，10，o的传感器。232适应度函数的设计无线传感器网络的适应度函数的设计需要考虑多个因素，比如：路径的总长度；每一个节点接收和发送数据的能量消耗；整个无线传感器网络的能量均衡分布。考虑到以上几个因素，一条由n个传感器组成的适应度函数可以用以下公式来表示：厂(p)一咖d(户)+me(p)+训f(户) (4)式中，妣为距离权重，砒为能量消耗权重，毗为整个无线传感器网络的能量消耗权重，d(户)为该传输路径的总长度，e(p)为该路径的能量消耗，z(声)为整个无线传感器网络的能量消耗。233选择操作在选择操作过程，每经过一轮寻优过程之后，会得到一个路径集合，将每条路径进行适应度函数的计算，从中选择

17、出比较优的路径来进行下一轮的搜索。这样经过几次寻优过程之后，会使比较优的路径上的信息素的浓度越来越大，该路径被选择的概率也越来越大，这样大大加快了寻优过程中的收敛速度。234交叉操作为了避免在全局搜索的过程中出现停滞不前的现象，引入了交叉操作口“。经过该操作，可以扩大搜索的范围，防止局部最优解出现。蚁群算法在经过一轮搜索之后，会得到一些优解和次优解的路径，将优解和次优解来进行交叉操作，可以得万方数据第2期 戴天虹，等：基于改进蚁群算法的无线传感器网络路由的优化 323 到更多的路径来进行选择。假如s。表示最优解，解，那么交叉操作可以用以下过程来表示：Sz表示次优 发生变异操作的概率为o01。无

18、线感器网络结构如图3所示。1)产生交叉操作的起始位置和交叉的长度都是随机的。2)假如S，的路径为P，P。，P3。S：的路径为Q，Q2，Q。发成交叉的位置为Pz和Q2，交叉的长度为Pz和Q2。那么经过交叉之后得到的新的路径为S。：P，Q2，P。，Ps。3)将S。中重复的节点删除，最后得到一个新的路径S。4)通过上述方法得到新的路径S；。5)对路径S。，Sz，S。，S。进行适应度函数计算，最终得到最优的一条路径。235变异操作1)假设发生N次变异；2)随机产生两个自然数，ll和n2，并且挖l，行2竹l；3)将最优路径S上的第九。和行z个节点进行相互交换，产生新的编码路径S。；4)对编码路径S和S。

19、进行适应度函数计算，最后选择最优编码路径进行下一步。236 改进蚁群算法路径优化流程在改进蚁群算法的无线传感器网络路径优化过程中，需要对无线传感器网络建立数学模型，并且进行初始化处理。文献13提出了一种基于路径平滑和信息素动态更新的自适应蚁群算法。在该算法的基础上得到启发：在寻优过程中，进行遗传算法中的选择、交叉和变异操作，来加快收敛速度和提高全局搜索的能力，最终得到一条最优的数据传输路径。整个工作流程如图2所示。图2改进蚁群算法的wsN路径优化流程3仿真研究31仿真环境以及参数设置为了更好地验证改进的蚁群算法的路径优化性能，需要对其进行仿真研究，采用网络模拟软件NS2来进行仿真。在仿真开始之

20、前，需要对参数进行初步的设置。进行仿真的传感器点的数目为10个。蚁群算法仿真所需要的参数为：整个路径中的蚂蚁总个数为10个，ao2，卢一o2，lDo3；遗传算法仿真所需要的参数为：蚂蚁种群的总个数为10个，在进化过程中最多能够进化1 Ooo次，发生交叉操作的概率为o9，图3无线传感器网络结构图32算法的性能评价指标为了能够更好地看出每种算法的优化效率，让结果具有可比性，需要建立算法的性能评价指标。本次指标从路径能量消耗和寻找最优路径的成功率两个方面来完成。同时将改进的蚁群算法和蚁群算法、遗传算法相比较，来体现出改进算法的优越性1“。蚂蚁在寻找最优路径的过程中需要不断的消耗能量，那么在寻找最优路

21、径的过程中蚂蚁消耗的总能量为：E一岛 (5)tl其中：E表示的是消耗的总能量，B表示的是每个节点消耗的能量。传输过程中的能量消耗采用自由空间模型计算。路径损耗由下面的公式来计算：1一面蒜 6)1 】2巳一而南酽舞。因此在已知传感器的初始能量、仿真次数和运行时间的前提下，可以计算出各个节点的剩余能量。33仿真结果331能量消耗仿真结果3种算法的能量消耗总量的仿真结果如图4所示，从图中可以看出，改进的蚁群算法在寻找最优路径的过程中消耗的能量最少，其次是蚁群算法，能量消耗最多的是遗传算法。因此，改进的蚁群算法能够减少能量消耗，延长整个网络的生命周期15。l _改进算法 c G图4 3种算法能量消耗图

22、5表示的是节点的平均剩余能量和算法运行的时间长短之间的关系。X轴为3种算法进行仿真的时间，本次的仿真时间为1 200 s，y轴表示的是无线传感器网络节点的平均剩余能量。从图中可以看出，在同一时刻，改进的蚁群算法的节点平均剩余能量要高于蚁群算法和遗传算法，表明改进的蚁群算法的能量消耗要低于其他的两种算法。在图中还可以得到，改进的蚁万方数据324 计算机测量与控制 第24卷群算法的网络生命周期是蚁群算法的121倍，是遗传算法的175倍。因此，改进的蚁群算法大大延长了整个网络的寿命。运行时问(20s)图5 节点平均剩余能量和算法运行时间的关系332最优路径搜索成功率表1所示的是3种算法经过loo组，

23、每组100次仿真之后得到的最优路径搜索的成功率。在仿真过程中，通过适应度函数和能量消耗的计算可以得到一条从初始节点到汇聚节点的一条最优路径S。每次仿真结束之后会得到一条路径S。，将S。与S相比较来确定该次仿真是否获得最优路径。从表中可以看出，改进的蚁群算法是3种算法中最优路径搜索成功率最高的，其实是蚁群算法和遗传算法。改进的蚁群算法在蚁群算法的基础上进行选择、交叉和变异的操作，不仅能够减少路径中能量的消耗，延长了整个网络的寿命，还大大提高了搜索最优路径的成功率。表l 3种算法最优路径搜索成功率算法 成功率改进的蚁群算法 9318蚁群算法 81_76遗传算法 72464 结论通过本文理论叙述和仿

24、真比较，验证了本文提出的算法在无线传感器网络实际应用中选择路径，均衡能源延长网络生命周期的优势：1)本文结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力。使网络能够快速地建立一条最优的无线传感器网络路径，减少能量消耗，延长了整个网络的寿命。2)本文综合考虑网络各性能指标，随着数据转发轮数增加，改进的蚁群算法能耗小，剩余能量多，网络生命周期明显延长；3)随着整个网络运行时间的增长，改进的蚁群算法，节点均衡能耗性好，最优路径搜索的成功率也明显优于其他两种算法。参考文献：1苏锦，等改进蚁群算法的无线传感器网络路径优化J计算机仿真，2012，29(8)：1121152陈 宇，

25、等基于改进蚁群算法的无线传感网络路由的研究D广州：华南理工大学，20123caro G D，Dorigo M AntNet：distributed stigmergetic control forcommunication networksJ Joumal of Artificial Intelligence Research，1998，9(1)：3173654caro D，Ducatelle F，Gambardena LAntHoc Net：an adaptive nature inspired algorithm for routing in mobiIe ad hoc networksJ

26、European Transactions on Telecommunnications， 2005， 1 6 (5)：4434555Rajagopalan s，shen c ASNI：A unicast routing protocol for mobile ad hoc networks using swarm intelligenceA Proceedings ofthe International conference on Artificial Intell培encec Italy，2005：24276王永玲，郭爱煌无线传感器网络路由协议及仿真J计算机工程，2006，32(20)：1

27、231257冯宝华蚁群优化算法的原理及改进J科技信息，2007，31(7)：94958吴虎发蚁群优化算法在求解最短路径问题中的研究与应用D安徽：安徽大学，20129程满中蚂蚁算法在车辆路径问题中的研究D湖北：中南民族大学，200710龚瑜面向无线传感器网络的多路径路由协议研究D南京：南京邮电大学，201211黎洋基于蚁群优化策略的wsN路由研究D长沙：长沙理工大学，201312陈雨基于改进遗传算法的测试用例生成J电子科技，2009，lO(7)：9一1213何武基于蚁群优化算法的无线传感器网络路由算法研究D重庆：西南交通大学，200814卢天宇遗传蚁群混合算法研究及应用D西安：西安科技大学，20

28、1215李洪兵基于蚁群算法的wsN路由算法研究D重庆：重庆理工大学，2011毋啦孕哆浮呈9诤鲫惮蛐博韭尊妇婷韭守旦9谆蚰诤旦9守蚋诤韭陋孚蜉孚啦乎驷诤业尊旦9诤鲫博曲诤韭诤韭寸韭诤韭孕蜱诤韭诤鲫诤蛐诤旦9诤蚋渺字旦9诤韭孚i9阻渺尊驷诤驷婷旦9诤蚰诤韭诤韭博辨溥iP韭诤弛曹蛐博韭孛蚌淳眇宇韭(上接第313页)设计了在现代飞行试验中海量AFDX总线数据检测分析的关键技术，采用这些算法设计了AFDx总线数据检测分析软件，解决了AFDx总线数据检测分析的关键问题。经某试验机试飞实际验证，该软件满足了试飞工程师的AFDx总线检测分析需求，分析的结果数据满足对航空设备航电系统进行科研鉴定的需求。参考文献

29、：1ARINc 664。Aircraft Data Network，Part7：Avionics Full Duplexswitched Ethernet(AFDx)Networks20052AFDx：The Next-Generation Interconnect for Avionics subsystemsJAvionics Magazine，20053宋东，曾星星，等AFDx网络系统建模与仿真实现J测控技术，2012(2)：76804赵永库等AFDx网络测试技术研究J计算机测量与控制，201220(4)5彭国金基于类PcM结构过程的试飞多科目iNet数据处理技术J计算机测量与控制，2015(10)6彭国金等非结构化海量网络数据处理技术研究J现代电子技术，2011(14)万方数据