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

（1.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西 西安 710077；2.中國人民解放軍93107部隊，遼寧 沈陽 110042；3.中國人民解放軍93303部隊，遼寧 沈陽 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ò)資源進行統(tǒng)一調(diào)配，對網(wǎng)絡(luò)實行集中管控，而數(shù)據(jù)轉(zhuǎn)發(fā)層的設(shè)備只負責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)分組。將軟件定義網(wǎng)絡(luò)的思想引入無人機飛行自組網(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)是利用單個控制器對網(wǎng)絡(luò)中所有的節(jié)點進行統(tǒng)一管控，但在FANET中，終端節(jié)點的分布范圍廣，網(wǎng)絡(luò)規(guī)模隨任務(wù)多樣化而不斷擴大，單控制器下的網(wǎng)絡(luò)容易出現(xiàn)單點故障、處理容量有限等問題?；诖?，研究者提出邏輯集中、物理分布的多控制器架構(gòu)體系，隨之而來的就是網(wǎng)絡(luò)的多控制器部署問題。多控制器部署問題（controller placement problem，CPP）主要包括3方面：確定控制器數(shù)量、控制器與傳輸節(jié)點的映射關(guān)系和最佳控制器部署位置。

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

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

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

1 模型構(gòu)建

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

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

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

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

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

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

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

2 控制器部署方法

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

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

2.1.1 LS算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1.2 LS算法優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

計算每個指標的熵值：

計算每個指標的權(quán)重系數(shù)：

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

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

2.2.2 PSO-IIW算法

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

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

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

3 仿真實驗

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

本文采用Matlab作為仿真平臺，由于整個部署過程分為兩個階段，因此仿真實驗也分為控制域劃分和控制器部署兩個階段以此進行?？刂朴騽澐蛛A段的仿真參數(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

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

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

3.2 仿真分析

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

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

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

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

圖4 平均控制時延Fig.4 Average control latency

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

圖5 控制域平均時延波動Fig.5 Fluctuation of average latency in control domain

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

圖6 控制器負載差異度Fig.6 Controller load difference

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

4 結(jié) 論

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