面向“云—邊—端”算力系統的計算和傳輸聯合優化方法

陳星延 張雪松 謝志龍 趙 宇 吳 鋼

（西南財經大學數字經濟與交叉科學創新研究院 成都 611130）

（xychen@swufe.edu.cn）

傳統網絡范式以TCP/IP 為核心（面向連接）、以覆蓋網絡為改良（面向內容）的架構設計，已經難以滿足以人工智能、元宇宙等為代表的計算密集型應用服務的資源需求.基于此，以算為中心、網為根基的新型網絡范式（面向計算）算力網絡應運而生，旨在當前網絡功能與技術的基礎上，進一步整合云計算、邊緣計算和泛在智能設備的異構計算資源，提供更高效的網絡化計算、儲存和傳輸服務.然而，由于異構網絡節點在設備配置、網絡環境、地理位置等方面存在較大差異，系統難以突破瓶頸節點的性能約束，導致網絡整體資源利用率較低、服務質量得不到提高.因此，如何靈活高效地分配和調度碎片化的異構資源①異構資源指不同設備的計算資源（CPU、GPU 算力資源）和傳輸資源（帶寬容量）.，成為了當前算力網絡研究的關鍵挑戰[1].

為克服這類挑戰，網絡研究者提出了許多面向異構環境的多維資源優化方案[1-13].例如，文獻[2]提出一種名為邊緣矩陣（EdgeMatrix）的云邊協同異構資源優化框架，利用網絡化多智能體強化學習技術適配系統中不同任務的資源組合，從而在最大化網絡吞吐量基礎上保證不同優先級任務的可靠完成.云邊協同架構的雖然能夠滿足部分用戶的服務需求，但面對大規模用戶場景依然存在資源緊缺和成本較高的問題.例如，騰訊云服務供應商專用計算設備的單臺租賃費用約為18.04 元/小時②https://buy.cloud.tencent.com/price/cvm/calculator（GN10X.2XLARG40）.

隨著軟硬件技術革新，廣泛普及的移動智能終端和家庭主機性能得到顯著增強，許多研究者提議將海量設備資源進行整合利用，設計面向眾包概念的終端協同計算范式[3-9]，用以解決資源受限和運營成本高的問題.其中，Zhang 等人[3]提出一種適用于大規模直播服務的眾包資源協同框架，通過將部分視頻轉碼任務卸載到觀看者終端設備，降低直播服務供應商的實時轉碼資源成本.Nagesh 等人[4]針對遠程云計算延時不可控、高成本等問題，介紹了一種基于工作竊取算法的移動群計算（crowd computing）框架，該方法根據移動終端對任務的依賴性和設備性能來優化資源分配策略，從而有效降低計算密集型任務處理時間和資源消耗.此外，群計算憑借其成本低、資源基數大等特性，在工業互聯網[5]、元宇宙[6]、智慧城市[7]、車聯網[8]和智能醫療[9]等領域也得到研究和應用.

可以預見，通過整合穩定高效的云服務器、低延時的邊緣服務器和低成本的用戶終端設備，云邊端混合的分布式協同計算模式被認為是未來算力網絡所設想的可能場景之一，近年來得到了研究關注[7-10]，例如，文獻[10]就針對當前計算下沉、邊緣智能模型泛在部署所帶來的安全性和可靠性問題，提出了面向云邊端全場景的深度學習模型對抗攻擊和防御方法.文獻[11]針對用戶隱私問題，設計了一種面向云邊端異構場景的分層聯邦學習方法.在先前的研究中，相關研究者也提出一些面向云邊端協同的多維資源聯合優化方案[12-13].文獻[12]中設計了一種廣義虛擬隊列來統一表征網絡節點的計算和傳輸任務負載，并通過隊列擁塞程度優化不同網絡節點的任務分配.文獻[13]進一步引入了一種圖模型，該模型通過在系統網絡拓撲上構建多層虛擬網絡結構，從而將計算和傳輸的聯合優化問題轉化為圖模型中的路由問題.

雖然文獻[1?13]方案為算力網絡的異構資源優化提供了思路，但都僅針對特定應用服務而設計專用資源優化方案，其在通用應用上的服務質量、大規模部署和協同并發等方面依然存在較大局限，難以適用于復雜算力網絡環境的異構資源優化問題.我們認為解決該問題首要任務是構建一套面向“云—邊—端”算力網絡的系統性解決方案，在應用服務需求感知、異構網絡狀態認知和異構資源聯合優化實現突破.基于此，本文提出了一種面向“云—邊—端”算力網絡的計算和傳輸資源聯合優化方法，主要研究內容和貢獻有4 個方面：

1）介紹了“云—邊—端”算力系統的異構網絡模型，并基于網絡服務功能鏈[14-15]，構建了一種廣義圖結構的通用應用服務模型，該模型能夠促進服務任務的并發部署.

2）根據分布式算力網絡的隨機特征，設計了量化網絡節點計算和傳輸負載的隊列表征方法.

3）為降低大規模算力網絡部署的復雜度，探究了該通用應用服務在算力網絡中的部署方式，提出了一種多維資源融合的增廣圖模型，該模型能夠將異構資源協同優化問題表征為面向增廣圖結構的路由問題，進而將該問題形式化為隨機優化問題.

