無線虛擬網(wǎng)絡(luò)中的鄰近節(jié)點(diǎn)分組映射算法

李 錚,丁 升,王瀟瀟,劉期烈

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 概述

隨著智能終端及其相關(guān)業(yè)務(wù)的發(fā)展，未來無線網(wǎng)絡(luò)將呈現(xiàn)密集部署、多樣業(yè)務(wù)、異構(gòu)網(wǎng)絡(luò)并存的多元化形態(tài)。在不斷擴(kuò)大的網(wǎng)絡(luò)規(guī)模和更為密集的網(wǎng)絡(luò)部署下，傳統(tǒng)的因特網(wǎng)網(wǎng)絡(luò)架構(gòu)和協(xié)議難以滿足網(wǎng)絡(luò)融合的需求，并且面臨網(wǎng)絡(luò)僵化的問題[1-2]。網(wǎng)絡(luò)虛擬化技術(shù)通過對共用的底層基礎(chǔ)設(shè)施進(jìn)行抽象，并提供統(tǒng)一的可編程接口，將多個彼此隔離且具有不同拓?fù)浣Y(jié)構(gòu)的虛擬網(wǎng)絡(luò)同時映射到共用的基礎(chǔ)設(shè)施上，為用戶提供差異性服務(wù)，實現(xiàn)資源共享，已成為未來網(wǎng)絡(luò)關(guān)鍵技術(shù)之一[3-4]。

網(wǎng)絡(luò)虛擬化是在物理網(wǎng)絡(luò)(Substrate Network,SN)上運(yùn)行多個異構(gòu)虛擬網(wǎng)絡(luò)(Virtual Network,VN)的技術(shù),通常在網(wǎng)絡(luò)虛擬化之后有兩個邏輯角色,即基礎(chǔ)設(shè)施提供商(Infrastructure Provider,InP)和網(wǎng)絡(luò)服務(wù)提供商(Service Provider,SP)[5-6]。InP負(fù)責(zé)向SP提供無線網(wǎng)絡(luò)資源;SP根據(jù)租用和分配的資源自行創(chuàng)建和部署虛擬資源,以滿足端到端的服務(wù)要求[7]。

然而,隨著無線流量和服務(wù)量的巨大增長,無線異構(gòu)網(wǎng)絡(luò)的管理愈加繁瑣,將虛擬化擴(kuò)展到無線網(wǎng)絡(luò)中可以簡化異構(gòu)網(wǎng)絡(luò)管理中出現(xiàn)的問題。無線網(wǎng)絡(luò)虛擬化是將無線物理基礎(chǔ)設(shè)施和無線電資源抽象并隔離成多個虛擬資源池,再將這些虛擬資源提供給不同SP[8]。在有線網(wǎng)絡(luò)虛擬化中,其帶寬資源的抽象和隔離可以在硬件基礎(chǔ)上完成(例如端口和鏈路);但在無線網(wǎng)絡(luò)虛擬化中,由于無線通信的固有傳播性質(zhì)和隨機(jī)波動,無線資源的抽象和隔離并不簡單[9-10]。文獻(xiàn)[11]提出一種無線環(huán)境下虛擬網(wǎng)絡(luò)的嵌入框架,但沒有給出解決問題的具體算法。文獻(xiàn)[12]引入基于卡諾圖的頻率和時間塊分配算法,將二維資源分配給VN請求。文獻(xiàn)[13]提出一種重新配置信道從而在無線網(wǎng)狀網(wǎng)絡(luò)中嵌入虛擬網(wǎng)絡(luò)的算法。上述方法都促進(jìn)了無線網(wǎng)絡(luò)虛擬化的發(fā)展。

