基于多微云協(xié)作的計(jì)算任務(wù)卸載

王慶永，毛鶯池，王繹超，王龍寶

（河海大學(xué)計(jì)算機(jī)與信息學(xué)院，南京211100）

0 引言

隨著物聯(lián)網(wǎng)的不斷發(fā)展，智能手機(jī)等多種移動(dòng)設(shè)備性能大幅提升，移動(dòng)設(shè)備已經(jīng)應(yīng)用到人們生活中的方方面面，從視頻影音、電子商務(wù)、社交網(wǎng)絡(luò)等領(lǐng)域改變著人們的生活行為方式。由于應(yīng)用程序的功能逐漸豐富，程序計(jì)算更加復(fù)雜，移動(dòng)設(shè)備的有限計(jì)算資源成為了移動(dòng)設(shè)備發(fā)展的瓶頸。移動(dòng)云計(jì)算（Mobile Cloud Computing，MCC）作為移動(dòng)互聯(lián)網(wǎng)和云計(jì)算相結(jié)合的產(chǎn)物，利用云端強(qiáng)大的存儲(chǔ)和計(jì)算資源能力，讓用戶方便地將計(jì)算任務(wù)卸載到云中，突破了移動(dòng)設(shè)備的資源限制，能為用戶提供更豐富的資源和更好的使用體驗(yàn)，顯著提升了服務(wù)質(zhì)量（Quality of Service，QoS）［1］。移動(dòng)云計(jì)算中的任務(wù)卸載技術(shù)可以將移動(dòng)設(shè)備上的任務(wù)以部分代碼或整個(gè)應(yīng)用的形式遷移到云端，利用云端強(qiáng)大的計(jì)算能力減少運(yùn)行時(shí)間并降低移動(dòng)設(shè)備能耗。但移動(dòng)設(shè)備訪問(wèn)遠(yuǎn)程云容易受到網(wǎng)絡(luò)連接的影響，可能出現(xiàn)傳輸時(shí)延過(guò)大或斷線等問(wèn)題。為了解決這個(gè)問(wèn)題，基于微云（Cloudlet）的計(jì)算模式被提出。微云是一種網(wǎng)絡(luò)邊緣的小型云，可以讓云中的存儲(chǔ)和計(jì)算資源更接近終端用戶，減少卸載過(guò)程中的網(wǎng)絡(luò)傳輸開(kāi)銷［2］。

微云通常以分布式的方式部署在各個(gè)區(qū)域中，為服務(wù)范圍內(nèi)的用戶提供存儲(chǔ)和計(jì)算資源。由于用戶分布的不均勻性和任務(wù)請(qǐng)求到達(dá)的隨機(jī)性，不同微云中的任務(wù)數(shù)量存在明顯差異。如果通過(guò)多微云協(xié)作的方式，將部分任務(wù)卸載到不同微云中運(yùn)行，可以有效縮短任務(wù)響應(yīng)時(shí)間。

本文所研究的移動(dòng)云計(jì)算任務(wù)卸載問(wèn)題基于微云架構(gòu)，將部分計(jì)算任務(wù)卸載到微云中運(yùn)行，與遠(yuǎn)程云相比可有效減少數(shù)據(jù)傳輸開(kāi)銷。基于微云架構(gòu)的計(jì)算任務(wù)卸載面臨三個(gè)挑戰(zhàn)：

1）近些年來(lái)的研究主要集中在單用戶卸載問(wèn)題上。在實(shí)際場(chǎng)景中，需要考慮到多個(gè)用戶對(duì)微云資源的競(jìng)爭(zhēng)，在制定卸載決策時(shí)需要為每個(gè)任務(wù)選擇合適的卸載地點(diǎn)。

2）現(xiàn)有的多用戶卸載策略大多將微云或邊緣服務(wù)器當(dāng)作獨(dú)立的資源，忽略了微云或邊緣服務(wù)器的協(xié)作。多用戶之間的任務(wù)卸載決策不僅取決于用戶自己的計(jì)算量開(kāi)銷，還應(yīng)考慮微云計(jì)算資源的限制。實(shí)際上，微云或邊緣服務(wù)器的協(xié)作，不僅可以有效平衡服務(wù)器的負(fù)載，還可以保證物聯(lián)網(wǎng)用戶設(shè)備的服務(wù)質(zhì)量。

3）基于多微云的計(jì)算任務(wù)卸載問(wèn)題是帶有約束條件的整數(shù)規(guī)劃問(wèn)題，該問(wèn)題為NP-hard 問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)，算法數(shù)學(xué)求解復(fù)雜度過(guò)高。

本文的主要工作有：

