# Safety Message Verification Using History-Based Relative-Time Zone Priority Scheme

Authors: Sam Banani; Somsak Kittipiyakul; Surapa Thiemjarus; Steven Gordon
Journal: Journal of Computer Networks and Communications
 (2019)

---

## Abstract

Safety message verification plays an important role in securing vehicular ad hoc networks (VANETs). As safety messages are broadcasted several times per second in a highly dense network, message arrival rate can easily exceed the verification rate of safety messages at a vehicle. As a result, an algorithm is needed for selecting and prioritizing relevant messages from received messages to increase the awareness of vehicles in the vicinity. This paper presents the history-based relative-time zone (HRTZ) priority scheme for selecting and verifying relevant received safety messages. HRTZ is an enhanced version of our previously proposed relative-time zone (RTZ) priority scheme. HRTZ achieves higher awareness of nearby vehicles and works in different road configurations. To increase awareness of neighboring vehicles, the average velocity of neighboring vehicles in the range of communication is used to determine the range of the danger zone and other zones. The messages are ranked based on the zone of transmitting vehicles, road configuration (with/without a barrier) and transmitting vehicle location and direction, and relative time between transmitting and receiving vehicles. Only the most up-to-date message from each vehicle is kept in the receiver’s buffer. As a result, each neighboring vehicle has only the most recent safety message in the buffer at any time. The simulation results show that HRTZ achieves a higher rate of verified messages with low delay for nearby vehicles and achieves higher awareness for vehicles in the vicinity, when compared to RTZ and other existing schemes.


---

## Body

## 1. Introduction

In recent years, the rapid growth of the transportation industry makes it easy for people to travel and transport goods around in a short duration. One of the challenging matters in transportation is how to increase road safety. In 2015, the World Health Organization (WHO) reported the number of road traffic deaths globally has plateaued at 1.25 million per year and as many as 20–50 million people are injured [1]. According to [2], 94% of accidents occurred because of drivers’ mistakes due to poor recognition or wrong decision-making. In general, during the accidents, 80% of drivers did not pay attention within the three seconds of an accident. Some countries such as France, Netherlands [3], and the US [4] suggested that the safety distance between vehicles should be more than two seconds. Specialists in transportation industries have been looking for services to increase safety and provide information among vehicles. To reach this goal, intelligent transportation systems (ITS) have proposed to share information among vehicles and infrastructure. This type of network is known as vehicular ad hoc networks (VANETs).In VANETs, each vehicle is usually equipped with necessary sensors (such as GPS and compass), a transceiver, and an onboard unit (for processing and storing necessary information). There are fixed roadside units (RSUs) along roads. Vehicles may communicate with other vehicles, directly or indirectly via RSUs to create a large-scale network for sharing necessary information. Wireless Access in Vehicular Environment (WAVE) [5] is one of the standards that allow vehicles and the infrastructure to communicate and share information wirelessly. To increase awareness in a vehicle about its neighboring vehicles, traffic efficiency, and increase safety, WAVE suggests that vehicles should broadcast Basic Safety Messages (BSMs) which contain vehicles’ status (e.g., position, velocity, and heading) every 100 ms or 300 ms to the one-hop communication range. After the received BSMs are verified, safety applications [6–9] use the information in BSMs to increase traffic efficiency and prevent vehicles from possible safety incidents by sending warnings to the drivers.In VANETs with traffic congestion, vehicles may receive thousands of BSMs from neighboring vehicles which make it impossible for vehicles to verify all messages [5, 10–15]. This is because the verification process for a message involves a time-consuming cryptographic operation; for example, it could take at least 4.97 ms on average [16, 17]. Due to the high density traffic, the BSM receiving rate is usually higher than the BSM verification rate. To cope with this problem, a vehicle can either accept BSMs without verification or verify as many BSMs as it can and discard the rest. The former method may cause the vehicle to be exposed to the possibility of being attacked, while the later may cause safety application [15] to miss relevant and important information. To better cope with the problem, it is better to selectively verify messages based on their potential relevance to the safety applications; that is, we require a verification prioritization scheme. Many studies [10–14, 18–22] have proposed verification prioritization schemes. In this paper, we propose an improvement of our previous relative-time zone (RTZ) scheme proposed in [15], called the history-based relative-time zone (HRTZ) scheme. The contributions of this paper are as follows:(i)
HRTZ uses the history of vehicles’ velocity in a one-hop communication range and road configuration (with/without a barrier) to dynamically divide the area of communication to discrete zones from near to far zones for clustering arrival of BSMs from transmitting vehicles. The first zone is called the danger zone, where BSMs received from this zone has a higher priority to verify compared to other zones (safe zones), since nearby vehicles are more likely to be involved in a safety incident.(ii)
Dangerous vehicles can be identified by rankings of received BSMs. HRTZ uses a combination of three criteria, namely, zone rank, BSM rank, and relative-time rank to rank arrival messages from transmitting vehicles. The higher rank indicates that the transmitting vehicle is more dangerous and the BSMs from those vehicles have a higher chance to be verified.(iii)
Vehicles should have a high awareness of neighboring vehicles in the communication range, so that safety applications are able to identify the dangerous situation. To increase awareness of vehicles about neighboring vehicles in the vicinity and up-to-date verified safety messages, HRTZ uses the history of one-hop communication to remove duplicate and old messages in the buffer. As a result, vehicles are able to verify more recent and up-to-date BSMs from neighboring vehicles and have higher awareness of the vicinity.This paper is organized as follows. Section2 reviews the prioritization of safety messages at vehicles in VANETs. Section 3 presents background and assumptions of our system model. Section 4 describes the details of the proposed history-based relative-time zone (HRTZ) priority scheme. Section 5 presents evaluation metrics and simulation setups. Section 6 provides experimental results and the comparison of HRTZ with other schemes. Section 7 concludes this paper.


## 2. Related Works

In general, there exist two techniques for solving the problem of mismatch between the BSM arrival rate and the BSM verification rate in a high density network: (1) safety message prioritization at the transmitter and (2) safety message prioritization at the receiver. Figure1 shows the categorization of the safety message prioritization scheme in VANETs.Figure 1
Categorization of the safety message prioritization scheme in VANETs.


### 2.1. Safety Message Prioritization at Transmitter

The message transmission rate can either be fixed or adaptive. In the adaptive case, message prioritization is performed based on transmission rate, transmission power, contention window size, or a combination of the aforementioned factors.


#### 2.1.1. Fixed Rate Transmission of BSM

WAVE protocol [5] uses a fixed rate to transmit BSMs in VANETs (e.g., 10 messages/s). WAVE adopts the enhanced distributed channel access (ECDA) mechanism from IEEE 802.11e [23] at the MAC layer to give priority to more important messages. As a result, important messages have a higher chance to be transmitted. Eenennaam et al. [24] proposed to drop old messages in the transmitter buffer to increase freshness of transmitting messages. The proposed mechanism is better than prioritization of messages in the WAVE, since WAVE uses the first-in-first-out buffer at the transmitter. As a result, new messages will be dropped if the buffer overflows.


#### 2.1.2. Adaptive Rate Transmission of BSM

This scheme adaptively adjusts the BSM transmission rate based on traffic conditions. The drawback of this scheme is that low transmission rate may reduce the awareness of neighboring vehicles causing inaccuracy in safety applications. In [25–27], the authors used different parameters to adaptively adjust BSM transmission rates.


#### 2.1.3. Adaptive Transmission Power of BSM

This scheme adaptively adjusts range of communication by changing the transmitting power. The higher the transmitting power, the farther the range the vehicle can broadcast messages. As a result, the lower transmission power can give closer vehicles higher priority. The drawback of this scheme is reducing transmission power impacts the number of vehicles that can receive messages. With low transmitting power, only neighboring vehicles in close proximity can receive the messages. This causes significant reduction in the awareness of neighboring vehicles. In addition, the factors such as obstacles in a VANET can affect signal strength which causes change in the communication range of transmitting vehicles. Some studies have proposed to use adaptive transmission power of BSMs [28–30].


#### 2.1.4. Adaptive Contention Window Size for Transmitting BSM

This scheme adaptively adjusts the contention window size (CW) of MAC in 802.11p [31] WAVE protocol. Reducing the CW parameter can give higher priority to the relevant messages for transmitting which causes the reduction in transmission delay for these messages. In contrast, increasing CW gives lower priority to irrelevant messages for transmission. The drawback of this scheme is that increasing the CW has a negative effect on transmission delay of the message because the back-off interval will be uniformly selected from [0, CW+1], and each time the transmission failed, the value of CW will be doubled. In [32, 33], adaptive contention window size is used for BSM transmission.


#### 2.1.5. Hybrid Scheme

This scheme uses a combination of adaptive transmission rate, adaptive transmission power, and/or adaptive contention window size for transmitting BSM [34–37].


### 2.2. Safety Message Prioritization at Receiver

Although prioritization of messages at transmitters can reduce message arrival rate at receivers, it does not consider the neighboring vehicles messages nor the receiver capability. As a result, prioritization of safety messages at a receiver is needed to verify more BSMs from transmitting vehicles in vicinity which are more likely to be involved in a safety incident. The receiver-based prioritization scheme can be categorized into four schemes: random-based, batch, priority-based, and hybrid schemes.


