張步碩，呂 娜，陳柯帆，曹芳波，劉 創(chuàng)

（空軍工程大學信息與導航學院，西安 710077）

0 引言

未來航空作戰(zhàn)具有高度對抗性、高度不確定性，少量的有人或無人航空作戰(zhàn)平臺無法滿足未來信息化航空戰(zhàn)場的需要[1-3]。受自然界生物行為啟發(fā)，產生了航空集群作戰(zhàn)這一未來航空作戰(zhàn)的重要模式[4-6]。作為軍事航空通信發(fā)展的方向，航空集群網(wǎng)絡在這些需求背景下被提出。航空集群網(wǎng)絡是無線自組織網(wǎng)在航空集群應用背景下產生的具體網(wǎng)絡，無線自組織網(wǎng)絡中路由協(xié)議是影響其性能的關鍵技術，因此，路由協(xié)議也是影響航空集群網(wǎng)絡的關鍵技術[7]。航空集群網(wǎng)絡具有以下特點：網(wǎng)絡規(guī)模較大，平臺類型多樣；傳輸范圍不一，航空集群作戰(zhàn)平臺一般搭載多個數(shù)據(jù)鏈通信設備，由于數(shù)據(jù)鏈通信設備的差異，導致節(jié)點的傳輸范圍不一；針對多種作戰(zhàn)任務，任務的多樣性導致節(jié)點間需經(jīng)常性地隨機組合，節(jié)點的這種經(jīng)常性的隨機組合會導致網(wǎng)絡拓撲變化，執(zhí)行具體單一任務時，網(wǎng)絡拓撲會維持一段時間，因此，航空集群網(wǎng)絡的拓撲呈現(xiàn)出階段性變化。現(xiàn)有的平面結構路由協(xié)議不能很好地適應于航空集群網(wǎng)絡，因為平面結構路由協(xié)議可擴展性較差，適用于規(guī)模較小的無線自組網(wǎng)。對于航空集群網(wǎng)絡來說，為了適應其大規(guī)模性、提高其可擴展性，本文針對航空集群網(wǎng)絡采用分層結構路由協(xié)議。利用圖論中的連通支配集理論是解決分層路由的一種有效的方法[8]，一方面可以方便地進行網(wǎng)絡建模，另一方面將路由過程簡化到支配集形成的骨干網(wǎng)中，可以有效減小網(wǎng)絡開銷。

但是現(xiàn)有對支配集理論構造路由算法的研究很少，在航空集群環(huán)境下結合支配集理論的路由算法還沒有相關研究。

對此，本文以支配集理論為基礎，研究基于連通支配集的路由算法。

對支配集理論的研究已經(jīng)開展多年，對基于路由約束的連通支配集已經(jīng)有相關研究，文獻[9]在無向圖的基礎上提出a-moc-cds（a-Minimum rOuting Cost Connected Dominating Set），通過使用 a-2hop-DS（a-2hop-Dominating Set）解決問題，文獻[10]提出一種集中式機制解決a-moc-cds問題，針對路徑長度數(shù)不超過4的節(jié)點對使用一種集中式算法連接最短路徑構造連通支配集，并且它們證明了a-moc-cds問題為NP-難。

但是以上研究工作還存在許多不足之處：大多數(shù)的研究都基于無向圖，航空集群網(wǎng)絡由于平臺類型多樣，傳輸范圍不一，必須在有向圖中研究；都簡單考慮能耗問題，沒有考慮節(jié)點帶寬資源，與航空集群環(huán)境不符；少數(shù)基于有向圖的支配集研究在構建連通支配集過程中都沒有考慮路由約束，平均傳輸路徑較長，相應的端端時延較大。路由約束是指基于有向圖構建的支配集形成連通支配集所需的特殊條件。文獻[10]指出在構建連通支配集過程中，將節(jié)點數(shù)不超過4的支配節(jié)點連接起來作為形成連通支配集的條件。但文獻[10]僅僅考慮圖論中的支配集問題研究，并沒有將支配集理論與路由算法結合起來，也沒有考慮航空集群網(wǎng)絡中節(jié)點ID號分配的問題。文獻[11-13]考慮了一種支配集維護算法，對于航空集群網(wǎng)絡進行支配集維護具有啟發(fā)意義，但是文獻[11-13]僅在無向圖中考慮支配集維護問題，對有向圖中的研究沒有論述。

