移動邊緣計算中服務(wù)功能鏈的自適應(yīng)優(yōu)化部署策略*

熊澤凱,王素紅,王靖君,祝長鴻,覃團發(fā)

(廣西大學(xué) a.計算機與電子信息學(xué)院;b.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室,南寧 530004)

0 引 言

移動邊緣計算(Mobile Edge Computing,MEC)[1]是一種新興的云架構(gòu),通過在基站(Base Stations,BS)部署MEC服務(wù)器,為移動用戶提供計算和存儲資源,顯著縮短響應(yīng)延遲,滿足多樣化的業(yè)務(wù)需求。在現(xiàn)代移動通信發(fā)展進程中,軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)與網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization,NFV)這兩個技術(shù)發(fā)揮的作用也正日益凸顯。其通過虛擬化技術(shù)和云技術(shù),利用商用服務(wù)器上的軟件應(yīng)用程序取代了需要專用硬件的網(wǎng)絡(luò)功能。其中,在虛擬機中實現(xiàn)的網(wǎng)絡(luò)功能稱為虛擬網(wǎng)絡(luò)功能(VNF);同時,業(yè)務(wù)流量需要由多個VNF按照嚴格的邏輯順序進行處理,該邏輯順序被稱為服務(wù)功能鏈(Service Function Chain,SFC)[2]。目前,將NFV與移動邊緣計算相結(jié)合引起了廣泛的關(guān)注,但由于CPU計算能力、服務(wù)器緩存資源等通信資源具有非常強的耦合性,也為移動邊緣計算網(wǎng)絡(luò)中的功能虛擬化帶來了更大的挑戰(zhàn):首先是邊緣網(wǎng)絡(luò)節(jié)點種類多樣,其通信特征、計算能力和緩存內(nèi)容有較大差異,很難滿足未來網(wǎng)絡(luò)發(fā)展要求[3];其次是隨著移動通信業(yè)務(wù)種類與數(shù)量的增長,對服務(wù)的要求也日益復(fù)雜。

NFV構(gòu)架由物理網(wǎng)絡(luò)層與虛擬網(wǎng)絡(luò)層組成。若要為通信業(yè)務(wù)提供相應(yīng)的服務(wù),則需要完成相對應(yīng)的SFC部署,即在SFC系統(tǒng)性能準則下,在網(wǎng)絡(luò)基礎(chǔ)設(shè)施上設(shè)計VNF的映射和路由方案[4]。如何將SFC高效且準確地映射和部署在底層的物理硬件網(wǎng)絡(luò)上,是目前受到廣泛關(guān)注的課題之一[5-14]。目前的主流研究方向有兩個:一個是將系統(tǒng)成本開銷最小化,從而獲得最大化的收益;另一個則是將通信流量最小化,從而降低系統(tǒng)的通信時延。

由于地理位置的限制,SFC中的各個節(jié)點被分散在整個網(wǎng)絡(luò)中,邊緣節(jié)點之間,核心節(jié)點與邊緣節(jié)點之間有著地理位置上的距離,在地理上分離的節(jié)點之間傳輸數(shù)據(jù)的時間成本很高[15],因此地理位置因素是在邊緣網(wǎng)絡(luò)中部署服務(wù)功能鏈時須考慮的首要問題。其次,由于資源的約束,額外配置對應(yīng)的VNF節(jié)點會造成有限資源的浪費,因此節(jié)點合理化共享和節(jié)點緩存資源的自適應(yīng)更新在SFC部署中尤為重要。此外,文獻[5-14]的研究工作并未考慮有線用戶和無線用戶存在的信道特征差異,有線和無線的傳輸成本相差巨大;同時也缺乏基于時延和開銷折中優(yōu)化的SFC部署研究。

針對上述問題,為更加高效且準確地部署SFC,在考慮不同用戶信道特征選取相應(yīng)的VNF節(jié)點的同時,還需要考慮不同VNF之間的資源協(xié)調(diào)分配,進而提高利用率和準確率,從而降低SFC的網(wǎng)絡(luò)部署成本。因此,在有線用戶和無線用戶都存在業(yè)務(wù)需求的網(wǎng)絡(luò)場景下,本文提出了一種移動邊緣計算中服務(wù)功能鏈的自適應(yīng)優(yōu)化部署策略,并通過實驗仿真驗證了其有效性。

