基于霧計(jì)算的智能工廠實(shí)時(shí)任務(wù)調(diào)度架構(gòu)

曾 鵬，鮑士兼，趙成林，許方敏

(1.北京郵電大學(xué) 信息與通信工程學(xué)院，北京 100876；2.中國國際工程咨詢有限公司，北京 100048)

0 引言

隨著工業(yè)領(lǐng)域向著數(shù)字化、智能化和服務(wù)化的方向發(fā)展[1]，智能制造技術(shù)已成為工業(yè)界高度重視的領(lǐng)域之一。在此背景下，智能工廠正有效地支持著智能制造的實(shí)施[2]。

然而，隨著智能工廠和物聯(lián)網(wǎng)的發(fā)展，智能工廠中的智能設(shè)備與傳感器越來越普及。傳統(tǒng)的基于云計(jì)算的網(wǎng)絡(luò)架構(gòu)無法再滿足智能工廠應(yīng)用對(duì)時(shí)延的需求[3-4]。

霧計(jì)算將數(shù)據(jù)的分析處理擴(kuò)展到了網(wǎng)絡(luò)邊緣，可以有效地克服云計(jì)算由于長傳輸距離帶來的高時(shí)延的缺點(diǎn)[5-7]。然而，要想充分利用霧計(jì)算中的網(wǎng)絡(luò)資源、使霧計(jì)算中的計(jì)算節(jié)點(diǎn)有效協(xié)作，還需要一個(gè)有效的任務(wù)調(diào)度方案[8-9]。

現(xiàn)有的任務(wù)調(diào)度方法大多是根據(jù)當(dāng)前霧計(jì)算資源的多少，與當(dāng)前接收到的任務(wù)集合進(jìn)行匹配，通過算法將各個(gè)任務(wù)分配到合適的計(jì)算節(jié)點(diǎn)進(jìn)行處理[10-12]。然而，這些研究都只考慮了某一時(shí)刻的任務(wù)調(diào)度，不太適用于實(shí)時(shí)的智能工廠生產(chǎn)環(huán)境。為此，本文深入調(diào)研分析了智能工廠的特點(diǎn)，利用霧計(jì)算的優(yōu)勢，設(shè)計(jì)了一種基于霧計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)，并且基于該架構(gòu)，提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的實(shí)時(shí)任務(wù)調(diào)度方案。

1 網(wǎng)絡(luò)架構(gòu)

基于霧計(jì)算的優(yōu)勢以及智能工廠的特點(diǎn)，設(shè)計(jì)了一個(gè)基于霧計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)，如圖1所示。整個(gè)架構(gòu)分為3層：基礎(chǔ)設(shè)施層、霧計(jì)算層和云計(jì)算層。

圖1 基于霧計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)地理分布Fig.1 Smart factory network architecture based on fog computing

智能設(shè)備層，主要由機(jī)械臂、車床、沖壓設(shè)備和攝像頭等各類現(xiàn)場設(shè)備和傳感器組成，傳感器實(shí)時(shí)采集設(shè)備狀態(tài)數(shù)據(jù)，用于異常檢測、故障診斷和剩余壽命預(yù)測等分析或機(jī)械控制等智能工廠應(yīng)用。根據(jù)現(xiàn)場設(shè)備所在的車間，傳感器通過WiFi、藍(lán)牙或有線鏈路將采集到的數(shù)據(jù)發(fā)送到相應(yīng)的霧節(jié)點(diǎn)進(jìn)行處理。

霧計(jì)算層，由一個(gè)霧管理節(jié)點(diǎn)和多個(gè)霧節(jié)點(diǎn)組成。每個(gè)霧節(jié)點(diǎn)負(fù)責(zé)接收和執(zhí)行所處車間中智能設(shè)備生成的任務(wù)，并定期將自己的運(yùn)行狀態(tài)發(fā)送到霧管理節(jié)點(diǎn)。而霧管理節(jié)點(diǎn)則根據(jù)霧節(jié)點(diǎn)的運(yùn)行狀態(tài)向各個(gè)霧節(jié)點(diǎn)下達(dá)任務(wù)調(diào)度決策，各霧節(jié)點(diǎn)根據(jù)決策調(diào)度等待隊(duì)列中的任務(wù)。霧計(jì)算層由于靠近設(shè)備端，可以處理時(shí)延敏感的任務(wù)。

