网络编码的工作原理_技术问题和应用.doc

网络编码的工作原理、技术问题和应用王海涛， 付鹰（解放军理工大学通信工程学院 ， 江苏省南京市210007）络中的协同网络编码以及网络编码中的路由与 调 度机制。0引言为了充分利用稀缺的无线网络的资源 ， 扩大网 络覆盖范围和提高系统容量 ， 提出采用多跳传输的 通 信 方 式 ， 典型的多跳网络技术包括 Ad Hoc 网 络、无线网状网和无线传感器网络等 。在多跳无线网 络中， 信息可以通过中继节点进行复制 、 放大和转 发。但是，中继节点的简单转发一般无法实现网络的 最 大 流 传 输 。 针对这一问题提出的网 络 编 码 （Net- work Coding） 技术可以实现网络的最大流传 输 ，并 有效解决中继节点的传输瓶颈问题 。 网络编码的一 个简单思想是允许网络的中间节点对接收到的信息 进行一定的信息处理 ，然后再转发出去 ，同时信宿节 点也通过一定的信息处理方式 ， 译出信源发出的信 息。这样，节点通过额外的信号处理提高了网络的整 体性能 。网络编码强调节点间的相互协作 ， 它从网络信 息论的角度出发 ， 将节点合作编码的概念应用到整个 网 络 中 ，以提高网络传输 性 能 、可靠性和安全性 。网络编码技术涉及信息论 、 计算机网络和图论等学 科知识 。 本文首先介绍网络编码的发展历程和基本工作原理 ， 然后说明网络编码的显著特点和主要技术问题 ，特别是线形网络编码的内容 。 此外，简单介 绍随机网络编码的基本知识 ， 最后说明无线通信网1网络编码的发展简史早 在 上 世 纪 50 年代香农就指出 ：“通 信 网 络 端 对端的最大信息流是由 网络有向图的最小割决定 的”，但传统路由器的存储转发模式难以达到最 大 流 最小割定理规定的上界 。 直到 2000 年，香港中 文 大 学 R.Ahlswdee 等人在发表的论文 Network Infor- mation Flow 中首次提出了网络编码 ， 并 依 据 信 息 论严格证明了网络编码允许中间节点对接收到 的 信 息进行编码并转发 ， 接收节点通过相应的解码 获 得 原始信息 ，这样可以达到通信网络的容量上界 ，从 而 最大限度利用网络资源 。 网络编码的提出从本 质 上 打破了通信网络中传统的信息处理方式 ， 是通 信 网 络研究领域中一个重要的里程碑事件 。实际上 ，香农 定理解决了点对点信道的容量极限问题 ， 而网 络 编 码则解决了如何达到单源到多点以及多源到多 点 的 网络容量的极限问题 。网络编码彻底改变了通信网络中信息处理 和 传 输的方式 ，是信息理论研究领域的重大突破 ，已 经 引 起学术界广泛关注和高度重视 。 国外许多著名 大 学 和研究机构都在积极开展对网络编码理论和应 用 的 研究， 与此同时网络编码也逐渐引起了国内学 术 界 的关注和重视 。 网络编码的一个研究重点是网 络 编 码的构造方式 ，当前主要有两种方式 ：一种是网 络 编 码的代数构造方式 ， 另一种是实现网络编码的 多 项基 金 项 目 ： 国 家 自 然 科 学 基 金 资 助 项 目 （61072043）5摘 要 网 络 编 码 是 一 种 允 许 中 继 节 点 对 已 接 收 到 的 数 据 包 进 行 编 码 后 再 发 送 出 去 、接 收节点通 过相应的译 码过程得到 完整信息 的信息处理 技术 。 首先概 述了网络编 码的发展 历 史 ，并 介 绍 了 网 络 编 码 的 基 本 原 理 。 在 此 基 础 上 说 明 了 网 络 编 码 的 显 著 特 点 和 主 要 技 术问题 ，归纳总结了 网络编码的 主要应用 领域 。 最后，对 网络编码未 来的发展方 向进行了 展望。关键词 网络 编码 ； 信息论 ； 组播； P2P 网络； 网 络安全图 1 一个简单的网络编码示例 技 术 交 流2011 年 第 2 期式时间算法 。 前者是在已知整个网络拓扑信息的情况下， 用一个系统转移矩阵来描述信源输入信息和 信宿接收信息之间的关系 ， 并通过构造符合要求的系统转移矩阵来实现网络编码 ； 后者进一步简化了网络编码的构造 ，它也是在已知拓扑的情况下 ，首先 通过最大 流 - 最小割算法找到完成组播所需的路径 集合， 然后在找出的这个子图中自上而下地确定各节点所需进行的操作 ， 从而可以将网络编码构造的 复杂度从指数级降低到多项式级 。 这两种方法都要 求已知网络拓扑信息 ， 但也可以采用不需网络拓扑 信息的分布式网络编码和随机网络编码 。 分布式网 络编码的实现是通过在网络中传输的每个数据报上 预先留出一些位置 ， 以记载此数据包在前面各编码 节点上所采取的操作 ， 然后接收节点可以根据收到 的数据包直接译出信源所发送的信息 。 这种方法可 以在不知网络拓扑信 息的情况下实现网络编码 ，但 会增加网络负载 。对于随机网络编码 ，中间编码节点 对接收到的信息会在一个有限域内随机选择一个元 素作为组合的系数 。 研究表明 ，只要有限域足够大 ， 随机网络编码的成功率就很高 。此外， 关于无线网络中网络编码的研究正在成 为一个新的研究热点 。 由于无线网络自身的一些独特特性 ， 网络编码应用于无线网络可以提高网络的 传输容量和降低能耗等 。另外，网络编码可以与其他 技术相结合 ，如网络编码和纠错码的结合 、网络编码和路由协议及调度算法的结合 ， 网络编码和协同通 信以及网络编码和加密机制的结合 ，等等。是完成数据复制操作 ， 单播传输中节点将收到的 分组在一定时延内复制到某个输出端口 ， 而在多播 传 输中， 节点将收到的分组在一定时延内复制到多 个输 出 端 口 。 令 输 入 分 组 为 xk （t）， 则输出可表示为 ak*xk（t-dk），dk 表 示 第 k 个 分 组 的 时 延 ，ak=1 或 0，即 分组或成功传输或被丢弃 。如果采用网络编码 ，那么输 出 可 表 示 为 yk（t）=fxk（t）, xk-1（t）, xk-m（t），其 中 ，最 简 单 有 效 的 一 种 f（函 数 ）是 异 或 （XOR）操 作 。这种编码获得的好处归功于节点不仅能够执行复制操 作 ，而且可以执行其他 合 适 的 操 作 ，如 异 或 操 作 。此 外 ，借助于这种编码的灵活性 ，使 得 NP 完 全 问 题 有可能变成多项式可解的 。 对于具有动态连接的大 规模网络 ， 这种特性可以大大简化网络设计和改 善 网络性能 。在此， 通过一个简单示例来说明网络编码方 法 带来的好处 。 如图 1 所示， 一个网络包含三个通 信站 ：一 个 基 站 A、一 个 中 继 站 R 和 一 个 用 户 站 B。 A和 B 之 间 建 立 多 条 连 接 ， 假定只有一种业务类型 ，为了支持网络编码 ， 将时间帧划分成时 隙 。如 果 A和 B 希望分别向对方发送数据块 x 和 y，使 用 传 统的通信技术 ，执行上述信息交换需要 4 个时隙 ：在第一个时隙 ，A 向 R 传送 x， 在第二个时 隙 ，R 向 B 传 送 x，在 第 三 个 时 隙 ，B 向 R 传 送 y，在 第 四 个 时 隙 ，R 向 A 传送 y。 借助于网络编码技术 ，可以将需要的时 隙 数 减 为 3 个 ： 在 第 一 个 和 第 二 个 时 隙 ，A 和 B分 别 向 R 传 送 x 和 y，在 第 三 个 时 隙 ，R 对 x 和 y 执 行异或操 作 ，并 向 A 和 B 广播异或的分组 。 由 于 A 和 B 自 己 存 储 有 x 和 y 分 组 ，可以方便地通过异或 操作进行译码得到 y 和 x。2网络编码的基本工作原理网络编码最初是针对组播技术提出来的 。组播的基本思想是 ： 源主机只需发送一份数据到组播组地址， 组播组中的所有接收者都可以收到同样的数 据副本 ，而网络中的其他主机则收不到该数据 。网络编码是针对传统组播技术无法实现最大流最小割定 理确定的容量上限而专门提出的 。 网络信息流的最大 流 最 小 割 定 理 ：对于已知的网络流图 ，信 源 S 到 信 宿 T 的流量的最大值 W 等 于 其 最 小 割 的 容 量 ， 即 max flow（S, T）=min C（S, T）。网络编码技术是一种非常有效的信息处理技 术，可以显著改善网络的性能 ，并且还能在多项式时 间 内 求 解 一 些 NP （Non-deterministic Polynomial）完全问题 。 我们知道 ，通信网络中节点的主要功能此外， 利用新近提出的物理层网络编码机制 还可以解决长期困扰 无线通信网络的两个突出问题 ：干扰和安全性问题 。例 如,在 上 面 的 示 例 中 ，采 用 常规 通 信 方 式, 节 点 A 和 B 不 能 同 时 向 R 发 送 信 号 ，否则会互相干扰 。但是采用物理层网络编码 ，在第一 个时隙节点 A 和 B 可以同时向 R 发送分 组 ，节 点 R接收到组合的信号 （x+y）。 在第二个时隙 ，节点 R 广播此组合信号 ，然 后 A 和 B 可以正确地译码得到想 要的信号 ， 这种情况只需要两个时隙 。 采用这种 编6技 术 交 流2011 年 第 2 期码，中间节点只能收到组合的信号 ，可以防止中间人截获信息 ，以确保更好的机密性 。 但是，这种编码机 制的性能依赖于时间同步 、 无线信道中的功率和相位控制等多个因素 。仅带来了额外的时延 ， 而且还要考虑网络节点同 步问题。再者，节点的编码和解码在一定程度上增加了 网络运算复杂度 。 需要指出的是 ，编码算法越复杂 ，解码的复杂度也随之增加 ， 因此需要折中考虑网 络编码的增益与复杂度 ，尽量使用低复杂度 、增益较大 的网络编码算法 。另外，网络编码对误码率有较高的要求， 只有较小的误码率才能保证网络编码的有 效性和可靠性 ，否则会降低系统的整体性能 。3网络编码的显著特点网络编码是允许中继节点对已接收到的多个数 据包进行编码后再发送出去 、 接收节点通过相应的 译码过程得到完整信息的信息处理技术 。 网络编码 可以提高网络吞吐量和健壮性 ， 同时可以通过分散 信息流以平衡网络负载 ， 但会增加信息传输时延和 节点的处理复杂度 。具体来说 ，网络编码具有如下显 著特点 ：a）增加网络吞吐量 ：已经证明 ，网络编码可以实 现网络的最大流传输 ， 网络的最大流即为从源点到 收点的最大数据传输速率 。 对于一个多源多接收端 的网络 ，只考虑其中一个接收端时 ，对应的该接收端 会有一个传输速率 ， 而网络编码的优势在于当所有 接收端同时接收信息时 ， 每个接收端仍可以保持原 有的速率 。 需要指出的是 ，网络节点数越多 ，网络编 码提高网络吞吐量的优势越明显 。b）提 高 网 络 健 壮 性 ：网络编码的独特之处是编 码后的各个数据包具有相同的重要性 ， 接收端只要 收到足够数量的数据包就可以进行解码 ， 从而提高 网络的健壮性 。另外，网络编码可以改善时延敏感及 丢包率较高的网络的传输性能 。 对于传统的端到端 传输方式 ，提高传输可靠性的两种主要方法是 ARQ（自 动 重 传 请 求 ）和 FEC（前 向 纠 错 ），前 者 以 时 延 为 代价获得了更优的速率 ， 后者以速率为代价获得了 更低的网络时延 。若采用网络编码 ，即允许中间节点 对输入信息进行组合再传送出去 ， 则可以同时在时 延和速率方面都达到最优 。c）均 衡 网 络 负 载 ：使用网络编码可以 充 分 利 用 网络中的各条链路 ， 使流量在传输过程中均匀地分 布于整个网络 ， 从而有效避免链路瓶颈造成的网络 拥塞。d）增 强 网 络 安 全 性 ：网络编码使传输的信息更 加分散 ，并且在一定程度上将信息进行隐藏 ，更难窃 听，提高了信息的安全性 。e）增加了信息传输时延和计算复杂度 ：对 网 络 编码而言 ，编码节点需要缓存收到的信息 ，然后通过 一定的处理 ，组合成待传送的编码信息 。这种运算不4网络编码的主要技术问题网络编码涉及通信 、 信号处理和计算机网络 等 众多学科领域 ，面临许多有待解决的技术问题 ，简述 如下：a）网络编码节点的选取方案 ：在 给 定 的 网 络 结 构中，只需选择其中的部分节点实施网络编码 ，而其 他节点只需具有传统的存储转发功能即可 。这样，不 仅可以降低网络编码算法的复杂度 ， 而且也降低 了 对节点硬件的要求 ， 从而使网络编码的应用更为 广 泛。 另外，无线网络要特别考虑节点能量和稳定性 ， 选择编码节点时应尽可能将能量高 、 运算能力强 和 存储空间大的节点作为编码节点 ， 以提高网络的 鲁 棒性。b）网络编码算法的设计 ：目前，网络编码主要有 确定性和随机性两种编码方案 ， 分别用于不同的 网 络架构上 。对于结构较简单的网络 ，可以选择比较简 单的确定性算法 。而对于无线网络 ，则主要采用随机 编码机制 。 对于随机编码 ，如果符号集加大 ，则信息 成功传输概率也会增大 ，但会增加数据报头的负担 。 因此，符号集的大小需要权衡各种因素 ，慎重选择 。c）网络编码复杂度的分析 ：网 络 编 码 涉 及 大 量 的数学运算 ，计算复杂度较高 ，对于确定网络编码而 言 ，所需的符号集较小 ，编码复杂度较低 ，但 是 需 要 中心节点集中控制网络信息 。 对于随机网络编码而 言，所需符号集较大 ，并且节点传输的系数向量也会 占用一定的网络带宽 。总之，网络编码复杂度受到符 号集大小 、节点计算复杂度 、网络编码方案等诸多因 素的影响 ，需要全面分析 。d）适 合网络编码的路由机制 ：网络编码可以将 多个输入的信息通过编码 组合成一个信息发送出 去 ，消除了节点处的排队时延 ，从而达到在组播通信 中本由多个接收节点共享的网络资源如同每个接收 节点独享资源的效果 。 传统的路由机制一般为了减7技 术 交 流2011 年 第 2 期少排队时延而尽量回避交叉路径 ， 而网络编码则无此限制 ，可以采取更加自由的路由机制 ，在出现交叉 路径时可以进行相应的网络编码来解决排队时延问题。 进一步讲 ，为了更充分地利用网络编码机制 ，可以有意采用交叉路径 ， 从而达到用较少的中继节点 即可起到同样的信息传输效果 。e）协同编码机制的研究 ：协 同 机 制 可 以 带 来 分 级增益 ，但是以更多的中继节点为代价 ，每个用户端需要单个或者多个中继节点 为其提供中继协同服 务。采用网络编码之后 ，可以使单个中继节点为两个 或多个终端服务 ，从而减少所需的中继节点的数量 。f）网 络编码的安全性分析 ：网络编码不仅可以 提高网络吞吐量 ，还会对网络的安全性能产生影响 。一方面 ， 网络编码造成的信息分散性和编译码特性 增加了信息破译难度 ，改 善 了 安 全 性 ；另 一 方 面 ，对确定性编码算法而言 ， 由于传输过程涉及较多的节 点数目 ，加之编码算法确定 ，又会降低系统的安全性 能。 因此，应针对不同的系统选用合适的编码算法 ，以提高网络的安全性能 。恢复原始数据 ，增强了网络的容错性和鲁棒性 。当前的研究热点集中于物理层网络编码 、 协同网络编 码 方案设计以及网络编码协议性能评估等 。 相对于传统的协作机制 ， 协同网络编码方案在同等的频谱 效率下可达到更高的分集增益 。2）P2P 网络网 络 编 码 应 用 在 P2P 网络具有两个明显的好 处：第一，减少了文件的下载时间 。 在一个大范围分 布式的端到端系统中 ， 找到最优的分组传输路径 十 分困难 ， 在主机对于底层网络拓扑知之甚少的情 况 下更是如此 。而使用网络编码 ，网络拓扑和发送次序 对文件发送时间的影响将会大大减小 。第二，由于编 码后的分组具有多样性的特点 ， 即使服务器在文 件 下载过程中离线 ， 或某些网络节点下载结束后立 刻 离开，都不会产生太大影响 ，所以基于网络编码的方 案与一般的方案相比具有更好的健壮性 。 相关实验 证明，如果所有的对等实体都运用网络编码 ，则 P2P 系统的平均下载速率较不用网络编码 时 提 高 了 23 倍 ， 而且网络编码能够适应 P2P 系 统 的 动 态 变 化 ， 如节点动态加入或离开等 。3）网络安全传统的网络安全手段主要利用数据加密 、 哈 希 函数和消息认证等方式来确保数据的安全传输 。 但是这些方法存在一定的局限性 ，如计算复杂度较大 、数据传输速率较低 、消息冗余较大等 ，因此需要寻找 一些安全 、高效的数据传输方式 。虽然网络编码的初衷在于提高网络的吞吐量 ， 但是随着进一步研究 发现， 它也可以很好地应用于网络安全领域 。 具体 来 说， 网络编码可以很好地防范网络窃听和对抗拜 占庭攻击 。 Jaggi 提出一种用散列函数检测拜占庭攻击 的方法 ，并给出了一种多项式复杂度的分布式算法 ，在可对抗攻击的 前提下达到最优组播速率 。 Krohn等人利用椭圆曲线算法给出了一种适用于网络编码 的签名方案 ，除了可检测被修改的分组 ，还加入了对数据的身份认证功能 。4）分布式文件存储分布式文件存储是网络编码的又一个应 用 热 点 。Aeedanski 等人研究了在多个存储资源受限的节点间进行分布式文件存储的问题 ， 比较了无编码 存储、 基于纠删码存储和采用随机线性码存储的三 种 策略。仿真结果表明 ，基于随机线性码的分布式存储5网络编码的应用网络编码作为新兴的富有前途的信息传输和处 理技术 ，实 际上是一种从总体上提高系统性能的方 法 ，有着广泛的应用场合 。 应用领域涵盖无线网络 、 P2P 系 统 、 网 络 安 全 和分布式文件存储等多个方 面 。例 如 ，在 P2P 网 络 中 ，网络编码可以加速信息下 载时间并提高系统健壮性 ；再 者 ，网 络 编 码 可 以 增 大网络通信流量 ，特 别适合提高带宽受限的无线网 络 的 吞 吐 量 。 网络编码还特 别适合组播和广播场 景 ，因 此 可 用 于 Mesh 网 络 、Ad Hoc 网 络 及 无 线 传 感网络等无线自组网 。 为了不对现有网络的软硬件 设 备 和 相应的协议做较大修改 ，可 以选择在高层实 现网络编码 。 下面简要介绍网络编码当前的主要应 用场合 。1）无线网络无线网络的物理层广播特性和业务流的双向性 非常适合使用网络编码 。应用网络编码 ，可以解决传 统路由 、 跨层设计等技术无法解决的问题 。 具体来说， 网络编码在无线网络中可以减少数据包的传播 次数，降低无线发送能耗 。 采用随机网络编码 ，即使网络部分节点或链路失效 ， 最终在目的节点仍然能8技 术 交 流2011 年 第 2 期策略，在无需全局文件服务器的参与时 ，其性能接近集中式全局调度算法 。技术一定会从理论走向实用 ， 而且其应用领域必 定会越来越宽泛 。6结束语网络编码理论是网络通信研究领域中的一项重 要突破 ，自首次提出以来 ，已迅速发展成一个重要的 研究方向 ，并对信息论 、编码、通信网络 、网络交换理 论 、无 线 通 信 、计 算 机 科 学 、密 码 学 、运 筹 学 、矩 阵 理 论等学科领域带来深远影响 。 尽管学术界已经对网 络编码理论和应用进行了广泛的研究 ， 并从理论模 型上证实了运用网络编码能提升网络的性能 ， 但验 证的步骤或模拟的环境大多基于若干假设或理想化 的模型 ，与实际的应用环境还有一定的差距 ，由此得 出的某些结论尚存局限性 。此外，研究过程大多基于 理论上定性的分析 ，缺乏定量的研究 。 因此，将网络 编码应用于实际 ，构建基于网络编码的实用系统 ，还 有待更严格 、更深入 、更广泛的研究与实践 。 我们有 理由相信 ，随着网络编码研究的不断深入 ，网络编码参考文献1彭 木 根 ， 王 文 博 . 协同无线通信原理与应用 M. 北 京 ：机械工业出版社 ，2009.陶 少 国 ，黄 佳 庆 ，杨 宗 凯 ，等. 网络编码研究 综 述 . 小 型 微 型 计 算 机 系 统. 2008，29（4）：583-589.R Ahlswede. Network Information Flow J. IEEE Trans. Info. Theory，2000,46（4）：87-93.郑 刚 ， 胡 晓 惠 . 网络编码的研究进展 J. 计 算 机 研 究与 发 展 ，2008，45（3）：400407.Fong S L，Yeung R W. Variable-rate linear nerwork coding C. Chengdu：IEEE Information Theory Work- shop,2006.2345王海涛 （1976），男，副教授 ，博士，主要研究方向为无线自组网 、普适计算和认知无线电 。收稿日期 ：2011-01-03!（上接第 4 页）灾难的发生 。有人测算过 ，提前几秒钟刹车就可避免90%以上 的 交 通 事 故 ， 而我国每年交通事故死亡七 八万人 。使用传感器 ，汽车行驶在道路上就可以随时 检测出车流量 、 车速甚至车辆形状 。 当你行驶在路 上 ，不用听收音机的路况信息 ，只要通过传感器 ，就 能了解实时路况 。机动车辆过拱桥时 ，驾车者往往会 有一个视线