曹　儐,郎文強,李　云

(1.重慶市移動通信重點實驗室，重慶 400065; 2.重慶郵電大學 通信與信息工程學院，重慶 400065)

?

基于最大收益的無線虛擬網(wǎng)絡(luò)重映射算法

曹儐1,2,郎文強1,2,李云1,2

(1.重慶市移動通信重點實驗室，重慶 400065; 2.重慶郵電大學 通信與信息工程學院，重慶 400065)

針對無線環(huán)境的動態(tài)性及虛擬網(wǎng)絡(luò)請求到達與離開的隨機性，使得物理網(wǎng)絡(luò)負載分布不均衡，導致后續(xù)請求的接受率降低的問題，提出一種無線網(wǎng)絡(luò)虛擬化中的兩階段重映射算法(two stages reconfiguration scheme for wireless network virtualization, TR-WNV)。該算法通過第1個階段選出合適的虛擬網(wǎng)絡(luò)進行重映射，接著在第2個階段按照優(yōu)先級對已選出的虛擬網(wǎng)絡(luò)進行重映射，并根據(jù)離散度來判斷每次映射效果。最后，通過仿真對算法進行驗證，結(jié)果表明該算法在保證虛擬網(wǎng)絡(luò)請求收益最大化同時，有效提高了虛擬網(wǎng)絡(luò)請求接受率，實現(xiàn)整個底層網(wǎng)絡(luò)的負載分布均衡。

無線網(wǎng)絡(luò)虛擬化；資源分配；虛擬網(wǎng)絡(luò)重映射

0　引　言

隨著第4代移動通信(4G)進入規(guī)模商用階段，全球通信行業(yè)已經(jīng)全面開啟對面向2020年及未來的第五代移動通信(5G)的探索[1]。更大的網(wǎng)絡(luò)容量、更可靠的傳輸和更快的處理速度成為了5G移動通信網(wǎng)絡(luò)的首要目標。為了更好地順應(yīng)5G的發(fā)展，無線網(wǎng)絡(luò)虛擬化得到廣泛應(yīng)用，具有安全、可擴展性、靈活性等技術(shù)特點[2]。網(wǎng)絡(luò)虛擬化中，虛擬網(wǎng)絡(luò)(virtual network, VN)就是一個基本實體，由多個虛擬節(jié)點和虛擬鏈路形成的虛擬拓撲組成。無線網(wǎng)絡(luò)虛擬化的核心問題之一就是如何簡單地管理控制網(wǎng)絡(luò)，高效分配網(wǎng)絡(luò)資源，從而達到共享底層基礎(chǔ)設(shè)施，提升網(wǎng)絡(luò)性能的目的。

在無線網(wǎng)絡(luò)虛擬化環(huán)境下，如何將VN請求合理映射到資源約束物理網(wǎng)絡(luò)中是一個關(guān)鍵問題。但是，隨著VN請求到達和離開，原先資源分配不再適合當前狀態(tài)；并且隨著時間推移，底層網(wǎng)絡(luò)資源表現(xiàn)出負載不均衡的現(xiàn)象，比如會出現(xiàn)有的底層物理資源利用率高，有的利用率低。因此，如果不考慮虛擬網(wǎng)絡(luò)重映射(virtual network reconfiguration, VNR)將會造成資源空閑，使得SN(substrate network)資源利用率降低[3]。所以通過VNR機制重優(yōu)化資源分配，有利于解決負載均衡問題，具有重要的研究意義。大多數(shù)研究僅僅考慮靜態(tài)VN請求，針對這種靜態(tài)請求設(shè)計高效的分配策略。然而，在實際情況下，分布式計算和在線程序等需要底層物理網(wǎng)絡(luò)資源隨著時間動態(tài)地變化。例如，在分布式計算中，新的工作開始和現(xiàn)有的工作完成，甚至從計算密集型階段到通信密集型階段也會導致VN請求的變更。因此,為了適應(yīng)需求的變化以及動態(tài)的映射，需要對VNR算法進行深入研究。

