黎作鵬 王浩翔

摘? 要： 小型基站（Small?cell base stations，SBSs）被認(rèn)為是邊緣計算環(huán)境中重要的組成部分。但由于自身計算資源有限，當(dāng)計算工作負(fù)載過大時，為用戶提供的服務(wù)質(zhì)量將面臨重大的挑戰(zhàn)。因此，針對小型基站間協(xié)同計算展開研究。首先，以最優(yōu)化小型基站的個人效用為目標(biāo)，結(jié)合多主多從斯塔克伯格（stackelberg）博弈模型，提出一種可實現(xiàn)小型基站間協(xié)同計算的算法。然后，通過循環(huán)迭代的方式求解小型基站之間非合作博弈的納什均衡解。最后，通過Matlab進行實驗，驗證了該算法的可行性和有效性。

關(guān)鍵詞： 小型基站; 邊緣計算; 協(xié)同計算; Stackelberg博弈; 納什均衡; 仿真分析

中圖分類號： TN929?34? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）14?0079?04

Research on edge cooperative computing based on Stackelberg game

LI Zuopeng1，2， WANG Haoxiang1，2

（1. School of Information and Electrical Engineering， Hebei University of Engineering， Handan 056038， China;

2. Hebei Key Laboratory of Security Information Perception and Processing， Hebei University of Engineering， Handan 056038， China）

Abstract：The small?cell base stations （SBSs） are considered as an important part of the edge computing environment. Since SBSs′ own computing resources are limited， the service quality provided to users will be faced with major challenges when the computing workload is too large. Therefore， the collaborative computing between SBSs is studied. With the goal of optimizing the personal utility of SBSs， an algorithm to realize the collaborative computing between SBSs is proposed in combination with the Stackelberg game model with multi?master and multi?slave. The Nash equilibrium solution of non?cooperative game between SBSs is solved by means of the loop iteration. The feasibility and effectiveness of the algorithm are verified by the experiments with Matlab.

Keywords： small base station; edge computing; collaborative computing; Stackelberg game; nash equilibrium; simulation analysis

0? 引? 言

隨著萬物互聯(lián)時代[1]的到來，數(shù)據(jù)呈現(xiàn)出爆炸性的增長，這使得傳統(tǒng)的集中式云計算模型在應(yīng)用服務(wù)實時性、用戶隱私保護和數(shù)據(jù)傳輸能耗等方面都出現(xiàn)了問題。在此背景下，一種新的在網(wǎng)絡(luò)邊緣執(zhí)行計算的模型，即邊緣計算隨之誕生。

小型基站（SBSs）被認(rèn)為是邊緣計算中關(guān)鍵的支撐設(shè)備，具有計算和存儲能力，可以作為云的替代品，為終端用戶提供任務(wù)卸載計算。但與云數(shù)據(jù)中心相比，SBS計算資源是有限的，依賴單個SBS會極大地限制邊緣計算的性能[2]。幸運的是，下一代（5G）移動網(wǎng)絡(luò)中SBSs的部署非常密集[3]，這為鄰近的SBSs間實現(xiàn)協(xié)同計算提供了可能。

本文中的SBSs是由個人部署的，因此每個SBS無法獲得全局信息。本文結(jié)合Stackelberg博弈模型，提出一種以最優(yōu)化SBSs個人效用函數(shù)為目標(biāo)的SBSs間協(xié)同計算算法。在該算法中考慮了SBSs間的通信和計算的過程[4]，將其產(chǎn)生的時延和能耗分別建模并歸一化為運行開銷[5]，同時為了SBS能夠更好地參與到邊緣計算協(xié)同當(dāng)中，引入了激勵機制。針對上述兩種開銷，過載的SBSs對任務(wù)進行本地計算或協(xié)同計算的選擇[6]。最后通過循環(huán)迭代的方法求解非合作博弈的納什均衡。

1? 模型分析與算法實現(xiàn)

1.1? 網(wǎng)絡(luò)模型

