一種基于Dijkstra算法的航空平臺組網技術

李德銀，王勝海

(解放軍92728部隊，上海 200436)

隨著航空兵部隊日常訓練水平的提升，對飛機進行全狀態(tài)安全監(jiān)控的需求日益增強。為了實現對空中飛機狀態(tài)的實時監(jiān)控，需要建立一個地空-空空高速實時無線傳輸網絡，將飛行參數實時下傳。但是，在飛機超低空和超視距飛行過程中，傳統(tǒng)單一的TDMA網絡難以滿足無盲區(qū)通信需求，本文研究一種基于Dijkstra算法的Ad Hoc組網技術，以實現動態(tài)路由和數據中繼轉發(fā)功能，增加網絡容量，提高網絡覆蓋范圍和實時性。

1 Ad Hoc組網設計

Ad Hoc網絡［1-2］是由一組無線移動節(jié)點組成的特殊分布式無線移動通信系統(tǒng)，是一種能夠迅速展開使用的網絡體系，其所有節(jié)點的地位平等，無需設置任何中心控制點;節(jié)點通過分層的網絡協(xié)議和分布式算法相互協(xié)調，實現網絡的自動組織和運行，可以動態(tài)地、隨意地、頻繁地進入和離開網絡，一般不需要事先預警，且不會影響網絡中其它節(jié)點的通信;網絡中通信的源節(jié)點和目的節(jié)點不在直接通信范圍之內時，可以經過多個中間節(jié)點轉發(fā)，即報文可以經過多跳(Hop)到達目的地。因此，Ad Hoc網絡被稱為移動自組織對等多跳網絡。Ad Hoc網絡中的每個移動節(jié)點都具有路由器和主機兩種功能。作為路由器，節(jié)點需要運行相應的路由協(xié)議，根據路由表參與分組轉發(fā)和路由維護工作;而作為主機，節(jié)點需要運行面向用戶的應用程序。

飛行參數實時下傳網絡通信方案中，每個空中平臺配置一套機載通信終端，每個機載通信終端建立一張鄰居信息表，機載通信終端通過周期性的廣播路由來更新鄰居信息表，地面中心站根據接收到的鄰居信息，生成子網的拓撲表，在這個子網的拓撲結構上利用Dijkstra算法計算出每個節(jié)點到組網內其他節(jié)點的最短路徑，即路由。得出路由表后，地面中心站需為每個機載通信終端分配資源，然后將路由表以及資源分配情況通過路由信令廣播給各個機載通信終端，從而實現各個節(jié)點直接的數據傳輸。最后采用路由維護協(xié)議來更新路由以應對網絡拓撲結構的變化，保證變化后的節(jié)點之間能正常通信，滿足大范圍無盲區(qū)通信需求。

2 網絡路由的建立

2.1 鄰居信息表

機載通信終端需要建立一個鄰居信息表［3］，如圖1所示。該信息表存儲了對應每個鄰居的記錄，每一條記錄為＜鄰居節(jié)點地址、下兩跳鄰居節(jié)點地址、跳數、該信息記錄的有效時間＞。在機載通信終端初始化的時候，鄰居信息表為空。機載通信終端通過周期性的廣播路由來更新鄰居信息表。

機載通信終端維護的鄰居信息表中的表項均在一定時間內有效，若存在超過有效時間的表項，機載通信 終端需要刪除該表項。

圖1 鄰居信息表

2.2 網絡拓撲表

地面中心站維持一張網絡拓撲表，用于描述網絡拓撲，計算路由。拓撲表包含三個部分:目的地址，到達目的地址所經過的中間節(jié)點的地址，表項有效時間。拓撲表中目的地址域保存所要到達的目的節(jié)點的地址，可以有多個表項具有相同的目的地址。表項有效時間用于表示該表項生存時間，超過生存時間的表項不能用于路由計算，必須刪除。

2.3 鄰居信息廣播通告

鄰居信息廣播通告是機載通信終端通過周期性的發(fā)送鄰居信息廣播來實現的，在機載通信終端發(fā)送鄰居信息廣播時，以鄰居信息為消息進行泛洪廣播更新鄰居信息表。

鄰居信息廣播消息不能被轉發(fā)，只能在一跳范圍內發(fā)送。假設機載A收到機載B發(fā)來的路由廣播，在更新鄰居信息表時算法步驟如下。

步驟1):對于B中的每一條鄰居記錄，若跳數大于3，則刪除;否則，將下一跳節(jié)點值賦給下下一跳節(jié)點值，同時下一跳節(jié)點值修改為B，跳數加1，其余不變。檢查A中是否有到達目的節(jié)點為B的鄰居記錄，若不存在，則在A中添加一條到B的鄰居記錄，其目的節(jié)點為B，下一跳為 B，下下一跳為空(NULL)，跳數加1。然后轉步驟2)。

步驟2):對于修改后的B中的每一條記錄，先檢查在A中是否存在一條記錄使得這2條記錄的目的節(jié)點一樣，若不存在，則增加該記錄到A中，若存在，則轉步驟3)。

步驟3):比較這2條記錄的下一跳地址是否一樣，若不一樣，則將該記錄添加到A中，否則，轉步驟4)。

