博弈論組合賦權的虛擬網(wǎng)絡映射算法

徐 江，孟相如，韓曉陽，史朝衛(wèi)

1(空軍工程大學 研究生院，西安 710051) 2(空軍工程大學 信息與導航學院，西安 710077)

1 引 言

網(wǎng)絡虛擬化[1]為解決網(wǎng)絡“僵化”問題提供了有效手段，它可以實現(xiàn)多個異構的虛擬網(wǎng)絡(Virtual Network，VN)共享底層網(wǎng)絡(Substrate Network，SN)資源，不僅提高了網(wǎng)絡資源利用率，也帶來了更加靈活多樣的服務，虛擬網(wǎng)絡映射作為網(wǎng)絡虛擬化的關鍵技術之一，受到廣泛關注[2-4].

虛擬網(wǎng)絡映射已被證明是NP-hard問題，相關的解決方法已經成為研究熱點[5-8].虛擬網(wǎng)絡映射按步驟可分一階段和兩階段映射，一階段映射算法由于復雜度較高，適應性較低，目前兩階段映射算法是研究的主流[3]，即首先將網(wǎng)絡所有節(jié)點進行映射，然后再進行鏈路映射，因此節(jié)點映射策略對于虛擬網(wǎng)絡映射成功與否起到非常關鍵的作用.節(jié)點映射方法主要有啟發(fā)式算法[4]、線性規(guī)劃求解[5]和智能優(yōu)化算法[6]等，節(jié)點排序也已經從簡單的節(jié)點資源排序[7]，發(fā)展到拓撲資源聯(lián)合排序[8]，逐漸形成了節(jié)點多指標排序[9]的問題.文獻[10]提出一種基于TOPSIS(Technique for Order Preference by Similarity to Ideal Solution，TOPSIS)的節(jié)點重要性評估方法，并且在考慮節(jié)點資源屬性的基礎上，引入了社會網(wǎng)絡分析法中的度中心性和接近度中心性，但TOPSIS方法的歐式距離無法區(qū)分與正負理想方案距離相等的點，并且節(jié)點指標權重人為設置，主觀性較強.文獻[11]提出一種加權相對熵的節(jié)點排序方法，能實現(xiàn)虛擬拓撲與物理拓撲聯(lián)合感知，但是其指標權重需要根據(jù)環(huán)境變化進行人為調整，因此對經驗依賴較大.文獻[12]介紹了底層網(wǎng)絡特征的提取過程、節(jié)點排序方法，并利用粒子群優(yōu)化方法訓練指標權重向量，它可以針對不同的優(yōu)化目標，自動確定算法中的參數(shù)，但是算法復雜度較高.

從目前的研究來看，虛擬網(wǎng)絡映射中節(jié)點多指標排序的問題，歸根到底是指標選擇與權重確定的問題.節(jié)點指標選擇主要是將節(jié)點資源屬性與拓撲屬性相結合從而更為綜合的反映節(jié)點的重要性，但是各指標之間相互關系復雜，對于具體指標的選擇是一個挑戰(zhàn)；指標權重的獲取主要有主觀賦權法[13]和客觀賦權法[14]，主觀賦權法結合了專家的經驗，能夠根據(jù)實際情況進行針對性的調整，但是對經驗依賴性較強，客觀賦權法基于相應的科學理論，方法眾多、應用廣泛，但與實際問題結合中存在一定的片面性.

針對上述問題，本文提出一種博弈論組合賦權的虛擬網(wǎng)絡映射算法(Virtual Network Embedding Algorithm Based on Game Theory Combination Weighting，GTCW-VNE)，首先綜合考慮節(jié)點資源屬性與拓撲屬性提取特征指標，進行歸一化處理后組成節(jié)點特征指標向量并構建決策矩陣，其次利用層次分析法(Analytic Hierarchy Process，AHP)和熵值法分別獲取節(jié)點指標權重向量，然后利用博弈論組合賦權法對其進行平衡，進而將具有互補作用的主客觀賦權法結合，兼顧兩者優(yōu)點，得到最優(yōu)的權重向量，最后按節(jié)點特征指標向量與指標權重向量的內積值對節(jié)點排序.仿真結果表明該算法提高了虛擬網(wǎng)絡映射成功率和收益開銷比.

