基于網(wǎng)絡(luò)切片的移動霧計算系統(tǒng)資源調(diào)度策略

張小佳，文 鵬，唐勝達

(1.廣西師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，廣西 桂林 541006；2.桂林學(xué)院理工學(xué)院，廣西 桂林 541006)

0 引言

目前，世界各地重大數(shù)字化技術(shù)的發(fā)展為人們提供各種各樣的應(yīng)用和服務(wù)，如智慧城市(Smart City，SC)、車對車(Vehicle to Vehicle，V2V)通信、虛擬現(xiàn)實(Virtual Reality，VR)/增強現(xiàn)實(Augmented Reality，AR)等[1].網(wǎng)絡(luò)設(shè)計和實現(xiàn)可以同時提供所有這些應(yīng)用的基本連接和性能要求，但這種網(wǎng)絡(luò)場景只具有單一的網(wǎng)絡(luò)功能集，不僅非常復(fù)雜，而且成本高得令人望而卻步，同時不同場景下的應(yīng)用程序具有不同的服務(wù)質(zhì)量(Quality of Service，QoS)要求和傳輸特性.例如，eMMB類別中的視頻點播流應(yīng)用需要非常高的帶寬，并能夠傳輸大量內(nèi)容，而物聯(lián)網(wǎng)(Internet of Thing，IoT)，通常應(yīng)具有大量低吞吐量設(shè)備。這些用例之間的差異表明傳統(tǒng)網(wǎng)絡(luò)一刀切的方法并不能滿足所有垂直服務(wù)的不同需求.為了滿足這些差異性的需求，網(wǎng)絡(luò)切片技術(shù)(Network Slicing，NS)應(yīng)運而生.

網(wǎng)絡(luò)切片技術(shù)本質(zhì)是將運營商的物理網(wǎng)絡(luò)分割成多個隔離的邏輯網(wǎng)絡(luò)[2].類似于云計算系統(tǒng)成功使用的服務(wù)器虛擬化技術(shù)，網(wǎng)絡(luò)切片旨在構(gòu)建一種虛擬化形式，將共享物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施劃分為多個端到端級別的邏輯網(wǎng)絡(luò)，允許流量分組和租戶流量隔離.網(wǎng)絡(luò)切片是5G網(wǎng)絡(luò)的關(guān)鍵推動因素之一，垂直服務(wù)提供商可以根據(jù)其服務(wù)需求靈活部署應(yīng)用程序和服務(wù).換句話說，網(wǎng)絡(luò)切片提供了一種網(wǎng)絡(luò)即服務(wù)(Network-as-a-Service，NaaS)模型，它允許服務(wù)提供商根據(jù)自己的需求構(gòu)建和設(shè)置網(wǎng)絡(luò)基礎(chǔ)設(shè)施，并針對多樣化和復(fù)雜化的場景進行定制.

移動霧計算系統(tǒng)(Mobile Fog Computing，MFC)是為實現(xiàn)物聯(lián)網(wǎng)提供計算、存儲、控制和聯(lián)網(wǎng)能力的新興架構(gòu)，能夠很好地配合網(wǎng)絡(luò)切片來應(yīng)對具有差異化的應(yīng)用場景.與移動云計算(Mobile Cloud Computing，MCC)相比，傳統(tǒng)的中心云通常位于遠離用戶的位置.對于延遲敏感的移動應(yīng)用程序，例如高質(zhì)量視頻流、移動游戲等，卸載到遠程中央云可能不是一個完美的解決方案.因此，在未來的移動網(wǎng)絡(luò)，尤其是新興的物聯(lián)網(wǎng)范式，傳統(tǒng)的中心云正面臨越來越大的挑戰(zhàn).

