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

，李硕彦等在证明了在足够大的有限域内，通过节点内进行线性网络编码（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]，中国科