基于Ad Hoc網絡的多機器人通信協議改進

，

(昆明理工大學 信息工程與自動化學院,昆明 650504)

基于Ad Hoc網絡的多機器人通信協議改進

雷金輝，潘虹

(昆明理工大學信息工程與自動化學院,昆明650504)

Ad Hoc自組網解決了多機器人系統中網絡拓撲結構動態變化和數據報文多跳轉發的通信問題，決定節點能耗、最優路由和網絡信息延遲等網絡性能，是多機器人系統網絡常用的通信方式；其中AODV協議能較好的在Ad Hoc自組網中適用，但由于多機器人系統中網絡拓撲動態變化，傳統的AODV協議的網絡節點負載情況以及選擇路由的準確性方面存在著一定缺陷；在AODV協議基礎上，采用負載均衡算法的方式，對路由代價進行優化，以便更好的解決網絡節點不均衡、出現擁塞時選路不準確的問題，更好的實現均衡節點能耗、優化路由以及減少網絡信息延遲的目標；以NS2為網絡仿真平臺進行仿真，并對結果進行分析得，與AODV協議相比，改進之后的路由協議的提高了分組投遞率、降低了平均端到端時延以及相對路由開銷。

多機器人通信;Ad Hoc自組網;AODV協議

0 引言

多機器人技術是多學科、多領域的高新技術，通信是多機器人之間相互協作的基礎[1]。Ad Hoc無線網絡是一種解決多機器人系統通信常用的自組織網絡，能夠支持網絡拓撲結構動態變化和數據報文多跳轉發[2-3]。針對基于Ad Hoc無線網絡的路由協議，國內外學者提出了許多方案，其中AODV(ad hoc on-demand distance victor)路由協議是結合了DSR(dynamic source routing)路由協議和DSDV(destination sequence distance vector)路由協議的一種典型的按需驅動路由協議。AODV協議是基于距離矢量算法且以最小跳數作為選擇依據的路由協議，具有出色的可擴展性、較強的環境適應性，成為無線路由協議中的研究熱點[4]。文獻[5-6]提出了基于備份路由的AODV協議改進路由AODV-BAK，在一次路由發現過程中建立主路由和備份路由，以此減少重新尋找路由的開銷。文獻[7]則采用對中斷鏈路進行雙向同時修復的方法以便節省AODV路由協議本地修復時間等。這些方法在一定程度上提高了AODV協議某些方面的性能，但由于多機器人移動過程中網絡拓撲結構變化較快，這些仍不夠理想。

目前對AODV協議的研究以及優化主要在于降低路由開銷和提高鏈路的穩定性。本文針對節點負載均衡以及路由選取提出了AODVH(ad hoc on-demand distance victor hold)協議，在路由選擇時引入負載均衡算法得到路由代價，在非擁塞的情況下選取路由代價作為選擇最佳路由的依據。

1 AODV路由協議

由于各移動節點收發功率和傳輸距離有限，Ad Hoc自組網的路由往往由多跳組成，通過若干中間節點為不在彼此通信范圍內的節點轉發。因為Ad Hoc自組網的網絡結構動態變化，所以傳統固定網絡路由協議變得不再適用，因此對路由協議成為了研究移動機器人通信的研究重點。其中AODV協議因其性能較好、算法簡易且便于實現，深受廣大學者青睞，是Ad Hoc自組網當中設計的相對比較成功的一種路由協議，但是它仍存在一些不足之處需要改進[8],例如：

1)在協議進行選擇路由時沒有考慮到節點負載是否均衡，所以容易出現擁塞情況。并且在一些節點，尤其是交叉節點由于其需要參與的數據轉發次數和頻率都大于其他節點，所以這一部分節點的負載大、能耗快，還會增加網絡延時；

2)在通信協議中源節點往往會接收到不止一個的有效應答，但是通常在進行路由選擇時會以跳數最小作為路由選擇依據，并未考慮到節點移動性。但是運用在多機器人協作時，由于多機器人系統協作所以節點移動性較高，從而以最小條數作為路由選擇的依據選出的路由并非最佳路由。

針對以上問題已經學者進行了研究，并有一些改進方法被提出，但大都從某個單一方面進行考慮。本文針對以上問題進行了研究分析，提出較為綜合的優化方案AODVH協議。AODVH協議的引入解決了AODV協議中負載不均衡以及選擇跳數最小的路由作為依據的弊端：在路由選擇時引入負載均衡算法計算路由代價并考慮節點擁塞情況。AODV協議中，源節點根據路徑長短進行路由選擇，但此方法在拓撲結構頻繁變化的情況下并不適用。對此，AODVH協議綜合了節點跳數和速度以及擁塞情況，引入負載均衡算法計算路由代價。

