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

①(中國(guó)科學(xué)院空天信息創(chuàng)新研究院 北京 100094)

②(中國(guó)科學(xué)院大學(xué) 北京 100049)

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

④(中國(guó)科學(xué)院網(wǎng)絡(luò)信息體系技術(shù)重點(diǎn)實(shí)驗(yàn)室 北京 100094)

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

⑥(北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100191)

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

1 引言

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

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

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

2 面向多節(jié)點(diǎn)協(xié)同計(jì)算的任務(wù)調(diào)度方法

2.1 多節(jié)點(diǎn)環(huán)境下協(xié)同計(jì)算任務(wù)調(diào)度框架

本文提出的調(diào)度框架的執(zhí)行過程可總結(jié)為以下步驟：(1)用戶提交任務(wù)后，任務(wù)加入調(diào)度器的等待隊(duì)列。(2)預(yù)測(cè)器對(duì)任務(wù)進(jìn)行分析，提供任務(wù)在各計(jì)算節(jié)點(diǎn)上的預(yù)計(jì)執(zhí)行時(shí)間。(3)控制器根據(jù)各計(jì)算節(jié)點(diǎn)的實(shí)時(shí)資源信息和網(wǎng)絡(luò)信息作出任務(wù)分配決策。(4)任務(wù)追蹤器對(duì)需要進(jìn)行計(jì)算卸載的任務(wù)，向?qū)?yīng)的計(jì)算節(jié)點(diǎn)上的任務(wù)調(diào)度接收服務(wù)發(fā)起計(jì)算卸載。(5)任務(wù)追蹤器在計(jì)算節(jié)點(diǎn)上監(jiān)控各任務(wù)的執(zhí)行情況，并進(jìn)行錯(cuò)誤處理，如：對(duì)被中斷的任務(wù)重新發(fā)起調(diào)度和卸載執(zhí)行過程?？蚣苁疽鈭D如圖1所示。

圖1 任務(wù)調(diào)度框架示意圖

2.2 產(chǎn)生概率分布和預(yù)測(cè)值的方法

在上述任務(wù)調(diào)度框架中，預(yù)測(cè)器負(fù)責(zé)產(chǎn)生任務(wù)分配決策所需各變量的預(yù)估值。預(yù)測(cè)器包含1個(gè)任務(wù)預(yù)測(cè)單元集合和1個(gè)節(jié)點(diǎn)預(yù)測(cè)單元集合。每個(gè)任務(wù)預(yù)測(cè)單元為1個(gè)或1組具有類似軟硬件配置的節(jié)點(diǎn)，負(fù)責(zé)維護(hù)已執(zhí)行任務(wù)的時(shí)間分布信息。類似地，節(jié)點(diǎn)預(yù)測(cè)單元為1個(gè)或1組具有類似網(wǎng)絡(luò)環(huán)境的節(jié)點(diǎn)，負(fù)責(zé)記錄和預(yù)估存留時(shí)間信息。

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

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

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

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

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

算法1首先根據(jù)1個(gè)位移值對(duì)1個(gè)直方圖進(jìn)行右移操作，然后將給直方圖轉(zhuǎn)換成概率直方圖。算法2首先在某個(gè)直方圖中根據(jù)某個(gè)給定值，過濾掉小于該值的點(diǎn)，然后將剩余的直方圖轉(zhuǎn)換為概率直方圖。本方法所述任務(wù)調(diào)度策略中各種時(shí)間值的概率分布的關(guān)系如圖2所示。

圖2 各時(shí)間值概率分布的關(guān)系

預(yù)測(cè)器從任務(wù)預(yù)測(cè)單元獲取任務(wù)的執(zhí)行時(shí)間的概率分布，并在計(jì)算任務(wù)的傳輸時(shí)間和等待時(shí)間后，使用算法1可以獲得任務(wù)完成時(shí)間的概率分布和預(yù)測(cè)值。類似地，從節(jié)點(diǎn)預(yù)測(cè)單元獲取存留時(shí)間的概率分布，在計(jì)算該節(jié)點(diǎn)的已存留時(shí)間后，使用算法2可以獲得節(jié)點(diǎn)剩余存留時(shí)間的概率分布。

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

2.3 風(fēng)險(xiǎn)感知的多節(jié)點(diǎn)計(jì)算任務(wù)調(diào)度策略

2.3.1 最小化平均完成時(shí)間的任務(wù)分配策略

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

