移動(dòng)邊緣計(jì)算中基于粒子群優(yōu)化的計(jì)算卸載策略

羅 斌 ，于 波

（1. 中國(guó)科學(xué)院大學(xué)，北京100049； 2. 中國(guó)科學(xué)院沈陽(yáng)計(jì)算技術(shù)研究所，沈陽(yáng)110168）

0 引言

5G 具有近鄰性、低延遲、高帶寬等特性，作為關(guān)鍵技術(shù)的移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）也逐漸成熟。MEC將無(wú)線網(wǎng)絡(luò)和互聯(lián)網(wǎng)技術(shù)融合在一起，工業(yè)作為5G的一個(gè)應(yīng)用方向，可以將MEC 應(yīng)用于現(xiàn)場(chǎng)設(shè)備實(shí)時(shí)控制、遠(yuǎn)程維護(hù)及操控、工業(yè)圖像處理等方面［1］。任務(wù)計(jì)算量的提升導(dǎo)致本地設(shè)備自身無(wú)法處理相應(yīng)的計(jì)算任務(wù)，而云計(jì)算的提出則很好地解決了算力不足的問題；但是云計(jì)算也帶來(lái)了數(shù)據(jù)傳輸成本、云存儲(chǔ)花費(fèi)、互聯(lián)網(wǎng)訪問管理和安全性等一系列問題［2］。MEC 將端云架構(gòu)轉(zhuǎn)變?yōu)槎诉呍萍軜?gòu)，在一定程度上降低了時(shí)延，并通過(guò)合理的計(jì)算卸載策略提高了計(jì)算任務(wù)的吞吐量，能更好地滿足用戶體驗(yàn)質(zhì)量需求，使經(jīng)濟(jì)利益最大化。計(jì)算卸載作為MEC 的研究方向之一，自2014 年提出以來(lái)，工業(yè)界與學(xué)術(shù)界已經(jīng)對(duì)其進(jìn)行了大量的研究。目前的卸載策略控制方式主要是集中式控制與分布式協(xié)作控制，在建模場(chǎng)景方面主要包括單用戶單MEC、多用戶單MEC 和多用戶多MEC，優(yōu)化目標(biāo)主要包括能耗約束條件下最小化時(shí)延、時(shí)延約束下最小化能耗以及平衡能耗與時(shí)延的卸載策略。目前研究的問題大部分是對(duì)于通用場(chǎng)景下的問題建模，針對(duì)工業(yè)場(chǎng)景下計(jì)算卸載策略的研究比較少?？紤]工業(yè)生產(chǎn)線中實(shí)際的卸載條件，工業(yè)場(chǎng)景相較于通用場(chǎng)景下的計(jì)算卸載策略存在以下不同：1）工業(yè)場(chǎng)景下接入MEC 服務(wù)器的設(shè)備數(shù)目多，需要考慮一種總體最優(yōu)的策略；2）工業(yè)場(chǎng)景下對(duì)于時(shí)延特性的要求會(huì)更加嚴(yán)格，主要關(guān)注如何最小化時(shí)延；3）工業(yè)場(chǎng)景下MEC 服務(wù)器會(huì)處理大量特定（圖像識(shí)別、設(shè)備控制等）的任務(wù)，需要選擇合適的計(jì)算模型以及通信方式。

本文主要考慮了工業(yè)生產(chǎn)線中的計(jì)算卸載策略，在多用戶多MEC 場(chǎng)景下，研究在能耗約束條件下時(shí)延最小化的問題，通過(guò)集中控制卸載高計(jì)算量的任務(wù)到MEC 服務(wù)器。工業(yè)生產(chǎn)線中可以降低傳輸能耗與計(jì)算能耗，選擇合適的通信方式以及數(shù)據(jù)壓縮來(lái)降低傳輸能耗［3］；通過(guò)提高M(jìn)EC 服務(wù)器的處理性能來(lái)降低計(jì)算能耗。當(dāng)前卸載策略應(yīng)用場(chǎng)景是通過(guò)虛擬現(xiàn)實(shí)（Virtual Reality，VR）眼鏡來(lái)實(shí)時(shí)識(shí)別和控制工業(yè)生產(chǎn)線中的設(shè)備，對(duì)于時(shí)延要求較高，因此選擇最小化時(shí)延的卸載策略。具體的工作如下：

1）為工業(yè)場(chǎng)景構(gòu)造時(shí)延模型與能耗模型，在MEC 系統(tǒng)中將計(jì)算卸載問題轉(zhuǎn)化為時(shí)延最小化時(shí)延模型，其中能耗模型作為約束條件；

