面向5G 網絡云原生應用資源調度的博弈優化策略

趙文君，周金和，王 晶

（北京信息科技大學信息與通信工程學院，北京 100101）

0 概述

隨著5G 網絡和云原生技術的發展，2018 年中國數字經濟的規模已達4.73 萬億元，其中70%以上的企業已經使用容器技術或正在測試相關的應用環境，2020 年將有約50%的老舊應用以云原生化的方式被改進，云原生應用將成為新常態［1］。云原生被證明是建設和連續運行世界上最大云的有效加速技術。在當前復雜的云計算環境中，傳統應用需要快速響應用戶需求，從而提高了應用的復雜性，同時，5G 網絡產生的新需求也對應用提出了更高的挑戰。微服務體系結構的出現成為解決該問題最有效的方案之一，其將應用劃分為多個小服務，其中，單個服務專注于特定的功能，并且獨立運行在隔離的環境中，然后使用輕量級通信機制進行集成從而形成高內聚低耦合的服務結構［2］。云原生技術使應用具有更強的可靠性、更短的交付時間、更簡化的運維操作以及更高的運營效率。

5G 云原生技術的發展使得云原生應用引起研究人員的廣泛關注。在大規模應用系統中，微服務數量較多，微服務之間存在復雜的交互關系，導致云原生應用在運行時的資源調度面臨新的挑戰。微服務之間存在對網絡資源的競爭關系，5G 云原生服務提供商缺乏充足的資源來滿足所有應用程序的需求［3］，因此，將可用的服務資源合理地分配給不同的應用程序具有重要意義。文獻［4］研究云分布虛擬資源上的最佳虛擬功能放置問題，使用分支定界和模擬退火2 種啟發式算法來實現最佳布局，其降低了執行復雜性并縮短了服務遷移的延遲。文獻［5］考慮系統調整的延遲性，提出一種基于控制理論前饋和反饋的虛擬資源動態分配方法。文獻［6］針對5G 云無線電接入網絡提出一種動態資源管理策略，設計2 種貪婪啟發式算法，從而有效降低網絡中的服務器總數并提高終端用戶的體驗質量。文獻［7］從計算資源成本的角度出發，以最小化所有背包成本之和為目標研究動態背包問題，實現了服務部署成本的最優化。

雖然上述研究均針對資源利用率和網絡延遲2 個方面進行了優化，但是都未充分考慮網絡收益問題。在資源調度的過程中，能耗是5G 網絡中亟待解決的問題之一。文獻［8］充分考慮網絡中的能耗問題，通過提供按需內容交付服務解決了部署成本與服務可用性之間的權衡問題，然后進一步提出多項式時間啟發式方法，以對計算資源進行合理分配。

目前，博弈論已經廣泛應用于資源分配與優化任務，如互聯網定價和5G 網絡切片資源分配等。文獻［9］針對云原生應用運行時計算資源有限的問題，采用擁塞博弈理論對運行時的微服務資源進行調度管理，其有效提高了云原生應用的整體性能。文獻［10］提出支持卸載和遷移的智能網關方法，該方法采用非合作博弈重新調度云環境中的計算任務，降低了能耗和網絡延遲，但是其未考慮用戶的需求，如用戶對應用程序的偏好性等。文獻［11］通過對多個用戶構建非合作博弈模型，考慮傳輸時間和網絡成本的影響從而確定用戶的利潤，其提高了用戶的體驗質量，但未充分考慮資源有限和云提供商的利潤問題。由于云環境下應用程序之間的資源競爭行為與經濟學中的自由競爭市場類似，因此基于博弈論的方法能夠構建資源管理中的競爭關系［12］。考慮微服務之間的協作與競爭關系，可以將博弈論引入微服務中，通過對有限的網絡資源進行競爭以獲取更多的網絡效益。

