一種面向航空集群的集中控制式網(wǎng)絡(luò)部署方法

呂娜，劉創(chuàng)，陳柯帆，曹芳波

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

近年來(lái)，隨著飛行器的更新?lián)Q代，尤其是無(wú)人機(jī)的迅速發(fā)展，航空平臺(tái)的信息化、智能化水平不斷提升，推動(dòng)了空中作戰(zhàn)模式的改變。為了使多個(gè)航空作戰(zhàn)平臺(tái)實(shí)現(xiàn)綜合化、體系化作戰(zhàn)，研究人員將生物集群的理念應(yīng)用到航空作戰(zhàn)領(lǐng)域，提出航空集群的概念[1-3]。航空集群作戰(zhàn)為了實(shí)現(xiàn)多平臺(tái)間戰(zhàn)術(shù)協(xié)同和平臺(tái)能力優(yōu)勢(shì)互補(bǔ)，需要依托機(jī)載網(wǎng)絡(luò)將大規(guī)?？罩衅脚_(tái)靈活組網(wǎng)。

當(dāng)前，以航空數(shù)據(jù)鏈和航空自組網(wǎng)為代表的機(jī)載網(wǎng)絡(luò)一直遵循著傳統(tǒng)分布式網(wǎng)絡(luò)架構(gòu)的設(shè)計(jì)思路[4]。通過(guò)不斷升級(jí)網(wǎng)絡(luò)設(shè)備的各種軟硬件雖然能夠一定程度上保證網(wǎng)絡(luò)性能的提升，但是這種“打補(bǔ)丁”的方式效率很低，不僅使得網(wǎng)絡(luò)變得更加臃腫，也使得網(wǎng)絡(luò)管理與配置過(guò)程復(fù)雜且僵化，導(dǎo)致網(wǎng)絡(luò)服務(wù)能力擴(kuò)展和升級(jí)變得十分困難，難以保障未來(lái)航空集群各成員間的靈巧作戰(zhàn)協(xié)同。

軟件定義網(wǎng)絡(luò)(Software Defined Networking，SDN)的出現(xiàn)為傳統(tǒng)分布式網(wǎng)絡(luò)的發(fā)展帶來(lái)了全新的研究思路，它使網(wǎng)絡(luò)控制平面與數(shù)據(jù)平面分離，通過(guò)邏輯集中控制的方式對(duì)網(wǎng)絡(luò)設(shè)備進(jìn)行統(tǒng)一管理[5]。與傳統(tǒng)網(wǎng)絡(luò)相比，SDN具有更高的靈活性、更強(qiáng)的可編程性和更大的開(kāi)放性。SDN在小型數(shù)據(jù)網(wǎng)絡(luò)中已經(jīng)得到了廣泛應(yīng)用，但是隨著SDN在大中型網(wǎng)絡(luò)中的應(yīng)用，控制平面的健壯性和可擴(kuò)展性面臨著重要挑戰(zhàn)[6]。

從網(wǎng)絡(luò)演進(jìn)的角度看，SDN的靈活性、開(kāi)放性、可編程性等優(yōu)勢(shì)正好可以彌補(bǔ)現(xiàn)有機(jī)載網(wǎng)絡(luò)在航空集群作戰(zhàn)應(yīng)用背景下存在的弊端，具有較好的應(yīng)用前景。目前相關(guān)的研究已經(jīng)展開(kāi)，如文獻(xiàn)[7-8]均指出SDN網(wǎng)絡(luò)范式應(yīng)用于機(jī)載網(wǎng)絡(luò)能夠帶來(lái)眾多優(yōu)勢(shì)。文獻(xiàn)[9]在總結(jié)航空集群作戰(zhàn)特點(diǎn)和SDN設(shè)計(jì)思想的基礎(chǔ)上提出了軟件定義航空集群機(jī)載戰(zhàn)術(shù)網(wǎng)絡(luò)，并對(duì)其基本網(wǎng)絡(luò)架構(gòu)進(jìn)行闡述。但是這些研究的內(nèi)容主要聚焦在概念和基本網(wǎng)絡(luò)架構(gòu)描述，缺乏深入的理論建模分析。在航空集群環(huán)境下由于節(jié)點(diǎn)的高移動(dòng)性和航空信道的不可靠性等因素使得控制器難以像地面網(wǎng)絡(luò)一樣與網(wǎng)絡(luò)節(jié)點(diǎn)有效可靠地交互信息，這對(duì)控制平面的健壯性和可擴(kuò)展性提出了更大挑戰(zhàn)。而如何在航空集群作戰(zhàn)環(huán)境下，構(gòu)造符合網(wǎng)絡(luò)需求的控制平面，解決大規(guī)模及動(dòng)態(tài)網(wǎng)絡(luò)下控制平面可擴(kuò)展性差的問(wèn)題，是實(shí)現(xiàn)SDN范式在機(jī)載網(wǎng)絡(luò)中實(shí)際應(yīng)用的重要前提。

為了解決單一控制器的性能瓶頸和單點(diǎn)失連問(wèn)題，提高網(wǎng)絡(luò)的可擴(kuò)展性，多控制器的架構(gòu)被普遍采用?，F(xiàn)有的多控制器架構(gòu)主要分為3類[10]：扁平式體系結(jié)構(gòu)如Onix、Ethane,垂直架構(gòu)如Kandoo、Logical xBar等，和以O(shè)rion為代表的混合層次式體系結(jié)構(gòu)。在多控制器的架構(gòu)下，研究人員發(fā)現(xiàn)控制器的部署位置和數(shù)量會(huì)直接影響到控制層面的性能，近年來(lái)針對(duì)控制器部署問(wèn)題(Controller Placement Problem，CPP)的研究逐漸成為研究熱點(diǎn)[11-12]?？刂破鞑渴鹗菍?shí)現(xiàn)控制平面構(gòu)建的基礎(chǔ)和前提。在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化和網(wǎng)絡(luò)連通性不穩(wěn)定的機(jī)載網(wǎng)絡(luò)中，控制器的位置不僅會(huì)影響到新流建立的時(shí)延，而且會(huì)直接影響到網(wǎng)絡(luò)的配置和管理效率和網(wǎng)絡(luò)的可靠性等方面。因此，在以航空集群為背景的集中控制式網(wǎng)絡(luò)中對(duì)控制器部署問(wèn)題進(jìn)行研究，提出合適的優(yōu)化模型和求解方法，對(duì)于提升網(wǎng)絡(luò)性能具有重要意義。

