# NCaAC: Network Coding-Aware Admission Control for Prioritized Data Dissemination in Vehicular Ad Hoc Networks

Authors: Shujuan Wang; Qian Zhang; Shuguang Lu
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

Vehicular Ad hoc NETworks (VANETs) are becoming an important part of people’s daily life, as they support a wild range of applications and have great potential in critical fields such as accident warning, traffic control and management, infotainment, and value-added services. However, the harsh and stringent transmission environment in VANETs poses a great challenge to the efficient and effective data dissemination for VANETs, which is the essential in supporting and providing the desired applications. To resolve this issue, Instantly Decodable Network Coding (IDNC) technology is applied to stand up to the tough transmission conditions and to advance the performance. This paper proposes a novel admission control method that works well with any IDNC-assisted data dissemination algorithm, to achieve fast and reliable data dissemination in VANETs. Firstly, the proposed admission control strategy classifies the safety-related applications as high priority and the user-related applications as low priority. It then conducts different admission policies on these two prioritized applications’ data. An artfully designed network coding-aware admission policy is proposed to regulate the flow of low-priority data requests and to prevent the network from congestion, through comparing the vectorized distances between the data requests and the encoding packets. Moreover, the carefully planned admission strategy is benefit for maximizing the network coding opportunities by inclining to admit requests which can contribute more to the encoding clique, thus further enhancing the system performance. Simulation results approve that the proposed admission control method achieves clear advantages in terms of delay, deadline miss ratio, and download success ratio.


---

## Body

## 1. Introduction

Owing to the rapid development of wireless communication technologies, electronic sensing technologies, and computer processing capabilities, as well as the increasing smart vehicle ownership, the Intelligent Transportation System (ITS) has evolved into the integrated smart control and management of public traffic and transportation. Vehicular Ad hoc NETworks (VANETs) are critical constituents of the ITS and have great potential in enhancing traffic safety and providing comfort for users [1]. VANETs are mainly composed of smart vehicles equipped with on-board communication devices and RoadSide Units (RSUs), which are connected to the backbone networks through wired links. Information generated and collected from various nodes in VANETs is transferred and exchanged under two classical communication models, which are known as the Vehicle-to-Vehicle (V2V) and Vehicle-to-RSU (V2R) modes [2]. During travelling, vehicles send out service requests for different applications, such as music or video download, locations search, or weather or traffic inquiry. Each application has specific requirements for Quality of Service (QoS), in terms of delay, jitter, or packet loss ratio. Moreover, extra considerations should be given under particular application scenarios. For example, when vehicles gather together and the number of requests increase largely, which is very commonly seen in the dense urban scenario or congested highway scenario, the limited network resources cannot guarantee that all requests can be served in time and network congestion will occur and make a great negative impact on the received QoS [3]. To provide user-satisfying QoS for wireless applications in VANETs, it is vital to avoid network congestion and prevent system overload through rational utilization of network resources.In VANETs, V2V communication refers to a network formed by vehicle nodes, which can share and forward information between each other. However, due to the limited transmission range and great mobility of vehicle nodes, the connected time between vehicles is very short, which, although not a severe issue for urban road with dense vehicle nodes [4, 5], can be a huge challenge and seriously affect the performance of data dissemination between vehicles in the highway scenarios, where the density of vehicles is sparse, the distance between vehicles is large, and vehicles are moving very fast which results in a rapidly changing network topology. Consequently, RSUs that are deployed along highway roads are preferred to realize data exchange with vehicles through single hop multicast, thanks to their high reliability and robustness.The typical applications that VANETs support are basically categorized as two main kinds: one is safety-related applications (collision warning, road condition information, etc.) and the other is user-related application (entertainment, internet access, etc.). Generally speaking, safety-related applications have higher requirements for real-time performance and accuracy, which can significantly reduce the occurrence of traffic accidents, and are the most important compared with user-related applications [6]. For example, when an accident occurs on a road spot, the safety-related applications are expected to timely send the information to the follow-up vehicles so these vehicles can take appropriate actions to avoid traffic accidents, such as serial collision. If the safety-related applications fail to send warning information to the subsequent vehicles in time, the consequences will be very serious. Therefore, the timeliness requirement of safety-related applications is very strict, and the reduction of data dissemination delay is very important. While ensuring security, it is also important to provide clients with good driving/riding experiences by providing them convenient data services. As a result, the QoS requirement of user-related applications for quick and efficient data services should be given enough consideration at the same time.Admission control is pervasively adopted in wireless networks, in the aim of load balancing and providing guaranteed QoS [7, 8]. The essence of admission control is to determine whether to accept a newly arrived service request, concerning if the rest network resources could meet the new service request’s resource demand without affecting the existing requests’ QoS, based on a certain criterion or calculation in the network [9, 10]. VANETs have the characteristics of mobile ad hoc networks, such as dynamic network topology and unfixed structure. Moreover, due to high-speed movement of nodes and dynamic change of node density, the communication channels in VANETs are unstable and the data transmission performance is affected greatly. The existing admission control schemes for mobile ad hoc networks or wireless networks cannot directly fit in VANETs, and appropriate admission control mechanism should be designed according to the characteristics of vehicle nodes. Currently, a number of studies that apply admission control in VANETs indicate that admission control can reasonably allocate network resources and efficiently control system load, thus having great potential in providing satisfying QoS [11–14].In this paper, we propose a novel network coding-aware admission control scheme that suits the data dissemination via V2R communication in VANETs. In particular, considering that the safety-related applications are highly affinitive with personal safety and security, it is of vital importance to fully meet the stringent QoS requirements of the safety-related applications. Meanwhile, the QoS requirements of data dissemination that supports the user-related applications should be satisfied as well. The proposed method jointly optimizes the transmission performance of safety-related and user-related applications, thus improving the overall QoS. The main contribution of this work can be summarized as follows:(i)
We artfully integrate admission control, the typical load balancing technology, with data dissemination in VANETs. In order to satisfy the data requests of user-related applications as much as possible without degrading the QoS of safety-related applications, distinct admission policies are proposed to discriminate different service requirements between safety-related applications and user-related applications.(ii)
We design a novel network coding-aware admission control scheme for V2R communications in VANETs. Different from existing admission control mechanisms, the proposed scheme adopts the network coding gain as major criterion for making admission decisions. The performance improvement derived from the network coding technology is able to be maximized and the degradation caused by excessive service requests can be mitigated in this way.(iii)
Extensive experiments are conducted to evaluate the performance of proposed admission control scheme. Simulation results demonstrate that the proposed scheme achieves marked performance enhancement in terms of download delay, deadline miss ratio, and download success ratio for prioritized data dissemination, thus justifying the effectiveness and efficiency of the proposed method.The rest of this paper is organized as follows: Section2 outlines the reference works of admission control and network coding for data dissemination in VANETs. Section 3 describes system model for V2R communication in highway environment. Section 4 explains the proposed network coding-aware admission control algorithm in detail. Section 5 provides extensive simulation results and evaluates the proposed algorithm. Finally, Section 6 concludes this paper.


## 2. Related Works

### 2.1. Admission Control for VANETs

