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

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

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

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

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

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

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

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

本文的主要貢獻包括以下四個方面：

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

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

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

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

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

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

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

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

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

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

1.2 時延能耗模型

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

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

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

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

Tloci=Rifu，Eloci=PuTloci（1）

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

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

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

TCeji=GiRej（2）

ECeji=PuTCeji（3）

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

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

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

TReji=Rifej（5）

EReji=PejTReji（6）

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

Teji=TCeji+TReji（7）

Eeji=ECeji+EReji（8）

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

TCej，eki=GiRej，ek（9）

ECej，eki=PtTCej，eki（10）

其中：Rej，ek表示ej到ek的傳輸速率，可由香農(nóng)公式計算得到，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í)行時延TReki和執(zhí)行能耗EReki分別為

TReki=Rifek（12）

EReki=PekTReki（13）

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

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

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

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

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

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

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

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

當任務(wù)i被卸載到云服務(wù)器執(zhí)行時，首先將任務(wù)i上傳至附近的ES，再由ES通過有線信道轉(zhuǎn)發(fā)給云服務(wù)器。當任務(wù)i需要轉(zhuǎn)發(fā)至云服務(wù)器時，相對于ES到云的傳輸時延，ES轉(zhuǎn)發(fā)任務(wù)前的等待時延相對較小可以忽略不計［15］?？紤]到云服務(wù)器有著較強的計算能力，執(zhí)行時延相對于傳輸時延來說可以忽略不計。因此，本文忽略在云服務(wù)器執(zhí)行時產(chǎn)生的執(zhí)行時延和能耗。當任務(wù)卸載到云服務(wù)器執(zhí)行時，產(chǎn)生的時延和能耗主要包括：將任務(wù)i上傳到ES的傳輸時延TCeji和傳輸能耗TCeji，及ES和云服務(wù)器之間轉(zhuǎn)發(fā)任務(wù)和返回任務(wù)結(jié)果產(chǎn)生的往返時延和能耗。由于云服務(wù)器距離ES較遠，ES和云服務(wù)器之間轉(zhuǎn)發(fā)任務(wù)和返回任務(wù)結(jié)果的時延會產(chǎn)生相近的往返時延和能耗［16］，且產(chǎn)生的時延和能耗與任務(wù)大小無關(guān)［17］。因此，ES和云服務(wù)器之間產(chǎn)生的往返時延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)生的時延；Pc為ES和云服務(wù)器之間的傳輸功率。所以任務(wù)i卸載到云服務(wù)器執(zhí)行時產(chǎn)生的總時延Tci和總能耗Tci分別為

Tci=TCeji+TCej，ci（20）

Eci=ECeji+ECej，ci（21）

本文采用二進制變量αi、βei、ηi表示任務(wù)的卸載決策，其中，αi、βei、ηi∈{0，1}。αi=1時表示任務(wù)i在本地執(zhí)行，αi=0時表示任務(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í)行時存在兩種情形，所以用二進制變量γei（γei∈{0，1}）表示任務(wù)i在ES的執(zhí)行方式。γei=1表示任務(wù)i可以在ej執(zhí)行，γei=0表示任務(wù)i通過ES之間的協(xié)作執(zhí)行。根據(jù)任務(wù)的卸載決策得出任務(wù)i的完成時延Ti為

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

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

Tiu=maxi∈I{Ti}（23）

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

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

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

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

其中：本文分別用αi、βei、ηi表示任務(wù)的卸載情況，αi、βei、ηi∈{0，1}。當αi=1時表示任務(wù)i在本地執(zhí)行，αi=0時表示任務(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ù)具有異構(gòu)性，在ES服務(wù)和資源受限的約束下，研究權(quán)衡68d6b2b4355a1153379b60bcf948f3c1時延和能耗（即成本）的異構(gòu)任務(wù)卸載問題。引入時延和能耗的權(quán)重參數(shù)ω（ω∈［0，1］），其取值由用戶對時延和能耗的偏好程度確定［18］。如果用戶對時延的需求超過能耗時，ω>0.5；反之ω<0.5。因此，根據(jù)式（25）（26），權(quán)衡時延和能耗的用戶總成本可表示為

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

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

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

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

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

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