前期對(duì)于CPP的研究背景主要集中在地面有線SDN，研究?jī)?nèi)容主要集中在性能尺度以及搜索算法兩個(gè)方面。文獻(xiàn)[13]首次提出控制器放置問(wèn)題，指出CPP問(wèn)題求解的關(guān)鍵點(diǎn)是控制器數(shù)量和控制器在網(wǎng)絡(luò)拓?fù)渲械奈恢?，同時(shí)作者闡述了不同控制器部署方案對(duì)網(wǎng)絡(luò)時(shí)延性能的影響。在此基礎(chǔ)上，文獻(xiàn)[14]提出了可靠性優(yōu)化的控制器部署問(wèn)題，并針對(duì)這一問(wèn)題提出了相應(yīng)的貪心算法和模擬退火算法進(jìn)行求解。除時(shí)延和可靠性外，控制器的負(fù)載均衡及網(wǎng)絡(luò)彈性和容錯(cuò)性也是求解CPP問(wèn)題考慮的重要性能尺度。文獻(xiàn)[15]針對(duì)控制器的負(fù)載均衡問(wèn)題，首次提出容量限制的控制器部署問(wèn)題(Capacitated Controller Placement Problem, CCPP),并針對(duì)這一問(wèn)題提出基于K-center的啟發(fā)式算法，求解滿足控制器容量限制的最小控制器數(shù)量。上述研究主要針對(duì)扁平式的控制器架構(gòu)，沒(méi)有考慮層次型控制器部署的需求。文獻(xiàn)[16]針對(duì)層次型多中心SDN控制器部署問(wèn)題，通過(guò)減少圖劃分的域間割邊數(shù)以降低SDN跨域流數(shù)量來(lái)提高流表構(gòu)建效率。文獻(xiàn)[17]在綜述已有研究的基礎(chǔ)上，也指出未來(lái)對(duì)CPP的研究應(yīng)從實(shí)用性角度出發(fā)設(shè)計(jì)求解方法，以便指導(dǎo)同類或相似的網(wǎng)絡(luò)場(chǎng)景中CPP的求解。

可以看出，現(xiàn)有CPP的研究主要面向固定拓?fù)涞牡孛嬗芯€網(wǎng)絡(luò)，沒(méi)有考慮到動(dòng)態(tài)拓?fù)湎聼o(wú)線網(wǎng)絡(luò)的部署需求。由于機(jī)載網(wǎng)絡(luò)與地面有線網(wǎng)絡(luò)的巨大差異，如在控制器架構(gòu)上，受高動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)浜皖l繁的鏈路中斷影響，以往CPP研究基于的扁平式多控制器架構(gòu)就難以適用于航空集群場(chǎng)景，同時(shí)針對(duì)地面網(wǎng)絡(luò)所設(shè)計(jì)的性能尺度和搜索算法也不能符合航空集群的優(yōu)化需要。因此在航空集群背景下對(duì)CPP研究，應(yīng)該在總結(jié)網(wǎng)絡(luò)場(chǎng)景需求特點(diǎn)的基礎(chǔ)上，結(jié)合控制器架構(gòu)設(shè)計(jì)符合實(shí)際應(yīng)用的性能尺度選取和求解算法。而目前相關(guān)研究由于缺乏這些考慮，在實(shí)際應(yīng)用時(shí)很難有較好的指導(dǎo)意義。

針對(duì)上述問(wèn)題，本文從航空集群控制平面的可擴(kuò)展性出發(fā)，研究了混合層次式的多控制器架構(gòu)及其部署問(wèn)題。在提出適合航空集群的控制器架構(gòu)基礎(chǔ)上，將傳統(tǒng)的多控制器直接部署轉(zhuǎn)化為子域劃分和域內(nèi)部署兩個(gè)步驟。提出了基于節(jié)點(diǎn)密度排序(Node Density Ranking, NDR)的子域劃分算法?？紤]到控制器的負(fù)載均衡，對(duì)NDR擴(kuò)展提出了容量限制下(Capacitated Node Density Ranking, CNDR)的子域劃分算法?？紤]到網(wǎng)絡(luò)的動(dòng)態(tài)特性，從網(wǎng)絡(luò)整體性能角度選取控制鏈路的平均時(shí)延和平均失連率作為優(yōu)化目標(biāo)，在子域劃分的基礎(chǔ)上提出了改進(jìn)的Pareto模擬退火(Improved Pareto Simulated Annealing，IPSA)對(duì)多目標(biāo)優(yōu)化問(wèn)題求解。

1 模型設(shè)計(jì)

1.1 場(chǎng)景及控制器架構(gòu)描述

本文討論是基于如圖1(a)所示的集群作戰(zhàn)應(yīng)用場(chǎng)景，該場(chǎng)景中存在預(yù)警機(jī)、戰(zhàn)斗機(jī)、偵察機(jī)、無(wú)人機(jī)等多種類型的作戰(zhàn)平臺(tái)，它們依據(jù)作戰(zhàn)階段的不同任務(wù)動(dòng)態(tài)組織。與傳統(tǒng)SDN應(yīng)用場(chǎng)景不同，在航空集群環(huán)境中，網(wǎng)絡(luò)節(jié)點(diǎn)的移動(dòng)性使得控制器與控制域內(nèi)傳輸節(jié)點(diǎn)的穩(wěn)定互聯(lián)變得十分困難；高對(duì)抗的戰(zhàn)場(chǎng)環(huán)境使得控制器存在較高的失連風(fēng)險(xiǎn)；無(wú)線鏈路的不可靠性使得扁平式控制器架構(gòu)難以實(shí)現(xiàn)多個(gè)控制器之間及時(shí)有效的信息共享；基于上述考慮，為實(shí)現(xiàn)對(duì)集群平臺(tái)的有效網(wǎng)絡(luò)管控和提高網(wǎng)絡(luò)的可擴(kuò)展性，航空集群環(huán)境中應(yīng)采用混合層次式控制器架構(gòu)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的邏輯集中控制。