在遺傳算法的選擇過程中，本文選用輪盤賭方法。在交叉過程中，選用標(biāo)準(zhǔn)的單點(diǎn)交叉操作子。在變異過程中，選用實(shí)值變異方法，設(shè)定變異比例為30%。每個(gè)染色體中的選中任務(wù)被隨機(jī)分配給可選的計(jì)算節(jié)點(diǎn)。本文設(shè)定染色體數(shù)量為30%，迭代次數(shù)為500。

2.3.2 風(fēng)險(xiǎn)感知的魯棒任務(wù)分配策略

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

然而任務(wù)中斷概率并不能準(zhǔn)確反映該中斷的潛在時(shí)間開銷。對(duì)于不同的計(jì)算節(jié)點(diǎn)，在具有相同的任務(wù)中斷概率的同時(shí)可能具有不同的存留時(shí)間，任務(wù)在中斷時(shí)已運(yùn)行的時(shí)間也不一定相同。因此，應(yīng)該從時(shí)間值的角度來比較分配的優(yōu)劣， 而不單是任務(wù)中斷概率。

由于每次任務(wù)分配決策是相互獨(dú)立的，故在量化單次任務(wù)中斷的時(shí)間開銷時(shí)假設(shè)任務(wù)的第2次執(zhí)行必然完成。又假設(shè)任務(wù)在重新調(diào)度時(shí)也被分配至一個(gè)軟硬件配置相似的計(jì)算節(jié)點(diǎn)，即第2次正常運(yùn)行時(shí)間與第1次正常運(yùn)行時(shí)間相同?；谝陨霞僭O(shè)，則定義在任務(wù)中斷風(fēng)險(xiǎn)下的期望完成時(shí)間為隨機(jī)變量TCT, 其定義為

在求解該規(guī)劃問題的優(yōu)化過程中，為了獲取最小代價(jià)，一方面需要為每一個(gè)任務(wù)最小化額外開銷時(shí)間，另一方面從總體上最小化任務(wù)的平均完成時(shí)間。從任務(wù)分配過程看，調(diào)度器將為每個(gè)任務(wù)盡量分配計(jì)算力強(qiáng)且風(fēng)險(xiǎn)小的計(jì)算節(jié)點(diǎn)。

以上策略的一個(gè)關(guān)鍵點(diǎn)是任務(wù)中斷風(fēng)險(xiǎn)的時(shí)間量化，而非僅僅獲知中斷概率。假如貪婪地保證中斷概率盡量小而不考慮完成時(shí)間的對(duì)比，那么會(huì)將多個(gè)任務(wù)分配至一個(gè)穩(wěn)定的計(jì)算節(jié)點(diǎn)，導(dǎo)致該計(jì)算節(jié)點(diǎn)的負(fù)載不均衡，反而增加任務(wù)的等待時(shí)間，且從整體上看，任務(wù)的平均完成時(shí)間會(huì)增大。故任務(wù)的正常完成時(shí)間和額外開銷時(shí)間應(yīng)當(dāng)同時(shí)考慮。

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

3 實(shí)驗(yàn)及結(jié)果分析

3.1 硬件配置

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

表3 計(jì)算節(jié)點(diǎn)硬件配置

本文同時(shí)設(shè)置模擬實(shí)驗(yàn)以評(píng)估在大量計(jì)算節(jié)點(diǎn)下各策略的任務(wù)分配性能，并驗(yàn)證不同的參數(shù)配置對(duì)任務(wù)分配性能的影響。模擬實(shí)驗(yàn)使用模擬計(jì)算節(jié)點(diǎn)，模擬計(jì)算節(jié)點(diǎn)與真實(shí)的計(jì)算節(jié)點(diǎn)的區(qū)別在于，該計(jì)算節(jié)點(diǎn)軟件運(yùn)行在同一臺(tái)式計(jì)算機(jī)，而非移動(dòng)設(shè)備。本文使用均勻分布 U(8 Mbit/s, 80 Mbit/s)為每個(gè)模擬計(jì)算節(jié)點(diǎn)生成帶寬值，并使用一個(gè)sleep函數(shù)模擬任務(wù)的傳輸過程。

本文使用泊松過程來模擬計(jì)算節(jié)點(diǎn)的到達(dá)規(guī)律，并使用正態(tài)分布生成每個(gè)移動(dòng)設(shè)備在集群中的存留時(shí)間。其中，正態(tài)分布的方差設(shè)置為均值的10%。

3.2 對(duì)比基準(zhǔn)策略

本文將上述容錯(cuò)機(jī)制加入調(diào)度策略中，提出一種具有容錯(cuò)能力的動(dòng)態(tài)節(jié)點(diǎn)任務(wù)調(diào)度方法(Dynamic Node of Task Assignment, DN-TA)，將與以下算法策略作對(duì)比。