為了克服這些缺點，霧計算，也稱為“邊緣云”[3]作為替代的解決方案出現(xiàn)，可以隨時隨地為移動用戶提供無處不在的計算服務(wù)，并支持未來的云服務(wù)和應(yīng)用程序，特別是對延遲和高彈性有嚴格要求的物聯(lián)網(wǎng)應(yīng)用程序[4].在移動霧計算系統(tǒng)中，將資源虛擬化[5]，即將物理資源抽象化，并根據(jù)抽象資源的分配結(jié)果來調(diào)度物理資源.具體來說，為了節(jié)省霧節(jié)點有限的資源，同時使移動用戶體驗更快的響應(yīng)時間，到達系統(tǒng)的計算請求不再只能分配到一臺物理機上，而是可將一臺或多臺物理機的計算資源虛擬化成一臺虛擬機(Virtual Machine，VM)來運行該計算請求，然后根據(jù)系統(tǒng)中可用的虛擬機數(shù)量，合理分配資源.所謂的VM是一種虛擬環(huán)境，其工作方式類似于計算機中的計算機，它運行在其主機的一個隔離分區(qū)上，擁有自己的CPU能力、內(nèi)存、操作系統(tǒng)(如Windows、Linux、macOS)和其他資源，稱為管理程序的軟件將機器的資源與硬件分開，并適當(dāng)?shù)嘏渲盟鼈?，以便虛擬機可以使用它們.

基于移動用戶請求，系統(tǒng)可以立即實例化一個或多個自定義VM來遠程執(zhí)行應(yīng)用程序[6].當(dāng)移動用戶的計算請求到達系統(tǒng)時，用戶根據(jù)計算請求類型分別接入各個切片，系統(tǒng)決定是否接受，若系統(tǒng)決定接受，則系統(tǒng)分配一定數(shù)量VM來處理計算請求，隨即計算結(jié)果被傳送回服務(wù)用戶.

對延時敏感要求高的移動用戶來講，計算請求延遲是系統(tǒng)采取動作時需要考慮的關(guān)鍵指標(biāo)，以確保計算請求順利完成.事實上，計算請求延遲包括計算延遲和傳輸延遲.計算延遲是計算卸載計算請求的持續(xù)時間，傳輸延遲代表發(fā)送計算請求并反饋計算結(jié)果的時間和持續(xù)時間.由于發(fā)送計算結(jié)果所產(chǎn)生的延遲比計算請求的延遲小得多，在這里可以忽略.在本文分析中可以忽略發(fā)送計算結(jié)果的傳輸延遲.僅考慮計算請求的計算延遲和發(fā)送計算請求的傳輸延遲.計算延遲受分配的VM數(shù)的影響，計算能力隨分配VM數(shù)的增加而增加，從而相應(yīng)地降低了計算延遲，同時系統(tǒng)要產(chǎn)生因處理計算請求而占用VM的成本.考慮上述因素，需要提高系統(tǒng)在計算請求卸載中的長期獎勵，包括傳輸延遲、計算延遲、可用VM、移動用戶的滿意度以及考慮網(wǎng)絡(luò)切片多樣性特征.為了解決這一問題，需設(shè)計一個適當(dāng)?shù)腣M資源分配方案，作出適當(dāng)?shù)男遁d決定，從而將系統(tǒng)的長期獎勵最大化.

1 相關(guān)工作

網(wǎng)絡(luò)切片作為5G通信網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，一直受到研究學(xué)者的關(guān)注.近年來，有大量文獻對網(wǎng)絡(luò)切片技術(shù)進行了研究.項弘禹等[7]將網(wǎng)絡(luò)切片和邊緣計算融合，提出了基于邊緣計算的接入網(wǎng)絡(luò)切片，能夠滿足5G中廣泛的用例和商業(yè)模型，使得運營商能夠根據(jù)第三方需求和網(wǎng)絡(luò)狀況以低成本為用戶靈活提供個性化的網(wǎng)絡(luò)服務(wù).FARACI等[8]對配備多接入邊緣計算(Mobile Edge Computation，MEC)設(shè)施的無人機(Unmanned Aerial Vehicles，UAV)擴展的5G網(wǎng)絡(luò)切片進行研究，提出了一個框架，系統(tǒng)可能將工作卸載到其他UAV，將根據(jù)功耗、工作損失和產(chǎn)生的延遲定義的目標(biāo)函數(shù)最大化.XIAO等[9]研究了具有能量收集功能的可擴展霧計算系統(tǒng)的動態(tài)網(wǎng)絡(luò)切片，提出了一種基于置信狀態(tài)部分可觀察馬爾可夫決策過程的算法，來實現(xiàn)所有霧節(jié)點之間的最優(yōu)資源切片結(jié)構(gòu).XIONG等[10]為了解決霧資源以及網(wǎng)絡(luò)流量利用率不高的問題，提出了一種車載霧無線接入網(wǎng)絡(luò)中的智能切片調(diào)度方案.