4）為了實際解決該問題，本方案根據波利亞重球法[16-17]（Polyak heavy-ball method），提出了一種異構資源協同優化算法，并研究了算法復雜度和其在實際部署環境下的可行性.進而給出了該算法在隊列長度上界、最優性和收斂性方面性能的理論分析；通過數值仿真和原型系統實驗，驗證了所提方法與同期相關解決方案相比在資源消耗和服務質量方面具有優勢.此外，本文所提出增廣圖模型為算力網絡異構資源協同優化的分析提供了新途徑.

1 相關工作

1.1 多資源協同優化

對于資源協調優化，文獻[18]為了解決云計算的成本問題，提出一種終端設備協同的混合云計算范式，通過將計算任務卸載到穩定的終端用戶，并利用排隊理論來評估終端設備的平均響應時間，該方法目標是在最小化延時的同時盡可能節約計算資源成本.另外，許多學者考慮了虛擬化和層次化的方法.如文獻[19]提出了一種基于多維資源融合化的網絡虛擬化架構，將多方、異構的資源有機整合成統一資源平面，在此基礎上根據用戶需求進行資源切割與虛擬化，可以有效利用資源并降低運營成本.文獻[20]中提出了一種雙層任務卸載和資源調度方法，上層用基于貪心的流水車間調度算法處理任務卸載決策和卸載調度問題，下層采用深度強化學習技術優化服務器資源分配問題.

由于網絡和用戶需求等所呈現的動態特性，動態方法和優先級被引入以更好的解決資源約束的問題.文獻[21]考慮了用戶服務需求、網絡環境、計算資源的動態變化問題，通過深度時空殘差網絡預測用戶服務需求，邊緣服務器協助全局系統進行全局網絡參數的更新，全局網絡將更新后的參數傳回本地網絡，由于邊緣服務器僅負責本地服務卸載決策，該方法能適應大規模環境.劉曉宇等人[22]提出了一種基于深度強化學習的動態優先級并發接入算法，針對工業網絡有限的時頻網絡難以支持大規模分布式高并發任務卸載的問題，首先為異構設備分配了不同的服務優先級，考慮在動態優先級和并發環境下的多目標決策問題，并利用強化學習技術實現效用優化.

此外，一些學者從架構的角度思考新的優化方法.文獻[23]提出了一種去中心化的在線任務調度與資源分配方法，任務調度與資源分配均在邊緣服務器、各個邊緣節點以異步的方式與周圍節點進行通信，避免了中心化架構在單點故障、高并發調度效率低和高時延等方面的問題，該方法還考慮了任務多樣性和優先級屬性，以加權任務卸載響應時間為優化目標，實現了優秀的任務調度和系統資源分配方案.文獻[24]提出了一種面向密集型實時內容分發場景的“計算—緩存—通信”聯合控制方案，在算力和傳輸的基礎上引入了緩存機制，有效降低了任務處理時延.文獻[25]提出了一種用于元宇宙應用管理和資源分配的元切片框架，它將應用程序分解為多個函數，并將不同的函數分配到合適的資源架構層，實現處理效率提升.同時該方案還將具有公共功能的程序放到一個元實例中，實現多個應用程序的共享，從而節省系統資源成本.

1.2 算力網絡相關研究

在數字經濟背景下的萬物互聯時代，大數據、人工智能等技術創新，加速了數字經濟的發展，同時也帶來了海量數據以及更嚴苛的任務處理要求.為了應對數據傳輸和算力的新時代要求，算力網絡（computing first network，CFN）應運而生.算力網絡根據業務需要，在云、邊、端等異構算力設備之間進行任務分配和資源調度，以滿足不同節點的算力服務需要，同時最大限度地提高資源利用效率.

目前算力網絡發展方興未艾，對算力網絡的研究還處于探索階段.文獻[26]提出了一種計算與網絡資源聯合優化方案，設計并構建了算力網絡管理編排平臺，通過分布式路由協議分發資源信息，通過算力網絡管理編排平臺集中調度網絡資源、計算資源等.劉澤寧等人[27]提出了一個云霧混合多層次算力網絡及計算卸載系統，系統定義了一個由時延、能耗及付費組成的加權代價函數，通過引入博弈論方法實現多用戶的任務調度優化.李銘軒等人[28]采用基于“Kubernetes+K3S”兩級聯動的架構來實現統一的邊緣側資源調度管理，實現了異構嵌入式計算資源的協同管理.算力網絡可編程基于對算網資源狀態的實時感知，將流量調度到合適的節點，以實現最大效能.文獻[29]探討了算力網絡可編程服務中集中式、分布式、混合式3 種路由策略的設計方案.

計算密集、實時性要求催生了對確定性算力網絡的需求.文獻[30]對確定性算力網絡進行了研究，并設計了技術架構與工作機制.文獻[31]對確定性網絡的標準化和現狀進行了研究，并對算力匹配調度進行了分析.綜上所述，算力網絡的資源協同優化需要考慮通用化、大規模部署、協同并發和虛擬化等需求.既能實現應用的通用化，又能適應大規模場景應用的需要；既能實現數據處理和傳輸的并行可靠，又能分離硬件和軟件綁定，建立邏輯關系，從而實現靈活的資源調度.現有方法僅能解決部分問題，具有局限性.本文提出的面向“云—邊—端”異構算力網絡的計算和傳輸聯合優化方法，在應用服務需求感知、異構網絡狀態認知和異構資源聯合優化3方面提出解決思路，希望提出一套兼顧上述4 個方面需求的系統性解決方案.

2 系統模型

