季子豪，江凌云

(南京郵電大學(xué)通信與信息工程學(xué)院，江蘇 南京 210003)

1 引言

隨著物聯(lián)網(wǎng)IoT(Internet of Things)、5G技術(shù)的發(fā)展，終端設(shè)備的數(shù)量迅速增加，其產(chǎn)生的數(shù)據(jù)量呈指數(shù)級(jí)增長(zhǎng)，當(dāng)前核心網(wǎng)的帶寬無(wú)法承受日益龐大的數(shù)據(jù)量傳輸。此外，增強(qiáng)現(xiàn)實(shí)、虛擬現(xiàn)實(shí)和無(wú)人駕駛等，尤其是基于人工智能的新型應(yīng)用程序的出現(xiàn)對(duì)時(shí)延和功耗提出了更高的要求[1]。IoT終端的計(jì)算、存儲(chǔ)和電池能力有限，無(wú)法獨(dú)立完成這些計(jì)算密集型應(yīng)用任務(wù)。邊緣計(jì)算(Edge Computing)為解決這些問(wèn)題提供了有效途徑。邊緣計(jì)算的思想是在靠近終端側(cè)部署計(jì)算資源和存儲(chǔ)資源，對(duì)終端的計(jì)算任務(wù)和存儲(chǔ)任務(wù)就近處理，以此優(yōu)化計(jì)算密集型應(yīng)用的響應(yīng)延遲[2]。

計(jì)算卸載是邊緣計(jì)算領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)[3]。計(jì)算卸載技術(shù)通過(guò)將資源受限的IoT終端的計(jì)算任務(wù)卸載到計(jì)算資源更強(qiáng)的邊緣節(jié)點(diǎn)或中心云執(zhí)行，可以優(yōu)化物聯(lián)網(wǎng)應(yīng)用的響應(yīng)延遲，同時(shí)有效降低終端設(shè)備的能耗。關(guān)于單一設(shè)備的計(jì)算卸載已經(jīng)有很多研究人員進(jìn)行了研究，即將應(yīng)用程序完整地部署在一臺(tái)設(shè)備上，在進(jìn)行卸載決策時(shí)，對(duì)應(yīng)用程序的各任務(wù)進(jìn)行代價(jià)分析，判斷哪些任務(wù)卸載到邊緣節(jié)點(diǎn)執(zhí)行，哪些任務(wù)在本地執(zhí)行，可以使得應(yīng)用程序的總執(zhí)行代價(jià)最小。

但是，在未來(lái)的IoT環(huán)境中，大部分應(yīng)用服務(wù)都將以分布式架構(gòu)的形式進(jìn)行部署，一個(gè)完整的IoT應(yīng)用被拆分為多個(gè)具有依賴關(guān)系的子任務(wù)，這些子任務(wù)初始部署在多個(gè)站點(diǎn)中，例如IoT終端、邊緣節(jié)點(diǎn)或中心云，這些站點(diǎn)協(xié)作完成整個(gè)應(yīng)用任務(wù)。但是，受計(jì)算資源、存儲(chǔ)容量和電池電量的影響，在終端進(jìn)行數(shù)據(jù)處理可能會(huì)耗費(fèi)過(guò)長(zhǎng)時(shí)間，需要將自身的計(jì)算任務(wù)卸載到邊緣節(jié)點(diǎn)或中心云處理[4]；同樣，受網(wǎng)絡(luò)帶寬的影響，終端和邊緣節(jié)點(diǎn)之間的數(shù)據(jù)傳輸代價(jià)可能大于本地執(zhí)行代價(jià)[5]，不適合卸載任務(wù)。在這樣的場(chǎng)景下，站點(diǎn)間的通信代價(jià)無(wú)法被簡(jiǎn)單忽略，進(jìn)行計(jì)算卸載決策、尋找最優(yōu)任務(wù)分配策略十分具有挑戰(zhàn)性。

