随机线性网络编码PPT课件

1、简要介绍简要介绍对于除了信宿节点外的所有中间节点，只要在一个足够大的有限对于除了信宿节点外的所有中间节点，只要在一个足够大的有限域上随机选择它们输入链路到输出链路的映射，且各节点映射关域上随机选择它们输入链路到输出链路的映射，且各节点映射关系的选取是相互独立的，从而保证各信宿能以较高概率成功译码系的选取是相互独立的，从而保证各信宿能以较高概率成功译码各链路上的系数向量和信源发各链路上的系数向量和信源发送的信息进行同步传输，信息送的信息进行同步传输，信息在通过编码节点时，系数向量在通过编码节点时，系数向量根据随机选取的映射关系进行根据随机选取的映射关系进行更新，最终信宿节点收到的输更新，最终信宿

2、节点收到的输入信息将包含输入链路对应的入信息将包含输入链路对应的全局编码向量和信源发送的信全局编码向量和信源发送的信息流，然后采用高斯消元法息流，然后采用高斯消元法（解线性方程组）正确译码获（解线性方程组）正确译码获得信源原始传输的信息得信源原始传输的信息第1页/共22页简要介绍简要介绍我们考虑的问题我们考虑的问题怎样构建随机线性网络编码怎样构建随机线性网络编码怎样在分布网络中有效的将信息传输到接收节点怎样在分布网络中有效的将信息传输到接收节点第2页/共22页编码模型编码模型做出的假设做出的假设每条链路的容量是一比特每单元，如果某条边的容量大于一比特每条链路的容量是一比特每单元，如果某条边的容

3、量大于一比特每单位时间，则看做是几条并行的边。如果边的容量不是整数，则每单位时间，则看做是几条并行的边。如果边的容量不是整数，则将时间单元取得大一点，使得小数部分可以近似成整数。将时间单元取得大一点，使得小数部分可以近似成整数。假设每条链路的延迟是一样的。假设每条链路的延迟是一样的。对于线性相关源，我们认为每一个独立信源的熵率是一比特每单对于线性相关源，我们认为每一个独立信源的熵率是一比特每单位时间，如果不是，则将它们变成一些并行的熵率是一比特每单位位时间，如果不是，则将它们变成一些并行的熵率是一比特每单位时间的源的集合。时间的源的集合。对于任意相关源，我们要求信源的熵是整数，并且有着任意的联

4、对于任意相关源，我们要求信源的熵是整数，并且有着任意的联合概率分布合概率分布对于不同的节点，它们要处理的随机过程之间是相互独立的，这对于不同的节点，它们要处理的随机过程之间是相互独立的，这个假设符合通信网络一般的情况个假设符合通信网络一般的情况第3页/共22页 Add your title in here编码模型编码模型多信源的多信源的Slepian WolfSlepian Wolf定理：定理：有有r r个离散的无记忆信息源个离散的无记忆信息源 , ,它们是随机二进制序列，它们是随机二进制序列，对每个信源独立进行编码，再进行联合译码，其性能跟所有信源对每个信源独立进行编码，再进行联合译码，其性

5、能跟所有信源联合编码是一致的。只要满足在联合编码是一致的。只要满足在r r个信源中任取个信源中任取k k个信源的和速率，个信源的和速率，不能小于这不能小于这k k个信源以剩余的个信源以剩余的r-kr-k个信源为条件的熵，而对于总的个信源为条件的熵，而对于总的和速率不能小于这和速率不能小于这r r个信源的联合熵。个信源的联合熵。 rXXX,21第4页/共22页 Add your title in here编码模型编码模型不考虑不考虑延迟延迟考虑考虑延迟延迟考虑边容量为考虑边容量为1 1的情况，的情况，每个节点在等到所有每个节点在等到所有进入此节点的信息后进入此节点的信息后才发往离开此节点的才发往

6、离开此节点的出边出边有着有着v v个节点和信息传输速率是个节点和信息传输速率是r r的的循环网络可以变成非循环网络，此循环网络可以变成非循环网络，此网络有网络有kvkv个节点，信息传输速率大个节点，信息传输速率大于等于（于等于（k-vk-v）r,r,信息在这种网络信息在这种网络上的传输可以被模仿成原来循环网上的传输可以被模仿成原来循环网络络k k个时隙的步骤。这种情况我们个时隙的步骤。这种情况我们假设每个链路的延迟是一样的。假设每个链路的延迟是一样的。第5页/共22页 Add your title in here编码模型编码模型符号简介（符号简介（1）非循环图非循环图G=G=（V,EV,E）表