在本節中，首先介紹了異構算力網絡模型，并展示了面向通用應用的服務模型和面向資源負載的隊列模型，最后給出了多維資源融合的增廣圖模型.表1 列出了本文中使用的數學符號及其定義.

2.1 異構算力網絡模型

圖1 給出了異構網絡系統示意圖.我們將異構算力網絡系統的拓撲結構表征為無向圖模型G=(V,E)，其中，包含網絡節點和鏈路的集合，將其分別表示為定義系統中的網絡節點包括3 種角色：1）服務提供者，即提供應用服務的源節點，能夠持續提供應用服務并且具備計算能力；2）網絡轉發者，負責異構網絡數據傳輸的中間轉發節點，能夠為網絡數據流提供計算服務；3）內容消費者，對特定服務提供者發送請求的用戶節點，能夠為算力網絡系統提供空閑的計算資源.文本分別定義服務提供者集合、網絡轉發者集合和內容消費者集合為Vp,Vt,Vc∈V.假設系統運行在離散系統中，劃分為時隙集合T={1,2,…,T}.在異構算力網絡系統中，我們認為每個網絡節點都具備提供計算和鏈路的轉發能力，由于網絡節點在運行過程中可能會受其它應用程序的影響，因此將節點在時刻t的可用計算資源表示為時變隨機變量，其中表示節點v所能提供的最大計算能力.將節點v1到節點v2的鏈路定義為其中v1,v2∈V.同理，當有數據流經過網絡鏈路時將消耗鏈路的帶寬資源，由于鏈路會受到外部環境因素和其它應用交叉流量等的影響，設置鏈路可用為時變變量ce(t)∈其中表示鏈路e的最大可用帶寬資源.

Table 1 Mathematical Symbols and Their Definitions表1 數學符號及其定義

Fig.1 Illustration of heterogeneous network system.圖1 異構網絡系統概述圖

對于異構算力網絡環境中不同網絡節點和鏈路的資源開銷代價存在差距，例如，云服務器和邊緣服務器等專用服務器租用費一般會高于用戶自愿提供的空閑算力成本.因此，定義網絡節點v計算資源的成本權重為wv，同理，定義網絡鏈路其中v1,v2∈V，帶寬資源的成本權重為we.

2.2 通用應用服務模型

圖2 展示了網絡服務功能鏈模型和通用應用服務模型的對比示意圖.網絡功能由于其自身服務特性表征為鏈狀模型（一組具有先后順序網絡功能實例），在該鏈狀結構下，數據流通常需要依次通過不同網絡服務功能進行順序處理，最終才能到達目的端.但算力網絡的通用應用服務還包括在工業互聯網、元宇宙、無人駕駛等新場景下的應用服務，因此考慮對鏈狀模型進行改進.例如，圖2 展示了元宇宙場景的虛擬數字人生成任務，該任務可拆分為語音生成和視頻生成2 個子任務，如果網絡節點可以提供完成任務的計算資源，則可將子任務卸載到不同網絡節點完成，并通過不同網絡路徑傳輸到目的節點.另外，單個子任務也能被進一步拆分，并交付給多個網絡節點協同完成，從而提高算力網絡的協同并發能力.

基于此分析，本文定義通用服務集合B={b1,b2,…,bi,…}，其中bi表示第i種數據流服務.并且將通用應用服務模型表示為有向圖結構D=(F,L)，其中將通用服務功能作為有向圖的節點，定義節點集合為有向邊集合為數據流需要從源點s出發經過通用服務功能fi∈F并最終到達終點t，其中數據流向必須遵循 L中的有向邊方向，并且有向圖 D所有節點必須有對應的數據流經過.因此，根據通用應用服務模型，有向圖 D可以抽象成多條由s到t的有向路，定義該向路集合為此外，由于不同網絡功能服務所消耗的計算資源存在差異，規定完成服務功能fi∈F任務的單位計算資源消耗為；同時數據流經過服務功能處理后，所需傳輸的數據量可能發生變化，因此定義有向鏈路li∈L的單位帶寬資源開銷為

Fig.2 Diagram of network service function chain model and general application service model.圖2 網絡服務功能鏈模型和通用應用服務模型圖

2.3 面向資源負載的隊列模型

對于離散時間系統，網絡節點的計算和傳輸負載通常被建模為虛擬隊列模型[32]，虛擬隊列堆積越嚴重表示節點資源負載越高.圖3 展示了單個網絡節點中計算和傳輸的雙虛擬隊列結構.

我們希望在盡可能完成計算和傳輸任務的同時避免隊列堆積并保持隊列長度的穩定.隊列大量堆積會導致任務長時間處于等待狀態，從而影響服務質量.根據文獻[32]，給出隊列的強穩定性條件.

定義1.均值穩定性.t∈{0,1,2,…}q(t)

對于任意隊列離散時間下的，如果：

在平穩狀態下隊列長度的均值是有限的，則稱隊列q(t)是均值穩定的.

2.4 多維資源融合的增廣圖模型

根據隊列模型，異構算力網絡場景中每個網絡節點的計算和傳輸負載可以顯式地表征為隊列堆積.這種隊列模型能夠很好地反映網絡局部（如單個網絡節點）的多資源負載情況，但是無法反映網絡的整體態勢情況.因此，為降低大規模算力網絡環境中計算和傳輸負載的表征復雜度，提出多維資源融合的增廣圖模型.該模型在網絡系統的物理拓撲上，為每個節點額外增加了一個虛擬的計算節點，具體如圖4所示.定義虛擬計算節點集合需要注意，由于虛擬計算節點和物理網絡節點是一一對應的，因此虛擬計算節點與網絡節點數相同，均為|V|.并且根據2.1節定義，節點v所對應的虛擬計算節點u在時刻t的處理容量為隨機變量其中表示節點v所能提供的最大計算能力.后續為了表示方便，將符號改寫為

