一種面向自動駕駛推理任務(wù)的工作流調(diào)度策略

林 凱，盧 宇，陳 星，林 兵

1(福建師范大學(xué) 物理與能源學(xué)院，福州 350117) 2(福州大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院，福州 350116)

1 引 言

隨著機動車保有量的增加，道路擁堵、交通安全、環(huán)境污染等問題日益突出.自動駕駛車輛的發(fā)展為這些問題提供了新的解決方案.高度自動化的車輛駕駛可以提高駕駛的便利性和舒適性，提高道路系統(tǒng)的整體交通效率和安全性，緩解交通擁堵，大大減少人為失誤造成的事故.此外，它還可以減少汽車尾氣排放對環(huán)境的污染，顯著提高燃油效率.

當(dāng)自動駕駛車輛行駛在道路上，傳感系統(tǒng)會檢測當(dāng)前的交通狀況，將路況信息傳遞到車輛的推理系統(tǒng)中，推理系統(tǒng)需要在短時間內(nèi)處理這些信息.隨后，車輛的傳動系統(tǒng)就能做出諸如加速、轉(zhuǎn)向等一系列響應(yīng)動作[1].由于OBU的計算能力不足，在容錯時間約束下，選擇合理的調(diào)度平臺，優(yōu)化自動推理任務(wù)的完成時間是自動駕駛技術(shù)中重點關(guān)注的問題.

邊緣計算為了將計算任務(wù)卸載到終端用戶附近的邊緣服務(wù)器，利用計算和存儲資源位于終端設(shè)備和云數(shù)據(jù)中心之間的邊緣設(shè)備.其目的是將計算任務(wù)卸載到終端用戶附近的邊緣服務(wù)器，并在數(shù)據(jù)源附近處理計算任務(wù)，從而縮短響應(yīng)時間.邊緣環(huán)境下推理任務(wù)的分解與調(diào)度能夠很好地滿足推理任務(wù)的低延遲處理要求，并產(chǎn)生良好的實時處理效果[2].

在自動駕駛推理任務(wù)的研究中，很少關(guān)注推理任務(wù)的調(diào)度問題，大部分研究集中自動駕駛過程中的交通狀況識別和推理分析[3-5].自動駕駛的推理任務(wù)調(diào)度問題類似于協(xié)同設(shè)計的任務(wù)調(diào)度和工作流調(diào)度.因此，協(xié)同設(shè)計任務(wù)和工作流調(diào)度的研究方案可以應(yīng)用于自動駕駛推理任務(wù)工作流調(diào)度中.由于推理任務(wù)通常調(diào)度在OBU上[6]，這將導(dǎo)致推理任務(wù)調(diào)度的高延遲，無法滿足推理任務(wù)的安全性和實時性要求.目前，啟發(fā)式算法被廣泛應(yīng)用于解決協(xié)同設(shè)計任務(wù)和工作流調(diào)度問題，如蟻群算法、粒子群算法、遺傳算法等[7-9]，這些算法雖然能較好地解決工作流調(diào)度問題和協(xié)同設(shè)計任務(wù)，但收斂速度慢，容易陷入局部最優(yōu)解，不能很好地滿足推理任務(wù)的低延遲要求.近年來，強化學(xué)習(xí)被應(yīng)用于解決協(xié)同設(shè)計任務(wù)和工作流的調(diào)度問題.該算法通過與不確定環(huán)境的交互作用來修正實際值與預(yù)測值之間的偏差，收斂速度較快.這些研究為自動駕駛推理任務(wù)工作流調(diào)度提供了一種新的解決方案[10-12].雖然推理任務(wù)的結(jié)構(gòu)類似于協(xié)同設(shè)計任務(wù)和工作流，但是自動駕駛車輛生成的推理任務(wù)需要滿足實時系統(tǒng)的低延遲要求.因此，有必要設(shè)計合適的調(diào)度策略和算法，以滿足自主駕駛推理任務(wù)的要求.

基于以上研究現(xiàn)狀，針對自動駕駛推理任務(wù)實時系統(tǒng)，根據(jù)車輛駕駛過程中推理任務(wù)和邊緣環(huán)境的變化，本文首先設(shè)計出一種在邊緣環(huán)境下的自動駕駛推理任務(wù)工作流調(diào)度策略，并充分利用邊緣計算平臺的計算能力對推理任務(wù)進(jìn)行調(diào)度.其次，利用SA-QL算法來尋找自動駕駛推理任務(wù)工作流的低延時調(diào)度方案.最后，本文對SA-RL算法和PSO算法進(jìn)行了性能比較.

本文的主要貢獻(xiàn)如下：

