基于混合粒子群的虛擬網(wǎng)絡(luò)映射算法

賈曉光

摘要：虛擬網(wǎng)絡(luò)映射的目標(biāo)是為用戶的虛擬網(wǎng)絡(luò)合理分配底層物理資源，是虛擬資源分配領(lǐng)域的熱點(diǎn)問題。針對粒子群算法在求解映射可行解時可能產(chǎn)生的早熟收斂、局部尋優(yōu)能力差等問題，該文將粒子群優(yōu)化算法與禁忌搜索算法和模擬退火算法相結(jié)合，利用禁忌列表和退火過程來解決早熟收斂問題，進(jìn)而提出混合粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法。仿真實(shí)驗(yàn)結(jié)果表明，我們所提出的算法在虛擬網(wǎng)絡(luò)接受率和收益/成本比方面相較已有算法有一定提升。

關(guān)鍵詞：虛擬化；虛擬網(wǎng)絡(luò)映射；粒子群算法；退火算法

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）07-0210-04

網(wǎng)絡(luò)虛擬化[1]技術(shù)允許在共享的底層物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施之上共存多重異構(gòu)的虛擬網(wǎng)絡(luò)。為用戶帶有節(jié)點(diǎn)（CPU、內(nèi)存、存儲）和鏈路資源（帶寬）約束條件的虛擬網(wǎng)絡(luò)請求分配底層物理網(wǎng)絡(luò)資源的問題稱為虛擬網(wǎng)絡(luò)映射（Virtual Network Embedding， VNE）問題[2]。虛擬網(wǎng)絡(luò)映射問題已經(jīng)被證明是NP 難問題，即使在所有的虛擬節(jié)點(diǎn)已被映射后，映射帶有帶寬資源約束的虛擬鏈路仍然是NP 難的[3]。因此，目前已有的研究成果大都采用智能算法解決虛擬網(wǎng)絡(luò)映射問題[4]。

離散粒子群（Discrete PSO， DPSO）算法是基于群體智能的啟發(fā)式全局優(yōu)化技術(shù)，群體中的每一個粒子代表待解決問題的一個候選解，算法通過粒子間信息素的交互作用發(fā)現(xiàn)復(fù)雜搜索空間中的最優(yōu)區(qū)域，其具有收斂速度快、算法簡單、搜索效率高等特點(diǎn)[5]。但在實(shí)際應(yīng)用中，采用單一的智能算法解決虛擬網(wǎng)絡(luò)映射問題是不夠的，單純基于粒子群算法的映射方案在運(yùn)行一段時間后會產(chǎn)生收斂于局部優(yōu)化解的問題。因此，本文基于TS算法和SA算法提出了混合粒子群優(yōu)化算法，HPTS-VNE-PSO（Hybrid of Particle swarm optimization，Tabu search and Simulated annealing about Virtual Network Embedding Based on Particle Swarm），算法利用了禁忌搜索算法中的禁忌列表以及模擬退火算法中的退火過程來解決尋優(yōu)過程中出現(xiàn)的早熟收斂問題。

1 Related works

在不對虛擬網(wǎng)絡(luò)映射問題約束進(jìn)行任何限制的情況下，文獻(xiàn)[5]提出了一種允許底物網(wǎng)絡(luò)支持路徑分離的方法從而使映射算法更有效地利用資源，從而簡化了虛擬鏈路的映射問題。文獻(xiàn)[6] 將底層物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)的拓?fù)涠伎醋饕粋€有向圖，提出了基于子圖同構(gòu)的映射算法，該算法在同時映射節(jié)點(diǎn)和鏈路。該算法可以被看作是經(jīng)典的VF圖形匹配算法[7]的擴(kuò)展版本，但該算法沒有考慮到虛擬節(jié)點(diǎn)的位置約束。文獻(xiàn)[8] 項(xiàng)等應(yīng)用粒子群優(yōu)化求解虛擬網(wǎng)絡(luò)映射問題，利用粒子群算法簡單，代碼執(zhí)行效率高的特點(diǎn)，將虛擬節(jié)點(diǎn)映射結(jié)果用粒子的位置表示，并利用底物網(wǎng)絡(luò)的資源消耗作為適應(yīng)度函數(shù)來評估當(dāng)前解的優(yōu)劣。在迭代的過程中，每個粒子根據(jù)個體和全局最優(yōu)信息來調(diào)整它們的飛行速度，以獲得最優(yōu)的虛擬網(wǎng)絡(luò)映射。

