基于网络编码的无线广播重传方案的研究毕业论文

1、本科毕业设计（论文）基于网络编码的无线广播重传方案的研究2011年6月本科毕业设计（论文）基于网络编码的无线广播重传方案的研究学 院： 专 业： 学生姓名： 学 号： 指导教师： 答辩日期：2011-6-25 xx大学毕业设计（论文）任务书学院： 系级教学单位： 学号学生姓名专 业班 级题目题目名称基于网络编码的无线广播重传方案的研究题目性质1.理工类：工程设计 （ ）；工程技术实验研究型（ ）；理论研究型（ ）；计算机软件型（ ）；综合型（ ）2.文管理类（ ）；3.外语类（ ）；4.艺术类（ ）题目类型1.毕业设计（ ） 2.论文（ ）题目来源科研课题（ ） 生产实际（ ）自选题目（ ）

2、主要内容 重传是无线网络广播传输中实现错误处理的重要技术。普通重传方法通常逐一发送丢失包来进行错误处理。本课题研究网络编码在无线广播重传中的应用，设计一种适用于单源多宿无线广播网络的、基于网络编码的重传方案，从而利用网络编码的特性，降低重传次数，提高传输特性。利用matlab对所设计方案进行仿真实验。基本要求1通过学习相应书籍和查阅资料，熟悉随机线性网络编码的基本理论2了解现有的无线广播数据重传方案。3设计出一种基于网络编码的重传方案4基于matlab仿真，分析方案性能。参考资料1网络编码理论与技术 杨义先主编 国防工业出版社 20092高损耗无线网络中基于网络编码的广播重传策略，中南大学学报

3、(自然科学版)，2008，39(6)3一种低丢包率无线网络中基于网络编码的广播重传方法 小型微型计算机系统2009，30(6)4中国期刊网上的关于网络编码的文章周 次第1 4 周第5 8 周第 912 周第1316 周第17 18 周应完成的内容收集资料熟悉课题内容确定设计思路熟悉程序设计语言，确定算法的实现方案编写程序实现设计方案上机调试并进行优化实验结果整理和总结撰写论文课题总结答辩指导教师：职称： 2011年 2 月28 日系级教学单位审批： 年 月 日摘要在无线网络广播的重传处理中，多个接收节点中的任意一个节点丢失信息包都要求源节点重传数据包，这就需要源节点广播发送较多的重传次数。本文

4、将随机线性网络编码技术应用在无线网络广播重传中，设计了一种基于随机线性网络编码的无线广播重传方案。在该方案中，源节点需记录多个接收节点中丢失信息包的数量最多的接收节点的丢包数量，再按照随机线性网络编码的方法编码组合该丢包数量个线性编码信息包；源节点广播重传线性编码组合包；接收节点采用运算编码线性组合的方法获得信息包数据。数学分析表明，该方法能保证所有接收节点的编码可解性，同时重传次数可达到理论最优性；模拟测试结果表明：与传统重传方法相比，应用随机线性网络编码的重传方案有效地减少了信息包的平均传输次数，提高了传输效率关键词无线广播；网络编码；随机线性网络编码；重传abstractin wirel

5、ess broadcasting retransmission, any node of multi-nodes request the retransmission of information packets. this approach always needs large mounts of broadcasting packets. this paper designs an approach in wireless broadcasting networks based on random linear network coding. firstly, source node wi

6、ll send linear coding packets based on the largest mounts of lost packets in received nodes. then, received nodes will decode lost packets with network coding theory mathematic analysis reveals that our approach can ensure the solvability in the received nodes, and have optimization performance in w

7、ireless retransmission. simulation results indicate that compared with existing approach; the approach in this paper can effectively reduce the average number of transmissions and advance the transmission efficiencykeywordswireless broadcasting; network coding; random linear network coding; retransm

8、ission 目 录摘要iabstractii第1章 绪论11.1 课题背景及意义11.2 本课题国内外的研究现状21.3 本课题研究的主要内容41.4 本文的章节安排4第2章 基于网络编码的无线传输的分析62.1 网络编码的概念与定义62.1.1 网络编码的基本原理62.1.2 最大流-最小割定理82.2 几种常见的网络编码构造方法102.2.1 网络编码的前提假设102.2.2 线性向量编码122.2.3 线性代数编码132.2.4 随机网络编码162.3 本章小结18第3章 基于随机网络编码的重传方案的设计193.1 随机网络编码的实现193.2 无线广播重传模型的建立213.3 随机线

9、性网络编码包的构造223.4 编码可解性的证明233.5 信息包的分批重传243.6 重传机制的描述253.7 具体重传过程263.7.1 重传方案描述263.7.2 实际重传方案描述283.8 本章小结32第4章 应用随机线性网络编码性能分析334.1 数学理论分析334.2 模拟测试分析334.3 本章小结35结论36参考文献37致谢39第1章 绪论近年来，随着无线技术的成熟，越来越多的人通过无线方式连接到互联网上。与此同时，由于用户数量的陡然增多、用户对网络服务需求的多样性以及用户对传输质量要求的不断提高，如何保障无线链路的可靠安全传输、优化无线网络性能、在现有网络资源的基础上提高网络资

