移動邊緣計算中基于混合人工蜂群算法的計算卸載策略

摘要 計算卸載是移動邊緣計算（Mobile Edge Computing，MEC）中的關鍵技術．針對多用戶多MEC服務器場景中計算卸載策略的不足，本文提出一種混合人工蜂群算法（Artificial Reverse Sine-Cosine，ARSC）．首先，使用反向學習策略初始化種群，優化種群的初始解;然后，在雇傭蜂階段利用正余弦算法的全局最優引導信息，提升算法的局部搜索能力;最后，為了平衡算法的全局搜索能力和局部搜索能力，引入動態感知因子對算法的步長因子進行改進．仿真實驗結果表明，相比基于粒子群算法的卸載策略、基于人工蜂群算法的卸載策略，ARSC策略在系統時延、系統能耗、收斂性等指標上均有所改善．關鍵詞移動邊緣計算;計算卸載;人工蜂群算法;正余弦算法;多用戶多MEC

中圖分類號TN925.5；TP18

文獻標志碼A

0引言

近年來，隨著物聯網、云計算、大數據等技術的高速發展，用戶數據規模呈指數型增長．傳統的云計算模式需要上傳大量本地數據到云服務器，但由于云服務器部署離本地終端較遠，傳輸過程中的響應延遲、能量損耗、網絡干擾、數據安全等問題難以避免．為了解決云計算中心離終端設備較遠帶來的時延、能耗等問題，學者們提出將云的功能向網絡邊緣轉移［1］．在接近移動終端設備的網絡邊緣端，移動邊緣計算（Mobile Edge Computing，MEC）作為提供信息技術服務且具有計算能力的一種新型網絡結構和計算范式被提出．

邊緣計算并不是取代云計算，而是作為傳統云計算的延伸．它將部分數據處理和服務遷移到離用戶更近的網絡邊緣節點上，從而降低網絡延遲、提高用戶體驗和數據安全性．然而，移動設備仍然面臨著資源和能耗方面的限制，無法滿足一些復雜或者實時性要求高的任務［2］．因此，如何將這些計算任務卸載到邊緣服務器進行處理，成為邊緣計算中備受關注的關鍵技術．

國內外研究人員針對邊緣計算中的計算卸載進行了大量研究．文獻［3］將工業物聯網環境下的任務卸載問題建模為一個多用戶多邊緣服務器問題，使用粒子群算法（Particle Swarm Optimization，PSO）對任務進行卸載．文獻［4］針對多設備MEC系統中計算任務的執行時間以及終端設備的能耗最小化問題，構建了一個云服務器輔助的多MEC服務器計算卸載模型，并提出一種改進的人工蜂群算法（Artificial Bee Colony algorithm，ABC）．文獻［5］針對能量和頻譜資源稀缺的問題，提出一種基于差分進化算法（Differential Evolution，DE）的任務卸載方法，該方案考慮了能源站的發射功率和邊緣服務器的計算能力等約束條件，建立了無線能源供應的邊緣計算網絡模型．文獻［6］將工業生產線中的計算卸載問題建模為多用戶、多MEC時延優化問題，為了消除本地設備使用能耗來換取時延的問題，通過懲罰函數平衡時延與能耗，并提出一種基于粒子群算法優化的卸載策略．

任務卸載策略求解過程屬于NP難問題［7］，MEC研究中大多將其轉化為多因素優化問題．文獻［8］在物聯網場景下，使用遺傳算法作為任務卸載策略，顯著降低了設備的能耗和數據傳輸的時延．為了解決邊緣計算中任務卸載調度的優化問題，文獻［9］對蝙蝠群算法（BA）進行改進，提出一種改進混沌蝙蝠群協同卸載方法，該方案大大減少了任務完成的時延，從而滿足任務實時處理的需求．文獻［10］通過對模型中的三個目標分別進行歸一化，消除維度的影響，對模型進行了改進，并引入灰狼優化算法（GWO）求解模型．文獻［11］基于非正交多址的多址邊緣計算系統，研究了卸載決策、子信道分配、發射功率和計算資源分配的聯合優化問題，使用鯨魚群算法（WOA）解決了發射功率和子信道分配的問題．文獻［12］將多代理生成對抗模仿學習和馬爾可夫策略相結合以逼近專家性能，實現算法的在線執行，最后結合非支配排序遺傳算法Ⅱ（NSGA-Ⅱ），對時延和能耗進行聯合優化．

