论文研究-基于局部信息的时延和时延差约束的组播路由.pdf

所需积分/C币:9 2019-09-13 05:32:07 592KB .PDF
收藏 收藏
举报

组播通信是从一个源节点同时向网络中的多个目的节点发送分组的通信服务,它一般提供一个以上的端到端的服务约束,实际的路由算法在应用时可以受到多重约束,解决这类问题的组播路由算法是NP完全的。在研究了构建组播树的相关算法后,提出了一种新的时延和时延差约束的低代价组播路由算法—DDVMC。该算法采用基于贪婪策略的Dijkstra最小生成树算法,利用局部信息来构建低代价组播树,很好地平衡了树的代价、时延和时延差。仿真表明,该算法能正确地构造出满足约束的组播树,同时还具有较低的代价和计算复杂度。
2012,48(34) Computer Engineering and Applications计算机工程与应用 价比较大的链路;随着树的建立和链路长度的增加 步骤1初始化。利用 Dijkstra SPI算法,计算 链路时延越来越大,最佳链路代价应越来越小。具源节点到所有目的结点的最小时延树T,求出时延 体来说,对于组播树T,组播节点u距离源节点s较约束最大值△和时延差约束最大值o。 近,其到s的时延比其他距离s较远的组播节点到s的 步骤2如果<△mx或者6<mx,则符合约東 吋延要小。因此,构造组播树初期,如果Dela(ω)满条件的组播树不存在,算法退出。否则执行步骤3。 足时延约束条件式(1)和时延差约束条件式(6),则 步骤3初始化生成树T。 从s到u的路径将被选择;建树后期,如果树中存在从 步骤4从目的结点集中选取到树T代价最小且 s到v的的路径p(s,)满足 Delay(n)< Delay(),则符合约束条件的结点加入树T,重复该过程,直到所 Delay(v)- Delay()>d。尽管从s到u的路径满足有目的节点加入树,输出树T。 所有约東,节点u并不一定能添加到树上 算法的伪代码描述如下 定理1在组播树7中,δ< Av Delay(≤△ 输入:G=(,E),s,M,A,δ 证明先证明0<δ<Δ。如果δ=0,这意味着所 *s∈V为源节点,McV-{s}为目的节点集,时延约束 有从源节点到目的节点的时延相同,目的节点在相同的上限为△,时延差上限为(,6均为正实数)* 时间点上接受数据,这种情况会导致网络拥塞,应当避 输出:以s为树根的时延受限的满足时延差的 Steiner树 免。如果δ>Δ,则退化到时延约束的最短路径问题。 T spanning M∪{s} DDVMC(G,S,M,△,O) 因此应有0<δ<4。假设 Delay(u)<δ,根据式(6)应 begin 有 Av Delay(m)=0,由此可推得∑(=0 run Dijkstra STP(G, S, M, 4. dto compute the lowest ∈Hr(S,V),Vv∈M 这和式(1)是矛盾的,故Dela(u)>6,同理 Av deluy(m)> possible bound Amax and d 0。因为Dela()≤△,有∑ Delay(m)≤△.m,即 if a >4 then return null; if 8 >s then return null T←8;Q←;Cos(s)=0; Delay(s)=0; / is a priority queue*/ 证毕。 for i=l to n do 根据定理1,为了兼顾各约束条件,组播树的平 Puer, u pu is a pointer pointing vertex u's parent*/ 均时延 Av Delay()可重新定义为: Begin △(vu∈M, if Delay(u)≤o Cost(u)← Max nunber; Delay(u)∈- Max number Av Delay T) Delay(u) (7) u plu]< NIL end; yt∈M otherwise Delay(v) Av Delay (r)<w 为了利用局部信息,结合DDMC( Destination -Driven repeat routing for low- Cost multicast)算法,重新加入节 点ν的链路选择函数 Extracting vertex u from queue Q Cost(v)=l,(uCost(u)+ Cost(u, v) (8) 7←TU{u}; 式中Cos(v)为源节点s到节点v的链路代价,Co(,) for all y do 为从节点u到节点ν的链路代价,vT,u∈T。1为 begin 指示函数,定义为: if Cost (v)>Id(u, v) Cost(u)+Cost(u, v))and Delay(u Delay(u)+deluy(u, v)<A)then D)=1Dln()+Dey1y∈M 1.u g M if Delay(u)+ delay(u,v)≤ o then Ay Delay(T)=△ 上式的含义为日的节点的时延偏离时延约束上 f lAv Delay(7)- Delay(u)+ Delay(u,v)|≤δ 限越远,其赋予的优先级越高,节点u成为新加入节 then Cost(v)=l(u, v)Cost(u)+Cost(u, v) 点ν的父节点的机会就越大。 up[v]← 根据上述分析,时延和时延差约束的最小代价 ←O 组播算法 DDVMC( Delay and Delay- Variation bounded end; Minimum cost multicast algorithm)可描述如下: 刘维群,李元臣:基于局部信息的时延和时延差约束的组播路由 2012,48(34) until 定理4算法的时间复杂度为O(n2)+O( elon)。 return T: 证明算法调用 Dijkstra_STP算法计算Δ-和 δm的时间复杂度最坏情况下为O(n2)。初始化Cost() 5算法分析与仿真实验 Delay(u)和up的时间复杂度为O(m)。Q为优先 511算法性能分析 级队列,其最大长度为n,节点出队列的时间复杂度 定理2只要满足给定时延和时延差约束条件的为Oogm)。处理u的邻接点v,其时间复杂度为 组播树存在,算法能够构建符合约束条件的组播树 O(ogn)。因此,算法总的时间复杂度=O(n2)+Om)+ 且包含组播节点。 2O(log n)+O(log n)2(computing u' adjacent nodes 证明v∈M-{s},根据算法,T的每个子树都是 D(n)+o(n)+nO(log n)+eO(ogn)=O(n)+O(e log n) 由边p(,s)构成的,因此满足约束条件的组播树存52仿真实验 在。算法中树的构造是从组播集M中选取节点加入 本文以VC+-为工具开发了仿真软件包,对 到树T中,直到M为空,因此所构成的树包含了所有 DDⅥMC算法进行了仿真。为了保证结果具有实际 的组播节点。 意义,实验采用文献[10-11]所用的方法来生成随机网 例如,如图1所示的网络,若源节点为S,目的节络模型。该模型产生的随机网络接近实际网络,广 点为A、B、D和F,边上的参数对表示(代价,时延),泛用于路由算法的仿真。该模型中,n个网络节点随 时延约束A-5,时延差约束δ=3.5按照算法得到的机分布在200×200卡尔坐标系内(相当于2000km 组播树如图2所示(粗线表示) 2000km的矩形区域),任意节点u,ν间存在边的概 率为 6 p(u,v)=Expl (t,y) (10) 其中,d(u,v)表示节点到v的距离;是任意两个节 点间的最人距离。参数x/在0和1间取值其值的 (8,1) 选取可以控制生成的图的密度特性。α影响长、短链 路的比重,α越大,长链路的比重越大。参数B控制网 络的平均节点度数,B越大,网络平均节点度数越 C (5,06) 大。代价定义为两个节点的距离,链路的时延定义 图1树络拓扑图 为代价乘以一个0到1之间的随机数。实验中,a= 定理3算法在构造组播树时不会形成环路 0.25,B=0.2,网络节点平均度数为6,实验次数为100 证明假设与树相连的部分形成环路,则必有一次,取其平均值作为测量值。 个以上节点与树相连接,则组播节点到其中一个节 图3所示为网络节点数为55,目的节点数为11, 点的路径是组播节点到已有树的代价最优路径,因时延上限Δ取-21,时延差取不同值时, DDVMC算 为最优路径与树只有一个节点相连,故假设不成立,法和DVMA算法求解成功率的对比。从图上可以看 即无环路形成。根据文献[9], Dijkstra SPT算法也不到,时延差要求不高时,两个算法的求解成功率接 会形成环路,因此按本文算法构造的组播树没有环路。近;随着时延差值的减少, DDVMC算法比DVMA算 (5,1 5,1 (8,1) (8,1) E (90s) (5,0.6) (b) (d) 图2算法构造组播树过程 80 2012,48(34) Computer Engineering and Applications计算机工程与应用 4.6 E& dVMA 4.4 DVMA 100-0 DDVMC 4,2 DDVMC 4333332 当26 40 2.2 20 10 l11l1 0864 cm+nNmo9=m±≌≌s2R 导怒R房京88 时延差δ 网终节点n(目的节点m=m/10) 图3 DDVMC算法和DVMA算法求解成功率比较 图4 DDVMO算法时延差和网络节点的关系 法的求解成功率高。当δ≈Δ时, DDVMC算法和 tional Journal of Communication Systems, 2004, 17(10) DMMA算法求解成功率接近100%,此时两个算法均 985-1000 已退化为时延约束算法。 [2」李元臣,刘维群基于共享边的时延约束组播路由算法 图4所示为 DDVMC算法和DVMA算法构造组 计算机应用,2009,29(11):2901-2903 播树时时延差和网络节点数的关系,实验时日的节3]刘维群,李元臣时延约束的链路选择平衡优化组播路由 算法门计算机应用,2011,31(4):925-927 点数为网络节点数的10%。从图上可以看到,本文算 [4 Rouskas G N, Baldine IMulticast routing with end-to-end 法的时延差小于DVMA算法的时延差,当网络中的 delay and delay variation constraints[J]IEEE JSAC 中目的节点数目增加时,非组播节点减少,可选路径数 1997,15(3):346-356 随之减少,两个算法的时延差都略有增加。 5 Guo L, Matta I.QMDR: an efficient dependent multicast routing algorithm[ C]/IEEE Real-Time Technology and 6结束语 Applications symposium, 1999: 213-222 传统的时延和时延差约束的启发式算法的整体6tcer, oun CScalable multicast routing algorithm for 性能不高,一般不能直接适用于实际网络。针对这 iation constrained minimum-cost treelo 2000:1343-1347 些问题,提出了一个快速有效的满足时延和时延差 [7] Mokbel M FNew algorithms for multicast routing in real 约束的组播路由算法。算法基于局部信息,平衡了 time networksDFacully of Engineering, Alexandria 各约束参数,对组播成员给予了相应的优先级,因此 有效地降低了组播树的代价。仿真结果表明,本文8] Shaikh a, Shin k g Destination -driven routing for low-cost 算法与DMA算法相比,更具实用性,对实时组播应 multicast[J.IEEE Journal on Selected Areas in Commu- 用能提供一定的参考。网络中提供QoS约束的组播 nications,1997,15(3):373-381 业务很多,本文仅对时延和时延差约束的组播路由91KouL, Markowsky G, Berman. I a fast algorithm for 问题做了探讨,还有很多问题有待于今后研究,如动 Steiner trees in graphs[ ].Acta Informatica, 1981, 15(2) 141-145 态组播路由、点到点的多路路由、分层组播由、分布 [10 Waxman B W Routing of multipoint connections[J]IEEE 式组播路由、以及组播路由的可靠性和快速收敛特 Journal on Selected Area in Communications, 1988,6 性等。 (9):1617-1622 [11] Salama H F Multicast routing for real-time communica- 参考文献: tion on high-speed networks]. North Carolina State [1] Aissa M, Mnaouer A B. A new delay-constrained algo- University, Department of/Electrical and Computer Engi ithm for multicast routing tree construction[J].Interna neering, 1996

...展开详情
试读 5P 论文研究-基于局部信息的时延和时延差约束的组播路由.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38743481 如果觉得有用,不妨留言支持一下
    2019-09-13
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于局部信息的时延和时延差约束的组播路由.pdf 9积分/C币 立即下载
    1/5
    论文研究-基于局部信息的时延和时延差约束的组播路由.pdf第1页
    论文研究-基于局部信息的时延和时延差约束的组播路由.pdf第2页

    试读已结束,剩余3页未读...

    9积分/C币 立即下载 >