The adoption and implementation of admission control in VANETs are becoming popular and valued. In [15], Tuan et al. proposed an admission control scheme which jointly considered channel IDR (IDle time Ratio) value and buffer situation. The scheme restricts the access of nonemergency services to the network and reserves bandwidth for emergency services, thus guaranteeing the QoS of emergency services. However, the proposed admission control scheme merely takes the IDR as the sole QoS metric, which is far from perfect. Reference [11] considered the scenario where vehicles are divided into multiple clusters, and RSUs are seen as the network access points forming in tree topology. An admission control scheme was proposed which employs multiple metrics of QoS (i.e., packet loss ratio, throughput, and average delay) to determine whether new vehicles should be allowed to enter a cluster without affecting the QoS of existing vehicles in the cluster. However, the scheme judges whether to allow new vehicles to enter the existing cluster using merely four QoS metrics, without considering the running statuses of vehicles, which may not be appropriate for usage in practical vehicular communication scenarios.The QoS of V2V and V2R communications in VANETs, as well as the system resource utilization, are badly affected by the characteristics of VANETs, such as limited network resources, high-speed moving vehicles, and frequently changing topologies. In [16], the author proposed a QoS-oriented adaptive admission control scheme based on vehicle density. By dynamically adjusting the transmission power of vehicles, the connection time of V2R communication links is improved. New arrived requests are determined whether they can be allowed to enter the system while ensuring throughput and maximizing the utilization of available resources. In [14], the problem of disconnection between vehicles and network communication links was considered in V2R communications when a vehicle node switches between two RSUs. An admission control algorithm that prioritizes handoff flows was proposed to ensure the QoS of the handoff flows while reasonably allocating available resources. Although the proposed scheme reduces the probability of frequent disconnection of vehicle nodes during handover, system performance may not change much when vehicle nodes successfully switch to another RSU. Reference [17] proposed a QoS-aware admission control method which is capable of finding a D2D communication link that maximizes the system performance under the constraints of QoS and network resources, while crucial vehicular factors are overlooked which may hinder the application in VANETs.


### 2.2. Network Coding-Based Data Dissemination in VANETs

Network coding technology enables the intermediate nodes to encode data packets before transmission, thus increasing the number of packets sent by the sending node in a single transmission. Through this way, the delay of data dissemination can be reduced and system throughput and resource utilization of the system are improved. Moreover, it has been proved that network coding technology has great potential for ensuring security and reducing packet loss [18–20]. In VANETs, the performance of data dissemination determines whether safety-related and user-related applications information can be provided for vehicle users in time and reliably. In [21], access points (APs) are optimized in V2R communications by selecting Random Linear Network Coding (RLNC) coded packets to multicast to all vehicles, thus improving data dissemination rate and reducing data dissemination delay. When transmitting nonsafety data between common interest regions of two RSUs, two packets from different RSUs are encoded into one packet by network coding technology, and the encoded packet is then multicasted to vehicle nodes, which effectively reduce bandwidth consumption and mitigate network congestion [22]. In [5], a data dissemination method based on network coding is proposed in V2R communication to reduce the response time of RSUs. However, the adopted Random Linear Network Coding technology introduces a certain decoding delay when the receiving vehicle node decodes the encoded packet, thus degrading the system performance.In order to solve this issue, Sorour and S. Valaee [23] proposed the Instantly Decodable Network Coding (IDNC) technology to minimize the decoding delay. Packets that are encoded by the IDNC technology are instantly decodable upon arriving at the receiving nodes; hence, the decoding delay introduced by the RLNC technology is decreased to zero. Obviously, the IDNC technology is more appropriate for applications in VANETs comparing to the RLNC technology, due to the stringent requirements for transmission delay. Wang and Yin [24] proposed a two-stage data dissemination strategy in VANETs. The IDNC technology was applied in the second stage where the selected relay nodes multicast IDNC encoded packets to serve vehicles that were not satisfied in the first-stage transmission. Later in [25], a prioritized data dissemination algorithm based on Instantly Decodable Network Coding for V2R communications in VANETs was proposed. The data of safety-related applications and user-related applications have been assigned different priorities. The proposed algorithm schedules the requested data packets based on a finely designed utility calculation method which takes multiple metrics into consideration, such as the data priority, the running status of each vehicle, the data popularity, and deadline constraints. Packet that has the highest utility is selected for instant transmission. Moreover, IDNC technology is adopted to further maximize network throughput and to reduce the access delay. Simulation results have justified the efficiency and performance improvement of the proposed algorithm. Nevertheless, the authors leave out an important issue that is critical for practical V2R communications. Given the dense vehicles and frequent requests in realistic V2R communication scenarios, network congestion and transmission collisions occur constantly, which will put a heavy burden on the serving RSUs and negatively affect the data dissemination performance. What is worse, a great number of requests for user-related application data will occupy and consume the network resources that are preferably utilized by the safety-related application data, degrading the QoS performance of safety-related applications and resulting in unacceptable dangers and risks.In view of this, this paper proposes a novel admission control method which is propitious for the IDNC-assisted prioritized data dissemination in VANETs. The proposed method regulates the number of admitted requests for user-related applications when the total number of data requests increases, thus keeping the network from becoming congested and preventing QoS degradation of safety-related applications. Meanwhile, the QoS of user-related applications is also carefully considered in that requests for user-related applications are admitted as much as possible so that the overall system performance is guaranteed.


## 2.1. Admission Control for VANETs

The adoption and implementation of admission control in VANETs are becoming popular and valued. In [15], Tuan et al. proposed an admission control scheme which jointly considered channel IDR (IDle time Ratio) value and buffer situation. The scheme restricts the access of nonemergency services to the network and reserves bandwidth for emergency services, thus guaranteeing the QoS of emergency services. However, the proposed admission control scheme merely takes the IDR as the sole QoS metric, which is far from perfect. Reference [11] considered the scenario where vehicles are divided into multiple clusters, and RSUs are seen as the network access points forming in tree topology. An admission control scheme was proposed which employs multiple metrics of QoS (i.e., packet loss ratio, throughput, and average delay) to determine whether new vehicles should be allowed to enter a cluster without affecting the QoS of existing vehicles in the cluster. However, the scheme judges whether to allow new vehicles to enter the existing cluster using merely four QoS metrics, without considering the running statuses of vehicles, which may not be appropriate for usage in practical vehicular communication scenarios.The QoS of V2V and V2R communications in VANETs, as well as the system resource utilization, are badly affected by the characteristics of VANETs, such as limited network resources, high-speed moving vehicles, and frequently changing topologies. In [16], the author proposed a QoS-oriented adaptive admission control scheme based on vehicle density. By dynamically adjusting the transmission power of vehicles, the connection time of V2R communication links is improved. New arrived requests are determined whether they can be allowed to enter the system while ensuring throughput and maximizing the utilization of available resources. In [14], the problem of disconnection between vehicles and network communication links was considered in V2R communications when a vehicle node switches between two RSUs. An admission control algorithm that prioritizes handoff flows was proposed to ensure the QoS of the handoff flows while reasonably allocating available resources. Although the proposed scheme reduces the probability of frequent disconnection of vehicle nodes during handover, system performance may not change much when vehicle nodes successfully switch to another RSU. Reference [17] proposed a QoS-aware admission control method which is capable of finding a D2D communication link that maximizes the system performance under the constraints of QoS and network resources, while crucial vehicular factors are overlooked which may hinder the application in VANETs.


## 2.2. Network Coding-Based Data Dissemination in VANETs

