云邊協同中的資源調度優化

王淑玲，孫杰，王鵬，楊愛東

云邊協同中的資源調度優化

王淑玲，孫杰，王鵬，楊愛東

（亞信科技（中國）有限公司，北京 100193）

隨著業務類型的豐富和多樣化，低時延、高帶寬、數據私密性、高可靠性等成為業務普遍的要求。邊緣計算、霧計算、分布式云、算力網絡等方案相繼被提出，并在產學研各界引發了深度的研究和探索。針對“多級的算力分布以及算力的協同將是未來算力結構的主流”這一觀點，產業內外達成了共識，算力管理、分配、調度等與資源優化相關的問題也成為當下的研究熱點和重點攻關方向。為此，面向未來的算力供給結構，首先描述了學術界、產業界資源調度優化問題的最新進展，總結了當前的主要方法論和工程實施架構；然后，針對兩種典型的云邊協同場景，從場景拆分、調度目標、求解方案依次進行分析，給出了適應場景特性的資源調度優化參考方案。

云邊協同；邊緣計算；算網融合；資源調度優化；算網聯合優化

0 引言

當前，社會正加速進入以數字化、網絡化、智能化為特征的信息社會。時低延、高帶寬、數據私密性、高可靠性等新時代業務的普遍訴求，推動基礎設施進入后云計算時代，邊緣計算、霧計算（fog computing）、分布式云、算力網絡等方案相繼被提出，并在產、學、研各界引發了深度的研究和探索。

針對邊緣計算的不同部署范式，多種概念被提出。多接入邊緣計算（multi-access edge computing，MEC）[1]由歐洲電信標準化協會（ETSI）率先提出，倡導在靠近業務的網絡邊緣側部署計算處理能力，以滿足未來業務對低時延、大帶寬、高可靠的要求。霧計算是一種分布式的計算基礎設施，通過將計算和存儲設備配置在互聯網邊緣減少互聯網數據傳輸量，從而降低時延、節省帶寬及相關費用。文獻[2]系統地闡述了霧計算的關鍵技術，列舉了常見的霧計算應用。分布式云由ITU-SG13[3]提出，強調將公有云服務分布到不同的物理位置，且服務的更新、管理仍由云服務商提供。算力網絡是2019年由中國運營商在ITU-SG13[4]上首次提出來的概念，其宗旨在于提供一體化的算力資源和網絡資源的聯合調度優化模型，以提升基礎設施資源的使用效率。

類似的概念還有很多，盡管各自強調的特點、提出的背景都不盡相同，但是，針對“多級的算力分布以及算力的協同將是未來算力結構的主流”這一觀點，產業內外達成了共識，算力管理、分配、調度等資源調度優化相關的問題也成為當下的研究熱點和重點攻關方向。

1 資源調度優化問題研究進展

資源調度優化問題是學術界和產業界的經典問題，在多種系統及場景下普遍存在。

針對云－邊算力協同場景，學術界的工作聚焦于：在算力和網絡的聯合資源約束、經濟性和綠色節能等效能要求下，用數學工具對資源調度優化問題進行建模并求解。文獻[5]和文獻[6]重點闡述了近3年內該領域的工作。文獻[5]針對“云－邊－端”的計算系統，全面闡述了單一任務的卸載或分配決策、多任務分配及調度、邊緣計算環境中任務優先級約束等幾種場景下的問題求解方法。文獻[6]將資源調度優化問題進一步細分為資源映射、任務調度、任務流調度3個子問題。結合子問題的數學模型類型，系統地總結了問題求解的方法和適用場景，包括：（1）經典的先來先服務（first come and first service，FCFS）、基于優先級等的調度方法[7-8]；（2）基于模糊理論的調度方法[9]，重點解決邊端的資源不確定性和動態性問題；（3）啟發式的調度方法[10-11]，以有限代價求解NP難問題；（4）強化學習算法[12]，應對環境的不確定性，提升系統的自優化、自學習能力。

