移動(dòng)云計(jì)算環(huán)境下基于任務(wù)依賴的計(jì)算遷移研究

鄭利陽(yáng) 劉茜萍

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室 江蘇 南京 210023)

0 引 言

近幾年來(lái)，移動(dòng)智能終端技術(shù)取得了巨大的進(jìn)步，可提供滿足用戶各種需求的移動(dòng)應(yīng)用。然而，由于其尺寸的限制，移動(dòng)終端總是存在諸如計(jì)算能力弱、存儲(chǔ)空間小和電量不足等問(wèn)題。資源受限的問(wèn)題同時(shí)也限制了移動(dòng)終端和移動(dòng)應(yīng)用的進(jìn)一步發(fā)展，因此，如何擴(kuò)展移動(dòng)終端的資源，成為需要迫切解決的問(wèn)題[1]。

為了解決移動(dòng)終端資源受限的問(wèn)題，移動(dòng)云計(jì)算技術(shù)應(yīng)運(yùn)而生，通過(guò)計(jì)算遷移，用戶可以將應(yīng)用遷移至遠(yuǎn)程云端或微云來(lái)進(jìn)行處理，以此彌補(bǔ)移動(dòng)終端的資源缺陷，提高應(yīng)用的服務(wù)質(zhì)量[2-3]。其中，與遠(yuǎn)程云端相比，微云具有與終端距離更近、傳輸延遲更小的優(yōu)勢(shì)。對(duì)于實(shí)時(shí)性要求很高而計(jì)算要求相對(duì)不高的應(yīng)用而言，它們就非常適合遷移至微云處理。這類(lèi)應(yīng)用往往可再細(xì)分為若干相互存在時(shí)序和數(shù)據(jù)依賴關(guān)系的任務(wù)。針對(duì)這一類(lèi)復(fù)雜應(yīng)用，在遷移過(guò)程中，如何根據(jù)各任務(wù)之間的依賴關(guān)系，有效地結(jié)合不同微云的優(yōu)勢(shì)，為移動(dòng)應(yīng)用中的計(jì)算任務(wù)確定合理有效的遷移方案，降低移動(dòng)設(shè)備上能量消耗和響應(yīng)時(shí)間，是一個(gè)值得挑戰(zhàn)的問(wèn)題。

針對(duì)移動(dòng)云環(huán)境下具有依賴關(guān)系的多任務(wù)計(jì)算遷移問(wèn)題，本文在考慮任務(wù)類(lèi)型細(xì)分的基礎(chǔ)上對(duì)不同微云的計(jì)算能力進(jìn)行了細(xì)化表達(dá)，并在此基礎(chǔ)上給出了遷移方案的效用函數(shù)計(jì)算方法，進(jìn)而基于時(shí)序和數(shù)據(jù)依賴約束提出了一個(gè)改進(jìn)的遺傳算法，以盡可能減少任務(wù)間的數(shù)據(jù)傳輸，提高任務(wù)的并行度，從而得到響應(yīng)時(shí)間和終端能量消耗總體較優(yōu)的遷移方案。

1 相關(guān)工作

