基于改进蚁群算法的无线传感器网络路由的优化

戴天虹，李　昊

(东北林业大学 机电工程学院，哈尔滨　150040)



基于改进蚁群算法的无线传感器网络路由的优化

戴天虹，李昊

(东北林业大学 机电工程学院，哈尔滨150040)

摘要：为了延长无线传感器网络(wireless sensor network,WSN)的生命周期，均衡各个节点间能量消耗，针对现有的WSN路由优化算法存在的问题，提出了一种基于改进蚁群算法的路由优化算法;首先通过对蚁群算法和遗传算法的优劣性比较，在蚁群算法的基础上，结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力;最优路径评价函数综合考虑节点能耗及节点的剩余能量，使剩余能量多的节点优先参与数据转发，均衡节点间的能量消耗;通过与经典蚁群算法及遗传算法的对比实验表明，随着数据转发轮数增加，改进的蚁群算法能耗小，剩余能量多，网络生命周期明显延长；随着整个网络运行时间的增长，改进的蚁群算法，节点均衡能耗性好，最优路径搜索的成功率也明显优于其他两种算法。

关键词：无线传感器网络；路由优化；蚁群算法；遗传算法

0引言

无线传感器网络(wireless sensor network，WSN)[1]是由分布在需要监测范围内的大量微型传感器通过无线通信的方式来传输数据所组成的一种网络，被广泛应用在环境比较复杂、人员不能到达的区域。传感器节点小，数量多，能量大多数由电池来提供，经过部署之后，很难再补充能量[2]。设计一个好的路由协议对减少能量消耗并且延长整个网络的生命周期有着重要的意义。针对现有的WSN路由优化算法，国内外学者进行了大量的研究，文献[3] Kassabalidis等人首次提出AntNet算法，该算法可以很快的建立好网络路由，对变化的网络拓扑结构有着很强的适应能力；但没有考虑网络节点的能耗，导致整个网络生命周期缩短。文献[4]提出了一种称之为ACRA的路由协议，这个路由算法，采用了主路径和备用路由相结合的方式，同时根据网络中节点状态更新路由表，从而使得整个网络的时延和能量消耗的性能有了很大的提高。文献[5]提出了一种基于地理位置信息的路由协议POSANT算法，按照邻居节点间的距离汇聚节点的远近程度划分区域，蚂蚁分组使用不同信息素更新策略来寻找下一跳路由。上述路由算法中，大部分是使网络的某一性能有所改善提高，并没有综合考虑多种性能参数，无法应对意外状况的发生。

如何综合考虑多种网络性能参数，改进蚁群算法使该算法适应WSN随机的网络拓扑环境？本文提出了一种基于改进蚁群算法的路由优化算法，在蚁群算法的基础上，结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力。最优路径评价函数综合考虑节点能耗及节点的剩余能量，使剩余能量多的节点优先参与数据转发，均衡节点间的能量消耗，达到延长网络生命周期的目的。

1无线传感器网络体系结构

无线传感器网络是由传感器、感知对象和观察者3个要素所构成的。 在无线传感器网络中，所有的传感器节点都是通过互相协调合作的方式来对该区域进行监测，并且通过无线信号来进行数据的传输和处理，最后将结果反馈给用户[6]。

无线传感器网络有以下几个特点：

1)每一个传感器节点在工作时不仅要进行数据的采集和发送，而且还要进行数据的转发。

2)每个传感器的节点都是以单跳或者多跳的方式来进行数据的传输，最终将信息发送到汇聚节点处。

3)汇聚节点与管理终端的数据发送方式有很多种，比如互联网、局域网、卫星通信等。

图1　无线传感器网络的体系结构

2蚁群算法

2.1基本的蚁群算法

蚁群算法是意大利学者M.Dorigo通过对自然界中蚂蚁的行为进行研究所提出的一种新型的模拟进化算法[7]。研究发现：蚂蚁在觅食过程中，会释放出一种信息素，该信息素会引导蚂蚁选择从洞穴到食物之间的最优路径。蚂蚁寻找到食物返回洞穴的过程中，会在返回的路径上留下信息素，后面的蚂蚁不但可以检测到该信息素的存在，还可以检测出信息素的浓度大小[8]。蚂蚁会选择信息素浓度较高的路径来进行觅食。同时，信息素还具有挥发的特性，随着时间的推移，路程较远的路径上的信息素会慢慢地挥发，浓度降低，那么蚂蚁选择该路径的概率会大大减少。路程较近的路径留下的信息素浓度增加，蚂蚁选择该路径的概率会增加，这种信息素浓度的增加会使后面的蚂蚁更高概率地选择该路径，这一现象就是正反馈。通过这种正反馈，蚂蚁总能选择到食物与洞穴之间的最优路径[9]。

