邊緣計算中多設(shè)備多任務(wù)的能耗均衡優(yōu)化算法

龐 源，武繼剛，陳 龍，姚棉陽

廣東工業(yè)大學 計算機學院，廣州510006

近年來，隨著科學技術(shù)水平的提高，增強現(xiàn)實、虛擬現(xiàn)實、實時游戲等時延敏感型應(yīng)用迅速發(fā)展。此類應(yīng)用的發(fā)展通常需要高性能機器支持。然而，隨著移動設(shè)備的普及，用戶傾向于在移動設(shè)備上完成各項任務(wù)。當用戶希望在移動設(shè)備上完成各項任務(wù)，包括時延敏感型應(yīng)用，就需要移動設(shè)備擁有足夠強大的計算能力和續(xù)航能力。但是，由于移動設(shè)備的便攜性，其體積通常不會很大，其計算能力和續(xù)航能力無法得到保證。為此，歐洲電信標準協(xié)會引入了移動邊緣計算（mobile edge computing，MEC）來解決這個問題。近幾年來，MEC 發(fā)展迅速，在視頻內(nèi)容傳輸、無人駕駛汽車等領(lǐng)域都有著重要的應(yīng)用。隨著物聯(lián)網(wǎng)和第五代通信技術(shù)發(fā)展迅速，互聯(lián)網(wǎng)中數(shù)據(jù)交換量不斷增大。據(jù)思科白皮書估計，到2022 年，移動設(shè)備的人均擁有數(shù)量將達到1.5 臺，移動設(shè)備將占全球IP 總流量的20%。當這些移動設(shè)備產(chǎn)生的數(shù)據(jù)都傳輸?shù)胶诵脑品?wù)器并由其完成時，勢必導致網(wǎng)絡(luò)的擁塞。但MEC 的應(yīng)用解決了這些問題。

MEC 通過協(xié)助完成移動設(shè)備的任務(wù)，可以減少移動設(shè)備完成這些任務(wù)的能耗和時延。然而，由于移動設(shè)備的功率有限，在節(jié)約能耗的同時提高其計算能力成為了一項挑戰(zhàn)?，F(xiàn)今的研究通常關(guān)注利用邊緣服務(wù)器或遠程云，以提高移動設(shè)備的計算能力，比如利用邊緣服務(wù)器和云服務(wù)器來最小化總能耗或最小化任務(wù)完成時間。但是目前的這些研究大都沒有涉及多移動設(shè)備共存計算任務(wù)卸載場景下，移動設(shè)備能耗均衡保障問題。

多設(shè)備多任務(wù)的能耗均衡問題是最小化多個設(shè)備的最大能耗問題。假設(shè)有一個名為的邊緣服務(wù)器和兩個分別名為、的移動設(shè)備。為了簡化，假設(shè)移動設(shè)備、均存在兩個任務(wù)，這兩個任務(wù)均需要在兩個時間周期內(nèi)完成。為簡化描述，假設(shè)邊緣服務(wù)器和移動設(shè)備在每個時間周期只能運行一個任務(wù)。此外，任務(wù)交付到邊緣服務(wù)器執(zhí)行時，所產(chǎn)生的能耗代價更低。如果將中的兩個子任務(wù)都交付給，則無法再使用邊緣服務(wù)器，這導致設(shè)備的能耗顯著高于設(shè)備，顯然這是不均衡的。因此，為了達到能耗均衡，需要重新設(shè)計任務(wù)調(diào)度策略。

據(jù)了解，與本文研究最相似的文獻為文獻[12]和文獻[13]。其中文獻[12]的結(jié)構(gòu)也是三層結(jié)構(gòu)，同時考慮了任務(wù)的依賴關(guān)系，但其目標是最小化總能耗，沒有考慮移動設(shè)備能耗的均衡問題。并且該文章的結(jié)構(gòu)由端邊云三者組成，也沒有考慮到使用中繼設(shè)備來優(yōu)化系統(tǒng)。而文獻[13]的結(jié)構(gòu)為多個原設(shè)備和一個由邊緣服務(wù)器集成的無線訪問接入點（wireless access point，AP）組成，研究的是兩個用戶下最小化加權(quán)能耗和。但該文獻也并沒有使用中繼設(shè)備，且該文獻中的任務(wù)是可以被隨意劃分的，任務(wù)之間不考慮依賴關(guān)系。

