余思東 黃 欣 趙志剛

1(廣西農(nóng)業(yè)職業(yè)技術(shù)學(xué)院信息與機(jī)電工程系 廣西 南寧 530007) 2(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 廣西 南寧 530004)

0 引 言

近年來(lái)，隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，移動(dòng)云計(jì)算(Mobile Cloud Computing，MCC)[1]逐漸成為了緩解移動(dòng)設(shè)備資源受限問(wèn)題的有效方法，并且越來(lái)越受到學(xué)術(shù)界的重視。MCC為移動(dòng)設(shè)備提供了高效的遠(yuǎn)程計(jì)算服務(wù)，移動(dòng)用戶可以通過(guò)MCC將計(jì)算密集型的任務(wù)卸載到遠(yuǎn)程云[2]、本地微云[3]和ad hoc云[4]處理，任務(wù)完成后再將計(jì)算結(jié)果返回，以此降低任務(wù)在本地處理的開銷，緩解移動(dòng)設(shè)備資源受限的問(wèn)題。在MCC的應(yīng)用場(chǎng)景中，遠(yuǎn)程云雖然計(jì)算能力強(qiáng)，但會(huì)帶來(lái)延遲和開銷較高的問(wèn)題；本地微云計(jì)算能力強(qiáng)且通信帶寬大，但卻無(wú)法保證用戶能夠隨時(shí)隨地接入；而基于ad hoc網(wǎng)絡(luò)[5]架構(gòu)的ad hoc云作為無(wú)預(yù)設(shè)基礎(chǔ)設(shè)施下MCC的一種特殊擴(kuò)展，用戶可以通過(guò)與附近的移動(dòng)設(shè)備共享其相對(duì)豐富的閑置資源進(jìn)行任務(wù)卸載，具有部署快速和擴(kuò)展靈活等優(yōu)點(diǎn)[6]。由于ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性、異構(gòu)性,以及動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)?，如何設(shè)計(jì)動(dòng)態(tài)高效的任務(wù)卸載算法成為了亟待解決的問(wèn)題。

在ad hoc云系統(tǒng)中，任務(wù)卸載不僅需要考慮完成時(shí)間和能量消耗，還要考慮自身的電池能量、信道環(huán)境和可用資源節(jié)點(diǎn)信息等。雖然現(xiàn)有工作對(duì)卸載決策和資源分配都分別進(jìn)行了較為細(xì)致的分析研究，但任務(wù)的卸載決策和資源分配顯然不能分開處理。此外，受信道環(huán)境、電池續(xù)航能力等因素的影響，系統(tǒng)中可用資源節(jié)點(diǎn)在為終端提供服務(wù)時(shí)顯然會(huì)消耗自身資源，這將嚴(yán)重影響其參與任務(wù)卸載的積極性，并且系統(tǒng)中任務(wù)的動(dòng)態(tài)到達(dá)性以及任務(wù)完成后被移除的隨機(jī)性，會(huì)產(chǎn)生資源分配不均衡等問(wèn)題。

為實(shí)現(xiàn)高效的任務(wù)卸載，現(xiàn)有研究為MCC設(shè)計(jì)了各種策略讓移動(dòng)用戶決定是否將任務(wù)卸載到遠(yuǎn)程執(zhí)行。為了最小化用戶開銷，文獻(xiàn)[7]提出了一種基于博弈論的多代理節(jié)點(diǎn)資源分配方案，但該方案僅將延遲開銷作為約束條件而忽略了其對(duì)用戶體驗(yàn)的影響，并且沒有考慮時(shí)變信道的影響。文獻(xiàn)[8]則嘗試通過(guò)Lyapunov優(yōu)化來(lái)實(shí)現(xiàn)電量消耗、處理速度和服務(wù)價(jià)格的平衡，但僅考慮了對(duì)延遲不敏感的應(yīng)用，并且使用傳輸隊(duì)列的大小間接度量應(yīng)用程序的延遲。文獻(xiàn)[9]在決定任務(wù)卸載時(shí)綜合考慮了能耗、延遲和價(jià)格因素，但沒有考慮任務(wù)的傳輸調(diào)度和無(wú)線信道的時(shí)變特性。

