付有斌，康巧燕，王建峰，胡海巖，趙 朔，3

（1.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077；2.中國人民解放軍93107部隊(duì)，遼寧 沈陽 110042；3.中國人民解放軍93303部隊(duì)，遼寧 沈陽 110042）

0 引 言

軟件定義網(wǎng)絡(luò)是美國斯坦福大學(xué)Clean Slate研究組提出的一種集中控制的新型網(wǎng)絡(luò)架構(gòu)，其核心理念是將網(wǎng)絡(luò)設(shè)備的控制層與數(shù)據(jù)轉(zhuǎn)發(fā)層分離，由控制層上的控制器對網(wǎng)絡(luò)資源進(jìn)行統(tǒng)一調(diào)配，對網(wǎng)絡(luò)實(shí)行集中管控，而數(shù)據(jù)轉(zhuǎn)發(fā)層的設(shè)備只負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)分組。將軟件定義網(wǎng)絡(luò)的思想引入無人機(jī)飛行自組網(wǎng)中，能夠有效解決飛行自組網(wǎng)（flying ad-hoc network，F(xiàn)ANET）架構(gòu)僵化、網(wǎng)絡(luò)資源分配不均、網(wǎng)絡(luò)效率低的問題，構(gòu)成軟件定義FANET（software defined FANET，SD-FANET）。

最簡單的軟件定義網(wǎng)絡(luò)（software defined network，SDN）架構(gòu)是利用單個(gè)控制器對網(wǎng)絡(luò)中所有的節(jié)點(diǎn)進(jìn)行統(tǒng)一管控，但在FANET中，終端節(jié)點(diǎn)的分布范圍廣，網(wǎng)絡(luò)規(guī)模隨任務(wù)多樣化而不斷擴(kuò)大，單控制器下的網(wǎng)絡(luò)容易出現(xiàn)單點(diǎn)故障、處理容量有限等問題?；诖耍芯空咛岢鲞壿嫾?、物理分布的多控制器架構(gòu)體系，隨之而來的就是網(wǎng)絡(luò)的多控制器部署問題。多控制器部署問題（controller placement problem，CPP）主要包括3方面：確定控制器數(shù)量、控制器與傳輸節(jié)點(diǎn)的映射關(guān)系和最佳控制器部署位置。

Heller等人首次提出CPP，隨著研究深入，CPP已經(jīng)被證明是一個(gè)NP（non-deterministic polynomial）難問題，其通用求解思路是根據(jù)實(shí)際問題需求，確定優(yōu)化目標(biāo)并得出優(yōu)化函數(shù)，然后對網(wǎng)絡(luò)進(jìn)行劃分以縮小搜索范圍，最后利用搜索算法尋找可行解。

