鄭利陽 劉茜萍

(南京郵電大學計算機學院江蘇省大數(shù)據(jù)安全與智能處理重點實驗室 江蘇 南京 210023)

0 引 言

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

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

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

1 相關工作

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

若從計算任務的處理位置來講，這些研究可大致分為兩類：第1類只考慮移動終端和遠程云端兩個處理位置[4-12]，第2類則考慮移動終端、微云和遠程云端三個處理位置[13-15]。遠程云端存儲資源豐富，處理計算任務的速度也非?？欤淙蝿仗幚頃r間相對移動終端而言幾乎可以忽略不計。然而，遠程云端往往距離用戶較遠，傳輸延遲較大，很多具有較高實時性要求的計算任務，并不適合遷移到遠程云端進行處理。與之相反，微云盡管存儲資源有限，處理計算任務的速度也相對遠端而言有所欠缺，但是它們距離用戶往往較近，傳輸延遲能得以大幅減少。

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

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

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

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

2.1 計算任務模型

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

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

2.2 計算資源模型

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

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

2.3 問題描述

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

(1)

移動終端的能量消耗為：

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

(2)

當si=1,2，…,k,…,m時，表示任務vi將要被遷移到微云中進行處理，此時其響應時間為：

ri/Bc+2×LLAN+Lwait

(3)

移動終端的能量消耗為：

Psend+(ri/Bc)×Prec

(4)

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

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

(5)

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

(6)

因為最終目標是響應時間最小并且終端能耗最低，所以效用值U越小即代表遷移方案越接近最優(yōu)，而此時所對應的遷移方案S即為最終遷移方案。

3 基于任務依賴的計算遷移方法

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

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

3.1 種群初始化

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

3.2 適應性值的計算

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

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

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

3.3 選擇操作

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

(7)

然后，計算個體k的累積概率以構造輪盤：

(8)

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

算法1選擇操作算法

輸入：父代種群及每個個體的適應值

輸出：進行選擇操作之后的子代種群

BEGIN

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

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

3. fork=1到popsize

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

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

6. 選擇個體k進入子代種群；

7. end

8. end

END

3.4 交叉操作

例如，選擇兩個即將進行交叉操作的父代個體Sp和Sq，并選取交叉點：

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

算法2交叉操作算法

輸入：進行選擇操作之后的種群

輸出：進行交叉操作之后的子代種群

BEGIN

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

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

3. ifmr<交叉概率pc

4.cpoint=find1()；

5. ifcpoint==false

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

7. else

8. 將cpoint之后的基因進行交叉；

9. end

10. end

11.find1()：

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

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

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

15. 將cpoint1進行四舍五入得到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 變異操作

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

算法3變異操作算法

輸入：進行交叉操作之后的種群

輸出：進行變異操作之后的子代種群

BEGIN

1. fori=1到popsize

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

3. ifmr<變異概率pm

4.mpoint=find2()；

5. ifmpoint==false

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

7. else

8. 進行基因變異：

9.smpoint=si或smpoint=sj；

10. end

11. end

12.find2()：

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

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

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

16. 將mpoint1進行四舍五入得到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é)果

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

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

4 仿真實驗和分析

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

將前文提到的效用值U作為性能指標，最后將實驗結(jié)果進行分析總結(jié)。

4.1 實驗設置

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

表1 移動設備性能參數(shù)

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

表3 其他參數(shù)

4.2 實驗過程

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

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

當計算任務的數(shù)量是20時，隨機生成的一組計算任務和任務之間的依賴關系分別如表4和表5所示。

表4 計算任務的屬性

表5 任務之間的依賴關系h(vi,vj)

4.3 實驗結(jié)果及分析

當α=1、β=0時，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖1所示。最后得到的最小效用值為0.338 5，而平均分配方案和隨機分配方案的效用值分別為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ù)的變化

當α=0、β=1時，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖2所示。最后得到的最小效用值為0.507 8，而平均分配方案和隨機分配方案的效用值分別為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ù)的變化

當α=0.5、β=0.5時，本文遷移方案的效用值U隨迭代次數(shù)的變化情況如圖3所示。最后得到的最小效用值為0.495 4，而平均分配方案和隨機分配方案的效用值分別為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是可以逐漸降低并最后得到一個最小值的，這說明本文的遷移方法是有效的。

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

在圖4中，α=1、β=0，此時的效用值U僅表示響應時間。

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

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

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

在圖6中，α=0.5、β=0.5，此時響應時間和終端能量消耗對于效用值U的影響是相同的。

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

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

5 結(jié) 語

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

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