一種融合遺傳蟻群算法的ad hoc云任務卸載算法

余思東 黃 欣 趙志剛

1(廣西農業職業技術學院信息與機電工程系 廣西 南寧 530007) 2(廣西大學計算機與電子信息學院 廣西 南寧 530004)

0 引 言

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

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

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

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

以上研究主要針對最小化用戶能耗和延遲等目標來設計解決方案，但沒有綜合考慮用戶的多目標需求以及ad hoc云中的多因素影響進行任務卸載決策和資源分配。鑒于此，本文綜合考慮用戶多目標需求設計任務卸載決策模型，并提出一種融合遺傳算法和蟻群算法的任務分配算法，綜合考慮用戶需求動態決策，充分利用遺傳算法的快速搜索能力和蟻群算法的正反饋機，根據網絡中節點的實際狀態進行高效的任務分配，最后通過仿真驗證了所提算法的有效性。

1 系統模型及卸載決策

1.1 系統模型

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

圖1 任務卸載模型

選定系統中的簇頭節點作為集中控制器，MU根據需求將任務按照優先級排序，并且當任務序列達到上限時，后續到達的任務將被放棄執行。對比任務在本地執行的開銷和卸載到MC的開銷之后，MU決定是將任務卸載還是留在本地執行，并且將需要卸載的任務隊列信息發送給集中控制器。集中控制器負責收集節點信息，并根據節點的實際狀態將MU決定卸載的任務分配給相應的MC，任務執行完成后MC再將結果返回給MU。在本文中，集中控制器雖然同樣具備MC的功能，但由于其作為簇頭節點需要通過與網絡中所有節點進行周期性的信息交互來實時動態地管理網絡中所有節點的信息，因此默認其只負責集中調度控制，而不作為任務卸載請求和計算資源提供設備,具體流程如下：

(1) 各節點設備周期性地向集中控制器發送自身設備信息，包括計算能力、通信能力、可用電池資源、任務隊列等信息。

(2) 集中控制器根據收集到的節點信息對節點編號并將信息整理至可用資源列表，為后續任務卸載做準備。

(3) MU根據需求向集中控制器發送任務卸載請求。

(4) 集中控制器將收集到的節點信息和網絡狀態發送給MU。

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

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

(7) MU根據集中控制器的反饋信息將需要卸載任務的數據發送給相應的MC。

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

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

1.2 卸載決策

在資源有限的情況下，網絡中的節點不會無償地為其他用戶提供服務，因此影響MU進行任務卸載決策的因素主要有任務完成時間、能耗和需要額外支付給MC的開銷。完成時間主要包括兩部分：傳輸時間和計算時間；能耗也包括兩部分：傳輸能耗和執行能耗；額外支付給MC的開銷主要取決于其計算速度和剩余可用負載。

假設MU決定將大小為D編號為m的任務卸載到編號為n的MC上執行，根據香農極限理論，最大數據傳輸速率可以表示為：

Rn=Blog(1+SINRn)

(1)

式中：Rn為數據傳輸速率；B為帶寬；SINRn為信號與干擾加噪聲比，通常表示無線鏈路的質量，可以通過式(2)計算：

(2)

(3)

傳輸能耗為：

(4)

需要額外支付給MC節點的開銷定義為：

(5)

(6)

執行能耗為：

(7)

式中：k為MC的處理功率。本文暫不考慮任務完成后數據回傳階段產生的能量消耗和傳輸時間，因為返回結果的大小應當遠小于輸入數據的大小。 因此，這一階段的消耗很小，可以忽略。根據以上計算定義函數fc(x)為任務卸載的總開銷，則：

(8)

式中：α、β、γ為完成時間、能耗、額外支付的開銷這三個因素占總開銷的權重系數，并且可以根據MU的實際需求動態設置，α+β+γ=1。同理，如果MU選擇將任務留在本地執行，則執行時間和能耗分別為：

(9)

(10)

(11)

式中：μ、η為執行時間、能耗占總開銷的權重系數，并且同樣可以根據MU的實際狀態設置，μ+η=1。當且僅當fc(x)

2 融合遺傳蟻群算法的任務分配算法

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

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

遺傳算法[17]通過模擬生物進化過程搜索最適應環境的個體，將任務分配問題的求解問題轉化為染色體種群編碼問題，根據設計的適應度函數值對相應的任務分配方案進行評估，利用選擇、交叉和變異等遺傳操作建立迭代過程，使產生的新一代個體在經過不斷的迭代進化之后，性能不斷優于上一代，逐漸求解出接近最優方案的任務分配方案。

2.1.1染色體編碼

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

2.1.2種群初始化

為加快算法的收斂速度，假設初始種群中的每個任務按照一定的隨機概率分配給MC執行，且MC被選擇執行的概率為：

(12)

2.1.3適應度函數設計

