無線環境下的虛擬網絡映射算法研究

姜 鑫，楊龍祥，吳夢婷

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

無線環境下的虛擬網絡映射算法研究

姜 鑫，楊龍祥，吳夢婷

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

隨著網絡用戶及用戶對業務需求的爆炸式增長，現有網絡的發展已經很難適應用戶日益增長的各種需求。對此，提出了網絡虛擬化技術。在虛擬化過程中，一個重要的問題就是，如何高效、可靠地將虛擬網絡的虛擬節點和虛擬鏈路映射到底層的物理網絡上，也就是虛擬網絡映射(Virtual Network Embedding,VNE)問題。VNE問題本身就是一個NP難題，而在無線網絡中，由于無線網絡固有的特性，例如鏈路的廣播特性、節點移動性等，使得無線環境下的VNE問題變得更加復雜和困難。對VNE的映射指標和解決策略進行了介紹，重點討論了無線環境下的VNE算法，在按照其所對應的無線網絡特性進行分類與討論的基礎上，對各類方法進行了對比分析，得出針對無線鏈路干擾和節點移動性問題處理的方法以及優缺點，據此指出了未來的研究方向。

無線虛擬化；虛擬網絡映射；NP難題；最優化；資源分配

0 引 言

經過幾十年的發展，互聯網已被廣泛地應用于各個領域，從根本上影響著人們的生活方式，對于社會的發展起到了至關重要的作用。但是隨著互聯網用戶以及用戶對各種業務需求的爆炸式增長，使得現有的傳統互聯網模式已經很難滿足未來網絡的發展需求。針對互聯網的發展問題，現已提出了很多種新的協議和技術，其中網絡虛擬化被認為是解決現有網絡發展問題的重要方法。

網絡虛擬化技術使得多種異構網絡架構能夠在同一物理網絡上共存，且互不干擾，在不改變物理網絡的前提下，能夠為用戶提供端到端的個性化服務，使得在有限的硬件物理架構條件下獲得的收益最大化。在虛擬化技術中，最基本的就是虛擬網絡(Virtual Network,VN)。VN是由一系列的虛擬鏈路相連接的虛擬節點形成的拓撲，通過將底層物理網絡(Substrate Network,SN)的資源進行虛擬化，使得多個具有不同特性的VN能夠在同一SN上并存。

虛擬化過程中的一個重要問題就是將虛擬網絡映射到物理網絡上，也就是虛擬網絡映射(Virtual Network Embedding,VNE)問題，通過將虛擬資源映射到現有的物理硬件資源上，以最大化物理網絡提供商的收益。VNE解決的是虛擬節點和虛擬鏈路的映射問題，因此，可以被分成兩個子問題：虛擬節點映射(Virtual Node Mapping,VNoM)和虛擬鏈路映射(Virtual Link Mapping,VLiM)。

針對無線環境下的虛擬網絡映射問題，介紹了VNE的映射指標和解決策略，重點討論了無線環境下的VNE算法，在按照其所對應的無線網絡特性進行分類與討論的基礎上，對各類方法進行了對比分析，描述了現階段的研究進展及成果，指出了未來的研究方向。

1 虛擬網絡映射

1.1 VNE問題模型

VNE問題是一個在滿足約束條件下的圖匹配問題，所以網絡模型可以用無向圖或者有向圖來表示。

物理網絡：可以用圖GS=(NS,LS)表示，其中，NS表示物理節點的集合，LS表示物理鏈路的集合。

虛擬網絡：可以用圖GV=(NV,LV)表示，其中，NV表示虛擬節點的集合，LV表示虛擬鏈路的集合。

通常，為了保證網絡的負載平衡，同一個VN中的不同虛擬節點會映射到不同的物理節點，尤其在虛擬節點沒有位置要求的情況下，這就顯得尤為重要。

1.2 映射指標

VNE的主要目的在于，在物理資源有限的條件下，充分利用物理資源，來為更多的虛擬網絡提供服務，從而使底層物理網絡運營商的收益最大化。所以最常用的評價指標有三個：長期平均收益R、VN請求接受率γ以及長期收益成本比R/C。