文獻(xiàn)[18]提出了一種用于大規(guī)模網(wǎng)絡(luò)的混合層次式控制器架構(gòu)，本文在此基礎(chǔ)上，考慮到航空集群的特殊應(yīng)用場(chǎng)景，做出以下設(shè)定。航空集群環(huán)境下的混合層次式控制器架構(gòu)如圖1(b)所示，考慮到網(wǎng)絡(luò)規(guī)模，本文將控制平面分為兩層。頂層由全局控制器(Globe Controller，GC)組成，GC負(fù)責(zé)跨區(qū)域流量計(jì)算和轉(zhuǎn)發(fā)。由于航空集群平臺(tái)能力之間存在較大差異，GC應(yīng)該部署于預(yù)警機(jī)、指通機(jī)等生存能力和綜合信息處理較強(qiáng)的平臺(tái)之上，GC之間通過(guò)定向天線對(duì)各自負(fù)責(zé)區(qū)域內(nèi)收集到的網(wǎng)絡(luò)視圖信息進(jìn)行交互，進(jìn)而形成掌握全局網(wǎng)絡(luò)信息的主控制平面。主控制平面從全域戰(zhàn)場(chǎng)的視角對(duì)整個(gè)航空集群網(wǎng)絡(luò)進(jìn)行管控，具有最高的控制優(yōu)先級(jí)。

底層由本地控制器(Local Controller，LC)組成，其僅具有自身控制域內(nèi)的本地網(wǎng)絡(luò)視圖信息，向上與GC共同維護(hù)全局網(wǎng)絡(luò)視圖，向下負(fù)責(zé)管理本地設(shè)備和本地流量的轉(zhuǎn)發(fā)。LC是根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模和分布、網(wǎng)絡(luò)流量等情況按需部署在集群平臺(tái)上的。由于其與平臺(tái)內(nèi)的網(wǎng)絡(luò)設(shè)備共用底層物理硬件資源，可以根據(jù)網(wǎng)絡(luò)變化情況在相應(yīng)平臺(tái)上開(kāi)啟或者關(guān)閉本地控制器，實(shí)現(xiàn)對(duì)本地網(wǎng)絡(luò)設(shè)備的彈性管控。動(dòng)態(tài)變化的本地控制器形成本地控制器資源池，與全局控制器共同形成控制邏輯集中的航空集群網(wǎng)絡(luò)的控制平面。本文只對(duì)該控制器架構(gòu)進(jìn)行簡(jiǎn)要概念描述，重點(diǎn)研究該架構(gòu)下本地控制器的部署問(wèn)題。

1.2 問(wèn)題建模

在上述混合層次式控制器架構(gòu)下，本文研究?jī)?nèi)容為在已知網(wǎng)絡(luò)節(jié)點(diǎn)和全局控制器數(shù)量和位置的情況下，求解滿足網(wǎng)絡(luò)管理的性能需求時(shí)的LC控制器數(shù)量和部署位置。

考慮到實(shí)際部署SDN時(shí)，傳統(tǒng)分布式網(wǎng)絡(luò)和SDN是共存的，控制器部署是按照覆蓋網(wǎng)(overlay)方式，即在原有網(wǎng)絡(luò)基礎(chǔ)上部署一個(gè)邏輯控制層面[19]。針對(duì)部署場(chǎng)景做以下假設(shè)：

1) 網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表一個(gè)交換機(jī)，本文統(tǒng)稱為傳輸節(jié)點(diǎn)，控制器為co-located部署方式，即控制器和交換機(jī)可以部署于網(wǎng)絡(luò)同一節(jié)點(diǎn)，此種情況下認(rèn)為兩者的傳輸時(shí)延為0。

2) 除GC之間單獨(dú)配置定向鏈路共享網(wǎng)絡(luò)視圖信息，其他控制路徑均為帶內(nèi)(in-band)方式，即控制信息和數(shù)據(jù)信息走相同路徑，不單獨(dú)部署控制信道。

3) 網(wǎng)絡(luò)中每個(gè)交換機(jī)在同一時(shí)間只能由唯一的LC控制，每個(gè)LC也只能由唯一的GC控制。

為形式化地描述本地控制器LC部署問(wèn)題，將網(wǎng)絡(luò)建模成一個(gè)無(wú)向圖G=(V,E,S,M)，其中V={v1,v2,…,vq}代表拓?fù)渲芯W(wǎng)絡(luò)節(jié)點(diǎn)集合，q為拓?fù)渲泄?jié)點(diǎn)數(shù)量;E={(vs,vt|vs,vt∈V)表示網(wǎng)絡(luò)節(jié)點(diǎn)之間鏈路的集合；M={m1,m2,…mm}表示全局控制器集合;S={s1,s2,…,sk}表示本地控制器集合，其中S?V且M?V；定義傳輸節(jié)點(diǎn)與LC的連接矩陣G=[xvs]|V|*|S|和LC與GC之間的連接矩陣H=[ysm]|S|*|M|，xvisj=1時(shí)，說(shuō)明節(jié)點(diǎn)vi屬于控制器sj的控制域下，反之則為0。相應(yīng)的ysimj=1時(shí)，表示LC節(jié)點(diǎn)si屬于GC節(jié)點(diǎn)mj的控制域下。

2 子域劃分算法的設(shè)計(jì)

航空集群執(zhí)行任務(wù)過(guò)程中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對(duì)保持穩(wěn)定。作戰(zhàn)任務(wù)改變，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化。在航空集群環(huán)境下，應(yīng)當(dāng)由掌握全網(wǎng)視圖信息的全局控制器根據(jù)網(wǎng)絡(luò)環(huán)境變化運(yùn)行LC部署算法得到部署結(jié)果，并將LC啟動(dòng)信息在全網(wǎng)廣播。根據(jù)該信息，網(wǎng)絡(luò)中的相應(yīng)節(jié)點(diǎn)啟動(dòng)控制器模塊成為L(zhǎng)C。

從上述部署流程中可以看出，LC資源池的方式使得控制器部署可以靈活適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，有利于對(duì)本地網(wǎng)絡(luò)設(shè)備的彈性管控。但這也給CPP算法的設(shè)計(jì)提出了較為苛刻的要求。首先集群構(gòu)型的改變具有時(shí)間限制；其次航空集群規(guī)模通常較大，平臺(tái)數(shù)量一般能達(dá)到上百架以上。對(duì)于CPP的求解是NP難問(wèn)題，當(dāng)網(wǎng)絡(luò)規(guī)模達(dá)到上百個(gè)時(shí)，根據(jù)使用算法不同，求解時(shí)間最大能夠達(dá)到幾個(gè)小時(shí)。為防止在大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下求解CPP時(shí)間過(guò)長(zhǎng)導(dǎo)致LC部署無(wú)法完成，本文算法的設(shè)計(jì)重點(diǎn)是在簡(jiǎn)化算法時(shí)間復(fù)雜度并保證解的精確性基礎(chǔ)上，求解出較優(yōu)的LC部署方案。

2.1 基于節(jié)點(diǎn)密度排序的子域劃分算法

為了區(qū)分節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，本節(jié)首先引入兩個(gè)定義，鄰居密度ρi和最短距離δi。

定義1節(jié)點(diǎn)的鄰居密度ρi為

(1)

式中:Dij為節(jié)點(diǎn)si和節(jié)點(diǎn)sj之間的實(shí)際距離;Dc為距離閾值，函數(shù)Γ被定義為

(2)

從式(1)中可以看出節(jié)點(diǎn)的鄰居密度僅與Dc的取值有關(guān)。由于不同拓?fù)錁?gòu)型的網(wǎng)絡(luò)節(jié)點(diǎn)鄰居密差異較大。在相同拓?fù)湎?，閾值越大，?jì)算越復(fù)雜，而閾值越小，難以有效區(qū)分不同節(jié)點(diǎn)的鄰居密度。因此，本文設(shè)置Dc為