1 網(wǎng)絡(luò)模型

系統(tǒng)模型如圖1所示,包括物理網(wǎng)絡(luò)層和虛擬網(wǎng)絡(luò)層。在物理網(wǎng)絡(luò)層中,存在許多的硬件設(shè)施資源,其中包括了計算資源、緩存資源、有線通信資源和無線接收接發(fā)資源等,能夠為有線用戶和無線用戶提供相應(yīng)的通信業(yè)務(wù)需求服務(wù)。其中,無線用戶需要與鄰近的無線通信設(shè)備進行業(yè)務(wù)請求與接收業(yè)務(wù)服務(wù),有線用戶則通過本地主機進行業(yè)務(wù)請求與接收業(yè)務(wù)服務(wù)。在虛擬網(wǎng)絡(luò)層中,有許多功能不同的VNF節(jié)點,當有業(yè)務(wù)需求的請求時,通過連接不同的VNF節(jié)點以源端點到目的端點的方式形成對應(yīng)的SFC,最后通過映射算法將SFC映射到物理網(wǎng)絡(luò)層中,從而實現(xiàn)對不同用戶的通信業(yè)務(wù)的服務(wù)。

圖1 移動邊緣計算中的SFC部署系統(tǒng)模型

2 問題描述與系統(tǒng)模型

2.1 問題描述

將物理層網(wǎng)絡(luò)可表示為￡=(X,Y),X表示邊緣計算中的物理節(jié)點集合,Y表示物理鏈路的集合。其中,物理鏈路中存在有線鏈路和無線鏈路,有線鏈路可以表示為Y(e,f),無線鏈路可以表示為Yw(e,f)。SFC的請求集合可以將其表示為S={Sk|k=1,2,…,K},K為業(yè)務(wù)請求的數(shù)值。由于每條SFC是由多個功能類型不同的VNF所構(gòu)成的,因此Sk={v1,v2,v3,…,vi|vi∈V},V為多個VNF節(jié)點的集合。由于節(jié)點的異構(gòu),因此需要考慮不同節(jié)點在某個時刻的緩存資源量和映射能力。有線節(jié)點的CPU計算資源為C(ne),緩存資源為M(ne),轉(zhuǎn)發(fā)資源為F(ne);無線節(jié)點的CPU計算資源為C(nf),天線數(shù)目為A(nf),無線緩存資源為B(nf),天線的發(fā)射功率為P(nf)。這里考慮到路徑損耗這個無線信道的衰落問題,其計算公式如下:

(1)

式中:d為距離或范圍,單位為m;f為信號發(fā)射的頻率,單位MHz。在一個時隙系統(tǒng)中,用t∈{1,2…}表示時隙序號。定義VNF的流量改變因子為

(2)

式中:rin和rout為VNF節(jié)點的輸入流量和輸出流量。接下來需要對VNF節(jié)點的緩存資源進行部署。不同業(yè)務(wù)需求所需要的緩存資源也不同,VNF節(jié)點的緩存資源可以表示為M={m1,m2,…,mn},因此VNF節(jié)點當前時刻的請求報告可以定義為R={r|r=(ui,tj,mn)},u為用戶集合。VNF節(jié)點間緩存內(nèi)容的相似度可以表示為

(3)

式中:Ri,k表示在t時刻第i個VNF節(jié)點中緩存內(nèi)容k的請求次數(shù)。相似度γ∈[0,1],其越接近1則說明兩個VNF節(jié)點之間的內(nèi)容越相近,能夠共同處理相同的業(yè)務(wù)請求。令有線鏈路的傳輸時延為Te,則可以表示為

(4)

式中:Lin為發(fā)送的數(shù)據(jù)包長度;Ve為有線節(jié)點之間的有線鏈路傳輸速率。令無線鏈路傳輸時延為Tw,則有

(5)

式中:Vw表示無線鏈路的傳輸速率,利用香農(nóng)公式可以將其表示為

(6)

式中:P為無線發(fā)射功率;h為VNF節(jié)點之間的無線信道系數(shù);B為VNF節(jié)點之間的無線信道帶寬;σ2為接收機噪聲的方差。在時隙t時刻,VNF節(jié)點的可用資源表示為