目前關(guān)于無線網(wǎng)絡(luò)虛擬化下的VNR問題沒有太多研究。而對于有線重配置問題，文獻[4]提出對底層物理鏈路和節(jié)點進行周期性地檢查，并將超過預先設(shè)定閾值的物理節(jié)點或物理鏈路標記出來，包含標記的VN即需要進行重映射。文獻[5]為了減低VNR的拒絕率，研究一種貪婪的VNR算法。對映射到超負載的底層物理節(jié)點或鏈路上典型的星型虛擬拓撲進行重新分配，減少了重映射開銷。文獻[6]設(shè)計出一種基于成本效益的重映射框架和算法，為了適應(yīng)用戶的需要變化，將重映射問題轉(zhuǎn)化為數(shù)學問題，利用混合整數(shù)線性規(guī)劃進行重配置。其目標函數(shù)為最小化VNR成本，在框架里考慮了負載均衡的問題，并盡量避免資源碎片。文獻[7]利用虛擬節(jié)點與鏈路的遷移、交換從而降低重映射的開銷，提高InP收益。文獻[8]的重映射算法只針對關(guān)鍵節(jié)點進行重映射。對關(guān)鍵節(jié)點重映射能夠提高接受率，并且降低重映射時間開銷。而由于無線環(huán)境中存在信道可變性、用戶的移動性、廣播、鏈路間干擾以及多種多樣的接入技術(shù)，所以，使得VNR機制變得復雜。

如果不考慮VNR機制將會導致網(wǎng)絡(luò)資源浪費，并對后續(xù)的VN請求接受率造成影響。因此，通過VNR機制重新優(yōu)化VN資源分配是必要的。本文主要針對以下問題對無線多跳網(wǎng)絡(luò)環(huán)境下的VNR機制進行研究：

1)判斷哪些VN需要進行重映射。在重映射過程中，為了減少重映射開銷以及切換中斷次數(shù)，并不是對多個或全部VN同時進行重映射，只需要選擇恰當?shù)腣N。那么，選擇哪些VN是本文研究的問題。

2)重映射優(yōu)先級問題。當所有重映射請求到達緩沖隊列后，如果按照時間先后順序依次處理，可能會導致排在后面的某個大型VN由于底層網(wǎng)絡(luò)缺少功率或帶寬資源沒有被接受，降低了重映射接受率。所以需要對重映射優(yōu)先級進行定義。

3)如何將重映射請求合理分配到底層無線網(wǎng)絡(luò)中。重映射過程需要根據(jù)底層網(wǎng)絡(luò)負載以及VN的收益分別對虛擬節(jié)點以及鏈路重映射。由于本文是在無線環(huán)境下進行研究，所以在進行重映射的過程中還要考慮干擾以及底層網(wǎng)絡(luò)的動態(tài)性。

本文提出一種無線網(wǎng)絡(luò)虛擬化中的兩階段重映射算法(two stages reconfiguration scheme for wireless network virtualization, TR-WNV)。TR-WNV算法包括2個階段：第1個階段是尋找合適的重映射請求(finding virtual network reconfiguration request, FVNR)，通過此階段解決了上述第1個問題。第2個階段是將重映射請求合理映射到底層無線網(wǎng)絡(luò)中(embedding virtual network reconfiguration request, EVNR)，從而解決問題2和問題3。實驗證明TR-WNV算法不僅提高了VN請求接受率以及收益，同時使得底層無線網(wǎng)絡(luò)負載更加均衡。

1　網(wǎng)絡(luò)模型

1.1VN模型

底層無線網(wǎng)絡(luò)拓撲用帶有權(quán)值的無向圖GS=(NS,ES)表示。其中，NS表示物理節(jié)點集合，ES表示鏈路集合。VN用無向圖GV=(NV,EV)表示，NV，EV分別表示虛擬節(jié)點集合和虛擬鏈路集合。另外，用RS表示物理網(wǎng)絡(luò)中一條物理路徑。

