# Cluster-Based Cooperative Cache Deployment and Coded Delivery Strategy in C-V2X Networks

Authors: Haizhou Bao; Yiming Huo; Chuanhe Huang; Xiaodai Dong; Wanyu Qiu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Cellular vehicle-to-everything- (C-V2X-) based communications can support various content-oriented applications and have gained significant progress in recent years. However, the limited backhaul bandwidth and dynamic topology make it difficult to obtain the multimedia service with high-reliability and low-latency communication in C-V2X networks, which may degrade the quality of experience (QoE). In this paper, we propose a novel cluster-based cooperative cache deployment and coded delivery strategy for C-V2X networks to improve the cache hit ratio and response time, reduce the request-response delay, and improve the bandwidth efficiency. To begin with, we design an effective vehicle cluster method. Based on the constructed cluster, we propose a two-level cooperative cache deployment approach to cache the frequently requested files on the edge nodes, LTE evolved NodeB (eNodeB) and cluster head (CH), to maximize the overall cache hit ratio. Furthermore, we propose an effective coded delivery strategy to minimize the network load and the ratio of redundant files. Simulation results demonstrate that our proposed method can effectively reduce the average response delay and network load and improve both the hit ratio and the ratio of redundant files.


---

## Body

## 1. Introduction

In recent years, cellular communications, edge computing, artificial intelligence (AI), etc., have greatly promoted the development of the cellular vehicle-to-everything (C-V2X) networks. At present, C-V2X is widely used in many scenarios such as road multimedia-related entertainment messages [1, 2], autonomous driving [3, 4], and emergency services [5]. Mobile devices, such as smartphones [6] and onboard navigation devices with wireless connectivity, have become more popular in recent years. However, these devices occupy considerable network bandwidth while providing users with a comfortable and enjoyable experience, especially when high-definition videos and games with significant network access requirements are usually the desired application scenarios. Furthermore, latency is more sensitive in most aforementioned applications and will largely impact the quality of service (QoS) and vehicle (user) experiences, especially for some delay-sensitive scenarios. How to reduce the network load and ensure network QoS is a major challenge in C-V2X networks with limited bandwidth resources.On the other hand, edge cache technology can effectively alleviate the pressing issues stem from the increasing data traffic in C-V2X networks. For example, it can also effectively reduce the response time to user requests, especially when users repeatedly request the same file from a remote server; a lot of network resources are wasted [7]. To avoid this problem, network edge nodes can prefetch part of the file from a remote server to cache [8], when a requested file is cached at the edge nodes by directly downloading from the edge node (user or eNodeB) to reduce the traffic load transmitted in the entire network, which can also reduce the response delay.Furthermore, the centralized architecture of the cellular network and its limited transmission capacity makes it difficult to cope with growing traffic demands. Also, due to the high velocity of vehicles in C-V2X networks and frequent changes of network topology, it is difficult to obtain reliable links among vehicle users and receive the desired data from neighbor vehicles or the nearby eNodeBs reliably and efficiently in C-V2X networks. There have been some research works on addressing this topic, for example, vehicle users on the road are divided into multiple clusters based on certain similar attributes [9, 10], i.e., velocity and position. Cluster members and cluster heads are continuously updated according to certain conditions. Furthermore, the dynamic network can be transformed into a static network as presented in research [11]. To satisfy users’ requests and ensure high QoS, it is necessary to improve the request hit ratio and reduce the delay for users to obtain the required data. Due to the various request probabilities of different files in the system, current research widely suggests that caches with high request probabilities should be preferentially deployed in edge nodes [12, 13] to improve the hit ratio as different cache deployment strategies will lead to different request delay. Moreover, a smaller request delay and a higher hit ratio can be obtained by optimizing the cache deployment strategy, which can also reduce the network load of the backhaul link. To reduce the network bandwidth resources consumed by user requests, utilizing a coded delivery method based on subfile coding [14, 15] can eliminate redundancy among multiple requested files and also reduce redundancy among subfiles. Due to ignoring the impact of cache deployment strategy on response delay and bandwidth [16], we combine the cache strategy and the transmission strategy to discuss their impacts on C-V2X networks in this article.In this paper, we investigate a novel cluster-based two-level cooperative cache deployment and coded delivery strategy for C-V2X networks to improve the cache hit ratio, reduce the response time, and improve the bandwidth usage efficiency. The main contributions of this paper are summarized as follows:(i)
To make the communication in C-V2X networks efficient and robust, we design a stable and reliable vehicle cluster, which includes the CH selection, the cluster formation, and the cluster merging. Based on the constructed cluster, we propose a two-level cooperative cache deployment strategy to reduce the response time and improve the hit ratio, where the response time for all user requests is defined as a function of the cache deployment decision, and then derive the optimal cache decision for the CH and eNodeB in C-V2X network(ii)
We propose a coded delivery strategy, i.e., file coding and subfile coding, on the edge cache nodes when they receive the users’ request. At this stage, the formulation of the coded delivery problem is formulated as a multiobjective set cover problem (MOSCP), which is an NP-hard problem. Eventually, we propose an efficient heuristic algorithm to minimize the transmission network load and the ratio of redundant files and satisfy users’ requests at the same timeThe rest of this paper is organized as follows: Section2 investigates and summarizes both the cache deployment scheme and coded delivery scheme on the Internet of Vehicles (IoV). Section 3 proposes a network model and processing procedure. In Section 4, first of all, we propose an effective cluster method, which includes a cluster head selection, cluster formation, and cluster merging. The cluster head selection metric is based on average relative speed, average relative distance, and average link availability. On the other hand, we propose a two-level cooperative caching approach to reduce the overall delay and improve the hit ratio. Eventually, we propose a coded delivery scheme to reduce the network load and improve the bandwidth efficiency with an effective heuristic algorithm. Section 7 validates our proposed models and analyzes the impact of cache size, size per file, average velocity, and arrival rate on the system performance. Section 8 summarizes this paper.


## 2. Related Work

As a new technology, many researchers have conducted researches on V2X to provide low-latency and high-reliability communication for automatic driving. Guan et al. [17] proposed an analytical model, simulation, measurement, and implementation of the bistatic radar cross-section (RCS) of traffic signs for V2X communications. Li et al. [18] have proposed to predict the near-field bistatic scattering of vehicles by taking advantage of the SCs of the vehicle in the C-V2X network. There have been also a handful of previous research about edge service or edge cache deployment C-V2X networks to improve the network performance. Ortiz et al. have proposed the virtual OBU at the network edge to reduce the complexity to implement local General Data Protection Regulation (GDRP) to guarantee privacy and access to sensitive data. Some researchers focus on eNodeB-based cache strategies [19, 20], and others focus on vehicle-based cache strategies [21], where both eNodeB (specify RSU) and vehicle users are network edge nodes. However, these methods usually only consider one node’s cache strategy to optimize the target and ignored the cooperative cache mode among multiple nodes. Some other researches have also considered using two types of cache simultaneously, i.e., eNodeB and vehicle users cache files at the same time [22], but all vehicle users participate to cache files to satisfy the requests of neighbor nodes, which will waste a lot of network resources; furthermore, in the cluster-based cache method, all cluster member nodes cache different files [23, 24], which also faces the problem of resource waste. The caching strategy mentioned above either leads to low cache efficiency due to only some edge nodes that participate in the cache strategy or causes excessive waste of resources because all edge nodes participate in the cache strategy.As motivated by solving the issue of the low bandwidth efficiency in C-V2X networks, many researchers have conducted significant research on data transmission methods based on the cache and coded delivery scheme. Liu et al. in [25] proposed a transmission method based on cache coding. Vehicle users cache coded data packets that cannot be decoded immediately, which can significantly improve the bandwidth efficiency of eNodeB. At the same time, to improve transmission efficiency, cache nodes will transmit data to multiple users via coding according to multiple file requests received. Bitaghsir and Khonsari in [26] modeled and analyzed the method of coded delivery in a hybrid network, proposed a subfile coding method, and considered that the traffic data of users within a hop range was transmitted by coding, but they ignore redundant files of user requests. Liu et al. in [27] considered designing an optimal coding scheme under cache constraints. However, transmitting the same data within one hop range would still cause users to waste bandwidth resources. Ramakrishnan et al. in [28] proposed to divide a file into subfiles and code the subfiles and then transmit them to users, which can effectively reduce the traffic on the shared link. Asghari et al. studied the optimal coded delivery scheme for arbitrary file deployment [14, 15] and formulated the problem as a set cover problem, which however ignored the redundant data among subfiles in the packet. Such data packets may cause repeated transmission of the same subfiles and still waste a lot of network bandwidth.Because of the limitations of the above methods, we focus on investigating the cluster method to make the communication more reliable, designing a two-level cooperative caching approach to improve the hit ratio and reduce the request delay, and coded delivery method to reduce the network load and further to improve the network performance.


## 3. Network Model and System Model

### 3.1. Network Model

We consider a C-V2X network scenario, where there areK eNodeBs, i.e., eNB1,eNB2,⋯,eNBK, and several vehicle users are randomly deployed in the network. The system structure diagram is depicted in Figure 1, in which the CH is a cluster head, the green dot circle represents a cluster, and vehicles in the cluster except the CH are cluster members. Each vehicular node uses the LTE-V standard supporting the side link or the vehicle-to-vehicle (V2V) communications by adopting the PC5 interface in the LTE system. The yellow dash line is a side link that is used for V2V communications with the PC5 interface, while the blue dash line is the link used for vehicle-to-infrastructure (V2I) communication with Uu interface.Figure 1
Network model.


### 3.2. System Model

The system model includes two parts: cluster-based two-level cooperative cache deployment strategy and coded delivery strategy. In cluster-based two-level cooperative cache deployment, we first propose a vehicle cluster model according to the vehicle speed, the position, and other information for reliable communication and then design an optimal cache deployment strategy to reduce the response delay and improve the hit ratio. Furthermore, we propose a coded delivery method to reduce the transmission load. From an overall standpoint, our system model is depicted in Figure2.Figure 2
System model.


## 3.1. Network Model

We consider a C-V2X network scenario, where there areK eNodeBs, i.e., eNB1,eNB2,⋯,eNBK, and several vehicle users are randomly deployed in the network. The system structure diagram is depicted in Figure 1, in which the CH is a cluster head, the green dot circle represents a cluster, and vehicles in the cluster except the CH are cluster members. Each vehicular node uses the LTE-V standard supporting the side link or the vehicle-to-vehicle (V2V) communications by adopting the PC5 interface in the LTE system. The yellow dash line is a side link that is used for V2V communications with the PC5 interface, while the blue dash line is the link used for vehicle-to-infrastructure (V2I) communication with Uu interface.Figure 1
Network model.


## 3.2. System Model

The system model includes two parts: cluster-based two-level cooperative cache deployment strategy and coded delivery strategy. In cluster-based two-level cooperative cache deployment, we first propose a vehicle cluster model according to the vehicle speed, the position, and other information for reliable communication and then design an optimal cache deployment strategy to reduce the response delay and improve the hit ratio. Furthermore, we propose a coded delivery method to reduce the transmission load. From an overall standpoint, our system model is depicted in Figure2.Figure 2
System model.


## 4. Cluster-Based Two-Level Cooperative Cache Deployment Strategy

### 4.1. Vehicle Cluster Model

We assume that vehicles in a cluster can communicate with a CH directly, and the CH can also communicate with its connected eNodeB directly. The status of a vehicle in a cluster includes Undecided Node (UN), CH, and cluster member (CM) as stated in [29, 30]. The clustering procedure includes the CH selection strategy, the cluster maintenance strategy, and the cluster merging strategy.Vehicles can exchange and collect necessary information about their one-hop vicinities reactively with each other through periodic beacon messages. Each vehicleVi constructs its neighbor list NLi; here, we assume the neighbor refers to the relative distance Δdi,j between any two vehicles Vi and Vj is less than the communication range R. After the necessary information from the disseminated beacon messages has been received, each vehicle can calculate three important factors, such as the relative distance, the relative speed, and the link reliability for one-hop neighbors within the communication range R.


### 4.2. Average Relative Speed and Average Relative Distance

The position and the velocity ofVi at time t can be presented as pit=pixt,piyt and vit=vixt,viyt, respectively. Similarly, the position and the velocity of Vj at time tpjt=pjxt,pjyt and vjt=vjxt,vjyt, respectively. Note that vehicles may be driving on the inverse direction, where the velocity is negative. The relative distance is Δdi,jt=pixt−pjxt2+piyt−pjyt22; similarly, the relative velocity is Δvi,jt=vixt−vjxt2+viyt−vjyt22. Therefore, the average relative distance Δdi¯t and average relative velocity Δvi¯t between vehicle Vi and its neighbors are given as
(1)Δdi¯t=1∣NLi∣∑Vj∈NLiΔdi,jt,(2)Δvi¯t=1∣NLi∣∑Vj∈NLiΔvi,jt,where NLi is the number of vehicle nodes in the neighbor list of vehicle Vi.


### 4.3. LLT and Link Reliability

