航空集群機載網絡Failure-Oblivious路由策略 *

呂 娜，潘 穎，朱夢圓，陳 坤，方 宇

(空軍工程大學 信息與導航學院， 陜西 西安 710077)

隨著網絡化集群作戰[1]理念在航空作戰領域的深入，受生物集群[2]啟發，航空集群[3]作為一種全新的航空作戰力量體系應運而生。航空集群在引發未來空戰樣式深刻革命[4]的同時，也給保障集群成員間通信的機載網絡[5]帶來諸多技術難題。

如圖1所示，航空集群機載網絡采用無線通信技術連接不同類型、功能各異的有人或無人空中平臺，實現了作戰平臺、指控平臺、傳感器平臺、武器平臺等各類平臺戰術信息資源網絡化，本質上是一種大規模異構數據鏈網絡[6]。由于空中平臺通信半徑有限，集群成員間通信需經過多跳轉發完成，因此路由策略是值得研究的問題。

圖1 航空集群機載網絡Fig.1 Airborne network for aeronautic swarm

航空集群機載網絡的特殊性給路由策略的研究帶來挑戰。其路由策略除了要適應多跳、自組織等機載網絡普遍特征外，還應關注航空集群機載網絡的以下特點：

1)編隊拓撲變化具有不確定性。航空集群作戰能力的涌現依賴于面向作戰任務的構型控制及演化[7]，即根據實際作戰任務需求臨時組建任務編隊。由于作戰任務突發性強，航空集群機載網絡拓撲結構變化并無明顯規律。

2)通信連通狀態具有不確定性。航空集群機載網絡節點機動性強，高速移動過程中極易超出鄰居節點電波通信覆蓋范圍，通信暫盲[8]現象時有發生。

3)鏈路通信質量具有不確定性。拒止空間復雜電磁對抗環境下，“戰爭迷霧”的存在使得航空集群機載網絡中每條鏈路均有可能受到敵方干擾機不同程度的干擾，鏈路通信質量波動較大。

上述不確定性使得路由失效成為航空集群機載網絡路由策略必須面對的挑戰之一。

為應對路由失效問題，近年來已有學者提出通過移動位置預測[9-10]及干擾感知檢測[11]等技術手段，獲取更多網絡狀態信息，提高路由策略的可靠性。但由于獲取信息需要一定的時間，并不能很好地保證路由策略的時效性。此外，航空集群機載網絡中存在諸多不確定性因素，網絡狀態信息難以被準確預測和精確感知，給上述方案的實際應用帶來困難。現有路由策略無法完全滿足航空集群機載網絡嚴苛的性能需求，如何在信息受限的不確定環境下兼顧信息傳輸實時性與可靠性，是航空集群機載網絡路由策略亟須解決的問題。

軟件定義航空集群機載網絡[12]的提出，給路由策略的研究帶來機遇。利用其集中控制功能和全網統一視圖，有助于路由策略擺脫傳統網絡分層協議棧的束縛[13]，使得全局最優路由策略的實現成為可能。從現有文獻來看，對軟件定義航空集群機載網絡路由策略的研究多集中于網絡更新[14]方面，對路由選擇算法的研究不夠充分。

基于此，在軟件定義網絡架構下，從路由選擇算法的角度，為航空集群機載網絡設計一種能兼顧實時性與可靠性的Failure-Oblivious路由策略。該策略根據控制平面提供的網絡拓撲圖為各節點對計算多條隨機路由，即使其中部分路由失效，其余未失效路由仍能保障正常通信。

1 相關研究

路由策略的關鍵在于路由選擇算法的設計[15]，路由選擇算法計算生成路由質量直接影響網絡端到端的通信質量[16]。依據路由策略所采用路由選擇算法的不同，常見的多路徑路由策略主要有以下三種：

1)最短路由策略。最短路由策略采用K條最短路由(K-Shortest Paths, KSP)[17]選擇算法進行路由決策。值得注意的是，這里的最短并不一定指實際通信距離最短，而是通信代價最低[18]，即通過定義鏈路代價函數確定拓撲圖中各邊權值，反映通信距離、跳數、時延[19]、流量[20]、擁塞程度[21]等開銷，將路由求解轉化為一個最優化問題。