#### 2.2.1. Random-Based Verification Scheme

In this scheme, messages to be verified are randomly picked from all available received messages. Despite its simplicity, a disadvantage of this scheme is that some relevant BSMs may be verified too late or not be verified at all. Raya et al. [18] proposed such a scheme to increase security and scalability of verified messages. Since messages are randomly selected, attackers cannot attack only a particular message. Several authentication methods [19, 38, 39] use this scheme.


#### 2.2.2. Batch Verification Scheme

In this scheme, a receiver collects arrival BSMs as a batch and then verifies all at once [19–22]. As a result, batch verification decreases the verification time per BSM. The disadvantages of this scheme [15] are as follows: (1) collecting messages in a batch causes an additional delay for verification, (2) the batch may not be successfully verified if any BSM in the batch has a false signature, and (3) the bilinear pairing-based signature used in batch verification has high computational complexity [40].


#### 2.2.3. Priority-Based Verification Scheme

In this scheme, a vehicle uses information (e.g., steer angle, velocity, heading, and position) in the BSMs received from neighboring vehicles to prioritize arrival BSMs in a buffer. Li and Chigan [12] proposed a verification scheme where arrival BSMs are ranked depending on distance and the number of hops between receivers and transmitters. The ranked BSMs are verified depending on a fixed probability threshold so that the BSMs from close-by neighboring vehicles with a lower number of hops have a higher probability to be verified. The verification based on probability may cause some received BSMs even from nearby transmitting vehicles to be not verified. Li and Chigan scheme achieves the same performance as random-based verification scheme in a low traffic condition [41]. Biswas et al. [10, 11] proposed a scheme where a vehicle ranks arrival messages using a decision tree based on three criteria, namely, transmitting vehicles’ position, acceleration, and velocity [42]. Each level of decision has a bloom filter [43, 44], which checks an assigned portion information in a BSM. After that, the BSMs are verified with specific verification probability from each associated rank. Hamida et al. [13, 14] used the k-mean clustering algorithm to cluster received signal strengths of BSMs into five areas which are mapped to multilevel priority queues for message verification. The buffer associated with closer area’s received messages has a higher priority for verification. A disadvantage of this scheme is that signal strength can vary significantly due to obstacles and environment. As a result, a signal strength may not be suitable for clustering arrival messages. Our previously proposed relative-time zone (RTZ) [15] prioritizes BSMs based on location and direction of the transmitting vehicle (quadrant), close proximity (zones), and relative time. The key design of RTZ uses adaptive discrete zones based on human reaction time and density of network where the received messages from the close zone with lower relative time have higher chance to be verified. In this paper, we propose history-based relative-time zone (HRTZ), which is an enhancement of RTZ.


## 2.1. Safety Message Prioritization at Transmitter

The message transmission rate can either be fixed or adaptive. In the adaptive case, message prioritization is performed based on transmission rate, transmission power, contention window size, or a combination of the aforementioned factors.


### 2.1.1. Fixed Rate Transmission of BSM

WAVE protocol [5] uses a fixed rate to transmit BSMs in VANETs (e.g., 10 messages/s). WAVE adopts the enhanced distributed channel access (ECDA) mechanism from IEEE 802.11e [23] at the MAC layer to give priority to more important messages. As a result, important messages have a higher chance to be transmitted. Eenennaam et al. [24] proposed to drop old messages in the transmitter buffer to increase freshness of transmitting messages. The proposed mechanism is better than prioritization of messages in the WAVE, since WAVE uses the first-in-first-out buffer at the transmitter. As a result, new messages will be dropped if the buffer overflows.


### 2.1.2. Adaptive Rate Transmission of BSM

This scheme adaptively adjusts the BSM transmission rate based on traffic conditions. The drawback of this scheme is that low transmission rate may reduce the awareness of neighboring vehicles causing inaccuracy in safety applications. In [25–27], the authors used different parameters to adaptively adjust BSM transmission rates.


### 2.1.3. Adaptive Transmission Power of BSM

This scheme adaptively adjusts range of communication by changing the transmitting power. The higher the transmitting power, the farther the range the vehicle can broadcast messages. As a result, the lower transmission power can give closer vehicles higher priority. The drawback of this scheme is reducing transmission power impacts the number of vehicles that can receive messages. With low transmitting power, only neighboring vehicles in close proximity can receive the messages. This causes significant reduction in the awareness of neighboring vehicles. In addition, the factors such as obstacles in a VANET can affect signal strength which causes change in the communication range of transmitting vehicles. Some studies have proposed to use adaptive transmission power of BSMs [28–30].


### 2.1.4. Adaptive Contention Window Size for Transmitting BSM

This scheme adaptively adjusts the contention window size (CW) of MAC in 802.11p [31] WAVE protocol. Reducing the CW parameter can give higher priority to the relevant messages for transmitting which causes the reduction in transmission delay for these messages. In contrast, increasing CW gives lower priority to irrelevant messages for transmission. The drawback of this scheme is that increasing the CW has a negative effect on transmission delay of the message because the back-off interval will be uniformly selected from [0, CW+1], and each time the transmission failed, the value of CW will be doubled. In [32, 33], adaptive contention window size is used for BSM transmission.


### 2.1.5. Hybrid Scheme

This scheme uses a combination of adaptive transmission rate, adaptive transmission power, and/or adaptive contention window size for transmitting BSM [34–37].


## 2.1.1. Fixed Rate Transmission of BSM

WAVE protocol [5] uses a fixed rate to transmit BSMs in VANETs (e.g., 10 messages/s). WAVE adopts the enhanced distributed channel access (ECDA) mechanism from IEEE 802.11e [23] at the MAC layer to give priority to more important messages. As a result, important messages have a higher chance to be transmitted. Eenennaam et al. [24] proposed to drop old messages in the transmitter buffer to increase freshness of transmitting messages. The proposed mechanism is better than prioritization of messages in the WAVE, since WAVE uses the first-in-first-out buffer at the transmitter. As a result, new messages will be dropped if the buffer overflows.


## 2.1.2. Adaptive Rate Transmission of BSM

This scheme adaptively adjusts the BSM transmission rate based on traffic conditions. The drawback of this scheme is that low transmission rate may reduce the awareness of neighboring vehicles causing inaccuracy in safety applications. In [25–27], the authors used different parameters to adaptively adjust BSM transmission rates.


## 2.1.3. Adaptive Transmission Power of BSM

This scheme adaptively adjusts range of communication by changing the transmitting power. The higher the transmitting power, the farther the range the vehicle can broadcast messages. As a result, the lower transmission power can give closer vehicles higher priority. The drawback of this scheme is reducing transmission power impacts the number of vehicles that can receive messages. With low transmitting power, only neighboring vehicles in close proximity can receive the messages. This causes significant reduction in the awareness of neighboring vehicles. In addition, the factors such as obstacles in a VANET can affect signal strength which causes change in the communication range of transmitting vehicles. Some studies have proposed to use adaptive transmission power of BSMs [28–30].


## 2.1.4. Adaptive Contention Window Size for Transmitting BSM

This scheme adaptively adjusts the contention window size (CW) of MAC in 802.11p [31] WAVE protocol. Reducing the CW parameter can give higher priority to the relevant messages for transmitting which causes the reduction in transmission delay for these messages. In contrast, increasing CW gives lower priority to irrelevant messages for transmission. The drawback of this scheme is that increasing the CW has a negative effect on transmission delay of the message because the back-off interval will be uniformly selected from [0, CW+1], and each time the transmission failed, the value of CW will be doubled. In [32, 33], adaptive contention window size is used for BSM transmission.


## 2.1.5. Hybrid Scheme

This scheme uses a combination of adaptive transmission rate, adaptive transmission power, and/or adaptive contention window size for transmitting BSM [34–37].


## 2.2. Safety Message Prioritization at Receiver

Although prioritization of messages at transmitters can reduce message arrival rate at receivers, it does not consider the neighboring vehicles messages nor the receiver capability. As a result, prioritization of safety messages at a receiver is needed to verify more BSMs from transmitting vehicles in vicinity which are more likely to be involved in a safety incident. The receiver-based prioritization scheme can be categorized into four schemes: random-based, batch, priority-based, and hybrid schemes.


### 2.2.1. Random-Based Verification Scheme

In this scheme, messages to be verified are randomly picked from all available received messages. Despite its simplicity, a disadvantage of this scheme is that some relevant BSMs may be verified too late or not be verified at all. Raya et al. [18] proposed such a scheme to increase security and scalability of verified messages. Since messages are randomly selected, attackers cannot attack only a particular message. Several authentication methods [19, 38, 39] use this scheme.


### 2.2.2. Batch Verification Scheme

In this scheme, a receiver collects arrival BSMs as a batch and then verifies all at once [19–22]. As a result, batch verification decreases the verification time per BSM. The disadvantages of this scheme [15] are as follows: (1) collecting messages in a batch causes an additional delay for verification, (2) the batch may not be successfully verified if any BSM in the batch has a false signature, and (3) the bilinear pairing-based signature used in batch verification has high computational complexity [40].