2.2蚁群算法

通过对蚂蚁觅食的基本原理进行研究，科学家们设计了能够寻找最优路径的蚁群算法，算法的主要步骤为：

1)设外出寻找食物的蚂蚁数量为m只，并且该m只蚂蚁是随机出发的。

2)蚂蚁在觅食的过程中会在路径上留下信息素。设经过时间t之后，在路径(i,j)上留下的信息素的浓度为τi,j(t) 。并且在初始时刻的时候各个路径上的信息素的浓度是相同的，并且τi,j(0)=C，C为常数。

3)蚂蚁从洞穴出发寻找食物，通过对每条路径上的信息素的浓度进行比较，最终决定转移的方向。由以下的公式来定义蚂蚁的选择概率：

(1)

(2)

4)蚂蚁在整个觅食过程中，一直在释放信息素。每条路径上的信息素浓度一直在发生着变化[10]。信息素浓度的变化过程可以用公式(3)来表示：τ(i,j)←(1-ρ)τ(i,j)+ρΔτk(i,j)

(3)

式中，ρ 表示的是信息素在挥发时的参数。Lk表示的是第k只蚂蚁所爬行的总路程。

2.3改进的蚁群算法

基本的蚁群算法在寻找最优路径的过程中，局部寻优能力比较强，但是全局搜索能力比较弱。当寻找路径到达一定程度时，就会停滞不前，搜索能力会大大减慢。为了提高无线传感器网络的路径优化的效率，提出了一种改进的蚁群算法[11]。该改进是将遗传算法中的交叉、选择和变异等遗传算子引入到蚁群算法中，来提高寻找最优路径过程中的收敛速度和全局搜索的能力。

2.3.1路径编码

改进的蚁群算法在寻找最优路径之前需要对路径进行编码。编码方式采用实数方式，假如整个传感器网络中的传感器的数量为n，则将传感器节点分别编码为1，2，3，…，n。传感器最终需要将数据发送到汇聚节点上，那么将最终的汇聚节点编码为0。每经过一次循环，即传感器采集数据，经过各个节点的接收和发送，最终传输到汇聚节点的过程，就会得到一组路径编码。比如，获得的一组编码是：1，2，4，6，10，0，那么数据传输的路径是经过编码为1，2，4，6，10，0的传感器。

2.3.2适应度函数的设计

无线传感器网络的适应度函数的设计需要考虑多个因素，比如：路径的总长度；每一个节点接收和发送数据的能量消耗；整个无线传感器网络的能量均衡分布。考虑到以上几个因素，一条由n个传感器组成的适应度函数可以用以下公式来表示：

(4)

式中，wd为距离权重，we为能量消耗权重，wl为整个无线传感器网络的能量消耗权重，d(p)为该传输路径的总长度，e(p)为该路径的能量消耗，l(p)为整个无线传感器网络的能量消耗。

2.3.3选择操作

在选择操作过程，每经过一轮寻优过程之后，会得到一个路径集合，将每条路径进行适应度函数的计算，从中选择出比较优的路径来进行下一轮的搜索。这样经过几次寻优过程之后，会使比较优的路径上的信息素的浓度越来越大，该路径被选择的概率也越来越大，这样大大加快了寻优过程中的收敛速度。

2.3.4交叉操作

为了避免在全局搜索的过程中出现停滞不前的现象，引入了交叉操作[12]。经过该操作，可以扩大搜索的范围，防止局部最优解出现。蚁群算法在经过一轮搜索之后，会得到一些优解和次优解的路径，将优解和次优解来进行交叉操作，可以得到更多的路径来进行选择。假如S1表示最优解，S2表示次优解，那么交叉操作可以用以下过程来表示：

1)产生交叉操作的起始位置和交叉的长度都是随机的。

