一種有效的空中自組織網(wǎng)絡(luò)路由算法

摘 要：介紹了空中作戰(zhàn)平臺(tái)間自組網(wǎng)概念和網(wǎng)絡(luò)組成單元，結(jié)合空中作戰(zhàn)平臺(tái)高速移動(dòng)的特點(diǎn)，給出一種適合于空中自組織網(wǎng)絡(luò)的動(dòng)態(tài)路由算法。該算法考慮節(jié)點(diǎn)間相對(duì)移動(dòng)特性，可以在高速移動(dòng)環(huán)境下保持較高的鏈路穩(wěn)定性，實(shí)現(xiàn)戰(zhàn)場(chǎng)信息的可靠傳輸。

關(guān)鍵詞：自組織網(wǎng)絡(luò)； 路由算法； 鏈路穩(wěn)定性

中圖分類(lèi)號(hào)：TP309；TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)07-2118-03



Effective routing algorithm for airborne network

DUAN Ya-jun1， WU Chang1， SHI Lei1， LI Cheng-en2

(1.College of Telecommunication Engineering， Air Force Engineering University， Xi’an 710077， China; 2.Xi’an Institute ZTE Corporation， Xi’an 710065， China)



Abstract:This paper introduced the concept of Ad hoc for the platform and the elements forming the airborne network. Considering the moving characteristic of the platform，presented a new dynamic routing algorithm. The algorithm can improve the link stability and insure the battlefield information delivering reliably.

Key words：Ad hoc network; routing algorithm; link stability



0 引言

2004年空中寬帶接入Internet開(kāi)始引起人們的關(guān)注，空中乘客希望在飛行中接入Internet（就像在地面一樣）。起初這一目標(biāo)是依賴(lài)于寬帶衛(wèi)星通信實(shí)現(xiàn)，但由于衛(wèi)星傳輸時(shí)延大并且成本高，能提供飛行中接入Internet的航空公司為數(shù)較少。雖然目前依賴(lài)衛(wèi)星通信系統(tǒng)基本可以滿足空中乘客的業(yè)務(wù)需求，但衛(wèi)星資源限制與用戶數(shù)量日益增多之間的矛盾迫使人們必須要研究除衛(wèi)星通信以外的其他通信技術(shù)。航空自組織網(wǎng)絡(luò)（aeronautical Ad hoc networks，AANET)應(yīng)運(yùn)而生，它也代表未來(lái)寬帶多媒體航空通信發(fā)展的必然趨勢(shì)。AANET是移動(dòng)自組織網(wǎng)絡(luò)思想的延伸和拓展，其移動(dòng)節(jié)點(diǎn)是空中高速飛行的飛機(jī)而不是地面低速或中速的移動(dòng)計(jì)算機(jī)或主機(jī)，這一思想使建立一個(gè)全球空中飛機(jī)互連的虛擬Internet成為可能^[1，2]。

Ad hoc由于其不需要基礎(chǔ)設(shè)施，移動(dòng)中可以通信、網(wǎng)絡(luò)快速展開(kāi)與組織、通信距離遠(yuǎn)（移動(dòng)節(jié)點(diǎn)可以通過(guò)單/多跳通信）、網(wǎng)絡(luò)抗毀性和自愈能力很強(qiáng)等特點(diǎn)非常適合于戰(zhàn)場(chǎng)通信，已成為美軍戰(zhàn)術(shù)互聯(lián)網(wǎng)的關(guān)鍵技術(shù)之一。美軍戰(zhàn)術(shù)互聯(lián)網(wǎng)中，空中作戰(zhàn)平臺(tái)之間組成的通信網(wǎng)絡(luò)稱(chēng)之為空中網(wǎng)絡(luò)，是戰(zhàn)時(shí)航空通信系統(tǒng)的重要組成部分，是獲取戰(zhàn)場(chǎng)態(tài)勢(shì)信息和指揮控制信息的重要手段。圖1和2分別給出了美軍空中Ad hoc的應(yīng)用實(shí)例及其網(wǎng)絡(luò)自愈功能演示^[3]。從圖1、2中可以看出，當(dāng)空中網(wǎng)絡(luò)的某一個(gè)節(jié)點(diǎn)被擊毀后，整個(gè)網(wǎng)絡(luò)不會(huì)發(fā)生癱瘓。通過(guò)采用Ad hoc技術(shù)，網(wǎng)絡(luò)可以快速地展開(kāi)，保障戰(zhàn)場(chǎng)信息的可靠傳輸。

