史琰　楊鵬

摘要：提出了一種適用于機(jī)間自組網(wǎng)的路由協(xié)議算法，該算法使用位置信息輔助計(jì)算節(jié)點(diǎn)間的鏈路持續(xù)時間，并以此鏈路持續(xù)時間作為拓?fù)浞€(wěn)定情況的預(yù)測。各節(jié)點(diǎn)則依據(jù)跳數(shù)最小原則和鏈路持續(xù)時間最長原則進(jìn)行路由計(jì)算，并在條件允許的情況下，為網(wǎng)絡(luò)中的節(jié)點(diǎn)建立兩條路由。仿真結(jié)果表明，該算法能夠滿足機(jī)間自組網(wǎng)的高動態(tài)拓?fù)渥兓峁┝己玫木W(wǎng)絡(luò)性能。

關(guān)鍵詞：自組織網(wǎng)絡(luò)；鏈路持續(xù)時間；表驅(qū)動路由；多路徑路由

機(jī)間自組織網(wǎng)絡(luò)是移動Ad Hoc網(wǎng)絡(luò)（MANET）在航空通信領(lǐng)域的應(yīng)用，其基本思想是：在一定范圍內(nèi)的飛行節(jié)點(diǎn)通過互相發(fā)送控制信息、感知信息等自動地建立起一個MANET[1]。在機(jī)間自組網(wǎng)中，飛行節(jié)點(diǎn)不但作為消息的收發(fā)節(jié)點(diǎn)，同時還在網(wǎng)絡(luò)中擔(dān)當(dāng)路由器的功能，這使得機(jī)間自組網(wǎng)可以采用多跳的方式傳輸數(shù)據(jù)，擴(kuò)大網(wǎng)絡(luò)的覆蓋范圍。

機(jī)間自組網(wǎng)應(yīng)用于民航通信可為空中交通管理提供新的技術(shù)[2]，為航班提供通信保障[3]；應(yīng)用于軍航通信可發(fā)揮抗毀、協(xié)同等優(yōu)勢，提升平臺的戰(zhàn)術(shù)效能[4]。與一般的自組織網(wǎng)絡(luò)相比，機(jī)間自組網(wǎng)不但具有多跳、自組織、無中心等固有的特點(diǎn)，同時還具有節(jié)點(diǎn)分布場景廣密度低[5]、網(wǎng)絡(luò)拓?fù)涞母邉討B(tài)性[6]、信道質(zhì)量的不穩(wěn)定性[7]、網(wǎng)絡(luò)的異構(gòu)性和臨時性。

1 位置信息輔助的機(jī)間自組網(wǎng)路由

1.1 機(jī)間自組網(wǎng)路由存在的問題

由于機(jī)間自組織網(wǎng)絡(luò)具有節(jié)點(diǎn)快速移動、拓?fù)渥兓杆俚奶攸c(diǎn)。在使用以往的基于最短路徑的路由時，路由計(jì)算時只考慮了路徑的長度。這在節(jié)點(diǎn)靜止或節(jié)點(diǎn)低速移動的場景中能夠適用，但是在機(jī)間自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)的快速移動會導(dǎo)致節(jié)點(diǎn)間的無線鏈路頻繁通斷。節(jié)點(diǎn)間鏈路的持續(xù)時間已成為影響路由的重要因素：距離最短的路徑其鏈路持續(xù)時間可能很短，其在通信過程中的失效則會導(dǎo)致丟包率上升從而降低網(wǎng)絡(luò)性能；鏈路持續(xù)時間長的路徑可能增加路由的距離，加重網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載，同時會增大信息傳輸?shù)亩说蕉藭r延。為了使所設(shè)計(jì)的路由協(xié)議適應(yīng)節(jié)點(diǎn)的移動并能夠使網(wǎng)絡(luò)具有良好的性能，在路由算法中將采用最短路徑原則和最長鏈路持續(xù)時間原則相結(jié)合。

1.2 位置信息輔助的鏈路持續(xù)時間計(jì)算

