WSN中基于蚁群算法的QoS路由协议*

王 镇，刘学军

(南京工业大学信息科学与工程学院，南京 210009)

随着传感器网络规模的指数增长使得一些网络动态特性更加突出，因此需要数据传输路径能够随着网络结构的变化而自适应地改变。传统的路由算法已经不能适应这种情况的需求，为解决传感器网络节点的数据拥塞、传输延时、能量消耗过大等问题，必须提出更为有效的QoS路由算法，一方面要路径尽量短，以满足实用性;另一方面又要避开负载较重的链路，保持网络负载分布的平衡性。

蚁群算法是一种基于种群的模拟进化算法，主要是通过蚂蚁觅食过程中群体之间的信息传递而达到寻优的目的，其原理是一种正反馈机制，通过信息素的不断更新达到最终收敛于最优路径上的目的，同时算法具有随机自适应性、全局优化和分布式等特点。蚁群算法的随机自适应性使得它很适合应用于无线传感器网络环境中［1－2］，所以将蚁群算法应用于无线传感器网络中的QoS(Quality of Service)研究有着重要的意义。

1 相关工作

AntNet［3］是将蚁群优化算法应用于网络路由问题的经典算法。在AntNet中，每个节点维护一个路由表和一个网络状态表，路由表中记录着该节点到达下一个目的节点的所有下一跳的信息素强度，数据包将根据信息素强度计算下一跳的选择路径。AntNet中使用了前向蚂蚁(Forward ant)和后向蚂蚁(Backward ant)两种移动代理。前向蚂蚁根据路由表信息，采用启发式算法寻找到达目的节点的路径，并收集路径上的网络状态，前向蚂蚁到达目的节点后即消亡，同时产生后向蚂蚁沿原路返回，并更新所经过的节点的路由表。文献［4］对AntNet路由的性能进行了分析，并对AntNet与Dijkstra进行了比较，仿真结果表明两者性能相近，但在通信量较大的网络中，AntNet优于 Dijkstra算法。文献［5］中，提出了EEABR算法，算法的核心思想是参考路径中的能量改进信息素的更新过程。如果某条路径上平均剩余能量较多，那么该路径上信息素的浓度会增加得越多，从而使得路径有更高的被选择的机会，但是一个剩余能量较少的节点仍有可能出在一条具有较高平均剩余能量的路径上，从而该节点会过早死亡，缩短网络生命周期。文献［6］分析了以数据为中心的无线传感器蚁群优化路由算法，并针对蚁群优化路由算法的缺陷提出了一种改进算法，通过增加一个称之为搜索蚂蚁(seach ant)的新型移动代理，帮助前向蚂蚁避免陷入环路陷阱。Reza GhasemAghaeil［7］等人提出了一种基于生物学启发式智能群体路由算法(SIBR)。作者提出两种基于智能群体的自适应路由算法:自适应路由算法(AR)和改进型自适应路由算法(IAR)。他们通过去除队列参数和加入强化学习概念(reinforcement learning concept)，改进了 ADR［8］(基于蚁群算法的自适应动态路由)算法，由此产生了AR算法［9］。然而，AR算法不能产生最优解。因此，通过增加系数，即邻居节点和目的节点之间的“代价”，作者提出了IAR算法，从而进一步改善了AR算法的性能。在文献［10］中，苏淼等人在传感器网络分层路由协议LEACH基础上，重新定义了“轮”的概念，提出了基于蚁群的无线传感器网络双簇头算法(ACDCHA)，算法把每一轮划分成3个阶段而不是传统的两个阶段。根据信息素浓度在每一簇中选择具有分工特征的主簇头和副簇头，主簇头进行数据收集和融合，副簇头进行数据传输工作。该算法较好的平衡了网络的能量消耗，延长了网络生命周期。文献［11］提出了一种基于多路径蚁群算法的无线传感器网络的路由(MACS)，该算法利用蚁群的自组织、自适应能力，并行地寻找最优传输路径，保留次优传输路径，以达到多路径传输的目的，使网络能量均衡消耗，延长了网络生命周期，但是没有考虑网络的QoS问题。文献［12］提出了一种面向传感器网络的蚁群优化路径恢复算法，通过建立一种兼顾节点能量消耗和节点剩余能量的路径选择概率模型，使得算法能够找到一条从源节点到sink的能量有效路径，提高了全网的能量有效性，但是在概率选择模型中没有考虑路径的延迟和带宽等因素。

