Turn, Turn, Turn

October 1, 2005 - By GPS World Staff

A number of factors have converged to promote the steady growth of in-vehicle navigation systems (IVNSs) within the automotive industry. When selective availability (SA) was set to zero on May 1, 2000, the performance of Standard Positioning Service (SPS) C/A-code receivers improved dramatically — virtually overnight. Users awoke the following morning and observed their receivers navigated remarkably better.

Additionally, commercial efforts to survey and digitize the vast North American road network intensified in the early part of this decade, which led to greatly improved quality and reliability of digital map data in geographic information systems (GISs). These mapping activities continue today at the same brisk pace and promise to further reduce vehicle navigation errors due to faulty GIS data.

Also, consumer familiarity with GPS technology has increased substantially over the past five years, spurring greater confidence in GPS-derived location data.

In addition to these contributing factors is the primary driver behind the rapid growth in IVNS technology: The downward trend in C/A-code receiver pricing.

In 1996, a typical handheld consumer GPS receiver cost more than $300. Today, a similar device sells for less than $100 and, at a slightly higher cost, may also contain a color display, a rich map database, and a serial interface to transfer the navigation data to an external application.

Unit size, weight, and power consumption also have trended downward. The net effect of these individual factors has been to accelerate the use of GPS within the automotive industry.

Road Obstacles. Nonetheless, significant technical challenges remain. A growing application of GPS/GIS technology involves providing timely and accurate turn-by-turn driving instructions to motorists. IVNSs may display these instructions on a map within the vehicle console and/or communicate the information verbally through spoken commands and street names, whichever the driver prefers.

In either case, the systems calculate in advance the most-efficient route to the driver’s requested destination using a route generator. Route generation may occur within the vehicle client (referred to as onboard navigation) or may be performed on a remote server (offboard navigation), whereby a high-bandwidth wireless data connection downloads turn-by-turn instructions to the vehicle client.

One of the application’s most difficult technical challenges is delivering reliable turn-by-turn navigation instructions in degraded GPS signal environments — in particular, the urban canyon environment found in most large cities.

Tall buildings, tunnels, and other barriers frequently obscure line-of-sight range measurements to orbiting satellites, limiting the receiver’s ability to compute a fix. Reflected multipath is also a common phenomenon that degrades fix accuracy and introduces the potential for false driving instructions.

Because many drive routes across North America pass through these environments, a reliable and cost-effective technical solution is required to overcome these challenges. Furthermore, a robust and repeatable method to test this system is needed to measure compliance with performance requirements across a broad spectrum of vehicles.

Inertial Sensors. A common approach in the automotive industry to minimizing the effects of degraded sky visibility and harsh urban multipath involves coupling the GPS receiver with an inertial sensor such as a gyroscope.

This dead-reckoning approach is supported by years of industrial research in applied Kalman filtering and sensor error modeling. However, there are two significant challenges to commercializing this approach for IVNSs:

1. First, to ensure two-dimensional (2D) rate gyros operate properly, we must mount gyros tangent to the Earth’s sur face (that is, flat or horizontal). This is not always feasible given the orien-tations of some embedded vehicle navigation systems. We can partially obviate this constraint by employing additional accelerometer sensors, but this approach introduces substantial design and manufacturing complexity. Replacing the 2D-rate gyro with a 3D gyro also solves the mounting problem, but at a significantly increased expense.
2. The second drawback of the gyro-based approach is its cost. Although the price of automotive-grade gyros gradually has trended downward over the past five years, a basic 2D device that satisfies strict automotive environ-mental requirements still costs a minimum of $10–12 in large quantities (more than one million). Current cost pressures in the automotive industry encourage suppliers and esigners to satisfy technical requirements at the lowest possible expense.

Figure 1 ABS system diagram

For these reasons, automakers and their IVNS suppliers have recently begun pursuing the innovative alternative of using independent wheel-speed sensor (WSS) measurements from the front and rear axles to calculate changes in yaw rate.

Wheel-Speed Sensors

