基于服務(wù)更新的異構(gòu)任務(wù)卸載方法

摘 要：邊緣計(jì)算將存儲(chǔ)和計(jì)算資源下沉到網(wǎng)絡(luò)邊緣，用戶可將時(shí)延敏感型和計(jì)算密集型應(yīng)用程序的任務(wù)卸載到邊緣服務(wù)器執(zhí)行，從而降低時(shí)延和能耗。已有的任務(wù)卸載研究通常忽略卸載任務(wù)的異構(gòu)性，且默認(rèn)邊緣服務(wù)器緩存的服務(wù)能夠長(zhǎng)期滿足用戶的服務(wù)需求。然而，不同的任務(wù)需要不同的服務(wù)提供執(zhí)行環(huán)境，且邊緣服務(wù)器資源受限只能部署少量服務(wù)。因此，為了最小化時(shí)延和能耗（即成本），提出了一種聯(lián)合服務(wù)更新和云邊端協(xié)作的異構(gòu)任務(wù)卸載方法。首先，通過(guò)改進(jìn)的頁(yè)面置換算法，預(yù)測(cè)出潛在的用戶服務(wù)需求量，及時(shí)更新邊緣服務(wù)器的服務(wù)。其次，在云邊端協(xié)作基礎(chǔ)上，通過(guò)改進(jìn)的貪婪算法完成任務(wù)卸載，且使得成本最小。最后，基于真實(shí)數(shù)據(jù)集進(jìn)行了充分的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與對(duì)比方法相比，所提方法能夠降低成本7%～16%。

關(guān)鍵詞：邊緣計(jì)算； 云邊端協(xié)作； 服務(wù)更新； 改進(jìn)的頁(yè)面置換算法； 改進(jìn)的貪婪算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2024）08-033-2481-08

doi：10.19734/j.issn.1001-3695.2023.12.0605

Heterogeneous task offloading method based on service update

Han Chaochen， Zhang Junna， Wang Xinxin， Yuan Peiyan， Zhao Xiaoyan， Liu Chunhong

（College of Computer & Information Engineering， Henan Normal University， Xinxiang Henan 453007， China）

Abstract：Edge computing brings storage and compute resources down to the edge of the network. Users can offload latency-sensitive and compute-intensive applications to the edge server for execution， thereby reducing latency and energy consumption. Existing task offload studies often fall short. The first point is that the existing research on task offloading often overlooks the heterogeneity of offloading tasks. The second point is that the default edge server caching service can meet the long-term service needs of users. However， different tasks require different services to provide execution environments. And the finite resources of edge servers can only deploy a small number of services. Therefore， to minimize latency and energy consumption（i.e.cost）， this article proposed a heterogeneous task offloading method that combined service updates and cloud edge collaboration. The method consisted two following main parts. The first part was an improved page replacement algorithm. The algorithm could predict the potential user service demand and updated the service of the edge server in time. The second part was the collaboration between the cloud-side ends， offloading tasks through collaboration and keeping minimum total costs. Finally， it conducted thorough experiments using real datasets. The experimental results show that the proposed method can reduce the total cost by 7% to 16% compared to the comparison methods.

Key words：edge computing; cloud edge collaboration; service update; improved page replacement algorithm; improved greedy algorithm

0 引言

隨著通信技術(shù)的快速發(fā)展和萬(wàn)物互聯(lián)時(shí)代的到來(lái)，推動(dòng)了認(rèn)知輔助、虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)等時(shí)延敏感型和計(jì)算密集型應(yīng)用程序的發(fā)展，也使得智能移動(dòng)設(shè)備的數(shù)量呈指數(shù)增長(zhǎng)［1］。根據(jù)思科最新的《年度互聯(lián)網(wǎng)報(bào)告》的分析和預(yù)測(cè)，2023年將有293億臺(tái)聯(lián)網(wǎng)移動(dòng)設(shè)備，預(yù)計(jì)至2030年將有5 000億臺(tái)［2］。然而，由于移動(dòng)設(shè)備有限的電池容量、計(jì)算和存儲(chǔ)資源，直接運(yùn)行上述應(yīng)用程序會(huì)產(chǎn)生較高的時(shí)延和能耗，使得用戶體驗(yàn)極差［3］。邊緣計(jì)算（edge computing，EC）通過(guò)在網(wǎng)絡(luò)邊緣部署邊緣服務(wù)器（edge server，ES），為用戶提供計(jì)算和存儲(chǔ)資源。移動(dòng)設(shè)備可將部分或全部任務(wù)卸載到ES處理，緩解移動(dòng)設(shè)備在電池容量、計(jì)算和存儲(chǔ)資源等方面的不足，從而提升用戶體驗(yàn)。

近年來(lái)，許多研究人員針對(duì)任務(wù)卸載進(jìn)行了研究。文獻(xiàn)［4］研究了邊緣計(jì)算中的單一類型任務(wù)卸載問(wèn)題，為了提升用戶體驗(yàn)，以最小化所有移動(dòng)終端的時(shí)延和能耗為目標(biāo)，提出了一種粒子群優(yōu)化任務(wù)調(diào)度算法，獲得了最優(yōu)的任務(wù)卸載決策。Chu等人［5］針對(duì)物聯(lián)網(wǎng)環(huán)境下的單一類型任務(wù)卸載問(wèn)題，提出了一種基于深度學(xué)習(xí)的任務(wù)卸載算法，對(duì)每個(gè)用戶的任務(wù)卸載比例進(jìn)行動(dòng)態(tài)微調(diào)，從而降低成本。然而，上述文獻(xiàn)只考慮了單一類型卸載的任務(wù)，而沒(méi)有考慮到卸載任務(wù)的異構(gòu)性，即同一用戶或不同用戶在不同區(qū)域、不同時(shí)間內(nèi)會(huì)產(chǎn)生不同類型的卸載任務(wù)。對(duì)于不同類型的卸載任務(wù)來(lái)說(shuō)，需要不同類型的服務(wù)為其提供執(zhí)行環(huán)境。也就是說(shuō)，同一用戶或者不同用戶在不同區(qū)域、不同時(shí)間內(nèi)的服務(wù)需求不同。因此，為了更好地滿足用戶的服務(wù)需求，本文綜合考慮用戶卸載任務(wù)的異構(gòu)性，通過(guò)在ES緩存不同類型的服務(wù)，可以及時(shí)執(zhí)行用戶的卸載任務(wù)，從而提高用戶的服務(wù)滿意度。

Chen等人［6］認(rèn)為ES可以滿足用戶所有的服務(wù)需求，針對(duì)動(dòng)態(tài)邊緣計(jì)算系統(tǒng)中的任務(wù)卸載調(diào)度問(wèn)題，提出了一種在線動(dòng)態(tài)任務(wù)卸載算法，通過(guò)權(quán)衡系統(tǒng)成本和隊(duì)列穩(wěn)定性來(lái)作出任務(wù)卸載決策，從而得到了最優(yōu)任務(wù)卸載決策。文獻(xiàn)［7］針對(duì)動(dòng)態(tài)任務(wù)卸載問(wèn)題，在ES緩存有大量流行度較高的服務(wù)場(chǎng)景下，以最大化任務(wù)完成率和最小化能耗為目標(biāo)，提出了一種基于深度強(qiáng)化學(xué)習(xí)的動(dòng)態(tài)任務(wù)卸載算法，可以根據(jù)復(fù)雜的環(huán)境調(diào)整并獲得最優(yōu)的任務(wù)卸載決策，提高用戶體驗(yàn)。然而，上述文獻(xiàn)只考慮到ES緩存了大量流行度較高的服務(wù)，而沒(méi)有考慮用戶的服務(wù)需求會(huì)發(fā)生改變，且忽略了ES是否具有充足的存儲(chǔ)資源。現(xiàn)實(shí)生活中，由于用戶的卸載任務(wù)具有異構(gòu)性，即隨著時(shí)間的推移和用戶的移動(dòng)，用戶的服務(wù)需求處于動(dòng)態(tài)變化之中；且ES的存儲(chǔ)資源受限，僅能緩存部分服務(wù)，只能為部分卸載任務(wù)提供執(zhí)行環(huán)境。所以，本文將時(shí)間劃分為時(shí)間片，根據(jù)上一時(shí)間片內(nèi)用戶的服務(wù)偏好，在滿足ES存儲(chǔ)資源的約束下更新ES緩存的服務(wù)，保證ES緩存有流行度較高的服務(wù)，可以及時(shí)為卸載任務(wù)提供執(zhí)行環(huán)境，從而促進(jìn)EC的長(zhǎng)期發(fā)展。

