車輛移動云可靠性任務調度

李曉靜 馬海英

1(濟源職業技術學院 河南 濟源 459000)2(南通大學計算機科學與技術學院 江蘇 南通 226019)

0 引 言

在物聯網IoT時代背景下，城市道路上的車輛通常配置有數量眾多的小規模處理能力的車載計算資源與設備。目前，大量研究正集中于如何利用車輛Ad Hoc網絡VANET應用實現更安全更智能的駕車體檢[1-2]。車載傳感器生成的大量數據催生了車輛云計算(Vehicular Cloud Computing,VCC)的產生，它使得車輛間可以協作地為用戶應用提供感知、計算和存儲服務[3-4]。不同于傳統的云計算，車輛云計算中的資源不固定于具體的物理位置，其形成的VANET拓撲結構會發生動態改變，車輛間的連通關系也無法可靠地持續連接。而車輛云計算技術充分利用鄰居車輛的多余空閑計算能力，使服務需求可以持續供應，保證應用執行的連續性。其中關鍵問題在于如何選擇鄰居計算資源，以確保用戶應用可以在截止時間內可靠執行并完成，并滿足用戶的服務質量需求。

目前，車輛環境下的云服務可分為三類[5]：1) 車輛利用傳統云服務，即車輛可提交作業至云端，從傳統的云數據中心獲取服務；2) 車輛云，即車輛間可將低效利用資源以云服務的形式共享至其他車輛；3) 混合云，即傳統云和車輛云混合提供計算服務。目前的車輛云研究多集中于第二種云環境。該環境下，車輛可形成臨時的服務集群，并從集群worker中獲取云服務。每個集群選擇一個集群首CH，CH的作用是決定何時何地如何以分布式方式執行車輛用戶提交的作業。文獻[6]提出一種TSBIP算法。該算法利用二進制整數規化模型建立了車輛云下的應用調度模型，以并行方式執行任務調度，但由于車輛云中的車輛可能隨時遠離云環境，其應用的服務復制機制顯得代價太大。文獻[7]提出了一種BSS算法用于任務調度時車輛服務器的選擇。該算法考慮了服務的執行能力，利用蜂群算法思想建立適應度函數選擇最優的車輛，但沒有考慮車輛移動環境下任務調度的可靠性，此時車輛間的連通對調度結果也具有重要影響。文獻[8]為了解決車輛云計算中車輛的高度動態性對調度問題中失效檢測性能的影響，設計了一種基于共享機制的失效檢測方法，針對錯誤發生率和車輛負載指標的定量分析，對車輛節點進行分組，實現了高度動態車輛移動環境下的失效檢測。此外，目前多數的車輛云中的任務調度多采用集中式調度方法[9-10]。然而，集中式調度在面對車載數據量劇增時顯得效率不高，且已有研究在關注作業執行時未考慮可靠性問題，這在時間敏感型應用中極其不利。

基于以上分析，本文設計了一種面向車輛云計算環境的滿足可靠性的任務調度算法OTS-VC，算法假設道路上擁有相對較低速度的車輛可以集群的方式構成群組，每個集群首CH利用MapReduce計算模型以快速分布式的方式進行數據處理，CH已知其所有worker成員節點的信息，包括若作業中的一個任務調度至成員節點時的期望執行時間和調度可靠性。將任務調度問題形式化為混合整型線性規化問題，提出一種啟發式方法求解了任務至不同worker節點的最優映射策略。最后在網絡仿真環境對算法的性能進行了有效性評估。

1 車輛移動云模型

考慮一個車輛移動云模型，車載單元可與鄰近的車輛相互間提供傳感與計算服務，允許具有相對較低速度的同向車輛組成車輛集群，集群首CH基于MapReduce分布式計算模型負責管理任一成員節點的作業發送任務[11]。

1.1 車輛集群形成

道路車輛通常在高速移動，導致車輛間的拓撲結構快速變化、通信不穩定，且新的拓撲信息在所有車輛間交換時開銷增大。為了改善車輛間的信息流通，增加車輛移動云中的服務質量交付，同向移動的車輛可組成集群，集群首CH負責管理集群成員節點，并負責成員worker間的中繼訪問、流量控制、作業分解、集群worker間的任務分配、執行結果收集與返回。CH的選擇考慮車輛的可用處理資源及吞吐量性能(信道帶寬、車輛移動模式和MAC協議決定)。本文將擁有最高吞吐量與可用資源之積的車輛選擇為集群首CH。