WSSs are a fundamental component of the antilock brake system (ABS), which is standard equipment on nearly all new vehicles. They generate electrical pulses at frequencies proportional to the rotation rate of the individual wheels and deliver these signals to the ABS controller as shown in Figure 1.

Differencing the pulse rates between the left and right wheels allows an IVNS to calculate changes in vehicle heading. The system also can determine nondirectional vehicle speed by averaging the left and right signals.

Figure 2 Wheel velocities

The generalized equations for yaw rate estimation are given as (see Figure 2):

where the V xx terms represent the velocities at each wheel (first subscript: l = left, r = right; second subscript: f = front; r = rear) and tw r is the track width of the rear axle (the distance between the rear-wheel tire tracks).

Similarly, yaw rate derived from the front wheels is defined as:

where δ is the steering angle. Note the effective track width for the front wheels varies according to the radius of the turn. We must model this effect appropriately in software to accurately compute heading rate using data from the front wheels.

Data Distribution. Use of WSS signals to perform dead reckoning is also appealing because ABS controllers transmit independent wheel-speed measurements at regular and frequent intervals over the vehicle local area network (LAN) that links together the various onboard microprocessors.

Many IVNSs include a gateway to the vehicle serial data bus; therefore no additional input pins are required for these systems to receive the WSS electrical pulses. Obtaining these periodic wheel-speed data is simply a matter of modifying the LAN controller software within the navigation system to retrieve these messages and deliver them with minimum latency to the embedded GPS receiver in the desired format.

Directional Accuracy. How accurately can an IVNS use WSS data to calculate changes in vehicle direction?

Consider a vehicle with 27-inch (68.6-centimeter) -diameter tires (measured tread-to-tread) with nominal air pressure, rear track width of 62 inches (157.5 centimeters) and sensor resolution of 47 teeth per rotation. The worst-case resolution based on 1-pulse-per-second quantization error and sufficiently high data sampling rate by the ABS controller can be obtained as follows:

By using WSS measurements from both wheel pairs simultaneously, we can improve this value by a factor of two, achieving a heading rate resolution of 0.84 degree per second. This measurement resolution equates to a maximum accumulated error of 13 degrees over one-quarter mile (0.4 kilometer) when traveling at 50 miles per hour (80.5 kilometers per hour). In practice, actual results are considerably better because uncorrelated jitter in the left and right wheel sensor data is smoothed out over time (see Figure 3).

Figure 3 Sample wheel-speed sensor data. Epoch interval is approximately 53 milliseconds.

Design Challenges

While the example above illustrates WSS dead reckoning performance under worst-case data quantization conditions, a num-ber of important variables must be factored into the system design to achieve reliable navigation performance under various conditions.

Sensor Type. Automotive WSSs are classified as either active or passive. Active sensors are based on a Hall-effect transducer using an active magnetic pickup to convert wheel motion to an electrical signal.

Active sensors have the advantage of performing well at extremely low speeds. Conversely, passive sensors use the principle of variable reluctance, in which the sensor teeth travel through a passive magnetic field at sufficient speed to generate a low voltage analog waveform (Figure 4).

Figure 4 Passive wheel-speed sensor

These types of sensors exhibit a deadband, or a discrete speed below which motion is undetected (typically 2 to 5 kilometers per hour or 1.2 to 3.1 miles per hour). This design limitation can dramatically degrade vehicle navigation performance if the dead-reckoning software within the GPS receiver is not designed to identify this condition.

A challenging situation occurs when one wheel sensor is generating pulses while the opposite wheel sensor does not. This may occur, for example, when a vehicle initiates a gradual turn after being stopped at an intersection — for a brief period of time the inside wheel may not rotate fast enough to generate electrical pulses.

The same situation may also occur if the wires carrying the electrical signals from the WSS pairs to the ABS controller are significantly different in length, causing further attenuation of the weaker signal.

