基于“适应活性”的QoS组播路由算法

王　帅　朱　磊　俞　璐　林万里

(解放军理工大学通信工程学院　江苏 南京 210007)



基于“适应活性”的QoS组播路由算法

王帅朱磊俞璐林万里

(解放军理工大学通信工程学院江苏 南京 210007)

摘要自然灾害、战争等特殊应用场景下通信网络易受到物理攻击和约束条件影响，难以为用户提供稳定服务。传统的QoS路由算法基于稳态网络，在物理攻击与多约束环境下难以适用。针对这一问题，首次提出并求解了“适应活性”模型以综合衡量节点及其相连链路的动态服务性能。进而通过改进蚁群算法，提出了基于“适应活性”的QoS组播路由算法。该算法能够结合外界环境、业务需求与网络状态，综合考虑链路与节点服务性能选择路径，在继承传统蚁群算法优点的同时，解决了外界环境影响节点性能变化导致选路无法达到QoS最优的问题。MATLAB仿真结果表明，该算法能够在网络性能变化时避开低性能节点，快速有效地选择QoS最优路径。

关键词物理攻击与多约束模型QoS路由适应活性蚁群算法

0引言

随着因特网技术的不断发展，各类新型多媒体业务对网络服务质量QoS的要求也越来越高。作为解决QoS问题的一项关键技术，QoS路由算法一直作为研究热点，受到国内外专家的重视。QoS路由是一种基于网络可用资源和业务流QoS需求来选择路径的机制。Wang等已经证明，当路由选择有两个或多个QoS约束时，这样的路由选择问题就是一类NP完全问题[1]。针对这一问题，国内外学者利用蚁群算法[2]、退火算法[3]、遗传算法[4]、神经网络等启发式算法设计路由算法，取得了较好的结果。

但是，现有路由算法主要应用于稳态网络，节点服务能力差别不大且稳定不变，因此现有路由算法主要将链路的花费、时延等作为选路参数，对节点服务性能的影响考虑较少。在物理攻击和多约束条件下，通信网络受到攻击的影响以及时间、空间、频率、节点能量等多种约束条件的限制，难以为用户提供稳定的通信服务[5,6]。这就为现有的QoS路由选择算法带来了新的挑战：1) 在物理攻击和多约束环境中，节点及其相连链路(以下简称节点(链路))服务能力受环境影响波动较大，对于QoS路径选择的影响不可忽略[7]。2) 目前缺少能够在物理攻击和多约束环境下刻画节点(链路)提供QoS综合服务能力的度量指标体系。

本文针对自然灾害、战争等特殊应用场景下通信网络易受到物理攻击和约束条件影响，难以为用户提供稳定服务[8]，现有QoS路由算法无法适用这一问题，提出基于“适应活性”的QoS路由算法。本文的主要工作有：

1) 构建节点(链路)的“适应活性”模型以反映网络节点(链路)在受到物理攻击和多约束条件下，实时适应不同业务和用户需求的综合能力。

2) 构建物理攻击模型和节点服务行为模型，并以此为基础结合网络演算的相关知识求解“适应活性”模型。

3) 根据“适应活性”模型改进蚁群算法，提出一种能够结合外界环境、业务需求与网络状态，综合考虑链路与节点服务性能选择路径的QoS组播路由算法。

1“适应活性”模型的建立与求解

1.1“适应活性”建模

自然灾害、战争等特殊应用场景下通信网络节点性能波动较大，常规环境下用来分析节点性能的网络建模、分析、评价方法难以满足应急环境下的特殊需求。本文首次提出并构建的网络节点(链路)“适应活性”模型是一套节点综合服务性能指标，用以反映节点(链路)在动态变化的外界环境下，针对不同业务需求表现出的实时服务能力。“适应活性”的分析框架如图1所示。

图1　“适应活性”分析框架图

本文采用一个6元组形式化地描述节点(链路)的“适应活性”。对于一个与n条链路相连的节点k，其“适应活性”值可表述为：

(1)

1.2“适应活性”模型的求解

1.2.1物理攻击模型的建立

为求解“适应活性”中各项指标，首先需要构建物理攻击模型和多约束可行域。物理攻击是指敌方通过火力打击、电磁脉冲炸弹等手段造成通信网络设备功能失效或通信效果不稳定，是影响应急网络通信能力的主要因素[9]。本文采用如下的物理攻击模型进行分析：

