多用戶動態節能資源競爭計算卸載策略

摘 要： 針對移動邊緣計算環境下，移動設備的計算、續航、存儲能力的不足，導致其響應延遲、電池壽命降低等問題，設計了一種動態節能資源競爭計算卸載（DERCO）策略。該策略綜合考慮了信道容量以及設備間的相互干擾等情況，以一種貪婪算法的思想，讓所有邊緣設備通過迭代競爭信道資源，節能效果最好的設備將獲得卸載機會，再利用一次性卸載方法，根據實時的信道狀況和卸載速率進行動態的細粒度子任務卸載決策。實驗結果表明，該策略優于一種近似協同計算卸載方案，有效降低了設備的能耗與時延。

關鍵詞： 移動邊緣計算； 卸載策略； 能耗優化； 降低時延

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

文章編號： 1001-3695（2022）05-041-1524-05

doi：10.19734/j.issn.1001-3695.2021.10.0436

Multi-user dynamic energy-saving resource competition computing offloading strategy

Fang Yuchao， Mei Hongyan， Zhou Jun， Zhang Xing

（School of Electronics amp; Information Engineering， Liaoning University of Technology， Jinzhou Liaoning 121001， China）

Abstract： In the mobile edge computing environment， the lack of computing， battery life， and storage capabilities of mobile devices lead to problems such as delayed response and reduced battery life. This paper designed a dynamic energy-saving resource competition computing offloading （DERCO） strategy to minimize the total energy consumption of all equipment. This strategy comprehensively considered the channel capacity and mutual interference between devices， and used the idea of a greedy algorithm to allow all edge devices to iteratively compete for channel resources. The device with the best energy-saving effect would get the opportunity to offload， and then used the one climb policy offloading method based on real-time channel conditions and offloading rate to make dynamic and fine-grained subtask unloading decisions. Experimental results show that this strategy is better than an approximate collaborative computing offloading scheme， which effectively reduces the energy consumption and time delay of the equipment.

Key words： mobile edge computing; offloading strategy; energy consumption optimization; reducing latency

0 引言

隨著互聯網技術的飛速發展以及物聯網設備的普及，智能手機、筆記本電腦等移動設備的技術發展與新型移動應用程序的發展齊頭并進［1］，使邊緣設備產生的數據量呈爆炸式增長，導致云中心的計算壓力過大，而邊緣設備計算能力有限，這將導致執行任務的響應延遲、能耗增加，極大地影響用戶體驗。計算卸載是邊緣計算的關鍵技術，通過將任務轉移到邊緣服務器或云，被視為解決物聯網設備計算能力不足的方案。這種技術可以帶來許多好處，例如延長電池壽命、減少延遲和提高應用程序性能［2］。例如，應用移動邊緣計算卸載技術的車載網絡可以滿足車輛對服務延時和通信可靠性的嚴格要求，提升車輛用戶的服務質量［3］。

邊緣計算的計算范式要求在網絡邊緣處理數據，有望解決響應時間要求、電池壽命限制、帶寬成本節約以及數據安全和隱私等問題［4］。而移動邊緣計算（MEC）的概念最早于2013年被提出［5］，此后隨著物聯網技術的發展以及移動設備數量的激增迅速推動了移動邊緣計算的發展，近年，移動邊緣計算更是作為5G的一項關鍵技術被提出［6，7］，被廣泛認為是解決物聯網設備計算能力有限和通信問題的較為有前途的技術［8～10］。

移動邊緣計算卸載策略需要考慮許多實際因素，例如邊緣設備的異構性，不同的邊緣設備具有不同的計算能力，且設備與基站的距離遠近會影響傳輸速率，尤其是移動設備的卸載需要考慮更復雜的情況［11］。網絡條件也是影響計算卸載的重要因素［12］，網絡的帶寬和來自其他設備的干擾等都會嚴重影響卸載效率，如果設備與服務器互連受到各種因素干擾會導致卸載時延過長［13］。邊緣服務器的性能也是計算卸載的決定性因素，服務器的計算能力將決定執行任務的效率，它的發送功率將決定把數據回傳到設備的時間，性能更高的邊緣服務器會有更好的卸載效果。

