by Chris Halsall
For most of our history, navigating with accuracy has been difficult. The various techniques to determine where one might be have delivered approximate results at best. The problem is that the question "Where am I?" is inherently relative to "Compared to what?" -- and usually there's not much to compare against.
Imagine yourself on a small sailboat -- or a large oil tanker -- in a zero visibility fog. Quiz: What can you measure to determine where you are? Magnetic north has been available to mariners for almost as long as we've been a seafaring species. "Down" is pretty easy to determine as well. But both of these simply give us our orientation, not our position.
It turns out there's no way, on a mobile platform, to determine one's position without making observations of external and known objects; the current time must also be known, with some precision. Early mariners learned to observe celestial objects with a sextant to determine their position; the art of accurate time-keeping was largely driven by the urgent needs of this application.
However, celestial navigation doesn't help us much in the fog. To help in such situations, modern solutions have used radio waves for triangulation. Loran-C is a system used for marine navigation, with coverage in US and Canadian waters as well as the Bering Sea. Inland, pilots use the "very high frequency omnidirectional range" (VOR) system -- a network of ground stations on which the airway system is based.
But such solutions continue to have limited coverage and accuracy, and they rely on infrastructure being deployed near where position determination is desired. Where do you put your navigational beacons when you want coverage everywhere? The only spot that makes sense is in orbit, and two systems designed for this purpose have been in use for many years: the US military funded Navstar Global Positioning System (GPS) and the Soviet GLONASS.
Three generations of GPS receivers, with a Palm for size comparison.
The Navstar GPS is the better known of the two because of its use in commercial and civilian applications, although such use was not its original goal. GPS was designed for military and approved government uses only, but this changed after the 1983 Korean Air Lines 007 disaster caused by Cold War tensions and poor navigation. GLONASS can also be used for civilian position determination, although its use is less frequent.
Launched and maintained by the 50th Space Wing, the GPS system consists of three segments: space, control, and user. The Space Segment is made up by 24 satellites in almost perfectly circular, 12-hour orbits, arranged in six orbital planes. The Control Segment is five ground-based monitoring stations located around the world and the Master Control Station (MCS), based at Falcon Air Force Base in Colorado Springs, CO, which maintains and controls the Space Segment.
The User Segment consists of devices that can process signals received from four or more satellites' transmissions simultaneously to calculate the receiver's location (to as close as 16 meters in 3D; 9 meters in 2D) and the current time (to microsecond accuracy). From repeated observations, current speed can also be derived. It's worth noting that no transmission takes place from the User Segment -- the receivers do not reveal themselves, and there is no limit to the number of receivers being used.
How GPS works
Each satellite transmits pseudo random noise spread spectrum signals on two different frequencies, L1 at 1575.42 MHz and L2 at 1227.6 MHz. L1 carries the coarse/acquisition code (CA-code) and a precision code (P-code). L2 usually only carries P-code, but could carry CA-code as well. This pseudo random noise can then be modulated, allowing multiple transmitters to use the same frequency.
The CA-code is a short sequence that repeats itself every millisecond, is different for every satellite, and is known and open to anyone who wishes to receive and decode it. The P-code, on the other hand, repeats every 267 days, and each satellite transmits a different seven-day segment before being reset. The P-code requires a cryptological key to decode, which is limited to US Department of Defense (DoD) and other "approved users."
Each satellite transmits a NAV message superimposed on both the CA- and P-codes. This contains GPS time, its ephemeris (orbit characteristics), almanac information for all the satellites in the GPS constellation, satellite health status, ionospheric delay estimates, and CA- to P-code hand-over information for approved users.
Position determination works by simple triangulation between a receiver and three or more satellites visible that moment. The arrangement of the satellites' orbits is such that at least five, and usually several more, are visible in the sky from any location on earth -- ignoring any local obstructions like hills or buildings. Those in northern or southern locations enjoy greater satellite coverage.
Drivers, boaters and pilots can know where they are, and where they've been.
The receivers start with zero knowledge -- they don't know where on the planet they are, or what time it is. Because of this, a good signal from three satellites is required to determine current time, latitude, and longitude, and a fourth to also determine altitude. Any additional signals increase accuracy. Most modern GPS receivers are capable of receiving on 12 separate channels or, basically, from every "bird" that might be visible in the sky.
P-code enabled receivers are able to benefit from having two different frequencies to lock onto. This is used to measure the effect the ionosphere is having on the signals and helps improve accuracy even further. Since the CA-code is only carried on one frequency, such measurements are not possible, so an estimate provided by the satellite is used. Triangulation based on the CA-code is known as the Standard Positioning Service (SPS), with the P-code-based system being called the Precise Positioning Service (PPS).
It's important to point out that GPS is a line-of-sight technology -- the receiver has to have a clear view of the satellites it is using to calculate its position. Thus, reception indoors is impossible. Quality of position determination can also be affected by hills, buildings, and trees.
GPS accuracy can be a tricky thing to discuss because there are so many different ways of expressing it. A common measure is Spherical Error Probable (SEP), which expresses 3D accuracy expected 50% of the time. The related Circular Error Probable (CEP) expresses accuracy for latitude and longitude only. Other accuracy measures include root mean square (RMS), twice distance RMS(2dRMS), and horizontal 95 percent accuracy (R95). RMS can represent one, two or three dimensions.
Using both P-code frequencies, PPS position accuracy has been published by the US military as being able to provide 9 meters CEP, 16 meters SEP, or 22 meters R95. UTC time is accurate to 200 nanoseconds. This is quite impressive accuracy, particularly considering that the position can be calculated after only a few seconds of observation from a complete "cold start." Methods for improving accuracy down to the meter level have also been proposed.
For non-privileged SPS users, the accuracy is about half as good. Before May 1st, 2000, SPS accuracy was significantly worse (approximately 76 meters SEP) because of something called selective availability (SA). SA is an operational mode of GPS, which introduces an intentional degrading of the CA-code signal. While now disabled, users should be aware it can be reactivated in (wide) areas during times of hostilities.
Better accuracy -- hacking the system
SPS still has a disturbing random wander, although it's certainly better than with SA enabled.
In a classic case of one branch of an organization directly working against another, the US Coast Guard installed the Maritime Differential GPS (DGPS) service. This works by having GPS receivers placed at fixed, known locations, and having them transmit information about each satellite's error.
DGPS-equipped receivers, when getting good signals from both the GPS satellites and one or more nearby DGPS stations, can resolve their position with an accuracy of 10 meters (R95) or better, depending on how close the receiver is to the DGPS station.
DGPS service is now available along the coastlines of the US, Canada, several European countries, and Australia. Inland DGPS deployment is underway (known as the Nationwide DGPS Service in the US), with the intent of allowing DGPS to be used for air traffic. Currently only VOR-type radio navigation is legal for Instrument Flight Rule (IFR), where the pilot needs to be able to fly (and land) in zero visibility situations.
Another option, currently being offered by companies like OmniSTAR, is DGPS information transmitted by way of commercial, geostationary satellites. Such systems require the same type of known-location GPS receivers scattered around the ground, but use them in a network fashion. Known as "wide-area DGPS," error reports from multiple stations surrounding the receiver can be used for even better accuracy.
Groove to the waves!
But what if you need to know where you are to an extreme accuracy -- like, two centimeters or so?? DGPS will never provide such accuracy, but there's still a way to use the GPS signals to do so. Called Real-Time Kinematic (RTK) GPS, two or more receivers are used, one of which remains stationary while the others can move a few tens of kilometers around to collect position measurements.
Instead of relying on the information encoded on the L1 or L2 frequencies, the carrier waves of one or both are directly monitored. Before any measurements can be made, the mobile rover receiver(s) must first be synchronized with the stationary base station, which can only be done with all units in close proximity.
During use of RTK, all cooperating receivers closely monitor the carrier waves from each satellite being used for the position solution. Whenever a position measurement is to be made, the rover station must also be receiving a good radio signal from the base station. This lets the rover station calculate the difference between the carrier phases it is observing vs. that of the base station.
While much more expensive than regular GPS or even DGPS receivers, RTK GPS offers unparalleled accuracy. It does have some limitations, however, the biggest being the permanent loss of position knowledge if the lock on the carrier signals is lost. Post-processing can often be used to resolve the errors, but for real-time applications, returning to the base station is the only option.
It's perhaps worth noting that RTK GPS receivers are limited, by US and Canadian export laws, to providing data only if they are traveling at 514 meters per second or less. So doing high resolution surveys with cruise missiles as the instrument platform is out.
Consumer grade kit
One of the main reasons for the decision to turn off selective availability was to foster continued commercial development of GPS solutions. GPS units are now available in several forms in the retail channel, with suggested retail prices staring at approximately $100 USD and climbing quickly from there.
Expect to pay between two to three times as much for a DGPS-capable setup. Most GPS receivers can take data from a DGPS beacon receiver, or else they have such receivers built in. Forget about using RTK for any but the most serious applications -- prices start in the many tens of thousands.
Most gear can communicate with a computer by way of the NMEA format, which is presented as a series of one-line sentences in a 4800 baud serial stream. Some units allow faster baud rates, and extension messages (such as the Garmin sentences) exist. Regardless, update rates tend to be 1 Hz or slower.
GPS receivers are also becoming available in form factors designed for use with PDAs. Receivers are available for Palm Pilots, Handsprings, and several Windows CE devices. PCMCIA versions have been available for some time, allowing laptops and PCMCIA-equipped handhelds to keep track of their location.
A great deal of excitement currently exists around the idea of GPS receivers being used with embedded and pervasive computing. As with all things electronic, receivers continue to get smaller and cheaper. It is expected that by 2005, most vehicles, mobile computers, and wireless communication devices will have GPS receivers built in.
Already the OnStar GPS navigation system is being used to entice buyers to higher end vehicles, while shipping and trucking companies have been using GPS for inventory management for some time. GPS receivers have become the preferred means of navigation for both land and marine travel.
The successes of the commercial applications of GPS have led to scores of applications -- it's now practically impossible to get lost if properly equipped. There are plans to provide a second civilian GPS signal on new navigation satellites by 2003, with a third by 2005, which would continue to improve the accuracy provided. Sub-meter resolution from GPS receivers for free consumer use may be something we see sooner rather than later.
Discuss this article in the O'Reilly Network Wireless Forum.
Return to the Wireless DevCenter.