多约束QoS组播路由

多约束QoS组播路由（通用5篇）

多约束QoS组播路由 篇1

0 引 言

随着高速网络技术的发展, 与多媒体相关的实时业务应用大量兴起[1], 而有效的组播路由[2]是实现多媒体通信的关键技术。传统的组播通信大多采用“尽力而为”, 没有很好地考虑服务质量QoS (Quality of Service) [3]。随着网络的发展, 多媒体通信对网络的服务质量QoS提出了越来越高的要求, QoS组播路由问题应运而生。QoS组播路由问题是指在分布的网络中寻找最优路径[4], 要求从源节点出发, 历经所有的目的节点, 找到一条满足网络路由中延时、带宽、丢包率等约束条件且花费最小的网络路径。Wang Z 等学者已经证明了包含两个及以上约束条件的QoS网络路由是一个NP完全问题[5]。

蚁群算法 (Ant Colony Algorithm, ACA) 是上世纪90年代意大利学者 M.Dorigo和V.Maniezzo等人通过模拟自然界蚂蚁寻径的行为提出的一种全新启发式算法, 它被广泛用于解决各种NP完全问题[6]。现利用一种基于自适应蚁群优化算法, 提出考虑网络链路利用率的QoS多约束条件下组播路由解决方法。

1 基本蚁群算法

蚁群算法是一种新近发展起来的、模拟蚂蚁群体觅食行为的仿生优化算法。蚂蚁在寻找食物的运动过程中, 能在其经过的路径上分泌一定数量具有气味的称为信息素的物质进行信息传递, 并指导自己的运动方向。某一路径上走过的蚂蚁越多, 此路径上蚂蚁留下的信息素轨迹也越多, 则后来蚂蚁选择该路径的概率也越大, 从而更增加了该路径被选择的可能性。同时, 路径上的信息素也会随着时间的流逝而不断地挥发, 这种机制所得蚂蚁不完全受过去经验的约束, 有利于蚂蚁向新的路径搜索。随着时间的推移, 蚂蚁就会找到由蚁巢到食物源的最优路径。该算法采用了正反馈并行自催化机制, 具有较强的鲁棒性、优良的分布式计算机制、易于与其他方面结合等优点。

蚁群算法利用随机策略, 使得进化速度较慢, 收敛速度不理想;利用正反馈强化性能较好的解, 但导致当前不被选用的路径, 往后被选用的概率越来越小, 使算法在某些局部最优解附近徘徊, 出现停滞现象, 而且挥发系数ρ的存在会使那些从未搜索到的路径上的信息素量逐渐减少到0, 从而降低算法的全局搜索能力。若ρ过大, 会使以前搜索过的路径被再次选择的可能性过大, 影响算法的全局搜索能力, 易于陷入局部最优解;若ρ过小, 虽然可以提高算法的全局搜索能力, 但会使算法的收敛速度降低。1996年Gambardella和Dorigo提出了一种修正的蚁群算法 (ACS) [7], 该算法对信息素的更新策略作了相应的改进, 即使用:

(1) 局部信息更新, 蚂蚁从城市i转移到城市j后, 路径上的信息素按式 (1) 进行更新:

undefined

式中:ξ∈ (0, 1) , τo为常数。

采用局部信息更新策略减小了已选择过的路径再次被选择的概率, 提高了算法的全局搜索能力。

(2) 全局信息更新, 针对全局最优解所属边按式 (2) 进行信息素更新:

τij (t+n) = (1-ρ) τij (t) +ρΔτundefined (t) , ρ∈ (0, 1) (2)

式中:Δτundefined (t) =1/Lgb;Lgb为当前全局最优解的路径长度。采用全局信息更新策略, 增强了全局最优解路径上的信息素, 加强了算法的正反馈作用, 从而加快算法的收敛速度。

2 QoS网络路由模型

2.1 QoS组播路由问题的基本概念和网络模型定义

就组播路由而言, 网络通常表示成一个带权图G= (V, E) , 其中V代表节点集合;E代表网络中双向链路集合, 关联每条链路的参数就是该链路的QoS度量。在此, E表示网络中双向链路的集合[8];S为源节点, S∈V;M∈{V-{S}}为目的节点集, S, M组成组播树T (s, M) 。对于任一链路e∈E, 可定义某些属性:延时函数:delay (e) :E∈R+;费用函数cost (e) :E∈R+;带宽函数bandwidth (e) :E∈R+。对于任一网络节点n∈V, 定义某些属性:延迟函数delay (n) :V∈R+;费用函数cost (n) :V∈R+, 由此存在如下关系:

undefined

式中:pT (s, t) 为组播树T (s, M) 上源点s到终点t的路径。

QoS组播路由问题是要寻找一颗组播树T (s, M) 满足:

延时约束:

undefined

带宽约束:

undefined

式中:B表示带宽约束;Dt表示延时约束。

费用函数 (目标函数) 可描述为在所有满足条件的组播树中, cost (T (s, M) ) 最小。

2.2 网络负载和链路利用率

为考虑链路利用率的情况, 将链路代价定义为[9]:

undefined

E中的每条边对应网络中的一条链路ei, j, 其中i表示上游路由器;j表示下游路由器。ei, j具有三个属性:Maximum Bandwidth (MB) , Reserved Bandwidth (RB) , Unreserved Bandwidth (UB) 。因此有对任意e∈E, ∃MB (i, j) , RB (i, j) 和UB (i, j) , 并且MB (i, j) =RB (i, j) +UB (i, j) 。在式 (8) 的基础上, 定义式 (9) , 用来计算图G中每条链路的代价。

undefined

由式 (9) 可知, 剩余带宽越大, 链路代价越小;反之, 链路代价越大。

3 自适应蚁群算法的QoS组播问题实现

3.1 适应度函数

适应度函数是蚁群进行路径选择的依据, 也就是蚂蚁从初始路径集Ωi中选择第j条路径的概率:

undefined

式中: phepj (s, Di) 是路径pj (s, Di) 上的分泌物强度, 它表明某条路径上的分泌物强度越大, 该路径被选中的概率也就越大。初始状态时各条路径上的分泌物强度相同。

3.2 蚂蚁的信息素调整

蚂蚁寻找路径时, 按以下规则进行信息素调整:

(1) 对蚂蚁所经过的路径进行分泌物强度调整。其中a是常量参数;cost (e) 为该路径的代价;phepi (s, Di) 为源节点S到目的节点Di的路径上的分泌物强度。调整后, 有:

undefined

上述公式与文献[10]不同, 信息素的调整不是固定值, 而是根据所选择路径的代价来调整的, 并且路径代价受带宽影响, 是根据链路利用率来确定的。增加信息调整的自适应性, 同时也加快了收敛速度。

(2) 当蚂蚁都走完一条路径时, 对所有路径进行分泌物挥发调整。其中ρ是挥发度;Δ为各条路径上的初始信息强度。

undefined

(3) 当蚂蚁都找到所有目的节点, 组成一颗组播树时, 再按式 (13) 进行信息素调整, 即:

undefined

式中:B为常量参数;cost (T) 为该组播树的代价;pi (s, Di) 是被选路径。

3.3 算法步骤

Step 1:生成初始路径集。找出从源节点S到每个目的节点Di∈D (i=1, 2, …, m) 满足延时约束的有效路径, 并组成初始路径集Ωi。

Step 2:初始化α, β, B, ANTn和初始集中各条路径上的信息强度Δ。

Step 3:从源节点发出ANTn只蚂蚁, 按式 (10) 计算路径集Ωi中每条路径的适应度, 每只蚂蚁再按赌轮旋转规则从中选择一条路径, 再按式 (11) 进行分泌物强度调整。