本文考慮的資源包括節(jié)點功率以及鏈路帶寬。對于每個物理節(jié)點nS∈NS，其所能提供的功率大小為p(nS)，單位為W。對于每條物理鏈路eS∈ES，其提供帶寬大小用b(eS)表示，單位為MHz。同理，對于每個虛擬節(jié)點nV∈NV，其所請求的功率大小為p(nV)，而每條虛擬鏈路eV∈EV，所請求的帶寬大小為b(eV)。

本文是在無線網(wǎng)絡(luò)環(huán)境下考慮重映射問題。因此，無線網(wǎng)絡(luò)中的干擾不可忽視。對于一條物理鏈路，本文只考慮相鄰鏈路之間的干擾，定義物理鏈路資源利用率影響因子dI(e)，對于每條物理鏈路有

(1)

(1)式中：λe∈[0,1]為干擾因子，其大小根據(jù)不同場景而設(shè)定；de表示可能產(chǎn)生干擾的相鄰物理鏈路個數(shù)。dI(e)與de成反比，這說明鏈路干擾對資源利用率影響是消極負面的。

1.2VNM(virtual network mapping)模型

本文要求同一個VN中虛擬節(jié)點必須分配到不同物理節(jié)點之上，對于每次無線虛擬網(wǎng)絡(luò)分配過程，能夠描述成從VN請求GV到底層無線網(wǎng)絡(luò)子集GS的映射，表示為M:GV(NV,EV)→GS(N*,R*)，其中,N*?NS,R*?RS，即

1)節(jié)點映射MN:NV→N*。

對于?nV∈NV,MN:nV→nS，需要滿足一定限制條件，即虛擬節(jié)點分配功率資源大小必須低于底層物理節(jié)點可用功率資源大小，在滿足條件同時，VN請求中虛擬節(jié)點距離其目標物理節(jié)點不能超過節(jié)點映射范圍，即

(2)

dis(loc(nV),loc(nS))≤D

(3)

(2)式中，restp(nS)表示底層物理節(jié)點可用功率資源即節(jié)點剩余功率資源。(3)式中，dis(loc(nV),loc(nS))表示虛擬節(jié)點nV到物理節(jié)點nS的距離；D表示VN請求中虛擬節(jié)點的映射半徑[9]。

2)鏈路映射ME:EV→R*。

本文中一條虛擬無線鏈路可以分配到一條或多條底層無線鏈路組成的路徑中。對于?eV∈EV,ME:eV→RS，RS表示映射的物理路徑集合。同理，在虛擬無線鏈路分配過程中也需要滿足限制條件，即虛擬鏈路分配帶寬大小不能大于物理鏈路剩余帶寬，restb(eS)表示物理鏈路的可用帶寬，即

(4)

1.3VNR請求模型

本文用VR(GV)=(NCV,ECV)表示VNR請求，即適合進行重映射的GV。GV中適合重映射虛擬節(jié)點集合用NCV表示，NCV?NV，ECV表示適合重映射虛擬鏈路集合，ECV?EV。對于每個nCV∈NCV，其所請求的功率大小為p(nCV)。同理，每條虛擬鏈路eCV∈ECV，所請求帶寬大小為b(eCV)。本文所涉及的重映射算法只針對GV中需要進行重映射的虛擬節(jié)點或鏈路，不對GV其余虛擬節(jié)點或鏈路進行重映射，這樣大大降低了重映射的開銷[10]。

1.4目標函數(shù)

本文從VN請求收益入手，首先對VN請求收益進行分析，對于一個VN請求GV，定義GV獲得的收益為

(5)

dis(loc(nV),loc(nS))≤D

(6)

2　TR-WNV算法

