基于改進粒子群優化的移動云應用卸載決策

李廷元

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

0 引 言

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

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

1 相關研究

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

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

2 模 型

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

2.1 任務構成

表1 符號定義及其說明

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

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

(1)權重代價模型

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

(1)

(2)

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

(2)時間模型

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

(3)

(4)

(5)

(6)

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

(7)

(8)

(9)

(3)能耗模型

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

(10)

約束條件為

(11)

(12)

(13)

(14)

(15)

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

3 OMPSO算法設計

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

算法1： OMPSO

(1) Population Initialization

(2)Repeat

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

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

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

圖1 OMPSO算法中的粒子結構

3.1 種群初始化

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

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

3.2 適應度函數

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

(16)

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

(17)

其中

(18)

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

3.3 粒子更新

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

(19)

(20)

(21)

(22)

(23)

(24)

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

圖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 全局最優更新

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

4 實驗評估

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

4.1 仿真實驗環境配置

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

表2 隨機應用任務圖特征

表3 現實應用任務圖特征

4.2 參數影響

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

圖4和圖5描述了兩個參數對OMPSO的影響。圖4代表場景C1下粒子群規模SS對算法的影響，同時考慮了DB和RayTrace應用。可以看到，粒子群規模的增加對OMPSO有直接影響，且在SS=50時算法得到了最優的適應度，大于50后，權重代價無明顯改進，故設置SS=50作為OMPSO算法的最優粒子群規模。圖5代表場景C2下迭代次數I對算法的影響。隨著迭代次數的增加，在I=30時，算法得到了最優適應度，繼續迭代并未對結果產生明顯影響。故設I=30作為OMPSO算法的最優迭代次數。

表4 參數配置

圖4 粒子群規模對權重代價的影響

圖5 迭代次數對權重代價的影響

4.3 性能仿真對比研究

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

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

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

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

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

表5 算法卸載決策時間

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

圖6 迭代次數對執行時間的影響

圖7 迭代次數對執行能耗的影響

圖8 迭代次數對權重代價的影響

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

圖9 傳輸帶寬對執行時間的影響

圖10 傳輸帶寬對執行能耗的影響

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

4.4 實驗床對比研究

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

表6 斐波那契算法執行時間/s

表7 N-皇后求解執行時間/s

表8 子串搜索求解執行時間/s

5 結束語

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