Step 4:当每只蚂蚁都完成一条路径选择后, 按式 (12) 进行分泌物挥发性调整。

Step 5:重复执行Step 3和Step 4, 直到蚂蚁找到所有目的节点的路径, 每只蚂蚁寻找到的路径各组成一颗组播树。计算各组播树的代价 (相同链路的代价只计算一次) , 判断是否大多数蚂蚁收敛于同一组播树, 如果是, 则该组播树为最优路径, 退出程序;否则, 用代价最小的组播树替代代价最大的组播树, 转执行Step 6。

Step 6:蚂蚁按原路返回, 并按式 (13) 调整返回路径上的分泌物强度, 再转Step 3执行。

4 实验仿真和算法分析

本文采用改进的Waxman网络拓扑仿真模型[11], 利用Matlab 7.0进行仿真, 其特点是每对节点之间按概率p (u, v) =βexp (-d (u, v) /2an) 相连, 其中d (u, v) 为u, v两节点之间的距离, 并且按照Salama和Reeves在Waxman基础上的网络生成算法使平均节点度达到指定值。参数α, β分别控制网络中长边和短边的比例以及边的密度, n为网络节点个数。参数的选取如表1所示。表2列出了30个节点的网络仿真试验中, 两种不同算法在不同延时约束条件下的组播树代价。每次试验分别进行20次, 其中代价值分别是20次试验得到的平均值。从表2容易看出, 算法IAAC比算法AAC在相同延时条件下生成组播树的代价要小。图1描述了两种算法在30个网络节点的网络仿真中, 组播树的代价随迭代次数的变化情况。从图中可以看出, IAAC算法在收敛速度上要优于AAC算法, 并且在最优组播树的代价上也要优于AAC算法。图2显示了两种算法在随着网络节点数变化时, 组播树代价的变化情况。随着网络节点数的增加, IAAC算法所得最优组播树的代价低于AAC算法所得最优组播树的代价, 并且最优组播树的代价增加比AAC算法得到最优组播树代价的增加速度要慢。通过仿真试验, 本文改进的自适应蚁群算法能以更快的收敛速度得到最优组播树, 并且最优组播树的代价相对原有自适应蚁群算法要更优。

5 结 语

本文提出了一种应用自适应蚁群算法并结合实际网络的链路利用率的多约束QoS组播路由算法。将链路利用和网络负载考虑到组播路由中, 使得网络路由问题的研究更符合实际网络的需求。在运用自适应蚁群时, 结合信息素更新的特点, 将链路代价考虑到其中, 使得信息调整的自适应性加强, 同时收敛速度得到改善。

摘要：结合多约束QoS组播路由的特点, 应用一种自适应蚁群优化算法解决组播路由问题。考虑到实际通信中链路利用率对网络的影响, 将网络中链路的带宽转化为链路的代价问题, 并在蚁群算法中根据蚂蚁所选路径的代价进行信息素更新, 增加了信息素调整的自适应性, 同时加快了算法的收敛速度, 使得组播路由算法在考虑网络QoS约束的基础上进一步贴合实际网络的需求。

关键词：QoS,蚁群算法,自适应,链路利用率

参考文献

[1]Chockler G V, et al.Group Communication Specifications:AComprehensive Study[J].ACM Computing Surveys, 2001, 33 (4) :1-43.

[2]Wang B, Hou C J.A Survey on Multicast Routing and ItsQoS Extensions:Problems, Algorithms and Protocols[J].IEEE Network Magazine, 2000, 14 (1) :22-36.

[3]Xiao X P, Ni L M.Internet QoS:the Big Picture[J].IEEENetwork Magazine, 1999, 13 (2) :1-13.

[4]邹德莉, 郝应光.基于非精确状态信息的QoS组播路由算法[J].微电子学与计算机, 2006, 23 (9) :66-72.

[5]Wang Zheng, Crowcroft J.Quality of Service Routing for-Supporting Multimedia Applications[J].IEEE Journal onSelected Areas in Communications, 1996, 14 (7) :1 228-1 234.

[6]Dorigo M, Maniezzo V, Colorni A.Ant System:Optimizationby a Colony Cooperating Agents[J].IEEE Trans.on Sys-tems, Man, and Cybernetics-bart B:Cybernetics, 1996, 26 (1) :29-41.

[7]李昌兵.基于计算智能的多播QoS路由技术研究[D].重庆:重庆大学, 2007.

[8]王应征, 石冰心.基于遗传算法的时延受限代价最小组播路由选择方法[J].通信学报, 2002, 23 (3) :112-117.

[9]Cisco.OSPF Design Guide[EB/OL].http://www.cisco.com/warp/public/104/1.html, 2004-02.

[10]李生红, 刘泽民.基于蚁群算法的组播路由调度方法[J].计算机工程, 2001, 27 (4) :63-65.

[11]Waxman B M.Routing of Multiple Connections[J].IEEEJournal on Selected Area in Communications, 1986, 6 (9) :1622-1 671.

[12]田炳丽, 刘常波, 解贵新.旋转货架拣选作业优化的交叉蚁群算法求解[J].现代电子技术, 2008, 31 (12) :59-61.

多约束QoS组播路由 篇2

近年来,计算机网络技术的飞速发展和网络多媒体的大量运用,对网络服务质量(QoS)提出了更高的要求,使得多约束限制的QoS组播路由问题成为计算机网络领域的一个研究热点。QoS组播路由选择的目的是找到一棵满足QoS需求且包括所有组播成员的最小组播生成树。不同业务对QoS要求不同,体现在带宽、时延、丢包率等方面。

研究表明,多约束QoS路由问题属于NP完全问题[1],通常使用智能算法来对QoS路由问题进行求解。如遗传算法、蚁群算法等[2,3]。遗传算法有收敛速度慢,求精确解效率不高等不足,蚁群算法也有搜索时间长,易出现停滞现象等缺点。总之,每种智能算法都有其不足和优点,为了使多种不同的智能算法可以优势互补,通常采用多种不同算法相互融合,以达到优劣互补的目的。针对量子算法有加速作用的特点,结合遗传算法的优点,Narayanan A和Moore M[4]首先提出了量子遗传算法。量子遗传算法是在量子计算原理的基础上新发展起来的一种遗传算法,使用量子比特编码的量子染色体能同时表示多个状态信息。与传统的遗传算法相比,量子遗传算法具有种群多样性、收敛速度快、并行性更高等特点。目前普通的量子遗传算法都是采用对染色体上量子位状态进行测量的方法来获得对应的二进制解,这是基于概率的一个过程,具有很大的随机性和盲目性。通常都采用查询表的方式来确定转角的方向和大小,从而影响了算法的效率。针对目前普通量子遗传算法的不足,李士勇、李盼池提出了基于实数编码方式的双链量子遗传算法DCQGA[5,6],并把该算法用于连续空间的优化,取得了较理想的效果。本文基于量子遗传算法的基本理论,并充分考虑了多约束QoS问题自身的特点,提出使用基于概率幅编码和目标梯度信息的双链量子遗传算法来解决多约束QoS组播路由问题。

1 QoS路由问题描述

组播网络可以表示为带权图G=(V,E),其中V={v1,v2,…,vn}表示节点集,E={e1,e2,…,em}表示通信链路集,$\left|V\right|$与$\left|E\right|$分别为网络中节点数与链路数。设s∈V为组播源节点,M⊆{V-{s}}为组播目的节点集,di∈M(i=1,2,…,n)表示组播目的节点,p(s,di)为从源节点s到目的节点di的路径,Tj(s,M)表示从源节点s到目的节点集M的一棵组播树。任意两节点间链路e∈E,可定义四种QoS特征值,其中R+是非负实数集。