WSN中现有的蚁群算法，一般是使用跳数［13］或者欧几里得距离［14］来计算下一跳概率的，他们几乎没有提及QoS问题。与上述研究不同，本文为了解决传感器网络的数据拥塞、传输延时、能量消耗过大等问题，本文提出了一种基于蚁群算法的传感器网络QoS路由算法。

2 基于蚁群算法的QoS路由算法

2.1 网络模型

给定网络G=(V，S，E)，其中V为传感器节点集，S为源节点集且S∩V=Φ，E为边集，假设所有的边都是双向的。对于任何节点v∈(S∪V)有一个最大传输距离r，用R(vi，vj)表示节点vi和vj的距离，如果R(vi，vj)≤r，则存在一条边e(vi，vj)∈E。本文讨论的无线传感器网络QoS路由是寻找到满足不同QoS需求的路径p。路径p满足QoS需求的目标函数如下:

其中，bandwidth(p)为路径p的带宽需求，delay(p)为路径p的延时需求，式(1)的目的是通过调整参数δ和σ从而使路径p达到满足不同QoS需求的目的。当δ=0时，目的是搜索满足延时需求的路径p;当σ=0时，目的是搜索满足带宽需求的路径p;当δ≠0且σ≠0时，目的是通过调整两个参数的大小，搜索到一条既满足一定的延时需求又满足一定的带宽需求的路径p。

定义1高带宽路径，即找到的路径p满足如下条件:

定义2低延时路径，即找到的路径p满足如下条件:

其中Bmin是最小带宽需求，Dmax是最大延时需求。

2.2 路由建立

2.2.1 下一跳节点的选择

首先，sink节点会向所有节点发送一个广播报文，该报文中记录了跳数、带宽和能量值，当前节点收到报文后，它会计算自己到达sink节点的跳数，本文用跳数来衡量各个节点与sink节点之间的距离，当一个源节点想要发送数据，它就会按照一定的概率来选择下一跳节点，这个概率与节点到sink的跳数和节点间的可用带宽有关，还与节点的剩余能量有关。本文将此问题抽象为基于最小费用流的组合规划问题，计算公式如下:

即节点vi根据最大的概率P(vi，vk)选择下一跳的节点vk。

其中各个字符的意义如下:P(vi，vj)，蚂蚁k将报文从节点vi传递到节点vj的概率，即节点vi选择下一跳节点的概率;λ，权值常数，0＜λ＜1，反映节点剩余能量在概率选择中所占比重的大小;τ(vi，vj)，节点vi到节点vj路径上的pheromone素浓度;d(vi，vj)，节点vi经过节点vj到达sink节点的跳数的倒数;b(vi，vj)，节点vi到节点vj路径上的可用带宽;Nvi，节点vi的所有邻居节点;α、β，参数，分别反映延时和带宽相对重要程度的参数;Evj，节点vj的剩余能量;Evu，节点vu的剩余能量。

下一跳节点采用上述方式时，会综合考虑带宽、延时、能量因素，可以根据节点vi到节点vj的可用带宽以及节点vj到达sink节点的跳数选择出高带宽路径和低延时路径，同时还考虑到了能量的因素，这样能量小的节点，被选择成为下一跳节点的概率会大大减小，从而保证算法能量消耗的均衡性。因此算法可以根据QoS需求选择相应的路径，进行数据传输。不过某些程度上增加了算法的复杂性，但是在WSN中，不可靠性一直是其最大的缺点之一，用一定的计算代价换来有一定QoS保证的数据传输，这种代价是值得的。

2.2.2 pheromone 素的更新规则

(1)局部信息素更新规则

当某个蚂蚁经过链路(vi，vj)时，链路(vi，vj)上的信息素强度根据如下公式更新:

其中 ρ为 pheromone素挥发因子，φ(根据对QoS的具体要求程度而定)为修正系数，Δτb(vi，vj)和Δτd(vi，vj)为信息素的变化量，定义如下:

定义3高带宽路径pheromone素变化大小Δτb(vi，vj)，表示pheromone素更新过程中高带宽路径上进行信息素的更新程度，计算公式如下:

