A Method for the Rapid Propagation of Emergency Event Notifications in a Long Vehicle Convoy (2024)

1.1. StringStability

The main challenge facing vehicle convoys is a phenomenon known as string stability. Typically, aconvoy of vehicles tries to maintain a certain headway distance or time between each other using sensors such as radar. If a vehicle experiences a disturbance in its velocity (such as applying the brakes), then the vehicles behind it apply actuations according to their control law to regain the nominal headway. If the disturbance is large enough or fast enough, then it may send the system into an unstable region, depending on various factors. A familiar example of string instability is in “phantom traffic jams”, where small decreases in the speed of a leader can cause follower vehicles to overcorrect. This, inturn, causes even greater overcorrection as the “wave” propagates rearward to the point that some vehicles may come to a complete stop on a highway. In short, this is a problem of delays. Even if the system could instantaneously recognize and decide upon an appropriate course of action, there are still unavoidable delays in vehicle actuation. The follower vehicle’s sensors only notice a change after the leader vehicle’s actuation delays have concluded. Thus, when considering its own actuation delays, thefollower has less time to react and so may need to apply a higher magnitude control input compared to the leader. If the follower could be informed of the leader’s actuation intent at the time that the decision is made, then the effect of actuation delays can be largely negated. At this point, the problem becomes one of communication delay. While this work does not address how communication delays affect a string-stable controller design, there is a wealth of prior research on this type of problem. Seileretal. discussed the general effects of string stability in a vehicle platoon that is controlled using a fixed inter-vehicle spacing[6]. Their findings showed that disturbance sensitivity increases for rearward vehicles when only information on the immediate neighbor is known, such as only using sensors or only having communication with the vehicle’s immediate leader. Only upon incorporating information on the behavior of the ultimate leader did the sensitivity decrease further down the platoon. Fernandesetal. created a more real-world style of experiment by directly addressing communication delays, amongother things[7]. In particular, they utilized anticipatory information broadcast (what a vehicle plans to do in the near future), afully non-overlapping transmission schedule, andsynchronized vehicle actuation to maintain the stability of the platoon. The most relevant aspect here is in how heavily the platoon leader’s information is weighted in the follower’s controller. When the leader’s information has no effect outside its immediate follower, theplatoon displays instability. The platoon becomes stable when the leader’s information is almost exclusively used. Zhengetal. discussed how a vehicle platoon’s internal stability is affected by communication topologies and the vehicles’ inertial delays[8]. While their work did not specifically deal with string stability, it did show how delays in information flow dramatically change the characteristics of the vehicle platoon. In their results, thetopologies that do not incorporate a direct link to the leader result in much greater spacing errors further rearward in the platoon when a disturbance occurs, ascompared to topologies that do incorporate a link to the leader. Ning and Lin worked toward finding string stability even when communication delay is randomly distributed[9]. What they showed is a method for determining a minimum headway time that guarantees string stability given a certain packet delivery probability. Specifically, their method allows for a certain percentage of message delays to be greater than a threshold value while still maintaining string stability. This work is pertinent here in that it shows how smaller inter-vehicle spacings become feasible as the delays become shorter and more consistent. Samii and Bekiaris-Liberis developed a linear predictor-feedback cooperative adaptive cruise control (LPF-CACC) that is robust to communication delays[10]. Of importance to us is their graphs that show how communication delays affect the region of parameters that guarantee string stability. As they increased the communication delay, the region shrinks, meaning more parameter sets are now string unstable. As with Ning and Lin, Samii and Bekiaris-Liberis also showed that there is a clear tradeoff between allowable communication delay and headway time. This further reinforces the idea that a lower communication delay allows for tighter vehicle platoons. Lastly, Tianetal. performed a similar analysis by performing a numerical analysis of a CACC vehicle platoon to show how string stability is affected by different parameter changes[11]. One set of graphs showed the string-stable set of control gains for different constant communication delays. The volume of the “stable body” as they called it shrinks considerably as the communication delay increases beyond 0.1 s. They later showed how spacing and speed errors propagate rearward through the platoon for different communication delays. In short, thelower the communication delay, the faster the error attenuates as it propagates rearward. When given a communication delay such that the control gains are on the edge of the stable region, thespacing and speed errors remain constant as they propagate rearward.