代价函数cost(e):E→R+,带宽函数bandwidth(e):E→R+,

时延函数delay(e):E→R+,丢包率函数packetloss(e):E→R+。

如果给定源节点s∈V,目的节点集M,则s和M构成的组播树Tj(s,M)与链路e之间有以下关系:

$C({\rm T}{}_j(s,{\rm M}))={\displaystyle \sum _{e\in {\rm T}{}_j(s,{\rm M})}\cos }t(e)$ (1)

B(p(s,di))=min{bandwidth(e),e∈P(s,di)} (2)

$D(p(s,d{}_i))={\displaystyle \sum _{e\in p(s,d{}_{{}_i})}d}elay(e)$ (3)

$L(p(s,d{}_i))=1-{\displaystyle \prod _{e\in p(s,d{}_i)}(}1-packtloss(e))$ (4)

用Pb、Pd和Ppl分别表示带宽约束、时延约束和丢包率约束,则一个满足带宽、时延和丢包率约束的多QoS组播路由请求可表示为:R=(s,M,Pb,Pd,Ppl),其目标是在给定的源节点s与目标节点集M时,找到一棵组播树Tj,使得从源节点s到任何目的节点di∈M的传输路径p(s,di)满足:

(1) 带宽约束:B(p(s,di))≥Pb;

(2) 时延约束:D(P(s,di))≤Pd;

(3) 丢包率约束:L(P(s,di))≤Ppl

在所有满足条件(1)-(3)的组播树中,目标函数C(Tj(s,M))最小。

2 量子遗传算法QGA简介

QGA(Quantum Genetic Algorithm)是遗传算法和量子计算相结合的产物。它将量子的矢量态表达引入遗传编码,用量子比特编码表示染色体,利用量子旋转门和量子非门对染色体进行更新。

2.1 量子比特编码

在QGA中,表示信息用量子比特。量子比特可处于$|\phi \rangle$和$|1\rangle$两种基本状态,也可处于两个基本状态的任意叠加态,可表示为[7]:

$|\phi \rangle =\alpha |0\rangle +\beta |1\rangle$ (5)

$\left|\alpha \right|{}^2+\left|\beta \right|{}^2=1$ (6)

式中,α、β是一对复数,称为量子态的概率幅。$\left|\alpha \right|{}^2$、$\left|\beta \right|{}^2$分别表示量子比特处于$|0\rangle$态和$|1\rangle$态的概率。

在QGA中用量子比特来表示染色体,用n个量子比特可以同时表示2n个状态,因此对于同样的优化问题,QGA种群可以比传统GA种群小很多。量子编码的染色体如下:$q{}_j{}^t=\left[\begin{array}{l}\alpha {}_1^t\\ \beta {}_1^t\end{array}|\begin{array}{l}\alpha {}_2^t\\ \beta {}_2^t\end{array}|\begin{array}{l}\alpha {}_3^t\\ \beta {}_3^t\end{array}|\begin{array}{l}\cdots \\ \cdots \end{array}|\begin{array}{l}\alpha {}_m^t\\ \beta {}_m^t\end{array}\right]$

式中,q${}_j^t$第t代第j个染色体,m为染色体中基因个数。

2.2 量子旋转门

QGA通常利用量子旋转门作用与各个染色体,来对染色体进行改变,从而达到对种群进行更新的目的。常用的量子旋转门定义为:

$U(\theta )=\left[\begin{array}{cc}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right]$

式中,θ为旋转角度。

2.3 量子遗传算法描述

步骤1 取种群规模为N的初始种群Q(t),t=0;

步骤2 对初始种群每个个体实施一次测量,得一个状态p(t);

步骤3 对每个状态计算适应度值,并记录最佳个体适应度值;

步骤4 当不满足终止条件时:

(1) t=t+1;

(2) 对种群Q(t+1)中每个个体实施一次测量得到一个状态p(t);

(3) 对每个状态计算适应度值;

(4) 利用量子旋转门操作对种群个体进行更新得到下一代种群Q(t+1);

(5) 记录最佳个体及其适应度值;

终止。

3 双链量子遗传算法(DCQGA)

3.1 双链量子编码

针对多约束QoS路由问题,通常采用树形结构编码方案,这种编码每条染色体代表一棵覆盖组播源节点和所有目的节点的组播树。给定组播源节点s和组播目的节点集M=(d1,d2,…,dm),则一棵组播树染色体可表示为:

pi=(g1,g2,…,gi,…,gm)

其中gi表示从源节点s到目的节点di之间的备选路径集合{p${}_i^1$,p${}_i^2$,…,p${}_i^j$,…,p${}_i^k$}中的路径,分别按顺序对它们进行编号{1,2,…,k},p${}_i^j$表示源节点s到目的节点di的第j条路径。

本文在传统树形结构编码基础上设计了一种双链量子编码,用量子位对树形结构染色体进行编码,用量子位的概率幅描述所选路径,则每个染色体可表示如下:

$p{}_i=\left[\left|\begin{array}{l}\cos (t{}_{i1})\\ \sin (t{}_{i1})\end{array}\right|\begin{array}{l}\cos (t{}_{i2})\\ \sin (t{}_{i2})\end{array}|\begin{array}{l}\cdots \\ \cdots \end{array}|\begin{array}{l}\cos (t{}_{im})\\ \sin (t{}_{im})\end{array}|\right]$

其中,tij=2π×rand(),rand()为(0,1)之间的随机数。i=1,2,…,n;j=1,2,…,m;n是种群规模,m是量子位数。

在DCQGA中,将每一个量子位的概率幅看做一对并列基因,则每条染色体可包含两条并列的基因链。每条合法基因链(即对应的组播树不含环)可代表一棵组播树,则每条染色体可以同时表示两棵组播树。因此每条染色体可同时代表搜索空间中的两个优化解:

pic=(cos(ti1),cos(ti2),…,cos(tin))

pis=(sin(ti1),sin(ti2),…,sin(tin))

pic和pis分别称为“余弦”解和“正弦”解。这种编码方案避免了不同进制间频繁解码过程,并且在染色体每次迭代时,两个解可同步更新,故在同等种群规模条件下,能加快优化进程,增强对搜索空间的遍历性,增加全局最优解数量,提高获得全局最优解概率。

3.2 解码过程

群体中每条染色体含2m个量子比特概率幅,可通过以下线性变换,使每个概率幅对应各个备选路径集合中的某个路径的编号。

令xi为目的节点di备选路径集中的路径编号,且wi≤ xi ≤bi(wi=1,bi =k; k , xi均为正整数),记染色体pj上第i个量子位为(α${}_i^j$,β${}_i^j$)T,则有如下线性转换关系:

$x{}_{ic}^j=\mathrm{int}\left\{\frac{1}{2}[b{}_i(1+\alpha {}_i^j)+w{}_i(1-\alpha {}_i^j)]\right\}$ (7)

$x{}_{is}^j=\mathrm{int}\left\{\frac{1}{2}\left[b{}_i\left(1+\beta {}_i^j\right)+w{}_i\left(1-\beta {}_i^j\right)\right]\right\}$ (8)

式中,int( )为取整函数,x${}_{ic}^j$和x${}_{is}^j$分别为正弦和余弦分量通过线性变换后对应的路径编号。

3.3 量子旋转门调整

由于转角大小和方向对算法的收敛速度和效率有很大影响,本文不再利用查表的方式对量子旋转门的转角大小和方向进行改变,而是利用以下方式自动进行调整:

(1) 旋转方向

令α0和β0分别表示当前搜索到的全局最优解中某量子位的一对概率幅,α1和β1是当前解中相应量子位的概率幅;记