其中b(vi，vj)为节点vi到节点vj路径上的可用带宽，Δwvu为节点vi到其邻居节点的所有可用带宽之和，Evj为节点vj的剩余能量，Evu为节点vu的剩余能量，Nvi为节点vi的所有邻居节点。

定义4低延时路径pheromone素变化大小Δτd(vi，vj)，表示 pheromone素更新过程中低时延路径上进行信息素的更新程度，计算公式如下:

其中Δwvj为节点vj将其收到的数据经低延时路径发送到sink节点的总代价，dvi为节点vi到达sink节点的跳数，dvj为节点vj到达sink节点跳数，Rvj为所有经过节点vj的源节点的集合，Nvi为节点vi的所有邻居节点。Hvu，vj为上述源节点各自到达节点vj的跳数的总和，Evj为节点vj的剩余能量，Evu为节点vu的剩余能量。

(2)全局信息素更新规则

当算法搜索到一条路径p时，由sink发送后向蚂蚁(backward ant)对该路径上的节点进行全局信息素更新，更新规则为:

其中ρ为pheromone素挥发因子，φ和θ(根据具体的 QoS需求而定)为调整参数，Δτb(vi，vj)和Δτd(vi，vj)分别为高带宽路径和低延时路径信息素的变化量，Bmin是路径P上的瓶颈带宽，Hp是路径p的跳数。全局信息素更新式(8)的目的是为具有较大可能的瓶颈带宽和较小路径跳数的路径分配较强的信息素，同时根据应用来调整参数θ的值来完成最小瓶颈带宽限制。

2.3 算法可行性分析

本节首先证明pheromone素的浓度τ(vi，vj)被限制在τmax和τmin之间，然后证明了算法以无限接近于1的概率搜索到最优路径。

引理1设信息素浓度τ(vi，vj)的全局最大值为τmax，则对于任意τ(vi，vj)有下式成立:

证明假定第一只蚂蚁经过任意链路(vi，vj)后，链路(vi，vj)上的增加信息量不会超过Δτ，信息素的初始值为τ0。显然在第一只蚂蚁选择链路(vi，vj)后，最大可能的信息量为(1－ρ)·τ0+φΔτ;第二只蚂蚁选择链路(vi，vj)后，则为(1－ρ)2·τ0+φ［(1－ρ)Δτ+Δτ］;其余依次类推。因此，由于信息素的挥发，在第t只蚂蚁选择链路(vi，vj)后，信息量的上限值为:

由此，当ρ∈(0，1)时，其和将最终收敛到:

引理2设信息素浓度τ(vi，vj)的全局最小值为τmin，若采用全局信息素更新规则，对于任意链路(vi，vj)∈p*且τ*(vi，vj)≥τmin(p*为最优路径)，则在搜索到最优路径p*后，该最优路径p*的τ*(vi，vj)会单调增加，且有:

引理2的证明是引理1的证明过程的重复，只不过是将引理1中的τ0用(vi，vj)来代替(vi，vj)为最优路径p*上链路(vi，vj)的信息素浓度，其中t*是搜索到最优路径p*时选择链路(vi，vj)的蚂蚁的个数。这里就不在重复定理2的证明过程。

定理1如果搜索蚂蚁个数足够多，则可保证该算法以无限接近于1的概率搜索到满足QoS需求的最优路径p*。假设p*(t)为t(0＜t＜m)只搜索蚂蚁进行搜索后发现最优路径p*的概率，则对于任意小的ε＞0和足够多的搜索蚂蚁个数m，有:

证明由于pheromone素的浓度τ(vi，vj)被限制在τmax和τmin之间，因此在蚂蚁寻找最优路径的过程中，状态转移概率p(vi，vj)＞0，且有:

其中，Nvi为节点vi的所有邻居节点之和。从而对于任意一只搜索蚂蚁均可以p(t)＞(pmin(vi，vj))h＞0的概率搜索到最优路径，其中h表示路径p的跳数，p(t)蚂蚁选择路径p的概率。假定只要有一只搜索蚂蚁搜索到最优路径即可满足要求，由此，p*(t)的一个下界为:

其中p*(t)蚁群算法搜索到最优路径的概率，对于任意小的ε＞0，搜索蚂蚁个数足够多时，有p*(t)＞1－ε，从而有p*(t)=1。

