Efficient Dissemination of Safety Messages in Vehicle Ad Hoc Network Environments

Abstract

The number of people owning vehicles has been steadily growing, resulting in increased numbers of vehicles on the roads, making roads more congested, and increasing the risk of accidents. In addition, heavy rain, snow, and fog have increased due to abnormal weather caused by global warming. These bad weather conditions can also affect the safety of vehicles and drivers. The need to disseminate safety messages on the social Internet of Vehicles due to these problems has been steadily increasing. In this paper, we propose an efficient safety message dissemination scheme that focuses on urban environments with high vehicle density and mobility to address these problems. The proposed scheme reduces packet loss by considering frequent cluster departures and subscriptions through an efficient cluster management technique. In a vehicle-to-vehicle environment, the dissemination of safety messages is divided into intracluster and intercluster emergencies, as well as a general safety message dissemination technique. In a vehicle-to-infrastructure environment, the proposed scheme reduces the number of processing requests and duplicate messages made to roadside units (RSUs) through a request operation process for each vehicle and an RSU scheduling technique. We conducted several performance evaluations of message packet loss and the number of RSU processing requests to demonstrate the superiority of the proposed scheme.

1. Introduction

Studies using a vehicular ad hoc network (VANET) to improve user driving convenience and traffic safety are currently being conducted [1,2,3,4,5]. In particular, services are being implemented that provide users with safety messages to avoid road accidents and find less congested routes, thus reducing fuel consumption and air pollution. The most basic safety message dissemination scheme is based on broadcasts [6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]. However, broadcast-based message dissemination causes the broadcast storm phenomenon, which causes excessive transmission delay, packet loss, transmission failure, and dissemination interference, and degrades overall network performance. Furthermore, broadcast storms occur more frequently in urban environments with high vehicle density.

Several schemes have been proposed for disseminating messages in a VANET environment [12,13,14]. However, the existing schemes are based on probabilistic schemes, which can cause unacceptable communication delays in real road environments [12]. Moreover, the existing schemes do not consider the frequent subscriptions and departures of vehicle clusters [13]. The more frequently vehicles departure from the cluster, the more message exchanges are required to maintain the cluster result in substantial safety message packet loss. In addition, they do not consider the various message types and the roadside unit (RSU) environment [13,14]. We need to use the V2I environment to efficiently disseminate the safety messages.

In this paper, we propose a safety message dissemination scheme that uses collaboration between vehicles in a VANET environment. The proposed scheme does consider various message types and the RSU environment. The urban environment considered in the proposed scheme has a higher need than rural environments for safety messages due to the higher traffic volume and a greater chance of sudden congestion and emergency situations arising. Traffic in urban environments also moves in different directions, such as at intersections, in contrast to one-way roads such as highways. Therefore, the proposed scheme disseminates safety messages considering the high mobility and density of vehicles. In particular, we propose a scheme to quickly recover the cluster if the cluster collapses due to the departure of the vehicles. It also performs cluster-based safety message dissemination considering both vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) environments.

This paper is organized as follows. Section 2 introduces related research and analyzes the differences and features of each scheme. Section 3 describes the cluster management, V2V, and V2I communication techniques for the proposed safety message dissemination scheme. Section 4 presents the results of performance evaluations conducted to demonstrate the superiority of the proposed scheme. Section 5 concludes this paper and describes future research.

2. Related Work

Broadcast-based message dissemination generates many duplicate messages, causing packet collisions and transmission delays. Recently, researchers have studied several message dissemination schemes to address these issues.

The reliable emergency message dissemination (REMD) scheme has been proposed [12], which ensures message dissemination reliability by performing the optimal number of broadcasts. REMD measures the quality of the vehicle’s wireless communication reception and uses this to calculate the optimal number of message repetitions. It then selects forwarders based on this information. In REMD, each hop’s forwarder performs cooperative communication to improve the network’s reliability.

Position-based emergency message dissemination (PBE), a scheme that disseminates location-based emergency messages by forming clusters, has also been proposed [13]. The proposed environment supports urban areas with high traffic density and bidirectional traffic with multiple lanes. Vehicles form clusters based on their speed and direction of movement. Each cluster consists of one cluster head (CH) and one or more cluster members (CMs). In PBE, the probability of emergency message dissemination between the vehicles is modeled using the Nakagami-m probability distribution.

A centralized scheduling algorithm within the RSU coverage area and a temporary message dissemination strategy outside the coverage area have also been proposed [14]. This scheme considers the highly dynamic network topology due to the high mobility of vehicles and the limited infrastructure-to-vehicle (I2V) bandwidth. The scheme analyzes how the dynamic network topology and limited bandwidth impact the number of message items vehicles can retrieve.

Enhanced cooperative load balancing (ECLB) has been proposed [15]. ECLB considers a multi-RSU environment. They emphasized the necessity of RSU scheduling to disseminate messages in a VANET. In addition, they proposed the RSU scheduling scheme using cooperation of multi-RSU. It was shown that when considering the remaining delay tolerance of submitted requests and the knowledge of fixed road layout, the performance of the cooperative load balancing system can be further improved significantly.