### 2.2.3. Priority-Based Verification Scheme

In this scheme, a vehicle uses information (e.g., steer angle, velocity, heading, and position) in the BSMs received from neighboring vehicles to prioritize arrival BSMs in a buffer. Li and Chigan [12] proposed a verification scheme where arrival BSMs are ranked depending on distance and the number of hops between receivers and transmitters. The ranked BSMs are verified depending on a fixed probability threshold so that the BSMs from close-by neighboring vehicles with a lower number of hops have a higher probability to be verified. The verification based on probability may cause some received BSMs even from nearby transmitting vehicles to be not verified. Li and Chigan scheme achieves the same performance as random-based verification scheme in a low traffic condition [41]. Biswas et al. [10, 11] proposed a scheme where a vehicle ranks arrival messages using a decision tree based on three criteria, namely, transmitting vehicles’ position, acceleration, and velocity [42]. Each level of decision has a bloom filter [43, 44], which checks an assigned portion information in a BSM. After that, the BSMs are verified with specific verification probability from each associated rank. Hamida et al. [13, 14] used the k-mean clustering algorithm to cluster received signal strengths of BSMs into five areas which are mapped to multilevel priority queues for message verification. The buffer associated with closer area’s received messages has a higher priority for verification. A disadvantage of this scheme is that signal strength can vary significantly due to obstacles and environment. As a result, a signal strength may not be suitable for clustering arrival messages. Our previously proposed relative-time zone (RTZ) [15] prioritizes BSMs based on location and direction of the transmitting vehicle (quadrant), close proximity (zones), and relative time. The key design of RTZ uses adaptive discrete zones based on human reaction time and density of network where the received messages from the close zone with lower relative time have higher chance to be verified. In this paper, we propose history-based relative-time zone (HRTZ), which is an enhancement of RTZ.


## 2.2.1. Random-Based Verification Scheme

In this scheme, messages to be verified are randomly picked from all available received messages. Despite its simplicity, a disadvantage of this scheme is that some relevant BSMs may be verified too late or not be verified at all. Raya et al. [18] proposed such a scheme to increase security and scalability of verified messages. Since messages are randomly selected, attackers cannot attack only a particular message. Several authentication methods [19, 38, 39] use this scheme.


## 2.2.2. Batch Verification Scheme

In this scheme, a receiver collects arrival BSMs as a batch and then verifies all at once [19–22]. As a result, batch verification decreases the verification time per BSM. The disadvantages of this scheme [15] are as follows: (1) collecting messages in a batch causes an additional delay for verification, (2) the batch may not be successfully verified if any BSM in the batch has a false signature, and (3) the bilinear pairing-based signature used in batch verification has high computational complexity [40].


## 2.2.3. Priority-Based Verification Scheme

In this scheme, a vehicle uses information (e.g., steer angle, velocity, heading, and position) in the BSMs received from neighboring vehicles to prioritize arrival BSMs in a buffer. Li and Chigan [12] proposed a verification scheme where arrival BSMs are ranked depending on distance and the number of hops between receivers and transmitters. The ranked BSMs are verified depending on a fixed probability threshold so that the BSMs from close-by neighboring vehicles with a lower number of hops have a higher probability to be verified. The verification based on probability may cause some received BSMs even from nearby transmitting vehicles to be not verified. Li and Chigan scheme achieves the same performance as random-based verification scheme in a low traffic condition [41]. Biswas et al. [10, 11] proposed a scheme where a vehicle ranks arrival messages using a decision tree based on three criteria, namely, transmitting vehicles’ position, acceleration, and velocity [42]. Each level of decision has a bloom filter [43, 44], which checks an assigned portion information in a BSM. After that, the BSMs are verified with specific verification probability from each associated rank. Hamida et al. [13, 14] used the k-mean clustering algorithm to cluster received signal strengths of BSMs into five areas which are mapped to multilevel priority queues for message verification. The buffer associated with closer area’s received messages has a higher priority for verification. A disadvantage of this scheme is that signal strength can vary significantly due to obstacles and environment. As a result, a signal strength may not be suitable for clustering arrival messages. Our previously proposed relative-time zone (RTZ) [15] prioritizes BSMs based on location and direction of the transmitting vehicle (quadrant), close proximity (zones), and relative time. The key design of RTZ uses adaptive discrete zones based on human reaction time and density of network where the received messages from the close zone with lower relative time have higher chance to be verified. In this paper, we propose history-based relative-time zone (HRTZ), which is an enhancement of RTZ.


## 3. System Model and Background

### 3.1. Case Scenario

We assume a straight highway, where the length of highway isc km with e lanes in each direction with width h m per lane. The RSUs are deployed along the sides of the road. These units can communicate directly or indirectly with vehicles. We assume that vehicles receive from RSUs the information about the road configuration such as the existing barrier separation for different directions and number of lanes. Each vehicle has length of l m with a width of w m. The velocity of vehicle i, vi m/s , may vary between vmin,vmax with an acceleration of ai m/s2. All vehicles are equipped with necessary sensors to detect their location (longitude x and latitude y), heading, steer angle, and other physical movement parameters. All vehicles are equipped with an onboard unit which has limited processing and storage capability. The onboard unit is responsible for processing and verifying messages. All vehicles in a VANET have a wireless communication device to communicate with other vehicles and infrastructure directly or indirectly. The transceivers in the VANET are compatible with the WAVE standard [5].


### 3.2. Safety Applications

Every year a significant number of accidents in the world are related to intersections, rear-end, head, bind spot, and lane change collisions. The main focus of safety applications in VANETs is to decrease probability of traffic accidents and loss of life [45–48]. Basic Safety Messages (BSMs) [49] is an important type of messages used in safety applications. Generally, vehicles in VANETs broadcast BSMs every 100 ms or 300 ms intervals to the one-hop communication range to inform neighboring vehicles about their status such as position, acceleration, and velocity. Safety applications analyze the information to assist and warn a driver in order to prevent an accident. Table 1 shows some of vehicle-to-vehicle road safety application requirements [6–9] such as transmission mode, allowable latency (s), and the maximum range (m).Table 1
Safety applications and their requirements.
Application
Transmission mode
Allowable latency (s)
Maximum range (m)
Cooperative forward collision warning
Periodic
100
150
Lane change warning
Periodic
100
150
Blind spot warning
Periodic
100
150
Highway merge assistance
Periodic
100
250
Visibility enhancement
Periodic
100
300
Cooperative collision warning
Periodic
100
150
Precrash sensing
Event-driven
20
50


### 3.3. Background on Relative-Time Zone Priority Scheme

In our previous study [15], we proposed the relative-time zone (RTZ) prioritization scheme which uses location and direction of nearby vehicles (quadrant), vehicle close proximity (zone), and relative time, to prioritize relevant received BSMs in a receiving vehicle’s buffer. RTZ scheme gives lower priority to BSMs from transmitting vehicles that travel in opposite directions and behind the receiving vehicle (quadrant 4). The BSMs are grouped into zones from close to distant zones where close zones have a higher priority for message verification compared to distant zones. The size of zone is determined based on network density and human reaction time. Finally, RTZ uses receiver and transmitter positions and motion to determine the relative time. The BSMs with a smaller relative time are considered more important in each zone. Some limitations of RTZ for prioritizing BSMs are as follows:(i)
The range of zones in close proximity is determined by using the message-receiving rate. Since the message receiving rate can vary due to wireless channels and obstacles, using that to define zones may be inaccurate.(ii)
Relative-time value between vehicles, which depends on velocity, acceleration, and position, can be negative, positive, or infinite. This may be problematic when prioritizing messages. In addition, vehicles traveling in the same direction generally have similar physical motion. Therefore, relative time between two vehicles can be high although they are nearby.(iii)
RTZ does not differentiate whether the road section has a physical barrier separating vehicles moving in opposite directions. RTZ gives the lowest priority to vehicles in quadrant 4. Vehicles in other quadrants are given the same priority independent of their traveling directions. However, this is not reasonable since when there is no barrier, the vehicles moving toward a receiving vehicle pose more danger than those closer vehicles moving in the same direction.To enhance RTZ and improve the performance of safety messages verification, we propose the history-based relative-time zone (HRTZ) prioritization scheme.


## 3.1. Case Scenario

We assume a straight highway, where the length of highway isc km with e lanes in each direction with width h m per lane. The RSUs are deployed along the sides of the road. These units can communicate directly or indirectly with vehicles. We assume that vehicles receive from RSUs the information about the road configuration such as the existing barrier separation for different directions and number of lanes. Each vehicle has length of l m with a width of w m. The velocity of vehicle i, vi m/s , may vary between vmin,vmax with an acceleration of ai m/s2. All vehicles are equipped with necessary sensors to detect their location (longitude x and latitude y), heading, steer angle, and other physical movement parameters. All vehicles are equipped with an onboard unit which has limited processing and storage capability. The onboard unit is responsible for processing and verifying messages. All vehicles in a VANET have a wireless communication device to communicate with other vehicles and infrastructure directly or indirectly. The transceivers in the VANET are compatible with the WAVE standard [5].


## 3.2. Safety Applications