云計(jì)算層，由高性能的服務(wù)器集群組成，具有強(qiáng)大的計(jì)算和存儲(chǔ)能力，負(fù)責(zé)處理工廠中計(jì)算復(fù)雜度大、延遲敏感度低以及數(shù)據(jù)量大的異構(gòu)數(shù)據(jù)。

因此，霧計(jì)算層負(fù)責(zé)處理實(shí)時(shí)的、時(shí)延敏感的計(jì)算任務(wù)，而云計(jì)算層負(fù)責(zé)處理大規(guī)模的、非實(shí)時(shí)的計(jì)算任務(wù)。由于霧計(jì)算層資源相比于云計(jì)算層相對(duì)匱乏，因此需要有一個(gè)高效的任務(wù)調(diào)度方案對(duì)霧計(jì)算的資源進(jìn)行調(diào)度。

2 實(shí)時(shí)任務(wù)調(diào)度方案

2.1 調(diào)度流程

霧計(jì)算層的任務(wù)調(diào)度模型如圖2所示。在智能工廠中，每個(gè)霧節(jié)點(diǎn)接收其對(duì)應(yīng)車間中智能設(shè)備的任務(wù)請求。任務(wù)請求到達(dá)霧節(jié)點(diǎn)之后，將被放入任務(wù)等待隊(duì)列中等待霧節(jié)點(diǎn)執(zhí)行。

圖2 任務(wù)調(diào)度模型Fig.2 Task scheduling model

然而，智能工廠中的實(shí)時(shí)任務(wù)通常具有不同的優(yōu)先級(jí)。若直接按照固定優(yōu)先級(jí)的調(diào)度模型執(zhí)行任務(wù)，會(huì)導(dǎo)致低優(yōu)先級(jí)任務(wù)不斷被高優(yōu)先級(jí)任務(wù)阻塞而超時(shí)，必然會(huì)影響智能工廠的正常生產(chǎn)?？紤]這些情況，結(jié)合任務(wù)的固定優(yōu)先級(jí)以及執(zhí)行緊迫度，提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的任務(wù)調(diào)度模型。在霧計(jì)算層中，各個(gè)霧節(jié)點(diǎn)可以按照任務(wù)的動(dòng)態(tài)優(yōu)先級(jí)執(zhí)行等待隊(duì)列中的任務(wù)。

此外，合理的任務(wù)調(diào)度對(duì)于任何系統(tǒng)來說都非常重要[13-15]。由于每個(gè)霧節(jié)點(diǎn)具有不同的計(jì)算能力，并且每個(gè)霧節(jié)點(diǎn)的任務(wù)到達(dá)率不同，一些霧節(jié)點(diǎn)將累積大量等待執(zhí)行的任務(wù)，而另外一些霧節(jié)點(diǎn)的資源利用相對(duì)空閑。針對(duì)這種情況，提出了一種定期執(zhí)行的計(jì)算卸載策略，該策略根據(jù)每個(gè)霧節(jié)點(diǎn)的計(jì)算能力、存儲(chǔ)容量和通信容量，將各個(gè)霧節(jié)點(diǎn)等待隊(duì)列中的任務(wù)重新分配，可以充分利用霧計(jì)算層的網(wǎng)絡(luò)資源，均衡霧計(jì)算層中每個(gè)霧節(jié)點(diǎn)的負(fù)載，從而提高任務(wù)完成率、降低任務(wù)執(zhí)行時(shí)間。

因此，提出的基于動(dòng)態(tài)優(yōu)先級(jí)的實(shí)時(shí)任務(wù)調(diào)度方案的任務(wù)調(diào)度流程如圖3所示。

