面向云計(jì)算的任務(wù)調(diào)度算法綜述①

楊 戈,趙 鑫,黃 靜,2

1(北京師范大學(xué)珠海分校 智能多媒體技術(shù)重點(diǎn)實(shí)驗(yàn)室,珠海 519087)

2(北京師范大學(xué)研究生院珠海分院,北京 100875)

3(北京大學(xué)深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實(shí)驗(yàn)室,深圳 518055)

1 引言

而隨著云技術(shù)的發(fā)展和云平臺(tái)的廣泛部署,云中的工作流調(diào)度問題成為一個(gè)重要的研究課題[1],在云計(jì)算服務(wù)交付的過程中,由于用戶直接面對(duì)的是虛擬機(jī)資源,而真正解決問題的是虛擬機(jī)映射的實(shí)際的物理資源,所以如何將任務(wù)合理分配到資源執(zhí)行是我們所重點(diǎn)關(guān)注的.

(1)云計(jì)算

云計(jì)算通過多種部署方式,包括私有云、社區(qū)云、公有云、混合云4 種部署模型[2],通過基礎(chǔ)設(shè)施即服務(wù)、平臺(tái)即服務(wù)、軟件即服務(wù)3 種服務(wù)模式用戶提供服務(wù).云計(jì)算有2 個(gè)顯著的特征,快速彈性可擴(kuò)展[3]、按需付費(fèi)服務(wù)[4].

云計(jì)算關(guān)鍵技術(shù)[5]分別有:虛擬化技術(shù)[6]、分布式數(shù)據(jù)存儲(chǔ)技術(shù)[7]、大規(guī)模數(shù)據(jù)管理技術(shù)[7]、調(diào)度技術(shù)[8].

(2)調(diào)度技術(shù)

云計(jì)算中的調(diào)度一般分為兩個(gè)部分:① 資源調(diào)度:資源調(diào)度是指對(duì)物理資源進(jìn)行合理有效的管理和使用等;② 任務(wù)調(diào)度:將任務(wù)合理分配到合適的計(jì)算資源執(zhí)行.

簡單點(diǎn)講,一次正常的用戶服務(wù)流程為:用戶提交任務(wù)到云端,任務(wù)調(diào)度器將任務(wù)分配到合適的計(jì)算資源上執(zhí)行,任務(wù)完成后再將結(jié)果反饋給用戶.其中,任務(wù)分配這一環(huán)尤其重要,一個(gè)合理高效的調(diào)度策略能夠極大的提升云計(jì)算系統(tǒng)的性能.下文重點(diǎn)關(guān)注的是任務(wù)調(diào)度.

隨著云用戶數(shù)量的不斷增加,為用戶提供優(yōu)質(zhì)的服務(wù)勢(shì)在必行.因此,任務(wù)調(diào)度非常重要,因?yàn)樗鼘Ｗ⒂谠谔囟〞r(shí)間將任務(wù)分配給可用資源.為了獲得良好的用戶服務(wù)質(zhì)量,需要高效的任務(wù)調(diào)度.現(xiàn)有的云計(jì)算任務(wù)調(diào)度技術(shù)已經(jīng)被研究者們提出,但要實(shí)現(xiàn)高效的任務(wù)調(diào)度,還需要進(jìn)一步的改進(jìn).所有算法的主要目標(biāo)都是最大限度地利用資源,最大限度地減少制造時(shí)間和成本,提高性能.

(3)云環(huán)境中的服務(wù)交付模型

云計(jì)算中的服務(wù)交付模型分為4 部分,如圖1 所示.

① 用戶提交任務(wù);

② 任務(wù)管理器將其拆分成多個(gè)子任務(wù);

③ 任務(wù)調(diào)度器通過調(diào)度技術(shù)將子任務(wù)與物理資源建立映射關(guān)系;

④ 任務(wù)完成后進(jìn)行匯總,反饋到用戶.

