科技文献综述竞赛网络编码研究综述姓名：贾骐玮张丽韩改霞专业：交通信息工程及控制学号：130112038213011203801301120372指导教师：张向东2014年4月7日网络编码研究综述贾骐玮，张丽，韩改霞（西安电子科技大学交通信息工程及控制专业，西安710071）摘要：网络编码是指网络中的节点参与编译码，它的提出对于网络信息论具有划时代的意义。

网络编码具有提高网络吞吐量、均衡网络负载、节省网络带宽、降低节点能耗等显著优点。

本文介绍了网络编码的起源与发展，基本原理以及其在无线网络、P2P系统、分布式文件存储、网络安全等领域的最新应用。

文章最后对网络编码的研究趋势和热点进行分析，并对其提出展望。

关键词：网络编码网络信息论P2P系统分布式文件存储网络安全Research on Wireless Network Coding:A SurveyJia Qiwei,Zhang Li,Han Gaixia(XiDian University,Traffic Information Engineering&Control,Xi’an710071,China)Abstract:Network coding refers to the nodes within the network involved to encoding and decoding,it has a great significance for network information work coding can larger throughput of the network,enhance network load balance,save network bandwidth and reduce the energy consumption of nodes.This article describes network coding origin and development,as well as its basic principles and its latest applications in the areas of wireless network,P2P systems,distributed file storage,and network security and so on.Finally,we analysis the trends and hot spots for the research of network coding,and then raise its outlook.Keywords:Network Coding;Network Information Theory;P2P System;Distributed File Storage;Network Security经典的信息理论指出，不论是互联网中的数据包还是移动网络中的信号，信息的传输都只是单纯的共享网络和链路资源，彼此互不相干、相互独立。

数据的路由、存储、差错控制等等研究都是基于上述假设。

直到网络编码的提出，完全打破了这一假设，开创了一个全新的领域。

网络编码(network coding)是一种融合了编码和路由转发的信息交换技术，在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码(如模二加、有限域上的运算等)信息融合，增加单次传输的信息量，以提高网络信息传输效率和整体性能。

网络编码打破了经典信息论中商品流(Commodity Flow)[2]不能被压缩的结论，指出网络信息流(Network Information Flow)可以被处理或压缩，从而可以进一步提升网络吞吐量。

1网络编码的起源和发展网络编码概念的诞生可以追溯到1998年论文“Network Information Flow Theory”[3](引自文献[4])和1999年Yeung和Zhang发表的关于卫星通信的论文[5](引自文献[6])。

网络编码原理论文正式发表于2000年的先锋论文“Network Information Flow”[1]，这是网络编码理论的奠基之作。

在2003年，网络编码领域发表了许多重要研究成果，具有里程碑意义。

2003年，香港中文大学讯息工程系的李硕彦教授、杨伟豪教授、蔡宁教授发表了论文“Linear Network Coding”[2]指出线性网络编码可以达到多播方式下的网络容量。

该文于2005年获得IEEE信息理论学会年度最佳论文奖。

该奖项首次颁发给亚洲学者，以表彰他们在信息理论领域的重要贡献，这也彰显出网络编码理论所具有的重大价值。

2003年，Koetter和Medard[7]提出网络编码的代数学(Algebra)框架，即用抽象代数来解决线性网络编码的问题，为研究网络编码提供了一个用力的数学工具。

2003年，Sanders等[8]提出具有多项式复杂度的线性信息流算法，该算法属于集中式的码构造算法。

2005年，Jaggi等[9]将之正式发表于IEEE信息论会刊，文献[6]中称LIF 算法为Jaggi-Sanders算法。

2003年，Ho等[10]提出随机网络编码(Random Network Coding,RNC)，属于分布式的码构造方法。

随机网络编码的基本思想并不复杂，每个节点均随机选取系数进行编码，将得到的线性组合向下游节点发送。

当信宿节点收到足够多线性无关的组合后，通过联立求解线性方程组，即可译码出信源节点发出的所有信息。

由于每个节点均随机的选择系数，节点不必获得全局信息，因此是分布式算法。

随机网络编码的提出证明了网络编码的可行性。

2003年，Chou等[11]提出诗句的网络编码及其相应的设计原则。

主要包括：①同步机制：采用网络编码，一般需要等到所有数据到达之后才进行，因此需要添加缓存。

②缓存刷新机制：由于缓存的大小总是有限的，所以需要设计缓存中内容的更新机制。

当然，缓存大小的最优设置也需要考虑。

③渐进译码机制：通过一边下载一边译码，来节省译码时间。

④译码成功率：译码成功概率与有限区域大小有一定关系。

Jaggi等[9]指出，当有限域大小为16|F时，译码成功率可达99.6%；Chou|=|=2|F且网络中的链路数为82等[11]指出有限域大小为28即可满足实际应用的需求。

