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

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

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

中圖分類號：TP391文獻標志碼：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引言

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

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

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

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

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

本文主要貢獻概述如下.

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

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

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

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

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

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

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

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

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

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

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

1.2計算模型

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

（1）本地計算

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

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

E=εC，（4）

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

（2）移動邊緣計算

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

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

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

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

2問題描述

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

C=βT+βE（7）

C=βT+βE（8）

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

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

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

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

3計算卸載和資源分配策略

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

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

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

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

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

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

通過KKT條件，有

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

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

3.2基于貪心算法的計算卸載算法

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

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

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

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

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

步驟二：由于混合罰函數(shù)法得到的解違反了問題P3的最后一個約束條件，不是該問題的可行解，卸載決策變量還需要將其修正到{0，1}上.算法1為基于貪心算法的計算卸載算法.如算法1所示，首先定義MEC服務(wù)器剩余計算資源量為S，其初始值為最大計算資源S（行1）;其次利用混合罰函數(shù)法求解問題P3，經(jīng)過k次迭代后獲得的解為（行2）;然后通過不斷迭代將所有卸載決策變量進行修正.在每次迭代過程中，不斷尋找A中最大卸載決策變量的任務(wù)i（行4），因為卸載決策變量越大，意味著第i個任務(wù)進行卸載的可能性就越大.然后，將該任務(wù)的計算資源s與MEC服務(wù)器剩余計算資源量S進行比較，若滿足計算容量限制，則將該任務(wù)卸載決策a置為1，同時更新MEC服務(wù)器剩余計算資源量，否則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)合計算卸載和資源分配策略通過相互迭代兩個子問題的解來獲得最佳卸載決策和資源分配. 算法2為聯(lián)合優(yōu)化算法.如算法2所示，初始化階段定義初始成本C以及最小誤差ε（行1），然后進入迭代階段，每次迭代過程中都先通過拉格朗日乘子法求解資源分配子問題，獲得初始卸載決策A下的計算資源分配結(jié)果S，并且通過算法1求解計算卸載子問題，獲得卸載決策結(jié)果A（行3—行4）.根據(jù)公式（9）重新計算成本，若前后成本差值滿足誤差條件，將第t次迭代得到的卸載決策和資源分配向量作為最佳解，算法停止（行6—行10），否則保存成本（行11）進入下次迭代.

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

4實驗仿真和性能評估

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

4.1實驗設(shè)置

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

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

4.2性能評估

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

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

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

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

5結(jié)論

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

[參考文獻]

[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é)的實踐與認識，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é)任編輯：李藝）