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

［摘 要］ 針對(duì)軟件定義網(wǎng)絡(luò)中的多控制器部署問(wèn)題，首先通過(guò)K-means++算法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)聚類(lèi)，得到網(wǎng)絡(luò)中初始控制域和控制器位置，然后使用粒子群算法以最小化時(shí)延和負(fù)載均衡為優(yōu)化目標(biāo)，多個(gè)粒子并行搜索最優(yōu)解，進(jìn)一步優(yōu)化控制域和控制器位置。在小、中、大型網(wǎng)絡(luò)拓?fù)渖吓c隨機(jī)算法、K-means++算法、粒子群算法的多控制器部署方法比較，仿真結(jié)果表明，在中小型網(wǎng)絡(luò)中，比其他3種算法在平均傳播時(shí)延和負(fù)載均衡上更加穩(wěn)定且時(shí)延更低，在大型網(wǎng)絡(luò)中，平均傳播時(shí)延，最壞傳播時(shí)延和控制器的負(fù)載均衡上均優(yōu)于其他3種算法。

［關(guān)鍵詞］ 軟件定義網(wǎng)絡(luò)； 多控制器部署； K-means++； 粒子群算法； 時(shí)延； 負(fù)載均衡

［中圖分類(lèi)號(hào)］ TP393 ［文獻(xiàn)標(biāo)識(shí)碼］ A

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

Heller[5]等首次提出了SDN網(wǎng)絡(luò)中的CPP，Torkamani[6]等提出了一種基于GSO算法的多控制器部署方法并應(yīng)用于不同類(lèi)型網(wǎng)絡(luò)中，實(shí)現(xiàn)了最小的時(shí)間延遲，沒(méi)有討論控制器的負(fù)載情況。Singh[7]等提出一種基于VBO的方法，實(shí)現(xiàn)了可靠的CPP，但是只考慮了總平均時(shí)延。馬勤[8，9]等提出的方法以負(fù)載均衡為主要目標(biāo)進(jìn)行多控制器的部署，實(shí)現(xiàn)了網(wǎng)絡(luò)中控制器與交換機(jī)的最佳分配問(wèn)題，但沒(méi)有考慮控制器間的時(shí)延。黃爾杰[10，11]等提出了以最小化時(shí)延為優(yōu)化目標(biāo)的控制器部署方法，但未考慮控制器的負(fù)載。Wang[12]等提出了一種優(yōu)化的K-means算法，減少了交換機(jī)與控制器之間的延遲，但未考慮控制器間的延遲和控制器的負(fù)載。

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

1 問(wèn)題描述及模型

1.1 問(wèn)題描述

控制器作為SDN網(wǎng)絡(luò)中控制平面的核心，數(shù)據(jù)平面的交換機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)將流請(qǐng)求發(fā)送給相應(yīng)的控制器，控制器收到請(qǐng)求后下發(fā)流表給交換機(jī)，在這個(gè)過(guò)程中，SDN網(wǎng)絡(luò)的性能主要由兩個(gè)方面決定，一是交換機(jī)與控制器之間的時(shí)延以及控制器間的時(shí)延，其影響著數(shù)據(jù)的傳輸速度；二是控制器收到請(qǐng)求時(shí)承載的負(fù)載容量，其決定著數(shù)據(jù)傳輸?shù)姆€(wěn)定性，這兩方面共同決定著SDN的網(wǎng)絡(luò)性能。

在SDN網(wǎng)絡(luò)的數(shù)據(jù)傳輸中，若通信設(shè)備之間產(chǎn)生的傳播時(shí)延過(guò)長(zhǎng)，則會(huì)影響網(wǎng)絡(luò)的整體性能，因此降低交換機(jī)與控制器以及控制器間通信產(chǎn)生的平均時(shí)延和最壞時(shí)延能保證網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)母咝浴?/p>

負(fù)載均衡是衡量網(wǎng)絡(luò)性能的重要指標(biāo)。如果控制器超過(guò)其自身負(fù)載容量，就會(huì)導(dǎo)致網(wǎng)絡(luò)事件的響應(yīng)時(shí)延增加和控制器故障率增加等問(wèn)題[13]，造成網(wǎng)絡(luò)的不穩(wěn)定性。

