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

宋 杰，吴 勇，陈明明

（安徽大学 计算机科学与技术学院，安徽 合肥 230601）

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

宋 杰，吴 勇，陈明明

（安徽大学 计算机科学与技术学院，安徽 合肥 230601）

无线传感器网络是一种能量、资源受限的网路系统，实现网络中节点能量使用均衡延长整个网络的生命周期是无线传感器网络路由设计的重要目标.本文在基本蚁群算法在无线传感器网络应用的基础之上提出了几点改进策略.将节点现有的能量水平作为计算转移概率的条件之一，使优秀路径上的节点在网络中存在的时间更长.将节点的位置信息作为计算转移概率的条件，通过将位置信息写入转移概率中，使节点在搜索路径时具有方向性.最后本文利用MATLAB工具对改进的策略进行了实验仿真，并将结果和原始的ACO算法进行比较分析，仿真结果显示改进策略在延长节点的生命周期，维持网络能量均衡方面比其他俩种算法具有一定的提升.

无线传感器网络；蚁群算法；能量均衡；路由协议

1 引言

随着传感技术、无线通信技术和嵌入式技术的不断发展成熟，无线传感器网络逐渐成为当今社会的研究热点.它强大的感知能力、自组织能力、部署方式简单方便的特点决定了在很多领域都有广阔的应用前景［1，2］.由于无线传感器网络中节点的能量受限，将传统的网络协议应用到无线传感器路中不太现实.近年来，许多学者对无线传感器网络路由做出了大量的研究［3］.

无线传感网最初的雏形是起源于上个世纪70年代，当时的技术仅处于初始的研制阶段，此时的网络采用点对点的传输，而且传感器节点只具有简单的数据获取能力.80年代左右，无线传感网技术己经慢慢发展起来，该网络采用串/并口方式与控制中心相连，并且传感器节点具有了获取各种不同信息的能力.到了20世纪的末期，由于其他学科技术的综合发展，使得无线传感网技术也有了更好的发展，该技术采用总线连接方式代替了串/并口方式，形成了真正意义上的无线局域网络21世纪，无线传感网作为多学科交叉的新兴技术研究领域，被世界各个国家高度关注，给军事方面、学术和工业界等带来了巨大反响.然而由于传感器一般由电池供应电能，而且分布的环境可能比较恶劣.经常更换电池不太现实，因此传感器的能源供应成为制约无线传感器网络发展的一个重要的因素.由于传感器能量主要消耗在数据的发送过程中，因此减少数据传输过程中发送次数、平衡整个网络中传感器的能量成为人们研究的热点.研究无线传感器网络路由算法起于1990年以后，如今这一课题的科研很有活力，不论国内还是国外相关的科研工作人员付出了很多的努力.无线传感器网络拓扑结构易变，并且使用有限能量的电池供电.这些特征使得传统的路由算法机制无法再用于无线传感器网络，所以要研究设计新的路由算法.目前越来越多的学者和科研机构投入到无线传感器网络路由算法的研究中来，使得这项研究成为当今的热点领域.路由算法越来越复杂，其性能越来越高，能满足更高层次的质量需求.同时越来越多的智能算法的引入使无线传感器网络路由算法更加高效、可靠，性能有了显著的提高，使之成为目前研究的重点.其中蚁群算法在无线传感器网络路由算法中得到了广泛的研究.

2 无线传感器网络的耗能分析

根据大量研究表明无线传感器网络中节点的能量消耗主要分为三个部分：数据采集（即感知环境）耗能、数据融合耗能、通信耗能［6］.由于通信耗能在三部分耗能中占据绝大部分，所以在试验中只考虑了节点间通信耗能.本文采用的能量消耗模型为：

图2.1 能量消耗模型

具体的计算公式如下：

（1）节点发送数据的能量消耗公式为：

从2-1可以看出当节点节点间的距离大于阈值时，发送数据的耗能将大大的增加.

（2）节点接收数据的能量消耗计算公式为：

