基于改進粒子群優(yōu)化的移動云應用卸載決策

李廷元

(中國民用航空飛行學院 計算機學院，四川 廣漢 618307)

0 引 言

移動互聯(lián)網(wǎng)的興起，使得人們在移動終端上執(zhí)行任務的需求越來越普遍，所執(zhí)行的任務類型也越來越多樣和復雜[1]。這類應用任務由大量非計算密集型任務和計算密集型任務構成。盡管元器件技術的更新?lián)Q代使得移動終端的處理能力大幅提高，但是對于處理計算密集型任務仍然存在瓶頸問題[2,3]。通過云計算技術，移動終端可以將自身任務提交至遠程無端執(zhí)行，即移動云計算技術[4,5]。移動云計算環(huán)境下，應用任務從本地移動終端提交至功能更強大的云端資源執(zhí)行，即為任務卸載技術[6-8]。由于任務卸載同時受到網(wǎng)絡傳輸帶寬資源及云端資源能力可用性的影響，任務卸載是否可以減小任務執(zhí)行延時需要綜合考慮。目前多數(shù)研究側重于研究如何卸載部分任務至遠程云端，以提升終端能效[9,10]。

目前的移動云環(huán)境中的任務卸載多集中于單站點環(huán)境[11,12]。然而，多站點環(huán)境下的任務卸載比單站點環(huán)境將擁有更好的性能表現(xiàn)。問題在于，多站點任務卸載求解是NP難問題。針對該問題，提出一種基于權重代價模型的多服務選擇任務卸載決策算法。算法以權重代價模型綜合考慮任務的執(zhí)行時間和能耗，然后利用粒子群優(yōu)化算法對任務卸載進行求解。同時，算法在粒子群優(yōu)化過程上做了一些改進，包括通過預定義粒子種群提升種群豐富性，通過改進初始化操作和粒子進化操作提高了得到最優(yōu)任務卸載決策的概率。

1 相關研究

文獻[13]利用整數(shù)線性規(guī)劃對任務卸載問題進行了求解，但僅僅優(yōu)化了能耗。文獻[14]同樣考慮了能耗目標，提出一種基于資源按需分配的任務卸載算法。文獻[11]引入網(wǎng)絡帶寬資源至任務卸載決策中，可以在執(zhí)行效率和能耗間進行多目標優(yōu)化。文獻[12]通過遺傳算法對工作流任務的卸載決策問題進行了求解，其適應度函數(shù)中綜合融入了執(zhí)行時間和執(zhí)行能耗，可以優(yōu)化綜合代價。文獻[15]提出一種任務卸載決策方法，在滿足執(zhí)行期限的同時對執(zhí)行能耗進行了優(yōu)化，可以實現(xiàn)任務分割的最優(yōu)解。文獻[16]在隨機無線信道中以路徑約束為基礎設計了一種自適應任務卸載算法，進一步降低了能耗。文獻[17]綜合考慮能耗、延遲、子任務執(zhí)行依賴，提出了聯(lián)合卸載算法。以上研究方法均是基于單站點環(huán)境的任務卸載決策問題，無法應用于多供應方的云服務環(huán)境。

文獻[18]利用粒子群優(yōu)化算法設計了多站點環(huán)境下的任務卸載策略，雖然綜合考慮了網(wǎng)絡帶寬和能耗問題，但算法復雜性較高，可能導致進行任務卸載決策的時間高于在本地終端上進行任務執(zhí)行的時間。文獻[19]提出一種基于螞蟻優(yōu)化算法的卸載決策算法，算法將收益和風險綜合考慮至卸載決策中，具有較好的可行性。然而，以上多站點環(huán)境下的任務卸載雖然有一定可行性，但是忽略了影響任務卸載決策的一些重要因素，如：在執(zhí)行延時、執(zhí)行能耗或網(wǎng)絡傳輸帶寬無法綜合考慮，而利用元啟發(fā)式方法得到的卸載決策復雜度過高等問題?；诖丝紤]，本文綜合考慮執(zhí)行時間和本地設備的執(zhí)行能耗，通過改進的粒子進化操作，對多重服務提供與選擇的任務卸載問題進行求解，并通過仿真實驗與同類算法的對比，驗證算法的可行性和有效性。

