An Alternative Safety Communications Protocol for V2V and V2I
Vehicle to vehicle (V2V) and vehicle to roadside infrastructure (V2I) communications will almost certainly play a major role in improving automotive safety in the future. The federal government, the car companies, and the major supply tiers are embarking on the design of a truly revolutionary system commonly called vehicle and infrastructure integration or VII. Much progress has been made to date including several vehicle test fleets. This system offers the potential to make significant improvements in vehicular safety, travel efficiency, and infotainment.
The high-level premise is that V2V and V2I can increase vehicular safety by providing information in a timely manner to enable drivers to avoid accidents. VII also can generate information sent to state and local data centers, which enable real-time traffic re-routing to more efficiently utilize the roadways. When the safety aspects of VII are considered, the communications protocol must be carefully chosen. The system must have the ability to deliver all messages within a defined latency period. Missed messages can significantly degrade the safety capability of the system or in extreme cases render it ineffective.
The current communications protocol being used for VII communications in test fleets evolved from a desktop wireless communications standard (IEEE 802.11a), which was introduced in the late 1990s. Its selection criteria for automotive was based primarily on the fact that the technology is mature and in high volume production (commercial and home wireless routers), driving down the cost. The 802.11a standard is intended for residential and office environments where subscribers are not moving rapidly, and where delivery of high data rate in a fairly benign radio environment is more important than operating with the radio link impaired by motion or rapid multipath fades. The fundamental structure of the 802 media access control (MAC) protocol is not intended to operate with hard real-time deadlines. These communications systems were never designed to handle hundreds of vehicles that must communicate in real time in order for mission-critical safety messages to be sent and received with a specified latency.
The key to understanding the deficiency of the current communications protocol is to understand how it resolves message collisions or what happens when multiple cars try to send messages at the same time. The current protocol implements carrier sense multiple access or CSMA. The protocol allows message collisions and then arbitrates the collisions. When vehicles want to transmit, they first listen to see if the channel is clear and then transmit. If two cars decide to transmit at nearly the same time they will not hear each other and will jam each other's transmissions. When a car fails to receive an acknowledgment from the intended recipient, each car will repeat its message. If many subscribers attempt to transmit at nearly the same time, for example to report an accident, then there will be many failed transmissions, many repeat transmissions, and the resulting avalanche effect may jam the bus for quite some time (referred to as “channel crowding” by VII engineers). CSMA arbitrates these message collisions with variable re-transmit times. Since message re-transmissions will occur at variable restart times, theoretically the probability of a collision on re-transmit is lowered. However, depending on how many vehicles are trying to re-transmit these transmissions may also have collisions. In desktop systems message collisions may result in slight delays getting to the Internet. In mission-critical systems this can cause serious problems.
The important result of this discussion is that the CSMA system has statistically indeterminate latency. This means that the message latency cannot be determined by calculation. Safety critical messages, therefore, cannot be guaranteed to be delivered in time to impact vehicle safety or to meet system latency specifications. For this reason, messaging protocols such as the one employed for VII are rarely used for mission-critical safety applications. Quantification of the real-world problems CSMA raises for vehicular safety application has been discussed in various IEEE papers.
CSMA VS TDMA
Contrast this with a time division multiple access (TDMA) approach. In TDMA, each vehicle is given its own unique time slot in which to transmit. Where CSMA allows message collisions TDMA prevents message collisions. In a TDMA system the latency is statistically determinate and can be easily calculated. Knowing the total number of slots and the timing for the entire frame, the worst-case latency can be established. In a TDMA system the safety-critical messages can be delivered because only one vehicle at a time is permitted to transmit.
TDMA can be visualized as a gear-toothed wheel. As the wheel spins, the gear teeth represent the unique time slots assigned to each vehicle. For example, if the repetition rate of the wheel is 100 ms the worst-case latency is when one car wants to send a message just after its assigned slot. In this case, it would have to wait 100 ms to transmit, making the system worst-case latency 100 ms or average latency 50 ms. A visualization of TDMA as a slotted wheel is shown in Figure 1.
One must ask at this point why the automotive protocol does not use TDMA. In most TDMA systems there is a master that assigns the slot times. In automotive, for vehicles traveling autonomously down the road, no master exists. However, a number of systems exist today that have self-assigning TDMA protocols. Europe's Cartalk2000 developed just such a system. There also exist shipboard identification systems and military systems that use self-assigning TDMA shown in Figure 2. This figure shows a number of cars moving down the road in various positions. Through reuse algorithms, such as are employed in the cellular industry today, slots can be dynamically reassigned as is shown here. Because automotive communication is short range, cars 1* and 2* are not in contact with the cohort of cars containing cars 1 and 2 and therefore slots 1 and 2 can be reused. A TDMA system with autonomous slot assignments should be looked at seriously for automotive safety applications. Discussions regarding CSMA versus TDMA for V2V and V2I parallel the discussions regarding statistical determinacy in vehicle buses such as CAN and Flexray.
Once a TDMA system is implemented another system problem can be readily solved. Today, for safety, some believe the accuracy specification for vehicle position must be one foot or greater to support safety use cases. Unassisted GPS systems are not capable of one-foot position accuracy. However, once the TDMA protocol is implemented, a time of flight algorithm can be used to significantly improve position accuracy. Each car can send its GPS-calculated location to all other cars during its assigned slot time. Each car looks like a GPS satellite to other cars and stochastic noise in the GPS position calculation can be filtered out. When each car transmits it also sends a time stamp. Since the receiving vehicles know the time the message was sent and the time it was received, a time of flight measurement of position can be made. Time of flight information can resolve 1 nanosecond in time difference between the time a car sends out a transmission and the time another car receives the transmission. At the speed of light (radio propagation) 1 nanosecond corresponds to 1 foot. With the GPS information from other vehicles and the time of flight information fed into a Kalmann filter, simulations predict accuracies of one foot are attainable.
As an example, in Figure 3 car A and car B's GPS calculated positions are shown as well as their actual position. GPS error is usually estimated at 15-20 feet and GPS error bands would be 15-20 foot diameter circles around each car's reported position. Additional information from the time of flight calculation shows car A and car B are actually only 1 foot apart. This makes the GPS error bands significantly tighter as portions of the error band would yield an impossible solution. In Figure 3, A and B are estimates based on Kalmann filtering, which show higher accuracy than by GPS alone. As more vehicles are involved, the actual and estimated positions converge.
A third problem that faces the automotive communications environment is the multipath. This is a signal reflection problem where the transmitted signals bounce off other cars, trees, buildings, etc. and distort the actual signal. Most people have readily experienced this problem when listening to a weak FM station in an urban environment as the signal fades in and out. The two effects of multipath are signal cancellation and intersymbol interference, shown in Figure 4.
The problem of multipath has already been seen in VII vehicle test fleets. It is quantifiable based on packet loss in the communications channel. The 802.11a standard utilizes a modulation scheme called orthogonal frequency division multiplexing or OFDM. OFDM has been recognized as being prone to multipath. Newer generations of home and commercial routers (802.11n), WiMAX, and the European broadcast television standards (DVB-T and DVB-H) all use a new modulation scheme called coded OFDM (COFDM), which is much more resistant to multipath.
Putting together the ideas of using an autonomous self-assigning TDMA, along with car-to-car time of flight ranging, and COFDM offers the following significant advantages for V2V and V2I safety systems:
Statistically determinate, low latency messaging, which is required for safety applications.
Time of flight vehicle ranging that significantly improves vehicle-positioning accuracy, as compared to unassisted GPS-based methods. This reduces the component cost of implementing assisted GPS systems.
Advanced coding methods, developed since 802.11a and now commonly in use significantly reduce multipath in systems with rapid motion.
The solution has the promise to be commercially viable at a lower cost than the current protocol being pursued for VII.
Automotive Communications Systems, Inc. has applied for a patent for the above approach. With our development partner, STMicroelectronics, we are working jointly on bringing this new safety protocol to the market as an alternative to the current protocol being used for VII.
Milt Baker is a co-founder of Automotive Communications Systems in Ann Arbor, MI. He has more than 30 years experience in automotive electronics, and began his career working on engine controls and body electronics at General Motors, and subsequently held significant positions at Motorola Automotive.
Larry Hill is also a co-founder of Automotive Communications Systems in Ann Arbor, MI. He has more than 30 years in commercial and military electronics with a specialization in radio communications. He has worked in large companies and led a number of start-ups.