遠海無人船編隊系統(tǒng)AD HOC網(wǎng)絡(luò)組播路由算法設(shè)計

李紅衛(wèi)，陳業(yè)程

(1.廣東交通職業(yè)技術(shù)學(xué)院,廣東 廣州 510800；2.廣東省船舶自動化工程技術(shù)研究中心,廣東 廣州 510800)

0 引 言

無人駕駛船最早出現(xiàn)于上世紀五六十年代，主要在遙控平臺的近程海域作業(yè)。隨著信息技術(shù)、通信導(dǎo)航、衛(wèi)星定位以及智能控制技術(shù)的進步，其作業(yè)范圍逐步拓展至遠程海域。近年來，自主無人船是水面航行器研究的一個熱點，特別在軍事領(lǐng)域，目前世界上多個海洋強國開發(fā)了多種遠程無人船平臺以滿足其軍事和國家安全的需要。國內(nèi)對遠程智能無人船的研究起步較晚，雖然與歐美國家還有一定差距，但也取得了一定的成果。

雖然無人船的應(yīng)用案例很多，優(yōu)勢明顯，但是單無人船作業(yè)，其作業(yè)范圍、作業(yè)時間、作業(yè)方式有限，且難以完成復(fù)雜任務(wù)。為了適應(yīng)未來挑戰(zhàn)，能夠順利、高效地完成復(fù)雜任務(wù)，除了提高單無人船功能和效用外，還需要實現(xiàn)及時、準確的多無人船編隊調(diào)度，利用多艘無人船同時工作，更高效地完成任務(wù)，具有更強大的海上執(zhí)行任務(wù)功能。

本文所述遠海無人船編隊系統(tǒng)包括船載控制系統(tǒng)和岸基控制系統(tǒng)。船載控制系統(tǒng)設(shè)置在無人船船體上，各無人船通過AD HOC網(wǎng)絡(luò)節(jié)點設(shè)備實現(xiàn)相互之間信息交互，包括作業(yè)控制信息、自動定點作業(yè)、多無人船自主交互、多無人船組合導(dǎo)航、自主巡航、安全避障、自主循跡等信息。同時定義其中一AD HOC網(wǎng)絡(luò)節(jié)點設(shè)備作為網(wǎng)絡(luò)匯節(jié)點，由匯節(jié)點通過船載衛(wèi)星通信終端實現(xiàn)無人船編隊與岸基控制系統(tǒng)的信息交互。所述遠海無人船編隊系統(tǒng)如圖1所示。

圖1 無人船編隊系統(tǒng)結(jié)構(gòu)圖

1 移動AD HOC網(wǎng)絡(luò)主要特點

移動AD HOC網(wǎng)絡(luò)是一種無中心自組織、沒有預(yù)設(shè)基礎(chǔ)設(shè)施的多跳無線網(wǎng)絡(luò)，是由一組帶有無線收發(fā)裝置的移動節(jié)點組成的臨時性自治系統(tǒng)，依靠網(wǎng)絡(luò)內(nèi)部具有移動性的節(jié)點之間的協(xié)作，完成節(jié)點間通信。與其它類型的無線網(wǎng)絡(luò)(如蜂窩網(wǎng)、無線局域網(wǎng)WLAN、衛(wèi)星系統(tǒng))相比，具有以下主要特性[1]：

(1) 自組織性。AD HOC網(wǎng)絡(luò)完全由無線節(jié)點組成，沒有任何固定基礎(chǔ)設(shè)施。所有節(jié)點地位平等，節(jié)點可隨時加入和離開，具有較強的抗毀性。

(2) 動態(tài)拓撲。AD HOC網(wǎng)絡(luò)具有動態(tài)特性，拓撲結(jié)構(gòu)可以高度變化，所有節(jié)點可以任意移動(包括高速移動)。

(3) 多跳拓撲。無限節(jié)點通信距離有限，節(jié)點具有轉(zhuǎn)發(fā)報文的能力，節(jié)點間的通信可能要經(jīng)過多個中繼節(jié)點的轉(zhuǎn)發(fā)，這也是AD HOC網(wǎng)絡(luò)與其他移動網(wǎng)絡(luò)的最本質(zhì)區(qū)別。