The temporary absence of sensor data that may occur in these examples might fool the dead-reckoning algorithm into underestimating the turn radius, consequently leading to an incorrect calculation of the vehicle heading. However, through careful, real-time analysis of the independent wheel-speed data, the system typically can detect this condition, thereby preventing mistakes in vehicle heading determination.

Sensor Tooth Count. The number of sensor teeth that pass through the magnetic pickup dictates the number of pulses generated per rotation. Heavy-duty vehicles such as trucks and sport utility vehicles often employ sensors with higher tooth counts. Smaller passenger cars may use sensors with fewer teeth. Although higher tooth counts provide greater quantization of wheel-rotation rate, it is important to design the system to operate reliably when fewer sensor teeth are present.

Tire Size. Changes in tire size occur constantly based on temperature, altitude, air pressure, and tread wear. Tires occasionally fail and must be replaced, often with a smaller-diameter spare.

Furthermore, some owners prefer to install custom wheels on their vehicles. As tire diameter varies, the distance traveled per WSS pulse also varies.

The dead-reckoning filter within the GPS receiver navigation engine must quickly adapt to all of these incremental changes in tire size to work properly under all conditions. This adaptation process is analogous to the continual estimation of gyro bias and drift terms in a traditional Kalman filter.

LAN Variability. The ABS controller must transmit wheel-speed messages across the vehicle LAN at a minimum rate of 10 Hz to provide sufficient resolution for the WSS dead-reckoning filter to detect small changes in heading.

Although this requirement is generally satisfied by most LAN architectures, not all new ABS controllers transmit wheel-speed data at an equivalent rate. Furthermore, there is broad diversity of LAN architectures and wheel-speed message formats between vehicles and vehicle manufacturers — requiring the LAN controller within the IVNS to flexibly adapt to the host serial data interface.

To simplify the processing of dead-reckoning inputs to the GPS receiver, LAN messages typically are accumulated at one-second intervals triggered by the rising edge of the GPS 1-pulse-per-second pulse.

It is important to note that wheel-speed LAN messages typically are not synchronized with an external timing source such as GPS. For example, a vehicle LAN designed to operate at a 20-Hz rate may actually transmit wheel-speed messages every 53 milliseconds — slightly slower than the 50 milliseconds expectation.

Because wheel-speed inputs are accumulated at precise one-second boundaries, the pulse-count inputs to the GPS receiver may spike every few seconds, giving the appearance of sudden decelerations and accelerations of the vehicle. This is simply because the LAN transmit interval may not multiply evenly into one-second boundaries.

This phenomenon is an artifact of message timing and will not affect navigation performance if it is managed properly in software. This effect is illustrated in Figure 5.

Figure 5 GPS-LAN timing mis-synchronization

Vehicle Chassis. Many important dead-reckoning parameters such as wheel track, wheelbase, center of gravity, sensor type, and minimum turn radius vary substantially from vehicle to vehicle.

These chassis parameters can be calculated automatically by comparing the output of the wheel sensors to GPS-derived position/velocity information. GPS data are used to continuously calibrate sensor data, ensuring that changes in heading and velocity derived from the wheel sensors will remain accurate. Conversely, navigation data from the wheel sensors is weighted more heavily when GPS information is less reliable, such as within a dense urban environment.

Wheel Slippage. Tires tend to slip on wet and icy roads. The same phenomenon occurs on gravel surfaces. Actively monitoring for this condition and discarding untrustworthy wheel data for short periods if a better data source is available can significantly mitigate this effect.

Figure 6 GPS/WSS dead-reckoning accuracy in Chicago

Road Tests

Because downtown Chicago contains particularly severe urban canyons (see photo), much of the navigation testing outlined in this article occurred within this city. Performance results for a vehicle in this environment are shown in Figure 6 and Figure 7.

We based the accuracy statistics upon a series of drives conducted throughout a four-hour period and derived the data using an automotive-grade gyro-based truth reference. Note that we discarded some gyro-based truth files due to poor performance.

Figure 7 2D ground plot (unaided GPS versus GPS/WSS dead reckoning)