本文對網(wǎng)絡(luò)場景做了如下假設(shè)：在一定范圍內(nèi)密集部署了x個SBSs（[SBSi∈{SBS1，SBS2，…，SBSx}]），由于設(shè)備都只具有有限的計算能力，所以本文假設(shè)[SBSi]在時隙t最大的卸載任務(wù)接收量（下轄終端用戶卸載的任務(wù)）為[wmaxi]，同時在時隙t終端用戶向[SBSi]卸載的總?cè)蝿?wù)量為[λi]。根據(jù)公式[αi?wmaxi-λi]對[SBSi]在時隙t的情況進行分類。如果[αi<0]，表示[SBSi]有空閑計算資源，可幫助其他有需求的SBSs進行協(xié)同計算，本文稱其為資源供應(yīng)點（后簡稱為供應(yīng)點），將符合這種情況的SBSs設(shè)為集合[SBSS={SBSS1，SBSS2，…，SBSSm}]。如果[αi>0]，表示[SBSi]需要其他SBSs來協(xié)助完成計算，本文稱其為資源請求點（簡稱為請求點），將符合的SBSs設(shè)為集合[SBSB={SBSB1，SBSB2，…SBSBn}]。每個SBS的狀態(tài)是呈現(xiàn)時空變化性的，但本文基于當(dāng)前時隙t內(nèi)各個SBS的負(fù)載狀態(tài)進行分析。由于SBSs間是純分布式的，無集中式管理的，結(jié)合文獻(xiàn)[7]中多主多從Stackelberg博弈模型，本文假設(shè)“資源供應(yīng)點”為領(lǐng)導(dǎo)者，“資源請求點”為跟隨者。其中[SBSSj]的出價為[pj]，所有供應(yīng)點的策略向量定義為[p=（p1，p2，…，pm）]。一個請求點可通過向多個不同的供應(yīng)點訂購一定量的計算資源，來彌補自身的不足。假定[dij]表示[SBSBi]當(dāng)前請求[SBSSj]協(xié)同處理的任務(wù)量，定義[di=（dij，d-ij）]為[SBSBi]向[SBSS]請求的協(xié)同計算總?cè)蝿?wù)量，其中[d-ij]表示[SBSBi]向[SBSSj]以外的其他供應(yīng)點請求協(xié)同計算的任務(wù)量。[d=（d1，d2，…，dn）]表示網(wǎng)絡(luò)中所有[SBSB]的請求協(xié)同計算的策略。為了便于計算，假設(shè)每個任務(wù)的數(shù)據(jù)為單位大小，所需計算周期為一個CPU周期。同時定義[αSj]為[SBSSj]的剩余可接收任務(wù)量，對于[SBSSj]幫助[SBSBi]協(xié)同完成的任務(wù)量[dij]，則需要滿足[0≤dij≤αSj]，同時對于[SBSSj]上所有請求協(xié)同計算的任務(wù)量，也需要滿足[i=1ndij≤αSj]。為了能夠更好地反映博弈中一個參與者對選擇策略的滿意程度，本文在上述研究背景下，建立了[SBSBi]和[SBSSj]的效用函數(shù)并進行了分析。

1.2? 資源請求點效用函數(shù)

對于請求點而言，它們之間構(gòu)成了非合作博弈關(guān)系。同時由于隱私的原因，請求點之間相互獨立且不會互相告知彼此的信息。在此背景下，本文針對請求點中過載任務(wù)量的效用函數(shù)進行了分析。該效用函數(shù)主要由三部分組成：協(xié)同計算開銷、本地計算開銷和激勵機制開銷。下面對這三部分進行建模分析。

1.2.1? 協(xié)同計算

協(xié)同計算過程的開銷主要分為兩部分，一部分是將數(shù)據(jù)[dij]從[SBSBi]傳輸至[SBSSj]的傳輸時延和傳輸能耗，其公式分別為：

[tB，trij=1rij]? ? ? ? ? ?（1）

[eB，trij=pij1rij]? ? ? ? ? （2）

式中：[rij]為[SBSBi]與[SBSSj]之間的傳輸速率;[pij]為[SBSBi]向[SBSSj]傳輸時的功率。

另一部分是在[SBSSj]上的計算時延，本文根據(jù)M/M/1排隊系統(tǒng)對計算時延進行建模，每個任務(wù)的平均計算延遲（包括任務(wù)等待時間和處理時間）公式如下：

[tS，lij=1fSj-ωSj]? ? ? ? ? （3）

式中，[ωSj]為[SBSSj]上的總?cè)蝿?wù)量，[ωSj=λSj+i=1ndij]，[i=1ndij]為[SBSSj]終端卸載任務(wù)量與協(xié)同任務(wù)量之和。

因此，[SBSBi]請求協(xié)同計算時的開銷為：

