王志剛 趙傳信

(安徽師范大學(xué)計算機與信息學(xué)院 安徽 蕪湖 241000)

0 引 言

為了減輕云計算中心的壓力，霧計算作為云計算的擴展被提了出來，主要為了解決需要低延遲、移動支持、地理分布和基于位置信息的問題。霧計算利用位于云計算網(wǎng)絡(luò)邊緣的設(shè)備為就近的用戶提供服務(wù)，促進了云計算中心和用戶之間的任務(wù)處理，那些不適合云計算的應(yīng)用可以交給霧計算執(zhí)行，例如需要減少延遲的視頻會議、智能交通等。

霧計算作為一種分布式計算平臺，節(jié)點們通過相互協(xié)作的方式來執(zhí)行用戶提交的計算任務(wù)，這些節(jié)點將本地可以利用的資源整合在一起，利用近距離低延遲的優(yōu)勢為用戶提供實時處理服務(wù)。同時作為云計算的補充，霧計算還可以使用云計算中心強大的計算能力和存儲能力，并將云計算的計算服務(wù)擴展到網(wǎng)絡(luò)邊緣。相比于云計算中心的設(shè)備，靠近用戶的霧計算節(jié)點設(shè)備通常是資源受限的設(shè)備，如基站、接入點、路由器等。目前基于霧計算的研究還屬于發(fā)展階段，研究人員為了更好地使用霧計算服務(wù)引入了任務(wù)調(diào)度，任務(wù)調(diào)度的目的就是將霧節(jié)點執(zhí)行的經(jīng)濟高效的服務(wù)提供給請求服務(wù)的終端。

在霧計算的初步研究中，包括任務(wù)調(diào)度與分配、霧計算參考架構(gòu)、功耗時延優(yōu)化等，國內(nèi)外學(xué)者對任務(wù)調(diào)度的研究相對較少。文獻[1]提出云霧架構(gòu)下的任務(wù)請求分配模式。Gupta等[2]提出設(shè)計一個高效的任務(wù)調(diào)度和資源管理的重要性。Zeng等[3]研究了如何平衡工作負載以及如何放置任務(wù)；何秀麗等[4]提出多設(shè)備分布式計算方法；程冬梅等[5]提出智能前端化的霧計算參考框架；Sarkar等[6]證明了在物聯(lián)網(wǎng)應(yīng)用程序需要實時低延遲服務(wù)情況下，霧計算平均能耗比常規(guī)云計算低。Deng等[7]提出云霧計算系統(tǒng)分配工作負載時功耗和計算延遲權(quán)衡問題，通過現(xiàn)有技術(shù)分解后采用He等[8]提出的凸優(yōu)化技術(shù)來處理霧計算子系統(tǒng)優(yōu)化功耗和延遲，采用Li等[9]提出的非線性規(guī)劃問題來尋找功耗和計算延遲的折衷點，最后采用Kuhn[10]提出的匈牙利方法解決從霧節(jié)點到云服務(wù)器的數(shù)據(jù)傳輸延遲，但是該研究不適合霧計算基礎(chǔ)設(shè)備，負責(zé)工作的中心節(jié)點容易出現(xiàn)性能瓶頸。Song等[11]提出了一種基于任務(wù)分配的圖形劃分的霧計算負載均衡機制，但是其缺點是頻繁的圖形重新劃分來處理霧的變化，性能對于動態(tài)霧負載均衡不是最佳的。Cardellini等[12]評估了在霧計算環(huán)境中運行的數(shù)據(jù)流分析的分布式服務(wù)質(zhì)量感知調(diào)度程序，然而復(fù)雜的霧拓撲結(jié)構(gòu)可能導(dǎo)致一些不穩(wěn)定性，從而降低程序的可用性。Oueis等[13]討論了霧計算的負載均衡問題以提高用戶體驗質(zhì)量，但是不適用大規(guī)模霧計算基礎(chǔ)設(shè)施，會出現(xiàn)高復(fù)雜性。Intharawijitr等[14]提出了一種霧計算架構(gòu)，以幫助計算系統(tǒng)通過確保最佳任務(wù)調(diào)度來實現(xiàn)最大功率，結(jié)果發(fā)現(xiàn)使用一個特定策略可能不是整個系統(tǒng)的最佳解決方案。Bitam等[15]針對霧計算的調(diào)度問題，提出了新的生物啟發(fā)式優(yōu)化方法蜜蜂生活算法(BLA)，在可用霧節(jié)點中尋找最優(yōu)分配，實驗驗證了BLA在霧計算環(huán)境下解決任務(wù)調(diào)度問題的有效性。