1）為解決上述問(wèn)題，本文考慮單個(gè)微云計(jì)算資源的有限性，對(duì)移動(dòng)終端、微云以及遠(yuǎn)程云中的任務(wù)執(zhí)行過(guò)程進(jìn)行建模，在移動(dòng)終端-微云-遠(yuǎn)程云三層架構(gòu)中研究任務(wù)卸載問(wèn)題，對(duì)任務(wù)卸載系統(tǒng)建模，以最小化任務(wù)總完成時(shí)間為目標(biāo)，考慮不同任務(wù)卸載策略，構(gòu)建基于多微云協(xié)作的任務(wù)卸載模型。

2）由于最優(yōu)卸載策略求解的較高復(fù)雜性，提出加權(quán)自適應(yīng)慣性權(quán)重的粒子群優(yōu)化（Weighted self-Adaptive Inertia Weight Particle Swarm Optimization，WAIW-PSO）算法求解任務(wù)卸載問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明，本文算法求解最優(yōu)卸載策略的性能均優(yōu)于標(biāo)準(zhǔn)PSO算法以及基于高斯函數(shù)遞減慣性權(quán)重的粒子群優(yōu)化（PSO with Decreasing Inertia Weight based on Gaussian function，GDIWPSO）算法。

3）仿真實(shí)驗(yàn)表明，與多微云系統(tǒng)中的不同任務(wù)卸載策略相比，基于WAIW-PSO 算法的協(xié)同任務(wù)卸載策略可以減少至少20%的卸載總時(shí)間。

1 相關(guān)工作

1.1 多用戶任務(wù)卸載

為了解決多用戶之間的任務(wù)卸載，可以根據(jù)需要卸載的數(shù)據(jù)量將所有的用戶設(shè)備分成兩組［3］：允許第一組的用戶設(shè)備訪問(wèn)邊緣服務(wù)器，第二組只能本地進(jìn)行處理任務(wù)。這種分組方式可以根據(jù)通信和計(jì)算資源的分配來(lái)確定最佳傳輸功率，也可以著重于通過(guò)無(wú)線網(wǎng)格網(wǎng)絡(luò)中的協(xié)同邊緣計(jì)算來(lái)減小飽和反向帶寬［4］。這種協(xié)同計(jì)算方法使用無(wú)線網(wǎng)絡(luò)使得網(wǎng)絡(luò)傳輸質(zhì)量極大地影響卸載策略的性能。為降低網(wǎng)絡(luò)傳輸質(zhì)量對(duì)任務(wù)卸載的影響，可以通過(guò)設(shè)計(jì)迭代算法來(lái)尋找上行鏈路中傳輸速率的最優(yōu)值［5］，也可以通過(guò)考慮應(yīng)用緩沖區(qū)來(lái)制定能耗最小化問(wèn)題，用一種基于Lyapunov 優(yōu)化的在線算法確定最優(yōu)CPU 頻率和傳輸任務(wù)，以及分配帶寬資源［6］。多用戶任務(wù)卸載中，每個(gè)用戶的時(shí)延與能耗各不相同，可以通過(guò)最小化所有用戶的時(shí)延與能耗，實(shí)現(xiàn)聯(lián)合優(yōu)化卸載決策與資源分配［7］。現(xiàn)有的研究更多是將部分卸載問(wèn)題表述為非線性約束問(wèn)題，并使用線性規(guī)劃求解，通過(guò)考察任務(wù)卸載完成總時(shí)間與能量消耗等因素，尋求最佳卸載策略。如Yang 等［8］研究移動(dòng)邊緣云中網(wǎng)絡(luò)感知的多用戶計(jì)算切分問(wèn)題，聯(lián)合優(yōu)化網(wǎng)絡(luò)帶寬分配和計(jì)算切分，將問(wèn)題轉(zhuǎn)化為經(jīng)典的多維背包問(wèn)題；Ning等［9］在移動(dòng)終端-邊緣服務(wù)器-遠(yuǎn)程云端三層架構(gòu)中研究多用戶計(jì)算卸載問(wèn)題，通過(guò)合理分配任務(wù)來(lái)降低時(shí)延。

1.2 多微云協(xié)作任務(wù)卸載

