一種基于風險感知策略的多節點任務調度方法

劉 斌 趙亦玄 王 輝 楚涌泉 付 琨

①(中國科學院空天信息創新研究院 北京 100094)

②(中國科學院大學 北京 100049)

③(中國科學院大學電子電氣與通信工程學院 北京 100094)

④(中國科學院網絡信息體系技術重點實驗室 北京 100094)

⑤(首都師范大學信息工程學院 北京 100048)

⑥(北京航空航天大學軟件開發環境國家重點實驗室 北京 100191)

⑦(中科邊緣智慧 北京 100190)

1 引言

隨著無線通信技術的不斷進步，越來越多的文獻開始研究關于集群網絡中節點容錯處理方法[1]及節點容錯調度[2]，由無人機組成的分布式集群具有設備數量多、計算任務復雜、多源設備協作的特點[3]，可執行勘探、檢測等數據處理的工作。集群中的每個無人機(Unmanned Aerial Vehicle, UAV)都被視為一個具有計算能力的節點，實現數字化信息的快速處理。但在復雜的真實環境下，任何計算節點(無人機)不僅面臨著自身任務處理能力有限，還可能出現網絡帶寬受限等問題[4]。一般地，資源不充裕的節點會將本地計算任務卸載[5]到資源充足的計算節點[6]，然而這會導致目標節點上正在執行的計算任務的中斷，給目標集群帶來一定風險。同時整個集群還需要承擔無人機節點隨機接入或離開時產生的網絡波動。

在現有工作中，研究者在解決分布式集群中任務計算與處理的問題時，普遍從節點資源利用率和任務處理時延的角度入手，將問題轉化為分布式任務分配與調度的問題。IBM研究中心和帝國理工大學的研究將資源分配和任務調度問題建模為一個馬爾可夫決策過程[7]，為了減少狀態空間，進一步將該問題轉化為兩個具有分割的狀態空間的獨立的馬爾可夫決策過程，并利用李雅普諾夫優化技術設計了一個代價最優的在線算法。研究針對無線城域網下Cloudlet集群的負載均衡問題，澳大利亞國立大學[8]給出的算法理念是：首先求取各任務的平均響應時間，然后決定每個Cloudlet需要分配多少任務到其他Cloudlet中。賓夕法尼亞州立大學[9]的研究指出目前多數模型將用戶服務請求(或應用程序)當作專用資源片，其獲得的計算、通信和存儲資源都是不可共享的，并且指出存儲資源不可共享的假設不適用于數據分析服務，如虛擬現實等，這些服務通常有部分存儲資源是可以共享的；該研究針對聯合服務放置和請求調度問題建立線性規劃模型，首次將通信資源和計算資源加入約束條件，并將同類型服務的存儲資源設定為可共享的，將優化目標設為最大服務用戶數，并給出了線性時間解的算法。佐治亞理工學院[10]提出了Femtoclouds框架，這是一種將邊緣集群設備轉化為Cloudlet的邊緣計算框架，用于處理來源于集群中或集群外的計算任務；Femtoclouds根據關鍵路徑將其拆分成多個路徑依賴的子任務，然后結合風險控制機制依照執行時間小的優先策略將子任務分配到邊緣設備上；在邊緣設備內部，基于各隊列中任務已執行時間為指標，對各隊列中的任務進行公平調度，并加入截止時間優化策略，優先處理接近截止時間的任務。上述工作的主要思想都是嘗試將計算任務劃分為細粒度的多個任務組件，再根據任務的資源需求特性、實時的網絡連接狀態等因素，動態地在計算終端之間進行任務的調度，通過多方算力間的協同工作來實現應用的分布式執行，但類似的解決方案尚無法滿足無人機集群所面臨的場景。由于單個節點(無人機)的機動性高且不穩定，整個網絡對可處理節點波動變化的容錯能力的要求越來越高[11]。

綜上所述，有效降低計算節點(無人機)的處理任務時間，將計算任務合理高效地在每個計算節點間動態調度以加快任務處理與反饋，同時還要保障集群網絡執行任務調度過程中可對節點的高度動態性和不穩定性做出容錯處理成為本文研究重點。為解決上述問題，本文提出一種新穎的計算任務調度策略，充分考慮了任務的時效性，同時為機動計算節點設計了容錯機制可以更好地應用于復雜環境。主要研究成果如下：(1)針對任務的執行要求和節點的資源狀況選擇合適的優化目標組合，并研究基于多目標優化方法的任務調度策略以盡量滿足這些優化目標。(2)針對多節點情況下因節點失效或離開等導致任務中斷的情況，研究任務調度的錯誤處理機制和容錯機制。錯誤處理機制用于確保任務的完整執行，監控任務在傳輸過程或執行過程的具體運行情況，當任務執行失敗中斷后重新調度并重新執行。

