簡琤峰,陳家煒,張美玉

(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院數(shù)字媒體技術(shù)研究所,杭州 310023)

1 引 言

邊緣計(jì)算作為一種新興的計(jì)算模型,可以將具有有限計(jì)算資源和能量的物聯(lián)網(wǎng)(IoT)設(shè)備的延遲敏感計(jì)算任務(wù)卸載到邊緣云[1].在云環(huán)境下為多功能需求任務(wù)選取服務(wù)組合問題本質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問題[2,3],云計(jì)算系統(tǒng)中,由于計(jì)算資源的復(fù)雜性和不確定性[4],在資源管理與調(diào)度方面,邊緣計(jì)算中的資源優(yōu)化調(diào)度是核心問題之一,只有實(shí)現(xiàn)了資源的科學(xué)管理、合理調(diào)度與分配,才能面向?qū)嶋H需求,充分發(fā)揮出云、邊緣服務(wù)器、終端的節(jié)點(diǎn)優(yōu)勢,實(shí)現(xiàn)利用率、能耗、帶寬、存儲(chǔ)等全方面優(yōu)化[5],終端可以使用面向服務(wù)的方式調(diào)用云服務(wù)來異步完成資源密集,用于集中處理的任務(wù).在本文中,我們研究了任務(wù)調(diào)度問題,以降低邊緣計(jì)算系統(tǒng)的成本,我們將任務(wù)調(diào)度模型建模為優(yōu)化問題,其目標(biāo)在滿足所有任務(wù)的延遲要求的同時(shí)最小化運(yùn)行時(shí)間.

此外,硬件的日益增加已經(jīng)允許這些微小設(shè)備執(zhí)行的不僅僅是感測,例如將自己表示為服務(wù)(即設(shè)備作為服務(wù)).這樣的演變中云在整個(gè)基礎(chǔ)設(shè)施中起著核心作用,用于數(shù)據(jù)處理,存儲(chǔ)和分析[6].但是,云計(jì)算模式面臨著提供低延遲,高可用性和實(shí)時(shí)位置感知服務(wù)的挑戰(zhàn)[7],而邊緣計(jì)算在網(wǎng)絡(luò)邊緣處理大量臨時(shí)數(shù)據(jù)，不再全部上傳云端，這極大地減輕了網(wǎng)絡(luò)帶寬和數(shù)據(jù)中心功耗的壓力[8].

集中式基礎(chǔ)架構(gòu)系統(tǒng)從我們當(dāng)前高度虛擬化的無線網(wǎng)絡(luò)平臺(tái)和物聯(lián)網(wǎng)(IoT)應(yīng)用程序中執(zhí)行現(xiàn)有的數(shù)據(jù)分析和決策流程.這些現(xiàn)有方法很可能會(huì)遇到與網(wǎng)絡(luò)動(dòng)態(tài)相關(guān)的更多挑戰(zhàn)和問題,導(dǎo)致網(wǎng)絡(luò)響應(yīng)時(shí)間的高開銷,從而導(dǎo)致延遲和流量[9].Hesham等人為了避免網(wǎng)絡(luò)中的這些問題并實(shí)現(xiàn)最佳資源利用水平,提出了一種稱為邊緣計(jì)算(EC)的新范例,文中提到了提供升級(jí)和高效的服務(wù),基于物聯(lián)網(wǎng)應(yīng)用的需求,需要結(jié)合適當(dāng)?shù)挠?jì)算技術(shù).

本文提出一種面向邊緣計(jì)算的改進(jìn)混沌蝙蝠群協(xié)同調(diào)度算法來進(jìn)行邊緣計(jì)算資源調(diào)度問題的優(yōu)化,能夠快速搜索到較優(yōu)的調(diào)度解,減少任務(wù)完成時(shí)間(使用計(jì)算任務(wù)的平均完成時(shí)間來衡量云性能,完成時(shí)間越短,邊緣云在單位時(shí)間內(nèi)可以承擔(dān)大量工作量,表明邊緣云提供了更強(qiáng)大的計(jì)算能力).

2 相關(guān)工作

在云調(diào)度問題中,已有的策略有如下幾種:

隨機(jī)選擇(RS)和輪詢(RR)云調(diào)度將作業(yè)分配給虛擬機(jī)而不考慮虛擬機(jī)的當(dāng)前負(fù)載[10-12].與其他調(diào)度算法相比,具有較小的調(diào)度開銷,思路簡單.但是其可能導(dǎo)致負(fù)載不均衡、資源利用率低、提交作業(yè)等待時(shí)間較長;RR即便每個(gè)虛擬機(jī)被分配到的任務(wù)數(shù)量相等,但是任務(wù)長度的不均同樣會(huì)導(dǎo)致上述RS的問題.

此外,傳統(tǒng)進(jìn)化算法應(yīng)用于調(diào)度問題有很好的效果[13],比如:

粒子群算法(PSO),包括帶有自適應(yīng)學(xué)習(xí)因子的粒子群(TDDALFPSO),量子粒子群(QPSO)等變體的粒子群算法的生物啟發(fā)技術(shù)和群體智能能用于復(fù)雜問題的解決,以精度高、收斂快等優(yōu)點(diǎn)獲得了在云調(diào)度方面的廣泛運(yùn)用[14,15],此外粒子群算法還有其他很多變種,PSO具有快速收斂的優(yōu)點(diǎn),但是同時(shí)也存在容易陷入局部最優(yōu)的問題.從基本概念入手,針對(duì)粒子群算法易陷入局部最優(yōu)、收斂速度慢的缺陷,在算法中加入改進(jìn)的慣性權(quán)重、學(xué)習(xí)因子和外部擾動(dòng)因子等是一些常采用的方法.盡管PSO已廣泛應(yīng)用于科學(xué)和工程領(lǐng)域,但其穩(wěn)健性,即其處理具有不同特征的問題的能力仍然不令人滿意,因此,需要有更好的搜索能力和魯棒性的改進(jìn)PSO以有效地解決該問題[16],在這基礎(chǔ)上[17]提出了量子粒子群(QPSO),在QPSO中,粒子行為遵循量子力學(xué)原理而不是PSO中強(qiáng)加的牛頓力學(xué),QPSO使用了量子粒子代替牛頓粒子進(jìn)行隨機(jī)游走,在本地和全局搜索之間實(shí)現(xiàn)良好平衡,其中量子粒子群中的收縮擴(kuò)張系數(shù)是唯一控制參數(shù),用于調(diào)整算法,本文內(nèi)使用的QPSO算法使用了[18]取的參數(shù)值.

蝙蝠群算法(BA)和改進(jìn)的蝙蝠群算法(NBA)則在群組智能算法的基礎(chǔ)上進(jìn)行了改進(jìn),從生物學(xué)的角度改進(jìn)算法,模擬蝙蝠的行為,通過模擬蝙蝠的回聲,通過設(shè)定響度和發(fā)聲頻率屬性模擬蝙蝠行為,同時(shí)NBA中更是加入了棲息地選擇和多普勒效應(yīng)均衡器的自適應(yīng)補(bǔ)償納入了基本BA算法,提高了效率和穩(wěn)定性,并提出了自適應(yīng)局部搜索策略[19].文章[19]中,專注于進(jìn)一步模仿蝙蝠的行為,并基于生物基礎(chǔ)改善BA,設(shè)計(jì)了新的局部搜索策略,基于二十個(gè)基準(zhǔn)問題和四個(gè)實(shí)際工程設(shè)計(jì)的模擬和比較證明NBA的有效性,效率和穩(wěn)定性,清楚的表明了NBA對(duì)基本BA和一些眾所周知的算法的優(yōu)越性.在該算法中,個(gè)體模擬能夠自適應(yīng)地補(bǔ)償回波中多普勒效應(yīng)的蝙蝠.根據(jù)特定個(gè)體與全局最佳個(gè)體之間的相對(duì)距離,頻率方程是自適應(yīng)的.對(duì)于本地搜索,位置更新公式是自適應(yīng)的,沒有任何用戶定義的參數(shù).其次,該算法具有良好的分集和收斂性能.結(jié)合了蝙蝠的棲息地選擇,該算法中的個(gè)體可以使用兩種不同的搜索策略進(jìn)化,從而增加個(gè)體的多樣性.

