网络编码VS.存储转发：移动自组网中实时多播机制仿真研究

谭国平, 季 敏, 倪新洋, 马赛赛

(河海大学计算机与信息学院通信与信息系统研究所,江苏南京210098)

1 引言

移动自组织网络(Mobile Ad Hoc Network,MANET)是一种由网络中的一组节点或终端形成的无中心、自组织、自管理的无线网络。与有线网络相比较,MANET对节点能耗及高效的带宽利用率的要求更高,设计高效的MANET路由协议是目前研究的热点问题之一。

目前已经存在多种MANET多播协议,但基于网络编码的多播协议打破了原有基于存储转发协议性能的局限。由文献[1]可知,采用网络编码的多播协议的信道容量可以达到最大流最小割定理的上界。而根据文献[2]可知,采用网络编码的数据分发机制可以大幅度减少数据包交换次数,减少能量开销。但是,与传统的基于存储转发的多播协议相比,基于网络编码的实时多播协议在时延、可靠性以及系统开销等方面性能增益尚不明确。因此采用网络编码技术,在NS2仿真平台上实现了一种基于网络编码的实时多播协议(Network Coding based Realtime Multicast,NCRM)。为了比较NCRM与传统的基于存储转发多播协议的性能,文章选取典型的基于树的MAODV[3](Multicast operation of the Ad hoc On-demand Distance Vector routing protocol)协议以及基于mesh的PUMA[4](Protocol for Unified Multicasting though Announcements)协议作为比较对象,在延时、开销以及可靠性等方面的性能进行仿真比较研究。

2 MAODV、PUMA及网络编码简介

2.1 MAODV协议

MAODV多播路由协议采用广播路由请求-答复机制。当某个节点想加入一个多播组或有数据分组需要发送到多播组时,便发起建立多播路由过程。如图1所示,MAODV的多播树中包括组成员和非组成员(也称树成员)两种,每个多播树有一个组长,主要负责维护多播树。

当某个节点想加入多播组时,它就广播一个带有“J”标志和多播组地址的RREQ消息。具有不小于接收到的RREQ-J消息中的组序列号的多播组成员单播一个RREP-J的应答消息。每一个接收到RREQ的节点都更新自己的路由表,并记录到请求源节点的下一跳信息以及传输RREP到源请求节点的路由信息。经过一段等待时间,发送RREQ消息的节点会在已接收到的RREP消息中选择一条具有最大序列号和最短距离的路径,并向下一跳发送一个MACT消息,激活多播表中选定的下一跳。这样一个更新后的多播树便建立完成。

图1 MAODV的多播路由过程

2.2 PUMA协议

PUMA协议是一种基于Mesh网络的多播路由协议,支持IP多播服务模式,采用由接收节点发起路由的方式,接收端通过使用核心节点的地址加入多播分组。核心节点周期性的发出单一的控制报文(Multicast Announcement,MA)给网络中的节点,节点根据接收到的MA中的信息建立起连接表。通过连接表,网络中的节点和核心节点之间的最短连接路径相连,所有这些最短路径一起构成mesh网格。沿着节点和核心节点间的最短路径发送多播数据。当多播数据到达任意一个mesh成员,mesh成员再将这个数据多播给其他所有mesh成员,并且每个节点都构建一个包ID缓存来验证是否收到重复的MA。

2.3 网络编码简介

网络编码的概念最初是由R.Ahlswed等[1]提出的。从信息论的角度出发,严格证明了在单点对多点的通信网络中,通过节点编码的方式可以使信息传输速率达到网络的最大流量。Li等[5]证明了可以使用线性网络编码方法使多播能够达到最大容量。随后Ho及Medard等[6]提出了随机线性网络编码的概念,文中NCRM的编码过程就采用了线性随机网络编码方式。

线性网络编码就是将一个或多个源节点产生的数据信息包线性的映射到一个有限域内,利用线性关系实现编译码的过程。线性网络编码在算法设计上分为确定性编码和随机编码两种。下面就是随机线性网络编码的实现过程。

源节点S要发送n个原始信息向量X1…Xn给目的节点,源节点发送前随机选择全局编码向量g1…gn将X1…Xn编码成Y=g1X1+g2X2+…gnXn之后再传输,记为(g,Y)。中继节点再随机在有限域内生成局部编码向量h=(h1…hn)对收到的 n个(g,Y)进行线性编码得到一个新的信息包(g′,Y′)再发送给邻节点。当目的节点接收到n个线性无关的(g′,Y′)后,则可根据高斯消元法进行解码。

3 基于网络编码的实时多播协议NCRM

3.1 NCRM协议的报文格式

为了在仿真平台中实现NCRM协议,设计的NCRM报文格式如图2所示。

3.2 NCRM处理流程