[CB，tri=i=1n[dijeB，trij+υ（tB，trijdij+tS，lijωSj）]] （4）

式中，[υ]為延遲成本和能量成本的歸一化系數(shù)。

1.2.2? 激勵機制

SBSs通常由個人用戶（例如家庭/企業(yè)所有者）擁有和部署，因此如果沒有適當(dāng)?shù)募顧C制，SBSs將不愿意參與邊緣的協(xié)同計算過程。結(jié)合網(wǎng)絡(luò)模型中供應(yīng)點的出價，可得當(dāng)[SBSBi]向[SBSSj]請求協(xié)同計算的任務(wù)量為[dij]時，需要向[SBSSj]支付的價格為[sij=qijpj]。

因此，[SBSBi]向[SBSS]支付的總費用為：

[SBi=j=1mdijpj]? ? ? ? （5）

1.2.3? 本地計算

在時隙t時，可能會出現(xiàn)協(xié)同計算成本高于本地計算成本的情況，所以可能部分過載任務(wù)會選擇在本地進行計算。針對[SBSBi]本地計算任務(wù)時的開銷進行建模。首先利用M/M/1排隊系統(tǒng)對計算時延進行建模，每個任務(wù)的平均計算延遲（包括任務(wù)等待時間和處理時間）為：

[tB，li=1fBi-ωBi]? ? ? ? ? （6）

式中，[ωBi]表示在[SBSBi]處理的工作負(fù)載大小，[ωBi=λBi-j=1mdij]。同時根據(jù)文獻(xiàn)[8]可知[SBSBi]處理每個任務(wù)的計算能耗與CPU速度的平方成正比，可以表示為：

[eB，li=κ（fBi）2]? ? ? ? ? （7）

式中，[κ]表示常量，取決于CPU架構(gòu)。

因此，在[SBSBi]上完成任務(wù)的計算開銷為：

[CB，li=βBi（eB，li+υtB，li）]? ? ?（8）

式中，[βBi]是過載任務(wù)量，[βBi=αBi-j=1mdij]。

1.2.4? 效用函數(shù)

根據(jù)上述三個模型，本節(jié)給出了請求點的效用函數(shù)，假定存在請求點[SBSBi]，其效用函數(shù)定義為[FBi（p，di，d-i）]，可以表示為：

[FBi（p，di，d-i）=-（CB，tri+CB，li+SBi）] （9）

每個請求點根據(jù)當(dāng)前的價格策略[p]，調(diào)整自身策略，最終實現(xiàn)效用函數(shù)[FBi]的最優(yōu)化，即[max{FBi（p*，di，d*-i）}]，其中[p*]和[d*-i]表示博弈中的其他參與者都各自選擇了最優(yōu)的價格策略和協(xié)同計算策略。

1.3? 資源供應(yīng)點效用函數(shù)

本文中的供應(yīng)點效用函數(shù)只考慮了出售計算資源得到的收益，所以供應(yīng)點效用函數(shù)可以利用收益函數(shù)[Gj（pj，q）]來表示。定義[SBSSj]的收益函數(shù)為[Gj（pj，d）=Qjpj]，其中[Qj=i=1ndij]表示請求點向[SBSSj]請求的協(xié)同計算任務(wù)總量。因為請求點的選擇會根據(jù)供應(yīng)點價格不同而產(chǎn)生變化，所以提供點的價格并不是越高越好，而是選擇使自身收益最大化的價格策略。假設(shè)[SBSSj]的最優(yōu)價格策略是[p*j]，則其最大收益為[max{Gj（pj，p*-j，d）}]，其中[p*-j]和[d*]表示博弈中其他參與者都選擇了使自身效用最優(yōu)的價格策略和協(xié)同計算策略。

1.4? 資源請求點非合作博弈的納什均衡點

納什均衡是非合作博弈問題的關(guān)鍵，同時也是非合作博弈的解。當(dāng)達(dá)到納什均衡后，非合作博弈中的每個參與者的效用函數(shù)都達(dá)到最大值，且參與者單方面改變自身的策略不會增加自身的收益。本節(jié)對納什均衡解的存在性進行了證明。

定理1 職對于供應(yīng)點價格策略[p=（p1，p2，???，pm）]給定的情況下，請求點之間存在非合作博弈，并存在納什均衡點[d*-i]，使所有請求點的效用函數(shù)最優(yōu)化，即[max{FBi（p*，di，d*-i）}]。