此類路由策略可使某些性能指標達到最優化，但由于最優解會隨網絡參數的變化而改變，對于動態變化的網絡，路由算法往往不能及時收斂。此外，對于鏈路資源有限的網絡，采用最短路由策略會使流量相對集中地分布于最短路由“瓶頸”上，導致網絡中某些鏈路負載過重，存在加劇通信故障的風險。

2)不相交路由策略。不相交路由策略采用邊不相交路由(Edge-Disjoint Paths, EDP)[22]選擇算法或點不相交路由(Vertex-Disjoint Paths, VDP)[23]選擇算法進行路由決策。邊不相交路由選擇算法可以降低鏈路失效風險[24]，點不相交路由選擇算法可以減少單點故障的影響。

此類路由策略魯棒性較強，但嚴格不相交的約束條件提高了路由的代價下限。同時，對于某些網絡拓撲而言，并不一定能夠尋找到完全不相交的多條路由。

3)Oblivious路由策略。Oblivious路由策略也稱Demand-Oblivious路由策略[25]，采用Oblivious路由選擇算法計算路由。Oblivious路由選擇算法可在通信流量需求產生之前完成路由決策，并為網絡各節點對間規劃出多條隨機路由，具有靈活、簡潔等優勢。Oblivious路由選擇算法設計之初旨在實現負載均衡性能，其主要思想是在無法精確掌握節點間流量需求的情況下，從博弈論的層面給出能夠應對隨機突發流量的路由策略。主要分為以下兩類：

一是由Valiant等[26]提出的Valiant負載均衡(Valiant Load-Balancing， VLB)路由選擇算法。主要思想是在待通信節點對之間增設一個在全網范圍內隨機選取的中間節點，分兩步進行路由：先選擇一條以中間節點為目的節點的隨機路由，再選出從該中間節點到目的節點的隨機路由。該算法巧妙利用隨機選取的中間節點分散負載壓力，從而降低網絡擁塞[27]；但缺點是路由代價不可控，且只適用于超立方體網絡、Mesh網絡、骨干網[28]等特定結構的網絡拓撲。

二是R?cke于2002年首次提出基于層次分解樹的Oblivious路由策略[29]，可用于任意網絡拓撲結構。但其算法的求解屬于NP難度問題，無法在多項式時間內求解路由；2004年，Azar等[30]和R?cke給出了一種能夠在多項式時間內求解最佳路由的算法，但此算法需要借助橢圓算法，處理數量無窮大的約束條件方程，復雜度仍較高；2008年，R?cke[31]指出利用FRT(Fakcharoenphol, Rao and Talwar)圖嵌入算法[32]等近似算法能夠快速、高效生成隨機層次分解樹；2020年，Czerner和R?cke提出了一種能夠節約路由表存儲空間、具有高性能比的Oblivious路由策略[33]。

基于上述兩類經典Oblivious路由選擇算法，其他相關研究人員沿襲Valiant和R?cke等的研究思路，對Oblivious路由策略進行了一系列的優化改進和創新。例如，文獻[34]提出基于VLB的兩階段路由，為任意拓撲結構的網絡提供了通用Oblivious路由方案；Harrelson等[35]提出了一種改進的圖分割算法，可在多項式時間內獲取具有近乎等價通信特性的路由樹；Applegate等則提出可用有限變量線性規劃方程求解的最優化路由算法[36]，與橢圓算法相比，其運算時間、空間復雜度大大降低。

當然，Oblivious路由策略也存在一些固有缺陷。由于其不考慮路由代價，在進行路由選擇時具有一定盲目性，對于性能要求嚴苛的網絡并不適用；由于其具有較強隨機性，Oblivious路由選擇算法在運行過程中會出現路由不連通等問題，致使路由選擇算法有時會因此停滯，不得不返回上一步循環來尋找連通路徑。

新的研究表明，將流量工程與Oblivious路由策略相結合，二者優勢互補設計Semi-Oblivious路由策略，不僅可有效均衡負載[37]，還可以低開銷獲得近乎最佳的網絡性能，且能夠應對突發流量和意外的鏈路故障[38]。文獻[39]則通過深入的仿真和在SDN硬件上的部署，進一步驗證了Semi-Oblivious路由策略具有可與SWAN[40]等先進流量工程路由策略相比擬的性能。