Every year a significant number of accidents in the world are related to intersections, rear-end, head, bind spot, and lane change collisions. The main focus of safety applications in VANETs is to decrease probability of traffic accidents and loss of life [45–48]. Basic Safety Messages (BSMs) [49] is an important type of messages used in safety applications. Generally, vehicles in VANETs broadcast BSMs every 100 ms or 300 ms intervals to the one-hop communication range to inform neighboring vehicles about their status such as position, acceleration, and velocity. Safety applications analyze the information to assist and warn a driver in order to prevent an accident. Table 1 shows some of vehicle-to-vehicle road safety application requirements [6–9] such as transmission mode, allowable latency (s), and the maximum range (m).Table 1
Safety applications and their requirements.
Application
Transmission mode
Allowable latency (s)
Maximum range (m)
Cooperative forward collision warning
Periodic
100
150
Lane change warning
Periodic
100
150
Blind spot warning
Periodic
100
150
Highway merge assistance
Periodic
100
250
Visibility enhancement
Periodic
100
300
Cooperative collision warning
Periodic
100
150
Precrash sensing
Event-driven
20
50


## 3.3. Background on Relative-Time Zone Priority Scheme

In our previous study [15], we proposed the relative-time zone (RTZ) prioritization scheme which uses location and direction of nearby vehicles (quadrant), vehicle close proximity (zone), and relative time, to prioritize relevant received BSMs in a receiving vehicle’s buffer. RTZ scheme gives lower priority to BSMs from transmitting vehicles that travel in opposite directions and behind the receiving vehicle (quadrant 4). The BSMs are grouped into zones from close to distant zones where close zones have a higher priority for message verification compared to distant zones. The size of zone is determined based on network density and human reaction time. Finally, RTZ uses receiver and transmitter positions and motion to determine the relative time. The BSMs with a smaller relative time are considered more important in each zone. Some limitations of RTZ for prioritizing BSMs are as follows:(i)
The range of zones in close proximity is determined by using the message-receiving rate. Since the message receiving rate can vary due to wireless channels and obstacles, using that to define zones may be inaccurate.(ii)
Relative-time value between vehicles, which depends on velocity, acceleration, and position, can be negative, positive, or infinite. This may be problematic when prioritizing messages. In addition, vehicles traveling in the same direction generally have similar physical motion. Therefore, relative time between two vehicles can be high although they are nearby.(iii)
RTZ does not differentiate whether the road section has a physical barrier separating vehicles moving in opposite directions. RTZ gives the lowest priority to vehicles in quadrant 4. Vehicles in other quadrants are given the same priority independent of their traveling directions. However, this is not reasonable since when there is no barrier, the vehicles moving toward a receiving vehicle pose more danger than those closer vehicles moving in the same direction.To enhance RTZ and improve the performance of safety messages verification, we propose the history-based relative-time zone (HRTZ) prioritization scheme.


## 4. History-Based Relative-Time Zone Prioritization

### 4.1. Clustering Vehicles in Zones Using Velocity and Road Configuration

In RTZ, the range of zones is determined from the BSM arrival rate and BSM verification rate. However, due to the nature of the wireless channel and obstacle and density of vehicles, the BSM arrival rate can vary significantly. To address this issue, we propose to use the average velocity of neighboring vehicles in the one-hop communication range to determine the size of zones.We assume that every vehicle keeps the history of recent verified BSM from transmitting vehicles within the communication range. The stored information includes senders’ ID, velocity, and acceleration. Therefore, the receiving vehicle can determine the average velocity of the current neighboring vehicles at timet traveling in the same direction as(1)v¯t=1n∑i=0nvit,where n is the number of vehicles traveling in the same direction and within the communication range r and vit is the velocity of the neighboring vehicle i at time t.In this paper, we determine the range of danger zonerdz depending on two scenarios based on road configuration: first, road with a barrier between different directions, and second, road without a barrier between different directions.Case 1 (Road with a Barrier Separating Different Directions).
In this case, neighboring vehicles in the same direction as receiving vehicles are considered more important. To determine the range of danger zone, we consider the worst situation where the leading vehiclej stops suddenly, i.e., vjt=0. Let us denote the threshold time spacing between two adjacent vehicles in the same lane as tth (e.g., tth=2 seconds). This means that if the receiving vehicle keeps on traveling at the same speed vt, when the front vehicle suddenly is at a full rest (this is not physically correct; however, here we are assuming the worst case), the receiving vehicle will hit the front one before the driver can respond if the distance separation is less:(2)rdz=v¯ttth.
We let this distance be the range of the danger zone for barrier roads since the danger zone is defined to cover all vehicles that are too close for the drivers of these vehicles to respond. The vehicles in the danger zone include not only the vehicles in the front but also those in the back and on the sides since the vehicles in the back can also hit the receiving vehicle. Note that we use the average velocityv¯t of the vehicles in the same direction as the receiving vehicle at time t as the velocity to define the range of the danger zone since vehicles are in danger zones to each other.Case 2 (Road without Any Barrier Separating Different Directions).
In this case, neighboring vehicles in the opposite direction and the front of the receiving vehicle are considered more important since vehicles which travel in the opposite direction are able to cross over and cause an accident. Ifv′¯t denotes the average velocity of vehicles in the opposite direction at time t, the range of the danger zone for no-barrier roads is given as follows:(3)rdz=v′¯t+v¯ttth,where v′¯t+v¯t is the relative average speed of the vehicles in the opposite direction to the receiving vehicle. Figure 2 shows the concept of zones in VANETs, where the danger zone is denoted as zone 1. Note that the higher the vehicle density, the smaller the radius of the danger zone because the velocity of the vehicle in vicinity decreases. Assume that the size of zones increases with the same scale as that of the danger zone, and the number of zones, M, can be defined as follows:(4)M=rrdz.
Therefore, the zone,z, of the transmitting vehicle j at distance dij from the receiving vehicle i [15] is(5)z=Mdijr,dij≤r,M,dij>r,where z=1,2,…,M. The first zone, z=1, is called the danger zone which has the highest priority for verification of BSMs, and the other zones are called safe zones since the vehicles in that zones have some distance to the receiving vehicle.Figure 2
Concept of zones based on velocity of neighboring vehicles and road configuration.


### 4.2. Ranking BSM Using Road Configuration and Location and Direction

Location and direction of vehicles are very important to prioritize BSMs. In [15], RTZ used location and direction of the transmitting vehicles (quadrant) to broadly filter out the irrelevant BSMs. The transmitting vehicles that travel in opposite directions and passing a receiving vehicle are considered low priority (quadrant 4) compared to other vehicles.To improve the location and direction ranking system method in RTZ, HRTZ uses a decision tree to rank BSMs,rdt, more relevantly based on road configuration and a transmitting vehicle’s location and direction. As shown in Figure 3, BSM can receive a rank between 7 and 4 for roads with a barrier and 3 to 0 for roads without a barrier. The rank of BSM, rBSM, based on rdt can be normalized between [0,1] as follows:(6)rBSM=rdt−34,4≤rdt≤7,rdt+14,0≤rdt≤3.Figure 3
BSM rank based on road configuration (with/without a barrier), location, and direction of transmitting vehicles.Case Study 1 (Road Has a Barrier between Different Directions).
A vehicle has to be more aware of neighboring vehicles that travel in the same direction and front of the receiving vehicles since these vehicles may suddenly stop/deaccelerate and can cause an accident. Therefore, the BSMs for these neighboring vehicles receive the highest priority (i.e.,rBSM=1). The other important neighboring vehicles are the vehicles which travel in the same direction and behind the receiving vehicle. The receiving vehicle has to be aware of those neighboring vehicles which travel close to or in a situation when the receiving vehicle wants to change the lane (i.e., rBSM=0.75). After that, the receiving vehicle may need to be aware of neighboring vehicles which travel in an opposite direction in front and behind of the receiving vehicle.Case Study 2 (Road Does Not Have a Barrier between Different Directions).
A vehicle has to be more aware of neighboring vehicles which travel in the opposite direction and front of the receiving vehicle since these neighboring vehicles may cross over to the receiving vehicle lane and cause an accident. Therefore, the BSMs received from those vehicles have the highest rankrBSM=1. On the contrary, neighboring vehicles traveling in the same direction and front of the receiving vehicle may suddenly stop/deaccelerate, and they may cause an accident (i.e., rBSM=0.75). After that, the receiving vehicle has to be aware of the neighboring vehicles which travel in the same direction and behind of the receiving vehicle and, lastly, the neighboring vehicles which travel in an opposite direction and passed the receiving vehicle.


### 4.3. Relative-Time Rank with respect to Distance

