高航航,王 翔,趙尚弘,彭 聰

(空軍工程大學(xué) 信息與導(dǎo)航學(xué)院,西安 710077)

0 概述

航空信息網(wǎng)絡(luò)又稱為機(jī)載網(wǎng)絡(luò)、空基網(wǎng)絡(luò),主要通過(guò)高空航空平臺(tái)進(jìn)行信息發(fā)送、節(jié)點(diǎn)接收或轉(zhuǎn)發(fā),是以節(jié)點(diǎn)間的無(wú)線通信為傳輸鏈路所組成的網(wǎng)絡(luò),其具有高動(dòng)態(tài)、覆蓋范圍廣、作戰(zhàn)任務(wù)多樣化、接入數(shù)據(jù)量大等特點(diǎn)[1-2]。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大和作戰(zhàn)環(huán)境的復(fù)雜化,當(dāng)前的航空信息網(wǎng)絡(luò)也逐漸暴露出一系列問(wèn)題[3],例如:如何對(duì)航空平臺(tái)所獲得的戰(zhàn)場(chǎng)信息進(jìn)行高效共享以及靈活調(diào)度控制;不同的作戰(zhàn)需求在網(wǎng)絡(luò)時(shí)延、可靠性方面具有不同QoS需求,要求網(wǎng)絡(luò)應(yīng)具備較強(qiáng)的差異化服務(wù)能力;軟件控制和硬件轉(zhuǎn)發(fā)緊密耦合的傳統(tǒng)網(wǎng)絡(luò)設(shè)備難以滿足網(wǎng)絡(luò)快速發(fā)展的需要。面向未來(lái)的航空信息網(wǎng)絡(luò)應(yīng)當(dāng)具備提供靈活耦合任務(wù)的差異化網(wǎng)絡(luò)服務(wù)、支持靈活高效的網(wǎng)絡(luò)配置、新網(wǎng)絡(luò)技術(shù)能夠簡(jiǎn)單快速部署等能力,而現(xiàn)有的無(wú)線信息網(wǎng)絡(luò)僅能滿足有限任務(wù)背景下模式固定的信息交互需求,難以支撐未來(lái)作戰(zhàn)中航空集群成員間的靈活協(xié)同。

軟件定義網(wǎng)絡(luò)[4](Software Defined Network,SDN)的出現(xiàn)為解決上述問(wèn)題提供了新思路,其通過(guò)將傳統(tǒng)網(wǎng)絡(luò)設(shè)備中的控制平面和數(shù)據(jù)平面相解耦,利用邏輯集中控制的SDN控制器對(duì)底層轉(zhuǎn)發(fā)設(shè)備進(jìn)行統(tǒng)一管控,控制平面負(fù)責(zé)策略制定與資源調(diào)配,底層轉(zhuǎn)發(fā)設(shè)備進(jìn)行數(shù)據(jù)業(yè)務(wù)的轉(zhuǎn)發(fā),有效提高了網(wǎng)絡(luò)的信息處理和管理控制能力。然而集中式的控制平面存在單點(diǎn)失效、可靠性低、處理能力受限等缺點(diǎn),實(shí)際中需要重點(diǎn)考慮控制平面的可擴(kuò)展性,采用物理上分布、邏輯上集中的多控制器部署架構(gòu)已成為目前解決控制平面可擴(kuò)展性的重要方法。

當(dāng)前對(duì)于SDN多控制器的部署研究主要以地面網(wǎng)絡(luò)為主,評(píng)估指標(biāo)包括網(wǎng)絡(luò)時(shí)延、可靠性、流量開銷等[5]。文獻(xiàn)[6]針對(duì)SDN中控制器部署問(wèn)題進(jìn)行研究,首先定義平均傳輸時(shí)延和最大傳輸時(shí)延,在此基礎(chǔ)上利用實(shí)際網(wǎng)絡(luò)拓?fù)溥M(jìn)行分析,得到控制器數(shù)量對(duì)網(wǎng)絡(luò)時(shí)延的影響以及最優(yōu)時(shí)延和平均時(shí)延的比較結(jié)果,但文中僅考慮了網(wǎng)絡(luò)傳輸時(shí)延。文獻(xiàn)[7]在傳輸時(shí)延基礎(chǔ)上增加發(fā)送時(shí)延以完善現(xiàn)有的時(shí)延模型,并對(duì)該模型是否存在最優(yōu)解進(jìn)行證明,針對(duì)是否發(fā)送時(shí)延分別提出傳輸算法和輸送算法。文獻(xiàn)[8]針對(duì)傳統(tǒng)靜態(tài)部署方案難以應(yīng)對(duì)高動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)浜土髁孔兓@一問(wèn)題,采用一種基于雙門限的交換機(jī)動(dòng)態(tài)遷移策略以解決控制器失效和資源浪費(fèi)問(wèn)題,結(jié)果表明該算法在提升系統(tǒng)吞吐量的同時(shí)可保證控制器間的負(fù)載均衡。文獻(xiàn)[9]以航空網(wǎng)絡(luò)的全網(wǎng)中斷概率最小為目標(biāo),提出一種融合人工免疫策略、小生境思想以及改進(jìn)遺傳算法的混合優(yōu)化算法,仿真表明該算法在獲得更優(yōu)值的同時(shí)其收斂時(shí)間也得到一定減少,但該文未考慮控制器的負(fù)載均衡問(wèn)題。文獻(xiàn)[10]針對(duì)控制路徑平均故障率提出有效控制路徑預(yù)期百分比這一指標(biāo),通過(guò)最大化預(yù)期百分比實(shí)現(xiàn)網(wǎng)絡(luò)控制路徑的強(qiáng)健壯性,但平均故障率僅能反映網(wǎng)絡(luò)整體故障,無(wú)法反映網(wǎng)絡(luò)的最壞狀態(tài)。