圖4 中給出了異構算力網絡場景下增廣圖模型的具體示例，圖4 中綠色曲線表示一條從服務提供者v10流向內容消費者v0的數據流，該數據流依次經過增廣圖節點v10→v8→u8→u6→u5→v5→v4→v2→v0.由于數據流經過虛擬節點ui時必然經過vi，所以可以簡化表示為序列：v10→u8→u6→u5→v4→v2→v0.數據流在增廣圖模型中的節點序列，揭示了算力網絡系統哪些節點為該服務提供了計算和傳輸服務支持，其中物理節點v8，v6，v5，v4和v2參與了數據轉發，物理節點v8，v6和v5提供計算支持.此外，任何傳輸和計算分配方案，都可以通過在增廣圖模型的一條或多條由源點v10到終點v0的路徑序列表示.借助該模型，能夠將算力網絡環境下計算和傳輸的聯合分配問題轉化為增廣圖模型中的“路由”選擇問題.

Fig.3 Dual virtual queue structure for computation and transmission.圖3 計算和傳輸的雙虛擬隊列結構

Fig.4 Generalized graph model under heterogeneous computing first network scenario.圖4 異構算力網絡場景下的增廣圖模型

3 問題的形式化表征

在給出問題形式化表征之前，本文先討論增廣圖模型視角下的隊列模型系統.如圖4 所示，對于增廣圖模型中的每條鏈路，由于鏈路會受帶寬限制，每條鏈路都應對應一個傳輸隊列，隊列處理能力為鏈路帶寬容量.另外，增廣圖中的虛擬節點u具備計算能力，算力容量為每個虛擬節點u上存在一個計算隊列.

本文的目標是在滿足內容消費者服務需求的前提條件下，尋找異構網絡系統最高效的計算和傳輸資源協同方案.首先，考慮算力網絡的傳輸資源成本，根據異構算力網絡模型，鏈路e，?e∈E的帶寬資源的成本權重為we.設經過鏈路e的所有數據流集合為B(e).對于?I∈F(e)，數據流I在時刻t所需要的帶寬資源為we·sI(t)，其中sI(t)表示數據流I在時刻t到達鏈路e的速率.因此，鏈路e的總帶寬資源需求表示為：

由于s和m具有相似的形式化表征，使用x來統一表示{s,m}.進而，系統的整體資源需求量為：

式（6）表示網絡系統的總資源消耗為所有節點和鏈路的計算和傳輸資源消耗總和.隨后，討論尋找異構網絡系統最高效的計算和傳輸資源協同方案，定義服務數據流的效用函數為U(·)，可選的效用函數形式包括：二次多項式和對數式等，一般具有凸性和二次連續可微性.因此.將該問題可建模為具有線性約束和凸目標函數的多數據流問題：

其中 α為效用和資源消耗間的權重因子.式（7-1）右邊max（）里面第1 項為系統整體效用，第2 項為系統整體資源消耗；式（7-2）和（7-3）分別表示傳輸資源和計算資源的容量約束條件；式（7-4）表示不同數據流I傳輸速率的最大值約束條件，xmax為服務流的最大傳輸速率.

式（7-2）和式（7-3）的2 個約束條件與隊列模型的穩定性條件存在關系.對于任意鏈路e，ce(t)為鏈路的處理能力，在傳輸隊列模型中表示出隊速度s?(t)；wexI(t)則表示鏈路處理數據流傳輸任務所需的帶寬資源，在傳輸隊列模型中表示入隊速度s+(t).隊列可以更新為：

若所采取的傳輸策略能夠保證約束條件在較長時間內滿足條件，則從時刻t=0 累加式（8）有：

根據條件（7-2）和q′(0)=0（假設初始隊列堆積為0），將式（9）兩邊取期望并從t=0 累加可達到的條件：

即為定義1 所給出的隊列均值穩定條件.同理可以證明若計算策略滿足約束條件（7-3），虛擬計算隊列q(t)也具有均值穩定性.

4 異構資源的協同優化算法設計

本節首先簡單介紹了波利亞重球法；隨后，基于該方法設計了用于求解問題（7-1）～（7-4）的資源聯合優化算法；最后，本節還給出了所提算法在隊列長度上界、最優性和收斂性等方面的理論性能.

4.1 Polyak Heavy-Ball 梯度下降法

波利亞重球法是一種用于求解無約束最小值問題，例如minf（x）的梯度下降算法，該方法求得最優值的條件要求所求函數式為二次連續可微的凸函數.由于波利亞重球法在收斂速度和最優性方面存在優勢，本文選用該方法進行算法設計.另外，波利亞重球法結合隨機優化中的隊列理論后，在隊列堆積上相較于傳統梯度下降法具有明顯優勢，相比于人工智能神經網絡理論，該方法在求解一些簡單優化問題時，也能夠快速準確地找到最優解.在介紹該方法前，先回顧一般形式的梯度下降算法，迭代式為：

其中 λt為時刻t的迭代步長，?f(xt)為xt的梯度值.波利亞重球的迭代式為：

