VEC中基于動態(tài)優(yōu)先級的搶占式任務調(diào)度方法

賈夢欣,范艷芳,宋志文,陳若愚,蔡英

(北京信息科技大學 計算機學院,北京 100101)

0 引言

隨著網(wǎng)絡技術(shù)的不斷發(fā)展,車聯(lián)網(wǎng)(Internet of vehicles,IoV)成為智能交通系統(tǒng)的基礎(chǔ)技術(shù)[1]。隨之而來的變化就是車輛上涌現(xiàn)出各式各樣的應用,如安全類的車載增強現(xiàn)實、車輛避障等,以及非安全類的車內(nèi)觀影、視頻通話等。這些應用的出現(xiàn)為車輛用戶提供了便利[2]。然而,部分應用或?qū)Y源的需求較高,或?qū)r延較敏感,車載軟件和硬件系統(tǒng)難以滿足其苛刻的要求[3-4]。為解決車輛自身計算能力有限的問題,引入移動云計算(mobile cloud computing,MCC)[5]技術(shù),利用云服務器中豐富的資源為應用提供計算服務,可為車輛用戶帶來更高質(zhì)量的體驗[6]。但是,云服務器部署的位置通常距離車輛較遠,遠程通信會帶來過高的傳輸延遲,可能會對車輛用戶的生命安全造成嚴重威脅[7-8]。

為了解決移動云計算中任務傳輸時延過大的問題,作為移動邊緣計算[9](mobile edge computing,MEC)和車聯(lián)網(wǎng)的交叉領(lǐng)域,車載邊緣計算(vehicular edge computing,VEC)可以滿足車載應用在時延和計算能力方面的嚴格要求[10]。在VEC環(huán)境中,服務器被部署在距離車輛更近的網(wǎng)絡邊緣[11],通過降低服務器和車輛之間的傳輸延遲,為車輛提供高質(zhì)量的服務。但是對于邊緣服務器來說,資源不如云服務器豐富[12],特別是在工作負載密集的場景中,不斷增加的車輛和計算任務會導致邊緣服務器負載過重,其中的任務可能由于不合理的調(diào)度順序,出現(xiàn)爭搶資源的情況,從而導致任務失敗率升高。若失敗的是與安全相關(guān)的任務,會影響車輛及用戶的生命財產(chǎn)安全。

現(xiàn)有研究主要通過為任務設(shè)置優(yōu)先級來安排任務的執(zhí)行順序。然而,車輛上的應用多種多樣,若只考慮某一類應用的需求,優(yōu)先級的設(shè)定會具有較強的針對性,忽略其他類應用的計算需求,從而導致整體效果不佳。因此,在設(shè)定任務優(yōu)先級時需要兼顧應用的多種計算需求。與此同時,車輛的高移動性致使其在基站(base station,BS)覆蓋范圍內(nèi)的停留時間有限,若車輛無法在駛出通信范圍前收到計算結(jié)果,也會導致任務失敗。因此,通過考慮多種因素綜合判斷出任務緊急程度,在執(zhí)行任務時適時調(diào)高緊急任務的優(yōu)先級,以降低任務失敗率,保護車輛用戶的安全。

本文的主要貢獻在于設(shè)計了多因素任務優(yōu)先級模型,在處理任務時可以更好地平衡車載應用的多種計算需求,避免優(yōu)先級偏向某一種類型的應用。通過設(shè)計基于任務緊迫性的優(yōu)先級動態(tài)調(diào)整策略,及時關(guān)注到由車輛移動性導致的任務計算需求的變化,從而提升緊急任務成功完成的可能性。通過將任務最大可等待時間與優(yōu)先級相結(jié)合,設(shè)計了一種任務搶占機制,使任務之間頻繁搶占的狀況得到改善,降低了任務失敗的可能性。

1 相關(guān)工作

在VEC環(huán)境中,為了解決服務器內(nèi)部任務執(zhí)行順序的問題,現(xiàn)有的相關(guān)研究關(guān)注任務的優(yōu)先級策略。優(yōu)先級策略根據(jù)任務特性安排執(zhí)行順序并按需為其分配計算資源,主要分為兩種:靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。