航空信息網(wǎng)絡(luò)具有高動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)?、遠(yuǎn)距離傳輸范圍、大尺度節(jié)點(diǎn)分布以及不穩(wěn)定的鏈路質(zhì)量,因此,傳統(tǒng)基于地面網(wǎng)絡(luò)的多控制器架構(gòu)、部署算法等不再適用。本文在總結(jié)航空信息網(wǎng)絡(luò)特點(diǎn)的基礎(chǔ)上,對(duì)傳統(tǒng)平面式和層次式SDN多控制器架構(gòu)進(jìn)行改進(jìn),設(shè)計(jì)一種混合式多控制器部署架構(gòu)。針對(duì)多控制器負(fù)載不均衡問(wèn)題,提出改進(jìn)的集群域劃分算法,并以網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路中斷概率為變量,將網(wǎng)絡(luò)控制路徑故障率最小作為優(yōu)化目標(biāo),設(shè)計(jì)改進(jìn)的離散粒子群優(yōu)化算法實(shí)現(xiàn)多控制器部署。

1 模型分析

1.1 軟件定義航空信息網(wǎng)絡(luò)架構(gòu)特點(diǎn)

航空信息網(wǎng)絡(luò)位于天基網(wǎng)絡(luò)和地面網(wǎng)絡(luò)之間,如圖1所示,其對(duì)上可與天基平臺(tái)建立信息鏈路,實(shí)現(xiàn)天基信息及時(shí)注入航空信息網(wǎng)絡(luò),為航空平臺(tái)提供信息支持,對(duì)下可與地面信息系統(tǒng)建立信息鏈路以保證地面指控信息的輸入,實(shí)現(xiàn)綜合信息處理分發(fā)、空中指揮控制和協(xié)同傳輸。目前航空信息網(wǎng)絡(luò)正朝著網(wǎng)絡(luò)異構(gòu)化、業(yè)務(wù)多樣化、功能復(fù)雜化的方向發(fā)展,加之網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性、鏈路的不穩(wěn)定性,其對(duì)當(dāng)前的網(wǎng)絡(luò)性能提出更高的要求?，F(xiàn)有的無(wú)線信息網(wǎng)絡(luò)雖然在傳輸可靠性、端到端時(shí)延、傳輸速率等網(wǎng)絡(luò)傳輸性能指標(biāo)上能夠支撐現(xiàn)有的航空網(wǎng)絡(luò)進(jìn)行一定程度的作戰(zhàn)協(xié)同,但其本質(zhì)上并非契合未來(lái)航空集群作戰(zhàn)的應(yīng)用背景,網(wǎng)絡(luò)僅能滿足有限任務(wù)背景下模式固定的信息交互需求,與作戰(zhàn)任務(wù)缺乏靈活的耦合關(guān)系,而構(gòu)建一個(gè)基于SDN的航空信息網(wǎng)絡(luò)將更符合未來(lái)作戰(zhàn)對(duì)網(wǎng)絡(luò)各方面性能的要求。

圖1 航空信息網(wǎng)絡(luò)示意圖

軟件定義航空信息網(wǎng)絡(luò)[3,11]利用SDN邏輯集中控制的網(wǎng)絡(luò)管控策略,能夠?qū)崟r(shí)掌握航空信息網(wǎng)絡(luò)全局視圖,實(shí)現(xiàn)對(duì)航空信息網(wǎng)絡(luò)中業(yè)務(wù)流量的優(yōu)化調(diào)度,滿足網(wǎng)絡(luò)中多用戶需求,改善整體性能?？刂破鞑渴鹱鳛闃?gòu)建控制平面的前提,對(duì)提升網(wǎng)絡(luò)性能具有重要意義,而控制平面中單控制器通常存在單點(diǎn)失效、處理能力受限等問(wèn)題,因此,多控制器部署架構(gòu)已經(jīng)成為目前有效的解決方案。多控制器部署架構(gòu)包括平面式架構(gòu)[12]、垂直式架構(gòu)[13]和混合式架構(gòu)[14]。由于高空節(jié)點(diǎn)的移動(dòng)性和鏈路的不可靠性易造成網(wǎng)絡(luò)通信中斷,在瞬息萬(wàn)變的戰(zhàn)場(chǎng)中控制器節(jié)點(diǎn)也存在一定的故障風(fēng)險(xiǎn),因此地面網(wǎng)絡(luò)中的平面式多控制器架構(gòu)將不再適用?？紤]到上述因素,航空信息網(wǎng)絡(luò)應(yīng)采用混合式的控制器架構(gòu)對(duì)網(wǎng)絡(luò)進(jìn)行集中管控,本文借鑒文獻(xiàn)[15]所構(gòu)建的混合式控制器架構(gòu)模型,結(jié)合具體的應(yīng)用場(chǎng)景設(shè)計(jì)一種航空信息網(wǎng)絡(luò)下的混合式多控制器架構(gòu),如圖2所示。