在多微云計(jì)算模式下，通過(guò)微云之間的協(xié)作，可以有效縮短任務(wù)完成總時(shí)間。如通過(guò)研究無(wú)線城域網(wǎng)中的微云布局問(wèn)題，降低用戶的平均訪問(wèn)延遲［10］。然而這種靜態(tài)的負(fù)載均衡方案不能適應(yīng)用戶請(qǐng)求的動(dòng)態(tài)變化，并且對(duì)于每個(gè)移動(dòng)微云，其鄰居的負(fù)載信息不斷變化，使得計(jì)算整體負(fù)載信息的成本變得昂貴。Beraldi等［11］提出了一種邊緣計(jì)算環(huán)境中鄰近數(shù)據(jù)中心的協(xié)同負(fù)載均衡策略CooLoad，如圖1所示。每個(gè)數(shù)據(jù)中心使用緩存區(qū)存儲(chǔ)服務(wù)請(qǐng)求，如果緩存區(qū)已滿則將請(qǐng)求轉(zhuǎn)發(fā)給鄰近數(shù)據(jù)中心。也有研究人員從任務(wù)重定向的角度探討無(wú)線城域網(wǎng)中的微云負(fù)載均衡問(wèn)題，使用排隊(duì)論建模微云中的任務(wù)執(zhí)行過(guò)程［12］，將高負(fù)載微云中的部分任務(wù)遷移到空閑微云中。但是由于網(wǎng)絡(luò)是間歇性連接的，任務(wù)重定向方法無(wú)法控制微云的移動(dòng)性，因此，不可能確切地將確定數(shù)量的任務(wù)從一個(gè)微云重定向到另外一個(gè)微云。Liu等［13］研究無(wú)共享、隨機(jī)共享以及最小負(fù)載共享等幾種負(fù)載均衡方案，使用馬爾可夫鏈對(duì)服務(wù)器進(jìn)行建模，證明最小負(fù)載共享策略能夠有效利用集群資源。在實(shí)際應(yīng)用中，微云移動(dòng)的靈活性使得動(dòng)態(tài)網(wǎng)絡(luò)中查詢?nèi)重?fù)載信息的成本較高，可以使用balls-and-bins 理論，通過(guò)有限的負(fù)載信息實(shí)現(xiàn)卸載任務(wù)的均衡分配，用于實(shí)現(xiàn)移動(dòng)微云網(wǎng)絡(luò)的協(xié)同任務(wù)卸載［14］。

以上工作將微云或邊緣服務(wù)器當(dāng)作獨(dú)立的資源，忽視了微云或邊緣服務(wù)器的協(xié)作。多用戶場(chǎng)景任務(wù)卸載問(wèn)題目前研究成果相對(duì)單用戶場(chǎng)景較少，但是隨著移動(dòng)云計(jì)算的發(fā)展，受到越來(lái)越多學(xué)者的關(guān)注。本文旨在多用戶場(chǎng)景中通過(guò)微云的協(xié)作平衡計(jì)算負(fù)載，確保任務(wù)得到足夠的微云計(jì)算資源，降低任務(wù)響應(yīng)時(shí)間并提高微云資源利用率。

圖1 CooLoad策略示意圖Fig.1 Schematic diagram of CooLoad scheme

2 系統(tǒng)模型與數(shù)學(xué)問(wèn)題

2.1 基于多微云的任務(wù)卸載系統(tǒng)模型

如圖2所示為移動(dòng)終端-微云-遠(yuǎn)程云模型示意圖。設(shè)整個(gè)系統(tǒng)中部署了K個(gè)微云，用C={c1，c2，…，cK}來(lái)表示。定義B ∈RK×K表示微云之間的數(shù)據(jù)傳輸速率矩陣，其中矩陣元素bu，v代表微云cu和微云cv之間的數(shù)據(jù)傳輸速率。如果u=v，則bu，v=∞。每個(gè)微云都可以同遠(yuǎn)程云端連接，微云cu與遠(yuǎn)程云之間的數(shù)據(jù)傳輸速率為buc。

圖2 系統(tǒng)模型示意圖Fig.2 Schematic diagram of system model

設(shè)系統(tǒng)中一共包含N 個(gè)移動(dòng)終端，用M={m1，m2，…，mN}來(lái)表示，每個(gè)移動(dòng)終端提交的計(jì)算任務(wù)數(shù)為L(zhǎng)。Ai={ai，1，ai，2，…，ai，L}為移動(dòng)終端mi提交的任務(wù)集合，每個(gè)任務(wù)的屬性包括輸入數(shù)據(jù)大小di，j和計(jì)算量wi，j。設(shè)二進(jìn)制變量zi，u表示移動(dòng)終端mi是否在微云cu所服務(wù)的區(qū)域內(nèi)，如果在則zi，u=1，否則zi，u=0。由于每個(gè)移動(dòng)設(shè)備只能屬于一個(gè)區(qū)域，所以有：

如果移動(dòng)終端mi在微云cu所服務(wù)的區(qū)域內(nèi)，則mi可以通過(guò)無(wú)線網(wǎng)絡(luò)將計(jì)算任務(wù)卸載到微云cu中，mi和cu之間的數(shù)據(jù)傳輸速率為

2.2 基于多微云協(xié)作的任務(wù)卸載模型

圖3 描述了多用戶場(chǎng)景中的任務(wù)卸載策略。任務(wù)的卸載地點(diǎn)共有三種選擇：第一種是直接在本地運(yùn)行；第二種是卸載到鄰近微云或其他微云中運(yùn)行；第三種是卸載到遠(yuǎn)程云中運(yùn)行。與在本地運(yùn)行和卸載到遠(yuǎn)程云中相比，將任務(wù)卸載到微云中可以有效減少任務(wù)完成時(shí)間，但是單個(gè)微云的計(jì)算資源是有限的，在卸載決策時(shí)需要考慮微云計(jì)算資源的限制。