針對以上問題，本文以航空集群環(huán)境為背景，在有向圖的基礎上，考慮節(jié)點帶寬資源，構造節(jié)點權值函數(shù)，并提出一種分布式算法構建路由約束連通支配集形成骨干網(wǎng)，有效延長網(wǎng)絡生命周期，減少平均傳輸路徑，在此基礎上，構建路由約束連通支配集路由算法，并提出基于有向圖的骨干網(wǎng)維護機制，增加航空集群網(wǎng)絡的魯棒性和可擴展性。

1 網(wǎng)絡模型

航空集群網(wǎng)絡中，利用有向圖G=（V，E）描述網(wǎng)絡拓撲結構，V代表網(wǎng)絡中所有節(jié)點，E代表網(wǎng)絡中所有邊。由于網(wǎng)絡中飛行器平臺類型不一，各個節(jié)點的通信半徑不一定相同。若節(jié)點v在節(jié)點u的通信半徑內，稱u為v的入點；相反，若節(jié)點u在節(jié)點v的通信半徑內，稱v為u的入點。為方便理解，對基本概念解釋如下：

定義1支配鄰居：在有向圖G中，若節(jié)點u，v互為出入點，則稱節(jié)點u、節(jié)點v互為支配鄰居。

定義2網(wǎng)絡生命周期：網(wǎng)絡中第一個節(jié)點耗盡自身資源死亡的時間。

定義3死亡節(jié)點數(shù)：網(wǎng)絡中耗盡自身資源不能提供路由轉發(fā)的節(jié)點個數(shù)。

定義4支配集：有向圖G=（V，E），若存在節(jié)點集S，?p∈V，要么p∈S，要么與S中的某一節(jié)點互為支配鄰居，則S為支配集。

定義5支配節(jié)點：S中的節(jié)點。

定義6被支配節(jié)點：不屬于S的節(jié)點。

定義7連通支配集：對有向圖G=（V，E）。存在節(jié)點集S（S?V），如果由S導出的子圖是連通圖，且S是一個支配集，則稱S為連通支配集。

2 路由約束連通支配集路由算法

航空集群網(wǎng)絡中，構建路由約束連通支配集路由算法需要以下幾步：1）路由約束連通支配集的構建；2）支配節(jié)點路由計算；3）連通支配集維護。

為有效延長航空集群網(wǎng)絡生命周期，本文以節(jié)點帶寬資源為因子，構建權值函數(shù)，計算節(jié)點權值大小。

航空集群網(wǎng)絡中存在大型預警機或指通機這種空中樞紐，全網(wǎng)其他飛機要定時向空中樞紐回傳自身狀態(tài)及檢測到的目標信息。在執(zhí)行特定任務時，這種空中樞紐會事先對網(wǎng)絡節(jié)點進行ID號再分配，分配的依據(jù)便是通過網(wǎng)絡各節(jié)點最近一次傳回的權值大小進行權值排序，分配ID號，權值越大，節(jié)點ID號越小。

航空集群網(wǎng)絡中，帶寬資源非常緊缺，因此，必須考慮支配節(jié)點自身帶寬資源是否夠用，對此，構造節(jié)點資源權值公式，對節(jié)點進行權值計算，具體節(jié)點權值如式（1）：