1)設(shè)計了一種推理任務(wù)工作流調(diào)度策略，考慮在不同時間窗內(nèi)邊緣環(huán)境和實時推理任務(wù)的變化情況，在滿足任務(wù)約束的條件下計算任務(wù)完成時間；

2)在邊緣環(huán)境下進(jìn)行自動駕駛推理任務(wù)工作流調(diào)度處理，在滿足推理任務(wù)約束條件下，減少任務(wù)完成時間；

3)引入SA-QL，結(jié)合本文提出的推理任務(wù)工作流調(diào)度策略，優(yōu)化自動駕駛實時推理任務(wù)工作流執(zhí)行時間.

本文余下部分組織布局如下.第2部介紹目前相關(guān)研究工作；第3部分對自動駕駛推理任務(wù)工作流調(diào)度問題進(jìn)行描述與分析，確定問題模型以及要求解的目標(biāo)，并用實例分析推理任務(wù)調(diào)度過程；第4部分提出了基于強化學(xué)習(xí)算法的推理任務(wù)工作流調(diào)度策略，設(shè)計了推理任務(wù)工作流調(diào)度算法來計算推理任務(wù)完成時間，提出了適用于本文研究問題的SA-QL算法；第5部分進(jìn)行實驗結(jié)果的討論與分析，對SA-RL算法及PSO算法進(jìn)行性能差異的分析；最后一部分總結(jié)全文，并討論本文未來的改進(jìn)與展望.

2 研究現(xiàn)狀

針對自動駕駛，當(dāng)前的研究工作主要集中于自動駕駛推理任務(wù)路況信息的推理決策和識別.例如Teichmann等人[3]提出了一種聯(lián)合分類、檢測和語義分割的語義推理方法，雖然加快了推理速度，在數(shù)據(jù)集中表現(xiàn)非常出色，但是仍存在著計算瓶頸和能耗大的問題，這些研究中，對推理決策過程進(jìn)行建模優(yōu)化，在自動駕駛推理決策問題中取得了不錯的效果，但未涉及推理任務(wù)調(diào)度問題的研究工作；Vacek等人[4]提出了一種基于案例推理的認(rèn)知汽車情景解釋方法，該方法依靠基于案例的推理來預(yù)測當(dāng)前場景的演變并選擇合適的行為，但是沒有使用實際場景進(jìn)行測試來顯示這種方法的潛力，而且沒有提出如何評估無案例知識下行為后果的方法；高振海等人[5]，針對決策過程的因果關(guān)聯(lián)問題,建立了車輛跟馳行為的馬爾可夫決策過程模型，基于增強Q學(xué)習(xí)算法對該模型進(jìn)行求解，驗證了方法的可行性與有效性，提升了決策過程的因果關(guān)聯(lián)性，改善了傳統(tǒng)決策方法中既定的邏輯切換策略并規(guī)避了固有設(shè)計理念中多參數(shù)調(diào)校的難題，使自動駕駛過程中車輛動作的選擇更貼合實際，但是回報函數(shù)的設(shè)計缺少舒適性等其他指標(biāo)的考慮，沒有驗證算法的穩(wěn)定性；王娟娟等人[6]基于可并行的有向無環(huán)圖提出了一種自動駕駛硬實時推理任務(wù)調(diào)度機制，保證所有進(jìn)入車載計算系統(tǒng)的推理任務(wù)都能在其截止期之前完成，有效提升自動駕駛時應(yīng)急避險的安全性，但是研究中將推理任務(wù)調(diào)度至車載處理器進(jìn)行處理，存在著處理設(shè)備計算能力不足，處理時延高的問題，不能很好的滿足自動駕駛推理任務(wù)的實時性要求.

由于自動駕駛推理任務(wù)與協(xié)同設(shè)計任務(wù)及工作流結(jié)構(gòu)相似，因此將協(xié)同設(shè)計任務(wù)與工作流調(diào)度問題的研究方法應(yīng)用于自動駕駛推理任務(wù)的調(diào)度上具有可行性.在工作流調(diào)度問題的研究中，研究者主要采用仿生算法進(jìn)行問題求解，例如Meena等人[7]提出了一種元啟發(fā)式成本效用遺傳算法，考慮了云的異構(gòu)性、按需付費價格模型，以及虛擬機性能變化和啟動時間等因素，在云環(huán)境中，滿足最后期限的同時，最大限度地降低工作流的執(zhí)行成本，雖然在執(zhí)行時間與執(zhí)行成本上取得了不錯的效果，但是未考慮到虛擬機的關(guān)閉時間，以及虛擬機部署在不同數(shù)據(jù)中心之間的數(shù)據(jù)傳輸成本，這些因素將影響工作流的總體執(zhí)行成本.Zhu等人[8]基于進(jìn)化多目標(biāo)優(yōu)化算法來解決基礎(chǔ)設(shè)施即服務(wù)平臺上的工作流調(diào)度問題，提出了一種針對特定問題的編碼和種群初始化、適應(yīng)度評價和遺傳算子的新方案，結(jié)果表明，算法具有較高的穩(wěn)定性，可以獲得更好的解決方案，但未考慮多個定價方案、實例類型、云的情況以及通信和存儲的成本；Xie等人[9]提出了一種全新的非局部收斂粒子群優(yōu)化算法，應(yīng)用非線性慣性權(quán)重來平衡和調(diào)整粒子的全局和局部搜索能力，通過加速粒子群加快近最優(yōu)解的搜索速度，通過選擇和變異操作，使粒子群以一定的概率逃離局部極值，保持粒子群的多樣性，減少極大地降低了云邊緣環(huán)境下工作流調(diào)度的時間和經(jīng)濟成本.

