基于移動邊緣計算的混合分布式任務容錯調度方法*

陳 剛 王志堅 徐勝超

（廣州華商學院數(shù)據(jù)科學學院 廣州 511300）

1 引言

移動邊緣計算［1～2］以及物聯(lián)網(wǎng)等技術的高速發(fā)展，異構分布式系統(tǒng)被廣泛的應用到飛機控制、核電站控制等各項高端系統(tǒng)中。這些系統(tǒng)在執(zhí)行任務時都存在實時性，因此若任務不能在規(guī)定時間內完成，會給整個系統(tǒng)帶來災難性打擊。為保障系統(tǒng)任務在出現(xiàn)故障后，仍能在任務時效范圍內完成任務，需要分布式系統(tǒng)［3～4］具備容錯力。因此移動邊緣計算中的任務調度也成了近年來國內外學者的重點關注與研究的問題。

文獻［5］研究了一種基于綜合匹配度的邊緣計算系統(tǒng)任務調度方法，針對邊緣計算系統(tǒng)資源異構且受限的特性，研究邊緣任務與目標設備資源深度匹配的有效方法，設計了基于任務資源匹配、負載均衡和任務公平性的綜合匹配度評估方法，并設計基于網(wǎng)絡流的在線多任務調度算法，時限任務調度，但是該方法由于調度環(huán)境較差，導致調度時延較高的問題。

文獻［6］研究了社會屬性感知的邊緣計算任務調度策略，根據(jù)服務器的負載分布情況衡量整個網(wǎng)絡的負載均衡度，結合強化學習方法為任務匹配合適的邊緣服務器，進而構造任務時延和終端發(fā)射功率的映射關系來滿足物理域的約束，結合終端用戶屬性，為任務不斷地選擇合適的中繼終端，通過終端輔助調度的方式實現(xiàn)任務調度，但是該方法的約束條件構建較差，導致調度精度低。

文獻［7］研究了面向優(yōu)先級用戶的移動邊緣計算任務調度策略，該算法根據(jù)任務的處理價值及任務的數(shù)據(jù)量，計算任務的優(yōu)先級，結合任務截止時間、服務器調度次數(shù)，制定資源匹配方案，解決了邊緣網(wǎng)絡中服務器為不同優(yōu)先級的用戶進行計算資源分配的問題，實現(xiàn)了任務調度，但是該方法由于匹配精度低，并且調度環(huán)境差，導致任務調度時的容錯成功率低。

移動邊緣計算可以有效構建平穩(wěn)的調度環(huán)境，因此，為解決上述任務任務調度方法中存在的問題，提出基于移動邊緣計算的混合分布式任務容錯調度方法。并且在此基礎上，結合了任務容錯調度模型，優(yōu)化了任務容錯調度方法，實現(xiàn)任務容錯調度，以期提高任務調度效率。

2 建立任務容錯模型

在對混合分布式任務開展容錯調度前，需要建立相對安全的移動邊緣計算環(huán)境，構建混合分布式任務的容錯調度模型。

2.1 基于邊緣計算的調度環(huán)境

容錯技術是指混合分布式系統(tǒng)在硬件、軟件故障的情況下仍然能正確的執(zhí)行任務，其本質就是冗余，因此系統(tǒng)任務容錯調度是系統(tǒng)的冗余容錯技術。該技術包括信息冗余、時間冗余、冗余附加。

信息冗余是指系統(tǒng)為達到糾正信息的目的，加入外部信息。采用冗余碼制式糾正信息。時間冗余主要是通過重復的執(zhí)行命令來消減瞬時錯誤影響。執(zhí)行過程為從系統(tǒng)源地址出發(fā)，經(jīng)過處理器處理，送至目的節(jié)點，該執(zhí)行過程成功，則執(zhí)行下一個任務指令，反之則復執(zhí)不成功。冗余附加是上述技術的保障，包括關鍵程序信息的冗余存儲和調用、系統(tǒng)檢測、切換、糾錯等預處理。

系統(tǒng)任務在容錯調度時，系統(tǒng)狀態(tài)較為復雜，并且需要處理大量的信息，同時，容錯技術存在時延長的局限性，因此，在容錯技術的基礎上，需要引入移動邊緣計算，構建一個穩(wěn)定的容錯調度環(huán)境的同時，處理調度任務數(shù)據(jù)，降低時延，提高調度精度。

