作者：蒲保兴,秦波莲
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
网络编码研究基础试读：
前言
网络编码是一种新型的数据传输技术，与传统的路由传输技术相比，中间节点不仅具有存储和转发数据的功能，还可以对接收到的信息进行编码后再进行传输。网络编码能提高网络的传输性能，在提升网络的吞吐率、实现网络的负载均衡、增加网络的顽健性与安全性等方面具有优势，但因节点需要编码或解码，数据传输过程中也增加了编码运算代价。
采用网络编码技术实现数据传输的关键是构造网络编码方案，编码方案不仅决定了宿点能否解码，还决定了网络的吞吐率和编码运算代价。显然，提高网络的吞吐率、降低编码运算代价对网络编码的实际应用具有重要的意义，是网络编码方案优化构造的两个重要目标。
笔者围绕这两个目标，对网络编码进行了潜心的研究，在多年研究的基础上撰写了本书。本书主要包括了以下几个方面的内容：（1）网络编码的基本原理；（2）在介绍了有限域算术运算方法的基础上，阐述了确定性网络编码和随机网络编码构造方法，并给出了仿真实验平台；（3）提出了网络编码导出与扩展技术；（4）讨论了未知网络拓扑环境下网络编码优化构造方法；（5）讨论了网络编码运算代价与环境参数（伽罗华域、多播率和数据块长）之间的关系；（6）对多源网络编码的优化构造进行了研究。
本书共分为10章，第1章为绪论，介绍了网络编码的基本概念、起源和发展；第2章阐述了阅读本书所需要的相关理论和技术，主要包括网络最大流的概念和算法、有限域的算术运算方法等；第3章阐述了线性网络编码的基本原理和技术，重点介绍了确定性网络编码和随机网络编码构造方法，并给出仿真实验平台；第4章运用了代数知识提出了线性网络编码的导出与扩展技术，它是第5章和第6章的基础；第5章给出了未知网络拓扑环境下确定性网络编码构造算法；第6章给出了网络编码优化构造方法，并给出了网络拓扑动态变化环境下的编码策略；第7章对网络编码的运算代价进行了估算与分析；第8章给出了一种分级网络编码构造方法；第9章给出基于随机网络编码的差错控制方法；第10章对多源网络编码进行了研究。附录给出了网络编码仿真实验平台的程序和使用说明。
本书得到了湖南省教育厅重点科研项目（11A111，12A068）的资助。由于水平有限，书中难免存在缺点和疏漏之处，敬请广大读者批评指正。蒲保兴2016年4月第1章绪论
网络传输和处理能力的大幅提高使基于网络的应用越来越多，特别是音频和视频技术的发展和成熟，使网络音频、视频应用成为最重要的应用之一，诸如视频点播、视频会议、远程学习、计算机协同操作等多媒体应用也随之出现。这些多媒体应用和一般的网络应用相比，有数据量大、时延要求高、持续时间长等特点。要解决这些具有传输带宽大、实时性强、有多点接收等特征的问题，需要采用不同于单播与广播机制的转发技术。多播是一种点到多点（或多点到多点）的通[1]信方式，由源点发送数据到多个宿点，且源点只需发送同一报文。多播通信方式能够有效地利用网络的带宽，提高了网络资源的利用率。作为一种新型的网络通信方式，多播通信方式具有广阔的应用前景，典型地可应用在视频点播、网络会议、远程教育、网络电话、交互游戏、分布式多媒体数据库等大量新型的多媒体通信应用领域。为实现这一新型的通信方式，需要对多播通信的理论与应用进行深入广泛的研究。自从20世纪90年代以来，基于路由技术的多播通信研究[2,3]已经得到了蓬勃的发展，研究人员提出了多个多播路由算法。21[4～6]世纪初提出的网络编码技术为网络理论与应用拓展了一个新的方向，相应地为多播通信方式提供了一个新的平台，面向多播通信的网络编码技术研究成为一个令人关注的热点，并得到了飞速地发展[7,8]。
网络编码是一种新型的数据传输技术，它与传统的路由技术相比，最大不同之处在于：在数据传输过程中，中间节点不仅能对接收到的消息直接转发，还可以把接收到的消息进行运算后再转发。
网络编码技术是通信网络中信息处理和传输理论研究上的重大突[9]破，它推广了传统的路由技术，其核心思想是既允许网络中间节点对传输的信息进行转发和复制，又可以进行信息编码，而路由本身则被认为是一种特殊的网络编码。与传统的路由技术相比，网络编码在提升网络的吞吐量、节省网络带宽的资源消耗、均衡网络负载、增加[9～12]网络的顽健性和安全性等方面具有优势。经过几年的发展，网络编码的理论研究已取得了可喜的进展，在应用基础和工程实践方面的研究已全方位地展开，网络编码已成为一项融合信息论、代数学、图论、网络流理论和优化理论等多门学科的交叉技术，且日益引起更多研究者的热切关注，为现有的网络体系结构、协议设计方法、信息[7,9]交换方式和网络管理模式带来了革命性的变化，国外多所著名大学和许多知名的IT 研究机构都在积极开展网络编码的理论和应用研[14～16]究。
根据香农理论，在单源多播网络中，源点的最大传输速率是分离[17,18]源点与所有宿点间的最小割值（最大流界）。基于路由技术的多播连接是通过构造多播树实现的，传统的多播树如最小费用多播树，[19]其构造过程一般是NP难问题，并对于一般的网络拓扑难以达到其最大流界。这主要是因为人们普遍认为在传统的路由机制中，网络中传输的信息是不能叠加的，因此中间节点只需进行信息的转发或复[4]制。2000年，Ahlswede等首次提出了网络编码的思想：在网络信息传输过程中，允许中间节点转发的信息是其输入信息在有限域上的编码组合。该文并且证明：采用网络编码技术可以实现单源多播网络的“最大流界”，并举例说明了传统的路由技术在一般情况下难以达到这个极限，从而采用网络编码传输技术可以提升单源多播网络的吞吐量。2003 年，李硕彦等[5]提出了线性网络编码技术，并证明了采用线性网络编码技术完全可以实现单源多播网络的最大流界，该文获得了“2005年美国电机与电子工程师学会（IEEE）信息论文学会论文奖”，该项奖是 30 多年来首次由亚洲研究人员所获。线性网络编码的核心思想是：网络节点输出信道传输的信息是该节点所接收信息的线性组合。因线性网络编码具有操作简单的特点，并可运用向量代数[20]的理论来进行相应的证明，从而其理论与应用得到了深入广泛地研究，如无特别说明，本书所述的网络编码均指线性网络编码。1.1 蝴蝶网络
图1-1（a）是典型的蝴蝶网络，在不少文献中用于描述网络编码的原理，它是一个有向无环单源多播网络，其中节点S是源点，T和1T是宿点，节点2、3、4、5为中间节点。设每条链路的信道容量均2为1，即每条链路在单位时间内最多只能传输一个字符，而源点S欲通过网络多播信息至两个宿点T、T。若采用路由传输技术，因为节12点4至节点5的信道是数据传输的瓶颈，在一个时间单元内，源点最多只能多播一个 1.5 个字符至两个宿点，若采用网络编码技术，则可以多播2个字符。图1-1 蝴蝶网络及路由传输方式
采用路由传输方式，则数据传输方式如图1-1（b）和图1-1（c）所示。在第1个时间单元内，数据传输方式如下。（1）S把字符a传输至输出信道
若以两个时间单元为一个传输周期，第1个时间单元的传输情况如图1-1（b）所示，而第2个时间单位的传输情况如图1-1（c）所示，从而在2个时间单元内，源点成功地多播了3个字符（a,b,c）至每一个宿点，则平均每个时间单元实现了多播1.5个字符。
若采用网络编码，即中间节点允许把接收到的信息进行编码后再转发，则能在每个时间单元内实现多播2个字符。在一个时间单元内各信道的传输情况如图1-2所示，传输方式如下。（1）S把字符a传输至输出信道
作为一种新型的数据传输技术，与传统的路由传输技术相比，网络编码具有下述优点：提升了网络的吞吐率；均衡了网络的流量负载；增加了网络的顽健性。（1）提升网络的吞吐率
图1-1和图1-2的例子能够说明：在多播方式下，蝴蝶网络在路由传输方式下平均每个时间单元最多只能实现多播1.5个字符，而采用网络编码方式可达到2个字符。（2）均衡网络的流量负载
图1-3描述了这一情形。图1-3（a）表示网络拓扑，其中每条边的链路容量均为1。如采用路由传输方式，如图1-3（b）所示，单位时间内源点S只能多播一个字符至宿点T和T，且网络的负载极不均12匀，只有
如图1-4所示，图1-4（a）给出了网络拓扑，图1-4（b）和图1-4（c）分别给出了路由传输方式，两者均利用于冗余信道。使用冗余信道的目的是当某些信道出现故障时宿点仍能正确地接收源点传送的信息。图1-4（b）对字符a传输2次，而图1-4（c）对字符b传输2次。图1-4（d）采用网络编码传输方式，注意到在网络编码传输方式中，宿点T可以任意选取两条输入链路的消息（有可能需要解码）获得源点播出的消息a和b，因此网络中任意一条链路出现故障，宿点仍然能够正确接收源点播出的消息。而对于路由传输方式，则不能满足这个条件，例如，在图 1-4（b）的传输方式中，若链路
与路由技术相比，网络编码存在如下不足之处：中间节点必须具有编码功能，宿点必须具有解码功能；中间节点增加了编码的运算代价，宿点增加了解码的运算代价；中间节点需获知编码的策略，宿点需获知解码的策略。（1）中间节点必须具有编码功能，宿点必须具有解码的功能
网络编码的实质是中间节点接收到信息后可以对其进行运算（编码），因此，中间节点必须具有能对接收的信息进行编码运算的功能，在传统的路由技术中，路由器等中间节点是不需要具备这些功能的。因此，如要采用网络编码技术，现有的网络体系结构无论从硬件还是软件上均要进行改进。（2）由于中间节点需要编码、宿点需要解码，导致了中间节点和宿点都增加了运算代价。（3）中间节点需获知编码策略，宿点需获知解码策略。
中间节点如何进行编码，宿点如何通过接收到的信息进行解码，这就是编码策略和解码策略，这一点非常重要，它有一套具体的规则，只有符合这套规则，才能保证宿点正确地解码恢复出源点的消息，下面章节将讨论这个问题，称之为网络编码的构造方法，就线性网络编码而言，有确定性网络编码构造方法和随机网络编码构造方法。1.4 网络编码的实质
网络编码的实质是允许中间节点通过对接收到的信息进行运算后再进行转发，从而提高了网络吞吐率，在整体上提高了网络的传输速度，但节点增加了运算开销，从而是通过节点的运算代价来换取网络的吞吐量。
网络编码不同于信源编码，也不同于信道编码，更不同于加密与解密运算。信源编码是为了实现信息的压缩，而信道编码是为了在不可靠信道上实现数据传输，加密与解密是为了在信息的传输过程中把明文转换成密文，从而隐藏信息，防止被人窃听。从参与网络通信的节点类型来看，无论是信源编码、信道编码还是加密与解密运算均只需考虑信源节点和信宿节点，而网络编码涉及网络的中间节点。1.5 线性网络编码与非线性网络编码
网络编码的实质是中间节点可以把接收到的信息进行运算再进行转发。如果把运算当成一个函数，则中间节点接收到的信息为自变量，运算后的结果为函数值，编码规则为函数运算。在宿点处，再把接收到的信息进行解码后再恢复出源点产生的信息，因此必须保证运算的封闭性，即选定一个集合，对集合中的元素进行运算，其运算的结果仍然是该集合的元素。
代数中的数域具有运算的封闭性。在线性网络编码中，一般选定一个有限域（即伽罗华域），编码与解码均是对有限域的元素进行操作。无论是源点产生的信息，还是中间节点接收到的信息均看成是有限域中的一个元素。当中间节点对接收到的信息进行运算后，其结果也为该有限域的元素。宿点接收到的信息也是该有限域上的元素，通过解码运算后，得到的结果仍为有限域中的元素。
目前研究的最多的是线性网络编码，线性网络编码具有运算简单、操作方便的特点，但也存在非线性网络编码。
线性网络编码的特点是编码与解码运算均是线性的，中间节点的编码运算结果是该节点接收到的信息的线性组合。
如图1-5所示，对于编码节点，它从3条输入链路上收到了3个消息y、y、y，这3个消息看成同一集合上的3个元素，对这3个元素123进行运算，把运算结果发送至输出链路上。图1-5 编码节点
式（1-1）描述了中间节点的网络编码，节点输出信道上传输的信息是由该节点从输入信道接收到的信息通过运算所得的结果。
若f和f均为y、y、y的线性组合，则称为线性网络编码，否则12123称之为非线性网络编码。在式（1-2）中，系数ξ（i=1,2，j=1,2,3）为ij与信息字符y、y、y同属一个集合，属线性网络编码。123
若编码如式（1-3）所示，则称为非线性网络编码。
关于非线性网络编码，作者认为可把分组加密算法的Feistel结构看成是由非线网络编码形成的。
文献[21]给出的Feistel结构如图1-6所示。Feistel结构采用乘积密码结构，首先把明文（假设为2n位二进制数）等分成两部分，左边部分的n位记为L，右边n位记为R，然后进行r轮加密变换，对于第i00轮加密变换，其变换公式如式（1-4）所示。经过r轮变换后，得到Lr和R为密文。r
以上操作可以看成是操作在一个有向无环网络上的从源点到宿点的网络编码运算，假设源点产生2n位的信息，把信息划分成两部分，左n位和右n位，分别传输至后继节点，中间节点接收到信息后，进行编码运算再传输到下一节点，最后宿点接收到的信息就是密文。当r=4时，其网络编码的模型如图1-7所示。图1-6 Feistel结构
图1-7中有10个节点，其中源点S产生明文，宿点T得到密文。源点S分别通过其输出信道把L传输至节点2，把R传输至节点1，节点001接收到R后，一方面把R通过输出信道直接传输至节点4，另一方00面，节点1把R与节点本身产生的子密钥K进行运算，得到F（R,K）0101并传输至节点2；节点2从两条输入信道分别接收到信息是L0与F（R,K），把两者进行异或运算后，把所得结果传输至节点3，这01样相当于进行了Feistel的第一轮加密运算；同理节点3和节点4把接收到的信息进行编码后再传输，相当于进行了Feistel的第二轮加密运算，以此类推，直至宿点T收到了L和R便形成了密文。假设T为宿44点，宿点可以通过解码运算恢复出明文，相当于解码得到源点传输的消息。
从以上可以看出，非线性网络编码比线性网络编码更为复杂，其操作也没有什么规律。编码操作可以是在有限域上的操作，也可以不是在有限域上的操作。正因为如此，人们更青睐了线性网络编码，对线性网络编码进行了深入广泛的研究，得出了较为完善的理论和技术，而非线性网络编码的研究仍涉及得较少。目前关于非线性网络编码的文献较少，文献[22]介绍了一个非线性网络编码的实例，提出了非线性网络编码的多项式描述方式，并与线性网络编码进行了比较，给出了从线性网络编码构造一种非线性网络编码的方法；利用编码函数与拉丁矩阵之间的有趣联系，证明了另一类非线性网络编码的存在性。图1-7 r=4时Feistel结构对应的非线性网络编码模型1.6 代内网络编码与代间网络编码
源点播出信息，中间节点进行编码和转发，宿点对接收到的消息进行解码，恢复出源点播出的消息，这一过程称之为一代[15]（Generation）。文献[9]指出分代具有3个目的。其一，减少编码与译码的复杂度；其二，减少编码与解码对内存的需求量；还有一个目的是能适应实时应用的需求。
分代网络编码又可分为代内（Intra-Generation）网络编码和代间（Inter-Generation）网络编码。代内网络编码把需要传输的数据分为多个代，每代从源点传输确定量的数据，中间节点的编码只针对本代的数据，与先前代的数据无关，宿点在进行解码后也只能恢复出本代的数据。而代间网络编码同样把源点要传输的数据分成多个代，但每代的传输过程中，中间节点的编码不仅让本代的数据参与编码，还可能涉及前几代的数据，宿点的解码后，不仅会得到本代的数据，还能得到前几代的数据。
代内网络编码的特点是各代的编码与解码不存在关联，而代间网络编码让若干代的数据一起参与编码与解码，显然代内网络编码需要较少的内存容量，编码与解码的计算量也较小，而代间网络编码则要求各节点有较大的内存，且编码与编码的计算量较大。但代间网络编码的优势是：可能解决“断代“的问题，当某代的数据传输过程中，宿点解码不成功时，采用代内网络编码的数据传输则需要重传该代的所有信息，使宿点通过重传的信息重新解码恢复出源点的信息，而代间网络编码则可能只需要重传该代的部分信息，而中间节点可以把重传的信息与之前传输的信息相结合进行编码，宿点也会解码译出信息，采用这种方式减少了数据的传输量，节省了网络的带宽。参考文献
[1]刘莹,徐格.Internet多播体系结构[M].北京:科学出版社,2008:1-17.
[2]SAHASRABUDDHE L H,MUKHERJEE B.Multicast routing algorithms and protocols:a tutorial[J].IEEE Network,2000,14(1):90-102.
[3]SALAMA H F.Evalution of multicast routing algorithm for real-time communication on high-speed networks[J].IEEE Journal on Selected Areas in Communication,1997,5(3):32-345.
[4]AHLSWEDE R,CAI N,LI S R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000,46(4):1204-1216.
[5]LI S Y R,YEUNG R W,CAI N.Linear network coding[J].IEEE Transactions on Information Theory,2003,49(2):371-381.
[6]FRAGOULI C,BOUDEC J Y L,WIDMER J.Network coding:an instant primer[J].ACM SIGCOMM Computer Communication Review,2006,36(1):63-68.
[7]杨林，郑刚,胡晓惠.网络编码研究进展[J].计算机研究与发展,2008,45(3):400-407.
[8]陶少国,黄佳庆,杨宗凯,等.网络编码研究综述[J].小型微型计算机系统,2008,29(4):583-592.
[9]黄佳庆,李宗鹏.网络编码原理[M].北京:国防工业出版社,2012:1-13.
[10]AGARWAL A,CHARIKAR M.On the advantage of network coding for improving network throughput[C]// IEEE Information Theory Workshop,2004:247-249.
[11]WU Y,CHOU P A,JAIN K.A comparison of network coding and tree packing[C]//Information Theory,International Symposium.2004.
[12]BAHRAMGIRI H，LAHOUTI F.Robust network coding using diversity through backup flows[C].Network Coding,Theory and Applications.2008:1-6.
[13]BHATTAD K,NAYAYANAN K R.Weakly secure network coding[C]//Proc First Workshop on Network Coding,Theory,and Applications(NetCod).2005:281-285.
[14]HO T,LEONG B,KOTTER R,et al.Byzantine modification detection in multicast networks using randomized network coding[J].Information Theory,Isit,Proceedings,International Symposinmon,2004,54(6):143.
[15]CHOU P A,WU Y N,JAIN K.Practical network coding[C]//The 41st Annual Allerton Conf on Communication,Control,and Computing.Monticello,IL,2003.
[16]FRAGOULI C,SOLJIANIN E.Decentralized network coding[C]//IEEE Information Theory Workshop.San Antonio,Texas,2004:310-314.
[17]ELIAS P,FEINSTEIN A,SHANNON C.A note on the maximum flow through a network[J].IEEE Transactions on Information Theory,1956,2(4):117-119.
[18]谢金星,邢文训,王振波.网络优化[M].北京:清华大学出版社,2007:125-136.
[19]LEONID Z,SAMIR K.On directed steiner trees[C]//13th Annual ACM-SIAM Symposium on Discrete Algorithms.2002:59-63.
[20]JAGGI S.Design and analysis of network codes[D].California Institute of Technology Pasadena,California,2005.
[21]宋震.密码学[M].北京:中国水利水电出版社,2002:55-57.
[22]李令雄,龙冬阳.非线性网络编码实例研究[J].计算机科学,2009,35(7):67-69.第2章相关理论与技术
网络编码是一项融合信息论、代数学、图论、网络流理论及优化[1]理论和技术等学科的交叉技术，在网络编码的研究过程中必定要用到这些学科的相关知识和技术。为使本书的编写具有逻辑性，并方便后续各章节的编写，把后续各章中要用到的相关理论和技术提炼成一章，作为后续各章的基础。在后续各章的叙述过程中凡要用到本章所述的一些理论和技术时，则可以直接引用，不再详叙。本章主要介绍了多播通信方式、图和网络的基本概念、网络最大流概念及计算方法、优化理论和技术、有限域（伽罗华域）的基本概念、有限域的算术运算方法等内容，最后介绍了本书所采用的仿真测试模型。部分算法的实现由附录给出，为了照顾不同群体的读者，算法的实现由两种语言给出，C++语言和Java语言，读者需要时可参考附录。2.1 多播通信、网络的最大流[2]
计算机通信通常具有3种方式：单播（Unicast）、广播（Broadcast）和多播（Multicast）。单播是指从信源到信宿沿一条路径转发信息的通信方式；广播是指在整个网络（或子网）内转发数据分组，子网内部的所有节点都能收到这些数据分组；多播介于单播和广播之间，通常指信源向一组宿点同时发送信息的通信方式。相对单播和广播而言，多播具有其独特性：适合于一对多或者多对多的通信业务，如视频点播、分布式控制；多播通信方式有利于网络资源的管理，能大大节省网络带宽。把源点同时传输数据至所有宿点称为一次多播联接（Multicast Connection）。基于路由方式的多播连接是通过建立一棵多播树来实现，而基于网络编码的多播连接要保证存在一个有向图（或有向子图），使在该有向图（或有向子图）中源点至任一[3～5]宿点的最小割值不能低于多播率。正如采用路由传输技术实现多播连接称之为路由多播一样，采用线性网络编码技术实现多播连接称为线性网络编码多播，简称网络编码多播。
研究网络编码多播需要运用图论与网络流的知识。图论是一门古老的数学分支，起源于著名的柯尼斯堡七桥问题。随着计算机技术和网络技术的发展，大大促进了图论理论研究内容的扩展。图论的内容主要包括图与网络的基本概念、图的存储结构、图的遍历算法、最短路径、最小生成树和拓扑排序等内容。网络是图的扩展，在网络中，从源点到宿点存在最大流，最大流是分离源点与宿点的最小割值，而[6,7]寻求最大流算法是一个多项式时间算法。[6～8]
图是一种多对多的数据结构，其定义如下。
定义2.1 图。一个图用二元组G=(V,E)表示，其中，V={v,v,…,v}12n称为图的节点集，两个节点的偶对称为一条边，若边是无方向的，记为(u,v)，若边是有方向的，记为
n9一条边可以是有方向的，也可以是无方向的。若图的边是有方向的，则称为有向图；若图的边是无方向的，则称为无向图。
在有向图中，若两节点间存在同始点和同终点的多条边，则把这些条边称为平行边，含有平行边的有向图称为有向多重图。
定义2.2 网络是图的扩展。若图中的每一条边分别被赋予一个相应的权，则称为网络，网络可以用三元组G=(V,E,W)表示，其中W为所有边的权组成的集合。
与图类似，可以根据网络中的边是否具有方向，定义无向网络与有向网络。
若网络中没有环，则称为无环网络，若网络中有环，则称为有环网络。
定义2.3 链路容量。通信网络中链路的容量表示链路允许的最大传输速度，即在单位时间内允许传输的最大比特数。
一个图或网络描述了一个通信网络的拓扑结构，网络中的节点对应于通信网络的节点，网络中的边对应于通信网络中连接两个节点的链路，边上的权对应于链路的容量。
本书与经典的网络编码文献[3～5]相似，仅研究有向无环网络的线性网络编码多播。即把所研究的多播网络（单源多播网络或多源多播网络）看成是一个有向无环网络，且链路容量是一个正整数。
定义2.4 子图。子图是图G=(V,E)的一个子集，可以表示为G=(V,E)，其中V和E分别是图G中V和E的子集。11111
定义2.5 子网络。子网络是网络 G=(V,E,W)的一个子集，可以表示为 G=(V,E,W)，其中V和E分别是原网络G中V和E的子集，而111111子图中每一条边的权不能超过该条边在网络G的权。
在有向网络G=(V,E,W)中，对于任意一条有向边e∈E，若始点为u∈V，也把u称为e的尾节点，记为u=tail(e)；终点为v∈V，把v称为e的头节点，记为v=head(e)，并记e=
设是 G 中的一个点边交错序列，则称从节点至存在一条路径，由于所考虑的网络是一个有向无环网络，显然在一条路径中不会存在两个相同的点或两条相同的边。对于一条路径中的所有边，因每一条边有一个权，把其最小的权称为这条路径的容量。显然，一条容量为k(k为整数)的链路，可以拆成k条单位容量的链路，且它们的边互不重叠，只在顶点处相交。
图或网络的遍历是指从某一顶点开始，访问图中每一个顶点，有深度优先遍历和广度优先遍历两种方法。图或者网络通常采用邻接矩阵或者邻接表来表示。
定义2.6 单源多播网络。给一个有向网络G=(V,E,W)，其顶点个数记为|V|[1]，在V中指定一点，称为源点（记为s），V中的一个子集T={r,r,…,r}称为宿点集，|T|为宿点的个数，源点无输入链路，所有12|T|宿点无输出链路，所有宿点欲接收源点s播出的信息，称之为单源多播网络。
图2-1给出了一个单源多播网络的拓扑结构，其中s为源点，r、1r、r、r、r为宿点，源点欲多播信息至所有的宿点，所给的网络为2345一个有向无环网络，其中链路上标出的数字是链路的容量，代表链路的最大传输速度。图2-1 单源多播网络示例
在单源多播网络中，一般来说链路的容量为单位时间内能传输的最大比特数，其量纲的单位为单位时间传输1 bit，事实上可以通过选取不同的单位时间和容量值使量纲的单位改变。同一条链路，根据选取的单位时间不同，可以改变其容量值和量纲的单位。例如，其量纲的单位可以为单位时间内传输的1 bit，也可以把若干比特看成是字母表上的一个字符，选取量纲的单位可以是单位时间内的传输的1字符数。总可以选取合适的单位时间，使各链路的容量值均为整数。例如，取单位时间为 t，一条链路的容量为 8，其中量纲的单位为 1 比特/单位时间，假设字母表上的每个字符为 4 bit，现取时间单位为 2t，若取量纲的单位为 1 比特/时间单位，则链路的容量为16，若取量纲的单位为1字母/时间单位，则链路的容量为4，即单位时间（2t）内传输的4个字符。
定义2.7 多源多播网络。若网络中有多个源点和多个宿点，则称为多源多播网络，若所有源点对应的宿点集相同，则称为多源多宿多播网络；若每一个源点对应的宿点集不相同，则称为一般的多源多播网络。
图2-2给出了一个多源多播网络，有3个源点s、s、s，有8个宿123点r、r、…、r，其中源点 s欲多播数据至{r,r,r}，源点 s欲多播12811232数据至{r,r,r}，源点 s欲多播数据至{r,r,r}（注意到t、t、t为3个4563678123虚拟宿点，它们采用虚拟链路分别与3组宿点相连）。图2-2 多源多播网络示例
3个源点传输的信息共享同一个网络，它们可以竞争网络的资源。
在一个有向无环多播网络G=(V,E,W)中，选定一个源点和一个宿点，记源点为s，宿点为r，现在构造一个子网络G1=(V1,E1,W1)，其构造方法为：初始时，G1为空，然后检测E中的每一条边e(e∈E)，若e在连接s至r的一条路径上，则把head(e)、tail(e)加入至V1中，并把e加入到E1中，且保留e的权值不变。这样构造的子网络必定是一个单源单宿网络（即只存在一个源点和一个宿点），如图2-3所示。
定义 2.8 割集与割值。给定单源单宿网络 G=(V,E,W)，其中，s 为源点，r为宿点，若点集V被剖分为两个非空集合V和V(V为V的ssss补集，V=V−V)，其中， s∈V ，r∈V ，则把所有尾节点在 V中且sssss头节点在V的边构成的集合称为分离s与r割集，记为(V,V)，而把割sss集(V,V)中所有边的容量之和称为这个割集的容量（简称割值），记ss为cut(V,V )，如式（2-1）所示。ss图2-3 割集示例
随着选取的V不同，所取得的割集也不同，在所有分离源点s和s宿点r的割集中，必定存在割值最小的割集，其最小割集的容量记为mincut(s,r)。
香农等[9]指出，通信网络中源点至宿点的最大传输速度不能超过分离源点与宿点间的最小割的容量。通常把分离源点与宿点的最小割称为源点到宿点的最大流。
寻求网络中的源点至宿点的最小割有多个算法，其中Ford-[10]Fulkerson算法（标号法）是较为经典的算法，该算法是一个多项式时间算法，它能求出任何两个节点间的最小割mincut(v,v)，同时能ij够找出从v至v的mincut(v,v)条“边不重叠”的路径。ijij
关于最大流算法（Ford-Fulkerson算法）的实现，本书附录中给出了两种不同语言书写的程序。
在具有多个宿点的单源多播网络中，对于r∈T，记分离源点s与宿点r的最小割为mincut(s,r)，那么在单源多播网络中，源点的最大传[3]输速度为
显然，式（2-2）的 C 表示分离源点 s 与所有宿点的最小割值，也可以记为mincut(s,T)。
定义2.9 同步方式。同步方式是指网络数据传输时，任一节点只有当所有输入信道的信息到达后才进行编码运算并转发，且编码运算的时间相对于信道上数据传输的时间小得多，节点也没有排队延时，节点只有传输延时和计算延时。
定义2.10 多播容量与多播率。多播容量是指当采用同步方式时，若各宿点能同时完整、正确地接收到播出源点信息的前提下，源点允许的最大发送速度，根据香农理论，多播容量等于分离源点与所有宿点的最小割的最小值，如式（2-2）所示，用符号C表示；多播率是指实际传输数据时，源点选定的数据发送速度，记为h，若要求宿点能正确地接收源点的信息，则必须满足条件h≤C。2.2 优化理论和模型[6]
最优化理论与方法属于运筹学的范畴，指的是在完成一项任务中有多种途径或多种方案可供选择，针对某一个或多个目标，选择使目标达到最优（最大或最小）的一种途径。最优化理论是一门应用相当广泛的学科，是当今重要的应用数学分支。它讨论了决策问题的最佳选择特性，构造寻求最佳解的计算方法。典型的优化模型有线性规划、非线性规划、整数规划等模型。若决策变量是连续型的，则称为连续型优化问题，若决策变量是离散型的，则称为离散型优化问题，也称为组合优化问题。即使最简单的组合优化问题，如整数线性规划问题，也难以找到确定性的方法求其最优解，即组合优化问题一般来说是 NP 难的，从而启发式算法是较好的近似求解算法，大量的文献[11通过实验表明，这些启发式算法如遗传算法、进化策略、进化规划～14]是行之有效的。[6]
最优化研究的工作可以归纳为以下几个步骤。
Step1 确定目标。即确定快策者期望从方案中得到什么。
Step2 问题的描述。进行问题分析和数据采集，以便了解问题的本质和问题中各个变量间的关系，得出模型的框架，并考虑问题能否分解为若干子问题，确定模型的细节，如问题尺度的确定、可控制决策变量的确定、不可控制决策变量的确定、有效性度量的确定以及各类参数和常数的确定。
Step3 模型的研制。模型是对各变量关系的描述，是解决问题的关键，构成模型关系有几种类型，常用的有定义关系、经验关系和规划关系。
Step4 计算手段的确定。在模型确定后，需要选用数值方法求解模型。其中包括对问题变量性质（确定性、随机性、模糊性）、关系特征（线性、非线性）、手段（模拟、优化）及使用方法（现有的、新构造的）等的确定。
Step5 数据收集。把有效性实验和实行方案所需的数据收集起来加以分析，研究输入的灵敏性，从而可以更准确地估计得到的结果。
求解一个优化问题是在问题空间中找出其最优解，问题空间通过满足约束条件来指定，一般通过不等式或等式约束来刻画问题空间。假设一个优化问题有 n个决策变量，m 个优化目标，记决策向量为x=(x,x,…x)，目标函数向量为f(x)=(f(x),f(x),…,f(x))，且优化的目12n12m标是使目标函数达到最小化，则优化问题的数学模型为
若目标函数向量只有一个分量，则是单目标优化问题；若目标函数向量的分量多于一个，则是多目标优化问题。已有相当多的文献对单目标优化问题进行了求解研究，除了少数问题可以采用确定的方法求解外（如线性规划问题），一般采用启发式算法，如采用遗传算法、[11～15]进化策略、进化规划和粒子群优化算法等进行求解。求解多目标优化问题通常通过求出其Pareto集，再由用户从Pareto边界中选择其中一个解。求解多目标优化问题的方法常用的有基于进化算法的[16～19]NSGAII和SPEA等方法。2.3 遗传算法的基本理论与应用[11]
遗传算法（GA）是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，它按照达尔文生物进化论中优胜劣汰、适者生存的自然选择机制进行搜索，在搜索过程中对每一个搜索的位置进行评估，得到较好的位置，再从这些较好的位置进行搜索直到达到目标，这种智能搜索方法省略大量无用的搜索路径，提高了搜索效率。
遗传算法应用于优化问题求解时，可以视为一种随机化搜索过程。在该搜索过程中，GA 不仅需要搜索解空间的全局最优解，而且应当充分利用已获得的解空间信息去逼近当前局部最优解，称之为求泛与求精。
采用遗传算法求解问题时，首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，即必须把问题空间映射到编码空间，在编码空间内通过随机产生初始群体，逐代进化后，求出编码解，然后把编码解转化为问题解。
在搜索过程中，必须为每一个搜索点确定适应度函数值，根据适应度函数值对各搜索点进行评估和比较，从中挑选出较优的搜索点，即进行选择操作，并从这些较优的搜索点开始进行下一步搜索。从当前较优的搜索点开始，通过执行交叉和变异操作生成下一批搜索点，这一过程叫做进化迭代。进化以编码群体为基础，以群体的中个体位串的遗传操作实现进化，建立起一个迭代过程。在这一过程中，通过随机重组编码位串中的重要基因，使子代位串集合优于父代位串集合。群体中的个体通过不断进化，逐渐接近或达到最优解，最终达到求解的目标。
遗传操作有选择、交叉和变异。选择是针对适应度函数值对群体的个体进行相互比较，从中选择出较优的个体；交叉操作一般有单点交叉和多点交叉，即两个个体以随机的方式互相交换染色体后，产生两个子个体，而子个体继承了两个父个体的部分基因特性；变异操作是模拟生物进化过程中染色体上某位基因发生突变现象，以一定的概率改变染色体的结构或物理性状。[11]
遗传算法的基本流程和结构如下。
Step1 选择编码策略，把问题空间转换为编码空间。
Step2 定义适应度函数fit(·)。
Step3 确定遗传策略，包括群体大小和选择、交叉、变异策略；确定交叉概率、变异概率等遗传参数。
Step4 随机产生初始群体。
Step5 计算群体中个体的适应度值。
Step6 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体。
Step7 判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回Step5，或者修改遗传策略再返回Step 5。
Step8 进化结束，从最后一代群体中选出最优个体，并把最优个体从编码空间转换至问题空间，得出问题空间的解，并以此作为问题的近似最优解。2.4 有限域的基本概念
采用线性网络编码实现多播连接，则网络节点需要对信息进行编码或解码运算，编码和解码的实质是在向量空间上进行运算，向量空[20]间必须建立在数域上。而网络单次传输信息的长度是有限的。因[21,22]而只有有限域满足这一要求，线性网络编码的编码运算与解码运算在有限域上进行。
在抽象代数中，域（Field）可以被定义为一个任意的代数系统（一个集合及定义在该集合上的运算），此代数系统中可以进行加、减、乘、除四则运算，其运算具有封闭特性，即任何两个元素的四则运算的结果仍为域中的元素，并满足代数运算中的结合律、分配律和[22]交换律。有限域最早是由伽罗华于 1830年在证明一般五次方程的不可解性时引入的，为了纪念这位数学家，有限域也称为伽罗华域（GF,Galois Field），它在计算机科学、编码理论、信息论与密码学中都有重要的应用。
定义2.11 群。对于定义在非空集合 G 中的二元运算“*”，若满足：1）运算在G上是封闭的；2）结合律；3）具有单位元e；4）对−1*−1集合G上的任意元素x，存在逆元x，使xx=e，则称代数系统
定义 2.12 域。对于一个定义在非空集合 F 中上的两个二元运算加“+”和乘“*”，若满足：1）
尽管只定义了两种运算“+”和“*”，由于
有限域是指元素个数有限的域，有限域上元素的个数称为有限域的阶，以下定理给出了有限域的相关性质。
定理2.1 有限域的阶是一个素数的方幂。
定理2.2 对每个素数p和每个正数n，在同构意义下存在唯一的pn阶的有限域。
上述两个定理的证明可参考文献[21]。
以上表明，有限域元素的个数（阶）要么是一个素数，要么是一个素数的若干次方，因此可以把一个有限域（伽罗华域）写成nGF(p)，其中，p为一个素数，n为正整数。m
在计算机科学中，由于普遍采用二进制，从而伽罗华域GF(2)m备受人们青睐，以下讨论伽罗华域GF(2)的构造。[21]
一个数域是形如
定义2.13 GF(2)=<{0,1},⊕,⊗>是一个有限域，对于a,b∈{0,1}，22则
上述定义了元素个数最小的域GF(2)={0,1}，每个元素均为一位二进制数，其中加法运算对应于二制的异或运算，乘法运算对应于二进制的与运算，其运算规则如下：1⊕1=0⊕0＝0，0⊕1＝1⊕0＝1，22221⊗1＝1，0⊗0＝1⊗0＝0⊗1＝0。2222m
定义2.14 GF(2)上未定元x的多项式是指形如a+ax+…+ax(a≠01mm0)，其中，a∈GF(2)（域中的一个元素是指该域集合中的元素，a∈iGF(2)是指a∈{0,1}，以下同)，m称为多项式的次数；定义多项式的两种运算⊕和⊗，其含义如下。
任取，则
其中，M=max(m,n)，当i>n时，取a=0；当i>m时，取b=0。ii
具有两个运算⊕和⊗的 GF(2)上的所有多项式构成的集合称为多项式环，记为GF(2)(x)。
两个多项式的运算与普通多项式的运算方法相同。两个多项式相加时，对未定元x指数相同的项合并同类项，即对应系数相加；两个多项式相乘，转化为对应的项分别相乘再相加，而两个单项式相乘是指对未定元x的指数相加，系数相乘。其中系数的相加与相乘符合GF(2)上的定义，即为⊕与⊗。22
定义2.15 设a(x),b(x)∈GF(2)(x)，且b(x)≠0，定义deg(a(x))为a(x)的次数，则存在唯一的一对GF(2)(x)上的多项式q(x)和r(x)，使式（2-8）成立。
其中，deg(r(x)) 记r(x)= a(x)mod b(x)，mod表示取余式。 定义2.16 不可约多项式。一个GF(2)(x)上的多项式，如果只能被1和其本身整除以外，不能被GF(2)(x)上任何其他的多项式整除，则称为不可约多项式。 事实上，判断一个次数为m的多项式是否为不可约多项式，只需用GF(2)(x)上所有次数不超过的多项式去试除，如果均不能整除，则该多项式为不可约多项式。n 定义2.17 有限域GF(2)的定义。p(x)是GF(2)(x)上的一个n次不可n约多项式，GF(2)= 其中，a(x)⊕b(x)是GF(2)(x)中多项式的加法运算。（2）乘法运算规则a(x)*b(x)=(a(x)⊗b(x))mod p(x)（2-10） 其中，a(x)⊗b(x)是GF(2)(x)中多项式的乘法运算。n 在GF(2)中，还可以引申得到减法运算、除法运算和求逆运算。（3）减法运算：a(x)−b(x)=a(x)+b(x)。（4）除法运算：，b(x)≠0，当且仅当b(x)*c(x)=a(x)。－1－1（5）求逆运算：a(x),当且仅当a(x)* a(x)=1。 在以上的论述中，请注意<⊕,⊗>、<⊕,⊗>、<+,*>的区别与联系。22在本书中，<⊕,⊗>用于GF(2)上两个元素运算，<⊕,⊗>用于GF(2)(x)22n上两个多项式的运算，<+,*>表示域GF(2)上两个元素的运算。n 伽罗华域 GF(2)也称为 GF(2)的扩域，其构造有多种方法。例如可以采用本原元的办法，即找到一个本原多项式，本原元是这个多项式的根，其中伽罗华域的所有元素均可以表示为这个根的若干次方，这种构造方法对于域的乘法运算非常方便，但对域的加法运算无规律；也可以采用向量空间的方法，还可以采用分裂域的方法，定义n2.17事实上是构造了一个伽罗华域GF(2)，采用的是生成多项式（不[21]可约多项式）构造的方法。m 对于GF(2)，它的元素就是所有次数小于m的GF(2)上的多项式，可以表示如下。m2m−1m GF(2)={0,1,x,1+x,1+x+x,…,1+x+x+…+x}，一共有2个元m素，也可以用这些多项式的系数代表一个元素，即GF(2)={00…00,00…01,00…10,…,11…11}，即每一个元素是一个m bit的二进制数。m在通信系统中，若采用GF(2)的元素为数据传输单位，也称为mGF(2)为字母表，每一个元素称为一个字符。 若采用某个 m 次不可约多项式 p(x)按定义 2.17 来生成一个伽罗华域，则把p(x)称为该伽罗华域的生成多项式。显然GF(2)上的m次不可约多项式可能不止一个，采用不同的生成多项式 p(x)，尽管得到的伽罗华域的元素相同，加法运算规则也相同，但根据式（2-10），具有不同的乘法运算规则，则得到了不同的伽罗华域，但它们之间是相[21]互同构的。22 例如，对于GF(2)，选定一个不可约多项式 x +x+1，其元素为{0，1，x，x+1} 4 个元素，采用多项式的系数代表其相应的元素，则可以把这个域写成{00,01,10,11}，则其加法运算与乘法运算如表2-1、表2-2所示。附录1中列出了部分伽罗华域的生成多项式。表2-1 二进制形式加法运算表2-2 二进制形式乘法运算
试读结束[说明：试读内容隐藏了图片]