由于多個VN請求共享底層的物理資源,因此為了提高物理資源的利用率和InP收益,高效地在線嵌入VN請求是至關(guān)重要的。文獻(xiàn)[14]提出基于約束的虛擬網(wǎng)絡(luò)設(shè)計和映射到基板網(wǎng)絡(luò)的算法以及本文使用的迭代設(shè)計算法。文獻(xiàn)[15]提出細(xì)分啟發(fā)式算法和自適應(yīng)優(yōu)化策略。文獻(xiàn)[16]提出兩階段協(xié)調(diào)性較好的VN嵌入算法。文獻(xiàn)[17]提出一種基于負(fù)載平衡感知的虛擬網(wǎng)絡(luò)嵌入算法。以上4種算法基于啟發(fā)式算法，在使用貪婪方法預(yù)選節(jié)點(diǎn)映射之后，大多數(shù)算法主要關(guān)注鏈路映射。但是，預(yù)先選擇節(jié)點(diǎn)映射可能導(dǎo)致算法性能不佳。文獻(xiàn)[18]提出一種基于虛擬節(jié)點(diǎn)和鏈路的分布式協(xié)同映射算法,但是該算法的穩(wěn)定性和性能不如集中式算法。

為解決無線虛擬網(wǎng)絡(luò)的映射問題,同時更有效地利用物理資源,本文提出鄰近節(jié)點(diǎn)分組映射(Packet Mapping of Adjacent Nodes,P-AN)算法。將節(jié)點(diǎn)分為中心節(jié)點(diǎn)和與其相連的邊緣節(jié)點(diǎn),兩者共同組成映射子集合。在此基礎(chǔ)上,依次進(jìn)行中心節(jié)點(diǎn)和邊緣節(jié)點(diǎn)的映射,并在所有節(jié)點(diǎn)映射完成后進(jìn)行鏈路映射,從而提高無線虛擬網(wǎng)絡(luò)映射接受率、收益開銷比和物理資源利用率。

1 無線虛擬網(wǎng)絡(luò)模型和問題描述

1.1 無線網(wǎng)絡(luò)模型

1.1.1 無線物理網(wǎng)絡(luò)模型

1.1.2 無線虛擬網(wǎng)絡(luò)模型

1.2 問題分析

1.2.1 物理網(wǎng)絡(luò)可用資源

物理網(wǎng)絡(luò)可用資源主要包含節(jié)點(diǎn)剩余可用資源和鏈路剩余可用資源。虛擬映射是指虛擬請求到達(dá)后根據(jù)物理網(wǎng)絡(luò)可用資源,選取合適的物理節(jié)點(diǎn)和鏈路進(jìn)行映射。

對于每一個節(jié)點(diǎn)nS∈NS,它的可用資源為:

(1)

與節(jié)點(diǎn)相同,不同虛擬請求的鏈路可以映射到同一物理鏈路上,對于每一條鏈路lS∈LS,它的可用資源為:

(2)

(3)

1.2.2 鏈路干擾

在無線環(huán)境下,無線鏈路間存在干擾。本文只考慮相鄰鏈路間的干擾,定義物理網(wǎng)絡(luò)中每一條鏈路的干擾為:

(4)

其中,dl表示與鏈路lS直接相連而產(chǎn)生干擾的物理鏈路個數(shù),1表示自身的干擾,σ為常數(shù)。鏈路干擾將在最短路徑算法中作為鏈路的一部分權(quán)值,用于尋找最優(yōu)的路徑。

1.3 無線虛擬網(wǎng)絡(luò)映射

當(dāng)一個VN請求到達(dá)時,物理網(wǎng)絡(luò)必須決定是否接受該虛擬請求。如果接受,那么物理網(wǎng)絡(luò)在資源池中需要為虛擬請求選擇滿足要求的物理節(jié)點(diǎn)和路徑,當(dāng)虛擬請求完成后,相應(yīng)物理資源將被釋放。

節(jié)點(diǎn)映射過程定義為MapN:NV→NS,?nV∈NV。存在如下約束:

d(l(nV),l(n:nV→nS))≤D

c(nV)≤cN(nS)(?nV→nS)

(5)

其中,d(l(nV),l(n:nV→nS))表示虛擬節(jié)點(diǎn)nV與待映射的物理節(jié)點(diǎn)nS間的實際矢量距離,D為虛擬節(jié)點(diǎn)的映射范圍矢量值。

鏈路映射過程定義為MapL:LV→LS,?lV∈LV。存在如下約束:

b(lV)≤BL(lS),?lV→lS,lS∈PS

(6)

1.4 收益與開銷

1.4.1 基礎(chǔ)設(shè)施商的收益

虛擬請求到達(dá)InP時,InP希望通過高效地分配資源來部署更多的虛擬請求從而獲得更多的收益。本文假設(shè)一組InP服務(wù)一個虛擬請求得到的收益為:

(7)

其中,α和β分別表示平衡節(jié)點(diǎn)資源和鏈路帶寬的加權(quán)系數(shù),由InP確定。

1.4.2 映射開銷

VN請求的映射開銷定義為請求映射到物理資源池上時消耗的節(jié)點(diǎn)資源和鏈路資源,即映射開銷為:

(8)

其中,αb和βb是加權(quán)系數(shù),用于平衡節(jié)點(diǎn)資源和鏈路資源的影響,l(lV)表示虛擬鏈路映射到物理路徑的長度。

收入與開銷的比值可以用來表示物理資源利用率。用GV(T)表示在時間T內(nèi)到達(dá)的VN的收益開銷比集合,可得長期收益開銷比為:

(9)

收益開銷比數(shù)值較大表示VN的映射集中在一片較小的物理區(qū)域內(nèi),此時網(wǎng)絡(luò)的負(fù)載均衡性能比較差。

2 中心度與拓?fù)鋭莘治?/h2>

在映射過程中,現(xiàn)有的映射算法大多是先尋找可用資源多的節(jié)點(diǎn)映射,再進(jìn)行鏈路映射,這種方式下節(jié)點(diǎn)映射和鏈路映射相互獨(dú)立,雖然節(jié)點(diǎn)能夠得到較好利用,但是由于底層資源的動態(tài)變化,鏈路資源可能無法得到合理利用。為避免資源分配不合理,本文首先選擇中心節(jié)點(diǎn)及其邊緣節(jié)點(diǎn)組成一個子集。

2.1 節(jié)點(diǎn)中心度

中心度是用來衡量人或物在其關(guān)系網(wǎng)絡(luò)中重要程度的一個指標(biāo)。本文借鑒社會關(guān)系網(wǎng)中的節(jié)點(diǎn)中心度,來反映節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械闹匾潭取?/p>

本文介紹3種相關(guān)的中心度的度量方法,即度數(shù)、連接強(qiáng)度和接近度。因為所使用的方法和針對的問題不同,所以在相同的環(huán)境下節(jié)點(diǎn)中心度可能會出現(xiàn)不同的排序[19]。

1)節(jié)點(diǎn)的度數(shù)

節(jié)點(diǎn)的度數(shù)DC是指與該節(jié)點(diǎn)直接相連的鄰近節(jié)點(diǎn)的個數(shù),即:

DCni=drg(ni)

(10)

虛擬節(jié)點(diǎn)的度數(shù)描述了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的局部重要性,較高度數(shù)的虛擬節(jié)點(diǎn)具有更多的相鄰節(jié)點(diǎn)和鏈路,可以接受更多的資源請求。

2)節(jié)點(diǎn)的連接強(qiáng)度

在虛擬網(wǎng)絡(luò)拓?fù)鋱DGV中,任意節(jié)點(diǎn)ni的連接強(qiáng)度Qni定義為與節(jié)點(diǎn)ni連接的所有鏈路的帶寬之和,定義式如下:

(11)

節(jié)點(diǎn)的連接強(qiáng)度反映了目標(biāo)節(jié)點(diǎn)與其他節(jié)點(diǎn)相互關(guān)聯(lián)的可能性。

3)節(jié)點(diǎn)的接近度

節(jié)點(diǎn)在網(wǎng)絡(luò)中所處位置的重要性可以用節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間的最短路徑來描述。以dij表示節(jié)點(diǎn)ni與節(jié)點(diǎn)nj之間通信所需的最短路徑的矢量值,如果i=j,則dij=0。

2.2 拓?fù)鋭莸囊?/h3>