如圖1所示，假設(shè)兩節(jié)點(diǎn)A和B，其中節(jié)點(diǎn)A的經(jīng)緯度分別為[（?A，θA）]，速度為[νA]，航向?yàn)閇CA]，飛行高度為[HA]；節(jié)點(diǎn)B的經(jīng)緯度分別為（[?B，θB]），速度為[νB]，航向?yàn)閇CB]，飛行高度為[HB]。以下關(guān)于角度的計(jì)算均是以正北方向?yàn)榛鶞?zhǔn)方向，節(jié)點(diǎn)B對于節(jié)點(diǎn)A的方位角為γ，兩節(jié)點(diǎn)間的航向夾角為α，節(jié)點(diǎn)A的航向與兩節(jié)點(diǎn)間連線的夾角為β，兩節(jié)點(diǎn)A、B與地球球心形成的球心角為[δAB]，節(jié)點(diǎn)間的最大通信距離為R。

根據(jù)兩節(jié)點(diǎn)的經(jīng)緯度信息，我們可以計(jì)算出兩節(jié)點(diǎn)以地球球心為頂點(diǎn)形成的角距離：

最后，通過上述計(jì)算可以得到節(jié)點(diǎn)A、B間的鏈路持續(xù)時間：

（1）當(dāng)時[νA=νB且α=0]時，如果[SR]，節(jié)點(diǎn)A和節(jié)點(diǎn)B無法通信，鏈路持續(xù)時間為0。

（2）當(dāng)[νA≠νB或α≠0]時，節(jié)點(diǎn)A和節(jié)點(diǎn)B間鏈路持續(xù)時間為：

1.3 位置信息輔助的路由算法步驟

在本算法中，節(jié)點(diǎn)內(nèi)部包含有2種類型結(jié)構(gòu)表：網(wǎng)絡(luò)拓?fù)浔鞹E和節(jié)點(diǎn)路由表RT。

每個機(jī)間自組網(wǎng)節(jié)點(diǎn)在本地存儲一張拓?fù)浔鞹E，用于存儲網(wǎng)絡(luò)中各節(jié)點(diǎn)的位置信息。該拓?fù)浔戆瑓?shù)LINK_TIME以表明相鄰節(jié)點(diǎn)之間的鏈路持續(xù)時間。如果節(jié)點(diǎn)i與節(jié)點(diǎn)j為鄰節(jié)點(diǎn)， TE[i][j].IS_VALID_FLAG = 1可以表明兩節(jié)點(diǎn)的鄰居關(guān)系，并且TE[i][j].LINK_TIME可以表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的鏈路持續(xù)時間。節(jié)點(diǎn)通過周期性地發(fā)送HELLO包的方式來進(jìn)行拓?fù)浔淼慕⒑途S護(hù)。HELLO包中會攜帶目前本節(jié)點(diǎn)已知的拓?fù)潢P(guān)系及鏈路信息。

節(jié)點(diǎn)內(nèi)部使用節(jié)點(diǎn)路由表RT記錄到達(dá)其他節(jié)點(diǎn)的路由，并且在條件允許的情況下，為網(wǎng)絡(luò)中的節(jié)點(diǎn)建立兩條路由：RT[i][0]和RT[i][1]，其中i為目的節(jié)點(diǎn)（[i]=1，2，…，N， N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量），標(biāo)志0為優(yōu)先路由，標(biāo)志1為備份路由。與網(wǎng)絡(luò)拓?fù)浔鞹E類似，RT[i][0].IS_VALID_FLAG =1表明該路由表項(xiàng)有效，RT[i][0].PATH_TIME記錄該路由路徑的持續(xù)時間。

機(jī)間自組網(wǎng)節(jié)點(diǎn)通過上文所述的方法獲取網(wǎng)絡(luò)拓?fù)湫畔⒉⒏孪鄳?yīng)的拓?fù)浔眄?xiàng)，然后各節(jié)點(diǎn)根據(jù)本地存儲的拓?fù)浔韥碛?jì)算路由生成表驅(qū)動路由表。

（1） 假設(shè)本地節(jié)點(diǎn)為S，節(jié)點(diǎn)S首先初始化本地路由表RT[i][j].IS_VALID_FLAG = 0 （[i]=1，2，…，N， j =0，1）；然后節(jié)點(diǎn)S再查找拓?fù)浔鞹E內(nèi)所有與自己為鄰居的節(jié)點(diǎn)，即TE[S][j].IS_VALID_FLAG = 1，（j =1，2，…，N），如果存在就更新節(jié)點(diǎn)j對應(yīng)的路由表表項(xiàng)，并記錄其與節(jié)點(diǎn)j之間的鏈路持續(xù)時間、距離、下一跳。如圖2所示，節(jié)點(diǎn)S根據(jù)本地的拓?fù)浔頌橄噜彽墓?jié)點(diǎn)生成路由表，圖中節(jié)點(diǎn)S首先生成到節(jié)點(diǎn)A和節(jié)點(diǎn)B的路由。

