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

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

0 概述

隨著智能終端及其相關(guān)業(yè)務(wù)的發(fā)展，未來無線網(wǎng)絡(luò)將呈現(xiàn)密集部署、多樣業(yè)務(wù)、異構(gòu)網(wǎng)絡(luò)并存的多元化形態(tài)。在不斷擴大的網(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è)施進行抽象，并提供統(tǒng)一的可編程接口，將多個彼此隔離且具有不同拓撲結(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)上運行多個異構(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負責向SP提供無線網(wǎng)絡(luò)資源;SP根據(jù)租用和分配的資源自行創(chuàng)建和部署虛擬資源,以滿足端到端的服務(wù)要求[7]。

然而,隨著無線流量和服務(wù)量的巨大增長,無線異構(gòu)網(wǎng)絡(luò)的管理愈加繁瑣,將虛擬化擴展到無線網(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ì)和隨機波動,無線資源的抽象和隔離并不簡單[9-10]。文獻[11]提出一種無線環(huán)境下虛擬網(wǎng)絡(luò)的嵌入框架,但沒有給出解決問題的具體算法。文獻[12]引入基于卡諾圖的頻率和時間塊分配算法,將二維資源分配給VN請求。文獻[13]提出一種重新配置信道從而在無線網(wǎng)狀網(wǎng)絡(luò)中嵌入虛擬網(wǎng)絡(luò)的算法。上述方法都促進了無線網(wǎng)絡(luò)虛擬化的發(fā)展。

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

為解決無線虛擬網(wǎng)絡(luò)的映射問題,同時更有效地利用物理資源,本文提出鄰近節(jié)點分組映射(Packet Mapping of Adjacent Nodes,P-AN)算法。將節(jié)點分為中心節(jié)點和與其相連的邊緣節(jié)點,兩者共同組成映射子集合。在此基礎(chǔ)上,依次進行中心節(jié)點和邊緣節(jié)點的映射,并在所有節(jié)點映射完成后進行鏈路映射,從而提高無線虛擬網(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é)點剩余可用資源和鏈路剩余可用資源。虛擬映射是指虛擬請求到達后根據(jù)物理網(wǎng)絡(luò)可用資源,選取合適的物理節(jié)點和鏈路進行映射。

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

(1)

與節(jié)點相同,不同虛擬請求的鏈路可以映射到同一物理鏈路上,對于每一條鏈路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ò)映射

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

節(jié)點映射過程定義為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é)點nV與待映射的物理節(jié)點nS間的實際矢量距離,D為虛擬節(jié)點的映射范圍矢量值。

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

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

(6)

1.4 收益與開銷

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

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

(7)

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

1.4.2 映射開銷

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

(8)

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

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

(9)

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

2 中心度與拓撲勢分析

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

2.1 節(jié)點中心度

中心度是用來衡量人或物在其關(guān)系網(wǎng)絡(luò)中重要程度的一個指標。本文借鑒社會關(guān)系網(wǎng)中的節(jié)點中心度,來反映節(jié)點在網(wǎng)絡(luò)拓撲中的重要程度。

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

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

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

DCni=drg(ni)

(10)

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

2)節(jié)點的連接強度

在虛擬網(wǎng)絡(luò)拓撲圖GV中,任意節(jié)點ni的連接強度Qni定義為與節(jié)點ni連接的所有鏈路的帶寬之和,定義式如下:

(11)

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

3)節(jié)點的接近度

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

2.2 拓撲勢的引入

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

對于網(wǎng)絡(luò)拓撲G=(N,L),根據(jù)場的勢函數(shù)定義,任意節(jié)點ni的拓撲勢TP可表示為:

(12)

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

將拓撲勢引入虛擬映射網(wǎng)絡(luò)中,其節(jié)點考慮4個屬性:節(jié)點的剩余計算能力大小,該節(jié)點到其他節(jié)點的最短路徑矢量值,該節(jié)點的度數(shù)以及該節(jié)點的連接強度,表示如下:

(13)

由以上定義可知,節(jié)點的拓撲勢值越大代表其附近的連接越密集,那么該節(jié)點在網(wǎng)絡(luò)中的位置越重要,越有可能成為中心節(jié)點。

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

3.1 目標節(jié)點的選取

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

(14)

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

(15)

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

(16)

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

3.2 算法流程

該算法的映射步驟如下:

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

步驟2計算當前虛擬網(wǎng)絡(luò)中虛擬節(jié)點的拓撲勢并降序排列,選取序列中拓撲勢最大的虛擬節(jié)點設(shè)為中心節(jié)點。

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

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

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

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

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

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

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

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

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

4.1 仿真場景設(shè)置

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

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

4.2 仿真結(jié)果

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

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

圖5描述了兩種算法在不同虛擬網(wǎng)絡(luò)規(guī)模的情況下映射接受率的變化趨勢,可以看出,當虛擬網(wǎng)絡(luò)請求中節(jié)點個數(shù)增加時,虛擬網(wǎng)絡(luò)請求接受率整體下降。這是由于虛擬網(wǎng)絡(luò)請求中的節(jié)點越多,對物理資源的消耗就越多,底層網(wǎng)絡(luò)中的可用資源減少,導致后期生成的虛擬網(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ī)模的情況下收益開銷比的變化趨勢。由于當虛擬網(wǎng)絡(luò)請求中節(jié)點個數(shù)增加時,虛擬網(wǎng)絡(luò)請求接受率整體下降,因此收益開銷比也隨之下降。從圖6可以看出,本文算法的收益開銷比高于對比算法,原因在于本文采取節(jié)點鏈路的半?yún)f(xié)同映射,節(jié)點映射時利用拓撲勢首先映射在虛擬拓撲中對信息交換比較重要的節(jié)點,提高了映射接受率和物理資源利用率。

圖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ò)映射算法進行改進,提出一種新的鄰近節(jié)點分組映射算法,充分考慮動態(tài)底層資源中節(jié)點與鏈路的協(xié)同作用,提高了物理資源利用率、虛擬網(wǎng)絡(luò)的映射成功率以及收益開銷比。下一步將設(shè)計針對節(jié)點和鏈路出現(xiàn)故障時的應(yīng)對機制和預(yù)測方案,并且實現(xiàn)5G網(wǎng)絡(luò)中異構(gòu)無線網(wǎng)絡(luò)的虛擬化。