隨著強化學(xué)習(xí)算法的發(fā)展，一些研究者將其運用至協(xié)同設(shè)計任務(wù)及工作流調(diào)度問題中，并取得了不錯的效果.例如，Wang 等人[10]將深度Q網(wǎng)絡(luò)模型應(yīng)用于多代理增強學(xué)習(xí)環(huán)境中，以指導(dǎo)云上多工作流的調(diào)度，構(gòu)建了一個馬爾可夫博弈模型，該模型以工作流應(yīng)用程序和異構(gòu)虛擬機的數(shù)量作為狀態(tài)輸入，以最大完成時間和成本作為回報，優(yōu)化了多工作流的完成時間和用戶成本，雖然生成調(diào)度策略優(yōu)于傳統(tǒng)算法，但是提出的方法未考慮更多的QoS指標(biāo)，如可靠性、安全性、負(fù)載平衡等，并且依賴于任務(wù)和候選云服務(wù)器的QoS數(shù)據(jù)信息，在實際應(yīng)用中，如果歷史QoS數(shù)據(jù)不足，收集數(shù)據(jù)的工作十分昂貴和耗時；Orhean等人[11]針對分布式系統(tǒng)中的調(diào)度問題，考慮了節(jié)點的異質(zhì)性及其在網(wǎng)格中的配置，提出了一種強化學(xué)習(xí)算法，從而確定一個更低執(zhí)行時間的調(diào)度策略，但是由于分布式系統(tǒng)的復(fù)雜性，學(xué)習(xí)模型存在局限性，當(dāng)系統(tǒng)添加的節(jié)點過多，強化學(xué)習(xí)代理將無法正確學(xué)習(xí)最佳策略.陳圣磊等人[12]建立了任務(wù)調(diào)度問題的目標(biāo)模型，給出調(diào)度問題的馬爾可夫決策過程描述，提出一種基于多步信息更新值函數(shù)的多步Q學(xué)習(xí)調(diào)度算法(Multi-step Q Learning Algorithm,MQ)，該算法收斂速度較快，能有效地解決任務(wù)調(diào)度問題，雖然采用多步Q學(xué)習(xí)算法能有效平衡協(xié)同設(shè)計任務(wù)調(diào)度的計算量和預(yù)見能力，但是由于算法步數(shù)的變化對算法性能有較大影響，而在自動駕駛推理任務(wù)工作流調(diào)度問題中，路況復(fù)雜性大，實時推理任務(wù)各同，數(shù)量大，不可能對所有實時推理任務(wù)進(jìn)行參數(shù)優(yōu)化，所以MQ算法并不適用于本文所論述的問題.

目前對自動駕駛推理任務(wù)調(diào)度的研究相對不足，因此本文從協(xié)同設(shè)計任務(wù)與工作流調(diào)度研究方法出發(fā)，對邊緣環(huán)境下的自動駕駛產(chǎn)生的實時推理任務(wù)調(diào)度問題進(jìn)行研究討論.一方面，本文設(shè)計了一種推理任務(wù)工作流調(diào)度策略，通過SA-QL優(yōu)化推理任務(wù)工作流完成時間，在嚴(yán)格容忍時間限制滿足推理任務(wù)實時系統(tǒng)低時延的約束條件，提高自動駕駛過程中推理任務(wù)調(diào)度的成功率；另一方面，本文證明了SA-RL算法和PSO算法在自動駕駛推理任務(wù)工作流調(diào)度問題上的可行性，并進(jìn)一步分析了SA-RL算法和PSO算法在自動駕駛推理任務(wù)工作流調(diào)度問題求解中的性能差異.

3 問題描述

3.1 問題定義

