一種面向霧計算的任務調度算法研究*

劉林東，鄔依林

廣東第二師范學院計算機學院，廣東廣州 510303

計算密集型應用和資源受限型設備之間的矛盾［1-3］已成為霧計算中提供滿意體驗的瓶頸，需要通過任務調度來解決此問題。霧計算［4］相對于傳統(tǒng)的分布式計算和云計算［5］，由數量眾多的位置分布的霧結點和終端設備構成，一般由計算性能有限的設備組成，包括路由器、交換機、網關和終端設備等［1，6-8］。由于帶寬以及能耗因素影響，性能異構的物聯網［9-12］設備（IOT） 得到的數據可以邊緣設備上進行計算、分析和調度，從而可以減輕云端的負擔。

現有的霧計算任務調度研究［13］，一般根據資源利用率、時間、能耗、成本、負載均衡等優(yōu)化目標進行資源分配或任務分配。文獻［14］ 提出了一種面向霧計算的多用戶小區(qū)聚類資源優(yōu)化策略，該策略以最大交付時延作為衡量服務質量的重要指標；文獻［15］ 通過定義計算延遲以及通信延遲模型的方法，為霧計算結點的任務調度提供依據；文獻［16］ 通過邊緣計算和云計算之間的協作，達到功耗以及傳輸延遲間的負載平衡；文獻［17］ 提出了一種啟發(fā)式任務調度算法，達到調度跨度以及調度成本間的平衡。霧計算任務調度是一個NP完全問題［1，18］。

文中對獨立任務流水線任務調度問題進行研究，通過改進的分類挖掘算法建立霧計算任務調度模型以及相應的調度算法，以任務調度跨度和平均等待時間作為主要優(yōu)化目標，從而提升霧計算用戶服務質量以及任務調度吞吐量。

1 霧計算模型

霧計算由前端層、霧層以及云層三層架構構成［19］，如圖1 所示。前端層作為用戶接口，一般由各種類型的物聯網設備組成，向霧層發(fā)送任務請求；霧層包括m個異構的霧結點，向霧層發(fā)送任務請求，霧層離前端層很近，一方面用戶可以直接利用霧層中的計算資源，另一方面，也可以減輕云層的計算壓力；部署了多臺服務器或者云結點的云層，相比較霧層計算能力更強，由于物理上遠離前端層，用戶請求一般不直接發(fā)送至云層。

圖1 霧計算系統(tǒng)架構Fig. 1 System architecture of fog computing

2 I-Apriori分類挖掘算法

2.1 算法描述

經典Apriori算法［20-21］每次迭代產生頻繁項集都需要去掃描事務數據庫D，由于掃描數據庫次數過多，造成生成頻繁項集的算法效率較低。為改進經典Apriori算法效率低下的問題，提出一種分類挖掘I-Apriori算法。I-Apriori算法包括兩個階段。第一步：產生頻繁1項集L1，獲取每個項集的事務標識TID，產生候選集1 項集C1，利用最小支持度閾值得到L1；第二步：生成頻繁項集L. 當Lk-1不為空時循環(huán)進行后面幾項操作，1） 候選k項集Ck直接通過Lk-1的自連接運算得到；2） 利用候選k項集Ck直接得到項集計數；3） 基于最小支持度閾值刪除候選k項集Ck中不滿足條件項集，得到頻繁k項集Lk. 循環(huán)結束后最終得到頻繁項集L. 算法描述如算法1所示。

算法1：I-Apriori算法

1 產生候選1項集C1；

2 統(tǒng)計事務D中TID的數量count；

3 循環(huán)對C1中每個項集s｛

4s. item-set=s；

5C1中s的數量s. count；

6 產生所有包含項集s的TID列表

7 如果s. count＜min_sup*count

8 刪除C1中的s；

9 ｝

10k=1；Lk=Ck，；

11 while （Lk-1≠?）｛

12 循環(huán)對Lk-1中的每個項集l1｛

13 循環(huán)對Lk-1中的每個項集l2｛

14 對l1和l2進行連接；

15 直接統(tǒng)計c. tid-list；

16 直接統(tǒng)計c. count；

17 ｝

18 ｝

19 如果c. count大于最小支持度計數｛

20 把c添加Ck中；

21Lk=Ck；｝

22 ｝

2.2 算法分析

利用Java 分別實現經典Apriori 算法和I-Apriori 算法，基于Intel Core（TM）i5-8265U 1. 6 GHz CPU、8 GB內存的硬件環(huán)境以及Win10系統(tǒng)生成頻繁項集。

在最小置信度為0. 6 的實驗條件下，通過對比50～500 個事務數下產生頻繁項集的執(zhí)行時間。圖2（a）為最小支持度計數為0. 40的情況下兩種算法時間開銷對比情況；圖2（b）為最小支持度計數為0. 45的情況下兩種算法的時間開銷對比情況。通過實驗得出，I-Apriori算法在兩種不同最小支持度下的時間開銷均小于經典Apriori 算法的時間開銷，最小支持度為0. 40 的情況性能提升了8. 1%～34. 4%，在最小支持度為0. 45的情況性能提升了7. 6%～37. 0%；總體上I-Apriori具有更好的性能。