1 戰(zhàn)術(shù)空中網(wǎng)絡(luò)

各種軍用飛機(jī)是構(gòu)成戰(zhàn)術(shù)空中網(wǎng)絡(luò)的基本單元，其中包括預(yù)警機(jī)、空中指揮機(jī)、戰(zhàn)斗機(jī)、直升機(jī)和無(wú)人駕駛飛機(jī)(UAV)等。戰(zhàn)術(shù)空中網(wǎng)絡(luò)包括以下四部分^[3]：

a）空中骨干網(wǎng)。預(yù)警機(jī)和空中指揮機(jī)具有相對(duì)穩(wěn)定的移動(dòng)特性，為空中網(wǎng)絡(luò)提供骨干業(yè)務(wù)。空中骨干網(wǎng)絡(luò)一般遠(yuǎn)離作戰(zhàn)區(qū)域以免受到攻擊，導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓；但又必須處于執(zhí)行作戰(zhàn)任務(wù)的戰(zhàn)斗機(jī)通信范圍之內(nèi)，以確保指揮控制和戰(zhàn)場(chǎng)態(tài)勢(shì)信息及時(shí)傳送到執(zhí)行作戰(zhàn)任務(wù)的戰(zhàn)機(jī)，提高戰(zhàn)斗機(jī)的作戰(zhàn)效能。

b）空中戰(zhàn)術(shù)邊緣子網(wǎng)。直接執(zhí)行作戰(zhàn)任務(wù)的戰(zhàn)斗機(jī)或戰(zhàn)斗機(jī)群組成空中戰(zhàn)術(shù)邊緣網(wǎng)絡(luò)，這些網(wǎng)絡(luò)節(jié)點(diǎn)之間具有相對(duì)穩(wěn)定的移動(dòng)特性，但相對(duì)于地基和海基網(wǎng)絡(luò)節(jié)點(diǎn)，具有很高的移動(dòng)性。戰(zhàn)術(shù)邊緣網(wǎng)絡(luò)利用空中骨干網(wǎng)接入戰(zhàn)術(shù)互聯(lián)網(wǎng)或全球信息柵格（global information grid，GIG）。

c）空中通信中繼子網(wǎng)。UAV是空中網(wǎng)絡(luò)與地面節(jié)點(diǎn)進(jìn)行通信的中繼節(jié)點(diǎn)，同時(shí)將傳感器獲取的ISR信息中繼到地面節(jié)點(diǎn)。UAV能為分塊網(wǎng)絡(luò)提供中繼服務(wù)增加網(wǎng)絡(luò)容量。大多數(shù)UAV上裝有紅外攝像機(jī)、雷達(dá)、攝影機(jī)，傳感器一旦感知戰(zhàn)場(chǎng)信息，將其通過(guò)網(wǎng)絡(luò)傳送至目標(biāo)接收節(jié)點(diǎn)。

d）低空子網(wǎng)。它主要由直升機(jī)和地面武器組成。直升機(jī)主要用來(lái)運(yùn)輸供給和作戰(zhàn)部隊(duì)以支持地面武器作戰(zhàn)。直升機(jī)盤(pán)旋在地基節(jié)點(diǎn)和海基節(jié)點(diǎn)上空時(shí)，快速移動(dòng)，成為地面與空中骨干網(wǎng)進(jìn)行通信的中繼節(jié)點(diǎn)。

2 路由算法描述

由空中網(wǎng)絡(luò)結(jié)構(gòu)可以歸納出其路由模型如圖3所示。鏈路穩(wěn)定性是衡量路由算法性能的主要因素之一^[4~6]。最短路徑不一定是最優(yōu)路徑。近幾年有關(guān)自組織網(wǎng)絡(luò)路由協(xié)議的研究成果眾多，如先應(yīng)式路由協(xié)議、按需路由協(xié)議、混合路由協(xié)議以及基于位置信息的路由協(xié)議等，這些路由協(xié)議在路由發(fā)現(xiàn)過(guò)程中未考慮節(jié)點(diǎn)的移動(dòng)特性。在空中網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)在路由發(fā)現(xiàn)過(guò)程中一直在移動(dòng)，節(jié)點(diǎn)移動(dòng)性是影響鏈路穩(wěn)定性的重要因素。一般用信號(hào)功率來(lái)衡量節(jié)點(diǎn)相對(duì)移動(dòng)性，但由于信號(hào)衰減尤其在下雨天氣導(dǎo)致這樣的方法不夠準(zhǔn)確。一種比較合適的方法是利用控制信息分組的Doppler頻移來(lái)預(yù)測(cè)鏈路的穩(wěn)定性和節(jié)點(diǎn)的相對(duì)穩(wěn)定性。

