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

随着无线通信技术、电子技术、传感器技术和微电系统的飞速发展，无线传感器网络的研究越来越受到人们的重视。传感器网络是由部署在观测环境内的大量微型传感器节点通过无线通信方式组成的一种无线网络。

组成传感器网络的节点包括传感器和汇聚节点(Sink)。传感器节点的能量十分有限，并且在部署后难以再次补充能量，因此传感器网络存在严重的能量约束问题[1]。

参考文献[2]提出一种无线传感器网络AODV(AdhocOn-DernandDistanceVector)路由协议改进方案，通过改进RREQ协议帧，使节点的剩余能量值参与到路径中，优化RREQ洪泛传播。但该算法是基于单路径数据传输，没有考虑节点的负载状况，节点容易产生拥塞，导致数据包的重传或数据丢失的情况。

参考文献[3]提出了一种基于蚁群优化的路由算法ARAWSN(ACO-BasedRoutingAlgorithmforWirelessSensorNetworks)，该算法在定向扩散协议的基础上，通过搜寻蚂蚁以广播的方式在网络中扩散建立起源节点到目的节点的多条路径的路由表。

利用蚁群算法的转移概率的方式来进行路径的选择，从而平衡网络中节点能量的消耗。该算法建立了所有到目的节点的路径，存在很大的冗余，影响网络的实时性，且在路由建立过程中采用洪泛的方式导致网络的路由开销比较大。

参考文献[4]综合考虑了均衡传输能量消耗和节点剩余能量，提出了多种群蚁群优化路由算法MACO(MultiAntColonyOptimization)。该算法优化了基本蚁群算法的蚂蚁前向移动的选择概率模型，同时利用多种群获得多条优化路径。但该算法需要进行多次迭代，且可能陷入局部最优解，影响网络数据传输的实时性。

针对上述路由算法及其存在的不足，本文提出了基于蚁群算法的无线传感器网络按需多路节能路由算法MP-ACA(On-demandMulti-pathandPower-savingAntColonyAlgorithm)。该算法结合蚁群算法和AODV路由协议，能够在源节点和目的节点之间建立起多条链路不相关路由，并改善了蚁群算法在无线传感器网络中查找路由的多次迭代的策略，有效地减少了拥塞频率、降低了路由的开销，同时均衡了节点的能量开销，延长了网络的生命周期。

1 蚁群算法简介

1.1 基本蚁群算法原理

蚁群算法[5]ACA(AntColonyAlgorithm)是一种模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法，其基本原理可大致描述如下:自然界蚂蚁会在所经过的路径上释放一定的信息素，后来的蚂蚁会根据信息素强度来选择路径，信息素强度越大的路径被选择的概率越大，于是就形成了一种正反馈机制，最终蚂蚁会选择信息素最大的最短路径。蚁群算法通过释放“人工蚂蚁”来模拟自然蚂蚁的行为以完成上述的选优过程。

1.2 蚁群算法

根据蚂蚁觅食的基本原理，科学家们设计了寻找最优路径的蚁群算法，其主要步骤为：

2 按需多路节能路由算法设计

针对无线传感器网络数据多跳传输、节点能量有限等特性，本文对基本蚁群算法和MACO算法进行改进，并结合AODV路由协议，赋予蚂蚁新的特性和路径搜索方式。下面介绍本文研究中使用的相关定义。

定义1：从源节点到目的节点的路径搜索蚂蚁称作前向蚂蚁，它执行路径搜索功能，并建立反向信息素表。

定义2：前向蚂蚁到达目的节点后，从目的节点返回到源节点的蚂蚁称作后向蚂蚁，它执行信息素更新功能，并建立路由表。

定义3：前向蚂蚁在路径搜索过程中，到达某一节点后建立的指向源节点的路由表称作反向信息素表，该表包括源节点、下一个节点、反向节点信息素τ(j，i)。

2.1 算法设计思想

MP-ACA算法在Ant-Net算法[6]的基础上，将蚂蚁分为前向蚂蚁和后向蚂蚁。为了实现不同节点的能量消耗均衡，MP-ACA算法中，将前向蚂蚁要访问的节点的剩余能量作为影响信息素浓度的一个参数。MP-ACA算法通过m只前向蚂蚁同时独立地进行路径搜索，并建立反向信息素表。

当每个前向蚂蚁到达目的节点时，它们将立即转化成一个后向蚂蚁，后向蚂蚁根据反向信息素表反向回到源节点后一次路由建立完毕，建立起信息素路由表以代替传统的网络节点路由表，并采用一种新的信息素规则进行信息素更新。

同时MP-ACA算法在极大-极小蚁群算法[7]上将各条路径上的信息素浓度限制在[τmin，τmax]之间，τmin可以有效地避免算法停滞，τmax避免某条路径上的信息素远大于其他路径，使所有的蚂蚁都集中到同一条路径上面，限制算法的扩散。在MP-ACA算法中，前向蚂蚁转移规则、信息素更新规则详细设计如下。