# Efficient Message Dissemination on Curve Road in Vehicular Networks

Authors: Shidong Huang; Chuanhe Huang; Dongfang Wu; Yabo Yin; M. Wasim Abbas Ashraf; Bin Fu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Effective emergency message dissemination is a great importance on a specific road in vehicular networks (VN). The existing methods are not most efficient solutions for message dissemination on the curve road, which primarily focus on highway and urban road. In order to improve the efficiency of message dissemination on the curved road, the paper proposed a message dissemination method based on bidirectional relay nodes. The message can be disseminated in two directions simultaneously. The paper designed a relay node selection method based on the neighbor nodes’ coverage length of the road. Different waiting delays are assigned to the neighbor nodes according to the cover capability of the road in which the message has not arrived. Simulation results demonstrated that the efficiency of the proposed method is superior to the common solutions in terms of the contention delay and the propagation velocity.


---

## Body

## 1. Introduction

Effective message dissemination is widely used in vehicular networks (VN). Transport commuting has become a ubiquitous part of daily life; vehicular networks play a positive role and improve the living standards of the people. VN can access the location where a traffic accident occurs and timely inform the relevant vehicles to adopt safety measurements. Traffic flow coordination can also benefit from the VN [1, 2]. People can get the current traffic information timely on the related road of the vehicle and then choose the optimal path. Traveling will become more convenient; an accurate match between user demand and vehicle dispatch can be achieved by related technologies of VN [3]. VN will make the intelligent transportation system a reality and can provide information regarding petrol stations, restaurants, services areas, weather information, navigation [4–6], and all desired information about the surrounding environment. The application of VN will raise efficiency and enhance the user experience. People in different vehicles can cooperate on different roads within the same team. Mobile devices and vehicles can also work together to finish the file upload and download [7, 8]. The large computational task can be divided into multiple subtasks according to [9–11], and vehicles can collaborate with each other or other heterogeneous devices to complete the computing task using the edge computing. Network security is important for the various applications in VN, while its own implementation process benefits much from VN [12, 13]. Efficient message dissemination plays a critical role in all the above application scenarios of VN.Due to the rapid movement of vehicles, there are still some challenges in term of efficient emergency message dissemination in VN. In order to solve this problem, researchers propose a variety of different routing protocols. The current data transmission routing protocols in VN mainly include the protocol based on the geographical location, broadcast protocol based on the infrastructure, and clustering-based protocol. In order to improve the efficiency of message dissemination, there are also some hybrid emergency message dissemination methods. The existing message dissemination schemes mainly focus on urban roads and high way, but there is little work to cope with the curve road scene.Rural roads sometimes are tortuous compared with the urban roads and high way. When a landslide, debris flow, bridge collapse, and other accidents suddenly appear in a certain position on the curve road during tourism, broadcasting these messages to nearby vehicles can make them avoid danger and choose other available paths to reach the destination. Timely and effective message dissemination in a specific area of the road can ensure the safety of life and property and avoid unnecessary detours. The existing emergency message dissemination mechanisms may not be the optimal solution for message dissemination of the curve road scene. This paper designs an emergency message dissemination method for the curve road scenario; the key contributions of this paper are summarized as follows:(i)
The paper proposed a robust relay selection method based on the coverage capability of the road in which the message has not arrived, and the method can reduce the collision probability of the response messages from the neighbor nodes and improve the efficiency of relay selection(ii)
The paper designed a message broadcast scheme based on the bidirectional relay selection as to the curve road, which can improve the forwarding efficiency of the emergency messages(iii)
Simulation results showed that the proposed method improves the efficiency of the relay selection and the message broadcast on the curve roadThe rest of the paper is organized as follows. Section2 introduces the related work. Section 3 proposes the relay selection method based on the coverage capability of the neighbor nodes. Section 4 presents the message broadcast method for curve road. Simulation and result discussion are presented in Section 5. Section 6 concludes this paper.


## 2. Related Work