与文献[7]的编码方法不同,NCRM是在基于PUMA协议的基础之上,利用随机网络编码算法对要发送的多播信息进行处理。发送数据包时不是直接单个发送,而是在发送端和中间节点对需要发送的一系列数据包采用随机网络编码的方式进行处理,同时在接收节点也采用网络编码的方式来协助解码。这样可显著减少网络中数据的传输次数,从而节省网络带宽并降低节点能耗。

3.2.1 发送端处理

假定发送节点的上层应用持续生成并连续发送数据包。当网络层接收到数据包时,根据数据包的UID将包分组成不同的block,且每BLOCK-SIZE个数据包组成一个block,随之将处理完的数据包存入发送节点的本地缓存中。

图2 NCRM的报文格式

当本地缓存中接收满一个block的数据包时,随即对block进行初始编码操作,生成编码包,同时将生成的随机编码向量存入编码包的encoding vector域中,随编码包一同传输。每次初始编码都将block编码成BLOCKSIZE个编码包发送给邻居节点,以确保包含了下游节点恢复原始数据包所需的足够多的线性无关的编码向量。

3.2.2 中间节点处理

网络中的某一节点收到一个编码包时,检查编码包是否携带新信息,若有则将编码包存入本地缓存,否则丢弃编码包。当中间节点在一定时间内尚未收集到足够多的关于某block的编码包,便利用已收集到的编码包进行二次编码,将编码成的一个编码包广播给邻居节点以期某个邻居节点可以提供节点所需的编码包。若中间节点在一定时间内收到关于某block足够多编码系数线性无关的编码包时,节点也会对block进行二次编码,接着将生成的编码包转发给邻居节点。

3.2.3 接收节点处理

当接收节点收到关于某个block足够多的编码向量线性无关的编码包时,节点可以顺利通过高斯消元法恢复出该block的原始数据包。若在一定时间内接收节点仍然无法收集满足够多的编码向量线性无关的编码包,则利用类似于中间节点的操作,即将已收集到的编码包二次编码生成一个编码包,以向邻居节点请求相关资源。

若接收节点顺利地恢复出某一block的原始数据包,则节点同时对block进行二次编码后将编码包广播给邻居节点,以期向下游节点传递该block或者为邻居节点提供block的冗余编码包。

4 仿真及分析

4.1 仿真环境介绍

4.1.1 NS2软件

NS2[8]是一种源代码公开免费仿真平台,是面向对象的离散时间驱动的网络模拟器,由UC Berkeley研发,能够对现有的网络协议提供很好的支持,提供基本的网络元素支持并用对象实现,易于组合,易于扩展,大大减少了网络模拟研究的工作量。

4.1.2 仿真协议栈

采用的仿真协议栈如图3所示,应用层中使用CBR(恒定比特率)的数据流作为传送的数据源,发送端CBR沿着传输层、网络层、MAC层以及使用Two-ray ground reflection模型的物理层进行传输。而接收端则沿着相反路径将接收的CBR传输到应用层。应用层主要提供面向用户的协通应用服务,而传输层主要是向应用层提供可靠的端到端服务。主要工作是在网络层中实现,网络层需要完成邻居发现、分组路由、拥塞控制以及网络互联等功能。在MAC层采用随机竞争机制IEEE802.11控制节点对无线信道的访问,而物理层负责无线信号的检测,调制解调,信号发送接收等工作。

4.2 仿真参数及性能指标

为了评估NCRM的性能,在NS2仿真平台上搭建了相应的仿真环境,仿真环境的参数设置如表1所示。

图3 仿真协议栈

表1 仿真参数设置

为了能合理的评估NCRM机制的性能仿真,选取3个指标进行性能评估,其定义如下：

分组投递率：即接收节点实际接受收的数据包的个数与希望接被接收节点接收到数据包的个数之比,反映了协议的可靠性,即分组率越高,可靠性越大。分组投递率=接收节点实际接收到数据包/(发送节点发送的数据包个数×接收节点个数)。

路由总开销：即发送的控制包、数据包个数之和与接收到的数据包的个数之比,反映了协议的有效性,即总开销越小,协议的效率越高。总开销=(发送的控制包个数+发送的数据包个数)/实际接收到的数据包的个数。

端到端延时：即数据包从发送节点到接收节点经历的时间,包括路由查找延时,数据包在接口队列的等待延时,传输延时及MAC层的重传延时,反映了路由的有效性。端到端延时=∑(接收到数据包时间-发送数据包时间)/发送数据包的个数。

4.3 仿真结果比较及分析

4.3.1 节点密度变化时性能的比较

为了研究多播组中的总节点密度对协议性能的影响,设置总节点密度分别为41/64、41/49、41/36、41/25、41/16、41/9(个/104m2),此外设置节点的移动速度为15m/s,则关于分组投递率、总开销以及端到端延时的仿真结果比较图如图4所示。

图4 节点密度对性能的影响

