卜旭陽,楊龍祥

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

基于資源再分配的無線虛擬網絡映射算法

卜旭陽,楊龍祥

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

針對具有Online特性的無線虛擬網絡映射問題，文中提出了一種基于資源再分配的動態無線網絡映射算法。該算法通過映射請求排序和資源空間再分配，來實現對于VNR的動態映射，其中資源空間的再分配是基于卡諾圖的。該算法的主要目的在于盡可能大地增加底層資源的利用率，同時最大化底層資源提供商的收益。文中將靜態映射算法與動態映射算法進行仿真比較，結果顯示動態映射算法在映射拒絕率和收益方面均優于靜態算法。同時，還比較了不同的參數，例如VNR的到達速率、持續時間等對于拒絕率和收益的影響。結果表明，到達速率與持續時間對拒絕率影響較大而對收益影響較小。

動態；資源再分配；卡諾圖；拒絕率；收益

0 引 言

隨著現代通信與網絡互聯技術的飛速發展，無線網絡已逐漸成為未來Internet的一種重要接入形式，而網絡虛擬化是實現未來網絡的關鍵技術之一。網絡虛擬化使得多個異構網絡能共享同一個底層物理網絡。在網絡虛擬化技術中，最核心的問題就是如何將虛擬網絡映射到物理網絡上，一般稱之為VNE(Virtual Network Embedding)問題。VNE問題需要同時處理虛擬節點映射和虛擬鏈路映射。由于資源約束、準入控制和拓撲多樣等因素的影響，VNE問題是NP難的。目前對于VNE算法已經存在一些研究，可將其分為三類：動態/靜態、分布式/集中式和冗余式/精簡式[1]。而算法的衡量標準則有服務質量、開銷、收益等。

目前移動網絡的發展越來越受移動網絡流量的限制，但運營商從移動網絡中可獲得的收益卻越來越大，因此新的技術也就呼之欲出。而無線虛擬網絡映射，就是其中一種很好的方法。無線網絡在現存網絡的地位日益重要。無線網絡虛擬化作為實現未來無線網絡的重要技術，擁有很大的研究價值。無線網絡與有線網絡的主要區別在于無線資源的局限性和無線鏈路的廣播性[2]，兩個因素之間是相互聯系的。一般避免干擾的方法是把無線資源(如頻率、時間、空間等)進行正交劃分，目前主要有FDM、TDM、CDM等方法。文獻[3-4]采用了TDM，文獻[5]采用了FDM，文獻[6-7]采用了CDM。

無線網絡環境錯綜復雜，不同無線環境下的網絡虛擬化研究也成為了研究者關注的重點，文獻[8-9]是關于無線網格網中的虛擬映射，文獻[10]是關于蜂窩網中的虛擬映射，而文獻[11]則描述了無線多跳情況的虛擬映射，文獻[12]研究了WiMax底層網絡的虛擬化。

但是與有線網絡的虛擬化相比，目前針對無線網絡虛擬化的研究還較少。文中主要研究基于資源再分配的動態無線虛擬網絡映射算法，核心思想在于對VNR(Virtual Network Request)進行最優的資源再分配，其過程主要包括兩步：

(1)對于未映射的VNR按照規則進行排序;

(2)采用卡諾映射算法對VNR及資源空間進行再分配。

該研究的主要目的在于盡量減小VNR的拒絕率并且最大化底層資源提供商(Infrastructure Provider,InP)的收益。

1 系統模型和問題定義

1.1 Online-VNE系統模型

一般來說，VNR的到達是具有Online特性的，其到達狀況一般服從泊松分布。新到達的VNR先放入VNR隊列，當某個時間窗結束時，VNR隊列中的VNR將會重新排序，該VNR隊列含有兩種VNR：在最近的時間窗到達的VNR和之前被拒絕映射的VNR[13]。如果一個VNR在某個時間窗內未能被成功映射，那么該VNR將被推入VNR隊列并且在下一個時間窗再次嘗試映射。該過程不斷循環，當某個VNR在規定時間內仍未被映射，就將該VNR從隊列中刪除。

對VNR隊列進行排序有一定的規則，其目的在于盡可能多地獲取收益。VNR的優先級越高，單位資源空間收費就越高，收益也越高。而VNR所需資源區域越大，則從該VNR處可獲得的收益也越大。

文中VNR的排序規則為：首先將VNR按照優先級進行排序，優先級高的靠前。優先級相同時，再按照其占用的資源區域大小進行排序，占用區域大的排在前面。在對VNR的排序完成后，下一步就是對VNR進行映射，在映射時，將使用基于卡諾圖的動態映射算法進行資源再分配。

1.2 條件描述

在無線網絡中，最重要的資源就是頻域和時域資源。不妨以FR和TR分別代表正交的頻道和時隙個數，每個VNR擁有四個要素：需要的頻道數Fj和時隙數Tj、生命周期Cj、優先級Pj。

(1)

其約束條件為：

j≤M

(2)

?j,Fj≤FR,Tj≤TR

(3)

(4)

(5)

(6)

2 卡諾映射算法