本文的其余部分組織如下：第2節(jié)介紹計(jì)算卸載的相關(guān)工作；第3節(jié)建立多站點(diǎn)協(xié)同計(jì)算卸載問(wèn)題的數(shù)學(xué)模型；第4節(jié)描述遺傳算法，并利用遺傳算法尋找最優(yōu)卸載決策，提出基于遺傳算法的多站點(diǎn)協(xié)同計(jì)算卸載算法GAMCCO(Genetic Algorithm-based Multi-site Collaborative Computation Offloading);第5節(jié)進(jìn)行仿真實(shí)驗(yàn)，并對(duì)結(jié)果進(jìn)行討論；最后對(duì)本文進(jìn)行了總結(jié)和展望。

2 相關(guān)工作

作為邊緣計(jì)算領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)，計(jì)算卸載已經(jīng)得到了廣泛的研究。文獻(xiàn)[6]提出了MAUI計(jì)算卸載框架，該框架將計(jì)算卸載問(wèn)題轉(zhuǎn)化為整數(shù)線性規(guī)劃問(wèn)題，將一些繁重的計(jì)算任務(wù)卸載到鄰近的邊緣云服務(wù)器上，以降低移動(dòng)設(shè)備的能耗。文獻(xiàn)[7]提出了基于遺傳算法的任務(wù)調(diào)度方案，該方案將應(yīng)用程序劃分為多個(gè)子任務(wù)，分別計(jì)算每一個(gè)子任務(wù)的本地執(zhí)行代價(jià)和遠(yuǎn)程執(zhí)行代價(jià)，構(gòu)建具有時(shí)延約束的能耗模型，最后利用遺傳算法分析該能耗模型，得出最佳卸載方案。文獻(xiàn)[8]將應(yīng)用程序建模為由細(xì)粒度任務(wù)組成的通用拓?fù)浣Y(jié)構(gòu)，這些細(xì)粒度任務(wù)可以在本地或邊緣節(jié)點(diǎn)上執(zhí)行，然后將計(jì)算卸載問(wèn)題規(guī)約為具有時(shí)延約束的工作流調(diào)度問(wèn)題，提出了基于拉格朗日松弛的聚合代價(jià)算法計(jì)算工作流調(diào)度問(wèn)題的最優(yōu)解。文獻(xiàn)[9]針對(duì)單一云服務(wù)器計(jì)算資源有限的情形，考慮將計(jì)算任務(wù)卸載到多個(gè)云服務(wù)器上，提出了基于遺傳算法的多站點(diǎn)計(jì)算卸載決策GAMCO(Genetic-based decision Algorithm for Multi-site Computation Offloading)，實(shí)現(xiàn)應(yīng)用程序的性能提升。文獻(xiàn)[10]實(shí)現(xiàn)了一個(gè)多站點(diǎn)自適應(yīng)卸載框架，該框架把設(shè)備的硬件信息變化和實(shí)時(shí)網(wǎng)絡(luò)條件納入考量，將移動(dòng)設(shè)備的計(jì)算任務(wù)卸載到自組織云、邊緣云和中心云中，以加快應(yīng)用程序的執(zhí)行。文獻(xiàn)[11]針對(duì)動(dòng)態(tài)環(huán)境中的計(jì)算卸載，采用隨機(jī)博弈方法建立了動(dòng)態(tài)模型，并提出多代理隨機(jī)學(xué)習(xí)的方法尋找最優(yōu)決策。文獻(xiàn)[12]提出了一種能量高效的動(dòng)態(tài)上傳策略，利用動(dòng)態(tài)電壓和頻率分配技術(shù)優(yōu)化移動(dòng)設(shè)備的性能。文獻(xiàn)[13]則是采用馬爾可夫決策過(guò)程，將多站點(diǎn)卸載問(wèn)題轉(zhuǎn)化為具有時(shí)延約束、最小卸載代價(jià)的最短路徑問(wèn)題，并提出基于能耗的多點(diǎn)卸載策略算法，尋找多站點(diǎn)任務(wù)卸載的解決方案。