為解決CPP，近年來有大量的部署策略被研究者提出。首次解決CPP的部署策略指出，控制器的最佳部署位置取決于交換機(jī)和控制器的傳播時(shí)延，并使用貪心算法進(jìn)行求解，但該算法沒有考慮控制器容量的影響。文獻(xiàn)［11］采用一種新的迭代和溫和匹配條件求解CPP，在考慮控制器容量的前提下不僅能夠獲得最低的時(shí)延，同時(shí)實(shí)現(xiàn)了最低的執(zhí)行時(shí)間以及更高的內(nèi)存消耗效率。許多研究都采用聚類算法作為基礎(chǔ)解決CPP，如Yao等人提出了一種容量k-center算法，該算法考慮了控制器容量對網(wǎng)絡(luò)成本和網(wǎng)絡(luò)效率的影響，根據(jù)節(jié)點(diǎn)距離進(jìn)行聚類，同時(shí)設(shè)定聚類中心作為控制器部署位置，有效減少了控制器數(shù)量，簡化了網(wǎng)絡(luò)結(jié)構(gòu)。文獻(xiàn)［13］采用改進(jìn)的k-means算法解決CPP，該算法有效避免了k-means算法結(jié)果隨機(jī)的缺點(diǎn)，但其只考慮平均控制時(shí)延，并未考慮負(fù)載均衡和跨域通信問題。文獻(xiàn)［14］同樣是基于k-means算法提出了一種改進(jìn)型的多控制器部署算法，該算法能夠有效降低網(wǎng)絡(luò)的最大時(shí)延，但由于其只考慮單一指標(biāo)，難以適應(yīng)復(fù)雜網(wǎng)絡(luò)。k-means算法及其改進(jìn)算法大都考慮的是最小化時(shí)延，沒有考慮到控制器容量和部署成本的問題，因此并不是通用的部署算法。而文獻(xiàn)［15］以譜聚類算法為基礎(chǔ)，引入時(shí)延和控制器容量約束進(jìn)行控制器部署，該算法能夠在保證時(shí)延約束的條件下使各控制器負(fù)載保持均衡；但該算法只能保證時(shí)延在約束內(nèi)，無法保證時(shí)延最低，同時(shí)也沒有考慮部署成本的問題。文獻(xiàn)［16］在給定的時(shí)延約束下，權(quán)衡控制器負(fù)載和切換頻率，在混合整數(shù)線性規(guī)劃模型的基礎(chǔ)上，給出CPP的求解公式，通過Pareto最優(yōu)算法的求解結(jié)果能夠滿足時(shí)延和控制器時(shí)延等目標(biāo)。此外，研究者將啟發(fā)式算法如蟻群算法、粒子群算法、布谷鳥算法等都被應(yīng)用到求解CPP，得到的結(jié)果都可被認(rèn)為是較優(yōu)解，如Fan等人在考慮鏈路失效的情況下，提出以最小化控制器與交換機(jī)之間的時(shí)延為目標(biāo)的部署策略，在該策略中引入粒子群算法進(jìn)行控制器位置的部署，該算法在80%以上的網(wǎng)絡(luò)中都能保證網(wǎng)絡(luò)時(shí)延低于10 ms。為了最大化網(wǎng)絡(luò)鏈路連通性，文獻(xiàn)［22］提出survivor模型，其目標(biāo)為優(yōu)化控制器與其每一個(gè)傳輸節(jié)點(diǎn)的不相交鏈路數(shù)量，該模型選擇不相交鏈路最多的節(jié)點(diǎn)作為控制器部署位置以增強(qiáng)網(wǎng)絡(luò)可靠性。文獻(xiàn)［23］考慮鏈路故障對網(wǎng)絡(luò)可靠性的影響，提出一種基于控制時(shí)延可靠性的控制性部署算法，該算法基于鏈路故障定義部署方案可靠性指標(biāo)，并以該指標(biāo)最大為準(zhǔn)則選擇控制器部署方案。

綜上可知，現(xiàn)有控制器部署方法大部分都是以優(yōu)化網(wǎng)絡(luò)指標(biāo)為目的，從而完成控制器部署，如優(yōu)化網(wǎng)絡(luò)時(shí)延、網(wǎng)絡(luò)可靠性等，除此之外還有綜合考慮多個(gè)指標(biāo)的控制器部署算法。但是，當(dāng)前并沒有綜合考慮網(wǎng)絡(luò)時(shí)延、控制器容量約束和部署成本三者的算法?；诖耍疚奶岢鲆环N標(biāo)簽分割（label segmentation，LS）的控制器部署方法，首先根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)狀態(tài)和約束條件自適應(yīng)對網(wǎng)絡(luò)進(jìn)行劃分，保證網(wǎng)絡(luò)可靠性的同時(shí)降低部署成本；然后在此基礎(chǔ)上綜合考慮平均控制時(shí)延、控制域時(shí)延波動(dòng)和控制器負(fù)載差異度3個(gè)指標(biāo)，搜索最佳部署方案，從而完成整個(gè)部署過程。本文的主要貢獻(xiàn)在于：①提出基于LS的控制域劃分方法，該方法優(yōu)勢在于能夠根據(jù)節(jié)點(diǎn)的自身特征和關(guān)聯(lián)特征定義懲罰函數(shù)，以懲罰函數(shù)值最小為準(zhǔn)則得出最佳劃分結(jié)果；同時(shí)采用布谷鳥搜索（Cuckoo search，CS）算法對其進(jìn)行優(yōu)化，保證輸出最優(yōu)結(jié)果的同時(shí)降低算法的計(jì)算復(fù)雜度和收斂時(shí)間；②重新定義控制器負(fù)載差異度，在考慮傳輸節(jié)點(diǎn)數(shù)量的基礎(chǔ)上進(jìn)一步考慮每個(gè)節(jié)點(diǎn)的流量請求，使其能更加全面地表征控制器負(fù)載的差異程度，并通過優(yōu)化該指標(biāo)均衡控制器負(fù)載。最后通過采用基于改進(jìn)慣性權(quán)重粒子群優(yōu)化（particle swarm optimization with improved inertial weight，PSO-IIW）算法的控制器部署算法完成整個(gè)網(wǎng)絡(luò)的多控制器部署。