10、源的利用率等问题已成为当今无线网络通信研究的重要课题之一。1.1 课题背景及意义数据广播业务在蜂窝网络和无线mesh网络中的应用越来越广泛，自动重复重传(automatic repeat request, arq)已经成为无线通信环境下的提供可靠通信的重要容错手段。普通的自动重复重传机制主要包括：停止-等待自动重复重传(sw-arq)、返回n型自动重复重传(gbn-arq)和选择自动重复重传(sr-arq)1。尽管自动重复重传应用于点对点传输确实可以达到较高的传输性能，然而对于多用户的广播、组播传输，其性能会随接收节点数目的增加而迅速下降2。2000年，香港中文大学的a. rhlswede等基

11、于网络流的概念率先提出了网络编码3这一概念，其精髓来源于著名的max-flow min-cut（最大流最小割）理论4。网络编码是指网络节点既实现路由功能又实现编码功能。利用无线信道的广播特性，网络编码被应用于提高无线网络性能、提高吞吐量、安全性等。同时网络编码也为无线广播重传提供了一种途径。2006年，nguyen等人将网络编码技术应用于重传策略中，提出了两个接收节点的编码重传策略，减少了平均传输次数，但nguyen等人的策略仅考虑了两个接收节点的情况且没有提出具体的编码方案。网络广播中应用普通的重传策略，在较高的出错率的情况下会产生两个方面的问题5：广播传输中丢失信息包较多，需要数量较大的重

12、传次数；重传信息包再次丢失，需要次数较大的再次重传。因此如何利用现有的网络资源来提高重传效率成为研究的热点。现在推广到多个接收节点的情况下，将网络编码与广播重传相结合以减少重传次数、提高重传效率。因此，研究将网络编码应用于单源多宿的无线广播网络中以降低重传次数是很有必要的。1.2 本课题国内外的研究现状无线传输中的广播信道特性，使得网络编码在减少无线传输次数方面有很好的应用，近年来出现了很多相关的研究。wu等人提出了利用网络编码减少信息包互换传输次数的方法6，bin等人提出了网络编码寻找无线mesh网最少传输次数路径的思想。katti等人构造了无线mesh网络使用网络编码的体系结构cope，并

13、利用29个节点的实验平台证实能显著减少平均传输次数。chachulski等人则提出无线路由协议more，并证实该协议能有效减少信息包的平均发送次数。同时，与传统的有线网络相比，无线网络拥有较高的比特出错率，重传效率问题显得更加重要。目前的研究现状来看，国外在无线传输技术中引入网络编码的研究起步较早。国外多所著名大学如麻省理工学院、普林斯顿大学、多伦多大学、瑞士epfl学院等和多家it公司的研究中心，包括微软研究所、贝尔实验室、at&t的香农信息实验室等都在积极开展相关的研究7。目前国外在无线传输技术中引入网络编码的研究主要侧重在二个方面：改善无线传输吞吐量和能量利用效率、保证无线链路的可靠传输

14、和安全性。在无线传输吞吐量研究上，a.rhlswede等人指出网络编码可以达到组播传输理论最大流速；li等人kotter等人8先后证明线性网络编码、随机网络编码同样可以达到组播传输理论最大流速、并对网络编码的数学框架进行了阐述，为网络编码在无线组播传输吞吐量方面的研究提供了必要的理论条件。在能量利用效率方面，wu等人证明在无线网络组播时应用网络编码，可以将最小化每位数据能量消耗问题归结为线性问题，为能量利用效率方面的研究提供了基础。kari等人证实了局部混合网络编码的传输，在tcp和udp传输流的环境下均可以显著提高传输吞量；wu等人接下来研究了基于局部混合网络编码互换传输的性能，证明了互换传

15、输可以优化传输性能，这些研究均为局部混合网络编码传输提供了理论基础和条件。无线网络由于环境的多变性，使得数据包在传输中更加容易丢失，传输中的重传技术研究非常必要。当前应用网络编码的重传技术研究主要涉及二个接收节点情况下的编码发送重传。从目前的研究现状来看，国内在无线传输中引入网络编码的研究起步较晚，中科院软件研究所、清华大学、中国科技大学、国防科技大学、上海交通大学、华中科技大学等高校均有相关的研究组进行该课题有关的领域研究。在无线组播传输性能研究、多源信息交换传输、p2p数据流传输、卫星技术中的组播传输、无线网络的动态网络编码协助通信等方面，国内均进行了相关的研究。从当前的国内外研究情况来看

16、，基于网络编码的无线传输技术的核心思想仍然是通过增加节点的编码(计算)能力来换取网络传输增益。一方面网络编码进行的运算复杂度相对来说较低，另一个方面来看，相比网络传输增益，节点计算代价和延时是可以接受的。网络编码技术的提出只有10年的时间。a.rhlswede等人首先提出网络编码这个概念。他们的工作主要针对单个源点，多个接收点的信息传输问题，证明了在源点发送能力无限的情况下，一个网络的最大信息传送率等于该网络的最小割的容量也就是网络的最大流。将信息传输与图论的最大流最小割理论联系在一起。这也是第一次提出通信网络的容量问题。a.rhlswede等人仅给出了网络最大信息传送速率的存在性证明，并没有

17、给出具体的网络编码实现方式。li，yeung和cai提出单一源，多接收点网络的最大传输速率可以通过线性编码实现9。通过一个广泛适的线性编码多播算法(lcm)，每个接收节点都可以应用无线网络编码达到其最大流。lcm主要应用于非循环网络。lcm规则为每条边分配边向量，每个节点分配向量空间。边向量与点向量空间按照lcm规则满足一定的关系通过边向量和节点上的信息向量相乘对信息编码，在接收节点处使用逆矩阵解码。lcm方法可以达到任意节点的最大流。但由于lcm规则过于严格，寻找符合规则的向量需要大量的时间，造成了网络的延时，因此lcm不适合用在实际网络中。koctter等人为网络解码设计了一个数学框架。它