RTZ uses relative time as one of metrics to prioritize safety messages. Relative time is the time when two vehicles reach the same position. As a result, the transmitting vehicles with a shorter relative time to the receiving vehicle have a higher priority for BSM verification. Relative time can be determined by using velocity,v, acceleration, a, and current position of the transmitting vehicle, xtx, and current position of the receiving vehicle, xrx, by using a uniform linear motion equation for constant acceleration. The relative time, t′, can be determined when the position of the transmitting vehicle, xtx′, and the position of the receiving vehicle, xrx′, reach the same point (i.e., xrx′=xtx′):(7)12arx−atxt′2+vrx−vtxt′+xrx−xtx=0.There are two drawbacks using only relative time for ranking BSMs: (1) the assumption of constant acceleration may not be valid due to buffering and processing delay and (2) the vehicles nearby in the same direction have the same physical motion (e.g., velocity and acceleration); therefore, they may have high relative time even the messages between them are very important.To address the first drawback, we use the history to verify recent received BSMs in a buffer, which will be presented in Section4.5. To address the later drawbacks, we propose to use the ranking system which uses relative time with distance between transmitting and receiving vehicles. Since the value of relative time can be positive, negative, or infinity, depending on the receiving vehicle and neighboring vehicles acceleration, velocity, position, and direction, we normalize the value of relative time to a rank between [0,1]. Therefore, the rank of relative time, rrt, between vehicles i and j can be determined as follows:(8)rrt=21+ekt′,t′≥0,0,t′<0,where t′ is the relative time between the receiving vehicle i and the transmitting vehicle j and k is a constant value for adjusting the rank of relative time.Figure4 shows the example of relative-time rank for k=0.2. Figure 4 shows the rank of relative time for t′=2 second is 0.8, the rank of relative time for t′=4 second is 0.6, and for relative time with a high value, the rank will be close to zero. The value of k can be changed between (0,1] based on the traffic density or other parameters in the network. The value k affects the importance and prioritization of safety messages in each zone. The smaller value of k gives a higher rank to the relative-time value. As a result, BSM receives a higher rank, and it causes BSMs to have a higher opportunity to be verified.Figure 4
Relative-time rank fork = 0.2.In a high traffic environment, vehicles in the same direction travel with a similar velocity and acceleration. As a result, the relative-time value between two vehicles will be high (the relative-time rank becomes very low) when two vehicles are very close. The safety messages received from nearby vehicles are important since they are more likely to cause an accident. We combine the rank of a relative time,rrt, with distance’s rank, rdist, to improve the rank of such vehicles. The distance’s rank between vehicles i and j can be determined as follows:(9)rdist=1−dijr,where dij is the distance between receiving vehicle i and transmitting vehicle j and r is the one-hop communication range. Therefore, the rank of relative time, rrt, with respect to distance’s rank, rdist, of two vehicles i and j can be determined as follows:(10)rrd=αrrt+1−αrdist,where α is a weight in 0,1.


### 4.4. Combining Final Ranks

We presented three ranking metrics: (1) clustering neighboring vehicles into the zone (z) based on the average velocity and road configuration, (2) BSM rank (rBSM) according to road configuration and transmitting vehicle location and direction, and (3) rank of relative time with respect to distance (rrd). To enhance and prioritize BSMs in a receiving vehicle’s buffer, we combine the three ranking metrics:(11)rT=M−z−1γ+rrd+rBSM,γ>rrd+rBSM,where M is the total number of zones, z is the zone of the transmitting vehicle, and γ is the weight for adjusting the total rank. The highest rank will be inserted at the head of a buffer, and the lowest rank will be at the end of the buffer. The higher ranked BSMs are considered more relevant to the receiving vehicle. Since the transmitting vehicles may cause an accident to the receiving vehicle, their BSMs should verify as soon as possible.


### 4.5. History-Based Verification of Ranked BSM

In VANETs, each vehicle broadcasts BSMs every 100 ms or 300 ms [5]. As a result, a vehicle receives several messages from the same neighboring vehicles per second. In a high density network, a receiving vehicle’s buffer may be overloaded with BSMs from the same nearby transmitting vehicles and does not have a clear picture about the status of neighboring vehicles. To cope with this problem, we proposed history-based verification in which duplicate old safety messages will be removed from a receiving vehicle’s buffer.We assume that each vehicle in VANET keeps information of one-hop recent communication with neighboring vehicles. The information such as sender’s ID, velocity, acceleration, the rank information (e.g., zone, distance, and relative time), and received message status (e.g., verified, unverified, and dropped) are stored in the history. As shown in Figure5, when a vehicle receives a BSM from a neighboring vehicle i, BSMi, the receiving vehicle checks the ID of received BSMi with the history. If the receiving vehicle finds the ID of the transmitting vehicle in the history and the status of the message is unverified, the receiving vehicle removes the old message, BSMi−1, from the buffer and inserts the new BSMi into the buffer according to the BSM’s rank and updates the history. As a result, each vehicle has only one recent BSM in the buffer at any time. This causes the vehicle to be able to verify more relevant safety messages with significantly lower delay in VANETs from neighboring vehicles.Figure 5
History-based verification mechanism.Algorithm1 shows the steps for processing arrival BSMi from a transmitting vehicle i at a receiving vehicle. Upon a vehicle receiving BSM from a neighboring vehicle i, BSMi, the receiving vehicle determines the rank of the safety message based on a scheme. Then, the receiving vehicle checks the ID of the transmitting vehicle in the history. If the status of the previously received safety message, BSMi−1, is verified/dropped, then the receiving vehicle updates the history and the status of BSMi in the history to unverified and insert BSMi into the buffer according to its rank. Otherwise, the receiving vehicle removes the old received safety message, BSMi−1, from the buffer and inserts the new received safety message, BSMi, into the buffer according to its rank and updates the history and the status of the safety message to unverified.Algorithm 1:The procedure of managing history for a new arrival BSM.
(1)
Procedure (BSMi)
(2)
rank = prioritization scheme (BSMi)
(3)
If (status.BSMi−1.verified) or (status.BSMi−1.dropped):
(4)
Update-History (BSMi.ID, status.BSMi.unverified, BSMi)
(5)
Else If (status.BSMi−1.unverified):
(6)
Discard (BSMi−1) from buffer
(7)
Update-History (BSMi.ID, status.BSMi.unverified, BSMi)
(8)
Insert BSMi into buffer
(9)
End Procedure


## 4.1. Clustering Vehicles in Zones Using Velocity and Road Configuration

In RTZ, the range of zones is determined from the BSM arrival rate and BSM verification rate. However, due to the nature of the wireless channel and obstacle and density of vehicles, the BSM arrival rate can vary significantly. To address this issue, we propose to use the average velocity of neighboring vehicles in the one-hop communication range to determine the size of zones.We assume that every vehicle keeps the history of recent verified BSM from transmitting vehicles within the communication range. The stored information includes senders’ ID, velocity, and acceleration. Therefore, the receiving vehicle can determine the average velocity of the current neighboring vehicles at timet traveling in the same direction as(1)v¯t=1n∑i=0nvit,where n is the number of vehicles traveling in the same direction and within the communication range r and vit is the velocity of the neighboring vehicle i at time t.In this paper, we determine the range of danger zonerdz depending on two scenarios based on road configuration: first, road with a barrier between different directions, and second, road without a barrier between different directions.Case 1 (Road with a Barrier Separating Different Directions).
In this case, neighboring vehicles in the same direction as receiving vehicles are considered more important. To determine the range of danger zone, we consider the worst situation where the leading vehiclej stops suddenly, i.e., vjt=0. Let us denote the threshold time spacing between two adjacent vehicles in the same lane as tth (e.g., tth=2 seconds). This means that if the receiving vehicle keeps on traveling at the same speed vt, when the front vehicle suddenly is at a full rest (this is not physically correct; however, here we are assuming the worst case), the receiving vehicle will hit the front one before the driver can respond if the distance separation is less:(2)rdz=v¯ttth.
We let this distance be the range of the danger zone for barrier roads since the danger zone is defined to cover all vehicles that are too close for the drivers of these vehicles to respond. The vehicles in the danger zone include not only the vehicles in the front but also those in the back and on the sides since the vehicles in the back can also hit the receiving vehicle. Note that we use the average velocityv¯t of the vehicles in the same direction as the receiving vehicle at time t as the velocity to define the range of the danger zone since vehicles are in danger zones to each other.Case 2 (Road without Any Barrier Separating Different Directions).
In this case, neighboring vehicles in the opposite direction and the front of the receiving vehicle are considered more important since vehicles which travel in the opposite direction are able to cross over and cause an accident. Ifv′¯t denotes the average velocity of vehicles in the opposite direction at time t, the range of the danger zone for no-barrier roads is given as follows:(3)rdz=v′¯t+v¯ttth,where v′¯t+v¯t is the relative average speed of the vehicles in the opposite direction to the receiving vehicle. Figure 2 shows the concept of zones in VANETs, where the danger zone is denoted as zone 1. Note that the higher the vehicle density, the smaller the radius of the danger zone because the velocity of the vehicle in vicinity decreases. Assume that the size of zones increases with the same scale as that of the danger zone, and the number of zones, M, can be defined as follows:(4)M=rrdz.
Therefore, the zone,z, of the transmitting vehicle j at distance dij from the receiving vehicle i [15] is(5)z=Mdijr,dij≤r,M,dij>r,where z=1,2,…,M. The first zone, z=1, is called the danger zone which has the highest priority for verification of BSMs, and the other zones are called safe zones since the vehicles in that zones have some distance to the receiving vehicle.Figure 2
Concept of zones based on velocity of neighboring vehicles and road configuration.


## 4.2. Ranking BSM Using Road Configuration and Location and Direction