(4) 帶寬有限且易變。無線信道本身的物理特性決定了它所能提供的網(wǎng)絡(luò)帶寬要比有線信道低得多。尤其野外情況下，由于復(fù)雜地形引起的多徑、衰落、噪聲及信道干擾、競爭共享無線信道所產(chǎn)生的碰撞等影響，帶寬利用率低且無線鏈路容量容易發(fā)生變化。

(5) AD HOC網(wǎng)絡(luò)的每個節(jié)點兼?zhèn)渲鳈C和路由器功能，是無線通信技術(shù)與計算機網(wǎng)絡(luò)技術(shù)相結(jié)合的產(chǎn)物。

總之，AD HOC網(wǎng)絡(luò)是一種移動、無線、多跳的分布式網(wǎng)絡(luò)。為了進行有效通信，必須在移動主機間建立合適的路由，所以設(shè)計快速、高效、健壯的路由算法極為必要[2]。

2 選路算法

當(dāng)源節(jié)點S需要在本地路由表中尋找一條到目的節(jié)點D的最優(yōu)路由時，可以采用多種算法，如果考慮鏈路的權(quán)值(如傳輸速率、誤碼率等)，則最優(yōu)路由是從S到D的所有鏈路的權(quán)值或者代價總和最小的一條路由。

本系統(tǒng)AD HOC網(wǎng)絡(luò)節(jié)點間的數(shù)據(jù)傳輸采用源路由方式，即每一個節(jié)點都需要維護一張到達全網(wǎng)其它節(jié)點的系統(tǒng)路由表，數(shù)據(jù)以源路由選項夾帶發(fā)送，中間節(jié)點不參與選路過程。系統(tǒng)路由表基于全網(wǎng)鏈路質(zhì)量矩陣(動態(tài)、靜態(tài)、混合3種)，采用最短路徑算法(Dijkstra)計算而得，鏈路質(zhì)量為由接收信噪比與物理層數(shù)據(jù)傳輸誤碼率及阻塞率計算得出的0～7的數(shù)值[3]。

Dijkstra最短路徑算法是典型的最短路徑算法，用于計算一個節(jié)點到其他節(jié)點的最短路徑。即以本節(jié)點為起點，不斷加入最短邊，最終得到目的節(jié)點的最短路徑。

該算法的具體描述如下：

集合S：存放已求出最短路徑的頂點，初始時，S中只包含起點即源節(jié)點v0。計算過程中求得的每一條最短路徑(v0, …vk)都放入集合S中，直到求出全部頂點算法即結(jié)束。

設(shè)置輔助數(shù)組d，其每一分量d[i]表示當(dāng)前找到的從源節(jié)點v0到終點vi的最短路徑的長度。若從源節(jié)點v0到終點vi有路徑可達，則將該路徑即該邊權(quán)值放入d[i]；若從源點到終點沒有路徑可達，即認為距離為+∞，并將+∞放入d[i]。

(1) 假設(shè)第1條最短路徑為(v0,vk),并且k滿足：d[k]=min{d[i] ∣vi∈V-v0}，V為所有頂點集合。

(2) 求下一條最短路徑：假設(shè)下次最短路徑的終點是vj，則它要么是(v0,vj)，要么是(v0,vk,vj)。其長度要么是從v0到vj邊上的權(quán)值，要么是d[k]與從vk到vj邊上的權(quán)值之和。

可知下一條次短的最短路徑的長度必是：d[k]=min{d[i] ∣vi∈V-S}。

(3) 集合S存放每一次已經(jīng)求出最短路徑的終點，然后對所有的vi∈V-S，修改其d[i]:d[i]=min{d[i],d[k]+e[k][i]}，e[k][i]為邊(vk,vi)上的權(quán)值。