靜態(tài)優(yōu)先級是指任務的優(yōu)先級一經(jīng)確定,便不會再改變,直至任務從隊列中被刪除。在現(xiàn)有基于靜態(tài)優(yōu)先級的任務調(diào)度研究文獻中,一般是基于任務的某一個特征來制定優(yōu)先級。Liu等[13]研究車輛應用在路邊單元(roadside unit,RSU)中的排序,對多個應用程序按照時延限制排序,并對同一應用程序中的多個任務按照依賴性排序,提出一個多應用多任務調(diào)度算法求解調(diào)度決策問題。仿真結(jié)果表明該算法可以顯著減少多個應用程序的平均完成時間。Chen等[14]針對移動環(huán)境下的調(diào)度問題,提出一種混合動態(tài)調(diào)度方案,由決策函數(shù)在基于隊列的算法和基于時間的算法中選擇一種,兩種算法分別按照服務器中隊列長度以及已等待時間進行排序,結(jié)果表明該方案在不穩(wěn)定的VEC環(huán)境中具有優(yōu)越的性能。Wang等[15]研究VEC網(wǎng)絡中根據(jù)車輛位置、速度和方向?qū)⑷蝿照{(diào)度給服務車輛(service provided vehicles,SPV)集群,并將SPV建模為M/G/K/N隊列系統(tǒng)。提出了基于模仿學習的在線調(diào)度算法。仿真表明,該方案與基準算法相比,平均能耗、本地SPV的任務處理率和平均任務執(zhí)行延遲方面均有超過50%的提高。Selvi等[16]對車輛上的緊急信息、一般信息和娛樂信息進行優(yōu)先排序,利用基于SMTP的相似性指標來定義信息的優(yōu)先級,并使用自適應調(diào)度分區(qū)技術(shù)完成緊急信息的廣播。Paymard等[17]提出了一種基于優(yōu)先級的任務調(diào)度策略,共同優(yōu)化計算和通信資源分配,以便在滿足用戶的服務質(zhì)量、用戶和基站的功耗以及服務速率分配的同時,使移動網(wǎng)絡運營商的利潤最大化。

動態(tài)優(yōu)先級是指系統(tǒng)先為任務分派一個初始優(yōu)先級,在運行過程中根據(jù)任務狀態(tài)等因素改變?nèi)蝿盏膬?yōu)先級。云計算環(huán)境中有部分文獻是基于任務的多種特性制定優(yōu)先級。如葉波等[18]根據(jù)任務價值度與任務緊急度計算動態(tài)優(yōu)先級,同時參考螢火蟲行為,由吸引度、亮度以及負載均衡度得出調(diào)度決策。該方案可以縮短總?cè)蝿盏耐瓿蓵r間,尤其當任務數(shù)與節(jié)點數(shù)規(guī)模較大時,該方案在負載均衡方面的優(yōu)勢更為明顯。劉亞秋等[19]利用任務價值密度和執(zhí)行緊迫性計算動態(tài)優(yōu)先級,通過模擬螢火蟲行為將任務調(diào)度至合適的虛擬機中。該方案可以降低任務的總完成時間,均衡虛擬機的負載,并降低任務的截止期錯失率。

然而,云環(huán)境中的任務是由固定設(shè)備或手機、電腦等移動性不高的設(shè)備產(chǎn)生,而在VEC環(huán)境中,任務是由移動車輛產(chǎn)生的,因此也要考慮到車輛的高移動性對調(diào)度決策的影響。Wang等[20]解決了車載系統(tǒng)中聯(lián)合任務調(diào)度與資源分配問題,首先利用任務的時延容忍度制定優(yōu)先級,再通過分組來優(yōu)化低優(yōu)先級的任務被提前處理的可能性,最后將資源分配問題轉(zhuǎn)化為馬爾可夫決策過程,用強化學習來求解。Li等[21]研究自動駕駛實時應用中計算資源調(diào)度問題。為了減少車輛從卸載數(shù)據(jù)時刻到接收結(jié)果時刻之間行駛的距離,根據(jù)邊緣服務器計算能力以及車輛移動性確定任務處理順序,用深度強化學習方法確定構(gòu)造的基于Whittle的指標來得到隨機調(diào)度方案。該方案以較低的復雜度,在適應車輛移動性的同時及時將結(jié)果傳遞給車輛。Zhang等[22]提出了一種針對車輛自組網(wǎng)安全消息的動態(tài)優(yōu)先級調(diào)度方案,動態(tài)調(diào)整消息的優(yōu)先級以滿足車輛的安全需求,該方案在車輛密度較高時可以減少網(wǎng)絡的重復遠程通信流量,在車輛密度較低時增加數(shù)據(jù)可傳輸?shù)木嚯x。