苑迎等人[9]提出的基于DPSO負(fù)載可控的虛擬網(wǎng)絡(luò)映射算法，同樣是采用粒子群優(yōu)化算法，針對多租賃模式下的虛擬網(wǎng)絡(luò)映射問題，提出了物理節(jié)點(diǎn)可復(fù)用、負(fù)載可控制的MLB-VNE-SDPSO算法。該算法兼顧了CPU主機(jī)資源利用率，節(jié)約了物理鏈路的帶寬資源，縮短了虛擬鏈路的映射時間。缺點(diǎn)是未考慮粒子群算法的早熟問題以及鏈路中中間節(jié)點(diǎn)的資源消耗。

PSO算法是獨(dú)立于問題的，也就是說不需要知道過多與問題相關(guān)的特定知識，只需要知道每個解的適應(yīng)度值就可以方便地進(jìn)行尋優(yōu)操作，這種優(yōu)勢使得PSO算法比許多其他搜索算法更健壯。然而，由于粒子群算法是一種隨機(jī)搜索算法，它被證明是不確定的全局搜索。如果問題的求解是十分困難而復(fù)雜的，PSO算法可能找不到所需的最佳解決方案。禁忌搜索（Tabu Search，TS）和模擬退火（Simulated Annealing，SA）算法能夠從某種程度上避免陷入局部最優(yōu)，搜索過程可以由冷卻策略得到控制。通過設(shè)計(jì)TS算法和SA算法的鄰域結(jié)構(gòu)和冷卻策略從而控制搜索過程，可以有效地避免個體陷入局部最優(yōu)。因此，我們提出HPTS-VNE-PSO算法，從橫向和縱向水平上擴(kuò)展搜索范圍。

2 基于混合粒子群的虛擬網(wǎng)絡(luò)映射算法設(shè)計(jì)

TS[10]算法作為一種元啟發(fā)式算法，某種程度上是模擬人類行為的智能搜索方式。不同于遺傳算法和模擬退火算法等特點(diǎn)的智能隨機(jī)算法，TS算法通過采用禁忌策略克服搜索過程中過早地陷入早熟收斂從而達(dá)到全局最優(yōu)，本文利用了TS算法的這一特點(diǎn)，借鑒該算法的禁忌列表來避免重復(fù)搜索，提高收斂效率。SA[11]引入了物理系統(tǒng)中退火降溫過程的自然機(jī)理， 在迭代過程中不僅接受使適應(yīng)度值變“好”的試探點(diǎn)，還以一定的幾率接受使適應(yīng)度值變“壞”的試探點(diǎn)，隨著溫度的下降接受的概率也將逐漸減小。這種搜索策略能夠有效避免搜索過程因陷入局部最優(yōu)解而無法掙脫的現(xiàn)象發(fā)生，從而提高求得全局最優(yōu)解的可靠性。

我們將PSO算法，TS算法和SA算法結(jié)合，設(shè)計(jì)了HPTS-VNE-PSO算法。如圖1所示，PSO算法通過結(jié)合本地搜索（自我經(jīng)驗(yàn)）與全局搜索（鄰居經(jīng)驗(yàn)）達(dá)到較高的搜索效率。TS算法則通過記憶功能來避免被困在局部最優(yōu)（水平方向上的計(jì)算）。SA算法的搜索過程由退火過程（也稱為垂直方向的計(jì)算）進(jìn)行控制，以一定的概率避免陷入局部最優(yōu)。

2.1 問題定義

HPTS-VNE-PSO算法的設(shè)計(jì)上存在幾個關(guān)鍵技術(shù)：1）搜索空間 、2）PSO算法框架、3）鄰居搜索、4）禁忌列表、5）適應(yīng)度函數(shù)、6）冷卻控制，下面依次進(jìn)行闡述：

1）搜索空間

假設(shè)虛擬節(jié)點(diǎn)數(shù)目為N，那么粒子群搜索范圍為N維空間。設(shè)定初始粒子群數(shù)目為m。由于虛擬網(wǎng)絡(luò)映射問題屬于離散問題，我們采用離散粒子群優(yōu)化算法，并重新定義第[i]個粒子的位置、速度、個體最優(yōu)位置以及全局最優(yōu)位置如下：

在一個粒子群中，“認(rèn)知”權(quán)重[c1]和“社會”權(quán)重[c2]控制著粒子移動的范圍，通常我們將其設(shè)置為2.0。本文采用的粒子速度的更新公式參照4.2式和4.3式。

3）鄰居搜索

為不斷拓展搜索空間禁忌搜索需要不斷進(jìn)行鄰居移動，鄰居移動即在當(dāng)前解的基礎(chǔ)上，按照某種特定的移動策略產(chǎn)生出一定數(shù)目的新解，稱為鄰居解。鄰居搜索對于局部搜索是十分有效的，一般來說沒必要的和不可行的移動必須終止。目前最著名的鄰居結(jié)構(gòu)是基于“塊”的。我們的算法鄰居結(jié)構(gòu)設(shè)為數(shù)組形式。