(1)長期平均收益R。

假設已接受的一個VN請求GV產生的收益表示為：

(1)

其中，常量α和β是權重因子，用來調節節點和鏈路資源的相對重要性，由運營商確定。

(2)VN請求接受率γ。

用GV(t)表示在時隙t內到達的VN的集合，則VN接受率為：

(3)長期收益成本比R/C。

假設成功映射一個VN請求GV的成本為：

(2)

R/C的取值范圍在0到1之間，如果這個值太小，表示映射的路徑產生的跳數太多，對底層資源的消耗大，但如果太大，表示VN的映射范圍比較集中，此時網絡的負載均衡性能會比較差。

1.3 最優化策略

VNE問題是NP難問題，因此，對于大規模網絡幾乎不可能在一定的時間內得出最優解。據此，有了三種不同的解決方案：精確解法、啟發式解法和元啟發式解法。

1.3.1 精確解法

可通過線性規劃(Linear Programming,LP)的方法得到最優精確解。更具體地說是整數線性規劃(Integer Linear Programming,ILP)。雖然在很多實用場景下ILP是NP難問題，但在小規模網絡中還是可能在一定時間內求解出來的，通常需要借助一些軟件工具來進行求解，例如GLPK。同時此精確解還可以作為啟發式解法的優化邊界使用。

1.3.2 啟發式解法

在VNE中，執行時間是很重要的。網絡虛擬化解決了在線動態情況的問題，也就是說即使無法提前知曉VNR的到達時間，也可解決。因此，為了避免對新到達VNR映射的延遲，VNE算法的執行時間要盡量小。所以提出了基于啟發式算法的VNE方法，該算法并不是為了求出全局最優解，而是為了保證在較短的執行時間內找出較好的映射方案，當然這樣很有可能得出的是遠離全局最優解的局部最優解。

1.3.3 元啟發式解法

VNE問題可以看作是組合型最優化問題，也就是在一個離散的搜尋空間中尋找一個最優解決方案。因為在大規模實例中難以找到最優化方案，可采用元啟發式算法，例如模擬退火法、遺傳算法、蟻群算法、顆粒群最優化算法、禁忌搜索法等，這些方法通常都是根據一定的目標參數來改善候選方案，從而找出近似最優解。

2 無線環境下的虛擬網絡映射

虛擬網絡映射的問題，現在已有大量的研究，學術界也提出了很多算法用于解決此問題。Fischer等[1]對于現有的大部分算法做了總結概括，并從三個不同方面對其中的算法做了分類，靜態與動態，集中式與分布式，精簡和冗余。

現在大部分的研究還是集中在有線網絡環境下，而無線網絡是現在一種常用的網絡形式，因此無線場景的虛擬化技術也是非常迫切需要解決的。但是因為無線網絡獨有的特性，例如：鏈路干擾、節點移動性等問題，使得無線環境下的虛擬網絡映射問題變得更加復雜，所以需要新的架構和算法來解決無線環境下的VNE問題。對現有的無線環境下的虛擬網絡映射算法，根據其所針對的無線特性問題及解決方法做了如下分類，見圖1。

圖1 無線虛擬網絡映射方法分類

2.1 解決鏈路干擾問題的無線VNE

有線網絡的鏈路本身就具有一定的獨立性，鏈路之間沒有干擾，但是無線網絡的鏈路具有廣播特性，互相之間很容易產生干擾，所以無線網絡虛擬化的主要難點也在于如何虛擬化無線鏈路。