圖3 多用戶場(chǎng)景中的任務(wù)卸載策略示意圖Fig.3 Schematic diagram of task offloading scheme in a multi-user scenario

設(shè)卸載決策變量xi，j，u∈X 代表移動(dòng)終端mi上的任務(wù)ai，j是否卸載到微云cu中，如果任務(wù)被卸載到cu中，則xi，j，u=1，否則xi，j，u=0。另外，使用xi，j，0表示任務(wù)ai，j是否在本地運(yùn)行，使用xi，j，K+1表示任務(wù)ai，j是否卸載到遠(yuǎn)程云中。由于每個(gè)任務(wù)只能被卸載到一個(gè)地點(diǎn)，有：

2.2.1 移動(dòng)端計(jì)算模型

設(shè)移動(dòng)終端mi的CPU 處理能力為任務(wù)ai，j在移動(dòng)設(shè)備的運(yùn)行時(shí)間為：

2.2.2 微云計(jì)算模型

如果任務(wù)ai，j卸載到微云cu中，響應(yīng)時(shí)間包括微云處理時(shí)間以及數(shù)據(jù)的傳輸時(shí)間。設(shè)微云cu的CPU 處理能力為，得到任務(wù)ai，j在cu中的運(yùn)行時(shí)間為：

考慮到微云計(jì)算資源的有限性，卸載到微云cu中所有任務(wù)的總計(jì)算量不能超過(guò)cu的計(jì)算容量Ru，那么有：

如圖4 所示，如果mi在cu的服務(wù)范圍內(nèi)，那么任務(wù)ai，j可以直接卸載到微云cu中；否則任務(wù)ai，j需要通過(guò)鄰近微云cv轉(zhuǎn)發(fā)到微云cu中，增加了額外的傳輸時(shí)延。任務(wù)ai，j卸載到微云cu中所需的傳輸時(shí)延為：

圖4 多微云協(xié)作的任務(wù)卸載示意圖Fig.4 Schematic diagram of task offloading based on multi-cloudlet collaboration

2.2.3 遠(yuǎn)程云計(jì)算模型

與微云相比，遠(yuǎn)程云具有充足的計(jì)算資源，任務(wù)在遠(yuǎn)程云中運(yùn)行不會(huì)受到計(jì)算資源的限制。設(shè)遠(yuǎn)程云的CPU 處理能力為yr，任務(wù)ai，j在遠(yuǎn)程云中的運(yùn)行時(shí)間為：

將任務(wù)ai，j卸載到遠(yuǎn)程云中所需的傳輸時(shí)延為：

綜合以上內(nèi)容，移動(dòng)終端mi提交的任務(wù)ai，j的完成時(shí)間Ti，j可以表示為：

基于多微云協(xié)作的計(jì)算任務(wù)卸載問(wèn)題的優(yōu)化目標(biāo)是在滿足式（2）和（5）的約束條件下，制定任務(wù)卸載策略X，使系統(tǒng)中所有任務(wù)的總完成時(shí)間最小，數(shù)學(xué)描述如下：

其中：約束條件（2）確保每個(gè)任務(wù)只能被卸載到一個(gè)地點(diǎn)，約束條件（5）確保卸載到每個(gè)微云中任務(wù)的總計(jì)算量不能超過(guò)微云的計(jì)算容量。卸載決策矩陣X 即為最后所求解，是一個(gè)N×L×(K+2)的矩陣，包含每個(gè)任務(wù)的卸載策略。當(dāng)問(wèn)題規(guī)模較大時(shí)，求解X 的復(fù)雜度極高，因此，本文提出一種加權(quán)自適應(yīng)慣性權(quán)重的粒子群優(yōu)化算法求解任務(wù)卸載決策。

3 基于粒子群優(yōu)化算法的任務(wù)卸載策略

從目標(biāo)函數(shù)可以看出，基于多微云協(xié)作的計(jì)算任務(wù)卸載問(wèn)題是帶有約束條件的整數(shù)規(guī)劃問(wèn)題，該問(wèn)題為NP-hard 問(wèn)題，解空間總數(shù)為(NL)(K+2)。當(dāng)問(wèn)題規(guī)模較大時(shí)，常規(guī)數(shù)學(xué)方法求解的復(fù)雜度過(guò)高。粒子群優(yōu)化算法（PSO）是受鳥(niǎo)群聚集模型啟發(fā)而提出的一種群體智能優(yōu)化算法，實(shí)現(xiàn)容易并且收斂速度快，常被用于解決多峰值和非線性的復(fù)雜問(wèn)題［15］。標(biāo)準(zhǔn)粒子群優(yōu)化算法適用于連續(xù)性問(wèn)題，本文改進(jìn)標(biāo)準(zhǔn)粒子群算法來(lái)求解整數(shù)規(guī)劃問(wèn)題。