18、将一般的网络编码寻找线性解的方法简化成为寻找多元多项式的非0解。同时寻找编码系数的方法也通过代数编码方式而简化了。针对多播信息传输问题，ho等人设计了一种不需要知道网络节点分布情况的随机运算法则，通过在字母表中随机选取系数实现网络编码。psanders等人提出了一种实现网络编码的多项式时间算法。这种方法将网络编码的构造进一步简化，它也是在己知拓扑的情况下，首先通过最大流最小割算法找到完成组播所需的路径的集合，在找出的这个子图上，再自上而下的确定各个节点所需要进行的操作。这种方法不但把网络编码构造的复杂度从指数级降到了多项式级，而且大大降低了网络编码中所采用的字母表的下限。另外，人们对网络编码在

19、提高网络性能方面的应用做了大量的研究。研究表明，网络编码除了能够提高系统的容量外，在数据压缩、负载均衡、降低节点能量消耗、减少传播时延、提高网络健壮性等方面都有重要的应用前景。1.3 本课题研究的主要内容本课题的研究目标是结合网络编码的思想，设计应用于高传输损耗下的广播重传策略。传输损耗较严重的情况下无线广播传输错误率高，必须使用重传策略来进行错误处理。普通的重传策略的思想在高损耗无线网络广播中会产生两个方面的问题：丢失的信息包多需要较大的重传次数；再次丢包率较高，需较大数量的再次重传。因此，本课题研究单源节点、多个接收节点的情况下，将网络编码应用于无线广播重传问题以提高重传效率、减少重传次数

20、，为网络编码技术在实际无线传输环境中的应用提供良好的理论基础。研究的主要内容为：在了解网络编码原理的基础，了解现有的无线广播重传方案。设计了一种基于随机网络编码的无线广播重传方法。首先建立了一种接近现实环境的无线广播重传模型，构造随机线性编码包，采用与传统传处理机制不同的处理机制即分批重传信息包，以及具体的重传步骤。1.4 本文的章节安排本文通过深入理解网络编码和无线网络领域近年来的重要研究成果，对网络编码在无线传输网络中的应用进行了深入的研究。设计了一种基于网络编码的无线广播重传方案，以减少重传次数、提高重传效率，各章的内容组织如下：第1章为绪论，主要介绍了应用网络编码的无线广播传输技术的研

21、究背景和意义、国内外的研究现状以及当前主要的研究成果，并对本文的主要工作进行了论述。第2章介绍了网络编码基本原理与最大流最小割定理，在此基础上又进一步阐述了几种常见的网络编码的构造方法和它们的优缺点。并从中选择了随机网络编码进行研究设计。第3章设计了一种基于随机线性网络编码的重传方案。首先建立了接近现实环境的无线广播模型，构造了随机网络编码包，具体的描述了重传过程以及重传机制。第4章用表与图两种形式展现了接收节点在不同的丢包率的情况下应用随机线性网络编码的重传方法与传统的方法在总的传输次数的比较，充分的证明了应用随机线性网络编码的重传方法减少了重传次数，提高了传输效率。第2章 基于网络编码的无

22、线传输的分析网络编码从广义上讲是网络中的节点将接收到的信息进行编码后再转发出去的多点传送技术。网络编码理论彻底改变了传统的存储转发性能，可以达到最大流传输的理论极限。而随机网络编码理论将网络编码的应用延伸到任意网络结构中。随机网络编码在无线网络中的应用更是因此得到了长足的发展。本章将首先介绍网络编码的基本理论，然后将引出随机网络编码在无线网络中的一般模型和方法为后续的章节的展开做好铺垫2.1 网络编码的概念与定义 网络编码(network coding)是一种融合编码和路由的信息交换技术，在传统存储转发路由方法基础上，通过允许对接收的多个数据包进行信息编码融合，增加单次传输的信息量，提高网络整

23、体性能。网络编码的本质是利用节点的计算能力提高链路带宽的利用率10。2.1.1 网络编码的基本原理 xyzyxzxyzf1(x, y, z)f2(x, y, z)f3(x, y, z)节点n节点na) 传统路由方法b) 网络编码的路由方法图2-1 网络编码概念描述如图2-1所示，节点是网络中的一个节点，其收到来自不同链路的信息包、并需要对信息包进行传输发送处理。如图2-1 a)所示在传统的计算机网络中，每个节点（可以是交换机或路由器），在存储转发模式下，节点只进行数据分组的路由和复制。而不同于传统网络，具有网络编码功能的节点则会对数据包进行编码/解码运算，如图2-1 b)，交换机输出的信息流是

24、其输入的信息流的函数。采用传统路由方法，节点仅需要对收到的信息包进行存储和转发，节点的发送信息包为、。采用网络编码，节点可以对收到的信息包进行编码运算，通过运算信息包、获得信息包、，新信息包是来自不同链路收到信息包的编码组合。此时，若通过网络编码进行发送，节点实现了对接收的多个数据的编码信息融合操作，即网络编码操作。传统网络的存储转发模式可看作网络编码的特例。为了便于网络编码理论的分析阐述，我们仅考虑组播情况并且建立相应的网络模型，模型中假设边的带宽为单位容量，允许节点间存在多条边，并忽略边的传输错误及延时。传统网络分析中，通信网络中的信息流被认为是网络管道中的流体，类似于水在渠道中流动一样。