The LLT describes the ability to maintain the connection of two vehicles. When two vehicles are moving in the same or opposite directions, the LLT between vehicleVi and vehicle Vj can be given as [31]
(3)LLTi,jt=R2Δvx2t+Δvy2t−ΔpxtΔvyt−ΔpytΔvxt2Δvx2t+Δvy2t−ΔpxtΔvxt−ΔpytΔvytΔvx2t+Δvy2t,where
(4)Δvxt=vixt−viyt,Δvyt=vjxt−vjyt,Δpxt=pixt−piyt,Δpxt=pixt−pjyt.Link reliability is the probability that a direct communication linkli,j will be available between two vehicles Vi and Vj over a particular time t. We assume that the velocity of vehicle Vi, vi, follows the Gaussian distribution Nμ,σ2 [11]. Furthermore, the probability density function (PDF) of the link communication duration T between vehicle Vi and vehicle Vj is [11]
(5)fT=4RσΔvi,j2πT2e−2R/T−μΔvi,j2/2σΔvi,j2,∀T>0,where Ri,j represents the relative transmission range, and μΔvi,j and σΔvi,j denote the mean and standard variation of relative velocity between vehicle Vi and vehicle Vj, respectively.The probability of the linkli,j between vehicle Vi and Vj is available during LLTi,j [32], which also represents the reliability of link li,j between vehicle Vi and Vj during LLTi,j and can be given as
(6)rtli,j=∫tt+LLTi,jfTdt=erf2R/t−μΔvi,jσΔi,j2−erf2R/t+LLTi,j−μΔvi,jσΔi,j2,LLTi,j>0,where erf is the Gauss error function [11].The average link reliability is given as(7)rtli,j¯=1∣NLi∣∑Vj∈NLirtli,j.According to the above definition, the largerrtli,j¯ is, the more reliable the links between the vehicle Vi and its neighbor nodes are. Furthermore, the smaller the Δdi¯ and Δvi¯ are, the more stable the topology is. Therefore, we use a score to evaluate the stability of each vehicle Vi as follows:
(8)Si=αi1−Δdi¯Δdmax+βi1−Δvi¯Δvmax+γirtli,j¯rtli,jmax,where Δdmax, Δvmax, and rtli,jmax denote the maximum relative distance, maximum relative speed, and maximum link reliability, respectively. αi, βi, and γi are the weight factor, and αi+βi+γi=1. We can easily find that the larger the score Si is, the more stable the cluster is. After the score is calculated for each vehicle, we can select an appropriate CH and then construct a cluster according to the score Si.


### 4.4. Procedure of Vehicle Cluster

The vehicle cluster construction includes three steps as follows:(i)
CH Selection. Each vehicle (UN) broadcasts a beacon message to all surrounding vehicles periodically, which includes its location, velocity, and direction information. To start with, each user exchanges beacon messages with its neighbors. Secondly, each user updates its neighbor list NLi after receiving the beacon messages from its neighbors and then calculates the score Si for itself and its neighbors. The vehicle with the highest score in the neighbor list (NL) is chosen as the CH, and it will broadcast the message CH_ACK to all its neighbors to announce itself as the CH and sets the timer CH_TIMER for its neighbors to finish a cluster construction(ii)
Cluster Formation. After a neighboring vehicle Vj receives a message CH_ACK or a beacon message from the CH Vi (abbreviated as CHi), if it is not a cluster member of the cluster Vi which CHi belongs to, it will send a message JOIN_REQ to the CHi to join the cluster Vi. When the CHi receives a message JOIN_REQ from a neighbor node Vj, the CHi will judge whether the neighbor vehicle Vj can join the current cluster. If the size of the current cluster NCMi of cluster Vi exceeds the maximum threshold value NCMmax, vehicle Vj is not allowed to join in the cluster; otherwise, CHi will send a joining message JOIN_RESP to the vehicle Vj and add the vehicle Vj to its cluster member list CMLISTi. If vehicle Vj receives a message JOIN_RESP within the duration JOIN_TIMER, it will change its status to a cluster member as CMi; otherwise, it will still keep its status as UN. The CH will broadcast the message that a new neighbor node joins the cluster to all the cluster members. If the vehicle can not join another cluster, and if the score Si of the vehicle is the largest value within the neighbor list, it will change its status to the CH and broadcast CH_ACK to its neighbor vehicles(iii)
Cluster Merging. When two clusters are too close that they overlap with each other, the overlapped area may consume more resources; consequently, we can merge these two clusters. When a CH Vi receives a beacon message from another CH Vj, if the potential size of the merged cluster is not larger than the threshold NCMmerg≤NCMmax and LLTi,j≥ω (Vi,Vj are the CH node), the CH with a smaller score will change its status to CM. Simultaneously, another CH with a higher score keeps the status as the CHAlgorithm 1: Cluster method.
Input: Velocity v, position xi,yi, and vehicle transmission radius R.Output: Cluster Head and Cluster Member.// CH Selection and Cluster Formationfor each vehicle with statei==UNdoVehicleVi calculate the score for itself and its neighbor Sisj according to (8)Vehicle withmaxSi announce it as CH and broadcast CH¯ACK and set CH¯TIMER;whileCH¯TIMER>0doif vehicle Vj receives CH¯ACK or beacon from CHithenVehicleVj unicasts JOIN¯REQ to CHi and set JOIN¯TIMERwhileJOIN¯TIMER>0doif vehicle Vj receives JOIN¯RESPthenCMi← vehicle Vj// change status toCMielsestatej←UN// keep the statusUNendendendifCHi receives JOIN¯REQ && NCMi+1≤NCMmaxthenCHi will unicasts JOIN¯RESP to vehicle Vj and add Vj to CMLISTiendendend// Cluster Mergingfor any two CHi and CHjdoifΔdi,j<Lc&&LLTi,j>ω && NCMi+NCMj≤NCMmaxthenTheCHj with smaller score Sj will change its CHi to CMi and add all its member to CMLISTiendend


### 4.5. Algorithm Description for Vehicle Cluster

In Algorithm1, lines 1-19 are the description of CH selection and cluster formation, and cluster merging procedure is described from lines 20 to 24. From line 2 to line 3, each vehicle calculates scores based on the obtained beacon message and the vehicle with the highest score is a CH, which can send CH¯ACK and set the timer CH¯TIMER. Lines 4-18 describe that the cluster member joins the cluster and the CH responds to the vehicle to join. During the CH timer CH¯TIMER, if the vehicle receives a message CH¯ACK, and it is not a member of the CHi, it will unicast the message JOIN¯REQ and then set the timer JOIN¯TIMER. During the JOIN¯TIMER, if the vehicle receives the message JOIN¯RESP, it will change its status to CMi, i.e., the cluster member of CHi. Otherwise, it will keep UN status. On the other hand, lines 15-17 describe the response of the CHi when it receives a message. If the CHi receives the message JOIN¯REQ and the potential number of CM, NCMi+1, is still smaller than the maximum number of CM NCMmax, the CHi will respond with the message JOIN¯RESP to the vehicle Vj. From lines 20 to 24, it is the procedure of cluster merging. If the distance of any two CH is smaller than the threshold Lc, the link duration between the two CHs is larger than a threshold ω, the total potential cluster member of the two clusters is not larger than the maximum value NCMmax, and then the CH with smaller score will give up its CH status and then change its status to CMi and add all its members to the CMLISTi.


### 4.6. Two-Level Cooperative Cache Model

#### 4.6.1. Cluster Size and Cluster Number

Assume that the arrival rate of vehicles follows a Poisson process, the distance between two vehicles follows an exponential distribution; the average number of vehicles in a cluster can be denoted as [29]
(9)Nc¯=ENc=1e−λRE1/V,where
(10)E1V=∫vminvmax1vfVvdv,where ⨆ is a floor function and R is the vehicle’s communication radius. Consequently, the average number of vehicles under the coverage of eNodeB is
(11)Nk=2Re×ρ¯=2Reρ¯,where ρ¯=λE1/V is the average density of vehicles [30], and Re is the transmission radius of eNodeB. Meanwhile, we can also obtain the average number of clusters under the coverage of the eNodeB, i.e., Nck=Nk/Nc¯.


#### 4.6.2. Request and Response Procedure

In this paper, the response mode for file request has four types as shown in Figure3, where the purple solid line and the dashed line are the request and response action, respectively. First of all, a file request from a CM is forwarded to a CH in the cluster; if the requested file is cached by the CH, the CH will respond to the request by transmitting the file to the user directly (e.g., steps (1) → (2)); otherwise, the request will be forwarded to the nearby eNodeB. Besides, if the eNodeB has cached the file, the eNodeB will immediately broadcast the file to the user (e.g., steps (3)→ (4)); otherwise, the eNodeB will forward the request to its neighboring eNodeB. Furthermore, if the neighboring eNodeBs have cached the requested file, the neighboring eNodeB will respond to the request of the user through the original eNodeB (e.g., steps (3)→ (5)→ (6)→ (4)); otherwise, the request will be forwarded to a remote server. Eventually, the server will transmit the file to the eNodeB and then forward it to the user (e.g., steps (3)→ (7) → (8)→ (4)).Figure 3
Request and response procedure.


#### 4.6.3. Delay of File Request

According to procedure4.6.2, we summarize the response delay as follows:
(i)
Response by the CH. The delay for a user to obtain a file from CH in a cluster is(12)tv2c=sqBvlog21+Pchc,j2/ξ2+∑n=1,n≠jN¯cPnhc,j2,where sq is the file size, the denominator represents the transmission rate between the vehicle Vj and the CH, hc,j is the channel coefficient from cluster head c to other vehicle Vj, Nc¯ is the total number of vehicles in the cluster, Pc is the transmit power of the CH, Bv is the channel bandwidth for the vehicle, ξ2 is the noise power, and Pn is the transmit power of other vehicles in the cluster, and the sum term in the denominator is total interferences from other vehicles to the current vehicle Vj in the cluster
(ii)
Response by eNodeB or Neighboring eNodeB. If the user cannot download the file from the CH in the cluster, the connected eNodeB or neighboring eNodeB will be scheduled to respond to the request. The response delay can be denoted, respectively, as follows:
(13)tv2R=sqBclog21+Prhr2/ξ2,tv2R¯=TNhop+tv2R,where tv2R is the delay from a eNodeB to a user and tv2R¯ is the delay from the user to the nearby eNodeB. The denominator denotes the transmission rate between the vehicle Vj and the corresponding eNodeB, Bc is the subchannel bandwidth allocated to the user Vj, hr is the channel coefficient from eNodeB to the user, Pr is the transmit power of the eNodeB, and ξ2 is the noise power. TNhop is the transmission delay from neighboring eNodeB to current eNodeB with Nhop hops; here, we assume the Nhop=1, and the transmission delay is usually milliseconds(iii)
Response by Remote Server. When the edge cache nodes (vehicle users) or neighbor eNodeB have not cached the file that the user requests, the user needs to download the file from a remote server. The latency of the response from a remote server is
(14)tv2s=sqRr2s+tv2R,where the first item is the delay from the remote server to the eNodeB and Rr2s is the transmission rate of the backhaul link. The second term is the delay from the eNodeB to the current user


#### 4.6.4. Hit Ratio of All Users

After obtaining the file request delay for four modes, we design an efficient cache strategy to reduce the average total delay for all file requests and satisfy the cache capacity for each node. We useQ=1,2,3,⋯,Q to represent the file library, where Q is the total number of files. Each file has sq bits with a different request probability; besides, the files are stored on a remote server in order from high to low according to the request probability. We use Zipf distribution to model the request probability of a file [33]; as a result, the probability that a file q is requested is
(15)pq=q−β∑i=1Qi−β,where β≥0 is the bias parameter of Zipf, which indicates popularity. Generally, the larger the value is, the more concentrated the request will be. We assume that all vehicles will just request once (different requests from the same vehicle can be seen as different requests from different vehicles). Obviously, the probability that all files requested by different users satisfy ∑q=1Qpq=1.We adopt a two-level edge cache strategy based on CH and eNodeB [24, 34] to improve the hit ratio and reduce the response time for all requests. The CH and eNodeB are the first and second layer cache nodes, respectively, and they cache different files. Furthermore, all CHs under the coverage of the eNodeB eNBk cache the same files. Let Vc and Vk denote the cache capacity of a vehicle and an eNodeB, respectively. On the other hand, we use the matrix Hiq=hiqkK∗I∗Q to indicate whether the ii∈1,2 layer under the coverage of the eNodeB eNBk stores the file q, if affirmative hiqk is 1, otherwise 0. Additionally, the probability that files q is requested under the coverage of eNodeB eNBk is denoted as pqk.The hit ratio of user requests under eNodeBeNBk coverage is defined as follows:
(16)HeNBk=∑k=1K∑q=1Qpqk∑i=12hiqk+∑k=1K∑q=1QpqkDq−h2qk−h1qk+∑k=1K∑q=1Q1−Dqpqk,where Dq=0,1 indicates whether the file q is cached at least one edge node (eNodeB or CH), and if affirmative, Dq=1 (at least one edge node can satisfy the user’s request, that is, h2qk=1 or h1qk=1), otherwise 0 (h2qk=0 and h1qk=0).


#### 4.6.5. Problem Formulation of Optimal Cache Deployment

Based on the hit ratio definition, we can formulate the problem as a response delay with a different cache strategy. According to the request procedure, the request delay is modeled as a function of the cache strategy. To reduce the overall delay for users to obtain the requested files and satisfy the constraints of cache size for each cache node, the problem can be formalized as follows:(17)minhiqk∑k=1Ktv2c∑q=1Qpqkh1qk+tv2R∑q=1Qpqkh2qk+tv2R¯∑q=1QpqkDq−∑i=12hiqk+tv2s∑q=1Q1−Dqpqks.t.∑i=12hiqk≤1,∑q=1Qh1qk≤Vc,∑q=1Qh2qk≤Vk,∑q=1Qhiqk∈0,1,∀i∈1,2.The cache strategy of the CH will directly affect the eNodeB cache strategy; thus, the cache strategy of the CH should be given a priority. In other words, each CH under the coverage of the eNodeBeNBk caches the most frequently requested files, namely, each CH should cache Vc files in order from high to low according to the request probability of each file. Consequently, each eNodeB eNBk selects files from the remaining file list Vc+1,Q to cache. Problem (17) can be further transformed into the following formation:
(18)minh2qk∑k=1Ktv2R∑q=Vc+1Qpqk∗h2qk+tv2R¯∑q=Vc+1QpqkDq′−h2qk+tv2s∑q=Vc+1Qpqk1−Dq′s.t.∑q=Vc+1Qh2qksq≤Vk,h2qk∈0,1,where Dq′=0,1 indicates that the file q is stored at least one edge node, i.e., CH or eNodeB. Particularly, the sum of the request probabilities for a file q under the coverage of eNodeB eNBk should satisfy
(19)∑k=1Kpkq=pq.We can convert problem (18) into
(20)minh2qktv2R∑q=Vc+1Qpqh2qk+tv2R¯∑q=Vc+1QpqDq′−h2qk+tv2s∑q=Vc+1Qpq1−Dq′s.t.∑q=Vc+1Qh2qk≤Vk,h2qk∈0,1,where the sum of request probabilities pq [12, 22] can be expressed as
(21)fx=∑q=Vc+1xpq≈∫Vc+1x1/qβ∑q=Vc+1Q1/qβdq=x1−β−Vc+1Q1−β−11−β.


