移動邊緣計(jì)算中基于云邊端協(xié)同的任務(wù)卸載策略

張文柱 余靜華

（西安建筑科技大學(xué)信息與控制工程學(xué)院 西安 710055）

隨著萬物互聯(lián)時(shí)代的到來，智能終端設(shè)備數(shù)量和其產(chǎn)生的數(shù)據(jù)量都急劇增長[1].Cisco 云預(yù)測，2021年全球范圍內(nèi)將有超過500 億個(gè)的終端設(shè)備，這些設(shè)備每年產(chǎn)生的計(jì)算型數(shù)據(jù)總量將超84 ZB，高計(jì)算應(yīng)用需求越來越多[2].移動終端設(shè)備因其有限的電量和計(jì)算能力不能滿足人們?nèi)找嬖鲩L的應(yīng)用需求，因此，如何提供高計(jì)算能力服務(wù)和服務(wù)質(zhì)量成為一個(gè)研究重點(diǎn).移動云計(jì)算（mobile cloud computing，MCC）[3]通過將移動終端設(shè)備的計(jì)算任務(wù)轉(zhuǎn)移到計(jì)算能力強(qiáng)大的云中心對任務(wù)進(jìn)行集中處理[4]，成為提供高計(jì)算能力的解決方案.但MCC 有其固有的局限性[5]：云中心與遠(yuǎn)距離終端之間的傳播時(shí)限使其無法高效處理終端設(shè)備產(chǎn)生的敏感時(shí)延性質(zhì)的數(shù)據(jù).因此，MCC 不適合服務(wù)于時(shí)延敏感的應(yīng)用.

歐洲電信標(biāo)準(zhǔn)協(xié)會（ETSI）在2014 年提出移動邊緣計(jì)算模式[6].移動邊緣計(jì)算是將計(jì)算和存儲資源部署在移動網(wǎng)絡(luò)邊緣側(cè)，為用戶提供云計(jì)算能力、低時(shí)延和高帶寬的網(wǎng)絡(luò)服務(wù)[7]，結(jié)合計(jì)算卸載技術(shù)很好地平衡了MCC 的局限性.未來的無線系統(tǒng)中，小基站、平板電腦等計(jì)算能力與計(jì)算機(jī)服務(wù)器相當(dāng)?shù)脑O(shè)備都可作為邊緣節(jié)點(diǎn)[8].

計(jì)算卸載技術(shù) [9]指終端設(shè)備將部分或全部計(jì)算任務(wù)交給邊緣云或中心云處理，為移動終端設(shè)備在資源存儲、計(jì)算性能以及能效等方面存在的不足提供解決方案，是移動邊緣計(jì)算（mobile edge computing，MEC）的關(guān)鍵技術(shù)之一.其中，卸載決策是計(jì)算卸載技術(shù)的核心問題[10]，卸載決策決定任務(wù)是否卸載、卸載什么以及卸載到哪里的問題[11].在多終端、多任務(wù)的復(fù)雜場景下，卸載決策的制定需要綜合任務(wù)計(jì)算量、數(shù)據(jù)傳輸量、邊緣云計(jì)算能力和資源利用率等諸多因素.傳統(tǒng)的卸載方式依靠虛擬機(jī)實(shí)現(xiàn)，而研究表明[12]，Docker 容器比虛擬機(jī)更輕量，節(jié)省了時(shí)間和能耗，它將任務(wù)程序代碼、任務(wù)依賴項(xiàng)和環(huán)境概要文件打包到鏡像副本中構(gòu)建容器鏡像，操作方便.在一個(gè)完備的執(zhí)行架構(gòu)中，根據(jù)任務(wù)的差異化制定最優(yōu)的卸載決策能有效提高任務(wù)的執(zhí)行效率，但依靠單一的終端設(shè)備計(jì)算、邊緣計(jì)算和云計(jì)算都不能滿足復(fù)雜場景的需求，不能同時(shí)平衡時(shí)延與能耗.因此，本文的目標(biāo)是綜合端—邊—云的優(yōu)勢，實(shí)現(xiàn)以下目標(biāo)：在最優(yōu)化時(shí)延與能耗的情況下，將時(shí)延敏感的任務(wù)卸載至邊緣節(jié)點(diǎn)計(jì)算，時(shí)延容忍的大數(shù)據(jù)量任務(wù)在云中心處理，時(shí)延容忍的小數(shù)據(jù)量任務(wù)在終端處理.本文的主要貢獻(xiàn)有3 個(gè)方面：

1）提出一個(gè)基于Docker 的云—邊—端協(xié)同的移動邊緣計(jì)算框架，建立了任務(wù)依賴關(guān)系聯(lián)合并行計(jì)算的任務(wù)執(zhí)行序列，在并行計(jì)算設(shè)定上分別建立了本地計(jì)算、邊緣計(jì)算和云計(jì)算的計(jì)算時(shí)間和能耗模型；

2）在多用戶服務(wù)場景中，通過跨端—邊—云的協(xié)作方式，制定任務(wù)最小計(jì)算時(shí)間和最低能耗的目標(biāo)卸載決策，為實(shí)現(xiàn)減小系統(tǒng)計(jì)算時(shí)間的同時(shí)降低系統(tǒng)能耗的目標(biāo)，設(shè)計(jì)了人工粒子蜂群（artificial particle swarm,APS）算法搜索最佳的卸載策略；

3）通過仿真實(shí)驗(yàn)，對比人工蜂群算法、粒子群算法和隨機(jī)卸載算法驗(yàn)證了APS 算法的性能；對比本地計(jì)算、邊緣計(jì)算、云計(jì)算、本地—邊緣聯(lián)合計(jì)算和隨機(jī)處理等計(jì)算模式，驗(yàn)證本系統(tǒng)的性能.

1 相關(guān)工作

近年來，隨著MEC 的應(yīng)用和卸載決策的研究不斷深入，網(wǎng)絡(luò)環(huán)境復(fù)雜度的提高和終端設(shè)備數(shù)據(jù)量的增大所帶來的挑戰(zhàn)也越來越嚴(yán)峻.尤其對于移動邊緣計(jì)算模型的建立和卸載策略的制定，要滿足任務(wù)的執(zhí)行條件，當(dāng)可用節(jié)點(diǎn)較少或卸載決策制定因素不完善時(shí)，會產(chǎn)生高時(shí)延甚至處理失敗.