但是，以上關(guān)于計(jì)算卸載的研究工作都是假設(shè)應(yīng)用程序初始完整地部署在一臺(tái)設(shè)備上，并將計(jì)算任務(wù)從該設(shè)備上卸載到其余站點(diǎn)執(zhí)行，并未考慮到應(yīng)用程序分布式部署在多個(gè)設(shè)備上的情形。因此，本文基于應(yīng)用程序分布式部署的情形，將多站點(diǎn)協(xié)同計(jì)算卸載問(wèn)題建模為一個(gè)通用的代價(jià)模型，利用遺傳算法尋找最優(yōu)的卸載方案，以最小化總執(zhí)行代價(jià)。

3 計(jì)算卸載模型

本節(jié)首先基于應(yīng)用程序分布式部署的假設(shè)，對(duì)多站點(diǎn)協(xié)同計(jì)算卸載的場(chǎng)景進(jìn)行描述，并以此構(gòu)建任務(wù)依賴關(guān)系圖。然后根據(jù)站點(diǎn)間通信代價(jià)、任務(wù)執(zhí)行的時(shí)延代價(jià)和能耗代價(jià)進(jìn)行模型構(gòu)建，最終得出模型的數(shù)學(xué)表達(dá)式。

3.1 系統(tǒng)場(chǎng)景

傳統(tǒng)的計(jì)算卸載場(chǎng)景如圖1所示。終端設(shè)備上有一個(gè)完整的應(yīng)用程序待執(zhí)行，應(yīng)用程序由多個(gè)子任務(wù)組成，根據(jù)相應(yīng)的計(jì)算卸載算法判斷哪些子任務(wù)在本地執(zhí)行，哪些子任務(wù)需要卸載到邊緣節(jié)點(diǎn)或中心云執(zhí)行。針對(duì)這種場(chǎng)景的計(jì)算卸載算法無(wú)法用于應(yīng)用程序在多站點(diǎn)分布式部署的情形。

Figure 1 Edge computing scenario for single device computation offloading

本文考慮這樣一個(gè)需要多站點(diǎn)協(xié)同計(jì)算的邊緣計(jì)算場(chǎng)景，如圖2所示。該場(chǎng)景包含多個(gè)IoT終端、1個(gè)邊緣節(jié)點(diǎn)和1個(gè)中心云，一共涉及K個(gè)節(jié)點(diǎn)。物聯(lián)網(wǎng)應(yīng)用程序在開(kāi)發(fā)時(shí)已經(jīng)被劃分為K個(gè)子任務(wù)V={v1,v2,…,vK}，并以分布式的形式部署在IoT終端、邊緣節(jié)點(diǎn)和中心云上，應(yīng)用程序執(zhí)行時(shí)需要這些站點(diǎn)協(xié)同計(jì)算。應(yīng)用程序的子任務(wù)之間具有依賴關(guān)系，初始部署在各個(gè)IoT終端上的計(jì)算任務(wù)既可以在該終端本地執(zhí)行，也可以根據(jù)上下文信息卸載到邊緣節(jié)點(diǎn)或中心云執(zhí)行。

Figure 2 Edge computing scenario for multi-site collaborative computation offloading

Figure 3 Dependency relationship graph among application components

3.2 系統(tǒng)代價(jià)模型

3.2.1 參數(shù)描述

下面對(duì)計(jì)算卸載模型涉及的參數(shù)進(jìn)行簡(jiǎn)要描述：

(1)計(jì)算卸載方案為X={x1,x2,…,xK}，其中xk∈{-1,0,1}，xk=-1表示將任務(wù)vk卸載到云端執(zhí)行，xk=0表示將任務(wù)vk卸載到邊緣節(jié)點(diǎn)執(zhí)行，xk=1表示在站點(diǎn)k處執(zhí)行即本地執(zhí)行。

(3)本文構(gòu)造的計(jì)算卸載代價(jià)模型由時(shí)延代價(jià)和能耗代價(jià)組成，用于尋找應(yīng)用程序組件的最佳卸載決策，以最小化應(yīng)用程序的總執(zhí)行代價(jià)。計(jì)算卸載決策X所對(duì)應(yīng)的應(yīng)用程序代價(jià)如式(1)所示：