在學術界，對于資源調度和優化問題，學者們提供了非常多的參考模型，但是，這些模型在走向工業生產時遇到了一些問題。這些問題主要體現在以下兩個方面：第一，參考模型基于的前提和假設與實際場景存在的差異；第二，模型以及求解過程中涉及的數據，在實際的系統中較難收集。因此，需要將實際工程的場景與學術參考模型的前提進行映射，進而選擇適宜的方案。

在產業界，云－邊協同的概念和實現方案尚未形成一個共識。首先，在概念上，國內和國際已經分化。國際上，以Gartner為首，將云－邊協同中的算力資源調度和網絡資源調度分別映射至分布式云（distributed cloud）[13]和云網絡（cloud networking）[14]兩個分支，推薦的供應商也分別屬于運營商和云商兩個陣營。在國外，算力和網絡分屬于兩個不同的產業角色，要將其聯合調度難度較大，因此，從全局資源統籌的角度上來看，兩類資源是分開調度的。在國內，算力基礎設施的供應一直存在著較為激烈的爭奪。運營商借助有網絡、有算力的優勢，在2018年就已經提出云網融合[15]的概念，以撼動云廠商算力運營服務的頭部地位。在2019年，中國運營商開始在ITU提出算力網絡[4]的概念，將云網資源統一協調和調度的想法又一次拋了出來，這一概念最初僅是云資源、網絡資源的聯合編排以及運營層的融合，但是隨著算力網絡熱潮的迅速到來、“東數西算”工程的快速推進，產業界已經著手考慮云、網資源聯合調度的技術攻關。在商業實現上，Kubernetes是當前云邊資源管理的主流框架。這一系統中的資源調度，重點還是考慮云資源的特性以及云內的算網協同，在其調度算法中更多考慮云資源的狀態等信息。針對這一問題，產業界針對邊緣算力的需求和特性做了一定的改進，如Kuberedge、Superedge等，但是算網資源效能、跨管理域中的資源協調等方面考慮得較少。

算力和網絡的底層基礎設施資源聯合調度是一個技術門檻較高的領域。在過去的十多年里，基礎資源的調度和優化一直以云商主導的IT路線為主。因此，整體以云和分布式云這套體系展開工作，云邊協同中的數據傳輸、鏡像傳輸等網絡需求是以一種較為粗放的方式滿足的。盡管做了一些工作，但是沒有太流行起來，對于成熟商用的系統，常常也都諱莫如深，并不過多暴露細節。為此，本文將面向未來的算力供給結構，結合學術界和產業界的研究進展，給工程實施提供一些框架性的思考。

2 云邊協同中的資源調度優化問題定義

盡管霧計算、MEC、分布式云、算力網絡等概念存在管理結構、算力形態等方面的差異，但是多級的、協同一體化的算力結構是一致的。

過去，在多級算力協同的場景下，針對算力如何組織、管理和調度，是通過集中式還是分布自治的方式，如何能夠達到資源效率的最優等關鍵問題，產業界內外存在不同的觀點和解決方案。文獻[18]從量化的角度證實，在多權屬的算力資源池中進行資源調度時，資源池的整體使用效率會得到提升。因此，面向未來的數字化經濟，需要打破集中式云算力的限制，利用網絡連接多級、多權屬算力，獲取強大的算力基礎設施資源。

一般地，資源調度優化問題定義如下。

3 云邊協同場景中資源調度優化問題的實施參考

3.1 工程實施方案三步驟

在求解定義1描述的問題時，算力的權屬、算力的結構、調度問題的決策主體等直接影響調度優化的維度，因此，在實際場景中，為了找到滿足資源約束、目標約束的，本文認為需要依次明確3個方面：場景、目標及約束、建模及求解。

（1）場景

在云邊多級算力協同的場景下，何方擁有算力的絕對管控權直接關系到問題的求解思路，具體地，會影響定義1中的目標函數、資源約束和映射的設計等。