2)假如S1的路径为P1,P2,P3。S2的路径为Q1,Q2,Q3。发成交叉的位置为P2和Q2，交叉的长度为P2和Q2。那么经过交叉之后得到的新的路径为S3:P1,Q2,P2,P3。

3)将S3中重复的节点删除，最后得到一个新的路径S3。

4)通过上述方法得到新的路径S4。

5)对路径S1,S2,S3,S4进行适应度函数计算，最终得到最优的一条路径。

2.3.5变异操作

1)假设发生N次变异；

2)随机产生两个自然数n1和n2，并且n1,n2

3)将最优路径S上的第n1和n2个节点进行相互交换，产生新的编码路径S1；

4)对编码路径S和S1进行适应度函数计算，最后选择最优编码路径进行下一步。

2.3.6改进蚁群算法路径优化流程

在改进蚁群算法的无线传感器网络路径优化过程中，需要对无线传感器网络建立数学模型，并且进行初始化处理。文献[13]提出了一种基于路径平滑和信息素动态更新的自适应蚁群算法。在该算法的基础上得到启发：在寻优过程中，进行遗传算法中的选择、交叉和变异操作，来加快收敛速度和提高全局搜索的能力，最终得到一条最优的数据传输路径。整个工作流程如图2所示。

图2改进蚁群算法的WSN路径优化流程

3仿真研究

3.1仿真环境以及参数设置

为了更好地验证改进的蚁群算法的路径优化性能，需要对其进行仿真研究，采用网络模拟软件NS2来进行仿真。在仿真开始之前，需要对参数进行初步的设置。进行仿真的传感器点的数目为10个。蚁群算法仿真所需要的参数为：整个路径中的蚂蚁总个数为10个，α=0.2，β=0.2，ρ=0.3；遗传算法仿真所需要的参数为：蚂蚁种群的总个数为10个，在进化过程中最多能够进化1 000次，发生交叉操作的概率为0.9，发生变异操作的概率为0.01。无线感器网络结构如图3所示。

图3　无线传感器网络结构图

3.2算法的性能评价指标

为了能够更好地看出每种算法的优化效率，让结果具有可比性，需要建立算法的性能评价指标。本次指标从路径能量消耗和寻找最优路径的成功率两个方面来完成。同时将改进的蚁群算法和蚁群算法、遗传算法相比较，来体现出改进算法的优越性[14]。蚂蚁在寻找最优路径的过程中需要不断的消耗能量，那么在寻找最优路径的过程中蚂蚁消耗的总能量为：

(5)

其中：E表示的是消耗的总能量，ei表示的是每个节点消耗的能量。

传输过程中的能量消耗采用自由空间模型计算。路径损耗由下面的公式来计算：

(6)

(7)

因此在已知传感器的初始能量、仿真次数和运行时间的前提下，可以计算出各个节点的剩余能量。

3.3仿真结果

3.3.1能量消耗仿真结果

3种算法的能量消耗总量的仿真结果如图4所示，从图中可以看出，改进的蚁群算法在寻找最优路径的过程中消耗的能量最少，其次是蚁群算法，能量消耗最多的是遗传算法。因此，改进的蚁群算法能够减少能量消耗，延长整个网络的生命周期[15]。

图4　3种算法能量消耗

图5表示的是节点的平均剩余能量和算法运行的时间长短之间的关系。X轴为3种算法进行仿真的时间，本次的仿真时间为1 200 s，Y轴表示的是无线传感器网络节点的平均剩余能量。从图中可以看出，在同一时刻，改进的蚁群算法的节点平均剩余能量要高于蚁群算法和遗传算法，表明改进的蚁群算法的能量消耗要低于其他的两种算法。在图中还可以得到，改进的蚁群算法的网络生命周期是蚁群算法的1.21倍，是遗传算法的1.75倍。因此，改进的蚁群算法大大延长了整个网络的寿命。

图5节点平均剩余能量和算法运行时间的关系

3.3.2最优路径搜索成功率

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

表1　3种算法最优路径搜索成功率

4结论

通过本文理论叙述和仿真比较，验证了本文提出的算法在无线传感器网络实际应用中选择路径，均衡能源延长网络生命周期的优势：

