基于蚁群系统的WSN 能量均衡多路径路由协议

肖 铖，孙子文

（江南大学 物联网工程学院，江苏 无锡214122）

0 引 言

随着无线传感器网络 （wireless sensor networks，WSN）的规模逐步增大，频繁的网络通信极易造成通信路径拥堵、节点能量耗尽等问题。而合理有效的路由协议是解决这些问题的关键因素。因此，设计一种能量均衡、网络拥塞程度低的路由协议成为无线传感器网络研究的目标之一［1］。

蚁群算法是一种仿生启发式群智算法，因其具有分布式、自组织、正反馈等系统特性，常用在解决无线传感器网络路由等组合优化问题上。作为蚁群算法的一个重要分支，蚁群系统 （ant colony system，ACS）是对AS （ant system）算法改进的蚁群算法，在避免局部最优解、加快收敛速度等方面性能有一定提升，算法过程包括伪随机状态转移规则、局部信息素更新和全局信息素更新3 个阶段［2］。文献 ［3，4］分别将ACS 算法、AS 蚁群算法与博弈论方法和模糊推理方法相结合，以提高路由路径的质量，降低网络能耗。然而，博弈论、模糊推理等方法的引入，加大了节点的计算处理时间，易带来网络拥塞等问题。基于蚁群优化和能量路由的思想，文献 ［5－8］提出关于WSN 的蚁群算法能量路由协议。其中文献 ［5，6］在典型路由协议EEABR （energy efficient ant－based routing）上进行了改进，EEABR 协议是一种针对WSN 的约束特点的主动式能量有效蚁群路由算法，通过人工蚂蚁搜索能量高效且最短的路径来最大地延长网络生命期［9］。然而，作为单路径路由方式，其难以有效地解决能量均衡和网络拥塞等问题。文献 ［10］中提到的AOMDV 协议是为减少路由发现频次并降低因路径故障而引起的丢包率的多路径路由协议，但这类路由协议缺少对节点能量约束方面的考虑且一直选择相同的路径进行数据转发，易导致路径中的部分节点能量过早耗尽，影响网络生命期，因此，不太适用于WSN 环境。文献 ［11］提出一种适于WSN 的多路径路由协议MACS （multipath routing based on ant colony system），MACS协议是基于ACS蚁群算法的多路径路由，但多路径的建立没有考虑路径的能量状态，对网络的能量效率提高不明显，同时也存在未能充分利用多路径进行数据发送的问题。

在这些研究基础上，为有效解决无线传感器网络能量均衡和网络拥塞问题，采用ACS蚁群算法，本文提出一种多路径路由协议 （ACS based wireless sensor networks multi－path routing protocol，ACSBMR）。一方面，该协议在ACS蚁群算法基础上对信息素更新方式和启发式策略进行改进，并构建路径综合评价函数，对路由路径进行择优筛选；另一方面，多路径建立可有效解决单路径路由在节点能耗分布不均、负载不均衡等方面的不足，有利于延长网络生命期［12］。通过NS2 仿真平台验证了该协议的可行性，仿真结果表明，其满足一定的路由性能指标，并达到了设计的目的。

1 网络模型

以中小规模静态无线传感器网络为研究对象，将其建模为具有加权系数的双向连通图G＝ （V，E），其中，V＝｛vi｜i＝1，2，…，n｝表示n 个节点的集合，E＝ ｛（vi，vj）｜1≤i≤n，1≤j≤n，i≠j｝表示任意相邻节点i、j之间的节点链路集合，源节点到目的节点的路由路径是由多个有序的带加权因子的节点链路组成。设网络中有一源节点v1和目的节点vn，v1到vn的所有路由路径的集合用P表示，其第k条路由路径记为Pk（Pk∈P），则Pk是由集合E中的部分元素按一定先后次序排列组成。无线传感器网络的网络层次结构自下而上可以分为物理层、数据链路层、网络层、传输层、应用层这横向五层，各层次协议间存在纵向管理机制，路由协议位于网络层，网络层的工作机制通常需要其它底层技术的支持［13］。