Since the REMD scheme for urban vehicle networks [12] uses a probability-based technique with Nakagami-m distribution, this may cause unacceptable communication delay errors in actual road environments. Location-based emergency message dissemination (PBE) for the Internet of Vehicles [13] does not consider the frequent cluster departures of vehicles due to the various directions of vehicles. Therefore, in PBE, the more frequent the CH’s departure from the cluster, the more score comparisons among CMs occur to select the next CH. The message exchanges required for this process result in substantial safety message packet loss. This scheme also does not consider various safety message types. Finally, this scheme does not consider the RSU environment. RSU support-adaptive scheduling for intervehicle message sharing in bidirectional road scenarios [14,15] focuses on RSUs, lacks detailed operations for message dissemination in environments without RSUs, and does not consider the RSU load. For efficient message distribution, a distribution scheme considering both V2V and V2I environments is required.

3. The Proposed Safety Message Dissemination Scheme

3.1. Overall Structure

The goal of this paper is to propose an efficient message dissemination scheme to reduce packet loss and decrease the number of duplicate requests and messages. The proposed scheme has the following features. It uses an efficient cluster management technique to reduce packet loss by considering frequent cluster departures and subscriptions in urban environments with high vehicle density and mobility. We especially consider the high mobility in the intersections of urban environments. In V2V environments, the message dissemination scheme can reduce the number of messages and broadcast storms through a detailed message dissemination process of clustered vehicles. In V2I environments, the safety message dissemination scheme proposes different formulas and operation processes for RSU scheduling to reduce the RSU’s load and the number of duplicate messages.

Safety messages are divided into emergency and general safety messages in this study. Emergency safety messages are messages that must be disseminated regardless of the desired reception due to high accident rates. They are defined as having a message ID, occurrence location and time, and maintaining urgency, and they inform surrounding vehicles of the emergency situation, with a specified minimum guaranteed life. General safety messages contribute to safety and are selectively received based on user settings. They have no urgency and communicate through requests and responses from vehicles that require general safety messages rather than forced dissemination. The request timing of general safety messages is divided into automatic required time requests based on the vehicle’s location and settings, and direct requests by users. Since each vehicle has a different destination, direction, and speed, and each user has a different required time for general safety messages, time is not considered. Therefore, in this study, the required time was assumed to be given for each vehicle or general safety message. Referring to the Korean Ministry of Land, Infrastructure and Transport C-ITS safety service plan [22], emergency safety messages include high-accident-rate road hazard information, vehicle collision prevention, and emergency situation warnings. General safety messages include location-based traffic information, yellow bus operation guidance, and school zone arrival and departure notifications. This study sets the road infrastructure as RSUs. Because RSUs require installation and maintenance costs, it is appropriate to install them in urban environments with higher vehicle traffic volume than in rural areas. Therefore, urban environments must consider both V2V and V2I environments.

The proposed scheme consists of three techniques to efficiently disseminate emergency and general safety messages in an urban environment. First, cluster management is a technique that forms clusters of vehicles with similar locations, directions, and speeds. The cluster management technique can efficiently maintain and manage clusters considering frequent cluster departures and subscriptions caused by the high mobility of urban vehicles. Second, the safety message dissemination scheme in a V2V environment uses a technique where vehicles, based in clusters, take on different roles to efficiently deliver messages to one another. The safety message dissemination scheme is divided into intracluster and intercluster communication. Third, the safety message dissemination scheme in a V2I environment uses a technique where vehicles entering the RSU’s communication range receive assistance from the RSU to disseminate safety messages. In a V2I environment, the safety message dissemination scheme is divided into a cluster-based request scheme and an RSU scheduling scheme.

Figure 1 shows the proposed safety message dissemination in an urban environment. V2V communication is a scheme where vehicles with similar locations, directions, and speeds form clusters and disseminate safety messages. The cluster consists of the cluster head (CH), which leads to the cluster and cluster members (CMs). When a vehicle detects an emergency situation, it generates an emergency safety message. This message is disseminated to nearby vehicles according to the proposed V2V safety message dissemination scheme. General safety messages are delivered based on request messages. In the proposed scheme, when the CH enters the RSU’s communication range, it collaborates with the RSU to disseminate emergency safety messages. Additionally, if the CH has general safety messages needed for its cluster, it requests them from the RSU. When the RSU receives a request for emergency safety messages or general safety messages, it considers factors such as the vehicle’s safety message holding rate and request rate to disseminate the safety messages.

3.2. Cluster Management

Urban environments are characterized by high vehicle mobility and density. In such environments, if all vehicles request or disseminate messages, excessive transmission delays may occur due to the broadcast storm phenomenon. Therefore, to efficiently disseminate safety messages, it is necessary for each vehicle to form a cluster and perform distinct roles. Here, a cluster management scheme is needed to configure and maintain clusters in a way that minimizes cluster management costs and allows clusters to last longer. Cluster management can be divided into the cluster subscription algorithm and the CH candidate algorithm for cluster maintenance.

