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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

2 選路算法

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

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

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

該算法的具體描述如下：

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

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

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

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

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

(3) 集合S存放每一次已經(jīng)求出最短路徑的終點(diǎn)，然后對(duì)所有的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時(shí)，算法為延遲最小路由算法；

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

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

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

在本系統(tǒng)中，取α=1，β=1，c=0，綜合鏈路權(quán)重W(i,j)主要依據(jù)全網(wǎng)鏈路質(zhì)量矩陣(動(dòng)態(tài)路由方式下為全網(wǎng)動(dòng)態(tài)鏈路質(zhì)量矩陣；靜態(tài)路由方式下為全網(wǎng)靜態(tài)鏈路質(zhì)量矩陣)和節(jié)點(diǎn)負(fù)載，每一條鏈路Q(chēng)(i,j)均考慮了正反向的鏈路狀況，為正反鏈路質(zhì)量之和(即系統(tǒng)路由決定于節(jié)點(diǎn)間的雙向鏈路)。此處的鏈路質(zhì)量并非節(jié)點(diǎn)間真實(shí)的鏈路質(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。

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

3 組播路由算法

3.1 算法思想

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

(1) 求出滿(mǎn)足約束條件下代價(jià)最小的組播樹(shù)；

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

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

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

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

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

3.3 算法描述

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

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

算法具體步驟如下：

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

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

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

圖3 合并中繼算法流程圖

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

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

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

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

3.4 應(yīng)用實(shí)例

網(wǎng)絡(luò)拓?fù)洌涸垂?jié)點(diǎn)S，目的節(jié)點(diǎn)C、D、E、F、G。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖如圖4所示。

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

通過(guò)Dijkstra最短路徑算法求得的最短路由樹(shù)如圖5所示。

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

算法詳細(xì)步驟：

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

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

(3)n=G，因?yàn)镃ov(G)={E，F(xiàn)}，覆蓋目的節(jié)點(diǎn)個(gè)數(shù)最大，Aux={D，G}；V={B，C，D，E}；MF={G}；

(4)Aux中所有節(jié)點(diǎn)覆蓋目的節(jié)點(diǎn)個(gè)數(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é)點(diǎn)，B為中繼節(jié)點(diǎn)，D，G為中繼或目的節(jié)點(diǎn)，C，E，F(xiàn)為目的節(jié)點(diǎn)。

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

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

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

4 仿真測(cè)試

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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