a) 物理攻击到达遵循泊松过程，攻击强度服从参数为a的均匀分布；

b) 节点受攻击后具有一定的恢复能力，恢复时间服从负指数分布，其参数由攻击强度决定，节点恢复过程也可以称为攻击消化过程；

c) 设Amax(标准化后Amax为正整数)为节点能承受的最大累积攻击强度，当未消化的攻击强度累积至Amax，则节点完全损毁失效；

d) 节点在恢复期间提供部分服务，服务能力由节点服务速率刻画。

(2)

(3)

1.2.2基于网络演算的活性指标求解

本文根据网络演算的相关理论求解活性指标，网络演算是最近十多年国内外发展起来一门新的分析网络中确定排队系统的理论[10,11]，网络演算将流入节点和流出节点的流量建模成到达曲线和服务曲线，以此定量分析网络的实时变化性能。以数据型业务为例，假设业务流通过一个桶深为b(b)，以速率r(bps)释放数据的漏桶整形器整形后流入节点k，则到达曲线α(t)为：

(4)

(5)

根据网络演算，如图2所示，时延d(t)为α(t)和β(t)之间的水平距离，数据积压bl(t)为α(t)和β(t)之间的垂直距离，可用带宽bw(t)为β(t)的切线斜率。

图2　时延、带宽、积压分析

则可以求出t0时刻节点的时延为：

(6)

t0时刻节点的积压为：

(7)

本文采用时延d(t)的导函数的绝对值刻画时延抖动，旨在表示时延的即时变化幅度，时延抖动为：

(8)

丢包通常发生在缓冲区溢出或超过时延限制两种情况下，分别称作溢出丢包和超时丢包。如图3所示，B、W分别为节点丢包率的时延和容量限制。则超时丢包量为d1-d3，溢出丢包量为d2-d4，丢包率为丢包量与数据总传输量的比值。

图3　丢包率分析

1.2.3多约束可行域的构建

本文主要考虑应急通信场景下时间、空间、频率、节点能量等约束条件，如表1所示。

表1　多约束条件

(1) 时空频可行域

通过分析应急通信场景下影响网络性能的多种约束条件，构建时空频可行域 ：

当节点处于可行域内时，才有可能为用户提供服务。

(2) 剩余工作时间

节点的剩余工作时间由节点能量决定，通过节点能量衰减模型可估算出节点的剩余工作时间。节点受干扰时，能量在常规工作衰耗的基础上加速衰耗，能量衰减模型表示为：

PW(t)=PW0e-λ0te-λ(j)t

(9)

其中，PW(t)是t时刻的剩余能量，PW0(t)表示初始能量，λ(j)是与干扰强度j有关的参数。

2算法设计与分析

2.1蚁群算法介绍

蚁群算法是由意大利学者Droigo等人提出的一种进化计算方法，具有分布式计算、无中心控制、分布式个体之间间接通信等特征。在众多智能算法中，蚁群算法有较强的鲁棒性，易于与其他算法结合，且在近年来国内外学者的不断研究下，蚁群算法存在的收敛速度较慢和易达到局部最优解的问题也得到了很大改善，算法性能有了显著提高[11,12]。

蚁群算法借鉴了蚂蚁寻找食物的过程，通过引入信息素的概念以及信息素更新策略来模拟蚂蚁的间接通信机制。在解决QoS路由问题时，假设目的节点有p个，在源节点释放m只蚂蚁，每只蚂蚁会按照选路规则构建路径，寻找目的节点。在所有蚂蚁构建完回路后，对筛选出的符合约束要求的回路上的信息素进行局部更新，同时所有路径的信息素随着时间推移而蒸发一部分，这样已构建的路径上的信息素与其他路径上的信息素相比就会相对增多。由于蚂蚁倾向于选择性能较好、花费较少且信息素浓度较高的路径，那么在多次迭代之后，蚂蚁就会逐渐收敛到一条路径，即求得的解上。

2.2基于“适应活性”的改进蚁群算法