1 問題描述

1.1 霧計算模型

本文研究的霧計算架構(gòu)是三層網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。頂層是云層，由遠端的云計算服務(wù)器組成，這些服務(wù)器有很強的計算和存儲能力；中間層是霧層，由靠近用戶的相對較弱的計算和存儲設(shè)備組成，這些設(shè)備大部分都是單片微型計算機、路由器、無線路由器、智能網(wǎng)關(guān)等霧節(jié)點設(shè)備，小部分是專門部署的霧計算服務(wù)器；底層是終端層，比通用的霧計算構(gòu)架多了感知執(zhí)行層，感知執(zhí)行層包括傳感器和執(zhí)行器，屬于終端層的一部分。很多文獻中的霧計算框架圖中都沒有傳感器和執(zhí)行器，這就讓人很容易忽略傳感器和執(zhí)行器，使人誤以為終端層只有移動用戶使用的手機、PC等設(shè)備，但是傳感器和執(zhí)行器才是霧計算不可缺少的一部分，例如：在智能交通的霧計算環(huán)境下，道路上的傳感器(攝像頭等)和執(zhí)行器(指示燈等)才是整個智能交通霧計算環(huán)境中參與度最高的設(shè)備。

圖1 霧計算架構(gòu)圖

1.2 任務(wù)調(diào)度問題

如圖2所示，霧計算環(huán)境下的視頻分析平臺是由N個霧節(jié)點和若干智能攝像頭組成。智能攝像頭收集到足夠多的視頻信息后便向就近的霧計算節(jié)點發(fā)出服務(wù)請求，提交視頻分析任務(wù)給霧計算節(jié)點，該節(jié)點接受任務(wù)之后傳遞給管理節(jié)點，管理節(jié)點匯總請求后進行任務(wù)調(diào)度分析。

圖2 霧計算視頻分析平臺

這里使用遺傳蟻群算法進行任務(wù)調(diào)度，由管理節(jié)點執(zhí)行，以找到最佳的順序調(diào)度霧節(jié)點執(zhí)行，調(diào)度模型如圖3所示。首先終端發(fā)送服務(wù)請求并提交任務(wù)(①)；接著霧節(jié)點們傳遞任務(wù)到管理節(jié)點(②)；然后管理節(jié)點執(zhí)行調(diào)度算法，分配任務(wù)給節(jié)點們(③)；最后匯總結(jié)果響應(yīng)給終端(④)。

圖3 霧計算任務(wù)調(diào)度模型

m個終端提交任務(wù)表示為：

Tasks={T1,T2,…,Ti,…,Tm} 1≤i≤m

(1)

n個霧節(jié)點表示為：

Fogs={F1,F2,…,Fj,…,Fn} 1≤j≤n

(2)

為了方便霧計算節(jié)點執(zhí)行任務(wù)Ti，將任務(wù)Ti進行分塊，分塊數(shù)為l時表示為：

Ti={TBi1,TBi2,…,TBik,…,TBil} 1≤k≤l

(3)

Ti={TBi1,TBi2,…,TBik,…,TBil} 1≤k≤l

(4)

式中：1≤x1,x2,…,xk,…,xl≤n。

霧節(jié)點Fj上被分配的任務(wù)為：

(5)

式中：1≤y1,y2,…,yq,yp≤m；1≤z1,z2,…,zq,…,zp≤l。

霧節(jié)點Fj的CPU執(zhí)行時間定義為：

(6)

霧節(jié)點Fj的內(nèi)存消耗定義為：

(7)

任務(wù)調(diào)度的首要目的就是盡可能滿足終端的請求，參考基于服務(wù)水平協(xié)議(SLA)的云計算調(diào)度，可以定義霧計算的違規(guī)花費為：

