柏建雄 魏佳隆 孟曉磊 劉揚(yáng) 趙振

摘? 要：在多用戶(hù)多邊緣服務(wù)器的邊緣計(jì)算場(chǎng)景下，用戶(hù)設(shè)備在任務(wù)卸載時(shí)，由于卸載目標(biāo)的不確定性常導(dǎo)致移動(dòng)邊緣服務(wù)器負(fù)載不均衡，出現(xiàn)資源緊張或資源空閑浪費(fèi)問(wèn)題，甚至導(dǎo)致卸載決策失效。針對(duì)此問(wèn)題，提出了面向時(shí)延和能耗感知的啟發(fā)式任務(wù)多邊協(xié)同卸載（HTMC）算法，并在算法中提出了一種基于粒子近期歷史位置的位置更新策略（PRPPUS）。該算法以最小化UE能耗和任務(wù)執(zhí)行時(shí)延的加權(quán)和為目標(biāo)，根據(jù)時(shí)延和能耗感知自適應(yīng)地選擇任務(wù)卸載策略，達(dá)到最小化UE開(kāi)銷(xiāo)目標(biāo)。仿真實(shí)驗(yàn)結(jié)果證明，與采用粒子群算法和遺傳算法的卸載策略比較，所提HTMC算法的性能更高、更平穩(wěn)，算法運(yùn)行開(kāi)銷(xiāo)較小，優(yōu)化效果更突出。

關(guān)鍵詞：移動(dòng)邊緣計(jì)算；計(jì)算卸載；邊云協(xié)同；邊邊協(xié)同；粒子群優(yōu)化算法

中圖分類(lèi)號(hào)：TN929.5；TP393? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2023）18-0011-09

Multi-user and Multilateral Cooperative Offloading Strategies in Mobile Edge Computing

BAI Jianxiong， WEI Jialong， MENG Xiaolei， LIU Yang， ZHAO Zhen

（School of Information Science and Technology， Qingdao University of Science and Technology， Qingdao? 266061， China）

Abstract： In the multi-user and multi-edge server edge computing scenario， the uncertainty of the offload target of User Equipment （UE） often leads to an unbalanced load on Mobile Edge Computing Server （MECS）， resource constraint or idle waste， and even leads to the offload decision fails. To address this problem， a delay and energy-aware Heuristic Task Multilateral Co-Offloading （HTMC） algorithm is proposed， and a Particle Recent Past-based Position Updating Strategy （PRPPUS） is proposed in the algorithm. The algorithm aims to minimize the weighted sum of UE energy consumption and task execution delay， and adaptively selects the task offloading strategy according to the delay and energy awareness to minimize UE overhead. The simulation experimental results prove that the proposed HTMC algorithm has higher and smoother performance， smaller algorithm running overhead， and more outstanding optimization effects compared with the offloading strategies using the Particle Swarm Optimization algorithm and Genetic Algorithm.

Keywords： mobile edge computing; compute offload; edge-cloud collaboration; edge-edge collaboration; Particle Swarm Optimization algorithm

0? 引? 言

近年來(lái)，深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Networks， DNN）在計(jì)算機(jī)視覺(jué)、模式識(shí)別等領(lǐng)域取得諸多成果，并且在人們的日常生活中被廣泛應(yīng)用，自1994年LeNet5[1]（5層）網(wǎng)絡(luò)提出以來(lái)，DNN的網(wǎng)絡(luò)結(jié)構(gòu)變得更復(fù)雜，其推理精度也獲得大幅提升，如ResNet[2]（152層），同時(shí)DNN模型計(jì)算需要的參數(shù)規(guī)模和推理計(jì)算量也急劇性增長(zhǎng)，導(dǎo)致DNN在訓(xùn)練和推理時(shí)需要更多的資源支撐。雖然新一代移動(dòng)用戶(hù)設(shè)備（User Equipment， UE）擁有更強(qiáng)大的計(jì)算能力，但仍不能支撐這些密集型低時(shí)延要求的新型應(yīng)用。因此在大多數(shù)UE上的人工智能（Artificial Intelligence， AI）應(yīng)用及服務(wù)需要將DNN的輸入數(shù)據(jù)傳輸?shù)皆浦行?，由云中心服?wù)器（Cloud Computing Server， CCS）執(zhí)行模型推理操作，最終將結(jié)果回傳至UE。但移動(dòng)云計(jì)算（Mobile Cloud Computing， MCC）模式存在以下問(wèn)題：

1）傳輸開(kāi)銷(xiāo)大，在移動(dòng)計(jì)算和物聯(lián)網(wǎng)進(jìn)步的推動(dòng)下，UE和物聯(lián)網(wǎng)設(shè)備數(shù)量爆發(fā)式增長(zhǎng)，并在邊緣側(cè)生成數(shù)以?xún)|計(jì)的數(shù)據(jù)字節(jié)，這些數(shù)據(jù)傳輸將帶來(lái)巨大網(wǎng)絡(luò)開(kāi)銷(xiāo)。

2）網(wǎng)絡(luò)依賴(lài)性強(qiáng)，當(dāng)UE處于低帶寬的無(wú)線(xiàn)網(wǎng)絡(luò)環(huán)境時(shí)，由于云中心模式依賴(lài)網(wǎng)絡(luò)實(shí)現(xiàn)數(shù)據(jù)傳輸，在這種場(chǎng)景下網(wǎng)絡(luò)存在嚴(yán)重的延遲和抖動(dòng)問(wèn)題，無(wú)法保證提供可靠的服務(wù)。

3）云中心開(kāi)銷(xiāo)過(guò)大，由于云中心需要接收UE采集的各種數(shù)據(jù)，并且大部分?jǐn)?shù)據(jù)沒(méi)有進(jìn)行預(yù)篩選操作，以行人檢測(cè)場(chǎng)景的圖像數(shù)據(jù)為例，由于大量的采集圖像在UE端產(chǎn)生，且大部分圖像數(shù)據(jù)中不包括行人目標(biāo)，然而云中心仍需要接收、存儲(chǔ)并推理這些數(shù)據(jù)，這給CCS帶來(lái)額外的計(jì)算和存儲(chǔ)開(kāi)銷(xiāo)。

