一種移動(dòng)云計(jì)算計(jì)算卸載算法及其仿真研究

劉 靜

(1. 蘇州健雄職業(yè)技術(shù)學(xué)院 軟件與服務(wù)外包學(xué)院, 江蘇 太倉(cāng) 215411; 2. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 江蘇 蘇州 215006)

0 引 言

隨著智能手機(jī)的快速普及，越來(lái)越多的新型移動(dòng)應(yīng)用，如人臉識(shí)別、自然語(yǔ)言處理、交互式游戲以及增強(qiáng)現(xiàn)實(shí)等正進(jìn)入社會(huì)生活的方方面面。這類移動(dòng)應(yīng)用通常為典型的資源緊俏型應(yīng)用，需要密集型計(jì)算和高能耗。由于物理大小的限制，移動(dòng)設(shè)備通常在計(jì)算資源和電池容量上是受限的。這種在移動(dòng)設(shè)備上資源需求緊俏與資源受限的矛盾為未來(lái)移動(dòng)平臺(tái)的發(fā)展帶來(lái)了挑戰(zhàn)[1]。

移動(dòng)云計(jì)算可以將資源豐富且計(jì)算能力更強(qiáng)的云擴(kuò)展至資源受限的移動(dòng)設(shè)備端以增強(qiáng)移動(dòng)設(shè)備的處理能力，以解決移動(dòng)設(shè)備資源受限的問(wèn)題[2]，模型如圖1所示。盡管如此，設(shè)計(jì)綜合性能可靠的移動(dòng)云計(jì)算系統(tǒng)仍是一項(xiàng)巨大挑戰(zhàn)，其中關(guān)鍵之一是如何在移動(dòng)設(shè)備用戶間實(shí)現(xiàn)高效的計(jì)算卸載機(jī)制。影響移動(dòng)云計(jì)算性能的關(guān)鍵因素之一是無(wú)線訪問(wèn)的效率[3]。因此會(huì)出現(xiàn)多個(gè)移動(dòng)用戶同步通過(guò)無(wú)線信道進(jìn)行計(jì)算卸載，它們之間勢(shì)必會(huì)出現(xiàn)相互干擾，從而降低數(shù)據(jù)傳輸?shù)乃俾剩@將導(dǎo)致低效的計(jì)算卸載和數(shù)據(jù)傳輸時(shí)間的延長(zhǎng)。此時(shí)，對(duì)于移動(dòng)用戶而言，計(jì)算卸載至云端將是得不償失的。

圖1 移動(dòng)云計(jì)算

本文提出了一種移動(dòng)云計(jì)算中的基于博弈的計(jì)算卸載算法。博弈論是設(shè)計(jì)分布式算法的有效框架，它使得系統(tǒng)中的移動(dòng)設(shè)備用戶可以自組織的形成相互滿意的計(jì)算卸載決策。自組織特征將自治性引入移動(dòng)云計(jì)算系統(tǒng)中，有助于簡(jiǎn)化云計(jì)算復(fù)雜中心化的管理策略(即：多方移動(dòng)用戶的信息收集與計(jì)算卸載調(diào)度)。同時(shí)，由于不同的移動(dòng)設(shè)備隸屬于不同的個(gè)體，它們追求的目標(biāo)也不相同，博弈論可以分析立足于自身興趣的多移動(dòng)設(shè)備用戶間的相互影響，并推導(dǎo)出兼容的計(jì)算卸載機(jī)制，使得沒(méi)有任一移動(dòng)用戶有動(dòng)機(jī)偏離于當(dāng)前策略。

1 相關(guān)研究

