面向移動(dòng)邊緣計(jì)算的聯(lián)合計(jì)算卸載和資源分配策略研究

黃冬晴 俞黎陽 陳玨 魏同權(quán)

摘要：隨著無人駕駛、在線游戲、虛擬現(xiàn)實(shí)等低延遲應(yīng)用的大量涌現(xiàn)，傳統(tǒng)集中式的移動(dòng)云計(jì)算范式越來越難以滿足此類用戶服務(wù)質(zhì)量的需求.為彌補(bǔ)云計(jì)算的不足，移動(dòng)邊緣計(jì)算應(yīng)運(yùn)而生.移動(dòng)邊緣計(jì)算通過計(jì)算卸載，將計(jì)算任務(wù)遷移到網(wǎng)絡(luò)邊緣服務(wù)器來為用戶提供計(jì)算和存儲(chǔ)資源.然而，現(xiàn)有大部分工作僅考慮了延遲或能耗的單目標(biāo)性能優(yōu)化，未考慮延遲和能耗的均衡優(yōu)化.為減少任務(wù)延遲和設(shè)備能耗，提出了一種面向多用戶的聯(lián)合計(jì)算卸載和資源分配策略.該策略首先利用拉格朗日乘子法獲得給定卸載決策的最佳計(jì)算資源分配;然后，提出一個(gè)基于貪心算法的計(jì)算卸載算法獲得最佳卸載決策;最后，通過不斷迭代得到最終解.實(shí)驗(yàn)結(jié)果表明，與基準(zhǔn)算法相比，所提算法最高可以降低40%的系統(tǒng)成本.

關(guān)鍵詞：移動(dòng)邊緣計(jì)算;計(jì)算卸載;資源分配;拉格朗日乘子法;貪心算法

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：ADOI：10.3969/j.issn.l000-5641.2021.06.010

Research on joint computation offloading and resource allocation strategy for mobile edge computing

HUANG Dongqing1，YU Liyang1，CHEN Jue2，WEI Tongquan1

（1. School of Computer Science and Technology. East China Normal University，Shanghai 200062. China;

2. School of Electronic and Electrical Engineering. Shanghai University of Engineering Science，Shanghai 201620，China）

Abstract：With the emergence of low-latency applications such as driverless cars，online gaming，and virtual reality，it is becoming increasingly difficult to meet users demands for service quality using the traditional centralized mobile cloud computing model. In order to make up for the shortages of cloud computing，mobile edge computing came into being，which provides users with computing and storage resources by migrating computing tasks to network edge servers through computation offloading. However，most of the existing work processes only consider single-objective performance optimization of delay or energy consumption，and do not consider the balanced optimization of delay and energy consumption. Therefore，in order to reduce task delay and equipment energy consumption，a multi-user joint computation offloading and resource allocation strategy is proposed. In this strategy，the Lagrange multiplier method is used to obtain the optimal allocation of computing resources for a given offloading decision. Then，a computation offloading algorithm based on a greedy algorithm is proposed to obtain the optimal offloading decision：thefinal solution is obtained through continuous iteration. Experimental results show that，compared with the benchmark algorithm，the proposed algorithm can reduce system costs by up to 40%.

Keywords：mobile edge computing;computation offloading;resource allocation;Lagrange multiplier method;greedy algorithm

0引言

隨著移動(dòng)互聯(lián)網(wǎng)和5G通信技術(shù)[1]的不斷發(fā)展，移動(dòng)設(shè)備上需要處理越來越多的延遲敏感性應(yīng)用，例如無人駕駛、在線游戲、虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)等[2].但是，由于計(jì)算和存儲(chǔ)資源的限制，移動(dòng)設(shè)備運(yùn)行這些應(yīng)用會(huì)造成很高的延遲和能耗.為解決該問題，移動(dòng)云計(jì)算（Mobile Cloud Computing，MCC）誕生了，它將用戶部分計(jì)算任務(wù)通過上行鏈路卸載到云端服務(wù)器，減少了任務(wù)的執(zhí)行時(shí)間.然而在傳統(tǒng)MCC中，集中式部署的云服務(wù)器與移動(dòng)設(shè)備距離較遠(yuǎn)，兩者數(shù)據(jù)傳輸過程中會(huì)占用大量網(wǎng)絡(luò)帶寬導(dǎo)致網(wǎng)絡(luò)擁塞，從而增加了通信延遲和能量消耗.因此，傳統(tǒng)的MCC范式越來越難以滿足用戶服務(wù)質(zhì)量的需求.