本文所提出的TR-WNV算法是將最大化VN請求收益作為目標函數(shù)，同時考慮底層無線網(wǎng)絡(luò)負載以及鏈路干擾。TR-WNV算法首先通過FVNR階段在VN中找出合適的重映射請求，從而避免對所有VN進行重映射，提高了重映射請求的效率。接著在EVNR階段，根據(jù)瞬時收益的大小確定優(yōu)先級。再以最大化VN請求收益為目標分別對虛擬節(jié)點以及鏈路進行映射，從而使得底層無線網(wǎng)絡(luò)能夠接受更多VN請求。下面將分別介紹FVNR與EVNR兩個階段。

2.1FVNR階段描述

為了描述整個底層無線網(wǎng)絡(luò)的負載情況，本文引入了數(shù)學中的離散度CV，即標準差除以平均數(shù)。離散度CV能夠表示一組數(shù)列中各個數(shù)據(jù)之間的離散程度，并且無量綱。整個數(shù)列的離散度CV越小，說明數(shù)列中各個數(shù)據(jù)間差異越小[11]。

(7)

(8)

(9)

(10)

(9)-(10)式中：N，M分別表示物理節(jié)點以及鏈路數(shù)量；μNS,μES分別表示整個無線物理節(jié)點功率以及鏈路帶寬的平均資源利用率。

為了選出合適的VR(GV)，借鑒文獻[4]，本文在FVNR階段定義選擇門限系數(shù)θ∈[0,1]。θ是根據(jù)具體場景設(shè)置的。并將承載壓力大的底層物理節(jié)點或鏈路上的VN作為VR(GV)。θ=0意味著負載最大的物理節(jié)點或鏈路承載壓力大；θ=1意味著所有節(jié)點或鏈路都承載壓力大。那么，承載壓力大的底層無線物理節(jié)點或者鏈路可以表示為

(11)

(12)

(12)式中：Nh表示承載壓力大的物理節(jié)點；Eh表示承載壓力大的物理鏈路；Lnmax(nS)表示整個底層無線網(wǎng)絡(luò)中最大物理節(jié)點負載；Lemax(eS)表示最大無線鏈路負載。

為了確定是選擇Nh還是Eh上的VN作為VR(GV)，在FVNR階段比較離散度CVn和CVe。如果CVn>CVe，那么包含Nh的VN即為VR(GV)，反之，包含Eh的VN即為VR(GV)。為了方便理解FVNR階段的過程，加深對離散度的理解，下面舉例說明如何通過FVNR階段找出重映射請求。

圖1　FVNR階段實例Fig.1　Example of FVNR stage

分別計算離散度CVn和CVe，并比較大小。

顯然，CVn

通過上述分析，在FVNR階段通過定義離散度及選擇門限系數(shù)，選出VR(GV)進行重映射，從而減少了重映射個數(shù)，降低了重映射開銷，同時為下一階段準備。

2.2EVNR階段描述

通過FVNR階段，所有VR(GV)進入請求隊列中排隊。接下來，本文將進入EVNR階段對請求隊列中的VR(GV)進行重映射。為了解決優(yōu)先級問題，在EVNR階段首先對請求隊列中多個VR(GV)進行排序。將VR(GV)按照其瞬時收益從大到小排列，并優(yōu)先處理重映射請求收益大的VR(GV)。為了盡量提高VNR質(zhì)量，減少VNR次數(shù)，本文將離散度作為衡量重映射效果參數(shù)。離散度越小說明該次重映射效果越好，越大則說明該次重映射沒有達到目標。

在執(zhí)行重映射階段時，除了滿足資源約束性條件外，還要遵守以下原則：

1)虛擬節(jié)點所分配到的底層物理節(jié)點應(yīng)該在其映射半徑范圍內(nèi)；

2)虛擬節(jié)點不能分配到原來底層物理節(jié)點上；同理，虛擬鏈路也不能分配到原來的物理鏈路上，防止產(chǎn)生不必要的開銷；

3)同一VN中節(jié)點進行重映射，不能重映射到同一個物理節(jié)點上。

本文在重映射過程中定義3個相關(guān)參數(shù)[12]。首先定義虛擬節(jié)點的重映射資源請求量為