其中，βt∈[0,1)為動量的權重值.為相比一般形式的梯度下降算法，波利亞重球法增加βt(xt?xt?1)項，該項為前一個時隙x的一階變化，通常被稱為 βt參數化的一階記憶（或稱為“動量”）.相比之下，傳統梯度下降算法中的值更新是零階記憶的，即梯度更新僅依賴前一個時隙的梯度值.

問題（7-1）～（7-4）為具有線性約束條件的優化問題，因此需要對該問題進行重構得到無約束形式，可使用拉格朗日乘子法，將線性約束條件轉化為懲罰項.當轉化為無約束問題，則可以嘗試使用波利亞重球法進行求解.定義輔助變量θ，構造目標（7-1）～（7-4）的max-drift-minus-penalty 表達式為：

其中，V是非負均衡因子，用于平衡效用項和懲罰項的權重因子.式（13）是關于變量x和θ={θe,θu}的函數，因此將該式（13）簡記為maxg(x,θ).我們的目標是在滿足內容消費者服務需求的前提條件下，尋找異構網絡系統最高效的計算和傳輸資源協同方案，即尋找最優數據發送速率x.g(x,θ)是原問題U()的對偶問題，因此可以先確定θ，再根據 θ和g(x,θ)形式求得最優解x.給出 θ梯度下降的迭代形式為：

其中?g(xt,θ)/?θ為g(xt,θ)關于 θ的偏導數.實際上?g(xt,θ)/?θ ∝wx(t)?c(t)，其中wx(t)為時刻t隊列增加量，c(t)為時刻t隊列減少量，在一般形式下 θ的一次迭代過程可以建模成隊列的變化過程：

進一步可以給出波利亞重球法的迭代更新式：

其中q?(t)=λtq(t).

4.2 基于Polyak Heavy-Ball 的資源優化算法

給出一種基于波利亞重球法的資源優化算法，來實現對異構算力網絡系統的計算和傳輸聯合優化.具體的算法步驟如算法1 所示.

算法1.基于Polyak Heavy-Ball 的資源優化算法.

初始化：

算法1 先初始化設置所有節點和鏈路隊列長度值q(t)=q′(t)=0和波利亞重球法參數θ0=θ?1=0.需要注意，所有節點中的隊列值和 θ具有一一對應關系，也就是一個隊列q對應于一個 θ參數.根據式（14），θ的更新與q?(t)=λtq(t)相關，后續在描述隊列更新時統一使用q?(t).此外算法的重要參數還包括V和 βt，這些參數會影響算法的隊列堆積、算法最優性和算法收斂速度，在算法分析部分會重點討論.

算法1 主循環包括3 部分：1）內容消費者選擇傳輸路徑；2）服務提供者確定發送速率；3）網絡所有節點確定計算處理速率；任意內容消費者它們首先需要確定交付路徑數量根據通用應用服務的有向圖模型，從到達候選服務提供者的路徑中選擇最合適的網絡路徑來獲取服務或數據流.由于每條鏈路和節點負載由虛擬隊列q?(t)和 θ參數決定，因此路徑上所有節點和鏈路的 θ值加和可以作為路徑選擇的依據.因為 θ累加和表示了路徑上隊列的總堆積情況，因此算法的規則是盡可能選擇堆積量較小的路徑傳輸數據，也就是 θ累加和較小的路徑.當內容消費者確定路徑并向服務提供者發送請求后，服務提供者需要根據內容消費者網絡狀態動態調整數據發送速率，從而避免傳輸擁塞等問題.數據流發送速率x由式（18）確定.隨后，由于網絡節點還需要對服務進行計算處理，每個網絡節點要根據自身的可用計算資源情況，調整計算隊列的入隊速度m+(t)，該部分處理速率m+(t)由式（19）計算得到.此外，網絡節點還需要更新自身虛擬隊列值q?(t)和 θ參數.

4.3 算法復雜度與性能分析

算法1 包含的三大部分復雜度分析：1）內容消費者選擇傳輸路徑需要消費者在網絡中尋找最優傳輸路徑，可以看成是網絡中的單源最短路徑算法，以Dijkstra 經典算法[33]為子算法，則該部分的時間復雜度為O(V3)，空間復雜度為O(V4)；2）服務提供者確定發送速率需要計算式（19），由于式（19）的復雜度為O(1)，因此第2 部分每個服務提供者的時間復雜度為O(V)；3）網絡所有節點確定每一條經過的數據流的計算處理速率，由于這部分和第2 部分相似，確定入隊速率m+(t)的時間復雜度為O(B)，同時由于隊列更新過程需要存儲 θt，θt?1，?q?(t)等信息，空間復雜度也為O(B).

定理1.隊列堆積與隊列穩定性

算法1 在穩定狀態條件下總隊列長度與均衡因子V滿足關系：

定理2.效用最優性

對于給定V條件下算法1 輸出的穩態均值結果x∞和最優值x?之間滿足條件和x?分別對應的效用滿足不等式因此，x∞收斂到x?的性能隨著V增長漸進增加.

定理3.算法收斂性

對于給定V∈(Φ/4,∞]和 β ∈[{Φ/2K?1}+,1)，有E{x(t)|θ(t)}滿足線性收斂，并有系數RV,β滿足：

其中，?和 Φ是2 個常數滿足? ≤?U′′(x)≤Φ.定理1，2，3 的證明可以在文獻[17]中找到.

