優(yōu)化人工蜂群算法的跨域虛擬網(wǎng)絡(luò)映射算法

顧艷林（內(nèi)蒙古財經(jīng)大學(xué)計算機(jī)信息管理學(xué)院，內(nèi)蒙古呼和浩特010020）

優(yōu)化人工蜂群算法的跨域虛擬網(wǎng)絡(luò)映射算法

顧艷林
（內(nèi)蒙古財經(jīng)大學(xué)計算機(jī)信息管理學(xué)院，內(nèi)蒙古呼和浩特010020）

針對跨域虛擬網(wǎng)絡(luò)映射問題，提出一種基于優(yōu)化人工蜂群算法的跨域虛擬網(wǎng)絡(luò)映射算法.該算法采用集中管理、分布控制的方式實現(xiàn)物理網(wǎng)絡(luò)資源的有效利用，并就人工蜂群算法收斂速度慢、局部最優(yōu)缺點(diǎn)，提出尋優(yōu)能力更強(qiáng)的優(yōu)化人工蜂群算法進(jìn)行域間映射請求的劃分.實驗結(jié)果表明：與LID－MVNE算法、Policy－MVNE算法、GA－MVNE算法相比，所提算法能夠以更小的額外開銷、更少的劃分時間實現(xiàn)更高的接受率.

人工蜂群；虛擬網(wǎng)絡(luò)；自治域；服務(wù)代理

虛擬網(wǎng)絡(luò)作為一種新穎的互聯(lián)網(wǎng)體系架構(gòu)，能夠有效地解決互聯(lián)網(wǎng)體系架構(gòu)的“僵化”問題［1］.在網(wǎng)絡(luò)虛擬環(huán)境下，基礎(chǔ)設(shè)施提供商（InP）負(fù)責(zé)物理網(wǎng)絡(luò)的管理和運(yùn)營，并且能向服務(wù)提供商（SP）提供網(wǎng)絡(luò)資源租賃服務(wù)，而被租賃的網(wǎng)絡(luò)資源被映射為虛擬網(wǎng)絡(luò)，從而實現(xiàn)個性化的可訂制的端到端服務(wù)［2］.其中，具有鏈路和節(jié)點(diǎn)資源約束的虛擬網(wǎng)絡(luò)到物理網(wǎng)絡(luò)的映射問題，被稱為虛擬網(wǎng)絡(luò)映射（VNE）問題［3］.隨著在線游戲、云計算、IPTV等新興網(wǎng)絡(luò)業(yè)務(wù)的迅猛發(fā)展，單個自治域難以很好地支撐這些新興的網(wǎng)絡(luò)業(yè)務(wù).跨域虛擬網(wǎng)絡(luò)映射（MVNE）算法就是用于解決多自治域下虛擬網(wǎng)絡(luò)到物理網(wǎng)絡(luò)的映射問題［4］.Dietrich等［5］提出了LID－MVNE算法，采用整數(shù)規(guī)劃把虛擬網(wǎng)絡(luò)拓?fù)浞纸獬捎刹煌灾斡蜇?fù)責(zé)的多個虛擬子網(wǎng)路，再通過域內(nèi)映射完成子網(wǎng)絡(luò)的映射.Chowdhury等［6］提出了Policy－MVNE算法，把VNE請求交由位置最近的自治域進(jìn)行處理，如果該自治域無法完成VNE，則該VNE請求轉(zhuǎn)交由相鄰的自治域處理.上述兩種算法存在復(fù)雜度高、平均劃分時間長的缺點(diǎn).Xiao等［7］提出了GA－MVNE算法，通過遺傳算法完成虛擬子網(wǎng)絡(luò)的劃分，但是GA－MVNE算法并沒有對域內(nèi)鏈路開銷進(jìn)行考慮.因此，本文提出了一種基于優(yōu)化人工蜂群算法的跨域虛擬網(wǎng)絡(luò)映射（OABC－MVNE）算法.

1 MVNE模型

