算力網絡環境下基于勢博弈的工作流任務卸載優化機制

姜玉龍 東 方 郭曉琳 羅軍舟

（東南大學計算機科學與工程學院 南京 211189）

（計算機網絡和信息集成教育部重點實驗室（東南大學）南京 211189）

（jyl1105@seu.edu.cn）

隨著人工智能與移動互聯網的不斷發展，遠程智能監控[1]、自動駕駛[2]等為代表的新型業務應用大量涌現，這些應用通常需要消耗大量的計算資源[3].同時，隨著應用越來越復雜，通常以微服務[4]的形式進行開發部署，此時一個應用往往可拆分成多個具有數據依賴與時序依賴關系的子任務集合，通常可表示為工作流結構[5]. 圖1 展示了2 種典型的工作流結構：鏈式工作流應用和有向無環圖（directed acyclic graph，DAG）式工作流應用. 鏈式工作流應用為一系列順序執行的子任務，如：采用深度神經網絡（deep neural network，DNN）模型（如VGG[6]）對圖像進行識別，其神經網絡模型可表示為若干順序執行的不同模型層次（如卷積層、池化層、全連接層等）[6-8]，并可按層進行任務劃分與卸載；而DAG 式工作流[5,9-10]則通常由多個分支與匯聚結構組成，比如：智能道路監控需要并行執行多項子任務，可以用DAG 圖來描述.

目前終端設備由于計算能力有限，難以支撐工作流應用的執行[11]，而云服務器雖然具有豐富的計算資源，但端云間較大的網絡通信延遲[9]將極大降低工作流應用的執行性能. 邊緣計算[12]通過將邊緣服務器部署在靠近用戶的網絡邊緣側為用戶提供計算資源，一方面補齊了終端算力不足的短板，另一方面降低了任務上云所帶來的通信開銷. 近年來已有不少相關工作[1,6-7,12-16]關注邊緣計算場景下的任務卸載與執行優化問題，然而這種端邊云之間的垂直協同模式通常僅考慮終端和相鄰邊緣計算資源的協同與卸載，無法有效融合廣域范圍內的算力資源，因此仍然難以滿足復雜工作流的高效能、低延遲需求.

近年來，邊緣服務器在網絡中的廣泛部署，使得算力從集中走向分布，計算從“點”到“網”逐漸成為網絡基礎設施的重要組成部分. 算力網絡[17]通過無處不在的網絡感知并連接分布式的算力節點，基于軟件定義網絡（software defined network，SDN）[18]的思想將路由層分為控制面和轉發面，綜合考慮網絡和計算資源狀況，將業務調度到合適的計算資源節點上.

然而，面對算力網絡中網絡環境高復雜強動態、算力資源高異構泛分布的特點，實現廣域算網融合環境下的資源高效融合和協同是一項挑戰. 具體表現在2 個方面：

1）計算模式方面. 許多新興應用其源與目的不一定相同[8]，如圖1 中的智能道路監控，橙色實線表示數據的傳輸路徑，道路圖像由路邊的攝像頭采集（源），而分析的結果需要傳到監控中心（目的）. 若采用傳統側重于靠近終端用戶的邊緣計算模式，將會在源端附近完成所有計算，然后再通過廣域網絡進行遠距離傳輸. 由于無法有效融合廣域范圍內的算力與網絡資源，將導致較差的任務執行性能. 因此算力網絡環境中的工作流調度需要同時考慮任務在多邊緣節點間的計算與傳輸開銷的協同分配模式，實現邊傳邊算，傳算協同.

2）問題求解方面. 廣域算力網絡環境和傳統邊緣計算環境相比，具有算力資源高異構、泛分布的特點，因此相較傳統端邊云間的任務卸載問題，算力網絡下的任務卸載問題具有更高的復雜性（不僅需要考慮任務的卸載還要決策數據的傳輸路徑）. 除此之外，應用的復雜性和環境的動態性將進一步增加任務卸載與資源分配的求解難度.

目前針對算力網絡環境下的復雜工作流任務，協同優化的工作還很少，而傳統邊緣計算環境下的工作流卸載的工作[9-10,19-20]無法直接適用. 為此，本文研究了算力網絡環境下工作流任務的卸載與資源分配優化問題，主要貢獻有3 個方面：