云原生應用資源調度的目的包括優化應用時間、保證服務質量、優化費用以及實現高效節能等。本文提出一種面向5G 網絡云原生應用的資源調度博弈優化策略。將云原生應用程序劃分為多個微服務，微服務資源由云原生服務提供商所有，云原生應用為云原生應用商所有。云原生應用商通過租用云原生服務提供商的微服務來構建應用，從而提高收益，而云原生服務提供商通過收取對應的費用作為收益。為了使云原生應用商與云原生服務提供商的收益最大化并最大限度地降低能耗，本文將云原生應用資源調度問題建模為多主多從的Stackelberg 博弈模型，構建收益函數對傳統收益進行具體化描述，并引入用戶偏好性指標以提高兩者的傳統收益。為解決能耗問題，本文對能耗和傳統收益進行聯合建模，并證明納什均衡解的存在。在此基礎上，引入柯西分布提高策略的收斂性，使用分布式迭代方法確定云原生應用商的最佳租用比例和云原生服務提供商的最佳定價，最后通過Stackelberg 博弈實現效用的最大化。

1 系統模型

根據5G 網絡架構［13］，本文將云原生服務提供商和數據網絡中的云原生應用商構建為圖1 所示的系統模型。

圖1 系統模型Fig.1 System model

由圖1 可知，本文系統模型主要由X個云原生應用商NCNAi（i=1，2，…，X）和Y個云原生服務提供商NCSPj（j=1，2，…，Y）構成。云原生應用商擁有有限的微服務資源，可以將微服務資源租給云原生應用商，以便對云原生應用進行開發。其中，微服務資源服從密度為φ的異構齊次泊松點分布。應用開發的資源調度過程為：

1）云原生服務提供商給定微服務資源的定價，并告知云原生應用商。

2）云原生應用商根據應用的性能和微服務的定價等多種因素確定自身租用微服務資源的比例，并將自身應用開發為云原生應用。

3）用戶依據自身偏好和滿意度對應用進行訪問。

1.1 云原生應用流行度

在現實中，用戶對不同的應用具有不同的偏好，因此，應用之間的流行度存在一定差別，應用流行度越高，用戶的訪問頻率越高，相應的收益越大。因此，引入應用流行度這一指標可以更合理地確定微服務的租用比例，從而提高云原生應用的收益。假設存在N個應用，用集合表示為A=｛A1，A2，…，AN｝，第n個應用的流行度為Dn，n=｛1，2，…，N｝。不同的應用有不同的流行度，假設云原生應用商的應用集依據應用流行度由高到低降序排列，則用戶向應用請求服務的概率為Dn，其服從Zipf 分布［14］。

隨著移動終端的普及，一些流行的應用開始為人們所熟知，如抖音、快手等。本文引入調節因子θ，以調整應用的流行程度，從而提高云原生應用的流行度與云原生應用商的收益。Dn的計算公式如下：

其中，α為云原生應用的流行度指數，流行度隨著α的增大而提高，即云原生應用1 最受用戶歡迎，云原生應用N最不受用戶歡迎。

1.2 用戶偏好性

用戶偏好性直接影響云原生網絡的收益，一般而言，如果用戶偏好性低，云原生應用的收益就會降低，反之亦然。因此，本文引入用戶偏好性指標來衡量應用的服務質量，通過用戶反饋來調整云原生應用商的收益。用戶偏好性表示用戶使用云原生應用的體驗水平，偏好性直接受到應用時延、能耗大小等多方面因素的影響。文獻［15］建立用戶偏好性和網絡服務質量之間的多維函數關系，以此為參考，本文對用戶偏好性進行定義。假設每個應用有M個評價指標，每個評價指標都有R個離散的取值，則每個應用對應一個應用偏好矩陣G：

其中，gmr表示用戶對應用的第m個特性的偏好程度，gmr∈[0，1]，0 代表用戶反感，1 代表用戶喜歡，m∈{1，2，…，M}，r∈{1，2，…，R}。W=[W1W2…WM]為M個評價指標的權重值矩陣，用戶對第n個應用的偏好性如式（2）所示：

其中，ε為用戶偏好性的影響因子，λ為云原生應用商給出的微服務的租用比例。評價指標的取值數量R可以自行設定，依據大數定律，R趨于無窮大時，Bn收斂到常數值，具體如下：

1.3 云原生應用商能耗