一个无线传感器网络的物理层和网络层之间的跨层设计模型如图1所示，通过这个模型可以获取节点之间的距离信息和节点队列长度。图中节点的队列长度Queue＿len从MAC层获得，而由物理层的信号接收功率Pr与节点间的距离d 成反比关系的原理，利用双径无线传播模型 （two ray ground）计算出d，如式 （1）所示

式中：Pt和Pr——信号发送、接收功率；Gt和Gr——发送、接收端天线增益；ht和hr——发送、接收端天线高度；L——系统损耗 （默认值1）。

图1 跨层设计模型

2 ACSBMR路由算法

2.1 路由发现

2.1.1 报文信息表示

ACSBMR 算法中用到的蚂蚁包有两种：前向蚂蚁Fant和后向蚂蚁Bant，其报文格式分别如图2、图3所示，报文各个参数及涵义见表1。

图2 Fant报文格式

图3 Bant报文格式

表1 Fant和Bant报文参数

表1中，TTL值的设置是为了防止前向蚂蚁在网络中无限地循环下去而浪费网络资源，前向蚂蚁每经过一个节点，TTL值就减1；当其值减为0时，节点就把此前向蚂蚁包丢弃，不再对其进行转发。

在传感器网络进行无线通信时，为了获知与维护邻居节点间的连通关系，每个节点需要周期性地发送Hello包来更新邻居节点，同时将相应的邻居节点信息保存在各自的邻居表Table中。Hello包的报文格式和Table结构分别如图4、图5所示，二者的各个参数及涵义见表2。

图4 Hello包报文格式

图5 Table结构

表2 Hello包报文和Table结构参数

表2中，Hello包的发送周期可以根据网络场景的稳定性进行设置，对于节点不移动的静态网络场景，各个节点的邻居关系相对稳定，其Hello包的发送周期可以大一点。本文设定Hello包的发送周期为5s，若超过10s没有收到某邻居节点发送的Hello包，则代表这个邻居已经死亡，应将这个邻居节点从邻居表Table中删除。

2.1.2 伪随机状态转移规则

源节点产生m 个前向蚂蚁，这些蚂蚁根据伪随机规则进行下一跳节点的选择直至到达目的节点。设第k 个前向蚂蚁当前所在节点为i，下一跳邻居节点为j，则节点j的选择规则如式 （2）所示

其中

式中：q是均匀分布在 ［0，1］区间的一个随机数，前向蚂蚁每次选择下一跳节点时都由算法随机产生，q0（0≤q0≤1）为常数；pij是选择节点j 作为下一跳的概率；Nki表示节点i的邻居节点集合；τir和ηir分别表示节点链路 （i，r）上信息素值和启发式函数值；α、β分别表示信息素值和启发式函数权重因子；Tuba表示禁忌表。在前向蚂蚁k 选择下一跳节点之后，当前节点i也加入到Tuba中。

启发式函数的引入可以提高算法的收敛速度，启发式函数ηij的定义如式 （4）所示

式中：dij和lj——相邻节点i、j之间的通信距离和下一跳邻居节点j 的队列长度，可通过调用网络跨层设计模型中的相关信息获得；D 和L——节点属性中的最大通信半径和最大队列长度；λ （0≤λ≤1）为可调参数，作为dij和lj的比例因子。这里启发式函数作为概率选择的辅助，同时权衡节点距离和队列长度，通信距离和队列长度越小的邻居节点作为下一跳节点可能性越大。

2.1.3 局部信息素更新

在前向蚂蚁搜索路由路径过程中，为扩大路径搜索空间，使后面的前向蚂蚁能够探索更多的较优路径，可以通过对节点链路进行局部信息素更新的方式来取得一定效果。当前向蚂蚁从节点i转移到下一跳节点j 时，对节点链路（i，j）上的信息素τij重新计算。信息素更新规则如式 （5）所示

式中：Ω＝τ0／dij，τ0为相邻节点链路初始信息素，dij为节点i、j之间的通信距离；ξ （0≤ξ≤1）为局部信息素挥发系数。