其中，式（11）為需要優(yōu)化的目標(biāo)函數(shù)，且θ，μ，ρ表示不同指標(biāo)的權(quán)重，式（12）表示θ，μ，ρ的取值范圍，式（13）表示控制器的負(fù)載應(yīng)小于其最大負(fù)載μi。

2 多控制器部署方法

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

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

對(duì)于第一個(gè)聚類(lèi)中心的選取，選擇樣本節(jié)點(diǎn)間距離相對(duì)較遠(yuǎn)的點(diǎn)作為第一個(gè)聚類(lèi)中心，樣本節(jié)點(diǎn)間的距離采用歐式距離計(jì)算，dis為每個(gè)樣本節(jié)點(diǎn)與當(dāng)前聚類(lèi)中心的最短距離。

在區(qū)間0，1之間生成一個(gè)均勻分布的偽隨機(jī)r，判斷r所在的概率區(qū)間位置，選出對(duì)應(yīng)的樣本節(jié)點(diǎn)作為聚類(lèi)中心。確定k個(gè)初始聚類(lèi)中心后，使用K-means算法，選出k個(gè)聚類(lèi)中心，不斷迭代，直到聚類(lèi)中心不再改變，最終選出k個(gè)聚類(lèi)中心的位置和聚類(lèi)，即控制器部署位置和控制域。

2.2 控制域和控制器位置的優(yōu)化

經(jīng)過(guò)K-means++算法對(duì)網(wǎng)絡(luò)的控制域劃分和初始控制器部署后，控制域劃分存在兩點(diǎn)不足之處，一是忽略了網(wǎng)絡(luò)實(shí)際鏈路連通性，故使用dijkstra算法計(jì)算拓?fù)鋱D中兩個(gè)節(jié)點(diǎn)之間的最短路徑，得到最短路徑矩陣CP，保證鏈路的連通性。二是聚類(lèi)算法計(jì)算的距離是歐式距離，但是在實(shí)際網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)間是物理距離，因此通過(guò)球面半正矢公式（1）計(jì)算每條鏈路的實(shí)際距離，得到距離矩陣DP。對(duì)SDN網(wǎng)絡(luò)中平均傳播時(shí)延、最壞傳播時(shí)延、負(fù)載均衡參數(shù)這3個(gè)指標(biāo)，采用粒子群算法（particle swarm optimization algorithm，PSO）進(jìn)一步優(yōu)化控制域和控制器位置。

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

首先初始化粒子群，粒子將初始控制器的位置設(shè)為當(dāng)前最優(yōu)位置Ppbest，設(shè)置粒子的初始和飛行速度，粒子的搜尋路線(xiàn)為網(wǎng)絡(luò)的鏈路，設(shè)置最大粒子群總數(shù)為網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)。PSO算法根據(jù)輸入的控制器集合C，控制器管理的交換機(jī)集合Sc，對(duì)初始劃分的控制域，選擇負(fù)載最大的控制器，找出其管理的控制域邊緣位置交換機(jī)節(jié)點(diǎn)為可移動(dòng)節(jié)點(diǎn)，以距離和Fmin為指標(biāo)不斷調(diào)整可移動(dòng)交換機(jī)的位置，劃分到相鄰最近的控制域，進(jìn)一步調(diào)節(jié)控制域間的最小時(shí)延和控制器的負(fù)載。以式（11）作為適應(yīng)度函數(shù)，找到粒子的當(dāng)前個(gè)體極值pbesti和粒子群的當(dāng)前最優(yōu)解gbesti，更新粒子的速度和位置

其中，ω表示慣性因子，c1和c2稱(chēng)為增速常數(shù)，一般取值為c1=c2∈［0，4］，rand（）是區(qū)間0，1上的隨機(jī)數(shù)。

若Fmin（Pposition）lt;Fmin（Ppbest）， 將粒子的當(dāng)前位置Pposition設(shè)為局部最優(yōu)位置Ppbest， 若Fmin（Ppbest）lt;Fmin（Pgbest）， 將粒子的局部最優(yōu)位置Ppbest設(shè)為全局最優(yōu)位置Pgbest， 直到最大迭代次數(shù)， 得到最終的控制器部署位置Pgbest， 控制域的交換機(jī)集合Sc。

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