在靜態算法中，即使底層資源足夠，VNR也有可能被拒絕，其過程如圖1所示。

在圖1中，總資源空間大小為6×4，在某個時刻分布著A,B,C三個VN。請求D所需的資源空間為3×3，可用的連續空間大小不足以映射D，然而總的可用空間其實是足夠的。但在靜態算法中，系統無法對VNR和資源進行再分配，因請求D還是會被拒絕。

靜態算法的這一特點將會導致資源的極大浪費。但在動態算法中，系統會對資源進行再分配，以獲得盡量多的連續資源空間，其過程如圖2所示。

圖2 動態VNE算法示意圖

資源再分配采用卡諾映射算法。這種算法是適用于動態情況的。該算法的核心思想是提高已用資源的集聚度以保證可用資源的連續性，以獲得最大的連續可用空間。該算法將嘗試映射盡可能多的VNR。

對于每個VNR而言，卡諾映射算法將會在可用資源空間中找出與VNR需求相同或者更大的連續空間，這樣的連續空間可能有多個，選取其中最小的一塊空間。在這塊空間中，系統使用映射密度指數(EmbeddingDestinyIndex,EDI)來標記各個角落的資源集聚度。EDI使用可用空間與已用空間之間邊界的條數來衡量。因而，資源集聚度越高，則EDI指數越低。系統將VN映射到EDI最低的角落，以此提高資源集聚度，提高資源利用率。EDI的具體定義如下所述。

使用am,n∈{0,1}來表示單位資源使用情況，am,n=0表示該塊資源可用，am,n=1表示該塊資源已用[14]。以em,n來表示EDI，則其計算方法如式(7)：

em,n=(am-1,n⊕am,n)+(am+1,n⊕am,n)+ (am,n-1⊕am,n)+(am,n+1⊕am,n)

(7)

那么某個包含多個單位資源塊的區域EDI就為：

(8)

接下來介紹卡諾映射算法的具體步驟：

(7)將Nj映射到選中的映射地。

(8)之后j=j+1，回到步驟2。

3 仿真與分析

3.1 靜態映射算法和動態映射算法的仿真與比較

衡量卡諾算法的首要指標就是收益。緊接收益的指標則是映射拒絕率。

文中以一個速率為λ的泊松過程來表示Online-VNR的到達，其中λ為每個時間窗內到達的VNR的平均個數。而每個VNR的持續時間則服從參數為μ的指數分布，即每個VNR在資源中停留的平均時間為μ個時間窗。圖3和圖4中取λ=4,μ=10。優先級服從U(1,3)的均勻分布，單位資源塊的收益pj與使用該資源的VNR的優先級有關，高優先級收益為5，中優先級為3，低優先級為1。每個VNR所需的資源個數在頻域和時域上都服從U(2,4)的均勻分布。整個資源區域內頻道數FR=15，時隙數TR=15。

定義某個時間窗Wi拒絕率Rei為:

(9)

單位資源在單位時間窗內獲得的平均收益Pi為：

(10)

圖3 靜態與動態映射算法的拒絕率

圖4 靜態與動態映射算法的收益

從圖3和圖4中可以看出，動態算法的拒絕率明顯低于靜態算法，在開始階段，整個拒絕率波動較大，但隨著時間的推移，整個拒絕率會趨向穩定，這與VNR隊列的相對穩定有關。動態拒絕率較靜態拒絕率低了50%左右，收益則較靜態算法高出23%左右。總體來說，在系統趨于平穩的過程中，拒絕率降低明顯，而InP的增收則相對較小。

3.2 動態映射算法在不同參數下的拒絕率與收益

仿真參數不同時，動態算法的拒絕率和收益是不同的，如當到達速率加快時，顯然拒絕率是會上升。圖5顯示了到達率和持續時間對于拒絕率的影響。

從圖5中可以看出，到達速率越快，則拒絕率越高。每個VN持續時間越長，則拒絕率也會越高，當μ=10時，λ=4的拒絕率較λ=10降低了45%左右；λ=4時，μ=10較μ=50的拒絕率低了62%左右。一般來說，到達速率和持續時間是難以準確估計的，但是服務提供商可以根據不同網絡的特征進行大致的估算。

圖5 不同參數情況下動態算法的拒絕率

從圖4和圖6的比較中可以看出，到達速率和持續時間對于收益的影響相對較小，這是因為VNR的優先級和請求的資源區域大小服從均勻分布，當經過較長的時間后，VNR隊列中的請求、拒絕率以及整個資源區域的分配情況就相對穩定，那么收益的差異也就相對較小。但是如果參數相差太大，也會產生比較顯著的差異。

圖6 不同參數情況下動態算法的收益

4 結束語

文中采用了Online-VNE模型，主要討論了基于卡諾圖的動態無線虛擬網絡映射的算法。該算法主要著力于研究時域和頻域資源的再分配問題。通過對VNR的排序和動態的資源再分配，VNE的拒絕率相對靜態算法將會大幅度下降，而InP的收益也將有所提升。文中還探討了不同參數對于動態算法的拒絕率和收益的影響程度，得出VNR的到達速率和持續時間與拒絕率呈正相關，且相關程度大，而對收益影響較小的結論。該算法要求服務商要對收益和大請求有著精確的預測，收益與計算優先級所需的開銷有關，優先級上的開銷影響著該優先級上VNR的接受數量。