目前，針對(duì)移動(dòng)云計(jì)算中計(jì)算遷移問(wèn)題的研究有很多，文獻(xiàn)[4]中將移動(dòng)應(yīng)用分為通信密集型和計(jì)算密集型，通信密集型應(yīng)用適合于終端處理，計(jì)算密集型應(yīng)用適合于遠(yuǎn)程云端處理，而介于兩者之間的應(yīng)用則需要根據(jù)局域網(wǎng)中的帶寬條件來(lái)確定處理位置。文獻(xiàn)[5]在博弈論的基礎(chǔ)上提出了一種算法，該算法對(duì)于移動(dòng)終端和遠(yuǎn)程云端的最優(yōu)能耗問(wèn)題，可獲得納什均衡解。文獻(xiàn)[6]同樣是在博弈論的基礎(chǔ)上提出了一種分布式的計(jì)算遷移方法，該方法可以根據(jù)技術(shù)任務(wù)的規(guī)模來(lái)有效地進(jìn)行任務(wù)遷移。文獻(xiàn)[7]提出了一種自動(dòng)貪婪遷移算法，可以更好地解決任務(wù)遷移過(guò)程中的能效問(wèn)題。文獻(xiàn)[8]提出了一種禁忌搜索算法，可以為應(yīng)用任務(wù)的遷移獲得更好的解決方案。文獻(xiàn)[9-10]根據(jù)逆推動(dòng)態(tài)規(guī)劃的解法提出了一種遷移算法，該算法對(duì)于一組串行任務(wù)，可在滿足響應(yīng)時(shí)間的前提下，將移動(dòng)終端的能耗最小化。文獻(xiàn)[11]提出了一組并行任務(wù)的聯(lián)合遷移算法，可以更快地獲得終端能耗的最優(yōu)解。文獻(xiàn)[12]提出了一個(gè)面向云數(shù)據(jù)中心的主動(dòng)服務(wù)遷移框架，該框架采用輕量級(jí)程序來(lái)部署運(yùn)行時(shí)分布式平臺(tái)，采用粗粒度級(jí)和簡(jiǎn)單的開(kāi)發(fā)部署過(guò)程，實(shí)現(xiàn)移動(dòng)云環(huán)境下的計(jì)算遷移。文獻(xiàn)[13]考慮了由遠(yuǎn)程云端、微云和移動(dòng)終端組成的三層移動(dòng)云計(jì)算架構(gòu)，根據(jù)局域網(wǎng)的條件提出了一種遷移算法，該算法可以在滿足響應(yīng)時(shí)間的同時(shí)降低移動(dòng)終端的能量消耗。文獻(xiàn)[14]將計(jì)算遷移模式分為三種：遠(yuǎn)程云端服務(wù)模式、連接式點(diǎn)對(duì)點(diǎn)(Ad Hoc)微云服務(wù)模式和機(jī)會(huì)式Ad Hoc微云服務(wù)模式，然后對(duì)提出的三種計(jì)算遷移模式在Ad Hoc微云上進(jìn)行了詳細(xì)的分析研究。文獻(xiàn)[15]使用了移動(dòng)云環(huán)境下的三層架構(gòu)，定義了一個(gè)模型來(lái)研究計(jì)算遷移對(duì)用戶感知性能的影響，把這個(gè)問(wèn)題表述為一個(gè)廣義納什平衡問(wèn)題，針對(duì)此問(wèn)題提出了一種分布式均衡計(jì)算算法。

若從計(jì)算任務(wù)的處理位置來(lái)講，這些研究可大致分為兩類(lèi)：第1類(lèi)只考慮移動(dòng)終端和遠(yuǎn)程云端兩個(gè)處理位置[4-12]，第2類(lèi)則考慮移動(dòng)終端、微云和遠(yuǎn)程云端三個(gè)處理位置[13-15]。遠(yuǎn)程云端存儲(chǔ)資源豐富，處理計(jì)算任務(wù)的速度也非常快，其任務(wù)處理時(shí)間相對(duì)移動(dòng)終端而言幾乎可以忽略不計(jì)。然而，遠(yuǎn)程云端往往距離用戶較遠(yuǎn)，傳輸延遲較大，很多具有較高實(shí)時(shí)性要求的計(jì)算任務(wù)，并不適合遷移到遠(yuǎn)程云端進(jìn)行處理。與之相反，微云盡管存儲(chǔ)資源有限，處理計(jì)算任務(wù)的速度也相對(duì)遠(yuǎn)端而言有所欠缺，但是它們距離用戶往往較近，傳輸延遲能得以大幅減少。

對(duì)很多實(shí)時(shí)性要求很高而計(jì)算要求相對(duì)不高的復(fù)雜應(yīng)用而言，比如某些在線網(wǎng)絡(luò)游戲、圖片處理等應(yīng)用，就更適合遷移到微云平臺(tái)而非遠(yuǎn)程云端上去處理。然而，目前僅考慮本地和微云的遷移研究較少，對(duì)不同微云的描述也不夠細(xì)致，難以為不同類(lèi)型任務(wù)計(jì)算遷移提供豐富的候選參數(shù)。