其中，d（u）為節(jié)點的度；N指網(wǎng)絡的平均節(jié)點度；δ是恒大于零的常數(shù)，通常取值為0.01；Bu是節(jié)點所能提供的帶寬資源，Bthr是節(jié)點帶寬資源閾值；當所能提供資源一旦小于閾值時，權值將減小，選擇該節(jié)點的可能性就減小，W（u）值越大，表示優(yōu)先級越高。

航空集群網(wǎng)絡針對多種作戰(zhàn)任務，執(zhí)行某一作戰(zhàn)任務時，對應的網(wǎng)絡拓撲的穩(wěn)定時間可能較長，因此，基于支配集路由算法的支配集節(jié)點的生存時間應盡可能長，不同于一般網(wǎng)絡中節(jié)點號分配的隨機性，航空集群網(wǎng)絡對節(jié)點進行權值計算，根據(jù)權值大小依次對節(jié)點進行排序，盡可能選取權值大的節(jié)點作為支配節(jié)點，以有效地延長網(wǎng)絡生命周期[12-13]。

2.1 路由約束連通支配集的構建

參考文獻[10]，有以下機制和引理。

機制1：考慮一個有向圖G，和G的一個支配集C，對于任意一對 d（u，v）≤4 的節(jié)點 u，v∈C，使得滿足d（u，v）≤4的最短路徑上的所有節(jié)點加入集合S。

引理4：給定一個有向圖G=（V，E），使用機制1從G獲得的S是連通支配集。

引理4表明通過機制1構造的連通支配集是一個基于路由約束的連通支配集。

根據(jù)以上結論，可在有向圖G=（V，E）的基礎上分布式地構建路由約束連通支配集。對于任意一個節(jié)點v，用N（v）表示和v的支配鄰居集。

2.1.1 構造支配集（DS）

航空集群網(wǎng)絡中通過HELLO分組交換用以進行鄰居發(fā)現(xiàn)。為有效地選出支配集節(jié)點，對OLSR算法中HELLO分組格式進行改進，增加對節(jié)點狀態(tài)的描述，以及修改原保留字節(jié)為節(jié)點ID。具體修改如圖1所示。

圖1 修改后的HELLO分組

ID：源節(jié)點ID號；Htime：HELLO分組發(fā)送間隔；Willingness：節(jié)點愿意轉發(fā)數(shù)據(jù)的意愿程度；IType：源節(jié)點狀態(tài)，為支配節(jié)點或被支配節(jié)點；Link Code：鏈路類型，有未知鏈路、非對稱鏈路、對稱鏈路、丟失鏈路；Reserved：保留域；Link Message Size：鏈路消息的規(guī)模，即有多少該類型的鄰居地址；Neighbor interface address：鄰居地址。

支配集構造流程如下：

1）對于每一個節(jié)點依據(jù)權值大小分配不同的正整數(shù)ID，不同節(jié)點有不同的ID；

節(jié)點間通過修改后HELLO分組的交換獲得支配鄰居表 N（v）。

2）每個節(jié)點比較自己的ID和支配鄰居表N（v）中的ID，如果自己的ID比雙向鄰居表中的ID都小，改變自身的狀態(tài)為支配節(jié)點，并發(fā)送dominator消息給鄰居節(jié)點。

3）對于接收到2中消息的節(jié)點，將自身狀態(tài)改為被支配節(jié)點，并發(fā)送dominated消息給鄰居節(jié)點。

4）每個節(jié)點更新自己的支配鄰居表，刪除狀態(tài)為dominated的節(jié)點。

5）返回1），直到每個節(jié)點的狀態(tài)都是dominator或 dominated。

構造基于路由約束的連通支配集有兩步，第1步，使用以上流程構造一個支配集；第2步，連接支配集構成連通支配集。

2.1.2 構造路由約束連通支配集

1）DS中的每一個支配節(jié)點（id1）發(fā)送消息（id1）給所有的鄰居節(jié)點。