綜上,靜態(tài)優(yōu)先級的性能在一般情況下不如動態(tài)優(yōu)先級,因為它無法體現(xiàn)車載任務需求的動態(tài)性。雖然在云計算中已經(jīng)有部分研究是根據(jù)任務的多種特性來制定優(yōu)先級,但在現(xiàn)有VEC任務調(diào)度研究中,優(yōu)先級制定依據(jù)較為單一,無法同時滿足任務的多種計算需求。此外,VEC環(huán)境中現(xiàn)有研究的優(yōu)先級較為固定,難以適應由車輛移動性引起的任務緊迫性的變化,容易導致任務失敗率升高。因此,在考慮制定任務優(yōu)先級時綜合多種應用的特點,設(shè)計一種基于動態(tài)優(yōu)先級的任務調(diào)度方法是很有必要的。

2 系統(tǒng)模型

2.1 車載邊緣計算場景

本節(jié)對車載邊緣計算場景進行描述。圖1所示為在城市單向道路上,一個由車輛、BS和VEC服務器組成的車載網(wǎng)絡。道路一側(cè)部署了覆蓋半徑為L的BS,BS中配置了VEC服務器,服務器的計算能力用f表示。道路中的車輛通過V2I(vehicle to infrastructure)的方式與BS通信,用集合N={1,2,3,…,n}表示某一時間段中BS覆蓋范圍內(nèi)的所有產(chǎn)生任務的車輛,由于車輛自身的計算資源有限以及處理車輛任務可能需要用到BS范圍內(nèi)的某些信息(環(huán)境等),因此本文中考慮的每個任務都需要卸載到VEC服務器并在延遲約束內(nèi)執(zhí)行,且每個車輛一次只產(chǎn)生一個計算任務,任務之間相互獨立。

圖1 車載邊緣計算場景Fig.1 Vehicular edge computing scenario

2.2 任務優(yōu)先級模型

由于以上三種因素的單位不一致,若直接利用原始數(shù)據(jù)進行計算,容易突出數(shù)值較大的因素的作用,同時削弱數(shù)值較小的因素的作用。為了消除數(shù)據(jù)單位帶來的影響,對初始數(shù)據(jù)進行標準化處理。本文采用離差標準化,分別對這三種影響因素的原始數(shù)據(jù)進行線性變換,使其結(jié)果映射到0和1之間,再根據(jù)各自的權(quán)重計算優(yōu)先級。以xi,j表示任務i的第j個優(yōu)先級影響因素,則處理后的數(shù)據(jù)x′i,j表示為

(1)

對任務原始數(shù)據(jù)進行標準化處理后,依據(jù)影響因素各自的權(quán)重值計算綜合優(yōu)先級,公式表示如下:

(2)

2.3 時延計算模型

(3)

(4)

(5)

2.4 任務優(yōu)先級調(diào)整策略

在實際生活中,與手機、電腦等移動性較弱的移動設(shè)備不同,車輛的移動性較強,使得車輛在BS覆蓋范圍內(nèi)的行駛時間有限,這對車載任務能否按時完成提出了挑戰(zhàn)。對于優(yōu)先級較低但緊迫性隨車輛移動而升高的任務,靜態(tài)優(yōu)先級策略無法很好地適應。因此,需要動態(tài)調(diào)整優(yōu)先級以降低任務失敗率,并分析影響優(yōu)先級調(diào)整的因素。

為了確保車輛在駛離范圍前及時收到任務的計算結(jié)果,要關(guān)注車輛的位置變化,重點研究臨近覆蓋范圍邊界的車輛。首先,利用車輛的坐標可以計算出t時刻車輛與通信范圍邊界的距離di,計算公式如下:

(6)

(7)

