周蕓韜

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

?

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

周蕓韜*

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

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

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

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

1 提出的路由方案

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

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

(1)

(2)

仿真表明，α和β的值在0.55到0.8之間，能獲得穩(wěn)定性好的節(jié)點.MQAAR通過使用該模型提取高穩(wěn)定性的中間節(jié)點，調(diào)整基于穩(wěn)定節(jié)點的路由網(wǎng)絡(luò)拓撲，降低鏈路失效的概率.

1.2 Qos擁塞模型

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

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

LB=QC/QS.(7)

1.3 路由建立

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

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

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

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

1.5 路由維護過程

2 仿真實驗

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

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

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

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

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

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

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

表6 移動速度變化時的平均端到端延遲Tab.6 Average end to end delay in moving speed change

3 結(jié) 論

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

[1] 符琦. 一種具有業(yè)務(wù)感知的多路徑Qos路由策略[J]. 計算機學(xué)報, 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]. 湘潭大學(xué)自然科學(xué)學(xué)報, 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é)議在移動Ad hoc網(wǎng)絡(luò)中的應(yīng)用研究[J]. 西安郵電大學(xué)學(xué)報, 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è)計工程, 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] 李澤平, 楊旋, 鮑序. 對等網(wǎng)端到端多路徑選擇建模及算法研究[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é)報, 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