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

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

0 引 言

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

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

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

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

1 系統(tǒng)模型

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

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

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

圖1 網(wǎng)絡(luò)架構(gòu)Fig.1 Network architecture

1.2 服務(wù)放置模型

(1)

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

1.3 無線通信模型

(2)

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

2 問題公式化

2.1 上行傳輸時延模型

(3)

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

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

(4)

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

(5)

(6)

2.2 計算時延模型

(7)

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

(8)

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

(9)

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

(10)

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

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

(11)

2.3 問題公式化

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

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

3 問題解耦

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

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

P2為凸優(yōu)化問題。

為證明問題P2為凸優(yōu)化問題,首先將驗證目標函數(shù)和約束條件分別為凸?？梢钥闯?約束條件C1～C4為線性約束,因此滿足凸函數(shù)性質(zhì)。

通過相關(guān)的計算,得到:

證畢

邊緣云與云服務(wù)器分別分配給服務(wù)的最優(yōu)計算資源比例為

(12)

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

C1, C2

(13)

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

(14)

(15)

(16)

(17)

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

C3, C4

(18)

證畢

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

4 基于DDL的邊緣服務(wù)放置策略

(19)

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

4.1 基于DDL的邊緣服務(wù)放置模型

4.2 邊緣服務(wù)放置動作生成

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

(20)

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

(21)

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

通過以上對所提模型的輸入與輸出關(guān)系的理論推導(dǎo)知道,當?shù)趥€DNN在任意時刻所觀察的環(huán)境狀態(tài)(),都可根據(jù)式(20)做出響應(yīng)的服務(wù)放置行為()?；诖?問題P1轉(zhuǎn)化為邊云計算資源分配問題P2。前面的工作已經(jīng)研究了已知邊緣服務(wù)放置策略()情況下,最優(yōu)的邊云計算資源分配策略如式(12)所示。最后,服務(wù)放置動作生成的具體流程如圖3所示。

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

(22)

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

4.3 DDL在線學習過程

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

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

(23)

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

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

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

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

5 仿真分析

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

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

表1 仿真參數(shù)

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

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

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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