姜 鑫，楊龍祥，吳夢(mèng)婷

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

無(wú)線環(huán)境下的虛擬網(wǎng)絡(luò)映射算法研究

姜 鑫，楊龍祥，吳夢(mèng)婷

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

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

無(wú)線虛擬化；虛擬網(wǎng)絡(luò)映射；NP難題；最優(yōu)化；資源分配

0 引 言

經(jīng)過(guò)幾十年的發(fā)展，互聯(lián)網(wǎng)已被廣泛地應(yīng)用于各個(gè)領(lǐng)域，從根本上影響著人們的生活方式，對(duì)于社會(huì)的發(fā)展起到了至關(guān)重要的作用。但是隨著互聯(lián)網(wǎng)用戶以及用戶對(duì)各種業(yè)務(wù)需求的爆炸式增長(zhǎng)，使得現(xiàn)有的傳統(tǒng)互聯(lián)網(wǎng)模式已經(jīng)很難滿足未來(lái)網(wǎng)絡(luò)的發(fā)展需求。針對(duì)互聯(lián)網(wǎng)的發(fā)展問(wèn)題，現(xiàn)已提出了很多種新的協(xié)議和技術(shù)，其中網(wǎng)絡(luò)虛擬化被認(rèn)為是解決現(xiàn)有網(wǎng)絡(luò)發(fā)展問(wèn)題的重要方法。

網(wǎng)絡(luò)虛擬化技術(shù)使得多種異構(gòu)網(wǎng)絡(luò)架構(gòu)能夠在同一物理網(wǎng)絡(luò)上共存，且互不干擾，在不改變物理網(wǎng)絡(luò)的前提下，能夠?yàn)橛脩籼峁┒说蕉说膫€(gè)性化服務(wù)，使得在有限的硬件物理架構(gòu)條件下獲得的收益最大化。在虛擬化技術(shù)中，最基本的就是虛擬網(wǎng)絡(luò)(Virtual Network,VN)。VN是由一系列的虛擬鏈路相連接的虛擬節(jié)點(diǎn)形成的拓?fù)?，通過(guò)將底層物理網(wǎng)絡(luò)(Substrate Network,SN)的資源進(jìn)行虛擬化，使得多個(gè)具有不同特性的VN能夠在同一SN上并存。

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

針對(duì)無(wú)線環(huán)境下的虛擬網(wǎng)絡(luò)映射問(wèn)題，介紹了VNE的映射指標(biāo)和解決策略，重點(diǎn)討論了無(wú)線環(huán)境下的VNE算法，在按照其所對(duì)應(yīng)的無(wú)線網(wǎng)絡(luò)特性進(jìn)行分類與討論的基礎(chǔ)上，對(duì)各類方法進(jìn)行了對(duì)比分析，描述了現(xiàn)階段的研究進(jìn)展及成果，指出了未來(lái)的研究方向。

1 虛擬網(wǎng)絡(luò)映射

1.1 VNE問(wèn)題模型

VNE問(wèn)題是一個(gè)在滿足約束條件下的圖匹配問(wèn)題，所以網(wǎng)絡(luò)模型可以用無(wú)向圖或者有向圖來(lái)表示。

物理網(wǎng)絡(luò)：可以用圖GS=(NS,LS)表示，其中，NS表示物理節(jié)點(diǎn)的集合，LS表示物理鏈路的集合。

虛擬網(wǎng)絡(luò)：可以用圖GV=(NV,LV)表示，其中，NV表示虛擬節(jié)點(diǎn)的集合，LV表示虛擬鏈路的集合。

通常，為了保證網(wǎng)絡(luò)的負(fù)載平衡，同一個(gè)VN中的不同虛擬節(jié)點(diǎn)會(huì)映射到不同的物理節(jié)點(diǎn)，尤其在虛擬節(jié)點(diǎn)沒(méi)有位置要求的情況下，這就顯得尤為重要。

1.2 映射指標(biāo)