首先,如图4(a)所示,随着节点密度的增大,对于每个节点,处在其信号覆盖范围内的邻居节点也随之增多,从而使节点间链路的可靠性得到增强。因此3种协议的分组投递率都逐渐增大,其中NCRM的分组投递率始终保持在90%以上。但NCRM和PUMA的分组投递率相对于MAODV始终保持5%以上的优势。因为基于mesh的PUMA和NCRM在节点增多的情况下,无需建立额外的节点间通信链路。而基于树形结构的MAODV,则需要更多的控制开销来建立、维护其多播树结构。而这些控制开销导致的信道资源占用将影响MAODV的分组投递率。

其次,如图4(b)所示,随着节点密度的增大,3种协议的总开销均呈下降趋势。节点密度的增大,使得NCRM中参与网络编码的节点个数增多,极大的减小了其总开销。MAODV借助于树形结构,其投递分组的效率高于PUMA。此外,由于存在mesh网之内的分组洪泛,PUMA的总开销在3种协议中始终最大。可以看出,为达到同样的分组投递率,NCRM所耗费的信道资源远远小于PUMA。

最后,如图4(c)所示,随着节点密度的增大NCRM的端到端时延呈下降趋势,但相较于PUMA和MAODV而言,NCRM的时延要远大于其他两个协议,是因为NCRM缓存数据包要花费大量的时间,因而NCRM的时延在3种协议中最大。

4.3.2 节点移动速度对性能的影响

为了研究在节点移动速度变化情况下协议的性能,设置节点移动速度分别为0、5、10、15、20、25(m/s)。则关于分组投递率、总开销以及端到端延时的仿真结果比较图如图5所示。

首先,如图5(a)所示,NCRM的包投递率基本维持在94%以上,体现了良好的鲁棒性。是因为随着节点移动速度的增加,虽然链路的不稳定性增大,但由于NCRM中进行网络编码操作的概率将逐渐增大,致使数据包的转发次数将少于PUMA以及MAODV。另外,NCRM中控制消息也很少,因此其在数据包转发过程中出现冲突的概率也较小。最终,当移动速度达到一定值时,NCRM中的包投递率明显优于其他两个协议。

其次,如图5(b)所示,由于PUMA在mesh网中所采用的数据包洪泛机制,其数据包转发次数明显高于NCRM及MAODV,致使PUMA协议的总开销高于MAODV及NCRM。但随着多播组个数的增加,MAODV需要维护多个多播树,其产生的控制开销将急剧增大,导致总开销也随之增大。文献[3]表明,若存在足够多的多播组,MAODV的总开销将会是PUMA以及ODMPR的数百倍,在这种情况下MAODV的包投递率呈逐步下降趋势。

最后,如图5(c)所示,此时NCRM的时延与密度变化时的情况变化不大,都是由于缓存数据包时花费了大量时间,因而其时延上面的性能远不及其他两个协议。综上,由密度变化和移动速度变化的情况可以看出,NCRM在分组投递率和总开销方面都有很大的优势,但由于NCRM机制的不成熟,NCRM在时延方面仍有很大的改进空间。

图5 节点移动速度对性能的影响

5 结束语

采用NS2仿真平台,实现了一种基于网络编码的实时多播协议(NCRM),与传统基于存储转发的协议(PUMA和MAODV)进行了性能比较。通过仿真结果发现与传统的基于存储转发技术的多播路由协议相比较,NCRM协议在可靠性,系统开销方面具有显著优势,但在时延性能方面不如传统的路由协议,由此可以看出,通过合理的参数设置,NCRM可以在以上几个方面取得很好的性能均衡。最后值得指出的是,仅基于单个多播场景对NCRM协议的性能进行了初步的仿真研究,多个多播场景并存的混合发送以及延时控制的问题将是下一步的研究内容。

[1]R Ahlswede,N Cai,S YR Li,et al.Network information flow[J].IEEE Trans.Inform.Theory,2000,46：1204-1216.

[2]黄辰,王芙蓉.基于网络编码的无线自组织网数据分发机制[J].电子学报,2010,38：1853-1857.

[3]E M Royer,C E Perkins.Multicast operation ofthe ad-hoc on-demand distance vector routing protocol[J].IEEE International Conference on Mobile Computingand Networking(MOBICOM),1999：207-218.

[4]Ravindraand J J.Efficient and Robust Multicast Routing in Mobile AdHoc Networks[J].IEEE International Conference on Mobile Ad-hoc andSensor System,2004：304-313.

[5]S YR Li,R W Yeung,N Cai.Liner network coding[J].IEEE Trans.Inform.Theory,2003,49：371-381.

[6]Ho T,Koetter M,Medard M,el at.Toward,A random operation of networks[J].IEEE Trans.Inform.Theory,2004：442-445.

[7]焦进,杨铭熙.基于网络编码的Ad Hoc网PUMA协议的研究[J].中国科技论文在线,2010：1-7.

[8]黄化吉,冯德力.NS网络模拟和协议仿真[M].北京：人民邮电出版社,2010.