航空信息網絡集中控制器部署優化策略研究*

冉金鵬，趙尚弘，王 翔

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

1 引言

航空信息網絡是指利用可用的無線通信鏈路和適當的組網機制將各個航空平臺、傳感器等鏈接形成的信息化網絡系統，具有高動態、覆蓋廣、重負載、多任務等特點[1-2]。當前提出的航空信息網絡架構大多遵循傳統的網絡架構和服務模式，主要是基于信息傳輸的可靠性和穩定性等方面考慮，與業務應用不具備靈活的耦合關系，導致網絡難以實現互聯互通，且網內各種協議體制采用封閉式設計，缺乏開放性，上述特點使得現階段航空信息網絡管理起來十分復雜且效率低下[3]。

軟件定義網絡（software defined networking，SDN）[3]的出現正好解決了上述的一系列問題。SDN 使數據平面與控制平面分離，突破了原網絡中兩平面緊密耦合的部署方式，采用邏輯集中的控制器對數據分發、轉換設備進行統一管理，使執行任務的各物理設備可以獨立完成相應功能。因此，有學者考慮將SDN 技術引入航空信息網絡，利用SDN 技術優勢進一步優化航空信息網絡性能，提出一種基于SDN 思想的新型航空信息網絡架構，即軟件定義航空信息網絡[4]。本文側重于研究軟件定義航空信息網絡架構下的控制器優化部署問題，對具體架構內容不再做過多贅述。

軟件定義航空信息網絡中控制器的部署對全網的運轉起著“金字塔”頂端式的核心控制作用[5]，其處理能力直接決定了整個網絡的性能好壞。因此，控制器的優化部署問題成為軟件定義航空信息網絡領域的熱難點。多控制器部署問題主要包括兩方面，控制器部署的位置以及相應所需的控制器個數。控制器部署的位置反映了控制器與網絡節點之間的映射關系，須兼顧全網平均時延、網絡管理復雜度以及各控制器之間的負載均衡；所需的控制器個數則直接關系到網絡的健壯性和成本開銷，多個控制器協同部署可有效提升網絡穩定性和可擴展性。綜合考慮時延、可靠性和負載均衡對網絡性能的影響是控制器優化部署要解決的核心問題，這是一個典型的NP-hard（non-deterministic polynomial hard）問題[6]。

文獻[6]基于貪心算法進行求解，采用控制器與交換機間平均傳輸時延和網絡零故障率時最壞傳輸時延等兩個性能指標研究問題，有效解決了控制器部署的位置和數量問題，但未考慮可靠性、網絡開銷及負載均衡等問題。文獻[7]綜合考慮傳播延遲和負載均衡，提出了網絡聚類粒子群優化算法（network clustering particle swarm optimization algorithm，NCPSO），通過生成具有高聚類效率的多樣化個體并克服離散問題中使用的粒子群算法的缺點，減少了控制器放置的數量，具有良好的負載均衡性能。文獻[8]以最小化SDN 控制路徑平均故障率為優化目標，提出了幾種網絡可靠性的度量和優化部署算法，并使用真實的網絡拓撲進一步評估量化控制器位置及數量對控制網絡可靠性的影響。但是同時以全局平均時延、網絡可靠性以及控制器負載均衡為優化目標的相關多目標組合優化問題卻少有研究。

基于上述分析，本文在基于控制器部署負載均衡基礎上同時考慮全局平均時延和網絡可靠性，將改進的蝙蝠優化算法引入到軟件定義航空信息網絡多控制器部署問題中，建立了多目標整數規劃模型，并采用改進算法對模型進行迭代求解。

2 控制器部署問題模型設計

本文在滿足軟件定義航空信息網絡特殊環境需求的前提下，綜合考慮網絡時延、可靠性和均衡問題，構建了控制器部署問題多目標組合優化模型，具體描述如下：

（1）軟件定義航空信息網絡用無向圖G(V,E)表示，其中V表示網絡拓撲中節點集合，V={v1,v2,…,vn}，vi表示一個網絡節點，|V|=n為節點個數，1 ≤i≤n；E表示連接各網絡節點的鏈路集合。

（2）定義Vl?V為部署在網絡中的控制器集合，Vl={vl1,vl2,…,vls}，vld表示一個控制器及其部署位置，|Vl|=s為控制器部署的個數，1 ≤d≤s。

（3）網絡中每個節點表示一個交換機，本文中統稱為傳輸節點。另外，假設網絡中一個傳輸節點僅受唯一控制器控制，而控制器可以管理多個傳輸節點。控制器部署在傳輸節點上，即與交換機處于同一位置，此時可認為兩者的時延和中斷概率都為0。

