劉振鵬， 王鑫鵬， 李 明， 任少松， 李小菲

(1.河北大學(xué) 電子信息工程學(xué)院，河北 保定 071002；2.河北大學(xué) 信息技術(shù)中心，河北 保定 071002)

0 引言

隨著網(wǎng)絡(luò)規(guī)模的增大，如何優(yōu)化網(wǎng)絡(luò)性能成為至關(guān)重要的問(wèn)題。軟件定義網(wǎng)絡(luò)(software define network，SDN)是近年來(lái)新興的一種網(wǎng)絡(luò)結(jié)構(gòu)，它將網(wǎng)絡(luò)的控制層和數(shù)據(jù)層解耦，利用集中式的控制器對(duì)底層設(shè)備進(jìn)行可編程化管理，進(jìn)而實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)資源的靈活調(diào)配[1]。然而，隨著大數(shù)據(jù)時(shí)代的到來(lái)，在大范圍的SDN網(wǎng)絡(luò)中部署健壯的控制平面仍然是一個(gè)主要的挑戰(zhàn)。為了解決這些問(wèn)題，引入了一個(gè)邏輯上集中、物理上分布的控制平面[2]。這種類型的控制體系結(jié)構(gòu)通常由多個(gè)控制器組成，這些控制器之間彼此相互通信，Kandoo[3]就是這種類型的一個(gè)例子。但在引入這一體系的同時(shí)，也出現(xiàn)了多個(gè)控制器如何部署的問(wèn)題。

目前，已經(jīng)有很多對(duì)SDN控制器部署研究的文獻(xiàn)。文獻(xiàn)[4]首次提出控制器部署問(wèn)題是一個(gè)NP問(wèn)題，以平均時(shí)延和最大時(shí)延為指標(biāo)，選擇控制器位置。文獻(xiàn)[5-8]提出了幾種基于群體的智能優(yōu)化算法，通過(guò)考慮時(shí)延作為單一目標(biāo)參數(shù)來(lái)求解控制器最優(yōu)部署位置。以上文獻(xiàn)在研究控制器時(shí)延問(wèn)題上均取得不錯(cuò)的效果，但在實(shí)際SDN環(huán)境下，控制器的負(fù)載能力也是一個(gè)不可忽略的因素。文獻(xiàn)[9]提出了基于控制器的負(fù)載平衡因子，在已知控制器數(shù)量的情況下，通過(guò)最小化負(fù)載平衡因子和總流請(qǐng)求代價(jià)來(lái)獲得特定控制器的位置。文獻(xiàn)[10]為了保證控制器負(fù)載均衡和相對(duì)較低的時(shí)延，提出了一種基于層次K-means算法的多控制器部署方案，但該方案只考慮控制器子域如何分配交換機(jī)數(shù)量，在單個(gè)控制器的負(fù)載能力上未作考慮。文獻(xiàn)[11]提出一個(gè)控制器位置-分配模型，引入公平負(fù)載分配函數(shù)來(lái)平衡控制器負(fù)載，并減少控制器之間的時(shí)延，但該方案未對(duì)整個(gè)網(wǎng)絡(luò)總體性能進(jìn)行分析。

為此，本文綜合考慮SDN環(huán)境下控制器的時(shí)延和負(fù)載問(wèn)題，提出控制器部署算法(MCP),并用改進(jìn)的粒子群算法(APSO)和MCP算法結(jié)合的APSO_MCP算法解決多控制器部署問(wèn)題。

1 控制器部署模型

1.1 問(wèn)題描述

在SDN架構(gòu)中，控制平面的控制器作為決策和信息收集的角色管理著數(shù)據(jù)平面的交換機(jī)，交換機(jī)與控制器之間的請(qǐng)求時(shí)延和處理時(shí)間影響了SDN網(wǎng)絡(luò)的整體性能。數(shù)據(jù)包到達(dá)控制器和完成處理返回的時(shí)間由2個(gè)因素共同決定，分別是交換機(jī)與控制器之間的距離和控制器管理的交換機(jī)數(shù)量。交換機(jī)與控制器之間的距離決定了傳播時(shí)延；而控制器管理的交換機(jī)數(shù)量決定了控制器的負(fù)載容量，即決定了流量轉(zhuǎn)發(fā)請(qǐng)求處理的時(shí)間。