此外，當(dāng)前研究大多為多個(gè)獨(dú)立任務(wù)的遷移研究，而實(shí)際的復(fù)雜應(yīng)用可以劃分為多個(gè)相互之間存在依賴關(guān)系的任務(wù)，任務(wù)之間不僅僅只有時(shí)序依賴，還存在有數(shù)據(jù)依賴。一個(gè)任務(wù)可能會(huì)接收另外任務(wù)的處理結(jié)果作為輸入數(shù)據(jù)進(jìn)行進(jìn)一步處理。此時(shí)，需基于數(shù)據(jù)依賴將各任務(wù)遷移至符合其特性的微云執(zhí)行，而大多現(xiàn)有文獻(xiàn)中的計(jì)算遷移策略很難適用于這種場(chǎng)景。

2 系統(tǒng)模型及問(wèn)題描述

在本文中，計(jì)算任務(wù)的處理位置只考慮終端本地和微云端，并且計(jì)算任務(wù)之間存在著時(shí)序和數(shù)據(jù)雙重依賴關(guān)系。在這種場(chǎng)景下，如何遷移處理計(jì)算任務(wù)，以期得到較優(yōu)的響應(yīng)時(shí)間和終端能耗，即較低的效用值，是我們將要解決的主要問(wèn)題。

2.1 計(jì)算任務(wù)模型

計(jì)算任務(wù)代表著在移動(dòng)應(yīng)用中，能實(shí)現(xiàn)某種特定目的的一個(gè)模塊或一段程序。一個(gè)移動(dòng)應(yīng)用在一個(gè)時(shí)間段內(nèi)，可能會(huì)產(chǎn)生一組計(jì)算任務(wù)，并且任務(wù)與任務(wù)之間存在著時(shí)序或數(shù)據(jù)依賴。用一個(gè)帶權(quán)有向無(wú)環(huán)圖G(V,ξ)來(lái)表示產(chǎn)生的一組計(jì)算任務(wù)，其中：V={v1,v2,v3,…,vn}表示這一組計(jì)算任務(wù)的集合，n表示這一組計(jì)算任務(wù)的數(shù)量。ξ={h(vi,vj)|vi,vj∈V}表示計(jì)算任務(wù)之間的依賴關(guān)系集合，當(dāng)h(vi,vj)=0時(shí)，表示任務(wù)vi和任務(wù)vj之間沒(méi)有依賴關(guān)系；當(dāng)h(vi,vj)=1時(shí)，表示任務(wù)vi和任務(wù)vj之間只有時(shí)序依賴；當(dāng)h(vi,vj)=2時(shí)，表示任務(wù)vi和任務(wù)vj之間存在時(shí)序和數(shù)據(jù)雙重依賴。

在本文中，用一個(gè)四元組vi=(di,wi,ri,tyi)來(lái)表示計(jì)算任務(wù)，其中:di(單位為MB)表示vi任務(wù)本身的數(shù)據(jù)量，wi(單位為MB)表示處理該任務(wù)時(shí)所需要的計(jì)算量，ri(單位為MB)表示任務(wù)vi的處理結(jié)果的數(shù)據(jù)量，tyi表示計(jì)算任務(wù)的類(lèi)型。計(jì)算任務(wù)可以根據(jù)其實(shí)現(xiàn)目的分為不同的類(lèi)型，例如視頻、圖片、游戲等。在本文中，假設(shè)有四種不同的任務(wù)類(lèi)型，用TY={A、B、C、D}來(lái)表示，tyi∈TY。由于指令集不同等原因，我們認(rèn)為本地或微云對(duì)于不同類(lèi)型的計(jì)算任務(wù)，其處理能力也是不同的。

2.2 計(jì)算資源模型