2 AODVH協議的提出

本文針對傳統的AODV通信協議中所存在的負載均衡、路由代價以及節點擁塞情況的問題進行分析，對AODV協議的算法進行了優化，主要是通過建立節點網絡模型進行判斷?？紤]到節點移動速度從而引入了路由代價函數來進行路由選擇，路由代價函數是綜合了節點跳數以及節點的移動速度進行路由選擇。與此同時源節點判斷到達目的節點路由代價最小的的路由是否存在擁塞狀況，若存在擁塞情況則舍去該條路由。

2.1 AODVH協議節點網絡模型

在Ad Hoc自組織網絡中，節點在MAC層緩沖隊列的占用情況和分組的網絡延時可以反映出節點擁塞情況。所以我們在建立路由時應盡可能避開出現擁塞的節點從而達到網絡中負載均衡的效果。

算法模型在創建路由之初對MAC層的鏈路狀態信息進行監視，并將節點自身的狀態參數發送到網絡層進行擁塞狀態判斷，估計節點到達節點數據包的平均網絡時延。

(1)

其中:λ(0≤λ≤1)代表加權平滑系數;

(2)

(3)

設R(j)代表該節點MAC層接口隊列當中已經存放的數據分組長度，則路徑的數據分組總負荷為:

(4)

設Q(j)代表節點j在MAC層緩存的接口隊列當中數據分組最大值，那么節點j在MAC層的接口隊列中被數據包使用的概率為:

(5)

定義節點j的網絡延時度為:

(6)

設η,ξ分別代表網絡中節點接口隊列使用率以及節點網絡延時度閥值，用S(j)表示節點j的狀態，當j等于0表示節點傳輸順暢，當j等于1表示此時節點擁塞。對于節點j是否擁塞可以進行如下判斷:

(7)

該擁塞模型算法，可較為準確的反映節點擁塞狀況。它考慮當前節點對數據分組的處理速度以及節點緩存隊列中數據分組的負荷。網絡節點尋路時，在節點收到路由請求分組轉發之前，檢查當前該路徑是否處于擁塞狀態。

2.2 AODVH協議路由代價

考慮到中間節點的穩定性，為節點路由增加數據字段Cost作為路由代價，RoutingCost為節點路由代價累加。源節點尋路過程中考慮通往目的節點需要的跳數以及路由中各中間節點的移動性。例如：在網絡中有n個節點分別為:x1,x2,x3,...xn，它們分別以0～Vm內任意速度移動，其中Vm是節點運動時移動的最大速度，設第i個節點移動的速度為Vi:

(8)

設節點i的路由代價為costi：其中跳數和速度引起的路由代價分別為costhopi和costvi，則有:

costi=costhopi+costvi

(9)

令:

Costhopi=1

(10)

(11)

則：

(12)

記p(n)=(1,2,...,j,...,n)表示途徑節點1到節點n，則該路徑的路由代價為：

(13)

由以上可得出：

1)當節點速度在0≤Vilt;0.3Vm時，路由代價值Costi=1，節點跳數和速度的代價分別為Costhopi=1和Costvi=0，此時節點的路由代價與跳數的增加相同，此時路由代價主要取決于節點跳數，與AODV選擇機制相吻合；

2)當節點速度為0.3Vm≤Vilt;0.7Vm時，路由代價值Costi=2，節點速度代價值為Costvi=1，此時每增加一跳節點的路由代價增長2，此時均衡考慮節點的跳數與速度因素；

3)節點速度為0.7Vm≤Vilt;Vm時，路由代價值Costi=3，節點速度的代價為2，每增加一跳節點的路由代價值會增加3，速度部分所占比重進一步增大，成為了主要考慮得因素。

在進行尋路的過程中，當源節點同時收到了多個應答消息的時候，會將每條可用的路由的RoutingCost作為依據來衡量路由穩定性選擇的依據，然后選擇RoutingCost最小的路由用來傳送數據分組。同時我們可以看出隨著速度的增大對路由代價的影響也變大，在進行路由選擇時把該節點用來轉發的可能性就越小。所以在選擇路由時我們比較傾向于選擇移動性較低的節點進行轉發，與此同時得到的路由鏈路的穩定性越強，節省了路由的網絡開銷。

2.3 AODVH路由協議分析

