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

沙娓娓，刘增力

（1. 昆明理工大学 信息工程与自动化学院，云南 昆明 650500；2. 昆明理工大学 民航学院，云南 昆明 650500）

0 引言

无线传感器网络：指利用无线通信的方法，将微型传感器节点（被感知对象的内部、附件之中）组成多跳自组织网络，在环境监测、国家安全以及军事侦察等相关领域得以普遍应用[1]。传感器节点由电池提供能量，同时具有数量多、体积小等特点，一旦完成部署，即难以继续补充能量。所以在设计无线传感器网络路由协议时，要充分考虑节点能量问题，以延长网络生存周期达到传输大量数据的要求[2]。

Dorigo针对TSP的问题，提出全新的模拟进化算法——蚁群优化算法[3]。与此同时随着该算法的应用，有效解决指派、调度以及旅行商等各类优化组合问题[4]。

Kassabalidis等潜心多年研究，结合蚁群算法，提出Ant-Net算法[5]，该算法中蚂蚁主要可分为两大类：其一是具有收集节点信息作用的前向蚂蚁；其二为返回蚂蚁，将前向蚂蚁收集的信息，反馈在路由表之中。

Schoonderwoerd R等人通过概率选择和更新路径的方式，提出ABC算法[6]，此算法中蚂蚁从源节点到达目的节点后就死亡，同时更新路由表。文献[7]基于 DD算法[8]提出一种全新的算法——ARAWSN，有助于改善能耗问题，可找到源节点到目的节点间最短的路径。

本文提出IARA这一全新优化的算法，在源节点选择下一跳节点，兼顾了节点的能量、传输方向、节点间距离等因素，通过改进的信息素更新公式、启发函数、选择概率这三个方面，不仅降低了节点能耗，同时有助于延长网络生存周期。

1 无线传感器网络通信的能耗模型

在能耗模型方面，本文考虑选择同文献[9]的模型，将k bit的数据发送到d节点时，可用如下公式表示这一过程消耗的能量。

此时接收节点消耗能量：

融合数据消耗能量：

式（1）～（3）中：elecE、ampE、fuseE分别指发送和接收、传输放大以及融合数据等单元功耗，如果传输距离较大，则通常建议选择运用多路径衰减模型，相反的如果较小，则一般运用自由能量模型。

2 改进的WSN蚁群路由算法描述

在具体设计 WSN路由时，应充分考虑到无线传感器网络节点的特殊性，即其能量有限。针对这一问题，本文紧扣“有效性”这一原则，充分考虑下一跳节点的能量参数以及实际传输距离、方向等问题，使蚁群在自动寻优的同时，也具有能量感知意识。

2.1 路径概率选择

从路径探索的角度出发，非常有必要结合某种概率访问周围节点：而从路径寻优这一层面分析，为避免局部最优解，在访问时节点时，如果仅以概率为基础，其获得的最优解并非都有意义[10]。因此，引入传输方向参数，改进后的转移概率公式如下：

式（4）中，表示第k只蚂蚁从节点i向节点j转移的概率；用于表示k可通信节点集合，如果其通信节点并非可允许的节点，那么此时概率应等于0；这里τij、ηij分别表示信息素浓度、启发函数，两者的权重值分别为α、β。假设α值较大，则对应的信息素浓度发挥的作用相对较大，换言之即蚂蚁会以已经走过的路径为主，彼此间具有较强的协同能力；相反的如果β值较大，则对应说明启发函数可发挥更大的作用，此时以未探索过的节点为主，换言之即蚂蚁具有较强的探索能力，可探索新节点。θ为下一跳节点 next,源节点 source和目的节点destination的夹角；γ为定义的常量，指明了传输方向对节点路由选择的影响程度。

如图1所示，即为θ的示意图，通过该图可充分说明，假设θ越小，那么对应的d1+d3越小，传输方向越接近于节点next到destination节点的连线方向，且

图1 传输方向Fig.1 Direction of communication

2.2 本地启发函数

