基于多目標優(yōu)化的移動邊緣計算任務卸載方法

蔣金陵，徐勝超

（廣州華商學院 數(shù)據(jù)科學學院，廣東 廣州 511300）

0 引言

移動互聯(lián)網(wǎng)的應用類型越來越多，導致移動終端設備對延時與能耗的要求越來越高[1-3]。移動邊緣計算指在移動終端周圍布設高性能邊緣服務器，通過該服務器處理網(wǎng)絡信息并卸載邊緣設備形成的部分任務，可降低網(wǎng)絡服務延時[4]。但移動邊緣計算內(nèi)包含大量邊緣設備與邊緣服務器，導致其任務卸載難度較高，降低了節(jié)點資源分配的合理性，無法為用戶提供高質(zhì)量的數(shù)據(jù)服務[5-6]。為此，需要研究移動邊緣計算任務卸載方法，提升數(shù)據(jù)服務質(zhì)量。

例如文獻[7]提出了一種基于元強化學習的任務卸載方法，該方法可以在少量梯度更新和樣本的情況下快速適應新環(huán)境；將移動應用程序建模為有向無環(huán)圖（DAG），并通過自定義序列到序列神經(jīng)網(wǎng)絡執(zhí)行卸載策略；利用一階近似和截斷代理目標協(xié)同的方法訓練網(wǎng)絡。該方法可以將延遲減少25%，同時能夠快速適應新環(huán)境，但該方法僅考慮了移動邊緣計算任務卸載的延遲問題，并未考慮任務卸載的能耗問題，導致任務卸載能耗較高。文獻[8]設計了一種基于深度Q 學習的智能任務卸載方案，以應對快速變化的場景，引入軟件定義網(wǎng)絡進行信息采集和集中管理，通過深度Q 學習處理集中管理的信息，完成任務卸載。該方法不僅具有良好的適應性，而且具有較高的性能，但該方法缺少訓練模型，影響任務卸載效果，沒有在任務卸載時同時優(yōu)化任務卸載時延與能耗兩個目標。文獻[9]提出針對移動邊緣計算的多目標優(yōu)化的云集部署和任務卸載方法，該方法通過優(yōu)化云服務器的部署位置和任務的卸載策略，旨在實現(xiàn)多個優(yōu)化目標的平衡，如延遲、能耗和帶寬利用率等。該方法可以提高移動邊緣計算系統(tǒng)的效率和性能，但在復雜的場景下，優(yōu)化問題的求解可能會面臨挑戰(zhàn)，需要考慮更多的約束條件和變量。文獻[10]提出基于OFDMA 的協(xié)同邊緣計算中的節(jié)能聯(lián)合任務卸載和資源分配，該方法利用OFDMA 技術將邊緣設備劃分為多個子載波，實現(xiàn)資源的分配和任務的卸載。通過聯(lián)合考慮任務卸載和資源分配，旨在提高邊緣計算系統(tǒng)的能源效率和性能，但在實際部署中需要考慮設備之間的協(xié)作和通信開銷，以及網(wǎng)絡拓撲結構的限制等因素。

為解決上述方法中存在的問題，本文研究基于多目標優(yōu)化的移動邊緣計算任務卸載方法，多目標優(yōu)化是一種能夠平衡多個沖突目標的優(yōu)化方法。在任務卸載中涉及到資源分配、能耗、延遲等多個指標，而這些指標之間存在相互制約和沖突關系。運用多目標優(yōu)化方法可以找到一組最優(yōu)解，使得各個目標得到平衡和優(yōu)化。多目標優(yōu)化的優(yōu)勢在于其平衡性、靈活性、可行性和魯棒性，它可以平衡不同目標之間的權衡關系，根據(jù)需求和約束條件進行調(diào)整，提供多個可行解供選擇，并具有更好的魯棒性。因此，在任務卸載中充分發(fā)揮多目標優(yōu)化技術的優(yōu)勢能夠優(yōu)化策略，提高移動邊緣計算系統(tǒng)的性能和效率。