基于K-means++和粒子群算法的多控制器部署方法首先采用K-means++算法對(duì)網(wǎng)絡(luò)的控制域進(jìn)行劃分，并初步部署控制器位置，然后采用PSO算法以目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，多個(gè)粒子并行搜索最優(yōu)解，進(jìn)一步優(yōu)化控制域和控制器的位置，以達(dá)到網(wǎng)絡(luò)中時(shí)延最小和控制器負(fù)載均衡的目的。多控制器部署方法流程如圖1所示。算法的具體步驟如下所示。

Step 1：根據(jù)公式（14）選出樣本節(jié)點(diǎn)間距離最大的節(jié)點(diǎn)作為第一個(gè)聚類(lèi)中心，再根據(jù)公式（15）和公式（16）計(jì)算其余樣本節(jié)點(diǎn)被選為聚類(lèi)中心的概率，確定k個(gè)初始聚類(lèi)中心；

Step 2：計(jì)算每個(gè)樣本節(jié)點(diǎn)到各個(gè)聚類(lèi)中心的最短距離dis，將樣本節(jié)點(diǎn)劃分到距離最近的聚類(lèi)中心所對(duì)應(yīng)的類(lèi)中；

Step 3：計(jì)算每個(gè)類(lèi)中所有樣本節(jié)點(diǎn)的均值，更新每個(gè)類(lèi)的聚類(lèi)中心，直到聚類(lèi)中心位置不再改變，得到k個(gè)初始控制域和控制器位置；

Step 4：使用dijkstra算法計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)間最短路徑矩陣CP，根據(jù)公式（1）計(jì)算網(wǎng)絡(luò)鏈路的距離矩陣DP；

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

Step 6：設(shè)置粒子的初始位置為初始控制器的位置，設(shè)置粒子的初始和飛行速度，設(shè)置最大粒子群總數(shù)為網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)數(shù)；

Step 7：根據(jù)公式（11）計(jì)算適應(yīng)度函數(shù)值Fmin，找到粒子的當(dāng)前個(gè)體極值pbesti和粒子群的當(dāng)前最優(yōu)解gbesti；

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

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

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證基于K-means++和粒子群算法的多控制器部署方法的有效性，在實(shí)際網(wǎng)絡(luò)拓?fù)渲袑?duì)該方法進(jìn)行仿真驗(yàn)證。仿真使用Pycharm軟件對(duì)多控制器部署模型進(jìn)行建模，該模型為最小化時(shí)延和負(fù)載均衡的多目標(biāo)優(yōu)化模型，采用K-means++算法和PSO算法對(duì)模型求最優(yōu)解，得出最佳的控制器部署位置和控制域。實(shí)驗(yàn)選擇網(wǎng)絡(luò)拓?fù)鋭?dòng)物園的Savvis網(wǎng)絡(luò)、IRIS網(wǎng)絡(luò)和Colt Telecom網(wǎng)絡(luò)，分別為小、中、大型網(wǎng)絡(luò)型拓?fù)洌W(wǎng)絡(luò)拓?fù)湫畔⑷绫?所示。假設(shè)實(shí)驗(yàn)中控制器的性能相同，交換機(jī)的性能相同，控制器負(fù)載最大值μ設(shè)置為1700，交換機(jī)請(qǐng)求λ設(shè)置為90，最大迭代次數(shù)設(shè)置為150，加權(quán)因子θ，μ，ρ分別設(shè)置為0.3、0.2、0.5。

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

將本文算法與隨機(jī)算法、K-means++算法、PSO算法在平均傳播時(shí)延、最壞傳播時(shí)延和負(fù)載均衡參數(shù)這3個(gè)性能指標(biāo)上進(jìn)行比較，圖2、圖3、圖4分別為Savvis網(wǎng)絡(luò)、IRIS網(wǎng)絡(luò)、Colt Telecom網(wǎng)絡(luò)的性能指標(biāo)，為方便對(duì)實(shí)驗(yàn)結(jié)果分析進(jìn)行表述，將基于K-means++與粒子群算法的多控制器部署方法簡(jiǎn)稱(chēng)為KPSO算法。