Location and direction of vehicles are very important to prioritize BSMs. In [15], RTZ used location and direction of the transmitting vehicles (quadrant) to broadly filter out the irrelevant BSMs. The transmitting vehicles that travel in opposite directions and passing a receiving vehicle are considered low priority (quadrant 4) compared to other vehicles.To improve the location and direction ranking system method in RTZ, HRTZ uses a decision tree to rank BSMs,rdt, more relevantly based on road configuration and a transmitting vehicle’s location and direction. As shown in Figure 3, BSM can receive a rank between 7 and 4 for roads with a barrier and 3 to 0 for roads without a barrier. The rank of BSM, rBSM, based on rdt can be normalized between [0,1] as follows:(6)rBSM=rdt−34,4≤rdt≤7,rdt+14,0≤rdt≤3.Figure 3
BSM rank based on road configuration (with/without a barrier), location, and direction of transmitting vehicles.Case Study 1 (Road Has a Barrier between Different Directions).
A vehicle has to be more aware of neighboring vehicles that travel in the same direction and front of the receiving vehicles since these vehicles may suddenly stop/deaccelerate and can cause an accident. Therefore, the BSMs for these neighboring vehicles receive the highest priority (i.e.,rBSM=1). The other important neighboring vehicles are the vehicles which travel in the same direction and behind the receiving vehicle. The receiving vehicle has to be aware of those neighboring vehicles which travel close to or in a situation when the receiving vehicle wants to change the lane (i.e., rBSM=0.75). After that, the receiving vehicle may need to be aware of neighboring vehicles which travel in an opposite direction in front and behind of the receiving vehicle.Case Study 2 (Road Does Not Have a Barrier between Different Directions).
A vehicle has to be more aware of neighboring vehicles which travel in the opposite direction and front of the receiving vehicle since these neighboring vehicles may cross over to the receiving vehicle lane and cause an accident. Therefore, the BSMs received from those vehicles have the highest rankrBSM=1. On the contrary, neighboring vehicles traveling in the same direction and front of the receiving vehicle may suddenly stop/deaccelerate, and they may cause an accident (i.e., rBSM=0.75). After that, the receiving vehicle has to be aware of the neighboring vehicles which travel in the same direction and behind of the receiving vehicle and, lastly, the neighboring vehicles which travel in an opposite direction and passed the receiving vehicle.


## 4.3. Relative-Time Rank with respect to Distance

RTZ uses relative time as one of metrics to prioritize safety messages. Relative time is the time when two vehicles reach the same position. As a result, the transmitting vehicles with a shorter relative time to the receiving vehicle have a higher priority for BSM verification. Relative time can be determined by using velocity,v, acceleration, a, and current position of the transmitting vehicle, xtx, and current position of the receiving vehicle, xrx, by using a uniform linear motion equation for constant acceleration. The relative time, t′, can be determined when the position of the transmitting vehicle, xtx′, and the position of the receiving vehicle, xrx′, reach the same point (i.e., xrx′=xtx′):(7)12arx−atxt′2+vrx−vtxt′+xrx−xtx=0.There are two drawbacks using only relative time for ranking BSMs: (1) the assumption of constant acceleration may not be valid due to buffering and processing delay and (2) the vehicles nearby in the same direction have the same physical motion (e.g., velocity and acceleration); therefore, they may have high relative time even the messages between them are very important.To address the first drawback, we use the history to verify recent received BSMs in a buffer, which will be presented in Section4.5. To address the later drawbacks, we propose to use the ranking system which uses relative time with distance between transmitting and receiving vehicles. Since the value of relative time can be positive, negative, or infinity, depending on the receiving vehicle and neighboring vehicles acceleration, velocity, position, and direction, we normalize the value of relative time to a rank between [0,1]. Therefore, the rank of relative time, rrt, between vehicles i and j can be determined as follows:(8)rrt=21+ekt′,t′≥0,0,t′<0,where t′ is the relative time between the receiving vehicle i and the transmitting vehicle j and k is a constant value for adjusting the rank of relative time.Figure4 shows the example of relative-time rank for k=0.2. Figure 4 shows the rank of relative time for t′=2 second is 0.8, the rank of relative time for t′=4 second is 0.6, and for relative time with a high value, the rank will be close to zero. The value of k can be changed between (0,1] based on the traffic density or other parameters in the network. The value k affects the importance and prioritization of safety messages in each zone. The smaller value of k gives a higher rank to the relative-time value. As a result, BSM receives a higher rank, and it causes BSMs to have a higher opportunity to be verified.Figure 4
Relative-time rank fork = 0.2.In a high traffic environment, vehicles in the same direction travel with a similar velocity and acceleration. As a result, the relative-time value between two vehicles will be high (the relative-time rank becomes very low) when two vehicles are very close. The safety messages received from nearby vehicles are important since they are more likely to cause an accident. We combine the rank of a relative time,rrt, with distance’s rank, rdist, to improve the rank of such vehicles. The distance’s rank between vehicles i and j can be determined as follows:(9)rdist=1−dijr,where dij is the distance between receiving vehicle i and transmitting vehicle j and r is the one-hop communication range. Therefore, the rank of relative time, rrt, with respect to distance’s rank, rdist, of two vehicles i and j can be determined as follows:(10)rrd=αrrt+1−αrdist,where α is a weight in 0,1.


## 4.4. Combining Final Ranks

We presented three ranking metrics: (1) clustering neighboring vehicles into the zone (z) based on the average velocity and road configuration, (2) BSM rank (rBSM) according to road configuration and transmitting vehicle location and direction, and (3) rank of relative time with respect to distance (rrd). To enhance and prioritize BSMs in a receiving vehicle’s buffer, we combine the three ranking metrics:(11)rT=M−z−1γ+rrd+rBSM,γ>rrd+rBSM,where M is the total number of zones, z is the zone of the transmitting vehicle, and γ is the weight for adjusting the total rank. The highest rank will be inserted at the head of a buffer, and the lowest rank will be at the end of the buffer. The higher ranked BSMs are considered more relevant to the receiving vehicle. Since the transmitting vehicles may cause an accident to the receiving vehicle, their BSMs should verify as soon as possible.


## 4.5. History-Based Verification of Ranked BSM

In VANETs, each vehicle broadcasts BSMs every 100 ms or 300 ms [5]. As a result, a vehicle receives several messages from the same neighboring vehicles per second. In a high density network, a receiving vehicle’s buffer may be overloaded with BSMs from the same nearby transmitting vehicles and does not have a clear picture about the status of neighboring vehicles. To cope with this problem, we proposed history-based verification in which duplicate old safety messages will be removed from a receiving vehicle’s buffer.We assume that each vehicle in VANET keeps information of one-hop recent communication with neighboring vehicles. The information such as sender’s ID, velocity, acceleration, the rank information (e.g., zone, distance, and relative time), and received message status (e.g., verified, unverified, and dropped) are stored in the history. As shown in Figure5, when a vehicle receives a BSM from a neighboring vehicle i, BSMi, the receiving vehicle checks the ID of received BSMi with the history. If the receiving vehicle finds the ID of the transmitting vehicle in the history and the status of the message is unverified, the receiving vehicle removes the old message, BSMi−1, from the buffer and inserts the new BSMi into the buffer according to the BSM’s rank and updates the history. As a result, each vehicle has only one recent BSM in the buffer at any time. This causes the vehicle to be able to verify more relevant safety messages with significantly lower delay in VANETs from neighboring vehicles.Figure 5
History-based verification mechanism.Algorithm1 shows the steps for processing arrival BSMi from a transmitting vehicle i at a receiving vehicle. Upon a vehicle receiving BSM from a neighboring vehicle i, BSMi, the receiving vehicle determines the rank of the safety message based on a scheme. Then, the receiving vehicle checks the ID of the transmitting vehicle in the history. If the status of the previously received safety message, BSMi−1, is verified/dropped, then the receiving vehicle updates the history and the status of BSMi in the history to unverified and insert BSMi into the buffer according to its rank. Otherwise, the receiving vehicle removes the old received safety message, BSMi−1, from the buffer and inserts the new received safety message, BSMi, into the buffer according to its rank and updates the history and the status of the safety message to unverified.Algorithm 1:The procedure of managing history for a new arrival BSM.
(1)
Procedure (BSMi)
(2)
rank = prioritization scheme (BSMi)
(3)
If (status.BSMi−1.verified) or (status.BSMi−1.dropped):
(4)
Update-History (BSMi.ID, status.BSMi.unverified, BSMi)
(5)
Else If (status.BSMi−1.unverified):
(6)
Discard (BSMi−1) from buffer
(7)
Update-History (BSMi.ID, status.BSMi.unverified, BSMi)
(8)
Insert BSMi into buffer
(9)
End Procedure


## 5. Simulation Setup and Evaluation Metrics

