算網融合下時間連續的計算任務卸載機制

郝 昊 楊樹杰 張 瑋

1 （齊魯工業大學（山東省科學院）山東省計算中心（國家超級計算濟南中心）濟南 250101）2 （網絡與交換技術國家重點實驗室（北京郵電大學）北京 100876）

（haoh@sdas.org）

隨著移動終端設備的快速發展，催生出許多計算密集和時延敏感的新型網絡服務，它極大地豐富我們生活的同時，也給網絡帶來了巨大的計算壓力.預計到2035 年，人均需求算力達到10 000 Gflops，是2018 年人均需求算力的21 倍[1]. 但由于工藝的限制和摩爾定律的逐漸失效，傳統集約化的數據中心算力增長空間極為有限，將計算任務卸載到遠端云服務器中進行集中處理的傳統云計算模式將難以滿足未來社會發展的需求. 作為補充，一種新的計算范式——移動邊緣計算（mobile edge computing，MEC）[2]應運而生. 與傳統云計算相比，移動邊緣計算可以在網絡邊緣節點提供計算能力以支持計算密集型網絡服務，從而降低計算任務傳輸時延和遠端云服務器的計算壓力. 由此，通過由遠端云服務器、邊緣節點、移動終端設備共同組成的“云—邊—端”算力網絡（computing power network）架構將逐漸成為未來發展的必然趨勢.

算網融合的算力網絡可以通過網絡協同調度遠端云服務器、邊緣節點和移動終端的計算資源來為用戶提供高質量計算服務. 這3 種計算模式也各有利弊，其中遠端云服務器計算資源充足，但由于傳輸距離較長、回程鏈路受限等原因容易導致傳輸時延過高、網絡擁塞等問題；邊緣計算通過在邊緣節點提供計算能力可以有效縮短傳輸距離、降低處理時延，但邊緣節點計算資源相對有限，難以支持所有的計算任務；本地終端計算則完全沒有傳輸時延，但終端設備本身計算能力十分有限，容易導致計算任務時延過高. 因此，如何確定計算任務的卸載位置，協同利用遠端云服務器、邊緣節點和終端設備的計算資源，是算力網絡算網融合下的一個重要的研究方向.

盡管目前研究人員在算網融合下計算卸載方向上進行了大量的嘗試和努力，并取得了一系列優異的成果，但由于問題的復雜性，該方向依然面臨著諸多挑戰. 具體來說，本文主要考慮3 方面的問題：

1）時間連續性問題. 在大部分工作中，為簡化問題建模，往往會將時間進行離散化設置，系統僅在每個時隙開始或結束時進行卸載決策. 換言之，當某個計算任務到達時，系統不會立刻進行計算卸載決策，而是需要等到時隙的開始或結束時進行統一決策.計算任務的平均決策等待時間為?/2，其中 ?為時隙的間隔時長. 但時隙的間隔時長往往是不可忽略的，時隙長度與無線信道的相干時間（wireless channel coherence time）有關，在實際系統中通常被設置為10～100 ms[3-4]. 此外，在很多研究工作中都有一個潛在假設，即計算任務不會跨時隙，所有計算任務需要在一個時隙內完成，這樣保證每個時隙可分配的計算資源上限不變，均為設備的總計算能力，從而方便計算能力這一約束條件的建模，但這也就意味著在許多場景中時隙的間隔時長不能太短. 因此，若不考慮時間連續性問題，將時間離散化會造成決策等待時延，增加了計算任務的延遲.

2）算法可擴展性問題. 在每個時隙中會產生多個計算任務的請求，在時隙開始或結束時，計算決策算法需要確定所有計算任務的卸載狀態，因此決策變量往往與計算任務數量相關. 特別是一些基于深度強化學習的計算卸載算法，模型構建時輸出神經元的數量往往取決于計算任務數量[5]. 但在實際中，新的計算任務會源源不斷產生，輸出神經元數量也需要隨之改變，這也就意味著之前訓練好的深度強化學習模型需要重新訓練，造成大量計算資源的浪費. 為簡化這個問題，很多工作都有一個隱含假設，即計算任務總數不變，不考慮算法的可擴展性.

3）邊緣節點的協同問題. 現有部分計算卸載方面的工作只考慮了云、邊、端間計算資源的縱向協同，卻忽略了邊緣節點間的橫向協作[6]，即假設終端設備只能將計算任務卸載到某個特定的邊緣節點（如接入的基站），而無法將計算任務卸載到其他邊緣節點. 但由于邊緣節點所在區域的不同，終端設備的數量和任務量也不同，若不考慮邊緣節點間的協同，容易導致各個邊緣節點間負載不均衡，無法充分利用整體邊緣計算資源. 因此，邊緣節點間的協同是十分必要的，終端設備可以將計算任務卸載到其他邊緣節點（即使終端設備與目標邊緣節點不直接相連，也可以通過終端設備接入的邊緣節點轉發至目標節點），從而實現邊緣節點間計算資源的協同和計算任務的負載均衡.

針對這3 個問題，本文提出了一種算網融合下時間連續的計算任務卸載方法，在滿足計算任務允許時延閾值條件下，以最大化服務體驗提升率為目標，通過深度強化學習方法進行卸載決策. 本文的主要貢獻包括3 個方面：