證明? 顯然，任意請求點[SBSBi]的任務(wù)協(xié)同計算策略[di]是歐幾里得空間中的有界閉集。此外，用戶的效用函數(shù)[FBi]在其策略空間上是連續(xù)的。對任意請求點[SBSBi]的效用函數(shù)求一階偏導(dǎo)得：

[fi（dij）=?FBi（p，di，d-i）?dij? ? ? =-（eB，trij-eB，trij+υtB，trij+pj）+υfSj（fSJ-ωSj）2-? ? ? 1（fBi-ωBi）2-βBi1（fBi-ωBi）2] （10）

對[SBSBi]的效用函數(shù)求二階偏導(dǎo)得：[?F2i（p，di，d-i）?d2ij=-2υfSj（fSj-ωSj）3+? ? ? ? ? ? ? ? ? ? ? ? ? ?1（fBi-ωBi）2+βBi（fBi-ωBi）3<0] （11）

式中，[βBi>0，fSj>0，υ>0]，可見請求點的效用函數(shù)是凹函數(shù)，確保了納什均衡的存在性[9]。

1.5? Stackelberg博弈問題的求解

由于SBS無法獲取全局信息，因此，本文采用了一種循環(huán)迭代的方法來求解Stackelberg博弈的納什均衡。假設(shè)在t 時供應(yīng)點的價格策略為p（t），請求點根據(jù)當(dāng)前價格調(diào)節(jié)協(xié)同計算策略，達(dá)到納什均衡。其中，協(xié)同計算任務(wù)量的變化率與請求點效用函數(shù)的梯度成正比。

[ddijdτ=dij～=?Fi（p，di，d-i）?dij]? ? ? （12）

式中，[τ]是時間變量。效用函數(shù)凹函數(shù)的特性保證了迭代算法能夠收斂到博弈的納什均衡點[7]，因此，[SBSBi]協(xié)同計算任務(wù)量迭代方程可表示為：

[dij（τ+1）=dij（τ）+ξidij～]? ? （13）

式中，[ξi>0]表示請求點卸載任務(wù)調(diào)節(jié)步長。

在請求點之間達(dá)到納什均衡后，供應(yīng)點根據(jù)各請求點的任務(wù)協(xié)同計算策略來調(diào)整自己的出價。供應(yīng)點的價格變化率可通過其邊際效用來表示，因此對任意資源供應(yīng)點[SBSsj]的價格迭代方程為：

[pj（t+1）=pj（t）+ψj?Gj（p（t），d（t））?pj（t）] （14）

式中，[ψj>0]表示供應(yīng)點價格策略調(diào)節(jié)步長。

資源供應(yīng)點的邊際效用可以通過一個小的變化量[ε]（例如[ε=10-4]）來計算其對效用產(chǎn)生的影響[8]。因此，邊際收益可以粗略的計算為：

[?Gj（p（t），d（t））?pj（t）≈[Gj（…，pj（t）+ε，…）-? ? ? ? ? ? ? ? ? ? ? ? ? ? Gj（…，pj（t）-ε，…）]（2ε）-1] （15）

在請求點達(dá)到納什均衡過程中，供應(yīng)點保持價格不變，觀察并等候請求點的任務(wù)協(xié)同計算策略達(dá)到穩(wěn)定。這一等候時間即是供應(yīng)點一次迭代的間隔時間[Δt]，[Δt]也是所有請求點迭代并達(dá)到納什均衡的時間間隔。所以供應(yīng)點根據(jù)式（14）和式（15）在多個[Δt]內(nèi)進行價格迭代。每個[Δt]中多個請求點根據(jù)式（12）和式（13）在時間間隔[Δτ]中進行迭代。對整個網(wǎng)絡(luò)而言，迭代的最終結(jié)果是請求點和供應(yīng)點得到了各自最優(yōu)的協(xié)同計算策略[d*]和價格策略[p*]，算法的時間序列如圖1所示。在上述的迭代過程分析的基礎(chǔ)上，給出實現(xiàn)協(xié)同計算的算法流程圖，如圖2所示。

2? 實驗仿真與分析

本文選擇了Matlab 2014a仿真平臺進行實驗，輔助以O(shè)rigin 9.0和Office 2010繪圖。

2.1? 參數(shù)設(shè)定