4）隱私泄露，隨著AI應(yīng)用深入人們生活，邊緣終端采集信息中包含大量用戶(hù)隱私數(shù)據(jù)，例如智能家居的室內(nèi)監(jiān)控應(yīng)用、工廠(chǎng)的產(chǎn)品缺陷檢測(cè)數(shù)據(jù)等。所有數(shù)據(jù)統(tǒng)一上傳CCS進(jìn)行處理，在傳輸和存儲(chǔ)過(guò)程中增加了隱私數(shù)據(jù)泄露的風(fēng)險(xiǎn)。

AI應(yīng)用及服務(wù)的低時(shí)延高精度的需求對(duì)傳統(tǒng)云中心模式提出了巨大挑戰(zhàn)，云中心模式已經(jīng)無(wú)法滿(mǎn)足邊緣側(cè)密集型任務(wù)的需求，而將云端的計(jì)算、存儲(chǔ)能力下沉至邊緣成為大勢(shì)所趨，于是移動(dòng)邊緣計(jì)算（Mobile Edge Computing， MEC）[3]應(yīng)運(yùn)而生。對(duì)于DNN而言，MEC在靠近數(shù)據(jù)生產(chǎn)源頭的用戶(hù)設(shè)備上部署DNN模型，由邊緣側(cè)服務(wù)器直接提供推理能力，無(wú)須將大量數(shù)據(jù)傳輸至云中心進(jìn)行推理操作。將模型的推理過(guò)程由云中心下沉到靠近用戶(hù)的邊緣側(cè)，在減少傳輸時(shí)延的同時(shí)，加強(qiáng)了用戶(hù)隱私數(shù)據(jù)保護(hù)，避免了網(wǎng)絡(luò)波動(dòng)的影響，提高了DNN服務(wù)應(yīng)用的響應(yīng)時(shí)間。雖然使用MEC減少了數(shù)據(jù)上云的傳輸延遲，但是邊緣側(cè)由于硬件資源限制，單一節(jié)點(diǎn)往往無(wú)法支撐起DNN等計(jì)算密集型應(yīng)用對(duì)存儲(chǔ)、計(jì)算資源的需求，如何有效地分配邊緣服務(wù)器資源，充分調(diào)度邊緣服務(wù)器的計(jì)算能力進(jìn)行模型推理仍然是一個(gè)充滿(mǎn)挑戰(zhàn)的問(wèn)題。

與MCC相比，MEC增加了邊緣計(jì)算層，提供了減少核心網(wǎng)絡(luò)擁堵導(dǎo)致的延遲問(wèn)題的機(jī)會(huì)[4]。計(jì)算卸載將任務(wù)調(diào)度至靠近用戶(hù)側(cè)的MECS上執(zhí)行，承擔(dān)了一部分云服務(wù)器的負(fù)載，減少了數(shù)據(jù)發(fā)送至云服務(wù)器的傳輸量，避免了網(wǎng)絡(luò)擁堵造成的時(shí)延問(wèn)題。計(jì)算卸載技術(shù)[5]是MEC中的一個(gè)關(guān)鍵點(diǎn)，其中，時(shí)延和能耗是任務(wù)卸載的主要指標(biāo)，大量研究針對(duì)降低時(shí)延、能耗為優(yōu)化目標(biāo)研究計(jì)算卸載策略。文獻(xiàn)[6]針對(duì)資源有限的單用戶(hù)計(jì)算場(chǎng)景下，考慮任務(wù)計(jì)算時(shí)延設(shè)計(jì)了一種一維搜索算法實(shí)現(xiàn)的計(jì)算卸載決策方案。文獻(xiàn)[7]以計(jì)算時(shí)延為優(yōu)化目標(biāo)，提出了一種低復(fù)雜度的基于Lyapunov優(yōu)化的動(dòng)態(tài)計(jì)算卸載算法，并減少了任務(wù)失敗率。文獻(xiàn)[8]考慮在電池供電的UE設(shè)備場(chǎng)景中，提出了一種基于A(yíng)DMM聯(lián)合優(yōu)化算法，聯(lián)合優(yōu)化了任務(wù)計(jì)算模式和系統(tǒng)時(shí)間分配。文獻(xiàn)[9]在滿(mǎn)足時(shí)延約束下，以最小化能耗為優(yōu)化目標(biāo)，提出基于粒子群優(yōu)化算法的能耗最小化約束任務(wù)卸載策略。文獻(xiàn)[10]在小型網(wǎng)絡(luò)的計(jì)算卸載場(chǎng)景，提出一種基于遺傳算法和粒子群算法的HGPCA算法，通過(guò)聯(lián)合設(shè)備功率、計(jì)算資源和網(wǎng)絡(luò)資源等因子，計(jì)算最小化能耗的任務(wù)卸載策略。文獻(xiàn)[11]考慮單用戶(hù)多任務(wù)場(chǎng)景，提出多任務(wù)協(xié)同計(jì)算卸載模型，并采用非線(xiàn)性慣性因子的粒子群算法優(yōu)化粒子群全局搜索能力。文獻(xiàn)[12]針對(duì)多用戶(hù)計(jì)算卸載場(chǎng)景，并以最小化多用戶(hù)的能耗和時(shí)延為目標(biāo)，提出了SDR-AO-ST算法，但僅考慮了單MECS的場(chǎng)景，并且沒(méi)有考慮每個(gè)UE多個(gè)任務(wù)之間的依賴(lài)性。文獻(xiàn)[13]針對(duì)超密集組網(wǎng)場(chǎng)景下，提出了基于匈牙利算法的任務(wù)分配策略，在滿(mǎn)足時(shí)延約束下最小化系統(tǒng)總能耗。文獻(xiàn)[14]在考慮卸載策略、計(jì)算資源、傳輸速率和功率分配的情況下，提出基于流水線(xiàn)的時(shí)延優(yōu)化卸載算法。