在默認(rèn)ES具有無(wú)限資源的情形下，文獻(xiàn)［8］研究了邊緣計(jì)算中的服務(wù)緩存和任務(wù)卸載問(wèn)題，考慮到任務(wù)請(qǐng)求的異構(gòu)性，以最小化系統(tǒng)的平均時(shí)延為目標(biāo)，提出了一種高效的協(xié)同服務(wù)緩存和任務(wù)卸載算法，獲得了最優(yōu)的服務(wù)緩存和任務(wù)卸載決策。Tian等人［9］研究了邊緣計(jì)算中服務(wù)緩存問(wèn)題，其認(rèn)為ES資源不受限制，提出了一種分布式協(xié)作服務(wù)緩存方案。通過(guò)將服務(wù)緩存問(wèn)題建模為馬爾可夫決策過(guò)程，優(yōu)化時(shí)延和提高命中率，從而提高服務(wù)質(zhì)量并減輕核心網(wǎng)絡(luò)的負(fù)擔(dān)。然而，上述文獻(xiàn)均認(rèn)為ES的資源是無(wú)限的，而沒(méi)有考慮到ES的計(jì)算資源是否足以執(zhí)行用戶的卸載任務(wù)。事實(shí)上，ES的計(jì)算資源是有限的，在滿足ES服務(wù)約束的前提下，還需要考慮ES是否具有充足的計(jì)算資源。因此，本文通過(guò)ES之間的水平協(xié)作和計(jì)算節(jié)點(diǎn)（云服務(wù)器、邊緣服務(wù)器和移動(dòng)設(shè)備）之間的垂直協(xié)作，為用戶的卸載任務(wù)分配到最佳的計(jì)算節(jié)點(diǎn)執(zhí)行，可以充分利用ES的資源，同樣，也可以保證用戶所有卸載任務(wù)都能被成功執(zhí)行，從而不僅可以提高用戶服務(wù)滿意度，也可以促進(jìn)EC的長(zhǎng)期發(fā)展。

綜上所述，任務(wù)卸載的相關(guān)研究往往忽略卸載任務(wù)的異構(gòu)性，沒(méi)有考慮到用戶的服務(wù)需求是動(dòng)態(tài)變化的，且默認(rèn)ES具有無(wú)限的資源。為了解決上述局限性，本文在ES服務(wù)緩存有限和資源受限的情況下，兼顧服務(wù)更新和云邊端協(xié)作，研究了權(quán)衡時(shí)延和能耗（即成本）的異構(gòu)任務(wù)卸載問(wèn)題。由于該問(wèn)題是NP-hard問(wèn)題，無(wú)法直接在多項(xiàng)式中求解，所以本文提出了一種聯(lián)合服務(wù)更新和協(xié)作任務(wù)卸載的方法（joint service update and collaborative task offloading，JSU-TO），來(lái)求解該問(wèn)題的近似最優(yōu)解。

本文的主要貢獻(xiàn)包括以下四個(gè)方面：

a）考慮到卸載任務(wù)的異構(gòu)性以及用戶的服務(wù)偏好，根據(jù)服務(wù)的流行度提出了ILFU算法。根據(jù)提出的ILFU算法來(lái)比較上一時(shí)間片內(nèi)服務(wù)的流行度，篩選出流行度較高的信息，在滿足ES存儲(chǔ)資源的約束下更新ES的服務(wù)，使ES緩存有多種類型且流行度較高的服務(wù)，從而可以執(zhí)行更多卸載任務(wù)，降低任務(wù)執(zhí)行成本。

b）在ES存儲(chǔ)和計(jì)算資源受限的約束下，建立了云邊端網(wǎng)絡(luò)模型；通過(guò)ES之間的水平協(xié)作和云邊端之間的垂直協(xié)作執(zhí)行用戶的卸載任務(wù)。不僅可以充分利用ES的資源，也可以保證用戶所有卸載任務(wù)都能被成功執(zhí)行，從而進(jìn)一步提高用戶服務(wù)滿意度，促進(jìn)EC的長(zhǎng)期發(fā)展。

c）若一個(gè)任務(wù)可以卸載到多個(gè)ES執(zhí)行，為了降低任務(wù)的執(zhí)行時(shí)延和能耗，且充分利用ES的資源，利用IGA算法為用戶選擇當(dāng)前服務(wù)部署下最佳的任務(wù)卸載決策，最小化任務(wù)執(zhí)行成本。

d）基于真實(shí)數(shù)據(jù)集，對(duì)本文方法與已有的方法進(jìn)行了充分的性能評(píng)估，實(shí)驗(yàn)結(jié)果表明，本文方法比對(duì)比方法在成本上減少了7%～16%。

1 系統(tǒng)建模和問(wèn)題描述

1.1 云邊端網(wǎng)絡(luò)模型

本文建立的云邊端網(wǎng)絡(luò)模型如圖1所示，模型由云服務(wù)器、ES和移動(dòng)設(shè)備三種不同計(jì)算節(jié)點(diǎn)組成，三者形成協(xié)作域，均可執(zhí)行用戶的卸載任務(wù)。用戶在運(yùn)行單個(gè)應(yīng)用程序時(shí)生成若干個(gè)不同的任務(wù)，每個(gè)任務(wù)需要特定的服務(wù)支持才能被成功執(zhí)行。云服務(wù)器緩存有所有類型的服務(wù)，可以為所有卸載任務(wù)提供執(zhí)行環(huán)境。ES因資源受限只能緩存少量服務(wù)，僅能執(zhí)行部分卸載任務(wù)。ES無(wú)法執(zhí)行的任務(wù)，可通過(guò)將任務(wù)轉(zhuǎn)發(fā)到云服務(wù)器執(zhí)行。用戶的任務(wù)也可以在移動(dòng)設(shè)備執(zhí)行。圖1虛線框內(nèi)表示ES緩存的服務(wù)，顏色形狀各不相同的圖形表示不同的服務(wù)。

云服務(wù)器用C表示，云服務(wù)器的位置距離用戶較遠(yuǎn)，意味著用戶與云服務(wù)器之間會(huì)產(chǎn)生較大的傳輸時(shí)延和能耗。ES的集合用E={e1，e2，e3，…，eL}表示，L表示ES的數(shù)量。不同ES具有不同的通信能力、計(jì)算和存儲(chǔ)資源，每個(gè)ES緩存有不同數(shù)量的服務(wù)。處于同一集群內(nèi)的ES通過(guò)無(wú)線信道連接，彼此貢獻(xiàn)緩存服務(wù)，形成共享資源池，通過(guò)水平協(xié)作執(zhí)行卸載任務(wù)［10］。若ES沒(méi)有緩存卸載任務(wù)所需的服務(wù)，或其計(jì)算資源不足以執(zhí)行卸載任務(wù)，ES可通過(guò)有線網(wǎng)絡(luò)將任務(wù)轉(zhuǎn)發(fā)到云服務(wù)器，通過(guò)垂直協(xié)作執(zhí)行［11］。

用戶的集合用U={u1，u2，u3，…，un}表示，n為用戶數(shù)量。用戶隨機(jī)分布，若用戶處于多個(gè)ES的覆蓋范圍內(nèi)，則用戶可以通過(guò)移動(dòng)或無(wú)線網(wǎng)絡(luò)向ES卸載任務(wù)。

用戶運(yùn)行應(yīng)用程序時(shí)生成I個(gè)不同的任務(wù)，所有用戶產(chǎn)生卸載任務(wù)的集合用I={i1，i2，i3，…，iq}表示，q表示任務(wù)的數(shù)量。由于任務(wù)具有異構(gòu)性，即同一用戶或不同用戶在不同區(qū)域、不同時(shí)間內(nèi)會(huì)產(chǎn)生不同類型的卸載任務(wù)，所以，需要提供不同類型的服務(wù)支持，同樣需要根據(jù)ES緩存的服務(wù)，卸載任務(wù)的特征以及ES的響應(yīng)時(shí)間、工作負(fù)載、延遲和能耗等參數(shù)［12］，將用戶的任務(wù)卸載到一個(gè)最佳的計(jì)算節(jié)點(diǎn)執(zhí)行。且不同任務(wù)需要不同的服務(wù)支持，任務(wù)只能被卸載到緩存有與卸載任務(wù)對(duì)應(yīng)服務(wù)的ES執(zhí)行［13］，任務(wù)之間彼此獨(dú)立，若計(jì)算節(jié)點(diǎn)資源允許，任務(wù)之間可以并行執(zhí)行。

1.2 時(shí)延能耗模型

