一种基于网络编码的应用层多播算法一种基于网络编码的应用层多播算法
研究了对多播网络进行网络编码的方法,提出了一种基于网络编码的应用层多播算法。该算法在计算网络拓扑
时考虑了链路的花费。源端和中间节点使用随机线性编码方法进行编码,在目的端进行解码操作使得目的端能
从乱序的信息和部分丢失的信息中恢复出原始数据,提高了网络的可靠性。通过对ns-2的扩展并进行仿真实
验,结果证明了基于网络编码的应用层多播算法是可以提高网络的吞吐量,并且和网络中最大的吞吐量比较接
近。在信息块不是很大的情况下,编码延迟率的增长是在一定的范围内的。
摘摘 要:要: 研究了对多播网络进行
关键词:关键词: 多播;网络编码;吞吐量
随着信息技术的不断发展,各种通信网络与人们工作生活的各个方面结合得越来越紧密。网络服务的多样化以及针对网络
传输质量要求的不断提高,如何提高现有网络资源的利用率,优化网络,已成为当今网络通信研究的重要课题之一。传统的网
络多播中,网络节点只对数据分组进行路由或复制,很难达到网络多播的最大传播容量。而且多播组上的所有接收者以相同的
吞吐量接收数据。这样如果从源到特定的接收者之间的通道上有一个瓶颈链路,则吞吐量将会被这个瓶颈链路的容量所限制。
2000年,AHLSWEDE R[1]等人提出了网络编码,其核心思想是在网络中的节点采用不加冗余的编码。利用网络编码,网
络节点可以把收到的多个数据包通过一定的编码手段重新组包再发送到下一节点,接收端收到一定数量的包后通过解码获得数
据。要对一个任意给定的多播网络进行网络编码,目前已有的方法有2种:一种是由Ralf Koeter等人提出的基于代数结构的网
络编码方法[2],这种方法是一种指数时间算法。另外一种重要的网络编码方法是由Peter Sanders等人提出的一种多项式时间
算法的网络编码方法[3],这种方法相对第一种方法而言不仅算法复杂度简化了,而且有一个很大的优点,就是在进行从源节
点到各个终端节点进行传输信息之前,先选好从源节点到各个终端节点的传输路径。因此,在同样的信息传输速率下减小了对
网络资源的占用,同时使网络编码变得更简单。
1 网络编码概念网络编码概念
网络中的节点对信息比特流进行一定的操作,如模2加、“与”、“或”等,而不仅仅是对其进行复制转发,称之为网络编码。
在参考文献[1]中,作者给出了一个多播网络的例子,采用网络编码时,传输速率比仅使用路由、转发时的要快,并且达到了
多播网络的速率上限C=min{ci}(ci从信源s到接收节点ri的最小割最大流值)。LI S Y R[4]等人随后表明采用线性的网络编码在有
限大的域中能够达到速率上限C。图1(a)为一个单源二接收多播传输网络图,网络中边上标的是链路的容量,即1 bit/单位时
间。实际网络中容量为K bit/单位时间的链路可拆开成K条容量为1 bit/单位时间的并行链路,因此为简单起见,图1中的所有链
路的容量都为1 bit/单位时间。
假如网络中的节点只对其收到的信息进行复制转发,则此网络多播速率无法达到2 bit/单位时间。因为接收节点3在1个单位
时间内只能转发从节点1和2过来的2个bit中的1个,如果3转发从1节点过来的信息,则接收节点t1,可以收到2 bit/单位时间,
但是接收节点t2,只能收到1 bit/单位时间。假设从源发向节点1的信息bit为b1,从源发向节点2的信息bit为b2。图1(b)中的节
点3将分别从节点1和2过来的信息b
1
和b
2
进行模2加,然后发向节点4,于是接收节点t1在1个单位时间内收到了b1和b
1
+b
2
,于
是可以通过b
1
+(b
1
+b
2
)=b
2
运算来得到b
2
,也就是说,接收节点t
1
,在1个单位时间内相当于收到了b
1
和b
2
。同理可以知道接收
节点t2在1个单位时间内也相当于收到了b
1
和b
2
于是图1(b)的传送方法达到了多播速率(2 bit/单位时间)。
2 一种基于网络编码的应用层多播算法一种基于网络编码的应用层多播算法
从当前主要的基于网络编码的应用层多播算法的比较分析当中可以看到,网络编码应用到应用层多播需要知道网络的拓扑
结构。现有的几种机制都是基于已知的网络拓扑结构,基于代数的构造方式提供了网络编码与应用层多播融合的最基本的模
型,它引入了转移矩阵来描述输入变量与输出变量之间的关系,使得对于网络编码是怎样应用到应用层多播这种机制有了更加
清晰的概念,但是这种模型对于具体的网络拓扑没有展开。而基于多项式时间算法,它运用最小割最大流算法构造网络拓扑,
使得这种拓扑结构能更加有效地传输编码信息。然而,它要求拓扑结构是一个无延时的理想状态,因此,这种算法求得的网络
最大吞吐量可能是理想状态的。正是基于以上分析,本文提出了一种基于随机方式的网络编码的应用层多播算法,在考虑链路
花费的情况下,提高网络的吞吐率。
2.1 编码理论编码理论
源端将原始的m个信息流编为一组并编码成n(n≥m)个大小相等的新信息流;中继节点对隶属同组的源端编码信息流进行重
编码并转发;目的端收到足够多的编码信息流后利用解码算法恢复出原始信息流。
2.1.1 源端编码源端编码
采用随机线性码[5-6]作为网络编码方案,按照产生的先后顺序,源端将每m个信息编为一组,记为x
1
,x
2
,…x
m
,并赋予相
评论0
最新资源