2）提出通過(guò)智能優(yōu)化算法中的粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法來(lái)解決最小化問題，對(duì)于離散粒子群算法進(jìn)行了一定修改來(lái)適應(yīng)問題；

3）通過(guò)仿真實(shí)驗(yàn)表明完全本地卸載策略與MEC 基準(zhǔn)卸載策略都存在各自的優(yōu)缺點(diǎn)，而本文提出的基于PSO 算法的計(jì)算卸載策略PSAO 能夠在能耗與時(shí)延上達(dá)到相對(duì)平衡，基于人工魚群算法（Artificial Fish Swarm Algorithm，AFSA）的卸載方案前期優(yōu)化效果與PSAO 相差不大，但當(dāng)設(shè)備數(shù)過(guò)多或者任務(wù)量過(guò)大時(shí)，魚群卸載策略遠(yuǎn)不如PSAO卸載策略。

1 相關(guān)工作

歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)（European Telecommunications Standards Institute，ETSI）提出了移動(dòng)邊緣計(jì)算（MEC）的概念，該概念將邊緣計(jì)算集成到移動(dòng)網(wǎng)絡(luò)架構(gòu)中［4］。2016年在原有的網(wǎng)絡(luò)基礎(chǔ)上接入了Wi-Fi，將MEC 的中文解釋修改為“多接入邊緣計(jì)算”。計(jì)算卸載是MEC中重要的研究方向，主要包含卸載決策和資源分配，本文主要關(guān)注計(jì)算卸載決策，也就是研究用戶中要不要卸載、卸載什么和卸載到哪里的問題［5］。文獻(xiàn)［6］中提出了動(dòng)態(tài)卸載方案，將卸載任務(wù)看作是兩級(jí)隨機(jī)優(yōu)化問題，通過(guò)任務(wù)排隊(duì)模型，由移動(dòng)設(shè)備來(lái)決定任務(wù)在本地執(zhí)行還是在MEC 服務(wù)器上執(zhí)行，采用馬爾可夫決策過(guò)程來(lái)處理該問題，提出一種有效的一位搜索算法來(lái)解決功率受限的時(shí)延問題。文獻(xiàn)［7］中以時(shí)延為優(yōu)化目標(biāo)，在文獻(xiàn)［6］的基礎(chǔ)上提出了自帶能量收集的MEC系統(tǒng)，選擇在線計(jì)算卸載策略，卸載過(guò)程中考慮了數(shù)據(jù)在信道中傳遞與CPU 上計(jì)算的各個(gè)因素，使用Lyapunov 優(yōu)化來(lái)得到最優(yōu)解。文獻(xiàn)［6-7］雖然對(duì)于單個(gè)任務(wù)卸載到MEC 問題給出了解決方案，但是在工業(yè)生產(chǎn)線中往往有成百上千個(gè)移動(dòng)設(shè)備和傳感器需卸載任務(wù)，此時(shí)需要分布式的策略來(lái)進(jìn)行卸載。文獻(xiàn)［8］中從另一方面來(lái)考慮卸載任務(wù)，主要是針對(duì)一系列具有順序關(guān)系的任務(wù)，通過(guò)拓?fù)鋱D的優(yōu)化方式來(lái)卸載，使用負(fù)載平衡試探法將任務(wù)卸載到MEC中，最大限度提高移動(dòng)設(shè)備與云之間的并行性。其他研究中也提出了通過(guò)匈牙利算法來(lái)解決一些非順序的任務(wù)，一般是需要本地設(shè)備進(jìn)行初步處理，MEC 完成后續(xù)高計(jì)算量的任務(wù)［9］，在移動(dòng)設(shè)備與云之間的并行方面也提供了新的思路。文獻(xiàn)［10-11］中將多用戶多MEC 場(chǎng)景建模為時(shí)延約束條件下的能量?jī)?yōu)化問題，通過(guò)AFSA來(lái)求解決策向量。文獻(xiàn)［12］中基于云計(jì)算提出了一種快速混合多站點(diǎn)計(jì)算卸載解決方案，可根據(jù)移動(dòng)應(yīng)用程序的大小實(shí)現(xiàn)最佳和接近最優(yōu)的卸載分區(qū)，當(dāng)規(guī)模擴(kuò)大時(shí)提出使用粒子群優(yōu)化（PSO）的優(yōu)化版本來(lái)獲得非常合適的卸載優(yōu)化解決方案。文獻(xiàn)［13］中結(jié)合人工智能技術(shù)，基于長(zhǎng)短期記憶（Long Short-Term Memory，LSTM）網(wǎng)絡(luò)預(yù)測(cè)計(jì)算任務(wù)，提出基于任務(wù)預(yù)測(cè)的移動(dòng)設(shè)備計(jì)算卸載策略。目前各個(gè)技術(shù)趨向于相互融合來(lái)達(dá)到更優(yōu)的結(jié)果，通過(guò)神經(jīng)網(wǎng)絡(luò)或者機(jī)器學(xué)習(xí)來(lái)輔助優(yōu)化邊緣計(jì)算卸載模型。文獻(xiàn)［14］中對(duì)近幾年關(guān)于計(jì)算卸載策略的研究做了匯總，主要根據(jù)計(jì)算卸載的卸載類型、優(yōu)化目標(biāo)提出解決方案、場(chǎng)景、評(píng)估方式進(jìn)行分類總結(jié)。MEC未來(lái)可能的應(yīng)用方向主要集中在動(dòng)態(tài)內(nèi)容優(yōu)化、物聯(lián)網(wǎng)、移動(dòng)大數(shù)據(jù)分析和智能交通［15］。

