基于分布式深度學習的邊緣服務放置策略

鄒 虹, 白陳陽, 何 鵬,*, 崔亞平, 王汝言, 吳大鵬

(1. 重慶郵電大學通信與信息工程學院, 重慶 400065; 2. 重慶高校市級光通信與網絡重點實驗室,重慶 400065; 3. 泛在感知與互聯重慶市重點實驗室, 重慶 400065)

0 引 言

隨著5G網絡的快速部署,增強現實(augment reality, AR)、虛擬現實(virtual reality, VR)等新型應用場景不斷涌現,這些應用往往具有低時延和大帶寬的需求,給計算、存儲能力不足且電量受限的移動設備帶來了極大的挑戰。根據思科的預測,2023年5G用戶將達到14億,平均5G連接速度將達到575 Mb/s。2013年歐洲電信標準組織(European Telecommunications Standards Institute, ETSI)提出移動邊緣計算(mobile edge computing, MEC),通過在無線接入網側部署基站和邊緣服務器,從而為這些應用需求提供支持。如何為移動設備提供低時延的持續服務是制約移動邊緣計算網絡持續發展的瓶頸之一。

在移動邊緣計算網絡中,由于邊緣服務器的通信、計算、緩存等資源受限,且用戶需求多樣性、區域熱點差異性等問題的存在,導致邊緣計算服務器負載不均衡,從而使接入到高負載邊緣服務器的用戶服務質量大大下降,邊緣服務放置技術則是解決這一問題的關鍵技術之一。合理的邊緣服務放置能夠保證用戶的服務質量要求,并且平衡部分高負載服務器的工作負擔。如何根據用戶服務質量要求以及資源限制等信息進行合理的邊緣服務放置成為移動邊緣計算網絡服務放置中亟待解決的關鍵問題之一。由于應用服務提供商(application service provider, ASP)的成本限制及服務能力有限,只能在邊緣服務器中部署部分熱點服務,因此在實際進行邊緣服務放置時,需要考慮用戶當前接入的邊緣云是否具有其請求的服務。將服務放置到某一個邊緣云后,需要進一步為放置的服務分配計算、存儲等資源,從而支持服務的正常運行并保證持續高質量的用戶服務。

關于移動邊緣計算的服務放置問題,國內外研究人員已開展研究。文獻[6]根據ETSI模型設計了一種新的MEC服務放置方案,建立了整數線性規劃問題,提出了一種禁忌搜索算法,在滿足計算資源、延遲要求和服務可用性的約束條件下有效平衡了計算負載,但禁忌搜索算法的缺點可能使其陷入局部最優。文獻[7]提出了一種動態服務放置策略,該策略在考慮平均服務放置延遲和成本的情況下最大化ASP的利益。所提算法根據延遲和成本等參數的閾值進行迭代,并重新進行服務放置,在一定程度上減少了延遲,但時間復雜度過高。文獻[8]考慮了長期成本約束下的多用戶服務放置場景,建立了長期成本約束條件下平均時延最小化問題,并提出了集中式的Markov近似策略和分布式的最佳響應更新策略,解決了單節點覆蓋的用戶服務請求決策問題,實現了次優解。文獻[9]考慮了ASP預算約束下的服務放置,以時隙為單位,在所有邊緣服務器中租用部分資源進行服務放置,利用組合上下文多臂賭博方法進行邊緣服務放置決策,有效降低了服務時延。文獻[8-9]僅考慮了資源限制,但是未考慮資源分配問題。當服務被放置到某一邊緣云后,需要進一步為服務分配合理的資源從而支持服務的正常運行。文獻[10]考慮了邊緣節點可用計算資源有限情況下車載無線通信技術(vehicle to everything, V2X)的服務放置,為了解決核心網與邊緣計算混合環境中的最佳V2X服務放置問題,提出了一種低復雜度的貪婪算法解決方案,達到了接近最優的性能。文獻[6-10]主要考慮了單一類型的服務放置,以及針對多邊緣節點的服務遷移,但均未考慮服務異構性問題,在實際服務放置過程中,服務類型往往是多樣化的,對單一類型的服務進行優化無法滿足實際場景的需求。文獻[11]考慮了邊緣計算系統節點特征和用戶位置的異構性問題,在每個邊緣節點中放置多種類的服務,以最大化服務放置獎勵為優化目標,提出了一種近似算法,但未考慮服務放置成本以及資源分配問題。