3 改进策略

3.1 将节点的位置作为影响转移概率的因素之一

当邻居节点的转移概率相近，或者转移概率最大的节点远离汇聚节点时，会增加传输路径的长度，增加了耗能.将节点相对于汇聚节点的位置信息作为计算转移概率的条件之一.转移函数可变为：

其中τij（t）为t时刻节点i到节点j路径上的信息素浓度；ηij（t）为t时刻节点i到几点j之间路径启发信息；其中ηij=1/dij即启发信息是俩节点之间距离的倒数；μj是节点位置对路径的启发信息，其中μj=1/dj，dj表示节点j到汇聚节点的距离.α、β、λ是调节因子，分别反映了信息素对蚂蚁转移概率的影响、节点间距离对蚂蚁转移概率的影响、节点到汇聚节点间的距离对蚂蚁转移概率的影响.可以看出当下一跳节点和汇聚节点的距离大时转移概率函数p相对变小，蚂蚁选择该节点的概率变小.

3.2 将节点剩余能量作为影响转移概率的因素之一

无线传感器网络是由多个传感器节点自组织形成的，每个节点的在网络的寿命，直接关系到整个网络的生命周期.将节点的剩余能量作为影响转移概率的因素显得十分必要.可以将转移概率函数设计为：

其中τij（t）为t时刻节点i到节点j路径上的信息素浓度；ηij（t）为t时刻节点i到几点j之间路径启发信息；其中ηij= 1/dij即启发信息是俩节点之间距离的倒数；

3.3 抑制信息素的增长

蚂蚁搜索出最优路径后，由于蚂蚁的正反馈机制该条路径上的信息素含量将会进一步的提高.这样全网中较优秀的路径上的节点能量很容易耗尽，降低了整个网络的生命周期.本文采用蚂蚁携带抑制信息的方法来解决上述问题.即当蚂蚁在节点i的候选节点集合中选择j为最优路径后，该路径上的信息素适度的降低.

3.4 路径信息素的更新

每当完成一轮路径选择后，对所有蚂蚁走过的路径上的信息素按照以下规则进行更新.

式中τij（t+n）表示t+n时刻节点i和节点j之间路径上的信息素含量；ρ表示整个网络路径中信息素的衰减因素；Δτij（t）表示本轮计算中m个蚂蚁对节点i和节点j之间路径上的信息素含量的抑制.其中

4 仿真分析

本文的仿真环境为MATLAB.仿真系统模型为：在面积大小为200*200的空间内随机的部署200个感知点，负责感知信息和接收、发送数据包.汇聚节点设置在感知区域的边沿，坐标为（0，0）.采用TSP标准库中的实例来布置场景，平面区域中的节点有的分布是均匀的有的分布是不均匀的.为了更好的进行试验，做出以下假设：（1）传感器节点的是不可以移动的.（2）所有的传感器具有唯一的标志ID，并且可以感知自己的坐标.（3）除汇聚节点外传感器节点的能量受限、初始能量相同，并且可以感知.

4.1 评价指标

本文提出的改进策略旨在实现无线传感器网络的能量均衡.仿真实验主要考察节点的能量消耗、网络的生命周期、路径长度等方面考察了改进策略的有效性.

4.1.1 节点的能量消耗

无线传感器网络需要将检测区域采集到的数据经过一定融合，传送到汇聚节点.为了延长整个网络的生命周期需要减少网络中所有节点的能耗，并且保证所有节点的能量使用的均衡.如果一些节点的网络任务过重，将会使这些节点过早的退出网络.不利于网络能源的均衡利用，可能降低网络的生命周期.

4.1.2 网络的生命周期

网络生命周期的长短是衡量无线传感器网络路由协议的重要指标之一.

4.1.3 路径长度

由于无线传感器网络中节点能耗主要体现在节点间的通信方面.而发送数据的能量消耗和节点间的距离是呈现出指数型关系.因此，降低传输路径长度降低网络能量消耗的重要手段.