Network coding technology enables the intermediate nodes to encode data packets before transmission, thus increasing the number of packets sent by the sending node in a single transmission. Through this way, the delay of data dissemination can be reduced and system throughput and resource utilization of the system are improved. Moreover, it has been proved that network coding technology has great potential for ensuring security and reducing packet loss [18–20]. In VANETs, the performance of data dissemination determines whether safety-related and user-related applications information can be provided for vehicle users in time and reliably. In [21], access points (APs) are optimized in V2R communications by selecting Random Linear Network Coding (RLNC) coded packets to multicast to all vehicles, thus improving data dissemination rate and reducing data dissemination delay. When transmitting nonsafety data between common interest regions of two RSUs, two packets from different RSUs are encoded into one packet by network coding technology, and the encoded packet is then multicasted to vehicle nodes, which effectively reduce bandwidth consumption and mitigate network congestion [22]. In [5], a data dissemination method based on network coding is proposed in V2R communication to reduce the response time of RSUs. However, the adopted Random Linear Network Coding technology introduces a certain decoding delay when the receiving vehicle node decodes the encoded packet, thus degrading the system performance.In order to solve this issue, Sorour and S. Valaee [23] proposed the Instantly Decodable Network Coding (IDNC) technology to minimize the decoding delay. Packets that are encoded by the IDNC technology are instantly decodable upon arriving at the receiving nodes; hence, the decoding delay introduced by the RLNC technology is decreased to zero. Obviously, the IDNC technology is more appropriate for applications in VANETs comparing to the RLNC technology, due to the stringent requirements for transmission delay. Wang and Yin [24] proposed a two-stage data dissemination strategy in VANETs. The IDNC technology was applied in the second stage where the selected relay nodes multicast IDNC encoded packets to serve vehicles that were not satisfied in the first-stage transmission. Later in [25], a prioritized data dissemination algorithm based on Instantly Decodable Network Coding for V2R communications in VANETs was proposed. The data of safety-related applications and user-related applications have been assigned different priorities. The proposed algorithm schedules the requested data packets based on a finely designed utility calculation method which takes multiple metrics into consideration, such as the data priority, the running status of each vehicle, the data popularity, and deadline constraints. Packet that has the highest utility is selected for instant transmission. Moreover, IDNC technology is adopted to further maximize network throughput and to reduce the access delay. Simulation results have justified the efficiency and performance improvement of the proposed algorithm. Nevertheless, the authors leave out an important issue that is critical for practical V2R communications. Given the dense vehicles and frequent requests in realistic V2R communication scenarios, network congestion and transmission collisions occur constantly, which will put a heavy burden on the serving RSUs and negatively affect the data dissemination performance. What is worse, a great number of requests for user-related application data will occupy and consume the network resources that are preferably utilized by the safety-related application data, degrading the QoS performance of safety-related applications and resulting in unacceptable dangers and risks.In view of this, this paper proposes a novel admission control method which is propitious for the IDNC-assisted prioritized data dissemination in VANETs. The proposed method regulates the number of admitted requests for user-related applications when the total number of data requests increases, thus keeping the network from becoming congested and preventing QoS degradation of safety-related applications. Meanwhile, the QoS of user-related applications is also carefully considered in that requests for user-related applications are admitted as much as possible so that the overall system performance is guaranteed.


## 3. System Model

The system model is depicted in Figure1. The framework of this system model is similar to that in a series of existing reference works [25–27], except for the admission control module. The focused scenario is the highway scenario where RSUs are assumed to be deployed equidistantly along the highway roadways. Each RSU is interconnected with the backbone internet through wired links and has access to the content server. The effective communication radius of each RSU is set as r. When a vehicle enters into the effective communication coverage of a RSU, the RSU provides wireless access port for the vehicle and two types of communication channels can be established between them. Control channel is set up for transmitting control signals and service channel is used for performing data transmission services. Each vehicle is equipped with an On-Board Unit (OBU) to communicate with RSUs through wireless channels, as well as with GPS (Global Positioning System) and sensors to obtain real-time location information of neighboring vehicles and surrounding roadway information. Further assume that both RSUs and vehicles with OBUs work in accordance with the Dedicated Short Range Communications (DSRC) protocol [28], which states that the transmitter/receiver nodes in VANETs should work in half-duplex mode; i.e., it is not allowed to transmit and receive packets at the same time.Figure 1
System model.Denote theM data items stored in the content server as D=d1,d2,…,dM. For any RSU Ri, N vehicles in Ri’s coverage are recorded as VH=vh1,vh2,…,vhN. The speed of vehicle vhi is marked as vi. Time is slotted and at any time slot t, vhi can send out a request for a specific application, along with vhi’s running status, such as vhi’s location, speed, and identification code. The request can be denoted as ri=qi|IDi,location,vi, where qi=dj represents the specific requested data item and IDi stands for vhi’s identification code. Upon receiving ri, Ri firstly determine the priority of this request. Safety-related request is classified as high priority and is assigned a weight ω1, while user-related request is categorized as low priority and is associated with a weight ω2, ω1>ω2. For high-priority request, Ri confirms vhi’s location and speed, checking whether vhi is within the communication coverage. If so, Ri accepts ri immediately and sorts ri into a dynamically maintained high-priority service queue. For low-priority request, Ri launches a network coding-aware admission control process to decide whether the request can be accepted and admitted into the service queue. After the precise decision-making process, if the answer is positive, the low-priority request is put into Ri’s low-priority service queue. Otherwise, the request is rejected immediately, and a rejection notification message is sent to the requesting vehicle. The vehicle discards the rejected request and can generate new requests in subsequent time slots, as long as it is covered by the communication radius.At each transmission,Ri schedules the data items in the service queues based on a chosen network coding-assisted scheduling algorithm. Firstly, Ri generates an IDNC encoded packet that potentially has the highest reward. It then multicasts this IDNC packet to all vehicles within its coverage. After receiving this packet, each vehicle decodes the encoded data items with the aid of its cached data items. If the requested data item can be decoded from the IDNC packet, a positive feedback message will be sent to Ri to notify the successful service for the request. Otherwise a negative feedback message will be sent back to Ri, indicating the failure of satisfying the request. Ri then decides whether the request needs to be served in the future or it shall be removed from the service queue based on the feedback message. The process goes until all vehicles run out of Ri’s coverage. The YES/NO feedback message is set to be 1-bit and is piggybacked with system signaling to be sent through the control channel, so that the total overhead of feedback is controllable and the successful receiving of feedback messages at the RSU can be guaranteed. Other than that, the interactions between vehicles and Ri occurred through the service channels.Obviously, since a vehiclevhi can only receive data items from Ri when it is within Ri’s coverage, there is a time limit on vhi’s request after which the request will expire. Thus, when vehicle vhi generates a request for desired data item, the request has an inherent deadline, which is the time that vhi can dwell in Ri’s coverage. In order to achieve satisfying QoS for both safety-related and user-related applications, Ri needs to serve as many requests as possible before they get expired. In the meantime, each request is expected to be served as fast as possible so that the corresponding data can be utilized by application layers timely. The overall data dissemination procedure is shown in Figure 2.Figure 2
NCaAC enabled prioritized data dissemination for VANETs.


## 4. Network Coding-Aware Admission Control (NCaAC) for Prioritized Data Dissemination in VANETs

In this section, we introduce the proposed Network Coding-aware Admission Control (NCaAC) algorithm in detail. This work mainly focuses on the design and utilization of efficient admission control strategy, so as to intimately work with existing network coding-based data dissemination methods to boost their adaptabilities for practical communication environment and to enhance their capabilities of guaranteeing the QoS of high-priority data applications under dense requests. For the purpose of clarity, we give a brief introduction of IDNC-assisted data scheduling algorithms before the elaboration of the NCaAC.


### 4.1. IDNC-Assisted Data Dissemination in VANETs

