余 翔,石雪琴,劉一勛

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 概述

隨著互聯(lián)網(wǎng)的發(fā)展,多種多樣的新型數(shù)據(jù)業(yè)務(wù)極大地豐富了用戶日常移動(dòng)應(yīng)用的體驗(yàn)[1],如人臉識(shí)別、交互式游戲和虛擬現(xiàn)實(shí)技術(shù)等[2]。但由于移動(dòng)設(shè)備(Mobile Devices,MD)的資源有限,無(wú)法頻繁處理占用資源較高的業(yè)務(wù)[3-4]。而移動(dòng)邊緣計(jì)算(Mobile-Edge Computing,MEC)的出現(xiàn)彌補(bǔ)了這些能力受限設(shè)備的不足,通過(guò)將密集型計(jì)算任務(wù)卸載到邊緣服務(wù)器可以為設(shè)備擴(kuò)展容量和降低能耗[5-6]。計(jì)算卸載是MEC的關(guān)鍵技術(shù)之一,也是MEC系統(tǒng)實(shí)現(xiàn)終端業(yè)務(wù)實(shí)時(shí)化處理的重要手段[7],實(shí)驗(yàn)結(jié)果表明,將任務(wù)卸載到MEC上,可以減少高達(dá)88%的時(shí)延和93%的能耗[8]。

文獻(xiàn)[9]研究了移動(dòng)設(shè)備中具有能量收集功能的MEC系統(tǒng),并提出了基于Lyapunov優(yōu)化的動(dòng)態(tài)計(jì)算卸載算法。文獻(xiàn)[10]使用馬爾可夫決策過(guò)程執(zhí)行隨機(jī)計(jì)算任務(wù)調(diào)度,并通過(guò)一維搜索算法得到了最佳的卸載決策。文獻(xiàn)[11]提出分段凸優(yōu)化方法,該方法通過(guò)次梯度優(yōu)化方法有效地解決執(zhí)行延遲最小問(wèn)題。文獻(xiàn)[12]研究了云和邊緣云之間的協(xié)作,將聯(lián)合通信和計(jì)算資源分配問(wèn)題轉(zhuǎn)化為等效的凸優(yōu)化問(wèn)題,并制定了資源分配策略。上述文獻(xiàn)專(zhuān)注于最小化時(shí)延的研究,然而能耗對(duì)于用戶的體驗(yàn)質(zhì)量也是至關(guān)重要的。文獻(xiàn)[13]設(shè)計(jì)了一種前、后向鏈路聯(lián)合優(yōu)化的計(jì)算卸載策略,通過(guò)改進(jìn)的人工魚(yú)群算法對(duì)時(shí)延和能耗進(jìn)行優(yōu)化。文獻(xiàn)[14]將計(jì)算任務(wù)表示為約束馬爾可夫決策過(guò)程,該過(guò)程基于應(yīng)用特性和無(wú)線電環(huán)境統(tǒng)計(jì)行為的先驗(yàn)知識(shí)預(yù)先計(jì)算的離線策略。文獻(xiàn)[15]考慮了一種基于時(shí)分多址的多用戶邊緣計(jì)算卸載系統(tǒng),使用次優(yōu)分配算法來(lái)優(yōu)化通信和計(jì)算資源。文獻(xiàn)[16]提出節(jié)點(diǎn)與云之間協(xié)同卸載,應(yīng)用拉格朗日乘數(shù)法在KKT約束條件下獲得最優(yōu)值。

在計(jì)算卸載過(guò)程中,傳輸數(shù)據(jù)產(chǎn)生的高能耗和高時(shí)延大幅降低了用戶的體驗(yàn)質(zhì)量。而傳輸功率則是影響卸載傳輸時(shí)延和能耗的主要因素,因此本文采用二分搜索法求得用戶最佳傳輸功率以提高用戶的體驗(yàn)質(zhì)量。將多用戶計(jì)算卸載決策問(wèn)題制定為非合作博弈,證明集中式優(yōu)化多用戶計(jì)算卸載解決方案是NP-hard,并且將最小化計(jì)算開(kāi)銷(xiāo)問(wèn)題制定為混合整數(shù)非線性規(guī)劃(MINLP)問(wèn)題,提出基于博弈論的功率優(yōu)化卸載算法,從而降低系統(tǒng)成本和提高用戶體驗(yàn)質(zhì)量。

1 系統(tǒng)模型

圖1 移動(dòng)邊緣計(jì)算環(huán)境模型

1.1 通信模型

本文將A={a1,a2,…,aN}表示所有MD的決策集合,其中,an=0為本地計(jì)算,an>0為計(jì)算卸載。與本地計(jì)算相比,計(jì)算卸載降低了時(shí)延和能耗,但在傳輸數(shù)據(jù)時(shí)花費(fèi)了額外的時(shí)間和能耗,即通信時(shí)延和能耗。根據(jù)Shannon-Hartley,將通信模型定義為:

(1)

