基于DP-HAFS算法的移動邊緣計算卸載策略

作者簡介：王亭惠（1998－），女（通信作者），吉林榆樹人，碩士研究生，主要研究方向為邊緣計算（wangtinghui0203@163.com）；陳桂芬（1964－），女，吉林九臺人，教授，博導，博士，主要研究方向為無線通信系統理論與技術．

摘 要：針對移動邊緣計算的計算資源有限、系統處理任務總開銷過高的問題，提出一種基于動態感知—混合人工魚群（DP-HAFS）算法的卸載策略。首先，構建本地—邊緣—云端三層網絡架構，采用基于細粒度的部分卸載模式；然后，針對一個終端設備被多個基站覆蓋的場景，提出基站選擇策略進行最優基站的選擇；最后，采用DP-HAFS算法對卸載決策進行動態修正，得到最優卸載策略。仿真結果表明，所提卸載策略在任務數量較多的場景下能有效降低系統總開銷。

關鍵詞：移動邊緣計算；卸載決策；基站選擇；人工魚群算法

中圖分類號：TP393 文獻標志碼：A

文章編號：1001－3695（2023）04－036－1184－05

doi：10.19734/j.issn.1001-3695.2022.08.0419

Abstract：Aiming at computer resources are limited and the total overhead of the system processing tasks are too high，this paper proposed an offloading strategy based on dynamic perception-hybrid artificial fish swarm（DP-HAFS） algorithm.Firstly，it constructed a local-edge-cloud three-layer network architecture and adopted a fine-grained partial offloading mode.Then，for the scenario where a terminal device covered by multiple base stations，this paper proposed a base station selection strategy to select the optimal base station.Finally，it used the DP-HAFS algorithm to dynamically modify the offloading decision and got the best uninstall strategy.The simulation results show that the proposed offloading strategy can effectively reduce the total system overhead in a scenario with a large number of tasks.

Key words：mobile edge computing（MEC）；offloading decision；base station selection；artificial fish swarm algorithm

0 引言

隨著網絡交流、增強現實、物聯網、車聯網等智能設備的快速發展，智能設備呈爆發式增長，但受其自身的計算、存儲及電池等資源的限制，針對計算密集型和時延敏感型的智能設備在處理大量任務時面臨挑戰[1，2]，因此，研究一種多終端設備—多服務器場景的移動邊緣計算卸載問題尤為重要。

蜂窩網絡是一種移動通信硬件架構，由于構成網絡覆蓋的各通信基地臺的信號覆蓋呈六邊形，使整個網絡像一個蜂窩，蜂窩網絡也因此而得名[3]。在蜂窩網絡中，計算卸載技術最初應用于移動云計算（MCC），MCC的優勢在于提供充足的計算資源，緩解任務在本地執行的高能耗和高時延。但云計算也存在明顯的弊端，因為移動終端設備與云服務器距離較遠，當執行任務量大時，會因傳輸距離較遠產生較大時延，導致能耗增加，即云計算不適合具有時延敏感型的應用[4～6]。為解決云計算所產生時延高的問題，有學者提出了移動邊緣計算（mobile edge computing，MEC），即將移動終端設備的任務通過無線蜂窩網絡卸載到了一個靠近MEC的服務器上，這種方法可以顯著提高計算速度和質量[7]。在移動邊緣計算卸載問題中，MCC和MEC各有利弊，MCC主要針對任務量較大的計算場景，MEC則適用于時延敏感型場景。

計算卸載技術是移動邊緣計算的關鍵技術，研究人員從不同方面提出移動邊緣計算卸載方案。針對MEC卸載結構，文獻[8～10]使用本地—邊緣兩層網絡卸載結構，主要針對時延敏感型場景，不適用于對數據處理量大的場景。因此有學者提出了云輔助的網絡卸載模型，能處理數據需求量大的場景，文獻[5]考慮了不同類型的云實例，針對多用戶—單基站場景基于排隊分析設計了最優資源分配算法，以最小的系統成本保證用戶服務質量。但文獻[5，11，12]僅考慮了多用戶—單基站場景，對用戶被多個基站覆蓋的情況并不適用。

