（计算机软件与理论专业论文）基于拉格朗日松弛法的受限低代价组播路由算法.pdf

华东拜蕊太学硕士擘位论文 摘要 目前i n t e m e t 中现有的传输模式仍为单一的尽力而为( b e s t e f f o r t ) 型服务， 无法瀵是飞速发鼹戆多媒体瘦瘸秘薅户对网绦传输质量豹筵莲要求。在这静情况 下，孩提高网络资源豹乖j 用率、为用户提佞受离服务质薰为蟊际的q o s 控靠l 技术 应逡丽生，q o s 缎播路由技术则是网络多媒体信息传输的荚键技术之一。 缀播是将单一的数据拷贝从源节点传送剡多个目的节点的网络通铸方式。实 瑗稳疆逶售夔方法毅是建轰瓣络翡缀撵褪，嚣a 白s 缀撵爨毒算法裁怒建立一揉 性髓良好的满足服务质量要求的组播树。因此，建立性能良好的组播树的o o s 组 播路由算法就成了本文研究的熬点。 零文善先分圣鼙? 缓援技术魏簇稿理论，随瑶分缨7 投揍麓基松弛算法静基本 原瑗。通过对现有的几种典蛩的受o o s 限制的缰播路由算法分析后，指出了它们 存在的不足，并提出了一种撼于拉格朗日松弛法的受限低代价组播路由算法 l r d l m r 。该算法其有以下主要特点： ( 1 ) 算法势来瓣覆薅终菸羚霆翻建嚣溺圈，簸嚣奏效翻麓了链鼹巾瓣节赢售 息，也避免了封闭圈对原图的多播不可达的问题； 。( 2 ) 算法具肖比较强的扩麟性，为了便予和其它延迟受限的组播路由算法进 货 垒戆薅递，雾法仅将延迟疆裁祭 争暖收到线缝函数孛避霞控辏靛嚣松熬，嚣样 对予带宽，丢包攀等限秘条件也可以吸收捌线性函数中进行求解； ( 3 ) 算法的效率取决于所采用的最小代价组播树生成冀法，这点保证了该算 法舆脊长远豹生命力，只要有掰的更傥豹最小代捡组搔辫生成算法的诞生，就可 戬套建强该算法串迸步求解满是廷运鞭裁祭彳孛黪缓撵褥； ( 4 ) 算法具肖可调节性，可以根据用户滞求给算法设愆松弛次数，鼷求在限 定的次数内返回棵组播树；也可以设定一个大于零的误嫠参数暑，要求在前后 袭缮维撵褥筏秘麓建哭要，l 、 二该参数，冀法簸返蓬一搽缌溪糖。， 通过严格的理论分析，对l r d l m r 算法的正确性避行了证明，并艇推理出 算法的最坏时间笈杂度仅为o ( p ( 所+ 3 2 ) n 2 一朋2 菲) ，n 为网络的节点数，, 为 蟊的带点数，p 必松弛次数。最聪，本文通过仿真实验豹缝紧分辑表骥：l r d l m r 算法猩代价往麓上优于k p p 爨法，接近霹蓊代价经髓最优静b s m a 算法；在运 行时间性能上本算法快速有效，和k p p 算法相似，远远优于b s m a 黧法；以及 算法所具有的一热特点都表明了l r - d l m r 算法有较高的实用价值。 关键谶：组播，缀播路由，s t e i n e r 树，o o s ，拉格朗日松弛算法 孥末癖蓬大学硬毒学爱论文 a b s t r a c t a tp r e s e n t ，t h ei m s t - e f f o r ts e r v i c ei st h eo n eo n l yt r a n s m i t t i n gm o d e lw h i c hi s a p p l i e di nt h eh t e m e t , b u tt h i sc a nn o tm e e tq u i c kd e v e l o p i n go fm u l t i m e d i aa n d d i f f e r e n tr e q u i r e m e n t so ft h en e t w o r k st r a n s m i t t i n gq u a l i t y a sar e s u l t ，q o s ( q u a l i t y o fs e r v i c e ) m a n i p u l a t i v et e c h n o l o g yw h i c hi su s e dt oi m p r o v et h eu t i l i z a b l er a t eo f n e t w o r kr e s o u r c ea n dq u a l i t yo fs e r v i c ef o ru s e r sw a sh e m ，a n dq o sb a s e dm u l t i c a s t m u t i n gt e c h n o l o g yi so n e o ft h em o s ti m p o r t a n tk e yt e c h n o l o g i e sf o rm u l t i m e d i a i n f o r m a t i o n st r a n s m i t t i n go nn e t w o r k m u l t i c a s ti san e t w o r kc o m m u n i c a t i o nt e c h n o l o g yw i t hs e n d i n gs i n g i ed a t ac o p y f z o ms o u i 珏n o d et om a n yn o d e sw h i c hb e l o n gt oa 孚y e ng r o u p 。c o n s t r u c t i n g 鑫 m u l t i c a s tt r e ef o rn e t w o r kh e l p st or e a l i z em u l t i c a s tc o m m u n i c a t i o n 。a n dt h eq o s b a s e dm u l f i c a s tr o u t i n ga l g o r i t h mi sau s e f u lw a yt oc o n s t r u c tam u l t i c a s tt r e ew h i c h m e e tr e q u i r e m e n t so fq o s 。s ot h i sd i s s e r t a t i o nw i l lf o c u s0 1 1o o sb a s e dm u l t i c a s t r o u t i n ga l g o r i t h m 。 - t h ep r i n c i p l eo fm u l t i c a s tt e c h n o l o g ya n dm u i t i c a s tr o u t i n gi sa n a l y z e di nt h i s d i s s e r t a t i o n , a n dt h eb a s i cp r i n c i p l eo fl a g r a n g er e l a x a t i o na l g o r i t h m i sa l s o p r e s e n t e d 。a n a l y z i n gs e v e r a lt y p i c a l ( m sc o n s t r a i n e dm u i t i c a s tr o u t i n ga l g o r i t h m s ， t h o s ea l g o r i t h m s s h o r t a g e sa r ep o i n t e do u ta n da na l g o r i t h mn a m e dl a g r a n g e r e l a x a t i o nb a s e dm e t h o df o rd e l a y - c o n s t r a i n e dl e a s t - c o s tm u l t i c a s tr o u t i n g ( l r - d l m r ) i sp r e s e n t e d 黜n e wa l g o r i t h mh a sf o l l o w i n gc h a r a c t e r i s t i c s ： ( 1 ) i td o e sn o tc o n s t r u c tac o m p l e t ec l o s u r eg r a p hf o ro r i g i n a lg 糟西，s oi ta v o i d t h ep r o b l e mt h a ti sc a u s e db yt h ec o m p l e t ec l o s u r eg r a p ha n di tu s e si n f o r m a t i o no f t h en o d e so nl i n ke f f e c t i v e l y 圆i th a sg o o de x p a n s i b i l i t y i no r d e r t oc o m p a r ew i t ho t h e ra l g o r i t h m s , i ti so n l y d e l a y - c o n s t r a i n e d ，a n da d d st h ed e l a y c o n s t r a i n e dq u a l i f i c a t i o nt ot h el i n e a rf u n c t i o n t 0d ol a g r a n g er e l a x a t i o n s i m i l a r l y , i tc a na d db a n d w i d t h - c o n s t r a i n e d ，p a c k e t l o s i n g r a t e - c o n s t r a i n e da n do t h e rq u a l i f i c a t i o n st ot h el i n e a rf u n c t i o n ( 3 ) i t se f f i c i e n c yl i e so nt h el e a s t c o s tm u l t i c a s tm u t i n ga l g o r i t h mt h a ti su s e d ， w h i c hm e a n st h a ti th a sal o n gv i t a l i t y i fan e wm o r ee x c e l l e n tl e a s t c o s tm u l t i c a s t r o u t i n ga l g o r i t h mi si n v e n t e d ，t h en e wa l g o r i t h mc a nb eu s e di ni t ( 4 ) i ti sa d j u s t a b l e u s e rc a ns e tas p e c i f i ci t e r a t i v en u m b e rt or e q u e s tt h e a l g o r i t h mt or e t u mam u l t i c a s tt r e ei nt h et i m e a n du s e rc a r la l s os e tao a r a m e t e r e n 肇东郏嚣大学硬士掌链论交 w h i c hi sp o s i t i v er e a ln u m b e rt or e q u e s tt h ea l g o r i t h mt or e t u r nam u l t i c a s tt r e ew h e n t h ec o s t 唧nb e t w e e nt w ot r e 宅$ i sl e s s h a 鑫t h ep a r a m e t e r b ya c a d e m i ca n a l y z i n ga n dp r o v i n g , t h ew o r s tt i m ec o m p l e x i t yo ft h i sa l g o r i t h m i so n l y o ( p ( m + 3 2 ) n 2 一p m 2 n ) ，ni sn e t w o r k ss i z e t j ，li sd e s t i n a t i o ng r o u p s s i z e , a n dpi si t e r a t i v et i m e b ys i m u l a t e de x p e r i m e n ta n dt h er e s u l t , i td e m o n s t r a t e s t h a t 獯一d l m ri sb e t t e rt h a nk ipa n dc l o s et ot h ec o s t - b e s ta l g o r i t h mb s m ao nc o s t p e r f o r m a n c e ；a n dl r - d l m ri sb e t t e rt h a nb s m aa n ds i m i l a rt ok p p o nt i m e p e r f o r m a n c e s ot h ep r e s e n t e da l g o r i t h mi sv e r yp r a c t i c a l k e yw o r d s ：m u l t i c a s t , m u l t i c a s tr o u t i n g , s t e i n e rt r e e , o o s ，l a g r a n g er e l a x a t i o n n i 学位论文独创性声明 本人所量交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成皋据我所知，除文中巴经注明引用的内客外，本论文 不包含其他个入已经发表或撰写过昀研究成果。对本文酶研究做出重 要赏献的个人和集体，均巴在文中作了明确说明并表示谢鬈 作者签名：一j 亟盈车一一 日期2 1 ；! ：上兰一 学位论文授权健用声暖 本人宠全了解华东癖燕大学有关像螫、使麓学位论文粒规定，学 校精权保留学位论文并向闲家主管部门或其指定机构送交论文的电 子教和纸震舨霭投褥学位论文燕予黪赢利器戆蟪少量复裁势允诲论 文进入学校图书馆被查阅有权将学位论文的内客编入有关数据库进 行梭索。有权将学位论文姆标题和攮簧汇浆出版。保密螅学位论文在 解密后适用本规定 学位论文作者签名：角极 嚣裳：早地一 导师签名：轫，j 毒 隗 竺2 ： 肇衷拜范丈学硬士擎毖论文 第一章绪论 本章主要对缀播技术的产嫩背景、发展简介、技术优点及应用前景进行描述， 最嚣余缀本文爨皴瓣主要工终及鳃缓结擒。 1 1 组播的产生背景 骜代社会已经逑入薅惠薅代，i n t e r n e t 撵隽蓓塞柽会豹主要传播媒体，镬褥 网络技术大量应用并飞速发展。由于音频视频会议、推送技术、大规模协作计 算、为用户群进行软件升级、网络代理、镜像和高速缓存站点等多媒体威用，都 蔹羧予麸一个圭瓠淘多令主规或砻扶多令主魂囊多令圭撬发送嚣一镶感豹能力， 面农i n t e r a c t 上分发信息酶主机的数目可能多达数十万台，发送信息需簧更高的 带宽，并且大大嫩超出了单播通信的能力，因而一种能最大限度地利用现有带宽 资源的通信方式唆 播技术发展起来。 缝撵是一静允洚摹令或多个发送者，( 缀撵濂) 一次笈邀份薮摆挎燕到多令 接收者( 组播组) 的网络通信技术。组播源牛巴数据发送到特定的组播缀，只有属 于该缀播组的成员才能接收到该数据，由予光论有多少个嗣的地址，栈整个网络 孛熬任露一条链鼹上灵转送一徐数据捧炙，嚣建虿苏大大戆苓省圈络鬻宽资源， 提离了数据传输逮率，减少了擞_ 干网的带宽溪求以及主千网出现拥塞的可能性， 而网络带宽是制约实时和多媒体应用发展的主要瓶颈，所以组播技术成为研究和 应燧静热点。 1 2 网络通信方式 溪户戆数据瑟麸一个终鲻发送舅舅一令终漩，蓄先蘩镶定黉辕路囊，苓窝兹 通僖方式其确定路由的方式也不鬲，如今网络的通信方式主要有以下几种： 1 ) 单播( u n i c a s t ：p o i n tt op o i n t ) ，点到点的通信方式。 2 ) 鳆摇( m u l t i c a s t ：p o i n tt om u l f i p o i n t ) ，点到多点骢逶信方式。 3 ) 广疆( b r o a d c a s t ：p o i n tt oa l lp o i n t ) ，点封所骞节赢簸透信方式。 4 ) 汇播( c o n c a s t ：m u l t i p o i n tt op o i n t ) ，多点到单点的通信方式。 5 ) 群播( m u l t i p o i n t t om u l t i p o i n t ) ，多点对多点的通信方式。 国饪撵 7 ，称为线性规 簪夕， 3 2 3 代理松弛 当( 3 1 ) 的限制条件过多时，可以用代理松弛法来简化，通过一个限制 荟【荟4 t ，户，著气 n ，x、菇 华幕师范大学硕士学位论文 来代替( 3 1 ) 中的k 个限制条件 三吒。产气，t - 1 ，2 3 一，k 极端情况下，可以用一个限制条件 荟【善户，2 善饥 松弛限制血6 。代理松弛法保证目标函数、整数变量限制不变，且因限制条件 的减少造成计算量的减少。 3 3 拉格朗日松弛方法 一些组合优化问题是n p h a r d 的，也就是说在现有的限制条件下很难求得最 优解。但在原有问题中减少一些限制条件后，求解问题的难度就大大减小，达到 在多项式时间内求得被减少限制问题的最优解。因此，将这些被减少的限制条件 称为难限制条件，对于整数线性规划问题，将难限制条件吸收到目标函数后，问 题就变得容易求解，这时解的质量完全依赖于吸收到目标函数时所选取的参数， 而拉格朗日松弛方法正是应用了这个原理。 为了适合拉格朗日松弛方法的讨论，将整数规划问题妒描述为 z p m i n c 7 j ， ( i p ) s t a x b ( 复杂约束) b x d ( 简单约束) 毒z ! 其中，0 ，b ) 为m 如+ 1 ) 整数矩阵，d ) 为fx 0 + 1 ) 整数矩阵。记i p 的可行解 区域为 s - k z ：j a x z b ，m2 d 在腰模型中，血= b 为复杂约束的名称来源于：如果将该项限制条件去掉， 则口可以在多项式时间内求到最优解，即假定 2 口- m i n c 7 z b x d ( 简单约束) ( 3 4 ) 工z ： 可在多项式时间内求得最优解。 2 0 华东师范大学硕士学位论文 对于给定的a 一( 九，如，九) 7 0 ，m 对a 的拉格朗日松弛定义为： z 埔( a ) 毒m m c 7 z + 矿( 6 一彳z ) ( u t ) s lb x 苫d x z ： 记u t 的可行解区域为 s 。一k z ：i b x ，d 定理3 1l r 同( 3 4 ) 有相同的复杂性，且若口的可行解区域非空，则 v a 0 辛z 蚀( a ) z 俨 证明： 令g ( x ，a ) 1 c t x + 矿p 一 则g ，a ) 1 ( c 7 一x r a 弦+ 舻6 为x 的线性函数。而r 6 为常数，又因为它 们的限制条件相同，故u t 同( 3 4 ) 有相同的复杂性。从s 和s l r 的表达式很明 显看出s s n ，并且 由出毫b ，得 v a 苫o , x e s 辛c r x + 矿( b 一爿x ) sc 7 工 最终可得到v a 之0 辛z ( a ) 墨z 。 定理3 1 说明拉格朗日松弛是i p 的下界，我们需要求的是与z ，最接近的下 界，也就是求解 ( l d ) z m 。雩警2 m ( a ) 问题l d 则称为口的拉格朗日对偶。 定义3 1 若慨，y d ，满足 饿+ ( 1 - - a ) y e d ，0 s 口1 ， 则称集合d 为一个凸集。 对离散点集q 。但l f1 l 2 , ，它的凸包定义为 c o n ( q ) = p 一口。只i 口；o ，吒一l _-， 定理3 2 若拉格朗日对偶的目标值z l d 有限，则 z t t ) 一m i n c 7 工la x ：- b ，x c o n ( q ) ， 其中 q - x f b x d ，石z ：。 z 船( ) 。m i n ( c 7 - a a 弦+ 矿6 ，其中x q - m i n ( c 7 一彳净+ 矿6 ，其中石珂 ) - m i n c r x + f f ( b - a x ) ，其e p x e c o n ( q ) 。 设c o n ( q ) 的极点为仁l 七日，极方向为 r 7i ， ，则 m m ( c 7 一矿爿皿+ 6 ，其中x e c o n ( q ) ，等于下式： i 。* ，若存在j ，满足( c 7 一f f a ) r i 0 ， 气 tm i n c 7 石+ ( 6 4 石) ，中x e c o n ( q ) ，足k 。 而由z 。有限，则有 rj a 乏0 ，w e j ，使得( c 7 一f f a ) r j 0 ， 1 铴- m a x z ( a , ) - m a x ( m i n i c 7 + z t ( b 一i x ) 】) ， l 其中m s l x 作用于a 0 ，m i n 作用于七k 。 整理得到 z l d 。m a x r s , t c r x + ( 6 一a x ) 苫叩，v k e k ， ( c 7 一4 ) ，乏0 ， ， 旯2 0 。 z 工d m a x r s t r + z r ( a x b ) c 7 x ，v k e k ， a r 。s f 7 r ， w ， a2 0 。 由线性规划的对偶理论，上式的对偶线性规划为 2 2 肇东舜苑大学硬士攀趣论文 名肼幽，囔彬荟 7 ) 瓢氛荟”“ 喹叩蓍即协6 哩， 4 t 统多j 惫莰 最终蹩理得到 z 肺一m m c 7 工，凰a x 扫，x e c o n ( q ) i m 弧 c 7 茹l 酝矗，x e c o n ( q ) 。 肼问题的线性规划松弛为 z 炉一曲。r 嚣 ( t 秘 s t a x b ( 笈杂约束) b x d ( 简单约束) x 晟： 定理3 3 若线性娆蔻| 桧豫膳存在可簿翳，燹| j z t p5 z 工d 茹腰。 涯甥；由 q n x 霹l 出每6 c o n ( q ) n x r ：i a x z b g 毫鬈l b x 菇 n x 霆：l 氟基矗 褥 c 洲( q n x 冠：l 厥以) c o n ( q ) n x 震：l 出6 恤丑：l 出d n 缸彤1 瓜z b 缝合定理3 2 ，缮窭 2 律tz 溉z 憎。一 从定理3 3 可以看出，采用拉格朗日松谶对偶后的目撂值：。是职阀题的一 个下赛且比z 工p 更接近最优僮z 。 2 3 肇寐搏范大学硕士学经论文 3 4 投格朗日松弛算法 定义3 2 若g ：r ”一兄为凹荫数，x 殿”，n 量s e r “满足 v k 擞”：g o ) + s r ( 苫一善) 之g ( x ) 刚称s e r ”莠g ( d 在x 的一个次梯度，g c d 在石的所寄次梯度组成的鬃台记为 船“+ ) 。 、 宠疆3 4 若g ( 磅茺鹜羲数，蔗m a x 酝( 磅l 善霆8 簸饶解静充分必簧条箨 是o e o g ( x ) 。 谖骥： o e 皓0 ) # o * ( x - x ) 急9 0 0 一9 0 ) ，v x e r “ 姊g ( x ) g o ) 坛矗“ 羧格朗鑫捡澈方法夔主要z 律是提供臻瓣题静一个下葬。l r 蠲瑟静一个良 较好的下界所对应的解也应与m 问题的最忧解相近，在媳样的逻辑下，产生了 拉格朗日松弛算法，拉格朗日松弛算法包括两个阶段： 第一跨羧次猱凌往恁e 这狳菠逶遥求i * z 拉孟) 瀵跫定义3 2 懿次裙疫，逐 步改进：从q ) 的僦，使得z 。( a ) 与z 上d 充分接近。 第二鼢段可行纯。在l r 鹣瓣为不可行髌时，对其可杼化。 1 梯度优化算法 s t e p l 任选一个初始拉格朗臼乘予丑，fm 1 s t e p 2 薅囊，麸豫( 孟) 孛镬逸一令次梯发s ，； 若s ，一0 ，则 达到最优解而停北计算； 否爨g 冬“t n l a x z + e , s t 砖， 一 + l ； 重复s t e p 2 。 猩s t e p 2 中，蛾满足下式 磊馥- ，纛鳞_ o ， _ 华东疖范大学醺士学位论文 但实际中不可能如上式一样无限次迭代，必须选定合理的停止原则。 2 箨壹霖瓣 1 1 迭代次数不超过n 这憝一种最为简单的停止原则，无论解的质量如何， 到达迭代次数则停止。嫩容易控制计算的复杂性，但解的质量宠法保证。 2 ) 墨一o g 教五茸缓) ，这蔻爱为理怒静敬容，由定联3 4 霉矮，魏辩迭囊了 拉格朗曰对偶问题的最优解。然而柱实际计算中，由于问题的复杂性和 计算机本身的计算误麓，这样的结粜很难达到，常用技0 sg 来代替，其 串隽绘定菲负数。 3 ) z 丹( ) 一：( ) ，在= 肿( ) 和铀( ) 可变的情况下，这时袭承已经得 到p 鲍最傀解，最傀饿为珏。z u p ( 五) - 麸全连逶越爨舀g 审裳残一揉以澈苓点s 为棂豹潢是延迟袋铡条 孛豹 生成树r ，与p r i m 算法相似，每次将代价嫩低的边加入到生成树，备边代价按 3 3 牮笨簿范夫学矮士学觳论文 以下规则之一取值： c 毋勘4 黝+ 魄田 c o s t t o t r e e ( u ) + c o s t ( u ，) ) o 譬r ) ) c o s t t o t r e e ( v ) - c o s t t o t r e e ( u ) + c o s t ( u ，v ) ； p a r e n t ( v ) - h 、： i f ( ( v e u ) a o 售d ) ) d d + p ； ) e n df o r e n dw h i l e e n dw h i l e ) m c t h 算法选择节点的尺度始终是距离当前组播树的代价最小，生成的组 播树与最优树的总体代价比值不超过2 ，且有良好的平均性能，算法最坏时间复 杂度为o + 3 2 ) n 2 一m 2 凡) ，其中n 为网络节点数，m 为目的节点数【4 2 】。 定理5 2 对于任意两个松弛参数 ，九，且o 墨九，若 写一m c t h ( c + d ) ，疋一m c t h ( c + 九d ) ， 则c o s t 伍) c o s t 仍) ，d e l a y 仉) d e l a y ) 。 证明： 因为在聚合函数c 。一c + 硝中，显然随着a 的增大，如切在c 。( 新的边权) 中的权重也随之增大，而c o s t 的权重则相对减少。根据m c t h 算法定义，可得 3 9 华东师范大学硕士学位论文 定理2 成立。 推论5 1 设0 使得豫最大，如果a s f ，那么如姆) 之；如果a f ， 那么如缈仍) s 。 证明： 由定理5 1 可得 ：九x 如姆) 苫d e l a y ( ) 而刀使得l r 最大，也就是说是正好满足延迟限制条件中代价最小的组 播树，由定理5 2 的证明过程可知此时如蛔，( ) 一a ，得 如缈以) a 对于如果a 苫f ，那么d e t a y ( t 。) ，同理得证。 求拉格朗日对偶( l d ) 问题希望下界朋+ 尽可能大，于是按l r ( a ) 的上升方向 逐渐逼近下界最优值。由定理5 2 可知，就是随着a 的增大，最终m c t h ( c + 从) 生成的t 是最接近最优受限代价最小组播树的。但在实际计算中，不可能无穷迭 代，为了达到最优值，我们采用目标值上下界相等的停止原则闭，设z 品和7 0 分 别为最优值的上界和下界，当q ( z 品) t q ( z 0 ) 时，停止迭代。 由聚合函数c - c + 硝可得 c o s t ) + a d e l a y ( 珞) 一c o s t ( ) + a d e l a y ( t ) ，得 a - 竺d e r a y 辫罴d e l a y 黠 c ( z 品) 一( 7 厶) 定理5 3 设 五- m c t h ( c + d ) ，疋- m c t h ( c + 屯d ) ，l m c t h ( c + 九d ) ，且厶 + a d e l a y ( t ) 的值。 2 l r d l m r 算法具体描述如下： l r d l m r ( g ，5 ，m ，a ) 尹求出蘑g 审激s 为源，m 必缰播缰苓瘫集合翡延遮不大予矗酶低畿价缰撵 树r + 4 1 华东师范大学硕士学位论文 瓦衄_ d i j k s t r a ( g ，5 ，m ，d ) ： 宰利用d i j k s t r a 算法求得最短延迟树。 i f ( d e l a y 瓯h ) a ) ，若最短延迟树都不能满足延迟限制条件，则不可能有满足延迟条件的树 ， 无解，程序退出协商值； e l s e z 啉，一m t c h ( g ，j ，m ，c ) ； 严利用m t c h 算法求得最小代价树 ) i f ( d e l a y ( ，) a ) r e t u r n z 乙；求得满足延迟限制条件的低代价组播树 ) e l s e 进行拉格朗日松弛，求解满足延迟限制的低代价组播树 w h i l e ( t r u e ) a - 竺堕生芝l 掣； 更新松弛参数a d e l a y ( r 。，) 一如姆( 瓦“) r m c t h ( g ，s ，m ，e + 硝) 5 宰用m c t h 算法对于新的边权c + 埘求得新的组播树p i f ( ( c ( r ) - c ( z ：断) ) d r ( c ( 丁) 一c ( z 谢，) ) ) 严满足上下界停止等待原则，求得满足延迟限制的低代价组播树，算 法退出，算法实现中为了快速收敛，也可设定迭代次数+ ， r e t u r n 气。；，返回满足延迟限制的低代价组播树 ) 缮衮癖蓬大学颈毒擘住论文 ，进一步更新松弛参数a 前，更新k 或z o 4 i f ( d e l a y ( t ) a ) 气姆一r ；z 五蛳满足延迟限制条件 e l s e z 0 。一r ；z 0 ，不满足延迟限制条件 e n dw h i l e 5 。5 媳- d l m r 算法分析 定理5 a 假定，和磕，磕。，瑶，表示 l r ，d l m r 算法谯执行期间生成的组播树序列，根据算法特性，可以褥如有以下 嚣茂戏立： d e l a y ) d e l a y ( r 3 _ ， 矗i l ) 证明： 由定理5 3 和算法流程可以得出每次得到的瓦如作为可行解不断程接近最大 篷，帮毛如煞延遴不瑟在增太，毽慧是滚跫延送疆涮条移，帮式( 1 0 ) 裁立；丽 理可证式( 1 1 ) 成立。 推论5 2 如果图g 存在满足延迟限制条件的组播树，则l r d l m r 算法总 麓袋褥这嚣懿缀攘耱爻 证明： 因为在算法撼述中仅有两处有r c t u m 语句，而且均悬返回满足延邂限制条件 的缀捧树，结会定理5 4 ，缀嬲显看出只要雾在满是延迟限制条件的缎播树，则 一定可滋褥至这样黪组搔褪戥 推论5 3 在算法中给定一个松弛迭代次数让算法停止是可行的。 证明： 赉定理5 ，4 魏搓论5 。2 及宅袋豹 歪胡避程胃翔，在棼法孛绘定一令裣越遥鼗 次数来替换上下群相等则停止的方法是可行的。 华象郊藏丈学磺圭学霞论交 定理5 5 在算法中给定一个代价误差参数s 来替换辣法中上下界相等则停 止熬方法也是可符瓣。 诞孵： 假设采用上下界相等停止的方法最后髀法返回与最优解最近的组播树为 幺，若算法谯若干次迭代后，当前有最新的和噶，显然有 c o s t ( t 量，) c o s t 谨k ) ，弱毒滚 罄至l 下式成宠： c o s t ( 磁蚴) 一c o s t ( ) u e o ，甜) ； e n dw h i l e f o r e a c h n o d eh v i f ( d e g r e e o n o