受此啟發，既然Demand-Oblivious路由策略可以在不掌握流量需求的情況下應對隨機突發流量，那么是否也存在Failure-Oblivious路由策略，可在鏈路通斷不確定條件下應對路由失效問題？在此問題驅動下，將最短路由策略與Oblivious路由策略相結合，設計航空集群機載網絡Failure-Oblivious路由策略，以期兼顧通信實時性與可靠性。

2 Failure-Oblivious路由策略

2.1 基本思想

采用數學語言，對Failure-Oblivious路由策略(以下簡稱FOR路由策略)基本思想描述如下：

如圖2所示，對于航空集群機載網絡，若將集群成員及其間通信鏈路分別對應節點集合V和邊的集合E，則航空集群機載網絡可以用圖G(V,E)表示。記圖G中節點數目|V|=n，邊的數目|E|=m。以航空集群機載網絡中各節點為圓心、節點最大通信距離r為半徑作圓，若兩個節點vi、vj間存在可行通信鏈路，則以兩節點為端點的邊e存在。將邊e的權值定義為兩個端點間的通信距離x，據此抽象出航空集群機載網絡對應賦權連通圖G(V,E)。

圖2 網絡模型Fig.2 Network model

FOR路由策略旨在為航空集群機載網絡拓撲圖G(V,E)中每個源-目的節點對(s,t)規劃k條(k>1且k∈Z+)可行路由pi。記節點對(s,t)之間所有可行路由{p1,p2,p3,…,pk}構成路由集合Ps,t。假設Ps,t中每條路由的失效概率均為q(0

S=(1-qk)×100%

(1)

顯然，當路由數量k增加時，通信成功概率S也將增大，通信可靠性隨之提高。

現假設每條路由平均失效概率q=0.5，若要求節點對間通信成功概率S>90%，由式(1)計算知，需k≥4。因此，當輸出路由數量取k=4時，理論上可保證平臺間平均通信成功率在90%以上。

以圖3所示節點對(s,t)為例，路由策略為該節點對之間規劃的路由集合Ps,t，共含4條可行路由。值得注意的是，上述通信成功率的理論推導建立在各條路由失效為相互獨立事件的基礎上，若想實現通信成功概率在90%以上的可靠通信，路由策略需為節點對(s,t)間規劃出互不相交的4條路由。然而，可靠性與實時性之間存在矛盾，嚴格不相交的約束將不可避免地增加路由長度，因此不相交路由策略可靠性的實現是以犧牲實時性為代價換取的，并不適合應用于對實時性、可靠性要求均較高的航空集群機載網絡中。為兼顧通信實時性、可靠性，不妨將“嚴格”不相交的約束去掉，尋找長度較短且盡可能不相交的多樣化路由。

圖3 k=4路由策略示例Fig.3 An example of k=4 routing strategy

2.2 算法實現

依據2.1節所述基本思想，設計一種滿足航空集群機載網絡高實時性、高可靠性要求的路由策略——FOR路由策略。該策略算法實現分為三個階段：

階段1：采用FRT算法，將高維度的航空集群機載網絡拓撲圖G(V,E)嵌入低維度的樹形度量空間中，并使用樹形圖TG(Vt,Et)反映各節點間距離關系以及圖上最短路由等特征。

階段2：構建G(V,E)與TG(Vt,Et)的路由映射，據此為待通信節點對生成一條隨機路由。

階段3：多次重復階段1、階段2，得到多條隨機路由，從中篩選出相對最優的k條路由。

2.2.1 FRT圖嵌入

由于航空集群機載網絡規模較大，其拓撲圖屬于復雜的高維空間，給路由的計算帶來困難。通過FRT圖嵌入算法，利用更為“簡單”的低維樹形度量空間近似表示高維網絡拓撲空間，并使用樹形圖TG(Vt,Et)反映圖G各節點間距離關系以及圖上最短路由等特征，有助于快速存儲、計算路由。

定義1用有序對(V,d)表示圖G中兩點i,j間圖上距離(最短路由長度)形成的度量空間，其中d:V×V→R+,滿足

1)?i∈V,d(i,i)=0；

2)?i,j∈V,d(i,j)=d(j,i)；

3)?i,j,k∈V,d(i,j)≤d(i,k)+d(k,j)(三角不等式)；