現有研究中的MEC卸載策略模型缺少對排隊等待時延的考慮，無法有效均衡邊緣服務器的計算資源．為了降低任務積壓在服務器中導致系統時延增加的影響，采用積壓隊列模型，以防止邊緣服務器中的任務隊列因積壓過多的計算任務導致系統總的時延增加，并針對多用戶多MEC系統卸載模型，提出一種混合人工蜂群算法（Artificial Reverse Sine-Cosine，ARSC）．ARSC使用反向學習策略對人工蜂群算法的初始化階段進行優化，并充分考慮正余弦算法收斂性強的優點，通過融合正余弦算法，提升算法的局部搜索能力．同時，引入動態感知因子改進算法的步長因子，進一步平衡算法的全局搜索能力和局部探索能力．

1系統模型

1.1時延模型

任務在不同的設備上執行有不同的時延模型：當任務在本地移動設備上執行，只需要考慮任務在移動設備上產生的計算時延;當任務被卸載到邊緣服務器上執行，需要考慮任務上傳的傳輸時延、服務器上的等待時延、計算時延、下傳的傳輸時延．因為下傳時延遠遠低于上傳時延，故本文不考慮下傳的傳輸時延．

1.1.1本地計算時延模型

1.1.2積壓隊列模型

邊緣服務器節點的計算能力是有限的，當一個服務節點中積壓大量計算任務時，會產生等待時延，從而導致系統時延的增加．為了有效利用邊緣服務器中的計算資源來減少等待時延，所以引入積壓隊列模型．當任務在邊緣服務器中的計算時延超過在本地計算時延時，邊緣服務器拒接卸載當前任務．邊緣節點中任務隊列的執行過程如圖2所示．

1.2能耗模型

1.3目標函數

2基于ARSC算法的卸載決策

2.1基本的人工蜂群算法

2.2混合人工蜂群算法

2.2.1反向學習策略

傳統的人工蜂群算法初始化蜜源位置采用隨機策略，而蜜源位置在解空間的分布直接影響算法的收斂速度和最終結果．為了改善蜜源位置，采用反向學習（Opposition-Based Learning，OBL）對初始解進行優化．反向學習［13］是一種優化策略，基本思想是通過計算當前解的反向解來擴大搜索范圍，以此來找出問題更好的解．

2.2.2正余弦策略

基本人工蜂群算法（ABC）及其搜索策略側重于提升全局搜索能力［14］，但由于ABC在每一代不直接使用全局最優信息，只是存儲其最優信息，導致其局部搜索能力較弱［15］．為了增強算法的局部搜索能力，在人工蜂群算法的雇傭蜂階段引入正余弦算法（Sine-Cosine Algorithm，SCA）［16］．這種方法通過采用正余弦算法中的全局最優解的引導信息來增強算法的局部搜索能力，利用正余弦算法的正余弦模型的振蕩特性來平衡探索與開發能力．混合人工蜂群算法的雇傭蜂階段蜜源位置更新策略為

2.2.3編碼和解碼

2.2.4算法偽代碼

3仿真結果分析

3.1仿真環境和參數

本文所有算法通過Python3實現，實驗環境為 Windows10 64 位操作系統，Intel Core i5-11400H CPU，16 GB內存．仿真用到的主要參數如表1所示．

3.2結果分析

根據表1的仿真參數進行實驗，本文采用本地卸載策略（LA）、隨機卸載策略（RA）、基于粒子群算法的卸載策略（PSO）、基于人工蜂群算法的卸載策略（ABC）、混合人工蜂群算法卸載策略（ARSC）來分析系統總的時延和能耗．

3.2.1不同任務數量下的能耗和時延

為了比較不同任務數量下的各卸載決策的能耗

和時延，本組實驗參數設置為任務數量分別為50、100、150、200、250，邊緣服務器數量設置為10個，任務的數據量為20 MB．實驗結果如圖4所示．由圖4可知，在不同任務數量下ARSC方法的時延和能耗都優于其他方法．在任務數量為250時，ARSC方法相較于本地卸載和隨機卸載分別降低51.3％、21.8％的時延和90.3％、47.2％的能耗;相較于ABC方法和PSO方法，在任務數量為250的則分別降低16.3％、16.6％的時延和11.9％、31.5％的能耗．由此可見，ARSC算法的局部搜索能力和全局搜索能力相較于ABC算法都得到了改善．