1）構建了基于時間連續性的計算任務卸載模型.本文沒有將時間軸進行離散化，然后從時隙的角度進行模型構建，而是從計算任務本身出發構建時間連續性的計算卸載模型. 該模型不會在每個時隙結束或開始時才進行計算卸載決策，而是在計算任務到達時立刻進行決策，從而避免了決策等待時延. 此外，模型構建時還考慮了邊緣節點間的協同，即終端設備可以選擇任意一個邊緣節點進行計算卸載.

2）提出了一種基于深度強化學習的計算卸載方法. 首先通過定義系統狀態、動作空間、獎勵函數等要素將問題模型轉化為馬爾可夫決策過程，進而通過深度強化學習方法進行求解. 設計時充分考慮了算法的可擴展性，決策變量與計算任務數量無關，僅與邊緣節點數量相關，即當邊緣節點數量保持不變時，即使計算任務數量發生變化，也不需要修改模型中輸出神經元數量，從而提高了算法的可擴展性.

3）通過大量仿真實驗驗證了所提算法的有效性.實驗驗證了算法的收斂性，并在性能方面與其他2種先進算法進行了對比. 實驗結果表明，所提算法能夠有效收斂，并在任務平均時延、服務提升率等方面明顯優于其他2 種對比方法.

1 相關工作

數據經濟的發展將產生海量數據，數據處理需要云、邊、端協同的強大算力和廣泛覆蓋的網絡連接. 作為一種在云、邊、端之間按需分配和靈活調度計算資源、存儲資源以及網絡資源的新型信息基礎設施，算力網絡已經引起了產業界和學術界的廣泛關注. 2019 年，中國聯通聯合多家高校和科研院所發布了第一個算力網絡方面的白皮書——《中國聯通算力網絡白皮書》[7]，其中明確了算力網絡的體系框架，即算力必然會從云和端向網絡邊緣進行擴散，網絡將出現云、邊、端三級算力架構. 2020 年，華為在《泛在算力：智能社會的基石》[1]文件中指出，由云—邊—端組成的泛在算力架構是技術發展至今的必然選擇結果，未來算力必然構建“云—邊—端”泛在部署架構，滿足社會智能化發展帶來的算力需求. 中國移動在2021 年發布的《中國移動算力網絡白皮書》[8]中也明確指出，以算為中心，構筑云—邊—端立體泛在的算力體系. 算力網絡標準化工作也在持續進行，2021 年7 月在國際電信聯盟電信標準化部門（Telecommunication Standardization Sector of the International Telecommunications Union, ITU-T）第13 研究組報告人會議上，通過了由中國電信研究院網絡技術研究所雷波牽頭的算力網絡框架與架構標準（Computing Power Network- framework and Architecture）系列編號Y. 2501，該標準是首項獲得國際標準化組織通過的算力網絡標準.

近年來，計算任務卸載作為算力網絡算網融合下的一個重點研究內容，引起了學術界的諸多關注.部分工作[9-12]研究了僅包含單個邊緣節點的計算卸載問題. 文獻[9]考慮了一個多用戶、單邊緣服務器和單云服務器的3 層計算卸載場景，在問題建模時加入了傳輸鏈路的帶寬分配，將計算卸載和帶寬分配的聯合優化構建成一個分段凸規劃問題，并提出了一種具有較強魯棒性的優化算法. 文獻[10]研究了面向移動云計算的計算任務動態卸載問題，將其描述成滿足任務依賴要求和時間期限約束的能效成本最小化問題，并提出了一種最優的動態卸載算法，可以根據無線信道狀態動態改變計算任務卸載速率.文獻[11]著重考慮了計算卸載時的能耗問題，將其建模為隨機優化問題，目標是在保證平均等待隊列長度的同時最小化任務卸載的能量消耗，通過隨機優化方法將原始問題進行了轉化，并提出了一種動態節能的計算卸載方法. 文獻[12]則整體考慮了計算任務時延和能量消耗2 方面的因素，將計算卸載問題轉化為多目標優化問題，并結合并行深度神經網絡和深度Q學習算法設計了一種新的深度元強化學習方法對問題進行求解.

當系統中包含多個邊緣節點時，由于每個邊緣節點服務范圍內終端設備數量不同、計算任務量不同，單邊緣節點卸載模型容易導致部分邊緣節點計算壓力大，而部分邊緣節點相對空閑，即出現邊緣節點間負載不均衡的現象，從而影響服務體驗. 因此，部分最新研究工作[13-19]考慮了多邊緣節點協作共同完成計算任務. 文獻[13]提出了一種面向多邊緣設備協作的計算卸載優化機制，將優化問題建模成混合整數非線性規劃問題，并設計了一種基于偏好的雙邊匹配算法，在降低任務整體執行時延的同時實現邊緣設備間的負載均衡. 文獻[14]通過計算量、通信成本等方面對應用程序任務進行分類，幫助計算卸載決策，并提出了一種基于貪婪任務圖劃分的卸載算法，采用貪婪優化方法使任務通信成本最小化.文獻[15]關注于具有統計服務質量保證的計算卸載問題，放松了對計算任務時延閾值的限制，將必須在時限內完成計算任務改變為完成概率高于某個閾值即可，將其表述為具有統計延遲約束的混合整數非線性規劃問題，并通過凸優化理論和吉布斯抽樣方法對問題進行了求解. 文獻[16]考慮了計算卸載時任務延遲和無線傳輸時能耗間的均衡問題，通過對系統流量的預測，提出了一種高效、分布式的多層霧計算系統預測卸載和資源分配方案，只需少量預測信息值就可顯著降低任務時延. 文獻[17]構建了一種基于軟件定義的細粒度多接入邊緣計算架構，對網絡和計算資源進行協同管理，并設計了一種基于深度強化學習的2 級資源分配策略，從而提供有效的計算卸載服務. 由于終端設備的移動性，終端設備與邊緣節點間的連接可能不穩定，這個將會影響卸載決策，甚至導致卸載失敗. 文獻[18]則加入了移動性方面的考慮，提出了一種具有故障恢復的高魯棒性計算卸載策略，在終端設備移動的情況下也可降低能量消耗和縮短任務完成時間. 文獻[19]研究了工業物聯網中的計算卸載問題，提出了整合遷移成本和計算時延的協同卸載框架，并設計了以最小化系統成本為目標的基于學習的任務協同卸載算法，從而在不需要完整卸載信息的情況下選擇最優邊緣節點.

