王志剛 趙傳信

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

0 引 言

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

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

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

1 問(wèn)題描述

1.1 霧計(jì)算模型

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

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

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

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

圖2 霧計(jì)算視頻分析平臺(tái)

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

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

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

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

(1)

n個(gè)霧節(jié)點(diǎn)表示為：

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

(2)

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

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é)點(diǎn)Fj上被分配的任務(wù)為：

(5)

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

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

(6)

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

(7)

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

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

(8)

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

(9)

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

(10)

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

(11)

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

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

func=Cost(FogsTasks)+PenaltyCost(Tasks)

(12)

2 算法設(shè)計(jì)

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

2.1 遺傳算法

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

2.2 蟻群算法

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

2.3 遺傳蟻群算法

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

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

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

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

圖5 遺傳算法單點(diǎn)變異

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

(13)

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

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

(14)

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

(15)

式中：ρmin是防止ρ過(guò)小降低算法收斂速度的最小值；Δτij表示每次迭代中霧節(jié)點(diǎn)i到霧節(jié)點(diǎn)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%用作蟻群算法信息素量的初始化，這里不同于其他文獻(xiàn)中直接轉(zhuǎn)換成信息數(shù)值，采用螞蟻進(jìn)行信息素量初始化，從低到高有目的地進(jìn)行選擇周游，這樣經(jīng)過(guò)螞蟻根據(jù)用于初始化的解結(jié)果執(zhí)行完周游后，初始化就完成了，這里的螞蟻數(shù)量需要根據(jù)用于初始化的解結(jié)果數(shù)量進(jìn)行合理取值。初始化完成后蟻群算法進(jìn)行探索的螞蟻數(shù)目應(yīng)該控制在10～50之間，最大進(jìn)化代數(shù)應(yīng)該控制在100～500之間，這樣的蟻群算法的性能相對(duì)比較均衡。圖6為遺傳蟻群算法流程。

圖6 遺傳蟻群算法流程

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)定

實(shí)驗(yàn)環(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；開(kāi)發(fā)工具Eclipse Java Oxygen(JDK1.8.0_144)、Visual Studio 2015(.NET Framework 4.5.2)；開(kāi)發(fā)語(yǔ)言Java、C#。

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

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

續(xù)表1

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

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

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

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

3.2 結(jié)果分析

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

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

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

圖9 花費(fèi)對(duì)比圖

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

圖10 時(shí)延對(duì)比圖

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

4 結(jié) 語(yǔ)

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