Instantly decodable network coding–assisted data dissemination for prioritized services in vehicular ad hoc networks

Abstract

Safety-related and user-related applications are two main kinds of services provided in vehicular ad hoc networks. Safety-related applications have great impact on vehicles and people who participate in the transportation. The quality requirements for safety data dissemination are strictly high, since this kind of service is usually concerned with the most important safety events in vehicular ad hoc networks. Meanwhile, user-related applications need to fulfill the varied demands for value-added services of consumers in vehicular ad hoc networks to retain existing consumers and to attract new ones. However, the unpleasant transmission environment of vehicular ad hoc networks, such as drastically changing network topology and unstable communication links, degrades the system performance and hinders the development of vehicular ad hoc networks. To tackle these issues, this article proposes a novel algorithm which prioritizes data based on their service purposes and schedules the most rewarding data item based on utility values calculated with multiple parameters, including data requirements of vehicles, vehicles density, speeds, and locations. Moreover, the algorithm applies instantly decodable network coding technique on the scheduled data to maximize the multicast throughput. Simulation results approve the performance advancement of the proposed algorithm in download delay, deadline miss ratio, and download success ratio for high- and low-priority data disseminations.

Keywords

Vehicular ad hoc networks vehicle-to-road side unit communications instantly decodable network coding differential service data dissemination

Introduction

Owing to the rapid development of wireless communication and mechanical automation technologies, vehicular ad hoc networks (VANETs) are introduced into modern daily life as a special case of the traditional mobile ad hoc networks (MANETs) for vehicular wireless data interaction.¹ In VANETs, small communication networks are formed between vehicles and roadside communication units, as well as other facilities. Data can be transmitted and exchanged not only between vehicles, but also between vehicles and road side units (RSUs).² Depending on the adopted communication modes, which are vehicle-to-vehicle (V2V) and vehicle-to-road side unit (V2R), VANETs provide two kinds of service applications. One is the safety-related service, which aims to provide transportation safety for all parties involving in the transportation. The other is user-related service, which provides value-added service for users, such as meeting the entertainment needs of passengers.

In VANETs, V2V communications refer to the communications between vehicles through single or multi hop, which are suitable for the congested and slow urban road traffic environment. In the highway environment, however, the high-speed movement of vehicles leads to rapid change of network topology. At the same time, locations and speeds of vehicles change frequently, which seriously affect the data dissemination performance.³ In order to overcome these problems in V2V communications, vehicles are enabled to communicate with RSUs to make information transmission more efficiently. In V2R communications, an RSU is usually directly connected to the backbone network. An RSU can exchange or synchronize information easily and quickly through the backbone network. Vehicles and RSUs only need one jump to achieve fast and reliable data interaction, which can ensure the high efficiency of data transmission. Compared with V2V communications, V2R communications have higher reliability and timeliness in highway environment. In addition, the deployment of RSUs can be realized through existing facilities along the highway, which reduces the cost of deployment to a certain extent, making it more suitable for carrying safety-related and user-related applications.

Clearly, reliable and well implementation of the safety-related applications in VANETs can significantly reduce the number of traffic accidents. For example, when a car is running on a highway, the driver usually only has a short time to judge and to react to the action of the vehicles ahead. If a traffic accident happens, vehicles which are running toward the accident spot often collide with each other if the drivers cannot react to the emergency quickly. VANETs can use the safety-related applications to forward accident alert message to all vehicles within the scope, prompting drivers to respond as soon as possible, so as to avoid the occurrence of continuous collisions. In addition, the safety-related applications can also provide real-time traffic report and navigation information for drivers, so that drivers can make convenient driving plans in advance and ensure driving safety.⁴ Besides safety, value-added services are also indispensable. The user-related applications provided in VANETs can meet personal requirements of passengers and keep them good company on the road. Meanwhile, network operators or related service providers can also publish commercial advertisements to vehicles through VANETs, which can not only provide convenience for passengers but also improve the efficiency of advertising.⁵ The time effectiveness and accuracy of data transmission over VANETs are the main factors that affect the provision of safety-related and user-related service applications. Especially, the effect of safety-related applications depend heavily on whether safety-related information can be transmitted to the application side in time. For safety-related applications, alarms that arrive after a rear-end accident are meaningless! For user-related applications, although the requirement of data transmission delay is less stringent than that of safety-related applications. The large waiting time before one can access the Internet and the long download delay of peer-to-peer (P2P) applications will seriously affect the quality of experience (QoE) and even make users lose interest and quit the application.⁶ Therefore, the performance of data dissemination for safety- and user-related applications in VANETs, especially the data download delay, is the key problem affecting the employment and popularization of VANETs.

This article focuses on the optimization of data dissemination delay of V2R communications in highway environment, especially on the data multicast of two main kinds of application services carried by VANETs. Using network coding technology, as well as integrating data priority and vehicle driving characteristics, an effective coding-based scheduling algorithm is designed to reduce deadline miss ratio, download delay, and improve the overall system performance. The main contribution of this work can be summarized as follows:

We explicitly divide the most commonly seen application services in VANETs into two kinds, namely safety related and user related. The two kinds of application data are prioritized through proper weight assignment. The importance of safety-related data for transportation safety in VANETs is depicted by giving higher weight to safety-related data than that of user-related data.

We design an efficient utility-based weighting scheme, which not only respects the innate different importance of safety-related and user-related data items but also considers various factors that have influence on the data dissemination performance, and the quality of service (QoS) eventually, such as the direct distance between a requesting vehicle and the serving RSU, the time a requesting vehicle dwells in the coverage of an RSU, and vehicles’ density and data popularity.