虛擬化無線鏈路的基本思想是將無線資源進行正交劃分，使其具有相對的獨立性，從而避免相互間的干擾。劉川川等[2-3]針對無線網絡鏈路可靠性低的特點，提出了一種分配算法。該算法對物理網絡進行預處理，并允許同一VN中的不同虛擬節點映射到同一物理節點上，減少了無線鏈路干擾的影響，并且大大提高了物理網絡的利用率，而且考慮了鏈路的可靠性進行映射，改善了服務質量，但也使得物理網絡局部節點和鏈路的負載較大，致使網絡的負載均衡性能變差。文獻[4-6]中對于無線資源的虛擬化，提出了通過空分復用(Space Division Multiplexing,SDM)、頻分復用(Frequency Division Multiplexing,FDM)、時分復用(Time Division Multiplexing,TDM)或者混合使用等方法，對無線資源在不同通信維度上進行正交劃分，從而避免干擾。文獻[7-9]中就應用了這種思想進行了無線資源的劃分。文獻[7]提出一種對于無線單跳蜂窩網絡的虛擬化方法—NVS，通過切割分離和流調度機制，提供了在蜂窩網絡中分配無線資源的一種高效方法。文獻[8-9]借鑒文獻[10-11]，將VN請求的資源模型化為矩形塊，同時也將物理資源在頻域和時域進行切割，提出了具體的資源分配算法，充分利用碎片資源，大大提高了物理資源的利用率。

2.1.1 利用SDM的無線VNE

這是一種最簡單的方式，任何無線傳播都是在一定的物理范圍內的，此范圍與很多因素有關，例如發送功率、信道特性等，以此來保證相互之間的獨立性。文獻[12]提出一種在ORBIT場景下的SDMA方法，通過對物理網絡的物理空間上的分割以及對節點發送功率的控制，來達到無線資源的獨立性，避免干擾。SDM雖然實現簡單，但是物理資源利用率比較低。此方法適用于節點密度低的網絡，Jayasumana等[13]就在傳感網絡的實用場景下使用了SDM。

2.1.2 利用TDM的無線VNE

將時間劃分為不相交的時隙，為無線物理鏈路按一定的規則分配時隙，并讓無線鏈路在相應的時隙內激活，從而達到避免干擾的目的。

文獻[14-15]首次為無線多跳網絡提出了VNE方法，利用無線物理鏈路的干擾矩陣，引入了一個沖突圖(conflict graph)的概念。此圖中，一條鏈路變為一個節點，如果兩條鏈路互相干擾就在此圖中將其連接，并對鏈路設置了一個參數作為權重，因此可量化任意兩條鏈路之間的干擾關系，再據此圖確定不同鏈路的激活時隙，從而避免干擾。同時還總結到，大部分映射算法遵循這樣的架構：

(1)選出某種可行的映射方法；

(2)根據某種目標來對此映射進行評估，例如用來映射的資源數量；

(3)重復(1)、(2)直到尋找到最好的映射方式。

算法的核心思想是檢查映射的可行性，評估映射的性能，選擇最優的進行映射，但是這些步驟在無線環境中是很難實施的，因為實際分配到某條鏈路上的資源會對鄰間鏈路上的實際剩余資源產生影響。所以提出了一種新的可行性檢測方法，同時，提出了一種新的度量參數。此參數考慮到了無線鏈路的干擾特性，重新量化了映射方案的優劣。算法首先對虛擬節點和物理節點進行排序，選出前K個物理節點作為根節點進行映射，由此產生K個候選映射方案，映射過程中，每映射一個節點的同時，根據此節點與已映射節點之間路徑的最短加權距離，來確定虛擬鏈路的映射。最后評估K個候選方案的性能來確定最終的映射方案。此算法有效地解決了無線鏈路的干擾問題，但是對每個VN都進行了K次映射產生候選方案，并進行了比較，大大增加了算法的執行時間，延長了VN的響應時間。