由此看出,從任務(wù)出發(fā)到完成,在整個(gè)任務(wù)執(zhí)行過程中,調(diào)度技術(shù)是重中之重,它影響到了整個(gè)系統(tǒng)的運(yùn)行效率、用戶服務(wù)質(zhì)量、系統(tǒng)負(fù)載均衡、系統(tǒng)能耗.

因此一個(gè)適合云計(jì)算環(huán)境的調(diào)度技術(shù)十分重要.由于調(diào)度技術(shù)分為資源調(diào)度和任務(wù)調(diào)度,本文只關(guān)注任務(wù)調(diào)度.

圖1 云計(jì)算服務(wù)交付模型圖

2 任務(wù)調(diào)度

任務(wù)調(diào)度,在云計(jì)算環(huán)境下其本質(zhì)是一個(gè)映射的過程,它在一定的約束條件下,根據(jù)云計(jì)算環(huán)境下任務(wù)、資源兩者的預(yù)測(cè)信息和狀態(tài)將用戶提交的互相獨(dú)立的任務(wù)映射到相應(yīng)的虛擬機(jī)資源上執(zhí)行,然后返回處理結(jié)果[9].簡單點(diǎn)說,就是將x個(gè)任務(wù)分配到y(tǒng)個(gè)計(jì)算機(jī)資源上執(zhí)行的過程.

根據(jù)工作流和資源的可用信息以及任務(wù)分配給資源的時(shí)間可以將任務(wù)調(diào)度分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度[1].

2.1 調(diào)度分類

2.1.1 靜態(tài)調(diào)度

靜態(tài)調(diào)度中分為4 類:列表調(diào)度啟發(fā)式[10,11]、聚類調(diào)度啟發(fā)式[11]、重復(fù)調(diào)度啟發(fā)式、元啟發(fā)式.

(1)列表啟發(fā)式

基本思想是通過給任務(wù)分配一些優(yōu)先級(jí),并根據(jù)優(yōu)先級(jí)對(duì)其進(jìn)行排序,從而生成一個(gè)任務(wù)調(diào)度列表,然后從調(diào)度列表中選擇第一個(gè)任務(wù),再將任務(wù)分配給其對(duì)應(yīng)的資源,直到對(duì)所有任務(wù)進(jìn)行調(diào)度.

調(diào)度列表可以靜態(tài)或動(dòng)態(tài)構(gòu)造.如果所有優(yōu)先級(jí)都是在任務(wù)分配之前構(gòu)造的,則為靜態(tài)列表調(diào)度;如果在每個(gè)任務(wù)調(diào)度之后重新計(jì)算未調(diào)度任務(wù)的優(yōu)先級(jí),則為動(dòng)態(tài)列表調(diào)度.但是無論是哪種列表調(diào)度,都必須要有一個(gè)優(yōu)先級(jí)的判斷屬性和資源選擇策略,并以此決定任務(wù)的優(yōu)先級(jí)與其對(duì)應(yīng)的最佳資源.

常見的列表調(diào)度啟發(fā)式算法,如最早時(shí)間優(yōu)先(Earliest Time First,ETF),異類最早完成時(shí)間(Predict Earliest Finish Time,PEFT)[10]等.

(2)聚類啟發(fā)式

基本思想是通過在同一個(gè)集群中對(duì)任務(wù)進(jìn)行聚類,將任務(wù)映射到集群,在同一個(gè)群集中排序任務(wù).盡量犧牲并行性來降低通信延遲,優(yōu)化數(shù)據(jù)相關(guān)任務(wù)之間的傳輸時(shí)間.

如果同一個(gè)集群中有兩個(gè)獨(dú)立的鄰居任務(wù),則稱為非線性集群;否則稱為線性集群.對(duì)于非線性聚類,對(duì)獨(dú)立任務(wù)進(jìn)行排序.線性聚類保留了并行性,不會(huì)增加并行執(zhí)行時(shí)間.非線性聚類通過對(duì)并行任務(wù)進(jìn)行排序來減少并行性,從而增加并行執(zhí)行時(shí)間.

(3)重復(fù)啟發(fā)式