1.2. CommunicationProtocols

String stability issues can be mitigated or even eliminated if the information delay between the leader and the followers is reduced. This can be accomplished by proactively informing the surrounding vehicles of actuation events as soon as the decision is made. Without loss of generality, we will assume that the primary actuation of interest is a braking event. SAE J2945/1 defines the communications for on-board vehicle-to-vehicle (V2V) systems[12]. Note that SAE J2945/1B is the standard governing Class 8 vehicles such as tractor trailers, butit defers to SAE J2945/1 for BSM communication scheduling It defines, amongother things, theschedule for Basic Safety Message (BSM) transmission for each vehicle. A BSM contains information on the overall vehicle state as well as any high-importance events. However, even if SAE J2945/1 is used, there can be up to 0.1 s of delay before transmitting a BSM that says a hard braking event is occurring. To make matters more difficult, there is no guarantee that the BSM is received. If the wireless communication channel is unreliable, then the overall delay between event and message reception may be much higher. While SAE J2945/1 has mechanisms in place for estimating the probability of a remote vehicle’s reception of a transmission, it does not allow BSM transmissions to occur any more frequently than10 Hz.

1.3. CommunicationChannels

Generally, thewireless channel in vehicular environments can be characterized using a combination of log-distance power loss and Nakagami fast fading. As a brief summary, log-distance states that receive power drops as a function of distance to the power of n, and Nakagami said that received power is randomly distributed more widely as the value of m decreases. Thus, ahigh probability of high received power over distance means a low log-distance n and high Nakagami m values. Molischetal. stated that for light traffic on a highway, the log-distance characterization parameter n generally falls between 1.8 and 1.9, withcrowded highways generally having higher values[13]. Molisch also stated that the fast-fading Nakagami m factor was usually 3–4 for short distances and less than 1 for long distances. Viriyasitavatetal. made similar findings, saying that the log-distance n could vary between 1.6 and 2.9 on the highway, 2.3 and 3.5 in suburban environments, and1.8 to 3.4 in urban environments[14]. Chengetal. focused on the 5.85–5.925 GHz range for their study and found similar results to those of Molisch with regards to the Nakagami m factor[15]. They found that m would typically be around 3 to 4 over a 0 to 5 m distance, while dropping below 1 at 70 to 90 m. Together, these findings imply that longer distance direct communications can be more challenging and much less predictable than shorter-rangecommunications.

1.4. AdHoc RoutingProtocols

