關(guān)于跨域虛擬網(wǎng)絡(luò)的優(yōu)化狼群映射研究仿真

王珂琦，張 耀

(河南工業(yè)大學(xué)漯河工學(xué)院，河南 漯河 462000)

1 引言

虛擬網(wǎng)絡(luò)的作用是解決物理網(wǎng)絡(luò)拓?fù)涞慕┗瘑栴}[1]，從而使有限的物理資源能夠滿足更多的網(wǎng)絡(luò)事務(wù)需求。而虛擬網(wǎng)絡(luò)映射，就是把物理資源準(zhǔn)確有效的配置到相應(yīng)的虛擬網(wǎng)絡(luò)上[2-3]，完成功能擴(kuò)展。隨著分布式網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)業(yè)務(wù)的運(yùn)營一般不是由單一服務(wù)商獨(dú)立支撐，而且物理網(wǎng)絡(luò)也并非處于同一位置，這就使得虛擬網(wǎng)絡(luò)映射需要面對大量具有異構(gòu)與分布性質(zhì)的跨域網(wǎng)絡(luò)資源，同時對虛擬網(wǎng)絡(luò)映射算法提出了更高要求。

文獻(xiàn)[4]分析了網(wǎng)絡(luò)節(jié)點(diǎn)與鄰近鏈路之間的資源差異，采用k最小路徑方式動態(tài)更新節(jié)點(diǎn)與鏈路資源，并得到鏈路開銷狀況，該方法獲得較好的映射率，并且能夠在資源缺乏時采取調(diào)整動作。文獻(xiàn)[5]針對最優(yōu)映射采用元胞遺傳算法，定義了元胞自動機(jī)，并利用改進(jìn)遺傳優(yōu)化元胞近鄰的訓(xùn)練能力，從而提高算法的收斂速度與局部最優(yōu)解的搜索性能，但是該方法缺乏對鄰域模型的動態(tài)調(diào)整能力。文獻(xiàn)[6]針對跨域情況設(shè)計了分層分域的資源管理模型，將最低映射開銷作為最優(yōu)解搜索，并引入蜂群改進(jìn)尋優(yōu)性能，取得了較好的網(wǎng)絡(luò)請求能力，但是該算法復(fù)雜度過高，無法應(yīng)用在網(wǎng)絡(luò)規(guī)模較大的場合。文獻(xiàn)[7]也將網(wǎng)絡(luò)映射轉(zhuǎn)換為尋優(yōu)問題，將單純形算法與遺傳相結(jié)合，從而避免遺傳算法早熟。現(xiàn)有的研究算法，都針對虛擬網(wǎng)絡(luò)映射的某個方面進(jìn)行優(yōu)化，并取得了一定程度的效果，但是缺乏對跨域本質(zhì)區(qū)別的考慮分析，不同域的網(wǎng)絡(luò)之間存在信息的未知性，同時，任一網(wǎng)絡(luò)域都存在不止一個對外節(jié)點(diǎn)，對外節(jié)點(diǎn)選取的不同會產(chǎn)生開銷差異，為此，本文提出了關(guān)于跨域虛擬網(wǎng)絡(luò)的優(yōu)化狼群映射方法。該方法分別針對域內(nèi)映射和域間映射進(jìn)行分析，采用資源開銷作為目標(biāo)，引入元胞轉(zhuǎn)換為尋優(yōu)計算。由于域內(nèi)映射產(chǎn)生的開銷不大，因此對其進(jìn)行快速處理，而域間開銷則加入優(yōu)化狼群，增加元胞尋優(yōu)的多樣性與全局性，提高域間映射的有效性，降低域間開銷。

2 跨域映射模型

