李德銀，王勝海

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

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

1 Ad Hoc組網(wǎng)設(shè)計(jì)

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

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

2 網(wǎng)絡(luò)路由的建立

2.1 鄰居信息表

機(jī)載通信終端需要建立一個(gè)鄰居信息表［3］，如圖1所示。該信息表存儲(chǔ)了對(duì)應(yīng)每個(gè)鄰居的記錄，每一條記錄為＜鄰居節(jié)點(diǎn)地址、下兩跳鄰居節(jié)點(diǎn)地址、跳數(shù)、該信息記錄的有效時(shí)間＞。在機(jī)載通信終端初始化的時(shí)候，鄰居信息表為空。機(jī)載通信終端通過(guò)周期性的廣播路由來(lái)更新鄰居信息表。

機(jī)載通信終端維護(hù)的鄰居信息表中的表項(xiàng)均在一定時(shí)間內(nèi)有效，若存在超過(guò)有效時(shí)間的表項(xiàng)，機(jī)載通信 終端需要?jiǎng)h除該表項(xiàng)。

圖1 鄰居信息表

2.2 網(wǎng)絡(luò)拓?fù)浔?/h3>

地面中心站維持一張網(wǎng)絡(luò)拓?fù)浔恚糜诿枋鼍W(wǎng)絡(luò)拓?fù)洌?jì)算路由。拓?fù)浔戆齻€(gè)部分:目的地址，到達(dá)目的地址所經(jīng)過(guò)的中間節(jié)點(diǎn)的地址，表項(xiàng)有效時(shí)間。拓?fù)浔碇心康牡刂酚虮４嫠竭_(dá)的目的節(jié)點(diǎn)的地址，可以有多個(gè)表項(xiàng)具有相同的目的地址。表項(xiàng)有效時(shí)間用于表示該表項(xiàng)生存時(shí)間，超過(guò)生存時(shí)間的表項(xiàng)不能用于路由計(jì)算，必須刪除。

2.3 鄰居信息廣播通告

鄰居信息廣播通告是機(jī)載通信終端通過(guò)周期性的發(fā)送鄰居信息廣播來(lái)實(shí)現(xiàn)的，在機(jī)載通信終端發(fā)送鄰居信息廣播時(shí)，以鄰居信息為消息進(jìn)行泛洪廣播更新鄰居信息表。

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

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

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

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

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

2.4 路由的建立

地面中心站根據(jù)接收到的鄰居信息，生成子網(wǎng)的拓?fù)浔?，用于描述?dāng)前時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，拓?fù)浔碛赡康墓?jié)點(diǎn)、跳數(shù)、到達(dá)目的節(jié)點(diǎn)所經(jīng)過(guò)的中間節(jié)點(diǎn)(包括源節(jié)點(diǎn)以及目的節(jié)點(diǎn))組成。在這個(gè)拓?fù)浣Y(jié)構(gòu)上，可利用帶權(quán)有向圖上的Dijkstra算法計(jì)算出每個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑，即路由。地面中心站可以對(duì)任兩個(gè)相鄰的節(jié)點(diǎn)設(shè)置一個(gè)權(quán)重函數(shù)，權(quán)重函數(shù)可以根據(jù)不同的需求對(duì)鏈路寬帶、時(shí)延、節(jié)點(diǎn)的能量等選擇適當(dāng)?shù)臋?quán)重來(lái)表示各路徑的長(zhǎng)短。

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

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

在圖2中，機(jī)載1、機(jī)載2、機(jī)載3分別廣播鄰居信息表，中心站收到這3個(gè)機(jī)載廣播的鄰居信息表后，便可生成子網(wǎng)的拓?fù)浔怼Ｈ缰行恼臼盏綑C(jī)載3廣播的鄰居信息表中的＜機(jī)載7、機(jī)載5、機(jī)載6、機(jī)載3＞這條記錄后，可得出中心站→機(jī)載3→機(jī)載5→機(jī)載6→機(jī)載7這樣一條拓?fù)湫畔ⅰ?/p>

2.5 路由維護(hù)

網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)通過(guò)周期性地與鄰居節(jié)點(diǎn)交換鄰居信息表來(lái)維持整個(gè)網(wǎng)絡(luò)的路由信息，也可根據(jù)網(wǎng)絡(luò)拓?fù)涞淖兓瘉?lái)觸發(fā)路由的更新。路由表是基于本地鄰居和本地拓?fù)浔碛?jì)算的，因此，一旦這兩個(gè)表出現(xiàn)任何變化，都需要觸發(fā)路由的更新，重新計(jì)算路由表，準(zhǔn)確地說(shuō)，如果鄰居節(jié)點(diǎn)集、拓?fù)浔碇腥魏我粋€(gè)出現(xiàn)變化，都需要重新計(jì)算路由表，更具體地說(shuō)，鄰居節(jié)點(diǎn)增加或減少，三跳鄰居節(jié)點(diǎn)的增減，拓?fù)浔碇杏涗浀脑鰷p，都將導(dǎo)致重新計(jì)算路由表。

3 Dijkstra算法及應(yīng)用

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

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

在一般情況下，下一跳長(zhǎng)度次短的最短路徑的長(zhǎng)度必是

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

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

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

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

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

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

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

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

本文以圖3為例討論這種算法在圖2中心站的拓?fù)浔碇械倪\(yùn)用，即尋找源節(jié)點(diǎn)到網(wǎng)絡(luò)中其他各節(jié)點(diǎn)的最短路徑，為方便起見(jiàn)，設(shè)源節(jié)點(diǎn)(中心站)為節(jié)點(diǎn)0，然后一步步尋找源節(jié)點(diǎn)到其余各個(gè)節(jié)點(diǎn)(航空平臺(tái))的最短路徑，直到把所有的節(jié)點(diǎn)都找到為止。其中圖3中兩節(jié)點(diǎn)之間連接線上的數(shù)字為權(quán)重。

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

圖3 對(duì)應(yīng)圖2中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Dijkstra算法運(yùn)用

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

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

表1 計(jì)算節(jié)點(diǎn)1的最短路徑步驟

接著就要對(duì)所有不在集合中的節(jié)點(diǎn)逐個(gè)執(zhí)行。

對(duì)于節(jié)點(diǎn)2，原來(lái)的D(2)=2，因此節(jié)點(diǎn)2到節(jié)點(diǎn)1距離不變，仍為2;

對(duì)于節(jié)點(diǎn)3，原來(lái)的D(3)=1，因此節(jié)點(diǎn)3到節(jié)點(diǎn)0距離不變，仍為1;

對(duì)于節(jié)點(diǎn)4，到節(jié)點(diǎn)1的距離仍為∞;

圖4 最短路徑的生成步驟

對(duì)于節(jié)點(diǎn)5，到節(jié)點(diǎn)1的距離仍為∞;

對(duì)于節(jié)點(diǎn)6，到節(jié)點(diǎn)1的距離仍為∞;

對(duì)于節(jié)點(diǎn)7，到節(jié)點(diǎn)1的距離仍為∞。

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

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

4 工程應(yīng)用

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

圖5 算法的工程應(yīng)用

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

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

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

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

［2］廈海輪.無(wú)線AdHoc網(wǎng)絡(luò)MAC協(xié)議及相關(guān)技術(shù)研究［D］.北京:北京郵電大學(xué)，2007:2-3.

［3］樂(lè)陽(yáng)，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，1999，24(3):209-211.

［4］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，1997:186-190.