在本文的任務(wù)和時(shí)延能耗模型中，首先，所有用戶可以并行執(zhí)行運(yùn)行程序，產(chǎn)生卸載任務(wù)，從而本文網(wǎng)絡(luò)模型可以并行執(zhí)行卸載任務(wù)。然后，在時(shí)延和能耗模型中具體對(duì)一個(gè)用戶運(yùn)行一個(gè)應(yīng)用程序產(chǎn)生的任務(wù)進(jìn)行分析，根據(jù)具體情況計(jì)算出任務(wù)的時(shí)延和能耗；所有用戶運(yùn)行應(yīng)用程序產(chǎn)生的卸載任務(wù)被成功執(zhí)行的過(guò)程都符合上述時(shí)延能耗分析過(guò)程。最后，計(jì)算出所有用戶運(yùn)行應(yīng)用程序時(shí)產(chǎn)生的卸載任務(wù)的時(shí)延和能耗。具體分析過(guò)程如下：

用戶的任務(wù)可選擇在移動(dòng)設(shè)備、卸載至ES或云服務(wù)器執(zhí)行，因此討論任務(wù)在三種不同計(jì)算節(jié)點(diǎn)產(chǎn)生的執(zhí)行時(shí)延和能耗，以及任務(wù)在傳輸過(guò)程中產(chǎn)生的傳輸時(shí)延和能耗。

a）任務(wù)在移動(dòng)設(shè)備執(zhí)行

移動(dòng)設(shè)備u具有一定的計(jì)算能力，可以執(zhí)行卸載任務(wù)i，其中i∈I，此時(shí)產(chǎn)生的執(zhí)行時(shí)延Tloci和執(zhí)行能耗Eloci分別為

Tloci=Rifu，Eloci=PuTloci（1）

其中：Ri為任務(wù)i所需的計(jì)算量；fu為移動(dòng)設(shè)備u的計(jì)算能力，受最大計(jì)算能力fmax的限制；Pu為移動(dòng)設(shè)備u的計(jì)算功率。

b）任務(wù)卸載至ES執(zhí)行

當(dāng)任務(wù)i被卸載到ej執(zhí)行時(shí)，需要考慮任務(wù)i上傳到ej的傳輸時(shí)延和能耗，在ej的執(zhí)行時(shí)延和能耗。與任務(wù)的上傳數(shù)據(jù)量相比，返回任務(wù)結(jié)果的數(shù)據(jù)量較小，產(chǎn)生的返回時(shí)延和能耗也相對(duì)較小，因此，本文忽略返回時(shí)延和能耗。那么，任務(wù)i卸載至ej的傳輸時(shí)延TCeji和傳輸能耗ECeji分別為

TCeji=GiRej（2）

ECeji=PuTCeji（3）

其中：Gi表示任務(wù)i的輸入數(shù)據(jù)量；Pu為移動(dòng)設(shè)備u向ES上傳的功率；Rej表示移動(dòng)設(shè)備u至ES的傳輸速率，可通過(guò)香農(nóng)公式［14］計(jì)算得到，即

Rej=Wi，ejlog2（1+Pi，ejHi，ejN）（4）

其中：Wi，ej為信道帶寬；Pi，ej為移動(dòng)設(shè)備的發(fā)射功率；Hi，ej為移動(dòng)設(shè)備和ej的信道增益；N為數(shù)據(jù)傳輸時(shí)產(chǎn)生的信噪功率。同時(shí)，在ES執(zhí)行時(shí)產(chǎn)生的執(zhí)行時(shí)延TReji和執(zhí)行能耗EReji分別為

TReji=Rifej（5）

EReji=PejTReji（6）

其中：Ri表示任務(wù)i所需的計(jì)算量；fej表示ej的計(jì)算能力；Pej為ES的計(jì)算功率。因此，任務(wù)i在ej執(zhí)行時(shí)產(chǎn)生的總時(shí)延Teji和總能耗Eeji分別為

Teji=TCeji+TReji（7）

Eeji=ECeji+EReji（8）

若ej無(wú)法執(zhí)行任務(wù)i，但是協(xié)作域中的ek可以執(zhí)行，由ej將任務(wù)i轉(zhuǎn)發(fā)到ek，通過(guò)ES之間的水平協(xié)作執(zhí)行。此時(shí)產(chǎn)生的時(shí)延和能耗包括：任務(wù)i上傳到ej的傳輸時(shí)延和能耗、ES之間的傳輸時(shí)延和能耗、在ek的執(zhí)行時(shí)延和能耗，以及將任務(wù)結(jié)果反饋給用戶的返回時(shí)延和能耗四部分。與任務(wù)的上傳數(shù)據(jù)量相比，返回任務(wù)結(jié)果的數(shù)據(jù)量較小，產(chǎn)生的返回時(shí)延和能耗也相對(duì)較小，本文同樣也忽略返回時(shí)延和能耗。因此，由ej將任務(wù)i轉(zhuǎn)發(fā)到ek產(chǎn)生的傳輸時(shí)延TCej，eki和傳輸能耗ECej，eki分別為

TCej，eki=GiRej，ek（9）

ECej，eki=PtTCej，eki（10）

其中：Rej，ek表示ej到ek的傳輸速率，可由香農(nóng)公式計(jì)算得到，Pt為ES之間的傳輸功率。

Rej，ek=Wej，eklog2（1+Pej，ekHej，ekN）（11）

其中：Wej，ek為ej和ek之間的信道帶寬;Pej，ek為ej和ek之間的發(fā)射功率;Hej，ek為ej和ek之間的信道增益。在ek的執(zhí)行時(shí)延TReki和執(zhí)行能耗EReki分別為

TReki=Rifek（12）

EReki=PekTReki（13）

其中：fek表示ek的計(jì)算能力；Pek為ek的計(jì)算功率。

那么，任務(wù)i由ej轉(zhuǎn)發(fā)到ek執(zhí)行時(shí)產(chǎn)生的總時(shí)延Tiej，ek和總能耗Eiej，ek分別為

Tiej，ek=TCiej+TCiej，ek+TRiek（14）

Eej，eki=ECeji+ECej，eki+EReki（15）

綜上所述，當(dāng)任務(wù)i在ES執(zhí)行時(shí)存在兩種情形：a）用戶處于ej的覆蓋范圍內(nèi)，且ej可以執(zhí)行任務(wù)i；b）用戶處于ej的覆蓋范圍內(nèi)，而ej無(wú)法執(zhí)行任務(wù)i，需要將任務(wù)i轉(zhuǎn)發(fā)給協(xié)作域中其他的ES，通過(guò)ES之間的水平協(xié)作執(zhí)行。因此，本文用二進(jìn)制變量γei（γei∈{0，1}）表示任務(wù)i在ES的執(zhí)行方式。γei=1時(shí)，表示任務(wù)i可以在ej執(zhí)行；γei=0時(shí)，表示任務(wù)i通過(guò)ES之間的協(xié)作執(zhí)行。所以，任務(wù)i卸載到ES執(zhí)行時(shí)產(chǎn)生的總時(shí)延和總能耗包括兩部分，分別是在ej執(zhí)行產(chǎn)生的總時(shí)延Teji和總能耗Eeji，及ES之間協(xié)作執(zhí)行產(chǎn)生的總時(shí)延Tej，eki和總能耗Eej，eki。因此，在ES執(zhí)行產(chǎn)生的總時(shí)延Tesi和總能耗Eesi分別為

Tesi=γeiTiej+（1-γei）Tiej，ek（16）

Eesi=γeiEeji+（1-γei）Eej，eki（17）

c）任務(wù)卸載至云服務(wù)器執(zhí)行

當(dāng)任務(wù)i被卸載到云服務(wù)器執(zhí)行時(shí)，首先將任務(wù)i上傳至附近的ES，再由ES通過(guò)有線信道轉(zhuǎn)發(fā)給云服務(wù)器。當(dāng)任務(wù)i需要轉(zhuǎn)發(fā)至云服務(wù)器時(shí)，相對(duì)于ES到云的傳輸時(shí)延，ES轉(zhuǎn)發(fā)任務(wù)前的等待時(shí)延相對(duì)較小可以忽略不計(jì)［15］。考慮到云服務(wù)器有著較強(qiáng)的計(jì)算能力，執(zhí)行時(shí)延相對(duì)于傳輸時(shí)延來(lái)說(shuō)可以忽略不計(jì)。因此，本文忽略在云服務(wù)器執(zhí)行時(shí)產(chǎn)生的執(zhí)行時(shí)延和能耗。當(dāng)任務(wù)卸載到云服務(wù)器執(zhí)行時(shí)，產(chǎn)生的時(shí)延和能耗主要包括：將任務(wù)i上傳到ES的傳輸時(shí)延TCeji和傳輸能耗TCeji，及ES和云服務(wù)器之間轉(zhuǎn)發(fā)任務(wù)和返回任務(wù)結(jié)果產(chǎn)生的往返時(shí)延和能耗。由于云服務(wù)器距離ES較遠(yuǎn)，ES和云服務(wù)器之間轉(zhuǎn)發(fā)任務(wù)和返回任務(wù)結(jié)果的時(shí)延會(huì)產(chǎn)生相近的往返時(shí)延和能耗［16］，且產(chǎn)生的時(shí)延和能耗與任務(wù)大小無(wú)關(guān)［17］。因此，ES和云服務(wù)器之間產(chǎn)生的往返時(shí)延TCej，ci和往返能耗ECej，ci分別為