混沌具有以下特征:對(duì)初始條件的敏感依賴性;存在眾多不穩(wěn)定的周期點(diǎn);準(zhǔn)隨機(jī)性;普遍性等.這些屬性使得混沌搜索算法成為有效的優(yōu)化方法[20].混沌研究的是非線性動(dòng)力系統(tǒng)的固有特性,是非線性系統(tǒng)普遍存在的現(xiàn)象,線性系統(tǒng)是非線性系統(tǒng)簡化而來的,其行為表現(xiàn)為不定性——不可重復(fù)、不可預(yù)測,這就是混沌現(xiàn)象,應(yīng)用于群組算法優(yōu)化中,可以避免出現(xiàn)兩次相同的調(diào)度情況,相比于其余的去局部最優(yōu)的方法有更好的效果.

本文提出了一種改進(jìn)混沌蝙蝠群算法(TDDCBA),加入了混沌因子和二維擾動(dòng)因子,相比較上述算法有更強(qiáng)的尋優(yōu)能力.

同時(shí),關(guān)于云中心管理和邊緣協(xié)同管理調(diào)度問題[21]由于對(duì)提高非通用設(shè)備的利用率以及降低成本來實(shí)現(xiàn)計(jì)算目標(biāo)的高度興趣,提出了一種用于在邊緣異構(gòu)云邊環(huán)境中調(diào)度微服務(wù)的新模型,通過CloudSim仿真框架進(jìn)行系統(tǒng)實(shí)驗(yàn),實(shí)驗(yàn)發(fā)現(xiàn)在其使用面向微服務(wù)的方法時(shí),一些非常簡單的調(diào)度算法可能在云邊緣環(huán)境中經(jīng)常出現(xiàn)的特定情況下優(yōu)于其他一些調(diào)度算法.其架構(gòu)定義了云部署管理器,可確保部署在給定資源上執(zhí)行任務(wù),這個(gè)模塊還處理云代理和作業(yè)執(zhí)行單元之間的通信,其模擬架構(gòu)為每臺(tái)虛擬機(jī)代表某組微服務(wù)的能力,這些虛擬機(jī)由云管理器管理,被自動(dòng)擴(kuò)展模塊的請(qǐng)求部署或銷毀.

3 提出的調(diào)度算法

3.1 調(diào)度模型建立

為了達(dá)到滿足用戶QoE的前提下最好地將任務(wù)分配給邊緣節(jié)點(diǎn)的目標(biāo),本文使用的邊緣計(jì)算資源協(xié)同調(diào)度模型,大體可以描述如圖1所示.

圖1 邊緣計(jì)算資源協(xié)同調(diào)度模型(三層)Fig.1 Edge computing resource collaborative scheduling model(three tier)

在將提交的任務(wù)進(jìn)行分割后,提交到邊緣設(shè)備,通過調(diào)度算法將分割后的任務(wù)通過邊緣計(jì)算代理(ECA)調(diào)度放到邊緣服務(wù)器上,服務(wù)器上的虛擬機(jī)代表用戶進(jìn)行處理卸載任務(wù)的工作.同時(shí),中心云可以進(jìn)行邊緣服務(wù)器之間的調(diào)度,將超出邊緣服務(wù)器的資源的任務(wù)調(diào)度給其他邊緣服務(wù)器進(jìn)行處理,對(duì)于超出虛擬機(jī)間帶寬量的任務(wù)通過提交到云端來進(jìn)行調(diào)度提速,從而達(dá)到云計(jì)算與邊緣計(jì)算協(xié)同調(diào)度的效果.

計(jì)算卸載是一種技術(shù),其中資源受限移動(dòng)設(shè)備完全或部分地將計(jì)算密集型任務(wù)卸載到資源充足的云環(huán)境.計(jì)算卸載主要執(zhí)行能量,電池壽命或由于終端設(shè)備無法處理計(jì)算量大的應(yīng)用程序[22].