本文的主要貢獻如下：

a.將虛擬網(wǎng)絡映射建模為一個節(jié)點多指標排序的優(yōu)化問題，指出影響節(jié)點排序優(yōu)劣的主要因素為能否根據(jù)映射目標選取合適的節(jié)點指標和權重.

b.提出了博弈論組合賦權的虛擬網(wǎng)絡映射算法，首次將主觀賦權方法與客觀賦權方法結合運用于虛擬網(wǎng)絡映射，提升了算法性能.

c.為了提高映射算法應對環(huán)境變化的能力，將熵值賦權法與AHP應用于節(jié)點指標賦權，使得節(jié)點指標權重可以隨網(wǎng)絡環(huán)境的變化進行相應的調整，增強了節(jié)點指標賦權的靈活性.

2 虛擬網(wǎng)絡映射模型與評價指標

2.1 網(wǎng)絡映射模型

2.1.1 底層物理網(wǎng)絡

底層物理節(jié)點與鏈路分別用與表示，底層物理網(wǎng)絡用帶權無向圖表示.可用CPU資源、地理位置約束為物理節(jié)點的屬性；物理鏈路的屬性為可用帶寬資源.

2.1.2 虛擬網(wǎng)絡

虛擬節(jié)點與鏈路分別用Nv與Ev表示，虛擬網(wǎng)絡用帶權無向圖Gv=(Nv，Ev)表示，CPU資源需求cpu(nv)和地理位置需求loc(nv)為虛擬節(jié)點nv的屬性；虛擬鏈路ev的屬性為帶寬資源需求bw(ev).

2.1.3 虛擬網(wǎng)絡映射

虛擬網(wǎng)絡映射是在滿足底層物理網(wǎng)絡承載能力的基礎上，將VN的節(jié)點和鏈路映射到SN中節(jié)點和鏈路的過程，主要分節(jié)點映射和鏈路映射兩個階段.圖1所示為一個映射可行方案，a，b，c為虛擬節(jié)點，A，B，C，D為物理節(jié)點，節(jié)點的CPU資源需求和可用CPU資源分別用方框內的數(shù)字表示，帶寬需求和可用帶寬資源分別用實線上的數(shù)字表示，虛擬網(wǎng)絡請求的節(jié)點映射方案為{a→A，b→D，c→C}，鏈路映射方{(a，b)→(A，D)，(a，c)→(A，C)，(b，c)→(D，C)}.

圖1 虛擬網(wǎng)絡映射示例

2.2 評價指標

2.2.1 映射成功率

虛擬網(wǎng)絡的映射成功率可表示為：

(1)

其中，NUMvacpt與NUMvall分別表示T時間內已經映射成功的虛擬網(wǎng)絡數(shù)和虛擬網(wǎng)絡映射請求總數(shù)，δ為無限小的常數(shù).

2.2.2 收益開銷比

虛擬網(wǎng)絡請求Gv=(Nv，Ev)在t時刻的收益R(Gv，t)與開銷C(Gv，t)分別定義為：

(2)

(3)

其中，參數(shù)α、β分別表示節(jié)點與鏈路資源的權重參數(shù)，對于網(wǎng)絡運營商來說收益和開銷的計算是復雜的，因此可根據(jù)實際情況設置不同的值，本文在仿真環(huán)境中為了便于比較計算將參數(shù)都設置為1.hops(ev)為虛擬鏈路在物理鏈路上經過的跳數(shù).

長期平均收益開銷比可以反映物理網(wǎng)絡資源的利用程度，定義為：

(4)

3 算法設計

3.1 節(jié)點特征指標提取