4）禁忌列表

禁忌列表中存放的是禁忌對象，被放入禁忌表中的禁忌對象在解禁之前不能被再次搜索。本文使用的禁忌列表是數(shù)組，禁忌對象為已經(jīng)搜索過的粒子。

禁忌長度指的是禁忌對象在禁忌列表中的生存時間。當(dāng)一個禁忌對象加入到禁忌列表時，設(shè)置其任期為禁忌長度值，HTPS-VNE-PSO算法設(shè)置種群大小為禁忌長度。搜索過程中禁忌長度是動態(tài)變化的，本文設(shè)置為每迭代一次則禁忌表中的禁忌對象的任期自動減1，當(dāng)某一禁忌對象任期為0時，則將其從禁忌列表中刪除，任期大于0的禁忌對象被設(shè)為禁忌狀態(tài)，搜索過程不可以被選為新解。

5）適應(yīng)度函數(shù)

評價函數(shù)可以計(jì)算解對應(yīng)的評價函數(shù)值，通過評價函數(shù)來評價禁忌搜索空間中的解。評價函數(shù)值的大小代表了解的優(yōu)劣程度，它是評價粒子群的性能指標(biāo)，通過比較評價函數(shù)值的大小確定當(dāng)前解是否更優(yōu)。解的評價函數(shù)，又稱為適應(yīng)度函數(shù)適應(yīng)度函數(shù)，我們使用帶寬開銷最小化作為適應(yīng)度函數(shù)：[Minluv→lijfuvijb（luv）]，其值越小越好，這也是VNE問題的典型目標(biāo)。

6）冷卻控制

SA算法模塊可以通過冷卻策略進(jìn)行控制。冷卻策略的初始溫度[T0=Δfmax]，其中[Δfmax]表示任意兩個鄰居解適應(yīng)度值的最大差值。溫度的變化公式為：[Tk=B×Tk-1（k=1，2，3...）]，下降因子B小于1。

2.2 HPTS-VNE-PSO 算法實(shí)現(xiàn)

如圖2所示，HTPS-VNE-PSO的主要思想是利用PSO算法逐輪生成粒子位置，即可能的映射方案；然后采用弗洛伊德最短路徑算法為虛擬鏈路尋找最短路徑，并為其分配鏈路；將初始粒子信息加入到禁忌列表中；對每個粒子計(jì)算適應(yīng)度值、gbest、pbest得到最優(yōu)解；根據(jù)特定規(guī)則為最優(yōu)解創(chuàng)造鄰居解，然后從不在禁忌列表中的鄰居解集中找到最好鄰居作為當(dāng)前解進(jìn)行存儲，更新禁忌列表。在模擬退火部分。我們首先選定初始溫度，當(dāng)溫度不足夠低時，用當(dāng)前解繼續(xù)生成鄰居解，并計(jì)算其適應(yīng)度值，如果達(dá)到終止條件則更新gbest，將其加入到禁忌列表中，并降低溫度。當(dāng)溫度降到一定程度則返回最優(yōu)解，否則繼續(xù)降溫過程。

PSO算法操作過程為HPTS-VNE-PSO算法提供了初始粒子，并構(gòu)成了整個算法的外圍框架，其偽代碼如下所示：

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

本文實(shí)驗(yàn)在CloudSim [12]中對比了VNE-R-PSO [9]和D-ViNE-SP[6]兩種算法，這兩種算法都是典型的基于粒子群的虛擬網(wǎng)絡(luò)方法。實(shí)驗(yàn)首先·對CloudSim進(jìn)行了二次開發(fā)，將其控制粒度從虛擬機(jī)修改為虛擬網(wǎng)絡(luò)，并設(shè)計(jì)了一個拓?fù)渖善鱽砩商摂M和物理拓?fù)?。生成器的參?shù)包含節(jié)點(diǎn)的數(shù)量、連接概率和虛擬網(wǎng)絡(luò)請求的任務(wù)持續(xù)時間。底物網(wǎng)絡(luò)被設(shè)置為擁有100個節(jié)點(diǎn)和500條鏈路。物理節(jié)點(diǎn)CPU容量和物理鏈路帶寬在[50， 100]區(qū)間隨機(jī)均勻分布。實(shí)驗(yàn)中，虛擬網(wǎng)絡(luò)請求的到達(dá)服從參數(shù)為5的泊松分布，最小時間間隔等于ColudSim中的100時間單位。每個虛擬網(wǎng)絡(luò)的生命周期服從參數(shù)為400時間單位的指數(shù)分布。對于每個虛擬網(wǎng)絡(luò)請求，其虛擬節(jié)點(diǎn)的數(shù)量在[2， 20]區(qū)間隨進(jìn)均勻分布，虛擬節(jié)點(diǎn)之間的鏈路生成概率是50%，虛擬網(wǎng)絡(luò)節(jié)點(diǎn)CPU請求和虛擬帶寬請求服從[3， 50]的隨機(jī)均勻分布。每次實(shí)驗(yàn)運(yùn)行50000時間單位，平均2500個虛擬網(wǎng)絡(luò)請求被映射。三種算法粒子群迭代的最大次數(shù)都被設(shè)置為20次。實(shí)驗(yàn)比較了三種算法的虛擬網(wǎng)絡(luò)接受率和收益成本比，具體結(jié)果如下。