1 多目標優(yōu)化的移動邊緣計算任務卸載方法描述

在傳統(tǒng)的單目標優(yōu)化中，只需考慮一個目標函數(shù)并尋找其最優(yōu)解。然而，在現(xiàn)實世界中，往往需要同時考慮多個目標，而這些目標之間常常存在著相互制約和沖突的關系。多目標優(yōu)化旨在通過尋找一組最優(yōu)解，使得各個目標盡可能地得到平衡和優(yōu)化，本文主要平衡的目標指標為資源分配、能耗、延遲。為了更好地理解多目標優(yōu)化的原理，可以考慮使用改進遺傳算法作為例子。

遺傳算法是一種模擬自然進化過程的優(yōu)化算法，通過借鑒生物進化中的遺傳、變異和選擇機制來搜索優(yōu)化空間。在傳統(tǒng)的遺傳算法中，只能優(yōu)化單個目標函數(shù)，而多目標優(yōu)化則將其擴展到多個目標函數(shù)的情況下。在多目標優(yōu)化中，改進遺傳算法可以通過引入多個適應度函數(shù)來評估解的質(zhì)量，每個適應度函數(shù)對應一個優(yōu)化目標。通過遺傳算子（如選擇、交叉和變異）對解進行操作，并根據(jù)多個適應度函數(shù)的值進行選擇，從而形成一組更好的解集，稱為“非支配解集”或“帕累托前沿”。改進遺傳算法中的非支配排序和擁擠度距離等技術可以幫助確定非支配解集中的優(yōu)秀解，并維持解的多樣性。通過迭代進化，逐步逼近帕累托前沿，從而找到一組平衡和優(yōu)化的解。將多目標優(yōu)化技術應用于邊緣計算任務卸載中，可以考慮在資源分配、能耗、延遲等指標之間進行權衡和優(yōu)化。

本文通過使用改進遺傳算法來搜索最優(yōu)解空間，可以得到一組平衡的任務卸載方案，使得系統(tǒng)能夠在多個目標之間取得最佳平衡。總結起來，多目標優(yōu)化是一種解決具有多個沖突目標問題的優(yōu)化方法，通過結合改進遺傳算法，可以在邊緣計算任務卸載中應用多目標優(yōu)化技術，以權衡和優(yōu)化不同指標，得到平衡和優(yōu)化的解決方案。

1.1 移動邊緣計算網(wǎng)絡

在網(wǎng)絡結構中，計算和存儲容量被下放到移動網(wǎng)絡的邊緣，如基站和無線接入點。移動設備可以將應用任務卸載到附近計算節(jié)點進行處理，進行低時延的計算服務[10-13]。移動邊緣計算網(wǎng)絡架構如圖1 所示。

圖1 移動邊緣計算網(wǎng)絡架構

在圖1 所示的移動邊緣計算（Mobile Edge Computing,MEC）網(wǎng)絡體系結構中，服務器的資源明顯少于核心網(wǎng)。因此，當服務器無法處理移動設備的任務請求時，它將向核心網(wǎng)發(fā)送請求進行處理。此外，核心網(wǎng)還負責存儲大量的數(shù)據(jù)信息、數(shù)據(jù)集成、分析和全局數(shù)據(jù)共享等功能。

邊緣云由各種服務器組成，部署在網(wǎng)絡邊緣，提供計算、存儲等資源。與傳統(tǒng)的MCC（Mobile Cloud Computing）網(wǎng)絡架構不同，邊緣云更接近移動設備，計算和存儲資源更加緊密。通過將任務卸載到邊緣云進行本地化處理，移動設備能夠有效減少任務處理延遲，節(jié)省設備能耗。在圖1 所示的網(wǎng)絡體系結構中，服務器的主要功能是處理移動設備的任務卸載策略，以滿足移動設備對低時延、可靠性和位置感知的需求。