移動邊緣計算是Intel、IBM等企業(yè)制定的電信標準。主要負責用戶周邊的IT服務環(huán)境，從而避免系統(tǒng)故障出現(xiàn)計算瓶頸。因此在開展混合分布式任務容錯調度前，需要依據(jù)移動邊緣計算構建安全平穩(wěn)的容錯調度環(huán)境。

移動邊緣計算架構于混合分布式系統(tǒng)與用戶移動設備之間，從而衍生出三層層次結構。移動邊緣計算采用任務卸載方式增強終端的設備性能，保障混合分布式系統(tǒng)及時完成任務。移動邊緣計算體系具體結構如圖1所示。

圖1 移動邊緣計算體系結構圖

構建移動邊緣計算環(huán)境的關鍵點是通過云計算在混合式系統(tǒng)邊緣、網(wǎng)絡以及移動網(wǎng)絡邊緣，為用戶提供計算，保障數(shù)據(jù)的敏感以及延遲敏感的應用。

依據(jù)圖1可知，移動邊緣計算體系結構由四分部分組成，分別為終端、邊緣網(wǎng)絡、核心網(wǎng)絡和云計算。終端主要由傳感器、手機等物聯(lián)網(wǎng)設備組成，主要作用是采集數(shù)據(jù)并上報。邊緣計算部分主要由邊緣網(wǎng)絡節(jié)點構成，分布在邊緣網(wǎng)絡模塊中，邊緣計算層包含多個邊緣網(wǎng)絡服務器，通過合理部署和調配網(wǎng)絡邊緣側的計算和存儲能力，實現(xiàn)任務調度的基礎服務響應。核心網(wǎng)絡由移動網(wǎng)絡構成，即主干網(wǎng)，其是在主要連接點之間建立的通信網(wǎng)絡。云計算部分是混合式分布系統(tǒng)組成，其是數(shù)據(jù)處理中心，并且存儲邊緣計算傳輸?shù)臄?shù)據(jù)，主要處理的內容是邊緣計算未分析處理的任務。

通過上述可知，移動邊緣計算體系將移動網(wǎng)絡、邊緣計算和云計算等相結合，即結合了邊緣計算、移動計算等，構建了一個云、邊、端的任務調度環(huán)境，它可以更加穩(wěn)定網(wǎng)絡環(huán)境，還可以通過邊緣計算模塊處理任務的容錯調度數(shù)據(jù)，保障了系統(tǒng)任務的容錯調度精準性。

2.2 構建混合分布式任務容錯調度模型

混合分布式系統(tǒng)是由若干有線寬帶網(wǎng)絡互聯(lián)形成的處理器構成，運行時需要控制多個回路，且每個回路以固定頻率運行，從而實現(xiàn)數(shù)據(jù)采集、運算、控制輸出等任務。由于任務之間互相影響，因此在控制過程中需要不同的處理器實施處理。

設定混合分布式控制系統(tǒng)的處理器［8～9］集合為C，獲取處理器cij的處理能力執(zhí)行速度，過程如下式所示：

式中，標準處理器執(zhí)行時間表述成S()nor形式，在cij上的執(zhí)行時間描述成S()cij形式，處理器處理能力系數(shù)標記δ。

由于系統(tǒng)在任務處理時，任務之間存在獨立主版本以及副板本，在不同的處理器上運行。因此，混合分布式系統(tǒng)在運行時若出現(xiàn)故障，通常先是主版本故障，再是副版本，所以需采用集成電路技術（Integrated Circuit，IC）決定任務主、副版本的控制?；诖耍嬎闾幚砥髌骄寐蔖i計算過程如下式所示［10］：

式中，處理器數(shù)量標記N形式，i表示任務，任務i的實時回路任務用ηi表述，T表示執(zhí)行周期。

最后依據(jù)上述制定的各項約束條件，建立混合分布式任務容錯調度模型，結果如下式所示：

式中，φ表示處理器執(zhí)行時間系數(shù)，混合分布式任務容錯調度模型用β描述。依據(jù)上述容錯調度模型［11～12］，確定任務執(zhí)行時的系統(tǒng)錯誤類型。

3 任務容錯調度

