随机线性网络编码[精选].ppt

L/O/G/O 编码模型 方案举例 总结与展望 overview A Random Linear Network Coding Approach to Multicast 简要介绍 简要介绍 最大流最小截定理 网络容量问题 随机分布问题 满足网络容量要求 多源（包括相关源）多径问题 一般组播网络结构 简要介绍 对于除了信宿节点外的所有中间节点，只要在一个足够大的有限域上随机选择它们输入链路到输出链路的映射，且各节点映射关系的选取是相互独立的，从而保证各信宿能以较高概率成功译码 各链路上的系数向量和信源发送的信息进行同步传输，信息在通过编码节点时，系数向量根据随机选取的映射关系进行更新，最终信宿节点收到的输入信息将包含输入链路对应的全局编码向量和信源发送的信息流，然后采用高斯消元法（解线性方程组）正确译码获得信源原始传输的信息 简要介绍 我们考虑的问题 ·怎样构建随机线性网络编码 ·怎样在分布网络中有效的将信息传输到接收节点 编码模型 做出的假设 ·每条链路的容量是一比特每单元，如果某条边的容量大于一比特每单位时间，则看做是几条并行的边。如果边的容量不是整数，则将时间单元取得大一点，使得小数部分可以近似成整数。 ·假设每条链路的延迟是一样的。 ·对于线性相关源，我们认为每一个独立信源的熵率是一比特每单位时间，如果不是，则将它们变成一些并行的熵率是一比特每单位时间的源的集合。 ·对于任意相关源，我们要求信源的熵是整数，并且有着任意的联合概率分布 ·对于不同的节点，它们要处理的随机过程之间是相互独立的，这个假设符合通信网络一般的情况 Add your title in here 编码模型 多信源的Slepian —Wolf定理： 有r个离散的无记忆信息源 ,它们是随机二进制序列，对每个信源独立进行编码，再进行联合译码，其性能跟所有信源联合编码是一致的。只要满足在r个信源中任取k个信源的和速率，不能小于这k个信源以剩余的r-k个信源为条件的熵，而对于总的和速率不能小于这r个信源的联合熵。 Add your title in here 编码模型 不考虑延迟 考虑延迟 考虑边容量为1的情况，每个节点在等到所有进入此节点的信息后才发往离开此节点的出边 有着v个节点和信息传输速率是r的循环网络可以变成非循环网络，此网络有kv个节点，信息传输速率大于等于（k-v）r,信息在这种网络上的传输可以被模仿成原来循环网络k个时隙的步骤。这种情况我们假设每个链路的延迟是一样的。 Add your title in here 编码模型 符号简介（1） 非循环图G=（V,E）表示的网络中，每条边可以根据网络拓扑进行顺序编号:如 ，对于每条从属于E的边，它的源表示为o( ),它的目的节点表示为d( )。一个路径就是一系列的链路集合 ，对任意的i ≠j, ≠ 。 节点V 即d( ) 既称为head（ ） 又称为tail( ) 边 边 O( ) 进入一个节点的边数称为一个节点的入度，由一个节点发出的边数称为节点的出度，节点的入度和出度的和称为节点的度数 Add your title in here 编码模型 符号简介（2） 定义 为所有以节点V为结束点的边的集合 定义 为所有从节点V开始的边的集合 接收机β处的终端链路的集合称为 是在节点v收集到的u(v)个离散随机过程 在边e上传输的随机过程称为Y(e) Add your title in here 编码模型 如图是一个非延迟网络，对于链路e上的随机处理过程满足 对于汇节点的输出Z是由属于 的所有边上的随机过程Y(e)形成的 这里的α，β，ε都是从伽罗华域中随机选择的 如果α，β，ε是独立的，则系统是时不变的，否则系统是时变的 Add your title in here 编码模型 表示在源节点观察到的输入信号矢量 另v’点是一个网络的汇结点，我们认为 是这个节点的输出过程矢量 另M表示一个网络的传输矩阵，这样z=x*M,对于固定的系数α，β，ε，我们不难看出，M矩阵里的数也是从伽罗华域中选取的。 Add your title in here 编码模型 GF( )域 以m=4为例，它的本原多项式为 ,即 在伽罗华域中，加法等于对应位异或 先给出推导过程 0 0000 1000 1 0001 0011