（电路与系统专业论文）基于组播的网络编码研究[电路与系统专业优秀论文].pdf

南京邮电大学硕士研究生学位论文 中文摘要 摘要 2 0 0 0 年，香港中文大学的a h l s w e d e 博士等基于网络信息流的概念提出了网络编码的思 想。网络编码是指在计算机网络的中间节点上对接收到的信息进行一定形式的编码处理， 然后再传输出去，在信宿节点上，通过一定的处理方式，译出信源节点所发的信息，而不 是像传统网络那样在中间节点上只是进行存储转发。 通过允许网络节点进行编码，可以获得网络组播速率的最大流限，即网络资源利用的 理论上限，而通过传统的路由和复制并不一定能够获得该最大流限。此外通过网络编码可 以取得节省网络带宽资源，平衡链路负载，优化能量受限网络的能量消耗等好处。目前， 有关网络编码理论的研究已经引起了学术界的高度重视，网络编码已经成为网络信息理论 领域最受瞩目的研究热点之一。 本论文在分析网络编码理论的基础上，对利用信息流分解来简化网络编码进行了研 究。论文首先简要介绍组播技术的产生、路由实现及组播技术的局限性，回顾了网络编码 的提出、发展和现状；其次描述了网络编码的基本概念，并介绍了目前网络编码最主要的 两种实现方式线性网络编码和随机网络编码，以及采用网络编码所带来的好处；最后 本文在描述了信息流分解的思想后，提出了一种新的基于节点合并的最小子树图算法。本 算法直接体现了信息流分解的思想，不需要对所有的边进行组播特性检测，并提出了简单 的组播特性检测方法，简化了计算。 关键词：网络信息流，组播，网络编码，最大流最小割，信息流分解，最小子树图 南京邮电大学硕士研究生学位论文 英文摘要 a b s t r a c t n e t w o r kc o d h a gw a sp u tf o r w a r db yd r a h l s w e d ei n2 0 0 0 ，w h i c hi sb a s e do nt h e c o n c e p t i o no fn e t w o r ki n f o r m a t i o nf l o w n e t w o r kc o d i n ga l l o w st h ei n t e r m e d i a t en o d e so ft h e c o m p u t e rn e t w o r k st oc o d et h ei n f o r m a t i o nn l e yr e c e i v e df r o mt h e i ri n c o m i n gl i n k s t h e na tt h e s i n k s ，i n f o r m a t i o ni sd e c o d e df r o mw h a tt h e yr e c e i v e d i fc o d i n gi sp e r m i t t e db yt h en e t w o r kv e r t i c e s ，t h em a x f l o wb o u n do fn e t w o r km u l t i c a s t c 趾b 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 r m o r e ，t h r o u g hn e t w o r kc o d i n g ，w e c a no b t a i nt h eb e l e f i t so fs a v i n gi nb 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 yu s a g eo f e n e r g 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 t i n t e r e s t sa n dh a sb 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 o r m a t i o nt h e o r y t h i st h e s i si n v e s t i g a t e ss o m ea s p e c t so fn e t w o r ki n f o r m a t i o nf l o wd e c o m p o s i t i o nf o r s i m p l i f y i n gn e t w o r kc o d h a g 、) v i mt h ea n a l y s i so fn e t w o r kc o d i n gt h e o r y f i r s t l y ，t h ed i s s e r t a t i o n i n t r o d u c e st h em u l t i c a s tt e c h n i q u ea n di t s p r a c t i c eb ym u t i n g , i t sl i m i t a t i o n t h ea n dt h e o e e u r r e m e n ta n dd e v e l o p m e n to fn e t w o r kc o d i n g s e c o n d l y ，i td e s c r i b e st h ec o n c e p to ft h e n e t w o r kc o d i n g ，m e t h o do fn e t w o r kc o d i n g ，l i n e a rn e t w o r kc o d i n ga n dr a n d o mn e t w o r kc o d i n g ， a n dt h e ni n t r o d u c e st h eb e l e f i t so fu s i n gn e t w o r kc o d i n g t h i r d l y ，i ti n t r o d u c e st h ec o n c e p t i o no f i n f o r m a t i o nf l o wd e c o m p o s i t i o nf o rn e t w o r ke o d m g f i n a l l y ，t h ea u t h o rp r o p o s e dan e w a l g o r i t h mo f m i n i m a ls u b t r e eg r a p h s ，w h i c hi st h ee m p h a s i so ft h ep a p e r a n dt h ea l g o r i t h mi s t h ed i r e c ts h o wo ft h ec o n c e p t i o no fi n f o r m a t i o nf l o wd e c o m p o s i t i o na n dm a k e si te a s yt o i d e n t i f yt h em u l t i c a s tp r o p e r t y ，b e c a u s et h i sa l g o r i t h md o e sn o tn e e dt oe x a m i n ee a c he d g e k e yw o r d s ： n e t w o r ki n f o r m a t i o nf l o w , m u l t i c a s t ，n e t w o r kc o d i n g ，m a x f l o wm i n - c u t , i n f o r m a t i o nf l o wd e c o m p o s i t i o n ，m i n i m a ls u b t r e eg r a p h s i l 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：童髫妲日期：二华 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名：彩錾杰么名师签名： 计哆日期：芦 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 当前世界经济正从工业经济向知识经济转变。知识经济的两个重要特点是信息化和全 球化。要实现信息化和全球化，就必须依靠完善的网络。因此，网络现在已经成为信息社 会的命脉和发展知识经济的重要基础。网络对社会生活的很多方面以及对社会经济的发展 已经产生了不可逆转的影响，尤其是i n t e m e t 的建立，推动了网络向更高层次发展，而建设 信息高速公路，更是使得网络技术进入新的历史阶段【。 l1 组播通信 随着网络技术的不断发展，特别是分布式多媒体应用技术的兴起，出现了诸如视频会 议、视频点播、网络电视、新闻发布等一对多或多对多的组播通信需求。这种业务的特点 是“在时间上具有一致性，空间上具有分布性 【2 】。比如，具有多个分会场的视频会议系 统是典型的多数据源多接收者的组播通信，而网络电视是典型的单数据源多接收者的组播 通信。网络中这种点到多点的通信方式称为组播( m u l t i c a s t ：p o i n tt om u l t i p o i n t ) 。 1 1 1 组播技术的产生 传统m 通信有两种方式【3 , 4 1 ：第一种是在一台源口主机和一台目的m 主机之间进行， 即单播( u n i c a s t ) ；第二种是在一台源p 主机和网络中所有其它的口主机之间进行，即广 播( b r o a d c a s t ) 。如果要将信息发送给网络中的多个主机而非所有主机，则要么由源主机分 别向网络中的多台目标主机以单播方式发送i p 包，要么采用广播方式。采用单播方式实现 时，由于p 包的重复发送会白白浪费掉大量带宽，也增加了服务器的负载；采用广播方式 实现时，不仅会将信息发送给不需要的主机而浪费带宽，也可能由于路由回环引起严重的 广播风暴。因此，传统的单播和广播通信方式不能有效地解决单点发送多点接收的问题。 i p 组播是指在i p 网络中将数据包以尽力传送( b e s t e f f o r t ) 的形式发送到网络中的某个 确定节点子集，这个子集称为组播组( m u l t i c a s tg r o u p ) 。i p 组播的基本思想是，源主机只 发送一份数据，这份数据中的目的地址为组播组地址，组播组中的所有接收者都可接收到 同样的数据拷贝，并且只有组播组内的主机( 目标主机) 可以接收该数据，网络中其它主 机不能收到。 南京邮电大学硕士研究生学位论文第一章绪论 1 i 2 组播技术的路由实现 考虑一个通信网络【4 ，5 1 ，它是由一些节点和边组成的集合，用有向图g = ( y ，e ) 来表示， y 和e 分别是节点和边的集合，非负数尺( p ) 用来表示边p 上允许传输信息的容量上限。在 这个通信网络中，要实现由一点了y 向多点tcy 组播信息，传统的路由方式是通过在通 信网络中建立个或多个组播树q = ( 圪，巨) ，每个组播树都将信源和所有的信宿连接起 来，所要传输的信息就在这些事先选好的路径上传输。每个组播树可以实现的传输速率取 决于组成这个树的所有的边中容量最小的边，也就是m m 醒目r k ( e ) 。为了可以获得更高的 组播速率，可以建立多个组播树q ，七- - 1 ，k ，并且在不同的组播树上传输不同的信息， 鬈 只要每条边上传输的信息量满足r ( p ) r ( p ) 即可。 七霉l 1 1 3 组播技术的局限性 上面已经提到，组播是靠在通信网络上建立组播树来实现的。由最大流最小割定理【5 1 ， 网络中两节点之间的最大流量可以通过最小割来衡量，同时，实现最大流的路径可以通过 最大流算法【6 】找到。当要建立两节点之间通信的时候，在两节点之间，应用最大流算法， 得到它们之间的最大传输速率。但是，一点向多点的组播路由树的建立是一个n p 问题【刀。 一般采用的方法是首先采用最大流算法找到信源与一个信宿之间的最大流及其实现的路 径，其次再依次寻找信源与其它信宿之间的路径。在寻找信源与第二个信宿之间的路径时， 就在原通信网络中去掉信源与第一个信宿之间已经用过的链路的容量。这样处理是因为， 传统路由认为网络中传输的信息是不能叠加的，只能进行存储转发。这样的组播树的建立 方式会导致信源与第二个及其后面所有信宿之间的路径都不是以它们之间的最大流进行 传输的。这将最终使得组播可以实现的传输容量远远小于最大流最小割定理确定的容量上 限。 i 2 网络编码的提出和发展现状 针对组播技术的上述局限性，网络编码应运而生，它可以用来实现由最大流最小割定 理给定的一个通信网络的容量上限。 2 南京邮电大学硕i ：研究生学位论文第一章绪论 1 2 1 现有的信息转发方式 一、电路交换 电路交换方式主要用于目前的电话通信网，它是一种面向连接的技术，一次通信过程 分为连接建立、数据传输和连接释放三个阶段。 在连接建立阶段，网络要完成两项工作：第一，确定本次通信从源端到目的地端，用 户业务信息应走的路由；第二，在该路由途经的交换节点进行全程的资源预留，预留的资 源包括交换节点从输入端口到输出端口的内部通道以及交换节点间中继线路上的带宽资 源，以这种方式建立一条端到端的专用通信连接，这个连接通常占用固定的带宽或时隙， 有固定的传输速率。在整个通信期间，不管实际有无数据传输，沿途的交换节点负责保持、 监视该连接，直到用户明确地发出通信结束的信号，网络彳释放被占用的资源，撤销该连 接。电路交换在连接建立时，预先分配固定带宽资源的方式被称为静态复用方式。 电路交换的主要特点是：在连接建立阶段，为用户静态地分配通信所需的全部网络资 源；并且在通信期间，资源将始终保持为该连接专用；在数据传输阶段，交换节点只是简 单将用户信息在预先建立的连接上进行转发，节点处理时延可以忽略不计，效率很高。电 路交换很适合实时性要求高的通信业务，传统电话通信网就采用这种方式，它很好地解决 了实时语音通信问题。它的主要缺点是信道资源的利用率低。 二、分组交换 分组交换方式主要用于计算机间的数据通信业务，它的出现晚于电路交换。采用分组 交换而不是电路交换来实现数据通信，主要基于以下原因： ( 1 ) 数据业务有很强的突发性，采用电路交换方式，信道利用率太低。 ( 2 ) 电路交换支持固定速率的数据传输，要求收发严格同步，不适用数据通信网中 终端问异步、可变速率的通信要求。 ( 3 ) 语音传输对时延敏感、对差错不敏感，而数据传输则恰好相反，用户对一定的 时延可以忍受，但关键数据细微的错误都可能造成灾难性后果。 ( 4 ) 分组交换是针对数据通信而设计的，主要特点是：数据以分组为单位进行传输， 分组长度一般在1 0 0 0 至2 0 0 0 字节左右；每个分组由用户信息部分和控制部分组成，控制部 分包含差错控制信息，可以用于对差错的检测和校f ；中间的交换节点以“存储一转发” 方式工作，可以方便地支持终端间异步、可变速率的通信要求；为解决电路交换方式信道 资源利用率低的缺点，分组交换引入了统计时分复用技术。 南京邮电大学硕士研究生学位论文第一章绪论 1 2 2 网络编码的提出 在目前的通信网络中，不管是采用电路交换还是采用分组交换的方式来传输信息，中 间节点都仅仅转发或存储转发它所接收到的信息，除了数据复制以外，网络的中间节点并 不需要做任何其它的数据处理。在许多实际应用中，人们为了信息分析，在中间节点所进 行的数据处理对数据传输过程本身并不会带来任何好处。 2 0 0 0 年，a h l s w e d e 等人喁】发表了一篇题为“网络信息流”的文章，提出了“网络编码 这一概念，该理论通过允许中间节点在转发信息前对输入信息流进行编码来实现网络组播 容量的极限。 a h l s w e d e 等根据网络信息流的概念指出，网络组播的最大容量等于发送节点和组播组 中各接收节点之间的最小割的最小值，该最小值称作网络组播的最大流限。对于一般的网 络，这一容量很难通过传统的路由组播获得，但却可以通过网络编码组播获得。网络编码 实际上是指网络节点的输入链路与输出链路上传播的数据的相互关系。网络编码思想是在 y e u n g 的对称分层编码【9 1o 1 1 ，1 2 1 3 1 研究的基础上提出的，将分层编码在信源节点的编码推广 到允许整个网络节点进行编码来获得网络组播的最大流限。传统的路由组播可以看作是网 络编码的一种特例。 1 2 3 网络编码的发展现状 自从2 0 0 0 年a h l s w e d e 等人提出网络编码的基本概念之后，关于网络编码的研究如雨后 春笋般多起来。目前，有很多电信业巨头和著名的大学都在致力于这方面的研究，如香港 中文大学、微软、麻省理工学院、伊利诺伊大学、加利福尼亚大学洛杉矶分校、以色列的 t e l - a v i v 大学等等。 a h l s w e d e 等人仅给出了网络最大信息传送速率的存在性证明，并没有给出具体的网络 编码实现方式。l i ，y e u n g 并q l c m 1 4 】提出单一信源，多接收节点网络的最大传输速率可以通 过线性网络编码实现。通过一个广泛适用的线性编码组播算法( l c m ) ，每个接收节点都 可以达到其最大流。l c m 主要应用于非循环网络。l c m 规则为每条边分配边向量，每个节 点分配向量空间。边向量与节点的向量空间按照l c m 规则满足一定的关系。通过边向量和 节点上的信息向量相乘对信息编码，在接收节点处使用逆矩阵解码。l c m 方法可以达到任 意节点的最大流。但由于l c m 规则过于严格，寻找符合规则的向量需要大量的时间，造成 了网络的时延，因此l c m 不适合用在实际网络中。 4 南京邮电大学硕士研究生学位论文第一章绪论 k o e t t e r 和m e d a r d 1 5 , 1 6 , 1 7 】为网络编码设计了一个数学框架。它将一般的网络编码寻找线 性解的方法简化为寻找多元多项式的非零解。同时寻找编码系数的方法也通过代数编码方 式而简化了。这种构造方式是在知道整个网络的拓扑信息的情况下，用一个系统转移矩阵 来描述信源输入信息和信宿上接收到的信息之间的关系，并通过构造符合要求的系统转移 矩阵来实现网络编码。另9 b s a n d e r s 等人提出了一种实现网络编码的多项式时间算法 l s j g l ， 这种方法将网络编码的构造进一步简化，它也是在知道整个网络的拓扑信息的情况下，首 先通过最小割最大流算法找到完成组播所需的路径的集合，在找出的这个子图上，再自上 而下的确定各个节点所需要进行的操作。这种方法不但把网络编码构造的复杂度从指数级 降到了多项式级，而且大大降低了网络编码中所采用的字母表的下限。 上述方法都是基于已知整个网络的拓扑信息，同时c h o u 等提出了不需网络拓扑信息的 分布式网络编码【捌。针对组播信息传输问题，h o 等人设计了一种不需要知道网络节点分布 情况的随机网络编码【2 1 捌。分布式网络编码的实现是在网络中传输的每个数据包上留出一 些比特用来记载此数据包在前面各个节点上所经历的各种操作，接收节点就可以从接收到 的数据包中直接译出信源所发送的信息。这种方法是可以在不知网络拓扑信息的情况下实 现网络编码，但是增加了网络负载，但是仿真结果表明 2 0 1 ，在整个信息的组播过程中，这 种处理方式所带来的负载代价不大。随机网络编码，即在网络的中间节点上对接收到的信 息在一个有限域内随机选择一个元素作为组合的系数。研究已经表明，网络中所有接收节 点收到全部信息的可能性至少为( 1 一d g ) ，其中d 是接收节点的个数，边上传递的信息来 自所有源节点，同时将信息传到任何一个接收节点去，满足这样要求的边的最大数量是1 ， g 是系数选择的范围，也就是字母表的大小。同时，由于随机网络编码在各条链路上以等 概传播信息，因此可以最大程度上保证传输的成功。只要有限域取的足够大，这种方法的 失败率就可以很低。这种方法带来的缺点一个是以一定的概率实现正确无误的传输，另一 个是需增大通信网络中所需的字母表的大小。 还有一些人致力于线性网络编码【1 4 ，2 3 】的研究，给出线性网络编码的实现方法，并分析 了线性网络编码的有效性澄2 5 1 。线性网络编码不但可以用在已知网络拓扑的构造方式中， 也可以用在不需网络拓扑信息的分布式网络编码和随机网络编码中。他们推测线性网络编 码可以实现所有的可解网络的网络编码【2 6 】。而文献【2 7 】中己经构造了一个特殊的网络说明 了线性网络编码的局限性，在这些特殊的网络中使用非线性网络编码可以实现由最大流最 小割确定的网络容量的上限，线性网络编码却无能为力。 上述研究都是针对有线网络的，关于无线网络中的网络编码的研究也是网络编码研究 5 南京邮电人学硕 ：研究生学位论文 第一币绪论 中的一个热点【2 8 , 2 9 3 0 3 。由于无线网络自身的一些不同于有线网络的特性，这使得网络编 码在无线网络中的应用带来了新的好处。 另外，现在关于网络编码和其它方面结合的研究也很多，例如网络编码和纠错码的结 合【3 2 ，3 3 3 4 1 ，网络编码和加密体制的结合【3 5 , 3 6 , 3 7 】等。人们对网络编码在提高网络性能方面的 应用也作了大量的研究，研究表明，网络编码除了能够提高系统的容量外，在数据压缩【3 蚋、 负载均衡【3 9 1 、降低节点能量消耗【删、减少传播时延、提高网络健壮性以及信息安全等方面 都有重要的应用前景。 目前，网络编码的研究热点主要集中在以下几个方面【4 a i 】： ( 1 ) 网络编码节点选取方案 在确定的网络结构中，并不是所有的节点都需要进行网络编码，而是选取其中需要编 译码的节点，给予编译码功能。对于不需要编译码的节点，只具有传统的存储转发功能即 可。这样不仅可以降低编码算法的复杂度，也减小了对硬件的要求，从而使得网络编码的 应用更为广泛。文献 3 4 】根据网络拓扑结构，利用一种子树分解算法来寻找编码节点。将 该算法应用于有线网络中并使用确定的网络编码机制，效果较好。对于无线网络，节点之 间的连接关系更为复杂，并且节点传输覆盖范围内的节点都可能接收到网络信息，导致拓 扑结构更为紧密，应用上述方法选择编码节点就不适合。无线网络中主要考虑节点能量及 稳定性的影响，选择编码节点或设计网络拓扑时应尽可能将节点能量较高、具有较强的运 算速度和较大的缓存空间的节点，以提高网络的健壮性。 ( 2 ) 网络编码算法的设计 目前，网络编码主要有确定性和随机性两种编码方案，分别用于不同的网络应用与构 架上，这些方案主要是基于理论上的分析和实现，在实际网络中需要针对不同的应用设计 相应的编码方式。对于结构较小的网络，可以选择比较简单的确定性算法，编码过程中甚 至可以通过转换为对数，将乘法运算转换成加法运算，降低总的编码复杂度。对于无线网 络，则应用随机编码机制是主要的研究趋势，即令中间节点随机生成编码系数，对节点所 有的可用信息应用线性编码，并随时更新编码系数。文献 1 6 】已经证明，当符号集为无穷 大时，采用随机编码，系数传输矩阵满秩的概率是1 ，即编码成功的概率很大，但同时会 增加数据报头的负担，因此符号集的大小需要权衡各种因素。 ( 3 ) 网络编码复杂度分析 网络节点编码过程中涉及到大量的乘法与加法运算，需要较大的计算复杂度，而接收 节点译码过程若应用高斯消除方法，也是较大的运算过程。接收节点个数和节点信息块的 大小共同决定了编码符号集的最低门限。对于确定性编码而言，所需的符号集可以较小， 6 雨京邮电大学硕士研究生学位论文第一章绪论 编码的复杂度较低，但这种机制需要有中心节点集中控制网络信息，对于网络编码的很多 应用场景以及网络构架都不适用，但可以通过对其相应的复杂度分析，来设计合适的编码 算法从而降低网络的复杂度。对于随机网络编码而言，所需的符号集较大，而且节点在传 送信息的同时传送系数向量，虽然系数向量相对于信息而言较小，但同样会占用较大的带 宽，因此需要设计合适的算法，保证在提高编码增益的同时降低复杂度。网络编码复杂度 要受到符号集大小、节点计算复杂度、网络编码方案等诸多因素的影响，需要全面分析得 出。 ( 4 ) 网络编码的性能分析和应用 网络编码可以提高网络容量，已经证明，应用网络编码可以逼近香农极限。网络编码 通过编码节点对输入信息线性或非线性的编码处理，可以在不提高消耗带宽的情况下，使 不同的信息同时通过有限的链路，从而提高网络流量。 网络编码导致编解码的过程中可能会产生编译码错误，这将增大网络数据传输的误码 率。而就网络编码本身而言，对误码率有着相当苛刻的要求，只有较小的误码率才能保证 网络编码的有效性和可靠性，否则使用网络编码可能还会带来系统整体性能的降低。因此， 如何设计可靠的网络编码方案以保证数据传输较低的误码率，并尽可能地采用相应技术减 少误码率对网络编码方案的影响是网络编码研究所必需的。 ( 5 ) 网络编码与系统安全性分析 网络编码不仅可以提高节点间传输效率和网络吞吐量，还会对网络的安全性能产生影 响。一方面，由网络编码导致的信息的分散性和编译码特性增加了信息破译难度，对安全 性而言是一种改善；另一方面，对确定性编码算法而言，由于传输过程中将涉及较多的节 点数目，以及编码算法方案的确定性，会导致系统的安全性能的降低。因此编码算法的设 计中也需要考虑系统的安全性能，通过对不同的编码算法进行恰当的安全性能分析，来确 定不同网络算法对系统安全性的影响，从而针对不同的系统应选用合适的编码算法，以提 高网络安全性能，这对于通信网络的研究具有重要意义。 ( 6 ) 网络编码在无线分布式网络中的应用 对网络编码技术的研究需要在加深理论研究的同时，考虑实际的应用场景，侧重解决 实际应用中遇到的问题，比如需要降低编码复杂度，需要考虑系统本身的延时以及网络编 码带来的延时影响等。网络编码在无线通信网络当中的应用是一片亟待开发的热土，一方 面无线网络的广播特性非常利于网络编码的应用；另一方面，相对于有线网络而言，无线 网络中的节点不可能同时监听来自多个信源的信息，对网络编码的应用造成了一定的阻 7 南京邮电大学硕士研究生学位论文第一章绪论 碍。如何结合无线分布式网络的特点扬长避短，找到能够最大程度发挥网络编码优势的结 合点，是需要考虑的主要问题。 总之，现在关于网络编码的研究是百家争鸣，各种方法和应用层出不穷。到目前为止， 关于网络编码的研究还有很多问题亟待解决，但随着更多学者对该领域的深入研究，网络 编码技术在未来通信中必将得到广泛应用。 1 3 本文的主要研究工作和章节安排 网络编码的提出彻底改变了计算机网络中的信息处理方式，网络节点不再仅仅限制于 存储转发，而是在网络节点上可以进行编码处理，实现利用有限的带宽资源传输更多的信 息。其研究涉及计算机通信技术、组播技术、信息论和图论等方面的知识。自从网络编码 概念提出以来，很多专家和学者都致力于网络编码算法的研究与设计，从不同的角度出发， 提出了很多的方案，大多基于理论的分析和实现。而网络编码的信息流分解是本文将要研 究的主要工作。 作者通过对网络编码的基本理论进行深入学习，在透彻理解信息流分解思想的基础 上，提出了基于节点合并的最小子树图算法，并说明了其优越性。本文共分五章，主要结 构如下： 第一章绪论部分简要介绍了组播技术的产生、路由实现及组播技术的局限性，回顾了 网络编码的提出、发展和现状。 第二章首先通过一个简单的组播问题( 只有一个信源和两个信宿) 直观地介绍了网络 编码的基本思想和概念，然后给出了网络信息流的定义以及研究和分析网络编码所需的图 论基础知识，为后续章节作铺垫；其次指出了应用网络编码可以实现网络中的最大流，并 给出了证明，而这正是应用网络编码的理论基础；随后重点介绍了网络编码目前最主要的 实现方式线性网络编码和随机网络编码，并指出了它们各自的优点和缺点，其中对于 线性网络编码给出了从不同角度出发的两种构造方式：从向量空间角度和从代数构造角度 出发的构造方式：最后给出了采用网络编码所带来的好处。 第三章首先介绍了信息流分解的思想以及用它来分析和构造网络编码的优势，其次介 绍了子树分解的概念和过程，最后讨论了在信息流分解的基础上构造有效网络编码的概念 和相应措施。 第四章在充分掌握了网络编码的基本理论知识和信息流分解的思想后，介绍了信息流 分解中最小子树图的概念以及它对于网络编码的意义，提出了一种新的基于节点合并的最 8 南京邮电大学硕士研究生学位论文第一章绪论 小子树图算法，并且说明了其优越性。本算法直接体现了信息流分解的思想，不需要对所 有的边进行组播特性检测，并提出了简单的组播特性检测方法，显著地简化了计算。 第五章对全文工作进行了总结并提出了需要进一步研究的方向。 9 南京邮电大学硕士研究生学位论文第二章网络编码概述 第二章网络编码概述 在这一章中，首先，从一个只有单个信源和两个信宿的简单组播问题出发，描述了网 络编码的基本思想和概念，并给出了采用网络编码可以实现网络中的最大流的证明，而这 正是应用网络编码的理论基础；其次，介绍了网络编码目前最主要的实现方式线性网 络编码和随机网络编码，并给出了线性网络编码的从不同角度出发的两种构造方式及其各 自的编码特点；最后，从理论上总结了网络编码性能分析的己有成果，这些成果显示了网 络编码的巨大优越性。 2 1 网络编码基础 2 1 1 网络编码的基本概念 在研究网络编码的过程中，通信网一般简化为相应的图来表示。假定有一个通信网络 如图2 1 所示，这是一个拥有单个信源和两个接收节点的网络，假设每条链路都无时延和无 ( i ) 边的容量 ( 2 ) 传统路由( 3 ) 网络编码 图2 1 经典网络编码原理图 差错。其中，j 是信源节点，y 和z 是接收节点。m 2 1 ( 1 ) 给出了每条边的信息速率均为1 1 0 南京邮电大学硕士研究生学位论文第二章网络编码概述 比特单位时间。由最大流最小割定理【5 1 容易得出从信源s 到接收节点j ，和z 的最大流均为 2 。由此得到信源j 可以同时发送2 比特信息给y 和z 。但是，如果按传统路由方式如图 2 1 ( 2 ) ，在一个单位时间内将无法完成以上传输。图2 1 ( 3 ) 给出一种编码方案，从图中可 以看出，为了从信源节点s 同时传输两比特信息岛，6 2 到接收节点，则在中间节点w 处，必 须通过网络编码，使输出边( w x ) 传输两条输入边上所携带信息的线性组合岛+ 6 2 ( 模2 加) ， 那么在接收节点y 和z 处，才可分别由岛+ 如t ub , ，6 l + 和6 2 ，通过模2 加恢复出所有的 信息a ，6 2 。因此，在这个简单的组播问题中，中间节点w 不再只进行简单的存储转发， 而是引入一定的操作，从而可以在一个单位时间内把两个比特的信息传输给接收节点y 和 z ，这就是网络编码的思想。 定义2 1 ：网络中的节点对信息比特流进行一定的操作，如模二加、与、或等等，而不 是仅仅对其进行复制转发，称之为网络编码。 简单的说，网络编码的操作就是确定网络节点的输入与输出的相互关系，也可说是确 定一个映射规则，中间节点按这个规则把输入映射为输出。 2 1 2 网络信息流 在上一节中提到最大流最小割定理决定了从信源s 到接收节点y 和z 的最大流，而针 对一般的组播问题，2 0 0 0 年，a h l s w e d e 等人【硼发表了一篇题为“网络信息流 的文章，对 组播网络的容量和网络中信息的流动做出了规范和定义。也正是在这篇文章中，提出了“网 络编码一这一概念。 网络编码的研究与分析离不开图论这一有用工具。因此，本节首先给出一些描述通信 网以及研究和分析网络编码时需要的图论基础知识【4 ，6 】，然后对组播网络中的最大流问题作 出说明。 图是由一些节点和连接两个节点之间的边所组成，至于边的长度及节点的位置是无关 紧要的【5 1 。 定义2 2 ：一个图g 是一个序偶( y ，d ，记为g = ( v ，e ) ，其中： ( 1 ) 矿= v l ，v 2 ， 是有限的非空节点集合，m ( i = i ，2 ，m ) 称为节点，y 称为节 点集，m 为节点的数目。 南京邮电大学硕士研究生学位论文 第二章网络编码概述 ( 2 ) e 是有限的边的集合，e 称为边集。e 中的每个元素都是以( _ ，) 或( 匕，_ ) 形式出 现的无序对，其中f ，= 1 ，2 ，m 。 若边p 与节点的无序对( 一，1 ，) 相对应，则称p 为无向边，记为p = ，这时称m 、 v ，是边p 的两个端点。若边e 与节点的有序对( 匕，v j ) 相对应，则称e 为有向边，记为 p = ( 哆，匕) ，这时v i 称为p 的始点，匕为e 的终点，统称为g 的端点。 为了描述简便起见，在一般情况下，对于一个图g = ( y ，e ) ，往往不写出y 和e 的集合 表示，而只画出它的图形，用小圆圈表示y 中的节点，用“，1 ，) 表示由_ 指向的有向线 段。 定义2 3 ：每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有 些边是无向边，而另一些边是有向边的图称为混合图。 在有向图中，两节点间( 包括节点自身间) 若有同始点和同终点的几条边，则这几条 边称为平行边。在无向图中，两节点间( 包括节点自身间) 若有几条边，则这几条边称为 平行边。两节点q 和匕问相互平行的边的条数称为边( e ，) 的重度。 定义2 4 ： ( 1 ) 图g = 缈，e ) 中节点m y 所关联的边数( 有环时计算两次) 称为节点h 的度数，简 称度，记为d e g ( m ) 。 ( 2 ) 设v j 为有向图g = ( y ，e ) 中的节点，以v j 为始点的边的条数称为节点e 的出度，记 为d e g + “) ；以哆为终点的边的条数称为节点_ 的入度，记为d e g 一( e ) 。显然， d e g ( v 1 ) = d e g + “) + d e g 一“) 。 ( 3 ) 对于图g = ( v ，e ) ，度数为l 的节点称为悬挂节点，它所关联的边称为悬挂边。 在研究和描述图的性质时，子图与补图的概念占重要地位。 定义2 5 ：设有图g = ( y ，e ) 和图g = ( y l e i ) 。 ( 1 ) 若y s 矿，e e ，则称g 是g 的子图，记为g g 。 ( 2 ) 若g g ，rg g ( 即v cy 或e ce ) ，则称g 是g 的真子图，记为g 匕g ( 3 ) 若v = 矿，e e ，则称g 是g 的生成子图。 ( 4 ) 设v ”冬y 且v 一，以y ”为节点集，以两个端点均在y ”中的边的全体为边集的g 的子图称为y ”导出的子图，简称g 的导出子图。 定义2 6 ：若有向图满足下列条件者，则称其为网络流图： ( 1 ) 有且仅有一个顶点s ，它的入度为零，这个顶点s 便称为信源节点，或称为发点。 1 2 南京邮电大学硕士研究生学位论文第二章网络编码概述 刁i o ( 2 ) 有且仅有一个顶点，它的出度为零，这个顶点f 便称为信宿，或称为接收节点。 ( 3 ) 每一条边都有一个与之相关的非负数，表示该边的容量。趔z c v , ，匕) 的容量用毛表 口 图2 2 网络流图 例如图2 2 便是一个网络流图。 上面定义的网络常常称为运输网络。可用运输网络来表示的物理模型是多种多样的。 网络中的有向边可以用来表示城市之间的公路、电讯局之间的通信线路，边的容量则可以 是允许通过的物资、速度，公路上的汽车数量或信号流量等等。 定义2 7 ：对于网络流图g ，每一条边“，v j ) 都给定一个非负数厶，这一组数满足下列 两条件时称为这个网络的可行流，用厂表示它。 ( 1 ) 每一条边( m ，v j ) 都对应一个非负数嘞，毛称为边的容量，有 石毛 ( 2 - i ) ( 2 ) 除了信源节点s 和接收节点，以外的所有的节点，恒有 石= 厶 j 七 式( 2 - 2 ) 说明中间节点m 的流量守恒，输入与输出的流量相等。 ( 3 ) 对于信源s 和信宿节点，有 厶= 厶= w ， ( 2 2 ) ( 2 3 ) 式( 2 3 ) 中w 叫做这个网络流的流量，而且从点s 发出的量等于流入信宿节点f 的量。 定义2 8 ：当= 毛时便称边( m ，_ ) 为饱和，表示流厂对该边已饱和。 1 3 南京邮电大学硕士研究生学位论文 第二章网络编码概述 所谓最大流问题是求使得从发点s 送往信宿节点f 的流量w 达到最大i y j b 虎f 。 为了解决求网络的最大流问题，给出切割的概念。 定义2 9 ：对有向图g = ，昱) 中两个不同的节点s 和f ，s f 割是g 中弧( x ，叉) 的集合， 其中s x ，f 一x ，x 是矿的子集，一x ：v x 。 定义2 1 0 ：在这集合( x ，叉) 中，把从x 到孑的边的容量的和叫做这个割切的容量，用 c ( x ，_ ) 表示，有 c ( x ，牙) = 一毛( 2 - 4 ) 图2 3 割切举例 如图2 3 中虚线分别表示割切，石) 和( 五，石) ，其中： 对于割切( 五，五) ，有 五= p ，五= 口，b ，c ，d ，f ) c ( 五，五) = + = 2 + 3 = 5 对于割切( 五，五) ，有 五= 仅a ，以，五= c ，d ， c ( 五，五) = + + = 1 + 1 + 4 = 6 定理2 1 t 3 6 】：( 最大流最小割定理) 对于已知的网络流，从源点s 到信宿f 的流量w 的最大 1 4 南京邮电大学硕士研究生学位论文第二章网络编码概述 值等于最小s f 割的容量，即 m a xw = m i n c ( x , ，置) ( 2 5 ) 其中，( 五，五) 是s t 割。 假定考虑一个通信网络，用有向图g = ( v ，d 来表示。设a ： l ，m 专v 和 b ： 1 ，m _ 2 y 是两个任意的映射。信源z 在节a ( i ) 上产生，它将被组播到节点i ，对 所有的歹6 ( f ) 。对于这里的单源问题，假定口( 1 ) = s ，和6 ( 1 ) = f l ，屯 ，也就是说，信源 五由节点s 产生，网络将其产生的信息组播到节点f 1 ，气。我们称节点s 为信源，节点 ，l ，气为信宿。对于某个特定的值，称这种问题为单信源三信宿问题。 定义一些下面将会用到的符号：设图g = ( y ，毋中的信源为s ，信宿为 ，乞。边 g ) e 上的容量为吗，且有刃= 【毛，o ，j ) e 】。从信源s 到信宿，1 = 1 ，工的子图用 g ，= ( y ，局) 表示，其中 与= ( i ，j ) ee ：边( 毛歹) 在信源s 到信宿毛的有向路径上 f - f ，o ，j ) e 司是图g 中s k 信源s 到信宿f ，的流 如果式( 2 - 6 ) 对于所有的( f ，j ) e 都成立 o s 弓s 心 ( 2 6 ) 且对于除信源s 和信宿f ，之外的所有其它节点i y 有 吒= 历 ( 2 7 ) i ：( ，) e e 1 1 ) e e 也就是流入节点珀勺总的流量等于流出节点f 的总的流量。弓是指向量f 在边( f ，歹) 上的取 值。向量f 的定义如下： 弓一瓦= 气一曩， ( 2 8 ) ：，) e et ( f ，5 ) 毫f，：j 山) e e：( h ) | 占 如果从信源j 到信宿的流量的值大于等于任何其它从信源s 到信宿的流量值，就称 ，为图g 中从信源j 到信宿的最大流。 当信源s 的信息速率为h 时，如果在图g 中所有从信源s 到信宿的最大流f 大于或等 1 5 南京邮电大学硕士研究生学位论文 第二章网络编码概述 于h ，则把这种情况称作三维向量( 刃，h ，g ) 是可达的。 对于一个网络g ( y ，e ) ，由最大流最小割定理，很容易求得信源s 到信宿f 的最大单播 速率。对于组播网，值得关心的是信源的最大组播信息速率问题。 定义2 1 1 ： 设6 ( v ，e ) 为一个组播网络，h 为信息从信源s 到信宿 ，t 2 ，屯的组播传 输速率。令信源s 到信宿节点f ，的最大流值为m a x f l o w ( s ，) ，则对于所有的，= 1 ，2 ，l ， 有 h u m a xf l o 以s ，r ，) ( 2 9 ) 即 h m m ，i n m a x f l o w