2 模 型

表1給出本文相關符號說明。

2.1 任務構成

表1 符號定義及其說明

2.2 面向多站點的計算卸載模型

本節(jié)將面向多站點的計算卸載模型形式為一個考慮應用總體執(zhí)行時間與總體執(zhí)行能耗的權重代價模型。

(1)權重代價模型

將多站點計算卸載問題描述如下：尋找最優(yōu)分割X’，滿足X’=argmin(W(X))。 當分割解為X時，權重代價W(X) 為

(1)

(2)

其中，Θ(X)為執(zhí)行時間，Φ(X)為執(zhí)行能耗，ΘLocal為本地執(zhí)行時間，ΦLocal為本地執(zhí)行能耗，時間權重wθ和能耗權重wφ用于決定用戶偏好，wθ=1且wφ=0為時間優(yōu)化模型，wθ=0且wφ=1為能耗優(yōu)化模型。

(2)時間模型

對于計算卸載決策解，執(zhí)行時間由所有任務單元在本地或云站點上的執(zhí)行時間與通信時間組成，任務執(zhí)行時間為節(jié)點權重。時間優(yōu)化模型目標是：尋找最優(yōu)分割X’，滿足X’=argmin(T(X))。 分割解X下執(zhí)行時間Θ(X)計算為

(3)

(4)

(5)

(6)

任務在本地執(zhí)行的時間由式(7)計算，在遠程云端執(zhí)行的時間由式(8)計算

(7)

(8)

(9)

(3)能耗模型

執(zhí)行能耗由任務執(zhí)行能耗和通信能耗組成。能耗優(yōu)化的目標是尋找最優(yōu)分割X’，滿足X’=argmin(Φ(X))。 分割解X下的執(zhí)行能耗Φ(X)為

(10)

約束條件為

(11)

(12)

(13)

(14)

(15)

其中，pCPU為移動設備CPU的功率，ptransfer為傳輸功率。

3 OMPSO算法設計

本文設計一種基于粒子群優(yōu)化的多站點計算卸載決策算法OMPSO，問題的解抽象為侯選粒子的集合，即粒子群。OMPSO算法中，每個粒子代表應用的一個分割解X，粒子由應用任務單元組成，即維度。粒子的每個維度附有一個值，代表分配給該任務的執(zhí)行站點，圖1代表一個算法中的粒子，OMPSO算法以最小化權重代價為目標，得到最優(yōu)分割X’。執(zhí)行步驟如下：

算法1： OMPSO

(1) Population Initialization

(2)Repeat

(3) Position Update//粒子位置更新

(4) Global_best Update//全局最優(yōu)解更新

(5)Untilthe stop criteria are reached//判定迭代結束條件

圖1 OMPSO算法中的粒子結構

3.1 種群初始化

該步驟初始化算法參數(shù)，包括：最大迭代次數(shù)I，粒子群模型SS，以及粒子本身也需要初始化。除了PSO中利用初始粒子群OS之外，算法還引入預留粒子群RS豐富OMPSO算法中的粒子。RS中的粒子(為任務分配的執(zhí)行站點)與OS具有很大不同，可獲得更高的適應度，這有助于豐富OMPSO中的粒子多樣性并降低搜索過程陷入局部最優(yōu)解。此外，多數(shù)遺傳和粒子群進化操作以隨機方式進行種群初始化，OMPSO算法將聯(lián)立預定義和隨機粒子的方式對粒子群進行初始化。根據(jù)移動云的卸載目標，由于任務卸載優(yōu)于本地執(zhí)行，算法先創(chuàng)建一個粒子，其所有任務單元均分配至本地執(zhí)行，這有助于在迭代中保護更有效的粒子(其執(zhí)行代價低于本地執(zhí)行代價)。另外，根據(jù)云端服務器的數(shù)量M，進行粒子初始化，其所有粒子均分配至一個云端服務器，生成M個粒子。剩余粒子則隨機產(chǎn)生。然后，為了獲得每個粒子群中的最優(yōu)粒子，以適應度對粒子排序，最優(yōu)個體被選擇為粒子群的全局最優(yōu)粒子。算法2為初始化過程。