然而，當前關于算力網絡算網融合下計算任務卸載方面的研究大多沒有考慮時間連續性問題，將時間進行離散化處理，導致產生額外的決策等待時延. 而且其中一些基于深度強化學習設計的卸載算法只考慮了固定數量的計算任務，當計算任務數量改變時，往往需要修改神經網絡輸出神經元數量并重新進行訓練，算法的可擴展性較差.

綜上所述，本文針對多邊緣節點協作的算網融合場景，研究基于時間連續性的計算任務協作卸載問題，提出一種可擴展性強的、基于深度強化學習的計算任務卸載算法，目標是在滿足計算任務延遲閾值的條件下，最大化服務體驗提升率.

2 系統模型與問題描述

本節首先進行場景描述；然后介紹系統模型，包括終端設備模型和其他節點模型；最后對本文要解決的問題進行數學建模. 本文涉及的主要變量及相關描述如表1 所示.

2.1 場景描述

本文針對的是云邊端協同的泛在算力網絡架構，如圖1 所示，云為遠端云服務器，邊為邊緣節點，端主要包括用戶終端設備，各節點間通過無線鏈路進行數據傳輸. 終端設備在產生計算任務后，既可以選擇在本地進行計算，又可以通過無線鏈路卸載到邊緣節點或遠端云服務器進行計算，從而降低自身計算壓力，提升服務質量.

Fig.1 Illustration of our system architecture圖1 本文系統架構示意圖

假設云邊端協同的泛在算力網絡中包含N個邊緣節點、M個終端設備和1 個遠端云服務中心. 其中每個邊緣節點n∈{1,2,…,N}都配置有一個服務器，可提供的計算能力為（單位為CPU 周期數/s）. 每個終端設備m∈{1,2,…,M}也具備一定的計算能力，為（單位為CPU 周期數/s）. 遠端云服務器具有充足的計算能力，會為每個終端設備m分配固定的計算能力除了云邊端的縱向協同模式外，邊緣節點間也可以相互協作，即終端設備并非只能卸載到自身所屬的某個邊緣節點（如只能卸載到自身接入的邊緣基站），而是可以將計算任務卸載到任意一個邊緣節點上.

傳統建模主要是通過時隙的增加來體現系統時間的演變，本文為保證時間的連續性，不再將時間建模成離散的多個時隙，因此無法通過時隙的增加來描述系統時間的變化. 但問題優化目標是長期平均性能，問題建模時仍需要系統時間的演變. 為此，本文從計算任務產生順序的角度進行建模，即計算任務k并不表示某一類或某一個具體的計算任務，而是指系統運行后終端設備產生的第k個計算任務，這樣通過計算任務編號的增加來體現系統時間的演進.例如，對視頻A進行解碼這一計算任務，終端設備a和終端設備b均產生了該計算任務，但分別對應整個網絡系統的第6 個計算任務和第9 個計算任務，雖然任務相同，由于2 個終端設備產生該任務的時間不同，在本文中也將會以第6 個計算任務和第9 個計算任務來分別描述. 而在其他文獻中，計算任務k往往表示某個具體任務，而非任務產生的排序，即對于相同任務而言，即使產生時間不同其表述也相同，如若用計算任務k表示對視頻A進行解碼這一計算任務，則無論此任務何時產生，其表述都為計算任務k.可以用一個五元組(ck,uk,tk,dk,mk)來表示第k個計算任務的各方面屬性，其中ck為完成該計算任務需要的計算量，uk為該計算任務卸載時需要傳輸的數據量，tk為生成該計算任務的時刻（tk是一個連續值），dk為該計算任務允許的延遲閾值，mk為生成該計算任務的終端設備.

與文獻[20?21]一致，本文假設計算任務是不可分割的. 如圖2 所示，當用戶終端設備產生新計算任務時，首先需要決定是在本地處理還是需要卸載到邊緣節點或遠端云服務器. 如果終端設備選擇本地處理計算任務，將該計算任務加入到本地計算隊列中進行等待；否則終端設備需要決定將計算任務卸載到哪個邊緣節點或遠端云服務器，并將計算任務加入到該節點的計算隊列中.

Fig.2 Process of computing task圖2 計算任務處理過程

用二元變量xk∈{0,1}來表示第k個計算任務的卸載決策. 若xk=1 則表示第k個計算任務會在本地終端設備進行處理；若xk=0 則表示第k個計算任務不會在本地終端設備進行處理，需要進行計算卸載. 若第k個計算任務不進行本地計算，還需確定其計算卸載位置，用多元變量yk∈{1,2,…,N,N+1}表示第k個計算任務卸載的位置，若yk∈{1,2,…,N}則表示第k個計算任務需要卸載到編號為yk的邊緣節點上處理；若yk=N+1則表示第k個計算任務需要卸載到遠端云服務器上進行處理.