We improve the instantly decodable network coding (IDNC) technology, so that it supports V2R communications better. The enhanced IDNC approach complies with the prioritized data characteristic of safety-related data and densifies coding opportunities among all kinds of data items so that more vehicles get served in each transmission and the download delay of both safety-related and user-related data is reduced.

Extensive simulation are executed to compare a variety of non-NC and NC-based data dissemination strategies in VANETs, including the classical earliest deadline first (EDF), slack time inverse number (SIN) of pending requests, and retransmission with instantly decodable network coding (IDRT) algorithms. Simulation results are provided to justify the effectiveness and efficiency of the proposed method for disseminating prioritized data in VANETs.

The rest of this work is organized as follows. We give a summary on the research of data dissemination in VANETs and the application of network coding technology on VANETs data multicast in section “Related Works.” Section “System Model” explains the concerned highway V2R data dissemination system in details. Based on the given system model, we propose the priority-based VANETs data dissemination (PVDD) method in the following section. The performance of the proposed algorithm is evaluated through extensive simulations, and the results are depicted and discussed thoroughly in the last section.

Related works

Data dissemination in VANETs

Focusing on the two typical communication modes in VANETs, researchers have proposed a variety of different VANETs data distribution methods for data transmission of different application types. In V2V communications, Tian et al.⁷ proposed the traffic adaptive data propagation (TrAD) protocol without infrastructure scheme to constrain the broadcast storm problem and to improve the transmission reliability. Lin et al.⁸ presented a moving-zone-based architecture and a corresponding routing protocol for message dissemination in VANETs. By using V2V communications only, this approach reduces communication overhead and increases message delivery rates. Ravi et al.⁹ designed a stochastic network optimization method for data dissemination with multi-hop routing in V2V communications. Although this method has high stability, the transmission of data is not flexible and the system utilization is relatively low. In view of the importance of highly efficient transmission for emergency data in VANETs, Ucar et al.¹⁰ proposed a hybrid architecture, namely VMaSC-LTE, combining IEEE 802.11p–based multi-hop clustering and the fourth-generation (4G) cellular system, with the goal of achieving a high data packet delivery ratio (DPDR) and low delay while keeping the usage of the cellular architecture at a minimum level. Bi et al.¹¹ presented a multi-hop broadcast protocol to reduce the transmission delay of emergency messages and message redundancy. In order to meet the priority transmission requirements of safety data in VANETs, a forwarding algorithm based on data priority and vehicle density is proposed by Wang and Huang¹² which effectively suppresses broadcast storms and improves the transmission rate of emergency information. However, due to the characteristics of V2V communications, these data dissemination methods have to go through multi hops to transmit data to the designated clients, which greatly increases the data transmission delay, and the time sensitiveness of safety-related information cannot be reflected.

In contrast, V2R communications usually require one hop to transmit data to the receiving vehicles, which reduces the times of data forwarding, and the transmission efficiency is better than that of V2V communications. However, due to the high-speed movement of vehicles in the highway environment, the V2R communications links are unstable, which greatly shorten the time of vehicles within the RSU communication coverage, and it is difficult to ensure the timely and reliable transmission of information for safety-related applications. To solve this problem, Tiennoy and Saivichit¹³ proposed using a distributed RSU for the data dissemination in VANETs with the named data architecture. This method can improve the network connectivity and data dissemination in mobile environments. However, if there are too many data requests, it is easy to cause data congestion, and safety-related information cannot be sent effectively. In order to overcome the intermittent data delivery service of RSUs that derives from the limited communication coverage of RSUs, Cho and Ahn¹⁴ proposed the backup route mechanism in preparation of route disconnection from the serving RSU, as well as the handover mechanism between two neighboring RSUs, aiming to enhance the data delivery performance in the vehicular communication environment where RSUs are sparsely placed. Chen et al.¹⁵ proposed a method for adjusting the data transmission rate according to the number of periphery APs to solve the problem of continuity and reliability, which is caused by frequent hand-off with base station due to high mobility of vehicles. Chen et al.¹⁶ proposed a cooperative communication strategy for vehicular networks with a finite vehicular density by utilizing V2R communications, V2V communications, mobility of vehicles, and cooperations among vehicles and infrastructure to improve the throughput.

In summary, the existing V2R data dissemination schemes seldom distinguish data according to different application services. However, due to the different uses of information carried by safety-related applications and user-related applications, the quality requirements of transmissions are also different. The transmission schemes that ignore such varied characteristics and differences that exist in VANETs service applications obviously cannot meet the quality of service requirements of the two kinds of applications, which will inevitably lead to the degradation of data transmission performance in VANETs.

Data dissemination in VANETs based on network coding technology