針對以上現存問題,本文從用戶的服務質量要求等實際情況出發,提出了一種基于分布式深度學習的邊緣服務放置策略。考慮到用戶服務請求類別的多樣性及ASP的服務放置成本,對邊緣服務放置策略與移動邊緣計算網絡的計算-存儲資源進行了聯合優化。為克服用戶服務請求發送至ASP遠端云服務器的響應時間過長,嚴重降低用戶服務體驗等問題,通過在靠近用戶側的邊緣云部署一定數量的熱點應用服務,從而快速響應用戶的服務需求,提高用戶的服務質量。其次,考慮到移動邊緣計算網絡的計算-存儲資源有限,為降低用戶服務請求的響應時間及ASP的服務部署成本,設計了最小化所有用戶服務請求的時延與加權服務放置成本總和的優化目標,將優化問題建模為混合整數非線性規劃問題。為求解所設計的優化目標問題,首先使用凸優化理論求解出了給定服務放置策略情況下邊云最優的計算資源分配方案。由于傳統數值優化方法在求解最優服務放置策略時存在算法時間復雜度過高等問題,本文設計了基于分布式深度學習的邊緣服務放置算法。該算法不僅降低了用戶服務請求時延及ASP的服務放置成本,而且能隨著時間的推移逐漸逼近全局最優的服務放置策略。

1 系統模型

MEC網絡能夠為電量和計算資源不足的用戶設備提供分布式計算資源和低時延服務,合理的邊緣服務放置策略可以提高MEC網絡中的用戶服務質量。由于資源受限,導致延遲敏感型任務和重流量負載型應用的服務質量降低。因此,本文在距離用戶較近的網絡邊緣部署MEC服務器,利用MEC的計算能力處理靠近網絡邊緣的用戶服務請求。本節首先介紹了MEC網絡的異構服務網絡架構,然后根據用戶接入網絡情況建模服務放置模型和通信模型。

1.1 網絡模型

系統的網絡架構如圖1所示,在宏基站(macro base station, MBS)覆蓋范圍內存在多個小基站(small base station, SBS),SBS均帶有邊緣云增強,令集合={1,2,…,,…,}表示全部邊緣云集合。

圖1 網絡架構Fig.1 Network architecture

1.2 服務放置模型

(1)

式中:表示服務所需要的存儲資源;表示邊緣云全部的存儲資源。

1.3 無線通信模型

(2)

式中:是信道帶寬;是加性高斯白噪聲雙邊功率譜密度;是信道中的隨機噪聲。

2 問題公式化

2.1 上行傳輸時延模型

(3)

此外,本文考慮到邊緣服務器的計算-存儲資源有限,因此ASP在每個邊緣云上只能部署有限的服務。當用戶所在的邊緣云沒有該用戶所需要的服務時,該用戶只能通過所在的SBS上傳自身的服務請求至擁有所有服務的云服務器。因此,用戶的上行傳輸時延主要有兩種情況:

(1) 邊緣云具有第個用戶所請求的第種服務。在該種情況中,邊緣云所服務的第個用戶的上行傳輸時延為

(4)

(2) 當邊緣云不具有第個用戶所請求的第種服務時,邊緣云所服務的第個用戶的服務請求只能通過邊緣云上傳到MBS,再通過核心網轉發至云中心。因此,邊緣云所服務的第個用戶上行傳輸時延為

(5)

(6)

2.2 計算時延模型

(7)

因此,邊緣云所服務的第個用戶的計算時延為

(8)

