基于MQAAR的移动自组织网络路由方案*

周芸韬

(云南师范大学 商学院，云南 昆明 650106)



基于MQAAR的移动自组织网络路由方案*

周芸韬*

(云南师范大学 商学院，云南 昆明 650106)

对于目前移动自组网(MANET)中大多数路由方案没有考虑中间节点处的排队延迟和竞争延迟，导致较大端到端延时的问题，提出一种基于移动性和Qos感知的任播路由方案(MQAAR).MQAAR使用改进的动态源路由(DSR)，设计节点稳定性模型、Qos拥塞模型，通过任播方式，优化MANET中路由发现和路由维护方法.仿真结果表明，相比ACAP、DSR和ALBRS，MQAAR在控制开销、数据包传输率和平均端到端延迟方面具有更高的性能.可以更好地应用于MANET中，具有一定的实际应用价值.

移动自组织网络；MQAAR；任播；稳定模型；拥塞模型；链路失效模型

移动自组网(Mobile Ad hoc Network, MANET)[1]已广泛应用于需要信息共享的场合，如矿井、紧急救灾、探险、会议室等[2-3].MANET中最重要的问题之一是找到一条有效且可靠的任播路由[4-5].当前，大多数任播路由方案通过构造任播信道,沿着最短路径发送数据包，如自适应神经模糊推理系统(Adaptive Neuro-Fuzzy Inference System, ANFIS)[6]和基于群蚁算法的Qos任播路由[7]等.这类路由方案中路由选择涉及的移动节点少，能节约宽带开销，但不能均匀分布路由负载，网络流量主要集中在中间节点上，容易造成中间节点网络拥塞和丢包率较高等问题[8].[9]提出了基于阈值端对端算法，使用链路失效、往返时间和重传时间预测等方法，来减少MANET中的链路失效损耗.[10]基于备份拓扑方法，考虑流量矩阵和拓扑，将高负载链路上的流量划分到其他链路.上述方案虽然采取了优化措施，但仍然集中于跳数最少、服务器负载低的自由组路由协议，不考虑中间节点处的排队延迟和竞争延迟.与一些备用路径相比，最小跳路径可能会引发更大的端对端通信延时.因此，本文提出在MANET中设计一种基于移动性和Qos感知的任播路由方案(Mobility and Qos Aware Anycast Routing, MQAAR).该方案使用改进的动态源路由(Dynamic Source Routing, DSR)[11]，集成节点稳定性模型和拥塞模型，通过任播方式优化了MANET中路由发现和路由维护方法.

1 提出的路由方案

DSR是一种按需反应式路由协议，它在低速移动环境中运作较好，但是随着节点移动速度的增大，其性能迅速下降[12].提出的MQAAR在DSR的基础上嵌入三种模型，对其进行改进.

1.1 节点稳定性模型

(1)

(2)

仿真表明，α和β的值在0.55到0.8之间，能获得稳定性好的节点.MQAAR通过使用该模型提取高稳定性的中间节点，调整基于稳定节点的路由网络拓扑，降低链路失效的概率.

1.2 Qos拥塞模型

为处理MANET中的拥塞问题，设计基于信道负载和链路缓冲占有量的拥塞模型.基于信道负载的变化率TL测量网络中的拥塞，TL=tbusy/(tbusy+tidle)，其中，tbusy和tidle为给定时间窗中信道的繁忙时间和空闲时间.

节点需均衡平均缓冲水平以避免拥塞和频繁链路失效.链路缓冲占有量LB表示为式(7)，QS为中间节点处给定时间窗口中的最大队列大小，QC表示链路队列占有率，

LB=QC/QS.(7)

1.3 路由建立

表1 中间节点I3的链路数据基础表Tab.1 Link data base table for intermediate node I3

1.4 路由发现过程

