優化人工蜂群算法的跨域虛擬網絡映射算法

顧艷林（內蒙古財經大學計算機信息管理學院，內蒙古呼和浩特010020）

優化人工蜂群算法的跨域虛擬網絡映射算法

顧艷林
（內蒙古財經大學計算機信息管理學院，內蒙古呼和浩特010020）

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

人工蜂群；虛擬網絡；自治域；服務代理

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

1 MVNE模型

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

2 優化目標

由于盡量減少虛擬鏈路所消耗的鏈路資源就能以最小的代價完成MVNE.因此，MVNE算法的優化目標函數為

式（1）中：li，j為虛擬鏈路；rcd為li，j對應的物理路徑；ls為li，j中的物理鏈路；m為虛擬網絡的節點數；n為物理網絡的節點數；D（ls）為ls的時延；λ為單位時延開銷；xi為li，j的類型，其表達式為

同時，表達式還應滿足2個約束條件，即

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

3 算法實現

虛擬網絡劃分問題已被證明是NP－hard問題，為了得到該問題的近似最優解，OABC－MVNE算法使用優化人工蜂群（optimized artificial bee colony，OABC）算法完成域間請求到域內請求的劃分.

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

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

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

定義2 蜜源的適應度.由于蜜源的好壞直接由蜜源的適應度fit（Xi）決定，因此，以MVNE算法的優化目標函數為參考設定fit（Xi），其值為

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

式（8）中：φi，j為［－1，1］上的隨機數；xbesti，j為蜜源歷史最優位置.

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

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

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

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

4 仿真分析

仿真實驗在Intel Xeon E5－2650CPU 2.0GHz，內存16G的聯想Think Station C30工作站上進行.物理網絡由10個自治域構成，每個自治域包含50個節點，其中，邊界節點2個，并且邊界節點之間是全連接.其他仿真參數，如表1所示.表1中：t1為仿真時間.

表1 仿真參數表Tab.1 Simulation parameter

4種算法的平均劃分時間（t）隨虛擬節點數（n）的變化，如圖1所示.隨著虛擬節點數的增加，4種算法的平均劃分時間都變大.這是因為虛擬節點數越多，虛擬網絡結構越復雜，需要花更多的時間完成虛擬網絡的劃分.其中，OABC－MVNE算法所需的平均劃分時間最小，這是由于OABC－MVNE算法使用OABC算法進行域間映射劃分，從而避免了復雜的數學運算，實現了平均劃分時間的減少.

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

圖1 平均劃分時間隨虛擬節點數的變化Fig.1 Average time changing with the number of virtual nodes

圖2 額外映射開銷隨虛擬節點數的變化Fig.2 Additional costs vary with the number of virtual nodes mapping

5 結束語

首先，對MVNE問題的基本概念與研究現狀進行闡述，指出現有算法存在復雜度高、平均劃分時間長、開銷大等缺陷.然后，針對以上問題，提出了OABC－MVNE算法，并介紹了OABC－MVNE算法的實現過程.最后，通過仿真實現，從平均劃分時間、平均接受率、平均額外開銷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，FU 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］ 黃嫻，譚鴿偉.人工蜂群算法結合PTS技術的PAPR降低方法［J］.華僑大學學報（自然科學版），2014，35（6）：631－635.

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

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－），女，副教授，主要從事計算機應用及網絡、程序設計的研究.E－mail：guyanlin5830908＠

126.com.

內蒙古自治區教育科學規劃課題（GJ2011－51－02）