綜上所述，在AODV協議進行優化之后的AODVH協議在路由發現的過程中，由源節點到目的節點之間經過不同節點會產生有不止一條路徑?？紤]到經過不同節點的節點速度以及跳數得出各條路徑的路由代價，若節點路由較大則可能是節點移動性較強，路由不穩定，容易出現斷裂。同時選擇設置合適的網絡節點接口隊列使用率以及節點網絡延時度閥值，判斷節點是否處于擁塞狀態，若出現擁塞則該路徑負荷較大，節點的丟包率和網絡延遲都很大，所以需要舍棄。再在非擁塞路徑中選擇路由代價最小的路徑作為最佳路由。這樣選擇出的最佳路由相對穩定，同時有效避免了因網絡擁塞以及節點速度過大而引起的路由失效而重新尋找路由。

3 協議仿真分析

利用NS2網絡平臺進行仿真：仿真中網絡范圍大小設為1 000*1 000的矩形區域，50個網絡節點。同時設置好不同的最大移動速度隨機地分布在拓撲結構區域內移動。最大連接數為20，發包速率為每秒可以發送4個CBR包，MAC層采用的協議是IEEE802.11。模擬時間設定為300 s，不同速度對比仿真情形中節點移動速度的最大值分別設置為1、5、10、15、20、25、30(m/s)。在不同節點暫停時間對比情形中，節點暫停時間分別設置為0、20、40、60、80、100、120(s)。該實驗中，在對節點擁塞狀態進行判斷時我們選取參數。

本實驗運用Otcl語言編寫程序，在NS2上對編寫完成的Otcl進行運行實現仿真。仿真完成之后生成相應的trace文件，分別對兩種協議仿真結果trace文件進行數據統計，利用MATLAB將提取出來的數據進行畫圖分析。

從圖1得出節點在移動速度較低的時候，AODV協議與AODVH協議的分組投遞率均處于較高水平，表明源節點發送的數據包基本都能被目的節點準確接收；與此同時當網絡中節點移動速度逐漸增大的同時二者分組投遞率均逐漸降低。此時AODV協議的分組投遞率下降較為迅速。由于AODVH協議在進行路由選擇時傾向選擇速度較低的路由作為轉發節點，所選路由較為穩定，分組投遞率下降相對緩慢。

圖1 分組投遞率

由圖2可得，在節點最大速度較低時，AODVH協議和AODV協議的平均端到端的網絡延時都比較小，隨著節點移動速度的增大，兩種協議的平均端到端延時都增大，這時在AODV協議中源節點發送的數據包會因為路由的斷裂失效或者由于網絡的擁塞等原因出現排隊等待、甚至會出現隊列溢出大量丟包而導致重傳，從而延遲增加。與此同時因為考慮到了AODV協議的缺點我們在AODVH協議引入了負載均衡，因此選擇出的路由更為穩定，其平均端到端的時延明顯低于AODV路由協議，出現的變化也相對比較穩定。

圖2 平均端到端延時

由圖3可知，在節點速度較低時，AODVH協議路由開銷高于AODV協議，這是因為AODVH協議在控制分組中添加了額外的字段，增加了尋找路由的開銷；隨著節點速度逐漸增大，二者的相對路由開銷都增大，從圖可以看出AODV協議的開銷急劇增大，AODVH協議由于增加了備用路由增大相對緩慢，明顯低于AODV協議。

圖3 相對路由開銷

由圖4可得，在節點最大速度較低時，網絡結構相對比較穩定，節點建立出的路由不容易斷裂而導致路由的失效。AODV協議和AODVH協議的路由發現頻率都比較低，隨著移動節點的速度的增大，網絡的拓撲結構變化也加快，此時路由的穩定性降低，開始出現斷裂和失效，AODV協議的路由發現頻率開始增加，而改進后的AODVH協議因為考慮到了負載均衡，從而減少了網絡中的擁塞情況，所選擇的路由相對穩定，路由發現頻率也明顯的低于AODV協議。

由以上實驗結果對比我們可以得出，在節點移動速度較低時兩種路由節點的分組投遞率、平均端到端延遲、相對路由開銷和路由發現頻率的區別不大。但是隨著節點速度的逐漸增大，AODV協議下節點的分組投遞率、平均端到端時延、相對路由開銷以及路由發現頻率均大于AODVH協議。該實驗

圖4 路由發現頻率

充分的驗證了在考慮了負載均衡以及路由開銷以及節點擁塞之后的AODVH路由協議的有效性和可用性。

4 總結

本文分析了Ad Hoc網絡中AODV路由協議在多機器人通信系統為背景的情況下因節點的移動性加強所以存在的一些問題，并對此做出了改進，提出了AODVH協議。AODVH協議以路由跳數與節點速度得出的路由代價，并綜合考慮到了節點擁塞情況作為選擇路由的基準，提出仿真進行實驗，通過對比節點的分組投遞率、平均端到端時延和相對路由開銷可以得出：改進后的AODVH協議在節點移動速度較快，網絡拓撲結構變化較為頻繁的環境下可以有效的提高網絡性能，為多機器人系統中通信協議的應用提供了指導，同時也為進一步研究Ad Hoc自組網中的其他路路由協議奠定了基礎[8-18]。