Dc=0.3max(Dij)

(3)

定義2節(jié)點(diǎn)最短距離δi為

(4)

根據(jù)定義一個(gè)具有較大ρi和δi值的節(jié)點(diǎn)，更有可能成為子域的頂點(diǎn)。對(duì)于在一定區(qū)域內(nèi)隨機(jī)分布的節(jié)點(diǎn)，為了找到子域的頂點(diǎn)，首先根據(jù)定義計(jì)算每個(gè)節(jié)點(diǎn)的鄰居密度ρ和連接距離δ。然后分別根據(jù)ρ值和δ值對(duì)節(jié)點(diǎn)排序，將排序號(hào)相加得到節(jié)點(diǎn)的總排序號(hào)，按照總排序號(hào)值和LC數(shù)量k得到區(qū)域頂點(diǎn)集Scon。最后按照到區(qū)域頂點(diǎn)距離最短的原則將網(wǎng)絡(luò)節(jié)點(diǎn)劃分為k個(gè)子域。算法1給出了NDR的描述細(xì)節(jié)。

算法1基于密度排序的子域劃分算法NDR

輸入：節(jié)點(diǎn)位置，LC數(shù)量k

輸出：子域集N

1) for eachs∈Sdo

2) 根據(jù)式(1)和式(4)分別計(jì)算每個(gè)節(jié)點(diǎn)的pi和δi3) end for

4) 將節(jié)點(diǎn)集V分別按照p值和δ值降序排列得到V1和V2

5) 記錄每個(gè)節(jié)點(diǎn)的對(duì)應(yīng)排列序號(hào)i和j

6) 將每個(gè)節(jié)點(diǎn)的p值排列序號(hào)i和δ值排列序號(hào)j相加，得到總排列序號(hào)

7) 將節(jié)點(diǎn)集V按照總排列序號(hào)值升序排列得到Vcon

8) 取前k個(gè)點(diǎn)形成區(qū)域頂點(diǎn)基Scon

9) for eachs∈Sdo

10) 計(jì)算每個(gè)節(jié)點(diǎn)到區(qū)域頂點(diǎn)的距離

11) end for

12) 按照距離區(qū)域頂點(diǎn)距離最短的原則，將網(wǎng)絡(luò)分成k個(gè)子域N={N1,N2,…,Nk}

2.2 控制器容量限制下的子域劃分算法

上述對(duì)子域的劃分沒(méi)有考慮控制器容量的限制，無(wú)法得到符合網(wǎng)絡(luò)需求的控制器數(shù)量，實(shí)現(xiàn)對(duì)CCPP問(wèn)題的求解。對(duì)于邏輯集中控制的機(jī)載網(wǎng)絡(luò)，控制器的數(shù)量對(duì)網(wǎng)絡(luò)性能有著重要影響。因?yàn)樵诩鹤鲬?zhàn)過(guò)程中，平臺(tái)多以編隊(duì)云的形式執(zhí)行作戰(zhàn)任務(wù)。屬于同一編隊(duì)云的作戰(zhàn)單元空間跨度較小、信息交互需求較高。將同屬于一個(gè)編隊(duì)云的節(jié)點(diǎn)放到同一本地控制域下，可以有效減少對(duì)GC的訪問(wèn)降低流表建立的開(kāi)銷和時(shí)延，因此子域數(shù)量應(yīng)該盡可能小。但是子域數(shù)量對(duì)應(yīng)于需要部署的LC數(shù)量k，當(dāng)k值過(guò)小時(shí)，本地控制器負(fù)載將會(huì)失衡，這將嚴(yán)重影響控制器的控制效能。綜合以上考慮，本文將考慮控制器容量的LC部署問(wèn)題定義為滿足網(wǎng)絡(luò)負(fù)載性能要求的最少LC數(shù)量。

算法2給出了容量限制的子域劃分算法CNDR。首先，根據(jù)算法1得到區(qū)域頂點(diǎn)集Scon。然后，根據(jù)Scon中節(jié)點(diǎn)排序情況，依次選取序號(hào)靠前的節(jié)點(diǎn)作為子域頂點(diǎn)，形成多個(gè)子域，計(jì)算每個(gè)子域的LC負(fù)載情況。最后逐漸增加子域規(guī)模直到求出所有子域都滿足負(fù)載均衡要求時(shí)的最小k值。

為了評(píng)估多個(gè)子域之間的負(fù)載情況，文獻(xiàn)[20]定義了負(fù)載均衡指數(shù)B，其表示子域間交換機(jī)提交的平均信息量之和的最大差值。需要說(shuō)明的是，由于航空集群的特殊環(huán)境，部署結(jié)果發(fā)送到相應(yīng)節(jié)點(diǎn)時(shí)間周期較長(zhǎng)。而請(qǐng)求信息量是動(dòng)態(tài)變化的，算法2使用的節(jié)點(diǎn)平均信息量只能通過(guò)預(yù)測(cè)或統(tǒng)計(jì)來(lái)大致判斷子域的負(fù)載情況。

(5)

算法2容量限制的子域劃分算法CNDR

輸入：節(jié)點(diǎn)位置，網(wǎng)絡(luò)負(fù)載均衡指標(biāo)

輸出：子域N,LC數(shù)量k

1) 首先根據(jù)算法1的1)～7)行，得到按照總排列序號(hào)值排序的Vcon

2) fori=1:n

3) 取Vcon中前i個(gè)節(jié)點(diǎn)作為頂點(diǎn)

4) 按照距離區(qū)域頂點(diǎn)距離最短的原則，將網(wǎng)絡(luò)分成i個(gè)子域

5) 根據(jù)式(5)計(jì)算每個(gè)區(qū)域內(nèi)的負(fù)載情況

7) 返回此時(shí)的i值和分域情況N

8) break

9) end if

10) end for