(8)

(9)

(10)

因此,在任務優(yōu)先級的調(diào)整策略中,本文設(shè)計一種優(yōu)先級調(diào)整必要性分析模型,將車輛在BS通信范圍內(nèi)的剩余時間和任務執(zhí)行狀態(tài)一同表示為任務的緊迫性,來決定是否調(diào)整任務優(yōu)先級。令Ui表示任務緊迫性對優(yōu)先級調(diào)整決策的影響:

(11)

當服務器檢測到有Ui=1的任務時,將任務的優(yōu)先級調(diào)至最高,搶占當前正在執(zhí)行的任務,使得緊急任務可以優(yōu)先獲得計算資源。

3 任務調(diào)度問題描述

本文研究VEC服務器內(nèi)的任務執(zhí)行順序,以降低任務失敗率過高對車輛用戶帶來的影響。為了更精確地計算服務器中任務的失敗率,選取某一時間段內(nèi)的任務,將任務總數(shù)記為n。本文以最小化任務失敗率為目標。首先,計算成功完成的任務數(shù)量S:

(12)

式中,Fi用來判斷任務是否在最大時延限制內(nèi)完成。

然后,制定最小化任務失敗率的優(yōu)化目標:

(13)

式中:第一個約束表示優(yōu)先級的三個影響因素的權(quán)重值之和為1;第二個約束表示任務的總完成時間要在其最大時延限制內(nèi);第三個約束表示生成的車輛坐標要保持在服務器通信范圍內(nèi)。

4 基于動態(tài)優(yōu)先級的搶占式調(diào)度

4.1 搶占式調(diào)度機制

在VEC環(huán)境中,當車輛的行駛位置臨近BS的覆蓋范圍邊界,且處于就緒態(tài)的任務緊迫性升高時,在傳統(tǒng)的非搶占式調(diào)度中,任務會因車輛駛出范圍而中斷執(zhí)行,也可能會由于等待時間過長而錯過最大時延限制,最終致使任務失敗。與此同時,由于任務優(yōu)先級由最大時延限制、任務重要性以及所需資源量共同決定,而優(yōu)先級高的任務大多數(shù)都是與車輛安全相關(guān)的,任務失敗會對車輛用戶的安全造成很大影響。因此,需要為緊迫性升高的任務優(yōu)先分配計算資源,最直接的辦法就是搶占當前正在執(zhí)行的任務。

然而,車輛的高移動性可能會使多輛車的任務在一段時間內(nèi)都需要盡快執(zhí)行,它們的優(yōu)先級也可能會被頻繁地調(diào)整。若一個高優(yōu)先級任務A剛搶占完畢,又出現(xiàn)了優(yōu)先級比它更高的任務B,根據(jù)搶占式調(diào)度算法,B是不會考慮A的執(zhí)行狀態(tài)的,于是B又搶占了A的資源,那么不僅A無法完成,B也面臨著被優(yōu)先級更高的任務的搶占。頻繁的互相搶占不僅會浪費計算資源,也會導致任務的失敗率升高。因此,為了保證任務的完成率,需要在搶占之前對搶占行為的必要性進行判斷。

由于搶占式調(diào)度中具有任務之間頻繁搶占導致失敗率升高的不足,因此需要找出合理的搶占時機,確保任務被搶占后依然能夠在時延限制內(nèi)完成。本節(jié)引入任務的最大可等待時間這一概念[23]。任務的最大可等待時間是任務最大時延限制與總完成時間之間的差值,用來表示任務在最大時延限制內(nèi)可以被耽擱的最長時間。公式表示為

(14)

將任務的最大可等待時間與任務優(yōu)先級同時作為搶占行為的判斷條件,主要思想是看參與搶占的兩個任務能否容忍讓對方先完成。假設(shè)當前執(zhí)行的任務是A,要搶占的任務是B,具體搶占行為判斷流程如下:

(15)

4.2 搶占式調(diào)度算法

