## LARS: A Latency-Aware and Real-Time Scheduling Framework for Edge-Enabled Internet of Vehicles

[A Latency-Aware and Real-Time Scheduling Framework for Edge-Enabled Internet of Vehicles](https://ieeexplore.ieee.org/document/9519531)

## Introduction
近年來，**車聯網（IoV）** 和 **邊緣運算** 等議題引起了廣泛關注。隨著硬體資源的不斷發展，行動裝置或是一些可移動裝置需要處理更龐大的運算任務和更多的傳輸資源，以滿足即時的計算需求。然而，傳統的集中式運算由於傳輸延遲、安全性等問題而難以有效應用於車聯網。這就是**邊緣運算**發揮作用的地方，它提供了解決集中式運算問題的有效方法。

然而，邊緣運算需要大量的硬體設備，如邊緣伺服器和儲存設備，這導致成本相對較高。雖然一些論文提出了利用閒置車輛的運算能力來實現邊緣運算，但這些方法往往沒有充分考慮實際情況，**如車輛的移動性或交通的變動性等因素**。此外，許多論文針對的邊緣運算問題往往是**獨立且缺乏相關性的**，而在現實情況下，許多運算程序是相互關聯的，需要考慮先後順序、資料傳輸等問題。因此，本文提出了更實際的方式來解決這些問題。

總之，隨著車聯網的發展，邊緣運算成為解決即時計算需求的關鍵方法。然而，傳統的硬體建置方式存在成本高昂的問題，本文提出的 "**Herds**" 概念則針對實際情況進行了優化，以更有效地支援車聯網的運算需求。

:bulb: 本文主要探討以下幾個議題:
* **城市中車流量以及邊緣運算的可行性。**
* **考慮到車輛的移動性以及實時的交通情況如何建置邊緣運算系統(分群)。**
* **車輛所需計算程序之關聯性以及順序和合理的分配至邊緣運算系統。**

## Observation & Systemodel
本節敘述城市車流量以及交通觀察和系統簡介
### Observation
本系統實際觀察中國深圳的交通資料，該資料集包含了2013年10月22日整天超過10,000輛計程車的相關資訊。
:arrow_up_small:**(fig.1)The mobile vehicle distribution at different time of a day**

:paperclip:從圖中可以觀察到，在**午夜12:00至凌晨4:00之間**，車輛活動數量最少，而其他時間段則有相對較高的車流量。本研究選擇了**當日18:00至18:05這段時間**，對整個城市的車輛活動進行觀察，並將**車輛活動較活躍的地區標記為熱點區域(Hot pots)**。
**:arrow_up_small:(fig.2)Hot pots in the city during 18:00-18:05**

:paperclip: 上圖顯示，在這段時間內，熱點區域對城市的覆蓋率相當高。

本研究進一步深入探討了這些熱點區域。由於**LTE這項通訊技術較適合用於V2I(車輛與基地台間的通訊)**，而LTE的通訊範圍**約為2km**，因此我們隨機從熱點中選擇某地點，並在該地點周圍2km範圍內計算車輛數量，以確認基礎設施通信範圍內是否存在足夠的車輛進行邊緣運算。
:arrow_up_small: **(fig.3)** 從選定的區域中，平均每個地點的車輛數量約為**183輛**，這一數字顯示城市內**擁有足夠的汽車數量進行邊緣運算**。這突顯了在城市環境中實施**邊緣運算的可行性**。

此外，車輛與車輛（V2V）之間的**分群管理**也是一個極為重要的議題。本文引入了"**Herds**"的概念，將**位置和運算資源相近**的車輛結合成群，共同提供計算服務。同時，考慮到V2V之間的通信通常**採用DSRC標準**，而該技術的通訊範圍**約為300m**。因此，本研究進一步觀察了車輛之間距離在300m內的機率。
:arrow_up_small: **(fig.4)** 從觀察**Table 2**中點A區域的結果可知，**在距離300米以內的機率約為0.45**，這表示**大約有95輛車**的距離在300米以內。這樣的結果顯示了"**Herd**"概念**具有足夠的車輛數量進行邊緣運算**，進一步證實了"**Herd**"**的可行性**。

### System Model
:arrow_up_small: **(fig.5)**
* **Controller(RSU)** : 車輛資訊蒐集、資源調度、任務分派。

* **Herds** : 由車輛群體組成，被當作車輛邊緣運算系統中的一個運算單位。

* **Jj = {tarrive_j, Gj}** : 表特定需要被邊緣運算的程序，其中 **tarrive_j** 表示程序被請求的時間；**Gj表程序關聯性關係圖(如fig.6)**

:arrow_up_small: **(fig.6)** 圖中的**ti表示程序中不同的tasks**，**li,j表示tasks之間相互的依賴關係**。

文中對任務中相互依賴的tasks舉了一個實際的例子:
**fig.6(a)代表了一個車輛監控任務**。當監視器所蒐集的影像被收集後，會**同時輸入到任務 t1 和 t2 進行預處理**。接下來，t1 的處理結果將被傳遞給 **t3用於行人行為分析**，同時也傳遞給 **t4用於車輛辨識**。另一方面，t2 的結果將會被傳遞給 **t5用於車牌識別**。最終，任務 t6 將整合所有的處理結果。

另外，fig.6(b)中的t3、t5為"**可選擇**"的tasks，這表示**t6只須接受t4以及t3和t5其中之一結果即可完成目標**。這樣的task作者使用**藍色**進行標記。

## LARS FRAMEWORK DESIGN
:arrow_up_small: **(fig.7) The architecture of LARS framework**

fig.7中所展示的是整個LARS的系統架構，用戶的應用程序被分成好幾個Task並透過LARS的API將工作交付給LARS平台，**LARS平台將不同的Task分配至合適的Herd進行運算**。

❗❗ **將程序分割成Tasks的方式以及Herd轉移問題不在此論文的討論範圍內。**

### Controller
:arrow_up_small: **(fig.8) Herd generator**

城市中的Controller如上圖所示，會定期蒐集附近的**車輛的Mobility state以及Resource state**。
* **移動狀態(Mobility state)** : 位置、移動速度、衛星導航軌跡。
* **資源狀態(Resource state)** : 車輛可用資源量(算力)、車輛可用時間。

當有汽車**進入**或**離開**該 Controller 所控制的範圍時，會向 Controller 提出**註冊(Register)** 或 **釋放(Released)** 的訊息，使得Controller能夠對範圍內的車輛進行**分群以及可用資源量計算**。
## Dynamic Scheduling
此部分包含 **Generating Herds**、**Problem Formulation**、**Task Scheduling Scheme**。
### Herds Generator
**GetHerds Algo.**
本演算法目標在於將區域內的車輛**特徵相近**的汽車進行分群，以實現每一個Herds都有**相近的可用時間、計算資源**等。
其中 **Mv(t) = <Lv, Sv, rv>** 表每台車輛的移動狀態，**Rv(t) = <Cv, uv>** 表每台車輛可用資源狀態。

**Mv(t)**
* **Lv** : **車輛位置**
* **Sv** : **車輛移動速度**
* **rv** : **車輛衛星導航軌跡**

**Rv(t)**
* **Cv** : **車輛資源量**
* **⊖v** : **車輛可用時間**

**GetHerds Algo(line 2-4)** 為 **(DR)**。
**GetHerds Algo(line 6)** 透過呼叫 **K-meansBasedCluster()** 來對車輛進行分群形成Herds。
**GetHerds Algo(line 8-10)** 在(line 2-4)更新車輛狀態資訊時，會需要呼叫此子函式來做車輛位置更新。
**GetHerds Algo(line 13-18)** 此部分為K-means的分群前置作業(初始群心挑選)，首先先選擇一個隨機的車輛作為第一個群心，接著計算其他車輛與該群心之距離，**選擇距離最遠之車輛作為第二個群心**，若要將所有車輛分為n個herds，則反覆此步驟直到n個初始群心皆被找到為止。
### Offloading Controller
* **Acceleration Evaluator** : 用來評估應用程序被分割並交付由邊緣裝置(Herds)進行運算的**加速效果**，以評估task交付給其他**車輛群進行運算的必要性**。
:arrow_up_small:Equation (1)(2) 為兩種**評估加速效果**的方法。
**Cacc_i** 表示**單個**任務(無法併行處理之Task)的**計算加速度**。
**Cacc_i'** 表示**平行處理**任務(可併行處理之Task)的**計算加速度**。

* **Equation(1)** 中的**Wi代表著task的運算量**，而**Pj表示著本地的IOT裝置算力**，另外**di代表著該task所需輸入的資料量大小**、**rj則是Controller和IOT裝置之間的傳輸速度**。最後l'代表著將task由IOT裝置分派給邊緣汽車群計算再將計算結果回傳所需要的**總來回傳輸時間**。
由 **Equation(1)** 可得知該task在**本地運算**和**分派給車聯網運算**之**花費時間比例**。

* 在**Equation(2)** 中，**I'代表可以平行運算的任務集合**，**Nworker_local表示本地可執行計算的單位數量（也就是核心數量）**，**Pj則代表本地的物聯網（IOT）裝置的運算能力**。因此，我們將所有**可平行運算的任務（Wi，i∈I'）的運算量相加**，然後除以**本地可執行計算單位數量(Nworker_local表示本地可執行計算的單位數量)**，就可以計算出每個單位所需的**平均算力釋放**。接著，再除以本地核心處理速度，就可以得知這個任務集合在**本地計算上需要花費多少時間**。
同樣地，**Nworker_m表示某個 Herd（處理器集合）中的車輛數量**，也就是計算單位的數量。特別的是，我們需要計算在**任務 Wi 分配給 Herds 中的哪個車輛群所占用最多時間的組合（max(i∈I0, m∈M))**，以確認即使在可能需要花費最長時間的情況下，仍然是否小於本地運算時間。**確保了整體處理時間是否優於本地計算時間**。
由**Equation(2)** 可得知**可平行化tasks**集合在**本地運算**和**分派給車聯網運算**之**花費時間比例**。

