標簽分割的軟件定義飛行自組網控制器智能部署方法

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

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

0 引 言

軟件定義網絡是美國斯坦福大學Clean Slate研究組提出的一種集中控制的新型網絡架構，其核心理念是將網絡設備的控制層與數據轉發層分離，由控制層上的控制器對網絡資源進行統一調配，對網絡實行集中管控，而數據轉發層的設備只負責轉發數據分組。將軟件定義網絡的思想引入無人機飛行自組網中，能夠有效解決飛行自組網（flying ad-hoc network，FANET）架構僵化、網絡資源分配不均、網絡效率低的問題，構成軟件定義FANET（software defined FANET，SD-FANET）。

最簡單的軟件定義網絡（software defined network，SDN）架構是利用單個控制器對網絡中所有的節點進行統一管控，但在FANET中，終端節點的分布范圍廣，網絡規模隨任務多樣化而不斷擴大，單控制器下的網絡容易出現單點故障、處理容量有限等問題?；诖?，研究者提出邏輯集中、物理分布的多控制器架構體系，隨之而來的就是網絡的多控制器部署問題。多控制器部署問題（controller placement problem，CPP）主要包括3方面：確定控制器數量、控制器與傳輸節點的映射關系和最佳控制器部署位置。

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

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

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

1 模型構建

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

圖1 分布式網絡架構Fig.1 Distributed network architecture

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

部署成本：將控制器部署在傳輸節點的位置，部署成本為所有控制器的成本之和。為了簡化起見，假設網絡中使用的控制器均為同一類型，部署一臺控制器的成本為，則部署成本為

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

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

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

2 控制器部署方法

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

對網絡進行控制域劃分，其本質就是根據網絡中的節點特征對節點進行分類。本文采用LS算法完成控制域的劃分。

2.1.1 LS算法

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

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

節點權值：節點權值是定義自身特征的基礎。在網絡初始化階段，所有節點的初始能量、帶寬等屬性都是相同的，因此將節點權值定義為關于節點時延的函數，其計算公式為

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

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

關聯特征AC：關聯特征是指節點與網絡中其他節點的關聯程度，對于網絡劃分而言，期望將關聯程度高的節點歸為一類，節點的關聯程度與節點間的距離和節點權值有關，節點間距離越小，關聯程度越高；節點權值越相近，關聯程度越高。因此，定義節點的關聯特征函數為

式中：是距離系數，其計算公式為

其中，Rt為節點通信范圍。

綜合節點自身特征和關聯特征，設定一個分類方案的懲罰函數LF，以懲罰函數值最低為準則對網絡中的節點進行分類，從而確定最佳分類方案，可表示為

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

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

關聯特征懲罰函數ACP ：為了使得分類結果更可靠，可在考慮節點自身特征的基礎上，兼顧節點的關聯特征。在分類方案中，節點的關聯程度越高，其對應的懲罰函數值越低。定義節點v 的關聯特征懲罰函數為

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

算法1中第7行中給定參數的取值范圍，是為了使得網絡劃分的結果能夠滿足組網要求的最少節點數量，在實際應用中可根據組網相關要求設定參數。

2.1.2 LS算法優化

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

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

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

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

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

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

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

將CS算法與LS算法結合能夠在設定迭代次數內搜索最優解和最優值，有效降低了LS算法的計算復雜度，在網絡規模較大時也能快速搜索到較優解。本文將優化后的控制域劃分方法稱為LS-CS算法。

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

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

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

2.2.1 相關指標定義

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

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

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

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

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

歸一化處理將指標同質化：

計算每個指標的熵值：

計算每個指標的權重系數：

將權重系數代入即可得到目標函數解析式。

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

2.2.2 PSO-IIW算法

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

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

在輸出最優部署方案后，將該方案下的相應節點設為控制器部署位置，其負載請求歸零。在此基礎上，根據節點時延、控制器負載等相關指標，根據計算結果評估輸出方案的可靠性。

3 仿真實驗

3.1 仿真參數設置

本文采用Matlab作為仿真平臺，由于整個部署過程分為兩個階段，因此仿真實驗也分為控制域劃分和控制器部署兩個階段以此進行?？刂朴騽澐蛛A段的仿真參數如表1所示。

表1 仿真參數設置-1Table 1 Simulation parameter setting-1

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

表2 仿真參數設置-2Table 2 Simulation parameter setting-2

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

表3 權重系數Table 3 Weight coef ficient

3.2 仿真分析

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

圖2 控制器數量與節點數量的關系Fig.2 Relationship between the number of controllers and nodes

圖3 控制器數量與控制器容量的關系Fig.3 Relationship between the number of controllers and the capacity of controllers

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

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

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

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

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

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

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

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

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

4 結 論

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