#### 4.6.6. Algorithm Design for Optimal Cache Deployment

To reduce the overhead of downloading files from remote servers or neighboring eNodeBs and simplify problem (20), each eNodeB can cache some identical files and a part of different files [35]. We assume that αVk of eNodeB capacity is used to cache the same files, and K1−αVk of eNodeB capacity will be used to cache different files for the total K eNodeBs; therefore, the total capacity of cached files on the eNodeB is Vk+K1−αVk,α∈0,1. The total hit ratio for all files is the sum of the hit ratio of caching the same file, and the mean hit ratio of caching different file. Consequently, the hit ratio to obtain files from eNodeBs can be expressed as
(22)HeNodeB=fαVk+K1−αVk+Vc−fαVk+VcK+fαVk+Vc.On the other hand, the hit ratio to obtain the requested files from neighbor eNodeBs through cooperation is(23)Hcoop=K−1KfαVk+K1−αVk+Vc−fαVk+Vc.After substituting (21), (22), and (23) into problem (20), the problem can be reduced to
(24)minαtv2RHeNodeB+tv2R¯Hcoop+tv2s1−HeNodeB−Hcoop=tv2s−tv2s−tv2RHeNodeB−tv2s−tv2R¯Hcoops.t.α∈0,1.Eventually, this problem can be transformed into the following equation:(25)maxαtv2s−tv2RHeNodeB+tv2s−tv2R¯Hcoops.t.α∈0,1.This problem can be solved by the first derivative for the following two equations:(26)dHeNodeBdα=K−1Vk1−βKQ1−β−1∗αVk+Vc1/β−αVk+K1−αVk+Vc1/β,dHcoopdα=K−1Vk1−βKQ1−β−1∗1−KαVk+K1−αVk+Vc1/β−αVk+Vc1/β.Combining the two equations in (26), we can obtain the solution (27) to the original problem (17). The procedure can be seen as Algorithm 2, and here, we assume that the merge sort algorithm is adopted at line 3, and the time complexity of Algorithm 2 is OK∗QlogQ, where K is the number of eNodeBs and Q is the total number of files.
(27)α∗≈tv2R¯−tv2R1/βKVk+Vc−Ktv2s−K−1tv2R¯−tv2R1/βVcKtv2s−K−1tv2R¯−tv2R1/βVk+tv2R¯−tv2R1/βK−1Vk.Algorithm 2: Optimal cache strategy.
Input: Cache capacity of vehicle and eNodeB, Vc, Vk, respectively.Output: Optimal cache Strategy for eNodeB and CH.fork=1toKdoCalculate the request probability,pqk, for each fileSort files in the descending order withpqk;CacheVc files on cluster headCalculate the optimal cache decision for eacheNBk according to (27);end


## 4.1. Vehicle Cluster Model

We assume that vehicles in a cluster can communicate with a CH directly, and the CH can also communicate with its connected eNodeB directly. The status of a vehicle in a cluster includes Undecided Node (UN), CH, and cluster member (CM) as stated in [29, 30]. The clustering procedure includes the CH selection strategy, the cluster maintenance strategy, and the cluster merging strategy.Vehicles can exchange and collect necessary information about their one-hop vicinities reactively with each other through periodic beacon messages. Each vehicleVi constructs its neighbor list NLi; here, we assume the neighbor refers to the relative distance Δdi,j between any two vehicles Vi and Vj is less than the communication range R. After the necessary information from the disseminated beacon messages has been received, each vehicle can calculate three important factors, such as the relative distance, the relative speed, and the link reliability for one-hop neighbors within the communication range R.


## 4.2. Average Relative Speed and Average Relative Distance

The position and the velocity ofVi at time t can be presented as pit=pixt,piyt and vit=vixt,viyt, respectively. Similarly, the position and the velocity of Vj at time tpjt=pjxt,pjyt and vjt=vjxt,vjyt, respectively. Note that vehicles may be driving on the inverse direction, where the velocity is negative. The relative distance is Δdi,jt=pixt−pjxt2+piyt−pjyt22; similarly, the relative velocity is Δvi,jt=vixt−vjxt2+viyt−vjyt22. Therefore, the average relative distance Δdi¯t and average relative velocity Δvi¯t between vehicle Vi and its neighbors are given as
(1)Δdi¯t=1∣NLi∣∑Vj∈NLiΔdi,jt,(2)Δvi¯t=1∣NLi∣∑Vj∈NLiΔvi,jt,where NLi is the number of vehicle nodes in the neighbor list of vehicle Vi.


## 4.3. LLT and Link Reliability

The LLT describes the ability to maintain the connection of two vehicles. When two vehicles are moving in the same or opposite directions, the LLT between vehicleVi and vehicle Vj can be given as [31]
(3)LLTi,jt=R2Δvx2t+Δvy2t−ΔpxtΔvyt−ΔpytΔvxt2Δvx2t+Δvy2t−ΔpxtΔvxt−ΔpytΔvytΔvx2t+Δvy2t,where
(4)Δvxt=vixt−viyt,Δvyt=vjxt−vjyt,Δpxt=pixt−piyt,Δpxt=pixt−pjyt.Link reliability is the probability that a direct communication linkli,j will be available between two vehicles Vi and Vj over a particular time t. We assume that the velocity of vehicle Vi, vi, follows the Gaussian distribution Nμ,σ2 [11]. Furthermore, the probability density function (PDF) of the link communication duration T between vehicle Vi and vehicle Vj is [11]
(5)fT=4RσΔvi,j2πT2e−2R/T−μΔvi,j2/2σΔvi,j2,∀T>0,where Ri,j represents the relative transmission range, and μΔvi,j and σΔvi,j denote the mean and standard variation of relative velocity between vehicle Vi and vehicle Vj, respectively.The probability of the linkli,j between vehicle Vi and Vj is available during LLTi,j [32], which also represents the reliability of link li,j between vehicle Vi and Vj during LLTi,j and can be given as
(6)rtli,j=∫tt+LLTi,jfTdt=erf2R/t−μΔvi,jσΔi,j2−erf2R/t+LLTi,j−μΔvi,jσΔi,j2,LLTi,j>0,where erf is the Gauss error function [11].The average link reliability is given as(7)rtli,j¯=1∣NLi∣∑Vj∈NLirtli,j.According to the above definition, the largerrtli,j¯ is, the more reliable the links between the vehicle Vi and its neighbor nodes are. Furthermore, the smaller the Δdi¯ and Δvi¯ are, the more stable the topology is. Therefore, we use a score to evaluate the stability of each vehicle Vi as follows:
(8)Si=αi1−Δdi¯Δdmax+βi1−Δvi¯Δvmax+γirtli,j¯rtli,jmax,where Δdmax, Δvmax, and rtli,jmax denote the maximum relative distance, maximum relative speed, and maximum link reliability, respectively. αi, βi, and γi are the weight factor, and αi+βi+γi=1. We can easily find that the larger the score Si is, the more stable the cluster is. After the score is calculated for each vehicle, we can select an appropriate CH and then construct a cluster according to the score Si.


## 4.4. Procedure of Vehicle Cluster

The vehicle cluster construction includes three steps as follows:(i)
CH Selection. Each vehicle (UN) broadcasts a beacon message to all surrounding vehicles periodically, which includes its location, velocity, and direction information. To start with, each user exchanges beacon messages with its neighbors. Secondly, each user updates its neighbor list NLi after receiving the beacon messages from its neighbors and then calculates the score Si for itself and its neighbors. The vehicle with the highest score in the neighbor list (NL) is chosen as the CH, and it will broadcast the message CH_ACK to all its neighbors to announce itself as the CH and sets the timer CH_TIMER for its neighbors to finish a cluster construction(ii)
Cluster Formation. After a neighboring vehicle Vj receives a message CH_ACK or a beacon message from the CH Vi (abbreviated as CHi), if it is not a cluster member of the cluster Vi which CHi belongs to, it will send a message JOIN_REQ to the CHi to join the cluster Vi. When the CHi receives a message JOIN_REQ from a neighbor node Vj, the CHi will judge whether the neighbor vehicle Vj can join the current cluster. If the size of the current cluster NCMi of cluster Vi exceeds the maximum threshold value NCMmax, vehicle Vj is not allowed to join in the cluster; otherwise, CHi will send a joining message JOIN_RESP to the vehicle Vj and add the vehicle Vj to its cluster member list CMLISTi. If vehicle Vj receives a message JOIN_RESP within the duration JOIN_TIMER, it will change its status to a cluster member as CMi; otherwise, it will still keep its status as UN. The CH will broadcast the message that a new neighbor node joins the cluster to all the cluster members. If the vehicle can not join another cluster, and if the score Si of the vehicle is the largest value within the neighbor list, it will change its status to the CH and broadcast CH_ACK to its neighbor vehicles(iii)
Cluster Merging. When two clusters are too close that they overlap with each other, the overlapped area may consume more resources; consequently, we can merge these two clusters. When a CH Vi receives a beacon message from another CH Vj, if the potential size of the merged cluster is not larger than the threshold NCMmerg≤NCMmax and LLTi,j≥ω (Vi,Vj are the CH node), the CH with a smaller score will change its status to CM. Simultaneously, another CH with a higher score keeps the status as the CHAlgorithm 1: Cluster method.
Input: Velocity v, position xi,yi, and vehicle transmission radius R.Output: Cluster Head and Cluster Member.// CH Selection and Cluster Formationfor each vehicle with statei==UNdoVehicleVi calculate the score for itself and its neighbor Sisj according to (8)Vehicle withmaxSi announce it as CH and broadcast CH¯ACK and set CH¯TIMER;whileCH¯TIMER>0doif vehicle Vj receives CH¯ACK or beacon from CHithenVehicleVj unicasts JOIN¯REQ to CHi and set JOIN¯TIMERwhileJOIN¯TIMER>0doif vehicle Vj receives JOIN¯RESPthenCMi← vehicle Vj// change status toCMielsestatej←UN// keep the statusUNendendendifCHi receives JOIN¯REQ && NCMi+1≤NCMmaxthenCHi will unicasts JOIN¯RESP to vehicle Vj and add Vj to CMLISTiendendend// Cluster Mergingfor any two CHi and CHjdoifΔdi,j<Lc&&LLTi,j>ω && NCMi+NCMj≤NCMmaxthenTheCHj with smaller score Sj will change its CHi to CMi and add all its member to CMLISTiendend


## 4.5. Algorithm Description for Vehicle Cluster

In Algorithm1, lines 1-19 are the description of CH selection and cluster formation, and cluster merging procedure is described from lines 20 to 24. From line 2 to line 3, each vehicle calculates scores based on the obtained beacon message and the vehicle with the highest score is a CH, which can send CH¯ACK and set the timer CH¯TIMER. Lines 4-18 describe that the cluster member joins the cluster and the CH responds to the vehicle to join. During the CH timer CH¯TIMER, if the vehicle receives a message CH¯ACK, and it is not a member of the CHi, it will unicast the message JOIN¯REQ and then set the timer JOIN¯TIMER. During the JOIN¯TIMER, if the vehicle receives the message JOIN¯RESP, it will change its status to CMi, i.e., the cluster member of CHi. Otherwise, it will keep UN status. On the other hand, lines 15-17 describe the response of the CHi when it receives a message. If the CHi receives the message JOIN¯REQ and the potential number of CM, NCMi+1, is still smaller than the maximum number of CM NCMmax, the CHi will respond with the message JOIN¯RESP to the vehicle Vj. From lines 20 to 24, it is the procedure of cluster merging. If the distance of any two CH is smaller than the threshold Lc, the link duration between the two CHs is larger than a threshold ω, the total potential cluster member of the two clusters is not larger than the maximum value NCMmax, and then the CH with smaller score will give up its CH status and then change its status to CMi and add all its members to the CMLISTi.


## 4.6. Two-Level Cooperative Cache Model

### 4.6.1. Cluster Size and Cluster Number

Assume that the arrival rate of vehicles follows a Poisson process, the distance between two vehicles follows an exponential distribution; the average number of vehicles in a cluster can be denoted as [29]
(9)Nc¯=ENc=1e−λRE1/V,where
(10)E1V=∫vminvmax1vfVvdv,where ⨆ is a floor function and R is the vehicle’s communication radius. Consequently, the average number of vehicles under the coverage of eNodeB is
(11)Nk=2Re×ρ¯=2Reρ¯,where ρ¯=λE1/V is the average density of vehicles [30], and Re is the transmission radius of eNodeB. Meanwhile, we can also obtain the average number of clusters under the coverage of the eNodeB, i.e., Nck=Nk/Nc¯.


### 4.6.2. Request and Response Procedure