針對MCC中存在的問題，歐洲標(biāo)準(zhǔn)協(xié)會(huì)提出了移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）[3].在MEC系統(tǒng)中，具有計(jì)算和存儲(chǔ)資源的邊緣服務(wù)器被部署在更靠近用戶的網(wǎng)絡(luò)邊緣，移動(dòng)設(shè)備便能以更低的通信延遲進(jìn)行任務(wù)卸載.MEC的優(yōu)勢包括低延遲、可靠的服務(wù)交付、高效的網(wǎng)絡(luò)運(yùn)營等.隨著移動(dòng)用戶數(shù)目的增加，邊緣服務(wù)器因其計(jì)算資源受限而影響了任務(wù)執(zhí)行延遲和能耗.因此，計(jì)算卸載和資源分配策略成為實(shí)現(xiàn)系統(tǒng)高效卸載的關(guān)鍵.

針對多用戶MEC系統(tǒng)資源受限的場景，有些學(xué)者關(guān)注最大程度減少任務(wù)時(shí)延：Zhang等[4]研究了基于時(shí)分多址的MEC系統(tǒng)中計(jì)算和通信資源分配問題，設(shè)計(jì)了一個(gè)次梯度算法以最大程度減少設(shè)備延遲;Alam等[5]提出了一種基于深度Q學(xué)習(xí)的自主計(jì)算卸載框架，用于處理系統(tǒng)中資源分配和移動(dòng)性問題;Paymard等[6]提出了一種高效可感知傳輸?shù)娜蝿?wù)調(diào)度和資源分配算法，聯(lián)合優(yōu)化上行/下行子載波、傳輸功率、計(jì)算資源分配及任務(wù)調(diào)度;Liu等[7]考慮任務(wù)隨機(jī)性和計(jì)算強(qiáng)度，設(shè)計(jì)了一個(gè)卸載框架，并通過分析邊緣服務(wù)器排隊(duì)模型提出了基于Lyapunov優(yōu)化的動(dòng)態(tài)資源分配算法.這些工作通常針對時(shí)延敏感型應(yīng)用，雖然都在一定程度上實(shí)現(xiàn)以極低的延遲進(jìn)行任務(wù)卸載，但是忽略了系統(tǒng)中設(shè)備的能量消耗.

此外，有學(xué)者重點(diǎn)關(guān)注進(jìn)一步節(jié)省系統(tǒng)中設(shè)備的能量消耗，以最大程度延長系統(tǒng)設(shè)備的使用壽命：Guo等[8]考慮到高干擾、多路訪問和有限資源，設(shè)計(jì)了一種基于遺傳算法的次優(yōu)卸載算法，以實(shí)現(xiàn)卸載決策、無線和計(jì)算資源分配的聯(lián)合優(yōu)化;Li等[9]基于Lyapunov優(yōu)化框架，提出了一種在線能耗最小化的卸載算法，來實(shí)現(xiàn)最佳能量和數(shù)據(jù)傳輸時(shí)間分配、任務(wù)卸載比例、傳輸功率以及設(shè)備計(jì)算頻率;Qian等[10]通過共同優(yōu)化資源分配和連續(xù)干擾消除排序來減少能耗，即先基于Karush-Kuhn-Tucher （KKT）條件和梯度下降法獲得最佳的傳輸功率和計(jì)算資源分配，然后提出基于禁忌搜索的排序算法;Zeng等[11]針對單小區(qū)中正交多址和非正交多址場景提出了近似最優(yōu)的解決方案，以實(shí)現(xiàn)傳輸功率和計(jì)算資源最佳聯(lián)合分配，同時(shí)也證明了非正交多址優(yōu)于正交多址方案.這些工作通常針對能量消耗型應(yīng)用，一般都是在滿足任務(wù)計(jì)算時(shí)延約束下最大程度降低系統(tǒng)的能耗，但是以增加計(jì)算時(shí)延的開銷為代價(jià).

以上研究工作都傾向于從延遲或能耗單目標(biāo)性能進(jìn)行系統(tǒng)優(yōu)化，未實(shí)現(xiàn)系統(tǒng)延遲和能耗的均衡優(yōu)化.在某些情況下，本文希望用更少的時(shí)間及更低的能耗完成系統(tǒng)所有計(jì)算任務(wù)，從而讓服務(wù)器可以更早地完成計(jì)算任務(wù)，為更多的用戶提供服務(wù)，同時(shí)延長系統(tǒng)壽命.因此，本文在考慮MEC系統(tǒng)場景下任務(wù)卸載中延遲和能耗兩個(gè)因素之間的權(quán)衡的基礎(chǔ)上，提出了一種面向多用戶的聯(lián)合計(jì)算卸載和資源分配策略.