結(jié)合以上的研究不難發(fā)現(xiàn)，雖然上述研究提出的系統(tǒng)或者算法在能耗和時(shí)延優(yōu)化方面都有著較優(yōu)的性能，但是都很難符合工業(yè)生產(chǎn)線場(chǎng)景下的計(jì)算卸載低時(shí)延目標(biāo)，其中文獻(xiàn)［12］中提出的快速混合多站點(diǎn)計(jì)算卸載能夠適應(yīng)工業(yè)場(chǎng)景，但是由于云計(jì)算帶來(lái)的成本問題以及傳輸時(shí)延增高等一系列問題，需要提出一種符合多用戶多MEC場(chǎng)景下，在能耗約束的條件下時(shí)延最小化的完全卸載策略。

2 系統(tǒng)模型

MEC 系統(tǒng)的部署場(chǎng)景如圖1 所示，MEC 服務(wù)器主要面向時(shí)延敏感型和計(jì)算量巨大的任務(wù)，核心任務(wù)包含工業(yè)設(shè)備的控制與工業(yè)設(shè)備的識(shí)別。本地設(shè)備（移動(dòng)設(shè)備、傳感器等）主要執(zhí)行數(shù)據(jù)收集或者是前期數(shù)據(jù)處理，在脫離MEC 服務(wù)器的情況下只能進(jìn)行簡(jiǎn)單任務(wù)的處理，需要將計(jì)算任務(wù)傳輸?shù)綄?duì)應(yīng)的MEC 服務(wù)器進(jìn)行計(jì)算。MEC 服務(wù)器部署的位置比較靈活，本文選擇將MEC 計(jì)算服務(wù)器部署于微蜂窩基站上，在微蜂窩基站上實(shí)現(xiàn)具體的計(jì)算功能，本地設(shè)備通過(guò)無(wú)線的方式與服務(wù)器之間進(jìn)行交互。針對(duì)工業(yè)生產(chǎn)線中的計(jì)算卸載問題：首先，在工業(yè)生產(chǎn)線中將會(huì)接入各種類型的移動(dòng)設(shè)備（全景攝像頭、智能手機(jī)、AR 眼鏡等），移動(dòng)設(shè)備也具有一定的計(jì)算能力，即“多用戶”；其次，在工業(yè)生產(chǎn)線中往往需要多個(gè)MEC 服務(wù)器來(lái)處理任務(wù)，即“多MEC”。PSAO 卸載策略應(yīng)用于AR眼鏡與工業(yè)設(shè)備的實(shí)時(shí)交互，需要保證低延遲。

圖1 多設(shè)備多MEC系統(tǒng)模型Fig. 1 Model of multi-device multi-MEC system

假定在當(dāng)前網(wǎng)絡(luò)中包括K個(gè)移動(dòng)設(shè)備，N個(gè)MEC 服務(wù)器。每一個(gè)移動(dòng)設(shè)備產(chǎn)生任務(wù)后指定一個(gè)服務(wù)器（或本地）來(lái)執(zhí)行，最后找到所有任務(wù)最優(yōu)的執(zhí)行位置，即計(jì)算卸載向量V，卸載結(jié)果會(huì)有N+ 1 種可能性，任務(wù)可能會(huì)在本地執(zhí)行或者將任務(wù)裝載到N個(gè)MEC 服務(wù)器中的其中一個(gè)，并由裝載服務(wù)器執(zhí)行。

2.1 時(shí)延模型

