Monday, September 21, 2020

Dead Reckoning

 U-blox, the Swiss manufacturer of GPS and GNSS receivers that I've used in a number of projects, has models that incorporate both a multi-band receiver and an Inertial Measurement Unit (IMU). The IMU uses accelerometers and gyroscopes to estimate the movement and rotation of the receiver (and whatever it is embedded in) even in the absence of a usable GNSS signal. This is referred to as dead reckoning. The u-blox NEO-M8U module, for example, uses both the ensemble GNSS fix (if it exists) and the IMU measurements to produce a continuous fusion fix that can be maintained even as the GNSS fix is temporarily lost and then reacquired.

How large is the IMU? It's inside the thumbnail-sized M8U module. Here's is an image of the M8U mounted on a tiny red printed circuit board from SparkFun Electronics, which I in turn mounted in a plastic box on a test fixture, along with a multi-band GNSS active antenna.

Note: Click on any image to see a larger version.


How is this possible? The accelerometers and gyroscopes are examples of a MicroElectroMechanical System (MEMS): microscopic electro-mechanical devices with moving parts, manufactured using semiconductor chip fabrication technology.

The IMU isn't perfect. Because the MEMS devices in the module are fairly noisy, the IMU has to do a fair amount of filtering and debouncing of their output. This leads to a noticeable latency of several seconds for the IMU to respond to changes in roll, pitch (road grade), or yaw (vehicle heading). This latency might explain some of the results I present below.

The IMU requires a short period of calibration at start up for it to determine the vehicle reference frame. The automatic calibration requires that the vehicle initially make turns and travel at sufficient speeds, all with adequate GNSS reception. I had to account for this calibration period during my test drives.

I also found that I got the best results when the M8U module was leveled and securely mounted with respect to the vehicle. Ultimately, this led me to mount the module on a gimbaled camera mount (like you might use for a GoPro), and to incorporate a spirit level into the test fixture.

But it's kind of remarkable that it works at all. The controller in the device itself does all of the heavy lifting. My software, running on a laptop or small computer like a Raspberry Pi, merely configures the module using proprietary UBX commands, and then reads the continuous stream of data from the device in the form of standard NMEA sentences and UBX messages. The device generates a position fix once a second, and reports useful information about the fix, like whether GNSS, or the IMU, or (more typically) both, were used in the solution.

Test Fixture

Here is the test fixture mounted on the dashboard of my Subaru WRX during a field test.


The module connects via a USB cable to a laptop running some flavor of Linux/GNU and my open source C-based Hazer software package. The USB cable provides both power to, and two-way communication with, the M8U module. As is typical, the active antenna is powered by the M8U via a voltage bias applied to its coaxial cable.

Here is the computer I used in later test runs: a GPD MicroPC industrial laptop running MATE, an Ubuntu-based version of Linux.


You won't want to do any touch typing on this tiny, almost pocket sized, computer, but it was perfect for this application. (Earlier I used an ancient HP 110 netbook running Mint, another Ubuntu-based Linux. It worked fine too.)

Test Strategy

I had to do some pondering as to how to test this device. The most obviously way was to obscure the antenna with something that would block the signals from the various GNSS satellite constellations. I owned several RF-blocking bags - originally purchased when I was testing cellular data modems - that I could have used for this purpose. I did do some early testing using this technique. But I wanted a more dynamic, organic approach that was in line with the M8U's intended use case in road vehicles.

That's when I remembered I lived in a western suburb of Denver Colorado, just east of the Rocky Mountains. Mountains with lots of highway tunnels. Like the short tunnels built in the 1930s along the United States route 6 road just a few minutes west of where I live. Or the ginormous 2.7km (1.7 mile) Eisenhower and Johnson tunnels built in the 1970s, that carry the Interstate route 70 highway through the Continental Divide about an hour west of my home. This project clearly called for a road trip.

My software can be configured to save the current position fix - latitude, longitude, and altitude, along with a bunch of other data - once a second. The data is saved in human-readable form to a file in Comma Separated Value (CSV) format. This makes it easy to post-process using simple scripts or even Excel. I wrote scripts that converted the CSV data into various files in Keyhole Markup Language (KML), an XML-based data format used to annotate place marks and visualize two- and three-dimensional paths in "earth browsers" like Google Earth.

So far I have done four test drives with my test fixture, through either the US-6 tunnels, or the I-70 tunnels, or (as luck would have it) a route that went through both.

Note: All of the screen shots from Google Earth below follow the usual convention of west to the left, east to the right, north up, and south down. In the U.S. we drive on the right-hand side, so in an east-west road, the upper lanes would be west-bound and the lower lanes would be east-bound. The discussion below assumes that Google Earth is pretty accurate in its mapping of latitude/longitude coordinates, and that they use the same datum, or definition of latitude/longitude, as GPS: WGS84.

Here's is a screen shot of one of my test drives as visualized in Google Earth.

Screen Shot 2020-09-15 at 12.13.25 PM