(13)

(13)式中，E(nCV)表示與虛擬節(jié)點nCV相連鏈路。PB(nCV)越大，表示該虛擬節(jié)點功率請求量與其相鄰鏈路帶寬請求量越大。定義物理節(jié)點的資源接受能力為

NR(nS)=restp(nS)+∑eS∈E(nS)restb(eS)

(14)

(14)式中，NR(nS)越大，表明該物理節(jié)點和與其相鄰鏈路負載越輕。定義物理鏈路的權(quán)重為

(15)

由于VNM問題不僅要滿足節(jié)點和鏈路多種約束條件，還要滿足其目標函數(shù)。從而使得VNM變得非常復雜。VNM屬于NPhard問題，因此在設(shè)計VNM算法過程中，一般通過簡化問題或放寬約束條件來獲取近似最優(yōu)解。本文在EVNR階段將采用貪婪算法重映射虛擬節(jié)點，再利用最短路徑算法找到映射的物理路徑，將最大化VN請求收益為目標，實現(xiàn)底層無線網(wǎng)絡(luò)的負載均衡。并在節(jié)點映射階段找到最大資源接受能力的物理節(jié)點。在鏈路映射階段同時考慮鏈路間干擾與鏈路負載，將鏈路干擾與鏈路可用資源的比值作為鏈路權(quán)值，采用最短路徑算法找到一條合適的物理路徑。最后計算離散度CVn或CVe值的大小，決定是否繼續(xù)處理請求隊列中剩余的VR(GV)。EVNR階段的基本步驟如下：

第1步將VR(GV)按照其瞬時收益從大到小排列。當?shù)?個VR(GV)到來時，首先根據(jù)虛擬節(jié)點資源請求量，從大到小將虛擬節(jié)點排序。

第2步在上一步確定的每個重映射虛擬節(jié)點映射半徑內(nèi)，找到NR(nS)最大物理節(jié)點。

第3步首先進行虛擬節(jié)點重映射。將第1步選出的虛擬節(jié)點按照順序依次映射到第2步對應(yīng)的NR(nS)最大物理節(jié)點上。

第4步進行虛擬鏈路重映射。先根據(jù)(15)式畫出帶有權(quán)重的底層無線網(wǎng)絡(luò)。然后將虛擬鏈路帶寬請求量從大到小排列，并根據(jù)第3步節(jié)點重映射結(jié)果，依次利用D最短路徑算法進行虛擬鏈路的重映射。

第5步當?shù)?個VR(GV)重映射成功后，繼續(xù)計算離散度CVn或CVe，如果離散度變小說明該次VNR的效果較好，使得網(wǎng)絡(luò)負載更加均衡，則繼續(xù)處理請求隊列里剩余的VR(GV)；如果離散度變大，則說明該次VNR效果不好，則停止EVNR階段，算法結(jié)束。

綜上所述，本文所提出的TR-WNV算法包括2個階段，在FVNR階段找出合適的重映射請求，然后進行EVNR階段，實現(xiàn)VN的重映射，提高了后續(xù)VN請求接受率，達到了使底層網(wǎng)絡(luò)的負載均衡的目的。需要說明的是本文TR-WNV算法是在底層網(wǎng)絡(luò)不支持任何特殊技術(shù)的情況下提出的，因此，TR-WNV算法也降低了InP成本和算法復雜度。

3　性能評估

為了驗證TR-WNV算法優(yōu)越性，本文在MATLAB仿真平臺下設(shè)計2組實驗對其分析評估。實驗1將本文定義選擇門限系數(shù)θ作為橫坐標，觀察VN重配置率及物理節(jié)點離散度的變化，從而選擇出一個合適的θ。實驗2將時間作為橫坐標，在實驗1的基礎(chǔ)上，設(shè)定合適的θ，分別對VN接受率以及VN請求收益進行分析，從而證明算法的有效性和可行性。

