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

王 恒 蔣大成 宋曉華

（西安工業(yè)大學(xué)電子信息工程學(xué)院 西安 710021）

1 引言

隨著微電子和通信技術(shù)的不斷發(fā)展，出現(xiàn)了大量新的應(yīng)用，如基于人臉識別的智能門禁［1］、智能車輛網(wǎng)絡(luò)［2］和虛擬現(xiàn)實［3］。這些應(yīng)用程序通常是計算密集型的，并且對延遲敏感［4～5］。但物聯(lián)網(wǎng)設(shè)備通常體積較?。ㄈ缰悄苁謾C），這進一步導(dǎo)致設(shè)備的計算和通信能力有限。為了提高物聯(lián)網(wǎng)系統(tǒng)的計算和通信能力，邊緣計算作為一種新興的計算架構(gòu)來解決這一問題［6］，旨在網(wǎng)絡(luò)邊緣提供計算資源，為資源受限的物聯(lián)網(wǎng)設(shè)備提供處理計算能力［7］。物聯(lián)網(wǎng)任務(wù)首先上傳到邊緣網(wǎng)絡(luò)，然后在邊緣網(wǎng)絡(luò)中進行處理。之后，結(jié)果將返回到相應(yīng)的物聯(lián)網(wǎng)設(shè)備［8］。通過將任務(wù)從資源受限的設(shè)備轉(zhuǎn)移到功能強大的邊緣設(shè)備上，可以減少系統(tǒng)整體延遲和能耗。因此，如何將邊緣計算中的任務(wù)進行合理地卸載是一個關(guān)鍵問題。

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

2 系統(tǒng)模型

2.1 場景描述

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

圖1 二進制卸載場景

2.2 邊緣計算系統(tǒng)模型

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

圖2 邊緣計算系統(tǒng)模型

2.3 服務(wù)價值定義

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

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

其中，p，Pe和Pa分別表示價值的數(shù)值、應(yīng)用性能和動態(tài)性能參數(shù)。Pa反映了用戶獲得的價值和應(yīng)用程序性能之間的時間變化關(guān)系。

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

2.4 問題定義

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

任務(wù)t到邊緣設(shè)備d分配所獲得的總價值是相應(yīng)的任務(wù)值和設(shè)備值之和，可以表示為

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

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

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

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

3 HBTS算法

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

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

圖3 轉(zhuǎn)移操作流程圖

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

圖4 交換操作流程圖

4 實驗和評估

4.1 實驗設(shè)置

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

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

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

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

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

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

4.2 實驗結(jié)果

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

為了表示本文提出的算法的較優(yōu)性，將其性能與其他3個算法進行了比較。由于窮舉法搜索所有可能的解，其運行時間非常長。因此，測試了一個小規(guī)模環(huán)境，包括D=8和G=3智能網(wǎng)關(guān)。圖5（a）、（b）、（c）分別顯示了服務(wù)的平均值、性能差異和平均運行時間?？梢钥闯觯岢龅腍BTS算法比最優(yōu)窮舉算法的性能更好，并且在平均服務(wù)價值和性能方差顯示的解的穩(wěn)定性方面顯著優(yōu)于其他基線。HBTS算法的平均運行時間也低于其他算法，證明了該算法具有較高的效率。

圖5 算法對比

4.2.2 邊緣設(shè)備數(shù)量的影響

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

圖6 邊緣設(shè)備數(shù)量的影響

4.2.3 任務(wù)數(shù)量的影響

根據(jù)等待任務(wù)的數(shù)量來評估平均服務(wù)價值性能。如圖7（a）、（b）顯示了任務(wù)數(shù)從2增加到11時的平均服務(wù)價值和性能差異。對于每個生成的環(huán)境設(shè)置，將可用邊緣設(shè)備的數(shù)量固定為8，將網(wǎng)關(guān)的數(shù)量固定為5，其中給定數(shù)量的任務(wù)是隨機分布的?？梢钥闯?，本文提出的HBTS算法可以得到最優(yōu)的服務(wù)價值且方差最低的解，并且平均服務(wù)價值隨著任務(wù)數(shù)的增加而增加。

圖7 任務(wù)數(shù)量的影響

5 結(jié)語

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