為了說(shuō)明CNDR-DPA算法的計(jì)算過(guò)程，在400 km×300 km的區(qū)域隨機(jī)部署36個(gè)節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)編號(hào)，節(jié)點(diǎn)分布如圖2(a)所示。設(shè)置節(jié)點(diǎn)的通信半徑R=80 km。根據(jù)算法1的1)～7)行，得到按照總排列序號(hào)值排序的Vcon，表1為Vcon總排序號(hào)靠前的部分節(jié)點(diǎn)排序情況。假設(shè)每個(gè)節(jié)點(diǎn)的流表策略配置需求l(v)相同，本地控制器的額定負(fù)載L(s)=t×l(v)。當(dāng)t為9，并取至Vcon的第5個(gè)節(jié)點(diǎn)時(shí)，計(jì)算所有子域的負(fù)載情況,均滿足額定負(fù)載要求，此時(shí)網(wǎng)絡(luò)將以節(jié)點(diǎn){18,25,1,28,20}為子域頂點(diǎn)，按照最短距離優(yōu)先原則將節(jié)點(diǎn)分成5個(gè)子域，得到節(jié)點(diǎn)分區(qū)結(jié)果如圖2(b)所示，分別用5種不同形狀的點(diǎn)表示。

節(jié)點(diǎn)序號(hào)1825128204ρ值排序號(hào)10115161712δ值排序號(hào) 11367814總排序號(hào) 111421232526

3 域內(nèi)LC的部署優(yōu)化

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

將網(wǎng)絡(luò)節(jié)點(diǎn)劃分成多個(gè)子域后，需要根據(jù)網(wǎng)絡(luò)性能尺度和搜索算法找到控制器在每個(gè)子域中的適當(dāng)位置。由于航空平臺(tái)的動(dòng)態(tài)移動(dòng)性和網(wǎng)絡(luò)狀態(tài)的時(shí)變性，本文在LC部署過(guò)程中從網(wǎng)絡(luò)的整體性能角度出發(fā)，考慮到混合層次式的控制器架構(gòu)設(shè)計(jì)了以下兩種性能尺度。

1) 控制路徑平均傳播時(shí)延

網(wǎng)絡(luò)的控制路徑平均傳播時(shí)延反映的是網(wǎng)絡(luò)中控制路徑傳播時(shí)延的整體情況。在大尺度分布的航空集群應(yīng)用場(chǎng)景下，網(wǎng)絡(luò)的發(fā)送時(shí)延、排隊(duì)時(shí)延和處理時(shí)延相對(duì)于傳播時(shí)延小很多，傳播時(shí)延為整個(gè)通信時(shí)延主要的影響因素。控制路徑的平均傳輸時(shí)延包括交換機(jī)與LC間平均傳播時(shí)延和LC與GC之間的平均傳播時(shí)延，它嚴(yán)重影響控制平面對(duì)網(wǎng)絡(luò)事件的響應(yīng)速度和管控效率。本文將控制路徑的平均傳播時(shí)延定義為傳輸節(jié)點(diǎn)到LC間平均傳輸時(shí)延和LC與GC之間的平均傳輸時(shí)延之和：

(6)

式中：d(vi,sj)為傳輸節(jié)點(diǎn)vi及LC節(jié)點(diǎn)sj之間的最短路徑時(shí)延集合；d(si,mj)為L(zhǎng)C節(jié)點(diǎn)sj與GC節(jié)點(diǎn)mj之間的最短路徑時(shí)延集合。

2) 控制路徑平均失連率

在邏輯集中控制式的網(wǎng)絡(luò)中管理和控制網(wǎng)絡(luò)的命令是通過(guò)控制路徑傳輸?shù)?，控制路徑的可靠性直接關(guān)系到整個(gè)網(wǎng)絡(luò)的可靠性。由于航空鏈路質(zhì)量的不穩(wěn)定性，控制鏈路出現(xiàn)容易出現(xiàn)中斷現(xiàn)象，同時(shí)在戰(zhàn)場(chǎng)環(huán)境下傳輸節(jié)點(diǎn)具有較高的失連概率。文獻(xiàn)[21]已經(jīng)做出了關(guān)于網(wǎng)絡(luò)可靠性的研究工作。在這里，為了對(duì)網(wǎng)絡(luò)控制路徑的可靠性進(jìn)行評(píng)估，本文定義控制路徑的平均失連率，它是指控制路徑失去連接概率的均值，包括交換機(jī)與LC失連概率和LC與GC失連概率。設(shè)控制鏈路中斷率為d1和傳輸節(jié)點(diǎn)失效率為p1，則控制路徑平均失連率為

(7)

式中：l∈(V,S)為傳輸節(jié)點(diǎn)到LC節(jié)點(diǎn)的控制路徑集合；l∈(S,M)為L(zhǎng)C節(jié)點(diǎn)到GC節(jié)點(diǎn)的控制路徑集合。

3.2 域內(nèi)LC部署算法

本文對(duì)每個(gè)子域內(nèi)LC的部署位置求解過(guò)程中以最小化控制路徑平均傳播時(shí)延和控制路徑平均失連率為目標(biāo)，這是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。由于多個(gè)目標(biāo)之間存在沖突，因此多目標(biāo)優(yōu)化最終得到多個(gè)Pareto解。

以往對(duì)于CPP的求解主要考慮的是域內(nèi)的性能尺度，因此在子域劃分完成之后，可以通過(guò)逐個(gè)子域進(jìn)行遍歷搜索的方式求解到控制器在每個(gè)子域內(nèi)合適的位置。而本文設(shè)定的優(yōu)化目標(biāo)考慮的是控制鏈路的整體性能，LC的位置是相互影響優(yōu)化目標(biāo)的，因此必須從整個(gè)網(wǎng)絡(luò)的角度來(lái)求解出控制器在每個(gè)子域內(nèi)的部署位置，但這也顯著增加了計(jì)算的復(fù)雜度。

對(duì)于多目標(biāo)優(yōu)化問(wèn)題求解的時(shí)間復(fù)雜度和精確性取決于所選取的算法，為了在有限時(shí)間內(nèi)搜索出精確結(jié)果，本文采用Pareto模擬退火(Pareto Simulated Annealing，PSA)算法。PSA算法是基于蒙特卡羅迭代求解法的一種多目標(biāo)啟發(fā)式隨機(jī)搜索算法，實(shí)現(xiàn)簡(jiǎn)單、計(jì)算效率高，通過(guò)合理的參數(shù)設(shè)置可以在計(jì)算時(shí)間和解的精確性之間權(quán)衡，具有較高的靈活性。