其中,ω表示信道帶寬,pn表示用戶n的傳輸功率,hn,m表示移動(dòng)用戶n和基站之間的信道增益,σ2表示高斯白噪聲功率,pihi,m表示其他用戶i與用戶n選擇同一信道進(jìn)行計(jì)算卸載產(chǎn)生的干擾。

1.2 計(jì)算模型

本文用Θn?(dn,cn)表示MD的計(jì)算任務(wù),dn表示輸入數(shù)據(jù)的大小,cn表示完成計(jì)算任務(wù)Θn所需的CPU周期總數(shù)。

1.2.1 本地計(jì)算

(2)

MD的本地計(jì)算能耗為:

(3)

其中,η表示每個(gè)CPU周期消耗能量的系數(shù),設(shè)置η=10-26是根據(jù)文獻(xiàn)[18]中的方法獲得。

1.2.2 邊緣計(jì)算

(4)

(5)

對(duì)于許多應(yīng)用程序而言,計(jì)算結(jié)果的大小通常遠(yuǎn)小于輸入數(shù)據(jù)的大小,因此忽略了服務(wù)器將計(jì)算結(jié)果發(fā)送給設(shè)備的開(kāi)銷(xiāo)[19]。根據(jù)上面分析,將計(jì)算模型定義為:

(6)

2 基于博弈論的功率優(yōu)化卸載算法

2.1 問(wèn)題描述

博弈論作為一種有效的方法被廣泛應(yīng)用于解決目標(biāo)約束的多博弈參與者之間的決策問(wèn)題[20]。在多個(gè)參與者的博弈中,每一步都有一個(gè)理性的參與者對(duì)前一步中其他參與者的行為做出反應(yīng),并進(jìn)行局部最優(yōu)決策。經(jīng)過(guò)若干步驟后,這些參與者自組織形成一個(gè)相互滿意的解決方案。

本文提出基于博弈論的功率優(yōu)化卸載方案,采用博弈論解決多用戶卸載決策問(wèn)題,結(jié)合二分搜索法優(yōu)化傳輸功率來(lái)降低傳輸時(shí)延和能耗,從而最小化系統(tǒng)的計(jì)算開(kāi)銷(xiāo)。根據(jù)第1節(jié)的系統(tǒng)模型,將最小化系統(tǒng)計(jì)算開(kāi)銷(xiāo)問(wèn)題建模為:

(7)

其中,C1保證分配給用戶的本地計(jì)算能力為正,C2保證分配給卸載用戶的計(jì)算資源不超過(guò)服務(wù)器所擁有的最大資源fs,C3保證分配給用戶的傳輸功率為正且不大于最大傳輸功率,C4用戶選擇相同信道進(jìn)行卸載時(shí)的干擾不超過(guò)預(yù)先設(shè)定的閾值。

在式(7)中,需要優(yōu)化的變量是傳輸功率與用戶卸載決策,由于功率pn為連續(xù)變量,卸載決策a為整數(shù)變量,因此該問(wèn)題被制定為MINLP。為了能夠求解式(7),進(jìn)一步將其分解為兩個(gè)相關(guān)的子問(wèn)題,首先優(yōu)化傳輸功率pn,用于特定的卸載決策;然后在上一步的基礎(chǔ)上優(yōu)化用戶的卸載決策a,從而最小化系統(tǒng)計(jì)算開(kāi)銷(xiāo)。基于此,可重寫(xiě)MINLP問(wèn)題式(7)為:

s.t.C1,C2,C3 andC4

(8)

式(8)中的功率優(yōu)化和卸載決策的約束是相互解耦的。因此,該問(wèn)題可以重寫(xiě)為:

s.t.C2,C3 andC4

(9)

其中,Z(a)是MD進(jìn)行卸載決策時(shí)的最佳傳輸功率。

2.2 優(yōu)化傳輸功率

結(jié)合式(4)和式(5),將式(9)重寫(xiě)為:

s.t.C2,C3 andC4

(10)

(11)

從式(11)可以看出,當(dāng)χ(pn)達(dá)到最小值時(shí)C(pn)為最優(yōu)。但是χ(pn)的二階導(dǎo)數(shù)在定義域內(nèi)并不總是正的,因此,χ(pn)在定義域內(nèi)不是凸的。

引理1χ(pn)函數(shù)是單峰的。

證明首先χ(pn)在R是二次可微的,接下來(lái)檢查擬凸二階條件,存在一點(diǎn)x0既滿足χ′(x0)=0也滿足χ″(x0)≥0。

χ(pn)的一階導(dǎo)數(shù)為:

(12)

χ(pn)的二階導(dǎo)數(shù)為:

(13)

(14)

將式(14)計(jì)算出的pn替換到式(13)中,得:

(15)

1.Initialize p0、ζth、ξ;

2.if φ(p0)<0 then

4.else

5.Initialize pl=0 and ph=p0;

6.pz=(pl+ph)/2;

7.if φ(pz)<0 then

8.pl=pz;

9.else

10.ph=pz;