一些特定應(yīng)用背景下MEC 系統(tǒng)模型和卸載決策的研究成果已經(jīng)落地.文獻(xiàn)[13]提出了一種面向多節(jié)點(diǎn)的自動駕駛邊緣卸載框架來提供效率和隱私導(dǎo)向的自動駕駛卸載服務(wù),在多邊緣節(jié)點(diǎn)中進(jìn)行卸載調(diào)度策略的實(shí)時(shí)求解.文獻(xiàn)[14]針對智慧城市領(lǐng)域提出了在能耗和響應(yīng)時(shí)間之間進(jìn)行權(quán)衡的任務(wù)卸載優(yōu)化策略，包括2 個(gè)子目標(biāo)的建模和啟發(fā)式雙目標(biāo)優(yōu)化算法.文獻(xiàn)[15]針對智能家居場景中的MEC,引入邊緣節(jié)點(diǎn)的泛在感知能力,在保證數(shù)據(jù)安全的基礎(chǔ)上實(shí)現(xiàn)邊緣節(jié)點(diǎn)資源的分配.文獻(xiàn)[16]研究雙無人機(jī)輔助MEC 系統(tǒng)的安全問題，通過抗干擾幫助地面終端設(shè)備計(jì)算卸載的任務(wù)，聯(lián)合了優(yōu)化通信資源、計(jì)算資源和無人機(jī)軌跡進(jìn)行任務(wù)卸載.

從MEC 應(yīng)用可知，任務(wù)卸載模型和計(jì)算卸載決策是MEC 中的研究熱點(diǎn)，二者共同決定任務(wù)的執(zhí)行位置與分配資源，主要研究方向有3 個(gè)：時(shí)延、能耗、權(quán)衡時(shí)延與能耗.文獻(xiàn)[17]提出一個(gè)任務(wù)卸載和異構(gòu)資源調(diào)度的聯(lián)合優(yōu)化模型，最小化用戶的設(shè)備能耗、任務(wù)執(zhí)行時(shí)延和成本來求解最優(yōu)的任務(wù)卸載算法.文獻(xiàn)[18]為了使時(shí)延敏感的處理任務(wù)在近終端用戶執(zhí)行，提出支持多個(gè)物聯(lián)網(wǎng)服務(wù)提供商在一個(gè)通用MEC 平臺部署的兼容方案，在平臺內(nèi)引導(dǎo)物聯(lián)網(wǎng)數(shù)據(jù)傳輸.文獻(xiàn)[19]提出緩存輔助邊緣計(jì)算的卸載決策制定與資源優(yōu)化方案，通過建立最小化用戶在任務(wù)執(zhí)行時(shí)最高能耗值，得到理想的卸載決策集合與資源分配方案.文獻(xiàn)[20]制定了在遷移能量預(yù)算的條件下盡量減少任務(wù)的平均完成時(shí)間的目標(biāo)，設(shè)計(jì)了基于強(qiáng)化學(xué)習(xí)的分布式任務(wù)遷移算法.文獻(xiàn)[21]考慮多用戶的MEC 系統(tǒng)以最小化終端能耗為目標(biāo)，通過聯(lián)合優(yōu)化任務(wù)傳輸功率、局部計(jì)算和邊緣計(jì)算能力來研究任務(wù)卸載問題.

然而，文獻(xiàn)[13?21]研究都依賴單一的計(jì)算模式，在通信資源有限的條件下，會因通信鏈路堵塞造成更大的時(shí)延.因此提出本文第一個(gè)改進(jìn)點(diǎn):建立多終端、多任務(wù)的云—邊—端協(xié)作任務(wù)執(zhí)行模型，并加入任務(wù)計(jì)算結(jié)果傳回終端設(shè)備的時(shí)延異步性因素；聯(lián)合時(shí)延與能耗，通過實(shí)驗(yàn)為時(shí)延與能耗分配最優(yōu)權(quán)重進(jìn)行計(jì)算卸載，保證此模型具備實(shí)際意義.

對于任務(wù)卸載策略的研究大多處于粗粒度范疇，隨著任務(wù)需求的提升，近年來也出現(xiàn)了考慮任務(wù)的差異化并對其進(jìn)行預(yù)處理的研究，表現(xiàn)為將任務(wù)進(jìn)行劃分或建立任務(wù)依賴關(guān)系.文獻(xiàn)[22]將一個(gè)任務(wù)劃分為多個(gè)子任務(wù)卸載給多個(gè)MEC 節(jié)點(diǎn)，通過預(yù)測每個(gè)候選MEC 節(jié)點(diǎn)上每個(gè)任務(wù)的總處理時(shí)間決定子任務(wù)卸載位置.文獻(xiàn)[23?24]研究單用戶MEC 系統(tǒng)、移動設(shè)備包含一個(gè)由多計(jì)算組件或具有依賴關(guān)系的任務(wù)組成的應(yīng)用程序，根據(jù)依賴執(zhí)行順序計(jì)算出最優(yōu)的任務(wù)卸載策略.文獻(xiàn)[25]研究多用戶任務(wù)卸載，為提高資源利用率，提出基于建立任務(wù)依賴關(guān)系的卸載調(diào)度器.文獻(xiàn)[26]先研究2 個(gè)設(shè)備間的任務(wù)依賴與相關(guān)性，然后擴(kuò)展到復(fù)雜交互的多用戶場景，實(shí)現(xiàn)最優(yōu)的任務(wù)卸載策略和資源分配.文獻(xiàn)[27] 提出一種用于多移動應(yīng)用的依賴任務(wù)卸載框架,將有依賴約束的計(jì)算密集型任務(wù)自適應(yīng)地卸載到MEC 和云.任務(wù)劃分的研究適用于資源需求大、數(shù)據(jù)量大和數(shù)量偏少的任務(wù)集，而在密集復(fù)雜環(huán)境中劃分任務(wù)會導(dǎo)致計(jì)算量呈指數(shù)增長，于系統(tǒng)服務(wù)無益.

