基于改进蚁群优化算法的网络服务质量路由算法

马世欢，李 伟

(河南工业职业技术学院计算机工程系，河南 南阳 473000)

0 引言

随着计算机信息技术与通信技术的飞速发展，无线传感器网络在军事、工业监控、环境监测等领域得到了成功应用［1］。路由技术是无线传感器网络的核心技术，传感器节点的能量、计算能力有限，再加上网络环境的不稳定性，如何对无线网络路由算法进行优化和设计，以满足用户对网络服务质量(Quality of Service，QoS)要求成为当前研究热点［2-3］。

根据无线传感器网络的特点，许多国内外学者对无线路由算法进行了深入的研究，取得一些研究成果［4］。传统QoS 的路由算法没有考虑无线网络的特殊性，如实时性差、外界干扰大等，因此不能直接应用于无线网络路由设计和优化中［5］。传统无线网络路由算法只考虑单一的QoS 指标，如网络延时、端到端带宽、网络丢包率、延时抖动等［6］，由于单一指标不能全面、准确描述无线路由性能，因此难以建立整体性能最优的数据转发路由，鲁棒性比较差，应用范围受限［8］。针对单一指标存在的不足，根据组合优化理论，一些学者提出了一些多指标QoS 的无线网络路由算法，如文献［9］提出了基于遗传算法的多约束QoS 路由算法，综合考虑无线网络的带宽、延时、延时抖动等数据链路指标，将QoS 路由问题看作是一个多约束的优化问题，通过全局搜索能力强的遗传算法进行求解，找到了最优数据转发路由方案，一定程度上解决了传统路由算法存在的不足。随后有学者提出采用蚁群优化算法(Ant Colony Optimization，ACO)、混沌遗传算法、量子遗传算法、文化算法等对无线网络路由算法进行优化，提高QoS 路由算法的求解速度［10-13］。

为了获得更加理想的QoS 路由算法，本文提出一种基于改进蚁群优化算法的QoS 路由算法MACO)，根据无线网络的路由特点，对标准蚁群算法进行相应的改进，最后通过仿真实验测试其性能。实验结果表明，本文算法减少了网络丢包率和平均延时，提高了网络通信的质量。

1 QoS 路由问题描述

1.1 QoS 参数选择

QoS 指无线网络为用户提供的服务质量，随着无线网络范围不断扩大，不同领域的QoS 参数不相同［14］。结合无线网络特点，可以采用一个带有权重信息的无向连通图对无线网络结构进行描述，G=＜V，E ＞，其中V 表示网络中所有节点的集合，E 为所有链路集合，P(s，d)表示从源节点s 到目的节点d的一条路经。本文选择的QoS 参数主要包括带宽(B)、端到端的延时(D)、数据包丢失率(L)、时延抖动(G)、链路花费(C)等［15］。

1.2 QoS 路由数学模型

设s 到d 之间的路径带宽满足:

其中，B 为要求最小带宽。

延时满足:

其中，D 为要求最大延时。

丢包率满足:

其中，L 为要求的最大丢包率。

时延抖动满足:

其中，J 为要求的最大时延抖动。

花费满足:

多约束路由的主要目标是在满足QoS 参数带宽、延时、时延抖动、丢包率约束条件下，寻找一条最优服务路径，同时保证链路花费少，收敛于最优路径速度快，且有较高的QoS 满意率。

2 改进蚁群算法的QoS 路由算法

2.1 标准蚁群算法

ACO 算法是一种性能优良的启发式优化算法，采用正反馈机制实现分布式全局优化，通过信息素不断更新，最终收敛于最优路径上。采用标准蚁群算法来对QoS 路由问题进行求解时，首先将蚁群起始点与食物转换成QoS 路由的源节点与目标节点，然后模拟蚁群觅食机制最终得到最优的路由。

状态转移概率的计算如下。

蚂蚁k 在t 时刻由节点i 到节点j 的概率计算公式为:

其中，τij(t)为节点i 与j 的信息强度;ηij(t)为启发因子;allowedk为可选的节点;α 为信息启发因子，β 为期望启发因子［16］。

蚂蚁在寻找路径的过程中会不断留下信息素，当信息素累积过多时，启发信息就会受到影响，所以信息素需要不断更新，各路径下的信息素全局和局部更新方式为:

其中，ρ 为信息素挥发系数;Δτij(t)为新增加的信息素总和，为遗留信息素总和，其计算公式如下:

其中，Q 为信息素强度;Lk为蚂蚁k 行走的所有路径长度之和。

2.2 蚁群算法的改进

1)状态转移概率的改进。网络路由优化问题具有自身的特殊点，选择路由节点时，需考虑带宽、端到端的延迟、数据丢包率以及时延抖动，因此在进行节点的状态转移过程中，将延时和延时抖动引入到状态转移概率计算中，具体为:

其中，q0为［0 1］之间的常数，q 为［0 1］之间的随机数。

启发因子ηij(t)为延时和延时抖动和倒数的函数，这样数据可以选择质量更好的路由进行转发。

2)信息素更新策略的改进。为了提高算法的收敛速度，本文在进行信息素更新策略时，同时考虑信息素的局部和全局更新。信息素更新思路具体为:在蚂蚁k 经过路径(i，j)时，仍根据式(8)进行信息素局部更新;其所经过全部路径的信息素全局更新方式为:

对其它未经过的路径上的信息素更新方式为:

其中，ρ1仍然为信息素的保留系数，Q=AQ1+BQ2，Q1表示路径(i，j)和节点i 上的丢包率和延时抖动之和，Q2表示路径(i，j)上的时延，B 为总带宽。

2.3 算法工作步骤

1)根据QoS 网络的约束条件，删除不满足条件的网络节点，建立一个新的网络拓扑图。