物理網(wǎng)絡(luò)由多個自治域構(gòu)成，每個自治域中都有一個區(qū)域服務(wù)代理（regional service agent，RSA）負(fù)責(zé)域內(nèi)狀態(tài)采集以及域內(nèi)VNE.同時，物理網(wǎng)絡(luò)中有一個全局服務(wù)代理（global service agent，GSA）負(fù)責(zé)域間拓?fù)錉顟B(tài)的采集、域間VNE的劃分以及與RSA的通信，以掌握自治域的資源使用情況.為了實現(xiàn)集中管理和分布控制，MVNE的工作流程如下.1）RSA負(fù)責(zé)接收域內(nèi)用戶的VNE請求，如果能完成VNE，那么，其通過單域VNE算法響應(yīng)該請求；否則，在GSA輪詢到該RSA時，把該請求轉(zhuǎn)交由GSA處理.2）在處理RSA提交的VNE請求的過程中，GSA把VNE請求放入FIFO隊列中，并按照先到先服務(wù)的原則串行處理每個VNE請求，并按照制定的域間劃分算法把域間請求劃分為若干個域內(nèi)請求，交由相應(yīng)的RSA處理.

2 優(yōu)化目標(biāo)

由于盡量減少虛擬鏈路所消耗的鏈路資源就能以最小的代價完成MVNE.因此，MVNE算法的優(yōu)化目標(biāo)函數(shù)為

式（1）中：li，j為虛擬鏈路；rcd為li，j對應(yīng)的物理路徑；ls為li，j中的物理鏈路；m為虛擬網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)；n為物理網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)；D（ls）為ls的時延；λ為單位時延開銷；xi為li，j的類型，其表達(dá)式為

同時，表達(dá)式還應(yīng)滿足2個約束條件，即

式（3）說明物理鏈路ls的剩余帶寬Re s（B（ls））能夠滿足虛擬鏈路的li，j帶寬需求.而式（4）說明路徑rcd的時延不大于虛擬鏈路li，j的時延約束.

3 算法實現(xiàn)

虛擬網(wǎng)絡(luò)劃分問題已被證明是NP－h(huán)ard問題，為了得到該問題的近似最優(yōu)解，OABC－MVNE算法使用優(yōu)化人工蜂群（optimized artificial bee colony，OABC）算法完成域間請求到域內(nèi)請求的劃分.

蜜源的位置通常用Xi＝（xi，1，…，xi，d）表示，而在尋找蜜源的過程中，表示為

式（5），（6）中：SN為蜂群數(shù)；k和j為隨機(jī)數(shù)，且k∈｛1，2，…，SN｝，j＝｛1，2，…，d｝，k≠i；ri，j為［－1，1］上的隨機(jī)數(shù)；vi，j為新蜜源的位置；pi為雇傭蜂被選中的概率.

定義1 蜜源位置.域間請求到域內(nèi)請求的劃分的解對應(yīng)著蜜源位置，而一個蜜源只對應(yīng)著一個雇傭蜂，即Xi＝（xi，1，xi，2，…，xi，m）T.式中：m為VNE請求中的虛擬節(jié)點(diǎn)數(shù)；行向量xi，j為邊界節(jié)點(diǎn)與虛擬節(jié)點(diǎn)的映射關(guān)系；i為第i個蜜源.

定義2 蜜源的適應(yīng)度.由于蜜源的好壞直接由蜜源的適應(yīng)度fit（Xi）決定，因此，以MVNE算法的優(yōu)化目標(biāo)函數(shù)為參考設(shè)定fit（Xi），其值為

定義3 位置調(diào)整準(zhǔn)則.基本ABC算法只進(jìn)行單維變量搜索，從而存在算法收斂速度慢的缺點(diǎn).針對這個問題，OABC算法引入蜜源歷史最優(yōu)位置加速搜索速度.因此，式（5）改寫為

式（8）中：φi，j為［－1，1］上的隨機(jī)數(shù)；xbesti，j為蜜源歷史最優(yōu)位置.

