网络编码的基本思想是允许网络中间节点参与编译码，看起来并不复杂的思想却在信息论领域带来重要的理论突破，指出信息流和商品流的本质不同，将对未来网络的构架和发展产生重大和深远的影响。网络编码的实际应用是网络编码理论发展的重要目标，也是学术界和工业界努力的重要方向。本书较系统阐述网络编码的基本技术和典型应用。本书注重阐明技术和应用背后所蕴含概念和原理的物理意义，力求深入浅出，便于读者理解和领会。

序 言 网络编码（Network Coding）是信息论与编码领域的重要理论突破，其基本思想是允许网络的中间节点参与编译码。网络编码的基本思想指出，信息流（Information Flow）和商品流（Commodity Flow）存在着本质不同，并由此开创了网络信息论领域的一个全新方向。网络编码理论及其应用将对当前和未来网络通信的体系架构和发展产生重要和深远的影响。 初识网络编码的读者可以通过了解“蝶形网络”（Butterfly Network）快速领略网络编码的魅力。本书编著者之前出版的《网络编码原理》侧重阐述网络编码的原理，本书则侧重阐述网络编码的核心技术和典型应用。 网络编码大道至简：①基本思想简单，即允许中间节点参与编译码；②名称简单，对“网络编码”进行拆分，“网络”和“编码”均是大家再熟悉不过的概念，结合在一起却构成本质上不同于信源编码和信道编码的新概念——信息流，“信息流”概念打破了经典信息论中“商品流”不能进一步细分的结论，是21世纪网络信息论领域的一个重要突破。本书从网络编码主要技术和典型应用的角度，带领读者感受简单思想闪烁在不同应用中的神奇。 本书的撰写原则：注重概念清晰及概念之间的内在逻辑关系；重要概念均附注英文对照，便于读者在拓展阅读时能够将这些重要概念与英文文献中的概念对应；读者可以结合作者最新研究成果，不断加深对网络编码的理解。 本书编著者的最新研究成果包括以下3个方面。 （1）提出将几何与网络编码结合的“空间信息流”概念。空间信息流（Space Information Flow，SIF），也称空间网络编码（Space Network Coding）或空间中网络编码（Network Coding in Space），于2011年由本书编著者Li Zongpeng首先提出。空间信息流不同于我们熟知的网络信息流（Network Information Flow，NIF），其也称网络中网络编码（Network Coding in Network）或图中网络编码（Network Coding in Graph）。SIF和NIF的本质区别可理解为连续域和离散域的区别。想要快速了解空间信息流（空间网络编码），可详见本书编著者黄佳庆提出的“五角星网络”（Pentagram Network）。空间信息流首次将几何与网络编码结合，具有重要方法论的意义。几何的发展已有几百年历史，具有极其丰富的数学思维和方法，将几何这种强有力的数学工具引入网络编码，可为网络编码的研究注入新的思路和角度，帮助我们更加深入地研究和揭示网络编码的本质。随着对网络编码研究的不断深入，我们对于网络编码的理解也将不断更新。 （2）构建的漩涡网络打破了信息论与编码领域的一个普遍观念。网络编码理论中最基础的定理证明了在任意单信源多信宿的多播网络中，只要所选的有限域足够大，便可在该域上构建达到网络多播容量的网络编码解。由此，信息论与编码领域学者的一个普遍观念是有限域越大，就越有可能在该域上构建达到网络多播容量的网络编码解。然而，本书编著者孙奇福与李宗鹏于2015年构建出一个与直觉相反的名为漩涡网络（Swirl Network）的多播网络，打破了这个传统观念：漩涡网络在5个元素的有限域上存在网络编码解，但在某些非常大的有限域上并不存在任何网络编码解。该重要发现还首次明确地指出除了有限域的大小，有限域的乘法子群代数结构也会影响多播网络可解性，从而为读者提供了崭新的角度以完善网络编码理论。 （3）提出可减小额外编译开销的循环移位网络编码方案。向量网络编码是经典标量网络编码的一个扩展，其将基于有限域的编码操作延伸至基于向量空间，从而指数倍地增加了备选编码操作数量，大大增加了编码灵活性。为了降低网络编码所引入的较高计算代价，在向量网络编码框架下，本书编著者孙奇福与李宗鹏于2019年建模出一套用循环移位操作代替经典有限域操作的全新网络编码技术，并针对多播网络提出了一种适用于任何奇数码长的高效构建循环移位网络编码解的算法。与传统标量网络编码方案相比，可大幅降低循环移位网络编码方案的编译码复杂度。基于该成果，循环移位网络编码可以潜在地替代目前大部分已知的标量网络编码传输方案，从而减小应用网络编码所带来的额外编译码开销。 网络编码需要从理论走向实际，本书通过网络编码在多个领域不同的典型应用，找到网络编码较为共性的内容呈现给读者，以期抛砖引玉，激发出更多新的思想火花，从而发挥网络编码的优势，并将网络编码劣势的影响程度降到最低。同时，我们也期待开发出更多的典型应用，让网络编码逐步从理论走向实用，最终走向规模化商用。网络编码应用的发展之路充满挑战但也充满机遇，有志于此的读者一定会大有所为。 本书组织结构的安排如下。第1章为网络编码概述，包括网络编码的概念、网络编码的优势和劣势、网络编码的可行性、网络编码的本质和网络编码的主要研究内容。第2章详述网络编码基础，包括标量线性网络编码、向量线性网络编码，网络编码与有限域以及网络编码与拓扑，其中一个与通常直觉相悖的重要结论是，有限域大小并不是影响多播网络线性可解性的唯一参量，简单地讲，有限域增大却不一定线性可解。第3章介绍网络编码技术，包括随机网络编码、实际网络编码、分代网络编码、多级网络编码、稀疏网络编码和部分网络编码等，这些技术多为随机网络编码的变型，已广泛应用于网络通信的多个领域。后续章节阐述网络编码的多种典型应用：第4章阐述网络编码在无线多跳网络中的应用；第5章阐述网络编码在无线中继网络中的应用；第6章阐述网络编码在内容分发网络中的应用；第7章阐述网络编码在网络交换中的应用；第8章阐述网络编码在网络监测中的应用；第9章阐述网络编码在分布式存储中的应用；第10章阐述网络编码在软件定义网络中的应用；第11章阐述格网络编码；第12章阐述网络编码在几何空间中的应用——空间网络编码（空间信息流）。 本书受国家自然科学基金项目“空间网络编码的关键理论与方法”（No. 61271227）和“多播网络编码中线性可解性若干新问题研究”（No. 61771045）资助。 本书第2章2.1～2.3节、第9章和第11章由北京科技大学计算机与通信工程学院孙奇福教授编著，其余章节由华中科技大学电子信息与通信学院黄佳庆副教授编著。本书由武汉大学计算机学院李宗鹏教授审校。 本书在编著过程中参阅的国内外书籍和文献均列于本书的参考文献中，在此向所有作者表示衷心感谢！ 感谢家人的默默支持！衷心感谢李晓艳在校稿过程中提出的宝贵意见！ 本书第二编著者黄佳庆特别写给黄翊安的话：本书的撰写过程贯穿你的出生和成长，并终于在你即将走进华科幼儿园、开始你的人生新阶段之时出版。虽然这份惊喜来得有些晚，但从未缺席。因为想做成的事情，不过保持努力做而已。也愿你的人生道路上以成长型思维为伴，人生的无限可能才有可期！ 限于编著者的知识水平和时间，书中难免有不妥和疏漏之处，热忱欢迎广大读者批评指正（意见和建议请发至邮箱jqhuang@mail.hust.edu.cn）。