Many would point to dedicated infrastructure, primarily cellular towers, asthe solution to vehicular message dissemination. While current and future cellular infrastructure could be used for this task, it may not always have the capacity, latency, or(most importantly) coverage to guarantee safety-critical communication. A potential solution could be the use of adhoc wireless networks, where participating devices take on the additional responsibility of routing messages for those that do not share a direct communication link. When applied to vehicles, this idea is known as a vehicular adhoc network (VANET). While there is a large body of work on standardizing the wireless communication systems for vehicles (e.g., IEEE P1609), a standard for vehicular adhoc routing has yet to be established. Thus, finding an effective and efficient routing scheme for VANETs has become the work of a large body of prior research. Li and Wang wrote a survey paper discussing the various types of routing protocols for VANETs[16]. Their findings indicate that standard adhoc routing protocols such as AODV and DSR are typically unsuitable for VANETs (see Section 3.3 for our tests on the matter). They mention geographic routing (using physical location to decide on the next hop) and cluster-based routing (recognizing groups of vehicles and assigning a “head” for each) among others as being attempts at solving the routing problem. A direct attempt at formulating a VANET routing protocol was made by Koubeketal. with their “Vehicular Reactive Routing” system[17]. The system was designed around the IEEE P1609 protocol stack and utilizes slightly modified versions of the existing messages. The relevant part of their system is in the retransmission choice mechanism. Every node that hears a packet being broadcast will decide on a backoff timer for retransmission. The timer was designed such that the node closest to and with the most similar motion to the destination will have the shortest timer and thus retransmit first. A similar backoff timer system was used by Sasakietal. for the purposes of removing neighbor discovery beacons in VANETs[18]. In their system, the rebroadcast delay is set purely based on proximity to the destination. The common thread in both systems is the use of “eavesdropping” to inform each node on the necessity of their retransmission, thus enhancing channel efficiency. Koubek primarily used the backoff timer as an arbitration mechanism, while Sasaki at least mentioned the benefits of redundant transmission paths. Lastly, Liuetal. approached the problem of safety message dissemination in an urban environment using clustering and vehicle movement prediction[19]. They recognized that infrastructure nodes will likely not be able to provide sufficient coverage to alert every vehicle of safety-critical information when and where it is needed. Their system constructs a “core” network of vehicles based on the vehicles’ trajectories in order to improve communication coverage. To find this set of vehicles, theinitiator sends a request indicating the region of interest for the safety message. The surrounding vehicles scale the delay of their responses to this request based on the similarity of their trajectories with respect to the region of interest. After the core vehicles are chosen by the initiator, those vehicles then repeat the process until as much of the region of interest is covered as possible. What many of the protocols mentioned here have in common is their use of backoff timers as more than just a message collision avoidance mechanism. Retransmission or response delays can be used to implicitly convey information about some relationship between the communicating vehicles, such as fitness toward a purpose.

3.1. Simulated WirelessChannel

We used ns3’s included YANS Wifi Physical and YANS Wifi Channel to simulate the physical layer of the channel. The propagation loss model was the combination of the log-distance, Nakagami, andrange cutoff values. Range cutoff was added to eliminate extremely low probability events from affecting the results. In addition, ns3’s included constant speed propagation delay model was used, thoughthis choice has little effect on the simulation’s fidelity. The simulated wireless channel was designed to be less reliable compared to the findings listed in Section 1.3. This was done for two reasons. First, we wanted to show the performance of our system in a degraded communication environment. Second, we wanted to reduce the number of simulated vehicles, asit would otherwise require a longer transmission distance to reach the desired reliability degradation. The issue of string stability still exists whether each “entity” is one vehicle or multiple all moving in unison due to being within the high-reliability transmission region of the leader. The approximate reception reliability vs. distance for the default parameter set is listed in Table 1.

3.2. Simulated WirelessProcotol

The lower layers of the network protocol consist of ns3’s included QoS WAVE MAC, 802.11p, andInternet stacks. These three stacks use default parameters aside from 802.11p, and we used OFDM 12 Mbps and 10 MHz instead of 6 Mbps. This change should have no effect on the end result; it is only included for completeness. Every vehicle in the simulation has a unique IP address on the samesubnet.

3.3. OLSR andAODV

To form a point of comparison for the effectiveness of the Convoy VANET System, we initially chose to test against two popular adhoc routing protocols: Optimized Link State Routing (OLSR) [20] and Adhoc On-demand Distance Vector (AODV) [21]. These two protocols represent the typical forms of proactive and reactive approaches to adhoc routing, respectively. The intention was to compare these two protocols against Convoy VANET in aspects such as message delay and route maintenance overhead. The experiment setup is similar to the experiments conducted on the Convoy VANET system; most importantly, the vehicles were spaced 30 m apart to induce an approximate 85% reception reliability. The only differences are that the convoy was only ten vehicles long (instead of 20) and the head of the convoy was unicasting its message to the last vehicle in the convoy (as opposed to broadcasting). The lack of broadcast is because OLSR and AODV do not handle broadcasts particularly well in ns3, andat this stage of the work, the experiment was meant to be a first pass at obtaining a point of comparison. The results of this experiment lend credence to the statements of Li and Wang in that normal routing protocols are ill suited for VANETs[16]. In short, both OLSR and AODV failed to reliably propagate packets down a ten-vehicle convoy. The packet delivery ratio to the last vehicle was consistently well under 50%, withratios as low as 10% being not uncommon. When it did manage to deliver a packet, it would occasionally be delayed by as much as one full second, which is obviously unacceptable. The exact results of these tests are not shown primarily because of the lack of nuance and useful information. Also, this particular experiment is simple enough to build for oneself using the simulation parameters provided throughout Section 3.

