改进蚁群算法在WSN路由优化中的应用*

李 锋

（广东交通职业技术学院，广州510650）

·微机网络与通信·

改进蚁群算法在WSN路由优化中的应用*

李 锋

（广东交通职业技术学院，广州510650）

无线传感网络是一种由大量传感节点构成的分布式网络系统，节点与节点之间通过彼此交换状态信息以发现和维护路由，组成统一网络。针对目前无线传感网络路由协议的不足，提出基于视野极值的改进蚁群路由算法，并通过信息素局部更新避免全部蚂蚁选择相同路径，算法提前收敛的问题。仿真实验证明，新算法具有正反馈、全局收敛和动态适应等优点，能很好适应无线传感网络节点随机分布，节点频繁加入和死亡的现象。

无线传感网络；蚁群算法；路由协议；无线自组织网络；传感节点；汇聚节点

1 引 言

无线传感网络是一种由大量传感节点构成的分布式网络系统，由传感节点、汇聚节点和管理节点组成，见图1。传感节点感知目标信息后以多跳接力方式传给汇聚节点，汇聚节点对附近传感节点信息汇总后通过卫星基站、互联网传送给管理用户［1－2］。

无线传感网络一般应用于恶劣环境或是人无法抵达的区域。由于节点数量繁多，并且无法精准定位，传感节点通常采用随机散播方式部署，节点与节点之间通过彼此交换状态信息以发现和维护路由，组成统一网络。网络层路由协议是WSN通信的基础，是实现网络可靠、有效传输的关键，既要考虑节点加入、移动和死亡过程，也要有一定的稳定性、容错性和扩展性［3］。目前，业界针对无线传感网络不同应用场合和需求研究出不同的路由协议。

2 无线传感网络路由协议

2．1 SPIN路由协议

SPIN（Sensor Protocols for Information via Negoti-ation）协议是一种自适应路由协议。由于邻居传感节点感知的路由信息具有相似性，为减少数据传输冗余，节点只广播其他节点没有的路由信息，从而共同维护全网路由，降低节点能耗［4－5］。SPIN路由算法简单，对发现新节点动作迅速，但对判断死亡节点耗时较长，不适合用于节点频繁加入和离开的场合。

图1 WSN体系结构

2．2 定向扩散协议

定向扩散协议（Directed Diffusion，DD）是以数据为中心的路由协议，汇聚节点周期性广播路由兴趣消息，通告整个网络中其他节点所需路由。途经节点通过建立反向梯度信息建立反向路径，并将梯度信息传至汇聚节点，由汇聚节点计算全网路由并返回给网络中所有节点。在定向扩散协议中，节点需要维护共同兴趣路由消息，加上洪泛机制影响，路由代价和消耗较大，不适合应用于大规模无线传感网络。

2．3 TTDD路由

TTDD（Two－Tier Data Dissemination）是针对网络中众多汇聚节点和汇聚节点移动问题所设计的路由协议。当多个节点感知新的路由信息时，共同选择中心节点作为源节点，由源节点计算相邻交叉点位置，利用贪心算法请求邻居节点成为新交叉点，新交叉点重复该过程直到网络边缘，从而构成格状网络［6］。汇聚节点计算格状网络邻近交叉点位置，而交叉点又保存了路由事件和源节点信息，汇聚节点通过泛洪广播交叉节点坐标，告知网络中节点完整的路由信息。TTDD计算与维护格状网开销较大，节点必须知道自身位置否则无法计算路由信息，路由精度对节点密度依赖较高。

无线自组织网络MANET（Mobile Ad Hoc Network）是一个由众多节点组成的无线通信对等网络，与无线传感网络相比十分接近，如节点能量有限，网络拓扑结构易变，部分路由协议相通等［7－8］。目前，无线自组织网络已利用蚁群算法应用于节点路由之中，通过信息素正向反馈机制找到全局最优路径。针对目前无线传感网络路由协议不足，提出基于视野极值的改进蚁群路由算法，并应用于无线传感网络路由协议之中。新算法具有分布式、正反馈、全局收敛和动态适应等优点，通过蚂蚁间的协同工作可以有效减少搜索最优路径的复杂度。

3 标准蚁群算法

蚁群算法（Ant Colony Algorithm）是基于蚁群觅食行为提出的一种仿生算法［9］。每个蚂蚁在觅食时在其所经路径分泌信息素进行标识，信息素会随时间蒸发直至消失，后继蚂蚁根据信息素浓度选择移动方向。路径长度越短，信息素挥发越少，信息素越浓，后继蚂蚁选择几率越大；反之，路径越长，所经时间越多，直至信息素挥发殆尽，所选路径被淘汰。大量蚂蚁分泌的信息素构成路径选择反馈机制，最终整个蚁群找到巢穴到食物之间的最优路径。算法模型如下：

