基于邊緣計(jì)算的計(jì)算資源分配和偏分任務(wù)卸載算法

王喜鴻，王良成，張小波

（1三亞理工職業(yè)學(xué)院 海南 三亞 572000）

（2三亞學(xué)院 海南 三亞 572000）

0 引言

隨著移動(dòng)設(shè)備和應(yīng)用的飛速增加，對(duì)無線網(wǎng)絡(luò)的吞吐量、低延時(shí)提出了更高的需求[1]。為了解決用戶超低延時(shí)和用戶設(shè)備更低能耗的需求，歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)（European Telecommunications Standard Institute，ETSI）提出了移動(dòng)邊緣計(jì)算（mobile edge computing，MEC），其是在無線網(wǎng)絡(luò)內(nèi)為附近用戶提供基礎(chǔ)IT和云服務(wù)。另外，還出現(xiàn)了許多中邊緣計(jì)算方式，如微云（cloudlets）、移動(dòng)云計(jì)算（mobile cloud computing，MCC）、霧計(jì)算（fog computing）等。雖然概念十分相似，但是在技術(shù)上存在著非常大的差別。

1 MEC的概念

MEC是一種能夠解決資源受限移動(dòng)設(shè)備和資源密集型應(yīng)用的技術(shù)，其具有MEC的數(shù)據(jù)中心，且在無線接入點(diǎn)或蜂窩基站部署了云資源，從而使終端設(shè)備用戶和公有云數(shù)據(jù)中心的延遲得到了有效降低。MEC與MCC對(duì)比情況見表1。

表1 MEC與MCC對(duì)比情況

2 MEC的相關(guān)研究

當(dāng)前關(guān)于MEC的相關(guān)研究包括資源分配、任務(wù)卸載兩個(gè)方面，因此主要研究目標(biāo)主要集中以下幾方面。

2.1 降低任務(wù)處理時(shí)間

為了避免相同資源分配方案與用戶狀態(tài)的重復(fù)學(xué)習(xí)，采用多疊強(qiáng)化學(xué)習(xí)（reinforcement learning，RL）算法，同時(shí)對(duì)于頻譜分配、傳輸功率分配進(jìn)行優(yōu)化，以此來實(shí)現(xiàn)用戶之間的傳輸延遲最小化。也有非合作博弈方法，通過分布式迭代算法解決MEC任務(wù)，最小化任務(wù)執(zhí)行延遲。

2.2 降低設(shè)備處理任務(wù)的能耗

胡錦天等[2]研究了MEC系統(tǒng)中時(shí)延敏感應(yīng)用的節(jié)能任務(wù)接納，并且提出了約束條件下總能耗最小化邊緣服務(wù)器的計(jì)算資源和延遲。在時(shí)間截止、傳輸錯(cuò)誤率等約束條件下，還提出了一種最小化移動(dòng)設(shè)備能耗的卸載決策方法，并且該方法在可接受試驗(yàn)和通信質(zhì)量下具有良好的效果。

2.3 在設(shè)備能耗間和任務(wù)處理時(shí)間的平衡

MEC應(yīng)用程序的任務(wù)卸載功能能夠提高移動(dòng)設(shè)備的處理能力，并降低能耗，但其前提條件需集中在一個(gè)系統(tǒng)中。無線信道帶寬有限，而設(shè)備需要網(wǎng)絡(luò)資源，彼此之間會(huì)互相競(jìng)爭(zhēng)，導(dǎo)致感染現(xiàn)象，降低數(shù)據(jù)傳輸速率，從而進(jìn)一步延長(zhǎng)數(shù)據(jù)傳輸時(shí)間[3]。另外，在邊緣云數(shù)據(jù)中心計(jì)算資源有限時(shí)，最佳選擇并不是邊緣云端將所有應(yīng)用程序卸載。而是，當(dāng)前的移動(dòng)終端設(shè)備性能在逐漸提升，在終端中處理部分移動(dòng)應(yīng)用程序，在邊緣云數(shù)據(jù)中心處理另一部分，可以降低移動(dòng)設(shè)備間數(shù)據(jù)傳輸時(shí)間延長(zhǎng)的問題，并且對(duì)于數(shù)據(jù)中心計(jì)算資源的需求也可以顯著下降。

