（信号与信息处理专业论文）编码分组网络的效用最大化及网络编码在应用方面的研究.pdf

北京邮电大学博士学位论文摘要 摘要 2 0 0 0 年，a h l s w e d e 等人基于网络信息流的概念提出了网络编码的思 想。通过允许网络节点进行编码，可以获得网络组播速率的最大流限， 即网络资源利用的理论上限，而通过传统的路由和复制并不一定能够获 得该最大流限。此外通过网络编码可以取得节省网络带宽资源，平衡链 路负载，优化能量受限网络的能量消耗等好处。目前，有关网络编码理 论的研究己经引起了学术界的高度重视，网络编码已经成为网络信息理 论领域最受瞩目的研究热点之一。 本论文的工作基本都围绕网络编码展开，首先对网络编码的设计进 入了系统深入的分析。在此基础上，在理论方面，对基于网络编码的分 组网络的效用最大化进行了深入的研究。在应用方面，研究了随机网络 编码在无线m e s h 网络中进行文件共享时对文件下载成功率或下载时间 的影响，以及如何利用网络编码技术在传感器网络实现连续实时的数据 采集等问题。论文包含以下几个部分： 第一章介绍网络编码提出的背景、网络编码的概念和网络编码的研 究现状，以及本论文所做的工作。 第二章总结网络编码在设计方面的研究成果，详细介绍线性网络编 码、随机线性网络编码、使用于循环网络的带时延的网络编码设计方案， 以及能够应用于分组网络的实用的网络编码，为后面几章的研究工作奠 定理论基础。 第三章研究编码分组网络的网络效用最大化问题。针对提出的单通 话编码分组网络效用最大化模型，提出了分布式的梯度投影算法，并证 明了算法收敛的充分非必要条件，通过仿真验证了算法的正确性。 第四章研究传输合同约束条件下且编码子图给定时编码分组网络 的效用最大化问题。基于提出的优化模型，通过对偶分解，提出了分布 式的梯度投影算法，证明了算法收敛的充分非必要条件，并通过仿真验 证了算法的正确性。 第五章研究随机线性网络编码在无线m e s h 网络中进行文件共享 时所带来的性能增益。针对上传数据受限且m a c 层理想无冲突、m a c 层存在冲突、以及节点移动且m a c 层存在冲突三种情形，分别通过仿 北京邮电大学博士学位论文摘要 真研究了随机线性网络编码相对于传统路由所带来的增益问题。 第六章研究在无线传感器网络中如何通过网络编码思想来实现对 数据的连续实时采集问题。研究发现，通过把部分网络编码和随机线性 网络编码分别应用于信源传感器节点和中继存储传感器节点，数据收集 器可以对数据进行连续实时的采集。 第七章对全文进行总结，并对下一步的研究工作进行了展望。 关键词：网络编码；随机线性网络编码；实用的网络编码；部分网络编 码；无线m e s h 网络；无线传感器网络；网络效用最大化；梯度投影算 法 i i 北京邮电大学博士学位论文 摘要 a b s t r a c t n e t w o r l ( c o d i n gi si n t r o d u c e db ya h l s w e d ei n2 0 0 0 ，w h i c hi sb a s e do n t h ec o n c 印t i o no fn e t w o r ki nf o m l a t i o nn o w i fc o d i n gi sp e n n i t e db yt h e n e t w o r kv e r t i c e st h em a x n o wb o u n do fn e t w o r km u l t i c a s tc a nb ea c h i e v e d i e t h et h e o r e t i c a lu p p e rb o u n do fn e t w o r kr e s o u r c eu t i l i z a t i o n ，w h i c hc a nn o t a l w a y sb ea c h i e v e db yt r a d i t i o n a lc o p y i n ga n dr o u t i n g f u r t h e m o r e ，t h r o u 曲 n e t w o r l ( c o d i n g ，w ec a no b t a i nt h eb e n e f i t so fs a v i n gi nb a n d w i d t h ，l o a d b a l a n c i n g ，o p t i m i z i n gt h ee n e 玛yu s a g eo fe n e 唱y l i m i t e dn e t w o r k sa n ds oo n n o w t h er e s e a r c ho fn e t w o r kc o d i n gh a sr e c e i v e dg r e a ti n t e r e s t sa n dh a s b e c o m eo n eo ft h em o s ta t t r a c t i v ef i e l d si nn e t w o r ki n f b n n a t i o nt h e o r 讥 t h i sd i s s e r t a t i o nm a i n l ys t u d i e sn e t w o r kc o d i n g f i r s t l y ，t h ed e s i g no f n e 研o r kc o d i n gi sd e 印l ya n a l y s e d b a s e do nt h i s ，i nt h e o 叫a s p e c t ，t h e n e t w o r ku t i l i t ym a x i m u mo fc o d e dp a c k e tn e t w o r ki ss t u d i e d i na p p l i c a t i o n a s p e c t ，w es t u d yt h e e f r e c t i o no fr a n d o ml i n e a rn e t w o r kc o d i n go nf i l e d o w n l o a ds u c c e s sr a t eo rd o w n l o a dt i m ei nw i r e l e s sm e s hn e t w o r k a n dt h e p r o b l e mo fc o n t i n u o u sr e a l t i m ed a t ac o l l e c t i o nb a s e do nn e t w o r kc o d i n gi n s e n s o rn e t w o r k t h ed i s s e r t a t i o ni n c l u d e st h ef o h o w i n 2 ： c h 印t e rli n t r o d u c e st h eb a c k g r o u n do fn e t w o r kc o d i n gb e e nr a i s e d ，t h e c o n c 印to fn e 佃o r kc o d i n g ，m er e s e a r c hs t a t l l so fn e t w o r kc o d i n g ，a n dt h e w o r ko ft h ed i s s e r t a t i o n c h a p t e r2s u m m a r i z e st h er e s e a r c hr e s u l t so nt h ed e s i g no fn e t w o r k c o d i n g ，i n t r o d u c e sm ed e s i g ns c h e m eo f1 i n e a rn e t w o r kc o d i n g ，r a n d o ml i n e a r n e t w o r kc o d i n g ，d e l a y e dn e t w o r kc o d i n gu s e do na c y c l i cn e t w o r k i na d d i t i o n ， t h ep r a c t i c a ln e t w o r kc o d i n gu s e di nr e a ln e t w o r ki sd i s c 抽e d t h ec h a p t e ri s t h et h e o r e t i c a lb a s i so f f o l l o w i n gc h 印t e r s c h a p t e r3s t u d l e st h ep r o b l e mo fn e t w o r ku t i l i t ym a x i m i z a t i o no fs i n 9 1 e s e s s i o nc o d e dp a c k e tn e t w o r l ( d e v e l o p sad i s t r i b u t e dp r l e c t i o n g r a d i e n t a l g o r i t h mf o rt h ep r o b l e m ，a n dp r o v e st h es u 箍c i e n tb u tn o tn e c e s s a 巧 c o n d i t i o nt h a tc a nm a k et h ep r o p o s e da l g o r i t h mc o n v e 唱et ot h e9 1 0 b a l l y o p t i m a l s o l u t i o n s n u m e r i c a l e x a m p l e s a r e p r o v i d e d t ov a l i d a t et h e c o r r e c t n e s so ft h ea l g o r i t h m i i i 北京邮电大学博士学位论文 摘要 c h a p t e r4s m d l e st h ep r o b l e mo fn e t w o r ku t l l l t ym a x l m i z a t i o no fc o d i n g p a c k e tn e t w o r ku n d e rd e l i v e 拶c o n t r a c t sc o n s t r a i n tw h e nc o d i n gs u b g r a p hi s g i v e n d e v e l o p sad i s t r i b u t e dp r o je c t i o ng r a d i e n ta l g o r i t h mf o rt h ep r o b l e m m o d e l p r o v e ss u m c i e n tb u tn o tn e c e s s a 叫c o n d i t i o nt h a tc a nm a k et h e p r o p o s e da l g o r i t h mc o n v e 玛et ot h e9 1 0 b a l l yo p t i m a ls 0 1 u t i o n s n u m e r i c a l e x a m p l e sa r ep r o v i d e dt oc o m p l 锄e n tm et 1 1 e o r e t i c a la n a l y s i s c h a p t e r5s t u d i e st h ep e r f o m l a n c eg a i nb r o u g h tb yr a n d o mn e t w o r k c o d i n gi nw i r e l e s sm e s hn e w o r kw h e nf i l e s h a r i n gi sc o n ( 1 u c t e d t h r o u g h s i m u l a t i o n ，p r o v e st h ep e r f o r m a n c eg a i nb r o u g h tb yr a n d o mn e t w o r kc o d i n g c o m p a r e dt ot h et r a d i t i o n a lr o u t ei nf o l l o w i n gt h r e ea s p e c t s ：n o d e sb eu p l o a d 1 i m i t e db u tm a c1 a y e rb ei d e a lc o n f l i c t f i e ；m a cl a y e rb ec o n n i c t ：n o d e s b em o b i l ea n dm a cb ec o n n i c t c h a p t e r6s t u d i e sc o n t i n u o u sr e a l t i m ed a t ac o l l e c t i o np r o b l e mi n w i r e l e s ss e n s o rn e t w o r k st h r o u g hn e t w o r kc o d i n g d a t ac o l l e c t o rc a nc o l l e c t d a t ai nc o n t i n u o u sr e a l - t i m em a n n e rt h r o u g hu s i n gp a r t i a ln e t w o r kc o d i n gi n s o u r c en o d e sa n dr a n d o mn e t w o r kc o d i n gi nr e l a ys t o r a g en o d e s f i n a l l y ，t h ed is s e r t a t i o ni ss u m m a r i z e d ，a n d 向t l l r er e s e a r c ho nn e t w o r k c o d i n ga r ep u tf o r w a r d k e yw o r d s ：n e t w o r kc o d i n g ； r a n d o ml i n e a rn e t w o r kc o d i n g ； p r a c t i c a l n e t w o r kc o d i n g ； p a n i a ln e t w o r kc o d i n g ； w i r e l e s sm e s hn e t w o r k ；w i r e l s e s s s e n s o rn e t w o r k ；n e 觚o r ku t i l i t ym a x i m u m ； p r o j e c t e dg r a d i e n ta l g o r i t h m 独创性说明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经 发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机构的学位或 论文而使用过的材料。与我一同工作的同志对本研究所作的任何贡献均已在论文中 作了明确的说明并表示了谢意。 本人签名：珈垒义日期：幽：g 。左多 关于论文使用授权的说明 本论文作者完全了解北京邮电大学有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构交送论文的复印件，允许论文被查阅和借阅。本人授权北 京邮电大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 本人签名：望缝文 日期：巡： 、左乡一 导师签名：二琴；f 缺啦日期：一 北京邮电大学博士学位论文第一章绪论 1 1 网络编码提出背景 第一章绪论 香农曾指出：“通信网络端对端的最大信息流，是由网络有向图的最小割决定”， 但目前传统路由器的存储转发模式根本不可能达到香农最大流最小割定理规定的上 界。在现有的通信网络中，信息传输都是由源节点经过中间节点，以存储转发的方 式传送到目标节点。除了数据复制以外，一般来说在网络的中间节点并不需要做任 何数据处理，因为普遍认为中间节点所进行的数据处理对数据传输过程本身并不会 带来任何好处。尤其当组播技术应用于通信网络中，更是如此。因为组播是靠在通 信网络上建立组播树来实现的，当考虑一点到多点的组播路由树的建立时，问题变 得复杂起来。一般认为，组播树的建立是一个n p 问题。通常采用的方法是先用最 大流算法找到信源与一个信宿之间的最大流及其实现的路径，然后再依次寻找其他 信宿与信源之间的路径。在寻找信源与第二个信宿之间的路径时，往往就在原通信 网络中去掉信源与第一个信宿之间已经用过的链路的容量。这样处理是因为，传统 路由认为网络中传输的信息是不能叠加的，只能进行存储转发。这样的组播树的建 立方式，会导致信源与第二个及其后面所有信宿之间的路径都不是以它们之间的最 大流进行传输的，最终使得组播可以实现的传输容量远远小于最大流最小割确定的 容量上限。 然而，2 0 0 0 年r a h l s w e d e 等提出了网络编码彻底推翻了这一结论 1 】。网络编 码指出允许路由器对不同的信息流进行编码组合可以达到该上限，在此基础上，参 考文献 2 进一步证明在单信源多信宿情况下，应用线性网络编码理论，能够达到该 容量上限。线性网络编码将原先分立于物理层和网络层的两个核心概念( 编码和路由) 有机地融为一体，彻底改变了交换路由器只能对信息进行存储转发的传统组播模式， 建立起一种全新的网络体系结构及信息编码和传输模式。 网络编码代表了一种协同工作的理念，这使得它的应用不仅仅局限于改进组播 增加网络容量，它与其他技术相结合已经应用于网络管理、纠错、信息安全、p 2 p 、 m e s h 等网络通信、路由和交换等领域。 1 2 网络编码的概念 网络编码也是基于一个很简单的思想，网络编码是指在组播通信网络中，可以 在网络的中间节点上对接收到的信息进行一定形式的编码处理，然后再传输出去， 北京邮电大学博士学位论文第一章绪论 而不是像传统通信网络中那样在中间节点上只是进行存储转发。最后再在信宿节点 上，通过一定的处理方式，译出信源所发的信息。 下面通过文献 1 】中的“蝴蝶图来说明网络编码的基本处理思想及其带来的好 处。在这里，我们考虑一个无差错的传输系统，如图1 1 所示： b 图1 1 网络编码的饲子，信源为s ，信宿为j l 和畋所有链路的容量为1 | 1 1 这是一个理想的组播网络，不考虑时延和传输差错。其中：s 是源节点，4 和d ， 是目的节点，每条边的容量均为1 比特单位时间，不难看出，此网络的组播容量为 2 ，从图中我们可以看出，为了从信源节点同时传输两比特信息口和6 到目的节点z 和以，则在中间节点w 处，必须通过网络编码，使输出边圳传输两个输入边上携带 信息的线性组合口+ 6 ，那么在目的节点吐和以，可分别由口+ 6 和口，口+ 6 和6 恢复 出所有信息口，6 。如果按传统路由方式，在一个单位时间内将无法完成以上传输，即 无法达到组播容量2 。 1 3 网络编码的研究现状 网络编码本身是一个学科交叉的产物，包括图论，算法，信息论，( 信道信源) 编码理论，最优化理论等。网络编码最早是针对有线网络提出的，最初几年中，关 厂网络编码的大量文章都在考虑这样的问题，即对于不同类型的网络和连接需要网 络编码具有怎样的特征，以便能达到最大容量。研究方向主要包括线性网络编码和 非线性网络编码 1 4 】；分布式网络编码和集中式网络编码；网络编码在组播和非组播 2 北京邮电大学博士学位论文第一章绪论 网络中的应用。 到目前为止，组播集中式线性网络编码构造算法主要有两种：一种是由r k o e t t e r 和m e d a r d 提出的基于代数构造方式的线性编码构造算法 3 卅，可以将先前的结论推 广到任意网络，而且网络具有健壮性，并对有坏的有向图运用最大流最小割限的时 不变方法证明了这个结论。这种构造方式需要知道整个网络的拓扑信息，用一个系 统转移矩阵描述信源输入的信息和信宿上接收到的信息之间的关系，并通过构造符 合要求的系统转移矩阵来实现网络编码。另一种是p s a j l d e r s 和s j a g 百等人针对无 环、无时延图中的单源组播问题，提出的多项式时问算法 5 7 】。这种方法将网络编 码的构造进一步简化，它也是在己知拓扑的情况下，首先通过最大流最小割算法找 到完成组播所需路径的集合，在找出的这个子图上确定各个节点所需要进行的操作。 这种方法不但把网络编码构造的复杂度从指数级降到了多项式级，而且有效降低了 网络编码中所采用的字母表的下限。 另外，c f r a g o u l i 给出了在有两个信源情况下严格的基域大小，且认为有两个 信源的组播网络，其网络编码是一个图论的着色问题 8 。 上述方法都是基于已知整个网络的拓扑信息，同时有人又提出了不需网络拓扑 信息的分布式网络编码和随机网络编码。分布式网络编码【9 】的实现，是在网络中传 输的每个数据包上留出一些比特，用来记载此数据包在前面各个节点上所经历的各 种操作，那么接收节点就可以从接收到的数据包中直接译出信源所发送的信息。这 种方法可以在不知网络拓扑信息的情况下实现网络编码，但是增加了网络负载；另 外一种不需网络拓扑信息的方法是随机网络编码 1 0 】【1 l 】，在网络的中间节点上对接 收到的信息，在一个有限域内随机选择一个元素作为组合的系数。研究表明只要有 限域足够大，这种方法的失败率就可以很低。这种方法的缺点是以一定的概率实现 正确无误的传输和需增大通信网络中所需的字母表的大小有关。随机网络编码提出 后，许多研究机构开始把随机网络编码应用于不同的系统中，比如微软的研究人员 就把随机网络编码应用于p 2 p 系统中实现大文件的分发，结果发现相对于传统的存 储转发，随机网络编码所带来的下载增益提高了3 4 倍【1 2 】。 线性网络编码不但可以用在己知拓扑的构造方式中，也可以用在不需网络拓扑 信息的分布式网络编码和随机网络编码中。参考文献 1 3 】推测线性网络编码可以实现 所有的可解网络的网络编码。而参考文献 1 4 】中己经构造了一个特殊的网络，说明了 线性网络编码的局限性，即存在一些网络使用非线性网络编码可以实现最大流最小 割确定的网络容量的上限，但是线性网络编码却无能为力。 随着网络编码在有线网络中研究的深入，许多有无线通信背景的学者开始考虑 北京邮电大学博士学位论文第一章绪论 把网络编码引入到无线通信领域，尤其考虑诸如a dh o c 、s e n s o r 、m e s h 等分 布式网络，随着研究的深入，他们发现应用网络编码，可以解决传统路由、跨层设 计等技术无法解决的问题，提高网络性能。具体来说，网络编码在无线网络中的应 用可以提高网络的吞吐量，尤其是组播吞吐量；可以减少数据包的传播次数，降低 无线发送能耗；采用随机网络编码，即使网络部分节点或链路失效，最终在目的节 点仍然能恢复原始数据，增强网络的容错性和鲁棒性；无需复杂的加密算法，采用 网络编码就可以提高网络的安全性，等等。但同时也发现，在网络编码的理论和应 用方面，无线网络与有线网络有着显著的差别，这主要是由无线网络的结构特征和 无线传输信道的时变衰落特性决定的。与通过电缆或者光纤等可靠媒介形成固定而 独立连接的有线网络不同，无线网络尤其是自组织网络的节点在分布上具有多维空 间上的随机特性，节点之间的连接因受节点移动或节点分布地域的限制，不但具有 时间域上的时变特性而且在空间域上具有相互制约的相关性，在信号传输上受到时 变衰落信道的影响具有时间域上的随机性和不可靠性。所以把网络编码从有线网络 推广到无线网络，用来提高无线网络传输的有效性和可靠性，一个首要的问题就是 对承载传输业务的无线网络的结构特性和传输特性进行深入透彻的认识，即加强对 网络模型的提取和对网络无线传输容量的细致研究。这一研究不但在确立无线网络 传输性能极限上具有重要的理论意义，而且对如何把网络编码应用于无线网络中有 着根本的指导作用。针对上述问题，许多学者从不同的角度进行了研究，下面主要 从无线自组织网络、无线传感器网络、无线m e s h 网络 4 7 】三个不同的分布式网络来 阐述网络编码的研究成果。 无线自组织网络 网络编码与a dh o c 结合已经取得了丰硕的成果。例如，为了解决优化a dh o c 网络吞吐量的问题，j u i l y u a n 等 1 5 】把该问题分解为两个子问题：第一个子问题是优 化网络层的多跳路由问题；第二个子问题是优化物理层能量分配问题。他们提出的 是一种跨层优化的策略，该策略分别在网络层和物理层平衡链路带宽的供需，在这 种平衡状态上，提供了利用网络编码优化吞吐量的流路由方法。与此类似，w u 等 提出了一种中心化的算法 1 6 】，该算法主要是进行递归的跨层优化，在获知物理层状 态的同时，对m a c 层分时调度和网络层最大流指派进行联合优化。x u 等 1 7 通过 联合优化网络编码子图、功率控制机制、拥塞控制机制来得到最小代价问题的最优 解，提出了一种基于节点的分布式的梯度投影算法，此算法通过迭代的方式来调整 局部的控制变量使功率、编码子图、以及拥塞控制参数配置达到最优。 运用网络编码虽然可以在很大程度上提高无线自组织网络的吞吐量，但是不可 避免地会增加网络的复杂性。因此，不少研究者致力于提高a dh o c 网络的组播吞 4 北京邮电大学博士学位论文第一章绪论 吐量，同时降低因采用网络编码带来的复杂性 1 8 ，1 9 】。鼬l g 等从网络编码的角度 把网络链路划分为两类：进入中继节点的链路和进入目的节点的链路 1 8 。他们证 明，在达到同样组播容量的前提下，只需要在进入中继节点的链路进行网络编码即 可。而对进入目的节点的链路，只采用路由策略，降低了网络的复杂性。t r a c e y 等 人主要考虑的是时变的、链路容量受噪声干扰影响的无线网络模型 1 9 】。t r a c e y 在 时变无线网络模型 2 0 】的基础上，使用了动态的压力反馈算法来分别优化网络编码 和路由。结果表明，在网络状况恶劣的条件下，网络编码和路由之间组播吞吐量的 差别并不大，网络编码的优势体现在降低网复杂性上；在网络状况较好的条件下， 网络编码相对于路由方法，能在很大程度上提高组播吞吐量。这就为根据网络状况 动态调整网络编码算法提供了可能。f r a g o u l i 等在文献 2 l 】中通过子树分解，提出了 一种寻找编码节点的算法， 2 2 通过把无线a dh o c 组播网络建模为一个随机图，利 用改进的f o r d f u l k e r s o n 算法得到了无向图中的最大流和需要进行网络编码的节点， 并且通过随机图理论研究了a dh o c 组播网络中编码节点和最大流的统计特性，发现 需要进行网络编码的节点数近似服从贝努力分布，当网络中的节点数趋于无穷大时 需要进行网络编码的节点数近似服从p o i s s o n 分布。 在节能方面，w u 和c h o u 提出了应用网络编码的最小化能量解决方法 2 3 】。最 小化能量组播就是源节点传输信息到目的节点集，使得传输每比特信息消耗的能量 最小。他们比较了路由和网络编码的信息传输耗能情况，指出：如果路由方式是把 无线a dh o c 网络抽象成组播树，树型结构的每条边代表着广播链路的每比特能耗， 那么最小化能耗的组播问题就划归为在组播速率一定的条件下最小化沿着组播树路 径的代价总和的问题，属于n p 难问题。而在采用网络编码的情况下，该问题可以 转化为线性规划的问题，在多项式时间内可解，并且在能耗和计算量上都要优于传 统路由。经过独立的研究工作，l 吼等人也得出了相似的结论【2 4 】。并且，为了在 动态变化和不可靠的网络环境下实现最小化能量的信息组播，和m 6 d a r d 还提 出了非中心化和随机化的网络编码解决方法 2 5 ，2 6 】。 广播通信是a dh o c 网络中一种很普遍的通信方式。在很多路由协议中，网络 大部分节点都需要对全网广播自身的某些信息。用路由的方法实现最小化能量广播 是非常困难的。已经证明，解决最小化能量广播问题的最小权生成树算法是n p 完 全问题 2 7 ，2 8 】。另外，也有人提出采用启发式算法 2 9 来解决这个问题，但是计算 开销和时间消耗都比较大。研究者开始转而利用网络编码来解决广播通信中的能量 有效性问题 3 0 ，3 l ，3 2 。f r a g o u l i 等首先提出了一种针对简单圆形拓扑和矩形拓 扑的网络编码算法 3 0 】，该算法相对于路由方法的精妙之处在于充分利用了无线通 信的广播特性，一次通信就让邻居节点都获得消息，邻居节点同时也获得自身邻居 的数据包并进行编码。这样，经过少数几次广播之后，每个节点都会获得全网节点 北京邮电大学博士学位论文第一章绪论 的信息。这种在简单网络拓扑结构下的广播算法推广到节点随机分布的一般网络中， 仍然取得了很好的效果。然而，不足之处是在网络丢包率较高的情况下( 丢包率大于 o 5 ) ，节点重新广播的概率较大。随后，f r a g u o l i 等又进行了相关的改进工作 3 1 ， 3 2 】 。 为了提高无线网络中的单播通信效率，传统的解决办法有重传、端到端编码( 前 向纠错码f e c ) 、链路编码、路径编码等。现在有研究者提出了网络编码和分布式 流优化结合的方法【3 3 】，这种方法能够在很大程度上提高传输效率，有效地减少重 传次数，增大传送成功概率，从而降低能量消耗。不足之处在于该研究针对的网络 节点数目较少( 1 2 个节点) 。另外，随着网络规模的扩大，该方法不能避免网络数据 包重传次数的增加。 无线传感器网络 相对于a dh o c 网络，无线传感器网络密度较大、移动性不强，通常运行在无 人值守的恶劣甚至危险的远程环境中，能源无法替代。设计有效的策略，延长网络 的生命周期，成为无线传感器网络的核心问题。传感器网络是以数据为中心的，非 常适合采用网络编码技术。 在减少能量消耗方面，s h 狮- s h a i l 等【3 4 提出了一种能量意识( e n e 唱ya w a r e ) 方法 把多径路由和实用的网络编码结合起来，通过这种方法可以减少输送数据所需要的 路径数，从而极大的减少了能量消耗，但是能够得到和传统多径机制同样的可靠性。 这种方法仅需要很小的负载和小规模的线性运算。x i o n g 等 3 6 】提出了一个群集模 型，并基于此模型提出了有效且可实施的网络编码算法和其他算法，当群集中的每 个节点作为信源传递信息到群集中所有其他节点时，网络编码算法和其他算法相比， 可以极大的节省能量和时间。p 咖v i c 等 4 l 】人提出了一种结合网络编码的、对无线 信号不进行调制的策略，他们证明，运用随机分布式网络编码，未经调制的无线信 号能够达到经过调制的无线信号一样的吞吐量，这样就能节省大量因为模拟器件进 行调制而消耗的能量和降低节点的成本。不足之处在于：为了防止未经调制的无线 窄带信号可能使节点之间出现不能互相通信的情况，不得不要求传感器网络保证一 定的节点密度。 在提高鲁棒性方面，z h a n g 等 4 2 提出了一种结合分布式源编码和网络编码的 优化算法，目的是用来提高传感器网络的容错性和可靠性，同时对分布式源编码的 压缩效率和网络鲁棒性进行了折衷考虑。该算法首先提出了节能和鲁棒性的量化模 型，然后提出了可动态调整的链式编码结构。编码链越长，越节省能量，但是可靠 性越低；编码链越短，能耗越大，但是可靠性越高。然而，随着网络规模的扩大， 6 北京邮电大学博士学位论文第一章绪论 该算法的复杂性将呈指数增长，同时该算法主要适用的是静态的传感器网络，未考 虑网络动态变化的情况。对于水下传感器网络，g u 0 等 3 7 证明网络编码对差错恢 复是很有帮助的，比仅在信源节点进行编码时要好很多。l e o n g 等 3 9 】提出了一种随 机网络编码算法：所有节点，除了接收节点，独立选择在有限域上的随机线性映射， 将映射作用于输入数据流上，即得到了输出数据，l e o n g 将该算法与基于在线s t e i n e r 树生成算法、d i j k s t r a 最短路径算法和最近节点优先算法 4 0 】等路由算法进行比较， 结果表明，分布式随机网络编码方法在组播吞吐量和鲁棒性方面要明显优于基于路 由的算法。 在数据采集方面，w a n g 等 3 5 】提出了部分网络编码( p n c ) 作为连续数据采集 的一般工具。p n c 推广了现有的网络编码，能够对传感器节点连续接收到的数据进 行有效的存储替换，而一般的网络编码无法做到这一点，他们证明，除了在存储和 通信时存在一些额外的次线性的负载外，部分网络编码的性能非常接近一般的网络 编码。d i m 抵s 等 4 3 提出了一种数据聚合算法：每个单独的节点只保存一个数据包， 当监听到邻居节点的数据包时，就在有限域上乘一个随机系数并和自身数据相加。 这样，单个普通传感器节点可能不能解码数据，但是对信宿节点来说，就能以很高 的概率通过查询仅仅，z 个节点而重建甩个数据包，使得传感器网络数据聚合的效率得 到极大的提高。 在安全方面， a y d a y 等 3 8 】提出了有位置意识的网络编码安全( l n c s ) 协议，这 个协议能够在采用随机线性网络编码的能量受约束的传感器网络中提供数据机密 性、真实性、可用性。 无线m e s h 网 尽管网络编码已经确立了它在理论上提高网络吞吐量的地位，但是很少有研究 者把目光投向网络编码具体实现这个领域。k a 戗i 等提出的基于机会的网络编码方法 ( c o p e ) 4 4 ，4 5 】则是首次研究网络编码在无线m e s h 网络环境中的协议层面上具体实 现的问题。在c o p e 协议中，每个节点对传输媒体进行侦听，获得它的邻居节点的 状态信息，决定进行编码的机会，并在本地的f i f o 缓存结构内进行编码，然后进行 基于机会的路由。c o p e 协议要求每个节点利用本地信息各自决定哪些数据包需要 进行编码以及如何进行编码。灵活的设计使得即使在网络交通需求未知或者网络流 量剧增、或者发送接收方动态变化的情况下，c o p e 协议仍能有效的支持多路单播 流。然而该协议需要节点存储数据包并进行编码，如果网络出现拥塞，可能就会耗 费较多的节点存储空间。 文件共享是无线m e s h 网的一种典型应用。为了评估网络编码对该应用的影响， 7 北京邮电大学博士学位论文第一章绪论 h a m r a 在理想化m a c 协议基础上开发了特定的仿真平台【4 6 】，分别比较了服务时间 等性能在节点个数、盲转发( b l i n df o 刑a r d i n 曲和选择性转发( s e l e c t i v ef o 刑a r d i n g ) 情况下的表现。实验结果表明，应用网络编码得到的改进，虽然不如在有线网络中 显著，但仍然能在很大程度上提高吞吐量、缩短服务时间。 1 4 论文的主要内容及结构 本论文的工作基本都围绕网络编码展开，首先对网络编码的设计进入了系统深 入的分析，在此基础上，在理论方面以凸优化为工具，对编码分组网络的网络效用 最大化进行了深入的研究。在应用方面，研究了随机网络编码在无线m e s h 网络中对 文件下载成功率或下载时间的影响，以及如何利用网络编码技术在传感器网络实现 连续实时的数据采集。论文包含以下几个部分： 在绪论部分，论文介绍了网络编码提出的背景，网络编码的概念和网络编码的 研究现状。 第二章总结网络编码的设计方面的研究成果。详细介绍了使用于非循环图的线 性网络编码、随机线性网络编码、使用于循环图的带时延的网络编码设计方案，最 后系统描述了实用的网络编码。 第三章研究编码分组网络的网络效用最大化问题。针对单通话( s i n 西es e s s i o n ) 编码分组网络，建模了编码子图给定时的网络效用最大化问题模型，基于此模型， 提出了分布式的梯度投影算法，并证明了算法收敛的充分非必要条件，最后通过仿 真验证了算法的正确性。 第四章研究在离散时间集合中，传输合同约束条件下编码子图给定时编码分组 网络的效用最大化问题，基于提出的优化模型，通过对偶分解，提出了分布式的梯 度投影算法，证明了算法收敛的充分非必要条件，通过仿真验证了算法的正确性。 第五章研究随机网络编码在无线m e s h 网络中进行文件共享时所带来的性能增 益，针对上传受限且m a c 层理想无冲突、m a c 层有冲突、以及节点移动且m a c 层有冲突三种情形，分别通过仿真验证了随机网络编码相对于传统路由所带来的性 能增益。 第六章研究网络编码在传感器网络中实现连续实时数据采集的问题，通过在数 据传感器节点周围放置廉价的存储传感器，让数据收集器通过与部分存储传感器节 点直接通信来实现对特殊环境的实时监控。其中，数据源传感器节点处采用部分网 络编码更新数据，而存储节点则仅对收集到的信息进行随机网络编码后传递给数据 北京邮电大学博士学位论文 第一章绪论 收集器。通过仿真得出了服务器连续成功恢复数据传感器节点数据的概率和数据传 感器节点与存储传感器节点的链路数之间的关系，以及服务器访问的存储传感器节 点的个数和服务器成功连续恢复数据传感器节点数据的概率之间的关系。 最后，对全文进行总结，并指出下一步研究的方向。 1 5 本章参考文献 1 】a h l s w e d er ，c a in ，e ta l ，n e 似o r ki n f o n n a t i o nf l o w ”，i e e et r a n so ni n f o m a t i o n t h e o v 0 1 4 6 ( 4 ) ，2 0 0 0 ，p p 1 2 0 4 1 2 1 6 2 】l isyy e u n grw ，c a in ，“n e a rn e 觚o r kc 0 d i n g ，i e e et r a n so ni n f o 咖a t i o n t h e 0 v 0 1 4 9 ( 2 ) ，2 0 0 3 ，p p 3 7 1 3 8 1 3 k o e t t e rr ，m e d a r dm ，“b e y o n dr o u t i n g ：a 1 1a l g e b r a i ca p p r o a c ht on e m o r kc o d i n g ，i i l p r o c o fi n f o c o m2 0 0 2 ，n e wy o r k ，2 0 0 2 p p 1 2 2 - 1 3 0 4 】k d e t t c rr ，m e d a r dm ，“a na l g e b r a i ca p p r o a c ht on e 觚o r kc o d i n g ，i e e e a c mt r a l l s o nn e t w o d ! ( i n g ，v 0 1 1 1 ，2 0 0 3 ，p p 7 8 2 - 7 9 5 5 】j a g 西sp ，c h o ua ，j a i nk ，“l o wc o m p l e x i t ya l g e b r a i cn e t w o r km u l t i c a s tc o d e s ”， i s i t - 2 0 0 3 ，j 印a i l ，2 0 0 3 ，p p 3 6 8 3 6 8 【6 】s 锄d e r sp ，e 印e rs ，t o l h u i z e nl ，“p o l ”o m i a lt i m ea l g o r i t h m s f o rn e t w o r k i n f - o m a t i o nf l o w ”，i i l15 t ha c ms p a a ，s 锄d i e 9 0 ，c a l i f o m i a ，2 0 0 3 【7 】j a g 舀s ，s a i l d e rp ，c h o wp a m ，e ta 1 ，“p o l y n o m i a lt i m ea l g o t h m sf o rn e t 、) l ，o r kc o d e c o n s t m c t i o n ”，i e e et r a l l so ni l l f o m a t i o nt l l e o v 0 1 51 ( 6 ) ，j u n2 0 0 5 ，p p 19 7 3 10 8 2 8 】f r a g o u l ic ，s o l j a l l i ne ，s h o k r o l l a h ia ，“n e t 、) l ，o r kc o d i n ga sac o l o r i n gp r o b l e m ”，i n p r o c o fc i s s2 0 0 4 ，p r i n c e t o n ，2 0 0 3 9 】c h o wpa ，w uy j a i nk “p r a c t i c a ln e 觚o r kc o d i n g ，i np r o co f4 1s ta n n u a la 1 1 e n o n c o n f e r e n c eo nc o m m u n i c a t i o n ，c o n t r o