邊緣計算中最大化服務價值的任務卸載算法*

王 恒 蔣大成 宋曉華

（西安工業大學電子信息工程學院 西安 710021）

1 引言

隨著微電子和通信技術的不斷發展，出現了大量新的應用，如基于人臉識別的智能門禁［1］、智能車輛網絡［2］和虛擬現實［3］。這些應用程序通常是計算密集型的，并且對延遲敏感［4～5］。但物聯網設備通常體積較小（如智能手機），這進一步導致設備的計算和通信能力有限。為了提高物聯網系統的計算和通信能力，邊緣計算作為一種新興的計算架構來解決這一問題［6］，旨在網絡邊緣提供計算資源，為資源受限的物聯網設備提供處理計算能力［7］。物聯網任務首先上傳到邊緣網絡，然后在邊緣網絡中進行處理。之后，結果將返回到相應的物聯網設備［8］。通過將任務從資源受限的設備轉移到功能強大的邊緣設備上，可以減少系統整體延遲和能耗。因此，如何將邊緣計算中的任務進行合理地卸載是一個關鍵問題。

針對邊緣計算下的任務卸載，提出了HBTS算法，該算法更多的面向用戶，以實現最大化服務價值為目標，從而有效地降低系統延遲和能耗。

2 系統模型

2.1 場景描述

本文研究了邊緣計算中的任務卸載方案，該方案適用于高度集成的任務，這些任務必須作為一個整體卸載到邊緣設備上。卸載場景如圖1所示，其中網關任務隊列中的一些等待任務如箭頭所示，邊緣設備由一個正方形來表示。每個任務由一個矩形表示，其模式表示不同的任務類型。此外，還有一個報頭設備，它在有等待任務和可用邊緣設備時執行卸載決策。當沒有空閑的邊緣設備時，為了確保高優先級任務具有優先執行權并有足夠的計算性能，需要停止就近邊緣設備上當前優先級較低的任務，將資源分配給優先級最高的任務。如果所有網關中的任務總數不超過邊緣設備的數量，則每個任務可以獲得一個執行機會。否則，每個邊緣設備將被分配一個任務，其余任務必須等待即將空閑的設備，這將觸發新一輪決策。否則，每個邊緣設備將被分配一個任務，其余任務必須等待即將空閑的設備，這將觸發新一輪決策。

圖1 二進制卸載場景

2.2 邊緣計算系統模型

邊緣計算系統的模型圖如圖2所示。每個網關負責從與其相連的物聯網傳感器或終端設備收集數據。物聯網設備通常具有較低的計算能力［9～10］，因此主要負責數據收集和預處理。通過這些數據，網關可以根據傳感器或終端設備的要求啟動計算任務。每個網關都設置一個任務隊列，用來緩存在等待中的任務。然后，網關將任務卸載到分布式協作的邊緣設備組中，其中有一個負責管理資源的報頭，如果有可用的邊緣設備并且任何網關的任務隊列都不為空，報頭就會執行一個卸載方案。

圖2 邊緣計算系統模型

2.3 服務價值定義

針對二進制的任務卸載，設計了面向用戶的最大化服務價值的評價指標來說明用戶獲得的量化的價值與性能（延遲或能耗）之間的關系。

服務價值是最終用戶獲得的總價值的總和，通過應用程序的實際性能（如響應時間或能耗）進行評估。本文提出了一個價值函數來表示價值和性能之間的聯系，可以表示為

其中，p，Pe和Pa分別表示價值的數值、應用性能和動態性能參數。Pa反映了用戶獲得的價值和應用程序性能之間的時間變化關系。

式（1）定義了服務價值的一般模型，將其應用于實際應用時，值函數可以實現應用程序的主要特性，包括給用戶帶來的功能收益和性能指標。對于本文研究的邊緣計算系統，重點研究任務完成延遲和設備能耗的性能。

2.4 問題定義

使用D，G和T表示所有網關上的邊緣設備、網關和任務的數量。所有邊緣設備和網關的集合由D={1，2，3，…，d}和G={1，2，3，…g}表示。網關g中的任務集合表示為T={1，2，3，…，t}。使用pt(S)表示任務t的價值函數，其中S是總任務延遲并且t∈T。同樣，設備d的價值函數表示為pd(E)，其中E是執行給定任務邊緣設備的能量損耗。

