（计算机软件与理论专业论文）下一代通信网络的资源优化及任务调度问题.pdf

摘要 摘要 全光传输网络以其稳定性好和传输容量大等优点，正迅速成为带宽需求较大 的下一代通信网络主要发展方向之一。基于波分复用( w a v e l e n g t hd i v i s i o n m u l t i p l e x i n g w d m ) 技术，可以在一根光纤中同时传输多个不同波长的光信号。 从而可以在不需重新铺设物理网络的情况下，大大提高光纤的传输容量。全光传 输网络通过网络节点上的全光终端设备来实现：在传输一个请求的过程中始终保 持光信号的状态。常用的全光终端设备包括被长转换器、光学加载器及下载器、 光学分光器、全光交换器等。本文主要研究了如何使得全光树形网络上给定一 个请求集合所需光学加载下载复用器的数目最少( m a d m 问题) ；在使用工 作波长可调节加载下载复用器的不同拓扑结构全光传输网络上，如何使得任意 请求集合的总传输时间最少( s t a d m 问题) 。 无线通信网络则因为它不需要事先的硬件铺设、使用灵话方便、可以在移动 过程中保持通信等特点，也是下一代通信网络的主要发展方向之一。本文主要研 究了如何在无线通信网络上引入小世界现象来提高无线通信网络中通信请求的 传输效率。 基于单跳多信道通信模式的全光传输网络模型和无线通讯网络模型，本文主 要研究了如何调度离线或在线情况下的任意一个请求集合，使得总调度时间最 少。 本文的主要贡献与创新工作包括以下一些内容： l ，以前的研究者主要考虑了对称全光环形网络上的m a d m 问题，丽本文研 究了对称全光树形网络上的m a d m 问题。酋先给出了一种多项式时间的路 由算法，并证明了它可以通过对给定的请求集合进行路由来使得它所需要的加载 ，下裁复甬器( a d m ) 数目最少；接着在所需要的a d m 数目最少的前提下， 基于已有的对称全光树形网络上的波长分配算法，本文还可以保证所需要的波长 数达到贪心最优。如果使用波长转换器，还可以进一步减少所需要的波长数。 2 以前的研究者研究了针对节点上放置不同加载器和下载器的全光网络上 中国科学技术大学计算机系博一| ：论文 任务凋度问题，而本文根据已有的光学设备制造方面的文献，构建了工作波长可 以调节的光学加载下载复用器模型( 可调a d m ) ，并提出了基于这种光学设备 的全光网络任务调度问题( s t a d m 问题) 。首先本文给出了单向全光线形网 络上s l a d m 问题的一个路由及波长分配算法，并证明了该算法可以同时使得总 调度时间和所需波长数最少。该算法可以简单的应用于对称全光线形网络，并得 到近似比为2 的算法。接着本文给出了对称全光树形网络上s 似d m 问题的 一个利用星形网络上情况的近似算法，并分析了它的近似比。然后本文基于 特殊情况下的s t a d m 问题的一个最优算法，给出了对称全光环形网络的一个常 数近似比的近似算法。将该算法应用到一般网络上，同样可以得到一个常数近似 比算法。 3 a h m e dh e l m y 等人首先研究了如何将小世界现象应用到多跳无线通信网 络中，并考察了它对无线通信网络请求传输性能的影响。但他们主要是基于无线 通信网络的逻辑拓扑结构进行分析的。本文提出了一个在无线通信网络的物理拓 扑结构上实现小世界现象的方法，并且通过试验表明它可以大大提高无线通信网 络的请求传输性能。 4 请求在被传输过程中，通常需要发送一些包含控制信息的数据包。本文 提出了具有一个控制信道及多个数据信道的单跳多信道通信网络上的新型任务 调度问题模型，并分析得到离线情况下l i s ts c h e d u l i n g 和l o n g e s tp r o c e s s t i n g t j m e 矗r s t 调度策略的近似比分别为( 5 2 1 2 m ) 和( 2 + 1 2 ( m + l ”，其中( m + 1 ) 为信道数目， 以及在线情况下l i s ts c h e d u l i n g 调度策略的竞争比为( 7 2 1 2 m ) 。 关键词：全光网络，无线网络，多信道通信网络，任务调度问题，组合优化算法 近似比，小世界。 摘要 a b s t r a c t t h e a 1 1 叩t i c a l c d m m u n i c a t i o nl s b e c o m i n g o n eo ft h em o s t p r o m i g i n g t e c h n i q u e s f o rt h e n e x t g e n e r a t i o n n e t w o r k sf o ri t s h i 曲s t a b i l i t y a n d l a 唱e t f a n s m i s s t o nb a n d w i d t h m u l t i p l e o p e 圮俎s i 鲷a l s 母v c fd 瓣e r e n tw a v e l n g t h sc o 吐l db e t r 觚s m i t t e dt h r o u g ho n e 纳e r s i m u l t a n e o u s l yb y t h e t e c h n i q u eo f w a v e l e n 舀王t d i v i s 主o n m u l t i p l e x i n g ( w d m ) ，w h i c hc o u l d 掣e a t l yi n c r e a s e t h eb a n d w i d t ho fa 1 1 o p t i c a l n e t w o r k s ，t h ea l l o p t l c a h r 锄s m i s s i o nc d u l db ea c h i e v e db ym ea 1 1 i d p t i c a l t e 肿j n a l d e v i c e s ，i n c l u d i n gw a v e l e n g mc o n v c r t e r s ，0 p t i c a lt r a i l s m i t t e r r e c c i v e r ，l i 曲ts p l i t t 钉 a n da l l o p t i c a l s w i t c h ，e t c ii nt kn e 呻o r kn o d e st h i st h e s i sc o n s i d e r s1 ) h o wt o n l i n i m i z em en u m b e rd fr e q u i r c do p i i c a l a d d d f 叩m u l t i p l e x e r ( a d m ) f o ra 斟v e n r e q u e s t s e to nad i r c c t e df i b e r 订e e ，d e n o t e da st h em a d m p r o b l e m ；2 ) h 。wt o n h n i m i 辞h e 雠出t r 孤s m i s s i o nt i m ef o f 勰y t e q s t s e to n n 玉l 一。p t i c a in 吐w 。r 虹w t 氐 o n ew a v e l e n 舒h t u n a b i e a d m ( t a d m ) p e r n o d e ，d e n o t e da st h es t a d mp r o b l e m t h ew i r e l c s sn e t w o r k sa r ea 1 5 0o n eo ft h 守m a i n t e c h n i q u e s f o rt l l en e x t g e n e r a t i o n c o m m u n i c a t i d nn c t w o r k s ，l n c em e yd dn o tn e e dp d ri n f r a s t r u c t u r e c o n s t m c t i o n s ，a n dk e 印u s e r sc o r u l e c t e de v c nd u r i n gm o v i n 吕t h i st h e s i sc o n s l d e r s h o wt oi n t r o d u c et h es m a l lw o r l d p h e n o n l e n o ni n t ot h cp h y s i c a lt o p o l o g yo f w i 【e k s s n e m o r k st di m p r o v et h e 仃a j l s m i s s i o ne 伍c i e n c y b a s e do na s i n g l e - h o pm u l t i p l e - c h 籼e l c a m m u n i c a t i o nn e t w o r k m o d e l ， i n c l 砸i n gt h 亡a b o v et w om o d c l s ，t h j st h e 鲑e 啦亭oc o n s i d 甘sh o wt oa s s i g nas a n j n g t i m ef o re a c h r e q u e s t so f a r e q u e s ts e tt om i n i m i z em e t o t a lm a k e s p a 芏1 t h er n a i nc o n t r i b u t i o n sa n di n n 日v a t i o n so f t h i st h e s i si n c l u d e ： 1 ) p r e v l o u sw o r km a i l l l yc o n s i d e r e d t l l em a d m p r o b l 锄d nm es y m m e t r i c a 1 1 - o p t i c a lr i n gn e t w o r k s t h i st h e s i ss t u d i e st h em a d mp r o b l e mo nt h es y i n m e t r i c d i r e c t e d b e rt r e e ，孤dp r o p o s e sap o l y n o m i a l t i l = t i ea 1 9 0 r i f h r n ，w 陌c hi sp r o v 甜t ob e a b i ec o6 n dt h em i n i m u mm l m b e ro f r 鹎u i r e da d m s f o ra g i v e n q u e s t s 。t b a s e do n ! 璺塑兰墼茎叁兰堡蔓! 堕塑：! ：笙茎 t h ek n o w n w a v e l e n g t ha s s i 髓m e ma l g o r i m m so n t 1 1 ed i r e c t e dn b c r t r e e s ，w ec o u l du s e t h eg w 甜ym i n i m 吼n u m b e ro f w a v e l e n g t h st oa c c o m m o d a t ea l lt h er e q u e s t sw h i l e s c i i l k e 印i n gm en u m b e ro fr e q u i r e da d m sm i n i m u m t h en u m b e ro fr e q u i r e d w a v e l e n g t h sc o u l dg e taf h r t h e rr c d u c t i o nw i mm ew a v e l e n 甜hc o n v e r t e r s 2 ) p r e v i o u sw o r km a i n l yc o n s i d 日e dm es c h e d _ l l 】i n gp r o b l e m sf o rt h ea 1 1 o p t i c a l n e t 、v o r k sw i t hi n d e p c n d e n tt m s m i t t e r sa n dr e c e i v e r so nn o d e s a c c o r d i n gt ot h e p u b l i s h e dm a l l u f a c t u r i n gt c c m q u e so fm eo p t i c a ld e v i c e s ， w ec o n s t r u c t e da j l a d 跏r d pm u l t i p l e x e r m o d e lw i t h t u n a b l 。w o r k j n gw a v e l e n g c h ( “心m ) ，a n dp r o p o s e d aj o b - s c h e d u l i n gp m b i e mf o rt h ea l l - o p t i c a ln e f w o r k sw i t l ls u c ht u n a b l ea d m s o n n o d e s ( t h e s 谯d m p f o b l e m ) f o rm es t a d m p r o b l e m o na n a l l o p t i c a l u n i - d i r e c t i o n a ll i n en e t w o r k ，w ep m p o s ea p o l y n o m i a l t i m er o u t m ga 1 1 dw a v e l e n g m a s s i g n m e n ta l g o r i t 胁，w h i c hc o u l dm a k et h e t o t a l m a l ( e s p a na n dm en u m b e ro f r e q u i r e dw a v e i e n 舀h sm ；n i m u ms i m u l t a n e o u s l y b y 印p l y i n g1 h ea b o v ea l g o r i t h mo n m e a 1 1 一o p “c a lb i - d i r e c t i o n a ll i n en e t w o r k ，at r i v i a l2 - a p p r o x i m a t i o ns 0 1 u t i o nc o u l db e g o t f o rt h es t a d mp m b l 锄o n t h ed i r e c t e d 助e rt r c e ，w ep o p o s ea na p p r o x i m a t i o n a l g o r i 锄n b a s e do nt h e s p e c i a l c a s e so f 出e 嘲fn e 柳k a 芏1 d a n a 】y z e t h e 印p r o x i m a t i o nr a t j o w ef i r s lf j n da i 】o p t j m a 】a 培o r i t h mo fas p e c i a lc a s e ，a 1 1 dt b e n a p p l yi t t o 幽【es t a d m p r o b l 踊o n 出e 越l o p l i c a ld l r e c t e d 聂n gn e t w o 呔st og e t 孙 a p p r o x i m a t i o na l g o r i t h mw i t h c o n s t a l l ta p p m x i m a t i o nr a t i o ac o n s t a n t a p p r o x i m a t i o n a l g o r i t h r nf o rt l l eg e n e r a ln e t w o r k sc o u l d a l s ob ef o u n di nas i m i l a rw a y 3 ) a h m e dh e l m y e ta 1 f i r s ti n t r d d u c e dt h e m a l lw o r l dp h e n o m e n o nj n t dt h e m u l t i _ h o pw i r e l e s sn e t w o r k s ，a 1 1 ds t u d i e di t si l u e n c e st ot h et r a n s m i s s i o ne f f i c i e n c y o ft h ew i f e l e s sn 吼w o r k s b 眦t h e ym a i n l yf 。c u s e do nt h e 1 0 9 i c a lt o p o l o g yo ft h e w j r e i e s sn e t w o r k s w ei m p l 锄锄t h es m a j jw d 撼p h 锄o m 锄o no nt h op h y s j c a i t o p 0 1 0 9 yo f t h ew i r e l e s sn e t w o r k s ，a n dc o n d u c ts o m ee x p e i i m e n t st os h o wt h a ti tc a l l 芦b a t i yi m p r o v e t h et r a n s m i s s i o ne 愿c i e n o y 。f 也ew i r e l e s sn 武w o r k s 4 ) i nm o s to fm ec u r r e n tt r a n s m i s s i o np r o t d c o l s ，s o m ep a c k e tw i m c o n t r o i l i i l g i n f o 帆a t l o ns h o u l db es e n to u tb e 内沁出ed a t a p 孔k e t 托i n g 铂n s m i 键e d w e p o p o s ea n o w a i t j o bs c h e d u l i n gp r o b l 锄m o d e lo nt h e s i n g l e h o pm u l t i p l e c h a n n e l c o m m u n i c a “o nn e t w o f k sw i 1o n e c o n h o l l i n gc h a n n e la n dm u l t i p l ed a t ac h a 彻e l s ，g e t t h ea p p r o x i m a t i o nr a t i d sd f “s t s c h 甜u l i n ga n dl o n g e s tp r o c e s s i n gt i m ef i r s tf d rt h e o m l i n er e q u e s ts e t ，w h i c ha r e ( 5 2 1 2 m ) a n d ( 2 + 1 2 ( m + 1 ) ) r e s p e c t i v e l y a n dg e tt h e c o m p e t i “v er a t i oo fl i s ts c h e d u l i n gf o rt 1 1 eo n i l n er e q u e s t5 e t ，( 7 2 1 2 m ) ，w h e r e ( m + 1 ) i st h en u m b e ro f c h a 蚰e l s 芷y w 口确? a l 卜o p t 沁a ln e n o r k s ，w i f e l e s sn e 时。_ k s m u ；t i e - c b a 酾e ic o m m u n i c 台t i 雠 1 1 e “v o r k s ，j o b s c h e d u l i n gp r o b i e m ， c o m b i n a t o r i a l 叩t i m i z j n ga l g o r i t h i n ， a p p r o x i m a t i o nr a t i o ，s m a l lw o r l d 中周科学披术人学计算茸【系博i ：论文 第一章绪论 本章摘要：本章给出了下一代通信网络上的基本研究问题、研究 现状、研究手段。 1 1 研究背景与发展现状 计算机网络技术的发明，大大促进了人类的资源共享和信息交流。通过计算 机网络，一个用户可以直接访问远在1 0 0 0 公旱外的数据。而在计算机网络发明 之前，这是不可想象的。利用电子邮件、网上聊天系统。分散在世界各地的人员， 甚至可以进行类似于“面对面”的讨论。这些系统可以大大降低工作成本，并且 大大提高了工作效率。 发展到今天的计算机网络主要基于电信号进行数据的传播，它的传输带宽通 常不超过1 0 0 m b s 。随着一些对带宽要求较高的应用被实现，如，视频会议，科 学数据的可视化，实时医学成像，等。目前的电信号网络越来越无法满足用户的 需要。全光传输技术可以提供高达1 0 0 0 m b s ( = 1 g b s ) 的带宽，并且通过波分 复用技术( w a v e l e n g t hd i v i s i o nm u l t - p l e x i n g w d m ) 还可以上千倍地提高全光传 输的带宽 1 1 。而对于某些特殊的情况下，电信号通信网络也有点力不从心，如， 移动中的计算机组网，战场上士兵之间需要建立的网络，等。无线通信网络以其 不需要事先的硬件铺设、使用灵活方便、可以在移动过程中保持通信等特点，而 被大量应用于公司、公共场所、家庭环境、以及战场上的通信网络。全光传输网 络和无线通信网络是下一代通信网络的两个主要发展方向。 1 1 1 常用硬件设备及相关问题 全光传输网络是通过放置在网络节点上的光学终端设备来实现：一个通信请 求在传输过程中不依靠光电，电光转换，始终使用光信号进行传输。这样可以大 大提高传输效率。常用的光学终端设备包括光信号加载器和下载器( 或称为发送 器和接收器) 、光信号波长转换器、光信号分流器等，下面主要介绍一下与本文 第一章绪论 相关的光学终端设备，它们的数学模型，以及相关的优化问题等。 1 。1 1 ，l 光信号鸯讧载器和下载器 全光传输网络中，把电信号的通信数据转换为光信号并加载到光纤中，以及 把光线中的光信号下载下来并转换为电信号的通信数掘的操作分别由光信号加 载器和下载器完成。一个加载器( 或下载器) 在某一个时刻只能够操作特定波长 的光信号，这个波长称为该加载器( 或下载器) 的工作波长。w d m 全光传输网 络的m a c 二屯 ， i 二、。 ， 、五 厂 、 、 ， 、 ，p 2 = 勺l j 2 ，肌勺，s p ，它们可以合并为链路 弘 勺o ，s i 、勺1 ，j 2 、，、勺 l ，踣， ，且称后为开的长度，记为l 丹l 。如果j o 哥t ， 则称丹为闭链；否则称为开链。如果链路a 中任两条有向路径不经过g 中的同 一条光纤，则称行为请求链。既是开链又是请求链的链路，称为请求开链；既 i 8 中露科学技术火学诗篓= 轨系懈t 论文 是闭链又是请求链的，称为请求闭链。 如图2 3 所示， 勺，6 ， 为开链， 勘，6 ， ， ， 为闭链。并且二者分别也是请求开链和请求闭链。 请求链肛 勺。，5 1 ，勺l 5 2 ， 和p 2 = 勺2 ，如 ，我们定义以下四种冲突 关系： 1 ) 若s l _ 。2 ，称p l 和j p 2 在s 1 处发生源冲突； 2 ) 若d l = 比，称p i 和p 2 在而处发生汇冲突； 3 ) 若d l = s 2 ，且p l 和p 2 经过了g 中一条边所对应的同一根物理光纤，则 称p l 和见在函处发生合并冲突； 4 ) 若d i 可2 ，且p - 和胁经过以矾为端点的某条边所对应的两条物理光纤， 穆它们在函处发生对称冲突。 图2 5 请求之间的冲突关系 在每个节点处放置一个可调a d m 的w d m 全光传输网络上互相冲突的两条 有向路径所对应的请求不能同时进行传输。如图2 5 所示，对请求集合r = v 1 ，、，3 ，也，v 4 ， 进行路由。因为节点v 2 处只有一个可调a d m ， 所以两个源冲突的有向路径 和( u ，v 4 不能同时通过这个可调a d m 进行 2 0 中露科学技术火学诗葬= 轨系懈t 论文 加载，汇冲突的请求也，。3 与 情况类似。而对于合并冲突的 和( v 4 ， ”3 ，出于它们无法同时使用一个波长进行传竣，所以节点札处的可调a d m 无 法同时对它们进行处理。因为与a d m 相同的原因，一个可调a d m 也无法同时 处理发生对称冲突的两个请求 和 也，) 。对于不冲突的两个有向路径 和 ，奄“，s p ) ，如果其中任意两个有 向路径对应的请求互不冲突，但弦不是请求链，则称乃中有向路径对应的请求 集合发生了链路冲突。 显然在对称全光树形网络上不存在链路冲突。 2 ，4 2 简化模型 上述的s t a d m 问题模型比较复杂，接下来本文给出一个简化的问题模型。 在常见的m a c 层( m e d i aa c c e s sc o n t m i ) 蝴络通信协议f j ，一个请求一旦 丌始传输。就不能中断：并通常将应用层的请求分割为多个定陡的数据包进行传 输。所以本文假设每一个请求，r 的传输时间为常数幻。 同时假设可调a d m 设备经过时间万可以将工作波长从一个波长转化到另一 个波长， 我们需要将有向路径集合p 分为尽可能少的子集，称为页面( p a g e s ) p l 、 p 2 、，、p 童，使得同一页面中任意两个请求之间郡没有 哇i 突，即可以同时在每个 节点上只有一个可调a d m 的w d m 全光传输网络上进行传输。传输完一个页面 ： 之后，根据下一页面中请求的需要调节部分可调a d m 的工作波长，然后传输 下页面中的请求。所以，总传输时间为： - 2 第二章光信号加载，下载复用器及相关问题 m 口克b 驴口，2 = ( f o + 占) b 出于f 。和占都是确定的，为了最小化总传输时间晰口七b 甲口h ，我们只需要最小 化页面数曰即可。在本文的其余部分，有关算法性能的讨论都是针对页面数b 的。 2 5 本章小结 本章给出了w d m 全光传输网络的数学模型；接着描述了加载下载复用器 的基本模型，包括固定a d m 设备和可调a d m 设备；最后分别给出了最小化 a d m 数问题和使用可调a d m 设备时的任务调度问题的数学模型及基本优化策 略。本章给出的定义、模型、结论，在下文中将不加说明的使用。 麓 中陶科学技术大学计算机系辩上论文 第三章全光树形网络上的 最小化固定加载下载复用器问题 ( m 睑d m ) 本章摘要：本章给出了w d m 全光传输树形网络上的骱蹦问题一个 多项式时问的m a d m 问题的最优算法。利用已有工作，我们可以在 保持使用最少的a d m 设备的前提下，使得所需要的波蚝数目大大降 低。出试验结果表明，我们的算法在具有大约5 0 0 个节点的小规模 局域树形网络e 具有非常好的性能。 3 1 问题的提出 由于最小化a d m 数问题是n p 完全的【3 4 】，所以通常研究的是近似算法的 设计与分析 3 4 3 7 。已有工作主要集中在全光环形网络上的最小化a d m 数问 题，本文利用已有的一些优化策略来研究全光树形网络上的情况。 本章讨论的是：w d m 全光传输树形网络上，如何使得给定的请求集合所需 要的a d m 数最少，即m a d m 问题。问题模型的描述如下： 给定无向树形网络仁( 联乃，目丁) ) ，以及r 上的一个请求集合r = _ | 存 在树r 上的从到的请求，其中h n 且吩坎乃 。对于树形网络l 一个 请求 l 有向路径9 ，v l p ，并且该有向路径可以和链路丹在节点 v l 处合并成为一个更长的请求链， 请求链丹的汇合并链路集为： p 及7 r ) = v ，户l 有向路径 ) 都是完备链路而对于请求链玑= ， 1 ，因为 尸日( 死) = 以及p r ( 弘) = 妒，故该请求链为不完备链路。 3 2 预备工作 接f 来，本文分析了，不【司的请求链对减少给定请求集合所需要的a d m 数目 的影响。 兄五a五 专 v 1屹 v 3 v 4v 5 囤囤囤圈囤 ( a ) 开链对a d m 数的需求 圆 圆_ 广囤l _ j 7 0 l _ j ( b ) 闭链对a d m 数的需求 图3 2 请求链对a d m 数的需求 一个工作波长为五的加载下载复用器( a d m ) 设备可以同时以波长为五的 光波发送一个请求和接收一个承载在波长为五的光信号。对于一条丌链乃= ， 第三章全光辩形瑚络七的屉小化固定加载，下载复用 i ；问题( m a d m ) v 2 | ， ) ，如果有向路径 ， 。对于闭链乃来说，只需要f 个a d m 设备就可以处理所有的有向路径了。如果有向路径 ，赋值n = ，乃) ，并尸= p 一 ) ，然后转至 第a 步；否则转至第b 步。 b ) 如果p r ( n ) ，那么从集合p r ( 乃) 中任意选取一个有向路径 ，赋值乃= ，丹) ，并p = p 一 ) ，然后转 至第b 步；否则转至第c 步。 c ) 赋值r d 把( 尸) = r d “把( p ) u 乃) ，并转至第2 步。 3 1去掉树r 的根节点，然后转至第2 步继续处理所有非平凡的子树。 钔若只剩下平凡予树，则转至第5 步i 否则重复第2 步和第3 步。 5 )输出当前所得到的链路集合r d “f ( p ) 。 ，2 r 中嗣科学技术犬学汁算桃系博士论文 e n d 根掘前面的源合并链路集和汇合并链路集的定义可知，第5 步输出的 尺。“f 8 ( 尸) 中的每一个请求链上的所有有向路径之问都没有使用树r 上同一根光 纤，所以它们可以使用同一个波长进行传输。在下面的讨论中，我们假设在同一 个请求链中的所有有向路径都使用同一个波长进行传输，所以我们只需要研究 r o “f p ( p ) 中开链数目的优化情况。在证明算法p f a 所得到的结果是w d m 全光 传输树形网络上m a d m 问题的最优解之前，我们首先给出一个引理： 引理3 3 ： 在上面的问题中，算法p f a 所得到的第一个请求链肛 勺l ，口2 ， ， 在p 的某个最优a d m 路由策略中。 证明： 图3 3 请求链丹i 和z 匕 给定有向路径集合p 的一个最优a d m 路由策略r d 妇( p ) 。由于在树形网 络上不存在请求闭链，所以舶“崛( | p ) 中的请求链都是请求丌链。假设在 r 。“镌( p ) 中，有向路径 并不与有向路径 合并成同一个请求链。 记在r d “鸠( p ) 中，有向路径 和 所在的请求链分别为 n = o ， ， ，) 和巩= ， ， ，一 。把请求链乃l 在节点2 处分割为两个请求链职= r ， 和玩= ( 口2 ，“” ，) ，以及把 请求链啦在节点口2 处分割为两个请求链玩= o ， ) 和 巩= ，) 。然后分别将请求链玩和矾合并为链路奶以及将请求链 2 0 第三章全光树形嘲络上的最小化固定加载，下栽复用器问题( m a d m ) 吼和吼合并为链路玑。取另一个a d m 路由策略 j r d “f e 2 ( 尸) = ( 肋“招( p ) 一溉，巩) ) u 珥，巩) ，并设助“f e 。( p ) 和r 。“f 口- ( p ) 中的请 求开链数分别为m 删1 和 m m 2 。如图3 3 所示根据4 个请求链玑、吼、7 r 5 、 和丹6 的情况可知： 1 ) 若玑声、巩庐、玑声、且巩，则有m 1 m m 2 ； 2 ) 若请求链7 b ，7 h ，7 h ，和7 h 中只有一个为空集、其他不为空集，则有 “】= _ z f ”2 ； 3 ) 若请求链玑，7 k 巩，和7 h 中只有两个为空集、其他不为空集，则不可 能两个空集都是同一个请求链玩或者z b 生成的，不妨设7 b 和7 h 是空 集，其他不是空集，所以有 m 卅2 寻批州l - l 甜m 聊1 ； 4 1 其他情况不可能。 所以我们可以得到，r 。“吻( p ) 中的请求丌链数不多于r d “f e ，( j d ) 中的请求了_ | ： 链数。又因为尺d “f 日( p ) 是最优a d m 路由策略，所以r d “呜( p ) 中的请求开链数 等于r o “旭( p ) 中的请求开链数。即r d “f ：( p ) 也是有向路径集合p 的一个最优 a d m 路由策略。 类似于上i f l 的讨论可以得到，存在p 的一个最优a d m 路山策略r d f g ( j p ) ， 使得请求丌链什= ， ， ) 肋“地( p ) 。由于请求开链 丹： ， ， 是算法p f a 得到的第一个请求链，所以它 是一个完备链路。 口 利用引理3 _ 3 的结论，我们进一步证明算法p f a 得到的a d m 路出策略是最 优的。 定理3 1 ： 算法p f a 输出的请求链路集合月d “把( p ) 是有向路径集合p 的一个最优a d m 路由策略。 证明： 中闻科学技术人学计算机系博_ 上论史 设算法p f a 所得到的第个请求链为肛 勺i ，口2 ，勺2 ，d 3 ，嘲f c ，4 f 。 由引理33 可得，请求链乃在有向路径集合p 的某个最优a d m 路由策略 r o “f e ，( 尸) 中。 从有向路径集合p 中去掉请求链开中的所有有向路径，得到一个新的有向 路径集合p l 。因为行是r o “织( p ) 中的一个完备链路，所以p 1 的最优a d m 路由 策略加上完备链路弦就是有向路径集合p 的一个最优a d m 路d j 策略。同样的 结论对p f a 算法在有向路径集合j p - 上得到的第一个请求丌链也成立。循环地进 行相同操作，知道所得到的有向路径集合为空集。 由上可得，尺。“e ( p ) 是有向路径集合p 的一个最优a d m 路由策略。