基于网络编码的多信源组播通信系统，包括源代码，原理 等(一)

　　摘要

　　网络编码改变了传统网络节点上路由器交换和交换机对信息流“存储—转发”的模式，提出网络路由交换节点对输入的信息流编码后再发送，并在接收器上进行解码，从而还原信息。随着网络编码理论的日益发展和完善，其应用的研究也越来越受到重视。

　　本文首先介绍网络编码理论的基本概念，回顾了近年来网络编码的研究动态。接着指出研究多信源网络编码组播通信的重要性，在使用NetFPGA开发平台的基础上，提出网络编码组播通信系统及其整体设计方案。在方案中重点介绍了硬件系统中采用的编码策略—随机线性编码，解码策略、算法以及通信协议，同时介绍了系统的软硬件接口和软件作用。最后，给出了编码路由器、转发路由器以及解码路由器三个系统的详细设计方案，方案中主要包括单元模块图，每个模块的主要功能与结构，数据处理流程及算法说明，输入输出信号及说明、关键时序或状态。

　　由于本系统的主要功能是由硬件实现，所以和传统组播通信网络相比，具有时延小，没有了调度和排队时间，使得网络中链路负载更均衡，体现出了网络编码的优势。

　　1 网络编码理论及相关研究应用背景

　　1.1网络编码理论产生背景和基本概念

　　60年前C.E.Shannon发表“通信数学原理“解决了信道容量极限问题。2000年诞生的网络编码(Network Coding:NC)是继此后的一个全新突破，它解决了网络通信中单/多源对多接收点组/广播如何达到网络容量极限的问题。传统网络通信节点上的路由交换机只完成存储转发功能。NC指出如果允许路由交换机对输入信息流进行编码再发送，使得网络节点既实现路由功能又实现编码功能。在这种全新的体系结构下,网络性能可以达到最大流传输的理论极限[1][2]。

　　2000年，以香港中文大学信息工程系为主的研究人员针对通讯网络的瓶颈问题，提出了一种看似疯狂的想法，这种具有革命潜力的方法名为网络编码，以网络编码器取代路由器;原本只是单纯的传送信息的路由器，换成编码器之后，传送的却是有关信息的证据，而不是信息本身;当接收器收到证据时，即可结合各项线索，推导出原始信息。[3]

　　《科学美国人》杂志(Scientific American Magazine)2007年6月，以“Breaking Network Logjams”(打破网络僵局)为题刊登了MIT科学家详细介绍了7年前诞生于香港中文大学的网络编码理论[4]。其中指出，网络编码是继60年前C.E.Shannon发表“通信的数学原理”后，网络通信理论的一个全新突破。C.E.Shannon解决了点对点信道的容量极限问题，而NC解决了如何达到单源对多点及多源对多点的网络通信容量极限的问题[4]。传统网络通信理论把信息流当成管道中流动的水，是不可压缩的;故传统网络节点上的路由交换机只是完成存储转发功能。NC理论的划时代意义在于：提出网络路由交换节点对输入的信息流进行编码再发送，可进一步提升网络吞吐量!从而改变了比特不能再被压缩的经典结论，指出网络信息流可以被压缩。

　　网络编码最简单的概念来自‘蝴蝶网’，如图1.1-1所示：

　　图1.1-1 网络编码的基本原理

　　上图所示的网络中，源节点S1想把信息流ai传送给R1和R2。另一方面，源节点S2也希望在相同时间、以相同速度，把信息流bi传送给同样的接收节点R1和R2。假设每个路径每秒可携带一个位元，而且只能顺着箭号所指的方向前进。如果路由器只传输其所接收到的信息，那么中间链路将是个瓶颈，因为每秒总共接收到二位元的资料，但其容量只有一位元，路由器每秒只能传送一位元资料给中间链路，这种瓶颈会造成可怕的塞车。相反，如果把一般的路由器换成编码器，它可以把两个信息通过异或或者线性组合运算成单一位元输送给中间链路，并且发送ai+bi (或者ai和bi的任意线性组合)，这样就轻而易举地解决了塞车问题[3][5]。

　　网络编码另一个与路由系统不同之处在于，充分利用网络资源。图1中，S1透过路径S1R1把ai传给R1，S2透过路径S2R2把bi传给R2，这在路由系统中是不会使用到的。节点R1接收到ai，并且根据每次编码器运算结果，输入到与编码器使用的相同函数(异或或者线性组合)内，推导出bi。节点R2解出ai也是同样的道理。重复对每个位元字串进行相同的流程，最后就能得出两个原始信息。

　　可见，有了网络编码，网络的运作可望变得更有效率(不需要增加硬件设备或频宽，就可以提高网络吞吐量)，可以改善网络的负载均衡，节省网络带宽消耗，节省无线网络的能量消耗，提高了网络的鲁棒性，同时对于具有链路时延的网络，相对于路由方式，通过网络编码进行多播传输时可以获得较小的传播时延[6][7]。

　　随后，李硕彦等在证明了在足够大的有限域内，通过节点内进行线性网络编码(Linear Network Coding： LNC)就可以达到网络组播，广播等的理论上限[8]。在线性范围内解决达到理论上界的问题为NC进入实际应用奠定了坚实的基础。随后，Yueng，李硕彦[9]等出版了国际上第一本网络编码理论专著“Network Coding Theory”。