為達到容錯目的，將任務分配在不同的處理器上，系統(tǒng)執(zhí)行任務時，通過主版本執(zhí)行任務，執(zhí)行過程若未發(fā)生故障，版本持續(xù)運行直至任務結束，若主版本發(fā)生故障，直接將任務調整至副版本投入運行。依據(jù)上述建立的混合分布式任務容錯調度模型，將混合分布式任務容錯調度分為任務分配以及處理器局部調度兩個部分。為實現(xiàn)容錯，需使任務在容錯調度時，滿足如下條件：

1）確定任務滿足?ηi∈Tφ·dp+φ·db≤ηi·Pi，主版本處理器標記dp形式，副版本用db表述，規(guī)避任務在主版本因故障執(zhí)行失敗后，副版本能夠有足夠的時間調度執(zhí)行任務。

2）系統(tǒng)實時任務ηi執(zhí)行主副版本需安置在不同的處理器上，且執(zhí)行過程不重疊。

3）保證主副處理器之間的通信時間，忽略處理器消息傳遞時間。

通過搶占式EDF（Earliest Deadline First）調度算法［13］對調度單處理器，調度過程當主版本時限為φ·dp≤ηi·(Pi-db)時，說明處理器未發(fā)生故障，但是任務同樣未能執(zhí)行，此時副版本處理任務。

設定任務集R在處理器集上C上的調度條件

混合式分布系統(tǒng)執(zhí)行任務時，發(fā)生故障時處理器cij要同時執(zhí)行主、副兩個版本任務?；谏鲜龇治鼋Y果，可使用貝克分析方法建立處理cij的任務可調度條件，過程如下式所示：

式中，tj表示第j個處理器的執(zhí)行時間，Pj表示第j個處理器的利用率。由于系統(tǒng)在執(zhí)行容錯調度時，主版本與副版本的任務時限需要小于計算出的采樣周期，因此需要對獲取的調度條件［14～15］更新優(yōu)化，過程如下式所示：

式中，t'表示副版本執(zhí)行時限。依據(jù)上述更新后調度條件，依據(jù)，獲取任務執(zhí)行時最小處理器數(shù)量，通過任務分配算法分配任務，通過分配結果，實現(xiàn)任務的容錯調度，過程如下：

步驟1：在模型中輸入任務的執(zhí)行時間、最小處理器數(shù)量，對模型中任務周期等參數(shù)初始化處理。

步驟2：辨識模型中最小處理器數(shù)量是否大于制定的相關約束條件。

步驟3：依據(jù)升序方式排列系統(tǒng)任務，依據(jù)上述獲取的滿足條件對任務分配處理。

步驟4：當任務ηi在分配的處理器中出現(xiàn)故障，依據(jù)制定的容錯調度條件，對任務容錯調度處理，依據(jù)處理結果，實現(xiàn)混合分布式系統(tǒng)的任務容錯調度。

4 實驗與性能分析

4.1 實驗方案

為了驗證上述移動邊緣計算下的任務容錯調度方法的整體有效性，需要測試設計方法的性能。設計整體實驗方案，準備實驗，明確研究對象，說明實驗參數(shù)，這是實驗的基礎。在完成實驗準備后，分型設計方法的性能，任務在開展容錯調度時，容錯調度方法的調度性能是檢測容錯調度方法優(yōu)劣的關鍵，依據(jù)任務容錯調度時任務的延時程度、調度精度以及容錯成功率檢測結果。根據(jù)上述實驗方案進行實驗分析。

4.2 實驗準備

實驗以某企業(yè)的混合分布式系統(tǒng)為研究對象，在該系統(tǒng)上應用所提方法。該企業(yè)系統(tǒng)的日任務調度規(guī)模在15G左右，隨機選取1000Mb的任務調度數(shù)據(jù)，并且在是實驗時，設置6個錯誤發(fā)生時間點，分別為0.2、0.4、0.6、0.8、1.0和1.2。具體實驗參數(shù)如表1所示。

表1 任務容錯調度實驗參數(shù)

