第1章 绪论

网络传输和处理能力的大幅提高使基于网络的应用越来越多，特别是音频和视频技术的发展和成熟，使网络音频、视频应用成为最重要的应用之一，诸如视频点播、视频会议、远程学习、计算机协同操作等多媒体应用也随之出现。这些多媒体应用和一般的网络应用相比，有数据量大、时延要求高、持续时间长等特点。要解决这些具有传输带宽大、实时性强、有多点接收等特征的问题，需要采用不同于单播与广播机制的转发技术。多播是一种点到多点（或多点到多点）的通信方式[1]，由源点发送数据到多个宿点，且源点只需发送同一报文。多播通信方式能够有效地利用网络的带宽，提高了网络资源的利用率。作为一种新型的网络通信方式，多播通信方式具有广阔的应用前景，典型地可应用在视频点播、网络会议、远程教育、网络电话、交互游戏、分布式多媒体数据库等大量新型的多媒体通信应用领域。为实现这一新型的通信方式，需要对多播通信的理论与应用进行深入广泛的研究。自从20世纪90年代以来，基于路由技术的多播通信研究已经得到了蓬勃的发展，研究人员提出了多个多播路由算法[2,3]。21世纪初提出的网络编码技术[4~6]为网络理论与应用拓展了一个新的方向，相应地为多播通信方式提供了一个新的平台，面向多播通信的网络编码技术研究成为一个令人关注的热点，并得到了飞速地发展[7,8]。

网络编码是一种新型的数据传输技术，它与传统的路由技术相比，最大不同之处在于：在数据传输过程中，中间节点不仅能对接收到的消息直接转发，还可以把接收到的消息进行运算后再转发。

网络编码技术是通信网络中信息处理和传输理论研究上的重大突破[9]，它推广了传统的路由技术，其核心思想是既允许网络中间节点对传输的信息进行转发和复制，又可以进行信息编码，而路由本身则被认为是一种特殊的网络编码。与传统的路由技术相比，网络编码在提升网络的吞吐量、节省网络带宽的资源消耗、均衡网络负载、增加网络的顽健性和安全性等方面具有优势[9~12]。经过几年的发展，网络编码的理论研究已取得了可喜的进展，在应用基础和工程实践方面的研究已全方位地展开，网络编码已成为一项融合信息论、代数学、图论、网络流理论和优化理论等多门学科的交叉技术，且日益引起更多研究者的热切关注，为现有的网络体系结构、协议设计方法、信息交换方式和网络管理模式带来了革命性的变化[7,9]，国外多所著名大学和许多知名的IT研究机构都在积极开展网络编码的理论和应用研究[14~16]。

根据香农理论，在单源多播网络中，源点的最大传输速率是分离源点与所有宿点间的最小割值（最大流界）[17,18]。基于路由技术的多播连接是通过构造多播树实现的，传统的多播树如最小费用多播树，其构造过程一般是NP难问题[19]，并对于一般的网络拓扑难以达到其最大流界。这主要是因为人们普遍认为在传统的路由机制中，网络中传输的信息是不能叠加的，因此中间节点只需进行信息的转发或复制。2000年，Ahlswede等[4]首次提出了网络编码的思想：在网络信息传输过程中，允许中间节点转发的信息是其输入信息在有限域上的编码组合。该文并且证明：采用网络编码技术可以实现单源多播网络的“最大流界”，并举例说明了传统的路由技术在一般情况下难以达到这个极限，从而采用网络编码传输技术可以提升单源多播网络的吞吐量。2003年，李硕彦等[5]提出了线性网络编码技术，并证明了采用线性网络编码技术完全可以实现单源多播网络的最大流界，该文获得了“2005年美国电机与电子工程师学会（IEEE）信息论文学会论文奖”，该项奖是30多年来首次由亚洲研究人员所获。线性网络编码的核心思想是：网络节点输出信道传输的信息是该节点所接收信息的线性组合。因线性网络编码具有操作简单的特点，并可运用向量代数的理论来进行相应的证明[20]，从而其理论与应用得到了深入广泛地研究，如无特别说明，本书所述的网络编码均指线性网络编码。