网络编码.ppt

1,网络编码,王新梅 西安电子科技大学ISN国家重点实验室,2,概 要,1.网络编码的提出及现状2.网络编码的基本原理3.基于网络编码的纠错码4.无线组播中的网络编码5.结束语,3,1.网络编码的提出,在现有通信网络中，网络节点只是对收到的信息进行存储和转发，扮演着转发器的角色。但是从信息理论的观点来说，没有理由让节点只能进行存储转发，可以让节点对多条输入边上收到的信息进行一定的线性或非线性操作（编码），然后再发送出去，起着编码器的作用。网络编码正是根据这思想而产生的。在接收节点上，通过一定的运算，译出信源所发的信息。,4,网络编码的提出,2000年，R.Ahlswede等人在IEEE trans-IT上发表了一篇题为“网络信息流”的文章，提出了网络编码的概念；那么，什么是网络编码呢？网络编码能给我们带来什么好处呢？,5,网络编码的提出,（点对点的最小割最大流定理）对于已知的网络流图，从发点 到收点 的流量 的最大值小于或等于任何一个割切的容量，即 记。,6,网络编码的提出,一个组播(multicast:point to multipoint)传输，信源为，接收节点集合为，那么可达最高组播速率为 如果采用传统传输方法，可能无法达到速率。如果采用网络编码，可达到该最高速率。,7,网络编码的提出,一个经典例子,采用网络编码后，达到速率。,8,网络编码的提出,网络编码带来的好处：使组播传输速率达到最小割最大流决定的网络容量的上限节省网络带宽资源消耗均衡网络负载提高网络鲁棒性,9,网络编码的发展过程,2000年，Ahlswede等提出了网络编码的概念。2002年，Koetter等给出了网络编码的代数构造算法，是指数时间算法（集中式）。2002年，Cai等提出了基于网络编码的网络纠错码概念。2002年，Cai等提出了采用网络编码时的信息完安全性问题。2003年，Sander等给出了网络编码的多项式时间算法（集中式）。2003年，Chou等提出了分布式网络编码，通过仿真得到其性能。2003年，Ho等也提出了随机网络编码（分布式）。2004年，Wu等将网络编码应用于无线网络以节省能量。,10,网络编码的现状,线性网络编码和非线性网络编码；分布式网络编码和集中式网络编码；网络编码在组播和非组播网络中的应用目前，组播集中式线性网络编码算法主要有两种：代数构造方式和多项式时间算法；,11,2.网络编码的基本原理,信息传输网络可用图 表示信源节点集：信宿节点集：边 的头节点用 表示 边 的尾节点用 表示,假设每条边容量为1比特/单位时间（可通过合适选取单位时间大小和将链路进行拆分实现）,12,网络编码的基本原理,网络编码的数学描述(适用于组播和非组播传输）对边集 中的每条边，存在一种 映射：这是对应于每条边的编码函数。,13,网络编码的基本原理,网络编码的数学描述(适用于组播和非组播传输）目的节点 为了得到所需信息，存在映射：映射 是对应于目的节点 的第 个信源符号的译码函数。,14,网络编码的基本原理,线性网络编码的代数构造 设所有信源 的总信息输出速率是 比特/单位时间。把它们的输出进行一个定序，如下：其中 是节点 的信息输出速率。,15,网络编码的基本原理,线性网络编码的代数构造 设 是无延迟的通信网络。我们称这样的编码为线性网络编码，如果对于网络中的每一条边 的传输符号均满足：其中。,16,网络编码的基本原理,线性网络编码的代数构造 定义 矩阵 和 矩阵 如下：则系统转移矩阵为：,是信源输出到所有链路的转移矩阵，,是链路间的转移矩阵。,17,网络编码的基本原理,组播线性网络编码成功的条件 组播通信网络中，信源输出向量：接收节点 接收向量:其中,是接收节点 的系统转移矩阵。于是，为了由接收到的信息向量 解出信 源输入，则必须要求系统转移矩阵 可逆。,18,3.基于网络编码的纠错码,基于网络编码的差错控制是针对网络、而非一条链路或一条路径进行操作的。通过合适的选择信源空间，可以纠正传输网络中几条链路上发生的传输错误，这是一个比较新的差错控制方式，称之为基于网络编码的差错控制。,19,基于网络编码的纠错码,参与多播传输的链路数用 表示。组播网络的网络容量 为 比特/单位时间。,20,基于网络编码的纠错码,如果从某条链路上输出的符号不等于输入的符号，那么称发生错误。如果在传输网络中总共有 条链路发生错误，就称为网络发生了 个错误。如果一个基于网络编码的纠错码能纠正所有错误个数小于等于 的情况，就称该码是-差错控制码。,21,基于网络编码的纠错码,把发生在传输网络上的错误用一个 维行向量 表示，称为错误向量。如果其 中有 个分量不为零，则称错误向量重为。,接收符号:,网络译码后:,(当有错误发生时):,其中 是 的子矩阵。,22,基于网络编码的纠错码,对于接收节点,定义 t-错误图样集合如下：,对于接收节点，定义t-错误图样的差分集合如下：,让,23,基于网络编码的纠错码,对于任意,和 可分,即能纠任意重量小于等于 t 的错误，当且仅当,(如果存在 和，满足，则存在错误图样 和，使，即，则会出现 和 不可分的情况。),24,基于网络编码的纠错码,对于一个线性网络编码,要使任意两个信源向量 和 可分,当且仅当,25,基于网络编码的纠错码,如果能够构造一个 奇偶校验矩阵,满足对于所有的,有,那么让（是 维空间）,则对于任意,和 可分。,关键问题：给定一个有限域，值能够达到多大？,26,基于网络编码的纠错码,矩阵 的构造(Varshamov 算法）：,构造过程：1:将 划分成多个子集合。其中 对于 必须满足 且向量 的最后一个非零分量的位置是。,27,基于网络编码的纠错码,2：令 维列向量空间，,是由 的前 列向量得到，,即,28,基于网络编码的纠错码,从 中任选一列作为。,3：,(2)从 中任选一列作为。,(i)从 中任选一列作为。,持续上面操作直到，因此得到矩阵。,29,基于网络编码的纠错码,可成功构造出 的条件：,对于线性网络编码，如果，则对任意 有,30,基于网络编码的纠错码,可成功构造出 的条件：,因为,31,基于网络编码的纠错码,可成功构造出，即构造出基于网络编码的纠错码，可纠任何满足 的错误。,因此当有限域大小 满足,32,基于网络编码的纠错码,根据上述构造校验矩阵的方法，对于给定的有限域 可得到 的一个下界值：,但此构造方法复杂度过大，有待找出一种可行的方法，来构造出 达到该下界值的 校验矩阵。,的一个上界值（Hamming 界）：,其中,33,易知，为使，根据下界值知 就可以构造出该纠错码。需要计算的差分错误图样的总个数有,基于网络编码的纠错码,小规模网络的纠错码构造：,34,4.无线组播中的网络编码,无线组播特性：,如果节点i向节点j和k发射相同的信息时，节点i上的发射功率：,如果节点i向节点j和k发射不同的信息时，i上的发射功率：,35,无线组播中的网络编码,一个例子（传统路由）：,36,无线组播中的网络编码,一个例子（利用网络编码来节省能量）：,37,无线组播中的网络编码,另一个例子（无线网络中基于网络编码的信息互换）：,传统方法,基于网络编码的方法,38,无线组播中的网络编码,利用无线组播特性降低能量消耗时，用到以下两点：广播特性 无线通信网络固有的；节点的输出边上必须携带相同的信息 使用网络编码。,39,无线组播中的网络编码,对于任何边，这里的 是非源节点，我们假定其上传输相同的信号，表示为：,40,无线组播中的网络编码,类似的，接收节点输出的随机过程可表示为:,41,无线组播中的网络编码,定理：由 表征的无线组播网络是可解的当且仅当对于所有的接收节点 相应的系统转移矩阵 的行列式在多项式环 上非零。,42,无线组播中的网络编码,基于无线组播特性的无线网络编码有以下特点：可以实现以网络的最大流传输信息，这是网络中容量的理论上限；可以降低无线网络中的能量消耗，这对以电池为能源供给的无线网络来说，是至关重要的；这种方法使系统转移矩阵中的变量个数由指数级降为多项式级，从而大大降低了实现网络编码算法的复杂度。这种处理方法在降低网络编码实现算法复杂度的同时，并没有增加网络编码字母表的大小。,43,5.结束语,网络编码是近年来兴起的一个新的研究领域，其正在引起人们越来越多的重视，而且其中有很多有待进一步解决的问题。网络编码在传输速率、负载消耗、负载均衡、鲁棒性等方面带来的好处有待深入研究。基于网络编码的差错控制是一种新的差错控制思想。网络编码需要网络路由器具有编码功能，且现有路由算法、传输协议等需要改变。,44,谢 谢！,