TCej，ci=2Tc，off（18）

ECej，ci=PcTCej，ci（19）

其中：Tc，off表示ES將任務(wù)i轉(zhuǎn)發(fā)到云服務(wù)器產(chǎn)生的時(shí)延；Pc為ES和云服務(wù)器之間的傳輸功率。所以任務(wù)i卸載到云服務(wù)器執(zhí)行時(shí)產(chǎn)生的總時(shí)延Tci和總能耗Tci分別為

Tci=TCeji+TCej，ci（20）

Eci=ECeji+ECej，ci（21）

本文采用二進(jìn)制變量αi、βei、ηi表示任務(wù)的卸載決策，其中，αi、βei、ηi∈{0，1}。αi=1時(shí)表示任務(wù)i在本地執(zhí)行，αi=0時(shí)表示任務(wù)i不在本地執(zhí)行；βei=1表示任務(wù)i在ES執(zhí)行，βei=0表示任務(wù)i不在ES執(zhí)行；ηi=1表示任務(wù)i在云服務(wù)器執(zhí)行，ηi=0表示任務(wù)i不在云服務(wù)器執(zhí)行。由于任務(wù)i在ES執(zhí)行時(shí)存在兩種情形，所以用二進(jìn)制變量γei（γei∈{0，1}）表示任務(wù)i在ES的執(zhí)行方式。γei=1表示任務(wù)i可以在ej執(zhí)行，γei=0表示任務(wù)i通過(guò)ES之間的協(xié)作執(zhí)行。根據(jù)任務(wù)的卸載決策得出任務(wù)i的完成時(shí)延Ti為

Ti=αiTloci+βeiTesi+ηiTci（22）

在計(jì)算資源允許的情況下，用戶產(chǎn)生的多個(gè)卸載任務(wù)可以同時(shí)執(zhí)行。由于用戶在運(yùn)行應(yīng)用程序時(shí)產(chǎn)生多個(gè)任務(wù)，應(yīng)用程序的完成時(shí)間由最晚完成的任務(wù)來(lái)確定，從而可以得到應(yīng)用程序的完成時(shí)延Tiu和完成能耗Eiu為

Tiu=maxi∈I{Ti}（23）