根據(jù)任務(wù)在不同設(shè)備上運(yùn)行，時(shí)延模型也會(huì)存在差別：如果當(dāng)前任務(wù)在本地設(shè)備執(zhí)行并且每個(gè)任務(wù)都沒有排隊(duì)延遲，此時(shí)只需要考慮本地計(jì)算時(shí)延；若將任務(wù)卸載到MEC 服務(wù)器執(zhí)行，完成當(dāng)前任務(wù)所需要的時(shí)延主要包括傳輸時(shí)延、MEC計(jì)算時(shí)延、反饋時(shí)延，其中反饋時(shí)延遠(yuǎn)遠(yuǎn)小于傳輸時(shí)延，因此在本文中將忽略反饋時(shí)延。表1 詳細(xì)介紹了系統(tǒng)建模中使用的符號(hào)含義和在仿真實(shí)驗(yàn)中的取值，其中：下標(biāo)i表示當(dāng)前當(dāng)前移動(dòng)設(shè)備編號(hào)，j表示當(dāng)前MEC 服務(wù)器編號(hào)，u 表示移動(dòng)設(shè)備標(biāo)識(shí)，s表示服務(wù)器標(biāo)識(shí)。

表1 系統(tǒng)建模中使用的符號(hào)含義Tab. 1 Meaning of symbols used in system modeling

1）本地計(jì)算時(shí)延。

式（1）表示本地計(jì)算時(shí)延與本地CPU 周期頻率的倒數(shù)成正比，Bi*fi表示當(dāng)前任務(wù)計(jì)算量。

2）MEC傳輸時(shí)延。

在考慮計(jì)算MEC 計(jì)算時(shí)延之前，需要去定義通道傳輸速率，根據(jù)香農(nóng)定義可知：

已知當(dāng)前任務(wù)在通道中的傳輸速率為式（2），當(dāng)前任務(wù)計(jì)算量為Bi*fi，則傳輸時(shí)延為：

3）MEC計(jì)算時(shí)延。

式（4）表示MEC計(jì)算時(shí)延與MEC服務(wù)器周期頻率的倒數(shù)成正比。

2.2 能耗模型

1）計(jì)算能耗。

CPU 的算力與芯片架構(gòu)有著密切的關(guān)系，每一代CPU 架構(gòu)都有固定的能耗比，在同架構(gòu)前提下，功耗與電壓和頻率都成正比［16］，設(shè)備之間的能耗也會(huì)受到計(jì)算任務(wù)量的影響：

其中：電容Ci取決于有效開關(guān)電容；L表示電壓。

2）傳輸能耗。

傳輸能耗針對(duì)的是卸載到MEC 服務(wù)器上的任務(wù)，在時(shí)延模型中已經(jīng)計(jì)算出傳輸時(shí)延，則傳輸能耗為：

2.3 計(jì)算模型

2.1 節(jié)和2.2 節(jié)對(duì)工業(yè)生產(chǎn)線問題抽象建模：首先當(dāng)前MEC 的垂直應(yīng)用場(chǎng)景主要是針對(duì)計(jì)算密集型和延遲敏感型計(jì)算任務(wù)，其中包含工業(yè)中的增強(qiáng)現(xiàn)實(shí)圖像識(shí)別；其次需要確保每一項(xiàng)本地設(shè)備的平均能耗都小于最大能耗，因此實(shí)際建模為在能耗約束條件下的最小化時(shí)延問題。

完成一個(gè)卸載任務(wù)的總時(shí)延為傳輸時(shí)延與服務(wù)器計(jì)算時(shí)延的和：

本地執(zhí)行一個(gè)任務(wù)的總時(shí)延為：

由式（7）與式（8），可以得到針對(duì)某一個(gè)計(jì)算任務(wù)，在本地設(shè)備計(jì)算與MEC 服務(wù)器計(jì)算時(shí)會(huì)有不同的時(shí)延求解公式，可以將當(dāng)前問題聯(lián)合表達(dá)為：

其中：式（9）表示找到使得滿足時(shí)延最小的卸載決策向量，vi表示任務(wù)i具體分配到的服務(wù)器編號(hào)；式（10）表示能耗約束，每個(gè)任務(wù)所耗費(fèi)的平均能耗小于最大能耗；式（11）表示本地設(shè)備的CPU 周期頻率小于最大CPU 周期頻率；式（12）表示MEC 服務(wù)器的CPU 周期頻率小于最大CPU 周期頻率。P1 更加關(guān)注在整個(gè)卸載過(guò)程中的時(shí)延問題。