對于自動駕駛推理任務(wù)而言，任務(wù)具有實時性的特點，在不同時間窗內(nèi)會產(chǎn)生不同實時推理任務(wù)，并且邊緣環(huán)境中邊緣節(jié)點數(shù)量也在不斷發(fā)生變化.圖1描述了邊緣環(huán)境下自動駕駛車輛產(chǎn)生的推理任務(wù)的不同以及邊緣節(jié)點在不同時間窗中的變化情況.

圖1 不同時間窗上邊緣環(huán)境及推理任務(wù)變化情況Fig.1 Change of edge environment and reasoning task in different time windows

(1)

(2)

(3)

(4)

為了在邊緣環(huán)境中更好地利用邊緣節(jié)點的計算資源，規(guī)定邊緣節(jié)點調(diào)度處理子任務(wù)要滿足特定的處理原則：

1)在相同邊緣節(jié)點上的子任務(wù)要按深度串行執(zhí)行，若深度相等，則按子任務(wù)序號升序執(zhí)行，子任務(wù)深度由公式(5)表示；

2)在不同邊緣節(jié)點上的子任務(wù)可并行執(zhí)行；

3)每個子任務(wù)只能被一個邊緣節(jié)點所調(diào)度，由公式(6)表示；

4)當(dāng)邊緣節(jié)點上分配的所有子任務(wù)傳輸完成時開始處理子任務(wù).

(5)

(6)

(7)

(8)

根據(jù)以上定義，自動駕駛推理任務(wù)工作流調(diào)度問題可以形式化地描述為：合理指派子任務(wù)到各個邊緣節(jié)點上處理，結(jié)合推理任務(wù)工作流調(diào)度策略，在滿足實時推理任務(wù)可容忍時間、子任務(wù)間偏序約束以及邊緣節(jié)點處理原則下，優(yōu)化實時推理任務(wù)完成時間，如公式(9)所示:

(9)

formula(6)

3.2 問題分析

圖2為某個時間窗下邊緣環(huán)境及自動駕駛車輛推理任務(wù)情況，此時邊緣環(huán)境中有2個邊緣節(jié)點{f1,f2}，自動駕駛汽車產(chǎn)生的實時推理任務(wù)可劃分為4個子任務(wù){(diào)n1,n2,n3,n4}，子任務(wù)間有著4條時序約束有向邊{e1,2,e1,3,e2,4,e3,4}，可容忍時間為30毫秒.

圖2 邊緣環(huán)境及自動駕駛車輛推理任務(wù)情況Fig.2 Edge environment and reasoning task of autonomous vehicle

該實時推理任務(wù)存在可行調(diào)度方案，其邊緣節(jié)點-子任務(wù)匹配矩陣如表1所示，表2為邊緣節(jié)點-子任務(wù)平均傳輸時間矩陣，表3為邊緣節(jié)點-子任務(wù)平均完成時間矩陣，表4為子任務(wù)-子任務(wù)平均傳輸時間矩陣，實時推理任務(wù)調(diào)度過程如3所示，總完成時間為17毫秒，其中所有子任務(wù)傳輸至邊緣節(jié)點的傳輸時間為3毫秒，調(diào)度時間為14毫秒，最差調(diào)度下調(diào)度總時間為24毫秒，小于實時推理任務(wù)可容忍時間.

表1 邊緣節(jié)點-子任務(wù)匹配矩陣Table 1 Matching matrix between edge-node and sub-task

表2 邊緣節(jié)點-子任務(wù)平均傳輸時間矩陣Table 2 Average transmission time matrix between edge-node and sub-task

表3 邊緣節(jié)點-子任務(wù)平均完成時間矩陣Table 3 Average completion time matrix between edge-node and sub-task

圖

表4 子任務(wù)-子任務(wù)平均傳輸時間矩陣Table 4 Average transmission time matrix among sub-tasks

圖3 實時推理任務(wù)調(diào)度過程Fig.3 Scheduling process of real time reasoning task

4 基于強化學(xué)習(xí)算法的推理任務(wù)工作流調(diào)度策略

在自動駕駛汽車運行過程中，路況不斷發(fā)生變化，感知系統(tǒng)不斷將路況信息傳遞給推理系統(tǒng)，推理系統(tǒng)處理的實時推理任務(wù)在不斷變化，而這些實時推理任務(wù)往往有著不同的約束條件，為了在滿足約束條件的前提下，降低調(diào)度處理時延，提出一種推理任務(wù)工作流調(diào)度策略，在該策略下，假設(shè)自動駕駛車輛所處的邊緣環(huán)境為理想狀態(tài)，即在當(dāng)前時間窗內(nèi)邊緣環(huán)境中所有邊緣節(jié)點都沒有宕機的情況，其中推理任務(wù)工作流調(diào)度算法根據(jù)當(dāng)前時間窗的邊緣環(huán)境及實時推理任務(wù)來計算完成時間.