25、对于一个实际的通信网络，我们可以采用一个有向图来加以描述和研究11。对于图，这里表示节点的集合，表示边的集合。网络中一条边用表示，这里，为网络中的两个节点。若图仅有一个源节点和一个接收节点，且有向图中的每一条边对应着一个非负数，并令其为该边的容量，则称该有向图为网络流图。对于网络流图每一条边都给定一个非负数，这一组数满足下列两个条件时称为这网络的可行流，表示为： (2-1)(1)每一条边,有。(2)除了源节点和接收节点 以外的所有的节点，恒有等式(2-2): (2-2)这表示中间节点的流量是守恒的，即节点的输入的流量和输出的流量是相等的。(3)源节点和接收节点满足公式(2-3): (2-3)其

26、中称作网络流的流量，而且从源节点流出的总量等于流入接收节点的总量。当时便称边饱和，或饱和，表示流对该边已饱和。该网络的最大流是指从源节点送往接收节点的流量的最大值，用表示。设为节点集合的一个子集，使得s，把一个端点属于而另一个端点不属于的边的集合称作源节点和接收节点的一个割。割的容量的定义为集合中包含所有边的容量的和，用表示，即式(2-4)： (2-4)2.1.2 最大流-最小割定理网络编码通过允许对来自不同链路的信息进行编码组合，从而提高网络性能，在这种全新的体系结构下，网络性能可以达到最大流传输的理论极限。最大流-最小割定理：对于已知的网络流图，从信源节点到接收节点的流量的最大值等于其最小

27、割的容量，即式（2-5）： (2-5)对于有向网络，可以用ford-fulkerson算法来求解网络的最大流。对于网络信息流，为一个多播网络，为信息从信源到信宿的多播传输速率。令信源节点到接收节点的最大流值为，则对于所有的，有式(2-6)： (2-6)即 (2-7)将这个称作网络多播传输的最大流限。如图2-2所示，图中给出了最大流最小割定理的一个实例，图中从信源节点到接收节点的流量最大值等于信源节点到接收节点的最大割集，即有： (2-8)图2-3所示的蝴蝶网络12是网络编码实现最大流传输的例子。图中假设网络中各条链路无差错和无时延，源节点通过网络将l比特信息和传输到接收节点和，所有的链路容量均

28、为l。satcb3242443图2-2 最大流最小割定理实力由图2-3 a)的网络链路容量图，可以得知： (2-9) 由最大流最小割定理有： (2-10)由图论中的点对点的最大流最小割定理，对于已知的网络流图2-3 a)，从源节点到接收节点的流量的最大值小于或等于任何一个割切的容量，即源节点到接收节点,的最大传输速率小于或等于2。图2-3 b)是使用传统路由传输的情况，节点一次只能传送l比特的信息到节点，节点也只能传送l比特的信息到接收节点和,节点和之间的链路不得不被使用了二次，接收节点和总共收到3比特信息，平均的传输速率是1.5比特/单位时间。采用传统路由传输的情况，发送者达不到最大流限。图

29、2-3 c)是网络编码传输的情况，这里采用异或(模2和)的编码方案。中间节点输入信息流进行编码，将编码的结果传送到节点，再传送给接收节点,。接收节点，根据自身己收到的信息和，可以通过解码解出。同理，接收节点z也能通过解码出的完整的信息，这样所能达到的平均速率是2比特/单位时间，发送者可以达到网络的最大流限。suvwdxzsuvwdxzsuvwdxz111111111ababaa/bbababaabbabababa) 网络链路容量b) 传统路由传输c) 网络编码传输图2-3 经典网络编码原理图2.2 几种常见的网络编码构造方法 在网络传输中应用网络编码技术，在每个节点如何进行编码组合，相应的网络

30、编码构造方法至关重要。如果网络节点对传输的信息进行线性操作, 则称为线性网络编码,否则称为非线性网络编码12。根据网络编码系数的选取，主要分为确定性网络编码和随机网络编码。确定性网络编码中网络节点对信息符号进行组合的系数是确定产生的，而随机网络编码的组合系数通常随机选取。本章介绍了几种常见的网络编码构造方式，这也是我们后面算法的基础。2.2.1 网络编码的前提假设li等人提出，通用的网络编码方法可以通过简单的线性运算实现，即节点的输出信息流是输入信息流的线性组合，因此这种编码方法称为线性网络编码。下面介绍的几种形式的网络编码都是基于这一简单的思想，只是编码的构造过程不同。为了简化计算我们要作如

31、下假设13：(1)传输网络是非循环网络(2)容量为的路径可以看作是条单位容量路径的并联。(3)网络中不存在传输错误，只存在由于节点和链路的无效造成的信息丢失。(4)每条边传输信号的时延相同。(5)多个源节点的网络可以看成只有一个虚拟源节点的网络。假设解释：为了简化问题的表示与描述，假定传输网络中没有环路的存在，这也是无时延网络的前提条件；通过选择一个非常小的单位容量，使每两个节点中间都有整数条路径连接。这样在下面讨论两个节点之间的容量的时候就可以用两个节点之间的单位路径数量来衡量，而且单位路径在单位时间内传输单位信息；假设理想情况，取消了网络的同步要求。在后面我们会讨论更实用的网络编码。 网络

