基于K-mean++和粒子群算法的SDN多控制器部署方法

［摘 要］ 針對軟件定義網絡中的多控制器部署問題，首先通過K-means++算法對網絡節點聚類，得到網絡中初始控制域和控制器位置，然后使用粒子群算法以最小化時延和負載均衡為優化目標，多個粒子并行搜索最優解，進一步優化控制域和控制器位置。在小、中、大型網絡拓撲上與隨機算法、K-means++算法、粒子群算法的多控制器部署方法比較，仿真結果表明，在中小型網絡中，比其他3種算法在平均傳播時延和負載均衡上更加穩定且時延更低，在大型網絡中，平均傳播時延，最壞傳播時延和控制器的負載均衡上均優于其他3種算法。

［關鍵詞］ 軟件定義網絡； 多控制器部署； K-means++； 粒子群算法； 時延； 負載均衡

［中圖分類號］ TP393 ［文獻標識碼］ A

軟件定義網絡[1]（software defined networking， SDN）是一種新型的網絡體系結構[1]，它的[BP）]核心理念是將網絡中的控制平面與數據平面分離，控制平面通過單一的控制器管理網絡中的所有設備，但是隨著網絡規模的擴大，交換機數量的增加，單一的控制器在處理越來越多的請求時不堪重負，從而無法保證高效的性能。有學者提出了一種分層式設計的多控制器體系結構解決這些問題[2]，例如Kandoo[3]，此種體系結構由多個控制器構成，且控制器間可以相互通信，隨著這一體系的誕生，多個控制器如何合理放置在控制平面上成為了亟待解決的問題。多控制器放置問題[4]（controller placement problem， CPP）是一個NP難問題，在SDN網絡中部署多個控制器，針對設定的優化目標，選出最合適的控制器數量和最佳放置位置，確定控制器與其管理的交換機的映射。

Heller[5]等首次提出了SDN網絡中的CPP，Torkamani[6]等提出了一種基于GSO算法的多控制器部署方法并應用于不同類型網絡中，實現了最小的時間延遲，沒有討論控制器的負載情況。Singh[7]等提出一種基于VBO的方法，實現了可靠的CPP，但是只考慮了總平均時延。馬勤[8，9]等提出的方法以負載均衡為主要目標進行多控制器的部署，實現了網絡中控制器與交換機的最佳分配問題，但沒有考慮控制器間的時延。黃爾杰[10，11]等提出了以最小化時延為優化目標的控制器部署方法，但未考慮控制器的負載。Wang[12]等提出了一種優化的K-means算法，減少了交換機與控制器之間的延遲，但未考慮控制器間的延遲和控制器的負載。

綜上，部分研究以時延為指標，僅考慮交換機與控制器之間的時延，而忽略了控制器間的時延。另外部分研究以負載均衡為指標，忽略了控制器的負載，未能從多個方面綜合考慮。故本文綜合考慮交換機與控制器之間以及控制器間的時延和負載均衡對CPP的影響，提出基于K-means++和粒子群算法（particle swarm optimization algorithm，PSO）的SDN多控制器部署方法，通過K-means++算法劃分初始控制域并確定控制器位置，再引入PSO算法保證網絡鏈路連通性，同時以最小化時延和負載均衡為優化目標，調整控制域，得出最佳的控制器部署位置和控制域。

1 問題描述及模型

1.1 問題描述

控制器作為SDN網絡中控制平面的核心，數據平面的交換機轉發數據包時將流請求發送給相應的控制器，控制器收到請求后下發流表給交換機，在這個過程中，SDN網絡的性能主要由兩個方面決定，一是交換機與控制器之間的時延以及控制器間的時延，其影響著數據的傳輸速度；二是控制器收到請求時承載的負載容量，其決定著數據傳輸的穩定性，這兩方面共同決定著SDN的網絡性能。

在SDN網絡的數據傳輸中，若通信設備之間產生的傳播時延過長，則會影響網絡的整體性能，因此降低交換機與控制器以及控制器間通信產生的平均時延和最壞時延能保證網絡數據傳輸的高效性。

負載均衡是衡量網絡性能的重要指標。如果控制器超過其自身負載容量，就會導致網絡事件的響應時延增加和控制器故障率增加等問題[13]，造成網絡的不穩定性。

其中，式（11）為需要優化的目標函數，且θ，μ，ρ表示不同指標的權重，式（12）表示θ，μ，ρ的取值范圍，式（13）表示控制器的負載應小于其最大負載μi。

2 多控制器部署方法

2.1 初始控制域劃分和控制器部署