Network coding technology integrates traditional routing and coding technologies and is mainly used in multicast networks. Applying network coding to VANETs can effectively improve network performance, reduce network redundancy, and reduce latency.¹⁷ In order to further improve the reliability and real-time performance of V2R communications, researchers try to introduce network coding technology into data dissemination in VANETs. Md. Nawaz Ali et al.¹⁸ proposed an approach to apply network coding in VANETs so that vehicles do not need to upload their cache information to the server. Network coding technology is used to improve the broadcast performance of RSUs in terms of minimizing deadline miss ratio of vehicles’ requests and reducing required response time of serving requests. Huang et al.¹⁹ proposed a method for transmitting business messages in VANETs by using network coding technology. When forwarding nodes receive messages from different source nodes, they can choose to wait for coding opportunities to save bandwidth, or to forward directly to reduce delay. Christian et al.²⁰ claimed that multihoming and network coding can be jointly used to provide high bandwidth and reliability to services in VANETs to reduce packet losses resulted by poor wireless signal quality and thus improving the final QoS. Li and Wang²¹ used random linear network coding technology to encode the content to be transmitted. The encoded contents are then randomly cached at each mobile vehicle node in an RSU’s coverage area. Although this method improves the channel utilization and data distribution performance of the system, large delay is introduced in the decoding on the receivers’ sides. In order to shorten the decoding delay as much as possible, Wang and Yin²² used the IDNC technology to improve the data dissemination performance in VANETs. Using this technology, the forwarding nodes encode and forward data packets under certain coding rules. Upon receiving a coded packet, a receiver can decode the wanted packet instantly using the coded packet and its cached packets together, thus shorten the waiting time for receivers to utilize the wanted packets and enhance the data transmission reliability of VANETs. The proposed algorithm helps the system to decide whether to retransmit packets by calculating the utility value of the data packets for the system, based on real-time information of status of vehicles. If retransmitting the data packets can improve the system performance, the retransmission will begin immediately. The selected relay vehicle nodes use real-time network coding technology to encode and retransmit the data packets, through which the efficiency of data retransmission can be enhanced effectively. Nevertheless, this work only regards the data carried by VANETs as one kind of type and cannot distinguish specific data types according to different service applications. Therefore, the designed data transmission scheme is only applicable to the transmission of ordinary data and cannot meet the specific transmission requirements of safety-related application data and user-related application data.

System model

Based on the data characteristics, we prioritize the data transmitted in VANETs into two categories: high priority for the safety-related application data and low priority for the user-related application data. Furthermore, we propose a network coding-based V2R data dissemination scheme that ensures the timely transmission of safety-related application data while taking into account the transmission efficiency of user-related application data.

The system model is shown in Figure 1. In the highway scenario, RSUs are senders of safety-related messages and user-related messages, and vehicles within RSUs’ coverage are receivers. Each RSU is deployed at fixed intervals along the traffic lanes. The radius of each RSU’s signal coverage is r. RSUs interact with each other through wired connections and are connected directly with the backbone network. The backbone network is connected with the central network through the Internet. When a vehicle enters an RSU’s signal coverage, the RSU provides the wireless access port for the vehicle, and the client vehicle can interact data with the RSU, including safety-related information and value-added business information.

Figure 1.

System model.

Assuming that every vehicle is equipped with global positioning system (GPS) devices, so that it can obtain real-time location information of its adjacent vehicles. Every vehicle is equipped with an on-board unit (OBU, also known as wireless transceiver), and vehicles receive peripheral messages regularly. Both type of nodes in the system, namely RSUs and OBUs are dedicated short range communications (DSRC) devices which work in half-duplex mode, that is, it is not allowed to transmit and receive packets at the same time. Radio works in multiple channels. Denote the M data items stored in one RSU as $D = (d_{1}, d_{2}, \dots, d_{M})$ , N vehicles in the RSU’s coverage are recorded as $VH = (v_{1}, v_{2}, \dots, v_{N})$ , the speed of vehicle i (denoted as $v_{i}$ ) is marked as $p_{i}$ .

When vehicle $v_{i}$ enters RSU $R_{i}$ ’s coverage, $v_{i}$ sends out a request to $R_{i}$ for specific data item which can be used according to its own need. in addtion, $v_{i}$ ’s identification code, location, and speed information are sent together with the specified data item requirement in the request. The data request of $v_{i}$ is recorded as $A_{i} = {Q_{i} | ID, location, velocity}$ , where $Q_{i}$ represents the specific data requested and ID represents $v_{i}$ ’s identification code. When $R_{i}$ receives $A_{i}$ , it first identifies the priority of the requested data item, it then confirms the location and speed of $v_{i}$ , and checks whether $v_{i}$ is within the range of its signal coverage. If $v_{i}$ is within $R_{i}$ ’s signal coverage, it accepts the request and gets ready to respond to the request.

Once $R_{i}$ decides to accept the request, it sorts the request into two different priority queues that it maintains. Safety-related service request is put into the high-priority queue, while user-related service request goes into the low-priority queue. At each transmission, $R_{i}$ ranks the data items that need to be sent according to the requests sent by the vehicles and the running status of the vehicles, and multicasts scheduled data packets to the targeted vehicles using network coding technology. After receiving the multicast encoded packet, each vehicle decodes the network-coded packet with its cached data items. If the requested data item can be decoded from the encoded packet, vehicles will feedback $R_{i}$ with a success message, otherwise a failure message will be sent back to $R_{i}$ . $R_{i}$ decides to remove the request from the service queue or continue to respond to the request based on the success/failure message. The process will go on until all vehicles run out of $R_{i}$ ’s coverage. The YES/NO feedback message is set to be 1-bit and is piggybacked with system signalings to be sent through the control channel, so that the overall 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 $R_{i}$ are occurred through the service channels.

PVDD method

When an RSU receives vehicles’ requests, it calculates and evaluates how to schedule data packets for encoded multicast in order to reduce download delay, to ensure the transmission speed of high-priority data and to improve the transmission efficiency of the whole system. In this section, we propose a data dissemination algorithm that prioritizes data of safety-related service applications and differentiates data of different priority levels for transmission. In addition, it applies network coding technology to the data scheduling process to improve the transmission efficiency of safety-related service data, while considering the transmission quality of user-related service data.

The algorithm consists of three steps:

Priority assignment: once an RSU accepts a data request from a vehicle, it classifies the request into one service queue based on the request’s priority determined by whether it is safety-related data request or user-related data request.