4.1 推理任務(wù)工作流調(diào)度策略

在不同時間窗內(nèi)，自動駕駛車輛產(chǎn)生的實時推理任務(wù)與邊緣環(huán)境將動態(tài)發(fā)生變化，有以下變化情況：

1)實時推理任務(wù)分解后的子任務(wù)數(shù)量；

2)實時推理任務(wù)分解后的子任務(wù)間偏序關(guān)系；

3)實時推理任務(wù)的可容忍時間；

4)當(dāng)前時間窗可用邊緣節(jié)點數(shù).

實時推理任務(wù)完成時間與自動駕駛車輛產(chǎn)生的實時推理任務(wù)與邊緣環(huán)境的變化有關(guān)，因此推理任務(wù)的完成時間就要在動態(tài)變化的邊緣環(huán)境中進(jìn)行計算.

推理任務(wù)工作流調(diào)度算法如算法1所示.

算法1.推理任務(wù)工作流調(diào)度算法

輸入：si,mi,Gi,Ami×si,Cmi×si

1.初始化：入度數(shù)組I→?及節(jié)點隊列Q→?，直接前驅(qū)節(jié)點集合R→?，前驅(qū)任務(wù)數(shù)據(jù)最長傳輸時間T(i)→0

2.由Gi計算I(i)

3.將I(i)=0的節(jié)點入隊，設(shè)置當(dāng)前深度p→1，已遍歷的節(jié)點數(shù)u→0，當(dāng)前層的節(jié)點數(shù)k為當(dāng)前隊列大小

4.whileQ≠?

5.ifu=kthen

6.p→p+1，u→0，k為當(dāng)前隊列大小

7.end if

8. 隊首出隊，出隊節(jié)點為v，設(shè)置D(v)→p

9.u→u+1

10.fori←0tosi

11.if存在v至i的有向邊then

12. 將v加入R(i)

13.I(i)→I(i)-1

14.T(i)→MAX(T(i),V(v,i))

15.ifI(i)=0then

16. 將任務(wù)i加入Q

17.end if

18.end if

19.end for

20.end while

21.由Ami×si為邊緣節(jié)點分配子任務(wù)

22.同一邊緣節(jié)點中子任務(wù)按任務(wù)深度值升序排序

23.初始化：完成列表O→?,子任務(wù)剩余執(zhí)行時間Y(i)=C(*,i)+T(i)，當(dāng)前時間h→0

24.whileO中元素個數(shù)小于si

25. 為每個邊緣節(jié)點確定要執(zhí)行的子任務(wù),該子任務(wù)要滿足其直接前驅(qū)集合為O子集

26. 在當(dāng)前執(zhí)行的子任務(wù)中找出最少執(zhí)行時間w

27.Y(i)→Y(i)-w，如果Y(i)=0，則加入O

28.h→h+w

29.end while

30.returnh

4.2 強化學(xué)習(xí)算法

4.2.1 馬爾可夫決策過程模型

馬爾可夫決策過程(Markov Decision Process,MDP)模型是強化學(xué)習(xí)算法的基本模型，由于現(xiàn)實環(huán)境中狀態(tài)轉(zhuǎn)移的概率往往和歷史狀態(tài)有關(guān)，這樣很難建立模型，因此可以根據(jù)馬爾科夫性(即無后效性，也就是指環(huán)境中的下個狀態(tài)只與當(dāng)前狀態(tài)信息有關(guān)，而與歷史的狀態(tài)無關(guān))來簡化模型，使得下個狀態(tài)只與當(dāng)前狀態(tài)和所采取的動作有關(guān)[13].

本文所研究的任務(wù)調(diào)度問題有以下特點：

1)沒有任何的先驗?zāi)Ｐ停?/p>

2)狀態(tài)空間中可解狀態(tài)數(shù)隨子任務(wù)數(shù)以及可行解約束條件動態(tài)變化；

3)動作空間中的動作數(shù)與子任務(wù)數(shù)相等.

既要滿足子任務(wù)時序約束，又要滿足嚴(yán)格容忍時間約束

基于以上特點，本文的MDP模型如下：

·智能體：子任務(wù)

·狀態(tài)：邊緣節(jié)點-子任務(wù)分配矩陣

·動作：動作空間內(nèi)動作數(shù)等于子任務(wù)數(shù)si，如果當(dāng)前狀態(tài)au,k=1表示第k個子任務(wù)當(dāng)前部署在第u個邊緣節(jié)點中，那么執(zhí)行動作k后，au,k=0，ax,k=1，其中x=(u+1)%mi表示將第k個子任務(wù)部署到下一個邊緣節(jié)點

