刘 静，李 琦，吴华伟

（1.湖北文理学院 机械与汽车工程学院，襄阳 441053；2.汽车零部件制造装备数字化湖北省协同创新中心，襄阳 441053；3.湖北文理学院 学工处，襄阳 441053）

0 引言

无线多媒体传感器网络在战场监控、环境监测、智能家庭护理和目标跟踪等方面得到了越来越多的广泛应用。但同时无线传感器网络存在资源受限、数据高度冗余，需要不同的QoS保障，使其路由问题变得复杂[1]，在满足QoS要求的无线传感器网络中，不仅要保证网络的连通性，还要满足用户对线路的带宽、延迟、延迟抖动、跳数、能量均衡等要求，故多约束QoS无线传感器网络路由问题成为研究热点。QoS网络路由问题是一个NP-hard问题[2]，因而传统算法对于此类问题面临计算复杂度高、计算时间长等问题，为此利用启发式算法成为学者们的首选，如蚁群算法[3,4]、遗传算法[5,6]、贪婪算法[7]、免疫算法[8]、模拟退火算法[9]、量子遗传算法[10]、粒子群算法[11]等。特别对蚁群算法的研究，将路由优化引向深入。

蚁群算法是1991年意大利学者Dorigo M等人[12]通过模拟自然界蚂蚁寻食的行为提出的一种全新的启发式算法。该算法不依赖于具体的数学描述，具有全局优化、自组织、自学习的能力和本质上的并行性等优点，是一种性能优良的启发式优化算法。该算法在求解复杂优化问题，特别是离散优化问题方面有很大的优越性和广阔的应用前景，但存在易陷入局部最优和前期搜索效率较低等缺点[13]。

针对蚁群算法缺点，本文结合无线传感器网络路由问题的特点，提出了一种基于蚁群算法的混合优化算法对无线传感器网络路由问题进行优化。该算法在初始化链路信息素浓度时，根据链路方向向量与链路起点指向目的节点的方向向量间夹角大小进行初始化赋值，减少蚂蚁前期寻路的盲目性；将交叉、变异、选择等遗传算子引入算法中，进行信息素更新之前对路径的调整或摄动，提高蚁群算法所获得路径的质量并扩展搜索区域；应用多属性决策方法利用加权法将延迟、延迟抖动、跳数等属性组合成路径评价函数，从而更加全面反映各条路径的综合信息。

1 路由网络模型

考虑链路带宽、延迟、延迟抖动等约束的多QoS路由问题，即在无线传感器网络中找到一条从源节点到目的节点满足带宽、延迟、延迟抖动等诸多约束的最优路径。无线传感器网络可以抽象为一个无向赋权图G=(V,E)进行研究，其中V表示无线传感器网络的节点集合，用V=(v1,v2,…,vn)表示，其中，n为无线传感器网络节点的数目，E表示由传感器节点与节点之间构成的链路集合。假设边ei,j=(vi,vj)∈E，表示由传感器节点(vi,vj)构成的一条无线多媒体传感器网络的链路，在图G中，从源节点vs到目的节点vd的一条路径用P来表示，即

定义1：设B(P)为路径上链路带宽最小值；D(P)为路径上链路的时延之和；J(P)为路径上链路时延抖动之和。则多QoS约束路由问题可描述为在无线传感器网络中寻找一条满足下列约束条件的最优路径：

定义2：在无向赋权图G=(V,E)中，源节点vs到目的节点vd的所有可行路径中，评价函数值最大的路径称为多QoS约束最优路径，其对应的路径P即为满足QoS约束条件的最优路径。

评价函数是用来评价路径好坏的标准，它将直接反映路径的优劣。本文将路径时延，时延抖动、跳数作为路径评价指标，采用加权法获得路径k的评价函数，如式(1)所示：

上式中设定Hmax为最大路径跳数，H(P)为路径跳数。从上述评价函数可知，只有时延最小，时延抖动最小且跳数最少的路径是最优的，这基本反映了用户的综合要求。

2 基于混合优化算法的多QoS约束路由优化

2.1 信息素初始化

基本蚁群路由算法的缺点之一是初始化所有链路的概率均设置成相等，导致前向蚂蚁在初始状态时寻路存在盲目性。为此，本文将在对每条链路赋予初始信息素C0基础上，根据链路方向对链路信息素浓度进行修正，从而获得链路ei,j=(vi,vj)上的初始信息素浓度τij(0)，具体公式如下：