時(shí)間延遲是影響網(wǎng)絡(luò)性能的一個(gè)重要因素。在SDN網(wǎng)絡(luò)中，時(shí)間延遲包括4個(gè)方面：傳輸、傳播、排隊(duì)和處理時(shí)延。對(duì)廣域網(wǎng)而言，在控制器不過(guò)載的前提下，傳播時(shí)延遠(yuǎn)超過(guò)其他時(shí)延，其他3種時(shí)延影響很小，可以忽略[12]。因此，在考慮時(shí)間延遲因素時(shí)選擇控制器和交換機(jī)之間的傳播時(shí)延。

負(fù)載是控制器的重要指標(biāo)。如果控制器負(fù)載過(guò)重就會(huì)導(dǎo)致其無(wú)法掌握實(shí)時(shí)的網(wǎng)絡(luò)狀態(tài)，造成網(wǎng)絡(luò)性能瓶頸。因此，將SDN的廣域網(wǎng)劃分為多個(gè)子域的網(wǎng)絡(luò)，合理分配各個(gè)子域內(nèi)的交換機(jī)數(shù)量，可以提高控制器的服務(wù)質(zhì)量，并且還可以限制廣播風(fēng)暴。

因此，本文考慮在平衡控制器負(fù)載能力的同時(shí)，最小化交換機(jī)和控制器之間的傳播時(shí)延。

1.2 系統(tǒng)模型