綜上所述，當(dāng)前主要考慮的是任務(wù)卸載問題，如任務(wù)在本地設(shè)備處理、在邊緣云處理[4]。因此，針對(duì)MEC的邊緣云計(jì)算資源分配與偏分任務(wù)卸載問題開展研究。

3 設(shè)置MEC模型

典型的MEC系統(tǒng)，如下圖1所示。多個(gè)服務(wù)器構(gòu)成的數(shù)據(jù)中心和N個(gè)物聯(lián)網(wǎng)設(shè)備構(gòu)成了MEC系統(tǒng)模型。MEC系統(tǒng)模型，設(shè)物聯(lián)網(wǎng)設(shè)備i∈[1，2，…，N]的任務(wù)為i。物聯(lián)網(wǎng)設(shè)備中含有一個(gè)延遲敏感（delay-sensitive）、任務(wù)需要處理，而任務(wù)中需要大量的計(jì)算資源。通過本地設(shè)備、邊緣云數(shù)據(jù)中心對(duì)于任務(wù)進(jìn)行處理。通過基站(base station，BS）實(shí)現(xiàn)物聯(lián)網(wǎng)設(shè)備對(duì)數(shù)據(jù)中心計(jì)算資源的訪問[5]。其中，Di為任務(wù)i的大?。籉為邊緣云數(shù)據(jù)中心服務(wù)器的CPU頻率；λ∈（0，1）為任務(wù)i本地處理的比例；fi，t為物聯(lián)網(wǎng)設(shè)備任務(wù)i的CPU頻率大??；Ci為完成任務(wù)i所需的CPU周期數(shù)。

圖1 典型的MEC系統(tǒng)

3.1 本地計(jì)算模型

通過物聯(lián)網(wǎng)終端設(shè)備處理移動(dòng)應(yīng)用程序。fi，t為設(shè)備的計(jì)算能力，使用每秒CPU周期來衡量。因此，物聯(lián)網(wǎng)設(shè)備處理任務(wù)所需時(shí)間（Ti，t）和消耗的能耗（Ei，t）可表示為：

3.2 通信模型

利用無線信道，將應(yīng)用程序卸載到邊緣云，可以獲得更多的上行鏈路傳輸能量和傳輸時(shí)間。上行傳輸?shù)臄?shù)據(jù)率（ri）可以表示為：

式中：Bi為分配給物聯(lián)網(wǎng)設(shè)備i的帶寬；q1為傳輸功率；h1為路徑損耗；N0為噪聲功率。

3.3 邊緣云計(jì)算模型

數(shù)據(jù)中心收到任務(wù)后重新分配計(jì)算資源，對(duì)于任務(wù)進(jìn)行處理。假設(shè)其計(jì)算資源分配采用fi，e表示，那么其在邊緣云中的處理時(shí)間可表示為：

4 解決算法

4.1 問題構(gòu)造

為了實(shí)現(xiàn)最小化系統(tǒng)計(jì)算開銷，構(gòu)造的優(yōu)化問題可表示為：

4.2 問題解決算法

通過定理1提出解決算法。

定理1 總是有supf（x，y）= supf∽（x，y）成立。其中，supf∽（x，y）= supf（x，y）。

上式表明，當(dāng)最小化1個(gè)函數(shù)時(shí)，可以對(duì)部分變量?jī)?yōu)先進(jìn)行優(yōu)化，然后再對(duì)剩余變量進(jìn)行優(yōu)化。因此，可以將問題變成2個(gè)子問題：子題1邊緣云計(jì)算開銷的最小化；子題2本地計(jì)算開銷的最小化。其中，子題1可表達(dá)為：

