基于改進布谷鳥搜索算法的多控制器部署方案*

楊曉琴

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

0 引 言

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

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

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

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

1 多控制器部署問題

1.1 問題描述

由于單一控制器的處理能力有限，對于大規(guī)模廣域網(wǎng)來說，使用單一控制器通常無法及時有效地處理來自所控交換機的所有請求. 如果在大規(guī)模廣域網(wǎng)上部署SDN，那么就需要使用多個控制器. 不可避免需要解決以下問題：對于一個給定的網(wǎng)絡拓撲，需要多少控制器并且這些控制器應該部署在哪些位置，才能實現(xiàn)控制器的合理部署，從而使得整個網(wǎng)絡的目標性能達到最優(yōu). 這就是所謂的多控制器部署問題，非常值得深入研究.

1.2 模型建立

假設在網(wǎng)絡拓撲G(V,E)中，其中V代表網(wǎng)絡中的節(jié)點，E代表網(wǎng)絡拓撲中的邊. 多控制器部署問題的模型建立如下：

Minimizef(x)+g(x),

(1)

(2)

(3)

約束條件如下：

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

(4)

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

(5)

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

(6)

2 基于改進布谷鳥算法的多控制器部署方案

2.1 布谷鳥搜索算法

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

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

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

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

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

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

⊕Levy(β),

(7)

(8)

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

(9)

(10)

2.2 改進的布谷鳥搜索算法

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

(11)

(12)

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

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

2.3 基于改進布谷鳥算法的多控制器部署方案

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

Step 1： 輸入SDN控制器個數(shù)，網(wǎng)絡拓撲，布谷鳥位置及參數(shù)；

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

Step 3： 根據(jù)公式計算每個位置的適應值；

Step 4： 是否滿足終止條件，若否，轉到step2；

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

3 仿真實驗

不同的網(wǎng)絡拓撲具有不同的復雜度. 因此，這里將在兩個網(wǎng)絡拓撲上進行實驗驗證，這兩個拓撲如圖 1 所示.圖1(a)是斯坦福大學提出的第二個網(wǎng)絡OS3E，SDN部署由34個節(jié)點和41個邊組成.圖1(b)是聯(lián)通主干網(wǎng)，由35個節(jié)點和38個邊組成. 這兩種拓撲幾乎都接近于真實網(wǎng)絡. 本文的算法用MATLAB編寫，并在英特爾I5和4GB RAM的機器上運行. 算法的粒子數(shù)為20，迭代次數(shù)是50代. 每個算法的具體參數(shù)列于表 1 中.

圖 1 網(wǎng)絡拓撲圖Fig.1 Network topologies表 1 算法參數(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)絡拓撲上進行比較. 所涉及的算法為： 遺傳算法(Genetic Algorithm，GA)，粒子群算法(Particle Swarm Algorithm，PSO)，布谷鳥算法(Cuckoo Search Algorithm，CS).

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

圖 2 給出了不同控制器數(shù)之間平均潛伏期的變化. 由圖2(a)可以看出，MCS在這個網(wǎng)絡拓撲上的所有控制器號碼中具有最好的性能，略優(yōu)于CS，粒子群優(yōu)化算法和遺傳算法相對較差. 由圖2(b)可以看出，MCS性能優(yōu)于其他三種算法，PSO的性能稍差于CS，其中GA具有最差的性能. 綜述所述，MCS可以通過改進的搜索策略跳出局部最優(yōu)，在兩個網(wǎng)絡拓撲上具有更好的全局最優(yōu).

4 結束語

本文研究了軟件定義網(wǎng)絡中的多控制器部署問題. 為了實現(xiàn)平均等待時間和處理時間之間的折衷，提出了一種新的布谷鳥搜索算法. 問題函數(shù)考慮了三個部分： 控制器和控制元素、控制器和控制器之間的平均等待時延. 在兩種網(wǎng)絡拓撲進行了仿真，實驗結果表明，該算法比其他算法具有更好的性能. 在今后的工作中，我們將研究動態(tài)網(wǎng)絡拓撲中的多控制器部署問題.