跨域虛擬網(wǎng)絡(luò)的映射可以通過圖1來描述。圖中模擬了三個虛擬網(wǎng)絡(luò)域，它們分別由三個InPs建立。在任意的網(wǎng)絡(luò)域中，都包含N類和B類兩種節(jié)點(diǎn)，它們分別代表各域中的內(nèi)部與邊界節(jié)點(diǎn)。所謂的跨域網(wǎng)絡(luò)映射，本質(zhì)就是利用N節(jié)點(diǎn)完成虛擬網(wǎng)絡(luò)的搭建，并利用B節(jié)點(diǎn)實(shí)現(xiàn)跨域數(shù)據(jù)的傳遞。

圖1 跨域映射模型框圖

(1)

(2)

(3)

另外，虛擬網(wǎng)絡(luò)中心還需要具有切片功能，因此，在其中一些節(jié)點(diǎn)中還應(yīng)該加以限制

(4)

當(dāng)滿足上述限制條件時，即認(rèn)為映射為有效的，虛擬網(wǎng)絡(luò)中會出現(xiàn)若干映射情況，而本文針對跨域虛擬網(wǎng)絡(luò)映射存在資源分配不合理，開銷過重，以及負(fù)載不均衡的問題進(jìn)行改進(jìn)優(yōu)化，為此，這里把跨域虛擬網(wǎng)絡(luò)在實(shí)現(xiàn)映射過程中所產(chǎn)生的負(fù)載情況描述如下

(5)

3 虛擬網(wǎng)絡(luò)域內(nèi)映射

(6)

(7)

網(wǎng)絡(luò)底層資源始終處于動態(tài)變化，尤其在負(fù)載增加的情況下，經(jīng)常會出現(xiàn)節(jié)點(diǎn)非均衡現(xiàn)象，如果要實(shí)現(xiàn)最大利益，就應(yīng)該盡可能縮減網(wǎng)絡(luò)底層成本，同時也應(yīng)該達(dá)到節(jié)點(diǎn)的均衡性。因此本文將底層資源的配置設(shè)定為元胞繁殖動作，將回收設(shè)定為元胞死亡動作，于是，更新操作可以進(jìn)一步描述為

(8)

映射產(chǎn)生的節(jié)點(diǎn)成本固定不變，在采用的映射策略改變時，影響的是所需帶寬，于是，設(shè)計模型更新過程中的目標(biāo)函數(shù)如下

(9)

(10)

假定虛擬網(wǎng)絡(luò)節(jié)點(diǎn)u與v依次完成了至底層i與j節(jié)點(diǎn)的映射處理，則u與v對應(yīng)的路徑也會與底層路徑形成對應(yīng)關(guān)系，因此通過上述連接限定，就能夠控制底層節(jié)點(diǎn)間的流量。

4 虛擬網(wǎng)絡(luò)域間映射

4.1 優(yōu)化狼群算法

狼群算法在尋求最優(yōu)解的過程中是利用分工合作機(jī)制完成的，其中包含頭狼，探狼，以及猛狼。探狼具有游走行為，根據(jù)決策獲取所需信息，同時得到頭狼的位置信息。頭狼具有召喚行為，傳遞猛狼和獵物對應(yīng)的信息。通過分工合作機(jī)制達(dá)到信息搜索與傳輸目的，并實(shí)現(xiàn)捕獵行為，即最優(yōu)解搜尋。

(11)

(12)

(13)

其中的D是維度，ω是閾值系數(shù)。

4.2 基于狼群優(yōu)化的虛擬網(wǎng)絡(luò)域間映射

對于跨域虛擬網(wǎng)絡(luò)，要得到資源的最佳配置，除了分析域內(nèi)的鏈路與節(jié)點(diǎn)消耗外，還需要分析域間的消耗情況。由于狼群算法具有出色的全局尋優(yōu)性能，因此，引入狼群優(yōu)化算法，改進(jìn)映射處理時鏈路與節(jié)點(diǎn)資源的全局性。在具有跨域?qū)傩缘奶摂M網(wǎng)絡(luò)中，MANO無法獲知網(wǎng)絡(luò)的詳細(xì)信息，可以利用競價來估算出各個網(wǎng)絡(luò)域的資源配置情況，也就是從域間的鏈路開銷與節(jié)點(diǎn)開銷兩方面采取配置分析。其中在鏈路資源方面，采取啟發(fā)算法，搜索出滿足時間約束的有效解。在節(jié)點(diǎn)資源方面，MANO能夠保存SP所請求的目標(biāo)節(jié)點(diǎn)，同時InPs會把所在域中的可用節(jié)點(diǎn)及其對應(yīng)資源與開銷通知服務(wù)中心，服務(wù)中心據(jù)此來建立競價機(jī)制，并由MANO完成節(jié)點(diǎn)的合理映射。