針對MEC任務卸載模式，文獻[13，14]采用二進制卸載，其中文獻[14]考慮了任務之間具有依賴關系，在原始卸載模型中提出了具有優先約束關系的工作流模型，使用基于改進遺傳算法的計算卸載算法求最優解；文獻[15]基于有向無環圖的多依賴任務計算卸載，共同考慮了應用程序的拓撲結構和多個用戶之間的信道干擾。文獻[14，15]對任務卸載劃分不夠精細，不能更加準確地得到卸載策略。文獻[16]采用部分卸載，將多用戶計算卸載問題轉換為一個混合整數線性規劃問題，設計了迭代啟發式MEC資源分配算法卸載決策。

針對優化邊緣計算卸載問題，文獻[17]針對密集型網絡，改進粒子群算法，提出種群多樣性的二進制粒子群算法的計算卸載策略，能有效尋找最優解，但僅考慮了時延對任務卸載的影響。文獻[18]研究了云端、邊緣端協同計算卸載問題，提出了近似協同計算卸載方案和博弈論協同計算卸載方案，只考慮能耗對任務卸載的影響；文獻[19]提出了一個隨機優化問題，涉及本地設備、基站和后端云之間的動態卸載和資源調度，提出了一種基于Lyapunov優化理論的在線動態卸載和資源調度，但算法過于復雜不易實現。

與已有研究不同，本文針對多終端設備—多服務器場景使用細粒度卸載，a）當一個終端用戶被多個基站覆蓋時，通過基站選擇函數，將任務卸載至選擇函數值最高的基站，該基站充分考慮了物理距離、負載率和卸載開銷等影響因素；b）提出了基于動態感知—混合人工魚群（dynamic perception-hybrid artificial fish swarm，DP-HAFS）算法，在人工魚群算法的基礎上充分考慮狼群算法收斂性強的優點，并引入動態感知擁擠度因子進行更優個體的篩選，基于該改進算法得到最優卸載策略。通過仿真結果發現，對比多個經典卸載策略和文獻[20]的卸載策略，本文提出的移動邊緣計算卸載策略在處理任務過程中的時延與能耗性能更優越、任務處理能力更強、總開銷更小。

1 系統模型及問題描述

1.1 系統模型

本文基于移動邊緣計算卸載的系統模型如圖1所示，模型包括一個遠端云服務器、多個帶有邊緣服務器的基站和多個移動終端設備，組成了云—邊—端三層 MEC 計算卸載結構。終端設備通過無線鏈路與基站相連，基站通過有線鏈路與云端相連。移動終端任務可以在本地執行或卸載到基站邊緣端執行，基站可以將任務卸載至遠端云服務器執行，并將遠端云服務器的計算結果返回到終端設備。如圖1所示，使用細粒度任務卸載，將一個任務隨機分割為多個具有依賴關系的子任務，每個子任務數據大小為200～400 KB，任務劃分后減少了計算復雜度和數據傳輸量，當將子任務部分卸載或者全部卸載至邊緣端時，可以有效地減少計算時延和傳輸時延。子任務1和6在本地設備執行，子任務2和4卸載至云端執行，子任務3和5卸載至邊緣服務器執行。

基站選擇函數由基站負載率k、終端設備i與基站j間的距離di，j、基站信號覆蓋范圍Cj和上一時刻子任務卸載到邊緣端開銷Hei決定，首次計算時給任務卸載到邊緣端的開銷賦初值Hi，其中，loadj表示基站j的負載，即分配給它的子任務數，m是子任務總數。