文獻(xiàn)[22?27]研究中建立任務(wù)依賴關(guān)系的方法大多面向單用戶系統(tǒng)，通過傳統(tǒng)的有向無環(huán)圖（directed acyclic graph，DAG）進(jìn)行任務(wù)拓?fù)渑判颍贁U(kuò)展到多個(gè)設(shè)備的DAG 調(diào)用.在每個(gè)處理器僅執(zhí)行1 個(gè)任務(wù)的情況下多個(gè)任務(wù)面臨等待，且調(diào)用多個(gè)DAG 進(jìn)行任務(wù)分配無法解決有依賴任務(wù)與無依賴任務(wù)的區(qū)別處理，造成不必要的時(shí)延浪費(fèi).基于文獻(xiàn)[22?27]分析，提出本文的第2 個(gè)改進(jìn)點(diǎn)：1）將任務(wù)依賴關(guān)系與任務(wù)并行處理相結(jié)合，以最優(yōu)最長鏈路拓?fù)渑判虻腒ahn 算法為基礎(chǔ)，加入行滿秩矩陣結(jié)果要求，使算法輸出的任務(wù)依賴矩陣的行元素直接表明任務(wù)的優(yōu)先級.第一優(yōu)先級任務(wù)為無依賴任務(wù)與依賴初始任務(wù)的集合，優(yōu)先級則代表任務(wù)的執(zhí)行順序；2）再結(jié)合云—邊協(xié)同架構(gòu)的并行處理原則，將表征任務(wù)依賴的優(yōu)先級矩陣抽象成任務(wù)執(zhí)行序列，每個(gè)序列將同步執(zhí)行，大大縮短任務(wù)的排序處理時(shí)延.

卸載策略求解過程屬于NP 難問題，MEC 研究中大多將其轉(zhuǎn)化為多因素優(yōu)化問題，近年來使用較多的求解方式是群體智能算法.文獻(xiàn)[28?29]研究了面向智能物聯(lián)網(wǎng)的MEC 應(yīng)用，采用遺傳（genetic algorithm,GA）算法優(yōu)化計(jì)算成本與能耗進(jìn)而得到卸載決策.文獻(xiàn)[30?31] 為了減少多接入環(huán)境和高需求應(yīng)用的能耗，利用模擬退火（simulated annealing,SA）算法全局尋優(yōu)能力求解卸載決策，使復(fù)雜優(yōu)化問題便于處理.文獻(xiàn)[32] 結(jié)合灰狼和混合鯨魚優(yōu)化算法實(shí)現(xiàn)卸載決策的3 個(gè)目標(biāo)優(yōu)化，并對比GA 說明了混合算法在考慮多因素求解卸載決策時(shí)的優(yōu)越性.文獻(xiàn) [33]為預(yù)測多服務(wù)器MEC 的自適應(yīng)服務(wù)質(zhì)量，采用人工蜂群（artificial bee colony，ABC）算法求解策略后再將各服務(wù)器結(jié)果進(jìn)行整體對比選擇任務(wù)執(zhí)行節(jié)點(diǎn).在多接入邊緣協(xié)同環(huán)境中，應(yīng)用最為廣泛的是粒子群（particle swarm optimization，PSO）算法.文獻(xiàn)[34?35]研 究了 多MEC服務(wù)器對多任務(wù)的卸載決策制定，采用PSO 得到任務(wù)遷移決策和計(jì)算資源分配方案.文獻(xiàn)[36]應(yīng)用PSO作為卸載決策算法處理計(jì)算密集型和時(shí)延敏感型任務(wù)，且對比說明PSO 相比于GA 與SA 的優(yōu)越性.但PSO 在處理異構(gòu)邊緣節(jié)點(diǎn)和復(fù)雜約束優(yōu)化問題時(shí)全局尋優(yōu)收斂時(shí)間太長，因此需融入局部尋優(yōu)能力強(qiáng)的算法平衡PSO 的缺陷，如ABC 是群體智能中最成功的局部尋優(yōu)算法之一，ABC 與PSO 的混合更有利于發(fā)揮群體智能算法在MEC 中的作用.

基于文獻(xiàn)[28?36]研究提出本文的第3 個(gè)改進(jìn)點(diǎn)為：結(jié)合ABC 算法的局部尋優(yōu)能力與PSO 算法的全局尋優(yōu)能力，組合成APS 算法用于求解云—邊—端協(xié)同框架下聯(lián)合時(shí)延與能耗的卸載決策；從降低算法復(fù)雜度的角度出發(fā)，通過引入“全優(yōu)率”參數(shù)進(jìn)行迭代結(jié)果的適應(yīng)度函數(shù)判斷，決定個(gè)體蜂的類型與蜜源搜索方式.表1 為現(xiàn)有的適用于復(fù)雜約束的PSOABC 混合算法相關(guān)研究與本文方法的對比，進(jìn)一步說明本文算法特點(diǎn).

Table 1 Comparison of Researches on ABC-PSO Hybrid Algorithm and the Proposed Method表1 ABC-PSO 混合算法相關(guān)研究與本文方法對比

2 系統(tǒng)架構(gòu)

本文提出一個(gè)基于Docker 的輕量級、虛擬化的云—邊—端協(xié)同卸載架構(gòu)，它包含K個(gè)云中心服務(wù)器、M個(gè)邊緣服務(wù)器和L個(gè)移動終端設(shè)備.邊緣服務(wù)器部署在近移動終端設(shè)備側(cè)的微型基站上；遠(yuǎn)程云中心服務(wù)器附加在宏基站上，其與邊緣服務(wù)器相比，它的存儲和計(jì)算能力更強(qiáng)大.設(shè)云中心集合表示為K={1,2,…,k},邊緣節(jié) 點(diǎn)集合 表示為M={1,2,…,m},移動終端設(shè)備集合表示為L={1,2,…,l}.同時(shí)假設(shè)每個(gè)終端設(shè)備與邊緣節(jié)點(diǎn)和云中心相關(guān)聯(lián)，移動設(shè)備與基站之間的鏈路集表示為R={1,2,…,r}.