當(dāng)前計(jì)算卸載算法設(shè)計(jì)方面的工作多集中于單移動(dòng)設(shè)備用戶環(huán)境。如文獻(xiàn)[4]中設(shè)計(jì)了一種最小化能耗的任務(wù)調(diào)度算法，文獻(xiàn)[5]中設(shè)計(jì)的隨機(jī)無(wú)線信道的能效最優(yōu)移動(dòng)云計(jì)算調(diào)度框架，文獻(xiàn)[6]中針對(duì)移動(dòng)任務(wù)設(shè)計(jì)的協(xié)作式任務(wù)執(zhí)行框架，以及文獻(xiàn)[7]中提出基于李雅普諾夫(Laypunov)優(yōu)化法設(shè)計(jì)的動(dòng)態(tài)計(jì)算卸載能耗優(yōu)化算法。然而，以上工作并未做到真正的能耗優(yōu)化，如局部調(diào)度時(shí)的中央處理器(Central Processing Unit, CPU)時(shí)鐘頻率控制，以及計(jì)算卸載至云端時(shí)的傳輸功率分配問(wèn)題。文獻(xiàn)[8]中雖考慮了能耗與應(yīng)用完成時(shí)間的同步優(yōu)化，但所涉及的是獨(dú)立任務(wù)集類型，任務(wù)間不存在順序依賴，且未考慮計(jì)算卸載決策時(shí)的資源分配。文獻(xiàn)[9]中利用遺傳算法來(lái)搜索云端和移動(dòng)終端計(jì)算資源聯(lián)合執(zhí)行應(yīng)用的全局最優(yōu)解，重點(diǎn)研究了任務(wù)遷移的選擇問(wèn)題。

部分文獻(xiàn)在多移動(dòng)設(shè)備用戶環(huán)境下解決計(jì)算卸載問(wèn)題。文獻(xiàn)[10]中研究了多用戶共享無(wú)線網(wǎng)絡(luò)帶寬的場(chǎng)景，設(shè)計(jì)了一種集中式啟發(fā)式遺傳算法用于求解移動(dòng)云計(jì)算性能最大化問(wèn)題。文獻(xiàn)[11]中考慮了用戶移動(dòng)模型，提出了一種集中式貪婪算法求解多用戶計(jì)算卸載問(wèn)題。文獻(xiàn)[12]提出一種集中式調(diào)度算法在擁有延時(shí)需求的多用戶間實(shí)現(xiàn)了最優(yōu)化通信和計(jì)算資源分配。然而，以上的集中式計(jì)算卸載算法均要求所有移動(dòng)用戶發(fā)送自身信息(即無(wú)線信道增益和計(jì)算任務(wù)大小)至一個(gè)中心實(shí)體(即云端)，然后通過(guò)該實(shí)體決定具體的計(jì)算卸載策略。文獻(xiàn)[13]中對(duì)能耗和時(shí)間進(jìn)行了聯(lián)合優(yōu)化，通過(guò)集中式調(diào)算策略的制定可以實(shí)現(xiàn)最優(yōu)解。文獻(xiàn)[14]對(duì)能耗進(jìn)行了最小化優(yōu)化，從移動(dòng)終端硬件出發(fā)，進(jìn)行能耗優(yōu)化。文獻(xiàn)[15]中提出一種臨近閑置移動(dòng)終端作為卸載目標(biāo)的分布式博弈算法，仿真出一種最優(yōu)結(jié)果。不同的是，本文將提出一種非中心式的博弈算法，它可以使每個(gè)移動(dòng)設(shè)備用戶在局部作出計(jì)算卸載決策，這有助降低云端的控制和信號(hào)開(kāi)銷。

2 系統(tǒng)模型

2.1 通信模型

無(wú)線訪問(wèn)基站s可以是一個(gè)無(wú)線網(wǎng)絡(luò)訪問(wèn)點(diǎn)，或蜂窩網(wǎng)中的宏單元基站，可用于管理移動(dòng)設(shè)備的上傳/下載通信鏈路。令an∈0,1表示移動(dòng)用戶n的計(jì)算卸載決策，an=1 表明移動(dòng)用戶n選擇通過(guò)無(wú)線信道將任務(wù)卸載至云端計(jì)算，an=0表明移動(dòng)用戶n選擇在其局部設(shè)備上執(zhí)行任務(wù)。給定所有用戶的決策集a=a1,a2,...,aN，N為用戶個(gè)數(shù)，根據(jù)香農(nóng)定律可以計(jì)算移動(dòng)用戶n進(jìn)行計(jì)算卸載時(shí)的數(shù)據(jù)傳輸速率為

