無線虛擬網絡中的鄰近節點分組映射算法

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

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

0 概述

隨著智能終端及其相關業務的發展，未來無線網絡將呈現密集部署、多樣業務、異構網絡并存的多元化形態。在不斷擴大的網絡規模和更為密集的網絡部署下，傳統的因特網網絡架構和協議難以滿足網絡融合的需求，并且面臨網絡僵化的問題[1-2]。網絡虛擬化技術通過對共用的底層基礎設施進行抽象，并提供統一的可編程接口，將多個彼此隔離且具有不同拓撲結構的虛擬網絡同時映射到共用的基礎設施上，為用戶提供差異性服務，實現資源共享，已成為未來網絡關鍵技術之一[3-4]。

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

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

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

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

1 無線虛擬網絡模型和問題描述

1.1 無線網絡模型

1.1.1 無線物理網絡模型

1.1.2 無線虛擬網絡模型

1.2 問題分析

1.2.1 物理網絡可用資源

物理網絡可用資源主要包含節點剩余可用資源和鏈路剩余可用資源。虛擬映射是指虛擬請求到達后根據物理網絡可用資源,選取合適的物理節點和鏈路進行映射。

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

(1)

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

(2)

(3)

1.2.2 鏈路干擾

在無線環境下,無線鏈路間存在干擾。本文只考慮相鄰鏈路間的干擾,定義物理網絡中每一條鏈路的干擾為:

(4)

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

1.3 無線虛擬網絡映射

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

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

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

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

(6)

1.4 收益與開銷

1.4.1 基礎設施商的收益

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

(7)

其中,α和β分別表示平衡節點資源和鏈路帶寬的加權系數,由InP確定。

1.4.2 映射開銷

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

(8)

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

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

(9)

收益開銷比數值較大表示VN的映射集中在一片較小的物理區域內,此時網絡的負載均衡性能比較差。

2 中心度與拓撲勢分析

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

2.1 節點中心度

中心度是用來衡量人或物在其關系網絡中重要程度的一個指標。本文借鑒社會關系網中的節點中心度,來反映節點在網絡拓撲中的重要程度。

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

1)節點的度數

節點的度數DC是指與該節點直接相連的鄰近節點的個數,即:

DCni=drg(ni)

(10)

虛擬節點的度數描述了該節點在網絡中的局部重要性,較高度數的虛擬節點具有更多的相鄰節點和鏈路,可以接受更多的資源請求。

2)節點的連接強度

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

(11)

節點的連接強度反映了目標節點與其他節點相互關聯的可能性。

3)節點的接近度

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

2.2 拓撲勢的引入

場是英國物理學家法拉第在1837年為解釋電磁感應現象而提出的一個概念。受法拉第電磁場思想的啟發,可將網絡拓撲看作是一個包含節點集合以及節點間鏈路集合的場,位于場中的任何節點都將受到其他節點的聯合作用[20]。

對于網絡拓撲G=(N,L),根據場的勢函數定義,任意節點ni的拓撲勢TP可表示為:

(12)

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

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

(13)

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

3 無線虛擬網絡映射算法

3.1 目標節點的選取

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

(14)

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

(15)

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

(16)

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

3.2 算法流程

該算法的映射步驟如下:

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

步驟2計算當前虛擬網絡中虛擬節點的拓撲勢并降序排列,選取序列中拓撲勢最大的虛擬節點設為中心節點。

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

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

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

步驟6重復步驟4和步驟5直到子集內節點映射完畢。

步驟7重復步驟2～步驟5直到該虛擬網絡請求內的節點映射完畢。

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

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

4 仿真與結果分析

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

4.1 仿真場景設置

利用MATLAB生成具有100個節點的物理網絡拓撲,節點隨機分布在4 km×4 km的范圍內。任意兩個物理節點之間隨機連接,連接成功率為0.5。物理拓撲網絡的節點與鏈路的大小是均勻分布在[50,100]之間的實數。

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

4.2 仿真結果

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

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

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

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

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

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

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

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

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

圖6描述了兩種算法在不同虛擬網絡規模的情況下收益開銷比的變化趨勢。由于當虛擬網絡請求中節點個數增加時,虛擬網絡請求接受率整體下降,因此收益開銷比也隨之下降。從圖6可以看出,本文算法的收益開銷比高于對比算法,原因在于本文采取節點鏈路的半協同映射,節點映射時利用拓撲勢首先映射在虛擬拓撲中對信息交換比較重要的節點,提高了映射接受率和物理資源利用率。

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

5 結束語

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