再考慮這樣一種情況：其中一個(gè)MEC 服務(wù)器性能更優(yōu)，按照式（9）的建模方式，因?yàn)闆]有考慮到排隊(duì)時(shí)延，導(dǎo)致大多數(shù)任務(wù)會(huì)卸載到性能更優(yōu)的MEC服務(wù)器，性能優(yōu)秀的MEC服務(wù)器的平均功耗會(huì)高于最大能耗，如果能將當(dāng)前任務(wù)卸載到其他MEC 服務(wù)器則可以緩解負(fù)載壓力。因此選擇將P1 問題轉(zhuǎn)化為增加懲罰函數(shù)的P2問題：當(dāng)設(shè)備平均能耗大于最大能耗時(shí)，通過(guò)增加懲罰函數(shù)的形式，來(lái)使得任務(wù)卸載到當(dāng)前MEC服務(wù)器的系統(tǒng)總成本增高。

其中：

其中：V表示需要求解的卸載向量；g表示懲罰系數(shù)，隨著計(jì)算消耗的能耗越多，則懲罰項(xiàng)越大，如果不超過(guò)最大能耗則不懲罰，增加懲罰函數(shù)的意義在于平衡能耗與時(shí)延。P2 更加關(guān)注在整個(gè)卸載過(guò)程中的時(shí)延與能耗的平衡。

3 基于PSO算法的優(yōu)化

PSO 算法受鳥類捕食行為的啟發(fā)并對(duì)這種行為進(jìn)行模仿，將優(yōu)化問題的搜索空間類比為鳥類的飛行空間，將每一只鳥抽象為一個(gè)粒子，粒子無(wú)質(zhì)量無(wú)體積，用以表征問題的一個(gè)可行解，優(yōu)化問題所要搜索到的最優(yōu)解等同于鳥類尋找的食物源［17］。

3.1 粒子編碼

假設(shè)粒子群規(guī)模為U，K 表示當(dāng)前本地任務(wù)數(shù)量，N 表示MEC 服務(wù)器的數(shù)量，所有任務(wù)的集合可以表示為M={m1，m2，…，mk}。首先對(duì)任務(wù)進(jìn)行定量描述，假設(shè)編號(hào)為i的移動(dòng)設(shè)備產(chǎn)生 mi(Bi，fi，Emax)個(gè)任務(wù)待計(jì)算。其中：Bi表示輸入數(shù)據(jù)量，fi表示計(jì)算密度，Emax表示任務(wù)的能耗約束。所有MEC 服務(wù)器周期頻率集合S = {s1，s2，…，sn}，包含了當(dāng)前系統(tǒng)中所有服務(wù)器的CPU 周期頻率。信道增益矩陣H =用來(lái)計(jì)算任務(wù)傳輸?shù)組EC 服務(wù)器的最大傳輸速率，Hi，i的信道增益為0，Hi，j（1 ≤i ≤K，1 ≤j ≤N，i ≠j）表示移動(dòng)設(shè)備i 產(chǎn)生的任務(wù)傳輸?shù)骄幪?hào)j 服務(wù)器所需要的信道增益。

粒子個(gè)體采用整數(shù)編碼，每一個(gè)粒子的元素可以取1到N之間的任意整數(shù)，粒子編碼的維度與任務(wù)集合的個(gè)數(shù)相同。假定當(dāng)前任務(wù)集合包含 5 個(gè)任務(wù) M={m1，m2，m3，m4，m5}，粒子編碼為[0，1，2，5，1，2]表示所有任務(wù)的執(zhí)行位置，其中第一個(gè)元素0 表示m1任務(wù)直接在本地進(jìn)行計(jì)算，第二個(gè)元素1表示m2任務(wù)將要裝載到編號(hào)為1 的MEC 服務(wù)器執(zhí)行，以此類推。

粒子表示當(dāng)前所有任務(wù)將要卸載到的具體某個(gè)MEC 服務(wù)器。每一個(gè)粒子的卸載決策向量V ={v1，v2，…，vk}表示所有任務(wù)最優(yōu)的執(zhí)行位置，其中vi在0到N中隨機(jī)取值：vi= 0表示當(dāng)前任務(wù)直接在本地執(zhí)行；vi= j(1 ≤j ≤N)表示當(dāng)前任務(wù)裝載到第j個(gè)MEC服務(wù)器，并由第j個(gè)服務(wù)器執(zhí)行。

