一种基于Ad Hoc网络的智能多径路由协议

乔平安　刘运爽　周　敏

(西安邮电大学计算机学院　西安　710121)



一种基于Ad Hoc网络的智能多径路由协议

乔平安刘运爽周敏

(西安邮电大学计算机学院西安710121)

运用无线自组网的多信道多路径路由度量准则(MWCETT),在DSR协议的基础上实现了一种智能多路径路由IMRP(Intelligent Multi-Routing Protocol)协议。该协议通过运用中间节点的路由缓存,减少了路由发现过程的开销。仿真结果表明,IMRP协议提升了网络的吞吐量和可靠性,进而提高了传输的效率。

无线自组网; MWCETT; IMRP; 多径路由

Class NumberTP393

1　引言

移动Ad Hoc网络是由一组兼具主机和路由功能的移动终端组成的多跳临时性自制系统,具有组网迅速和无需基站组织的特点。目前,Ad Hoc网络的路由协议主要分为三种:表驱动(Table-driven)路由协议、按需(On-demond)路由协议和混合式(Hybrid)路由协议[1]。其中,DSR(Dynamic Source Routing)是比较典型的Ad Hoc网络按需路由协议,该协议不需要使用周期性的路由广播和相邻节点探测机制,减少了网络开销,但容易受到节点移动速度和节点暂停时间的影响[2]。MSR(Multi-path Source Routing)协议是在DSR协议的基础上扩展而来的,减少了分组发送时的时延,提高了源节点与目的节点之间的聚合吞吐量,但增加了发包时的处理开销[3～4]。为此,文章基于无线自组网的多信道多路径路由度量准则,在DSR协议和MSR协议的基础上,提出了一种新的Ad Hoc网络智能多径路由协议。

2　多信道传输的路由度量准则

在多信道的无线Ad Hoc网络下,存在路径内、路径之间的信道干扰,为了能够在多信道中表现出较好的网络性能,多信道多路径传输的路径度量准则对于多径路由协议显得尤为重要。

2.1WCETT的路由选择准则

WCETT是一种单路径单信道的路由选择准则,该准则由累计期望传输时间和瓶颈信道传输共同决定单信道路径的性能,即:

(1)

其中ETTi是链路的期望传输时间值,α是一个可调因子,WCETT准则通过瓶颈信道的累积传输时间和所有的链路累积传输时间的加权平均值来反映吞吐量的品质因素,但它仅能反映路径内信道之间的干扰,不能反映多条路径的相同信道之间产生的干扰以及节点间的拥塞情况[5]。

2.2MWCETT路由选择准则

MWCETT路由选择准则是在WCETT路由选择准则的基础上提出的,该准则是根据多条路径合计吞吐量的大小,由单路径时延因子δ、路径干扰因子η、排队时延因子φ三方面的结合而得出的。本文以三条路径为例来分析,但也适用于大于等于四条路径。

2.2.1路径干扰因子η

假设无线路径Lk有Nk个信道,则定义路径在信道j上的累积传输时间Ykj为

(2)

假定一个多路径组合的瓶颈信道传输时间在三条路径上的通信量分配为(x∶y∶z),x分组在路径La上,y分组在路径Lb上以及z分组在Lc上消耗的时间为x*Yaj+y*Ybj+z*Zcj,这样信道j上每个分组消耗的时间均值为

j∈SR(La)∪SR(Lb)∪SR(Lc)

(3)

从式(3)可以看出,通信量分配比例(x∶y∶z)决定了分组在信道上的消耗时间,消耗时间最长的信道为瓶颈信道。用Sabc表示路径组合(La,Lb,Lc)上的信道总数,在通信量分配比例为(x∶y∶z)的情况下,多路径信道干扰因子η为

(4)

2.2.2路径延时因子δ

对于有nk个信道有n跳的路径Lk,其WCETT为

(5)

由式(5)知在一条路径上的WCETT值越小,预期的吞吐量越高,为了反映多条路径上的分组的累积传输时间,定义路径延时因子δ(x,y,z)为多条路径上WCETT上的加权平均值,如下所示:

(6)

2.2.3排队时延因子φ