2.2 終端設備模型

計算任務進行本地處理時，需要將該計算任務加入到相應終端設備的本地計算隊列中，并按照先進先出（first-in first out, FIFO）的模式進行服務[22]，此時終端設備計算隊列模型的更新分為2 種情況：生成該計算任務的終端設備計算隊列更新和其他終端設備的計算隊列更新.mk

1）對于生成第k個計算任務的終端設備 而言，其需要本地計算第k個計算任務，計算隊列長度增加第k個任務的計算量，表示為

2）對于其他終端設備（m≠mk）而言，第k個計算任務進行本地計算不會增加自身計算任務量，則其計算隊列表示為

需要說明的是在離散時間建模中大多假設計算任務可以在一個時隙內完成，主要記錄每個時隙內到達的計算任務和其需要的計算資源，沒有構建計算等待隊列，其等待時間計算公式為其中是終端設備m為計算任務k分配的計算資源. 等待時間計算公式同樣適用于離散時間建模下的邊緣節點.

由于計算任務是在本地處理計算，因此不需要進行數據的傳輸，此時第k個計算任務的時延為

值得一提，本文雖然采取的是先進先出無優先級的服務模式，但這項工作也可以擴展到計算任務具有不同優先級的場景. 具體來說，每個終端設備不再只有一個計算等待隊列，而是對每類優先級的計算任務分別建立一個計算等待隊列，即計算等待隊列數量與優先級的數量相同. 當計算任務在本地計算時，會將該計算任務添加到對應優先級的計算等待隊列中. 計算時延時，將不低于本計算任務優先級的等待隊列相加即可確定在該計算任務前需要完成的計算量，再除以設備計算能力即可獲得任務的計算時延.

若計算任務k需要卸載到邊緣節點或遠端云服務器，除了對終端設備本地隊列進行更新外，還需要計算終端設備mk通過無線鏈路將計算任務k傳輸到相應節點上的傳輸時間. 考慮終端設備在正交信道上傳輸的無線網絡模型[23]，終端設備到邊緣節點或遠端云服務器的無線傳輸鏈路存在信號衰減.用代表從終端設備m到節點n（邊緣節點或遠端云服務器）的信道增益，則其傳輸速率為

其中Wm,n為終端設備m到節點n的鏈路帶寬，Pm為終端設備m的傳輸功率，表示噪聲功率. 需要說明的是，若終端設備m和節點n間不直接相連，可以通過其他節點進行轉發，在模型計算時調整鏈路帶寬也可以模擬估計出其傳輸速率，而不用對每個轉發過程進行單獨建模. 若第k個計算任務卸載到編號n的節點上處理，則其傳輸時延為

2.3 其他節點模型

當終端設備將計算任務卸載到邊緣節點時，即xk=0&&yk∈{1,2,…,N}，由于邊緣節點自身計算能力有限，且需要為多個終端設備提供服務，因此也會形成計算隊列的積壓，邊緣節點計算隊列的到達是終端設備卸載到該邊緣節點的計算任務，計算隊列的減少是該邊緣節點根據自身計算能力完成的計算任務量. 與終端設備計算隊列相似，邊緣節點的計算隊列也采用先進先出的服務模式，隊列更新也分為目標節點計算隊列更新和非目標節點計算隊列更新2種情況.

當第k個計算任務從終端設備卸載到邊緣節點時，若該邊緣節點為卸載的目標節點，即n=yk，則其需要將第k個計算任務加入到自身的計算隊列中，計算隊列表示為

綜上，第k個計算任務進行卸載后，邊緣節點n的計算隊列長度更新為

此時，第k個計算任務的計算時延為

除了邊緣節點外，終端設備還可以將計算任務卸載到遠端云服務器，即xk=0&&yk=N+1，與邊緣節點不同，遠端云服務器具有充足的計算資源，可以為每個終端設備提供固定的計算能力[24]，從而快速完成計算任務. 因此，若第k個計算任務卸載到遠端云服務器中，則不需要考慮云服務器中計算隊列的積壓，即計算隊列長度為0，計算時延為處理計算任務本身的時間：

2.4 云邊端計算卸載問題建模

在云邊端協同的計算卸載模式中，計算任務可以在終端設備、任意邊緣節點或遠端云服務器上執行，其服務時延為

計算任務協同卸載可以協同利用云邊端的計算資源完成計算任務，而在云計算模式中只能通過遠端云服務器來完成相關計算任務. 為了直觀體現云邊端協同卸載帶來的優勢，以云計算模式下服務時延作為對比，定義了服務體驗提升率Rk評價指標：

服務體驗提升率是一個相對性指標，服務體驗提升率越高說明與云計算模式相比，云邊端協同的計算卸載模式能夠減少的時延越多，服務體驗越好.與直接優化服務時延相比，優化服務體驗提升率能更好反映各個計算任務的服務體驗，降低某些極端計算任務對整體優化目標的影響. 因此，將平均服務體驗提升率定為云邊端計算卸載問題的優化目標，建立優化問題模型為：

X={x1,x2,…,xk,…xK}其中為是否進行本地計算的決Y={y1,y2,…,yk,…yK}策變量，為計算卸載的目標選擇變量，約束條件（15.1）保證計算任務能夠在計算任務允許的延遲閾值內完成，約束條件（15.2）為終端設備等待隊列、邊緣節點等待隊列、云服務排隊狀態等相關約束，約束條件（15.3）和（15.4）是對計算卸載變量取值的約束.