一般来说，大部分基于蚁群算法的QoS路由算法在处理多约束问题时都是在选路规则或信息素更新规则中加入QoS度量指标作为启发因素，并通过参数来控制影响大小。算法通过设置禁忌表标记已经过节点来防止产生回路，蚂蚁在选路时读取禁忌表和路径信息表来计算选路指标。但是，现有算法中禁忌表和路径信息表大都基于稳态网络和固定拓扑，且进行选路时主要考虑下一链路的花费和时延等情况，很少考虑下一节点的服务性能。但是在物理攻击和多约束条件下，网络拓扑调整变化迅速、节点服务性能波动明显，传统QoS路由选择算法很难满足路由选择的时效性和环境适应性等要求。对于整条路径而言，QoS参数根据运算性质可分为加性参数(时延、数据积压)、乘性参数(丢包率)和凹性参数(可用带宽、时延抖动、剩余工作时间)。但对于单个节点来说，QoS参数则可根据越大越好或越小越好分为正向指标(可用带宽、剩余工作时间)和负向指标(数据积压、时延、时延抖动、丢包率)。为了对节点的动态性能进行衡量，本文首先根据QoS参数性质将“适应活性”转换为一种复合型的网络节点性能指标。形式化地，通过链路(w,n)与节点w相连的节点n的适应活性值复合型性能指标可定义为：

(10)

(11)

从式(11)中可以看出，节点在选择路径时偏向于选择信息素高、链路花费少、延时小且下一节点活性高的路径，α、β、γ、θ用来调整各参数的权重，保证了算法能够在网络性能动态变化时找到符合QoS需求的路径。由于比起网络遭受攻击的间隔，算法收敛所需要的时间量级明显较小，因此活性指标只要在需要重新选路之前刷新即可，以防止选路过程中网络性能变化频繁而导致算法难以收敛。同时，在对路径信息素进行更新时，也应考虑与链路相连的下一节点的适应活性值，当蚂蚁完成一轮选路后，对符合要求的路径上的信息素按照式(12)进行更新：

(12)

对其他路径上的信息素按照式(13)进行更新：

phrm(w,n)=(1-ρ)phrm(w,n)

(13)

其中phrm(w,n)为链路(w,n)上的信息素值，ρ为蒸发系数，Q为信息素更新系数，ε、η用来调节链路时延与节点活性值在信息素更新时的影响权重。

根据上述思想，本文提出的基于“适应活性”的蚁群改进算法的具体描述如下：

初始化初始化网络中各链路的信息素强度、各仿真参数以及拓扑信息。根据网络拓扑生成禁忌表，计算并构建节点“适应活性”表。创建蚂蚁分组，启动到p个目的节点的k轮蚂蚁觅食活动，每轮派出m只蚂蚁。

Step1初始化禁忌表和路径信息，发送蚂蚁分组，根据式(11)在当前节点的下一可选节点集中选择下一节点，执行step2。

Step2当以p节点为目的节点的第j轮第i只蚂蚁到达节点s时，如果s=p，则记录路径信息并与QoS约束条件比对，当路径符合QoS需求时蚂蚁分组按原路返回源节点，转入step3。如果s≠p，则更新禁忌表和可选节点集并根据式(11)在s的可选节点集中选择下一节点设为s，重新开始step2，如果没有下一节点可选，则丢弃分组。

Step3当源节点收到返回的第j轮第i只蚂蚁分组时，如果i=m，则本轮选路完成。在本轮选出的所有路径中找出最优路径(根据业务需求可以是时延最小或花费最小等)，并按照式(12)刷新所有经过的路径的信息素强度值，用式(13)刷新其他没有经过的路径的强度值，将源节点设置为当前节点，当j≠k时转入step1，否则转入step4。如果i≠m，则将源节点设置为当前节点，转入step1。

Step4判断节点p是否是目的节点集中的最后一个节点，如果不是，则从目的节点集中选择下一节点作为算法目的节点p，初始化网络中各链路的信息素强度，转入step1。否则转入step5。

Step5整理各轮选路的最优路径结果，并统计比对，找出最符合要求的路径绘制组播树。

3仿真结果与分析