5 實驗設置與性能評估

本節首先介紹實驗場景和參數設置；隨后，為驗證算法的理論性能，給出了數值仿真結果；最后，在一個小型原型系統環境，證明了所提方法在服務效用和資源消耗方面優于目前先進解決方案[2,12,18].

5.1 實驗場景與參數設置

為驗證算法理論性能，首先設置了數值仿真實驗，通過INET①https://inet.omnetpp.org/工具生成一個包括1 010 個網絡節點的異構網絡拓撲.按照節點的連接度設置3 類不同的網絡節點，包括服務提供者、網絡轉發者和內容消費者，其中連接度最高的10 個節點設置為服務提供者，連接度低于服務提供者、高于內容消費者，設置500個網絡轉發者節點，連接度最小的500 個網絡節點設置為內容消費者.網絡中的節點間鏈路帶寬被設置為10～20Mbps 之間的隨機值，并且每條鏈路可用帶寬會動態變化，用于模擬時變的網絡環境.設置不同服務提供者的內容服務各不相同，因此共有10 個不同服務B={b1,b2,…,b10}.并且對于不同的服務bi設置對應的通用應用的有向圖模型 Di.內容消費者會對不同服務隨機產生興趣，該興趣產生過程服從泊松分布.當內容消費者對某個服務產生興趣后，需要等到服務結束后，才會對新的服務產生興趣.設置總仿真時間為T=106；設置計算資源成本權重為帶寬資源的3 倍即，wu=3we；設置效用函數和資源成本的權重因子α=1.此外V和 β對算法理論性能具有較大影響，因此數值仿真測試了不同V和 β條件下隊列堆積q?(t)、θ參數、效用值和資源成本的變化情況.

為證明所提方法的實用性能，本文搭建了一個小型原型系統，對比測試了3 種不同的多資源優化策略.后續在5.3 節中將給出更多原型系統的設置細節，在原型系統中部署了一個通用服務，該服務能夠提供虛擬人直播服務，用戶可以通過上傳文本信息，實現實時的虛擬人音視頻生成.

5.2 數值仿真結果

圖5 展示了在不同V（100，200，300，400 和500）和 β（0 和0.9）條件下隊列長度隨時隙的變化情況.可以看到隊列長度q?(t)隨著V增加而增長，其中當β=0時，隊列長度q?(t)隨著V線性增加；當V=100時，q?(t)為10 左右；當V增加至500 時，q?(t)穩定時的取值為50 左右.對比相同V條件下β=0.9的情況，隊列長度明顯有所減少，其中V=500時，隊列長度q?(t)穩定值在5～6.滿足定理1所表明的量級隊列堆積性能.

Fig.5 Changes of queue length with time slot under different V and β.圖5 不同V 和 β條件下隊列長度隨時隙變化

圖6 揭示了當V=500 時，不同 β條件下隊列長度q?(t)隨時間的變化情況，可以看到隨著 β增加，隊列長度q?(t)呈現逐漸減少趨勢.當 β取值為0，0.5，0.8，0.9和0.95時，隊列長度q?(t)在穩定時的值分別為50，25，11，6 和4.根據 定理1，有等式q?(t)=O((1?β)V)+當V=500 可以計算理論上q?(t)的取值大約為52，28，14，8 和6.理論結果和實際數值結果基本吻合.綜上所述，圖5 和圖6 驗證了所提算法定理1的正確性.

Fig.6 Changes of queue length with time slot under different β.圖6 不同 β條件下隊列長度隨時隙變化

圖7 給出了不同V和 β條件下，θ隨時隙變化的趨勢.不同于隊列長度q?(t)，穩定時的 θ值與參數 β值沒有關系，可以從V=100 和V=500 時，θ收斂時的值得出該結論.β參數僅影響 θ的波動情況，可以看到伴隨著 β參數的增加，θ的波動會變得愈發劇烈.V的取值會影響 θ的穩態值，當V=500，時 θ穩態值大約為50；當V=100 時，θ穩態值大約為10.

Fig.7 Changes of θ with time slot under different V and β.圖7 不同V 和 β條件下θ 隨時隙變化

如圖8 所示，當V=100 時，取不同 β值時，服務提供者的發送速率x（t）隨時間的變化情況.根據實驗環境設置，網絡中鏈路帶寬設置為10～20 Mbps 隨機數，瓶頸帶寬值約為10 Mbps.可以看到算法收斂時的穩態值大約為10 Mbps，并且伴隨一定的波動.雖然，通過之前的數值實驗發現，增加 β值能夠有效減少隊列長度q?(t)，但是增加 β值會影響x（t）收斂性能，可以看到 β值越大收斂速度越慢.此外由于 β值不會影響收斂后的穩態值，因此該實驗從一定程度驗證了定理2 的正確性，即 β的取值并不會影響算法的最優性.

Fig.8 Changes of sending rate x(t) with time slot.圖8 發送速率x(t)隨時隙的變化

圖9 給出了當V=100 時，系統總效用 U在不同β值條件下隨時間變化趨勢圖，由于效用和發送速率正相關，因此總效用曲線和發送具有相似的趨勢，該實驗是對算法效用最優性的補充實驗.可以看到當β取不同的值時，算法收斂后的穩態值是相同的，這證明了算法最優性和 β的取值無關，但當 β趨近于1 時，算法收斂值在穩態值附近的波動范圍不一樣，當 β取較大值時，算法收斂后效用值的波動幅度較大.