實驗環(huán)境網(wǎng)絡包含一個云服務器、多個邊緣網(wǎng)絡服務器，兩個RSU節(jié)點，n個任務節(jié)點，任務節(jié)點數(shù)量n≥1，使用Tra CI移動模型的SUMO模型放置的多個任務調度節(jié)點。在實驗中，云服務器、多個邊緣網(wǎng)絡服務器的位置固定，每個任務節(jié)點與云服務器以及邊緣服務器彼此之間都是獨立的，任務節(jié)點在與云服務器、邊緣服務器進行信息傳輸交互過程互不影響。在實驗過程中允許的數(shù)據(jù)包大小即隊列容量上限為256 bytes。

4.3 性能分析

分別采用基于移動邊緣計算的混合分布式任務容錯調度方法（本文方法）、社會屬性感知的邊緣計算任務調度策略（文獻［6］方法）、面向優(yōu)先級用戶的移動邊緣計算任務調度策略（文獻［7］方法）測試。

1）任務容錯調度的延遲程度測試

將任務調度延遲為調度效果測試指標，任務調度延時結果越大，說明調度效果越差，反之則越好。選取所提方法、文獻［6］方法以及文獻［7］方法開展任務容錯調度時，測試上述3種方法的任務調度延遲程度，結果如表2所示。

表2 不同方法的任務調度延遲測試結果

分析表2實驗數(shù)據(jù)可知，隨著調度規(guī)模的增加，3種方法測試出的調度延遲結果均出現(xiàn)不同程度的上升趨勢。其中，本文方法在開展任務容錯調度時，測試出的調度延時是3種方法中最小的，證明本文方法在任務容錯調度時的延時較短，調度效果好。

2）任務調度精度測試

任務調度規(guī)模是在相關約束條件下，將滿足調度條件的任務分配到相應處理器上，可作為調度精度的辨別指標。

采用本文方法、文獻［6］方法以及文獻［7］方法開展任務容錯調度時，測試上述3種方法的任務調度規(guī)模，測試結果如圖2所示。

分析圖2實驗數(shù)據(jù)可知，任務調度規(guī)模的大小會影響調度方法的調度精度。其中，本文方法在開展任務容錯調度時，所受的影響低于其他兩種方法，在任務調度規(guī)模達到600Mb時，本文方法的任務容錯調度精度為88.9%，文獻［6～7］方法的調度精度分別為64.8%和52.9%，本文方法比文獻方法高了24.1%和36.0%，因此，本文方法有效提高了任務容錯調度精度。這主要是因為本文方法在開展任務容錯調度前，建立了基于移動邊緣計算的任務調度環(huán)境，從而有效地提升了任務的調度精度。

圖2 不同方法的任務調度精度測試結果

3）容錯成功率測試

容錯成功率是指系統(tǒng)在任務執(zhí)行時，任務容許的失誤幾率。任務容錯調度時，保證一定的容錯成功率，能夠有效增加調度的可靠性。

采用本文方法、文獻［6］方法以及文獻［7］方法開展任務容錯調度時，測試上述3種方法任務調度時的容錯成功率，測試結果如圖3所示。

圖3 不同方法的任務調度容錯成功率測試結果

分析圖3可知，在任務容錯調度過程中，任務執(zhí)行時執(zhí)行前期的容錯成功率會高于任務執(zhí)行后期。本文方法測試出的容錯成功率明顯高于文獻

［6］方法以及文獻［7］方法，在時間點為1.2時，本文方法的容錯成功率為90.8%，文獻方法容錯成功率分別為73.1%和61.2%，相比本文方法分別低了17.7%和29.6%，因此，說明所提方法在任務容錯調度時，具備有效性。

綜上所述，本文方法在任務容錯調度時，調度延遲低、調度精度高、容錯成功率大，證明本文方法在任務容錯調度時，調度性能好。

5 結語

隨著混合分布式系統(tǒng)使用范圍的增加，混合分布式任務容錯調度就變得尤為重要。針對傳統(tǒng)容錯調度方法中存在的問題，提出基于移動邊緣計算的混合分布式任務容錯調度方法。該方法依據(jù)相關約束條件建立系統(tǒng)的任務容錯調度模型，基于建立的模型以及制定的容錯調度條件，完成混合分布式現(xiàn)任務的容錯調度。本文方法的調度延遲僅為1.27s，調度精度提高了24.1%和36.0%，調度容錯成功率提高了17.7%和29.6%，由此可知，本文方法具備可行性和有效性，其應用價值更高。在未來的工作中，需要針對調度條件，深入優(yōu)化調度方法。