實(shí)驗(yàn)1：平均傳播時(shí)延。實(shí)驗(yàn)結(jié)果如圖2a、圖3a和圖4a所示，可以看出隨著控制器數(shù)量的增加，平均傳播時(shí)延均在降低，圖2a中，隨機(jī)算法的平均傳播時(shí)延均高于其他3種算法，K-means++算法的波動(dòng)較大，綜合圖2a和圖3a來(lái)看，PSO與KPSO算法的折線(xiàn)趨勢(shì)相對(duì)平穩(wěn)，且KPSO算法的平均傳播時(shí)延始終低于PSO算法，說(shuō)明在中小型規(guī)模網(wǎng)絡(luò)中，KPSO算法在平均傳播時(shí)延上更加穩(wěn)定且時(shí)延更低。在圖4a中，控制器個(gè)數(shù)為15，16，19時(shí)，K-means++算法的平均傳播時(shí)延略低于KPSO算法，這是由于隨著網(wǎng)絡(luò)規(guī)模增大，網(wǎng)絡(luò)節(jié)點(diǎn)增多，K-means++算法的聚類(lèi)特性更能表現(xiàn)出來(lái)，但K-means++算法在考慮傳播時(shí)延時(shí)忽略了鏈路連通性，故在實(shí)際網(wǎng)絡(luò)環(huán)境中部署控制器時(shí)，KPSO算法更具備現(xiàn)實(shí)合理性。

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

實(shí)驗(yàn)3：負(fù)載均衡。實(shí)驗(yàn)結(jié)果如圖2c、圖3c和圖4c所示，KPSO算法的負(fù)載均衡參數(shù)均低于其他3種算法。圖1c中，KPSO算法的負(fù)載均衡參數(shù)趨勢(shì)更平穩(wěn)，更加接近于1，最大值與最小值的差值為0.33，說(shuō)明在小規(guī)模網(wǎng)絡(luò)中，對(duì)比其他3種算法，KPSO算法的負(fù)載均衡穩(wěn)定性最好。圖3c中，控制器個(gè)數(shù)為8時(shí)，K-means++算法、PSO算法、KPSO算法的負(fù)載均衡參數(shù)均上升，隨后又下降，分析原因可能是此時(shí)三種算法均對(duì)控制域劃分得不均衡。

圖4c中，控制器個(gè)數(shù)少于17時(shí)，K-means++算法的負(fù)載均衡參數(shù)大致呈現(xiàn)上升趨勢(shì)，這是因?yàn)榇笠?guī)模網(wǎng)絡(luò)中節(jié)點(diǎn)較多，控制器個(gè)數(shù)越少，控制域也越少，其管理的交換機(jī)個(gè)數(shù)更容易出現(xiàn)不均衡情況，隨著控制器個(gè)數(shù)增加，該情況會(huì)變好，控制器管理的交換機(jī)個(gè)數(shù)更加均衡。

4 結(jié)論

以最小化時(shí)延和負(fù)載均衡為優(yōu)化目標(biāo)，建立多控制器部署模型，提出了一種基于K-means++和粒子群算法的SDN多控制器部署方法，并對(duì)模型進(jìn)行求解。該方法將K-means++算法的分類(lèi)特點(diǎn)與PSO算法尋找目標(biāo)函數(shù)最優(yōu)解的特點(diǎn)相結(jié)合，能夠有效地劃分控制域，保證網(wǎng)絡(luò)的連通性，實(shí)現(xiàn)時(shí)延最小化和負(fù)載均衡的多控制器部署。實(shí)驗(yàn)結(jié)果表明，與隨機(jī)算法、K-means++算法和PSO算法相比，本文提出的方法在不同規(guī)模的網(wǎng)絡(luò)中，實(shí)現(xiàn)了最小的平均傳播時(shí)延和最壞傳播時(shí)延，且保證了控制器的負(fù)載均衡。

［ 參 考 文 獻(xiàn) ］

［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] 賈吾財(cái)，呂光宏，王桂芝，等.SDN多控制器放置問(wèn)題研究綜述[J].計(jì)算機(jī)科學(xué)，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中一種多控制器負(fù)載均衡方案[J].西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2021，46（07）：114-119.

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

[10] 黃爾杰，尚秋峰.基于時(shí)延的軟件定義網(wǎng)絡(luò)控制器部署策略研究[J].科技與創(chuàng)新，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

［責(zé)任編校： 裴 琴］

［收稿日期］ 2022-10-20

［基金項(xiàng)目］ 國(guó)家自然科學(xué)基金（61602162）

［第一作者］ 徐 慧（1983—）， 女， 湖北武漢人， 工學(xué)博士， 湖北工業(yè)大學(xué)教授， 研究方向?yàn)榫W(wǎng)絡(luò)管理與安全。