VNE的主要目的在于，在物理資源有限的條件下，充分利用物理資源，來(lái)為更多的虛擬網(wǎng)絡(luò)提供服務(wù)，從而使底層物理網(wǎng)絡(luò)運(yùn)營(yíng)商的收益最大化。所以最常用的評(píng)價(jià)指標(biāo)有三個(gè)：長(zhǎng)期平均收益R、VN請(qǐng)求接受率γ以及長(zhǎng)期收益成本比R/C。

(1)長(zhǎng)期平均收益R。

假設(shè)已接受的一個(gè)VN請(qǐng)求GV產(chǎn)生的收益表示為：

(1)

其中，常量α和β是權(quán)重因子，用來(lái)調(diào)節(jié)節(jié)點(diǎn)和鏈路資源的相對(duì)重要性，由運(yùn)營(yíng)商確定。

(2)VN請(qǐng)求接受率γ。

用GV(t)表示在時(shí)隙t內(nèi)到達(dá)的VN的集合，則VN接受率為：

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

假設(shè)成功映射一個(gè)VN請(qǐng)求GV的成本為：

(2)

R/C的取值范圍在0到1之間，如果這個(gè)值太小，表示映射的路徑產(chǎn)生的跳數(shù)太多，對(duì)底層資源的消耗大，但如果太大，表示VN的映射范圍比較集中，此時(shí)網(wǎng)絡(luò)的負(fù)載均衡性能會(huì)比較差。

1.3 最優(yōu)化策略

VNE問(wèn)題是NP難問(wèn)題，因此，對(duì)于大規(guī)模網(wǎng)絡(luò)幾乎不可能在一定的時(shí)間內(nèi)得出最優(yōu)解。據(jù)此，有了三種不同的解決方案：精確解法、啟發(fā)式解法和元啟發(fā)式解法。

1.3.1 精確解法

可通過(guò)線性規(guī)劃(Linear Programming,LP)的方法得到最優(yōu)精確解。更具體地說(shuō)是整數(shù)線性規(guī)劃(Integer Linear Programming,ILP)。雖然在很多實(shí)用場(chǎng)景下ILP是NP難問(wèn)題，但在小規(guī)模網(wǎng)絡(luò)中還是可能在一定時(shí)間內(nèi)求解出來(lái)的，通常需要借助一些軟件工具來(lái)進(jìn)行求解，例如GLPK。同時(shí)此精確解還可以作為啟發(fā)式解法的優(yōu)化邊界使用。

1.3.2 啟發(fā)式解法

在VNE中，執(zhí)行時(shí)間是很重要的。網(wǎng)絡(luò)虛擬化解決了在線動(dòng)態(tài)情況的問(wèn)題，也就是說(shuō)即使無(wú)法提前知曉VNR的到達(dá)時(shí)間，也可解決。因此，為了避免對(duì)新到達(dá)VNR映射的延遲，VNE算法的執(zhí)行時(shí)間要盡量小。所以提出了基于啟發(fā)式算法的VNE方法，該算法并不是為了求出全局最優(yōu)解，而是為了保證在較短的執(zhí)行時(shí)間內(nèi)找出較好的映射方案，當(dāng)然這樣很有可能得出的是遠(yuǎn)離全局最優(yōu)解的局部最優(yōu)解。

1.3.3 元啟發(fā)式解法

VNE問(wèn)題可以看作是組合型最優(yōu)化問(wèn)題，也就是在一個(gè)離散的搜尋空間中尋找一個(gè)最優(yōu)解決方案。因?yàn)樵诖笠?guī)模實(shí)例中難以找到最優(yōu)化方案，可采用元啟發(fā)式算法，例如模擬退火法、遺傳算法、蟻群算法、顆粒群最優(yōu)化算法、禁忌搜索法等，這些方法通常都是根據(jù)一定的目標(biāo)參數(shù)來(lái)改善候選方案，從而找出近似最優(yōu)解。

2 無(wú)線環(huán)境下的虛擬網(wǎng)絡(luò)映射