$A=\left|\begin{array}{cc}\alpha {}_0& \alpha {}_1\\ \beta {}_0& \beta {}_1\end{array}\right|$

,则转角θ的方向按如下规则选取:

当A≠0时,方向为-sgn(A);当A=0时,方向取正负均可。

(2) 转角大小

本文设计旋转角大小时充分考虑适应度函数值在搜索点(单个染色体)处的变化趋势,并把相应信息融入到转角步长函数中。在搜索点处,如果适应度函数值变化较大,则适当减小转角大小,反之则适当加大转角。这样可以使各染色体根据自身特性在搜索区域的平坦之处迈大步,在搜索区域陡峭之处迈小步,从而更有利于求全局最优解[8]。

转角步长函数定义为:

$\Delta \theta {}_{ij}=-\mathrm{sgn}(A)\times \Delta \theta {}_0\times \exp \left(-\frac{\left|\nabla fit(p{}^j)\right|-\nabla fit{}_j\min }{\nabla fit{}_j\max -\nabla fit{}_j\min }\right)$

式中,A的定义同上,Δθ0为迭代初值,fit(pj)为染色体pj的适应度值;

ᐁfit(pj)=fit(p${}_{par}^j$)-fit(pj) (9)

其中p${}_{par}^j$为染色体pj的父代染色体。

3.4 变异处理

利用量子非门作用于染色体来实现变异。首先依据变异概率随机选择一条量子染色体,然后利用量子非门对此量子染色体的若干量子位施加量子非门变换,使该量子位两个概率幅互换,这样可以使两条基因链同时得到变异。

3.5 适应度函数的确立

适应度函数值是评价种群中个体好坏的标准,它能够反应出被选个体优劣。本文适应度函数定义为:

fit(Tj)=fC(afB+bfD+cfPL) (12)

$f{}_C=\frac{1}{C({\rm T}{}_j)}$ (13)

$f{}_B={\displaystyle \prod _{i=1}^n\Phi }({\rm P}{}_b-B(p(s,d{}_i)))$ (14)

$f{}_D={\displaystyle \prod _{i=1}^n\Phi }(D(p(s,d{}_i))-{\rm P}{}_d)$ (15)

$f{}_{{\rm P}L}={\displaystyle \prod _{i=1}^n\Phi }(L(p(s,d{}_i))-{\rm P}{}_{pl})$ (16)

式中a,b,c为归一化系数,分别表示带宽、时延、丢包率在适应度函数中所占比重,本文取a =0.4,b=0.3,c=0.3;Φ(Z)为惩罚函数,当个体满足约束条件,即Z≤0时,Φ(Z)=1;否则Φ(Z)=r,0<r<1,r值决定了惩罚程度,本文取Φ(Z)=0.5。

3.6 算法描述

步骤1 利用Salama网络拓扑随机生成算法,随机生成N个节点的网络拓扑图,并初始化网络;

步骤2 对网路拓扑图进行预处理,删除不满足带宽约束路径,利用备选路径生成算法生成各目的节点备选路径集合,并对各集合中的路径分别进行编号;

步骤3 用本文中双链量子编码方案,产生n条合法的量子染色体(合法即每条染色体中不能含有环),由它们组成初始种群;

步骤4 对种群各染色体及其它参数分别进行初始化,并设定转角步长初值为θ0、变异概率为pm;

步骤5 对各染色体进行解码,检查各染色体是否含有环,如有则进行去环处理;

步骤6 求出各个染色体的适应度值。令当代最优解为$\tilde{X}$0,其对应的量子染色体为$\tilde{p}$0;令到目前为止的全局最优解为X0,其对应量子染色体为p0。如果$fit(\tilde{X}{}_0)>fit(X{}_0)$,则$p{}_0=\tilde{p}{}_0$;

步骤7 对种群中每条染色体的各量子位,以p0中相应量子位为目标,按3.3节中方法确定转角的方向和大小,运用量子旋转门更新其量子位;

步骤8 对种群中每条染色体,运用量子非门按变异概率实施变异;

步骤9 返回步骤5循环计算,直到满足收敛条件或达到最大循环代数为止;

步骤10 输出全局最优解X0,并求出其相应的适应度值fit(X0)

4 仿真实验

本文采用的仿真工具是Matlab 7.0, 在CPU为Pentium 3GHz ,2.99GHz,内存为 512M的微机上运行,对遗传算法(GA)、量子遗传算法(QGA)和本文中的算法(DCQGA)性能进行了对比。实验是在网络节点数不同的情况下,利用改进型Salama网络拓扑生成方法产生多个网络拓扑图,并分别运行上述算法各10次,仿真结果取其统计的均值。

图1显示了三种算法在不同网络规模条件下算法收敛平均运行时间的对比关系,可见,本文算法有较快的收敛速度,并且随着网络规模的增大这种优势体现的更明显,充分体现了本文算法收敛速度快,并行性好的优点。图2则显示在不同网络规模条件下,三种算法的组播树代价均值随网络节点数变化的情况,结果表明:随着网络规模的变大,组播树代价也在增加,但本文算法求得的组播树代价较小,算法的解质量较高。

5 结 语

多约束条件下的组播路由问题是网络研究的热点。本文在量子遗传算法的基础上,提出了一种基于带有目标梯度信息的双链量子遗传算法的组播路由优化算法。该算法克服了遗传算法和普通量子遗传算法的不足,取得了比较理想的效果。实验表明,本文的算法具有并行性好、收敛快、种群丰富等优点,适合用来解决网络中的组播路由问题。

摘要：多约束QoS组播路由问题是NP完全问题。提出一种基于双链量子遗传算法的多约束QoS组播路由算法,该算法具有种群多样性、收敛速度快、并行性更高等优点,并对算法具体流程和实现方法进行了详细的描述。实验结果表明,与已有的遗传算法、量子遗传算法相比,该算法有搜索速度快、全局寻优能力强等优点。

关键词：组播路由,QoS,双链量子遗传算法

参考文献

[1]Wang Z,Crow Croft J.Quality of service routing for supporting multi-media application[J].IEEE Journal on Selected Areas in Communica-tions1996,14(7):148-154.

[2]王征应,石冰心.基于启发式遗传算法的QoS组播路由问题求解[J].计算机学报,2001,24(l):55-61.

[3]许毅,李腊元.基于蚁群算法的QoS多播路由优化算法[J].计算机应用研究,2005,(1):183-185.

[4]Narayanay A,Moore M.Quantum-inspired genetic algorithms[C]//Proceedings of IEEE International Conference on Evolutionary Compu-tation,Nagoya,Japan,1996:61-66.

[5]Li P C,Li S Y.Quantum-inspired evolutionary algorithm for continu-ous spaces optimization[J].Chinese Journal of Electonics,2008,17(1):80-84.

[6]李士勇,李盼池.基于实数编码和目标函数梯度的量子遗传算法[J].哈尔滨工业大学学报,2006,38(8):1216-1218,1223.

[7]杨淑媛,刘芳,焦李成.一种基于量子染色体的遗传算法[J].西安电子科技大学学报,2003,31(1):76-81.

多约束QoS组播路由 篇3

文献[4]提出的基于遗传算法的Qo S路由,该算法选择带宽、时延、丢包率作为约束参数,寻找最优路径,但是未对网络资源及负载均衡优化,且未考虑过算法的收敛性。文献[5]提出的改进遗传算法以网络消耗和负载均衡分布为目标函数,最终使网络达到负载均衡,降低了网络的拥塞,但是并未考虑算法的过早收敛以及收敛速度。 针对现有算法的问题,本文通过对遗传算法适应度函数和遗传算子的改进,使得算法最终有较快的收敛速度,同时避免早收敛,提高Qo S满意率。