4.2.2 基于推理任務(wù)工作流調(diào)度策略的Q-learning算法

Q-learning是一種時序差分(Temporal-Difference,TD)算法，它基于隨機過程且不依賴模型(Model-Free)，無狀態(tài)轉(zhuǎn)化概率矩陣.由于算法更新價值函數(shù)時會選擇最大價值進(jìn)行更新，而動作選擇不一定按最大價值所對應(yīng)動作，因此會導(dǎo)致價值函數(shù)的樂觀估計，由于這一特性，Q-learning屬于離線策略(off-policy)學(xué)習(xí)方法[14].

Q-learning價值函數(shù)根據(jù)四元組信息進(jìn)行更新，其中S代表當(dāng)前狀態(tài)，A代表當(dāng)前選擇的動作，R代表即時獎勵，S′代表轉(zhuǎn)移后的狀態(tài).

Q-learning價值函數(shù)更新方式如下：

Q(s,a)=Q(s,a)+α[r+γmaxa′Q(s′,a′)-Q(s,a)]

(10)

其中α為學(xué)習(xí)效率，表示價值函數(shù)更新的程度，r為即時獎勵，表示轉(zhuǎn)移至下一個狀態(tài)所得到的獎勵，γ為折扣因子，表示后續(xù)狀態(tài)的價值對當(dāng)前狀態(tài)的影響程度，maxa′Q(s′,a′)為選取的價值最大的狀態(tài)-動作對的值.

由于：

Qreal=r+γmaxa′Q(s′,a′)

(11)

Qeval=Q(s,a)

(12)

因此，價值函數(shù)更新公式可進(jìn)一步表示為：

Q(s,a)=Q(s,a)+α(Qreal-Qeval)

(13)

即Q-learning價值函數(shù)的更新可表示為價值函數(shù)值加上現(xiàn)實值與估計值的差值與學(xué)習(xí)效率的乘積.

為了平衡算法的探索與開發(fā)，本文采用Metropolis準(zhǔn)則[15]進(jìn)行動作的選擇，其中退火策略采用等比降溫策略：

Tk=θkT0

(14)

其中T0為初始溫度，k為當(dāng)前回合次數(shù)，θ為降溫系數(shù).

為減小狀態(tài)-動作值表大小，減少狀態(tài)搜索耗時，本文選擇在可解狀態(tài)空間中進(jìn)行探索，即算法中探索的所有狀態(tài)均滿足公式(9)中的約束條件.基于推理任務(wù)工作流調(diào)度策略的Q-learning算法如算法2所示.

算法2.基于推理任務(wù)工作流調(diào)度策略的Q-learning算法

輸入：回合數(shù)，回合迭代數(shù)，初始狀態(tài)，初始溫度

輸出：Q(s,a)

1.fori←0to回合數(shù)

2. 隨機選取動作，使初始狀態(tài)變?yōu)榭尚薪?/p>

3.forj←0to回合迭代數(shù)

4. 根據(jù)Metropolis準(zhǔn)則選擇動作，該動作轉(zhuǎn)移的狀態(tài)必須為可行解狀態(tài)

5. 執(zhí)行動作，轉(zhuǎn)移狀態(tài)

7. 根據(jù)<當(dāng)前狀態(tài),選擇動作,即時獎勵,轉(zhuǎn)移后狀態(tài)>四元組信息由公式(10)進(jìn)行價值函數(shù)的更新

8. 根據(jù)公式(14)進(jìn)行對當(dāng)前溫度進(jìn)行降溫處理

9.end for

10.end for

5 算法實驗與分析

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

通過多次實驗調(diào)參結(jié)果，本文設(shè)置強化學(xué)習(xí)算法參數(shù)：α=0.01，γ=0.9，λ=0.5，λ為Sarsa(λ)[16]、Q(λ)[16]算法中效用跡矩陣衰減率，回合數(shù)為100，回合迭代數(shù)為1000；設(shè)置PSO算法參數(shù)：ω=0.9，c1=2，c2=2；設(shè)置模擬退火參數(shù)：T0=150，θ=0.9.

本文采用文獻(xiàn)[12]的調(diào)度實例，假設(shè)該實時推理任務(wù)可容忍時間為 60毫秒，任務(wù)分解后有7個子任務(wù)，子任務(wù)間時序約束的DAG如圖4所示.

圖4 子任務(wù)間時序約束的DAGFig.4 DAG with temporal constraints among sub-tasks

設(shè)當(dāng)前邊緣環(huán)境中有3個可用邊緣節(jié)點，子任務(wù)在各邊緣節(jié)點上平均完成時間、平均傳輸時間、子任務(wù)間平均傳輸時間如表5、表6、表7所示.

