面向多租戶網絡資源分配的博弈優化策略

鄭振康，周金和

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

0 概述

5G 網絡設計的目的是為了能夠支持來自不同垂直行業和用戶間差異化的服務需求。在傳統網絡中，針對特定服務和需求來設計專用網絡的方式雖然部署簡單、隔離性強，但是存在資源利用率低、服務響應時延大等問題。為了在不犧牲服務質量的前提下，合理有效地利用基礎設施并更加高效地提供定制化服務，網絡切片技術成為5G 網絡應對上述問題的關鍵［1］。5G 網絡切片通過集中控制和云計算技術，將公共的基礎設施資源集中云化，并基于資源池劃分出不同的網絡切片。每個切片都由多種網絡功能構成，不同類型的切片應用于特定服務場景下的具體用例［2-3］。5G 網絡切片從本質上改變了傳統的服務方式，通過對物理網絡的資源分層切片，為不同的請求提供專用網絡，能夠進一步優化由于請求差異化與服務多樣化引發的資源浪費和網絡部署成本過高的問題［4］。

靈活的網絡切片部署依賴于高效的切片資源分配和編排管理，合理的資源分配方案能夠有效降低網絡部署成本、提高資源利用率和用戶滿意度。網絡資源分配優化作為5G 網絡切片中尚未有效處理的難點，如何制定高效可行的資源分配方案引起了學術界的廣泛關注。相關學者充分考慮了網絡切片中資源的分配優化和方案部署，多數方案都從提高資源利用率和降低網絡能耗兩方面進行研究。文獻［5］研究無線虛擬化環境中的帶寬資源分配，通過貪婪搜索實現高效的資源編排，可以為用戶動態地分配帶寬資源，優化系統性能。文獻［6］研究切片即服務，開發了一種基于多云域的內容分發網絡即服務平臺，能夠改善內容分發網絡切片的部署成本和服務質量。文獻［7］研究多服務無線網絡中的資源分配，聯合考慮了切片間的資源分配以及切片內的資源調度問題，該方案可以在保證切片隔離的同時，平衡分配效率和服務時延。文獻［8］研究蜂窩異構網絡中的頻譜資源分配問題，聯合優化了網絡中的頻譜分配和用戶接入，可以提高網絡終端速率。上述研究工作主要對網絡切片的成本以及服務時延進行了優化，但沒有考慮網絡能耗。

博弈論是研究理性個體在利益沖突的情況下制定對策，最終達到平衡態的數學工具。博弈模型為分析和預測群體的策略交互行為提供了一個系統的理論工具，被廣泛用于解決網絡切片資源分配和優化問題。文獻［9］研究無線接入網切片的動態資源分配問題，提出一種基于博弈論的自動化機制協助租戶決策，該機制能夠明顯提高租戶收益。文獻［10］將端到端網絡切片的資源分配問題建模為系統收益最大化的問題，并通過拍賣機制求解，該機制能保證資源分配的公平性，但切片間的競爭性不足。文獻［11］提出一種面向5G 網絡緩存資源分配的博弈優化策略，聯合優化了網絡提供商的收益和網絡能耗，有效地改善了緩存命中率和系統能耗，但未考慮緩存資源的高效利用。文獻［12］研究無線頻譜資源、無線網絡基礎設施和移動用戶間的三方匹配問題，通過匹配博弈解決資源分配問題，降低了資源分配的響應時延和系統成本并提高了用戶滿意度，但該文獻未考慮服務切片在實際網絡部署的網絡能耗和資源利用率等關鍵指標。

通過博弈來實現多租戶網絡中頻譜資源的合理分配，能夠提高頻譜資源的利用率、降低切片部署成本、增加網絡收益并提升用戶滿意度。為此，本文提出一種面向多租戶網絡資源分配的博弈優化策略。網絡中基礎設施提供商為網絡切片租戶（Network Slice Tenants，NSTs）分配構建接入服務切片所需的基站頻譜資源，NSTs 和用戶的關系建模為多主多從的Stackelberg 博弈。通過引入切片流行度和服務命中率等指標，構建博弈雙方的收益函數。在此基礎上，應用逆向歸納法，通過拉格朗日乘數法求解出用戶的最優吞吐量需求，并根據分布式迭代算法求解NSTs 的最優接入服務切片定價，最終經過多次迭代后收斂到唯一的納什均衡點。

1 系統模型