因此為了改進現(xiàn)有的工作，綜合上述文章，本文在原有的結(jié)構(gòu)中去除了傳輸能耗更大的云服務(wù)器，加入了中繼設(shè)備節(jié)點作為任務(wù)的中轉(zhuǎn)節(jié)點，構(gòu)成了一個由移動設(shè)備、中繼設(shè)備和邊緣服務(wù)器組成的三層結(jié)構(gòu)。本文的貢獻點如下：

（1）基于上述結(jié)構(gòu)設(shè)計了一種滿足任務(wù)依賴的多設(shè)備多任務(wù)能耗均衡貪心算法MMG（min-max greedy algorithm）。較之現(xiàn)存的最小能耗算法，MMG 算法在具有任務(wù)依賴關(guān)系的多設(shè)備多任務(wù)能耗均衡問題上具有更有效的表現(xiàn)。

（2）將能耗均衡問題轉(zhuǎn)化為最小化最大能耗問題，并且設(shè)計了總能耗優(yōu)化算法以及隨機算法來與MMG 算法進行對比。

（3）為了驗證MMG 算法的優(yōu)越性，進行了大量的對比實驗。實驗結(jié)果證明，MMG 算法的平均性能在能耗均衡方面可進一步提升66.59%。

1 相關(guān)工作

在MEC 的研究上，大部分的團隊集中于研究如何充分地利用服務(wù)器的資源以提高移動設(shè)備的性能。其目標一般分為兩種：節(jié)約能耗成本和減少任務(wù)完成時間。

在節(jié)約能耗成本上，文獻[14]設(shè)計了一個動態(tài)計算卸載算法和一個對應(yīng)的在線卸載算法來解決動態(tài)計算卸載問題和節(jié)省移動設(shè)備能耗。文獻[15]提出了一種調(diào)度算法來分配無線帶寬，使所有用戶的總成本最小化。文獻[16]提出了兩種卸載策略，以最小化延遲約束下的能耗。文獻[17]提出了一種邊緣云架構(gòu)，并設(shè)計了貪心算法來最小化移動設(shè)備的總能耗。文獻[18]設(shè)計了一種結(jié)合“0-1”編程和聯(lián)盟博弈并通過在移動用戶之間共享計算結(jié)果的分布式算法來最小化移動設(shè)備的總能耗。文獻[19]研究的是在一個由遠程云和異構(gòu)本地處理器組成的體系結(jié)構(gòu)中，在時間約束下最小化應(yīng)用程序總執(zhí)行成本問題。文獻[20]提出了一種分布式線性松弛啟發(fā)式算法和貪婪啟發(fā)式算法來最小化移動用戶的總能耗。文獻[21]考慮的是能耗問題和敏感型任務(wù)的調(diào)度策略問題，并設(shè)計了一種分布式動態(tài)卸載和資源調(diào)度策略，目標是最小化移動設(shè)備能耗，但沒有考慮設(shè)備間的能耗均衡問題。上述的這些文章都沒有充分考慮任務(wù)完成時間的問題，也沒有考慮利用中繼設(shè)備的協(xié)作作用來更好地優(yōu)化移動設(shè)備的能耗。

在降低任務(wù)完成時間上，文獻[22]通過利用馬爾可夫決策方法，提出了一種高效的一維搜索算法，使每個計算任務(wù)的平均延遲最小化。在多用戶多任務(wù)問題上，文獻[23]設(shè)計了集中式分布式貪心最大調(diào)度算法，解決了多用戶多任務(wù)計算卸載問題，但文章沒有考慮任務(wù)依賴關(guān)系。文獻[24]提出了一種“邊緣-云”協(xié)作的“依賴-感知”卸載方案，并設(shè)計了兩種算法，解決的是在任務(wù)依賴約束和給定預算的情況下最小化設(shè)備任務(wù)完成時間。文獻[25]假設(shè)邊緣服務(wù)器的資源無限大，研究不同移動用戶隨機到達的異構(gòu)延遲敏感計算任務(wù)環(huán)境下，使移動用戶在任何給定的計算卸載策略下的總時延最小問題，并將該問題建模成一個動態(tài)優(yōu)先隊列，同時設(shè)計了一種優(yōu)先傳輸調(diào)度策略來解決。然而上述文章也都沒有考慮使用中繼設(shè)備。