場是英國物理學(xué)家法拉第在1837年為解釋電磁感應(yīng)現(xiàn)象而提出的一個概念。受法拉第電磁場思想的啟發(fā),可將網(wǎng)絡(luò)拓?fù)淇醋魇且粋€包含節(jié)點(diǎn)集合以及節(jié)點(diǎn)間鏈路集合的場,位于場中的任何節(jié)點(diǎn)都將受到其他節(jié)點(diǎn)的聯(lián)合作用[20]。

對于網(wǎng)絡(luò)拓?fù)銰=(N,L),根據(jù)場的勢函數(shù)定義,任意節(jié)點(diǎn)ni的拓?fù)鋭軹P可表示為:

(12)

其中,影響因子σ表示每個節(jié)點(diǎn)的作用范圍;mj≥0,用來描述每個節(jié)點(diǎn)所擁有的屬性。

將拓?fù)鋭菀胩摂M映射網(wǎng)絡(luò)中,其節(jié)點(diǎn)考慮4個屬性:節(jié)點(diǎn)的剩余計算能力大小,該節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑矢量值,該節(jié)點(diǎn)的度數(shù)以及該節(jié)點(diǎn)的連接強(qiáng)度,表示如下:

(13)

由以上定義可知,節(jié)點(diǎn)的拓?fù)鋭葜翟酱蟠砥涓浇倪B接越密集,那么該節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置越重要,越有可能成為中心節(jié)點(diǎn)。

3 無線虛擬網(wǎng)絡(luò)映射算法

3.1 目標(biāo)節(jié)點(diǎn)的選取

在處理虛擬請求的操作中,通過計算拓?fù)鋭葸x出中心節(jié)點(diǎn)。在進(jìn)行中心節(jié)點(diǎn)的映射部署時,選出符合約束要求的物理節(jié)點(diǎn)集合,并根據(jù)物理節(jié)點(diǎn)的擴(kuò)展資源公式,優(yōu)先選擇集合中擴(kuò)展資源值比較大的承載節(jié)點(diǎn)進(jìn)行中心節(jié)點(diǎn)的映射。其中,物理節(jié)點(diǎn)的擴(kuò)展資源定義為:

(14)

在中心節(jié)點(diǎn)映射完成后,進(jìn)行邊緣節(jié)點(diǎn)的映射部署。邊緣節(jié)點(diǎn)的映射需求能力用虛擬節(jié)點(diǎn)的擴(kuò)展資源表示,其定義為:

(15)

邊緣節(jié)點(diǎn)按照擴(kuò)展資源大小降序排列,等待映射。根據(jù)文獻(xiàn)[17]提出的鏈路聚合負(fù)載壓力來為排在首位的邊緣節(jié)點(diǎn)選擇合理的物理節(jié)點(diǎn)。負(fù)載應(yīng)力LP由新SN路徑上影響距離加權(quán)的總帶寬要求來度量,其定義為:

(16)

其中,b(lV)是中心節(jié)點(diǎn)與要映射的節(jié)點(diǎn)間的虛擬鏈路帶寬值。選擇最小的LP值,代表選擇被嵌入的物理節(jié)點(diǎn)與中心節(jié)點(diǎn)的鏈路帶寬較大而干擾較小,P表示節(jié)點(diǎn)間的路徑。

3.2 算法流程

該算法的映射步驟如下:

步驟1將虛擬網(wǎng)絡(luò)請求按照收益大小降序排列,選取當(dāng)前收益最大的虛擬請求進(jìn)行映射。

步驟2計算當(dāng)前虛擬網(wǎng)絡(luò)中虛擬節(jié)點(diǎn)的拓?fù)鋭莶⒔敌蚺帕?選取序列中拓?fù)鋭葑畲蟮奶摂M節(jié)點(diǎn)設(shè)為中心節(jié)點(diǎn)。

步驟3遍歷物理網(wǎng)絡(luò),根據(jù)節(jié)點(diǎn)約束條件尋找虛擬中心節(jié)點(diǎn)的可映射物理節(jié)點(diǎn)集合,并選取集合中物理可擴(kuò)展資源最大的物理節(jié)點(diǎn)作為中心節(jié)點(diǎn)的承載節(jié)點(diǎn)。