在集團企業自建的云邊協同架構下，云邊算力為企業私有，邊緣算力調度目標是在有限的資源內完成盡可能多的任務。集中式的調度方法所需的絕對控制權、數據使用權在此種場景下都能夠得到充分的滿足。在分布式云的架構下，盡管云商有算力的絕對控制和感知能力，但是調度目標受到了資源需求方的服務等級協定（service level agreement，SLA）、經濟性等的約束，因此，調度問題則會轉化為云商和需求方之間的博弈問題，從而目標函數則轉換為滿足需求方SLA約束下最大化云商利潤率。在運營商主導的算力網絡架構體系下，目標函數又會包含盡可能多地調度到指定的算力節點或者均衡化算力節點的資源利用率等。同樣的情況，也會出現在和的設計上。

因此，在考慮問題的解決方案時，首先需要對算力結構、算力的管控權屬等問題進行明確。

（2）目標及約束

在支撐數字化業務的過程中，調度算法會根據參與主體對調度結果的評估維度，選擇合適的資源。但在實際的場景中，不同參與方的評估維度存在較大差異，甚至相悖，如在一個開放的算力供需市場下，算力的需求方期望的是以最低的算力成本得到最好的服務，而算力的供給方則是滿足業務SLA的同時收益最高。

因此，第2個需要明確的是：滿足何種約束條件，如何評估調度方案的優劣。

（3）建模及求解

云邊協同中的資源調度優化是一個比較復雜的問題。在算力節點規模較小時，簡單模型即能在可接受的時間內得到可接受的解，但是在諸如算力網絡這樣的場景下，節點規模大、節點類型多、資源約束維度高，優化方案的求解相對不容易，已有多項學術研究[16-20]證明了這是一個NP難問題。因此，需要對問題進行抽象和建模，并借助數學手段快速找到解。目前，針對這一問題，學術界的研究非常多，給產業界提供了很好的參考。文獻[5-6]基于霧計算的場景，全面地綜述和分析了當前的模型和求解方法，并對求解方法進行了分類。

3.2 典型場景的方案建議

基于前文的三步驟法，本節選擇AR/VR業務以及企業云邊協同數據治理業務作為云邊協同的典型場景，討論資源調度優化的實現架構和方案。

（1）AR/VR業務

AR/VR業務本質上是一種交互式的在線視頻流，AR/VR業務交互模式如圖1所示，對邊、云側有較強的算力和低時延的網絡需求。在公共的邊/云側算力完成渲染后，通過高速、高可靠的網絡傳送給用戶，如手機、個人計算機、平板計算機、機頂盒等終端設備；用戶通過輸入設備（虛擬鍵盤、手柄等）對業務進行實時的操作。另外，AR/VR業務在高鐵、地鐵等高速移動的場景下，用戶側終端設備將會在多個基站甚至多個地域進行網絡切換，這樣與初始連接的公共邊、云側節點網絡時延增加，因而需要在多個公共的算力節點進行切換，根據用戶的實際情況進行統一的調度和管理，將計算能力在多個節點之間無縫遷移，且保障用戶無感的服務切換。

圖1 AR/VR業務交互模式

將AR/VR業務與上述的模型進行映射。首先，在場景方面，AR/VR業務所需的算力是典型的多方供給模式。端側的算力屬于終端用戶，由業務方進行調度和控制；考慮業務接入的隨機性和高速需求，邊側的算力和網絡資源大概率為運營商所控制；云側的算力屬于云商。因此，在AR/VR場景中的資源調度優化需要將服務商和資源方的權責進行解耦。在基礎設施資源層，由運營商依照基礎設施的布局，為業務選擇合適的算力資源和網絡資源的組合；在基礎設施服務層，云商在自身的資源約束下，依據調度優化目標的指引，為業務服務選擇合適的資源；在業務服務層，業務服務方在應用層定義子業務和資源的映射。

目標函數的設定也是多維度的。在基礎設施資源層，調度的目標是優化資源的使用效率，包括資源的電量消耗、資源負載的均衡、資源供應方的偏好、業務的SLA等。在基礎設施服務層，服務商的考慮包括資源類型、服務優先級、集群負載等。在業務服務層，考慮的是業務的體驗質量（quality of experience，QoE）。文獻[19]是在Kubernetes調度機制上的改進，在云算力的基礎上增加了邊緣算力相關的時延、數據傳輸等指標，以適應云邊協同中存在的鏡像同步、數據同步等場景。

按照第2節對于資源問題的定義，可將AR/VR業務建模如下。