1网络模型以及数学描述

Qo S路由的网络可以描述为图G( V,E) ,在满足给定约束的条件下,寻找从源服务节点s到目的服务节点d的一条最优服务路径。对于路径P( s,d) ,在Qo S路由选择时主要考虑的参数有网络链路带宽B、时延D、花费C、丢包率L。20节点网络拓扑如图1所示。

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

式中: B为要求链路带宽 。 而时延满足

式中: D为要求最大时延。丢包率满足

式中: L为要求的最大丢包率。花费满足

本文就是在带宽、时延、丢包率约束条件下,寻找一条最优服务路径,同时链路花费少、收敛于最优路径速度快,且有较高的Qo S满意率。

2基于遗传算法的Qo S路由

2. 1编码方法以及群体初始化

本文采用较为简单的编码方式,根据网络的拓扑,采用深度优先搜索算法找到一条从源服务节点到目的服务节点的路径。在遗传操作中无论是交叉还是变异,都无需编码和解码了。在种群初始化时,先做一个预处理,在网络中将不满足带宽B要求的链路先删除掉,得到新的拓扑图,如若得到的拓扑图是非连通的,且源节点和目的节点不在同一连通子图里则无法提供服务。本文假设经过处理后的图为连通的,由于深度优先搜索算法是根据邻接矩阵搜索的,所以从源节点开始每搜完一个节点后就随机选取当前节点下的一个邻接点,且此节点并未被搜索过, 然后再搜索,直到搜索到目的节点而完成单次寻找路径的过程,重复此过程直到达到种群规模。

2. 2适应度函数的设计

适应度函数的设计是遗传算法的关键部分,直接影响到算法收敛的速度,以及能否找到优化解。本论文设计的适应度函数为

式中: ψ( P( s,d) ) 是一个惩罚函数,当路径上的时延或者丢失率不满足要求时,它的值会相应减少,且有

在式( 5 ) 中, C是一个常数 。D ( B ) 代表了选择当前路径之后剩下可用带宽偏离程度即链路负载均衡度, N L为当前路径中的链路数目 。 如果选择的路径D ( B ) 越小, 说明链路负载均衡能力越好,这样可以有效降低网络的拥塞程度,那么全局负载就会越均衡 。 系数A , B是一个为了平衡分母下每个优化目标的影响 。 如果一个优化目标过大会使得另一个优化目标被忽略 。

而式( 5) 中的指数函数是为了在算法后期拉开个体之间的差异,从而加快收敛速度,最终找到最优路径。

2. 3选择操作

选择算子的优劣直接影响到算法的收敛性,文献[6] 提出的基于切断的轮盘赌选择的方式来单独选择最优个体,同时在选定个体后相应减少其比例的大小,重复这样的操作直到个体达到种群规模为止,但是基于赌轮的选择本身就存在较大的随机误差,于是本文对文献[6]提出的基于切断的轮盘赌选择进一步改进为通过多轮盘赌选择, 并且为了增加选择的多样性对比例的减少也做了改进。 这样的选择操作进一步减少了随机误差,增大了最优个体被保留的可能性,同时又不失种群的多样性。

假设种群大小为M,计算所有个体选择概率Pi,并将计算出的概率根据其大小分布在[0,1]上,则在[0,1]上存在着M个区间,这M个区间为A1,A2,…,AM。然后开始M × N多轮盘赌选择,M为种群数目,N代表在每一次选择个体时都要进行轮盘赌N次,并统计这N次中落在M个区间中每个区间的次数,选择次数最大的个体为本轮选择的个体,种群数目有M个,则重复M次从而得到M个个体。若出现落入区间最大次数相同的个体,则选择概率大的。初始时根据每个个体适应度计算其选择概率,即为 ,则具体的算法步骤如下:

1 ) 计算比例 ,并按照上述的方式分布在[ 0 , 1 ]区间内 。

2) 进行N次轮盘赌选择,并统计落入每个区间的次数。选择区间落入次数最多的一个个体t( t ∈[1,M]) , 判断Pt,如果Pt- 1 / M ≤ 0 ,则令Pt= Pt/2 ,否则Pt= Pt- 1 / M 。

3) 若选出的个体数目达到种群大小M,则结束。否则转到1) 继续选择个体。

2. 4交叉操作

遗传算法中交叉算子模拟自然界生物的杂交过程对个体进行交叉操作,不断产生新的个体,增加种群的多样性。在路由寻址的应用中体现了其较强的全局搜索能力, 它扩展了求解空间,并为寻找到最优路径发挥着重要作用。本文的交叉算子实现较为简单,具体过程如下:

1) 根据选择概率随机选择父代中参与交叉操作的链路Px和Py,随机选择Px和Py除源节点和目的节点的共同节点作为杂交点。如果没有共同节点,则随机选择交叉节点。

2) 交换杂交点后的所有节点得到新的子女个体。如果新的子女个体在节点之间不存在链路连接,利用上文提及的根据邻接矩阵使用随机化的深度优先搜索算法寻找节点之间的链路。如若新个体中存在环路,则删除形成环路。

2. 5变异操作

种群的变异是为了使物种提高自身的适应能力,并存活下来,使得群体质量上升。但是变异也存在优劣之差,优良的变异使得物种适应环境并延续后代,较差的变异会直接导致物种被大自然淘汰。为了使得物种适应环境的变化,朝着好的方向变异。本文提出了一种新的变异算子,其具体的思想为在选择后的当前种群中,优秀的个体即为较高适应度的个体,必然是某些优秀基因的存在导致的,而本文对优秀基因的判别是统计在优秀个体中此基因出现次数的和。某种基因在当代种群的优秀个体中出现的次数越多,说明其越是优秀,变异的可能性就会越低, 相反在优秀个体中没有出现的或者是统计次数较低的基因,其变异的可能性就会很大。这样个体变异就会朝着好的方向发展,可以提高算法收敛速度。具体的算法步骤如下:

1) 执行完选择操作后,统计当前种群中所有链路个体中除源节点和目的节点以外经过的每个相同节点各自出现的次数和,这里把经过选择后当前链路种群中适应度值大于平均适应度值的链路定义为优秀链路。将当前种群中节点出现次数排在前N位的节点定义为优秀节点基因,其中N可表示为

2) 在经过交叉后的链路群体中依照变异概率随机地选择一个个体链路Px,然后从个体链路中随机地选择非优秀基因进行变异操作。具体的变异操作过程为在链路中随机地选取一个非优秀基因g。以g为起点,在链路Px上沿着g向前向后移动,直到移动到的节点基因为优秀节点基因为止。随机选择使用花费Cost、链路剩余带宽的倒数1 /B,或者时延D之一为链路的参数,以A* 算法求出节点g之前向前向后移动到的优秀节点基因之间的路径。 最后,将此路径替换个体链路Px中最开始的链路,如果替换后有回路,则将其删除。

3实验仿真

本文利用含有20个节点的图1进行实验仿真。设置每条链路的参数,其中链路的带宽在1 ~10之间,链路的时延在10 ~100之间,链路的丢失率在0. 01 ~ 0. 1之间,花费在1 ~5之间。用户要求的带宽为2,时延小于200,丢失率小于0.2。且本文路由的源节点为1,目的节点为20。

1) 验证本文提出的改进遗传算法的可行性。本文首先利用深度优先搜索算法穷举出两点间所有的可达路径, 并比较它们之间的适应度值,求出最大适应度值的路径, 即本文所要求的最佳路径,其为1→4→7→14→20,其适应度为13. 06。本文算法的遗传迭代过程如图2所示。

从图2可以看出,在本算法进行到第5代时就收敛到全局最优解1→4→7→14→20,并且收敛过程中每一代的丢失率与时延变化如图3、图4所示。