4.2 路径长度

从上文的无线通信能量模型中我们可以看出无线通信能耗主要体现在节点间的通信方面.而发送数据的能量消耗和节点间的距离是呈现出指数型关系.降低传输路径长度降低网络能量消耗的重要手段.在依次仿真试验中选取某个节点作为源节点，通过蚁群算法和改进的算法搜索路径.得到的数据如图所示：

图4.1 一次搜索路径示意图

从上图4.1中可以看出原始的蚁群算法在搜索最优路径过程中经历了10跳，而改进的算法在搜索最优路径的过程中经历了8跳.俩种算法都经过了编号为89的节点，由于改进的算法引用了节点的位置信息，下一跳节点选择为编号为60的节点，原始的蚁群算法从邻居节点中选取转移概率最大的编号为198的节点.明显的增加了整体的路径长度.因此，可以看出改进的算法在降低传输路径长度方面有一定的提升.

4.3 能量消耗情况

改进策略的初衷是降低网络整体的耗能、均衡网络的消耗实现无线传感器网络生命周期的延长.本实验迭代100次，俩算法下的网络能耗如下所示：

图4.2 能量消耗展示图

从图4.2中可以看出，俩种算法随着网络使用时间的增加网络整体的能耗趋于平衡，改进的策略和原始蚁群算法相比较在能耗方面有一定的优势.在网络开始阶段，由于网络上各个路径上的信息素相等，传统蚁群算法在转移概率相等时随机的选择邻居节点集合中的一个节点作为下一跳，改进策略将节点的位置信息作为转移概率计算的参数之一，使搜索路径具有方向性.这样改进策略在开始阶段的路径长度很可能小于原始的蚁群算法.在图4.2中可以看出在开始阶段改进策略的能耗明显小于原始算法.随着网络使用时间的增加，每个节点的能量差开始体现出来，位置信息对搜索路径的影响降低.因此，从图中可以看出，在稳定阶段二者的能耗差距不是非常的明显.

4.4 网络的生命周期

无线传感器网络的生命周期直观的体现是网络中存活节点的个数.无线传感器网路中每个节点的传输能力有限，需要多个节点多跳的方式将数据传送到汇聚节点.当网络中存活节点的个数低于一定数量时，网络趋于瘫痪，不能够进行正常的采集传输工作.

图4.3

从图4.3中可以看出在开始阶段，不考率人为的破坏的情况下传感器节点的数量是不降低的，随着使用时间的增加，当出现节点退出网络时，网络存活节点数量随着时间的推移急速下降.由于将节点的能量水平作为计算转移概率的因素之一，从图4.3中可以看出改进策略对网络中优秀路径中的节点起到了很大的保护作用，改进策略出现死亡节点的时间明显滞后于原始算法.

5 结束语

通过阅读大量的文献，本文在原有的蚁群算法基础之上提出了几点改进策略旨在实现网络的能量均衡，延长网络的生命周期.同过和原有的蚁群算法相比较可以看出本文提出的算法有效地降低了网路中的路径长度，在提升网络生命周期方面有一定的优势.

〔1〕孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005，3～23.

〔2〕Bonnet P，Gehrke J，Seshadri P. Querying the physical world ［J］. IEEE Personal Communication，2000，7（5）：10-15.

〔3〕刘志.无线传感器网络中的能量高效覆盖与路由算法研究［D］.北京：北京交通大学，2011.

〔4〕唐勇，周明天，张欣.无线传感器网络路由协议研究进展［J］.软件学报，2006，17（3）：410-421.

〔5〕Hedetniemi S.M.，HedetniemiS.T.， Liestman A.L.. A survey of gossiping and broadcasting in communication networks［J］.Networks，1988，18（4）：319-349.

〔6〕谢耀华.基于蚁群算法的无线传感器网络路由算法研究及实现.西安电子科技大学，2013.3.

TP393

A

1673-260X（2015）05-0013-03