2013年，Stasi等[16]以無線mesh網絡作為底層物理網絡，引入了沖突域(collisiondomain)的概念，此沖突域中包含無線鏈路e以及不能與e同時被激活的其他無線鏈路。沖突域中如果除e之外的某條鏈路被激活，就會延遲e上信息的發送或者發送失敗。因此，e上的可提供帶寬取決于它的沖突域的組成，利用此特性，如果有必要，就會通過改變沖突域的組成來改變鏈路的可提供帶寬，這樣就可以映射先前沒有映射的VN請求。例如圖2中，在圖(a)的物理網絡WMN中，信道編號和可提供CPU資源分別標在了相應的無線鏈路旁和節點旁，圖(b)的VNR中，給定了CPU需求(節點上)和帶寬需求(鏈路旁)。假設每條鏈路的傳送率是c，在信道1上運行很完美的鏈路調度機制，那么每條這樣的鏈路的可提供帶寬為c/2，這樣的配置顯然無法滿足此VNR的需求，但如果將節點1和2之間的鏈路從信道1轉換到信道2中，那么節點0和1及之間的鏈路就可以滿足需求了。

映射算法中根據沖突域的構成來進行信道的分配，也以沖突域的概念為基礎，定義了一種新的鏈路容量量化規則，同時采用干擾物理模型，將接受端的信噪比大小考慮進來，判斷鏈路的可靠性。完成鏈路的虛擬化后，節點映射階段采用文獻[17]中的節點映射策略。在鏈路映射階段，借鑒已有的負載識別信道分配算法(Flow-awareChannelandRateAssignment，FCRA)[18]或者MVCRA(MinimumVariationChannelandRateAssignment)[19]，重新分配信道，改變鏈路的可提供帶寬，避免了VNR的重新映射，同時也彌補了靜態映射的不足，大大提高了VNR的接受率。

圖2 信道重配置完成映射圖

2015年，LuoJ等[20]針對一種特定的無線數據中心網絡Cayley，提出了一種虛擬資源映射算法以及基于鏈路干擾的著色算法。此網絡中的每個節點有一個半雙工的無線收發器，所有節點共享一個信道，天線是有向的，因此節點間的干擾并不主要取決于距離，而是是否處于發送節點的發送角內以及接收端的信噪比(SNR)是否大于一定的閾值，據此建立一個干擾矩陣。當干擾矩陣初始化后，映射算法尋找具有最多CPU資源的節點來分配給虛擬請求，然后計算SNR，根據物理干擾模型建立連接。將處于同一個發送節點發送角內并且SNR低于閾值的節點標記為同一顏色，具有同一顏色的節點不能互相通信。最后，更新干擾矩陣。節點和鏈路映射是并發進行的，可以動態調整，因為干擾的存在，鏈路分配可能失敗，此時，就會回溯到上一次的映射，動態調整整個虛擬資源的分配。

2.1.3 利用FDM的無線VNE

在對無線鏈路進行虛擬化時，FDM是最常用的一種虛擬化方法，利用不同頻段的信道對無線鏈路進行隔離劃分，從而避免干擾，通常這要求節點具有多個無線收發接口，并且工作在不同頻道上。

文獻[21]提出了一種方法，主要解決將具有可靠性限制的多播VNs映射到具有鏈路損耗特性的WMN的問題，是第一個在不可靠無線鏈路條件下，解決多播面向服務的VNE問題的方法。此方法將VN模型化為具有多播特性的星型拓撲，將物理網絡模型化為分層結構，為每一層分配不同的信道，這樣避免了鏈路間干擾，在此情況下，選出可以進行重新轉發數據的節點，以提高鏈路的可靠性。但是該方法并沒有考慮具體的節點資源和鏈路資源的限制。