The unaided GPS fix-density metrics achieved in Chicago are representative of a typical low-sensitivity GPS receiver in a severe urban environment. Note the significant improvement in fix density and 2D-position accuracy achieved through the use of WSS dead reckoning.

Test Barriers. Although tests similar to those described above provide an excellent venue for collecting system performance data, a number of variables make it impractical to conduct repeated and extensive drive tests in geographically separated cities.

Limited vehicle availability, varying GPS constellation geometry, unpredictable multipath effects, engineering resource availability, inclement weather conditions, and travel expenses make lengthy field trials by IVNS testers impractical. For these reasons, my company assisted in the development of an automated simulation capability to assess system performance for a wide class of vehicles under controlled multipath, obscuration, and satellite-geometry conditions.

These simulations can be repeatedly executed for extended periods of time at the developer’s lab facilities. This simulation system is shown in block-diagram format in Figure 8.

Figure 8 GPS/WSS dead-reckoning automated test setup

Simulations

Procedures for creating a GPS/WSS dead-reckoning simulation are described below.

First, we equipped a test vehicle with a generic GPS receiver capable of National Marine Electronics Association (NMEA) 0183 message-type output and a roof-mounted antenna.

NMEA Messaging. We connected a specially designed LAN-data-capture utility to the On-Board Diagnostics level 2 (OBD2) port below the steering wheel to retrieve wheel speed messages, odometer data, steering wheel angle, and transmission status messages. This data-capture utility creates an ASCII file of serial LAN messages interspersed with once-per-second $GGA/$RMC NMEA 0183 sentences and text markers to indicate the rising edge of 1-pulse-per-second pulses.

After remaining stationary in an open area for three minutes to ensure a 3D fix is achieved, we drove the vehicle for 90 minutes in open sky conditions with minimal obscuration. The test route contains a series of sharp left and right turns, several straight and curved road sections, forward and reverse maneuvers, and a varied speed profile. Upon completion of the test route, we switched off the data recorder.

LA SALLE ST., downtown Chicago

Motion Profile. Next, we used the recorded NMEA data file to create a 1-Hz motion profile for the GPS constellation simulator. We loaded the most-current almanac into the 12-channel simulator and initialized the scenario start time to the beginning of the test drive. We then set output power levels to the expected C/N0 values for open sky conditions with attendant radio-frequency (RF) cable loss.

We then connected the LAN data recorder to the simulation equipment on the test bench and toggled it to "playback" mode. The rising edge of the first pulse from the GPS simulator 1-pulse-per-second output triggers playback to the receiver being tested. The playback tool is designed to maintain synchronization between 1-pulse-per-second updates and corresponding LAN data to within 10 milliseconds throughout the 90-minute scenario.

Comparative Studies. While the simulation is in progress, the test PC logs the binary once-per-second messages from the receiver under test. At the conclusion of the scenario, we plot the receiver’s latitude and longitude values and compare them with the actual test drive. We conduct additional comparisons between the test receiver’s speed, heading, and C/N0 values, and the actual values observed during the test drive.

If the test was set up correctly and the equipment operated normally, there should be virtually no difference between the simulated and actual results. Minor discrepancies may be observed due to expected differences in ionospheric and tropospheric modeling, receiver noise figure differences, and ephemeris variations.

Controlled Testing. At this point, inten-tional multipath, obscuration, and power level variations can be deliberately introduced into the GPS simulator scenario. These effects are created to model tunnels, reflections from tall buildings, and limited sky visibility between intersections — conditions found frequently in large cities.

These phenomena provide excellent, controlled test conditions for the dead-reckoning filter within the GPS receiver — the filter should weight WSS measurements more heavily when GPS pseudorange residuals are high, C/N0 values are weak, or the satellite signals are otherwise in doubt.

Although this approach still requires data collection in a vehicle, the duration of the test is reduced to 90 minutes and we can repeatedly change the environmental characteristics of the scenario to model a variety of signal conditions. This method can be used to emulate a city such as Chicago without requiring travel to that location.