（1）初始化节点和蚁群数量，蚁群随机选择路径，直到抵达目的节点。

（2）每个节点存储其邻居节点通往目的节点的路径开销，后继蚂蚁根据路径开销值计算节点转向概率。设节点i路径开销为Qi，其邻居节点j的路径开销值为Qj，则对于节点i选择下一节点j的转向概率为：

（3）若蚂蚁在t时刻探索路径，在t＋1时刻选择到下一路由，完成一次循环迭代，则在t＋1时刻节点i选择节点j的信息素浓度增量将按照以下公式更新：

（4）蚂蚁根据下一节点信息素浓度Tg选择最优路径，概率为：

4 蚁群算法在WSN网络中的应用

蚁群算法通过单个蚂蚁活动和协作完成路径搜索，个体之间相互独立，按照既定规则运行，共同决定全局最优路径。这种自组织、自适应、并行搜索和动态反馈机制能够在最短时间内找到全局最优解。在无线自组织网络中，节点铺设成本较高，密度均匀，结构相对稳定，蚁群算法利用信息素反馈以适应网络拓扑结构的微小变化。而在无线传感网络中，第一，节点会因为复杂环境变化重启和失效，节点加入和死亡更为频繁，必须重新定义信息素转移概率和挥发系数，否则蚂蚁将花费大量时间等待信息素更新；第二，节点成本低廉，一般采用空投方式部署，随机性很大，节点分布极不均匀，此时基于跳数的路径开销会产生局部路径计算不合理的问题，必须限制蚂蚁每次行进最大距离，即视野范围；第三，信息素的正向反馈机制会促使所有蚂蚁走到同一路径，造成算法过早收敛，找到的解是全局近优解，此时必须在蚂蚁抵达目的节点后对其所选路径的信息素进行局部更新，减少相同路径信息素浓度值。综上所述，改进的蚁群算法在无线传感网络中应用如下：

（1）初始化参数，定义蚁群数量n和蚂蚁每次行进距离P，P取值区间为：

其中Di－Sink是节点i到汇聚节点之间的距离，MaxRadius是蚂蚁最大通信半径。

（2）蚂蚁在节点i选择节点j的路径转移概率为：

其中P是式（5）的行进距离，α和β是节点i和节点j各自权重。

（3）蚂蚁根据转移概率行进至下一节点，完成一次循环迭代，信息素浓度更新如下式：

（4）蚂蚁抵达目的节点后，利用式（9）对其所选路径局部更新，减少相同路径的信息素浓度，避免所有蚂蚁收敛至同一路径。

其中τ（i，j）是节点i选择节点j的信息素迹量。

（5）重复步骤（3）和步骤（4），直到所有蚂蚁都生成完整路径。

（6）全部蚂蚁根据式（10）更新全局信息素浓度。

（7）循环步骤（2）至步骤（6），每次迭代找出的路径长度将越来越短，直至算法收敛获得全局最优解，或超出最大循环次数，此时算法终止。

5 仿真测试

定义传感节点分布区域为100*100，汇聚节点8个，均匀分布，其中汇聚节点⑧为根节点；传感节点80个，随机生成。初始化蚁群数量n为30，最大迭代次数200，α＝1．5，β＝1．7，ρ＝0．5，节点加入和死亡率分别为5%和8%，表1是四种算法的结果。从表1可以看出，SPIN算法简单，能耗较低，但选择的路径长度偏大，并且判断死亡节点耗时较长，导致节点失效率很高。DD和TTDD算法利用节点泛洪更新路由信息，节点能耗较大，并且全局最优解与节点密度相关，路径算法偏差较大。而新算法找出的路径长度最短，路径平均费用最低，能量消耗也适中，能很好满足无线传感网络的工程应用需求。

表1 四种算法结果比较

算法在第162次完成迭代，找到全局最优路径。根据各节点转移概率连接节点连通状态，构成无线传感网络全局路由信息图。其中圆点表示传感节点，方框表示汇聚节点，如图2所示。

图2 WSN全局路由信息图

6 结束语

针对目前无线传感网络路由协议不足，提出基于视野极值的改进蚁群路由算法，并通过信息素局部更新避免全部蚂蚁选择相同路径。新算法具有正反馈、全局收敛和动态适应等优点，能很好的适应无线传感网络节点随机分布，节点频繁加入和死亡的现象。