目 录 第1章 网络编码概述 001 1.1 网络编码的概念 002 1.1.1 网络编码快速入门——蝶形网络 003 1.1.2 网络编码即“计算换吞吐量” 005 1.1.3 网络编码是路由的超集 006 1.1.4 网络编码与信源编码、信道编码的比较 006 1.2 网络编码的优势和劣势 007 1.2.1 网络编码的优势 007 1.2.2 网络编码的劣势 014 1.3 网络编码的可行性——随机网络编码 016 1.4 网络编码的本质——信息流 017 1.5 网络编码的主要研究内容 021 1.5.1 基于不同性能指标的网络编码 022 1.5.2 基于不同条件的网络编码 027 1.5.3 与不同的理论结合的网络编码 032 1.5.4 基于不同分层的网络编码 033 本章小结 036 本章参考文献 037 第2章 网络编码基础 055 2.1 标量线性网络编码 056 2.1.1 数学模型 056 2.1.2 线性可解性 062 2.1.3 线性解高效构建算法 064 2.2 向量线性网络编码 066 2.2.1 数学模型 066 2.2.2 线性可解性 075 2.2.3 循环移位线性网络编码 078 2.3 网络编码与有限域 088 2.3.1 单源多播网络 088 2.3.2 多源多播网络 093 2.4 网络编码与拓扑 096 2.4.1 图子式 097 2.4.2 网络编码与图子式 098 本章小结 099 本章参考文献 100 第3章 网络编码技术 103 3.1 随机网络编码 104 3.1.1 编码原理 104 3.1.2 译码原理 105 3.1.3 硬件加速 107 3.2 实际网络编码 107 3.3 分代网络编码 110 3.3.1 代内网络编码 110 3.3.2 代间网络编码 111 3.4 多级网络编码 113 3.5 稀疏网络编码 114 3.6 部分网络编码 115 本章小结 117 本章参考文献 117 第4章 网络编码在无线多跳网络中的应用 121 4.1 网络编码在无线Ad-Hoc网络中的应用 122 4.2 网络编码在无线传感器网络中的应用 123 4.3 网络编码在无线Mesh网络中的应用 124 4.3.1 COPE 124 4.3.2 MORE 126 4.3.3 MIXIT 126 本章小结 129 本章参考文献 130 第5章 网络编码在无线中继网络中的应用 133 5.1 物理层网络编码 134 5.2 异构物理层网络编码 136 5.3 模拟网络编码 142 5.4 复数域网络编码 146 本章小结 147 本章参考文献 147 第6章 网络编码在内容分发网络中的应用 151 6.1 网络编码在P2P文件下载中的应用 152 6.2 网络编码在P2P流媒体直播中的应用 154 6.3 网络编码在P2P流媒体点播中的应用 157 本章小结 159 本章参考文献 159 第7章 网络编码在网络交换中的应用 163 7.1 网络编码与冲突超图 164 7.2 流内网络编码 165 7.3 流间网络编码 167 本章小结 168 本章参考文献 169 ? 第8章 网络编码在网络监测中的应用 171 本章小结 175 本章参考文献 175 第9章 网络编码在分布式存储中的应用 177 9.1 最大距离可分码 178 9.2 再生码 179 9.3 局部可修复码 184 本章小结 185 本章参考文献 185 第10章 网络编码在软件定义网络中的应用 189 10.1 软件定义网络 190 10.1.1 软件定义网络架构 191 10.1.2 SDN与主动网络的比较 193 10.1.3 SDN与网络功能虚拟化的比较 195 10.2 网络编码在SDN中的实现 197 本章小结 199 本章参考文献 200 第11章 格网络编码 203 11.1 格码与计算转发 204 11.2 格网络编码概述 206 本章小结 213 本章参考文献 213 第12章 空间网络编码 215 12.1 空间网络编码与空间路由比较 217 12.1.1 空间路由 217 12.1.2 空间网络编码概述 231 12.1.3 空间网络编码与已有研究的关系 234 12.2 基于多播的空间网络编码 239 12.2.1 空间网络编码性质 239 12.2.2 空间网络编码算法 242 12.3 基于多单播的空间网络编码 247 本章小结 249 本章参考文献 250