To serve the admitted data requests, at each time slot,Ri firstly constructs an IDNC graph GV,E according to the admitted data requests in the service queues. Assume vehicle vhi requests data item dj from Ri, and this request is admitted. A vertex aij∈V is generated, where V is the vertex set of G. Similarly, vehicle vhl is admitted for requesting data dk, which is denoted as vertex alk. Consequently, each request in the service queues is recorded as a vertex in graph G, and the weight of each vertex is assigned as a specific value that is calculated according to different scheduling algorithms. For instance, the weight of each vertex is defined as the deadline of the corresponding request in the classical Earliest Deadline First (EDF) scheduling algorithm [29]. An edge between any two vertices aij and alk can be drawn if and only if any of the following conditions stands:(1)
j=k, the condition holds when vhi and vhl request the same data item(2)
datadj which is requested by vehicle vhi is cached at vehicle vhl, while data dk which is requested by vehicle vhl is cached at vehicle vhiWhen any of the above conditions is met, an edgeejk is generated between aij and alk. It is easy to know that ejk represents the coding opportunity between aij and alk. When vertices are connected with each other through edges, an IDNC packet can be generated by XORing the data items that are identified by each vertex over a clique in G, and this IDNC packet is instantly decodable at vehicle receivers. Therefore, IDNC provides the maximum system performance enhancement by searching the maximum weighted clique in the constructed graph and further encoding the data items that are recognized by the vertices in the found maximum weighted clique. Once the IDNC packet is generated, Ri multicasts this packet to all vehicles within its coverage. Each vehicle that receives this packet executes the decoding process with the aid of cached data items to decode out the requested data item. A 1-bit YES/NO feedback message is sent to Ri to indicate the success/failure of receiving the requested data item. Based on the feedbacks, Ri updates the IDNC graph by removing vertices that represent the newly received data items, deleting expired vertices, and redrawing edges between updated vertices. The process goes on until the updated IDNC graph becomes empty; in other words, no active request remains in Ri’s service queues. The pseudocode of IDNC-assisted data dissemination in VANETs is given in Algorithm 1.Algorithm 1:IDNC‐assisted data dissemination.
input: data requests of vehicles within coverage
(1)
while Ri’s service queues are not empty do
(2)
Ri constructs the IDNC graph GV,E as described in Section 4.1;
(3)
Ri calculates each vertex’s weight according to a specific scheduling algorithm;
(4)
Ri finds the maximum weighted clique C∗ in G;
(5)
Ri generates the IDNC packet by XORing all the data items identified by the vertices in C∗ and multicast it to all vehicles;
(6)
Each vehicle decodes the IDNC packet and sends back a 1-bit message toRi, notifying the success/failure of receiving the requested data item;
(7)
Ri updates the service queues and the vehicles’ statuses based on the feedbacks.
(8)
end while


### 4.2. Network Coding-Aware Admission Control Strategy

In this section, we explain minutely the proposed network coding-aware admission control strategy. The design of the admission control algorithm is inspired by the prioritized data scheduling in [25], while it works well with any known IDNC-assisted data scheduling algorithm. The admission control consists of two steps as follows.


#### 4.2.1. Characteristics Vectorization

As shown in Figure1, at each time slot, there might be multiple vehicles that are requesting the same data item dj from Ri within the transmission coverage. These requests, although they want the same item dj, have different deadlines as they are associated with varied vehicles. Denote the deadline of vehicle vhi for requesting item dj as dlij; define(1)dljmin=min1≤k≤Ndlkj,vhk∈VHdj,where VHdj is the set of vehicles that are requesting dj and dljmin represents the deadline of the most urgent request among all requests that are asking for item dj. Hj=e−dljmin stands for the utility value of all active requests that regard data item dj. To quantify the popularity of dj, define an indicator function Iidj, where Iidj=1 means that vehicle vhi is requesting item dj; otherwise, Iidj=0. The popularity of data item dj thus can be expressed as(2)Pdj=∑vhi∈RCRiIidj,where RCRi denotes the set of vehicles that are within Ri’s coverage.Moreover, in view of the fact that the probability of itemdj being successfully received by all requesting vehicles is strongly correlated with the distance between the requesting vehicles, the aggregation level of requesting vehicles is chosen to evaluate vehicles’ capability of receiving item dj. The degree of polymerization for vehicles that are requesting dj is defined as(3)DPdj=1/VHdj∑vhi∈VHdjxi−xRi2+yi−yRi2−μ2μ,where xi,yi and xRi,yRi are the coordinates of vehicle vhi and RSU Ri, respectively. µ is the average distance from all vehicles requesting dj to RSU Ri, and μ can be calculated as(4)μ=∑vhi∈VHdjxi−xRi2+yi−yRi2VHdj.Meanwhile, it is noticed that the shorter distance between all vehicles that are requestingdj and Ri would help to build more stable communication channels and thus increase the successful ratio of transmission. The distance between the geometric center of all vehicles requesting dj and Ri is a fine indicator to evaluate the transmission success ratio, and it can be calculated as(5)Ldj=xRi−∑vhi∈VHdjxiVHdj2+yRi−∑vhi∈VHdjyiVHdj2.Considering all the above factors, each admitted data request in the service queues can be represented by a vector. For instance, the request ofvhi for dj is expressed as a vector rvij=Hj,Pdj,DPdj,Ldj. For any IDNC-assisted data scheduling algorithm, each vertex in the found maximum weighted clique (MWC) can be represented as a vector, and a vector set VE is formed over the MWC as(6)VE=rvij=Hj,Pdj,DPdj,Ldj,…rvlk=Hk,Pdk,DPdk,Ldk,…1≤i,l≤N;1≤j,k≤M,The mean vector ofVE is denoted as rv¯=H¯,P¯,DP¯,L¯, and rv¯ can be obtained by calculating the average value of the four components separately.


#### 4.2.2. Admission Control Decision Process