其中θ为R1与R2间的夹角，R1表示为节点vi指向它的邻域节点vj的方向向量，R2示为节点vi指向目的节点vd的方向向量。式(2)表示R1与R2同向时，才为链路ei,j=(vi,vj)赋正值，否则赋零，即从节点vi开始选择下一跳节点时，只考虑前向节点。

2.2 算法设计

无线传感器网络混合路由算法的具体算法步骤如下：

步骤1：初始化参数。

首先进行参数的初始化，如节点规模（蚂蚁数量）n、性价比因子α、诱发函数因子β、性价比挥发因子ρ、性价比总量Q、迭代次数初值iter=1。

步骤2：构建解空间。

以网络源节点作为n个蚂蚁的寻路起点，对蚂蚁k而言，利用下式计算

ηij(t)为诱发函数，表示从节点i到节点j传输数据的时延大小；α为性价比因子，越小的α值表示性价比在选择下一跳过程中影响越小；β为诱导函数因子，越小的β值表示诱发函数在选择下一跳过程中的影响越小。Allowed(i)表示节点i可访问的邻域节点集合。初始信息素浓度采用式(2)计算获得。利用轮盘赌的方法选出蚂蚁k从节点i到节点j的路线（即要访问的下一个节点j）。以此方法，直到蚂蚁k寻到目的节点。

步骤3：对上述n个路由方案（染色体），应用遗传算法进行交叉、变异操作，评价各方案，采用轮盘赌与最优保持策略选择n个新种群，并对信息素浓度进行更新。

步骤3.1：交叉操作。为了避免交叉操作产生非法路径，采用了如下单点交叉操作：根据交叉率在父代中随机选取若干染色体对进行交叉操作，比较两个父代染色体，并找到所有相同的基因（即节点），随机从这些相同基因中选取一个作为交叉点，交换从交叉点开始的后续所有基因。例如父代染色体（3 6 12 45 21 5）和（9 10 43 12 7 21 73 14）包含两个相同基因12与21，随机选择基因12作为交叉点，则交叉后得到子代个体为（3 6 12 7 21 73 14）与（9 10 43 12 45 21 5）。

步骤3.2：变异操作。为避免产生非法路径，采用如下变异过程：根据变异率任选取一个染色体，在该染色体中随机选择节点p，并将节点p之前的所有节点加入到子代中，然后以节点p为起点，以目的节点为终点，使用随机走动法在前向节点集中找到一条不含有节点p之前所有节点的随机路径，将该路径加到子代的后面。

步骤3.3：选择操作。利用评价函数Fi评价路径i转发数据的优劣，采用轮盘赌与最优保持策略选择n个新种群作为蚁群算法中路径信息素浓度更新的较好路径。

其中：

步骤5：完成一次迭代后，记录最优路径的评价函数值与平均评价函数值。若连续多次计算结果没有明显改善（相邻迭代结果之差小于ε），则输出最优解；否则，iter=iter+1，清空蚂蚁所经路径的记录表并返回到步骤2。

3 仿真实验

仿真实验采用Waxman提出的随机图模型生成仿真网络拓扑图[15]。该模型在平面[a,b]上，采用泊松分布随机布置节点。本文生成的是234个节点随机布置在150×150范围内，节点之间的通讯距离为20，节点的度为2。实验时，带宽设置为1～10之间的随机数，链路间的时延是[8,16]间的随机数，链路间的时延抖动为[0.01,0.1]之间的随机数，假设QoS需求Bmin为5；Dmax为170，Jmax为1；Hmax为100。设置试验中蚁群算法的性价比因子α=1，诱发函数因子β=5，性价比挥发因子ρ=1，ω1、ω2、ω3分别设定为0.6、0.2、0.2。遗传算法的参数设置为：遗传代数为50，种群大小为20；交叉率为0.8；变异率为0.1。设定源节点是节点188，汇聚节点是节点145，得到的优化路径为[188, 191, 1, 35, 230, 176, 91, 31, 156, 42, 11, 161, 145]。