SP={SP1, SP2, SP3}為服務提供商，分別代表終端應用開發商、邊緣算力及服務提供商、云端算力及服務提供商。

={1,2, ···,I}為所有的算力節點集合，其中，網絡抽象為一類特殊的節點。

因此，基于節點和服務供應商的從屬關系可定義為：

在時刻，針對用戶發出的任務，其資源調度結果為：

如此，用戶針對任務付出的代價定義為：

服務提供商在一個計費周期內得到的效用為：

目標函數可定義為：

上述模型從經濟效能的角度，給出了調度方案的評估模型示例。當然也可根據實際系統的設計重新設計。文獻[16]提出的Zenith就是另一項值得參考的研究工作。Zenith在服務管理、邊緣資源管理解耦的前提條件下，提出了一種基于市場動態定價的機制的邊緣算力調度和優化方法提升邊緣數據中心（data center，DC）使用效率的同時提升了資源服務提供方的利潤率。基本過程是：①資源需求方（App層）根據自身業務特點，規劃好對于邊緣DC的需求；②根據地理分布特點，引入維諾圖，并基于加權維諾圖的理論為資源需求方選擇位置臨近的邊緣DC；③邊緣DC算力的多個算力服務提供方依據自身的成本和利潤，向資源需求方報價；需求方依據該DC的歷史服務質量等級給出報價，并選擇合適的算力供應方；④雙方就報價形成共識，則需求方的任務調度到邊緣DC上。

支持AR/VR業務時，該方案值得參考的包括：服務管理和邊緣資源管理解耦的前提與實際情況較為符合；在需求方和供給方之間，以市場化的手段，基于算力的歷史服務水平指導供需雙方合理定義量化的算力價格，對算力的供給、定價模式有較強的參考價值；Zenith通過市場機制，橋接了資源型調度和服務型調度的差異。同時，尚有幾點需要進一步細化：①選擇邊緣DC。文中未細化描述邊緣DC與業務接入點的映射。在業務實施中，可考慮接入點位置、邊緣DC的網絡接入帶寬等因素；亞信科技提出了算力網絡中的一種資源調度方法，為云邊協同業務選擇合適的DC；文獻[17]針對主播直播場景提出了一種邊緣接入節點的選擇方案；②邊緣算力提供報價時，如何評估資源自身的成本。在文獻的基礎上，可以考慮增加數據傳輸代價、鏡像傳輸代價。

（2）企業數據治理業務

當數據定義為企業的數字化資產后，通過數據治理逐步實現數據價值成為企業轉型的關鍵環節。在面對企業數據治理業務的“海量數據”“即時交互”“穩定安全”的要求時，傳統集中模式的云計算已不再是最優方案，云邊端協同成為產業界公認的替代方案。在工業生產中，端側部署現場的數采能力對接生產現場的各種異構數據源；邊緣側以“服務器+虛擬化”的方式部署的服務包括業務數據處理能力、數據的建模和可視化能力、數據開放的三大能力以及本地應用的管理；云側采用“1+”的集團——工廠的集約式管理，多層級聯，一次定義多點分發的模式，提升企業管理效率和標準化程度。

企業自建云或者企業自建邊緣云+公有云是支撐數據治理業務的典型算力結構。此方式下的場景建模可認為是AR/VR業務的簡化。首先是服務提供商方面的簡化，服務提供商收縮為企業、網絡供應商和公有云服務商；其次，是各類業務參與者的效用函數設計。在企業自建云的場景下，可設計為：

該類問題的求解還可參考文獻[18]的相關工作。文獻[18]基于有限的資源池，聚焦考慮數據密集型業務場景，提出了一種邊緣服務部署以及服務請求調度的方案。該方案值得參考的包括：①方案基于的前提和假設與企業自建云情形較為吻合，包括資源有限、調度目標設計、數據密集型、調度方案動態調整等；②方案采用啟發式的方法求解問題，以有限的代價得到可接受的方案，便于工程實施。尚需進一步探討的是該方案在當前的主流開發框架中的軟件實現。目前，Kubernetes是云計算的主流工程框架，并且在隨著云邊協同的需求迭代和演進，出現了KuberEdge、SuperEdge等云邊協同的開源框架，得到了產業界的關注。但是，主要集中在云邊服務的管理和協同，對于云邊協同的資源調度優化較少涉及，相關的工作可以參考文獻[19]。