圖2 混合式多控制器架構(gòu)示意圖

混合式多控制器架構(gòu)中的控制平面由全局控制器(Global Controller,GC)和本地控制器(Local Controller,LC)組成,其中:GC可從全域戰(zhàn)場(chǎng)視角對(duì)航空信息網(wǎng)絡(luò)實(shí)施集中管控,應(yīng)部署在信息綜合處理能力和生存能力較強(qiáng)的飛機(jī)節(jié)點(diǎn)上,如指通機(jī)、預(yù)警機(jī)等,其控制優(yōu)先級(jí)最高;LC負(fù)責(zé)管控其自身控制區(qū)域內(nèi)的網(wǎng)絡(luò)節(jié)點(diǎn),考慮到航空信息網(wǎng)絡(luò)的實(shí)際需求及特點(diǎn),可在每個(gè)航空平臺(tái)上布置LC,實(shí)際中網(wǎng)絡(luò)根據(jù)自身狀態(tài)及GC的部署策略開啟或關(guān)閉相應(yīng)的LC,實(shí)現(xiàn)對(duì)其動(dòng)態(tài)部署。

1.2 數(shù)學(xué)建模

軟件定義航空信息網(wǎng)絡(luò)中的多控制器部署問(wèn)題描述如下:

1)G(V,E,Vc,Ec)表示航空信息網(wǎng)絡(luò)拓?fù)?其中,V代表網(wǎng)絡(luò)中飛機(jī)節(jié)點(diǎn)集合,E代表飛機(jī)節(jié)點(diǎn)間的通信鏈路集合,Vc代表網(wǎng)絡(luò)中部署的控制節(jié)點(diǎn)集合,Ec代表控制路徑集合,且Vc?V,Ec?E。

2)本文假定已知混合式多控制器架構(gòu)下GC的部署個(gè)數(shù)和位置,僅對(duì)控制平面中的LC進(jìn)行部署,下文所提的控制節(jié)點(diǎn)與LC節(jié)點(diǎn)均為同一概念。

3)考慮到實(shí)際情況,網(wǎng)絡(luò)中所有飛機(jī)節(jié)點(diǎn)均應(yīng)布置控制器,控制器按照具體部署策略相應(yīng)打開或關(guān)閉。當(dāng)飛機(jī)節(jié)點(diǎn)i上的控制器打開時(shí),節(jié)點(diǎn)i為控制節(jié)點(diǎn);當(dāng)控制器關(guān)閉時(shí),節(jié)點(diǎn)i為交換節(jié)點(diǎn),也稱作普通傳輸節(jié)點(diǎn),網(wǎng)絡(luò)中任意節(jié)點(diǎn)均有機(jī)會(huì)成為控制節(jié)點(diǎn)或交換節(jié)點(diǎn)。

4)控制路徑包括LC與GC節(jié)點(diǎn)之間的路徑以及交換節(jié)點(diǎn)與LC節(jié)點(diǎn)間相連的路徑。由于GC的優(yōu)先級(jí)最高,因此GC之間單獨(dú)配置控制路徑,實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)視圖信息的共享。其余控制路徑為帶內(nèi)方式,不單獨(dú)配置控制路徑,即控制信息和數(shù)據(jù)信息通過(guò)相同的路徑進(jìn)行傳輸。

5)假定網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈路發(fā)生故障的概率均是獨(dú)立的,po和pv分別表示鏈路中斷概率和節(jié)點(diǎn)失效概率,有0≤po<1,0≤pv<1。

6)網(wǎng)絡(luò)中每個(gè)LC在同一時(shí)間內(nèi)只能由唯一的GC控制,每個(gè)交換節(jié)點(diǎn)也只能由唯一的LC控制。

為方便描述多控制器部署問(wèn)題,現(xiàn)對(duì)具體數(shù)學(xué)模型中的符號(hào)進(jìn)行說(shuō)明,如表1所示。

表1 符號(hào)說(shuō)明

根據(jù)上述分析,可將軟件定義航空信息網(wǎng)絡(luò)中的多控制器部署問(wèn)題建立如下目標(biāo)函數(shù):

