一種聯合時延和能耗的依賴性任務卸載方法

張俊娜 鮑 想 陳家偉 趙曉焱 袁培燕 王尚廣

1 （河南師范大學計算機與信息工程學院 河南新鄉 453007）

2 （智慧商務與物聯網技術河南省工程實驗室（河南師范大學） 河南新鄉 453007）

3 （網絡與交換技術國家重點實驗室（北京郵電大學） 北京 100876）（jnzhang@htu.edu.cn）

隨著物聯網的快速發展和萬物互聯時代的到來，智能移動設備在人們的日常生活中越來越普及.同時，諸如虛擬現實、人臉識別、圖像處理等[1]低時延、高能耗的應用程序得到了廣泛應用.但移動設備受電池容量、計算和存儲能力等諸多限制，直接運行上述應用程序會帶來較高的延遲和能耗，用戶體驗極差[2].為了提升用戶體驗，邊緣計算（edge computing,EC）應運而生，其在距離移動設備最近的邊緣網絡提供計算和存儲資源，目的是減少延遲來確保高效的網絡操作和服務交付[3].通過將移動設備中部分或全部計算任務卸載到邊緣服務器處理，可以解決移動設備在資源存儲、計算能力以及電池容量等方面存在的不足，并降低應用的延遲.

近年來，許多學者針對任務卸載進行了研究[4-7]，然而這些研究也存在一些局限性：1）只考慮單一優化目標.即只優化卸載任務的完成時間或能耗.如文獻[8]只考慮卸載任務的完成時間，無法滿足用戶對能耗的需求.2）假定卸載的多個任務相互獨立.現實中很多應用程序包含的任務往往存在依賴關系.例如，人臉識別應用程序包含特征提取和特征分類任務，且“特征提取”任務的輸出是“特征分類”任務的輸入.因此，只有“特征提取”任務成功執行，才能開始執行“特征分類”任務.3）默認邊緣服務器緩存有卸載任務所需的所有服務.文獻[9-10]均研究依賴性任務的卸載問題，但均假設邊緣服務器緩存有卸載在其上的所有任務所需的服務.現實生活中，任務的執行往往需要特定執行環境.例如，人臉識別應用程序中“特征提取”任務，只能被卸載到配置有相應機器學習服務的邊緣服務器才能被成功執行.若邊緣服務器上沒有配置該服務，將導致卸載任務無法執行.而邊緣服務器存儲資源有限，只能緩存有限服務，因此卸載任務時需考慮邊緣服務器緩存服務約束.4）假定邊緣服務器具有無限存儲和計算資源.文獻[11-12]均不考慮邊緣服務器的存儲和計算資源，而現實中邊緣服務器提供的資源是有限的，卸載任務時必須考慮資源受限問題，否則會出現任務卸載不成功的風險.

綜上所述，已有任務卸載研究往往忽略任務間的依賴關系，默認邊緣服務器緩存有任務所需的所有服務和具有無限資源，且大多只優化單一用戶需求.為了解決上述局限性，本文研究在邊緣服務器計算資源和服務緩存有限的情形下，權衡時延和能耗的依賴任務卸載問題，并提出了聯合時延和能耗的依賴性任務卸載方法（dependent task offloading method for joint time delay and energy consumption, DTO-TE）.

首先，放松優化函數中的二進制變量為連續變量，并修改相關約束，將問題轉換成凸優化問題進行求解.其次，將得到的小數解作為卸載概率進行迭代運算使其恢復成二進制解，作為應用程序中每個任務的可行卸載決策，并根據該決策計算任務的卸載優先級.最后，按照任務優先級從高到低依次將任務卸載到成本最小的邊緣服務器.若多個依賴任務卸載到不同的邊緣服務器，則采用改進粒子群優化方法（particle swarm optimization, PSO）求解邊緣服務器的最佳傳輸功率，從而獲得最小的傳輸時延和傳輸能耗.

本文的主要貢獻有4 點：

1）在邊緣服務器計算資源和服務緩存有限的約束下，建立了任務依賴模型、網絡模型、完成時間模型和能耗模型，并采用線性加權的方法將對時延和能耗的共同優化轉化為對成本優化的單目標優化問題.

2）針對非凸的NP-hard 問題，通過松弛約束中的二進制變量將其轉換成凸優化問題.采用凸優化工具求得可行卸載決策，從而確定任務的最優卸載順序.

3）若將多個依賴任務卸載到不同的邊緣服務器，邊緣服務器間因傳輸數據產生成本.為了最小化總成本，采用改進的粒子群算法求解邊緣服務器的最佳傳輸功率.

4）基于真實數據集，本文方法與已有的方法進行了充分的實驗對比.實驗結果表明，本文方法比其他對比方法在總成本上減少8%～23%.

1 相關工作

近年來，任務卸載作為EC 關鍵技術之一受到了廣泛的關注.針對任務卸載問題，許多學者提出了解決方法或研究思路，并取得了較好的研究成果.下面將對一些與本文研究密切相關的成果予以分析.

