《网络编码的无线广播重传论文12117.doc》由会员分享，可在线阅读，更多相关《网络编码的无线广播重传论文12117.doc（53页珍藏版）》请在三一办公上搜索。
1、基于网络编码的无线广播重传方案的研究摘要在无线网络广播的重传处理中，多个接收节点中的任意一个节点丢失信息包都要求源节点重传数据包，这就需要源节点广播发送较多的重传数。本文将随机线性网络编码技术应用在无线网络广播重传中，设计了一种基于随机线性网络编码的无线广播重传方案。在该方案中，源节点需记录多个接收节点中丢失信息包的数量最多的接收节点的丢包数量，再按照随机线性网络编码的方法编码组合该丢包数量个线性编码信息包；源节点广播重传线性编码组合包；接收节点采用运算编码线性组合的方法获得信息包数据。数学分析表明，该方法能保证所有接收节点的编码可解性，同时重传次数可达到理论最优性；模拟测试结果表明：与传统重
2、传方法相比，应用随机线性网络编码的重传方案有效地减少了信息包的平均传输次数，提高了传输效率关键词无线网络广播；网络编码；随机线性网络编码；重传AbstractClick here and input abstract in EnglishKeywordsClick here and input keywords in EnglishAbstract正文选用字体：Times New Roman，小四号字，行距20磅。（此段文字阅后删除） 目 录摘要IAbstractII第1章 绪论11.1 课题背景及意义11.2 本课题国内外的研究现状21.3 本课题研究的主要内容41.4 本文的章节安排4第2
3、章 基于网络编码的无线传输的分析62.1 网络编码的概念与定义62.1.1 网络编码的基本原理62.1.2 最大流-最小割定理82.2 几种常见的网络编码构造方法112.2.1 网络编码的前提假设112.2.2 线性向量编码122.2.3 线性代数编码142.2.4 随机网络编码172.3 本章小结19第3章 基于随机网络编码的无线广播重传方案的设计203.1 随机网络编码的实现203.2 无线广播重传模型的建立213.3 随机线性网络编码包的构造223.4 编码可解性的证明243.5 信息包的分批重传253.6 具体重传过程263.6.1 重传方案描述263.6.2 实际重传方案描述28第4
4、章 应用随机网络编码性能分析204.1 数学理论分析204.2 模拟测试分析204.3 本章小结20结论2参考文献3致谢4附录16附录26附录36附录412第1章 绪论近年来，随着无线技术的成熟，越来越多的人通过无线方式连接到互联网上。与此同时，由于用户数量的陡然增多、用户对网络服务需求的多样性以及用户对传输质量要求的不断提高，如何保障无线链路的可靠安全传输、优化无线网络性能、在现有网络资源的基础上提高网络资源的利用率等问题已成为当今无线网络通信研究的重要课题之一。1.1 课题背景及意义数据广播业务在蜂窝网络和无线Mesh网络中的应用越来越广泛，自动重复重传(Automatic Repeat
5、reQuest,ARQ)已经成为无线通信环境下的提供可靠通信的重要容错手段。普通的自动重复重传机制主要包括：停止-等待自动重复重传(SW-ARQ)、返回N型自动重复重传(GBN-ARQ)和选择自动重复重传(SR-ARQ)。尽管自动重复重传应用于点对点传输确实可以达到较高的传输性能，然而对于多用户的广播、组播传输，其性能会随接收节点数目的增加而迅速下降。2000年，香港中文大学的A.Rhlswede等基于网络流的概念率先提出了网络编码这一概念，其精髓来源于著名的Max-flow Min-cut（最大流最小割）理论。网络编码是指网络节点既实现路由功能又实现编码功能。利用无线信道的广播特性，网络编码
6、被应用于提高无线网络性能、提高吞吐量、安全性等。同时网络编码也为无线广播重传提供了一种途径。2006年，Nguyen等人将网络编码技术应用于重传策略中，提出了两个接收节点的编码重传策略，减少了平均传输次数，但Nguyen等人的策略仅考虑了两个接收节点的情况且没有提出具体的编码方案。网络广播中应用普通重传策略，较高的出错率会产生2个方面的问题：广播传输中丢失信息包较多，需要数量较大的重传次数；重传信息包再次丢失，需要次数较大的再次重传。因此如何利用现有的网络资源来提高重传效率成为研究的热点。现在推广到多个接收节点的情况下，将网络编码与广播重传相结合以减少重传次数、提高重传效率。因此，研究将网络编
7、码应用于单源多宿的无线广播网络中以降低重传次数是很有必要的。1.2 本课题国内外的研究现状无线传输中的广播信道特性，使得网络编码在减少无线传输次数方面有很好的应用，近年来出现了很多相关的研究。Wu等人提出了利用网络编码减少信息包互换传输次数的方法，Bin等人提出了网络编码寻找无线Mesh网最少传输次数路径的思想。Katti等人构造了无线Mesh网络使用网络编码的体系结构COPE，并利用29个节点的实验平台证实能显著减少平均传输次数。Chachulski等人则提出无线路由协议MORE，并证实该协议能有效减少信息包的平均发送次数。同时，与传统的有线网络相比，无线网络拥有较高的比特出错率，重传效率问
8、题显得更加重要。目前的研究现状来看，国外在无线传输技术中引入网络编码的研究起步较早。国外多所著名大学如麻省理工学院、普林斯顿大学、多伦多大学、瑞士EPFL学院等和多家IT公司的研究中心，包括微软研究酣、贝尔实验室、AT&T的香农信息实验室等都在积极开展相关的研究。目前国外在无线传输技术中引入网络编码的研究主要侧重在二个方面：改善无线传输吞吐量和能量利用效率、保证无线链路的可靠传输和安全性。在无线传输吞吐量研究上，Ahlswede等人指出网络编码可以达到组播传输理论最大流速；Li等人Kotter等人先后证明线性网络编码、随机网络编码同样可以达到组播传输理论最大流速、并对网络编码的数学框架进行了阐
9、述，为网络编码在无线组播传输吞吐量方面的研究提供了必要的理论条件。在能量利用效率方面，Wu等人证明在无线网络组播时应用网络编码，可以将最小化每位数据能量消耗问题归结为线性问题，为能量利用效率方面的研究提供了基础。KaRi等人证实了局部混合网络编码的传输，在TCP和UDP传输流的环境下均可以显著提高传输吞量；Wu等人接下来研究了基于局部混合网络编码互换传输的性能，证明了互换传输可以优化传输性能，这些研究均为局部混合网络编码传输提供了理论基础和条件。无线网络由于环境的多变性，使得数据包在传输中更加容易丢失，传输中的重传技术研究非常必要。当前应用网络编码的重传技术研究主要涉及二个接收节点情况下的编码
10、发送重传。从目前的研究现状来看，国内在无线传输中引入网络编码的研究起步较晚，中科院软件研究所、清华大学、中国科技大学、国防科技大学、上海交通大学、华中科技大学等高校均有相关的研究组进行该课题有关的领域研究。在无线组播传输性能研究线多源信息交换传输、P2P数据流传输、卫星技术中的组播传输、无线网络的动态网络编码协助通信等方面，国内均进行了相关的研究。从当前的国内外研究情况来看，基于网络编码的无线传输技术的核心思想仍然是通过增加节点的编码(计算)能力来换取网络传输增益。一方面网络编码进行的运算复杂度相对来说较低，另一个方面来看，相比网络传输增益，节点计算代价和延时是可以接受的。网络编码技术的提出只
11、有10年的时间。Ahlswede等人首先提出网络编码这个概念。他们的工作主要针对单个源点，多个接收点的信息传输问题，证明了在源点发送能力无限的情况下，一个网络的最大信息传送率等于该网络的最小割的容量也就是网络的最大流。将信息传输与图论的最大流最小割问题联系在一起。这也是第一次提出通信网络的容量问题。Ahlswede等人仅给出了网络最大信息传送速率的存在性证明，并没有给出具体的网络编码实现方式。Li，Yeung和Cai提出单一源，多接收点网络的最大传输速率可以通过线性编码实现。通过一个广泛适的线性编码多播算法(LCM)，每个接收节点都可以无线网络编码研究达到其最大流。LCM主要应用于非循环网络。
12、LCM规则为每条边分配边向量，每个节点分配向量空间。边向量与点向量空间按照LCM规则满足一定的关系通过边向量和节点上的信息向量相乘对信息编码，在接收节点处使用逆矩阵解码。LCM方法可以达到任意节点的最大流。但由于LCM规则过于严格，寻找符合规则的向量需要大量的时间，造成了网络的延时，因此LCM不适合用在实际网络中。Koctter等人为网络解码设计了一个数学框架。它将一般的网络编码寻找线性解的方法简化成为寻找多元多项式的非零解。同时寻找编码系数的方法也通过代数编码方式而简化了。针对多播信息传输问题，Ho等人设计了一种不需要知道网络节点分布情况的随机运算法则，通过在字母表中随机选取系数实现网络编码
13、。他同时证明了在该法则下，网络中所有接收点收到全部信息的可能性至少为(1-d/q)其中d是接收节点的个数。边上传递的信息来自所有源节点，同时将信息传到任何一个接收节点去。满足这样要求的边的最大数量是v。q是系数选择的范围就是字母表的大小。同时，由于随机编码在各条链路上以等概率传播信息，因此可以最大程度上保证传输的成功。PSanders等人提出了一种实现网络编码的多项式时间算法。这种方法将网络编码的构造进一步简化，它也是在己知拓扑的情况下，首先通过最小割最大流算法找到完成组播所需的路径的集合，在找出的这个子图上，再自上而下的确定各个节点所需要进行的操作。这种方法不但把网络编码构造的复杂度从指数级
14、降到了多项式级，而且大大降低了网络编码中所采用的字母表的下限。另外，人们对网络编码在提高网络性能方面的应用做了大量的研究。研究表明，网络编码除了能够提高系统的容量外，在数据压缩、负载均衡、降低节点能量消耗、减少传播时延、提高网络健壮性等方面都有重要的应用前景。1.3 本课题研究的主要内容本课题的研究目标是结合网络编码的思想，提出应用于不同传输因素下的广播重传策略。传输损耗较严重的情况下无线广播传输错误率高，必须使用重传策略来进行错误处理。普通的重传策略的思想在高损耗无线网络广播中会产生2个方面的问题：丢失的信息包多需要较大的重传次数；再次丢包率较高，需较大数量的再次重传。因此，本课题研究单源节
15、点、多个接收节点的情况下，将网络编码应用于无线广播重传问题以提高重传效率、减少重传次数，为网络编码技术在实际无线传输环境中的应用提供良好的理论基础。研究的主要内容为：分析针对不同丢包率进行网络编码重传的可解性条件，提出具有实际可用性的网络编码组合算法和重传机制；针对基于网络编码的无线广播重传策略在较高链路丢包率的性能下降问题，引入重传再丢失策略和发送排序策略进行改进来改善重传性能。1.4 本文的章节安排本文通过深入理解网络编码和无线网络领域近年来的重要研究成果，对网络编码在无线传输网络中的应用进行了深入的研究。设计了一种基于网络编码的无线广播重传方案，以减少重传次数提高重传效率，各章的内容组织
16、如下：第1章为绪论，主要介绍了应用网络编码的无线广播传输技术的研究背景和意义、国内外的研究现状以及当前主要的研究成果，并对本文的主要工作进行了论述。第2章介绍了网络编码基本原理与最大流最小割定理，在此基础上又进一步阐述了几种常见的网络编码的构造方法和它们的优缺点。并从中选择了随机网络编码进行研究设计。第3章设计了一种随机线性网络编码的重传方案。首先建立了接近现实环境的无线广播模型，构造了随即网络编码包，具体的描述了重传过程以及重传机制。第4章用表与图两种形式展现了接受节点在不同的丢包率的情况下应用随机线性网络编码的重传方法与传统的方法在总的传输次数的比较，充分的证明了应用随机线性网络编码的重传
17、方法。第2章 基于网络编码的无线传输的分析网络编码从广义上讲是网络中的中间节点是网络中的节点将接收到的信息进行编码后再转发出去的多点传送技术。网络编码理论彻底改变了传统的存储转络性能可以达到最大流传输的理论极限。而随机网络编码理论将网络编码的应用延伸到任意网络结构中。随机网络编码在无线网络中的应用更是因此得到了长足的发展。本章将首先介绍网络编码的基本理论，然后将引出随机网络编码在无线网络中的一般模型和方法为后续的章节的展开做好铺垫2.1网络编码的概念与定义 网络编码(Network Coding)是一种融合编码和路由的信息交换技术，在传统存储转发路由方法基础上，通过允许对接收的多个数据包进行编
18、码信息融合，增加单次传输的息量，提高网络整体性能。网络编码的本质是利用节点的计算能力提高链路带宽的利率。2.1.1 网络编码的基本原理 图2-1 网络编码概念描述xyzyxzxyzF1(x, y, z)F2(x, y, z)F3(x, y, z)节点N节点Na) 传统路由方法b) 传统路由方法如图2-1所示，节点N是网络中的一个节点，其收到来自不同链路的信息包x、 y、z并需要对信息包进行传输发送处理。如图2-1.a)所示在传统的计算机网络中，每个节点（可以是交换机或路由器），在存储转发模式下，节点只进行数据分组的路由和复制。而不同与传统网络，具有网络编码功能的节点则会对数据包进行编码/解码运
19、算，如图2-1.b)，交换机输出的信息流是其输入的信息流的函数。采用传统路由方法，节点N仅需要对收到的信息包进行存储和转发，节点的发送信息包为x、y、z。采用网络编码，节点N可以对收到的信息包进行编码运算，通过运算信息包x、y、z获得信息包F1(x, y, z)、F2(x, y, z)、F3(x, y, z)，新信息包是来自不同链路的收到信息包的编码组合。此时，若通过网络编码进行发送，节点实现了对接收的多个数据的编码信息融合操作，即网络编码操作。传统网络的存储转发模式可看作网络编码的特例。为了便于网络编码理论的分析阐述，我们仅考虑组播情况并且建立相应的网络模型，模型中假设边的带宽为单位容量，允
20、许节点间存在多条边，并忽略边的传输错误及延时。传统网络分析中，通信网络中的信息流被认为是网络管道中的流体，类似于水在渠道中流动一样。对于一个实际的通信网络，我们可以采用一个有向图G(V,E)来加以描述和研究。对于图G = (V, E)，这里V 表示节点的集合，E表示边的集合。网络中一条边用(i, j)表示，这里i，j 为网络中的两个节点。若图G = (V, E)仅有一个源节点s和一个接收节点t，且有向图中的每一条边(i, j)对应着一个非负数，并令其为该边的容量，则称该有向图为网络流图。对于网络流图G每一条边(i, j)都给定一个非负数f ，这一组数满足下列两个条件时称为这网络的可行流，用表示
21、它。1. 每一条边(i, j) ,有。2除了源节点s和接收节点t 以外的所有的节点i ，恒有式(2-1): (2-1) 这表示中间节点i的流量守恒，即节点的输入的流量和输出的流量是相等的。3源节点s和接收节点t满足公式(2-2): (2-2) 其中R称作网络流的流量，而且从源节点流出的总量等于流入接收节点 的总量。当时便称边(i, j)饱和，或f 饱和，表示流f 对该边已饱和。该网络的最大流是指从源节点送往接收节点的流量R的最大值，用max flow(s, t)表示。设U 为节点集合的一个子集，使得sU ，tU ，把一个端点属于U 而另一个端点不属于U 的边的集合称作源节点s 和接收节点t 的
22、一个割。割的容量的定义为集合EU中包含的所有边的容量的和，用C(s, t)表示，即式(2-3): (2-3) 2.1.2 最大流-最小割定理网络编码通过允许对来自不同链路的信息进行编码组合，从而提高网络性能，在这种全新的体系结构下，网络性能可以达到最大流传输的理论极限。最大流-最小割定理：对于已知的网络流图，从信源节点s到接收节点t的流量R的最大值等于其最小割的容量，即式（2-4）： (2-4) 对于有向网络，可以用Ford-Fulkerson算法来求解网络的最大流。对于网络信息流，G(V,E) 为一个多播网络， h 为信息从信源s 到信宿t1，t2，t3，的多播传输速率。令信源节点s到接收节
23、点的最大流值为max flow(s, )， 则对于所有的l =1,2,L，有： 即 将这个称作网络多播传输的最大流限。satcb3242443图 2-3 最大流最小割定理实力如图2-2所示，图中给出了最大流最小割定理的一个实例，图中从信源节点s到接收节点的流量最大值C等于信源节点到接收节点t的最大割集，即有：C=mincut(s，t)=9。图2-3所示的蝴蝶网络是网络编码实现最大流传输的例子。图中假设网络中各条链路无差错和无时延，源节点s通过网络将l比特信息a和b传输到接收节点x和z，所有的链路容量均为l。由图2-4.a)的网络链路容量图，可以得知： (2-5) 由最大流最小割定理有： (2-
24、6)suvwdxzsuvwdxzsuvwdxz111111111ababaa/bbababaabbabababa) 网络链路容量b) 传统路由传输c) 网络编码传输图2-3 经典网络编码原理图由图论中的点对点的最大流最小割定理，对于已知的网络流图2-4.a)，从源节点到接收节点的流量的最大值小于或等于任何一个割切的容量，即源节点s到接收节点x, z，的最大传输速率小于或等于2。图2-3.b)是传统路由传输的情况，节点w一次只能传送l比特信息到节点d，节点d也只能传送l比特信息到接收节点x和 z,节点w和d之间的链路不得不使用了二次，接收节点x和z总共收到3比特信息，平均传输速率是15比特单位时
25、间。采用传统路由传输情况，发送者达不到最大流限。图2-3.c)是网络编码传输的情况，这里采用异或(模2和)的编码方案。中间节点w输入信息流进行编码，将编码的结果传送到节点d，再传送给接收节点x, z。接收节点x，根据自身己收到的信息a和，可以通过解码解出b。同理，接收节点z也能通过解码出a的完整的信息，这样所能达到的平均速率是2比特单位时间，发送者可以达到网络的最大流限。2.2 几种常见的网络编码构造方法 在网络传输中应用网络编码技术，在每个节点如何进行编码组合，相应的网络编码构造方法至关重要。如果网络节点对传输的信息进行线性操作, 则称为线性网络编码,否则称为非线性网络编码。根据网络编码系数
26、的选取，主要分为确定性网络编码和随机网络编码。确定性网络编码中网络节点对信息符号进行组合的系数是确定产生的，而随机网络编码的组合系数通常随机选取。本章介绍了几种常见的网络编码构造方式，这也是我们后面算法的基础。2.2.1 网络编码的前提假设Li等人提出，通用的网络编码方法可以通过简单的线性运算实现，即节点的输出信息流是输入信息流的线性组合，因此这种编码方法称为线性网络编码。下面介绍的几种形式的网络编码都是基于这一简单的思想，只是编码的构造过程不同。为了简化计算我们要作如下假设：(1)传输网络是非循环网络(2)容量为n的路径可以看作是n条单位容量路径的并联。(3)网络中不存在传输错误，只存在由于
27、节点和链路的无效造成的信息丢失。(4)每条边传输信号的时延相同。(5)多个源节点的网络可以看成只有一个虚拟源节点的网络。假设解释：为了简化问题的表示与描述，假定传输网络中没有环路的存在，这也是无时延网络的前提条件；通过选择一个非常小的单位容量，使每两个节点中间都有整数条路径连接。这样在下面讨论两个节点之间的容量的时候就可以用两个节点之间的单位路径数量来衡量，且单位路径在单位时间内传输单位信息；假设理想情况，取消了网络的同步要求。在后面我们会讨论更实用的网络编码。 虚拟源的设置如图2-4。图2-4 虚拟源节点SS1S2S3网络可以通过一个虚拟源节点和一些虚拟链接，使虚拟源节点含有所有实际源节点所
28、含有的信息，而将所有实际源节点都转化成传输网络的中间节点。整个网络就从多个源节点、多个接收节点的网络转化成为单个源节点、多接收节点的网络。虚拟的方法是，将网络中实际的源看作是这个虚拟源节点连接的第一层接收节点。如果实际的源节点每次有n个信息要传送给其他节点，那么在虚拟源节点与这个实际源节点之间的链接上，信息以n个单位信息每单位时间的速率传送。相当于所有信息都是从虚拟源节点通过实际源节点传送给接收节点的。2.2.2 线性向量编码假设源节点s发出的所有信息都是d维(d是整个网络所有接收点最大流的最小值)的行向量，称为信息向量。源节点一次传送d个不同的信息，对应信息放在信息向量的对应位置上。对每个信
29、息进行标号，无论信息中间经过怎样的变化在信息向量中的位置是不变的。中间节点将所有接到的信息按照标号放在对应位置上，形成中间节点的信息向量。节点根据线性编码多播LCM(Linear-code muticast)的规则为每一条边分配一个边向量，也称为局部编码向量。边上传递的信息是节点的信息向量与局部编码向量作向量乘法之后得到的数值。每一个信息都携带一条全局编码向量。这条全局编码向量记载了某个信息在网络中经过不同的边所经历的编码的过程。中间节点发送信息的时候，首先将所有接到信息的全局编码向量合成一个d*d的矩阵。信息k的全局编码是矩阵中的第k列。该矩阵与边上的边向量根据编码规则作向量乘法，得到的d维
30、列向量就是输出信息的全局编码向量。在解码信息的时候，将所有接到的信息的全局编码组合成一个完整的矩阵F。因为所以只要解出的逆矩阵就可以解码出原始信息。 (2-5)为了方便起见，源节点的第k条边向量可以简化成仅在第k 个位置上向量的值不为0。通过这种方法源节点首次传输的信息实际是不同的单个信息而不是信息混合后的结果。定义2.1 一个通用的多播网络的线性编码(LCM)方法是，对于传输网络，V是所有节点的集合，E是所有边的集合。给每一个节点v分配一个线性空间矿，每一条边分配一个向量。源节点的向量它们之间的关系是：(1)(2)只要(3)对任何非源节点的集合，满足： (2-6)(4)节点的输出边的向量是节
31、点输入边向量的线性组合其中是线性张成的意思。是一个d维的向量空间，d是网络的最大流。(1)的意思是源节点的向量空间是d维的，就是说源节点可以同时发出d个线性无关的信息。(2)的意思是对于某一个节点发出的所有边，边上的向量都属于该点的向量空间。(3)的意思是某个非源节点的的向量空间可以由其发出的边的向量线形张成。也就是说，如果某些边是从某个非源节点发出的，那么这些向量的线性运算可以张成整个节点的线性空间。想实现这个要求就需要所有边上的向量都是d维的线性无关的向量。(4)由于有这一条限制，输出的信息包含全部的输入信息。输出信息是输入信息的线性组合，也就是说所有输入信息的混合信息。虽然信息的大小没有
32、变化，但是包含的信息量有所增加。在不增加传送的次数的前提下增加了单个信息的接受范围，由于一个信息可以被多个接收节点接收，相当于不同接收节点共用了信道。这种编码方法的评价： 满足以上方法的网络编码可以在网络无错传输的情况下，在接收节点处正确地解码出所有的信息，同时使任何一个网络中的节点达到该节点的最大流。线性向量编码可以充分利用网络资源，使每一个传输的信息都被多个接收节点接收。但是要想达到所有边向量线性无关的限制，在选择向量的时候必须将生成的向量与所有已知向量比较，确定任意维的向量之间都是线性无关的。当网络的容量很大的时候，由于任意n维向量所组成集合的数量随着网络的边数成指数形式增长，验证的工作
33、量是很大的，因此将线性向量编码应用到大型网络中是不现实的。2.2.3 线性代数编码Koetter和Medard从代数构造角度出发，给出了实现线性网络编码的全局编码向量所必须满足的条件。在这种表示方法中，引入了系统转移矩阵来描述输入变量与输出变量之间的关系。设节点s是网络中的唯一源节点，源节点s的输出表示为。同时，用来表示接收节点s的输入。则输入变量和输出变量之间的关系我们就可以表示为，其中就称为系统转移矩阵。所以，要想在接收节点由接收到的消息向量z得到源节点输入，则必须要求系统转移矩阵的行列式不为0。那么，剩下的问题就是如何求得系统转移矩阵？下面首先给出线性网络编码的代数描述。定义2.2:设是
34、无延迟的通信网络。如果对于网络中的每一条边上的随机过程均满足 (2-7)在接收节点处有： (2-8)其中，的取值为有限域中的元素。称这样的无延迟的通信网络为线性网络。定义23：式(2-7)和式(2-8)中的系数，被称为局部编码向量。定义24：组播通信网络中，信源节点的输入可以看作是有限域上的向量。由于采用线性网络编码，则边上携带的信息是信源输节点入符号向量的线性组合，用一个向量来表示，称其为全局编码向量。则有： (2-9)可以着出，全局编码向量和局部编码向量之间的关系是: (2-10)式(2-10)表示全局编码向量与局部编码向量之间的关系，描述出了若要在一个通信网络中实现网络编码，网络中的各个
35、节点上需要进行的各种操作。定义2.4：任意通信网络的邻接矩阵，其中的元素为： (2-11)则邻接矩阵是一个的的矩阵，它直接反映了通信网络的拓扑结构。定义2.5:任意通信网络的信源输出矩阵，其中的元素为： (2-12)它是一个阶矩阵，反映了源节点的输出情况。定义2.6：任意通信网络的接收节点输入矩阵定义为： （2-13）它是一个阶矩阵，反映了某个接收节点对信息的接收情况。式(2-11)、式(2-12)、式(2-13)中矩阵,和都用编码向量来表示，它们反映了整个通信网络的信息输入输出情况和整个拓扑结构的情况。其次给出系统转移矩阵的表达式。定理2.7：在给定了一个表示网络的矩阵，后，可以得到这个网络
36、的系统的转移矩阵为： (2-14)其中，一个的单位矩阵。证明：矩阵与矩阵、对整个转移矩阵不起根本性的作用，它们只是输入与输出随机过程的一个线性组合。为了找到在一个输入随机过程与输出随机过程间连接关系，必须沿着所有经过的路径记录随机过程所经历的所有变化，并最终转化为。在网络中节点间的路径的变化可以用序列来表示。其中矩阵是一个上三角矩阵，最终将会有一个N使得为一个全零矩阵。又因为，又有。所以得到，反映了源节点的信息在网络的传输过程中由于经过网络编码而引起的影响。定理得证。由以上的叙述可以得到以下重要定理：定理28：给定一个线性网络，以下的三个命题是等价的：(1)一个组播传输是可解的。(2)可以达到
37、图G上由最小割-最大流定理得到的容量限。(3)转移矩阵的行列式在环非零。只要根据约束条件，系统转移矩阵的行列式不为0，确定出上式中的满足条件的变量，也就是得到了局部编码向量，就完成了这个通信网络的线性网络编码。这种编码方法的评价：代数编码方法适用于动态网络，优点在于编码调整时的灵活性。当网络拓扑改变的时候，网络编码矩阵不需要整体改动，只需要局部调整编码系数，令网络的转移矩阵对于所有接收节点都有解即可适应新的网络结构。同时代数编码抵抗网络变化的能力更高，也就是鲁棒性很好，尤其是对节点和链路丢失的错误情况。因为链路的丢失意味着在全局编码矩阵中，边上的局部编码为0。由于网络转移矩阵的行列式值由多个局
38、部编码联合作用得到，其中几个值为0有可能不会影响到所有接收节点。仍然有接收节点可以解码出全部信息。同时网络局部编码系数也不需要太大的改变，因此称代数编码对于网络链路的丢失有一定的鲁棒性。但是这种方法由于需要每一个节点知道网络的全局拓扑，因而并不能完全在实际网络上应用。2.2.4 随机网络编码实际网络中，由于网络拓扑的变化和网络规模的扩大，每一个无线节点获取整个网络结构信息和网络中各个节点的编码系数是不容易实现的。针对这一问题，Ho等人提出了一种随机网络编码的思想。随机网络编码思想的系数构造中，可以让节点携带一个全局编码向量，在经过每一个节点的时候都根据该节点的编码方式在改变信息的同时改变编码向
39、量。这样当接收节点接到信息的时候不需要知道整个网络的拓扑和网络的编码情况，只要接到信息的全局编码向量组成的矩阵维数d(一次发送信息的数量)就可以解码出全部的d个信息。这样接收节点就不需要知道网络拓扑。图2-5举例说明了随机网络编码的思想。(1, 2, 3)(4, 5, 6)Random LinearNetwork Coding(6, 9, 12)图2-5 随机网络编码思想举例图2-5中，中间节点接收到信息编码组合包和。此时，中间节点将应用随机网络编码的思想发送信息包，这就需要在一个有限域中随机选取新的编码系数(图2-5例中选取的编码系数为2、1)，并对编码组合后的信息包包进行新的编码运算得到新
40、的编码系数为6,9,12，将新的编码组合包传输发送。该方法不需要考虑网络拓扑结构，并适合在分布式的网络中使用。应用随机网络编码发送，当节点收到满足线性可解条件的编码组合，即可使用解线性组合的方法获得原始信息包。随机网络编码同时规定，中间节点在分配局部编码向量的时候只需要在有限域中随机选取系数，不需要验证是否相关。当然这样的结果是在接收节点可能出现的线性相关的向量从而使接收节点解码失败。对于可行的多播网络，带有独立或线性相关的源，当所有的系数都在有限域中独立随机地选择时，所有的接收节点都能够解码出信息的可能性至少是，其中d是接收节点的个数，q是系数选择的范围即字母表的大小，v是满足以下条件的边的
41、最大数量，该条件为：边上传递的信息来自所有源节点，同时可将信息传到任何一个接收节点。由此可见，网络传输的失败率与网络的尺寸成反比，传输失败率与编码之后码字的长度成指数关系减少。这样只要根据网络的大小和信息多少，估算出传输需要的中间边的数量就可以适当的选择合适的字母表大小，在网络的稳定性与网络传播冗余量之间作出选择。对于线性相关的网络，这种算法也不需要源节点知道其他源节点的信息。与传统路由方法相比，对于源节点增加减少和网络拓扑的变化等问题，随机网络编码更加灵活。2.3 本章小结本章阐述了网络编码的概念、原理，并且对几种常见的网络编码的构造方法做了归类，同时也分析了这几种常见的网络编码方案的优缺点
42、，对当前基于网络编码的无线传输技术研究作了综述。第3章 基于随机网络编码的无线广播重传方案的设计无线广播传输中，为了保证无线链路的可靠性，多个接收节点中任意一个节点丢失的信息包都要求源节点重新传送数据包以实现差错控制，需要较高的信道占用率和较多的重传次数。本章针对无线传输中的广播重传问题，研究了如何应用网络编码的思想组合多个接收节点上的不同丢失信息包进行重传发送，提出了一种基于随机网络编码的无线广播重传策略，该策略对传输信息包进行分批重传处理，采用随机线性网络编码解码的方法保证每一信息包批次内的重传可解性，相比起原有策略显著的提高了重传性能。尽管该策略需要对批次内的信息包进行延时等待，但重传性
43、能可以达到每个信息包批次内的重传最优性。3.1 随机网络编码的实现在这一部分，我们首先介绍了随机线性网络编码的基本思想，然后阐述了节点如何构造随机线性网络编码信息包的策略思想，最后分析了随机线性网络编码包在接收节点的解码操作和可解性条件。络中所有节点对其输入信息进行线性操作，称为线性网络编码，如果线性系数是随机产生的则称为随机线性网络编码。图3-1说明了普通传输方法与应用随机线性网络编码的传输方法的比较。如图所示，节点R需要发送信息包，。图3-1.a)表示传统的发送方法：发送节点要逐一广播待发送的信息包,接收节点也逐一接收各个信息包，完成节点间的数据传输过程。图3-1.b)表示应用了随机线性网络编码思想的信息包的传输方法。节点R不再仅具有存储转发功能，而是具有编码功能，其可以再一个有限域中选取随机系数、，通过编码运算得到、三个编码信息包，同时把随机编码系数、写入编码组合包，节点R广播逐一发送各编码组合包。接收节点X和Y在完整接收到3个编码组合包以后，将会获得： (3-1) (3-2) (3-3)节点X(或者节点Y)联合式(3-1)、式(3-2)和式(3-3)，将得到一个包含三个方程的方程组，其中编码系数、在编码组合包中为已知，三个方程有三个未知数(,)，具有可解性，节点X(或者节点Y)可以通过解方程组运算操作解出原始信息包,。
