基于ILS-PSO 算法的移動云計算DAG 圖的任務(wù)調(diào)度研究與應(yīng)用*

董 韻 張 毅 孫 晉

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

移動云計算（Mobile Cloud Computing，MCC）的概念基于云計算提出，是云計算和移動網(wǎng)絡(luò)融合的產(chǎn)物，作為一種全新的交付模式，將任務(wù)分布在由大量移動設(shè)備構(gòu)成的網(wǎng)絡(luò)上。移動云計算的主要目標是利用云端的計算、存儲等資源優(yōu)勢，突破移動設(shè)備的資源限制，通過無線網(wǎng)絡(luò)以按需、可擴展的模式從云端獲得所需的基礎(chǔ)設(shè)施、平臺和軟件等［1～2］。

隨著4G 網(wǎng)絡(luò)成熟并廣泛應(yīng)用，移動通信開始朝向5G 的發(fā)展階段大步邁進，促進了移動網(wǎng)絡(luò)的飛速發(fā)展和移動應(yīng)用的極大豐富，移動設(shè)備已經(jīng)滲透到人們生活和工作的方方面面［3］。但是移動設(shè)備與傳統(tǒng)的PC設(shè)備相比較，具有計算速度慢、存儲容量少、安全性差等缺點，同時還存在電池容量的限制，移動設(shè)備的硬件缺陷成為了移動應(yīng)用智能化發(fā)展的瓶頸［4］。

通過將云計算引入移動網(wǎng)絡(luò)，將移動應(yīng)用遷移到移動設(shè)備網(wǎng)絡(luò)中執(zhí)行，來彌補單個移動設(shè)備計算速度慢、存儲容量少的缺點，減少移動設(shè)備所消耗的電量，保證整個網(wǎng)絡(luò) QoS［5～6］，縮短移動應(yīng)用的執(zhí)行時間。

移動云計算的任務(wù)調(diào)度是一種組合優(yōu)化問題，已被證明是NP 完全問題，無法在多項式時間內(nèi)求解［7～8］。目前對于移動云計算的任務(wù)調(diào)度的研究成果［9～11］，大多是針對同構(gòu)設(shè)備構(gòu)成的網(wǎng)絡(luò)提出的，對于異構(gòu)設(shè)備網(wǎng)絡(luò)下的任務(wù)調(diào)度研究有待進一步深入。任務(wù)調(diào)度問題根據(jù)任務(wù)類型的不同分為獨立任務(wù)調(diào)度和關(guān)聯(lián)任務(wù)調(diào)度，關(guān)聯(lián)任務(wù)調(diào)度更符合于實際應(yīng)用的運行情況。

電池容量是移動設(shè)備本身具有的局限性，是移動云計算的一種內(nèi)在的約束性，本文針對移動云計算異構(gòu)設(shè)備網(wǎng)絡(luò)的任務(wù)調(diào)度問題，移動設(shè)備的電池容量能夠滿足所執(zhí)行任務(wù)消耗電量的前提下，提出了一種應(yīng)用迭代局部搜索策略（ILS）的粒子群優(yōu)化算法（PSO），求解最優(yōu)調(diào)度方案的方法，并在Cloud-Sim 云計算仿真平臺上進行實驗以驗證算法的有效性。

2 任務(wù)調(diào)度數(shù)學模型

使用DAG 圖對移動云計算環(huán)境下的應(yīng)用進行建模，記作DAG={T，E，W}，節(jié)點集T={t1，t2，…，tn}表示任務(wù)的集合；E是有向邊的集合，從ti指向tj的有向邊記作eij，如果eij∈E，表示任務(wù)ti和tj之間存在依賴關(guān)系，tj要在ti完成之后才能執(zhí)行；W是有向邊的權(quán)值集合，?eij∈E存在|eij|∈W，表示ti和tj之間的通信量。