从图3和图4可以看出,求解的最优路径丢失率和时延均满足要求时延,因此本文提出的改进遗传算法用于寻找一条满足时延、丢失率、带宽的最优路径是可行的。

2) 与传统遗传算法相比。验证本文提出的改进遗传算法较之传统的遗传算法在收敛速度和Qo S满意率方面的优势。其中定义收敛速度为每次实验成功迭代到全局最优解的代数的累积和与成功实验次数总和之比,定义Qo S满意率为每次实验成功找到全局最优解的累计次数与实验次数总和之比。本次实验的两个算法具有相同的初始环境,即算法的种群规模均为50,迭代次数均为20, 且两个算法均实验50次,每次的初始种群均是相同的,使用的适应度函数均为本文提出的适应度函数。具体的实验数据比较如表1所示。

从表1的数据可以看出,在收敛速度上,改进的遗传算法平均在迭代的第3代即可收敛到最优解,而传统的遗传算法平均在迭代的4. 7代才可以收敛到最优解,故改进的遗传算法在收敛速度上有一定的提升。在Qo S满意率方面,改进遗传算法的满意率为86% ,大于传统遗传算法70% 的满意率,也就是表明改进的遗传算法可收敛到最优解的概率明显大于传统的遗传算法。

4总结

在多约束Qo S路由网络中,本文提出的改进遗传算法将带宽、时延、丢失率作为约束条件,改进了适应度公式和遗传操作。实验仿真表明该算法是可行的,并能在一定程度上克服传统的遗传算法缺点,提高收敛速度,有效避免过早收敛,提高Qo S满意率。

摘要：遗传算法良好的全局搜索能力使其被广泛地应用于网络中多约束QoS路由寻址,并取得了较好的成果。然而大部分应用于多约束QoS寻址的改进遗传算法存在无法有效利用网络资源使得网络拥塞、网络过早收敛陷入局部最优解,以及过慢结束的缺点。针对上述问题,对传统遗传算法中的适应度函数和遗传算子做出相应的改进,并通过实验验证提出改进遗传算法。最终,仿真实验表明该算法是可行的,并能在一定程度上克服传统遗传算法的缺点,提高收敛速度,有效避免过早收敛,提高QoS满意率。

多约束QoS组播路由 篇4

波分复用技术(WDM)因其大容量传输数据的特点,在网络中得到广泛应用。然而网络中一旦出现故障,其损失也是巨大的。目前,针对这一问题主要有保护机制和恢复机制两种解决方案[1]。

所谓的保护机制是为防止因网络故障而导致的数据丢失,在资源分配之前预留一条保护路径(分专用保护和共享保护[1]),一旦工作路径断接,则将数据转向保护路径传输。而恢复机制则是事先不预留空闲资源,如果工作路径出现故障,则动态地从当前网络中再查找一条可用路径。两种方案各有利弊,恢复机制能够提高网络资源的利用效率,而保护机制可提供更快的恢复时间,有利于网络QoS的保障。

本文在保护机制的基础上提出了一种查找工作路径和保护路径链路不相交[2]的QoS路由方法。

1多约束链路不相交QoS路由算法

QoS路由主要针对当前所流行的多媒体流的传输,根据相应的QoS参数计算并优化可用路径。

在过去的传统算法中,对链路不相交路由的查找是通过剪枝法进行的,即首先找到一条代价最小的路径;然后在拓扑图中,删除该路径上的所有链路,再从修剪后的拓扑图中找一条代价最小的路径,那么该路径与先前被剪枝路径即为所求的链路不相交路径。重复以上做法,可获得一组链路不相交路径。

此算法存在以下缺点:其一,通过剪枝法找到的两条链路不相交路径,可能相差的链路数太大,从而造成数据在从工作路径转到保护路径的时延增加,而此时的网络中却可能存在两条传输性能相似的链路不相交的次优路径,如果选择这两条路径,则能够保障工作路径和保护路径QoS性能约束的一致性。其二,以剪枝法求解,可能从拓扑图中根本找不到两条链路不相交路径。

举例:如图1所示,以传统算法查找节点对<1, 7>间两条链路不相交路径。

(1) 找到两点间的最短路径{1, 5, 6, 7};

(2) 剪枝;

(3) 拓扑图变为非连通图,节点对<1, 7>间无可达路径;

(4) 得出结论,拓扑图中节点对<1, 7>间不存在链路不相交路径。

然而,从拓扑图中我们很明显可以看出,如果以次短路径为基准,则存在两条链路不相交路径{1, 2, 3, 6, 7}和{1, 5, 4, 8, 7}。

鉴于上述算法中存在的问题,本文提出了一种新算法,即在给定拓扑图中,找到所有节点对间的满足QoS多约束的全部路径,进而获得最短(这里以链路跳数为代价,最短即最优) 的两条相似(指两条路径代价相似)的链路不相交路径。此外,本算法还适用于解决大数据流复用到多条路径的时延抖动问题。

2路由算法模型

给定一个无向图G=〈V, E〉表示网络的拓扑结构[3],其中,V={v0, v1, …, vn}表示网络中节点的集合,E={e0 , e1, …, en}表示网络中链路集合,n为节点数目。

本文中网络服务质量的约束条件[4]指定为:带宽约束、路径(链路)时延。对于给定的业务请求连接(s, d, B*, D*),s为源节点,d为目的节点, B*为满足QoS的约束带宽, D*为满足QoS的约束时延。

2.1QoS约束条件

(1) minB(e)≥B*,e∈p,B(e)为链路e上的剩余带宽, p为当前查找的路径。

(2) D(p)≤D*, D(p)=∑e∈pd(e), d(e)为链路e上的时延,D(p)为路径p上的总的时延。

2.2满足QoS约束的路由算法

2.2.1 初始化

在给定拓扑图上,删除不满足带宽和时延约束条件的链路。对剩余链路以li(i=1,2,,…,x, x为剩余链路数目)标记;如果从s到d间没有直接链路则标记为0。

2.2.2 查找满足QoS的任意两点的全路由

该过程由图论中矩阵逻辑相乘的基本原理展开:

定义 1 矩阵:M={msd}n×n

n为节点个数,msd为该矩阵中的元素,形式化代表从节点s到d的所有路径,具体含义如下:如果s=d,即求节点到自身的路径,此时令msd=1;否则,msd表示为节点对<s, d>间所有路径之和,每条路径以该路径上链路标识之积表示。

对msd进行如下分步求解:

(1) 初始矩阵M0中的元素,可形式化为:

如果节点对〈s,d〉间存在直接链路li,则

m${}_{sd}^0$=li (1)

如果节点对〈s,d〉间存在多条并联的直接链路,li1, li2, …, liz,那么

msd0 = li1 + li2 + ... + liz[5] (2)

(2) 对矩阵进行n次变换,即把n个节点作为桥梁,依次加入源-目节点对间的路径中,从而得到节点对〈s,d〉的全部可达路径。 变换过程中,遵守规则如下:

规则1

$\left(m{}_{sd}^k\right)´=m{}_{sk}^{\left(k-1\right)}.m{}_{kd}^{\left(k-1\right)}$k=1, 2, …,n (3)

其中m${}_{sd}^k$表示经过第k次变换后,对应节点对〈s,d〉间的全部满足QoS约束的路径;$\left(m{}_{sd}^k\right)´$为一个中间量,表示加入第k个节点后比之前新增的路径。

规则2

对求得的$\left(m{}_{sd}^k\right)´$以“加号”为界,将多项式进行拆分,得到的每一个乘积项为加入第k个节点后,从s到d间新增的可达路径pi,i=1, 2, …, y, 其中y为拆分后得到的乘积项的数目。