云原生應用商提供云原生應用的過程主要包括：1）云原生應用的開發，其中主要為微服務的開發；2）維持云原生應用的運行。因此，云原生應用商能耗被定義為微服務開發能耗Ed和應用運行能耗Er之和，單位為瓦特。應用運行能耗Er包括微服務運行能耗Emr和傳統應用運行能耗Etr。微服務開發能耗是開發時間的函數，表示為tdevedev，其中，edev為單位時間內微服務開發所需能耗。綜上，云原生應用商的總能耗計算公式如式（4）所示：

其中，emr、etr分別為單位時間內微服務運行和傳統應用運行的能耗，tdev、trun分別為微服務開發和應用運行的時間，eidle為空閑時應用所消耗的能耗，Ttotal為應用開發和運行的總時間。

2 博弈創建

面向5G 網絡的云原生應用資源調度策略采用Stackelberg 博弈進行優化。Stackelberg 博弈模型至少包括博弈方、博弈的策略空間和博弈的效用函數［16］3 個元素。Stackelberg 博弈是一種符合主從關系的博弈，博弈方一般由主導者和追隨者構成，博弈雙方都存在各自的效用函數和策略空間［17］。本文的博弈過程可描述為：

1）主導者根據效用函數做出決策。

2）追隨者根據主導者的效用函數和決策給出自己的決策。

3）主導者根據追隨者的決策和自己的效用函數調整自己的決策。

4）博弈雙方通過調整各自的決策從而達到納什均衡，最終使雙方的效用達到最優。

2.1 博弈構成

Stackelberg 博弈模型的3 個元素具體如下：

1）博弈方：主導者是X個云原生應用商，追隨者是Y個云原生服務提供商。

2）博弈的策略空間：主導者的策略空間是云原生應用商給出的微服務的租用比例λxy，追隨者的策略空間是云原生服務提供商制定的微服務價格P={P1，P2，…，PY}。

3）博弈的效用函數：主導者的效用函數是云原生應用商的效用Ux，追隨者的效用函數是云原生服務提供商的效用Uy。云原生應用商的效用函數Ux由云原生應用商所得收益Uprofx（如式（5）所示）與用戶租用微服務的租金Urentx和運行能耗Ex之差構成，如式（6）所示。

其中，T為單位時間內應用的被訪問次數，S為每次服務的單價。

云原生服務提供商的效用函數Uy由租用微服務收取的費用Pyφyλxy和微服務管理成本Cyφyλxy之差構成，如式（8）所示：

2.2 問題創建

在微服務分配的過程中，云原生應用商通過租用云原生服務提供商的微服務來開發自身應用，以降低應用的時延和能耗，從而為用戶提供優質的服務并提高自己的收益。云原生服務提供商可以通過租用微服務來獲取一定的收益，最終通過博弈使云原生應用商與云原生服務提供商的收益最大化。

云原生服務提供商的優化問題可以視為使其效用函數最大化的問題，表達式為：

云原生應用商的優化問題也可以創建為其效用函數最大化問題，即：

效用函數最大化意味著云原生應用商收益最大化且能耗達到最優。通過對式（7）進行推導，可以得到云原生應用商的效用函數，即：

通過博弈構建過程可知，云原生服務提供商的博弈目的是最優化自己的效用函數值。云原生應用商依據收益和能耗租用一定比例λ的微服務，λxy的大小取決于云原生服務提供商的微服務定價Py，如果微服務的定價過高，云原生應用商將不會租用微服務；反之，如果微服務定價過低，云原生服務提供商難以獲得利潤。因此，云原生服務提供商只有進行合理地定價，云原生應用商才能選擇合適的租用比例，使雙方效用函數最優化，從而提高用戶體驗質量并使能耗達到最優。

2.3 納什均衡

Stackelberg 博弈由多個云原生應用商和多個云原生服務提供商構成，由于云原生服務提供商資源有限，因此多個云原生應用商之間存在競爭關系。同時，每個云原生應用商的租用策略會影響云原生服務提供商的微服務定價，從而影響其他云原生服務提供商的租用策略，因此，云原生應用商之間存在非合作博弈關系。

納什均衡是非合作博弈的最優解，是博弈參與者之間策略空間的穩定狀態，即不存在一個博弈參與者能夠通過改變對應的策略空間來取得更多的收益［18］。對于非合作博弈而言，如果博弈滿足如下條件：

1）博弈方的集合有限。

2）博弈參與者的策略空間集合為歐氏空間中的封閉、有界以及非空的凸集。

