高可靠性軟件定義航空光信息網絡的控制器分布優化策略

趙　靜, 趙尚弘, 趙衛虎, 李勇軍

(1. 空軍工程大學信息與導航學院, 陜西 西安 710077; 2. 國防科技大學信息通信學院, 陜西 西安 710106)

0　引　言

航空網絡是以空中高速飛行的飛機為空中無線通信的主要節點,以節點間無線通信連接為鏈路組成的網絡,具有覆蓋廣、高動態、接入量大、任務多樣化等特點[1-2]。當前基于機間寬帶射頻數據鏈構建的航空骨干網存在帶寬資源受限、強電磁干擾環境下通信能力弱等問題,而激光通信鏈路具有低截獲、高速率、抗干擾等特點,是構建航空骨干網絡的理想方案。作為未來航空網絡的發展方向,基于激光鏈路的航空骨干網能夠連接衛星網絡實現大范圍空域的綜合業務傳輸,并通過無線射頻鏈路與各類戰術子網形成互聯互通的通信網絡。然而,利用現有的網絡技術來構建未來航空網絡存在著許多矛盾與挑戰,其中最突出的是通用互聯網協議(Internet protocol,IP)網絡與上層應用多樣化特征和需求之間的矛盾[3-4]。

軟件定義網絡(software defined network,SDN)的出現為解決上述問題提供了契機。SDN將控制平面從傳統的路由交換設備中解耦出來,使未來網絡中的基礎交換設備只具有轉發功能,轉發平面具有協議無關性、集中化和可編程性。由控制器組成的邏輯上集中控制平面能夠檢測和采集鏈路狀況和組網信息,具有根據用戶需求,對網絡資源進行調配的能力,同時具有策略制定和流表項下發功能[5-7]。集中式控制器平面可擴展性較差,易引起連接中斷,嚴重影響網絡可靠性,在大規模網絡中其性能急劇下降。因此,采用邏輯上集中、物理上分布的控制器部署方式成為未來軟件定義航空網絡的重要解決方法。控制器部署問題需要考慮兩個主要問題,即在網絡中部署控制器的數量及部署位置[8-10]。

目前國內外關于控制器部署主要是圍繞時延、可靠性、流量處理開銷等優化指標來確定的。文獻[11]主要解決在給定網絡拓撲下,需要多少個控制器以及怎樣部署這些控制器這兩個問題,通過定義控制器與交換機之間平均/最大傳播時延兩個指標來分析控制器部署問題。文獻[12]以平均時延最短和控制器數量較少為優化目標,采用基于二值粒子群優化算法的方法獲得控制器部署問題的非劣最優解集合。文獻[13]定義控制路徑失效百分比的期望值作為可靠性指標,應用l-w-greedy算法和模擬退火算法解決了SDN中可靠性感知的控制器部署問題。

基于軟件定義網絡思想,提出了以激光通信鏈路為骨干互連，以節點間無線通信連接為鏈路組成的軟件定義航空光信息網絡的網絡架構，分析了軟件定義航空光信息網絡中控制器部署問題的特點,針對航空光信息網絡中的控制器部署問題進行研究,建立了基于網絡可靠性的整數規劃模型,提出融合人工免疫策略、小生境思想和改進遺傳算法的混合優化算法,以實現對基于可靠性模型的優化。最后,以包含34個航空節點的航空網絡為仿真場景,考慮了網絡中斷概率和控制器數量兩個瓶頸指標,采用仿真對比實驗,驗證了本文算法在收斂速度、部署結果方面的性能。

1　軟件定義航空光信息網絡控制器部署特點

軟件定義航空光信息網絡根據未來航空信息網絡的應用需求,基于軟件定義網絡的先進思想設計的具有開放可擴展、信息資源高效靈活調度、面向航空服務的新一代航空信息網絡,能夠為未來航空通信系統提供差異化服務。其主要特點是通過構建具有不同QoS等級的虛擬網絡,使得不同等級的航空應用可以根據特定的業務和應用需求選擇合適的服務等級,從而實現全網差異化服務,構建靈活高效的新型信息傳輸模式,極大提高網絡通信效能。本文提出了基于SDN技術的航空光信息網絡概念,軟件定義航空光信息網絡的網絡架構如圖1所示。

圖1　軟件定義航空光信息網絡系統示例