==**若Cacc_i > 1** or **Cacc_i’ > 1** **本地運算所花費時間>邊緣運算時間**，適合將此**Tasks分配至Herds進行運算**==。
**Offloading controller** 會將此結果加入工作集合 **T_off{t1,t2,t3,t4,...,tn}**，以做後續的運算分配。
### Job Assigner
==本系統的主要目標為 : 為每個Tasks找到具有**最大加速的Herds**和**最低的處理成本**。==
* P1為本系統目標函式，透過α β 兩個介於0-1之間的權重來表示系統注重於透過Herds提升處理速度(α)抑或是降低成本(β)
* 3(a):

### Task Scheduling
#### **Problem Formulation**
* task_i開始時間為 task_i之所有前置task中結束時間+傳輸給task_i時間中最大的值作為task_i預期開始時間。
* 某個job結束時間為所有task中最晚的結束時間。
* 本系統目標為盡量的減少 **job到達時間 - job結束時間**
#### **Theoretical Analysis**
此章節將敘述如何在LARS框架中執行任務調度，分成兩個步驟。
* **將任務分配到適當的工作單位。**
* **對工作調度進行合理排序。** (參考MESTF方式進行排序)

**THM1** : **MESTF Rule** **越早**可開始的task優先安排。

**THM2** : 由不同處理器處理某個task_i的k個前置task_j的前題下，先針對前置task_j作根據tas_j運行時間+task_j由該處理器傳輸至task_i之時間由大到小作排序。接著 1<=l<=k 做測試，舉例來說若l = 2 將task_1 、task_2做MESTF排班結束時間與 task_3運行+傳輸時間做比較，取大的代表task_i最早可開始時間。

