Content Caching-Assisted Vehicular Edge Computing Using Multi-Agent Graph Attention Reinforcement Learning

As shown in Fig. 1, we consider a Manhattan vehicular network model which consists of multiple horizontal and vertical two-lane two-way roads. $L$ RSUs are deployed uniformly and $M$ VUs drive along the road with their velocity obeying the Markov-Gaussian stochastic process independently and may change their direction at intersections with a given probability $\eta$. Let $\mathcal{L}=\{1,2,\cdots,L\}$ and $\mathcal{M}=\{1,2,\cdots,M\}$ denote the index sets of RSUs and VUs, respectively. Both RSUs and VUs have the capability to compute tasks and cache contents, which are referred to as service nodes (SNs). Let $\mathcal{N}=\mathcal{L}\cup\mathcal{M}=\{1,2,\cdots,N\}$ represent the index set of $N$ SNs.

Without loss of generality, we assume that the system operates in a time-slot (TS) mode and environmental parameters (e.g. transmit power and channel gain) remain unchanged during each TS. Additionally, new tasks with different popularity characteristics arrive every certain TSs, and each task can be completed successfully during each TS. Let $\mathcal{K}=\{1,2,\cdots,K\}$ represent the index set of tasks, where task $k$ is represented by a 3-tuple $\left\langle d_{k},s_{k},b_{k}\right\rangle$ with the task size $d_{k}$, the number of CPU cycles required to process the task $s_{k}$ and the size of the processed task content $b_{k}$. Note that, if the content of the task result has been cached on SNs within the communication range of the VU, the content can be fetched directly from SNs to VUs. Otherwise, the VU has to compute the task itself or offload it for execution. In this case, after completing the task, each VU needs to decide whether to cache the content and to which SN.

Let $P_{m}$ and $g_{m,n}^{\text{up}}(t)$ denote the transmit power of VU $m$ and the channel gain spanning from VU $m$ and SN $n$ in TS $t$, respectively. In this framework, we consider the small-scale fading and the path loss of vehicle-to-vehicle (V2V) communication and vehicle-to-infrastructure (V2I) communication, neglecting the effects of shadow fading [4]. We assume that the inter-user interference has been eliminated by allocating orthogonal resource blocks. Thus, the uplink transmission rate from VU $m$ to SN $n$ in TS $t$ is given by

where $B$ is the bandwidth of each channel, and $\sigma^{2}$ is the power of the additive Gaussian white noise, both of which are assumed to be the same for each TS. Similarly, let $P_{n}$ and $g_{n,m}^{\text{down}}(t)$ denote the transmit power of SN $n$ and the channel gain spanning from SN $n$ and VU $m$ in TS $t$, respectively. Thus the downlink transmission rate from SN $n$ to VU $m$ in TS $t$ is given by

Let $k_{m}(t)$ denote the task requested by VU $m$ in TS $t$ and $w_{m}(t)\in\{0,1\}$ denote whether VU $m$ has to offload $k_{m}(t)$. If $w_{m}(t)=0$, VU $m$ computes $k_{m}(t)$ itself, otherwise VU $m$ offloads $k_{m}(t)$ to the nearest SN $n_{m}(t)$.

• •

  Local Computing: Let $f_{m}^{\text{l}}$ be the computation capability on VU $m$. Therefore, the latency of computing task $k_{m}(t)$ generated by user VU $m$ is given by $T_{m}^{\text{l}}(t)=(1-w_{m}(t)){s_{k_{m}(t)}}/{f_{m}^{\text{l}}}$.

• •

  Task Offloading: Let $f_{n_{m}(t)}^{\text{off}}$ be the computation capability on SN $n_{m}(t)$. Then, the latency in completing task $k_{m}(t)$ is expressed as $T_{m}^{\text{off}}(t)=w_{m}(t)(T_{m}^{\text{up}}(t)+T_{m}^{\text{exe}}(t)+T_{m}^{\text{down}}(t))$, where $T_{m}^{\text{up}}(t)={d_{k_{m}(t)}}/{\zeta_{m,n_{m}(t)}^{\text{up}}(t)}$, $T_{m}^{\text{exe}}(t)={s_{k_{m}(t)}}/{f_{n_{m}(t)}^{\text{off}}}$ and $T_{m}^{\text{down}}(t)={b_{k_{m}(t)}}/{\zeta_{n_{m}(t),m}^{\text{down}}(t)}$ denote the task offloading latency, task computing latency, and result content fetching latency, respectively.

Let $\textbf{H}_{\text{ca}}(t)=[h_{n,k}^{\text{ca}}(t)]_{\forall n,\forall k}$ represent whether computing result contents are cached or not by all SNs in TS $t$. Specifically, $h_{n,k}^{\text{ca}}(t)=1$ if the content of task $k$ is cached on SN $n$ in TS $t$, otherwise $h_{n,k}^{\text{ca}}(t)=0$. Note that all SNs have limited caching capacity with $g_{n}(t)$ for SN $n$, thus it is impossible to cache all the task contents. Let us continue to denote $a_{m}^{\text{ca}}(t)\in\{0,1,\cdots,N\}$ as the caching decision variable for VU $m$ in TS $t$. To be specific, if $a_{m}^{\text{ca}}(t)=n~{}(n\neq 0)$, VU $m$ caches the computing result content to SN $n$ and $h_{n,k}^{\text{ca}}(t)=1$, otherwise VU $m$ does not cache the content to any SN. Then, the caching decision of all VUs in TS $t$ can be denoted as $\textbf{a}_{\text{ca}}(t)=[a_{1}^{\text{ca}}(t),a_{2}^{\text{ca}}(t),\cdots,a_{M}^{\text{ca}}(t)]$.