（4）假設網絡中節點和鏈路相互獨立，互不影響，即節點故障并不影響鏈路性能。反之，鏈路故障也不影響節點性能，對于網絡元素（節點或者鏈路）w∈V?E，定義Pw為元素中斷概率，且0 ＜Pw＜1。

（5）對于傳輸節點vi、vd，定義r(vi,vd)為傳輸節點vi到vd的最短路徑，假設控制路徑為傳輸節點到控制器以及控制器到控制器的有效路徑，且控制路徑只取最短路徑，定義控制器與控制器之間的路徑為鄰接路徑，當采用層次型控制器部署時，由文獻[9]可知，鄰接路徑條數受控制器個數約束。

（6）設vi∈V,vld∈Vl，x(vld)=1 代表一個控制器布置在位置vld，否則為0；y(vi,vld)=1 代表x(vld)=1 且傳輸節點vi分配給了控制器vld，或x(vi)=x(vld)=1 且控制器之間有鄰接路徑，否則為0；設pw(vi,vld)=1 代表vi與vld之間控制路徑經過元素w，否則為0。在SDN 網絡無保護機制情況下，控制路徑平均故障率指傳輸節點與控制器以及控制器與控制器之間失去連接概率的均值[10]，本文以中斷概率近似代替平均故障率，設網絡狀態分為連通和中斷兩種狀態，則連通狀態出現的概率為：

那么網絡中斷概率為：

（7）對于航空信息網絡高動態性特征的考慮，借鑒衛星網絡中“拓撲快照”[11]的思想將網絡運行時間切割為許多時間碎片，在碎片時間內網絡處于保持狀態，利用連續靜態拓撲模擬航空網絡的動態拓撲時變。

2.1 全局平均時延

網絡時延包括處理時延、等待時延、傳輸時延以及發送時延。在網絡未擁塞情況下，等待時延[12]忽略不計；處理時延與發送時延通常為固定值；傳輸時延與兩個節點間距離有關，包括控制器與傳輸節點間以及控制器與控制器之間的傳輸時延[13]。在網絡時延方面，本文僅考慮軟件定義航空信息網絡的傳輸時延對全網性能的影響。最小化傳輸節點間和控制器的延時能有效提高網絡中元素故障的發現率和數據傳輸效率，降低網絡擁塞。而邏輯集中、物理分布式控制器部署特點要求控制器與控制器之間的延時盡量最小，確保全網狀態邏輯一致，提高協同處理過程的快速反應能力。下面給出最小化全局平均時延公式：

式中，將傳輸節點和控制器的最短路徑時延集合定義為d(vi,vld)，控制器與控制器之間的最短路徑時延集合定義為d(vli,vld)，網絡節點之間的時延存儲在時延矩陣中，用于最短路徑時延的計算，n為網絡中節點個數，s為控制器部署的個數，c1、c2為調整傳輸節點和控制器之間延時以及控制器與控制器延時的比例參數，本文取c1=c2=0.5。加號前半部分用于計算傳輸節點間到控制器的平均時延，加號后半部分用于計算控制器與控制器之間的平均時延，兩者之和即為全局平均時延。優化目標f1為最小化全局平均時延。

2.2 全網中斷概率

由于航空信息網絡具有空間大尺度分布、高動態、拓撲鏈路不穩定等特點，其節點和鏈路性能受大氣信道影響嚴重，極易導致節點和鏈路失連以及網絡中斷，而網絡魯棒性和可靠性直接影響到整個航空平臺性能的優劣，因而在分析研究軟件定義航空信息網絡控制器部署優化問題時應該著重考慮全網中斷概率。通常網絡故障分為節點故障和鏈路故障兩類，節點故障又分為傳輸節點故障和控制器故障，一般由設備中軟、硬件故障引起，易導致傳輸節點和控制器間連接中斷，鏈路故障一般由鏈路維護、鏈路攻擊引起，易造成傳輸鏈路上數據的丟失。單一鏈路和節點的故障會造成傳輸節點和控制器之間以及控制器之間用于管理與控制SDN 指令的控制路徑的中斷，控制路徑的中斷則會帶來網絡拓撲的不穩定，從而影響網絡的全局可視性。因此，考慮節點和鏈路故障影響，將部分節點和鏈路發生故障時全網中斷概率最小化作為優化目標，給出最小化全網中斷概率公式：

式中,y(vi,vld)=1 代表x(vld)=1 且傳輸節點vi分配給了控制器vld，或x(vi)=x(vld)=1 且控制器之間有鄰接路徑，否則為0；pw(vi,vld)=1 代表vi與vld間控制路徑經過元素w，否則為0。Pw為元素中斷概率，且0 ＜Pw＜1。優化目標f2為最小化全網中斷概率。

