面向大規模航空集群組網的控制器部署方法

付皓通， 王 翔， 趙尚弘， 宋鑫康， 薛鳳鳳

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

隨著智能航空平臺的發展和多樣化任務需求的涌現[1-2]，“煙囪式”獨立的航空平臺無法實現信息交互與任務協同功能，亟需構建一個具有高效互聯互通能力，滿足差異化航空業務需求，實現信息實時共享的航空集群網絡[3]。

現有的航空集群網絡多數基于傳統的網絡架構和服務模式，例如，以航空數據鏈和航空自組網[4]為代表的機載網絡一直遵循著業務與設備緊密耦合的設計思想。雖然通過不斷更新設備的軟硬件能夠緩解業務升級需求的壓力，但這種“打補丁”的方式效率很低，使得網絡協議變得臃腫，同時造成了網絡管理與配置過程復雜僵化，難以適應航空集群網絡成員間靈巧的交互協同。軟件定義網絡(software defined network, SDN)的出現打破了傳統分布式網絡發展的“瓶頸”[5]，其所具有的靈活性、可編程性和開放性等優點為組建航空集群網絡帶來了眾多優勢[6]。文獻[7]提出了軟件定義航空集群機載戰術網絡架構，有效地提升了網絡管理效率，增強了差異化服務能力，推進了SDN與航空集群網絡結合的進程。應用SDN范式構建航空集群網絡，首先需要搭建控制結構，實現邏輯上的集中控制。在航空集群網絡中，節點高速移動，拓撲動態變化，鏈路可靠性差，部署單一控制器存在性能受限和故障失效問題，可通過部署多控制器來提高網絡的魯棒性和擴展性。近年來控制器部署問題(controllers placement problem, CPP)逐漸成為了研究熱點[8-9]。

目前關于控制器部署的研究主要集中在地面網絡，并隨著各類應用場景的出現而拓展。文獻[9]首次提出控制器部署問題，指出CPP核心是控制器數量和部署位置，并分析了不同的部署方案對網絡時延的影響；以此為基礎，文獻[10]研究了基于可靠性優化的控制器部署問題，引入貪婪算法和模擬退火算法求解，得到了可靠性更高的部署方案；文獻[11]以時延和負載失衡度最小化為目標，提出基于粒子群變異函數的多目標遺傳算法，提高算法收斂速度同時獲得多樣性更高的Pareto解。為了將地面網絡控制器部署研究拓展到航空集群網絡中，文獻[12]基于航空集群網絡場景特點，以全網平均時延、平均中斷概率和控制器負載失衡度最小化為目標，提出一種基于改進蝙蝠算法的部署算法，提升了Pareto解的質量。文獻[13]針對航空集群網絡的拓展性，提出一種SDN航空集群網絡架構，并設計一種混合優化算法來獲得最佳控制器部署方案。然而現有航空集群網絡控制器部署算法，所考慮的航空平臺數量受限，在小規模網絡場景下具有搜索速度快、尋優精度高等優點，但當網絡中平臺數量增多到幾百架時，算法的復雜度會急劇上升，計算時間可達幾小時之久，難以滿足航空集群網絡實時響應需求，且會對網絡計算資源進行大量占用。

基于以上分析，針對大規模航空集群網絡控制器部署算法所存在的計算復雜度高，實時響應能力不足問題，本文結合SDN混合式架構下的多控制器部署模型，設計一種面向大規模航空集群網絡的控制器部署算法(large-scale network controller deployment algorithm, LNCDA)，所提算法分為2個階段，首先將大規模航空集群網絡進行劃分，然后在子群內搜索尋優，最后得到關于Pareto前沿解的控制器部署方案。

1 系統模型

1.1 場景及控制器架構

本文基于圖1(a)所示航空集群場景，該場景下存在各類有人/無人機航空平臺，依據不同航空任務靈活動態組織。與地面SDN網絡場景不同，在航空集群環境中，網絡節點的高移動性使得傳輸節點與控制節點間難以穩定相連；電磁環境的復雜性使得控節點容易出現故障風險；無線鏈路的不可靠性使得機間通信存在較大中斷概率?；谝陨戏治?，扁平式架構難以及時掌握全局視圖信息，層次式架對頂層控制器的性能提出較高要求，而混合式架構具有良好的擴展性和高效的信息共享能力，能夠滿足構建SDN航空集群網絡的需求。因此，本文基于混合式架構[14]構建SDN航空集群網絡，實現對網絡的集中控制。