基本思想是在目標(biāo)任務(wù)的同一資源上正確地復(fù)制任務(wù),從而避免這兩個(gè)任務(wù)之間的執(zhí)行時(shí)間沖突,以及在不同的時(shí)間段內(nèi)可能會(huì)發(fā)生一些資源閑置的情況.

因?yàn)樵趯?shí)際的調(diào)度中,有些任務(wù)可能正在等待分配給其他資源的任務(wù)的數(shù)據(jù),只有接收到該數(shù)據(jù)之后,任務(wù)才能開始執(zhí)行,如果在數(shù)據(jù)接收之前輪到該任務(wù)執(zhí)行,就會(huì)發(fā)生阻塞,產(chǎn)生空閑時(shí)段,直到數(shù)據(jù)到來,影響到后面任務(wù)的執(zhí)行.如果使用有效的調(diào)度算法,通過識(shí)別任務(wù)使得這些空閑時(shí)段可以有效地利用,那么就可以縮短總的執(zhí)行時(shí)間.

基于重復(fù)的調(diào)度通常可以縮短生成時(shí)間.然而,這也使得調(diào)度問題更加困難.調(diào)度算法不僅需要觀察任務(wù)之間的優(yōu)先級(jí)約束,還需要識(shí)別哪些任務(wù)需要復(fù)制,以及如何將它們放入空閑時(shí)段.

(4)元啟發(fā)式

元啟發(fā)式是啟發(fā)式的進(jìn)化版,是對(duì)啟發(fā)式局部搜索的改進(jìn),元啟發(fā)式方法通常提供了一種快速朝著一個(gè)非常好的解決方案前進(jìn)的有效方法.如遺傳算法、蟻群算法、粒子群算法等.

與基于局部搜索的啟發(fā)式方法相比,元啟發(fā)式方法能夠在更大的解空間中搜索到任務(wù)解決方案.因此,在大多數(shù)情況下,元啟發(fā)式比基于局部搜索的啟發(fā)式性能更好.

將以上局部的靜態(tài)調(diào)度做了一個(gè)比較,比較結(jié)果如表1 所示.

列表啟發(fā)式大部分都適用于資源數(shù)量有限的系統(tǒng),比較關(guān)注如何在保證能完成調(diào)度的同時(shí)降低系統(tǒng)的開銷.

聚類啟發(fā)式通常假定資源數(shù)量無限,并將大量通信任務(wù)分配給同一類資源.雖然它減少了資源間的通信,但當(dāng)任務(wù)在資源上按優(yōu)先級(jí)約束排序時(shí),也可能導(dǎo)致負(fù)載不平衡或空閑時(shí)隙.

重復(fù)啟發(fā)式算法旨在降低任務(wù)的執(zhí)行時(shí)間,避免大量的通信.重復(fù)啟發(fā)式通常在犧牲計(jì)算時(shí)間復(fù)雜性的情況下具有更好的調(diào)度質(zhì)量.

元啟發(fā)式比以上基于局部的啟發(fā)式性能更好.但是,隨著工作流任務(wù)數(shù)的增加,元啟發(fā)式算法的調(diào)度時(shí)間開銷也會(huì)迅速增加.

表1 靜態(tài)調(diào)度比較表

2.1.2 動(dòng)態(tài)調(diào)度

動(dòng)態(tài)調(diào)度[12]是為了解決調(diào)度信息的不可用性和資源與其他工作流或非工作流系統(tǒng)負(fù)載的爭用而開發(fā)的,目標(biāo)是在可用資源隊(duì)列之間平衡負(fù)載.

任務(wù)執(zhí)行和通信時(shí)間由資源和工作流信息共同決定.其中工作流信息包括工作流結(jié)構(gòu)、任務(wù)執(zhí)行工作量、通信數(shù)據(jù)量等,資源信息包括云環(huán)境下的可用性、處理能力、通信帶寬等.在實(shí)際生產(chǎn)系統(tǒng)中它們都是不完整的、動(dòng)態(tài)的.要準(zhǔn)確地評(píng)估每個(gè)隊(duì)列的負(fù)載并不容易,因此需要一個(gè)動(dòng)態(tài)調(diào)度策略來處理這些不確定性.