本节使用Matlab模拟物理攻击和多约束条件下的网络环境，并对标准蚁群系统算法和本算法进行仿真实现，进而通过对比算法结果来验证本算法的有效性。首先在空间约束为10km的正方形区域中生成25个节点的随机网络。选择10km作为空间约束，一是符合战场通信网络规模，二是可使链路时延单位数量级与节点时延相同，在之后的分析中可以通过比对不同算法选择路径的总时延验证本文算法兼顾节点与链路进行选路的特点。设置仿真参数α=2、β=2、ε=1、η=0.5、Q=5×10-5初始信息素为1，路径花费cost以跳数衡量。从源节点发送漏桶型数据，发送速率r=6(bit/s)，桶深b=10(bit)。每轮释放蚂蚁50只，算法迭代30轮，则选路结果如图4所示。

图4　标准蚁群系统算法选路结果

如图4所示，节点13为源节点，节点9、12、20、23为目的节点。由于路径花费为跳数，路径时延=节点距离/数据传播速度，则该选路问题可以简化为一个最短路径求解问题。可见标准蚁群算法所选路径为最优解。此时在不考虑通信静默的情况下，按照1.2.1节中的攻击模型对网络节点施加物理攻击。攻击频率λ=1次/min，标准化后单次攻击强度服从a=3的均匀分布，节点修复速率μ=2/min。为了对比选路结果，假设中间节点14能够承受的最大累积攻击强度A=5，其余节点能够承受的最大累积攻击强度A=10，节点能够提供的最大服务速率R=10(bit/s)，按照1.2.2节的分析和式(10)构建节点(链路)“适应活性”表。物理攻击开始5分钟后，同时运用标准蚁群算法与本算法进行选路。由于标准蚁群系统算法并不考虑环境影响与节点性能，因此选路结果仍为图4所示，而本算法选路结果如图5所示。

图5　基于“适应活性”的QoS组播路由算法选路结果

fwn表示通过链路(w,n)与节点w相连的节点n的复合适应活性值。则取活性表的相关部分如表2所示，结合比较图4与图5可知，节点14在受攻击条件下“适应活性”值较低，说明其在时延、积压、丢包率等服务性能上相比其他节点较弱。在综合考虑链路花费、链路时延和下一节点“适应活性”的情况下，算法选路绕过节点14，选择花费为3的路径[13,6,8,12]。而其他三条路径相关节点“适应活性”值相差不大，本文算法选路结果与标准蚁群系统算法选路结果相同。由于稳态环境下各个节点之间的“适应活性”指标可认为是相等的，则上述实验结果证明本算法可适用于稳态环境，且在物理攻击和多约束下可以根据节点“适应活性”选择更优的QoS路径。

表2　部分节点(链路)活性值

标准蚁群算法与本算法在组播树费用收敛，单次迭代花费、时延收敛情况的对比结果如图6、图7、图8所示。

图6　组播树费用收敛曲线对比

图6显示了选路时符合QoS需求，目的节点正确的路径构成的组播树的总费用。算法在一开始时让蚂蚁充分扩散以避免陷入局部最优解。随着第一轮迭代结束，算法找出最优解并更新信息素，使后续蚂蚁逐渐收敛至最优路径上。图6中标准蚁群算法约在第125只蚂蚁时算法收敛，本算法约在第100只蚂蚁处收敛。由于本算法在选路时避开了活性值较低的节点14，因此最优组播树花费比标准蚁群算法选出的最优组播树花费略高。

图7　路径费用变化情况对比

图8　路径时延变化情况对比

图7、图8为每一轮迭代中初次构建的组播树的费用和时延，相比于标准蚁群系统算法，本算法最终构建的最优组播树绕开了节点14，因此费用略微增多。但由于物理攻击下节点14活性较低，所以本算法构建的最优组播树总体延时反而小于标准蚁群算法构建的经过节点14的最短路径时延。综上所述，本算法具有和标准蚁群算法相差不多的收敛速度和求解能力，但在选路时能够结合外界环境、业务需求与网络状态，综合考虑链路与节点服务性能选择路径。因此能够有效解决物理攻击与多约束条件下的QoS路由组播问题。

4结语

本文提出并求解了节点(链路)的“适应活性”模型以反映网络节点(链路)在外界物理攻击和多约束条件下，实时适应不同业务和用户需求的综合能力。在此基础上，本文对标准蚁群算法进行改进，提出了基于“适应活性”的QoS组播路由算法，用以解决物理攻击和多约束条件下网络QoS路由问题。仿真证明了该算法能够结合外界环境、业务需求与网络状态，综合考虑链路与节点性能选择路径，克服了传统蚁群算法局限于求解稳态网络的缺点。