在SDN網絡中部署多個控制器，每個控制器管理其周邊的若干個交換機，在網絡中形成多個控制域，因此控制器部署過程可以被描述為樣本點的聚類過程，本文假設一個控制器管理一個控制域，控制域類比為聚類，控制器的位置類比為聚類中心，交換機的位置類比為聚類的其他樣本點。由于K-means算法隨機選取樣本點作為初始聚類中心，極大影響了算法的收斂速度，導致最終聚類結果差異較大，而K-means++算法初始聚類中心的選取進行了改進，通過計算每個樣本點被選為聚類中心的概率來確定聚類中心，加快了算法的收斂速度，因此本文采用K-means++算法。

對于第一個聚類中心的選取，選擇樣本節點間距離相對較遠的點作為第一個聚類中心，樣本節點間的距離采用歐式距離計算，dis為每個樣本節點與當前聚類中心的最短距離。

在區間0，1之間生成一個均勻分布的偽隨機r，判斷r所在的概率區間位置，選出對應的樣本節點作為聚類中心。確定k個初始聚類中心后，使用K-means算法，選出k個聚類中心，不斷迭代，直到聚類中心不再改變，最終選出k個聚類中心的位置和聚類，即控制器部署位置和控制域。

2.2 控制域和控制器位置的優化

經過K-means++算法對網絡的控制域劃分和初始控制器部署后，控制域劃分存在兩點不足之處，一是忽略了網絡實際鏈路連通性，故使用dijkstra算法計算拓撲圖中兩個節點之間的最短路徑，得到最短路徑矩陣CP，保證鏈路的連通性。二是聚類算法計算的距離是歐式距離，但是在實際網絡中，網絡節點間是物理距離，因此通過球面半正矢公式（1）計算每條鏈路的實際距離，得到距離矩陣DP。對SDN網絡中平均傳播時延、最壞傳播時延、負載均衡參數這3個指標，采用粒子群算法（particle swarm optimization algorithm，PSO）進一步優化控制域和控制器位置。

粒子群算法[15]是一種以群體迭代為基礎的算法，在整體空間內，粒子搜尋時僅僅跟隨最優粒子。由于PSO算法具有良好的全局搜索能力，對于多控制器部署的多目標問題能更好地求出最優解，因此，在控制域和控制器位置的優化過程中，對建立的多控制器部署模型，采用PSO算法找到可行的部署方案，每個粒子都表示一次可行的部署方式。PSO算法以初始控制器的位置為粒子的初始位置，式（11）作為適應度函數，不斷迭代，粒子群中的粒子搜尋合適的交換機位置作為新的控制器位置，確定控制器的最佳位置。

首先初始化粒子群，粒子將初始控制器的位置設為當前最優位置Ppbest，設置粒子的初始和飛行速度，粒子的搜尋路線為網絡的鏈路，設置最大粒子群總數為網絡拓撲節點數。PSO算法根據輸入的控制器集合C，控制器管理的交換機集合Sc，對初始劃分的控制域，選擇負載最大的控制器，找出其管理的控制域邊緣位置交換機節點為可移動節點，以距離和Fmin為指標不斷調整可移動交換機的位置，劃分到相鄰最近的控制域，進一步調節控制域間的最小時延和控制器的負載。以式（11）作為適應度函數，找到粒子的當前個體極值pbesti和粒子群的當前最優解gbesti，更新粒子的速度和位置

其中，ω表示慣性因子，c1和c2稱為增速常數，一般取值為c1=c2∈［0，4］，rand（）是區間0，1上的隨機數。

若Fmin（Pposition）lt;Fmin（Ppbest）， 將粒子的當前位置Pposition設為局部最優位置Ppbest， 若Fmin（Ppbest）lt;Fmin（Pgbest）， 將粒子的局部最優位置Ppbest設為全局最優位置Pgbest， 直到最大迭代次數， 得到最終的控制器部署位置Pgbest， 控制域的交換機集合Sc。

2.3 基于K-means[HT5，6H]++和粒子群算法的多控制器部署方法流程

基于K-means++和粒子群算法的多控制器部署方法首先采用K-means++算法對網絡的控制域進行劃分，并初步部署控制器位置，然后采用PSO算法以目標函數作為適應度函數，多個粒子并行搜索最優解，進一步優化控制域和控制器的位置，以達到網絡中時延最小和控制器負載均衡的目的。多控制器部署方法流程如圖1所示。算法的具體步驟如下所示。

Step 1：根據公式（14）選出樣本節點間距離最大的節點作為第一個聚類中心，再根據公式（15）和公式（16）計算其余樣本節點被選為聚類中心的概率，確定k個初始聚類中心；

Step 2：計算每個樣本節點到各個聚類中心的最短距離dis，將樣本節點劃分到距離最近的聚類中心所對應的類中；

Step 3：計算每個類中所有樣本節點的均值，更新每個類的聚類中心，直到聚類中心位置不再改變，得到k個初始控制域和控制器位置；