航空集群網絡混合式架構如圖1(b)所示，控制平面擴展為全局控制器平面和局部控制器平面兩層。全局控制器(global controller, GC)掌握全局視圖信息，負責跨區域流量轉發，通常部署于生存能力、計算處理能力較強的航空平臺上。局部控制器(local controller, LC)掌握局部網絡視圖信息，負責本區域內設備管理與流量轉發，通常部署在航跡相對穩定的航空平臺上。二者組成了航空集群網絡的控制平面，共同維護邏輯上的集中控制。

圖1 航空集群場景及控制架構

1.2 控制器部署模型

文獻[15]對混合式架構進行了深入研究，本文重點研究該架構下LC的部署問題。針對控制器部署作如下假設：

2) 網絡中所有傳輸節點均可成為控制節點，當收到部署指令時，傳輸節點開啟控制器功能，成為控制節點，此時認為傳輸節點與控制節點的時延為零。

3) 定義傳輸節點與LC之間的映射關系矩陣H=[xij]n×r，LC與GC之間的映射關系矩陣K=[yij]r×t。當xij=1時，表示vi映射到sj，否則為0；yij=1表示si映射到cj，否則為0。

4)網絡中每個傳輸節點同一時間只受一個LC控制，而每個LC能控制多個傳輸節點；每個LC同一時間只受一個GC控制，而每個GC能控制多個LC。

5)傳輸節點vi的流量請求為ti，每個LC具有相同的容量，映射到同一LC上的傳輸節點流量請求之和不超過其容量Φ，且任意傳輸節點到LC的時延小于閾值τ。

6) 由于航空集群網絡具有空間分布尺度大、拓撲結構動態性高的特點，采用“拓撲快照”[16]的思想來分析網絡的動態運行過程。

模型的約束條件如下：

(1)

(2)

(3)

2 集群劃分算法設計

航空集群網絡的規模通常較大，平臺數量有時可達到幾百架以上，對控制平面的計算性能造成嚴重負擔。針對上述問題，本文首先根據節點規模和相關性對集群劃分，減小尋優范圍，得到相關性強且分布均勻的子群。

2.1 集群劃分算法的相關指標

航空集群的空間相關性很強，因此，各航空平臺間的距離是衡量相關性的主要依據。同時，由于控制器的容量限制，子群規模過大將會導致控制器過載及航空平臺失連現象，因此需要合理控制每個子群的平臺數。為此，提出負載均衡指數B:

(4)

(5)

綜合考慮平臺間距離及負載均衡因素的影響，設計改進距離：

l=μD+λB

(6)

式中：D表示vi到中心節點的距離；B為vi加入到子群Gj后網絡負載均衡指數；μ和λ分別為權重因子。

2.2 基于負載均衡的劃分算法

文獻[17]所提DPC聚類算法，得到了相關性較好的聚類結果，然而卻沒有考慮容量限制因素。本文提出一種基于負載均衡的劃分算法(load balance based division algorithm, LBDA),以得到相關性強且均衡的劃分結果。引入如下定義：

定義1 局部密度ρi。

(7)

(8)

式中：ρi為節點vi在Dc半徑范圍中的鄰近節點個數；Dc表示截斷距離。

定義2 密度距離δi。

(9)

式中：δi表示節點vi到任意局部密度比它高的節點的最短距離。對于網絡中局部密度最大的節點，設δmax=max(dij)。

算法首先根據網絡特征參數ρi和δi得到各子群中心節點，然后將其余的節點依據l值最小原則分配到不同子群中。表1所示為LBDA算法流程。

表1 基于負載均衡劃分算法

3 子群控制器部署優化

3.1 優化性能指標

航空集群網絡各子群聯系緊密，協同配合執行任務，子群間LC的部署位置相互影響，局部最優有時不一定能使得全網性能最優。因此本文從網絡整體效能層面對控制器部署進行規劃，定義了如下性能指標：

3.1.1 控制路徑平均傳播時延

網絡中的控制路徑是指GC到LC，LC到傳輸節點的路徑。當網絡狀況良好時，傳播時延遠大于其他時延[18]，因此本文主要考慮傳播時延?？刂坡窂狡骄鶄鞑r延可以反映傳播時延的整體情況，表示如下：