Figure 2 shows the overall process of the proposed cluster management technique. The initial state of all vehicles is IN. When a vehicle in the IN state receives a CHA from nearby vehicles, it subscribes to the cluster. Once a vehicle subscribes to a cluster, it becomes a CM. If the vehicle does not subscribe to any cluster within a certain period, it declares itself as a CH and broadcasts a CHA. All vehicles subscribed to a cluster perform V2V communication. Finally, when a vehicle departs from the cluster, it returns to the IN state.

3.2.1. Cluster Subscription

The purpose of clustering is to differentiate the roles of each vehicle, reduce duplicate messages, and improve the reception rate of safety messages. However, in urban vehicle environments with high mobility and varying travel directions, clusters frequently need to be reconfigured. If the urban vehicle environment is not taken into consideration, high cluster management costs are incurred. The purpose of the proposed cluster subscription algorithm is to form clusters with vehicles that have similar locations, speeds, and directions, allowing the cluster to last longer.

Algorithm 1 shows the cluster subscription algorithm. Vehicles periodically broadcast basic safety messages (BSMs) to share their basic state information with nearby vehicles. The CH uses BSMs to send CHAs to unsubscribed vehicles (IN). Vehicles that receive the CHA send a cluster invitation confirmation message to the CH. The CH compares the cluster’s direction, location, and speed with the IN, and if the score is above a certain threshold, it sends a subscription completion message, and then the other vehicle is subscribed to the cluster. ‘t’ indicates the wait time for a cluster invitation message. f = 1 indicates the cluster search state. Each vehicle ends the cluster search state (f = 0) once the cluster subscription is completed within the time ‘t’. When ‘t’ reaches 0, each vehicle declares itself as a CH and broadcasts a CHA to its surroundings.

Algorithm 1. Cluster subscription algorithm.
Cluster subscription algorithm
Notation:
01:	Vi = Vehicle i
02:	IN = Inferior Node
03:	BSM: Basic information message of vehicle
04:	t: Set amount of time to wait for a vehicle with a score higher than oneself
05:	f: Cluster search state (0: cluster search ended, 1: cluster search)
06:	CH = Cluster head
07:	Input: BSM, t
08:	Output:   Cluster subscription
09:	if Vi == IN:
10:	Broadcast(BSM)
11:	t.start()                // timer start
12:	f = 1               // cluster search
13:	While t > 0:
14:	if cluster invitation message received:
15:	send cluster invitation confirmation message to CH
16:	if cluster subscription completion message received:
17:	f = 0
18:	Vi = CM          // cluster subscription completed
19:	return
20:	if f == 1:       // timer ends and cluster subscription fails
21:	declare oneself as CH
22:	send cluster invitation message
23:	if Vi == CH:
24:	if CH received cluster invitation confirmation message:
25:	if direction, location, and speed are the same as IN:
26:	send cluster subscription completion message to IN
27:	else:
28:	Ignore

3.2.2. Cluster Head Candidates

In urban environments, vehicles have high mobility and density. In V2V communication, this causes frequent cluster subscriptions and departures, which must be considered. The CH candidate algorithm proposed in this paper is a scheme to always maintain CMs that can perform the role of the next CH. The proposed scheme supports immediate CH replacement using the CH candidate algorithm if a problem arises with the CH, maintaining V2V communication. If the frequent reconfiguration of clusters is not considered, then when the CH suddenly departs, packet loss of safety messages will occur during the time it takes to reselect a CH. Therefore, a CH candidate algorithm considering the sudden departure of the CH from the cluster is needed.

Figure 3 shows the proposed CH candidate selection process. Time 1 shows the process of CMs periodically sending scores to the CH. Time 2 shows the process of the CH receiving scores from the CMs and disseminating the Cluster Head Candidate List along with the cluster information. The CH aggregates and sorts the scores from the CMs, and then creates and disseminates the Cluster Head Candidate List. Each CM that receives this list learns who the next CH candidate is and prepares for the sudden departure of the CH. If the CH suddenly departs, the CMs wait for a certain time ‘t’. If time ‘t’ passes, each CM assumes the CH has departed, and the next CM with the highest score declares itself as the CH. The proposed scheme minimizes packet loss for safety messages by having a CM immediately perform the role of the CH through the CH candidate algorithm.

To select a cluster head candidate, each CM comprehensively calculates its reception quality, total number of messages, movement speed, and the number of nearby connected vehicles, and then sends its score to the CH. Reception quality refers to how well the vehicle can communicate. The most important role of the CH is to effectively disseminate messages. The proposed scheme considers vehicles with better reception quality to have a higher message dissemination success rate, as they have a lower signal attenuation rate [12]. The total number of messages represents how many messages a vehicle has. The proposed scheme considers that vehicles with more messages can respond to different requests from CMs. Movement speed refers to the vehicle’s speed and how close it is to the average movement speed of the vehicles within the cluster. The proposed scheme considers that vehicles with speeds closer to the cluster’s average speed are more likely to maintain the CH for a longer period without departing from the cluster. The number of connected vehicles refers to how many vehicles within the cluster the vehicle can communicate with. The proposed scheme considers that vehicles that can communicate with many other vehicles within the cluster can perform the role of the CH well. Accordingly, the CH candidate score is the sum of these attribute scores; higher scores indicate a higher likelihood of becoming the CH.

