李廷元

(中國(guó)民用航空飛行學(xué)院 計(jì)算機(jī)學(xué)院，四川 廣漢 618307)

0 引 言

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

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

1 相關(guān)研究

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

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

2 模 型

表1給出本文相關(guān)符號(hào)說(shuō)明。

2.1 任務(wù)構(gòu)成

表1 符號(hào)定義及其說(shuō)明

2.2 面向多站點(diǎn)的計(jì)算卸載模型

本節(jié)將面向多站點(diǎn)的計(jì)算卸載模型形式為一個(gè)考慮應(yīng)用總體執(zhí)行時(shí)間與總體執(zhí)行能耗的權(quán)重代價(jià)模型。

(1)權(quán)重代價(jià)模型

將多站點(diǎn)計(jì)算卸載問(wèn)題描述如下：尋找最優(yōu)分割X’，滿足X’=argmin(W(X))。 當(dāng)分割解為X時(shí)，權(quán)重代價(jià)W(X) 為

(1)

(2)

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

(2)時(shí)間模型

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

(3)

(4)

(5)

(6)

任務(wù)在本地執(zhí)行的時(shí)間由式(7)計(jì)算，在遠(yuǎn)程云端執(zhí)行的時(shí)間由式(8)計(jì)算

(7)

(8)

(9)

(3)能耗模型

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

(10)

約束條件為

(11)

(12)

(13)

(14)

(15)

其中，pCPU為移動(dòng)設(shè)備CPU的功率，ptransfer為傳輸功率。

3 OMPSO算法設(shè)計(jì)

本文設(shè)計(jì)一種基于粒子群優(yōu)化的多站點(diǎn)計(jì)算卸載決策算法OMPSO，問(wèn)題的解抽象為侯選粒子的集合，即粒子群。OMPSO算法中，每個(gè)粒子代表應(yīng)用的一個(gè)分割解X，粒子由應(yīng)用任務(wù)單元組成，即維度。粒子的每個(gè)維度附有一個(gè)值，代表分配給該任務(wù)的執(zhí)行站點(diǎn)，圖1代表一個(gè)算法中的粒子，OMPSO算法以最小化權(quán)重代價(jià)為目標(biāo)，得到最優(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//判定迭代結(jié)束條件

圖1 OMPSO算法中的粒子結(jié)構(gòu)

3.1 種群初始化

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

算法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//計(jì)算初始粒子群適應(yīng)度

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

(18)endfor

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

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

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

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

3.2 適應(yīng)度函數(shù)

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

(16)

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

(17)

其中

(18)

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

3.3 粒子更新

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

(19)

(20)

(21)

(22)

(23)

(24)

每個(gè)粒子群中的粒子或者根據(jù)對(duì)應(yīng)速度的概率改變其位置至速度的分配站點(diǎn)，或者保持在當(dāng)前位置上。

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

圖3 OMPSO算法的雜交繁育實(shí)例

算法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//更新預(yù)留粒子群粒子位置

(16)endfor

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

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

(19)foritoSSdo

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

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

(22)endfor

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

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

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

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

4 實(shí)驗(yàn)評(píng)估

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

4.1 仿真實(shí)驗(yàn)環(huán)境配置

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

表2 隨機(jī)應(yīng)用任務(wù)圖特征

表3 現(xiàn)實(shí)應(yīng)用任務(wù)圖特征

4.2 參數(shù)影響

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

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

表4 參數(shù)配置

圖4 粒子群規(guī)模對(duì)權(quán)重代價(jià)的影響

圖5 迭代次數(shù)對(duì)權(quán)重代價(jià)的影響

4.3 性能仿真對(duì)比研究

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

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

(2)標(biāo)準(zhǔn)粒子群算法SPSO：該算法即為常規(guī)的PSO算法；

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

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

表5 算法卸載決策時(shí)間

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

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

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

圖8 迭代次數(shù)對(duì)權(quán)重代價(jià)的影響

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

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

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

圖11 傳輸帶寬對(duì)權(quán)重代價(jià)的影響

4.4 實(shí)驗(yàn)床對(duì)比研究

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

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

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

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

5 結(jié)束語(yǔ)

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