粒子的速度表示當(dāng)前任務(wù)分配到其他MEC 服務(wù)器的趨勢(shì)快慢，記作Xi={x1，x2，…，xk}，粒子速度隨機(jī)初始化為整數(shù)值并在更新過(guò)程中進(jìn)行取整，粒子速度的編碼維度與任務(wù)集合的數(shù)目相同。假定當(dāng)前任務(wù)集合包含5 個(gè)任務(wù)M ={m1，m2，m3，m4，m5}，粒子速度為[0，3，1，4，1，2]，其中第一個(gè)元素0表示m1任務(wù)依舊由原來(lái)的MEC 服務(wù)器處理，第二個(gè)元素3 表示m2任務(wù)由原來(lái)下移3 位的MEC 服務(wù)器處理，以此類推。

每一個(gè)粒子在所有迭代過(guò)程中的最優(yōu)位置記作Pbest={ p1，p2，…，pn}，表示當(dāng)前粒子找到的使得系統(tǒng)總代價(jià)最小的任務(wù)分配方式；記錄所有粒子中出現(xiàn)的最優(yōu)位置，記作Gbest={g1，g2，…，gn} ，表示所有粒子中系統(tǒng)代價(jià)最小的分配方式。

3.2 適應(yīng)度函數(shù)

粒子的適應(yīng)度表示所有任務(wù)分配到不同MEC 服務(wù)器的系統(tǒng)總代價(jià)，計(jì)算公式為：

3.3 計(jì)算卸載流程

粒子群速度更新的決定因素主要包含三部分：第一部分主要是自身原來(lái)的速度，也可以稱作“慣性影響”；第二部分主要是自身記憶的最優(yōu)位置，也可以稱作“認(rèn)知影響”；第三部分主要是全部粒子記憶的最優(yōu)位置，也可以稱作“社會(huì)影響”。最后用粒子群算法解決計(jì)算卸載問題。

算法1 基于PSO算法的卸載流程。

輸入：

1）本地任務(wù)集合M = {m1，m2，…，mk}，MEC 服務(wù)器集合S ={s1，s2，…，sn}，信道增益矩陣H。

2）算法控制參數(shù)：粒子群規(guī)模N = 25，迭代代數(shù)maxGen = 100，速度邊界 vmax為 MEC 服務(wù)器個(gè)數(shù)的 2 倍，位置邊界 pmax為 MEC 服務(wù)器的個(gè)數(shù)，學(xué)習(xí)因子 c1= 1.5，c2= 1.5 慣性因子Wp= 0.4，懲罰因子g = 1 × 10-2.5。

輸出：

最 優(yōu) 分 配 向 量 Vi={v1，v2，…，vn} 與 最 小 延 遲Fitness(V)。

初始化：

1）初始化每一個(gè)粒子的隨機(jī)位置Vi與速度Xi，其中i 表示第i個(gè)粒子。

2）初始化適應(yīng)度值：通過(guò)本機(jī)任務(wù)集合M、MEC服務(wù)期集合S 和信道增益矩陣H 計(jì)算時(shí)延與能耗，按式（16）來(lái)計(jì)算每一個(gè)粒子的適應(yīng)度。

3）初始化粒子最優(yōu)分配與全局最優(yōu)分配：將粒子當(dāng)前位置設(shè)置為個(gè)體最優(yōu)任務(wù)分配方案Pbest，并將適應(yīng)度值最小的粒子的位置設(shè)置為群體最優(yōu)分配方案Gbest。

迭代計(jì)算：

4）令迭代次數(shù)t = 0

5）while t ≤ maxGen

a）更新速度。粒子中的每一個(gè)維度獨(dú)立去更新速度X[i]，如果速度大于vmax，則令X[i]= vmax。粒子速度的更新公式為：

其中：c1和 c2為學(xué)習(xí)因子；Wp為慣性權(quán)重：rand（）為 0～1的隨機(jī)數(shù)。

b）更新位置。粒子中的每一個(gè)維度獨(dú)立去更新位置V[i]，如果 V[i]位置大于 pmax，則令 V[i]= pmax。粒子位置的更新公式為：

c）更新粒子最優(yōu)分配與全局最優(yōu)分配。通過(guò)本機(jī)任務(wù)集合M、MEC 服務(wù)期集合S 和信道增益矩陣H 計(jì)算時(shí)延與能耗，按式（16）來(lái)計(jì)算每一個(gè)粒子的適應(yīng)度。如果更新后的適應(yīng)值小于當(dāng)前適應(yīng)值，則更新粒子最優(yōu)分配方案Pbest、群體最優(yōu)分配方案Gbest和系統(tǒng)總代價(jià)Fitness(V)。

d）t = t + 1

6）End

輸出結(jié)果：

7）得到最佳分配向量V[i]= Gbest和最小延遲Fitness(V)。

8）如果最優(yōu)解不滿足，則轉(zhuǎn)到步驟1）；否則輸出最優(yōu)分配向量Vi={v1，v2，…，vn}與最小延遲Fitness(V)。