目前對(duì)ad hoc云中任務(wù)卸載的研究仍處于初步階段，僅有很少的研究針對(duì)這種特殊的分布式架構(gòu)提出了有效的任務(wù)卸載方案。為解決計(jì)算密集型應(yīng)用卸載問(wèn)題，文獻(xiàn)[10]提出了一種在線批調(diào)度啟發(fā)式方法，動(dòng)態(tài)地選擇移動(dòng)設(shè)備進(jìn)行任務(wù)卸載。針對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的異構(gòu)特性，文獻(xiàn)[11]根據(jù)能耗和延遲約束設(shè)計(jì)了一種異構(gòu)感知的任務(wù)分配算法，但沒有考慮節(jié)點(diǎn)的移動(dòng)性和網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化特性。為使移動(dòng)用戶能夠獲得最優(yōu)的任務(wù)卸載決策，文獻(xiàn)[12]提出了一種基于馬爾可夫決策過(guò)程的卸載模型，動(dòng)態(tài)決定將任務(wù)卸載到可用的資源節(jié)點(diǎn)。為降低用戶能耗和計(jì)算成本，文獻(xiàn)[13]提出了一種基于微云輔助的任務(wù)分配機(jī)制，制定了一個(gè)兩階段Stackelberg博弈來(lái)確定節(jié)點(diǎn)提供的執(zhí)行單元數(shù)量，而用戶將以此確定補(bǔ)償策略，但是該機(jī)制在任務(wù)分配時(shí)并未考慮可用移動(dòng)設(shè)備的資源異構(gòu)特性。文獻(xiàn)[14]提出了一種用于異構(gòu)移動(dòng)云的通用卸載框架，它使用移動(dòng)設(shè)備、附近的小型云和遠(yuǎn)程云來(lái)提高M(jìn)CC服務(wù)的性能和可用性，然而，所提出的框架并沒有充分考慮ad hoc云的特性。為了滿足移動(dòng)設(shè)備的延遲限制，文獻(xiàn)[15]提出了一種節(jié)能任務(wù)調(diào)度方案，并針對(duì)不同的任務(wù)，設(shè)計(jì)了一種自適應(yīng)概率調(diào)度器，不僅能滿足延遲約束，而且能在執(zhí)行計(jì)算密集型實(shí)時(shí)應(yīng)用程序時(shí)最小化能耗，但其計(jì)算復(fù)雜度較高。

以上研究主要針對(duì)最小化用戶能耗和延遲等目標(biāo)來(lái)設(shè)計(jì)解決方案，但沒有綜合考慮用戶的多目標(biāo)需求以及ad hoc云中的多因素影響進(jìn)行任務(wù)卸載決策和資源分配。鑒于此，本文綜合考慮用戶多目標(biāo)需求設(shè)計(jì)任務(wù)卸載決策模型，并提出一種融合遺傳算法和蟻群算法的任務(wù)分配算法，綜合考慮用戶需求動(dòng)態(tài)決策，充分利用遺傳算法的快速搜索能力和蟻群算法的正反饋機(jī)，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的實(shí)際狀態(tài)進(jìn)行高效的任務(wù)分配，最后通過(guò)仿真驗(yàn)證了所提算法的有效性。

1 系統(tǒng)模型及卸載決策

1.1 系統(tǒng)模型

為了不失一般性，本文選取ad hoc網(wǎng)絡(luò)中的一個(gè)分簇[16]作為ad hoc云系統(tǒng)，系統(tǒng)中只存在一個(gè)簇頭節(jié)點(diǎn)，其他節(jié)點(diǎn)則為簇內(nèi)成員節(jié)點(diǎn)，并且簇頭節(jié)點(diǎn)往往具有距離簇內(nèi)成員節(jié)點(diǎn)較近、相對(duì)移動(dòng)性較低、能量穩(wěn)定等特點(diǎn)。假設(shè)在ad hoc云系統(tǒng)中有一個(gè)移動(dòng)用戶(Mobile User，MU)節(jié)點(diǎn)和N個(gè)移動(dòng)微云(Mobile Cloudlet，MC)節(jié)點(diǎn)，MU有一組計(jì)算密集型任務(wù)M需要處理，如果僅僅依靠自身處理這些任務(wù)很可能會(huì)耗盡自身資源并且?guī)?lái)較高的延遲，十分影響用戶體驗(yàn)。而其他N個(gè)MC節(jié)點(diǎn)則擁有相對(duì)豐富的閑置資源(如計(jì)算能力和電池電量)，在Wi-Fi覆蓋范圍內(nèi)，MU可以將部分或全部任務(wù)卸載到MC節(jié)點(diǎn)上執(zhí)行，任務(wù)完成后再將計(jì)算結(jié)果返回，從而實(shí)現(xiàn)對(duì)自身資源的擴(kuò)展。在資源受限的情況下，各節(jié)點(diǎn)設(shè)備不會(huì)無(wú)償?shù)貫槠渌?jié)點(diǎn)提供資源，而分布式的網(wǎng)絡(luò)架構(gòu)也很難實(shí)現(xiàn)最大化利用系統(tǒng)資源，因此本文采用集中式策略來(lái)進(jìn)行任務(wù)卸載過(guò)程的統(tǒng)一調(diào)度控制，并選取需要實(shí)時(shí)與所有節(jié)點(diǎn)進(jìn)行信息交互的簇頭節(jié)點(diǎn)作為集中控制器。MU和MC節(jié)點(diǎn)均通過(guò)與集中控制器的信息交互來(lái)實(shí)現(xiàn)整個(gè)任務(wù)卸載的過(guò)程。由于MU的任務(wù)卸載模型幾乎完全涵蓋了實(shí)際移動(dòng)應(yīng)用程序的各個(gè)方面，其較高的復(fù)雜性可能會(huì)使問(wèn)題難以解決，因此為了簡(jiǎn)化計(jì)算，本文設(shè)計(jì)如圖1所示的任務(wù)卸載模型。