To provide differentiated service for safety-related and user-related applications, as well as to make better use of limited network resources, the proposed admission control strategy allows all safety-related data requests to enter the network and entitles them to data service provided by the RSU. However, user-related data requests, namely, low-priority requests, have to pass the admissible test imposed by the admission controller before they are welcomed to the service.At any time slot, vehiclevhi generates a data request ri, specifically requesting data item dj. Upon receiving ri, the admission controller in Ri firstly determines the type of ri. Since ri is low priority, it needs to pass the admissible test before further response. Denote the vector set that is established on the MWC before Ri accepts ri as VEα; the mean vector of VEα is rvα¯=Hα¯,Pα¯,DPα¯,Lα¯. Moreover, if ri is admitted into Ri’s service queues, the IDNC graph will update and the MWC found on the graph will change accordingly, resulting in a new vector set VEβ. Denote the mean vector of VEβ as rvβ¯=Hβ¯,Pβ¯,DPβ¯,Lβ¯. The new request ri can be denoted as a data vector rvij=Hj,Pdj,DPdj,Ldj. The distance between rvij and rvα¯ can be calculated as(7)distrvij,rvα¯=Hj−Hα¯2+Pdj−Pdjα¯2+DPdj−DPdjα¯2+Ldj−Ldjα¯2.Similarly, the distance betweenrvij and rvβ¯ can be calculated as(8)distrvij,rvβ¯=Hj−Hβ¯2+Pdj−Pdjβ¯2+DPdj−DPdjβ¯2+Ldj−Ldjβ¯2.Based on the definition of vector similarity, it can be concluded that whendistrvij,rvα¯≤distrvij,rvβ¯, the new request ri is more similar with the mean vector of VEα than it is with the mean vector of VEβ. In other words, the mean vector of the vertices set that is constructed over the updated MWC after accepting the new request ri will drift away from the vector of ri. Thus, if the request is admitted, the probability of it being encoded into the IDNC packet is small. What is worse, the admission of ri could possibly prolong the waiting time of other admitted requests (especially the ones that ask for high-priority data items) and cause network congestion. As a result, in order to ensure the dissemination quality of admitted data requests in the system, the new request is rejected. Contrarily, if distrvij,rvα¯>distrvij,rvβ¯, it indicates that rvij is more similar with the mean vector of VEβ than it is with the mean vector of VEα. In other words, the acceptance of ri will advocate higher probability of being encoded into the IDNC packet and provide more coding opportunities. Accordingly, ri is admitted and put into Ri’s low-priority service queue. After the admission control decision process, Ri adopts the IDNC-assisted data scheduling algorithm to serve vehicles. The pseudocode of the proposed NCaAC is shown in Algorithm 2. Based on Algorithms 1 and 2, the overall prioritized data dissemination algorithm, which is IDNC-assisted and admission control enabled, is obtained. And the pseudocode is given in Algorithm 3.Algorithm 2:Network Coding-Aware Admission Control (NCaAC).
(1)
If Ri receives a newly arriving request ri then
(2)
Determine the priority ofri;
(3)
if ri is high priority then
(4)
Admitri and put ri into the high priority service queue;
(5)
else
(6)
Vectorizeri as rvij, the mean vector of VEα as rvα, and the mean vector of VEβ as rvβ;
(7)
Calculatervα and rvβ as described in Section 4.2.1;
(8)
Calculate the distance betweenrvij and rvα, and the distance between rvij and rvβ, respectively;
(9)
Compare the distances
(10)
if distrvij,rvα¯≤distrvij,rvβ¯ then
(11)
Rejectri;
(12)
Send a rejection message to the vehicle;
(13)
else
(14)
if distrvij,rvα¯>distrvij,rvβ¯ then
(15)
Admitri and put ri into the low priority service queue;
(16)
end if
(17)
end if
(18)
end if
(19)
end ifAlgorithm 3:NCaAC enabled prioritized data dissemination for VANETs.
Input: For any vhi belongs to VH, 1≤i≤N
(1)
while vhi dwells in the coverage of Ri do
(2)
Vehiclevhi randomly generates a request ri and sent it to Ri;
(3)
Ri receives ri;
(4)
Ri calls Algorithm 2 to perform admission control;
(5)
Ri calls Algorithm 1 to serve vehicles;
(6)
end while


## 4.1. IDNC-Assisted Data Dissemination in VANETs

To serve the admitted data requests, at each time slot,Ri firstly constructs an IDNC graph GV,E according to the admitted data requests in the service queues. Assume vehicle vhi requests data item dj from Ri, and this request is admitted. A vertex aij∈V is generated, where V is the vertex set of G. Similarly, vehicle vhl is admitted for requesting data dk, which is denoted as vertex alk. Consequently, each request in the service queues is recorded as a vertex in graph G, and the weight of each vertex is assigned as a specific value that is calculated according to different scheduling algorithms. For instance, the weight of each vertex is defined as the deadline of the corresponding request in the classical Earliest Deadline First (EDF) scheduling algorithm [29]. An edge between any two vertices aij and alk can be drawn if and only if any of the following conditions stands:(1)
j=k, the condition holds when vhi and vhl request the same data item(2)
datadj which is requested by vehicle vhi is cached at vehicle vhl, while data dk which is requested by vehicle vhl is cached at vehicle vhiWhen any of the above conditions is met, an edgeejk is generated between aij and alk. It is easy to know that ejk represents the coding opportunity between aij and alk. When vertices are connected with each other through edges, an IDNC packet can be generated by XORing the data items that are identified by each vertex over a clique in G, and this IDNC packet is instantly decodable at vehicle receivers. Therefore, IDNC provides the maximum system performance enhancement by searching the maximum weighted clique in the constructed graph and further encoding the data items that are recognized by the vertices in the found maximum weighted clique. Once the IDNC packet is generated, Ri multicasts this packet to all vehicles within its coverage. Each vehicle that receives this packet executes the decoding process with the aid of cached data items to decode out the requested data item. A 1-bit YES/NO feedback message is sent to Ri to indicate the success/failure of receiving the requested data item. Based on the feedbacks, Ri updates the IDNC graph by removing vertices that represent the newly received data items, deleting expired vertices, and redrawing edges between updated vertices. The process goes on until the updated IDNC graph becomes empty; in other words, no active request remains in Ri’s service queues. The pseudocode of IDNC-assisted data dissemination in VANETs is given in Algorithm 1.Algorithm 1:IDNC‐assisted data dissemination.
input: data requests of vehicles within coverage
(1)
while Ri’s service queues are not empty do
(2)
Ri constructs the IDNC graph GV,E as described in Section 4.1;
(3)
Ri calculates each vertex’s weight according to a specific scheduling algorithm;
(4)
Ri finds the maximum weighted clique C∗ in G;
(5)
Ri generates the IDNC packet by XORing all the data items identified by the vertices in C∗ and multicast it to all vehicles;
(6)
Each vehicle decodes the IDNC packet and sends back a 1-bit message toRi, notifying the success/failure of receiving the requested data item;
(7)
Ri updates the service queues and the vehicles’ statuses based on the feedbacks.
(8)
end while


## 4.2. Network Coding-Aware Admission Control Strategy

In this section, we explain minutely the proposed network coding-aware admission control strategy. The design of the admission control algorithm is inspired by the prioritized data scheduling in [25], while it works well with any known IDNC-assisted data scheduling algorithm. The admission control consists of two steps as follows.


### 4.2.1. Characteristics Vectorization

As shown in Figure1, at each time slot, there might be multiple vehicles that are requesting the same data item dj from Ri within the transmission coverage. These requests, although they want the same item dj, have different deadlines as they are associated with varied vehicles. Denote the deadline of vehicle vhi for requesting item dj as dlij; define(1)dljmin=min1≤k≤Ndlkj,vhk∈VHdj,where VHdj is the set of vehicles that are requesting dj and dljmin represents the deadline of the most urgent request among all requests that are asking for item dj. Hj=e−dljmin stands for the utility value of all active requests that regard data item dj. To quantify the popularity of dj, define an indicator function Iidj, where Iidj=1 means that vehicle vhi is requesting item dj; otherwise, Iidj=0. The popularity of data item dj thus can be expressed as(2)Pdj=∑vhi∈RCRiIidj,where RCRi denotes the set of vehicles that are within Ri’s coverage.Moreover, in view of the fact that the probability of itemdj being successfully received by all requesting vehicles is strongly correlated with the distance between the requesting vehicles, the aggregation level of requesting vehicles is chosen to evaluate vehicles’ capability of receiving item dj. The degree of polymerization for vehicles that are requesting dj is defined as(3)DPdj=1/VHdj∑vhi∈VHdjxi−xRi2+yi−yRi2−μ2μ,where xi,yi and xRi,yRi are the coordinates of vehicle vhi and RSU Ri, respectively. µ is the average distance from all vehicles requesting dj to RSU Ri, and μ can be calculated as(4)μ=∑vhi∈VHdjxi−xRi2+yi−yRi2VHdj.Meanwhile, it is noticed that the shorter distance between all vehicles that are requestingdj and Ri would help to build more stable communication channels and thus increase the successful ratio of transmission. The distance between the geometric center of all vehicles requesting dj and Ri is a fine indicator to evaluate the transmission success ratio, and it can be calculated as(5)Ldj=xRi−∑vhi∈VHdjxiVHdj2+yRi−∑vhi∈VHdjyiVHdj2.Considering all the above factors, each admitted data request in the service queues can be represented by a vector. For instance, the request ofvhi for dj is expressed as a vector rvij=Hj,Pdj,DPdj,Ldj. For any IDNC-assisted data scheduling algorithm, each vertex in the found maximum weighted clique (MWC) can be represented as a vector, and a vector set VE is formed over the MWC as(6)VE=rvij=Hj,Pdj,DPdj,Ldj,…rvlk=Hk,Pdk,DPdk,Ldk,…1≤i,l≤N;1≤j,k≤M,The mean vector ofVE is denoted as rv¯=H¯,P¯,DP¯,L¯, and rv¯ can be obtained by calculating the average value of the four components separately.