(10)

式中：α和β為權重因子，經仿真分析當α=0.8，β=0.2時更接近實際的網絡傳輸狀況。

3.1.2 控制路徑平均失連概率

文獻[19]已對網絡可靠性進行研究，指出可靠性對于網絡性能的重要意義。網絡中的數據流和控制信息均由控制路徑傳輸，控制路徑的可靠性直接關系到整個網絡的可靠性。

(11)

3.2 子群LC部署算法

為保證求解精確度同時降低算法復雜度，本文對文獻[20]中非支配排序遺傳算法II (nondominated sorting genetic algorithm II,NSGA-Ⅱ)進行改進，設計了一種具有染色體自適應交叉和變異算子的改進NSGA-Ⅱ算法(improved NSGA-Ⅱ，INSGA-Ⅱ)，動態調整交叉和變異概率，提高算法搜索能力和收斂速度。表2所示為基于INSGA-Ⅱ算法的LC部署流程。

表2 基于改進NSGA-Ⅱ算法的LC部署

表2(續)

對算法主要步驟進行說明：

1)種群個體初始化。設置種群規模pop，將種群個體分成K個均勻的子集{p1,p2,…,pK}，K為LC部署數量。

2) 非支配排序。計算每個個體P的被支配個體數np和支配個體集合Up，直到種群中所有個體的非支配等級被劃分。

3) 擁擠度計算。首先任選一種目標函數fu，計算Ri+1中個體的fu值并按升序排列得到ξ，接下來計算ξ中每個個體的其他類型目標函數值。規定邊界值為無窮大，即fu(ξ1)=fu(ξn)=∞。個體d的擁擠度nd的計算如下：

(12)

4)精英保留策略。將表現更優、多樣性更好的個體保留進入下一代。

5)交叉、變異。采用自適應算子對所選染色體進行單點交叉和位變異操作，動態調整交叉和變異概率。

3.3 復雜度分析

INSGA-Ⅱ算法的復雜度與網絡節點數n，目標函數個數m，及迭代次數I有關，其尋優復雜度表示如下：

ο(INSGA-Ⅱ)=ο(Imn2)

(13)

本文所提LNCDA算法，第1階段將航空集群劃分為子群，第2階段在子群內部署尋優。第一階段復雜度主要由距離值計算ο(n2)、降序排列ο(n2logn)和ρ及δ值計算ο(n2)組成，即：

ο(phase_1)=ο(n2)+ο(n2logn)+ο(n2)≈

ο(n2logn)

(14)

第2階段在劃分后的子群中進行全局尋優，復雜度為：

(15)

因此本文所提算法復雜度為：

ο(LNCDA)=ο(phase_1)+ο(phase_2)=

(16)

式中：K為待劃分子群數目。

4 實驗結果及分析

4.1 仿真環境及參數設置

對實驗的仿真環境和參數設置作如下說明：

1)實驗基于MATLAB2016a對本文所提模型和算法進行仿真實驗。

2)假設所有LC節點具有相同的負載容量和處理能力；傳輸節點的請求為單位流量；節點的故障概率為[0,0.04]中的隨機值；l和σ鏈路的失連概率分別為[0,0.08]和[0,0.06]之間的隨機值。

3)規定當網絡節點規模小于100時，GC數量為1；當節點規模大于100時，GC數量為2。GC部署的位置為網絡中隨機確定的節點。

4)為了體現網絡拓撲的隨機變化性，在給定區域內隨機生成多個節點，利用Bellman-ford算法得到任意兩點間的最短路徑。實驗中網絡節點的分布范圍為400 km×300 km的矩形區域，節點的通信半徑為50 km。

4.2 子群劃分算法性能分析

為了評價LBDA的性能，本節將LBDA與Louvain算法[21-22]和K-means算法[23-24]進行對比。

分別設置節點規模為50、100、150的航空集群，在每種節點規模下比較不同算法的負載均衡指數隨子群數的變化情況。

實驗結果如圖2所示，Louvain、DPC和K-means算法的負載均衡指數均高于LBDA，表明LBDA的負載均衡性更優。由于Louvain、DPC和K-means算法在劃分過程中只考慮節點間的相關性而沒有限制子群規模，導致各子群節點數量分布不均；而LBDA綜合考慮二者的影響，在保證較好相關性的同時獲得更均衡的劃分結果。