算法1 基于動態(tài)優(yōu)先級的搶占式調(diào)度算法輸入:任務數(shù)量n輸出:任務執(zhí)行順序1. 初始化f、α、β、γ、θ、τ、xi、yi;2. for i = 1 to n do3. Pprii=α·x′i,1+β·x′i,2+γ·x′i,3,存入隊列;4. 利用快速排序算法按優(yōu)先級數(shù)值從小到大排列,如果優(yōu)先級數(shù)值相同,則按照tmaxi的值從小到大排列;5. 每隔τ時間:6. if Ui+1 = 1:7. if tmaxwait,i+1

5 實驗結(jié)果

5.1 實驗參數(shù)設(shè)置

本文運用Python語言進行實驗,在不失一般性的前提下,考慮如下場景:取一段長為1 000 m的直線郊區(qū)道路,每輛車在這條道路范圍內(nèi)最多只產(chǎn)生一個任務。道路一側(cè)部署了基站,在其范圍內(nèi)車輛可與之進行通信。其他具體仿真參數(shù)如表1所示。

表1 仿真實驗參數(shù)Table 1 Parameters of simulation experiment

5.2 實驗結(jié)果分析

引入以下三種方案與本文的動態(tài)優(yōu)先級搶占式調(diào)度方案(dynamic priority preemptive scheduling,DPPS)進行比較。

1)靜態(tài)優(yōu)先級調(diào)度方案(static prioritized scheduling,SPS)。服務器根據(jù)任務的初始優(yōu)先級進行排序,不考慮處理過程中任務優(yōu)先級的變化。

3)直接搶占調(diào)度方案(direct preemption scheduling,DPS)。當任務優(yōu)先級發(fā)生變化時,服務器不考慮當前任務的執(zhí)行狀態(tài),直接讓高優(yōu)先級任務搶占資源。

首先將本文方案與SPS和HRRN進行對比,比較任務失敗率。當任務數(shù)量較少時,大部分任務都能按時完成;而當任務數(shù)量較多時,任務失敗的概率增大。因此,在固定的任務數(shù)量下比較三種算法的執(zhí)行結(jié)果。圖2給出了任務數(shù)量與任務失敗率的關(guān)系?？梢钥闯?當服務器中任務數(shù)量較少時,三種方案幾乎都能保證任務在各自的時延限制內(nèi)完成;隨著任務數(shù)量的增長,任務的失敗率呈緩慢上升趨勢。本文方案的失敗率整體增幅是最慢的,即方案能保證大部分任務在時延限制內(nèi)完成,原因是采用動態(tài)優(yōu)先級的方式能夠考慮到由車輛移動性以及等待時間所引起的任務緊迫性的變化,重點關(guān)注失敗可能性較大的任務,及時調(diào)整此類任務的優(yōu)先級,保證大部分任務的完成率。靜態(tài)優(yōu)先級調(diào)度方案中的優(yōu)先級一經(jīng)確定就不再改變,隨著任務數(shù)量的增加,隊列中優(yōu)先級較低的任務很可能因為等待時間過長而超出時延限制,導致任務失敗。HRRN方案雖然考慮了任務的等待時間,但任務的優(yōu)先級每時每刻都在變化。隨著任務數(shù)量的增加,優(yōu)先級需要調(diào)整的次數(shù)也隨之增加,任務的排序不穩(wěn)定,會互相搶占計算資源,如此反復,可能會令多數(shù)任務都無法按時完成,也會導致失敗率升高。

圖2 任務數(shù)量與任務失敗率的關(guān)系Fig.2 Relationship between number of tasks and task failure rate

任務最大時延限制表示任務從生成開始所能容忍的最長時間,時延限制越小的任務失敗的概率越大。因此比較不同時延限制對三種算法失敗率的影響。圖3給出了任務最大時延限制與任務失敗率的關(guān)系。

圖3 任務最大時延限制與任務失敗率的關(guān)系Fig.3 Relationship between maximum task delay limit and task failure rate

可以看出,隨著最大時延限制的增加,三種方案的任務失敗率在整體上皆呈下降趨勢。靜態(tài)優(yōu)先級調(diào)度方案與本文的方案相比缺乏靈活性,雖然任務最大時延限制的增加能夠提升部分低優(yōu)先級任務被處理的可能性,但長時間的等待也會增加部分任務失敗的可能性。HRRN方案中任務的優(yōu)先級隨著等待時間的增加在實時變化,對時延敏感的任務通常被優(yōu)先處理,留下部分對時延不敏感的任務,這些任務的執(zhí)行順序不固定,所有任務都面臨著被其它任務搶占的可能性,而可能性的大小會影響任務的完成,因此該方案無法保證任務的完成率。本文的方案對以上兩種方案進行了權(quán)衡,不僅能夠及時地為緊急任務分配計算資源,同時也會分析搶占行為的必要性,能夠保證多數(shù)任務被成功處理。