移動設備主要指位于網(wǎng)絡邊緣的用戶使用的各種設備，包括智能手機、可穿戴智能設備、筆記本電腦和無人駕駛汽車等。在分布式網(wǎng)絡體系結構中，移動設備是各種應用任務處理的發(fā)起者，也是網(wǎng)絡計算服務的主要用戶。

令卸載任務集為Q={q1,q2,…,qn}，且每個子任務間無任何關聯(lián)[14-15]。在任務集Q內(nèi)，各任務均需決定本地或邊緣服務器的卸載方式。

1.2 移動邊緣計算任務卸載多目標優(yōu)化模型

將Q劃分成四部分，即Q={}Rin,W,Z,Rout。其中：Rin是任務傳輸至移動邊緣服務器CPU 的數(shù)據(jù)量；W是任務計算量；Z是任務卸載計算資源；Rout是任務卸載結束后反饋至移動邊緣設備的數(shù)據(jù)量。

令移動邊緣設備CPU 的計算能力是不變的，即移動邊緣設備CPU 的計算能力為x，且x為不變的，則qi在本地CPU 執(zhí)行的時延為wi與x的比值，即=wix。

移動邊緣服務器CPU 的計算能力V在執(zhí)行任務卸載時是固定不變的，而移動邊緣設備上傳數(shù)據(jù)的傳輸速率為gup，移動邊緣設備下載任務的傳輸速率為gdown。任務卸載時延可以通過將qi任務上傳到移動邊緣服務器CPU 內(nèi)進行計算來展開，qi的任務卸載時延在4 種條件下的情況如下：

式中：f0是移動邊緣設備本地CPU 計算頻率；fj是移動邊緣服務器計算頻率；qi-1=1時，代表任務已在移動邊緣服務器CPU 內(nèi)卸載，qi-1=0時，代表任務在移動邊緣設備本地CPU 內(nèi)卸載。

移動邊緣計算任務卸載的總時延為：

移動邊緣計算任務卸載的總能耗為：

式中：pend、pup、pdown分別是移動邊緣設備CPU 執(zhí)行、上傳、接收功率；tend、tup、tdown分別是執(zhí)行、上傳、接收時間；γ是能耗系數(shù)。

以最小時延、最小能耗為優(yōu)化目標，建立移動邊緣計算任務卸載多目標優(yōu)化模型，公式如下：

式中：F(X)是綜合代價因子；ω是權值；O1是任務卸載計算資源分配約束；ri是卸載qi時的數(shù)據(jù)量；ti是卸載qi的時間；O2是權值約束；O3是總能耗低于設備剩余電量的約束；yi是qi的卸載決策；yij是第j個邊緣設備與邊緣服務器間的任務卸載決策；gj是邊緣設備與邊緣服務器間的傳輸速率；di是CPU 周期數(shù)；O4是任務卸載決策約束；O5是任務卸載傳輸功率約束；pi是卸載qi時的傳輸功率；pmax是最大傳輸功率；O6是任務卸載的時延約束；Z'為最大傳輸數(shù)據(jù)量；yik是第k個邊緣設備與邊緣服務器間的任務卸載決策。

1.3 節(jié)點切換約束

設備在移動時，網(wǎng)絡連通性可能會發(fā)生變化，因此，邊緣節(jié)點應考慮移動設備鏈接的穩(wěn)定性，并及時檢測和處理網(wǎng)絡中斷或切換。這樣可以確保任務能夠平穩(wěn)地從一個邊緣節(jié)點切換到另一個邊緣節(jié)點，而不會丟失數(shù)據(jù)或?qū)е路罩袛唷?/p>

考慮到移動邊緣計算網(wǎng)絡各個節(jié)點之間的執(zhí)行優(yōu)先級以及執(zhí)行期限，節(jié)點切換需要滿足運行截止期限的約束、優(yōu)先級約束以及節(jié)點完成期限約束。在此次構建的多目標優(yōu)化模型中，第一個任務和最優(yōu)一個均在本地執(zhí)行，因此運行截止期限約束可以表示為：