在實際的大城市中，終端設備與基站密度較大，此時基站選擇矩陣為滿陣（任務處理可選擇的基站較多），考慮終端設備的移動與基站負載率實時變化，蜂窩網絡覆蓋半徑較大，可以認為移動終端設備的位置在某個給定時隙是近似不動的，即移動終端設備選擇某一個基站進行任務處理。當基站接近滿載時，基站選擇函數近似于0，拒收任務且反饋給終端滿載信號，終端收到該滿載信號后將該基站選擇函數歸零并根據新的選擇矩陣重新選擇最優基站，此時基站滿載的選擇函數值保留至矩陣中，直到該基站處理完一個子任務才對矩陣進行更新，避免多次選擇接近滿載的矩陣。對于郊區、農村等設備密度低的地點，選擇矩陣稀疏且維度小，矩陣計算損耗小且時延低，仍然很實用。

2 動態感知—混合人工魚群算法

在進行任務卸載時，移動終端設備需要選擇邊緣服務器或云端進行子任務卸載，可將該過程視為不同的子任務去尋找自己的最優位置。基于此提出DP-HAFS算法，在此算法中要優化的目標函數即魚群生存空間的食物濃度，食物濃度越大，所引來此處覓食的人工魚越多，目標函數的解也越優。該策略的總體思路如圖3所示。

a）發現節點。首先對終端設備周圍可用邊緣節點進行選擇，對后續任務卸載做準備，其中邊緣節點包括位于網絡邊緣側的邊緣服務器和位于遠端云計算中心的云服務器。

b）任務分割。把待處理的任務分割成各個子任務，分割過程中盡量保持分割后子任務功能的完整性，以便進行卸載。

c）基站選擇。當終端設備被多個基站覆蓋時，根據基站選擇策略對基站進行選擇，基站選擇函數由距離、基站負載率和卸載開銷的折中計算決定。

d）運行算法。終端設備使用DP-HAFS算法解決卸載問題，對子任務進行卸載決策的選擇。

e）執行策略。當終端設備作出卸載決策后，將本地執行的子任務放在本地執行；邊緣端執行的子任務通過有線網絡上傳至邊緣服務器；云端執行的子任務通過無線網絡上傳至云服務器，執行完畢后再將各節點的計算結果傳回終端設備。

2.2 混合人工魚群算法

人工魚群算法在運行過程中存在較大隨機性，在避免陷入局部最優的同時降低了算法的收斂性。本文利用狼群算法的優點對人工魚群算法進行優化，狼群算法具有并行性，可以在同一時間從多個點出發進行搜索，以較大概率快速找到最優解。狼群算法模擬狼群的捕獵行為處理函數優化問題，各人工狼被視為所求問題的可行解，獵物氣味濃度被視為目標函數適應度值。狼群分為頭狼、探狼和猛狼，本文將人工魚也分為頭魚、探魚和猛魚，如圖4所示，其作用與狼群算法相同。在人工魚群進行覓食、聚群、追尾、隨機行為后進行狼群尋優行為，利用狼群算法對魚群個體進行更優個體的選擇。

3 仿真結果分析

為驗證基于DP-HAFS算法的任務卸載策略性能，采用本文提出的云—邊—端三層 MEC 計算卸載結構，將場景設置在120 m×120 m的正方形區域內，分布九個基站和一個云服務器。相關仿真參數如表1所示。

將本文DP-HAFS算法卸載策略與基于人工魚群算法的卸載策略、文獻[21]、任務完全在本地執行卸載策略、任務完全在最優邊緣端執行卸載策略及任務完全在云端執行卸載策略進行對比。本文方案中為綜合考量時延能耗指標，設置此時的時延與能耗之間的權重系數β=0.5。

產生任務的終端設備在區域內均勻分布，當任務增多時，仿真計算這六種控制策略的能耗如圖5所示。

圖5顯示了六種方案的系統總能耗與任務數量的關系。從圖中可以看出，當任務完全由終端設備處理時，任務處理能耗與任務數近似線性，當任務完全上傳到邊緣端或云端時，隨著任務處理的復雜性增加，可以看出能耗越來越大且比任務完全在終端處理要多。當采用人工魚群算法對任務進行自適應處理時，能耗介于邊緣端處理與云端處理之間，對比文獻[21]的結果，當任務數量較少時，由于各個方案資源豐富，本文方案無明顯優勢。隨著任務數量變大，設備間干擾變大，存在滿載設備，全部卸載到邊緣端或云端的能耗明顯增加，并且由于邊緣端計算過程中存在單位數據的附加能耗要大于終端處理能耗，所以本地處理任務的能耗要小于邊緣端處理任務的能耗。本文DP-HAFS算法對任務的尋優處理過程兼顧邊緣端與云端，與文獻[21]相比能耗也略有增加。

