楊曉琴

(太原廣播電視大學(xué)，山西 太原 030024)

0 引 言

隨著有線網(wǎng)絡(luò)規(guī)模的急劇膨脹，原有的網(wǎng)絡(luò)技術(shù)無法滿足無線終端的需求. 因此，軟件定義網(wǎng)絡(luò)[1-2](Software defined networks, SDN)提出將網(wǎng)絡(luò)的數(shù)據(jù)層與控制層解耦，采用集中控制的方式提高無線網(wǎng)絡(luò)的控制能力. 相比原有的網(wǎng)絡(luò)架構(gòu)，SDN提高了網(wǎng)絡(luò)控制的靈活性，增強(qiáng)了網(wǎng)絡(luò)新技術(shù)的支持能力.

SDN通過南向接口，實(shí)現(xiàn)控制層與數(shù)據(jù)層的交互，當(dāng)前主要的通信協(xié)議有OpenFlow, HyperFlow, Cross Flow等. SDN的網(wǎng)絡(luò)狀態(tài)主要由控制器[3]負(fù)責(zé)，隨著SDN控制元素的增長，一個(gè)SDN控制器由于自身能力的限制，難以控制所有元素. 同時(shí)，單個(gè)控制器一旦發(fā)生故障，會(huì)造成整個(gè)網(wǎng)絡(luò)的癱瘓. 主流方式是在SDN網(wǎng)絡(luò)中分布式部署多個(gè)控制器，提高大規(guī)模網(wǎng)絡(luò)的控制能力. 但在大規(guī)模網(wǎng)絡(luò)部署中，控制器的數(shù)量和位置決定了網(wǎng)絡(luò)的成本，因此如何有效合理地部署控制器是SDN中的難點(diǎn). 軟件定義網(wǎng)絡(luò)的多控制器部署問題由Heller提出[4]，目前已經(jīng)吸引了很多學(xué)者研究，模型主要考慮節(jié)點(diǎn)的平均時(shí)延和最小時(shí)延，解決方法主要有聚類方法[5]、模擬退火算法[6]、粒子群算法[7]等.

Yang等人于2009年提出了一種新的智能優(yōu)化算法——布谷鳥搜索算法(Cuckoo Search，CS)[8]. 該算法是Yang等人基于布谷鳥巢寄生行為所提出的. 與其他智能優(yōu)化算法相比，該算法易于實(shí)現(xiàn)、操作簡單，在許多最優(yōu)化問題的處理結(jié)果更有優(yōu)勢，并且已經(jīng)成功應(yīng)用于很多工程領(lǐng)域[9-10]. 趙專政等[11]使用布谷鳥算法對(duì)文本進(jìn)行分類，提高了分類效率. 胡宗慶[12]利用布谷鳥算法擬合模型參數(shù)，使指數(shù)曲線模型參數(shù)的求解更加方便，模型的精度更高. 高述濤[13]提出一種CS算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)參數(shù)的短時(shí)交通流量預(yù)測模型. 姚遠(yuǎn)遠(yuǎn)等[14]嘗試采用CS算法來求解JSP問題也達(dá)到了很好的效果.

因此，為了提高CS算法的搜索性能，避免算法陷入局部最優(yōu)，本文提出了一種改進(jìn)的CS算法，將改進(jìn)的CS算法應(yīng)用到SDN控制器部署問題，并通過仿真實(shí)驗(yàn)驗(yàn)證本文所提出方法的有效性.

1 多控制器部署問題

1.1 問題描述

由于單一控制器的處理能力有限，對(duì)于大規(guī)模廣域網(wǎng)來說，使用單一控制器通常無法及時(shí)有效地處理來自所控交換機(jī)的所有請(qǐng)求. 如果在大規(guī)模廣域網(wǎng)上部署SDN，那么就需要使用多個(gè)控制器. 不可避免需要解決以下問題：對(duì)于一個(gè)給定的網(wǎng)絡(luò)拓?fù)洌枰嗌倏刂破鞑⑶疫@些控制器應(yīng)該部署在哪些位置，才能實(shí)現(xiàn)控制器的合理部署，從而使得整個(gè)網(wǎng)絡(luò)的目標(biāo)性能達(dá)到最優(yōu). 這就是所謂的多控制器部署問題，非常值得深入研究.

1.2 模型建立