值得注意的是,當用戶的服務請求不能被本地邊緣云所響應時,該用戶的服務請求只能通過本地的SBS上傳至ASP的云服務器。令表示云服務器的計算能力,可得邊緣云所服務的第個用戶的服務請求被云服務器所計算的時延為

(9)

式中:()∈[0,1]表示時刻云服務器分配給第種服務的計算資源比例。云服務器分配給全部服務的計算資源比例需滿足:

(10)

針對于云服務器存儲服務的條件,本文假設ASP的云服務器具有全部類型的服務。

綜上所述,邊緣云所服務的第個用戶的最終計算時延為

(11)

2.3 問題公式化

首先,為緩解大量服務請求上傳到遠端云服務器對核心網造成的流量擁塞以及解決如何進一步提高用戶的服務體驗等問題,部署在邊緣服務器上的服務應最大化滿足用戶的需求。但如果每個邊緣服務器都部署所有的服務將導致部署成本過高等問題。針對于該問題,本文制定了如下的優化目標:

s.t. 式(1),式(3),式(7),式(10)

3 問題解耦

本文求解問題P1的總體思路如下。首先令時刻ASP已經作出最優的服務放置策略()。在該條件下,問題1將轉化為不含整型變量的邊云計算資源分配問題P2,其表述如下:

式中:C1表示邊緣云分配給所托管的服務的計算資源不能大于其最大計算資源;C2表示邊緣云分配給第種應用服務的計算資源比例;C3表示云服務器分配給所托管的服務的計算資源不能大于其最大計算資源;C4表示邊緣云分配給第種服務的計算資源比例。

P2為凸優化問題。

為證明問題P2為凸優化問題,首先將驗證目標函數和約束條件分別為凸。可以看出,約束條件C1～C4為線性約束,因此滿足凸函數性質。

通過相關的計算,得到:

證畢

邊緣云與云服務器分別分配給服務的最優計算資源比例為

(12)

觀察問題P2可以看出,優化目標的第一項只與約束條件C1與C2相關,第二項與約束條件C3與C4相關。因此,問題P2可以分解為兩個子問題,分別為邊緣云的計算資源分配問題P2_1與云服務器的計算資源分配問題P2_2。下面將求解子問題P2_1,并在其基礎上求解問題P2_2。問題P2_1表述如下:

C1, C2

(13)

運用拉格朗日乘子法消去約束式,得優化算子為

(14)

(15)

(16)

(17)

接下來將求解問題P2_2。問題P2_2表述如下:

C3, C4

(18)

證畢

通過以上的理論推導,證明了在任意時刻,已知ASP的最優服務放置策略()條件下的最優邊云計算資源分配策略。下面將求解在任意時刻,ASP最優的服務放置策略()。首先通過觀察可知,問題P1是一個混合整數非線性規劃問題(mixed integer nonlinear program, MINLP)。如果通過窮舉法尋找最佳的服務放置策略(),所需要的計算時間隨著用戶、邊緣云和服務請求種類的數量成指數級增長,顯然不利于實際的移動邊緣計算網絡。因此本文的目標是設計一種時間復雜度較低且能通過學習隨著時間的推移逐漸逼近最優解的解決方案。基于此,本文提出了一種基于分布式深度學習(distributed deep learning, DDL)的邊緣服務放置策略。

4 基于DDL的邊緣服務放置策略

(19)

由于所求解的二進制服務放置集合()可能存在的組合數為2種,隨著邊緣云和服務種類數量的增加,該組合數大小將呈指數增長,導致在任意時刻尋找最優的服務放置行為()是一個NP難問題。基于此,本文使用基于深度神經網絡(deep neural network, DNN)的參數化函數近似表示服務放置策略。不同于經典的深度學習方法,本文使用了基于DDL的邊緣服務放置(DDL based edge service placement, DDL-ESP)策略,通過個并行的DNN獲得種候選的二進制的服務放置行為。該方法不僅具有更快的收斂速度,且能獲得更高的服務放置準確度。

4.1 基于DDL的邊緣服務放置模型

4.2 邊緣服務放置動作生成

