史琰　楊鵬

摘要：提出了一種適用于機間自組網(wǎng)的路由協(xié)議算法，該算法使用位置信息輔助計算節(jié)點間的鏈路持續(xù)時間，并以此鏈路持續(xù)時間作為拓撲穩(wěn)定情況的預測。各節(jié)點則依據(jù)跳數(shù)最小原則和鏈路持續(xù)時間最長原則進行路由計算，并在條件允許的情況下，為網(wǎng)絡中的節(jié)點建立兩條路由。仿真結(jié)果表明，該算法能夠滿足機間自組網(wǎng)的高動態(tài)拓撲變化，提供良好的網(wǎng)絡性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

每個機間自組網(wǎng)節(jié)點在本地存儲一張拓撲表TE，用于存儲網(wǎng)絡中各節(jié)點的位置信息。該拓撲表包含參數(shù)LINK_TIME以表明相鄰節(jié)點之間的鏈路持續(xù)時間。如果節(jié)點i與節(jié)點j為鄰節(jié)點， TE[i][j].IS_VALID_FLAG = 1可以表明兩節(jié)點的鄰居關系，并且TE[i][j].LINK_TIME可以表示節(jié)點i與節(jié)點j之間的鏈路持續(xù)時間。節(jié)點通過周期性地發(fā)送HELLO包的方式來進行拓撲表的建立和維護。HELLO包中會攜帶目前本節(jié)點已知的拓撲關系及鏈路信息。

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

機間自組網(wǎng)節(jié)點通過上文所述的方法獲取網(wǎng)絡拓撲信息并更新相應的拓撲表項，然后各節(jié)點根據(jù)本地存儲的拓撲表來計算路由生成表驅(qū)動路由表。

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

（2）節(jié)點S根據(jù)各一跳節(jié)點的拓撲關系計算兩跳范圍內(nèi)的路由，如圖3所示。

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

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

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

如圖6所示，假設圖中的鏈路持續(xù)時間按其鏈路編號由大到小排列（鏈路1持續(xù)時間最長），節(jié)點S到節(jié)點A的鏈路持續(xù)時間最長且跳數(shù)最短，則節(jié)點S只為節(jié)點A建立一條優(yōu)先路由：S→A。節(jié)點S到節(jié)點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é)點S到節(jié)點j最短且持續(xù)時間最長的路由，備份路由為節(jié)點S到節(jié)點j次短但持續(xù)時間比優(yōu)先路由時間長的路由。當節(jié)點S使用優(yōu)先路由與節(jié)點j進行通信時發(fā)現(xiàn)鏈路即將斷開時，節(jié)點S切換備份路由進行通信，以此來保障節(jié)點間通信的連續(xù)性。

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

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

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

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

3 結(jié)束語

機間自組織網(wǎng)絡具有節(jié)點快速移動、拓撲變化迅速的特點，機間自組織網(wǎng)絡中的路由很大程度上受到這些特點的影響。位置信息輔助的最短路徑原則和最長鏈路持續(xù)時間原則相結(jié)合的路由算法，可以降低高動態(tài)變化的網(wǎng)絡拓撲對路由的影響。在網(wǎng)絡拓撲允許的情況下，通過使用優(yōu)先路由和備份路由的方法，保障了數(shù)據(jù)信息在節(jié)點間傳輸時不受鏈路通斷的影響。

參考文獻

[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] 韓勇， 陳強， 王建新.機載網(wǎng)絡技術綜述[J].電訊技術， 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