用無(wú)向圖G(V,E)來(lái)表示物理網(wǎng)絡(luò)拓?fù)?，V和E分別表示節(jié)點(diǎn)集合和邊的集合。n=|V|表示節(jié)點(diǎn)的個(gè)數(shù)。節(jié)點(diǎn)集合的每個(gè)節(jié)點(diǎn)都是交換機(jī)的位置,則有交換機(jī)集合S={s1,s2,…,sn}。假設(shè)節(jié)點(diǎn)集合中的每個(gè)節(jié)點(diǎn)都可能是控制器部署的位置，需要在網(wǎng)絡(luò)中部署k(k

Dp∩Dq=?，?p,q∈[1,k]，p≠q。

(1)

每個(gè)交換機(jī)只能由一個(gè)控制器控制,即

(2)

其中，當(dāng)交換機(jī)Si由控制器Cj控制時(shí),δSiCj=1，否則δSiCj=0。

每個(gè)控制器可以同時(shí)管理多個(gè)交換機(jī)，每個(gè)交換機(jī)只在一個(gè)控制器子域內(nèi)，則有：

(3)

(4)

式中：m為單個(gè)控制器管理的交換機(jī)個(gè)數(shù)；n為k個(gè)控制器管理的交換機(jī)個(gè)數(shù)之和。

1.2.1 時(shí)間延遲

交換機(jī)和控制器之間的時(shí)延在控制器部署問(wèn)題中是一種常用的度量方式，單個(gè)交換機(jī)和控制器之間的傳播時(shí)延可用式(5)表示：

(5)

式中：dSiCj為交換機(jī)Si和控制器Cj之間的傳輸距離；vc為數(shù)據(jù)在鏈路中的傳輸速度。

各個(gè)控制器子域的傳播時(shí)延和整個(gè)網(wǎng)絡(luò)的總時(shí)延可由式(6)和式(7)分別表示：

；

(6)

(7)

為了衡量整個(gè)網(wǎng)絡(luò)的控制器部署在時(shí)延方面的合理性，引入傳播時(shí)延標(biāo)準(zhǔn)差ξT來(lái)評(píng)判各個(gè)控制器子域的傳播時(shí)延與整個(gè)網(wǎng)絡(luò)的總傳播時(shí)延之間的差異，由式(8)表示：

(8)

(9)

式中：ξTmax為最差傳播時(shí)延標(biāo)準(zhǔn)差；ξTmin為最優(yōu)傳播時(shí)延標(biāo)準(zhǔn)差。

1.2.2 負(fù)載均衡

在網(wǎng)絡(luò)G(V,E)中，存在n個(gè)交換機(jī)，每個(gè)交換機(jī)的負(fù)載請(qǐng)求表示為λSiCj,則每個(gè)控制器子域的負(fù)載請(qǐng)求λCj為：

(10)

其中，每個(gè)控制器子域內(nèi)的負(fù)載λCj不能大于控制器Cj自身的最大負(fù)載能力λCj max,即滿足：

λCj≤λCjmax。

(11)

整個(gè)網(wǎng)絡(luò)的總負(fù)載和平均負(fù)載可由式(12)和式(13)表示：

(12)

(13)

為了衡量整個(gè)網(wǎng)絡(luò)在負(fù)載方面的合理性，引入了負(fù)載均衡標(biāo)準(zhǔn)差ξL來(lái)評(píng)判各個(gè)控制器子域的負(fù)載與整個(gè)網(wǎng)絡(luò)的平均負(fù)載的差異，如下所示：

(14)

(15)

1.2.3 控制器部署模型

針對(duì)以上以傳播時(shí)延差異性和負(fù)載差異性為指標(biāo)的多控制器部署問(wèn)題，可以找到一個(gè)合適的部署方案，即使以上指標(biāo)最小化，為此提出控制器部署模型為

(16)

其中，

α+β=1,0≤α，β≤1。

(17)

式中：F為優(yōu)化目標(biāo)，是整個(gè)網(wǎng)絡(luò)的性能；參數(shù)α、β為調(diào)節(jié)目標(biāo)函數(shù)的影響權(quán)重，參數(shù)α越大，越注重網(wǎng)絡(luò)整體的傳播時(shí)延差異性，參數(shù)β越大，越注重網(wǎng)絡(luò)整體的負(fù)載差異性。

2 控制器部署和改進(jìn)的粒子群算法

2.1 控制器部署算法(MCP)

為解決上述問(wèn)題，根據(jù)建立的模型提出多控制器部署算法(multi-controller placement，MCP)。MCP算法的目的是在保證整個(gè)網(wǎng)絡(luò)較高的負(fù)載均衡性能的基礎(chǔ)上降低各個(gè)控制器子域的傳播時(shí)延，從而保證整個(gè)網(wǎng)絡(luò)的總時(shí)延相對(duì)較低。

控制器部署算法分為3個(gè)階段：①網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)預(yù)處理(Step 1～3);②選取控制器部署位置(Step 4);③控制器子域部署交換機(jī)(Step 5～18)。在網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)預(yù)處理階段，將無(wú)向圖G(V,E)中節(jié)點(diǎn)和邊的數(shù)據(jù)矩陣轉(zhuǎn)換成距離矩陣，并通過(guò)Johnson全源最短路徑算法可以計(jì)算出每個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短距離。在選取控制器部署位置階段，采用粒子群算法初始化控制器部署位置。在控制器子域部署交換機(jī)階段，以距離最近原則開(kāi)始構(gòu)建子網(wǎng)(Step 5～10)，當(dāng)各個(gè)控制器子域管理的交換機(jī)個(gè)數(shù)相同且均等于?n/k」時(shí)，如果網(wǎng)絡(luò)中還有未被分配的交換機(jī)節(jié)點(diǎn)，對(duì)剩下的交換機(jī)節(jié)點(diǎn)繼續(xù)按照距離最近原則進(jìn)行分配，直到所有控制器節(jié)點(diǎn)都被分配(Step 11～18)。至此，k個(gè)負(fù)載均衡的控制器子域分配結(jié)束。

通過(guò)改進(jìn)的粒子群算法初始化控制器部署位置，確定控制器管理的交換機(jī)數(shù)量?n/k」，這樣可以保證整個(gè)網(wǎng)絡(luò)的負(fù)載均衡，接著選擇與各個(gè)控制器距離最近的交換機(jī)進(jìn)入各控制器子域，這樣可以保證每個(gè)控制器子域的傳播時(shí)延盡可能小。當(dāng)各個(gè)控制器子域管理的交換機(jī)個(gè)數(shù)相同且均等于?n/k」時(shí)，優(yōu)先按照距離最近原則分配交換機(jī)。這樣可以保證剩余的交換機(jī)和控制器間的傳播時(shí)延，犧牲了部分負(fù)載均衡性能。整個(gè)過(guò)程2種目標(biāo)互相折中，從而使得整個(gè)網(wǎng)絡(luò)的性能達(dá)到最優(yōu)。

