How does GPS Work?

During my previous series “What’s the point of high school math?”, I talked about the need for GPS-denied navigation for self driving cars, but I never discussed how Global Positioning Systems, or GPS, work in the first place. This article will rectify that.

How it works

GPS relies on multiple satellites circling the Earth. These groups are called constellations, and while they do not all need to be in the same orbit, they do need to be close enough to the ground for ground stations to transmit information to them, and for GPS receivers to get measurements.

Getting a GPS measurement requires at least four unique satellites to perform trilateration, or the process of determining where a receiver is located in relation to the satellites. Each satellite contains a highly accurate clock called an atomic clock, which measures the resonant frequency of atoms and thus (theoretically) should never drift.

The satellite is following a certain orbit that is constrained by the traditional Keplerian elements, which means that if the satellite knows the current time and the time and location of launch, it should be able to tell exactly where it is. In addition, ground control stations on Earth are continuously monitoring the satellites and will tell the satellite to update its position estimate if it becomes inaccurate. The satellite will then broadcast in all directions a message packet that says its current location and time.

When this message is received on Earth, the receiver can calculate how far they are using the message packet and the speed of light:

Distance = speed of light * (current time - time in message)

However, the satellite broadcasts in all directions, and there is always error involved when using sensors over such great differences, so we cannot say exactly which direction the measurement came from. Instead, we have a 3D sphere of possible locations, with the true satellite position somewhere inside it. In two dimensions, that would look like this:

It is amazing to me that we have this technology, but unfortunately it does not help us figure out where we are on Earth. So, we repeat the process with another satellite. This will also give us a sphere of possible locations, but now our position is narrowed down: in order to have received both messages, we can only be in the area where our first satellite’s sphere intersects with the second’s, like so:

Repeating a third time will narrow down our location in 2D space, and the fourth satellite will constrain us to a single 3D point:

Now we know where we are! In theory, this should give us a perfect location estimate every time, but anyone who has used Google Maps for walking knows that it is often off by a few feet. There are a few aspects that can cause issues - first, the makeup of the ionosphere can cause the clocks to drift over time. This might not seem like a big issue, but the speed of light is 983,571,056 feet per second, so a drift of one nanosecond (1 times 10 to the -9) can result in an error of about a foot. The clocks can be synchronized with a larger, more accurate clock on the ground, but that requires communication with the ground station. Quantum clocks might be able to solve that problem, but it will likely be years before it is feasible in terms of cost, weight, and actual technology development. Another source of error could be large structures such as buildings or mountains - if the signal bounces off of them before hitting the receiver, the wrong distance will be calculated. In addition, all sensors contain noise, especially when receiving messages from so far away. This leads to uncertainty in the measurement calculations, which could lead to either a bad measurement or the need for more satellites to converge on a possible answer. This uncertainty, combined with the fact that GPS measurements are easy to spoof (imitate) or jam (block from receivers), means that location estimation without GPS is necessary for applications that require very accurate position estimates, such as self-driving cars, as well as a backup for all current GPS-based systems in the event a political or military event renders them unusable.

Types of Constellations

The original GPS constellation is NAVSTAR, the 31 satellites launched by the United States Department of Defense for military use and later opened to civilians. It provides world coverage, and it is reportedly accurate to 7 meters. Japan’s QZSS, or Quasi-Zenith Satellite System, contains 4 satellites and is compatible with NAVSATR. Europe’s Galilelo and Russia’s GLONASS complete GNSS, or the Global Navigation Satellite System, which provide world coverage with extensive redundancy due to the overlapping satellites. China and India also have their own constellations, called BEIDOU and IRNSS, respectively, but those satellites are in a geo-synchronus orbit, which means they constantly stay above a single continent, and thus only provide coverage in their given countries. All constellations require continuous upkeep and launch of new satellites, as radiation, time, and technological updates cause old satellites to break down.