Computer Science and Application
Vol.05 No.10(2015), Article ID:16276,6 pages
10.12677/CSA.2015.510045

Overview of Wireless Sensor Network Routing Protocol Based on Ant Colony Algorithm

Jinrui Ma1, Zhansheng Chen1,2*

1School of Applied and Technology, Beijing Union University, Beijing

2School of Computer and Information Technology, Beijing Jiaotong University, Beijing

Email: *ldtchenzs@buu.edu.cn

Received: Oct. 8th, 2015; accepted: Oct. 26th, 2015; published: Oct. 30th, 2015

Copyright © 2015 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

This paper briefly introduces the characteristics of the wireless sensor network, the principle and characteristics of the basic ant colony algorithm, and summarizes the application of ant colony algorithm in the traveling salesman problem. Then, it focuses on how to improve the ant colony algorithm and apply it to the wireless sensor network, and points out the comparative performance of the WSNs routing protocol based on the improved ant colony algorithm.

Keywords:Wireless Sensor Network, Ant Colony Algorithm, Routing Protocol

基于蚁群算法的无线传感器网络路由协议综述

马金锐1,陈战胜1,2*

1北京联合大学应用科技学院,北京

2北京交通大学计算机与信息技术学院,北京

Email: *ldtchenzs@buu.edu.cn

收稿日期:2015年10月8日;录用日期:2015年10月26日;发布日期:2015年10月30日

摘 要

本文简要介绍了无线传感器网络的特点,引出并归纳了基本蚁群算法的原理及特点,并总结了蚁群算法在旅行商问题中的应用。然后,重点介绍了目前部分研究学者如何改进蚁群算法并应用于无线传感器网络,指出业界在基于改进蚁群算法的WSNs路由协议的对比性能指标和研究方向。

关键词 :无线传感器网络,蚁群算法,路由协议

1. 引言

无线传感网络(Wireless Sensor Networks, WSNs)是一种由大量微型传感器节点构成的分布式网络系统,节点分为传感节点、汇聚节点和管理节点。WSNs通常应用于恶劣环境,多是人无法抵达的区域,传感节点通常采用随机散播方式部署,节点与节点之间通过无线通信交换彼此信息以发现和维护路由,组成统一的网络。其中,网络层路由协议是WSNs通信的基础,是WSNs网络可靠、有效传输的关键。此外,需要考虑节点加入、移动和死亡引起的网络拓扑变化,会影响路由协议的稳定性和扩展性。

目前,业界针对WSNs不同应用场合和需求研究出不同的路由协议。其中,利用蚁群算法应用于WSNs节点路由之中,通过信息素的正反馈机制找到全局最优路由,能够有效的均衡网络节点能耗,延长WSNs的生命期。

2. 基本蚁群算法原理

自然界中的蚂蚁在随机寻找食物过程中,通过在寻找食物和返回巢穴的路径上分泌俗称信息素的化学物质,不断加强路径对其他蚂蚁的影响,促使蚂蚁快速找到食物。随着时间的推移,信息素的不断蒸发会降低路径的吸引力,避免了系统快速收敛到局部最优解而非全局最优解。

2.1. 蚁群的生物行为特征

蚂蚁是一种群居生物,共有蚁后、雄蚁、工蚁和兵蚁四种,分工不同各司其职。蚂蚁通过自身分泌的一种化学刺激物进行通信,且群体协作能力呈现出高智商协作化的特点,能完成远远超过个体能力的复杂任务。

其中,蚂蚁的生物行为具有任务分配、觅食聚集等特点,介绍如下。

(1) 任务分配。自然界中蚂蚁面对的任务分配与现实中的生产调动极为相似,其中蕴含着优先级调度原理。当蚂蚁在执行任务过程中接收到更高级别的任务,会停止当前任务而转去执行新任务;当新任务优先级低于当前任务时,蚂蚁会保持原有状态。

(2) 觅食聚集。自然界中蚁巢周围存在很多毫无规律可循、随机分布的食物源。但是,经过一段觅食时间后,众多蚂蚁总是可以找到一条蚁巢到食物源的最优路径。

2.2. 蚁群算法基本原理