3.1 編碼與離散化處理

標(biāo)準(zhǔn)粒子群算法的速度與位置更新公式如下：

在基于多微云協(xié)作的計(jì)算任務(wù)卸載問(wèn)題中，每個(gè)粒子采用整數(shù)編碼，編碼長(zhǎng)度為N×L，即有N×L 維分量，代表任務(wù)的卸載策略，共有K+2 種選擇。如果粒子編碼為0，則表示任務(wù)在本地運(yùn)行；若為K+1，則表示任務(wù)卸載到遠(yuǎn)程云運(yùn)行；若粒子編碼∈[1，K]，則表示任務(wù)卸載到對(duì)應(yīng)編號(hào)的微云中。

圖5 是多用戶場(chǎng)景中任務(wù)卸載的一個(gè)示例。圖中包括c1和c2兩個(gè)微云以及m1和m2兩個(gè)移動(dòng)終端設(shè)備，m1在c1的服務(wù)范圍內(nèi)，m2在c2的服務(wù)范圍內(nèi)，每個(gè)移動(dòng)設(shè)備提交三個(gè)任務(wù)。從圖中可以看出，任務(wù)a1，1在本地運(yùn)行，x1，1，0=1；任務(wù)a1，2在微云c1中運(yùn)行，x1，2，1=1；任務(wù)a1，3通過(guò)微云c1轉(zhuǎn)發(fā)到微云c2中運(yùn)行，x1，3，2=1；任務(wù)a2，1在微云c2中運(yùn)行，x2，1，2=1；任務(wù)a2，2卸載到遠(yuǎn)程云中運(yùn)行，x2，2，3=1；任務(wù)a2，3在本地運(yùn)行，x2，3，0=1。圖6是任務(wù)卸載策略對(duì)應(yīng)的粒子編碼。

圖5 多微云協(xié)作的任務(wù)卸載示例Fig.5 Example of task offloading based on multi-cloudlet collaboration

由于使用式（11）和（12）計(jì)算會(huì)出現(xiàn)連續(xù)值，需要對(duì)編碼進(jìn)行離散化處理。為了將粒子的位置值轉(zhuǎn)化為值域中的整數(shù)，采用就近取整的方法，定義距離函數(shù)為：

其中：xij為根據(jù)式（12）計(jì)算得到的粒子位置；yjm為粒子第j 維分量的值域中第m 個(gè)整數(shù)的值，整數(shù)值域?yàn)閧0，1，…，K+1}。分別計(jì)算粒子位置到值域中每個(gè)元素的距離，并選取距離最小的元素替換粒子的位置，實(shí)現(xiàn)粒子編碼的離散化。

圖6 任務(wù)卸載策略對(duì)應(yīng)的粒子編碼Fig.6 Particle coding corresponding to task offloading scheme

3.2 約束處理

由于目標(biāo)函數(shù)帶有約束條件，導(dǎo)致粒子在運(yùn)動(dòng)過(guò)程中可能出現(xiàn)不可行解。采用罰函數(shù)法處理違反約束的粒子，根據(jù)約束條件（5）構(gòu)造約束函數(shù)為：

其中βu為懲罰因子，可以取一個(gè)足夠大的正數(shù)。通過(guò)構(gòu)造懲罰函數(shù)，定義粒子的適應(yīng)度函數(shù)為：

3.3 基于進(jìn)化代數(shù)和個(gè)體適應(yīng)度的加權(quán)自適應(yīng)慣性權(quán)重

在粒子群算法中，慣性權(quán)重ω 的值對(duì)粒子的局部和全局搜索能力有重要影響：較大的ω值可以提高全局搜索能力，而較小的ω值則有利于算法收斂。在求解過(guò)程中粒子的多樣性不斷減弱，算法雖然收斂速度較快但容易陷入局部最優(yōu)。為了避免算法陷入局部最優(yōu)，可以根據(jù)進(jìn)化代數(shù)動(dòng)態(tài)調(diào)整慣性權(quán)重：在算法初期，ω 應(yīng)該取一個(gè)較大的值來(lái)提高算法的全局搜索能力；隨著迭代次數(shù)的增加，應(yīng)該減少ω 來(lái)加速收斂，如線性遞減［16］等。張迅等［17］提出了基于高斯函數(shù)遞減慣性權(quán)重的調(diào)整策略：

其中：α 為常數(shù)，取值為[0.1，0.3]；t 為當(dāng)前進(jìn)化代數(shù)，tmax為最大進(jìn)化代數(shù)；ωmax和ωmin分別為初始化時(shí)慣性權(quán)重的最大值和最小值。

