周冬楊,潘顯兵

(1.重慶移通學(xué)院 數(shù)字經(jīng)濟(jì)與信息管理學(xué)院,重慶 401520;2.公共大數(shù)據(jù)安全技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 401420)

0 引 言

物聯(lián)網(wǎng)傳感器的爆炸式增長(zhǎng)和智能設(shè)備的廣泛普及造成移動(dòng)網(wǎng)絡(luò)的流量迅速增加。因便攜式移動(dòng)設(shè)備的計(jì)算和存儲(chǔ)資源容量有限,可以將任務(wù)卸載到遠(yuǎn)程云進(jìn)行處理,但這不可避免地會(huì)導(dǎo)致響應(yīng)延遲,降低用戶體驗(yàn)[1-2]。移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)[3]是一種新興的云架構(gòu),通過(guò)在基站(Base Station,BS)側(cè)部署MEC服務(wù)器,為移動(dòng)用戶提供計(jì)算和存儲(chǔ)資源,顯著縮短響應(yīng)延遲,滿足多樣化的業(yè)務(wù)需求。

網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization,NFV)技術(shù)用虛擬機(jī)中的軟件替代傳統(tǒng)硬件實(shí)現(xiàn)的網(wǎng)絡(luò)功能,稱為虛擬化網(wǎng)絡(luò)功能(Virtual Network Function,VNF)。通常,業(yè)務(wù)流量需要由多個(gè)VNF按照邏輯順序進(jìn)行處理,稱為服務(wù)功能鏈(service Function Chain,SFC)。NFV與MEC的結(jié)合可以減少云服務(wù)提供商(Cloud Service Provider,CSP)核心網(wǎng)的服務(wù)延遲和流量壓力,提供方便靈活的VNF管理,大大降低CSP的運(yùn)營(yíng)費(fèi)用。

由于邊緣云(Edge Cloud,EC)的資源有限,合理分配EC資源以滿足盡可能多的用戶需求是至關(guān)重要的。另外,當(dāng)用戶跨基站移動(dòng)時(shí),需決定由以前的EC或遷移到新的EC執(zhí)行流量處理。第一種情況,SFC沒(méi)有遷移,以犧牲用戶通信時(shí)延為代價(jià)節(jié)約了CSP的網(wǎng)絡(luò)成本。第二種情況,用戶通信延遲是最優(yōu)的,但有潛在的SFC數(shù)據(jù)遷移成本。因此,移動(dòng)用戶的延遲和運(yùn)營(yíng)成本之間存在一個(gè)權(quán)衡。同時(shí),為了讓用戶不能直接感知因SFC遷移過(guò)程造成的服務(wù)中斷,需要進(jìn)行無(wú)縫遷移[4]。

當(dāng)前,部分文獻(xiàn)主要關(guān)注MEC網(wǎng)絡(luò)中VNF的映射[5-6],然而沒(méi)有考慮到用戶的移動(dòng)性,這是MEC網(wǎng)絡(luò)的一個(gè)基本特征。隨著用戶的移動(dòng),SFC固有的映射方法可能會(huì)導(dǎo)致用戶服務(wù)延遲嚴(yán)重惡化。

文獻(xiàn)[2]主要研究用戶移動(dòng)時(shí)VNF的最優(yōu)遷移時(shí)間,但以整體網(wǎng)絡(luò)遷移成本作為優(yōu)化目標(biāo),不能保證單個(gè)移動(dòng)用戶的QoS總是可靠的。文獻(xiàn)[8]使用圖劃分算法最小化VNF在集群之間遷移的數(shù)量,不能保證具有嚴(yán)格延遲要求的用戶服務(wù)。

與上述研究不同,本文綜合考慮遷移成本和服務(wù)時(shí)延兩個(gè)指標(biāo),提出了基于用戶移動(dòng)的SFC無(wú)縫遷移策略。

1 系統(tǒng)模型

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

用無(wú)向圖G=(B∪V,L)表示移動(dòng)邊緣云網(wǎng)絡(luò),其中B為BS集合,V為EC集合,L為BS之間的物理鏈路集合。

每個(gè)基站b∈B起到服務(wù)接入和轉(zhuǎn)發(fā)的作用。對(duì)于每個(gè)ECv∈V,用Cv表示最大的計(jì)算能力,可用于實(shí)現(xiàn)移動(dòng)用戶的SFC。為了節(jié)約CSP的成本,EC的數(shù)量小于BS的數(shù)量,即不是所有的BS都綁定EC。此外,BS和同位EC之間的傳播延遲可以忽略不計(jì)。物理鏈路l∈L是一條高速光纜連接各個(gè)BS,將其表示為五元組{s,d,bl,dl,cl},其中s,d表示源BS和目的地BS,bl是最大帶寬,dl是固有的傳播延遲,cl表示數(shù)據(jù)在鏈路l上的傳輸成本。