在企業自建邊緣云+公有云的算力結構下，資源調度問題退化為結合網絡代價選擇云端算力，此種情況可參考文獻[16]。在該工作中引入云代理的角色處理云端算力的選擇問題，對云管平臺相關廠商有較大的參考價值。基于不同地域、不同云服務商的算力價格不同的現實情況，該文獻以算力需求方的目標為導向，綜合考慮虛擬機鏡像啟動時延和遷移代價，構建資源調度優化模型，并采用啟發式的方法求解問題。

4 結束語

云邊協同的計算模式由原來的“中心-用戶”的單邊模式轉變為“用戶-中心”“用戶-用戶”的多邊模式。伴隨這種轉變，在新的商業模型、技術架構調整的引領下，云邊系統中資源調度優化問題需要產業界、學術界共同攻克。在中國，算力網絡的概念引發了算力資源和網絡資源聯合調度的研究熱潮。但是，縱觀國內外，國際產業界鮮有相關的工程實施參考，學術界的研究成果對于工程實施的指導意義又有一定局限性。因此，本文結合產業界的典型場景，試圖篩選出對工程實施具有較大參考價值的學術成果，以期為未來的云邊協同架構的推進盡一份力量。

從上述云邊協同的典型場景分析中可知，為了應對算力權屬的多樣性，資源調度和優化需要劃分層次。在涉及多方權屬問題時，采用資源分配型調度方式，以經濟性換取可用性；在獨立權屬的資源池內，可采用服務型調度方式，滿足用戶對于靈活、動態、彈性等高級特性的需求。因此，面向未來的云網協同場景，資源調度優化針對調度的維度會劃分成不同的階段，并且這種多階段的調度方式將會持續較長的一段時間。

未來的工作將主要聚焦在泛在算力的納管、多級算力結構下的調度協同、調度機制在工程項目中的軟件實現。

[1] ETSI. Multi-access edge computing (MEC)[EB]. 2022.

[2] HU P F, DHELIM S, NING H S, et al. Survey on fog computing: architecture, key technologies, applications and open issues[J]. Journal of Network and Computer Applications, 2017(98): 27-42.

[3] MARTIN A. Distributed computing: utilities, grids & clouds ITU-T technology watch report 2009[R]. 2009.

[4] ITU-T. Y.2501: computing power network-framework and architecture[S]. 2019.

[5] 王凌, 吳楚格, 范文慧. 邊緣計算資源分配與任務調度優化綜述[J]. 系統仿真學報, 2021, 33(3): 509-520.

WANG L, WU C G, FAN W H. A survey of edge computing resource allocation and task scheduling optimization[J]. Journal of System Simulation, 2021, 33(3): 509-520.

[6] JAMIL B, IJAZ H, SHOJAFAR M, et al. Resource allocation and task scheduling in fog computing and Internet of everything environments: a taxonomy, review, and future directions[J]. ACM Computing Surveys, 2022, 54(11s): 1-38.

[7] IBRAHIM E, EL-BAHNASAWY N A, OMARA F A. Task scheduling algorithm in cloud computing environment based on cloud pricing models[C]//Proceedings of 2016 World Symposium on Computer Applications & Research (WSCAR). Piscataway: IEEE Press, 2016: 65-71.

[8] Abdullahi C, Gour k, Joarder K. The co-evolution of cloud and IoT applications: recent and future trends[R]. 2019.

[9] BENBLIDIA M A, BRIK B, MERGHEM-BOULAHIA L, et al. Ranking fog nodes for tasks scheduling in fog-cloud environments: a fuzzy logic approach[C]//Proceedings of 2019 15th International Wireless Communications & Mobile Computing Conference (IWCMC). Piscataway: IEEE Press, 2019: 1451-1457.