根據(jù)以上分析，利用算法1或算法2對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)分區(qū)后，需要在每個(gè)子域內(nèi)部署一個(gè)控制器。為了滿足LC部署問(wèn)題需求和求解方便，本文對(duì)PSA算法進(jìn)行改進(jìn)(IPSA)，算法3中描述了求解流程，有如下關(guān)鍵步驟：

1) 種群個(gè)體初始化。算法中的種群個(gè)體是由k個(gè)元素構(gòu)成的向量X，k為L(zhǎng)C節(jié)點(diǎn)的數(shù)量。PSA算法通常會(huì)采用完全隨機(jī)的初始種群，這種方法雖然能夠保持較好的種群多樣性，但是容易生成適應(yīng)度差的個(gè)體，不利于算法收斂。本文設(shè)置初始種群為子域頂點(diǎn)集Sopt，這樣鄰居密度更高的節(jié)點(diǎn)成為初始種群可以有效節(jié)省PSA算法的初始運(yùn)行時(shí)間，提高精度。

2) 目標(biāo)函數(shù)權(quán)重。合理的目標(biāo)函數(shù)權(quán)重可以保證產(chǎn)生的解具有良好的多樣性。PSA算法在每迭代過(guò)程中用一系列產(chǎn)生樣本的解來(lái)控制目標(biāo)函數(shù)權(quán)重的大小。如果x第一次迭代或者沒(méi)有一個(gè)最靠近樣本x的非劣解x′，則設(shè)置權(quán)重為隨機(jī)值且滿足?λi≥0，∑λi=1；否則，則設(shè)置每個(gè)目標(biāo)函數(shù)fi的權(quán)重為

(8)

式中：α>1。

4) 接受概率P。PSA算法的接受概率與權(quán)值大小有關(guān)，通過(guò)對(duì)權(quán)值大小的控制可以增加或降低某個(gè)目標(biāo)的接受概率。PSA是以概率P接受新解。

(9)

算法3基于改進(jìn)PSA的域內(nèi)LC部署

輸入：G=(V,E)，Sopt，k，m，初始溫度T0，降溫系數(shù)p

輸出：Pareto解集M，LC部署位置

1) 初始化目標(biāo)權(quán)重λi,T=T0

2) 初始解X=Sopt，計(jì)算所有目標(biāo)函數(shù)值并加入Pareto解集M中

3) whileT>1 do

4) 產(chǎn)生鄰域解Y，并計(jì)算其所有目標(biāo)函數(shù)值

5) 比較新產(chǎn)生的鄰域解Y與Pareto解集M中的每個(gè)解并更新Pareto解集M

6) 根據(jù)式(8)和式(9)分別計(jì)算權(quán)重λi和接受概率P

7) 如果Y未進(jìn)入Pareto解集M，以概率P接受Y，如果新解被接受，則令其為X，如果新解未被接受，則保留當(dāng)前解

8) if 完成m次迭代 then

9)T=Tp

10) end if

11) end while

4 實(shí)驗(yàn)結(jié)果及分析

4.1 仿真環(huán)境及參數(shù)說(shuō)明

對(duì)于實(shí)驗(yàn)的相關(guān)環(huán)境和參數(shù)作出如下說(shuō)明：

1) 在一臺(tái)主頻為3 GHZ、內(nèi)存為8 GB的PC上，基于MATLAB環(huán)境下對(duì)本文算法進(jìn)行仿真。

2) 由于目前尚不存在實(shí)際應(yīng)用的具體參數(shù)作為參考，為簡(jiǎn)化實(shí)驗(yàn)過(guò)程作出以下假設(shè)：所有本地控制器都有相同的負(fù)載容量、處理能力等；所有的傳輸節(jié)點(diǎn)向控制器提交的請(qǐng)求信息量相同，設(shè)l(vi)=1；單個(gè)節(jié)點(diǎn)和鏈路的故障率為區(qū)間[0,0.04]和[0,0.08]之間的隨機(jī)數(shù)；值得說(shuō)明的是，這種參數(shù)設(shè)置僅影響具體的計(jì)算值，并不影響對(duì)算法正確性的驗(yàn)證，實(shí)際應(yīng)用時(shí)可根據(jù)全局控制器掌握的具體參數(shù)信息進(jìn)行計(jì)算。IPSA算法的具體參數(shù)在4.4節(jié)實(shí)驗(yàn)中根據(jù)節(jié)點(diǎn)數(shù)量進(jìn)行設(shè)置。

3) 本文算法并不考慮GC的數(shù)量和位置對(duì)網(wǎng)絡(luò)性能的影響。因此規(guī)定在實(shí)驗(yàn)過(guò)程中，節(jié)點(diǎn)數(shù)量小于100時(shí)，GC數(shù)量為1。節(jié)點(diǎn)數(shù)量大于100時(shí)，GC數(shù)量為2。GC的部署位置為隨機(jī)指定的節(jié)點(diǎn)。

4) 考慮到航空集群中各作戰(zhàn)單元依據(jù)作戰(zhàn)動(dòng)態(tài)組織，在網(wǎng)絡(luò)拓?fù)渖媳憩F(xiàn)為隨機(jī)動(dòng)態(tài)變化。為了體現(xiàn)這一特點(diǎn)，實(shí)驗(yàn)中使用的拓?fù)涫窃诮o定區(qū)域內(nèi)隨機(jī)生成多個(gè)節(jié)點(diǎn)，利用Dijkstra算法得到任意兩點(diǎn)間的最短路徑方式獲得的。實(shí)驗(yàn)中設(shè)置網(wǎng)絡(luò)節(jié)點(diǎn)分布區(qū)域的大小為700 km×600 km，節(jié)點(diǎn)的通信半徑R為120 km。

由于在相同節(jié)點(diǎn)數(shù)量下，不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)性能具有一定差異。為了驗(yàn)證本文算法在不同網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模下的有效性和適用性，實(shí)驗(yàn)過(guò)程中將相同節(jié)點(diǎn)數(shù)量作為一種實(shí)驗(yàn)條件，為了排除節(jié)點(diǎn)位置變化對(duì)算法驗(yàn)證的影響，對(duì)比的性能指標(biāo)是相同實(shí)驗(yàn)條件下得到不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)性能優(yōu)化結(jié)果的均值。具體實(shí)驗(yàn)次數(shù)和網(wǎng)絡(luò)拓?fù)鋽?shù)量在各小節(jié)實(shí)驗(yàn)中說(shuō)明。