總的來說,在靜態(tài)中,所有關(guān)于任務(wù)的信息在執(zhí)行之前都是調(diào)度程序已知的,可以事先獲取到更多信息,對(duì)任務(wù)調(diào)度的方案進(jìn)行優(yōu)化,使得任務(wù)實(shí)際執(zhí)行時(shí)開銷更小;而在動(dòng)態(tài)中,關(guān)于任務(wù)的信息在執(zhí)行之前不知道,但運(yùn)行時(shí)開銷更大,但是能更好地處理負(fù)載平衡的問題.

通過對(duì)調(diào)度的分析發(fā)現(xiàn),不管是靜態(tài)還是動(dòng)態(tài)調(diào)度,由理論到實(shí)際解決問題都是依靠具體的任務(wù)調(diào)度算法執(zhí)行的.簡單地說,一種任務(wù)調(diào)度算法就是一種調(diào)度方式,云計(jì)算中任務(wù)調(diào)度的優(yōu)劣主要就體現(xiàn)在任務(wù)調(diào)度算法的優(yōu)劣上.

合理的任務(wù)調(diào)度要從2 個(gè)出發(fā)點(diǎn)進(jìn)行考慮:云計(jì)算提供商,用戶.對(duì)提供商來說,最關(guān)心的就是成本,所以要能夠有效協(xié)調(diào)和分配資源,降低成本;對(duì)用戶來說,服務(wù)質(zhì)量放在首位,所以需要在完成需求的同時(shí),降低任務(wù)的總執(zhí)行時(shí)間.

所以一個(gè)既可以對(duì)虛擬資源進(jìn)行有效的協(xié)調(diào)和分配,降低提供商的成本;又能快速、準(zhǔn)確地完成任務(wù),給用戶一個(gè)好的用戶體驗(yàn);能讓提供商和用戶都滿意的任務(wù)調(diào)度算法是云計(jì)算所迫切需要的.

而任務(wù)調(diào)度的約束條件就是依靠具體的任務(wù)調(diào)度算法來執(zhí)行的,所以選擇合適的任務(wù)調(diào)度算法對(duì)策略的執(zhí)行具有很重大的意義.

2.2 任務(wù)調(diào)度算法

任務(wù)調(diào)度算法根據(jù)調(diào)度目標(biāo)的數(shù)量可以分為2 類:針對(duì)單一目標(biāo)優(yōu)化的傳統(tǒng)任務(wù)調(diào)度算法,針對(duì)多目標(biāo)優(yōu)化的啟發(fā)式思想的智能化算法.

2.2.1 單目標(biāo)優(yōu)化的任務(wù)調(diào)度算法

單目標(biāo)優(yōu)化的任務(wù)調(diào)度算法主要包括最小完成時(shí)間(Minimum Completion Time,MCT)、最小執(zhí)行時(shí)間(Minimum Execution Time,MET)、交換算法(Switching Algorithm,SA)、貪心算法(GReedy Algorithm,GRA)、先來先服務(wù)(先進(jìn)先出)算法(First Come First Server,FCFS/First In First Out,FIFO)、短作業(yè)優(yōu)先算法(Shortest Job First,SJF)等.

其中MET 算法考慮到任務(wù)的最短執(zhí)行時(shí)間,忽略了負(fù)載是否平衡的問題;MCT 算法考量到任務(wù)最早的完成時(shí)間,但是可能導(dǎo)致工作時(shí)間變長;SJF 算法考慮選擇用時(shí)較短的任務(wù)優(yōu)先執(zhí)行,而忽略了任務(wù)的優(yōu)先級(jí).

