移動邊緣計算中的多用戶多邊協(xié)同卸載策略

柏建雄 魏佳隆 孟曉磊 劉揚 趙振

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

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

中圖分類號：TN929.5；TP393? 文獻標識碼：A? 文章編號：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? 引? 言

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

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

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

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

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

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

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

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

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

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

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

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

1? 系統(tǒng)模型

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

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

1）本地執(zhí)行：計算任務在用戶本地設備上執(zhí)行。

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

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

1.1? 通信模型

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

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

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

信道增益Hij又可由信道長度dij計算得出[24]，信道增益計算式為：

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

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

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

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

1.2? 計算卸載模型

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

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

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

1）當任務在本地執(zhí)行時，任務Ti的計算時延為：

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

2）任務卸載至邊緣服務器執(zhí)行時，根據(jù)文獻[25]，數(shù)據(jù)上行和下行分別具有不同的信號頻率，由香農(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之間的距離。

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

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

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

將任務卸載至MECS時，當靠近UE的MECS負載過高時，任務將由當前服務器卸載至異地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之間的距離。

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

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

3）任務卸載至CCS執(zhí)行時，UE終端將任務卸載至CCS執(zhí)行，并需要將任務執(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之間的距離。

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

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

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

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

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

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

2? HTMC算法設計

2.1? 粒子編碼方式

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

2.2? 解法模型

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

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

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

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

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

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

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

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

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

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

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

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

2）如果下一代粒子的位置超出約束范圍時，若該任務與其余任務沒有時間沖突，分配其計算代價最低的卸載設備。

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

2.3.2? 分級交叉變異

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

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

2.4? HTMC算法流程設計

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

算法：HTMC算法

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

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

1.隨機初始化粒子位置；

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

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

4. while （當前粒子編號＜粒子總數(shù)） do

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

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

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

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

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

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

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

2.5? HTMC算法復雜度分析

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

1）計算粒子個體屬性，計算量為n。

2）對粒子適應度排序分組，使用歸并排序算法，平均計算量為n*logn+2。

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

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

3? 仿真實驗與分析

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

3.1? 實驗設置

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

3.2? 算法性能評價實驗

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

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

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

3.3? 算法運行開銷對比實驗

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

4? 結(jié)? 論

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

參考文獻：

[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] 張海波，李虎，陳善學，等.超密集網(wǎng)絡中基于移動邊緣計算的任務卸載和資源優(yōu)化 [J].電子與信息學報，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] 羅斌，于波.移動邊緣計算中基于粒子群優(yōu)化的計算卸載策略 [J].計算機應用，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.

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