3.2.2各方法收斂性對比

為了比較ARSC、ABC、PSO三種算法的收斂性，設置任務數量為50，邊緣服務器數量為10，實驗結果如圖5所示．由圖5可知，ARSC算法有很強的全局搜索能力，在算法的前期不斷尋找全局最優解，且在后期擁有良好的局部搜索能力．在時延上，ARSC相較于ABC和PSO算法，分別降低6.4％和11.7％;在能耗上，ARSC算法相較于ABC算法和PSO算法，分別降低5.2％和6.6％．

3.2.3任務的等待時延分析

為了分析任務所需計算資源增多時，是否造成系統的等待時延增加．本組實驗參數設置任務數量為50，任務的數據量為20 MB，邊緣服務器的數量為10，任務所需資源量為1 、1.5、2、2.5和3 GHz．由圖6可知．當任務所需計算資源為0.5、1和1.5 GHz時，任務的等待時延在總的系統時延中所占比重較少，此時的邊緣服務器資源能夠滿足同時執行多個任務，所以系統總的時延增加較少．當任務所需的計算資源達到1.5 GHz以上時，等待時延在總的系統時延中占比較大，系統總的等待時延增加較多，此時的邊緣服務器資源不能同時滿足多個任務同時執行，造成統總的時延和等待時延的增加．ARSC卸載策略相比其他卸載策略總的等待時延最?。?/p>

3.2.4不同任務數據量下的時延和能耗

為了比較不同任務數據量下的各卸載決策的能耗和時延，本組實驗參數設置為任務數量為50，邊緣服務器數量設置為10個，任務的數據量分別7、14、21、28和35 MB．實驗結果如圖7所示．由圖7可知，隨著任務的數據量增加本地卸載策略的時延和能耗會快速增加，而基于ARSC方法的卸載策略的時延和能耗相對于其他方法都是最優的．在數據量為35 ""MB下，相較于LA、RA、PSO、ABC卸載策略，時延分別降低61.6％、19.1％、5.4％、2.5％，能耗分別降低66.1％、25.8％、8.8％、8.3％．

4結論

本文針對多用戶多MEC場景下計算卸載問題進行了研究．首先，將該場景下的計算卸載問題轉化為聯合時延和能耗最小化模型，并提出積壓隊列模型，防止邊緣服務器中積壓過多計算任務導致的系統總時延的增加．其次，提出一種混合人工蜂群算法卸載策略ARSC，該算法利用正余弦算法的全局最優引導信息提升人工蜂群算法的局部搜索能力，同時使用反向學習策略優化算法的初始階段，并引入動態感知因子進一步平衡算法的全局搜索能力和局部搜索能力．最后，對算法進行離散化處理，使其符合邊緣計算應用模型．通過實驗分析表明，ARSC算法相較于ABC、PSO算法，在系統時延、能耗、系統總的代價等指標上均有改善．

參考文獻

References

［1］MaoY Y，You C S，Zhang J，et al.A survey on mobile edge computing：the communication perspective［J］.IEEE Communications Surveys ＆ Tutorials，2017，19（4）：2322-2358

［2］董思岐，李海龍，屈毓錛，等.移動邊緣計算中的計算卸載策略研究綜述［J］.計算機科學，2019，46（11）：32-40DONG Siqi，LI Hailong，QU Yuben，et al.Survey of research on computation unloading strategy in mobile edge computing［J］.Computer Science，2019，46（11）：32-40

［3］LiangL，Xiao J T，Ren Z，et al.Particle swarm based service migration scheme in the edge computing environment［J］.IEEE Access，2020，8：45596-45606

［4］章呈瑞，柯鵬，尹梅.改進人工蜂群算法及其在邊緣計算卸載的應用［J］.計算機工程與應用，2022，58（7）：150-161ZHANG Chengrui，KE Peng，YIN Mei.Improved artificial bee colony algorithm and its application in edge computing offloading［J］.Computer Engineering and Applications，2022，58（7）：150-161

［5］Sun Y Y，Song C H，Yu S M，et al.Energy-efficient task offloading based on differential evolution in edge computing system with energy harvesting［J］.IEEE Access，2021，9：16383-16391

