一种无线传感器网络路由算法基于蚁群算法区域

一种无线传感器络路由算法基于蚁群算法

电系统（Micro-Electro-Mechanism System, MEMS）、片上系统（SOC， SySTem ON Chip）、无线通信和低功耗嵌入式技术的飞速发展，孕育出无线传感器络（Wireless Sensor Networks, WSN），并以其低功耗、低成本、分布式和自组织的特点带来了信息感知的一场变革。无线传感器络就是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织络。

随着无线通信技术、电子技术、传感器技术和微电系统的飞速发展，无线传感器络的研究越来越受到人们的重视。传感器络是由部署在观测环境内的大量微型传感器节点通过无线通信方式组成的一种无线络。组成传感器络的节点包括传感器和汇聚节点（Sink）。传感器节点的能量十分有限，并且在部署后难以再次补充能量，因此传感器络存在严重的能量约束问题。

参考文献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 蚁群算法简介

蚁群算法（ant colony optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

1.1 基本蚁群算法原理

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

1.2 蚁群算法

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

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

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

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

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

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

2.1 算法设计思想

MP-ACA算法在Ant-Net算法的基础上，将蚂蚁分为前向蚂蚁和后向蚂蚁。为了实现不同节点的能量消耗均衡，MP-ACA算法

式中，W（ j）是节点j的剩余能量；JK（i）代表了位于节点i的前向蚂蚁k允许访问的邻居节点集合。在这里定义满足以下两个要求的节点j将会属于JK（i）：（1）节点

3.2 能量不为零的节点数目

图2反映了三种算法在整个络时间内能量不为零的节点数目随时间的变化关系。由图可知，节点一直运行到110 s的时候，三种算法下有效的节点数目都为总的节点数目，但随着时间的推移，由于ACA算法没有考虑到节点剩余能量的情况，造成了某些节点耗能不均衡而过早的能量耗尽。

蚁群算法作为一种新的仿生优化算法，具有分布计算、信息正反馈和启发式搜索等特点。本文在对现有无线传感器络蚁群改进路由算法的基础上，改进了现有路由算法路径搜索方式，很好地权衡了路由收敛速度与络生命周期的相互制约关系。同时将其应用在无线传感器络中进行路由选择，对于提高无线传感器络的络效率、延长络的生存周期具有很高的应用价值。

来源:阴雨