最后通過(guò)集中控制的方式，vi(i = 1，2，…，K) = 0 將該任務(wù)放入本地設(shè)備中執(zhí)行，vi=j(j= 1，2，…，n)將該任務(wù)放入對(duì)應(yīng)編號(hào)j的MEC服務(wù)器中執(zhí)行。

4 仿真與結(jié)果分析

4.1 仿真環(huán)境以及參數(shù)設(shè)置

通過(guò)Java 語(yǔ)言實(shí)現(xiàn)了PSO 算法，從而具體地評(píng)估所提出的計(jì)算卸載策略的性能。在工業(yè)生產(chǎn)線場(chǎng)景中，設(shè)備的個(gè)數(shù)K=［50，100，150，200，250］，MEC 服務(wù)器的個(gè)數(shù)為10，分別有K個(gè)移動(dòng)設(shè)備向10個(gè)服務(wù)器發(fā)起卸載請(qǐng)求。仿真用到的主要參數(shù)取值與符號(hào)含義［10］如表2所示。

4.2 結(jié)果分析

根據(jù)表2 的參數(shù)取值進(jìn)行仿真實(shí)驗(yàn)，本文選擇四種卸載策略進(jìn)行對(duì)比：本地卸載策略、MEC 基準(zhǔn)卸載策略、基于人工魚群算法（AFSA）的卸載策略和PSAO；同時(shí)也通過(guò)PSO 算法優(yōu)化基準(zhǔn)卸載策略在卸載過(guò)程中的平均總時(shí)延。在實(shí)際生產(chǎn)環(huán)境中本地設(shè)備只能進(jìn)行簡(jiǎn)單任務(wù)的處理，仿真實(shí)驗(yàn)中假設(shè)本地設(shè)備也能夠處理高計(jì)算量的任務(wù)，假設(shè)每一項(xiàng)任務(wù)到達(dá)即執(zhí)行，不會(huì)存在任務(wù)排隊(duì)導(dǎo)致的時(shí)延增加。

表2 主要參數(shù)取值與符號(hào)含義Tab. 2 Main parameter values and symbol meanings

圖2 為不同能耗約束下不同卸載策略的系統(tǒng)總代價(jià)對(duì)比，設(shè)置設(shè)備數(shù)K= 50，MEC 服務(wù)器的個(gè)數(shù)N= 10，每一項(xiàng)任務(wù)數(shù)據(jù)量大小Bi= 3 Mb?？梢杂^察到，隨著能耗約束的增大，四種卸載策略系統(tǒng)總代價(jià)降低。當(dāng)能耗（單位：J）約束為0時(shí)，本地卸載策略的系統(tǒng)總代價(jià)遠(yuǎn)遠(yuǎn)高于其他三種卸載策略，這是由于本地設(shè)備處理任務(wù)將會(huì)產(chǎn)生較高的能耗；能耗約束為750 J 時(shí)，本地卸載策略代價(jià)開始低于MEC 基準(zhǔn)卸載策略，這是由于能耗約束的增大，模型對(duì)能耗約束的敏感度降低，因此需要選擇合適的能耗約束。PSAO 卸載策略在不同的能耗約束下都優(yōu)于其他MEC 基準(zhǔn)卸載策略和本地卸載策略，當(dāng)能耗約束大于750 J 時(shí)，基于AFSA 的卸載策略與PSAO 卸載策略優(yōu)化效果相差不大。

圖2 能耗vs. 系統(tǒng)總代價(jià)Fig. 2 Energy consumption vs. total system cost

圖3 對(duì)PSAO 卸載策略的收斂性進(jìn)行評(píng)估，設(shè)置設(shè)備數(shù)K= 50，MEC 服務(wù)器的個(gè)數(shù)N=10，每一項(xiàng)任務(wù)數(shù)據(jù)量大小Bi=3 Mb，通過(guò)改變迭代次數(shù)來(lái)觀察所有任務(wù)的平均總時(shí)延。

圖3 收斂性分析Fig.3 Convergence analysis

由圖3可以觀察到，算法在前25次迭代過(guò)程中收斂較快，迭代50 次后系統(tǒng)總代價(jià)保持不變，找到全局最優(yōu)解。PSAO具有很強(qiáng)的全局優(yōu)化能力，在算法的前期不斷尋找全局的最優(yōu)解，且在后期具有良好的全局搜索能力。PSO 算法優(yōu)化后平均總時(shí)延從原來(lái)的303.33 ms 降低至241.824 ms，并在后期迭代過(guò)程中保持不變，相比原來(lái)系統(tǒng)的總時(shí)延降低了20%。