1.2 作業執行模型

在每個集群中，利用MapReduce大數據處理模型進行任務處理。MapReduce是處理大量原始數據的分布式計算模型，它簡化了計算并行性、工作分布及機器可靠性，有助于車輛云計算應用開發者集中于具體的目標優化。

模型中，Map函數執行輸入任務的預處理，并產生中間結果(key,value)，表示為：

(1)

Map函數對輸入數據進行分類并將其置為就緒狀態。Reduce函數在中間結果ilist(key,value)上產生的輸出結果為：

(2)

車輛云計算的MapReduce框架如圖1所示。CH(簇首)可視為MapReduce框架中的master節點，其他成員節點可將其作業執行請求發送至CH節點。CH節點將作業分割為多個Map任務，Map任務為原子任務，即僅可成功完成執行或完全失效。Map任務在作為worker的車輛資源集合上進行調度。以上Map任務的結果被發送至另一worker資源集合，并在Map任務結果基礎上執行Reduce任務。Reduce任務的結果最終被發送至CH，并最后將結果發送至請求的車輛。

圖1 車輛云的MapReduce框架

在一個集群Cluster中，每個成員車輛的可用資源需要發送至CH節點。當車輛連接至一個CH節點時，需要廣播其傳感與計算資源信息至CH節點。被連接的車輛也需要周期性地發送其當前可用資源信息至CH節點，同時需要在CH上執行虛擬化過程以滿足云任務執行環境，并持續追蹤當前worker的所有可用資源信息。

圖2是車輛云計算結構模型和CH及其worker成員的系統組成。不在本地資源上執行的應用可發送至CH，利用車輛云計算系統進行任務執行。

圖2 基于MapReduce的車輛云系統

在作為CH的車輛中，Task Scheduler根據每個worker的能力分派任務至所選worker，worker的能力定義為其包含的時隙數量，一個時隙表示車輛上物理資源的可用性。在每個車輛上的Map與Reduce時隙數量是固定的，其時隙與內核比例由系統決定。每個時隙在給定時間內僅可運行一個任務。CH上的Task Coordinator需要周期性地檢查每個worker的連通性和可用性，并重新調度運行至集群外的worker任務，增強系統的可靠性。每個worker節點需要監測其擁有的可用時隙，并周期性地通過Heartbert消息告之CH，信息格式如下：

Heartbeat Genertor周期性產生包含可用時隙數量、當前速度、位置和加速度的Heartbeat消息，并發送至CH。Resource Monitor檢查時隙可用性、每個時隙中的任務隊列、每個時隙的負載及處理器負載以決定可用時隙的數量。Task Executor從每個時隙的輸入隊列中載入任務并追蹤每個任務的狀態。

本文相關符號說明如下：

J：車輛的一個作業請求；

M：車輛集群中所有成員worker集合；

Sm：workerm∈M的可用時隙集合；

B：無線信道的bit速率，單位bps；

vm：workerm∈M的指令執行速率；

δm：workerm∈M與CH間互連周期；

σm：workerm∈M與CH間互連周期；

pm(t)：workerm∈M與CH的連接概率；

α：響應時間與執行成功率間的相對權重因子。

2 車輛云中的最優任務調度算法OTS-VC

任務調度最優化問題即是以提高可靠性和降低任務響應時間為目標，進行任務執行worker群組的選擇。若任務執行結果在截止時間前返回，則認為所選worker與CH間未失去連通性，是可靠的。響應時間定義為任務提交至worker與任務結果返回的時間間隔。worker擁有越多數量的Map和Reduce時隙，越可以降低共享中間結果的通信延時。worker處理單元越快，響應時間也越快?；谝陨戏治?，本文設計一種目標函數用于選擇最優的worker集合，實現任務的執行并滿足預定約束。以下先給出響應時間和作業執行成功率的計算方法。

2.1 響應時間計算

作業響應時間由以下幾個部分組成：1) Map任務的傳輸時間；2) Map任務的執行時間；3) 發送Map任務結果至Reduce任務的時間；4) 執行Reduce任務的時間；5) 收集結果的時間。不同子任務的通信和計算時間在不同集群成員worker上是不同的，如：Reduce任務的處理在得到Map任務的結果后即可開始，無需等待所有其他Map任務完成。因此，傳輸與處理子任務的最大時間之和給出了作業響應時間的最差值。令M為可用worker集合，Sm為workerm∈M的可用時隙集合，二進制變量Ajms=1表明任務j∈J執行于workerm∈M時隙s∈Sm中，否則，Ajms=0。