圖2 不同節點規模的負載均衡指數

4.3 控制器部署算法性能分析

為評價本文所提LNCDA算法的多目標尋優能力，本節設置網絡節點數為150，LC數量K=6，使用標準NSGA-Ⅱ算法, INSGA-Ⅱ算法, 窮舉算法(brute force, BF)對網絡進行直接尋優；而本文所提LNCDA算法將網絡劃分為6個子群，然后在各子群內進行尋優。幾種算法的Pareto前沿對比見圖3。

圖3 Pareto前沿對比圖

由圖3可知控制路徑平均傳播時延與平均失連概率呈負相關，從而驗證了CPP是一個多目標優化問題，兩種性能指標之間存在一定程度的互斥關系。INSGA-Ⅱ算法性能較NSGA-Ⅱ算法有了明顯提升，能獲得更優的Pareto前沿，接近理論最優的BF算法。由圖可知當測試算法收斂時，LNCDA算法尋優能力接近NSGA-Ⅱ算法。LNCDA算法通過集群劃分，降低了網絡尋優復雜度，從而使算法能夠快速收斂。然而對網絡劃分，也限制了算法的尋優能力，位于子群中心的節點更有可能部署控制器，而子群邊緣的節點在尋優中可能被跳過。因此，LNCDA算法以損失一定尋優精度的代價，獲得了更快的收斂速度。

為比較不同LC數量下LNCDA算法，K-means算法，INSGA-Ⅱ算法和多目標粒子群優化算法(multiple objective particle swarm optimization, MOPSO)[25]對網絡性能的優化能力，對控制路徑平均傳播時延、平均失連概率兩種性能指標進行討論分析，比較結果見圖4。

圖4 算法性能指標隨LC數量變化情況

由圖4(a)可知，K-means算法的平均傳播時延最小，因為該算法主要依據類內節點距離最短原則劃分子群，而其余算法需要兼顧其他優化目標。當LC數量小于7時，LNCDA算法的時延低于MOPSO算法、INSGA-II算法，較MOPSO算法和INSGA-II算法分別降低了20.87%和12.75%。隨著LC數量增加，子群數也同步增加，每個子群的規模不斷減小，從而限制了LNCDA算法的尋優能力，因此當LC數量多于7時，LNCDA算法的時延會逐漸高于INSGA-II算法。

由圖4(b)可知，K-means算法的平均失連概率始終高于其他算法。當LC數量小于7時，LNCDA算法的失連概率小于MOPSO算法、INSGA-Ⅱ算法，較MOPSO算法和INSGA-II算法分別降低了7.65%和5.87%；當LC數量大于7時，LNCDA算法的失連概率高于MOPSO算法和INSGA-II算法。因此，LNCDA算法在子群數量較少時表現出較好的全局優化能力。

圖5為算法的平均計算時間隨LC數量的變化情況?？芍S著LC數量增加，K-means、MOPSO、INSGA-II算法的計算用時不斷增加。而LNCDA算法的計算用時不斷減少，并收斂到較低值。K-means算法，MOPSO算法和INSGA-II算法直接應用于全網尋優，搜索范圍大，計算復雜度高，存在對目標重復搜索情況，易陷入局部最優解；LNCDA算法對網絡進行算法劃分，能夠避免重復搜索的情況，具有較好的全局搜索能力。由于K-means、MOPSO和INSGA-II算法基于迭代方式尋優，當網絡規模不變時，尋優變量數目增多反而使時間復雜度增加；而LNCDA算法只需要一次分域就能實現集群劃分，并隨著子群規模逐漸減小，尋優復雜度不斷降低，因此具有更低的時間復雜度。

圖5 平均計算時間隨LC數量變化情況

5 結語

本文針對現有航空集群網絡存在的業務與設備耦合緊密，網絡配置與管理復雜的問題，引入軟件定義網絡的設計思想，搭建混合式控制架構，增強了控制平面的擴展性，實現邏輯上的集中控制；考慮到航空集群網絡節點規模大，拓撲動態變化的特點，設計了一種大規模航空集群網絡控制器部署優化算法，通過仿真分析證明所提算法能夠有效提升網絡性能，同時具有較快的收斂速度，適用于解決大規模動態場景下控制器部署問題。