Due to the high mobility of the vehicles, there are some challenges for efficient message dissemination in VN. In order to solve the problem, researchers proposed a variety of message dissemination methods based on vehicle-to-vehicle (V2V) or vehicle-to-infrastructure (V2I) communication. Common data dissemination is implemented by vehicle broadcasting in V2V communication; it can also be achieved by infrastructure broadcasting or the cooperation between the two ways.Broadcast in the vehicular ad hoc network is very important to complete the data dissemination when the infrastructure is not available or has a heavy workload. To improve the multihop broadcast efficiently in the urban vehicular ad hoc network, link quality was considered to select the suitable relay node in [14]. For multihop message broadcast in urban vehicular ad hoc networks, the authors proposed a relay selection method by asynchronous contention based on iterative partition in [15] and then designed the directional broadcast, bidirectional broadcast, and multidirectional broadcast scheme to complete the message dissemination in target area. To solve the broadcast storm problem, effective candidate number, maximum forwarding distance, and global traffic density are all taken into account in relay node selection; the authors proposed a local topology-aware broadcast protocol in [16]. Taking into consideration the vehicle mobility and link quality in vehicular ad hoc network, the authors proposed the relay selection method and designed the corresponding broadcast protocols for broadcast delay and efficiency, respectively, in [17]. More broadcast methods in VN were surveyed in [18–20].Geocast is the common solution for data dissemination in VN. Geographical location information of the candidate nodes is the major consideration in the position-based routing protocols. Tian et al. proposed the solution for the directional broadcasting in the VN; the neighbor node determines whether it needs to forward the message again according to the direction of the message propagation and its current location [21]. Karimi and Shokrollahi improved the existing greedy perimeter stateless routing (GPSR) based on the location prediction of the nodes. Whether the node was selected as the relay, the future location of the node should be considered [22]. With vehicles’ location and mobile information, Ryu and Cha proposed the relay selection method based on the predicted link lifetime. The candidate node with the longest lifetime was selected as the relay node to forward messages [23]. Jiang et al. proposed the UAV-assisted geographic routing in VANETs based on the Q-Learning, the aerial component calculates the global routing path for the ground component, and then, the vehicle on the ground forwards the routing request to the optimal node [24]. Residual bandwidth and packet loss rate are considered to calculate the link utility of the two-hop neighbors; Alzamzami and Mahguob designed the geographic routing for urban VANETs based on the link utility [25].With regard to the clustering-based message dissemination scheme, Alkhalifa and Almogren proposed a method based on the link stability for the construction of the clusters. In order to avoid the collision of broadcast messages among cluster members, the CSMA/CA method was designed based on cache size and vehicle density [26]. To improve the reliability of emergency message distribution in VN, the authors proposed a dynamic clustering scheme of vehicles and designed two MAC layer broadcast protocols in [27]. For the sake of improving the stability and maintenance time of clusters, Seo et al. proposed a cluster data distribution protocol PCDB based on the path similarity of nodes [28]. Abbas and Fan proposed a clustering-based multipath routing protocol with the ant colony optimization technique to achieve high efficiency of the data transmission [29]. Information can be delivered by the base station or RSU to the transportation management system. Dua et al. designed the routing protocol based on the cluster for the information delivery from the source to the nearest RSU. The turning probability of the cluster was considered in the routing decision [30]. For the efficiency of data upload from vehicles to BS, Garbiso et al. designed the adaptive clustering method of vehicles according to the density of vehicles; the proposed method can ensure the effectiveness and fairness of data upload [31]. In addition, more clustering schemes in vehicular networks are introduced in [32–34].As to the emergency message dissemination based on the road side unit (RSU), Tiennoy and Saivichit modified the structure of the named data networking (NDN) to improve the efficiency of data collection and distribution [35]. Li et al. used a quadtree model that represents a hierarchical decomposition of the global area and then proposed the selection approach of the RSU to forward the message to the destination area [36]. Fan et al. proposed a stochastic multihop broadcast scheme to solve the collision of the message rebroadcast by the vehicles which was firstly broadcast by RSU [37]. Sometimes vehicles do not get the full data requested when it run out the range of RSU; then, the base station is responsible for the data dissemination to complete the data requested. Liu et al. proposed the data dissemination solution for base station based on network coding technology [38]. To improve the efficiency of the content distribution from RSU, Dai et al. designed a schema based on the coding-decoding technology. The coded files are cached on multiple RSUs, the vehicle can offload the encoded packets from RSU, and then, it can decode the original file if it got enough coded packets [39].Because of the good maneuverability of UAV, it is often used to the data distribution in the VN. We proposed the data distribution scheme based on the network coding [40] to improve the data dissemination efficiency in vehicular networks assisted by UAV with an active directional antenna. For the multimedia data offloaded from RSU, Nam et al. proposed the adaptive content precaching scheme for RSU based on the mobility of the vehicles, and RSU cached appropriate amounts of data according to the predictive speed of the vehicles [41]. As to the coverage problem of the multiple dynamic vehicles with the limited number of UAVs, Samir et al. proposed a control method for UAV’s trajectories based on the reinforcement learning technology. The framework can achieve maximum vehicular coverage with the minimum number of UAVs and the minimum energy consumption [42]. Zhou et al. designed aerial-ground cooperative vehicular networking architecture to improve the availability of the network. UAV can be used for auxiliary communication when there is an interruption of VN, and data can be transferred by the way of UAV-to-UAV (U2U), UAV-to-vehicle (U2V), and vehicle-to-vehicle (V2V) [43].The related research work focused on the scene of highway or urban scene. When selecting the relay node, few solutions take into account the length of the road that the candidate node can cover. In this paper, relay selection based on cover capability and a curved road broadcast mechanism based on the bidirectional relay is proposed, which can improve the efficiency of message dissemination in the curve road scene. Vehicles on the curve road can receive the message disseminated in time.


## 3. Relay Selection Based on Cover Capability

### 3.1. System Model and Assumption

Assume that multiple vehicles are traveling on the curve road, it is necessary to inform all vehicles within a specific segment due to an emergency, such as the road segment between pointS and point D, as thown in Figure 1. There is no available infrastructure-assisted communication and message transmission between vehicles via broadcasting. Each vehicle is equipped with an OBU device which can accomplish the message receiving and sending. The communication radius of the vehicle is r. GPS is installed on each vehicle to access its own position information in real time. Map information of the current road is cached on every vehicle.Figure 1
Curve road scene.


### 3.2. Optimal Relay Selection Based on Road Coverage Capability