圖3 任務(wù)調(diào)度流程Fig.3 Task scheduling process

2.2 動(dòng)態(tài)優(yōu)先級(jí)

為了解決基于固定優(yōu)先級(jí)的任務(wù)調(diào)度模型的缺點(diǎn)，應(yīng)該考慮任務(wù)的延遲容忍屬性。目前已有許多根據(jù)任務(wù)的延遲容忍屬性決定優(yōu)先級(jí)的調(diào)度算法[16-17]。然而，這些算法卻忽略了任務(wù)本身的優(yōu)先級(jí)。因此，本文基于任務(wù)的固定優(yōu)先級(jí)和執(zhí)行緊急程度，設(shè)計(jì)了基于動(dòng)態(tài)優(yōu)先級(jí)的任務(wù)調(diào)度模型，用于等待隊(duì)列中任務(wù)的調(diào)度執(zhí)行。

分別代表任務(wù)Tk到達(dá)霧節(jié)點(diǎn)的時(shí)刻及其最大容忍時(shí)延。

集合{Fog1，F(xiàn)og2，F(xiàn)og3，…，F(xiàn)ogN}代表霧計(jì)算層中的N個(gè)霧節(jié)點(diǎn)，并且霧節(jié)點(diǎn)Fogn用向量{Cn，Sn，Pn}表示。其中，Cn代表霧節(jié)點(diǎn)Fogn的CPU計(jì)算頻率；Sn代表霧節(jié)點(diǎn)Fogn的可用存儲(chǔ)容量；Pn代表霧節(jié)點(diǎn)Fogn的傳輸發(fā)射功率。

因此，在t時(shí)刻，任務(wù)Tk在霧節(jié)點(diǎn)Fogn中的執(zhí)行緊迫度可表示為：

(1)

在t時(shí)刻，任務(wù)Tk在霧節(jié)點(diǎn)Fogn中的實(shí)時(shí)優(yōu)先級(jí)為：

(2)

式中，prmax表示所有任務(wù)的最高優(yōu)先級(jí)；p，q代表權(quán)重參數(shù)，二者用來權(quán)衡固定優(yōu)先級(jí)以及任務(wù)執(zhí)行緊迫度的重要程度。

本文考慮的是任務(wù)之間是非強(qiáng)占關(guān)系。因此，對(duì)于霧節(jié)點(diǎn)Fogn，每執(zhí)行完一個(gè)任務(wù)，會(huì)重新計(jì)算等待隊(duì)列中任務(wù)的實(shí)時(shí)優(yōu)先級(jí)Dprk，n，并且選擇其中Dprk，n最高的任務(wù)執(zhí)行。

2.3 任務(wù)卸載策略

本文用I表示2次任務(wù)卸載策略的執(zhí)行間隔，由于每次卸載時(shí)任務(wù)規(guī)模不同，因此I是動(dòng)態(tài)調(diào)整的，可以通過下式得到：

(3)

當(dāng)?shù)讦寥蝿?wù)卸載策略執(zhí)行時(shí)，假設(shè)霧計(jì)算層所有霧節(jié)點(diǎn)的等待隊(duì)列中共有K個(gè)任務(wù)，可以用集合{T1，T2，T3，…，TK}表示。并且，每個(gè)任務(wù)所在的霧節(jié)點(diǎn)用集合{l1，l2，l3，…，lK}表示，其中l(wèi)k∈{1，2，…，N}。此時(shí)，任務(wù)Tk在等待隊(duì)列中已經(jīng)等待的時(shí)間為：

(4)

式中，tα表示當(dāng)前任務(wù)卸載策略的開始時(shí)刻。

當(dāng)霧管理節(jié)點(diǎn)執(zhí)行完任務(wù)卸載策略之后，會(huì)得到每個(gè)任務(wù)的卸載決策。這里使用xk，n表示任務(wù)Tk是否被分配到霧節(jié)點(diǎn)Fogn，則：

(5)

因此，可以用集合{xk，n}表示此次卸載決策，其中k∈{1，2，…，K}，n∈{1，2，…，N}。

