基于MQAAR的移動(dòng)自組織網(wǎng)絡(luò)路由方案*

周蕓韜

(云南師范大學(xué) 商學(xué)院，云南 昆明 650106)

?

基于MQAAR的移動(dòng)自組織網(wǎng)絡(luò)路由方案*

周蕓韜*

(云南師范大學(xué) 商學(xué)院，云南 昆明 650106)

對(duì)于目前移動(dòng)自組網(wǎng)(MANET)中大多數(shù)路由方案沒有考慮中間節(jié)點(diǎn)處的排隊(duì)延遲和競爭延遲，導(dǎo)致較大端到端延時(shí)的問題，提出一種基于移動(dòng)性和Qos感知的任播路由方案(MQAAR).MQAAR使用改進(jìn)的動(dòng)態(tài)源路由(DSR)，設(shè)計(jì)節(jié)點(diǎn)穩(wěn)定性模型、Qos擁塞模型，通過任播方式，優(yōu)化MANET中路由發(fā)現(xiàn)和路由維護(hù)方法.仿真結(jié)果表明，相比ACAP、DSR和ALBRS，MQAAR在控制開銷、數(shù)據(jù)包傳輸率和平均端到端延遲方面具有更高的性能.可以更好地應(yīng)用于MANET中，具有一定的實(shí)際應(yīng)用價(jià)值.

移動(dòng)自組織網(wǎng)絡(luò)；MQAAR；任播；穩(wěn)定模型；擁塞模型；鏈路失效模型

移動(dòng)自組網(wǎng)(Mobile Ad hoc Network, MANET)[1]已廣泛應(yīng)用于需要信息共享的場合，如礦井、緊急救災(zāi)、探險(xiǎn)、會(huì)議室等[2-3].MANET中最重要的問題之一是找到一條有效且可靠的任播路由[4-5].當(dāng)前，大多數(shù)任播路由方案通過構(gòu)造任播信道,沿著最短路徑發(fā)送數(shù)據(jù)包，如自適應(yīng)神經(jīng)模糊推理系統(tǒng)(Adaptive Neuro-Fuzzy Inference System, ANFIS)[6]和基于群蟻算法的Qos任播路由[7]等.這類路由方案中路由選擇涉及的移動(dòng)節(jié)點(diǎn)少，能節(jié)約寬帶開銷，但不能均勻分布路由負(fù)載，網(wǎng)絡(luò)流量主要集中在中間節(jié)點(diǎn)上，容易造成中間節(jié)點(diǎn)網(wǎng)絡(luò)擁塞和丟包率較高等問題[8].[9]提出了基于閾值端對(duì)端算法，使用鏈路失效、往返時(shí)間和重傳時(shí)間預(yù)測等方法，來減少M(fèi)ANET中的鏈路失效損耗.[10]基于備份拓?fù)浞椒ǎ紤]流量矩陣和拓?fù)?，將高?fù)載鏈路上的流量劃分到其他鏈路.上述方案雖然采取了優(yōu)化措施，但仍然集中于跳數(shù)最少、服務(wù)器負(fù)載低的自由組路由協(xié)議，不考慮中間節(jié)點(diǎn)處的排隊(duì)延遲和競爭延遲.與一些備用路徑相比，最小跳路徑可能會(huì)引發(fā)更大的端對(duì)端通信延時(shí).因此，本文提出在MANET中設(shè)計(jì)一種基于移動(dòng)性和Qos感知的任播路由方案(Mobility and Qos Aware Anycast Routing, MQAAR).該方案使用改進(jìn)的動(dòng)態(tài)源路由(Dynamic Source Routing, DSR)[11]，集成節(jié)點(diǎn)穩(wěn)定性模型和擁塞模型，通過任播方式優(yōu)化了MANET中路由發(fā)現(xiàn)和路由維護(hù)方法.

1 提出的路由方案

DSR是一種按需反應(yīng)式路由協(xié)議，它在低速移動(dòng)環(huán)境中運(yùn)作較好，但是隨著節(jié)點(diǎn)移動(dòng)速度的增大，其性能迅速下降[12].提出的MQAAR在DSR的基礎(chǔ)上嵌入三種模型，對(duì)其進(jìn)行改進(jìn).

1.1 節(jié)點(diǎn)穩(wěn)定性模型

(1)

(2)

仿真表明，α和β的值在0.55到0.8之間，能獲得穩(wěn)定性好的節(jié)點(diǎn).MQAAR通過使用該模型提取高穩(wěn)定性的中間節(jié)點(diǎn)，調(diào)整基于穩(wěn)定節(jié)點(diǎn)的路由網(wǎng)絡(luò)拓?fù)洌档玩溌肥У母怕?

1.2 Qos擁塞模型