In this paper, the response mode for file request has four types as shown in Figure3, where the purple solid line and the dashed line are the request and response action, respectively. First of all, a file request from a CM is forwarded to a CH in the cluster; if the requested file is cached by the CH, the CH will respond to the request by transmitting the file to the user directly (e.g., steps (1) → (2)); otherwise, the request will be forwarded to the nearby eNodeB. Besides, if the eNodeB has cached the file, the eNodeB will immediately broadcast the file to the user (e.g., steps (3)→ (4)); otherwise, the eNodeB will forward the request to its neighboring eNodeB. Furthermore, if the neighboring eNodeBs have cached the requested file, the neighboring eNodeB will respond to the request of the user through the original eNodeB (e.g., steps (3)→ (5)→ (6)→ (4)); otherwise, the request will be forwarded to a remote server. Eventually, the server will transmit the file to the eNodeB and then forward it to the user (e.g., steps (3)→ (7) → (8)→ (4)).Figure 3
Request and response procedure.


### 4.6.3. Delay of File Request

According to procedure4.6.2, we summarize the response delay as follows:
(i)
Response by the CH. The delay for a user to obtain a file from CH in a cluster is(12)tv2c=sqBvlog21+Pchc,j2/ξ2+∑n=1,n≠jN¯cPnhc,j2,where sq is the file size, the denominator represents the transmission rate between the vehicle Vj and the CH, hc,j is the channel coefficient from cluster head c to other vehicle Vj, Nc¯ is the total number of vehicles in the cluster, Pc is the transmit power of the CH, Bv is the channel bandwidth for the vehicle, ξ2 is the noise power, and Pn is the transmit power of other vehicles in the cluster, and the sum term in the denominator is total interferences from other vehicles to the current vehicle Vj in the cluster
(ii)
Response by eNodeB or Neighboring eNodeB. If the user cannot download the file from the CH in the cluster, the connected eNodeB or neighboring eNodeB will be scheduled to respond to the request. The response delay can be denoted, respectively, as follows:
(13)tv2R=sqBclog21+Prhr2/ξ2,tv2R¯=TNhop+tv2R,where tv2R is the delay from a eNodeB to a user and tv2R¯ is the delay from the user to the nearby eNodeB. The denominator denotes the transmission rate between the vehicle Vj and the corresponding eNodeB, Bc is the subchannel bandwidth allocated to the user Vj, hr is the channel coefficient from eNodeB to the user, Pr is the transmit power of the eNodeB, and ξ2 is the noise power. TNhop is the transmission delay from neighboring eNodeB to current eNodeB with Nhop hops; here, we assume the Nhop=1, and the transmission delay is usually milliseconds(iii)
Response by Remote Server. When the edge cache nodes (vehicle users) or neighbor eNodeB have not cached the file that the user requests, the user needs to download the file from a remote server. The latency of the response from a remote server is
(14)tv2s=sqRr2s+tv2R,where the first item is the delay from the remote server to the eNodeB and Rr2s is the transmission rate of the backhaul link. The second term is the delay from the eNodeB to the current user


### 4.6.4. Hit Ratio of All Users

After obtaining the file request delay for four modes, we design an efficient cache strategy to reduce the average total delay for all file requests and satisfy the cache capacity for each node. We useQ=1,2,3,⋯,Q to represent the file library, where Q is the total number of files. Each file has sq bits with a different request probability; besides, the files are stored on a remote server in order from high to low according to the request probability. We use Zipf distribution to model the request probability of a file [33]; as a result, the probability that a file q is requested is
(15)pq=q−β∑i=1Qi−β,where β≥0 is the bias parameter of Zipf, which indicates popularity. Generally, the larger the value is, the more concentrated the request will be. We assume that all vehicles will just request once (different requests from the same vehicle can be seen as different requests from different vehicles). Obviously, the probability that all files requested by different users satisfy ∑q=1Qpq=1.We adopt a two-level edge cache strategy based on CH and eNodeB [24, 34] to improve the hit ratio and reduce the response time for all requests. The CH and eNodeB are the first and second layer cache nodes, respectively, and they cache different files. Furthermore, all CHs under the coverage of the eNodeB eNBk cache the same files. Let Vc and Vk denote the cache capacity of a vehicle and an eNodeB, respectively. On the other hand, we use the matrix Hiq=hiqkK∗I∗Q to indicate whether the ii∈1,2 layer under the coverage of the eNodeB eNBk stores the file q, if affirmative hiqk is 1, otherwise 0. Additionally, the probability that files q is requested under the coverage of eNodeB eNBk is denoted as pqk.The hit ratio of user requests under eNodeBeNBk coverage is defined as follows:
(16)HeNBk=∑k=1K∑q=1Qpqk∑i=12hiqk+∑k=1K∑q=1QpqkDq−h2qk−h1qk+∑k=1K∑q=1Q1−Dqpqk,where Dq=0,1 indicates whether the file q is cached at least one edge node (eNodeB or CH), and if affirmative, Dq=1 (at least one edge node can satisfy the user’s request, that is, h2qk=1 or h1qk=1), otherwise 0 (h2qk=0 and h1qk=0).


### 4.6.5. Problem Formulation of Optimal Cache Deployment

Based on the hit ratio definition, we can formulate the problem as a response delay with a different cache strategy. According to the request procedure, the request delay is modeled as a function of the cache strategy. To reduce the overall delay for users to obtain the requested files and satisfy the constraints of cache size for each cache node, the problem can be formalized as follows:(17)minhiqk∑k=1Ktv2c∑q=1Qpqkh1qk+tv2R∑q=1Qpqkh2qk+tv2R¯∑q=1QpqkDq−∑i=12hiqk+tv2s∑q=1Q1−Dqpqks.t.∑i=12hiqk≤1,∑q=1Qh1qk≤Vc,∑q=1Qh2qk≤Vk,∑q=1Qhiqk∈0,1,∀i∈1,2.The cache strategy of the CH will directly affect the eNodeB cache strategy; thus, the cache strategy of the CH should be given a priority. In other words, each CH under the coverage of the eNodeBeNBk caches the most frequently requested files, namely, each CH should cache Vc files in order from high to low according to the request probability of each file. Consequently, each eNodeB eNBk selects files from the remaining file list Vc+1,Q to cache. Problem (17) can be further transformed into the following formation:
(18)minh2qk∑k=1Ktv2R∑q=Vc+1Qpqk∗h2qk+tv2R¯∑q=Vc+1QpqkDq′−h2qk+tv2s∑q=Vc+1Qpqk1−Dq′s.t.∑q=Vc+1Qh2qksq≤Vk,h2qk∈0,1,where Dq′=0,1 indicates that the file q is stored at least one edge node, i.e., CH or eNodeB. Particularly, the sum of the request probabilities for a file q under the coverage of eNodeB eNBk should satisfy
(19)∑k=1Kpkq=pq.We can convert problem (18) into
(20)minh2qktv2R∑q=Vc+1Qpqh2qk+tv2R¯∑q=Vc+1QpqDq′−h2qk+tv2s∑q=Vc+1Qpq1−Dq′s.t.∑q=Vc+1Qh2qk≤Vk,h2qk∈0,1,where the sum of request probabilities pq [12, 22] can be expressed as
(21)fx=∑q=Vc+1xpq≈∫Vc+1x1/qβ∑q=Vc+1Q1/qβdq=x1−β−Vc+1Q1−β−11−β.


### 4.6.6. Algorithm Design for Optimal Cache Deployment

To reduce the overhead of downloading files from remote servers or neighboring eNodeBs and simplify problem (20), each eNodeB can cache some identical files and a part of different files [35]. We assume that αVk of eNodeB capacity is used to cache the same files, and K1−αVk of eNodeB capacity will be used to cache different files for the total K eNodeBs; therefore, the total capacity of cached files on the eNodeB is Vk+K1−αVk,α∈0,1. The total hit ratio for all files is the sum of the hit ratio of caching the same file, and the mean hit ratio of caching different file. Consequently, the hit ratio to obtain files from eNodeBs can be expressed as
(22)HeNodeB=fαVk+K1−αVk+Vc−fαVk+VcK+fαVk+Vc.On the other hand, the hit ratio to obtain the requested files from neighbor eNodeBs through cooperation is(23)Hcoop=K−1KfαVk+K1−αVk+Vc−fαVk+Vc.After substituting (21), (22), and (23) into problem (20), the problem can be reduced to
(24)minαtv2RHeNodeB+tv2R¯Hcoop+tv2s1−HeNodeB−Hcoop=tv2s−tv2s−tv2RHeNodeB−tv2s−tv2R¯Hcoops.t.α∈0,1.Eventually, this problem can be transformed into the following equation:(25)maxαtv2s−tv2RHeNodeB+tv2s−tv2R¯Hcoops.t.α∈0,1.This problem can be solved by the first derivative for the following two equations:(26)dHeNodeBdα=K−1Vk1−βKQ1−β−1∗αVk+Vc1/β−αVk+K1−αVk+Vc1/β,dHcoopdα=K−1Vk1−βKQ1−β−1∗1−KαVk+K1−αVk+Vc1/β−αVk+Vc1/β.Combining the two equations in (26), we can obtain the solution (27) to the original problem (17). The procedure can be seen as Algorithm 2, and here, we assume that the merge sort algorithm is adopted at line 3, and the time complexity of Algorithm 2 is OK∗QlogQ, where K is the number of eNodeBs and Q is the total number of files.
(27)α∗≈tv2R¯−tv2R1/βKVk+Vc−Ktv2s−K−1tv2R¯−tv2R1/βVcKtv2s−K−1tv2R¯−tv2R1/βVk+tv2R¯−tv2R1/βK−1Vk.Algorithm 2: Optimal cache strategy.
Input: Cache capacity of vehicle and eNodeB, Vc, Vk, respectively.Output: Optimal cache Strategy for eNodeB and CH.fork=1toKdoCalculate the request probability,pqk, for each fileSort files in the descending order withpqk;CacheVc files on cluster headCalculate the optimal cache decision for eacheNBk according to (27);end


## 4.6.1. Cluster Size and Cluster Number

Assume that the arrival rate of vehicles follows a Poisson process, the distance between two vehicles follows an exponential distribution; the average number of vehicles in a cluster can be denoted as [29]
(9)Nc¯=ENc=1e−λRE1/V,where
(10)E1V=∫vminvmax1vfVvdv,where ⨆ is a floor function and R is the vehicle’s communication radius. Consequently, the average number of vehicles under the coverage of eNodeB is
(11)Nk=2Re×ρ¯=2Reρ¯,where ρ¯=λE1/V is the average density of vehicles [30], and Re is the transmission radius of eNodeB. Meanwhile, we can also obtain the average number of clusters under the coverage of the eNodeB, i.e., Nck=Nk/Nc¯.


## 4.6.2. Request and Response Procedure

In this paper, the response mode for file request has four types as shown in Figure3, where the purple solid line and the dashed line are the request and response action, respectively. First of all, a file request from a CM is forwarded to a CH in the cluster; if the requested file is cached by the CH, the CH will respond to the request by transmitting the file to the user directly (e.g., steps (1) → (2)); otherwise, the request will be forwarded to the nearby eNodeB. Besides, if the eNodeB has cached the file, the eNodeB will immediately broadcast the file to the user (e.g., steps (3)→ (4)); otherwise, the eNodeB will forward the request to its neighboring eNodeB. Furthermore, if the neighboring eNodeBs have cached the requested file, the neighboring eNodeB will respond to the request of the user through the original eNodeB (e.g., steps (3)→ (5)→ (6)→ (4)); otherwise, the request will be forwarded to a remote server. Eventually, the server will transmit the file to the eNodeB and then forward it to the user (e.g., steps (3)→ (7) → (8)→ (4)).Figure 3
Request and response procedure.


## 4.6.3. Delay of File Request

According to procedure4.6.2, we summarize the response delay as follows:
(i)
Response by the CH. The delay for a user to obtain a file from CH in a cluster is(12)tv2c=sqBvlog21+Pchc,j2/ξ2+∑n=1,n≠jN¯cPnhc,j2,where sq is the file size, the denominator represents the transmission rate between the vehicle Vj and the CH, hc,j is the channel coefficient from cluster head c to other vehicle Vj, Nc¯ is the total number of vehicles in the cluster, Pc is the transmit power of the CH, Bv is the channel bandwidth for the vehicle, ξ2 is the noise power, and Pn is the transmit power of other vehicles in the cluster, and the sum term in the denominator is total interferences from other vehicles to the current vehicle Vj in the cluster
(ii)
Response by eNodeB or Neighboring eNodeB. If the user cannot download the file from the CH in the cluster, the connected eNodeB or neighboring eNodeB will be scheduled to respond to the request. The response delay can be denoted, respectively, as follows:
(13)tv2R=sqBclog21+Prhr2/ξ2,tv2R¯=TNhop+tv2R,where tv2R is the delay from a eNodeB to a user and tv2R¯ is the delay from the user to the nearby eNodeB. The denominator denotes the transmission rate between the vehicle Vj and the corresponding eNodeB, Bc is the subchannel bandwidth allocated to the user Vj, hr is the channel coefficient from eNodeB to the user, Pr is the transmit power of the eNodeB, and ξ2 is the noise power. TNhop is the transmission delay from neighboring eNodeB to current eNodeB with Nhop hops; here, we assume the Nhop=1, and the transmission delay is usually milliseconds(iii)
Response by Remote Server. When the edge cache nodes (vehicle users) or neighbor eNodeB have not cached the file that the user requests, the user needs to download the file from a remote server. The latency of the response from a remote server is
(14)tv2s=sqRr2s+tv2R,where the first item is the delay from the remote server to the eNodeB and Rr2s is the transmission rate of the backhaul link. The second term is the delay from the eNodeB to the current user


## 4.6.4. Hit Ratio of All Users