1.2 移動(dòng)用戶模型

移動(dòng)用戶i的移動(dòng)軌跡表示為L(zhǎng)i={li(t)}。li(t)∈B為用戶i在時(shí)隙t時(shí)的臨時(shí)位置,此時(shí),通過(guò)最近的BS接入網(wǎng)絡(luò),服務(wù)流量vi(t)通過(guò)相應(yīng)的EC處理。隨著用戶移動(dòng),接入的BS會(huì)進(jìn)行切換。

2 問(wèn)題描述及模型定義

2.1 問(wèn)題描述

假設(shè)每個(gè)移動(dòng)用戶只請(qǐng)求一種SFC類型,且該用戶具有較高的移動(dòng)性和服務(wù)延遲敏感性。當(dāng)用戶i在時(shí)隙t移動(dòng)到一個(gè)新的臨時(shí)位置時(shí),如果業(yè)務(wù)流量vi(t+1)仍然由之前的EC處理,可能會(huì)違反用戶u的端到端延遲容忍。因此,需要根據(jù)用戶u的配置文件確定最優(yōu)EC的位置。也就是說(shuō),當(dāng)用戶跨越EC,即vi(t)≠vi(t+1),需要一個(gè)合理的遷移策略來(lái)決定何時(shí)以及如何選擇相關(guān)的路徑對(duì)SFC進(jìn)行無(wú)縫遷移。

2.2 相關(guān)參數(shù)定義

移動(dòng)用戶請(qǐng)求ri的端到端延遲主要分為四部分:接入延遲、通信延遲、執(zhí)行延遲和遷移延遲。用戶i將服務(wù)請(qǐng)求數(shù)據(jù)Qi,t(以b為單位)傳輸給相應(yīng)的EC進(jìn)行計(jì)算。

接入延遲dacc(i,t):表示請(qǐng)求ri在用戶i和附近的無(wú)線信道與BSli(t)之間傳輸流量數(shù)據(jù)所花費(fèi)的總時(shí)間。無(wú)線信道的最大數(shù)據(jù)傳輸速率ri,t(單位:b/s)為

(1)

式中:W為信道帶寬;Pi為用戶移動(dòng)設(shè)備的發(fā)送功率;gt為時(shí)隙t無(wú)線信道增益;σ2為噪聲功率。因此,接入延遲表示為

(2)

(3)

從本地BSli(t)到選定EC,流量vi(t)的傳播延遲和傳輸延遲表示為

(4)

(5)

則總通信時(shí)延dcom(i,t)為

(6)

執(zhí)行延遲dpro(i,t)是在相應(yīng)的EC上處理用戶數(shù)據(jù)包所花費(fèi)的時(shí)間。設(shè)EC的最大處理能力為fi,t(單位:Hz),處理密度為wi(Hz),CPU分享率是ηi,t,則處理延遲dpro(i,t)表示為[9]

(7)

(8)

(9)

式(9)中:Δt表示時(shí)間間隔的大小。

(10)

(11)

(12)

(13)

未完成數(shù)據(jù)的新的執(zhí)行延遲為

(14)

用zi(t)來(lái)指示是否觸發(fā)遷移:

(15)

因此,最終在時(shí)隙t的遷移延遲dmig(i,t)表示為

(16)

用C(i,t)表示移動(dòng)用戶i的SFCi遷移成本。C(i,t)也是SFCi狀態(tài)數(shù)據(jù)在路徑上的傳輸成本,用以下公式計(jì)算:

(17)

2.3 問(wèn)題模型設(shè)計(jì)

基于t-1時(shí)隙遷移的SFC映射,為時(shí)隙t需遷移的用戶i找到一個(gè)最優(yōu)的遷移路徑集Pi,t,目標(biāo)是使遷移成本與用戶請(qǐng)求ri的端到端延遲之和最小。根據(jù)上一節(jié)的描述,用戶請(qǐng)求ri在時(shí)隙t的總延遲為

D(i,t)=dacc(i,t)+dcom(i,t)+dexe(i,t)+dmig(i,t)

(18)

因此,MEC網(wǎng)絡(luò)中的SFC遷移問(wèn)題用公式(19)表示,約束條件為公式(20)～(25)。

O(S)=α1D(i,t)+α2C(i,t)

(19)

s.t. C1:xp,l,i(t)∈{0,1},yp,l,i(t)∈{0,1}

(20)

C2:D(i,t)≤Di

(21)

(22)

(23)

(24)

(25)

3 算法設(shè)計(jì)

3.1 算法概述

給定一個(gè)MEC網(wǎng)絡(luò)G=(B∪V,L)和一個(gè)支持NFV的用戶請(qǐng)求ri,目標(biāo)是最小化用戶在邊緣網(wǎng)絡(luò)上移動(dòng)時(shí)的請(qǐng)求延遲和網(wǎng)絡(luò)成本。要解決這個(gè)問(wèn)題,有兩個(gè)挑戰(zhàn):一是在整個(gè)時(shí)間范圍T中觸發(fā)SFC遷移的時(shí)機(jī);二是如何選擇SFC的遷移路徑。