2.4 算法流程图及协议描述

(1)算法流程图和伪代码

算法伪代码如下:

(2)协议描述

图1 算法流程图

本文路由协议的主要思想是通过在源节点周期性地向目的节点发送蚂蚁，找到满足QoS(定义1和定义2)的路径，并尽可能的使网络的能量消耗最小、负载处于平衡状态。每个节点都包含所有相邻链路的剩余带宽和距离sink节点的最小跳数信息。如果由于某些环境因素或者节点自身能量耗尽出现路径断裂，那么根据式(4)从断裂节点的上一节点的邻居节点中选择概率较大的下一跳节点;如果由于某些环境因素或者节点自身能量消耗出现路径退化，那么协议会根据局部信息素浓度更新式(5)和全局信息素浓度更新式(8)自适应的调整路径上的信息素浓度，从而保证路径一直维持在比较好的状态，进行数据传输。基本过程如下:

描述1:按照网络负载的分配状态，初始化信息素浓度值，设为τ0。按照式(4)初始化每个节点的信息素表。当给定源节点集S和一个目的节点时，就周期性地在源节点释放一定数量的以该目的节点为目的地的蚂蚁分组。当蚂蚁到达某个中间节点u时，首先在该信息素表中选择满足式(4)的相邻节点作为蚂蚁移动的下一跳节点。

描述2:在蚂蚁从源节点到达目的节点的过程中，根据式(5)、式(6)、式(7)记录所访问过的节点到相邻节点的剩余带宽信息和到目的节点的跳数信息。如果链路(vi，vj)的传输延迟之和满足式(3)和剩余带宽满足式(4)，则蚂蚁发送到下一跳节点vj，同时用局部信息素更新式(5)更新链路(vi，vj)的信息素浓度。当蚂蚁运动到目的节点时，除了重复以上过程外，同时利用全局信息素更新式(8)更新路径上所有链路的信息素浓度。

描述3:根据不同的QoS需求，选择不同的路径，进行数据传输。

从以上描述可以看出，一旦搜索到最优路径，协议就能够选择满足不同QoS需求的路径。描述中每个节点的路由信息(即每个节点的信息素表)的收集的能耗相对于大量的数据传输的能耗来说很小，可以忽略不计。

3 算法仿真研究

本文采用NS2模拟仿真环境，在500 m×500 m的区域内随机部署300个传感器节点(包括基站)，基站位置(250，250)在无线传感器网络中，相对于数据无线发送接收来说，节点进行计算和储存的能耗基本可以忽略不计，所以网络的生存时间主要取决于数据传输。设定节点初始能量为50 J，发送和接收能耗均为5×10－8J/bit，空闲能耗为 4×10－9J/bit。数据融合功耗为 5×10－9J/bit，放大电路功耗为 5×10－8J/bit，通信距离为50 m～60 m。

为了验证本文所提出的给予蚁群算法的QoS路由协议的有效性，本文从多个角度对该协议进行了分析，并与传统蚁群算法和LEACH算法进行了比较。

为了获得较优的;路径平均传输时延的优化值，讨论了2个参数α，λ对路径平均传输端到端时延的影响，实验中，变化其中参数，从 0.1～0.9，另外一个个参数为剩余比例，如 α=0.3，则 λ=0.7，结果表明当两个参数在0.47附近时，路径平均传输端到端延时较优，结果如图2所示。

图2 参数－端到端延迟影响

为了获得较优的路径平均传输带宽的优化值，讨论了3个参数β，θ，λ对路径平均传输带宽的影响，实验中，变化其中参数，从0.1～0.9，其余两个参数等分剩余比例，如 β=0.6，则 λ=θ=0.2，结果表明当三个参数在0.4附近时，路径平均传输带宽较优，结果如图3所示。

图4显示了网络节点能量的总剩余率，本文算法在保证QoS要求的前提下，综合考虑了能量因素，优先选择能量较大的节点作为下一跳节点，使网络能量消耗更加均衡，使整个网络生命周期得到改善。本文算法网络能量消耗较好于LEACH协议，但是相比较传统蚁群算法而言，有明显优势。

图3 参数－平均传输带宽影响

图4 能量剩余率