合理的適應度函數設計能夠有效評估種群中染色體的環境適應能力，同時適應度函數的值也對應著任務分配方案性能優劣的評判，并最終決定著求解出的任務分配方案是否接近最優解的判斷。由于遺傳算法中的適應度函數值一般為非負值，因此本文結合式(8)定義適應度函數為：

(13)

式中：α、β、γ分別表示完成時間、能耗、需要額外支付的開銷的權重系數。

2.1.4遺傳操作

選擇、交叉和變異是三種基本的遺傳算法操作，分別對應著自然界中生物繁衍過程中的正常交配、跨種群雜交和基因突變等現象，是保證遺傳算法能夠不斷產生新的優秀個體的根本。對其具體設計如下：

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

(14)

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

(2) 交叉操作模擬了自然界中生物有性繁殖的基因重組過程，下一代的個體可以通過這種交叉重組的方式獲得上一代的優秀基因，從而產生比上一代更加適應環境的個體。本文采用面向知識領域的位交叉來模擬交叉操作，并以此來計算個體染色體上每一位基因的適應度函數值，并結合式(8)定義基因的適應度函數為：

(15)

在計算得到每一位基因的適應度函數值后，可以根據染色體上對應位置基因的適應度函數值大小對基因進行篩選，并選擇將適應度函數值較小的基因保留下來。

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

(16)

式中：hi表示染色體上第i位基因的適應度函數值。顯然，任務完成時間越長、能量消耗和額外開銷越高的任務，分配結果對應的基因更容易發生變異。

2.1.5種群更新操作

按照適應度函數值從大到小對種群中個體進行排序，并用前T個個體替代上一代種群中的對應個體，從而形成新的種群。

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

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

2.2.1算法初始化

將信息素的值賦給MC，并且信息素值的大小表示MC節點上可用資源的多少。根據前期遺傳算法輸出的最終結果可以解析出對應的任務分配方案，將該方案對應地轉化為MC節點的初始信息素值，根據影響任務執行的異構因素定義每個MC節點的初始信息素值為：

(17)

2.2.2轉移概率設計

轉移概率的大小是將下一個任務分配給系統中合適的MC節點的主要參考依據，這里同樣根據節點的異構性將節點的計算速度、剩余可用負載和剩余電池能量作為其性能優劣的主要判斷依據，因此在t時刻的轉移概率的設計主要取決于每個節點的計算速度、剩余可用負載、剩余電池能量和信息素值。則轉移概率可以表示為：

(18)

2.2.3信息素更新

當外出覓食的螞蟻從節點轉移時，節點上的信息素濃度就會相應地發生變化，因此需要及時更新信息素的值才能提高蟻群算法的收斂精度。這里根據求得的可行解對應的任務分配方案及任務的實際完成情況，對求得的所有路徑上的信息素值進行更新，則信息素值的更新依據可以定義為：

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

(19)

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

2.3 融合算法流程描述

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

算法1融合算法

輸入： 隨機產生的初始種群。

輸出： 全局最優的任務分配方案。

步驟1參數初始化。

步驟2初始化種群。

步驟3計算種群中個體的適應度值。

步驟4選擇適應度值高的個體作為父代染色體。

步驟5按概率進行遺傳操作。

步驟6判斷是否滿足約束條件，是則轉到下一步，否則將適應度值函數值較高的個體加入種群并返回步驟3。

步驟7將染色體種群中適應度函數值最高的個體作為最優解輸出并進行下一步。

步驟8根據步驟7的最優解輸出初始化蟻群。

步驟9根據轉移概率選擇下一節點。

步驟10更新信息素。

步驟11計算適應度值。

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

3 仿真對比分析

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

表1 MC的位置

表2 任務設置

任務完成時間是影響用戶體驗最重要的因素，圖2為GACA、RTA、HTA、GA在相同任務設置情況下的平均完成時間隨著節點數量不斷變化的關系曲線。

圖2 平均任務完成時間對比

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

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

圖3 平均任務執行能耗對比

RTA的性能依然較差并且不夠穩定，任務的平均完成能耗相比于其他算法依然存在較大差距；隨著節點數量的增加，HTA雖然也能降低能耗，但總體效果不明顯，這是因為盡管節點數量不斷增加，而HTA依然優先選擇執行速度快的節點，從而導致了較高的能耗；GACA與GA具有明顯的優勢，但平均任務執行能耗優化性能相差不大，甚至GA在節點數量較少時表現更好。這是由于GACA為了提升網絡整體性能，在適應度函數的設計上忽略了一定程度的能耗性能，但是隨著系統中MC節點設備數量的增加，蟻群算法所具備的精確求解能力對最優任務分配方案求解的影響逐漸增大，GACA的平均任務完成能耗呈現出明顯的下降趨勢。

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

圖4 平均任務完成時間對比

4 結 語

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