圖1 任務(wù)卸載模型

選定系統(tǒng)中的簇頭節(jié)點(diǎn)作為集中控制器，MU根據(jù)需求將任務(wù)按照優(yōu)先級(jí)排序，并且當(dāng)任務(wù)序列達(dá)到上限時(shí)，后續(xù)到達(dá)的任務(wù)將被放棄執(zhí)行。對(duì)比任務(wù)在本地執(zhí)行的開銷和卸載到MC的開銷之后，MU決定是將任務(wù)卸載還是留在本地執(zhí)行，并且將需要卸載的任務(wù)隊(duì)列信息發(fā)送給集中控制器。集中控制器負(fù)責(zé)收集節(jié)點(diǎn)信息，并根據(jù)節(jié)點(diǎn)的實(shí)際狀態(tài)將MU決定卸載的任務(wù)分配給相應(yīng)的MC，任務(wù)執(zhí)行完成后MC再將結(jié)果返回給MU。在本文中，集中控制器雖然同樣具備MC的功能，但由于其作為簇頭節(jié)點(diǎn)需要通過(guò)與網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行周期性的信息交互來(lái)實(shí)時(shí)動(dòng)態(tài)地管理網(wǎng)絡(luò)中所有節(jié)點(diǎn)的信息，因此默認(rèn)其只負(fù)責(zé)集中調(diào)度控制，而不作為任務(wù)卸載請(qǐng)求和計(jì)算資源提供設(shè)備,具體流程如下：

(1) 各節(jié)點(diǎn)設(shè)備周期性地向集中控制器發(fā)送自身設(shè)備信息，包括計(jì)算能力、通信能力、可用電池資源、任務(wù)隊(duì)列等信息。

(2) 集中控制器根據(jù)收集到的節(jié)點(diǎn)信息對(duì)節(jié)點(diǎn)編號(hào)并將信息整理至可用資源列表，為后續(xù)任務(wù)卸載做準(zhǔn)備。

(3) MU根據(jù)需求向集中控制器發(fā)送任務(wù)卸載請(qǐng)求。

(4) 集中控制器將收集到的節(jié)點(diǎn)信息和網(wǎng)絡(luò)狀態(tài)發(fā)送給MU。

(5) MU根據(jù)收到的信息作出卸載決策并將需要卸載的任務(wù)隊(duì)列信息發(fā)送給集中控制器。

(6) 集中控制器采用合理的資源分配算法將任務(wù)分配給相應(yīng)的MC并將信息反饋給MU。

(7) MU根據(jù)集中控制器的反饋信息將需要卸載任務(wù)的數(shù)據(jù)發(fā)送給相應(yīng)的MC。

(8) MC在收到數(shù)據(jù)后進(jìn)行處理，完成后將結(jié)果返回給MU并將信息反饋給集中控制器。

(9) 集中控制器將已完成任務(wù)從隊(duì)列中移除，重復(fù)以上過(guò)程直到任務(wù)隊(duì)列為空。

1.2 卸載決策

在資源有限的情況下，網(wǎng)絡(luò)中的節(jié)點(diǎn)不會(huì)無(wú)償?shù)貫槠渌脩籼峁┓?wù)，因此影響MU進(jìn)行任務(wù)卸載決策的因素主要有任務(wù)完成時(shí)間、能耗和需要額外支付給MC的開銷。完成時(shí)間主要包括兩部分：傳輸時(shí)間和計(jì)算時(shí)間；能耗也包括兩部分：傳輸能耗和執(zhí)行能耗；額外支付給MC的開銷主要取決于其計(jì)算速度和剩余可用負(fù)載。