由圖1可知,軟件定義航空光信息網絡主要由3部分組成:①移動子節點,主要包括空中接入節點、地面移動節點等。可通過短波、超短波、無線激光通信等無線通信鏈路實現多種狀態數據的收集和傳輸。②航空骨干節點,主要包括飛行位置和特性相對穩定的大型飛機平臺,通過激光鏈路構建骨干鏈路,作為數據接收器接收并傳輸來自移動節點的狀態數據。航空骨干節點同時可作為網絡控制器實現對網絡的管理與控制。③帶內、帶外控制信道,能夠在移動節點及控制器之間實現控制信息的傳輸與交換。

特別地,軟件定義航空信息網絡控制器部署問題具有以下特點:

(1) 節點移動性。航空網絡中,節點間相對運動速率大,網絡拓撲快速動態變化,同時由于機間激光束對準難度大[14],導致傳輸節點與控制器的連接中斷,進而造成傳輸節點的不可用,帶來航空網絡連通性問題。

(2) 節點傳輸終端故障。受器件性能、傳輸環境等影響,航空節點上通信終端會發生故障導致該天線資源在某段時間內失效,則在該段時間內與該控制器相連的傳輸節點需要進行重新安排,這對網絡連通性和故障恢復能力帶來極大挑戰。

(3) 鏈路傳輸不穩定性。航空網絡中激光鏈路受大氣信道影響嚴重,大氣吸收、散射及光強閃爍效應會造成激光大氣衰減效應。微波射頻鏈路容易受到大氣中雨、雪、霧等自然狀況、路徑衰落、多徑效應或無線干擾等影響。因此航空鏈路容易出現頻繁的鏈路中斷和重建,具有高誤碼率、大鏈路時延等特點[15],這給航空網絡的連通性、可用性帶來問題。

(4) 三維、大尺度的節點分布特性。航空通信網絡中,不同飛機節點的飛行高度存在差異性,飛機節點稀疏分布在大尺度三維空域場景中,導致節點間鏈路傳輸時延差異較大。

根據以上分析可知，由于軟件定義航空光信息網絡中節點運動及鏈路傳輸的特點,網絡中控制器故障、轉發節點及轉發鏈路故障是影響網絡性能的重要因素。

2　控制器部署模型

控制器部署是非確定性多項式難(non-deterministic polynomial hard, NP-hard)問題。由上述對軟件定義航空信息網絡的控制器部署問題特點分析可知,控制器故障、轉發節點及轉發鏈路故障是影響軟件定義航空信息網絡中控制器部署問題的關鍵,因此可以將該問題看作一類基于網絡可靠性的整數規劃模型。考慮網絡元素的中斷概率,對軟件定義航空信息網絡中控制器分布問題的約束條件作以下描述:

(1) 假設G(V,E)表示網絡拓撲,V代表拓撲中網絡節點集合,E?V×V代表網絡節點之間鏈路的集合,鏈路權重代表傳輸時延,設n為網絡節點個數,有n=|V|。

(2) 假設網絡節點及鏈路之間都是獨立的。對每一個物理網絡元素l∈V∪E,定義pl為元素l的中斷概率,0

(3) 給定兩個節點s及t,設pathst為從s到t之間的最短路徑,假設網絡節點與控制器之間的控制路徑取最短。

(4) 定義Vc?V為控制器可選位置集合。設M?Vc代表即將分布在網絡中的控制器集合,|M|=k為所需部署的控制器個數。

(5) 交換機與控制器可重復使用同一網絡節點,此種情況下,認為二者之間路徑的中斷概率為0;

(6) 設i∈V,j∈Vc,yj=1代表控制器布置在位置j,否則為0。

(7)xij=1代表yj=1且交換節點i分配給了控制器j,或yi=yj=1且控制器i,j之間有鄰接路徑,否則為0。設hijl=1代表i與j之間控制路徑經過l,否則為0。

優化目標函數是軟件定義航空信息網絡的全網中斷概率。可靠性優化問題模型為

(1)

(2)

(3)

(4)

yi,xij,hijl∈{0,1};?i∈V,j∈V,l∈V∪E

(5)

3　控制器部署混合優化算法設計

3.1　混合優化算法流程

融合人工免疫策略、小生境思想和改進遺傳算法的混合優化算法總流程如圖2所示。算法主要由5大函數模塊組成,分別為:主函數模塊、適應度值計算模塊、小生境淘汰模塊、精英保留的自適應遺傳算法模塊和人工免疫模塊。

圖2　混合優化算法流程