如圖1 所示，系統(tǒng)架構(gòu)由卸載調(diào)度、卸載決策算法和任務(wù)執(zhí)行部分（移動設(shè)備側(cè)、邊緣節(jié)點(diǎn)側(cè)和云中心側(cè)）組成.首先，移動終端設(shè)備生成任務(wù)集合并制定執(zhí)行矩陣；其次，由卸載決策模塊收集任務(wù)的執(zhí)行要求和邊緣節(jié)點(diǎn)的資源使用情況，通過卸載決策算法得到任務(wù)的執(zhí)行方案；最終，將隊(duì)列中的全部任務(wù)分別發(fā)送到本地計(jì)算任務(wù)集合、邊緣節(jié)點(diǎn)，計(jì)算任務(wù)集合和云中心計(jì)算任務(wù)集合.經(jīng)過卸載模塊計(jì)算，無需卸載的任務(wù)在本地進(jìn)行計(jì)算，需要卸載的任務(wù)通過卸載調(diào)度模塊將任務(wù)程序代碼、數(shù)據(jù)和Dockerfile 文件發(fā)送至邊緣節(jié)點(diǎn)或云中心，構(gòu)建任務(wù)鏡像并創(chuàng)建容器進(jìn)行任務(wù)計(jì)算，計(jì)算完成后將結(jié)果返回原終端設(shè)備.

Fig.1 Cloud-edge-end system architecture圖1 云—邊—端系統(tǒng)架構(gòu)

3 系統(tǒng)模型和卸載決策制定

基于圖1 所示的多用戶移動邊緣計(jì)算場景，卸載決策模塊為基站覆蓋服務(wù)區(qū)的N個(gè)終端用戶提供任務(wù)執(zhí)行方案.每個(gè)終端用戶都可以選擇在本地計(jì)算任務(wù)，或?qū)⑷蝿?wù)卸載至邊緣節(jié)點(diǎn)或云中心執(zhí)行.任務(wù)模型、本地計(jì)算模型、邊緣計(jì)算模型、云計(jì)算模型在本節(jié)進(jìn)行說明.

3.1 任務(wù)依賴模型與并行計(jì)算說明

3.1.1 任務(wù)模型

假設(shè)任務(wù)是完整的且不可再劃分，移動終端設(shè)備產(chǎn)生n個(gè)待處理任務(wù)Task={T1,T2,…,Tn},每個(gè)任務(wù)Tj有6 個(gè)基本屬性：

其中：wj表示任務(wù)j的計(jì)算量，通過CPU 周期度量；fmin.j表示任務(wù)j需要的最小計(jì)算能力；cpuj和memj分別表示任務(wù)j執(zhí)行時(shí)需要的CPU 資源和內(nèi)存資源；dataj表示任務(wù)j卸載時(shí)需要傳輸?shù)臄?shù)據(jù)量，包括過程代碼和輸入?yún)?shù)等信息；tmax.j表示完成任務(wù)j允許的最大時(shí)延.

3.1.2 任務(wù)依賴模型

同一設(shè)備產(chǎn)生的不同任務(wù)通常具有一定的依賴關(guān)系，本文通過建立任務(wù)執(zhí)行矩陣來提高處理任務(wù)效率.當(dāng)任務(wù)生成后，將任務(wù)如何執(zhí)行的初始狀態(tài)抽象成DAG；再將DAG 進(jìn)行拓?fù)渑判蛏扇蝿?wù)執(zhí)行矩陣；最后根據(jù)卸載策略判斷任務(wù)的執(zhí)行位置.本文設(shè)計(jì)的任務(wù)依賴關(guān)系算法以雙維護(hù)集Kahn 拓?fù)渌惴榛A(chǔ)，融入行滿秩矩陣要求,在保證最優(yōu)且唯一的同時(shí)避免出現(xiàn)分支多組合路徑.為與任務(wù)并行計(jì)算設(shè)定相結(jié)合，此算法的目標(biāo)是在多種拓?fù)漤樞虻那闆r下選出多行少列的依賴關(guān)系矩陣結(jié)果作為任務(wù)調(diào)度方案，最大限度確保有依賴任務(wù)有序執(zhí)行，無依賴任務(wù)快速執(zhí)行.任務(wù)依賴矩陣結(jié)果同時(shí)也是任務(wù)優(yōu)先等級的劃分結(jié)果，每一行向下遞減一個(gè)優(yōu)先級.執(zhí)行偽代碼如算法1.

