基于霧計算的智能工廠實時任務調度架構

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

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

0 引言

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

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

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

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

1 網絡架構

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

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

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

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

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

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

2 實時任務調度方案

2.1 調度流程

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

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

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

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

因此，提出的基于動態優先級的實時任務調度方案的任務調度流程如圖3所示。

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

2.2 動態優先級

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

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

集合{Fog1，Fog2，Fog3，…，FogN}代表霧計算層中的N個霧節點，并且霧節點Fogn用向量{Cn，Sn，Pn}表示。其中，Cn代表霧節點Fogn的CPU計算頻率；Sn代表霧節點Fogn的可用存儲容量；Pn代表霧節點Fogn的傳輸發射功率。

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

(1)

在t時刻，任務Tk在霧節點Fogn中的實時優先級為：

(2)

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

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

2.3 任務卸載策略

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

(3)

當第α任務卸載策略執行時，假設霧計算層所有霧節點的等待隊列中共有K個任務，可以用集合{T1，T2，T3，…，TK}表示。并且，每個任務所在的霧節點用集合{l1，l2，l3，…，lK}表示，其中lk∈{1，2，…，N}。此時，任務Tk在等待隊列中已經等待的時間為：

(4)

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

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

(5)

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

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

(6)

(7)

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

(8)

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

(9)

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

當任務Tk被卸載到對應的霧節點后，還需要經歷等待與計算2個過程。這2個過程產生的時延為：

(10)

(11)

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

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

(12)

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

(13)

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

(14)

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

(15)

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

(16)

s.t.

(17)

(18)

(19)

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

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

實現提出的實時任務調度方案，必須要解決提出的優化問題。由于提出的優化問題由2個目標函數組成，是一個典型的多目標優化模型，因此本文使用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:初始化:設置種群規模M,初始化種群Y1,最大迭代次數maxGen,交叉概率p1和變異概率p2。2:計算當前種群中每個個體的適應度函數值,并執行非支配快速排序和擁擠度排序。3:fort=1:maxGendo4:通過二進制錦標賽法從Yt中選擇個體,并執行交叉和變異操作以生成新一代種群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 仿真場景與參數設置

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

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

表1 任務參數設置Tab.1 Task parameter settings

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

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

方案1：霧節點之間不進行任務卸載，每個霧節點根據先到先服務的規則執行任務。

方案2：每個霧節點隨機將任務卸載到其他霧節點，每個霧節點根據先到先服務的規則執行任務。

方案3：使用提出的任務卸載策略對霧節點進行任務卸載，并且每個霧節點根據先到先服務的規則執行任務。

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

本文的方案：使用提出的任務卸載策略對霧節點進行任務卸載，并且每個霧節點根據提出的基于動態優先級的任務調度模型執行任務。

4.2 仿真結果分析

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

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

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

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

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

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

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

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

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

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

5 結束語

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