從以上不難看出:單目標(biāo)優(yōu)化的任務(wù)調(diào)度算法重點(diǎn)在于單一目標(biāo)的最優(yōu)解,即某個(gè)實(shí)例的最優(yōu),體現(xiàn)在“最”字上,這樣的話其他實(shí)例沒在考慮的范圍內(nèi),就會(huì)不可避免的舍棄掉很多東西,比較局限于某個(gè)目標(biāo)最優(yōu),而無法考慮到全局,都是比較極端的算法,為了達(dá)到目標(biāo),可以不惜犧牲一切.導(dǎo)致的后果是:雖然該實(shí)例取得的效果最好,但是因?yàn)橐畲蠡臐M足它而舍棄掉太多東西,導(dǎo)致其他實(shí)例的效果就不是很理想甚至很糟糕,使得結(jié)果具有很大的局限性而無法推廣.

2.2.2 多目標(biāo)優(yōu)化的任務(wù)調(diào)度算法

在優(yōu)化設(shè)計(jì)中,要求多個(gè)目標(biāo)達(dá)到最優(yōu)的問題被稱為多目標(biāo)優(yōu)化或者多約束問題.在這種情況下,基于啟發(fā)式思想的智能化算法應(yīng)運(yùn)而生.

啟發(fā)式思想的智能化算法思想在于:解決多約束問題時(shí),在可以接受的花費(fèi)的前提下,得到一個(gè)解決方案,給出盡量滿足多個(gè)目標(biāo)優(yōu)化的一個(gè)可行解.其核心點(diǎn)在于“多目標(biāo)優(yōu)化”,即對(duì)于每一個(gè)實(shí)例來說,也許當(dāng)下解并不是它的最優(yōu)解,但卻是多個(gè)實(shí)例在盡量滿足需求條件下的極優(yōu)解.

常用的啟發(fā)式思想的智能化算法包括2 類[13]:

(1)基于生物啟發(fā)(Biological Inspiration,BI)

遺傳算法(Genetic Algorithm,GA)、模因算法(Memetic Algorithm,MA)、獅子算法(Lion Algorithm,LA)、帝國競爭算法(Imperialist Competitive Algorithm,ICA),是在云計(jì)算中與任務(wù)調(diào)度相關(guān)的少數(shù)生物啟發(fā)算法.

(2)基于群體智能(Swarm Intelligence,SI)

蟻群(Ant Colony Optimization,ACO)算法、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法、模擬退火(Simulated Annealing,SA)算法、人工蜂群(Artificial Bee Colony,ABC)算法、貓群優(yōu)化(Cat Swarm Optimization,CSO)算法、蝙蝠算法(Bat Algorithm,BA)、風(fēng)驅(qū)動(dòng)優(yōu)化(Wind Driven Optimization,WDO)算法等[13].

3 任務(wù)調(diào)度算法

3.1 遺傳算法

GA 的創(chuàng)造思路來源于達(dá)爾文著名的生物進(jìn)化論中“優(yōu)勝劣汰”的自然選擇原則,將自然生物的進(jìn)化類比應(yīng)用到實(shí)際問題中,是通過模擬自然進(jìn)化的過程來解決組合優(yōu)化問題的一種搜索最優(yōu)解的方法.

GA 對(duì)于給定問題的任何解決方案都由一組稱為基因的元素組成的染色體代表,即每一條染色體代表一個(gè)解決方案.算法終止后,最出色的染色體就是給定問題的最優(yōu)解.

算法的優(yōu)點(diǎn):進(jìn)行選擇、交叉、變異等操作的目標(biāo)是選擇區(qū)域中所有的染色體,初期全局搜索能力強(qiáng),并行性強(qiáng);

缺點(diǎn):要花費(fèi)大量時(shí)間對(duì)染色體進(jìn)行評(píng)估、選擇、交叉、變異等操作,后期求解效率低.

遺傳算法的優(yōu)點(diǎn)主要在于其強(qiáng)力的全局搜索,但是在算法的搜索效率以及算法解的多樣性方面還是需要改進(jìn),所以以下文獻(xiàn)主要對(duì)算法的這2 個(gè)部分進(jìn)行優(yōu)化,如表2 所示.

表2 遺傳算法優(yōu)化表

3.2 蟻群算法

