# Adaptive Virtual RSU Scheduling for Scalable Coverage under Bidirectional Vehicle Traffic Flow
## 5 Cache Replication
### Online Implementation
#### 5.2.1 A Special Case Scenario  
In the special case scenario, all of the vehicles can visit every RSU in sequence. In other words, we can redirect the request demand of a vehicle to an arbitrary RSU when it passes by the coverage area. Even though it is a special case, it also can be prevalent in the real world, especially the highway, in which the vehicles can drive a long distance and RSUs can be allocated along the road. Therefore, if we do not consider the delay constraint, in this special case scenario, our problem can be transmitted into a minimum weight set cover problem, in which the storage capacity can be considered as the weight of each RSU. As we assume that all the RSUs are with equal storage capacity like previous works [13; 14], the weight of the set can refer to the number of RSUs in our formulated problem. Accordingly, we can present an adaptive greedy replication (AGR) for a special case scenario in Figure 6.  
As we assume that the traffic flow would pass all the RSUs in a sequence along the road, the popularity distribution of replication content in cloud servers can be recorded in advance. The popularity list can be achieved for each replica, and the replicas can be migrated among the RSUs in a sequence. In the adaptive greedy replication strategy, the replica with the highest popularity in the current situation would be allocated in the RSU until the storage capacity is full. After each  
Figure 5: Two layer mapping model. round of replication, the corresponding request demand of the vehicles can be served by this RSU when they pass by. This procedure is implemented at each RSU in a sequence until all of the request demands of the traffic flow are satisfied. Therefore, the replicas with high popularity would be allocated at the head of the RSU sequence, and the ones with low popularity are allocated at the end of the RSU sequence. During practical implementation, the replicas in the sequence of RSUs can be migrated adaptively to adjust with time-varying request demands. According to the request demands, the adaptive greedy replication strategy can start a new RSU or terminate an old RSU at the tail of the sequence. In other words, our proposed greedy algorithm is straightforward enough to allocate the most popular replicas in priority, and adaptively redirect the request demands towards these RSUs to maximize the service time. **Theorem 2**. : _For any instance \((R,S,V)\), the greedy algorithm finds a set cover with a result at most \(H(\lambda)\cdot OPT(R,S,V)\), where \(\lambda=max_{s_{k}\in S}|s_{k}|\) and \(H(\lambda)=1+1/2+...+1/\lambda\)._  
Proof. : Let \((R,S,V)\) be an instance with \(\{s_{1},s_{2},...,s_{k}\}\) as the solution found by the adaptive greedy solution, where \(\eta_{i}\) is the set chosen in the i-th iteration. For \(j=0,...,k\), let \(W_{j}=\bigcup_{i=1}^{j}\eta_{i}\). For each replica \(e\), let \(j(e)=min\{j\in\{1,...,k\}|e\in R_{j}\}\) be the iteration where replica \(e\) is covered, and \(y(e)\) be the popularity. Given an RSU allocation \(S\) and \(k^{\prime}=max\{j(e)|e\in S\}\), we can have  
\[\sum_{e\in S} = \sum_{i=1}^{k^{\prime}}\sum_{j(e)=i}y(e)\leq c(S)\cdot\sum_{i}^{ k^{\prime}}\frac{\varepsilon_{i}-\varepsilon_{i+1}}{\varepsilon_{i}}\] \[= c(S)\cdot\sum_{i=1}^{k^{\prime}}(\frac{1}{\varepsilon_{i}}+ \frac{1}{\varepsilon_{i}-1}+...+\frac{1}{\varepsilon_{i+1}})\leq c(S)\cdot H( \varepsilon_{1}),\]  
where \(\varepsilon_{i}=|S\ W_{i-1}|\). As \(\varepsilon_{i}=|S|\leq\lambda\), we can have \(\sum\limits_{e\in S}y(e)\leq c(S)\cdot H(\lambda)\). Furthermore, we sum over all \(S\in OPT\) for an optimum set cover \(OPT\) and have  
\[c(OPT)\cdot H(\lambda)\geq\sum_{S\in OPT}\sum_{e\in S}y(e)\geq\sum_{e\in U}y( e).\]  
Figure 6: Adaptive greedy replication. We can see that the greedy algorithm can achieve an optimal solution if \(y(e)\) is constant for every \(e\in U\) (i.e., the popularity is equal for every replica). In addition, the adaptive greedy strategy is efficient especially when there are a great number of replicas or RSUs to be matched.