4)當i≠j時, ?i,j∈V,d(i,j)>0。

定義2若一個度量空間可以用賦權樹形圖表示，則稱度量空間(V,d)為樹形空間。

定義3若存在映射f：V→V2使得以下公式恒成立，則稱度量空間(V2,d2)是度量空間(V,d)的一個失真度為γ的嵌入。

(2)

能夠將任意拓撲圖以低失真度嵌入樹形空間中的算法通常為NP難度。Fakcharoenphol等[32]提出一種近似算法，即FRT圖嵌入算法。FRT算法利用隨機性，能夠將任意一個含有n個節點的網絡拓撲空間G(V,d)嵌入平均失真度為O(log2n)的一簇樹形空間T(Vt,dt)中。

圖4展示了采用FRT圖嵌入算法將圖G(V,d)隨機嵌入樹形空間T(Vt,dt) 的一個示例。值得注意的是，FRT算法設計之初并非針對路由問題而設，其在對點集V進行層次聚類時是基于空間距離關系，并未關注各點間實際路由連通性關系。因此，FRT算法并不能直接應用于航空集群機載網絡路由策略中。為此，對原算法進行調整，使之拓展至圖上最短路由長度所張成的度量空間上。調整后的FRT算法用偽代碼描述，如算法1所示。

圖4 FRT圖嵌入Fig.4 FRT graph embedding

算法1 調整后的FRT算法

圖5給出了算法1的一個運行結果示例。進一步分析知，輸出樹形圖T根節點代表圖G節點全集{V}，葉子節點與單元素子集{vi}存在一一對應關系。逐層迭代嵌入實質上是將圖G中節點依據兩點間圖上最短路由長度進行層次聚類，且總是以父節點對應節點集合中編號最小的點為聚類中心，下一層聚類半徑最大值為上一層半徑的1/2，各層最大半徑依次為{2δ,U2δ-2,…,U20}，因此位于第i層同一節點集合中任意兩點間圖上最短路由長度不會超過2i。考慮通信實時性要求，由點u到點v的路由應從同時包含u、v兩點的最小公共祖先(Least Common Ancestor, LCA)對應節點集合中選取。

圖5 算法1運行示例Fig.5 An example of Algorithm 1

2.2.2 路由映射

在階段1求得樹形圖T的基礎上，為確定任意兩點間的實際路由，需進行路由映射，即：通過構建樹形圖TG(Vt,Et)與圖G(V,E)中實際路由的映射關系，據此指導待通信節點對(s,t)間路由生成。為避免傳統Oblivious路由策略采用隨機算法進行路由映射所導致的路由不連通、代價不可控等問題，FOR路由策略中采用確定性路由映射，具體步驟如下：

步驟1：點的映射mV。Vt→V將樹形圖TG節點vt映射到圖G中相應節點vi。映射mV(vt)結果為vt所表示點集中編號最小的節點(即該集合的聚類中心節點)對應原圖G中相應節點。注意：經過FRT圖嵌入后圖G節點編號被打亂重排，進行映射時應還原節點自身編號。圖6給出了點的映射示例。

圖6 點的映射示例Fig.6 An example of node mapping

步驟2：構造路由生成樹RT。經過步驟1點的映射后，將映射結果相同的點合并為一個點，即若mV(vt)=mV(ut)=vi，則將vt、ut合并，記作點vi，得到路由生成樹RT。圖7給出了路由生成樹構造示例。

圖7 路由生成樹構造示例Fig.7 An example of routing tree construction

步驟3：邊的映射mE。Ert→E*將樹形圖RT的邊ert(vi,vj)映射到圖G中對應的路由。定義映射mE(ert)結果為該邊兩個端節點在圖G中的最短路由，并用最短路由所經過邊的序列E*表示。圖8給出了邊的映射示例。

圖8 邊的映射示例Fig.8 An example of edge mapping

步驟4：確定路由。根據路由生成樹RT，確定源節點s到目的節點t在圖G中的路由。首先找到節點s、t在樹形圖RT中對應的路徑，然后將該路徑經過邊的序列Ert按照mE映射到圖G中的相應路由，最后刪去路由中的冗余環路部分，輸出源節點s到目的節點t的路由。圖9給出了確定路由的一個示例。