為了綜合評(píng)估本文算法的有效性，在實(shí)驗(yàn)過(guò)程中，選取3種解決大規(guī)模SDN控制器部署問(wèn)題的算法作為對(duì)比，3種算法的主要描述如表2所示。第1種是基于社團(tuán)發(fā)現(xiàn)的控制器部署算法。第2種是以K-means代表的聚類問(wèn)題求解算法。第3種是將啟發(fā)式算法引入到CPP問(wèn)題求解。前兩種算法為降低時(shí)間復(fù)雜度，都采取了子域劃分域內(nèi)部署控制器的設(shè)計(jì)思路。

表2 對(duì)比算法描述Table 2 Description of comparison algorithms

4.2 NDR劃分算法分析

為了驗(yàn)證NDR對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的子域劃分情況，分別在節(jié)點(diǎn)規(guī)模為60、100、140的航空集群網(wǎng)絡(luò)環(huán)境中，每個(gè)節(jié)點(diǎn)數(shù)量下隨機(jī)生成10個(gè)拓?fù)?，比較不同節(jié)點(diǎn)規(guī)模下的負(fù)載均衡指標(biāo)隨控制器數(shù)量變化情況，并以LPA和K-means算法作為對(duì)比。對(duì)于LPA和K-means算法，因?yàn)樽佑騽澐诌^(guò)程帶有隨機(jī)性，因此實(shí)驗(yàn)結(jié)果采用多次仿真取平均值的方法。

實(shí)驗(yàn)結(jié)果如圖3所示，子域劃分LPA和K-means算法的子域規(guī)模不可控，負(fù)載均衡指數(shù)波動(dòng)較大，且遠(yuǎn)遠(yuǎn)高于NDR算法，因此極易出現(xiàn)控制器負(fù)載不均衡的情況。3種子域劃分算法在計(jì)算過(guò)程中都沒(méi)有對(duì)控制器容量進(jìn)行限制，LPA算法利用節(jié)點(diǎn)標(biāo)號(hào)在網(wǎng)絡(luò)中任意傳播直至收斂來(lái)進(jìn)行子域劃分，K-means算法是通過(guò)迭代計(jì)算將節(jié)點(diǎn)按照最小時(shí)延劃分為K個(gè)類別，而NDR算法在劃分子域過(guò)程中主要考慮周圍節(jié)點(diǎn)的密度和網(wǎng)絡(luò)節(jié)點(diǎn)的分布情況，因此可以獲得更優(yōu)的負(fù)載均衡指數(shù)。需要說(shuō)明的是，本節(jié)僅比較了不同算法的子域負(fù)載均衡指數(shù)，實(shí)際上控制器的負(fù)載狀況不僅與子域規(guī)模有關(guān)，也與控制器在子域中的位置相關(guān)。實(shí)驗(yàn)也表明，利用NDR算法將網(wǎng)絡(luò)劃分多個(gè)子域，可以有效限制子域規(guī)模之間的差距，對(duì)實(shí)現(xiàn)控制器的均衡具有良好效果。

4.3 CNDR劃分算法分析

為了驗(yàn)證CNDR算法對(duì)于CCPP求解的有效性，本節(jié)在節(jié)點(diǎn)規(guī)模從50～200的區(qū)間里，隨機(jī)生成100個(gè)網(wǎng)絡(luò)拓?fù)洌褂肅DNR算法計(jì)算每個(gè)拓?fù)湓诰哂邢嗤刂破魅萘肯拗葡滤璧淖钚C數(shù)量。本文使用文獻(xiàn)[15]提出的求解CCPP問(wèn)題的K-center算法作為對(duì)比。K-center算法是一種基于啟發(fā)式的隨機(jī)搜索算法，通過(guò)迭代尋找滿足控制器負(fù)載均衡的K個(gè)中心，來(lái)求解出網(wǎng)絡(luò)所需的控制器部署數(shù)量和位置。實(shí)驗(yàn)中，每個(gè)傳輸節(jié)點(diǎn)向LC提交的請(qǐng)求信息為[0.5,1.5]之間的隨機(jī)數(shù)，但所有傳輸節(jié)點(diǎn)向?qū)?yīng)LC提交的請(qǐng)求信息總量為N，N為節(jié)點(diǎn)數(shù)量。實(shí)驗(yàn)結(jié)果如圖4所示，x軸表示LC數(shù)量，y軸表示滿足控制器負(fù)載均衡的拓?fù)湓谒型負(fù)渲兴急壤?/p>

從圖4中可以看出，使用CNDR算法,當(dāng)控制器個(gè)數(shù)超過(guò)10時(shí)，50%以上的拓?fù)淠軌驖M足控制器容量的要求;當(dāng)控制器個(gè)數(shù)達(dá)到20時(shí)，所有的拓?fù)涠伎梢詽M足控制器容量的要求。而使用K-center算法，需要的控制器數(shù)量為15～26個(gè)。實(shí)驗(yàn)結(jié)果表明，使用CNDR算法相比于K-center算法求解所需的控制器數(shù)量更少，求得CCPP問(wèn)題解的質(zhì)量更高。這是因?yàn)楸举|(zhì)上K-center是一種啟發(fā)式搜索算法，主要思想是通過(guò)反復(fù)迭代找到滿足控制器容量限制的K個(gè)中心。在節(jié)點(diǎn)數(shù)量較多的情況下，K-center算法容易陷入局部最優(yōu)解。而CNDR算法只需數(shù)學(xué)計(jì)算即可，不會(huì)陷入局部最優(yōu)。

4.4 IPSA性能分析

為了評(píng)估IPSA算法的優(yōu)化性能，本節(jié)設(shè)置場(chǎng)景中的節(jié)點(diǎn)個(gè)數(shù)為80，LC數(shù)量為k=6，在子域劃分基礎(chǔ)上，以控制路徑的平均傳播時(shí)延Tavg和平均故障率σavg作為目標(biāo)函數(shù)，對(duì)LC部署進(jìn)行優(yōu)化。為了在求解精度和求解時(shí)間之間權(quán)衡，根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模，設(shè)置IPSA中迭代次數(shù)m=30，初始溫度T0=150，降溫系數(shù)p=0.90。實(shí)驗(yàn)過(guò)程中使用窮舉算法(Brute Force，BF)對(duì)子域間所有解的組合進(jìn)行遍歷搜索，尋找問(wèn)題最優(yōu)解，作為對(duì)比驗(yàn)證IPSA算法在求解精度上的損失和計(jì)算時(shí)間上的優(yōu)勢(shì)。