When SNs cache the content of $Z_{t}$ task computing results in TS $t$, we have $\mathcal{Z}=\{1,2,\cdots,Z_{t}\}$. We assume that the task content popularity follows the Zipf distribution, thus the probability of task content $z\in\mathcal{Z}$ to be requested is expressed as $q_{z}(t)={I_{z}(t)^{-\delta}}/{\sum_{z=0}^{Z}I_{z}(t)^{-\delta}}$ , where $I_{z}(t)$ denotes the ranking of the popularity of task content $z$ in descending order in TS $t$, and $\delta$ is the Zipf distribution parameter.

Our aim is to design an edge caching scheme for the VEC system to minimize the long-term task computing latency by utilizing limited edge caching resources. To formulate our problem, we introduce an auxiliary variable $e_{m}(t)$, where $e_{m}(t)=1$ when $m$ can fetch the required content directly from SNs within its communication range, otherwise $e_{m}(t)=0$. Thus, the total computation latency is the local computing latency or the task offloading latency when $e_{m}(t)=0$, and is the latency for fetching the cached task result when $e_{m}(t)=1$. Then, the task computing latency for VU $m$ in TS $t$ can be expressed by $T_{m}(t)=(1-e_{m}(t))(T_{m}^{\text{l}}(t)+T_{m}^{\text{off}}(t))+e_{m}(t)T_{m}^{\text{down}}(t)$. Mathematically, the optimization problem is formulated as

Based on the learned policy and its observation in TS $t$, VU agent $m$ selects an action $a_{m}^{ca}(t)$ to decide whether to cache the content and to which SN.

The vehicular network topology can be modeled as a graph $\mathcal{G}=\{\mathcal{V},\mathcal{E}\}$ where the node set $\mathcal{V}$ is the set of $M$ VUs and the edge set $\mathcal{E}$ is determined by the distance among vehicles. To be specific, there exists an edge between two nodes when their distance does not exceed the maximum communication range and such vehicles are neighbors of each other. Let $\mathcal{A}_{i}^{t}$ denote the set of neighbors of node $i$ in TS $t$. Each node in the graph has its node features, denoted by $h_{i}^{t}$ for node $i$ in TS $t$, which are yielded from the observation $o_{i}^{t}$ through a fully connected network.

The latent feature generating stage utilizes the convolutional layer to integrate the node features in node $i$’s local region, which includes $i$ and $\mathcal{A}_{i}^{t}$ to generate the latent feature $h_{i}^{\prime t}$ in TS $t$. Firstly, in TS $t$, all nodes’ feature vectors are merged into a feature matrix $\mathbf{F}^{t}$ with size $M\times D$ in the order of index where $D$ is the length of the feature vector. Then, let $\mathcal{A}_{+i}^{t}$ represent the set of node $i$ and $\mathcal{A}_{i}^{t}$ and we introduce an adjacency matrix $\mathbf{C}_{i}^{t}$ with size $\lvert\mathcal{A}_{+i}^{t}\rvert\times M$ to denote the one-hot representations of $\mathcal{A}_{+i}^{t}$. To be specific, the first row of $\mathbf{C}_{i}^{t}$ is the one-hot representation of node $i$, and the $j\in\{2,3,\cdots,\lvert\mathcal{A}_{+i}^{t}\rvert\}$th row is the representation of the $(j-1)$th neighbor of $i$. Then, the features in the local region of node $i$ are obtained by $\mathbf{C}_{i}^{t}\times\mathbf{F}^{t}$.

To further capture the relationships among nodes, the multi-head attention is adopted as the convolution kernel to integrate the feature vectors in the local region of node $i$ and generate the latent feature vector $h_{i}^{\prime t}$. Let $W_{Q}^{u}$, $W_{K}^{u}$ and $W_{V}^{u}$ denote the parameter matrices corresponding to the query, key, and value representation in attention head $u$, respectively. For attention head $u$, the relationship between node $i$ and its neighbor $j\in\mathcal{A}_{+i}^{t}$ in TS $t$ can be formulated as

where $\tau$ is a scaling factor. Next, the outputs of $U$ attention heads for node $i$ are concatenated and then fed into function $\bm{\sigma}$ to produce the output of the convolutional layer, expressed as $h_{i}^{\prime t}=\bm{\sigma}(\textbf{{con}}[\sum_{j\in\mathcal{A}_{+j}^{t}}a_{i,j,t}^{u}W_{V}^{u}h_{j}^{t},\forall u])$, where con denotes the concatenation of the outputs of $U$ attention heads. Note that, more graphical information can be extracted through increasing the number of convolutional layers.