ACO 最早是于20 世紀(jì)90 年代,Dorigo M 等[19]通過觀察螞蟻覓食行為,并從中獲得設(shè)計(jì)靈感而提出的,常用于求解復(fù)雜組合優(yōu)化問題的一種元啟發(fā)式智能優(yōu)化技術(shù)[20].

信息素的管理主要包括信息素的局部更新和信息素的全局更新2 個(gè)部分[21].

算法的優(yōu)點(diǎn):在后期確定了目標(biāo)點(diǎn)和最優(yōu)路徑之后,所有成員每次都會(huì)按照最優(yōu)路徑進(jìn)行計(jì)算,節(jié)省大量時(shí)間,速度快.

缺點(diǎn):在初期確定目標(biāo)點(diǎn)和最優(yōu)路徑時(shí),因?yàn)樾畔T乏需要花費(fèi)大量的時(shí)間做大量的摸索嘗試,速度慢.

蟻群個(gè)體之間通過信息素交流,信息素積累起來之后,搜索效率、解的精度極高,但同時(shí),其缺點(diǎn)在于前期信息素的積累花費(fèi)了太多時(shí)間,由于收斂速度快,也容易陷入局部最優(yōu),所以以下文獻(xiàn)主要在算法的解的多樣性和算法前期的搜索效率方面進(jìn)行優(yōu)化,如表3所示.

表3 蟻群算法優(yōu)化表

3.3 粒子群算法

粒子群算法,也稱為鳥群、魚群覓食算法,是模擬鳥群、魚群的覓食行為規(guī)律在搜索空間進(jìn)行搜索最優(yōu)解的方法.最早由Kennedy J 和Eberhart R[26],該算法最初是對(duì)一個(gè)簡化的社會(huì)環(huán)境的模擬,主要應(yīng)用于求解連續(xù)搜索范圍問題[27].

與遺傳算法這種進(jìn)化算法不同,遺傳算法會(huì)舍棄適應(yīng)度較低的染色體,而粒子群不使用選擇,不會(huì)舍棄任何一個(gè)解,盡管這個(gè)解的質(zhì)量很差,算法會(huì)利用粒子間的信息交流對(duì)差解不斷地優(yōu)化,所有的種群成員從試驗(yàn)開始一直存活到最后.

算法的優(yōu)點(diǎn):搜索速度快、收斂速度快、參數(shù)少等.

缺點(diǎn):局部搜索能力差、初始化粒子隨機(jī)性強(qiáng).

粒子群和蟻群算法在某些方面比較相似,搜索速度快,但是容易陷入極值,所以以下文獻(xiàn)主要在算法多樣性和精度方面進(jìn)行優(yōu)化,如表4 所示.

表4 粒子群算法多樣性優(yōu)化表

3.4 模擬退火算法

模擬退火算法是一種隨機(jī)搜索算法,是對(duì)熱力學(xué)中固體物質(zhì)退火過程的模擬.文獻(xiàn)[34]中介紹模擬退火算法最早的思想是由Metropolis 等提出.Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領(lǐng)域.

固體物質(zhì)退火過程與一般組合優(yōu)化問題之間的相似性如表5 所示.

表5 模擬退火算法與組合優(yōu)化問題的相似性

SA 對(duì)于給定問題的任何解決方案都由退火過程中物質(zhì)的狀態(tài)代表,即每個(gè)溫度下物質(zhì)的狀態(tài)代表一個(gè)解決方案,當(dāng)內(nèi)能到達(dá)最低時(shí),物質(zhì)的狀態(tài)就代表最優(yōu)解[35].

算法的優(yōu)點(diǎn):穩(wěn)定性好,在局部最優(yōu)時(shí)容易有概率跳出并趨于全局最優(yōu);

缺點(diǎn):對(duì)參數(shù)依賴性強(qiáng),收斂速度慢,搜索時(shí)間長.如果冷卻過程足夠慢,模擬運(yùn)行時(shí)間足夠長,模擬退火幾乎可以保證找到最優(yōu)的解決方案.