如圖2所示,對于時刻的輸入(),使用個DNN生成個候選的邊緣服務放置行為,其中每個DNN將對應生成一個邊緣服務放置行為。令第個DNN輸入與輸出的關系函數為(,()),可得第個DNN輸出的服務放置行為:

(20)

式中：表示第個DNN內部各層神經元之間的連接權重與偏置集合。具體解釋為由于DNN的各層之間的神經元通過簡單的線性函數進行前向傳遞,其表達式如下:

(21)

圖2 DDL-ESP模型Fig.2 DDL-ESP model

通過以上對所提模型的輸入與輸出關系的理論推導知道,當第個DNN在任意時刻所觀察的環境狀態(),都可根據式(20)做出響應的服務放置行為()。基于此,問題P1轉化為邊云計算資源分配問題P2。前面的工作已經研究了已知邊緣服務放置策略()情況下,最優的邊云計算資源分配策略如式(12)所示。最后,服務放置動作生成的具體流程如圖3所示。

圖3 服務放置動作生成過程Fig.3 Process of service placement action generation

(22)

根據式(22)獲得的最優服務放置行為()將作為所提服務放置策略的最終輸出。

4.3 DDL在線學習過程

為了讓DDL方法能夠隨著時間的推移漸進地學習接近全局最優解的邊緣服務放置策略,本文使用了深度強化學習的經驗回放機制。DDL方法完成在線學習過程如下所述:首先,在當前任意時刻,根據式(22)獲取最佳邊緣服務放置決策(),然后將環境狀態()拼接為帶有標簽的數據((),())并存入有限容量的記憶回放內存。當記憶回放內存被標簽數據占滿,其中最為陳舊的數據條目將被記憶回放內存所丟棄。為了使個DNN能在線學習最優的邊緣服務放置策略,每隔時間,從記憶回放內存為每一個DNN隨機選取大小為的標簽數據,用于訓練DNN,從而實現在線學習最優的服務放置策略過程,其流程如圖4所示。其中，每個DNN采用梯度下降算法最小化當前標簽與最優標簽的損失函數來優化每個DNN的參數值,其損失函數表述為

(,(),())=-()log(,())- (1-())log(1-(,()))

(23)

圖4 DDL-ESP在線學習過程Fig.4 Online learning process of DDL-ESP

通過對基于DDL的邊緣服務放置策略詳細的介紹與說明,推導出了任意時刻,最優的服務放置行為()產生過程及如何在線學習漸近最優的邊緣服務放置策略,最終的實現流程如算法1所示。

算法1 DDL-ESP算法輸入 時刻t,用戶的服務請求集合X(t)輸出 時刻t,邊緣云最優的服務放置行為Y*(t)1. 隨機初始化每個DNN的內部參數ξm;2. for t=0,1,…,+∞ do3. 以X(t)作為每個DNN的輸入,得到邊緣服務放置行為集合(t);4. 使用式(22)挑選出最優的服務放置Y*(t);5. 以Y*(t)作為該環境狀態X(t)的標簽;6. 檢查記憶回放內存是否占滿,如果占滿刪除時間最為陳舊的標簽數據,并存入該時刻最新的數據(X(t),Y*(t));7. ift>0 and t%τ==0 do8. 隨機從記憶回放內存中為每一個DNN選取大小為A的數據集,使用式(23)作為損失函數,然后使用隨機梯度下降算法訓練每一個DNN更新內部參數ξm,從而實現在線地學習最優服務放置策略π*;9. end if10. end for

首先隨機初始化個DNN的內部參數值并保證每個DNN內部參數不能完成相同。此外,還需初始化記憶回放內存為空。通過大量的仿真分析可知,當>1時,DDL-ESP算法能快速收斂到最佳的服務放置策略。

5 仿真分析