由空中網(wǎng)絡(luò)組成單元可見(jiàn)，網(wǎng)絡(luò)節(jié)點(diǎn)有其特殊的移動(dòng)特性和移動(dòng)模型。節(jié)點(diǎn)具有固定的航線，可看做是沒(méi)有暫停時(shí)間的偽線性快速移動(dòng)實(shí)體，且具有群組移動(dòng)特性。路由目的是保證數(shù)據(jù)能正確地從發(fā)送節(jié)點(diǎn)傳送到接收節(jié)點(diǎn)，兩個(gè)因素影響鏈路的穩(wěn)定性，分別是一條鏈路上兩個(gè)節(jié)點(diǎn)之間的相對(duì)速度和相對(duì)位置。相對(duì)速度比相對(duì)位置對(duì)鏈路穩(wěn)定性的影響要大。鏈路上的節(jié)點(diǎn)既有移動(dòng)速度也有移動(dòng)方向，群組移動(dòng)節(jié)點(diǎn)通過(guò)單跳和多跳很容易實(shí)現(xiàn)信息共享。圖4給出了最優(yōu)路徑示意圖。

為了更準(zhǔn)確地評(píng)估鏈路的穩(wěn)定性，必須要考慮靠近節(jié)點(diǎn)和遠(yuǎn)離節(jié)點(diǎn)的影響。一般而言，靠近節(jié)點(diǎn)鏈路穩(wěn)定性是遠(yuǎn)離節(jié)點(diǎn)的兩倍。與鏈路穩(wěn)定性相關(guān)的鏈路代價(jià)函數(shù)（velocity link cost，VLC）定義為

VLC=-v 如果v＜0，表示接近2v如果v＞0，表示遠(yuǎn)離（1） 

其中v表示一條路徑上兩個(gè)節(jié)點(diǎn)的相對(duì)速度。代價(jià)越小，鏈路的穩(wěn)定性越高，最優(yōu)路徑具有最小的VLC。在高速移動(dòng)環(huán)境中，多普勒頻移對(duì)鏈路穩(wěn)定性的影響比較大。與光速c相比，飛機(jī)節(jié)點(diǎn)之間的相對(duì)速度v很小，期望接收信號(hào)的頻率f與觀察到的頻率f0之間的關(guān)系為

f/f0=1+v/c（2）

從式(2)中可以看出， f/f0與節(jié)點(diǎn)間的相對(duì)移動(dòng)速度v成正比。假定所有飛機(jī)使用同一頻率f進(jìn)行通信，VLC與多普勒值（Doppler value）的關(guān)系為

Doppler value=-c(f/f0-1) (f/f0＜1)，接近2c(f/f0-1)（f/f0＞1)，遠(yuǎn)離

通過(guò)觀察節(jié)點(diǎn)對(duì)之間的多普勒頻移可以判斷鏈路的穩(wěn)定性。本文將該算法稱(chēng)為多普勒路由算法。

多普勒路由算法也是一種按需路由算法，在路由過(guò)程中考慮到節(jié)點(diǎn)的移動(dòng)性，它依賴(lài)多普勒值選擇最穩(wěn)定的路由，路由發(fā)現(xiàn)原則與其他按需路由洪泛原則相同。與DSR（dynamic source routing）協(xié)議一樣，在發(fā)送RREQ路由請(qǐng)求數(shù)據(jù)包時(shí)包含節(jié)點(diǎn)地址。多普勒路由算法適合于偽線性高速移動(dòng)節(jié)點(diǎn)（如飛機(jī)等），這些移動(dòng)節(jié)點(diǎn)間的多普勒頻移是可測(cè)量的。

該算法依賴(lài)于這樣的原則：一個(gè)節(jié)點(diǎn)從另外一些可能提供數(shù)據(jù)d的節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)d，目的節(jié)點(diǎn)不惟一，每一個(gè)可能提供數(shù)據(jù)d的節(jié)點(diǎn)形成了候選節(jié)點(diǎn)集合。多普勒路由的目的是發(fā)現(xiàn)一條足夠穩(wěn)定的路徑以保證數(shù)據(jù)完整傳輸。為了得到最穩(wěn)定的鏈路，算法考慮到不同節(jié)點(diǎn)的組合，這里也考慮非不相交路徑，這使得該算法明顯區(qū)別于以往的反應(yīng)式路由算法。反應(yīng)式路由算法僅考慮不相交路徑，通過(guò)扔掉相同請(qǐng)求數(shù)據(jù)包使相同數(shù)據(jù)包額外的洪泛減少了，僅發(fā)送具有小的Doppler value的數(shù)據(jù)包，其他的扔掉，大大減少了洪泛。

