關于跨域虛擬網絡的優(yōu)化狼群映射研究仿真

王珂琦，張 耀

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

1 引言

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

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

2 跨域映射模型

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

圖1 跨域映射模型框圖

(1)

(2)

(3)

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

(4)

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

(5)

3 虛擬網絡域內映射

(6)

(7)

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

(8)

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

(9)

(10)

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

4 虛擬網絡域間映射

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

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

(11)

(12)

(13)

其中的D是維度，ω是閾值系數。

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

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

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

(14)

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

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

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

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

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

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

5 仿真分析

5.1 仿真與參數設置

仿真采用GT-ITM構建網絡拓撲，其中設定InPs數量為5個，物理節(jié)點數量為100，物理鏈路數量為500，且網絡中InPs提供給節(jié)點的資源滿足[20,50]與[0,50]均勻分布，設置虛擬節(jié)點形成鏈路的概率為0.5。另外初始化參數如表1所示。

表1 初始化參數

5.2 仿真結果分析

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

圖2 映射開銷與節(jié)點數量關系曲線

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

圖3 映射開銷與網絡域數量關系

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

圖4 跨域虛擬網絡映射執(zhí)行時間

6 結束語

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