在大規(guī)模邊緣計(jì)算模型中，UE端產(chǎn)生的任務(wù)通常具有強(qiáng)依賴(lài)性。文獻(xiàn)[15]針對(duì)多用戶(hù)場(chǎng)景中子任務(wù)的強(qiáng)依賴(lài)性，通過(guò)引入一個(gè)新的因子來(lái)確定并行子任務(wù)的處理順序，提出了一種啟發(fā)式算法，對(duì)延遲和能量進(jìn)行聯(lián)合優(yōu)化。文獻(xiàn)[16]針對(duì)工業(yè)4.0領(lǐng)域中的邊緣計(jì)算模型，以?xún)?yōu)化時(shí)延和能耗為目標(biāo)，提出一種面向多任務(wù)依賴(lài)的計(jì)算卸載（ET-DTCO）算法。文獻(xiàn)[17]提出了一種基于遺傳算法的多群體協(xié)同優(yōu)化算法（MCE-GA），解決MEC中多任務(wù)依賴(lài)的卸載問(wèn)題，最大限度地減少任務(wù)執(zhí)行時(shí)延和能耗。

隨著高速率、低時(shí)延的新一代寬帶移動(dòng)通信技術(shù)的發(fā)展，MEC得到了極大的推廣應(yīng)用，僅考慮任務(wù)時(shí)延和能耗最小化優(yōu)化已經(jīng)不能滿(mǎn)足密集型的新型應(yīng)用需求。文獻(xiàn)[18]通過(guò)聯(lián)合網(wǎng)絡(luò)各方資源，動(dòng)態(tài)權(quán)衡時(shí)延和能耗，在有限的能源和時(shí)延要求下構(gòu)建大規(guī)模且低成本的邊緣計(jì)算網(wǎng)絡(luò)。文獻(xiàn)[19]利用軟件定義網(wǎng)絡(luò)（Software Defined Network， SDN）思想，將計(jì)算卸載問(wèn)題抽象為任務(wù)放置子問(wèn)題和資源分配子問(wèn)題，以最小化時(shí)延為優(yōu)化目標(biāo)。文獻(xiàn)[20]針對(duì)多MECS場(chǎng)景，在能耗約束條件下提出一種基于粒子群優(yōu)化的卸載算法，計(jì)算最小化時(shí)延的卸載策略，并通過(guò)懲罰函數(shù)保持能耗和時(shí)延的平衡，但只考慮了MECS，沒(méi)有關(guān)注MECS與CCS相結(jié)合的場(chǎng)景。文獻(xiàn)[21]考慮UE的CPU利用率和內(nèi)存利用率的動(dòng)態(tài)權(quán)衡，根據(jù)UE的響應(yīng)時(shí)間和能耗建立計(jì)算卸載模型，提出一種在多用戶(hù)邊緣計(jì)算環(huán)境中基于變異算子的粒子群優(yōu)化的動(dòng)態(tài)計(jì)算卸載算法，降低了卸載成本和UE能耗，并提高了任務(wù)卸載成功率。

綜上所述，大部分研究?jī)H以時(shí)延約束或能耗約束作為優(yōu)化目標(biāo)，沒(méi)有考慮任務(wù)之間的依賴(lài)性，而在UE端產(chǎn)生的任務(wù)往往具有依賴(lài)性，任務(wù)無(wú)序卸載會(huì)造成服務(wù)器資源的浪費(fèi)，甚至導(dǎo)致任務(wù)執(zhí)行失敗。并且大多研究忽略了邊與邊之間的協(xié)作，只針對(duì)UE與MECS之間的任務(wù)卸載進(jìn)行研究，而由于UE任務(wù)卸載時(shí)具有不確定性，導(dǎo)致MECS負(fù)載不均衡，出現(xiàn)資源緊張或資源浪費(fèi)的情況。本文考慮上述研究的局限性，將移動(dòng)邊緣服務(wù)器（Mobile Edge Computing Server， MECS）與異地MECS抽象成一個(gè)任務(wù)協(xié)同卸載整體，并以最小化任務(wù)執(zhí)行總時(shí)延和總能耗為目標(biāo)，設(shè)計(jì)移動(dòng)邊緣計(jì)算場(chǎng)景中多用戶(hù)多任務(wù)的計(jì)算卸載模型，提出了面向時(shí)延和能耗感知的啟發(fā)式任務(wù)多邊協(xié)同卸載（Heuristic Task Multilateral Co-Offloading， HTMC）算法，在滿(mǎn)足任務(wù)依賴(lài)約束的前提下，綜合考慮了UE能耗和任務(wù)執(zhí)行時(shí)延，根據(jù)時(shí)延和能耗感知自適應(yīng)地選擇任務(wù)卸載策略，達(dá)到最小化UE開(kāi)銷(xiāo)目標(biāo)。本文主要貢獻(xiàn)：

1）構(gòu)建了任務(wù)多邊卸載開(kāi)銷(xiāo)優(yōu)化模型，量化UE執(zhí)行的能耗和任務(wù)執(zhí)行時(shí)延開(kāi)銷(xiāo)，并以最小化UE能耗和任務(wù)執(zhí)行時(shí)延為優(yōu)化目標(biāo)，實(shí)現(xiàn)了多用戶(hù)多任務(wù)邊緣計(jì)算場(chǎng)景下的有效任務(wù)多邊卸載調(diào)度。

2）針對(duì)粒子群易陷入局部最優(yōu)問(wèn)題，提出了一種基于粒子近期歷史的位置更新策略，同時(shí)利用了分級(jí)交叉突變運(yùn)算增加樣本豐富度，并驗(yàn)證了算法的收斂效率和準(zhǔn)確性。

1? 系統(tǒng)模型

多邊協(xié)同的邊緣計(jì)算架構(gòu)模型可分為三層，分別是用戶(hù)層、邊緣層和云層，如圖1所示。用戶(hù)層可以根據(jù)計(jì)算任務(wù)與自身設(shè)備的計(jì)算能力的匹配度選擇是否在本地執(zhí)行，或者選擇將任務(wù)卸載至邊緣層或云層執(zhí)行。邊緣層由靠近用戶(hù)的具有一定計(jì)算能力的MECS和異地的邊緣服務(wù)器群組成，可以接收用戶(hù)層卸載的任務(wù)并執(zhí)行。云層由高性能的服務(wù)器組成，具有遠(yuǎn)大于MECS的存儲(chǔ)能力和計(jì)算能力，并提供協(xié)同管理邊緣層計(jì)算資源的能力。

本文假設(shè)系統(tǒng)由u個(gè)UE、m個(gè)MECS以及1個(gè)CCS組成，UE中總共有n個(gè)任務(wù)需要執(zhí)行，任務(wù)可以在UE、MECS、異地MECS以及CSS執(zhí)行。任務(wù)卸載決策有三種方案，分別為：