Equation (1) calculates the reception quality (RQ). Reception quality is calculated as 1 minus the packet loss rate. The packet loss rate is calculated by dividing the number of packet losses (PL) by the total number of packets (TP).

$$R{Q}_{\left(V_i\right)}=1-\frac{P{L}_{\left(V_i\right)}}{T{P}_{\left(V_i\right)}}$$

(1)

Equation (2) calculates the total number of messages (TD). This is calculated by dividing the total number of messages the individual vehicle has by the number of messages held by the vehicle with the most messages in the cluster. A higher number of messages leads to a higher score.

$$T{D}_{\left(V_i\right)}=\frac{{{\displaystyle \sum }}_{i=1}^{n}Data\left(V_i\right)}{Highest({{\displaystyle \sum }}_{i=1}^{n}Data\left(V_j\right))\in Cluster }$$

(2)

Equation (3) calculates the movement speed (speed score). This is the absolute value of the difference between the average movement speed of vehicles within the cluster and the individual vehicle’s speed. Smaller values indicate that it is closer to the average speed, leading to a higher score. When each CM receives cluster information from the CH, it also receives the cluster average speed (CAS).

$$S{S}_{\left(V_i\right)}=1-\left(\left|CAS-Spee{d}_{\left(V_i\right)}\right|+1\right)\ast 0.01$$

(3)

Equation (4) calculates the total number of connected vehicles (TCV). This score is calculated by dividing the number of connected vehicles (CV) within one hop by the total number of vehicles in the cluster (TV). A higher number of connected vehicles leads to a higher score.

$$TC{V}_{\left(V_i\right)}=\frac{CV{\left(V_i\right)}^{\prime }s 1 hop}{TV\in Cluster}$$

(4)

Equation (5) calculates the final CH candidate score. This is the sum of the reception quality, total number of messages, movement speed, and number of connected vehicles scores. The CM with the highest score is the first candidate to become the next CH.

$$Scor{e}_{\left(V_i\right)}=RQ+TD+SS+TCV$$

(5)

3.3. V2V Communication

The proposed message dissemination scheme operates similarly to PBE, a cluster-based V2V communication scheme [13]. Figure 4 shows the operation structure of V2V communication. The proposed V2V communication scheme is divided into intercluster and intracluster communication. Intracluster communication refers to the communication between the CH and CMs within the same cluster. Intercluster communication refers to the communication between CHs in different clusters. CHs perform both intracluster and intercluster communication, whereas CMs perform only intracluster communication.

3.3.1. Intracluster Communication

The purpose of intracluster communication is to divide the roles of vehicles participating in message dissemination and to disseminate messages. The proposed scheme reduces duplicate messages and improves the reception rate of safety messages through intracluster communication.

Intracluster communication refers to message dissemination between the CH and CMs within a cluster. Algorithm 2 shows the intracluster communication algorithm. Intracluster communication operates differently depending on the type of message. Emergency safety messages are disseminated regardless of each vehicle’s willingness to receive them, as they are related to driver safety. In addition, emergency safety messages start to be delivered as soon as a vehicle becomes aware of an emergency event. In contrast, general safety messages are nonurgent and are initiated by user requests.

The intracluster message delivery process in situations where emergency safety messages are disseminated is as follows. When a CM becomes aware of an emergency situation or receives an emergency safety message, it immediately sends the emergency safety message to the CH. When a CH becomes aware of an emergency situation or receives an emergency safety message, it disseminates the message to the CMs. At the same time, the CH disseminates the message to nearby CHs; this process is explained in the intercluster communication section. If an IN becomes aware of an emergency situation, it broadcasts the message.

General safety messages are communicated through requests from vehicles that need general safety messages and responses from vehicles that can provide the messages. The request timing of general safety messages is divided into automatic requests based on vehicle location and settings, and direct user requests. Since each vehicle has a different destination, direction, and speed, and each user has a different set of needs, the timing of general safety message requests also varies. The intracluster message delivery process in situations where general safety messages are disseminated is as follows. If a CM needs a general safety message, it requests it from the CH. If the CH has the requested safety message, it sends the message to the requesting CM. If the CH does not have the requested safety message, it checks if any other CM within the cluster has the message. If a CM within the cluster has the message, the CH delivers the safety message request to the CM with the message. Then, a connection is established between the CM that received the safety message request and the CM that requested the safety message, and the general safety message is sent. If the requested message does not exist within the cluster, the CH delivers the request to another CH; this process is explained in the intercluster communication section.

All vehicles, upon receiving safety messages, determine whether they are duplicates and store only new messages. CMs send their list of messages to the CH every time they receive a new message and store the last times they sent the list. The CH consolidates the CMs’ message lists, updates the message lists held within the cluster, and manages them.