將虛擬網(wǎng)絡(luò)節(jié)點(diǎn)作為元胞，所有節(jié)點(diǎn)對應(yīng)的元胞組成一組向量，向量的大小由節(jié)點(diǎn)數(shù)量決定，向量中任意分量表示節(jié)點(diǎn)標(biāo)識，不同的映射結(jié)果將產(chǎn)生不同的向量。另外，在映射過程中，向量結(jié)果也將同步進(jìn)行更新。更新的判定依據(jù)為方向向量，其向量元素包含0和1，分別對應(yīng)不更新與更新標(biāo)志。對于每種映射結(jié)果，為判定其優(yōu)劣程度，設(shè)計目標(biāo)函數(shù)如下

(14)

這里的LEN(u，v)代表鏈路(u，v)映射時對應(yīng)的實(shí)際跳數(shù)，BW(u，v)代表鏈路帶寬。根據(jù)該公式，利用域間節(jié)點(diǎn)的映射情況計算出鏈路的目標(biāo)函數(shù)，獲取鏈路的適應(yīng)程度。其處理過程可以描述如下：

1)參數(shù)初始化，包括元胞向量，方向向量，狼群數(shù)量，以及其它因子參數(shù)；

2)隨機(jī)選擇頭狼，并搜索出合理的探狼，進(jìn)行游走，利用方向更新節(jié)點(diǎn)元胞位置，得到新的元胞向量；

3)求解映射的最小路徑，利用猛狼感知，當(dāng)Yi>Wlead時，令Wlead=Yi，并產(chǎn)生召喚信息，當(dāng)Yi

4)利用目標(biāo)函數(shù)得到適應(yīng)度，并根據(jù)適應(yīng)度衡量節(jié)點(diǎn)元胞向量的優(yōu)劣性，零局部演化Δfi=0，且kmax=kmax+1，采取獵殺操作，對現(xiàn)有優(yōu)勢空間進(jìn)行更新操作。

5)再次更新元胞向量，求解鏈路最小路徑，當(dāng)成功實(shí)現(xiàn)映射，跳回上一步，當(dāng)未成功完成映射，同時又未達(dá)到約束計數(shù)上限的，繼續(xù)更新元胞向量，直至映射成功或者確定失敗。

5 仿真分析

5.1 仿真與參數(shù)設(shè)置

仿真采用GT-ITM構(gòu)建網(wǎng)絡(luò)拓?fù)洌渲性O(shè)定InPs數(shù)量為5個，物理節(jié)點(diǎn)數(shù)量為100，物理鏈路數(shù)量為500，且網(wǎng)絡(luò)中InPs提供給節(jié)點(diǎn)的資源滿足[20,50]與[0,50]均勻分布，設(shè)置虛擬節(jié)點(diǎn)形成鏈路的概率為0.5。另外初始化參數(shù)如表1所示。

表1 初始化參數(shù)

5.2 仿真結(jié)果分析