2 面向多節點協同計算的任務調度方法

2.1 多節點環境下協同計算任務調度框架

本文提出的調度框架的執行過程可總結為以下步驟：(1)用戶提交任務后，任務加入調度器的等待隊列。(2)預測器對任務進行分析，提供任務在各計算節點上的預計執行時間。(3)控制器根據各計算節點的實時資源信息和網絡信息作出任務分配決策。(4)任務追蹤器對需要進行計算卸載的任務，向對應的計算節點上的任務調度接收服務發起計算卸載。(5)任務追蹤器在計算節點上監控各任務的執行情況，并進行錯誤處理，如：對被中斷的任務重新發起調度和卸載執行過程。框架示意圖如圖1所示。

圖1 任務調度框架示意圖

2.2 產生概率分布和預測值的方法

在上述任務調度框架中，預測器負責產生任務分配決策所需各變量的預估值。預測器包含1個任務預測單元集合和1個節點預測單元集合。每個任務預測單元為1個或1組具有類似軟硬件配置的節點，負責維護已執行任務的時間分布信息。類似地，節點預測單元為1個或1組具有類似網絡環境的節點，負責記錄和預估存留時間信息。

本文采用一種黑盒方法[12]來為每個任務產生概率分布和預測值。該方法假設大部分任務與先前所有任務的某個子集類似，且類似任務有相似的執行時間。該方法不需要獲取任務的結構信息或用戶預先提供的信息，但需要每個任務的屬性集合。本文選用3個屬性：提交任務的鏡像名、任務的CPU需求和任務的內存需求。對于每個屬性-鍵值對，該方法通過直方圖跟蹤所有具有相同屬性和值的任務的執行時間并生成一個經驗分布。每個屬性-鍵值對在直方圖中由算法進行預估，數值類型包括：平均值、中值、衰減率為0.5的移動平均值以及最近20個任務的平均值。同時在每次預估時維護4個點估計方法的歸一化平均絕對誤差(Normalized Mean Absolute Error, NMAE)。當預估一個帶有若干屬性任務的執行時間時，從所有屬性-鍵值對應的直方圖中比較所有點的估計值的NMAE，選擇最低NMAE對應的點估計值和執行時間分布。此外，本方法使用一個直方圖以跟蹤所有任務的執行時間，用于預估平均任務執行時間。根據以上原理，每個任務預測單元為1個或1組服務節點維護其任務執行時間的分布。同理，每個節點預測單元為1組服務節點維護其存留時間的分布，但并不用區分多種屬性維護存留時間的分布。

本方法采用一種基于流的直方圖算法以構建直方圖[13]。1個直方圖是1個鍵值對的集合，作為1個實數集合的近似代表，表示為{(v1,f1),(v2,f2),...,(vB,fB)}。 對于每對(vi,fi),1≤i ≤B,vi表示1個數字的值，fi表示該數字的頻數。1個直方圖在生成時規定最大鍵數量B，當新加入某個數值而導致直方圖總鍵數超過規定數量時，歸并數值最近的兩個鍵值對。

本方法定義了概率直方圖的概念，表示為{(v1,p1),(v2,p2),...,(vB,pB)}。 對于每對(vi,pi),1≤i ≤B,vi表 示一個數字的值，pi表示該數字的概率。因此，概率直方圖是一個概率分布的近似代表。本方法新增兩個算法用以將直方圖轉換為概率直方圖，如表1和表2所示。

表1 右移和概率轉換過程(算法1)

表2 從給定值開始概率轉換過程(算法2)

算法1首先根據1個位移值對1個直方圖進行右移操作，然后將給直方圖轉換成概率直方圖。算法2首先在某個直方圖中根據某個給定值，過濾掉小于該值的點，然后將剩余的直方圖轉換為概率直方圖。本方法所述任務調度策略中各種時間值的概率分布的關系如圖2所示。

圖2 各時間值概率分布的關系