1 模型構(gòu)建

在SD-FANET中，網(wǎng)絡(luò)節(jié)點(diǎn)的運(yùn)動(dòng)范圍廣、分布稀疏，僅使用一個(gè)控制器難以對全網(wǎng)節(jié)點(diǎn)進(jìn)行有效控制，而且當(dāng)控制器故障或者處理能力有限時(shí)，容易引起網(wǎng)絡(luò)效率下降甚至網(wǎng)絡(luò)失效等問題。因此，SD-FANET采用分布式的SDN架構(gòu)，如圖1所示。

圖1 分布式網(wǎng)絡(luò)架構(gòu)Fig.1 Distributed network architecture

控制器容量：單臺(tái)控制器的載荷及其處理能力都是有限的，為了使得控制器能夠正常工作，需要保證每臺(tái)控制器管理的傳輸節(jié)點(diǎn)數(shù)不超過給定的上限值，該值即為控制器容量。

部署成本：將控制器部署在傳輸節(jié)點(diǎn)的位置，部署成本為所有控制器的成本之和。為了簡化起見，假設(shè)網(wǎng)絡(luò)中使用的控制器均為同一類型，部署一臺(tái)控制器的成本為，則部署成本為

在部署控制器的過程中，控制器數(shù)量過多會(huì)造成冗余，同時(shí)增加不必要的部署成本；而數(shù)量過少會(huì)導(dǎo)致部分傳輸節(jié)點(diǎn)不受控制器管理或者部分控制器過載的情況，因此在部署控制器之前無法事先確定控制器數(shù)量。本文解決的問題可描述為在給定控制器容量下，以最低的部署成本獲取最優(yōu)的控制器部署方案，數(shù)學(xué)描述為

式（2）中的l 表示第個(gè)控制器部署節(jié)點(diǎn)；式（3）為約束條件，其中S表示第個(gè)控制域，｜S｜表示第個(gè)控制域中的節(jié)點(diǎn)數(shù)量。

在多控制器SDN環(huán)境下，控制器的部署往往分為3個(gè)階段：控制器數(shù)量的確定；根據(jù)控制器數(shù)量劃分控制域；在各個(gè)控制域中部署控制器。本文將確定控制器數(shù)量和劃分控制域合并為一個(gè)步驟，在劃分控制域的過程中綜合考慮部署成本和網(wǎng)絡(luò)可靠性，自適應(yīng)地確定控制器數(shù)量，然后在已劃分好的控制域內(nèi)部署控制器。因此，可以將多CPP分解成控制域劃分和控制器部署兩個(gè)子問題，根據(jù)子問題性質(zhì)和特點(diǎn)分別解決。

2 控制器部署方法

2.1 基于LS的控制域劃分方法

對網(wǎng)絡(luò)進(jìn)行控制域劃分，其本質(zhì)就是根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)特征對節(jié)點(diǎn)進(jìn)行分類。本文采用LS算法完成控制域的劃分。

2.1.1 LS算法

GC（GraphCut）算法是一種圖像分割算法，其基本思想是根據(jù)圖像中每個(gè)點(diǎn)的像素值將圖像的前景和背景分割開。與譜聚類算法和k-means及其改進(jìn)算法相比，GC算法能夠同時(shí)兼顧節(jié)點(diǎn)自身屬性特征和網(wǎng)絡(luò)連接性，并根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對二者進(jìn)行均衡從而得到更好的分類結(jié)果，因此，本文以GC算法為基礎(chǔ)進(jìn)行改進(jìn)并提出LS算法。

在LS算法中，每個(gè)節(jié)點(diǎn)有一個(gè)“像素值”，本文稱其為節(jié)點(diǎn)標(biāo)簽l （l ＝0，1），根據(jù)節(jié)點(diǎn)標(biāo)簽將節(jié)點(diǎn)分為兩類，通過重復(fù)使用LS算法對網(wǎng)絡(luò)進(jìn)行控制域劃分，直至結(jié)果滿足約束條件時(shí)結(jié)束劃分。