为了提高路由发现过程的效率，需要对前向蚂蚁的延迟做一定约束处理。设第一个到达目的节点的前向蚂蚁的端到端时延记为Ts－d（Ts－d可以从前向蚂蚁包的报文格式中的起始时间得到）［14］。针对前向蚂蚁的延迟问题，在目的节点设置一个等待时间Td如式 （6）所示

式中：系数Cd可根据网络实际环境进行适当调整。对于第一个以及在Td内到达目的节点的前向蚂蚁都转化为相应的后向蚂蚁，其它前向蚂蚁则丢弃不作处理。

2.1.4 全局信息素更新

目的节点接收到前向蚂蚁后，将搜索得到的路由信息进行一定处理后转化为相应的后向蚂蚁。后向蚂蚁沿前向蚂蚁的反向路径返回至源节点，并对经过的节点链路进行一次全局信息素更新，更新规则如式 （7）所示

式中：ρ （0≤ρ≤1）是全局信息素挥发因子。Δτij为第k 条路径上信息素增量，其表达式如式 （8）所示

式中：σ——信息素增强系数；E0——节点的初始能量；Ei——节点i的当前能量值；Pk——后向蚂蚁返回至源节点对应的第k 条路径；N——路径Pk上的节点数；Emin和Eavg——路径上的节点中的最小剩余能量和平均剩余能量。因此，Δτij综合衡量了路径上节点的能量瓶颈情况和能量均衡度，其值越大，说明路径上节点能量均衡越好，而且所有节点的能量值也相对较高。

2.2 多路径评价及数据发送

经过算法的路由发现过程，在源节点已形成n（n≤m）条可达目的节点的路由路径。根据后向蚂蚁中存储的路由跳数信息和信息素信息，源节点对获得的路由路径按照路径综合评价函数Fitness（k）以衡量路径质量水平，路径综合评价函数计算公式为式 （9）

式中：h（k）——第k条路径的路由跳数，k＝1，2，…，n。通过计算路径综合评价函数值，源节点可通过建立多条路由路径，以概率选择的方式进行数据流发送。

第k条路径发送数据包的概率R（k）表达式如式 （10）所示

式中：n代表所有路由路径的数量。综合评价函数Fitness（k）值越大，被选择为发送路径的概率就越大，即质量越好的路径被选作发送数据的可能性越大，相应承担的数据负载越多，这种方式在一定程度上有助于网络能量资源消耗的均衡。随着节点的启发因子和节点链路上信息素浓度的不断变化，Fitness（k）和R（k）的值也被不断更新，数据流也随之往质量较好的路径上发送。

2.3 算法步骤

由于蚂蚁数和算法的迭代次数需要视网络环境而定，不适宜取固定值［15］，在本文路由算法中，源节点产生的蚂蚁数m 和算法的迭代次数Nmax由网络规模大小决定，其中m＝NNantss，Nmax＝NNiters；Ns表示网络中节点的个数，Nants∈ ［0，1］和Niter∈ ［0，1］。算法的主要步骤归纳如下：

步骤1 初始化迭代次数Nmax和相邻节点链路的起始信息素值τ0，并令当前迭代次数Nc＝0。

步骤2 在源节点处构造m 只前向蚂蚁，每只蚂蚁标记为k，k＝1，2，…，m。

步骤3 前向蚂蚁k 根据伪随机状态转移规则式 （2）选择下一跳邻居节点j。

步骤4 前向蚂蚁k 根据局部信息素更新规则式 （5）对所选的节点链路上的信息素进行更新，并不断重复直至目的节点。

步骤5 对于在Td时间内到达目的节点的前向蚂蚁，将其转化为后向蚂蚁并根据全局信息素更新规则式（7）对反向路径上的节点链路进行信息素更新，直至返回至源节点。

步骤6 如果算法满足结束条件Nc＞Nmax，则跳到步骤7；否则Nc＝Nc＋1，并返回至步骤2。

步骤7 当所有后向蚂蚁到达源节点后，根据式 （9）确定多条路由路径。

步骤8 由最终确定的多条路由路径，根据式 （10）以概率选择方式进行数据发送。

3 仿真与分析