在任務(wù)卸載過程中，一個(gè)任務(wù)只能分配給一個(gè)霧節(jié)點(diǎn)。同時(shí)，考慮到霧節(jié)點(diǎn)的存儲(chǔ)容量限制。那么有：

(6)

(7)

此外，在任務(wù)卸載過程中，霧節(jié)點(diǎn)之間的任務(wù)卸載是需要考慮傳輸時(shí)延的。在此，將任務(wù)Tk從霧節(jié)點(diǎn)Foglk卸載到霧節(jié)點(diǎn)Fogn所需要的傳輸時(shí)延為：

(8)

式中，Translk，n表示從霧節(jié)點(diǎn)Foglk卸載到霧節(jié)點(diǎn)Fogn的所有任務(wù)組成的集合；rlk，n表示霧節(jié)點(diǎn)Foglk與霧節(jié)點(diǎn)Fogn之間的數(shù)據(jù)傳輸速率。由式(9)可得：

(9)

式中，Blk，n為霧節(jié)點(diǎn)Foglk與霧節(jié)點(diǎn)Fogn之間的信道帶寬；hlk，n為信道增益；N0為噪聲。

當(dāng)任務(wù)Tk被卸載到對(duì)應(yīng)的霧節(jié)點(diǎn)后，還需要經(jīng)歷等待與計(jì)算2個(gè)過程。這2個(gè)過程產(chǎn)生的時(shí)延為：

(10)

(11)

式中，HPtasksk，n表示在任務(wù)Tk之前執(zhí)行的任務(wù)的集合。

由式(3)～(11)可以得到，任務(wù)Tk從生成到執(zhí)行完成所需的總時(shí)延為：

(12)

由于容忍時(shí)延的約束，則有：

(13)

并且根據(jù)式(12)，可以得到所有任務(wù)執(zhí)行完成的時(shí)刻為：

(14)

此外，將任務(wù)的值定義為完成任務(wù)的固定優(yōu)先級(jí)，可以得到本次任務(wù)卸載決策獲得的總價(jià)值為：

(15)

本文的目標(biāo)是每次的任務(wù)卸載策略可以在降低任務(wù)完成時(shí)延的同時(shí)，獲得最大的卸載決策價(jià)值。任務(wù)卸載策略是一個(gè)多目標(biāo)優(yōu)化問題，在最大限度地減少任務(wù)的完成時(shí)間的同時(shí)，最大化卸載決策完成任務(wù)的總價(jià)值，該優(yōu)化問題為：

(16)

s.t.

(17)

(18)

(19)

在滿足式(17)～(19)的條件下，盡量優(yōu)化式(16)。

3 基于NSGA-II的任務(wù)卸載算法

實(shí)現(xiàn)提出的實(shí)時(shí)任務(wù)調(diào)度方案，必須要解決提出的優(yōu)化問題。由于提出的優(yōu)化問題由2個(gè)目標(biāo)函數(shù)組成，是一個(gè)典型的多目標(biāo)優(yōu)化模型，因此本文使用NSGA-II算法[18]來解決問題。

算法1 基于NSGA-II算法的任務(wù)卸載算法輸入:Fog1,Fog2,Fog3,…,FogN{}T1,T2,T3,…,TK{}l1,l2,l3,…,lK{}輸出:xk,n{},k∈1,2,…,K{},n∈1,2,…,N{}1:初始化:設(shè)置種群規(guī)模M,初始化種群Y1,最大迭代次數(shù)maxGen,交叉概率p1和變異概率p2。2:計(jì)算當(dāng)前種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值,并執(zhí)行非支配快速排序和擁擠度排序。3:fort=1:maxGendo4:通過二進(jìn)制錦標(biāo)賽法從Yt中選擇個(gè)體,并執(zhí)行交叉和變異操作以生成新一代種群Gt。5:通過將新一代種群與上一代種群合并得到組合種群Rt=Yt∪Qt。6: 對(duì)Rt進(jìn)行非支配排序,并通過擁擠度排序以及精英保留策略選擇M個(gè)個(gè)體,形成新一代種群Yt+1。7:end for8:從最終代種群YmaxGen+1選擇一個(gè)最佳個(gè)體,并得到卸載決策。9:returnxk,n{},k∈1,2,…,K{},n∈1,2,…,N{}

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