其中，因?yàn)槟繕?biāo)函數(shù)為凸函數(shù)，所以構(gòu)造拉格朗日函數(shù)，并且基于凸優(yōu)化中的KKT條件，得到以下結(jié)果：

通過式（7）、（8），可以了解到μ＞0，從而獲得：

5 基于MEC的負(fù)載均衡方案

基于大量密集型部署MEC服務(wù)器導(dǎo)致的高能量消耗，推出一種MEC服務(wù)器休眠的負(fù)載均衡方案。根據(jù)M/M/m多服務(wù)臺(tái)排隊(duì)理論，對(duì)于MEC服務(wù)器的卸載任務(wù)量進(jìn)行建模，通過集合均值迭代比較算法，將卸載任務(wù)量劃分成2個(gè)不同卸載任務(wù)量集的MEC服務(wù)器集合，選擇卸載任務(wù)量較低的MEC服務(wù)器，通過休眠操作，降低系統(tǒng)能耗，保證網(wǎng)絡(luò)負(fù)載均衡。

5.1 系統(tǒng)模型

將1個(gè)宏基站和M各小區(qū)基站構(gòu)成密集異構(gòu)網(wǎng)絡(luò)，在小區(qū)基站側(cè)部MEC服務(wù)器，網(wǎng)絡(luò)用戶在MEC中卸載計(jì)算任務(wù)。設(shè)定每個(gè)MEC服務(wù)器的覆蓋范圍，假設(shè)用戶隨機(jī)接入，整個(gè)網(wǎng)絡(luò)的用戶卸載任務(wù)量會(huì)隨時(shí)間變化而變化[6]。

5.2 方案設(shè)計(jì)

假設(shè)網(wǎng)絡(luò)中一共有N個(gè)活躍狀態(tài)的MEC服務(wù)器，其休眠操作是以T為周期進(jìn)行循環(huán)。在單個(gè)周期內(nèi)操作步驟如下：

步驟1 宏基站獲取小區(qū)中MEC服務(wù)器卸載情況，根據(jù)預(yù)設(shè)卸載任務(wù)量閾值，得到MEC服務(wù)器休眠操作待選子集。在集合為0的情況下，表示當(dāng)前周期T內(nèi)MEC服務(wù)器不需要進(jìn)行休眠操作。

步驟2 對(duì)于MEC服務(wù)器休眠操作待選子集，隨對(duì)應(yīng)的卸載任務(wù)量集合排序后，進(jìn)行MEC服務(wù)器休眠操作。

步驟3 執(zhí)行集合均值迭代比較算法，在第i次進(jìn)行計(jì)算平均卸載任務(wù)量的過程中，系統(tǒng)對(duì)集合中最后1個(gè)MEC服務(wù)器中的卸載任務(wù)量MEC服務(wù)器集合的算數(shù)平均值，如果該值大于或等于卸載任務(wù)量，則可以認(rèn)為從MEC服務(wù)器開始，集合中各個(gè)MEC服務(wù)器的卸載任務(wù)量均低于平均卸載任務(wù)量。因此，該算法可以分為步驟3.1和步驟3.2這2個(gè)卸載任務(wù)量級(jí)別不同的集合，其中步驟3.1為卸載任務(wù)量較小的集合，可以將其納入休眠操作范圍；而步驟3.2為卸載任務(wù)量較大的集合，繼續(xù)保持活躍狀態(tài)[7]。

步驟4 根據(jù)步驟3的結(jié)果，選擇步驟3.1作為需要執(zhí)行休眠操作的MEC服務(wù)器集合，宏基站將休眠信號(hào)發(fā)送到小區(qū)中的MEC服務(wù)器之前，詳細(xì)步驟3.1中的MEC服務(wù)器執(zhí)行休眠操作是否會(huì)出現(xiàn)服務(wù)質(zhì)量退化的情況。如果滿足該條件，則選擇相應(yīng)的MEC服務(wù)器執(zhí)行休眠操作。