由圖2可知，主函數模塊主要負責對算法的各類參數進行設置和對遺傳過程的控制,最后生成控制器部署序列和目標適應度值。設置的參數包括初始化種群規模及最大遺傳代數、自適應交叉和變異參數、及小生境相關參數和免疫記憶庫的容量等參數。

3.2　基于精英保留的自適應遺傳算法模塊

3.2.1問題編碼

遺傳算法是針對離散問題提出的進化算法,其思想來源于“物競天擇、適者生存”的自然法則,具有很強的全局搜索能力。算法中每個個體代表問題的一個解,稱為染色體,解的好壞用適應度值來評價。控制器部署問題的每個可行解即為一個控制器分配方案,每個分配方案Xi有n個決策變量,即染色體的n個基因,代表n個交換節點。每個編碼基因Xi=[xi1,xi2,…,xin]代表一種控制器部署方案,xin表示在第i個分配方案中第n個交換節點所選擇的控制器。

3.2.2自適應交叉、變異算子

本文設計混合的自適應交叉、變異算子,令Pc和Pm分別為交叉和變異概率。當種群陷入局部最優時,采用小生境淘汰后,新個體可能圍繞小生境周邊,種群多樣性較差。因此,此時選擇較大的Pc和Pm可增加新個體的產生,利于跳出局部最優。在算法初始階段或種群適應度值較分散時,選擇較小的Pc和Pm利于保留精英個體,可加快算法的收斂;因此,采用式(6)和式(7)具體計算自適應交叉概率和變異概率。

(7)

式中,參數k1、k2、k3、k4為交叉、變異參數,是0到1之間的變量,其大小在搜索過程中將根據人工免疫模塊中“疫苗接種”的情況進行調整,具體調整方法如式(10)所示。favg為種群的平均適應度值,fmin為種群的最小適應度值,fc為交叉個體平均適應度值,fm為要變異個體的適應度值。

3.2.3精英保留策略

傳統遺傳算法中個體被選擇的概率與個體適應度值呈正比,通常需要對目標值進行調整后作為適應度值,而調整不當將影響算法的性能。為克服此不足,采用精英保留策略的遺傳算法,將每代最優秀的部分個體直接遺傳到下代。因此適應度函數只需反映個體的優劣,直接采用目標值即可。由于個體適應度值的計算量較大,因此需充分利用已完成計算的個體;并且采用小生境淘汰可能降低算法的收斂速度。選擇時將父代個體與子代個體合并為大種群,將其最優的一半種群個體直接保留到下代,參與下代競爭,并將這部分精英個體作為父代以產生新個體。因此,直接保留的精英個體適應度值不需再計算,從而節省了計算資源,加快了收斂速度。

3.3　小生境思想

為避免種群聚集在局部最優值附近,以保持種群多樣性,提高算法搜索效率和全局優化能力,算法引入小生境思想,采用動態變化的小生境距離參數,對搜索到最優值附近的次優個體進行懲罰,從而減小聚集在局部最優值附近個體被選擇到下一代的概率。

定義1設個體Xi與種群中所有個體的最小歐氏距離為其與種群的差異Di,即

i=1,2,…,Nscale

(8)

式中,變量Nscale為種群規模。

定義2設Nniche個最優個體與種群中平均差異為種群的小生境距離L,當平均差異小于1時,取小生境距離L=1,即

(9)

3.4　人工免疫模塊

(1) 疫苗接種

傳統遺傳算法在收斂到局部最優值的搜索后期,會頻繁產生曾經搜索過的個體,不但浪費計算資源,耽誤計算時間,還將造成算法尋優能力的下降。針對此問題,本文借鑒人工免疫算法思想,將歷史搜索過的較優個體記憶成“抗體”,產生的新個體視作“嫌疑抗原”,經過新個體與系統接種的“疫苗”比對,消除其嫌疑或將其定性為“抗原”,則分別采取“釋放”或“吞噬”操作。當進行“吞噬”操作后,采用“免疫克隆”方法重新產生新個體來替代這個個體。在產生新個體時,采用式(6)和式(7)計算自適應交叉、變異概率。

在搜索過程中一旦出現重復個體,則將當前種群放入“免疫記憶庫”，隨著搜索的進行,用搜索到的較優個體更新“記憶庫”中最差的個體。在“疫苗接種”過程中,需要將新個體與“抗體”對比,若直接逐個比較,計算量大。因此,將記憶庫中的個體(免疫知識)進行整理,建立記憶庫個體基因的索引;當新個體與之比較時,可采用“二分法”檢索,則計算量將成指數級減少。