節(jié)點(diǎn)權(quán)值：節(jié)點(diǎn)權(quán)值是定義自身特征的基礎(chǔ)。在網(wǎng)絡(luò)初始化階段，所有節(jié)點(diǎn)的初始能量、帶寬等屬性都是相同的，因此將節(jié)點(diǎn)權(quán)值定義為關(guān)于節(jié)點(diǎn)時(shí)延的函數(shù)，其計(jì)算公式為

式中：TL 為節(jié)點(diǎn)v 與其所有鄰居節(jié)點(diǎn)間時(shí)延的最大值。節(jié)點(diǎn)v 和節(jié)點(diǎn)v 之間的距離為d ，電磁波傳播速度為，節(jié)點(diǎn)v 的鄰居節(jié)點(diǎn)集合為N ，則TL 的計(jì)算公式為

節(jié)點(diǎn)標(biāo)簽概率（l ＝l ）：在對節(jié)點(diǎn)進(jìn)行分類之前，對于每個(gè)節(jié)點(diǎn)都可根據(jù)其權(quán)值計(jì)算出其初始標(biāo)簽的概率，因此可將節(jié)點(diǎn)標(biāo)簽概率視為節(jié)點(diǎn)的自身特征。在LS算法中，若節(jié)點(diǎn)v的權(quán)值最大，則令其標(biāo)簽l ＝1，該節(jié)點(diǎn)的標(biāo)簽概率可表示為（l ＝1）＝1或（l ＝0）＝0，同理可得權(quán)值最小的節(jié)點(diǎn)標(biāo)簽概率可表示為（l ＝0）＝1或（l ＝1）＝0。在此基礎(chǔ)上，可得其他節(jié)點(diǎn)的標(biāo)簽概率計(jì)算方法如下：

關(guān)聯(lián)特征AC：關(guān)聯(lián)特征是指節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的關(guān)聯(lián)程度，對于網(wǎng)絡(luò)劃分而言，期望將關(guān)聯(lián)程度高的節(jié)點(diǎn)歸為一類，節(jié)點(diǎn)的關(guān)聯(lián)程度與節(jié)點(diǎn)間的距離和節(jié)點(diǎn)權(quán)值有關(guān)，節(jié)點(diǎn)間距離越小，關(guān)聯(lián)程度越高；節(jié)點(diǎn)權(quán)值越相近，關(guān)聯(lián)程度越高。因此，定義節(jié)點(diǎn)的關(guān)聯(lián)特征函數(shù)為

式中：是距離系數(shù)，其計(jì)算公式為

其中，Rt為節(jié)點(diǎn)通信范圍。

綜合節(jié)點(diǎn)自身特征和關(guān)聯(lián)特征，設(shè)定一個(gè)分類方案的懲罰函數(shù)LF，以懲罰函數(shù)值最低為準(zhǔn)則對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分類，從而確定最佳分類方案，可表示為

式中：LF（）為該方法下的懲罰函數(shù)，為節(jié)點(diǎn)分類方法；SCP 為自身特征懲罰函數(shù)；ACP 為關(guān)聯(lián)特征懲罰函數(shù)；為SCP 和ACP 之間的重要因子，決定其對懲罰函數(shù)的影響大小。懲罰函數(shù)LF（）值最低時(shí)對應(yīng)的為最佳分類方法。下面給出SCP 和ACP 的定義。

自身特征懲罰函數(shù)SCP ：若只考慮節(jié)點(diǎn)自身特征，即只根據(jù)節(jié)點(diǎn)標(biāo)簽概率（l ＝l ）對節(jié)點(diǎn)進(jìn)行分類，此時(shí)希望得到的懲罰函數(shù)值最小，所以可以將節(jié)點(diǎn)v的自身特征懲罰函數(shù)定義為

關(guān)聯(lián)特征懲罰函數(shù)ACP ：為了使得分類結(jié)果更可靠，可在考慮節(jié)點(diǎn)自身特征的基礎(chǔ)上，兼顧節(jié)點(diǎn)的關(guān)聯(lián)特征。在分類方案中，節(jié)點(diǎn)的關(guān)聯(lián)程度越高，其對應(yīng)的懲罰函數(shù)值越低。定義節(jié)點(diǎn)v 的關(guān)聯(lián)特征懲罰函數(shù)為

基于LS算法的控制域劃分算法用于在給定控制器容量時(shí)，如何在約束內(nèi)得到最佳的網(wǎng)絡(luò)劃分方案＝｛S｝，＝1，2，…，，偽代碼如算法1所示。