卸載策略需要在考慮諸多影響因素的情況下制定，卸載策略是否有效取決于各種衡量指標，比如能耗、時延，或者聯合優化兩個指標。Yang等人［14］提出了一種基于勢博弈論的分布式算法（PGOA），聯合優化了時延與能耗。同樣是基于博弈論，Guo等人［15］提出了一種博弈論協同計算卸載方案（GT-CCO）和一種近似協同計算卸載方案（ACCO），以達到總能耗最低。以上兩種基于博弈論的卸載策略都屬于完全卸載策略。對于基于博弈論的部分卸載策略，Shu等人［16］提出了一種分布式最早完成時間卸載方案（DEFO），以減少端到端任務的執行時間，提高邊緣服務器的資源利用率。在降低能耗方面，Zhao等人［17］提出了一種基于分支定界的重構線性化技術方法（RLTBB），以達到最低能耗。同樣是對能耗進行優化，Chen等人［18］基于李雅普諾夫隨機優化理論，提出一種高效節能的動態卸載算法（EEDOA），在保證平均隊列長度的同時最小化卸載能耗。對于部分卸載策略，Wu等人［19］提出了一種最小成本卸載分區算法（MCOP），在不同的成本模型和移動環境下找到應用程序的最優分區方案，以減少執行時間和能耗。Liu等人［20］采用馬爾可夫決策過程方法，通過分析每個任務的平均延遲和移動設備的平均功耗，提出了一個功率受限的延遲最小化問題，并提出了一種一維搜索算法來尋找最優的任務調度策略，與基線策略相比，該策略能夠獲得更短的平均執行延遲。

除了以能耗、時延等作為衡量指標的卸載策略，還有一類基于拍賣理論，注重計算資源分配的卸載方案。Zhang等人［21］基于拍賣理論提出了一種多輪密封順序組合拍賣（MSSCA）機制，以達到更好的系統性能。Jin等人［22］提出了一種激勵相容拍賣機制（ICAM），可以分配云服務器資源以滿足移動設備的服務需求，保證個體理性、預算平衡、真實性（激勵相容性）以及計算效率等方面的期望屬性。Sun等人［23］提出了基于盈虧平衡的雙拍賣算法（BDA）和基于動態定價的雙拍賣算法（DPDA）兩種具有動態定價的雙拍賣方案，以提高移動邊緣計算的系統效率。盛津芳等人［24］綜合考慮智能設備性能和服務器資源，提出了一種基于改進拍賣算法的計算卸載策略，以達到降低服務時延、減少智能設備能耗、改善用戶體驗的目的。

本文基于多用戶單服務器的網絡架構，綜合考慮了信道條件限制、用戶間的相互干擾以及用戶與接入點距離等因素，以一種貪婪算法的思想最大化節能收益，具體是讓所有邊緣設備通過迭代競爭信道資源，節能收益最好的設備將獲得卸載機會，再利用一次性卸載方法，根據實時的信道狀況和卸載速率進行動態的細粒度子任務卸載決策，以一種輕量級算法在限制時延與能耗的同時降低所有設備的總能耗。

1 系統模型

本文模型建立在多用戶單服務器場景下，網絡架構模型如圖1所示。各種異構的邊緣設備連接到無線基站，邊緣服務器在無線基站附近為用戶提供計算資源，將得到的分析和計算結果回傳到邊緣設備和推送到云存儲庫中。用戶可以自由選擇滿足接入條件的接入點，接入點有唯一對應的邊緣服務器，一般認為每個用戶確定了接入點就不能同時再去連接其他的接入點，基于該模型，本文考慮的問題是如何最大程度地降低所有設備總能耗。