文獻[13]研究小蜂窩網絡下單個邊緣服務器的任務卸載問題，并提出了一種高效的低時延云邊端協同卸載方案，該方案不僅可以降低任務的總處理時延，還可以處理大量的用戶請求.文獻[14]在多基站的EC 場景下，研究多用戶任務卸載問題，該問題以最小化所有用戶最大任務執行時間為目標，提出了一種啟發式計算卸載方法.文獻[8]研究了兼顧邊緣服務器服務緩存的依賴任務卸載問題，以最小化卸載任務的完成時間為目標，提出基于凸優化的依賴任務卸載方法.該方法將每個任務卸載到完成時間最小的邊緣服務器上，從而優化整個應用程序的完成時間.文獻[15]在超密集組網的EC 場景下，聯合優化卸載決策和資源分配問題，提出了基于坐標下降法的任務卸載方案.然而，文獻[13-15]只考慮單一優化目標，即只優化時延或能耗，無法滿足用戶對時延和能耗的共同需求.

文獻[16]針對超密集網絡下獨立任務的卸載問題，提出一種基于雙深度Q 網絡的在線卸載方法，通過特定的神經網絡估計每個動作所獲得的獎勵值，獲得最優的任務卸載策略以及最佳的CPU 頻率和發射功率，從而最小化任務的完成時間和終端能耗.文獻[17]研究在邊緣服務器資源受限情形下的獨立任務卸載問題，為了有效利用EC 的計算資源和提高用戶體驗，以最小化所有移動設備的時延和能耗為目標，提出了一種高效的李亞普諾夫在線算法，獲得了最優的任務卸載和數據緩存決策.文獻[18]研究在多個邊緣服務器覆蓋場景下的獨立任務卸載問題.該文獻設計了一種概率優先的先驗卸載模型，將問題轉換成平衡時延和能耗的效用函數，提出基于遺傳算法的聯合卸載比例和傳輸功率的分布式先驗卸載機制.文獻[16-18]均假定卸載的多個任務相互獨立，然而現實應用程序中任務間往往存在依賴關系.

文獻[9]研究依賴任務的調度決策問題.在應用程序完成時間的約束下，將調度決策問題構建成以應用程序執行成本最小化為目標的優化函數，提出啟發式多用戶重分配卸載方法以獲取最優的卸載決策，從而優化任務的完成時間.文獻[10]提出一種面向多用戶的串行任務動態卸載策略，為所有任務做出近似最優的卸載策略，從而使平均完成時間和移動設備的平均能耗達到近似最優.文獻[19]研究在完成時間受到預定期限的約束下依賴任務的卸載問題，以最小化移動設備的能耗為目標，提出了一種高效的自適應卸載算法，確定哪些任務必須被卸載及卸載到哪個邊緣服務器.文獻[9-10,19]雖然考慮了任務之間的依賴關系，但均假設邊緣服務器上緩存有執行卸載任務的服務.因邊緣服務器的存儲能力有限，往往只能緩存有限的服務.

文獻[20]針對邊緣服務器只能緩存有限服務的情形，研究依賴任務的卸載和調度問題.為了降低所有卸載任務的完成時間，提出一種求解最優任務分配和高效調度的方法.文獻[11]研究具有時間約束的依賴任務卸載問題.為了最小化應用程序完成時間，提出了基于貪婪調度的個體時間分配算法.文獻[12]研究在服務緩存受限的EC 系統中依賴任務的調度問題.為了解決任務對邊緣服務器資源的競爭，將任務調度定義為以最小化時延為目標的優化問題，并在此基礎上，提出了上下文感知的貪婪任務調度算法以獲得最佳的調度決策.文獻[11-12, 20]均假設邊緣服務器的計算資源是無限的，可執行任意數量的任務.但現實中邊緣服務器往往具有有限的資源.

為了解決上述局限性，本文研究在邊緣服務器計算資源和服務緩存有限的情形下，權衡時延和能耗的依賴任務卸載問題，并提出了DTO-TE 方法.

2 系統建模和問題描述

本節首先介紹邊緣服務器間的網絡模型和任務間的依賴模型；然后詳細描述了任務卸載到邊緣服務器執行的完成時間模型和能耗模型；最后描述了在邊緣服務器計算資源和服務緩存有限的情形下，依賴性任務的卸載問題，并將其構建成以最小化總成本為目標的優化函數.

2.1 網絡模型

本文建立的網絡模型如圖1 所示，邊緣網絡由若干個基站組成，每個基站均部署1 個EC 服務器，不同EC 服務器具有不同的處理和通信能力，且通過無線方式相互通信.虛線方框中內容表示邊緣服務器緩存的服務，不同形狀的圖形表示不同的服務；實線表示邊緣服務器之間通過局域網或蜂窩網連接.

Fig.1 Network model圖1 網絡模型

集合M={m1,m2,···,ml,}表示EC 網絡中的集，其中l表示邊緣服務器的數量.從邊緣服務器m傳輸數據到邊緣服務器m′的 通信延遲為tmm′.當m=m′時，表示為同一服務器，此時通信時延為0.每個邊緣服務器最大限度地緩存服務，Mv表示可以處理任務v的邊緣服務器集，即任務v只能卸載到Mv中的邊緣服務器上才能被執行.此外，每個邊緣服務器具有有限的計算資源，采用CPU 周期表示.邊緣服務器m具有的計算資源為C（m）.tvm表示任務v卸載到邊緣服務器m上的執行時間，rvm表示邊緣服務器m執行任務v每秒所需要的CPU 周期.