算法2： Initialization-初始化

(1)setOSas original swarm,RSas reserve swarm

(2)set maximum iteration numberI,swarm sizeSS, application unit numberdand execution sitesS

(3)fori=1 toSdo

(4)forj=1 toddo

(5) OS[i][j]=i-1

(6)RS[i][j]=random[0,S-1]

(7)endfor

(8)endfor

(9)fori=S+1 toSSdo

(10)forj=1 toddo

(11)OS[i][j]=random[0,S-1]

(12)RS[i][j]=random[0,S-1]

(13)endfor

(14)endfor

(15)fori=1 toSSdo

(16)OS_fitness[i]=set fitness by Equ.1//計算初始粒子群適應度

(17)RS_fitness[i]=set fitness by Equ.16//計算預留粒子群適應度

(18)endfor

(19)Ascending SortOS_fitness//初始粒子群作適應度降序排列

(20)Ascending SortRS_fitness//預留粒子群作適應度降序排列

(21)global_bestOS=the best particle ofOS_fitness//選擇初始粒子群的最優(yōu)粒子

(22)global_bestRS=the best particle ofRS_fitness//選擇預留粒子群的最優(yōu)粒子

3.2 適應度函數(shù)

OMPSO算法中，初始粒子群的適應度函數(shù)定義為式(1)。由于使用了預留粒子群豐富粒子多樣性，基于預留粒子群的目標設計另一適應度函數(shù)，RS的適應度函數(shù)定義為

(16)

其中，SS表示粒子群規(guī)模，Pi表示OS中的第i個粒子，Pr表示RS中的給定粒子，H表示漢明距離函數(shù)，定義為

(17)

其中

(18)

FRS(r) 的漢明距離函數(shù)用于根據(jù)任務分配站點的不同計算給定粒子間的差異，gi,k表示初始種群中的粒子i的維度k，gr,k表示預留粒子群中的粒子r的維度k。

3.3 粒子更新

該步驟以維持在速度上的概率改變維度的分配站點(位置)至新站點，從而使粒子收斂至更優(yōu)解上。速度上保存概率是為了改變每個維度的分配站點到特定站點序號上。如圖2是OMPSO算法的速度表示。為了指定維度的值，需要從粒子群選擇3個最優(yōu)粒子。然后，每個粒子的對應維度根據(jù)OS和RS的局部適應度進行比較，兩種適應度分別定義為

(19)

(20)

(21)

(22)

(23)

(24)

每個粒子群中的粒子或者根據(jù)對應速度的概率改變其位置至速度的分配站點，或者保持在當前位置上。

圖2 OMPSO算法中粒子的速度表示

圖3 OMPSO算法的雜交繁育實例

算法3： Position Update-粒子位置更新

(1)fori=1 to 3do

(2)forj=1 toddo

(5)endfor

(6)endfor

(7)fori=1 to 3do

(8)forj=1 toddo

(11)endfor

(12)endfor

(13)fori=1 toSSdo

(14)OS[i]=update position byvel_prOS//更新初始粒子群粒子位置

(15)RS[i]= update position byvel_prRS//更新預留粒子群粒子位置

(16)endfor

(17)OS=crossbreeding(POSbest,PRSbest)//初始粒子群的雜交繁育

(18)RS=crossbreeding(POSbest,PRSbest) //預留粒子群的雜交繁育

(19)foritoSSdo

(20)OS_fitness[i]=set fitness by Equ.1//計算初始粒子群的適應度

(21)RS_fitness[i]=set fitness by Equ.16//計算預留粒子群的適應度

(22)endfor

(23)OS=keep the bestOSparticles//初始粒子群更新

(24)RS=keep the bestRSparticles//預留粒子群更新

3.4 全局最優(yōu)更新

該步驟中，當前迭代中每個粒子群中獲得的最優(yōu)粒子與粒子群的全局最優(yōu)global_best粒子比較，若當前迭代中的最優(yōu)粒子優(yōu)于全局最優(yōu)粒子，則更新全局適應度。當?shù)竭_預先定義的迭代次數(shù)或結果無法進一步更新時，OMPSO算法停止執(zhí)行。OS中獲得的全局最優(yōu)粒子選擇為多站點計算卸載問題的最優(yōu)分割解X’。