層次結(jié)構(gòu)的第一層服務(wù)器通過無線鏈路直接從邊緣設(shè)備接收工作任務(wù)進(jìn)行調(diào)度.而邊緣服務(wù)器收到的設(shè)備工作任務(wù)負(fù)載超過其計(jì)算容量那么過多的工作負(fù)載將進(jìn)一步卸載到更高層的服務(wù)器,通過這種方式來提供服務(wù)大量的峰值負(fù)載[23].同時(shí)[1]文內(nèi)已經(jīng)證明在該調(diào)度模型可以被證明為一個(gè)無法在多項(xiàng)式時(shí)間內(nèi)解決的NP難問題,而本文也將面向邊緣計(jì)算的協(xié)同調(diào)度問題簡化成了:在邊緣服務(wù)資源有限的情況下,確定調(diào)度邊緣服務(wù)執(zhí)行請(qǐng)求的分配,從而讓服務(wù)請(qǐng)求整體時(shí)間最少,提出一種調(diào)度優(yōu)化算法優(yōu)化調(diào)度過程獲得最優(yōu)解決方案.

在[1]文內(nèi)第一階段處理后,我們得到了初步的任務(wù)調(diào)度策略,但是在一些特殊情況下,可以進(jìn)一步降低初步調(diào)度策略的系統(tǒng)成本,舉例說明:考慮有兩個(gè)任務(wù)T1,T2和兩個(gè)邊緣服務(wù)器S1,S2,資源需求矢量分別為(10,10,10)和(20,20,20),邊緣服務(wù)器的可用資源向量分別是(15,15,15)和(50,50,50),根據(jù)第一階段的調(diào)度,任務(wù)T1將會(huì)被調(diào)度到服務(wù)器S1,任務(wù)T2分配到S2,這種情況下,總成本是兩個(gè)成本的總和,但是如果所有任務(wù)都放到S2服務(wù)器上進(jìn)行,則總成本僅為服務(wù)器S2的成本.因此,在第一個(gè)階段后,我們需要進(jìn)一步優(yōu)化調(diào)度策略以減少不必要的成本和運(yùn)行時(shí)間,因此本實(shí)驗(yàn)將負(fù)載均衡也作為評(píng)判指標(biāo)之一.

邊緣計(jì)算調(diào)度問題可以簡化為將m個(gè)任務(wù)分配到n個(gè)服務(wù)器上進(jìn)行運(yùn)算的問題,其中任務(wù)劃分后的子任務(wù)長度描述為:T={t1,t2,t3,…,tm},其中ti表示第i個(gè)子任務(wù)總長度.同時(shí)假設(shè)有n個(gè)不均勻的邊緣服務(wù)器(計(jì)算能力不同),邊緣服務(wù)器上的虛擬機(jī)可以描述為:VM={vm1,vm2,vm3,…,vmn},其中vmj表示 第j個(gè)服務(wù)器(虛擬機(jī))的計(jì)算能力.

VM間帶寬描述為矩陣

(1)

其中vcij代表vmi和vmj之間的通信帶寬,當(dāng)i=j時(shí)vcij為0.

定義第p種調(diào)度方案的負(fù)載均衡度評(píng)價(jià)函數(shù)LBp為:

(2)

其中

(3)

Pij代表第i個(gè)任務(wù)是否分配給第j個(gè)服務(wù)器(虛擬機(jī)),如果分配就是1,否則為0.

具有以下約束:

(4)

定義第p種調(diào)度方案的運(yùn)行時(shí)間評(píng)價(jià)函數(shù)RTp為:

(5)

由于每個(gè)服務(wù)器上的資源是優(yōu)先的,調(diào)度約束條件需要滿足(每個(gè)服務(wù)器中需要有重組的內(nèi)存空間來存儲(chǔ)處理的任務(wù),否則就會(huì)丟失任務(wù)數(shù)據(jù),任務(wù)帶寬和也不能超過服務(wù)器總帶寬):

(6)

(7)

其中,si為第i個(gè)任務(wù)的內(nèi)存需求,bij為任務(wù)i分配給服務(wù)器j的帶寬需求,Sj為服務(wù)器j的可用內(nèi)存,Bj為服務(wù)器j和ECA之間的通信帶寬.

3.2 云調(diào)度的蝙蝠群算法

蝙蝠群算法的思想來自于蝙蝠的回聲定位,應(yīng)用于調(diào)度方面的該算法的具體步驟如下:

Step 1.初始化信息,一個(gè)蝙蝠代表一個(gè)解決方案,一個(gè)蝙蝠具有位置信息xij和速度信息vij,其中i代表種群數(shù)量,j代表第j個(gè)任務(wù).xij的值為小于服務(wù)器虛擬機(jī)編號(hào)(所有服務(wù)器的數(shù)量)的整數(shù).位置更新公式如下:

xij=xmin+(xmax-xmin)×λ

(8)

其中xmax和xmin代表虛擬機(jī)編號(hào)的最大最小值,λ為0到1之間的均勻分布的隨機(jī)數(shù).

Step 2.生成新的解決方案,公式如下:

fi=fmin+(fmax-fmin)×β

(9)

(10)

(11)

其中β為0到1之間的服從均勻分布的隨機(jī)數(shù).fmin和fmax分別為頻率的最大和最小,t代表迭代次數(shù),gbest代表全局最優(yōu)調(diào)度方案.

(12)

其中rand(-1,1)為-1到1之間的服從均勻分布的隨機(jī)數(shù),Ameant則是第t次迭代的平均響度.

Step 3.隨機(jī)更新響度和脈沖發(fā)射率,生成一個(gè)服從均勻分布的隨機(jī)數(shù),若其小于響度Ai,且按照(9)生成的新的頻率fnew小于之前的頻率fi,則進(jìn)行下列更新:

fi=fnew

(13)

(14)

(15)

其中α和γ在本文實(shí)驗(yàn)中均按照文獻(xiàn)[8]取0.9.

Step 4.更新全局最優(yōu)解gbest

3.3 二維擾動(dòng)

BA的位置更新公式和PSO一致,為了進(jìn)行波動(dòng)調(diào)整,避免減小陷入局部最優(yōu)的問題,對(duì)于(11)進(jìn)行改進(jìn),加入二維擾動(dòng).同時(shí)為了避免振蕩幅度過大導(dǎo)致偏離原來的位置,將振幅限制在20%之內(nèi),加入二維擾動(dòng)后的位置更新公式如下:

(16)

其中ω和σ均為-1到1之間的服從均勻分布的隨機(jī)數(shù).

3.4 混沌理論

混沌變量在種群運(yùn)動(dòng)過程中起到控制粒子混沌程度的作用[24],本文擬通過混沌因子將系統(tǒng)從有序變?yōu)闊o序,從而更好地達(dá)到全局個(gè)體隨機(jī)出現(xiàn)效果.初始化混沌變量為:

(17)

其中rid為0到1之間服從均勻分布的常數(shù).

(18)

(19)

其中ψ和Mi分別表示為:搜索測度和搜索空間向負(fù)方向移動(dòng)的比例,在本文的模型中兩者的值分別為服務(wù)器數(shù)量n和0.

3.5 改進(jìn)混沌蝙蝠群算法描述

本文的算法在BA算法的基礎(chǔ)上加入了二維擾動(dòng)因子和混沌因子,對(duì)于跳出局部最優(yōu)和全局搜索能力進(jìn)行了優(yōu)化,具體步驟如下:

1)初始化參數(shù):設(shè)置種群(速度初始化為0,位置全局隨機(jī)初始化為小于虛擬機(jī)數(shù)量的正整數(shù)),迭代次數(shù),設(shè)置任務(wù)長度和虛擬機(jī)的計(jì)算能力和混沌變量的各項(xiàng)參數(shù),在本文的模型中搜索測度和搜索空間向負(fù)方向移動(dòng)的比例分別取n和0.

2)根據(jù)初始化參數(shù)進(jìn)行中間參數(shù)初始化:全局最優(yōu)值gbest,即為初始化種群中適應(yīng)度函數(shù)最小的值,響度A為[0,2]服從均勻分布的隨機(jī)數(shù),平均響度Amean的初始化,脈沖發(fā)射率ri和混沌因子中間變量rid均初始化為[0,1]服從均勻分布的隨機(jī)數(shù),初始化混沌變量C.

3)當(dāng)前迭代次數(shù)iter小于規(guī)定的最大迭代次數(shù)gmax時(shí)循環(huán)執(zhí)行Step 4和Step 5,循環(huán)結(jié)束后的gmax即為最終獲得的值.