根據(jù)上述場(chǎng)景描述，本文假設(shè)移動(dòng)云計(jì)算環(huán)境下的計(jì)算資源主要由移動(dòng)終端的本地資源和微云資源兩部分組成，它們兩者之間可以通過(guò)局域網(wǎng)進(jìn)行通信。由于普通云端往往距離較遠(yuǎn)，因此會(huì)造成延遲過(guò)大，所以暫不考慮。

微云資源可通過(guò)fkty表示，其中k表示微云的編號(hào)，k=1,2,…,m。fkty(單位為GHz)表示微云的不同計(jì)算能力，ty∈TY。此外，移動(dòng)終端和微云之間一般通過(guò)局域網(wǎng)進(jìn)行通信，該局域網(wǎng)帶寬可統(tǒng)一通過(guò)Bc(單位為MB/ms)表示。

2.3 問(wèn)題描述

在移動(dòng)云計(jì)算環(huán)境下，由移動(dòng)終端產(chǎn)生的計(jì)算任務(wù)，可以有在本地處理和遷移到微云端處理兩種選擇。本文用一個(gè)一維向量S=(s1,s2,…,sn)來(lái)表示遷移方案，其中si∈{0,1,…,k,…,m}，m表示微云的個(gè)數(shù)。當(dāng)si=0的時(shí)候，表示任務(wù)vi在本地進(jìn)行處理，此時(shí)，其響應(yīng)時(shí)間為：

(1)

移動(dòng)終端的能量消耗為：

e(i,0)=t(i,0)×Plocal

(2)

當(dāng)si=1,2，…,k,…,m時(shí)，表示任務(wù)vi將要被遷移到微云中進(jìn)行處理，此時(shí)其響應(yīng)時(shí)間為：

ri/Bc+2×LLAN+Lwait

(3)

移動(dòng)終端的能量消耗為：

Psend+(ri/Bc)×Prec

(4)

針對(duì)一組具有時(shí)序和數(shù)據(jù)依賴的任務(wù)，本文的遷移方案主要綜合了響應(yīng)時(shí)間和移動(dòng)終端能耗這兩方面的考慮，以期能夠在節(jié)約能耗的同時(shí)獲得較好的應(yīng)用性能。

在本文中，采用效用函數(shù)來(lái)表示最終的優(yōu)化結(jié)果，其公式如下：

(5)

α+β=1 0≤α≤1，0≤β≤1

(6)

因?yàn)樽罱K目標(biāo)是響應(yīng)時(shí)間最小并且終端能耗最低，所以效用值U越小即代表遷移方案越接近最優(yōu)，而此時(shí)所對(duì)應(yīng)的遷移方案S即為最終遷移方案。

3 基于任務(wù)依賴的計(jì)算遷移方法

根據(jù)以上描述，結(jié)合遺傳算法，本文提出了一個(gè)基于任務(wù)依賴的多任務(wù)遷移方法，以期獲得響應(yīng)時(shí)間和終端能耗總體較優(yōu)的遷移方案。遺傳算法是一種參照生物進(jìn)化規(guī)律而設(shè)計(jì)的隨機(jī)搜索方法，被廣泛用于解決此類(lèi)求全局最優(yōu)解的問(wèn)題[16]。遺傳算法模擬生物的遺傳規(guī)律，從初始個(gè)體出發(fā)，通過(guò)選擇、交叉和變異操作來(lái)產(chǎn)生新的個(gè)體，如此不斷進(jìn)化下去，直到滿足停止條件。