Utility calculation: upon each multicast, the RSU calculates a utility value for each data item in the service queues based on the requests’ priority and the running status of vehicles accordingly. The utility value of each data item reflects the reward the system can get if the RSU decides to multicast the according data item.

Network-coded multicast: after the utility calculation, the RSU finds out the most rewarding data item that is to be multicasted, it further applies network coding technology on the scheduled item, along with other data items as long as the decoding condition is met, so as to maximize the throughput and minimize the transmission delay.

Priority assignment

When an RSU receives a data request, it first determines the priority of the request according to the specific data item of the request. The requested data item with different priority has different weight values. Considering the two different data service kinds in VANETs, the data priority can be classified as follows:

Safety-related service data have great influence on driving safety, traffic control and management, which requires stringent delay and reliability. This kind of information is thus considered as high priority and assigned the weight $ω_{1}$ .

User-related service data support applications that make drivers and passengers comfort during the ride. These data often are used for multimedia entertainment, commercial advertisement, weather or tourist inquiry, and so on. Comparing with the safety-related service applications, this kind of information has less strict requirement for transmission delay. This kind of data items is divided into low priority and assigned weight $ω_{2}$ .

Obviously, the weight of safety-related service data is always greater than that of user-related service data, which means $ω_{1} > ω_{2}$ .

Utility calculation

In order to distribute the requested data items to the target vehicles as soon as possible, how an RSU will respond to the multiple requests it receives at hand is critical. Since a vehicle can only receive data when it is within the RSU’s coverage, the request of one vehicle will become invalid if this vehicle runs out of the RSU’s coverage before it has received the request data. In view of this, when a vehicle generates a request for desired data items, this request has a deadline inherently, which is the time that the vehicle can stay within the RSU’s coverage. The deadline of a request is the time elapses from the moment a vehicle sends out the request to the moment that the vehicle runs out of the RSU’s coverage. Denoting the request of vehicle $v_{i}$ as $Q_{i}$ , $Q_{i} = {d l_{i}, d_{i} \in D}$ , where $d l_{i}$ represents the deadline of request $Q_{i}$ , and $d_{i} \in D$ represents the specific data item that $v_{i}$ wants to receive. As shown in Figure 2, RSUs are deployed equidistantly along the highway lanes, the coordinates of one RSU are marked as $(x_{R}, y_{R})$ , each RSU’s communication radius is set as r, and vehicles $v_{i}$ and $v_{j}$ are within RSU’s coverage, with coordinates $(x_{i}, y_{i})$ and $(x_{j}, y_{j})$ , $1 \leq i, j \leq N$ , respectively. $v_{i}$ and $v_{j}$ are running from east to west. Suppose $v_{i}$ sends out a request $Q_{i}$ to the RSU, from location $(x_{i}, y_{i})$ , the deadline $d l_{i}$ of request $Q_{i}$ is calculated as follows (r is the coverage radius of RSU)

d l_{i} = \frac{(x_{i} - x_{R}) + r * \sin (\arccos \frac{y_{i}}{r})}{p_{i}}

(1)

where $p_{i}$ is the velocity of vehicle $v_{i}$ . Similarly, if $v_{j}$ sends out a request from location $(x_{j}, y_{j})$ , the deadline $d l_{j}$ of request $Q_{j}$ of vehicle $v_{j}$ is calculated as follows

d l_{j} = \frac{\frac{y_{j}}{\tan (\arcsin \frac{y_{j}}{r})} - (x_{R} - x_{j})}{p_{j}}

(2)

and $p_{j}$ is the velocity of the vehicle $v_{j}$ .

Figure 2.

An example for utility calculation.

In one RSU’s coverage, there are usually several high-speed vehicles at the same time. Data requests from these vehicles may overlap, that is, more than one vehicle request the same data item. When multiple vehicles request the same data item, the RSU schedules to multicast this popular data item, since it has the potential to satisfy multiple requests at one time. Furthermore, the shorter distance between the RSU and the requesting vehicle is, the more likely that the multicast data item can be successfully received. Therefore, when an RSU makes scheduling decisions, it is necessary to consider the specific data items requested by the vehicles and also the ability of the requesting vehicles to receive these data items.

In order to evaluate the ability of vehicles to receive data items, vehicle aggregation degree is introduced as a quantization characteristic of inter-vehicle channel conditions. Denote the set of vehicles that are requesting the same data item $d_{i}$ as $VH (d_{i})$ , vehicle aggregation degree ED is given by

ED = \frac{\sqrt{\frac{1}{| VH (d_{i}) |} \sum_{v_{i} \in VH (d_{i})} {(s_{R_v_{i}} - μ)}^{2}}}{μ}

(3)

where $s_{R_v_{i}}$ represents the distance between vehicle $v_{i}$ and RSU R, and $s_{R_v_{i}}$ can be calculated as follows

S_{R_v_{i}} = \sqrt{{(x_{R} - x_{i})}^{2} + {(y_{R} - y_{i})}^{2}}

(4)

$μ$ is the average distance from all vehicles requesting data $d_{i}$ , and $μ$ can be calculated as follows

μ = \frac{\sum_{v_{i} \in VH (d_{i})} S_{R_v_{i}}}{| VH (d_{i}) |}

(5)

By the definition of aggregation degree, the smaller the value of ED gets, the more aggregated the vehicles are, and the shorter distances between vehicles requesting, the same the data item are. In other words, the shorter distances between vehicles and RSU represent the more stable communication channels and lower bit error ratio, which are desired characteristics in VANETs multicast. Therefore, the influence of transmission distance between aggregated vehicles and RSU on successfully receiving data items is elaborated carefully. Denote the distance between the geometric center of all vehicles requesting data $d_{i}$ and the serving RSU as L