2.3 控制器負載失衡度

對于軟件定義航空信息網絡負載均衡問題的考慮，一方面結合成本開銷，使用最少數量的控制器最大化地利用控制器控制能力，另一方面不能使控制器實際負載超過其額定負載能力，否則將增加網絡擁塞，降低網絡性能[14]。這就要求接入控制器的傳輸節點數量盡可能均勻分布在整個全局網絡，減小全局網絡控制器負載差異度，從而保證網絡資源的充分利用，提高航空信息網絡連接成功率，增加航空信息網絡魯棒性。下面給出最小化控制器負載失衡度公式：

式中，qvld表示控制器vld接入控制的節點個數，q0表示所有控制器的平均接入節點數，s為控制器個數。從上式可以看出，控制器負載失衡度越小，控制器控制的傳輸節點數量越均衡，負載均衡性能越好。

2.4 約束條件

結合控制器部署問題特性，可列出以上三個目標函數的約束條件，如下所示：

式（7）表示網絡中部署的控制器個數；式（8）表示網絡中一個傳輸節點僅受唯一控制器控制；式（9）表示控制器間鄰接路徑的條數；式（10）表示前文中已敘述的控制器整數規劃假設條件。

3 控制器部署優化策略分析

本文研究的控制器優化部署問題以傳輸節點-控制器分配方案為優化對象，算法優化時引入變速度修正因子和高斯變異擾動，克服蝙蝠算法存在的收斂速度慢、易陷入局部最優的缺點，利用改進的蝙蝠優化算法求出模型的非劣最優解集。

3.1 蝙蝠算法及改進

蝙蝠算法[15]是由劍橋大學學者Yang 在2010 年提出的一種新型智能優化算法，該算法通過模擬自然界蝙蝠種群的回聲定位來準確探測獵物的位置以及有效避障。與其他一些優化算法相比，該算法具有尋優更為簡潔、收斂速度較快、魯棒性強等特點，適合于求解多目標優化問題。

該算法基本思路是以一只蝙蝠作為基本單元，且每只蝙蝠都有一個適應度值來對函數解空間進行優化。每只蝙蝠可以調整自身發射超聲波的強度、頻度等對空間進行搜索，使整個種群的活動逐步由無序變為有序。蝙蝠位置以及速度更新公式如下：

式中，fi表示第i只蝙蝠的脈沖頻率；fmin、fmax分別表示最小和最大脈沖頻率；α是屬于[0,1]的任一隨機數；Xi(t)和Vi(t)分別表示第i只蝙蝠t時刻的位置和速度；Xbest(t-1)表示t-1 時刻全局蝙蝠中使得適應度值最小的最優位置。當蝙蝠個體在進行局部尋優時，則隨機擾動從當前最優解集中任選一解更新下一位置，公式如下：

式中，η∈[-1,1]，Ai(t)表示蝙蝠的脈沖強度。

在搜尋初期，蝙蝠發射的聲波脈沖具有較大的脈沖強度和較小的脈沖頻度，以便于擴大搜索空間，當距離目標較近時，蝙蝠會減小脈沖強度并增加脈沖頻度，以便于準確定位目標。蝙蝠發射聲波脈沖強度和頻度更新公式如下：

式中，β為脈沖強度衰減系數，β∈[0,1]；γ為脈沖頻度放大系數，γ＞0；ri(t)表示第i只蝙蝠t時刻的脈沖頻度。

針對基本蝙蝠算法在尋優末段容易陷入局部最優的極值，本文引入變速度修正因子，使得蝙蝠的前期搜索為后期的搜索提供經驗，盡可能避免局部極值的困境；為了進一步提高算法的運算效率，本文引入高斯變異擾動，使得蝙蝠在局部尋優階段，減少更新至下一位置的隨機性，提高收斂速度。

3.2 算法相關參數定義

蝙蝠位置定義：算法中每只蝙蝠的位置表示控制器部署問題的一個解，即一種可能的控制器分配方案，解集長度為傳輸節點個數n，可表示為X=[x1,x2,…,xn]。解中第i個位置對應于第i個節點所接入的控制器，每個傳輸節點的控制器選擇xi構成控制器部署方案X。