在另一方面，慣性權(quán)重的調(diào)整也需要考慮每個(gè)粒子適應(yīng)度的差異：對(duì)于適應(yīng)度較大的粒子，應(yīng)當(dāng)減少慣性權(quán)重加速收斂；而對(duì)于適應(yīng)度較小的粒子，應(yīng)當(dāng)增加慣性權(quán)重提高全局搜索能力。根據(jù)每個(gè)粒子的適應(yīng)度調(diào)整慣性權(quán)重的公式為：

其中：fitnessi(t)為第t 代時(shí)粒子i 的適應(yīng)度，fitnessb(t)和fitnessw(t)分別為第t代時(shí)粒子的最優(yōu)和最差適應(yīng)度。

綜合兩種慣性權(quán)重調(diào)整策略，得到慣性權(quán)重的更新公式為：

綜合以上內(nèi)容，本文提出加權(quán)自適應(yīng)慣性權(quán)重的粒子群優(yōu)化（WAIW-PSO）算法解決多用戶場(chǎng)景中的計(jì)算任務(wù)卸載問(wèn)題。設(shè)粒子總數(shù)為R，算法最大迭代次數(shù)為D。

WAIW-PSO算法的主要流程如下：

1）創(chuàng)建R 個(gè)維度為N×L 的粒子，并隨機(jī)初始化粒子的速度和位置，粒子的位置編碼代表任務(wù)卸載決策。隨后算法計(jì)算每個(gè)粒子的適應(yīng)度，根據(jù)適應(yīng)度得到初始種群中的個(gè)體最優(yōu)位置和全局最優(yōu)位置。

2）粒子初始化完成后，算法進(jìn)入迭代過(guò)程。首先根據(jù)式（18）計(jì)算加權(quán)自適應(yīng)慣性權(quán)重，根據(jù)式（11）和（12）更新粒子的速度和位置，其中位置需要根據(jù)式（13）進(jìn)行取整。然后計(jì)算每個(gè)粒子當(dāng)前的適應(yīng)度，并更新個(gè)體和全局最優(yōu)位置。

3）當(dāng)?shù)螖?shù)達(dá)到L時(shí)，算法結(jié)束，最優(yōu)適應(yīng)度的粒子編碼即為任務(wù)卸載策略。

從算法流程中可以得到，WAIW-PSO 算法迭代部分的時(shí)間復(fù)雜度為O(N ?L ?R ?D)。當(dāng)問(wèn)題規(guī)模較大時(shí)，可以在較短的時(shí)間內(nèi)得到近似最優(yōu)解。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 仿真場(chǎng)景與參數(shù)設(shè)置

本文通過(guò)計(jì)算機(jī)仿真實(shí)驗(yàn)評(píng)估基于WAIW-PSO 算法的多微云協(xié)作卸載策略的有效性，實(shí)驗(yàn)平臺(tái)為Matlab R2016a。仿真場(chǎng)景中包含多個(gè)微云節(jié)點(diǎn)，微云之間通過(guò)網(wǎng)絡(luò)相互連接，將移動(dòng)終端隨機(jī)分配到各個(gè)微云節(jié)點(diǎn)所服務(wù)的區(qū)域內(nèi)。仿真參數(shù)參考了文獻(xiàn)［7，9，18-20］，如表1所示。

表1 主要仿真參數(shù)Tab.1 Main simulation parameters

4.1.2 實(shí)驗(yàn)方案

本文實(shí)驗(yàn)主要分為以下兩部分：

1）WAIW-PSO算法實(shí)驗(yàn)分析。

為了評(píng)估WAIW-PSO 算法的性能，選取標(biāo)準(zhǔn)PSO 算法以及基于高斯函數(shù)遞減慣性權(quán)重的粒子群優(yōu)化算法（GDIWPSO）［17］進(jìn)行對(duì)比實(shí)驗(yàn)，比較三種算法在不同移動(dòng)終端數(shù)和任務(wù)數(shù)下最優(yōu)解的差異。

WAIW-PSO 算法的仿真參數(shù)如下：最大迭代次數(shù)D=600，粒子總數(shù)R=30，ωmax=0.8，ωmin=0.2，c1=1.7，c2=1.5，α=0.2，λ1=λ2=0.5；GDIWPSO 算法的參數(shù)與WAIWPSO 相同；標(biāo)準(zhǔn)PSO 算法的慣性權(quán)重取ω=0.8。為了確保實(shí)驗(yàn)結(jié)果的有效性，取10次實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。

2）任務(wù)卸載實(shí)驗(yàn)分析。

為了評(píng)估基于WAIW-PSO 算法的協(xié)同任務(wù)卸載策略的有效性，選擇以下幾種任務(wù)卸載策略進(jìn)行對(duì)比實(shí)驗(yàn)，比較不同場(chǎng)景中任務(wù)總完成時(shí)間的變化情況。

a）本地運(yùn)行策略（Local）：任務(wù)在移動(dòng)設(shè)備上運(yùn)行。