Traditional solutions select the furthest neighbor node as the relay node. As to the highway scene shown in Figure2, S is the current node, and vR1 and vR2 are in the communication range of the node S. S selects the node vR1 as the relay node to broadcast the message. As to curve road scene shown as the Figure 1, vR2 is selected as the relay node because it is closer to the reference point A. These relay selection methods are carried out without consideration for the road coverage capability of the candidate nodes. If we take the road coverage capability into account, vR1 is most suitable candidate of the scene shown in Figure 1. Thus, the relay selection method is proposed based on the road coverage capability of the candidates in the paper.
(1)Widthsegm,k=1ω1+ωk−1modN+1/N−1+ωk−1modN/N·Widthsegm−1,kN.Figure 2
Highway scene.After receiving the message, collision may occur when the neighbor nodes try to response simultaneously. The RTB/CTB is employed to deal with the hidden terminal problem and the broadcast storm problem. Some contention approaches are proposed based on the distance partition [44, 45]. Waiting delay of neighbor node is determined according to the distance between the neighbor node and the reference point. The neighbor node whose waiting delay expired firstly obtains the opportunity of forwarding. We propose the optimal relay selection method based on the maximum length of uncovered roads (PBOL) to improve the broadcast efficiency for the curve road scene. The method is also suitable for the urban road scene, as shown in Figure 2. vR1 can cover the road segment between the point A and C, and the length of the road segment between the point A and C is dR1; vR2 can cover the road segment between the point A and B, and the length of the road segment between the point A and B is dR2; vR1 selected as the relay node is more suitable because the value of dR1 is greater than the value of dR2.When sending node wants to send message, it broadcasts RTB message at first. The message consists of the location information of the sending node and the maximum uncoverage road length of the message that the node can cover at any location in the communication range of the sending node. After receiving RTB from sending node, all neighbor nodes in the communication range can calculate the length of the road that it can cover and the message have not arrived at according to the location information of the sending node, its own location information, and the local cached map information. Every neighbor node maps the length of the road that it can cover to the new location of the maximum uncovered road length of the message that the node can cover being at any location in the communication range of the sending node. Then we partition the maximum uncovered road lengthdmax into multisegments with the formula (1), Widthsegm,k represents the length of the kth segment in the mth partition, Widthseg0,0=dmax. ω is a constant used to adjust the width of partitioned segment. Which segment the neighbor node belongs to determines its waiting delay, the nodes belong to the same segment with the same waiting delay. When the waiting delay expires firstly, nodes belong to the same segment broadcast a black-burst message. Nodes belonging to other segments receive the black-burst message, and they will give up the contention. Then, the segment that the nodes’ waiting delay expires firstly will be partitioned recursively until the partition times reached the predefined threshold. After the final round of the partitioning, the neighbor nodes in the selected partition will randomly choose their back-off periods from the available contention windows, the one with the minimum delay is selected as the forwarder. The procedure of the relay selection is shown as Algorithm 1.We take an example to illustrate the details of the procedure. As shown in Figure1, node S wants to broadcast a message; then, it first broadcast RTB, and neighbor nodes receive it. The intersection of node S′ communication range, and the road is A. The neighbor node of node S may appear anywhere along the road between the point S and the point A. Suppose that the intersection of a neighbor node vR1’s communication range and the road is C, then, the length dR1 of the uncovered road that vR1 can cover is the length of the road between A and C. The length of the road between any two poins can be calculated by the math method, which has been widely used in Google Map and Baidu Map. Given the coordinates of the source and the destination, the map can output the distance between the source and the destination. Neighbor node may appear at any location of the road that belongs to the node S′ communication range; then, S can get the length of uncovered road that the neighbor node can cover being at any location of the road and the message have not arrived at and then take the maximum value dmax as the maximum coverage length that the neighbor nodes can cover.Then,S node puts its own location information and the the maximum coverage length dmax that the neighbor nodes can cover into RTB message when it sends RTB. After receiving RTB from node S, any neighbor node vRi can calculate the length of the uncovered road it can cover according to the sending node’s location information, communication radius, cached map information, and its own location information, which is denoted by dRi. The neighbor node can map its location to the dmax according to the length of the uncovered road it can cover. Mapped locations of the neighbor node vR1 and vR2 are shown as Figure 3.Figure 3
Relay selection on the curve road.Then,dmax is divided into different N segments with the formula (1). vR1 is mapped in the hth segment. After h−1th time slot, vR1 broadcasts a burst message. Other neighbor nodes receive the burst message from the node vR1, and they will give up the contention. There may be multiple neighbor nodes locating at the hth segment, so the hth segment is divided iteratively until the maximum number of recursive partition M is reached with the same method. Lastly, nodes belonging to the kth segment of the Mth iteration select a waiting delay randomly; the node with the minimum waiting delay is selected as the relay.Algorithm 1: Relay selection based on PBOL.
Input: location of the sending node and its neighbors;Map information; communication radius;Output: relay selected;1:while partitionNum ≤ M do2:segmentk=formula (1);3:if (dRi∈segmentk and partitionNum<M) then4:delayRi=delayRi+k∗time slot;5:else6:if (dRi∈segmentk and partitionNum=M) then7:delayRi=delayRi+k∗timeslot+randomValue;8:end if9:end if10:whiledelayRi epired do11:nodeRi broadcast Burst message;12:  break;13:end while14:Relay=nodeRi;15:if (nodex receive the burst messagebeforedelayx expired) then16:nodex give up contention;17:end if18:partitionSegment=Segmentk whichthenodeRi locate in;19:  partitionNum++;20:end while21:return: Relay;


## 3.1. System Model and Assumption