本文主要貢獻(xiàn)概述如下.

（1）考慮多用戶單小區(qū)MEC系統(tǒng)場景，建立了本地計(jì)算模型和移動(dòng)邊緣計(jì)算模型.每個(gè)任務(wù)計(jì)算成本被表述為時(shí)延和能耗加權(quán)和，在有限的信道和計(jì)算資源約束下，優(yōu)化問題被建模為一個(gè)混合整數(shù)非線性規(guī)劃（Mixed Integer Nonlinear Programming，MINILP）問題.

（2）提出了一種面向多用戶的聯(lián)合計(jì)算卸載和資源分配策略.針對資源分配子問題，采用拉格朗日乘子法獲得最佳計(jì)算資源分配.針對計(jì)算卸載子問題，提出一種基于貪心算法的計(jì)算卸載算法.最后，通過不斷迭代獲得最優(yōu)卸載決策和計(jì)算資源分配.

（3）通過仿真實(shí)驗(yàn)，驗(yàn)證了本文所提算法的有效性.與本地執(zhí)行算法、全卸載算法、分支定界算法以及帶漢明距離終止的動(dòng)態(tài)規(guī)劃卸載算法進(jìn)行比較，本文所提算法優(yōu)于其他算法，且系統(tǒng)成本最高可以降低40%.

1系統(tǒng)架構(gòu)和計(jì)算模型

在本章中，首先對系統(tǒng)架構(gòu)進(jìn)行詳細(xì)介紹，然后給出任務(wù)計(jì)算模型，包括本地計(jì)算和移動(dòng)邊緣計(jì)算.

1.1系統(tǒng)架構(gòu)

如圖1所示，考慮1個(gè)多用戶單小區(qū)MEC系統(tǒng)，有N個(gè)移動(dòng)設(shè)備（Mobile Device，MD），每個(gè)移動(dòng)設(shè)備都被視為用戶，用戶通過無線信道的方式連接附近基站（Base Station，BS）.假設(shè)在某一時(shí)刻每個(gè)用戶僅產(chǎn)生1個(gè)計(jì)算任務(wù)，對于第i（i=1，2，…，N）個(gè)移動(dòng)設(shè)備，定義表示其計(jì)算任務(wù)要求，其中B表示計(jì)算任務(wù)的數(shù)據(jù)大小，即移動(dòng)設(shè)備傳輸?shù)竭吘壏?wù)器的數(shù)據(jù)量，包括系統(tǒng)設(shè)置、程序代碼和輸入?yún)?shù);C表示任務(wù)所需的計(jì)算資源量，即完成計(jì)算任務(wù)需要的CPU周期數(shù).電信運(yùn)營商在基站附近部署有MEC服務(wù)器，其具有一定的存儲(chǔ)容量和計(jì)算能力，可以存儲(chǔ)用戶的輸入任務(wù)并提供計(jì)算服務(wù).表1總結(jié)了本文所使用的關(guān)鍵符號及其含義.

由于MEC服務(wù)器為多個(gè)移動(dòng)用戶提供服務(wù)，計(jì)算任務(wù)可以選擇卸載到MEC服務(wù)器或本地設(shè)備執(zhí)行.定義用戶i的二進(jìn)制卸載決策變量為a∈{0，1}，其中a=1表示其計(jì)算任務(wù)將決定通過無線信道卸載到MEC服務(wù)器，a=0表示任務(wù)在本地設(shè)備上進(jìn)行計(jì)算.因此，A= {a，a，…，a}為所有用戶卸載決策集合.

對于小區(qū)中不同用戶傳輸，采用正交頻分多址方案.整個(gè)頻譜被均勻的劃分為K個(gè)子信道，將每個(gè)任務(wù)分配給1個(gè)子信道，確保用戶上行鏈路傳輸信道的正交性.定義B為無線信道的系統(tǒng)帶寬，W為用戶帶寬.因此，BS最多可以服務(wù)的用戶數(shù)為

每個(gè)移動(dòng)用戶通過正交頻分復(fù)用信道接入小區(qū)基站，根據(jù)香農(nóng)公式可知，移動(dòng)用戶i的上行鏈路傳輸速率為

其中，為信噪比，p表示用戶i的傳輸功率，g表示用戶i與BS之間的信道增益，σ為高斯信道噪聲的方差.

1.2計(jì)算模型