與其它智能算法不同的是,SA 在迭代過程中會(huì)以一定的概率接受與當(dāng)前解相比較差的解,接受概率隨著溫度的降低減小.由于在搜索過程中接受差解,所以有可能導(dǎo)致遺失掉最優(yōu)解;另一方面,這種處理可以在一定程度上避免算法陷入局部最優(yōu)解.

以下文獻(xiàn)主要在使用Metropolis 準(zhǔn)則對(duì)新解進(jìn)行一個(gè)概率接受的部分進(jìn)行優(yōu)化,減小陷入局部最優(yōu)的可能性.如表6 所示.

3.5 算法對(duì)比

由以上第4 章對(duì)各算法的闡述,發(fā)現(xiàn)各個(gè)算法都有其自身的優(yōu)點(diǎn)和不足,這里對(duì)其能力的各個(gè)方面進(jìn)行比較,如表7 所示.

算法搜索過程中會(huì)進(jìn)行信息交互的算法ACO,PSO 都會(huì)面臨一個(gè)問題:信息交互后,每個(gè)個(gè)體都會(huì)受到優(yōu)秀個(gè)體搜索結(jié)果的影響,都會(huì)向著優(yōu)秀的個(gè)體“看齊”,這樣就會(huì)導(dǎo)致算法收斂速度大大加快.算法收斂速度快會(huì)產(chǎn)生2 種結(jié)果:

① 算法整體的進(jìn)程節(jié)奏加快,更早地達(dá)到終止條件;

② 算法喪失多樣性,容易陷入局部最優(yōu).

與之相反,GA,SA 的收斂速度都相對(duì)比較慢,其原因是GA 會(huì)對(duì)種群中的大量個(gè)體執(zhí)行操作,SA 則會(huì)對(duì)溫度變化過程中產(chǎn)生的每一個(gè)新解都進(jìn)行操作,花費(fèi)了大量的時(shí)間,收斂速度自然就快不起來.算法收斂速度慢會(huì)產(chǎn)生2 種結(jié)果:

③ 算法整體的進(jìn)程節(jié)奏過慢,算法搜索效率低;

④ 加強(qiáng)了算法的全局搜索能力,有效降低陷入局部最優(yōu)的可能性.

所以如何將算法的收斂性利用好,在加速算法進(jìn)程的同時(shí)增加算法解決方案的多樣性是值得進(jìn)行研究的.

啟發(fā)式思想的智能化算法相比較于傳統(tǒng)的算法優(yōu)化更全面,適用性更廣,雖然各自有各自的特點(diǎn),但同時(shí)也有自身的不足,要想使其具有更強(qiáng)的生命力,就需要不斷自我提升;同時(shí)也需要借鑒其他算法的優(yōu)勢(shì),彼此相互學(xué)習(xí),優(yōu)劣互補(bǔ)來彌補(bǔ)自身的不足,同時(shí)達(dá)到更優(yōu)的效果.

表6 模擬退火算法優(yōu)化表

表7 算法對(duì)比

4 結(jié)束語

對(duì)云計(jì)算作了一個(gè)概述,闡述了云計(jì)算環(huán)境下的任務(wù)調(diào)度模型,并對(duì)其進(jìn)行了分析,再由任務(wù)調(diào)度引出4 個(gè)比較完善、具有代表性的任務(wù)調(diào)度算法ACO、GA、PSO、SA,分別對(duì)它們做了詳細(xì)分析,包括基本思想、算法特點(diǎn)以及可改進(jìn)的方式,針對(duì)各個(gè)算法的特點(diǎn),歸納了一些各個(gè)算法兩兩之間可以進(jìn)行改進(jìn)以及融合方法;再對(duì)相比前面4 種算法,比較新穎的ACO、ICA、BA、CSO 做了分析,包括算法的基本思想、特點(diǎn)和可改進(jìn)的方式;由于從理論想要應(yīng)用到實(shí)踐,就必須要經(jīng)過實(shí)驗(yàn)對(duì)其進(jìn)行驗(yàn)證,而直接投入實(shí)際環(huán)境中進(jìn)行實(shí)驗(yàn)會(huì)花費(fèi)大量的時(shí)間、資源等.