1）本地執(zhí)行：計(jì)算任務(wù)在用戶(hù)本地設(shè)備上執(zhí)行。

2）邊緣服務(wù)器執(zhí)行：UE通過(guò)無(wú)線(xiàn)網(wǎng)絡(luò)將任務(wù)卸載至MECS或異地MECS執(zhí)行。

3）云中心服務(wù)器執(zhí)行：UE通過(guò)基站網(wǎng)絡(luò)將任務(wù)傳輸至CCS執(zhí)行。

1.1? 通信模型

邊緣服務(wù)器部署在無(wú)線(xiàn)接入網(wǎng)（Radio Access Network， RAN）側(cè)，UE產(chǎn)生的任務(wù)經(jīng)周邊基站接收后，被轉(zhuǎn)發(fā)至MECS。網(wǎng)絡(luò)傳輸信道的傳輸速率根據(jù)香農(nóng)公式計(jì)算可得，香農(nóng)[22]提出了在高斯白噪聲干擾下的信道中，數(shù)據(jù)傳輸最高峰值速率為：

式中，W表示信道帶寬；S表示信道內(nèi)信號(hào)的有效功率；N表示信道內(nèi)高斯噪音功率。

信噪比可以由當(dāng)前設(shè)備信道內(nèi)噪聲、其他設(shè)備功率、其他設(shè)備與當(dāng)前信號(hào)接收方之間信道增益計(jì)算得出[23]，其信噪比算式為：

信道增益Hij又可由信道長(zhǎng)度dij計(jì)算得出[24]，信道增益計(jì)算式為：

將式（2）、（3）帶入式（1），得到數(shù)據(jù)傳輸速率為：

式中，Pi表示設(shè)備i的信號(hào)發(fā)送功率；Hij表示發(fā)送方設(shè)備i與接收方設(shè)備j之間的信道增益； 是設(shè)備u與接收方設(shè)備j之間的信號(hào)發(fā)射功率和信道增益的乘積，表示其他設(shè)備向接收方設(shè)備j的信號(hào)發(fā)送對(duì)發(fā)送方設(shè)備i與接收方設(shè)備j之間通信造成的信道干擾；dij表示發(fā)送方設(shè)備i與接收方設(shè)備j之間的歐式距離；α表示路徑損失因子。

由此可知，當(dāng)W、Pi、Pu、N0確定時(shí)，傳輸速率僅受數(shù)據(jù)發(fā)送方和數(shù)據(jù)接收方之間的距離影響。當(dāng)其干擾信號(hào)源與數(shù)據(jù)接收方之間的距離較遠(yuǎn)時(shí)，即duj→∞，此時(shí)有：

本文假設(shè)其他設(shè)備的干擾忽略不計(jì)，則信號(hào)發(fā)送方設(shè)備i與信號(hào)接收設(shè)備j的傳輸速率為：

1.2? 計(jì)算卸載模型

邊緣計(jì)算的任務(wù)卸載過(guò)程主要分為任務(wù)卸載的傳輸過(guò)程、任務(wù)的執(zhí)行過(guò)程，從最小化時(shí)延和能耗的目標(biāo)角度上看，任務(wù)卸載過(guò)程可以從五個(gè)部分進(jìn)行建模，分別為任務(wù)傳輸時(shí)延、任務(wù)傳輸能耗、任務(wù)卸載執(zhí)行時(shí)延、任務(wù)本地執(zhí)行時(shí)延和任務(wù)本地執(zhí)行能耗。

假設(shè)所有的MECS的計(jì)算能力相同，則UE、MECS和CCS的計(jì)算能力分別為Fl、Fe、Fc；UE、MECS和CCS計(jì)算1 bit數(shù)據(jù)所需CPU周期分別為fl、fe、fc；UE、MECS和CCS執(zhí)行任務(wù)時(shí)的功率分別為Pl、Pe、Pc。將n個(gè)任務(wù)集合建模為T(mén) = {T1，T2，…，Tn}，則第i個(gè)任務(wù)建模為T(mén)i = {ui，ci，di}。ui表示任務(wù)Ti的輸入數(shù)據(jù)量，即任務(wù)卸載時(shí)的網(wǎng)絡(luò)傳輸數(shù)據(jù)量，ci表示任務(wù)Ti在計(jì)算過(guò)程中的總數(shù)據(jù)量，di表示任務(wù)Ti執(zhí)行后反饋結(jié)果的數(shù)據(jù)量，即任務(wù)結(jié)果傳回UE的網(wǎng)絡(luò)傳輸數(shù)據(jù)量。

UE產(chǎn)生的多任務(wù)往往具有依賴(lài)關(guān)系，使用有向無(wú)環(huán)圖（Direct Acyclic Graph， DAG）表示多任務(wù)之間的依賴(lài)關(guān)系。

1）當(dāng)任務(wù)在本地執(zhí)行時(shí)，任務(wù)Ti的計(jì)算時(shí)延為：

任務(wù)Ti在UE本地執(zhí)行能耗為：

2）任務(wù)卸載至邊緣服務(wù)器執(zhí)行時(shí)，根據(jù)文獻(xiàn)[25]，數(shù)據(jù)上行和下行分別具有不同的信號(hào)頻率，由香農(nóng)公式可得出UE上行數(shù)據(jù)和下行數(shù)據(jù)的傳輸速率為：

式中， 和? 分別表示UE與MECS之間上行數(shù)據(jù)和下行數(shù)據(jù)的信道帶寬， 和? 分別表示UE和MECS的數(shù)據(jù)發(fā)送功率。 表示UE和MECS之間數(shù)據(jù)傳輸?shù)穆窂綋p耗， 則表示UE和MECS之間的距離。

任務(wù)Ti卸載至靠近UE的MECS時(shí)，任務(wù)傳輸時(shí)延包括UE將任務(wù)卸載至邊緣服務(wù)器的時(shí)延以及任務(wù)在MECS執(zhí)行完將執(zhí)行結(jié)果回傳至UE的時(shí)延，時(shí)延傳輸時(shí)延為：

UE在任務(wù)傳輸過(guò)程中產(chǎn)生的能耗為：