b）遠(yuǎn)程云卸載策略（Remote）：任務(wù)卸載到遠(yuǎn)程云中運(yùn)行。

c）非協(xié)同任務(wù)卸載策略（No-Cooperation）：以最小化任務(wù)完成時(shí)間為目標(biāo)，將任務(wù)卸載到移動(dòng)終端、鄰近微云或者遠(yuǎn)程云中，但是任務(wù)不能卸載到其他微云中。

d）基于WAIW-PSO 算法的協(xié)同任務(wù)卸載策略（WAIWPSO-Cooperation）：與No-Cooperation 策略相比，在任務(wù)卸載過(guò)程中考慮了微云的協(xié)作，可以將任務(wù)卸載到其他微云中運(yùn)行。

4.2 實(shí)驗(yàn)結(jié)果與分析

4.2.1 WAIW-PSO算法實(shí)驗(yàn)分析

圖7（a）和7（b）顯示了標(biāo)準(zhǔn)PSO算法、GDIWPSO算法以及WAIW-PSO 算法在不同移動(dòng)設(shè)備數(shù)和任務(wù)數(shù)下最優(yōu)解的差異。從圖中可以看出，WAIW-PSO 算法在不同場(chǎng)景中所得解的質(zhì)量均優(yōu)于其他兩種算法。標(biāo)準(zhǔn)PSO算法由于很容易陷入局部最優(yōu)解，解的質(zhì)量較差。GDIWPSO 算法根據(jù)進(jìn)化代數(shù)調(diào)整慣性權(quán)重，解的質(zhì)量?jī)?yōu)于標(biāo)準(zhǔn)PSO算法；但是當(dāng)種群中粒子的適應(yīng)度比較接近時(shí)，種群多樣性很差，容易陷入局部最優(yōu)解。WAIW-PSO算法在慣性權(quán)重的自適應(yīng)調(diào)整過(guò)程中綜合考慮種群進(jìn)化代數(shù)和個(gè)體適應(yīng)度的影響，在種群進(jìn)化前期或者個(gè)體適應(yīng)度較差的情況下通過(guò)增加慣性權(quán)重來(lái)提高全局搜索能力，在種群進(jìn)化后期或者個(gè)體適應(yīng)度較好的情況下通過(guò)減少慣性權(quán)重來(lái)加速收斂，利用慣性權(quán)重的自適應(yīng)調(diào)整平衡全局和局部搜索能力，優(yōu)化效果較好。

圖7 三種啟發(fā)式算法的最優(yōu)解對(duì)比Fig.7 Comparison of optimal solution of three heuristic algorithms

4.2.2 任務(wù)卸載實(shí)驗(yàn)分析

圖8（a）顯示了在L=5的場(chǎng)景中，四種任務(wù)卸載策略在不同移動(dòng)設(shè)備數(shù)下任務(wù)總完成時(shí)間的變化情況。從圖中可以看出，隨著移動(dòng)設(shè)備數(shù)量的增加，提交的任務(wù)數(shù)量越來(lái)越多，系統(tǒng)中任務(wù)的總完成時(shí)間隨之增加。Local 策略在本地運(yùn)行所有任務(wù)，由于移動(dòng)設(shè)備的計(jì)算能力較弱，任務(wù)的處理時(shí)延很大。Remote 策略將任務(wù)卸載到遠(yuǎn)程云中運(yùn)行，雖然遠(yuǎn)程云處理能力較強(qiáng)，但移動(dòng)終端與遠(yuǎn)程云之間的傳輸時(shí)延很大。No-Cooperation 策略和WAIW-PSO-Cooperation 策略可以將任務(wù)卸載到微云中，利用微云的計(jì)算能力執(zhí)行任務(wù)，總完成時(shí)間少于Local和Remote策略。當(dāng)移動(dòng)終端數(shù)量N ≤30時(shí)，單個(gè)微云的計(jì)算資源相對(duì)充足，No-Cooperation 策略和WAIW-PSOCooperation 策略都可以將任務(wù)卸載到鄰近微云中運(yùn)行，任務(wù)總完成時(shí)間相差不大。但是當(dāng)N ＞30 后，由于單個(gè)微云計(jì)算資源有限，不足以處理所有的任務(wù)請(qǐng)求，No-Cooperation 策略忽視了微云的協(xié)作，將一部分任務(wù)卸載到遠(yuǎn)程云中運(yùn)行，造成額外的傳輸開(kāi)銷；而WAIW-PSO-Cooperation 策略可以將一部分任務(wù)卸載到其他計(jì)算資源充足的微云中運(yùn)行。當(dāng)N=100時(shí)，WAIW-PSO-Cooperation 策略與No-Cooperation 策略相比總完成時(shí)間減少了24.6%，與Remote 策略相比總完成時(shí)間減少了33.9%，與Local策略相比總完成時(shí)間減少了46.7%。