多租戶網絡中無線接入網切片結構如1 所示，其中包括物理基礎設施層、虛擬網絡資源層、網絡切片實例層和網絡服務實例層4 個模塊［13］。本文提出的面向多租戶網絡資源分配的博弈優化策略用于解決接入服務切片通信資源中頻譜資源的合理分配，部署在網絡切片管理和編排模塊，以實現接入服務切片實例資源的合理分配，并為用戶提供接入服務實例。

圖1 無線接入網切片結構Fig.1 Structure of radio access network slice

在本文模型中，各模塊的具體功能如下：

1）物理網絡基礎設施層包括基站等接入設施、計算服務器和存儲單元，分別由不同的提供商管理。

2）虛擬網絡資源層包括三大網絡資源，為物理網絡基礎設施通過虛擬化技術整合而成的資源塊，并提供給NSTs。

3）NSTs 解析服務需求映射，租用虛擬網絡資源，構建網絡切片實例層。

4）網絡服務實例層提供用戶和業務服務，每種服務包括不同用例，每個用例都由一個服務切片實例表示。

1.1 系統模型

本文系統模型如圖2 所示，由1 個基礎設施提供商、M個NSTs{1,2,…,M}以及N個用戶組成。其中用戶包括K個內部接入用戶{1,2,…,K}和L個外部接入用戶{1,2,…,L}，所有用戶均可訪問所有NSTs，切片間的頻譜共享借助于多址接入技術。

圖2 本文系統模型Fig.2 System model in this paper

在本文系統模型中，服務請求和切片構建的具體過程如下：

1）基礎設施提供商擁有基站頻譜資源，為合理高效地利用物理設施并增加自身收益，將虛擬網絡資源出租給NSTs。

2）NSTs 根據用戶的需求和切片流行度構建接入服務切片，為用戶提供網絡接入服務。

3）用戶購買接入服務切片，接入網絡獲取所需內容。

由于網絡中的物理資源有限，NSTs 會根據用戶的需求和自身的服務能力來動態地調整切片定價，以最大化自身收益，進而最大化網絡收益。

1.2 資源模型

基礎設施提供商基站的頻譜資源抽象為：最大帶寬頻譜資源為B，下行傳輸功率為p，假設B和p為常數。對于NSTsm，m∈{1,2,…,M}，從基礎設施提供商處租用虛擬頻譜資源，以分配得到一定比例的頻譜帶寬。本文假設接入服務切片之間是物理隔離的，NSTs 之間不存在干擾。

對于內部用戶而言，能夠直接獲得的網絡接入吞吐量Ri與訂購的切片類型有關，即與NSTsm在接入服務切片中再分配的頻譜資源有關。Ri計算如下：

1.3 切片流行度

由于用戶對于不同接入服務的偏好不同，因此NSTs 需要提供不同的切片類型。通過分析用戶的請求分布，提前構建用戶下一次可能請求的切片實例，能夠提高用戶滿意度，降低切片請求時延和網絡能耗。

假設用戶總共請求C種接入服務切片，C={S1,S2,…,SC}。Zipf 分布［14］描述了接入服務切片排名與其訪問概率之間的關系，假設{S1,S2,…,SC}是接入服務切片排名，訪問概率Dc計算如下：

其中：ω為平坦因子，當ω=0 時滿足一般的冪律分布；υ＞0 為偏態因子，也稱為流行度指數，υ越大，切片被訪問的概率越高，即切片流行度越高，S1越受歡迎，并且少量切片類型占有更高的請求概率。

1.4 服務命中率

假設用戶對網絡接入服務的請求滿足泊松分布，平均請求率為λ，根據文獻［15］，本文考慮生存時間（TTL）切片管理模型，則NSTsm接入服務切片c的命中率可表示為：

其中：λn,c=λ·Dc表示用戶對切片c的請求率；Tm表示NSTsm的接入服務切片特征時間，即從切片實例構建到終止服務的持續時間。

由于切片的類型數量很大，因此到達每個NSTsm的請求率相對很小，根據等價無窮小定理，e-x～x(x→0)，可以近似得到：

2 問題構建

一個博弈模型通常由3 個基本元素組成：決策個體集合，每個決策者所能采取的策略集合以及每個決策者的收益函數［16］。

本文考慮的Stackelberg 博弈模型的決策個體地位不對等，決策個體集合分為領導者和從屬者，其中領導者處于決策的主導地位，每個決策個體都有自身的策略集合和對應的收益函數［17］。Stackelberg 博弈可以概括為以下3 個階段：

1）領導者首先做出當前收益函數下的最優決策。

2）從屬者考慮領導者和其他從屬者的策略，結合自身收益跟隨決策。

3）領導者再考慮從屬者的策略和自身收益函數調整其決策。整個博弈過程是動態的，當雙方收益不再增加，即沒有決策個體愿意改變策略時，博弈過程結束。