The reason why OLSR and AODV ultimately failed is due to the fact that they do not have any substantial reception reliability mechanisms. This is understandable given that they exist at the network layer of the typical OSI or TCP/IP stack instead of the transport layer. If we had added reliability guarantees using TCP instead of UDP, then we would have also foregone the ability to broadcast the messages at the transport layer (unless we make significant modifications to TCP). One could argue that transmission eavesdropping could still occur with TCP andthat the participatory devices could still exchange data fragments until all have received the message. However, this approach only moves the problem up to the application layer, andthe process for the efficient exchange of the eavesdropped data would still need to be defined.

3.4. Convoy VANETSystem

The purpose of the convoy VANET system is to quickly and efficiently disseminate Safety Messages (SM) to all vehicles in the convoy. An SM can be any highly time-sensitive piece of information, buthere, we considered it to be a hard braking maneuver. To accomplish this goal, theConvoy VANET system included a few independent components. The most important component is the routing choice method. In essence, therouting system is a combination of traditional adhoc routing schemes and the methods proposed by Koubek and Sasaki. When a node decides to (re)transmit an SM it will decide upon a preferred retransmitter (PRTX). This choice of PRTX will be listed in the SM and read by all that receive the message. If the designated PRTX receives the SM, it will retransmit the SM immediately. Every other node that receives the SM will decide on a retransmission delay that is based on its physical distance to the designated PRTX (if it is known). If a node hears that the SM has been retransmitted by a rearward peer, then it cancels its queued SM retransmissions to reduce the number of unnecessary retransmissions. After the initial “wave front” of transmissions, thenodes will be listening for any peers that did not receive the SM and then attempt to rectify the situation. The goal of this type of system is for the SM to have the opportunity to move as quickly as possible down the convoy, even if it is not received by every node on the first pass. The remaining details will be described in the followingsubsections.

3.4.3. RoutingProtocol

The routing protocol is the main contributor of the Convoy VANET system’s behavior. The routing protocol’s major components are reliability mapping, preferred retransmitter updating, delayed SM scheduling, output routing, andinputrouting.

Reliability mapping is simply the periodic check of how many VS messages have been received compared to how many should have been received. As VS messages are received, they are added to a map that is keyed off of the remote node ID. In this way, every vehicle is tracking the reception reliability between itself and every other vehicle. Outdated data are periodically pruned to prevent memory leaks. While this assumes symmetric channel reliability, it could be cumbersome in a real system to include reliability metrics in the state message (see Future Work, Section 7). These reliability metrics are used in the preferred retransmitterupdate.

Preferred retransmitters (PRTXs) are a part of the message propagation system. In short, aPRTX is a node that is designated by the original (re)transmitter to be the one that retransmits an SM as soon as they receive it. Every other node that hears an SM will set their retransmission delay according to various metrics outlined below. This idea is meant to be a hybrid between the retransmission delay systems of Koubek and Sasaki and the single-retransmitter systems used in most adhoc routing protocols. The PRTX is chosen based on two metrics: distance and reliability. The PRTX is simply the node that is furthest rearward that maintains some minimum level of reception reliability. If no nodes meet the reliability requirement, thePRTX is set to null, meaning every node that hears the transmission will fall back onto the retransmission delay system, asoutlined later. The PRTX is periodically updated based on the current reliabilitymap.