表5 邊緣節(jié)點-子任務(wù)平均傳輸時間矩陣Table 5 Average transmission time matrix between edge-node and sub-task

表6 邊緣節(jié)點-子任務(wù)平均完成時間矩陣Table 6 Average completion time matrix between edge-node and sub-task

表7 子任務(wù)-子任務(wù)平均傳輸時間矩陣Table 7 Average transmission time matrix among sub-tasks

5.2 對比算法

為了驗證SA-RL算法在自動駕駛推理任務(wù)調(diào)度上的有效性，本文選擇TD(0)算法：Sarsa[17]，TD(λ)算法：Sarsa(λ)、Q(λ)作為對比算法.為了比較SA-RL與傳統(tǒng)啟發(fā)式算法的性能區(qū)別，本文選擇PSO[18]作為比較算法，其中PSO算法中粒子比較方式[19]如下：

1)兩個粒子都滿足可行解條件：選擇完成時間較小的粒子;

2)兩個粒子都不滿足可行解條件：選擇完成時間較小的粒子;

3)一個粒子滿足可行解條件，一個粒子不滿足可行解條件：選擇滿足可行解條件的粒子.

5.3 實驗結(jié)果與分析

本實驗的實驗環(huán)境為，CPU：Intel(R)Core(TM)i7-4720HQ CPU 2.60GHz，內(nèi)存：8GB，操作系統(tǒng)：Windows 10，編程語言：Python.

由搜索算法可得狀態(tài)空間可解狀態(tài)數(shù)為2042個.

在該實例中，SA-RL算法和PSO算法均能找到2個最優(yōu)邊緣節(jié)點-子任務(wù)匹配矩陣：

傳輸時間為3毫秒，實時推理任務(wù)最短的最佳運行時間均為32毫秒，匹配矩陣1對應(yīng)分配策略的調(diào)度處理過程如圖5所示.

圖5 最優(yōu)分配策略1調(diào)度處理過程Fig.5 Scheduling process of optimal allocation strategy 1

以圖5為例分析對應(yīng)邊緣節(jié)點-子任務(wù)分配方案調(diào)度過程：

1)根據(jù)子任務(wù)深度與子任務(wù)序號為邊緣節(jié)點分配子任務(wù)：f1:{n1,n4,n5},f2:{n2,n7},f3:{n3,n6}；

2)經(jīng)過3毫秒，所有子任務(wù)卸載到對應(yīng)的邊緣節(jié)點上，子任務(wù)1卸載至邊緣節(jié)點1上執(zhí)行，到6毫秒時子任務(wù)1完成；

3)子任務(wù)2經(jīng)過卸載至邊緣節(jié)點2上，經(jīng)過2毫秒任務(wù)間的數(shù)據(jù)傳輸時間，子任務(wù)開始執(zhí)行，到10毫秒時，子任務(wù)2完成；

4)子任務(wù)3、4分別卸載至邊緣節(jié)點3、1上，經(jīng)過1毫秒任務(wù)間的數(shù)據(jù)傳輸時間以及4毫秒的任務(wù)處理時間，到15毫秒時子任務(wù)4完成，此時子任務(wù)3還剩2毫秒的數(shù)據(jù)傳輸時間以及2毫秒的任務(wù)處理時間；

5)子任務(wù)5卸載至邊緣節(jié)點1進(jìn)行任務(wù)調(diào)度，到19毫秒時，子任務(wù)3完成，此時子任務(wù)5還剩2毫秒的數(shù)據(jù)傳輸時間以及2毫秒的任務(wù)處理時間；

6)子任務(wù)6卸載至邊緣節(jié)點3進(jìn)行任務(wù)調(diào)度，到23毫秒時，子任務(wù)5完成，此時子任務(wù)6還剩1毫秒的任務(wù)處理時間；

7)經(jīng)過1毫秒，到24毫秒時，子任務(wù)6完成；

8)子任務(wù)7卸載至邊緣節(jié)點2進(jìn)行任務(wù)調(diào)度，經(jīng)過5毫秒任務(wù)間的數(shù)據(jù)傳輸時間以及3毫秒的任務(wù)處理時間，到32毫秒時完成調(diào)度.

SA-RL算法與PSO算法每10回合平均完成時間如圖6所示.隨著回合數(shù)不斷增加，各算法平均完成時間不斷降低，平均完成時間均低于可容忍時間.從圖中可以看出，回合剛開始，強化學(xué)習(xí)算法平均完成時間波動較小且維持在較高水平，這是因為初始溫度較高，因此選擇隨機動作的概率較大；但是隨著Metropolis準(zhǔn)則的降溫處理，回合即將達(dá)到設(shè)定的回合數(shù)時，強化學(xué)習(xí)算法以接近于1的概率選擇最佳動作，因此算法平均完成時間不斷下降，其中Sarsa(λ)、Q(λ)算法收斂較早，這是因為算法中引入了效用跡矩陣，采用多步更新策略，因此能加快收斂速度.