参考文献

[1] Wang Z,Crowcroft J.Quality of service for supporting multi-media applications[J].IEEE JSAC,1996,9(14):1228-1234.

[2] Dorigo M,Stützle T.Ant colony optimization:overview and recent advances[M].Handbook of metaheuristics.Springer US,2010:227-263.

[3] Xu Y,Qu R.Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighborhoods[J].Journal of the Operational Research Society,2011,62(2):313-325.

[4] Zafar S,Soni M K.Trust based QOS protocol (TBQP) using meta-heuristic genetic algorithm for optimizing and securing MANET[C]//Optimization,Reliabilty,and Information Technology (ICROIT),2014 International Conference on.IEEE,2014:173-177.

[5] Zakaria A H,Saman M Y M,Noor A S M,et al.Performance Analysis of Mobile Ad Hoc Networks Using Queuing Theory[C]//Proceedings of the First International Conference on Advanced Data and Information Engineering (DaEng-2013).Springer Singapore,2014:555-562.

[6] Zhang L,Liu J,Yang K.Quality of service modelling of virtualized wireless networks:A network calculus approach.Mobile Networks and Applications[J].Mobile Network and Applications,2014,19(4):572-582.

[7] Badenhop C W,Mullins B E.A black hole attack model using topology approximation for reactive ad-hoc routing protocols[J].International Journal of Security and Networks,2014,9(2):63-77.

[8] Peng S,Wang G,Hu Z,et al.Survivability modeling and analysis on 3D mobile ad-hoc networks[J].Journal of Central South University of Technology,2011,18(2):1144-1152.

[9] Yao F,Xu R,Liang Q,et al.Some key issues on modeling and simulation of military communication network[C]//Computer Science and Electronics Engineering (ICCSEE),2012 International Conference on.IEEE,2012,1:532-535.

[10] Fidler M.Survey of deterministic and stochastic service curve models in the network calculus[J].Communications Surveys & Tutorials,IEEE,2010,12(1):59-86.

[11] Kanan A,Eldos T,AlKahtani M.Mobile Ad Hoc Networks Routing Using Ant Colony Optimization[J].World of Computer Science and Information Technology Journal (WCSIT) ISSN,2013,20(1):2221-0741.

[12] Metri R,Agrawal S.Ant colony optimization algorithm based an intelligent protocol to improve QoS of MANETs[C]//Circuits,Systems,Communication and Information Technology Applications (CSCITA),2014 International Conference on.IEEE,2014:121-125.

A QoS MULTICAST ROUTING ALGORITHM BASED ON ‘ADAPTIVE LIVING’

Wang ShuaiZhu LeiYu LuLin Wanli

(CollegeofCommunicationsEngineering,PLAUniversityofScienceandTechnology,Nanjing210007,Jiangsu,China)

AbstractIn special application scenarios such as the natural disasters and the wars, communication networks are difficult to provide stable services to users because it is prone to the effects of physical attacks and multi-constraints. Traditional QoS routing algorithms are based on steady network, they are no longer suitable under the condition of physical attacks and multi-constraints. Aiming at this problem, in the paper we put forward and calculate for the first time the ‘adaptive living’ model to comprehensively measure the dynamic service performance of network nodes and their connecting links. Furthermore, by improving the ant colony optimisation algorithm we put forward an ‘adaptive living’-based QoS multicast routing algorithm. The algorithm can consider comprehensively the selection path of the link and the service performance of nodes in combination with the external environment, service requirements and network status, while inheriting the advantage of traditional ant colony optimisation, it solves the problem that the external environment affects the variation of node performance which in turn causes the path selection cannot reach QoS optimum. Result of simulation on MATLAB shows that the algorithm can keep away from low performance nodes when the networks performance varying, and can fast and effectively select QoS optimal path.

KeywordsModels of physical attacks and multi-constraintsQoS routingAdaptive livingAnt colony optimisation

收稿日期：2014-12-30。2014年江苏省自然科学基金项目(BK20 141071)。王帅，硕士，主研领域：网络性能分析，网络抗毁性。朱磊，教授。俞璐，副教授。林万里，硕士。

中图分类号TP393

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.066