L = \sqrt{{(x_{R} - x_{0})}^{2} + {(y_{R} - y_{0})}^{2}}

(6)

where $(x_{R}, y_{R})$ is the coordinate of the serving RSU, and $(x_{0}, y_{0})$ is the coordinate of geometric center of all vehicles requesting data $d_{i}$ . It can be easily obtained that $x_{0} = (\sum_{v_{i} \in V H (d_{i})} (x_{i})) / | V H (d_{i}) |$ , and $y_{0} = (\sum_{v_{i} \in VH (d_{i})} (y_{i})) /$ $| VH (d_{i}) |$ , while $(x_{i}, y_{i})$ is the coordinate of vehicle $v_{i}$ . The smaller the L is, the closer the aggregated vehicles get to the serving RSU, and the higher probability that the requesting vehicles will receive the required data successfully.

Next, define a sign function as $I_{j} (d_{i})$ , $I_{j} (d_{i}) = 1$ if vehicle $v_{j}$ requests data item $d_{i}$ , and $I_{j} (d_{i}) = 0$ , otherwise. All vehicles that request the same data item $d_{i}$ within RSU’s coverage can be expressed as

h (d_{i}) = \sum_{(x_{j}, y_{j}) \in RSU' scoverage} I_{j} (d_{i})

(7)

Further assume that for all requesting vehicles, each vehicle has a request expiration time. Denote the shortest expiration time of all requests as $d l_{\min}$ , and $K = e^{- d l_{\min}}$ represents the utility value of the minimum expiration time.

On one hand, when the serving RSU schedules the multicast data item, the popularity of each data item should be taken into account, which is the times that a same data item is requested by multiple vehicles. It should also consider the request deadline, and the data priority and other properties have influence on the multicast efficiency. On the other hand, the distance between the requesting vehicle and the serving RSU, as well as the distance between aggregating vehicles, shall be considered thoroughly, since these are the factors that affect the transmission reliability heavily. Combining all the above factors, the utility value for the serving RSU to multicast data item $d_{i}$ can be calculated as

U (d_{i}) = \frac{(h (d_{i}) + K) * ω_{k}}{ED * L}

(8)

where $ω_{k}$ represents the weight corresponding to the priority of $d_{i}$ . The serving RSU calculates the utility value of all data items in the transmission queues and selects the item with the largest utility value for multicasting.

Network coded multicast

It has been proved that network coding technology can be used for maximizing network throughput and reducing transmission delay. After deciding the most rewarding data item to be multicast based on the calculated utility values, IDNC technology is applied to make full use of the channel resources in VANETs and to further improve the transmission performance of V2R communication.

First, an IDNC graph model $G (V, E)$ is constructed based on the data requests. Assuming vehicle $v_{i}$ requests data item $d_{j}$ for the serving RSU, this case is recorded as a vertex $a_{ij}$ , and $a_{ij} \in V$ , where V is the vertices set of graph G. Similarly, vehicle $v_{l}$ requests for data item $d_{k}$ , and it is recorded as vertex $a_{lk} \in V$ . Each request of a vehicle is recorded as a vertex in the graph, and the weight of each vertex is assigned as the calculated utility value. An edge between any two vertices $a_{ij}$ and $a_{lk}$ can be drawn if and only if any of the following conditions holds:

Condition 1: $j = k$ , which means vehicle $v_{i}$ , and $v_{l}$ request the same data item;

Condition 2: item $d_{j}$ requested by vehicle $v_{i}$ is cached at vehicle $v_{l}$ , and item $d_{k}$ requested by vehicle $v_{l}$ is cached by vehicle $v_{i}$ .

When any of the above conditions is met between vertices $a_{ij}$ and $a_{lk}$ , they are connected by an edge $e_{jk}$ . Obviously, edge $e_{jk}$ actually represents the network coding opportunity between item $d_{j}$ and $d_{k}$ . When there is an edge between two vertices, the data items which are identified by the vertices can be coded. If XOR encoding is adopted, the encoded packet is instantly decodable at the receivers. Hence, by searching the maximum weighted clique in the constructed IDNC graph and by encoding the data items corresponding to the vertices of the maximum weighted clique, the coded data packet that can provide the maximum system gain for RSU multicast can be obtained. The encoded packet is multicasted to all vehicles within the serving RSU’s coverage. After receiving the network coded packet, each vehicle decodes the requested data using its own cached data, so as to get satisfied and feedbacks a successful acknowledgment to the serving RSU. If a vehicle cannot decode out its requested data item from the encoded packet, it discards the packet immediately and feedbacks a failure acknowledgment message to the serving RSU. The serving RSU then updates the IDNC graph according to the feedbacks, removing the corresponding vertices of the satisfied data requests, clearing the invalid vertices whose requests become expired and redrawing the edges between updated vertices. The process will continue until all vertices in the updated IDNC graph have been investigated and responded. The pseudocode of the proposed PVDD algorithm is given in Algorithm 1.

Algorithm 1. Priority-based VANETs data dissemination
Require:
1: Initialize (VH, D, r, $ω_{k}$ , $(x_{R}, y_{R})$ , $(x_{i}, y_{i})$ , $p_{i}$ )
2: while ( $t \leq T_{total}$ ) do
3: for $i = 1 : N$ do
4: if ( $v_{i}$ sends data request $A_{i}$ to RSU) then
5: RSU identifies the priority of $A_{i}$ , assigns $ω_{i}$ as the weight of $A_{i}$ ’s priority, and stores $A_{i}$ in the serving queue.
6: end if
7: end for
8: for $i = 1 : M$ do
9: if $d_{i}$ is in the serving queue then
10: Calculate $d_{i}$ ’s utility value.
11: end if
12: end for
13: seed item ← item with the largest utility value
14: Construct IDNC graph $G (V, E)$ according to the method in Section 4.3.
15: Searching for the Maximum Weighted Clique C which contains the seed item in $G (V, E)$ .
16: The encoded packet $P_{c}$ is obtained by XORing all data items which are identified by the vertices in C.
17: RSU multicasts $P_{c}$ .
18: All vehicles in RSU’s coverage receive $P_{c}$ and decode $P_{c}$ , update their caches.
19: Update vehicle location information, service queues and IDNC graph $G (V, E)$ .
20: end while

Performance evaluation

In this section, we evaluate the performance of the proposed PVDD algorithm by comparing it with the classical algorithms EDF (Xuan et al.²³), SIN (Xu et al.²⁴), and IDRT.²² In EDF, RSU always selects the most urgent data item, also known as the item with the earliest deadline, to be scheduled and multicasted to all vehicles within the coverage. In SIN, RSU multicasts the data item with the minimum SIN first, where $SIN = slack / num$ , slack is the duration from the current time slot to the deadline of the most urgent pending request for the data item, and num is the number of pending requests for the data item. In IDRT, the authors proposed a collision-free distributed relay selection method and adopted IDNC technology for the selected relay vehicle to retransmit lost packets. Once the relay vehicle is selected, it constructs an IDNC graph based on the packets receiving status of its client vehicles and generates retransmission packets based on this graph. The relay vehicle multicasts the IDNC packet which is combined using the packets that are identified by the vertices of the maximum clique in the graph, and the process continues until all client vehicles are satisfied. These methods are chosen as the benchmark algorithms because they represent the most classical and widely used scheduling algorithms, and they adopt the same network coding technology as the PVDD algorithm does.

Considering the highway V2R data dissemination scenario shown in Figure 2. Assuming that vehicles are randomly distributed in lanes, each vehicle in the coverage can send out a request for specific data item so as to support the users of the vehicle to get desired services. Each vehicle in the range generates a stream of requests one by one with exponentially distributed inter-arrival time. The mean request arrival rate is set to be a constant $λ$ , which is actually a scaling factor of the request arrival rate. The data access pattern is shaped with the Zipf distribution with skewness parameter $θ$ , $0 \leq θ \leq 1$ . The smaller the value of $θ$ is, the less different the items are accessing frequency among all data items in the database. In particular, when $θ = 0$ , the distribution becomes the uniform distribution, while the Zipf distribution becomes extremely skewed as $θ$ increases to 1. Time is slotted. The simulation parameters are set up as Table 1 shows.

Table 1.

System parameter settings.

Name	Range of values	Value
Coordinates of RSU	$- 1500 m \leq x_{R} \leq 1500 m$	$x_{R} = 0, y_{R} = 0$
	$- 50 m \leq y_{R} \leq 50 m$
% of high priority data	0–1	0.5
% of low priority data	0–1	0.5
Number of lanes	Bidirectional lanes 4–10	6 lanes
Widths of lane	3.5–3.75 m	3.75 m
Speed	60–120 km/h	120km/h
r	100–1500 m	100 m
M	Positive integer	300
$λ$	10–25 slots	10 slots
$ω_{1}$	10–20	20
$ω_{2}$	0–10	1
$θ$	0–1	0.5

RSU: road side unit.

The performance metrics used in the simulations are as follows:

Average download delay: mark the time elapses from the moment vehicle $v_{i}$ sends out a request until the moment that this request gets satisfied as $t_{i}$ , $t_{i}$ is the download delay of $v_{i}$ ’s request. For the system running period $T_{total}$ , if Z requests are satisfied, the average download delay for the Z requests is the average download delay of the system: $AT = \sum_{Z} t_{i} / (Z)$ . AT reflects the response speed of an RSU to data requests. Obviously, the smaller the average download delay, the faster the RSU responses and the better the system performance will be.

Deadline miss ratio: deadline miss ratio is defined as the ratio of the number of expired requests to the total number of requests. Low deadline miss ratio represents more satisfied requests and better system performance.

Average download delay for different priority data: as mentioned above, safety-related service applications have more stringent delay constraint than user-related service applications do. Since the safety-related applications support accident warning, traffic condition alert, navigation service and so on, and this information is related to vehicle driving safety, traffic control, and management. By introducing the average download delay for high-/low-priority data as a performance metric, we can evaluate the proposed algorithm in a more refined granularity.

Average download success ratio for different priority data: the download success ratio for high-priority data equals the number of satisfied high-priority data requests over the total number of high-priority data requests. Similarly, the download success ratio for low-priority data equals the number of satisfied low-priority data requests over the total number of low-priority data requests. Obviously, the higher the success rate of data download is, the higher the bandwidth utilization of the system gets, and the better the QoS.

The results are obtained when the system was in a steady state and all data points are based on the average of over 5000 simulation runs.

Deadline miss ratio

The experimental results are shown in Figure 3. It is seen that with the increment of the vehicles number, the deadline miss ratios increase gradually with all compared algorithms. This is because when the number of vehicles increase, the number of requests increases as well, and the system load increases, resulting in decreased RSU scheduling performance. Meanwhile, IDRT has the highest deadline miss ratio among all compared algorithms, for it sacrifices the time effectiveness for maximizing the number of vehicles that receive a wanted item in each retransmission. SIN performs better than EDF, since it not only considers the deadline of each data item but also the number of pending requests for the item. Comparing the four algorithms, the proposed PVDD algorithm achieves the lowest deadline miss ratio than that of the other three comparison algorithms, under different vehicle numbers, which shows that PVDD algorithm can satisfy as many data requests as possible, and the performance of PVDD algorithm is less affected by the system load.

Figure 3.

Deadline miss ratio vs number of vehicles.

Average download delay

As shown in Figure 4, EDF requires the longest download delay to fulfill all requesting vehicles, and SIN reduces the download delay by trying to schedule the mostly wanted data item in each retransmission. IDRT and the proposed PVDD algorithm have shorter average download delays than that of EDF and SIN algorithms under varied number of vehicles, which indicates that IDRT and PVDD algorithm can serve vehicle users more quickly with their wanted data and services than EDF and SIN. In addition, noticing that when the number of vehicles is 10, the average download delay of IDRT algorithm is lower than that of the proposed PVDD algorithm. However, when the number of vehicles exceeds 15, the average download delay of the proposed PVDD algorithm is lower than that of the IDRT algorithm, and this advantage of PVDD algorithm maintains when the number of vehicles increases. Since PVDD algorithm takes many factors affecting the download delay into full account and can respond to vehicle requests faster and better adapt to the increase of system load. It can be concluded that PVDD algorithm performs better than IDRT algorithm in average download delay, especially in densified vehicular communication scenarios. In addition, PVDD algorithm and IDRT algorithm both adopt network coding technology during the data scheduling. Comparing with EDF and SIN algorithms, which do not employ network coding technology, they can disseminate data items to all nodes in the network more quickly, which justifies the performance gain introduced by network coding technology.

Figure 4.

Average download delay vs number of vehicles.

Average download delay for different priority data

The average download delay is an indicator to show how fast the RSU can satisfy vehicles within its coverage. However, it is more important to ensure that the safety-related service requests can be satisfied timely so that vital functions of VANETs, such as safe driving, emergency alert, traffic control and management, can be supported. For this purpose, we use the metric of average download delay for high-/low-priority data to evaluate the algorithms capability to provide time-sensitive high-priority data dissemination without losing support for low-priority data. The simulation results of average download delay for different priority data are shown in Figures 5 and 6.

Figure 5.

Average download delay for high-priority data.

Figure 6.

Average download delay for low-priority data.

As shown in Figure 5, the average download delay for high-priority data of the four algorithms increase with the number of vehicles. EDF consumes more time slots to serve the requesting vehicles than SIN does when the number of vehicles is low, while SIN costs more slots than EDF does with the increment of number of vehicles. IDRT performs better than EDF and SIN. However, the proposed PVDD algorithm achieves the best performance that the average download delay of PVDD for the high-priority data is the shortest among all contrasted algorithms, indicating that the proposed PVDD algorithm performs best for providing safety-related time-sensitive service applications. Meanwhile, as it can be seen from Figure 6, the average download delay for low-priority data with PVDD algorithm is lower than that of SIN and EDF algorithms, and PVDD achieves the lowest average download delay for low-priority data among all compared algorithms, except when the network is very sparse that IDRT performs better than PVDD does. In addition, it is noticed that the average download delay for high-priority data is slightly shorter than that for low-priority data with PVDD algorithm. From Figures 7 and 8, it is seen that the average download success ratio for high-priority data is higher than that for low-priority data. It can be concluded that the low-priority data achieves the similar average download delay as the high-priority data, at the price of bringing down the average number of vehicles that are satisfied with their wanted items. Comparing with the rest algorithms, PVDD provides the shortest average download delay for both high- and low-priority data, which shows that PVDD algorithm can guarantee fast response to high-priority data requests while taking into account the response speed of low-priority data requests, to serve both high-/low-priority data requests in a more balanced and advanced way than the compared algorithms.

Figure 7.

Average download success ratio for high-priority data.

Figure 8.

Average download success ratio for low-priority data.

Average download success ratio for different priority data

As shown in Figure 7, with the increment of total number of vehicles in the system, the average download success ratios for high-priority data of four compared algorithms decrease gradually, since the system load increases with the number of vehicles. IDRT has the lowest average download success ratio for high-priority data, which means that only a few requests for high-priority data are satisfied with IDRT. Besides, EDF and SIN satisfy more requests for high-priority data than IDRT does, but there exists much room for improvement. It is clearly seen that the average download success ratio of PVDD algorithm for high-priority data is always higher than other comparison algorithms, which shows that PVDD is good at serving the most high-priority data requests satisfied than other algorithms. In addition, it is noticed from Figure 8 that while trying to satisfy the high-priority data requests as much as possible, PVDD can also serve the low-priority data requests at relatively acceptable success ratio, so as to ensure the average download success ratio of all data requests in the system.

Conclusion

The service applications carried by VANETs are mainly classified into safety-related applications and user-related applications. Furthermore, the safety-related applications are fundaments to advanced VANETs functions such as intelligent transportation, intelligent cities, traffic control and management and so on, which have great influence on VANETs and social transportation systems, thus should be given full attention. Meanwhile, user-related applications are mainly adopted as value-added services of VANETs. They provide varieties of applications for drivers and other traffic participants, including entertainment services, information inquiry, to provide drivers and passengers’ convenience, and to improve QoE in the period. In order to realize these attracting functions of VANETs, efficient data dissemination algorithms should be developed for distributing essential data to support different kinds of service applications. Particularly, the time sensitivity of safety-related service data dissemination, as well as the reliability requirements of both safety-related and user-related service data dissemination should be considered carefully to meet the transmission requirements. This article focuses on improving the data multicast performance of the safety-related and user-related services in VANETs, by differentiating the inherent priority in these two kinds of data services, and utilizing this characteristic to design a priority-based scheduling method, which considers multiple factors, such as vehicle location, speed, and vehicle aggregation degree that affect the transmission success ratio and deadline miss ratio. It then further applies the IDNC technology on the scheduling method to maximize the throughput and to reduce download delay. The proposed PVDD algorithm and the classical algorithms are compared by extensive simulation experiments. The experimental results show that PVDD algorithm can provide satisfactory QoS for data dissemination of safety-related service applications without degrading the QoS of user-related service applications under different conditions. Compared with other classical algorithms, PVDD algorithm exhibits better performance in average download delay, deadline miss ratio, average download delay for high-/low-priority data, and average download success ratio for high-/low-priority data.

Footnotes

Handling Editor: Juan Cano

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study was supported by the National Natural Science Foundation of China (grant no.: 61561029).

ORCID iD

Shujuan Wang

References

Zekri

Jia

Heterogeneous vehicular communications: a comprehensive study. Ad Hoc Netw 2018; 75(76): 52–79.

Zhang

Wang

et al . Development strategy and status of intelligent transportation vehicular networks. Commun Technol 2017; 50(7): 1345–1350.

Cheng

et al . Survey on vehicular ad hoc network based intelligent transportation system. Comput Sci 2014; 41(6): 1–10.

Kumar

Lee

JK.

Peer-to-peer cooperative caching for data dissemination in urban vehicular communications. IEEE Syst J 2014; 8(4): 1136–1144.

Zhao

Zhang

et al . A context-aware budget-constrained targeted advertising system for vehicular networks. IEEE Access 2018; 6: 8704–8713.

Dai

Liu

Zhuge

et al . Quality-of-experience-oriented autonomous intersection control in vehicular networks. IEEE T Intell Transp Syst 2016; 17(7): 1956–1967.

Tian

Hou

. Trad: traffic adaptive data dissemination protocol for both urban and highway vanets. In: Proceedings of the IEEE 30th international conference on advanced information networking and applications (AINA), Crans-Montana, 23–25 March 2016. New York: IEEE.

Lin

Kang

et al . Mozo: a moving zone based routing protocol using pure V2V communication in vanets. IEEE T Mobile Comput 2017; 16(5): 1357–1369.

Ravi

Thangaraj

Petale

. Stochastic network optimization of data dissemination for multi-hop routing in vanets. In: Proceedings of the international conference on wireless communications, signal processing and networking (WiSPNET), Chennai, India, 22–24 March 2018. New York: IEEE.

10.

Ucar

Ergen

Ozkasap

Muitihop-cluster-based IEEE 802.11p and LTE hybrid architecture for vanet safety message dissemination. IEEE T Veh Technol 2016; 65(4): 2621–2636.

11.

Shan

Shen

et al . A multi-hop broadcast protocol for emergency message dissemination in urban vehicular ad hoc networks. IEEE T Intell Transp Syst 2016; 17(3): 736–750.

12.

Wang

Huang

A safety data dissemination algorithm based on data priority and vehicle density. Comput Eng Sci 2017; 39(3): 485–491.

13.

Tiennoy

Saivichit

Using a distributed roadside unit for the data dissemination protocol in vanet with the named data architecture. IEEE Access 2018; 6: 32612–32623.

14.

Cho

Ahn

. AODV-based seamless data delivery in the intermittent v2i communication environment. In: Proceedings of the international conference on information and communication technology convergence (ICTC), Jeju, South Korea, 18–20 October 2017. New York: IEEE.

15.

Chen

Lee

Hwang

. Adaptive data rate transmission for v2i communication. In: Proceedings of the international conference on information and communication technology convergence (ICTC), Jeju, South Korea, 19–21 October 2016. New York: IEEE.

16.

Chen

Mao

et al . Throughput of infrastructure-based cooperative vehicular networks. IEEE T Intell Transp Syst 2017; 18(11): 2964–2978.

17.

Zhang

Cui

Bai

. Research of routing strategies based on network encoding under vehicle networking. In: Proceedings of the 8th international conference on electronics information and emergency communication (ICEIEC), Beijing, China, 15–17 June 2018. New York: IEEE.

18.

Nawaz

Ali

Md Ashiqur

Chong

PHJ

et al . On efficient data dissemination using network coding in multi-rsu vehicular ad hoc networks. In: Proceedings of the IEEE 83rd vehicular technology conference (VTC2016-Spring), Nanjing, China, 15–18 May 2016. New York: IEEE.

19.

Huang

Zhao

Wan

et al . BDNC: network coding-based message transmission protocol in vanets business application. Appl Electron Tech 2016; 42(8): 125–129.

20.

Christian

Luis

Sargento

et al . Multi-technology vs single-technology architecture for network coding in vanets. In: Proceedings of the IEEE symposium on computers and communications (ISCC), Natal, Brazil, 25–28 June 2018. New York: IEEE.

21.

Wang

An area content distribution scheme based on local response service for vehicular ad hoc networks. J Chin Comput Syst 2014; 35(1): 80–84.

22.

Wang

Yin

Efficient data dissemination strategy for vanets based on network coding. Comput Eng 2016; 42(5): 118–122, 129.

23.

Xuan

Sen

Gonzalez

et al . Broadcast on demand: efficient and timely dissemination of data in mobile environments. In: Proceedings of the 3rd IEEE real-time technology and applications, Montreal, QC, Canada, 9–11 June 1997. New York: IEEE.

24.

Tang

Lee

et al . Time-critical on-demand data broadcast: algorithms, analysis, and performance evaluation. IEEE T Parallel Distribu Syst 2006; 17(1): 3–14.