蝙蝠速度定義：算法中每只蝙蝠的速度表示蝙蝠位置解向量的尋優更新策略，可表示為V=[v1,v2,…,。向量中元素取1 表示該位置解向量需要進行尋優更新。

適應度函數定義：蝙蝠在搜尋獵物過程中通過不斷更新函數的適應度值達到尋優更新的目的，此處取目標函數F(X)={f1,f2,f3}，依次對其進行計算以評價部署方案優劣。本文研究的是一個三目標決策的問題，中斷概率與時延、負載失衡度三目標之間在一定程度上可能存在互斥情況，例如當要求控制器間高可靠性時，其傳輸時延可能較大，因此當滿足一個或者兩個優化部署方案時不一定能同時保證另外一個或者兩個達到最優，此時考慮在可行部署方案中取非劣最優解集以最大限度滿足最優部署。

3.3 算法設計與描述

本文所提算法的設計思路是：首先根據初始化網絡中傳輸節點-控制器分布找出一個可行的控制器分配方案，將其作為初始解，然后按照本文所提的改進方式更新蝙蝠的位置與速度，并在迭代中進行Pareto 解集選擇，通過不斷遞進尋優，獲得控制器部署問題的近似最優解。算法的具體流程圖、步驟及偽代碼描述如下。

OBA-CP（controller placement based on optimized bat algorithm）算法流程圖如圖1 所示。

OBA-CP 算法具體步驟描述如下：

步驟1隨機初始化蝙蝠個體N，初始位置Xi(t)，初始速度Vi(t)，脈沖強度Ai(t)，脈沖頻度ri(t)，脈沖頻率fi范圍。

Fig.1 Flow chart of improved bat algorithm圖1 改進蝙蝠算法流程圖

步驟2根據適應度函數F(X)求出每只蝙蝠的適應度函數值，并找出最優解，記錄最優解位置X*。

步驟3更新蝙蝠位置與速度。引入變速度修正因子，對速度更新公式進行改進優化。

式中，χ(t)表示引入的變速度修正因子，其作用是使蝙蝠的前期搜索為后期搜索提供參照；χmax、χmin分別為χ(t)最大值和最小值；σ∈[1,T]，T表示最大迭代次數。

步驟4生成隨機數rand1，如果rand1 ＜ri，則引入高斯變異操作，其作用是減少更新至下一位置的隨機性，提高收斂速度。

式中，N(0,1)表示服從均值為0，方差為1的高斯分布。

步驟5再次生成隨機數rand2，如果滿足rand2 ＜Ai&fit(Xi)＜fit(Xnew)，則接受新解，更新Ai(t)和ri。

步驟6排列所有蝙蝠位置，找出當前最優值及對應位置。

步驟7設當前最優解為F*，然后使所有蝙蝠繼續向下一時刻搜尋，另設解空間保存已找到的最優解集，解空間元素隨搜尋進行逐漸增多，其前沿逼近真實的Pareto 前沿。當達到最大迭代次數后轉到步驟8，否則轉到步驟3。

步驟8輸出結果。

OBA-CP 算法偽代碼描述如下：

輸入：網絡拓撲G(V,E)。

輸出：模型的Pareto 解集。

4 仿真及結果分析

為了驗證本文提出算法的有效性，采用節點數30 的航空信息網絡拓撲，參考文獻[16-17]中初始化方法，用傳輸時延代表鏈路權重，時延越大，權值越高，設權值為區間[1,10]內的隨機整數。為保證網絡連通性，考慮網絡組件故障率較小的場景，設單個節點和單條鏈路的中斷概率分別為區間[0,0.02]和[0,0.04]內的隨機數。實驗網絡拓撲結構如圖2 所示，在1×1 范圍內隨機生成均分分布的傳輸節點和鏈路，控制器部署在傳輸節點上。設置改進的蝙蝠優化算法種群規模N為80，最大迭代次數T為500，初始脈沖強度和脈沖頻度為0.5，fmax、fmin分別為3 和0，β、γ均為0.9，σ取2。

Fig.2 Experimental network topology圖2 實驗網絡拓撲

各算法利用生成的相同網絡拓撲，分別取控制器個數從3 個到11 個，重復100 次計算取最終平均值，從全局平均時延、全網中斷概率和控制器負載均衡等三項性能尺度指標對改進算法進行評價，并以SPEA-Ⅱ算法[18]和NCPSO 算法[7]作為對比。文獻[18]基于典型的多目標優化算法SPEA（strength Pareto evolutionary algorithm）提出了SPEA-Ⅱ算法，利用模糊集理論優化折衷分配方案，證明了改進算法可以產生更廣泛且不受支配的Pareto 解集，NCPSO 算法則是利用粒子群遞進尋優的思想解決多控制器部署問題。

圖3 為采用OBA-CP 算法獲得Pareto 解最優前沿，由圖可知，全網中斷概率與全局平均時延、控制器負載失衡度成反比，驗證了控制器部署問題是一個多目標決策問題，中斷概率與時延、負載失衡度三目標之間在一定程度上存在互斥情況。此外，表明了Pareto 解最優前沿并不是一個最優解，而是在滿足一定約束條件下的權衡解，網絡部署決策者可根據Pareto 解最優前沿選擇其中滿足特定網絡需求的一個或一組有效解作為控制器部署問題的最終解。

Fig.3 Pareto solution optimal frontier圖3 Pareto 解最優前沿

圖4 比較了不同算法下的全局平均時延，由圖4可知，隨著控制器數量的增加，全局平均時延逐漸降低，符合全局平均時延定義。剛開始控制器個數在4個左右時，通過OBA-CP 算法與NCPSO 算法計算出的時延基本相當，但隨著迭代進行，后期在部署相同控制器數量條件下，采用OBA-CP 算法整體上擁有最小的平均時延，其性能優于NCPSO 算法和SPEA-Ⅱ算法。在不同的控制器數量條件下，OBA-CP 算法得到的部署結果中平均時延較NCPSO 算法和SPEA-Ⅱ算法分別降低了2.33%和3.47%。

Fig.4 Global average delay of different algorithms圖4 不同算法的全局平均時延

圖5 比較了不同算法下的全網中斷概率，由圖5可知，當控制器個數小于8 個時，隨著控制器數量的增加，全網中斷概率降低速度較快，超過8 個以后，中斷概率趨于穩定，且在部署相同控制器數量條件下，采用OBA-CP 算法明顯性能優于NCPSO 算法和SPEA-Ⅱ算法。只有在控制器數量為7 時，NCPSO 算法的中斷概率略低于OBA-CP 算法，但這不影響整體上性能效果。對于不同控制器數量條件下中斷概率降低的效率，與NCPSO 算法和SPEA-Ⅱ算法相比，平均降低了0.41%和1.25%。

Fig.5 Network-wide outage probability of different algorithms圖5 不同算法的全網中斷概率

Fig.6 Load imbalance of different algorithms圖6 不同算法的整體負載失衡度

圖6 比較了不同算法下的整體負載失衡度，由圖6 可知，在初始階段，當控制器個數較少時，三種算法的負載失衡度較高，是由于網絡中控制器接入節點個數分布的不均衡所導致；隨著控制器個數的增加，失衡度迅速下降，特別地，采用OBA-CP 算法的失衡度較NCPSO 算法和SPEA-Ⅱ算法分別降低了0.73%和0.96%。三種算法得到的失衡度均在0.40 以下且效率對比基本持平。

圖7 比較了不同算法下的平均計算用時，由圖7可知，采用SPEA-Ⅱ算法的計算用時遠高于OBA-CP算法和NCPSO 算法，約為OBA-CP 算法的5 倍左右，這是由于SPEA-Ⅱ算法存在搜索效率低的問題，而采用OBA-CP 算法具有更短的運行時間，這是由于改進的蝙蝠算法具有較好的收斂性和全局搜索能力，有利于搜索過程快速收斂到Pareto 解最優前沿。

Fig.7 Average calculation time of different algorithms圖7 不同算法的平均計算用時

由圖4～圖7 的分析可知，OBA-CP 算法通過對網絡拓撲中控制器各部署位置的網絡性能進行評估以獲取近似最優解，利用優化策略提高蝙蝠算法的收斂速度和運算效率。性能對比上采用OBA-CP 算法的平均時延和計算用時略優于NCPSO 算法，采用OBA-CP 算法的平均時延、中斷概率和計算用時顯著優于SPEA-Ⅱ算法。

5 結束語

本文針對邏輯集中控制的航空信息網絡環境，綜合考慮全局平均時延、網絡可靠性和控制器負載均衡等三項性能尺度指標，建立了軟件定義航空信息網絡控制器部署問題的多目標組合優化模型，采用改進的蝙蝠優化算法進行求解，充分利用其較好的尋優功能獲得滿足特定條件的航空信息網絡控制器部署問題的Pareto 解集。仿真結果表明，所搭建的模型可實現多控制器的合理有效部署，提出的算法具有更高的效率，能夠快速收斂到Pareto 最優前沿。與SPEA-Ⅱ算法和NCPSO 算法相比，改進算法在三項指標上均有良好的網絡性能，對于解決軟件定義航空信息網絡多控制器優化部署問題提供了一種新思路。由于控制器的部署對于軟件定義航空信息網絡性能具有重要影響，其中還存在很多問題需要解決，下一步將對一致性、域內連通性等方面展開研究。