假定Li为节点i上等待队列的平均长度,vi为该节点发送数据包的速率,由liang ma提出的在路径Lp中节点的负载度[6]可表示为

(7)

La,Lb,Lc为三条无线自组网中的路径,那么定义该路径中节点排空该队列的累积时间为

(8)

由以上可以看出,多路径间的η,δ和φ取决于负载分配比率x∶y∶z,单一的η,δ和φ不能全面的反映路径的变化,只有综合考虑信道间的干扰,端到端的延迟以及排队时延的特性,才能全面反映路径的变化。于是,由η,δ以及φ组合的多信道多路径路由选择准则(MWCETT)便应运而生了,即

MWCETT=β*(α*η+(1-α)*δ)+(1-β)*φ

(9)

MWCETT解决了端到端延迟,信道干扰以及排队时延的问题。MWCETT值越低,路径累积吞吐量就越高。α,β之间的不同取值尝试着在信道干扰因子、端到端延迟因子以及排队时延因子之间获得均衡[7]。

3　IMRP协议

MSR协议作为多径路由协议中较成功的路由协议,通过主动探测的机制来感知路由的拥塞情况,根据路径的拥塞状况,将数据流量分摊到预先选出的若干条路径上进行传输。MSR使用多条路径可以提高网络的性能,但是多径路由协议维护辅助路径需要更大的路由表空间和计算开销。针对该问题,文章提出了一种全新的路由协议,即智能多径路由协议IMRP。

3.1IMRP路由发现机制

IMRP协议的路由发现机制为:当启动一次路由发现机制后,源节点首先使用洪泛的方式发送路由请求分组RREQ,通过中间节点的层层转发,目的节点收到RREQ分组后根据独立路径算法选择出若干组相互独立的路由,以每三条独立路径为一组将信息封装到RREP分组中,将分组沿着其中的一条路由回溯给源节点,源节点收到路由应答分组后,利用源节点的独立路径算法选择合适的路由[8]。

3.2IMRP协议独立路径算法

为了节省计算的开销,IMRP协议采用三条路径进行数据的传输,目的节点执行IMRP协议的独立路径算法,当第一个RREQ到达目的节点时,将启动该协议的独立路径算法,该算法的具体流程如下:

1) 初始化程序,设置路由的最大跳数N,最大路径数3,发送RREP个数最大值L,路径数n=0,倒计时T。

2) 记录RREQ1中信息中所包含的路径,n=1。

3) 判断倒计时是否到达T,如果时间到达,则跳转到第6)步。

4) 准备接收下一个路由请求分组(RREQi)。

5) 将路由跳数与N进行比较,若小于N则记录该分组的路径;若大于N,直接丢弃该分组。跳转到第3)步。

6) 根据所收到的RREQ分组中所包含的路径构造有向图G(V,E),并删除有向图中RREQ1路径中源节点与目的节点之间的中间节点。

7) 若RREQi中不包含RREQi-1中的节点,则记录RREQi中的路径,n=n+1。

8) 若n=3时,将三个RREQ分组中所代表的路由信息写入到RREP分组中,RREP个数加1,并将分组沿RREQi分组中所代表的路径回溯给源节点。此时重置n=0,并删除有向图中RREQi中所指路径的中间节点;若n<3,执行第7)步。

9) 比较RREP个数与L的大小,若大于,结束程序;若小于等于,继续执行第7)步。

由该算法可以看出,目的节点每选出三条独立路由才回复给源节点一个路由应答分组。通过降低路由应答包的数目理论上降低了路由控制信息的开销。

3.3IMRP协议源节点的路由选择算法

源节点的路由选择算法具体流程如下所示:

1) 源节点收到目的节点发送回来的第一个RREP分组后,取出其中的route1、route2、route3中各条路由的链路状态信息,根据这些信息计算出δ,η,φ值,根据这些值给每条路径分配权重,进而计算出该组多路径的MWCETT1的值,源节点就把该组多路径作为主路径按照所分配的权重将数据包传送出去。

2) 如果RREP2到达源节点,根据路径的状态信息计算出MWCETT2,并比较MWCETT2和MWCETT1值的大小,较小的那组所代表的路由对为主路由,并使用该组路由发送数据,另外一组作为备份路由。