本文采用Python IDE Pycharm作為實驗的仿真軟件。當前Pycharm有兩個版本,分別為專業版與社區版。專業版功能強大,主要是為Python和Web開發者而準備的。由于社區版具備完成仿真實驗所需的全部模塊(如numpy、scipy、tensorflow、keras等),所以使用版本為Pycharm Community Edition 2019.2.5的IDE進行仿真實驗。與此同時,為縮短仿真時間,使用戴爾易安信PowerEdge R730機架式服務器(Xeon E5-2603 V3/8GB/1.2TB)搭建仿真平臺。

在邊緣計算網絡中,本文假設MBS覆蓋范圍內存在的SBS數量=3且每個SBS覆蓋的用戶數=3(∈)。每個SBS分配給每個用戶的上行傳輸帶寬=10 MHz。此外,假設系統中服務請求的種類數量=4。其他仿真參數設置如表1所示。

表1 仿真參數

圖5仿真了在不同DNN數量情況下,DDL-ESP算法所產生的所有用戶加權時延總和與窮舉法所計算的全局最優的加權時延總和比值(在圖中用時延增益表示)隨時間推移的變化曲線。可以看出，隨著時間的不斷推移,當≥8時,所提出的DDL-ESP算法最終能以大約98%的時延增益逐漸逼近窮舉法所產生的全局最優解。即,所提算法最終所計算出的所有用戶加權時延總和與全局最優解之間的誤差大約為2%。此外還可以看出,隨著DNN數量的不斷增大,所提算法的收斂性也不斷變快。其產生的主要原因在于,隨著值的增大,DDL-ESP算法在任意時刻的服務放置行為生成過程中將會產生更多的服務放置行為。即,在這些服務放置行為中,將可能出現更好的服務放置行為,使得問題P1的值更小,從而使得DDL-ESP算法在線學習過程中更容易接近全局最優的服務放置策略。但值得注意的是,增大值也意味著算法在學習過程中將需要訓練更多的DNN,導致訓練時間過程變長等問題。因此，在實際運用中,值的設置需要結合設備的計算能力及外部環境變化的快慢,才能使訓練時間與算法收斂性達到最佳的平衡狀態。

圖5 DNN數量與DDL-ESP算法收斂性Fig.5 Number of DNNs and the convergence of DDL-ESP algorithm

圖6仿真了在不同學習率lr情況下,DDL-ESP算法的時延增益,其中設置DNN的數量=8。同理可知,隨著時間的不斷推移,當lr=0.01時,所提出的DDL-ESP算法最終同樣能以大約為98%的時延增益逐漸逼近窮舉法所產生的全局最優解。當學習率lr分別為0.000 1,0.001與0.01時,可以看出,適當地增大學習率lr能加快DDL-ESP算法的收斂速度。對比于學習率lr分別為0.000 1與0.001,當lr=0.01時,所提算法分別能提高平均時延增益0.058%與0.015%。當lr=0.1時,數據表明過大的學習率lr值不但不能使算法收斂,并且對比于lr=0.01所得到的時延增益反而降低大約0.136%。其產生的主要原因在于,在DNN訓練過程中過大的lr值容易導致所使用的梯度下降算法在接近最優解附近來回震蕩,導致算法無法準確地收斂到最優解,從而導致時延增益曲線出現不收斂現象且時延增益相對較低。但值得注意的是,如果學習率lr值過小,意味著算法在學習過程中將需要更多的訓練時間找到最優解。同理,在實際運用中,學習率lr值的設置需要結合數據集的特征及大量的實驗才能使訓練時間與算法收斂性達到最佳狀態。

圖6 學習率lr與DDL-ESP算法收斂性Fig.6 Learning rate lr and the convergence of DDL-ESP algorithm

為了驗證所提算法的可行性,本文考慮了3種基準對比算法,分別為云服務方案、邊緣云服務方案與窮舉法。其中,在云服務方案中,所有用戶的服務請求通過本地SBS上傳至ASP的云服務器,因此邊緣云不為任何用戶提供服務。相反,在邊緣云方案中,ASP在每一個邊緣云放置用戶需要的所有服務,云服務器將不會為任何用戶提供服務。對比于DDL-ESP算法而言,窮舉法將列舉出所有可能的服務放置行為,然后挑選出使得優化目標最小化的服務放置行為作為當前時刻最優的邊緣服務放置行為()。顯然,在任意時刻,窮舉法都能獲取全局最優解,但該算法的時間復雜度將隨著邊緣云及服務種類的數量增加成指數式增長,不利于在環境實時變化的動態網絡中應用。