計(jì)算任務(wù)的處理可分為本地計(jì)算和移動(dòng)邊緣計(jì)算兩種方式，下面分別介紹這兩種計(jì)算方式在時(shí)延和能耗方面的計(jì)算開銷.

（1）本地計(jì)算

對于本地計(jì)算方式，每個(gè)用戶在本地設(shè)備執(zhí)行其計(jì)算任務(wù).由表1可知，C表示用戶任務(wù)的計(jì)算需求，即完成計(jì)算任務(wù)所需的總CPU周期數(shù).定義f表示用戶i的本地設(shè)備CPU計(jì)算能力，即每秒CPU周期數(shù).用戶i的任務(wù)在本地計(jì)算所需的時(shí)延為

相應(yīng)地，本地計(jì)算所需的能耗為

E=εC，（4）

其中，ε是能耗系數(shù)，表示用戶i的本地設(shè)備每個(gè)CPU周期消耗的能量，是用戶CPU計(jì)算能力的超線性函數(shù)[12-13].設(shè)置能耗模型為ε=k（f），其中k是芯片的能耗系數(shù)，這里取k=10，r=2.

（2）移動(dòng)邊緣計(jì)算

對于移動(dòng)邊緣計(jì)算方式，每個(gè)用戶將根據(jù)卸載決策通過無線信道將任務(wù)卸載到MEC服務(wù)器上.任務(wù)卸載過程分為上傳任務(wù)、處理任務(wù)和下載任務(wù)3個(gè)部分.任務(wù)上傳時(shí)延為，處理時(shí)延為.由于任務(wù)處理后的數(shù)據(jù)大小遠(yuǎn)小于任務(wù)執(zhí)行之前的數(shù)據(jù)大小，并且下行鏈路傳輸速率也遠(yuǎn)遠(yuǎn)高于上行鏈路傳輸速率，因此下載任務(wù)的時(shí)延和能耗一般忽略不計(jì).根據(jù)用戶上行鏈路傳輸速率r，任務(wù)卸載到MEC服務(wù)器所需的時(shí)延為

其中，s表示MEC服務(wù)器分配給任務(wù)i的計(jì)算資源量.定義S表示MEC服務(wù)器上可用的最大計(jì)算資源量，即服務(wù)器CPU計(jì)算能力，且滿足.

相應(yīng)地，任務(wù)卸載到MEC服務(wù)器所需的能耗為

其中，p和p分別是用戶i設(shè)備的傳輸功率大小和空閑狀態(tài)下電路功率大小.

2問題描述

在MEC系統(tǒng)中，用戶的服務(wù)質(zhì)量由完成任務(wù)的延遲和能耗決定.定義β和β分別表示第i個(gè)用戶任務(wù)執(zhí)行時(shí)延和能耗的偏好參數(shù)，滿足β，β∈[0，1]，β+β=1，可以根據(jù)任務(wù)完成時(shí)間的需求和剩余電池壽命來進(jìn)行設(shè)置.例如，在線游戲、高清視頻等時(shí)延要求較高的應(yīng)用可以增加為β并減少β從而最大限度減少延遲;而當(dāng)設(shè)備電量較低時(shí)，可以減少β并增加β來節(jié)省設(shè)備能耗.考慮到不同用戶的偏好，定義用戶i的計(jì)算總成本為時(shí)延和能耗的加權(quán)和，則可獲得本地計(jì)算和移動(dòng)邊緣計(jì)算下的總成本，分別為

C=βT+βE（7）

C=βT+βE（8）

對于所有用戶i∈N，計(jì)算系統(tǒng)總成本，總成本為

為提高用戶任務(wù)卸載效率，本文主要是通過優(yōu)化卸載決策和計(jì)算資源分配來最小化任務(wù)總成本. 優(yōu)化問題P1建模如下.

式（10）中，A={a，a，…，a，…，a}是所有任務(wù)卸載決策集合;S={s，s，…，s，…，s}是計(jì)算資源分配集合;約束C1控制信道容量，BS最多可以同時(shí)服務(wù)K個(gè)用戶;約束C2確保計(jì)算卸載決策是二進(jìn)制變量;約束C3表示MEC服務(wù)器CPU計(jì)算資源量約束;最后約束C4限制資源分配范圍.

由于存在整數(shù)變量A以及線性變量S，問題P1為1個(gè)MINILP問題，被證明是NP-hard的.隨著用戶數(shù)量的急劇增加，直接解決此問題非常困難，因此必須找到一種有效且簡化的解決方案.

3計(jì)算卸載和資源分配策略