**THM3** : **Tend_i <= T^end_i** 未排班的任務根據已排班的任務計算截止時間需要小於或等於T^end_i 才不會影響到後續的任務執行。

#### 📌**Greedy-Based Task Scheduling Algorithm**
> #### **GBTSA (Greedy-Based Task Scheduling Algorithm)**
> 

>##### **Introduction**
>此演算法旨在透過**Greedy**的方式，目標為**盡可能的提早每一個task的完成時間**並將tasks**合理的分配至每一個workers**。

>##### **Algorithm Overview**
>The GBTSA algorithm consists of 2 key steps:
>* **Procedure Preparation** : 此部分為排班的前置作業，當一個job到達時，先將該job內所有tasks放入 waiting Queue準備進行排班，再由Queue中挑出 **沒有前置任務的tasks** or **前置任務已經被安排**的tasks進行scheduling。
>* **Procedure Schedule(ti)** : 此部分透過迴圈的方式反覆測試不同 task在不同worker上的效果，並試圖找到能夠最小化task完成時間的方式

>##### **Initialization**
>初始化所有變數 :
>- **WorkerS** (Herds中所有汽車)
>- **WaitQ** (待執行tasks)
>- **ExcuS** (執行中tasks)
>- **ProT** (準備排程的tasks)
>- **reTaskS** (需重複執行的 tasks)