7、示的）表示的网络中，每条边可以根据网络中，每条边可以根据网络拓扑进行顺序编号网络拓扑进行顺序编号: :如如 ，对于每条从，对于每条从属于属于E E的边，它的源表示为的边，它的源表示为o( ),o( ),它的目的节点表示它的目的节点表示为为d( )d( )。一个路径就是一。一个路径就是一系列的链路集系列的链路集合合 ，对任意的，对任意的i j, i j, 。Eeee,21ieie)()(1iieoed)(ied)(jed节点节点V V 即即d( )d( ) 既称为既称为headhead（ ）又称为又称为tail( )tail( )边边ie1ie边边ie1ieO( )O( )ieie进入一个节点的

8、边数称为一个节进入一个节点的边数称为一个节点的入度，由一个节点发出的边点的入度，由一个节点发出的边数称为节点的出度，节点的入度数称为节点的出度，节点的入度和出度的和称为节点的度数和出度的和称为节点的度数第6页/共22页 Add your title in here编码模型编码模型 符号简介（符号简介（2）)(vI定义定义 为所有以节点为所有以节点V V为结束点的边为结束点的边的集合的集合veheadEevI)(:)(定义定义 为所有从节点为所有从节点V V开始的边的集合开始的边的集合)(0vvetailEev)(:)(0)(vI)(0v接收机接收机处的终端链路的集合称为处的终端链路的集合称为

9、)(,(,),2 ,(),1 ,()(vuvXvXvXv 是在节点是在节点v v收集到的收集到的u(v)u(v)个离散随机过程个离散随机过程在边在边e e上传输的随机过程称为上传输的随机过程称为Y(e)Y(e)第7页/共22页 Add your title in here编码模型编码模型如图是一个非延迟网络，对于链路如图是一个非延迟网络，对于链路e e上的随机处理过程满足上的随机处理过程满足对于汇节点的输出对于汇节点的输出Z Z是由属于是由属于 的所有边上的随机过程的所有边上的随机过程Y(e)Y(e)形成形成的的)(uI这里的这里的，都都是从伽罗华域中随机是从伽罗华域中随机选择的选择的如果如果

10、，是独是独立的，则系统是时不立的，则系统是时不变的，否则系统是时变的，否则系统是时变的变的第8页/共22页 Add your title in here编码模型编码模型)(,(,),2 ,(),1 ,(vuvXvXvXx 表示在源节表示在源节点观察到的输入信号矢量点观察到的输入信号矢量另另vv点是一个网络的汇结点，我点是一个网络的汇结点，我们认为们认为 是是这个节点的输出过程矢量这个节点的输出过程矢量)(, (,),2 , (),1 , (vvZvZvZz另另M M表示一个网络的传输矩阵，这表示一个网络的传输矩阵，这样样z z= =x x* *M,M,对于固定的系数对于固定的系数，我们不难看出

11、，我们不难看出，M M矩阵里的数矩阵里的数也是从伽罗华域中选取的。也是从伽罗华域中选取的。第9页/共22页 Add your title in here编码模型编码模型GF(GF( ) )域域以以m=4m=4为例，它的本原多项式为为例，它的本原多项式为 , ,即即 在伽罗华域中，加法等于对应位异或在伽罗华域中，加法等于对应位异或先给出推导过程先给出推导过程0 0000 10000 0000 10001 0001 0011 10011 0001 0011 1001 0010 0110 0001 0010 0110 0001 0100 0100 可以看出，当可以看出，当m=4m=4时，时，GF(4

12、)GF(4)是一个包含是一个包含1515个数的有限域，个数的有限域，且这且这1515个数循环产生。个数循环产生。在伽罗华域中，每对应一个在伽罗华域中，每对应一个m m，会有一个相应的本原多项，会有一个相应的本原多项式，根据这个本原多项式，就可以推出域里面的值。式，根据这个本原多项式，就可以推出域里面的值。 m20141423451415第10页/共22页 Add your title in here编码模型编码模型传输矩阵可以表示为传输矩阵可以表示为第11页/共22页 Add your title in here编码模型编码模型矩阵矩阵 A A为源节点输入信息与边之间的关为源节点输入信息与边之

13、间的关系矩阵，矩阵系矩阵，矩阵B B为接收节点对接收到的数为接收节点对接收到的数据进行线性组合。单源单汇的节点的信据进行线性组合。单源单汇的节点的信息传输时，只要相应的转移矩阵是满秩息传输时，只要相应的转移矩阵是满秩的，则源节点输出的信息在接收端就可的，则源节点输出的信息在接收端就可以准确的恢复。单源多汇的节点的信息以准确的恢复。单源多汇的节点的信息多播传输，利用网络编码时，只要能保多播传输，利用网络编码时，只要能保证各个目的节点对应的网络转移矩阵是证各个目的节点对应的网络转移矩阵是满秩的，则目的节点就可以准确的恢复满秩的，则目的节点就可以准确的恢复出原始发送的信息。出原始发送的信息。传输矩阵

14、可以表示为传输矩阵可以表示为第12页/共22页编码模型编码模型对有向网络来说，对网络节点进行排序，定义相应的邻接矩对有向网络来说，对网络节点进行排序，定义相应的邻接矩阵阵F F，F F矩阵的第矩阵的第i i行第行第 j j 列元素表示网络流图中第列元素表示网络流图中第i i条边与第条边与第 j j 条边的连接关系，条边的连接关系，F F可表示为可表示为其中其中 表示有向边表示有向边 的终点与有向边的终点与有向边 的起点重的起点重合，合， 是有限域中的一非是有限域中的一非 0 0 元素，则元素，则M M可表示为：可表示为：这种编码的构造简单而且有效，但是计算量大。这种编码的构造简单而且有效，但是

15、计算量大。其它,0)()(,jieejietaileheadFji)()(jietaileheadiejejiee ,TBFIAM1)(第13页/共22页编码模型编码模型图中节点图中节点 v v ，接收到编码包，接收到编码包 和和 。节点。节点 v v 应用随机网络编码的思想，在有限域中随机选取系数应用随机网络编码的思想，在有限域中随机选取系数(1,2)(1,2)，并对接收到的两个编码包进行运算并对接收到的两个编码包进行运算 ，得到新的编码系数得到新的编码系数(3,10,13)(3,10,13)，并将新的编码包发送。，并将新的编码包发送。32132xxx32154xxx)54( 2)32( 1

16、321321xxxxxx第14页/共22页编码模型编码模型随机网络编码中中间节点只需要对接收到的数据进行线性组合，随机网络编码中中间节点只需要对接收到的数据进行线性组合，而不需要判断接收到的信息是否线性相关。这样在接收节点处而不需要判断接收到的信息是否线性相关。这样在接收节点处有可能出现线性相关的编码信息导致解码失败。对于任意一个有可能出现线性相关的编码信息导致解码失败。对于任意一个可行的多播网络，如果网络编码部分或所有的编码系数都是独可行的多播网络，如果网络编码部分或所有的编码系数都是独立的均匀的在一个有限域立的均匀的在一个有限域 上选取，则所有的目的节点能够成上选取，则所有的目的节点能够成

17、功进行解码的概率至少为功进行解码的概率至少为 ，q dq d ，其中，其中 d d 表示目表示目的节点的数目，的节点的数目， 为随机选取编码系数的链路数目，为随机选取编码系数的链路数目，q q为编码为编码符号域的大小。当有限域的字母表大小符号域的大小。当有限域的字母表大小 q q 远大于接收节点数目远大于接收节点数目 d d 时，所有的接收节点可以以很高的概率恢复出原始信息。采时，所有的接收节点可以以很高的概率恢复出原始信息。采用随机线性网络编码的多播网络中，多个源节点可以相互独立，用随机线性网络编码的多播网络中，多个源节点可以相互独立，也可以线性相关。对于线性相关的源，随机线性编码起到了信也

18、可以线性相关。对于线性相关的源，随机线性编码起到了信息压缩的作用。息压缩的作用。qF)/1(qd第15页/共22页方案举例方案举例网络的目的是每个节点都能收到信源发出的两个随机过程随机流结构随机流结构(RF)(RF)源节点延两个轴向分别发送两源节点延两个轴向分别发送两 个信息个信息只接收到一个信息过程的节点只接收到一个信息过程的节点向其它三个方向发送信息向其它三个方向发送信息接收到两个信息过程的节点分接收到两个信息过程的节点分别向对应的轴向发送相应的信息别向对应的轴向发送相应的信息第16页/共22页方案举例方案举例随机编码结构随机编码结构(RC)(RC)源节点延两个轴向分别发送两源节点延两个轴向分别发送两 个信息个信息只接收到一个信息过程的节点向其它三个只接收到一个信息过程的节点向其它三个方向发送信息方向发送信息接收到两个信息过程的节点向其余的轴向接收到两个信息过程的节点向其余的轴向发送接收到的信息的线性组合发送接收到的信息的线性组合对于接收位置为（对于接收位置为（x,yx,y）的点，接收）的点，接收机能接收到两个发送信息的概率为机能接收到两个发送信息的概率为RFRFRC RC （q q是伽罗华域字母表）是伽罗华域字母表）)2(2)/11(yxq第17页/共22页方案举例方案举例RFRF方案和方案和RCRC方案