［6］羅斌，于波.移動邊緣計算中基于粒子群優化的計算卸載策略［J］.計算機應用，2020，40（8）：2293-2298LUO Bin，YU Bo.Computation offloading strategy based on particle swarm optimization in mobile edge computing［J］.Journal of Computer Applications，2020，40（8）：2293-2298

［7］Islam A，Debnath A，Ghose M，et al.A survey on task offloading in multi-access edge computing［J］.Journal of Systems Architecture，2021，118：102225

［8］AbbasiM，Mohammadi-Pasand E，Khosravi M R.Intelligent workload allocation in IoT-fog-cloud architecture towards mobile edge computing［J］.Computer Communications，2021，169：71-80

［9］簡琤峰，陳家煒，張美玉.面向邊緣計算的改進混沌蝙蝠群協同調度算法［J］.小型微型計算機系統，2019，40（11）：2424-2430JIAN Chengfeng，CHEN Jiawei，ZHANG Meiyu.Improved chaotic bat swarm cooperative scheduling algorithm for edge computing［J］.Journal of Chinese Computer Systems，2019，40（11）：2424-2430

［10］Feng S L，Chen Y J，Zhai Q H，et al.Optimizing computation offloading strategy in mobile edge computing based on swarm intelligence algorithms［J］.EURASIP Journal on Advances in Signal Processing，2021，2021（1）：1-15

［11］Pham H G T，Pham Q V，Pham A T，et al.Joint task offloading and resource management in NOMA-based MEC systems：a swarm intelligence approach［J］.IEEE Access，2020，8：190463-190474

［12］劉建華，李煒，劉佳嘉，等.基于多代理模仿學習的普適邊緣計算資源分配［J］.南京信息工程大學學報，2024，16（1）：83-96LIU Jianhua，LI Wei，LIU Jiajia，et al.Resource allocation for pervasive edge computing based on multi-agent imitation learning［J］.Journal of Nanjing University of Information Science ＆ Technology，2024，16（1）：83-96

［13］TizhooshH R.Opposition-based learning：a new scheme for machine intelligence［C］／／International Conference on Computational Intelligence for Modelling，Control and Automation and International Conference on Intelligent Agents，Web Technologies and Internet Commerce.November 28-30，2005，Vienna，Austria.IEEE，2006：695-701

［14］匡芳君，金忠，徐蔚鴻，等.Tent混沌人工蜂群與粒子群混合算法［J］.控制與決策，2015，30（5）：839-847KUANG Fangjun，JIN Zhong，XU Weihong，et al.Hybridization algorithm of Tent chaos artificial bee colony and particle swarm optimization［J］.Control and Decision，2015，30（5）：839-847

［15］Alatas B.Chaotic bee colony algorithms for global numerical optimization［J］.Expert Systems with Applications，2010，37（8）：5682-5687

［16］Mirjalili S.SCA：a sine cosine algorithm for solving optimization problems［J］.Knowledge-Based Systems，2016，96：120-133

［17］雍龍泉，黎延海，賈偉.正弦余弦算法的研究及應用綜述［J］.計算機工程與應用，2020，56（14）：26-34YONG Longquan，LI Yanhai，JIA Wei.Literature survey on research and application of sine cosine algorithm［J］.Computer Engineering and Applications，2020，56（14）：26-34

Computational offloading strategy based on hybrid artificial bee colony algorithm in mobile edge computing

SHEN Zhenglin WU Tao ZHOU Qizhao CHEN Xi

1School of Computer Science，Chengdu University of Information Technology，Chengdu 610225，China

2School of Computer Science and Technology，Southwest Minzu University，Chengdu 610225，China

AbstractComputational offloading is an essential technology in Mobile Edge Computing （MEC）.To address the shortage of computational offloading strategies in multi-user and multi-MEC server scenarios，this paper proposes a hybrid artificial bee colony approach （Artificial Reverse Sine-Cosine，ARSC）.First，the opposition-based learning strategy is used to initialize the population and optimize the initial solution of the population.Then the global optimal bootstrap information of the sine-cosine algorithm is exploited to improve the local search capability in the employed bee stage.Finally，to balance the global and local search capability of the approach，the step size factor is adapted by introducing dynamic perception.Simulation results show that the proposed ARSC approach outperforms offloading strategies based on particle swarm algorithm and artificial bee colony algorithm in convergence，latency，and energy consumption.

Key wordsmobile edge computing（MEC）;computation offloading;artificial bee colony algorithm;sine-cosine algorithm;multi-user and multi-MEC server