任務(wù)Ti在MECS執(zhí)行所產(chǎn)生的時(shí)延為：

將任務(wù)卸載至MECS時(shí)，當(dāng)靠近UE的MECS負(fù)載過(guò)高時(shí)，任務(wù)將由當(dāng)前服務(wù)器卸載至異地MECS執(zhí)行。MECS之間上行數(shù)據(jù)和下行數(shù)據(jù)的傳輸速率為：

式中， 和? 表示MECS之間上行數(shù)據(jù)和下行數(shù)據(jù)的信道帶寬； 和? 分別表示MECS和異地MECS的數(shù)據(jù)發(fā)送功率； 表示MECS和異地MECS之間數(shù)據(jù)傳輸?shù)穆窂綋p耗； 則表示MECS和異地MECS之間的距離。

任務(wù)Ti從當(dāng)前MECS卸載到異地MECS執(zhí)行產(chǎn)生的傳輸時(shí)延為：

本文假設(shè)所有MECS具有統(tǒng)一的計(jì)算能力，任務(wù)Ti在異地MECS執(zhí)行的時(shí)延為 。在移動(dòng)邊緣計(jì)算體系中任務(wù)卸載時(shí)主要考慮用戶(hù)側(cè)的任務(wù)執(zhí)行能耗，因MECS采用電網(wǎng)供電方式，故任務(wù)在MECS執(zhí)行所產(chǎn)生的能耗將不被記入任務(wù)執(zhí)行總能耗中。

3）任務(wù)卸載至CCS執(zhí)行時(shí)，UE終端將任務(wù)卸載至CCS執(zhí)行，并需要將任務(wù)執(zhí)行結(jié)果回傳至UE終端，UE與CCS之間上行數(shù)據(jù)和下行數(shù)據(jù)的傳輸速率為：

式中， 和? 表示UE與CCS之間上行數(shù)據(jù)和下行數(shù)據(jù)的信道帶寬， 和? 分別表示UE與CCS的數(shù)據(jù)發(fā)送功率。 表示UE與CCS之間數(shù)據(jù)傳輸?shù)穆窂綋p耗， 則表示UE與CCS之間的距離。

任務(wù)Ti卸載至CCS執(zhí)行時(shí)，任務(wù)傳輸總時(shí)延為：

任務(wù)Ti卸載至CCS執(zhí)行時(shí)，任務(wù)傳輸總能耗為：

任務(wù)Ti在CCS執(zhí)行時(shí)延為：

在移動(dòng)邊緣計(jì)算體系中任務(wù)卸載時(shí)主要考慮用戶(hù)設(shè)備終端側(cè)的任務(wù)執(zhí)行能耗，因CCS采用電網(wǎng)供電方式，故任務(wù)在CCS執(zhí)行所產(chǎn)生的能耗將不被記入任務(wù)執(zhí)行總能耗中。

UE所有任務(wù)執(zhí)行的總時(shí)延為：

UE所有任務(wù)執(zhí)行總能耗為：

2? HTMC算法設(shè)計(jì)

2.1? 粒子編碼方式

本文采用整數(shù)編碼，每一個(gè)粒子代表一種在多邊邊緣計(jì)算場(chǎng)景下的卸載策略，粒子位置取值范圍為0～3。假設(shè)用戶(hù)設(shè)備終端共產(chǎn)生n個(gè)任務(wù)，粒子i的位置向量表示為Xi = {1，2，11，0，…，3，1，2}，則該粒子卸載策略如圖2所示，0表示任務(wù)在UE上執(zhí)行，1表示任務(wù)卸載至MECS上執(zhí)行，2表示任務(wù)卸載至異地MECS上執(zhí)行，3表示任務(wù)卸載至CCS上執(zhí)行。

2.2? 解法模型

為了解決時(shí)延和能耗多目標(biāo)優(yōu)化問(wèn)題，本文是以線(xiàn)性加權(quán)法，通過(guò)引入時(shí)延與能耗權(quán)重系數(shù)調(diào)節(jié)在不同邊緣計(jì)算場(chǎng)景下對(duì)時(shí)延、能耗的不同要求。因此，該問(wèn)題的特征函數(shù)定義為：

式中，Xi表示任務(wù)卸載方案，且ω1 + ω2 = 1。對(duì)于優(yōu)化目標(biāo)的時(shí)延與能耗權(quán)重系數(shù)，可以根據(jù)用戶(hù)偏好進(jìn)行調(diào)節(jié)，較重要的優(yōu)化目標(biāo)設(shè)置較大權(quán)重系數(shù)值。如在用戶(hù)設(shè)備終端時(shí)延目標(biāo)優(yōu)先的任務(wù)場(chǎng)景下，可以增加時(shí)延目標(biāo)的權(quán)重系數(shù)ω1，能耗目標(biāo)的權(quán)重系數(shù)ω2會(huì)相應(yīng)地變小。

2.3? HTMC算法結(jié)構(gòu)

2.3.1? 基于近期歷史位置的位置更新策略

針對(duì)粒子群算法[26]在執(zhí)行過(guò)程中容易陷入局部最優(yōu)問(wèn)題，本文提出了一種PRPPUS（Particle Recent Past-based Position Updating Strategy）機(jī)制，用于改進(jìn)PSO算法。該機(jī)制是Askari[27]在2020年提出政治優(yōu)化器（Political Optimizer， PO）中的重要組成部分，利用歷史信息加速收斂，并避免陷入局部最優(yōu)。

本文HTMC算法使用式（26）～（27）更新粒子的位置信息，依據(jù)粒子當(dāng)前適應(yīng)值 、近期適應(yīng)值? 選擇式（27）或式（28）執(zhí)行。然后，依據(jù)粒子當(dāng)前位置 、全局最優(yōu)粒子矢量位置X *和范圍在[0，1]的隨機(jī)因子r進(jìn)行矢量計(jì)算。RPPUS計(jì)算表示如圖3所示，陰影部分表示最優(yōu)解區(qū)域。當(dāng)適應(yīng)度提高時(shí)，選擇式（27）計(jì)算粒子第p維度的位置，分三種情況討論。

1）當(dāng)前位置? 位于參考值? 和上次途經(jīng)位置? 之間時(shí)，最優(yōu)解范圍 ，如圖3（a）所示；