minf=f1+f2

(1)

(2)

(3)

s.t.pv,po∈[0,1);?v∈V,e∈E

(4)

btjcl=htl;l∈Vc,t,j∈V

(5)

(6)

(7)

l∈Vc,e∈E,g∈{GC}

(8)

式(1)表示最小化控制路徑故障率;式(2)表示LC節(jié)點(diǎn)和交換節(jié)點(diǎn)間的控制路徑故障率;式(3)表示LC節(jié)點(diǎn)與GC節(jié)點(diǎn)間的控制路徑故障率;式(4)表示節(jié)點(diǎn)、鏈路失效概率取值范圍;式(5)表示節(jié)點(diǎn)t受控制節(jié)點(diǎn)l所管控;式(6)表示網(wǎng)絡(luò)中部署的控制器個(gè)數(shù);式(7)表示一個(gè)交換節(jié)點(diǎn)只能由一個(gè)LC節(jié)點(diǎn)管控;式(8)表示各式中變量的取值范圍。

2 算法設(shè)計(jì)

2.1 航空集群域劃分算法

在航空信息網(wǎng)絡(luò)中存在著功能各異的飛機(jī)節(jié)點(diǎn),本文參考文獻(xiàn)[15],假定在執(zhí)行某作戰(zhàn)任務(wù)過(guò)程中其網(wǎng)絡(luò)拓?fù)浔３窒鄬?duì)穩(wěn)定,隨著作戰(zhàn)任務(wù)變化,網(wǎng)絡(luò)拓?fù)湟蚕鄳?yīng)改變,本文在此基礎(chǔ)上對(duì)航空信息網(wǎng)絡(luò)進(jìn)行進(jìn)一步集群域劃分。

2.1.1 k-means聚類算法

k-means是一種簡(jiǎn)單高效、快速實(shí)現(xiàn)的基于劃分原理的聚類算法,其將數(shù)據(jù)集U={x1,x2,…,xn}按照某種準(zhǔn)則劃分為若干個(gè)子集,其中k為聚類數(shù)目,且聚類滿足以下約束:

Uj≠?,j=1,2,…,k

(9)

Ui∩Uj=?,i,j=1,2,…,kandi≠j

(10)

圖3所示為傳統(tǒng)k-means算法流程,其中輸入為數(shù)據(jù)集U和聚類個(gè)數(shù)k(見式(11)),輸出為聚類劃分結(jié)果,算法結(jié)束的條件為聚類中心不再發(fā)生變化或變化范圍在規(guī)定的閾值內(nèi)。

(11)

圖3 傳統(tǒng)k-means算法流程

由于k-means算法是隨機(jī)選擇初始聚類中心的,聚類結(jié)果會(huì)隨初始聚心的改變而改變,因此本文引入聚類質(zhì)量評(píng)估函數(shù)作為聚類效果的評(píng)價(jià)準(zhǔn)則,其中對(duì)聚類質(zhì)量評(píng)估函數(shù)定義如下:

(12)

(13)

式(12)表示各聚類的內(nèi)距離和,J值越小則代表聚類的效果越優(yōu);式(13)表示集群域j的聚心。

2.1.2 改進(jìn)k-means聚類算法

傳統(tǒng)k-means聚類算法是一種貪婪算法,容易陷入局部最優(yōu),并且該算法選擇的初始聚心極有可能偏離數(shù)據(jù)密集區(qū),若初始聚心位于孤點(diǎn)或者偏遠(yuǎn)點(diǎn),則會(huì)導(dǎo)致劃分的集群域性能變差。針對(duì)該問(wèn)題,本文參考文獻(xiàn)[16-17]中提出的離群因子對(duì)k-means算法初始聚心位置隨機(jī)這一不足加以改進(jìn),設(shè)計(jì)一種基于離散因子(Discrete Factor,DF)的改進(jìn)k-means算法,通過(guò)計(jì)算各節(jié)點(diǎn)的離散因子值,并選擇合適的離散因子值所對(duì)應(yīng)的節(jié)點(diǎn)作為集群域初始中心,避免網(wǎng)絡(luò)中的孤點(diǎn)或離散點(diǎn)成為初始聚心,最終得到的集群域也將更加合理。算法描述具體如下:

定義1數(shù)據(jù)x的第k距離

x的第k距離dk(x)指在數(shù)據(jù)集合U中存在數(shù)據(jù)o,數(shù)據(jù)o與數(shù)據(jù)x之間的距離記為d(o,x),當(dāng)滿足下述條件時(shí),x的第k距離dk(x)等于d(o,x):

1)數(shù)據(jù)集U中至少存在k個(gè)數(shù)據(jù)o′∈D{x}滿足d(x,o′)≤d(x,o) 。

2)數(shù)據(jù)集U中至多存在k-1個(gè)數(shù)據(jù)o′∈D{x}滿足d(x,o′)

定義2數(shù)據(jù)x的第k距離鄰域