網(wǎng)絡(luò)中的移動設(shè)備集記為D={d1，d2，…，dm} ，移動設(shè)備的計算性能為MIPS={mips1，mips2，…，

由于移動設(shè)備資源受限，無法滿足如視頻處理、實時大數(shù)據(jù)分析等復(fù)雜應(yīng)用的要求，阻礙了此類應(yīng)用在移動云計算環(huán)境下的有效運行。對于可用有向無環(huán)圖（Directed Acyclic Graph，DAG）表示的應(yīng)用，在移動云環(huán)境中將應(yīng)用劃分成多個不相交的集合分配至移動設(shè)備上執(zhí)行，使得每個移動設(shè)備的可用資源能滿足所分配部分的資源要求。如何有效劃分應(yīng)用是移動云計算領(lǐng)域的重要研究問題，稱為應(yīng)用劃分問題，也稱為任務(wù)調(diào)度［12］。

2.1 數(shù)學模型

mipsm}表示，電池容量為BC={bc1，bc2，…，bcm} 。由于移動云網(wǎng)絡(luò)是異構(gòu)的，移動設(shè)備的處理性能各不相同，任務(wù)在各個設(shè)備執(zhí)行所需時間也各不相同 。使 用 向 量ci={ci1，…，cin}={s(ti)mips1，…，s(ti)mipsn}表示任務(wù)ti在各移動設(shè)備上的執(zhí)行時間，s(ti)是任務(wù)ti的長度。

為了便于確定任務(wù)的開始執(zhí)行時間和構(gòu)建任務(wù)間的依賴關(guān)系，定義DAG 圖上任務(wù)的高度height［13］：

其中ti∈T，pred(ti)是任務(wù)ti的前驅(qū)任務(wù)集合。任務(wù)高度函數(shù)可以表示任務(wù)之間執(zhí)行關(guān)系，如果從ti到tj之間存在一條路徑，則有ti在tj之前執(zhí)行并且height(ti)＜height(tj)；如果兩個任務(wù)之間不存在路徑，那么它們之間的執(zhí)行順序可以是任意的，但是要保證處理器之間的優(yōu)先關(guān)系。任務(wù)高度height的缺點是最優(yōu)的任務(wù)調(diào)度方案可能無法滿足式（1），為減少這種可能性的發(fā)生，定義任務(wù)高度height［'14］：

其中，succ(ti)是ti的后繼任務(wù)的集合，rand(a，b)是在區(qū)間[a，b] 上的隨機整數(shù)。沒有前驅(qū)節(jié)點的任務(wù)稱為入口任務(wù)，對應(yīng)著height'最小的節(jié)點；沒有后繼節(jié)點的任務(wù)稱為出口任務(wù)，對應(yīng)著height'最大的節(jié)點。為方便研究，規(guī)定DAG 任務(wù)圖只有一個入口任務(wù)和一個出口任務(wù)。

2.2 優(yōu)化目標

為了方便研究，除了上述數(shù)學模型，做出如下假設(shè)：1）任務(wù)是非搶占的，相同任務(wù)不能同時在兩個及以上移動設(shè)備上運行；2）每個虛擬機同一時刻只能處理一個任務(wù)；3）具有依賴關(guān)系的任務(wù)，前驅(qū)任務(wù)執(zhí)行完成，后繼任務(wù)獲得依賴數(shù)據(jù)后才能執(zhí)行；4）具有依賴關(guān)系的任務(wù)分配在不同移動設(shè)備執(zhí)行時才考慮網(wǎng)絡(luò)通信開銷；5）移動設(shè)備網(wǎng)絡(luò)是全互連結(jié)構(gòu)，每個移動設(shè)備到任意設(shè)備都存在路徑。

移動云計算任務(wù)調(diào)度的目標函數(shù)定義如下：移動云計算的DAG 任務(wù)圖中的任務(wù)分配給特定的移動設(shè)備，使得應(yīng)用的完成時間最小，形式化描述如下：

其中F 是可行調(diào)度方案集，f 是一種可行的調(diào)度方案，makespan是移動設(shè)備上最后一個任務(wù)的完成時間，F(xiàn)T 是在調(diào)度方案f 下應(yīng)用的最早完成時間［15］。

分配到設(shè)備dj的任務(wù)集T，應(yīng)滿足在移動設(shè)備上執(zhí)行任務(wù)所消耗的電量不應(yīng)超過設(shè)備的電池容量，則目標函數(shù)應(yīng)該滿足如下條件：