假設(shè)在網(wǎng)絡(luò)拓?fù)銰(V,E)中，其中V代表網(wǎng)絡(luò)中的節(jié)點(diǎn)，E代表網(wǎng)絡(luò)拓?fù)渲械倪? 多控制器部署問題的模型建立如下：

Minimizef(x)+g(x),

(1)

(2)

(3)

約束條件如下：

1) 假設(shè)控制器的個(gè)數(shù)總數(shù)是N.

(4)

2) 每個(gè)控制元素只能被一個(gè)控制器控制.

(5)

3) 每個(gè)控制器最多管理L個(gè)元素.

(6)

2 基于改進(jìn)布谷鳥算法的多控制器部署方案

2.1 布谷鳥搜索算法

布谷鳥算法[15-17]是一種新型的智能優(yōu)化算法，這種算法源于模擬布谷鳥巢寄生的行為和萊維飛行習(xí)性兩個(gè)方面. 該算法相比于其他算法的特別之處是搜索路徑不同，它的搜索方式是Levy飛行，Levy飛行由兩部分組成：一是方向，二是步長，方向按照均勻分布進(jìn)行選擇，而步長選擇是服從Levy分布的游走步長. 在CS算法中，步長的選擇是利用具有Levy分布特征的Mantegna法則來完成的. Levy飛行可以在不確定的區(qū)域中最大限度地進(jìn)行有效搜索. 該算法比較簡單，參數(shù)少，易于實(shí)現(xiàn)，具有很好的全局搜索能力，因此受到國內(nèi)外許多學(xué)者的關(guān)注.

布谷鳥算法基于以下三個(gè)理想化的條件：

1) 每只布谷鳥隨機(jī)選擇一個(gè)鳥窩，并放置一個(gè)蛋；

2) 表現(xiàn)好的鳥窩將會(huì)被保留至下一代，這樣可以保證算法能夠獲得更優(yōu)解；

3) 可以選擇的鳥窩數(shù)量n是固定的，另外鳥窩中的鳥蛋被發(fā)現(xiàn)的概率是Pa，且Pα∈[0,1].

基于以上三個(gè)理想化的條件，布谷鳥搜索算法主要包括局部搜索和全局搜索兩種位置更新公式. 其中，全局搜索位置更新公式為

⊕Levy(β),

(7)

(8)

式中：μ和ν服從標(biāo)準(zhǔn)正態(tài)分布，β=1.5.

(9)

(10)

2.2 改進(jìn)的布谷鳥搜索算法

為了提高算法的局部搜索能力，本文在進(jìn)行局部搜索時(shí)讓個(gè)體朝著全局最優(yōu)的方向搜索，保證算法更新方向的有效性，具體公式修改如式(11)所示

(11)

(12)

此外，如果讓全部個(gè)體采用公式(8)進(jìn)行局部搜索，一直朝著較優(yōu)個(gè)體的方向搜索，從而導(dǎo)致算法陷入局部最優(yōu)，影響算法性能. 為了規(guī)避較優(yōu)個(gè)體陷入局部最優(yōu)，進(jìn)一步提出改進(jìn)布谷鳥算法(Motified cuckoo search algorithm, MCS).

首先對(duì)所有個(gè)體按照優(yōu)劣依次排序，然后將種群劃分為兩部分. 較優(yōu)種群按照公式(10)進(jìn)行局部搜索，由于這些個(gè)體當(dāng)前位置較優(yōu)，在進(jìn)行局部搜索時(shí)按照式(10)搜索范圍增大. 較差種群按照公式(11)進(jìn)行局部搜索，由于這些個(gè)體當(dāng)前位置較差，在進(jìn)行局部搜索時(shí)依賴歷史最優(yōu)位置的信息，提高個(gè)體搜索精度. 通過這樣改進(jìn)，布谷鳥算法種群整體的局部搜索能力增強(qiáng)，并且具有跳出局部最優(yōu)的能力. 經(jīng)實(shí)驗(yàn)驗(yàn)證，較優(yōu)種群與較差種群的數(shù)量比為1∶9時(shí)，性能最佳.

2.3 基于改進(jìn)布谷鳥算法的多控制器部署方案