Step 4：使用dijkstra算法計算網絡節點間最短路徑矩陣CP，根據公式（1）計算網絡鏈路的距離矩陣DP；

Step 5：對負載最大的控制域，將距離控制域邊緣最近的交換機分配給相鄰的控制域，更新控制域的交換機集合Sc；

Step 6：設置粒子的初始位置為初始控制器的位置，設置粒子的初始和飛行速度，設置最大粒子群總數為網絡拓撲節點數；

Step 7：根據公式（11）計算適應度函數值Fmin，找到粒子的當前個體極值pbesti和粒子群的當前最優解gbesti；

Step 8：根據公式（17）和公式（18）分別更新粒子P的速度和位置，更新粒子的局部最優位置Ppbest和全局最優位置Pgbest；

Step 9：若達到最大迭代次數，則輸出控制器部署位置Pgbest，控制域的交換機集合Sc，否則返回到Step 5繼續迭代。

3 仿真實驗與分析

3.1 實驗設計

為驗證基于K-means++和粒子群算法的多控制器部署方法的有效性，在實際網絡拓撲中對該方法進行仿真驗證。仿真使用Pycharm軟件對多控制器部署模型進行建模，該模型為最小化時延和負載均衡的多目標優化模型，采用K-means++算法和PSO算法對模型求最優解，得出最佳的控制器部署位置和控制域。實驗選擇網絡拓撲動物園的Savvis網絡、IRIS網絡和Colt Telecom網絡，分別為小、中、大型網絡型拓撲，網絡拓撲信息如表1所示。假設實驗中控制器的性能相同，交換機的性能相同，控制器負載最大值μ設置為1700，交換機請求λ設置為90，最大迭代次數設置為150，加權因子θ，μ，ρ分別設置為0.3、0.2、0.5。

3.2 實驗結果分析

將本文算法與隨機算法、K-means++算法、PSO算法在平均傳播時延、最壞傳播時延和負載均衡參數這3個性能指標上進行比較，圖2、圖3、圖4分別為Savvis網絡、IRIS網絡、Colt Telecom網絡的性能指標，為方便對實驗結果分析進行表述，將基于K-means++與粒子群算法的多控制器部署方法簡稱為KPSO算法。

實驗1：平均傳播時延。實驗結果如圖2a、圖3a和圖4a所示，可以看出隨著控制器數量的增加，平均傳播時延均在降低，圖2a中，隨機算法的平均傳播時延均高于其他3種算法，K-means++算法的波動較大，綜合圖2a和圖3a來看，PSO與KPSO算法的折線趨勢相對平穩，且KPSO算法的平均傳播時延始終低于PSO算法，說明在中小型規模網絡中，KPSO算法在平均傳播時延上更加穩定且時延更低。在圖4a中，控制器個數為15，16，19時，K-means++算法的平均傳播時延略低于KPSO算法，這是由于隨著網絡規模增大，網絡節點增多，K-means++算法的聚類特性更能表現出來，但K-means++算法在考慮傳播時延時忽略了鏈路連通性，故在實際網絡環境中部署控制器時，KPSO算法更具備現實合理性。

實驗2： 最壞傳播時延。實驗結果如圖2b、圖3b和圖4b所示，可以看出最壞傳播時延整體趨勢隨著控制器數量增加而降低。圖2b中，控制器個數為2時，KPSO算法的最壞傳播時延高于PSO算法，圖3b中，控制器數量為6時，KPSO算法的最壞傳播時延略高于PSO算法，分析其原因，PSO算法在中小型規模網絡中選取初始控制器位置時，控制器間距離較近，部署的控制器個數越少，則控制器間的最長路徑距離更短。從圖4b中可以看出在控制器個數相同的情況下，KPSO算法在最壞傳播時延上均低于其他三種算法，綜合來看，KPSO算法均適用于小、中、大型網絡上的多控制器部署。

實驗3：負載均衡。實驗結果如圖2c、圖3c和圖4c所示，KPSO算法的負載均衡參數均低于其他3種算法。圖1c中，KPSO算法的負載均衡參數趨勢更平穩，更加接近于1，最大值與最小值的差值為0.33，說明在小規模網絡中，對比其他3種算法，KPSO算法的負載均衡穩定性最好。圖3c中，控制器個數為8時，K-means++算法、PSO算法、KPSO算法的負載均衡參數均上升，隨后又下降，分析原因可能是此時三種算法均對控制域劃分得不均衡。

圖4c中，控制器個數少于17時，K-means++算法的負載均衡參數大致呈現上升趨勢，這是因為大規模網絡中節點較多，控制器個數越少，控制域也越少，其管理的交換機個數更容易出現不均衡情況，隨著控制器個數增加，該情況會變好，控制器管理的交換機個數更加均衡。

4 結論