隨著信息技術(shù)的不斷進(jìn)步,物聯(lián)網(wǎng)在我們的日常生活中發(fā)揮著越加重要的作用,人們生活水平的提高,對(duì)各種物聯(lián)網(wǎng)應(yīng)用的要求也越來越高,對(duì)云計(jì)算的挑戰(zhàn)也隨之到來.在傳統(tǒng)的云計(jì)算中,每一次服務(wù)交付都要將計(jì)算過程上傳到云,有限的帶寬和網(wǎng)絡(luò)資源被大量數(shù)據(jù)傳輸所占用,然而云是遠(yuǎn)離用戶的,這就直接造成了云計(jì)算所面臨的第一大難點(diǎn):網(wǎng)絡(luò)延遲.此外,物聯(lián)網(wǎng)設(shè)備和傳感器的功率是有限的,大量的數(shù)據(jù)傳輸也給物理設(shè)備帶來了壓力,這也是云計(jì)算所面臨的第二大難點(diǎn):功耗成本.

為了延長設(shè)備的使用壽命,就很有必要通過將計(jì)算調(diào)度到具有更高功率和計(jì)算能力的設(shè)備來平衡功耗,即通過改善任務(wù)調(diào)度可以有效地降低云計(jì)算的功耗成本.因此,任務(wù)的調(diào)度和處理分配就成為了云計(jì)算需要解決的關(guān)鍵問題.

雖然通過調(diào)度方案的優(yōu)化可以減少云計(jì)算的功耗,但是由于云計(jì)算服務(wù)中,每一次服務(wù)交付都要將計(jì)算過程上傳到云端,即使改進(jìn)了調(diào)度方案,還是無法有效地解決網(wǎng)絡(luò)延遲的問題.

為了解決云計(jì)算網(wǎng)絡(luò)延遲的問題,邊緣計(jì)算[40]出現(xiàn)了.邊緣計(jì)算不同于云計(jì)算,很直觀地,邊緣計(jì)算就是在網(wǎng)絡(luò)的“邊緣”進(jìn)行服務(wù)交付,執(zhí)行的數(shù)據(jù)計(jì)算和存儲(chǔ)在用戶附近.相比較云計(jì)算與用戶的距離更近近,最直觀導(dǎo)致的結(jié)果就是降低了網(wǎng)絡(luò)延遲、網(wǎng)絡(luò)的帶寬需求、數(shù)據(jù)計(jì)算或存儲(chǔ)期間的傳輸延遲,并且有效地降低了物理設(shè)備損耗速度.此外,與云計(jì)算相比,邊緣計(jì)算可以將計(jì)算和通信開銷從具有有限電池或電源的節(jié)點(diǎn)遷移到具有大量功率資源的邊緣節(jié)點(diǎn).

2016 年5 月,美國自然科學(xué)基金委(National Science Foundation,NSF)在計(jì)算機(jī)系統(tǒng)研究中將邊緣計(jì)算替換云計(jì)算,列為突出領(lǐng)域[41].雖然其發(fā)展和技術(shù)還不太成熟,但是由于其自身的特點(diǎn),邊緣計(jì)算將會(huì)成為繼云計(jì)算之后的又一大熱點(diǎn)領(lǐng)域.7 個(gè)關(guān)鍵技術(shù)包括:網(wǎng)絡(luò)、隔離技術(shù)、體系結(jié)構(gòu)、邊緣操作系統(tǒng)、算法執(zhí)行框架、數(shù)據(jù)處理平臺(tái)以及安全和隱私;未來幾年迫切需要解決的6 個(gè)方向問題:編程模型、軟硬件選型、基準(zhǔn)程序與標(biāo)準(zhǔn)、動(dòng)態(tài)調(diào)度、與垂直行業(yè)的緊密結(jié)合以及邊緣節(jié)點(diǎn)的落地[41].