由于整個(gè)網(wǎng)絡(luò)系統(tǒng)的負(fù)載不均衡主要集中在初始分配時(shí)期，使用MCP算法可以更好地確定控制器的位置和各控制器子域管理的交換機(jī)，使得整個(gè)網(wǎng)絡(luò)的初始分配時(shí)期獲得一個(gè)更良好的布局，可以有效降低動(dòng)態(tài)網(wǎng)絡(luò)中多控制器部署中出現(xiàn)的閾值過(guò)載現(xiàn)象。MCP算法的描述如下。

算法1控制器部署(MCP)。

輸入：網(wǎng)絡(luò)拓?fù)銰(V,E),控制器個(gè)數(shù)k；

輸出：控制器部署矩陣place_value。

Step1使用Haversine公式[13]計(jì)算出拓?fù)渖瞎?jié)點(diǎn)間距離；

Step2使用Johnson全源最短路徑算法計(jì)算出單個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)的最短距離；

Step3使用式(5)計(jì)算出單個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)的最小時(shí)延；

Step4使用粒子群算法選擇k個(gè)控制器的初始位置作為被部署的控制器集合C={c1,c2,…,ck}；

Step5找到控制器集合C={c1,c2,…,ck}與所有交換機(jī)集合S={s1,s2,…,sn}之間的最小時(shí)延；

Step6將最小時(shí)延放到控制器部署矩陣place_value(n，k)對(duì)應(yīng)位置；

Step7將最小時(shí)延對(duì)應(yīng)的交換機(jī)節(jié)點(diǎn)si放到被挑選的交換機(jī)集合select_switch{si}；

Step8將最小時(shí)延對(duì)應(yīng)的控制器節(jié)點(diǎn)cj放到被挑選的交換機(jī)集合select_controller{cj}；

Step9統(tǒng)計(jì)select_controller集合中c1,c2,…,ck的個(gè)數(shù)；

Step10重復(fù)Step 5～9直到select_controller集合中c1,c2,…,ck的個(gè)數(shù)都等于?n/k」；

Step11從交換機(jī)集合S中選擇select_switch集合中沒(méi)有出現(xiàn)的元素si，形成集合S′={si}；

Step12找到交換機(jī)S′={si}集合與控制器集合C={c1,c2,…,ck}之間的最小時(shí)延；

Step13將最小時(shí)延放到控制器部署矩陣place_value(n,k)對(duì)應(yīng)位置；

Step14將最小時(shí)延對(duì)應(yīng)的交換機(jī)節(jié)點(diǎn)放到被挑選的交換機(jī)集合select_switch{si}；

Step15將最小時(shí)延對(duì)應(yīng)的交換機(jī)節(jié)點(diǎn)si從S′集合中移除；

Step16將最小時(shí)延對(duì)應(yīng)的控制器節(jié)點(diǎn)cj從C={c1,c2,…,ck}集合中移除；

Step17統(tǒng)計(jì)select_switch集合中所有元素的個(gè)數(shù)；

Step18重復(fù)Step 12～17，直到select_switch集合中所有元素的個(gè)數(shù)等于n；

Step19返回控制器部署矩陣place_value。

2.2 改進(jìn)的粒子群算法

2.2.1 粒子群算法(PSO)

粒子群算法(particle swarm optimization，PSO)是一種源于自然的基于種群的隨機(jī)優(yōu)化算法[14]。粒子群算法在群體中尋找最優(yōu)解，并從兩種學(xué)習(xí)方式中獲益:基于個(gè)體歷史的認(rèn)知學(xué)習(xí)和基于群體歷史的社會(huì)學(xué)習(xí)[15]。初始階段，認(rèn)知學(xué)習(xí)需要確定最優(yōu)位置，在獲取局部最優(yōu)后，社會(huì)學(xué)習(xí)來(lái)決定全局最優(yōu)位置。

假設(shè)有n個(gè)群體表示潛在的解決方案，每個(gè)群體都可以用d維向量表示。在粒子群算法中， 每個(gè)粒子包含2個(gè)分量：速度和位置[16]。當(dāng)前的粒子群位置向量用Xi=[xi1,xi2,…,xid](i=1，2,…,n)表示。當(dāng)前的速度向量用Vi=[vi1,vi2,…,vid]表示。粒子群的局部最優(yōu)位置為Pi=[pi1,pi2,…,pid],Pgb為全局最優(yōu)位置向量。