1）分析了算力網絡下的工作流任務卸載與執行模式，并提出了算力網絡環境下工作流任務卸載與資源分配問題. 綜合考慮了算力網絡中的網絡環境、計算資源以及工作流任務的拓撲信息，建立時延模型，為工作流任務卸載與資源分配問題提供優化目標.

2）針對鏈式工作流任務，設計并實現了一種基于勢博弈[21]的分布式工作流卸載（decentralized workload offloading，DWO）算法. 首先根據卸載決策通過凸優化[22]方法得到最優資源分配方案；然后將卸載決策建模為一個加權擁塞博弈問題，并證明了該博弈是一種勢博弈（至少存在一個納什均衡解）和無政府代價[21]（price of anarchy，PoA）值. 另外，針對DAG 工作流任務，設計并實現了一種基于動態資源權重的啟發式工作流卸載（heuristic workflow offloading, Heu-WO）算法. 該算法將每個資源的占有情況記作資源權重，每個子任務基于資源權重選擇完成時間最少的節點進行卸載，并動態更新資源權重.

3）針對算力網絡環境下工作流任務卸載和資源分配問題，為了驗證本文所提算法的有效性，設計并實現了仿真實驗. 相比較最優解，本文所提算法DWO降低了一個維度（用戶維度）的時間復雜度，解的近似比高達94.6%，相比其他算法可以獲得最高3.2x 的加速比；本文所提算法Heu-WO 的時間復雜度為多項式級別，相比其他算法可以獲得最高2.8x 的加速比.從而驗證了本文所提算法的有效性.

1 相關工作

為了解決終端計算能力的限制，文獻[6, 13?15]從模型切分和卸載的角度出發，研究了將任務部分卸載到邊緣服務器上處理來降低任務的計算時延.其中LEIME[6]提出了一種基于多出口DNN 的低延遲邊緣智能方案來解決傳統多出口DNN 無法提供快速且一致的推理. 首先它在模型級別，提出了一種提前退出算法，以自動構建具有較低時間復雜度的最優 ME-DNN；在計算層面，提出了一種分布式卸載機制，在運行時微調任務調度，以維持動態環境中的高性能，具有接近最優性能保證的特性. Neurosurgeon[13]所考慮的計算任務是基于AlexNet，VGG 這樣的鏈式深度神經網絡模型，并按照層來考慮切分點位置，綜合網絡環境和終端設備算力及邊緣服務器的算力，找到一個最佳的切分位置使得總體的計算時延最低或者能量開銷最低. 文獻[14]提出了一種將 DNN 劃分為多個分區的技術，這些分區可以在本地處理或卸載到一個或多個強大的節點. 通過設計自適應 DNN分區方案和基于匹配游戲方法卸載計算的分布式算法來加快推理速度. 文獻[15]在基于正交頻分多址（orthogonal frequency division multiple access，OFDMA）的協同邊緣計算場景下考慮了卸載決策、協作決策、計算資源分配和通信資源分配問題. 用戶的延遲敏感任務可以在本地計算，或卸載到協作設備、MEC服務器. 目標是在延遲約束下最小化所有移動用戶的總能量消耗，并提出了一種兩級交替方法來解決公式化的混合整數非線性規劃（mixed-integer nonlinear programming，MINLP）問題. 在上層，使用啟發式算法來處理初始設置下的協作決策和卸載決策；在下層，基于當前卸載決策，通過深度強化學習更新功率、子載波和計算資源的分配. 但是由于啟發式算法和深度強化學習的聯合算法的算法復雜度會比較高，上述工作[6,13-15]基于傳統深度學習模型具有鏈式的特點，在研究模型切分時對于鏈式任務的切分難以表達現在復雜工作流任務，呈現DAG 的依賴關系.