圖6 每10回合平均完成時間Fig.6 Average completion time of every 10 rounds

除此之外，PSO算法的平均完成時間雖然一直在下降但是波動較大，平均完成時間會維持在較高水平，這是由于啟發(fā)式算法收斂速度慢、易陷入局部最優(yōu)解的特點導(dǎo)致的.

SA-RL算法每10回合平均獎勵如圖7所示.隨著回合數(shù)不斷增加，各強化學(xué)習(xí)算法平均獎勵不斷提高，在后期收斂過程中Sarsa(λ)、Q(λ)的平均獎勵值維持在較高水平，這是由于算法收斂速度快，因此會更快得到更優(yōu)的價值函數(shù).

圖7 每10回合平均獎勵Fig.7 Average reward of every 10 rounds

SA-RL算法與PSO算法每10回合完成時間平均方差如圖8所示.從圖中可以看出PSO算法與SA-RL算法相比，平均方差維持在較高水平，平均完成時間波動較大.Sarsa(λ)、Q(λ)較其他強化學(xué)習(xí)算法而言，收斂較快，平均方差能維持在較低水平，平均完成時間波動較小.

圖8 每10回合完成時間平均方差Fig.8 Average variance of completion time

SA-RL算法運行5次探索到所有可解狀態(tài)數(shù)時的回合次數(shù)如表8所示.從表中可以看出SA-RL算法探索到所有可解狀態(tài)數(shù)的回合數(shù)相差不大，其中TD(λ)算法探索到所有可解狀態(tài)所需的回合次數(shù)少于TD(0).

表8 探索到所有可解狀態(tài)時的回合次數(shù)Table 8 Amount of rounds when SA-RL found all feasible states

SA-RL算法運行5次探索到所有可解狀態(tài)數(shù)時的耗時如表9所示.從表中可以看出當(dāng)探索到所有可解狀態(tài)時，Q-learning、Sarsa較Sarsa(λ)、Q(λ)而言耗時較短，原因是Sarsa(λ)、Q(λ)算法進(jìn)行學(xué)習(xí)時不僅要對遍歷過狀態(tài)的狀態(tài)-動作表進(jìn)行更新，還要對效用跡矩陣進(jìn)行更新，隨著狀態(tài)空間的增大，算法所要更新的表空間不斷增加，因此耗時較長.

表9 探索到所有可解狀態(tài)時的耗時Table 9 Time when SA-RL found all feasible states

綜上所述，對于自動駕駛實時推理任務(wù)工作流調(diào)度問題，SA-RL算法與PSO算法在實驗中均能找到符合約束條件的優(yōu)解，均具備可行性的特點；強化學(xué)習(xí)算法與PSO算法每回合平均完成時間均隨著回合數(shù)增加不斷降低，不斷趨于收斂狀態(tài)，證明了強化學(xué)習(xí)算法與PSO算法的有效性；在探索可行解狀態(tài)過程中，Q-learning、Sarsa耗時較短，表明TD(0)算法探索性較強；由每回合平均完成時間與完成時間平均方差的變化，可以看出Sarsa(λ)、Q(λ)收斂較快，平均方差最終維持在較低水平，波動較小，表明TD(λ)算法的收斂性更強.

6 結(jié) 論

針對自動駕駛推理任務(wù)工作流調(diào)度問題，提出了一種基于強化學(xué)習(xí)算法的推理任務(wù)工作流調(diào)度策略.實驗結(jié)果表明，該策略能快速有效地找到滿足容錯時間的調(diào)度方案.SA-QL和Sarsa在探索可行狀態(tài)上所耗費的時間更少.這說明TD(0)算法更具探索性.從平均完成時間的變化以及平均方差可以看出，Sarsa(λ)和Q(λ)收斂更快.此外，Sarsa(λ)和Q(λ)的平均方差保持在較低水平，波動較小.實驗表明，TD(λ)算法具有良好的收斂性.

在未來的工作中，我們將考慮云計算和車聯(lián)網(wǎng)混合環(huán)境下的調(diào)度問題，以促進(jìn)卸載設(shè)備的多樣性和任務(wù)調(diào)度的靈活性.此外，我們還將考慮使用RL算法結(jié)合深度學(xué)習(xí)技術(shù)來優(yōu)化推理任務(wù)的完成時間.