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

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

隨著智能航空平臺的發(fā)展和多樣化任務(wù)需求的涌現(xiàn)[1-2]，“煙囪式”獨立的航空平臺無法實現(xiàn)信息交互與任務(wù)協(xié)同功能，亟需構(gòu)建一個具有高效互聯(lián)互通能力，滿足差異化航空業(yè)務(wù)需求，實現(xiàn)信息實時共享的航空集群網(wǎng)絡(luò)[3]。

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

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

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

1 系統(tǒng)模型

1.1 場景及控制器架構(gòu)

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

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

圖1 航空集群場景及控制架構(gòu)

1.2 控制器部署模型

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

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

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

4)網(wǎng)絡(luò)中每個傳輸節(jié)點同一時間只受一個LC控制，而每個LC能控制多個傳輸節(jié)點；每個LC同一時間只受一個GC控制，而每個GC能控制多個LC。

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

6) 由于航空集群網(wǎng)絡(luò)具有空間分布尺度大、拓撲結(jié)構(gòu)動態(tài)性高的特點，采用“拓撲快照”[16]的思想來分析網(wǎng)絡(luò)的動態(tài)運行過程。

模型的約束條件如下：

(1)

(2)

(3)

2 集群劃分算法設(shè)計

航空集群網(wǎng)絡(luò)的規(guī)模通常較大，平臺數(shù)量有時可達到幾百架以上，對控制平面的計算性能造成嚴重負擔。針對上述問題，本文首先根據(jù)節(jié)點規(guī)模和相關(guān)性對集群劃分，減小尋優(yōu)范圍，得到相關(guān)性強且分布均勻的子群。

2.1 集群劃分算法的相關(guān)指標

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

(4)

(5)

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

l=μD+λB

(6)

式中：D表示vi到中心節(jié)點的距離；B為vi加入到子群Gj后網(wǎng)絡(luò)負載均衡指數(shù)；μ和λ分別為權(quán)重因子。

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

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

定義1 局部密度ρi。

(7)

(8)

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

定義2 密度距離δi。

(9)

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

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

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

3 子群控制器部署優(yōu)化

3.1 優(yōu)化性能指標

航空集群網(wǎng)絡(luò)各子群聯(lián)系緊密，協(xié)同配合執(zhí)行任務(wù)，子群間LC的部署位置相互影響，局部最優(yōu)有時不一定能使得全網(wǎng)性能最優(yōu)。因此本文從網(wǎng)絡(luò)整體效能層面對控制器部署進行規(guī)劃，定義了如下性能指標：

3.1.1 控制路徑平均傳播時延

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

(10)

式中：α和β為權(quán)重因子，經(jīng)仿真分析當α=0.8，β=0.2時更接近實際的網(wǎng)絡(luò)傳輸狀況。

3.1.2 控制路徑平均失連概率

文獻[19]已對網(wǎng)絡(luò)可靠性進行研究，指出可靠性對于網(wǎng)絡(luò)性能的重要意義。網(wǎng)絡(luò)中的數(shù)據(jù)流和控制信息均由控制路徑傳輸，控制路徑的可靠性直接關(guān)系到整個網(wǎng)絡(luò)的可靠性。

(11)

3.2 子群LC部署算法

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

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

表2(續(xù))

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

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

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

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

(12)

4)精英保留策略。將表現(xiàn)更優(yōu)、多樣性更好的個體保留進入下一代。

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

3.3 復雜度分析

INSGA-Ⅱ算法的復雜度與網(wǎng)絡(luò)節(jié)點數(shù)n，目標函數(shù)個數(shù)m，及迭代次數(shù)I有關(guān)，其尋優(yōu)復雜度表示如下：

ο(INSGA-Ⅱ)=ο(Imn2)

(13)

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

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

ο(n2logn)

(14)

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

(15)

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

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

(16)

式中：K為待劃分子群數(shù)目。

4 實驗結(jié)果及分析

4.1 仿真環(huán)境及參數(shù)設(shè)置

對實驗的仿真環(huán)境和參數(shù)設(shè)置作如下說明：

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

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

3)規(guī)定當網(wǎng)絡(luò)節(jié)點規(guī)模小于100時，GC數(shù)量為1；當節(jié)點規(guī)模大于100時，GC數(shù)量為2。GC部署的位置為網(wǎng)絡(luò)中隨機確定的節(jié)點。

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

4.2 子群劃分算法性能分析

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

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

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

圖2 不同節(jié)點規(guī)模的負載均衡指數(shù)

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

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

圖3 Pareto前沿對比圖

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

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

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

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

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

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

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

5 結(jié)語

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