算法1中第7行中給定參數(shù)的取值范圍，是為了使得網(wǎng)絡(luò)劃分的結(jié)果能夠滿足組網(wǎng)要求的最少節(jié)點(diǎn)數(shù)量，在實(shí)際應(yīng)用中可根據(jù)組網(wǎng)相關(guān)要求設(shè)定參數(shù)。

2.1.2 LS算法優(yōu)化

在算法1中，第7～17行是根據(jù)懲罰函數(shù)最小準(zhǔn)則求解最佳分類方案，采取的是窮盡搜索的方式，其優(yōu)勢在于能夠通過遍歷所有的解從而搜索到最優(yōu)解，但是計(jì)算量龐大，計(jì)算復(fù)雜度很高。為了在保證能夠搜索到較優(yōu)解的前提下降低計(jì)算復(fù)雜度，本文采用CS算法對LS算法進(jìn)行優(yōu)化。

CS算法是一種新型元啟發(fā)式搜索算法，其主要優(yōu)點(diǎn)是參數(shù)少、隨機(jī)搜索路徑優(yōu)、尋優(yōu)能力強(qiáng)等。在CS算法的搜索過程中，兩個(gè)位置的更新至關(guān)重要。

一個(gè)是采用Lévy飛行更新位置，Lévy飛行已被應(yīng)用于優(yōu)化搜索方面，其結(jié)果表明該行為在優(yōu)化效果上具有較大潛力。其位置更新公式定義如下：

式中：是步長縮放因子；Levy（）表示Lévy隨機(jī)路徑，Levy（）＝，1＜≤3。

另一個(gè)是以發(fā)現(xiàn)概率P丟棄一部分位置并產(chǎn)生相同數(shù)量的新位置代替，位置的更新主要采用隨機(jī)游動(dòng)的方式，即利用其他位置的相似性。該更新公式為

式中：和是服從均勻分布的隨機(jī)數(shù)；（）是單位階躍函數(shù)；X 和X 是其他任意兩個(gè)位置。

通過這兩種位置更新方法可以提高CS算法搜索效率，在較短的時(shí)間內(nèi)收斂到全局最優(yōu)值。CS算法偽代碼如算法2所示。

將CS算法與LS算法結(jié)合能夠在設(shè)定迭代次數(shù)內(nèi)搜索最優(yōu)解和最優(yōu)值，有效降低了LS算法的計(jì)算復(fù)雜度，在網(wǎng)絡(luò)規(guī)模較大時(shí)也能快速搜索到較優(yōu)解。本文將優(yōu)化后的控制域劃分方法稱為LS-CS算法。

通過理論分析可知，與k-means算法與譜聚類算法相比較，LS-CS算法能夠充分考慮到節(jié)點(diǎn)自身的自身特征與節(jié)點(diǎn)間的相關(guān)性，并且無需預(yù)設(shè)控制器數(shù)量，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)自適應(yīng)對網(wǎng)絡(luò)進(jìn)行劃分，從而得到更好的網(wǎng)絡(luò)劃分結(jié)果。因此，本文通過LS-CS算法將網(wǎng)絡(luò)劃分為多個(gè)控制域后，在每個(gè)控制域中選定節(jié)點(diǎn)部署控制器，即完成整個(gè)控制器部署的過程。

2.2 PSO-IIW的控制器部署方法

本節(jié)基于均衡控制器性能的思想，主要考慮網(wǎng)絡(luò)時(shí)延和控制器負(fù)載，具體指標(biāo)為控制器平均時(shí)延、控制域平均時(shí)延波動(dòng)和控制器負(fù)載差異度，以優(yōu)化這3個(gè)指標(biāo)為目標(biāo)，搜索最佳控制器部署方案。

2.2.1 相關(guān)指標(biāo)定義

控制器平均時(shí)延：根據(jù)Open Flow協(xié)議機(jī)制可知，在網(wǎng)絡(luò)工作時(shí)，傳輸節(jié)點(diǎn)與控制器之間以及傳輸節(jié)點(diǎn)之間會(huì)進(jìn)行頻繁通信，因此網(wǎng)絡(luò)模型中的時(shí)延包括控制時(shí)延和傳輸時(shí)延?？刂茣r(shí)延是指控制器與傳輸節(jié)點(diǎn)之間的時(shí)延，傳輸時(shí)延是指傳輸節(jié)點(diǎn)之間互相發(fā)通信的時(shí)延。由于傳輸時(shí)延在劃分控制域時(shí)已作為參考指標(biāo)之一，因此網(wǎng)絡(luò)時(shí)延性能只考慮控制器平均時(shí)延，其計(jì)算公式如下：