Dorigo M.博士于1991年首次提出蚁群算法ACO (Ant Colony Optimization),该算法是一种新型的模拟进化算法,通过模拟蚂蚁的觅食过程,寻找蚁巢和食物源之间的最优路径。其中,蚁巢对应着WSNs的源节点,食物源对应着WSNs的目的节点,蚂蚁的走动比作WSNs中数据通信。

蚁群算法提出的人工蚂蚁,与自然蚂蚁存在如下共同特点。

(1) 通信交流机制相同。人工蚂蚁通过数据等数字信息来模拟自然蚂蚁在路径上释放的化学信息素。需要注意的是,人工蚂蚁释放的数字信息也需要定期人工挥发。

(2) 数据汇聚目的相同。人工蚂蚁与自然蚂蚁相同,旨在寻找从“源点”出发到“目的地”的最短路径。需要注意的是,人工蚂蚁和自然蚂蚁都是在相邻节点间逐步移动,不能跳跃。

(3) 路由转发策略相同。人工蚂蚁和自然蚂蚁都采用的是“局部视角”,根据相邻可达路径上的信息依据路由转发策略来随机选定路径,不会考虑从“源点”到“目的地”的全局路径。

2.3. 蚁群算法在路径寻优中的应用

旅行商问题TSP (Traveling Salesman Problem)是经典的线路寻优问题。其实质是一个旅行商要遍历N个城市,从一个城市出发,经历所有城市且每个城市仅仅经历一次后回归出发的城市,要求遍历路径最短。TSP问题规则简单,随着问题规模的增大求解复杂度骤增。以50个城市为例,采用穷举法再择优,由于路径总数量巨大,计算非常费时。但是,蚁群算法具有很强的发现最优解能力,适合解决此类问题。设定为城市规模,为蚂蚁个数,网络运行初始每条路径上信息素为零。

下面给出任意时刻时,蚂蚁从城市到城市的转移概率公式,如式(1)所示。

(1)

如式(1)所示,表示蚂蚁在当前路径时可选择的下一城市集合。表示路径信息素信息对蚂蚁选择路径的影响因素,表示影响因素的权重,这里路径信息为信息素。为蚂蚁在城市选择城市为转发城市的启发期望因素,在TSP问题中通常选择城市距离的倒数,表示启发期望因素的权重。当时视作只考虑信息素的影响因素,当时视作局部路径贪婪期望启发式。

当蚂蚁遍历完所有的城市,称为一次循环。随着的推移,路径上的信息素会因挥发而变化,因此循环一次后对路径上的信息素进行更新,更新公式如式(2)和式(3)所示。

(2)

(3)

其中,为信息素的挥发系数,为当前循环中路径上的新增信息素。

就信息素更新而言,有局部更新和全局更新两种方式。局部更新是指一个蚂蚁经过城市后及时进行更新的方式。全局更新通常指当前循环中全局最优解的蚂蚁赢得机会对全局最优路径上的信息素作出的更新方式。

3. WSNs中基于蚁群算法路由协议的应用研究

3.1. WSNs路由模型

WSNs路由模型建立之前,假定WSNs监测区域为一个的二维平面,其中传感器节点地位相同,初始能量相同且具有唯一标识。传感器可以获得相邻节点的相关信息,且节点之间通信对称。

3.2. 改进蚁群算法的研究现状

蚁群算法作为当前WSNs路由协议选择的热点算法,受到了业界学者的广泛深入的研究。其中,罗旭[1] 等针对基本蚁群算法容易陷进局部最优解和收敛时间过长的问题,提出了改进的蚁群算法。其思想是在状态转移概率公式中引入罚函数和动态权重因子,并采用局部信息素更新和全局信息素更新相结合的方式更新路径信息,考虑了节点的剩余能量,节点之间的相邻距离等因素,利用MATLAB仿真从传感器节点剩余能量和传输数据包时延两个方面,与焦斌[2] 等人提出的蚁群算法进行了比较,验证了该改进蚁群算法的高效性。该算法利用节点能量与分界点的划分,当节点能量大于时,引入奖励因子,对于该类节点赋予更高的概率值。对于节点能量小于的节点,则选择100为惩罚系数,对于该类节点赋予较小的选择概率。虽然文中给出了动态权重因子,奖励因子和惩罚因子100,同时进行了信息素因子在不同取值时改进蚁群算法的全局最优解的验证,但是并没有给出改进蚁群算法与动态权重因子之间的关系,也没有给出惩罚因子100的由来。董国勇 [3] 等人针对WSNs中多跳通信造成的“热区”问题,提出了一种WSN能量均衡非均匀分簇路由算法EUCRP-ACO,该算法利用节点剩余能量和节点稀疏度确定簇首的选举和簇规模的大小,并将优化蚁群算法应用到多条路径的搜索优化过程中,从而在优化网络能量均衡时延长了网络生命周期。该算法在簇首选举时,根据式(4)来决定簇首的竞争半径。式(4)中表示为竞争半径的最大值,表示节点到Sink节点的最大距离和最小距离,表示节点到Sink的距离,为节点初始能量,为节点剩余能量,为节点最低工作能量。