步驟4):將A中的記錄替換成序列號最新的那條路由記錄。直到所有的鄰居記錄都更新完畢。

2.4 路由的建立

地面中心站根據接收到的鄰居信息，生成子網的拓撲表，用于描述當前時刻的網絡拓撲結構，拓撲表由目的節(jié)點、跳數、到達目的節(jié)點所經過的中間節(jié)點(包括源節(jié)點以及目的節(jié)點)組成。在這個拓撲結構上，可利用帶權有向圖上的Dijkstra算法計算出每個源點到其余各頂點的最短路徑，即路由。地面中心站可以對任兩個相鄰的節(jié)點設置一個權重函數，權重函數可以根據不同的需求對鏈路寬帶、時延、節(jié)點的能量等選擇適當的權重來表示各路徑的長短。

由于Ad Hoc網絡的特點可見，一條路由的穩(wěn)定性依賴于許多因素，這些因素有些是相互聯(lián)系或相互制約的，所以很難選擇出一條具有絕對穩(wěn)定性的路由。而且，除穩(wěn)定性外，路由協(xié)議還必須考慮路由延遲、吞吐量等。在選擇路由的時候，不可能將所有的因素都考慮在內，在設置權重函數時各權重因子之和必須為1。

地面中心站根據路由表為機載通信終端分配資源，保證轉發(fā)節(jié)點有足夠的資源轉發(fā)業(yè)務數據。地面中心站需要將路由表以及資源分配情況通過路由信令廣播給各個機載通信終端。機載通信終端需要記錄路由及資源配置信息，并轉發(fā)該路由信令，保證子網內所有機載通信終端都能收到路由信令。

在圖2中，機載1、機載2、機載3分別廣播鄰居信息表，中心站收到這3個機載廣播的鄰居信息表后，便可生成子網的拓撲表。如中心站收到機載3廣播的鄰居信息表中的＜機載7、機載5、機載6、機載3＞這條記錄后，可得出中心站→機載3→機載5→機載6→機載7這樣一條拓撲信息。

2.5 路由維護

網絡中的每個節(jié)點通過周期性地與鄰居節(jié)點交換鄰居信息表來維持整個網絡的路由信息，也可根據網絡拓撲的變化來觸發(fā)路由的更新。路由表是基于本地鄰居和本地拓撲表計算的，因此，一旦這兩個表出現任何變化，都需要觸發(fā)路由的更新，重新計算路由表，準確地說，如果鄰居節(jié)點集、拓撲表中任何一個出現變化，都需要重新計算路由表，更具體地說，鄰居節(jié)點增加或減少，三跳鄰居節(jié)點的增減，拓撲表中記錄的增減，都將導致重新計算路由表。

3 Dijkstra算法及應用

Dijkstra算法主要是解決帶權有向圖上的單源點的最短路徑問題［4］，該算法是一個按路徑長度遞增的次序產生最短路徑的算法。在路由表的建立過程中可以使用該算法得出各節(jié)點到其它節(jié)點的路由信息。

首先，引進一個輔助向量D，D的每個分量D［i］表示當前所找到的從始點v到每個終點Vi的最短路徑的長度。D的初態(tài)為:若從v到Vi有弧，則D［i］為弧上的圈值;否則置 D［i］為 ∞。顯然，長度為 D［j］=Min{D［i］}(其中Vi屬于V)的路徑就是從v出發(fā)的長度最短的一條最短路徑，此路徑為(v，Vi)。

在一般情況下，下一跳長度次短的最短路徑的長度必是

D［j］=Min{D［i］}(Vi屬于(V － S))，其中，D［i］或者是弧(v，Vi)上的權值，或者是D［k］(Vk屬于S)和弧(Vk，Vi)上的權值之和。

Dijkstra算法描述如下(假設共有n個節(jié)點):

1)假設用帶權的鄰接矩陣arcs來表示帶權有向圖，arcs［i］［j］表示弧(Vi，Vj)上的權值。若(Vi，Vj)不存在，則置arcs［i］［j］為∞(在計算機上可用允許的最大值代替)。N為已找到的從v出發(fā)的最短路徑的終點的集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(終點)Vi可能到達到的最短路徑長度的初值為

D［i］=arcs［Locate Vex(G，v)］［i］Vi屬于 V;

2)選擇Vj，使得 D［j］=Min{D［i］}，Vi屬于V － N;

Vj就是從v出發(fā)的最段路徑的終點。令N=N∪{j};

3)修改從v出發(fā)到集合V－N上任一頂點Vk可達的最短路徑長度。如果 D［J］+arcs［j］［k］＜ D［k］，則修改 D［k］為 D［k］=D［j］+arcs［j］［k］;

4)重復操作2)、3)共n－1次，由此求得從v到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。

本文以圖3為例討論這種算法在圖2中心站的拓撲表中的運用，即尋找源節(jié)點到網絡中其他各節(jié)點的最短路徑，為方便起見，設源節(jié)點(中心站)為節(jié)點0，然后一步步尋找源節(jié)點到其余各個節(jié)點(航空平臺)的最短路徑，直到把所有的節(jié)點都找到為止。其中圖3中兩節(jié)點之間連接線上的數字為權重。