針對日益復雜的應用，文獻[9?10, 19?20]研究了工作流任務的卸載問題. 其中，文獻[9]研究了具有預算約束下最小化工作流任務完成時間問題，即每個移動設備的預算都是有限的，并且必須確定哪些子任務應該在本地計算或者應該發送到邊緣服務器或云服務器，針對2 種合作模式（單邊緣服務器與云服務器協同和多邊緣服務器協同），分別設計了基于貪心策略的任務卸載算法. 文獻[10]研究了MEC 在依賴和服務緩存約束下的任務卸載問題，提出了一種基于表的啟發式任務卸載算法，該算法能夠預測卸載決策的影響. 通過使用時間消耗表來預測卸載某個子任務的影響力，從而做出卸載決策. 文獻[19]研究了具有通信延遲和應用程序完成截止日期的異構處理器上的工作流任務調度，提出了一種啟發式算法ITAGS，首先通過松弛原問題中的二元約束，轉化成凸問題，并獲得原問題最優目標的下界；然后為每個單獨子任務分配截止時間；最后貪婪地優化每一子任務調度. 文獻[20]提出了一種聯合工作流任務卸載和流調度的啟發式算法，利用每個任務圖的知識和流程的開始時間來做出任務卸載決策. 文獻[9?10, 19?20] 工作默認卸載是單跳的，沒有考慮到算力網絡環境中任務可以通過多跳的方式卸載到原本訪問不到的算力節點上，即算力路由問題，難以有效利用網絡中的算力資源.

為了有效利用網絡中的算力資源，文獻[8, 23?25]研究了任務在多跳網絡環境下的卸載問題. 其中，文獻[8]介紹了一種低延遲自適應工作負載分配框架，首先通過一種自適應任務劃分和放置算法來利用計算網絡資源. 其次，為了解決復雜的 DAG 拓撲，設計了一種分區和放置的最優尋路算法用于聯合優化計算尋路和工作負載分配. 文獻[23]研究了工業物聯網場景下多跳計算卸載中的計算卸載和通信路由問題，以最小化每個任務的計算時間和能量消耗為目標，將聯合優化問題制定成一個勢博弈問題；通過一種自由約束機制來確保有限的改進路徑可以達到納什均衡，提出了一種多跳協作消息傳遞機制并開發了2 種可以實現納什均衡的服務質量（quality of service，QoS）感知分布式算法. 文獻[24]研究了聯合多任務部分計算卸載和網絡流調度問題，目標是最小化所有任務的平均完成時間，提出了一種聯合部分卸載和流調度的啟發式算法，通過考慮設備的等待時間和網絡流的開始時間來決定部分卸載率；同時使用McCormick 包絡將公式化的MINLP 問題松弛成線性規劃（linear programming，LP）問題，以提供下界. 文獻[25]提出了一種避免分割網絡的啟發式方法和一種可以優化多跳協作網絡中計算任務分配的迭代任務分配算法，來評估多跳網絡中計算卸載的效果. 上述工作[8, 23-25]聚焦卸載問題，沒有考慮資源分配的問題，而是事先聲明一個子任務需要多少的計算資源或者考慮排隊、均勻分配資源，然而對于不同任務，適當的資源分配算法對滿足延遲要求是至關重要的.

綜上，現有的研究工作難以適用于算力網絡環境下的工作流卸載問題，因此本文以最小化平均工作流任務完成時間為目標，研究了算力網絡環境下工作流任務卸載與資源分配問題.

2 問題定義和建模

2.1 問題分析

本文旨在研究一種算力網絡環境下的通用工作流任務的執行優化機制，對于許多新興業務應用其源與目的不一定相同[8]，例如：智能安防、遠程控制、增強現實應用等. 圖2 展示了算力網絡環境下算力節點協作處理工作流任務的場景. 在這一場景中，算力節點高效協同，為低延時的工作流任務提供更好的性能保障. 如圖2 中任務執行路徑所示，數據在終端設備（攝像頭）上產生，需要經過多個算力節點協同分析處理，最終將數據的識別結果發送至遠端的智能監控中心. 在這種執行模式下，數據源和目的之間的路徑選擇、工作流任務的卸載位置以及算力節點的資源分配情況都將影響應用的執行性能. 因此，本文研究的問題是在算力網絡環境下聯合任務卸載和資源分配優化問題，以最小化工作流任務的端到端延遲.

2.2 問題建模