3）博弈的效用函數在博弈參與者的策略空間中滿足連續的性質且為凹函數。

則可以證明該博弈過程存在納什均衡解，每一個博弈方的效用函數都可以達到最優化，且任何博弈的參與者不能通過改變自己的策略來獲得更高的收益［19］。

納什均衡的證明過程如下：

1）設主導者（云原生應用商）為X個，追隨者（云原生服務提供商）為Y個，則對應的集合有限。

2）博弈參與者的策略空間顯然是歐氏空間中的有界非空閉集，且效用函數在策略空間上連續。

3）對效用函數Ux求一階和二階偏導數分別可得：

顯然，存在一階偏導數（如式（12）所示）和二階偏導數（如式（13）所示），且二階偏導數小于0，可得效用函數在策略空間上滿足嚴格凹函數特性。

綜上，云原生應用商之間的非合作博弈存在納什均衡解，證畢。

3 策略優化

云原生服務提供商的微服務資源有限，因此，云原生應用商的租用比例應該符合實際情況。本文考慮租用比例的合理性，通過求最值來確定租用比例的邊界條件，然后通過拉格朗日乘數法對博弈進行優化求解，最后利用迭代方法給出云原生應用商的最佳租用比例以及云原生服務提供商的最佳定價。策略優化過程具體如下：

假設微服務資源足夠所有云原生應用商使用，云原生服務提供商給出一組微服務租用價格P={P1，P2，…，PY}，通過求導可得云原生應用商的最佳租用比例，如下：

由式（14）可知，當λ=0，即云原生應用商的租用比例為0 時，云原生應用商將不會租用微服務，此時云原生服務提供商和云原生應用商都不會在云原生網絡中受益，而且用戶體驗質量不能得到改善。因此，存在微服務定價的最大值，由λ=0 可以求得微服務定價的最大值為：

當λ=1，即云原生應用商的租用比例為1 時，云原生應用商將租用所有微服務，由于云原生服務提供商資源有限，而且租用所有微服務會導致云原生服務提供商效用減少，因此存在微服務定價的最小值。由λ=1 可以求得微服務定價的最小值為：

綜上，存在微服務定價的最大值和最小值，當定價小于最小值時，云原生服務提供商應該上調當前的租用價格；當定價大于最大值時，云原生服務提供商應該下調當前的租用價格。通過多次調整來達到最佳微服務定價，最終使兩者利潤最大化，同時提高用戶的體驗質量。

在實際情況中，云原生服務提供商的微服務資源情況不可忽略，其需滿足式（17），而且云原生應用商的租用比例應該滿足0 ≤λ≤1。

其中，Fmax是微服務資源數量的最大值。

本文利用拉格朗日乘數法對博弈進行優化求解，首先構建拉格朗日函數如下：

其中，ω、ξ、υ為拉格朗日函數中的拉格朗日乘數。拉格朗日函數的充分必要約束條件為：

經過推導可得微服務的最佳租用比例如式（20）所示：

其中，γ的表達式如式（21）所示，其為云原生服務提供商微服務資源的約束條件。

對云原生服務提供商的效用函數求最大值可得到微服務資源的最優定價Py，將微服務的資源租用比例最佳取值代入式（8）進行求導，求導結果如式（22）所示，令導數為0 可反解出Py，每次更新的微服務資源定價如式（23）所示。

由式（23）可知，單個微服務資源的最優定價是動態變化的，它與其他云原生服務提供商的微服務定價密切相關。因此，本文采用迭代法對微服務的最優定價進行求解，迭代公式如下：

其中，t為迭代次數，為第t次迭代時微服務資源的定價，為第t次迭代時微服務資源管理的成本價，ρ為迭代步長，其為一個遞減參數，取值隨著迭代次數的變大而逐漸變小。在實際情況中，遞減參數值過小或過大都不利于納什均衡點逼近，因此，本文引入柯西分布［20］對該系數進行優化，柯西分布較高的兩翼概率特性使其可以產生遠離原點并具有較寬分布范圍的隨機數，使策略可以在更寬的范圍內尋找納什均衡點，從而提高策略的收斂性能。優化后的迭代步長ρ*表達式如下：

