网络编码--权威专家王新梅教授学术讲座.ppt

1 网络编码networkcoding 西电ISN国家重点实验室2005 3 2 概要 1 网络编码的提出及现状2 网络编码的基本原理3 基于网络编码的纠错码4 无线组播中的网络编码5 结束语 3 1 网络编码的提出 在现有通信网络中 网络节点只是对收到的信息进行存储和转发 扮演着转发器的角色 但是从信息理论的观点来说 没有理由让节点只能进行存储转发 可以让节点对多条输入边上收到的信息进行一定的线性或非线性操作 编码 然后再发送出去 起着编码器的作用 网络编码正是根据这思想而产生的 在接收节点上 通过一定的运算 译出信源所发的信息 4 网络编码的提出 2000年 R Ahlswede等人在IEEEtrans IT上发表了一篇题为 网络信息流 的文章 提出了网络编码的概念 那么 什么是网络编码呢 网络编码能给我们带来什么好处呢 5 网络编码的提出 点对点的最小割最大流定理 对于已知的网络流图 从发点到收点的流量的最大值小于或等于任何一个割切的容量 即记 6 网络编码的提出 一个组播 multicast pointtomultipoint 传输 信源为 接收节点集合为 那么可达最高组播速率为如果采用传统传输方法 可能无法达到速率 如果采用网络编码 可达到该最高速率 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 无线组播中的网络编码 基于无线组播特性的无线网络编码有以下特点 可以实现以网络的最大流传输信息 这是网络中容量的理论上限 可以降低无线网络中的能量消耗 这对以电池为能源供给的无线网络来说 是至关重要的 这种方法使系统转移矩阵中的变量个数由指数级降为多项式级 从而大大降低了实现网络编码算法的复杂度 这种处理方法在降低网络编码实现算法复杂度的同时 并没有增加网络编码字