# 論文問題草稿1 ###### tags: `論文` ## System model ### System Architecture * 我們考慮在城市內一段有一個路側單元(RSU)覆蓋的雙向快速道路如圖Fig. 1，RSU上裝有邊緣伺服器(MEC)，我們假設RSU的覆蓋範圍為R，在RSU覆蓋範圍中有計算任務的任務車輛的集合為 $TV=\{tv_0,tv_1,...,tv_N\}$，在覆蓋範圍中有閒置計算資源的服務車輛的集合為 $SV=\{sv_0,sv_1,...,sv_K\}$，每輛任務車輛都有一個計算任務要執行，任務可以在任務車輛上執行，或透過V2I和V2V將任務卸載到RSU或附近的服務車輛上執行</br>![](https://i.imgur.com/mK3Q2CK.png) <!-- https://ieeexplore.ieee.org/abstract/document/10007714 -->架構是參考這篇，可能實驗參數可以參考 ### Link Connection Time <!-- https://ieeexplore.ieee.org/abstract/document/9684560 --> V2V的部分是參考這篇，V2I是我額外想的 * 假設車輛A的位置、速度和行駛方向為 $(x_A,y_A), v_A$ 和 $direction_A$，車輛B的位置、速度和行駛方向為 $(x_B,y_B), v_B$ and $direction_B$，RSU的位置表示為 $(x_{RSU},y_{RSU})$，若車輛從左往右行駛(x變大)，則 $direction=1$，反之若車輛從右往左行駛(x變小)，則 $direction=-1$，V2I的通訊範圍表示為 $R_{V2I}$，V2V的通訊範圍表示為 $R_{V2V}$ #### V2V Link Connection Time * 車輛A和車輛B之間可以透過V2V直接通訊的時間表示為鏈路連接時間 $lifetime_{A,B}$ * 當2車都向同個方向行駛且A車的速度大於B車，2輛車的鏈路連接時間可以表示為 $lifetime_{A,B}=\frac{x_B-x_A+\sqrt{R^2-(y_A-y_B)^2}}{v_A-v_B}$![](https://hackmd.io/_uploads/SkoRJVP4n.png) * 當2車都向同個方向行駛且A車的速度小於B車，2輛車的鏈路連接時間可以表示為 $lifetime_{A,B}=\frac{x_A-x_B+\sqrt{R^2-(y_A-y_B)^2}}{v_B-v_A}$![](https://hackmd.io/_uploads/rJ2RxVPNn.png) * 當2輛車行駛方向相反時，2輛車的鏈路連接時間可以表示為 $lifetime_{A,B}=\frac{x_A-x_B+\sqrt{R^2-(y_A-y_B)^2}}{v_A+v_B}$ (往右行駛的車為B車)![](https://hackmd.io/_uploads/Hywjb4wV3.png) * 根據上面3個公式，車輛A和車輛B之間的鏈路連接時間可以表示為 $lifetime_{A,B} = \begin{cases} \frac{x_B-x_A+\sqrt{R^2-(y_A-y_B)^2}}{v_A-v_B} \ ,v_A \ge v_B \ and \ direction_A=direction_B \\ \frac{x_A-x_B+\sqrt{R^2-(y_A-y_B)^2}}{v_B-v_A} \ ,v_A < v_B \ and \ direction_A=direction_B \\ \frac{x_A-x_B+\sqrt{R^2-(y_A-y_B)^2}}{v_A+v_B} \ ,direction_A\ne direction_B \end{cases}$ #### V2I Link Connection Time * 當車輛A在RSU的通訊範圍內時，車輛A從左往右行駛($direction=1$)，車輛A和RSU之間的鏈路連接時間可以表示為 $lifetime_{A,RSU}=\frac{x_{RSU}-x_A+\sqrt{R^2-(y_A-y_{RSU})^2}}{v_A}$![](https://hackmd.io/_uploads/rJ6KOVw43.png) * 當車輛A在RSU的通訊範圍內時，車輛A從右往左行駛($direction=-1$)，車輛A和RSU之間的鏈路連接時間可以表示為 $lifetime_{A,RSU}=\frac{x_A-x_{RSU}+\sqrt{R^2-(y_A-y_{RSU})^2}}{v_A}$![](https://hackmd.io/_uploads/rysoF4v42.png) * 根據上面2個公式，車輛A和RSU之間的鏈路連接時間可以表示為 $lifetime_{A,RSU}=\begin{cases} lifetime_{A,RSU}=\frac{x_{RSU}-x_A+\sqrt{R^2-(y_A-y_{RSU})^2}}{v_A} \ ,direction_A=1 \\ lifetime_{A,RSU}=\frac{x_A-x_{RSU}+\sqrt{R^2-(y_A-y_{RSU})^2}}{v_A} \ ,direction_A=-1 \end{cases}$ ### Communication model #### V2V communication * 類似於[]，我們選擇在車輛之間選擇相同且獨立分布的頻道，因此車輛n和k之間V2V通訊的路徑損失可以表示為 $L^{V2V}_{n,k} = 10^{-\frac{63.3+17.7log_{10}(d_{n,k})}{10}}$，$d_{n,k}$ 為車輛n和k之間的距離 * 車輛n和k之間的傳輸速率為 $R^{V2V}_{n,k} = B_{V2V}log_2(1+\frac{P_nL^{V2V}_{n,k}|h^2|}{N_0})$ * $B_{V2V}$ 是V2V的傳輸頻寬 * $P_n$ 是車輛n的傳輸功率 * $h$ 是頻道增益 * $N_0$ 是高斯白噪音 #### V2I communication * 車輛n和RSU之間V2I通訊的路徑損失表示為 $d^{-\sigma}_{n,rsu}$，$d_{n,rsu}$ 為車輛n和RSU之間的距離，$\sigma$ 是路徑損失指數，車輛n和RSU之間的傳輸速率為 $R^{V2I}_n = B_{V2I}log_2(1+\frac{P_nd^{-\sigma}_{n,rsu}|h^2|}{N_0})$ * $B_{V2I}$ 是V2I的傳輸頻寬 <!-- https://journalofcloudcomputing.springeropen.com/articles/10.1186/s13677-020-00175-w --> ### Computation task model * 每個任務車輛都有一個計算任務 $\phi_i$ 要執行，可以根據計算任務的分割限制將計算任務分成3個集合分別為$Task_1,Task_2,Task_3$，計算任務 $\phi_i$ 可以表示為 $\{D_n,C_n,T^{max}_n,Type_n\}$ * $D_i$ 任務的數據大小 * $C_i$ 完成任務所需要的CPU cycles數 * $T^{max}_i$ 任務的最大延遲限制 * $Type_i = \begin{cases} 1，任務無法分割，只能都在本地計算或都進行卸載\\ 2，任務能分割成2部分，1部分在本地執行，1部分進行卸載 \\ 3，任務可以任意分割\end{cases}$ * 因為任務可以在本地計算、卸載到RSU或服務車輛上，因此有必要對任務進行分割，並決定要卸載到哪裡和需要卸載的比例，卸載決策矩陣定義為 $D=[d_0,d_1,...,d_N]$，其中 $d_i = [a^i_{loc},a^i_{mec},a^i_0...,a^i_K]$ * $a^i_{loc}$ 表示任務 $i$ 在任務車輛 $tv_i$ 上執行的比例 * $a^i_{RSU}$ 表示任務 $i$ 卸載到RSU上執行的比例 * $a^i_j, j\in(0,1,...,K)$ 表示任務 $i$ 卸載到服務車輛 $sv_j$ 上執行的比例 * 不同類型的任務對於分割有不同限制，若 $Type_i = 1$，則 $a^i_{loc},a^i_{RSU},a^i_j \in \{0,1\}$，卸載比例只能是0或1，且 $a^i_{loc}+a^i_{RSU}+\displaystyle\sum_{j=0}^K a^i_j = 1$，只能卸載到1個地方 * 若 $Type_i = 2$，則 $a^i_{loc},a^i_{RSU},a^i_j \in [0,1]$，卸載比例介於0~1之間，且$\lceil a^i_{RSU} \rceil+\displaystyle\sum_{j=0}^K \lceil a^i_j \rceil \le 1$ 表示最多只能卸載到1個地方，$a^i_{loc}+a^i_{RSU}+\displaystyle\sum_{j=0}^K a^i_j = 1$，表示全部任務都要執行 * 若 $Type_i = 3$，則 $a^i_{loc},a^i_{RSU},a^i_j \in [0,1]$，卸載比例介於0~1之間，且$a^i_{loc}+a^i_{RSU}+\displaystyle\sum_{j=0}^K a^i_j = 1$，表示全部任務都要執行 #### Local computation model * 在本地計算模型中，計算任務 $i$ 會在任務車輛 $tv_i$ 上本地執行，對於計算任務 $i$ 在任務車輛 $tv_i$ 上執行的本地執行延遲表示為 $T^{loc}_i = \frac{a^i_{loc} \, C_i}{f^{TV}_i}$ * $f^{TV}_i$ 是任務車輛 $tv_i$ 的計算能力 * 本地執行的總能量消耗 $E^{loc}_i$ 可以表示為 $E^{loc}_i = b \, (f^{TV}_n)^2 \, a^n_0 \, C_n$ * $b$ 是一個取決於晶片架構的係數 <!--https://ieeexplore.ieee.org/document/9771732 有寫能量消耗公式和晶片係數--> #### RSU computation model * 在RSU計算模型中，計算任務會被卸載到裝備有MEC server的RSU上，任務車輛 $tv_i$ 將計算任務傳送到RSU的傳送延遲 $t^{up}_{i,RSU} = \frac{a^i_{RSU} \, D_i}{R_{V2I,i}}$ * 計算任務卸載到RSU上執行的執行延遲 $t^{com}_{i,RSU} = \frac{a^i_{RSU} \, C_i}{f^{RSU}_i}$ * $f^{RSU}_i$ 表示RSU分配給計算任務 $i$ 的計算資源 * 在RSU上執行計算任務的能量消耗 $e^{com}_{i,RSU} = b_{RSU} \, (f^{RSU}_i)^2 \, a^i_{RSU} \, C_i$ * 從任務車輛 $tv_i$ 將計算任務卸載到RSU上執行的總延遲為 $T^{RSU}_i = t^{up}_{i,RSU} + t^{com}_{i,RSU}$ * 從任務車輛 $tv_i$ 將計算任務卸載到RSU上執行的總能量消耗為 $E^{RSU}_i = P_{tv_i} \, (t^{up}_{i,RSU}) + e^{com}_{i,RSU}$ #### Service vehicle computation model * 在服務車輛計算模型中，計算任務會被卸載到附近有閒置計算資源的服務車輛上，任務車輛 $tv_i$ 將計算任務傳送到服務車輛 $sv_j$ 的傳送延遲 $t^{up}_{i,j} = \frac{a^i_{j}D_i}{R^{V2V}_{i,j}}$ * 計算任務卸載到服務車輛 $sv_j$ 上執行的執行延遲 $t^{com}_{i,j} = \frac{a^i_j \, C_i}{f^{SV}_j}$ * $f^{SV}_j$ 是服務車輛 $sv_j$ 閒置的計算資源 * 在服務車輛 $sv_j$ 上執行的能量消耗 $e^{com}_{i,j} = b \, (f^{SV}_j)^2 \, a^i_j \, C_i$ * 從任務車輛 $tv_i$ 將計算任務卸載到服務車輛 $sv_j$ 上執行的總延遲為 $T^{SV}_{i,j} = t^{up}_{i,j} + t^{com}_{i,j}$ * 從任務車輛 $tv_i$ 將計算任務卸載到服務車輛 $sv_j$ 上執行的總能量消耗為 $E^{SV}_{i,j} = P_i \, (t^{up}_{i,j}) + e^{com}_{i,j}$ ## Problem formulation * 因為卸載出去的部分可以平行執行，所以計算任務 $i$ 的總延遲為 $T^i = max(T^{loc}_i,T^{RSU}_i,T^{SV}_{i,j}) \ j \in (0,1,...,K)$ * 計算任務 $i$ 的總能量消耗為 $E^i = E^{loc}_i+E^{RSU}_i+\displaystyle\sum_{j=0}^K E^{SV}_{i,j}$ * 本文的目標是在計算任務最大延遲 $T^{max}$ 和資源限制下，最小化系統的總成本，因此系統的計算卸載和資源分配問題可以描述為</br> $\min_{D,F} \displaystyle\sum_{i=0}^N \gamma \cdot T^i + (1-\gamma) \cdot E^i \\ st. \ C1:T^i \le T^{max}_i,\ \forall i \in N\\ \ \ \ \ \ \ C2:0 \le f^{RSU}_i \le f^{RSU}, \forall i \in N \\ \ \ \ \ \ \ C3:\displaystyle\sum_{i=0}^N \lceil \alpha^i_{RSU} \rceil f^{RSU}_i \le f^{RSU}\\ \ \ \ \ \ \ C4:T^{RSU}_i \le lifetime_{i,RSU},\forall i \in N\\ \ \ \ \ \ \ C5:T^{SV}_{i,j} \le lifetime_{i,j},\forall i \in N, \forall j \in K\\ \ \ \ \ \ \ C6:\alpha^i_{loc},\alpha^i_{RSU},\alpha^i_j\in \{0,1\}, i \in N_1\\ \ \ \ \ \ \ C7:\alpha^i_{loc},\alpha^i_{RSU},\alpha^i_j\in [0,1], i \in N_2 \ or \ N_3\\ \ \ \ \ \ \ C8:\alpha^i_{loc}+\alpha^i_{RSU}+\displaystyle\sum_{j=0}^K\alpha^i_j=1,\forall i \in N\\ \ \ \ \ \ \ C9:\lceil\alpha^i_{RSU}\rceil+\displaystyle\sum_{j=0}^K\lceil\alpha^i_j\rceil \le 1, i \in N_2$ * $\gamma$ 是延遲的權重，$(1-\gamma)$是能量的權重，可以根據服務的要求和移動設備的狀態來設置，例如當執行延遲敏感的服務時，可以適當增加 $\gamma$ 值 * D是卸載決策矩陣 * $F=[f^{RSU}_0,f^{RSU}_1,...,f^{RSU}_N]$ 是RSU的計算資源分配向量 * C1表示任務的總延遲不能超過任務的最大延遲 * C2表示RSU分配給任務的計算資源不能超過RSU的最大計算資源 * C3表示RSU分配給計算任務的總計算資源不能超過RSU的最大資源 * C4表示卸載到RSU的總延遲不能超過可以和RSU維持通訊的時間 * C5表示卸載到服務車輛的總延遲不能超過可以和服務車輛維持通訊的時間 * C6表示屬於 $N_1$ 的任務其 $\alpha^i_{loc},\alpha^i_{RSU},\alpha^i_j$ 為0或1 * C7表示屬於 $N_2$ 或 $N_3$ 的任務其 $\alpha^i_{loc},\alpha^i_{RSU},\alpha^i_j$ 介於0~1 * C8表示卸載到本地、RSU或服務車輛的卸載比例相加要等於1，整個任務都要執行 * C9表示對於屬於 $N_2$ 的任務，其卸載目標最多不能超過1個 ## Adaptive Particle Swarm Optimization Solution * 粒子群演算法(PSO)是一種演化式演算法(Evolutionary Algorithms)，起源於對鳥類捕食行為的研究，假設有 $N$ 個粒子群 $X=\{\text{x}_1,\text{x}_2,...,\text{x}_N\}$，每個粒子群的位置和速度為 $\text{x}_i=\{x_1,x_2,...,x_D\}, \text{v}_i=\{v_1,v_2,...,v_D\}$，$D$ 是需要優化的參數量 * 在每次迭代中，粒子會根據速度、自身經歷過的最佳解(pbest)和群體經歷過的最佳解(gbest)來更新當前的位置，粒子群的速度更新公式為 $\text{v}_i(t+1)=\omega(t+1)\text{v}_i(t)+c_1(pbest_i-\text{x}_i(t))R_1+c_2(gbest-\text{x}_i(t))R_2$ * $\omega$ 是慣性權重用來避免速度爆炸 * $R_1,R_2$ 是一個介於[0,1] 均於分布的亂數 * $c_1,c_2$ 是加速常數用來平衡區域探索和全域探索 * 粒子群的位置更新公式為 $\text{x}_i(t+1) = \text{x}_i(t)+\text{v}_i(t+1)$ ### Particle encoding * 對於 $type_1$ 的任務需要決定其卸載目標和RSU資源分配的比例，在優化問題中，卸載決策矩陣 $d_i=[a^i_0,a^i_1,...,a^i_K],K\in SV$ 且 $a^i_j\in\{0,1\}$，原本為二元變數，透過實數編碼將卸載決策矩陣 $d_i$ 編碼成1個介於0~K+1的實數，因此若 $\lfloor d_i \rfloor = k$，則 $a^i_k = 1$ 且 $a^i_j = 0,j\ne k$，表示任務i卸載到服務車輛k，因此$type_1$的任務需要決定卸載目標和RSU資源分配，需要2個變數來表示解 * 對於 $type_2$ 的任務需要決定其卸載目標、卸載比例和RSU資源分配的比例，卸載對象類似於$type_1$任務中的實數編碼，將卸載決策矩陣$d_i$編碼成一個介於0~K+1的實數，除了卸載目標還需要決定卸載比例和RSU資源分配的比例，因此 $type_2$ 需要3個變數來表示解 * 對於 $type_3$ 的任務需要決定其卸載比例和RSU資源分配，因$type_3$ 需要SV+1個變數來表示解 * 每個粒子群的大小為 $D = 2*type1+3*type2+(SV+1)*type3$，假設總共有3個任務，任務 $\phi_1,\phi_2,\phi_3$的類型分別為$task_1,task_2,task_3$，$SV=4$，有1個可行解$X_i = \{2.3,0.2,1.59,0.84,0.35,0.32,0,0,0.68,0.4\}$，表示 $\phi_1$ 卸載到 $sv_2$，$\phi_2$ 卸載0.35到 $sv_1$，$\phi_3$ 卸載0.32到 $sv_0$，卸載0.68到 $sv_3$，並分配0.4的計算資源給$\phi_3$![](https://hackmd.io/_uploads/BkBcKJM83.png)