Eiu=∑i∈I{αiEloci+βeiEesi+ηiEci）（24）

因此，在該模型下所有用戶運(yùn)行應(yīng)用程序產(chǎn)生的卸載任務(wù)的總完成時(shí)延T（τ）和總完成能耗T（τ）可以表示為

T（τ）=∑u∈UTiu（25）

E（τ）=∑u∈UEiu（26）

其中：本文分別用αi、βei、ηi表示任務(wù)的卸載情況，αi、βei、ηi∈{0，1}。當(dāng)αi=1時(shí)表示任務(wù)i在本地執(zhí)行，αi=0時(shí)表示任務(wù)i不在本地執(zhí)行；βei=1表示任務(wù)i在ES執(zhí)行；βei=0表示任務(wù)i不在ES執(zhí)行；ηi=1表示任務(wù)i在云服務(wù)器執(zhí)行；ηi=0表示任務(wù)i不在云服務(wù)器執(zhí)行。

1.3 問(wèn)題描述

本文的用戶任務(wù)具有異構(gòu)性，在ES服務(wù)和資源受限的約束下，研究權(quán)衡68d6b2b4355a1153379b60bcf948f3c1時(shí)延和能耗（即成本）的異構(gòu)任務(wù)卸載問(wèn)題。引入時(shí)延和能耗的權(quán)重參數(shù)ω（ω∈［0，1］），其取值由用戶對(duì)時(shí)延和能耗的偏好程度確定［18］。如果用戶對(duì)時(shí)延的需求超過(guò)能耗時(shí)，ω>0.5；反之ω<0.5。因此，根據(jù)式（25）（26），權(quán)衡時(shí)延和能耗的用戶總成本可表示為

EC=ωT（τ）+（1-ω）E（τ）（27）

因此，本文研究問(wèn)題可形式化為如下優(yōu)化問(wèn)題：

minαi、βei、γei EC

s.t. C1：∑Ii=1Xe，S·rS≤Rn

C2：αi+∑e∈Eβei+ηi=1 i∈I

C3：αi+∑e∈ESiβei+ηi=1i∈I

C4：∑Ii=1βei·Tesi·Ci≤Cm i∈I（28）

其中：C1表示服務(wù)受ES存儲(chǔ)資源約束，Xe，S∈（0，1）表示服務(wù)是否放置在ES，rS表示服務(wù)所需的存儲(chǔ)資源，ES的存儲(chǔ)資源為Rn；C2表示每個(gè)任務(wù)只能在一個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行；C3表示任務(wù)被卸載到ES執(zhí)行時(shí)服務(wù)的約束問(wèn)題，即ES必須緩存有與卸載任務(wù)對(duì)應(yīng)的服務(wù)；C4表示ES自身計(jì)算資源的約束，βei∈（0，1）表示任務(wù)是否卸載到ES上，ES的計(jì)算資源（CPU周期數(shù)）為Cm，任務(wù)每單位時(shí)間消耗Ci的CPU周期［19］。

文獻(xiàn)［20］研究了邊緣環(huán)境中異構(gòu)任務(wù)卸載和ES資源受限的約束下，最小化時(shí)延問(wèn)題，并證明了研究問(wèn)題為NP-hard問(wèn)題。與文獻(xiàn)［20］研究的問(wèn)題相比，本文在優(yōu)化目標(biāo)中加入了能耗問(wèn)題，因此，本文研究的問(wèn)題也屬于NP-hard問(wèn)題。

2 基于服務(wù)更新的任務(wù)卸載方法

為了求解本文研究的異構(gòu)任務(wù)卸載問(wèn)題，本章結(jié)合改進(jìn)的貪婪算法（improved greedy algorithm，IGA）和改進(jìn)的頁(yè)面置換算法（improved least frequently used，ILFU），提出了一種JSU-TO方法來(lái)解決異構(gòu)任務(wù)卸載問(wèn)題。JSU-TO方法總體架構(gòu)如圖2所示，主要分為兩部分。第一部分是在云邊端協(xié)作的基礎(chǔ)上，通過(guò)IGA為用戶的卸載任務(wù)確定最佳的卸載位置（可以是移動(dòng)設(shè)備、ES或者云服務(wù)器）。由于用戶周圍部署有多個(gè)ES，當(dāng)任務(wù)選擇在ES執(zhí)行時(shí)，需要考慮ES是否緩存有與卸載任務(wù)對(duì)應(yīng)的服務(wù)，以及是否具有充足的計(jì)算資源，才能挑選出滿足條件的ES。然后，通過(guò)比較在三種不同計(jì)算節(jié)點(diǎn)執(zhí)行產(chǎn)生的成本，為用戶的卸載任務(wù)選擇最佳的卸載位置。第二部分是通過(guò)ILFU算法更新ES的服務(wù)。根據(jù)時(shí)間片di內(nèi)的任務(wù)卸載情況得到服務(wù)流行度信息，并收集時(shí)間片di內(nèi)的服務(wù)信息和ES的信息。收集的信息包括服務(wù)的流行度Sd（i）和服務(wù)大小、ES的計(jì)算和存儲(chǔ)能力等。根據(jù)收集到的服務(wù)信息篩選并保存流行度較高的服務(wù)Sd（i+1），并將其回送給ES并更新ES的服務(wù)，使得ES在時(shí)間片di+1內(nèi)緩存有流行度較高的服務(wù)，供時(shí)間片di+1內(nèi)執(zhí)行卸載任務(wù)使用。

2.1 任務(wù)卸載算法

本文采用貪婪算法求解任務(wù)卸載決策。貪婪算法的基本思想是指在對(duì)問(wèn)題進(jìn)行求解時(shí)，尋求當(dāng)前狀態(tài)下的最優(yōu)解。因此，貪婪算法求得的解可能不是全局最優(yōu)解。為此，本文在貪婪算法中加入啟發(fā)式信息和引入回溯機(jī)制，提出了一種改進(jìn)的貪婪算法IGA，可以更靈活、更全面地求解問(wèn)題的最優(yōu)解，使算法更加智能化，從而提高算法的效率和準(zhǔn)確性。

由于ES的計(jì)算資源受限，當(dāng)任務(wù)卸載到ES執(zhí)行時(shí)，需要挑選計(jì)算資源充足的ES執(zhí)行用戶的卸載任務(wù)。為了挑選滿足條件的ES，在貪婪算法中加入啟發(fā)式信息，即在貪婪算法中加入ES的計(jì)算資源約束。通過(guò)比較ES剩余的計(jì)算資源，判斷ES的計(jì)算資源是否足以執(zhí)行卸載任務(wù)，從而為用戶的卸載任務(wù)選擇計(jì)算資源充足的ES。ES的計(jì)算資源約束為

r（m）=r（m）-TesiCi（29）

ei（r）=ei∩{e|r（m）≥TesiCi，ei∈E}（30）

其中：ES剩余的計(jì)算資源用r（m）表示；Tesi表示任務(wù)在ES執(zhí)行時(shí)產(chǎn)生的總時(shí)延；Ci表示任務(wù)單位時(shí)間消耗的CPU周期；ei（r）表示同時(shí)滿足條件的ES集合。

由于云服務(wù)器、ES和移動(dòng)設(shè)備都可以執(zhí)行用戶的卸載任務(wù)，為了充分利用三種計(jì)算節(jié)點(diǎn)的資源，在貪婪算法中引入回溯機(jī)制，即通過(guò)比較任務(wù)在不同計(jì)算節(jié)點(diǎn)執(zhí)行時(shí)產(chǎn)生的成本，為用戶的卸載任務(wù)選擇成本最小的計(jì)算節(jié)點(diǎn)，從而確定最佳的卸載位置。在移動(dòng)設(shè)備、ES和云服務(wù)器執(zhí)行產(chǎn)生的成本分別用ECi，l、ECi，e、ECi，c表示。如下式所示。

ECi，l=ωTloci+（1-ω）Eloci（31）

ECi，e=ωTesi+（1-ω）Eesi（32）

ECi，c=ωTci+（1-ω）Eci（33）

其中：ω（ω∈［0，1］）表示時(shí)延和能耗的權(quán)重參數(shù)，其取值由用戶對(duì)時(shí)延和能耗的偏好程度確定。

IGA的具體實(shí)現(xiàn)過(guò)程如算法1所示。首先，初始化ES的剩余計(jì)算資源和任務(wù)在不同計(jì)算節(jié)點(diǎn)的執(zhí)行成本。然后，判斷任務(wù)是否可以在ES執(zhí)行，并判斷ES是否具有充足的計(jì)算資源，將滿足條件的ES保留至集合ei（r）中，用集合Resedge存放ek的計(jì)算資源。接著，從集合Resedge中挑選出計(jì)算資源充足的ES，并從集合ei（r）中找到對(duì)應(yīng)的ES編號(hào)（第1～8行）。然后，計(jì)算任務(wù)在移動(dòng)設(shè)備、ES和云服務(wù)器執(zhí)行時(shí)產(chǎn)生的成本，即ECi，l、ECi，e、ECi，c，并比較任務(wù)在三種計(jì)算節(jié)點(diǎn)的執(zhí)行成本，判斷任務(wù)在哪個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行時(shí)產(chǎn)生的成本最小，選擇成本最小的計(jì)算節(jié)點(diǎn)作為任務(wù)i最優(yōu)的卸載位置。重復(fù)上述過(guò)程，直到所有任務(wù)均執(zhí)行完畢（第9～18行）。其中，r（m）表示ES剩余的計(jì)算資源，Cm表示ES的計(jì)算資源。

算法1 IGA

輸入：任務(wù)集合I;ES集合E。

輸出：最優(yōu)的任務(wù)卸載決策αi、βei、ηi，執(zhí)行成本EC。

1 初始化ES的剩余計(jì)算資源r（m）=Cm

2 將EC、ECi，l、ECi，e、ECi，c初始化為0

3 for i=1 to I

4 for每個(gè)邊緣服務(wù)器ek in E do

5 if判斷任務(wù)是否可以在ek執(zhí)行，then ei（r）←ek并將ek剩余的處理資源r（m）保存至集合Resedge

6 end if

7 挑選出計(jì)算資源充足的ES，并找到對(duì)應(yīng)的編號(hào)

8&nbsp; end for

9 根據(jù)式（31）～（33）計(jì)算出ECi，l、ECi，e、ECi，c

10 篩選出成本最小的計(jì)算節(jié)點(diǎn)：

11 if ECi，l=min{ECi，l、ECi，e、ECi，c} then αi←1，保存ECi，n←ECi，l

12 else if ECi，e=min{ ECi，l、ECi，e、ECi，c} then βei←1，保存ECi，n ←ECi，e

13 else ηi←1，保存ECi，n ←ECi，c

14 end if

15 執(zhí)行成本EC=EC+ECi，n

16 end for

17 輸出每個(gè)任務(wù)的卸載決策αi、βei、ηi

18 輸出最小的成本EC

2.2 服務(wù)更新算法

本文將時(shí)間劃分為時(shí)間片，一個(gè)時(shí)間片表示一段時(shí)間，例如十分鐘、一個(gè)小時(shí)、一天等。在不同時(shí)間片內(nèi)，用戶的服務(wù)需求會(huì)發(fā)生變化，從而影響服務(wù)流行度，應(yīng)根據(jù)不同時(shí)間片內(nèi)的服務(wù)流行度來(lái)更新ES的服務(wù)。服務(wù)流行度表示服務(wù)的受歡迎程度，服務(wù)的受歡迎程度越高，表示需要該服務(wù)提供執(zhí)行環(huán)境的卸載任務(wù)越多。ES將服務(wù)信息上傳到云服務(wù)器，云服務(wù)器根據(jù)服務(wù)流行度的高低更新ES的服務(wù)。

服務(wù)的集合用S={S1，S2，S3，…，Sv}表示，v表示服務(wù)的數(shù)量，表示一個(gè)時(shí)間片內(nèi)與用戶卸載任務(wù)對(duì)應(yīng)的所有服務(wù)請(qǐng)求，rS表示每個(gè)服務(wù)所需的存儲(chǔ)空間。本文將一個(gè)時(shí)間片劃分為一天，那么時(shí)間片的集合用D={d1，d2，d3，…，dp}表示，其中p表示時(shí)間片的個(gè)數(shù)。在不同時(shí)間片內(nèi)，服務(wù)流行度會(huì)發(fā)生變化，集合Sd（i）表示在時(shí)間片di內(nèi)服務(wù)的流行度信息，集合Sd（i+1）表示在時(shí)間片di+1內(nèi)ES要更新的服務(wù)。

雖然經(jīng)典LFU算法可以用于更新ES的服務(wù)，但仍面臨兩個(gè)問(wèn)題。第一，由于LFU算法只能比較ES已緩存服務(wù)的流行度，不能比較ES沒(méi)有緩存服務(wù)的流行度，從而無(wú)法對(duì)所有服務(wù)的流行度進(jìn)行對(duì)比。第二，若存在多個(gè)服務(wù)的流行度相同，且緩存所有流行度相同的服務(wù)將超出ES存儲(chǔ)空間，經(jīng)典LFU算法將無(wú)法準(zhǔn)確更新ES的服務(wù)。為了解決上述兩個(gè)問(wèn)題，本文提出了一種改進(jìn)的服務(wù)更新算法ILFU算法。

ILFU的算法思想為：收集時(shí)間片di內(nèi)所有被成功執(zhí)行的卸載任務(wù)信息以及對(duì)應(yīng)的服務(wù)信息，并將服務(wù)信息放入集合Sd（i）中，同時(shí)，根據(jù)集合Sd（i）中的服務(wù)信息建立一個(gè)二元組Sd（i）=（CNTik，RTik）。其中，CNTik表示服務(wù)的請(qǐng)求次數(shù)，RTik表示服務(wù)的響應(yīng)時(shí)間。通過(guò)比較相關(guān)的服務(wù)信息，比較所有服務(wù)的流行度。ILFU算法的具體實(shí)現(xiàn)過(guò)程如算法2所示。首先，根據(jù)服務(wù)的使用頻率降序排列放入集合Sd（i+1）中。若存在兩個(gè)服務(wù)的流行度相同，通過(guò)比較兩者最后一次響應(yīng)時(shí)間RTik來(lái)判斷服務(wù)流行度的高低。根據(jù)時(shí)間局部性原理，最晚被請(qǐng)求的服務(wù)再次被請(qǐng)求的概率較大，將響應(yīng)時(shí)間最晚的服務(wù)賦予較高的流行度，將流行度較高的服務(wù)放入集合Sd（i+1）中（第1～6行）。然后，計(jì)算Sd（i+1）中服務(wù)所需的存儲(chǔ)資源，并判斷集合Sd（i+1）中的服務(wù)是否滿足ES的存儲(chǔ)資源約束。在滿足ES存儲(chǔ)資源約束的條件下，更新集合Sd（i+1）中的服務(wù)。最后，集合Sd（i+1）中存放的服務(wù)就是時(shí)間片di+1內(nèi)ES要更新的服務(wù)（第7～13行）。用rS表示服務(wù)所需的存儲(chǔ)資源，ES的存儲(chǔ)資源為Rn。

算法2 ILFU

輸入：服務(wù)集合Sd（i）;服務(wù)信息Sd（i）=（CNTik，RTik）;ES的集合E。

輸出：時(shí)間片di+1內(nèi)ES要部署的服務(wù)集合。

1 為服務(wù)二元組編號(hào)S={S1，S2，S3，…，Sv}

2 for每個(gè)二元組中CNTik in Sd（i） do

3 將集合Sd（i）中服務(wù)使用頻率降序排列并放入集合Sd（i+1）

4 if CNTik=CNTik+1 then RTik<RTik+1

5 將服務(wù)Sk+1放入集合Sd（i+1）

6 end if

7 for每個(gè)Si in Sd（i+1）

8 判斷服務(wù)是否滿足ES存儲(chǔ)資源約束

9 if Rn-（Si·rs）>0 then將Si放入集合Sd（i+1）

10 end if

11 end for

12 end for

13 輸出在時(shí)間片di+1內(nèi)ES部署的服務(wù)集合

2.3 JSU-TO方法

本文方法可以為用戶的卸載任務(wù)選擇當(dāng)前服務(wù)部署下最優(yōu)的卸載決策，最小化任務(wù)的完成時(shí)延和能耗，從而降低用戶成本。JSU-TO的具體實(shí)現(xiàn)過(guò)程如算法3所示。首先，根據(jù)ILFU算法得到時(shí)間片di+1內(nèi)流行度較高的服務(wù)集合Sd（i+1），在滿足ES存儲(chǔ)資源約束的前提下更新ES的服務(wù)（第1～4行），在時(shí)間片di+1內(nèi)ES緩存有流行度較高的服務(wù)。然后，對(duì)于時(shí)間片di+1內(nèi)用戶的每個(gè)卸載任務(wù)i∈I，通過(guò)IGA為任務(wù)選擇當(dāng)前服務(wù)部署下成本最小的計(jì)算節(jié)點(diǎn)，并選擇最優(yōu)的卸載決策。重復(fù)上述過(guò)程，直到所有任務(wù)均執(zhí)行完畢（第5～16行）。其中，用r（m）表示ES剩余的計(jì)算資源，Cm表示ES的計(jì)算資源。

算法3 JSU-TO方法

輸入：用戶集合U;任務(wù)集合I;服務(wù)集合Sd（i+1）。

輸出：最優(yōu)的任務(wù)卸載決策αi、βei、ηi;執(zhí)行成本EC。

1 for e=1 to E

2 根據(jù)ILFU算法得到時(shí)間片di+1內(nèi)ES部署的服務(wù)集合Sd（i+1）

3 在滿足ES存儲(chǔ)資源的約束下更新ES的服務(wù)

4 end for

5 for u=1 to U

6 for i=1 to I

7 在當(dāng)前ES的服務(wù)部署下

8 通過(guò)IGA篩選出成本最小的計(jì)算節(jié)點(diǎn)

9 并保存其卸載決策和執(zhí)行成本

10 執(zhí)行成本EC=EC + ECi，n

11 end for

12 end for

13 輸出每個(gè)任務(wù)的卸載決策αi、βei、ηi

14 輸出執(zhí)行成本EC

2.4 時(shí)間復(fù)雜度分析

假設(shè)ES的數(shù)量為L(zhǎng)，用戶的數(shù)量為n，用戶運(yùn)行應(yīng)用程序時(shí)生成的任務(wù)數(shù)量為q。算法3中的第1～4行調(diào)用算法2，根據(jù)ILFU算法得到時(shí)間片di+1內(nèi)流行度較高的服務(wù)，在滿足ES存儲(chǔ)資源的約束下更新ES的服務(wù)，使得ES在時(shí)間片di+1內(nèi)緩存有流行度較高的服務(wù)。其中，ILFU算法根據(jù)時(shí)間片di內(nèi)的服務(wù)流行度信息，得到時(shí)間片di+1內(nèi)流行度較高的服務(wù)，其時(shí)間復(fù)雜度為O（v×v′×L×（k-1））。因此，算法3中第1～4行的時(shí)間復(fù)雜度為O（v×v′×L2×（k-1））。算法3中的第5～14行調(diào)用算法1，通過(guò)IGA為用戶的卸載任務(wù)選擇成本最小的計(jì)算節(jié)點(diǎn)，從而為用戶的卸載任務(wù)選擇當(dāng)前服務(wù)部署下最優(yōu)的卸載決策。其中，IGA根據(jù)卸載任務(wù)選擇計(jì)算資源充足的ES，然后選擇執(zhí)行成本最小的計(jì)算節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O（n×q）。因此，算法3中第5～14行的時(shí)間復(fù)雜度為O（L×n×q）。綜上所述，JSU-TO方法的時(shí)間復(fù)雜度為O（v×v′×L3×（k-1）×n×q）。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)設(shè)置