32、可以通过一个虚拟源节点和一些虚拟链接14，使虚拟源节点含有所有实际的源节点所含有的信息，而将所有实际的源节点都转化成传输网络的中间节点。整个网络就从多个源节点、多个接收节点的网络转化成为单个源节点、多接收节点的网络。虚拟源的设置如图2-4：ss1s2s3图2-4 虚拟源节点虚拟的方法是，将网络中实际的源节点看作是这个虚拟源节点连接的第一层接收节点。如果实际的源节点每次有个信息要传送给其他节点，那么在虚拟源节点与这个实际的源节点之间的链接上，信息以个单位信息每单位时间的速率传送。相当于所有信息都是从虚拟源节点通过实际的源节点传送给接收节点的。2.2.2 线性向量编码假设源节点发出的所有信息都是维

33、(是整个网络所有接收点最大流的最小值)的行向量，称为信息向量15。源节点一次传送个不同的信息，对应信息放在信息向量的对应位置上。对每个信息进行标号，无论信息中间经过怎样的变化在信息向量中的位置是不变的。中间节点将所有接到的信息按照标号放在对应位置上，形成中间节点的信息向量。节点根据线性编码多播lcm(linear-code muticast)的规则为每一条边分配一个边向量，也称为局部编码向量16。边上传递的信息是节点的信息向量与局部编码向量作向量乘法之后得到的数值。每一个信息都携带一条全局编码向量。这条全局编码向量记载了某个信息在网络中经过不同的边所经历的编码的过程。中间节点发送信息的时候，首

34、先将所有接到信息的全局编码向量合成一个的矩阵。信息的全局编码是矩阵中的第列。该矩阵与边上的边向量根据编码规则作向量乘法，得到的维列向量就是输出信息的全局编码向量。在解码信息的时候，将所有接到的信息的全局编码组合成一个完整的矩阵。因为所以只要解出的逆矩阵就可以解码出原始信息。 (2-11)为了方便起见，源节点的第条边向量可以简化成仅在第个位置上向量的值不为0。通过这种方法源节点首次传输的信息实际是不同的单个信息而不是信息混合后的结果。定义2.1 一个通用的多播网络的线性编码(lcm)方法是，对于传输网络，是所有节点的集合，是所有边的集合。给每一个节点分配一个线性空间，每一条边分配一个向量。源节点

35、的向量它们之间的关系是：(1)；(2)只要；(3)对任何非源节点的集合，满足： (2-12)式中 线性张成的意思；是一个维的向量空间，是网络的最大流。(4)节点的输出边的向量是节点输入边向量的线性组合。(1)的意思是源节点的向量空间是维的，就是说源节点可以同时发出个线性无关的信息。(2)的意思是对于某一个节点发出的所有边，边上的向量都属于该点的向量空间。(3)的意思是某个非源节点的向量空间可以由其发出的边的向量线形张成。也就是说，如果某些边是从某个非源节点发出的，那么这些向量的线性运算可以张成整个节点的线性空间。想实现这个要求就需要所有边上的向量都是维的线性无关的向量。 (4)由于有这一条限制

36、，输出的信息包含全部的输入信息。输出信息是输入信息的线性组合。虽然信息的大小没有变化，但是包含的信息量有所增加。在不增加传送的次数的前提下增加了单个信息的接收范围，由于一个信息可以被多个接收节点接收，相当于不同接收节点共用了信道。这种编码方法的评价：满足以上方法的网络编码可以在网络无错传输的情况下，在接收节点处正确地解码出所有的原始信息，同时也可以使任何一个网络中的节点达到该节点的最大流。但是要想达到所有边向量线性无关的限制，在选择向量的时候必须将生成的向量与所有已知向量比较，确定任意维的向量之间都是线性无关的。当网络的容量很大的时候，由于任意维向量所组成集合的数量随着网络的边数成指数形式增长

37、，验证的工作量很大，因此将线性向量编码应用到大型网络中是不现实的。2.2.3 线性代数编码koetter和medard从代数构造角度出发，给出了实现线性网络编码的全局编码向量所必须满足的条件。在这种表示方法中，引入了系统转移矩阵来描述输入变量与输出变量之间的关系17。设节点是网络中的唯一源节点，源节点的输出表示为。同时，用来表示接收节点的输入。则输入变量和输出变量之间的关系我们就可以表示为，其中就称为系统转移矩阵。所以，要想在接收节点由接收到的消息向量得到源节点输入，则必须要求系统转移矩阵的行列式不为0。那么，剩下的问题就是如何求得系统转移矩阵？下面首先给出线性网络编码的代数描述。定义2.2：

38、设是无延迟的通信网络。如果对于网络中的每一条边上的随机过程均满足 (2-13)在接收节点处有： (2-14)其中，的取值为有限域中的元素。称这样的无延迟的通信网络为线性网络。定义23：式(2-13)和式(2-14)中的系数，被称为局部编码向量。定义24：组播通信网络中，信源节点的输入可以看作是有限域上的向量。由于采用线性网络编码，则边上携带的信息是信源节点输入符号向量的线性组合，用一个向量来表示，称其为全局编码向量。则有： (2-15)由式(2-15)可以看出，全局编码向量和局部编码向量之间的关系是: (2-16)式(2-16)表示全局编码向量与局部编码向量之间的关系，描述出了若要在一个通信网