Penalty(Ti)=basePenalty(Ti)+β(Ti)×delayTime(Ti)

(8)

式中：Ti因為服務(wù)超時而發(fā)生違規(guī)；basePenalty(Ti)表示Ti的基本違規(guī)花費；β(Ti)表示單位時間違規(guī)花費;delayTime(Ti)表示延遲時間。定義違規(guī)任務(wù)集合為VTasks，因此目標(biāo)的違規(guī)花費定義為：

(9)

其次，最小化所有霧節(jié)點的CPU執(zhí)行時間和消耗內(nèi)存也就是霧計算的花費，定義為：

(10)

CostFunc(FjTasks)=w1Exec(FjTasks)+w2Mem(FjTasks)

(11)

式中：w1和w2是權(quán)重因子，用于強調(diào)CPU執(zhí)行時間和內(nèi)存消耗兩個評估目標(biāo)的重要性。

綜上所述，霧計算任務(wù)調(diào)度的目標(biāo)函數(shù)為：

func=Cost(FogsTasks)+PenaltyCost(Tasks)

(12)

2 算法設(shè)計

針對霧計算的任務(wù)調(diào)度研究仍是一個比較重要的問題?，F(xiàn)有的調(diào)度算法都是單獨使用遺傳算法或者蟻群算法，無法獲取較好的結(jié)果。通過對遺傳算法與蟻群算法的研究與實驗發(fā)現(xiàn)，遺傳算法在搜索的初期尋找最優(yōu)解的速度比較快，但是在一段時間后速度明顯下降。而蟻群算法在初期搜索最優(yōu)解的速度特別緩慢，當(dāng)搜索產(chǎn)生的信息素濃度變高時尋找最優(yōu)解的速度迅速提高。因此本文提出一種針對霧計算任務(wù)調(diào)度的遺傳蟻群算法，在遺傳算法性能出現(xiàn)下降的時間點生成蟻群所需要的信息素，并隨后使用蟻群算法求最優(yōu)解。

2.1 遺傳算法

傳統(tǒng)的遺傳算法用于解決窮舉耗費時間過長的解空間比較龐大的問題。遺傳算法的思想就是要模擬自然選擇，因此遺傳算法必須同時滿足遺傳、突變、選擇這三個要素。遺傳算法有并行、高效、全局搜索的優(yōu)點，但是也存在局部搜索能力差和過早陷于最優(yōu)的缺點。

2.2 蟻群算法

蟻群算法通過模擬自然界螞蟻尋找食物過程的優(yōu)化算法，與真實螞蟻通過信息素的留存、跟隨行為進行間接通信相似，蟻群算法中一群簡單的人工螞蟻利用代碼中的信息素數(shù)據(jù)進行間接通信，不斷利用該信息來構(gòu)建問題的解。蟻群算法優(yōu)點包括并行、自組織、正反饋、易與別的優(yōu)化算法結(jié)合，但是也存在前期需要較長的搜索時間和容易出現(xiàn)停止現(xiàn)象的不足。

2.3 遺傳蟻群算法

遺傳算法和蟻群算法的相互融合是指前期使用遺傳算法先進行搜索并在合適的時候停止，可以避免蟻群算法前期比較耗時的搜索過程，再使用蟻群算法，把遺傳算法得到的解作為蟻群算法的初始值，利用蟻群算法的正反饋更好地找到問題的解。

遺傳算法編碼有很多種，本文采用直接編碼，假設(shè)有n個霧節(jié)點和m個任務(wù)，任務(wù)分塊后為w個，則染色體的長度為w，假設(shè)m=5、w=10、n=5，單個染色體解釋如下：

“5324415243”：任務(wù)塊1、7分配給霧節(jié)點5；任務(wù)塊2、10分配給霧節(jié)點3；任務(wù)塊3、8分配給霧節(jié)點2；任務(wù)塊4、5、9分配給霧節(jié)點4；任務(wù)塊6分配給霧節(jié)點1。