虛擬網(wǎng)絡(luò)映射的問(wèn)題，現(xiàn)在已有大量的研究，學(xué)術(shù)界也提出了很多算法用于解決此問(wèn)題。Fischer等[1]對(duì)于現(xiàn)有的大部分算法做了總結(jié)概括，并從三個(gè)不同方面對(duì)其中的算法做了分類，靜態(tài)與動(dòng)態(tài)，集中式與分布式，精簡(jiǎn)和冗余。

現(xiàn)在大部分的研究還是集中在有線網(wǎng)絡(luò)環(huán)境下，而無(wú)線網(wǎng)絡(luò)是現(xiàn)在一種常用的網(wǎng)絡(luò)形式，因此無(wú)線場(chǎng)景的虛擬化技術(shù)也是非常迫切需要解決的。但是因?yàn)闊o(wú)線網(wǎng)絡(luò)獨(dú)有的特性，例如：鏈路干擾、節(jié)點(diǎn)移動(dòng)性等問(wèn)題，使得無(wú)線環(huán)境下的虛擬網(wǎng)絡(luò)映射問(wèn)題變得更加復(fù)雜，所以需要新的架構(gòu)和算法來(lái)解決無(wú)線環(huán)境下的VNE問(wèn)題。對(duì)現(xiàn)有的無(wú)線環(huán)境下的虛擬網(wǎng)絡(luò)映射算法，根據(jù)其所針對(duì)的無(wú)線特性問(wèn)題及解決方法做了如下分類，見(jiàn)圖1。

圖1 無(wú)線虛擬網(wǎng)絡(luò)映射方法分類

2.1 解決鏈路干擾問(wèn)題的無(wú)線VNE

有線網(wǎng)絡(luò)的鏈路本身就具有一定的獨(dú)立性，鏈路之間沒(méi)有干擾，但是無(wú)線網(wǎng)絡(luò)的鏈路具有廣播特性，互相之間很容易產(chǎn)生干擾，所以無(wú)線網(wǎng)絡(luò)虛擬化的主要難點(diǎn)也在于如何虛擬化無(wú)線鏈路。

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

2.1.1 利用SDM的無(wú)線VNE

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

2.1.2 利用TDM的無(wú)線VNE

將時(shí)間劃分為不相交的時(shí)隙，為無(wú)線物理鏈路按一定的規(guī)則分配時(shí)隙，并讓無(wú)線鏈路在相應(yīng)的時(shí)隙內(nèi)激活，從而達(dá)到避免干擾的目的。

文獻(xiàn)[14-15]首次為無(wú)線多跳網(wǎng)絡(luò)提出了VNE方法，利用無(wú)線物理鏈路的干擾矩陣，引入了一個(gè)沖突圖(conflict graph)的概念。此圖中，一條鏈路變?yōu)橐粋€(gè)節(jié)點(diǎn)，如果兩條鏈路互相干擾就在此圖中將其連接，并對(duì)鏈路設(shè)置了一個(gè)參數(shù)作為權(quán)重，因此可量化任意兩條鏈路之間的干擾關(guān)系，再據(jù)此圖確定不同鏈路的激活時(shí)隙，從而避免干擾。同時(shí)還總結(jié)到，大部分映射算法遵循這樣的架構(gòu)：

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

(2)根據(jù)某種目標(biāo)來(lái)對(duì)此映射進(jìn)行評(píng)估，例如用來(lái)映射的資源數(shù)量；

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

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

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

映射算法中根據(jù)沖突域的構(gòu)成來(lái)進(jìn)行信道的分配，也以沖突域的概念為基礎(chǔ)，定義了一種新的鏈路容量量化規(guī)則，同時(shí)采用干擾物理模型，將接受端的信噪比大小考慮進(jìn)來(lái)，判斷鏈路的可靠性。完成鏈路的虛擬化后，節(jié)點(diǎn)映射階段采用文獻(xiàn)[17]中的節(jié)點(diǎn)映射策略。在鏈路映射階段，借鑒已有的負(fù)載識(shí)別信道分配算法(Flow-awareChannelandRateAssignment，F(xiàn)CRA)[18]或者M(jìn)VCRA(MinimumVariationChannelandRateAssignment)[19]，重新分配信道，改變鏈路的可提供帶寬，避免了VNR的重新映射，同時(shí)也彌補(bǔ)了靜態(tài)映射的不足，大大提高了VNR的接受率。

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

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