實驗場景為：網(wǎng)絡(luò)拓撲由60個物理節(jié)點組成，隨機分布在20×20 km2范圍內(nèi)，并假設(shè)每個虛擬節(jié)點映射半徑為D=500 m。為了簡化實驗將可調(diào)系數(shù)α、干擾因子λe均設(shè)為1。并設(shè)置網(wǎng)絡(luò)參數(shù)γ,η。其中，γ表示節(jié)點間連接與斷開的比例，η表示物理鏈路密度。物理節(jié)點功率為[5,10]，物理鏈路帶寬為[2,5]。VN請求達到數(shù)量服從λ=4的泊松分布，每個VN的生存周期為10個時隙。VN請求的虛擬節(jié)點個數(shù)限制在[3,5]。

由于θ對選擇哪些VN進行重映射有很大影響，所以實驗1計劃通過觀察相關(guān)變量隨著θ的變化趨勢，找到一個合適的θ，使得算法發(fā)揮出最佳效果。在實驗1中，首先觀察VN重配置率隨著θ的變化情況。重配置率即表示需要進行重配置的VN占所有VN的比重。VN重配置率如圖2所示，隨著選擇門限系數(shù)θ不斷增加，VN重配置率逐漸升高。這是因為當θ取值越小時，得到物理節(jié)點或鏈路承載壓力大的幾率就越小，相反，如果θ不斷增加，則被判斷為承載壓力大的物理節(jié)點或鏈路就越多，重配置的VN也就越多。當θ超過0.7后，重配置率逐漸穩(wěn)定，因為幾乎所有的VN都要進行重映射。但是，重映射請求的增多將會增加開銷，所以，重配置率不能太高。

因此，很多媒體和專家，已經(jīng)開始將天然氣管道互聯(lián)互通的效果看作檢驗今冬明春用氣高峰時期天然氣供應(yīng)能力的標準。事實上，天然氣管道互聯(lián)互通工程早有開展。2006年和2013年，中國石油已經(jīng)分別實現(xiàn)了與中國石化華北管網(wǎng)安濟線安平站和榆濟線榆林站的互聯(lián)互通，互供能力分別為300萬立方米/日和400萬立方米/日。

圖2　VN重配置率Fig.2　Reconfiguration rate of VN

本文中物理節(jié)點離散度和物理鏈路離散度是2個非常重要的參數(shù)，不僅在FVNR階段中作為判斷VN是否重映射的依據(jù)，還在EVNR階段衡量重映射的效果。θ的大小會對物理節(jié)點與鏈路的離散度產(chǎn)生影響。圖3表示θ與執(zhí)行TR-WNV算法之后的物理節(jié)點離散度的關(guān)系。由于本文在考慮收益的同時，還考慮了節(jié)點與鏈路的負載情況，所以每經(jīng)過一次重映射都會降低離散度。但是當θ大于0.7后，可能映射在底層網(wǎng)絡(luò)中所有VN都要進行重映射，所以本文中節(jié)點離散度最后會穩(wěn)定在一個值上。

從上述分析可以看出，θ在0.4至0.5之間時，重映射配置率明顯升高。而當θ大于0.5后，物理節(jié)點的離散度也趨于穩(wěn)定。所以，當θ在0.4至0.5之間時各個變量均處在比較合適的值?；诖?，本文將0.45作為實驗2的θ。

本文是在無線網(wǎng)絡(luò)虛擬化環(huán)境下研究VNR問題，但是目前的研究都是針對無線環(huán)境下的VNM問題[12-14]。為了體現(xiàn)TR-WNV算法的優(yōu)越性，在實驗2中將TR-WNV算法與WEM算法[12]相比較。整個仿真時間持續(xù)100個時隙。VN 請求到達數(shù)量隨著時間的變化情況如圖4所示。由于VN請求到達服從泊松分布，并且每個VN請求的生存周期為10個時隙，因此，隨著時間的增加，VN請求數(shù)量逐漸穩(wěn)定在45個。