在云邊端網(wǎng)絡(luò)模型中，用戶運(yùn)行應(yīng)用程序會(huì)產(chǎn)生不同類型的任務(wù)。本文使用谷歌數(shù)據(jù)集模擬用戶產(chǎn)生的任務(wù)，谷歌數(shù)據(jù)集中每個(gè)任務(wù)都有詳細(xì)的參數(shù)，包括任務(wù)特征和所需服務(wù)類型［21］。為了執(zhí)行異構(gòu)任務(wù)，需要不同類型的服務(wù)為其提供執(zhí)行環(huán)境；為了得到最小成本，需要為用戶選擇最優(yōu)的卸載決策。

本實(shí)驗(yàn)在一臺(tái)計(jì)算機(jī)上運(yùn)行，具體配置為：Intel CoreTM i5-7300HQ CPU@ 2.50 GHz， Windows 10 中文版64位，實(shí)驗(yàn)環(huán)境為Python 3.9.0。

3.2 對(duì)比方法

本文選擇以下四種方法，與本文方法進(jìn)行對(duì)比：

a）文獻(xiàn)［22］提出的MMTO方法，其在車輛計(jì)算資源受限的約束下，優(yōu)化卸載任務(wù)的執(zhí)行時(shí)延和計(jì)算成本。根據(jù)本文的研究問(wèn)題，在MMTO方法的優(yōu)化目標(biāo)中加入能耗，同時(shí)將其約束條件改為本文方法的約束條件。

b）文獻(xiàn)［23］提出的OJTR方法，是在滿足服務(wù)需求和資源的約束下，以最小化所有車輛總?cè)蝿?wù)處理時(shí)延為目標(biāo)。為了使OJTR方法能與本文方法作對(duì)比，在其優(yōu)化目標(biāo)中加入能耗。

c）文獻(xiàn)［24］提出的GA，其目標(biāo)是最小化任務(wù)的處理時(shí)延和能耗。將GA的約束條件修改為本文方法所提的約束條件。

d）經(jīng)典的頁(yè)面置換算法LFU，根據(jù)用戶的服務(wù)偏好更新ES的服務(wù)，從而可以為更多卸載任務(wù)提供執(zhí)行環(huán)境。

3.3 權(quán)重參數(shù)ω的影響