路由发现过程包括请求阶段和应答阶段.请求阶段采用前文提出的节点稳定性模型和Qos拥塞模型确定稳定且非拥塞的节点担任中间节点，创建从客户端到服务器的任播路由.其操作过程如下：(1)客户端组装RR数据包.(2) RR数据包通过稳定且拥塞的邻近节点进行转发.(3)若该节点之前已接收过RR数据包(通过序列号和客户端地址匹配)，则丢弃本次RR数据包，并停止RR数据包转发.(4)若RR数据包不是重复包，且检测到RIC中路由可用，则组装成RP数据包，并启动到客户端的应答传播.(5)若RIC中路由不可用，则通过更新邻近节点的路由参数(路由记录、稳定值、拥塞因子、下一跳地址等)，执行步骤2转发RR数据包.(6)执行步骤3到步骤5直至到达任播服务器.(7)若在设定的跳数内没有到达服务器，则发送RE数据包到客户端.

当RP数据包到达服务器，则启动应答过程：(1)服务器计算收到的RR数据包中的RET.(2)服务器在多个路径中筛选RET高的路径.(3)服务器为RET最高的RR数据包生成RP数据包，并通过更新RIC转发RP数据包到相邻节点地址.(4)收到RP数据包的中间节点根据RP数据包内容更新RIC，并转发到邻近节点.若链路失败，则发送PE数据包到服务器，同时停止RP数据包转发.(5)执行步骤3直至到达客户端.(6)若未发现客户端，则发送PE数据包到服务器.(7)若RP数据包到达客户端，则客户端基于最高RET的路径确定任播服务器.(8)对于所选的服务器，选择跳跃较少的路径，并预留通往所选服务器的其他路径作为备用路径.

1.5 路由维护过程

2 仿真实验

将MQAAR与自适应拥塞感知协议(Adaptive Congestion Aware Protocol, ACAP)[8]、DSR和ALBRS的性能进行对比分析，分别在控制开销、数据包传输率(Packet Delivery Ratio, PDR)和平均端到端延迟方面进行比较.使用C++编程语言建立3种模型的仿真环境：信道模型，网络模型、移动模型.设置仿真参数：网络区域选用200 m*200 m平格栅区；节点数500；客户端数量1～20；服务器的系数情况数1～20；节点布置形式为随机；信道容量2 Mbps；路由传输范围250 m；载波监听范围500 m；数据包大小为1 024 B；最小带宽取60 Kbps；最大延迟0.1 s；仿真时间600 s；权重因子α和β取0.55～0.8之间随机数；Nsf阈值取0.55～0.85之间随机数；CF阈值取0.05～0.4之间随机数.表2和表3分别表示相对于不同数量的服务器和客户端控制开销的变化规律.相比于ACAP、DSR和ALBRS，MQAAR的控制开销有所减少.原因在于随着服务器数的增加，客户端连接到任意服务器的概率也增大，并且MQAAR只使用满足节点稳定性、非拥塞的路径，因此，链路失败和节点失效的情况较少，相应控制开销也会降低.同理，如表3所示，当客户端数增加时，MQAAR的控制开销更小.

表2 服务器数变化时的控制开销Tab.2 Controls overhead when the number of servers is changed

表3 客户端数变化时的控制开销Tab.3 Controls overhead when the number of clients is changed

表4、表5分别为仿真不同节点数和节点移动性条件下各方案的PDR.如表4所示，各方案的PDR均随着节点数的增加而增大，而MQAAR的PDR明显优于ACAP、DSR和ALBRS.

表4 节点数变化时的PDRTab.4 PDR of the change of the number of nodes

节点移动速度对PDR的影响如表5所示，随着节点移动速度的增加，ACAP、DSR和ALBRS链路失败的概率都增大，链路将启动新路径发现，引起数据包丢失，从而导致PDR降低.而MQAAR基于三种模式重建传输路径，无论是节点失效还是节点移动速度过快，都会最大程度转发数据包.因此，MQAAR比其他方案具有更高的PDR.

表6表示节点移动速度和节点数变化对各方案端到端延迟的影响.随着节点移动速度的增加，端到端延迟也增加.相比于ACAP、DSR和ALBRS，MQAAR中的延迟较低.

表6 移动速度变化时的平均端到端延迟Tab.6 Average end to end delay in moving speed change

3 结 论