觀察到問題P1中約束C1和約束C2用于約束整數(shù)變量A，約束C3和約束C4用于約束線性變量S，彼此是相互分離的，因此本文考慮將優(yōu)化問題拆分為兩個(gè)子問題：計(jì)算資源分配子問題及計(jì)算卸載子問題，最后，通過迭代獲得最優(yōu)的卸載決策和資源分配結(jié)果.

3.1基于拉格朗日乘子法的計(jì)算資源分配

因?yàn)镸EC服務(wù)器僅為確定卸載的用戶任務(wù)分配計(jì)算資源，給定U為卸載用戶集合，即.首先，制定計(jì)算資源分配子問題P2，為

計(jì)算目標(biāo)函數(shù)的二階導(dǎo)數(shù)，可得

黑塞矩陣（Hessian Matrix）中參數(shù)都是正數(shù)，因此目標(biāo)函數(shù)C（S）的黑塞矩陣是正定的;而C（S）的域是凸的，這是一個(gè)凸優(yōu)化問題，用拉格朗日乘子法進(jìn)行求解.

通過引入拉格朗日乘子λ，建立問題P2的拉格朗日函數(shù)

通過KKT條件，有

通過求解上述公式，得到最優(yōu)資源分配為

將式（16）代入P2，得到目標(biāo)函數(shù)最優(yōu)值，為

3.2基于貪心算法的計(jì)算卸載算法

通過上面的討論，已經(jīng)為給定用戶卸載集合U獲得了最優(yōu)資源分配的封閉形式解，并計(jì)算得了最優(yōu)的C（S）.在此基礎(chǔ)上，原始優(yōu)化問題轉(zhuǎn)換為

可以看出這是關(guān)于A的0-1規(guī)劃問題，也是NP完全問題.解決該問題的簡單方法是通過分支定界（Branch and Bound，BB）算法，在遍歷所有卸載決策情況下，算法計(jì)算復(fù)雜度為O（2）.本文提出了一種基于貪心算法的計(jì)算卸載算法，該算法基本思想是將問題變量先進(jìn)行松弛，即先求解該松弛問題，再把變量修正到{0，1}上，得到問題的解.

步驟一：采用變量松弛法將約束條件C2中的二元變量α進(jìn)行松弛，問題可以等價(jià)地替換為問題P3，即

在問題P3的約束條件中，根據(jù)變量α的離散特點(diǎn)，引入了一個(gè)有關(guān)于α的非線性等式約束來代替變量α的0-1離散限制，將原問題轉(zhuǎn)化為1個(gè)[0，1]區(qū)間上的等價(jià)非線性約束優(yōu)化問題.文獻(xiàn)[14]通過數(shù)學(xué)歸納法和反證法對兩個(gè)問題進(jìn)行了等價(jià)性證明.考慮到求解非線性約束優(yōu)化問題的困難，采用混合罰函數(shù)法進(jìn)行求解，根據(jù)罰函數(shù)的思想，建立新的定義域內(nèi)的無約束目標(biāo)函數(shù)

其中，r為G（A，r）的懲罰因子，通過牛頓法求解上面無約束問題;相當(dāng)于內(nèi)點(diǎn)罰函數(shù)的作用，能夠限制搜索點(diǎn)一直在不等式約束確定的區(qū)域;相當(dāng)于外點(diǎn)罰函數(shù)的作用，能夠迫使搜索點(diǎn)靠近等式約束.

步驟二：由于混合罰函數(shù)法得到的解違反了問題P3的最后一個(gè)約束條件，不是該問題的可行解，卸載決策變量還需要將其修正到{0，1}上.算法1為基于貪心算法的計(jì)算卸載算法.如算法1所示，首先定義MEC服務(wù)器剩余計(jì)算資源量為S，其初始值為最大計(jì)算資源S（行1）;其次利用混合罰函數(shù)法求解問題P3，經(jīng)過k次迭代后獲得的解為（行2）;然后通過不斷迭代將所有卸載決策變量進(jìn)行修正.在每次迭代過程中，不斷尋找A中最大卸載決策變量的任務(wù)i（行4），因?yàn)樾遁d決策變量越大，意味著第i個(gè)任務(wù)進(jìn)行卸載的可能性就越大.然后，將該任務(wù)的計(jì)算資源s與MEC服務(wù)器剩余計(jì)算資源量S進(jìn)行比較，若滿足計(jì)算容量限制，則將該任務(wù)卸載決策a置為1，同時(shí)更新MEC服務(wù)器剩余計(jì)算資源量，否則a置為0（行5—行10），當(dāng)完成決策變量a修正后，就將該變量從A中刪除（行11）.最后，不斷重復(fù)上述過程直到A中卸載變量全部修正完成，即A=0，則迭代結(jié)束，得到最終的任務(wù)決策變量A.