2.2 任務依賴模型

本文研究將1 個應用程序卸載到EC 環境中.假定應用程序能被劃分成多個依賴任務，1 個任務僅能被卸載到1 個邊緣服務器，且任務執行需要計算資源和相應服務的支持.如圖2 所示，假設應用程序由4 個任務組成.只有菱形代表的服務可為任務2 提供執行環境，那么任務2 只能被卸載到緩存有菱形代表的服務的邊緣服務器上.此外，任務2 與任務1 存在依賴關系，即任務2 是任務1 的后繼任務，那么當且僅當任務1 執行完畢，且執行結果被傳輸到任務2卸載的邊緣服務器后，任務2 才可以執行.

Fig.2 Task dependent model圖2 任務依賴模型

本文采用有向無環圖（directed acyclic graph,DAG），G=（V, E）表示任務之間的依賴關系，其中V表示任務集，E表示邊集.為了便于描述，為應用程序構建DAG 時增加2 個虛擬任務vs和ve.vs表示開始任務，沒有前驅任務；ve表示結束任務，沒有后繼任務.這2 個任務無需被卸載，即在用戶設備執行時所需時間為0，那么應用（包含n個任務）DAG 的任務集為V={vs,v1,v2,···,vn,ve}.有向邊 (v,v′)表 示任務v和v′之間存在依賴關系，即任務v的輸出是任務v′的輸入.用dvv′表 示 任 務v到任 務v′需 傳輸 的 數 據 量.表1 總 結 了在本文中使用的關鍵符號.

Table 1 Key Symbols Meaning表1 關鍵符號意義

2.3 完成時間模型

由2.2 節可知，應用程序的完成時間從vs開始執行，至ve執行完畢.vs和ve為虛擬節點，所需的執行時間為0，那么vs執行結束時刻即為應用程序開始時刻，ve開始執行時刻即為應用程序結束時刻.當ve的所有前驅任務均執行完畢，并把結果傳回到用戶設備時，用戶設備可開始執行.由此可知，應用程序的完成時間可由組成其的任務完成時間及任務間的依賴關系得出.

通過2.2 節構造的應用程序的DAG 可知，任務v能夠執行時需滿足2 個條件：1）任務v所有前驅任務均執行完畢，且把執行結果傳輸至其被卸載的邊緣服務器；2）卸載任務v的邊緣服務器有計算資源執行任務v.

依賴任務被卸載至相同邊緣服務器，數據傳輸時延為0；卸載至不同邊緣服務器時，需要傳輸的數據量為dv′v，則傳輸時延可表示為

其中Rm′m是邊緣服務器m′到 邊緣服務器m的傳輸速率，tm′m表示m′與m之間的傳輸時延，可通過香農公式[10]計算得到：

其中B是信道帶寬，Pm′是邊緣服務器m′的傳輸功率，hm′m是m′和m之 間的信道增益，N0表示噪聲功率.

任務v可能由多個前驅組成，那么任務v接收到所有前驅任務執行結果的時刻為

其中Pred(v)表 示任務v的直 接前驅任務集合，tv′表示任務v′的開始執行時刻，tv′m′表 示任務v′在邊緣服務器m′上所需執行時間.

此外，本文研究場景中，邊緣服務器串行執行卸載至其上的任務.當任務v卸載到邊緣服務器m時，需要等待排在其前面的所有任務執行完才能被執行.假如排在任務v之前的任務為k，用SLm表示任務k被卸載的邊緣服務器m執行完畢的時刻，那么有

其中tk表示任務k真正的開始時刻，tkm表 示任務k在邊緣服務器m上的執行時間.

因此，任務v在邊緣服務器m上的開始時刻為

通過上述分析，應用程序的完成時間可表示為

其中二進制變量zmv表示任務v是否卸載到邊緣服務器m上 ，zmv= 1 表示是，zmv=0 表示否.tvm表 示任務v在邊緣服務器m上的執行時間.

2.4 能耗模型

執行應用程序的能耗包括在用戶設備和在邊緣服務器上產生的能耗.本文只關注邊緣服務器上產生的能耗、可能產生執行卸載任務的執行能耗，以及傳輸具有依賴關系任務之間的執行結果的傳輸能耗.

任務v在邊緣服務器m的執行能耗evm可表示為

假設2 個依賴任務 (v,v′)分別被卸載到邊緣服務器m′和 邊緣服務器m時，傳輸能耗可表示為

其中Pm′表 示邊緣服務器m′的傳輸功率.

因此，邊緣服務器的總能耗可以表示為

其中M′表 示任務v所有前驅任務所在的邊緣服務器集合.

2.5 研究問題描述

本文研究在邊緣服務器計算資源和服務緩存有限的約束下，聯合時延和能耗的依賴任務卸載問題.引入時延和能耗的偏好權重變量 ω(ω ∈[0,1])，其取值由用戶對時延和能耗的需求決定[21].如果對時延的需求超過能耗時，例如延遲敏感型應用人臉識別，用戶更關注時延時， ω ＜0.5；反之，例如執行應用的設備為電池容量有限的移動設備，用戶更關注能耗時，ω ≥0.5.因此，根據式（6）（9），權衡時延和能耗的應用程序總成本可定義為