Assume that multiple vehicles are traveling on the curve road, it is necessary to inform all vehicles within a specific segment due to an emergency, such as the road segment between pointS and point D, as thown in Figure 1. There is no available infrastructure-assisted communication and message transmission between vehicles via broadcasting. Each vehicle is equipped with an OBU device which can accomplish the message receiving and sending. The communication radius of the vehicle is r. GPS is installed on each vehicle to access its own position information in real time. Map information of the current road is cached on every vehicle.Figure 1
Curve road scene.


## 3.2. Optimal Relay Selection Based on Road Coverage Capability

Traditional solutions select the furthest neighbor node as the relay node. As to the highway scene shown in Figure2, S is the current node, and vR1 and vR2 are in the communication range of the node S. S selects the node vR1 as the relay node to broadcast the message. As to curve road scene shown as the Figure 1, vR2 is selected as the relay node because it is closer to the reference point A. These relay selection methods are carried out without consideration for the road coverage capability of the candidate nodes. If we take the road coverage capability into account, vR1 is most suitable candidate of the scene shown in Figure 1. Thus, the relay selection method is proposed based on the road coverage capability of the candidates in the paper.
(1)Widthsegm,k=1ω1+ωk−1modN+1/N−1+ωk−1modN/N·Widthsegm−1,kN.Figure 2
Highway scene.After receiving the message, collision may occur when the neighbor nodes try to response simultaneously. The RTB/CTB is employed to deal with the hidden terminal problem and the broadcast storm problem. Some contention approaches are proposed based on the distance partition [44, 45]. Waiting delay of neighbor node is determined according to the distance between the neighbor node and the reference point. The neighbor node whose waiting delay expired firstly obtains the opportunity of forwarding. We propose the optimal relay selection method based on the maximum length of uncovered roads (PBOL) to improve the broadcast efficiency for the curve road scene. The method is also suitable for the urban road scene, as shown in Figure 2. vR1 can cover the road segment between the point A and C, and the length of the road segment between the point A and C is dR1; vR2 can cover the road segment between the point A and B, and the length of the road segment between the point A and B is dR2; vR1 selected as the relay node is more suitable because the value of dR1 is greater than the value of dR2.When sending node wants to send message, it broadcasts RTB message at first. The message consists of the location information of the sending node and the maximum uncoverage road length of the message that the node can cover at any location in the communication range of the sending node. After receiving RTB from sending node, all neighbor nodes in the communication range can calculate the length of the road that it can cover and the message have not arrived at according to the location information of the sending node, its own location information, and the local cached map information. Every neighbor node maps the length of the road that it can cover to the new location of the maximum uncovered road length of the message that the node can cover being at any location in the communication range of the sending node. Then we partition the maximum uncovered road lengthdmax into multisegments with the formula (1), Widthsegm,k represents the length of the kth segment in the mth partition, Widthseg0,0=dmax. ω is a constant used to adjust the width of partitioned segment. Which segment the neighbor node belongs to determines its waiting delay, the nodes belong to the same segment with the same waiting delay. When the waiting delay expires firstly, nodes belong to the same segment broadcast a black-burst message. Nodes belonging to other segments receive the black-burst message, and they will give up the contention. Then, the segment that the nodes’ waiting delay expires firstly will be partitioned recursively until the partition times reached the predefined threshold. After the final round of the partitioning, the neighbor nodes in the selected partition will randomly choose their back-off periods from the available contention windows, the one with the minimum delay is selected as the forwarder. The procedure of the relay selection is shown as Algorithm 1.We take an example to illustrate the details of the procedure. As shown in Figure1, node S wants to broadcast a message; then, it first broadcast RTB, and neighbor nodes receive it. The intersection of node S′ communication range, and the road is A. The neighbor node of node S may appear anywhere along the road between the point S and the point A. Suppose that the intersection of a neighbor node vR1’s communication range and the road is C, then, the length dR1 of the uncovered road that vR1 can cover is the length of the road between A and C. The length of the road between any two poins can be calculated by the math method, which has been widely used in Google Map and Baidu Map. Given the coordinates of the source and the destination, the map can output the distance between the source and the destination. Neighbor node may appear at any location of the road that belongs to the node S′ communication range; then, S can get the length of uncovered road that the neighbor node can cover being at any location of the road and the message have not arrived at and then take the maximum value dmax as the maximum coverage length that the neighbor nodes can cover.Then,S node puts its own location information and the the maximum coverage length dmax that the neighbor nodes can cover into RTB message when it sends RTB. After receiving RTB from node S, any neighbor node vRi can calculate the length of the uncovered road it can cover according to the sending node’s location information, communication radius, cached map information, and its own location information, which is denoted by dRi. The neighbor node can map its location to the dmax according to the length of the uncovered road it can cover. Mapped locations of the neighbor node vR1 and vR2 are shown as Figure 3.Figure 3
Relay selection on the curve road.Then,dmax is divided into different N segments with the formula (1). vR1 is mapped in the hth segment. After h−1th time slot, vR1 broadcasts a burst message. Other neighbor nodes receive the burst message from the node vR1, and they will give up the contention. There may be multiple neighbor nodes locating at the hth segment, so the hth segment is divided iteratively until the maximum number of recursive partition M is reached with the same method. Lastly, nodes belonging to the kth segment of the Mth iteration select a waiting delay randomly; the node with the minimum waiting delay is selected as the relay.Algorithm 1: Relay selection based on PBOL.
Input: location of the sending node and its neighbors;Map information; communication radius;Output: relay selected;1:while partitionNum ≤ M do2:segmentk=formula (1);3:if (dRi∈segmentk and partitionNum<M) then4:delayRi=delayRi+k∗time slot;5:else6:if (dRi∈segmentk and partitionNum=M) then7:delayRi=delayRi+k∗timeslot+randomValue;8:end if9:end if10:whiledelayRi epired do11:nodeRi broadcast Burst message;12:  break;13:end while14:Relay=nodeRi;15:if (nodex receive the burst messagebeforedelayx expired) then16:nodex give up contention;17:end if18:partitionSegment=Segmentk whichthenodeRi locate in;19:  partitionNum++;20:end while21:return: Relay;