遺傳算法群體規(guī)模一般選擇為10～200之間，這樣既不會導(dǎo)致計算復(fù)雜度較高又不會很快陷入局部最優(yōu)。遺傳算法的適應(yīng)度函數(shù)的選擇可以直接使用霧計算調(diào)度的目標(biāo)函數(shù)。遺傳算法的交叉操作采用兩點交叉，如圖4所示，交叉的概率控制在0.25～1.00之間，避免遲鈍的同時也可增加搜索能力。遺傳突變操作采用單點突變，如圖5所示，變異的概率控制在0.001～0.1之間，防止重要基因丟失和避免趨向純粹的隨機搜索。遺傳算法的終止進化代數(shù)是運行結(jié)束的參數(shù)，可以通過判斷子代進化率來確定，當(dāng)進化率低于1%的時候，結(jié)束遺傳算法進入蟻群算法。

圖5 遺傳算法單點變異

蟻群算法中螞蟻找到的路徑就是任務(wù)調(diào)度的一個解，因此螞蟻每次需要選擇的就是霧節(jié)點。螞蟻每次從原點出發(fā)，第一次選擇的霧節(jié)點就是給第一個任務(wù)分塊選擇的，以此類推。當(dāng)所有的任務(wù)分塊都有對應(yīng)的霧節(jié)點時，螞蟻完成使命回到原點。螞蟻會根據(jù)路徑上的信息素量和啟發(fā)式信息獨立選擇下一個霧節(jié)點，在t時刻螞蟻a從一個霧節(jié)點i轉(zhuǎn)移到另一個霧節(jié)點j的概率為：

(13)

式中：Jk(i)={1,2,…,j,…,n}表示下一步可以取的霧節(jié)點編號集合。禁忌數(shù)tabuNumber記錄了螞蟻a選擇霧節(jié)點的數(shù)目。當(dāng)tabuNumber達到任務(wù)分塊總數(shù)時就代表所有任務(wù)分塊都分配完畢，螞蟻a便完成一次周游，此時螞蟻a選擇的霧節(jié)點序列就是霧計算任務(wù)調(diào)度的一個可行解。ηij是啟發(fā)式因子，表示螞蟻從霧節(jié)點i選擇下一個到霧節(jié)點j的期望程度，在任務(wù)調(diào)度問題中取選擇后需要的花費。α和β分別表示信息素量和期望啟發(fā)式因子的相對重要程度，一般α取1～4之間，β取3～5之間，為了避免過早停滯和陷入局部最優(yōu)，必須在兩者選取一個平衡點。當(dāng)所有的螞蟻完成一次周游后，需要更新各個路徑上的信息素量，公式如下：

τij(t+n)=(1-ρ)τij(t)+Δτij

(14)

式中：ρ(0<ρ<1)表示路徑上信息素量的蒸發(fā)系數(shù)，則1-ρ表示信息素的保留系數(shù)。為了避免固定不變的更新信息量采用自適應(yīng)改變ρ的值，即:

(15)

式中：ρmin是防止ρ過小降低算法收斂速度的最小值；Δτij表示每次迭代中霧節(jié)點i到霧節(jié)點j路徑上的信息素量的增量，先采用最大最小螞蟻系統(tǒng)控制信息素量的范圍在[τmin,τmax]內(nèi)，采用精英螞蟻系統(tǒng)和基于排序的蟻群算法，精英螞蟻也就是解的目標(biāo)函數(shù)最小的螞蟻釋放最多的信息素，在每次循環(huán)中，排名前x名的螞蟻和精英螞蟻才允許釋放信息素，精英螞蟻起到最大的作用需要和系數(shù)x+1相乘，排名第y名的螞蟻乘以系數(shù)x-y-1，即：

(16)

(17)

取遺傳算法得到的解結(jié)果的10%用作蟻群算法信息素量的初始化，這里不同于其他文獻中直接轉(zhuǎn)換成信息數(shù)值，采用螞蟻進行信息素量初始化，從低到高有目的地進行選擇周游，這樣經(jīng)過螞蟻根據(jù)用于初始化的解結(jié)果執(zhí)行完周游后，初始化就完成了，這里的螞蟻數(shù)量需要根據(jù)用于初始化的解結(jié)果數(shù)量進行合理取值。初始化完成后蟻群算法進行探索的螞蟻數(shù)目應(yīng)該控制在10～50之間，最大進化代數(shù)應(yīng)該控制在100～500之間，這樣的蟻群算法的性能相對比較均衡。圖6為遺傳蟻群算法流程。