蚂蚁从节点i转移到节点j的期望程度用启发函数ijη表示。由于最初是针对TSP的问题而提出该算法，所以启发函数并未充分考虑其它因素，仅以两节点的距离为考量重点。而无线传感器网络，除应充分重视距离因素之外，还需综合考虑诸如节点、邻居节点剩余能量等多方面的问题。基于此，如式（6）所示，即为本文的启发函数定义：

式（6）中，Ecurrent(j)为节点 i的邻居节点 j当前剩余能量；Ni(k)表示集合节点i的邻居节点集合；(k)为节点i所有邻居节点的剩余能量。节点剩余能量与该节点是否会被选择有直接的关系，节点的能量水平越低，被选择的概率也会越低；dij表示的是节点i和节点j之间的距离。

2.3 信息素更新

蚂蚁选择下一跳节点时，会在经过路径上释放出信息素，从而形成并增加可用于引导后来蚂蚁的信息素浓度。由改进后的公式可知，节点剩余能量越多的路径上累积的信息素浓度也会越高，这样有助于避免由于路径（最短）的信息素浓度过大，而出现蚂蚁过分集中的问题，有助于避免节点能量消耗过快。给出信息素更新公式如下：

其中：Lk为蚂蚁k从源节点到目的节点所经过的路径长度；λ为一个全局设定的常量； Ek_min、Ek_avg分别可用于表示蚂蚁k经过路径节点的最小能量、平均能量。如式（8）所示，综合考虑了路径中最小能量、平均能量以及路径总长度这三个因素。假设在更新路径信息素时，未充分考虑这一情况 ，仅以节点能量为依据，那么运用此算法，则路径不一定最短。

2.4 IARA算法的实现

具体实现步骤如下：

（1）初始化。清空蚂蚁路径，初始化访问标志，显示为未访问；在源节点中放m只蚂蚁，同时设置为已访问，此为路线的第一个节点，另外各节点的初始值均为常数，且包含同样的信息素；信息素增量在初始时为0；

（2）Antnum等于0，即到达目的节点的蚂蚁数为0；

（3）蚂蚁数k等于0；

（4）通过计算求出节点间距离；

（5）运用（4）式计算转移概率，并确定节点j，把蚂蚁k转移至此j，同时设置该节点为已访问，除了要修改蚂蚁节点的能量外，还应对应修改前一节点能量；

（6）如果有节点能量耗尽，则直接跳至（9），如果没有则依据（7）进行；

（7）k等于k+1，对比该值与m大小，较小转（5），否则转（8）；

（8）判断Antnum是否等于m，若两者相等，即此时蚂蚁都到目的节点，则转（9），如果没有则转（3）；

（9）计算蚂蚁经过的整个路径的长度，比较得出最优路径；

（10）如果通过计算，并未有节点耗尽能量，则根据式（7）、（8）进行信息素的全局更新后转（2）执行；否则转（11）；

（11）如上述循环结束，最终输出结果。

3 仿真及结果分析

通过Matlab访真、验证IARA算法，在此基础上对比分析了 ACO算法（文献[3]），仿真范围为100 m×100 m，并在这一范围内播撒（随机）50个节点，将设定目标节点（50,50）。

考虑到测试的方便性，本文中设蚂蚁总数为50只，即等于节点个数；无线传感器节点每次传输相同大小的数据包，参数初值为：α=1，β=2，γ=1，λ =1，rmax=50，每个节点初始能量为0.5J。

正如上文所述，引入本算法的目的，即在延长网络使用时长的同时，最小化能量消耗。所以本文基于蚂蚁群算法，提出IACA法，该法改进了相关参数，通过传输距离、节点能量、传输方向这三者的综合考虑，从而找到理想的延长网络生存时间的方法。因此，为了验证算法的性能，对比ACO算法，具体体现在如下两个方面：其一网络节点能耗总量；其二死亡节点数。

3.1 节点能耗