Algorithm 2. Intracluster communication algorithm.
Intracluster communication algorithm
Notation:
01:	N: Current vehicle
02:	M: Message
03:	EM: Emergency safety message
04:	SM: General safety message
05:	RM: Request message for general safety message
06:	Input: N, M
07:	Output: message dissemination and transmission
08:	M receipt          // message receipt
09:	if M == EM and EM == new EM:
10:	if N == CH:
11:	disseminate emergency safety message to one’s own CMs
12:	call intercluster communication algorithm  // disseminate EM to nearby CHs
13:	elsif N == CM:
14:	disseminate EM to one’s own CH
15:	elsif N == IN:
16:	broadcast emergency safety message
17:
18:	if M == SM and SM == new SM:
19:	if needed by oneself:
20:	store
21:	if N == CH:
22:	update messages held in cluster
23:	elsif N == CM:
24:	send CH an updated list of held messages
25:	else:
26:	ignore
27:
28:	if M == RM:
29:	if N == CH:
30:	if oneself has a safety message of RM:
31:	send SM (RM == SM) to the CM that sent the RM
32:	elsif a CM in the cluster has safety message of RM:
33:	SM transmission request to CM with safety message of RM
34:	else:              // when there is no safety message of RM in the cluster
35:	call intercluster communication algorithm
36:
37:	elsif N == CM and CM receives SM transmission request from CH:
38:	send SM (RM == SM) to CM or CH that made the request
39:
40:	else:
41:	ignore

3.3.2. Intercluster Communication

Intercluster communication refers to message dissemination between the CHs of different clusters. There are two main situations where intercluster communication is necessary. First, when disseminating emergency safety messages, CHs must perform message dissemination as representatives. Second, when a general safety message is requested and the requested data do not exist within the cluster, it is necessary to forward the request to another cluster.

Algorithm 3 shows the intercluster communication algorithm, which is divided into disseminating emergency safety messages and forwarding request messages for general safety messages. When a CH has an emergency safety message with remaining lifetime, it disseminates the message to the CH of another cluster. If a request for a general safety message needs to be disseminated to another CH, the CH first stores the request message in the cluster request message table (CRD). When the CM that requested the general safety message receives the message or departs from the cluster, the request message is deleted from the CRD. The CH periodically disseminates the CRD to CHs in nearby clusters. CHs receiving the CRD from another cluster check if the requested general safety message exists within their cluster. If the requested safety message exists within the cluster, a connection is established between the two CHs, and the message is delivered. If the requested safety message does not exist within the cluster, the CH ignores the request.

Algorithm 3. Intercluster communication algorithm.
Intercluster communication algorithm
Notation:
01:	CRD: Cluster request message table
02:	CRD_total: Total messages of CRD
03:	CRD_i: Cluster request message i
04:	EM: Emergency safety message
05:	lifetime = Survival time that must be guaranteed for EM
06:	RM: Request message for general safety message
07:	N: Current vehicle
08:	Input: RM, EM
09:	Output: CRD message request
10:	def To_Other_Cluster(CRD):
11:	if len(CRD) != 0:
12:	send all messages of the CRD to other nearby clusters
13:	if the CM that requested CRD_i departed from the cluster or received CRD_i:
14:	CRD_total—CRD_i
15:	if CRD_i within CRD is received from another nearby cluster:
16:	CRD_total—CRD_i
17:	send CRD_i to the CM that made the request
18:
19:	while N == CH and if not departed from cluster:
20:	if holds EM and the EM’s lifetime != 0:
21:	disseminate emergency safety message // disseminate emergency safety message to nearby CHs
22:	if there is no safety message of RM in the cluster:
23:	insert RM in CRD
24:	To_Other_Cluster(CRD)

3.4. V2I Communication

The proposed scheme performs message dissemination using the RSU as a supplementary tool when a vehicle is connected to an RSU [23,24,25,26,27]. V2I communication refers to communication between vehicles and RSUs within the RSU’s communication range. RSUs have several advantages, such as larger storage space, a wider communication range, and fast collaboration between RSUs. However, since vehicle density is high in urban environments, direct communication between all vehicles and the RSU can create a heavy load on the RSU [27]. Therefore, in the proposed scheme, V2I communication operates similarly to cluster-based V2V communication. V2I communication in the proposed scheme is divided into a cluster-based V2I communication technique and an RSU scheduling technique.

3.4.1. Cluster-Based V2I Communication

Figure 5 shows the operation process of V2I communication. Cluster-based V2I communication has similar required time and operation processes to intercluster communication in V2V communication. Cluster-based V2I communication is performed when disseminating emergency messages and when general safety messages that do not exist within the cluster are requested. To prevent load on the RSU, CMs communicate with the RSU through the CH. INs communicate directly with the RSU.