在本文考慮的移動邊緣計算系統中，其中M={1，2，…，m}代表m個邊緣設備，V={V1，V2，…，Vm}代表設備子任務數，其中Vi代表第i個邊緣設備的子任務數，Ai={ai，1，ai，2，…，ai，vi}代表任務卸載決策，ai，j代表設備i的j個子任務的卸載決策，且ai，j∈{0，1}，當子任務選擇在本地執行時ai，j為0，選擇在邊緣服務器執行時ai，j為1。本文考慮的子任務依賴關系為，每一個子任務的輸入依賴于前一個任務的輸出，除起始任務和終止任務，每一個子任務都有唯一的前驅子任務和后繼子任務，執行時須嚴格按照依賴關系的順序。

3 實驗結果及分析

本文使用Python 3.9模擬DERCO卸載策略，實驗參數設置如下：實驗分別設置了3和5兩種子任務數的設備，每個邊緣設備子任務負載在10～200 Mcycles內隨機產生，每個子任務對應的輸出數據大小設定在1 000～2 000 KB，邊緣設備的發送功率為0.1 W，邊緣服務器和邊緣設備的計算能力分別為1010 cycles/s 和108 cycles/s，信道噪聲功率σ2=10－10 W，以上參數設置與文獻［26］一致，信道帶寬設為20 MHz與文獻［16］一致，此外將邊緣設備的計算效率參數設置為k=10－25，實驗將設備設定在與基站的距離為10～110 m內均勻分布，信道容量設定為最多容納70個邊緣設備。

實驗中除了本文DERCO卸載策略以外，還采用了ACCO［15］算法和兩種基線方案，即所有設備任務分別在本地執行和在邊緣服務器執行，分別對比了四種方案在不同用戶規模下的總能耗、不同任務數量下的總能耗、不同用戶數量下的總執行時間，并分析了迭代次數對設備總能耗的影響。

3.1 不同執行策略下的能耗對比

圖4、5分別展示了四種執行方案在不同用戶規模下和不同任務數量下的設備能耗。從圖4可以看出，在不同設備數量規模下，相對于ACCO算法，DERCO算法的節能效果更好，這是因為DERCO算法是根據信道條件和卸載速率實時動態地進行部分卸載決策，且采用貪婪算法的思想選擇節能效果好的設備進行卸載執行。相對于在本地執行DERCO算法至少節省50%的能耗，而且如果設備數在不超過信道容量所能容納最大設備數的情況下更是節省近60%的總能耗。對于所有設備任務都卸載到服務器執行的情況，在設備數較少時有明顯的節能效果，但是隨著設備數增多導致卸載速率下降，總能耗迅速增加甚至超過本地執行的能耗。

為了更加直觀地分析DERCO算法的節能效果，本文對在不同任務數量下的能耗進行了分析。從圖5可以看出，隨著任務數量的增加，DERCO算法在降低能耗的效果上優于ACCO算法，且能耗曲線相對平滑穩定，這是因為每一輪迭代都會在設備集選擇一個卸載后節能效果最好的設備執行計算卸載，使獲得卸載資格的設備執行能耗不會相差過多，所以隨著任務數的增加，總能耗也不會有明顯的增幅。相較于本地執行和全部卸載執行，DERCO在節能方面有著明顯的優勢。隨著任務數的增加，也就是隨著邊緣設備數的增加，全部卸載執行的能耗曲線斜率明顯增大，這是由于卸載設備之間的相互干擾導致卸載速率下降，卸載能耗大幅增加。

3.2 不同執行策略下的執行時間對比