After obtaining the file request delay for four modes, we design an efficient cache strategy to reduce the average total delay for all file requests and satisfy the cache capacity for each node. We useQ=1,2,3,⋯,Q to represent the file library, where Q is the total number of files. Each file has sq bits with a different request probability; besides, the files are stored on a remote server in order from high to low according to the request probability. We use Zipf distribution to model the request probability of a file [33]; as a result, the probability that a file q is requested is
(15)pq=q−β∑i=1Qi−β,where β≥0 is the bias parameter of Zipf, which indicates popularity. Generally, the larger the value is, the more concentrated the request will be. We assume that all vehicles will just request once (different requests from the same vehicle can be seen as different requests from different vehicles). Obviously, the probability that all files requested by different users satisfy ∑q=1Qpq=1.We adopt a two-level edge cache strategy based on CH and eNodeB [24, 34] to improve the hit ratio and reduce the response time for all requests. The CH and eNodeB are the first and second layer cache nodes, respectively, and they cache different files. Furthermore, all CHs under the coverage of the eNodeB eNBk cache the same files. Let Vc and Vk denote the cache capacity of a vehicle and an eNodeB, respectively. On the other hand, we use the matrix Hiq=hiqkK∗I∗Q to indicate whether the ii∈1,2 layer under the coverage of the eNodeB eNBk stores the file q, if affirmative hiqk is 1, otherwise 0. Additionally, the probability that files q is requested under the coverage of eNodeB eNBk is denoted as pqk.The hit ratio of user requests under eNodeBeNBk coverage is defined as follows:
(16)HeNBk=∑k=1K∑q=1Qpqk∑i=12hiqk+∑k=1K∑q=1QpqkDq−h2qk−h1qk+∑k=1K∑q=1Q1−Dqpqk,where Dq=0,1 indicates whether the file q is cached at least one edge node (eNodeB or CH), and if affirmative, Dq=1 (at least one edge node can satisfy the user’s request, that is, h2qk=1 or h1qk=1), otherwise 0 (h2qk=0 and h1qk=0).


## 4.6.5. Problem Formulation of Optimal Cache Deployment

Based on the hit ratio definition, we can formulate the problem as a response delay with a different cache strategy. According to the request procedure, the request delay is modeled as a function of the cache strategy. To reduce the overall delay for users to obtain the requested files and satisfy the constraints of cache size for each cache node, the problem can be formalized as follows:(17)minhiqk∑k=1Ktv2c∑q=1Qpqkh1qk+tv2R∑q=1Qpqkh2qk+tv2R¯∑q=1QpqkDq−∑i=12hiqk+tv2s∑q=1Q1−Dqpqks.t.∑i=12hiqk≤1,∑q=1Qh1qk≤Vc,∑q=1Qh2qk≤Vk,∑q=1Qhiqk∈0,1,∀i∈1,2.The cache strategy of the CH will directly affect the eNodeB cache strategy; thus, the cache strategy of the CH should be given a priority. In other words, each CH under the coverage of the eNodeBeNBk caches the most frequently requested files, namely, each CH should cache Vc files in order from high to low according to the request probability of each file. Consequently, each eNodeB eNBk selects files from the remaining file list Vc+1,Q to cache. Problem (17) can be further transformed into the following formation:
(18)minh2qk∑k=1Ktv2R∑q=Vc+1Qpqk∗h2qk+tv2R¯∑q=Vc+1QpqkDq′−h2qk+tv2s∑q=Vc+1Qpqk1−Dq′s.t.∑q=Vc+1Qh2qksq≤Vk,h2qk∈0,1,where Dq′=0,1 indicates that the file q is stored at least one edge node, i.e., CH or eNodeB. Particularly, the sum of the request probabilities for a file q under the coverage of eNodeB eNBk should satisfy
(19)∑k=1Kpkq=pq.We can convert problem (18) into
(20)minh2qktv2R∑q=Vc+1Qpqh2qk+tv2R¯∑q=Vc+1QpqDq′−h2qk+tv2s∑q=Vc+1Qpq1−Dq′s.t.∑q=Vc+1Qh2qk≤Vk,h2qk∈0,1,where the sum of request probabilities pq [12, 22] can be expressed as
(21)fx=∑q=Vc+1xpq≈∫Vc+1x1/qβ∑q=Vc+1Q1/qβdq=x1−β−Vc+1Q1−β−11−β.


## 4.6.6. Algorithm Design for Optimal Cache Deployment

To reduce the overhead of downloading files from remote servers or neighboring eNodeBs and simplify problem (20), each eNodeB can cache some identical files and a part of different files [35]. We assume that αVk of eNodeB capacity is used to cache the same files, and K1−αVk of eNodeB capacity will be used to cache different files for the total K eNodeBs; therefore, the total capacity of cached files on the eNodeB is Vk+K1−αVk,α∈0,1. The total hit ratio for all files is the sum of the hit ratio of caching the same file, and the mean hit ratio of caching different file. Consequently, the hit ratio to obtain files from eNodeBs can be expressed as
(22)HeNodeB=fαVk+K1−αVk+Vc−fαVk+VcK+fαVk+Vc.On the other hand, the hit ratio to obtain the requested files from neighbor eNodeBs through cooperation is(23)Hcoop=K−1KfαVk+K1−αVk+Vc−fαVk+Vc.After substituting (21), (22), and (23) into problem (20), the problem can be reduced to
(24)minαtv2RHeNodeB+tv2R¯Hcoop+tv2s1−HeNodeB−Hcoop=tv2s−tv2s−tv2RHeNodeB−tv2s−tv2R¯Hcoops.t.α∈0,1.Eventually, this problem can be transformed into the following equation:(25)maxαtv2s−tv2RHeNodeB+tv2s−tv2R¯Hcoops.t.α∈0,1.This problem can be solved by the first derivative for the following two equations:(26)dHeNodeBdα=K−1Vk1−βKQ1−β−1∗αVk+Vc1/β−αVk+K1−αVk+Vc1/β,dHcoopdα=K−1Vk1−βKQ1−β−1∗1−KαVk+K1−αVk+Vc1/β−αVk+Vc1/β.Combining the two equations in (26), we can obtain the solution (27) to the original problem (17). The procedure can be seen as Algorithm 2, and here, we assume that the merge sort algorithm is adopted at line 3, and the time complexity of Algorithm 2 is OK∗QlogQ, where K is the number of eNodeBs and Q is the total number of files.
(27)α∗≈tv2R¯−tv2R1/βKVk+Vc−Ktv2s−K−1tv2R¯−tv2R1/βVcKtv2s−K−1tv2R¯−tv2R1/βVk+tv2R¯−tv2R1/βK−1Vk.Algorithm 2: Optimal cache strategy.
Input: Cache capacity of vehicle and eNodeB, Vc, Vk, respectively.Output: Optimal cache Strategy for eNodeB and CH.fork=1toKdoCalculate the request probability,pqk, for each fileSort files in the descending order withpqk;CacheVc files on cluster headCalculate the optimal cache decision for eacheNBk according to (27);end


## 5. Coded Delivery Strategy

When the cache node (for example, CH, eNodeB, or remote server) receives the user’s request, it will transmit the requested file to the users according to the response model. However, it usually costs too many bandwidths and leads to a large delay for message transmitting due to the MAC layer collision, in particular, when many vehicle users exchange multimedia messages on a crowded road in a city scenario, which may lead to higher risk. Usually, when the cache node receives many requests within a certain period, it can respond to asynchronous requests through broadcasting to reduce the response time during a period. To further reduce the consumption of bandwidth resources by cache nodes, we propose an effective coded delivery scheme based on file coding and subfile coding [14, 16], which can minimize network load and reduce the ratio of redundant files or subfiles.


### 5.1. Subfile Coding

In this section, eNodeB is taken as an example to illustrate the data transmission strategy. According to (11), there are total Nk users under the coverage of eNodeB eNBk. We assume that the nth user requests the file wnwn∈Q, and all requests are denoted as a set w1,w2,⋯,wNrk during a time, where Nrk is the real number of users that initiate a request. Obviously, the conditions n∈Nrk and Nrk≤Nk are satisfied.The cache file in eNodeBeNBk may be allocated among Nrk users, and the file wn can be composed of different subfiles wn,S, that is, a subfile consisting of a set of bits and these bits are stored only in a specific user group S, where S⊂Nrk, and Nrk represents a set of Nrk users [14]. When multiple users initiate requests at the same time, the eNodeB firstly reduces the duplicate files by using XOR coding. The set of files requested by all users under the coverage of eNodB eNBk after XOR coding is
(28)W=w,w∈⊕n∈Nrkwn.For the filewn requested by user n, eNodeB eNBk only need to transmit all subfiles to users as follows:
(29)fn=wn,S,S⊆W\n.Therefore, the set of subfiles thateNBk needs to broadcast is
(30)F=∪n∈Wfn.To reduce the number of the subfiles to be transmitted, we can select a part of the subfilesF′∈F and transform all the selected subfiles into a feasible data packet. As a consequence, the feasible data packet can be denoted as
(31)pi=⊕wj,S∈F′wj,S,F′⊆F.Accordingly, we usePk=p1,p2,⋯ to denote the set of feasible data packets.


### 5.2. Problem Formulation of Coded Delivery

The construction of a feasible data packet, however, may ignore the fact that the same subfiles may appear repeatedly in different data packets, resulting in repeated data transmission and a waste of bandwidth. To avoid the above problems, a data packet with fewer redundant subfiles should be selected as much as possible when a feasible data packet is generated. For any feasible data packetpi∈Pk, we firstly count the number of repetitions for each subfile. If a subfile wj,S appears rwj,S times in set Pk and rwj,S>1, the subfile is considered as a redundant subfile. In this way, the redundant times of subfile wj,S is recorded as rwj,S−1, otherwise 0. The redundancy times for all subfiles in each feasible data packet should be added up. The redundant ratio of the packet is calculated as follows:
(32)Rpi=∑wj,S∈pirwj,S−1∑pi∈Pk∣pi∣,where ∣pi∣ denotes the number of total subfiles in packet pi.The size of the feasible packet is defined as [14]
(33)Bpi=maxwj,S∈piBwj,S,where pi represents a feasible data packet, and wj,s is a subfile contained in the feasible data packet.We can usexi to indicate whether the feasible data packet pi is selected for transmission. If pi is selected, xi=1, otherwise 0. The vector X=xi∣pi∈Pk represents a set of decision variables xi. Thus, the problem is denoted as
(34a)min∑pi∈PxiBpi,(34b)min∑pi∈PxiRpi,(34c)s.t.⋃pi∈P,xi=1pi=F,where (34a) and (34b) denote the size of the data to be transmitted and the redundancy ratio of the total transmitted subfiles by using the transmission decision variable vector X, respectively. (34c) indicates that the selected subfiles need to satisfy the user’s request. According to [14], condition (34c) can be converted to a linear condition. To ensure each receiver can successfully decode the files that they received, it needs to satisfy AX≥1,X∈0,1∣Pk∣, where 1 is ∣F∣×1 column vector. The feasible region of the problem can be defined as
(35)X=xi∈RPk,∑aij∈Aaijxi≥1,xi∈0,1,where A∣F∣∗∣Pk∣ is a 0−1 matrix, each row denotes a subfile to be sent, and each column denotes a feasible data packet. If the subfiles can be decoded from the data packet, the corresponding element in the matrix is 1, otherwise 0.The problem formulation (34) is a multiple objective set covering problem (MOSCP), which is also an NP-hard problem and difficult to solve. Usually, the MOSCP is converted into a single objective problem [36, 37] to simplify the problem. We propose to use the weighted-max-ordering method [38] to convert problem (34) into the following form:
(36)minmaxλqzqxs.t.x∈X,where λ1,λ2 represents the weight coefficients of the first and second objective functions of equations (34a) and (34b), respectively, λ1+λ2=1, and zqx is the qth objective function in (34), q∈1,2.


### 5.3. Algorithm Design

To reduce the network load and computing complexity, Asghari et al. [14, 15] proposed an efficient method to avoid obtaining the set of feasible data packets, namely, data packets with smaller bits and more subfiles are selected from the subfile set as much as possible. However, for a multiobjective optimization problem, this method cannot be used directly. To solve the multiobjective problem, many authors have proposed to use the cost/coverage ratio as the metric to select items when they face a multiobjective cover problem. The metric is usually defined as metric cjqλq/∣Sj∣ to select data from the original set, where ∣Sj∣ is the number of items in the selected subset, cjq is the coefficient of the qth objective function, and λq is the weight factor of the qthq=1,2 objective function [36–39]. The main idea of the algorithm is to find the subset (packet) that can cover as more as possible items (subfiles) from the original set E and select the subset with λqcjq as small as possible. Similarly, the cost/coverage ratio can be used as a measure of our problem. Whenever a data packet is generated, a packet with a relatively small cost/coverage ratio should be selected as much as possible. We define the cost/coverage ratio vector αi of the packet pi as
(37)αi=α1i,α2iT=λ1Bpi∣pi∩F∣,λ2Rpi∣pi∩F∣T,where Bpi and Rpi are the size and ratio of redundant files for packet pi in the objective function, pi is the set of subfiles in the data packet pi, and pi∩F and ∣pi∩F∣ are the set of subfiles and the number of elements in the set pi∩F, respectively. The lower the packet cost/cover ratio, the more likely that a packet is to be selected. For two packets pi, pj, if the following conditions are satisfied:
(38)maxαi=α1i,α2iT≤maxαj=α1j,α2jT,the packet pi will be chosen as a feasible packet.


### 5.4. Algorithm Description and Analysis