式中：Blocal,m表示緩存器數(shù)據(jù)延遲；Tm表示節(jié)點結束時間；λem表示常數(shù)；e(vm,vn)表示服務器執(zhí)行延遲；Lm表示最后一個節(jié)點在本地的執(zhí)行延遲；Tn表示第一個任務開始的時間。

如果節(jié)點vi是節(jié)點vj直接父節(jié)點，則節(jié)點vi的執(zhí)行優(yōu)先級高于節(jié)點vj。節(jié)點vi的優(yōu)先級計算公式為：

式中：priority(vi)表示節(jié)點vi的執(zhí)行優(yōu)先權；succ(vi)表示節(jié)點vi的直接后繼節(jié)點集合。

從最后一個節(jié)點vv開始遍歷全部優(yōu)先級，最后一個節(jié)點的優(yōu)先級可以表示為：

式中Tv表示最后一個節(jié)點的執(zhí)行時間。

任何一個任務節(jié)點vj都必須在其所有先前任務都完成以及處理完組件設備之后才算結束，因此節(jié)點vj的開始時間不得早于節(jié)點vi的結束時間。如果兩個節(jié)點不處于一個分區(qū)內(nèi)，還需要考慮傳輸時間的影響。在上述情況下構建節(jié)點完成期間約束公式：

式中：Bserver,k表示服務器數(shù)據(jù)延遲；w(e(vi,vj))表示兩個節(jié)點間的通信延遲；Sj表示延遲參數(shù)。

1.4 移動邊緣計算任務卸載多目標優(yōu)化模型求解

完成節(jié)點切換約束的處理后，采用改進遺傳算法對移動邊緣計算任務卸載多目標優(yōu)化模型進行求解。

改進遺傳算法是對傳統(tǒng)遺傳算法的一種優(yōu)化和改進，具有提高收斂速度、支持多目標優(yōu)化和維持解的多樣性等優(yōu)勢。相比其他智能優(yōu)化算法，改進遺傳算法具有較強的全局搜索能力、適應性和魯棒性，并且具有較好的可解釋性，它通過引入非支配排序、擁擠度距離等技術，能夠加快收斂速度，生成平衡和優(yōu)化的解集，并在復雜問題中找到全局最優(yōu)解或接近最優(yōu)解。這使得改進遺傳算法成為解決多目標優(yōu)化和需要維持解多樣性問題的有效工具。因此，本文選擇改進遺傳算法作為優(yōu)化方法，能夠充分發(fā)揮其優(yōu)勢，提高問題求解的效率和質(zhì)量。利用改進遺傳算法求解1.2 節(jié)建立的移動邊緣計算任務卸載多目標優(yōu)化模型，得到最小時延、最小能耗對應的移動邊緣計算任務卸載策略。多目標優(yōu)化模型的求解流程如圖2 所示。

圖2 改進遺傳算法與多目標優(yōu)化模型求解流程

以下是使用改進遺傳算法解決多目標優(yōu)化模型的步驟：

步驟1：初始化，設置最大容忍時延與設備剩余電量等參數(shù)[16]，定義種群規(guī)模與迭代次數(shù)等參數(shù)。

步驟2：利用十進制實數(shù)編碼方式編碼個體，即移動邊緣計算任務卸載策略，生成初始種群[17-19]，即移動邊緣計算任務多目標優(yōu)化模型的全部可行解。

步驟3：利用式（2）計算移動邊緣時延t。

步驟4：利用式（3）計算E。

步驟5：利用式（4）計算F(X)。

步驟6：求解各移動邊緣計算任務卸載策略是否符合式（4）的約束條件，如果符合約束，則繼續(xù)步驟7，反之，返回步驟3。

步驟7：保留符合約束條件的種群個體[20]，并計算這些個體的適應度。適應度是以移動邊緣計算任務卸載的綜合代價因子為基礎，即綜合代價越小，個體適應度越大。