假設(shè)MU決定將大小為D編號(hào)為m的任務(wù)卸載到編號(hào)為n的MC上執(zhí)行，根據(jù)香農(nóng)極限理論，最大數(shù)據(jù)傳輸速率可以表示為：

Rn=Blog(1+SINRn)

(1)

式中：Rn為數(shù)據(jù)傳輸速率；B為帶寬；SINRn為信號(hào)與干擾加噪聲比，通常表示無(wú)線鏈路的質(zhì)量，可以通過(guò)式(2)計(jì)算：

(2)

(3)

傳輸能耗為：

(4)

需要額外支付給MC節(jié)點(diǎn)的開銷定義為：

(5)

(6)

執(zhí)行能耗為：

(7)

式中：k為MC的處理功率。本文暫不考慮任務(wù)完成后數(shù)據(jù)回傳階段產(chǎn)生的能量消耗和傳輸時(shí)間，因?yàn)榉祷亟Y(jié)果的大小應(yīng)當(dāng)遠(yuǎn)小于輸入數(shù)據(jù)的大小。 因此，這一階段的消耗很小，可以忽略。根據(jù)以上計(jì)算定義函數(shù)fc(x)為任務(wù)卸載的總開銷，則：

(8)

式中：α、β、γ為完成時(shí)間、能耗、額外支付的開銷這三個(gè)因素占總開銷的權(quán)重系數(shù)，并且可以根據(jù)MU的實(shí)際需求動(dòng)態(tài)設(shè)置，α+β+γ=1。同理，如果MU選擇將任務(wù)留在本地執(zhí)行，則執(zhí)行時(shí)間和能耗分別為：

(9)

(10)

(11)

式中：μ、η為執(zhí)行時(shí)間、能耗占總開銷的權(quán)重系數(shù)，并且同樣可以根據(jù)MU的實(shí)際狀態(tài)設(shè)置，μ+η=1。當(dāng)且僅當(dāng)fc(x)

2 融合遺傳蟻群算法的任務(wù)分配算法

合理的任務(wù)分配算法能充分利用節(jié)點(diǎn)的計(jì)算資源，提升整個(gè)網(wǎng)絡(luò)的系統(tǒng)性能。但當(dāng)網(wǎng)絡(luò)中存在大量節(jié)點(diǎn)時(shí)，用傳統(tǒng)的數(shù)學(xué)方法來(lái)解決這類任務(wù)分配問(wèn)題往往需要大量的計(jì)算時(shí)間，而啟發(fā)式算法可以在相對(duì)較短的時(shí)間內(nèi)獲得接近最優(yōu)解的結(jié)果。相比于其他啟發(fā)式算法，遺傳算法由于前期收斂速度快且較為穩(wěn)定而廣泛應(yīng)用于任務(wù)調(diào)度領(lǐng)域，但卻存在易陷入局部收斂而無(wú)法獲得全局最優(yōu)解的問(wèn)題；蟻群算法則具有良好的適應(yīng)能力和正反饋機(jī)制，在求解多目標(biāo)組合優(yōu)化問(wèn)題上有著獨(dú)特的優(yōu)勢(shì)，但由于初始信息素積累較慢容易導(dǎo)致迭代時(shí)間較長(zhǎng)。因此本文采用融合遺傳算法和蟻群算法的方法來(lái)解決任務(wù)分配問(wèn)題，核心思想是利用遺傳算法的快速收斂能力得到可行解，在其迭代速度降低到一定水平而陷入局部最優(yōu)之前，將求得的可行解對(duì)應(yīng)轉(zhuǎn)化為蟻群算法的初始信息素并開始新的迭代過(guò)程。這樣不僅可以避免使遺傳算法陷入局部收斂，也解決了蟻群算法初始信息素積累緩慢的問(wèn)題，從而實(shí)現(xiàn)兩種算法的有機(jī)結(jié)合。

2.1 基于遺傳算法的快速搜索