算法 1.任務(wù)依賴關(guān)系算法/*對輸入的有向無環(huán)圖生成拓?fù)渑判蚝蟮膱?zhí)行矩陣L（該矩陣中行向量線性無關(guān)）.

輸入：有向無環(huán)圖G，G=(V，E)，V表示任務(wù)集，E表示任務(wù)之間依賴關(guān)系鏈路集；

輸出：執(zhí)行矩陣L.

任務(wù)之間的初始狀態(tài)關(guān)系如圖2 所示,根據(jù)拓?fù)渌惴ń?zhí)行矩陣式（2），假設(shè)由卸載決策算法得到任務(wù)的決策矩陣式（3），其中，“1”表示任務(wù)在終端設(shè)備執(zhí)行，“?1”表示任務(wù)在邊緣節(jié)點(diǎn)執(zhí)行，“0”表示任務(wù)在云中心執(zhí)行.

Fig.2 Initial state relationship among tasks圖2 任務(wù)之間的初始狀態(tài)關(guān)系

3.1.3 任務(wù)并行計(jì)算說明

采用Docker 封裝卸載的形式使并行計(jì)算成為可能.當(dāng)邊緣節(jié)點(diǎn)i滿足任務(wù)j需求的存儲資源但不滿足任務(wù)j的CPU 計(jì)算資源需求時(shí)，結(jié)合時(shí)延與能耗，判斷是否等待邊緣節(jié)點(diǎn)i計(jì)算完1 個(gè)或若干任務(wù)后釋放CPU 資源以達(dá)到任務(wù)需求，若合適仍將任務(wù)卸載到此邊緣節(jié)點(diǎn).任務(wù)到達(dá)邊緣節(jié)點(diǎn)i后先儲存到內(nèi)存中，等待滿足CPU 資源后參與計(jì)算.并行計(jì)算過程如圖3 所示：

Fig.3 Parallel computing process of edge node圖3 邊緣節(jié)點(diǎn)并行計(jì)算過程

圖3 中a1，a2，a3，a4分別為任務(wù)1～4 抵達(dá)節(jié)點(diǎn)i的時(shí)間.假設(shè)任務(wù)1～3 抵達(dá)節(jié)點(diǎn)i時(shí)，節(jié)點(diǎn)可用內(nèi)存資源和計(jì)算資源大于任務(wù)所需資源，則任務(wù)1～3 立即執(zhí)行；假設(shè)任務(wù)4 抵達(dá)節(jié)點(diǎn)時(shí)節(jié)點(diǎn)可用計(jì)算資源小于任務(wù)所需計(jì)算資源，則任務(wù)4 不能立即執(zhí)行.對比任務(wù)1～3 的計(jì)算時(shí)間，任務(wù)2 最先計(jì)算完畢，其次任務(wù)1完成計(jì)算；假設(shè)任務(wù)1 釋放CPU 計(jì)算資源后該節(jié)點(diǎn)滿足任務(wù)4 的計(jì)算需求，則任務(wù)4 開始執(zhí)行，時(shí)間a6為任務(wù)1 的完成時(shí)間.我們將考慮任務(wù)之間的并行依賴關(guān)系 后制定的 卸載決 策表示為ST={st1,st2,…,stn}，stj表示任務(wù)j的執(zhí)行地點(diǎn).

任務(wù)并行計(jì)算的重要基礎(chǔ)是任務(wù)依賴矩陣的生成，矩陣行向量傳達(dá)了任務(wù)的優(yōu)先級執(zhí)行順序，行向量之間的無依賴關(guān)系任務(wù)就可以依據(jù)資源情況在相關(guān)節(jié)點(diǎn)并行計(jì)算.當(dāng)設(shè)備數(shù)量與任務(wù)數(shù)量較多時(shí)，結(jié)合任務(wù)依賴于并行計(jì)算，實(shí)現(xiàn)同一時(shí)間計(jì)算出不同設(shè)備上同一優(yōu)先級的任務(wù)結(jié)果，真正將多維分散無序計(jì)算變?yōu)閙× 1 維有序執(zhí)行.

3.2 本地計(jì)算模型

任務(wù)在終端設(shè)備進(jìn)行計(jì)算的時(shí)延如式（4）.其中fl表示終端設(shè)備的計(jì)算能力，cpul表示終端設(shè)備可用CPU 資源，meml表示終端設(shè)備可用內(nèi)存資源.任務(wù)在終端設(shè)備進(jìn)行計(jì)算的能耗為表示CPU 循環(huán)1 個(gè)周期所產(chǎn)生的能耗，表示由芯片結(jié)構(gòu)而定的開關(guān)電容.

3.3 邊緣節(jié)點(diǎn)計(jì)算模型

本系統(tǒng)中M個(gè)邊緣服務(wù)器的集合為Edge={Ed1,Ed2,…,Edm}，每個(gè)邊緣服務(wù)器的基本屬性如式（6）所示.fi表示邊緣節(jié)點(diǎn)i的最大計(jì)算能力，cpui表示邊緣節(jié)點(diǎn)i的可用CPU 資源，memi表示邊緣節(jié)點(diǎn)i的可用內(nèi)存資源，Ri是邊緣節(jié)點(diǎn)與移動設(shè)備間的數(shù)據(jù)傳輸速度，Pi為邊緣節(jié)點(diǎn)i的發(fā)射功率.

考慮任務(wù)卸載至邊緣節(jié)點(diǎn)時(shí)存在并行計(jì)算的情況，假設(shè)模型中并行計(jì)算等待過程的能耗忽略不計(jì)，只討論產(chǎn)生的等待延時(shí)，則任務(wù)計(jì)算完成并將結(jié)果返回移動終端設(shè)備的總時(shí)延TEN計(jì)算存在2 種情況，如式（7）所示：

1）任務(wù)j抵達(dá)邊緣節(jié)點(diǎn)i后，若邊緣節(jié)點(diǎn)i當(dāng)前剩余資源滿足任務(wù)計(jì)算所用資源，即c puj≤cpui，memj≤memi.此時(shí)任務(wù)j可立即執(zhí)行，其完成時(shí)間如式（8）所示：

2）任務(wù)j抵達(dá)邊緣節(jié)點(diǎn)i后，若邊緣節(jié)點(diǎn)i當(dāng)前剩余資源小于任務(wù)計(jì)算所用資源，即cpuj>cpui，memj>memi.此時(shí)任務(wù)j需要等待此節(jié)點(diǎn)執(zhí)行完優(yōu)先級高的任務(wù)并釋放足夠的計(jì)算資源后方可參與計(jì)算，其完成時(shí)間為式（17）.等待時(shí)間可根據(jù)已建立的任務(wù)執(zhí)行矩陣得式（18）.

3.4 云中心計(jì)算模型

本系統(tǒng)中部署K個(gè)云服務(wù)器，因?yàn)樵浦行牡腃PU 資源和內(nèi)存資源遠(yuǎn)高于終端設(shè)備和邊緣節(jié)點(diǎn)，本文僅考慮云中心的3 個(gè)屬性.其中，fk表示云中心的最大計(jì)算能力，Rk為云中心與移動設(shè)備間的數(shù)據(jù)傳輸速度，Pk表示云中心的發(fā)射功率.

3.5 聯(lián)合時(shí)間與能耗的卸載決策目標(biāo)函數(shù)

綜上，可以得到所有任務(wù)的云—邊—端協(xié)同卸載執(zhí)行計(jì)算需要的時(shí)間Tall描述和能耗Eall描述分別為式（28）和式（29），其 中βED,βEN,βC∈{0,1}.規(guī)定任務(wù)在1 個(gè)位置執(zhí)行，βED,βEN,βC這3 個(gè)參數(shù)只取0 或1，根據(jù)任務(wù)的執(zhí)行位置決定云、邊、端時(shí)間與能耗的參數(shù)取值.

由式（30）可知，系統(tǒng)計(jì)算時(shí)間和能耗的優(yōu)化問題轉(zhuǎn)化為有約束條件下目標(biāo)函數(shù)Q的最優(yōu)化問題，即通過搜索卸載決策方案獲得Q最大值.優(yōu)化目標(biāo)及其約束條件如式（31）所示：

4 基于APS 算法求解卸載決策

4.1 APS 算法說明

本文設(shè)計(jì)的人工粒子蜂群算法包含5 個(gè)要素：蜜源、引領(lǐng)蜂、跟隨蜂、粒子蜂和偵察蜂.APS 采用原人工蜂群算法進(jìn)行初始化，隨機(jī)生成初始解xi(i=1,2,…,S N）.在搜索階段，引領(lǐng)蜂依據(jù)式（32）尋找新蜜源.

APS 融合ABC 算法和粒子群算法，解決了ABC搜索效率低和提前陷入局部最優(yōu)的問題.主要體現(xiàn)在引領(lǐng)蜂變異為偵查蜂階段，APS 改變了ABC 算法的位置更新策略，根據(jù)全局最優(yōu)解的位置和個(gè)體最優(yōu)解的位置來搜索蜜源，跳出局部最優(yōu).

APS 算法中引入了式（34）“全優(yōu)率”參數(shù)和粒子蜂對ABC 與PSO 進(jìn)行融合，全優(yōu)率的含義為：每一個(gè)個(gè)體在迭代過程中的適應(yīng)度值相對于全局最優(yōu)解的概率.假設(shè)連續(xù)幾代蜜源適應(yīng)度不變時(shí)所有的引領(lǐng)蜂都為粒子蜂，通過衡量全優(yōu)率，將引領(lǐng)蜂分成2 類：一類是全優(yōu)率大于1 的蜜蜂變異為偵查蜂，在當(dāng)前蜜源附近搜索；另一類全優(yōu)率小于1 的蜜蜂變異為粒子蜂，迭代按照PSO 算法的式（34）進(jìn)行迭代.

4.2 算法描述及流程

算法2.為基于APS 算法的卸載決策.

步驟1.初始化參數(shù)，包括種群規(guī)模、引領(lǐng)蜂和跟隨蜂數(shù)量、最大迭代次數(shù)、限定蜜源更新次數(shù)、搜索空間等；

步驟2.隨機(jī)生成初始蜜源，要求初始蜜源表示的卸載決策方案均滿足各任務(wù)對內(nèi)存的需求；

步驟3.進(jìn)行鄰域搜索，通過式（33）分別計(jì)算初始蜜源和領(lǐng)域更新后蜜源的適應(yīng)度，采用貪婪選擇方法保留較好的蜜源；

步驟4.根據(jù)引領(lǐng)蜂分享的信息，判斷是否為跟隨蜂分配蜜源，如果分配則記錄下最好的蜜源位置；

步驟5.如果不分配則為跟隨蜂選擇1 個(gè)蜜源，然后搜索新的蜜源計(jì)算適應(yīng)度函數(shù)進(jìn)行貪婪選擇，并保留較好的蜜源；

步驟6.判斷是否達(dá)到最大蜜源更新次數(shù)，“是”則記錄最好的蜜源位置，“否”則回到步驟5；

步驟7.為避免陷入局部最優(yōu)，進(jìn)行當(dāng)前最好蜜源的全優(yōu)率判斷，全優(yōu)率大于1 則產(chǎn)生偵查蜂，使用式（4）更新蜜源位置；全優(yōu)率小于1 則產(chǎn)生粒子蜂，使用式（5）和式（6）更新蜜源位置；

步驟8.判斷是否達(dá)到最大迭代次數(shù)，“是”則進(jìn)行步驟9，“否”則回到步驟3；

步驟9.輸出最優(yōu)卸載決策ST.

算法2 流程圖如圖4 所示.

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 仿真實(shí)驗(yàn)介紹

Fig.4 Flow chart of APS algorithm圖4 APS 算法流程圖

在本節(jié)中，部署了一個(gè)云—邊—端協(xié)同的網(wǎng)絡(luò)結(jié)構(gòu)仿真，提出的任務(wù)卸載架構(gòu)包括1 個(gè)服務(wù)半徑為1 km 的云中心服務(wù)器、4 個(gè)服務(wù)半徑為500 m 的邊緣服務(wù)器和50 個(gè)移動終端設(shè)備，總覆蓋面積為2 km×2 km.移動終端設(shè)備和邊緣服務(wù)器隨機(jī)分布在覆蓋區(qū)域中.本文采用Python 語言進(jìn)行編程仿真，仿真實(shí)驗(yàn)中使用的相關(guān)參數(shù)參考文獻(xiàn)[41]設(shè)定，如表2 所示，實(shí)驗(yàn)內(nèi)容如表3 所示.

為驗(yàn)證以上實(shí)驗(yàn)內(nèi)容對系統(tǒng)性能的影響，將本文方案與5 種任務(wù)處理方式作比較:

1）Local：任務(wù)只在終端設(shè)備進(jìn)行處理計(jì)算.

2）Edge：任務(wù)隨機(jī)卸載到邊緣節(jié)點(diǎn)上計(jì)算.

3）Cloud：任務(wù)全部卸載到云中心執(zhí)行.

4）Local-Edge：任務(wù)在本地和邊緣節(jié)點(diǎn)執(zhí)行.

5）Random：任務(wù)在端—邊—云隨機(jī)執(zhí)行.

5.2 實(shí)驗(yàn)結(jié)果與分析

5.2.1 θ1，θ2的取值實(shí)驗(yàn)

圖5 和圖6 分別表征了系統(tǒng)在處理100 個(gè)隨機(jī)任務(wù)的情況下，θ1取不同的值時(shí)系統(tǒng)的計(jì)算時(shí)間和能耗情況.從圖5 和圖6 可知，當(dāng) θ1=0.6 時(shí)，系統(tǒng)計(jì)算時(shí)間最短；θ1=0.5 時(shí)，系統(tǒng)能耗最低.同時(shí)從2 個(gè)結(jié)果圖的變化趨勢可以看出，θ1的取值對于系統(tǒng)計(jì)算時(shí)間的影響較大，能耗的變化相比于計(jì)算時(shí)間來講比較平緩，尤其是當(dāng) θ1=0.4，0.5，0.6 時(shí)，能耗的變化微小.因此綜合以上情況分析，取 θ1=0.6 時(shí)具有最合適的延時(shí)與能耗表現(xiàn).

Table 2 Experimental Parameters Setting表2 實(shí)驗(yàn)參數(shù)設(shè)定

Table 3 Experimental Contents Setting表3 實(shí)驗(yàn)內(nèi)容設(shè)定

Fig.5 The relationship of value θ1 and the systematic calculation time圖5 θ1的取值與系統(tǒng)計(jì)算時(shí)間的關(guān)系

Fig.6 The relationship of value θ1 and the systematic energy consumption圖6 θ1的取值與系統(tǒng)能耗的關(guān)系

5.2.2 卸載決策算法驗(yàn)證

在處理不同的任務(wù)量并經(jīng)過100 次迭代計(jì)算后，4 種卸載決策算法的計(jì)算時(shí)間和能耗對比分別如圖7和圖8 所示.由圖7 可知，當(dāng)任務(wù)數(shù)量較少時(shí)，APS 算法雖然具備一定的優(yōu)越性，但同比ABC 和PSO 差距較?。浑S著任務(wù)數(shù)量的增多，APS 相比于ABC 算法、PSO 算法和RAN 算法，計(jì)算時(shí)間分別降低了19.6%，29.6%，51.9%.圖8 展示了系統(tǒng)能耗的變化，對比不同數(shù)量的任務(wù)，APS 算法的能耗都在不同程度上降低，其中，相比于ABC 算法能耗最大能降低12.8%，相比于PSO 算法能耗最大能降低40.3%，相比于RAN 算法能耗最大能降低50.2%.由此可見，APS 算法具有不可比擬的優(yōu)越性，極大提升了整個(gè)系統(tǒng)性能.

Fig.7 Calculation time of four algorithms for different numbers of tasks圖7 不同任務(wù)數(shù)量下4 種算法的計(jì)算時(shí)間

Fig.8 Systematic energy consumption of four algorithms for different numbers of tasks圖8 不同任務(wù)數(shù)量下4 種算法的系統(tǒng)能耗

5.2.3 用戶數(shù)量對系統(tǒng)的影響

圖9 和圖10 分別評估了終端設(shè)備的數(shù)量對系統(tǒng)總時(shí)延和系統(tǒng)能耗的影響.從圖9 中可以看出，所有方案的總時(shí)延都隨著終端設(shè)備數(shù)量的增加而上升，但Joint 的總時(shí)延始終是最小的.當(dāng)終端設(shè)備數(shù)量增多時(shí)，所產(chǎn)生的任務(wù)需要的計(jì)算資源也迅速增多，結(jié)合任務(wù)的數(shù)據(jù)量等特性，系統(tǒng)依據(jù)卸載模型將一些任務(wù)從終端設(shè)備卸載到邊緣節(jié)點(diǎn)或云中心處理，以獲得最小的服務(wù)時(shí)延.此外，發(fā)現(xiàn)當(dāng)用終端數(shù)量逐漸增多時(shí)，邊緣節(jié)點(diǎn)計(jì)算方案的總時(shí)延大于本地計(jì)算方案的總時(shí)延，這是由于任務(wù)在卸載過程中信道和邊緣節(jié)點(diǎn)計(jì)算資源的競爭沒有遵循合理的卸載順序，導(dǎo)致任務(wù)在傳輸過程和計(jì)算過程都存在不必要的等待環(huán)節(jié)，因此時(shí)延越來越高.

Fig.9 Effect of the number of end users on the total systematic delay圖9 終端用戶數(shù)量對系統(tǒng)總時(shí)延的影響

Fig.10 Effect of the number of end users on the systematic energy consumption圖10 終端用戶數(shù)量對系統(tǒng)能耗的影響

從圖10 中可以看出，系統(tǒng)能耗也隨著終端數(shù)量的增多而增多，且Joint 的能耗表現(xiàn)具有很強(qiáng)的優(yōu)越性.Edge 的能耗低于Cloud 的能耗的原因在于：不同于系統(tǒng)時(shí)延，任務(wù)卸載到邊緣節(jié)點(diǎn)的方案存在滯后等待，當(dāng)任務(wù)到達(dá)Edge 后，等待過程的能耗可忽略不計(jì).相比于遠(yuǎn)距離的Cloud，Edge 的傳輸能耗顯著降低，因此，總體上Edge 的能耗低于Cloud 的能耗.

5.2.4 任務(wù)的配置文件對系統(tǒng)性能的影響

這里評估了任務(wù)所需計(jì)算資源量和任務(wù)輸入數(shù)據(jù)量對系統(tǒng)總體時(shí)延和系統(tǒng)能耗的影響（終端設(shè)備數(shù)量為30）.2 種配置下各方案的時(shí)延表現(xiàn)如圖11 和圖13 所示.6 種方案的總體時(shí)延都隨任務(wù)計(jì)算資源量的增加而增加，但Joint 的總時(shí)延始終是最小的.由于本地計(jì)算不涉及任務(wù)的卸載和傳輸，因此時(shí)延保持為一個(gè)穩(wěn)定的數(shù)值.而 Edge 模式隨著卸載任務(wù)和數(shù)據(jù)量的增加時(shí)，出現(xiàn)爭奪通信資源和邊緣節(jié)點(diǎn)計(jì)算資源的情況，因此其時(shí)延要高于云計(jì)算和本地計(jì)算.從2 種任務(wù)配置因素得知，本文系統(tǒng)可快速處理一些要求計(jì)算資源量高和輸入數(shù)據(jù)量高的任務(wù).

Fig.11 Effect of computing resources required by tasks on systematic delay圖11 任務(wù)所需計(jì)算資源對系統(tǒng)時(shí)延的影響

如圖12 所示，當(dāng)任務(wù)所需計(jì)算資源量增加時(shí)，6 種方案的能耗隨之上升，但Joint 的能耗遠(yuǎn)小于其他系統(tǒng)的能耗.通過計(jì)算平均任務(wù)所需資源量，Joint能耗分別比Random 降低了58.28%，比Local 降低55.60%，比Cloud 降低43.54%，比Edge 降低24.46%，比Local-Edge 降低16%.由圖14 得，隨著任務(wù)輸入數(shù)據(jù)量的增加，本地計(jì)算不涉及數(shù)據(jù)輸入，能耗逐漸穩(wěn)定增大，Joint 尤其表現(xiàn)優(yōu)越.因此，當(dāng)面臨大數(shù)據(jù)量輸入時(shí)，Joint 的能耗表現(xiàn)遠(yuǎn)遠(yuǎn)優(yōu)于其他模式，其中相比Random 最高降低了52.72%，比Local 最高降低29.20%，比Cloud 最高降低26.92%，比Edge 最高降低22.45%，比Local-Edge 最高降低19.82%.

Fig.12 Effect of computing resources required by tasks on systematic energy consumption圖12 任務(wù)所需計(jì)算資源對系統(tǒng)能耗的影響

Fig.13 Effect of the amount of date input by tasks on systematic delay圖13 任務(wù)輸入數(shù)據(jù)量對系統(tǒng)時(shí)延的影響

Fig.14 Effect of the amount of date input by tasks on the systematic energy consumption圖14 任務(wù)輸入數(shù)據(jù)量對系統(tǒng)能耗的影響

5.2.5 任務(wù)的固定屬性對系統(tǒng)性能的影響

Fig.15 Effect of the maximum delay of tasks on the systematic delay圖15 任務(wù)最大延遲對系統(tǒng)延時(shí)的影響

這里評估了任務(wù)最大時(shí)延和任務(wù)所需最小計(jì)算能力對系統(tǒng)時(shí)延和能耗的影響.如圖15 所示，當(dāng)任務(wù)的時(shí)延要求逐漸增大時(shí)，將有更多任務(wù)在本地執(zhí)行，同時(shí)所需計(jì)算資源量大的任務(wù)卸載到邊緣節(jié)點(diǎn)，因此系統(tǒng)總時(shí)延隨著時(shí)延容忍的增加而減少.Joint 相比其他方案的總時(shí)延總是保持最小，圖16 中能耗也呈現(xiàn)出和時(shí)延狀態(tài)相似的表現(xiàn)，Joint 方案對應(yīng)總體時(shí)延和能耗始終維持低數(shù)值，具有一定優(yōu)越性.

Fig.16 Effect of the maximum delay of tasks on the systematic energy consumption圖16 任務(wù)最大延遲對系統(tǒng)能耗的影響

圖17 和圖18 反映了任務(wù)所需的最小計(jì)算能力對系統(tǒng)的影響.由圖17 得知，當(dāng)最小所需計(jì)算能力不斷增加時(shí)，任務(wù)的執(zhí)行位置越來越受限，從而導(dǎo)致本地設(shè)備不能參與計(jì)算，所有任務(wù)為了卸載至邊緣服務(wù)器或者云中心，全部都去競爭有限的信道資源與網(wǎng)絡(luò)資源，因此系統(tǒng)總體時(shí)延性能變差.從圖18 可知，雖然Joint 的能耗在高計(jì)算能力需求時(shí)在一定程度上與邊緣計(jì)算模式和云計(jì)算相近，但充分滿足了系統(tǒng)時(shí)延的要求.綜上所述，與其他5 種方案相比，Joint 方案在大規(guī)模計(jì)算情況下具備很強(qiáng)的自適應(yīng)性.

Fig.17 Effect of the minimum computing power required by tasks on the systematic delay圖17 任務(wù)所需最小計(jì)算能力對系統(tǒng)延時(shí)的影響

Fig.18 Effect of the minimum computing power required by tasks on the systematic energy consumption圖18 任務(wù)所需最小計(jì)算能力對系統(tǒng)能耗的影響

5.2.6 終端最大發(fā)射功率對系統(tǒng)性能的影響

Fig.19 Effect of the maximum transmitting power of end on the systematic delay圖19 終端設(shè)備最大發(fā)射功率對系統(tǒng)延遲的影響

Fig.20 Effect of the maximum transmitting power of end on the systematic energy consumption圖20 終端設(shè)備最大發(fā)射功率對系統(tǒng)能耗的影響

圖19 和圖20 分別顯示了終端設(shè)備最大發(fā)射功率對系統(tǒng)時(shí)延與能耗的影響.由圖19 可知隨著終端設(shè)備最大發(fā)射功率的不斷增加，發(fā)射功率的范圍變大，終端設(shè)備的可用功率相應(yīng)增加，因此任務(wù)卸載速度變快，系統(tǒng)總時(shí)延變小.由圖20 得知，終端最大發(fā)射功率增加幅度小，但系統(tǒng)時(shí)延下降較快，因此系統(tǒng)能耗總體上呈下降趨勢.Joint 方案相比于其他方案不論是時(shí)延還是能耗都顯現(xiàn)出一定的優(yōu)勢，終端設(shè)備最大發(fā)射功率在合理范圍內(nèi)調(diào)整時(shí)，Joint 系統(tǒng)性能始終最優(yōu).

6 總結(jié)

在本文中，我們部署了一個(gè)云—邊—端協(xié)同計(jì)算架構(gòu)，此架構(gòu)可實(shí)現(xiàn)移動終端設(shè)備的任務(wù)擇優(yōu)在本地、邊緣節(jié)點(diǎn)或云中心處理.本文在以往研究成果的基礎(chǔ)上考慮了任務(wù)之間存在的依賴關(guān)系、任務(wù)并行計(jì)算以及任務(wù)結(jié)果回程問題，基于此分別建立了端、邊、云任務(wù)計(jì)算模型，設(shè)計(jì)聯(lián)合優(yōu)化時(shí)延與能耗的目標(biāo)函數(shù)；其次，在ABC 算法和PSO 算法基礎(chǔ)上引入全優(yōu)率指數(shù)與粒子蜂，設(shè)計(jì)了APS 算法求解聯(lián)合優(yōu)化時(shí)延與能耗的任務(wù)卸載決策；最后，在多接入情況下，構(gòu)造最小化任務(wù)計(jì)算時(shí)間和能耗的目標(biāo)問題，在評估各項(xiàng)資源的情況下實(shí)現(xiàn)自適應(yīng)地卸載任務(wù).仿真結(jié)果表明，本文方案在多終端、多任務(wù)情況下可提供低時(shí)延、低能耗的服務(wù).未來本研究計(jì)劃通過聯(lián)合優(yōu)化時(shí)延和能耗進(jìn)一步優(yōu)化任務(wù)執(zhí)行矩陣，并探索5G網(wǎng)絡(luò)環(huán)境下，結(jié)合人工智能技術(shù)動態(tài)預(yù)測和評估計(jì)算資源的利用和服務(wù)質(zhì)量.

作者貢獻(xiàn)聲明：張文柱指導(dǎo)論文寫作，并參與實(shí)驗(yàn)設(shè)計(jì)和實(shí)驗(yàn)數(shù)據(jù)分析；余靜華完成數(shù)據(jù)分析和論文的寫作.