The choice of retransmission delay is given by one of two equations. If the SM includes a PRTX and the node knows its location, then the delay is given by Equation(1):

$$d=(D\ast t_D)+r_{D,min}+(R_1\ast r_{D,range})+(R_2\ast r_{S,range})$$

(1)

where d is the total delay, D is the distance to the PRTX, $t_D$ is the time per unit distance, $r_{D,min}$ is the random component minimum where distance is known, $r_{D,range}$ is the random component range where distance is known, $r_{S,range}$ is the random component range for adding an extra “small” amount of randomness, and$R_1$ and $R_2$ are uniform random variables between 0 and 1. Note, while the “small randomness” component could just as well be added to the other range components, it is possible in the code to disable its inclusion, and while this functionality is never used, it is included here for accuracy and completeness. Otherwise, thedelay is purely random and given by Equation(2):

$$d=r_{R,min}+(R_1\ast r_{R,range})+(R_2\ast r_{S,range})$$

(2)

where $r_{R,min}$ is the random component minimum when the distance is unknown, and $r_{R,range}$ is the random component range when the distance is unknown. All other variables are the same as in Equation(1). After the delay is determined, thenode checks its currently scheduled transmissions to ensure that no two occur within a certain amount of time of each other. This time amount is called the “transmission keep-out” time (see Section 4). Any SM transmissions that fall within the keep-out time of another will simply bedropped.

Every packet created by a node passes through the output routing function. In the case of the leader sending an SM, it checks whether this SM has been confirmed as having propagated rearward. If it has not propagated rearward, then the function adds the current choice of PRTX to the packet and allows it to be sent. If the SM is confirmed as having propagated rearward, then the function does not allow the packet to be sent (see Section 3.4.1). If the message is a VS, then it attaches a list of the most recently received SMs and allows the packet to be sent. Note that theSM list does not include the entire SM but merely an identifying value for each one. This is to reduce the amount of data added to the VS message. The received SM list is used by other nodes as a confirmation of reception. If the VS’s sender is behind the receiving node, then this confirmation is also proof of rearward propagation. Hearing a rearward node’s retransmission of an SM is the other method of confirming rearwardpropagation.

Every packet received by a node passes through the input routing function. While the input routing function handles both VS and SM packets, VS packets are simply stripped of their SM lists and then handed off to the receiver (see Section 3.4.2). Received SM lists are handled by Algorithm 1. Received SMs are handled by Algorithm 2. Note, in Algorithm 1, the for-each loop uses the set difference operation in its check, meaning that it is executing for every SM we have received thus far but not including every SM the sending node has listed as received.

Algorithm 1:Handler Function for Received SMList

Algorithm 2:Route Input Function forSM

5.1. Known BehavioralAnomalies

In most of the plots showing number of retransmissions, node 19 (the one at the end of the convoy) is shown to consistently transmit more than the others (see Figure 8, Figure 10 and Figure 12). This is because node 19 is effectively unaware that it is the end of the convoy. Because there is no rearward peer to retransmit the SM to (which would cause node 19 to cancel its pending retransmissions), it simply continues retransmitting until the retransmission counter hits zero. This issue was deemed a low priority as it is isolated to a single node and predictable due to its position. Nevertheless, it is still mentioned in the Future Work section (Section 7). The similarly high transmission numbers of node 0 are discussed in Section 5.3.

5.2. General Trends andAnalysis

