Accurately interpreting satellite data is half the job
By JON PERSON
Jon is the author of the GPS.NET Global Positioning SDK component and has consulted for military companies and the Forest Service on GPS solutions. He can be reached at firstname.lastname@example.org.
In his article "GPS Programming & .NET" (DDJ, June 2004), Johan Franson examined several fundamental GPS topics, including working with serial ports, detecting data errors, and calculating the distance and bearing with Universal Transverse Mercator (UTM) coordinates. Still, there are more questions that need to be addressed, especially for developers who want to write applications for the real world. For instance, what do GPS applications need to be good enough at to pilot airplanes? And how does the process of interpreting GPS data actually work? In this article, I cover both of these topics and present techniques for writing commercial-grade GPS applications that work with most GPS devices available today.
The key to writing GPS-enabled software is being able to interpret raw GPS data. Fortunately, the National Marine Electronics Association (http://www.nmea.org/) has simplified the task with standards that are adhered to by most GPS devices. NMEA data is sent as comma-delimited "sentences," which contain information based on the first word of the sentence. There are more than 50 kinds of sentences, yet an interpreter only needs to handle a few to get the job done. The most common NMEA sentence of all (described by Johan in Table 2 of his article) is the "Recommended Minimum" sentence, which begins with "$GPRMC." For example:
This single sentence contains nearly everything GPS applications needlatitude, longitude, speed, bearing, satellite-derived time, fix status, and magnetic variation.
The Core of an Interpreter
The first step in interpreting raw NMEA data is to build or otherwise utilize an interpreter. To give you a headstart, I present source code from my GPS.NET Global Positioning SDK component (http://www.gpsdotnet.com/). The code is stripped of features such as multithreading and error handling for brevity. The interpreter does two things: separates each sentence into its individual words and examines the first word to figure out what information is available to extract. Listing One is a function that's the start of the interpreter class.
The next step is to perform actual extraction of information, starting with latitude and longitude. Latitude and longitude are stored in the form "DDD¡MM'SS.S," where D represents hours (also called "degrees"), M represents minutes, and S represents seconds. Coordinates can be displayed in shorthand, such as DD¡MM.M' or even DD¡. The fourth word in the sentence, 3939.7, shows the current latitude as hours and minutes (39¡39.7'), except the numbers are squished together. The first two characters (39) represent hours and the remainder of the word (39.7) represents minutes. Longitude is structured the same way, except that the first three characters represent hours (105¡06.6'). Words 5 and 7 indicate the "hemisphere," where N means North, W means West, and so on. The hemisphere is appended to the end of the numeric portion to make a complete measurement.
NMEA interpreters are easier to work with when they are event driven because data arrives in no particular order. An event-driven class gives the interpreter the most flexibility and responsiveness to an application. Consequently, I design the interpreter to report information using events. The first event, PositionReceived, will be raised whenever the current latitude and longitude are received. Listing Two expands the interpreter to report the current position, so that it then can report the current latitude and longitude.
One thing to watch out for here is that some GPS devices report blank values when no information is known. Therefore, it's a good idea to test each word for a value before parsing. If you need to type the degree symbol (¡), hold down the Alt key and type "0176" on the numeric keypad.
Taking Out the Garbage
Each sentence is accompanied by a checksum used to detect any errors in NMEA data. A checksum is calculated as the XOR of bytes between (but not including) the dollar sign ($) and asterisk (*). This checksum is then compared with the checksum from the sentence. If the checksums do not match, the sentence is typically discarded. This is okay to do because the GPS devices tend to repeat the same information every few seconds. I modified Johan's ValidateChecksum method slightly to divide the checksum calculation and comparison procedures, but the technique is still the same. With the ability to compare checksums, the interpreter is able to throw out any sentence with an invalid checksum. Listing Three expands the interpreter to detect errors and parse only error-free NMEA data.
Wireless Atomic Time
Time is the cornerstone of GPS technology because distances are measured at the speed of light. Each GPS satellite contains four atomic clocks that it uses to time its radio transmissions within a few nanoseconds. One fascinating feature is that with just a few lines of code, these atomic clocks can be used to synchronize a computer's clock with millisecond accuracy. The second word of the $GPRMC sentence040302.663contains satellite-derived time in a compressed format. The first two characters represent hours, the next two represent minutes, the next two represent seconds, and everything after the decimal place is milliseconds. So, the time is 4:03:02.663 am. However, satellites report time in universal time (GMT+0), so the time must to be adjusted to the local time zone. Listing Four (available electronically) adds support for satellite-derived time and uses the DateTime.ToLocalTime method to convert satellite time to the local time zone.
Direction and Speed Alerts
GPS devices analyze your position over time to calculate speed and bearing. The $GPRMC sentence previously presented also includes these readings. Speed is always reported in knots and bearing is reported as an "azimuth," a measurement around the horizon measured clockwise from 0¡ to 360¡ where 0¡ represents north, 90¡ means east, and so on. A little math is applied to convert knots into miles per hour. The power of GPS is again demonstrated with one line of code in Listing Five (available electronically) that figures out if a car is over the speed limit.
Are We Fixed Yet?
The $GPRMC sentence also includes a value that indicates whether a "fix" has been obtained. A fix is possible when the signal strength of at least three satellites is strong enough to be involved in calculating your location. If at least four satellites are involved, altitude also becomes known. The third word of the $GPRMC sentence is one of two letters: "A" for "active," where a fix is obtained, or "V" for "invalid" where no fix is present. Listing Six (available electronically) includes code to examine this character and report on the fix status.
As you can see, a lot of information is packed into a single NMEA sentence. Now that the $GPRMC sentence has been fully interpreted, the interpreter can be expanded to support a second sentence$GPGSV. This sentence describes the configuration of satellites overhead, in real time.
Real-Time Satellite Tracking
Knowing the location of satellites is important when determining how precise readings are and how stable a GPS fix is. I address GPS precision later in this article. Here, I focus on interpreting satellite location and signal strength.
There are 24 operational satellites in orbit. Satellites are spaced in orbit so that at any time, a minimum of six satellites will be in view to users anywhere in the world. Satellites are constantly in motion, which is good because it prevents the existence of "blind spots" in the world with little or no satellite visibility. Just like finding stars in the sky, satellite locations are described as the combination of an azimuth and an elevation. Again, azimuth measures a direction around the horizon. Elevation measures a degree value up from the horizon between 0¡ and 90¡, where 0¡ represents the horizon and 90¡ represents "zenith," directly overhead. So, if the device says a satellite's azimuth is 45¡ and its elevation is 45¡, the satellite is located halfway up from the horizon towards the northeast. In addition to location, devices report each satellite's Pseudo-Random Code (PRC), which is a number used to uniquely identify one satellite from another.
Here's an example of a $GPGSV sentence:
Each sentence contains up to four blocks of satellite information, comprised of four words. For example, the first block is "24,82,023,40," the second block is "05,62,285,32," and so on. The first word of each block gives the satellite's PRC. The second word gives each satellite's elevation, followed by azimuth and signal strength. If this satellite information were to be shown graphically, it looks like Figure 1.
Perhaps the most important number in this sentence is the signal-to-noise ratio (SNR). This number indicates how strongly a satellite's radio signal is being received. Remember, satellites transmit signals at the same strength but things, such as trees and walls, can obscure a signal beyond recognition. Typical SNR values are between 0 and 50, where 50 means an excellent signal. (SNR can be as high as 99, but I've never seen readings above 50 even in wide open sky.) In Figure 1, the green satellites indicate a strong signal, whereas the yellow satellite signifies a moderate signal. Satellite #1's signal is completely obscured. Listing Seven (available electronically) shows the interpreter after it is expanded to read satellite info.
A World-Class Interpreter
International readers may have spotted a subtle problem early on that was not handled in the source code I've presentednumbers were being reported in the numeric format used in the United States! Countries such as Belgium and Switzerland, which use different formats for numbers, require adjustments to the interpreter in order to work at all. Fortunately, the .NET Framework includes built-in support for converting numbers between different cultures, so the changes to the interpreter required are straightforward. In the interpreter, the only fractional values are speed and bearing, so two changes are necessary. The NmeaCultureInfo variable represents the culture used for numbers within NMEA sentences. The Double.Parse method is then used with this variable to convert speed into the machine's local culture. Listing Eight (available electronically) shows the completed interpreter, ready for use internationally.
Once you understand how an NMEA interpreter extracts words from sentences, you can harness the power of satellites to determine your location, synchronize your computer clock, find your direction, watch your speed, and point to a satellite in the sky on a cloudy day. The interpreter I present here also works with the .NET Compact Framework without any modifications. If sentences were also stored in a file, the interpreter can be used to play back an entire road trip. These are all great features, especially considering the small size of the class, but is this interpreter ready to drive your car and pilot an airplane? Not quite yet. There is one important topic remaining, which is required to make GPS applications safe for the real worldprecision.
Although the interpreter I've presented now works with handheld devices and supports international developers, it still isn't necessarily suitable for commercial use because it does not monitor precision. Without precision, applications could end up making unintelligent business decisions such as accidentally telling drivers to turn left into an alley, or worse. Clearly, the issue of "precision" must be addressed if GPS applications are to be smart enough for in-car navigation and reliable enough to autopilot an airplane.
GPS devices calculate your position using a technique called "3D multilateration," which is the process of determining where several spheres intersect. In the case of GPS, each sphere has a satellite at its center; the radius of the sphere is the calculated distance from the satellite to the GPS device. Ideally, these spheres would intersect at exactly one point, causing there to be only one possible solution to the current location, but in reality, the intersection forms more of an oddly shaped area. The device could be located within any point in the area, forcing devices to choose from many possibilities. Figure 2 shows such an area created from three satellites (using the $GPGSV sentence). The current location could be any point within the gray-colored area. Precision is said to be "diluted" by this area, which leads to this article's second focus: dilution of precision. The monitoring and control of dilution of precision (DOP) is the key to writing high-precision applications.
DOP values are reported in three types of measurements: horizontal, vertical, and mean. Horizontal DOP (HDOP) measures DOP as it relates to latitude and longitude. Vertical DOP (VDOP) measures precision as it relates to altitude. Mean DOP, also known as Position DOP (PDOP), gives an overall rating of precision for latitude, longitude, and altitude. Each DOP value is reported as a number between 1 and 50, where 50 represents very poor precision and 1 means ideal accuracy. Table 1 lists what I believe to be an accurate breakdown of DOP values.
Looking again at Figure 2, three satellites created a large area of possible solutions. This situation could be improved by two factors: adding more satellites to the fix, and using satellites evenly distributed throughout the sky. What would Figure 2 look like if the situation was improved like this? Figure 3 shows Figure 2 after three more evenly distributed satellites have been added.As a result, the DOP has been reduced.
Advanced GPS application developers could know if positional readings are precise enough to use just by looking at one $GPGSA sentence. Again, the best DOP ratings occur when there are several satellites involved in a fix and the satellites are evenly distributed throughout the sky and at separate elevationshitting the GPS device from all angles, so to speak.
Determining Precision Needs
The next step is to determine the actual precision needs of an application. As a general rule, an HDOP value of 6 or less is recommended for any application that makes suggestions to the user based on the current location. For example, in-car navigation programs that tell the user to "turn left now" should ignore positional measurements when HDOP is greater than 6.
But is 6 really good enough? How can you figure out which HDOP values to use for your applications? To answer these kinds of questions, use this simple formula:
Accuracy of GPS Device * DOP =
Maximum Allowable Error
This formula uses DOP as a factor of error that, when combined with the accuracy of the GPS device being used, yields the maximum error allowed by a level of DOP in the form of a specific, measurable distance. Another general rule is that typical consumer GPS devices are capable of between 5-7 meters of accuracy without enhancements (such as DGPS or WAAS), or an average of 6 meters. Using the in-car navigation HDOP of 6 and a typical GPS device, the maximum error allowed is 6m * 6 = 36 meters, or 118 feet. Given that a downtown city block is roughly 475 feet square, the maximum allowable error is about a quarter of a city block. This is precise enough to make sure that drivers turn at the correct road. On the other hand, an HDOP of 12 results in an allowable error of half a city block (237 feet), which could cause drivers to turn down an alley accidentally. So, using the formula, it is possible to use an HDOP greater than 6 for in-car navigation, but not by much.
The trick to using this formula is researching real-world distances, especially the smallest important distances. To demonstrate, take a look at golf. Does golf require more precision than in-car navigation? A golf program needs to tell users which golf club to use to make the best shot. Some research into important golf distances finds that for most players, there is a regular distance interval between clubs of about 10-15 yards. Therefore, a golf program needs no more than 10 yards (9.1 meters) of allowable error to consistently suggest the right club. When 9.1 meters is put into the formula as Maximum Allowable Error, the maximum HDOP comes out to 3. So, golfing applications do indeed require about twice the precision as in-car navigation systems.
Why not skip the formulas and always enforce an HDOP of 1? This looks like a reasonable practice, but greater precision requires greater satellite visibility. An in-car navigation system will probably not get an HDOP of 1 (or even 3) downtown because signals are being obscured by buildings. If the enforced HDOP is too small, the application throws out too many positional readings and just sits there while drivers lose patience. Golfing applications, on the other hand, can realistically enforce a small HDOP because they operate in more open sky. The golfer's PDA is likely to have enough sky to pick up several evenly distributed satellites, unless their ball is in the middle of the woods, in which case they're on their own.
To summarize, successful GPS software developers use the formula to determine the largest possible DOP number. This ensures that the application minimizes the most problems due to inaccuracy while at the same time allowing the application to function in the poorest possible satellite visibility conditions. This practice maximizes the value and versatility of any GPS application.
Once the precision needs of a GPS application have been determined, it's time to find out what source code is necessary to extract and enforce maximum DOP values. All DOP measurements are packaged into the $GPGSA sentence every few seconds. Here is a sample of a $GPGSA sentence:
The last three words of this sentence are 2.3, 1.2, and 2.0, representing mean, horizontal, and vertical DOP, respectively. This sentence represents a high- precision environment (suitable enough for both golfing and driving). Using Listing Eight (available electronically), a method called ParseGPGSA is added, which extracts DOP values and reports them via three eventsHDOPReceived, VDOPReceived, and PDOPReceived (see Listing Nine, available electronically).
Enforcing DOP values is the easiest part of the programming process because enforcing precision is a matter of ignoring positional measurements until HDOP is at (or below) the maximum. This can be done in a single if statement. To demonstrate this, I've written a small app (Listing Ten, available electronically) that uses the NMEA interpreter to enforce high precision.
Controlling dilution of precision is the key to writing commercial-grade GPS applications. A basic formula can be applied to determine the maximum allowable error for a particular application. The maximum allowable error should be the greatest possible value that minimizes accuracy problems while maximizing operational conditions.
While this article covered programming techniques for controlling precision, there are several other technologies that I did not cover in detail. For example, when satellite radio signals are transmitted, they are distorted by the troposphere and especially the ionosphere. In fact, satellites very low on the horizon are not good for getting a fix because the signals travel through so much of the troposphere. Precision errors can be compounded by slight inaccuracies in each satellite's ephemeris (its actual position in orbit), its clocks, and something called "multipath" where radio signals that bounce off objects are detected along with the original signal, confusing the device. Technologies such as DGPS, Internet DGPS, SisNet, WAAS, and EGNOS attempt to minimize most of these precision errors by providing corrective data that, when integrated with a device's own data, can improve accuracy down to as little as 1 meter in good conditions. A lot of consumer devices are now being shipped with built-in support for WAAS, but WAAS is still considered experimental and frequently broadcasts that it is in test mode.
There are some applications that require so much precision that they escape the scope of this article and enter the realm of expensive dual-channel receivers and custom ground stations. Yet, GPS is successfully landing planes while you read this, and it is only a matter of time before precision down to a centimeter becomes cost-effective for industry. When that happens, I believe it will cause a critical mass that opens the door to some truly amazing and helpful thingsautomated construction machines, coupons on your cell phone for that restaurant across the street, traffic-control systems that actually take the wheel...and self-guiding golf balls.
'******************************************************* '** The core of an NMEA interpreter '******************************************************* Public Class NmeaInterpreter ' Processes information from the GPS receiver Public Function Parse(ByVal sentence As String) As Boolean ' Divide the sentence into words Dim Words() As String = GetWords(sentence) ' Look at the first word to decide where to go next Select Case Words(0) Case "$GPRMC" ' A "Recommended Minimum" sentence was found! ' Indicate that the sentence was recognized Return True Case Else ' Indicate that the sentence was not recognized Return False End Select End Function ' Divides a sentence into individual words Public Function GetWords(ByVal sentence As String) As String() Return sentence.Split(","c) End Function End ClassBack to article
'******************************************************* '** Extracting information from a sentence '******************************************************* Public Class NmeaInterpreter ' Raised when the current location has changed Public Event PositionReceived(ByVal latitude As String, ByVal longitude As String) ' Processes information from the GPS receiver Public Function Parse(ByVal sentence As String) As Boolean ' Look at the first word to decide where to go next Select Case GetWords(sentence)(0) Case "$GPRMC" ' A "Recommended Minimum" sentence was found! Return ParseGPRMC(sentence) Case Else ' Indicate that the sentence was not recognized Return False End Select End Function ' Divides a sentence into individual words Public Function GetWords(ByVal sentence As String) As String() Return sentence.Split(","c) End Function ' Interprets a $GPRMC message Public Function ParseGPRMC(ByVal sentence As String) As Boolean ' Divide the sentence into words Dim Words() As String = GetWords(sentence) ' Do we have enough values to describe our location? If Words(3) <> "" And Words(4) <> "" And Words(5) <> "" And Words(6) <> "" Then ' Yes. Extract latitude and longitude Dim Latitude As String = Words(3).Substring(0, 2) & "¡" ' Append hours Latitude = Latitude & Words(3).Substring(2) & """" ' Append minutes Latitude = Latitude & Words(4) ' Append the hemisphere Dim Longitude As String = Words(5).Substring(0, 3) & "¡" ' Append hours Longitude = Longitude & Words(5).Substring(3) & """" ' Append minutes Longitude = Longitude & Words(6) ' Append the hemisphere ' Notify the calling application of the change RaiseEvent PositionReceived(Latitude, Longitude) End If ' Indicate that the sentence was recognized Return True End Function End ClassBack to article
'******************************************************* '** Detecting and handling NMEA errors '******************************************************* Public Class NmeaInterpreter ' Raised when the current location has changed Public Event PositionReceived(ByVal latitude As String, ByVal longitude As String) ' Processes information from the GPS receiver Public Function Parse(ByVal sentence As String) As Boolean ' Discard sentence if its checksum does not match calculated checksum If Not IsValid(sentence) Then Return False ' Look at the first word to decide where to go next Select Case GetWords(sentence)(0) Case "$GPRMC" ' A "Recommended Minimum" sentence was found! Return ParseGPRMC(sentence) Case Else ' Indicate that the sentence was not recognized Return False End Select End Function ' Divides a sentence into individual words Public Function GetWords(ByVal sentence As String) As String() Return sentence.Split(","c) End Function ' Interprets a $GPRMC message Public Function ParseGPRMC(ByVal sentence As String) As Boolean ' Divide the sentence into words Dim Words() As String = GetWords(sentence) ' Do we have enough values to describe our location? If Words(3) <> "" And Words(4) <> "" And Words(5) <> "" And Words(6) <> "" Then ' Yes. Extract latitude and longitude Dim Latitude As String = Words(3).Substring(0, 2) & "¡" ' Append hours Latitude = Latitude & Words(3).Substring(2) & """" ' Append minutes Latitude = Latitude & Words(4) ' Append the hemisphere Dim Longitude As String = Words(5).Substring(0, 3) & "¡" ' Append hours Longitude = Longitude & Words(5).Substring(3) & """" ' Append minutes Longitude = Longitude & Words(6) ' Append the hemisphere ' Notify the calling application of the change RaiseEvent PositionReceived(Latitude, Longitude) End If ' Indicate that the sentence was recognized Return True End Function ' Returns True if a sentence's checksum matches the calculated checksum Public Function IsValid(ByVal sentence As String) As Boolean ' Compare the characters after the asterisk to the calculation Return sentence.Substring(sentence.IndexOf("*") + 1) = GetChecksum(sentence) End Function ' Calculates the checksum for a sentence Public Function GetChecksum(ByVal sentence As String) As String ' Loop through all chars to get a checksum Dim Character As Char Dim Checksum As Integer For Each Character In sentence Select Case Character Case "$"c ' Ignore the dollar sign Case "*"c ' Stop processing before the asterisk Exit For Case Else ' Is this the first value for the checksum? If Checksum = 0 Then ' Yes. Set the checksum to the value Checksum = Convert.ToByte(Character) Else ' No. XOR the checksum with this character's value Checksum = Checksum Xor Convert.ToByte(Character) End If End Select Next ' Return the checksum formatted as a two-character hexadecimal Return Checksum.ToString("X2") End Function End ClassBack to article