为了进一步验证本文设计算法的有效性，应用路径时延和运算时间作为路由问题求解主要考察指标。分别应用遗传算法[16]、蚁群算法[17]以及遗传-蚁群算法[18]对上述案例进行计算，对应设置与本文设计的混合算法相同的参数值，则优化结果对比情况如表1所示。在5次随机计算过程中，本文设计的混合算法所求最优路径时延均值与计算时间都要优于GA算法、ACO算法、GA-ACO算法，并且能较好地解决大规模无线传感器路由问题。

表1 算法优化结果对比表

4 结论

本文基于无线传感器路由问题特性分析，提出了基于蚁群算法的无线传感器网络混合路由求解算法。该算法引用了链路方向的概念，并将遗传算法的交叉、变异及选择算子引入算法中，同时应用多属性决策方法将路径时延、时延抖动、跳数三个路径评价属性整合为路径考察指标，从而使算法具有较好的全局搜索能力与局部搜索能力，且能综合反映路径的优劣。仿真实验表明：本文所设计算法要优于蚁群算法，遗传算法以及遗传-蚁群算法。并且算法具有较强的灵活性，只需要改变路径时延、时延抖动、跳数三个路径评价属性的权重就可反映不同用户对网络服务要求的偏好。

图1 仿真网络拓扑图

[1] Aky ildiz I F, Melo dia T, Chow dhur y K R. A surveyon w ir eless multimedia sensor netw orks[J].omputer Netw o rks,2007, 51(4)：921-960.

[2] 陈年生,李腊元,等.基于混合遗传算法的QoS多播路由算法[J].计算机应用.2005,25(7);1485-1487.

[3] Rahman MA,GhasemAghaei R, El Saddik A, et al. M-IAR： biologically inspired routing protocol for wireless multimedia sensor networks[A].proceedings of the 2008 IEEE Instrumentation and Measurement Technology Conference (IMTC '08),Victoria, British Columbia, Canada,[C].IEEE Computer Society Press, 2008.

[4] 柯宗武,李腊元,陈年生.无线多媒体传感器网络QoS路由博弈算法[J].武汉理工大学学报(交通科学与工程版).2009,33(02)：295-298.

[5] 凌启东,马欣荣,詹新生.基于遗传算法的WSID网络路由建模与优化[J].江苏建筑职业技术学院学报,2012,1(1)：55-58.

[6] 王征应,石冰心.基于启发式遗传算法的QoS多播路由问题求解[J].计算机学报,2001,24(1)：56-61.

[7] He Tian, Stankovic JA,Lu CY, et al. A spatiotemporal communication protocol for wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(10)：995-1006.

[8] 刘芳,冯小军.免疫组播路由选择算法[J].计算机学报.2003,26(6)： 676-681.

[9] 胡世余,谢剑英.基于模拟退火的QoS路由算法[J].计算机工程, 2004,30(5)：109-110.

[10] 唐义龙,潘炜,李念强,等.基于量子遗传算法的无线传感器网络路由研究[J].传感器与微系统.2011,30(12)：68-70.

[11] 刘敏,徐世军,孙思毅,等.基于QoS-PSO的无线传感器网络路由算法[J].同济大学学报.2010,38(12)：1846-1850.

[12] Colorni A, Dorigo M, Maniezzo V.Distributed Optimization by Ant Colonies[A].Proceedings of the First European Conference on Artificial Life,1991.Paris, France：Elsevier Publishing, Amsterdam[C].1991：134-142.

[13] 王菁,刘三阳,李祖猛.基于改进蚁群算法的QoS单播路由优化[J].系统仿真学报,2009,21(19)：6081-6085.

[14] 石钊,葛连升.一种解多QoS约束组播问题的改进蚁群算法[J]. 山东大学(理学版),2007,42(9)：41-45.

[15] Waxman BM.Routing of multipoint Connections[J]. IEEE Journal on Selected Areas in Commuciations,1988,6(9)：1617-1622.

[16] Neeraj Kumar，Rahat Iqbal，Naveen Chilamkurti. An ant based multi constraints QoS aware service selection algorithm in wireless Mesh networks[J].Simulation Modelling Practice and Theory,2011,19(9)：1933-1945.

[17] LEELA R,THANULEKSHMI N,SELVAKUMAR S. Multiconstraint Qos unicast routing using genetic algorithm (MURUGA)[J]. Applied Soft Computing,2011,11(2)：1753-1761.

[18] Zeng X, Tu Z Y.A study on the optimization of the constrained routing problem based on genetic-ant colony algorithm[J].IEEE Computer Society,2010,218：860-863.