(1)

2.2 計(jì)算模型

考慮每個(gè)移動(dòng)設(shè)備用戶n擁有一個(gè)計(jì)算任務(wù)In=Bn,Dn，可在局部移動(dòng)設(shè)備上計(jì)算，也可通過(guò)計(jì)算卸載至云端進(jìn)行計(jì)算。Bn為計(jì)算任務(wù)In的計(jì)算輸入數(shù)據(jù)量，Dn為完成計(jì)算任務(wù)In需要的CPU周期數(shù)量。以下討論在局部計(jì)算和云端計(jì)算時(shí)的能耗與處理時(shí)間模型。

(2)

計(jì)算能耗為:

(3)

根據(jù)式(2)和(3)，可以計(jì)算局部計(jì)算時(shí)以處理時(shí)間和能耗衡量的計(jì)算開(kāi)銷為：

(4)

(2) 云計(jì)算模型。對(duì)于云計(jì)算方法，移動(dòng)設(shè)備用戶n將卸載其計(jì)算任務(wù)In至云端，云端將負(fù)責(zé)執(zhí)行用戶的計(jì)算任務(wù)。計(jì)算卸載將為移動(dòng)用戶n計(jì)算再來(lái)由于通信無(wú)線訪問(wèn)傳輸數(shù)據(jù)至云端的時(shí)間與能耗方面的開(kāi)銷。根據(jù)前文的通信模型，可以計(jì)算移動(dòng)設(shè)備用戶n卸載輸入數(shù)據(jù)大小為Bn的傳輸時(shí)間(下標(biāo)中引入off表示卸載，上標(biāo)c表示開(kāi)銷，下同)與能耗分別為：

(5)

(6)

(7)

根據(jù)式(5)～(7)，可以計(jì)算云端執(zhí)行時(shí)以處理時(shí)間和能耗衡量的計(jì)算開(kāi)銷為:

(8)

根據(jù)通信模型和計(jì)算模型可知，移動(dòng)用戶間的計(jì)算卸載決策是相互關(guān)聯(lián)的。若過(guò)多移動(dòng)用戶同步選擇將任務(wù)通過(guò)無(wú)線信道計(jì)算卸載至云端，勢(shì)必會(huì)導(dǎo)致嚴(yán)重干擾和低數(shù)據(jù)傳輸率。當(dāng)移動(dòng)用戶n的數(shù)據(jù)率Rn(a)較低時(shí)，計(jì)算卸載時(shí)無(wú)線訪問(wèn)會(huì)帶來(lái)較高能耗和較長(zhǎng)的傳輸時(shí)間。此時(shí)，將任務(wù)進(jìn)行在移動(dòng)設(shè)備上局部執(zhí)行將更加有利，可以避免云端計(jì)算的過(guò)長(zhǎng)處理時(shí)間和高能耗。以下將引入博弈方法求解實(shí)現(xiàn)多移動(dòng)用戶的計(jì)算卸載決策問(wèn)題。

3 計(jì)算卸載博弈

3.1 博弈形式化

考慮一個(gè)計(jì)算卸載周期內(nèi)多個(gè)移動(dòng)設(shè)備用戶間的分布式計(jì)算卸載決策問(wèn)題，令a-n=a1,…，an-1,an+1,…，aN為除用戶n之外所有其他用戶的計(jì)算卸載策略。給定其他用戶的決策a-n，用戶n選擇合適的策略an∈{0,1}(即：局部計(jì)算或云計(jì)算)，最小化能耗與處理時(shí)間組成的計(jì)算開(kāi)銷，即：

?n∈N

根據(jù)式(4)、(8)，計(jì)算得到移動(dòng)用戶n的代價(jià)函數(shù)為

(9)