The Convoy VANET system generally works well at ensuring a quick propagation of SMs. The standard spacing scenarios consistently show less than 20 ms propagation times to the end of the convoy, even with a doubled delay and delay randomness (Figure 1, Figure 3 and Figure 5). All but the far-spacing plus doubled-delay situation (Figure 15) consistently resulted in propagation times lower than 0.10 s to the end of the convoy. The reception delay generally follows a linear trend outside the close-spacing situations (Figure 7, Figure 9 and Figure 11), and the number of SM transmissions are mostly consistent across the convoy (barring nodes 0 and 19 of course). The number of SM transmissions is typically reasonable given the channel reliability as well. For a 65% reliability link (i.e., a 60 m distance), it would require, on average, approximately 1.54 transmissions before the first successful reception. This means that there would be an average of approximately three transmissions for a successful single message exchange between two nodes. We see for the far-spacing situation that most of the nodes transmit between one and five times per safety event (see Figure 13, Figure 15 and Figure 17). The 3D bar plots show that for each safety event, there is a small subset of nodes that transmit much more than the others (e.g., Figure 2, Figure 4 and Figure 6). However, this subset typically changes for each safety event, leading to the bar and whisker plots showing an even distribution of high-transmission outliers (e.g., Figure 14, Figure 16 and Figure 18). Doubled delays tend to increase the reception delay while having a minimal effect on the number of transmissions. Doubled-delay randomness tends to not increase the reception delay at all over standard delays, while also not having a significant effect on the number of transmissions. The most significant factor in the number of transmissions and reception delay is spacing, which it is effectively a proxy for communication reliability. Close spacing results in many nodes receiving the first transmission, as seen by how the reception delays only increase marginally for the rearward nodes. Far spacing results in a wider variance of propagation delay as most receptions occur between immediate neighbors, leading to more opportunities for delays. The “far-to-close” spacing tests produce results that resemble a combination of all three fixed spacing tests. The reception delay plots in Figure 19, Figure 22 and Figure 25 show the higher-end tracking more closely to the far spacing tests and the lower-end tracking more closely to the standard- and close-spacing tests. The number of transmissions do not change much over the course of the vehicle movement, apart from the very last SM event at the closest distance having several non-transmitting nodes (Figure 20, Figure 23 and Figure 26). Of particular importance are Figure 21, Figure 24 and Figure 27. These figures illustrate the data contained in the reception delay plots in Figure 19, Figure 22 and Figure 25, respectively, but are here separated by SM events. They were included to show how the reception delay for each vehicle decreases as they move closer together. This highlights the Convoy VANET system’s ability to adapt to changing scenarios, taking advantage of a more reliable communication channel to reduce propagation delay.

5.3. Outliers

Occasionally, there will be a node with a reception delay that is approximately 0.05 s to 0.10 s higher than that of its nearby peers. This occurs when an SM is transmitted but the skipped node does not receive it while a further node does. The further node then retransmits the SM, but againn the skipped node does not receive it while the original transmitter does, causing the original transmitter to recognize it as having propagated rearward. In assuming the skipped node does not receive the SM from any further rearward nodes’ transmissions, it must now wait until a node hears its VS, which indicates that it has not heard the SM. At this point, the nearby nodes will begin transmitting the SM again, allowing it to be received. Because the VS is transmitted every 0.10 s, this situation will incur, on average, 0.05 s of extra delay.

A more common outlier is node 0 transmitting SMs much more than its followers (see Figure 12). When any node transmits more than 5 SMs, it is usually a consequence of hearing a VS message and scheduling uncancelable delayed SM transmissions. This is especially prevalent with node 0 because of simulation timing consistency. Node 0 always sends the SM on the exact 5 s division (20.000 s, 25.000 s, 30.000 s, etc.). If another node schedules its VS before the minimum delay afforded by the retransmission system, then node 0 will schedule several uncancelable SM retransmissions (see Section 3.4.3). Other nodes do not exhibit this behavior as consistently because the time at which they first receive an SM is largely random, as opposed to node 0’s perfect consistency. This issue is not as prevalent with far spacing due to the lower reception reliability of VS messages, meaning only one node may trigger it semi-consistently instead of two or three. There is no mechanism in place to recognize the minimum amount of time needed before a confirmation of reception may be received (see Future Work, Section 7). While this issue may not be realistic, it was left in because it illustrates the main shortcoming of the system: the use of uncancelable SM retransmissions.