39、络中实现网络编码，网络中的各个节点上需要进行的各种操作。定义2.4：任意通信网络的邻接矩阵，其中的元素为 (2-17)则邻接矩阵是一个的的矩阵，它直接反映了通信网络的拓扑结构。定义2.5：任意通信网络的信源输出矩阵，其中的元素为： (2-18)它是一个阶矩阵，反映了源节点的输出情况。定义2.6：任意通信网络的接收节点输入矩阵定义为： (2-19)它是一个阶矩阵，反映了某个接收节点对信息的接收情况。式(2-17)、式(2-18)、式(2-19)中矩阵,和都用编码向量来表示，它们反映了整个通信网络的信息输入输出情况和整个拓扑结构的情况。其次给出系统转移矩阵的表达式。定理2.7：在给定了一个表示网络

40、的矩阵，后，可以得到这个网络的系统的转移矩阵为： (2-20)其中，一个的单位矩阵。证明：矩阵与矩阵,对整个转移矩阵不起根本性的作用，它们只是输入与输出随机过程的一个线性组合。为了找到在一个输入随机过程与输出随机过程间的连接关系，必须沿着所有经过的路径记录随机过程所经历的所有变化，并最终转化为。在网络中节点间的路径的变化可以用序列来表示。其中矩阵是一个上三角矩阵，最终将会有一个使得为一个全零矩阵。又因为，又有。所以得到，反映了源节点的信息在网络的传输过程中由于经过网络编码而引起的影响。定理得证。定理2.8：给定一个线性网络，以下的三个命题是等价的：(1)一个组播传输是可解的。(2)可以达到图g

41、上由最小割-最大流定理得到的容量限。(3)转移矩阵的行列式在环非零。只要根据约束条件，在系统转移矩阵的行列式不为0的条件下，确定出上式中的满足条件的变量，也就是得到了局部编码向量，就完成了这个通信网络的线性网络编码。这种编码方法的评价：代数编码方法适用于动态网络，优点在于编码调整时的灵活性强。当网络的拓扑结构改变的时候，网络编码矩阵不需要整体改动，只需要局部调整编码系数，令网络的转移矩阵对于所有接收节点都有解即可适应新的网络结构。同时代数编码抵抗网络变化的能力更高，也就是鲁棒性很好，尤其是对节点和链路丢失的错误情况。因为链路的丢失意味着在全局编码矩阵中，边上的局部编码为0。由于网络转移矩阵的行

42、列式值由多个局部编码联合作用得到，其中几个值为0有可能不会影响到所有接收节点。仍然有接收节点可以解码出全部信息。同时网络局部编码系数也不需要太大的改变，因此称代数编码对于网络链路的丢失有一定的鲁棒性。但是这种方法由于需要每一个节点知道网络的全局拓扑，因而并不能完全在实际网络上应用。2.2.4 随机网络编码实际网络中，由于网络拓扑的变化和网络规模的扩大，每一个无线节点获取整个网络结构信息和网络中各个节点的编码系数是不容易实现的。针对这一问题，ho等人提出了一种随机网络编码的思想18。随机网络编码思想的系数构造中，可以让节点携带一个全局编码向量，在经过每一个节点的时候都根据该节点的编码方式在改变信

43、息的同时改变编码向量。这样当接收节点接到信息的时候不需要知道整个网络的拓扑和网络的编码情况，只要接到信息的全局编码向量组成的矩阵维数(一次发送信息的数量)就可以解码出全部的个信息。这样接收节点就不需要知道网络拓扑。图2-5举例说明了随机网络编码的思想。(1, 2, 3)(4, 5, 6)random linearnetwork coding(6, 9, 12)图2-5 随机网络编码思想举例图2-5中，中间节点接收到信息编码组合包和。此时，中间节点将应用随机网络编码的思想发送编码信息包，这就需要在一个有限域中随机选取新的编码系数(图2-5例中选取的编码系数为2、1)，并对编码组合后的信息包进行新

44、的编码运算： (2-21)得到新的编码系数为6,9,12，将新的编码组合包传输发送。该方法不需要考虑网络拓扑结构，并适合在分布式的网络中使用。应用随机网络编码传输，当接收节点收到满足线性可解条件的编码组合，即可使用解线性组合的方法恢复原始信息包。随机网络编码同时规定，中间节点在分配局部编码向量的时候只需要在有限域中随机选取系数，不需要验证是否相关。当然这样的结果是在接收节点可能出现的线性相关的向量从而使接收节点解码失败。对于可行的多播网络，带有独立或线性相关的源，当所有的系数都在有限域中独立随机地选择时，所有的接收节点都能够解码出信息的可能性至少是 (2-22)式中 接收节点的个数；系数选择的

45、范围即字母表的大小；满足以下条件的边的最大数量。该条件为：边上传递的信息来自所有源节点，同时可将信息传到任何一个接收节点。网络传输的失败率与网络的尺寸成反比，传输失败率与编码之后码字的长度成指数关系减少。这样只要根据网络的大小和信息多少，估算出传输需要的中间边的数量就可以适当的选择合适的字母表大小，在网络的稳定性与网络传播冗余量之间做出选择。对于线性相关的网络，这种算法也不需要源节点知道其他源节点的信息。与传统路由方法相比，对于源节点的增加或减少和网络拓扑结构的变化等问题，随机网络编码更加灵活。2.3 本章小结本章阐述了网络编码的概念、原理，并且对几种常见的网络编码的构造方法做了归类，同时也分