在執(zhí)行完上述步驟之后，進(jìn)入單周期內(nèi)的MEC服務(wù)器技術(shù)休眠操作流程，在下一個(gè)周期到來前，系統(tǒng)從最初步驟開始執(zhí)行。通常情況下，當(dāng)系統(tǒng)中的卸載任務(wù)量較少時(shí)，如果網(wǎng)絡(luò)中的MEC服務(wù)器保持活躍狀態(tài)的話，會(huì)消耗大量的能量，因此需要執(zhí)行休眠操作，避免卸載任務(wù)量過少的空閑MEC服務(wù)器而產(chǎn)生大量能耗[8]。當(dāng)系統(tǒng)中需要MEC服務(wù)器處理的卸載任務(wù)量增加之后，此時(shí)保持活躍狀態(tài)的MEC服務(wù)器所可以服務(wù)的卸載任務(wù)量會(huì)達(dá)到上限，隨后通知處于休眠狀態(tài)的MEC服務(wù)器進(jìn)入活躍狀態(tài)，對(duì)于卸載任務(wù)量進(jìn)行高效處理。

6 仿真實(shí)驗(yàn)

6.1 設(shè)置參數(shù)

一個(gè)MEC系統(tǒng)中共有N個(gè)（N=5）設(shè)備，對(duì)于物聯(lián)網(wǎng)的參數(shù)設(shè)置見表2。本文研究更側(cè)重于部分任務(wù)卸載情景。

表2 參數(shù)設(shè)置

6.2 實(shí)驗(yàn)結(jié)果

為了對(duì)于本文提出的算法有效性進(jìn)行驗(yàn)證，對(duì)于本地任務(wù)處理(local)（本地設(shè)備端處理所有的任務(wù)）和邊緣云任務(wù)處理（edge cloud）（所有任務(wù)均經(jīng)過邊緣云設(shè)備端進(jìn)行處理）進(jìn)行對(duì)比。

物聯(lián)網(wǎng)設(shè)備的任務(wù)選擇決定如上圖2所示，物聯(lián)網(wǎng)設(shè)備的任務(wù)是由不同帶寬值來選擇確定的。其中，0表示任務(wù)卸載到了本地設(shè)備，而1表示物聯(lián)網(wǎng)設(shè)備將任務(wù)卸載到了邊緣云?？梢钥闯?，如設(shè)備1和設(shè)備2需要計(jì)算資源較少。如果帶寬值較小，則物聯(lián)網(wǎng)設(shè)備可以在邊緣云卸載任務(wù)，然后處理任務(wù)。

圖2 物聯(lián)網(wǎng)設(shè)備的任務(wù)選擇決定

隨寬帶變化的任務(wù)處理時(shí)間變化情況，如下圖3所示。其中，系統(tǒng)代價(jià)是以任務(wù)處理時(shí)間和能耗來進(jìn)行判斷的。網(wǎng)絡(luò)帶寬值較小時(shí)，各個(gè)方面更大。

圖3 隨寬帶變化的任務(wù)處理時(shí)間變化情況

本地處理所需時(shí)間最小情境下的算法最低能耗如圖4所示，本地處理消耗的能量逐漸高于邊緣云處理所消耗的能量。

圖4 隨著寬帶變化的任務(wù)處理時(shí)間的變化

隨著網(wǎng)絡(luò)帶寬值的增加，邊緣云處理的系統(tǒng)代價(jià)要低于本地處理，系統(tǒng)代價(jià)更小，證實(shí)了算法的有效性。系統(tǒng)代價(jià)隨著寬帶的變化情況，如圖5所示。

圖5 系統(tǒng)代價(jià)隨著寬帶的變化情況

7 總結(jié)

綜上所述，因?yàn)楫?dāng)前多MEC服務(wù)器部署下，考慮到用戶和服務(wù)器效益，導(dǎo)致卸載和資源分配的難度大大提升。通過研究邊緣計(jì)算的計(jì)算資源分配和任務(wù)卸載問題，提出了任務(wù)卸載與計(jì)算資源分配算法，結(jié)果表明可以有效降低任務(wù)處理的能耗和延遲。