4 實驗評估

本節(jié)評估OMPSO算法的性能，以下將分別描述在仿真實驗和試驗臺實驗中的參數(shù)取值。實驗中，式(2)中的時間因子和能耗因子均等于0.5，即應用執(zhí)行對于執(zhí)行時間和執(zhí)行能耗具有同等的偏好，該取值可根據(jù)用戶應用的執(zhí)行需求進行調(diào)整。

4.1 仿真實驗環(huán)境配置

仿真實驗中，所有算法在配置為2.3GHz Intel core i7CPU和8 GB RAM的計算機上以JAVA實現(xiàn)。實驗分別利用從現(xiàn)實應用抽象出的任務圖和隨機任務圖進行仿真測試。為了評估應用規(guī)模的影響，實驗生成了擁有不同數(shù)量頂點和邊的不同隨機圖。對于現(xiàn)實應用的任務圖，3種SpecJvm基準統(tǒng)計的開源應用DB、JESS和RayTrace通過統(tǒng)計分析用于現(xiàn)實應用測試。表2和表3給出了隨機任務圖和現(xiàn)實任務圖的特征描述。假設現(xiàn)有4個執(zhí)行站點可用，包括一個本地站點和3個過程云服務器站點。網(wǎng)絡帶寬范圍為10 Kbytes/s～100 Kbytes/s，本地移動設備的CPU功率和數(shù)據(jù)傳輸功率與具體利用硬件相關，本文利用華為P6的硬件配置。

表2 隨機應用任務圖特征

表3 現(xiàn)實應用任務圖特征

4.2 參數(shù)影響

OMPSO算法的執(zhí)行首先需要獲得最適合的參數(shù)配置，本節(jié)將通過實驗獲取算法得到最優(yōu)結果時粒子群規(guī)模SS和最大迭代次數(shù)I，具體實驗場景見表4。

圖4和圖5描述了兩個參數(shù)對OMPSO的影響。圖4代表場景C1下粒子群規(guī)模SS對算法的影響，同時考慮了DB和RayTrace應用?？梢钥吹剑Ｗ尤阂?guī)模的增加對OMPSO有直接影響，且在SS=50時算法得到了最優(yōu)的適應度，大于50后，權重代價無明顯改進，故設置SS=50作為OMPSO算法的最優(yōu)粒子群規(guī)模。圖5代表場景C2下迭代次數(shù)I對算法的影響。隨著迭代次數(shù)的增加，在I=30時，算法得到了最優(yōu)適應度，繼續(xù)迭代并未對結果產(chǎn)生明顯影響。故設I=30作為OMPSO算法的最優(yōu)迭代次數(shù)。

表4 參數(shù)配置

圖4 粒子群規(guī)模對權重代價的影響

圖5 迭代次數(shù)對權重代價的影響

4.3 性能仿真對比研究

本節(jié)做算法的對比分析，實驗參數(shù)設置如4.2節(jié)所述，對比算法包括：

(1)本地執(zhí)行算法Local：該算法中所有應用任務均執(zhí)行于本地移動設備上，該算法可用于衡量其它算法得到的卸載增益；

(2)標準粒子群算法SPSO：該算法即為常規(guī)的PSO算法；

(3)MMRO算法[19]：該算法利用蟻群算法實現(xiàn)多站點任務卸載決策。

表5給出了算法做出卸載決策的時間，可以看到，算法卸載決策時間是相近的，但OMPSO的時間略長于MMRO和SPSO，這是由于算法計算卸載最優(yōu)解的粒子進化步驟有所改進導致的，但算法復雜度并未增加。

表5 算法卸載決策時間