圖7仿真了在不同折扣因子值情況下,4種方案所得到的平均用戶加權時延。可以看出,隨著折扣因子的不斷增大,DDL-ESP算法所產生的平均用戶加權時延比窮舉法所產生的全局最優解約高23.3 ms。在不同值情形下,通過對DDL-ESP算法與其他兩種方案加權時延的數值差進行相加并求平均值,然后除以所有用戶,得出DDL-ESP算法能夠分別將平均用戶加權時延降低為0.31 s與0.48 s。此外還可以看出,當≤001時,4種方案所產生的平均用戶加權隨著折扣因子的增大出現緩慢增長。其原因在于,當相對較小時,意味著ASP將在邊緣云部署更多的服務,從而保障用戶服務質量,也即犧牲更多的服務放置成本換取更好的服務質量。但≥001時,ASP為節約服務放置的部署成本,選擇犧牲用戶服務質量,從而導致用戶的加權時延急速增大。因此,在實際運用中,ASP如果想節約服務放置的部署成本或者為用戶提供更好的服務質量,都可以通過調控折扣因子值來完成。如果ASP既要保持用戶服務質量不低于某一閾值的情況下降低其邊緣服務部署成本,顯然需要結合用戶的服務請求密度及采集大量的用戶數據等才能達到部署成本與服務質量相對折中的狀態。

圖7 折扣因子β與用戶的加權時延Fig.7 Discount factor β and users’weighted delay

圖8 邊云計算資源與用戶加權時延Fig.8 Resource of edge-cloud computing and users’weighted delay

結合圖8(a)與圖8(b)可知,雖然所提算法得到的平均用戶加權時延高于窮舉法,但是算法時間復雜度卻遠低于窮舉法,使得所提算法的運行時間遠低于窮舉法。該結論將在圖9進行驗證分析。對比于其他兩種算法,雖然所提算法的復雜度相對較高,但可以大幅度降低平均用戶的加權時延,提高用戶的服務質量。顯然,所提算法不僅克服了云服務與邊緣云方案容易導致用戶的服務體驗降低問題,而且解決了窮舉法時間復雜度過高問題。

圖9 平均運行時間Fig.9 Average running time

為進一步驗證所提出的算法在放置行為生成過程中需要的運行時間與窮舉法的運行時間的差異,仿真了不同SBS數量下兩種算法的運行時間,如圖9所示。本文設置每個SBS服務的用戶數相等。從圖9可以看出,隨著SBS數量的不斷增加,兩種算法所需的平均運行時間也隨之變大。需要注意的是,窮舉法所需要的運行時間隨著SBS數量的不斷增加,呈現指數式增長。顯然在實際的多用戶多基站的邊緣計算網絡中,該方法不利于處理最優的服務放置行為生成過程。對比于窮舉法,所提算法增加了3.47%的用戶加權時延,但所提的DDL-ESP算法在運行時間上遠低于窮舉法,且每個用戶的平均運行時間縮短了0.29 s。

6 結 論

為了滿足MEC網絡中多用戶服務放置的需要,同時降低ASP的服務放置成本,提出了一種基于DDL的邊緣服務放置策略。該策略考慮了用戶服務請求時延以及服務放置成本兩個因素,首先解決了計算資源分配問題,然后通過DDL解決了邊緣服務放置問題。仿真結果表明,對比于云服務方案與邊緣云方案,所提算法可以有效地降低平均用戶加權時延,提高用戶的服務質量。與窮舉法相比,所提算法增加了少量加權時延,但大幅度縮短了算法的平均運行時間。在未來的工作中,將研究帶有用戶需求預測的移動邊緣計算服務放置及小基站重疊覆蓋對服務放置策略的影響等問題。