黎作鵬 王浩翔
摘? 要: 小型基站(Small?cell base stations,SBSs)被認(rèn)為是邊緣計(jì)算環(huán)境中重要的組成部分。但由于自身計(jì)算資源有限,當(dāng)計(jì)算工作負(fù)載過大時(shí),為用戶提供的服務(wù)質(zhì)量將面臨重大的挑戰(zhàn)。因此,針對小型基站間協(xié)同計(jì)算展開研究。首先,以最優(yōu)化小型基站的個(gè)人效用為目標(biāo),結(jié)合多主多從斯塔克伯格(stackelberg)博弈模型,提出一種可實(shí)現(xiàn)小型基站間協(xié)同計(jì)算的算法。然后,通過循環(huán)迭代的方式求解小型基站之間非合作博弈的納什均衡解。最后,通過Matlab進(jìn)行實(shí)驗(yàn),驗(yàn)證了該算法的可行性和有效性。
關(guān)鍵詞: 小型基站; 邊緣計(jì)算; 協(xié)同計(jì)算; 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)時(shí)代[1]的到來,數(shù)據(jù)呈現(xiàn)出爆炸性的增長,這使得傳統(tǒng)的集中式云計(jì)算模型在應(yīng)用服務(wù)實(shí)時(shí)性、用戶隱私保護(hù)和數(shù)據(jù)傳輸能耗等方面都出現(xiàn)了問題。在此背景下,一種新的在網(wǎng)絡(luò)邊緣執(zhí)行計(jì)算的模型,即邊緣計(jì)算隨之誕生。
小型基站(SBSs)被認(rèn)為是邊緣計(jì)算中關(guān)鍵的支撐設(shè)備,具有計(jì)算和存儲能力,可以作為云的替代品,為終端用戶提供任務(wù)卸載計(jì)算。但與云數(shù)據(jù)中心相比,SBS計(jì)算資源是有限的,依賴單個(gè)SBS會極大地限制邊緣計(jì)算的性能[2]。幸運(yùn)的是,下一代(5G)移動(dòng)網(wǎng)絡(luò)中SBSs的部署非常密集[3],這為鄰近的SBSs間實(shí)現(xiàn)協(xié)同計(jì)算提供了可能。
本文中的SBSs是由個(gè)人部署的,因此每個(gè)SBS無法獲得全局信息。本文結(jié)合Stackelberg博弈模型,提出一種以最優(yōu)化SBSs個(gè)人效用函數(shù)為目標(biāo)的SBSs間協(xié)同計(jì)算算法。在該算法中考慮了SBSs間的通信和計(jì)算的過程[4],將其產(chǎn)生的時(shí)延和能耗分別建模并歸一化為運(yùn)行開銷[5],同時(shí)為了SBS能夠更好地參與到邊緣計(jì)算協(xié)同當(dāng)中,引入了激勵(lì)機(jī)制。針對上述兩種開銷,過載的SBSs對任務(wù)進(jìn)行本地計(jì)算或協(xié)同計(jì)算的選擇[6]。最后通過循環(huán)迭代的方法求解非合作博弈的納什均衡。
1? 模型分析與算法實(shí)現(xiàn)
1.1? 網(wǎng)絡(luò)模型
本文對網(wǎng)絡(luò)場景做了如下假設(shè):在一定范圍內(nèi)密集部署了x個(gè)SBSs([SBSi∈{SBS1,SBS2,…,SBSx}]),由于設(shè)備都只具有有限的計(jì)算能力,所以本文假設(shè)[SBSi]在時(shí)隙t最大的卸載任務(wù)接收量(下轄終端用戶卸載的任務(wù))為[wmaxi],同時(shí)在時(shí)隙t終端用戶向[SBSi]卸載的總?cè)蝿?wù)量為[λi]。根據(jù)公式[αi?wmaxi-λi]對[SBSi]在時(shí)隙t的情況進(jìn)行分類。如果[αi<0],表示[SBSi]有空閑計(jì)算資源,可幫助其他有需求的SBSs進(jìn)行協(xié)同計(jì)算,本文稱其為資源供應(yīng)點(diǎn)(后簡稱為供應(yīng)點(diǎn)),將符合這種情況的SBSs設(shè)為集合[SBSS={SBSS1,SBSS2,…,SBSSm}]。如果[αi>0],表示[SBSi]需要其他SBSs來協(xié)助完成計(jì)算,本文稱其為資源請求點(diǎn)(簡稱為請求點(diǎn)),將符合的SBSs設(shè)為集合[SBSB={SBSB1,SBSB2,…SBSBn}]。每個(gè)SBS的狀態(tài)是呈現(xiàn)時(shí)空變化性的,但本文基于當(dāng)前時(shí)隙t內(nèi)各個(gè)SBS的負(fù)載狀態(tài)進(jìn)行分析。由于SBSs間是純分布式的,無集中式管理的,結(jié)合文獻(xiàn)[7]中多主多從Stackelberg博弈模型,本文假設(shè)“資源供應(yīng)點(diǎn)”為領(lǐng)導(dǎo)者,“資源請求點(diǎn)”為跟隨者。其中[SBSSj]的出價(jià)為[pj],所有供應(yīng)點(diǎn)的策略向量定義為[p=(p1,p2,…,pm)]。一個(gè)請求點(diǎn)可通過向多個(gè)不同的供應(yīng)點(diǎn)訂購一定量的計(jì)算資源,來彌補(bǔ)自身的不足。假定[dij]表示[SBSBi]當(dāng)前請求[SBSSj]協(xié)同處理的任務(wù)量,定義[di=(dij,d-ij)]為[SBSBi]向[SBSS]請求的協(xié)同計(jì)算總?cè)蝿?wù)量,其中[d-ij]表示[SBSBi]向[SBSSj]以外的其他供應(yīng)點(diǎn)請求協(xié)同計(jì)算的任務(wù)量。[d=(d1,d2,…,dn)]表示網(wǎng)絡(luò)中所有[SBSB]的請求協(xié)同計(jì)算的策略。為了便于計(jì)算,假設(shè)每個(gè)任務(wù)的數(shù)據(jù)為單位大小,所需計(jì)算周期為一個(gè)CPU周期。同時(shí)定義[αSj]為[SBSSj]的剩余可接收任務(wù)量,對于[SBSSj]幫助[SBSBi]協(xié)同完成的任務(wù)量[dij],則需要滿足[0≤dij≤αSj],同時(shí)對于[SBSSj]上所有請求協(xié)同計(jì)算的任務(wù)量,也需要滿足[i=1ndij≤αSj]。為了能夠更好地反映博弈中一個(gè)參與者對選擇策略的滿意程度,本文在上述研究背景下,建立了[SBSBi]和[SBSSj]的效用函數(shù)并進(jìn)行了分析。
1.2? 資源請求點(diǎn)效用函數(shù)
對于請求點(diǎn)而言,它們之間構(gòu)成了非合作博弈關(guān)系。同時(shí)由于隱私的原因,請求點(diǎn)之間相互獨(dú)立且不會互相告知彼此的信息。在此背景下,本文針對請求點(diǎn)中過載任務(wù)量的效用函數(shù)進(jìn)行了分析。該效用函數(shù)主要由三部分組成:協(xié)同計(jì)算開銷、本地計(jì)算開銷和激勵(lì)機(jī)制開銷。下面對這三部分進(jìn)行建模分析。
1.2.1? 協(xié)同計(jì)算
協(xié)同計(jì)算過程的開銷主要分為兩部分,一部分是將數(shù)據(jù)[dij]從[SBSBi]傳輸至[SBSSj]的傳輸時(shí)延和傳輸能耗,其公式分別為:
[tB,trij=1rij]? ? ? ? ? ?(1)
[eB,trij=pij1rij]? ? ? ? ? (2)
式中:[rij]為[SBSBi]與[SBSSj]之間的傳輸速率;[pij]為[SBSBi]向[SBSSj]傳輸時(shí)的功率。
另一部分是在[SBSSj]上的計(jì)算時(shí)延,本文根據(jù)M/M/1排隊(duì)系統(tǒng)對計(jì)算時(shí)延進(jìn)行建模,每個(gè)任務(wù)的平均計(jì)算延遲(包括任務(wù)等待時(shí)間和處理時(shí)間)公式如下:
[tS,lij=1fSj-ωSj]? ? ? ? ? (3)
式中,[ωSj]為[SBSSj]上的總?cè)蝿?wù)量,[ωSj=λSj+i=1ndij],[i=1ndij]為[SBSSj]終端卸載任務(wù)量與協(xié)同任務(wù)量之和。
因此,[SBSBi]請求協(xié)同計(jì)算時(shí)的開銷為:
[CB,tri=i=1n[dijeB,trij+υ(tB,trijdij+tS,lijωSj)]] (4)
式中,[υ]為延遲成本和能量成本的歸一化系數(shù)。
1.2.2? 激勵(lì)機(jī)制
SBSs通常由個(gè)人用戶(例如家庭/企業(yè)所有者)擁有和部署,因此如果沒有適當(dāng)?shù)募?lì)機(jī)制,SBSs將不愿意參與邊緣的協(xié)同計(jì)算過程。結(jié)合網(wǎng)絡(luò)模型中供應(yīng)點(diǎn)的出價(jià),可得當(dāng)[SBSBi]向[SBSSj]請求協(xié)同計(jì)算的任務(wù)量為[dij]時(shí),需要向[SBSSj]支付的價(jià)格為[sij=qijpj]。
因此,[SBSBi]向[SBSS]支付的總費(fèi)用為:
[SBi=j=1mdijpj]? ? ? ? (5)
1.2.3? 本地計(jì)算
在時(shí)隙t時(shí),可能會出現(xiàn)協(xié)同計(jì)算成本高于本地計(jì)算成本的情況,所以可能部分過載任務(wù)會選擇在本地進(jìn)行計(jì)算。針對[SBSBi]本地計(jì)算任務(wù)時(shí)的開銷進(jìn)行建模。首先利用M/M/1排隊(duì)系統(tǒng)對計(jì)算時(shí)延進(jìn)行建模,每個(gè)任務(wù)的平均計(jì)算延遲(包括任務(wù)等待時(shí)間和處理時(shí)間)為:
[tB,li=1fBi-ωBi]? ? ? ? ? (6)
式中,[ωBi]表示在[SBSBi]處理的工作負(fù)載大小,[ωBi=λBi-j=1mdij]。同時(shí)根據(jù)文獻(xiàn)[8]可知[SBSBi]處理每個(gè)任務(wù)的計(jì)算能耗與CPU速度的平方成正比,可以表示為:
[eB,li=κ(fBi)2]? ? ? ? ? (7)
式中,[κ]表示常量,取決于CPU架構(gòu)。
因此,在[SBSBi]上完成任務(wù)的計(jì)算開銷為:
[CB,li=βBi(eB,li+υtB,li)]? ? ?(8)
式中,[βBi]是過載任務(wù)量,[βBi=αBi-j=1mdij]。
1.2.4? 效用函數(shù)
根據(jù)上述三個(gè)模型,本節(jié)給出了請求點(diǎn)的效用函數(shù),假定存在請求點(diǎn)[SBSBi],其效用函數(shù)定義為[FBi(p,di,d-i)],可以表示為:
[FBi(p,di,d-i)=-(CB,tri+CB,li+SBi)] (9)
每個(gè)請求點(diǎn)根據(jù)當(dāng)前的價(jià)格策略[p],調(diào)整自身策略,最終實(shí)現(xiàn)效用函數(shù)[FBi]的最優(yōu)化,即[max{FBi(p*,di,d*-i)}],其中[p*]和[d*-i]表示博弈中的其他參與者都各自選擇了最優(yōu)的價(jià)格策略和協(xié)同計(jì)算策略。
1.3? 資源供應(yīng)點(diǎn)效用函數(shù)
本文中的供應(yīng)點(diǎn)效用函數(shù)只考慮了出售計(jì)算資源得到的收益,所以供應(yīng)點(diǎn)效用函數(shù)可以利用收益函數(shù)[Gj(pj,q)]來表示。定義[SBSSj]的收益函數(shù)為[Gj(pj,d)=Qjpj],其中[Qj=i=1ndij]表示請求點(diǎn)向[SBSSj]請求的協(xié)同計(jì)算任務(wù)總量。因?yàn)檎埱簏c(diǎn)的選擇會根據(jù)供應(yīng)點(diǎn)價(jià)格不同而產(chǎn)生變化,所以提供點(diǎn)的價(jià)格并不是越高越好,而是選擇使自身收益最大化的價(jià)格策略。假設(shè)[SBSSj]的最優(yōu)價(jià)格策略是[p*j],則其最大收益為[max{Gj(pj,p*-j,d)}],其中[p*-j]和[d*]表示博弈中其他參與者都選擇了使自身效用最優(yōu)的價(jià)格策略和協(xié)同計(jì)算策略。
1.4? 資源請求點(diǎn)非合作博弈的納什均衡點(diǎn)
納什均衡是非合作博弈問題的關(guān)鍵,同時(shí)也是非合作博弈的解。當(dāng)達(dá)到納什均衡后,非合作博弈中的每個(gè)參與者的效用函數(shù)都達(dá)到最大值,且參與者單方面改變自身的策略不會增加自身的收益。本節(jié)對納什均衡解的存在性進(jìn)行了證明。
定理1 職對于供應(yīng)點(diǎn)價(jià)格策略[p=(p1,p2,???,pm)]給定的情況下,請求點(diǎn)之間存在非合作博弈,并存在納什均衡點(diǎn)[d*-i],使所有請求點(diǎn)的效用函數(shù)最優(yōu)化,即[max{FBi(p*,di,d*-i)}]。
證明? 顯然,任意請求點(diǎn)[SBSBi]的任務(wù)協(xié)同計(jì)算策略[di]是歐幾里得空間中的有界閉集。此外,用戶的效用函數(shù)[FBi]在其策略空間上是連續(xù)的。對任意請求點(diǎn)[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],可見請求點(diǎn)的效用函數(shù)是凹函數(shù),確保了納什均衡的存在性[9]。
1.5? Stackelberg博弈問題的求解
由于SBS無法獲取全局信息,因此,本文采用了一種循環(huán)迭代的方法來求解Stackelberg博弈的納什均衡。假設(shè)在t 時(shí)供應(yīng)點(diǎn)的價(jià)格策略為p(t),請求點(diǎn)根據(jù)當(dāng)前價(jià)格調(diào)節(jié)協(xié)同計(jì)算策略,達(dá)到納什均衡。其中,協(xié)同計(jì)算任務(wù)量的變化率與請求點(diǎn)效用函數(shù)的梯度成正比。
[ddijdτ=dij~=?Fi(p,di,d-i)?dij]? ? ? (12)
式中,[τ]是時(shí)間變量。效用函數(shù)凹函數(shù)的特性保證了迭代算法能夠收斂到博弈的納什均衡點(diǎn)[7],因此,[SBSBi]協(xié)同計(jì)算任務(wù)量迭代方程可表示為:
[dij(τ+1)=dij(τ)+ξidij~]? ? (13)
式中,[ξi>0]表示請求點(diǎn)卸載任務(wù)調(diào)節(jié)步長。
在請求點(diǎn)之間達(dá)到納什均衡后,供應(yīng)點(diǎn)根據(jù)各請求點(diǎn)的任務(wù)協(xié)同計(jì)算策略來調(diào)整自己的出價(jià)。供應(yīng)點(diǎn)的價(jià)格變化率可通過其邊際效用來表示,因此對任意資源供應(yīng)點(diǎn)[SBSsj]的價(jià)格迭代方程為:
[pj(t+1)=pj(t)+ψj?Gj(p(t),d(t))?pj(t)] (14)
式中,[ψj>0]表示供應(yīng)點(diǎn)價(jià)格策略調(diào)節(jié)步長。
資源供應(yīng)點(diǎn)的邊際效用可以通過一個(gè)小的變化量[ε](例如[ε=10-4])來計(jì)算其對效用產(chǎn)生的影響[8]。因此,邊際收益可以粗略的計(jì)算為:
[?Gj(p(t),d(t))?pj(t)≈[Gj(…,pj(t)+ε,…)-? ? ? ? ? ? ? ? ? ? ? ? ? ? Gj(…,pj(t)-ε,…)](2ε)-1] (15)
在請求點(diǎn)達(dá)到納什均衡過程中,供應(yīng)點(diǎn)保持價(jià)格不變,觀察并等候請求點(diǎn)的任務(wù)協(xié)同計(jì)算策略達(dá)到穩(wěn)定。這一等候時(shí)間即是供應(yīng)點(diǎn)一次迭代的間隔時(shí)間[Δt],[Δt]也是所有請求點(diǎn)迭代并達(dá)到納什均衡的時(shí)間間隔。所以供應(yīng)點(diǎn)根據(jù)式(14)和式(15)在多個(gè)[Δt]內(nèi)進(jìn)行價(jià)格迭代。每個(gè)[Δt]中多個(gè)請求點(diǎn)根據(jù)式(12)和式(13)在時(shí)間間隔[Δτ]中進(jìn)行迭代。對整個(gè)網(wǎng)絡(luò)而言,迭代的最終結(jié)果是請求點(diǎn)和供應(yīng)點(diǎn)得到了各自最優(yōu)的協(xié)同計(jì)算策略[d*]和價(jià)格策略[p*],算法的時(shí)間序列如圖1所示。在上述的迭代過程分析的基礎(chǔ)上,給出實(shí)現(xiàn)協(xié)同計(jì)算的算法流程圖,如圖2所示。
2? 實(shí)驗(yàn)仿真與分析
本文選擇了Matlab 2014a仿真平臺進(jìn)行實(shí)驗(yàn),輔助以O(shè)rigin 9.0和Office 2010繪圖。
2.1? 參數(shù)設(shè)定
本節(jié)對仿真系統(tǒng)的參數(shù)進(jìn)行了設(shè)置[9?10],具體情況如表1所示。假設(shè)整個(gè)無線網(wǎng)絡(luò)環(huán)境為100 m×100 m×100 m,仿真環(huán)境中部署了10個(gè)同構(gòu)的小型基站,每個(gè)小型基站接收到的終端用戶卸載任務(wù)到達(dá)速率(單位:個(gè)/s)為[λi∈(0,300)]。
2.2? 結(jié)果分析
本次實(shí)驗(yàn)從資源供應(yīng)點(diǎn)和資源請求點(diǎn)兩個(gè)集合中分別選取一個(gè)小型基站進(jìn)行分析,并將其迭代運(yùn)行情況進(jìn)行繪圖,如圖3、圖4所示。首先由圖3可知,在迭代的過程中,資源請求點(diǎn)的效用函數(shù)整體呈現(xiàn)增長的趨勢,在趨向收斂的過程中略微有所減小,但達(dá)到納什均衡點(diǎn)后,收益最終趨于穩(wěn)定。隨著本地計(jì)算開銷的減少,協(xié)同計(jì)算開銷和激勵(lì)機(jī)制的開銷都在增長,但在達(dá)到納什均衡之后趨于平穩(wěn)。這是由于在達(dá)到納什均衡后,更改任何策略都無法使效用函數(shù)的值更優(yōu),因此不再改變?nèi)蝿?wù)協(xié)同計(jì)算策略。圖4中,從曲線上可以看出資源供應(yīng)點(diǎn)的效用函數(shù)是基于價(jià)格的凹函數(shù)。在價(jià)格從0.1逐漸增大的過程中,資源供應(yīng)點(diǎn)的效用函數(shù)隨之先增大后減小,在0.37左右達(dá)到最大值。這是由于在競爭的過程中,提高價(jià)格可以提升自身的效用函數(shù),但是如果價(jià)格過高,就會失去競爭力,資源請求點(diǎn)就會選擇其他的資源提供點(diǎn)來進(jìn)行協(xié)同計(jì)算。
3? 結(jié)? 語
本文針對邊緣環(huán)境中的小型基站間的協(xié)同計(jì)算進(jìn)行研究,在同時(shí)考慮了請求點(diǎn)和供應(yīng)點(diǎn)的效用函數(shù)最優(yōu)的情況下,通過Stackelberg博弈分析了兩者的交互關(guān)系,提出了一種邊緣協(xié)同計(jì)算的方法。并通過仿真實(shí)驗(yàn)證明循環(huán)迭代的方法可使其達(dá)到納什均衡,可以使每個(gè)小型基站的效用函數(shù)最大化,同時(shí)也提供了網(wǎng)絡(luò)的資源利用率。本文下一步的工作是對復(fù)雜任務(wù)的情況進(jìn)行分析,另外在計(jì)算資源供應(yīng)點(diǎn)效用時(shí)還需對其運(yùn)行開銷進(jìn)行考慮。
參考文獻(xiàn)
[1] 施巍松,孫輝,曹杰,等.邊緣計(jì)算:萬物互聯(lián)時(shí)代新型計(jì)算模型[J].計(jì)算機(jī)研究與發(fā)展,2017,54(5):907?924.
[2] 周悅芝,張迪.近端云計(jì)算:后云計(jì)算時(shí)代的機(jī)遇與挑戰(zhàn)[J].計(jì)算機(jī)學(xué)報(bào),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] 孟陳融.面向邊緣計(jì)算的數(shù)據(jù)中心服務(wù)資源調(diào)度機(jī)制研究[D].北京:北京郵電大學(xué),2018.
[6] 李波,黃鑫,牛力,等.車載邊緣計(jì)算環(huán)境中的任務(wù)卸載決策和優(yōu)化[J].微電子學(xué)與計(jì)算機(jī),2019,36(2):78?82.
[7] 田厚平,郭亞軍,王學(xué)軍.一類基于進(jìn)化博弈的多主多從Stackelberg對策算法[J].系統(tǒng)工程學(xué)報(bào),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博弈的分布式定價(jià)和資源分配算法[J].通信學(xué)報(bào),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.