11.until ph-pl<ξ

13.end if

2.3 優(yōu)化卸載策略

定理1博弈Λ至少有一個(gè)純策略NEP。

(16)

其中,om表示用戶選擇的信道,Πl(fā)和Πc(r)分別為:

(17)

(18)

(19)

(20)

借用勢(shì)函數(shù)Φ來(lái)證明博弈Λ至少有一個(gè)純策略NEP,根據(jù)勢(shì)函數(shù)的定義,即式(16)、式(17)和式(18)可得用戶n在計(jì)算卸載決策變化前后的勢(shì)函數(shù)為:

(21)

(22)

其中,oan表示卸載的用戶,由式(19)～式(22)可得:

(23)

(24)

(25)

同理,根據(jù)勢(shì)函數(shù)的定義,即式(16)～式(18)可得用戶n在計(jì)算卸載決策變化前后的勢(shì)函數(shù)為:

(26)

(27)

同樣,根據(jù)式(24)～式(27)可以得出:

(28)

對(duì)于情況3):和情況2)類(lèi)似,很容易證明得出:

通過(guò)上述3種情況的證明,勢(shì)博弈可以通過(guò)一個(gè)精確的勢(shì)函數(shù)表示,并且根據(jù)納什均衡存在定理[20],其中至少存在一組純策略納什均衡。多用戶卸載作為一個(gè)有限博弈,也會(huì)得到這樣一組策略,并達(dá)到納什均衡。根據(jù)上面分析,本文提出的基于博弈論的功率優(yōu)化算法(Game-Theoretic with Power Optimization Offloading Algorithm,GT-POOA)詳細(xì)描述如下(ε為GT-POOA收斂的迭代次數(shù)):

輸出A*、Υn

4.store MD n into set of A*

5.end for

6.while A*=? do

9.else

10.an=an

12.end while

3 仿真結(jié)果與分析

本節(jié)通過(guò)仿真來(lái)驗(yàn)證GT-POOA的性能,模擬一個(gè)多用戶MEC計(jì)算卸載系統(tǒng),表1為性能評(píng)估中的主要參數(shù)設(shè)置,并將GT-POOA與以下卸載方案相比較:

1)博弈論卸載方案(GT-scheme):單純的博弈卸載。

2)多用戶計(jì)算卸載(MECO):一種自適應(yīng)順序卸載博弈方法。

3)本地處理(Computing locally at the ME):所有的用戶總是本地執(zhí)行任務(wù)。

4)計(jì)算卸載(Computing offloading at the edge):所有用戶將任務(wù)進(jìn)行卸載。

表1 仿真參數(shù)

首先驗(yàn)證GT-POOA的納什均衡性和收斂性。分別進(jìn)行多次重復(fù)實(shí)驗(yàn)(N取20、30、40),通過(guò)圖2可以看出,GT-POOA在經(jīng)過(guò)有限次迭代后可以達(dá)到納什均衡。通過(guò)圖3可以看出,GT-POOA在MDs逐步增多的情況下,收斂的平均迭代次數(shù)與MDs的數(shù)量是近似線性的。

圖2 GT-POOA在最小計(jì)算開(kāi)銷(xiāo)下的收斂性

圖3 不同用戶數(shù)下GT-POOA收斂的平均迭代次數(shù)

本文通過(guò)實(shí)驗(yàn)來(lái)研究用戶在不同卸載方案下的平均邊緣計(jì)算用戶的數(shù)量和平均系統(tǒng)計(jì)算開(kāi)銷(xiāo)(N分別取10、15、20、25、30、35、40)。從圖4可以看出,對(duì)于有益于邊緣計(jì)算用戶數(shù)量的度量,本文提出的GT-POOA與上述卸載方案1)、方案2)、方案4)相比,性能分別可以提高15%、8%、31.5%。從圖5可以看出,與上述卸載方案1)～方案4)相比,本文方案性能可以提高41%、12%、67%、71.8%。本文利用二分搜索算法為卸載用戶找到最佳傳輸功率來(lái)減少傳輸時(shí)延和能耗,并采用博弈論為用戶組找到最佳的卸載決策組合來(lái)降低系統(tǒng)成本。綜上分析,本文提出的GT-POOA算法具有較好的計(jì)算卸載性能。

圖5 用戶在不同卸載方案下的平均計(jì)算開(kāi)銷(xiāo)

4 結(jié)束語(yǔ)

本文采用博弈論解決MEC中多用戶之間的計(jì)算卸載決策問(wèn)題,設(shè)計(jì)一種基于博弈論的功率分配算法GT-POOA,以實(shí)現(xiàn)多用戶計(jì)算卸載博弈的納什均衡。仿真結(jié)果表明,GT-POOA具有較好的計(jì)算卸載性能。下一步將研究用戶在動(dòng)態(tài)計(jì)算和離開(kāi)狀態(tài)下的MECO場(chǎng)景,從而實(shí)現(xiàn)更有效的計(jì)算卸載機(jī)制。