W=C(t)+M(t)+F(t) 。

(7)

式中:C(t)表示CPU的計算資源;M(t)表示節(jié)點的緩存資源;F(t)為傳輸資源。特別地,對于具有無線傳輸功能的VNF節(jié)點,其可用資源可以表示為

Wf=W+A(t)+Bm(t)+p(t) 。

(8)

式中:A為天線數(shù)目;Bm為無線緩存資源;p為無線傳輸功率。令VNF節(jié)點的部署資源所需成本為

Cn=∑(αC(vi)+βM(vi)+μF(vi)) 。

(9)

式中:α,β,μ分別表示CPU計算資源、VNF節(jié)點緩存資源和轉(zhuǎn)發(fā)資源的加權(quán)系數(shù)。定義Q為系統(tǒng)組件的可靠性,表示為

Q=∏rn。

(10)

式中:rn為系統(tǒng)組件在規(guī)定時隙時段內(nèi)無故障提供業(yè)務(wù)服務(wù)的概率,可以表示為

(11)

式中:ρ表示系統(tǒng)組件正常工作的時間;ξ代表組件需要的修復(fù)時間。令虛擬鏈路集合為L={li,0,li,1,…,li,n},li,i+1表示第i個VNF節(jié)點與第i+1個VNF節(jié)點之間所構(gòu)成的虛擬鏈路。將虛擬鏈路映射至物理網(wǎng)絡(luò)層時,由于功能不同,不同的VNF節(jié)點所組成的鏈路也不同,與之對應(yīng)的映射方法也不同,因此,SFC的映射所需要的成本開銷也不同。令Cm為SFC的映射成本,可以將其表示為

(12)

式中:括號內(nèi)的第一項為VNF節(jié)點vi所映射到的物理節(jié)點上的物理鏈路的映射帶寬資源和業(yè)務(wù)請求的鏈路成本;φ表示的時物理鏈路之間固有的資源消耗;第三項為鏈路帶寬消耗,其中,b為鏈路剩余帶寬,τ表示當前的VNF節(jié)點到下一節(jié)點的跳數(shù)最小值。為了擴展系統(tǒng)帶寬,增加系統(tǒng)的吞吐量,加強網(wǎng)絡(luò)數(shù)據(jù)的處理能力,提高網(wǎng)絡(luò)的靈活性和可用性,在這里考慮各個物理節(jié)點的負載均衡。因此,具有無線功能的物理節(jié)點的資源成本可以表示為

(13)

式中:H(vi)表示VNF節(jié)點vi被請求業(yè)務(wù)所需的無線資源;q表示物理節(jié)點啟用無線虛擬功能所需要的資源成本;A(n)表示無線傳輸所需的天線數(shù)目;Aall(n)表示節(jié)點總共的天線數(shù)目;B(n)表示節(jié)點無線傳輸所需的無線資源塊數(shù);Ball(n)表示節(jié)點擁有的無線資源總塊數(shù);P(n)表示節(jié)點處理業(yè)務(wù)時所占用的無線功率;LP表示路徑損耗功率;Pall(n)表示節(jié)點擁有的最大無線傳輸功率;x∈{0,1},當x為1時表示vi已部署之邊緣節(jié)點,反之則未部署之邊緣節(jié)點。

綜上,整個SFC網(wǎng)絡(luò)部署的總代價可以表示為

(14)

式中:ω1,ω2,ω3分別表示VNF部署所需資源成本、SFC映射成本和物理節(jié)點資源成本的權(quán)重系數(shù);ω4表示節(jié)點之間的傳輸資源的權(quán)重系數(shù);τ表示初始節(jié)點到目的節(jié)點之間的最短條數(shù);b(li)為整個虛擬鏈路所需帶寬資源。

2.2 系統(tǒng)模型

2.2.1 統(tǒng)評價指標

1)SFC部署成功率

定義為在規(guī)定時間內(nèi)到達的SFC請求數(shù)量與成功部署的SFC的數(shù)量的比值,表示為

(15)

式中的分子表示在總運行時間趨向于無窮大的時候,已經(jīng)完成的SFC的部署總量;分母表示在總運行時間趨向于無窮大的時候,SFC請求的總量。