## 4. Message Broadcast Method for Curve Road

### 4.1. Relay Selection Based on PBOL

The relay selection strategy has an important influence on the speed of message dissemination. The common way is to select the node farthest from the sending node or the reference point as the relay node. Relay selection by this method may not be the optimal solution for the curve road. As to the scenario of the Figure1, there are two available neighbor nodes in the communication range of the node S. With the common way, the node vR2 will be selected as the relay node, which can cover the section of the road between A and B. If vR1 is selected as the relay node with the proposed method PBOL, the section of the road between A and C can be covered. In this case, vR1 acting as the relay will be more efficient than the node vR2. The proposed method PBOL is used to select the relay when the emergency message is broadcasting on the curve road.Algorithm 2: Message broadcast on curve road.
Input: message broadcast;Output:∅;1:functionvoidBroadcast2:while (not all road is covered by the message) do3:   Current node sets RTB symbol and sends RTB;4:   Neighbor nodes receive RTB;5:if (RTB symbol==0) then6:     Unidirectional relay = Select unidirectionalrelay with method PBOL;7:     Current node broadcast the message;8:     Current node = Unidirectional relay;9:     Current node updates the road coverageof the message;10:Broadcast11:end if12:if (RTB symbol==1) then13:     Bidirectional relays = Select the bidirectionalrelays with method PBOL;14:     Current node broadcast the message;15:     Current nodes = Bidirectional relays;16:     Current nodes update the road coverageof the message;17:Broadcast;18:end if19:end while20:end function


### 4.2. Emergency Message Broadcast Mechanism on Curve Road

To improve the efficiency of the message dissemination, we adopt a bidirectional relay broadcast mechanism when necessary. After the current relay node is determined, if there is an uncovered road segment between the current relay node and the sending node, then the current relay node starts to select the bidirectional relay nodes with the proposed method PBOL, as shown in Figure4. Assuming that the road before vs have been covered by the message, vs starts to select the unidirectional relay node with the proposed method PBOL. There are neighbor nodes v1 and v22 available in its communication range. Based on the method PBOL, the source node vs selects v1 as the relay node and then broadcasts the message. After the node v1 receives the message, it can be concluded that there is a road section between vs node and v1 node (road section between E and F) being not covered according to the coordinates of vs node, communication radius r, its own location information, and map information. v1 now needs to start the bidirectional relay node selection by the PBOL method. If there is no uncovered road section between the node v1 and the previous hop vs, v1 only need to select the unidirectional relay node for message forwarding by the PBOL method.Figure 4
Bidirectional relay selection on the curve road.For bidirectional relay node selection method, when the current relay nodev1 broadcasts the RTB messages, the symbol of RTB is set to 1 which indicates that bidirectional relay node selection is requested. If there is no neighbor node in the communication range of the current relay node, the current relay node adopts storage-carry-forward strategy. The uncover road is partitioned into two parts by the current relay node v1: one part is before the current relay node and the other part is behind the current relay node. The current relay node selects one from its neighbor nodes who can cover the maximum length of the front uncovered road as the front relay node and selects one from its neighbor nodes who can cover the maximum length of the back uncovered road as the back relay node. v1 selects the v21 as the front relay and v22 as the back relay in Figure 4. The selected relay node decides to select the unidirectional relay or bidirectional relay based on whether there is uncovered road segment between itself and the prehop, the flow diagram of the relay selection is shown as Figure 5. The procedure is repeated until all the road is covered by the message, which is shown as the Algorithm 2.Figure 5
Flow diagram of relay selection on the curve road.


## 4.1. Relay Selection Based on PBOL

The relay selection strategy has an important influence on the speed of message dissemination. The common way is to select the node farthest from the sending node or the reference point as the relay node. Relay selection by this method may not be the optimal solution for the curve road. As to the scenario of the Figure1, there are two available neighbor nodes in the communication range of the node S. With the common way, the node vR2 will be selected as the relay node, which can cover the section of the road between A and B. If vR1 is selected as the relay node with the proposed method PBOL, the section of the road between A and C can be covered. In this case, vR1 acting as the relay will be more efficient than the node vR2. The proposed method PBOL is used to select the relay when the emergency message is broadcasting on the curve road.Algorithm 2: Message broadcast on curve road.
Input: message broadcast;Output:∅;1:functionvoidBroadcast2:while (not all road is covered by the message) do3:   Current node sets RTB symbol and sends RTB;4:   Neighbor nodes receive RTB;5:if (RTB symbol==0) then6:     Unidirectional relay = Select unidirectionalrelay with method PBOL;7:     Current node broadcast the message;8:     Current node = Unidirectional relay;9:     Current node updates the road coverageof the message;10:Broadcast11:end if12:if (RTB symbol==1) then13:     Bidirectional relays = Select the bidirectionalrelays with method PBOL;14:     Current node broadcast the message;15:     Current nodes = Bidirectional relays;16:     Current nodes update the road coverageof the message;17:Broadcast;18:end if19:end while20:end function