為了驗(yàn)證本文方法在虛擬網(wǎng)絡(luò)映射中的實(shí)際性能，仿真過程中，采用文獻(xiàn)[5]與文獻(xiàn)[6]中的方法作為對比。首先，通過仿真，得到虛擬網(wǎng)絡(luò)映射的開銷與節(jié)點(diǎn)數(shù)量之間的關(guān)系，如圖2所示。根據(jù)結(jié)果曲線可知，隨著虛擬網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增加，所有方法的映射開銷均呈現(xiàn)增加趨勢，其中兩種文獻(xiàn)方法的增長速度近似線性，當(dāng)節(jié)點(diǎn)數(shù)量達(dá)到一定值后，很容易導(dǎo)致處理崩潰，而本文方法則近似于對數(shù)增長，當(dāng)節(jié)點(diǎn)數(shù)量急劇增加時，其映射開銷也不會隨之急劇增加，由于從節(jié)點(diǎn)與鏈路兩方面進(jìn)行資源尋優(yōu)，同時針對離散情況引入元胞處理，有效提高了離散情況下最優(yōu)解的尋求性能，能夠有效應(yīng)對大規(guī)模網(wǎng)絡(luò)場景。

圖2 映射開銷與節(jié)點(diǎn)數(shù)量關(guān)系曲線

為了驗(yàn)證本文方法在跨域映射中的具體性能，仿真得出映射開銷與網(wǎng)絡(luò)域數(shù)量之間的關(guān)系，如圖3所示。實(shí)驗(yàn)過程中，令虛擬節(jié)點(diǎn)與底層節(jié)點(diǎn)數(shù)量相同，僅讓底層的網(wǎng)絡(luò)域數(shù)量發(fā)生改變。根據(jù)結(jié)果數(shù)據(jù)比較，當(dāng)網(wǎng)絡(luò)域數(shù)量發(fā)生改變時，文獻(xiàn)方法的映射開銷均有一定程度的增加，而本文方法的映射開銷幾乎保持不變，且始終小于文獻(xiàn)方法的映射開銷。表明網(wǎng)絡(luò)域的增加導(dǎo)致文獻(xiàn)方法的額外開銷，本文方法由于針對域間映射做了處理，并引入狼群優(yōu)化，結(jié)合元胞處理，有效應(yīng)對了跨域映射的尋優(yōu)性能，合理處理了域內(nèi)與域間的節(jié)點(diǎn)、帶寬資源，實(shí)現(xiàn)域間節(jié)點(diǎn)的資源均衡。

圖3 映射開銷與網(wǎng)絡(luò)域數(shù)量關(guān)系

圖4所示為三種網(wǎng)絡(luò)映射的執(zhí)行時間結(jié)果，可以看出，本文方法的執(zhí)行速度要稍微領(lǐng)先于文獻(xiàn)方法。這三種方法均為改進(jìn)方法，在引入算法時帶來了算法與時間復(fù)雜度的增加，本文方法由于元胞空間的龐大，導(dǎo)致映射處理的中間變量增加，但是元胞與狼群優(yōu)化對于尋優(yōu)和收斂效果的改進(jìn)，使得本文方法在映射時間上最終還是產(chǎn)生了一定的優(yōu)勢。

圖4 跨域虛擬網(wǎng)絡(luò)映射執(zhí)行時間

6 結(jié)束語

虛擬網(wǎng)絡(luò)映射可以把物理資源配置到對應(yīng)的虛擬節(jié)點(diǎn)上，并在其上實(shí)現(xiàn)業(yè)務(wù)處理功能，避免網(wǎng)絡(luò)底層資源受成本和性能等因素制約。由于現(xiàn)有虛擬網(wǎng)絡(luò)映射算法不能有效滿足跨域分布需求，本文提出了優(yōu)化狼群映射算法。將跨域映射問題分解為域內(nèi)和域間兩種情況進(jìn)行分析。在跨域映射時，主要資源開銷在于域間，因此對域內(nèi)采取快速處理，僅引入元胞處理進(jìn)行最優(yōu)資源開銷搜索。域間處理在元胞基礎(chǔ)上加入了優(yōu)化狼群，增強(qiáng)全局搜索能力，從而得到合理的節(jié)點(diǎn)與鏈路資源分配。通過仿真，驗(yàn)證了本文方法在跨域情況下，有效降低了網(wǎng)絡(luò)映射開銷，且資源開銷受網(wǎng)絡(luò)域數(shù)量的影響很小，同時也降低了網(wǎng)絡(luò)映射的執(zhí)行時間。