2)系統(tǒng)平均可靠性

由于節(jié)點的部署是獨立的,因此SFC系統(tǒng)的平均可靠性可以表示為

(16)

3)系統(tǒng)平均時延

SFC的傳輸時延為傳輸時延、節(jié)點處理數(shù)據(jù)時延以及虛擬鏈路的部署時延之和,可以表示為

(17)

公式中的第一項表示系統(tǒng)中有線鏈路的傳輸時延總和;第二項表示系統(tǒng)中無線鏈路的傳輸時延總和;第三項表示節(jié)點部署與虛擬鏈路部署時延總和;第四項表示節(jié)點數(shù)據(jù)處理時延,其中,C(n)表示節(jié)點CPU計算能力,Bs表示處理業(yè)務(wù)的內(nèi)容數(shù)據(jù)大小。則系統(tǒng)平均時延可以表示為

(18)

4)系統(tǒng)帶寬消耗

SFC成功部署所需要的帶寬可以表示為

(19)

式中:b為第k條SFC成功部署所需要消耗的帶寬資源。

2.2.2 優(yōu)化目標函數(shù)

在SFC的部署時,為了滿足業(yè)務(wù)需求,需要使部署成本最小。同時,為了提高SFC部署的可靠性,也要降低鏈路的時延。優(yōu)化目標函數(shù)可以表示為

min[μ1T+μ2ψc]。

(20)

式中:μ1表示SFC傳輸時延的加權(quán)系數(shù);μ2表示SFC部署總成本的加權(quán)系數(shù)。

2.2.3 約束條件

SFC中任意的VNF節(jié)點都能夠部署在物理網(wǎng)絡(luò)層的有線或無線的節(jié)點上,由于物理網(wǎng)絡(luò)層的節(jié)點功能異構(gòu),因此只能夠?qū)⒆疃嘁粋€物理節(jié)點進行實例化,即

(21)

用y∈{0,1}表示虛擬鏈路在物理層鏈路的部署方式,當y的值為1時表示li部署至無線鏈路,反之則部署至有線鏈路。為了確保業(yè)務(wù)請求鏈路的通暢,每條SFC虛擬鏈路只能對其對應(yīng)的那一條物理鏈路進行映射,即

(22)

每個物理節(jié)點所映射的VNF節(jié)點所消耗的資源,不能夠超過物理節(jié)點所擁有的最大資源,即

Cvi≤Cnj。

(23)

式中:Cvi表示VNF節(jié)點的映射消耗資源量;Cnj表示物理節(jié)點能夠提供給VNF節(jié)點的映射資源的總量。由于系統(tǒng)帶寬的限制,SFC部署時所需帶寬不能超過該時隙時刻系統(tǒng)中的閑置帶寬,即

(24)

式中:φ∈{0,1},當其值為1時表示已將虛擬鏈路映射至物理網(wǎng)絡(luò)層,反之則表示并未將虛擬鏈路映射至物理網(wǎng)絡(luò)層。規(guī)定時延要小于用戶所能承受的最大等待時延,即

T≤T0(li),?li∈L。

(25)

式中:T0(li)表示用戶所能承受的最大等待時延。而對于VNF節(jié)點而言,還需要滿足以下約束條件:

(26)

(27)

(28)

式中:maxB(j),maxA(j),maxP(j)分別表示節(jié)點能夠提供的最大無線資源塊數(shù)、天線最大數(shù)量和最大的發(fā)射功率。

3 算法介紹

SFC的部署是一種虛擬化網(wǎng)絡(luò)的嵌入問題[16],屬于非確定性多項式問題,求解難度很大,因此,需要降低SFC部署方案的計算復(fù)雜度。在對時隙時刻的隨機業(yè)務(wù)請求到達時,對用戶地理位置和通信方式進行分類,區(qū)分有線和無線通信類型的用戶類型,提出了基于用戶通信類型與位置感知的共享節(jié)點選取算法,判斷所需部署SFC中的VNF位置與通信類型,用于滿足節(jié)點共享的條件,達到減小VNF節(jié)點之間、物理節(jié)點與用戶之間的通信時延和提高通信可靠性。在VNF節(jié)點配置階段,根據(jù)用戶請求處理的數(shù)據(jù)內(nèi)容的新鮮度記錄,自適應(yīng)動態(tài)增加和刪減相應(yīng)的緩存,利用資源感知算法在保證數(shù)據(jù)傳遞可靠性的同時減少服務(wù)節(jié)點的配置個數(shù),降低配置開銷。最后,在服務(wù)功能鏈部署階段,利用基于KSP的功耗感知算法求出最短路徑的集合,得到低時延低功耗的SFC鏈路映射,不但保證了SFC部署的低時延和低功耗,還能減少鏈路重映射。