首先我們需要基于應(yīng)用中的任務(wù)數(shù)量設(shè)置與種群大小、染色體(chromosome)長(zhǎng)度等相對(duì)應(yīng)的參數(shù)值,然后根據(jù)參數(shù)值生成初代種群，種群中的每個(gè)染色體對(duì)應(yīng)于遷移方案，染色體中的每個(gè)基因?qū)?yīng)于任務(wù)所在的處理位置。之后可根據(jù)式(5)得出種群中每個(gè)個(gè)體的適應(yīng)性值，即效用函數(shù)U。然后，根據(jù)個(gè)體適應(yīng)性值進(jìn)行選擇操作，適應(yīng)性較優(yōu)的個(gè)體根據(jù)計(jì)算任務(wù)之間的雙重依賴關(guān)系進(jìn)行交叉、變異操作，操作之后產(chǎn)生的新個(gè)體遺傳到下一代種群。如此不停地迭代，直到滿足停止條件，產(chǎn)生結(jié)果。

3.1 種群初始化

種群初始化操作就是初始化計(jì)算任務(wù)的處理位置，對(duì)于一個(gè)任務(wù)vi的處理位置，隨機(jī)產(chǎn)生si={0,1，…,m}的隨機(jī)整數(shù)。在進(jìn)行初始化時(shí)，暫不考慮任務(wù)依賴對(duì)遷移的影響。用相同的方法遍歷所有的計(jì)算任務(wù)，可以獲得作為染色體的初始位置集合S0，并且染色體的長(zhǎng)度即基因數(shù)量由所有計(jì)算任務(wù)的數(shù)量確定。由于種群由多個(gè)染色體組成，因此在本文中，種群由矩陣pop表示。

3.2 適應(yīng)性值的計(jì)算

在遺傳算法中，每個(gè)染色體代表一個(gè)解，滿足最優(yōu)適應(yīng)性值的個(gè)體即為最優(yōu)解。為了在選擇過(guò)程中衡量每一個(gè)個(gè)體的優(yōu)異程度，需要設(shè)計(jì)一個(gè)能直接反映個(gè)體性能的適應(yīng)度函數(shù)，在本文中，效用函數(shù)U即為適應(yīng)度函數(shù)，由該函數(shù)計(jì)算得到的效用值即為適應(yīng)性值。

在計(jì)算個(gè)體的效用值之前，要將每個(gè)計(jì)算任務(wù)的具體描述以及任務(wù)之間的依賴關(guān)系輸入進(jìn)來(lái)。為了得到個(gè)體的效用值，首先我們要遍歷該個(gè)體的每一個(gè)基因值，根據(jù)其基因值所代表的任務(wù)處理位置，使用式(1)或式(3)可得出每個(gè)計(jì)算任務(wù)的響應(yīng)時(shí)間。其中，若多個(gè)并行的任務(wù)遷移到同一個(gè)微云進(jìn)行處理，則會(huì)出現(xiàn)等待現(xiàn)象，此時(shí)需要將處理時(shí)間較少的任務(wù)優(yōu)先處理，以降低等待時(shí)間。然后根據(jù)式(2)或式(4)可得出處理每個(gè)計(jì)算任務(wù)的終端能耗。

求這一組任務(wù)全部處理完時(shí)的響應(yīng)時(shí)間總和與終端能耗總和，此時(shí)需要結(jié)合兩個(gè)計(jì)算任務(wù)之間的依賴關(guān)系以及是否可以聯(lián)合遷移，將兩個(gè)任務(wù)之間進(jìn)行數(shù)據(jù)傳輸部分的響應(yīng)時(shí)間和終端能耗去掉。最后根據(jù)式(5)得出該個(gè)體的效用值。種群中的其他個(gè)體效用值可用同樣的方式計(jì)算得出。

3.3 選擇操作

選擇操作是選擇效用值較優(yōu)的部分染色體，并將其進(jìn)行交叉、變異操作產(chǎn)生適應(yīng)性更佳的下一代染色體。本文采用輪盤(pán)賭法來(lái)進(jìn)行選擇操作。首先，用下式計(jì)算第j個(gè)個(gè)體被選擇的概率，Uj表示第j個(gè)個(gè)體的效用值：

(7)

然后，計(jì)算個(gè)體k的累積概率以構(gòu)造輪盤(pán)：

(8)

最后進(jìn)行輪盤(pán)選擇，在[0,1]區(qū)間內(nèi)產(chǎn)生一個(gè)隨機(jī)數(shù)ms，若ms滿足如下條件：qk-1