在本節(jié)實(shí)驗(yàn)中，設(shè)定實(shí)驗(yàn)環(huán)境中ES的數(shù)量為5，用戶的數(shù)量為100，假設(shè)每個(gè)用戶產(chǎn)生10個(gè)卸載任務(wù)，此時(shí)卸載任務(wù)的數(shù)量為1 000個(gè)。其中，ω取值為［0，1］，改變?chǔ)氐娜≈担诒疚姆椒ㄏ逻M(jìn)行實(shí)驗(yàn)。從圖3中可以看出，ω的取值與能耗成正比， 取值與時(shí)延成反比。也就是說(shuō)，當(dāng)ω<0.5時(shí)，意味著用戶對(duì)能耗需求比較高，此時(shí)，計(jì)算節(jié)點(diǎn)可通過(guò)延長(zhǎng)卸載任務(wù)的完成時(shí)間，從而降低計(jì)算節(jié)點(diǎn)的能耗；相反，當(dāng)ω>0.5時(shí)，意味著用戶更偏好時(shí)延，此時(shí)，通過(guò)增大計(jì)算節(jié)點(diǎn)之間的傳輸功率，可以降低任務(wù)的傳輸時(shí)延。為了驗(yàn)證本文方法既能滿足用戶對(duì)能耗的需求，也能滿足時(shí)延偏好，實(shí)驗(yàn)中ω分別取值為0.2和0.8。

3.4 對(duì)比實(shí)驗(yàn)

1）用戶數(shù)量對(duì)成本、時(shí)延和能耗的影響

邊緣環(huán)境中用戶數(shù)量對(duì)實(shí)驗(yàn)結(jié)果會(huì)產(chǎn)生影響，隨著用戶數(shù)量的增加，用戶產(chǎn)生的卸載任務(wù)也增加，為了執(zhí)行用戶的卸載任務(wù)，ES要消耗更多的計(jì)算資源和帶寬資源，從而會(huì)增加用戶成本。為了找到某一特定邊緣環(huán)境中最佳容納用戶的數(shù)量，本節(jié)通過(guò)變化用戶數(shù)量，探究同一邊緣環(huán)境中用戶數(shù)量對(duì)任務(wù)時(shí)延、能耗和成本的影響，從而為該邊緣環(huán)境確定最佳容納用戶的數(shù)量，使得用戶成本最小化，提升用戶體驗(yàn)。

設(shè)定實(shí)驗(yàn)環(huán)境中ES的數(shù)量為5，權(quán)重參數(shù)ω取值分別為0.2和0.8。變化用戶的數(shù)量，采用五種方法分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4和5所示。隨著用戶數(shù)量的增加，在五種方法下，時(shí)延、能耗和成本都逐漸上升。主要是因?yàn)殡S著用戶數(shù)量的增加，用戶產(chǎn)生的卸載任務(wù)數(shù)量增加。由于ES的服務(wù)和資源是有限的，只能為部分任務(wù)提供執(zhí)行環(huán)境；ES無(wú)法執(zhí)行的任務(wù)則需要轉(zhuǎn)發(fā)到其他ES或云服務(wù)器執(zhí)行，產(chǎn)生額外的傳輸時(shí)延和能耗，增加成本。本文方法首先通過(guò)ILFU算法，根據(jù)服務(wù)流行度更新ES的服務(wù)，使其緩存有流行度較高的服務(wù)，從而可以為更多卸載任務(wù)提供執(zhí)行環(huán)境；然后通過(guò)IGA為卸載任務(wù)選擇成本最小的計(jì)算節(jié)點(diǎn)，降低成本。與其他四種方法相比，本文方法總成本最小。通過(guò)觀察可知，當(dāng)用戶數(shù)量小于160時(shí)，總成本增加的速度較慢。此時(shí)，既可以充分利用ES的資源，也可以及時(shí)執(zhí)行用戶的卸載任務(wù)，降低用戶成本。當(dāng)用戶數(shù)量超過(guò)160時(shí)，該邊緣環(huán)境不能為用戶提供足夠的資源。因此，該邊緣環(huán)境中最佳容納用戶數(shù)量為160。

2）任務(wù)數(shù)據(jù)量大小對(duì)成本的影響

設(shè)定用戶數(shù)量為160，產(chǎn)生的任務(wù)數(shù)量為1 600個(gè)，以每次增加5的規(guī)律，變化任務(wù)的數(shù)據(jù)量從5至30，采用五種方法分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6所示。隨著任務(wù)數(shù)據(jù)量的增大，ES處理任務(wù)的時(shí)延和能耗也會(huì)增大，且ES處理任務(wù)時(shí)所需的資源也在增加，因此，五種方法的成本也隨之增加。

由于MMTO和OJTR方法都不考慮更新ES的服務(wù)，導(dǎo)致ES緩存的服務(wù)不能長(zhǎng)期為用戶的卸載任務(wù)提供執(zhí)行環(huán)境。主要是因?yàn)殡S著時(shí)間的變化，相同用戶會(huì)產(chǎn)生不同的卸載任務(wù)；由于用戶的移動(dòng)性，邊緣環(huán)境中會(huì)出現(xiàn)不同的用戶，不同用戶會(huì)產(chǎn)生不同的卸載任務(wù)；不同卸載任務(wù)需要不同的服務(wù)提供執(zhí)行環(huán)境，導(dǎo)致用戶的服務(wù)需求發(fā)生改變。且隨著任務(wù)的平均數(shù)據(jù)量增大，產(chǎn)生的傳輸時(shí)延和能耗也隨之增加，從而產(chǎn)生較高的成本。與前兩種方法不同，LFU算法通過(guò)更新ES的服務(wù)，使得ES緩存有較高流行度的服務(wù)，從而可以為更多卸載任務(wù)提供執(zhí)行環(huán)境。但是LFU算法只能比較ES已緩存服務(wù)的流行度，不能比較用戶新的服務(wù)請(qǐng)求，即ES沒(méi)有緩存服務(wù)的流行度；若多個(gè)服務(wù)的流行度相同，且緩存所有流行度相同的服務(wù)將超出ES存儲(chǔ)空間，LFU算法將無(wú)法準(zhǔn)確更新ES的服務(wù)。此時(shí)，ES緩存的服務(wù)無(wú)法為任務(wù)選擇最佳的卸載決策，從而產(chǎn)生較高的時(shí)延和能耗，增加成本。在GA方法中，隨著數(shù)據(jù)量的增加，產(chǎn)生的成本逐漸增加。從圖6中可以看到，相比于其他四種方法，本文方法可以為用戶分配當(dāng)前服務(wù)部署下最優(yōu)的卸載決策，從而使得成本最小。

3）ES的存儲(chǔ)和計(jì)算資源對(duì)成本和命中率的影響

邊緣環(huán)境中ES的存儲(chǔ)和計(jì)算資源大小對(duì)實(shí)驗(yàn)結(jié)果也會(huì)產(chǎn)生影響，當(dāng)任務(wù)卸載到ES執(zhí)行時(shí)會(huì)競(jìng)爭(zhēng)ES有限的服務(wù)和資源。本節(jié)通過(guò)變化ES的存儲(chǔ)和計(jì)算資源，探究ES存儲(chǔ)和計(jì)算資源對(duì)成本和命中率的影響，從而為ES確定最佳的存儲(chǔ)和計(jì)算資源。

設(shè)定用戶任務(wù)數(shù)量為1 600個(gè)，變化ES的存儲(chǔ)資源從5至30。ω分別取值為0.2和0.8，采用五種方法分別進(jìn)行實(shí)驗(yàn)。圖7中，隨著ES存儲(chǔ)資源的增加，成本逐漸降低。這是因?yàn)樵贓S數(shù)量和用戶任務(wù)數(shù)量不變的情況下，隨著ES存儲(chǔ)資源的增加，ES可以緩存更多的服務(wù)，從而可以為更多卸載任務(wù)提供執(zhí)行環(huán)境，使得轉(zhuǎn)發(fā)到其他ES或者云服務(wù)器執(zhí)行的任務(wù)減少，傳輸成本減少，進(jìn)一步降低成本。同樣，如圖8所示，隨著ES存儲(chǔ)資源逐漸增加，ES緩存的服務(wù)較多，可以更好地滿足用戶的服務(wù)需求，提高命中率。

從圖7和8可以看出，當(dāng)ES存儲(chǔ)資源增長(zhǎng)到20，五種方法成本降低趨勢(shì)減緩，命中率上升速率漸緩。在卸載任務(wù)數(shù)量不變的情況下，此時(shí)ES可以最大程度地降低成本，提高命中率。若繼續(xù)增加ES的存儲(chǔ)資源，既不會(huì)顯著降低用戶成本，也不能明顯提高命中率。因此ES存儲(chǔ)資源最佳設(shè)置應(yīng)為20。

同樣，設(shè)定用戶任務(wù)數(shù)量為1 600個(gè)，變化ES的計(jì)算資源從20至120。ω分別取值為0.2和0.8，采用五種方法分別進(jìn)行實(shí)驗(yàn)。在圖9中，隨著ES計(jì)算資源逐漸增加，成本逐漸降低。這是因?yàn)樵贓S數(shù)量和用戶任務(wù)數(shù)量不變的情況下，隨著ES計(jì)算資源的增加，在滿足ES服務(wù)約束前提下，ES可以執(zhí)行更多的卸載任務(wù)，使得轉(zhuǎn)發(fā)到其他ES或者云服務(wù)器執(zhí)行的任務(wù)減少，傳輸成本和用戶成本降低。

