基于分布式深度學(xué)習(xí)的邊緣服務(wù)放置策略

鄒 虹, 白陳陽(yáng), 何 鵬,*, 崔亞平, 王汝言, 吳大鵬

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

0 引 言

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

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

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

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

1 系統(tǒng)模型

MEC網(wǎng)絡(luò)能夠?yàn)殡娏亢陀?jì)算資源不足的用戶設(shè)備提供分布式計(jì)算資源和低時(shí)延服務(wù),合理的邊緣服務(wù)放置策略可以提高M(jìn)EC網(wǎng)絡(luò)中的用戶服務(wù)質(zhì)量。由于資源受限,導(dǎo)致延遲敏感型任務(wù)和重流量負(fù)載型應(yīng)用的服務(wù)質(zhì)量降低。因此,本文在距離用戶較近的網(wǎng)絡(luò)邊緣部署MEC服務(wù)器,利用MEC的計(jì)算能力處理靠近網(wǎng)絡(luò)邊緣的用戶服務(wù)請(qǐng)求。本節(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)存在多個(gè)小基站(small base station, SBS),SBS均帶有邊緣云增強(qiáng),令集合={1,2,…,,…,}表示全部邊緣云集合。

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

1.2 服務(wù)放置模型

(1)

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

1.3 無線通信模型

(2)

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

2 問題公式化

2.1 上行傳輸時(shí)延模型

(3)

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

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

(4)

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

(5)

(6)

2.2 計(jì)算時(shí)延模型

(7)

因此,邊緣云所服務(wù)的第個(gè)用戶的計(jì)算時(shí)延為

(8)

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

(9)

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

(10)

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

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

(11)

2.3 問題公式化

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

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

3 問題解耦

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

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

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

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

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

證畢

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

(12)

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

C1, C2

(13)

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

(14)

(15)

(16)

(17)

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

C3, C4

(18)

證畢

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

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

(19)

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

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

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

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

(20)

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

(21)

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

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

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

(22)

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

4.3 DDL在線學(xué)習(xí)過程

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

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

(23)

圖4 DDL-ESP在線學(xué)習(xí)過程Fig.4 Online learning process of DDL-ESP

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

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

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

5 仿真分析

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

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

表1 仿真參數(shù)

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

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

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

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

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

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

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

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

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

圖9 平均運(yùn)行時(shí)間Fig.9 Average running time

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

6 結(jié) 論

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