與離散時間建模相比，對計算卸載問題進行連續時間建模的優勢主要有2 個方面：1）避免決策等待時延. 在離散時間建模中，時間軸被分成了離散的時隙，并只在時隙結束時進行卸載決策，即當計算任務到達時并不會立刻進行決策而是需要等待時隙的結束，但時隙的間隔時長往往是不可忽略的[3-4]，導致較長的決策等待時間；在連續時間建模中，計算任務到達后可以立刻進行卸載決策，不需要等到時隙結束時進行統一決策，從而避免了決策等待時延，降低了計算任務的整體等待時延. 2）提升算法模型的可擴展性. 在離散時間建模中，由于一個時隙內會有多個計算任務請求，卸載決策時需要確定所有任務的狀態，因此決策模型與計算任務數量相關，即計算任務數量變化時，決策模型也需要隨之修改；在連續時間建模中，計算任務到達后會立刻對其進行卸載決策，決策模型每次只需要確定一個計算任務的卸載狀態，與計算任務數量無關，因此可以適應不同計算任務數量的場景，從而提升了算法模型的可擴展性.

云邊端計算卸載問題模型的目標是對長時間平均服務體驗提升率的優化，該類問題若通過動態規劃等傳統方式進行求解就往往需要獲取與用戶請求相關的完整狀態轉移概率，即獲取所有時間內的用戶請求后才會做出決策，因此傳統方法需要預測未來信息. 然而，由于網絡系統的動態特性，這種預測是十分困難的. 而深度強化學習通過數據采樣的方式代替狀態轉移概率，可以實現無模型學習，即只需要當前狀態，而不用預測未來信息，是解決這類問題的有效方法.

3 問題的馬爾可夫決策過程

通過深度強化學習解決的問題往往可以描述為馬爾可夫決策過程，本節將云邊端計算卸載問題描述為馬爾可夫決策過程，從而便于后續問題的求解.

由于連續時間建模下沒有定義時隙，因此將原來時隙變化而導致狀態轉移修改為計算任務編號增加而導致狀態轉移，即每個新計算任務為一個狀態節點而非每個時隙為一個狀態節點. 具體思路為：在新計算任務產生時，終端設備會觀察系統狀態（例如，任務大小、計算隊列信息），然后基于系統狀態為該任務選擇卸載動作（即本地計算卸載到邊緣節點、卸載到云服務器等），該狀態和動作將產生相應獎勵（例如，任務時延減少、超出任務延遲閾值受到懲罰）. 每個終端設備的目標是通過優化從狀態映射到動作的策略來最大化系統長期獎勵.

3.1 系統狀態

當第k個計算任務產生時，產生該任務的終端設備mk當前的負載狀態是影響卸載決策的重要因素之一. 用開始處理第k個計算任務前需要的等待時延表示終端設備的負載狀態，其定義為

其中式（16）的分子為第k個計算任務產生時終端設備mk積壓的計算量，分母為終端設備的計算能力.

除終端設備mk的負載狀態外，邊緣節點的當前計算負載狀態也是影響卸載決策的重要因素，與終端設備相似，用邊緣節點開始處理第k個計算任務前需要的等待時延表示邊緣節點的當前負載狀態：

除節點當前負載信息外，還需要考慮任務本身的一些屬性，具體來說，當第k個計算任務產生時終端設備mk觀察到的系統狀態定義為

其中Td(k)為所有邊緣節點等待時延組成的向量：

Tu(k)為計算任務k傳輸到所有其他節點（邊緣節點或遠端云服務器）需要的傳輸時延：

fedge為所有邊緣節點計算能力組成的向量：

3.2 動 作

當第k個計算任務產生后，終端設備mk需要對該任務進行卸載決策：①是否在本地處理計算任務，即確定xk=0或xk=1；②若需要進行計算任務卸載，則進一步確定其卸載的位置，卸載到哪個邊緣節點或遠端云服務器，即確定yk的取值. 因此，當第k個計算任務產生后，終端設備mk采取的動作可以表示為

當xk=1 即計算任務在本地執行時，yk的取值就無關緊要；只有當xk=0 即計算任務需要進行卸載時，yk的取值才決定計算卸載的位置. 因此，問題動作空間的大小為N+2. 在其他基于時間離散的計算卸載策略中，每個時刻需要為所有計算任務進行卸載決策，其動作空間的大小往往與計算任務數量成指數關系，增加了模型訓練的難度，而且計算任務的數量往往是動態變化的，這就導致當任務數量改變時，需要重新訓練決策模型，可擴展性差. 而該模型的優勢在于其動作空間的大小只與邊緣節點的數量成線性關系，與服務數量無關. 因此，本文模型的訓練成本更低，也更具有可擴展性.

3.3 獎勵函數

在本文構建的云邊端計算卸載問題中優化目標為最大化平均服務體驗提升率，因此如果一個動作能帶來更高的服務體驗提升率，其獲得的獎勵值也應越大. 此外，每個計算任務都有其允許的延遲閾值，若超出這個閾值，則應受到一定的懲罰. 基于此基本準則，獎勵函數定義為

4 基于深度強化學習的計算卸載算法

本節提出了一種基于深度強化學習的計算卸載算法，可以讓每個終端設備分布式的進行卸載決策.該算法基于深度Q學習（deepQlearning，DQN）模型方法[25]，可以在不獲取先驗知識的前提下，通過數據采樣的方式對優化問題進行求解. 而且，該方法通過神經網絡來預測獲得Q值（狀態-動作對的預期長期回報），每個輸出神經元對應一種動作的Q值，可以有效解決狀態空間大、動作離散的優化問題. 本節將分別介紹構建的神經網絡模型和基于DQN 的計算卸載算法.