預測器從任務預測單元獲取任務的執行時間的概率分布，并在計算任務的傳輸時間和等待時間后，使用算法1可以獲得任務完成時間的概率分布和預測值。類似地，從節點預測單元獲取存留時間的概率分布，在計算該節點的已存留時間后，使用算法2可以獲得節點剩余存留時間的概率分布。

在可擴展性方面，本方法主要使用3種設計以減少內存占用。首先，基于流的直方圖算法使用歸并方法控制其最大支持的鍵數量，其本身的設計能夠使用固定大小的內存來維護1個任意鍵值對數量的直方圖。其次，每個任務預測單元不必僅為單個服務節點維護1個執行時間直方圖，可同時對應一群軟硬件配置相似的節點。最后，每個節點預測單元為1群網絡環境相似(比如在同一接入點范圍內)的節點維護1個存留時間直方圖，而不僅是單個節點。

2.3 風險感知的多節點計算任務調度策略

2.3.1 最小化平均完成時間的任務分配策略

本文整體看待任務集中的所有任務，構建最小化任務平均完成時間的策略，將該任務分配問題構建為0-1整數線性規劃問題如式(4)所示

在遺傳算法的選擇過程中，本文選用輪盤賭方法。在交叉過程中，選用標準的單點交叉操作子。在變異過程中，選用實值變異方法，設定變異比例為30%。每個染色體中的選中任務被隨機分配給可選的計算節點。本文設定染色體數量為30%，迭代次數為500。

2.3.2 風險感知的魯棒任務分配策略

本文選用一種直方圖算法[15]分類記錄每個已完畢任務的運行時間及其頻率分布，并采用了多評估方法預估某個任務的運行時間，認為應該使用某個時間變量的概率分布，而非該變量的一個單點估計值(如平均值和中值等)。本文將節點的預計存留時間和節點在當前集群中已度過的時間兩者差值定義為節點的剩余存留時間。當將一個任務分配至一個計算節點時，假設該計算節點的剩余存留時間為一個隨機變量RPT，其概率分布率為式(7)

然而任務中斷概率并不能準確反映該中斷的潛在時間開銷。對于不同的計算節點，在具有相同的任務中斷概率的同時可能具有不同的存留時間，任務在中斷時已運行的時間也不一定相同。因此，應該從時間值的角度來比較分配的優劣， 而不單是任務中斷概率。

由于每次任務分配決策是相互獨立的，故在量化單次任務中斷的時間開銷時假設任務的第2次執行必然完成。又假設任務在重新調度時也被分配至一個軟硬件配置相似的計算節點，即第2次正常運行時間與第1次正常運行時間相同。基于以上假設，則定義在任務中斷風險下的期望完成時間為隨機變量TCT, 其定義為

在求解該規劃問題的優化過程中，為了獲取最小代價，一方面需要為每一個任務最小化額外開銷時間，另一方面從總體上最小化任務的平均完成時間。從任務分配過程看，調度器將為每個任務盡量分配計算力強且風險小的計算節點。

以上策略的一個關鍵點是任務中斷風險的時間量化，而非僅僅獲知中斷概率。假如貪婪地保證中斷概率盡量小而不考慮完成時間的對比，那么會將多個任務分配至一個穩定的計算節點，導致該計算節點的負載不均衡，反而增加任務的等待時間，且從整體上看，任務的平均完成時間會增大。故任務的正常完成時間和額外開銷時間應當同時考慮。

在求解算法上，可以沿用上述遺傳算法。其中規劃問題的總代價更新為

3 實驗及結果分析

3.1 硬件配置

本文使用若干移動設備搭建了一個測試床。其中，使用一部臺式計算機作為本地節點，該計算機配置有Intel(R) Core(TM) i5-8400的CPU和16 GB的內存。使用包括Surface Pro 4(M3)，樹莓派3B+和樹莓派4B 3種類型移動設備作為計算節點。各設備的硬件配置參見表3。各設備通過WiFi相互連接。

表3 計算節點硬件配置

本文同時設置模擬實驗以評估在大量計算節點下各策略的任務分配性能，并驗證不同的參數配置對任務分配性能的影響。模擬實驗使用模擬計算節點，模擬計算節點與真實的計算節點的區別在于，該計算節點軟件運行在同一臺式計算機，而非移動設備。本文使用均勻分布 U(8 Mbit/s, 80 Mbit/s)為每個模擬計算節點生成帶寬值，并使用一個sleep函數模擬任務的傳輸過程。