2.1 任務(wù)卸載算法

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

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

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

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

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

由于云服務(wù)器、ES和移動設(shè)備都可以執(zhí)行用戶的卸載任務(wù)，為了充分利用三種計算節(jié)點的資源，在貪婪算法中引入回溯機制，即通過比較任務(wù)在不同計算節(jié)點執(zhí)行時產(chǎn)生的成本，為用戶的卸載任務(wù)選擇成本最小的計算節(jié)點，從而確定最佳的卸載位置。在移動設(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］）表示時延和能耗的權(quán)重參數(shù)，其取值由用戶對時延和能耗的偏好程度確定。

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

算法1 IGA

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

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

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

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

3 for i=1 to I

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

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

6 end if

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

8&nbsp; end for

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

10 篩選出成本最小的計算節(jié)點：

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 輸出每個任務(wù)的卸載決策αi、βei、ηi

18 輸出最小的成本EC

2.2 服務(wù)更新算法

本文將時間劃分為時間片，一個時間片表示一段時間，例如十分鐘、一個小時、一天等。在不同時間片內(nèi)，用戶的服務(wù)需求會發(fā)生變化，從而影響服務(wù)流行度，應(yīng)根據(jù)不同時間片內(nèi)的服務(wù)流行度來更新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ù)量，表示一個時間片內(nèi)與用戶卸載任務(wù)對應(yīng)的所有服務(wù)請求，rS表示每個服務(wù)所需的存儲空間。本文將一個時間片劃分為一天，那么時間片的集合用D={d1，d2，d3，…，dp}表示，其中p表示時間片的個數(shù)。在不同時間片內(nèi)，服務(wù)流行度會發(fā)生變化，集合Sd（i）表示在時間片di內(nèi)服務(wù)的流行度信息，集合Sd（i+1）表示在時間片di+1內(nèi)ES要更新的服務(wù)。

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

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

算法2 ILFU

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

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

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

2 for每個二元組中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每個Si in Sd（i+1）

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

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

10 end if

11 end for

12 end for

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

2.3 JSU-TO方法

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

算法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算法得到時間片di+1內(nèi)ES部署的服務(wù)集合Sd（i+1）

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

4 end for

5 for u=1 to U

6 for i=1 to I

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

8 通過IGA篩選出成本最小的計算節(jié)點

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

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

11 end for

12 end for

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

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

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

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

3 實驗驗證

3.1 實驗設(shè)置

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

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

3.2 對比方法

本文選擇以下四種方法，與本文方法進行對比：

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

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

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

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

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

在本節(jié)實驗中，設(shè)定實驗環(huán)境中ES的數(shù)量為5，用戶的數(shù)量為100，假設(shè)每個用戶產(chǎn)生10個卸載任務(wù)，此時卸載任務(wù)的數(shù)量為1 000個。其中，ω取值為［0，1］，改變ω的取值，在本文方法下進行實驗。從圖3中可以看出，ω的取值與能耗成正比， 取值與時延成反比。也就是說，當ω<0.5時，意味著用戶對能耗需求比較高，此時，計算節(jié)點可通過延長卸載任務(wù)的完成時間，從而降低計算節(jié)點的能耗；相反，當ω>0.5時，意味著用戶更偏好時延，此時，通過增大計算節(jié)點之間的傳輸功率，可以降低任務(wù)的傳輸時延。為了驗證本文方法既能滿足用戶對能耗的需求，也能滿足時延偏好，實驗中ω分別取值為0.2和0.8。

3.4 對比實驗

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

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

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

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

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

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

3）ES的存儲和計算資源對成本和命中率的影響

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

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

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

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

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

4 結(jié)束語

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

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

參考文獻：

［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.