遺傳算法[17]通過(guò)模擬生物進(jìn)化過(guò)程搜索最適應(yīng)環(huán)境的個(gè)體，將任務(wù)分配問(wèn)題的求解問(wèn)題轉(zhuǎn)化為染色體種群編碼問(wèn)題，根據(jù)設(shè)計(jì)的適應(yīng)度函數(shù)值對(duì)相應(yīng)的任務(wù)分配方案進(jìn)行評(píng)估，利用選擇、交叉和變異等遺傳操作建立迭代過(guò)程，使產(chǎn)生的新一代個(gè)體在經(jīng)過(guò)不斷的迭代進(jìn)化之后，性能不斷優(yōu)于上一代，逐漸求解出接近最優(yōu)方案的任務(wù)分配方案。

2.1.1染色體編碼

為了能通過(guò)遺傳算法進(jìn)行迭代尋找合理的任務(wù)分配方案，首先需要將任務(wù)分配問(wèn)題進(jìn)行編碼，形成染色體種群，從而建立實(shí)際任務(wù)分配方案和染色體種群編碼之間的聯(lián)系。染色體長(zhǎng)度即為任務(wù)隊(duì)列的最大容量l，其中的元素對(duì)應(yīng)相應(yīng)的任務(wù)，元素的值代表該任務(wù)被分配到的MC節(jié)點(diǎn)的編號(hào)，編號(hào)由集中控制器統(tǒng)一分配管理，并且一般為固定不變的值。將染色體編碼表示為Gi=(g1,g2,…,gl)，其中i=1,2,…,S，S為算法編碼空間的大小即任務(wù)分配方案的大??；gj表示任務(wù)分配結(jié)果，并且gj∈[1,N]，j∈[1,l]，例如當(dāng)G=(3,2,1,2,3)時(shí)，表示任務(wù)1和5將被分配給編號(hào)為3的MC節(jié)點(diǎn)執(zhí)行，任務(wù)2和4被分配給編號(hào)為2的MC節(jié)點(diǎn)執(zhí)行，任務(wù)3被分配給編號(hào)為1的MC節(jié)點(diǎn)執(zhí)行，特別的是，當(dāng)選擇將任務(wù)留在本地執(zhí)行時(shí)gj為0，其他情況以此類推。

2.1.2種群初始化

為加快算法的收斂速度，假設(shè)初始種群中的每個(gè)任務(wù)按照一定的隨機(jī)概率分配給MC執(zhí)行，且MC被選擇執(zhí)行的概率為：

(12)

2.1.3適應(yīng)度函數(shù)設(shè)計(jì)

合理的適應(yīng)度函數(shù)設(shè)計(jì)能夠有效評(píng)估種群中染色體的環(huán)境適應(yīng)能力，同時(shí)適應(yīng)度函數(shù)的值也對(duì)應(yīng)著任務(wù)分配方案性能優(yōu)劣的評(píng)判，并最終決定著求解出的任務(wù)分配方案是否接近最優(yōu)解的判斷。由于遺傳算法中的適應(yīng)度函數(shù)值一般為非負(fù)值，因此本文結(jié)合式(8)定義適應(yīng)度函數(shù)為：

(13)

式中：α、β、γ分別表示完成時(shí)間、能耗、需要額外支付的開銷的權(quán)重系數(shù)。

2.1.4遺傳操作

選擇、交叉和變異是三種基本的遺傳算法操作，分別對(duì)應(yīng)著自然界中生物繁衍過(guò)程中的正常交配、跨種群雜交和基因突變等現(xiàn)象，是保證遺傳算法能夠不斷產(chǎn)生新的優(yōu)秀個(gè)體的根本。對(duì)其具體設(shè)計(jì)如下：

(1) 選擇操作模擬了自然界中的自然選擇過(guò)程，能夠根據(jù)種群中個(gè)體的適應(yīng)度函數(shù)值將具有較大值的個(gè)體篩選出來(lái)，以便更好地從種群中獲得相對(duì)優(yōu)秀的個(gè)體。本文根據(jù)適應(yīng)度函數(shù)值比重選擇的形式和輪盤賭的方式來(lái)實(shí)現(xiàn)選擇操作。對(duì)于染色體群G={G1,G2,…,GS}，個(gè)體Gj∈G的適應(yīng)度值為F(Gj)，則其選擇概率為：

(14)

式(14)決定了更新后的種群染色體的概率分布情況。

(2) 交叉操作模擬了自然界中生物有性繁殖的基因重組過(guò)程，下一代的個(gè)體可以通過(guò)這種交叉重組的方式獲得上一代的優(yōu)秀基因，從而產(chǎn)生比上一代更加適應(yīng)環(huán)境的個(gè)體。本文采用面向知識(shí)領(lǐng)域的位交叉來(lái)模擬交叉操作，并以此來(lái)計(jì)算個(gè)體染色體上每一位基因的適應(yīng)度函數(shù)值，并結(jié)合式(8)定義基因的適應(yīng)度函數(shù)為：

