基于網絡切片的移動霧計算系統資源調度策略

張小佳，文 鵬，唐勝達

(1.廣西師范大學數學與統計學院，廣西 桂林 541006；2.桂林學院理工學院，廣西 桂林 541006)

0 引言

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

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

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

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

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

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

1 相關工作

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

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

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

2 系統模型與資源分配問題

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

表1 系統框架中的符號及說明

2.1 MFC系統VM資源分配模型

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

圖1 MFC系統VM資源分配模型

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

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

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

2.2 VM資源分配問題

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

因此，本文考慮的系統獎勵是凈獎勵R，可表示為R=I-C.考慮到移動用戶的計算請求的動態特性，當前狀態下的動作可能會直接導致下一個狀態相當大的變化，從而對系統的期望總獎勵產生嚴重影響.換句話說，從長遠來看，最大化當前狀態獎勵的動作可能會變得不明智，尤其是系統資源相對稀缺的情況.因此，本文的目標是通過適當地分配MFC系統中的VM資源，使長期期望的總獎勵V最大化.

3 SMDP框架

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

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

3.1 狀態集

設MFC系統中的狀態集合為

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

(1)

(2)

(3)

3.2 動作集

(4)

3.3 獎勵函數

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

(5)

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

系統獲得的獎勵為

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

(6)

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

3.3.1 收入

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

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

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

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

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

(7)

3.3.2 成本

設當前狀態為s，給定動作a時產生的期望貼現成本為C(s,a)，與文獻[12]相似，假定持續時間服從指數分布.根據文獻[13-14]，期望貼現成本為

(8)

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

3.4 轉移概率

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

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

(9)

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

(10)

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

由(9)式與命題1，可得到決策后狀態的變化情況(表2).

表2 決策后狀態的變化情況

4 模型求解

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

4.1 歸一化處理

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

(11)

將獎勵、轉移概率和貼現因子歸一化，歸一化方程如下：

(12)

(13)

(14)

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

Bellman最優方程可以改寫為

(15)

4.2 值迭代算法

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

Step4 對于每一個狀態s∈S，計算最優平穩策略并停止，公式如下：

5 數值結果與分析

5.1 仿真參數設置

仿真參數設置如表3所示.

表3 仿真參數設置

5.2 仿真結果分析

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

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

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

圖3 系統長期期望獎勵隨K變化的情況

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

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

6 結語

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

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