（运筹学与控制论专业论文）环型网络的信息通过量问题.pdf

环形网络路由问题的近似算法研究 摘要 同步光纤网络( s o n e t ) 在当今网络通讯技术中被普遍应用。分布在网络 各节点处的设备控制网络的容量，且s o n e t 网络的费用随着其容量的增加而增 加。针对环型s o n e t 上的一组信息发送请求，设计一个路由算法来确定各条信 息被传送的方向，使得传送所有信息所必需的带宽达到最小，该问题称为路由 负载平衡问题。而如果网络带宽本身是有限制的，则要求我们设计路由选择算 法来确定各条信息的传送策略一包括顺时针传送、逆时针传送和放弃传送，使 得在不超过带宽限制的前提下，被传送的信息总量达到最大，该问题称为信息 通过量问题。对于信息通过量问题的研究具有很好的理论意义和应用前景。 本文主要内容如下： 对于环型s o n e t 的路由负载平衡问题现有算法中的“线性规划舍入”技巧 进行总结，分析一般信息权重情况下的近似算法的设计和在单位信息权重 情况下的多项式时间精确算法的设计。 对于环型s o n e t 信息通过量问题进行深入研究，论证其n p 困难性、并通 过改进“线性规划舍入”方法给出该问题的多项式时间近似算法和近似度 估计。 关键词：环形s o n e t ；n p 困难；近似算法；路由负载平衡；信息通过量 a p p r o x i m a t i o na l g o r i t h m sf o rc a l lr o u t i n g p r o b l e m si ns o n e t r i n g a b s t r a c t s y n c h r o n o u so p t i c a ln e t w o r k ( s o n e t ) h a sb e e na d o p t e d 嬲a l li m p o r t a n t t r a n s p o r tt e c h n o l o g yi nn e t w o r kc o m m u n i c a t i o n t h en o d e so nas o n e ts e n d a n dr e c e i v em e s s a g e sv i aa d d d r o pm u l t i p l e x e r s ( a d m s ) t h a td e t e r m i n et h ea c t u a lb a n d w i d t ha v a i l a b l eo nt h en e t w o r k a n dt h ec o s to fas o n e ti n c r e a s e s w i t hi t sb a n d w i d t h g i v e nas e to fc a l l si nt h es o n e t r i n g t h ea i mo ft h el o a d b a l a n c e dr o u t i n gp r o b l e mi st od e v i s ear o u t i n gs c h e m e ，s ot h a tt h eb a n d w i d t h r e q u i r e dt ot r a n s m i ta l lt h ec a l l si sm i n i m i z e d 、珊i l ei ng e n e r a l t h ea v a i l a b l e b a n d w i d t ho f f e r e di sl i m i t e d t h ep r o b l e md e r i v e df r o mt h i sb a c k g r o u n di sc a l l e d c a l lc o n t r o la n dr o u t i n gp r o b l e m ，t h ea i mo fw h i c hi st of i n d ，f o rag i v e ns e to f c a l l s ，as u b s e to fc a l l sa n dt h e i rr o u t i n gp a t h ss u c ht h a tt h et o t a ld e m a n do f a c c e p t e dc a l l si sm a x i m u ms u b j e c tt ot h eb a n d w i d t hc a p a c i t yr e s t r i c t i o n t h e s t u d yo nt h ec a l lc o n t r o la n dr o u t i n gp r o b l e mi sm e a n i n g f u la n dm a yf i n dm a n y a p p l i c a t i o n si np r a c t i c e t h em a i nr e s u l t so ft h et h e s i sa x ea sf o l l o w s ： f o rt h el o a d - b a l a n c e dr o u t i n gp r o b l e mi ns o n e t r i n g s ，t h et e c h n i q u eo fl p r o u n d i n gi ss u m m a r i z e d ；t h ea p p r o x i m a t i o na l g o r i t h mi ng e n e r a lw e i g h t e d c a s et h ep o l y n o m i a lt i m ee x a c ta l g o r i t h mi nu n i tw e i g h t e dc a s ea r eb o t h 出s c u s s e d f o rt h ec a l lc o n t r o la n dr o u t i n gp r o b l e mi ns o n e t r i n g s t h en p h a r d n e s s r e s u l ta r ep r o v e d ；b yw a yo fa ne l e g a n ta p p l i c a t i o no ft h et e c h n i q u eo fl p r o u n d i n g ，8 2 1a p p r o x i m a t i o na l g o r i t h mw i t hag o o dp e r f o r m a n c er a t i oi s g i v e n k e y w o r d s ：s o n e tr i n g ；n p - h a r d n e s s ；a p p r o x i m a t i o na l g o r i t h m ； l o a d - b a l a n c e dr o u t i n g ；r o u t i n gt h r o u g h p u t 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特 i i j j n 以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：琦澜玛签字日期：如矿年y 月刁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：路布寸磋 导师签字： 签字日期：溯g 年 扫1 e t签字日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 乒 1 中盯 吁 渺 第l 章综述 1 1s o n e t 路由问题的背景 在世界范围内，伴随着潜在带宽的增长和包括视频在内的网络多媒体通讯 技术的推广，通讯设备公司花费了数百亿美元用光纤取代传统的铜制导线。对 于光纤网络通讯技术，目前美国应用最多居于统治地位的技术是“同步光纤网 络”( 英文缩写s o n e t ) ，该技术最终成为美国的网络通讯技术标准。在同步光 纤网络中，分布在各处的通讯节点被一个具有固定结构的光纤网络所连接，每 个节点都通过添加或减少被称为多路( 复用) 器( a d m s ) 的设备来发送、接收 和转播信息f 1 ，2 1 。 在现实生活中，比较常见的网络拓扑结构可以分为总线型网络、树型网络、 环型网络和星型网络等。与其他网络结构相比，环型s o n e t 网络具有自己的 优点。环型网络的节点对称结构确保了每个节点都能以相似的方式装备并且具 备同样的功能。由于是环型结构，即使网络中有一个连接( 即环上连接两个相 邻节点的一条边，下文简称为边) 或者一个节点出现故障，仍然能够保证其余部 分的信息通讯畅通。 在实际中，由于硬件设备成本的限制，光纤网络中可供利用传送信息的带 宽通常是有限的，这就是所谓的光纤网络的容量。不同s o n e t 网络的容量彼此 之间往往是不同的，但一般情况下，同一个网络内部的每个边的容量都是相同 的。特别要说明的是，光纤网络的花费是随着其容量的增加而增加的，这并不 是因为光纤本身的原因，而是由于多路器( a d m s ) 对于带宽的限制。当然，造 成的结果是显然的：对于容量为c 的网络，任何一个边都不允许携带超过容量 限制c 的信息。 对于某些环型网络，除非有错误发生，所有的信息都会选择同一个方向传 送。此时容量实际上是用来限制所有点对点信息所产生信息通过量的总和，这 类网络又被称为无向环型s o n e t 。与此相对应的是，在一个有向环型s o n e t 中，每一个信息都需要通过算法选择路径，也就是选择顺时针传送或者是逆时 针传送。由于可以选择传送方向，有向环型s o n e t 在带宽利用方面效率更高。 例如，如果所有信息包含的信息量都是统一的，那么同样容量限制下的有向环 环形网络上的信息通过量问题 型网络上的信息通过量是无向环型网络的四倍。 对于同步光纤网络，最常见、同时也是解决得比较彻底的最优化问题是路 由负载平衡问题( l o a d b a l a n c e dr o u t i n gp r o b l e m ) ，该问题的目标是针对网络 上的一组待发信息，设计一个路由算法使得传送所有信息所必需的带宽达到最 小。然而，在带宽有限情况下，即使将必需的带宽最小化，仍然可能超过实际中 可供利用的带宽，从而导致最终只有一部分信息请求可以不被延迟地得到满足。 因此，开发在给定数量的带宽限制下能够传送尽可能多的信息的算法技术有重 要意义。带有上述背景的最优化问题被称作信息控制和路由问题( c a l lc o n t r o l a n dr o u t i n gp r o b l e m l ，也被称为信息通过量问题。 路由负载平衡问题和信息通过量问题都与图论中边不交路问题以及整数网 络流问题密切相关f 3 4 ，5 1 。在许多网络结构下，例如环型结构等，路由负载平 衡和信息通过量问题都是n p 困难问题，即不存在多项式时间算法来求得最优 解，除非p = n p 。本文研究的目的是论证在环型s o n e t 网络结构下，信息通过 量问题是n p 困难的，在此基础上给出多项式时间的近似算法，并分析算法的近 似度。 1 2 研究现状 本节主要针对环型s o n e t 的路由负载平衡问题和信息控制问题等相关问 题的研究现状给予综述。对于文中所涉及到的有关图论、计算复杂性和近似 算法的概念和理论，例如n p 困难性、多项式时间算法、近似度等请参见文献 f 6 ，7 ，8 】，这里不再赘述 以下我们针对几个信息传输方面的典型问题分别进行论述。 问题a ：环型s o n e t 路由负载平衡问题 给定有n 个节点的有向环型s o n e t ，假设有m 个信息，它们对应的序列对 分别为( s 1 ，t l ；d 1 ) ：( 8 2 ，t 2 ；d 2 ) ，( s 仇，t r n ；d m ) ，其中s t 和t i 都是环上的节点，分别 表示第i 个信息的起点和终点，d , n 表示第i 个信息信息量，即该信息的权重。 问题之一是：寻求各信息的传送路径，顺时针方向或逆时针方向，使得环上 各边上最大的双向负载达到最小。该问题也称为双向负载平衡问题。具体地，对 于任意i = 1 ，2 ，m ，用五= 1 表示将第i 个信息沿顺时针方向传送；用戤= 0 表 示将第i 个信息沿逆时针方向传送。则问题是寻找一组z l ，x m o ，l 使负 2 环形网络上的信息通过量问题 载l = m l z + 坛) 达到最小，其中 k 【s l ，岛一1 ) ，反= 1 ) ； 七【t i ，魂一1 ) ，z i = o ， 分别为环上顺时针边k + 1 ) 和逆时针边( 忌+ 1 ，纠上关于解z 的负载，而三称为 网络的双向负载。这里符号k ，) 表示半开半闭区f 日7 i ，i + 1 ，j 一1 。 问题之二是：寻求各信息的传送路径，顺时针方向或逆时针方向，使得环上 各边上最大的单向负载达到最小。该问题也称为单向负载平衡问题。具体地，对 于任意i = l ，2 ，仇，用z i = 1 表示将第i 个信息沿顺时针方向传送；用黾= 0 表 示将第i 个信息沿逆时针方向传送。则问题是寻找一组z 1 ，x m o ，1 使负 载l = m a x m a x k l + ，m a x k l i ) 达到最小。这里，l 称为网络的单向负载。 在一般情况下，环型s o n e t 的路由负载平衡问题( 双向负载与单向负载) 都是n p 一困难的。针对环型s o n e t 双向负载平衡问题，最早c o s a r e s 和s a n i e e 9 1 给出了问题的n p 困难性证明；他们还给出了该问题的一个多项式时间2 近似 算法；r a g h a v a n 和u p f a l i o 贝u 给出了该问题的更好有效近似算法。之后，对于 环型s o n e t 双向负载平衡问题的研究更加深入。s c h r i j v e r ，s e y m o u r 和w i n k l e r f l l l 利用线性规划“舍入技术”和弧图中割的性质，给出了一个1 + 半近似度的 算法，其中d 为待传送信息的最大权重：在他们研究结果基础上，k h a n n a 【1 2 】给 出了该问题的一个p t a s ，从而在近似算法理论上彻底解决了该问题。 对于环型s o n e t 单向负载平衡问题，w h 和y ：a n g 【1 3 证明了其n p 困难性， 并给出了一股隋况下了该问题的一个p t a s ，他们在研究中仍然沿用了s c h r i j v e t ， s e y m o u r $ 1 w i n k l e r 在文献1 1 】中使用的一个重要技巧，即精巧的线性规划舍入 技术。w 缸和y a n g 1 3 1 的结果也是环型s o n e t 单向负载平衡问题上最好的理论 结果。 对于所有信息权重均为1 的环型s o n e t 单向负载平衡问题，w i l f o n g 和 w i n k l e r 1 4 利用更为精巧的线性舍入技术和理论分析，给出了一个多项式时 间的精确最优解算法。这一结果说明在这种特殊情况下的单向平衡负载问题 是p 问题。由此人们很自然地提出问题：信息权重均为1 的环型s o n e t 双向负载 平衡问题是否也存在多项式时间精确算法? 但迄今为止该问题还未得到解决。 问题b ：环型s o n e t 信息控制问题 给定有n 个节点的有向环形s o n e t ，其环容量有限，设为c ；假设有m 个信 g ( s 1 ，t 1 ；d 1 ) ，( s 2 ，t 2 ；d 2 ) ，( s m ，t r n ；d m ) ；另外，在给出信息请求的同时还给定 3 画应 ，t r t 1 l ，! l ，仁 = = + 七一七 l 环形网络上的信息通过量问题 了它的指定路由( 信息在传送时必须按指定方向) 。考察的问题是在满足容量限 制的前提下，确定出要被传送的信息子集，使得被传送的总信息量达到最大。具 体地，对于任意i = l ，2 ，m ，用鼢= 1 表示第i 个信息将被传送；用翰= 0 表示 第i 个信息将被拒绝传送，问题是寻找一组z 1 ，z m o ，1 ) 满足约束条件 l 毒c 并且l - ；c 并使信息传送量! ，( i t 盈达到最大，其中 l 毒= 应：k s i ，如一1 ) ，戤= 1 ，且该信息指定顺时针传送) ； 钉= i 【d i ：k t i ，s i 1 ) ，以= l ，且该信息指定逆时针传送 a d a m y 等学者 1 5 】研究了环型s o n e t 中单位权重信息情况下的信息控制问题， 给出了一个多项式时间精确算法；b e c c h e t t i 1 6 等学者给出了该问题在一般信 息权重下的常数近似度的多项式时间算法：而n o m i k o s 、p a g o u r t z i s 和z a c h o s 1 7 则进一步改进了他们的结果，给出了的2 3 - 近似算法。 上面谈到的研究成果主要针对环型网络，但是在现实生活中其他一些网络 结构同样常见，例如直线形网络、树形网络、甚至更为宽泛的网状网络结构。这 些网络结构下信息路由问题同样也受到了学者的关注，在算法的理论和应用方 面均取得了许多好的结果，在此不再赘述。另外。还有学者研究节点赋权的环 型网络中的路由负载平衡问题1 8 。s o n e t 网络上的信息传送问题实际上就是 弧图上的多商品流问题，因而一般的多商品流问题是s o n e t 网络上的信息传送 问题的推广；另外，还有一类问题与环型s o n e t 网络上的信息传送问题密切相 关，就是环上的超边嵌入问题。 问题c ：网络上的多商品流问题 给定具有边容量限制的网络t = ( ve ，u ) ，假定每条边上的容量限制t 。都是 整数，7 被称作供应图；另在相同顶点集合y 上构造一个多重图胃= ( ved ，叫) 。 它的每条边，f 都代表一个商品发送请求；整数d ，表示商品量；实数训，表示 运输该商品可得到的利润：日被称作需求图。一组商品发送请求对应需求图的 边集合f 。如果边子集s f 满足：其每个边，s 的两顶点之间存在一条供应 图中的路p f ，使得供应图中各边被这些路使用的次数不超过相应的边容量限 制，则称该边子集是一个可行的商品运输方案、即可行解。在给定的供应图和 需求图上定义的多商品流问题就是要寻找一个可行的商品运输方案s ，使总利 润w ( s ) = f e bw s 达- n 最大。 4 环形网络上的信息通过量问题 以下为描述方便，我们仅对供应图为树型网络这一情形，建立相应的多商 品流问题的整数规划模型。令。，= 1 表示商品发送请求，被发送，z ，= o 表示商 品发送请求，未被发送，则有如下整数规划： m a x f f t u f z f 5 t ，：c 凡矾( ，) d z ， v e e z ，| 【o ，1 ) v ，f 对于树型结构的多商品流问题，在商品量的权重都为l 情形下，g a r g 、v a z i r a n i 和y a n n a k a k i s 【1 9 】证明了其n p - 困难性，并给出了一个多项式时间的2 - 近似 算法。在他们研究的基础上，c h e k u r i 、m y d l a r z 和s h e p h e r d 2 0 1 利用线性规划松 弛给出了任意利润和商品量权重情况下的算法近似度估计。 问题d ：环上的最小拥塞超边嵌入问题 给定超图h = ( ve h ；d ) ，其中v = u 1 ，忱，v n 是g 的n 个顶点的集合， 每个顶点均表示一个网络用户：e h = 九1 ，h 2 ， n ) 是g 的m 条超边的集合， 每条超边都是由两个或者更多节点构成的顶点子集，表示该顶点子集中的顶 点之间需要共享信息，或互相传送信息，因此每个超边也称为一个信息传送要 求；d 是定义在超边上的权重函数，表示各超边上所需传送的信息量的大小。通 过图g 的顶点集合y 构造一个环型网络c ，其边集合为 e c = ( u 1 ，忱) ，( v 2 ，v 3 ) ，( v n i ，u n ) ，( ，t ，1 ) ) 对任意的1 f m ，第i 个信息传送要求的连接路径只c 必须是c 的包含 第i 个超边中所有顶点的一条路。环上的最小拥塞超边嵌入问题就是对每个超 边厄( 1 i m ) ，寻找连接路径只，使得环上的最大拥塞m 瓯ce d i ：e 只，达到最小。 对于环型网络上的最小拥塞超边嵌入问题，g a n l e y 和c o h o o n 【2 1 论证其 n p 困难性，并且首先给出了一个3 - 近似算法；l e e 和h o 2 2 贝j j 在他们研究的基 础上提出了两个新的2 近似算法，其中一个算法是基于线性规划松弛的算法， 而另一个则是启发式算法：d e n g 和“2 3 】针对超边权重为1 的情况给出了p t a s ， 从而在算法理论上彻底解决了该问题。 到目前为止，对于信息控制和路由问题( 即信息通过量问题) 的研究结果 还很少，而在实际应用中，带宽成为通讯瓶颈的情况又是很常见的，这就激发 5 环形网络上的信息通过量问题 了我们研究信息通过量问题问题的浓厚兴趣。当s o n e t 为线型网络时，利用线 图的性质和整数多面体理论可以证明相应的信息通过量问题是多项式时间可解 的。然而，环型网络的信息通过量问题却是n p 一困难的，本文我们将集中研究这 一问题的算法。相对于被广泛研究的路由负载平衡问题，信息通过量问题的主 要困难就是在带宽限制的条件下，不仅要确定信息的发送方向，还要确定信息 的取舍。 本文在总结现有相关研究成果基础上，主要研究环型s o n e t 信息通过量问 题的计算复杂性和近似算法的设计等。本文结构如下： 在第二章，总结环型s o n e t 负载平衡问题的现有研究方法，特别是基 于“线性规划舍入”技巧的近似算法的设计； 在第三章，首先证明环型s o n e t 信息通过量问题的n p 一困难性，其次，利 用“线性规划舍入”技巧的深入应用，给出了近似度为1 一嘉，_ 的多项式 时间近似算法( 其中，k 2 是常数，且任何信息权重都不超过1 k 倍的环 容量) 。 6 第2 章环型s o n e t 路由负载平衡问题的研究方法及其 复杂性 本章主要考虑对环型s o n e t 单向负载平衡问题的近似算法，特别地，对于 算法中反复用到的l p 舍入技巧进行总结。这一技巧也是我们在第三章中解决信 息控制和路由问题的主要技巧。 2 1 问题的描述 设g 是一个由两条拥有同样的n 个节点的方向相反的环组成的网络。假设 环型网络的节点被从1 到n 沿某个方向编号，例如沿着顺势针方向由小到大编号。 所有涉及节点的运算均在模n 下进行。g 对应的边集合是 ( 1 i + 1 ) ，( i + 1 ，i ) ：l = 0 ，1 ，n 一1 。在这若干点组成的环形网络中传递任意一条信息，选择顺时针 传递和逆时针传递将会占用不同的信道。给定一组信息，其中某条信息请求对 应一条从某个发送节点到某个目标节点的路径。我们的目标是：通过路由选择 算法确定每一条信息请求的传送路由一沿起点到终点顺时针传送、或逆时针传 送，从而使最终被传送的信息所对应的总负载最小。该问题称为环型s o n e t 的 路由负载平衡问题( 简记为l b r o u t i n g 问题) 。 以下给出问题具体的描述。对于有n 个节点的有向环形s o n e t ，假设 有m 个信息，它们对应的节点序列对分别为( 5 1 ，t t ) ，( 5 m ，k ) ，( 其中起点s i ， 终点t i 都是环上的节点) 。它们对应的权重分别为d l ，如。另外记权重最大的 发送请求d r r 脚为d 。用x t 表示将第i 个信息沿着顺时针方向传送出去的部分，因 此有0 毛盔。那么也一致就表示将第i 个信息逆时针传送出去的部分。 环型s o n e t 的路由负载平衡问题是寻找整数解z 1 ， o ，画) 使负 载三最小，其中 l = m a x ( m a x k4 女，m a x kb k ) ， a k = e k 【s i , $ 1 - 1 lx i ，鼠= e i ：k e c “，以一l 】( 矾一戤) ， 即a 南为通过顺时针方向的边k k + 1 的信息负载，而鼠为通过逆时针方向的 边七+ 1 _ 七的信息负载；所有边负载中最大的一个记作网络负载l 。 环形网络上的信息通过量问题 如果一个路径选择，也称为路由负载平衡问题的一个解，满足每个信息整 体都沿着顺时针或者整体沿着逆时针方向传送，即满足盈 o ，盔) ，( 珑) ，那么 就称这个解是整数解；如果一个解中的信息既有沿着顺时针方向传送的部分又 有沿着逆时针传送的部分则称该解为小数解，此时孔 0 ，d i 】；如果一个小数解 还满足在两个方向上传送的信息总量( 即x i 和( 盔一而) ) 都是整数，则称该解 为整和解。 为给出路由负载平衡问题的计算复杂性，我们给出该问题的判定形式。路 由负载平衡问题的判断型式就是再给定一个目标值t ，问是否存在问题的一个 解该z 满足l t 。实际上，路由负载平衡问题相当于一个整数多重商品流问 题( i n t e g e rm u l t i c o m m o d i 姆- f l o wp r o b l e m l ，这类问题都是n p 困难的，只不过路 由负载平衡问题是其中的一个特殊情况。 定理2 1 1 环型s o n e t 的路由负载平衡问题是一个n p 困难问题。 路由负载平衡问题一个简单的递归( r e d u c t i o n ) 就是划分( p a r t i t i o n ) 问 题。由于划分问题是一个已知的n p 困难问题，因此通过对划分问题的多项式时 间构造，即满足路由负载平衡问题的判断实例为是实例，当且仅当原划分问题 实例为是实例，就能够证明路由负载平衡问题的n p 困难性。证明过程略。 对于一个n p 困难问题，既然不存在多项式时间内的最优解( 除非p = p ) ，一个自然的想法就是寻找一个近似算法给出满意解，从而解决实际问 题。 路由负载平衡问题的实际应用中，人们希望找到的好的近似算法具有如下 三个特征： 1 该算法必须是快的( 多项式时间内) ； 2 在绝大多数实际情况下，该算法提供的解不要超过最优解负载的5 ： 3 如果可能的话，该算法应该保证同时实现上述两个特征。 2 2 l + 警近似算法 本节我们描述由w a j l 和y 叽g 1 3 】给出的l b r o u t i n g 问题的1 + 孚近似算法。 算法步骤1 ：线性松弛： 将l & r o u t i n g 问题的限制条件 o ，应放宽到o 毛盔( i = 1 ，2 ，m ) ， 得至j l b r o u t i n g f 司题的线性规划松弛： 8 环形网络上的信息通过量问题 对于有n 个节点的有向环型s o n e t ，假设有m 个信息，问题是寻找小数 解x l ，z m 【0 ，d t 】，使负载l 最小，其中 l = m a x ( m 砜4 七，m a x 七鼠) a k = 蠢氓妒l 一，既= 诎一1 j ( 画一戤) 。 为了更清楚的描述问题，下面定义平行和交叉的概念： 两条信息如果满足 s ，如】【，岛】或者 勺，t j 】k 纠，则被称为平行，否 则被称为交叉。特别地，如果岛= 彤或者如= 岛，也称两个发送请求是平行的。 如果个解。满足：不存在两个平行的发送请求都是对应小数解，则称z 是平行 解。换句话说，在平行解中，任何两个对应小数解的信息发送请求都一定是交 叉的。 算法主要步骤如下： 1 求解信息控制和路由问题的线性规划松弛，得到一个最优实数解z ； 2 将解z 转化为平行解z ； 3 利用“l p 舍入技术”将平行解z 转化为整数解。 命题2 2 1 ：对于最优整和解z ：和它对应的负载q ，以及最优小数解z 和它 对应的负载l 备，满足：l ；。 算法步骤2 ：转化为平行解 引理2 2 2 ：任何解z 都能够在多项式时间内被转化平行解z ，并且同时满 足戤= z ：、以及每个边上的负载都不增加这两个条件。 证明假设第i 个信息和第7 个信息是平行的，并且它们对应的解都是小数 解。不失一般性，假设s i ，纠 ，t j 。若魏+ 巧 d i ，那么我们定义一个新的 解z 为 z ：= 五 弓= 翰+ 而一也 z ：= z 七 v 七i ，歹； 若甄+ z f 也，则定义一个新的解z 为 9 钆* 七 v 巧 上 ， 戤o i i i i i i ，甄，吩， 环形网络上的信息通过量问题 经过上述两种情况，两个平行的小数解中至少有一个不再是小数解，并且 每条边的负载都不变或者减少，同时保证了顺时针方向传送的信息总量保持不 变即而= z ：。重复上述转化步骤至多m 次，就可以在多项式时间内将给定 的解全部转换为平行解。证毕。 算法步骤3 ：将平行解转化为整数解 引理2 2 3 ：任何平行解x 都能够在多项式时间内转化为一个整数解y ，并且 对应的负载满足l ( v ) 一l ( x ) 孚( 其中d = m o = 4 1 0 x i d i ) ) 。 证假设z 是一个平行解。应用“l p 舍入技术”可以将每个对应小数解的信 息选择沿着唯一的方向发送出去，最终就能得到一个整数解。 由于交叉的信息不能共享同一个起点和终点，那么经过前面的步骤之后 对应小数解的信息个数就不会超过环的节点数n 。为了明晰起见，我们对于信 息重新编号，假定有g ( g 亿) 个信息对应小数解z ，记作 五。，五：，五。) ，按 照起点( 或者终点) 的顺时针方向上的顺序对这q 个对应小数解的信息重新编 号为 ，2 ，矗 ：同时对于每一个信息五，其终点和权重的顺序也依据重 新编号后的顺序重排，即j f ；f = ( s i ，t i ；也) ( 对于每个i = 1 ，2 ，口) 。而不包括 在 五。，五。，五。) 中的信息可以任意的分别编号为厶+ 1 ，f q + 2 ，厶。 按照如下方法从给定的平行解z 构造整数解可： 对于第i 个信息，若i 隹 0 ，能 够在多项式时间内找到一个( 1 + e ) 近似算法。该算法利用l p 舍入的技术将最优 小数解最终转化为一个次优整数解。 环形网络上的信息通过量问题 引理2 3 1 ：任何的平行解z 都可以在多项式时间内被转化为一个整数解剪同 时满足l ( 可) 一l ( z ) 孚。其中l ( z ) 代表解z 对应的负载，d = m a x d i l o x i 盔) 。 这个引理实际上就是上一节中的引理2 2 3 这里不再重复。 若用l ；，表示原问题的最优整数解。利用引理2 3 1 ( 即引理2 2 3 ) 证明过程 中的转化方式，就能得到一个不超过原问题线性规划松弛后的最优小数解对应 的负载睇的( 1 + 半) 倍的整数解。引理2 3 1 同时说明：如果一个路径选择z ( 满 足l x l 矗) 中所有的信息发送请求的权重都不超过竿，那么利用上一节 中提到的转化为0 ，1 整数解的方法在多项式时间内就能够得到一个负载不超 过( 14 - z ) l b 的整数解。 那么如何找到这个解呢? 不妨假设l 是经过短路算法得到的解对应的负 载。定义满足权重不超过学( 2 e 己玉) 的信息为”轻”的信息，否则为”重”的。可 以证明： 引理2 3 2 ：重的信息的数量一定少于譬。 证明方法是依据割的定义和经典的d o u b l e - c o u n t i n g 技术构造一个用于估计 的不等式( n 1 ) 警 n ( n 一1 ) 2 l ，又因为l 夤l 。，所以有h 挚。( 具体 证明略。) 引理2 3 3 ：对于原问题的任何最优整数解，沿长路( 即两条路径中经过节点 相对较多的路径) 被传送的”重”的信息的数量总是少于譬。 证明：利用反证法，假设对于某个最优整数解z ，存在至少孚个重的信息被 沿着长路传送。由于一个信息沿长路传送一定经过至少罟1 个边。所以由这些沿 长路传送的重的信息所产生的负载总和至少是詈 譬譬2 n l 。由于考虑 到方向相当于有2 n 个边( 有向边) ，利用抽屉原理，就至少有一个边的负载大于 等于( 百2 n l * ) = l ，这与z 是最优解产生矛盾。证毕。 有了引理2 3 3 之后，定义为数量少于譬的重的信息集组成的集族。由引 理2 3 2 和不等式( ：) ( 警) 七， n i 篝( 等) 掣1 2 矿e l 12-t-1 2e n 卟喜( 习i 【i ) 7 这意味着n 中的元素个数是一个关于1 2 的多项式。 1 2 环形网络上的信息通过量问题 对任意集合s i i ，令r s 表示所有满足如下条件的可行解型成的集 合：所有s 中的信息都沿长路发送。其余的重的信息都沿短路发送，由引 理2 3 3 ，m i n s e nr a i n 写r sl ( x ) l 各。 由于中的元素个数是一个关于佗的多项式，并且对于每个s i i ，f s 中的 一个满足负载为m i n 霉r sf ( z ) 的解是能够通过解线性规划模型在多项式时间内得 到的。因此最终找到一个集合s i i 和一个解z f s 满足如下条件： ( z ) = m s n ：i nr a 吣i nl ( z ) 注意到三( z ) 玉并且任何轻的信息其权重都不超过学。因此，一旦得 到z ，我们就能在多项式时间内将x 转化为整数解y 并且满足l ( 可) 0 ，在多 项式时间内能够找到一个整数解，满足其负载不超过最优整数解的( 1 + ) 倍。 2 4 单位权重情况下的精确算法 j w a n 和y a n g 1 3 给出了加权的单向路由负载平衡问题的p t a s 算法，那么权 重也= 1 的特殊情况是否能够得到更好的结果呢? 答案是肯定的。对于有向环 型s o n e t 上的信息权重都为l 的路由负载平衡问题，w i 蜘n g 和w i i 埘e r 1 4 利用 更精巧的技术给出了一个多项式时间内的最优解。 问题2 4 1 ：对于有n 个节点的有向环型s o n e t ，假设有m 个信息，它们对 应的序列对分别为( s 1 ，t 1 ) ，( s 仇，t m ) ，( 其中起点s i ，终点t i 都是环上的节点) 。 它们对应的权重d 1 ，d m 的值都为1 ，为了方便起见本节也会用d 1 ，d m 表示 这些信息。用x i = l 表示将信息也顺时针传送，用以= 0 表示将信息盔逆时针传 送。寻找解x l ，x m o ，1 ) 使满足负载l 最小，其中 = m a x ( m s , x ka k ，m a x kb k ) a k = m ：k kt i l 】a n d 戤= 1 ) i 鼠= m ：七5 一1 】a n d8 = o ) i 县1 a k 为通过顺时针方向的边是_ 七+ l 的信息负载，而鼠为通过逆时针方 向的边k + 1 叶七的信息负载；所有边负载中最大的一个记作网络负载l 。问题 的目标是确定0 1 解z = z l ，：z 期值使负载l 最小。 1 3 环形网络上的信息通过量问题 问题2 4 2 ：问题2 4 1 问题的线性规划松弛：寻找解2 ；1 ，x m 【o ，1 】使负 载口最小，其中 l + = m a x ( m a - x ka k ，m 魄b k ) ； a _ ：= e i ：k e 8 。，缸一l l 盈，b ：= e i ：k e 慨，以一l 】( 1 一甄) 。 现在问题就转化为一个多项式时间内可解的线性规划问题，且线性规划 松弛的最优解对应的负载刀满足l 6 刀l o p t ，其中l d 门是原问题的最优 解。因此有f 己6 p t l l o e t 。接下来的整体策略是寻找一个实数解z 满足两个 性质，并且对应的负载l 满足l 7 l o p t 。最后修改z 的值得到一个负载严格小 于+ l 的 o ，1 ) 整数解z 。这个x 实际上就是原问题的最优整数解。首先定义整 和的概念，如果2 ，z ：是一个整数，则称解x 是整和解。 引理2 4 1 ：给定问题2 4 1 的一个实例的线性规划松弛，能够在多项式时间 内得到一个满足负载l sl o p t 的整和解o 。 证明思路：考虑t , i = 0 ，而= l ，以= m 这m - t - 1 个条件，将它们 作为约束分别单独加入原问题中求解，共得n m + 1 个解，取其中负载最小的一 个即为所求，对应的负载记为l f 。 引理2 4 2 ：给定问题2 4 1 的一个实例的线性规划松弛，和一个对应负载 为l 的整和解x ，就能够在多项式时间内构造出一个平行解x 7 ，满足每个边上的 负载都不增加。 证明：假设两条平行的信息盔，d j ，对应的解0 x i l ，o z ， 1 一奶，则定义： ， 苁= l ，勺= 墨+ 巧一l 这样就得到一个对应负载为l l o p t 的整和解z 7 ，这个整和解还满足不存 在两条平