　　Koetter等[10]于2003年提出将NC问题与多项式方程建立数学联系，使得讨论NC问题又多了一种有力的数学工具代数理论;LNC针对于已经了解整个网络拓扑状况的情况下，经过网络路由设定，通过确定的矩阵计算公式对报文进行编解码，实现简单，但适应性和容错性较差。论文[11]中提出随机网络编码概念(Random Network Coding：RNC)，与线性编码结合在一起，使得分布式的、简单实用的网络编码体系形成。随机线性网络编码是一种分布式算法，编码在有限域上进行，系数随机选取，其灵活性远大于LNC。

　　下面给出一个不仅NC提高多播网络吞吐量，而且显著改善网络负载均衡的例子。图1.1-2(a)显示了网络的容量，所有的边的容量都是2。在这个例子中，最大流是4。图2(b), (c)和(d)分别显示了单会话IP组播，多会话IP组播和基于网络编码的组播的分配树。在图2(b)中，发送端通过一个组播分配树同时向接收端R1, R2和R3发送了两个比特a，b。在图2(c)中，组播会话1，2和3分别向接收者发送了比特a，b和c。需要指出的是多会话IP组播所有的会话不是拥有同一个分配树。在图2(d)中，发送端同时向接收端R1, R2和R3发送了四个比特a，b，c和d[12]。

　　所有的组播技术中网络编码可以达到最高的吞吐量，因为它可以最大流发送信息。我们看到在图2(b), (c)和(d)中在单位时间内接收端分别接收到2，3和4比特。因此在这个例子中，基于网络编码的组播的吞吐量是单会话IP组播的2倍，多会话IP组播的1.3倍。

　　通过比较基于网络编码的组播和现在的组播来研究负载均衡的影响。假定基于网络编码的组播使用图2(d)例子中的容量的一半。在这种情况下，单会话IP组播和网络编码都在单位时间内向所有的接收端发送了2比特。在图2(b)中，通过了网络中9条链路(总共发送10比特)中的5条来传输2比特，另外4条没有使用。另一方面，当网络编码使用时，2( d) 通过了9条链路(总共发送9比特)来传输2比特。于是通过应用网络编码，流量负载可以分散在整个网络上。

　　(a)链接容量 (b)单会话的IP组播

　　(c)多会话的IP组播 (d)网络编码组播

　　图1.1-2 网络编码提高网络容量，同时均衡了网络流量

　　1.2国内外研究动态与现状

　　网络编码自诞生以来，普及性的急速增长就连其奠基者也始料未及。从2005年开始每年一次的NetCod workshop 得到了Microsoft, Qualcomm等机构的资助。短短几年，发表了几百篇学术论文。这个崭新的领域对许多相关学科产生了深远的影响，NC的理论研究范围包括信息论及通信的几乎每个领域，如线性编码，非线性编码，随机编码，静态码，卷积码，群码，Alphabet码，码构建，算法协议，有环网络，无向网络，链路失效及其网络管理，分离理论，错误检测和纠错码，密码学，多信源编码，多-单播编码, Cost Criteria, 非均匀需求,关联信源编码，最大流/刮集界，叠加编码，网络互连，路由寻找，无线及卫星网络，Ad hoc网络，传感网络，数据存储及分布，矩阵理论，复杂性理论，图论，随机图论，树装箱(Tree Packing)，多种物流(Multicommodity flow)，游戏理论，矩阵胚理论(Matriod theory)，信息论不等式，排队论分析，率失真(rate-distortion)可逆网络，多用户信道，联合网络信道编码，P2P网络等[13]。

　　国外多所著名大学如普林斯顿大学、麻省理工、瑞士EPFL 学院等和多家IT 公司的研究中心,包括微软研究院、贝尔实验室、AT &T 的香农信息实验室等都在积极开展对网络编码理论和应用的研究。与此同时，网络编码的实际应用问题被提到技术研究的前线。从2005年第一届Net Cod国际会议上就明确将NC在现实通信中的应用作为研究的重点。微软公司是最早开展网络编码应用研究的公司[14]，Microsoft公司已经采用网络编码作为其下一代网络内容发布平台Avalanche的核心技术。

不仅国外，近两年来国内学者也开始研究网络编码。清华大学[15]，西安电子科大、及电子科技大学[16]，北京邮电大学[17]均投

入了NC与无线网络方面的研究。NC在P2P网络传输，流媒体广播及内容分发方面的应用方面，上海大学[18]、湖南大学[19]和并行与分布处理国家重点实验室[20]，中国科学技术大学[21]等都进行了研究。最近几年中，网络编码在组播通信方面的应用成为了研究的热点，复旦大学研究了单信源组播并提出了一项关于在目前internet路由器上实现网络编码的专利[23]，西安电子科技大学提出了一种基于网络编码的组播路由算法，能够大大降低网络资源消耗，同时能改善负载均衡[24]。

　　以上网络编码在通信中的应用研究基本上都是处于理论和计算机软件仿真阶段，在用硬件平台搭建实际的组播网络，并在真实的网络环境中应用网络编码，进行其实现的复杂度和网络性能的评估等方面的研究尚处于起步阶段。