2.1.3 利用FDM的無(wú)線VNE

在對(duì)無(wú)線鏈路進(jìn)行虛擬化時(shí)，F(xiàn)DM是最常用的一種虛擬化方法，利用不同頻段的信道對(duì)無(wú)線鏈路進(jìn)行隔離劃分，從而避免干擾，通常這要求節(jié)點(diǎn)具有多個(gè)無(wú)線收發(fā)接口，并且工作在不同頻道上。

文獻(xiàn)[21]提出了一種方法，主要解決將具有可靠性限制的多播VNs映射到具有鏈路損耗特性的WMN的問(wèn)題，是第一個(gè)在不可靠無(wú)線鏈路條件下，解決多播面向服務(wù)的VNE問(wèn)題的方法。此方法將VN模型化為具有多播特性的星型拓?fù)洌瑢⑽锢砭W(wǎng)絡(luò)模型化為分層結(jié)構(gòu)，為每一層分配不同的信道，這樣避免了鏈路間干擾，在此情況下，選出可以進(jìn)行重新轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)，以提高鏈路的可靠性。但是該方法并沒(méi)有考慮具體的節(jié)點(diǎn)資源和鏈路資源的限制。

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

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

圖3 信道分配過(guò)程示意圖

圖3(a)中，S為空集，而R為所有物理節(jié)點(diǎn)的集合。用[i,j]表示從編號(hào)i到j(luò)的信道集合，圖中也就是一個(gè)節(jié)點(diǎn)的候選信道集，鏈路旁的數(shù)字表示鄰間節(jié)點(diǎn)的信道分離權(quán)重。在初始階段，每個(gè)節(jié)點(diǎn)的信道候選集是[1,11]，最大度節(jié)點(diǎn)a在第一輪中分配到信道1，并將其加入集合S，而R則變成還未分配信道的a的鄰間節(jié)點(diǎn)的集合，見(jiàn)圖3(b)，已分配的節(jié)點(diǎn)用灰色標(biāo)出，同時(shí)R中節(jié)點(diǎn)的信道候選集根據(jù)鄰間節(jié)點(diǎn)的信道分離權(quán)重進(jìn)行更新，然后，R中最大度節(jié)點(diǎn)根據(jù)其信道候選集分配信道，重復(fù)以上過(guò)程。圖3(e)中節(jié)點(diǎn)e被分配信道后，因?yàn)槠渌朽忛g節(jié)點(diǎn)都已經(jīng)被分配信道，所以R={c}。當(dāng)所有節(jié)點(diǎn)都被分配信道后，信道分配算法成功結(jié)束，見(jiàn)圖3(f)。

在節(jié)點(diǎn)映射過(guò)程中，提出了一種增強(qiáng)型的遺傳算法。由于普通的遺傳算法使用的是隨機(jī)產(chǎn)生第一代，無(wú)法保證最終方案的質(zhì)量，而該算法使用貪婪算法來(lái)加速遺傳算法的收斂速度，改善了遺傳算法每一步迭代的質(zhì)量。在鏈路映射階段，采用最短路徑算法，找出最小距離權(quán)重的路徑進(jìn)行映射。該算法大大改善了映射方案的質(zhì)量，但是由于增強(qiáng)型遺傳算法是兩種算法的結(jié)合，需要一定的時(shí)間開(kāi)銷。

2.2 解決節(jié)點(diǎn)移動(dòng)性問(wèn)題的無(wú)線VNE

不同于有線網(wǎng)絡(luò)，無(wú)線網(wǎng)絡(luò)的節(jié)點(diǎn)具有一定的移動(dòng)性，節(jié)點(diǎn)的移動(dòng)很容易使鏈路變得不穩(wěn)定，甚至斷開(kāi)，最終導(dǎo)致VN在生命周期內(nèi)停止服務(wù)。所以無(wú)線網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性也是一個(gè)需要解決的問(wèn)題，通常節(jié)點(diǎn)移動(dòng)性需要采用分布式方法來(lái)進(jìn)行管理。