3.1 基于用戶通信類型與位置感知的共享節(jié)點選取算法

針對用戶的位置與通信類型,將用戶分為有線用戶和無線移動用戶。為保證信息傳輸?shù)目煽啃?有線用戶只能夠和有線的物理邊緣節(jié)點進行信息交互,無線用戶只能夠和無線的物理邊緣節(jié)點進行信息交互,但是各個有線或無線的邊緣物理節(jié)點都能夠進行信息傳輸與處理。為此,則需要感知VNF節(jié)點的位置與通信方式是否滿足用戶的通信類型。當有SFC業(yè)務(wù)請求時,首先判斷用戶的通信類型和地理位置,便于尋找各類用戶所對應(yīng)距離最短的VNF節(jié)點。接著再判斷整個SFC中的VNF節(jié)點是否存在著功能互斥,在這里將共享節(jié)點的內(nèi)容相似度門限設(shè)為0.85,這樣在確保節(jié)點能夠進行共享的同時,還能夠使得共享后的節(jié)點可以高效地處理相同類型業(yè)務(wù),不但保證了系統(tǒng)具有較高的魯棒性,還能減少額外節(jié)點的配置。最后根據(jù)流量因子乘積是否滿足共享條件,求出進行共享的VNF節(jié)點集合。

基于用戶通信類型與位置感知的共享節(jié)點選取算法(算法1)具體步驟如下:

輸入:物理層邊緣網(wǎng)絡(luò)信息￡,用戶通信類型與位置信息

輸出:共享VNF節(jié)點集合Group

IF用戶為無線用戶

確定滿足條件且離用戶最近的無線VNF節(jié)點作為源節(jié)點

ELSE

將有線用戶的VNF節(jié)點作為源節(jié)點

FOR除源節(jié)點外所有待部署的VNF節(jié)點

IF當前VNF節(jié)點滿足初始共享條件(γ> 0.85)

進入下一步共享操作

ELSE

退出共享

END IF

END FOR

IF 該時刻下SFC具有無線功能

FORSk中所有待部署的VNF

IF當前位置滿足無線和有線功能性約束的VNF集合為連續(xù)VNF節(jié)點所組成

該VNF集合進入待合并隊列Group’

ELSE

解散該VNF集合

FOR Group’中的每個VNF集合

IF有線和無線VNF節(jié)點都滿足δ(vii)>1&δ(vii+1)<1&δ(vii+2)<1

該VNF進入合并隊列Group

ELSE

解散當前Group’集合

END IF

END FOR

ELSE

FORSk中的每一個有線VNF節(jié)點

IF當前位置滿足有線功能性約束的VNF集合為連續(xù)VNF節(jié)點所組成

該VNF集合進入待合并隊列Group’

ELSE

解散該VNF集合

FOR Group’中每個VNF集合

IF有線VNF節(jié)點滿足δ(vii)>1&δ(vii+1)<1&δ(vii+2)<1

該VNF進入合并隊列Group

ELSE

解散當前Group’集合

END IF

END FOR

END IF

3.2 基于緩存內(nèi)容新鮮度的節(jié)點配置算法

在對用戶的通信類型與地理位置進行對應(yīng)的VNF節(jié)點感知后,就要對SFC中相應(yīng)的節(jié)點進行配置。本文提出了基于緩存內(nèi)容新鮮度的節(jié)點自適應(yīng)配置算法,在主動緩存放置的時段中,如果用戶發(fā)出了請求Sk,且最近的對應(yīng)VNF節(jié)點中沒有相應(yīng)的緩存內(nèi)容,則進行緩存內(nèi)容的替換,并將該緩存內(nèi)容的新鮮度數(shù)值賦值為10。接著遍歷整個緩存內(nèi)容的新鮮度矩陣,對VNF節(jié)點內(nèi)的3次請求都未利用到的緩存內(nèi)容資源塊的新鮮度數(shù)值減去1,最后刪除新鮮度數(shù)值低于閾值所對應(yīng)的緩存內(nèi)容資源(本文設(shè)定閾值為6)。這樣不僅能夠保證部署SFC的效益值更高,減少了配置VNF節(jié)點的個數(shù),還能夠提高緩存資源的利用率。