(15)

在計(jì)算得到每一位基因的適應(yīng)度函數(shù)值后，可以根據(jù)染色體上對(duì)應(yīng)位置基因的適應(yīng)度函數(shù)值大小對(duì)基因進(jìn)行篩選，并選擇將適應(yīng)度函數(shù)值較小的基因保留下來(lái)。

(3) 變異操作模擬了自然界中普遍存在的基因突變現(xiàn)象，合理的設(shè)計(jì)不僅有利于種群多樣性的豐富，還能防止算法在獲得最優(yōu)解之前提前收斂。與另外兩種遺傳操作相比，變異操作僅充當(dāng)可選擇性的非必要輔助手段，僅在求得的任務(wù)分配方案不合理時(shí)才會(huì)使用。這里同樣采用面向領(lǐng)域知識(shí)的位變異來(lái)模擬變異操作，類似地，基因的變異概率依然與適應(yīng)度函數(shù)值大小相關(guān)，可以定義為：

(16)

式中：hi表示染色體上第i位基因的適應(yīng)度函數(shù)值。顯然，任務(wù)完成時(shí)間越長(zhǎng)、能量消耗和額外開銷越高的任務(wù)，分配結(jié)果對(duì)應(yīng)的基因更容易發(fā)生變異。

2.1.5種群更新操作

按照適應(yīng)度函數(shù)值從大到小對(duì)種群中個(gè)體進(jìn)行排序，并用前T個(gè)個(gè)體替代上一代種群中的對(duì)應(yīng)個(gè)體，從而形成新的種群。

2.2 基于蟻群算法的精確求解

蟻群算法具備較好的魯棒性、并行性和正反饋特性，可以很好地應(yīng)用于任務(wù)調(diào)度問(wèn)題[18]。但是當(dāng)需要求解的問(wèn)題規(guī)模較大時(shí)，由于該算法的本質(zhì)決定了信息素的產(chǎn)生需要消耗大量的時(shí)間，容易導(dǎo)致算法收斂速度較慢，因此需要結(jié)合遺傳算法前期的快速搜索能力實(shí)現(xiàn)對(duì)任務(wù)分配方案的精確求解。為了將任務(wù)分配問(wèn)題對(duì)應(yīng)為螞蟻種群的外出覓食問(wèn)題，需要將能夠充分反映節(jié)點(diǎn)計(jì)算資源豐富度的硬件性能信息對(duì)應(yīng)為蟻群算法的初始信息素。

2.2.1算法初始化

將信息素的值賦給MC，并且信息素值的大小表示MC節(jié)點(diǎn)上可用資源的多少。根據(jù)前期遺傳算法輸出的最終結(jié)果可以解析出對(duì)應(yīng)的任務(wù)分配方案，將該方案對(duì)應(yīng)地轉(zhuǎn)化為MC節(jié)點(diǎn)的初始信息素值，根據(jù)影響任務(wù)執(zhí)行的異構(gòu)因素定義每個(gè)MC節(jié)點(diǎn)的初始信息素值為：

(17)

2.2.2轉(zhuǎn)移概率設(shè)計(jì)

轉(zhuǎn)移概率的大小是將下一個(gè)任務(wù)分配給系統(tǒng)中合適的MC節(jié)點(diǎn)的主要參考依據(jù)，這里同樣根據(jù)節(jié)點(diǎn)的異構(gòu)性將節(jié)點(diǎn)的計(jì)算速度、剩余可用負(fù)載和剩余電池能量作為其性能優(yōu)劣的主要判斷依據(jù)，因此在t時(shí)刻的轉(zhuǎn)移概率的設(shè)計(jì)主要取決于每個(gè)節(jié)點(diǎn)的計(jì)算速度、剩余可用負(fù)載、剩余電池能量和信息素值。則轉(zhuǎn)移概率可以表示為：

(18)

2.2.3信息素更新

當(dāng)外出覓食的螞蟻從節(jié)點(diǎn)轉(zhuǎn)移時(shí)，節(jié)點(diǎn)上的信息素濃度就會(huì)相應(yīng)地發(fā)生變化，因此需要及時(shí)更新信息素的值才能提高蟻群算法的收斂精度。這里根據(jù)求得的可行解對(duì)應(yīng)的任務(wù)分配方案及任務(wù)的實(shí)際完成情況，對(duì)求得的所有路徑上的信息素值進(jìn)行更新，則信息素值的更新依據(jù)可以定義為：