同樣，如圖10所示，隨著ES計(jì)算資源的增加，在ES滿足服務(wù)約束的前提下，ES可以執(zhí)行更多的卸載任務(wù)，從而提高命中率。從圖9和10可以看出，當(dāng)計(jì)算資源增長(zhǎng)到80時(shí)，五種方法的成本降低趨勢(shì)減緩，命中率上升速率變慢，此時(shí)ES可以最大程度地降低成本，提高命中率。若繼續(xù)增加ES的計(jì)算資源，既不會(huì)明顯降低用戶的成本，也不會(huì)顯著提高命中率。因此，ES的計(jì)算資源最佳設(shè)置應(yīng)為80。從圖7～10中可以看出，無(wú)論為ES配備多大的存儲(chǔ)和計(jì)算資源，本文方法性能均為最優(yōu)，都能為卸載任務(wù)選擇當(dāng)前服務(wù)部署下最佳的卸載決策，從而降低用戶成本，提高命中率。

4 結(jié)束語(yǔ)

本文聯(lián)合考慮服務(wù)更新和云邊端協(xié)作，研究了在ES服務(wù)緩存和資源受限約束下，權(quán)衡時(shí)延和能耗的異構(gòu)任務(wù)卸載問(wèn)題，并提出了JSU-TO方法。JSU-TO通過(guò)ILFU算法，預(yù)測(cè)出潛在的用戶服務(wù)需求量，及時(shí)更新ES的服務(wù)；在云邊端協(xié)作的基礎(chǔ)上，通過(guò)IGA為用戶選擇當(dāng)前服務(wù)部署下最佳的卸載決策，完成任務(wù)卸載，且保持成本最小。實(shí)驗(yàn)結(jié)果表明，所提方法有效降低了用戶成本。

雖然本文方法具有較好的效果，但還存在局限性：a）用戶的移動(dòng)性對(duì)服務(wù)的流行度也會(huì)產(chǎn)生影響，本文卻忽略了這一點(diǎn)；b）本文沒(méi)有考慮服務(wù)的放置。從網(wǎng)絡(luò)運(yùn)營(yíng)商的角度考慮，服務(wù)的放置需要成本，如何解決服務(wù)的放置問(wèn)題，使其不僅可以滿足用戶的服務(wù)需求，同時(shí)也可以最大化網(wǎng)絡(luò)運(yùn)營(yíng)商的收益。因此，下一步的工作重點(diǎn)將嘗試在服務(wù)更新過(guò)程中，根據(jù)用戶的移動(dòng)性來(lái)進(jìn)行服務(wù)的更新，制定更優(yōu)的服務(wù)更新策略，使網(wǎng)絡(luò)運(yùn)營(yíng)商的收益達(dá)到最大化。

參考文獻(xiàn)：

［1］Duan Sijing， Wang Dan， Ren Ju， et al. Distributed artificial intelligence empowered by end-edge-cloud computing： a survey［J］. IEEE Communications Surveys & Tutorials， 2022，25（1）：591-624.

［2］Koot M， Wijnhoven F. Usage impact on data center electricity needs： a system dynamic forecasting model［J］. Applied Energy， 2021，291：116798.

［3］Xiang Zhengzhe， Deng Shuiguang， Taheri j， et al. Dynamical service deployment and replacement in resource-constrained edges［J］. Mobile Networks and Applications， 2020， 25（2）： 674-689.

［4］Wei Zhe， Yu Xuebin，Zou Lei. Multi-resource computing offload stra-tegy for energy consumption optimization in mobile edge computing［J］. Processes， 2022，10（9）： 1762.

［5］Chu Xiao， Leng Ze. Multiuser computing offload algorithm based on mobile edge computing in the Internet of Things environment［J］. Wireless Communications and Mobile Computing， 2022， 2022： 1-9.

［6］Chen Ying， Zhao Fengjun， Lu Yanghuang， et al. Dynamic task offloading for mobile edge computing with hybrid energy supply［J］. Tsinghua Science and Technology， 2022， 28（3）： 421-432.

［7］Chen Ying， Gu Wei， Li Kaixin. Dynamic task offloading for Internet of Things in mobile edge computing via deep reinforcement learning［J/OL］. International Journal of Communication Systems. （2022-03-30）. https：//onlinelibrary.wiley.com/doi/abs/10.1002/dac.5154.

［8］Zhong Shijie， Guo Songtao， Yu Hongyan， et al. Cooperative service caching and computation offloading in multi-access edge computing［J］. Computer Networks， 2021， 189： 107916.

［9］Tian Hao， Xu Xiaolong， Lin Tingyu， et al. DIMA： distributed coop-erative microservice caching for Internet of Things in edge computing by deep reinforcement learning［J］. World Wide Web， 2022， 25（5）： 1769-1792.

［10］Liu Chenfeng， Bennis M， Debbah M， et al. Dynamic task offloading and resource allocation for ultra-reliable low-latency edge computing［J］. IEEE Trans on Communications， 2019， 67（6）： 4132-4150.

［11］Chen M H， Dong Min， Liang Ben. Resource sharing of a computing access point for multi-user mobile cloud offloading with delay constraints［J］. IEEE Trans on Mobile Computing， 2018，17（12）： 2868-2881.

［12］Zhang Xinglin， Li Zhenjiang， Lai Chang， et al. Joint edge server placement and service placement in mobile-edge computing［J］. IEEE Internet of Things Journal， 2021， 9（13）： 11261-11274.

［13］Almashhadani H A， Deng Xiaoheng， Abdul L S N， et al. An edge-computing based task-unloading technique with privacy protection for Internet of connected vehicles［J］. Wireless Personal Communications， 2022， 127（2）： 1787-1808.

［14］Cao Kun， Cui Yangguang， Liu Zhiquan， et al. Edge intelligent joint optimization for lifetime and latency in large-scale cyber-physical systems［J］. IEEE Internet of Things Journal， 2021， 9（22）： 22267-22279.

［15］Wang Changyu， Yu Weili， Zhu Fusheng， et al. UAV-aided multiuser mobile edge computing networks with energy harvesting［J］. Wireless Communications and Mobile Computing， 2022， 2022： 6723403.

［16］Xu Xiaolong， Fang Zijie， Qi Lianyong， et al. A deep reinforcement learning-based distributed service offloading method for edge computing empowered Internet of Vehicles［J］. Chinese Journal of Computers， 2021， 44（12）： 2382-2405.

［17］Singh P， Singh R. Energy-efficient delay-aware task offloading in fog-cloud computing system for IoT sensor applications［J］. Journal of Network and Systems Management， 2022， 30： 1-25.

［18］Ko S W， Kim S J， Jung H， et al. Computation offloading and service caching for mobile edge computing under personalized service prefe-rence［J］. IEEE Trans on Wireless Communications， 2022， 21（8）： 6568-6583.

［19］Zhang Junna， Chen Jiawei， Bao Xiang， et al. Dependent task offloading mechanism for cloud-edge-device collaboration［J］. Journal of Network and Computer Applications， 2023， 216： 103656.

［20］Liu Yu， Mao Yingling， Liu Zhenhua， et al. Joint task offloading and resource allocation in heterogeneous edge environments［C］//Proc of IEEE Conference on Computer Communications. Piscataway，NJ：IEEE Press， 2023.

［21］Reiss C， Tumanov A， Ganger G R， et al. Heterogeneity and dynamicity of clouds at scale： Google trace analysis［C］ //Proc of the 3rd ACM Symposium on Cloud Computing. New York： ACM Press， 2012： 1-13.

［22］Liu Lei， Zhao Ming， Yu Miao， et al. Mobility-aware multi-hop task offloading for autonomous driving in vehicular edge computing and networks［J］. IEEE Trans on Intelligent Transportation Systems， 2022， 24（2）： 2169-2182.

［23］ Fan Wenhao， Su Yi， Liu Jie， et al. Joint task offloading and resource allocation for vehicular edge computing based on V2I and V2V modes［J］. IEEE Trans on Intelligent Transportation Systems， 2023， 24（4）： 4277-4292.

［24］Chakraborty S， Mazumdar K. Sustainable task offloading decision using genetic algorithm in sensor mobile edge computing［J］. Journal of King Saud University-Computer and Information Sciences， 2022， 34（4）： 1552-1568.