網(wǎng)絡中每個節(jié)點都有著各自的特征，這些特征決定了節(jié)點在網(wǎng)絡中的重要程度，在節(jié)點多指標排序的虛擬網(wǎng)絡映射算法中，為了更加科學的對節(jié)點進行排序，提高映射效率，需要對網(wǎng)絡節(jié)點提取相應的特征指標，從而更加全面的對節(jié)點資源進行描述.本文提取了以下4個節(jié)點特征指標.

3.1.1 節(jié)點計算資源

節(jié)點計算資源NCR(ni)用CPU資源表示，如式(5)所示.

NCR(ni)=cpu(ni)

(5)

具有較大計算資源的物理節(jié)點將更有可能承載資源需求較多的虛擬節(jié)點.隨著虛擬節(jié)點的映射，此項資源也將隨之更新.

3.1.2 節(jié)點鄰接帶寬資源

節(jié)點的鄰接帶寬資源即與節(jié)點相連的所有鄰接鏈路帶寬之和，反映了此節(jié)點可用的帶寬資源，如式(6)所示.

(6)

式中，E(ni)為節(jié)點ni的鄰接鏈路集合.

3.1.3 節(jié)點的度

節(jié)點的度指的是與該節(jié)點直接相連的節(jié)點數(shù)量，用DEG(ni)表示，對于一個有較多鏈路連接的節(jié)點，該節(jié)點可以擁有更多連通性，更有可能找到與其它節(jié)點之間較短的通路，如式(7)所示.

(7)

式中，Gn為網(wǎng)絡中所有節(jié)點的集合，Aij表示節(jié)點ni和nj的關系，如果兩個節(jié)點相鄰則值為1，不相鄰則值為0.

3.1.4 節(jié)點就近度

節(jié)點就近度能夠反映節(jié)點在網(wǎng)絡拓撲中的重要性，如式(8)所示.

(8)

(9)

在獲得了節(jié)點的特征指標向量之后，為特征指標向量中的每一個元素賦予一個權重wNCR，wDC，wDEG，wCC，構造出節(jié)點的權重向量w(n)，如式(10)所示.

w(n)=[wNCR，wDC，wDEG，wCC]

(10)

將特征指標向量與權重向量的內積作為節(jié)點排序的依據(jù)，如式(11)所示.

W(ni)=a(ni)·w(n)

(11)

3.2 博弈論組合賦權模型

在虛擬網(wǎng)絡映射中，節(jié)點權重向量的選取對映射結果有決定性的影響，然而使用單一方法確定權重向量難以避免片面性、獨斷性，為了提高權重向量賦值的科學性，本文采用博弈論組合賦權方法確定節(jié)點權重向量.

3.2.1 基本權重集

為了提高節(jié)點權重向量選擇的科學性，可以使用L種方法獲取權重向量，如此構造出一個基本權重向量集{ω1，ω2…，ωk}，k=1，2…L，本文采用熵值法和層次分析法2種方法獲取基本權重向量集.

熵值法：熵值法通過指標的相對差異判斷其對系統(tǒng)的影響程度，是一種客觀賦權方法.

首先，根據(jù)節(jié)點特征指標向量，構建決策矩陣A，如式(12)所示.

A=[a(n1)，a(n2)…，a(nm)]T

(12)

其中，m是網(wǎng)絡中節(jié)點的數(shù)目，a(ni)為節(jié)點的特征指標向量.

計算節(jié)點第j個指標的熵值為Ej，如式(13)所示.

j=1，2…，N

(13)

其中，aij為代表矩陣A中第i個節(jié)點，第j個指標的值，N為節(jié)點指標數(shù)量.

最終，確定指標權重wj，如式(14)所示.

(14)

層次分析法賦權：層次分析法能夠將復雜的多目標問題分解成為層次結構來解決，本文將節(jié)點計算資源、鄰接帶寬資源、度和就近度指標作為一層分析，層次分析法的具體過程參考文獻[13].