綜合以上分析，本文研究問題可以優化為

其中：C1表示任務的卸載決策，取zmv=1 表示任務v被卸載到邊緣服務器m上，反之取zmv=0；C2表示每個任務只能卸載到緩存有其所需服務的邊緣服務器；C3表示依賴任務之間的執行順序；C4表示同一邊緣服務器上任務的執行順序；C5表示任務需要卸載到滿足其計算資源的邊緣服務器；C6表示邊緣服務器傳輸功率的取值范圍.

文獻[8]研究在邊緣服務器計算資源和服務緩存有限的約束下，時延最優的依賴性任務卸載問題，并證明了研究問題為NP-hard 問題.與文獻[8]研究問題相比，本文優化目標增加了能耗，因此，本文研究問題也屬于NP-hard 問題.

根據化學結構分類，腸內營養制劑可分為要素型與非要素型，要素型以氨基酸或蛋白水解物（氨基酸、肽類）為氮源，不需消化或少量消化便可吸收。非要素型是以整蛋白為氮源，需經過消化才可以吸收。對于消化和吸收功能基本正常的患者可選用非要素型腸內營養制劑，如營養不良，中度燒傷、創傷，昏迷不醒等患者。而對于消化和吸收功能受到不同損傷的患者更適用要素型腸內營養制劑，如重度燒傷、創傷，腸瘺，膽囊纖維化，急性胰腺炎，短腸綜合征等患者。

3 聯合時延和能耗的依賴性任務卸載方法

為了求解本文研究的NP-hard 問題，本節提出一種聯合時延和能耗的依賴性任務卸載方法，該方法可分3 步：1）松弛二進制變量.松弛式（11）中C1，將問題轉換為凸優化問題，即轉化NP-hard 問題，并使用凸優化工具進行求解，為每個卸載任務獲得多個介于[0,1]的松弛解；2）計算卸載任務的優先級.選擇每個任務松弛解中最大值作為其可行解，通過迭代運算確定每個任務的卸載優先級；3）完成卸載任務.按照優先級從高到低把任務卸載到邊緣服務器，若多個依賴任務可卸載到不同的邊緣服務器，則采用改進的粒子群方法求解邊緣服務器的最佳傳輸功率.

3.1 松弛變量和定義優先級

由式（11）中約束C1可知，本文研究問題為非凸問題.將C1中二進制變量zmv松弛為[0,1]（即C7），即假設每個卸載任務可被劃分為若干個子任務，且可被卸載到不同的邊緣服務器并行執行.因此優化問題可轉換為

引理1.式（12）為凸優化問題.

證明.由凸優化問題的判定準則可知，若式（12）同時滿足3 個條件時為凸優化問題：

1）目標函數為凸函數.目標函數為多元變量相加的一次函數，因此其Hesse 矩陣為零矩陣.又因零矩陣為半正定矩陣，所以目標函數為凸函數.

2）不等式約束為凸函數.式（12）中有多個不等式約束，但證明方法類似.現以最復雜的不等式約束C3為例進行證明.令c(x)=tv′+tv′m′+tmm′-tv，可以看出c(x)為多元相加的一次函數，Hesse 矩陣為0，因此約束C3為凸函數.同理，其他不等式約束也是凸函數.

3）等式約束為仿射函數.將式（12）中約束C2轉換成可得出g(x)為仿射函數.

綜上所述，式（12）為凸優化問題.證畢.

由于式（12）中傳輸功率是未知的，為了能求解凸優化問題，先將傳輸功率固定為其范圍內的隨機數（其最優值求解見3.2 節）.借助CPLEX[22]凸優化工具在多項式時間求得最優解.由于為連續變量，所以求得的解 0 ≤≤1.但本文中任務是不可拆分的，需把松弛后得到的結果恢復成原始問題的二進制值.

通過求得的每個任務可行的卸載決策，將DAG每條邊的權值設為wv′v=tv′m+ev′m，與結束任務相連的邊的權值設為0.任務v到結束任務的最大權值定義為任務v的優先級，采用L(v)表示，按照優先級倒序存放在隊列Q中.按照隊列Q卸載任務，不僅能保留任務間的依賴關系，還將DAG 中最長路徑上的任務優先卸載執行.

3.2 卸載任務

為了方便描述，再定義一些變量，用R(m)表示邊緣服務器m的剩余資源，Mv(R)表 示同時滿足任務v的計算資源和服務緩存約束的邊緣服務器集合.根據3.1 節得到的隊列Q依次將任務卸載到總成本最小的邊緣服務器.每卸載一個任務v，用式（13）～（17）更新其實際的開始時間AS T(v,mv)、 完成時間ACT(v,mv)、能耗SEC(v,mv) 、 總能耗TEC(v,mv)和 剩余資源R(mv).

在2.1 節中，為了能夠對式（12）求解，假設傳輸功率為隨機值.隨著傳輸功率取值的增大，時延會變短，但能耗會增加；反之隨著傳輸功率取值的減小，能耗會降低，但又會增加時延.為了能夠使應用程序的總成本最小，應求邊緣服務器的最佳傳輸功率.由文獻[23]可知，邊緣服務器間最佳傳輸功率問題為NP-hard 問題，因此只能采用啟發式算法進行求解.基于PSO 不依賴問題規模，設置參數少、收斂速度快的特點，本文采用改進的PSO 算法求解邊緣服務器間的最佳傳輸功率.