數(shù)據(jù)x的第k距離鄰域指不超過(guò)數(shù)據(jù)x的第k距離內(nèi)所有數(shù)據(jù)的集合,其表達(dá)式如式(14)所示,可以看出,若該集合較大,則說(shuō)明數(shù)據(jù)x的第k距離鄰域較大,表明數(shù)據(jù)偏離程度較大,反之偏離程度較小。

Nk(x)={o∈D{x}|d(x,o)≤dk(x)}

(14)

定義3數(shù)據(jù)x的離散因子

數(shù)據(jù)x的離散因子Dk(x)指在(x)的第k距離范圍內(nèi),集合U中數(shù)據(jù)的平均分布密度大小,Dk(x)值越大,則x越可能成為離群點(diǎn),其計(jì)算公式如下:

(15)

(16)

本文利用歐式距離計(jì)算出數(shù)據(jù)x的第k距離大小,并根據(jù)式(14)得到數(shù)據(jù)x的第k距離鄰域,最后在x的鄰域內(nèi)計(jì)算出其余節(jié)點(diǎn)相對(duì)x的平均分布狀況,依次對(duì)集合U內(nèi)數(shù)據(jù)進(jìn)行計(jì)算,得到集合U內(nèi)所有節(jié)點(diǎn)的平均分布密度大小。本文基于離散因子的改進(jìn)k-means算法描述如下,其通過(guò)計(jì)算集合U中各數(shù)據(jù)的離散因子值,找出離散因子值較小的節(jié)點(diǎn)作為候選初始聚心集合,在該集合中通過(guò)計(jì)算距離進(jìn)而得出最終的聚心位置。

算法1改進(jìn)的k-means算法

輸入數(shù)據(jù)集U,聚類個(gè)數(shù)k,取樣系數(shù)α

輸出聚類結(jié)果Uj(j=1,2,…,k)

1.for each xi∈U

2.計(jì)算xi的DF值,并將計(jì)算結(jié)果按照升序排列到ListDF中

3.選擇ListDF中前n×α個(gè)數(shù)據(jù),生成候選初始聚心集合CandidateClusterSet

4.令C=?,在CandidateClusterSet中選擇DF值最小的數(shù)據(jù)xi作為初始聚心C1,C={C1},并從CandidateClusterSet中刪除該數(shù)據(jù),Update CandidateClusterSet

5.for each xi∈CandidateClusterSet

6.計(jì)算數(shù)據(jù)xi與C1之間的歐氏距離,選擇距離最大的數(shù)據(jù)點(diǎn)作為第2個(gè)初始聚心C2,C={C1,C2},并從Candidate ClusterSet中刪除該數(shù)據(jù),Update CandidateClusterSet

7.for each xi∈CandidateClusterSet

8.分別計(jì)算xi與{C1,C2}之間的距離,將計(jì)算結(jié)果相加,選擇最大值所對(duì)應(yīng)的數(shù)據(jù)作為下一個(gè)初始聚心C3,C={C1,C2,C3},并從CandidateClusterSet中刪除該數(shù)據(jù),Update CandidateClusterSet

模糊PID控制器采用單片機(jī)編程設(shè)計(jì)，由于MSP430單片機(jī)內(nèi)部沒(méi)有專用的浮點(diǎn)數(shù)處理器，因此在數(shù)據(jù)的處理過(guò)程中，浮點(diǎn)數(shù)的計(jì)算是通過(guò)特定的算法程序來(lái)實(shí)現(xiàn)，如果采用浮點(diǎn)數(shù)計(jì)算來(lái)進(jìn)行數(shù)據(jù)處理，將消耗大量的CPU資源，同時(shí)數(shù)據(jù)的處理周期較長(zhǎng)，影響其單片機(jī)的實(shí)時(shí)控制，因此在數(shù)據(jù)處理時(shí)應(yīng)盡量少用實(shí)型數(shù)據(jù)計(jì)算處理。在實(shí)際設(shè)計(jì)中將浮點(diǎn)數(shù)的小數(shù)部分放大，在滿足精度要求的基礎(chǔ)上，盡可能采用整形數(shù)據(jù)來(lái)處理數(shù)據(jù)計(jì)算，也可以采用長(zhǎng)整形來(lái)實(shí)現(xiàn)數(shù)據(jù)的處理（見圖4）。

9.Repeat and Update C

10.until i>k

11.輸出k個(gè)初始聚心結(jié)果uj( j=1,2,…,k)

12.從得到k個(gè)初始聚心出發(fā),利用最短路徑算法求出聚類結(jié)果

