摘 要： 提出一种基于蚁群算法的无线传感器网络按需多路节能路由算法。该算法综合了蚁群优化算法和AODV路由协议的思想，通过蚂蚁并行地在源节点和目的节点之间建立多路径路由，提高了网络数据传输的实时性、延长了整个网络的生命期。仿真结果表明，该算法与多种群蚁群优化路由算法、基本蚁群算法相比，在整个网络的生命期和节能方面效果显著。关键词： 无线传感器网络；路由；蚁群算法；多路节能 随着无线通信技术、电子技术、传感
摘 要：提出一种基于蚁群算法的无线传感器网络按需多路节能路由算法。该算法综合了蚁群优化算法和AODV路由协议的思想，通过蚂蚁并行地在源节点和目的节点之间建立多路径路由，提高了网络数据传输的实时性、延长了整个网络的生命期。仿真结果表明，该算法与多种群蚁群优化路由算法、基本蚁群算法相比，在整个网络的生命期和节能方面效果显著。
关键词：无线传感器网络；路由；蚁群算法；多路节能
随着无线通信技术、电子技术、传感器技术和微电系统的飞速发展，无线传感器网络的研究越来越受到人们的重视。传感器网络是由部署在观测环境内的大量微型传感器节点通过无线通信方式组成的一种无线网络。组成传感器网络的节点包括传感器和汇聚节点(Sink)。传感器节点的能量十分有限，并且在部署后难以再次补充能量，因此传感器网络存在严重的能量约束问题[1]。
参考文献[2]提出一种无线传感器网络AODV(Ad hoc On-Dernand Distance Vector)路由协议改进方案，通过改进RREQ协议帧，使节点的剩余能量值参与到路径中，优化RREQ洪泛传播。但该算法是基于单路径数据传输，没有考虑节点的负载状况，节点容易产生拥塞，导致数据包的重传或数据丢失的情况。参考文献[3]提出了一种基于蚁群优化的路由算法ARAWSN(ACO-Based Routing Algorithm for Wireless Sensor Networks)，该算法在定向扩散协议的基础上，通过搜寻蚂蚁以广播的方式在网络中扩散建立起源节点到目的节点的多条路径的路由表。利用蚁群算法的转移概率的方式来进行路径的选择，从而平衡网络中节点能量的消耗。该算法建立了所有到目的节点的路径，存在很大的冗余，影响网络的实时性，且在路由建立过程中采用洪泛的方式导致网络的路由开销比较大。参考文献[4]综合考虑了均衡传输能量消耗和节点剩余能量，提出了多种群蚁群优化路由算法MACO(Multi Ant Colony Optimization)。该算法优化了基本蚁群算法的蚂蚁前向移动的选择概率模型，同时利用多种群获得多条优化路径。但该算法需要进行多次迭代，且可能陷入局部最优解，影响网络数据传输的实时性。
针对上述路由算法及其存在的不足，本文提出了基于蚁群算法的无线传感器网络按需多路节能路由算法MP-ACA(On-demand Multi-path and Power-saving Ant Colony Algorithm)。该算法结合蚁群算法和AODV路由协议，能够在源节点和目的节点之间建立起多条链路不相关路由，并改善了蚁群算法在无线传感器网络中查找路由的多次迭代的策略，有效地减少了拥塞频率、降低了路由的开销，同时均衡了节点的能量开销，延长了网络的生命周期。
1 蚁群算法简介
1.1 基本蚁群算法原理
蚁群算法[5]ACA(Ant Colony Algorithm)是一种模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法，其基本原理可大致描述如下:自然界蚂蚁会在所经过的路径上释放一定的信息素，后来的蚂蚁会根据信息素强度来选择路径，信息素强度越大的路径被选择的概率越大，于是就形成了一种正反馈机制，最终蚂蚁会选择信息素最大的最短路径。蚁群算法通过释放“人工蚂蚁”来模拟自然蚂蚁的行为以完成上述的选优过程。
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算法中，前向蚂蚁转移规则、信息素更新规则详细设计如下。
2.2 前向蚂蚁转移规则
为了均衡网络中节点的能量消耗，MP-ACA算法在蚁群算法的基础上，新加入两节点间的剩余能量因子改进前向蚂蚁转移规则。改进后的算法在蚂蚁寻找最短路径的同时受到了节点能量消耗的限制。MP-ACA算法中处于节点i的蚂蚁k选择下一节点j进行访问的概率pkij使用以下公式确定：
式中，W( j)是节点j的剩余能量；JK(i)代表了位于节点i的前向蚂蚁k允许访问的邻居节点集合。在这里定义满足以下两个要求的节点j将会属于JK(i):(1)节点j还未被蚂蚁k访问；(2)节点j比前一节点i距离目的节点更近，且距离源节点更远。
MP-ACA算法采用改进的转移规则，简化了MACO算法使得MP-ACA更适用于无线传感器网络。同时前向蚂蚁在寻找路径的同时受到了节点能量消耗的限制，平衡了节点的能量消耗。
2.3 信息素更新规则
如果节点i，j是前向蚂蚁k选择路径上的相邻节点，当每个前向蚂蚁到达目的节点时，它们将通过式(5)、式(6)来调节。对前向蚂蚁到达目的节点后立即转化成一个后向蚂蚁，并且它将沿着反向信息素表回到源节点。中间节点收到后向蚂蚁时，将按照式(5)、式(7)更新相邻节点信息素强度。
MP-ACA算法改进了MACO算法信息素更新规则，可以加快搜索路径的速度，提高网络数据传输的实时性，同时更进一步平衡了网络节点的能量消耗。
2.4 MP-ACA算法步骤
(1)初始化时，Sink节点跳数设置为0，其他节点跳数设置为100。Sink节点在全网范围内广播跳数广播报文，该报文包括数据包类型、距Sink节点跳数、剩余能量和源地址。该报文初始值为：跳数为0，源地址为0。中间节点收到该报文后，保存报文中节点的地址、跳数和能量状态