圖6顯示了六種方案的系統總時延與任務數量的關系。當任務數量較少時，設備間干擾較小，本地處理較有優勢。但隨著任務數量增加，上傳到邊緣端處理時，時延有所減少；同樣地，任務數量多時，上傳到云端最終比上傳到邊緣端更優。基于人工魚群算法對任務進行卸載時，時延比前面三種都要小。本文方案在時延方面與文獻[21]相比，在任務數量較少時時延會有增加，但與其他策略相比時延還是明顯減小，隨著任務數量增加，本文方案時延增加緩慢，優勢愈漸明顯。

系統總開銷與任務數量的關系如圖7所示，此時總開銷表示終端設備時延與能耗的綜合度量。以任務完全在本地執行時為基準值，可以看出，隨著任務數量的增大，任務完全在本地執行的總開銷標幺值恒為1。當任務數量增多，對比其他卸載策略，DP-HAFS算法的基站選擇策略在計算大量任務時有明顯優勢，在通信資源與計算資源有限的情況下更有效地降低了系統總開銷。

圖8顯示時延與能耗的權重參數β對系統總開銷的影響。權重參數β決定終端設備的優化偏好，當β接近于1時，系統更注重時延對總開銷的影響；當β接近于0時，系統則更關注能耗的優化。例如，當終端設備用于處理大量數據時，對時延要求不高，則β值可以設置為接近于0。從圖8可以看出，隨著β的增加，當任務數量增大時，總開銷增加的比率逐漸減小；且當任務數量不變時，隨著β的增加，系統總開銷顯著降低，這意味著調整β可以有效地控制優化系統總開銷，而本文策略更適用于時延敏感型場景。

圖9顯示迭代次數對系統總開銷的影響。取任務數量m=50，主要研究了迭代次數在[20，100]變化。從圖中可以看出隨著迭代次數的增加，系統總開銷呈下降趨勢，當迭代次數大于等于60時，各算法的系統總開銷趨于平穩，由此可以得出結論，當任務數量m=60時可以得到較優仿真結果。

4 結束語

本文提出本地—邊緣端—云端三層網絡架構，討論多終端設備—多服務器場景下的移動邊緣計算卸載問題。考慮具有優先約束關系的工作流建立移動服務模型，使用細粒度卸載，節省了計算時延和傳輸時延。對于終端設備被多個基站覆蓋的情況，提出基站選擇策略；然后提出了DP-HAFS算法，在經典人工魚群算法的基礎上加入狼群算法。仿真結果表明，本文方案在任務數量較多時有明顯優勢，能夠有效降低系統總開銷。接下來的工作中，在保持終端設備時延優勢的基礎上對能耗優化問題進行研究。

參考文獻：

［1］Wei Feng，Chen Sixuan，Zou Weixia.A greedy algorithm for task offloading in mobile edge computing system[J].China Communications，2018，15（11）：149-157.

[2]Shi Weisong，Cao Jie，Zhang Quan，et al.Edge computing：vision and challenges[J].IEEE Internet of Things Journal，2016，3（5）：637－646.

[3]王衛軍.高校圖書館移動信息服務模式創新研究[J].圖書館學研究，2014（17）：65-70.（Wang Weijun.Innovation of mobile information service in academic libraries[J].Research on Library Science，2014（17）：65-70.）

[4]Yang Guisong，Hou Ling，He Xingyu，et al.Offloading time optimization via Markov decision process in mobile-edge computing[J].IEEE Internet of Things Journal，2021，8（4）：2483－2493.