3.2.1 PSO 算法

PSO 是基于群體的進化方法，源于對鳥群捕食的行為研究，基本思想是通過群體中個體之間的協作和信息共享來尋找最優解.本文采用的PSO 在1維的搜索空間隨機產生V個粒子構成原始種群X={x1,x2,···,xv}.對應于本文研究問題，搜索空間為邊緣服務器間傳輸功率的可取值范圍.每個粒子包含位置和速度2 個屬性，位置表示搜索空間中一個解，即邊緣服務器間傳輸功率一個取值；速度表示粒子在搜索空間中尋找最佳傳輸功率的方向和大小.尋優過程中第k個粒子搜索到的最優位置表示為pbestk,全局搜索過程中粒子群搜索到的最優位置表示為gbest,第k個粒子的位置和速度更新的計算過程[24]分別為

其 中w表 示 慣 性 權 重，c1和c2為 學 習 因 子，rand()表 示[0,1]的隨機數，t表示迭代次數.

雖然經典PSO 算法收斂速度較快，但存在容易陷入局部最優解等缺點[25]，究其原因是因為經典PSO算法采用固定的慣性權重.較大的慣性權重有利于跳出局部解，便于全局搜索；而較小的慣性權重則有利于對當前的搜索區域進行精確局部搜索.當慣性權重的值恒定時，迭代前期缺少全局搜索能力或迭代后期缺少局部搜索能力，易造成PSO 方法陷入局部最優解，或后期在全局最優解附近產生振蕩現象.為了平衡全局和局部搜索能力，本文改進了經典PSO算法.

3.2.2 改進的PSO 算法

本文采用如式（20）所示的慣性權重線性遞減的調整方法進行尋優：

其中wmax，wmin分 別表示w的最大值和最小值，t表示當前迭代次數，tmax表 示最大迭代次數，通常取wmax=0.9，wmin=0.4[25].

3.2.3 適應度函數構造

PSO 算法采用適應度評價優化目標.本文將任務在邊緣服務器上執行產生的時延和能耗作為優化目標.構造適應度函數為

其中fitness值越小，越優，反之亦然.

3.3 方法實現

通過3.2 節的分析，本節將詳細描述聯合時延和能耗的依賴性任務卸載方法，即DTO-TE 方法.該方法為應用程序中所有卸載任務做出最優的卸載決策，從而優化任務卸載產生的總成本.

DTO-TE 的具體實現過程如算法1.

算法1.DTO-TE 方法.

輸入：任務集合V，邊緣服務器集合M，DAG；

輸出：任務的卸載決策和應用程序的總成本.

①根據3.2 節計算每個任務的優先級L(v)；

②按照任務優先級降序排列，并保存到卸載隊列Q；

③初始化AS T(v)=ACT(v)=TEC(v)=0；

④初始化邊緣服務器的剩余資源R(m)=C(m)；

⑤ whileQ≠?

⑥v=Q.top（），將任務v產生的能耗SEC(v)置0；

⑦ form∈Mv(R) do

⑧ 用3.2.2 節提出的改進PSO 算法計算m和v前驅任務所在的邊緣服務器間的最佳傳輸功率；

⑨ 計算保存v在邊緣服務器m的總成本；

⑩ end for

? 將任務卸載到成本最小的邊緣服務器；

? 根據式（14）（16）（17）更新ACT，TEC，R(m)；

? 保存v的卸載決策并從隊列Q刪 除任務v；

? end while

算法1 的分析過程分為2 個部分：1）獲取任務的優先級，按照優先級降序保存到隊列Q，并初始化任務和邊緣服務器信息（行③④）.2）判斷Q是否為空，若非空將其中的任務按順序卸載到總成本最小的邊緣服務器上.用改進的PSO 算法求解邊緣服務器間的最佳傳輸功率（行⑤～?）.更新任務的完成時間、總能耗和最終卸載的邊緣服務器的剩余資源，并從隊列中刪除已卸載任務，繼續循環，直至循環結束（行?～?）.

算法2給出了改進的PSO 算法求得最優傳輸功率的過程.

算法2.改進的PSO 算法.

輸入: 任務v前驅任務所在的邊緣服務器和任務v所在的邊緣服務器；

輸出: 最佳傳輸功率.

①初始化種群規模PopS ize=20 ， 加速因子c1=2，c2=2， 迭代次數為MaxIter；

② 根據式（21）,計算每個粒子的適應度值；

③ forj=1 toPopS ize

④ 初始位置xj和初始速度vj在搜索空間范圍內隨機產生；

⑤pbestj=xj；/*初始化每個粒子的歷史最優解*/

⑥endfor

⑦gbestj=max(pbestj)； /*初始化全局最優解*/

⑧ fori=1 toMaxIter

⑨ forj=1 toPopS ize

⑩ 根據式（20）更新權重；

? 根據式（18）（19）更新粒子速度vi和 位置xi；

? 計算適應度函數得出適應度值fitness(xi)；

? 更新粒子的歷史最優解；

? 更新全局最優解；