CH將作業J分割為j′個子任務，通過Map時隙執行，并將執行結果發送至J-j′個Reduce任務。函數f′()和f″()分別表明執行Map和Reduce任務時的指令。因此，所有Map和Reduce任務集合可表示為：

J={x1,x2,…,xj|(?j>j′,?j″≤j′)xj=f′(xj″)}

(3)

選擇worker中合適可用時隙數量j調度Map和Reduce任務。令Y為Map和Reduce任務的輸出成分集合，表示為：

Y={y1,y2,…,yj|(?j>J)yj=
f′(xj|j≤j′)∨f″(xj|j>j′)}

(4)

f′(xj)和f″(xj)的執行時間取決于不同的應用類型。每個worker發送帶有其鄰居worker的連接列表至CH。根據接收的連接列表，CH創建一個二維連接矩陣C，其元素定義為：

(5)

式(5)的條件1表明Map和Reduce任務可在同一worker的不同時隙中執行。最優任務調度方法在分配不同的Reduce任務至worker的可用時隙時需要最小化Cmn值。假設所有worker與CH間的所有信道擁有相同的bit速率，為了計算Map任務和Reduce任務的傳輸與執行時間，任務中花費傳輸與執行時間最長即為總執行時間(由于不同worker的傳輸與執行可并行)。令B為無線信道的傳輸bit速率，workerm接收Map任務的傳輸延時為：

(6)

由于車載計算單元擁有不同的計算能力，任務xj的執行延時在不同worker上是不同的。對于任一j∈J|j≤j′，workerm處理Map任務時計算任務xj的延時為：

(7)

任意worker完成Map任務后，傳輸結果至|J|-j′個Reduce任務的延時為：

(8)

對于任一j∈J|j>j′，workerm處理Reduce任務時計算任務xj的延時為：

(9)

最后，Reduce任務結果傳輸至CH的傳輸延時為：

(10)

綜合式(6)-式(10)涉及的所有延時，作業的總體響應時間為：

(11)

若作業中的任務在本地完成，需要的時間為：

(12)

式中：vo為單個時隙中的指令執行速率，So為可用時隙數量，vo×So則表示所有可用時隙中指令的執行速率；f′()表示執行Map任務的指令數，f″()表示執行Reduce任務的指令數；J為任務集合，j′為任務分割點，即j≤j′為Map任務，j>j′為Reduce任務。分子即代表所有Map任務和Reduce任務的總指令數，總指令數除以執行速率即可得到作業的執行時間。

2.2 調度成功率計算

與CH連接概率越高，車輛worker在截止時間內執行任務的可靠性越高。由于worker的位置與速度具有高度動態性，選擇worker時必須考慮可靠性，從而避免失效與延時增加。若作業請求者脫離集群或應用執行發生逾期，則任務的截止時間T也將逾期。在截止時間T內完成任務概率越高的worker，選擇為計算目標的概率也越高。該概率利用車輛worker與CH的連接率進行計算。workerm的連接率定義為δm=1/E[σm]，σm為workerm與CH間的互連周期。

(13)

(14)

式中：二進制變量ζm表示worker m的時隙可用性。若worker m至少擁有一個空閑時隙，則ζm=1；否則，ζm=0。為了增加作業執行成功率，在進行任務分配時需要最大化所有任務的執行成功率。作業J的所有任務的整體執行成功率可表示為：

(15)

2.3 最優化問題的形式化

(16)

式中：α表示權重因子，給出作業完成時間和執行成功率的相對優先性。一些應用可容忍延時，但需要更高的執行成功率，一些實時應用則側重作業完成時間而忽略執行成功率。作業發送至CH時，請求方可具體描述執行作業的響應時間Ir和成功率Is，并通過下式計算權重因子：

(17)

2.4 優化約束

1) 分配約束：

Ajms={0,1} ?j∈J,m∈M,s∈Sm

(18)

(19)

式中：Ajms表示分配因子。若Ajms=1，則表明任務j∈J執行于workerm∈M時隙s∈Sm中；否則，Ajms=0。式(18)說明對于給定時間內，一個任務至多只能分配至一個worker的特定時隙中，式(19)則確保一個任務僅能在單個worker的單個時隙中執行，不能進行任務分割。