（2）節(jié)點(diǎn)S根據(jù)各一跳節(jié)點(diǎn)的拓?fù)潢P(guān)系計(jì)算兩跳范圍內(nèi)的路由，如圖3所示。

（3）節(jié)點(diǎn)S根據(jù)兩跳節(jié)點(diǎn)的拓?fù)潢P(guān)系繼續(xù)計(jì)算，并按照跳數(shù)的增加逐步擴(kuò)散出去，直至到所有節(jié)點(diǎn)的路由都被計(jì)算出來。如圖4所示，節(jié)點(diǎn)S根據(jù)本地的拓?fù)浔碇泄?jié)點(diǎn)A和節(jié)點(diǎn)B的鄰居關(guān)系生成兩跳范圍內(nèi)的路由表，圖中節(jié)點(diǎn)S通過節(jié)點(diǎn)A可以計(jì)算出兩條跳數(shù)為兩跳的路由，其中一條到節(jié)點(diǎn)C，另一條到節(jié)點(diǎn)D，同理節(jié)點(diǎn)S根據(jù)節(jié)點(diǎn)B的鄰居關(guān)系計(jì)算到節(jié)點(diǎn)C的跳數(shù)為兩跳的路由。由圖中還可以看出節(jié)點(diǎn)S為節(jié)點(diǎn)C建立了兩條路由，S到C的路由：優(yōu)先路由為S→B→C，備份路由為S→A→D→C。

（4）在節(jié)點(diǎn)S計(jì)算路由表時，可能會出現(xiàn)節(jié)點(diǎn)S到某一節(jié)點(diǎn)j有多條路由，此時節(jié)點(diǎn)S依照圖5所示原則對計(jì)算出的多條路由進(jìn)行處理：

首先，節(jié)點(diǎn)S從計(jì)算出到節(jié)點(diǎn)j的多條路由中選擇跳數(shù)最短的路由，當(dāng)同時存在多條跳數(shù)最短的路由時，選擇其中持續(xù)時間最長的路由作為優(yōu)先路由，并將路由表項(xiàng)RT[j][0]按照上文所述方法更新；其次，當(dāng)?shù)焦?jié)點(diǎn)j存在其他跳數(shù)次短但持續(xù)時間比優(yōu)先路由時間長的路由時，將這條路由作為備份路由并更新路由表項(xiàng)RT[j][1]，同樣當(dāng)存在多條跳數(shù)次短的路由時，選擇其中持續(xù)時間最長的路由作為備份路由。

如圖6所示，假設(shè)圖中的鏈路持續(xù)時間按其鏈路編號由大到小排列（鏈路1持續(xù)時間最長），節(jié)點(diǎn)S到節(jié)點(diǎn)A的鏈路持續(xù)時間最長且跳數(shù)最短，則節(jié)點(diǎn)S只為節(jié)點(diǎn)A建立一條優(yōu)先路由：S→A。節(jié)點(diǎn)S到節(jié)點(diǎn)C的兩條路由分別為：優(yōu)先路由為S→B→C，備份路由為S→A→D→C。如圖中所示，雖然鏈路S→A→C同樣是兩跳，但是由于其與鏈路S→B→C跳數(shù)相同且鏈路持續(xù)時間比S→B→C短，所以舍棄鏈路S→A→C。

總而言之，優(yōu)先路由為節(jié)點(diǎn)S到節(jié)點(diǎn)j最短且持續(xù)時間最長的路由，備份路由為節(jié)點(diǎn)S到節(jié)點(diǎn)j次短但持續(xù)時間比優(yōu)先路由時間長的路由。當(dāng)節(jié)點(diǎn)S使用優(yōu)先路由與節(jié)點(diǎn)j進(jìn)行通信時發(fā)現(xiàn)鏈路即將斷開時，節(jié)點(diǎn)S切換備份路由進(jìn)行通信，以此來保障節(jié)點(diǎn)間通信的連續(xù)性。

