蚁群算法在无线传感器网络能量均衡中的应用

摘 要

针对无线传感器网络的节点能量消耗不均衡，避免部分节点过早死亡而引起整个网络死亡的问题，提出一种改进后的蚁群算法，算法能有效的帮助源节点选择合适的下一跳节点，建立其高效路由，从而改进了能耗不均衡现象，延长网络寿命。

【关键词】无线传感器网络 能量 蚁群算法

近些年来，一个融合了传感器技术、无线通信技术、微电子技术、嵌入式系统、和分布式信息处理等诸多技术为一体的新型微型智能网络无线传感器网络应运而生，无线传感器网络作为一个新兴的研究领域，当前备受关注，成为各大公司和科研机构的研究热点。

1 无线传感器网络

无线传感器网络是由大量分布在监测区域的微型智能传感器节点通过无线自组形式构成的网络，它们之间通过协作感知、监测、实时采集无线传感器网络覆盖区域中感知对象的信息，并进行一定的加工处理，最后发送给需要的用户。同时用户还可以通过网络终端设备以及监控软件来监测网络的实时状况，并可对该网络中的所有节点进行监控管理。

无线传感器网络是由大量的传感器节点组成，每个节点对其周围环境进行感知（信息采集），然后通过一跳或者多跳的方式将感知到的数据传给汇聚节点（即Sink节点），汇聚节点在通过有线或者无线网络（如卫星）传给监测者，供其使用，其网络结构图如图1所示。

一般的传感器节点通常由四大部分组成：传感单元、数据处理单元、无线收发单元以及供电单元。传感器单元包含传感器和AD（数模转换器），主要负责对监测环境的数据采集和数据信号转换，数据处理单元包含处理器和存储器，主要是对数据进行处理和数据存储，无线收发单元主要进行数据发送（转发）和接受，供电单元为整个模块工作提供能量，一般来说，为节点提供的电能是有限的。典型的无线传感器网络节点的结构如图2。

跟传统的无线网络不同，无线传感器网络是一种能量有限的网络，且通常能量不可补充，所以保证网络工作正常的前提下，如何节省能量、高效利用能量是成了研究无线传感器网络的热点。

大量的研究表明，在无线传感器网络中，数据的接受与发送在占传感器能量消耗的绝大部分。 而随着时间的推进，当传感器剩余的能量再无法进行数据的收发后，这个节点就无法正常工作，宣布死亡。当大量节点死亡后，整个传感器网络就无法再进行监测任务了。在传感器网络中，每个节点由于地理位置的不同和距离汇聚节点（目标节点）的距离不通，所消耗的能量也不相同，这样会导致能量消耗快的节点就死亡的快，而它们死亡后其周围节点由于它们的死亡将会承担更多的数据转发任务，如此一来，也加速了周围节点的死亡，从而加速了整个网络的死亡，降低了网络寿命。

2 蚁群算法

蚁群算法是一种生物仿生算法，生物学家通过观察发现，蚁群总能找到食物和蚁穴之间的路径，并且随着时间的推移，蚂蚁总能找出食物和蚁穴之间的较短的路径，后续的蚂蚁不断加强这条路径，而单个蚂蚁却不能完成这个任务。后来研究发现，蚂蚁之所以能从中找出最短路径，并且让后续蚂蚁重复这条路径，是因为蚂蚁自身带有一种称为“信息素”的物质，这种物质具有挥发性，能够被其它蚂蚁识别，并且能影响蚂蚁对路径进行选择。

假设蚁穴和食物之间有若干条路线，蚂蚁从蚁穴出发后会随机选择路线，在所有到达食物的路线中，有线路线较长，有些路线较短，蚂蚁以相同的速率同时向食物出发，相同的时间内，选择短路线的蚂蚁会往返的次数较多，而较长路径的蚂蚁往返的次数较少，从而在较短路径上蚂蚁释放的“信息素”浓度就越高，而较长路径的上的“信息素”浓度较低，而蚂蚁在路径的选择上往往会偏向于“信息素”浓度高的路径。由于“信息素”具有挥发性，它也会以一定速率进行挥发，这样也有利于避免路径选择时陷入局部最优的情况。