1）系統建模. 我們把算力網絡建模成一個有向無環圖[5]（DAG）：GE=(M,ER)，其中M表示算力節點的集合，ER表示算力節點之間物理鏈路的集合. 我們用Fm表示算力節點m∈M的計算能力（以FLOPS 來衡量）；Bm,n表示算力節點m到算力節點n之間的帶寬.

2）任務建模.U表示用戶的集合，由于工作流任務由多個具有依賴關系的子任務構成，將任務建模成一個有向無環圖：GT=(S,SR)，其中S表示工作流任務中子任務的集合，SR表示子任務之間依賴關系集合.c u,s表示用戶u中子任務s所需的計算量，du,s表示子任務s的中間數據/輸出結果所需的數據傳輸量. 本文中主要符號及含義如表1 所示.

基于上述問題建模，本文研究的問題包含二維影響工作流任務執行性能的決策變量：卸載決策和資源分配決策. 卸載決策決定將工作流任務中的子任務提交到哪個算力節點Au,s上進行執行；資源分配決策決定工作流任務中提交的子任務分配計算資源的比例Pu,s，以及分配的帶寬資源的比例Qu,s,t.

2.3 問題定義

工作流任務的處理延遲包括計算延時和中間數據/結果的傳輸時延2 部分. 對于任意用戶u的子任務s，其計算延時可以通過其計算量和所分配的計算資源表示：

Table 1 Meaning of the Main Symbols表1 主要符號的含義

本文用K表示子任務間的傳輸路徑集合，Ku,s,t則表示用戶u的子任務s到子任務t的傳輸路徑，由卸載決策A決定，如式（2）所示：

結合式（1）和式（3）可以得出工作流任務的子任務s的完成時間為：

其中，s.pre表示子任務s的前驅子任務集合.

因此，工作流任務的完成時間即為最后一個子任務(s_last)的完成時間：

本文的研究問題，即聯合優化工作流任務的卸載決策、資源分配決策來最小化所有用戶的平均完成時間，該問題P可以表示的數學模型為：

目標函數：

約束條件：

其中，A,P,Q分別表示卸載位置決策、算力比例決策和帶寬比例決策.I(·)表示指示函數，當括號里等式成立時值為1，反之則為0. 約束式（7）和式（8）分別保證分配給用戶的算力資源和帶寬資源大于0，是連續性變量；約束式（9）（10）保證分配的資源比例之和小于或等于1；約束式（11）表示卸載位置變量的取值范圍，是離散型變量. 在有M個算力節點、N個用戶，每個用戶的工作流應用含有S個子任務的場景下，卸載決策的空間為MNS，因此，該問題是一個混合整數非線性規劃問題，同時也是一個NP 難問題.

3 工作流卸載算法

本文研究了2 種典型的工作流結構：鏈式工作流任務和DAG 式工作流任務. 針對鏈式工作流任務，本文提出了一種基于勢博弈的分布式工作流卸載算法DWO 來最小化工作流任務的完成時間；針對DAG式的工作流任務，本文提出了一種基于動態資源權重的啟發式工作流卸載算法Heu-WO 來減小工作流任務的完成時間.

3.1 鏈式工作流卸載算法

通過對鏈式工作流結構進行分析，可以將原問題P分解成2 個子問題：子問題P1根據卸載策略和路徑選擇策略決定最優的資源分配方案；子問題P2根據最優分配策略決定卸載位置和傳輸路徑，該問題基于勢博弈進行求解.

3.1.1 最優資源分配策略

子問題P1目標是在給定卸載策略和路徑選擇策略的前提下，決定最優的資源分配策略使得工作流任務完成時間最小.

目標函數：

在P1中，式（12）表示的目標函數是凸函數，式（13）和式（14）表示的定義域為凸集，式（15）和式（16）表示的也是凸函數，因此P1是一個凸優化問題，且最優解滿足KKT（Karush-Kuhn-Tucker）條件. 首先給出P1的拉格朗日函數：

其中，α和β分別表示2 個約束項的參數. 從而獲得拉格朗日對偶問題和KKT 條件，通過求解KKT 條件，得到最優的資源分配策略，資源分配的表達式為

