（信号与信息处理专业论文）基于线性优化实现的对于网络编码仿真工具的开发.pdf

摘要 摘要 随着网络编码领域研究的飞速发展，编码不再仅仅局限于信息源点。通 过将信息传递的中间节点引入编码范围，整个网络的吞吐量和鲁棒性可能得到大 幅度的提升。另一方面，编码本身需要消耗一定的处理时间，为了成功解码还 要在原有数据包上添加数据包头，因此网络编码在一定程度上也增加了整个网络 的负荷。为了克服以上弊端，设计出高效的网络编码方案是当前网络编码领域的 重要议题。 基于以上两方面的原因，我开发了用于网络编码规划的仿真工具软件。我 们统一了网络编码规则，并在逼真的网络情景下测试了网络编码的效果。 需要 强调的是，我们是在针对多播，且实现最小费用的网络子图上进行网络编码， 而并不是在整个网络拓扑图上进行编码。借助上述优化，网络编码将变得更加 高效且有益。 对于优化以及网络编码方案的选择上，我选用了便于用分布式方法实现的 算法。与集中式相比，分布式方法更加灵活，且更具可行性。它可以及时对网 络的变化做出反映，更好的适应现实情况。 本论文实现对无线网络仿真工具s w a n s 的进一步开发，增加了在网络传 输过程中实现线性优化及网络编码的新功能，并在此基础上得到了较为理想的仿 真结果。 关键词：网络编码， 线性优化， 无线网络， 多播， 最小费用路径， j i s t ， s ，a n s a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fr e s e a r c ho nn e t w o r kc o d i n g ，c o d i n gd o e s n to n l yh a p p e na t s o u r c en o d e sa n ym o r e b yt a k i n gt h ei n t e r m e d i a t en o d e si n t oc o n s i d e r a t i o n ，t h e t h r o u g h p u ta n dt h er o b u s t n e s so ft h ew h o l en e t w o r ku n d e rc e r t a i ns c e n a r i om a yr i s e r e m a r k a b l y o nt h eo t h e rh a n d ，c o d i n gi t s e l fn e e d ss p e n d i n gp r o c e s st i m ea n dh a s t o i m p o s es o m ei n f o r m a t i o nh e a d e mo n t ot h eo r i g i n a lp a c k e t s ，f o rt h i sr e a s o n i tm a ya l s o p u tab u r d e no nt h ew h o l en e t w o r kt o ac e r t a i ne x t e n t h e n c e ，f i n d i n ge f f i c i e n t n e t w o r kc o d i n gs c h e m e s b e c o m e so n eo ft h ec r u c i a li s s u e so nt h er e s e a r c hf i e l d t h en e t w o r kc o d i n gs t r a t e g ye m p l o y e di nm yt h e s i si sc l o s e l yr e l a t e dt op r a c t i c e i ti s s e r v e da sas i m u l a t i o nt o o lf o rn e t w o r kc o d i n gp l a n n i n g w eg e n e r a l i z ear u l eo f n e t w o r kc o d i n ga n dt e s tt h ep e r f o r m a n c eo ft h en e t w o r kc o d i n gi naq u i t er e a l n e t w o r ks e e n a r i 0 m o r e o v e r i no u rn e t w o r kp l a n n i n gt o o ln e t w o r kc o d i n gi si m p l e m e n t e do v e r a s u b g r a p hw i t ht h em i n i m u m c o s tm u l t i c a s t ，n o tt h ew h o l en e t w o r k w i t ht h eh e l po f s u c ho p t i m i z a t i o n ，t h en e t w o r kc o d i n gb e c o m e sm o r ee f f i c i e n ta n db e n e f i c i a l a n o t h e ra s p e c tw ea r ec o n c e r n e dw i t hi st ot r yt oi m p l e m e n tt h eo p t i m i z a t i o na n d n e t w o r kc o d i n gi nad i s t r i b u t e dw a y c o m p a r e dw i t hac e n t r a l i z e dm a n n e r ，a d i s t r i b u t e dw a yi sm u c hm o r ef e a s i b l ea n df l e x i b l e i tc a nr e a c tt oc h a n g e si n n e t w o r k si nt i m ea n da d a p tb e t t e rt oan e wr e a l i t y o u rw o r kf o c u s e so nm u l t i c a s t si nl o s s l e s sw i r e l e s sn e t w o r k s b e s i d e st h et h e o r e t i c a l a n a l y s i s ，w ea l s op a yc l o s ea t t e n t i o no ns t u d y i n gt h es i m u l a t i o n t o o ls w a n sa n d f u r t h e rd e v e l o p i n gt h es i m u l a t i o nt o o lt om e e tt h en e e d so ft h ec u r r e n tn e t w o r kc o d i n g s i m u l a t i o n s k e y w o r d s ：n e t w o r kc o d i n g , l i n e a ro p t i m i z a t i o n ，w i r e l e s sn e t w o r k ，m u l t i c a s t ， m i n i m u m c o s tp a t h ，j i s t , s w a n s 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 当今，许多研究团体都在致力于网络编码方面的研究。传统意义上的数据 传输规划都专注于解决网络流量问题。网络编码突破了这种传统思路，提出了 直接规划数据包传输的新理念，即在信息传输的过程中，将若干不同的数据包在 传输的中间节点进行随机组合从而生成新的数据包。 在特定的网络情景下，由于网络编码可以带来显著的增益，因而具有特殊 的吸引力。在本论文中，我们考虑的是无线网络中的多播情况。这种网络情景的 两大特点表明其尤为适合实施网络编码。【1 】 首先，多播方式增加了信道复用的可能性。 其次，在无线网络中，信息 传输采用广播方式，换句话说，由网络中的一个节点向另一个节点发送消息， 实际上将是向属于同一范围内的一组节点发送消息。尤其是对于传输编码后的数 据包，这种多播传输机制可以带来很大增益。 现有的网络编码方案可以大致分为两大类【1 】： 第一类，分布式方案只要满足最大流一最小割定理，网络中的每一个节点都 实施随机网络编码，无需寻找路由。这种方法构建了一个实现网络编码的通用 结构。借助添加在数据包头的信息，每一个接收点都可以准确无误的对数据包 进行解码f 2 1 。然而，这种方案往往并非网络资源利用的最佳解决方案。 第二类，集中式方案这种方案会在实施网络编码前先确定路由，它能 够帮助我们找到网络资源分配在特定标准下的最佳解决方案( 例如，最短路径、 最大流量或者最小费用等) 。根据路由得到的流量信息我们能够进一步得到网络 编码的最优解决方案，即在通过路由得到的网络子图上实施网络编码。这种方 案对于网络编码来说更加高效且更接近最优。 本论文中，我所设计的仿真工具主要基于第二类方案，它可以帮助我们实 现最优的网络编码规划。我的工作可以大致分为两个阶段。首先，利用线性优 化找到针对一组多播的最小费用路径。其次，在得到的最小费用路径的信息交 汇点实施网络编码。 我们的目标是将优化理论与网络编码理论相结合，并将这些理论知识应用 于接近真实的网络环境中得以检验。为了达到这个目的，我们不仅要实现相关 的算法，还要考虑许多现实的网络传输问题。 在工作中，我需要设计新的路由 协议，并且在此基础上，确定合适的网络编码方案。 与此同时，还要设计与 之相应的完善的传输机制。 第一二章叫络编码以及优化理论 第二章网络编码以及优化理论 2 1 网络编码理论 网络编码理论表明，网络编码是一种达到网络容量的有效方法。在我们开 发的软件工具中，我们希望实现网络编码的功能，并在网络仿真中测试网络编 码的性能。现在留给我们的问题是如何实施网络编码，以使得信息传输过程中 能够恰当的被编码，并能最终成功被解码。与此同时，我们希望网络编码对传 输效率的影响降至最小。另一个急待解决的问题是如何将网络编码方案与现有 的网络通信协议和传输机制匹配起来。下文中我们将详尽介绍上述两个问题的 解决方案。 2 1 1 网络编码简介 让我们从网络编码的基本概念丌始进行介绍。传统意义上，信源或信道编 码都发生在源节点。中间节点负责传递数据包而不做任何修改和处理。与简单 的复制数据包相反，在实施网络编码时，中间节点将线性组合其接收到的数据包， 生成一个编码后的数据包，并传递出去。 通过网络编码， 我们可以得到的两大收益是：【3 】 1 在很多情况下，它增加了整个网络的吞吐量，使得我们可以更有效的利用有限 的网络资源。 2 它可以容忍数据丢失和传输失败的出现，因此，网络传输的努棒性增强。从 这个意义上看，网络编码也可以用于网络传输出错后的信息恢复。 本论文中，我们更专注于第一条性质。我们希望借助网络编码能够是网络 容量最大化。我们假设一个具体的网络情景，我们将在一个数据包网络中实施 网络编码。正如我们在简介中所提到的，网络编码的研究对象是数据包而不是 流量。如果数据包的长度不同，将数据长度短的数据包补零。【4 】中的结论告诉 我们线性网络编码足以保证成功实施编解码，因此我们在网络编码算法中采用 线性结构。在编码过程中，我们线性结合若干数据包。编码过程中的加法、乘 法运算必须在有限域f 中进行。在这里，i 指的是i 一字节码字。下文中我们 将阐明编解码过程中所用到的算法。【5 】 1 编码阶段 假设我们有m 1 ，m 2 m n 个原始数据包由一个过几个信源发出。在线性编 2 第二章网络编码以及优化理论 码中，数据包中的每一个码字都是原始数据包的线性组合，其形式为 以一罗& m ：。在这里， 系数序列9 1 ，9 2 ，g n 被称为有限域f 2 8 上的编码 向量。”1 编码后的码字集合组成编码后的数据包。网络编码允许编码后的数据包 递归地被继续被编码。假设一个节点收到了一组编码后的数据包，它可以将其 进行线性组合，生成一个新的编码后的数据包，其形式为mt ；yj l l ；m ，在 这里，新的系数序列是新的编码向量。新的全局编码向蜇i 由以下公式 g ：一罗庇f g ? 得出。 裂解码阶段 假设一节点接收到一组编码后的数据包。为了成功恢复n 个原始数据包， 解码过程当且仅当满足下列条件时才可能发生，即当节点接收到多于n 个线性 无关的编码后的数据包时。从数学角度来看，上述解码过程等同于解方程求未 知数。我们需要m = n 个等式以解出n 个未知数的值。这类问题可以通过高斯 消去法求解。高斯消去法通过按行消去等式矩阵中的元素，最终将矩阵转换成对 角阵的形式。一旦矩阵中的编码系数变成单位对角阵，我们所得到的数据包向 量即为原始的数据包组。 谈及具体的编码、解码操作，我们将用以下一个例子来做具体说明。我们 选取有限域f 2 8 ，所有操作都在这一有限域上进行。相应于有限域的纬度，代 表网络编码操作最小单元的码字长度为8 比特。 1 加法运算 有限域f 2 8 上的加法运算是标准的按位异或运算。也就是说一个数据包中的 每一个码字与另一个数据包相应位置上的码字进行异或运算。 2 减法运算 有限域上的减法运算可以转化为加法运算的形式，即a b = a + ( 一b ) ，这 里一b 被称为b 取反。对于有限域e 来说，减法运算和加法运算操作相同。 3 乘法运算 有限域f 2 8 上的乘法运算分为两步完成。每一个码字或系数都被表示为多 项式的形式a 0 + a l x + 。首先将两个操作数相乘，我们得到一个新的多项式， 其阶数可能大于7 ，如果运用r i j n d a e l 有限域( 也被称为g a l o i s 域g f ( 2 8 ) ) ，则 其高次不可约多项式形式为1 + x + x 3 + x 4 + x 8 。第一步相乘的结果与高次不可 约多项式求余，由此得到最终的有限域f 2 8 上的乘法运算结果。 4 除法运算 有限域上的除法运算可以转化为乘法运算的形式，即a b = a xb 一，这里元 素b 1 被称为b 的逆。因此，在进行除法运算时，我们只需先找到b 的逆然后 进行乘法运算。 3 第二章网络编码以及优化理论 2 1 2 代数观点 代数几何学引入了数学处理方法中的一些重要定理，用以解决网络编码问 题。本论文中网络编码的实现基于【8 】中提供的结构。文献【8 】中表明，一个网络 中的多播连接可以表示成多项式的特殊结构。文中给出了网络g 以及有一定的 网络链路，并给出了一系列简化假设。 1 有限域上的任意链路容量为常数，即没单位时间m 比特。不失通用性， 我们可以假设任一链路拥有单位容量。 2 网络中的链路具有相同的时延，为了确保网络的稳定性，在这里假设无 延时网络非循环。 3 已知随机过程x ( mz ) ，z 独立于速率每单位时间m 比特。这里的单位 时间与链路容量中所指的单位时间一致。任一链路c - - - “v t , m0 ) 的r ( c ) 是整 数，等于陬嵋驯。 4 对于不同的y ，由不同源节点发出的随机过程x 和，z ) 相互不相关，更严 格的说，相互独立。 5 除了上述假设条件外，作者还假设网络中的通信由传输比特向量实现， 向量的长度，即所有传输的码字长度相同，并假设所有链路传输同步。 定义1 【8 】：已知g = ( 肜e ) 是一个无延时通信系统。我们说g 是一个有限域 f 2 m 上的线性网络，如果对于所有链路而言，链路e = o ，u ，f ) e 上的随机过程 y ( c ) 满足 卢p ) y m 善砘卅。篆绯，尾川p ( 2 1 ) 这里系数q ，和成是有限域f 上的元素，任一节点v 上输出z 是y ( e ) 的一种 线性组合： z d ，j ) 一 罗嘶y 0 i ) ( 2 2 ) 。协c ：奢矗一v 系数q 。，展：。，和占卅的值可以随机从有限域f 2 m 中选取。 已知网络g 和网 络中的链路连接，则解决网络编码问题可以被视为在代数条件下寻找可行的链 路连接。在代数观点下，等同于确定参数q ，。，, a e ：。，和占。：，在有限域f 2 m 中 的值。由此，所有的欲求得的链路连接可以通过确定参数的值而在网络中建立起 来。在此定义的基础上，作者进一步阐明了代数思想，其引入了一些矩阵理论 中的基本概念和操作。借助于线性代数的知识，我们可以构建和解决最初的网 络编码问题。 4 第二章网络编码以及优化理论 定理1 【8 】：让我们考虑一个拥有单一源节点和单一目的节点的网络，链路连接c = ( v ，v ，x ( v ，) ) 。当且仅当链路连接的速率r ( c ) 小于或等于v 和1 ，之间所 有割集的最小值时，网络编码问题可解。 证明见附录b 。 上述最小割一最大流定理可以被看作是一个图的定理。下文中，我们将从 代数角度来解释这一定理。对于最小割一最大流定理转换可通过引入矩阵概念得 以实现。 对于一个有限域f 2 m 上的线性网络，我们可以用一个转移矩阵来准确描述 输入向量x 和输出向量z 之间的关系，这一发现对我们是一个极大的鼓舞。我 们用矩阵m 来代表这一网络中的系统转移矩阵，则输入向量x 和输出向量z 之 间的关系可以表示为： z = x m ( 2 3 ) m 是具有固定系数哆，。，屈：。，和乞j 矩阵。 矩阵中的元素属于有限域 f 2 m 。对于我所研究的情况，我们将这些系数视为中间变量。我们不妨给出一 个例子来说明上述矩阵观点的应用方法。考虑以下网络拓扑图： 图2 1 两数据包进行网络编码的网络拓扑图 c ：f 属t 屈s 屈s 氏1 p hp 1 3 良4p 玎p ，5 p 5 6 ) ( 2 4 ) 在这里，矩阵a m x n 包含了输入随机过程的线性组合系数，其中m 由所发送 啦啦易岛 硒踊 历所 ，。一，、 = = 彳 口 第二章网络编码以及优化理论 在这里，矩阵a m n 包含了输入随机过程的线性组合系数，其中m 由所发送 的随机过程数目决定，而n 由从源节点发出的链路数目决定。矩阵日：i x k 存储了 输出随机过程的线性组合系数信息。其中，j 代表了进入目标节点的链路数目， 而k 代表了输出随机过程的数目。矩阵c 反映了网络中的连接情况。它包含了 网络中所有可能的链路连接信息。在上述例子中，我们可以用转移矩阵m 来描 述输入输出之间的关系： m = a c b r ( 2 5 ) 如果将网络视为数据包网络，那么在每一个观察点的随机过程可视为相互 独立的数据包。如果我们跟踪数据包的传输轨迹，那么编码后的数据包可以表 示为以下形式： k 一，口1 x + 口i x k 一口2 x + 口2 x 匕一展，x k 一局。x e ；风e + 岛，匕 k 一尾。e z - 4 k + f 7 e z 。一f ：k + ； ( 2 6 ) 在此项目中，我们希望在目标节点成功解码，即z x 。我们可以进一步 将矩阵a 和转移矩阵m 简化为单位对角矩阵。我们最初提出的找出可行的网 络编码方案的问题就转化为了寻找在矩阵c 中合适的系数的值。 定理2 【8 】是最小割一最大流定理的变形。如上文提到的， 已知一线性网 络，源节点为l ，目标节点为1 ，7 ， 网络中的链路连接记为c = ( 嵋y ：x p ，) ) ， 链路上的传输速率为r ( c ) 。以下三种陈述等价： 1 可能存在一点到点的链路连接c = ( my ：x p ，v ) ) 。 2 ，和 ，之间以速率r ( c ) 传输满足最小割一最大流条件( 定理1 ) 3 r ( c ) xr ( c ) 的转移矩阵其行列式的值在有限域环 e 【- ，q ，成_ ，鲥】上不为零。 证明见附录b 。 通过定理变形和以上的例子，我们发现了解决网络连接问题和确定有限域 上多项式系数的等价关系。 对于多播网络，定理4 说明已知一个无延时网络g 以及网络中的一系列链 6 第二章网络编码以及优化理论 路连接c ； ( 秒，“。，z ( ) ) ，( ，h ：，z ( 抄) ) ，( ”，z ( u ) ) ，则当且仅当最小割一最 大流的条件满足时，对于所有的链路连接网络问题( gc ) 可解。 证明见附录b 。 鉴于我们有了如此强大的数学工具，现在我们更加关注用以代表特定网络 情景的矩阵以及矩阵的内的系数。通过这种方式我们可以更多的利用数学方法 来分析网络。以下推论是关于网络和矩阵关系研究得到的结论之一。 推论1 ：已知一个无延时通信网络g 以及一个有解的多播网络问题，其带有一 个源节点和n 个目标节点。设r 是源节点发送消息的速率，则在有限域f 2 n 上 存在对于网络编码问题的解，其中m 满足ms l o g ：( n r + 1 ) 1 明见附录。 。 2 1 3 多播网络的容量 我们需要强调网络容量这一概念的初衷源于【9 】中得出的一个重要结论，即 通常来说，通过简单的路由，将信息在网络中不做任何变化的传输，无法达到 网络传输最优。我们必须引入网络编码以使网络传输达到网络容量。那么我们如 何设计我们的网络编码方案来达到这个目标昵? 下文中我们将阐明符合以上要 求网络编码的标准。 与【3 1 中的标记方式保持一致，我们用参数a ，b 以及向量h 来表示一组多 播要求，其中h = h 1 ，h m 】，h i 定义了信息源x i 的信息传输速率。x 1 ， x m 是一组相互独立的信息源。设a ：1 ，m - - - + 协b ：1 ，m _ 2 v ，其表示 是2 v 上的任意映射，则多播组可以用a ，b 和向量h 来描述。现在考虑一个多 播从源节点s 出发，发送到l 个目的节点t i ，t l 。任一链路o ，_ ) e 上的信 道容量记为嘞，其中r 表示所有链路上信道容量的集合，即r = 限，( f ，j ) 明。 在分析一源节点一四目标节点网络编码问题的基础上，作者由此得出了以下推 论。 推论2 ：已知g = ( ke ) 是一个拥有一个源节点s 以及l 个目标节点t l ， t l 的网络拓扑图。任一链路上的信道容量记为凰，那么当且仅当从s 到任一t l ， 其中z = 1 ，2 ，l 大于或等于h ，即信源速率的时候，( 尺，h ，g ) 是可行的 网络编码方案。这一推论是最小割一最大流图形化的解释。接下来我们给出了 一个例子来说明这一推论。 7 第二章网络编码以及优化理论 图2 2 带有信道容量的网络拓扑图 图2 3 达到信道容量的网络编码方案 如图所示，对于l = 2 推论2 成立。图2 2 标明了每一条链路上的信道容量， 图2 3 表示出了编码方案。 上述网络编码理论是进行实际网络编码的基础。接下来我们需要解决的问 题是网络优化的问题。 2 2 优化理论 8 第二章网络编码以及优化理论 2 2 1 问题的数学表述 已知一个有向图g 有一系列节点y 和边e 组成。如果我们将图中的点视为 一组分享共同网络资源的用户，他们可以在网络中发送或接收消息，并且将图中 所有的边视为网络中用来实现信息交互的链路或信道，这种连接可以是有线的也 可以是无线的，那么有向图g 即可以代表一个网络拓扑图。如果我们进一步 给图中的每条链路配置参数，那么有向图g 则能够描述和模拟一个更具体的网 络情景。例如，如果我们给每一条边赋以边界条件，则可以将它对应为网络 链路中的信道容量。如果我们给每一条边赋以权重参数，那么在实际中它可以 模拟任意影响网络连接情况的因素。例如，传输功率、干扰或者时间分片，甚 至是建设开销等等。我们把这些因素抽象为费用参数。 我们希望解决的问题是当数据包在无线网络中传输时，使费用函数最小化。 我们所研究的网络情况是多播网络。通过优化任一链路上的流量值，我们能够 得到问题的最优解。在这里，我们强调多播这一概念，即由一个源节点同时传 输给多个目标节点。 尤其是对于无线网络，如果我们设定网络模型为无损广播传输方式，则有 线网络中普遍意义上点到点的链路连接将被一点到多点的所谓超链路连接所代 替。它代表了由一点到其所有邻居节点的链路集合。这里所指的邻居节点即所有 与源节点属于同一范围的所有节点。让我们再更清楚的表述一下这一优化问题。 设一源节点s 要以速率尺发送数据包到一组目标节点r ，其中z 为非空集 合。我们将优化问题公式化为 1 0 1 ： m i n m i z e f ( z ) s u b j e c tt o z e z 搿，v ( f ，j ) 爿，kc - ，t e t ( 2 7 ) 承 州蠢，荟弘州，磊罔，z 鬟# o , ( t m 刨 f r 础0 , v ( i ，j ) 彳，v j e j ，t z 其中，f 是费用函数，t 表示目标节点集合中的一个节点。句表示在超链 路( j ) 上的传输速率。考虑链路中的传输损失，则每条链路上实际接收数据 包的速率被记作z 叔符号公式( 2 7 ) 中的反映了网络传输中的损失情况， 它由以下公式求得： 罗缸 ；型譬 ( 2 8 ) 9 第二二章网络编码以及优化理论 以下的定理阐明了传输与优化问题之间的关系。 定理3 ：向量z 是优化问题的解，当且仅当网络编码使得无线网络中，每一超 链路连接上的传输速率无限接近时，在多播超链路连接h 上从源节点到一组 目的节点的传输速率将无限接近尺。 证明见【1 0 】。 由于此项目针对无损无线网络，在这种情况下我们可以设k = j ，则 = 1 。 将的值带入公式( 2 7 ) ， 则优化问题的数学形式变为： m i n m i z e f ( z ) s u b j e c tt o z e z z u2 z 嘲，v ( i ，) 彳，f 丁 ( 2 9 ) 似蠢，荟镏一硎，善罔，x 譬i m 胙z 瑚苫o ，v ( i ，j ) 彳，v j s y ，te t 如果进一步假设费用的值离散递增，则网络中的总费用等于各链路上费用 的总和，即厂( z ) ：一罗厶( z u ) 。 鉴于我们将费用函数定义为线性，那么解决 上述线性优化问题，p 箕费用函数可表示为厂( z ) 净罗a u z 盯。 为了进一步简化问题，我们采用( 1 0 ) 中提世酌方法，引入一组新的变量 薪。以下我们将解释如何求得新- - b a r ，以及其物理意义。首先，假设每一个 节点i 拥有m i 条超链路连接，由i 点发出( i , j ( 1 0 ) ，f ，p ) ，( f ，2 ) ， 其中 衅j 爹j 芸。并且，我们同时假设这m i 条超链路连接已经按费用大小 进行了由d , n 大的排序，即以下不等式成立： ，彬，( ；) 厶9 ( 亭) 毛口( ；) ，对于所有；0 - - 以及所有节点i 。 则变量 甾被定义为a ： 热荟m i 、磁， m - m u ，j j ( 2 1 0 ) 其中，m ( i ，k ) 是唯一的m 值使得_ ，：，篡。( j o 被定义为空集，对于 所有的f ) 。具体到我们的项目，费用的不等式条件可表示为 口尔o 巴，j ，卜 口讲，l o 相应的变量硝可被解释成所有费用大于或等于由f 到_ 的超链路连接中链路上传输速率值的总和。经过以上的简化，线性优化问题可以 表示为以下形式： 1 0 第二章网络编码以及优化理论 m i n i m i z e f ( z ) i 知 m i n i m i z e r ( z ) 薯允( 知) s u b j e c tt o z z 心磊跛，。素朋碰之。甘磊让。镏，研；k m ，t z ， q j 。 州蠢，荟喵州，善罔，础t 可，f r ， 掣so ，v ( i ，j ) ，e a ，t e t 以下的命题证明了优化问题( 2 9 ) 和( 2 1 1 ) 在一定限制条件下的等价性， 并且找到了解向量并。与相应的原问题的解向量z 之间的关系。 命题1 ： 假设，( z ) ：曩厶( ) ，且厶f f i ( 考) 厶，( 考) 毛婉( ；) ，对 于所有0 乏0 和节点i ：而问题( 2 9 ) 和问题( 2 1 1 ) 是等价的，因为两问题拥有 相同的最小费用解，且当且仅当z 是问题( 2 9 ) 的最优解时，z 是问题( 2 1 1 ) 的最优 解。 证明 假设( x ，z ) 是问题( 2 9 ) 的有效解，那么对于所有的( f ，j ) ，e a 。以及所有t e t 磊锄n 。善荟瑙k 。瓢一。瓢，攫k 旧磊，叫瓢川攫k 仁1 2 4 旧菇，磊j ，铱 v锣 旧g j 巩札。 因此，( x ，z ) 是问题( 2 1 1 ) 带有相同费用参数的有效解。 现在假设( x ，z ) 是问题问题( 2 9 ) 的最优解。由于我们假设 么，( 当) 么，( 纠 0 代表适当选取的步长。这里p 。阢+ 1 】是新一轮的迭代值，它通过将 p 箩伽】+ 研，l 蝣1 1 投射到弓上而得到。如果我们将p n l + o 1 4 n l 记为 变量u ， 并进一步假设u ( t o 芑l l ( f 2 ) “，其中i 丁l 代表了目标节点的数 目，我们将到达每一个节点的u 由大n 4 进行排序，并找出指数， 其被定义 k 为满足以下不等式的最小k 值： k ( a # - 耖) 轳) ( 2 2 7 ) 如果不存在这样满足条件的指数，则= 例。通过引入这样一个变量，我们 上述的投射迭代过程可以简化为 证明 我们希望解决以下问题： 其中弓是t 维的单形。 b 西暑a r g m i n 舡一x l l 2 ：x e x m i n i m i z 0 2 ( v 一“) 2 i 七- ， s u b j e c tt oy 弓 ( 2 2 8 ) ( 2 2 9 ) 第二章网络编码以及优化理论 弓5 y i 善v 。= 口驴，y o ( 2 3 0 ) 首先，由于主函数以及限制条件嘞都是凸性的，因此可以直接建立起对 于在弓上全局最优v p 的充要条件： o 净( “o 一y o ) 乏( 一) ，v r e t ( 2 3 1 ) 设“( t ) “( f z 乏乏“i ，则我们可以记v t l 0 ，对于所有z ；1 , 2 ，k ， 且 矿一0 ， 对于所有l k - t - 1 ，如果上述结论不成立，那么我们司以通过交换向量 中的元素来得到带有更小费用的解。因此，条件( 2 3 1 ) 表明必然存在某一d 值， 使得 ；“( r ) + d 。 对y - 所有f 戗，气) ，且ds - - u ( t ) ， 对于所有 f 饥小，t i r i 。其等价于d - - u ( t * * do 由于；在单形弓中，它符合以下等 式。 趔+ 甜= z o 其中 “a # - 扩) 将k 设为j j ，其中表示符合以下不等式条件的最小k 值 七( a 玎一耋“( f ) s “以+ 1 ) ( 否则= 川) ，我们可以得出 击卜p ) u 它可以被进一步整理成以下形式 因此我们可以得到以下结论： 丢( 一耋“( f ) 一m ( f i ) 1 6 第二章网络编码以及优化理论 既陋+ 1 】：皇 + 华 仁3 动 另一个我们需要注意的地方是，在主要迭代步骤中停止条件亭= 0 在现 实中过于严格，即使对于确实存在最优解的情况。确定恰当的迭代中止标准对 于实现次梯度算法来说是十分必要的。一种方法是限定实施算法时迭代的最大 次数。另一种方法是比较每一次得到的优化结果，一旦前后两次迭代的差距小 于预先设定的一个范围亭 0 ， 则中止迭代。 如公式所示，步长作为一个关键的因素，将很大程度上影响算法的效果。 鉴于这个原因我们需要认真考虑任何选取步长函数或步长值。 对于这个问题， 有许多方法和标准可供参考，他们解释了如果确定步长并在不同程度上改进了次 梯度算法的计算效果。由于我们的初衷是找到最小费用这一原问题的最优解， 因此步长的确定也必须服务于寻找原问题的最优解，这也就是说步长的确定不 能只局限于考虑求解拉哥朗日对偶问题。下文中当分析如何由拉哥朗日对偶解 来恢复原问题解的时候，我们将给出步长的确定方法以及步长的最终形式。 次梯度优化得到了拉哥朗日对偶问题的最优解，但这一解并不一定是原问 题的最优解，因此我们引入了原恢复方法以保证原问题的解最优。 【1 4 】中提供 了若干种由拉哥朗日对偶的最优解恢复出原问题最优解的方法，其恢复方法与上 述次梯度算法相联系。通过计算特定的迭代公式我们可以得到原问题的最优解。 在接下来的小节里，我们将深入了解原问题恢复算法这一概念，并确定合适的 步长。 2 2 4 原问题恢复算法 定理2 ( 弱对偶定理) 【1 3 】 设x 是问题p 的解，x e x ，g ) 0 0 ) a0 ，并设问题d 的解为( 屿 ，) ，其 中u 0 贝0 厂o ) 苫o ( u ， ，) 。 证明 借助对于o ( u ，) 的定义以及x e x 我们可以得到 目( “) 一i n f f ( y ) + “g ( _ y ) + ，h ( y ) ：y x s 厂( z ) + h 。g ( x ) + y 7 ( x ) ( 2 3 3 ) 墨，( 工) 由于砧0 ，gs0 且 一0 证明完毕。 1 7 第二章网络编码以及优化理论 假设我们已经得到了对偶问题的解，通过上述定理我们可以得到对偶问题 解和原问题解的关系，鉴于对偶问题的解往往并不等同于原问题的解，我们必须 引入原问题恢复算法。 在文献f 1 4 】中给出了若干中由对偶最优解恢复出原问题最优解的方法。 如 果我们在解决拉哥朗日对偶问题时，使用的是次梯度算法，那么我们假设任一次 迭代以之0 ，k 1 ，在万= 吒的次梯度瓯可以由以下等式计算出来： g t = a x , ，k - b ，w h e r ex , , , 以_ 缸：s o l u t i o nt o ( 2 2 1 ) ( 2 3 4 ) 根据s h o r 得到的l p 与l d 之间的数学关系，我们可以构造以下等式： 静屯 其中荟；1 孤d ，k o 幻r j l ，七 ( 2 3 5 ) 在这里， 在公式( 2 3 5 ) 中所定义的k ，且j c l ；v j - 1 , ，k 是一系 列在k 次迭代中的凸组合系数。如公式所示，原问题的最优解以是其通过次 梯度方法得到的对偶问题解的凸性组合。让我们由此引出以下定义： 并且 ) ，弦一肛；力，j 11 , ，k f o re a c hk 一1 ，2 ， ( 2 3 6 ) 戌懈暑m a x i m u m r 肚一y ( 卜啪：j 一2 ，丘 ( 2 3 7 ) 基于上述等式，我们可以引出以下定理。 定理3 设次梯度方法按照一定的步长达到了对偶问题的收敛解，即当k 呻0 0 时 吒呻万对于万0 。如果步长和凸组合系数；，k 选取满足以下条件： 1 y 弦一) ，( ，- 1 ) i f o ra l l j 一2 ，。七f o re a c h k 2 当k - 0 0 ，) ，严_ 0 3 当k 呻，y n 呻0 ) ，船s 6f o ra l lk ，f o rs o m e6 0 则由次梯度方法得到的对偶问题解序列的组合即是原问题的解。 证明 通过公式( 2 3 4 ) 和( 2 3 5 ) 我们可以得到 戤小荟k 限( 吒一6 ) 一再k 郴k ， 删8 ) 第- 二章网络编码以及优化理论 其中g ，是对偶问题在p i 上的次梯度，由于乃+ 。乃+ 以毋， 我们可以得到 如一6 ( 乃+ l - 乃) = 一筹乃+ 粪( 鲁一等卜+ 和妻杀 = 一乃七乃一( 7 肛一弦，+ 以“(239)y(j-m 3 9 ) 2 一乃一乞【一只+ 以“ ( 2 = 乃+ y a n k + l _ 另( - r ( 川) 。) + ( 一弛) 。) ( 孑一乃) = ( 死+ 。一孑) + n 。( 牙一巧) + 宅( 一以川，。) ( 另一乃) 设v k 表示公式( 2 3 9 ) 中的等式的最后一项，我们发现当尼- - - - o o ， 唯一0 。任取 占 o ， 并设，2 足够大，则对于所有的眵一乃0 占2 万成立。 那么对 于k j 且j 足够大，关注定理3 中的条件1 和条件2 ， 我们由条件1 和三角 公式可以得到 薹k ( 仇川塘一乃0 矿到j 孑一乃i | + 寺吾k 。( 一b 呲) ( 2 4 0 ) -。+g。g(r肚2一) 三+ 三一 由于占 0 是任意选取的， 我们可以推出当k 0 0 。吃j0 。而且，由于 碗l 属于集合x ， 必然存在一收敛序列使得 吒) 鬈jx 乃 符。 其用特定集合k 标 记。将( 2 3 8 ) 中的限制条件考虑进来，k 呻0 0 ，k k ，我们可以得到a x b 。又 因为对于所有的k x x ，则对于x x 我们可以得到相同的结论，由此定理得 证。 由公式( 2 3 5 ) 我们可以确保收敛得到原问题的最优解。在定理3 的条件下， 作者在 1 4 1 q b 进一步给出了定理4 。它表明了运用定理3 中的方案得到对偶问题 和原问题最有解组的可行性。 定理4 假设次梯度方法选取了合适的步长达到了对偶收敛，得到问题的解万 设x 为任意累积点如果以表示由公式( 2 3 5 ) 得到的原问题解序列。如果步长屯和 1 9 第一二章网络编码以及优化理论 设x 为任意累积点如果蠢表示由公式( 2 3 5 ) 得到的原问题解序列。如果步长九和 凸组合系数i t 满足定理3 中的3 个条件，则x ，万分别为l p 和l d 问题的最 优解。 根据 1 4 1 q b 推论3 和推论4 我们可以实现原问题恢复算法通过确定合适的 步长九以及组合系数t ，其符合定理3 中的3 个条件，并满足定理4 。 推论3( l a r s s o na n dl i u sr u l e ) 1 6 1 设步长和凸组合系数分别为以下形式： 九p ( 尼) ；a ( b + c k ) v k ，；1 k = l ，k ，v k ，( 2 4 1 ) 其中a 0 , b 0a n dc 0 是选定的常数。那么定理3 中的3 个条件成立。 证明 通过公式( 2 3 6 ) 和( 2 4 1 ) 我们可以得到y 雎= p + c j ) a kf o r a l lj 一1 ，后f o ra l lk 。 因此，对于j = 2 ，k 存在y 肚一) ，( - l 弘一c a k 0 ， 且当k 趋于无穷时， 理缸= c a k _ o ，_ 0 , r a c a 。由此推论得证。 推论4 设步长满足 对于所有k o 九+ ts 九! 觋尼九一0 0( 2 4 2 ) 则可以达到对偶收敛，即对于某一石乏0 s r k 足一万。 如果将凸组合