3.2.2 可能權重向量集

可能權重向量集是優(yōu)化權重的基礎，它由基本權重向量集構建而成，為優(yōu)化權重提供了多樣的選擇，可能權重向量集里包含了我們需要的理想權重向量.記k個權重向量ωk(本文采用熵值法和層次分析法分別獲取指標權重向量)的任意線性組合為：

(15)

3.2.3 博弈論組合賦權法

博弈論組合賦權的思想在于“協(xié)調沖突，利益最大化”，即盡量找到與各個基本指標權重向量之間偏差最小的向量，可以歸結為對公式(15)中的線性組合系數(shù)?k進行優(yōu)化，從而使w和各個ωk的離差最小，有對策模型如式(16)所示.

(16)

求解該模型即可得到一個與基本賦權方法相協(xié)調、均衡的綜合權重向量.

由矩陣的微分性質可得到式(16)最優(yōu)化的導數(shù)為：

(17)

對應的線性方程組公式為：

(18)

式(18)求得的(?1，?2，…?L)，有時并不能滿足作為指標權重向量的系數(shù)，因此要進行歸一化處理，如式(19)所示.

(19)

4 GTCW-VNE算法實現(xiàn)

本節(jié)設計了GTCW-VNE啟發(fā)式算法求解節(jié)點多指標排序的虛擬網(wǎng)絡映射問題.GTCW-VNE算法在節(jié)點映射階段，對虛擬節(jié)點和物理節(jié)點分別計算節(jié)點特征指標向量與權重向量的內積，并作為節(jié)點排序的依據(jù)，鏈路映射采用k-最短路徑算法.GTCW-VNE算法節(jié)點映射步驟如下：

輸入：Gs，Gv

輸出：NodeEmbeddingList

1. 根據(jù)網(wǎng)絡環(huán)境運用層次分析法獲取節(jié)點指標權重向量

2. for虛擬網(wǎng)絡中每一個虛擬節(jié)點nv∈Nv

4. 采用熵值法，運用公式(12)-公式(14)計算節(jié)點指標權重向量

5. 根據(jù)第1步和第4步得出的節(jié)點指標權重向量，運用公式(15)構造可能權重向量集合w

9. end for

11. 把虛擬節(jié)點映射次序存入鏈表VNodeList

13. do

15. 刪除已經映射的候選節(jié)點

17. returnNODE_EMBEDDING_FAILED

18. else

21. end for

23. 更新已映射物理節(jié)點集合OSNode

24. end if

25. end for

26. return NODE_EMBEDDING_SUCCESS

5 性能評估與分析

5.1 仿真環(huán)境

仿真實驗中的底層物理網(wǎng)絡和虛擬網(wǎng)絡請求采用改進Salam網(wǎng)絡拓撲隨機生成算法生成.底層物理網(wǎng)絡在1000×1000范圍內生成均勻分布的100個節(jié)點，節(jié)點間的鏈路連接概率為0.5.物理節(jié)點的CPU資源和物理鏈路的帶寬資源均服從[50，100]的均勻分布，虛擬網(wǎng)絡請求服從泊松分布，每100個時間單元的到達個數(shù)期望為5.虛擬網(wǎng)絡的生存時間服從指數(shù)分布，期望為1000個時間單元，節(jié)點的數(shù)目服從[2，10]的均勻分布，CPU資源需求服從[10，50]的均勻分布，虛擬鏈路帶寬資源需求服從[10，30]的均勻分布，將虛擬節(jié)點的位置約束設置為500.依照文獻[11]的節(jié)點指標權重賦值思想，結合本實驗環(huán)境，設置層次分析法賦權的判斷矩陣如表1所示.

表1 判斷矩陣及指標權值

仿真實驗運行50000個時間單元，進行10次，將平均值作為最終結果以降低隨機因素的影響.

5.2 算法的對比評價