根據(jù)算法1可得到最終的聚心分布結(jié)果,相比于傳統(tǒng)k-means算法,該算法有效地避免了聚心位于孤點(diǎn)或偏遠(yuǎn)點(diǎn),使得聚心分布更加合理。算法在構(gòu)造集群域時(shí)主要考慮節(jié)點(diǎn)的分布特點(diǎn),而在實(shí)際部署過(guò)程中由于LC存在處理能力受限等問(wèn)題,易造成某LC負(fù)載過(guò)載或欠載,從而引起數(shù)據(jù)擁塞或不能充分利用資源等問(wèn)題,本文在此基礎(chǔ)上加入LC負(fù)載受限這一約束條件對(duì)集群域劃分結(jié)果進(jìn)行優(yōu)化調(diào)整。通過(guò)引入負(fù)載均衡指數(shù)B對(duì)各集群域間的負(fù)載是否均衡進(jìn)行計(jì)算判斷,其表達(dá)式如下:

(17)

(18)

其中,a(xi)表示節(jié)點(diǎn)xi向其集群域內(nèi)的LC提交的數(shù)據(jù)請(qǐng)求信息,且集群域內(nèi)所包含節(jié)點(diǎn)提交的總數(shù)據(jù)請(qǐng)求信息不能超過(guò)該集群域內(nèi)LC的負(fù)載能力。LC負(fù)載約束的集群域劃分算法描述如下:

算法2LC負(fù)載約束的集群域劃分算法

輸入初始聚心結(jié)果uj,負(fù)載均衡指數(shù)B

輸出LC負(fù)載約束的聚類劃分結(jié)果Uj

1.利用改進(jìn)k-means算法求出初始聚心。

2.按照最短距離算法將xi分配給各uj,形成集群域Uj。

3.計(jì)算各集群域內(nèi)LC負(fù)載以及負(fù)載均衡指數(shù)B,并判斷B是否符合預(yù)先設(shè)置值,若符合,則轉(zhuǎn)到步驟5,否則執(zhí)行步驟4。

4.將LC過(guò)載對(duì)應(yīng)的集群域內(nèi)節(jié)點(diǎn)分配至距離次短的集群域內(nèi),并轉(zhuǎn)到步驟3。

5.得到LC負(fù)載約束的集群域劃分結(jié)果。

2.2 集群域內(nèi)的控制器部署算法

將航空信息網(wǎng)絡(luò)劃分為多個(gè)集群域后,在集群域中以控制路徑總故障率最小為目標(biāo)進(jìn)行LC部署,其目標(biāo)函數(shù)如式(1)～ 式(8)所示,本文采用一種改進(jìn)的離散粒子群算法BPSO對(duì)目標(biāo)函數(shù)進(jìn)行求解。

2.2.1 離散粒子群算法

離散粒子群優(yōu)化算法是一種基于群體智能理論的優(yōu)化算法,其用空間中的粒子表示問(wèn)題的解,并根據(jù)適應(yīng)度函數(shù)判斷粒子的好壞,粒子依據(jù)個(gè)體最優(yōu)和全局最優(yōu)進(jìn)行位置更新,具有收斂速度快、易實(shí)現(xiàn)等特點(diǎn)[18-20]。BPSO算法中的粒子X(jué)i由d維二進(jìn)制編碼組成,將粒子X(jué)i=(xi1,xi2,…,xid)的每一維限制為0或1,其速度Vi=(vi1,vi2,…,vid)不加限制,每個(gè)位根據(jù)式(19)改變速度,改變后的速度轉(zhuǎn)換為位變量取1的概率,通常利用式(20)中的sigmoid函數(shù)計(jì)算該概率值,在算法搜索過(guò)程中,粒子X(jué)i通過(guò)自身和種群狀態(tài)對(duì)其位置動(dòng)態(tài)調(diào)整,其每一維的速度和位置計(jì)算公式如下:

(19)

(20)

(21)

2.2.2 改進(jìn)的離散粒子群優(yōu)化算法

由上述分析可知,BPSO算法中的sigmoid函數(shù)僅能求解出粒子位取1或者取0的概率,無(wú)法求出粒子位的變化值大小。在實(shí)際生活中,人們?cè)诮鉀Q問(wèn)題時(shí)通常會(huì)依賴以往的個(gè)人歷史經(jīng)驗(yàn)和社會(huì)歷史經(jīng)驗(yàn)[22]。 結(jié)合上述分析,本文提出一種改進(jìn)的離散粒子群算法進(jìn)行求解。

(22)

(23)

(24)

(25)

在尋找最優(yōu)解的過(guò)程中,粒子的好壞程度用適應(yīng)度函數(shù)來(lái)評(píng)價(jià),本文用式(1)作為改進(jìn)BPSO算法的適應(yīng)度函數(shù),即F=f,若某粒子的適應(yīng)度函數(shù)值小,則代表該粒子所對(duì)應(yīng)的解更優(yōu),否則較差,集群域內(nèi)的LC部署算法描述如下:

算法3改進(jìn)BPSO算法的控制器部署算法

輸入各集群域Uj

輸出控制器部署方案

1.設(shè)置粒子種群規(guī)模N,迭代次數(shù)Tmax,控制器數(shù)目k。

2.初始化粒子位置Xi,速度Vi,個(gè)體最優(yōu)pid并計(jì)算全局最優(yōu)pgd。