A highway simulation scenario is conducted in order to evaluate HRTZ performance. We consider high density scenario to show the effectiveness of the scheme. In order to simulate communication between vehicles, NS3.19 [50] is used with VANET-Highway version 2 module [51]. The VANET highway module allows vehicles to change their speed and lane without causing an accident in the VANET. To simulate the wireless channel, the log-distance propagation path loss model was used similar to the work in [15]. The one-hop communication range for vehicle-to-vehicle 300 meters was used similar as to other studies and experimental testbeds in [7, 12, 15, 52–57]. The rest of simulation variables and their values is presented in Table 2.Table 2
Simulation variables.
Parameter
Value
Number of lanes
4 lanes/direction
Lane width
3 m
Road length
2500 m
Number of vehicles entering highway
3 vehicles/s
Initial vehicle velocity
65–85 km/h
BSM interval
100 ms
BSM lifetime
2 s
BSM processing time
5 ms
BSM size
254 bytes
Buffer capacity
200 pkts
Data rate
6 Mb/sThe simulation duration is 300 s where the first 120 s is a warmup period to make sure that the highway is full of vehicles. The length of highway is 2500 meters. However, the data were collected from the vehicles within 1500 meters from the middle. The data are collected from and averaged across 100 randomly selected vehicles to represent all vehicles in network. The performance of HRTZ is compared with the following receiver-based verification schemes:(1)
First-in-first-out (FIFO) : WAVE protocol [5] uses the FIFO approach as a baseline which gives no priority to received BSMs in a buffer.(2)
Last-in-first-out (LIFO): the new arrival BSMs are verified first.(3)
Serve-in-random-order (SIRO) [18]: BSMs are randomly chosen from a buffer for verification.(4)
Li and Chigan’s [12] method (referred to as the Li scheme in this paper): BSMs are verified based on a fix probability value and message rank. The rank of BSMs depends on distance and number of hops between transmitters and receivers. The BSMs with a higher rank have a higher chance to be verified.(5)
Relative-time zone priority (RTZ) scheme [15]: messages are prioritized based on transmitter’s location and direction, close proximity, and relative time in a buffer. As a result, the BSMs from nearby vehicles with smaller relative time have a higher chance to be verified.The following six metrics are used to study the performance of different schemes for verifying safety messages:(1)
Packet verified is the number of BSMs verified.(2)
Packet loss is the number of packets that are dropped at a receiver. The packets are dropped because of (I) buffer overflow, (II) exceeded lifetime of message, and (III) scheme design.(3)
Delay is the time from a transmitting vehicle sends a BSM to the time when the BSM is verified at a receiving vehicle. It is important that the delay of verified BSMs be small such that safety applications are able to respond to a safety incident before it happens.(4)
Intermessage delay [58, 59] is the latency of back-to-back BSMs received from the same transmitting vehicle. This metrics shows the up-to-date verified BSMs.(5)
Duplicate message ratio is the ratio of duplicate BSMs of neighboring vehicles at a receiving vehicle’s buffer at specific time instants. This metric shows how duplicate BSMs have an effect on awareness and delay of verified messages.(6)
Awareness quality level of up-to-date messages (AQLU) is the modified version of awareness quality level (AQL) metrics proposed in [60]. AQLU shows the average ratio of vehicles’ awareness in an area where neighboring vehicles are discovered via verified messages with a delay less than ε compared to the actual number of vehicles in that area in specific time instant:(12)AQLUT,z,ε=∑j=1T∑i∈VAztεjiT×V,where Aztεji is the awareness of vehicles i from transmitting vehicle j in zone z at time tεj where the verified BSMs from vehicle j have delay less than ε. The records of awareness of V randomly selected vehicles are collected for T different time instants. AQLUT,z,ε shows the average of the collected awareness records over all vehicles and time instants.


## 6. Simulation Results

### 6.1. BSM Arrival Rate in High Density Traffic Scenario

Figure6 shows the cumulative probability distribution of the BSM arrival rate in a high density network condition where each vehicle broadcasts BSMs every 100 ms. Since the verification process of BSM’s signature with the ECDSA P-224 curve takes around ∼4.97 ms [16, 17], a receiving vehicle is able to verify 200 messages per second on average. However, the message arrival rate is always higher than 200 messages per second. Therefore, vehicles needed to select and verify the most relevant and recent received BSMs from neighboring vehicles.Figure 6
The cumulative probability of number of packets received per second by each vehicle.


### 6.2. Packet Loss vs BSM Ranks

Figure7 shows the cumulative percentage of the packet dropped for different locations and directions of transmitting vehicles (quadrant). In our proposed ranking system in Section 4.2, the BSMs which transmit from neighboring vehicles traveling in the opposite direction and behind the receiving vehicle receive the lowest rank (e.g., these vehicles may not cause any safety incident to the receiving vehicle). In the Li scheme, the percentage of packet loss is very high compared to other schemes. This is because message verification in the Li scheme relies on a filter probability p, while that of other schemes relay on only the processing time (i.e., 42% of the received messages dropped). Therefore, the Li scheme with a filter probability 0.9 can verify only 32% of received messages, and 68% of received messages are dropped. HRTZ has the lowest packet dropped for different quadrants compared to FIFO, LIFO, SIRO, Li, and RTZ. It means that HRTZ gives more opportunity to relevant BSMs’ neighboring vehicles in quadrants 1, 2, and 3 to be verified.Figure 7
The cumulative percentage of packet loss with respect to different locations and directions (quadrant) of transmitting vehicles.


### 6.3. Packet Loss vs Distance between Vehicles

Figure8 shows packet loss for distances between receiving and transmitting vehicles. HRTZ and RTZ achieve the best performance across all distances since our proposed schemes use zones, locations, and directions (quadrant) of transmitting vehicles to prioritize BSMs at a receiving vehicle. HRTZ and RTZ achieve ∼0% packet loss for neighboring vehicles within a distance less than 25 m. HRTZ has a lower packet loss for vehicles in the vicinity that have a distance greater than 50 m compared to RTZ and other approaches. This is because HRTZ gives priority to more recent and relevant safety messages to be verified.Figure 8
The cumulative percentage of packet loss with respect to distances between transmitting and receiving vehicles.


### 6.4. BSMs Duplicate Rate vs Distance between Vehicles

Figure9 shows the rate of receiving duplicated messages in a receiver’s buffer across the distances. HRTZ and Li achieve the best performance of ∼0% duplicated message in the buffer across all distances. Since the Li rank scheme is a probabilistic scheme and it has a high drop rate, it causes the buffer of receiving vehicles to be empty. HRTZ uses the history to check and remove duplicated messages in the buffer; therefore, each vehicle has only one recent safety message in the buffer at any time. In RTZ, by increasing the distance between receiving and transmitting vehicles, the rate of duplicated messages increases. This is because the RTZ scheme gives a higher priority to safety messages coming from nearby vehicles, so the safety messages received from distant neighboring vehicles have to wait in the buffer. Therefore, the number of duplicated messages from those vehicles will increase.Figure 9
The cumulative percentage of the received duplicated messages from neighboring vehicles across distances at a receiving vehicle’s buffer.


### 6.5. Verification Rate vs Delay of Verified BSMs

One of the important metrics for safety applications is delay of verified messages. BSMs verified with high delay may be out-of-date and may cause safety applications unable to respond properly to safety incidents. Figure10 shows the cumulative percentage of verified messages for different schemes with respect to delay. In LIFO and Li schemes, the delay of most verified messages are less than ∼200 ms. This is because in LIFO new arrival BSMs always have a higher priority to be verified and in the Li rank, the buffer of receiving vehicles is empty most of the time due to the probabilistic nature of the scheme. In FIFO, the priority is always given to the oldest BSM, and FIFO achieves the worst performance. Our proposed HRTZ is able to achieve the lowest verification delay with highest percentage of packets verification compared to the rest of the scheme. It is able to verify ∼99% of BSMs with a delay less than 200 ms. This is because HRTZ uses the history to remove old and duplicated BSMs from the buffer and gives more opportunity to recent received BSMs from neighboring vehicles.Figure 10
The cumulative percentage of verified messages versus delay of verified messages.


### 6.6. Delay of Verified BSMs vs Distance between Vehicles

Figure11 shows average delay of verified BSMs for distance between receiving and transmitting vehicles. In LIFO and Li, most of safety messages are verified on an average of less than 40 ms across distances. HRTZ and RTZ achieves delay less than 40 ms for close distance (i.e., 50 m). However, HRTZ achieves delay less than 100 ms for distance less than 175 m compared to RTZ which is increased to 300 ms. This is because, RTZ verifies some old and duplicate safety messages from neighboring vehicles.Figure 11
Average delay of verified messages versus distances between vehicles.


### 6.7. Intermessage Delay vs Distance between Vehicles

Figure12 shows the average intermessage delay between the receiving vehicle and transmitting vehicles across different distances. It is important for safety applications to regularly receive recent BSMs to identify any danger on time. Since every vehicle generates BSM every 100 ms in our simulation, the intermessage delay for received BSMs on average will be above 100 ms. The Li scheme achieves the worst performance since the probability of the message verified will decrease by increasing distance between receiving and transmitting vehicles. In HRTZ and RTZ, intermessage delay for distance less than 75 m is less than 150 ms. HRTZ intermessage delay will increase when the distance is more than 75 m since it drops duplicated and old safety messages from the buffer and verified only the recent BSMs.Figure 12
The intermessage delay for verified messages versus distances between vehicles.