未來的研究將主要探討如何使得該算法真正實用于無線網絡中。另外，目前對于鏈路虛擬化的研究還相對較少，并且相對有限，未來在鏈路虛擬化研究方面還大有文章可做。

[1]FischerA,BoteroJF,TillBM,etal.Virtualnetworkembedding:asurvey[J].IEEECommunicationsSurveys&Tutorials,2013,15(4):1888-1906.

[2]ChowdhuryM,RahmanMR,BoutabaR.ViNEYard:virtualnetworkembeddingalgorithmswithcoordinatednodeandlinkmapping[J].IEEE/ACMTransactionsonNetworking,2012,20(1):206-219.

[3]SmithG,ChaturvediA,MishraA,etal.Wirelessvirtualizationoncommodity802.11hardware[C]//ProcofsecondACMinternationalworkshoponwirelessnetworktestbeds,experimentalevaluationandcharacterization.[s.l.]:ACM,2007:75-82.

[4]PerezS,CaberoJM,MiguelE.Virtualizationofthewirelessmedium:asimulation-basedstudy[C]//Procofvehiculartechnologyconference.Barcelona:IEEE,2009:1-5.

[5]SinghalS,HadjichristofiG,SeskarI,etal.EvaluationofUMLbasedwirelessnetworkvirtualization[C]//ProcofNGI.[s.l.]:[s.n.],2008:223-230.

[6]JayasumanaAP,HanQ,IllangasekareTH.Virtualsensornetworks-aresourceefficientapproachforconcurrentapplications[C]//Procofinternationalconferenceoninformationtechnology.Washington,DC,USA:IEEEComputerSociety,2007:111-115.

[7]MahindraR,BhanageG,HadjichristofiG,etal.Spaceversustimeseparationforwirelessvirtualizationonanindoorgrid[C]//ProcofNGI.[s.l.]:[s.n.],2008:215-222.

[8]BhanageGD,ZhangYanyong,RaychaudhuriD.Virtualwirelessnetworkmapping:anapproachtohousingMVNOsonwirelessmeshes[C]//ProcofPIMRC.[s.l.]:IEEE,2011:187-191.

[9]StasiGD,AvalloneS,CanonicoR.Virtualnetworkembeddinginwirelessmeshnetworksthroughreconfigurationofchannels[C]//Procof2013IEEE9thinternationalconferenceonwirelessandmobilecomputing,networkingandcommunications.[s.l.]:IEEE,2013:537-544.

[10]KokkuR,MahindraR,ZhangH,etal.NVS:asubstrateforvirtualizingwirelessresourcesincellularnetworks[J].IEEE/ACMTransactionsonNetworking,2012,20(5):1333-1346.

[11]YunD,YiY.Virtualnetworkembeddinginwirelessmultihopnetworks[C]//Proceedingsofthe6thinternationalconferenceonfutureinternettechnologies.[s.l.]:ACM,2011:30-33.

[12]KokkuR,MahindraR,ZhangH,etal.NVS:avirtualizationsubstrateforWiMAXnetworks[C]//Procof16thannualconferenceonmobilecomputingandnetworkingunitedstates:associationforcomputingmachinery.Chicago,IL,USA:[s.n.],2010:233-244.

[13] 羅 娟,劉川川,李仁發.基于鏈路可靠性的無線虛擬網絡分配方法[J].通信學報,2012,33(S1):88-95.

[14]YangM,LiY,ZengL,etal.Karnaugh-maplikeonlineembeddingalgorithmofwirelessvirtualization[C]//ProcofWPMC.[s.l.]:IEEE,2012:594-598.

A Wireless Network Virtualization Algorithm Based on Resource Reconfiguration Embedding

BU Xu-yang,YANG Long-xiang

(College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

A dynamic algorithm based on resource reconfiguration to solve the VNE problem with online feature was put forward.This algorithm realizes dynamic embedding through VNR sort and resource reconfiguration,and the reconfiguration is based on Karnaugh-map.The object of this algorithm is to maximize the utility rate of resource and revenue of InP.Compared dynamic algorithm with static algorithm,the simulation result shows that the dynamic algorithm performs better than static algorithm in both rejection rate and revenue.Meanwhile,compare and analyze how parameters,such as arriving rate and duration of VNR,influence rejection rate and revenue.The simulation result shows that arriving rate and duration influence more on reject rate than revenue.

dynamic;resource reconfiguration;Karnaugh-map;rejection rate;revenue

2015-05-07

2015-08-11

時間：2016-01-26

國家“973”重點基礎研究發展計劃項目(2013CB329104)作者簡介：卜旭陽(1991-)，男，碩士，研究方向為移動通信與無線技術;楊龍祥,教授,博士生導師，研究方向為移動無線通信系統和物聯網。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1520.034.html

TP301.6

A

1673-629X(2016)02-0039-04

10.3969/j.issn.1673-629X.2016.02.009