其中，Du,s(A)表示卸載決策A中與用戶u的子任務卸載到同一節點的用戶和子任務集合，Ru,s,t(A)表示卸載決策A中與用戶u的子任務s到子任務t占有相同鏈路的用戶和子任務集合. 根據最優資源分配策略，將式（17）中的和式（18）中的代入到式（12）中，可以獲得在卸載策略A下的各個用戶的工作流任務完成時間

因此，原問題P可以表示為P2問題：

子問題P2的2 種變量均為離散型，本文考慮工作流子任務的個數為S，故可行的解空間大小為|M||U|S.解空間是指數級的. 本文采用基于勢博弈的方法來解決子問題P2.

3.1.2 多用戶卸載博弈（multi-user offloading game，MOG）

基于3.1.1 節的分析，本文設計了一種基于勢博弈的方法來解決工作流卸載問題. 首先將子問題P2建模為一個多用戶卸載博弈G={U,Au,Vu}，其中U表示用戶集合，Au表示用戶u的卸載決策，Vu表示用戶u的效用函數.

定理1.在最優資源分配條件下，用戶間的相互作用可以被建模為一個資源依賴加權的擁塞博弈，每個用戶的代價函數為

本文將用戶的效用函數Vu定義為該用戶工作流的完成時間，即

定義1.納什均衡[21]. MOG 的策略A?是納什均衡解當且僅當任意用戶無法通過改變自身策略降低自己的效用值Vu.

接下來，本文分析了MOG 的納什均衡的存在性，關鍵在于證明MOG 是一個嚴格勢博弈[7].

定義2.（嚴格 勢博弈[21]） 博弈G={U,Au,Vu}是 嚴格博弈需滿足式（24）：

其中Φ(Au,A?u)表示為勢函數.

為了證明MOG 是一個嚴格勢博弈，本文將勢函數定義為

下面分3 種情況討論：

3.1.3 基于勢博弈的分布式工作流卸載算法

針對鏈式工作流應用，本文提出了基于勢博弈的分布式工作流卸載算法，該算法的設計依據是基于博弈論的有限改進性質（在有限迭代輪次下可以獲得一個納什均衡解[26]）. 偽代碼如算法1 所示.

算法1.DWO 算法

算法DWO 根據MOG 的有限改進性質，且一次只允許一個用戶對它的策略進行改善. 首先，每個用戶隨機地選擇一個可行策略；然后，在每一輪迭代過程中按序選擇一個用戶對它的策略進行改善，并更新到總的策略集上，直到所有的用戶都不再更新策略，即算法達到納什均衡.

3.1.4 時間復雜度分析

假設算力節點的數量為M，用戶數量為U，工作流任務拓撲中的節點數為S，根據式（17）和式（18）可知資源分配策略的時間復雜度為O(US). 在每一輪迭代過程中，用戶進行決策的時間復雜度為O(MSUS).假設算法DWO 經過C輪達到收斂，因此算法DWO的時間復雜度為O(CMSUS). 當子任務數量較少時可以有效進行求解；而針對子任務數量較多的場景，一種可行的優化思路是先篩選若干個子任務切分點，將子任務數量降低，從而降低時間復雜度.

3.1.5 PoA 分 析

本文探討算法DWO 的納什均衡解的有效性. 算法DWO 可能有多個納什均衡解，根據博弈論中的PoA 的定義，本文將最差的納什均衡解和最優解的比值定義為算法DWO 的PoA值.

其中：A表示算法DWO 的納什均衡解集，A?表示最優策略. 顯然可以得到PoA值的下界：

本文將介紹PoA值的一個上界.

根據納什均衡的定義，可得：

將所有用戶合成一個不等式，可得：

重新排序并重寫式（31），可得：

因為式（35）包含了DWO 的所有納什均衡解，同樣包含了最差的納什均衡解，因此：

3.2 DAG 式工作流卸載算法

針對DAG 式工作流，本文同樣將資源分配和任務卸載分開. 由于目標函數中含有不可微函數max(·)，本文基于松弛的資源分配策略進行資源分配；由于算法DWO 在子任務數量大的場景下其時間復雜度較高，難以在可接受的計算時間內獲得一個可行解. 因此，本文設計了一種基于動態資源權重的啟發式工作流卸載算法Heu-WO.

3.2.1 松弛的資源分配策略