圖9 確定路由示例Fig.9 An example of route ascertainment

根據上述步驟，可為圖G中任意兩點確定一條無環路的連通路由。

2.2.3 篩選優質路由

對于階段1輸出的每個樹形圖TG，經階段2路由映射可得一例路由生成樹RT，從而據此確定圖G中任意兩點間路由。事實上，由于算法1中隨機置換序列π和隨機數U的不同會導致輸出樹形圖TG不同，對應路由生成樹RT也不同。通過多次循環階段1、階段2，得到多例不盡相同的RT，形成一簇RTs，據此為航空集群機載網絡各節點對間篩選出長度較短且盡量不相交的k條優質路由。

假設由RTs為航空集群機載網絡中節點對(s,t)規劃出k′條不同的路由(k′>k)，按路由長度由小到大依次排列，形成{p′1,p′2,p′3,…,p′k′}，記作路由集合P′s,t。然后根據下述方程從中篩選出k條優質路由：

MinimizeEdge_num{p1∩p2∩p3∩…∩pk}

s.t.p1,p2,p3,…,pk∈P′s,t

其中，MinimizeEdge_num{p1∩p2∩p3∩…∩pk}表示在滿足約束條件s.t.p1,p2,p3,…,pk∈P′s,t時，使得k條路由相交鏈路數目這一目標函數最小化。這樣，由上述方程可確定k條長度較短且盡量不相交的路由，構成節點對(s,t)的路由集合Ps,t={p1,p2,p3,…,pk}。

2.3 主要創新

基于以上對航空集群機載網絡路由策略基本思想和算法步驟的闡述，FOR路由策略與經典Oblivious路由策略相比，創新之處在于：

1)經典Oblivious路由策略中，各邊權重表示鏈路帶寬，以實現負載均衡性能；FOR策略中，各邊權重反映節點間通信距離，旨在保證通信時效性。

2)經典Oblivious路由策略采用隨機算法進行路由映射，會導致生成路由不連通且路由長度不可控；FOR路由策略根據樹形圖所對應最短路由進行確定性路由映射，以減少迂回路由并確保路由的連通性。

3)經典Oblivious路由策略中，生成路由即被固定，不夠靈活；FOR路由策略增設優質路由篩選機制，可根據實際需求調整輸出路由，能夠適應復雜多變的戰場環境，具有較強的靈活性、可擴展性。

此外，盡管FOR路由策略具有一定的隨機性，導致為航空集群機載網絡各節點對(s,t)間規劃的路由不一定為圖上最短路由，但可以證明，該路由策略時效性代價是存在上界的。

3 路由策略時效性分析

對于航空集群機載網絡，端到端時延反映其通信時效性，包括處理時延、排隊時延、傳輸時延和傳播時延等。其中，傳播時延是指信息在飛機間的無線空間信道上傳播所需的時間，與路由長度成正比。基于此，定量分析路由策略對傳播時延的影響，以此衡量航空集群機載網絡FOR路由策略的時效性。

3.1 理論分析

3.1.1 概率分析

事實上，由于FOR路由策略在選取聚類中心節點時具有隨機性，網絡拓撲圖G中任意節點都有可能出現在節點對(s,t)所對應的隨機路由中。現通過概率分析證明，對于航空集群機載網絡中節點對(s,t)之間的通信路由，距離兩個節點較近的節點更容易出現在FOR路由策略的隨機路由中。

定理1長度較長的路由出現的概率低于長度較短的路由。

證明：任取圖G中兩個節點a、b，設節點a、節點b與節點對(s,t)最短路由中點的距離分別為α、β(α<β)。現證明節點a具有更高的概率成為其最小共同祖先節點相應聚類中心節點。

若節點為節點對(s,t)最小共同祖先節點相應聚類中心節點，則聚類半徑需恰好使得節點對(s,t)兩個端點分離。如圖10所示，圖中紅色區域表示圖G中節點對(s,t)間最短路由長度為τ，則以聚類中心節點為端點，長度為聚類半徑的線段的另一端點應落在紅色區域內。

圖10 聚類中心節點條件分析Fig.10 Analysis of clustering center node condition