2003年以后，网络编码的发展可以用如火如荼来形容，众多的研究成果也是层出不穷。

网络编码彻底改变了通信网络中信息处理和传输的方式，是信息理论研究领域的重大突破，已经引起学术界广泛关注和高度重视。

国际许多著名大学和研究机构，国外许多著名大学，如普林斯顿大学[12]、麻省理工大学[13]、瑞士EPFL学院[14]等以及多家IT公司的研究中心，包括微软研究院[15]、贝尔实验室[16]、AT&T的香农信息实验室[17]等都在积极开展对网络编码理论和应用的研究；网络编码也逐渐引起了国内学术界的关注和重视，我国的清华大学[18]、南京大学[19]、西安电子科技大学[20]等都对网络编码进行了探索。

2网络编码基本原理2.1基本原理网络编码的本质是利用节点的计算能力提高链路带宽的利用率。

图1以典型的蝶形网络为例对比了网络编码与传统路由传输的区别、特点以及网络编码的基本原理。

图中s是信源,x，y是信宿,各链路的带宽均为1bit/单位时间，现要将2bit数据a，b同时从s传到x，y。

易知s与x，y之间均分别存在两条独立路径,若采用传统路由方法,如图1(a)所示,由于两组路径间存在共有链路w-z，a、b不能同时在w-z上传输（要么传消息a，要么传消息b，即1bit信息）,则s到x，y的最大信息流速率为1.5bit/单位时间，即每个信宿节点的平均吞吐量为1.5b/节点；若采用网络编码方法,在节点w上对a)(计算译码出b,同理y也可以译ba，b执行异或操作并转发，则节点x可以通过a码出a，从而使s到x，y的信息流速率达到2bit/单位时间，平均每个信宿节点的吞吐量为2b/节点，带宽利用率提高33%。

图1路由方法和网络编码比较(a)路由方法；(b)网络编码2.2主要优点由图1可以看出网络编码可以显著提高网络吞吐量，此外，理论研究表明，网络编码在改善负载均衡、节省带宽资源、减少节点能量损耗、增强网络鲁棒性等方面均显示出其相对于传统网络传输的优越性[21]。

(1)提升网络吞吐量：这是网络编码的最主要的优点，无论是否是均匀链路，网络编码都能获得更高的多播容量，且节点平均度数越大，网络编码的优势越明显[22]。

(2)均衡网络负载：网络编码可以有效利用除了多播树路径外的其他网络链路，将网络流量分布于更广泛的网络上，从而均衡网络负载，进而延长网络工作时间。

(3)节省网络带宽资源消耗，提高带宽利用率：信道的带宽一般是有限的，而且信道具有波动性，节点数目众多将会导致带宽资源紧张。

网络编码则可以有效提高带宽利用率，通过有效的节点网络编码，可以融合不同输入链路的信息，从而使网络链路上的有效信息量增加，进而可以使用较少的通信链路实现多播[23]。

(4)减少数据包传输次数，降低无线发射能量：无线信道中的数据传输往往存在丢包问题，而广播和多播等接收节点数目较多，信息包损耗分散，重传信息包可能再次丢失，从而造成很大的重传量，不仅消耗带宽，也会消耗节点能量。

通过网络编码将不同节点损耗的信息包进行组合编码传输，可以有效降低重传次数，并可以在信息包再次丢失的情况下动态调整组合数据包，极大地降低信息包重传次数，从而节约各个节点的无线发射能量[23,25]。

(5)有效应对节点动态加入、离开、链路失效问题，增强网络容错性和鲁棒性：通过网络编码可以抵抗网络链路和节点的非各态历经失败对网络链接的影响，恢复链路失效[24]。

网络编码的这一优点使其非常适合无线视频传感器网络。

无线视频传感器网络的动态性很强，较难形成稳定的通信拓扑，当节点能量耗尽或遭到破坏时就无法继续工作，原路由路径被迫断开，必须重新选择新的转发节点，造成资源的浪费和信息的不稳定。

通过网络编码可应对节点的动态加入和离开，提高网络链接的鲁棒性[25]。

(6)网络编码无需复杂的加密算法就可以提高网络安全性：网络编码在编码过程中能够融合来自不同源、不同类别的信息，这一点是传统编码无法做到的，这也使得网络编码比传统编码复杂，间接提高了接收端译码的难度。

同时，也可以将网络密钥加入到网络编码的信息中，没有网络密钥的接收节点就无法正确地接受和译码，因此网络编码也能达到提高网络安全性的目的。

3网络编码的最新应用发展状况网络编码的诸多优势决定了其巨大的应用潜力，应用领域涉及无线网络、P2P系统、分布式文件存储和网络安全等网络的多个层面，文献[26]对网络编码的应用进行了详细总结，本文在其基础上对最新的应用发展状况进行归纳分析。