服務器的計算能力決定了任務的計算時間,計算時間越長的任務失敗的概率越大。因此比較不同服務器計算能力對三種算法失敗率的影響。圖4給出了服務器的計算能力與任務失敗率的關(guān)系?？梢钥闯?隨著服務器計算能力的增大,本文的方案和靜態(tài)優(yōu)先級調(diào)度方案的任務失敗率在大體上皆呈下降趨勢,僅有小范圍內(nèi)的波動,這是因為當服務器能力相差不大時,任務的計算時間也相差不大,又因為搶占行為本身具有不確定性,可能使少數(shù)任務無法成功完成,但從整體的角度來看,本文方案優(yōu)于靜態(tài)優(yōu)先級調(diào)度方案。而HRRN方案的失敗率變化幅度較大,原因是隨著服務器計算能力的提升,資源需求量較小的任務可以在短時間內(nèi)完成,但資源需求量較大的任務的完成時間較長,在處理的過程中容易受到高優(yōu)先級任務的直接搶占而被迫中斷,導致任務失敗。

圖4 服務器計算能力與任務失敗率的關(guān)系Fig.4 Relationship between server computing power and task failure rate

然后將本文方案與DPS進行對比,在固定的任務數(shù)量下比較兩者的執(zhí)行結(jié)果。圖5給出了任務數(shù)量與任務搶占次數(shù)的關(guān)系。可以看出,與直接搶占調(diào)度方案相比,本文的方案能夠有效降低任務搶占次數(shù)。在直接搶占調(diào)度中,服務器不會考慮被搶占任務的執(zhí)行狀態(tài),而是默許優(yōu)先級較高的任務直接中斷當前任務以獲取計算資源,頻繁的搶占不僅會增大任務失敗的可能性,還會增加搶占時產(chǎn)生的系統(tǒng)開銷,從而造成計算資源的浪費。而本文提出的方案會通過考慮任務執(zhí)行狀態(tài)來決定是否需要搶占,最大程度上減少不必要的搶占行為。

圖5 任務數(shù)量與任務搶占次數(shù)的關(guān)系Fig.5 Relationship between number of tasks and number of task preemptions

圖6給出了檢測時間間隔與任務失敗率的關(guān)系。由于在任務執(zhí)行過程中需要檢測是否有Ui=1的任務,因此設(shè)定一個檢測時間間隔τ,τ取值的不同會導致優(yōu)先級調(diào)整結(jié)果的不同,從而影響到任務失敗率。因此為了選擇合適的檢測時間間隔,實驗從[3,10] s中每隔0.5 s選取一次作為τ的取值。可以看出,當τ≤7 s時,任務失敗率的增幅較小,從τ>7 s之后,任務失敗率的增幅較大。因此本文在實驗過程中選擇3到7的中間值5 s作為τ的取值。

圖6 檢測時間間隔與任務失敗率的關(guān)系Fig.6 Relationship between detection time interval and task failure rate

6 結(jié)束語

本文在車載邊緣計算場景下設(shè)計一個考慮多因素的任務優(yōu)先級模型,并以此提出一種基于動態(tài)優(yōu)先級的任務調(diào)度方案,解決了因優(yōu)先級固定導致緊迫任務失敗率過高的問題。該方案通過設(shè)計結(jié)合任務最大可等待時間和優(yōu)先級的任務搶占機制,使緊迫性升高的任務及時得到處理,從而降低任務失敗率。仿真結(jié)果表明,相比于直接搶占調(diào)度方案,所提方案可以減少任務爭搶資源所帶來的搶占次數(shù),降低頻繁搶占對失敗率的影響;相比于靜態(tài)優(yōu)先級調(diào)度和高響應比優(yōu)先調(diào)度方案,所提方案可以降低10%以上的任務失敗率。