3) 当源节点收到RREPi分组后,源节点取出含有路径链路状态的信息,在计算出它的MWECTTi后,分别于主路由和备份路由的MCWETT值进行比较:若MWCETTiMWCETT(备份),则直接丢弃该路由分组;若MCETT(主)

3.4IMRP协议路由维护机制

在进行数据包的传送时,中间节点发现到达下一跳节点的链路因中断而无法使用时,中间节点会将收集来的链路断裂信息组成路由错误分组(RRER分组)沿着原路回溯给源节点,源节点收到RRER分组后,会在路由缓存中将失效的路由信息进行删除,接着在自身的路由缓存中,查找是否有可用的备份路由对,如果有则替换为主路由进行数据传输;如果缓存中路由无法使用,则重新启动一次路由发现机制。

4　仿真结果与分析

本文采用OPNET对IMRP路由协议的性能进行验证[9]。OPNET仿真平台是最具有代表性的一款网络仿真工具,可进行无线局域网(Wireless LAN)和多跳Ad Hoc网络的仿真,无线模块以Mobile Node为基本核心,支持多跳网络的模拟[10]。

定义仿真场景设置[11]如下:

1) 仿真区域:2000m*2000m的矩形区域;

2) 仿真节点:100个随机分布的节点组成移动自组网,节点的运动符合Random Waypoint模型。仿真中所使用的运动场景文件的特征由停顿时间(Pause time)参数来界定;

3) 节点传输范围:设定每个节点的传输功率范围为半径200m的圆形区域;

4) 跳数限制:路由跳数过大的话,路径的传输能力会很差,因此,在仿真之中对最大跳数作出限制,假设最大跳数为8跳;

5) 信道传输速率:2Mbps;

6) 发送数据包大小:512bit;

7) 在IMRP协议中,综合考虑在进行数据传输时存在的端到端延迟、使用多信道传输时存在的信道干扰以及传送数据存在的排队迟延问题,在这里设置参数η=0.5、δ=0.5、φ=0.5。

4.1网络的吞吐量

在该组实验中设置节点的停顿时间分别为0s、50s、100s、150s、200s、250s、300ss,0s即为节点到达目标节点后不做任何的停留,继续向其它目标节点运动,设置数据源的数目分别为20个、30个,仿真结果如图1、2所示。

图1　三种路由协议吞吐量间的比较(20个数据源)

图2　三种路由协议吞吐量间的比较(30个数据源)

4.2路由可靠性

在该组实验中,无线网络的数据源设置为20个,节点的停顿时间为0s、150s,仿真结果如图3、4所示。

图3　路由可靠性(停顿时间为0s)

图4　路由可靠性(停顿时间为150s)

4.3仿真结果

由图1和图2可知,DSR、MSR和IMRP三种协议随停顿时间的加大各自的吞吐量变化趋势基本保持一致,但是综合来看,IMRP协议在通信数据量加大时,由于有备份的路由对进行数据传输,所以也就保证了IMRP协议在吞吐量方面要优于DSR协议和MSR协议;在可靠性方面,MSR协议、IMRP协议都要比DSR协议有所提高,并且IMRP协议相对于MSR协议有大约10%以上的提升,这是由于MSR协议使用主动探测机制来获取多条拥塞小的多条路由进行数据传输,并且定时的进行路由信息的更新,这种机制保证了路由可靠性较高;并且,IMRP协议与MSR协议相比,其源节点使用了自己的路径选择算法,使得该节点的缓存中有备份路由对的存在,即便是主路由对失效时,还有备份路由对接着对数据进行传输,这种路由缓存机制在理论上也决定了其在数据传输时有较高的路由可靠性。

5　结语

本文针对MSR协议独立路径数目过多、路由应答开销过大的缺陷,提出了一种智能多信道多路由协议IMRP。在该协议的路由发现过程中,使用MWCETT准则,选择多条相互独立的路径(文中为三条路径)作为主路由对,进行数据的传输,另外选择多条相互独立的路径作为备份路由对保存在路由缓存中,当主路由失效时,将采用备份路由对进行数据的传输,这样从理论上提高网络的吞吐量和可靠性。最后通过仿真实验,验证了IMRP协议的可行性。