2）對每一個被支配節(jié)點（id2），如果節(jié)點id1（STEP1）在自己的支配鄰居表N（id2）中，添加自己的id2給每一個收到的ID id1，然后發(fā)送消息（id1，id2）給所有的鄰居。

3）對每一個節(jié)點。

①對STEP1所有的支配節(jié)點IDS idi，每一對支配節(jié)點 id1 和 id1'，如果 id1＜id1'，發(fā)送消息（id1'，id*，id1）給支配節(jié)點 ID id1。

② 對每一個消息（id1，id2），id0（STEP1 中的支配節(jié)點），如果 id1＜id0，發(fā)送消息給（id0，id*，id2，id1）被支配節(jié)點 ID id2；否則（id1，id2，id*，id0），發(fā)送消息到支配節(jié)點ID id0。

4）當一個被支配節(jié)點ID id2收到一個消息（id0，id*，id2，id1），發(fā)送此消息給鄰居支配節(jié)點ID id1。

5）每一個支配節(jié)點ID id1刪除只有兩個ID信息的ID分組，剩余信息組成集合M，M不等于φ，執(zhí)行下列計算：

if：支配節(jié)點ID id1有兩個相同的的信息（id0，id*，id2，id1），則刪除該信息。

else：執(zhí)行選擇（idh，id2，id1）∈M，發(fā)送消息（idh，id2，id1）到節(jié)點 ID id2，刪除所有從 idh 開始的信息。并向ID id2發(fā)送dominator消息，ID id2收到后將自身變?yōu)橹涔?jié)點。

6）如果STEP5中沒有消息通過，停止，否則，繼續(xù)轉到STEP5執(zhí)行。

7）輸出：所有的節(jié)點（dominator）組成一個基于路由約束的連通支配集。

2.2 支配節(jié)點路由計算

在構建好的支配集的基礎上，為了進一步減少網(wǎng)絡開銷，被支配節(jié)點i只需維護支配鄰居表即可，每個支配節(jié)點維護骨干網(wǎng)全網(wǎng)其他節(jié)點路由表以及一張鄰居對照表。

接下來支配節(jié)點基于骨干網(wǎng)范圍獨立選擇自身的MPR集，通過使用OLSR路由算法中的機制進一步減小網(wǎng)絡開銷。而后支配節(jié)點進行骨干網(wǎng)全網(wǎng)的路由計算，通過TC消息擴散建立拓撲，網(wǎng)絡中被支配節(jié)點收到TC消息后直接丟棄，每個支配節(jié)點維護一張骨干網(wǎng)中所有支配節(jié)點的路由表。此外，支配節(jié)點需維護一張鄰居對照表，用以知道所有被支配節(jié)點下相鄰支配節(jié)點，便于進行數(shù)據(jù)轉發(fā)。

基于路由約束的連通支配集路由算法描述如圖2，圖中深色節(jié)點表示支配節(jié)點，淺色節(jié)點為被支配節(jié)點。

圖2 路由約束連通支配集路由算法描述

2.3 連通支配集維護

在執(zhí)行特定任務時，網(wǎng)絡拓撲需要維持一段時間，在此期間，當連通支配集構成的骨干網(wǎng)中的節(jié)點由于資源不足或突然被敵方攻擊而死亡后，必須進行有效維護以確保網(wǎng)絡的暢通，因此，必須研究連通支配集維護機制。連通支配集維護機制如圖3所示。

圖3 骨干網(wǎng)維護機制

通過以上機制進行連通支配集的維護確保骨干網(wǎng)的連通性，可以有效地增加航空集群網(wǎng)絡的可擴展性和魯棒性。

3 仿真驗證

本文使用Qualnet仿真軟件，針對航空集群作戰(zhàn)的集群作戰(zhàn)特點，設定仿真參數(shù)如表1所示。

表1 不同類型飛機參數(shù)設定

死亡節(jié)點數(shù)與總數(shù)據(jù)業(yè)務的實驗結果如圖4所示。