46、析了这几种常见的网络编码方案的优缺点，对当前基于网络编码的无线传输技术研究作了综述。第3章 基于随机网络编码的重传方案的设计无线广播传输中，为了保证无线链路的可靠性，多个接收节点中任意一个节点丢失的信息包都要求源节点重新传送数据包以实现差错控制，需要较高的信道占用率和较多的重传次数。本章针对无线传输中的广播重传问题，研究了如何应用网络编码的思想组合接收节点上的多个不同丢失信息包进行重传发送，设计了一种基于随机网络编码的无线广播重传策略，该策略对传输信息包进行分批重传处理，采用随机线性网络编码解码的方法保证每一信息包批次内的重传可解性，相比起原有策略显著的提高了重传性能。尽管该策略需要对批次内的

47、信息包进行延时等待，但重传性能可以达到每个信息包批次内的重传最优性。3.1 随机网络编码的实现在这一部分，我们首先介绍随机线性网络编码的基本思想，然后阐述节点如何构造随机线性网络编码信息包的策略思想，最后分析了随机线性网络编码包在接收节点的解码操作和可解性条件。网络中所有节点对其输入信息进行线性组合操作，称为线性网络编码，如果线性编码系数是随机产生的则称为随机线性网络编码。图3-1说明了普通传输方法与应用随机线性网络编码的传输方法的比较。如图所示，节点需要发送信息包，。图3-1 a)表示传统的发送方法：源节点要逐一广播待发送的信息包,接收节点也逐一接收各个信息包，完成节点间的数据传输过程。当节

48、点丢失某信息包时，源节点要逐一发送丢失的信息包。图3-1 b)表示应用了随机线性网络编码思想的信息包的传输方法。节点不再仅具有存储转发功能，而是具有编码功能，其可以再一个有限域中独立随机的选取系数、，通过编码运算得到： (3-1) (3-2) (3-3)三个编码信息包，同时把随机编码系数、写入编码组合包，节点广播逐一发送各编码组合包。接收节点x和y在完整接收到3个编码组合包以后，将会获得: (3-4) 节点x(或者节点y)联合式(3-4)，将得到一个包含三个方程的方程组，其中编码系数、在编码组合包中为已知，三个方程有三个未知数(,)，由矩阵论可知，当三个方程线性无关时，此方程组具有可解性，节点

49、x(或者节点y)可以通过解方程组运算操作解出原始信息包,。rxy,rxya) 传统的发送方法b) 随机线性网络编码方法图3-1 传统方法和随机线性网络编码方法的信息传输比较应用随机线性网络编码的重传方法，接收节点处理的问题由是否接收到完整的信息包的问题，转换为是否收到足够多的满足可解性条件的编码信息包的问题。通过研究发现，通过发送随机线性网络编码组合可以带来良好的吞吐量、鲁棒性、安全性等个方面的增益，为网络传输性能的改善提供了一种新的途径。对于源节点的增加或减少和网络拓扑结构的变化等问题，随机线性网络编码更加灵活。3.2 无线广播重传模型的建立无线广播重传策略的设计，需要建立一个接近现实环境的

50、无线广播重传模型。假设一具有一个广播源节点和(，本课题设计的是)个接收节点的无线广播网络，广播源节点和接收节点之间的传输链路存在损耗。假设1 传输信息包长度相同，均为比特，由编码运算中的有限域封闭计算理论，线性网络编码包的长度同样为比特。广播源以固定时间间隔()广播传送信息包(本课题设计的是有10个待发送的信息包)，广播源节点和(,本课题设计的是)个接收节点之间的传输丢包率互不相关，且服从伯努利分布，对应某个接收节点()的丢包率为。12345信息包反馈图3-2 一个源节点五个接收节点无线广播模型假设2 广播源节点传输中某个信息包发送完毕后，(,本课题设计的是)个接收节点接收并发送ack/nak

51、控制信息包反馈该信息包的接收情况。丢失情况包括：信息包是否成功接收；丢失信息包序列号和丢失节点序列号。假定ack/nak控制信息包在信道中不存在损耗。ack/nak中包含丢失包的序列号与接收节点序列号。假设3 (,本课题设计的是)个接收节点的丢失情况记录在一个广播接收状态矩阵中。矩阵中行表示接收节点的接收情况，列表示信息包接收情况。接收成功相应位置赋值为0，否则赋值为1。3.3 随机线性网络编码包的构造在编码中，把信息看作是特定基域上的向量，假定每一个信息包等长为比特(当参与编码的信息包的长度低于比特时，通过补0来实现同样长度)，由编码运算中的有限域封闭计算理论，线性网络编码包的长度同样为比特

52、。图3-3为随机线性网络编码的构造描述，其中假定源节点传输中将要发送这10个原始信息包。接收节点原始信息包源节点接收节点图3-3 随机线性网络编码构造描述在随机线性网络编码包构造中，网络节点均是在有限域上随机的选取线性编码系数。ho等人已证明，若随机编码系数都在有限域中独立随机地选择时，当有限域字母表足够大时，系数选取出现线性有关的概率会越来越小。而且，在普通的随机线性编码传输中，选取的字母表时即可以保证出现线性有关的概率忽略不计。如图3-3所示，在源节点需要构造随机线性网络编码时，源节点随机选取线性编码系数，将编码系数和原始信息包进行有限域运算获得随机线性网络编码包数据，对应编码数据为： (

53、3-5)若用分别表示随机线性网络编码包中对应的编码系数，如表示中对应的原始信息包的系数，则随机线性网络编码包中对应的系数向量为： (3-6)在随机线性网络编码包构造中，源节点通过编码运算获得编码信息包以及相应的系数向量，并发送相应的到传输链路中。3.4 编码可解性的证明当接收节点收到来自传输链路的关于原始信息包的若干个随机线性网络编码包，接收节点对应有： (3-7) 当接收节点获得式(3-7)的个编码信息包后，随机线性网络编码包的解码问题就可以转换为个关于的线性组合的可解性问题。由矩阵论中关于线性方程组具有可解性的定理可知，只有当式(3-6)中个线性组合中线性无关的线性方程组个数大于未知变量的