>##### **Preparation (Procedure Preparation)**
>- 從WaitQ中選出**不須前置tasks** or **前置tasks已經在ExcuS** task 加入**ProT**。
>- 從 **ProT** 中對個別task_i 找出t_opt(其他可選擇的task)，若已存在ExcuS，則將該task_i從ProT移除。
>- 將**ProT中**的每個 task 依序 Schedule。
>- 得到排程結果並將reTaskS、task_i 和 Selected worker之ExcuS中tasks根據MESTF執行。

>##### **Scheduling (Procedure Schedule)**
>1. 計算 task_i **Effective end time(T^end(ti))**。
>2. 將task_i逐一分配給不同的workers，以**MESTF方式排班**計算Task_i**有效完成時間(T_end(ti))**。
>3. 若當前 **T_end(ti)** < **Effective end time(T^end(ti))** 則結束迴圈，將該task分配給此worker。
>4. 若當前 **T_end(ti)** > **Effective end time(T^end(ti))** 則根據定理2，找出該task前置tasks中完成時間+傳輸到此worker時間**最長**的task重新安排至此worker，並利用MESTF排班，重新計算T_end(ti)，若小於前一次T_end(ti)則更新其值，持續迴圈尋找直到找到最小的T_end(ti)值為止。
## EXPERIMENTS AND EVALUATION
本節針對 **GetHerds** 和 **GBTSA** 兩部分做性能評估。
### Simulation Results for GetHerds
:arrow_up_small: **(fig.9) The snapshot of vehicles at time 18:00**
此實驗使用Shenzhen city 18:00 on October 22, 2013 經緯度(114.143951, 22.554733) 的位置當作控制中心，而fig.9顯示控制中心2km的覆蓋範圍，紫色點代表當下的汽車。本實驗隨機為每一台車輛生成**資源量**(介於4-6資源單位)及**可用時間**(介於3-5分鐘)。
:arrow_up_small: **(Table.1)**
Table.1顯示了每個Herd中平均車輛距離皆小於300m，滿足了車輛之間的DRSC通訊標準。此外不同車輛群體的時速差異也大多在時速3km/hr以下。可用資源量的平均差異在1左右而可用時間平均差異大多小於10秒。
:arrow_up_small: **(Table.2)**
**Table.1**顯示了每個Herd中平均車輛距離**皆小於300m**，滿足了車輛之間的DRSC通訊標準。此外不同車輛群體的時速差異也大多在**時速3km/hr以下**。可用資源量的平均**差異在1**左右而可用時間平均差異大多**小於10秒**。
**Table.2**再增加分配的herds數後能夠更縮小化**各個worker之間的平均差異**。

==由以上結果得知每個生成的群體的移動性和資源狀態相似，並可以保持穩定的周期以提供計算服務。==
### Experiment on Testbed
此章節主要在測試評估GBTSA之效能。
#### Evaluation Setup
:arrow_up_small: **(fig.10) LARS system implementation**
* **邊緣節點（Edge Nodes）**：這些節點被視為擁有穩定和可用狀態的群體（Herd），每個節點都被看作是群體的計算工作者，用樹梅派來模擬。
* **控制器（Controller）**：一台電腦被用來負責資源調度和管理，作為控制器的角色。
* **生成應用程序（Generate Applications）**：一台筆記型電腦被用來生成應用程序，並決定是否將這些應用程序卸載到LARS框架中。
* **硬體規格（Hardware Specifications）**：
這些設備和邊緣節點之間透過 socket 相互連接。
* **工作模擬（Poisson Arrival Process）**：使用PythonSimPy工具模擬工作的到達過程，並通過到達率來控制工作的到達速度。到達率從範圍[0.2, 0.5]中隨機生成。
* **應用程序驗證（Application Verification）**：使用了兩個真實世界的應用程序來測試GBTSA的性能。
* **穩定工作時間（Stable Working Time)**：為了防止任務遷移，假設群體的穩定工作時間要大於所有任務處理所需的時間。
#### Baselines
1. **Local（本地）**：這意味著所有作業的所有任務都在本地處理。