4.1 仿真場景與參數(shù)設(shè)置

采用Matlab作為實(shí)驗(yàn)平臺(tái)來評(píng)估所提出的任務(wù)調(diào)度方案的性能。在提出的基于霧計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)下，車間數(shù)量為6，每個(gè)車間有1臺(tái)服務(wù)器作為霧節(jié)點(diǎn)。霧節(jié)點(diǎn)的計(jì)算能力隨機(jī)分布在2～4 GHz，可用存儲(chǔ)容量隨機(jī)分布在10～20 GB，霧節(jié)點(diǎn)之間的傳輸速率ri，j∈[20，40]Mbps。

另外，本文考慮智能工廠中有3種優(yōu)先級(jí)任務(wù)的情況，任務(wù)參數(shù)參考文獻(xiàn)[19-20]設(shè)置，具體參數(shù)如表1所示。

表1 任務(wù)參數(shù)設(shè)置Tab.1 Task parameter settings

到達(dá)的任務(wù)流遵循泊松分布，3種任務(wù)的總到達(dá)率為λ，3種任務(wù)到達(dá)率之比為0.4∶0.25∶0.35，實(shí)驗(yàn)?zāi)M20 s的任務(wù)產(chǎn)生。在基于NSGA-II算法的任務(wù)卸載策略中，變異概率設(shè)置為0.1，交叉概率設(shè)置為0.9，種群大小為100。

為了驗(yàn)證提出的任務(wù)調(diào)度方案的性能，建立了幾組對(duì)比實(shí)驗(yàn)方案：

方案1：霧節(jié)點(diǎn)之間不進(jìn)行任務(wù)卸載，每個(gè)霧節(jié)點(diǎn)根據(jù)先到先服務(wù)的規(guī)則執(zhí)行任務(wù)。

方案2：每個(gè)霧節(jié)點(diǎn)隨機(jī)將任務(wù)卸載到其他霧節(jié)點(diǎn)，每個(gè)霧節(jié)點(diǎn)根據(jù)先到先服務(wù)的規(guī)則執(zhí)行任務(wù)。

方案3：使用提出的任務(wù)卸載策略對(duì)霧節(jié)點(diǎn)進(jìn)行任務(wù)卸載，并且每個(gè)霧節(jié)點(diǎn)根據(jù)先到先服務(wù)的規(guī)則執(zhí)行任務(wù)。

方案4：使用本文提出的任務(wù)卸載策略對(duì)霧節(jié)點(diǎn)進(jìn)行任務(wù)卸載，并且每個(gè)霧節(jié)點(diǎn)根據(jù)EDF算法[13]調(diào)度執(zhí)行任務(wù)。

本文的方案：使用提出的任務(wù)卸載策略對(duì)霧節(jié)點(diǎn)進(jìn)行任務(wù)卸載，并且每個(gè)霧節(jié)點(diǎn)根據(jù)提出的基于動(dòng)態(tài)優(yōu)先級(jí)的任務(wù)調(diào)度模型執(zhí)行任務(wù)。

4.2 仿真結(jié)果分析

圖4比較了在不同任務(wù)到達(dá)率下，5組實(shí)驗(yàn)的平均實(shí)驗(yàn)性能。仿真結(jié)果表明，提出的任務(wù)調(diào)度方案具有最佳的平均時(shí)延性能。這是由于提出的任務(wù)卸載策略充分利用了霧計(jì)算層的資源。此外，由于使用動(dòng)態(tài)優(yōu)先級(jí)模型調(diào)度任務(wù)，霧節(jié)點(diǎn)可以先執(zhí)行更高優(yōu)先級(jí)和更緊急的任務(wù)，從而減少任務(wù)的整體等待延遲。此外，可以看到，當(dāng)同時(shí)使用任務(wù)卸載策略和EDF算法(方案4)時(shí)，平均時(shí)延性能非常差。這是因?yàn)殪F節(jié)點(diǎn)僅在調(diào)度任務(wù)時(shí)考慮了任務(wù)的截止時(shí)間，導(dǎo)致低計(jì)算時(shí)延的任務(wù)請求到達(dá)霧節(jié)點(diǎn)之后，由于截止日期還早而被迫等待，因此增加了整體等待延遲。