(1)

其中，T(X)和E(X)分別表示應(yīng)用程序使用卸載方案X的時(shí)延代價(jià)和能耗代價(jià)；Torigin和Eorigin分別表示應(yīng)用程序組件不經(jīng)過(guò)計(jì)算卸載，直接按照初始部署執(zhí)行的總時(shí)延和能耗代價(jià)，可以認(rèn)為是一個(gè)常數(shù)；α和β分別表示時(shí)延和能耗在整個(gè)代價(jià)模型中所占的比重。

3.2.2 時(shí)延代價(jià)模型

時(shí)延代價(jià)包括任務(wù)計(jì)算時(shí)延和數(shù)據(jù)通信時(shí)延。對(duì)于每一個(gè)站點(diǎn)k，fk表示該站點(diǎn)的計(jì)算能力，任務(wù)vk在各站點(diǎn)本地的計(jì)算時(shí)延可以表示為式(2)：

(2)

在邊緣節(jié)點(diǎn)的計(jì)算時(shí)延由式(3)表示：

(3)

在云端的計(jì)算時(shí)延由式(4)表示：

(4)

其中，fe和fc分別表示邊緣節(jié)點(diǎn)和云端的計(jì)算能力。

(5)

當(dāng)計(jì)算任務(wù)vi和任務(wù)vj的卸載目的地一致時(shí)，它們之間的數(shù)據(jù)通信時(shí)延為0。

時(shí)延模型的優(yōu)化目標(biāo)是找到應(yīng)用程序的最佳計(jì)算卸載決策Xbest，滿足應(yīng)用程序各組件的時(shí)延代價(jià)加權(quán)最小。

根據(jù)候選卸載決策X給出的應(yīng)用程序時(shí)延模型如式(6)所示：

(6)

(7)

3.2.3 能耗代價(jià)模型

與終端相比，邊緣節(jié)點(diǎn)和云端的電量近乎是無(wú)限的，因此本文只考慮終端產(chǎn)生的能耗。終端產(chǎn)生的能耗包括計(jì)算能耗和數(shù)據(jù)傳輸?shù)耐ㄐ拍芎?。與以往關(guān)于計(jì)算卸載的研究類似，在數(shù)據(jù)傳輸?shù)耐ㄐ拍芎倪@一方面，本文只考慮終端發(fā)送數(shù)據(jù)的能耗，因?yàn)榕c發(fā)送功率相比，接收功率往往很小，可以忽略不計(jì)。

任務(wù)vk在各站點(diǎn)的計(jì)算能耗如式(8)所示：

(8)

(9)

能耗模型的優(yōu)化目標(biāo)是找到應(yīng)用程序的最佳計(jì)算卸載決策Xbest，使得應(yīng)用程序各組件的能耗代價(jià)加權(quán)最小。

根據(jù)候選卸載決策X給出的應(yīng)用程序能耗模型如式(10)所示：

(10)

4 GAMCCO算法

由于考慮了多站點(diǎn)之間的任務(wù)依賴關(guān)系，求解最佳計(jì)算卸載策略的難度大大提高，很難在多項(xiàng)式時(shí)間內(nèi)計(jì)算出最優(yōu)解。因此，本文引入遺傳算法，提出GAMCCO算法來(lái)尋找計(jì)算卸載策略的最優(yōu)解。

遺傳算法借鑒了自然界的遺傳選擇和自然淘汰的生物進(jìn)化過(guò)程，其核心思想是模擬一個(gè)人工種群的進(jìn)化過(guò)程，通過(guò)選擇、交叉和變異機(jī)制，經(jīng)過(guò)若干代進(jìn)化后，產(chǎn)生最優(yōu)個(gè)體，是一種高效的全局搜索算法，適合處理傳統(tǒng)尋優(yōu)算法難以解決的非線性問(wèn)題。

遺傳算法的個(gè)體對(duì)應(yīng)到計(jì)算卸載問(wèn)題中即為計(jì)算卸載方案，染色體表示經(jīng)過(guò)編碼后的卸載方案，基因表示每個(gè)任務(wù)的卸載目的地。