Similar to the traditional deep Q network (DQN) algorithm using Q values to estimate the long-term cumulative reward of taking a certain action at the current state, the MGARL algorithm utilizes both the training network and the target network, where the training network parameters are updated by optimizing the loss function of the target network. Through extracting graphical information to facilitate cooperative learning, the MGARL method can better capture the dynamics and irregularities than the traditional DRL methods. In order to utilize historical data for training and improve sample utilization, the tuple $\left\langle o_{i}^{t},a_{i}^{t},r_{i}^{t},o_{i}^{t+1},\mathbf{C}_{i}^{t},\mathbf{C}_{i}^{t+1}\right\rangle$ of vehicular agent $i$ is stored in the shared replay buffer in each TS. When training, $S$ sets of samples are randomly selected to update the parameters of the training network. Particularly, in order to achieve stable interactions between agents, MGARL optimizes the attention weight distribution of the last convolutional layer to minimize the Kullback-Leibler divergence of the attention weight distribution in the current TS over the weights in the next TS. Then, the loss function of the target network is expressed as

Let us now discuss the complexity of the graph attention convolutional layer in TS $t$ including the feature mapping of nodes and the calculation of attention weights. We assume that the constructed graph in TS $t$ consists of $\lvert\mathcal{E}_{t}\rvert$ edges and each node feature is mapped from dimension $F$ to space in dimension $F^{\prime}$. Then, the computational complexity for mapping node features is represented as $\mathcal{O}\left(MFF^{\prime}\right)$ while the computational complexity in calculating attention weights is related to the number of edges, which is expressed as $\mathcal{O}\left(\lvert\mathcal{E}_{t}\rvert F^{\prime}\right)$. Therefore, the total computational complexity with $U$ attention heads is determined by the number of VUs, the number of edges, and the node feature dimension, given by $\mathcal{O}\left(U(MFF^{\prime}+\lvert\mathcal{E}_{t}\rvert F^{\prime})\right)$.

We consider a Manhattan vehicular network model, where the length and width of the road are both $1$ km. By default, we set $M=20$, $L=16$, $d_{k}\in\left[50,80\right]$ MB, $b_{k}\in\left[6,16\right]$ MB, $s_{k}=50$ Megacycles $(\forall k)$, $B=10$ MHz, $\sigma^{2}=-174$ dBm/Hz, $\delta=0.5$, $re_{m}=2\ (\forall m)$, and $pl\in\{0,-0.5\}$. The transmit power of RSUs and VUs are set to $40$ dBm and $23$ dBm, respectively. The caching capacity of RSUs and VUs are $100$ MB and $50$ MB, respectively. The computation capability of RSUs and VUs are $1$ GHz and $0.8$ GHz, respectively. The communication range of RSUs and V2V communication are set as $400$ m and $300$ m, respectively. We adopt the channel model according to [4]. In terms of the VU mobility model, we set $\eta=0.4$ and the mean range of VUs’ velocity as $[36,54]$ km/h, and other parameters setting please refer to [17]. With regard to the learning configurations, $\gamma=0.9$, $S=128$, the learning rate is $0.001$ and the buffer capacity is $2000$. For fair comparison, we choose the proposed w/o attention based scheme, multi-agent Independent Double Deep Q Network (IDDQN) based scheme and the random content caching scheme.

Fig. 3 presents the convergence performance of all schemes. It can be observed that the cumulative reward of the proposed scheme is higher than the baselines. This is attributed to the fact that the proposed scheme, in conjunction with the proposed w/o attention and IDDQN-based scheme, can learn policy by continuously interacting with the environment. Moreover, the proposed scheme utilizes graph attention convolution kernels to capture the relationships among agents to further enhance cooperation, which is more adaptable to irregular network topologies and consequently has the highest cumulative reward.

The converged content hit ratio versus the number of VUs is investigated in Fig. 4 when the number of content types (CTs) is 10 and 20. The first point to observe is that the converged content hit ratio increases as the number of VUs increases. This is because more users lead to the increasing number of content requests, thus increasing the probability of reusing the same cached content. Secondly, it is clear that the content hit ratio is reduced when the number of CTs is increased from $10$ to $20$. The underlying reason is that due to the limited caching capacity of SNs, they may not cache all the contents, which decreases the hit ratio of each content. Moreover, we can see that our proposed scheme outperforms other schemes in improving the content hit ratio regardless of both the number of CTs and the number of VUs, which verifies the effectiveness of the proposed scheme in improving caching resource utilization.

Fig. 5 compares the converged total system latency versus the number of RSUs. Firstly, as the number of RSUs increases, the converged total system latency exhibits a downward trend. The underlying reason for this phenomenon is that with more RSUs having computation and caching capability, VUs are more likely to fetch the cached result content from the surrounding RSUs, thus avoiding the repeated uploading and computing process. Secondly, it can be seen that the proposed scheme outperforms other schemes under different numbers of RSUs, since multiple graph attention convolutional layers can extract more hidden structural information to facilitate cooperative learning. This phenomenon implies that the proposed scheme can make better use of densely deployed cache resources to further reduce the total system latency.