圖4 不同任務(wù)調(diào)度方案的平均時(shí)延Fig.4 Average delay of different task scheduling schemes

圖5和圖6分別比較了在不同任務(wù)到達(dá)率下，5組實(shí)驗(yàn)完成任務(wù)的總價(jià)值和完成任務(wù)的數(shù)量。

圖5 不同任務(wù)調(diào)度方案完成任務(wù)的總價(jià)值Fig.5 Total value of tasks completed by different task scheduling schemes

圖6 不同任務(wù)調(diào)度方案完成任務(wù)的數(shù)量Fig.6 Number of tasks completed by different task scheduling schemes

可以看到，提出的任務(wù)卸載策略在完成任務(wù)的總價(jià)值方面具有最佳性能，并且完成任務(wù)數(shù)量的性能僅僅略低于方案4。這是因?yàn)镋DF算法只考慮了任務(wù)的截止日期，因此可以完成更多任務(wù)。然而，就平均延遲而言，方案4的性能非常差。因此，本文提出的任務(wù)調(diào)度方案的性能最優(yōu)。

此外，表2中的數(shù)據(jù)顯示了任務(wù)的總到達(dá)率為60的情況下，方案4和本文提出的任務(wù)調(diào)度方案的3種任務(wù)的完成數(shù)量以及完成率?？梢钥闯?，由于方案4只考慮了任務(wù)的截止日期，導(dǎo)致大量較高優(yōu)先級(jí)的任務(wù)未能執(zhí)行，不能滿足智能工廠的要求。

表2 3種任務(wù)的完成數(shù)量和完成率Tab.2 Completion quantities and rates of three tasks

圖7顯示了任務(wù)的總到達(dá)率為60的情況下，不同優(yōu)先級(jí)權(quán)重下3個(gè)任務(wù)的完成率?？梢钥闯?，當(dāng)權(quán)重p較大時(shí)，固定優(yōu)先級(jí)越高的任務(wù)的完成率越高。這是因?yàn)楫?dāng)霧節(jié)點(diǎn)執(zhí)行等待隊(duì)列的任務(wù)時(shí)，更傾向于執(zhí)行具有更高固定優(yōu)先級(jí)的任務(wù)。此外，當(dāng)權(quán)重q較大時(shí)，系統(tǒng)將更傾向于執(zhí)行具有更高執(zhí)行緊急度的任務(wù)，因此這種情況下，固定優(yōu)先級(jí)較低的任務(wù)的完成率比權(quán)重p較大時(shí)更高。通過調(diào)整權(quán)重p，q的大小，可以滿足智能工廠在不同場景下的不同要求。

圖7 不同優(yōu)先級(jí)權(quán)重下各類任務(wù)的完成率Fig.7 Completion rates of various tasks under different priority weights

5 結(jié)束語

針對(duì)于基于云計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)的缺陷，設(shè)計(jì)了一種基于霧計(jì)算的智能工廠網(wǎng)絡(luò)架構(gòu)，并在此架構(gòu)的基礎(chǔ)上，提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的實(shí)時(shí)任務(wù)調(diào)度方案。仿真結(jié)果證明了提出的網(wǎng)絡(luò)架構(gòu)以及任務(wù)調(diào)度方案可以在霧計(jì)算層資源緊張的情況下，有效地降低霧計(jì)算層執(zhí)行任務(wù)的平均時(shí)延并提高了霧計(jì)算層任務(wù)執(zhí)行的價(jià)值。