2.1 博弈構成

本文通過多主多從的Stackelberg 博弈來建模多租戶網絡接入服務切片的頻譜資源分配問題，基本元素構成具體包括：

1）決策個體集合。領導者是M個NSTs{1,2,…,M}。在多租戶網絡中，NSTs 租用基礎設施提供商的基站資源，它具有先手優勢，首先決定接入服務切片定價并影響從屬者的決策。從屬者包括內部用戶{1,2,…,K}和外部用戶{1,2,…,L}，用戶 考慮NSTs 的切片定價和自身吞吐量需求，調整切片訂購策略，最大化自身收益。

2）策略集合。用戶的策略是其在每個NSTs 處訂購的服務切片比例xi,m、xj,m，其需求可由多個NSTs滿足。NSTs 進行資源的切片實例化和重售，它的策略是制定切片的價格P={P1,P2,…,Pm}。

3）收益函數。用戶的收益函數用Un表示，NSTsm的收益函數用Um表示，其中，n∈{1,2,…,K；1,2,…,L}，m∈{1,2,…,M}。

假設多租戶網絡中包括兩類用戶，即內部用戶和外部用戶。這種假設是合理的，例如在通過接入服務切片接入學校網絡時，內部用戶包括學生、教職工等，可通過校園網直接接入，而外部人員需要借助虛擬專用網間接接入。

用戶的收益Un包括兩部分：一部分是獲得接入服務切片的收益，表示為接入吞吐量Rn的對數形式［18］；另一部分是購買服務切片的支出。

對于內部接入用戶i，i∈{1,2,…,K}，式（5）表示與接入吞吐量Ri相關的收益：

用戶獲得接入服務切片時的最終收益為：

其中：δi為收益系數；λ為平均請求率。

切片的價格應該結合市場規律，即NSTsm的訪問人數越多，切片價格應該更高，這個關系用nm/Nm表示，為NSTsm中當前存在的用戶數除以其最大服務能力。用戶購買接入服務切片的成本如式（7）所示，內部接入用戶的凈收益如式（8）所示：

其中：ηm為成本系數表示受市場規律影響下的切片價格。

對于外部接入用戶j，j∈{1,2,…,L}，與內部接入用戶不同，其成本與切片價格是二次函數關系，即對外部接入用戶收費更高，并且沒有保證基礎吞吐量式（9）和式（10）為外部接入用戶與接入吞吐量相關的收益和購買接入服務切片的成本，外部接入用戶與NSTs 的博弈建模及求解與內部接入用戶類似，故后續博弈求解中只考慮內部用戶接入。

其中：τ為調整系數，控制外部接入用戶成本函數的變化。

NSTs 的收益包括接入服務切片定價Pm帶來的收益以及構建切片實例的成本Εm，則NSTsm的收益函數為：

2.2 問題建模

在本文資源分配系統中，用戶通過訂購接入切片來接入網絡，在支付切片價格后獲得所需服務。同時，NSTs 通過制定資源的重售價格，創建網絡切片來獲取收益。兩者在考慮服務能力和體驗質量的前提下，都試圖最大化自身收益。

對于每個NSTs 而言，資源分配優化問題可映射為其收益最大化問題，即：

其中：切片定價為非負值。

對于兩類用戶而言，優化問題同樣被映射為其收益最大化問題，將式（6）、式（7）代入式（8），得到內部接入用戶的凈收益解析式為：

則對應的收益最大化問題為：

其中：0 ≤x≤1 為用戶訂購切片比例取值。

從上述博弈模型問題構建可以看出，NSTs 的目標是最大化其在式（11）中的收益。而用戶作為從屬者，其目標為式（14），在NSTs 做出決策后跟隨決策。

本文考慮的接入服務切片頻譜資源分配模型中存在兩種博弈，NSTs 和用戶之間是符合主從關系的Stackelberg 博弈，在NSTs 切片定價決策后，用戶之間是非合作博弈關系。NSTs 之間通過價格博弈，來吸引更多的用戶購買接入服務切片，盡可能增加自身收益；同樣，用戶可以根據NSTs 的定價調整自己的購買策略。博弈建模的結果是得到純策略納什均衡點，該點處博弈雙方選擇最佳策略，并得到最佳策略下的最大收益。

2.3 純策略納什均衡

Stackelberg 博弈的納什均衡定義為子博弈完美納什均衡：一個接入頻譜資源的分配和定價策略，其中沒有任何一個決策個體有興趣偏離該策略，否則自身收益會減少［19］。