4.1 編碼和初始種群

實(shí)現(xiàn)遺傳算法的第1步是對(duì)求解問(wèn)題的解空間進(jìn)行編碼。在本文提出的多站點(diǎn)協(xié)同計(jì)算卸載模型中，應(yīng)用程序被劃分為K個(gè)需要卸載的子任務(wù)，因此在遺傳算法中每條染色體由K個(gè)基因組成，部署在各站點(diǎn)的任務(wù)可以在本地執(zhí)行，也可以遷移到邊緣節(jié)點(diǎn)或遷移到云端執(zhí)行，因此每個(gè)基因有3個(gè)可能值(云：-1，邊緣：0，本地：1)。一條染色體就是一個(gè)可能的計(jì)算卸載方案，如圖4所示，是一個(gè)由K個(gè)基因構(gòu)成的染色體。

Figure 4 A chromosome with K genes

初始種群使用隨機(jī)構(gòu)造的方法產(chǎn)生，初始種群規(guī)模為M。

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

遺傳算法對(duì)一個(gè)個(gè)體(解)的好壞用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)[14]。在本文中，適應(yīng)度函數(shù)定義為應(yīng)用程序計(jì)算卸載總代價(jià)的倒數(shù)，如式(11)所示，以此評(píng)判每個(gè)計(jì)算卸載方案的優(yōu)劣，適應(yīng)度函數(shù)值越大，對(duì)應(yīng)的總代價(jià)越小，那么計(jì)算卸載方案越好。

(11)

在每一次的迭代進(jìn)化過(guò)程中，采取精英選擇的策略保留每一代的精英解。進(jìn)行第i次迭代時(shí)，首先計(jì)算第i代種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值，并將種群中的個(gè)體按照適應(yīng)度函數(shù)值大小降序排列，然后丟棄適應(yīng)度較低的后一半個(gè)體，選擇種群中適應(yīng)度較高的前一半個(gè)體延續(xù)到下一步的交叉過(guò)程。

4.3 交叉過(guò)程

交叉過(guò)程中，2個(gè)父親染色體按照某種規(guī)則交換其部分基因，產(chǎn)生子代染色體。本文選取了單點(diǎn)交叉的方式進(jìn)行交叉操作。所謂單點(diǎn)交叉，就是在父親染色體中隨機(jī)選擇1個(gè)交叉點(diǎn)，然后以交叉點(diǎn)為界，交換2個(gè)父親染色體交叉點(diǎn)位置的左右基因，產(chǎn)生2個(gè)新的染色體。一個(gè)單點(diǎn)交叉的例子如圖5所示。

Figure 5 An example of a single point crossing

4.4 變異過(guò)程

變異操作是根據(jù)設(shè)定的變異概率選取染色體的若干位基因改變其值，其目的是產(chǎn)生新的個(gè)體，保持種群的多樣性，防止過(guò)早陷入局部最優(yōu)。本文對(duì)交叉過(guò)程產(chǎn)生的染色體種群進(jìn)行基因變異。另一方面，變異操作完成后，為了將盡可能多的卸載方案納入考量，防止適應(yīng)度函數(shù)過(guò)早收斂，本文構(gòu)造與當(dāng)前的精英染色體數(shù)目相等的隨機(jī)染色體，兩者共同組成新一代的染色體種群。在這一步中使用隨機(jī)染色體和精英染色體共同組成新種群的方法則是對(duì)經(jīng)典遺傳方法的改進(jìn)，經(jīng)典遺傳方法只會(huì)保留精英個(gè)體，容易過(guò)早收斂。

4.5 終止條件