除能耗和任務(wù)完成時間外，也有一些研究致力于解決邊緣計算所遇到的其他難解問題。文獻[26]利用博弈論設(shè)計了一種分布式計算卸載算法，研究了多信道無線干擾環(huán)境下的多用戶卸載問題。文獻[27]利用進化博弈策略來研究動態(tài)環(huán)境下的多用戶計算卸載問題。文獻[28]利用無人機的移動性來解決邊緣服務(wù)器的低移動性問題。

2 模型

本章將會先介紹本文系統(tǒng)的模型。本文所使用到的符號及其含義如表1 所示。

表1 本文所用符號Table 1 Notations of this paper

2.1 系統(tǒng)模型

如圖1 所示，系統(tǒng)是一個具有三層架構(gòu)的移動邊緣計算模型。系統(tǒng)的頂層位于一個具有計算能力的邊緣服務(wù)器上，而這個服務(wù)器一般位于基站或遠程訪問點。系統(tǒng)的中間層為中繼設(shè)備，它們只負責任務(wù)傳輸?shù)回撠熑蝿?wù)的執(zhí)行。系統(tǒng)底層是移動設(shè)備，每個移動設(shè)備都有一個正在運行的應(yīng)用程序，每個應(yīng)用程序由多個具有任務(wù)依賴關(guān)系的子任務(wù)組成。

圖1 系統(tǒng)模型Fig.1 System model

移動設(shè)備通過無線連接的方式與中繼設(shè)備進行通信，如Wi-Fi 等。中繼設(shè)備也通過無線連接與邊緣服務(wù)器通信。模型中存在多個移動設(shè)備，用集合M={,,…,m}表示，其中是移動設(shè)備的數(shù)量。此外，模型中的中繼設(shè)備用集合H={,,…,h}表示，其中是中繼設(shè)備的數(shù)量。對于每一個移動設(shè)備,都包含個有依賴關(guān)系的子任務(wù)，用N={,,…, n}表示。

以下，將詳細介紹本文的通信模型和計算模型。

2.2 無線通信模型

無線通信存在于移動設(shè)備和中繼設(shè)備以及中繼設(shè)備和邊緣服務(wù)器之間。根據(jù)香農(nóng)公式，從第個移動設(shè)備到第個中繼設(shè)備之間的上行數(shù)據(jù)速率可以表示為：

類似地，第個中繼設(shè)備與邊緣服務(wù)器之間的上行數(shù)據(jù)速率為：

其中，d為節(jié)點與之間的歐式距離，為路徑損失分量，且,∈{M ?H?{}}。

2.3 計算模型

當中的在移動設(shè)備本地執(zhí)行時，其執(zhí)行時間可以表示為：

其中，W是完成第個移動設(shè)備中的第個子任務(wù)所需要的工作量大小，f是第個移動設(shè)備的CPU 時鐘周期頻率，單位為cycle/s，對應(yīng)的能耗可以表示為：

其中，ρ為取決于移動設(shè)備架構(gòu)的一個正常數(shù)。如果第個移動設(shè)備中的第個子任務(wù)被卸載到第個中繼設(shè)備時，此階段的傳輸時間可以表示為：

其中，D為第個移動設(shè)備的第個子任務(wù)的數(shù)據(jù)量大小。這個過程的能耗可以表示為：

如果第個移動設(shè)備中的第個子任務(wù)從第個中繼設(shè)備被卸載到邊緣服務(wù)器，此過程的傳輸時間可以表示為：

對應(yīng)的能耗為：

在邊緣服務(wù)器上完成第個移動設(shè)備的第個子任務(wù)的計算時間為：

其中，f為的CPU 時鐘周期頻率，單位為cycle/s。

因此，完成第個移動設(shè)備的第個子任務(wù)的能耗為：

2.4 任務(wù)依賴性

本節(jié)定義了子任務(wù)之間的依賴關(guān)系。子任務(wù)的完成時間分為以下幾部分。

因此，第個移動設(shè)備完成所有子任務(wù)所需要的時間為：

綜上所述，第個移動設(shè)備的總能量消耗可以表示為：

2.5 問題定義

本節(jié)將給出最小化最大能耗問題的公式化定義。最小化最大能耗問題描述如下：