算法1選擇操作算法

輸入：父代種群及每個(gè)個(gè)體的適應(yīng)值

輸出：進(jìn)行選擇操作之后的子代種群

BEGIN

1. 根據(jù)式(7)計(jì)算第j個(gè)個(gè)體被選擇的概率spj；

2. 根據(jù)式(8)計(jì)算個(gè)體k的累積概率qk，并將其放入矩陣中，以構(gòu)造輪盤(pán)；

3. fork=1到popsize

4. 在[0,1]區(qū)間產(chǎn)生一個(gè)隨機(jī)數(shù)ms；

5. ifms<=qk且ms>qk-1

6. 選擇個(gè)體k進(jìn)入子代種群；

7. end

8. end

END

3.4 交叉操作

例如，選擇兩個(gè)即將進(jìn)行交叉操作的父代個(gè)體Sp和Sq，并選取交叉點(diǎn)：

Sp=(s1,s2,s3,s4,s5,s6,|s7,s8,s9,s10)

算法2交叉操作算法

輸入：進(jìn)行選擇操作之后的種群

輸出：進(jìn)行交叉操作之后的子代種群

BEGIN

1. fori=1到popsize-1，每次循環(huán)i=i+2

2. 在[0,1]區(qū)間產(chǎn)生一個(gè)隨機(jī)數(shù)mr；

3. ifmr<交叉概率pc

4.cpoint=find1()；

5. ifcpoint==false

6. 跳出該次循環(huán)；

7. else

8. 將cpoint之后的基因進(jìn)行交叉；

9. end

10. end

11.find1()：

12. 定義尋找次數(shù)flag，并初始化為0；

13. do(在[0,1]區(qū)間產(chǎn)生隨機(jī)數(shù)mr1；

14.cpoint1=mr1*基因個(gè)數(shù)；

15. 將cpoint1進(jìn)行四舍五入得到cpoint；

16.flag=flag+1；)

17. while((h(vi,vcpoint)==2 &&si==scpoint)

18. &&flag<=10)

19. ifflag==11

20. return false；

21. else

22. returncpoint；

END

3.5 變異操作

采用上述變異操作所獲得的新個(gè)體具有較好的適應(yīng)性，也可以有效提高算法的收斂速度。

算法3變異操作算法

輸入：進(jìn)行交叉操作之后的種群

輸出：進(jìn)行變異操作之后的子代種群

BEGIN

1. fori=1到popsize

2. 在[0,1]區(qū)間產(chǎn)生一個(gè)隨機(jī)數(shù)mt；

3. ifmr<變異概率pm

4.mpoint=find2()；

5. ifmpoint==false

6. 跳出該次循環(huán)；

7. else

8. 進(jìn)行基因變異：

9.smpoint=si或smpoint=sj；

10. end

11. end

12.find2()：

13. 定義尋找次數(shù)flag，并初始化為0；

14. do(在[0,1]區(qū)間產(chǎn)生隨機(jī)數(shù)mt1；

15.mpoint1=mt1*基因個(gè)數(shù)；

16. 將mpoint1進(jìn)行四舍五入得到mpoint；

17.flag=flag+1；)

18. while((h(vi,vmpoint)==2 &&si==smpoint)

19. ‖(h(vmpoint,vj)==2 &&smpoint==sj)

20. &&flag<=10)

21. ifflag==11

22. return false；

23. else

24. returnmpoint；

END

3.6 得出結(jié)果

對(duì)于迭代的停止條件，一般有兩種方式：第一種是設(shè)置一個(gè)期望結(jié)果的界限，當(dāng)結(jié)果達(dá)到這個(gè)界限時(shí)，迭代停止；第二種就是設(shè)置迭代次數(shù)限制，當(dāng)?shù)螖?shù)達(dá)到限制次數(shù)時(shí)，迭代停止。