仿真采用WindowsXP＋Cygwin2.738＋ns2.35 平台，通过多组不同仿真实验结果取平均值来对本文路由算法进行评估与分析，并与AOMDV、EEABR 路由协议进行比较分析。

3.1 仿真场景与参数设置

所有仿真场景均在1000 m×1000 m 的平面区域内进行，为比较各路由协议在不同的节点密度下的性能，每个场景分别部署50／100／200／300／400个节点，数据流最大连接数依次为10／15／25／35／45，并在节点中随机选取源节点和目的节点。每个场景的仿真时间为300s，节点通信范围设置为100m，数据流采用cbr模型，由数据流生成工具cbrgen产生，数据分组大小为512Byte，数据流速率为4 packets／s，无线传播方式为Propagation／TwoRayGround，能量模型为EnergyModel，节点发送一个包所需要的功耗txPower＝0.660 w，节点接收一个包所需要的功耗rxPower＝0.395w，MAC类型为Mac／802＿11，节点的最大队列长度为50，节点的初始能量为20J。路由算法的具体参数设置见表3。

表3 ACSBMR算法参数

3.2 仿真结果及性能分析

考虑到本文路由算法以均衡网络能量和减小网络拥塞度为目标，仿真主要从能量效率、节点剩余能量标准差、端到端平均时延、网络生命期这几个方面对3种路由协议进行性能分析与比较。

能量效率定义为仿真过程中网络平均每消耗1焦耳的能量，目的节点接收到的数据包大小 （Kbits）。从图6中可以看出，随着网络节点数目的增加，网络的负载能力更强，各个协议的能量效率都有一定的提高，但ACSBMR 协议比其它两种协议的能量效率均要高25%左右。ACSBMR 协议对建立的多条路径以概率选择的方式进行路由，提高了对多路由路径的利用效率，减少了因多次路由控制而引发的能量上的消耗，所以其能量效率相对较高。

图6 能量效率

节点剩余能量标准差衡量的是仿真结束时所有节点剩余能量的分散程度，其值越大，说明路由协议的能量均衡性越差。从图7 可以看出，在各个仿真场景结束时，ACSBMR 协议的节点剩余能量标准差比其它两种协议都要小很多，且当节点数少于200个时，其剩余能量标准差变化相对平稳，说明ACSBMR 协议的能量均衡性相对较好。与AOMDV 协议不同的是ACSBMR 协议主要以单播路由方式进行节点间通信，减少了能量消耗，且在路径选择时考虑节点能量的均衡性，故ACSBMR 协议在节点剩余能量标准差方面的性能要好很多。而EEABR 协议是单路径路由方式，在能量效率上主要考虑单条路径的能量消耗情况，不利于能量的均衡。

图7 节点剩余能量标准差

端到端平均时延是在数据包传输过程中从源节点到目的节点的平均时间差值。从图8可以看出，随着节点数目的增加，端到端平均时延随之增加，其中AOMDV 和EEABR 协议明显高于ACSBMR 协议，且在网络节点数目不断增加下，ACSBMR 协议仍能保持较小的时延增长率。这是由于ACSBMR 协议采用多路径路由方式，各路径根据路径综合评价函数以概率分配方式发送数据包，有利于减少网络拥塞的发生，同时在启发式函数中考虑节点队列长度，优先选择网络接口队列长度小的节点作为下一跳节点，避开了相对拥塞的节点。

图8 端到端平均时延

网络生命期定义为从仿真开始到第一个节点死亡 （即能量耗尽）的时间段。图9的仿真结果显示，随节点数目的增加，各路由协议得到的网络生命期变化不大，但ACSBMR 协议中第一个节点死亡时间要晚于AOMDV 和EEABR 协议。从图上可以看出，ACSBMR 协议中的网络生命期为150s左右，相对AOMDV 和EEABR 协议的分别提高了约50%和87.5%，这种提升对于延长网络生命期具有重要意义。

图9 网络生命期

综上仿真结果，由于在信息素更新中加入了节点能量均衡策略，同时数据传输以多路径的形式完成，ACSBMR 协议能够使节点能量得到均衡，进而延长网络的生存期。

4 结束语