The red line (a LineString in KML) marks my path, and the yellow push pins (Placemarks in KML) mark the important points like tunnels along the way (different post-processing scripts define the push pins differently). The label on each push pin is effectively elapsed seconds. (It's actually the position fix number, but there is a fix recorded every second.)

The total travel duration for this road trip was about two and a half hours. This route took me west through on I-70 through a short tunnel just east of Idaho Springs, then through the Eisenhower Tunnel, turning around at Silverthorne, then back east on I-70 through it's peer, the Johnson Tunnel, exiting onto US-6 through a series of smaller tunnels, and finally back home. I began each test drive with enough meandering around my neighborhood that the IMU should have been able to calibrate. (Whether more meandering would have yielded better results is an open question.)

Road Trips

Here is a satellite view of the eastern end of the Eisenhower/Johnson tunnels on I-70. The yellow push pins here mark where there were changes in the position fix - a change in the number of satellites in view, or a total loss of GNSS navigation with a fallback onto the IMU. I'm entering the west-bound Eisenhower Tunnel at the top, and later exiting the east-bound Johnson Tunnel at the bottom.

Screen Shot 2020-09-21 at 8.41.08 AM

When I entered the Eisenhower Tunnel at the top going west,  I quickly lost GNSS reception until it was completely gone and I was relying solely on the IMU at the last of the west-bound push pins. Later, on the return leg, when I exited the Johnson Tunnel at the bottom going east, having turned around, it took a few moments for the module to reacquire GNSS signals at the first east-bound push pin, but then it quickly acquired more satellites by the last east-bound push pin.

A similar story is found at the western end of the Eisenhower/Johnson tunnels, exiting the west-bound Eisenhower Tunnel at the top, entering the east-bound Johnson Tunnel at the bottom.

Screen Shot 2020-09-21 at 8.40.40 AM

It took a few moments to reacquire the fix upon exiting the tunnel when heading west. Going back east on my return leg, I lost the GNSS fix quickly upon entering the tunnel. 

I traversed the Eisenhower and Johnson tunnels on three different test drives, each with slightly different results.

Screen Shot 2020-06-22 at 1.19.49 PM

In screen shot above, at the western end of the tunnels, the purely IMU position fix of my west-bound track drifted so far left (down), it crossed the east-bound track and made it look like I was in the wrong tunnel (which is impossible). When the module reacquired GNSS, it quickly corrected the fix to put me in the correct lane.

Screen Shot 2020-09-03 at 12.54.01 PM

In the screen shot above, its hard to say whether the IMU position fix drifted since I don't know exactly the path of the two tunnels through the mountain range, but it seems likely. (There is a pronounced bend in the tunnels at the eastern end, which you can see from the orientation of the eastern entrance relative to the western entrance.)

Screen Shot 2020-09-15 at 12.15.02 PM

Once again, there is an obvious drift in the screen shot above that makes it look like the tunnels merge at the western end (they do not). It's corrected as soon as I get near enough to the tunnel mouth that GNSS is reacquired.

There were even more radical corrections on the far shorter tunnels along US-6. (Updated 2020-10-03) Note, however, that both of these tests shown below were performed before I came up with the more stable test fixture on which I mounted the GNSS module; results after that change were noticeably better. This illustrates the importance of having a secure mounting. (End Update)

Screen Shot 2020-06-15 at 1.44.39 PM

On the western end of the tunnel above, you can see the sudden and abrupt correction made as I exited the tunnel going west-bound. It looks like I was smoking the tires on the WRX as I made a pair of bootlegger turns.

Screen Shot 2020-09-15 at 12.19.16 PM

Above, on another tunnel along different section of US-6 going east bound, you can see a similar sudden correction.

But some of the test runs in some of the tunnels looked nearly perfect.

Screen Shot 2020-09-03 at 12.52.54 PM

This tunnel is far shorter than, and not as deeply buried as, the Eisenhower/Johnson tunnels. Going back and examining the original CSV file, I see in this particular case that a GNSS fix was maintained for about half way through the west-bound tunnel, and for about a third of the way through the east-bound tunnel. In both directions, the position fix was then made solely using the IMU until I exited the tunnel.

Parking Garage

Another idea I had to test the IMU was by driving around inside a four-level parking garage at a shopping mall just a few minutes away from my home. This is what that path looked like after I converted the CSV into KML and imported it into Google Earth.

Screen Shot 2020-09-17 at 10.14.11 AM

Even driving around in the lowest two levels, then parking at the lowest, darkest, level of the garage, where no direct sunlight was visible, I was able to get a GNSS fix with at least six satellites (the minimum necessary is four if you want to also solve for altitude). The M8U used both the GNSS and the IMU for a position fix, but in this case the IMU was continuously able to be checked and if necessary corrected using GNSS.

Screen Shot 2020-09-17 at 10.34.31 AM

Looking at a close up, tilted, view of the parking garage in Google Earth, the path deviates enough that it looks like my WRX flew out of the parking deck and (somehow) back in again in a couple of places. This could be a lack of precision in the position fix of the M8U (GNSS isn't perfect either), an error on the part of Google Earth, or maybe I should audition for the next Fast and Furious movie. If I were to fly out of the parking deck and back in again, the Subaru WRX would be the car I'd use to do it.

Since the iterative least-squares algorithms typically used by GNSS receivers to compute the overdetermined solution is more accurate the more satellites it uses, and in open sky the M8U is able to use many satellites from several constellations, it is possible that in some circumstances in the garage the IMU could actually be more accurate than the GNSS when only a very few satellites are visible and they are close enough in their orbits that Dilution of Precision is an issue.


The integrated Inertial Measurement Unit in the NEO-M8U added to the accuracy of the position fix when GNSS signals were completely unavailable, but only for a short amount of time. The longer the device went without GNSS, the more the IMU position fix drifted.

The IMU might be quite useful for its intended application with typical road vehicles. I wouldn't use it to navigate in any coal mines. But it works fine over short periods of no satellite reception. And it's remarkable that it works at all.