控制域平均時(shí)延波動(dòng)：SD-FANET工作時(shí)需要保證通信暢通，因此對時(shí)延要求較為敏感，主控制器會(huì)根據(jù)任務(wù)性質(zhì)和時(shí)延要求將其分配給不同的子域，當(dāng)網(wǎng)絡(luò)中各子域平均時(shí)延相差較大時(shí)，平均時(shí)延較小的子域會(huì)被頻繁分配任務(wù)，而平均時(shí)延較大的子域活躍程度相對較低，這會(huì)使得整個(gè)網(wǎng)絡(luò)負(fù)載不均衡，網(wǎng)絡(luò)效率較低。因此，在保證全局平均時(shí)延符合要求時(shí)，還要確保各控制域時(shí)延差異在一定范圍內(nèi)，因此定義控制域平均時(shí)延波動(dòng)指標(biāo)，其計(jì)算公式為

控制器負(fù)載差異度：當(dāng)前文獻(xiàn)定義控制器負(fù)載差異度時(shí)僅考慮控制器域內(nèi)的傳輸節(jié)點(diǎn)數(shù)量，當(dāng)各域內(nèi)的傳輸節(jié)點(diǎn)數(shù)量相同，但流量請求差異較大時(shí)，當(dāng)前概念認(rèn)為控制器負(fù)載差異度為0，這顯然是不夠完善的。因此，本文將控制器負(fù)載差異度定義為各控制器域內(nèi)的節(jié)點(diǎn)平均請求量與全局平均請求量的標(biāo)準(zhǔn)差，其計(jì)算公式為

在選擇控制器部署方案時(shí)，期望存在一個(gè)最佳方案能夠使得以上3個(gè)指標(biāo)均達(dá)到最優(yōu)，但這往往是難以實(shí)現(xiàn)的。因此，本文對各個(gè)目標(biāo)函數(shù)進(jìn)行線性加權(quán)，將該問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，即

式中：f （＝1，2，3）分別表示制器平均時(shí)延、控制域平均時(shí)延波動(dòng)和控制器負(fù)載差異度；λ為目標(biāo)函數(shù)f 的權(quán)重系數(shù)，其值由熵值法確定。求解λ的步驟如下。

歸一化處理將指標(biāo)同質(zhì)化：

計(jì)算每個(gè)指標(biāo)的熵值：

計(jì)算每個(gè)指標(biāo)的權(quán)重系數(shù)：

將權(quán)重系數(shù)代入即可得到目標(biāo)函數(shù)解析式。

由于控制器部署問題比網(wǎng)絡(luò)劃分問題的復(fù)雜度更低，可以采用簡單且能快速收斂的PSO-IIW對目標(biāo)函數(shù)進(jìn)行求解。

2.2.2 PSO-IIW算法

傳統(tǒng)粒子群算法的收斂能力取決于慣性權(quán)重系數(shù)，當(dāng)較大時(shí)，全局收斂能力強(qiáng)而局部收斂能力弱；當(dāng)較小時(shí)，全局收斂能力弱而局部收斂能力強(qiáng)。為了避免算法陷入局部最優(yōu)，期望算法運(yùn)行前期粒子運(yùn)動(dòng)速度較快，同時(shí)為了防止偏離全局最優(yōu)，期望算法運(yùn)行后期粒子運(yùn)動(dòng)較慢。因此對慣性權(quán)重系數(shù)進(jìn)行改進(jìn)，令改進(jìn)后的慣性權(quán)重系數(shù)為

式中：為最大慣性權(quán)重系數(shù)；為當(dāng)前迭代次數(shù)；為最大迭代次數(shù)。PSO-IIW算法偽代碼如算法3所示。

在輸出最優(yōu)部署方案后，將該方案下的相應(yīng)節(jié)點(diǎn)設(shè)為控制器部署位置，其負(fù)載請求歸零。在此基礎(chǔ)上，根據(jù)節(jié)點(diǎn)時(shí)延、控制器負(fù)載等相關(guān)指標(biāo)，根據(jù)計(jì)算結(jié)果評(píng)估輸出方案的可靠性。