2）參考值? 位于當(dāng)前位置? 和上次途經(jīng)位置? 之間時(shí)，最優(yōu)解范圍 ，如圖3（b）所示；

3）上次途經(jīng)位置? 位于當(dāng)前位置? 和參考值? 和之間時(shí)，最優(yōu)解范圍 ，如圖3（c）所示。

反之，選擇式（28），其最優(yōu)解范圍如圖3（d）～（f）所示。

在粒子位置迭代過(guò)程中粒子位置更新后可能會(huì)超出最優(yōu)解區(qū)域，不符合本文定義的取值范圍約束。本文結(jié)合啟發(fā)式方式對(duì)迭代后不符合約束的粒子進(jìn)行規(guī)正，根據(jù)邊緣計(jì)算任務(wù)卸載的約束條件，定義以下啟發(fā)式規(guī)則：

1）對(duì)于粒子位置不符合整數(shù)約束的維度，進(jìn)行取下整運(yùn)算。

2）如果下一代粒子的位置超出約束范圍時(shí)，若該任務(wù)與其余任務(wù)沒(méi)有時(shí)間沖突，分配其計(jì)算代價(jià)最低的卸載設(shè)備。

3）如果下一代粒子中存在任務(wù)與其他任務(wù)之間不符合卸載節(jié)點(diǎn)設(shè)備的時(shí)間占用約束，則搜索與該任務(wù)存在時(shí)間沖突任務(wù)，并為這些任務(wù)重新分配卸載節(jié)點(diǎn)設(shè)備。

2.3.2? 分級(jí)交叉變異

在常用的進(jìn)化算法中[28]，在比較適應(yīng)度值較優(yōu)區(qū)域和較劣區(qū)域時(shí)，會(huì)選擇適應(yīng)度值較優(yōu)區(qū)域而淘汰較劣區(qū)域，這樣的做法導(dǎo)致粒子種群的多樣性下降，極大縮小了算法的搜索空間，導(dǎo)致算法容易陷入局部最優(yōu)限制。為了豐富粒子種群中的多樣性，擴(kuò)大算法的解空間，在本文所提出的改進(jìn)算法中，先利用啟發(fā)式規(guī)則對(duì)不符合約束的粒子進(jìn)行規(guī)正，再將粒子按照適應(yīng)度值高低分為兩組，結(jié)合遺傳理念中交叉思想，在兩組粒子中各選取一個(gè)粒子進(jìn)行交叉重組操作，選取子代中適應(yīng)度值比父代粒子適應(yīng)度值優(yōu)越的粒子進(jìn)入種群中，粒子分級(jí)交叉重組操作過(guò)程如圖4所示。

通過(guò)分級(jí)交叉重組使得粒子種群的適應(yīng)度值優(yōu)于交叉操作之前，提升粒子種群樣本豐富性。此外，本文還結(jié)合了遺傳理念中的突變思想，在粒子進(jìn)行分級(jí)交叉操作之后，根據(jù)突變概率對(duì)粒子進(jìn)行突變操作，增加算法的隨機(jī)搜索能力，利用變異算子的局部隨機(jī)搜索能力加快算法的收斂速度。

2.4? HTMC算法流程設(shè)計(jì)

本文所提的HTMC算法流程如圖5所示。

算法：HTMC算法

輸入：相關(guān)仿真設(shè)備參數(shù)，粒子長(zhǎng)度n，迭代次數(shù)m，種群數(shù)cp

輸出：最優(yōu)任務(wù)卸載策略

1.隨機(jī)初始化粒子位置；

2.根據(jù)適應(yīng)度函數(shù)計(jì)算粒子的適應(yīng)度值，并記錄全局最優(yōu)適應(yīng)度Gbest、全局最優(yōu)位置X *；

3. while （當(dāng)前迭代次數(shù)＜迭代退出次數(shù)）do

4. while （當(dāng)前粒子編號(hào)＜粒子總數(shù)） do

5.依據(jù)粒子適應(yīng)度值高低進(jìn)行分組，并執(zhí)行交叉變異運(yùn)算；

6. 根據(jù)公式（27-28），更新粒子位置；

7. if （粒子是否符合約束條件）then

8.根據(jù)啟發(fā)式規(guī)則對(duì)不符合約束的粒子進(jìn)行規(guī)正，使該粒子符合約束條件；

9.更新全局最優(yōu)適應(yīng)度Gbest；

10.根據(jù)公式（29），更新慣性權(quán)重因子；

11. 輸出最優(yōu)的任務(wù)卸載策略；

2.5? HTMC算法復(fù)雜度分析

HTMC算法的時(shí)間復(fù)雜度主要工作量是粒子群迭代進(jìn)化過(guò)程，包括目標(biāo)函數(shù)的計(jì)算和擴(kuò)大粒子種群豐富的計(jì)算。在一次迭代過(guò)程中，計(jì)算過(guò)程分為3個(gè)階段：

1）計(jì)算粒子個(gè)體屬性，計(jì)算量為n。

2）對(duì)粒子適應(yīng)度排序分組，使用歸并排序算法，平均計(jì)算量為n*logn+2。

3）計(jì)算式（26），并將所有代價(jià)進(jìn)行加權(quán)和，計(jì)算量為2n+1。

HTMC的平均時(shí)間復(fù)雜為cp*m*（n*（logn+3）+3）。HTMC的空間使用主要是保存種群屬性值和粒子適應(yīng)度值，分別為cp*n和2*（cp+1），所以算法空間復(fù)雜度為cp*（n+2）+2。

3? 仿真實(shí)驗(yàn)與分析

在本節(jié)中，對(duì)上述所提模型進(jìn)行仿真實(shí)驗(yàn)，模擬多UE終端向多個(gè)MECS和CCS的任務(wù)卸載場(chǎng)景，并將本文提出的HTMC算法與任務(wù)本地計(jì)算策略、基于遺傳算法的任務(wù)卸載策略、基于傳統(tǒng)粒子群算法的任務(wù)卸載策略進(jìn)行了對(duì)比實(shí)驗(yàn)。

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