其中Wj是移動設(shè)備dj的功率，sumj是在dj上執(zhí)行的任務(wù)的長度之和，應(yīng)滿足分配給各個移動設(shè)備的任務(wù)個數(shù)之和等于任務(wù)總數(shù)n。

3 粒子群優(yōu)化算法

粒子群優(yōu)化（Particle Swarm Optimizer，PSO）算法是由R.C.Eberhart 博士和J.Kennedy 博士提出的一種仿生智能的全局優(yōu)化算法［16～17］。種群中的個體稱為粒子，粒子具有簡單的行為規(guī)則，從而使種群表現(xiàn)出復(fù)雜的特性。粒子根據(jù)自身經(jīng)歷過的最優(yōu)位置和種群經(jīng)歷過的最優(yōu)位置更新位置和速度，經(jīng)過多次迭代搜索解出空間的最優(yōu)解，用于求解復(fù)雜的優(yōu)化問題［18］。

在d 維搜索空間中，P={p1，p2，…，pM}表示由M 個粒子組成的種群，向量xi={xi1，xi2，…，xid}和vi={vi1，vi2，…，vid}分別表示粒子pi的位置和速度。粒子pi經(jīng)歷過的最優(yōu)位置記為pbesti，而種群經(jīng)歷過的最優(yōu)位置記為gbest。粒子pi根據(jù)pbesti和gbest，利用式（4）和（5）更新自己的位置xi和速度vi。

其中t 為當前迭代次數(shù)，T 為最大迭代次數(shù)。學習因子c1、c2取值都為2［19］，r1、r2為區(qū)間［0，1］上的隨機數(shù)。ω為慣性權(quán)重，采用文獻［20］提出的線性遞減策略動態(tài)調(diào)整慣性權(quán)重策略，其中ωmax和ωmin分別是ω的最大值和最小值，根據(jù)文獻［21］，本文取ωmax=0.9，ωmin=0.2。此外，為了防止粒子飛出解空間，設(shè)定速度的邊界值Vmax。

3.1 離散與編碼

移動云計算的任務(wù)調(diào)度是組合優(yōu)化問題，粒子的位置和速度要用離散的方式表示，而PSO算法是基于連續(xù)空間的優(yōu)化問題，導致粒子的位置不能按照式（4）和（5）進行更新［22］。為使PSO 算法能夠在離散組合優(yōu)化問題中得到有效應(yīng)用，本文采取一種基于任務(wù)自然數(shù)的編碼方式，編碼長度取決于任務(wù)數(shù)量，如n任務(wù)m移動設(shè)備的調(diào)度問題，用n維向量編碼{c1，c2…，cn} 表示粒子的位置，編碼的第i維分量ci∈{1 ，2，…，m} ，表示將任務(wù)ti分配到移動設(shè)備dci上執(zhí)行。

使用編碼的方式可以將PSO 算法應(yīng)用于求解離散空間組合優(yōu)化問題，按照式（4）和（5）更新后的粒子位置向量可能不符合本文提出的編碼，則可以如下方法對更新后的粒子位置向量進行再調(diào)整：給出 一個粒 子位置 向 量x={x1，x2，…，xn} ，如 果xi∈[-m，0 )∪(0 ，m]，則 更 新如果xi∈(- ∞，-m)∪(m，+∞ )，則更新如果xi=0，則更新xi為{1 ，2，…，m} 上的隨機值。

3.2 適應(yīng)度

本文采用總完成時間FT 作為粒子的適應(yīng)度，同時考慮移動設(shè)備的電池容量的約束。適應(yīng)度作為優(yōu)化的目標，可以作為粒子的評價標準，粒子的適應(yīng)度越小，越容易被選擇作為潛在的最優(yōu)解。粒子的適應(yīng)度計算方法如算法1所示。

算法1 粒子適應(yīng)度的計算方法

輸入 移動云計算的DAG 任務(wù)圖，粒子的位置編碼x，網(wǎng)絡(luò)帶寬（bps），移動設(shè)備網(wǎng)絡(luò)（處理性能、電池容量等）

輸出 粒子的適應(yīng)度FT

step1 計算DAG圖中每個任務(wù)的高度height'；

step2 為所有任務(wù)建立隊列；