3 仿真實(shí)驗(yàn)

3.1 仿真參數(shù)設(shè)置

本文采用Matlab作為仿真平臺(tái)，由于整個(gè)部署過程分為兩個(gè)階段，因此仿真實(shí)驗(yàn)也分為控制域劃分和控制器部署兩個(gè)階段以此進(jìn)行。控制域劃分階段的仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置-1Table 1 Simulation parameter setting-1

在控制器部署階段，設(shè)置控制器容量＝8，采用該條件下的劃分結(jié)果作為輸入，其他仿真參數(shù)如表2所示。

表2 仿真參數(shù)設(shè)置-2Table 2 Simulation parameter setting-2

通過計(jì)算，得到在＝8時(shí)，3個(gè)指標(biāo)的權(quán)重系數(shù)如表3所示（保留3位有效數(shù)字）。

表3 權(quán)重系數(shù)Table 3 Weight coef ficient

3.2 仿真分析

在控制域劃分時(shí)，期望以最少的控制器達(dá)到控制整個(gè)網(wǎng)絡(luò)的目的，這既可以使得網(wǎng)絡(luò)的可靠性得到保證，也能夠降低部署成本。本文將LS-CS算法與譜聚類算法和k-means算法進(jìn)行比較，在不同約束條件下得到的結(jié)果如圖2和圖3所示。

圖2 控制器數(shù)量與節(jié)點(diǎn)數(shù)量的關(guān)系Fig.2 Relationship between the number of controllers and nodes

圖3 控制器數(shù)量與控制器容量的關(guān)系Fig.3 Relationship between the number of controllers and the capacity of controllers

圖2為在給定控制器容量＝8時(shí)，控制器數(shù)量隨網(wǎng)絡(luò)規(guī)模的變化。由圖2可知，在控制器容量確定時(shí)，同等網(wǎng)絡(luò)規(guī)模下，與k-means算法和譜聚類算法相比，LS-CS算法所需的控制器數(shù)量最更少，根據(jù)式（1）可知，本文算法所需的部署成本更低。

圖3為在給定網(wǎng)絡(luò)規(guī)模＝50時(shí)，控制器數(shù)量與控制器容量的關(guān)系。由圖3可知，在網(wǎng)絡(luò)規(guī)模一定時(shí)，3種算法計(jì)算得到的控制器數(shù)量均隨著控制器容量的增大而減少，而LS-CS算法與k-means算法和譜聚類算法相比，在控制器容量相同時(shí)的控制器數(shù)量也是更少的。這是因?yàn)闊o論是k-means算法還是譜聚類算法，其聚類目標(biāo)都是最小化時(shí)延，而LS-CS算法在其基礎(chǔ)上，考慮了節(jié)點(diǎn)的關(guān)聯(lián)特征，即網(wǎng)絡(luò)連通性，綜合考慮時(shí)延因素和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此能夠在相同約束條件下得到更好的結(jié)果。綜合圖2和圖3可知，在網(wǎng)絡(luò)規(guī)模和控制器容量都確定的情況下，LS-CS算法性能更加優(yōu)異。在完成控制器劃分之后，本文根據(jù)相應(yīng)指標(biāo)需求選擇PSO-IIW算法搜索最佳控制器部署方法，并與depoly-cd算法、k-center策略和survivor策略進(jìn) 行比較。

圖4表示在不同部署方案下，平均控制時(shí)延隨網(wǎng)絡(luò)規(guī)模的變化關(guān)系。相較于其他3種策略，PSO-IIW 算法對于平均控制時(shí)延有一定的優(yōu)化效果。這是由于在對網(wǎng)絡(luò)進(jìn)行劃分的階段，自身特征是在最大時(shí)延的基礎(chǔ)上定義的，而劃分時(shí)要求懲罰函數(shù)最小，即要求最大時(shí)延最低，因此與其他算法相比，平均控制時(shí)延得到了一定的優(yōu)化。由于仿真中設(shè)置的指標(biāo)如通信范圍，系統(tǒng)信噪比等相較于實(shí)際應(yīng)用有一定的簡化和降低，因此在實(shí)際應(yīng)用中，優(yōu)化效果將會(huì)更明顯。隨著節(jié)點(diǎn)數(shù)量的增加，平均控制時(shí)延會(huì)逐漸降低，這是由于在節(jié)點(diǎn)數(shù)量增加的過程中，仿真區(qū)域是固定不變的，從而導(dǎo)致節(jié)點(diǎn)密度增大，節(jié)點(diǎn)間的時(shí)延也就隨之降低了。