2)初始化网络，初始各链路上的信息素以及蚁群算法相关参数值，将蚂蚁置于源节点上。

3)每只蚂蚁根据式(10)选择路径，根据式(8)对路上信息素进行局部更新，根据式(11)和式(12)对路上信息素进行全局更新。

4)如果迭代次数超过最大迭代次数，搜索终止，输出最优路由选择方案;不然，迭代次数增加，转至步骤3)继续搜索。

3 仿真实验

3.1 仿真环境

为了测试改进蚁群优化算法的QoS 路由算法的性能，在Intel 4 核3.0 GHz 的CPU，4 GB RAM，Windows 7 操作系统的计算机上，采用NS2 仿真软件进行仿真实验。仿真参数如表1 所示，网络的拓扑结构如图1 所示。

表1 仿真参数设置

图1 网络拓扑结构

3.2 对比算法及性能评价标准

为了使MACO 算法的结果更具说服力，选择遗传算法(GA)［17］进行对比实验，MACO 算法参数设置:α=2，β=2，Q=50，ρ=2.5，GA 的参数设置为:交叉概率为0.85，变异概率为0.05，种群规模为20，最大迭代次数为500，选择平均延时、包投递率对算法性能的优劣进行评价。

3.3 结果与分析

3.3.1 平均延时对比

GA 和MACO 算法的平均延时变化曲线如图2所示。从图2 可以知道，随着仿真时间的增加，MACO、GA 路由的平均延时不断减小，MACO 算法的平均延时下降比较平缓，而且一直小于GA 的平均延时，这主要是由于MACO 算法具有更好的搜索能力，找到性能更优的数据转发路由，使网络拓扑结构十分稳定，变化比较小，减少了数据包从源节点传输目标节点的平均延时，对比结果表明，MACO 算法选择的数据路由响应速度更快，建立的链路路由质量更高，可以满足用户服务质量要求。

图2 MACO 算法与对比算法的延时对比曲线

3.3.2 包投递率对比

GA 和MACO 算法的包投递率变化曲线如图3所示。从图3 可以知道，随着仿真时间的增加，MACO、GA 路由的包投递率不断上升，MACO 算法的包投递率一直高于GA 的包投递率，这主要是由于MACO 算法建立比较理想的数据转发路由，减少了数据的丢包率和网络拥塞概率，保证了数据包转发的可靠性。

图3 MACO 算法与对比算法的包投递率对比曲线

4 结束语

为了提高无线网络通信的可靠性，节约通信成本，本文提出了一种基于改进蚁群优化算法QoS 路由算法，并通过仿真对比实验对算法的性能进行分析。实验结果表明，改进蚁群优化算法在满足网络通信质量要求的条件下，不仅大幅度减少了网络的平均延时，加快了数据传输速度，而且提高了包投递率，降低了网络的丢包率，在无线网络中具有广泛的应用前景。

［1］Ehsan S，Hamdaoui B.A survey on energy-efficient routing techniques with QoS assurances for wireless multimedia senor networks［J］.IEEE Communications Surveys ＆Tutorials，2012，14(2):265-278.

［2］葛连升，江林，秦丰林.QoS 组播路由算法研究综述［J］.山东大学学报(理学版)，2010，32(1):55-65.

［3］Denouri D，Balasingham I.Traffic differentiation based modular QoS localized routing for wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2011，10(6):797-809.

［4］Jakllari U，Eidcnbcnz S，Hengartner N，et al.Link positions matter:A non-commutative routing metric for wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(1):61-72.

［5］Hou R，Lui K S，Baker F，et al.Hop-by-hop routing in wireless mesh networks with bandwidth guarantees［J］.IEEE Transactions on Mobile Computing，2012，11(2):261-277.

［6］王锋.基于遗传算法的多参数QoS 网络路由算法［J］.计算机与数字工程，2014，42(5):785-786.

［7］王浩，曹仲伟.基于遗传蚁群算法的QoS 路由约束问题的研究［J］.湖北工业大学学报，2011，26(2):71-73.

［8］钟李全，孟李林，柯冰，等.基于分级结构的优化QoS 路由算法［J］.光通信研究，2014，184(4):31-33.

［9］刘欣，李飞，郑宝玉.基于量子遗传算法的多约束QoS路由算法［J］.南京邮电大学学报(自然科学版)，2011，31(2):31-35.

［10］何志东，俞鹤伟，陶铭.双向搜索蚁群算法在QoS 单播路由中的应用［J］.计算机工程与应用，2011，46(31):106-108.

［11］王镇，刘学军.WSN 中基于蚁群算法的QoS 路由协议［J］.传感技术学报，2011，24(11):1625-1631.

［12］于淼，白光伟，沈航，等.无线传感器网络启发式QoS 路由协议［J］.计算机科学，2014，41(7):171-177.

［13］叶仕通，万智萍.高效的遗传蚁群组合算法在QoS 路由上的运用［J］.重庆大学学报，2013，36(10):82-88.

［14］Yen Yun-sheng，Chao Han-chieh，Chang Ruay-shiung，et al.Flooding limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs［J］.Mathematical and Computer Modeling，2011，53(11-12):2238-2250.

［15］Leela R，Selvakumar S.Genetic algorithm approach to dynamic multiconstraint multi-path QoS routing algorithm for IP networks［J］.International Journal of Communication Networks and Distributed Systems，2010，5(4):392-411.

［16］万博，卢星，陈立云，等.基于改进蚁群算法的拥塞规避QoS 路由算法［J］.计算机工程，2011，37(20):49-51.

［17］张月华，孙学梅，张明伟，等.基于文化算法的无线Mseh网QoS 路由算法［J］.计算机应用与软件，2012，29(11):264-268.