本節(jié)對仿真系統(tǒng)的參數(shù)進行了設(shè)置[9?10]，具體情況如表1所示。假設(shè)整個無線網(wǎng)絡(luò)環(huán)境為100 m×100 m×100 m，仿真環(huán)境中部署了10個同構(gòu)的小型基站，每個小型基站接收到的終端用戶卸載任務(wù)到達(dá)速率（單位：個/s）為[λi∈（0，300）]。

2.2? 結(jié)果分析

本次實驗從資源供應(yīng)點和資源請求點兩個集合中分別選取一個小型基站進行分析，并將其迭代運行情況進行繪圖，如圖3、圖4所示。首先由圖3可知，在迭代的過程中，資源請求點的效用函數(shù)整體呈現(xiàn)增長的趨勢，在趨向收斂的過程中略微有所減小，但達(dá)到納什均衡點后，收益最終趨于穩(wěn)定。隨著本地計算開銷的減少，協(xié)同計算開銷和激勵機制的開銷都在增長，但在達(dá)到納什均衡之后趨于平穩(wěn)。這是由于在達(dá)到納什均衡后，更改任何策略都無法使效用函數(shù)的值更優(yōu)，因此不再改變?nèi)蝿?wù)協(xié)同計算策略。圖4中，從曲線上可以看出資源供應(yīng)點的效用函數(shù)是基于價格的凹函數(shù)。在價格從0.1逐漸增大的過程中，資源供應(yīng)點的效用函數(shù)隨之先增大后減小，在0.37左右達(dá)到最大值。這是由于在競爭的過程中，提高價格可以提升自身的效用函數(shù)，但是如果價格過高，就會失去競爭力，資源請求點就會選擇其他的資源提供點來進行協(xié)同計算。

3? 結(jié)? 語

本文針對邊緣環(huán)境中的小型基站間的協(xié)同計算進行研究，在同時考慮了請求點和供應(yīng)點的效用函數(shù)最優(yōu)的情況下，通過Stackelberg博弈分析了兩者的交互關(guān)系，提出了一種邊緣協(xié)同計算的方法。并通過仿真實驗證明循環(huán)迭代的方法可使其達(dá)到納什均衡，可以使每個小型基站的效用函數(shù)最大化，同時也提供了網(wǎng)絡(luò)的資源利用率。本文下一步的工作是對復(fù)雜任務(wù)的情況進行分析，另外在計算資源供應(yīng)點效用時還需對其運行開銷進行考慮。

參考文獻(xiàn)

[1] 施巍松，孫輝，曹杰，等.邊緣計算：萬物互聯(lián)時代新型計算模型[J].計算機研究與發(fā)展，2017，54（5）：907?924.

[2] 周悅芝，張迪.近端云計算：后云計算時代的機遇與挑戰(zhàn)[J].計算機學(xué)報，2018，41（25）：1?24.

[3] ANDREWS J G， BUZZI S， CHOI W， et al. What will 5g be？ [J]. IEEE journal on selected areas in communications， 2014， 32（6）： 1065?1082.

[4] ZHANG H Q， XIAO Y， BU S R， et al. Computing resource allocation in three?tier IoT fog networks： a joint optimization approach combining Stackelberg game and matching [J]. IEEE Internet of Things journal， 2017， 4（5）： 1204?1215.

[5] 孟陳融.面向邊緣計算的數(shù)據(jù)中心服務(wù)資源調(diào)度機制研究[D].北京：北京郵電大學(xué)，2018.

[6] 李波，黃鑫，牛力，等.車載邊緣計算環(huán)境中的任務(wù)卸載決策和優(yōu)化[J].微電子學(xué)與計算機，2019，36（2）：78?82.

[7] 田厚平，郭亞軍，王學(xué)軍.一類基于進化博弈的多主多從Stackelberg對策算法[J].系統(tǒng)工程學(xué)報，2005（3）：303?307.

[8] CHEN L X， XU J. Socially trusted collaborative edge computing in ultra dense networks [C]// Proceedings of the Second ACM/IEEE Symposium on Edge Computing. San Jose： ACM， 2017： 9.

[9] 姜永，陳山枝，胡博.異構(gòu)無線網(wǎng)絡(luò)中基于Stackelberg博弈的分布式定價和資源分配算法[J].通信學(xué)報，2013，34（1）：61?68.

[10] CHEN L X， ZHOU S， XU J X. Computation peer offloading for energy?constrained mobile edge computing in small?cell networks [J]. IEEE/ACM transactions on networking， 2018， 26（4）： 1619?1632.