定義4 蜜源選擇準(zhǔn)則.基本ABC算法會導(dǎo)致蜂群快速向好蜜源靠近，導(dǎo)致局部最優(yōu).為了增加種群的多樣性，式（6）改寫為

定義5 隨機(jī)搜索準(zhǔn)則.如果觀察蜂在蜜源鄰域搜索l次后，蜜源適應(yīng)度值的變化值小于閥值ε，那么，通過雜交操作生成新的蜜源.雜交公式為

式（10）中：α為［－1，1］上的隨機(jī)數(shù)；j∈｛1，2，…，SN｝，j≠i；Xbestj為Xj的當(dāng)前最佳位置.

OABC算法的工作流程：1）設(shè)置蜂群規(guī)模SN，最大迭代次數(shù)M，最大搜索次數(shù)l，閥值ε，隨機(jī)生成SN個初始蜜源；2）計算所有蜜源的適應(yīng)度，并按照從大到小的順序排序，選擇前［SN／2］個作為蜜源，蜜源與雇傭蜂一一對應(yīng)；3）雇傭蜂根據(jù)位置調(diào)整準(zhǔn)則來尋找新的蜜源，并比較新舊蜜源的適應(yīng)度值，如果fit（XNew）＜fit（Xi），保留舊蜜源，否則，留下新蜜源；4）根據(jù)雇傭蜂釋放的信息，觀察蜂以式（9）進(jìn)行蜜源選擇，并按照位置調(diào)整準(zhǔn)則進(jìn)行更優(yōu)蜜源的搜索；5）如果經(jīng)過l搜索后，蜜源適應(yīng)度值的變化量小于ε，對其進(jìn)行雜交操作；6）如果迭代次數(shù)小于M，跳到步驟2），否則，算法結(jié)束，輸出最優(yōu)解.

4 仿真分析

仿真實驗在Intel Xeon E5－2650CPU 2.0GHz，內(nèi)存16G的聯(lián)想Think Station C30工作站上進(jìn)行.物理網(wǎng)絡(luò)由10個自治域構(gòu)成，每個自治域包含50個節(jié)點(diǎn)，其中，邊界節(jié)點(diǎn)2個，并且邊界節(jié)點(diǎn)之間是全連接.其他仿真參數(shù)，如表1所示.表1中：t1為仿真時間.

表1 仿真參數(shù)表Tab.1 Simulation parameter

4種算法的平均劃分時間（t）隨虛擬節(jié)點(diǎn)數(shù)（n）的變化，如圖1所示.隨著虛擬節(jié)點(diǎn)數(shù)的增加，4種算法的平均劃分時間都變大.這是因為虛擬節(jié)點(diǎn)數(shù)越多，虛擬網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜，需要花更多的時間完成虛擬網(wǎng)絡(luò)的劃分.其中，OABC－MVNE算法所需的平均劃分時間最小，這是由于OABC－MVNE算法使用OABC算法進(jìn)行域間映射劃分，從而避免了復(fù)雜的數(shù)學(xué)運(yùn)算，實現(xiàn)了平均劃分時間的減少.

3種算法的額外映射開銷（η）隨虛擬節(jié)點(diǎn)數(shù)（n）的變化，如圖2所示.由圖2可知：Policy－MVNE算法的額外開銷是最大的，這是因為在邊界節(jié)點(diǎn)信息未知的情況下，Policy－MVNE算法并沒有對跨域開銷進(jìn)行優(yōu)化.圖2中：OABC－MVNE算法和GA－MVNE算法的額外開銷都始終小于5%.這是因為2種算法在邊界節(jié)點(diǎn)信息已知的情況下以最小資源開銷為目標(biāo)進(jìn)行了跨域開銷的優(yōu)化.由于OABC－MVNE算法的尋優(yōu)能力更強(qiáng)，因此，其額外開銷小于GA－MVNE算法.

圖1 平均劃分時間隨虛擬節(jié)點(diǎn)數(shù)的變化Fig.1 Average time changing with the number of virtual nodes