3.3聯(lián)合優(yōu)化策略總結(jié)

聯(lián)合計(jì)算卸載和資源分配策略通過相互迭代兩個(gè)子問題的解來獲得最佳卸載決策和資源分配. 算法2為聯(lián)合優(yōu)化算法.如算法2所示，初始化階段定義初始成本C以及最小誤差ε（行1），然后進(jìn)入迭代階段，每次迭代過程中都先通過拉格朗日乘子法求解資源分配子問題，獲得初始卸載決策A下的計(jì)算資源分配結(jié)果S，并且通過算法1求解計(jì)算卸載子問題，獲得卸載決策結(jié)果A（行3—行4）.根據(jù)公式（9）重新計(jì)算成本，若前后成本差值滿足誤差條件，將第t次迭代得到的卸載決策和資源分配向量作為最佳解，算法停止（行6—行10），否則保存成本（行11）進(jìn)入下次迭代.

用戶任務(wù)數(shù)目設(shè)置為N，該算法首先獲得計(jì)算資源分配需要經(jīng)過N次計(jì)算，計(jì)算復(fù)雜度為。（N），然后通過算法1獲得卸載決策，計(jì)算復(fù)雜度為O（KN+N），其中K是使混合罰函數(shù)算法達(dá)到收斂的迭代次數(shù)，最后經(jīng)過通過T次迭代獲得最佳卸載決策和最佳資源分配，算法的總計(jì)算復(fù)雜度為O（KNT+2NT），該算法相比傳統(tǒng)分支定界算法的計(jì)算復(fù)雜度更低.

4實(shí)驗(yàn)仿真和性能評估

本章采用Python語言進(jìn)行仿真實(shí)驗(yàn)，通過設(shè)置相應(yīng)仿真參數(shù)來評估本文所提算法的性能.

4.1實(shí)驗(yàn)設(shè)置

在仿真場景中，MEC服務(wù)器位于BS附近，網(wǎng)絡(luò)中有15到35個(gè)隨機(jī)分布的用戶移動(dòng)設(shè)備，BS覆蓋范圍為1 000m.設(shè)置系統(tǒng)帶寬B=20MHz，用戶傳輸帶寬W=1 MHz，因此K=20，通信參數(shù)遵循第三代合作伙伴計(jì)劃規(guī)范[15].設(shè)置無線信道增益模型為g=127+30×logd，其中d為用戶與MEC服務(wù)器之間的距離;高斯信道噪聲σ=2×10W;移動(dòng)設(shè)備CPU計(jì)算能力f=1 GHz/s;MEC服務(wù)器最大計(jì)算資源量S=20 GHz/s，移動(dòng)設(shè)備傳輸功率p=0.5 W，以及空閑狀態(tài)下功率p=0.1 W;用戶偏好參數(shù)為β=β=0.5.與文獻(xiàn)[16]工作類似，假設(shè)任務(wù)數(shù)據(jù)通過概率分布（即，正態(tài)分布和均勻分布）生成：任務(wù)數(shù)據(jù)大小B和計(jì)算資源量C由正態(tài)分布生成時(shí)，B^N（500，100）kB，C～N（1 000，100）megacycles;任務(wù)數(shù)據(jù)大小B和計(jì)算資源量C由均勻分布生成時(shí)，B～U（400，600）kB，C～U（800，1 200）megacycles.此外，初始用戶卸載集合為全部用戶，卸載決策集合A初始化為全1以及計(jì)算資源分配S初始化為全0.

仿真實(shí)驗(yàn)結(jié)果取100次實(shí)驗(yàn)的平均值，分別從移動(dòng)設(shè)備數(shù)目，任務(wù)計(jì)算資源量，MEC服務(wù)器計(jì)算資源量，用戶偏好參數(shù)幾個(gè)方面對本文所提算法進(jìn)行評估和分析.同時(shí)，將本文所提算法與本地執(zhí)行、全卸載算法、BB卸載算法以及帶漢明距離終止的動(dòng)態(tài)規(guī)劃（Dynamic Programming with HammingDistance Termination，DPH）卸載算法[17]進(jìn)行對比實(shí)驗(yàn).注意當(dāng)任務(wù)數(shù)超過BS容納的最大數(shù)量時(shí)，所有系統(tǒng)帶寬均已被占用，移動(dòng)用戶默認(rèn)選擇本地執(zhí)行其計(jì)算任務(wù)，MEC服務(wù)器中資源分配均由拉格朗日乘子法給出.