文獻[22]研究了WMN的虛擬接入網絡映射(VirtualAccessNetworkEmbedding,VANE)的問題。為了能在VANE中靈活地分配資源，每個接入節點都是基于正交頻分復用接入(OrthogonalFrequencyDivisionMultipleAccess,OFDMA)的，且都配有雙無線收發器，兩個無線收發器分別工作在2.4G和5G頻段，避免了帶外干擾。通過分配給每條鏈路的子載波，VAN被很好地分隔開來。在有限的正交信道的限制下，為了協同不同鏈路的信道分配，提出了一種利用信道部分重疊的信道分配算法，采用了一種多項式時間內的近似算法。該算法首先初始化兩個集合，已被分配信道的節點集合S和未被分配信道的節點集合R，然后定義節點的鄰間節點數為節點的度，給R中最大度的節點優先分配信道，原因是最大度節點對鄰間具有最大的約束。給最大度節點分配信道后，根據此節點與其鄰間節點的信道分離權重，確定其鄰間節點的待分配信道候選集。給節點分配信道時，信道從每一輪的信道候選集的交集中選擇，如果有多個候選信道，則選擇編號最小的信道。一旦一個節點(例如n)被分配了一個信道，則將其加入集合S中。在下一輪中，可被分配信道的節點的集合有兩種情況：如果n的鄰間節點還沒有被分配信道，則這些鄰間節點組成集合R；否則，R為所有未被分配信道的節點集合。當每個節點都被分配一個信道后，算法成功結束。一旦交集為空集或者沒有可分配的信道，算法停止，報告失敗。

圖3展示了此算法的信道分配過程。

圖3 信道分配過程示意圖

圖3(a)中，S為空集，而R為所有物理節點的集合。用[i,j]表示從編號i到j的信道集合，圖中也就是一個節點的候選信道集，鏈路旁的數字表示鄰間節點的信道分離權重。在初始階段，每個節點的信道候選集是[1,11]，最大度節點a在第一輪中分配到信道1，并將其加入集合S，而R則變成還未分配信道的a的鄰間節點的集合，見圖3(b)，已分配的節點用灰色標出，同時R中節點的信道候選集根據鄰間節點的信道分離權重進行更新，然后，R中最大度節點根據其信道候選集分配信道，重復以上過程。圖3(e)中節點e被分配信道后，因為其所有鄰間節點都已經被分配信道，所以R={c}。當所有節點都被分配信道后，信道分配算法成功結束，見圖3(f)。

在節點映射過程中，提出了一種增強型的遺傳算法。由于普通的遺傳算法使用的是隨機產生第一代，無法保證最終方案的質量，而該算法使用貪婪算法來加速遺傳算法的收斂速度，改善了遺傳算法每一步迭代的質量。在鏈路映射階段，采用最短路徑算法，找出最小距離權重的路徑進行映射。該算法大大改善了映射方案的質量，但是由于增強型遺傳算法是兩種算法的結合，需要一定的時間開銷。

2.2 解決節點移動性問題的無線VNE

不同于有線網絡，無線網絡的節點具有一定的移動性，節點的移動很容易使鏈路變得不穩定，甚至斷開，最終導致VN在生命周期內停止服務。所以無線網絡中節點的移動性也是一個需要解決的問題，通常節點移動性需要采用分布式方法來進行管理。

2010年，Hernando等[23]設計了一種新的協議，來解決移動性的問題。該協議的核心思想是通過節點和鏈路的重映射來修補受影響的VN。算法對物理網絡進行了區域劃分，并對物理節點之間的通信定義了很多不同的信息，來滿足在物理節點移動時對虛擬節點和虛擬鏈路重映射時的需求。在節點重映射時，重新尋找符合條件的物理節點進行映射，當然，此算法中對于節點具有位置要求，大大減少了映射節點的搜索空間。在鏈路重映射的過程中，利用了路徑分割和遷移技術，以優化物理資源的利用。

2015年，Chochlidakis等[24-25]提出了利用DMM(Distributed Mobility Management)機制對節點的移動性進行管理，文獻[25]中還考慮了鏈路的流量需求問題，在最短路徑算法的基礎上，設計了一種能夠應對事先不確定流量需求的最優化算法，大大提高了該映射算法的魯棒性。

3 結束語