為處理MANET中的擁塞問題，設(shè)計(jì)基于信道負(fù)載和鏈路緩沖占有量的擁塞模型.基于信道負(fù)載的變化率TL測量網(wǎng)絡(luò)中的擁塞，TL=tbusy/(tbusy+tidle)，其中，tbusy和tidle為給定時(shí)間窗中信道的繁忙時(shí)間和空閑時(shí)間.

節(jié)點(diǎn)需均衡平均緩沖水平以避免擁塞和頻繁鏈路失效.鏈路緩沖占有量LB表示為式(7)，QS為中間節(jié)點(diǎn)處給定時(shí)間窗口中的最大隊(duì)列大小，QC表示鏈路隊(duì)列占有率，

LB=QC/QS.(7)

1.3 路由建立

表1 中間節(jié)點(diǎn)I3的鏈路數(shù)據(jù)基礎(chǔ)表Tab.1 Link data base table for intermediate node I3

1.4 路由發(fā)現(xiàn)過程

路由發(fā)現(xiàn)過程包括請(qǐng)求階段和應(yīng)答階段.請(qǐng)求階段采用前文提出的節(jié)點(diǎn)穩(wěn)定性模型和Qos擁塞模型確定穩(wěn)定且非擁塞的節(jié)點(diǎn)擔(dān)任中間節(jié)點(diǎn)，創(chuàng)建從客戶端到服務(wù)器的任播路由.其操作過程如下：(1)客戶端組裝RR數(shù)據(jù)包.(2) RR數(shù)據(jù)包通過穩(wěn)定且擁塞的鄰近節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā).(3)若該節(jié)點(diǎn)之前已接收過RR數(shù)據(jù)包(通過序列號(hào)和客戶端地址匹配)，則丟棄本次RR數(shù)據(jù)包，并停止RR數(shù)據(jù)包轉(zhuǎn)發(fā).(4)若RR數(shù)據(jù)包不是重復(fù)包，且檢測到RIC中路由可用，則組裝成RP數(shù)據(jù)包，并啟動(dòng)到客戶端的應(yīng)答傳播.(5)若RIC中路由不可用，則通過更新鄰近節(jié)點(diǎn)的路由參數(shù)(路由記錄、穩(wěn)定值、擁塞因子、下一跳地址等)，執(zhí)行步驟2轉(zhuǎn)發(fā)RR數(shù)據(jù)包.(6)執(zhí)行步驟3到步驟5直至到達(dá)任播服務(wù)器.(7)若在設(shè)定的跳數(shù)內(nèi)沒有到達(dá)服務(wù)器，則發(fā)送RE數(shù)據(jù)包到客戶端.

當(dāng)RP數(shù)據(jù)包到達(dá)服務(wù)器，則啟動(dòng)應(yīng)答過程：(1)服務(wù)器計(jì)算收到的RR數(shù)據(jù)包中的RET.(2)服務(wù)器在多個(gè)路徑中篩選RET高的路徑.(3)服務(wù)器為RET最高的RR數(shù)據(jù)包生成RP數(shù)據(jù)包，并通過更新RIC轉(zhuǎn)發(fā)RP數(shù)據(jù)包到相鄰節(jié)點(diǎn)地址.(4)收到RP數(shù)據(jù)包的中間節(jié)點(diǎn)根據(jù)RP數(shù)據(jù)包內(nèi)容更新RIC，并轉(zhuǎn)發(fā)到鄰近節(jié)點(diǎn).若鏈路失敗，則發(fā)送PE數(shù)據(jù)包到服務(wù)器，同時(shí)停止RP數(shù)據(jù)包轉(zhuǎn)發(fā).(5)執(zhí)行步驟3直至到達(dá)客戶端.(6)若未發(fā)現(xiàn)客戶端，則發(fā)送PE數(shù)據(jù)包到服務(wù)器.(7)若RP數(shù)據(jù)包到達(dá)客戶端，則客戶端基于最高RET的路徑確定任播服務(wù)器.(8)對(duì)于所選的服務(wù)器，選擇跳躍較少的路徑，并預(yù)留通往所選服務(wù)器的其他路徑作為備用路徑.

1.5 路由維護(hù)過程

2 仿真實(shí)驗(yàn)