多普勒路由算法中的幾種Doppler value定義如下：a)包多普勒值（packet’s Doppler value，PDV）是指一個(gè)數(shù)據(jù)包從前一個(gè)節(jié)點(diǎn)傳輸?shù)疆?dāng)前節(jié)點(diǎn)所經(jīng)歷的多普勒頻移。b)包頭多普勒值（packer header Doppler value，PHDV），每個(gè)節(jié)點(diǎn)(包括請(qǐng)求節(jié)點(diǎn)和應(yīng)答節(jié)點(diǎn))的PHDV用PDV和PHDV值中較大者更新。c)保存在接收節(jié)點(diǎn)中的相同請(qǐng)求數(shù)據(jù)包的最小Doppler value定義為BDVSF（best Doppler value so far）。BDVSF是為了區(qū)分相同請(qǐng)求包，因此具有最小Doppler value的數(shù)據(jù)包被發(fā)送，在發(fā)送數(shù)據(jù)前，每個(gè)節(jié)點(diǎn)增加自己的地址到RREQ包的緩存中。下面通過(guò)一個(gè)例子來(lái)說(shuō)明該算法路由過(guò)程。假如飛機(jī)A上的飛行員想聽(tīng)一首歌而在本機(jī)的數(shù)據(jù)庫(kù)中沒(méi)有，這首歌將有一個(gè)ID，路由過(guò)程如下:

a）請(qǐng)求節(jié)點(diǎn)A。廣播具有ID的路由請(qǐng)求消息RREQ到所有LOS范圍內(nèi)單跳節(jié)點(diǎn)。

b)接收節(jié)點(diǎn)（RREQ路由請(qǐng)求消息重新廣播）。如果PDV＞PHDV，用PDV代替當(dāng)前PHDV；如果PHDV＜BDVSF，此時(shí)BDVSF=PHDV。

c)如果節(jié)點(diǎn)能提供這個(gè)數(shù)據(jù)，產(chǎn)生路由應(yīng)答RREP消息，否則重新廣播。如果PHDV＞BDVSF，丟棄該數(shù)據(jù)包。

d)接收節(jié)點(diǎn)(RREP路由應(yīng)答消息發(fā)送)。更新每個(gè)節(jié)點(diǎn)的PHDV，如果接收節(jié)點(diǎn)就是請(qǐng)求節(jié)點(diǎn)，將RREP保存在路由表中，否則發(fā)送到下一個(gè)節(jié)點(diǎn)。

路由請(qǐng)求節(jié)點(diǎn)A在路由表中保存所有已知的路徑，以PHDV從小到大順序排列。它選擇具有最小開(kāi)銷(xiāo)的路徑發(fā)送被請(qǐng)求的數(shù)據(jù)，如果第一條路徑失敗了，選擇第二條直到發(fā)送成功為止。

3 仿真結(jié)果

3．1 單跳場(chǎng)景仿真

為了說(shuō)明節(jié)點(diǎn)相對(duì)速度對(duì)鏈路穩(wěn)定性的影響，產(chǎn)生具有可變節(jié)點(diǎn)密度隨機(jī)場(chǎng)景^[7]：在某一確定時(shí)間段內(nèi)節(jié)點(diǎn)是單方向以固定速度移動(dòng)的，有一個(gè)請(qǐng)求節(jié)點(diǎn)，其他節(jié)點(diǎn)都是提供被請(qǐng)求數(shù)據(jù)的候選節(jié)點(diǎn)。仿真中當(dāng)有節(jié)點(diǎn)離開(kāi)請(qǐng)求節(jié)點(diǎn)LOS范圍時(shí)，有兩種路由方案：a）選擇最近節(jié)點(diǎn)路由，當(dāng)相關(guān)節(jié)點(diǎn)離開(kāi)LOS，重復(fù)。b)選擇具有最小相對(duì)移動(dòng)速度，當(dāng)相關(guān)節(jié)點(diǎn)離開(kāi)LOS，重復(fù)。