### 6.8. Awareness Quality Level of Up-To-Date Messages vs Distance between Vehicles

Figure13 shows the awareness quality level of up-to-date messages, AQLU, defined in (12) for different distances. HRTZ and RTZ provide higher awareness for close by vehicles (i.e., within 25 m). HRTZ achieves better results for distance more than 25 m compared to RTZ. Since FIFO, LIFO, and SIRO do not consider vehicles’ locations and directions, their AQLU for the close distance area (i.e., >75 m) are lower than our approaches. Li scheme achieves the lowest awareness at most of distances as it verifies only some BSMs. In a high density traffic condition, it is important that vehicles are immediately aware of neighboring vehicles in the vicinity especially the close by vehicles. As shown in Figure 13, HRTZ achieves higher AQLU for nearby vehicles and lower AQLU for distant vehicles (i.e., >75 m).Figure 13
AQLU of receiving vehicles with respect to distances between vehicles.


## 6.1. BSM Arrival Rate in High Density Traffic Scenario

Figure6 shows the cumulative probability distribution of the BSM arrival rate in a high density network condition where each vehicle broadcasts BSMs every 100 ms. Since the verification process of BSM’s signature with the ECDSA P-224 curve takes around ∼4.97 ms [16, 17], a receiving vehicle is able to verify 200 messages per second on average. However, the message arrival rate is always higher than 200 messages per second. Therefore, vehicles needed to select and verify the most relevant and recent received BSMs from neighboring vehicles.Figure 6
The cumulative probability of number of packets received per second by each vehicle.


## 6.2. Packet Loss vs BSM Ranks

Figure7 shows the cumulative percentage of the packet dropped for different locations and directions of transmitting vehicles (quadrant). In our proposed ranking system in Section 4.2, the BSMs which transmit from neighboring vehicles traveling in the opposite direction and behind the receiving vehicle receive the lowest rank (e.g., these vehicles may not cause any safety incident to the receiving vehicle). In the Li scheme, the percentage of packet loss is very high compared to other schemes. This is because message verification in the Li scheme relies on a filter probability p, while that of other schemes relay on only the processing time (i.e., 42% of the received messages dropped). Therefore, the Li scheme with a filter probability 0.9 can verify only 32% of received messages, and 68% of received messages are dropped. HRTZ has the lowest packet dropped for different quadrants compared to FIFO, LIFO, SIRO, Li, and RTZ. It means that HRTZ gives more opportunity to relevant BSMs’ neighboring vehicles in quadrants 1, 2, and 3 to be verified.Figure 7
The cumulative percentage of packet loss with respect to different locations and directions (quadrant) of transmitting vehicles.


## 6.3. Packet Loss vs Distance between Vehicles

Figure8 shows packet loss for distances between receiving and transmitting vehicles. HRTZ and RTZ achieve the best performance across all distances since our proposed schemes use zones, locations, and directions (quadrant) of transmitting vehicles to prioritize BSMs at a receiving vehicle. HRTZ and RTZ achieve ∼0% packet loss for neighboring vehicles within a distance less than 25 m. HRTZ has a lower packet loss for vehicles in the vicinity that have a distance greater than 50 m compared to RTZ and other approaches. This is because HRTZ gives priority to more recent and relevant safety messages to be verified.Figure 8
The cumulative percentage of packet loss with respect to distances between transmitting and receiving vehicles.


## 6.4. BSMs Duplicate Rate vs Distance between Vehicles

Figure9 shows the rate of receiving duplicated messages in a receiver’s buffer across the distances. HRTZ and Li achieve the best performance of ∼0% duplicated message in the buffer across all distances. Since the Li rank scheme is a probabilistic scheme and it has a high drop rate, it causes the buffer of receiving vehicles to be empty. HRTZ uses the history to check and remove duplicated messages in the buffer; therefore, each vehicle has only one recent safety message in the buffer at any time. In RTZ, by increasing the distance between receiving and transmitting vehicles, the rate of duplicated messages increases. This is because the RTZ scheme gives a higher priority to safety messages coming from nearby vehicles, so the safety messages received from distant neighboring vehicles have to wait in the buffer. Therefore, the number of duplicated messages from those vehicles will increase.Figure 9
The cumulative percentage of the received duplicated messages from neighboring vehicles across distances at a receiving vehicle’s buffer.


## 6.5. Verification Rate vs Delay of Verified BSMs

One of the important metrics for safety applications is delay of verified messages. BSMs verified with high delay may be out-of-date and may cause safety applications unable to respond properly to safety incidents. Figure10 shows the cumulative percentage of verified messages for different schemes with respect to delay. In LIFO and Li schemes, the delay of most verified messages are less than ∼200 ms. This is because in LIFO new arrival BSMs always have a higher priority to be verified and in the Li rank, the buffer of receiving vehicles is empty most of the time due to the probabilistic nature of the scheme. In FIFO, the priority is always given to the oldest BSM, and FIFO achieves the worst performance. Our proposed HRTZ is able to achieve the lowest verification delay with highest percentage of packets verification compared to the rest of the scheme. It is able to verify ∼99% of BSMs with a delay less than 200 ms. This is because HRTZ uses the history to remove old and duplicated BSMs from the buffer and gives more opportunity to recent received BSMs from neighboring vehicles.Figure 10
The cumulative percentage of verified messages versus delay of verified messages.


## 6.6. Delay of Verified BSMs vs Distance between Vehicles

Figure11 shows average delay of verified BSMs for distance between receiving and transmitting vehicles. In LIFO and Li, most of safety messages are verified on an average of less than 40 ms across distances. HRTZ and RTZ achieves delay less than 40 ms for close distance (i.e., 50 m). However, HRTZ achieves delay less than 100 ms for distance less than 175 m compared to RTZ which is increased to 300 ms. This is because, RTZ verifies some old and duplicate safety messages from neighboring vehicles.Figure 11
Average delay of verified messages versus distances between vehicles.


## 6.7. Intermessage Delay vs Distance between Vehicles

Figure12 shows the average intermessage delay between the receiving vehicle and transmitting vehicles across different distances. It is important for safety applications to regularly receive recent BSMs to identify any danger on time. Since every vehicle generates BSM every 100 ms in our simulation, the intermessage delay for received BSMs on average will be above 100 ms. The Li scheme achieves the worst performance since the probability of the message verified will decrease by increasing distance between receiving and transmitting vehicles. In HRTZ and RTZ, intermessage delay for distance less than 75 m is less than 150 ms. HRTZ intermessage delay will increase when the distance is more than 75 m since it drops duplicated and old safety messages from the buffer and verified only the recent BSMs.Figure 12
The intermessage delay for verified messages versus distances between vehicles.


## 6.8. Awareness Quality Level of Up-To-Date Messages vs Distance between Vehicles

Figure13 shows the awareness quality level of up-to-date messages, AQLU, defined in (12) for different distances. HRTZ and RTZ provide higher awareness for close by vehicles (i.e., within 25 m). HRTZ achieves better results for distance more than 25 m compared to RTZ. Since FIFO, LIFO, and SIRO do not consider vehicles’ locations and directions, their AQLU for the close distance area (i.e., >75 m) are lower than our approaches. Li scheme achieves the lowest awareness at most of distances as it verifies only some BSMs. In a high density traffic condition, it is important that vehicles are immediately aware of neighboring vehicles in the vicinity especially the close by vehicles. As shown in Figure 13, HRTZ achieves higher AQLU for nearby vehicles and lower AQLU for distant vehicles (i.e., >75 m).Figure 13
AQLU of receiving vehicles with respect to distances between vehicles.


## 7. Conclusion

In high density VANETs, the message arrival rate can be higher than the verification rate of safety messages at a vehicle. We proposed the history-based relative-time zone (HRTZ) message prioritization scheme, which enhances the performance over the relative-time zone (RTZ) priority algorithm, for selecting the most relevant received safety messages at a receiver for verification. HRTZ scheme uses three criteria to prioritize safety messages, namely, zone rank, BSM rank, and relative-time rank. To obtain better performance, HRTZ uses the following additional information: (1) history of one-hop communication to determine relative velocity of transmitting vehicles based on road configuration to dynamically cluster received BSMs more accurately into zones, (2) a combination of road configuration (road with/without a barrier) with location and direction of transmitting vehicles to rank received BSMs and to improve the prioritization of arrival BSMs, and (3) a combination of relative-time rank with distance rank to improve the rank of BSMs from nearby transmitting vehicles which are traveling in the same direction as a receiving vehicle and have similar physical motions. In addition, HRTZ keeps only recent and up-to-date received BSMs in the buffer. The higher rank for BSM indicates that the transmitting vehicle is more dangerous, and the BSM is verified with a higher chance. Compared with the default FIFO, RTZ, and other schemes, the simulation results show that HRTZ achieves better performance in terms of lower packet loss, higher awareness, and lower message verification delay for vehicles in the vicinity. HRTZ achieves ∼0% packet loss for nearby vehicles. The delays of verified safety messages are 20 ms and 200 ms on average for neighboring vehicles within a distance less than 50 m and for distant neighboring vehicles, respectively. The intermessage delay is less than 600 ms across all distances.



---

*Source: 8568912-2019-03-12.xml*