（信号与信息处理专业论文）网络编码在ad+hoc网络中的应用研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 2 0 0 0 年，a h l s w e d e 等人基于网络信息流的概念提出了网络编码的思想。通过允许网 络节点进行编码，可以获得网络组播速率的最大流限，即网络资源利用的理论上限，而通 过传统的路由和复制并不一定能够获得该最大流限。此外通过网络编码可以取得节省网络 带宽资源，平衡链路负载，优化能量受限网络的能量消耗等好处。目前，有关网络编码理 论的研究己经引起了学术界的高度重视，网络编码已经成为网络信息理论领域最受瞩目的 研究热点之一。 本文首先介绍了网络编码及研究进展，给出了网络编码的基本原理和相关的算法，讨 论了网络编码与组播融合的优势，以及网络编码在降低能耗方面的应用；最后研究了网络编 码在a dh o c 网络中的实际应用。在研究中，对于a dh o c 网络中最大流路径的建立，采用 f o r d f u l k e r s o n 算法来实现，并在原来的f o r d f u l k e r s o n 算法基础上做了改进：在对已标未 查端的邻端进行检查时，取消了对有向边的判断，这样在无向图中也能找到最大流。本文 还对随机方式的编码策略进行分析研究，并对编码节点进行了分配选择，大大减少了系统 开销。最后，在所研究算法的基础上进行仿真，仿真结果表明网络编码可以显著提高网络 的性能。 关键词：网络编码，a dh o c ，组播，f o r d f u l k e r s o n 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t n e t w o r kc o d i n gw a 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 nt h ec o n c e p t i o no f n e t w o r ki n f o r m a t i o nf l o w i fc o d i n gi sp e r m i r e db yt h en e t w o r kn o d e ，t h em a x - f l o wb o u n do f n e t w o r km u l t i c a s tc a l lb ea c h i e v e d ，h o w e v e ri tc a nn o ta 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 g a n dr o u t i n g f u r t h e r m o r e ，t h r o u g hn e t w o r kc 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 n b a n d w i d t h , l o a db a l a n c i n g ，o p t i m i z i n gt h ee n e r g yc o n s u m p t i o no fe n e r g y - l i m i t e dn e t w o r k sa n d s oo n n o w , t h er e s e a r c ho fn e t w o r kc o d 访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 sb e c o m eo n eo f t 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 o r m a t i o nt h e o r y t h i st h e s i si n t r o d u c e st h ec o n c e p t i o na n dt h er e s e a r c hp r o g r e s so fn e t w o r kc o d i n g a f t e r i n t r o d u c i n gt h ef u n d a m e n t a lt h e o r ya n dr e l a t i v ea l g o r i t h m s ，w es u m m a r i z et h ea d v a n t a g e so f n e t w o r kc o d i n gi nn e t w o r km u l f i c a s ta n de n e r g ys a v i n g t h e n ，w ed i s c u s st h ep r a c t i c a lu s eo f n e t w o r kc o d i n gi na dh o en e t w o r ka n da p p l yt h em o d i f i e df o r d - f u l k e r s o na l g o r i t h mt ot h e m a x f l o wr o u t i n g ，t h e nw ec a l lo b t a i nt h em a x i m u mf l o wi nu n d i r e c t e dg r a p h ，w ea n a l y z et h e r a n d o mc o d i n g ，c h o o s ew h i c hn o d e sn e e dc o d i n g a tl a s t ，w ec o m p l e t et h es i m u l a t i o na n dv e r i f y t h ea d v a n t a g e so fn e t w o r kc o d i n g k e y w o r d s ：n e t w o r kc o d i n g ， a dh o c ，m u l t i c a s t ，f o r d - f u l k e r s o n i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：量盘地日期：翟堕：全：! 1 7 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：逸盏) 逸导师签名 南京邮i 乜人学硕l ：研究生学位论文 第一章绪论 第一章绪论 1 1 网络编码的提出和发展现状 随着信息时代的不断发展，各种通信网络与人们工作生活的各个方面结合得越来越紧 密。与此同时，由于用户数量的激增，网络服务的多样化以及针对网络传输质量要求的不 断提高，如何提高现有网络资源的利用率，优化网络，己成为当今网络通信研究的重要课 题之一。传统的网络组播方式是在网络中寻找一棵有效的组播树，这种方式下网络节点只 对数据分组进行路由或复制。这样很难达到网络组播的最大传播容量。从信息论的观点讲， 我们没有必要对网络节点的功能加以限制。 2 0 0 0 年，香港中文大学的r a h l s w e d e 等人在i e e e 上发表了一篇题为“网络信息流 的 文章，这篇文章为我们提高网络的传输容量指明了一个新的发展方向，他们从信息论的角 度出发，严格证明了：网络编码可以帮助我们达到通信网络的最大容量，从而最大限度的 利用网络的现有资源。网络编码的提出从本质上打破了通信网络中传统的信息处理方式， 它现在已是通信网络研究领域中的一个新的研究热点。 像很多基本的概念一样，网络编码也是基于一个很简单的思想。网络编码是指在组播 通信网络中，可以在网络的中间节点上对接收到的信息进行一定形式的编码处理，然后再 传输出去，而不是像传统通信网络中那样在中间节点上只是进行存储转发，然后再在信宿 节点上，通过一定的处理方式，译出信源所发的信息。 一个通信网络可以用有向图来表示，根据图论中的最小割最大流定理可知，一个网络 可以传输的最大流量等于其最小割。但传统的存储转发式路由方式，并不能实现网络的最 大流传输，所以它并不是最佳的，而如果使用网络编码的话，即在网络的中间节点上，对 其接收到的信息允许先进行编码后再传输出去；在接收端，目的节点再根据自己的要求译出 所需的信息，则可以大大提高网络的传输速率，充分利用网络中的链路资源，从而实现最 小割最大流定理给定的可传输信息的上限。严格的讲，其实传统的路由方式是网络编码的 一种特殊形式。 南京邮电大学硕士研究生学位论文 第一章绪论 ( b ) 图1 1网络编码原理图 我们考虑一个无差错的传输系统。通信网络如图1 1 ( b ) 所示，这是一个组播网络，不 考虑时延和传输差错。其中s 是源节点，和乃是目的节点，每条边的信息速率均为每单位 时间1 比特。从图中我们可以看出，为了从信源节点s 同时传输两比特信息a 、b 到目的节点， 则在中间节点3 处，必须通过网络编码，使输出边( 3 ，4 ) 传输两个输入边上携带信息的线性组 合口ob ，那么在目的节点和处，才可分别由口0 6 和a ，口ob 和b ，恢复出所有信息b 、 a 。如果按传统路由方式，在一个单位时间内将无法完成以上传输。 网络编码不但可以用在组播通信网络中，而且还可以用在非组播网络中以提高网络容 量。另一方面，网络编码在提高网络的通信容量的同时，在负载均衡、降低能量消耗等方 面也有不容忽视的作用。 1 2 网络编码研究现状 前期网络编码研究的背景主要是基于有线网络的，逐步深入的研究展示了网络编码 扩展到无线网络中的广阔前景。但是在网络编码的理论和应用方面，无线自组织网络与有 线网络有着显著的差别，这主要是由无线自组织网络的结构特征和无线传输信道的时变衰 落特性决定的。与通过电缆或者光纤等可靠媒介形成固定而独立连接的有线网络不同，无 线自组织网络的节点在分布上具有多维空间上的随机特性，节点之间的连接因受节点移动 或节点分布地域的限制，不但具有时间域上的时变特性而且在空间域上具有相互制约的相 关性，在信号传输上受到时变衰落信道的影响具有时间域上的随机性和不可靠性。所以把 网络编码从有线网络推广到无线自组织网络，用来提高无线网络传输的有效性和可靠性， 一个首要的问题就是对承载传输业务的无线自组织网络的结构特性和传输特性进行深入 透彻的认识，即加强对网络模型的提取和对网络无线传输容量的细致研究。这一研究不但 在确立无线网络传输性能极限上具有重要的理论意义，而且对如何把网络编码应用于无线 2 南京邮l u 人学硕 ：研究生学位论文 第一章绪论 网络中有着根本的指导作用。 目前，网络编码是国际信息论和网络理论领域所关注的热点，相关的研究人员如 m e d a r d 、e f f r o 和y e u n g 等人已经在建立网络编码的数学描述方法等方面作了大量的工作， 得到了有线网络中利用网络编码实现最大流传输的若干判定定理。然而，他们的工作主要 是集中在具有固定拓扑结构和容量的有线网络上，对网络编码在无线网络中的应用涉及得 较少。由于有线网络中的带宽资源相对丰富，并且超高速传输对于处理的复杂度限制较低。 而对于无线自组织网络，原有的关于有线网络的固定特性也不适于在任意端到端之间构造 相应的网络编码，难于适合网络拓扑的变化。因此网络编码在无线网络中的应用还面临着 很多独特的问题。关于网络编码的复杂度，k o e t t o r 在文献【4 9 】中证明，应用他们的算法， 所用编码系数的符号集大大小于l o g ，( m h + 1 ) 。其中h 是广播的流量，m 是接收点的数目。 f r a g o u l i l 5 0 j 将其缩小到2 历一7 4 + l 2 。 在文献 5 1 】中，作者系统地研究了网络编码的线性可解性和符号集大小的关系，并指 出在某个符号集上有解的广播网络编码，在更大的符号集上未必可解。在一个广播会话中， 不是所有的中继节点都要对输入信息进行编码处理，只需在必须编码的节点处进行即可。 这些必须编码的节点叫做编码节点，在编码节点处编码后的信息输出的链路叫做编码边。 在文献 5 2 】中，l a n g b e r g 等人给出了一个广播网络中编码边数的上界和下界。不幸的是， 他们还证明了确定编码边数的最小值是个非线性编程硬( n p h a r d ) i 口- j 题。这表明，在目前 任何寻找编码节点和编码边的有效算法都只能是近似的。尽管如此，选择性的编码比在所 有节点都进行编码的方法系统丌销还是要小得多。f r a g o u l i 5 0 】提出了一种子树分解算法来 寻找编码节点。在算法设计上，形成了两个极端。一种是完全确定的编码方案。k o e t t o r 【4 9 】 提出了较为完备的线性网络编码的代数实现。但是他们的方法运算量太高。确定性的编码 方案能够保证容许性，并且所需的符号集比较小。但是确定性的网络编码需要了解全网的 情况，复杂度比较高，难于分布式的实现。一旦网络拓扑结构发生了变化，就必须对整个 编码方案进行修改，所以鲁棒性比较差。由于确定性网络编码的以上缺点，后来提出了随 机编码 3 9 i 的概念。随机编码是指每个节点随机地选取一组编码向量，对输入信息进行编码， 并把这组随机向量作为报头的一部分发送给收点，以便于解码。随机编码可以分布式地实 现，并且可以增加保密性。随机编码可以解决分布式实现的问题，但是可能造成系统传输 矩阵奇异，导致在收点无法恢复出原始数据。可以证明，当符号集为无穷大时，采用随机 编码，系统传输矩阵满秩的概率为“1 。其余的算法基本上都是以上两个极端的折衷， 例如可以采用半随机的编码方案。整个网络被化分成若干区域，各区域都采用随机编码， 但为了保证传输矩阵满秩，区域间要相互传递信息，以使每个区域在选择编码向量时尽量 南京邮电大学硕士r 4 f 究生学位论文第一章绪论 不选可能导致解码失败的那些向量。为了保证随机编码成功概率，编码向量的符号集必须 足够大，这可能增加数据包头部的负担，因此符号集的大小必须仔细选择。 此外，还有一些研究人员利用网络编码的思想提出了一些方案，以达到与最大流类似 的最小费用、最低能量传输等网络优化目标。对等网络( p 2 p ) 网络中，网络编码策略可以降 低下载时间，在大规模的分配式p 2 p 网络中，全局的调度非常复杂，而应用网络编码后， 可以采用很简单的机制来构造随机的网络架构，提高系统性能，同时由于已编码文件块的 密集性，基于网络编码的解决方案健壮性更强，例如当某种子节点过早离开时，编码机制 的应用使网络信息块平等，从而可以降低信息丢失的情况。在增大流量上，利用网络编码 可以达到理论上限，可以应用于带宽有限的无线网络，利用其节点信息可以被周围邻居检 测接收的特点。如图1 2 所示，无线网络中当两个无线节点需要通过一个共同的基站来进行 通信时，网络编码可以提高双向业务的网络流量，将结论推广到无线网络中的多跳路由中， 两个终端节点的业务是双向的，且拥有相同的包要交换，在相邻路由器间应用轮询的时间 调度，通过最初几步后，所有的中间节点都存储了要向两个方向传送的数据，当有传送机 会时，路由器将要向两个方向传送的数据编码，传送出去，从而充分利用无线传输的特点： 而对于接收节点，可以通过相应译码得到所需信息，信道的流量增加了一倍。网络编码还 可以在组播、广播场景中应用，于是可以用于无线格状i 网( m e s h ) 、自组织( a dh o c ) 网络及 无线传感器等多跳网络中。 a 三一s b a s 一! b n a a s 一b + b s b 一b s s 奠一s b a b ( a ) 传统方式( b ) 采用网络编码方式 图1 2无线信息交换方式 网络编码机制使信息更加分散，等同于将信息进行了隐藏，更难窃听，提高了信息 安全性。节点需要具有译码功能，同时要求得到足够的数据才能正确解码，信息很难被窃 听，同时网络编码还可以防止拥塞方面的侵害，因此，将网络编码技术应用于军事等领域， 其保密性和鲁棒性方面的潜力很大。 为了不对现有网络的软硬件设备和相应的协议做很大的修改，可以选择在更高层实现 网络编码。基于组播覆盖网络节点功能更强、拓扑结构易构建的特点，应用简单的编码策 南京邮电大学硕士研究生学位论文第一章绪论 略就可以提高网络容量和降低信息传输时延。基于这种思想，可以考虑在无线传感器网络， 无线m e s h 网络中应用网络编码，有效降低成本。 1 3 网络编码的研究热点 作为一种新型的网络传输技术，网络编码的优点不言而喻。但到目前为止，对这一领 域的研究还主要集中在理论方面以及应用局限性的分析方面。 1 3 1 网络编码节点选取方案 在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编 译码的节点，给予编译码功能，对于不需要编译码的节点，只要具有传统的存储转发功能 即可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码 的应用更为广泛。文献【5 3 】根据网络拓扑结构，利用一种子树分解算法来寻找编码节点。 将该算法应用于有线网络中并使用确定的网络编码机制，效果较好；但对于无线网络，节 点之间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导 致拓扑结构更为紧密，则应用上述方法选择编码节点就不太适合。因此，无线网络中主要 考虑节点能量及稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较 高、具有较强的运算速度和较大的缓存空间的节点，以提高网络的鲁棒性。 1 3 2 网络编码算法的设计 目前网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构架 上，这些方案主要是基于理论上的分析和实现，因此在实际网络上需要针对不同的应用设 计相应的编码方式：如对于结构较小的网络，可以选择比较简单的确定性算法，编码过程 中甚至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度；而对于 无线网络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对 节点所有的可用信息应用线性编码，并随时更新编码系数，文献【5 】已经证明，当符号集为 无穷大时，采用随机编码，系数传输矩阵满秩的概率是“l ”，即编码成功的概率很大， 但同时会增大数据报头的负担，因此符号集的大小需要权衡各种因素。 1 3 3 网络编码复杂度的分析 网络节点编码过程中会涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接 5 南京邮电火学硕士研究生学位论文第一荦绪论 收节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块 大小共同决定了编码符号集的最低门限。对于确定性编码而言，所需的符号集可以较小， 编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多 应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码 算法从而降低网络的复杂度；对于随机网络编码而言，所需的符号集较大，而且节点在传 送信息的同时传送系数向量，虽然系数向量相对于信息而言较小，但同样会占用较大的带 宽，因此需要设计合适的算法，保证在提高编码增益的同时降低复杂度。网络编码复杂度 要受到符号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面分析得 出。 1 3 4 网络编码的性能分析和应用 网络编码机制可以提高网络容量。已经证明应用网络编码，可以达到香农极限。网络 编码通过编码节点对输入信息线性或非线性的编码处理，可以在不提高消耗带宽的情况 下，使不同的信息同时通过有限的链路，从而提高网络流量。对于无线网络中的网络编码 性能进行分析则需要应用网络信息论的知识，建立合适的网络容量模型来进行容量分析。 网络编码导致编解码【2 i 】的过程中可能会产生编译码错误，这将增大网络数据传输的误码 率。而就网络编码本身而言，对误码率有着相当苛刻的要求，只有较小的误码率才能保证 网络编码的有效性和可靠性，否则使用网络编码可能还会带来系统整体性能的降低。因此， 如何设计可靠的网络编码方案【2 】以保证数据传输较低的误码率，并尽可能地采用相应技术 减少误码率对网络编码方案的影响是网络编码研究所必需的。 1 3 5网络编码系统安全性分析 网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络的安全性能产生影 响。一方面，由网络编码导致的信息的分散性和编译码特性增加了信息破译难度，对安全 性而言是一种改善；另一方面，对确定性编码算法而言，由于传输过程中将涉及较多的节 点数目，以及编码算法方案的确定性，会导致系统的安全性能的降低。因此编码算法的设 计中也需要考虑系统的安全性能1 2 6 】，通过对不同的编码算法进行恰当的安全性能分析，来 确定不同网络算法对系统安全性的影响，从而针对不同的系统应用选用合适的编码算法， 以提高网络安全性能，这对于无线通信具有重要意义。 6 南京邮电大学硕士研究生学位论文 第一章绪论 1 3 6 网络编码在无线分布式网络中的应用 对网络编码技术的研究需要在加深理论研究的同时，考虑实际的应用场景，侧重解决 实际应用中遇到的问题，比如需要降低编码复杂度，需要考虑系统本身的延时以及网络编 码带来的延时影响等。网络编码在无线通信网络 3 5 1 当中的应用是一片亟待开发的热土，一 方面无线网络的广播特性非常利于网络编码的应用；另一方面，相对于有线网络而言，无 线网络中的节点不可能同时监听来自多个源的信息，对网络编码的应用造成了一定的阻 碍。如何结合无线分布式网络的特点扬长避短，找到能够最大程度发挥网络编码优势的结 合点，是需要考虑的主要问题。 1 4 论文内容及安排 网络编码的思想突破了通信网络中信息传输的固有模式，将编码的概念引入到网络传 输中，其研究也涉及信息与通信学科的多个领域。本文在研究网络编码的基础上，特别研 究了网络编码与多播技术的融合，并做了仿真研究。 本文共分六章，其余几章的安排如下： 第二章对网络编码进行了介绍，包括网络编码的网络模型，数学描述以及在组播中实 现最大流的可行性证明，最后分别介绍了实现网络编码的代数方法和多项式时阳j 算法。 第三章讨论了网络编码在无线组播网络中的应用，首先介绍了无线组播网络的特性， 然后介绍了网络编码的构造，使用网络编码的最小能量组播以及网络编码中的信息交换。 第四章主要是对原有的f o r d f u l k e r s o n 算法进行了改造，使之能在无向图中使用，并且 对网络中需要编码的节点进行了选择，最后介绍了本文采用的编码方案。 第五章主要进行了性能仿真以及对仿真结果的分析。 第六章总结了全文，并指出了今后有待进一步深入研究的一些问题。 7 南京邮电人学硕：j j 研究生学位论文第二隶网络编码幕础 第二章网络编码基础 本章首先介绍网络编码的基础知识，主要介绍网络编码的网络模型、数学描述以及网 络编码在组播中实现最大流的可行性证明，最后着重分析了线性网络编码的各种方法。 2 1 网络编码基本概念 传统上，通信网络中的信息流被认为是网络管道中的流体，就好像是水在渠道中流动 一样，一个渠道中可以通过的水量受到渠道的横截面积的影响。所以，具有单位信道容量 的边不能同时被多于一个的单位信息速率的信源使用。然而，实际上，通信网络中传输的 信息是一系列的比特串，这就与像水那样的媒质有着本质的区别，所以我们可以对在某条 边上传输的信息进行处理，即进行网络编码。下面首先介绍网络编码的网络模型。 2 1 1 网络模型 一个通信网络可以用有向图6 ( v ，e ) 来表示，其中v 代表节点集，e v xv 代表边 集。考虑组播情况，用scv 来表示通信网络中的信源，集合tcv 表示目的节点的集合。 网络中的节点可以分为源节点、中间节点、目的节点( 有时一个节点会充当多种角色，比如 说既是中间节点又是源节点) 。我们用( 1 ，1 ，) 来表示节点1 ，到节点，的边，即( 1 ，v 。) e ；边 e = ( v ，v 。) 的头为v 。= 办( e ) ，其尾为v = t ( e ) ， f ，( 1 ，) 表示节点y v 的输入边的集合；t 。( v ) 表 示节点v v 的输出边的集合。 某个信源节点v 产生的信息空间为q ( v ) = x ( v ，1 ) ，x ( v ，2 ) ，x ( v ，4 v ) ) ) ，它是由( v ) 个 离散独立的随机过程组成的，其中每个离散随机过程均取自有限域只。，所以节点v 的熵 正，( v ) 为 = h ( x ( v ，f ) ) = m 4 v ) 。 目的节点1 ，所收到的信息空间 ，= i 甲( v ) = z ( v ，1 ) ，z ( v ，2 ) ，z ( v ，7 7 ( v ) ) ) ，它是由q ( v ) 个离散随机过程组成。在一个通信网络中， 可以用( v ，v ，q ( v ，1 ，) ) 来表示节点，和节点v 之间的通信，它们之间所需传输的信息是 q ( v ，v ) 。节点v 可以通过从其出发的边e ( v ，v ) 来传输信息，我们用随机过程，( p ) 来表示。 边上所传输的随机过程的取值范围是有限域只。 本文所讨论的通信网络都满足以下基本假设： ( 1 ) 有向图g 中的任意一条边的容量均为常数，比如说一比特每单位时间。这种假设可 r 南京邮l u 人学颂l ：研究生学位论义 第二荦嘲络编码幂础 以达到任意的精度。如果某条边上的容量超过了一比特每单位时间，则我们用并行边来表 示，每条边的容量还是一比特每单位时间。我们可以通过选择足够大的时间单位来精确的 表示边上的容量为分数的情况。 ( 2 ) 通信网络中的任意链路上都有相同的时延。在这里，我们假定所有链路的时延均为 o ，也就是不考虑网络的时延。 ( 3 ) 为了简化问题的表示与描述，我们假定网络中没有环路存在。 ( 4 ) 不考虑通信网络中链路上的传输差错，这是因为网络编码是网络中网络层的操作。 在网络的七层模型中，差错控制可以由底层完成，而提供给网络层的是一个没有差错的系 统。 ( 5 ) 信源产生的随机过程x ( v ，z ) ，z 1 ，2 ，( v ) ) 是相互独立的，并且有相同的整数熵， 不如说一比特每单位时间，而且不同节点产生的随机过程也是彼此独立的。 2 1 2 网络编码的数学描述 在第一章中，我们已经用一个简单的例子说明了网络编码的基本原理，在这里，我们 给出网络编码的抽象数学描述。网络编码不同于传统路由之处就在于在各个中间节点上的 信息处理方式，下面定义各边上的函数映射。对边集e 中的每条边p ( v ，v ) ，存在一种映射： z ：兀互。一。 pe 厂，( v ) 这是对应于每条边的编码函数，它把某个节点所有输入边上的信息映射成其某个输出边上 将传输的信息。目的节点v 为了得到所需信息，对v z ( v ，f ) w ( v ) ， g 吖：兀t ，专乞 f 乍n ( v ) 映射g 。是对应与目的节点v 的第i 个所需信息的译码函数，它从此目的节点输入边上所传 输的信息中恢复出所需信息。如果存在编码函数z 和译码函数毋i ，使q ( 1 ，v 。) c 甲( ，) ，则 称通信网络( v ，v ，n ( v ，v ) ) 是可解的，同时称编码函数工和译码函数邑，是此网络的一组解。 2 1 3 网络编码可以实现网络最大流的可行性证明 在这一部分，我们介绍一种广义的网络编码方案一口一码，并给出一个重要的结论： 网络编码可以实现多播网络的最大容量。设有向图g ( 矿，e ) 中，信源为s ，信宿为，以， 在边( f ，) e 上的容量为r i ，。因为我们所关心的是信源到信宿的最大流，所以，不失一般 9 南京邮电大学硕士研究生学位论文第二章网络编码皋础 性，我们假定图中没有从其他节点流入信源s 的边，也不存在( f ，f ) e 。 我们考虑一个码长为n 的分组码。x 的取值x 取自于均匀分布的集合q 中，集合q 中的 元素称为信息。对于边( f ，) e ，节点f 发送给节点的信息仅仅依赖于节点f 以前接收到 的信息。下面我们定义一类分组码，口码。 图g 上的一个 ，z ，( r u ，( f ，j ) e ) ，h 口- 码的定义包含以下要素： ( 1 ) 一个正整数k ； ( 2 ) u ： 1 ，k ) 专v ，v ： 1 ，k ) 专v ， 使得 ( 尼) ，v ( 七) ) e ； ( 3 ) 4 = l ，1 4 i ) ，( 1 4 l l ，1 k k ) ， 使得兀1 4 i = ， k e 7 ； 此处乙= 1 七k ：( “( 七) ，v ( 尼) ) = ( f ，肼。 ( 4 ) 如果u ( k ) = j ，那么五：q j 4 ， 否则：六：兀4 ，j4 ， g 其中q = l ，2 曲i ) ，o k = 1 k 0 ，存在一个 足够大的n 和图g 上的 ，z ，( 仍，( f ，) e ) ，h s ) 口- 码，使得对于所有的边( f ，) e 均满足： ，z l 0 9 2 心+ ( 2 1 - 1 ) 则称图g 上的三维向量( 瓦厅，g ) 是可达的。这里刀l o g ：r u 是编码后链路( i ，j ) 上的平均比特 速率。 2 r h “= 夏：( 尺，h ，g ) 是口一可达的 。 3 有向图g = ( v ，e ) 中，信源为s ，信宿f 1 ，t l ，边( i ，j ) 上的容量为r o ，则 g = r ：从s 到，f u = 1 ，三) 的最大流h 。 4 r “= ，“。 ( 2 1 - 2 ) 证明：首先，证明心，g = ，6 。也就是如果对任意的占 o ，则存在一个足够大的甩，使得 图g _ k o o n ，( ，( f ，歹) e ) ，乃一占) 口一码，对于所有的边( f ，) e 均满足刀l 0 9 2r 0 如+ 占的 话，则从s 到，= 1 ，的最大流大于等于h 。 取1 ，l 和bc l 使得s b 且萑b 。令 = ( f ，) e ；i b 且：，仨b ) ( 2 1 3 ) k ( x ) = ( 五( 工) ，七岵毛) ( 2 - 1 4 ) 其中x eq ，a ( x ) 代表函数l ( x ) 的以x 为自变量时的取值。w ( x ) 指信宿f ，在编码阶段所 收到的关于消息x 的所有信息。根据前面对口- 码的定义，以( z ) 是节点( 尼) 上前面所收到 的信息的函数，所以，是万( x ) ，k eu 乃的函数。因为节点f 上可以接收到信息x ，所 ( ，) 以有： 何( x ) = 日( m ( x ) )( 2 - 1 5 ) = 日( 以( x ) ，k u 乙) ( 2 - 1 _ 6 ) 日( 万( x ) ) ( 2 一i 一7 ) ( ，) 拈弓 l o g ： ( 2 - 1 - 8 ) ( ，。，) e b = l o g ：( 丌1 4 f ) ( ，, j ) e i i e 女巧 ( 2 1 - 9 ) 南京邮i u 人学倾i ：研究生学位论文 第_ 二章网络编码皋础 = l o g ：( ) ( i , j ) e e b 因此， 办一占n - 1 日( x ) 甩l 0 9 2 ( ，) e e n ( 2 - l - 1 0 ) ( 2 1 11 ) ( 气+ 占) ( 2 - l - 1 2 ) ( ，j ) $ e b 局+ i e i 占 ( 2 - l 1 3 ) ( f ，) e 在集合b 的所有可能取值范围内最小化上式的右边，得到 h - e _ 艿的最小值： 2 ) 在t ，中找到一个口，使得f ( 岛善2 ，己) i 爵= 口0n - 令- f 卜f ( 卣磊，磊) i 白呻： 3 ) 如果f = 甩则停止，否则，卜t + 1 ，返回到2 ) 。 输出：( a 1 口2 ，口。) 。 有了此算法就可以找出一个点( ，口啊，危，一，占，) 使 f ( ，口。，尾一，占， ) 0 。算法中给出了网络编码可解时有限域大小的一个上界，即 当域的大小大于等于2 时该网络的网络编码是一定有解的。 定理：对于一个单源多播网络g ，有n 个接收节点。用f 表示n 个子矩阵m 矿m ，2 ，m “行 列式之积且假设万是f 中关于任意变量f 的最高次幂，则在域只，中存在该网络的网络编码 有解，这儿的i 取满足2 万的最小值。算法2 1 给出了求解的方法。 推论：在一个零延迟可解多播传输网络g 中，有一个源节点和n 个接收节点，令其传输速率 为r ，则在有限域c ，( 肌il 0 9 2 ( n r + 1 ) 中网络编码有解。给出了网络的上述代数描述后， 可以得到下面的重要定理： 给定一个线性网络，下面的三个命题是等价的： 1 ) 一个点到点的传输( v ，v ，q ( y ，v ) ) 是可解的。 2 ) 可以达到图g 上由最小割最大流定理得到的容量限。 3 ) 系统转移矩阵m 的行列式在环e 1 ，口，以，e f t j , - j 上非零。 只要根据约束条件：系统转移矩阵的行列式不为0 ，确定出上式中的满足条件的变量， 也就是得到了局部编码向量，就完成了这个通信网络的线性网络编码。 南京邮电大学硕士研究生学位论文 第二章网络编码皋础 2 2 3 多项式时间算法 文献 3 0 】 3 1 从线性子空间的角度提出了一种多项式时间算法，比之前面的算法，这种 方法降低了算法复杂度，更加有效。 对于一个单位容量的多播网络g = ( v ，e ) ，信源为s ，t 为接收节点的集合，设其最大 大多播容量为h 。引入一个虚拟源j ，并引入从j 到s 的h 条并行边，用e ，e ：，e 。表示。 假设这h 条并行边传输的符号分别为q ，盯：，表示，即信源输出信息向量的h 个分量。 为了叙述方便，下面重新定义一下需要用到的符号，用长度为i f j ( s t a r t ( e ) l 的m 。来表示前述 的局部编码向量口“，厦，p ，c e 。，用万( p ) 表示全局编码向量v e ( e ) 。所以有： 】，( p ) = 坍。( p ) y ( p ) ( 2 2 - 18 ) p e n ( s t a r t ( e ) ) 其中棚。：r , ( s t a r t ( e ) ) 专f i n 删圳。 对e e ，有 万( p ) = m 。( p ) 万( p ) ( 2 - 2 - 1 9 ) p e l ( 肌州( p ) ) 其中万( p ) f 6 ，b - ( p ) = 0 i - il ，0 】。 可得： 】，( p ) = a g 7 ) = 仃l ，盯2 ，】万7 0 ) ( 2 2 2 0 ) 当且仅当对所有的f t ，向量集 万( p ) ：p r ，( ，) ) 可以张成向量空间f “时，可以实现源s 到终端t 多播的线性网络编码的实现。终端节点可以通过解h 个变量的线性方程组来重建原 始信息。算法的目的是在一个小的有限域上快速有效的选取局部编码向量，从而降低时间 复杂度。 初始时刻，对任一接收节点t t ，计算s t 之间大小为h 的流厂，并将这些流分解成从s 到t 的h 条互不重合的路径。如果某条边e 在s 到t 的路径w 上，用足( p ) 表示边e 在路径w 上的 前一条边。按信息流的顺序对节点u v 进行排序，这样可保证当确定了节点u 的输出边的 局部编码向量时，其所有输入边的全局编码向量是已知的。算法每次确定一个边e l ( 材) 的系数m 。令丁( p ) 表示通过边e 的流厂对应的接收节点的集合，尸( p ) = 足( p ) ：t 7 ( e ) ) 表 示穿过边e 的路径中边e 的前一条边的集合，对相对应集合尸( p ) 中的边的系数m 。选取非零 值。对每一接收节点，t 维持一个具有h 条边的集合c ，使得全局编码向量 e = 万( c ) ：c c ，) 张成线性向量空间f 6 ，即通过集合c ，中的边所携带的信息可以重建原 l q 南京邮电大学硕士研究生学位论文 第二章网络编码基础 始的输入信息。集合c ，中边的全局编码向量按拓扑顺序逐一更新。这样，当计算结束时根 据接收节点的输入边集合c ，f i ( f ) 可以解出所有的信息。 算法中关键是如何确定系数m 。以保持不变性，使其对应的全局编码向量线性无关，从 而对所有的r 丁( p ) ，新的e = 万( c ) ：c c f ) 是f 6 的一个基。 下面给出快速检测向量i 是否线性独立于另外n 1 维向量空间的一种方法。 假定b 表示f 6 的一组基且万b 。如果向量万f 6 满足v 万b ：万万= 磊石，( 皖，。意思 为：如果a - b ，则皖。= 1 ，否则皖。= 0 ) ，即向量万线性独立于向量空间b 万 ，则任何 向量i f 6 独立于b b 当且仅当i 万0 。 证明：令i = 矶占x ( b 一) 万，即可用基b 唯一表示。那么有 i a 一= “占x ( b 一) 弘万= “b x ( 万) 磊尹= x ( 万) 。 因此，i 不在向量空间b 万) 里当且仅当x ( 万) 0 。 由此，对所有f t ( e ) ，可以给c f 中的每条边e c f 对应于一个向量a t ( c ) ，于是可用 该向量来判断一个向量是否线性独立于b t 万( c ) ) 。因此逐条边求解全局编码向量的过程 中，不变性等价于 v t t ：ic f i = h 和v c ，c c ，：6 ( c ) 瓦( c ) = 皖 ( 2 - 2 2 1 ) 总共有p ( e ) 条边的信息汇合到边e ，如果是随机选择这些系数，则满足不变性的概率是 1 l f i ，即： 对任意一条p e 和，丁( p ) ，假定包含万( 足( p ) ) 的e 是f 6 的一组基，则当随机选择 系数所。时，( e 万( 足( p ) ) ) ) u 万( p ) ) 不是f 6 的一组基的概率为1 吲。其中 阳= p e p ( e ) 册。( p 万( 列。 随机选择系数m ，时，对所有接收节点而言，其所选参数不满足不变性、即失败的概率 至多为t l i f i 。当j f | 2j t l 时，失败的概率至多为1 2 。但是这个失败概率太大，因此当i f i 比较小时，随机选择系数这种方案并不可行，有必要找出一种更为有效的方法。 2 3 本章小结 本章给出了网络编码的基本概念，对网络编码的网络模型、数学描述以及网络编码实 现多播网络最大流的可行性进行了证明，最后从两个方面介绍了实现网络编码的可行算 2 0 南京邮i 【1 人学硕i 1 i # f = l 生学位论义第二章嘲络编码暴础 法，通过比较可以看出，使用代数方法实现网络编码，需要知道整个网络的拓扑信息情况， 通过构造符合要求的系统转移矩阵来实现网络编码，运算量非常大，而多项式时间算法是 由线性子空间的角度提出的，和代数方法相比较，降低了算法复杂度，也更加有效。 南京邮电大学硕j 研究生学位论文 第三章无线组播中的i | ) 4 络编码研究 第三章无线组播中的网络编码研究 前面一章我们介绍了网络编码的基本概念和两种可行算法，本章我们将讨论在无线组 播环境下网络编码的研究，首先介绍了无线网络中特有的无线组播特性；接着讨论了结合无 线组播特性和网络编码实现的最小能量组播方法：最后给出了这种方法的一个应用特例一 通信网络中信息互换中的网络编码应用。 3 1 无线组播特性 3 1 1 无线组播特性w m a 我们考虑一个无线组播网络，网络的连通性取决于各个节点的发射能量。我们假定每 个节点可以自由选择它的发射能量值，但其值不可超过，接收能量值随，叫变化，其 中，是接收节点距离发射节点的距离，口为取值在2 和4 之间参数，具体取值取决于网络 的通信介质的特性。所以，相距为，的两个节点之间建立链路所需的发射能量正比于厂一， 不失一般性，我们归一化能量值为l 。由此可得， 只，节点i 和节点j 之间建立链路所需的能量= ，呻 ( 3 1 1 ) 如果一个无线通信网络的最大允许发射能量足够大，那么节点就可以以足够大的能量 值发射，以使整个通信网络是全连通的。 我们假设用的是全向天线，因此在一个发射节点通信范围内的所有节点均可以收到其 发射的信息。下面就举例说明无线通信中的广播特性在组播中应用的重要性。如图3 一l 所 示，无线通信网络中节点i 要同时向其邻居节点j 和k 传输相同的信息，设到达节点j 和k 分别所需的能量为尼，和b ，而节点i 只要以b ( ，i ) = m a x ( 只，尼，k ) 的能量发射，则节点j 和k 都可以接收到所要的信息。于是可以节省的能量为：p u + 只，。一只( m ) 。这就是无线网 络中的无线组播特性。 南京邮电大学硕1 ：研究生学位论文 第三章无线纽播中的网络编码研究 3 1 2 代价衡量 k 图3 - 1 无线组播特性易( t ) = m a x ( p , p 1 ， ) 寻找最优的组播路由算法，就是要在最小可能的能源消耗情况下，完成最大信息量的 传输。在考虑无线组播特性的