當迭代次數為t+1 時，若云原生服務提供商和云原生應用商的效用值達到最大，則終止迭代過程；反之，進入下一個周期，直到兩者效用值最大后停止迭代過程。

4 仿真分析

本文通過MATLAB R2016b 對所提策略進行仿真驗證，網絡模型由2 個云原生服務提供商和6 個云原生應用商構成，云原生應用商競爭微服務資源以開發應用。具體的仿真參數設置如下：單個云原生服務提供商擁有500 個微服務資源，λ=0.6，ε=0.2，R=50，T=100，S=2。在仿真中，將本文策略與蟻群（ACA）算法［21］、全局最優（GOS）策略［22］、QOS 優先（QOS PA）算法［23］，分別在云原生應用商效用、用戶滿意度和能耗減少率3 個方面進行對比分析。

圖2 所示為云原生服務提供商1 和云原生服務提供商2 之間微服務定價的關系，曲線上的點表示當前云原生服務提供商相對于另一個云原生服務提供商的最優定價策略。從圖2 可以看出，（0.49，0.4）為2 條曲線的交點，即納什均衡點，此處代表雙方定價和效用達到最優。雖然云原生服務提供商之間的最優定價互相影響，但是總存在一組最優定價使雙方效用最大化。

圖2 2 個云原生服務提供商之間的微服務定價關系Fig.2 Microservices pricing relationship between two cloud native service providers

圖3 所示為不同應用流行指數下云原生應用商的收益變化情況。從圖3 可以看出，在相同迭代次數情況下，α值越大，云原生應用商越受歡迎，對應的云原生應用商收益越大。在α一定的情況下，隨著迭代次數的增大，云原生應用商收益逐漸提高，當迭代次數約為50 時，云原生應用商收益值收斂到當前情況下的最大值。

圖3 云原生應用商收益與迭代次數之間的關系Fig.3 The relationship between the benefits of cloud native application business and the number of iterations

圖4 所示為不同策略和算法下云原生應用商的效用變化情況。從圖4 可以看出，本文策略的效用函數明顯優于其他策略和算法，且在4 種不同的策略和算法中，GOS 策略的收斂性能最好，在迭代次數約為45 時其收斂到最大值。

圖4 云原生應用商效用和迭代次數之間的關系Fig.4 The relationship between the utility of cloud native application business and the number of iterations

圖5 所示為不同策略和算法下用戶平均偏好度和用戶對應用的使用次數之間的關系，從圖5 可以看出，隨著用戶對應用使用次數的增加，用戶的平均偏好度逐漸增加，且本文優化策略的用戶平均偏好度明顯優于其他3 種策略和算法。

圖5 應用使用次數與用戶平均偏好度的關系Fig.5 The relationship between the number of applications used and the average user preference

圖6 所示為不同策略和算法下應用使用次數與能耗減少率的關系，本次實驗中假定不同策略和算法下用戶產生的請求一致。從圖6 可以看出，隨著應用使用次數的增加，能耗減少率逐漸提高，且本文優化策略的能耗減少率性能優于其他3 種策略和算法。

圖6 應用使用次數與能耗減少率的關系Fig.6 The relationship between the number of applications used and energy consumption reduction rate

5 結束語

本文針對5G 網絡中云原生應用的微服務資源調度問題進行研究，提出一種面向云原生應用資源調度的博弈優化策略，以提高云原生應用商和云原生服務提供商的收益，降低網絡能耗，提高用戶的體驗質量。將云原生應用資源調度問題建模為多主多從的Stackelberg 博弈模型，對傳統收益進行具體描述，引入用戶偏好性指標，以提高云原生應用商和云原生服務提供商的傳統收益。針對資源調度過程中的能耗問題，對能耗和傳統收益進行聯合建模，證明納什均衡解的存在，并使用分布式迭代方法確定云原生應用商的最佳租用比例和云原生服務提供商的最佳定價，在此基礎上，通過Stackelberg 博弈實現效用的最大化。仿真結果表明，該策略能夠有效提高網絡收益并降低網絡能耗。本文工作對構建未來的綠色網絡有一定參考意義，下一步將在5G 網絡和信息中心網絡中聯合部署云原生應用，以提高內容分發率并降低網絡能耗。