本文使用泊松過程來模擬計算節點的到達規律，并使用正態分布生成每個移動設備在集群中的存留時間。其中，正態分布的方差設置為均值的10%。

3.2 對比基準策略

本文將上述容錯機制加入調度策略中，提出一種具有容錯能力的動態節點任務調度方法(Dynamic Node of Task Assignment, DN-TA)，將與以下算法策略作對比。

(1)最短完成時間優先(Shortest Completion Time First, SCTF)：貪婪地將任務分配至能有最小完成時間的計算節點。

(2)最小化批量完成時間(Minimize Batch Completion Time, MBCT)：即最小化平均完成時間的任務分配策略。

(3)在現有相關工作Femtocloud中使用的啟發式算法。對于每一個任務，該算法首先根據節點的任務中斷頻率遞增排序。然后將首個節點設為最佳節點，并迭代地按序與余下每一個節點對比兩個指標。一個指標是候選節點與最佳節點的相對節省時間，另一個是候選節點與最佳節點的相對增加風險。假如相對節省時間超過相對增加風險，則將該候選節點設置為最佳節點。

在以上3個算法策略中，前兩個策略都默認任務的運行過程是無風險的。后者則考慮了任務中斷風險，但其僅僅考慮任務中斷概率，并沒有量化任務中斷帶來的額外開銷時間，但相同的任務中斷概率可能對應不同的額外開銷時間。

3.3 性能指標

對于沒有截止時間限制的任務，本文使用平均完成時間和平均任務執行次數來評估任務分配性能。對于帶有截止時間限制的任務，本文使用截止時間錯失率來評估任務分配性能。這些指標的定義如下所示。

(1)平均完成時間(average completion time)：該指標計算所有已完成任務的完成時間的平均值。

(2)平均任務執行次數(average number of executions)：該指標計算所有已完成任務的平均執行次數。該指標直接反映了任務分配策略選擇低風險節點的能力，即避免任務中斷的能力。

(3)截止時間錯失率(deadline miss ratio)：該指標統計所有未能在截止時間前完成的任務所占的百分比。

3.4 仿真實驗與分析

(1)測試床實驗。在測試床實驗方面，由于實驗設備數目較少，不使用泊松過程模擬計算節點的到達過程。當一個計算節點離開時，該節點在一段空閑時間后重新加入集群。使用正態分布生成該空閑時間的長度，該分布的均值等于節點平均存留時間的20%，標準差為均值的10%。因此，每個計算節點在集群的存留時間占比為80%。任務到達率設為每分鐘10個任務。實驗的參數設置如表4所示。各任務分配策略在測試床實驗的性能對比結果如圖3所示。

圖3 測試床實驗結果

表4 測試床參數設置

本文所提出的策略DN-TA具有最短的平均完成時間和最低的截止時間錯失率，并和Femtocloud獲得相近的平均任務執行次數。從任務中斷風險避免的性能看，DN-TA和Femtocloud兩個考慮任務中斷風險的策略相比不考慮的兩個策略獲得更小的平均任務執行次數。然而，盡管DN-TA和Femtocloud具有差不多的平均任務執行次數，但卻具有最短的平均完成時間和更低的截止時間錯失率。這一方面反映了DN-TA的最小化平均完成時間的策略的有效性，另一方面反映了Femtocloud在優先確保較小的任務中斷風險時，未能同時考慮最小化部分任務的完成時間。

(2)模擬實驗。在模擬實驗中，本文研究一些參數配置(比如任務到達速率，計算節點的平均存留時間等)在任務分配性能上對各任務分配策略的影響。改變這些參數，可以改變集群的整體計算能力和工作負載，從而改變任務中斷風險的大小。在模擬實驗中，各參數的默認值如表5所示。

表5 默認參數設置

(a) 任務到達速率的影響分析。任務到達速率直接影響了集群的工作負載量和各計算節點等待隊列的長度。等待隊列長度越長，則在隊列尾部的任務的中斷風險越高。因此任務到達速率越高，任務中斷風險也越高。研究改變任務到達速率對任務分配性能的影響的實驗結果如圖4所示。

圖4 任務到達速率的影響