3.計(jì)算當(dāng)前時(shí)刻粒子的適應(yīng)度值F。

4.比較當(dāng)前時(shí)刻粒子的適應(yīng)度值F與個(gè)體最優(yōu)下的適應(yīng)度值和全局最優(yōu)下的適應(yīng)度值大小,判斷是否更新個(gè)體最優(yōu)和全局最優(yōu)。

5.更新粒子速度Vi并根據(jù)表2更新粒子位置Xi。

6.是否達(dá)到迭代次數(shù)上限T,若未達(dá)到,則執(zhí)行步驟3。

7.判斷控制器數(shù)目i

8.得到不同的控制器個(gè)數(shù)k以及不同的LC部署方案。

上述LC部署算法根據(jù)式(19)對(duì)粒子速度進(jìn)行更新,在對(duì)粒子位置更新時(shí)采用如下策略:

1.產(chǎn)生隨機(jī)數(shù)r = rand()

if r < α then xi= 1 else xi=0

if r < 1- α then xi=1 else xi=0

if r < β then xi= 1 else xi=0

5.else

if r < 1- β then xi= 1 else xi=0

3 仿真結(jié)果分析

3.1 仿真設(shè)置

本文設(shè)置航空信息網(wǎng)絡(luò)的范圍為600 km×600 km,為體現(xiàn)出網(wǎng)絡(luò)的動(dòng)態(tài)性,在該范圍內(nèi)分別隨機(jī)生成2種大小規(guī)模不同的網(wǎng)絡(luò)拓?fù)?小規(guī)模網(wǎng)絡(luò)包括36個(gè)節(jié)點(diǎn)和84條鏈路,大規(guī)模網(wǎng)絡(luò)包括72個(gè)節(jié)點(diǎn)和176條鏈路。假定只有一個(gè)GC,且GC的位置隨機(jī)指定,并忽略GC的數(shù)量和位置對(duì)網(wǎng)絡(luò)性能和部署結(jié)果造成的影響。在部署LC過(guò)程中,假定所有LC的處理能力和負(fù)載容量均相同,所有傳輸節(jié)點(diǎn)向LC傳輸?shù)恼?qǐng)求信息量也相同,節(jié)點(diǎn)和鏈路發(fā)生故障的概率分別為[0,0.03]和[0,0.05]內(nèi)的隨機(jī)數(shù)。此外,為體現(xiàn)2種不同規(guī)模網(wǎng)絡(luò)中部署LC的差異性,在小規(guī)模中的每個(gè)集群域內(nèi)僅部署一個(gè)控制器,而在大規(guī)模網(wǎng)絡(luò)中每個(gè)集群域內(nèi)部署若干個(gè)控制器。

在仿真中同時(shí)設(shè)置Random算法、ANIGA算法[9]和Survivor[23]算法進(jìn)行性能對(duì)比。Random算法在網(wǎng)絡(luò)中隨機(jī)選擇節(jié)點(diǎn)部署LC;ANIGA是一種基于啟發(fā)式的隨機(jī)搜索算法,其通過(guò)循環(huán)迭代找出滿足中斷概率條件時(shí)的LC數(shù)量和位置。Survivor算法通過(guò)選擇不相交路徑最多的節(jié)點(diǎn)部署LC,并按最短距離為其分配交換機(jī)節(jié)點(diǎn)。此外,為排除干擾因素,仿真中將實(shí)驗(yàn)重復(fù)20次,并計(jì)算結(jié)果的平均值作為最終結(jié)果輸出。

3.2 結(jié)果對(duì)比與分析

圖4(a)和圖4(b)分別為傳統(tǒng)k-means算法和改進(jìn)算法在2種不同網(wǎng)絡(luò)中的聚類質(zhì)量評(píng)估函數(shù)值,可以看出,改進(jìn)算法的J值波動(dòng)范圍與k-means算法相比較小,且整體J值均低于k-means算法,這是由于在改進(jìn)算法中加入了負(fù)載均衡模塊,劃分的每個(gè)集群域中節(jié)點(diǎn)個(gè)數(shù)差異較小,進(jìn)而計(jì)算出的J值波動(dòng)范圍較小。此外,由于改進(jìn)算法在選擇初始聚心時(shí)充分考慮到網(wǎng)絡(luò)中各節(jié)點(diǎn)的離散系數(shù),有效地避免了孤點(diǎn)或離散點(diǎn)成為初始聚心,進(jìn)而計(jì)算出的J值更小,說(shuō)明了采用改進(jìn)算法劃分的集群域更合理。

圖4 聚類質(zhì)量評(píng)估函數(shù)值