## 4.2. Emergency Message Broadcast Mechanism on Curve Road

To improve the efficiency of the message dissemination, we adopt a bidirectional relay broadcast mechanism when necessary. After the current relay node is determined, if there is an uncovered road segment between the current relay node and the sending node, then the current relay node starts to select the bidirectional relay nodes with the proposed method PBOL, as shown in Figure4. Assuming that the road before vs have been covered by the message, vs starts to select the unidirectional relay node with the proposed method PBOL. There are neighbor nodes v1 and v22 available in its communication range. Based on the method PBOL, the source node vs selects v1 as the relay node and then broadcasts the message. After the node v1 receives the message, it can be concluded that there is a road section between vs node and v1 node (road section between E and F) being not covered according to the coordinates of vs node, communication radius r, its own location information, and map information. v1 now needs to start the bidirectional relay node selection by the PBOL method. If there is no uncovered road section between the node v1 and the previous hop vs, v1 only need to select the unidirectional relay node for message forwarding by the PBOL method.Figure 4
Bidirectional relay selection on the curve road.For bidirectional relay node selection method, when the current relay nodev1 broadcasts the RTB messages, the symbol of RTB is set to 1 which indicates that bidirectional relay node selection is requested. If there is no neighbor node in the communication range of the current relay node, the current relay node adopts storage-carry-forward strategy. The uncover road is partitioned into two parts by the current relay node v1: one part is before the current relay node and the other part is behind the current relay node. The current relay node selects one from its neighbor nodes who can cover the maximum length of the front uncovered road as the front relay node and selects one from its neighbor nodes who can cover the maximum length of the back uncovered road as the back relay node. v1 selects the v21 as the front relay and v22 as the back relay in Figure 4. The selected relay node decides to select the unidirectional relay or bidirectional relay based on whether there is uncovered road segment between itself and the prehop, the flow diagram of the relay selection is shown as Figure 5. The procedure is repeated until all the road is covered by the message, which is shown as the Algorithm 2.Figure 5
Flow diagram of relay selection on the curve road.


## 5. Performance Evaluation

### 5.1. Simulation Settings

In order to evaluate the performance of the relay selection method, we choose a 4 km long mountain road as the simulation scene which is in Ziquejie Park, China [45] and shown as the Figure 6. The message is expected to cover all parts of the road from the Start to the end. The position distribution of vehicles on the road obeys Poisson distribution, and vehicles drive at a fixed speed on the road without lane change and overtaking. The speed of vehicles obeys the uniform distribution in 1/2vmax,vmax. Due to the mountain road condition, the maximum speed vmax is 40 km/h. In order to verify the performance of the scheme in different vehicle densities, the vehicle density varies from 0.025 to 0.305. The arrival rate of the message is set to 2 EMs/s. PBOL is compared with binary-partition-assisted MAC-layer broadcast method (BPAB) [46], trinary partitioned black-burst-based broadcast mechanism (3P3B) [44], and relay selection based on the distance to reference point (PBOP) [45] in the view of contention delay, one-hop delay, and message propagation speed. M,N,ω=2,4,2 in PBOP and PBOL. Simulation is conducted in MATLAB, and the main parameters are shown in Table 1.Figure 6
Simulation scene of the road.Table 1
Major simulation parameters.
ParametersDefault valuesBit rate18 MbpsMessage packet size500 bytesRTB packet size20 bytesCTB packet size14 bytesSlot time13μsDIFS58μsSIFS32μsTransceiver’s switching time1μsCommunication range500 mIn the following we will give a brief overview of metrics. Partition delay is the time consumed during the partitioning phase.Nm,k means the number of time slots consumed if k-segment is selected in mth iteration. Pselm,k denotes the possibility of k-segment being selected in mth iteration. Tslot is the value of every slot. The average partition time consumed Tpart is shown as
(2)Tpart=∑m=1M∑k=1NNm,kPselm,k+1Tslot.Contention latency is the time consumed in the contention phase, and the equation for the average contention delay is shown as the formula (3). Pselk means the possibility of k-segment being selected as the final segment in the last iteration. Tcont_segk means the contention latency of k-segment.
(3)Tcont=∑k=1NMTcont_segkPselk.One-hop delay is the average time consumed of one-hop message delivery; the equation for it is shown as the formula (4). Tinit means the initializing time (i.e., sender accesses the channel), Tpartion is the partition delay, and Tcontention is the contention delay which are explained as before. Tdata means the time consumed of the data transmission.
(4)Td=Tinit+Tpartion+Tcontention+Tdata.One-hop message progress is the ratio of the road length that the selected relay can cover andLengthoptimal, the equation for it is shown as the formula (5). Lengthrelay represents the length of road that the selected relay can cover, and the disseminated message has not arrived. Assuming the node can be at any road location in the current sender’s communication range, Lengthoptimal means the maximum length of the node can cover and the disseminated message has not arrived.
(5)β=LengthrelayLengthoptimal.Message dissemination speed is the propagation velocity of the message disseminated, and the equation for it is shown as the formula (6). Lengthroad represents the length of road that the message has been arrived. Tconsu means the time consumed to cover the road segment with the length being Lengthroad.
(6)Vspeed=LengthroadTconsu.