本節(jié)在相同的實驗條件下，設置不同的場景，從映射成功率、長期平均收益開銷比兩方面對比分析GTCW-VNE算法與其它3種算法(見表2)的性能.

表2 算法對比表

圖2是4種不同虛擬網(wǎng)絡映射算法映射成功率隨時間變化的曲線，可以看出，TA-SVNE算法的映射成功率最低，保持在0.62左右，主要是因為其指標權重的選擇過于主觀片面，PSODD-VNE算法采用粒子群優(yōu)化算法，針對特定的評價指標(長期平均收益開銷比)進行多輪訓練，不斷更新各個粒子對應的權重向量參數(shù)，實現(xiàn)排序結果優(yōu)化，但是其指標選擇較為片面，并且沒有考慮虛擬節(jié)點拓撲屬性，因此映射成功率較低，保持在0.70附近，EAJTA-VNE算法不僅綜合考慮了節(jié)點CPU資源、鄰接鏈路帶寬以及就近度3個指標，還采用加權相對熵的方法對具有多個指標的節(jié)點進行量化處理，并且能夠根據(jù)環(huán)境的變化，賦予節(jié)點指標不同權值，其映射成功率保持在0.72附近，本文提出的GTCW-VNE算法，綜合考慮了節(jié)點CPU資源，鄰接鏈路帶寬，節(jié)點的度和就近度4個指標，利用博弈論組合賦權法對熵值法和層次分析法產生的指標權重進行平衡，綜合了主觀賦權法和客觀賦權法的優(yōu)點，因此獲得了更好的效果，其映射成功率最高，保持在0.74左右.

圖3比較了4種算法的長期平均收益開銷比.TA-SVNE算法因為映射成功率最低，收益開銷比明顯低于其它三種算法，穩(wěn)定后為0.4左右，PSODD-VNE算法以平均收益開銷比作為優(yōu)化目標來計算指標權值，但是對虛擬節(jié)點進行排序時僅考慮了資源屬性，并且提取的底層節(jié)點部分指標代表性不強，導致資源開銷較大，所以長期平均收益開銷比較低，穩(wěn)定后維持在0.48附近，EAJTA-VNE算法考慮了節(jié)點CPU資源、鄰接帶寬資源和就近度等屬性，針對網(wǎng)絡環(huán)境變化對指標權重適當進行了調整，并且采用加權相對熵的節(jié)點排序方法實現(xiàn)了拓撲聯(lián)合感知，其收益開銷比較高，穩(wěn)定后為0.5左右，而本文提出的GTCW-VNE算法全面考慮了節(jié)點的資源與拓撲屬性，綜合了主觀與客觀因素對指標權重的影響，獲得了最優(yōu)的權重向量，提高了收益開銷比，穩(wěn)定后為0.51左右.

圖2 映射成功率

Fig.2 Acceptance ratio

圖3 長期平均收益開銷比

Fig.3 Long-term average revenue to cost ratio

本節(jié)在特定網(wǎng)絡環(huán)境下比較分析了4種映射算法的性能，但現(xiàn)實中虛擬網(wǎng)絡請求是多樣化的，并且對節(jié)點資源的需求各異，本節(jié)設置了兩種不同的虛擬網(wǎng)絡請求場景以比較4種算法在不同場景之下的性能.

場景1.本組實驗模擬4種虛擬網(wǎng)絡映射算法在不同CPU需求情況下的性能差異.虛擬網(wǎng)絡CPU需求服從[0，q]的均勻分布，其中，q為虛擬網(wǎng)絡CPU需求上限，帶寬需求服從[10，30]的均勻分布.當CPU需求上限q在[30，50]之間時，層次分析法的判斷矩陣設置如表3所示.

表3 判斷矩陣及指標權值

當CPU需求上限q在[50，70]之間時，層次分析法的判斷矩陣如表4所示.

表4 判斷矩陣及指標權值

