网络编码在OBS组播中的应用.pptxVIP

网络编码在OBS组播中的应用;;图1(b)表示的是网络编码方法，节点W对输入的信息进行模二加操作，然后将操作结果 发送至输出链路WX，然后又通过链路XY和XZ，最终达到信宿Y和Z。Y收到b1和 后，通过译码操作 就能解出b2，因此，信宿Y同时收到了b1和b2。同理，通过译码操作 ，信宿Z也同时收到b1和b2。由此，基于网络编码的多播实现了理论上的最大传输容量;网络编码优缺点： 1. 提高网络吞吐量 如果 为信源节点的符号空间， 为通信网络中的节点数目，则对于每条链路都是单位容量的通信网络，基于网络编码的多播的吞吐量是路由多播的 倍[16 ]. 2.均衡网络负载 图2(a)所示的通信网络，其各链路容量为2。图2(b)表示的是基于多播树的路由多播，为使各个信宿节点达到最大传输容量，该多播共使用SU、UX、UY、SW和WZ 共5条链路，且每条链路上传输的可行流为2；图2(c)表示的是基于网络编码的多播，图2(c)所示的网络编码多播所用的传输链路为9条，比图2(b)的多播树传输要多4条链路。 ;3.提高带宽利用率 图2(b) 消耗的总带宽为：5×2= 10；图2(c) 消耗总带宽为：9×1= 9，因此带宽消耗节省了10% ，提高了网络带宽利用率。 ;网络编码的分类 如果网络节点对传输的信息进行线性操作，则称为线性网络编码(Linear Network Coding)；否则称为非线性网络编码。如果网络节点对信息进行操作的系数是随机选取的，则称为随机网络编码；如果是通过算法确定出来的，则称为确定性网络编码。另外有人已经证明在有限域F q中，只要域足够大，则通过合适的线性网络编码，就能使多播传输达到最大的传输容量。目前，网络编码研究均限于有限域F q中的线性网络编码。 网络编码的构造算法 网络编码构造算法解决的主要问题是如何有效求得每条链路对应的编码向量，并运用该编码向量进行线性操作计算出链路上传输的信息向量。编码算法的复杂性是衡量网络编码能否有效实现的重要依据。典型的算法包括指数时间算法[6]、多项式时间算法[7]和贪婪算法[8]等，其中因多项式时间算法具有较低的复杂性，因此具有重要的理论和应用价值。 ;线性网络编码 线性网络编码对单位容量的信道进行编码,当连接两个节点的有向链路的容量大于1时,把这条链路分成多条单位容量的信道。对于节点v∈V,记In(v)和Out(v)分别为输入信道集和输出信道集, |In(v) |和|Out(v) |分别为节点v的输入信道数和输出信道数。 组播网络中,各节点收到对应的单位信息,或称为字符,在进行数据转发前,需要对这些信息进 行编码。我们将这类信息称为源信息。假定一个节点的源信息为X1,X2,……X|In(v) |,那么应用线性网络编码后各信道输出的信息为: Yi=gi1X1+gi2X2+……+gi|In(v) |X|In(v) | 公式(3) 其中i=1, 2,……, |Out(v) |, gi1, gi2,……,gi|In(v) |为有限域GF(2m)上的一组系数。我们将系 数gi= (gi1, gi2,……, gi|In(v) |)称为编码向量,将Yi称为信息向量。 当输出信息Yi成为下游节点的输入信息时,节点将对接收到的信息进行新一轮的编码。新的编码信息表示如下: Yi’=gi1’X1’+gi2’X2’+……+gi|In(v) |’X|In(v) |’ 公式(4) 假设接收节点接收到的编码向量为(g1, g2,……, gm),信息向量为(Y1,Y2,……,Ym),为了求出源点播出的信息,我们需要求解以下等式: Yj=gj1X1+gj2X2+……+gjnXn 公式(5) 其中, j=1, 2,…,m。也相当于求解如下的线性方程组: ;;;;光组播树多路径波长优化算法 组播路由问题从源节点的数量上分为点到多点和多点到??点的组播。处理此类问题一般有两种方法: a)将多点到多点问题看成多个点到多点问题,即为每个源节点构造一棵基于源的组播树(source-specificmulticast tree); b)为所有的源节点和目的节点建立组播树,即组播共享( shared multicast tree)。两者最大的区别在于:构造共享树需要首先选择一个组播中心。由于找出最优共享树是非常困难的[5],在研究共享树问题时总是将该问题划分为两个子问题进行研究,即中心选择问题(center selection problem)和路由选择问题( route selection problem) ? 基于最少占用波长数的核点选择算法, 具体如下: a)初始化SUM为任意大的数值, sum为零, CORE为空