### 5.2. Simulation Results

The partition latency of the proposed solution is checked with the road segment betweenS1 and E1 of Figure 5. The partition latency under the different vehicle densities is shown as Figure 7. The partition latency of BPAB keeps stable, and the partition latency of the other three methods decrease with the increment of the vehicle density. The number time slots spent for the partition procedure of BPAB is fixed as M−1. If there are more available vehicles locate on the road segment, then there will be no need to waiting too long to select the segment with vehicles. The partition latency of PBOL is lower than PBOP, because the distance between vehicles and the reference point maybe similar but the road coverage capability of the vehicles maybe different. The advantage of PBOL is not obvious anymore with increase of vehicle density, because there will be more vehicles close to each other and these vehicles have the similar capacity of road coverage. As to these vehicles in PBOP, the distance from the reference point is also similar.Figure 7
.Partition delay under different vehicle densities.In order to verify the relay selection effectiveness of the method proposed, PBOL is compared with BPAB, 3P3B, and PBOP in the view of contention delay. The result is shown in Figure8, we can see that the contention delay of PBOL is lower than another three methods. Because the relay node is selected based on the length of the road, it can cover instead of the distance from the sending node or the reference point. Some neighbor nodes may have the similar distance from the sending node or the reference point, but they have the different road cover capability and then they are mapped into different waiting slots. This can reduce the probability of collision and shorten the contention delay.Figure 8
Delay of contention under different vehicle densities.For the purpose of verifying the effectiveness of the proposed relay selection scheme, the proposed scheme PBOL is compared with BPAB, 3P3B, and PBOP in the term of one-hop average delay under different vehicle densities. The result is shown in Figure9, and we can see that the delay of our method PBOL is lower than another three methods in term of one-hop average delay. Because the waiting delay of the neighbor nodes in our method is determined according to the length of the road it can cover, and nonequal length partition of the coverage length is adopted. Collision probability of the neighbor nodes’ response will be lower which results in the lower competition delay and one-hop delay.Figure 9
One-hop average delay under different vehicle densities.The proposed method PBOL is compared with other three methods BPAB, 3P3B, and PBOP in terms of the average one-hop message progress. As the vehicle density increases, the average one-hop message progress of several schemes also increases to some extent and finally is maintained at a stable state, which is shown as Figure10. That is because there are more available candidate nodes with the increment of the vehicle density. Once the vehicle density reaches a certain level, the improvement of average one-hop message progress is limited. PBOL has a better average one-hop message progress compared with the other three methods because PBOL selects the relay based on the road coverage capability of the candidate node and the other three methods select the relay based on the distance between the candidate node and the reference point.Figure 10
One-hop average message progress under different vehicle densities.PBOL is compared with BPAB, 3P3B, and PBOP in terms of message propagation speed so as to verify the effectiveness of the relay node selection scheme proposed in this paper. The message propagation speed of several schemes under different vehicle densities is compared. The result is shown as Figure11, and we can see that PBOL has obvious superiority compared with another three methods in term of the propagation speed. Because PBOL considers the road cover capability of the neighbor node, not the distance between the neighbor node and the sending node or the reference point. Meanwhile, we use bidirectional relay to broadcast the message when necessary. The method can make the message cover more parts of the road with less hops and improve the speed of message dissemination.Figure 11
Message dissemination speed under different vehicle densities.


## 5.1. Simulation Settings

In order to evaluate the performance of the relay selection method, we choose a 4 km long mountain road as the simulation scene which is in Ziquejie Park, China [45] and shown as the Figure 6. The message is expected to cover all parts of the road from the Start to the end. The position distribution of vehicles on the road obeys Poisson distribution, and vehicles drive at a fixed speed on the road without lane change and overtaking. The speed of vehicles obeys the uniform distribution in 1/2vmax,vmax. Due to the mountain road condition, the maximum speed vmax is 40 km/h. In order to verify the performance of the scheme in different vehicle densities, the vehicle density varies from 0.025 to 0.305. The arrival rate of the message is set to 2 EMs/s. PBOL is compared with binary-partition-assisted MAC-layer broadcast method (BPAB) [46], trinary partitioned black-burst-based broadcast mechanism (3P3B) [44], and relay selection based on the distance to reference point (PBOP) [45] in the view of contention delay, one-hop delay, and message propagation speed. M,N,ω=2,4,2 in PBOP and PBOL. Simulation is conducted in MATLAB, and the main parameters are shown in Table 1.Figure 6
Simulation scene of the road.Table 1
Major simulation parameters.
ParametersDefault valuesBit rate18 MbpsMessage packet size500 bytesRTB packet size20 bytesCTB packet size14 bytesSlot time13μsDIFS58μsSIFS32μsTransceiver’s switching time1μsCommunication range500 mIn the following we will give a brief overview of metrics. Partition delay is the time consumed during the partitioning phase.Nm,k means the number of time slots consumed if k-segment is selected in mth iteration. Pselm,k denotes the possibility of k-segment being selected in mth iteration. Tslot is the value of every slot. The average partition time consumed Tpart is shown as
(2)Tpart=∑m=1M∑k=1NNm,kPselm,k+1Tslot.Contention latency is the time consumed in the contention phase, and the equation for the average contention delay is shown as the formula (3). Pselk means the possibility of k-segment being selected as the final segment in the last iteration. Tcont_segk means the contention latency of k-segment.
(3)Tcont=∑k=1NMTcont_segkPselk.One-hop delay is the average time consumed of one-hop message delivery; the equation for it is shown as the formula (4). Tinit means the initializing time (i.e., sender accesses the channel), Tpartion is the partition delay, and Tcontention is the contention delay which are explained as before. Tdata means the time consumed of the data transmission.
(4)Td=Tinit+Tpartion+Tcontention+Tdata.One-hop message progress is the ratio of the road length that the selected relay can cover andLengthoptimal, the equation for it is shown as the formula (5). Lengthrelay represents the length of road that the selected relay can cover, and the disseminated message has not arrived. Assuming the node can be at any road location in the current sender’s communication range, Lengthoptimal means the maximum length of the node can cover and the disseminated message has not arrived.
(5)β=LengthrelayLengthoptimal.Message dissemination speed is the propagation velocity of the message disseminated, and the equation for it is shown as the formula (6). Lengthroad represents the length of road that the message has been arrived. Tconsu means the time consumed to cover the road segment with the length being Lengthroad.
(6)Vspeed=LengthroadTconsu.