检查得到的y条新路径是否满足QoS约束,并过滤掉不合要求的路径,以保证每一步都能满足QoS约束。规则如下:

① 检查由规则2中得到的所有新增路径(乘积项)中链路的QoS指标,如果其中有路径pi不满足要求,则令pi=0,i=1, 2, … , y

② 将①中得到的过滤后的路径(乘积项)再次相加(此时各路径均满足QoS要求),从而得到加入第k个节点后产生的满足QoS约束的新路径$\left(m{}_{sd}^k\right)˝$,形式化如下:

$\left(m{}_{sd}^k\right)˝={\displaystyle \sum p}{}_i$i=1,2,…,y (4)

③ 将这些新增路径与加入第k个节点之前得到的所有路径(m${}_{sd}^{k-1}$)求和,即得到加入第k个节点后,节点对间的全部的满足QoS约束的路径。形式化如下:

$m{}_{sd}^k=\left(m{}_{sd}^k\right)˝+m{}_{sd}^{k-1}$ (5)

(3) 重复以上操作,直到把n个节点都加入到路径的求解运算中,即可得到节点对〈s, d〉间的满足QoS约束的全部路径。

2.3链路不相交相似路径算法

由于链路出现故障,要使用保护路径的概率较低,因而,原则上只要工作路径和保护路径的相似性保持在一定范围内,还是应该首选最优路径,本文中我们允许在小结点网络中工作路径和保护路径间的链路数目差最大为3(太大则可能会出现大抖动现象)。算法表述如下:

(1) 将2.2节中全路由算法中得到的给定的节点对〈s, d〉间的所有满足约束条件的y条路径,按其链路数目由小到大进行排序,这样得到的第一条路径即为最短路径。

(2) 定义n×y阶二维表格。其中,每条记录依次对应了(1)中求得的一条路径;第一个字段存储各条记录上路径的链路数目,其他字段依次对应拓扑图中的全部链路标号。表格数据填充规则如下:对求得的第k条路径,k=1, 2, …, y, 检查其链路数目,并将其赋值给第k行的第一个元素,再查看该路径上的链路标号,映射到二维表中的第k条记录,将对应项置1,其他项置0。

(3) 求链路不相交的最短相似路径。将第一条记录(最短路径),与之后的记录比较,如果同时满足以下两个条件,那么,这两条路径即为所求的链路不相交最短相似路径。

1) 两条路径的链路数目之差<=3;

2) 将这两条记录对应元素相减,再将差值取绝对值后累加,其累加结果与两条路径的链路数之和相等。

如果不满足以上两个条件之一,则将记录下移一条,再与之后的记录进行如上所述比较,重复操作,直到得出结果。

3算例分析

到来请求:(s, d, B*, D*)=(1, 4, 4, 10);

l1=(5, 2), l2=(7, 3), l3=(5, 4), l4=(6, 2), l5=(6, 3), l6=(6, 5), l7=(7, 3), l8=(3, 5)。如图2所示。

对原拓扑图剪枝,即剪掉不满足QoS约束的链路,本例中l8的带宽不足,删掉。得新拓扑图如图3所示。

由图3得初始关联矩阵:

${\rm M}{}^0=\left(\begin{array}{ccccc}1& l{}_1& l{}_3& l{}_5& 0\\ l{}_1& 1& 0& l{}_2& 0\\ l{}_3& 0& 1& l{}_4& l{}_6\\ l{}_5& l{}_2& l{}_4& 1& l{}_7\\ 0& 0& l{}_6& l{}_7& 1\end{array}\right)$

(6)

k=1时,即加入第一个节点后,矩阵变换为:

${\rm M}{}^1=\left(\begin{array}{ccccc}1& l{}_1& l{}_3& l{}_5& 0\\ l{}_1& 1& l{}_{1}l{}_3& l{}_{1}l{}_5+l{}_2& 0\\ l{}_3& l{}_{1}l{}_3& 1& l{}_{3}l{}_5+l{}_4& l{}_6\\ l{}_5& l{}_{1}l{}_5+l{}_2& l{}_{3}l{}_5+l{}_4& 1& l{}_7\\ 0& 0& l{}_6& l{}_7& 1\end{array}\right)$

(7)

现对节点对(2, 3), (2, 4), (3, 4)的新增路径渐进行拆分,并判断加入节点后得到的新路径是否还满足QoS约束,不满足则接着删除该新路径。本次变换中都满足条件,因而M1如(7)式所示。以下方法雷同,则不再详细解释。

省略中间变换。

k=5时,即加入第五个节点后,变换并删除不符合QoS约束后,矩阵形如公式(8)所示。

(8)

从而由公式(8)得到任意节点对间的所有满足QoS约束的可达路径。

本例:到来请求为〈1, 4, 4, 10〉。

通过上述计算,得出节点对〈1, 4〉间满足QoS约束的可达路径有:p1=l1→l2;p2=l3→l4;p3=l5。

现对此请求查找最短相似链路不相交路由。

建立二维表如表1所示。

1) p2.num-p1.num=1<3

$2)\left|p{}_1.l{}_1-p{}_2.l{}_1\right|+\left|p{}_1.l{}_2-p{}_2.l{}_2\right|+\left|p{}_1.l{}_5-p{}_2.l{}_5\right|=p{}_1.\text{n}\text{u}\text{m}+p{}_2.\text{n}\text{u}\text{m}$

满足算法中的条件,从而,得到节点对〈1,4〉间的最短的相似的链路不相交路由为p1、p2。

4结束语

根据图论有关知识,结合QoS约束,二维空间向量的四则运算等相关规则,提出了一种新的求节点对间的最短的相似的链路不相交路由的算法。此算法在查找路径时没有提高时间复杂性的基础上,完善了从工作路径向保护路径转移数据后的延迟差距,使一些即时网络或高实时性网络得到更好的优化,具有一定的理论和实际意义。

摘要：为提高网络路由可靠性,改善网络资源利用率,提出一种满足多个QoS约束的基于链路保护机制的路由算法。该算法首先通过图论的有关性质找到满足给定约束条件的节点对间的全部路径,并在此基础上利用邻接矩阵的方法得到其最短链路不相交相似路径,最后赋以算例分析。结果证明,该算法在减小网路传输时延方面有一定的优势,对于高实时性网络应用有更好的优化作用。

关键词：多约束QoS路由,保护机制,链路不相交

参考文献

[1]杨璐,邱代燕,刘彤.网络生存性综述[J].计算机工程与设计,2005,26(5):1225-1227.

[2]Guo Yuchun,Kuipers Fernando,Mieghem P V.Link-disjoint paths forreliable QoS routing[J].International Journal of Communication Sys-tems,2003,16:779-798.

[3]陈有汉,胡仲海,桂志波.考虑不确定信息的QoS路由算法综述[J].计算机工程与应用,2006(15):125-128.

[4]许毅,李腊元.一种支持多QoS约束的多播路由协议[J].小型微型计算机系统,2005,26(12):1065-1068.

多约束QoS组播路由 篇5

Internet网络的兴起之后,各式网络服务争相出现,包括各种先进的多媒体业务蓬勃发展。传统的以文字和图片为主的服务已不能满足用户的需要,具有视频和音频的多媒体服务正成为主流。然而,目前的传输网络面临下列两个难题:首先,网络业务对传输时延、时延抖动等参数较为敏感;其次,多媒体业务消耗大量带宽,给现有的网络传输提出新的课题[1,2]。因此,QoS组播路由算法成了当前研究的热门。