在t+1時(shí)刻,更新粒子群的位置Xid和速度Vid分別表示為：

(18)

(19)

式中：ω為慣性權(quán)重；r1和r2為[0,1]的隨機(jī)數(shù)；c1和c2分別為調(diào)整個(gè)體部分的局部學(xué)習(xí)因子和調(diào)整社會(huì)部分的全局學(xué)習(xí)因子。

一個(gè)大的慣性權(quán)重ω有利于展開(kāi)全局尋優(yōu)，而一個(gè)小的慣性權(quán)重值有利于局部尋優(yōu)。因此，采用時(shí)變權(quán)重，在迭代過(guò)程中采用線性遞減慣性權(quán)值，則粒子群算法在開(kāi)始時(shí)具有良好的全局搜索性能，能夠迅速定位到接近全局最優(yōu)點(diǎn)的區(qū)域，而在后期具有良好的局部搜索性能，能夠精確地得到全局最優(yōu)解。時(shí)變權(quán)重的表達(dá)式如下：

ω=ωmax-((ωmax-ωmin)/Imax)×I。

(20)

式中：Imax為最大迭代；I為當(dāng)前迭代;通常ωmax和ωmin分別取0.9和0.1。

每個(gè)粒子的最優(yōu)位置向量為

(21)

2.2.2 改進(jìn)的粒子群算法

針對(duì)PSO算法出現(xiàn)的收斂速度慢的缺點(diǎn)，采用改進(jìn)的粒子群優(yōu)化算法(advanced particle swarm optimization，APSO)以改善種群的收斂速度。

由于PSO算法的搜索過(guò)程是一個(gè)非線性的復(fù)雜過(guò)程，采用慣性權(quán)重線性過(guò)渡的方法并不能正確地反映真實(shí)的搜索過(guò)程。因此引入文獻(xiàn)[17]中收斂因子概念，從提高種群的收斂速度方面對(duì)粒子群算法進(jìn)行改進(jìn)。其中收斂因子表達(dá)式為

(22)

對(duì)粒子群算法的速度方程稍加改進(jìn)，可得到：

(23)

根據(jù)式(23)可以更新粒子的飛行速度。文獻(xiàn)[18]證明了采用收斂因子的優(yōu)化算法相比于采用慣性權(quán)重的優(yōu)化算法有更好的收斂速度。

2.2.3 改進(jìn)的粒子群算法實(shí)現(xiàn)控制器部署(APSO_MCP)

在改進(jìn)的粒子群算法中，通過(guò)迭代，使多個(gè)粒子并行搜索最優(yōu)解，并確定最小合適度時(shí)控制器的位置。控制器位置向量是上述目標(biāo)函數(shù)的次優(yōu)解,每個(gè)個(gè)體都表示控制器部署的一種方式。在給定控制器數(shù)量為k個(gè)的情況下，單個(gè)粒子的位置向量為Pi=[pi1,pi2,…,pik]。APSO_MCP算法將所有節(jié)點(diǎn)的經(jīng)緯度latlon、需要被部署的控制器數(shù)量k、最大迭代maxIt作為輸入，最后得到控制器的最終部署位置Pgbest,整個(gè)網(wǎng)絡(luò)的最優(yōu)合適度F(Pgbest)。APSO_MCP算法的描述如下。

算法2APSO_MCP算法。

輸入：所有節(jié)點(diǎn)的經(jīng)緯度latlon，被部署的控制器數(shù)量k，最大迭代次數(shù)maxIt；

輸出：最終的控制器部署位置Pgbest，全局最優(yōu)合適度值F(Pgbest)。

(1)初始化階段:

①初始化學(xué)習(xí)因子c1,c2,收斂因子χ，粒子群nPop，將粒子群全局最優(yōu)合適度F(Pgbest)設(shè)置為∞ ；

②fori=1 tonPop

③ 隨機(jī)部署k個(gè)控制器部署位置Pposition,并將當(dāng)前位置設(shè)為當(dāng)前最優(yōu)位置Ppbest；

④ 初始化粒子的速度Pvelocity為0；