其中，為給定的第個移動設(shè)備完成所有子任務(wù)的預算時間。式（20）是對第個移動設(shè)備的完成時間的約束。式（21）和式（22）是子任務(wù)的依賴性約束，確保第個移動設(shè)備的第個子任務(wù)只能在其所有前驅(qū)子任務(wù)完成后才能開始執(zhí)行。式（23）表示第個移動設(shè)備的第個子任務(wù)只能在本地執(zhí)行或者在邊緣服務(wù)器執(zhí)行。

據(jù)現(xiàn)有的研究可知，最小化最大能耗問題是一個找尋調(diào)度策略的優(yōu)化問題，可以規(guī)約為文獻[29]中的最小化最大時間問題，而該文獻將最小化最大時間問題規(guī)約為NP-hard 整數(shù)規(guī)劃問題。因此，最小化最大能耗問題為NP-hard。

3 算法設(shè)計與分析

本章對提出的MMG 算法進行詳細描述。

本文根據(jù)子任務(wù)的數(shù)量將劃分為幾個部分，并且每一層的每個子任務(wù)都應(yīng)該在劃分完成之后的區(qū)間結(jié)束。對于每個子任務(wù)，根據(jù)時間和能耗條件確定計算模式。然后，對于每個子任務(wù)，通過最小-最大算法來獲得分配方案。此外，再判斷分配方案是否滿足時間限制。

在以上分析的基礎(chǔ)上，首先，通過計算獲得不同子任務(wù)在本地計算、遷移到邊緣服務(wù)器計算的能耗，并形成一個能耗矩陣。對于每一個移動設(shè)備源節(jié)點，都隨機分配一個中繼設(shè)備節(jié)點。假設(shè)是源節(jié)點到中繼的最大能耗，找到并將所有中繼設(shè)置為“unused”，當中繼設(shè)備被占用時設(shè)置為“used”。獲取分配策略。逐個判斷最大能耗所分配的中繼設(shè)備節(jié)點之外是否有其他中繼設(shè)備節(jié)點可用。若可用，則更換中繼設(shè)備節(jié)點，確定新的（調(diào)整能耗使得分配策略所得的總能耗在盡量小的情況下能耗差更小）。若未找到其他可用中繼設(shè)備節(jié)點，則開始判斷分配策略是否滿足時間約束，若不滿足，則重新分配策略；若滿足，則獲得可行分配策略。

設(shè)定移動設(shè)備的數(shù)量為，每個移動設(shè)備的子任務(wù)數(shù)量為，中繼設(shè)備的數(shù)量為。算法的總時間復雜度為(+)。

首先，本文提出的算法分三層嵌套循環(huán)來計算時間消耗和能量消耗，其時間復雜度為()。然后，分析了最小-最大函數(shù)的時間復雜度。每次迭代的復雜度為()，每次迭代最多有對，因此最小-最大的總時間復雜度為()。在時間檢查方面，這是一個只有一層循環(huán)的sum 函數(shù)，包括兩層嵌套的While 循環(huán)，每個While 循環(huán)不超過次，因此其時間復雜度為()。此外，第二步是在不同的子任務(wù)層下執(zhí)行的，因此第二步的總時間復雜度為()。該算法的總時間復雜度為(+)。

任意移動邊緣計算結(jié)構(gòu)的二部圖都可以轉(zhuǎn)化為能量消耗矩陣。將和分別表示為一個任意小的正常數(shù)和子任務(wù)數(shù)，則該貪心算法的近似比可以達到(1+)。

在定理1 中，分析得到算法的時間復雜度為(+)，其最大的迭代次數(shù)為。對于一個子任務(wù)而言，根據(jù)式（7）、式（9），分別令其傳輸能量比為和；根據(jù)式（5），令其計算能量比為。每個“設(shè)備-中繼”對的能耗可以表示為E=min(σ+γ, ψ)?！霸?中繼”的最大和有效最小能耗分別設(shè)為和。則有：

其中

因此，每個“設(shè)備-中繼”對的能量消耗上界為。設(shè)=/，其中為每個“設(shè)備-中繼”對最大能耗平均調(diào)整的步長，是迭代的最大次數(shù)，則有=/。設(shè)()為最小化每個“設(shè)備-中繼”對的最大能耗的最優(yōu)解，其中對應(yīng)的最優(yōu)策略。設(shè)′為貪心算法中每個“設(shè)備-中繼”對的最大能耗，則有()≤(′)。又=/，則有=。因此，是其中一個移動設(shè)備能耗調(diào)整的上界。據(jù)此，則有：根據(jù)式（24）和0 ＜＜()，有：