基于緩存內(nèi)容新鮮度的節(jié)點配置算法(算法2)具體步驟如下:

輸入:VNF節(jié)點緩存內(nèi)容矩陣Z,Sk請求緩存內(nèi)容B(k),新鮮度矩陣D

輸出:更新的VNF節(jié)點緩存內(nèi)容矩陣Z

IFB(k)被請求且節(jié)點并未有相應(yīng)緩存

THEN

將B(k)緩存內(nèi)容添加至矩陣Z

THEN

將D中B(k)所對應(yīng)的新鮮度賦值為10

THEN

FORZ中的所有緩存內(nèi)容

IF 該緩存內(nèi)容已有3次未被利用

在新鮮度矩陣中對應(yīng)的新鮮度數(shù)值減1

END IF

END FOR

FOR 新鮮度數(shù)值矩陣Z

IF 新鮮度數(shù)值<6

在Z中刪除對應(yīng)的緩存內(nèi)容

END IF

END FOR

更新VNF節(jié)點的緩存內(nèi)容矩陣Z

END IF

3.3 基于KSP的功耗感知虛擬鏈路映射算法

在VNF節(jié)點選取和配置成功后,需要對相應(yīng)的鏈路進行虛擬映射。首先,將該時隙中的帶寬矩陣轉(zhuǎn)化為稀疏矩陣,刪除不滿足帶寬要求和所選取VNF節(jié)點之間互不相通的鏈路,以便節(jié)省帶寬資源,提高傳輸效率。利用基于KSP的功耗感知鏈路映射算法,得到時延與功耗均低于系統(tǒng)約束條件的虛擬鏈路集合,進而找到最優(yōu)的映射鏈路。

基于KSP的功耗感知虛擬鏈路映射算法(算法3)具體步驟如下:

輸入:待部署的所有SFC映射方案集合Sk′

輸出:所要部署SFC的映射方案Sk

FOR待部署的所有SFC映射方案集合Sk′

利用KSP算法計算相應(yīng)加權(quán)路徑的功耗矩陣

求出最短路徑跳數(shù)τ和組成鏈路的VNF節(jié)點集合

計算重復(fù)映射鏈路數(shù)量

根據(jù)最短路徑更新集合Sk′

END FOR

FOR 更新后的集合Sk′

IF該Sk不具有無線功能

FORSk中的VNF節(jié)點

計算Sk功耗

計算Sk時延

END FOR

IF該Sk時延>用戶時延約束條件

刪除該Sk

ELSE

將該Sk放入新的集合Sk″

END IF

ELSE

FORSk中的VNF節(jié)點

計算Sk有線和無線功耗總和

計算Sk時延

END FOR

IF該Sk時延>用戶時延約束條件

刪除該Sk

ELSE

將該Sk放入新的集合Sk″

END IF

END FOR

FOR滿足用戶時延約束條件的待部署SFC映射方案集合Sk″

IF該Sk功耗為最小

映射成功,更新鏈路剩余資源

ELSE

映射不成功,刪除該Sk的部署

END FOR

4 實驗仿真

本節(jié)對本文所提方案與隨機選擇算法、遍歷選擇算法和貪婪算法(Greedy Algorithm,GA)這三種基準方案進行系統(tǒng)的評估比較,考慮了SFC部署的平均資源消耗、平均時延、平均可靠性、鏈路重映射數(shù)量、平均帶寬消耗、規(guī)定時隙內(nèi)映射成功率、算法時間復(fù)雜度、有線和無線業(yè)務(wù)請求數(shù)量與SFC部署成功率的關(guān)系等作為系統(tǒng)性能的評價指標。其中,隨機選擇算法不進行VNF節(jié)點的共享,僅根據(jù)業(yè)務(wù)請求類型隨機選擇可用節(jié)點;遍歷選擇算法和貪婪算法都進行VNF節(jié)點的共享,兩者不同之處在于遍歷選擇算法會根據(jù)每一條業(yè)務(wù)請求進行全局遍歷尋優(yōu),進而選擇下一最優(yōu)節(jié)點,而貪婪算法只對當前VNF節(jié)點的下一節(jié)點集合進行遍歷尋優(yōu),選擇最優(yōu)的下一個VNF節(jié)點。此外,所進行對比的三種算法均不進行節(jié)點緩存內(nèi)容的自適應(yīng)更新和鏈路映射時最短路徑的選擇,也不考慮負載均衡。