任務t到邊緣設備d分配所獲得的總價值是相應的任務值和設備值之和，可以表示為

任務和邊緣設備之間的分配關系可以用一個D×T的順序矩陣X。二進制變量x(d，t)表示元素是否位于第d行和第t列，表示任務是否分配給邊緣設備d。x(d，t)=1表示任務t將被卸載到邊緣設備d中，x(d，t)=0則相反。如果有多余的邊緣設備，也就是當T＜D時，將會有D-T個邊緣設備無需分配任何任務，因此無需卸載導致的能耗。根據價值函數的定義，一個邊緣設備d無需能耗即可獲得最大值pmax(d)，其中d∈D~，D~表示未分配任務的邊緣設備集合。相反，如果任務數量超過邊緣設備數量，即T＞D，將會有T-D個未分配的任務，由于完成時間的不確定性而無法獲得價值。服務價值是所有任務和邊緣設備的總價值之和，表示為

在式（3）的右項中，第一部分是已分配任務和設備的值總和，第二部分是未分配任何任務的空閑邊緣設備獲得的總值。

綜上，針對邊緣計算中的任務卸載問題可以形式化表示為

式中，約束（4）表示x(d，t)是一個二進制變量。約束條件（5）和（6）意味著給定的任務不能卸載到多個設備上，給定的設備最多只能分別分配一個任務。約束（7）確保方案能夠充分利用可用設備來完成等待任務。如果有足夠的邊緣設備，每個任務都可以獲得執行的機會。否則，每個設備都應該加載一個任務，剩下的任務必須等待更多空閑設備。

3 HBTS算法

針對邊緣計算系統中的任務卸載問題，提出了一種啟發式算法，即HBTS算法。該算法可以在多項式時間內找到問題P的局部最優解，從一個隨機初始化開始，并重復進行一個本地操作，即傳輸操作和交換操作，如果它們可以提高目標值ν(x)。轉移操作則將未分配任務或邊緣設備的任務重新分配，交換操作改變了兩個任務或者兩個邊緣設備之間以前的分配，因此它們都可以滿足P的條件約束，該算法的偽代碼如下：

轉移操作的流程圖如圖3所示，首先將HBTS算法的卸載策略進行保存，如果任務數量大于邊緣設備數量，將所有未被分配的任務檢索出來，由于任務未被分配，此時的二進制變量為0，再對所有未被分配的任務進行遍歷，將其二進制變量置為1，如果可以提高平均服務價值，則更新卸載策略，再將二進制變量置為0。如果任務數量小于邊緣設備數量，將所有未被分配任務的邊緣設備檢索出來，由于邊緣設備上未被分配任務，此時的二進制變量為0，再對所有未被分配任務的邊緣設備進行遍歷，將其二進制變量置為1，如果可以提高目標值ν(x)，則更新卸載策略，再將二進制變量置為0，最終輸出最新的卸載策略X′。

圖3 轉移操作流程圖

交換操作的流程圖如圖4所示，首先將HBTS算法的卸載策略進行保存，如果任務數量大于等于邊緣設備數量，遍歷所有任務，交換兩個邊緣設備上原有的分配，如果可以提高平均服務價值，則進行交換，更新卸載策略。如果任務數量小于邊緣設備數量，遍歷所有的邊緣設備，將部署在兩個邊緣設備上原有的任務進行交換，如果可以提高平均服務價值，則進行交換，更新卸載策略，最終輸出最新的卸載策略X′。

圖4 交換操作流程圖

4 實驗和評估

4.1 實驗設置