隨著網絡用戶數量的不斷暴增，用戶對于網絡提供的業務需求也越來越多樣化，現有網絡的發展已經很難滿足用戶的需求，網絡虛擬化技術隨之產生，對于未來網絡的發展具有非常重要的作用。目前對無線網絡的VNE問題還處于起步階段，尤其是對于無線環境下節點移動性問題的映射研究方面，還沒有太多的文獻，但是現有的研究已經總結出了一些很好的經驗。對于鏈路干擾問題，最基本的解決方案就是無線資源的虛擬化，例如TDM、FDM等方法，通過結合使用這些方法，避免鏈路干擾，在此基礎上優化映射方案；對于節點移動性的問題，都離不開重映射的思想，在節點的移動影響到VN的服務時，需要迅速重新找到合適的資源進行映射，以保證VN的生命周期內的服務質量。不過針對鏈路干擾問題，大部分方案仍然還是靜態映射，從而造成了物理資源的利用率低下，負載平衡不好的問題；而對于節點移動性問題，用到了重映射的方法，一定程度上優化了物理資源的利用率，但無線網絡中的節點移動通常會是大范圍的，如果只有一個中央處理節點，會造成網絡服務的巨大延遲和不可靠性。所以，未來的研究還需要關注以下兩個方面：

(1)動態映射：VN是具有一定的生存時間的，當某個VN生命時間結束，其所占用的物理資源被釋放，使得物理網絡的資源分配發生改變，網絡負載均衡性也會受到影響，對即將到來VN的映射也會有一定影響，此時如果能夠對已映射的VN進行重映射，優化物理資源的分配，將會大大提高VN請求的接受率，并且使網絡具有一定的自適應性。

(2)分布式：實際中，一些無線網絡場景缺乏對網絡進行全局管理的中心實體，例如ad-hoc網絡，該網絡中任何一個無線節點都可以發揮路由器的作用，而且網絡拓撲是在實時變化的，需要一個動態的分布式管理機制。而且對于規模比較大的網絡來說，如果不采用分布式的算法，映射時的搜索空間會非常大，使得算法執行時間過長，甚至可能無法滿足多項式時間要求。

[1]FischerA,BoteroJF,BeckMT,etal.Virtualnetworkembedding:asurvey[J].IEEECommunicationsSurveysandTutorials,2013,15(4):1888-1906.

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

[3] 劉川川.無線網絡虛擬化中資源分配算法研究[D].長沙:湖南大學,2013.

[4]ParkKM,KimCK.Aframeworkforvirtualnetworkembeddinginwirelessnetworks[C]//Proceedingsofthe4thinternationalconferenceonfutureinternettechnologies.[s.l.]:ACM,2009:5-7.

[5]BanerjeeS,ChaturvediA,MishraA,etal.Wirelessvirtualizationoncommodity802.11hardware[C]//ACMinternationalworkshoponwirelessnetworktestbedsexperimentalevaluationandcharacterizationserwintech.[s.l.]:ACM,2007:75-82.

[6]SinghalS,HadjichristofiG,SeskarI,etal.EvaluationofUMLbasedwirelessnetworkvirtualization[C]//Nextgenerationinternetnetworks.[s.l.]:[s.n.],2008:28-30.

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

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

[9]vandeBeltJ,AhmadiH,DoyleLE.Adynamicembeddingalgorithmforwirelessnetworkvirtualization[C]//Vehiculartechnologyconference.[s.l.]:IEEE,2014:1-6.

[10]Ben-ShimolY,KitroserI,DinitzY.Two-dimensionalmappingforwirelessOFDMAsystems[J].IEEETransactionsonBroadcasting,2006,52(3):388-396.

[11]NeckerMC,K?hnM,ReifertA,etal.OptimizedframepackingforOFDMAsystems[C]//IEEEvehiculartechnologyconference.[s.l.]:IEEE,2008:1483-1488.

[12]MahindraR,BhanageGD,HadjichristofiG,etal.Spaceversustimeseparationforwirelessvirtualizationonanindoorgrid[C]//Nextgenerationinternetnetworks.[s.l.]:IEEE,2008:215-222.

[13]JayasumanaAP,HanQ,IllangasekareTH.Virtualsensornetworks-aresourceefficientapproachforconcurrentapplications[C]//Internationalconferenceoninformationtechnology:newgenerations.[s.l.]:IEEE,2007:111-115.

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