Clean Data. At this point, the reader might ask why the data is not collected in a severe urban environment in the first place. Why is it necessary to collect open-sky data and to add artificial multipath, tall buildings, and tunnel effects later?

The answer is that when the GPS simulator generates a scenario based on pre-recorded NMEA motion data, it creates the nominal satellite RF signals that correspond with those times and locations.

Satellite C/N0 values, Doppler values, and code phases are all generated to correspond with that exact vehicle motion profile. If NMEA data were to be collected in a harsh environment such as Chicago, this motion file would be heavily corrupted by the same signal effects mentioned earlier (reflections and obscura). The GPS simulator would not know this, and would simply create the nominal satellite signals corresponding to those corrupted once-per-second locations.

If we connected the navigation system under test to the simulator and LAN playback utility, the GPS signal characteristics would appear to be optimal throughout the route, interfering with the IVNS’s ability to distinguish good satellite signals from poor ones. This in turn would cause the IVNS to de-weight or to ignore the wheel-speed dead-reckoning inputs at times when their contributions to the solution were especially important. In short, these test results would be invalid.

Sample simulation results are shown in Figure 9. The test vehicle in this example was a 2005 Chevrolet Equinox, traveling east toward downtown Detroit. Note that a smaller-diameter spare tire was deliberately installed on the right rear wheel prior to the test drive to assess the ability of the dead-reckoning filter to adapt.

Figure 9 Actual GPS/WSS dead-reckoning data versus simulation playback

During the simulation, we deliberately switched off the GPS satellite signals prior to the Lodge Freeway tunnel and reintroduced them as the vehicle exited approximately one-half a mile (0.8 kilometer) later. In both cases (actual and simulation), the WSS data (including pulses from the right-rear spare tire) helped the driver accurately navigate throughout the tunnel.

Conclusion

Our customer developed an innovative approach to automotive dead reckoning using WSS data to calculate changes in vehicle yaw and tested the technique in many environments including downtown Chicago and Detroit.

This augmentation technique will be an effective method to deliver accurate turn-by-turn driving instructions to customers requesting navigation assistance in difficult environments.

The technique significantly reduced 2D position errors achieved in Chicago compared to unaided GPS, while improving fix density in challenging environments to 100 percent.

We also have assisted with the development of a creative and reliable approach to thoroughly evaluate navigation performance on a variety of vehicles that requires only 90 minutes of local driving. This simulation capability will reduce test time required to certify system performance and will help identify technical problems well before product launch.

Manufacturers

The test drives referenced in this article were conducted using a 12-channel Oncore GPS receiver with WSS dead-reckoning input from Motorola Inc. (www.motorola.com) and a SiRFDrive II GPS receiver with WSS dead reckoning from SiRF Technology, Inc. (www.sirf.com). (Note: SiRF acquired Motorola’s GPS product line on June 1, 2005.) Spirent Communications (www.spirentcom.com manufactured the 12-channel GPS simulator used. Custom development tools manufactured by Danlaw Inc. (www.danlawinc.com) helped retrieve the ABS wheel-speed signals from the vehicle LAN, and reformat and deliver them to both GPS receivers.

CURTIS HAY served as an officer in the United States Air Force for eight years in a variety of GPS-related assignments. He conducted antijam GPS research and development for precision weapons while assigned to the Air Force Research Laboratory, and managed the GPS Accuracy Improvement Initiative for the control segment while assigned to the GPS Joint Program Office. After separating from active duty, he became the lead GPS engineer for OnStar, a division of General Motors Corp. Hay currently serves as a senior systems engineer for Spirent Federal Systems (www.spirentfederal.com a supplier of high-performance GPS test equipment. He can be reached at curtis.hay@spirentfederal.com

"Innovation" is a regular column featuring discussions about recent advances in GPS technology and its applications as well as the fundamentals of GPS positioning. The column is coordinated by RICHARD LANGLEY of the Department of Geodesy and Geomatics Engineering at the University of New Brunswick, who appreciates receiving your comments and topic suggestions. To contact him, see the "Columnists" section on page 6 of this issue.