本文利用改進(jìn)的布谷鳥算法對(duì)大規(guī)模廣域網(wǎng)多控制器部署問題進(jìn)行研究，以期達(dá)到最小的控制開銷，從而實(shí)現(xiàn)多控制器的合理有效部署. 本文主要研究的對(duì)象是由支持Openfllow的交換機(jī)和多個(gè)有容量限制的控制器所組成的大規(guī)模廣域網(wǎng)，并且每個(gè)控制器都維持一個(gè)全局網(wǎng)絡(luò)視圖. 根據(jù)Openfllow協(xié)議，在任何時(shí)候網(wǎng)絡(luò)中一個(gè)交換機(jī)都至少與一個(gè)控制器相連接. 算法具體步驟如下：

Step 1： 輸入SDN控制器個(gè)數(shù)，網(wǎng)絡(luò)拓?fù)洌脊萨B位置及參數(shù)；

Step 2： 按照公式更新每個(gè)布谷鳥位置；

Step 3： 根據(jù)公式計(jì)算每個(gè)位置的適應(yīng)值；

Step 4： 是否滿足終止條件，若否，轉(zhuǎn)到step2；

Step 5： 輸出控制器位置和平均時(shí)延.

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

不同的網(wǎng)絡(luò)拓?fù)渚哂胁煌膹?fù)雜度. 因此，這里將在兩個(gè)網(wǎng)絡(luò)拓?fù)渖线M(jìn)行實(shí)驗(yàn)驗(yàn)證，這兩個(gè)拓?fù)淙鐖D 1 所示.圖1(a)是斯坦福大學(xué)提出的第二個(gè)網(wǎng)絡(luò)OS3E，SDN部署由34個(gè)節(jié)點(diǎn)和41個(gè)邊組成.圖1(b)是聯(lián)通主干網(wǎng)，由35個(gè)節(jié)點(diǎn)和38個(gè)邊組成. 這兩種拓?fù)鋷缀醵冀咏谡鎸?shí)網(wǎng)絡(luò). 本文的算法用MATLAB編寫，并在英特爾I5和4GB RAM的機(jī)器上運(yùn)行. 算法的粒子數(shù)為20，迭代次數(shù)是50代. 每個(gè)算法的具體參數(shù)列于表 1 中.

圖 1 網(wǎng)絡(luò)拓?fù)鋱DFig.1 Network topologies表 1 算法參數(shù)設(shè)置Tab.1 Parameters of algorithms

算法參數(shù)GAPc=0.8, Pm=0.1PSOc1=2.0, c2=2.0, w(0.9→0.4)CSPa=0.25, a=1

本文將MCS與其他兩種啟發(fā)式算法在網(wǎng)絡(luò)拓?fù)渖线M(jìn)行比較. 所涉及的算法為： 遺傳算法(Genetic Algorithm，GA)，粒子群算法(Particle Swarm Algorithm，PSO)，布谷鳥算法(Cuckoo Search Algorithm，CS).

為了驗(yàn)證該算法的性能，實(shí)驗(yàn)采用不同的控制器數(shù)目. 隨著控制器的增加，多控制器部署問題的復(fù)雜性將大大增加.

圖 2 給出了不同控制器數(shù)之間平均潛伏期的變化. 由圖2(a)可以看出，MCS在這個(gè)網(wǎng)絡(luò)拓?fù)渖系乃锌刂破魈?hào)碼中具有最好的性能，略優(yōu)于CS，粒子群優(yōu)化算法和遺傳算法相對(duì)較差. 由圖2(b)可以看出，MCS性能優(yōu)于其他三種算法，PSO的性能稍差于CS，其中GA具有最差的性能. 綜述所述，MCS可以通過改進(jìn)的搜索策略跳出局部最優(yōu)，在兩個(gè)網(wǎng)絡(luò)拓?fù)渖暇哂懈玫娜肿顑?yōu).

4 結(jié)束語

本文研究了軟件定義網(wǎng)絡(luò)中的多控制器部署問題. 為了實(shí)現(xiàn)平均等待時(shí)間和處理時(shí)間之間的折衷，提出了一種新的布谷鳥搜索算法. 問題函數(shù)考慮了三個(gè)部分： 控制器和控制元素、控制器和控制器之間的平均等待時(shí)延. 在兩種網(wǎng)絡(luò)拓?fù)溥M(jìn)行了仿真，實(shí)驗(yàn)結(jié)果表明，該算法比其他算法具有更好的性能. 在今后的工作中，我們將研究動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)渲械亩嗫刂破鞑渴饐栴}.