⑤ 調(diào)用控制器部署算法(MCP),調(diào)用合適度函數(shù)F；

⑥ if(F(Ppbest)

⑦ 將局部最優(yōu)位置Ppbest設(shè)為全局最優(yōu)位置Pgbest；

⑧ 將局部最優(yōu)合適度F(Ppbest)設(shè)為全局最優(yōu)合適度F(Pgbest)；

⑨endif

⑩endfor

(2)優(yōu)化階段：

粒子合適度函數(shù)F通過(guò)式(5)～(17)來(lái)計(jì)算。

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

3.1 實(shí)驗(yàn)設(shè)置

相關(guān)算法均在MATLAB中運(yùn)行，選擇的仿真環(huán)境是MATLAB 2018a,系統(tǒng)配置是Windows 10 64位系統(tǒng)，i5處理器，8 GB內(nèi)存。實(shí)驗(yàn)采用的網(wǎng)絡(luò)拓?fù)溥x自于網(wǎng)絡(luò)拓?fù)鋭?dòng)物園的Xspedius網(wǎng)絡(luò)。Xspedius網(wǎng)絡(luò)有34個(gè)節(jié)點(diǎn)和49條邊。設(shè)置控制器的最大負(fù)載為1 600 flows/s,各個(gè)交換機(jī)的流請(qǐng)求相互獨(dú)立且為100 flows/s[19]。設(shè)置vc為3×108/s,設(shè)置粒子群種群數(shù)量為50,迭代次數(shù)為300。設(shè)置控制器部署模型權(quán)重因子α為0.5,β為0.5。

為了使實(shí)驗(yàn)仿真更具有說(shuō)服力，選用隨機(jī)算法和K-means算法做對(duì)比。隨機(jī)算法是面對(duì)大量的數(shù)據(jù)，從其中隨機(jī)選取一些數(shù)據(jù)來(lái)進(jìn)行分析。K-means算法是輸入聚類個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)，輸出滿足標(biāo)準(zhǔn)方差最小的k個(gè)聚類的一種算法。將APSO_MCP算法、隨機(jī)算法[7]、K-means算法[20]和PSO_MCP算法[7]在網(wǎng)絡(luò)總時(shí)延、負(fù)載均衡比、總體性能以及運(yùn)行時(shí)間方面進(jìn)行比較。

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

實(shí)驗(yàn)1驗(yàn)證隨機(jī)算法、K-means算法、PSO_MCP算法和APSO_MCP算法在控制器傳播時(shí)延上的差異。如圖1所示，由于改進(jìn)的粒子群算法是在收斂速度的基礎(chǔ)上進(jìn)行改進(jìn)，故APSO_MCP算法和PSO_MCP算法在控制器傳播時(shí)延上的差異不大；在控制器數(shù)量為3、4、5時(shí)，APSO_MCP算法和K-means在總時(shí)延的差別較大;隨著控制器數(shù)量的增加，APSO_MCP算法在總傳播時(shí)延方面接近于K-means算法。出現(xiàn)這種情況的原因是K-means算法在部署控制器時(shí)根據(jù)最小距離原則選擇和更新控制器位置，而本文算法選擇增加部分傳播時(shí)延來(lái)平衡負(fù)載均衡指標(biāo)。

圖1 網(wǎng)絡(luò)總時(shí)延比較Figure 1 The comparison about the total latency of the network

實(shí)驗(yàn)2驗(yàn)證隨機(jī)算法、K-means算法、PSO_MCP算法和APSO_MCP算法在整個(gè)網(wǎng)絡(luò)最大負(fù)載控制器子域和最小負(fù)載控制器子域之間的差異。實(shí)驗(yàn)結(jié)果如圖2所示,APSO_MCP算法和PSO_MCP算法的實(shí)驗(yàn)結(jié)果相近，始終接近于理想?yún)?shù)1，優(yōu)于K-means算法和隨機(jī)算法。分析其原因是：網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)分布不均勻，小部分分散，大部分相對(duì)集中，而K-means是以減少傳播時(shí)延為目標(biāo)，在劃分控制器子域時(shí)未考慮控制器子域的負(fù)載，從而導(dǎo)致部分控制器子域內(nèi)的負(fù)載大幅增大。

圖2 網(wǎng)絡(luò)負(fù)載均衡比比較Figure 2 The comparison about the load balance ratio of the network