將以上優(yōu)化問(wèn)題形式化為博弈模型G=N,{An}n∈N,{Vn}，移動(dòng)用戶N為博弈者集合，An={0,1} 為用戶n的博弈策略集合。以下稱博弈G為分布式計(jì)算卸載博弈，并引入納什(Nash)均衡概念。

(10)

?an∈An,n∈N

Nash均衡具有自適應(yīng)的穩(wěn)定屬性，它使得用戶在均衡處可以實(shí)現(xiàn)相互滿意的解，沒(méi)有用戶有動(dòng)機(jī)偏離該均衡。

3.2 博弈性質(zhì)

以下研究分布式計(jì)算卸載博弈中Nash均衡的存在性，先引入最優(yōu)回應(yīng)的概念。

定義2給定其他博弈者的策略a-n，博弈者n的策略a*n∈An是最優(yōu)回應(yīng)，如果：

(11)

根據(jù)式(10)和(11)，可以看出，處于Nash均衡時(shí)，所有用戶的策略對(duì)于其他用戶的策略均是相互最優(yōu)回應(yīng)。基于最優(yōu)回應(yīng)概率，可以得到以下分布式計(jì)算卸載博弈的屬性。

推論1給定分布式計(jì)算卸載博弈中其它移動(dòng)用戶的策略a-n，用戶n的最優(yōu)回應(yīng)可由以下閾值策略得到：

(12)

式中，閾值

(13)

(1) 同質(zhì)無(wú)線訪問(wèn)情形。若無(wú)線信道為同質(zhì)的，則對(duì)于任意用戶n,m∈N，PmHm=PnHn=K。這表明所有移動(dòng)用戶擁有相同信道條件，與基站分配相同傳輸功率。然而，不同用戶擁有不同閾值Ln，即在計(jì)算能力和任務(wù)方面是異質(zhì)的。

對(duì)于同質(zhì)無(wú)線訪問(wèn)，對(duì)移動(dòng)設(shè)備用戶集N進(jìn)行排序，使得L1/K≥L2/K≥…≥LN/K，得到以下結(jié)論。

推論2對(duì)于同質(zhì)無(wú)線訪問(wèn)的分布式計(jì)算卸載博弈，若存在一個(gè)非空可獲利移動(dòng)用戶組S?N，使得S≤Li/K+1,i∈S，且對(duì)于S?N，S>Li/K,j∈NS，則用戶i∈S的策略an=1，其他用戶j∈NS的策略aj=0組成的策略集為一個(gè)Nash均衡。

證明根據(jù)式(12)，對(duì)于一個(gè)用戶i∈S，其接收的干擾為：

(14)

根據(jù)推論1可知，執(zhí)行策略an=1為最優(yōu)回應(yīng)。類似地，對(duì)于用戶j∈NS，可知執(zhí)行策略aj=0為最優(yōu)回應(yīng)。由于所有用戶都相互執(zhí)行最優(yōu)回應(yīng)策略，故所提策略集即為Nash均衡。

例如：對(duì)于4個(gè)用戶L1/K,L2/K,L3/K,L4/K=5,4,3,2，可獲得的用戶組S=1,2,3。當(dāng)L1/K≥0時(shí)，可以通過(guò)算法1構(gòu)造可獲利用戶組。

定理1對(duì)于同質(zhì)無(wú)線訪問(wèn)的分布式計(jì)算卸載博弈總存在一個(gè)Nash均衡。具體地，所有用戶n∈N當(dāng)L1/K<0時(shí)，執(zhí)行策略an=0即為一個(gè)Nash均衡。當(dāng)L1/K≥0時(shí)，通過(guò)算法1構(gòu)造一個(gè)可獲利用戶組S≠φ，則用戶i∈S的策略an=1，其他用戶j∈NS的策略aj=0組成的策略集為一個(gè)Nash均衡。