算法1中聚類半徑受到隨機數U的影響。如圖11所示，由于隨機數U在區間[1,2)內等概率選取，當距離為d的節點向目標節點對(s,t) 瞄準時，線段的另一端點將均勻且隨機地分布于區間[d,2d)內。故落在紅色區域內的概率為：

(3)

圖11 隨機數的影響分析Fig.11 Analysis of influence of random number

考慮任意兩個節點a、b，有：

(4)

由于α<β，故有Pa>Pb。因此，距離較近的節點具有更高的概率出現在兩個通信節點所對應的隨機路由中。

□

3.1.2 競爭比分析

隨著網絡節點數目的增加，FOR路由策略生成隨機路由長度具有較強的不確定性，從而影響該策略的時效性。為檢驗該路由策略的時效性，采用競爭比分析方法，以路由長度所引起的傳播時延為影響因子，定量評估路由策略的時效性。

如圖12所示，設基于最短路由算法生成的路由長度為l，依據FOR路由策略生成的k條路由平均長度為L，定義時延因子為：

(5)

顯然，總有l≤L，故γ≥1恒成立。由于輸出路由具有隨機性，考慮網絡中任意兩個節點間的路由長度，時延因子γ可視為一隨機變量。整個網絡中所有節點間路由時延因子的平均期望值E(γ)越小，即其值越接近于1，時效性越強。現計算路由策略時延因子γ的平均期望理論上界。

圖12 時延因子示意Fig.12 Schematic diagram of delay factor

設網絡拓撲圖G中任意兩點u、v間圖上最短路由長度為dG(u,v)，故：

l=dG(u,v)

(6)

設經圖嵌入后，樹形圖上兩點u、v間距離為dT(u、v)。則u,v兩點間路由平均長度滿足：

L≤dT(u,v)

(7)

因此，時延因子滿足：

(8)

由式(8)可計算時延因子上界值。

引理1在隨機嵌入每一個樹形圖T的過程中， 圖G中u、v兩點嵌入dT(u,v)的聚類中心節點w存在且唯一。

證明：假設u、v兩點之間隨機嵌入的聚類中心節點w位于樹形圖的第iw層(iw≥2)。

1)存在性。節點對(u,v)與點w的距離關系如圖13所示。由圖13知，當且僅當dG(w,u)≤βiw

(9)

圖13 節點對(u,v)與點w距離關系圖Fig.13 Distance between node w and node pair (u,v)

2)唯一性。假設存在兩個不同層級聚類中心節點，這就意味著相鄰兩層節點集合完全相同，但相鄰兩層半徑之差必定大于等于2，而圖G中邊長最小值為2，這顯然是矛盾的。故縮小為原半徑的1/2后必將產生新的集合，相鄰兩層節點集合不可能完全相同，點w唯一。

□

引理2若生成節點對(u,v)之間路由的點w位于樹形圖中第i層，則必有dT(u,v)<2i+3。

證明：樹形圖中同時包含u、v兩點的集合中層數最低的節點集合為最小共同祖先節點。如圖14所示，假設同時包含u、v兩點的最小共同祖先節點位于第i+1層，邊(u,v)在樹形圖中所對應的路徑，其實僅和u、v兩點距離2i-1U以內的點有關。又因為1≤U<2，累加可得：

(10)

圖14 節點對(u,v)與第i層某點距離關系圖Fig.14 Distance between node pair(u,v) and level i

基于上述引理，計算時延因子的平均期望值。值得注意的是，點w得以截斷節點對(u,v)的前提是：點w的標號足夠小，使得在其他距離節點對(u,v)較近的那些點之前率先掌握對于(u,v)的優先截斷權。設比點w距離(u,v)更近的點共有s-1個，也就是說，按照與(u,v)圖上距離從近到遠排序，點w排在第s名。

則有：

(11)

由三角不等式，dG(w,v)-dG(w,u)≤dG(u,v)，因此：

(12)

則期望值滿足：

(13)

右邊分式約去公約數后，得：

(14)

由調和級數展開式，得：

(15)

知其與log2n同階，故：

(16)

對于任意節點數目為n的網絡，時延因子平均上界存在，且理論期望為O(log2n)。

□

綜上所述，隨著網絡節點數目增加，時延因子并不是呈指數上升，而是呈對數級增長，這說明網絡規模的增大并不會導致時延指數爆炸式增長。