4.1 神經網絡模型

神經網絡的目標是建立狀態-動作對到Q值的映射，即通過學習訓練獲得每個狀態-動作對的Q值.本文采用Double DQN（DDQN）訓練模式提升模型訓練的效率，圖3 為構建的神經網絡模型示意圖，具體來說，系統狀態信息通過輸入層傳遞到神經網絡中，此后通過2 個全連接層（full connected layer, FC）學習從狀態-動作對到Q值的映射.

Fig.3 Illustration of neural network model圖3 神經網絡模型示意圖

1）輸入層. 該層負責將系統狀態作為輸入傳遞到神經網絡中，輸入層神經元數量與系統狀態的變量參數相關，如式（18）所示，系統狀態包括本地計算延遲、傳輸時延等7 方面的參量，因此輸入神經元的數量為1+1+N+(N+1)+N+1+1=3N+5.

2）全連 接層. 2 個FC 層負責學習從 狀態到 對應動作Q值的映射關系，每個神經元層包含一組具有線性整流函數（rectified linear unit, ReLU）的神經元，這些神經元與前一層和后一層的神經元相連.

3）輸出層. 每個輸出神經元對應于一個動作的Q值，動作空間的大小為N+2，因此輸出神經元的數量也為N+2.

DDQN 模型訓練方式為：為避免過估計問題（overestimate）而導致模型訓練穩定性差，本文采用DDQN 的學習方式. 有2 個具有相同結構的神經網絡模型，一個稱為主網絡，另一個稱為目標網絡，其中主網絡是我們需要訓練學習的模型，目標網絡用來生成Q值的預測值，參數更新公式為其中Qm(s,a)代表主網絡的輸出Q值，Qt(s,a)代表目標網絡的輸出Q值，η為學習速率，γ為折扣因子. 模型采用經驗回放的方式進行學習，即將探索形成的數據組進行隨機打亂，使神經網絡可以重復多次訓練學習，從而打亂樣本間的關聯性，提升樣本利用效率.

4.2 基于深度強化學習的求解算法

本文提出的基于深度強化學習的計算卸載方法最終將運行在終端設備上，幫助終端設備進行計算卸載決策. 但在模型的訓練期間，需要消耗大量的計算資源，因此，采用邊緣節點輔助的方式進行訓練.在模型訓練期間終端設備m可以讓與自身具有最大傳輸能力的邊緣節點nm進行輔助訓練，然后邊緣節點nm將訓練好的模型參數傳輸給終端設備m，終端設備m則可以應用訓練好的模型直接進行計算卸載決策.

算法1 和算法2 分別描述了在終端設備m和邊緣節點nm上執行的深度強化學習算法，其主要思想是將終端設備給出的經驗信息（即狀態、動作、獎勵和下一個動作）傳輸給對應的邊緣節點，邊緣節點利用經驗信息來訓練神經網絡，得到模型參數，再將模型參數傳回終端設備，從而實現計算卸載決策.

終端設備主要負責信息的收集，在生成第1 個計算任務時，對終端設備m上狀態信息進行初始化：

其中td(L)=0，Td(L)=0，表示在進行第1 個計算任務時終端設備和邊緣節點均無計算任務的積壓. 終端設備m上運行的具體步驟總結如算法1 所示.

算法1.終端設備執行的算法.

輸入：神經網絡參數、系統狀態信息；

輸出：經驗信息四元組.

在終端設備m產生新任務時，會向其對應的邊緣節點發送參數更新請求，從而更新自身神經網絡模型和其他狀態信息，但過于頻繁的參數更新也會加重終端設備的傳輸壓力，因此這里有一個潛在問題：如何根據傳輸鏈路質量、模型收斂速度來確定參數更新頻率，換言之，算法1 中的步驟④～⑥并不一定每次執行. 為實現模型的快速收斂，本文實驗中終端設備每次產生新任務時均會發送參數更新請求.根據接收到的神經網絡模型參數 θm，通過ε 貪心算法選擇動作，即：

邊緣節點神經網絡模型訓練過程如算法2 所示.

算法2.邊緣節點執行的模型訓練算法.

輸入：經驗信息四元組，更新頻率L；

輸出：神經網絡模型參數.

在初始化Netm和以及經驗池后，邊緣節點開始等待終端設備m的請求消息. 如果接收到的是參數請求消息，邊緣節點則將Netm當前的參數向量發送給終端設備m；如果接收到的是一個經驗信息四元組，則將其存儲到經驗池中. 算法2 中的行⑩～?為模型訓練，首先從經驗池中隨機選取一批樣本，然后根據樣本信息計算目標Q值：

其中i代表一批樣本中的第i個樣本. 模型優化的目標是減小Netm輸出的Q值與目標Q值間的差距，即通過迭代優化算法（如梯度下降等）的方式最小化損失函數

其中P代表一批樣本中樣本的數量. 讓count代表模型訓練的次數，即每當模型訓練L次后，就需要用主網絡參數 θm更新目標網絡參數如算法2 中行?～?所示.

4.3 算法分析