[1] 李悦,蔡振.Ad Hoc网络的研究现状与发展[J].软件导刊,2012,11(2):109-111.

LI Yue, CAI Zhen. Current research and development of Ad Hoc Networks[J]. Software GUIDE,2012,11(2):109-111.

[2] 郭鹏远,李洪烈,王公浩,等.移动Ad Hoc网络按需路由协议的研究[J].信息技术,2015(2):130-133.

GUO Pengyuan, LI Gonglie, WANG Gonghao, et al. Research on demand routing protocol of mobile Ad Hoc network[J]. Information Technology,2015(2):130-133.

[3] Priyanka Goyal, Sahil Batra. A Literature Review of Security Attack in Mobile Ad hoc Networks[J]. International Journal of Computer Applications,2010,6(12):11-15.

[4] 田野,盛敏,李建东,等.一维Ad Hoc网络二连通性的研究[J].电子学报,2008,36(4):715-719.

TIAN Ye, SHENG Min, LI Jiandong, et al. Research on the two connectivity of one dimensional Ad Hoc network[J]. Electronic Journal,2008,36(4):715-719.

[5] 孙志.基于WCETT的多信道WMN路由度量的研究[J].通信技术,2013,6(46):82-84.

SUN Zhi. Research on multi channel WMN routing metrics based on WCETT[J]. Communications Technology,2013,6(46):82-84.

[6] Hong Li, Huang Tingpei, Zou Weixia, et al. Research of AODV routing protocol based on link availability prediction[J]. Journal on Communications,2008,29(7):118-123.

[7] 乔平安,邵凯,刘运爽.基于无线Ad Hoc的多路径多信道路由度量准则[J].电子科技,2015,28(8):60-62.

QIAO Ping’an, SHAO Kai, LIU Yunshuang. Multi path multi channel routing metric based on wireless Ad Hoc[J]. Electronic Science and Technology,2015,28(8):60-62.

[8] 陈博.Ad Hoc多径源路由协议的研究与改进[D].合肥:合肥工业大学,2008.

CHEN Bo. Research and improvement of Ad Hoc multipath source routing protocol[D]. Hefei: Hefei University of Technology,2008.

[9] 周杰.Ad Hoc网络中三种典型路由协议的仿真分析与比较[J].大众科技,2010,125(1):57-58.

ZHOU Jie. Simulation analysis and comparison of three typical routing protocols in Ad Hoc networks[J]. Popular Science and Technology,2010,125(1):57-58.

[10] 刘敏,高明霞,陆思羽,等.基于OPNET的地域通信网网络仿真研究[J].电子设计工程,2012,20(4):120-124.

LIU Min, GAO Mingxia, LU Siyu, et al. Research on network simulation of regional communication network based on OPNET.

[11] Feng W, Zhang L, Elmirghani J. Energy saving geographic routing in Ad Hoc wireless networks[J]. IET Communications,2012,6(1):116-124.

An Intelligent Multi-path Routing Protocol Based on Ad Hoc Network

QIAO Ping’anLIU YunshuangZHOU Min

(School of Computer, Xi’an University of Posts & Telecommunications, Xi’an710121)

Basing on DSR, this paper implemented an intelligent multi-path routing IMRP(Intelligent Multi-Routing Protocol) protocol, which used the multi-channel wireless Ad Hoc multi-path routing metric criteria(MWCETT). The agreement used an intermediate node routing cache, thereby it reduced the overhead of route discovery process. Simulation results showed that, IMRP agreement can enhance the throughput and reliability of the network, and increase the efficiency of the transmission.

Ad Hoc, MWCETT, IMRP, multi-path routing

2016年2月7日,

2016年3月30日

乔平安,男,副教授,研究方向:计算机应用技术。刘运爽,女,硕士研究生,研究方向:通信软件开发与测试。周敏,女,硕士研究生,研究方向:通信软件开发与测试。

TP393

10.3969/j.issn.1672-9722.2016.08.029