3.2 遷移觸發(fā)

通過(guò)設(shè)計(jì)合理的SFC遷移觸發(fā)機(jī)制,可以避免不必要的SFC遷移(為云服務(wù)提供商節(jié)省遷移成本)。當(dāng)服務(wù)請(qǐng)求延遲大于延遲容忍閾值Di時(shí),就會(huì)觸發(fā)SFC跨節(jié)點(diǎn)遷移,而不是在移動(dòng)用戶i跨BS移動(dòng)時(shí)就考慮遷移,從而影響移動(dòng)用戶的QoS。換句話說(shuō),SFC在時(shí)隙t滿足D(i,t)>Di時(shí)遷移將被觸發(fā)。

3.3 遷移算法

SFC的遷移實(shí)際上可以看作是有狀態(tài)數(shù)據(jù)的遷移。給出遷移源EC和目標(biāo)EC后,可以選擇多個(gè)數(shù)據(jù)遷移路徑并發(fā)執(zhí)行,保證服務(wù)數(shù)據(jù)的無(wú)縫遷移。為此,提出了一種基于Dijkstra 的遷移算法。遷移算法(Migration Strategy Algorithm,MSA)的偽代碼如下:

Output 數(shù)據(jù)遷移路徑的集合:Pi,t;

1G′←通過(guò)階段1推導(dǎo)出網(wǎng)絡(luò)加權(quán)圖;

6 return null;

7 end

10 更新網(wǎng)絡(luò)加權(quán)圖G′(階段4);

11 end

12 returnPi,t;

MSA核心思想基于以下四個(gè)階段:

階段1：得到MEC網(wǎng)絡(luò)的加權(quán)圖(代碼第1行)?？紤]到網(wǎng)絡(luò)鏈路的兩個(gè)參數(shù)(數(shù)據(jù)遷移延遲和代價(jià))的不同性質(zhì),將這兩個(gè)參數(shù)集成為一個(gè)新的邊緣參數(shù)。首先將這兩個(gè)參數(shù)歸一化到一個(gè)統(tǒng)一的量級(jí),以得到相同規(guī)格的鏈路傳播延遲和傳播代價(jià)。歸一化公式表示為

(26)

(27)

3.4 算法時(shí)間復(fù)雜度分析

4 性能評(píng)估

4.1 仿真設(shè)置

4.2 結(jié)果分析

平均SFC延遲如圖1所示,MSA算法的結(jié)果是最好的,ODA的性能好于RBA和GBA。隨著移動(dòng)用戶數(shù)量的增加,SFC請(qǐng)求的平均時(shí)延基本保持穩(wěn)定,表明該模型和算法在不同規(guī)模場(chǎng)景下可以有效地改善用戶體驗(yàn)。

圖1 SFC的平均延遲比較Fig.1 Average latency comparison of SFC

整體遷移成本如圖2所示,與移動(dòng)用戶數(shù)量近似成比例。原因是用戶數(shù)量越多,在相同的時(shí)間間隔內(nèi)遷移的數(shù)量就越多。此外,MSA的遷移代價(jià)最小,RBA和GBA代價(jià)最大。

圖2 遷移代價(jià)比較Fig.2 Comparison of migration costs

執(zhí)行時(shí)間如圖3所示,MSA執(zhí)行時(shí)間優(yōu)于GBA算法;與ODA算法相似,隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加,每個(gè)算法的執(zhí)行時(shí)間都會(huì)增加。

圖4顯示了權(quán)重參數(shù)α對(duì)MSA算法的平均延遲和總代價(jià)的影響。通過(guò)將α1從0增加到1,MSA算法更加關(guān)注平均SFC延遲,從而平均SFC延遲減小,然而總體遷移成本會(huì)增加。因此,CSP可以通過(guò)合理調(diào)整兩個(gè)目標(biāo)的權(quán)重參數(shù)來(lái)強(qiáng)調(diào)自己的偏好。

圖4 權(quán)重參數(shù)α對(duì)MSA算法的影響Fig.4 The impact of weight parameter α on MSA algorithm

5 結(jié) 論

本文將MEC網(wǎng)絡(luò)中的SFC遷移問(wèn)題表述為一個(gè)考慮用戶移動(dòng)性的數(shù)學(xué)模型。為了實(shí)現(xiàn)無(wú)縫遷移,提出了MSA算法來(lái)計(jì)算SFC遷移路徑,目標(biāo)是最小化SFC的平均延遲和CSP的遷移成本。仿真結(jié)果表明,考慮用戶移動(dòng)性的MSA算法能夠在保證服務(wù)延遲的同時(shí)有效地降低網(wǎng)絡(luò)成本。