使用Secp256k1生成256位公鑰/密鑰，然后編譯成64位長度的十六進(jìn)制字符串；采用公鑰的Keccak-256哈希算法，得到一個(gè)32字節(jié)的字十六進(jìn)制字符串，接下來對(duì)該字符串進(jìn)行取截，取字符串的最后20個(gè)字節(jié)（即刪除前12個(gè)字節(jié)），得到了40個(gè)字節(jié)的字符串，在簽名加上0x前綴，就可以得到一個(gè)42個(gè)字節(jié)長的地址，該地址就是以太坊用戶全網(wǎng)唯一的賬號(hào)。

4)根據(jù)公式(17)更新混沌變量C,公式(9)和公式(13)更新fi,公式(10)更新速度v,根據(jù)公式(12)、(16)、(17)、(18)、(19)更新蝙蝠所在位置,同時(shí)進(jìn)行邊界判斷(速度值不超過n,位置值也不超過n,超過部分按照邊界值取),這里速度值和位置值保留小數(shù)值不進(jìn)行取整,但是進(jìn)行適應(yīng)度函數(shù)取值的時(shí)候進(jìn)行四舍五入取整后計(jì)算適應(yīng)度值,同時(shí)迭代次數(shù)iter加一.

5)根據(jù)公式(14)和公式(15)更新全局最優(yōu)值,更新響度A,平均響度Amean和頻率r.

算法中的各項(xiàng)參數(shù)設(shè)置見表1.

表1 算法中各項(xiàng)參數(shù)的值
Table 1 Value(v)of each parameter(p)in the algorithm

pvα0.9γ0.9fmin0fmax2A[0,2]r[0,1]pvω[-1,1]σ[-1,1]ψnMi0λ[0,1]β[0,1]pvri[0,1]

算法偽代碼如下:

Input:gmax:the number of iteration

pop:random scheduling schemes(a swarm of bats)

cloudletlist:set of tasks to be scheduled

variables of TDDCBA

Initialize gbest

Initialize A Amean r riC