經(jīng)過(guò)上述遺傳算法的操作，可以得到新一代的染色體種群，根據(jù)本文提出的適應(yīng)度函數(shù)，對(duì)新一代種群進(jìn)行適應(yīng)度評(píng)估。如果當(dāng)前迭代次數(shù)已經(jīng)達(dá)到了預(yù)先設(shè)定的最大值，或者在連續(xù)的若干代染色體種群中，最低適應(yīng)度函數(shù)值沒(méi)有改進(jìn)，那么遺傳尋優(yōu)過(guò)程的終止條件得到滿足，算法終止；否則，繼續(xù)重復(fù)遺傳迭代進(jìn)化過(guò)程，直至滿足算法的終止條件。

4.6 算法流程

本文提出的卸載架構(gòu)如圖6所示，其中設(shè)備D1、D2和D3是終端節(jié)點(diǎn)，具備計(jì)算和本地組網(wǎng)功能，邊緣節(jié)點(diǎn)作為控制調(diào)度器進(jìn)行參數(shù)收集和卸載決策。云、邊緣節(jié)點(diǎn)和終端共同構(gòu)成了一項(xiàng)服務(wù)。UE是用戶設(shè)備，由它來(lái)調(diào)用該服務(wù)。當(dāng)邊緣節(jié)點(diǎn)接收到用戶的調(diào)用請(qǐng)求后，分析各站點(diǎn)的硬件信息和網(wǎng)絡(luò)條件，進(jìn)行分析決策，并將決策結(jié)果告知各站點(diǎn)進(jìn)行計(jì)算，最終將計(jì)算結(jié)果返回給用戶。

Figure 6 Offloading framework

基于遺傳算法的多站點(diǎn)協(xié)同計(jì)算卸載算法(GAMCCO)的流程圖如圖7所示。

Figure 7 Flow chart of GAMCCO

5 仿真和評(píng)估

本節(jié)將使用Matlab對(duì)提出的GAMCCO算法進(jìn)行仿真并加以分析。

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

仿真場(chǎng)景包括1個(gè)中心云、1個(gè)邊緣節(jié)點(diǎn)和多個(gè)終端節(jié)點(diǎn)，總計(jì)為K個(gè)。對(duì)于終端節(jié)點(diǎn)，假設(shè)除了部署在各節(jié)點(diǎn)的任務(wù)不同外，它們的硬件完全相同，即擁有完全一樣的計(jì)算能力和功耗。仿真實(shí)驗(yàn)的部分參數(shù)如表1所示。

以圖像拼接應(yīng)用為例，圖像拼接技術(shù)的原理是根據(jù)圖像重疊部分將多幅銜接的圖像拼合成一幅高分辨率全景圖。目前圖像拼接過(guò)程主要包括以下幾個(gè)主要步驟：圖像預(yù)處理、圖像配準(zhǔn)、圖像融合與邊界平滑。其中，圖像預(yù)處理主要是對(duì)各攝像終端采集的圖像進(jìn)行幾何畸變校準(zhǔn)和噪聲點(diǎn)抑制，使

Table 1 Parameters of simulation experiment

參考圖像不存在明顯的幾何畸變。該步驟可以在各攝像終端直接運(yùn)行，當(dāng)終端資源受限時(shí)可以選擇卸載到邊緣節(jié)點(diǎn)或云端運(yùn)行。本文分析了此應(yīng)用程序內(nèi)部的方法調(diào)用關(guān)系，將其細(xì)分為由10個(gè)任務(wù)組成的應(yīng)用，并構(gòu)造相應(yīng)的任務(wù)依賴關(guān)系圖，然后利用模擬的數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。以下Cttotal是根據(jù)一組模擬的數(shù)據(jù)集計(jì)算出的時(shí)延代價(jià)矩陣，Cttotal中的行代表應(yīng)用程序的子任務(wù)，列代表云端、邊緣節(jié)點(diǎn)或本地，Cttotal[i][j]表示應(yīng)用程序子任務(wù)vi在站點(diǎn)j處執(zhí)行的總代價(jià)(包括通信時(shí)延代價(jià)和計(jì)算時(shí)延代價(jià))。當(dāng)給定卸載方案X={x1,x2,…,xK}時(shí)，根據(jù)Cttotal和X即可計(jì)算出式(1)中T(X)所表示的應(yīng)用程序總時(shí)延代價(jià)。同理，總能耗代價(jià)E(X)也可根據(jù)能耗代價(jià)矩陣和卸載方案X計(jì)算得到。設(shè)置了時(shí)延因子α和能耗因子β后，式(1)的總代價(jià)W(X)也可計(jì)算得出。