圖8（b）顯示了在N=50 的場(chǎng)景中，四種任務(wù)卸載策略在不同任務(wù)數(shù)下任務(wù)總完成時(shí)間的變化情況。從圖可以看出，隨著移動(dòng)設(shè)備提交任務(wù)數(shù)量的增加，任務(wù)總完成時(shí)間呈上升趨勢(shì)：L ≤3時(shí)，由于微云計(jì)算資源充足，No-Cooperation策略和WAIW-PSO-Cooperation 策略的任務(wù)總完成時(shí)間相差不大；當(dāng)L ＞3 后，由于單個(gè)微云計(jì)算資源的有限性，No-Cooperation 策略將一部分任務(wù)卸載到遠(yuǎn)程云中導(dǎo)致傳輸開(kāi)銷增加，而WAIW-PSO-Cooperation策略可以將任務(wù)卸載到其他計(jì)算資源充足的微云中運(yùn)行，任務(wù)總完成時(shí)間較短。當(dāng)L=10 時(shí)，WAIW-PSO-Cooperation 策略與Local 策略相比任務(wù)總完成時(shí)間減少了40.9%，與Remote 策略相比任務(wù)總完成時(shí)間減少了33.6%，與No-Cooperation 策略相比任務(wù)總完成時(shí)間減少了21.5%。

圖8（c）顯 示 了 在N=50 以 及L=5 的 場(chǎng) 景 中，No-Cooperation 策略和WAIW-PSO-Cooperation 策略得到的任務(wù)總完成時(shí)間在不同微云計(jì)算容量下的變化情況。從圖中可以看出，隨著微云計(jì)算容量的增加，任務(wù)總完成時(shí)間呈現(xiàn)出下降趨勢(shì)。當(dāng)微云計(jì)算容量較小時(shí)，WAIW-PSO-Cooperation 策略通過(guò)多微云的協(xié)同平衡計(jì)算負(fù)載，確保任務(wù)得到足夠的微云計(jì)算資源，任務(wù)總完成時(shí)間優(yōu)于No-Cooperation 策略。隨著微云計(jì)算容量越來(lái)越大，更多的任務(wù)可以卸載到微云中運(yùn)行，No-Cooperation 策略的任務(wù)總完成時(shí)間明顯縮短。當(dāng)微云計(jì)算容量達(dá)到7 Gigacycles（Gigacycle 表示微云的計(jì)算容量，代表每個(gè)時(shí)鐘周期的計(jì)算次數(shù)）時(shí)，兩種策略得到的任務(wù)總完成時(shí)間基本相同。

圖8 不同場(chǎng)景下的任務(wù)完成總時(shí)間對(duì)比Fig.8 Comparison of total task completion time in different scenarios

4.3 實(shí)驗(yàn)結(jié)論

從實(shí)驗(yàn)結(jié)果可以得出：

1）與標(biāo)準(zhǔn)PSO 算法和GDIWPSO 算法相比，WAIW-PSO 算法根據(jù)進(jìn)化代數(shù)和個(gè)體適應(yīng)度綜合調(diào)整慣性權(quán)重，尋優(yōu)能力較強(qiáng)。

2）基于WAIW-PSO 算法的協(xié)同任務(wù)卸載策略能夠利用多個(gè)微云的協(xié)作突破單微云計(jì)算資源的限制，確保任務(wù)可以得到足夠的微云資源，在不同場(chǎng)景中的任務(wù)總完成時(shí)間優(yōu)于其他卸載策略。

5 結(jié)語(yǔ)

本文研究了多微云計(jì)算模式中的計(jì)算任務(wù)卸載問(wèn)題，通過(guò)多微云協(xié)作的方式構(gòu)建計(jì)算任務(wù)卸載模型，并針對(duì)問(wèn)題求解的復(fù)雜性，提出了加權(quán)自適應(yīng)慣性權(quán)重的粒子群優(yōu)化（WAIW-PSO）算法，能有效地縮短任務(wù)卸載問(wèn)題總時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明，基于WAIW-PSO 算法的協(xié)同任務(wù)卸載策略能夠突破單微云計(jì)算資源的限制，確保計(jì)算任務(wù)可以得到足夠的微云資源，在不同場(chǎng)景中的任務(wù)總完成時(shí)間均優(yōu)于其他卸載策略。本文在研究計(jì)算任務(wù)卸載的過(guò)程中并未考慮用戶移動(dòng)帶來(lái)的網(wǎng)絡(luò)切換或者連接中斷的問(wèn)題。在實(shí)際場(chǎng)景中，通過(guò)挖掘用戶的移動(dòng)規(guī)律制定高效的卸載決策對(duì)提高任務(wù)的執(zhí)行成功率具有重要意義，因此，在未來(lái)研究中應(yīng)考慮任務(wù)卸載中的網(wǎng)絡(luò)通信開(kāi)銷等因素。