然而以上文獻都沒有考慮將網(wǎng)絡(luò)切片與霧計算結(jié)合起來，在構(gòu)成的基于網(wǎng)絡(luò)切片的MFC系統(tǒng)中進行最優(yōu)的計算資源調(diào)度.本文提出一個基于網(wǎng)絡(luò)切片的MFC系統(tǒng)的資源最優(yōu)分配方案.網(wǎng)絡(luò)切片借助網(wǎng)絡(luò)功能虛擬化(Network Function Virtualization，NFV)技術(shù)，實現(xiàn)軟硬件解耦，將物理資源抽象成虛擬資源為VM，構(gòu)成霧計算系統(tǒng)資源池.針對到達系統(tǒng)的計算請求，首先為其適配切片，再根據(jù)服務(wù)需求和當(dāng)前的計算資源情況為其配置共享資源.采取最優(yōu)的VM資源調(diào)度策略，使系統(tǒng)的期望獎勵最大化.

將最優(yōu)資源分配問題轉(zhuǎn)化為求解系統(tǒng)的最大化長期獎勵問題，進而將最優(yōu)決策過程表示為半馬爾可夫決策過程(Semi-Markov Decision Process，SMDP)，通過值迭代算法求解SMDP問題，得到最優(yōu)分配方案.

2 系統(tǒng)模型與資源分配問題

本文使用的主要符號及說明見表1.本文主要考慮MFC系統(tǒng)中的資源分配問題.

表1 系統(tǒng)框架中的符號及說明

2.1 MFC系統(tǒng)VM資源分配模型

基于網(wǎng)絡(luò)切片的MFC系統(tǒng)如圖1所示.在MFC系統(tǒng)中密集部署大量小型服務(wù)器，每臺物理機的計算資源可虛擬化成VM，為移動用戶提供計算能力和存儲功能，共同構(gòu)成MFC系統(tǒng)中的VM資源池.用K表示MFC資源池中VM數(shù)量，K<∞.

圖1 MFC系統(tǒng)VM資源分配模型

將網(wǎng)絡(luò)切片劃分為高優(yōu)先級和低優(yōu)先級兩類，高優(yōu)先級網(wǎng)絡(luò)切片，主要運行一些要求較低時延的計算請求；低優(yōu)先級網(wǎng)絡(luò)切片主要接入對用戶安全性、私密性有較高要求的計算請求.為了方便表示，使用#表示優(yōu)先級，具體地，#=h表示高優(yōu)先級，#=l表示低優(yōu)先級.當(dāng)移動用戶產(chǎn)生的計算請求達到系統(tǒng)時，接入對應(yīng)的網(wǎng)絡(luò)切片.假設(shè)計算請求的到達和完成服從泊松分布，以便在不損失一般性的情況下形成VM資源分配的動態(tài)過程.用λ#,μ#分別表示類型為#的計算請求的到達速率和服務(wù)速率,#∈{h,l}.

在MFC系統(tǒng)中，當(dāng)移動用戶產(chǎn)生新的計算請求時，由于自身的計算能力與存儲功能有限，用戶選擇將計算請求傳輸給MFC系統(tǒng)，系統(tǒng)根據(jù)資源池中空閑的VM數(shù)作出相應(yīng)決策.假定每次只有單個計算請求到達，設(shè)類型為計算請求在本地卸載的計算時間為T#，即計算請求不傳輸給MFC系統(tǒng)在本地設(shè)備上卸載的時間.