步驟4將與中心節(jié)點(diǎn)直接相連的虛擬節(jié)點(diǎn)稱為關(guān)聯(lián)節(jié)點(diǎn),將中心節(jié)點(diǎn)的所有關(guān)聯(lián)節(jié)點(diǎn)放在一個集合內(nèi),組成虛擬節(jié)點(diǎn)映射子集,并按其擴(kuò)展資源的大小降序排列。

步驟5選取當(dāng)前序列中排在首位的虛擬節(jié)點(diǎn),尋找該節(jié)點(diǎn)的可映射物理節(jié)點(diǎn)集合,并計算該集合中的LP值,取最小值作為該虛擬節(jié)點(diǎn)的承載節(jié)點(diǎn)進(jìn)行映射,并用最短路徑K算法進(jìn)行中心節(jié)點(diǎn)與該邊緣節(jié)點(diǎn)間的鏈路映射。

步驟6重復(fù)步驟4和步驟5直到子集內(nèi)節(jié)點(diǎn)映射完畢。

步驟7重復(fù)步驟2～步驟5直到該虛擬網(wǎng)絡(luò)請求內(nèi)的節(jié)點(diǎn)映射完畢。

步驟8選出已映射的虛擬節(jié)點(diǎn)中度數(shù)大于等于2的虛擬節(jié)點(diǎn),分別計算物理網(wǎng)絡(luò)中每條鏈路的干擾權(quán)值。在滿足帶寬需求的鏈路中,用最短路徑K算法進(jìn)行子集間的鏈路映射。若無法滿足映射要求則映射失敗,否則更新底層物理網(wǎng)絡(luò)資源狀態(tài)信息。

步驟9重復(fù)步驟1～步驟9直到所有的虛擬請求映射完畢。

4 仿真與結(jié)果分析

本文使用MATLAB對P-AN算法進(jìn)行仿真。為驗證P-AN算法的性能,將其與經(jīng)典的D-ViNE[15]算法進(jìn)行對比。

4.1 仿真場景設(shè)置

利用MATLAB生成具有100個節(jié)點(diǎn)的物理網(wǎng)絡(luò)拓?fù)?節(jié)點(diǎn)隨機(jī)分布在4 km×4 km的范圍內(nèi)。任意兩個物理節(jié)點(diǎn)之間隨機(jī)連接,連接成功率為0.5。物理拓?fù)渚W(wǎng)絡(luò)的節(jié)點(diǎn)與鏈路的大小是均勻分布在[50,100]之間的實數(shù)。

假設(shè)VN請求到達(dá)是一個λ=5的泊松過程。每個VN請求具有指數(shù)分布的生命周期和平均時間單位。在每個VN請求中,虛擬節(jié)點(diǎn)的數(shù)量在[2,20]之間均勻分布且隨機(jī)確定,平均VN連接率為固定值0.5。虛擬節(jié)點(diǎn)的計算能力要求和虛擬鏈路的帶寬要求都均勻分布在[0,50]之間。虛擬節(jié)點(diǎn)位于(25×25)網(wǎng)格上。設(shè)定虛擬節(jié)點(diǎn)的可映射范圍D=800 m。每次仿真運(yùn)行的時間為10 000個時間單位。對于每組實驗,進(jìn)行100次仿真,取實驗結(jié)果的平均值。

4.2 仿真結(jié)果

本文從虛擬請求接受率、平均收益、平均開銷和收益開銷比4個方面來對比兩種算法的仿真結(jié)果,并考慮不同虛擬網(wǎng)絡(luò)規(guī)模對結(jié)果的影響。

圖1展示了兩種算法的虛擬請求接受率,可以看出兩種算法的接受率先隨時間下降而后趨于平穩(wěn)。這是由于映射剛開始時物理資源比較充足,但隨著資源的消耗,接受率逐漸降低直至達(dá)到一個平穩(wěn)的狀態(tài)。由圖1可知,本文算法P-AN與對比算法D-ViNE相比,具有更高的虛擬請求接受率,這是因為P-AN算法充分考慮了在動態(tài)的底層資源中節(jié)點(diǎn)與鏈路映射的協(xié)同作用。