Based on the above analysis, we propose an efficient heuristic algorithm to solve problem (34) as shown in Algorithm3. The lines 1-2 in Algorithm 3 denote the packets that the eNodeB needs to transmit and the remaining set of subfiles in subfile set F, respectively. As observed from lines 3-11, it firstly uses the function Genpacket ε to generate the appropriate packets. From line 5 to line 10, it will judge whether each subfile of the potential packet exists in the remaining subfile set. If affirmative, the subfile will be added to the data packet and deleted from the remaining subfile set ε. This procedure will continue until the remaining subfile set is empty. In the function Genpacket ε, we can obtain an appropriate packet to transmit from line 2 to line 11. The second line illustrates the number of requests from all users under the coverage of eNBk, and then, we can build a set of a feasible packet with the smallest possible subfile size from line 2 to line 11. From line 12 to line 19, we will select the packet with the lowest cost/coverage ratio from the set of feasible data packets according to the definition of cost/coverage ratio. Furthermore, the eNodeB eNBk can calculate the set of packets Pk′ to be transmitted based on the subfile set F. Finally, all these calculated data packets will be sent to users from eNBk, and the user that has made a request can decode the files they need based on the received files and the cached file by themselves. As Algorithm 3 will be terminated until ε=∅, we can see that Algorithm 3 needs O∣F∣Nrk2Nrk operation, where F is the number of subfiles in the subfile set, and Nrk is the number of users that really initiate a request under the coverage of eNBk.Algorithm 3: Packets sent by eNBk.
Input: Subfile set F.Output: Packets sent by eNodeB eNBk.Setψ=∅;Setε=F;whileε≠∅doCalculate the packetpi=Genpacketε;for each subfile wj,S∈pidoifwj,S∈pi∩εthenψ=ψ∪wj,S;ε=ε\wj,S;endendendAlgorithm 4
Function Genpacket εp=∅;LetM=i∣i∈N,∃wi,S∈ε,S⊆N\i;forT⊆M && ∣T∣≠0doforj∈TdoLj,T=wj,S∣wj,S∈ε,T\j⊆S;CalculateVj,T=argminw∈Lj,TBw;PT=PT∪Vj,T;endP=P∪PT;endαj∗=αj∗1,αj∗2T=+∞,+∞T;forpj∈Pdoαj=αj1,αj2T=λ1Bpj/∣pj∩ε∣,λ2Rpj/∣pj∩ε∣T;ifmaxαj1,αj2T≤maxαj∗1,αj∗2Tthenαj∗=αj;p=pj;endendreturnp;


## 5.1. Subfile Coding

In this section, eNodeB is taken as an example to illustrate the data transmission strategy. According to (11), there are total Nk users under the coverage of eNodeB eNBk. We assume that the nth user requests the file wnwn∈Q, and all requests are denoted as a set w1,w2,⋯,wNrk during a time, where Nrk is the real number of users that initiate a request. Obviously, the conditions n∈Nrk and Nrk≤Nk are satisfied.The cache file in eNodeBeNBk may be allocated among Nrk users, and the file wn can be composed of different subfiles wn,S, that is, a subfile consisting of a set of bits and these bits are stored only in a specific user group S, where S⊂Nrk, and Nrk represents a set of Nrk users [14]. When multiple users initiate requests at the same time, the eNodeB firstly reduces the duplicate files by using XOR coding. The set of files requested by all users under the coverage of eNodB eNBk after XOR coding is
(28)W=w,w∈⊕n∈Nrkwn.For the filewn requested by user n, eNodeB eNBk only need to transmit all subfiles to users as follows:
(29)fn=wn,S,S⊆W\n.Therefore, the set of subfiles thateNBk needs to broadcast is
(30)F=∪n∈Wfn.To reduce the number of the subfiles to be transmitted, we can select a part of the subfilesF′∈F and transform all the selected subfiles into a feasible data packet. As a consequence, the feasible data packet can be denoted as
(31)pi=⊕wj,S∈F′wj,S,F′⊆F.Accordingly, we usePk=p1,p2,⋯ to denote the set of feasible data packets.


## 5.2. Problem Formulation of Coded Delivery

The construction of a feasible data packet, however, may ignore the fact that the same subfiles may appear repeatedly in different data packets, resulting in repeated data transmission and a waste of bandwidth. To avoid the above problems, a data packet with fewer redundant subfiles should be selected as much as possible when a feasible data packet is generated. For any feasible data packetpi∈Pk, we firstly count the number of repetitions for each subfile. If a subfile wj,S appears rwj,S times in set Pk and rwj,S>1, the subfile is considered as a redundant subfile. In this way, the redundant times of subfile wj,S is recorded as rwj,S−1, otherwise 0. The redundancy times for all subfiles in each feasible data packet should be added up. The redundant ratio of the packet is calculated as follows:
(32)Rpi=∑wj,S∈pirwj,S−1∑pi∈Pk∣pi∣,where ∣pi∣ denotes the number of total subfiles in packet pi.The size of the feasible packet is defined as [14]
(33)Bpi=maxwj,S∈piBwj,S,where pi represents a feasible data packet, and wj,s is a subfile contained in the feasible data packet.We can usexi to indicate whether the feasible data packet pi is selected for transmission. If pi is selected, xi=1, otherwise 0. The vector X=xi∣pi∈Pk represents a set of decision variables xi. Thus, the problem is denoted as
(34a)min∑pi∈PxiBpi,(34b)min∑pi∈PxiRpi,(34c)s.t.⋃pi∈P,xi=1pi=F,where (34a) and (34b) denote the size of the data to be transmitted and the redundancy ratio of the total transmitted subfiles by using the transmission decision variable vector X, respectively. (34c) indicates that the selected subfiles need to satisfy the user’s request. According to [14], condition (34c) can be converted to a linear condition. To ensure each receiver can successfully decode the files that they received, it needs to satisfy AX≥1,X∈0,1∣Pk∣, where 1 is ∣F∣×1 column vector. The feasible region of the problem can be defined as
(35)X=xi∈RPk,∑aij∈Aaijxi≥1,xi∈0,1,where A∣F∣∗∣Pk∣ is a 0−1 matrix, each row denotes a subfile to be sent, and each column denotes a feasible data packet. If the subfiles can be decoded from the data packet, the corresponding element in the matrix is 1, otherwise 0.The problem formulation (34) is a multiple objective set covering problem (MOSCP), which is also an NP-hard problem and difficult to solve. Usually, the MOSCP is converted into a single objective problem [36, 37] to simplify the problem. We propose to use the weighted-max-ordering method [38] to convert problem (34) into the following form:
(36)minmaxλqzqxs.t.x∈X,where λ1,λ2 represents the weight coefficients of the first and second objective functions of equations (34a) and (34b), respectively, λ1+λ2=1, and zqx is the qth objective function in (34), q∈1,2.


## 5.3. Algorithm Design

To reduce the network load and computing complexity, Asghari et al. [14, 15] proposed an efficient method to avoid obtaining the set of feasible data packets, namely, data packets with smaller bits and more subfiles are selected from the subfile set as much as possible. However, for a multiobjective optimization problem, this method cannot be used directly. To solve the multiobjective problem, many authors have proposed to use the cost/coverage ratio as the metric to select items when they face a multiobjective cover problem. The metric is usually defined as metric cjqλq/∣Sj∣ to select data from the original set, where ∣Sj∣ is the number of items in the selected subset, cjq is the coefficient of the qth objective function, and λq is the weight factor of the qthq=1,2 objective function [36–39]. The main idea of the algorithm is to find the subset (packet) that can cover as more as possible items (subfiles) from the original set E and select the subset with λqcjq as small as possible. Similarly, the cost/coverage ratio can be used as a measure of our problem. Whenever a data packet is generated, a packet with a relatively small cost/coverage ratio should be selected as much as possible. We define the cost/coverage ratio vector αi of the packet pi as
(37)αi=α1i,α2iT=λ1Bpi∣pi∩F∣,λ2Rpi∣pi∩F∣T,where Bpi and Rpi are the size and ratio of redundant files for packet pi in the objective function, pi is the set of subfiles in the data packet pi, and pi∩F and ∣pi∩F∣ are the set of subfiles and the number of elements in the set pi∩F, respectively. The lower the packet cost/cover ratio, the more likely that a packet is to be selected. For two packets pi, pj, if the following conditions are satisfied:
(38)maxαi=α1i,α2iT≤maxαj=α1j,α2jT,the packet pi will be chosen as a feasible packet.


## 5.4. Algorithm Description and Analysis

Based on the above analysis, we propose an efficient heuristic algorithm to solve problem (34) as shown in Algorithm3. The lines 1-2 in Algorithm 3 denote the packets that the eNodeB needs to transmit and the remaining set of subfiles in subfile set F, respectively. As observed from lines 3-11, it firstly uses the function Genpacket ε to generate the appropriate packets. From line 5 to line 10, it will judge whether each subfile of the potential packet exists in the remaining subfile set. If affirmative, the subfile will be added to the data packet and deleted from the remaining subfile set ε. This procedure will continue until the remaining subfile set is empty. In the function Genpacket ε, we can obtain an appropriate packet to transmit from line 2 to line 11. The second line illustrates the number of requests from all users under the coverage of eNBk, and then, we can build a set of a feasible packet with the smallest possible subfile size from line 2 to line 11. From line 12 to line 19, we will select the packet with the lowest cost/coverage ratio from the set of feasible data packets according to the definition of cost/coverage ratio. Furthermore, the eNodeB eNBk can calculate the set of packets Pk′ to be transmitted based on the subfile set F. Finally, all these calculated data packets will be sent to users from eNBk, and the user that has made a request can decode the files they need based on the received files and the cached file by themselves. As Algorithm 3 will be terminated until ε=∅, we can see that Algorithm 3 needs O∣F∣Nrk2Nrk operation, where F is the number of subfiles in the subfile set, and Nrk is the number of users that really initiate a request under the coverage of eNBk.Algorithm 3: Packets sent by eNBk.
Input: Subfile set F.Output: Packets sent by eNodeB eNBk.Setψ=∅;Setε=F;whileε≠∅doCalculate the packetpi=Genpacketε;for each subfile wj,S∈pidoifwj,S∈pi∩εthenψ=ψ∪wj,S;ε=ε\wj,S;endendendAlgorithm 4
Function Genpacket εp=∅;LetM=i∣i∈N,∃wi,S∈ε,S⊆N\i;forT⊆M && ∣T∣≠0doforj∈TdoLj,T=wj,S∣wj,S∈ε,T\j⊆S;CalculateVj,T=argminw∈Lj,TBw;PT=PT∪Vj,T;endP=P∪PT;endαj∗=αj∗1,αj∗2T=+∞,+∞T;forpj∈Pdoαj=αj1,αj2T=λ1Bpj/∣pj∩ε∣,λ2Rpj/∣pj∩ε∣T;ifmaxαj1,αj2T≤maxαj∗1,αj∗2Tthenαj∗=αj;p=pj;endendreturnp;


## 6. Cluster-Based Two-Level Cooperative Cache Deployment and Coded Delivery Strategy

In this section, we summarize the cache deployment and coded delivery as Algorithm5. The first line shows the vehicle cluster procedure, and the second line is to cache the files on the edge node (CH or eNodeB). From line 3 to line 9, it illustrates the transmission strategy for the cache nodes. If the cache node CNi received several requests during Tr and has cached the requested files, it will first calculate the subfile set F according to the users’ requests and then calculate a set of packets Pi′ that needs to be transmitted by cache node CNi. As there are Nk vehicle users under the coverage of eNBk, Algorithm 1 needs OKNk operations, and Algorithm 2 needs to operate OKQlogQ times. Furthermore, as there are Nck clusters under the coverage of each eNodeB; thus, there are total KNck cluster heads, it needs to operate OKNck∣F∣Nrk2Nrk times, and the K eNodeBs need to operate OK∣F′∣Nrkc2Nrkc times from step 3 to step 9 in Algorithm 5 according to Algorithm 3, where Nrkc is the total number of users that initiate a request in a cluster under the coverage of eNBk, and ∣F′∣ is the number of subfiles in a cluster. Therefore, the total time complexity of Algorithm 5 is OKNk+QlogQ+Nck∣F∣Nrk2Nrk+F′Nrkc2Nrkc.Algorithm 5: Cluster-based two-level cooperative cache deployment and coded delivery strategy.
Input: Velocity vi, position xi,yi, number of files Q, file size sq, cache capacity of vehicle Vc, cache capacity of eNodeB Vk, file q request probability pqk under eNodeB k, bias parameter of Zipf β, transmission power Pc,Pn,Pr, bandwidth Bv and Bc, and cluster size Nk.Output: Cluster, cache decision, transmitted packet.// Cache DeploymentDivide all vehicles into clusters and calculate the CH and CM according to Algorithm1;Cache the frequently requested file at all CHs and eNodeBs according to Algorithm2;// Coded Deliversfor any cache node CNi received several requests within Trdoif node CNi has cached the requested file thenSetN users’ requests as w1,w2,⋯,wN;Calculate the subfile setF according to (30);Calculate the packetPi′ transmitted by CNi according to Algorithm 3;endend


## 7. Performance Evaluation

### 7.1. Parameter Setting