2 位置信息輔助的路由算法仿真結(jié)果

仿真軟件使用OPNET14.5，其中各參數(shù)設(shè)置如表1所示。

仿真中媒體接入控制層（MAC）采用時分多址（TDMA）的形式。時隙長度為2 ms，其中1 ms為發(fā)送數(shù)據(jù)，1 ms為保護(hù)間隔。時隙沒有空間上的復(fù)用，節(jié)點(diǎn)發(fā)送周期為32 ms。物理層采用全向天線，信道速率為50 Mbit/s。節(jié)點(diǎn)每時隙內(nèi)發(fā)送數(shù)據(jù)量上限為50 kbit，發(fā)送周期為32 ms。MAC層的發(fā)送速率上限為1.5625 Mbit/s。

圖7仿真結(jié)果是在節(jié)點(diǎn)的移動速度固定為220 m/s，分組產(chǎn)生速率分別為10、20、30、40、70、100、130個/秒/節(jié)點(diǎn)，而MAC層緩存隊(duì)列長度為1 000 pk下進(jìn)行的。圖7（a）為網(wǎng)絡(luò)平均端到端時延，隨著網(wǎng)絡(luò)負(fù)載的增加，分組平均端到端時延由0.03 s增加到11.62 s；圖7（b）為網(wǎng)絡(luò)吞吐量與網(wǎng)絡(luò)負(fù)載之間的關(guān)系，圖7（c）為網(wǎng)絡(luò)丟包率與網(wǎng)絡(luò)負(fù)載的關(guān)系，由這兩幅圖可以看出隨著負(fù)載的增加網(wǎng)絡(luò)吞吐量逐漸增加并趨于穩(wěn)定在10 Mbit/s，而網(wǎng)絡(luò)丟包率增加到59%；由圖7（d）為節(jié)點(diǎn)MAC層的傳輸能力統(tǒng)計(jì)曲線，可以看出網(wǎng)絡(luò)中每個節(jié)點(diǎn)的MAC層均達(dá)到了其傳輸能力的上限，因此限制了網(wǎng)絡(luò)性能的提升。

3 結(jié)束語

機(jī)間自組織網(wǎng)絡(luò)具有節(jié)點(diǎn)快速移動、拓?fù)渥兓杆俚奶攸c(diǎn)，機(jī)間自組織網(wǎng)絡(luò)中的路由很大程度上受到這些特點(diǎn)的影響。位置信息輔助的最短路徑原則和最長鏈路持續(xù)時間原則相結(jié)合的路由算法，可以降低高動態(tài)變化的網(wǎng)絡(luò)拓?fù)鋵β酚傻挠绊?。在網(wǎng)絡(luò)拓?fù)湓试S的情況下，通過使用優(yōu)先路由和備份路由的方法，保障了數(shù)據(jù)信息在節(jié)點(diǎn)間傳輸時不受鏈路通斷的影響。

參考文獻(xiàn)

[1] EHSSN S， ABBAS J. The Global in-Flight Internet [J]. IEEE Journal on Selected Areas in Communications， 2006， 24（9）： 1748-1757

[2] MAGGIE X C. Connectivity of Ad Hoc Networks for Advanced Air Traffic Management [J]. Journal of Aerospace Computing， Information and Communication， 2004， 1（5）： 225-238

[3] HU D T， SHIGERU S. A Proposal of Relaying Data in Aeronautical Communication for Oceanic Flight Routes Employing Mobile Ad Hoc Network[C]// 2009 First Asian Conference on Intelligent Information and Database Systems， Washington DC， USA， 2009

[4] 韓勇， 陳強(qiáng)， 王建新.機(jī)載網(wǎng)絡(luò)技術(shù)綜述[J].電訊技術(shù)， 2008，48（8）：111-114

[5] YANG W. Fundamental Issues in Systematic Design of Airborne Networks for Aviation[C]//IEEE Aerospace Conference， 2006

[6] JUSTIN P R， ABDUL J， EGEMEN K C， et al. High-Dynamic Cross-Layered Aeronautical Network Architecture [J]. Aerospace & Electronic Systems IEEE Transactions on， 2011， 47（4）：2742-2765

[7] ERIK H. Aeronautical channel modeling [J]. IEEE Transactions on Vehicular Technology， 2002， 51（2）： 254-264.doi： 10.1109/25.994803