針對DAG 式的工作流應用進行分析，由于DAG式工作流的完成時間中含有函數max(·)，故其目標函數不能像鏈式的工作流轉化成式（12）. 而函數max(·)也是凸函數[22]，所以該問題的目標函數式（6）仍然是凸函數；且定義域和約束函數與P1問題中的一致，故原問題的定義域為凸集，約束函數也是凸函數，所以該問題也是凸優化問題. 但是因為函數max(·)不可微，求解比較困難. 所以本文將函數max(·)松弛為求和函數∑(·)，即，將目標函數從式（6）松弛成式（12），這樣便可以通過3.1.1 節中的式（17）和式（18）求解得到該問題的資源分配方案.

3.2.2 基于動態資源權重的啟發式工作流卸載算法

針對DAG 式工作流應用，本文提出了一種基于動態資源權重的啟發式工作流卸載算法Heu-WO，它將每個資源的占有情況記作資源權重，對每個子任務基于資源權重選擇完成時間最少的節點進行卸載，并動態更新資源權重. 偽代碼如算法2 所示.

算法2.基于動態資源權重的啟發式工作流卸載算法Heu-WO

根據公平性原則，每個用戶對其子任務s選擇最佳的卸載方案，如算法2 行⑤表示選擇最小化子任務s的完成時間的卸載位置，行⑥～⑧更新策略和環境中的占用情況，以供其他用戶做出決策.

3.2.3 時間復雜度分析

假設算力節點的數量為M，用戶數量為U，工作流任務拓撲中的節點數為S. 由算法2，外部（行③，④）是雙層循環，故時間復雜度為O(US)；內部（行⑤）是對所有算力節點的一次遍歷，故時間復雜度為O(M). 綜上，本文所提算法Heu-WO 的時間復雜度為O(US M).

4 實驗結果與分析

本文進行了算力網絡環境下工作流任務的執行優化實驗，首先對實驗環境與參數進行說明，然后展示仿真結果并對其進行分析.

4.1 實驗環境與參數設置

本文使用擁有i7-12700K CPU，32GB RAM 的服務器作為算力網絡環境工作流任務執行優化的硬件平臺，軟件平臺采用Ubuntu 20.04 x86_64 操作系統，Visual Studio Code 1.73.1 版本以及Python3. 8 版本的編程環境，并采用了DAG 生成器[27]生成DAG 拓撲數據，以此代表具有依賴關系的工作流任務. 通過控制參數n和參數density來隨機生成不同的工作流任務，其中參數n控制DAG 的節點個數，即子任務數量；參數density表示DAG 密度，是邊數與節點數的比值，用于控制DAG 中節點間的邊數，即子任務間的依賴關系，density值越大，DAG 中的邊數越多，子任務之間的數據交互就越多. 為了便于理解，圖3 展示了DAG 生成器在不同參數下所生成的DAG 結構. 同時，本文的網絡拓撲也采用了DAG 生成器用于生成復雜的網絡環境.

本文實驗環境參數如表2 所示.

4.2 對比算法

為了驗證本文所提算法DWO 和算法Heu-WO的有效性，將DWO 和Heu-WO 與其他4 種算法進行對比實驗. 具體描述為：

1）低延遲自適應工作負載分配（low-latency adaptive workload allocation，LAWA）[8]. 該算法在已知一條最優傳輸路徑的前提下，通過聯合優化計算尋路和工作負載分配來降低工作流應用的完成時間.但是LAWA 沒有考慮如何尋找到最優路徑. 因此，本文先通過最短路徑算法獲得傳輸路徑.

Table 2 Experimental environment Parameters表2 實驗環境參數

2）最佳卸載（Optimal）. 該算法通過暴力求解方法遍歷卸載空間以獲取最優解. 但該方法的復雜度太高，難以在大規模場景下進行求解.

3）最近卸載（Nearest）. 該算法先根據任務的原數據量和結果數據量決策卸載到靠近發送方的算力節點或靠近接受方的算力節點上進行處理，用戶獨立選擇最短傳輸路徑，然后基于凸優化方法求得的最優的資源分配方案.

4）隨機卸載（Random）. 該算法指的是用戶將每個子任務隨機卸載到算力節點上，子任務傳輸獨立選擇最短路徑，然后基于凸優化方法求得最優的資源分配方案.