### 4.2.2. Admission Control Decision Process

To provide differentiated service for safety-related and user-related applications, as well as to make better use of limited network resources, the proposed admission control strategy allows all safety-related data requests to enter the network and entitles them to data service provided by the RSU. However, user-related data requests, namely, low-priority requests, have to pass the admissible test imposed by the admission controller before they are welcomed to the service.At any time slot, vehiclevhi generates a data request ri, specifically requesting data item dj. Upon receiving ri, the admission controller in Ri firstly determines the type of ri. Since ri is low priority, it needs to pass the admissible test before further response. Denote the vector set that is established on the MWC before Ri accepts ri as VEα; the mean vector of VEα is rvα¯=Hα¯,Pα¯,DPα¯,Lα¯. Moreover, if ri is admitted into Ri’s service queues, the IDNC graph will update and the MWC found on the graph will change accordingly, resulting in a new vector set VEβ. Denote the mean vector of VEβ as rvβ¯=Hβ¯,Pβ¯,DPβ¯,Lβ¯. The new request ri can be denoted as a data vector rvij=Hj,Pdj,DPdj,Ldj. The distance between rvij and rvα¯ can be calculated as(7)distrvij,rvα¯=Hj−Hα¯2+Pdj−Pdjα¯2+DPdj−DPdjα¯2+Ldj−Ldjα¯2.Similarly, the distance betweenrvij and rvβ¯ can be calculated as(8)distrvij,rvβ¯=Hj−Hβ¯2+Pdj−Pdjβ¯2+DPdj−DPdjβ¯2+Ldj−Ldjβ¯2.Based on the definition of vector similarity, it can be concluded that whendistrvij,rvα¯≤distrvij,rvβ¯, the new request ri is more similar with the mean vector of VEα than it is with the mean vector of VEβ. In other words, the mean vector of the vertices set that is constructed over the updated MWC after accepting the new request ri will drift away from the vector of ri. Thus, if the request is admitted, the probability of it being encoded into the IDNC packet is small. What is worse, the admission of ri could possibly prolong the waiting time of other admitted requests (especially the ones that ask for high-priority data items) and cause network congestion. As a result, in order to ensure the dissemination quality of admitted data requests in the system, the new request is rejected. Contrarily, if distrvij,rvα¯>distrvij,rvβ¯, it indicates that rvij is more similar with the mean vector of VEβ than it is with the mean vector of VEα. In other words, the acceptance of ri will advocate higher probability of being encoded into the IDNC packet and provide more coding opportunities. Accordingly, ri is admitted and put into Ri’s low-priority service queue. After the admission control decision process, Ri adopts the IDNC-assisted data scheduling algorithm to serve vehicles. The pseudocode of the proposed NCaAC is shown in Algorithm 2. Based on Algorithms 1 and 2, the overall prioritized data dissemination algorithm, which is IDNC-assisted and admission control enabled, is obtained. And the pseudocode is given in Algorithm 3.Algorithm 2:Network Coding-Aware Admission Control (NCaAC).
(1)
If Ri receives a newly arriving request ri then
(2)
Determine the priority ofri;
(3)
if ri is high priority then
(4)
Admitri and put ri into the high priority service queue;
(5)
else
(6)
Vectorizeri as rvij, the mean vector of VEα as rvα, and the mean vector of VEβ as rvβ;
(7)
Calculatervα and rvβ as described in Section 4.2.1;
(8)
Calculate the distance betweenrvij and rvα, and the distance between rvij and rvβ, respectively;
(9)
Compare the distances
(10)
if distrvij,rvα¯≤distrvij,rvβ¯ then
(11)
Rejectri;
(12)
Send a rejection message to the vehicle;
(13)
else
(14)
if distrvij,rvα¯>distrvij,rvβ¯ then
(15)
Admitri and put ri into the low priority service queue;
(16)
end if
(17)
end if
(18)
end if
(19)
end ifAlgorithm 3:NCaAC enabled prioritized data dissemination for VANETs.
Input: For any vhi belongs to VH, 1≤i≤N
(1)
while vhi dwells in the coverage of Ri do
(2)
Vehiclevhi randomly generates a request ri and sent it to Ri;
(3)
Ri receives ri;
(4)
Ri calls Algorithm 2 to perform admission control;
(5)
Ri calls Algorithm 1 to serve vehicles;
(6)
end while


## 4.2.1. Characteristics Vectorization

As shown in Figure1, at each time slot, there might be multiple vehicles that are requesting the same data item dj from Ri within the transmission coverage. These requests, although they want the same item dj, have different deadlines as they are associated with varied vehicles. Denote the deadline of vehicle vhi for requesting item dj as dlij; define(1)dljmin=min1≤k≤Ndlkj,vhk∈VHdj,where VHdj is the set of vehicles that are requesting dj and dljmin represents the deadline of the most urgent request among all requests that are asking for item dj. Hj=e−dljmin stands for the utility value of all active requests that regard data item dj. To quantify the popularity of dj, define an indicator function Iidj, where Iidj=1 means that vehicle vhi is requesting item dj; otherwise, Iidj=0. The popularity of data item dj thus can be expressed as(2)Pdj=∑vhi∈RCRiIidj,where RCRi denotes the set of vehicles that are within Ri’s coverage.Moreover, in view of the fact that the probability of itemdj being successfully received by all requesting vehicles is strongly correlated with the distance between the requesting vehicles, the aggregation level of requesting vehicles is chosen to evaluate vehicles’ capability of receiving item dj. The degree of polymerization for vehicles that are requesting dj is defined as(3)DPdj=1/VHdj∑vhi∈VHdjxi−xRi2+yi−yRi2−μ2μ,where xi,yi and xRi,yRi are the coordinates of vehicle vhi and RSU Ri, respectively. µ is the average distance from all vehicles requesting dj to RSU Ri, and μ can be calculated as(4)μ=∑vhi∈VHdjxi−xRi2+yi−yRi2VHdj.Meanwhile, it is noticed that the shorter distance between all vehicles that are requestingdj and Ri would help to build more stable communication channels and thus increase the successful ratio of transmission. The distance between the geometric center of all vehicles requesting dj and Ri is a fine indicator to evaluate the transmission success ratio, and it can be calculated as(5)Ldj=xRi−∑vhi∈VHdjxiVHdj2+yRi−∑vhi∈VHdjyiVHdj2.Considering all the above factors, each admitted data request in the service queues can be represented by a vector. For instance, the request ofvhi for dj is expressed as a vector rvij=Hj,Pdj,DPdj,Ldj. For any IDNC-assisted data scheduling algorithm, each vertex in the found maximum weighted clique (MWC) can be represented as a vector, and a vector set VE is formed over the MWC as(6)VE=rvij=Hj,Pdj,DPdj,Ldj,…rvlk=Hk,Pdk,DPdk,Ldk,…1≤i,l≤N;1≤j,k≤M,The mean vector ofVE is denoted as rv¯=H¯,P¯,DP¯,L¯, and rv¯ can be obtained by calculating the average value of the four components separately.