? end for

? end for

? 最佳傳輸功率=gbesti.

算法2 可分為5 個部分.1）定義了種群規模、加速因子、迭代次數和適應度函數（行①②）并隨機生成每個粒子的初始位置（傳輸功率的初始值）、初始速度、每個粒子的極值和全局最優解（行③～⑦）.2）進行迭代（行⑧～?），迭代部分可分為3 個階段： 更新權重；更新每個粒子的位置、速度；計算當前位置的適應度值（當前傳輸功率對應的成本）（行⑩～?）.3）比較當前粒子位置所得適應度值是否小于當前粒子歷史最優解的適應度值，若是，則更新粒子的歷史最優解；否則，當前粒子歷史最優解不變（行?）.4）比較當前粒子歷史最優解的適應度值是否小于全局最優解的適應度值，若是，則更新全局最優解（行?）.5）迭代結束后，將全局最優解作為最佳傳輸功率（行?）.

3.4 算法1 的時間復雜度分析

假設應用程序中的任務數量為n，邊緣服務器數量為l，每個任務的前驅任務數量為P，粒子種群規模為PopS ize，最大迭代次數為MaxIter.算法1 中，行①～④求解任務的卸載順序，并初始化信息，其時間復雜度為O(n2)；行⑤～?，按照隊列中任務順序進行卸載，但卸載過程中需用改進的PSO 算法求解邊緣服務器間的傳輸功率.由于本文采用的PSO 算法是一維的，故時間復雜度為O(MaxIter×PopS ize+PopS ize).所以算法1 中行⑤～?的時間復雜度為O(n×l×P×PopS ize×(MaxIter+1)).

綜上所述，算法1 總的時間復雜度為O(n2+n×l×P×PopS ize×(MaxIter+1)).

4 實驗驗證

4.1 實驗設置

本文實驗配置為：華碩靈耀S4000UA, IntelRCoreTMi5-7200U CPU@ 2.5～2.7 GHz， RAM 8192 MB,Windows 10 中文版 64 b，實驗環境為Python3.9.0.

在EC 網絡場景中[26]，假設網絡中有1 個應用程序需要卸載.該應用程序可分為若干個任務，根據任務之間的依賴關系，使用拓撲排序算法生成DAG.使用谷歌數據集[27]模擬每個任務在邊緣服務器上的處理時間和所需的處理資源.為了便于實驗，本文采用文獻[8]中的做法，將數據集中的任務執行時間和所需的處理資源統一映射至區間（1,10）.緩存某一服務的邊緣服務器數量并設置為邊緣服務器總數量的50%.邊緣服務器間信道帶寬和背景噪聲功率設置參考文獻[28]，邊緣服務器的能量系數、最大傳輸功率和信道增益參考文獻[18]，具體數值如表2 所示.

Table 2 Experimental Parameters表2 實驗參數

4.2 對比方法

由于沒有和本文方法完全一致的方法，故修改與本文類似的3 種已有方法作為對比方法.

對比方法1：文獻[8]提出的方法CP，其在邊緣服務器具有服務緩存和有限資源的約束下，優化應用程序的完成時間.根據本文的研究問題，在CP 方法的優化目標中加入能耗.

對比方法2：文獻[11]提出的基于貪婪卸載的個體時間分配方法ITAGS，其目標是在滿足完成時間約束的同時最小化通信和計算成本.為了能使ITAGS與本文所提方法進行比較，將 ITAGS 的約束條件修改為本文所提方法的約束條件.

對比方法3：文獻[12]提出的一種上下文感知的貪婪任務調度方法CaGTS，其目標是最小化任務的響應時間.將CaGTS 的優化目標和約束條件修改為本文方法的優化目標和約束條件.

4.3 數值歸一化

相較于時延，能耗的值較大，兩者不在同一數量級，導致時延在實驗結果中的占比小，對任務的卸載決策影響較小.為了使時延和能耗在同一數量級上，需要對時延和能耗進行歸一化.由于時延和能耗中存在未知變量，如傳輸功率作為一種常用的歸一化方法不適用于本文.

本文采用文獻[29]的方法，將時延擴大到與能耗同一數量級，即E/(α×T)≈1， 歸一化因子 α為正數.對應用程序包含的任務數量取不同值，并設定DAG邊數是任務數量的2 倍，邊緣服務器的數量為10.采用不同的 α值分別進行實驗，實驗結果如圖3 所示.隨著 α的增加不同任務數量下的E/(α×T)呈 下降趨勢.當α=10時 ，不同任務數量下的E/(α×T)≈1.因此，在下面實驗中，均將時延擴大10 倍后再計算應用程序的總成本.

Fig.3 Effect of α onE/(α×T)圖3 α 對E /(α×T)的影響

4.4 參數分析

為了降低參數對實驗結果的影響，本節對權重因子、邊緣服務器數量和迭代次數設置不同的值進行實驗，并觀察這些參數對實驗結果的影響.為了保證實驗結果的公正性，本文每類實驗結果均取運行100 次實驗后的平均值.

4.4.1 權重因子 ω的影響