4.3 DWO 算法性能分析

驗證算法的性能以及收斂性. 本節在小規模鏈式工作流場景下進行了500 次獨立實驗，然后將結果按照Optimal 的值進行規格化處理，最后取平均值.

Fig.4 The performance of algorithms圖4 算法性能

如圖4 所示，DWO 算法可以很快達到收斂，與Optimal 相比，DWO 解的近似比高達94.6%，與其他算法相比，加速比最高達3.2x，Heu-WO 次之，然后依次是LAWA，Nearest，Random. LAWA 考慮了在最優傳輸路徑上進行卸載，有效利用了傳輸路徑上的計算資源，但是沒有聯合計算路徑和傳輸路徑，其最優傳輸路徑上的算力節點相比較其他算力節點未必是最優的. Nearest 是一種0/1 卸載，傳輸成本低，但是無法利用其他節點上的資源，導致計算時延大. Random隨機地選擇卸載位置會導致傳輸開銷大，在網絡帶寬小的情況下尤為突出.

4.4 Heu-WO 算法性能分析

4.4.1 算法效率分析

為了驗證Heu-WO 算法的效率，本節通過改變節點數量、用戶數量和子任務數量進行了3 組實驗.

圖5 展示了算法完成時間與算力節點數量之間的關系，用戶數量越多，算法的完成時間也就越長；隨著算力節點的增加，算法的完成時間呈現出線性增長的趨勢. 本文通過最小二乘法對各曲線進行線性擬合，得到的4 條近似直線，其斜率由上到下依次是0.044，0.087，0.122，0.169. 可以看出，算法完成時間與相應的節點數之間存在線性關系.

Fig.5 Impact of the quantity of computing nodes on completion time of algorithm圖5 算力節點數量對算法完成時間的影響

Fig.6 Impact of the quantity of users on completion time of algorithm圖6 用戶數量對算法完成時間的影響

圖6 展示了算法完成時間與用戶數量之間的關系，算力節點數量越多，算法的完成時間也就越多；隨著用戶數量的增加，算法的完成時間同樣呈現出線性增長的趨勢. 同樣通過最小二乘法對各曲線進行線性擬合，得到的4 條近似直線，其斜率由上到下依次是0.048，0.090，0.128，0.169. 可以看出，完成時間與相應的用戶數量之間也存在線性關系.

圖7 展示了算法完成時間與子任務數量之間的關系，其中：Cx_Ny表示在用戶數為x、算力節點數為y的情況下，隨著用戶數量與節點數量的增加，算法的完成時間相應地增加；子任務數量越多，算法的完成時間也就越大，同樣呈現出線性增長的趨勢. 本文通過最小二乘法對各曲線進行線性擬合，得到的4條近似直線，其斜率由上到下依次是0.20，0.40，0.41，0.79. 可以看出，完成時間與用戶數量和節點數量的乘積存在正比關系.

Fig.7 Impact of the quantity of sub-tasks on completion time of algorithm圖7 子任務數量對算法完成時間的影響

綜上，圖5，6，7 共同體現出該算法的完成時間與算力節點數量、用戶數量以及子任務數量均呈現出正比關系，從而驗證了3.2.3 節中所分析的Heu-WO的時間復雜度為O(US M).

4.4.2 驗證算力網絡環境資源的影響

本節驗證算力網絡環境資源對算法性能的影響，通過實驗分析平均時延與算力網絡環境資源（節點計算能力和帶寬資源）的關系.

圖8 展示了不同算法在不同算力節點計算能力下的平均時延. 隨著算力節點計算能力的增加，各個算法的平均時延均有所降低. 這是因為算力節點的計算資源越多，可以分配給用戶的計算資源相應地增加了，降低了計算帶來的時間開銷. 與其他算法相比， Heu-WO 算法實現了最低平均時延（加速比最高達2.7x）.

圖9 展示了不同算法在不同網絡帶寬下的平均時延. 隨著網絡帶寬的增加，各個算法的平均時延也均有所降低. 這是因為網絡帶寬越大，傳輸數據則越快，降低了數據傳輸的時間開銷. 與其他算法相比， Heu-WO 算法實現了最低平均時延（加速比最高達2. 4x）.