Algorithm 4 shows the cluster-based V2I communication algorithm. If an emergency safety message exists, the CM delivers the emergency safety message to the CH in the same way it operates in V2V intracluster communication. CMs do not communicate directly with the RSU. On the other hand, CHs and INs directly deliver emergency safety messages to the RSU when such messages exist. The RSU receiving the emergency safety message checks for duplicates and then immediately disseminates the message. If a request for a general safety message exists, the CH delivers the CRD to the RSU in the same way it operates in V2V intercluster communication. The RSU receiving the vehicle’s general safety message request broadcasts the message needed by the vehicle. Here, the RSU performs scheduling considering factors such as the holding rate and request rate within the communication range to disseminate higher-priority messages. The RSU disseminates the safety message to vehicles within the communication range according to the scheduling results.

Algorithm 4. Cluster-based V2I communication algorithm.
Cluster-based V2I communication algorithm
Notation:
01:	CRD: Cluster request message table
02:	CRD_i: Cluster request message i
03:	EM: Emergency safety message
04:	RM: Request message for required general safety message
05:	N: Current vehicle
06:	Input: RM, EM
07:	Output: CRD message request
08:	def In_RSU(CRD):
09:	send CRD to RSU and nearby CHs
10:	if CRD_i within CRD is received from RSU:
11:	CRD_total—CRD_i
12:
13:	while if within the RSU’s communication range:
14:	if N != CM:
15:	if holding the EM:
16:	send emergency safety message to the RSU
17:	if there is a required general safety message:
18:	if N == IN:
19:	send RM to RSU
20:	if N == CM:
21:	send RM to CH
22:	if N == CH:
23:	if there is no message of RM in the cluster:
24:	call intracluster communication algorithm
25:	else:                   // if there is no requested message in the cluster
26:	insert RM in CRD
27:	if len(CRD) != 0:
28:	In_RSU(CRD)
29:	if the vehicle that requested CRD_i has departed:
30:	CRD_total—CRD_i
31:
32:	if outside the RSU’s communication range:
33:	call intracluster communication algorithm

3.4.2. RSU Scheduling

RSUs have a wider communication range than vehicles. Therefore, they can disseminate the necessary messages to many vehicles at once [3,5,6,7]. However, since RSUs have limited communication bandwidth, they cannot send all messages at once. Thus, an RSU scheduling technique is needed to determine the priority of messages and disseminate them.

RSUs determine which messages to disseminate based on the CRD received from the CH of each cluster. The proposed scheme considers the holding rate and request rate of messages to determine their priority. RSUs store and manage the following information for scheduling. First is the broadcast candidate table (BCT), which sorts and stores the priority of each safety message. The BCT consists of the message ID, holding rate, request rate, lifetime, urgency index, and score. The BCT updates the priorities every time the RSU makes a broadcast. Second is the vehicle information table (VIT), which stores information about vehicles and clusters. The VIT consists of the vehicle ID, cluster ID, cluster information, travel direction, cluster request messages, cluster holding messages, destination, latitude, and longitude. Third is the formula table (FT), which stores the formulas needed for BCT priority. The FT is calculated by joining the BCT and VIT, and consists of the requested cluster ID, requested message ID, and holding status. The FT is used to calculate the holding rate and request rate of each message in the BCT.

Equation (6) calculates the holding rate (HR), which refers to the proportion of clusters within the RSU’s communication range that have the corresponding message. The holding rate is calculated by dividing the number of clusters holding the data (NCH) by the number of clusters requesting the data (NCR). A high holding rate indicates a high probability of sharing the message through V2V communication. Therefore, the proposed scheme considers messages with high holding rates as lower priority.

$$HR\left(D_{\left(a\right)}\right)=\frac{NC{H}_{D_{\left(a\right)}}}{NC{R}_{D_{\left(a\right)}}}$$

(6)

Equation (7) calculates the request rate (RR), which refers to the proportion of vehicles within the RSU’s communication range requesting the corresponding message. The RR is calculated by dividing the number of vehicles requesting the message by the total number of messages requested by the vehicles. The proposed scheme considers messages with high request rates as higher priority.

$$RR\left(D_{\left(a\right)}\right)=\frac{{{\displaystyle \sum }}_{i=1}^n{D}_{\left(a\right)}}{{{\displaystyle \sum }}_{i=1}^n{D}_{\left(a\right)}+{{\displaystyle \sum }}_{i=1}^n{D}_{\left(b\right)}+\dots +{{\displaystyle \sum }}_{i=1}^n{D}_{\left(z\right)}}$$

(7)

Equation (8) calculates the priority score of the BCT. The proposed scheme unconditionally assigns a score of 2 to the emergency safety message if there are clusters that have not received it. The BCT priority score of general safety messages is the sum of the holding rate and request rate.