学者们近期提出QoS路由的概念,其目的是:在当前网络传输中,寻找满足用户对时间、成、延迟、抖动、故障率等要求的最佳路线[3]。考虑到QoS路由问题是一个NP-C问题,较好的方法是采用进化算法求解。国外文献如Yen[4]提出用遗传算法(GA)求解,Forsati[5]提出用和谐搜索方法,Vijayalakshmi[6]提出采用人工免疫结合GA的方法。Rehab F[7]提出采用离散粒子群(Discrete PSO)与GA相结合的方法求解。

遗憾的是,上述的算法虽然可以较好地解决QoS问题,其本身也存在缺陷[8]。GA运行一定步数后,其向全局最小解的收敛速度过慢;人工免疫模仿人类的免疫系统,但数据存取操作频繁[9];ACA前期收敛较慢[10]。为此,有必要寻找新的性能更好的智能优化算法。

本文介绍一种新的优化算法,细菌趋药性算法(BCO),它的原理如下:细菌觅食过程当中,处于一个类似的化学引诱剂环境中,其运动行为总是最合理。因此BCO算法模拟这个过程,实现函数的优化。另外,最新的证据显示,细菌在引诱剂环境下的应激机制,类似于传统的梯度下降相。由于BCO性能优异,被称为第二代进化算法。

本文采用BCO对QoS组播路由问题进行仿真。实验表明,基于BCO用于QoS组播路由问题, 性能优于各类文献提出的算法。在节点数目较多的情况下,时间仅有其他算法的40%-60%左右。

1 数学模型

建立如下模型:假设网络为G=(V, E),其中V代表节点集合,E代表链路集合,每条链路存在一个三元组,即时延、时延抖动、代价三个QoS参数。不失一般性,假定两节点之间最多仅有一条边。组播会话的源节点S∈V,目的节点集M={m1, m2, …, mN}⊆V-{S},M中每个节点mi称为组成员,N为组成员的个数。

组播树T是G的子图,T中包含N条路径Pi,其根为源节点S,叶为目的节点mi。考虑到链路上的三元组,则组播树T与路径Pi存在下列关系:

$delay({\rm P}{}_i)={\displaystyle \sum _{x\in {\rm P}{}_i}d}elay(x)i=1,2,\cdots ,{\rm N}$ (1)

$delayjitter({\rm P}{}_i)={\displaystyle \sum _{x\in {\rm P}{}_i}d}elayjitter(x)i=1,2,\cdots ,{\rm N}$ (2)

$cost({\rm T})={\displaystyle \sum _{x\in {\rm T}}\cos }t(x)$ (3)

式中x表征对应的属于组播树T或路径Pi的节点与子链路。因此,QoS问题就是如下约束最优化问题。

式中Di表示第i个目的节点的延迟约束,Ji表示第i个目的节点的延迟抖动约束。

2 BCO简介

2.1 原 理

单个细菌在引诱剂环境下的反应运动遵循如下假设:

(1) 细菌的运行轨迹由一系列直线组成,速度、方向和运动时间等3个参数决定了其运行曲线。另外假设其速度为恒值。

(2) 细菌改变运动方向时,向左拐、向右拐的概率相同,均为50%。

(3) 细菌在运动轨迹上的移动时间,相邻轨迹间的夹角,满足给定的概率分布。

(4) 细菌在运动轨迹上的持续时间,满足指数分布,并随迭代步数逐渐减少。

(5) 细菌在运动轨迹上的持续时间,以及各段相邻轨迹间的夹角,独立于之前运动轨迹的方向和时间参数。

2.2 算法伪码

基于上述假设,BCO算法步骤如下[11]:

Step1 假定细菌的移动速度为常数1:

v=1 (7)

Step2 计算细菌在新方向上的移动时间τ,其数值由概率分布决定:

${\rm P}(X=\tau )=\frac{1}{{\rm T}}\exp \left(-\frac{\tau }{{\rm T}}\right)$ (8)

参数T由下式决定:

Step3 计算细菌的新运动方向,它与原轨迹的夹角根据新方向向左或向右偏转分别服从[12]:

${\rm P}(X=\alpha ,v=\mu )=\frac{1}{\sqrt{2\text{π}}\sigma }\exp \left[-\frac{(\alpha -v){}^2}{2\sigma {}^2}\right]$ (10)

${\rm P}(X=\alpha ,v=-\mu )=\frac{1}{\sqrt{2\text{π}}\sigma }\exp \left[-\frac{(\alpha -v){}^2}{2\sigma {}^2}\right]$ (11)

这里,变量X的数学期望μ = E(X)和对应的方差σ = Var(X)1/2[13,14]在fpr/lpr<0条件下为:

μ=62°(1-cosθ) (12)

σ=26°(1-cosθ) (13)

cosθ=exp(-τcτpr) (14)

式中τc为细菌的当前运动轨迹的相关时间,τpr为细菌上一步运动轨迹的持续时间[15];反之,若fpr/lpr≥0,则μ=62°,σ=26°。

Step4 计算细菌在变量空间中新的位置:

xnew=xold+nul (15)

其中xnew为细菌新位置,xold为细菌上一时刻位置,nu是归一化的新轨迹方向向量,l为新轨迹长度。

整个算法中,T0、τc与b为3个需要预先设定的参数,它们与期望的计算精度ε有关:

T0=ε0.3010-1.73 (16)

b=T0(T${}_0^{-1.54}$100.60) (17)

$\tau {}_c=\left(\frac{b}{{\rm T}{}_0}\right){}^{0.31}10{}^{1.16}$ (18)

3 实验与讨论

仿真实验采用随机生成的网络,见图1所示。节点数分别为20,30,40,50,60,分别令距离小于最大距离30%,24%,22%,20%, 18%的两个节点存在链路。源节点设为0号节点,目的节点取总结点数的10%,目的节点号随机产生。节点的延迟在[30ms, 120ms]内均匀分布,延时抖动在[0ms, 10ms]上均匀分布。链路的时延在[0ms, 40ms]上均匀分布,实验抖动在[0ms, 15ms]上均匀分布。费用在[0, 50]上均匀分布。仿真环境采用P4 3.6GHz处理器,2G内存,Matlab7.1。

对比算法采用和谐搜索(HS)[16]与人工免疫遗传算法(AIGA)[6]。实验中各算法的参数设置如下:本文算法中设置T0=0.0047,b=72.144,τc=287.3042。HS与AIGA按照试错法选取最优值。实验分两部分,第一部分观察算法的整体性能。固定解的大小,使这三种算法求解的结果基本达到最优解时停止,然后比较不同算法的运行时间,结果列于表1所示。

从表1可以看出,当节点数较少时,BCO略优;当节点数超过30时,BCO效率有重大改进,明显优于HS和AIGA。若节点数越多,BCO的性能优势越强。当节点数为60时,BCO消耗的时间仅有HS的35%,AIGA的42.5%。

实验第二部分观察算法的内部性能。我们对节点数为20的网络进行优化,图2显示了不同算法每步的优化结果。

从图2可以看出,BCO算法在前10代就已经接近全局最优点,然后在第10代-30代是迅速逼近。而HS与AIGA却会陷入局部最优点,如HS在第40代附近,AIGA在第30代附近,虽然其后跳出了局部最优,但是造成了时间和资源的耗费[17]。

4 结 语

BCO算法克服了传统进化算法的不足[18,19],在QoS组播路由问题中取得较好的效果。今后的进一步研究包括下面几个方面:1) 研究参数改变对BCO的影响,寻找适合BCO用于QoS组播路由的经验;2) 考虑将BCO推广到更多更广泛的领域中去,包括工业检测、信号处理、图像处理、机器人等方面;3) 考虑将BCO与其他优化算法相结合,例如GA、PSO、HSFL、ABC等性能优异的全局优化算法。