step3 按照height'遞增的順序?qū)θ蝿?wù)隊列排序，height'相同的則按照任務(wù)編號遞增排序；

step4 如果任務(wù)隊列非空，轉(zhuǎn)到step5；否則，轉(zhuǎn)到step10；

step5 從任務(wù)隊列的頭部取出一個任務(wù)為tk；

step6 根據(jù)粒子位置編碼x 將任務(wù)tk分配到移動設(shè)備dxk上執(zhí)行；

step7 計算tk在dxk上的執(zhí)行所需時間，記為time；

step8 tk獲得設(shè)備的時間記為GainTime，經(jīng)過Delay 時間的通信延時，tk獲得所有的依賴數(shù)據(jù)，則tk的完成時間為GainTime+Delay+Time（如果存在依賴關(guān)系的任務(wù)在相同移動設(shè)備上執(zhí)行，則通信開銷cost=0 ；否則cost=通信量/bps。Delay=max(costi)）；

step9 tk執(zhí)行完成后，從任務(wù)隊列中刪除tk，轉(zhuǎn)到step4；

step10如果所有移動設(shè)備的電池容量可以滿足在其上執(zhí)行任務(wù)消耗的電量，轉(zhuǎn)到step11；否則轉(zhuǎn)到step12；

step11輸出所有的移動設(shè)備中最后一個任務(wù)的完成時間，轉(zhuǎn)到step13；

step12輸出∞，轉(zhuǎn)到step13

step13算法結(jié)束。

3.3 PSO求解任務(wù)調(diào)度問題

PSO 算法將任務(wù)高度height'，使用算法1 的方法作為粒子的適應(yīng)度函數(shù)，使用全局模型進行粒子更新，最優(yōu)粒子為適應(yīng)度最小的粒子。PSO 求解移動云計算任務(wù)調(diào)度問題的過程如算法2所示。

算法2 PSO求解任務(wù)調(diào)度問題

輸入 移動云計算的DAG 任務(wù)圖，網(wǎng)絡(luò)帶寬（bps），移動設(shè)備網(wǎng)絡(luò)（處理性能、電池容量等），粒子數(shù)

輸出 全局最優(yōu)的調(diào)度方案

step1 計算DAG圖中每個任務(wù)的高度height'；

step2 初始化PSO 的相關(guān)參數(shù)，設(shè)置最大迭代次數(shù)T和當前迭代次數(shù)t=0；

step3 使用離散編碼的方式，初始化種群粒子的位置為{1 ，2，…，m} 中的隨機值；初始化種群粒子的速度為[-Vmax，Vmax] 上的隨機數(shù)；

step4 計算種群中每個粒子pi的適應(yīng)度FT(pi)；

step5 如果FT(pi)＜FT(pbesti)，轉(zhuǎn)到 step6；否則，轉(zhuǎn)到step7；

step6 粒子pi當前位置xi為自身經(jīng)歷過的歷史最優(yōu)位置，更新pbesti=xi；

step7 如果FT(pi)＜FT(gbest)，轉(zhuǎn)到step8；否則，轉(zhuǎn)到step9；

step8 粒子pi當前位置xi為種群的歷史最優(yōu)位置，更新gbest=xi；

step9 根據(jù)式（4）和（5），更新粒子位置xi和速度vi；

step10t=t+1；

step11如果t小于T，轉(zhuǎn)到step4，否則轉(zhuǎn)到step12；

step12輸出gbest；

step13算法結(jié)束。

3.4 迭代局部搜索

在調(diào)度問題中，PSO 算法的優(yōu)化過程都是從初值出發(fā)，求解初值所在鄰域的極值，存在著過早收斂，搜索精度不高等缺點，容易陷入局部最優(yōu)解，無法保證是解空間的最優(yōu)解［23］。為了避免算法陷入局部最優(yōu)，則需要提出一種擾動策略，為搜索找到新的方向。

迭代局部搜索（Iterated Local Search，ILS）是一種元啟發(fā)式算法，為局部搜索策略提供簡單、強大而高效的框架，成功地應(yīng)用于TSP 問題，車間調(diào)度和背包問題等領(lǐng)域［24］。ILS使用PSO搜索到的最優(yōu)解作為當前解，通過擾動到當前解的鄰近區(qū)間尋求更優(yōu)的解更新當前解，直到無法改進為止，作為近似全局最優(yōu)解，這是一種可行的全局優(yōu)化方案。