表1是對圖3網絡進行求解的詳細步驟，可以看出，上述的步驟2)、3)共執(zhí)行了7次，表中帶圈的數據時在每次執(zhí)行時所尋找到的具有最小值的D(w)值，當第7次執(zhí)行步驟2)、3)并得出了結果后，所有網絡節(jié)點都包含在N中，整個算法結束。

圖3 對應圖2中網絡拓撲結構Dijkstra算法運用

節(jié)點0為源節(jié)點，因此一開始在集合N為N={0}，因為節(jié)點0和節(jié)點1、節(jié)點2、節(jié)點3相連，故在初始化時，在D(1)、D(2)、D(3)中為節(jié)點0到這些節(jié)點的距離，而 D(4)、D(5)、D(6)、D(7)為∞。

在節(jié)點0以外的節(jié)點中，找出一個距離節(jié)點0最近的節(jié)點 w，即節(jié)點1，因為在 D(1)、D(2)、D(3)中，D(1)、D(3)最小。因此不妨將節(jié)點1加入到集合N中，這時N={0，1}，這時在步驟1)這一行和D(1)這一列下寫入，表示節(jié)點1到節(jié)點0的距離為1，并且節(jié)點1在這個步驟中加入到集合N中了。

表1 計算節(jié)點1的最短路徑步驟

接著就要對所有不在集合中的節(jié)點逐個執(zhí)行。

對于節(jié)點2，原來的D(2)=2，因此節(jié)點2到節(jié)點1距離不變，仍為2;

對于節(jié)點3，原來的D(3)=1，因此節(jié)點3到節(jié)點0距離不變，仍為1;

對于節(jié)點4，到節(jié)點1的距離仍為∞;

圖4 最短路徑的生成步驟

對于節(jié)點5，到節(jié)點1的距離仍為∞;

對于節(jié)點6，到節(jié)點1的距離仍為∞;

對于節(jié)點7，到節(jié)點1的距離仍為∞。

在節(jié)點0和節(jié)點1以外的節(jié)點中，找出距節(jié)點0最近的節(jié)點，即節(jié)點3，將其添加到集合N中。以此循環(huán)，直到所有節(jié)點集合N不再變化為止。

最后就得出以節(jié)點0為根的最短路徑樹。圖4給出了各個步驟執(zhí)行后的結果。從最短路徑樹可以清楚地找出從源節(jié)點0到組網內任何節(jié)點的最短路徑，即路由信息。

4 工程應用

本文針對飛行參數實時下傳的用戶需求，工程中建立地空-空空高速實時無線傳輸網絡，以單地面中心站配置方式，機載電臺直接與中心站進行通信，其應用場景如圖5所示，機載電臺采集的數據通過天線發(fā)送到無線信道，與地面站和其他機載電臺共同構成無線通信網絡，實時地將飛行數據傳輸至地面顯控臺。通過多架次的實際試飛驗證(包括超低空和超視距飛行)，統(tǒng)計了能夠表明網絡運行情況的數據丟包率(見表2)，共統(tǒng)計10個飛行架次，丟包率最低0.03%，最高0.61%，丟包率最高時飛機作大機動、超視距飛行，采用了中繼通信方式，有中繼時由于增加了數據轉發(fā)次數從而導致丟包率增加，飛機作大機動飛行時丟包率增加，主要是因為天線安裝位置原因，飛機作大機動飛行時可能造成天線遮擋?？偟膩碚f，經試飛可以得出結論:基于Dijkstra算法Ad Hoc組網技術應用于某型飛機平臺的空中組網后，成功實現了多架飛機飛行參數的超低空和超視距中繼通信，數據丟包率低，組網通信穩(wěn)定可靠，網絡數據刷新率不低于8次/秒，帶寬不小于2M，誤碼率小于1%，系統(tǒng)延時小于1s，支持3跳以內中繼通信，能夠滿足部隊超低空和超視距飛行無盲區(qū)通信需求。

圖5 算法的工程應用

表2 空中試飛數據丟包率統(tǒng)計

5 結束語

本文針對空中平臺高速、超低空和遠距離移動等特點，提出了具有針對性的動態(tài)路由解決方案，并在部隊日常訓練中得到應用，能夠滿足飛行訓練中高速實時的可靠無線傳輸需求，有助于實現飛行過程的安全狀態(tài)監(jiān)控，為提升航空兵部隊訓練質量奠定基礎。

［1］陳林星，曾曦，曹毅.移動Ad Hoc網絡——自組織分組無線網絡技術［M］.北京:電子工業(yè)出版社，2012:3-7.

［2］廈海輪.無線AdHoc網絡MAC協(xié)議及相關技術研究［D］.北京:北京郵電大學，2007:2-3.

［3］樂陽，龔健雅.Dijkstra最短路徑算法的一種高效率實現［J］.武漢測繪科技大學學報，1999，24(3):209-211.

［4］嚴蔚敏，吳偉民.數據結構［M］.北京:清華大學出版社，1997:186-190.