## 4.2.2. Admission Control Decision Process

To provide differentiated service for safety-related and user-related applications, as well as to make better use of limited network resources, the proposed admission control strategy allows all safety-related data requests to enter the network and entitles them to data service provided by the RSU. However, user-related data requests, namely, low-priority requests, have to pass the admissible test imposed by the admission controller before they are welcomed to the service.At any time slot, vehiclevhi generates a data request ri, specifically requesting data item dj. Upon receiving ri, the admission controller in Ri firstly determines the type of ri. Since ri is low priority, it needs to pass the admissible test before further response. Denote the vector set that is established on the MWC before Ri accepts ri as VEα; the mean vector of VEα is rvα¯=Hα¯,Pα¯,DPα¯,Lα¯. Moreover, if ri is admitted into Ri’s service queues, the IDNC graph will update and the MWC found on the graph will change accordingly, resulting in a new vector set VEβ. Denote the mean vector of VEβ as rvβ¯=Hβ¯,Pβ¯,DPβ¯,Lβ¯. The new request ri can be denoted as a data vector rvij=Hj,Pdj,DPdj,Ldj. The distance between rvij and rvα¯ can be calculated as(7)distrvij,rvα¯=Hj−Hα¯2+Pdj−Pdjα¯2+DPdj−DPdjα¯2+Ldj−Ldjα¯2.Similarly, the distance betweenrvij and rvβ¯ can be calculated as(8)distrvij,rvβ¯=Hj−Hβ¯2+Pdj−Pdjβ¯2+DPdj−DPdjβ¯2+Ldj−Ldjβ¯2.Based on the definition of vector similarity, it can be concluded that whendistrvij,rvα¯≤distrvij,rvβ¯, the new request ri is more similar with the mean vector of VEα than it is with the mean vector of VEβ. In other words, the mean vector of the vertices set that is constructed over the updated MWC after accepting the new request ri will drift away from the vector of ri. Thus, if the request is admitted, the probability of it being encoded into the IDNC packet is small. What is worse, the admission of ri could possibly prolong the waiting time of other admitted requests (especially the ones that ask for high-priority data items) and cause network congestion. As a result, in order to ensure the dissemination quality of admitted data requests in the system, the new request is rejected. Contrarily, if distrvij,rvα¯>distrvij,rvβ¯, it indicates that rvij is more similar with the mean vector of VEβ than it is with the mean vector of VEα. In other words, the acceptance of ri will advocate higher probability of being encoded into the IDNC packet and provide more coding opportunities. Accordingly, ri is admitted and put into Ri’s low-priority service queue. After the admission control decision process, Ri adopts the IDNC-assisted data scheduling algorithm to serve vehicles. The pseudocode of the proposed NCaAC is shown in Algorithm 2. Based on Algorithms 1 and 2, the overall prioritized data dissemination algorithm, which is IDNC-assisted and admission control enabled, is obtained. And the pseudocode is given in Algorithm 3.Algorithm 2:Network Coding-Aware Admission Control (NCaAC).
(1)
If Ri receives a newly arriving request ri then
(2)
Determine the priority ofri;
(3)
if ri is high priority then
(4)
Admitri and put ri into the high priority service queue;
(5)
else
(6)
Vectorizeri as rvij, the mean vector of VEα as rvα, and the mean vector of VEβ as rvβ;
(7)
Calculatervα and rvβ as described in Section 4.2.1;
(8)
Calculate the distance betweenrvij and rvα, and the distance between rvij and rvβ, respectively;
(9)
Compare the distances
(10)
if distrvij,rvα¯≤distrvij,rvβ¯ then
(11)
Rejectri;
(12)
Send a rejection message to the vehicle;
(13)
else
(14)
if distrvij,rvα¯>distrvij,rvβ¯ then
(15)
Admitri and put ri into the low priority service queue;
(16)
end if
(17)
end if
(18)
end if
(19)
end ifAlgorithm 3:NCaAC enabled prioritized data dissemination for VANETs.
Input: For any vhi belongs to VH, 1≤i≤N
(1)
while vhi dwells in the coverage of Ri do
(2)
Vehiclevhi randomly generates a request ri and sent it to Ri;
(3)
Ri receives ri;
(4)
Ri calls Algorithm 2 to perform admission control;
(5)
Ri calls Algorithm 1 to serve vehicles;
(6)
end while


## 5. Performance Evaluation

In this section, we evaluate the performance of the proposed NCaAC strategy. The classical time-sensitive data scheduling algorithms, namely, Earliest Deadline First (EDF) and Slack time Inverse Number of pending requests (SIN) [29], are chosen as the comparison algorithms. In addition, the Priority-based VANETs Data Dissemination (PVDD) algorithm [25], which is the latest time-sensitive data dissemination algorithm for VANETs, is selected for evaluation.As the name suggests, EDF algorithm schedules data item that has the shortest deadline at each transmission. Cooperating with IDNC, EDF assigns the deadline of each request as the weight of each corresponding vertex in the IDNC graph. Nonetheless, SIN considers not only the deadline of each request, but also the popularity of data items. Therefore, the item that has the minimumslack/num value is chosen to be multicasted to vehicles, where slack refers to the duration from current time to the most urgent pending request’s deadline and num is the number of pending requests. Consequently, SIN assigns the slack/num value of each request as the weight of the vertex accordingly in the IDNC graph. The weight assignment of vertex in PVDD is more complex. To provide both satisfying and differentiated service quality for various kinds of VANETs applications, PVDD employs a fine designed utility calculation process which considers multiple parameters including data requirements of vehicles, vehicles densities, speeds, and locations, to quantify the rewarding that the system can get through multicasting the selected data items. The weight of each vertex in PVDD is determined as the calculated utility value. Once the weights of vertices are determined, the multicast IDNC packet can be generated by finding the maximum weighted clique over the IDNC graph.Consider the system model in Figure1. RSUs are set along the traffic lanes equidistantly. Within each RSU’s communication radius, vehicles are randomly distributed and running at constant speeds. At any time slot, vehicles can generate and send out time-sensitive data requests for safety-related/user-related applications. Each request has a deadline after which the request expires and the data receiving becomes useless. The deadline of each request is randomly generated from a uniform distribution ULmin,Lmax. In the meantime, a request will become invalid once the corresponding vehicle leaves the coverage of the RSU. The arrival time interval of each data request of a vehicle subjects to an exponential distribution with parameter λ, and the request data item is determined by the Zipf distribution with skewness θ, 0≤θ≤1. With smaller θ, the access frequency of one data item among all data items in the database is low. Particularly, if θ=0, the distribution becomes the uniform distribution, while the Zipf distribution becomes extremely skewed as θ increases to 1. The simulation parameters are shown in Table 1.Table 1
System parameter settings.
Name
Range of values
Value
x
R
i
−
1500,1500 m
400
y
R
i
−
50,50 m
11.25
% of high-priority data
0,1
0.5
% of low-priority data
0,1
0.5
Number of bidirectional lanes
4,10
6
Width of single lane
3.5
,
3.75 m
3.75
Speed
60,120 km/h
60,120
r
100,1000 m
400
M
Positive integer
300
λ
Positive integer
12
ω
1
Positive integer
20
ω
2
Positive integer
1
L
min
Positive integer
5
L
max
Positive integer
15
θ
0∼1
0.2The performance metrics used to evaluate the algorithms are defined as follows:(1)
Average download delay: defineti as the download delay of request ri (the time elapses from the moment ri is sent out to the moment ri is received by the same vehicle); if ri∈Ah, where Ah is the set of satisfied high-priority requests, then the average download delay of high-priority data requests is calculated as ∑ri∈Ahti/Ah. Similarly, the average download delay of low-priority data request is ∑rj∈Altj/Al, where Al is the set of satisfied low-priority data requests. The overall average download delay thus is ∑rk∈Ah∪Altk/Ah∪Al. The average download delay is a sensitive indicator that reflects RSUs’ responding capability. Obviously, shorter average download delay means quicker response and better service experience.(2)
Deadline miss ratio: it is the ratio of expired high (low) priority data requests to the total number of admitted high (low) priority requests. Of course, the deadline miss ratio is expected to be as small as possible so as to minimize the number of expired requests and to serve as many vehicles’ requests as possible to enhance the overall satisfaction of end users.(3)
Download success ratio: it is the ratio of the number of successfully received high (low) priority data requests to the total number of admitted high (low) priority requests.For the chosen IDNC-assisted algorithms, we compare the performance metrics of them with and without admission control, to verify the validity and efficiency of the proposed admission control strategy. The original IDNC-assisted algorithms without admission control are labeled as EDF, SIN, and PVDD, respectively. The algorithms with network coding-aware admission control are denoted as EDF_NCaAC, SIN_NCaAC, and PVDD_NCaAC. The results are obtained when the system is in a steady state and all data points are based on the average of over 5000 simulation runs.