[10] ABDELMONEEM R M, BENSLIMANE A, SHAABAN E. Mobility-aware task scheduling in cloud-Fog IoT-based healthcare architectures[J]. Computer Networks, 2020(179): 107348.

[11] NI L N, ZHANG J Q, JIANG C J, et al. Resource allocation strategy in fog computing based on priced timed petri nets[J]. IEEE Internet of Things Journal, 2017, 4(5): 1216-1228.

[12] ZHAO X Y, ZONG Q, TIAN B L, et al. Fast task allocation for heterogeneous unmanned aerial vehicles through reinforcement learning[J]. Aerospace Science and Technology, 2019(92): 588-594.

[13] Gartner. Gartner trends 2021: what they mean for retailers[R]. 2020.

[14] Cloud Networking. The 2020 gartner magic quadrant for data center and cloud networking[R]. 2019.

[15] 中國電信. 云網融合2030技術白皮書[R]. 2020.

China Telecom. Computing and network convergence technical white paper[R]. 2020

[16] RAUSCH T, RASHED A, DUSTDAR S. Optimized container scheduling for data-intensive server less edge computing[J]. Future Generation Computer Systems, 2021 (114): 259-271.

[17] XU J L, PALANISAMY B, LUDWIG H, et al. Zenith: utility-aware resource allocation for edge computing[C]//Proceedings of 2017 IEEE International Conference on Edge Computing (EDGE). Piscataway: IEEE Press, 2017: 47-54.

[18] CHEN J S, BALASUBRAMANIAN B, HUANG Z. Liv(e)-ing on the edge: user-uploaded live streams driven by “first-Mile” edge decisions[C]//Proceedings of 2019 IEEE International Conference on Edge Computing (EDGE). Piscataway: IEEE Press, 2019: 41-50.

[19] FARHADI V, MEHMETI F, HE T, et al. Service placement and request scheduling for data-intensive applications in edge clouds[J]. IEEE/ACM Transactions on Networking, 2021, 29(2): 779-792.

[20] ADDYA S K, SATPATHY A, GHOSH B C, et al. CoMCLOUD: virtual machine coalition for multi-tier applications over multi-cloud environments[J]. IEEE Transactions on Cloud Computing, 2021(99): 1.

Resource scheduling optimization in cloud-edge collaboration

WANG Shuling, SUN Jie, WANG Peng, YANG Aidong

Asia Info Technologies (China) Co., Ltd., Beijing 100193, China

With the enrichment and diversification of business types, low latency, high bandwidth, data privacy and high reliability have become common requirements. Edge computing, fog computing, distributed cloud, computing power network and other solutions have been proposed, and have triggered in-depth research and exploration in industry, academia and research. There is a consensus within and outside the industry on the view that “multi-level computing power distribution and collaboration of computing power will be the mainstream of computing power structure in the future”. The problems related to resource scheduling optimization, such as computing power management, allocation, scheduling, have also become the current research hotspot and key research direction. Therefore, for the future computing power supply structure, focuses on the latest progress of resource scheduling optimization in academia and industry, the current main methodology and engineering implementation architecture was summarized. And then, for the two typical cloud edge collaboration scenarios, the analysis was carried out from the perspective of scene splitting, scheduling objectives, and solutions in turn, and the resource scheduling optimization reference schemes that adapted to the characteristics of the scenarios were analyzed and discussed respectively.

cloud-edge collaboration, edge computing, computer and network convergence, resource scheduling optimization, computing and networking joint optimization

TP393

A

10.11959/j.issn.1000–0801.2023027

王淑玲（1988– ），女，博士，亞信科技（中國）有限公司研發中心規劃部規劃總監，主要研究方向為網絡通信、云網融合。

孫杰（1983– ），男，亞信科技（中國）有限公司研發中心云網規劃部經理，主要研究方向為通信與5G網絡智能化。

王鵬（1976– ），男，亞信科技（中國）有限公司研發中心高級總監，主要研究方向為通信業務支撐、大數據和人工智能。

楊愛東（1984– ），男，博士，亞信科技（中國）有限公司通信人工智能實驗室首席數據科學家，主要研究方向為5G無線通信、大數據挖掘、機器學習及其應用。

2022-09-07；

2023-02-08