蚁群算法以其分布式计算、信息正反馈和启发式搜索等系统特点，在无线传感器网络中的应用已很广泛。本文将ACS蚁群算法的全局优化能力、多路径路由方法以及能量均衡策略相结合，设计了一种无线传感器网络能量均衡多路径路由协议ACSBMR。从路由发现所获的路径信息构造了路径综合评价函数，由此得到源节点与目的节点之间的多条优化路径。在数据发送阶段，根据各条路由路径的不同路径质量水平以概率分配方式选择合适的路由路径，把数据流量均衡地注入无线传感器网络，使得数据均衡地发送。仿真结果表明，ACSBMR 协议能够实现无线传感器网络中均衡网络能量和降低网络拥塞的目的，进而延长网络的生命期。

［1］Pantazis NA，Nikolidakis SA，Vergados DD.Energy－efficient routing protocols in wireless sensor networks：A survey ［J］.Communications Surveys ＆ Tutorials，2013，15 （2）：551－591.

［2］Saleem M，Di Caro GA，Farooq M.Swarm intelligence based routing protocol for wireless sensor networks：Survey and future directions ［J］.Information Sciences，2011，181 （20）：4597－4624.

［3］ZHAO Hong，HU Zhi，WEN Yingyou.ACS based differen－tiated service routing algorithm in wireless sensor network ［J］.Journal on Communications，2013，34 （10）：106－115（in Chinese）.［赵宏，胡智，闻英友.基于ACS的无线传感器网络区分服务路由算法［J］.通信学报，2013，34 （10）：106－115.］

［4］Rabelo RAL，Sobral JVV，Araujo HS，et al.An approach based on fuzzy inference system and ant colony optimization for improving the performance of routing protocols in wireless sensor networks［C］／／IEEE Congress on Evolutionary Computation，2013：3244－3251.

［5］Dominguez C，Cruz－Cortés N.Energy－efficient and locationaware ant colony based routing algorithms for wireless sensor networks［C］／／Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation.Dublin：ACM，2011：117－124.

［6］Zungeru AM，Seng KP，Ang LM，et al.Energy efficiency performance improvements for ant－based routing algorithm in wireless sensor networks［J］.Journal of Sensors，2013，2013（759654）：1－17.

［7］Jiang Xuepeng，Hong Bei.ACO based energy－balance routing algorithm for WSNs ［C］／／Proceedings of the First interna－tional conference on Advances in Swarm Intelligence.Beijing：Peking University，2010：298－305.

［8］Mahadevan V，Chiang F.iACO：A bio－inspired power efficient routing scheme for sensor networks ［J］.International Journal of Computer Theory and Engineering，2010，2 （6）：972－977.

［9］Mundada MR，Kiran S，Khobanna S，et al.A study on energy efficient routing protocols in wireless sensor networks ［J］.International Journal of Distributed and Parallel Systems，2012，3 （3）：311－330.

［10］Tekaya M，Tabbane N，Tabbane S.Multipath routing with load balancing and QoS in ad hoc network ［J］.IJCSNS international Journal of computer science and network security，2010，10 （8）：280－286.

［11］Ren Xiuli，Liang Hongwei，Wang Yu.Multipath routing based on ant colony system in wireless sensor networks［C］／／International Conference on Computer Science and Software Engineering.Wuhan：IEEE，2008：202－205.

［12］Kim S.An ant－based multipath routing algorithm for QoS aware mobile ad－hoc networks ［J］.Wireless Personal Communications，2012，66 （4）：739－749.

［13］Kiran M，Reddy GRM.Design and evaluation of load balanced termite：A novel load aware bio inspired routing protocol for mobile ad hoc network ［J］.Wireless Personal Communications，2014，75 （4）：2053－2071.

［14］Krishna PV，Saritha V，Vedha G，et al.Quality－of－serviceenabled ant colony－based multipath routing for mobile ad hoc networks［J］.IET Communications，2012，6 （1）：76－83.

［15］Mármol FG，Pérez GM.Providing trust in wireless sensor networks using a bio－inspired technique［J］.Telecommunication Systems，2011，46 （2）：163－180.