圖4 為不同設(shè)備個(gè)數(shù)的情況下，不同卸載策略的系統(tǒng)總代價(jià)對(duì)比。MEC 服務(wù)器的個(gè)數(shù)N= 10，每一項(xiàng)任務(wù)數(shù)據(jù)量大小Bi= 3 Mb?？梢杂^察到在設(shè)備數(shù)分別為50，100，150，200，250 時(shí)，平均總時(shí)延是處于增長(zhǎng)的趨勢(shì)，這是由于隨著設(shè)備數(shù)的增加，所需要的處理時(shí)間與傳輸時(shí)間也隨之增加；但是，隨著任務(wù)數(shù)目的增加，PSAO卸載策略總時(shí)延增長(zhǎng)幅度遠(yuǎn)遠(yuǎn)小于MEC 基準(zhǔn)卸載策略與本地卸載策略?；贏FSA 的卸載策略在設(shè)備數(shù)小于200 時(shí)，優(yōu)化程度與PSAO 卸載策略相差不大；但當(dāng)設(shè)備數(shù)目大于200 時(shí)，系統(tǒng)總代價(jià)開始急速上升，遠(yuǎn)遠(yuǎn)高于PSAO卸載策略。

圖4 設(shè)備數(shù)vs. 系統(tǒng)總代價(jià)Fig. 4 Number of devices vs. total system cost

圖5 為不同任務(wù)量的情況下，不同卸載策略的平均總時(shí)延對(duì)比。設(shè)置任務(wù)數(shù)K= 50，MEC 服務(wù)器的個(gè)數(shù)N= 10，可以觀察到：在任務(wù)量分別為3、10、15、25、40 Mb 時(shí)，隨著任務(wù)量的增加，平均總時(shí)延也逐漸增加。本地卸載策略比其他策略增長(zhǎng)速度更快，表明隨著任務(wù)量的增加會(huì)導(dǎo)致更多的時(shí)間與能量消耗。其中，基于AFSA 的卸載策略在任務(wù)量小于15 Mb 時(shí)，與PSAO 卸載策略優(yōu)化效果相差不大；但是在任務(wù)量大于15 Mb 時(shí)，容易收斂于局部最優(yōu)，并且在后期搜索過(guò)程中盲目性比較大，卸載效果不理想。PSAO卸載策略增幅程度遠(yuǎn)遠(yuǎn)小于MEC 基準(zhǔn)卸載策略與本地卸載策略，并且在任務(wù)量過(guò)大時(shí)可以取得最佳效果。

圖5 任務(wù)量vs. 系統(tǒng)總代價(jià)Fig. 5 Task size vs. total system cost

5 結(jié)語(yǔ)

本文將工業(yè)生產(chǎn)線中的計(jì)算卸載問題建模為多用戶多MEC 時(shí)延優(yōu)化問題，為了消除本地設(shè)備使用能耗來(lái)?yè)Q取時(shí)延的問題，通過(guò)懲罰函數(shù)平衡時(shí)延與能耗，并提出基于PSO算法優(yōu)化的卸載策略PSAO?；诜治鼋Y(jié)果可知，本地卸載策略與MEC 基準(zhǔn)卸載策略都有一定的局限性，本文選擇PSAO 卸載策略讓本地設(shè)備和MEC 服務(wù)器協(xié)作計(jì)算，使原本系統(tǒng)總代價(jià)降低了20%，并且隨著設(shè)備數(shù)目和任務(wù)量的增加，它的增幅程度遠(yuǎn)小于本地卸載策略和MEC 基準(zhǔn)卸載策略，滿足延遲敏感型應(yīng)用的服務(wù)質(zhì)量要求；基于AFSA 的卸載策略雖然能夠起到一定的優(yōu)化作用，但在設(shè)備數(shù)增加和任務(wù)量增大的情況下，無(wú)法找到任務(wù)最佳分配方案。工業(yè)系統(tǒng)對(duì)于可靠性要求非常高，PSAO 卸載策略屬于啟發(fā)式卸載策略，大部分啟發(fā)式算法能夠生成高質(zhì)量的近似最優(yōu)解，由于啟發(fā)式方法的結(jié)果是隨機(jī)產(chǎn)生的近似解，因此缺少可靠性［18］。未來(lái)將會(huì)考慮粒子群與其他優(yōu)化算法相結(jié)合，提高尋找到最優(yōu)解的魯棒性，從而在降低時(shí)延的前提下，提高整個(gè)卸載策略的可靠性。