在每個計算請求到達系統(tǒng)時，系統(tǒng)根據(jù)當(dāng)前狀態(tài)來確定是否卸載計算請求，當(dāng)系統(tǒng)決定卸載計算請求時，則分配一定的VM資源，然后系統(tǒng)將計算結(jié)果返回給移動用戶.計算請求的卸載時間受分配的VM數(shù)影響，用f(i)表示分配i個VM的計算時間，具體可表示為f(i)=1/(iμ#).若系統(tǒng)的資源不足，系統(tǒng)就會考慮拒絕計算請求，用M表示空閑的VM數(shù).不失一般性，設(shè)相同優(yōu)先級的計算請求都具有相同的傳輸時間δ#與本地處理時間T#.

2.2 VM資源分配問題

當(dāng)計算請求到達系統(tǒng)時，接入對應(yīng)類型的網(wǎng)絡(luò)切片.系統(tǒng)根據(jù)資源池中的VM資源數(shù)，決定是否立即處理.若系統(tǒng)決定立即處理它，則將確定分配給此計算請求的VM數(shù)量；如果系統(tǒng)VM數(shù)量不足或者成本函數(shù)C太大，則會拒絕請求，此時系統(tǒng)會給出丟棄計算請求這一動作相應(yīng)的懲罰ξ#.一旦系統(tǒng)接受計算請求，就會立即獲得一個即時收入I，具體來說，即時收入就是系統(tǒng)關(guān)于計算時間的函數(shù)，可表示為I=g(T#-f(i)).相對地，系統(tǒng)要產(chǎn)生成本C，作為使用VM的費用.C是關(guān)于使用VM個數(shù)的函數(shù)，可表示為C=h(i).

因此，本文考慮的系統(tǒng)獎勵是凈獎勵R，可表示為R=I-C.考慮到移動用戶的計算請求的動態(tài)特性，當(dāng)前狀態(tài)下的動作可能會直接導(dǎo)致下一個狀態(tài)相當(dāng)大的變化，從而對系統(tǒng)的期望總獎勵產(chǎn)生嚴重影響.換句話說，從長遠來看，最大化當(dāng)前狀態(tài)獎勵的動作可能會變得不明智，尤其是系統(tǒng)資源相對稀缺的情況.因此，本文的目標(biāo)是通過適當(dāng)?shù)胤峙銶FC系統(tǒng)中的VM資源，使長期期望的總獎勵V最大化.

3 SMDP框架

在MFC系統(tǒng)中，可用VM的總數(shù)受到事件的影響，例如計算請求的到達和離開.當(dāng)移動用戶的計算請求到達MFC系統(tǒng)時，系統(tǒng)必須決定是接受還是拒絕.如果接受計算請求，則根據(jù)當(dāng)前可用資源分配VM.通過計算請求卸載決策，系統(tǒng)實現(xiàn)了依賴于傳輸延遲、計算延遲、當(dāng)前可用VM、用戶滿意度和計算請求的多樣性特征的獎勵.

下面使用SMDP模型來描述MFC系統(tǒng).在SMDP模型中，狀態(tài)代表一個集合，由不同數(shù)量的VM分配的計算請求數(shù)量和不同事件下可用的VM的數(shù)量組成；動作反映不同事件下分配的VM的數(shù)量；獎勵表示MFC系統(tǒng)在不同狀態(tài)和動作下的效益；轉(zhuǎn)移概率刻畫在不同動作下狀態(tài)轉(zhuǎn)換的概率.接下來，將MFC系統(tǒng)模型轉(zhuǎn)化為SMDP.

3.1 狀態(tài)集

設(shè)MFC系統(tǒng)中的狀態(tài)集合為

S={s│s=(nh,nl,M,e)},

(1)

(2)

(3)

3.2 動作集

(4)

3.3 獎勵函數(shù)

本文中MFC系統(tǒng)的獎勵包含了移動用戶的滿意度，類似于文獻[11]，定義Sigmoidal函數(shù)來描述移動用戶滿意度.

(5)

其中，U(a)表示MFC系統(tǒng)執(zhí)行動作a的滿意度，參數(shù)ω1和ω2由用戶對QoS的需求來設(shè)定.