[1] Li Ping, Yang Yin. Progress of Task Allocation in Multi-robot Systems[J]. Computer Engineering and Application ,2008,44(17):201-205.

[2] 陳林星,曾 曦,曹 毅.移動Ad Hoc網絡--自組織分組無線網絡技術[M].2版.北京:電子工業出版社,2012.

[3] 羅 超.Ad Hoc網絡中按需路由協議AODV的改進與仿真[D]武漢:武漢理工大學,2010.

[4] Misra R, Mandal C R. Performance comparison of AODV/DSR on-demand routing protocols for ad hoc networks in constrained situation[A].IEEE International Conference on Personal Wireless Communication[C]. 2005:86-89.

[5] 羅 超.Ad hoc 網絡中按需路由協議AODV的改進與仿真[D].武漢理工大學,2010.

[6] 蔡 箐,朱余兵.一種基于AODV改進的城市車載自主網絡路由協議研究[J].計算機工程與科學,2013,35(1)：61-65.

[7] Bahador Amiri, Hamid R Sadjapour. Outage optimum routing for wireless Ad Hoc networks[A]. Proc of 7th International Conference of Wireless Communications and Mobile Computing[C], 2011:1576-1587.

[8] 劉開創，施家棟，王建中，等.移動機器人自主返航控制系統設計與實驗[J].計算機測量與控制,2016,11(3):1671-1782.

[9] 王首浩,仲 悅,張 巍,等.一種用于分布式控制的光纖通信協議設計與仿真[J].計算機測量與控制,2014,22(9):3044-3046.

[10] Zhang Yi, Li Yanle, Luo Yuan. Multi-robot map building based on Ad Hoc network communication[C].中國自動化學會控制理論專業委員會c卷,2011:4007-4010.

[11] 仁孝平,蔡自興,陳愛斌.多移動機器人通信系統研究進展[J].控制與決策,2010,25(3):327-332.

[12] 李向麗,荊瑞霞,何一涵.避免路由斷裂的優化AODV路由協議[J].計算機應用,2014,34(9):2458-2471.

[13] 王金龍.Ad Hoc移動無線網絡[M].北京：國防部工業出版社，2004.

[14] 李 云,隆克平,吳詩其.IEEE802.1 1 DCF性能分析及改進[J].電子學報,2003,31(10):1446-1451.

[15] 朱龍杰,方旭明.UWB技術在移動Ad Hoc網絡中的應用研究[J].數據通信,2004(6):16-20.

[16] 肖 靂. AODV路由協議路由修復研究和改進[D].北京:北京郵電大學.2010.

[17] 李 慶,劉 聰,江漢紅,等.Ad Hoc網絡中AODV路由協議的優化[J].計算機工程,2008,34(13):107-109.

[18] 曹勇剛,羅慶生,等.新型球形機器人控制系統雙處理器通信機制研究[J].計算機測量與控制,2009,17(7):1311-1355.

ImprovementofMulti-RobotCommunicationProtocolBasedonAdHocNetwork

Lei Jinhui, Pan Hong

(College of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650504, China)

Ad Hoc network solves the communication problem of network topology dynamic structure and multi-hop forwarding of data packets in multi-robot system, and determines the network performance such as node energy consumption, optimal routing and network information delay. It is a commonly used way of communication for multi-robot system network. The AODV protocol can be applied in the Ad Hoc network, but there are some shortcomings in the network topology of the traditional AODV protocol and the accuracy of the selection route because the dynamic changes of the network topology in the multi-robot system. Based on the AODV protocol, adopts the method of load balancing algorithm to optimize the routing cost to solve the problem that the network nodes are not balanced, and the congestion is not accurate. Better achieve energy consumption of balanced nodes, optimize routing and reduce the delay of network information . NS2 is used to simulate the network simulation platform, and the results are analyzed .The simulation results show that compared with the AODV protocol, the improved routing protocol improves the packet delivery rate and reduces the average end-to-end delay and the relative routing cost.

multi-robot communication; Ad Hoc network; AODV protocol

2017-03-14；

2017-03-31。

國家自然科學基金資助項目(51365019)。

雷金輝(1965-),男,云南昆明人,副教授，主要從事計算機應用方向的研究；

潘 虹(1992-),女, 四川廣元人,碩士研究生，主要從事信號與信息處理方向的研究。

1671-4598(2017)09-0191-03

10.16526/j.cnki.11-4762/tp.2017.09.049

TP393.4

A