圖5(a)顯示了在小規(guī)模網(wǎng)絡(luò)中控制路徑故障率隨集群域個(gè)數(shù)變化的情況,可以看出,隨著集群域個(gè)數(shù)的增加,4種算法下的控制路徑故障率均逐漸降低,如集群域個(gè)數(shù)為2、6、10時(shí)對(duì)應(yīng)的控制路徑故障率分別為0.246、0.124、0.093,這是由于隨著集群域個(gè)數(shù)的增加,小規(guī)模網(wǎng)絡(luò)中的控制器數(shù)量隨之增加,控制節(jié)點(diǎn)與交換節(jié)點(diǎn)間的控制路徑增多,進(jìn)而控制路徑的可靠性增大。

圖5(b)顯示了在大規(guī)模網(wǎng)絡(luò)中控制節(jié)點(diǎn)所占比例對(duì)網(wǎng)絡(luò)控制路徑故障率的影響,可以看出,在各集群域中控制節(jié)點(diǎn)比例逐漸增加的同時(shí),控制路徑故障率相應(yīng)地減小,如集群域個(gè)數(shù)為4時(shí),當(dāng)控制節(jié)點(diǎn)比例為0.2、0.3和0.4時(shí)所對(duì)應(yīng)的控制路徑故障率分別為0.386、0.363、0.327,可見在集群域中通過(guò)增加控制器的個(gè)數(shù)能夠有效地降低網(wǎng)絡(luò)控制路徑故障率。

圖5 控制路徑故障率

圖6(a)顯示了小規(guī)模網(wǎng)絡(luò)下控制器間的數(shù)據(jù)同步時(shí)延,可以看出,隨著集群域個(gè)數(shù)的增多,控制器間同步時(shí)延呈現(xiàn)上升的趨勢(shì),如優(yōu)化前和優(yōu)化后同步時(shí)延分別增加了2.741 ms和4.212 ms,這是由于隨著集群域數(shù)量的增加,網(wǎng)絡(luò)中的控制器個(gè)數(shù)隨之增加,控制器節(jié)點(diǎn)間的控制路徑增加,進(jìn)而造成網(wǎng)絡(luò)中的同步時(shí)延增大。此外,隨著集群域個(gè)數(shù)的增多,集群域中節(jié)點(diǎn)數(shù)量減少,控制器部署位置的差異度也隨之減小,從而優(yōu)化前后控制器間同步時(shí)延的差距也逐漸縮小。

圖6(b)顯示了大規(guī)模網(wǎng)絡(luò)下不同控制器數(shù)量對(duì)控制器間時(shí)延的影響,可以看出,隨著集群域個(gè)數(shù)的增加,圖中曲線的變化趨勢(shì)較為緩慢,這是由于當(dāng)集群域個(gè)數(shù)較少時(shí),各集群域內(nèi)的節(jié)點(diǎn)數(shù)量較多,其集群域內(nèi)的控制節(jié)點(diǎn)也相對(duì)較多,而當(dāng)集群域個(gè)數(shù)增多時(shí),集群域內(nèi)的節(jié)點(diǎn)數(shù)量減少,在同等控制節(jié)點(diǎn)數(shù)量比例下其集群域內(nèi)的控制節(jié)點(diǎn)也相應(yīng)減少。因此,盡管集群域個(gè)數(shù)在逐漸增多,但其控制器總數(shù)量與集群域個(gè)數(shù)較少時(shí)網(wǎng)絡(luò)中的控制器總數(shù)量相差不大,意味著在網(wǎng)絡(luò)中不能一味地追求集群域的數(shù)量,如圖中集群域個(gè)數(shù)k=8時(shí)網(wǎng)絡(luò)中的控制器間同步時(shí)延最小,在該集群域數(shù)量下可獲得較小的時(shí)延開銷。此外,在相同的集群域個(gè)數(shù)下,隨著網(wǎng)絡(luò)中控制節(jié)點(diǎn)比例的增加,控制路徑數(shù)量也隨之增加,進(jìn)而使得控制器間同步時(shí)延開銷增大,如當(dāng)控制節(jié)點(diǎn)比例從0.2增加到0.4時(shí),其控制器間平均時(shí)延值分別增加了1.608 ms和2.896 ms。

圖6 控制器間時(shí)延

4 結(jié)束語(yǔ)

本文針對(duì)軟件定義航空信息網(wǎng)絡(luò)架構(gòu)中的控制平面可擴(kuò)展性問(wèn)題展開研究,將航空信息網(wǎng)絡(luò)劃分為多個(gè)集群域。在劃分集群域時(shí),為避免集群域中心位于孤點(diǎn)或偏遠(yuǎn)點(diǎn),提出一種基于離散因子的改進(jìn)k-means算法,結(jié)果表明該算法得到的聚心分布更合理。在集群域內(nèi)LC部署方面,以控制路徑故障率最小為優(yōu)化目標(biāo)設(shè)計(jì)改進(jìn)的BPSO算法。仿真結(jié)果驗(yàn)證了本文在解決控制器部署問(wèn)題方面的有效性。本文重點(diǎn)考慮控制器無(wú)故障下的部署方案,下一步將針對(duì)控制器的可生存性進(jìn)行研究,以確保控制器工作的可連續(xù)性。