4.2性能評估

圖2顯示了移動(dòng)設(shè)備數(shù)量對系統(tǒng)成本（時(shí)延和能耗的加權(quán)和）的影響，移動(dòng)設(shè)備數(shù)量（N）從15增加到35.由圖2可以看到，所有算法成本均隨移動(dòng)設(shè)備數(shù)量的增加而增加，其中有兩條重疊的曲線，表明本文所提算法以及BB算法的系統(tǒng)成本幾乎相等，因此，本文所提算法可以收斂到由BB算法得出的最優(yōu)解，并且相比本地執(zhí)行算法、全卸載算法和DPH算法，本文所提算法的系統(tǒng)成本最低.在圖2（a）和圖2（b）中，本文所提算法相比本地執(zhí)行算法最高可以減少40%的系統(tǒng)成本.

圖3顯示了不同任務(wù)計(jì)算資源量對系統(tǒng)成本的影響，移動(dòng)設(shè)備數(shù)量設(shè)置為25.從仿真結(jié)果來看，隨著任務(wù)計(jì)算量的增加，算法系統(tǒng)成本也隨之增加.而且在所有算法中，本文所提算法的系統(tǒng)成本最低.在圖3（a）中，本文所提算法相比本地執(zhí)行算法可以減少40%的系統(tǒng)成本;與全卸載算法和DPH算法相比，本文所提算法可以減少10%的系統(tǒng)成本，從圖3（b）中也得到了同樣的結(jié)論.

為了分析MEC服務(wù)器計(jì)算資源量如何影響系統(tǒng)成本，在圖4中，移動(dòng)設(shè)備數(shù)量設(shè)置為25，通過改變服務(wù)器容量，對比各卸載算法的系統(tǒng)成本.從圖4（a）和4（b）中可以看出，當(dāng)MEC服務(wù)器計(jì)算資源量增加時(shí)，本地執(zhí)行算法的系統(tǒng)成本基本不變，這是因?yàn)槿蝿?wù)執(zhí)行只是消耗了用戶設(shè)備的計(jì)算資源，與MEC服務(wù)器無關(guān).對于其他算法，MEC服務(wù)器計(jì)算資源量越大，則分配給每個(gè)卸載任務(wù)的計(jì)算資源量就越多，系統(tǒng)成本自然降低.特別注意到，當(dāng)MEC服務(wù)器計(jì)算資源量小于14時(shí)，全卸載算法的系統(tǒng)成本最高，這是由于服務(wù)器計(jì)算資源受限，每個(gè)卸載任務(wù)分配到的計(jì)算資源較少，才導(dǎo)致高成本.反之，當(dāng)MEC服務(wù)器計(jì)算資源量大于25時(shí)，服務(wù)器計(jì)算資源充足，全卸載算法，DPH算法，BB算法以及所提算法的系統(tǒng)成本均緩慢降低，并且最終趨近一致.

圖5顯示了本文算法在不同時(shí)延偏好參數(shù)下任務(wù)平均時(shí)延和能耗，同時(shí)對比了移動(dòng)設(shè)備數(shù)量（N）為20和30的這兩種情況.設(shè)置任務(wù)數(shù)據(jù)大小和計(jì)算量都服從正態(tài)分布，時(shí)延偏好參數(shù)β從0.1變化到0.9，則能耗偏好參數(shù)為β=1-β，i=1，2，…，N.在時(shí)延偏好參數(shù)β增加的情況下，任務(wù)的平均時(shí)延降低，代價(jià)是消耗更多的能量.在N=30的情況下，用戶競爭計(jì)算資源導(dǎo)致任務(wù)卸載的可能性降低，因此，與N=20的情況相比，任務(wù)具有更高的平均延遲和能耗.

5結(jié)論

本文為降低多用戶MEC系統(tǒng)任務(wù)卸載的時(shí)延和能耗，提出了一個(gè)聯(lián)合計(jì)算卸載和資源分配策略. 優(yōu)化問題以最小化所有用戶計(jì)算時(shí)延和設(shè)備能耗的加權(quán)和為目標(biāo)，共同優(yōu)化了卸載決策和計(jì)算資源分配.優(yōu)化問題被拆分為資源分配子問題和計(jì)算卸載子問題，先通過拉格朗日乘子法求解資源分配子問題，然后提出一個(gè)基于貪心算法的計(jì)算卸載算法來求解計(jì)算卸載子問題，最后給出聯(lián)合優(yōu)化算法并證明其具有較低的計(jì)算復(fù)雜度.實(shí)驗(yàn)仿真驗(yàn)證了本文所提算法的有效性，該算法與其他基準(zhǔn)算法相比能實(shí)現(xiàn)更低的系統(tǒng)成本.在未來，這項(xiàng)工作將擴(kuò)展到多服務(wù)器的移動(dòng)邊緣系統(tǒng)中，并考慮用戶設(shè)備功率、信道干擾等因素的影響.

