博弈論組合賦權的虛擬網絡映射算法

徐 江，孟相如，韓曉陽，史朝衛

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

1 引 言

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

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

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

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

本文的主要貢獻如下：

a.將虛擬網絡映射建模為一個節點多指標排序的優化問題，指出影響節點排序優劣的主要因素為能否根據映射目標選取合適的節點指標和權重.

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

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

2 虛擬網絡映射模型與評價指標

2.1 網絡映射模型

2.1.1 底層物理網絡

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

2.1.2 虛擬網絡

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

2.1.3 虛擬網絡映射

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

圖1 虛擬網絡映射示例

2.2 評價指標

2.2.1 映射成功率

虛擬網絡的映射成功率可表示為：

(1)

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

2.2.2 收益開銷比

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

(2)

(3)

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

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

(4)

3 算法設計

3.1 節點特征指標提取

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

3.1.1 節點計算資源

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

NCR(ni)=cpu(ni)

(5)

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

3.1.2 節點鄰接帶寬資源

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

(6)

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

3.1.3 節點的度

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

(7)

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

3.1.4 節點就近度

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

(8)

(9)

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

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

(10)

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

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

(11)

3.2 博弈論組合賦權模型

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

3.2.1 基本權重集

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

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

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

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

(12)

其中，m是網絡中節點的數目，a(ni)為節點的特征指標向量.

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

j=1，2…，N

(13)

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

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

(14)

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

3.2.2 可能權重向量集

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

(15)

3.2.3 博弈論組合賦權法

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

(16)

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

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

(17)

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

(18)

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

(19)

4 GTCW-VNE算法實現

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

輸入：Gs，Gv

輸出：NodeEmbeddingList

1. 根據網絡環境運用層次分析法獲取節點指標權重向量

2. for虛擬網絡中每一個虛擬節點nv∈Nv

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

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

9. end for

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

13. do

15. 刪除已經映射的候選節點

17. returnNODE_EMBEDDING_FAILED

18. else

21. end for

23. 更新已映射物理節點集合OSNode

24. end if

25. end for

26. return NODE_EMBEDDING_SUCCESS

5 性能評估與分析

5.1 仿真環境

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

表1 判斷矩陣及指標權值

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

5.2 算法的對比評價

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

表2 算法對比表

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

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

圖2 映射成功率

Fig.2 Acceptance ratio

圖3 長期平均收益開銷比

Fig.3 Long-term average revenue to cost ratio

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

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

表3 判斷矩陣及指標權值

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

表4 判斷矩陣及指標權值

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

圖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.本組實驗模擬虛擬網絡映射算法在不同帶寬需求下的性能.虛擬鏈路帶寬需求服從[10，p]的均勻分布，p為鏈路帶寬需求分布的上限，節點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種映射算法的映射成功率和收益開銷比均有一定的下降，主要是因為隨著帶寬需求的增加而底層網絡帶寬資源的承載能力有限，導致部分鏈路映射開銷過大或者映射失敗.而本文提出的GTCW-VNE算法，因為考慮了更多的節點拓撲屬性，并且根據帶寬需求的變化對帶寬資源的權重進行了相應的調整，因此映射效率優優于其它算法.通過2組實驗可以發現，虛擬網絡資源需求的改變對算法映射性能有著較大的影響.GTCW-VNE算法因為結合了主觀賦權法和客觀賦權法的優勢，避免了其它三種算法的局限性、片面性，因此相比其它算法效果更好.

6 結束語

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