從圖4和圖5可以看出，隨著CPU需求的增大4種映射算法的映射成功率均有所下降，GTCW-VNE算法的映射成功率最高且收益開銷比也優(yōu)于其它算法.前期由于虛擬網(wǎng)絡CPU資源需求較少，帶寬需求對于映射成功率影響較大，因此利用層次分析法適當增大帶寬資源的指標權重，優(yōu)先映射鏈路帶寬資源豐富的區(qū)域，后期隨著CPU資源需求的增大，因此對映射成功率影響也越來越大，利用層次分析法適當增大CPU資源的權重，可以提高映射效率.從表3、表4可以看出隨著節(jié)點資源屬性權重的調整，拓撲屬性權重也隨之增加，這有利于減少鏈路映射跳數(shù)，節(jié)約資源開銷，提高了收益開銷比.GTCW-VNE算法因為可以根據(jù)網(wǎng)絡環(huán)境的變化利用博弈論組合賦權法綜合主客觀賦權方法的優(yōu)點，對權重向量進行自適應的調整，因此性能始終最優(yōu).

圖4 不同CPU需求時映射成功率

Fig.4 Acceptance ratio for different CPU requirements

圖5 不同CPU需求時長期平均收益開銷比

Fig.5 Long-term average revenue to cost ratio for different CPU requirements

場景2.本組實驗模擬虛擬網(wǎng)絡映射算法在不同帶寬需求下的性能.虛擬鏈路帶寬需求服從[10，p]的均勻分布，p為鏈路帶寬需求分布的上限，節(jié)點CPU需求服從[0，50]的均勻分布.當帶寬需求上限p在[20，30]之間時，層次分析法的判斷矩陣如表4所示，當帶寬需求上限p在[30，40]之間時，層次分析法的判斷矩陣如表3所示.

圖6 不同帶寬需求時映射成功率

Fig.6 Acceptance ratio for different bandwidth requirements

圖7 不同帶寬需求時長期平均收益開銷比

Fig.7 Long-term average revenue to cost ratio for differ-ent bandwidth requirements

從圖6和圖7可以看出，隨著虛擬鏈路帶寬需求的增加，4種映射算法的映射成功率和收益開銷比均有一定的下降，主要是因為隨著帶寬需求的增加而底層網(wǎng)絡帶寬資源的承載能力有限，導致部分鏈路映射開銷過大或者映射失敗.而本文提出的GTCW-VNE算法，因為考慮了更多的節(jié)點拓撲屬性，并且根據(jù)帶寬需求的變化對帶寬資源的權重進行了相應的調整，因此映射效率優(yōu)優(yōu)于其它算法.通過2組實驗可以發(fā)現(xiàn)，虛擬網(wǎng)絡資源需求的改變對算法映射性能有著較大的影響.GTCW-VNE算法因為結合了主觀賦權法和客觀賦權法的優(yōu)勢，避免了其它三種算法的局限性、片面性，因此相比其它算法效果更好.

6 結束語

本文針對節(jié)點多指標排序的虛擬網(wǎng)絡映射算法在指標權重確定中存在的片面性和局限性問題，提出一種博弈論組合賦權的虛擬網(wǎng)絡映射算法.首先提取網(wǎng)絡節(jié)點的各項特征指標，并進行歸一化處理，組成特征指標向量，建立對節(jié)點資源情況的全面掌握，其次引入指標權重向量，利用熵值法和層次分析法構建基本權重向量集，然后利用博弈論組合賦權法，對基本權重向量進行均衡處理，以獲取最優(yōu)權重向量并對節(jié)點進行排序，最后依據(jù)排序結果進行節(jié)點映射，采用k-最短路徑算法進行鏈路映射.仿真結果表明GTCW-VNE算法能夠靈活適應網(wǎng)絡環(huán)境變化，優(yōu)化節(jié)點排序，相比于其他算法提高了虛擬網(wǎng)絡映射成功率和收益開銷比.下一步將結合安全虛擬網(wǎng)絡映射進行研究.