將MQAAR與自適應(yīng)擁塞感知協(xié)議(Adaptive Congestion Aware Protocol, ACAP)[8]、DSR和ALBRS的性能進(jìn)行對(duì)比分析，分別在控制開銷、數(shù)據(jù)包傳輸率(Packet Delivery Ratio, PDR)和平均端到端延遲方面進(jìn)行比較.使用C++編程語言建立3種模型的仿真環(huán)境：信道模型，網(wǎng)絡(luò)模型、移動(dòng)模型.設(shè)置仿真參數(shù)：網(wǎng)絡(luò)區(qū)域選用200 m*200 m平格柵區(qū)；節(jié)點(diǎn)數(shù)500；客戶端數(shù)量1～20；服務(wù)器的系數(shù)情況數(shù)1～20；節(jié)點(diǎn)布置形式為隨機(jī)；信道容量2 Mbps；路由傳輸范圍250 m；載波監(jiān)聽范圍500 m；數(shù)據(jù)包大小為1 024 B；最小帶寬取60 Kbps；最大延遲0.1 s；仿真時(shí)間600 s；權(quán)重因子α和β取0.55～0.8之間隨機(jī)數(shù)；Nsf閾值取0.55～0.85之間隨機(jī)數(shù)；CF閾值取0.05～0.4之間隨機(jī)數(shù).表2和表3分別表示相對(duì)于不同數(shù)量的服務(wù)器和客戶端控制開銷的變化規(guī)律.相比于ACAP、DSR和ALBRS，MQAAR的控制開銷有所減少.原因在于隨著服務(wù)器數(shù)的增加，客戶端連接到任意服務(wù)器的概率也增大，并且MQAAR只使用滿足節(jié)點(diǎn)穩(wěn)定性、非擁塞的路徑，因此，鏈路失敗和節(jié)點(diǎn)失效的情況較少，相應(yīng)控制開銷也會(huì)降低.同理，如表3所示，當(dāng)客戶端數(shù)增加時(shí)，MQAAR的控制開銷更小.

表2 服務(wù)器數(shù)變化時(shí)的控制開銷Tab.2 Controls overhead when the number of servers is changed

表3 客戶端數(shù)變化時(shí)的控制開銷Tab.3 Controls overhead when the number of clients is changed

表4、表5分別為仿真不同節(jié)點(diǎn)數(shù)和節(jié)點(diǎn)移動(dòng)性條件下各方案的PDR.如表4所示，各方案的PDR均隨著節(jié)點(diǎn)數(shù)的增加而增大，而MQAAR的PDR明顯優(yōu)于ACAP、DSR和ALBRS.

表4 節(jié)點(diǎn)數(shù)變化時(shí)的PDRTab.4 PDR of the change of the number of nodes

節(jié)點(diǎn)移動(dòng)速度對(duì)PDR的影響如表5所示，隨著節(jié)點(diǎn)移動(dòng)速度的增加，ACAP、DSR和ALBRS鏈路失敗的概率都增大，鏈路將啟動(dòng)新路徑發(fā)現(xiàn)，引起數(shù)據(jù)包丟失，從而導(dǎo)致PDR降低.而MQAAR基于三種模式重建傳輸路徑，無論是節(jié)點(diǎn)失效還是節(jié)點(diǎn)移動(dòng)速度過快，都會(huì)最大程度轉(zhuǎn)發(fā)數(shù)據(jù)包.因此，MQAAR比其他方案具有更高的PDR.

表6表示節(jié)點(diǎn)移動(dòng)速度和節(jié)點(diǎn)數(shù)變化對(duì)各方案端到端延遲的影響.隨著節(jié)點(diǎn)移動(dòng)速度的增加，端到端延遲也增加.相比于ACAP、DSR和ALBRS，MQAAR中的延遲較低.

表6 移動(dòng)速度變化時(shí)的平均端到端延遲Tab.6 Average end to end delay in moving speed change

3 結(jié) 論

對(duì)于目前MANET中的路由方案沒有考慮中間節(jié)點(diǎn)處的排隊(duì)延遲和競爭延遲，從而產(chǎn)生較大的端到端延時(shí)的問題，本文提出MQAAR路由方案.MQAAR是在DSR的基礎(chǔ)上嵌入兩種模型，即識(shí)別穩(wěn)定節(jié)點(diǎn)的穩(wěn)定模型和感知網(wǎng)絡(luò)擁塞的Qos擁塞模型，并采取任播的方式，綜合考慮了穩(wěn)定性、網(wǎng)絡(luò)擁塞、控制開銷、負(fù)載平衡和Qos的因素.仿真結(jié)果表明：相比ACAP、DSR和ALBRS，MQAAR在控制開銷、數(shù)據(jù)包傳輸率和平均端到端延遲方面具有更高的性能，可以更好地應(yīng)用于需要信息共享的場合，具有一定的實(shí)際應(yīng)用價(jià)值.

[1] 符琦. 一種具有業(yè)務(wù)感知的多路徑Qos路由策略[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 陳立, 朱志勇, 姚丹霖. 基于蟻群優(yōu)化算法的Qos多播路由算法改進(jìn)及實(shí)證[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 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] 王多華, 劉乃安, 劉明宇. 任播路由協(xié)議在移動(dòng)Ad hoc網(wǎng)絡(luò)中的應(yīng)用研究[J]. 西安郵電大學(xué)學(xué)報(bào), 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組播路由優(yōu)化[J]. 電子設(shè)計(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] 李澤平, 楊旋, 鮑序. 對(duì)等網(wǎng)端到端多路徑選擇建模及算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 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 結(jié)合 SA 優(yōu)化算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 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.

責(zé)任編輯：龍順潮

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