節省能耗對于延長移動設備電池壽命和待機時長起到重要作用，而降低時延改善用戶體驗也是卸載策略的重點，圖6展示了不同用戶數量下所有設備任務的執行時間。從圖中可以看出，DERCO算法有效地降低了時延，不僅略優于ACCO算法，相對于本地執行更是節省近50%的總執行時間，這是因為DERCO算法以貪婪算法思想結合一次性卸載方法在節能的同時還優化了執行時間。全部卸載到服務器執行的方案雖然在設備數量少的情況明顯降低了時延，但是隨著設備數的增加導致卸載速率下降，總執行時間大幅增加，甚至超過在本地執行。

3.3 迭代次數對能耗的影響

圖7展示了DERCO算法通過有限次迭代降低了所有設備的總能耗，在算法開始時，所有設備都在本地執行，每一次迭代都會角逐出一個優勝設備獲得卸載權利和信道資源，隨著迭代次數的增加，越來越多的邊緣設備通過卸載任務到邊緣服務器，使得總能耗大幅降低。從圖中可以看出，當迭代次數接近信道容量時，總能耗已經達到最低，不再變化，這是由于其他設備對信道造成干擾，使卸載速率大幅下降，如果設備選擇卸載任務，其傳輸能耗已經大于在本地執行的能耗，所以在迭代次數接近信道容量所能容納的設備數量以后，剩余設備都會選擇在本地執行，此時繼續迭代總能耗也不會再變化。

4 結束語

由于越來越多的延遲敏感型應用程序的出現，移動設備的計算、續航、存儲能力的不足，導致其響應延遲、電池壽命降低。針對上述問題，本文設計了一種動態節能資源競爭計算卸載（DERCO）策略。通過讓所有邊緣設備迭代競爭信道資源，使節能收益最大化，再利用一次性卸載方法，根據實時的信道狀況和卸載速率進行動態的細粒度子任務卸載決策，同時優化時延與能耗。通過大量實驗證明，DERCO算法優于一種近似協同計算卸載方案和兩種基線卸載方案，有效降低了所有設備總能耗和總執行時間。接下來的工作方向是考慮在多用戶多服務器的場景下，對能耗和時延進行聯合優化。

參考文獻：

[1]Mach P， Becvar Z. Mobile edge computing： a survey on architecture and computation offloading［J］.IEEE Communications Surveys amp; Tutorials，2017，19（3）：1628-1656.

［2]Zheng Tao， Wan Jian， Zhang Jilin， et al. A survey of computation offloading in edge computing［C］//Proc of International Conference on Computer， Information and Telecommunication Systems.Pisca-taway，NJ：IEEE Press，2020：1-6.

［3]谷曉會，章國安.移動邊緣計算在車載網中的應用綜述［J］.計算機應用研究，2020，37（6）：1615-1621.（Gu Xiaohui， Zhang Guoan. Survey of mobile edge computing applications in vehicular network［J］.Application Research of Computers，2020，37（6）：1615-1621.）

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

［5]Barbarossa S， Sardellitti S， Di Lorenzo P. Communicating while computing： distributed mobile cloud computing over 5G heterogeneous networks［J］.IEEE Signal Processing Magazine，2014，31（6）：45-55.

［6]Hu Y C， Patel M， Sabella D， et al. Mobile edge computing a key technology towards 5G［J］.ETSI White Paper，2015，11（11）：1-16.

［7]Wang Shuo， Zhang Xing， Zhang Yan， et al. A survey on mobile edge networks： convergence of computing， caching and communications［J］.IEEE Access，2017，5：6757-6779.

［8]Dinh H T， Lee C， Niyato D， et al. A survey of mobile cloud computing： architecture， applications， and approaches［J］.Wireless Communications and Mobile Computing，2013，13（18）：1587-1611.

［9]Lyu Xinchen， Tian Hui， Sengul C， et al. Multiuser joint task offloa-ding and resource optimization in proximate clouds［J］.IEEE Trans on Vehicular Technology，2016，66（4）：3435-3447.

［10]Fan Qilin， Yin Hao， Jiao Libo， et al. Towards optimal request mapping and response routing for content delivery networks［J］.IEEE Trans on Services Computing，2018，14（2）：606-613.