本文中的网络生存时间，由所有节点消耗的能量之和反映，假设能耗越大，那么其生存时间就会越短；也就是说，一定时间内消耗大量的能量，则其对应的网络生存时间较短；相反的，如果能量消耗较小，则说明具有较长的生存时间，全网节点共计50个，每个节点的初始能量为0.5J，因此全网总能量为25J，图2 IARA和ACO能量消耗对比图。从图2中可以看出，IARA和ACO分别在930、710轮时全网能量消耗殆尽。

3.2 死亡节点数

能耗与死亡节点有一定关系，但是两者又存在一定差异性。通过能耗量可充分说明在接收或者发送数据的消耗量，但是节点平均能耗与死亡节点数没有必然的联系，即死亡节点数不会单纯因为节点平均能耗多而增多。假设仅少数节点消耗了能量，其它节点并未消耗或者基本没有消耗能量，这种情况下死亡节点数较少，但是不可忽视的是极有可能死亡节点均处于关键路径上，即使得整个网络瘫痪，对应的其网络生存的时间必然也会很短；假设由多个节点共同消耗节点能量，即属于平均消耗，那么就算最后有很多死亡节点，也不易出现关键节点完全失效的问题，即相应的出现网络瘫痪的机率也会较小，这样一来，即有延长网络生存时间的作用。从图3中可以看出，IARA和ACO分别在930、710轮时全部节点死亡，因此IARA算法的生命周期比ACO要长，达到了预期的效果，证明了算法的有效性。

图2 能量消耗Fig.2 Energy consumption

图3 死亡节点数Fig.3 Nodes death

4 总结

本文基于无线传感器网络的特殊性，即节点能量少，引入具有健壮性、自组织性、自治性等优点的蚁群算法，提出改进的蚁群路由算法 IARA，在基本蚁群算法的基础上综合考虑了节点的能量、距离、传输方向等参数。仿真结果表明：通过该算法解决了无线传感器网络瓶颈问题，即能耗大、网络生存时间短，形成了节能、快速的路由来满足网络使用需要。

[1] 段海滨. 蚁群算法及其应用[M]. 北京: 科学出版社2007:1389.DUAN H B, Ant colony algorithm and its application[M].Beijing: Science Press 2007: 1389.

[2] 陈宇, 等. 基于改进蚁群算法的无线传感器网络路由的研究[D]. 广州: 华南理工大学, 2012.CHEN Y, et al. Research on routing of wireless sensor networks based on improved ant colony algorithm[D]. Guangzhou:South China University of Technology, 2012.

[3] Dorigo M, Gambardella L M. Ant colony system a cooperative learning approach to the travelling salesman problem[J].IEEE Transactions on Evolutionary Computation. 1997, 1(1): 53-66.

[4] Sim K M, Sun W H. Multiple ant-colony optimization for network routing[C]//Proceedings of the 1st International Symposium on Cyber Worlds, Washington DC, USA, 2001:277-281.

[5] Kassabalidis I, El-Sharkaw M A, Marks R J. Swarm intelligence for routing in communication networks[J]. Global telecommunications 2001, 6(6): 3613-3617.

[6] Schoonderwoerd R, Holland O, Bruten J, et al. Ants for load balancing in telecommunication networks[R]. Bristol: Hewlett Packard Lab, 1996. M. Goldfarb. Analog baseband IC for use in direct conversion W-CDMA receivers. IEEE.

[7] 梁华为, 陈万明, 李帅, 等．一种无线传感器网络蚁群优化路由算法[J]. 传感器技术学报, 2007, 20(11): 2450-2455.LIANG W H, CHEN W M, LI S et al. Ant colony optimization routing algorithm for Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(11): 2450-2455.

[8] Intanagonmimwt C, Govindan R, Estrin D. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans on Networking, 2003, 11(1): 2-16.

[9] Heinzelman W R. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communication, 2002, 1(4): 660-670.

[10] 滑楠, 史浩山, 高程, 等． 一种适用于无线传感器网络路由的改进蚁群算法[J]. 传感技术学报, 2007, 20(7):1063-1069.HUA N, SHIH S, GAO C, et al. An improved ant colony algorithm for routing in Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(7): 1063-1069.