τi(t+1)=τi(t)+Δτi(t)i=0,1,…,N

(19)

式中：當(dāng)任務(wù)執(zhí)行成功時(shí)有Δτi(t)=ksfc(x)，當(dāng)任務(wù)執(zhí)行失敗時(shí)有Δτi(t)=klfc(x)，ks、kl分別為任務(wù)執(zhí)行成功、失敗的獎(jiǎng)懲因子，并且ks>kl。

2.3 融合算法流程描述

為充分利用遺傳算法的全局快速搜索能力和蟻群算法良好的正反饋機(jī)制，對(duì)它們進(jìn)行優(yōu)勢(shì)互補(bǔ)，在完成了基于遺傳算法的快速搜索和基于蟻群算法的精確求解設(shè)計(jì)之后，給出融合算法的詳細(xì)流程，如算法1所示。

算法1融合算法

輸入： 隨機(jī)產(chǎn)生的初始種群。

輸出： 全局最優(yōu)的任務(wù)分配方案。

步驟1參數(shù)初始化。

步驟2初始化種群。

步驟3計(jì)算種群中個(gè)體的適應(yīng)度值。

步驟4選擇適應(yīng)度值高的個(gè)體作為父代染色體。

步驟5按概率進(jìn)行遺傳操作。

步驟6判斷是否滿足約束條件，是則轉(zhuǎn)到下一步，否則將適應(yīng)度值函數(shù)值較高的個(gè)體加入種群并返回步驟3。

步驟7將染色體種群中適應(yīng)度函數(shù)值最高的個(gè)體作為最優(yōu)解輸出并進(jìn)行下一步。

步驟8根據(jù)步驟7的最優(yōu)解輸出初始化蟻群。

步驟9根據(jù)轉(zhuǎn)移概率選擇下一節(jié)點(diǎn)。

步驟10更新信息素。

步驟11計(jì)算適應(yīng)度值。

步驟12判斷是否滿足約束條件，是則輸出結(jié)果，否則返回步驟9重新進(jìn)行迭代操作。

3 仿真對(duì)比分析

為驗(yàn)證本文融合遺傳蟻群算法的任務(wù)卸載算法(Genetic Ant Colony Algorithm，GACA)的性能，將其與隨機(jī)任務(wù)分配算法(Random Task Assignment Algorithm，RTA)、異構(gòu)感知任務(wù)分配算法(Heterogeneity-aware Task Allocation Algorithm，HTA)[9]和遺傳算法(Genetic Algorithm，GA)進(jìn)行仿真對(duì)比，RTA是將任務(wù)完全隨機(jī)地分配給可用節(jié)點(diǎn)，而HTA則是根據(jù)節(jié)點(diǎn)性能和任務(wù)大小進(jìn)行任務(wù)分配。

表1 MC的位置

表2 任務(wù)設(shè)置

任務(wù)完成時(shí)間是影響用戶體驗(yàn)最重要的因素，圖2為GACA、RTA、HTA、GA在相同任務(wù)設(shè)置情況下的平均完成時(shí)間隨著節(jié)點(diǎn)數(shù)量不斷變化的關(guān)系曲線。

圖2 平均任務(wù)完成時(shí)間對(duì)比

隨著節(jié)點(diǎn)數(shù)量的增加，任務(wù)的平均完成時(shí)間總體呈下降趨勢(shì)，這是因?yàn)槿蝿?wù)數(shù)量固定的情況下，節(jié)點(diǎn)數(shù)量的增加會(huì)顯著提高任務(wù)分配的效率。其中：對(duì)所有任務(wù)進(jìn)行完全隨機(jī)分配的RTA性能較差并且不夠穩(wěn)定，盡管節(jié)點(diǎn)數(shù)量在不斷增加，RTA也無(wú)法充分地利用可用資源；HTA根據(jù)節(jié)點(diǎn)設(shè)備的性能進(jìn)行任務(wù)分配，忽略了節(jié)點(diǎn)間的通信開銷，雖然也能不斷降低任務(wù)執(zhí)行時(shí)間，但總體效果一般；GA與GACA更加有效，并且當(dāng)系統(tǒng)中可用節(jié)點(diǎn)設(shè)備數(shù)量較少時(shí)，這兩種算法下任務(wù)的平穩(wěn)完成時(shí)間相差不明顯，這是因?yàn)楫?dāng)系統(tǒng)中的可用MC節(jié)點(diǎn)數(shù)量較少時(shí)，蟻群算法對(duì)于任務(wù)分配方案的精確求解能力受到了一定的限制，而遺傳算法可以在前期利用全局搜索能力快速得出較優(yōu)的任務(wù)分配方案。隨著系統(tǒng)中可用資源節(jié)點(diǎn)設(shè)備數(shù)量的不斷增加，由于GACA相比于GA具有更精確的求解能力，所以任務(wù)的平均完成時(shí)間呈現(xiàn)出更明顯的下降趨勢(shì)。