設定實驗環境中邊緣服務器的數量為10，應用程序的任務數量為500，DAG 邊的條數為1 000.變化ω的取值，采用本文方法和3 種對比方法進行實驗.時延隨 ω變化結果如圖4（a）所示，可以看出 ω取值與時延成正比關系；能耗隨 ω變化結果如圖4（b）所示，ω取值與能耗成反比關系.也就是說，當 ω ＜0.5時，意味著用戶更偏好時延，此時，可增大用戶設備到邊緣服務器的傳輸功率，降低任務的傳輸時間；相反，當ω ≥0.5時，意味著用戶對能耗的需求較高，此時，邊緣服務器可以適當增大應用程序的完成時間，以降低邊緣服務器的能耗.為了驗證本文方法既能滿足用戶時延偏好又能滿足能耗偏好，下面每類時延對 ω分別取值為0.2 和0.8.

Fig.4 Effect of weights on time and energy consumption圖4 權重對時間和能耗的影響

此外，從圖4 還可以看出，無論 ω怎么取值，本文方法實驗結果均優于3 個對比方法.

4.4.2 邊緣服務器數量對總成本的影響

邊緣環境中邊緣服務器的數量對實驗結果也會產生影響.數量較少時，每個邊緣服務器需要處理的任務會較多.又因為邊緣服務器串行處理卸載在其上的任務，所以會增加任務的等待時延，從而增加應用程序的總時延.真實場景中因為成本問題，網絡提供商也不可能部署特別多的邊緣服務器.所以本節通過實驗，試圖找到一種合適的服務器數量設置，既不會增加過多的等待時延，又較符合真實場景中邊緣服務器的數量部署.

設定應用程序包含的任務數量為500，DAG 邊的條數為1 000， ω分別取值為0.2 和0.8，變化邊緣服務器的數量，采用4 種方法分別進行實驗，實驗結果如圖5 所示.隨著邊緣服務器數量的增加，4 種方法的總成本都明顯下降.主要因為當邊緣服務器數量為2 時，所有任務只能卸載到2 個邊緣服務器上，且卸載到同一邊緣服務器的概率變大，因此，任務在邊緣服務器上的等待時間變長，從而增加了總成本.而隨著邊緣服務器數量的增加，任務可選擇卸載的邊緣服務器數量也隨之增加，對邊緣服務器資源的競爭也在降低，因此，降低了任務在邊緣服務器的等待時間，從而降低了總成本.但當邊緣服務器數量不斷增加時，總成本降低幅度變得很小且趨于平穩，這是因為當邊緣服務器增加到一定數量時，在固定任務數下，系統資源變得充足且可以滿足所有任務.本文方法考慮從最長路徑卸載任務，可以減少任務在邊緣服務器的等待時間；此外，考慮待卸載任務的前驅任務卸載決策和邊緣服務器間的最佳傳輸功率.因此，與其他3 種方法相比，本文方法總成本最小.從圖5可以看出，邊緣服務器數量小于10 時，4 種方法的總成本降低速度較快；當邊緣服務器數量大于10 時，4種方法的總成本降低速度放緩.因此，服務器數量較佳設置應為10.

Fig.5 Effect of the number of edge servers on the total costs圖5 邊緣服務器數量對總成本的影響

4.4.3 PSO 迭代次數的影響

對應用程序包含的任務數量取不同的值，并設定DAG 邊數是任務數量的2 倍，采用不同的迭代次數分別進行實驗，實驗結果如圖6 所示.隨著迭代次數的增加，不同任務數量下的應用程序總成本均呈下降趨勢.而當迭代次數大于20 時，總成本下降的趨勢很小.繼續迭代可能會求得更優的傳輸功率，但對總成本的影響很小.而多余的迭代次數會增加算法的運行時間.因此，為了盡可能降低總成本，在接下來的實驗中，設置PSO 的迭代次數為20.

Fig.6 Effect of PSO iteration numbers on total costs圖6 PSO 迭代次數對總成本的影響

4.5 實驗對比

本節通過改變應用程序中任務數量、應用程序大小和任務間依賴關系，并設定邊緣服務器數量為10， ω分別取值為0.2 和0.8，PSO 迭代次數為20.采用本文方法與3 種對比方法進行實驗對比.

4.5.1 任務數量對總成本的影響

對應用程序包含的任務數量取值，并設定DAG的邊的數量是任務數量的2 倍，分別采用4 種方法進行實驗，實驗結果如圖7 所示.隨著任務數量的增加，4 種方法的總成本隨之增加，且CaGTS 增加得最多.究其原因為CaGTS 總將任務卸載到執行時間最小的邊緣服務器，不考慮前驅任務的卸載位置，導致產生大量傳輸能耗，從而增加總成本.ITAGS 和CaGTS 在任務數量較少時，總成本很接近，但隨著任務數量增加，ITAGS 的總成本小于CaGTS，主要因為ITAGS 每次貪婪卸載任務時，會兼顧前驅任務的卸載位置，從而減少了邊緣服務器間的通信成本.CP 和ITAGS 相比，在任務數量較少的時候，兩者的總成本很接近，但隨著任務數量的逐漸增大，CP 明顯優于ITAGS，究其原因是CP 優先卸載執行時間長且距離結束任務遠的任務，因此進一步降低了總成本.本文方法不僅先卸載距離結束任務遠的任務，還兼顧前驅任務的卸載位置.此外，本文方法在進行依賴性任務的數據傳輸時，采用最佳的傳輸功率降低了總成本.因此，此類實驗本文方法結果最佳.