定義1（最佳響應）一個決策個體i對于策略組合s-i的最佳響應為純策略使得對于所有的策略

具體地，在本文的模型中，NSTs 之間共享用戶的接入服務請求，每個NSTs 決定頻譜資源的重售價格以最大化自身收益。顯然，當服務兩類用戶的收益更大時，該NSTs 的最佳響應超過只服務單一用戶。

定義2（納什均衡）如果對于所有的決策個體i，si均是對策略組合s-i的一個最佳響應，則策略集s=(s1,s2,…,sn)是一個納什均衡。

下文將給出本文資源分配博弈優化模型純策略納什均衡解的證明。

假定領導者已做出決策，即公布資源重售（服務切片）價格p，在該定價下用戶之間是非合作博弈關系，收益函數為Ui(p,xi,m,x-i,m)，其 中i∈{1,2,…,K}，則用戶的切片訂購策略間存在唯一的納什均衡點。

證明：根據文獻［16］中布勞威爾不動點定理可知，若滿足博弈的決策個體有限，每個用戶的策略空間x是歐氏空間上的有界閉集，并且其收益函數Ui在x上是連續的，且存在一個不動點，則該博弈具有一個純策略納什均衡解。

下文證明用戶收益函數Ui在其策略空間x上是凹函數。首先將用戶收益函數Ui對策略空間xi,m求一階偏導數：

然后將用戶收益函數對策略空間xi,m求二階偏導數：

由式（16）可知，一階偏導數存在，二階偏導數為負，即收益函數在整個策略空間上為凹函數，再結合收益函數的單調性和凹函數圖像性質可知，用戶的切片訂購策略間存在唯一的納什均衡點，證畢。

3 博弈求解

第2 節已經證明了本文提出的Stackelberg 博弈模型存在子博弈完美納什均衡，本節用一種逆推解法——逆向歸納法來求解博弈模型。首先，求解Stackelberg 博弈的第二階段，得到用戶最優的吞吐量需求，即用戶訂購的服務切片比例x*。然后，將x*用于求解博弈的第一階段，得到NSTs 切片的最優定價p*。

3.1 用戶的最優吞吐量需求

由于在多租戶網絡中，基礎設施提供商基站的頻譜資源有限，并且用戶存在預算約束，因此在實際求解中，必須考慮用戶的最大成本約束。用戶的最優吞吐量x*求解問題表示為：

本文選擇拉格朗日乘數法來求解約束優化問題式（17）。構造拉格朗日函數如下：

其中：α、β、γ是拉格朗日乘子。

通過KKT（Karush-Kuhn-Tucher）條件［20］得到用戶的最優吞吐量需求，條件如下：

其中：條件②和條件③分別為原始和對偶可行條件；條件④和條件⑤為互補松弛條件。

求解式（19）得到用戶的最優吞吐量需求，如式（20）所示：

3.2 NST 的最優切片定價

得到用戶的最優吞吐量需求x*后，本文提出一種復雜度較低的迭代算法，用于求解NST 的最優接入服務切片定價p*，具體步驟如下：

1）輸入x*及其他初始化參數。

2）初始化P={P1,P2,…,Pm}，令P1=P2=…=Pm=0。

3）求解式（11）關于Pm的偏導數：

4）式（21）不是解析解，NSTs 最優的切片定價需要通過迭代求解，迭代公式如下：

其中：t為迭代次 數為 第t次迭代 時NSTsm的切片定價；λk為迭代步長，與總迭代次數成反比。

4 仿真結果與分析

4.1 仿真設置

為驗證本文所提策略，對提出的資源分配優化策略性能進行仿真分析，使用NS2 和GT-ITM 工具構建多租戶網絡環境和接入服務切片實例，利用Python 進行結果分析。對比算法包括最大最小公平策略［21］、基于優先級的動態資源分配策略［22］和時延最小化資源分配策略［23］，在資源利用率、網絡收益和能耗減少率3 個方面進行對比驗證。其中，文獻［19］提出的最大最小公平算法首先滿足所有用戶的最低需求，再將剩余資源平均分配；文獻［20］提出的基于優先級的動態資源分配算法考慮用戶的需求和優先級，動態地進行資源分配；文獻［21］提出的時延最小化資源分配算法考慮切片的優先級并最小化切片時延。

仿真中模擬的網絡環境中包括2 個NSTs 和100 個內部接入用戶，網絡中最大的帶寬頻譜資源B=500，每個NSTs 租用的最大頻譜帶寬Wm=250。其他的仿真參數如表1 所示。

表1 仿真參數與參數值Table 1 Simulation parameters and parameter values