2010年，Hernando等[23]設(shè)計(jì)了一種新的協(xié)議，來(lái)解決移動(dòng)性的問(wèn)題。該協(xié)議的核心思想是通過(guò)節(jié)點(diǎn)和鏈路的重映射來(lái)修補(bǔ)受影響的VN。算法對(duì)物理網(wǎng)絡(luò)進(jìn)行了區(qū)域劃分，并對(duì)物理節(jié)點(diǎn)之間的通信定義了很多不同的信息，來(lái)滿足在物理節(jié)點(diǎn)移動(dòng)時(shí)對(duì)虛擬節(jié)點(diǎn)和虛擬鏈路重映射時(shí)的需求。在節(jié)點(diǎn)重映射時(shí)，重新尋找符合條件的物理節(jié)點(diǎn)進(jìn)行映射，當(dāng)然，此算法中對(duì)于節(jié)點(diǎn)具有位置要求，大大減少了映射節(jié)點(diǎn)的搜索空間。在鏈路重映射的過(guò)程中，利用了路徑分割和遷移技術(shù)，以優(yōu)化物理資源的利用。

2015年，Chochlidakis等[24-25]提出了利用DMM(Distributed Mobility Management)機(jī)制對(duì)節(jié)點(diǎn)的移動(dòng)性進(jìn)行管理，文獻(xiàn)[25]中還考慮了鏈路的流量需求問(wèn)題，在最短路徑算法的基礎(chǔ)上，設(shè)計(jì)了一種能夠應(yīng)對(duì)事先不確定流量需求的最優(yōu)化算法，大大提高了該映射算法的魯棒性。

3 結(jié)束語(yǔ)

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

(1)動(dòng)態(tài)映射：VN是具有一定的生存時(shí)間的，當(dāng)某個(gè)VN生命時(shí)間結(jié)束，其所占用的物理資源被釋放，使得物理網(wǎng)絡(luò)的資源分配發(fā)生改變，網(wǎng)絡(luò)負(fù)載均衡性也會(huì)受到影響，對(duì)即將到來(lái)VN的映射也會(huì)有一定影響，此時(shí)如果能夠?qū)σ延成涞腣N進(jìn)行重映射，優(yōu)化物理資源的分配，將會(huì)大大提高VN請(qǐng)求的接受率，并且使網(wǎng)絡(luò)具有一定的自適應(yīng)性。

(2)分布式：實(shí)際中，一些無(wú)線網(wǎng)絡(luò)場(chǎng)景缺乏對(duì)網(wǎng)絡(luò)進(jìn)行全局管理的中心實(shí)體，例如ad-hoc網(wǎng)絡(luò)，該網(wǎng)絡(luò)中任何一個(gè)無(wú)線節(jié)點(diǎn)都可以發(fā)揮路由器的作用，而且網(wǎng)絡(luò)拓?fù)涫窃趯?shí)時(shí)變化的，需要一個(gè)動(dòng)態(tài)的分布式管理機(jī)制。而且對(duì)于規(guī)模比較大的網(wǎng)絡(luò)來(lái)說(shuō)，如果不采用分布式的算法，映射時(shí)的搜索空間會(huì)非常大，使得算法執(zhí)行時(shí)間過(guò)長(zhǎng)，甚至可能無(wú)法滿足多項(xiàng)式時(shí)間要求。

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

[2] 羅 娟,劉川川,李仁發(fā).基于鏈路可靠性的無(wú)線虛擬網(wǎng)絡(luò)分配方法[J].通信學(xué)報(bào),2012,33(Z1):88-95.

[3] 劉川川.無(wú)線網(wǎng)絡(luò)虛擬化中資源分配算法研究[D].長(zhǎng)沙:湖南大學(xué),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

時(shí)間：2017-02-17

國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329104)

姜 鑫(1992-)，男，碩士，研究方向?yàn)橐苿?dòng)通信與無(wú)線技術(shù);楊龍祥，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)無(wú)線通信與物聯(lián)網(wǎng)。

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