(4)

针对李成法 [4] 等人提出的EEUC算法,存在使用阈值以剩余能量随机选择簇首存在减少高剩余能量节点竞争簇首的范围,并且未考虑节点疏密度的情况,EUCRP-ACO算法增加了节点密集区竞争簇首的概率,在LEACH [5] 算法的基础上改进了候选簇首的概率选择公式,具体如式(5)所示,其中

(5)

其中增加了剩余能量,节点所处区域节点密度和簇规模平均值三者因素的影响。在路由选择中利用节点剩余能量改进基本蚁群算法,在网络路由转发过程中决定人工蚂蚁的路由转发,该算法将式(1)中的信息素定义为节点之间能量距离的倒数,公式如式(6)所示,细节参考文献 [3] 。该算法在仿真中与EECU [4] 算法相比,延迟了网络首个失效节点的轮次,并在相同轮次大大降低了网络能量的消耗,考虑了路径搜索和路由构建的鲁棒性,但是该算法在执行效率方面较EEUC相对要耗费更多的时间代价。

(6)

刘剑鸣[6] 等人则在自然蚂蚁属性方面,增加了能量、时延和带宽因素,通过前向蚂蚁进行信息素的局部更新,返回蚂蚁进行信息素的全局更新,根据带宽瓶颈来限定信息素量大路径较短路径的选择,提出了性能较优的WRAC算法,并给出了WRAC算法实现的两种方案。WRAC算法从理论分析了算法的可行性、能耗和时延等性能,但并未进行WRAC算法仿真以及与其它算法的比较。为了提升WSNs的节点能量利用率,保证网络能耗均衡,杨婷[7] 等人提出了基于改进蚁群算法的IACOA算法。IACOA算法将WSNs数据传输的延迟、可靠性和能量消耗将Qos分为三类,然后利用人工蚂蚁的协作聚群特点进行WSNs最优路由的搜索。IACOA算法提出了数据分组成功接收率与距离之间的关系,以及选择数据路由转发节点的计算公式,给出了不同类型服务中蚂蚁的转移概率函数,将局部信息素更新与全局信息素更新相结合,采用VC++仿真并与郜帅[8] 等人提出的路由算法和Dijkstra算法进行数据传输延时、传输分组丢包率和节点剩余能量三个指标的比较,从仿真结果可以看出在数据传输延迟方面,IACOA算法略优于文献[8] 的延迟效果,分组丢失率相对较低,相同轮次节点剩余能量相对较多,WSNs整体网络能耗性能较好。缪聪聪[9] 等人针对节点剩余能量及链路状况可能对WSNs中部分节点寿命减少而造成整个网络生命周期严重受到影响的情况,将蚁群算法与非均匀分分簇路由算法相结合,提出AC-EBUC路由算法。AC-EBUC路由算法利用节点剩余能量优化网络非均匀成簇,采用蚁群算法进行多路径搜索,搜索过程中考虑因素包括路径传输能耗、路径最小剩余能量、传输路径、跳数、链路时延和带宽等,仿真结果反映该算法性能较优。AC-EBUC算法根据轮次分为簇首选举、路径搜索、数据传输、簇内调整和路由更新。AC-EBUC算法为了尽可能延长网络生命周期,仅仅在第一轮实行全网络竞争方式,后续仅仅在簇内进行调整的方式进行簇首的竞选,竞选方式是以高剩余能量因子来增加候选节点的竞选概率。同时,为了实现理想的簇首个数,AC-EBUC利用YE M [9] 等人提出的理想簇首数目,并改进李成法[4] 等人对非均匀分簇中簇首竞争半径公式,从而实现簇首竞选。在多径路由选择阶段,AC-EBUC算法利用前向蚂蚁携带簇首节点等路由信息表进行路径探索,利用后向蚂蚁携带的路由信息进行路径信息素的更新,从而实现多径路由选择。在簇首调整阶段,根据簇首剩余能量来决定是重新竞选还是维持原簇首,在一定程度上减少了网络能量的消耗。在仿真阶段,AC-EBUC算法与EEUC等算法进行了比较,主要包含网络能量消耗、算法的可靠性和实时性、网络生命周期以及数据路由转发的成功率。从仿真实验数据可知,AC-EBUC算法性能较优。