由于用戶在一段時間內興趣偏好不會發生改變，神經網絡模型并不需要實時訓練更新，可以采用離線訓練的方式進行更新，如模型可以每2 個周更新訓練一次，而其他時間只是使用訓練好的模型進行卸載決策，而不進行訓練. 因此，主要分析終端設備每次計算卸載決策時的算法復雜度，而非模型訓練時的復雜度. 終端設備根據神經網絡輸出結果進行卸載決策，在此過程中只涉及到神經網絡正向傳播的過程，以乘積數量表示其計算復雜度，其中輸入層神經元數量為3N+5，全連接層神經元數量也與N相關，因此輸入層到第1 個全連接層的計算復雜度為同理，全連接層間計算復雜度、全連接層到輸出層的計算復雜度均為綜上，所提算法的計算復雜度為

關于收斂性，正如許多已有的著作（如文獻[26]）所提到的，深度強化學習算法的收斂性保證仍然是一個有待解決的問題. 盡管強化學習算法的收斂性可以被證明，但深度強化學習算法需要使用神經網絡進行函數逼近（例如深度Q學習算法中Q值的逼近），在這種情況下收斂性可能不再得到保證. 在第5 節通過實驗的方式對算法收斂性進行了評估.

5 實驗仿真

本節通過仿真實驗對提出的算法進行性能分析.首先驗證了算法的收斂性，其次從移動終端數量、邊緣節點數量、時間閾值要求等多個方面對算法性能進行評估.

5.1 實驗設置

考慮一個70 個終端設備、8 個邊緣節點和1 個遠端云服務器的網絡場景. 其中終端設備的計算能力取值區間為2～3 GHz，邊緣節點的計算能力取值區間為30～40 GHz，終端設備到邊緣節點的傳輸速率取值區間為10～15 Mbps，終端設備到遠端云服務器傳輸速率的取值區間為2.5～3.5 Mbps，計算任務傳輸數據量的取值區間為1～2 Mb，每個計算任務需要的計算量取值區間為0.5～1.5 Gigacycles，實驗具體參數設置如表2 所示. 設置神經網絡訓練時批量大小為16，學習速率η=0.01，折扣因子為 γ=0.9，并采用隨機梯度下 降（stochastic gradient descent, SGD）優化器進行模型的訓練優化.

Table 2 Parameter Settings表2 參數設置

為了評估算法性能，本文將所提算法與其他2 種計算卸載算法進行對比.

1）NOCO（non-cooperative algorithm）. 利用文獻[9]所提出的計算卸載策略，每個終端設備在將計算任務卸載到邊緣節點時，只能選擇本地關聯的特定邊緣節點，不能卸載到其他邊緣節點，而且邊緣節點間不會進行任務卸載.

2）COOF（cooperative-offloading algorithm）. 根 據文獻[19]提出的基于學習的計算卸載策略，邊緣節點間可以相互協作卸載，在不需要完全卸載信息的情況下選擇最優邊緣節點. 但算法中將時間進行離散化會引入計算決策等待時延.

3） TCCO（time-continuous cooperative offloading algorithm）. 本文提出的算法，考慮了時間的連續性問題，基于深度強化學習設計了多邊緣節點協作的計算卸載算法.

5.2 算法收斂性

本文通過離線方式對神經網絡進行訓練，并在不同神經網絡超參數下對算法的收斂性進行了評估.η

圖4 顯示了算法在不同學習速率（learning rate）下的收斂情況，其中學習速率即每次迭代時向損失函數最小值移動的步長. 如圖4 所示，學習速率不同，模型的學習效果與收斂速度也各不相同. 當學習速率η=0.1 時，模型會迅速逼近極值（當訓練次數在300次左右），但由于學習速率過大，模型在最后收斂狀態時也產生較大的波動，不利于模型的收斂；當學習速率η=0.001 時，學習速率過小，模型前期訓練時收斂速度較慢，訓練次數達到1 000 次左右時模型才逐漸收斂，學習速率過小也不利于模型的收斂；當學習速率η=0.01 時，模型既可以較快速度的收斂，而且收斂狀態也比較穩定. 因此，設置實驗仿真中模型的學習速率η=0.01.

Fig.4 Convergence of the proposed algorithm under different learning rates圖4 所提算法在不同學習速率下的收斂性

圖5 顯示了算法在不同批量大?。╞atch size）下的收斂情況，其中批量大小即模型每一輪訓練時選中的經驗池中經驗信息四元組的數量. 如圖5 所示，當批量大小為4 時，模型收斂速度較慢，需要經過600 次左右訓練才能收斂；當批量大小從4 增加到16時，模型收斂速度明顯加快，在400 次左右達到收斂；當批量大小從16 增加到64 時，模型收斂速度沒有明顯的增加. 而每一輪訓練時間和計算量與批量大小成正相關，即批量越大，每一輪需要訓練的經驗信息四元組的數量越多，計算量越大，訓練時間也就越長.因此，在實驗中選擇批量大小為16，即可以減少每一輪的訓練時間，又不會明顯降低算法收斂速度.

Fig.5 Convergence of the proposed algorithm under different batch sizes圖5 算法在不同批量大小下的收斂性

5.3 算法性能對比

本節在不同實驗參數下，通過與其他算法進行對比，對所提算法的服務提升率Rk進行分析.

