余 翔,石雪琴,劉一勛

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

0 概述

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

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

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

1 系統模型

圖1 移動邊緣計算環(huán)境模型

1.1 通信模型

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

(1)

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

1.2 計算模型

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

1.2.1 本地計算

(2)

MD的本地計算能耗為:

(3)

其中,η表示每個CPU周期消耗能量的系數,設置η=10-26是根據文獻[18]中的方法獲得。

1.2.2 邊緣計算

(4)

(5)

對于許多應用程序而言,計算結果的大小通常遠小于輸入數據的大小,因此忽略了服務器將計算結果發(fā)送給設備的開銷[19]。根據上面分析,將計算模型定義為:

(6)

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

2.1 問題描述

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

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

(7)

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

在式(7)中,需要優(yōu)化的變量是傳輸功率與用戶卸載決策,由于功率pn為連續(xù)變量,卸載決策a為整數變量,因此該問題被制定為MINLP。為了能夠求解式(7),進一步將其分解為兩個相關的子問題,首先優(yōu)化傳輸功率pn,用于特定的卸載決策;然后在上一步的基礎上優(yōu)化用戶的卸載決策a,從而最小化系統計算開銷?；诖?可重寫MINLP問題式(7)為:

s.t.C1,C2,C3 andC4

(8)

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

s.t.C2,C3 andC4

(9)

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

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

結合式(4)和式(5),將式(9)重寫為:

s.t.C2,C3 andC4

(10)

(11)

從式(11)可以看出,當χ(pn)達到最小值時C(pn)為最優(yōu)。但是χ(pn)的二階導數在定義域內并不總是正的,因此,χ(pn)在定義域內不是凸的。

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

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

χ(pn)的一階導數為:

(12)

χ(pn)的二階導數為:

(13)

(14)

將式(14)計算出的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博弈Λ至少有一個純策略NEP。

(16)

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

(17)

(18)

(19)

(20)

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

(21)

(22)

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

(23)

(24)

(25)

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

(26)

(27)

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

(28)

對于情況3):和情況2)類似,很容易證明得出:

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

輸出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é)通過仿真來驗證GT-POOA的性能,模擬一個多用戶MEC計算卸載系統,表1為性能評估中的主要參數設置,并將GT-POOA與以下卸載方案相比較:

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

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

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

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

表1 仿真參數

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

圖2 GT-POOA在最小計算開銷下的收斂性

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

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

圖5 用戶在不同卸載方案下的平均計算開銷

4 結束語

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