方案b)在數(shù)據(jù)取回時(shí)考慮了節(jié)點(diǎn)的相對(duì)速度，而方案a)僅選擇最短路徑，是以節(jié)點(diǎn)間的距離為尺度。下面對(duì)兩種路由方案進(jìn)行仿真，給出了鏈路穩(wěn)定性和handoff次數(shù)之間的關(guān)系，如表1所示。在某一時(shí)間段內(nèi)保持節(jié)點(diǎn)100個(gè)。

通過(guò)增加節(jié)點(diǎn)密度，觀察節(jié)點(diǎn)密度對(duì)兩種路由方案的影響，仿真結(jié)果如圖5所示。節(jié)點(diǎn)分布在100 m2范圍內(nèi)。從圖5可以看出，handoff次數(shù)與鏈路穩(wěn)定性成反比，隨著節(jié)點(diǎn)數(shù)目的增加，有更多的節(jié)點(diǎn)在路由范圍之內(nèi)。方案a)僅考慮距離最近的節(jié)點(diǎn)，而方案b)選擇與請(qǐng)求節(jié)點(diǎn)相對(duì)速度最近的節(jié)點(diǎn)進(jìn)行路由。隨著節(jié)點(diǎn)密度的增加，有更多的候選節(jié)點(diǎn)，方案b)中與請(qǐng)求節(jié)點(diǎn)相對(duì)速度更近的節(jié)點(diǎn)越多。由于這些節(jié)點(diǎn)被選擇，handoff次數(shù)減少，鏈路穩(wěn)定性增加。方案b)考慮了相對(duì)速度作為移動(dòng)性參數(shù)，路經(jīng)選擇優(yōu)于方案a)，尤其適合于節(jié)點(diǎn)密度大的情況。

3．2 多跳場(chǎng)景仿真

仿真中節(jié)點(diǎn)移動(dòng)速度為840 km/h，平均飛行時(shí)間為230 min，請(qǐng)求數(shù)據(jù)節(jié)點(diǎn)占到1%，最大跳數(shù)為6跳，在900萬(wàn)平方米的空間上有5 000個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)隨機(jī)產(chǎn)生。通信范圍在200~600 km可變，通信距離的限制主要是考慮了路徑損耗和信號(hào)衰減，但還要保證飛機(jī)之間良好的通信質(zhì)量。仿真DSR動(dòng)態(tài)源最短路徑路由協(xié)議和多普勒路由協(xié)議。表2和圖6給出了仿真結(jié)果。

從圖6可以看出，多普勒路由算法性能優(yōu)于DSR路由算法，它是以犧牲跳數(shù)和平均路徑距離為代價(jià)，但保持了較高了鏈路穩(wěn)定性。隨著通信范圍的增加，切換次數(shù)減少。

4 結(jié)束語(yǔ)

本文提出一種基于控制消息分組的多普勒頻移路由方案，仿真分析了該算法的有效性。該算法與傳統(tǒng)的自組網(wǎng)路由算法相比，具有較高的鏈路穩(wěn)定性。

參考文獻(xiàn)：

［1］JAHN A，HOLZBOCK M，MULLER M，et al. Evolution of aeronautical communications for personal and multimedia services[J].IEEE Communications Magazine，2003，41(7):36-43.

[2]SAKHAEE E，JAMALIPOUR A.The global inflight Internet[J].Journal on Selected Areas in Communication，2006，24(9):1748-1757.

[3]CANDHI M.A holistic networking perspective on mobile tactical networks for the department of the defense[C]//Proc of SDR Confe-rence，2005.

[4]CHO S，HAYES J P.Impact of mobility on connection stability in Ad hoc networks[C]//Proc of IEEE Communications Networking Conference.2005:1350-1656.

[5]BAI Fan，SADAGAPAN N，KRISHNAMACHARI B，et al. Modeling path duration distributions in MANETs and their impact on reactive routing protocols[J].IEEE Journal on Selected Areas in Communication，2004，22(7):1357-1373.

[6]SADAGOPAN N，BAI Fan，KRISHNAMACHARI B，et al.PATHS:analysis of PATH duration statistics and their impact on reactive MANET routing protocols[C]//Proc ofthe 4th ACM Mobi Hoc.Mariland:ACM，2003:245-256.

[7]SAKHAEE E，JAMALIPOUR A.AerouterTM:a graphical simulation tool for routing in aeronautical systems[C]//Proc of IEEE Wireless Communications Networking Conference.2005.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”