(1)最短完成時(shí)間優(yōu)先(Shortest Completion Time First, SCTF)：貪婪地將任務(wù)分配至能有最小完成時(shí)間的計(jì)算節(jié)點(diǎn)。

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

(3)在現(xiàn)有相關(guān)工作Femtocloud中使用的啟發(fā)式算法。對(duì)于每一個(gè)任務(wù)，該算法首先根據(jù)節(jié)點(diǎn)的任務(wù)中斷頻率遞增排序。然后將首個(gè)節(jié)點(diǎn)設(shè)為最佳節(jié)點(diǎn)，并迭代地按序與余下每一個(gè)節(jié)點(diǎn)對(duì)比兩個(gè)指標(biāo)。一個(gè)指標(biāo)是候選節(jié)點(diǎn)與最佳節(jié)點(diǎn)的相對(duì)節(jié)省時(shí)間，另一個(gè)是候選節(jié)點(diǎn)與最佳節(jié)點(diǎn)的相對(duì)增加風(fēng)險(xiǎn)。假如相對(duì)節(jié)省時(shí)間超過相對(duì)增加風(fēng)險(xiǎn)，則將該候選節(jié)點(diǎn)設(shè)置為最佳節(jié)點(diǎn)。

在以上3個(gè)算法策略中，前兩個(gè)策略都默認(rèn)任務(wù)的運(yùn)行過程是無風(fēng)險(xiǎn)的。后者則考慮了任務(wù)中斷風(fēng)險(xiǎn)，但其僅僅考慮任務(wù)中斷概率，并沒有量化任務(wù)中斷帶來的額外開銷時(shí)間，但相同的任務(wù)中斷概率可能對(duì)應(yīng)不同的額外開銷時(shí)間。

3.3 性能指標(biāo)

對(duì)于沒有截止時(shí)間限制的任務(wù)，本文使用平均完成時(shí)間和平均任務(wù)執(zhí)行次數(shù)來評(píng)估任務(wù)分配性能。對(duì)于帶有截止時(shí)間限制的任務(wù)，本文使用截止時(shí)間錯(cuò)失率來評(píng)估任務(wù)分配性能。這些指標(biāo)的定義如下所示。

(1)平均完成時(shí)間(average completion time)：該指標(biāo)計(jì)算所有已完成任務(wù)的完成時(shí)間的平均值。

(2)平均任務(wù)執(zhí)行次數(shù)(average number of executions)：該指標(biāo)計(jì)算所有已完成任務(wù)的平均執(zhí)行次數(shù)。該指標(biāo)直接反映了任務(wù)分配策略選擇低風(fēng)險(xiǎn)節(jié)點(diǎn)的能力，即避免任務(wù)中斷的能力。

(3)截止時(shí)間錯(cuò)失率(deadline miss ratio)：該指標(biāo)統(tǒng)計(jì)所有未能在截止時(shí)間前完成的任務(wù)所占的百分比。

3.4 仿真實(shí)驗(yàn)與分析

(1)測(cè)試床實(shí)驗(yàn)。在測(cè)試床實(shí)驗(yàn)方面，由于實(shí)驗(yàn)設(shè)備數(shù)目較少，不使用泊松過程模擬計(jì)算節(jié)點(diǎn)的到達(dá)過程。當(dāng)一個(gè)計(jì)算節(jié)點(diǎn)離開時(shí)，該節(jié)點(diǎn)在一段空閑時(shí)間后重新加入集群。使用正態(tài)分布生成該空閑時(shí)間的長(zhǎng)度，該分布的均值等于節(jié)點(diǎn)平均存留時(shí)間的20%，標(biāo)準(zhǔn)差為均值的10%。因此，每個(gè)計(jì)算節(jié)點(diǎn)在集群的存留時(shí)間占比為80%。任務(wù)到達(dá)率設(shè)為每分鐘10個(gè)任務(wù)。實(shí)驗(yàn)的參數(shù)設(shè)置如表4所示。各任務(wù)分配策略在測(cè)試床實(shí)驗(yàn)的性能對(duì)比結(jié)果如圖3所示。

圖3 測(cè)試床實(shí)驗(yàn)結(jié)果

表4 測(cè)試床參數(shù)設(shè)置

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