能量消耗同樣是影響用戶體驗(yàn)的另一重要因素，由于節(jié)點(diǎn)能量有限，因此較低的能耗能支持設(shè)備運(yùn)行更長(zhǎng)的時(shí)間，圖3為本文GACA和RTA、HTA、GA在相同任務(wù)設(shè)置情況下的平均任務(wù)執(zhí)行能耗隨著節(jié)點(diǎn)數(shù)量不斷變化的關(guān)系曲線。

圖3 平均任務(wù)執(zhí)行能耗對(duì)比

RTA的性能依然較差并且不夠穩(wěn)定，任務(wù)的平均完成能耗相比于其他算法依然存在較大差距；隨著節(jié)點(diǎn)數(shù)量的增加，HTA雖然也能降低能耗，但總體效果不明顯，這是因?yàn)楸M管節(jié)點(diǎn)數(shù)量不斷增加，而HTA依然優(yōu)先選擇執(zhí)行速度快的節(jié)點(diǎn)，從而導(dǎo)致了較高的能耗；GACA與GA具有明顯的優(yōu)勢(shì)，但平均任務(wù)執(zhí)行能耗優(yōu)化性能相差不大，甚至GA在節(jié)點(diǎn)數(shù)量較少時(shí)表現(xiàn)更好。這是由于GACA為了提升網(wǎng)絡(luò)整體性能，在適應(yīng)度函數(shù)的設(shè)計(jì)上忽略了一定程度的能耗性能，但是隨著系統(tǒng)中MC節(jié)點(diǎn)設(shè)備數(shù)量的增加，蟻群算法所具備的精確求解能力對(duì)最優(yōu)任務(wù)分配方案求解的影響逐漸增大，GACA的平均任務(wù)完成能耗呈現(xiàn)出明顯的下降趨勢(shì)。

迭代次數(shù)是衡量啟發(fā)式算法性能優(yōu)劣的重要指標(biāo)，圖4為GA和GACA在相同節(jié)點(diǎn)數(shù)量和任務(wù)設(shè)置的情況下平均任務(wù)完成時(shí)間隨著迭代次數(shù)逐漸增加的變化曲線對(duì)比情況。隨著迭代次數(shù)的增加，任務(wù)的平均完成時(shí)間顯著降低，而相比于GA，GACA性能更佳，收斂速度更快。這是由于GACA融合了遺傳算法的全局搜索能力和蟻群算法的反饋能力，收斂速度加快，得到更優(yōu)的任務(wù)分配方案，克服了GA易獲得局部最優(yōu)解的缺陷，縮短任務(wù)分配問(wèn)題求解時(shí)間，取得更好的效果。

圖4 平均任務(wù)完成時(shí)間對(duì)比

4 結(jié) 語(yǔ)

本文研究ad hoc云環(huán)境下的任務(wù)卸載算法，為了有效降低任務(wù)完成的時(shí)間和能耗，設(shè)計(jì)基于用戶多目標(biāo)需求的任務(wù)卸載決策模型，并選取網(wǎng)絡(luò)中具有穩(wěn)定能量和較低移動(dòng)性的簇頭節(jié)點(diǎn)作為集中控制器進(jìn)行卸載決策后的任務(wù)分配；提出融合遺傳算法和蟻群算法的高效任務(wù)卸載算法，綜合利用遺傳算法的快速搜索能力和蟻群算法的正反饋機(jī)制，迅速得到更優(yōu)的任務(wù)分配方案。仿真結(jié)果表明，相比于隨機(jī)任務(wù)分配算法、異構(gòu)感知任務(wù)分配算法和遺傳算法，本文算法能有效降低任務(wù)的平均執(zhí)行時(shí)間和能量消耗，實(shí)現(xiàn)高效的任務(wù)卸載，從而提升整個(gè)網(wǎng)絡(luò)的性能。