圖6～圖8是迭代次數(shù)對任務總體執(zhí)行時間(圖6)、執(zhí)行能耗(圖7)和權重代價(圖8)的影響。實驗中傳輸帶寬設置為100 Kbytes/s，粒子群規(guī)模為50。圖中結果表明，Local算法由于在本地執(zhí)行所有任務，執(zhí)行時間不會發(fā)生變化，因為本地處理能力是固定的。由于本地處理能力遠小于云服務站點的處理能力，故Local算法在各項指標上均是最差的。OMPSO算法相比其它算法可以更少的迭代次數(shù)得到更優(yōu)解，表現(xiàn)在任務執(zhí)行時間、執(zhí)行能耗和權重代價均是最小的。與SPSO相比，OMPSO在初始化過程中引入預定義粒子群，使得初始粒子群中的粒子更加豐富且初始適應度更高，有利于后繼進化時的最優(yōu)解生成。而粒子更新中為不同類型粒子群定義不同適應度的方法也可以進一步使粒子進化加速收斂，也利于最優(yōu)解生成。而MMRO算法雖然利用蟻群優(yōu)化的思想可以降低應用執(zhí)行代價，但沒有根本解決局部收斂的問題，使得最終解并非真正的最優(yōu)解。

圖6 迭代次數(shù)對執(zhí)行時間的影響

圖7 迭代次數(shù)對執(zhí)行能耗的影響

圖8 迭代次數(shù)對權重代價的影響

圖9～圖11是傳輸帶寬對任務總體執(zhí)行時間、執(zhí)行能耗和權重代價的影響。顯然，增加帶寬會降低執(zhí)行時間，原因在于增加帶寬雖然未影響任務在站點上的執(zhí)行時間，但會降低數(shù)據(jù)的傳輸時間。OMPSO算法通過本文設計的粒子群進化機制更好生成了應用分割與卸載解，且在傳輸帶寬較低時，性能也未受到明顯影響。對比算法的性能結果在較低帶寬時甚至得到了比本地執(zhí)行更高的代價，這說明SPSO和MMRO算法僅在卸載環(huán)境擁有較高帶寬時才可能通過任務分割與卸載產(chǎn)生更小的權重代價，對帶寬的依賴性遠高于本文算法。綜合來看，OMPSO算法不僅在3個性能指標表現(xiàn)更高，并且對環(huán)境參數(shù)的改變具有更好的適應性。

圖9 傳輸帶寬對執(zhí)行時間的影響

圖10 傳輸帶寬對執(zhí)行能耗的影響

圖11 傳輸帶寬對權重代價的影響

4.4 實驗床對比研究

現(xiàn)實實驗床研究中，選取Huawei V9和Galaxy S6兩款智能手機作為移動設備，選擇3臺不同計算能力的計算機作為異構的遠程卸載服務器，配置8 G RAM，CPU配置分別為2.3 GHz core I7、1.6 GHz core I7和2.2 GHz core I5。作為執(zhí)行的移動樣本應用，選擇斐波那契算法、N-皇后求解和子串搜索求解3個問題運行于Android平臺上，以上3個問題在相應輸入規(guī)模n較大時，其執(zhí)行時間也較長。分別利用在手機Android平臺上的本地執(zhí)行方法和本文提出的OMPSO算法在不同的輸入值n下對以上問題進行求解。表6～表8的結果表明，CMPSO算法在執(zhí)行3種應用時得到的執(zhí)行時間優(yōu)于本地執(zhí)行算法。此外，算法得到的執(zhí)行時間均隨著n值的增加而增加，而本地設備在求解規(guī)模較大甚至無法求解出3個應用任務的解，這源于其本地設備RAM受限，執(zhí)行時間過長，此時以N表示。綜合來看，CMPSO算法可以比本地執(zhí)行更快獲得求解問題的解，驗證算法是有效可行的。

表6 斐波那契算法執(zhí)行時間/s

表7 N-皇后求解執(zhí)行時間/s

表8 子串搜索求解執(zhí)行時間/s

5 結束語

為了優(yōu)化移動云計算中應用執(zhí)行延時和移動設備能效，提出基于粒子群優(yōu)化的移動云應用卸載決策算法。算法利用了預定義和隨機粒子群方法混合生成粒子群的初始種群；為預定義的預留粒子群設計一種基于漢明距離函數(shù)的適應度函數(shù)，更好衡量粒子差異；為豐富種群多樣性，利用雜交繁育生成了變異粒子。改進粒子進化操作可以更合理地獲取應用分割的最優(yōu)解。仿真結果表明，改進算法在能耗、效率及綜合權重代價指標上均表現(xiàn)更好。