对于目前MANET中的路由方案没有考虑中间节点处的排队延迟和竞争延迟，从而产生较大的端到端延时的问题，本文提出MQAAR路由方案.MQAAR是在DSR的基础上嵌入两种模型，即识别稳定节点的稳定模型和感知网络拥塞的Qos拥塞模型，并采取任播的方式，综合考虑了稳定性、网络拥塞、控制开销、负载平衡和Qos的因素.仿真结果表明：相比ACAP、DSR和ALBRS，MQAAR在控制开销、数据包传输率和平均端到端延迟方面具有更高的性能，可以更好地应用于需要信息共享的场合，具有一定的实际应用价值.

[1] 符琦. 一种具有业务感知的多路径Qos路由策略[J]. 计算机学报, 2014, 37(10):2153-2164.

[2] YANG H S, SUN J H. A study on stable data transmission using hierarchical share group in mobile Ad Hoc network[J]. Wireless Personal Communications, 2016, 86(1): 333-349.

[3] 陈立, 朱志勇, 姚丹霖. 基于蚁群优化算法的Qos多播路由算法改进及实证[J]. 湘潭大学自然科学学报, 2009, 31(2): 155-159.

[4] MOHANAPRIYA M, KRISHNAMURTHI I. Modified DSR protocol for detection and removal of selective black hole attack in MANET[J]. Computers & Electrical Engineering, 2014, 40(2): 530-538.

[5] 王多华, 刘乃安, 刘明宇. 任播路由协议在移动Ad hoc网络中的应用研究[J]. 西安邮电大学学报, 2004, 9(1): 6-10.

[6] SHOKRI B J, RAMAZI H, ARDEJANI F D. Prediction ofpyrite oxidation in a coal washing waste pile applying artificial neural networks (ANNs) and adaptive Neuro-fuzzy inference systems (ANFIS)[J]. Mine Water & the Environment, 2014, 33(2): 146-156.

[7] 王莘. 基于克隆选择的Qos组播路由优化[J]. 电子设计工程, 2014, 22(3): 83-84.

[8] ZHANG J, REN F, HUANG T, et al. Congestion-aware adaptive forwarding in datacenter networks [J]. Computer Communications, 2015, 62(3): 34-46.

[9] 李泽平, 杨旋, 鲍序. 对等网端到端多路径选择建模及算法研究[J]. 计算机应用研究, 2016, 33(4):1191-1198.

[10] TEMBO S, YUKIMATSU K I, TAKAHASHI R, et al. A new backup topology design method for congestion avoidance in IP fast reroute[J]. International Journal of Networks & Communications, 2012, 2(5): 123-131.

[11] 杨建辉, 吴聪. PSO 结合 SA 优化算法的无线传感器网络路由协议[J]. 湘潭大学自然科学学报, 2015, 37(4): 98-104.

[12] MANDHARE V V, THOOL R C. Improving Qos of mobile Ad-hoc network using cache update scheme in dynamic source routing protocol[J]. Procedia Computer Science, 2016, 79(3): 692-699.

责任编辑：龙顺潮

A Routing Scheme for Mobile Ad Hoc Network Based on MQAAR

ZHOUYun-tao*

(Business School, Yunnan Normal University, Kunming 650106 China)

Aiming at the problems of queuing delay and contention delay at the intermediate node are not taken into account for route selection in most routing schemes with a higher end-to-end delay in Mobile Ad hoc Network (MANET). A Mobility and Qos Aware Anycast Routing (MQAAR) scheme is proposed. The improved Dynamic Source Routing (DSR), node stability model and Qos congestion model are used in MQAAR to optimize route discovery and route maintenance in the mode of anycast. The simulation results indicate that compared to ACAP, DSR, and ALBRS, MQAAR has higher performance in control overhead, packet delivery ratio and average end-to-end delay. It can be better applied in MANET, which has some practical value.

MANET; MQAAR; anycast; stability model; congestion model; link expiration time model

2016-02-21

云南省教育厅课题(2015Y518)

周芸韬(1981-)，女，湖南 澧县人，讲师. E-mail:zhouyuntaoynnu@126.com

TP393

A

1000-5900(2016)03-0069-05