實(shí)驗(yàn)3驗(yàn)證隨機(jī)算法、K-means算法、PSO_MCP算法和APSO_MCP算法在整個(gè)網(wǎng)絡(luò)的性能上的差異。實(shí)驗(yàn)結(jié)果如圖3所示，APSO_MCP算法和PSO_MCP算法在整個(gè)網(wǎng)絡(luò)的總體性能上相近。在控制器數(shù)量為3、4、5時(shí)，隨機(jī)算法、K-means和APSO_MCP在整個(gè)網(wǎng)絡(luò)的性能的差別較大。出現(xiàn)這種現(xiàn)象的原因是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)分布不均勻，使用K-means算法劃分子域后，各個(gè)控制器子域的傳播時(shí)延和整個(gè)網(wǎng)絡(luò)的總時(shí)延、各個(gè)控制器子域之間的負(fù)載和整個(gè)網(wǎng)絡(luò)的平均負(fù)載相差較大，從而導(dǎo)致整個(gè)網(wǎng)絡(luò)的性能降低。隨著控制器數(shù)量的增加，K-means算法和隨機(jī)算法在整個(gè)網(wǎng)絡(luò)的性能方面接近于APSO_MCP。分析其原因是隨著K-means算法劃分的控制器子域數(shù)量的增多，每個(gè)子域管理的交換機(jī)數(shù)量逐漸減少，整個(gè)網(wǎng)絡(luò)被劃分成的控制器子域在傳播時(shí)延和負(fù)載均衡方面越來(lái)越合理，整個(gè)網(wǎng)絡(luò)的性能越來(lái)越穩(wěn)定。

圖3 網(wǎng)絡(luò)的總體性能比較Figure 3 The comparison about the overall performance of the network

實(shí)驗(yàn)4驗(yàn)證隨機(jī)算法、K-means算法、PSO_MCP算法和APSO_MCP算法在運(yùn)行時(shí)間上的差異。如圖4所示，隨機(jī)算法的運(yùn)行時(shí)間低于K-means算法、PSO_MCP算法和APSO_MCP算法。隨機(jī)算法沒(méi)有迭代過(guò)程，故運(yùn)行時(shí)間最短。K-means算法隨著控制器數(shù)量、迭代次數(shù)增加，運(yùn)行時(shí)間逐漸增長(zhǎng)。而APSO_MCP算法由于引入收斂因子，種群的收斂速度加快，在運(yùn)行時(shí)間方面優(yōu)于PSO_MCP算法，種群的收斂速度提升約6.3%，并且隨著控制器數(shù)量的增加，APSO_MCP算法的收斂速度快的優(yōu)勢(shì)越來(lái)越明顯。

圖4 運(yùn)行時(shí)間比較Figure 4 Comparison of the computing time

4 結(jié)論

(1)針對(duì)軟件定義網(wǎng)絡(luò)中多控制器部署問(wèn)題，以時(shí)間延遲和負(fù)載為雙重優(yōu)化目標(biāo)，建立控制器部署模型，提出MCP算法。結(jié)果表明該算法可以保證多控制器子域之間的負(fù)載均衡性能，并且有效降低整個(gè)網(wǎng)絡(luò)的時(shí)間延遲，從而確保了整個(gè)網(wǎng)絡(luò)的總體性能處于最優(yōu)的狀態(tài)。

(2)針對(duì)傳統(tǒng)粒子群算法收斂速度慢問(wèn)題，引入收斂因子概念，提出APSO算法。結(jié)合APSO算法和MCP算法來(lái)部署多控制器位置。結(jié)果表明APSO_MCP算法和PSO_MCP算法相比，有效地縮短了算法的運(yùn)行時(shí)間，驗(yàn)證了本文提出的APSO_MCP算法可以有效地提高種群的收斂速度。

(3)合理部署控制器位置的算法可以提升網(wǎng)絡(luò)性能[21]。然而本文提出的算法還有一些不足，提出的是一種靜態(tài)的部署算法，在實(shí)際網(wǎng)絡(luò)中，網(wǎng)絡(luò)狀態(tài)不斷變化，還需要考慮動(dòng)態(tài)網(wǎng)絡(luò)中的負(fù)載情況。