［1］ 张轮，陆琰，董德存．一种无线传感器网络覆盖的粒子群优化方法［J］．同济大学学报（自然科学版），2009（2）：181－185．Zhang Lun，Lu Yan，Dong De Cun．A New Wireless Sensor Network Optimization Algorithm Base On Particle［J］．Journal Of Tongji University（NATURAL SCIENCE EDITION），2009（2）：181－185．

［2］ 徐云剑，彭沛夫，郭艾寅．基于改进蚁群算法的WSN移动代理路由算法研究［J］．计算机工程与应用，2009（4）：45－49．Xu yun jian，Peng Pei Fu，Guo Ai Yan．Study Of Mobile Agent Routing Algorithm Based On Improved Ant Colony Algorithm In WSN［J］．Computer Engineering And Application，2009（4）：45－49．

［3］ 孙力娟，王良俊，王汝传．改进的蚁群算法及其在TSP中的应用研究［J］．通信学报，2004（10）：238－241．Sun Li Juan，Wang Liang Jun，Wang Ru Chuan．Study Of Improved Ant Colony Algorithm And Application In TSP［J］．Journal On Communications，2004（10）：238－241．

［4］ 高坚．基于自适应蚁群算法的多受限网络QoS路由优化［J］．计算机工程，2003（19）：242－248．Gao Jian．OptimizationOfMultipleConstrainsQoS Routing Based On Ant Colony System Algorithm［J］．Computer Engineering，2003（19）：242－248．

［5］ 叶志伟，郑肇葆．蚁群算法中参数α、β、ρ设置的研究—以TSP问题为例［J］．武汉大学学报（信息科学版），2004（7）：95－100．Ye Zhi Wei，Zheng Zhao Bao．Study On The Parameter α、β、ρSet In Ant Colony Algorithm—Taking TSP For Example［J］．Journal Of Wuhan University（Information Science Edition），2004（7）：95－100．

［6］ 季莹莹，章坚武，虞成磊．无线传感器网络权值分簇路由协议改进［J］．杭州电子科技大学学报，2008（6）：193－197．Ji Ying Ying，Zhang Jian，Yu Cheng Lei．An Improvement Routing Protocol by Weighted Clustering Algorithm in WSN［J］．Journal of Hangzhou Dian Zi University，2008（6）：193－197．

［7］ 汪学清，杨永田，孙亭．无线传感器网络中基于网格的覆盖问题研究［J］．计算机科学，2006（11）：215－221．Wang Xue Qing，Yang Yong Tian，Sun Ting．Research On The Grid－based Coverage Problem In Wireless Sensor Networks［J］．Computer Science，2006（11）：215－221．

［8］ 梁华为，陈万明，李帅．一种无线传感器网络蚁群优化路由算法［J］．传感技术学报，2007（11）：65－69．Liang Hua Wei，Chen Wan Ming，Li Shuai．A Wireless Sensor Network Routing Optimization Algorithm Base On Ant Colony［J］．Journal Of Sensor Technology，2007（11）：65－69．

［9］ 杨文国，郭田德．求解无线传感器网络路由问题的蚁群最优化算法及其收敛性［J］．系统科学与数学，2007（2）：195－201．Yang Wen Guo，Guo Tian De．Ant Colony Optimization Algorithm And Convergence For Wireless Sensor Network Routing Problem［J］．System Science And Mathematics，2007（02）：195－201．

Application of Improved Ant Colony Algorithm in WSN Routing Optimization

Li Feng
（Guangdong Communication Polytechnic，Guangzhou 510650，China）

Wireless sensor network，as a distributed network system，is composed of a large number of sensor nodes．By exchanging state information，the nodes can discover and maintain routing information to form a unified network．Aiming at the problems of routing protocol in wireless sensor networks，this paper describes a new ant algorithm based on vision extremes，and avoids all the ants to choose the same path by update partial pheromones．The simulation results show that new algorithm has advantages of positive feedback，global convergence and dynamic adaptation and is suitable for the phenomenon of large nodes join and death in wireless sensor network．

WSN；Ant Colony Algorithm；Routing Protocol；Mobile Ad Hoc Network；Sensor Node；Sink Node

10．3969／j．issn．1002－2279．2015．04．004

TP393

A

1002－2279（2015）04－0011－04

2012年广东省高等学校教学质量与教学改革工程省级精品资源共享课程（粤教高函［2013］13号）；2013年广东省高职高专校长联席会议教改项目（GDXLHQN012）；2014年广东省高等职业教育教学改革项目；2014中国交通教育研究会科研项目（交教研1402－136）

李锋（1981－），男，广东省龙川县人，硕士研究生，讲师，主研方向：计算机系统结构和网络安全方向的研究。

2015－01－16