圖2 額外映射開銷隨虛擬節(jié)點(diǎn)數(shù)的變化Fig.2 Additional costs vary with the number of virtual nodes mapping

5 結(jié)束語

首先，對MVNE問題的基本概念與研究現(xiàn)狀進(jìn)行闡述，指出現(xiàn)有算法存在復(fù)雜度高、平均劃分時間長、開銷大等缺陷.然后，針對以上問題，提出了OABC－MVNE算法，并介紹了OABC－MVNE算法的實現(xiàn)過程.最后，通過仿真實現(xiàn)，從平均劃分時間、平均接受率、平均額外開銷3個方面，驗證了OABCMVNE算法的有效性.

［1］ CHEN Zhong，GUAN Zhi，MENG Hongwei，et al.A survey of future internet architecture and security design［J］.Journal of Information Security Research，2015，6（2）：89－98.

［2］ LUO Juan，F(xiàn)U Shan，CHEN Lei，et al.Concurrent resource mapping in virtual network［J］.Journal of Computational ＆Theoretical Nanoscience，2014，11（5）：1264－1270.

［3］ FISCHER A，BOTERO J F，TILL BECK M，et al.Virtual network embedding：A survey［J］.IEEE Communications Surveys ＆Tutorials，2013，15（4）：1888－1906.

［4］ PITTARAS C，PAPAGOANNI C，HAM J V D，et al.Resource discovery and allocation for federated virtualized infrastructures［J］.Future Generation Computer Systems，2015，42（C）：55－63.

［5］ DIETRICH D，RIZK A，APADIMITRIOU P.Multi－domain virtual network embedding with limited information disclosure［C］∥Proceedings of IFTP Networking Conference.Brookyln：IEEE Press，2013：1－9.

［6］ CHOWDHURY M，SAMUEL F，BOUTABA R.PolyViNE：Policy－based virtual network embedding across multiple domains［J］.Journal of Internet Services and Applications，2013，6（4）：1－23.

［7］ XIAO Ailing，WANG Ying，MENG Luoming，et al.Knowledge description and genetic algorithm based multi－domain virtual network embedding［J］.Journal of Software，2014，25（10）：1289－2205.

［8］ RAZZAQ A.Virtual network embedding［J］.Journal of Electrical ＆Computer Engineering，2012，7（15）：762－771.

［9］ KARABOGA D，BASTURK B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）：687－697.

［10］ 黃嫻，譚鴿偉.人工蜂群算法結(jié)合PTS技術(shù)的PAPR降低方法［J］.華僑大學(xué)學(xué)報（自然科學(xué)版），2014，35（6）：631－635.

（責(zé)任編輯：黃曉楠 英文審校：吳逢鐵）

Multi－Domain Virtual Network Mapping Algorithm Based on Optimized Artificial Bee Colony

GU Yanlin
（College of Computer Science and Technology，Inner Mongolia University of Finance and Economics，Huhehaote 361021，China）

Aiming at the problem of multi－domain virtual network embedding，a multi－domain virtual network mapping algorithm based on optimized artificial bee colony is proposed.The proposed algorithm can maximize the utilization of limited physical network resources through centralized management and distributed control.And to overcome the defaults of the local optimization and low convergence of the traditional artificial bee colony algorithm，an optimized artificial bee colony algorithm is proposed，which is used to deal with the division of cross－domain mapping request.The experimental result shows that compared with LID－MVNE，Policy－MVNE，GA－MVNE，the proposed algorithm can realize higher acceptance ratio with less extra cost and time division.

artificial bee colony；virtual network；autonomous domain；service agent

TP 393

A

1000－5013（2016）04－0507－04

10.11830／ISSN.1000－5013.201604023

2016－05－01

顧艷林（1971－），女，副教授，主要從事計算機(jī)應(yīng)用及網(wǎng)絡(luò)、程序設(shè)計的研究.E－mail：guyanlin5830908＠

126.com.

內(nèi)蒙古自治區(qū)教育科學(xué)規(guī)劃課題（GJ2011－51－02）