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

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

0 引言

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

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

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

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

1 網(wǎng)絡架構

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

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

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

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

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

因此，霧計算層負責處理實時的、時延敏感的計算任務，而云計算層負責處理大規(guī)模的、非實時的計算任務。由于霧計算層資源相比于云計算層相對匱乏，因此需要有一個高效的任務調度方案對霧計算的資源進行調度。

2 實時任務調度方案

2.1 調度流程

霧計算層的任務調度模型如圖2所示。在智能工廠中，每個霧節(jié)點接收其對應車間中智能設備的任務請求。任務請求到達霧節(jié)點之后，將被放入任務等待隊列中等待霧節(jié)點執(zhí)行。

圖2 任務調度模型Fig.2 Task scheduling model

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

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

因此，提出的基于動態(tài)優(yōu)先級的實時任務調度方案的任務調度流程如圖3所示。

圖3 任務調度流程Fig.3 Task scheduling process

2.2 動態(tài)優(yōu)先級

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

分別代表任務Tk到達霧節(jié)點的時刻及其最大容忍時延。

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

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

(1)

在t時刻，任務Tk在霧節(jié)點Fogn中的實時優(yōu)先級為：

(2)

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

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

2.3 任務卸載策略

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

(3)

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

(4)

式中，tα表示當前任務卸載策略的開始時刻。

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

(5)

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

在任務卸載過程中，一個任務只能分配給一個霧節(jié)點。同時，考慮到霧節(jié)點的存儲容量限制。那么有：

(6)

(7)

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

(8)

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

(9)

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

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

(10)

(11)

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

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

(12)

由于容忍時延的約束，則有：

(13)

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

(14)

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

(15)

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

(16)

s.t.

(17)

(18)

(19)

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

3 基于NSGA-II的任務卸載算法

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

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

4 仿真實驗

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

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

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

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

到達的任務流遵循泊松分布，3種任務的總到達率為λ，3種任務到達率之比為0.4∶0.25∶0.35，實驗模擬20 s的任務產(chǎn)生。在基于NSGA-II算法的任務卸載策略中，變異概率設置為0.1，交叉概率設置為0.9，種群大小為100。

為了驗證提出的任務調度方案的性能，建立了幾組對比實驗方案：

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

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

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

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

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

4.2 仿真結果分析

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

圖4 不同任務調度方案的平均時延Fig.4 Average delay of different task scheduling schemes

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

圖5 不同任務調度方案完成任務的總價值Fig.5 Total value of tasks completed by different task scheduling schemes

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

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

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

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

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

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

5 結束語

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