(2)模擬實(shí)驗(yàn)。在模擬實(shí)驗(yàn)中，本文研究一些參數(shù)配置(比如任務(wù)到達(dá)速率，計(jì)算節(jié)點(diǎn)的平均存留時(shí)間等)在任務(wù)分配性能上對(duì)各任務(wù)分配策略的影響。改變這些參數(shù)，可以改變集群的整體計(jì)算能力和工作負(fù)載，從而改變?nèi)蝿?wù)中斷風(fēng)險(xiǎn)的大小。在模擬實(shí)驗(yàn)中，各參數(shù)的默認(rèn)值如表5所示。

表5 默認(rèn)參數(shù)設(shè)置

(a) 任務(wù)到達(dá)速率的影響分析。任務(wù)到達(dá)速率直接影響了集群的工作負(fù)載量和各計(jì)算節(jié)點(diǎn)等待隊(duì)列的長(zhǎng)度。等待隊(duì)列長(zhǎng)度越長(zhǎng)，則在隊(duì)列尾部的任務(wù)的中斷風(fēng)險(xiǎn)越高。因此任務(wù)到達(dá)速率越高，任務(wù)中斷風(fēng)險(xiǎn)也越高。研究改變?nèi)蝿?wù)到達(dá)速率對(duì)任務(wù)分配性能的影響的實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 任務(wù)到達(dá)速率的影響

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

(b) 計(jì)算節(jié)點(diǎn)到達(dá)速率的影響分析。計(jì)算節(jié)點(diǎn)到達(dá)速率直接影響了集群中計(jì)算節(jié)點(diǎn)的數(shù)量，更多的計(jì)算節(jié)點(diǎn)能承擔(dān)更多工作負(fù)載，減少等待隊(duì)列長(zhǎng)度，提供更穩(wěn)定的運(yùn)行環(huán)境，減少任務(wù)中斷風(fēng)險(xiǎn)。研究改變計(jì)算節(jié)點(diǎn)到達(dá)速率對(duì)任務(wù)分配性能的影響的實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 計(jì)算節(jié)點(diǎn)到達(dá)速率的影響

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

(c) 計(jì)算節(jié)點(diǎn)異構(gòu)性的影響分析。該模擬實(shí)驗(yàn)?zāi)康脑谟隍?yàn)證任務(wù)分配策略是否能充分利用具有更高計(jì)算能力但卻有更短的平均存留時(shí)間的計(jì)算節(jié)點(diǎn)。本文在保持原有的節(jié)點(diǎn)的同時(shí)，新加入一組模擬節(jié)點(diǎn)。這些節(jié)點(diǎn)運(yùn)行在一臺(tái)性能更強(qiáng)的配置有Intel(R) Core(TM) i7-8700的 CPU和6 GB內(nèi)存的臺(tái)式機(jī)上。研究改變異構(gòu)節(jié)點(diǎn)的到達(dá)速率對(duì)任務(wù)分配性能的影響的實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 計(jì)算節(jié)點(diǎn)異構(gòu)性的影響

總體上，所有指標(biāo)都隨著異構(gòu)節(jié)點(diǎn)到達(dá)速率增大而減小。相比其他策略，F(xiàn)emtocloud能很好地保持較低的平均任務(wù)執(zhí)行次數(shù)，因該策略優(yōu)先保障任務(wù)更可靠執(zhí)行。而DN-TA傾向于使用能具有更短完成時(shí)間的節(jié)點(diǎn)，盡管此時(shí)的任務(wù)風(fēng)險(xiǎn)增大。

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

圖7 計(jì)算節(jié)點(diǎn)平均存留時(shí)間的影響

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

4 結(jié)束語

在實(shí)際的多計(jì)算節(jié)點(diǎn)間任務(wù)調(diào)度執(zhí)行過程中，不同的任務(wù)調(diào)度策略將導(dǎo)致不同的任務(wù)響應(yīng)時(shí)延，甚至出現(xiàn)節(jié)點(diǎn)并不滿足任務(wù)資源的需要導(dǎo)致任務(wù)延誤乃至失敗的情況。針對(duì)這一問題，本文圍繞實(shí)際情況，研究多計(jì)算節(jié)點(diǎn)的任務(wù)調(diào)度方法，根據(jù)卸載任務(wù)的具體需求以及機(jī)動(dòng)計(jì)算節(jié)點(diǎn)的動(dòng)態(tài)狀態(tài)信息進(jìn)行實(shí)時(shí)調(diào)度，使得計(jì)算任務(wù)能夠分布式進(jìn)行，實(shí)現(xiàn)縮短任務(wù)的平均響應(yīng)時(shí)間等目標(biāo)。本文提出的DNTA策略使調(diào)度方法具有容錯(cuò)性，同時(shí)基于多目標(biāo)優(yōu)化的任務(wù)調(diào)度算法使整個(gè)調(diào)度流程提升了效率。