圖4 死亡節(jié)點數(shù)與總數(shù)據(jù)業(yè)務曲線

AODV算法由于選擇最少跳為轉發(fā)路徑，導致某些節(jié)點成為關鍵節(jié)點，頻繁地完成轉發(fā)任務，致使其所能提供的帶寬資源被耗盡，無法繼續(xù)正常提供路由轉發(fā)功能，成為死亡節(jié)點，隨著業(yè)務量的增大，死亡節(jié)點數(shù)目也隨之上升。采用OLSR算法時，節(jié)點保持全網(wǎng)各節(jié)點的路由信息，發(fā)送數(shù)據(jù)時直接進行數(shù)據(jù)傳送，但還是會有部分節(jié)點作為關鍵節(jié)點而耗盡資源，死亡節(jié)點數(shù)相較于AODV差別不大。本文算法中數(shù)據(jù)轉發(fā)都在連通支配集形成的骨干網(wǎng)里進行，依據(jù)節(jié)點權值大小選取一組平均權值較大的節(jié)點作為支配節(jié)點，有效地延長網(wǎng)絡生命周期，降低了網(wǎng)絡死亡節(jié)點數(shù)，相較于以上兩種算法，死亡節(jié)點數(shù)明顯降低。

時延與總數(shù)據(jù)業(yè)務的實驗結果如圖5所示。

圖5 時延與總數(shù)據(jù)業(yè)務曲線

采用AODV算法時，節(jié)點在需要進行數(shù)據(jù)通信時，才會發(fā)起路由發(fā)現(xiàn)，因此，時延較長，采用OLSR算法時，節(jié)點始終維護到任意節(jié)點的路由信息，因此，時延相較于AODV來說有明顯優(yōu)勢，采用本文算法時，節(jié)點間需進行數(shù)據(jù)傳送時，先將數(shù)據(jù)傳送到連通支配集形成的骨干網(wǎng)中，再由骨干網(wǎng)轉發(fā)至目的節(jié)點，由于構建的是基于路由約束的連通支配集，平均路徑長度相較于現(xiàn)有的連通支配集明顯減短，相應的時延也縮短，與OLSR算法時延基本一致，相比于AODV來說時延有明顯改善。

路由開銷與總數(shù)據(jù)業(yè)務實驗結果如圖6所示。

圖6 路由開銷與總數(shù)據(jù)業(yè)務曲線

此處的路由開銷為成功發(fā)送一個數(shù)據(jù)分組需要的控制分組數(shù)，采用AODV算法時，數(shù)據(jù)在發(fā)送時才進行路由發(fā)現(xiàn)，路由開銷較小，但當業(yè)務量增大時，AODV所產生的控制流量中路由開銷隨著同時處于活動狀態(tài)的數(shù)據(jù)流數(shù)據(jù)的增加而增大；采用OLSR算法時，節(jié)點要時刻維護全網(wǎng)各節(jié)點的路由信息。因此，路由開銷較于AODV較大，但是OLSR算法中節(jié)點定期廣播路由流量，而不管有多少分組的產生，因此，路由開銷基本保持平穩(wěn)；采用本文算法時，只有支配節(jié)點須維護骨干網(wǎng)全網(wǎng)路由信息，非支配節(jié)點只需維護鄰居列表信息，因此，路由開銷相較于AODV，OLSR改善明顯。

4 結論

本文針對航空集群網(wǎng)絡提出了路由約束連通支配集路由算法，闡述了算法的相關思路，設計了節(jié)點權值函數(shù)和基于路由約束的連通支配集來減少網(wǎng)絡死亡節(jié)點數(shù)、降低端端時延及路由開銷，將本文算法與AODV、OLSR進行了對比分析，仿真結果表明，本文算法相較于AODV、OLSR路由算法對網(wǎng)絡死亡節(jié)點數(shù)、時延以及路由開銷都有明顯改善，能夠更好地適應于航空集群網(wǎng)絡。