## Multiagent Reinforcement Learning-Based Cooperative Multitype Task Offloading Strategy for Internet of Vehicles in B5G/6G Network

### system model - network model

在一個system上, 會有 M 個 edge server (ES) 使用 ℳ={1,2,3,…,𝑀} 表示

接著, 使用 𝐹={𝑓_1, 𝑓_2, …, 𝑓_𝑀}表示 ESs 的 computation power, 單位為 CPU frequency

對於每輛車子能發出的任務類型, 使用 𝒯={1,2,…,𝑇} 表示, 實驗方便, 每輛車子一個時間點發出的 𝒯 集合大小相同

對於每個任務類型的特性, , 𝑛∈𝒯, 𝑐_𝑛^𝑡 表示 size of the computation task (CPU cycle), 𝑠_𝑛^𝑡 表示 size of input data, 𝑑_𝑛^(𝑡,𝑡𝑜𝑙𝑒) 表示最大可容忍延遲。任務的大小會影響該任務的負載。

### system model - Offloading model

 表示 ES m 的最大 computation resource.

, 其中表示在 ES m 上的第n個類型的任務在 t 時刻造成的負載, 此外本篇論文假設任務是 fine-grained, 所以可以任意比例的分配給不同的 ES 執行處理任務

 表示為 ES m 在時刻 t 的卸載策略, 表示將 nth-type 任務卸載給 ES 𝑚_1 的比例, 𝑚_1∈ℳ, 

### Delay model - Computation Delay

延遲的部份分成兩個, 一個是計算所需的時間和傳輸任務計算資源的時間, 首先是
#### computation delay

表示 ES m 在 t 時刻的compuation power, 相當於可以同時處理幾個任務, 和前面的不一樣

根據queuing theory 的 W = 𝜌/(𝜇−𝜆) 可以寫下在 ES m 上第 nth-type 的任務在t時刻的 queuing delay：


這是任務在等待列隊中等待的時間, 需要特別注意的地方是分母的減號後面使用了一個假設, 也就是穩定狀態下, 某個edge server把任務分給其他ES的情況相當於其他ES分給本edge server的情況, 原因是, 在原本的queuing theory中 𝜆 代表到達率, sum中的a為ES m 給ES m_1的比例

接著是實際計算的時間, 表示在ES m上第nth-type的任務的computation delay：

所以total delay  為：

會有 𝒳2 的原因是, 我們把任務分給其他edge server, 所以一個任務的完成不僅僅只有本地 ES 處理完, 還要等待其他 ES 處理完

#### communication delay

ES 間通過 fiber-wireless 傳輸 data。ES 在通訊時, 會有bandwidth division 和 channel interference 問題。簡單起見, 假設一對 ES 通訊的傳輸速率固定, 使用 表示

通訊時的queuing delay也是根據 W = 𝜌/(𝜇−𝜆) 可以寫下 ：

會有這個 delay 的原因是接收任務也是一個一個接收, 一個一個傳送, 所以也會有排隊的問題, 其中

所以total delay如下, 

後半為實際傳輸的時間量

### Delay model – Problem Description

所以將上面兩種 delay 加總如下：

所以目標就是最小化這個 delay：

a,b,c 為條件

其中, , 這代表在 ES m 上第nth-type的任務的平均延遲

而分子的部分分別為

### MDP

C- 為懲罰, 因為我們不希望負載低的 ES 將任務卸載給高負載的 ES, 所以把這些負載的加總作為懲罰

### SAC

梯度公式和以往一樣


#### Offloading Algorithm Based on ISAC

因為車聯網的環境變化快速, 且變化頻繁, 所以使用 priority replay buffer, 學習那些比較需要學習的訓練資料, 並希望快速收斂, 不然 agent 還沒學到怎麼做, 環境又改變了

 代表 the complexity of the jth sample in the experience replay buffer, 主要由  和  定義

如果目前 sample 到 jth 資料的頻率較低, 則提高它下次被採樣到的機率