步驟8：計算個體選擇概率，并利用輪盤賭[21]選擇法執(zhí)行選擇操作。

步驟9：計算選擇個體的單體分解概率，并計算雙體組合概率，然后根據(jù)雙體組合概率計算個體間隔互換概率。接著進行個體交叉操作與變異操作[22]。

步驟10：反復操作步驟9 以生成新種群位置，修正移動邊緣計算任務卸載策略。

步驟11：反復操作步驟3～步驟9，以達到最大迭代次數(shù)為止[23]，輸出最小時延與最小能耗對應的移動邊緣計算任務卸載策略。

2 仿真實驗與性能分析

2.1 實驗環(huán)境設置

此次仿真實驗的環(huán)境參數(shù)如表1 所示。

表1 仿真實驗的環(huán)境參數(shù)

為了驗證所提出方法的性能，將使用Matlab 7.2 進行實驗。在這個實驗中將建立一個真實的網(wǎng)絡場景，每個移動設備都將運行真實的應用程序，例如人臉識別、視頻處理和語音識別等。信道的時變性將遵循瑞利分布。設置移動設備的數(shù)量在40～100 之間，并且信道數(shù)量在4～8 之間變化。移動邊緣計算網(wǎng)絡服務器的數(shù)量為{4，6，8，10，12}，基站的覆蓋范圍則在50～100 m 之間變化。

該移動邊緣計算場景的具體參數(shù)如表2 所示。改進遺傳算法的具體參數(shù)如表3 所示。

表2 移動邊緣計算場景的具體參數(shù)

表3 改進遺傳算法的具體參數(shù)

該多任務-多邊緣服務器移動邊緣計算場景共包含兩種類型，分別是復雜移動邊緣計算場景與簡單移動邊緣計算場景。

2.2 目標函數(shù)綜合代價的結果分析

本文方法中，權值的取值直接影響移動邊緣計算任務卸載效果，為此，分析不同權值ω時本文方法任務卸載的綜合代價，確定最佳的權值ω取值，分析結果如圖3所示。

圖3 不同權值時的綜合代價

根據(jù)圖3 的結果顯示，本文方法在簡單場景和復雜場景下，移動邊緣計算任務卸載的綜合代價隨著權值的提升先下降后上升。當權值ω為0.7時，兩種場景下的綜合代價達到最低點，之后開始上升。這一實驗結果驗證了本文方法在權值為0.7 時能夠?qū)崿F(xiàn)移動邊緣計算任務卸載的最小綜合代價，可以通過改進遺傳算法的特點來解釋。改進遺傳算法具有全局搜索能力和多樣性維持的優(yōu)勢，在優(yōu)化過程中，初始權值較低時，算法更加注重優(yōu)化目標的平衡，使得綜合代價下降。然而，隨著權值的增加，算法更加注重單個優(yōu)化目標，可能導致部分解的質(zhì)量下降，從而使綜合代價上升。因此，通過遺傳算法的優(yōu)化過程，本文方法能夠找到權值為0.7 時的最優(yōu)解，使得移動邊緣計算任務卸載的綜合代價最小化。這也說明了遺傳算法在尋找復雜優(yōu)化問題最優(yōu)解方面的有效性和適用性。

2.3 任務卸載結果分析

以簡單移動邊緣計算場景為例，在該場景內(nèi)隨機選擇10 個需要任務卸載的移動邊緣設備，利用本文方法對這10 個移動邊緣設備進行任務卸載，任務卸載結果如表4 所示。

表4 移動邊緣計算任務卸載結果