2. **Random（隨機)**：控制器將隨機選擇一個Herd中的工作者來處理卸載的任務。

3. **Shortest Transmission Time First (STTF)（優先最短傳輸時間）**：控制器傾向於將任務安排給**傳輸時間最短**的(控制器到worker)邊緣裝置上。

4. **Shortest Queue Length First (SQLF)（優先最短佇列長度）**：控制器傾向於將任務排程給在查詢時間時具有**最少排隊任務**的工作者。
##### **Case study**
本研究透果兩個實際的 Program 來模擬本系統的實驗結果。

**Case 1** : **Use ADE20K dataset provided by
MIT for Scene Understanding Experiments**
透過ADE20K資料及對圖片中的場景、物體等做辨識。
:arrow_up_small: **(fig.11)**
**fig.11** 顯示了場景辨識實驗中可能會出現不同Job的tasks之間的相依性，其中fig.11( c )、fig.11( d ) 中不同顏色(藍、綠)的tasks皆為 **可選擇(optional)** task，也就是同一個顏色擇期一即可。

:arrow_up_small: **(fig.12)**
**fig.12**顯示五種方案下的20個jobs的響應時間，GBTSA在處理20個job中都是響應時間最短的。
:arrow_up_small: **(fig.13)**
從**fig.13(a)** 中各項花費時間佔比分析，可得知GBTSA花費較多的時間在不同汽車之間或是汽車與控制器之間的**傳輸工作**，因此傳輸速物的加速是未來可提升此系統效能的一大關鍵。
:arrow_up_small: **(fig.14)** Average workers versus different number of jobs.

關於資源利用率的問題，可觀察到無論多少工作，GBTSA這個方法的參與workers數量接接近4，都大於其他方法，由此可見此方法能夠有效利用所有workers資源。

**Case 2** : **Driving Behavior Detection**
**駕駛行為檢測**，安全監控在交通感測應用中使用捕獲的車輛圖像來檢測危險行為。例如，一個位於路口的監視攝像頭可以捕獲正在開車時使用手機的駕駛員，然後將危險信號提醒交通警察。在這個案例研究中，使用了Berkeley DeepDrive數據集來進行駕駛行為檢測實驗。

:arrow_up_small: **(fig.15)**
**fig.15** 顯示五種方案下的20個jobs的響應時間，GBTSA在處理20個job中大多響應時間最短的，然而有幾個工作響應時間略高於SQLF方法，作者認為此原因來自於通訊不穩定。

:arrow_up_small: **(fig.16)**
從**fig.16(a)** 中各項花費時間佔比分析，可同樣得知GBTSA花費較多的時間在不同汽車之間或是汽車與控制器之間的**傳輸工作**，因此傳輸速物的加速是未來可提升此系統效能的一大關鍵。
:arrow_up_small: **(fig.17)** Average workers versus different number of jobs.
關於資源利用率的問題，可同樣觀察到無論多少工作，GBTSA這個方法的參與workers數量接接近4，都大於其他方法，由此可見此方法能夠有效利用所有workers資源。
## Conclusion
這篇論文的分析結果，我們驗證了在深圳的真實交通數據集上形成「Herds」（類似群組或集群）在邊緣使用「Internet of Vehicles（IoV）」進行邊緣運算的可行性。為了更好地管理車聯網中的計算資源並有效提供計算服務，我們設計了一個動態調度 LARS。在 LARS 中，我們提出了一個基於「K-means」的聚類算法 GetHerds 來生成「Herds」。應用程序的任務應該經過評估，以確定是否可以從卸載到「Herds」中獲益。對於卸載的工作，控制器中的作業分配器首先選擇適當的「Herds」，然後使用基於「貪婪算法」的任務調度算法 GBTSA 來調度任務到適當的工作者並對每個工作者上的任務進行排序。基於真實交通數據的模擬實驗顯示，由 GetHerds 生成的「Herds」可以保持穩定的週期以提供計算服務。在測試平台上進行的實驗包括兩個案例研究，表明 GBTSA 在減少作業的總延遲方面表現良好，同時最大化了邊緣啟用的「Internet of Vehicles（IoV）」的資源利用率。來自測試平台的實驗結果顯示，通信時間是導致作業總延遲的瓶頸因素。基於這一觀察，作者將建立一個基於「5G通信」的實驗環境，以使應用程序的計算卸載到「IoV」更加真實。