圖4　VN請求到達數(shù)量Fig.4　Request arrives quantity of VN

圖5表示VN請求接受率隨時間的變化情況。在剛開始的一段時間內(nèi)，由于底層物理節(jié)點與鏈路的負載輕，VN請求接受率會很高，但是隨著時間的增加，VN請求越來越多，底層物理節(jié)點與鏈路的負載增加，導致請求接受率逐漸下降。隨著時間的推移，VN請求到達的數(shù)量逐漸穩(wěn)定，所以VN請求接受率也逐漸穩(wěn)定。由于TR-WNV算法考慮重映射機制，首先選出合適的重映射請求，再對瞬時收益大的VN請求映射，并且在虛擬節(jié)點與鏈路映射的過程中均考慮底層物理網(wǎng)絡(luò)的負載，所以VN請求接受率要高于WEM算法。

圖5　VN請求接受率Fig.5　Request acceptance rate of VN

圖6表示VN請求收益隨時間的變化情況。由于剛開始VN請求接受率較高，并且生命周期還沒有結(jié)束，所以，VN請求收益逐漸增加。隨著時間的推移，VN請求到達的數(shù)量趨于穩(wěn)定，同時底層資源也達到瓶頸，收益逐漸穩(wěn)定。通過執(zhí)行TR-WNV算法提高了VN請求接受率，VN收益也會增加。因此VN請求收益要高于WEM算法。

圖6　VN請求收益Fig.6　Request benefit of VN

4　總　結(jié)

針對底層無線網(wǎng)絡(luò)的動態(tài)變化而導致的VN請求接受率降低的問題，本文提出一種無線網(wǎng)絡(luò)虛擬化中的兩階段重映射算法TR-WNV，該算法包括FVNR階段與EVNR階段。TR-WNV算法首先通過FVNR階段，找到了需要進行重映射的VN，選擇合適的VN進行重映射，減少了重映射開銷，提高了重映射效率。接著進行EVNR階段，通過在重映射請求隊列中設(shè)置優(yōu)先級，并根據(jù)最大化VN請求收益為目標解決了虛擬節(jié)點與鏈路重映射問題。從而提高了VN請求接受率以及收益，實現(xiàn)底層無線網(wǎng)絡(luò)負載分布均衡。最后，通過仿真實驗，證明了TR-WNV算法的正確性和有效性。

[1]METIS. Mobile and wireless communications enablers for the 2020 information society[EB/OL]. [2015- 04- 03]. https://www.metis2020.com.

[2]WANG Xin, KRISHNAMURTHY P, TIPPER D. Wireless network virtualization[C]//2013 International Conference on Computing, Networking and Communications (ICNC). San Diego, CA: IEEE Press, 2013: 818-822.

[3]JONATHAN van de Belt, AHMADI H, DOYLE L E. A Dynamic Embedding Algorithm for Wireless Network Virtualization[J]. IEEE Vehicular Technology Conference, 2014, 88(4):1- 6.

[4]ZHU Yong, AMMAR M. Algorithms for assigning substrate network resources to virtual network components[C]//2006 In Proceedings of the 25th IEEE International Conference on Computer Communication (INFOCOM). Barcelona, Spain: IEEE Press, 2006: 1-12.

[5]FAJJARI I, AITSAADI N, PUJOLLE G. VNR algorithm：A greedy approach for virtual networks reconfigurations[C]//2011 IEEE Global Communications Conference(GLOBECOM). Houston, USA: IEEE Press, 2011: 1- 6.

[6]SUN G, YU H, ANAND V, et al. A cost efficient framework and algorithm for embedding dynamic virtual network requests[J]. Future Generation Computer Systems, 2013, 29(5):1265-1277.

[7]XU L, TAN G, ZHANG X. A cost sensitive approach for Virtual Network reconfiguration[C]// Computing, Communications and It Applications Conference. [S.l.]: IEEE, 2015.