在仿真平臺上,設(shè)置邊緣網(wǎng)絡(luò)節(jié)點數(shù)為100,其中隨機的40個節(jié)點擁有無線功能。隨機產(chǎn)生用戶數(shù)量和用戶的通信業(yè)務(wù)需求,用戶分為有線用戶和無線用戶,無線用戶只能夠與無線物理節(jié)點進行信息交互。SFC服從到達率為0.05的泊松分布,且為動態(tài)到達模式。為了減少其他因素的影響,將300次實驗后的平均值作為仿真的最終結(jié)果,每次實驗有40 000個時隙單位,且每個資源塊是不可分割的。相應(yīng)的參數(shù)配置如表1所示。

表1 仿真參數(shù)設(shè)置

圖2為在各個方案下的SFC成功部署數(shù)量對平均資源消耗、平均時延、平均可靠性、平均帶寬消耗和鏈路重映射數(shù)量這5個系統(tǒng)評價指標的影響情況。圖2(a)為平均資源消耗對比,可見隨著SFC成功部署數(shù)量的增加,本文方案的平均資源消耗均小于另外三種方法。隨機選擇算法由于沒有考慮節(jié)點的共享,且隨機選擇的無線節(jié)點數(shù)量過多,導(dǎo)致路徑損耗較大,故資源消耗最多。遍歷選擇算法和貪婪算法雖然考慮了節(jié)點的共享,但都忽略了負載均衡,且每次確定最佳的下一節(jié)點都要進行一次遍歷,故資源消耗較多。本文方案以邊緣節(jié)點資源有限作為前提,通過節(jié)點的共享和緩存資源的自適應(yīng)動態(tài)調(diào)整,減少了VNF的配置個數(shù)和節(jié)點之間的跳數(shù),故平均資源消耗最少。圖2(b)為平均時延對比,可見隨著SFC成功部署數(shù)量的增加,本文方案的平均時延大都優(yōu)于另外三種算法。隨機選擇算法由于缺少了節(jié)點的共享,故平均時延最高。貪婪算法是局部最優(yōu)的選擇算法,在沒達到局部最優(yōu)之前,平均時延略小于本文算法,但達到了局部最優(yōu)之后,其跟遍歷選擇算法一樣,都需要對全局進行遍歷尋優(yōu),增加了相應(yīng)的時延。本文將物理節(jié)點共享給更多的VNF節(jié)點,且利用基于新鮮度的緩存替換策略,將VNF節(jié)點之間的數(shù)據(jù)變成節(jié)點內(nèi)部數(shù)據(jù)進行傳輸,在緩存資源獲取時不需要每次都進行遍歷尋優(yōu),且在SFC映射時將時延權(quán)重作為評判標準,故平均時延最低。圖2(c)為平均可靠性對比,可見除了隨機選擇算法,其他的三種方案的平均可靠性均高于0.8。因為這三種方案都在共享節(jié)點時將可靠性權(quán)重作為考慮的依據(jù),通過優(yōu)先選擇高可靠性的節(jié)點來提高平均可靠性。本文方案還考慮了用戶的地理位置和通信特性,區(qū)分與用戶對接的鄰近節(jié)點的通信特性和緩存特性,故有更高的平均可靠性。圖2(d)為平均帶寬消耗對比,可見本文方案由于將節(jié)點進行共享并利用了緩存自適應(yīng)動態(tài)調(diào)整策略,且在SFC映射時考慮了負載均衡,故平均帶寬開銷均低于另外三種方案。隨機算法由于為對節(jié)點進行共享,且未考慮負載均衡,故平均帶寬開銷最大。遍歷算法和貪婪算法雖然考慮了節(jié)點的共享,但在SFC映射時未考慮節(jié)點最短路徑的選擇,故平均帶寬消耗較高。圖2(e)為各方案鏈路重映射數(shù)量隨SFC成功部署數(shù)量的變化關(guān)系,可見本文利用基于KSP的功耗感知映射算法,在尋找最短路徑時利用功耗矩陣作為約束條件,能夠降低鏈路重映射的數(shù)量,故本文方案的鏈路重映射數(shù)量低于另外三種方案。