(2) 自適應參數調整

在“疫苗接種”過程中,根據本代種群個體的重復率,調整自適應遺傳算法中的交叉、變異參數。當重復個體較多時,放大交叉、變異參數以增加種群的多樣性,減少重復個體的出現,交叉、變異參數更新公式為

(10)

式中,變量β為放大因子,取值范圍為1到2之間(通常取1至1.1之間小數),β越大，變異參數放大得越快,在仿真分析中一般根據經驗給定變量β取值。

4　仿真及結果分析

為了驗證算法的有效性,采用34個節點的航空網絡拓撲,對于每個節點標號,假設每個節點均可放置交換機,控制器部署在交換機的位置上。在航空網絡拓撲中,采用時延作為鏈路的權重,鏈路權重為[1,10]的均勻隨機數;為了保證網絡連通性,采用網絡組件故障率較小的網絡場景,設單個節點和鏈路的中斷概率為區間[0,0.02]和[0,0.04]的隨機數[16-17]。實驗仿真分別采用標準的遺傳算法和本文提出的混合優化算法對問題進行尋優,對比分析兩算法的搜索過程。設置兩算法的種群規模Nscale=80,迭代次數為100,根據多次重復試驗,將自適應交叉、變異參數初始值分別為0.5、0.25、0.05、0.025,放大因子β=1.05。

當控制器數量取k=6時,標準的遺傳算法和混合優化算法的搜索結果如圖3、圖4所示。

圖3　標準遺傳算法搜索過程

圖4　混合優化算法搜索過程

由圖3和圖4的對比單次實驗可知,標準遺傳算法搜索到的最優值是0.077 6;而混合優化算法的最優值是0.073 6,明顯優于標準遺傳算法。由圖3、圖4搜索中期局部放大圖可知,標準遺傳算法在60代左右已完全收斂,最優值保持不變;本文提出的混合優化算法在60代基本收斂之后,最優值還出現了多次小幅度的跳躍,表明混合優化算法在收斂之后仍然能夠跳出局部極值,搜索到更優解。對比兩圖的最優值和平均值曲線可知,到搜索后期標準遺傳算法的種群均值與最優值趨于一致,表明種群個體相似度極高,大部分個體聚集在最優值附近,這是由于標準遺傳算法的多樣性較差。而混合優化算法的種群均值與最優值存在較大差距,表明混合優化算法引入小生境思想和自適應遺傳算子提高了種群的多樣性。

為了驗證本文算法的有效性,在圖5中給出了不同控制器數量條件下,標準遺傳算法和本文提出混合優化算法所得到的部署結果。對每組算例(即在每個控制器個數條件下)進行100次仿真,得到每次仿真的最優值作為該次仿真結果,再對多次仿真結果求取均值,得到不同控制器數量條件下全網中斷概率如圖5所示。

圖5　中斷概率隨控制器數量的變化

由圖5可知，優化目標值,即全網中斷概率隨著控制器數量的變化,代表了某個控制器數量環境下,算法優化部署的有效性。該優化目標值越小,表示部署方案的效果越好。當控制器數量為2～7時,在圖5中分別標出了兩種算法得到的優化結果數值。由圖5可知,在不同的控制器數量條件下,本文提出的混合優化算法得到的部署方案結果均優于標準遺傳算法,特別地,當控制器數量大于6,混合優化算法的尋優結果表現出明顯的優勢。這是由于兩種隨機搜索算法,在有限的迭代過程中標準遺傳算法找到最優值的概率較低,而混合優化算法引入小生境和人工免疫思想,在算法收斂后具有主動改進算法多樣性的策略和跳出局部極值的操作,表明此算法適用于處理此類NP-hard問題。

當控制器數量分別為4、8、12時,采用混合優化算法的算法收斂性能,其中全網中斷概率為每代最優值,其隨迭代次數的變化情況如圖6所示。算法種群規模Nscale=80,迭代次數為150。

圖6　不同控制器數量下中斷概率隨迭代次數的變化

由圖6可知,隨著控制器數量的增加,算法收斂時間變長,收斂速度變慢。特別地,當控制器個數為4時,算法在50代左右基本收斂,而當控制器數量增加到k=8和k=12時,算法迭代至100代和110代左右基本收斂。這是因為控制器數量增加,控制器部署方案的多樣性增加、相應的方案數量增加,因此收斂到較優方案的時間增加。

5　結　論