We simulate our algorithms by using NS-3 simulation software to compare other methods. The arrival process of vehicles follows a Poisson distribution, and the average velocityμ of vehicles is 40, 60, 80, 100, and 120 km/h, respectively, and the corresponding standard deviation δ is 10, 16, 22, 28, and 34. The minimum speed and maximum speed are μ−3δ and μ+3δ according to [33], respectively. Vehicle arrival rates are 600, 700, 800, 900, and 1000 vehicles/h, and the total number of files is 160, i.e., Q=160. The cache capacity of eNodeB is set to 8, 16, 24, 32, and 40, and the cache capacity of eNodeB is set to 4, 8, 12, 16, and 20, respectively. The size of each file is set to 1, 2, 3, 4, and 5 MB. The vehicle communication radius is 200 m while the eNodeB transmission radius is 500 m. Furthermore, the road networks are generated by the SUMO software, we choose one road with length 2 km to conduct the simulation, and the parameter of the Zipf distribution is 0.5. The path loss among vehicles is 128+36.7log10d db, where d is the distance between the vehicle and CH or eNodeB, d in km, and the power of noise power density is -174 dBm/Hz. Bandwidth Bv=Bc is 10 MHz, and the transmitting power is set as 6 dBm. The detailed simulation parameters can be seen in Table 1.Table 1
Simulation parameters.
ParameterValueNumber of fileQ160Cache capacity of eNodeBVk (#)8, 16, 24, 32, 40Cache capacity of vehicleVc (#)4, 8, 12, 16, 20Transmission range of vehicleR200 mTransmission range of eNodeBRe500 mRoad lengthL2 kmCluster merging thresholdLc100 mNCMmax10Zipf parameterβ0.5sq1, 2, 3, 4, 5 MBCH metric coefficientαi,βi,γi0.32, 0.32, 0.36Coded delivery time thresholdTr1.0 sCH¯TIMER,JOIN¯TIMER2.0 sLink life time thresholdω2.0 sMultiobjective function coefficientλ1,λ20.01, 0.99BandwidthBv=Bc10 MHzTransmission powerPr=Pc=Pn6 dBmNoise power density-174 dBm/HzBackhaul link data rateRr2s40 MbpsWe compare and validate our proposed method with some state-of-the-art schemes in terms of the following performance metrics:(1)
Cache Hit Ratio. The ratio of the files satisfied by all cache nodes to all requests to the cache nodes(2)
Average Response Delay. The average time interval from the user sending the request to receive data (short for)(3)
Network Load. The network load that is downloaded from edge cache nodes and a remote server(4)
Ratio of Redundant Files. The ratio of the received packets that contain redundant subfiles to the total received subfiles in all packets, we use redundant ratio in figures to represent the ratio of redundant files to simplify the expressionOn the one hand, we compare our coded delivery method with COMP [23], “RSU-based cache only” [40], and “FSA-based cache” [41] in terms of a cache hit ratio, average response delay, and average network load. On the other hand, we compare our proposed method with “Optimal coded cache” [14] and “No coded-based method”, which includes COMP, “RSU-based cache only”, and “FSA-based cache” in terms of the ratio of the redundant files. Last but not the least, we will analyze the impact of cache size, size per file, velocity, and arrival rate on the four metrics.


### 7.2. Effect of Cache Size

As can be seen from Figure4, we compare our proposed method with COMP, “FSA-based cache”, and “RSU-based cache only”. In addition, we set the cache size of eNodeB Vk {8, 16, 24, 32, 40} and Vc {4, 8, 12, 16, 20}, respectively. The average velocity is 40 km/h, and the arrival rate of vehicles is set to 600 vehicles/h; the size per file is set as 1 MB. The number of the x axis on y axis represent the total cache size, i.e., Vk+Vc, and the performance metrics, respectively.Figure 4
Effect of cache sizeVk and Vc on system performance.
(a)
Network load vs. cache size(b)
Redundant ratio vs. cache size(c)
Hit ratio vs. cache size(d)
Average response delay vs. cache sizeFigure4(a) illustrates that the network load of the other three methods keeps constant and higher than our proposed method despite different cache sizes. Because our proposed coded delivery method does not only reduce redundant files requested by users but also eliminates the redundancy among subfiles, however, the total requests of the other three methods do not change due to the constant vehicle number given the fixed velocity and arrival rate.Furthermore, in Figure4(b), we can find that the ratio of redundant files of all methods will almost decrease slightly with the increase of cache size on the edge nodes because the probability of different users request the same file will decrease with the increase of cache size.From Figure4(c), it is easily observed that our proposed method outperforms the other three methods in terms of hit ratio. It can be explained that our proposed method considers a two-level edge cache; for instance, cluster head and eNodeB can cache the most requested files according to the request probability. COMP also adopts cluster heads to cache the most popular files and part of less popular files cooperatively, but there is no cooperation among RSUs; thus, the hit ratio is lower than ours. The “FSA-based cache” method and “RSU-based cache only” are worse than our proposed method and COMP due to the lack of edge cache. On the other hand, the hit ratio “FSA-based cache” is higher than that of “RSU-based cache only” because RSU also considers the cooperation cache among RSUs though it ignores the cooperation among cluster heads in “FSA-based cache.”In Figure4(d), the average response delay of the four methods is compared. On the one hand, the average response delay of all methods will decrease with the increase of cache size, because more requests will be satisfied by the cache node if the cache size is large enough. On the other hand, it can be observed that our proposed method can obtain the least average response delay because we cache the popular file on the edge node as much as possible, where the response delay is smaller compared to the response delay from the remote server. The average response delay of COMP decreases quickly because more requests will be satisfied by cluster heads and eNodeB when the cache size increase although the request is mainly satisfied by a remote server at the beginning. As for “FSA-based cache” and “RSU-based cache only”, the average response delay is much larger than our proposed method, because they do not consider caching files on cluster head cache, all the requests will be satisfied from eNodeB or remote server. Furthermore, the average response delay of the “FSA-based cache” outperforms that of “RSU-based cache only”, because “FSA-based cache” has also considered the cooperation among eNodbBs. From the above figures, we can easily find that cache size has a great impact on the hit ratio and response delay, and the impact of cache size on the network load and redundant ratio is not so obvious.


### 7.3. Effect of Size per File

In this subsection, the capacity of eNodeB and CH isVk=40 and Vc=20, respectively. The average velocity is 40 km/h, and the arrival rate of vehicles is set to 600 vehicles/h, and Q=160. The size per file changes from 1 MB to 5 MB.From Figure5(a), we can find that our proposed method can achieve better performance in terms of network load compared with COMP, “FSA-based cache”, and “RSU-based cache only.” The network load of COMP, “FSA-based cache”, and “RSU-based cache only” almost increase with the size per file linearly, because the total number of requests is almost the same given the mean velocity and arrival rate, and the network load will increase with the increase of the size of per file. Our proposed method adopts the coded delivery method to reduce the data traffic so that it can outperform the other three methods.Figure 5
Effect of size per file on system performance.
(a)
Network load vs. size per file(b)
Redundant ratio vs. size per file(c)
Hit ratio vs. size per file(d)
Average response delay vs. size per fileFrom Figure5(b), it can be observed that the ratio of redundant files of our proposed method outperforms the “Optimal coded cache” and “No coded-based method” methods, as it not only considers reducing the ratio of redundant files between files and also reduces the ratio of redundant files between subfiles. “No coded-based method” is the worst in terms of the ratio of redundant files because they do nothing to reduce the redundancy among files.As can be seen from Figure5(c), the hit ratio of four methods almost keeps the same under different sizes per file, as the hit ratio has nothing to do with size per file. Furthermore, the hit ratio of our proposed method is larger than the other three methods as our proposed method adopts the two-level caching strategy. COMP is also better than the other two methods as it takes advantage of the RSU cache cooperatively.From Figure5(d), it can be observed that the average response delay of the “RSU-based cache only” is larger than any other methods despite different sizes per file. Furthermore, the performance of “FSA-based cache” is better than that of “RSU-based cache only” since it considers the cooperation among RSUs. COMP and our proposed method can almost achieve the same performance and better than “FSA-based cache” and “RSU-based cache only”, as they obtain the request files mainly from edge cache node; thus, the average delay is smaller than that of “FSA-based cache” and “RSU-based cache only.” From the above discussion, we can find that the average response delay linearly grows with the size per file for all methods, since we assume that the response delay for each unit file is fixed. It can also be found that size per file has a large influence on the average response delay and network load, but little impact on the redundant ratio and hit ratio.


### 7.4. Effect of Velocity of Vehicle

In this subsection, we compare our proposed method with other methods and analyze the impact of the mean velocity of vehicles on the performances. We set the size per file as 1 MB,Vk=8, and Vc=4. The arrival rate of vehicles is set to 600 vehicles/h, and the average velocity changes from 40 km/h to 120 km/h.As can be seen from Figure6(a) that the network load for all methods decreases with the mean velocity because the larger the mean velocity is, the smaller the cluster size and the total number of vehicles on the road is, however, the number of clusters will increase. Thus, the request and response data traffic from all vehicles will decrease with the increase of mean velocity. Though the reduction is not significant for our proposed method, our proposed method outperforms the other three methods in terms of network load due to the coded delivery method.Figure 6
Effect of velocity of vehicles on system performance.
(a)
Network load vs. mean velocity(b)
Redundant ratio vs. mean velocity(c)
Hit ratio vs. mean velocity(d)
Average response delay vs. mean velocityFrom Figure6(b), we can find that the ratio of redundant files of “No coded-based method” cache and “Optimal coded cache” increases slightly with the increase of velocity, and our proposed method increases rapidly but has better redundant performance than the other two methods. The reason is that when the average velocity increases, there are more clusters and smaller cluster sizes under the coverage of eNodeB, which means that there are more CH that can cache popular files. Each CH under the coverage of eNodeB will cache the same files, and our proposed method is more dependent on the edge cache, which causes a sharp increase in the ratio of redundant files in our proposed method when the arrival rate is high.From Figure6(c), it can be easily found that our proposed method can achieve the highest hit ratio; the second one is COMP. With the increase of velocity, there will be more clusters and each CH can cache some files, and our proposed method and COMP can take advantage of the edge cache; thus, their hit ratio will grow significantly with the increase of velocity. However, “FSA-based cache” and “RSU-based cache only” mainly depend on the cache of eNodeB; thus, their hit ratio almost keeps constant.In Figure6(d), we compare our proposed method with the other three methods in terms of the average response delay. When the mean velocity increases, there will be more clusters and smaller size of the cluster; thus, many files can be cached on the CHs, which will reduce the response time greatly and improve the hit ratio for our proposed method and COMP; of cause, our proposed method still obtain the lowest response delay. Furthermore, we can find the average response delay of “FSA-based cache” and “RSU-based cache only” slowly decreases as the total number of vehicles and requests will decrease with the increase of mean velocity. From the simulation, it can be found that the mean velocity has a great impact on all performance metrics.


### 7.5. Effect of Arrival Rate

In this subsection, we will compare our proposed method with the other three methods and analyze the impact of the arrival rate of vehicles on the performances. In this subsection, we set the size per file 1 MB,Vk=24, and Vc=12. The average velocity is 40 km/h, the file number is set as Q=160, and the arrival rate of vehicles changes from 600 vehicles/h to 1000 vehicles/h.From Figure7(a), it is observed that the network load for the other three methods increases when the arrival rate of vehicles also increase, which can be explained by the fact that the larger the arrival rate of vehicles will lead to more vehicles on the road given the mean velocity; consequently, the request and the total traffic will also increase. However, the arrival rate of vehicles almost does not put any impact on our proposed method in terms of network load, that is because we adopt the coded delivery method.Figure 7
Effect of arrival rate of vehicles on system performance.
(a)
Network load vs. arrival rate(b)
Redundant ratio vs. arrival rate(c)
Hit ratio vs. arrival rate(d)
Average response delay vs. arrival rateFrom Figure7(b), we can find that the ratio of redundant files in our proposed method is the lowest among all methods. Though the “Optimal coded cache” and our proposed method have adopted coded delivery method to reduce the ratio of redundant files. What is more, our proposed method also focuses on reducing the ratio of redundant files among subfiles; thus, our proposed method can outperform “Optimal coded cache.” “No coded-based method” is still the worst method in terms of the ratio of redundant files as it does nothing to reduce the redundant files.In Figure7(c), we compare the hit ratio with the other three methods and analyze the impact of the arrival rate on the hit ratio. First of all, we find that the hit ratio of all four methods will decrease with the increase in the arrival rate. The reason is that when the arrival rate increase when the mean velocity is given, the total number of vehicles and the cluster size on the road will also increase; however, the number of the cluster under the coverage of each eNodeB will decrease, which will lead to the decrease of the contents on the edge nodes; therefore, the hit ratio will decrease, especially for our proposed method and COMP. The hit ratio of “FSA-based cache” and “RSU-based cache only” almost keep the constant, because their hit ratio mainly depends on the cached files on eNodeB (RSU); furthermore, we can also find that our proposed method still can obtain the highest hit ratio.From Figure7(d), it can be easily found that the average response delay will grow with the increase of arrival rate, and this can also be explained that a larger arrival rate will lead to larger cluster size and less number of cluster, which leads to a decrease in the hit ratio, and more requests will be responded by a remote server. Our proposed method outperforms other methods because it can make the most of the edge cache advantage and cooperatively cache on neighboring eNodeBs, and it will obtain the most files from the edge nodes. CH cache is also considered in COMP; thus, its average response delay is better than that of “FSA-based cache” and “RSU-based cache only.” When the arrival rate increase, more vehicles will compete to request the files from the limited space of eNodeB, and the average response delay for “FSA-based cache” and “RSU-based cache only” will almost linearly grow with the increasing of arrival rate. In summary, we can find that the arrival rate of vehicles has a great impact on the network load, hit ratio, and average response delay.


## 7.1. Parameter Setting

We simulate our algorithms by using NS-3 simulation software to compare other methods. The arrival process of vehicles follows a Poisson distribution, and the average velocityμ of vehicles is 40, 60, 80, 100, and 120 km/h, respectively, and the corresponding standard deviation δ is 10, 16, 22, 28, and 34. The minimum speed and maximum speed are μ−3δ and μ+3δ according to [33], respectively. Vehicle arrival rates are 600, 700, 800, 900, and 1000 vehicles/h, and the total number of files is 160, i.e., Q=160. The cache capacity of eNodeB is set to 8, 16, 24, 32, and 40, and the cache capacity of eNodeB is set to 4, 8, 12, 16, and 20, respectively. The size of each file is set to 1, 2, 3, 4, and 5 MB. The vehicle communication radius is 200 m while the eNodeB transmission radius is 500 m. Furthermore, the road networks are generated by the SUMO software, we choose one road with length 2 km to conduct the simulation, and the parameter of the Zipf distribution is 0.5. The path loss among vehicles is 128+36.7log10d db, where d is the distance between the vehicle and CH or eNodeB, d in km, and the power of noise power density is -174 dBm/Hz. Bandwidth Bv=Bc is 10 MHz, and the transmitting power is set as 6 dBm. The detailed simulation parameters can be seen in Table 1.Table 1
Simulation parameters.
ParameterValueNumber of fileQ160Cache capacity of eNodeBVk (#)8, 16, 24, 32, 40Cache capacity of vehicleVc (#)4, 8, 12, 16, 20Transmission range of vehicleR200 mTransmission range of eNodeBRe500 mRoad lengthL2 kmCluster merging thresholdLc100 mNCMmax10Zipf parameterβ0.5sq1, 2, 3, 4, 5 MBCH metric coefficientαi,βi,γi0.32, 0.32, 0.36Coded delivery time thresholdTr1.0 sCH¯TIMER,JOIN¯TIMER2.0 sLink life time thresholdω2.0 sMultiobjective function coefficientλ1,λ20.01, 0.99BandwidthBv=Bc10 MHzTransmission powerPr=Pc=Pn6 dBmNoise power density-174 dBm/HzBackhaul link data rateRr2s40 MbpsWe compare and validate our proposed method with some state-of-the-art schemes in terms of the following performance metrics:(1)
Cache Hit Ratio. The ratio of the files satisfied by all cache nodes to all requests to the cache nodes(2)
Average Response Delay. The average time interval from the user sending the request to receive data (short for)(3)
Network Load. The network load that is downloaded from edge cache nodes and a remote server(4)
Ratio of Redundant Files. The ratio of the received packets that contain redundant subfiles to the total received subfiles in all packets, we use redundant ratio in figures to represent the ratio of redundant files to simplify the expressionOn the one hand, we compare our coded delivery method with COMP [23], “RSU-based cache only” [40], and “FSA-based cache” [41] in terms of a cache hit ratio, average response delay, and average network load. On the other hand, we compare our proposed method with “Optimal coded cache” [14] and “No coded-based method”, which includes COMP, “RSU-based cache only”, and “FSA-based cache” in terms of the ratio of the redundant files. Last but not the least, we will analyze the impact of cache size, size per file, velocity, and arrival rate on the four metrics.


## 7.2. Effect of Cache Size

As can be seen from Figure4, we compare our proposed method with COMP, “FSA-based cache”, and “RSU-based cache only”. In addition, we set the cache size of eNodeB Vk {8, 16, 24, 32, 40} and Vc {4, 8, 12, 16, 20}, respectively. The average velocity is 40 km/h, and the arrival rate of vehicles is set to 600 vehicles/h; the size per file is set as 1 MB. The number of the x axis on y axis represent the total cache size, i.e., Vk+Vc, and the performance metrics, respectively.Figure 4
Effect of cache sizeVk and Vc on system performance.
(a)
Network load vs. cache size(b)
Redundant ratio vs. cache size(c)
Hit ratio vs. cache size(d)
Average response delay vs. cache sizeFigure4(a) illustrates that the network load of the other three methods keeps constant and higher than our proposed method despite different cache sizes. Because our proposed coded delivery method does not only reduce redundant files requested by users but also eliminates the redundancy among subfiles, however, the total requests of the other three methods do not change due to the constant vehicle number given the fixed velocity and arrival rate.Furthermore, in Figure4(b), we can find that the ratio of redundant files of all methods will almost decrease slightly with the increase of cache size on the edge nodes because the probability of different users request the same file will decrease with the increase of cache size.From Figure4(c), it is easily observed that our proposed method outperforms the other three methods in terms of hit ratio. It can be explained that our proposed method considers a two-level edge cache; for instance, cluster head and eNodeB can cache the most requested files according to the request probability. COMP also adopts cluster heads to cache the most popular files and part of less popular files cooperatively, but there is no cooperation among RSUs; thus, the hit ratio is lower than ours. The “FSA-based cache” method and “RSU-based cache only” are worse than our proposed method and COMP due to the lack of edge cache. On the other hand, the hit ratio “FSA-based cache” is higher than that of “RSU-based cache only” because RSU also considers the cooperation cache among RSUs though it ignores the cooperation among cluster heads in “FSA-based cache.”In Figure4(d), the average response delay of the four methods is compared. On the one hand, the average response delay of all methods will decrease with the increase of cache size, because more requests will be satisfied by the cache node if the cache size is large enough. On the other hand, it can be observed that our proposed method can obtain the least average response delay because we cache the popular file on the edge node as much as possible, where the response delay is smaller compared to the response delay from the remote server. The average response delay of COMP decreases quickly because more requests will be satisfied by cluster heads and eNodeB when the cache size increase although the request is mainly satisfied by a remote server at the beginning. As for “FSA-based cache” and “RSU-based cache only”, the average response delay is much larger than our proposed method, because they do not consider caching files on cluster head cache, all the requests will be satisfied from eNodeB or remote server. Furthermore, the average response delay of the “FSA-based cache” outperforms that of “RSU-based cache only”, because “FSA-based cache” has also considered the cooperation among eNodbBs. From the above figures, we can easily find that cache size has a great impact on the hit ratio and response delay, and the impact of cache size on the network load and redundant ratio is not so obvious.


## 7.3. Effect of Size per File

In this subsection, the capacity of eNodeB and CH isVk=40 and Vc=20, respectively. The average velocity is 40 km/h, and the arrival rate of vehicles is set to 600 vehicles/h, and Q=160. The size per file changes from 1 MB to 5 MB.From Figure5(a), we can find that our proposed method can achieve better performance in terms of network load compared with COMP, “FSA-based cache”, and “RSU-based cache only.” The network load of COMP, “FSA-based cache”, and “RSU-based cache only” almost increase with the size per file linearly, because the total number of requests is almost the same given the mean velocity and arrival rate, and the network load will increase with the increase of the size of per file. Our proposed method adopts the coded delivery method to reduce the data traffic so that it can outperform the other three methods.Figure 5
Effect of size per file on system performance.
(a)
Network load vs. size per file(b)
Redundant ratio vs. size per file(c)
Hit ratio vs. size per file(d)
Average response delay vs. size per fileFrom Figure5(b), it can be observed that the ratio of redundant files of our proposed method outperforms the “Optimal coded cache” and “No coded-based method” methods, as it not only considers reducing the ratio of redundant files between files and also reduces the ratio of redundant files between subfiles. “No coded-based method” is the worst in terms of the ratio of redundant files because they do nothing to reduce the redundancy among files.As can be seen from Figure5(c), the hit ratio of four methods almost keeps the same under different sizes per file, as the hit ratio has nothing to do with size per file. Furthermore, the hit ratio of our proposed method is larger than the other three methods as our proposed method adopts the two-level caching strategy. COMP is also better than the other two methods as it takes advantage of the RSU cache cooperatively.From Figure5(d), it can be observed that the average response delay of the “RSU-based cache only” is larger than any other methods despite different sizes per file. Furthermore, the performance of “FSA-based cache” is better than that of “RSU-based cache only” since it considers the cooperation among RSUs. COMP and our proposed method can almost achieve the same performance and better than “FSA-based cache” and “RSU-based cache only”, as they obtain the request files mainly from edge cache node; thus, the average delay is smaller than that of “FSA-based cache” and “RSU-based cache only.” From the above discussion, we can find that the average response delay linearly grows with the size per file for all methods, since we assume that the response delay for each unit file is fixed. It can also be found that size per file has a large influence on the average response delay and network load, but little impact on the redundant ratio and hit ratio.


## 7.4. Effect of Velocity of Vehicle

In this subsection, we compare our proposed method with other methods and analyze the impact of the mean velocity of vehicles on the performances. We set the size per file as 1 MB,Vk=8, and Vc=4. The arrival rate of vehicles is set to 600 vehicles/h, and the average velocity changes from 40 km/h to 120 km/h.As can be seen from Figure6(a) that the network load for all methods decreases with the mean velocity because the larger the mean velocity is, the smaller the cluster size and the total number of vehicles on the road is, however, the number of clusters will increase. Thus, the request and response data traffic from all vehicles will decrease with the increase of mean velocity. Though the reduction is not significant for our proposed method, our proposed method outperforms the other three methods in terms of network load due to the coded delivery method.Figure 6
Effect of velocity of vehicles on system performance.
(a)
Network load vs. mean velocity(b)
Redundant ratio vs. mean velocity(c)
Hit ratio vs. mean velocity(d)
Average response delay vs. mean velocityFrom Figure6(b), we can find that the ratio of redundant files of “No coded-based method” cache and “Optimal coded cache” increases slightly with the increase of velocity, and our proposed method increases rapidly but has better redundant performance than the other two methods. The reason is that when the average velocity increases, there are more clusters and smaller cluster sizes under the coverage of eNodeB, which means that there are more CH that can cache popular files. Each CH under the coverage of eNodeB will cache the same files, and our proposed method is more dependent on the edge cache, which causes a sharp increase in the ratio of redundant files in our proposed method when the arrival rate is high.From Figure6(c), it can be easily found that our proposed method can achieve the highest hit ratio; the second one is COMP. With the increase of velocity, there will be more clusters and each CH can cache some files, and our proposed method and COMP can take advantage of the edge cache; thus, their hit ratio will grow significantly with the increase of velocity. However, “FSA-based cache” and “RSU-based cache only” mainly depend on the cache of eNodeB; thus, their hit ratio almost keeps constant.In Figure6(d), we compare our proposed method with the other three methods in terms of the average response delay. When the mean velocity increases, there will be more clusters and smaller size of the cluster; thus, many files can be cached on the CHs, which will reduce the response time greatly and improve the hit ratio for our proposed method and COMP; of cause, our proposed method still obtain the lowest response delay. Furthermore, we can find the average response delay of “FSA-based cache” and “RSU-based cache only” slowly decreases as the total number of vehicles and requests will decrease with the increase of mean velocity. From the simulation, it can be found that the mean velocity has a great impact on all performance metrics.


## 7.5. Effect of Arrival Rate

In this subsection, we will compare our proposed method with the other three methods and analyze the impact of the arrival rate of vehicles on the performances. In this subsection, we set the size per file 1 MB,Vk=24, and Vc=12. The average velocity is 40 km/h, the file number is set as Q=160, and the arrival rate of vehicles changes from 600 vehicles/h to 1000 vehicles/h.From Figure7(a), it is observed that the network load for the other three methods increases when the arrival rate of vehicles also increase, which can be explained by the fact that the larger the arrival rate of vehicles will lead to more vehicles on the road given the mean velocity; consequently, the request and the total traffic will also increase. However, the arrival rate of vehicles almost does not put any impact on our proposed method in terms of network load, that is because we adopt the coded delivery method.Figure 7
Effect of arrival rate of vehicles on system performance.
(a)
Network load vs. arrival rate(b)
Redundant ratio vs. arrival rate(c)
Hit ratio vs. arrival rate(d)
Average response delay vs. arrival rateFrom Figure7(b), we can find that the ratio of redundant files in our proposed method is the lowest among all methods. Though the “Optimal coded cache” and our proposed method have adopted coded delivery method to reduce the ratio of redundant files. What is more, our proposed method also focuses on reducing the ratio of redundant files among subfiles; thus, our proposed method can outperform “Optimal coded cache.” “No coded-based method” is still the worst method in terms of the ratio of redundant files as it does nothing to reduce the redundant files.In Figure7(c), we compare the hit ratio with the other three methods and analyze the impact of the arrival rate on the hit ratio. First of all, we find that the hit ratio of all four methods will decrease with the increase in the arrival rate. The reason is that when the arrival rate increase when the mean velocity is given, the total number of vehicles and the cluster size on the road will also increase; however, the number of the cluster under the coverage of each eNodeB will decrease, which will lead to the decrease of the contents on the edge nodes; therefore, the hit ratio will decrease, especially for our proposed method and COMP. The hit ratio of “FSA-based cache” and “RSU-based cache only” almost keep the constant, because their hit ratio mainly depends on the cached files on eNodeB (RSU); furthermore, we can also find that our proposed method still can obtain the highest hit ratio.From Figure7(d), it can be easily found that the average response delay will grow with the increase of arrival rate, and this can also be explained that a larger arrival rate will lead to larger cluster size and less number of cluster, which leads to a decrease in the hit ratio, and more requests will be responded by a remote server. Our proposed method outperforms other methods because it can make the most of the edge cache advantage and cooperatively cache on neighboring eNodeBs, and it will obtain the most files from the edge nodes. CH cache is also considered in COMP; thus, its average response delay is better than that of “FSA-based cache” and “RSU-based cache only.” When the arrival rate increase, more vehicles will compete to request the files from the limited space of eNodeB, and the average response delay for “FSA-based cache” and “RSU-based cache only” will almost linearly grow with the increasing of arrival rate. In summary, we can find that the arrival rate of vehicles has a great impact on the network load, hit ratio, and average response delay.


## 8. Conclusion

In this paper, we have designed an effective cluster method for reliable communication and proposed a two-level cooperative cache deployment approach based on the CH and eNodeB cache to reduce the response delay and improve the hit ratio. In the proposed approach, eNodeBs can cooperatively cache the same and different files to further improve the hit ratio and reduce the response time, and then, we derive an optimal cache deployment strategy for eNodeB and CH is derived. Lastly, we have proposed a coded delivery method based on file coding and subfile coding to reduce the network load and reduce the response delay. In terms of the simulation results, it is unveiled that a larger cache size, smaller size per file, smaller mean velocity, and arrival rate can improve the system performance. On the other hand, our proposed method can greatly reduce the network load and the response delay and improve the ratio of redundant files and hit ratio. In future work, we will focus on a multihop transmission strategy based on edge cache and a coded delivery strategy in the 5G New Radio (NR) V2X system.



---

*Source: 8864004-2021-05-03.xml*