蚁群模型描述：将若干只蚂蚁分别放在不同的城市中，蚂蚁按照一定的规则对所有的城市访问，直到遍历完所有的城市，遍历完所有城市后更新所经过路径的信息素浓度，最后从所有的遍历路径中找出一条最短的回路。

蚁群算法的路径转移：假设有m只蚂蚁被随机放在n（m≤n）个城市中，t时刻蚂蚁k（k=1，2，…，m）从某个城市出发后，选择下一个目标城市的概率是，的公式如下

式（3-1）

从公式中可以看出，的大小主要取决和，表示时刻t城市i到城市j路径上蚂蚁释放的信息素浓度，它在初始时刻t=0时，它的浓度为常数C（C=0），α表示信息素浓度在整个路径选择中所占的权重参数。表示城市i到城市j的启发式知识，它与实际的问题相关，例如在旅行商问题中，可以设ηij=1/dij，dij表示城市i和j之间的距离，β表示启发因子在路径转移计算中的权重参数，另外，为了避免蚂蚁重复造访已经访问过的城市，每只蚂蚁存放有一个路径表forbidk，这个表用来记录已经遍历过的城市。

信息素更新：

每只蚂蚁在遍历完所有城市后，会在所有经过的路径上释放信息素，蚂蚁之间正是通过信息素来传递信息的，信息素具有挥发性，它们以一定的速度挥发，这样也避免路线上残留的信息素的无限递增淹没了启发式对路径选择的影响。在经过一次循环后，时刻为t=t+1时，信息素进行了更新，其更新规则如下：

式（3-2）

在上述表达式3-2中，表示t时刻路径（i，j）中的信息素残留，ρ表示信息素挥发速率百分比，取值通常在（0，1）之间，即0<ρ<1， 表示所有m只蚂蚁在完成当次遍历后在路径（i，j）上释放的信息素总量。表示蚂蚁k在完成当次遍历后在路径（i，j）上释放的信息素。

在无线传感器网络中，在每一个传感器节点中放入一个人工蚂蚁，它具有自然蚂蚁的基本特性，同时还具备一定的存储能力，用于对路径信息的存储。每一只蚂蚁都能够找到一条“合适”的路径。为延长传感器网络的寿命，既要考虑节点能量消耗，又要考虑能耗均衡。而节点传输数据的能耗与节点传输距离紧密相关，而能量均衡则要求，节点在选择下一跳路径时必须考虑下一跳节点的剩余能量，所以对传感器节点下一跳节点的选择做适当改进，人工蚂蚁选择下一跳节点的计算公式：

式（3-3）

上式中，Eit表示在t时刻节点i的剩余能量，E0表示的是传感器节点的初始能量。

源节点在蚁群算法的指导下择优选出下一跳节点，直到将信息传送到汇聚节点，完成整个数据的传送过程。

仿真实验表明，采用改进的蚁群算法后，节点能量消耗比经典的Leach分簇算法更均衡。无论是首个节点的死亡时间、半数节点死亡时间还是绝大部分节点死亡都比Leach算法更晚，因而其网络寿命更长久。

参考文献

[1]常薇，刘才兴.基于多态蚁群算法的WSN能耗均衡路由协议[J].计算机工程，2010，36（7）：87-92.

[2]方育奇，左宪章.无线传感器网络中基于蚁群的簇间路由算法研究[J].计算机测量与控制，2010，18（5）：76-78.

[3]陈友荣，俞立.基于蚁群的无线传感网最大化生存时间路由[J].计算机应用，2011，31（11）：28-29.

[4]赵凌.基于PEGASIS算法的无线传感器网络路由算法的研究[D].重庆：重庆理工大学，2009.

作者单位

湖南文理学院计算机学院 湖南省常德市 415000