Fig.9 Changes of total utility U with time slot.圖9 系統總效用 U隨時隙的變化

圖10 展示了不同V值條件下，發送速率x（t）隨時間的變化情況，根據定理2 可知，算法最優性受V的取值影響，當V值越大時，算法穩態時的取值越接近最優值.藍色曲線表示當V=100 時的變化趨勢，可以看到該曲線收斂到最優值所用的迭代輪次最少，并且在達到穩定狀態之后上下波動的幅度較小.黑色曲線表示V=500 時的變化情況，相比于藍色曲線，黑色曲線在到達穩定狀態所需要的時間更長，并且在穩定狀態條件下黑色曲線的波動范圍更小.但是不同V值條件的曲線都存在一定的抖動，并且相互之間差別并不算很大，因此V對算法收斂性以及最優性的影響并不大.通過上面分析，考慮在原型系統實驗中將所提算法的參數設置為V=100 和β=0.9.

Fig.10 Changes of sending rate x(t) with time slot under different V.圖10 不同V 條件下發送速率x(t)隨時隙的變化圖

5.3 原型系統結果

本節首先介紹了原型系統的搭建細節，隨后對比了所提方法與3 種主流方案（文獻[2]、文獻[12]和文獻[18]）在服務質量、資源消耗等方面的性能對比情況.

1）EdgeMatrix[2].采用網絡化多智能體Actor-Critic算法，該方案將物理資源重新定義為邏輯隔離的資源單元.通過聚類算法將具有相似特征的資源分組為不同的資源集合，以資源集合對外提供服務從而保證不同優先級服務質量，解決了邊緣云集群之間的聯合服務編排和請求調度問題.

2）AGO[12].采用多隊列系統和Nesterov’s 加速梯度下降算法，該方法提議綜合利用了云計算、邊緣計算和終端設備的計算資源，構建計算和傳輸2 個虛擬隊列系統，并通過隊列堆積情況給不同設備分配計算任務，同時根據傳輸隊列擁塞情況調節發送速率.

3）Cloud-Crowd[18].該方法利用李雅普諾夫優化技術，設計了一種請求分配的在線決策算法，該算法主要在云計算設備和終端設備之間分配計算任務，未能有效利用網絡中間轉發者的計算資源.

如圖11 所示，原型系統多臺異構設備，包括1 臺高性能服務器（Intel Xeon CPU/256 GB 2*RTX1080 12 GB）、3 臺臺式工作站（AMD Ryzen5/16 GB RTX3080 12 GB）和1 臺筆記本電腦（AMD Ryzen9/32GB RTX3080 16 GB）.該系統的主要代碼見源庫①https://github.com/uglyghost/MultNodeVirtualLive，虛擬人生成的核心代碼基于百度飛槳PaddleBoBo②https://github.com/uglyghost/PaddleBoBo.

Fig.11 Schematic of the topology of the prototype system圖11 原型系統拓撲示意圖

設置高性能服務器為系統的服務提供者，工作站為網絡轉發者，筆記本電腦為內容消費者.內容消費者通過給服務提供者發送請求獲取生成的虛擬視頻，請求內容為文本數據.內容服務器在3 臺工作站的協助下完成視頻生成任務，并將數據內容推送給內容消費者.為實現多臺主機的實時協作，系統使用Flask 搭建視頻生成服務器.通過SRS 工具搭建基于動態自適應碼率的協同流媒體服務集群③https://ossrs.net/lts/zh-cn/docs/v4/doc/sample-hls-cluster，其中高性能服務器配置為推流的源站，臺式工作站作為邊緣服務器，筆記本電腦設置為用戶個人設備.

為模擬異構算力網絡系統中云服務器、邊緣服務器和用戶個人設備，本文選用了3 種不同的設備.圖12 展示了原型系統中不同設備在生成虛擬視頻方面的性能.藍色虛線是高性能服務器（Server）生成視頻長度和運行時間關系，可以看到在服務器上生成30 s 虛擬視頻大概需要110 s，每秒可生成視頻長度為0.272.紅色虛線、綠色虛線和黃色帶標記實現分別表示3 臺臺式工作站（WorkStation，WS）的性能曲線，3 臺工作站配置相似，因此也具有相似的生成性能.生成30 s 虛擬視頻大概需要120～140 s，每秒生成視頻長度為0.230.對比所有設備，筆記本電腦（Laptop）性能較差，生成30 s 視頻大概需要170 s 運行時間，每秒生成視頻長度為0.176.設備在虛擬視頻生成方面性能存在較大差異，能夠模擬簡單的異構算力網絡場景.整合所有設備資源，每秒最多可生成視頻長度為1.138，大于1，理論上可生成連續不卡頓的虛擬視頻內容.考慮不同設備的資源成本，設置高性能云服務器的單位計算資源，成本權重為3，臺式工作站為2，筆記本電腦為1.

Fig.12 Comparison of video generation duration for different devices.圖12 不同設備視頻生成時間的對比