算法的核心是綜合鏈路權(quán)重，表示為：W(i,j)=αQ(i,j)+βD(i,j)+c。其中，Q(i,j)表示鏈路i→j的鏈路質(zhì)量；D(i,j)表示鏈路i→j的延遲參數(shù)；α和β為權(quán)值；c為恒定參數(shù)；參數(shù)的不同選擇，決定了算法的適用環(huán)境：

(1) 當(dāng)α=0時，算法為延遲最小路由算法；

(2) 當(dāng)β=0時，算法為鏈路質(zhì)量最大路由算法；

(3) 當(dāng)α=0，β=0時，算法為傳統(tǒng)的最小跳數(shù)路由算法；

(4) 當(dāng)α>0，β>0時，算法為綜合最優(yōu)路由算法。

在本系統(tǒng)中，取α=1，β=1，c=0，綜合鏈路權(quán)重W(i,j)主要依據(jù)全網(wǎng)鏈路質(zhì)量矩陣(動態(tài)路由方式下為全網(wǎng)動態(tài)鏈路質(zhì)量矩陣；靜態(tài)路由方式下為全網(wǎng)靜態(tài)鏈路質(zhì)量矩陣)和節(jié)點負載，每一條鏈路Q(i,j)均考慮了正反向的鏈路狀況，為正反鏈路質(zhì)量之和(即系統(tǒng)路由決定于節(jié)點間的雙向鏈路)。此處的鏈路質(zhì)量并非節(jié)點間真實的鏈路質(zhì)量，而是由鏈路質(zhì)量矩陣經(jīng)轉(zhuǎn)換而得，轉(zhuǎn)換規(guī)則如下：

(1) 鏈路質(zhì)量為0，則轉(zhuǎn)換后的值為240；

(2) 鏈路質(zhì)量為1，則轉(zhuǎn)換后的值為60；

(3) 鏈路質(zhì)量為2，則轉(zhuǎn)換后的值為10；

(4) 鏈路質(zhì)量為3，則轉(zhuǎn)換后的值為9；

(5) 鏈路質(zhì)量為4，則轉(zhuǎn)換后的值為8；

(6) 鏈路質(zhì)量為5，則轉(zhuǎn)換后的值為7；

(7) 鏈路質(zhì)量為6，則轉(zhuǎn)換后的值為6；

(8) 鏈路質(zhì)量為7，則轉(zhuǎn)換后的值為5。

另外，對于鏈路的2個頂點，還考慮了該節(jié)點數(shù)據(jù)發(fā)送緩沖的當(dāng)前擁塞系數(shù)(即可能造成的傳輸延時)。

3 組播路由算法

3.1 算法思想

求出滿足約束條件下的基于最少中繼節(jié)點的最小代價組播樹，算法分為以下兩步：

(1) 求出滿足約束條件下代價最小的組播樹；

(2) 合并中繼節(jié)點，使得到的組播樹中的中繼節(jié)點最少。

3.2 代價函數(shù)及約束條件

在組播路由中，鏈路代價函數(shù)cost主要由鏈路質(zhì)量及節(jié)點負載構(gòu)成。

約束條件主要包括最大跳數(shù)約束、最小代價約束和最小性資源消耗約束。最大跳數(shù)約束：從源節(jié)點到目的節(jié)點的路徑長度，必須低于給定的門限值(這里限定為6跳網(wǎng)絡(luò))；最小代價約束：生成的滿足最大跳數(shù)約束的組播樹的總體代價最??；最小性資源消耗約束：根據(jù)無線網(wǎng)絡(luò)的特點，某節(jié)點發(fā)送一次數(shù)據(jù)，其鄰居節(jié)點都能收到，如果組播樹的中繼節(jié)點越少，分配給中繼進行數(shù)據(jù)轉(zhuǎn)發(fā)的時隙越少，資源消耗越少。