圖3所示是算法隨著時鐘節(jié)拍的增加虛擬網(wǎng)絡(luò)請求接受率的變化曲線，負(fù)載因子[γ]取值均為1。從圖中可以看出，隨著時間推移HPTS-VNE-PSO算法虛擬網(wǎng)絡(luò)請求接受率逐漸下降并趨于平緩，比其他算法效果要好。

圖4所示是HPTS-VNE-PSO算法與表中另外2個算法在長期平均收益成本比方面的比較，負(fù)載因子[γ]取值均為1。從圖中可以看出，幾個算法的平均長期收益成本比波動都不大，大約在0.05范圍以內(nèi)，但隨著時間推移HPTS-VNE-PSO，比另外2個算法的表現(xiàn)要好。

4 結(jié)論

本文通過引入禁忌搜索算法的禁忌列表和模擬退火算法的退火技術(shù)，提出了一種混合粒子群優(yōu)化算法。禁忌搜索算法的禁忌列表可以避免重復(fù)搜索，擴(kuò)大橫向搜索范圍，而模擬退火算法則在縱向水平上避免陷入局部尋優(yōu)的困境，兩者的結(jié)合能夠在一定程度上解決單純基于粒子群算法解決虛擬網(wǎng)絡(luò)映射問題時容易陷入早熟的問題，從而獲得了較好的虛擬網(wǎng)絡(luò)接受率和收益成本比。

參考文獻(xiàn)：

[1] Chowdhury NMMK， Boutaba R. Network virtualization： State of the art and research challenges[J].IEEE Communications Magazine， 2009， 47（7）： 20?26.

[2] Cheng Xiang， Zhang Zhong-bao， Su Sen， Yang Fang-chun. Survey of virtual network embedding proble[J]m. Journal on Communications， 2011， 32（10）： 143-141 （in Chinese）

[3] Zhi-ping C， Qiang L， Pin L， Nong X， Zhi-ying W. Virtual Network Mapping Model and Optimization Algorithms[J]. Journal of Software， 2012， 23（4）： 864?877.

[4] Beck MT， Fischer A， Botero JF， Linnhoff-Popien C， Meer HD. Distributed and scalable embedding of virtual networks[J]. Journal of Network and Computer Applications 2015， 56：124-136.

[5] Ma Xuan， Liu Qing. Particle Swarm Optimization for Multiple Multicast Routing Problem[J]. Journal of Computer Research and Development， 2013， 50（2）： 260-268.

[6] Lischka J， Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection[C]//Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures， ACM， 2009： 81-88.

[7] Cordella L P， Foggia P， Sansone C， et al. An improved algorithm for matching large graphs[C]//3rd IAPR-TC15 workshop on graph-based representations in pattern recognition， 2001： 149-159.

[8] Xiang Cheng， Baozhong Zhang. Virtual Network Embedding Based on Particle Swarm Optimization[J]. Acta Electronica Sinica， 2011，39（10）：2240-2244.

[9] 苑迎， 王翠榮， 王聰， 等.基于DPSO負(fù)載可控的虛擬網(wǎng)絡(luò)映射算法[J]. 東北大學(xué)學(xué)報(bào)， 2014， 35（1）： 10-14.

[10] Glover F. Future paths for Integer Programming and Links to Artificial Intelligence[J]. Comput Oper Res， 1986，13：533-549.

[11] Kirkpatrick S， Jr Gelatt C D，Vecchi MP.Optimization by simulated annealing[J]. Sciennce， 1983（11）： 650-671.

[12] Calheiros R N， Ranjan R， Beloglazov A，et al. Buyya， Cloudsim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software Practice and Experience，2011， 41（1）：23-50.