如果目前 sample 的 jth 資料 Q 值還沒收斂, 下次採樣到的機率也會較高

此項為 TD error


此項為 TD error 的係數, 由於 的 R_j 必為負數, 而熵必為正, 所以也就是說, 當某個 sample 亂度較大時, 代表這個 sample 更重要, 需要多加訓練, 另外, 延遲和懲罰的加總很小(負值), 則係數不要成長太大, 因為 TD error 可能已經很大


所以針對每個 sample 的抽取機率如下
這個係數主要是避免distribution error的問題, 也就是說抽的sample沒有均勻分佈, 所以導致某部分的sample抽太多了, 導致那部分會overfitting, 而部分的sample反而都沒有抽到


### ISAC-Based Solution

此部分和以往的SAC差不多

**Offloading strategy**

**Temperature parameter**



### Distributed Offloading Algorithm Based on ISAC

這裡使用常見的集中式訓練 critic, 分散式執行 actor, 以下是其tuple


要注意, 只有 critic 會看到全域資訊, actor 只能看到本地資訊

### algorithm


這裡要特別注意, 第19行作者有寫錯, 網路的參數更新理應要和第15行的 delta 有直接關係, 但公式 24 並沒有, 以下附上原始版本的 priority replay buffer 算法

algorithm 2 的第 15 行和 19 行對應 algorithm 1 的 13 行和 15 行

### Performance Evaluation
作者使用自己 OCTDE-ISAC 算法和以下五種算法比較
* **DDPG**：DDPG 可以在連續動作空間中快速收斂，但不適合用於 IoV，因為這是快速變化的隨機環境。
* **RO**：ES randomly offloads local tasks to neighbor ESs.
* **Centralized SAC Offloading (CSACO)**：有一個集中式 agent，其負責訓練所有 ESs 的所有卸載策略，此代理人會 蒐集所有 ESs 的 local state，結合卸載行動，以促進 ES 間的合作。
* **Decentralized SAC Offloading (DSACO)**：和 CSACO 相反，在每個 ES 上都有 SAC 的 offload model，ES 根據 local state 去執行卸載任務。
* **SAC-Based Off-Line Centralized Training Distribution Execution Offloading Algorithm (OCTDE-SAC)**：和 OCTDE-ISAC 類似，但在採樣時沒有考慮樣本間的差異。


SAC 優於 DDPG，因為 SAC 會做較多探索。

ISAC 收斂得更快，是因為 priority sample，表現更好的原因是 ISAC 的網路架構更接近 MADDPG，所以agent可以更好的合作。


學習率高，收斂速度快，但穩定性差，無法到最優卸載策略

學習率低，收斂速度慢，還沒收斂，環境又變了


其他條件都不變，改變 ES computation capabilities，直觀的延遲都有所降低。

ISAC 優於其他算法的原因是其會考慮樣本的重要性，提高採樣效率、收斂速度和穩定性。


即使任務規模增加，ISAC 穩定性較好。



當任務數量增加，部分 ES 會接近滿載。

OCTDE-ISAC 會將不同類型的計算任務卸載到最合適的ES上執行。 這減少了計算任務的延遲並實現ES之間的負載平衡。


平衡 ESs 的負載, 以降低降低任務的平均延遲, 使系統的 throughput 提升


## Conclusion

* 本篇為了實現 ES 之間的負載平衡並減少車輛任務的延遲，提出了一種edge-edge協作 MEC 結構。透過考慮任務類型數量、資料大小、延遲容忍度等參數，將多ES計算卸載模型視為MDP。

* 提出一種ISAC演算法來優化系統的平均延遲，並採用自適應權重採樣機制來提高演算法的收斂速度和穩定性。為了減少通訊花費，採用離線集中訓練分散式執行架構，促進 ES 之間的協同卸載。

* 實驗結果表明，對於車聯網高動態場景，OCTDE-ISAC 在延遲、收斂性和效率方面優於現有的運算卸載策略。