在本文中我們使用第二種迭代停止方式，我們?cè)O(shè)置一個(gè)最大迭代次數(shù)，當(dāng)?shù)螖?shù)達(dá)到設(shè)定的值之后就會(huì)停止，然后將適應(yīng)性U最優(yōu)的個(gè)體輸出，得到遷移方案S即為最終的遷移方案。

4 仿真實(shí)驗(yàn)和分析

在這一節(jié)中，將會(huì)對(duì)本文提出的假設(shè)及其實(shí)現(xiàn)算法進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證。為了驗(yàn)證方法的有效性，我們求取了另外三種遷移方案與本方法所求遷移方案進(jìn)行對(duì)比，分別是將計(jì)算任務(wù)全部放在終端進(jìn)行處理的無(wú)遷移方案、將計(jì)算任務(wù)在微云和終端隨機(jī)分配處理的遷移方案和將計(jì)算任務(wù)在微云平均分配處理的遷移方案。

將前文提到的效用值U作為性能指標(biāo)，最后將實(shí)驗(yàn)結(jié)果進(jìn)行分析總結(jié)。

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)在配置為3.4 GHz Intel(R) Core(TM) i3-4130 CPU和8 GB RAM的機(jī)器上運(yùn)行，操作系統(tǒng)為Windows 10，采用MATLAB 2016版軟件進(jìn)行編程仿真。本文主要考慮在商場(chǎng)等固定公眾場(chǎng)所下的微云場(chǎng)景，人們?cè)谛蓍e等待時(shí)往往會(huì)有實(shí)時(shí)游戲等娛樂(lè)需求，其周?chē)奈⒃茢?shù)量可設(shè)置為4。在實(shí)驗(yàn)進(jìn)行之前，首先要設(shè)置實(shí)驗(yàn)的參數(shù)，如移動(dòng)設(shè)備的性能、微云的性能以及在實(shí)驗(yàn)進(jìn)行中需要用到的參數(shù)等，各具體參數(shù)參照本文的部分參考文獻(xiàn)，并歸納分析，設(shè)置如表1-表3所示。

表1 移動(dòng)設(shè)備性能參數(shù)

表2 微云性能參數(shù) GHz

表3 其他參數(shù)

4.2 實(shí)驗(yàn)過(guò)程

在設(shè)置好實(shí)驗(yàn)參數(shù)之后，我們隨機(jī)生成一組計(jì)算任務(wù)，然后隨機(jī)生成各個(gè)計(jì)算任務(wù)之間的依賴關(guān)系，用一個(gè)二維矩陣表示：0表示兩個(gè)計(jì)算任務(wù)之間沒(méi)有依賴關(guān)系，1表示兩個(gè)計(jì)算任務(wù)之間只有時(shí)序依賴，2表示兩個(gè)計(jì)算任務(wù)之間存在時(shí)序和數(shù)據(jù)雙重依賴關(guān)系。

生成一組計(jì)算任務(wù)之后，就可以根據(jù)前文提出的算法將該組計(jì)算任務(wù)進(jìn)行遷移處理，然后得到實(shí)驗(yàn)結(jié)果，即效用值U和遷移方案S。

當(dāng)計(jì)算任務(wù)的數(shù)量是20時(shí)，隨機(jī)生成的一組計(jì)算任務(wù)和任務(wù)之間的依賴關(guān)系分別如表4和表5所示。

表4 計(jì)算任務(wù)的屬性

表5 任務(wù)之間的依賴關(guān)系h(vi,vj)

4.3 實(shí)驗(yàn)結(jié)果及分析

當(dāng)α=1、β=0時(shí)，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖1所示。最后得到的最小效用值為0.338 5，而平均分配方案和隨機(jī)分配方案的效用值分別為0.412 3和0.442 3。最終的遷移方案S={3,3,4,2,2,3,1,3,3,3,3,3,3,3,3,2,3,4,1,0}。

圖1 效用值隨迭代次數(shù)的變化