圖2 兩種算法在不同最小支持度下執(zhí)行時間對比Fig. 2 Comparison of execution time of two algorithms under different minimum support

設Apriori 算法中事務數為n，項目數為m，頻繁項集迭代數為k， 則算法時間復雜度為O（k4·m·n）；I-Apriori算法的時間復雜度為O（m+n+k3），I-Apriori時間復雜度性能更優(yōu)。

3 霧計算中任務調度

3.1 任務調度模型

針對霧計算環(huán)境中獨立任務流水線任務調度問題，將I-Apriori 算法融入到任務調度過程中。霧計算任務調度模型如圖3 所示，任務調度模型包括霧結點集F、任務集T、事務集D、調度關系R以及I-Apriori 和ITPS兩種算法，在F和T間實現資源分配和任務調度。任務調度的過程是一個迭代更新的過程，每次迭代的基本流程首先利用I-Apriori算法對歷史調度事務集D進行分類挖掘，得到F與T間的調度規(guī)則，然后利用ITPS算法讀取調度規(guī)則，得到F與T間的調用關系R，并循環(huán)將R更新到D中。

圖3 霧計算中任務調度模型Fig. 3 Task scheduling model of fog computing

3.2 ITPS調度算法

ITPS任務調度算法（詳見算法2） 主要包括3個步驟：

1） 任務選擇。循環(huán)選擇任務集中的任務，首先選擇到達時間ATi最早的任務，若兩個以上任務同時到達，則優(yōu)先選擇調度關系R中的任務；若任務到達時間均不相同，算出全部任務在霧計算資源上的最早完成時間，依據最早完成時間和加權鏈接數的從小到大進行調度；

2） 霧計算結點選擇。選擇最早完成時間最小的霧計算結點進行任務調度；

3） 任務調度。在霧結點上完成任務的執(zhí)行，得出任務執(zhí)行時間等調度數據，直到所有任務被調度完成為止。

3.3 調度過程

通過一個完整的任務調度案例分析ITPS 算法的調度過程，任務調度過程包括任務初始化、初始事務集、I-Apriori算法、任務調用關系以及ITPS算法調度等幾個步驟。

3.3.1 任務初始化設任務集T中包含10（n=10）個獨立流水線任務，每個任務ti（0≤i≤9）的到達時間如表1所示，其中t0，t2和t5，t3和t4的到達時間相同；霧計算結點集F中包括4（m=4）個性能異構的計算結點Fj（0≤j≤3），任務ti在霧計算結點Fj上的執(zhí)行開銷如表2 所示，執(zhí)行開銷滿足一致性模型條件，即任務ti如果在霧計算結點Fj上的執(zhí)行開銷比霧計算結點Fk上的執(zhí)行開銷短，則任何其他任務也是如此。

表1 任務到達時間Table 1 Arrival time of task ms

表2 任務集在處理機集上的執(zhí)行開銷矩陣Table 2 Execution time of task set on fog node set ms

3.3.2 初始事務集初始事務集是任務集T中的任務ti與霧計算結點集F的結點Fj之間的調度關系的集合，事務集中每一條記錄為每一次任務調度的信息，“1” 表示任務ti以及霧計算結點Fj出現在某條事務Tz中，“0” 表示事務Tz不包含任務ti以及霧計算結點Fj，設事務集中包含10（z=10）條事務，初始事務集D如表3所示。

表3 事務集Table 3 Transaction set

3.3.3 I-Apriori算法

1） 產生頻繁項集。基于初始事務集D執(zhí)行I-Apriori算法，以最小支持度0. 5為例，得到｛F1，F0，F3，t2｝

算法2：ITPS算法

輸入：Time［n，m］，R［t，c］，任務集TS

輸出：任務調度跨度makespan，任務平均等待時間AWT

1 針對任務集｛ //循環(huán)對每個任務集進行調度

2 針對每個任務｛

3 針對每個霧計算結點｛

4 計算EFT［］；

5 ｝

6 查找具有最小最早完成時間的任務tj；

7 計算任務開始時間ST［］；

8 按EFT［］值對任務進行排序；

9 ｝

10 當任務集非空｛

11 針對霧計算結點

12 計算加權最小鏈接nwc［］；

13 若多個任務同時到達

14 選擇調度關系R中的任務

15 否則

16 選擇最早完成時間EFT［］最小的任務ti；

17 選擇任務ti最早完成時間EFT ［i］ 最小的霧計算結點Fj上調度；

18 計算任務調度時間WT；

19 更ST［］和FT［］；

20 任務降序排列；

21 ｝

22 計算并輸出makespan以及AWT；

23｝

以及｛F2，F0，F3，t3｝兩個頻繁項集；

2） 產生關聯規(guī)則。設最小置信度為0. 7，利用生成的頻繁項集，得到兩個關聯規(guī)則，分別為t2?F1∨F0∨F2，t3?F2∨F0∨F3.