系統(tǒng)獲得的獎勵為

R(s,a)=I(s,a)-C(s,a),

(6)

其中，I(s,a)表示系統(tǒng)在狀態(tài)s采取動作a時系統(tǒng)獲得的即時收入，C(s,a)表示系統(tǒng)在狀態(tài)s執(zhí)行動作a時計算請求的處理成本.

3.3.1 收入

分別定義不同動作和事件下的收入.

循環(huán)參數(shù)：預(yù)變性94℃維持4 min，之后30個循環(huán)的94℃變性45 s、55℃退火45 s和72℃延伸1 min，再以72℃修復(fù)延伸10 min。

1)a=i,e=R#，即計算請求到達，系統(tǒng)分配i個VM來處理計算請求.此時，直接獎勵可表示為β·[T#-(1/(iμ#))-δ#]-γδ#+ρ#·U(i)，其中，β是單位時間節(jié)省的價格；T#是優(yōu)先級為#的計算請求在本地卸載任務(wù)的計算時間；δ#表示類型為#的計算請求傳輸?shù)組FC系統(tǒng)的傳輸時間；γ是單位時間成本；1/(iμ#)是系統(tǒng)中分配i個VM處理計算請求的計算時間；ρ#表示移動用戶對優(yōu)先級為#的計算請求單位滿意度的價格，此時用戶滿意度為U(i).

2)a=0,e=R#，即計算請求到達系統(tǒng)，系統(tǒng)由于可用VM不足，或者成本代價太高而拒絕卸載計算請求.在這種情況下，MFC系統(tǒng)受到ξ#懲罰.

因此，I(s,a)可由下式表達：

(7)

3.3.2 成本

設(shè)當(dāng)前狀態(tài)為s，給定動作a時產(chǎn)生的期望貼現(xiàn)成本為C(s,a)，與文獻[12]相似，假定持續(xù)時間服從指數(shù)分布.根據(jù)文獻[13-14]，期望貼現(xiàn)成本為

(8)

其中，α是貼現(xiàn)因子，η表示單個VM的單位時間使用價格，不失一般性，令η=1.

3.4 轉(zhuǎn)移概率

本文中計算請求的到達及完成都是泊松過程.對于泊松過程而言，有如下引理[15].

引理1 設(shè){N1(t),t≥0}與{N2(t),t≥0}為相互獨立參數(shù)λ1,λ2的泊松過程，則{N(t)=N1(t)+N2(t),t≥0}是參數(shù)為λ1+λ2的泊松過程，即事件發(fā)生間的時間服從均值為λ1+λ2的指數(shù)分布.

(9)

命題1假設(shè)X1和X2是兩個獨立的指數(shù)隨機變量，其參數(shù)分別為λ1和λ2，有

(10)

證明 由于隨機變量X1和X2是獨立的，因此聯(lián)合概率密度函數(shù)為f(x1,x2)=λ1e-λ1x1·λ2e-λ2x2，則有

由(9)式與命題1，可得到?jīng)Q策后狀態(tài)的變化情況(表2).

表2 決策后狀態(tài)的變化情況

4 模型求解

為了解決上述問題，利用迭代算法來最大化SMDP的長期獎勵.在每次迭代中，根據(jù)Bellman方程迭代計算不同動作下各狀態(tài)的最大值函數(shù).重復(fù)上述步驟，直到各狀態(tài)的最大值函數(shù)收斂為止.為了便于理解，將在下面進一步描述所提出的算法.

4.1 歸一化處理

在離散時間MDP中，可以通過直接迭代Bellman最優(yōu)方程[14](11)式得到最優(yōu)策略.為了將離散時間MDP的算法應(yīng)用于SMDP，通過歸一化方法將SMDP轉(zhuǎn)換為離散時間的MDP.

(11)

將獎勵、轉(zhuǎn)移概率和貼現(xiàn)因子歸一化，歸一化方程如下：

(12)

(13)

(14)

其中，y=λh+λl+K·N·(μh+μl).這里，y是一個歸一化因子，y大于最大的總事件率.