[參考文獻(xiàn)]

[1]GOHIL A，MODI H，PATEL S K. 5G technology of mobile communication：A survey [C]// 2013 International Conference on Intelligent Systems and Signal Processing （ISSP）. IEEE，2013：288-292.

[2]MACH P，BECVAR Z. Mobile edge computing：A survey on architecture and computation offloading [J]. IEEE Communications Surveys and Tutorials，2017，19（3）：1628-1656.

[3]HU Y C，PATEL M，SABELLA D，et al. Mobile Edge Computing：A Key Technology Towards 5G [M]. [S.I.]：ETSI （European Telecommunications Standards Institute），2015.

[4]ZHANG D Y，TANG J Z，DU W T，et al. Joint optimization of computation offloading and UL/DL resource allocation in MEC systems [C]// 2018 IEEE 29th Annual International Symposium on Personal，Indoor and Mobile Radio Communications （PIMRC）. IEEE，2018：6 pages. DOI：10.1109/PIMRC.2018.8580841.

[5]ALAM M G R，HASSAN M M，UDDIN M Z，et al. Autonomie computation offloading in mobile edge for loT applications [J]. Future Generation Computer Systems，2019，90：149-157.

[6]PAYMARD P，REZVANI S，MOKARI N. Joint task scheduling and uplink/downlink radio resource allocation in PD-NOMA basedmobile edge computing networks [J]. Physical Communication，2019，32：160-171.

[7]LIU J H，ZHANG Q. Computation resource allocation for heterogeneous time-critical loT services in MEC [EB/OL]. （2020-02- 12）[2020-05-30]. https：//arxiv.org/abs/2002.04851.

[8]GUO F X，ZHANG H L，JI H，et al. Energy efficient computation offloading for multi-access MEC enabled small cell networks [C]// 2018 IEEE International Conference on Communications Workshops （ICC Workshops）. IEEE，2018：6 pages. DOI：10.1109/ICCW. 2018.8403701.

[9]LI C L，TANG J H，ZHANG Y，et al. Energy efficient computation offloading for nonorthogonal multiple access assisted mobile edge computing with energy harvesting devices [J]. Computer Networks，2019，164：106890.

[10]QIAN L P，ZHU Z Y，YU N N，et al. Joint minimization of transmission energy and computation energy for MEC-aware NOMA NB-IoT networks [C]// 2019 IEEE Global Communications Conference （GLOBECOM）. IEEE，2019：7 pages. DOI：10.1109/ GLOBECOM38437.2019.9013350.

[11]ZENG M，F(xiàn)ODOR V. Energy minimization for delay constrained mobile edge computing with orthogonal and non-orthogonal multiple access [J]. Ad Hoc Networks，2020，98：102060.

[12]LI J，GAO H，LYU T J，et al. Deep reinforcement learning based computation offloading and resource allocation for MEC [C]// 2018 IEEE Wireless Communications and Networking Conference （WCNC）. IEEE，2018：6 pages. DOI：10.1109/WCNC.2018.8377343.

[13]HUANG C M，CHIANG M S，DAO D T，et al. V2V data offloading for cellular network based on the software defined network （SDN）inside mobile edge computing （MEC）architecture [J]. IEEE Access，2018（6）：17741-17755.

[14]隋允康，賈志超.0-1線性規(guī)劃的連續(xù)化及其遺傳算法解法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2010，40（6）：119-127.

[15]3GPP Technical Specification Group Radio Access Network. Further advancements for E-UTRA physical layer aspects（Release 9）[R]. 3GPP TS 36.814 V9.0.0，2010.

[16]CHEN M，HAO Y X. Task offloading for mobile edge computing in software defined ultra-dense network [J]. IEEE Journal on Selected Areas in Communications，2018，36（3）：587-597.

[17]SHAHZAD H，SZYMANSKI T H. A dynamic programming offloading algorithm for mobile cloud computing [C]// 2016 IEEE 9th International Conference on Cloud Computing （CLOUD）. IEEE，2016：960-965.

（責(zé)任編輯：李藝）