[15]YunD,OkJ,ShinB,etal.Embeddingofvirtualnetworkre-questsoverstaticwirelessmultihopnetworks[J].ComputerNetworks,2013,57(5):1139-1152.

[16]StasiGD,AvalloneS,CanonicoR.Virtualnetworkembeddinginwirelessmeshnetworksthroughreconfigurationofchannels[C]//IEEEinternationalconferenceonwirelessandmobilecomputing.[s.l.]:IEEE,2013:537-544.

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

[18]AvalloneS,D’EliaFP,VentreG.Anewchannel,powerandrateassignmentalgorithmformulti-radiowirelessmeshnetworks[J].TelecommunicationSystems,2012,51(1):73-80.

[19]AvalloneS,D’EliaFP,VentreG.Atraffic-awarechannelre-assignmentalgorithmforwirelessmeshnetworks[C]//Wirelessconference.[s.l.]:IEEE,2010:683-688.

[20]LuoJ,GuoY,FuS,etal.Virtualresourceallocationbasedonlinkinterferenceincayleywirelessdatacenters[J].IEEETransactionsonComputers,2015,64(10):3016-3021.

[21]LvP,CaiZ,XuJ,etal.Multicastservice-orientedvirtualnetworkembeddinginwirelessmeshnetworks[J].IEEECommunicationsLetters,2012,16(3):375-377.

[22]LvP,WangX,XuM.Virtualaccessnetworkembeddinginwirelessmeshnetworks[J].AdHocNetworks,2012,10(7):1362-1378.

[23]HernandoG,PérezS,CaberoJM.Mobilityawaredistributedembeddingofvirtualnetworks[C]//Futurenetworkandmobilesummit.[s.l.]:[s.n.],2010:1-8.

[24]ChochlidakisG,FriderikosV.Mobilityawarevirtualnetworkembedding[C]//2015IEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2015:5846-5852.

[25]ChochlidakisG,FriderikosV.Robustvirtualnetworkembeddingformobilenetworks[C]//IEEEinternationalsymposiumonpersonal,indoorandmobileradiocommunication.HK:IEEE,2015:1867-1871.

[26]EspositoF,ChitiF.Distributedconsensus-basedauctionsforwirelessvirtualnetworkembedding[C]//2015IEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2015:472-477.

[27]AbdelwahabS,HamdaouiB,GuizaniM,etal.Efficientvirtualnetworkembeddingwithbacktrackavoidancefordynamicwirelessnetworks[J].IEEETransactionsonWirelessCommunications,2016,15(4):2669-2683.

Investigation on Virtual Network Embedding Algorithm in Wireless Scenarios

JIANG Xin，YANG Long-xiang，WU Meng-ting

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

Over the last decades,it’s becoming more and more difficult for existing network architecture to satisfy the continuously increasing demands of users for new better service.Network virtualization is considered as a critical technology to overcome this problem and how to allocate resource of the substrate network effectively to virtual networks is the main challenge in network virtualization which is usually referred to as Virtual Network Embedding (VNE) problem,a NP-hard problem.However,due to various features unique in wireless networks,e.g.,broadcast nature of links,mobility of nodes,etc.,the VNE problem becomes much more complex and harder.The definition of VNE is proposed and embedding objects and the optimization strategies of VNE are introduced,especially discussion of the VNE algorithm in wireless scenarios.The important part,some VNE algorithms for wireless network are categorized and compared based on the wireless feature they aim to address.And based on the conclusion from the comparison,some future trends for the virtual network embedding over wireless substrate network are pointed out.

wireless virtualization;virtual network embedding;NP-hard;optimization;resource allocation

2016-04-22

2016-08-11

時間：2017-02-17

國家“973”重點基礎研究發展計劃項目(2013CB329104)

姜 鑫(1992-)，男，碩士，研究方向為移動通信與無線技術;楊龍祥，教授，博士生導師，研究方向為移動無線通信與物聯網。

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

TP301.6

A

1673-629X(2017)04-0077-06

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