2) 作業完整約束：

(20)

式(20)確保作業中的每個任務必須分配至worker中任一時隙中執行，不可丟棄任務或不對任務分配時隙。

3) 能力約束：

(21)

式(21)確保分配至worker的任務數量不可超過其能力。

4) 時隙可用約束：

|J|≤∑?m∈M|Sm|

(22)

式(22)確保所有worker中的總體可用時隙總量需大于或等于作業中的任務數，否則，作業執行不可行。

5) QoS約束：

(23)

(24)

式(23)確保車輛移動云中的作業執行時間需小于作業本地執行的時間，式(24)確保所有任務需在截止時間內完成。

2.5 啟發式任務調度算法

本節設計一種啟發式算法以更低的時間復雜度得到任務調度的最優解。算法可確保所選worker具有如下屬性：對于給定的任務j，所選worker需滿足最小執行成功率閾值pj，且得到的任務執行時間最小，從而得到最小化Z。即對于所有worker，以下不等式成立：

(25)

對于每個任務j的最小執行成功率閾值pj計算為：

(26)

式中：

(27)

算法1啟發式任務調度算法

Input:J,M,Sm,α

Output:Ajms

[1]SΩ←?

[2]Ajms=0|j∈J,m∈M,s∈Sm

[3]foreach taskj∈J

[4] calculateαusing Equ.17

[5]foreach workerm∈M

[7]endfor

[8] calculatepjusing Equ.26

[10]ifMp=?then

[11]exit

[12]endif

[13]foreach slots∈Sm|m∈Mpdo

[16]foreach slotwinSΩdo

[18]endfor

[19]endfor

[21]Sm←Smsj

[22]SΩ←SΩ∪sj

[23]Ajms=1|s=sj&sj∈Sm

[24]endfor

算法時間復雜度分析。步驟3-步驟24的循環需要迭代J次，步驟5-步驟9擁有相同時間復雜度O(M)，步驟13-步驟19在最差情況下迭代Sm次，其內層步驟16-步驟18迭代SΩ次，SΩ?Sm。因此，算法的總體時間復雜度為O(JM+JSm2)≈O(JSm2)。

3 仿真實驗

3.1 實驗環境

利用Hadoop MapReduce仿真器MRPerf[12]和車輛移動仿真軟件SUMO[13]進行車輛云計算中的任務調度模擬。MRPerf可生成Map和Reduce任務的數據和流量，SUMO可仿真城市車輛移動和車輛行為，模擬道路負載。兩種仿真器可并行運行于網絡仿真器NS3中。

實驗設置每公里道路區域內有20～50輛車，速度為36～90 km/h，每輛車的傳輸范圍為100 m，利用SUMO生成城市環境為500 m×500 m的正方形區域，每條道路的250 m處有一個轉彎道。利用WAVE(IEEE802.11p)實現車輛間的數據傳輸，該環境下擁有7條無線信道，信道速率為6 Mbit/s。每個數據包大小為1 024 bytes，每輛車擁有2～6個Map或Reduce任務，每個Map時隙和Reduce時隙分別配置1 500 MIPS和2 000 MIPS。每個worker包含1 GB或2 GB RAM和40～100 GB的存儲。實驗中每分鐘生成2～8個應用，每個應用包含10～20個任務。每個任務的指令不同，故其執行周期也不相同。設置Is=6，Ir=4，heart-beat消息發送間隔分別設置為80 ms和40 ms，對應兩種版本算法OTS-VC-80和OTS-VC-40。選擇同為車輛云中的調度算法TSBIP[6]和BSS[7]作為性能對比算法。

3.2 性能指標

1) 作業的平均執行時間：個體作業的執行時間定義為作業發送時間與接收返回結果的時間間隔，平均值為所有作業的執行時間的均值。2) 調度成功率:當CH接收到執行任務的所有worker的返回結果時，即認為作業執行是成功的。那么，成功執行作業的比例可用成功完成的作業數量與仿真期間的總作業數量的比值得到。3) 系統吞吐量：單位時間內執行的作業數量。4) 任務執行開銷：表示Map和Reduce時隙中的實際任務執行時間與總體響應時間的比例，定義如下：

(28)

3.3 實驗結果