當(dāng)α=0、β=1時(shí)，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖2所示。最后得到的最小效用值為0.507 8，而平均分配方案和隨機(jī)分配方案的效用值分別為0.724 6和0.673 8。最終的遷移方案S={0,0,2,2,2,3,0,0,4,3,2,0,0,0,2,2,1,0,2,2}。

圖2 效用值隨迭代次數(shù)的變化

當(dāng)α=0.5、β=0.5時(shí)，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖3所示。最后得到的最小效用值為0.495 4，而平均分配方案和隨機(jī)分配方案的效用值分別為0.568 5和0.554 6。最終的遷移方案S={3,0,4,0,3,2,3,1,3,3,4,4,3,4,3,3,4,1,4,4}。

圖3 效用值隨迭代次數(shù)的變化

由圖1-圖3可以看出，隨著迭代次數(shù)的增多，效用值U是可以逐漸降低并最后得到一個(gè)最小值的，這說(shuō)明本文的遷移方法是有效的。

為了驗(yàn)證實(shí)驗(yàn)效果，在本文中，計(jì)算任務(wù)的數(shù)量分別設(shè)置為10、20、30、40和50。通過(guò)記錄多組的效用值U，最后生成比較圖。由于在計(jì)算效用值U時(shí)，選取了計(jì)算任務(wù)全部在終端進(jìn)行處理的無(wú)遷移方案作為分母，因此將計(jì)算任務(wù)全部放在終端進(jìn)行處理的無(wú)遷移方案的效用值等于1，并未在比較圖中畫(huà)出。

在圖4中，α=1、β=0，此時(shí)的效用值U僅表示響應(yīng)時(shí)間。

圖4 效用值隨計(jì)算任務(wù)數(shù)量的變化

在圖5中，α=0、β=1，此時(shí)效用值U僅表示終端的能量消耗。

圖5 效用值隨計(jì)算任務(wù)數(shù)量的變化

在圖6中，α=0.5、β=0.5，此時(shí)響應(yīng)時(shí)間和終端能量消耗對(duì)于效用值U的影響是相同的。

圖6 效用值隨計(jì)算任務(wù)數(shù)量的變化

綜合圖4-圖6可以看出，本文的遷移方法均可以得到相對(duì)最小的效用值，這說(shuō)明對(duì)于具有數(shù)據(jù)、時(shí)序依賴關(guān)系的一組任務(wù)而言，本文所提出的遷移方法確實(shí)可以得到更優(yōu)化的解，遷移方案S即為最終遷移方案。

5 結(jié) 語(yǔ)

本文針對(duì)移動(dòng)云環(huán)境下計(jì)算任務(wù)遷移的響應(yīng)時(shí)間和終端設(shè)備能耗綜合優(yōu)化問(wèn)題進(jìn)行了研究。針對(duì)延遲比較敏感且計(jì)算要求相對(duì)不高的多個(gè)相互依賴的任務(wù)，提出了一種基于遺傳算法思想的遷移方法。該方法根據(jù)計(jì)算任務(wù)的不同類(lèi)型和不同微云的分類(lèi)處理能力描述來(lái)計(jì)算遷移方案的效用值并完成選擇操作，基于各個(gè)任務(wù)之間的依賴關(guān)系來(lái)完成交叉和變異操作，從而通過(guò)多次迭代最終生成綜合效用值較優(yōu)的任務(wù)遷移方案。仿真實(shí)驗(yàn)結(jié)果表明，本文方法能有效減少移動(dòng)終端的響應(yīng)時(shí)間和能耗。

本文的研究仍然存在不足和值得進(jìn)一步研究的問(wèn)題，例如，如果移動(dòng)用戶處于移動(dòng)狀態(tài)，而且所應(yīng)用到的無(wú)線網(wǎng)絡(luò)也是會(huì)發(fā)生變化的。將用戶的移動(dòng)性和網(wǎng)絡(luò)的時(shí)變性加入到遷移模型中，更加貼合現(xiàn)實(shí)生活，再在此基礎(chǔ)上研究遷移方法，是未來(lái)的工作之一。