［11]Yang Chao， Liu Yi， Chen Xin， et al. Efficient mobility-aware task offloading for vehicular edge computing networks［J］.IEEE Access，2019，7：26652-26664.

［12]Huang Dong， Wang Ping， Niyato D. A dynamic offloading algorithm for mobile computing［J］.IEEE Trans on Wireless Communications，2012，11（6）：1991-1995.

［13]Khan M A. A survey of computation offloading strategies for perfor-mance improvement of applications running on mobile devices［J］.Journal of Network and Computer Applications，2015，56：28-40.

［14]Yang Lichao， Zhang Heli， Li Xi， et al. A distributed computation offloading strategy in small-cell networks integrated with mobile edge computing［J］.IEEE/ACM Trans on Networking， 2018，26（6）：2762-2773.

［15]Guo Hongzhi， Liu Jiajia. Collaborative computation offloading for multiaccess edge computing over fiber-wire-less networks［J］.IEEE Trans on Vehicular Technology，2018，67（5）：4514-4526.

［16]Shu Chang， Zhao Zhiwei， Han Yunpeng， et al. Multi-user offloading for edge computing networks： a dependency-aware and latency-optimal approach［J］.IEEE Internet of Things Journal，2019，7（3）：1678-1689.

［17]Zhao Pengtao， Tian Hui， Qin Cheng， et al. Energy-saving offloading by jointly allocating radio and computational resources for mobile edge computing［J］.IEEE Access，2017，5：11255-11268.

［18]Chen Ying， Zhang Ning， Zhang Yongchao， et al. Energy efficient dynamic offloading in mobile edge computing for Internet of Things［J］.IEEE Trans on Cloud Computing，2021，9（3）：1050-1060.

［19]Wu Huaming， Knottenbelt W J， Wolter K. An efficient application partitioning algorithm in mobile environments［J］.IEEE Trans on Parallel and Distributed Systems，2019，30（7）：1464-1480.

［20]Liu Juan， Mao Yuyi， Zhang Jun， et al. Delay-optimal computation task scheduling for mobile-edge computing systems［C］//Proc of IEEE International Symposium on Information Theory. Piscataway，NJ：IEEE Press，2016：1451-1455.

［21]Zhang Heli， Guo Fengxian， Ji Hong， et al. Combinational auction-based service provider selection in mobile edge computing networks［J］.IEEE Access，2017，5：13455-13464.

［22]Jin Along， Song Wei， Zhuang Weihua. Auction-based resource allocation for sharing cloudlets in mobile cloud computing［J］.IEEE Trans on Emerging Topics in Computing，2015，6（1）：45-57.

［23]Sun Wen， Liu Jiajia， Yue Yanlin， et al. Double auction-based resource allocation for mobile edge computing in industrial Internet of Things［J］.IEEE Trans on Industrial Informatics，2018，14（10）：4692-4701.

［24]盛津芳，滕瀟雨，李偉民，等.移動邊緣計算中基于改進拍賣模型的計算卸載策略［J］.計算機應用研究，2020，37（6）：1688-1692.（Sheng Jinfang， Teng Xiaoyu， Li Weimin， et al. Computational offloading strategy based on improved auction model in mobile edge computing［J］.Application Research of Computers，2020，37（6）：1688-1692.）

［25]Cheng Kang， Teng Yinglei， Sun Weiqi， et al. Energy-efficient joint offloading and wireless resource allocation strategy in multi-mec server systems［C］//Proc of IEEE International Conference on Communications. Piscataway，NJ：IEEE Press，2018：1-6.

［26]Yan Jia， Bi Suzhi， Zhang Yingjun， et al. Optimal task offloading and resource allocation in mobile-edge computing with inter-user task dependency［J］.IEEE Trans on Wireless Communications，2019，19（1）：235-250.