While(iter

update C(17)

update fi(9)

update v(8)

update position(12 16 17 18 19)

judge the border

update gbest

update A,Amean,r(14 15)

iter++

end while

find best in pop

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

4.1 算法性能對(duì)比

為了驗(yàn)證本文提出的改進(jìn)混沌蝙蝠群協(xié)同算法在邊緣計(jì)算資源協(xié)同調(diào)度模型中的有效性,本文挑選出效果較好的幾種算法與本文算法進(jìn)行比較,并使用CloudSim仿真平臺(tái)[25]進(jìn)行實(shí)驗(yàn).通過比較不同的調(diào)度算法調(diào)度結(jié)果的執(zhí)行時(shí)間和負(fù)載均衡度來比較算法的效果.

表2 算法對(duì)比情況
Table 2 Algorithm comparison

TDDCBABAnmTQTQ301014.509.3425.7712.9501022.4422.0942.0222.541001041.6165.7654.5565.4530010131.13365.16161.15364.8050010223.83793.20253.07793.01100010469.852260.24530.392259.62302010.093.2220.324.38502015.676.9833.637.911002028.1420.4985.3721.583002075.36124.00100.08123.750020127.91273.57187.99273.18100020255.29789.25293.53788.7230308.882.3029.9210.27503012.913.9152.0010.781003022.5510.1045.8011.623003055.1764.75149.7164.735003088.77145.31127.46145.04100030174.73424.34205.63424.03

在表2中,T為運(yùn)行時(shí)間(ms),Q為負(fù)載均衡度(1),n代表任務(wù)數(shù),m為服務(wù)器數(shù)(虛擬機(jī)數(shù)).

圖2 虛擬機(jī)組的計(jì)算能力(MIPS)Fig.2 Computation power of VMs

實(shí)驗(yàn)運(yùn)行環(huán)境為Windows10 64位操作系統(tǒng),Intel Core i5-7500CPU,8GB內(nèi)存.

為了描述更方便,下面將本實(shí)驗(yàn)中服務(wù)器上的虛擬機(jī)計(jì)算能力以圖表方式列出來:10個(gè)服務(wù)器為一個(gè)組,后面的20、30是前10個(gè)服務(wù)器計(jì)算能力的復(fù)制.配置除了計(jì)算能力MIPS,即每秒可以執(zhí)行多少百萬的指令數(shù)量不同,其余數(shù)據(jù)都相同.本文使用虛擬機(jī)的MIPS具體數(shù)據(jù)設(shè)置見圖2.

其中任務(wù)長度為初始化為500-10000的隨機(jī)整數(shù)常數(shù).幾種算法的運(yùn)行找到的最佳調(diào)度方案的運(yùn)行時(shí)間和對(duì)應(yīng)的負(fù)載均衡比較如下:(為了除去偶然性影響因素以及更好地觀測全局效果,實(shí)驗(yàn)取10次的平均值,群組的迭代次數(shù)固定20次).

Cloudsim服務(wù)器主機(jī)參數(shù)設(shè)置為:10個(gè)服務(wù)器(虛擬機(jī))的時(shí)候ram=8192,bw=10000,20個(gè)服務(wù)器(虛擬機(jī))的時(shí)候ram=16384,bw=20000,30個(gè)服務(wù)器(虛擬機(jī))的時(shí)候ram=24576,bw=30000.(ran即為內(nèi)存,bw即為帶寬)

表3 算法對(duì)比情況
Table 3 Algorithm comparison

QPSOGAnmTQTQ301018.739.1525.918.97501025.0021.6931.75123.851001044.4765.6254.1265.1630010131.34365.12139.23364.7850010231.43793.11233.09792.92100010476.752259.74471.252259.72302010.733.3020.583.80502016.647.0025.606.871002027.8320.6335.6820.323002076.02123.7879.17123.7250020128.63273.48131.82273.48100020258.26789.00262.79788.9930309.662.1716.262.65503014.693.7320.523.861003022.3810.4428.3910.113003055.44122.5660.8764.545003090.02145.2299.94145.00100030180.97424.14181.88424.91

從表2和表3可以看出,TDDCBA對(duì)于不同任務(wù)數(shù)和不同服務(wù)器數(shù)的邊緣計(jì)算任務(wù)調(diào)度所產(chǎn)生的時(shí)間開銷和負(fù)載均衡度絕大多數(shù)情況下均小于QPSO,GA和BA算法.在本文中,還加入了服務(wù)器之間的帶寬因素,所以TDDCBA算法所要求解的問題復(fù)雜度更高.其他三種算法在較小的迭代次數(shù)和較小的種群數(shù)量情況下,對(duì)比尋優(yōu)效率普遍小于TDDCBA,容易陷入局部最優(yōu)狀態(tài),而加入了二維擾動(dòng)因子和混沌因子的TDDCBA算法可以更好地跳出局部最優(yōu),實(shí)現(xiàn)在較少的迭代次數(shù)和較小的種群數(shù)量情況下獲得更優(yōu)解的效果.而表2和表3為了消除偶然性,取的是10次實(shí)驗(yàn)的平均值,較小的誤差和個(gè)別的相較于TDDCBA更短的時(shí)間開銷值不能較直觀顯示QPSO和TDDCBA算法之間的差別,接下來對(duì)于多次運(yùn)行結(jié)果的數(shù)據(jù)進(jìn)行對(duì)比,比較算法的穩(wěn)定性.由于種群初始化是隨機(jī)生成的,所以算法每次運(yùn)行的時(shí)候初始種群數(shù)據(jù)都會(huì)不一樣,所以這就要求算法需要有一定的穩(wěn)定性,對(duì)于不同的初始化情況都有較好的收斂性.

4.2 算法穩(wěn)定性對(duì)比

算法變化趨勢對(duì)比圖3所示.(為了查看全局效果運(yùn)行10次):

圖3中使用虛擬機(jī)數(shù)量為10,任務(wù)數(shù)量為30,迭代次數(shù)均設(shè)置為20,對(duì)比各算法多次運(yùn)行結(jié)果,可以看到TDDCBA算法的穩(wěn)定性較好,并且具有較強(qiáng)的尋優(yōu)能力,與其對(duì)比的算法中GA尋優(yōu)能力不夠好,QPSO和BA算法變化起伏較大.

為了對(duì)比算法效率,再次減少種群迭代次數(shù),迭代次數(shù)為10的結(jié)果見圖4(任務(wù)數(shù)量為300,虛擬機(jī)數(shù)量為10,ram=8192,bw=10000為了查看全局效果運(yùn)行21次).

圖3 算法迭代趨勢變化Fig.3 Algorithm iteration trend

圖4 算法迭代趨勢變化Fig.4 Algorithm iteration trend

從圖4中能看出,TDDCBA算法在較小的群組迭代次數(shù)下同樣有較好的效果,而在這方面,GA和BA算法明顯較弱,而QPSO的波動(dòng)范圍較大,不能很好地穩(wěn)定在一定的范圍內(nèi),相比較于TDDCBA具有較差的穩(wěn)定性.

同時(shí)對(duì)于服務(wù)器之間的負(fù)載均衡為主判斷標(biāo)準(zhǔn)的實(shí)驗(yàn)效果如下,同樣為了消除偶然性取10次結(jié)果平均值.

表4 算法對(duì)比情況
Table 4 Algorithm comparison

TDDCBABAnmQTQT30108.1737.8619.9270.9430010363.60219.63615.76736.51

表5 算法對(duì)比情況
Table 5 Algorithm comparison

QPSOGAnmQTQT30109.4231.558.9037.7330010363.66273.80363.84215.36

根據(jù)表4和表5可以看到,BA相比于TDDCBA效果非常差,而與GA相比,TDDCBA對(duì)于主要適應(yīng)度函數(shù)具有較好的尋優(yōu)效果,但是存在偶然性GA效果相比較于TDDCBA運(yùn)行時(shí)間更短,在多目標(biāo)優(yōu)化的情況下TDDCBA算法與GA相比一定情況下存在一定的缺陷.與QPSO相比,在任務(wù)數(shù)量只有30的時(shí)候,由于虛擬機(jī)的MISP不相等和誤差的存在,TDDCBA雖然負(fù)載均衡度高,但是某些情況下運(yùn)行時(shí)間不是最佳.然而任務(wù)數(shù)量到了300后,時(shí)間上的優(yōu)勢被擴(kuò)大,TDDCBA算法的優(yōu)勢被體現(xiàn)了出來.

4.3 算法負(fù)載均衡度對(duì)比

圖5是對(duì)于30個(gè)任務(wù)分配給10臺(tái)虛擬機(jī)的預(yù)測調(diào)度方案的負(fù)載均衡的效果比較.

圖5 多次調(diào)度方案負(fù)載均衡度比較Fig.5 Comparison of load balancing degree of multiple scheduling schemes

可以看到當(dāng)負(fù)載均衡度作為主要評(píng)判標(biāo)準(zhǔn)的時(shí)候,TDDCBA具有很好的穩(wěn)定性,這是因?yàn)槎S擾動(dòng)因子和混沌因子具有較好的全局搜索能力,能夠在迭代次數(shù)和種群數(shù)量限制下快速收斂從而能有效防止粒子早熟,所以多次實(shí)驗(yàn)結(jié)果適應(yīng)度值基本不變.