圖13 和圖14 分別給出了數據發送速率x(t)和系統總效用U在理論值和原型系統測試中的對比情況.在數據發送速率x(t)方面，深紅色實曲線展示了理論發送速率隨算法迭代的變化情況，淺藍色實線則表示原型系統測試中的算法迭代結果.可以看出，深紅色實線具有更穩定的實驗結果，能夠更快收斂到穩態值，并在穩態值附近波動，其波動振幅相較于淺藍色實線更小，實際測試環境的外界環境影響具有高度不確定性，算法更難收斂，而淺藍色實線在整個迭代過程中一直處于上下震蕩的情況.淺紅色虛線和亮藍色虛線分別表示理論值和原型測試結果的累計均值曲線，在累計均值結果上，理論結果一直優于測試結果并且相差不大，隨著時間推移，測試值逐漸逼近理論值.上述結果證明所提方法在原型系統環境，數據發送速率x(t)具有穩健性.在系統總效用U方面，圖14 深紅色實曲線展示了總效用U隨算法迭代的變化情況，淺藍色實線則表示原型系統測試中的算法迭代結果，淺紅色虛線和亮藍色虛線分別表示理論值和原型測試結果的累計均值曲線.總效用對比結果與數據發送速率x(t)結果類似，可以看到，算法在原型系統的迭代過程中具有較大振幅，但累計均值結果逐漸趨于穩定并逼近理論值.因此，系統總效用U在原型系統環境中具有穩健性.

Fig.13 Comparison of theory and prototype experimental results in data transmission rate x(t).圖13 數據發送速率x(t)的理論與原型實驗結果對比

Fig.14 Comparison of theory and prototype experimental results in the total utility U.圖14 系統總效用U 的理論與原型實驗結果對比

圖15 展示了4 種不同方法中高性能服務器、3臺臺式工作站和筆記本電腦的工作負載對比.對比4種方法，我們所提的Heavy-Ball 方法在不同設備的工作分配最均勻，而其它3 種方法的任務分配會導致高性能服務器和筆記本電腦的負載過大，導致異構設備復雜分配不均的主要原因是算法在動態系統中收斂速度慢.其中Cloud-Crowd 在調整分配方案過程中，算法迭代到最優分配策略的速度較慢，因此就容易導致異構設備工作負載的增加.Heavy-Ball 的動量概念算法，分配過程中不僅能夠觀測當前各設備負載情況，還會考慮工作負載的變化速率，從而預測未來趨勢，因此在不同設備計算任務分配中，Heavy-Ball 相較于其它3 種方法具有一定優勢.

Fig.15 Comparison of workload for heterogeneous devices under four different solutions.圖15 4 種不同方法中異構設備的負載對比

圖16 給出了4 種解決方案在平均下載時間、卡頓時間、平均視頻碼率和資源消耗方面的性能對比.由于視頻內容分塊傳輸，一般設置視頻塊播放時長為2 s，下載時間表示下載2 s 視頻塊所用時間；卡頓時間是指虛擬視頻在實時生成過程中由于資源約束等問題，未按預期完成視頻生成任務而導致的卡頓時間占總生成視頻時間的比例；平均碼率代表用戶接收視頻內容的分辨率清晰度；資源消耗表示在整個視頻生成過程中，按照資源成本權重3∶2∶1 設置，每秒系統的平均資源消耗.可以看到Heavy-Ball 具有較低的平均下載時間、卡頓時間占比和資源總消耗、較高的視頻碼率.

Fig.16 Comparison of four metrics in four different solutions.圖16 4 種解決方案的4 個性能指標對比

根據圖15 實驗分析，Cloud-Crowd 方法會導致筆記本電腦和高性能服務器工作負載過高的問題，難以協調具有高度異構性的設備資源.此外，在卡頓時間方面，AGO 取得最好性能，Heavy-Ball 相比AGO 性能相當.4 種不同方法所生成虛擬人視頻經過基于SRS 自適應碼率集群為內容消費者提供視頻服務，在視頻碼率性能對比中Heavy-Ball 方法取得最好性能.對于整體資源消耗，Heavy-Ball 取得4 種方法中最優性能.綜上所述，Heavy-Ball 相較于另外3 種同期方案，在服務質量和資源消耗的綜合性能方面具有優勢.

6 結 論

本文提出了一種面向異構算力系統的計算和傳輸資源協同優化方法.首先介紹了異構算力網絡場景，并提出了一種面向通用應用的有向圖服務模型，該模型通過在有向圖結構表征應用服務的處理流程.隨后為表征網絡節點計算和傳輸負載情況，提出了一種計算和傳輸雙虛擬隊列模型.進一步提出多資源融合的增廣圖模型，將服務中的計算和傳輸聯合資源優化問題轉化為增廣圖路由選路問題.隨后，對多資源優化的問題進行建模，得到服務效用與系統資源聯合優化問題的形式化表示.并提出了一種基于波利亞重球法的梯度下降算法，并分析了該算法的時間與空間復雜度，此外還給出該算法在隊列穩定性、效用最優性和收斂性方面的理論性能.最后，進行了數值仿真測試和原型系統實驗，數值結果表明，基于波利亞重球法的資源優化算法理論性能的正確性，并具有良好的隊列長度、效用最優性和收斂性.另外在原型系統實驗中對比了同期的3 種解決方案，該算法在服務性能與系統資源開銷方面均具有一定優勢.然而，所提方法在面對節點頻繁加入/離開時，在系統穩定性上依然存在一些問題.希望未來工作能夠進一步彌補這些問題，并且在實際的應用環境中部署該算法，創造社會價值和商業效益，為用戶帶來更優質的服務體驗.

作者貢獻聲明：陳星延提出了研究思路并撰寫論文；張雪松負責完成實驗；謝志龍提出了指導意見并修改論文；趙宇和吳鋼提供了實驗方案.