3.2 仿真分析

為進一步論證FOR路由策略時效性，評估路由策略在不同規模網絡下的實際效果，通過仿真實驗研究該策略時延因子隨網絡規模增大的變化趨勢，并在相同條件下進行時延因子變化對照實驗，將FOR路由策略與KSP、EDP路由策略相比較。

實驗在一臺CPU為Intel Core i5、主頻2.40 GHz、內存16 GB、64位操作系統的PC機上進行，算法編譯采用科學計算軟件Mathematica 12.0。利用Mathematica軟件內置函數生成節點數目為3～100的網絡，模擬不同規模的航空集群機載網絡，并分別計算三種路由策略在不同規模網絡中各節點對間路由時延因子平均值，繪制時延因子γ隨網絡節點數目n增大時的實際變化曲線，實驗結果如圖15所示。

圖15 時延因子變化曲線圖Fig.15 Delay factor curve

對比圖15中三種路由策略在不同規模網絡下的實驗結果，可知：

1) 從變化趨勢來看，隨著節點數目n的增加，FOR路由策略時延因子緩慢增大，但增長速率逐漸趨緩，呈現對數級增長趨勢，這說明網絡規模的增大不會引發FOR路由策略時延因子呈指數爆炸性增長，這與3.1.2節中時延因子理論變化趨勢相符；KSP路由策略時延因子的變化速率近似等于0，這說明KSP路由策略受網絡規模增大影響不大；EDP路由策略的時延因子則隨網絡規模增大無明顯變化規律。

2) 從波動幅度來看，本實驗中FOR路由策略時延因子的最大值小于2，波動范圍較小；KSP路由策略時延因子波動幅度并不大，基本維持在γ=1.25這一水平線上；而形成鮮明對比的是，EDP路由策略時延因子最大值超過3，隨網絡節點數目的改變有較大幅度的波動。

3) 對于同樣規模的網絡，當網絡節點數目較小時，FOR路由策略時延因子大小與KSP路由策略較為接近；當網絡節點數目較大時，FOR路由策略與EDP路由策略較為接近。因此可以推斷，FOR路由策略的時效性能介于KSP路由策略與EDP路由策略之間。

4)本實驗中時延因子最小值γ=1由FOR路由策略取得，這是因為存在一定的概率使得FOR路由策略生成的隨機路由恰好與最短路由相同；KSP路由策略選取節點對間前K條最短路由，這K條不同的路由中必然存在非最短路由，故KSP路由策略時延因子恒大于1；圖中EDP路由策略時延因子存在最低下限，則是由于其嚴格不相交的約束條件所導致的。

綜上所述，盡管FOR路由策略的時效性略差于KSP路由策略，但顯著優于EDP路由策略，且時延因子隨網絡規模的增大不會呈爆炸性增長，而是呈對數級緩慢增長，故FOR路由策略所引起的傳播時延代價上界可控。

4 路由策略魯棒性分析

4.1 理論分析

對于航空集群機載網絡，一般情況下節點失效概率遠小于鏈路失效概率。當航空集群機載網絡編隊拓撲隨作戰任務改變、通信連通狀態變化或通信鏈路質量波動時，均可能導致其鏈路失效，從而引發路由失效。由于航空集群機載網絡面臨諸多不確定性因素，鏈路失效在整個網絡中分布將呈現隨機性。

若將鏈路隨機失效視為路由策略進行路由選擇的對手，為保證航空集群成員間通信可靠性，路由策略在進行路由選擇時需與之展開一場博弈。在這場博弈中，路由策略應盡可能降低所選路由集合Pu,v中各路由失效風險，以提高路由策略魯棒性，從而保障待通信節點對間通信可靠性。

現定義路由失效函數y(z)定量評估路由策略魯棒性。對于邊數為m的網絡，該函數定義域為{z|0≤z≤m}。函數值y(z)表示隨機刪除網絡拓撲中的z條邊后，對應路由失效比例，即：

(17)

式中，R表示路由策略為網絡中所有待通信節點對(u,v)規劃的路由集合Pu,v總數，r表示所有待通信節點對間失效路由集合Pu,v的數目。故函數值y(z)反映z條鏈路隨機失效后，因路由失效導致節點對間通信中斷數占所有待通信節點對數量的百分比。該比例越高，則整個網絡中節點對之間通信連通率越低，通信可靠性越差。從理論上講，函數值y(z)將隨自變量z的增加而呈增長趨勢。