圖6 遺傳蟻群算法流程

3 仿真實驗

3.1 實驗設(shè)定

實驗環(huán)境設(shè)置：仿真軟件iFogSim；處理器AMD Athlon(tm) X4 860K Quad Core Processor 3.9 GHz；內(nèi)存16.0 GB；操作系統(tǒng)Windows 7 旗艦版 64位 SP1；開發(fā)工具Eclipse Java Oxygen(JDK1.8.0_144)、Visual Studio 2015(.NET Framework 4.5.2)；開發(fā)語言Java、C#。

霧節(jié)點的參數(shù)設(shè)置如表1所示，任務(wù)參數(shù)設(shè)置如表2所示，算法的參數(shù)設(shè)置如表3所示，計算資源參數(shù)如表4所示，額外需要的算法參數(shù)如表5所示。

表1 霧節(jié)點的參數(shù)設(shè)置

續(xù)表1

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

表3 算法參數(shù)設(shè)置

表4 計算資源參數(shù)

表5 算法參數(shù)列表

3.2 結(jié)果分析

為了證明遺傳蟻群算法相比較于傳統(tǒng)的遺傳算法和蟻群算法在任務(wù)調(diào)度上更有效，在C#中實現(xiàn)遺傳算法、蟻群算法、遺傳蟻群算法并進行任務(wù)調(diào)度比較。算法中霧計算節(jié)點的設(shè)置依據(jù)表1，任務(wù)分塊大小設(shè)置依據(jù)表2，算法的參數(shù)依據(jù)表3。圖7為遺傳蟻群算法、遺傳算法、粒子群算法的CPU執(zhí)行時間結(jié)果；圖8為消耗內(nèi)存結(jié)果；圖9為霧計算花費結(jié)果。可以看出，遺傳蟻群算法與遺傳算法、粒子群算法相比，能得到最佳的效果。

圖7 執(zhí)行時間對比圖

圖8 消耗內(nèi)存對比圖

圖9 花費對比圖

驗證過遺傳蟻群算法的有效性后，就可以進行遺傳蟻群算法在仿真平臺上的實驗。iFogsim仿真平臺是Cloudsim團隊編寫的霧計算仿真平臺，在iFogsim上的仿真實驗主要針對云霧協(xié)作的霧計算，終端產(chǎn)生的任務(wù)由隨機程序模擬產(chǎn)生，請求數(shù)量分別設(shè)置為100、300、500、700、900；請求的任務(wù)大小為500～15 000 MI之間；資源參數(shù)依據(jù)表4；懲罰使用的參數(shù)依據(jù)表5。從圖10和圖11所示的時延與SLO違規(guī)率對比可知，與霧-遺傳算法相比，霧-遺傳蟻群算法不僅在時延上有優(yōu)勢而且違規(guī)率更低。這是因為霧-遺傳蟻群算法融合了遺傳算法和蟻群算法的優(yōu)點，在問題解空間里能夠更快更好地找到分配結(jié)果。與云霧-遺傳蟻群算法相比，由于霧-遺傳蟻群算法將部分任務(wù)分配到可行的霧節(jié)點上，有效縮短響應(yīng)時間，所以降低了SLO違規(guī)率。

圖10 時延對比圖

圖11 SLO違規(guī)率對比圖

4 結(jié) 語

本文研究了應(yīng)用在霧計算任務(wù)調(diào)度上的遺傳蟻群算法，使用CPU執(zhí)行時間、內(nèi)存消耗、時延和SLO違規(guī)率進行算法的評估。實驗結(jié)果表明，遺傳蟻群算法在以上四個方面都具有比較好的優(yōu)勢。未來研究可以考慮加入動態(tài)任務(wù)調(diào)度，這樣基于遺傳蟻群算法的霧計算任務(wù)調(diào)度才能更好地為終端服務(wù)。