## 5.2. Simulation Results

The partition latency of the proposed solution is checked with the road segment betweenS1 and E1 of Figure 5. The partition latency under the different vehicle densities is shown as Figure 7. The partition latency of BPAB keeps stable, and the partition latency of the other three methods decrease with the increment of the vehicle density. The number time slots spent for the partition procedure of BPAB is fixed as M−1. If there are more available vehicles locate on the road segment, then there will be no need to waiting too long to select the segment with vehicles. The partition latency of PBOL is lower than PBOP, because the distance between vehicles and the reference point maybe similar but the road coverage capability of the vehicles maybe different. The advantage of PBOL is not obvious anymore with increase of vehicle density, because there will be more vehicles close to each other and these vehicles have the similar capacity of road coverage. As to these vehicles in PBOP, the distance from the reference point is also similar.Figure 7
.Partition delay under different vehicle densities.In order to verify the relay selection effectiveness of the method proposed, PBOL is compared with BPAB, 3P3B, and PBOP in the view of contention delay. The result is shown in Figure8, we can see that the contention delay of PBOL is lower than another three methods. Because the relay node is selected based on the length of the road, it can cover instead of the distance from the sending node or the reference point. Some neighbor nodes may have the similar distance from the sending node or the reference point, but they have the different road cover capability and then they are mapped into different waiting slots. This can reduce the probability of collision and shorten the contention delay.Figure 8
Delay of contention under different vehicle densities.For the purpose of verifying the effectiveness of the proposed relay selection scheme, the proposed scheme PBOL is compared with BPAB, 3P3B, and PBOP in the term of one-hop average delay under different vehicle densities. The result is shown in Figure9, and we can see that the delay of our method PBOL is lower than another three methods in term of one-hop average delay. Because the waiting delay of the neighbor nodes in our method is determined according to the length of the road it can cover, and nonequal length partition of the coverage length is adopted. Collision probability of the neighbor nodes’ response will be lower which results in the lower competition delay and one-hop delay.Figure 9
One-hop average delay under different vehicle densities.The proposed method PBOL is compared with other three methods BPAB, 3P3B, and PBOP in terms of the average one-hop message progress. As the vehicle density increases, the average one-hop message progress of several schemes also increases to some extent and finally is maintained at a stable state, which is shown as Figure10. That is because there are more available candidate nodes with the increment of the vehicle density. Once the vehicle density reaches a certain level, the improvement of average one-hop message progress is limited. PBOL has a better average one-hop message progress compared with the other three methods because PBOL selects the relay based on the road coverage capability of the candidate node and the other three methods select the relay based on the distance between the candidate node and the reference point.Figure 10
One-hop average message progress under different vehicle densities.PBOL is compared with BPAB, 3P3B, and PBOP in terms of message propagation speed so as to verify the effectiveness of the relay node selection scheme proposed in this paper. The message propagation speed of several schemes under different vehicle densities is compared. The result is shown as Figure11, and we can see that PBOL has obvious superiority compared with another three methods in term of the propagation speed. Because PBOL considers the road cover capability of the neighbor node, not the distance between the neighbor node and the sending node or the reference point. Meanwhile, we use bidirectional relay to broadcast the message when necessary. The method can make the message cover more parts of the road with less hops and improve the speed of message dissemination.Figure 11
Message dissemination speed under different vehicle densities.


## 6. Conclusion

The paper proposed a relay selection method based on the maximum road coverage capacity to improve the message dissemination efficiency on curve road in VN. The method can reduce the waiting delay of neighbor nodes and improve the access efficiency. When there is an uncovered road segment between the current relay and the prehop sending node, this paper proposed a bidirectional message dissemination method based on the bidirectional relay selection, and the method can speed up the message dissemination in an emergency. The simulation results indicate that our proposed data dissemination solution is best when the speed of message dissemination is a real concern in VN. In the future, the data dissemination method based on the network coding will be explored in vehicular networks.



---

*Source: 6836268-2022-03-24.xml*