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

 

　　电系统（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算法中，将前向蚂蚁要访问的节点的剩余能量作为影响信息素浓度的一个参数。MP-ACA算法通过m只前向蚂蚁同时独立地进行路径搜索，并建立反向信息素表。当每个前向蚂蚁到达目的节点时，它们将立即转化成一个后向蚂蚁，后向蚂蚁根据反向信息素表反向回到源节点后路由建立完毕，建立起信息素路由表以代替传统的网络节点路由表，并采用一种新的信息素规则进行信息素更新。同时MP-ACA算法在极大-极小蚁群算法上将各条路径上的信息素浓度限制在[τ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蚁群算法的实现

　　下面的程序开始运行之后，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着屏幕爬满整个画面，直到找到食物再返回窝。

　　其中，‘F’点表示食物，‘H’表示窝，白色块表示障碍物，‘+’就是蚂蚁了。

　　参数说明：

　　信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。

　　错误概率表示这个蚂蚁不往信息素的区域走的概率，越大则表示这个蚂蚁越有创新性。

　　速度半径表示蚂蚁能走的长度，也表示这个蚂蚁的感知范围。

　　记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。

　　2.3 信息素更新规则

　　如果节点i，j是前向蚂蚁k选择路径上的相邻节点，当每个前向蚂蚁到达目的节点时，它们将通过式（5）、式（6）来调节。对前向蚂蚁到达目的节点后立即转化成一个后向蚂蚁，并且它将沿着反向信息素表回到源节点。中间节点收到后向蚂蚁时，将按照式（5）、式（7）更新相邻节点信息素强度。

　　MP-ACA算法改进了MACO算法信息素更新规则，可以加快搜索路径的速度，提高网络数据传输的实时性，同时更进一步平衡了网络节点的能量消耗。

　　2.4 MP-ACA算法步骤

　　（1）初始化时，Sink节点跳数设置为0，其他节点跳数设置为100。Sink节点在全网范围内广播跳数广播报文，该报文包括数据包类型、距Sink节点跳数、剩余能量和源地址。该报文初始值为：跳数为0，源地址为0。中间节点收到该报文后，保存报文中节点的地址、跳数和能量状态。如果收到的报文中跳数小于节点自身的跳数，则将自身的跳数设置为报文中的跳数加1，并转发自己新的跳数信息和能量信息的报文，否则不广播。 节点在转发该报文的过程中收集、存储邻居节点相关信息，终在全网内建立了到Sink节点的跳数信息。

　　（2）路径搜索初始时，赋予每条路径上相等数量的初始信息素τ0，本文设置为信息素浓度下限τmin。

　　（3）路径搜索开始时，m只前向蚂蚁从源节点S处出发，前向蚂蚁所要携带的信息有：源节点ID号、目的节点ID号、节点i到节点j的信息素强度τ（i，j）、经过节点的剩余能量的总和以及当前总跳数。

　　（4）位于节点i的前向蚂蚁k，依据转移规则从相邻的下一跳节点集合中选择一个节点，并根据式（5）、式（6）更新路径上信息素强度。

　　（5）当中间节点j收到来自邻居节点的蚂蚁节点时：①更新前向蚂蚁搜索包跳数h（i）=h（i）+1，i∈[1，m]。如果前向蚂蚁没有到达目的节点，且h<hmax，则转入下一步，否则丢弃该数据包；②检查自己是否比节点i距离目的节点更近，且距离源节点更远。若是，转入下一步，否则简单丢弃；③然后检查是否已收到同一目的节点前向蚂蚁搜索包。若是，则此节点只接收早到达而且信息素的前向蚂蚁搜索包，将其余的丢弃。当前向蚂蚁从节点i到达节点j后，根据前向蚂蚁所携带的信息值建立到源节点的反向点信息素表，跳转到第（4）步。

　　（6）当每个前向蚂蚁到达目的节点时，它们将立即转化成一个后向蚂蚁，并且它将沿着反向信息素表回到源节点。中间节点收到后向蚂蚁数据包时，按照式（5）、式（7）将更新相邻节点信息素强度，并建立到目的节点的路由表，路由表是一个三元组包括：目的节点、下一个节点、信息素。

　　（7）后向蚂蚁到达源节点后路由建立完毕。

　　2.5 网络的维护

　　在无线传感器网络中，节点的故障和能量的耗尽都将导致网络拓扑结构的变化，这使得路由维护显得十分重要。路由断路和节点能量的消耗是路由维护中必须解决的两个关键问题。

　　（1）路由断路。当中间节点发现路径不通或收到路由断路的消息后，它首先根据断路的路径信息删除自己对应的路由表条目，然后查询可能性路由表条目，看是否能找到到达同一目的地的其他路径。如果有，则根据路由表中信息素的条目作为的路径进行通信；如果没有到达对应目的地的可选路径后，即向其他节点继续发送路由断路消息。当源节点在通信完成前收到路由断路消息后，如果没有到目的地的其他路径，则将发起新的路径探索过程，直到通信完成。

　　（2）节点能量的消耗。为了不频繁地重建路由表，节省能量，MP-ACA算法根据每个节电的剩余能量自动更新路由表，这样就使得节点的能耗尽可能保持平衡。节点能量每下降10%，节点就会向周围节点广播自己的剩余能量，收到广播的节点用式（8）更新路由表：

 

　　3.1 接收到数据包的平均延时

　　图1反映了三种算法网络传输数据的平均传输延时随时间的变化关系。由图可知，各算法的时延呈现先降后增的趋势，主要是由于网络刚建立时，节点需要建立路由表，然后时延呈下降趋势。网络运行一段时间后，由于网络中部分节点死亡，导致路由的重建，致使时延呈上升趋势。总的来说，MP-ACA的平均传输延时要小于MACO和ACA的平均传输延迟，主要是因为在MACO和ACA其路由是通过多次迭代而建立起来的，需要的时间长，从而增加了网络延时。

　　3.2 能量不为零的节点数目

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

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