3.3.4 任務調用關系根據I-Apriori 算法得出的兩個關聯規(guī)則，生成對應的任務調度關系。任務調用關系是任務集T中的任務ti與霧計算結點集F中的結點Fj之間的強關系的集合，即出現在任務調度關系中的任務ti優(yōu)先被調度。ti和Fj存在3種關系：①若ti與Fj未出現在關聯規(guī)則中，則ti行對應的值全部為0，其中t0，t1，t4，t5，t6，t7，t8，t9與Fj未出現在關聯規(guī)則中；②若ti與Fj出現在關聯規(guī)則中，則計算任務ti在霧計算結點Fj上的置信度，t2在F0，F1，F2上的置信度分別為0. 33，0. 37和0. 30，t3在F0，F1，F2，F3上的置信度分別為0. 33，0，0. 35 和0. 32；③沒有出現在關聯規(guī)則中的霧計算結點，對應的位置值為-1，F3未出現在t2中。

3.3.5 ITPS算法調度利用ITPS算法進行任務調度，以表1～2和任務調用關系作為輸入，輸出任務集任務調度跨度makespan以及平均等待時間AWT。

以任務集｛t0，t1，t2，t7｝作為調度對象，由于任務t1最早到達，所以先對任務t1進行調度，選擇最早完成時間最小的霧計算結點F2進行調度；接下來選擇任務t0和t2，由于t0，t2任務同時到達，且任務t2出現在關聯關系R中，因此任務t2被優(yōu)先調度，然后選擇最早完成時間最小的霧計算結點F0進行調度；任務集中還有任務t0和t7未被調度，由于任務t0早于任務t7到達，因此選擇任務t0在F1上調度；最后再將任務t7調度到F3，得到任務集｛t0，t1，t2，t7｝與霧計算結點集｛F0，F1，F2，F3｝的調度關系如圖4所示。

圖4 任務與霧計算結點之間調度關系圖Fig. 4 Scheduling relationship between tasks and fog computing nodes

4 模擬結果與結果分析

為了驗證ITPS算法的性能和效率，搭建基于SimGrid［22-24］模擬器工具包的仿真實驗環(huán)境。實驗環(huán)境中霧計算結點間通過高速網絡連接，霧計算結點的計算性能異構，霧計算結點進行任務調度的同時也可以與其他霧計算結點進行通信，獨立流水線任務分配到霧計算結點上執(zhí)行直到任務執(zhí)行完成。

實驗中使用的計算機配置：Intel Core（TM）i5-8265U 1. 6 GHz CPU、4 GB 內存硬件環(huán)境、Ubuntu12操作系統(tǒng)以及SimGrid3. 11工具包，在相同實驗條件對ITPS算法以及wLC和wRR算法進行性能比較。

4.1 測試數據集

為測試各種算法的性能，需要給定任務調度算法的測試數據集，包括任務集、霧結點集、任務執(zhí)行開銷矩陣、事務集以及調度關系等。任務測試集中的任務數從50開始，每次遞增50個任務，最大到1 000個任務，任務集中的任務與任務編號通過隨機程序生成，任務集中每個任務的到達時間通過隨機程序生成；霧結點測試數據集包括4個性能異構的結點；任務集在霧結點集上的執(zhí)行開銷通過隨機程序生成；調度關系由I-Apriori算法根據初始事務集D得到；初始事務測試集由500個隨機生成的事務構成。

4.2 實驗結果分析

利用測試數據集，分別執(zhí)行ITPS、wLC 以及wRR 任務調度算法，對不同任務數及不同任務到達時間對任務集進行調度，任務到達時間區(qū)間為［0，50］的調度情況，以及任務到達時間區(qū)間為［0，100］的調度情況圖5所示。

圖5 不同任務數性能對比Fig. 5 Performance comparison of different tasks

通過上述實驗可以得到，ITPS 算法在不同任務數以及不同任務到達時間條件下，任務調度跨度和平均等待時間均比wLC 和wRR 算法要短，而wRR 算法的性能總體上要優(yōu)于wLC 算法。ITPS算法相比wLC 算法的任務調度跨度縮短2. 48%～10. 62%，平均等待時間AWT 值縮短14. 97%～49. 79%，任務越晚到達，IPTS 的性能更優(yōu)；ITPS 算法相比wRR 算法的任務調度跨度縮短2. 19%～11. 78%，平均等待時間AWT 值縮短4. 55%～20. 53%，任務越早到達，IPTS 的性能更佳，總體上ITPS 算法要優(yōu)于wLC 和wRR 兩種任務調度算法。

5 結 語

通過對經典Apriori算法的改進，提出一種霧計算環(huán)境中任務的分類I-Apriori算法，I-Apriori算法提升了分類挖掘的效率和性能；利用I-Apriori 算法，面向霧計算環(huán)境下的任務調度問題，建立霧計算任務調度模型，并提出ITPS任務調度算法。ITPS算法在makespan及AWT具有更好的性能。