Fig.7 Effect of task quantity on total costs圖7 任務數量對總成本的影響

4.5.2 應用程序大小對總成本的影響

設定應用程序包含的任務數量為100，任務大小隨機生成，執行時間根據谷歌數據集中任務大小和執行時間的比值求得，DAG 邊數為200，采用4 種方法分別進行實驗，實驗結果如圖8 所示.因為本文實驗中應用程序任務數量固定不變，所以隨著應用程序大小的增加，任務的平均大小也會增加，邊緣服務器處理任務的時延和能耗會隨之變大，且邊緣服務器處理任務所需的資源也在增加.因此，4 種方法的總成本也隨之增加.

Fig.8 Effect of App sizes on total costs圖8 應用程序大小對總成本的影響

由于CaGTS 和ITAGS 都不考慮任務卸載的優先級，導致距離結束任務較遠的任務可能后執行，會產生較長的等待時間.與CaGTS 和ITAGS 不同，CP 考慮了前驅任務的卸載位置，且優先卸載距離結束任務遠的任務，這將大大降低任務在邊緣服務器的等待時間.但由于CP 的傳輸功率是固定的，當任務大小增加時，任務間傳輸數據的成本就會增加，進而增加總成本.本文方法和CP 相比，在應用程序較小時，總成本非常相近.因為這2 種方法的邊緣服務器處理任務的時間相同.CP 是根據任務的執行時間對傳輸時間進行調整，因此在應用程序較小時，傳輸時間也相對較小.但隨著應用程序增大，邊緣服務器執行任務的時間也增大，因此CP 的傳輸時間也會增大，從而對總成本影響較大.本文方法無論在應用程序多大時，均能求得邊緣服務器的最佳傳輸功率，從而降低總成本.

4.5.3 任務依賴關系對總成本的影響

設定應用程序的任務數量為300，依賴關系，也就是DAG 邊數從100 遞增至1 000，實驗結果如圖9所示.DAG 邊數越多，任務間依賴關系越復雜，致使邊緣服務器間的傳輸次數的增加，從而導致這4 種方法總成本增加.當DAG 邊較少時，4 種方法的總成本都很相近.這是因為任務之間依賴較少時，邊緣服務器間的傳輸次數也較少，此時本文方法通過獲取最佳傳輸功率從而降低總成本的優勢不明顯.此外，本文方法為得到最佳傳輸功率，還需額外增加計算時延，從而導致在 ω =0.2（用戶更偏好時延），邊數為100～200 時，本文方法性能略差于對比方法.然而，隨著DAG 邊數的增加，邊緣服務器間的通信成本隨之增大，此時本文方法明顯優于其他3 種方法.

Fig.9 Effect of task dependency relationship on total costs圖9 任務的依賴關系對總成本的影響

相比于ITAGS 和CaGTS，本文方法優先卸載到結束任務路徑最長的任務，可以減少任務在邊緣服務器的等待時延；并且卸載任務時考慮到當前任務的前驅任務，通信成本也會降低.本文方法和CP 的總成本總體上接近，特別是在DAG 邊數在100～500之間，這是因為這2 種方法都優先卸載最長路徑上的任務且考慮前驅任務的卸載決策，但隨著邊數不斷的增多，本文方法明顯優于CP.這是因為任務之間的依賴關系變得越來越復雜，且任務的前驅任務也變多了，邊緣服務器之間傳輸數據的次數也變得頻繁，由于本文方法考慮邊緣服務器間傳輸數據時的最佳傳輸功率，可以獲得最小的傳輸時延和能耗，從而降低總成本.因此，本文方法取得的實驗結果最佳.由此可知，本文方法更適合應用依賴任務較多的情形.

5 總結與展望

本文研究了在邊緣服務器計算資源和服務緩存有限的約束下，權衡時延和能耗的依賴性任務卸載問題，并提出了DTO-TE 方法.DTO-TE 通過松弛研究問題的約束將其轉換成凸優化問題，并求得松弛解；根據松弛解求得滿足約束的可行解，從而確定任務的卸載優先級；按照優先級依次將任務卸載到成本最小的邊緣服務器上.實驗結果充分表明，本文方法在本文設置的各類實驗中均獲得了最優的結果.

雖然本文方法較對比方法有一定的優勢，但是仍存在一些不足：1）本文方法只進行了基于真實數據的仿真實驗，因實驗設備的限制并沒有在真實場景下進行實驗驗證；2）本文方法只建立了邊—端卸載模型，只適合較小規模應用程序，對于大規模應用程序，可以考慮建立云—邊—端協同卸載模型；3）本文方法只研究1 個應用程序卸載，實際應用中存在協同卸載多個應用程序的場景.因此，下一步工作擬研究云—邊—端模型中的多個應用程序的協同卸載，并在真實場景下對研究問題進行實驗驗證.

作者貢獻聲明：張俊娜提出論文思路，并全程指導實驗設計、結果分析和論文撰寫；鮑想負責實驗的實現和論文的撰寫；陳家偉和趙曉焱參與實驗設計和論文撰寫；袁培燕和王尚廣修改論文.