X′表示初始種群中的卸載方案樣本的集合，它的每一列都表示一個(gè)卸載方案。由于本文將初始種群設(shè)置為100個(gè)，所以X′的列數(shù)為100，行數(shù)為子任務(wù)數(shù)。實(shí)際實(shí)驗(yàn)時(shí)，本文使用多組模擬的數(shù)據(jù)集計(jì)算平均結(jié)果，盡可能確保實(shí)驗(yàn)結(jié)果不具備偶然性。

5.2 結(jié)果分析

遺傳算法的參數(shù)對(duì)GAMCCO算法的性能有著很大的影響，例如初始種群規(guī)模、突變概率和遺傳迭代次數(shù)等。為了使GAMCCO算法獲得最佳性能，本文利用控制變量的方法研究了突變概率和遺傳迭代次數(shù)對(duì)總代價(jià)的影響。圖8展示了突變概率對(duì)算法總代價(jià)的影響。具體設(shè)置為初始種群規(guī)模100，迭代次數(shù)100，突變概率在[0,0.2]變化，同時(shí)適應(yīng)度函數(shù)中的時(shí)延因子α和能耗因子β都設(shè)置為0.5。從圖8可以看出，在[0,0.04]內(nèi)，總代價(jià)呈下降趨勢(shì)，然后隨著突變概率的增加，總代價(jià)上升，突變概率增加到0.15以后，總代價(jià)上下起伏。這是因?yàn)殡S著突變概率的增加，種群中的較優(yōu)解可能會(huì)變異為較差解，導(dǎo)致性能下降。

Figure 8 Impact of mutation probability on the performance of the algorithm

圖9展示了遺傳迭代次數(shù)對(duì)算法總代價(jià)的影響。具體參數(shù)設(shè)置為初始種群規(guī)模100，突變概率0.04，迭代次數(shù)從1增加至100，時(shí)延因子α和能耗因子β都為0.5。從圖9可以發(fā)現(xiàn)，隨著迭代次數(shù)的增加，總代價(jià)雖有起伏，但仍呈下降趨勢(shì)，當(dāng)?shù)螖?shù)達(dá)到80后，代價(jià)曲線基本平穩(wěn)。

Figure 9 Impact of the number of genetic iterations on the performance of the algorithm

根據(jù)以上實(shí)驗(yàn)，本文將遺傳算法參數(shù)設(shè)置為種群數(shù)100，突變概率0.04，遺傳迭代次數(shù)100。為了評(píng)估所提算法的可行性和性能，將GAMCCO算法的結(jié)果和以下幾種卸載方案對(duì)比：

(1)本地卸載方案(Local)：所有站點(diǎn)的計(jì)算任務(wù)都在各站點(diǎn)本地執(zhí)行。

(2)邊緣卸載方案(Edge)：所有站點(diǎn)的計(jì)算任務(wù)都遷移到邊緣節(jié)點(diǎn)執(zhí)行。

(3)遺傳方案(GA)：使用遺傳算法的經(jīng)典實(shí)現(xiàn)對(duì)本文所建立的代價(jià)模型進(jìn)行遺傳尋優(yōu)。

(4)多站點(diǎn)卸載方案(GAMCO)：對(duì)該算法的代價(jià)模型和卸載方案進(jìn)行了擴(kuò)展，使其能適用于本文的多站點(diǎn)協(xié)同計(jì)算卸載的場(chǎng)景，并進(jìn)行了仿真。

圖10～圖12展示了GAMCCO算法和以上4種卸載方案的對(duì)比。圖10中時(shí)延因子α和能耗因子β都設(shè)置為0.5，橫坐標(biāo)為遺傳迭代次數(shù)，縱坐標(biāo)為總代價(jià)，由于本文所建立的代價(jià)函數(shù)模型是卸載方案代價(jià)與本地代價(jià)的比值，因此縱坐標(biāo)的總代價(jià)沒(méi)有單位。