本文所提出的貪心算法偽代碼如下所示：

Min-max greedy algorithm(MMG)

輸入：工作量大小，數(shù)據(jù)量大小，時間約束。

輸出：分配策略。

Min-max algorithm

輸入：子任務(wù)數(shù)量的級別，能量消耗矩陣。

輸出：分配策略。

1.for(,) in listdo

2.檢查中繼節(jié)點的可用性

3.if(,) is availability then

4.將源節(jié)點的對移除

5.將(,)對分配給源節(jié)點

6.回到第二行來確定一個新的

7.if no pair availability then

8.算法結(jié)束

4 性能評估

本章設(shè)計了實驗來研究所提出的算法的性能。本文利用Matlab r2016a 進行了大量的實驗，并得到了實驗結(jié)果。

文中將覆蓋范圍設(shè)定為50 m×50 m。默認情況下，子任務(wù)、移動設(shè)備和中繼設(shè)備的數(shù)量分別設(shè)置為4、3和3，實驗中的其他參數(shù)如表2所示。在整個實驗過程中，文章假設(shè)計算任務(wù)的數(shù)據(jù)大小、工作量大小在[25 Kbit,1 024 Kbit]范圍內(nèi)遵循正態(tài)分布，平均值為512，標準差為256。此外，本文還設(shè)計了一個總能耗優(yōu)化算法（total energy consumption minimization algorithm，TECM）的實驗對比算法。

表2 實驗參數(shù)Table 2 Experimental parameters

在實驗1 中，文章研究了路徑損耗分量與子任務(wù)最大能量消耗之間關(guān)系的變化。圖2（a）描述了子任務(wù)的最大能量消耗隨著路徑損耗分量的增加而增加。從式（1）、（2）、（3）、（6）、（8）中得出，子任務(wù)的最大能量消耗與路徑損耗分量成正比，這解釋了實驗圖2 中的曲線形狀。實驗表明，當移動設(shè)備的傳輸功率分別為5 dBm 和6 dBm 時，MMG 算法在最小化子任務(wù)的最大能耗方面的性能平均比隨機算法提升66.59%和61.87%，接近蠻力算法得到的最優(yōu)解。圖2（b）基于圖2（a）的結(jié)果，結(jié)果表明，當移動設(shè)備的最小傳輸功率分別為5 dBm 和6 dBm 時，MMG 算法的近似比分別為1.096 9 和1.098 4。

圖2 實驗1Fig.2 The first experiment

實驗2 研究了子任務(wù)在時間約束變化下的最大能量消耗。在圖3（a）和圖3（b）中，移動設(shè)備的最小傳輸功率為5 dBm。結(jié)果表明，貪心算法的性能優(yōu)于總能耗優(yōu)化算法和隨機算法。

圖3 實驗2Fig.3 The second experiment

最后，在路徑損耗分量為0.1 的情況下，文章觀察了子任務(wù)的最大能量消耗隨任務(wù)層數(shù)的變化。如圖4（a）所示，隨著任務(wù)數(shù)量的增加，每個子任務(wù)的完成時間相應(yīng)地減少，從而導致任務(wù)需要在更短的時間內(nèi)執(zhí)行。這導致完成任務(wù)所需的能量消耗增加。但是MMG 算法在最小子任務(wù)的最大能耗的性能上明顯優(yōu)于TECM 算法和隨機算法。如圖4（b）所示，隨著子任務(wù)數(shù)的增加，子任務(wù)的最大能量消耗增加，當移動設(shè)備的傳輸功率分別為5 dBm 和6 dBm 時，MMG 的近似比分別為1.353 7、1.353 8。

圖4 實驗3Fig.4 The third experiment

5 結(jié)束語

本文研究了多移動設(shè)備多任務(wù)中的能耗均衡問題，這個問題是NP-hard。文章在原有的結(jié)構(gòu)中去除了傳輸能耗更大的云服務(wù)器，加入了中繼設(shè)備節(jié)點作為任務(wù)的中轉(zhuǎn)節(jié)點，構(gòu)成了一個由移動設(shè)備、中繼設(shè)備和邊緣服務(wù)器組成的三層結(jié)構(gòu)。同時本文設(shè)計了MMG 算法來求解能耗均衡問題，并通過大量的對比實驗證明了MMG 算法的有效性。