證明給定滿足L1/K≥L2/K≥…≥LN/K排序的移動(dòng)用戶集，若L1/K<0，易知可獲利用戶組S=φ。此時(shí)，所有用戶n∈N執(zhí)行策略an=0為最優(yōu)回應(yīng)，即一個(gè)Nash均衡。

若L1/K≥0，可通過(guò)算法1構(gòu)造可獲利用戶組S≠φ。第1步，設(shè)置S=1，易知S=1≤L1/K+1，滿足式(12)中的條件。第2步，2≤t≤N，定義S′=S∪t。若S′>Lt/K+1，則得到可獲利用戶組S=1,…,t-1，原因在于：①S滿足S≤Lt-1/K+1(否則無(wú)法推進(jìn)至步驟t)，這表明式(12)的條件是滿足，即：S≤Lt-1/K+1≤…≤L1/K+1;② 由于S′=t>Lt/K+1，有S=t-1>Lt/K，這表明式(13)的條件是滿足的，即：S>Lt/K≥…≥LN/K。由于算法1中步驟數(shù)上限為N，故必定可以得到可獲利用戶組S≠φ。

算法1尋找可獲利用戶組算法

1. Input:the set of ordered mobile device users withL1/K≥L2/K≥…≥LN/KandL1/K≥0

2. output:a beneficial cloud computing groupS

3. setS={1}

4. fort=2 toNdo

5. setS’=S∪{t}

6. if |S’|>Lt/K+1 then

7. stop and go to return

8. else setS=S’

9. end if

10. end for

11. return S

(2) 一般無(wú)線訪問(wèn)情形。若無(wú)線信道為異質(zhì)的，則PmHm≠PnHn。由于移動(dòng)設(shè)備用戶擁有不同的傳輸功率Pn，信道增益Hn及閾值Ln，故不能應(yīng)用同質(zhì)環(huán)境中采用的方法。以下引入勢(shì)博弈的概念進(jìn)行求解。

(15)

則有：

(16)

(17)

以下通過(guò)說(shuō)明分布式計(jì)算卸載博弈為勢(shì)博弈的方式證明該博弈存在Nash均衡。具體地，定義勢(shì)函數(shù)為：

(18)

IA為指標(biāo)函數(shù)，若事件A為真，則IA=1，否則，IA=0。

定理2分布式計(jì)算卸載博弈為帶有勢(shì)函數(shù)式(18)的勢(shì)博弈，總存在一個(gè)Nash均衡。

4 計(jì)算卸載博弈算法

本節(jié)設(shè)計(jì)分布式計(jì)算卸載博弈算法，如算法2所示，可用于實(shí)現(xiàn)分布式計(jì)算卸載博弈決策的Nash均衡解。

算法2分布式計(jì)算卸載博弈算法

1. Initialization:

2. Each mobile device usernchooses the computation decisionan(0)=1

3. end initialization

4. repeat for each usernand each decision slottin parallel

5. measure the interferenceμn(t)

6. compute the best response set △n(t)

7. if △n(t)≠? then

8. contend for the decision update opportunity

9. if win the decision update contention then

10. choose the decisionan(t+1)∈△n(t) for next slot

11. broadcast the RTU message to other users

12. else choose the original decisionan(t+1)=an(t) for next slot

13. end if

14. else choose the original decisionan(t+1)=an(t) for next slot

15. end if

16. until no RTU message are broadcasted forMconsecutive slots

4.1 算法設(shè)計(jì)

分布式計(jì)算卸載博弈使移動(dòng)用戶在計(jì)算任務(wù)執(zhí)行前實(shí)現(xiàn)相互滿意的決策，主要利用了博弈的有限改進(jìn)屬性，使得每個(gè)移動(dòng)用戶每次均可進(jìn)行計(jì)算卸載決策的改進(jìn)更新。具體地，可利用無(wú)線訪問(wèn)基站的同步時(shí)鐘信號(hào)，考慮一個(gè)計(jì)算卸載決策中的時(shí)槽結(jié)構(gòu)，每個(gè)決策時(shí)槽t包括兩個(gè)部分：