圖1 兩種算法的虛擬請求接受率Fig.1 Virtual request acceptance rate of two algorithms

圖2和圖3分別對比了兩種算法的虛擬網(wǎng)絡(luò)平均收益和平均開銷。圖2顯示了為VN提供物理資源的基礎(chǔ)設(shè)施商的收益隨時間的變化,圖3顯示了一段時間內(nèi)的平均開銷,可以看出兩種算法的收益和開銷均隨著時間的推移而增加直至平穩(wěn),同時本文算法要明顯優(yōu)于對比算法,因為本文提出的P-AN算法在動態(tài)的映射過程中提高了物理資源的利用率,從而提升了收益也節(jié)省了開銷。

圖2 兩種算法的平均收益Fig.2 Average revenue of two algorithms

圖3 兩種算法的平均開銷Fig.3 Average cost of two algorithms

圖4描述了兩種算法的收益開銷比,其表示底層物理資源利用率,可以看出,本文算法的收益開銷比較對比算法高出約60%。由此得出,在相同的資源環(huán)境下,P-AN算法充分考慮了節(jié)點(diǎn)與鏈路的資源特性,使之有較高的物理資源利用效率,提高了映射成功率。

圖5描述了兩種算法在不同虛擬網(wǎng)絡(luò)規(guī)模的情況下映射接受率的變化趨勢,可以看出,當(dāng)虛擬網(wǎng)絡(luò)請求中節(jié)點(diǎn)個數(shù)增加時,虛擬網(wǎng)絡(luò)請求接受率整體下降。這是由于虛擬網(wǎng)絡(luò)請求中的節(jié)點(diǎn)越多,對物理資源的消耗就越多,底層網(wǎng)絡(luò)中的可用資源減少,導(dǎo)致后期生成的虛擬網(wǎng)絡(luò)請求的部署失敗率增加,從而使得虛擬網(wǎng)絡(luò)請求的整體接受率降低。如圖5所示,本文算法在虛擬請求接受率上優(yōu)于對比算法。

圖5 VN規(guī)模對兩種算法虛擬請求接受率的影響Fig.5 Effect of VN size on virtual request acceptance rate of two algorithms

圖6描述了兩種算法在不同虛擬網(wǎng)絡(luò)規(guī)模的情況下收益開銷比的變化趨勢。由于當(dāng)虛擬網(wǎng)絡(luò)請求中節(jié)點(diǎn)個數(shù)增加時,虛擬網(wǎng)絡(luò)請求接受率整體下降,因此收益開銷比也隨之下降。從圖6可以看出,本文算法的收益開銷比高于對比算法,原因在于本文采取節(jié)點(diǎn)鏈路的半?yún)f(xié)同映射,節(jié)點(diǎn)映射時利用拓?fù)鋭菔紫扔成湓谔摂M拓?fù)渲袑π畔⒔粨Q比較重要的節(jié)點(diǎn),提高了映射接受率和物理資源利用率。

圖6 VN規(guī)模對兩種算法收益開銷比的影響Fig.6 Effect of VN size on revenue/cost ratio of two algorithms

5 結(jié)束語

網(wǎng)絡(luò)虛擬化是解決無線網(wǎng)絡(luò)僵化問題的一種有效而具有前景的技術(shù),虛擬網(wǎng)絡(luò)的嵌入則是其重要組成部分。本文對已有虛擬網(wǎng)絡(luò)映射算法進(jìn)行改進(jìn),提出一種新的鄰近節(jié)點(diǎn)分組映射算法,充分考慮動態(tài)底層資源中節(jié)點(diǎn)與鏈路的協(xié)同作用,提高了物理資源利用率、虛擬網(wǎng)絡(luò)的映射成功率以及收益開銷比。下一步將設(shè)計針對節(jié)點(diǎn)和鏈路出現(xiàn)故障時的應(yīng)對機(jī)制和預(yù)測方案,并且實現(xiàn)5G網(wǎng)絡(luò)中異構(gòu)無線網(wǎng)絡(luò)的虛擬化。