交換是最常用的擾動策略，分為鄰位交換和一般交換。鄰位交換是指將粒子位置編碼的第i個和i+1個分量互換；一般交換是指將粒子位置編碼第i個和j個分量互換（i≠j）。一般交換的方法可能擾動作用過于強烈，所以本文采用鄰位交換的擾動方式。

將迭代局部搜索應(yīng)用于任務(wù)調(diào)度問題，最大未改進次數(shù)（MAX_UNMODIFIED_COUNT）是最常用的終止條件。根據(jù)文獻［25］，考慮將最大未改進次數(shù)設(shè)為80，最終可以得到更好的解。

將PSO 算法作為ILS 局部搜索方法，求解移動云計算任務(wù)調(diào)度問題的過程由算法3給出。

算法3 ILS-PSO求解任務(wù)調(diào)度問題

輸入 移動云計算的DAG 任務(wù)圖，網(wǎng)絡(luò)帶寬（bps），移動設(shè)備網(wǎng)絡(luò)（處理性能、電池容量等），粒子數(shù)

輸出 全局最優(yōu)的調(diào)度方案

step1 計算DAG圖中每個任務(wù)的高度height'；

step2 初始化PSO 和ILS 的相關(guān)參數(shù)，最大迭代次數(shù)T和最大未改進次數(shù)MAX_UNMODIFIED_COUNT；

step3 初始化當前未改進次數(shù)k=0；

step4 使用離散編碼的方式，初始化種群粒子的位置為{1 ，2，…，m} 中的隨機值；初始化種群粒子的速度為[-Vmax，Vmax] 上的隨機數(shù)；

step5 執(zhí)行PSO搜索，搜索結(jié)果gbest賦值給sbest；

step6 k ＜ MAX_UNMODIFIED_COUNT，則轉(zhuǎn)到step7；否則，轉(zhuǎn)到step12；

step7 使用鄰位交換的方法對粒子的位置編碼進行擾動；

step8 執(zhí)行PSO搜索，結(jié)果gbest賦值給slocal；

step9 如果FT(slocal)＜FT(sbest)，轉(zhuǎn)到step10；否則，轉(zhuǎn)到step11；

step10sbest=slocal，k=0，轉(zhuǎn)到step6；

step11k=k+1，轉(zhuǎn)到step6；

step12輸出sbest；

step13算法結(jié)束。

4 實驗與分析

本文采用CloudSim作為仿真環(huán)境，對移動云計算任務(wù)調(diào)度問題進行仿真，實驗環(huán)境為Microsoft Windows 7 專 業(yè) 版 、Intel Core i7-6700 3.40GHz、8.00G RAM、CloudSim-3.0.3、Eclipse。

參數(shù)設(shè)置：

1）PSO的相關(guān)參數(shù)：c1=2，c2=2，r1、r2為區(qū)間［0，1］上的隨機數(shù)，ωmin=0.2 ，ωmax=0.9 ，Vmax=1。

2）ILS 的相關(guān)參數(shù)：最大未改進次數(shù)設(shè)置為MAX_UNMODIFIED_COUNT=80。

3）移動云計算的設(shè)備網(wǎng)絡(luò)由5 個移動設(shè)備構(gòu)成，網(wǎng)絡(luò)帶寬bps=1，移動設(shè)備的處理性能和可提供給任務(wù)的最長可執(zhí)行時間（即電池容量/功率）如下所示：

實驗設(shè)計：

1）粒子數(shù)為100，任務(wù)數(shù)為100，最大迭代次數(shù)為100，觀察隨著當前迭代次數(shù)的增加，PSO優(yōu)化性能的變化。

2）粒子數(shù)為100，任務(wù)數(shù)為100，最大迭代次數(shù)從0 遞增到100，觀察最大迭代次數(shù)對PSO 和ILS-PSO尋優(yōu)的影響。