(2) 決策更新。使每個(gè)移動(dòng)用戶在每個(gè)決策時(shí)槽中進(jìn)行一次決策更新，以搜索博弈的有限改進(jìn)屬性。每個(gè)能夠改進(jìn)其計(jì)算性能的用戶以分布式方式競(jìng)爭(zhēng)決策更新機(jī)會(huì)。具體地，根據(jù)推論1，每個(gè)移動(dòng)用戶n首先基于度量干擾μnt計(jì)算其最優(yōu)回應(yīng)集為：

Δn(t)=

故若Δn(t)≠φ，即用戶n可以改進(jìn)，則用戶n將競(jìng)爭(zhēng)決策更新機(jī)會(huì)。否則，用戶n將在下一決策時(shí)槽中維持當(dāng)前策略不變，即ant+1=ant。對(duì)于決策更新，本文采用隨機(jī)退避算法設(shè)置決策更新時(shí)長(zhǎng)為τ*。

4.2 性能分析

本節(jié)討論分布式計(jì)算卸載博弈算法的Nash均衡的有效性。由于算法可能產(chǎn)生多個(gè)Nash均衡，算法將隨機(jī)選擇一個(gè)Nash均衡(由于決策更新階段用戶是隨機(jī)選擇的)。基于博弈調(diào)和率PoA的概念，以量化最差Nash均衡與集中最優(yōu)解的效率。令χ為算法產(chǎn)生的Nash均衡集，則PoA可定義為

5 數(shù)值仿真

首先考察算法得到的移動(dòng)設(shè)備用戶的計(jì)算代價(jià)Vn(a)的變化情況，如圖2所示。可以看出，算法可以降低用戶代價(jià)，并收斂于均衡解。為了證明收斂均衡為Nash均衡，進(jìn)一步給出了算法中勢(shì)函數(shù)Ψ(a)的變化，如圖3所示。結(jié)果表明，博弈算法可以使得勢(shì)函數(shù)到達(dá)最小值，而根據(jù)勢(shì)函數(shù)屬性可以斷定該點(diǎn)即為Nash均衡。

圖2 用戶代價(jià)變化

圖3 勢(shì)函數(shù)值變化

圖4 CPU周期數(shù)對(duì)總體代價(jià)的影響

圖5 計(jì)算數(shù)據(jù)量對(duì)總體代價(jià)的影響

圖6 總體代價(jià)

圖7 算法迭代次數(shù)

為了評(píng)估分布式計(jì)算卸載算法的控制和信號(hào)開(kāi)銷，進(jìn)一步觀察了在移動(dòng)設(shè)備與云端間進(jìn)行信號(hào)控制信息交換的信號(hào)量，如圖8所示。結(jié)果表明分布式計(jì)算卸載算法相對(duì)集中式算法可以降低89%的信號(hào)量，這是因?yàn)榉植际剿惴ㄖ校瑔蝹€(gè)移動(dòng)用戶僅在進(jìn)行計(jì)算卸載決策更新時(shí)才進(jìn)行信息交換(干擾度量和決策更新)。而集中式算法中，每個(gè)移動(dòng)用戶需要傳輸所有其局部參數(shù)至云端，包括傳輸功率、信道增益、背景干擾功耗、局部計(jì)算能力等。而分布式計(jì)算卸載算法僅在局部進(jìn)行計(jì)算卸載決策。

圖8 控制信息開(kāi)銷

6 結(jié) 語(yǔ)

基于移動(dòng)云計(jì)算環(huán)境，設(shè)計(jì)了一種分布式計(jì)算卸載博弈算法，以實(shí)現(xiàn)移動(dòng)用戶任務(wù)的高能效執(zhí)行。建立了計(jì)算卸載決策的博弈模型，證明了在同質(zhì)和異質(zhì)無(wú)線訪問(wèn)模型中，博弈均總是存在Nash均衡解，且博弈算法總能得到該Nash均衡。數(shù)值仿真結(jié)果證明博弈算法是有效可行的。