54、个数10时，线性方程组才具有可解性。同时，式(3-7)中个编码信息包对应原始信包的系数向量为： (3-8)由矩阵论可知，系数向量的秩即线性组合中线性无关的线性方程组个数，当时，随机线性网络编码包组合具有可解性，可以通过解码操作解出原始信息包。当目的节点收到的编码信息包满足可解性定理，即组成的系数向量的秩时，对应有： (3-9)随机线性网络编码组合的解码操作即在式(3-9)中通过收到的编码信息包组合和系数向量解出即： (3-10)接收节点通过对满足可解性的系数向量运算或得，通过式(3-10)可以解码运算获得原始信息包，完成解码操作。3.5 信息包的分批重传为将随机线性网络编码应用于无线重传策略中

55、达到重传最优性，我们需要采用与传统传处理机制不同的处理机制。信息包分批的重传处理机制的核心思想是将全部信息包分批成若干个信息包批次，将全部信息包的重传问题转换为若干个信息包批次的重传问题。假设全部参与传输的信息包的个数为，假定分批中将每个信息包视为一个信息包批次，则全部的信息包可以转换为个信息包批次的情况(若不为整数，可以补零)，此时全部的个信息包的重传问题变成了个信息包批次的重传问题。图3-4给出了信息包分批处理的描述。123412414244433441424344批次1批次11图3-4 将信息包分成信息包批次在图3-4中，全部参与传输的信息包个数。若取每个信息包分批构成一个信息包批次，此

56、时全部的信息包可以分成个信息包批次。因而，全部参与传输44个信息包的重传问题就转换成个信息包批次的重传问题。本课题只考虑一个信息包批次的重传，信息包批次内含有10个信息包。3.6 重传机制的描述综合随机线性网络编码应用于无线传输方案的状态报告包的定义,随机线性编码重传包的定义和随机线性网络编码方案的源节点编码的策略，参照现有的重传机制，可以给出应用随机线性网络编码的无线传输的重传处理机制。接收端上的节点，可以根据信息接收情况，获得该节点在对序列为的信息包批次的丢包数，并将该数值记录在状态报告包中发送到发送端，发送端在延时时间后获得所有接收节点的状态报告，执行随机线性网络编码策略的源节点编码策略

57、，发送随机线性网络编码重传包。接收端在收到随机线性网络编码重传包后执行解码操作解出丢失数据，完成重传。图3-5给出了该处理机制的描述。block0block1block3发送端接收端report 0report 1report 2 图 3-5 随机线形网络编码策略的重传机制图3-5中，发送端发送信息包批次、，接收端的多个接收节点将信息包批次的状态报告、反馈给发送端，发送端根据随机线性网络编码策略的源节点编码策略，发送重传编码包完成重传。3.7 具体重传过程由3.5节、3.6节的信息包分批重传处理机制描述，全部传输的信息包的广播重传问题可以表示若干个信息包批次的广播重传问题。此时，无线广播重传策

58、略所需要解决的问题就转换成在一个固定长度的信息包批次中如何实现重传。3.7.1 重传方案描述 应用随机线性网络编码的重传策略的基本思想是源节点记录针对信息包批次中多个接收节点上丢包最多的接收节点丢包数，再按照随机线性网络编码的方法编码组合该丢包数个线性网络编码包，然后再广播发送编码组合包，实现重传。为了便于阐述，图3-5给出了一个信息包批次的随机线性网络编码的重传策略的示例。示例中有五个接收节点，一个信息包批次包含五个信息包，接收状态矩阵中行表示接收节点的接收情况，列表示信息包接收情况。0表示信息成功接收，1表示信息接受失败。1111111100000000000000001abcder1r2

59、r3r4r5源节点r1r2r3r4r5状态矩阵图3-6 信息报分批重传示例如图3-6所示，广播源节点首先逐一广播发送么信息包。发送后，接收节点，丢失信息包；接收节点丢失信息包；接收节点丢失信息包；接收节点丢失信息包；接收节点丢失信息包。需要应用重传来实现差错控制。差错控制应用普通重传策略，广播源节点需要分别逐一广播重传1、2、2、3、4、5这五个信息包，在不存在重传丢失的情况下，需要广播源节点广播重传5次。差错控制应用随机线性网络编码的重传策略，五个信息包看成是一个信息包批次，广播源节点参照全局的接收节点丢包情况进行随机线性网络编码处理。在该例中，五个接收节点中，接收节点均丢失2个信息包；接收

60、节丢失1个信息包。最大的单个接收节点丢失信息包个数为2。这样，源节点可以通过随机线性网络编码构造方法计算得到： (3-11) (3-12)将随机线性网络编码系数和附带到编码组合包中，将随机线性网络编码包广播重传。这样，接收节点，在收到编码组合包后，由于接收节点，有信息包，而且接收到的中包含有和，则通过将编码系数和的值代入式(3-11)得： (3-13) (3-14)由式(3-13)、(3-14)得： (3-15) (3-16)在式(3-13)和(3-14)中，由于网络编码系数是已知的，二个线性方程二个未知参数具有编码可解性，可以转换为式(3-15)式(3-16)的形式，代入已知值，解出丢失包。同理节点可解出丢失