對于任意給定的網絡拓撲圖G(V,E)，在相同通信流量需求下，通過分別繪制采用不同路由策略時路由失效函數y(z) 實際曲線，比較相同z值時函數值大小，可評估路由策略的魯棒性。若路由策略A對應曲線圖像恒位于路由策略B所對應曲線下方，則路由策略A相較于路由策略B魯棒性更強。

特別地，由于EDP路由策略能夠為各節點對間規劃出完全不相交的多條路由，失效概率最低，故理論上EDP路由策略魯棒性最高，可將EDP路由失效曲線作為下界參考曲線，其他路由策略對應路由失效曲線應恒位于該參考曲線上方。一般而言，路由策略所對應路由失效曲線與EDP路由失效曲線越接近，魯棒性越強。

4.2 仿真分析

為進一步論證航空集群機載網絡FOR路由策略保障節點對間通信可靠性，評估其應對路由隨機失效能力，通過仿真實驗研究該策略的魯棒性。實驗中，采用Barabasi-Albert網絡模擬航空集群機載網絡復雜網絡特征[41]，通過隨機刪除網絡拓撲圖中的通信鏈路，模擬航空集群機載網絡鏈路隨機失效的不確定性，并進行100次重復實驗，統計路由失效函數值y(z)的平均值，繪制其隨失效鏈路數目增加變化曲線，并在相同條件下與KSP路由策略、EDP路由策略變化曲線相比較，檢驗FOR路由策略的可靠性。實驗設定三種多路徑路由算法為各節點對間規劃路由數量k=|Pu,v|=2，結果如圖16所示。

(a) n=11、m=19 (b) n=21、m=39

(c) n=31、m=59 (d) n=41、m=79

(e) n=51、m=99 (f) n=61、m=119

(g) n=71、m=139 (h) n=81、m=159

(i) n=91、m=179 (j) n=101、m=199圖16 不同規模網絡下三種路由策略仿真曲線Fig.16 Simulation curves of three routing strategy in different network scales

觀察圖16中不同規模網絡下各路由策略仿真曲線，可得出以下結論：

1)隨著刪除邊數的增加，三種路由策略的路由失效比例大致呈線性增長趨勢，與4.1節中對路由失效函數y(z)的理論分析趨勢相符。

2)當隨機刪除邊數大于網絡中總邊數的50%時，FOR路由策略路由失效函數仿真曲線向EDP路由策略靠攏，此時FOR路由策略能夠達到可與EDP路由策略相比擬的魯棒性能，這說明FOR路由策略特別適合應用于易出現鏈路大規模失效的航空集群機載網絡中。

3)盡管FOR路由策略的仿真曲線有時位于KSP路由策略曲線之上，但在大多數情況下，相比KSP路由策略，FOR路由策略具有更低的路由失效概率，反映出FOR路由策略應對鏈路故障魯棒性強于KSP路由策略。

4)各仿真圖中，EDP路由策略對應路由失效曲線恒位于其余兩種路由策略對應路由失效曲線下方，這與理論預計結果相符，同時也驗證了實驗所得數據的真實性和可信度。

綜上所述，與傳統最短路由策略相比，FOR路由策略能夠有效降低路由失效風險，提升航空集群機載網絡路由魯棒性；與EDP路由策略相比，FOR路由策略并沒有通過刻意規避鏈路相交來提升魯棒性，而是利用隨機算法，巧妙地減少了各路由間的鏈路交叉概率。

5 結論

針對航空集群機載網絡路由失效問題，考慮到航空集群機載網絡具有較強不確定性，提出一種可滿足集群成員間信息傳輸實時性與可靠性需求的FOR路由策略。通過概率分析、競爭比分析等理論推導，以及時效性、魯棒性仿真檢驗，結果表明：該策略能夠有效降低航空集群機載網絡路由失效風險，且時延代價上界存在，在航空集群機載網絡中具有一定應用價值。此外，應該指出的是，由于FOR路由策略建立在隨機算法的基礎上，性能不太穩定，仍存在進一步改進空間。