[8]CHEN Dongdong, QIU Xuesong, QU Zhaowei, et al. Algorithm for virtual nodes reconfiguration on network virtualization[C]//2011 International Conference on Advanced Intelligence and Awareness Internet (AIAI). Shenzhen: IET Press, 2011:333-337.

[9]CHOWDHURY N M M K, RAHMAN M R, BOUTABA R. Virtual network embedding with coordinated node and link mapping[C]//2009 In Proceedings IEEE International Conference on Computer Communication (INFOCOM). Rio de Janeiro: IEEE Press, 2009: 783-791.

[10] 曲樺, 趙季紅, 郭爽樂,等. 基于最小代價的虛擬網(wǎng)絡(luò)重配置方法[J]. 北京郵電大學學報, 2014, 37(5): 114-118.

QU Hua, ZHAO Ji Hong, GUO Shuangle, et al. Resource Reconfiguration Method Based on Minimum Cost for Network Virtualization.[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(5): 114-118.

[11] 王文森. 變異系數(shù)：一個衡量離散程度簡單而有用的統(tǒng)計指標[J]. 中國統(tǒng)計, 2007(6): 41- 42.

WANG Wensen. The coefficient of variation: A simple and useful measure of the degree of dispersion of statistical indicators[J]. China Statistics, 2007(6): 41- 42.

[12] YUN D, OK J, SHIN B, et al. Embedding of virtual network requests over static wireless multihop networks[J]. Computer Networks, 2013, 57(5): 1139-1152.

[13] YANG Mao, LI Yong, ZENG Lieguang, et al. Karnaugh-map like online embedding algorithm of wireless virtualization[C]//2012 15th International Symposium on Wireless Personal Multimedia Communications (WPMC). Taipei: IEEE Press, 2012: 594-598.

[14] JONATHAN V D B, AHMADI H, DOYLE L E. A dynamic embedding algorithm for wireless network virtualization[C]//2014 Vehicular Technology Conference (VTC Fall). Vancouver, BC: IEEE Press, 2014:1- 6.

曹儐(1983-)， 重慶人，講師，博士，主要研究方向為網(wǎng)絡(luò)虛擬化、軟件定義網(wǎng)絡(luò)、資源管理和網(wǎng)絡(luò)協(xié)議設(shè)計及性能分析。 E-mail: Caobin65@163.com。

郎文強(1992-)，安徽阜陽人，碩士研究生，主要研究方向為無線網(wǎng)絡(luò)虛擬化。E-mail: 1191481477@qq.com。

李云(1974-)，四川西充人，教授，博士，主要研究方向為無線通信，軟件定義網(wǎng)絡(luò)。E-mail: liyun@cqupt.edu.cn。

(編輯：魏琴芳)

s：The Science Research Project of Chongqing University of Posts and Telecommunications for Young Scholars(A2014-92, A2014-94)

Virtual network reconfiguration in wireless network virtualization based on maximum revenue

CAO Bin1,2, LANG Wenqiang1,2, LI Yun1,2

(1.Chongqing Key Lab of Mobile Communications Technology, Chongqing 400065, P.R. China;2.School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China)

Due to the dynamic nature of the wireless environment, coupled with the random of the virtual network request arrival or departure, the load distribution of the physical network is not balanced and the acceptance rate of the subsequent request would be reduced. Based on this, two stages reconfiguration scheme for wireless network virtualization is proposed, called TR-WNV. The algorithm through the first stage selects the appropriate virtual network to map. Then, the selected virtual networks with the high priority are managed and following the discrete degree to judge each mapping. Finally, the simulation shows the algorithm improves the acceptance rate and benefit of request as well as achieving the load balance of substrate network.

wireless network virtualization; resource allocation; virtual network reconfiguration

10.3979/j.issn.1673-825X.2016.05.003

2016-05-31

2016-09-18通訊作者：曹儐caobin65@163.com

重慶郵電大學青年科學研究項目(A2014-92, A2014-94)

TN92

A

1673-825X(2016)05-0620-08