同時在選擇路由時需要合理考慮流量平衡問題，一個基本原則就是到不同目的節(jié)點盡量使用不同的中繼節(jié)點。如果到同一目的節(jié)點存在多條長度相等但經(jīng)過不同中繼節(jié)點的路由，則每次發(fā)送數(shù)據(jù)時也盡量使用不同的路由，這樣有利于實現(xiàn)轉(zhuǎn)發(fā)節(jié)點的流量平衡，避免出現(xiàn)轉(zhuǎn)發(fā)數(shù)據(jù)大量堆積在某個中繼節(jié)點而無法及時得到轉(zhuǎn)發(fā)的情況。

3.3 算法描述

為描述算法，給出幾個定義：T表示生成樹，T′用來存儲節(jié)點跳數(shù)按升序排序后的生成樹。R指生成樹中的源節(jié)點s和目的節(jié)點集合D以外的節(jié)點。Dk表示D中滿足跳數(shù)要求的目的節(jié)點集合。

最小路徑：2個節(jié)點之間的最小路徑是指這2個節(jié)點之間代價最小的路徑；某節(jié)點到最小生成樹的路徑是指該節(jié)點到樹的各節(jié)點最短路徑中代價最小的那條。節(jié)點到樹的最短路徑也被稱為樹到節(jié)點的最短路徑，節(jié)點到樹最短路徑的代價稱為節(jié)點到樹的最短距離[4]。

算法具體步驟如下：

(1) 求滿足跳數(shù)約束的最低代價組播樹，如圖2所示。

圖2 求滿足跳數(shù)約束的最低代價組播樹算法流程圖

(2) 合并中繼，流程圖如圖3所示。

圖3 合并中繼算法流程圖

定義：V為最小生成樹中所有節(jié)點集合，R為中繼節(jié)點集合，Tmp為臨時節(jié)點集合，n為臨時節(jié)點。Cov(v)為節(jié)點v所覆蓋的目的節(jié)點集合。

最終所求組播樹的構(gòu)成如下:

(a) 首先,包括所有的目的節(jié)點,即D內(nèi)的所有節(jié)點,設(shè)置節(jié)點類型為目的節(jié)點；

(b) 其次,包括R內(nèi)所有節(jié)點,節(jié)點類型為中繼節(jié)點,如果,該節(jié)點同時為目的節(jié)點,則設(shè)置節(jié)點類型為中繼或目的節(jié)點。

3.4 應(yīng)用實例

網(wǎng)絡(luò)拓撲：源節(jié)點S，目的節(jié)點C、D、E、F、G。網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖如圖4所示。

圖4 網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖

通過Dijkstra最短路徑算法求得的最短路由樹如圖5所示。

圖5 最短路由樹結(jié)構(gòu)圖

算法詳細步驟：

(1)MF=φ，V= {B，C，D，E，F(xiàn)，G}，Aux={C，D，E，F(xiàn)，G}；

(2) 源節(jié)點S覆蓋的目的節(jié)點C，將C從Aux中刪除：Aux={D，E，F(xiàn)，G}；

(3)n=G，因為Cov(G)={E，F(xiàn)}，覆蓋目的節(jié)點個數(shù)最大，Aux={D，G}；V={B，C，D，E}；MF={G}；

(4)Aux中所有節(jié)點覆蓋目的節(jié)點個數(shù)均小于2，n=null，停止；

(5)Aux！=φ，所以查找路由表，發(fā)現(xiàn)路由{S，B，D}和{S，B，D，G}，將這2條路由的所有中繼添加到MF中，則MF={B，D，G}；

(6) 所以源路由為：{S，B，C，D，E，F(xiàn)，G}，其中S為源節(jié)點，B為中繼節(jié)點，D，G為中繼或目的節(jié)點，C，E，F(xiàn)為目的節(jié)點。

最終得到的最小組播路由樹如圖6所示。

圖6 最小組播路由樹結(jié)構(gòu)圖

在綜合平衡最大跳數(shù)約束、最小代價約束和最小性資源消耗約束等約束條件情況下，獲得基于最少中繼節(jié)點的最小代價組播樹。該最小代價組播樹包含所有源節(jié)點、目的節(jié)點、最短路由邊的拓撲矩陣，使得發(fā)送數(shù)據(jù)時，將數(shù)據(jù)沿著盡可能多的覆蓋目的節(jié)點的路徑傳輸，可以減少路由請求次數(shù)，減少網(wǎng)絡(luò)開銷，在最短的時間內(nèi)將數(shù)據(jù)傳送到各個目的節(jié)點。