以最小化時延和負載均衡為優化目標，建立多控制器部署模型，提出了一種基于K-means++和粒子群算法的SDN多控制器部署方法，并對模型進行求解。該方法將K-means++算法的分類特點與PSO算法尋找目標函數最優解的特點相結合，能夠有效地劃分控制域，保證網絡的連通性，實現時延最小化和負載均衡的多控制器部署。實驗結果表明，與隨機算法、K-means++算法和PSO算法相比，本文提出的方法在不同規模的網絡中，實現了最小的平均傳播時延和最壞傳播時延，且保證了控制器的負載均衡。

［ 參 考 文 獻 ］

［1］ ZHANG J LAN， Y. HU， et al. Survey on scalability of control plane in Software-Defined networking[J]. Journal of Software， 2018， 29（01）：160-175.

[2] KILLI B，" RAO S. Controller placement in software defined networks： a comprehensive survey[J].Computer networks， 2019 （163）： 106883.

[3] YEGANEH S，" YASHAR G. KANDOO. A framework for efficient and scalable offloading of control applications[C]. In Proc. 1st Workshop on Hot Topics in Software Defined Networking， 2012： 19-24.

[4] 賈吾財，呂光宏，王桂芝，等.SDN多控制器放置問題研究綜述[J].計算機科學，2020，47（07）：206-212.

[5] HELLER B，SHERWOOD R，MCKEOWN N.The controller placement problem[J].ACM SIGCOMM Computer Communication Review，2012，42：473-478.

[6] TORKAMANI A， SAHAND. A new GSO based method for SDN controller placement[J]. Jahanshahi， Computer Communications， 2020， 163：" 91-108.

[7] SINGH A，" MAURYA S. Heuristic approaches for the reliable SDN controller placement problem[J]. Transactions on Emerging Telecommunications Technologies，" 2020，31： e3761.

[8] 馬勤，李志芳.SDN中一種多控制器負載均衡方案[J].西南師范大學學報（自然科學版），2021，46（07）：114-119.

[9] 唐鐵斌，劉煒.基于改進樽海鞘群算法的SDN控制器部署算法[J].計算機應用與軟件，2021，38（12）：291-297.

[10] 黃爾杰，尚秋峰.基于時延的軟件定義網絡控制器部署策略研究[J].科技與創新，2019（03）：68-69.

[11] QI Y， WANG D， YAO W，et al.Towards multi-controller placement for SDN based on density peaks clustering[C]∥ICC 2019-2019 IEEE International Conference on Communications （ICC）.IEEE， 2019： 1-6.

[12] WANG G，" ZHAO Y，" HUANG J，et al. A K-means-based network partition algorithm for controller placement in software defined network[C]. 2016 IEEE International Conference on Communications （ICC）， 2016： 1-6.

[13] YAO G，" BI J， GUO L. On the cascading failures of multi-controllers in software defined networks[C]. 2013 21st IEEE International Conference on Network Protocols （ICNP）， 2013： 1-2.

[14] YAO G，BI J，LI Y，et al.On the capacitated controller placement problem in software defined networks[J].IEEE Communications Letters，2014，18：1339-1342.

[15] KENNEDY J，" EBERHART R. Particle swarm optimization[C]. In Proceedings of the 4th IEEE International Conference on Neural Networks. Piscataway： IEEE ServiceCenter，1995： 1942-1948.

Multi-controller Deployment Method Based on K-means++ andParticle Swarm Optimization in SDN

XU Hui， WU Meilian

（School of Computer Science， Hubei Univ. of Tech.， Wuhan 430068，China）

Abstract： To solve the problem of multi-controller deployment in software defined networking， a multi-controller deployment method based on K-means++ and particle swarm optimization is proposed. Firstly， the K-means++ algorithm is used to cluster the network nodes to obtain the initial control domain and controller position in the network， and then the particle swarm optimization algorithm is used to minimize delay and load balancing as the optimization goal， and multiple particles search for the optimal solution in parallel to further optimize the control domain and controller position. Compared with the multi-controller deployment methods of random algorithm， K-means++ algorithm and particle swarm optimization algorithm in small， medium and large scale network topology， simulation results show that it is more stable and less delay than the other three algorithms in average propagation delay and load balancing in small and medium scale network， and average propagation delay， the worst propagation delay and the load balancing of the controller are better than the other three algorithms in large scale network.

Keywords： Software Defined Networking; multi-controller deployment; K-means++; particle swarm optimization algorithm; delay; load balancing

［責任編校： 裴 琴］

［收稿日期］ 2022-10-20

［基金項目］ 國家自然科學基金（61602162）

［第一作者］ 徐 慧（1983—）， 女， 湖北武漢人， 工學博士， 湖北工業大學教授， 研究方向為網絡管理與安全。