實驗使用Matlab平臺實現，為了簡化模擬，假設有10種類型的任務。同一類型的任務在任務值函數中有相同的最大值和最小值，它們是從集合{0.1，0.2，…，1.0}中隨機抽樣的［11］。每種類型也分配了不同的正態分布，以確定單個任務的大小。每個任務都有其特定的硬閾值和軟閾值［12］，它們在(，)范圍內均勻采樣，和分別是所有可用邊緣設備中任務的最短和最長可能完成時間。類似地，對于每個設備的值函數，最大值和最小值也從集合{0.1，0.2，…，1.0}中隨機選擇。每個邊緣設備值函數在（，）范圍內均勻分布。其中和，是設備在等待處理的所有任務中可能消耗的最低和最高能量。每個網關的任務隊列中的任務數是一個均勻分布在［1，5］內的隨機正整數值［13］。每個任務從10種任務類型中隨機選擇，然后根據與其類型相關的正態分布分配大小。此外，讓所有任務的處理密度都為Ct=737.5cycle/bit，t∈T。

將本文提出的HBTS算法的性能與以下算法進行比較。

窮舉法（Exhaustion）［14］：這是一種蠻力方法，通過窮舉搜索所有可能的決策來找到最優卸載方案；由于其計算復雜度非常高，因此該方法僅適用于小型網絡環境。

貪心算法（Greedy）［15～16］：如果D≥T，所有任務都被排序成一個隨機序列，然后每個任務按順序被貪婪地分配一個目標設備，該設備可以在所有可用設備上最大限度地提高操作系統的性能。如果D＜T，因為每個設備都可以被分配一個任務，所以首先隨機地對設備進行排序，然后輪流貪婪地為每個設備選擇任務，這樣就可以在所有未分配的任務中最大程度地提高服務價值。

隨機算法（Random）［17］：所有任務按隨機順序排序，然后從所有可用設備中隨機選擇一個設備，直到分配完所有任務或沒有可用設備為止。

考慮到實際邊緣計算環境的隨機性，比較了4種算法在500個隨機生成的環境設置下的統計性能，包括平均服務價值、平均運行時間、性能方差。性能方差定義為給定方法的解與窮舉法的解之比的方差，用來衡量最優解的穩定性。

4.2 實驗結果

4.2.1 HBTS算法與主流算法的對比

為了表示本文提出的算法的較優性，將其性能與其他3個算法進行了比較。由于窮舉法搜索所有可能的解，其運行時間非常長。因此，測試了一個小規模環境，包括D=8和G=3智能網關。圖5（a）、（b）、（c）分別顯示了服務的平均值、性能差異和平均運行時間。可以看出，所提出的HBTS算法比最優窮舉算法的性能更好，并且在平均服務價值和性能方差顯示的解的穩定性方面顯著優于其他基線。HBTS算法的平均運行時間也低于其他算法，證明了該算法具有較高的效率。

圖5 算法對比

4.2.2 邊緣設備數量的影響

根據邊緣計算系統中可用的不同數量的邊緣設備來評估服務價值，如圖6（a）、（b）所示。將空閑邊緣設備的數量從2變為10，并比較平均服務價值和性能差異。網關G的數量設置為3，每個網關中等待任務的數量從1到5進行統一采樣，這意味著總任務的數量T在［3，15］的范圍內變化。從圖6可以看出，所提出的HBTS算法帶來了最優的解決方案，可以提供最大的服務價值，性能方差顯示了最高的穩定性。此外，平均服務價值隨著服務器數量的增加而顯著增加。這是因為隨著邊緣設備數量的增加，有著更大的解決方案空間，因此改進解決方案的可能性更高。

圖6 邊緣設備數量的影響

4.2.3 任務數量的影響

根據等待任務的數量來評估平均服務價值性能。如圖7（a）、（b）顯示了任務數從2增加到11時的平均服務價值和性能差異。對于每個生成的環境設置，將可用邊緣設備的數量固定為8，將網關的數量固定為5，其中給定數量的任務是隨機分布的。可以看出，本文提出的HBTS算法可以得到最優的服務價值且方差最低的解，并且平均服務價值隨著任務數的增加而增加。

圖7 任務數量的影響

5 結語

為了使邊緣計算網絡中各種應用程序可以更好地給用戶帶來實際價值，提出了服務價值作為性能指標，主要包括延遲和能耗，并建立邊緣計算系統的模型，針對邊緣計算的任務卸載問題，提出了HBTS算法，該算法旨在最大化服務價值，仿真結果表明，與其他主流算法相比，本文提出的HBTS算法可以實現最大化服務價值，效率顯著提高。