綜上TDDCBA在BA算法的基礎(chǔ)上改進(jìn)有很好的效果,同時(shí)對(duì)比其他效果較好的算法也能在較少的迭代次數(shù)下?lián)碛懈玫男Ч?應(yīng)用到云計(jì)算和邊緣計(jì)算的協(xié)同調(diào)度模型中能有效減少邊緣服務(wù)器調(diào)度時(shí)間.

5 總結(jié)展望

本文針對(duì)邊緣計(jì)算服務(wù)器之間通過云平臺(tái)調(diào)度策略和調(diào)度速度深入分析當(dāng)前較先進(jìn)的調(diào)度算法,降低由于調(diào)度不均衡導(dǎo)致的速度長、負(fù)載不均問題,主要進(jìn)行了以下改進(jìn):對(duì)于現(xiàn)有效果較好算法進(jìn)行改進(jìn),使尋優(yōu)能力增強(qiáng),陷入局部最優(yōu)概率大幅度降低,實(shí)驗(yàn)結(jié)果詳細(xì)分析了在CloudSim云仿真平臺(tái)上的仿真結(jié)果,接下來可以進(jìn)行算法的更優(yōu)值尋找改進(jìn),同時(shí)將算法應(yīng)用到多目標(biāo)優(yōu)化中,實(shí)驗(yàn)證明混沌特性比量子具有較好的擺脫局部優(yōu)勢的能力,并且能夠在較少的迭代次數(shù)下找到較優(yōu)的解,同時(shí)一定程度的二維擾動(dòng)對(duì)于跳出局部最優(yōu)具有很好的效果.