$$BCT Scor{e}_{\left(D_{\left(a\right)}\right)}=\left\{\begin{array}{c}2\\ HR\left(D_{\left(a\right)}\right)+RR\left(D_{\left(a\right)}\right) \end{array}\begin{array}{c}, if EM\\ , if SM\end{array}\right.$$

(8)

Algorithm 5 shows the RSU scheduling algorithm. The RSU receives the cluster information and CRD from each CH. If a new safety message is received, the RSU calculates the storage priority and performs BCT management, which includes inserting new messages and deleting unimportant messages. If there is no new message received or BCT management is completed, then the formula table is updated. Updating the formula table includes calculating the holding rate and request rate for each message. The priority of each message is calculated based on the updated formula table, and the BCT is updated accordingly. The RSU broadcasts safety messages based on the updated BCT. If there are still vehicles within the RSU’s communication range after broadcasting, the RSU receives the vehicle information and safety messages and repeats the process. If there are no more vehicles within the RSU’s communication range after broadcasting, the RSU waits until new vehicles connect.

Algorithm 5. RSU scheduling algorithm (with broadcast).
RSU scheduling algorithm (with broadcast)
Notation:
01:	lifetime = Survival time that must be guaranteed for EM
02:	BCT = Broadcast candidate table
03:	BCTscore(D(a)) = BCT priority score for a message
04:	Input: cluster information and requests, sorted_BCTscore_list
05:	Output: broadcast
06:	def FT_update(cluster information and requests, BCT):    // update formula table
07:	calculate holding rate
08:	calculate request rate
09:	return HR(D(a)), RR(D(a))
10:
11:	def BCT_update(HR(D(a)), RR(D(a))):              //update BCT
12:	BCTscore(D(a)) = HR(D(a) + RR(D(a))          //priority score
13:	BCTscore_list = BCT[BCTscore(D(a)), .... BCTscore(D(c))]
14:	sorted_BCTscore_list = BCTscore_list.sort(reverse = True) // sort priority scores in descending order
15:	return sorted_BCTscore_list
16:
17:	def RSU_Broadcast(cluster information and requests, sorted_BCTscore_list):
18:	if a new message is received:
19:	BCT management               // insert new messages, delete low-importance messages
20:	FT_update(cluster information and requests)
21:	BCT_update(HR(D(a)), RR(D(a)))
22:	if there is a safety message to request to vehicle:
23:	add safety message request
24:	// send priority messages corresponding to the packet size RSU can send at once
25:	for   i in len(max(RSUpacketsize)):
26:	broadcast(sorted_BCTscore_list[i])
27:
28:	while if a vehicle is within communication range:
29:	receive cluster information and requests
30:	RSU_Broadcast(cluster information and requests, BCT)

4. Performance Evaluation

4.1. Performance Evaluation Environment

To demonstrate the superiority of the scheme proposed in this study, we conducted performance evaluations of the safety message dissemination scheme in an urban environment. For this, two experimental evaluations were conducted. The first compared the packet loss of safety messages when cluster candidates were maintained by the cluster candidate algorithm and not maintained. The second compared the number of RSU processing requests and duplicate messages when all vehicles requested safety messages from the RSU according to the vehicle request algorithm and when clusters were used to request safety messages in a V2I environment.

Table 1. Performance evaluation environments.

Environment	Value
CPU	Intel(R) Core(TM) i5-9600 CPU   3.70 GHz
Memory	32.0 GB
OS	Window 10 64-bit
Language	Python 3
MAC Model	IEEE 802.11p WAVE

shows the environments in which the performance evaluations were conducted.

This study implemented a safety message dissemination environment proposed according to the communication standards of VANET.

Table 2. Performance evaluation parameters.

Parameter	Value
Time to wait for disconnected CH	1.5 s
Message transmission rate	6 Mbps
Channel synchronization period	100 ms
Beacon size	194 bytes
EM packet size	170 bytes

shows the parameter values applied in the performance evaluations. The performance evaluations were implemented with the Python programming language. The values of the parameters, such as communication period, transmission rate, and message size, were implemented according to the communication standards of VANET. We performed comparative evaluations using the same message size and communication environment as previous studies.

4.2. Performance Evaluation Results

4.2.1. Comparison of Safety Message Packet Loss

We compared the safety message packet loss rate with an existing scheme to demonstrate the superiority of the proposed scheme. The existing scheme, proposed by Muhammad Ali (PBE) [13], forms clusters for communication but does not maintain separate CH candidates. Therefore, when the CH departs from the cluster in the existing scheme, a new CH is selected from when it departs. However, during the operation of selecting a new CH in the existing scheme, safety message packets are lost. Conversely, the proposed scheme preselects and maintains CH candidates, so even if the CH departs from the cluster, it can be immediately replaced with a new CH. In the experimental evaluations, we measured the packet loss that occurred when the CH departed compared to the number of safety message packets that the CH could disseminate during the evaluation time and converted it into a percentage. In the first experimental evaluation, for the transmission cycle and message transmission rate, messages were assumed to be disseminated by performing a time sleep in units of ms. The vehicle departure was performed at intervals of 60 s.

Figure 6 shows the safety message packet loss rate according to the CH departure cycle. In the V2V environment, the experimental evaluation was conducted by changing the departure cycle of the CH, the main agent of safety message dissemination, from 120 s to 10 s. The experimental evaluation time, number of vehicles, and maximum time, which is the time to wait for the disconnected CH and detect that the CH has departed, was 1.5 s. PBE compares scores among the CMs 1.5 s after the CH is disconnected to select a new CH. Therefore, in PBE, the more frequent the CH’s departure from the cluster, the more score comparisons among CMs occur to select the next CH. The message exchanges required for this process result in substantial safety message packet loss. However, the proposed CH candidate algorithm enables the CM with the highest score in the cluster to immediately perform the new CH role 1.5 s after the CH is disconnected, resulting in packet loss for only the 1.5 s that they wait for the CH. Thus, the proposed CH candidate algorithm outperformed PBE by approximately 16.5% in terms of the packet loss rate.

Figure 7 shows the safety message packet loss rate according to the number of CM vehicles. In the V2V environment, the experimental evaluation was conducted by changing the number of CM vehicles forming the cluster to 10, 20, 30, 40, and 50. PBE and the proposed CH candidate algorithm showed little difference when the number of CM vehicles was relatively small; however, as the number of CM vehicles increased, more score comparisons between the CMs occurred, causing delays in selecting the next CH and increasing the packet loss. Thus, the proposed CH candidate algorithm outperformed PBE by up to 10%.

4.2.2. Comparison of the Number of RSU Processing Requests

We compared the number of RSU processing requests with the existing scheme to demonstrate the superiority of the proposed scheme. PBE and other existing schemes do not consider either the cluster or the V2I environments using RSUs, so all vehicles send duplicate safety message requests to the RSUs. In contrast, in the proposed cluster environment scheme, vehicles only request messages from the RSU that are not held within the cluster. In the experimental evaluation, we measured the number of RSU processing requests in two cases: when vehicles within the RSU communication range request only safety messages (CRD) not in the cluster according to the proposed operation algorithm, and when all vehicles within the communication range send safety messages to the RSU.

Figure 8 shows the number of RSU processing requests according to the probability of holding a message within the cluster. This experiment assumed 1 cluster, with 20 vehicles and 20 safety messages needed per vehicle, which were randomly selected. The probability of holding a safety message within the cluster was set so that vehicles within the same cluster could hold the message with the corresponding probability by randomly selecting messages for each vehicle. When the holding probability within the cluster was high, the proportion of CRDs containing messages not held within the cluster decreased. A decrease in the proportion of CRDs means that messages can be shared within the cluster, thus reducing the number of requests made to the RSU.

Figure 9 shows the reduction in duplicate messages according to the probability of holding a message within the cluster. As the probability of processing the message within the cluster increased, there was no need to request the message from the RSU. Hence, the proposed scheme, where vehicles request only necessary messages, reduced the number of duplicate messages, making it much more efficient than the existing scheme, where all vehicles directly request all messages from the RSU. Therefore, the proposed scheme produced only 12.5% of nonduplicate safety message requests compared to the existing scheme. This means that the proposed scheme also generated only 12.5% of RSU requests compared to the existing scheme.

Figure 10 shows the number of RSU processing requests according to the density. This experiment assumed 20 vehicles forming the cluster, with 20 safety messages needed per vehicle that were randomly selected. The vehicle’s probability of holding the message within the cluster was set to 20%. The number of vehicles varied from 20 to 200 in the experimental evaluation. As the number of vehicles increased, the number of requests the RSU had to process also increased. At a low density, there were few messages shared between vehicles, so the number of RSU processing requests barely differed between the proposed scheme and the existing scheme. However, as the density increased, the number of messages that could be shared within the cluster also increased due to the messages held by the vehicles.

Figure 11 shows the reduction in duplicate messages according to density. The proposed scheme produced only 20% of nonduplicate safety message requests compared to the existing scheme, where all vehicles directly request messages from the RSU. This means that the proposed scheme also generated only 20% of RSU requests compared to the existing scheme. Particularly, as the density increased, the proposed scheme became more efficient than the existing scheme in terms of the number of message requests that the RSU had to process, reducing duplicate messages.

5. Conclusions

This paper proposes a safety message dissemination scheme considering the high mobility and density of vehicles in urban vehicular network environments. The proposed scheme efficiently performs message dissemination considering both V2V and V2I environments. Specifically, in the V2V environment, the proposed scheme reduces packet loss caused by frequent cluster subscriptions and departures through a cluster management technique. Furthermore, in V2I communication, the proposed scheme reduces duplicate message requests and the number of RSU processing requests through intercluster safety message dissemination. To demonstrate the superiority of the proposed scheme, we conducted experimental evaluations of the cluster management technique and vehicle request algorithm. The performance evaluation results show that the proposed scheme outperformed the existing scheme. In future research, we plan to conduct additional performance evaluations using simulation libraries and frameworks that can design and implement real road environments. In additional performance evaluations, we will consider many factors that affect the V2V communication, such as the road capacity, the number of lanes, the size and type of vehicles, terrain, and obstacles, the number of lanes, and speed limits. In addition, we will analyze more in-depth coverage of transportation-related concepts as well as the transportation system’s underlying principles, dynamics, and limitations to improve the proposed scheme. Finally, we will consider interference from other external devices in transferring the messages.