根據(jù)表4 可知，本文方法可有效完成移動邊緣計算任務卸載，對于卸載資源低于20%的移動邊緣設備，其任務卸載方式為本地CPU 卸載，對于卸載資源超過20%的移動邊緣設備，結合多目標優(yōu)化和改進遺傳算法，本文方法在邊緣任務卸載中展現(xiàn)出了優(yōu)秀的性能。多目標優(yōu)化能夠平衡多個沖突的優(yōu)化目標，并生成一組平衡的解集，適用于考慮延遲、能耗、帶寬利用率等多個指標的邊緣任務卸載場景。改進遺傳算法具有全局搜索能力和多樣性維持的優(yōu)勢，在復雜問題空間中能夠搜索全局最優(yōu)解或接近最優(yōu)解的解集。同時，改進遺傳算法具有較好的可解釋性，易于理解和解釋算法的運行過程。因此，通過將多目標優(yōu)化與改進遺傳算法相結合，本文方法在邊緣任務卸載中展現(xiàn)出了出色的性能和效果。

2.4 任務卸載的時延分析

利用本文方法對兩種移動邊緣計算場景進行移動邊緣計算任務卸載，移動邊緣計算任務卸載的時延如圖4 所示。

圖4 移動邊緣計算任務卸載的時延

根據(jù)圖4 可知，對于簡單場景與復雜場景，本文方法均可有效完成移動邊緣計算任務卸載，不同移動邊緣數(shù)量時，復雜場景下任務卸載時延均高于簡單場景下任務卸載時延。簡單場景的最高時延在40 s 左右，復雜場景的最高時延在43 s 左右。根據(jù)表2 可知，18 個移動邊緣設備的最大容忍時延是72 s，對比可知，在簡單場景與復雜場景下，本文方法任務卸載時延均顯著低于最大容忍時延，說明本文方法任務卸載的時延較短。

2.5 任務卸載的能耗分析

移動邊緣計算任務卸載的能耗如圖5 所示。根據(jù)圖5 可知，不同移動邊緣數(shù)量時，復雜場景下任務卸載能耗均高于簡單場景下任務卸載能耗。簡單場景的最高能耗在13 kJ左右，復雜場景的最高能耗在15 kJ左右，在簡單場景與復雜場景下，本文方法任務卸載能耗均未超過能耗閾值，說明本文方法任務卸載的能耗較低。

圖5 移動邊緣計算任務卸載的能耗

綜合分析可知，對于簡單場景與復雜場景來說，本文方法均可有效縮短移動邊緣計算任務卸載延時，降低任務卸載能耗。

2.6 平均用戶效用分析

以復雜場景為例，分析在文獻[7]、文獻[8]方法和本文方法作用下的平均用戶效能，其值越低，任務卸載效果越佳，分析結果如圖6所示，平均用戶效用需控制在1.0以內(nèi)[23]。

圖6 平均用戶效用分析結果

根據(jù)圖6可知：隨著剩余電量的提升，在三種方法作用下平均用戶效用均呈下降趨勢；剩余電量一致時，本文方法作用下的平均用戶效用最低，即任務卸載效果較佳。

3 結論

移動邊緣計算通過將移動設備生成的任務卸載至邊緣服務器，并利用虛擬化和網(wǎng)絡等技術提供了更靈活的計算資源獲取方式。為了進一步提升移動邊緣計算任務卸載的效果，本文采用了基于多目標優(yōu)化的方法，該方法中考慮了任務卸載延時和能耗這兩個關鍵的優(yōu)化目標，以提供高質(zhì)量的數(shù)據(jù)服務給用戶。為了實現(xiàn)這一目標，運用改進遺傳算法進行任務卸載決策的優(yōu)化。通過將多目標優(yōu)化與改進遺傳算法相結合，能夠在移動邊緣計算任務卸載中實現(xiàn)更好的效果，平衡了任務卸載延時和能耗這兩個優(yōu)化目標，從而為用戶提供高質(zhì)量的數(shù)據(jù)服務。通過改進遺傳算法的全局搜索能力和多樣性維持的特點，能夠找到最優(yōu)的任務卸載決策，以實現(xiàn)綜合優(yōu)化的目標。因此，基于多目標優(yōu)化和改進遺傳算法的移動邊緣計算任務卸載方法能夠提供更高效、可靠的數(shù)據(jù)服務，并滿足用戶對計算資源獲取的靈活需求。