在仿真實(shí)驗(yàn)中，利用Python實(shí)現(xiàn)HTMC算法，并采用隨機(jī)方式生成任務(wù)數(shù)據(jù)，其中任務(wù)數(shù)據(jù)量在[20-100]之間隨機(jī)產(chǎn)生，每個(gè)任務(wù)反饋結(jié)果數(shù)據(jù)量大小滿(mǎn)足[20，100]均勻分布。本仿真實(shí)驗(yàn)忽略用戶(hù)移動(dòng)過(guò)程中網(wǎng)絡(luò)通信鏈路切換的影響，只聚焦任務(wù)卸載過(guò)程，并假設(shè)邊緣服務(wù)器具有統(tǒng)一的計(jì)算能力。在模擬場(chǎng)景中，設(shè)置UE終端數(shù)量為3臺(tái)，MECS數(shù)量為8臺(tái)，CCS數(shù)量為1臺(tái)。在文獻(xiàn)[10]的基礎(chǔ)上設(shè)定本文模型的基本參數(shù)，算法具體參考值如表1所示。

3.2? 算法性能評(píng)價(jià)實(shí)驗(yàn)

為了研究本文所提的HTMC算法的性能，設(shè)置任務(wù)數(shù)為10，在迭代次數(shù)不同的情況下對(duì)比了基于遺傳算法的卸載策略（MEC_GA）、基于傳統(tǒng)粒子群算法的卸載策略（MEC_PSO）和HTMC算法，每組實(shí)驗(yàn)進(jìn)行10次，取平均值，仿真結(jié)果如圖6所示。三種算法的系統(tǒng)總代價(jià)都隨著迭代次數(shù)增加逐漸減少，本文所提的HTMC算法在收斂速度上相較于MEC_PSO和MEC_GA有較大提升，在迭代30次后平穩(wěn)，而MEC_GA到達(dá)優(yōu)化目標(biāo)位置需要的迭代次數(shù)最多，在迭代40次后趨于平穩(wěn)。

針對(duì)不同任務(wù)數(shù)量，設(shè)置迭代次數(shù)為40，對(duì)比三種算法和本地卸載策略，分析不同任務(wù)數(shù)對(duì)算法性能的影響。任務(wù)數(shù)在[25，100]之間，設(shè)置遞增梯度為25，每組實(shí)驗(yàn)進(jìn)行10次，取平均值，仿真結(jié)果如圖7所示。隨著卸載任務(wù)數(shù)量的增加，系統(tǒng)總代價(jià)升高，是因?yàn)槿蝿?wù)數(shù)量增加意味著處理任務(wù)帶來(lái)的時(shí)延和能耗增加。HTMC算法與其余三種策略對(duì)比，消耗是最低的，約為L(zhǎng)OCAL策略的12.55%、MES_PSO的29.97%、MEC_GA的38.4%。

針對(duì)不同邊緣服務(wù)器數(shù)量，設(shè)置終端數(shù)量為3、任務(wù)數(shù)為10、迭代次數(shù)為40，對(duì)比三種算法，分析邊緣服務(wù)器與異地邊端服務(wù)器數(shù)量的影響。邊緣服務(wù)器數(shù)量設(shè)置為1～8，異地邊緣服務(wù)器數(shù)量為邊緣服務(wù)器總數(shù)量減1，其中邊緣服務(wù)器數(shù)量為1時(shí)，僅包括離用戶(hù)最近的邊緣服務(wù)器。仿真結(jié)果如圖8所示，邊緣服務(wù)器數(shù)量的增加，意味著提供計(jì)算的資源增多，從圖中可知，系統(tǒng)總代價(jià)隨著邊緣服務(wù)器的數(shù)量增加而減少。HTMC算法的系統(tǒng)總代價(jià)在邊緣服務(wù)器數(shù)量為4時(shí)變得平穩(wěn)，表示在此環(huán)境下，邊緣服務(wù)器的資源能被充分利用。此外，HTMC算法在不同數(shù)量邊緣服務(wù)器下的系統(tǒng)代價(jià)始終最低。

3.3? 算法運(yùn)行開(kāi)銷(xiāo)對(duì)比實(shí)驗(yàn)

在本小節(jié)中，算法執(zhí)行過(guò)程所需要的運(yùn)行時(shí)間被用作算法運(yùn)行開(kāi)銷(xiāo)的評(píng)估參數(shù)。算法的運(yùn)行時(shí)間主要與算法迭代次數(shù)和解決約束沖突的計(jì)算次數(shù)相關(guān)。由于粒子群算法和遺傳算法均存在一定的隨機(jī)因素，為了排除仿真實(shí)驗(yàn)的偶然性，對(duì)三種算法分別進(jìn)行10次實(shí)驗(yàn)，取平均數(shù)。針對(duì)不同任務(wù)數(shù)，設(shè)置迭代次數(shù)為40次，其余參數(shù)相同，實(shí)驗(yàn)結(jié)果如圖9所示。圖中隨著任務(wù)數(shù)量的增加，算法的開(kāi)銷(xiāo)幾乎呈線(xiàn)性增長(zhǎng)，這是因?yàn)檫z傳算法和粒子群算法在迭代進(jìn)化時(shí)需要計(jì)算個(gè)體中每一個(gè)元素，而種群個(gè)體的長(zhǎng)度與任務(wù)數(shù)量是呈線(xiàn)性相關(guān)的。此外，相比另外兩者算法，HTMC算法能保持較低的開(kāi)銷(xiāo)。

4? 結(jié)? 論

本文針對(duì)邊緣計(jì)算的任務(wù)多邊卸載場(chǎng)景下的時(shí)延與能耗的優(yōu)化問(wèn)題，及MECS之間的協(xié)同任務(wù)計(jì)算問(wèn)題進(jìn)行研究，提出了HTMC算法策略。仿真結(jié)果表明，HTMC算法有更強(qiáng)的全局搜索能力，收斂速度很快，且更穩(wěn)定，算法運(yùn)行開(kāi)銷(xiāo)相對(duì)于MEC_GA和MEC_PSO有較好的優(yōu)勢(shì)。在后續(xù)研究工作中，將繼續(xù)對(duì)性能更高的時(shí)延能耗感知卸載模型進(jìn)行探究。同時(shí)，對(duì)多用戶(hù)多邊協(xié)同卸載的實(shí)際應(yīng)用也是后續(xù)的研究方向。

參考文獻(xiàn)：