[5]Ma Xiao，Wang Shangguang，Zhang Shan，et al.Cost-efficient resource provisioning for dynamic requests in cloud assisted mobile edge computing[J].IEEE Trans on Cloud Computing，2021，9（3）：968－980.

[6]Ma Xiao，Zhou Ao，Zhang Shan，et al.Dynamic task scheduling in cloud-assisted mobile edge computing[J].IEEE Trans on Mobile Computing，2021，22（4）：2116-2130.

[7]Alfakih T，Hassan M M，Gumaei A，et al.Task offloading and resource allocation for mobile edge computing by deep reinforcement learning based on SARSA[J].IEEE Access，2020，8：54074－54084.

[8]Ge Yanhong，Wang Shubin，Jinyu Ma.Optimization on TEEN routing protocol in cognitive wireless sensor network[J].EURASIP Journal on Wireless Communications and Networking，2018，2018（2）：article No.27.

[9]Elgendy I A，Zhang Weizhe，Zeng Yiming，et al.Efficient and secure multi-user multi-task computation offloading for mobile-edge computing in mobile IoT networks[J].IEEE Trans on Network and Ser-vice Management，2020，17（4）：2410－2422.

[10]Li Bin，Fei Zesong，Shen Jian，et al.Dynamic offloading for energy harvesting mobile edge computing：architecture，case studies，and future directions[J].IEEE Access，2019，7：79877-79886.

[11]Lyu Xinchen，Tian Hui，Jiang Li，et al.Selective offloading in mobile edge computing for the green Internet of Things[J].IEEE Network，2018，32（1）：54－60.

[12]方加娟，李凱.基于邊緣云和移動輔助設備的計算卸載優化方案[J].計算機應用與軟件，2020，37（12）：6-12.（Fang Jiajuan，Li Kai.Optimal scheme of computation offloading based on edge cloud and mobile auxiliary equipment[J].Computer Applications and Software，2020，37（12）：6-12.）

[13]Chen Xianfu，Zhang Honggang，Wu Celimuge，et al.Optimized computation offloading performance in virtual edge computing systems via deep reinforcement learning[J].IEEE Internet of Things Journal，2019，6（3）：4005－4018.

[14]王妍，葛海波，馮安琪.云輔助移動邊緣計算中的計算卸載策略[J].計算機工程，2020，46（8）：27－34.（Wang Yan，Ge Haibo，Feng Anqi.Computation offloading strategy in cloud-assisted mobile edge computing[J].Computer Engineering，2020，46（8）：27－34.）

[15]Chen Jiawen，Yang Yajun，Wang Chenyang，et al.Multitask offloading strategy optimization based on directed acyclic graphs for edge computing[J].IEEE Internet of Things Journal，2022，9（12）：9367－9378.

[16]Ning Zhaolong，Dong Peiran，Kong Xiangjie，et al.A cooperative partial computation offloading scheme for mobile edge computing enabled Internet of Things[J].IEEE Internet of Things Journal，2019，6（3）：4804－4814.

[17]薛建彬，劉星星.基于PD-BPSO算法的計算卸載策略[J].傳感器與微系統，2020，39（11）：103-106.（Xue Jianbin，Liu Xingxing.Computation offloading strategy based on PD-BPSO algorithm[J].Transducer and Microsystem Technologies，2020，39（11）：103-106.）

[18]Guo Hongzhi，Liu Jiajia.Collaborative computation offloading for multi-access edge computing over fiber-wireless networks[J].IEEE Trans on Vehicular Technology，2018，67（5）：4514－4526.

[19]Zhao Fengjun，Chen Ying，Zhang Yongchao，et al.Dynamic offloading and resource scheduling for mobile-edge computing with energy harvesting devices[J].IEEE Trans on Network and Service Ma-nagement，2021，18（2）：2154－2165.

[20]Liao Zhuofan，Peng Jingsheng，Xiong Bing，et al.Adaptive offloading in mobile-edge computing for ultra-dense cellular networks based on genetic algorithm[J].Journal of Cloud Computing，2021，10（2）：article No.15.