圖4 平均控制時(shí)延Fig.4 Average control latency

圖5表示在不同部署方案下，控制域平均時(shí)延波動(dòng)隨網(wǎng)絡(luò)規(guī)模的變化關(guān)系。由圖5可知，4種方法下的時(shí)延波動(dòng)均隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而降低。與其他3種策略相比，PSO-IIW算法的效果更佳。其原因是在網(wǎng)絡(luò)劃分階段，增加了對節(jié)點(diǎn)關(guān)聯(lián)特征的考慮，而關(guān)聯(lián)特征的定義也與時(shí)延有關(guān)，即在網(wǎng)絡(luò)劃分時(shí)，除了確保各個(gè)控制域的最大控制時(shí)延最低，還保證了各個(gè)控制域的平均控制時(shí)延相近，從而達(dá)到懲罰函數(shù)最小的目的，因此本文算法的平均時(shí)延波動(dòng)更穩(wěn)定。與平均控制時(shí)延相似，隨著節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)中的節(jié)點(diǎn)密度會(huì)增大，從而導(dǎo)致時(shí)延降低，且節(jié)點(diǎn)更加密集會(huì)導(dǎo)致節(jié)點(diǎn)間時(shí)延趨于相近，因此時(shí)延波動(dòng)也會(huì)更加平穩(wěn)。

圖5 控制域平均時(shí)延波動(dòng)Fig.5 Fluctuation of average latency in control domain

圖6為不同部署策略下控制器負(fù)載差異度隨網(wǎng)絡(luò)規(guī)模的變化情況。由圖6可知，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，k-center策略和survivor策略下的控制器負(fù)載差異度呈現(xiàn)下降的趨勢，控制器負(fù)載逐漸趨于均衡。而deploy-cd算法和PSOIIW算法下的控制器負(fù)載差異度始終保持平穩(wěn)的趨勢且相比于其他兩種策略表現(xiàn)更加優(yōu)異，其中在PSO-IIW 算法下，該指標(biāo)始終處于最低的位置，說明PSO-IIW 算法對于部署控制器而言能夠體現(xiàn)出更優(yōu)異的性能。這是因?yàn)楸疚奶岢隽诵碌呢?fù)載差異度的概念，在對比算法僅考慮傳輸節(jié)點(diǎn)數(shù)量的基礎(chǔ)上增加了對節(jié)點(diǎn)流量請求的考慮，在此概念下，對比算法的負(fù)載差異度增大，對比之下即可說明本文算法能夠更好地實(shí)現(xiàn)控制器的負(fù)載均衡。

圖6 控制器負(fù)載差異度Fig.6 Controller load difference

本文提出的LS-CS算法在對網(wǎng)絡(luò)進(jìn)行劃分時(shí)，綜合考慮網(wǎng)絡(luò)節(jié)點(diǎn)特征和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特征，在約束條件下對網(wǎng)絡(luò)進(jìn)行劃分。通過仿真結(jié)果及相應(yīng)分析能夠證明，LS-CS算法能夠有效降低網(wǎng)絡(luò)平均控制時(shí)延，穩(wěn)定控制域平均時(shí)延波動(dòng)并且能夠均衡控制器負(fù)載。在此基礎(chǔ)上采用PSOIIW算法，其目的是能夠更加快速地在給定的范圍內(nèi)搜尋到最佳控制器部署位置，從而提高控制器部署效率。

4 結(jié) 論

本文將多控制器的部署問題分解成兩個(gè)子問題解決，首先使用LS-CS算法的控制域劃分方法將整個(gè)網(wǎng)絡(luò)劃分為滿足約束條件的多個(gè)控制域，在此基礎(chǔ)上采用PSO-IIW 算法在各個(gè)域內(nèi)部署控制器從而完成多控制器部署的整個(gè)過程。通過與其他策略的比較，表明LS-CS算法能在保證網(wǎng)絡(luò)可靠性的情況下降低部署成本，提高劃分效率，而PSOIIW算法能夠得到更低的時(shí)延，同時(shí)該算法下的控制器負(fù)載更佳均衡，為控制器的高效工作提供了可靠的保障。