图5显示了算法从开始到搜索到最优路径后的平均时延情况，由仿真曲线可以看出算法的收敛速度比较快，经过短暂的搜索过程后，平均时延逐渐下降，并最终达到稳定状态。

图5 时间步和平均延时的关系

某一时刻的路由拓扑结构图6所示。

图6 某一时刻协议路由示例

图6给出了某一时刻三种不同的路径形态:Ⅰ保证低数据传输延迟和高带宽需求的情况下，能量消耗较小的路径;Ⅱ低延迟路径，即在保证低数据传输延迟的情况下，能量消耗较小的路径;Ⅲ高带宽路径，即在保证数据可靠性的情况下，能量消耗较小的路径。

表1显示了3种算法在3种网络性能方面的表现，由于本文协议采用了基于蚁群算法的QoS保证机制，因此增加了网络的等效带宽，缩短了端到端的时延，增加了网络可靠性。

表1 网络性能统计

4 结束语

本文提出了一种WSN中基于蚁群算法的QoS路由算法，综合考虑能量、时延、带宽等因素，将如何搜索最佳路径问题抽象为组合规划问题，根据最小费用流规则定义了高带宽和低时延路径的判决条件，利用蚁群优化算法，寻找到两条不同目标函数的路径，达到满足不同QoS需求的目的。仿真实验表明，本文算法在满足不同QoS需求的同时，较好的减少了网络的能量消耗，延长了网络生命周期，但是在如何降低算法复杂度的方面需要做进一步的研究。

［1］田丽娟，张爱华，卢秀清.基于蚁群算法的无线传感器网络中心点融合算法研究［J］.传感技术学报，2010，23(4):579－581.

［2］胡彧，王静.基于蚁群算法的LEACH协议研究［J］.传感技术学报，2011，24(5):747－751.

［3］Dicaro G，Dorigo M.AntNet Distributed Stigmergetic Control for Communications Networks［J］.Vivck，1999，12(3/4):2－37.

［4］Dhillon S S，Vanmieghem P.Performance Analysis of the AntNet algorithm［J］.Computer Networks，2007，51(8):2104－2125.

［5］Camilo T，Careeto C，Silva J S，et al.An Energe-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks［C］//LNCS 4150:Proc of ANTS 2006.Heideberg:Springer，2006:49－59.

［6］Ge C，Tiande G，Wenguo Y，et al.An Improved Ant-Based Routing Protocol in Wireless Sensor Networks［C］//Proc of 2006 Int Conf on Collaborative Computing:Networking，Applications and Worksharing.Los Alamitos，CA:IEEE Computer Society，2006:442－448.

［7］Aghaeil R G，Rahman M A，Gueaieb W，et al.Ant Colony-Based Reinforcement Learing Alg-orithm for Routing in Wireless Sensor Networks［C］//Instrumentation and Measurement Technology Conference-IMTC 2007.Warsaw，Poland，May 2007.

［8］Lu Y，Zhao G，Su F.Adaptive Ant-Based Dynamic Routing Algorithm［C］//Proceedings of the 5th World Congress on Intelligent Control and Automation.IEEE，Hangzhou，China，June 2004:2694－2697.

［9］Zhang Y，Kuhn L D，Fromherz M P J.Improvement on Ant Routing for Sensor Networks［C］//Intelligence Workshop on Ant Colony Optimization and Swarm Intelligence.Sep.2004.

［10］苏淼，钱还，王煦法.基于蚁群的无线传感器网络双簇头算法［J］.计算机工程，2008，34(13):174－176.

［11］任秀丽，梁红伟，汪宇.基于多路径蚁群算法的无线传感器网络路由［J］.计算机科学，2009，36(4):116－118.

［12］郑巍，刘三阳，寇晓丽.一种面向传感器网络的蚁群优化路径恢复算法［J］.西安交通大学学报，2010，44(1):83－86.

［13］Liao W H，Kao Y，Fan C M.Data aggregation in wireless sensor networks using ant colony algorithm［J］.Networks and Computer Applications，2008，31(4):387－401.

［14］Misra R，Mandal C.Ant-aggregation for optimal data aggregation in wireless sensor networks［C］//Proc on Int Conf on Wireless and Optical Communications Neworks.New York:IEEE，2006:349－353.