1)本文结合遗传算法的选择、交叉和变异的操作，从而提高蚁群算法的搜索速度和寻优能力。使网络能够快速地建立一条最优的无线传感器网络路径，减少能量消耗，延长了整个网络的寿命。

2)本文综合考虑网络各性能指标，随着数据转发轮数增加，改进的蚁群算法能耗小，剩余能量多，网络生命周期明显延长；

3)随着整个网络运行时间的增长，改进的蚁群算法，节点均衡能耗性好，最优路径搜索的成功率也明显优于其他两种算法。

参考文献：

[1] 苏锦，等.改进蚁群算法的无线传感器网络路径优化[J].计算机仿真，2012,29(8):112-115.

[2] 陈宇，等.基于改进蚁群算法的无线传感网络路由的研究[D].广州：华南理工大学，2012.

[3] Caro G D, Dorigo M.AntNet: distributed Stigmergetic control for communication networks [J]. Journal of Artificial Intelligence Research, 1998,9(1):317-365.

[4] Caro D, Ducatelle F, Gambardella L. AntHoc Net: an adaptive nature inspired algorithm for routing in mobile ad hoc networks[J].European Transactions on Telecommunnications, 2005,16(5)：443-455.

[5] Rajagopalan S, Shen C .ASNI: A unicast routing protocol for mobile ad hoc networks using swarm intelligence[A].Proceedings of the International Conference on Artificial Intelligence[C]. Italy, 2005：24-27.

[6] 王永玲，郭爱煌.无线传感器网络路由协议及仿真[J]．计算机工程，2006,32(20):123-125.

[7] 冯宝华. 蚁群优化算法的原理及改进[J].科技信息, 2007, 31(7):94-95.

[8] 吴虎发.蚁群优化算法在求解最短路径问题中的研究与应用[D].安徽:安徽大学，2012.

[9] 程满中. 蚂蚁算法在车辆路径问题中的研究[D].湖北:中南民族大学, 2007.

[10] 龚瑜. 面向无线传感器网络的多路径路由协议研究[D].南京:南京邮电大学,2012.

[11] 黎洋.基于蚁群优化策略的WSN路由研究[D].长沙:长沙理工大学,2013.

[12] 陈雨.基于改进遗传算法的测试用例生成[J].电子科技，2009,10(7)：9-12.

[13] 何武.基于蚁群优化算法的无线传感器网络路由算法研究[D].重庆:西南交通大学,2008.

[14] 卢天宇.遗传蚁群混合算法研究及应用[D].西安：西安科技大学，2012.

[15] 李洪兵.基于蚁群算法的WSN路由算法研究[D].重庆：重庆理工大学，2011.

Optimization of Wireless Sensor Network Routing Based on Improved Ant Colony Algorithm

Dai Tianhong, Li Hao

(School of Mechanical and Electrical Engineering, Northeast Forestry University, Harbin150040，China)

Abstract:In order to extend wireless sensor networks (WSN) life cycle, to keep each node balance between energy consumption, to optimize existing WSN routing algorithm, we propose a routing optimization algorithm based on improved ant colony algorithm. Firstly, the ant colony algorithm and genetic algorithm comparison of the merits, on the basis of ant colony algorithm based on the combination of genetic algorithm selection, crossover and mutation operation, ant colony algorithm to improve search speed and optimization capabilities. Optimal route evaluation function considering the residual energy of nodes and node energy, the remaining energy of many nodes participate in forwarding priority, energy consumption balanced between the nodes. With the classical ant colony algorithm and genetic algorithms comparative experiments show that the number of rounds increases data transfer, improved ant colony algorithm energy consumption, surplus energy and more significantly prolong the network life cycle; with the growth of the entire network uptime, 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 algorithms.

Keywords:wireless sensor network; route optimization; ant colony algorithm; genetic algorithms

文章编号：1671-4598(2016)02-0321-04

DOI：10.16526/j.cnki.11-4762/tp.2016.02.089

中图分类号：TN926

文献标识码：A

作者简介：戴天虹(1963-)，男，黑龙江哈尔滨人，博士，教授，主要从事自动化等方面的教学与科研工作。

基金项目：哈尔滨市科技创新人才(优秀学科带头人计划类)基金项目2014RFXXJ086。

收稿日期：2015-08-29；修回日期：2015-10-11。