### 5.1. Average Download Delay

Figure3 depicts the average download delay of EDF and EDF_NCaAC for high-priority data, low-priority data, and total data requests. It is clearly seen that, with the aid of the proposed NCaAC, not only the average download delay of high-priority data requests is reduced, but also that of low-priority data requests is shortened. As a result, the overall average download delay of the system is improved. Similar conclusions can be drawn for SIN and PVDD algorithms from Figures 4 and 5. Based on Figures 3–5, it is justified that the proposed NCaAC is good for enabling the system to respond and to serve the data requests of vehicles promptly.Figure 3
Average download delay for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 4
Average download delay for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 5
Average download delay for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


### 5.2. Deadline Miss Ratio

Figures6–8 give the deadline miss ratios for different priorities requests and overall requests under multiple comparison algorithms. It is seen that, with the increasing number of vehicles, the deadline miss ratio increases with all algorithms. In addition, with the help of the proposed NCaAC strategy, EDF_NAaAC and SIN_NCaAC are able to achieve smaller deadline miss ratios for any kind of data requests, thus shortening the overall deadline miss ratios. In Figure 8(a), the improvement of NCaAC for high-priority data requests on deadline miss ratio is faint, for that PVDD is a discriminating algorithm which inherently has a preference for high-priority data requests. In spite of this, the effectiveness of NCaAC is approved in Figures 8(b) and 8(c) in that the deadline miss ratios for low-priority and overall data requests are reduced signally by cooperating NCaAC into the original PVDD algorithm.Figure 6
Deadline miss ratio for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 7
Deadline miss ratio for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 8
Deadline miss ratio for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


### 5.3. Download Success Ratio

Figures9–11 give the download success ratios for different priorities requests and overall requests under multiple comparison algorithms. The density of vehicles has a great impact on the download success ratio for all algorithms. It can be seen that, with the increasing of vehicles, the system load becomes heavier and the download success ratio decreases. Fortunately, by introducing the NCaAC into the network, the download success ratios of high/low-priority data requests with all comparison algorithms are improved with noticeable increment, which further validates the effectiveness and efficiency of the proposed admission control strategy.Figure 9
Download success ratio for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 10
Download success ratio for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 11
Download success ratio for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


## 5.1. Average Download Delay

Figure3 depicts the average download delay of EDF and EDF_NCaAC for high-priority data, low-priority data, and total data requests. It is clearly seen that, with the aid of the proposed NCaAC, not only the average download delay of high-priority data requests is reduced, but also that of low-priority data requests is shortened. As a result, the overall average download delay of the system is improved. Similar conclusions can be drawn for SIN and PVDD algorithms from Figures 4 and 5. Based on Figures 3–5, it is justified that the proposed NCaAC is good for enabling the system to respond and to serve the data requests of vehicles promptly.Figure 3
Average download delay for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 4
Average download delay for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 5
Average download delay for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


## 5.2. Deadline Miss Ratio

Figures6–8 give the deadline miss ratios for different priorities requests and overall requests under multiple comparison algorithms. It is seen that, with the increasing number of vehicles, the deadline miss ratio increases with all algorithms. In addition, with the help of the proposed NCaAC strategy, EDF_NAaAC and SIN_NCaAC are able to achieve smaller deadline miss ratios for any kind of data requests, thus shortening the overall deadline miss ratios. In Figure 8(a), the improvement of NCaAC for high-priority data requests on deadline miss ratio is faint, for that PVDD is a discriminating algorithm which inherently has a preference for high-priority data requests. In spite of this, the effectiveness of NCaAC is approved in Figures 8(b) and 8(c) in that the deadline miss ratios for low-priority and overall data requests are reduced signally by cooperating NCaAC into the original PVDD algorithm.Figure 6
Deadline miss ratio for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 7
Deadline miss ratio for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 8
Deadline miss ratio for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


## 5.3. Download Success Ratio

Figures9–11 give the download success ratios for different priorities requests and overall requests under multiple comparison algorithms. The density of vehicles has a great impact on the download success ratio for all algorithms. It can be seen that, with the increasing of vehicles, the system load becomes heavier and the download success ratio decreases. Fortunately, by introducing the NCaAC into the network, the download success ratios of high/low-priority data requests with all comparison algorithms are improved with noticeable increment, which further validates the effectiveness and efficiency of the proposed admission control strategy.Figure 9
Download success ratio for EDF and EDF_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 10
Download success ratio for SIN and SIN_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)Figure 11
Download success ratio for PVDD and PVDD_NCaAC with different vehicles number: (a) high-priority data and (b) low-priority data and (c) total data.
(a)
(b)
(c)


## 6. Conclusion

The utilization of network coding technology for data dissemination in VANETs becomes more and more popular since it has been proved that network coding is efficient for enlarging network transmission throughput and reducing transmission delay. By integrating the IDNC technology into the data dissemination process, the decoding delay derived from traditional network coding methods can be minimized, thus further reducing the overall delay. However, the QoS of applications degrades with the increasing number of requests, and the whole system performance can be threatened by a burst of newly generated requests. To resolve this issue, this paper focuses on improving the data dissemination performance in VANETs through efficient admission control strategy. Moreover, the priority of disseminated data is a major concern in this paper in that differentiated admission control policies are designed carefully for safety-related and user-related data applications, so that the proposed NCaAC is more adaptable and can better fit in practical environments. The proposed NCaAC strategy adopts the network coding gain as the admission criterion to determine whether a request can be accepted into the system. Therefore, it works well with any IDNC-assisted data scheduling algorithm. The performance improvement derived from the NCaAC is sufficiently investigated through extensive simulations. From the simulation results, it is confirmed that the proposed NCaAC strategy is capable of balancing system load under different environments, reducing transmission delay and increasing transmission success probabilities for prioritized data applications, as well as for the overall data dissemination in VANETs.



---

*Source: 6758536-2020-02-28.xml*