提出軟件定義航空光信息網絡中基于網絡可靠性的控制器部署策略,利用融合人工免疫策略、小生境思想和改進遺傳算法的混合優化算法,在滿足網絡性能的條件下,為確定在網絡中部署多少個控制器以及如何部署控制器提供了可行方案。該策略以網絡中斷概率為評價指標,算法優化目標是全網中斷概率最小,應用混合優化算法進行迭代進化,得到了最終的優化解集,由此得到了網絡中不同控制器數量條件下的最優部署方案。由于控制器部署會影響軟件定義航空信息網絡的諸多方面,下一步將針對控制器部署問題的多類評價指標,如時延、流量、負載均衡等參數展開研究,提出相應的控制器部署策略。

參考文獻：

[1] KWAK K, SAGDUYU Y, YACKOSKI J, et al. Airborne network evaluation: challenges and high fidelity emulation solution[J]. IEEE Communications Magazine, 2014, 52(10): 30-36.

[2] SCHNELL M, EPPLE U, SHUTIN D, et al. Future aeronautical communications for air-traffic management[J]. IEEE Communications Magazine, 2014, 52(5): 104-110.

[3] MENDONCA M, ASTUTO B, NGUYRN N, et al. A survey of software-defined networking: past, present, and future of the programmable networks[J]. IEEE Communication Surveys and Tutorials, 2014, 16(3): 1617-1634.

[4] 王俊, 陳志輝, 田永春, 等.軟件定義網絡技術在戰術通信網中的應用研究[J]. 通信技術, 2014, 47(12): 1392-1399.

WANG J, CHEN Z H, TIAN Y C, et al. Application of software-defined network technology in tactical communication network[J]. Communications Technology, 2014, 47(12): 1392-1399.

[5] AGUADO A, LOPEZ V, MARHUENDA J, et al. ABNO: a feasible SDN approach for multivendor IP and optical networks[J]. IEEE/OSA Journal of Optical Communications & Networking, 2015, 7(2): A356-A362.

[6] OLIVEIRA B T D, GABRIEL L B, MARGI C B. TinySDN: enabling multiple controllers for software-defined wireless sensor networks[J]. IEEE Latin America Transactions, 2014, 13(11): 3690-3696.

[7] MATIAS J, GARAY J, TOLEDO N, et al. Toward an SDN-enabled NFV architecture[J]. IEEE Communications Magazine, 2015, 53(4): 187-193.

[8] LANGE S, GEBERT S, ZINNER T, et al. Heuristic approaches to the controller placement problem in large scale sdn networks[J]. IEEE Trans.on Network & Service Management, 2015, 12(1): 4-17.

[9] ROS F J, RUIZ P M. On reliable controller placements in software-defined networks[J].Computer Communications,2016,77:41-51.

[10] VOCHIN M, BORCOCI E, AMBARUS T. On multi-controller placement optimization in software defined networking based WANs[C]∥Proc.of the 14th International Conference on Networks, 2015: 261-266.

[11] HEELER B, SHERWOOD R, MCKEOWN N. The controller placement problem[C]∥Proc.of the Workshop on Hot Topics in Software Defined Networks, 2012: 7-12.

[12] 王麗霞,曲樺,趙季紅.軟件定義網絡中應用二值離子化優化的控制器部署策略[J].西安交通大學學報,2015,49(6):67-71.

WANG L X, QU H, ZHAO J H. A strategy of controller placement in software defined networks using binary particle swarm optimization[J]. Journal of Xi’an Jiaotong University, 2015, 49(6): 67-71.

[13] HU Y N, WANG W D, GONG X Y, et al. Reliability-optimized controller on placement for software-defined networks[J]. China Communications, 2014, 11(2): 38-54.

[14] Oppenhauser G. In orbit test result of an operational optical inter-satellite link between ARTEMIS and SPOT4, SILEX[J]. Proc.of SPIE-the International Society for Optical Engineering, 2002, 4635:1-15.

[15] CHENG B N, CHARLAND R, CHRISTENSEN P, et al. Evaluation of a multihop airborne IP backbone with heterogeneous radio technologies[J]. IEEE Trans.on Mobile Computing, 2014, 13(2): 299-310.

[16] LI X, NAHRSTEDT K. Reliability models and evaluation of internal BGP networks[C]∥Proc.of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, 2004: 1593-1604.

[17] HU Y N, WANG W D, GONG X Y, et al. On the placement of controllers in software-defined networks[J]. Journal of China Universities of Posts and Telecommunications, 2012, 19(9): 92-97.