Figure 10 Comparison of 4 offloading schemes when α=0.5 and β=0.5

圖11中時(shí)延因子α設(shè)置為1，能耗因子β設(shè)置為0，這時(shí)只考慮時(shí)延代價(jià)。

Figure 11 Comparison of 4 offloading schemes when α=1 and β=0

圖12中時(shí)延因子α設(shè)置為0，能耗因子β設(shè)置為1，此時(shí)考慮的是能耗代價(jià)。

Figure 12 Comparison of 4 offloading schemes when α=0 and β=1

從圖10～圖12中可以發(fā)現(xiàn)，GAMCCO算法求出的方案均優(yōu)于其余4種卸載方案。和GAMCCO算法相比，GA算法的曲線收斂較快，這是由于本文在實(shí)現(xiàn)GA經(jīng)典方法時(shí)，在遺傳選擇的步驟中僅僅使用精英選擇的策略篩選出了精英解，并沒(méi)有對(duì)種群的其余個(gè)體進(jìn)行替換，導(dǎo)致大部分的卸載方案都沒(méi)有被考慮進(jìn)去，從而過(guò)早陷入了局部最優(yōu)，最差的情況在到達(dá)第30次迭代左右就收斂。而GAMCCO算法在遺傳迭代步驟中，使用精英選擇策略+隨機(jī)解替換的方式，篩選出當(dāng)前種群的較優(yōu)解，同時(shí)將較差解替換為隨機(jī)解，考量到了更多的卸載方案，因此收斂性能較好。但是，無(wú)論是GAMCCO還是GA算法求出的方案，都優(yōu)于本地執(zhí)行和邊緣執(zhí)行。而GAMCO算法則是采用了2個(gè)初始種群進(jìn)行遺傳迭代，即采用固定種群+隨機(jī)種群的方式，也能避免過(guò)早收斂的情況，如圖12所示，迭代到達(dá)80次才收斂，但其性能仍然劣于本文提出的GAMCCO算法的。GAMCCO算法可以有效降低多站點(diǎn)協(xié)同計(jì)算卸載時(shí)的總代價(jià)。

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

隨著物聯(lián)網(wǎng)和分布式服務(wù)的發(fā)展，未來(lái)物聯(lián)網(wǎng)應(yīng)用程序?qū)⑵毡椴捎梅植际讲渴鸬姆绞健Ｈ欢植际讲渴鹨肓苏军c(diǎn)間任務(wù)依賴的問(wèn)題，使得這種場(chǎng)景下的計(jì)算卸載更為復(fù)雜。為了優(yōu)化應(yīng)用程序的執(zhí)行代價(jià)(時(shí)延和能耗)，本文提出了基于遺傳算法的多站點(diǎn)協(xié)同計(jì)算卸載算法GAMCCO。該算法分析了應(yīng)用程序各站點(diǎn)、各任務(wù)之間的依賴關(guān)系，將計(jì)算任務(wù)卸載到邊緣節(jié)點(diǎn)或云端，以縮短應(yīng)用程序的執(zhí)行時(shí)間，降低終端的能耗。實(shí)驗(yàn)結(jié)果表明，GAMCCO算法可以有效減少應(yīng)用的執(zhí)行時(shí)間，降低能耗代價(jià)。本文還將GAMCCO算法和GA算法、GAMCO算法進(jìn)行了比較，GAMCCO算法比GA算法收斂更慢，不會(huì)過(guò)早收斂，性能也優(yōu)于GA和GAMCO算法的。但是，本文提出的算法并不總是能得到最優(yōu)解，在實(shí)驗(yàn)中存在著收斂較快，陷入局部最優(yōu)的情況。未來(lái)將繼續(xù)對(duì)代價(jià)模型進(jìn)行完善，同時(shí)考慮將遺傳算法和其他的啟發(fā)式算法相結(jié)合，盡可能減少陷入局部最優(yōu)的情況。