[1] LECUN Y，BOTTOU L，BENGIO Y，et al. Gradient-based Learning Applied to Document Recognition [J].Proceedings of the IEEE，1998，86（11）：2278-2324.

[2] HE K M，ZHANG X Y，REN S Q，et al. Deep Residual Learning for Image Recognition [C]//2016 IEEE Conference on Computer Vision and Pattern Recognition（CPVR）.Las Vegas：IEEE，2016：770-778.

[3] 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.

[4] LI H X，SHOU G C，HU Y H，et al. Mobile Edge Computing：Progress and Challenges [C]//2016 4th IEEE International Conference on Mobile Cloud Computing， Services， and Engineering（MobileCloud）.Oxford：IEEE，2016：83-84.

[5] FLORES H，HUI P，TARKOMA S，et al. Mobile Code Offloading：From Concept to Practice and Beyond [J].IEEE Communications Magazine，2015，53（3）：80-88.

[6] LIU J，MAO Y Y，ZHANG J，et al. Delay-optimal Computation Task Scheduling for Mobile-edge Computing Systems [C]//2016 IEEE International Symposium on Information Theory（ISIT）.Barcelona：IEEE，2016：1451-1455.

[7] MAO Y Y，ZHANG J，LETAIEF K B. Dynamic Computation Offloading for Mobile-edge Computing with Energy Harvesting Devices [J].IEEE Journal on Selected Areas in Communications，2016，34（12）：3590-3605.

[8] BI S Z，ZHANG Y J. Computation Rate Maximization for Wireless Powered Mobile-edge Computing with Binary Computation Offloading [J].IEEE Transactions on Wireless Communications，2018，17（6）：4177-4190.

[9] DENG M F，TIAN H，F(xiàn)AN B. Fine-granularity Based Application Offloading Policy in Cloud-Enhanced Small Cell Networks [C]//2016 IEEE International Conference on Communications Workshops（ICC）.Kuala：IEEE，2016：638-643.

[10] GUO F X，ZHANG H L，JI H，et al. An Efficient Computation Offloading Management Scheme in the Densely Deployed Small Cell Networks with Mobile Edge Computing [J].IEEE/ACM Transactions on Networking，2018，26（6）：2651-2664.

[11] WU J Z，CAO Z Y，ZHANG Y J，et al. Edge-cloud Collaborative Computation Offloading Model Based on Improved Partical Swarm Optimization in MEC [C]//2019 IEEE 25th International Conference on Parallel and Distributed Systems（ICPADS）.Tianjin：IEEE，2019：959-962.

[12] CHEN M-H，LIANG B，DONG M. Joint Offloading and Resource Allocation for Computation and Communication in Mobile Cloud with Computing Access Point [C]//IEEE INFOCOM 2017-IEEE Conference on Computer Communications.Atlanta：IEEE，2017：1-9.

[13] 張海波，李虎，陳善學(xué)，等.超密集網(wǎng)絡(luò)中基于移動(dòng)邊緣計(jì)算的任務(wù)卸載和資源優(yōu)化 [J].電子與信息學(xué)報(bào)，2019，41（5）：1194-1201.

[14] KAI C H，ZHOU H，YI Y B，et al. Collaborative Cloud-edge-end Task Offloading in Mobile-edge Computing Networks with Limited Communication Capability [J].IEEE Transactions on Cognitive Communications and Networking，2020，7（2）：624-634.

[15] SUN M，BAO T，XIE D，et al. Towards Application-driven Task Offloading in Edge Computing Based on Deep Reinforcement Learning [J].Micromachines，2021，12（9）：1011.

[16] ABDEL-KADER R F，EL-SAYAD N E，RIZK R Y. Efficient Energy and Completion Time for Dependent Task Computation Offloading Algorithm in Industry 4.0 [J].PLoS One，2021，16（6）：e0252756.

[17] FANG J，SHI J M，LU S B，et al. An Efficient Computation Offloading Strategy with Mobile Edge Computing for IoT [J].Micromachines，2021，12（2）：204.

[18] YANG T T，F(xiàn)ENG H L，GAO S，et al. Two-stage Offloading Optimization for Energy–latency Tradeoff with Mobile Edge Computing in Maritime Internet of Things [J].IEEE Internet of Things Journal，2020，7（7）：5954-5963.

[19] 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.

[20] 羅斌，于波.移動(dòng)邊緣計(jì)算中基于粒子群優(yōu)化的計(jì)算卸載策略 [J].計(jì)算機(jī)應(yīng)用，2020，40（8）：2293.

[21] LIU Y P，HUANG W，WANG L P，et al. Dynamic Computation Offloading Algorithm Based on Particle Swarm Optimization with a Mutation Operator in Multi-access Edge Computing [J].Mathematical Biosciences and Engineering，2021，18（6）：9163-9189.

[22] SHANNON C E. Communication in the Presence of Noise [J].Proceedings of the IRE，1949，37（1）：10-21.

[23] XIAO M B，SHROFF N B，CHONG E K P. A Utility-based Power-control Scheme in Wireless Cellular Systems [J].IEEE/ACM Transactions on Networking（TON），2003，11（2）：210-221.

[24] RAPPAPORT T S. Wireless Communications：Principles and Practice：2nd Edition [M].New York：Pearson Education India，2001.

[25] WANG Y，SHENG M，WANG X，et al. Mobile-edge Computing：Partial Computation Offloading Using Dynamic Voltage Scaling [J].IEEE Transactions on Communications，2016，64（10）：4268-4282.

[26] KENNEDY J，EBERHART R C. A Discrete Binary Version of the Particle Swarm Algorithm [C]//1997 IEEE International Conference on Systems，Man，and Cybernetics.Computational Cybernetics and Simulation.IEEE，1997，5：4104-4108.

[27] ASKARI Q，YOUNAS I，SAEED M. Political Optimizer： A Novel Socio-inspired Meta-heuristic for Global Optimization [J].Knowledge-based Systems，2020，195：105709.

[28] GONG Y J，LI J J，ZHOU Y，et al. Genetic Learning Particle Swarm Optimization [J].IEEE Transactions on Cybernetics，2015，46（10）：2277-2290.

作者簡(jiǎn)介：柏建雄（1998—），男，漢族，湖南永州人，碩士研究生在讀，研究方向：邊緣計(jì)算。