，

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

基于Ad Hoc網(wǎng)絡(luò)的多機器人通信協(xié)議改進

雷金輝，潘虹

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

Ad Hoc自組網(wǎng)解決了多機器人系統(tǒng)中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化和數(shù)據(jù)報文多跳轉(zhuǎn)發(fā)的通信問題，決定節(jié)點能耗、最優(yōu)路由和網(wǎng)絡(luò)信息延遲等網(wǎng)絡(luò)性能，是多機器人系統(tǒng)網(wǎng)絡(luò)常用的通信方式；其中AODV協(xié)議能較好的在Ad Hoc自組網(wǎng)中適用，但由于多機器人系統(tǒng)中網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化，傳統(tǒng)的AODV協(xié)議的網(wǎng)絡(luò)節(jié)點負(fù)載情況以及選擇路由的準(zhǔn)確性方面存在著一定缺陷；在AODV協(xié)議基礎(chǔ)上，采用負(fù)載均衡算法的方式，對路由代價進行優(yōu)化，以便更好的解決網(wǎng)絡(luò)節(jié)點不均衡、出現(xiàn)擁塞時選路不準(zhǔn)確的問題，更好的實現(xiàn)均衡節(jié)點能耗、優(yōu)化路由以及減少網(wǎng)絡(luò)信息延遲的目標(biāo)；以NS2為網(wǎng)絡(luò)仿真平臺進行仿真，并對結(jié)果進行分析得，與AODV協(xié)議相比，改進之后的路由協(xié)議的提高了分組投遞率、降低了平均端到端時延以及相對路由開銷。

多機器人通信;Ad Hoc自組網(wǎng);AODV協(xié)議

0 引言

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

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

1 AODV路由協(xié)議

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

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

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

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

2 AODVH協(xié)議的提出

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

2.1 AODVH協(xié)議節(jié)點網(wǎng)絡(luò)模型

在Ad Hoc自組織網(wǎng)絡(luò)中，節(jié)點在MAC層緩沖隊列的占用情況和分組的網(wǎng)絡(luò)延時可以反映出節(jié)點擁塞情況。所以我們在建立路由時應(yīng)盡可能避開出現(xiàn)擁塞的節(jié)點從而達到網(wǎng)絡(luò)中負(fù)載均衡的效果。

算法模型在創(chuàng)建路由之初對MAC層的鏈路狀態(tài)信息進行監(jiān)視，并將節(jié)點自身的狀態(tài)參數(shù)發(fā)送到網(wǎng)絡(luò)層進行擁塞狀態(tài)判斷，估計節(jié)點到達節(jié)點數(shù)據(jù)包的平均網(wǎng)絡(luò)時延。

(1)

其中:λ(0≤λ≤1)代表加權(quán)平滑系數(shù);

(2)

(3)

設(shè)R(j)代表該節(jié)點MAC層接口隊列當(dāng)中已經(jīng)存放的數(shù)據(jù)分組長度，則路徑的數(shù)據(jù)分組總負(fù)荷為:

(4)

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

(5)

定義節(jié)點j的網(wǎng)絡(luò)延時度為:

(6)

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

(7)

該擁塞模型算法，可較為準(zhǔn)確的反映節(jié)點擁塞狀況。它考慮當(dāng)前節(jié)點對數(shù)據(jù)分組的處理速度以及節(jié)點緩存隊列中數(shù)據(jù)分組的負(fù)荷。網(wǎng)絡(luò)節(jié)點尋路時，在節(jié)點收到路由請求分組轉(zhuǎn)發(fā)之前，檢查當(dāng)前該路徑是否處于擁塞狀態(tài)。

2.2 AODVH協(xié)議路由代價

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

(8)

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

costi=costhopi+costvi

(9)

令:

Costhopi=1

(10)

(11)

則：

(12)

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

(13)

由以上可得出：

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

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

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

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

2.3 AODVH路由協(xié)議分析

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

3 協(xié)議仿真分析

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

本實驗運用Otcl語言編寫程序，在NS2上對編寫完成的Otcl進行運行實現(xiàn)仿真。仿真完成之后生成相應(yīng)的trace文件，分別對兩種協(xié)議仿真結(jié)果trace文件進行數(shù)據(jù)統(tǒng)計，利用MATLAB將提取出來的數(shù)據(jù)進行畫圖分析。

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

圖1 分組投遞率

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

圖2 平均端到端延時

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

圖3 相對路由開銷

由圖4可得，在節(jié)點最大速度較低時，網(wǎng)絡(luò)結(jié)構(gòu)相對比較穩(wěn)定，節(jié)點建立出的路由不容易斷裂而導(dǎo)致路由的失效。AODV協(xié)議和AODVH協(xié)議的路由發(fā)現(xiàn)頻率都比較低，隨著移動節(jié)點的速度的增大，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化也加快，此時路由的穩(wěn)定性降低，開始出現(xiàn)斷裂和失效，AODV協(xié)議的路由發(fā)現(xiàn)頻率開始增加，而改進后的AODVH協(xié)議因為考慮到了負(fù)載均衡，從而減少了網(wǎng)絡(luò)中的擁塞情況，所選擇的路由相對穩(wěn)定，路由發(fā)現(xiàn)頻率也明顯的低于AODV協(xié)議。

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

圖4 路由發(fā)現(xiàn)頻率

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

4 總結(jié)

本文分析了Ad Hoc網(wǎng)絡(luò)中AODV路由協(xié)議在多機器人通信系統(tǒng)為背景的情況下因節(jié)點的移動性加強所以存在的一些問題，并對此做出了改進，提出了AODVH協(xié)議。AODVH協(xié)議以路由跳數(shù)與節(jié)點速度得出的路由代價，并綜合考慮到了節(jié)點擁塞情況作為選擇路由的基準(zhǔn)，提出仿真進行實驗，通過對比節(jié)點的分組投遞率、平均端到端時延和相對路由開銷可以得出：改進后的AODVH協(xié)議在節(jié)點移動速度較快，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化較為頻繁的環(huán)境下可以有效的提高網(wǎng)絡(luò)性能，為多機器人系統(tǒng)中通信協(xié)議的應(yīng)用提供了指導(dǎo)，同時也為進一步研究Ad Hoc自組網(wǎng)中的其他路路由協(xié)議奠定了基礎(chǔ)[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網(wǎng)絡(luò)--自組織分組無線網(wǎng)絡(luò)技術(shù)[M].2版.北京:電子工業(yè)出版社,2012.

[3] 羅 超.Ad Hoc網(wǎng)絡(luò)中按需路由協(xié)議AODV的改進與仿真[D]武漢:武漢理工大學(xué),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 網(wǎng)絡(luò)中按需路由協(xié)議AODV的改進與仿真[D].武漢理工大學(xué),2010.

[6] 蔡 箐,朱余兵.一種基于AODV改進的城市車載自主網(wǎng)絡(luò)路由協(xié)議研究[J].計算機工程與科學(xué),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] 劉開創(chuàng)，施家棟，王建中，等.移動機器人自主返航控制系統(tǒng)設(shè)計與實驗[J].計算機測量與控制,2016,11(3):1671-1782.

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

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

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

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

[13] 王金龍.Ad Hoc移動無線網(wǎng)絡(luò)[M].北京：國防部工業(yè)出版社，2004.

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

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

[16] 肖 靂. AODV路由協(xié)議路由修復(fù)研究和改進[D].北京:北京郵電大學(xué).2010.

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

[18] 曹勇剛,羅慶生,等.新型球形機器人控制系統(tǒng)雙處理器通信機制研究[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。

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

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

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

1671-4598(2017)09-0191-03

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

TP393.4

A