3）最大迭代次數(shù)為100，粒子數(shù)為100，任務(wù)數(shù)從0 遞增到300，觀察輪轉(zhuǎn)算法（RR），貪心算法（Greedy）、PSO 和 ILS-PSO 求解不同數(shù)目的任務(wù)調(diào)度問題的性能差異。

本文采用文獻［26］的方法，根據(jù)任務(wù)數(shù)隨機生成DAG 任務(wù)圖，任務(wù)的長度為[2 0000，30000] 上的隨機整數(shù)。每個實驗重復(fù)20 次，實驗結(jié)果取平均值來降低誤差。

實驗1結(jié)果如圖1所示?？梢钥闯鯬SO具有優(yōu)化性能好、快速收斂的優(yōu)點，然而迭代進行到了40次左右的時候，優(yōu)化陷入了局部最優(yōu)解，隨著迭代次數(shù)的增加，搜索性能不再有明顯變化。

實驗2 結(jié)果如圖2 所示。由實驗1 的結(jié)果可以，迭代次數(shù)到達45 次左右時，PSO 算法進入局部最優(yōu)，所以最大迭代次數(shù)小于45 的時候，隨著最大迭代次數(shù)的增加，PSO 搜索性能持續(xù)提升；當最大迭代次數(shù)接近并且超過45 的時候，PSO 搜索性能提升緩慢直到不再有明顯變化。對于ILS-PSO 算法，當PSO 搜索陷入局部最優(yōu)時，通過多次擾動到臨近區(qū)間迭代求解更優(yōu)解，求解出近似全局最優(yōu)解。

圖1 實驗1的結(jié)果

圖2 實驗2的結(jié)果

圖3 實驗3的結(jié)果

實驗3 的結(jié)果如圖3 所示。可知PSO 和ILS-PSO 在初期搜索優(yōu)勢并不明顯，這是由于任務(wù)數(shù)量較少時，DAG 圖的復(fù)雜程度較低，可以使用Greedy 算法求解出較好的結(jié)果。隨著任務(wù)數(shù)量的增加，DAG 圖的復(fù)雜程度劇增，可以看出RR 和Greedy 的最大完成時間與任務(wù)數(shù)量近似成正比。由于存在迭代搜索過程，在中后期PSO 和ILS-PSO的搜索效果明顯優(yōu)于RR 和Greedy，同時ILS-PSO為防止PSO搜索進入局部最優(yōu)應(yīng)用了擾動策略，迭代搜索出近似全局最優(yōu)解，所以ILS-PSO 的搜索性能優(yōu)于PSO，并且隨著問題復(fù)雜程度的增加，優(yōu)勢更加明顯。

在三種情況下進行仿真實驗，結(jié)果表明了本文所提出的ILS-PSO 調(diào)度算法可以有效提高移動云計算環(huán)境下的系統(tǒng)處理調(diào)度問題，減少了總?cè)蝿?wù)的完成時間，提高了移動設(shè)備的利用效率，在時間性能和優(yōu)化性能上取得了較好的效果。

5 結(jié)語

異構(gòu)移動設(shè)備網(wǎng)絡(luò)和移動設(shè)備的電池容量限制是影響移動云計算環(huán)境下任務(wù)調(diào)度執(zhí)行效率最具有挑戰(zhàn)性的關(guān)鍵因素。本文分析了當前移動云計算任務(wù)調(diào)度的研究現(xiàn)狀和移動設(shè)備存在的客觀約束的基礎(chǔ)上，提出了適用于異構(gòu)移動設(shè)備網(wǎng)絡(luò)下的DAG 任務(wù)圖的ILS-PSO 算法求解全局最優(yōu)調(diào)度方案。通過位置編碼的方式，將連續(xù)空間的優(yōu)化問題和離散空間的調(diào)度問題聯(lián)系起來，將任務(wù)高度作為任務(wù)的優(yōu)先級，PSO 算法作為搜索方法，從而得到高效的調(diào)度方案，提高了資源利用率，也縮短了程序的完成時間。為防止PSO搜索陷入局部最優(yōu)，應(yīng)用迭代局部搜索策略，通過擾動方法到局部解的鄰近區(qū)間尋求更優(yōu)解更新當前解，最終找到近似全局最優(yōu)解。最后通過實驗仿真，驗證了本文提出的ILS-PSO算法的有效性。