4 仿真測試

本方案中采用OPNET Technologies Inc公司的OPNET網(wǎng)絡(luò)仿真工具對組播協(xié)議進行仿真。在AD HOC網(wǎng)絡(luò)中，每個節(jié)點都是對等節(jié)點，即每個節(jié)點都可以作為服務(wù)器，也可以作為客戶端，且所有節(jié)點可以產(chǎn)生的業(yè)務(wù)也是相同的。因此，所設(shè)計的組播路由算法的仿真采用wlan_server_adv通用平臺，其節(jié)點模型如圖7所示。

圖7 仿真節(jié)點模型

對于所設(shè)計的組播算法的性能優(yōu)劣主要通過與Internet網(wǎng)絡(luò)比較指標得到，在此比較丟包率和時延參數(shù)。在該仿真試驗中，若某個節(jié)點發(fā)送數(shù)據(jù)包之后，如收到目的節(jié)點回復(fù)ACK即認為發(fā)送成功，否則認為發(fā)送數(shù)據(jù)包丟失。

丟包率的計算公式可以寫為：丟包率=(發(fā)送數(shù)據(jù)包數(shù)-收到ACK數(shù))/發(fā)送數(shù)據(jù)包數(shù)。時延為一次完整通信過程所持續(xù)的時間，即數(shù)據(jù)包從源節(jié)點到目的節(jié)點所占用的時間。

本仿真中定義丟包率為同網(wǎng)絡(luò)規(guī)模下的平均數(shù)據(jù)傳輸丟包率，時延為不同網(wǎng)絡(luò)規(guī)模下的平均傳輸時延。圖8為移動AD HOC網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)在不同網(wǎng)絡(luò)規(guī)模下的平均數(shù)據(jù)傳輸丟包率，圖9為移動AD HOC網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)在不同網(wǎng)絡(luò)規(guī)模下的平均傳輸時延。

圖8 AD HOC網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)數(shù)據(jù)傳輸丟包率仿真曲線

圖9 AD HOC網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)數(shù)據(jù)傳輸時延仿真曲線

從以上仿真結(jié)果可知當(dāng)節(jié)點數(shù)在32個以內(nèi)時，移動AD HOC網(wǎng)絡(luò)移動Internet網(wǎng)絡(luò)的數(shù)據(jù)傳輸丟包率性能相當(dāng)，而AD HOC網(wǎng)絡(luò)的時延，明顯小于Internet網(wǎng)絡(luò)的時延，說明設(shè)計的組播路由算法在AD HOC網(wǎng)絡(luò)規(guī)模較小時具有較高的信號傳輸效率，且信號失真率低[5]。隨著節(jié)點數(shù)量的增加，2種網(wǎng)絡(luò)的信號傳輸時延逐漸相同。

5 結(jié)束語

自主無人船是無人船編隊水面航行器研究的一個熱點，在未來將得到大力發(fā)展。為滿足無人船編隊自組織網(wǎng)絡(luò)的數(shù)據(jù)傳輸需求，本文基于移動 AD HOC網(wǎng)絡(luò)設(shè)計組播路由算法，以便網(wǎng)絡(luò)節(jié)點按組工作完成給定任務(wù)。本文設(shè)計了改進的Dijkstra最短路徑選路算法，通過選路算法求出節(jié)點到節(jié)點之間的最短路徑，通過合并中繼可求出最小組播路由樹。仿真比較不同網(wǎng)絡(luò)規(guī)模下AD HOC網(wǎng)絡(luò)與Internet網(wǎng)絡(luò)的傳輸性能，驗證了該算法具有良好的數(shù)據(jù)傳輸效率。不同網(wǎng)絡(luò)的節(jié)點數(shù)據(jù)傳輸仿真試驗表明，該組播路由算法具有良好的數(shù)據(jù)傳輸效率。