Bellman最優(yōu)方程可以改寫為

(15)

4.2 值迭代算法

迭代算法的偽代碼算法如下：

Step4 對于每一個狀態(tài)s∈S，計算最優(yōu)平穩(wěn)策略并停止，公式如下：

5 數(shù)值結(jié)果與分析

5.1 仿真參數(shù)設(shè)置

仿真參數(shù)設(shè)置如表3所示.

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

5.2 仿真結(jié)果分析

通過數(shù)值模擬實驗所得數(shù)值結(jié)果驗證最優(yōu)方案的性能.圖2所示是系統(tǒng)的動作概率與MFC系統(tǒng)中最大VM數(shù)量K之間的關(guān)系.動作0隨著最大VM數(shù)的增加而減少，這是因為當(dāng)最大VM數(shù)增加時，系統(tǒng)中可用VM數(shù)也會增加，從而降低了動作0的動作概率.當(dāng)系統(tǒng)中最大VM數(shù)較大時，動作1、動作2和動作3逐漸增大，這是因為系統(tǒng)中可用的VM增多，系統(tǒng)決定分配VM來卸載計算請求.隨著MFC資源池中VM數(shù)的增大，動作3的動作概率增加速率相對于其他的動作概率較快，這是因為系統(tǒng)中可用VM數(shù)的增加所致.

圖2 系統(tǒng)動作概率隨K變化的情況(μh=20)

圖3表示系統(tǒng)長期期望獎勵隨K變化的情況，當(dāng)μh=20時，比較該算法與基于GA的方案的長期期望獎勵.可以看出，長期期望獎勵隨著VM數(shù)量的增加而增加.與基于SMDP的最優(yōu)方案相比，基于SMDP的最優(yōu)方案的長期期望獎勵增加了11.7%.這是由于基于GA的方案總是分配盡可能多的VM，而不考慮長期獎勵.

圖3 系統(tǒng)長期期望獎勵隨K變化的情況

在μh=20與μh=10的情況下，MFC系統(tǒng)長期期望獎勵隨K變化的情況如圖4所示.可以看出，μh越大，系統(tǒng)的長期期望獎勵就越大.這是因為與μh=10相比，μh=20時系統(tǒng)分配的VM更快地卸載計算請求，因此空閑VM數(shù)量增加.在這種情況下，與μh=10的情況相比，系統(tǒng)嘗試分配更多VM.因此，μh=20時系統(tǒng)的長期期望獎勵比μh=10時大.

圖4 不同μh下系統(tǒng)長期期望獎勵隨K變化的情況

6 結(jié)語

本文設(shè)計了一個SMDP模型來解決基于網(wǎng)絡(luò)切片的MFC系統(tǒng)中移動用戶的計算請求卸載問題，其中共同考慮了傳輸延遲、計算延遲、可用VM以及網(wǎng)絡(luò)切片的類型特征.然后通過Bellman方程值迭代方法得到了長期獎勵最大化的最優(yōu)方案.數(shù)值結(jié)果表明，本文提出的SMDP方案優(yōu)于我們所考慮的其他方案.

本文的主要貢獻總結(jié)如下：(1)將MFC系統(tǒng)與網(wǎng)絡(luò)切片結(jié)合起來，討論了網(wǎng)絡(luò)切片的優(yōu)先級與計算請求的多樣性特征.(2)在MFC系統(tǒng)中，研究系統(tǒng)計算資源最優(yōu)分配問題.用SMDP模型建立MFC系統(tǒng)計算資源分配模型，以系統(tǒng)長期獎勵最大化為優(yōu)化目標(biāo)，來尋找MFC計算資源分配的最優(yōu)策略.實驗數(shù)據(jù)結(jié)果證明了基于SMDP的最優(yōu)方案的性能.目前，網(wǎng)絡(luò)切片研究工作已取得諸多成果，但是，無論是在霧計算還是網(wǎng)絡(luò)切片方面，接入網(wǎng)絡(luò)切片的實現(xiàn)仍然面臨諸多挑戰(zhàn)，還需要進一步研究.