本文對3 種算法從多個性能指標進行了對比，結果如圖6 所示. 4 種性能指標的定義為：1）平均時延為所有計算任務的平均等待時延，即其中K為計算任務總數；2）平均減少時延：與云計算相比，3 種算法能夠平均減少的任務時延，即3）服務體驗提升率Rk見式（14）；4）任務超時率即未能在允許的延遲閾值內完成的計算任務比例. 圖6 表明，由于沒有決策等待時延，所提算法TCCO 在平均減少時延和服務體驗提升率方面明顯優于其他2 種算法，在任務超時率和平均時延方面也明顯低于其他2 種算法，算法整體性能優于其他2種算法. 算法COOF 由于考慮了邊緣節點間的協作，能夠有效利用邊緣資源，從而各方面性能也都優于沒有節點間協作的NOCO 算法.

Fig.6 Performance comparison of three algorithms圖6 3 種算法的性能對比

圖7 顯示了3 種算法在不同計算任務允許的延遲閾值下的性能對比. 整體而言，TCCO 要優于其他2 種對比方法，這是因為在TCCO 中并沒有將實驗時間進行離散化，當計算任務產生時，TCCO 會立刻進行計算卸載決策，沒有等待時延；而其他2 種算法將時間進行離散，需要等到每個時刻結束或開始時才進行卸載決策，且在本實驗中，每個時刻的間隔設置為0.1 s，因此TCCO 在性能方面有較大提升. NOCO性能表現最差，這是因為NOCO 并沒有考慮各個邊緣節點間的協同，終端設備只能將計算任務卸載到某個特定的邊緣節點，從而導致算法性能較低. 有趣的是，隨著計算任務允許的延遲閾值增加，服務提升率反而增加. 這是由于在實驗時沒有引入超過閾值就將計算任務進行丟棄的機制，即在不同閾值情況下，計算任務的總量是相同的，而隨著延遲閾值的增加，約束條件放寬，算法就具有更多的調度方案，整體性能上也就會有所提升，但該提升會逐漸趨于平緩.

Fig.7 Three agorithms performance under different delay thresholds圖7 3 種算法在不同延遲閾值下的性能

圖8 描述了3 種算法在邊緣節點數量不變，不同終端設備數量下的性能對比. 終端設備數量從30 逐漸增加到130，隨著終端設備的增加，3 種算法的服務提升率均逐漸減小. 原因在于邊緣節點數量保持不變，即邊緣節點的計算能力沒有增加，而終端設備數量的增加，雖然增加了端點處的計算能力，但也意味著計算任務數量的增加，此時受限于有限的邊緣計算能力，更多的計算任務將卸載到遠端云服務器，服務提升率也就逐漸降低.

Fig.8 Three algorithms performance under different number of devices圖8 3 種算法在不同終端設備數量下的性能

本文測試了3 種算法在終端設備數量不變，不同邊緣節點數量情況下的性能變化，如圖9 所示. 與終端設備增加情況相反，隨著邊緣節點數量增加（邊緣節點數量從3 增加到12），3 種算法的服務提升率均有所提升. 原因在于終端設備數量不變，即計算任務量沒有發生變化，而邊緣節點數量增加使邊緣處的計算能力增強，可以在邊緣節點處理的計算任務數量也隨之增多，卸載到遠端云服務器的計算任務數量減少，服務提升率也就隨之增加. 但由于邊緣計算本身也會有傳輸時延和計算時延，因此服務提升率并不會隨著邊緣節點數量增加而一直增加，而是逐漸趨于平緩.

Fig.9 Three algorithms performance under different number of edge nodes圖9 3 種算法在不同邊緣節點數量下的性能

此外，本文還對3 種算法在終端設備、邊緣節點、遠端云服務器上的計算任務數量比例進行了分析，如圖10 所示. 3 種算法中，TCCO 在邊緣節點中計算任務數量比例最高，COOF 次之，這2 種算法在邊緣節點完成計算任務數量比例明顯高于遠端云服務器，這是因為這2 種算法均實現了邊緣節點間的協同，對于邊緣計算資源利用更加充分. 而NOCO 由于沒有考慮邊緣節點間的協同，邊緣資源利用率較低，相對而言更容易將計算任務卸載到遠端云服務器，因此在遠端云服務器執行的計算任務比例相對較高. 3種算法中終端設備完成的計算任務比例均很低，原因在于終端設備上計算資源有限，本地計算時延開銷大于進行計算卸載時帶來的傳輸時延開銷，因此大部分計算任務都將卸載到遠端云服務器或邊緣節點執行.

Fig.10 Executed task ratios of cloud, edge and devices圖10 在云、邊、端上執行的任務比例

6 結 論

針對目前算力網絡中計算卸載優化時算法可擴展性差、將時間軸離散化、只對單個邊緣節點優化等諸多挑戰，本文研究了面向時間連續的算力網絡計算任務卸載問題，從計算任務本身而非時隙的角度進行模型構建，并通過系統狀態、動作空間、獎勵函數等要素定義了問題的馬爾可夫決策過程. 提出了一種基于深度強化學習的計算卸載算法以確定計算任務在云、邊、端上的執行位置. 仿真實驗表明，所提TCCO 算法在服務平均時延、服務提升率等方面比現有卸載算法具有更好的性能.

由于能耗是某些場景（如物聯網）中重要影響因素，因此在未來工作中將在本文基礎上加入能量消耗的影響. 同時考慮設備的安全性和隱私性問題，將更多的影響因素加入到算法中，以適應各種不同的網絡場景和需求. 此外，用戶移動性會導致傳輸路徑和鏈路帶寬發生變化，未來也將對此進行深入研究和詳細建模，使得算法能夠更好適應移動網絡場景.

作者貢獻聲明：郝昊提出了算法思路并撰寫論文；楊樹杰設計了實驗方案并負責完成實驗；張瑋提出指導意見并修改論文.