Fig.8 Relationship of average latency and computing capability圖8 平均時延與計算能力的關系

Fig.9 Relationship of average latency and bandwidth of network圖9 平均時延與網絡帶寬的關系

4.4.3 驗證節點數量和用戶數量的影響

本節驗證節點數量和用戶數量對算法性能的影響. 通過控制變量，分析平均時延與節點數量和用戶數量的關系.

圖10 展示了不同算法在不同節點數量下的平均時延，隨著節點數量的增加，各個算法的平均時延均有所降低. 這是由于資源增加使得用戶之間的資源競爭減弱，用戶可以分配更多的資源，從而降低了平均時延. 與其他算法相比， Heu-WO 保持最優（加速比最高達2.8x）.

Fig.10 Relationship of average latency and quantity of nodes圖10 平均時延與節點數量的關系

圖11 展示了不同算法在不同用戶數量下的平均時延，隨著用戶數量的增加，各個算法的平均時延均有所上升. 這是由于用戶數量增加加劇了用戶之間的資源競爭，從而增加了平均時延. 與其他算法相比，Heu-WO 仍保持最優（加速比最高達1.9x）.

Fig.11 Relationship of average latency and quantity of users圖11 平均時延與用戶數量的關系

4.4.4 驗證子任務數量的影響

圖12 展示了不同算法在不同子任務數量下的平均時延. 隨著子任務數量的成倍增加，各個算法的平均時延也呈現出線性上升的趨勢. 這是因為雖然子任務數量增加，而資源沒發生變化，子任務分配到的資源相應降低，從而導致平均時延的增加. 與其他算法相比， Heu-WO 保持最優（加速比最高達1.7x）.

Fig.12 Relationship of average latency and quantity of subtasks圖12 平均時延與子任務數量的關系

5 結論與展望

本文研究了算力網絡環境下工作流任務卸載與資源分配問題. 根據工作流應用的特點，針對鏈式工作流任務，本文提出了一種基于勢博弈的分布式工作流卸載算法DWO，首先已知卸載決策下的資源分配問題是一個凸優化問題，通過凸優化方法得到最優資源分配方案，基于凸優化求解的資源分配方案，將卸載問題建模成一個加權擁塞博弈. 本文證明了該博弈是一種勢博弈（至少存在一個納什均衡解）和PoA值；針對DAG 工作流任務，本文提出了一種基于動態資源權重的啟發式工作流卸載算法Heu-WO，每個子任務基于資源權重選擇完成時間最少的節點進行卸載. 數值仿真實驗表明，在子任務數較小場景下，DWO 可以有效地取得高近似比的解（94.6%），相比其他算法可以獲得最高3.2x 的加速比；Heu-WO 可以在較低多項式時間內進行求解，與現有算法相比，最高可以獲得2.8x 的加速比. 從而驗證了本文所提算法DWO 和Heu-WO 的有效性.

未來的工作包括3 個方面：

1）本文為了簡化問題，在考慮子任務間傳輸時只考慮了單跳的傳輸路徑（見式（2）），然而子任務間的傳輸可以是多跳的. 因此，下一步我們將對子任務多跳傳輸的路徑選擇問題做進一步研究.

2）DWO 具有一定的理論性，但是針對子任務數量大的場景，時間復雜度較高（見3.1.4 節），且難以適用于DAG 式工作流任務；而Heu-WO 雖然時間復雜度低，但是缺乏理論保證. 因此，下一步我們將考慮對DAG 式工作流任務的卸載問題進行松弛，采用勢博弈方法求解，并進行理論分析.

3）本文研究的工作流任務卸載問題只考慮了算力資源同構的場景. 事實上，在大規模算力網絡環境下存在大量的異構算力節點，如中央處理器（central processing unit，CPU）、圖形處理器（graphics processing unit，GPU）. 因此，異構算力網絡場景下的工作流任務卸載問題將是我們未來要進一步研究的工作.

作者貢獻聲明：姜玉龍負責算法設計、仿真與論文撰寫；東方負責提出論文整體架構與論文修訂指導；郭曉琳負責算法指導與文字把關；羅軍舟負責總體思路指導.