1) 車輛密度的影響。增加worker數量會增加可用資源量，降低作業執行時間，但同時會增加worker間的數據傳輸干擾，導致數據傳輸時間增加。圖3-圖4是改變車輛密度時的性能表現，此時令作業到達率為6 jobs/min。圖3表明所有算法的作業平均執行時間會隨車輛密度增加會劇烈下降，這是由可利用的worker資源增加導致的。同時，車輛密度到達40后，執行時間趨于穩定。本文算法在平均作業執行時間方面優于TSBIP和BSS，這是由于OTS-VC所選車輛可以降低執行時間，提高可靠性，進而導致任務執行、任務重調度重處理及數據重傳輸的平均時間大幅降低。由于OTS-VC-40擁有更高的heart-beat消息傳輸頻率，導致網絡中消息沖突會隨著車輛密度增加，這也解釋了該算法為何得到了相對更低的可靠性和更高的作業執行時間。作業執行成功率隨著車輛密度呈指數級增加，達到穩定點后略成下降趨勢，原因在于：系統在車輛數量、數據傳輸量和控制信息數據包增加到一定程度時會出現擁塞，降低系統性能。本文算法擁有更高的任務執行成功率、更低的任務執行與數據傳輸延時，以及成功執行作業比例。由于OTS-VC-40算法中heart-beat消息傳輸頻率更高，數據包沖突會隨著車輛密度增加，導致其作業執行成功比例下降。圖4表明，任務調度的吞吐量增加到一定程度后會開始緩慢下降，原因同上。本文算法得到的吞吐量仍高于另外兩種算法，這是由于OTS-VC選擇的worker擁有最小的數據處理和傳輸代價，這樣可以降低任務的重處理代價。TSBIP和BSS的吞吐量性能隨著車輛密度的增加出現了交叉，前者利用分布式方法，后者利用了集中式調度方法，開銷更高，車輛規模會對其產生更大影響。

圖3 車輛密度對平均執行時間和執行成功率的影響

圖4 車輛密度對吞吐量的影響

2) 作業到達率的影響。圖5-圖6是車輛密度為30時作業到達率對算法性能的影響。圖5表明，任務執行延時會隨著作業到達率的增加呈指數級增加，這是由于車輛資源上增加的計算負載會導致更多的任務重調度、重處理、數據傳輸時間，用于任務處理的時間則相對較少。OTS-VC相比另外兩種算法擁有更低的任務執行時間，由于前者在鄰居節點中選擇了可靠性更高的計算資源，使得可以一定程度降低任務處理、重處理及重調度的時間。此外，任務重處理重調度數量增加也會導致消息傳輸更加頻繁，進而導致更大的任務執行延時。同時，作業執行成功比例會隨著作業到達率的增加呈指數級下降，這是由于增加的系統負載會迫使系統選擇能力較差的節點執行任務。本文算法在選擇worker時考慮了任務執行成功率，因此擁有相對更高比例的任務成功執行量。OTS-VC-40性能較差，由于控制數據包的沖突會隨著作業到達率增加而變得更加劇烈。圖6表明，本文算法的吞吐量更高，由于算法在單位時間內可執行更多的任務，將任務重調度、重處理與數據重傳輸時間降低止最小。

圖5 作業到達率的影響

圖6 作業到達率對吞吐量的影響

3) 任務執行開銷。圖7-圖8研究了車輛密度和作業到達率對任務執行開銷的影響。圖7表明，車輛密度增加時系統開銷呈指數級增長。本文算法執行開銷更小，由于算法可以避免任務重調度和重處理，系統的管理開銷相對更小。OTS-VC-40相比OTS-VC-80開銷更高，由于前者在消息傳輸失效時需要進行任務重調度。圖8表明，系統開銷會隨著作業到達增加呈指數級增長。本文算法執行開銷更小，由于算法選擇的worker是傳輸延時最小的，這樣任務重處理的概率將大幅減小。

圖7 車輛密度對開銷的影響

圖8 作業到達率對開銷的影響

4 結 語

為了實現車輛云計算環境中任務的可靠性調度，本文提出了一種滿足截止時間的任務調度算法。算法為了同步優化任務調度時間和任務調度可靠性兩個目標，將任務調度的最優車輛選擇問題形式化為混合整型線性規化問題，并設計了一種低時間復雜度的啟發式任務調度方法對該問題進行求解?；诙喾N仿真平臺的結合對車輛云計算的任務調度進行了仿真模擬。實驗結果表明，該算法在調度時間和調度成功率方面均優于比較算法。