首先重復(fù)實(shí)驗(yàn)100次，驗(yàn)證IPSA算法的穩(wěn)定性，記錄Tavg和σavg的取值情況。圖5為100次實(shí)驗(yàn)平均傳播時(shí)延和平均失連率的取值情況變化，圖中橫線為使用BF算法得到的最優(yōu)值。Tavg在[0.807,0.887]內(nèi)波動(dòng)，波動(dòng)幅度為±2.36%；σavg波動(dòng)區(qū)間為[0.122,0.135]，波動(dòng)幅度為±1.36%。

表3給出了BF、IPSA和PSA 3種算法的平均性能比較。3種算法都是在利用NDR算法進(jìn)行子域劃分的基礎(chǔ)上進(jìn)行優(yōu)化求解的。從表中結(jié)果可以看出，通過(guò)改進(jìn)的PSA算法——IPSA算法具有更高的穩(wěn)定性，且更接近最優(yōu)解。

表3 100次獨(dú)立實(shí)驗(yàn)平均性能比較

圖6為采用IPSA、POCO、PSA和BF算法獲得的Pareto解最優(yōu)前沿。從圖中可以看出，控制路徑平均失連率和平均傳輸時(shí)延成反比。相比于PSA算法和POCO算法，IPSA算法得到了較為平滑且均勻的Pareto面，且解更接近BF算法得到的結(jié)果。注意圖中給出的Pareto解為滿足優(yōu)化目標(biāo)的一組權(quán)衡解，實(shí)際的控制器部署過(guò)程中應(yīng)該根據(jù)網(wǎng)絡(luò)性能需求，從Pareto解集中選擇合適的方案。

4.5 本文算法的優(yōu)化性能分析

本節(jié)利用LPA、K-means、POCO和本文所提的NDR和IPSA算法(以下用NDR-IPSA統(tǒng)一表示)對(duì)LC部署優(yōu)化性能進(jìn)行驗(yàn)證。節(jié)點(diǎn)規(guī)模為100，對(duì)比算法的迭代次數(shù)均為200次，IPSA算法參數(shù)中m=20，初始溫度T0=100，降溫系數(shù)p=0.95。首先，驗(yàn)證LC數(shù)量對(duì)網(wǎng)絡(luò)性能的影響。圖7和圖8分別給出了在不同LC數(shù)量下控制路徑的平均傳播時(shí)延Tavg和平均失連率σavg，實(shí)驗(yàn)數(shù)據(jù)為各算法重復(fù)計(jì)算50次的平均值。

從圖7和圖8均可以看出，隨著LC個(gè)數(shù)的增加，平均傳播時(shí)延Tavg和平均失連率σavg均逐漸降低。其中，Tavg平均降低了46.7%，σavg平均減少了24.8%。因此，在航空集群集中控制式的網(wǎng)絡(luò)中增加本地控制器的數(shù)量可以有效減少控制鏈路的平均時(shí)延和平均失連率。對(duì)比其他3種算法，POCO優(yōu)化性能更好，這是因?yàn)楫?dāng)劃分子域過(guò)多時(shí)域內(nèi)節(jié)點(diǎn)數(shù)量將變少，這直接限制了算法的優(yōu)化能力。而與本文算法在子域劃分中僅考慮節(jié)點(diǎn)鄰居密度不同的是，K-means是根據(jù)預(yù)先定義的優(yōu)化目標(biāo)進(jìn)行子域劃分的，更具靈活性，在子域數(shù)量較多的情況下優(yōu)化性能也好。

圖9為4種算法的計(jì)算時(shí)間隨LC數(shù)量變化情況，可知LPA和K-means算法隨著LC數(shù)量的增加，計(jì)算用時(shí)平穩(wěn)增長(zhǎng)，增長(zhǎng)幅度較小。而POCO隨著LC數(shù)量的增加，計(jì)算用時(shí)顯著增長(zhǎng)，增長(zhǎng)幅度較大。與這3種算法不同，本文算法的計(jì)算用時(shí)快速減小。這是因?yàn)殡S著LC數(shù)量增加，子域數(shù)量也在增加，IPSA算法的搜索空間逐漸減小。LPA和K-means是基于迭代的子域劃分方法，因此在網(wǎng)絡(luò)規(guī)模一定的情況下，子域數(shù)量增多反而增加了時(shí)間復(fù)雜度，而NDR-IPSA算法只需要一次計(jì)算就可以實(shí)現(xiàn)網(wǎng)絡(luò)區(qū)域的劃分。

圖10給出了在不同節(jié)點(diǎn)數(shù)量下計(jì)算時(shí)間的對(duì)比情況。隨著節(jié)點(diǎn)數(shù)量的增加，4種算法的計(jì)算時(shí)間都在增加，其中POCO算法計(jì)算時(shí)間遠(yuǎn)高于LPA、K-means和本文算法，在節(jié)點(diǎn)數(shù)量為120以上時(shí)POCO的平均計(jì)算時(shí)間是本文算法的6倍左右。可以看出，與使用啟發(fā)式算法的POCO表現(xiàn)不同的是，使用子域劃分域內(nèi)部署控制器的方式可以顯著降低大規(guī)模SDN控制器部署的時(shí)間復(fù)雜度，但是結(jié)合圖7和圖8的仿真可以看出，這種方式也損失了解的精確度。對(duì)比可知，本文所提算法更適用于大規(guī)模網(wǎng)絡(luò)及動(dòng)態(tài)拓?fù)洵h(huán)境下的控制器部署問(wèn)題。

5 結(jié) 論

1) 針對(duì)航空集群的特殊環(huán)境，通過(guò)擴(kuò)展控制層級(jí)和定義本地控制器資源池的方式，使得控制器部署可以靈活適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，增?qiáng)了網(wǎng)絡(luò)的可擴(kuò)展性。

2) 為了滿足本地控制器快速部署需求，針對(duì)航空集群環(huán)境下節(jié)點(diǎn)規(guī)模大、計(jì)算復(fù)雜度高的問(wèn)題，提出了NDR和IPSA算法，通過(guò)仿真驗(yàn)證了本文算法提升網(wǎng)絡(luò)性能的有效性和在大規(guī)模網(wǎng)絡(luò)及動(dòng)態(tài)拓?fù)洵h(huán)境下的適用性。

3) 考慮到控制器的負(fù)載均衡，為了求解出網(wǎng)絡(luò)需要的控制器數(shù)量，對(duì)NDR擴(kuò)展提出了CNDR，并通過(guò)仿真驗(yàn)證了該算法對(duì)于解決CCPP問(wèn)題的有效性。