總體上，平均完成時間、平均任務執行次數、截止時間錯失率3個指標值都隨著任務到達速率的增大而增大。在大部分情況下DN-TA具有最短的平均完成時間和最低的截止時間缺失率。與同樣最小化平均完成時間的策略MBCT相比，當任務到達速率較低時，DN-TA 具有近似的平均完成時間。但當任務到達速率較高時(大于150 任務/min)，DNTA具有更短的平均完成時間和更低的截止時間缺失率，表明在任務中斷風險較高時，DN-TA的風險感知機制的有效性。與Femtocloud相比，盡管Femtocloud有更低的平均任務執行次數，但DNTA卻具有更低的平均任務完成時間。這表明DNTA在更可靠的執行和更短的執行時間兩者的權衡中表現更好，因其量化了中斷風險的額外時間開銷，可以直接比較潛在的額外開銷時間和因選擇更短無風險完成時間而節省的時間，以預估中斷風險下期望最短完成時間。

(b) 計算節點到達速率的影響分析。計算節點到達速率直接影響了集群中計算節點的數量，更多的計算節點能承擔更多工作負載，減少等待隊列長度，提供更穩定的運行環境，減少任務中斷風險。研究改變計算節點到達速率對任務分配性能的影響的實驗結果如圖5所示。

圖5 計算節點到達速率的影響

總體上，所有指標隨著到達速率增大而降低。當到達速率大于4 節點/min時，DN-TA和Femtcloud具有差不多的平均任務執行次數，但DN-TA有更短的平均完成時間和更低的截止時間缺失率，表明DN-TA能更好地衡量更可靠的執行和更短的執行時間。與MBCT相比，DN-TA有差不多的平均完成時間但有更低的截止時間缺失率。這表明MBCT的各任務的完成時間有更大的方差，在部分任務的分配決策中，因總是選擇最短的無風險完成時間反而增加因任務中斷導致的額外開銷時間。當到達率為2節點/min時，所有策略的截止時間缺失率都很高且差距不大，說明此時工作負載十分繁重，也說明了在負載十分繁重的情況下，考慮風險感知并無幫助。

(c) 計算節點異構性的影響分析。該模擬實驗目的在于驗證任務分配策略是否能充分利用具有更高計算能力但卻有更短的平均存留時間的計算節點。本文在保持原有的節點的同時，新加入一組模擬節點。這些節點運行在一臺性能更強的配置有Intel(R) Core(TM) i7-8700的 CPU和6 GB內存的臺式機上。研究改變異構節點的到達速率對任務分配性能的影響的實驗結果如圖6所示。

圖6 計算節點異構性的影響

總體上，所有指標都隨著異構節點到達速率增大而減小。相比其他策略，Femtocloud能很好地保持較低的平均任務執行次數，因該策略優先保障任務更可靠執行。而DN-TA傾向于使用能具有更短完成時間的節點，盡管此時的任務風險增大。

(d) 計算節點平均存留時間的影響分析。計算節點的平均存留時間直接影響了任務中斷風險。在此實驗中，為了在改變平均存留時間的前提下，保持整體集群中計算節點的可用性，采用與測試床實驗一樣的實驗方法。每個計算節點在退出集群后，在一段時候后重新加入集群。本文將每個節點的可用時間占比保持在80%。研究改變計算節點平均存留時間對任務分配性能的影響的實驗結果如圖7所示，其中+∞表示節點在實驗過程從不退出集群。

圖7 計算節點平均存留時間的影響

DN-TA和Femtocloud在3個指標上都優于其余兩個不考慮任務分配風險的策略。從截止時間缺失率看，除平均存留時間為+∞時的其余情況下，工作負載偏重。此時，盡管 Femtocloud有更低的平均任務執行次數，但其平均完成時間與DN-TA差不多。表明了此時任務中斷帶來的額外的開銷時間與選擇更短無風險完成時間而節省下來的時間基本相等。

4 結束語

在實際的多計算節點間任務調度執行過程中，不同的任務調度策略將導致不同的任務響應時延，甚至出現節點并不滿足任務資源的需要導致任務延誤乃至失敗的情況。針對這一問題，本文圍繞實際情況，研究多計算節點的任務調度方法，根據卸載任務的具體需求以及機動計算節點的動態狀態信息進行實時調度，使得計算任務能夠分布式進行，實現縮短任務的平均響應時間等目標。本文提出的DNTA策略使調度方法具有容錯性，同時基于多目標優化的任務調度算法使整個調度流程提升了效率。