4.2 仿真結果

圖3 給出了網絡切片提供商NSTs 1 與NSTs 2 的切片定價的關系，兩條曲線上的點分別表示當前NSTs 對另一NSTs 的最佳響應定價策略。由圖3 可知，（1.4，1.8）是雙方定價的交點，也是博弈均衡點，在該點處NSTs 1 與NSTs 2 都沒有興趣改變定價策略使自己的收益降低，為雙方收益最大化的最佳定價組合。

圖3 NSTs 1 與NSTs 2 的切片定價關系Fig.3 Slice pricing relationship of NSTs 1 and NSTs 2

圖4 給出NSTs 的收益同其切片流行度之間的關系。由式（2）可知，切片流行度與流行度指數υ和平坦因子ω有關。從圖4 可以看出：當ω一定時，υ越大，切片越受歡迎，訪問概率越大，相應的NSTs 的收益越高；而當υ一定時，ω越小，流行切片的訪問概率越大，相應的NSTs 的收益越高；當υ、ω一定時，隨著迭代次數增加，NSTs 的收益值逐漸增加；當迭代次數為70 左右時，NSTs 的收益收斂到最大值，并且υ越大，ω越小，收斂越快。

圖4 NST 收益與迭代次數的關系Fig.4 The relationship of NSTs revenue and iterations numbers

圖5 給出不同策略下接入服務用戶的收益與迭代次數的關系。由圖5 可知，當迭代次數相同時，本文提出的基于博弈的資源分配策略中接入服務用戶收益值最大，隨著迭代次數的增加，接入服務用戶的收益值逐漸增大。基于優先級的動態分配策略僅考慮最大化切片的服務質量，未能有效保證用戶收益，而時延最小化資源分配策略考慮了切片服務時延并設置了切片偏好度，用戶收益相對更高。基于博弈的資源分配策略通過博弈加快了收斂，迭代次數為70 左右時收斂，收斂速度僅次于最大最小公平策略。

圖5 用戶收益與迭代次數的關系Fig.5 The relationship of user revenue and iteration numbers

圖6 給出不同策略下網絡中頻譜帶寬利用率與用戶接入服務切片請求到達率的關系，初始條件用戶接入相同，4 種策略資源利用率相同。由圖6 可知，隨著用戶切片請求到達率的增加，利用率逐漸增大，本文提出的基于博弈的資源分配策略能收斂到最大的資源利用率。基于優先級的動態資源分配策略通過維護切片的優先級和需求量，動態地為切片分配資源，比起時延最小化資源分配策略僅考慮計算和通信資源的按需分配策略，能到達更大的資源利用率。

圖6 資源利用率與請求到達率的關系Fig.6 The relationship of resource utilization and request arrival rate

基于博弈的資源分配策略的接入服務用戶收益值迭代70 次左右達到收斂，最大最小公平算法收斂最快，但資源利用率最低。

圖7 給出不同策略下系統的網絡能耗減少率與用戶請求率的關系。為對比需要，假設不同策略下用戶的請求模式相同，都為泊松分布，以此反映不同策略下的能耗情況。由圖7 可知，隨著請求到達率的增加，網絡的能耗減少率持續增加，本文提出的基于博弈的資源分配策略能達到最高的網絡能耗減少率。基于博弈的資源分配策略通過用戶和NSTs 間的博弈，實現了多租戶網絡中頻譜資源的更加合理的分配，相比于其他3 種策略，切片部署成本更低，并且資源利用率更高，實現了更高的網絡能耗減少率，能更好地響應綠色通信。

圖7 網絡能耗減少率與請求到達率的關系Fig.7 The relationship of network energy consumption reduction rate and request arrival rate

5 結束語

高效網絡切片的部署實現是推進5G 網絡發展的關鍵因素，其中網絡資源的分配優化是網絡切片的關鍵問題之一。針對多租戶網絡中NSTs 的接入服務切片頻譜資源分配問題，本文提出一種面向多租戶網絡資源分配的博弈優化策略。將NSTs 和用戶構建為多主多從的Stackelberg 博弈模型，引入切片流行度和服務命中率指標，將博弈方的傳統收益具體建模，并證明該博弈模型存在唯一的納什均衡。在此基礎上，提出一種分布式迭代策略求解NSTs 的最優切片定價以及用戶的最優吞吐量需求。仿真結果表明，本文策略能夠提高資源利用率和用戶滿意度，并降低切片部署能耗。本文對于5G 網絡切片的部署實現有重要意義，下一步將考慮端到端網絡切片的資源分配優化方案，利用強化學習實現方案的主動部署。