圖3為各個方案穩(wěn)定性的對比實驗結(jié)果。為衡量部署方案的魯棒性和穩(wěn)定性,將以規(guī)定時隙內(nèi)的SFC映射成功率、算法時間復(fù)雜度和不同類型、不同數(shù)量的業(yè)務(wù)請求條件下的SFC部署成功率作為評價指標。圖3(a)為在規(guī)定的40 000個時隙單位內(nèi)四種算法的SFC映射成功率對比,可見隨機選擇算法由于沒有考慮節(jié)點的資源共享,也沒有考慮負載均衡,因此增大了時延和資源消耗,故映射成功率最低。遍歷選擇和貪婪算法雖然考慮了節(jié)點的共享,但未綜合考慮全局的時延與功耗,只考慮了局部的最優(yōu),因此在SFC部署中不能夠同時保證時延和功耗,故映射成功率也低于本文算法。圖3(b)為所進行的300次實驗中四種方案的算法時間對比,可以看出遍歷選擇和貪婪算法的時間復(fù)雜度較高。這是因為遍歷選擇和貪婪選擇都需要對每一個當前節(jié)點的下一跳節(jié)點進行遍歷尋優(yōu),進而耗費了大量時間。隨機選擇算法由于其算法流程過于簡單,故算法時間復(fù)雜度最低,但對比于本文所提方案,其系統(tǒng)性能指標均存在較大的劣勢。本文所提方案由于考慮了最佳節(jié)點的選取和節(jié)點緩存資源的自適應(yīng)更新,不需要頻繁對節(jié)點的選擇進行遍歷尋優(yōu),極大地降低了最短路徑的生成時間,故相較于遍歷選擇和貪婪算法,本文所提方案能夠在保證系統(tǒng)性能的同時極大降低算法的時間復(fù)雜度。圖3(c)和圖3(d)分別為有線業(yè)務(wù)請求的SFC部署成功率對比和混合無線與有線業(yè)務(wù)請求的SFC部署成功率對比,可見在只有有線業(yè)務(wù)請求的情況下,由于隨機選擇算法沒有共享節(jié)點,故SFC的部署需要消耗更多的資源,且時延也得不到滿足,故SFC部署成功率低于另外三個方案。遍歷選擇和貪婪算法由于沒有從全局考慮時延和功耗,故SFC部署成功率略低于本文所提方案。在混合了有線和無線業(yè)務(wù)請求的情況下,由于沒有根據(jù)用戶的地理位置和通信特征進行節(jié)點的選取,也沒有根據(jù)業(yè)務(wù)內(nèi)容的新鮮度對節(jié)點進行緩存內(nèi)容的自適應(yīng)動態(tài)調(diào)整,故另外三種方案的SFC部署成功率都明顯低于本文所提方案。由于考慮了業(yè)務(wù)類型和用戶地理位置和通信特征,且從全局對時延和功耗進行加權(quán)約束,本文方案無論是在有線業(yè)務(wù)處理場景下或是混合有線無線業(yè)務(wù)處理場景下都有著較穩(wěn)定的SFC部署成功率。

5 結(jié) 論

本文研究了移動邊緣計算中面向用戶的服務(wù)功能鏈部署問題,提出了針對服務(wù)功能鏈的支出成本與時延聯(lián)合自適應(yīng)優(yōu)化的部署策略。實驗結(jié)果表明,在5G移動邊緣計算場景中,相比于已有方案,該方法能夠在有效降低部署成本與時延的同時對不同類型用戶的服務(wù)功能鏈部署做到自適應(yīng)優(yōu)化,提高了服務(wù)功能鏈的部署成功率和穩(wěn)定性。