3.3. 改进蚁群算法在WSNs中应用总结

由于针对WSNs网络具体应用的不同需求,业界在利用改进蚁群算法进行WSNs路由协议优化时,侧重于路由选择策略。根据上述分析,研究学者在仿真验证时参照的性能指标存在多样化,主要涉及网络剩余能量,数据传输时延、路径搜索和路由构建的鲁棒性、算法执行效率以及传输数据分组丢包率等方面。今后,将研究重点放在如何有效提升改进蚁群算法的执行效率,提升数据在路由转发的成功率和可靠性方面,有效缩短时延将是未来研究的方向。

4. 结束语

本文简单介绍了无线传感器网络的应用和特点,引出了基本蚁群算法特点及其在TSP问题中的应用。然后,简要汇总了当前业界将改进蚁群算法应用于无线传感器网络的研究现状并对仿真指标进行汇总。最后指出了改进蚁群算法在无线传感器网络中应用的研究方向。

在改进蚁群算法方面,大多研究学者从节点剩余能量,簇首竞争半径,邻接点等因素方面考虑,本文作者将会从节点分布的疏密度、节点转发频度等角度出发,进一步将改进蚁群算法应用于无线传感器网络路由协议,在均衡网络能量的同时有效延长WSNs的生命期。

基金项目

北京联合大学“启明星”大学生科技创新项目(12205991501113),北京联合大学新起点计划项目资助(zk10201303),北京市职业院校教师素质提高工程资助项目。

文章引用

马金锐,陈战胜. 基于蚁群算法的无线传感器网络路由协议综述
Overview of Wireless Sensor Network Routing Protocol Based on Ant Colony Algorithm[J]. 计算机科学与应用, 2015, 05(10): 359-364. http://dx.doi.org/10.12677/CSA.2015.510045

参考文献 (References)

  1. 1. 罗旭, 吴晓军 (2015) 蚁群优化算法在WSN路由中的应用研究. 计算机工程与科学, 4, 740-745.

  2. 2. 焦斌, 熊友平, 顾辛生 (2011) 蚁群优化算法在无线传感器网络中的应用. 吉林大学学报(工学版), 1, 215-218.

  3. 3. 董国勇, 彭力, 吴凡, 闻继伟 (2015) 一种采用蚁群优化的WSN能量均衡非均匀分簇路由算法. 小型微型计算机系统, 7, 1565-1568.

  4. 4. 李成法, 陈贵海, 叶懋, 等 (2007) 一种基于非均匀分簇的无线传感器网络路由协议. 计算机学报, 1, 27-36.

  5. 5. Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-efficient communication protocol for wireless microsensor networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 3005-3014.

  6. 6. 刘剑鸣, 赵日记 (2015) 基于改进蚁群算法的无线传感器网络路由算法的研究. 计算机科学, 6A, 107-111.

  7. 7. 杨婷, 白云丽, 姜新华 (2015) 基于改进蚁群算法的无线传感器网络路由. 内蒙古大学学报(自然科学版), 1, 92-96.

  8. 8. 郜帅, 霍宏伟, 张宏科, 等 (2009) 基于数据采集均衡的移动无线传感器网络节能机制. 通信学报, 9, 109-116.

  9. 9. 缪聪聪, 陈庆奎, 曹剑炜, 等 (2013) 基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法. 计算机应用, 12, 3410-3414.

期刊菜单