The Physics of GPS

Introduction

Whilst complaining about GPS inaccuracies and stupid route choices is a popular pastime, how is it that a set of satellites orbiting 20,000km above us can pinpoint our location on earth’s surface (which is itself rotating at 1,600kph) so accurately?

It is undoubtedly a great feat of engineering that is taken for granted today. The infrastructure and the physics behind the componentry is both complex and intriguing. The GPS project was launched in the ’70s primarily for military purposes. It became fully operational in the ’90s when it also took on a civilian dimension. It is being continually enhanced; satellites get periodically replaced and new functionality gets added. You probably own several, relatively inexpensive, devices capable of navigating using GPS.

The rest of this post details the principles behind how GPS works. Enjoy!

The Basics of Satellite Navigation Systems

GPS24goldenSML

An example of a 24 satellite constellation in motion with the earth rotating. Notice how the number of satellites in view from a given point on the earth’s surface, e.g. Colorado, USA, changes with time.

A satellite navigation system lets a receiver, like a GPS unit or watch, receive radio wave signals for a constellation of satellites orbiting the earth, and process these signals to determine the receiver’s position.

The basic idea is to time-stamp the signal when it leaves the satellite at a known location. When the signal is received, the time it has been in flight is used with the known position of the satellite and the known speed of radio waves, to determine how far the satellite is from the receiver. Repeating this process for multiple satellites gives the location of the receiver.

The radio waves are weak and easily blocked by solid objects like mountains or buildings so line-of-sight from the satellite to the receiver is required. Nothing else is required for the system to work, e.g. no need for the internet or a telephony connection.

The Constellations

There are several satellite constellations; both local and global:

  • Global Positioning System (GPS). This is the original network and the name is synonymous with satellite navigation the way Hoover is with vacuum cleaners. Originally 24 satellites in 6 planes, now 32 satellites. Owned by the US Government and run by the US Air Force. The 2018 GPS budget is just under $1.2bn.
  • Global’naya Navigatsionnaya Sputnikovaya Sistema (GLONASS). This is a russian network of 24 satellites.
  • Galilleo. Expected to be fully operational around 2020 with 30 satellites, owned by the European Union.
  • BeiDou. Owned by China and currently localised to Asia with 16 satellites. Global expansion planned for 2020 with 35 satellites.
  • NAVigation with Indian Constellation (NAVIC). Owned by the Indian government and localised to India with 8 satellites.
  • Quasi-Zenith Satellite System (QZSS). Owned by the Japanese Government, these satellites enhance GPS in Japan.

500px-Comparison_satellite_navigation_orbits.svg

This diagram shows the orbits of the major constellations. Roughly speaking, the satellites orbit twice per day, at about 20,000 km from the earth’s surface whilst travelling at 14,000 kph.

The orbit chosen would have been a compromise between having the satellites far enough away from the earth’s surface so they are visible from as large a portion of the earth as possible, but near enough to the earth to be controlled by the ground stations.

So Where is the Satellite?

I guess when GPS was being devised, there was several ways they could have worked out to get the position of the satellite, at the time the signal was sent, to the receiver.

  1. The satellite could calculate it, knowing its orbit and the time, and send it to the receiver with the time message. This would place the burden of calculating the position on the satellite where computing power would have been at a premium, plus it would complicate the time message sent from the satellite.
  2. The satellite could periodically send details of its flight path to the receiver and based on a simple time message sent from the satellite, the receiver could calculate the satellite’s position. This places the burden of calculating the satellite’s position on the receiver.

Option 2 is what was chosen.

Satellite Orbits

Kepler did a lot of work on the motion of planets around the sun and between 1609 and 1619 published his 3 laws of planetary motion, that Newton later explained with his theory of gravity. There is a whole load of terminology associated with ellipses and planetary motion that gets in the way of understanding what is going, but I’ll do my best to explain it.

The rest of this section is going to get a little complex mathematically, so if this is not your thing please skip it. But bear in mind all these calculations are doing is providing a flight path that allows the receiver to use to calculate the position of the satellite at the time it sent its time message.

We need to be able to describe the position of the satellite at a particular time, t. In general we would need 6 variables in addition to time, to describe this; 3 positional variable (for 3 dimensions) and 3 velocity variables (for the 3 dimensions) at some reference time, t_0. Then based on the force acting on the satellite due to gravity:

F = \frac {G \times m_s \times M_E} {r^2}

Where G is the gravitational constant, m_s is the mass of the satellite, M_E is the mass of the earth and r is the distance from the centre of the earth to the satellite.

Kepler showed that the path followed by two bodies orbiting one another (like the earth around the sun, or a satellite around the earth, is an ellipse. A lot of the geometry of the orbits is done in the frame of reference of the orbit because this makes the 3D problem a 2D problem (at least for a while). The 6 parameters are called the Kepler Elements.

Screen Shot 2018-04-23 at 15.50.54Defining the Kepler Elements

The starting point for a satellite orbiting the earth is that it will follow an ellipse, or squashed circle, with the centre of earth at one of the two foci.

So lets get into some definitions; firstly in relation to the shape and size of the ellipse that the satellite is following:

  • Semi-major axis, a, is half of the long axis of the ellipse.
  • Eccentricity, e = \frac {c} {a} is the degree of ‘squashed-ness’ of the circle.

Screen Shot 2018-04-23 at 17.04.05Now we need to define some sort of earth centred coordinate system.

In this system in the diagram opposite, K points ‘upward’ through the north pole. What about the I and J directions? These form the equatorial plane, but how do we choose 2 axes? Well by definition, I points to the direction of the vernal (March) equinox. J then becomes an orthogonal coordinate (I and J could be chosen differently, it does not really matter).

Screen Shot 2018-04-22 at 20.15.54Next, we need to describe the satellite orbital plane in relation to the earth’s equatorial reference plane. The satellite cuts through the earth’s equatorial plane at two points; where the satellite goes from the Southern Hemisphere to the Northern Hemisphere is called the Ascending Node. The other node is the Descending Node. Two Kepler elements define the orientation of the orbital plane:

  • Inclination, i, is the vertical tilt of the ellipse with respect to the reference plane, measured at the Ascending Node (where the satellite’s orbit passes upward through the reference plane, the green angle i in the diagram).
  • Longitude of the Ascending NodeΩ, is the horizontal orientation of the Ascending Node of the ellipse (where the orbit passes upward through the reference plane) with respect to the reference frame’s reference direction (the green angle Ω in the diagram).

The remaining two Kepler elements are:

  • Argument of Periapsisω, defines the orientation of the ellipse in the orbital plane, as an angle measured from the ascending node to the periapsis (the closest point the satellite object comes to the earth, the purple angle, ω, in the diagram).
  • True anomalyν, at time, t, defines the position of the orbiting body at a specific time, t, called the “epoch”. The word “anomaly” is used here to mean angle.

Things to Note about the Kepler Elements

At first glance the Kepler elements seem like a very complicated way of expressing where the satellite is. For a GPS satellite the Kepler elements are:

  • Semi-major axis, a = 26,610 km
  • Eccentricity, e ≅ 0 (nearly circular orbit)
  • Inclination, i = 55°
  • Longitude of the ascending node, Ω = varies per satellite
  • Argument of periapsis, ω = varies per satellite
  • True anomaly, ν = varies per satellite with time, t

So the first 3 elements are fixed for all satellites in a constellation; the next 2 are fixed for a given satellite and the 6th, ν, is the only one varying with time. This is why for position calculations the Kepler elements are “convenient”; there is only 1 variable, the other Kepler Elements are constants.

The Anomalies (or Angles)

Screen Shot 2018-04-24 at 09.41.35More definitions I am afraid!

Consider the following diagram of the satellite orbit (in the satellite plane so we are in 2-D) and a theoretical circular orbit. I know, I know I’ve been making things complex by using elliptical orbits and now I’m pretending the orbit is circular! In this case it does not make much different as the orbit is very close to being circular. So, there are 3 angles here:

  • The True Anomalyν, describes the angle from the centre of earth to the satellite.
  • The Eccentric Anomaly, E, describes the angle to the theoretical, circular orbit the same x distance as the satellite.
  • The Mean Anomaly, M, describes the angle a hypothetical satellite, travelling the circular orbit at constant angular speed with the same period as the real satellite, travels the elliptical orbit.

Calculating the Satellite’s Position

We have all the pieces now, so let’s calculate the satellite’s position at time, t.

We can start by defining Mean Motion, n:

n = \frac {2 \times \pi} {T}

where T is the time to make one complete orbit.

It is possible to calculate the Mean Anomaly, M:

M = M_0 + (n \times t) where M_0 is Mean Motion at a reference time.

Kepler’s equation relates Mean Anomaly, M, with the Eccentric Anomaly, E:

M = E - e \times \sin E

This cannot be solved algebraically, but an iterative numerical method can quickly calculate E.

The True Anomalyν, can then be calculated from the Eccentric Anomaly, E, as follows:

v = \arctan \frac {\sqrt (1 - e^2) \times \sin E / (1 - e \times \cos E} {(\cos E - e) / (1 - e \times \cos E}

And the distance from the centre of the earth to the satellite, r, can be calculated from:

r = a \times (1 - e \times \cos E)

We now have all the elements to calculate the satellite’s position in its orbital plane:

x_{OP} = r \times cos (v)

y_{OP} = r \times sin (v)

z_{OP} = 0

Orbital Plane to ECEF Reference Frame

So, we now need to convert from the orbital plane to a reference frame that makes sense to us. This will be a reference frame that is stationary relative to the earth’s surface. For now, lets centre it at the centre of the earth (as per the orbital plane so no origin translation is required). However, there are a number of rotations required.

Screen Shot 2018-04-22 at 20.15.54

Consider this diagram again. The plane of reference is the earth’s surface.

The x-axis has been rotated by i and the z-axis by Ω.

The standard 3D rotational matrices for rotating each axis through angle Θ are given by:

R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta \\ 0 & \sin \theta & \cos \theta \end{bmatrix}

R_y(\theta) = \begin{bmatrix} \cos \theta & 0 & \sin \theta \\ 0 & 1 & 0 \\ -\sin \theta & 0 & \cos \theta \end{bmatrix}

R_z(\theta) = \begin{bmatrix} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{bmatrix}

So, to transform the x_{OP}, y_{OP}, z_{OP} in the orbital plane to the ECEF reference frame (x, y, z):

x = x_{OP} \times \cos \omega - y_{OP} \times \cos i \times \cos \omega

y = x_{OP} \times \sin \omega + y_{OP} \times \cos i \times \cos \omega

z = y_{OP} \times \sin i

So there you have it; this is what a typical receiver does to calculate its position.

World Geodetic System (WGS-84)

The ECEF frame of reference used by GPS is the WGS-84. This defines the earth as an ellipsoid (yes, ellipsoids again!). The main parameters are:

  • The coordinate origin of WGS-84 is located at the earth’s center of mass.The WGS-84 meridian of zero longitude is the IERS Reference Meridian (102 metres east of the Greenwich meridian.
  • The WGS-84 datum surface is an oblate spheroid with equatorial radius a = 6,378,137 m at the equator and flattening f = 1/298.257223563. The polar semi-minor axis b then equals a × (1 − f) = 6,356,752.3142 m.Currently, WGS 84 uses the Earth Gravitational Model 1996 geoid, revised in 2004.

If your GPS is set to display a different frame of reference then there will be additional conversions going on from WGS-84, which is what GPS is using internally, to the display format of your choice.

Elliptical Orbit Perturbations

Up until now we have considered the satellite motion to be a pure Kepler orbit due to the gravitational effect of a nice, spherical earth on the satellite. This is not quite true and other effects come into play that effect the satellite’s orbit.

  • The Earth is not a uniform sphere. It is an ellipsoid with a diameter 20km more at the equator than at the poles. Also, the density is not uniform with distance from the centre which has an effect on the satellite’s orbit.
  • Other gravitational effects in the Solar system most notably the sun and the moon have an effect on the satellite’s orbit.
  • Effects of tides.
  • Solar radiation pressure.
  • Atmospheric drag.
  • Relativistic effects.

All of these effects move the satellite a small amount from the elliptical orbit modelled above. The ground station monitors the path of each satellite and predicts how these effects will move the satellite’s orbit in the future. These small effects are modelled back into the elliptical equations as adjustments that are send to the satellite with the orbital parameters, and are sent on from the satellite to the receivers back on earth. The GPS specification explains how to take these small adjustments into account in calculating the satellite position.

The Ephemeris

Each satellite travels on an elliptical orbit around the earth. The administrators of the constellation are monitoring each satellite constantly for two things: the time of the onboard clock (will come back to this because it is critical to the whole GPS setup); and the exact orbit that the satellite is following. Information is sent to the satellite regarding any clock drift which can be corrected for, and the location of the satellite at any given time, called the satellite’s ephemeris.

In turn, the satellite broadcasts a signal, in effect saying, at this precise time, t, the satellite is exactly here. This is the information received by the GPS receiver.

Of course, the issue is that the satellites are not following exact orbits and therefore there is some error in these calculations. This is estimated at 2.5m

GPS Signals

GPS uses the ‘L’ band of 1 – 2 GHz which is microwave. It is relatively easy to generate but still passes through the atmosphere, clouds, rain, etc with minimal interference. It can be detected with small antennas (unlike radio and TV waves for example).

The table below summarises the carrier frequency bands used by GPS:

Screen Shot 2018-04-21 at 08.22.08

L1, L2 and L5 are relevant for GPS navigation. The encrypted messages are for military purposes.

The data is modulated onto the carrier wave, which is right-hand circularly polarised. For example, in the case of the L1 carrier:

Screen Shot 2018-04-21 at 08.30.42

There are two types of codes: C/A (course/aquisition) codes and P (precision) codes.

P codes are very long; they repeat every 266 days so not relevant for moving GPS applications.

The C/A code is a pseudo random number (PRN) code (also called a Gold code, after Robert Gold).

In addition to the codes. a navigation (Nav) message is also modulated onto the carrier wave at 50bps.

PRN Code

The L1 PRN code is a binary sequence of information (‘0s’ and ‘1s’) that repeats itself every millisecond. It is 1,023 bits long, called a chip giving rise to a chipping rate (the rate at which each chip is modulated onto the carrier) of 1.023 Mbps.

The L5 PRN code is longer than the L1 PRN code. It repeats every millisecond and has a chipping rate ten times higher at 10.23 Mbps.

The purpose of the PRN code is to identify the originating satellite and to provide a time marker that is used to calculate the satellite range from the receiver.

Navigation Message

The Navigation message is structured as follows:

  • 25 frames, each consisting of 5 sub-framesSub-frame 1 contains clock correction, GPS week info
    • Sub-frames 2 and 3 contain Ephemeris data
    • Sub-frames 4 and 5 contain Ionosphere and satellite constellation information called the Almanac. There are 25 different versions of ‘sub-frames’ 4 and 5, each one called a page. Each page holds a piece (a 25th) of the total data.
  • Each sub-frame consists of 10 wordsWord 1 is always the telemetry, TLM, word.
    • Word 2 is always the HandOver word, How.
    • Words 3 – 10 contain frame specific data.
  • Each word consists of 30 bits of data.

Screen Shot 2018-04-21 at 14.57.22

So 1 Nav message = 25 frames = 25 x 5 sub-frames = 25 x 5 x 10 words

1 Nav message = 25 x 5 x 10 x 30 bits = 37,500 bits.

The message is broadcast at 50bps so takes 12.5 minutes to broadcast.

TLM Word

The TLM word enables the receiver to detect the beginning of a subframe and determine the receiver clock time at which the navigation subframe begins; it synchronises the receiver with the Nav message. The TLM word starts with an 8 bit preamble for recognition for the receiver. This is then followed by 16 bits of reserved data which includes the ending 6 bit checksum or parity.

A receiver will look for the preamble which marks the beginning of the new sub-frame. To confirm this, the receiver takes the reserved data, creates a parity, and checks to see if this corresponds with the last 6 bits of the TLM. If this does not match, the receiver again looks for the next preamble.

How Word

The Handover word, How, comprises two sections. The first 17 bits of this part of the header are given over to providing Time of Week to ensure that the GPS receiver is fully synchronised to the satellite time.

The last six bits within the How word are used for another parity check.

Sub-frame

Each sub-frame has a separate header so that a receiver can start meaningful reception in the middle of a broadcast, and not have to wait up to 30 seconds for the next cycle.

Sub-frames 2 and 3

These contain Ephemeris data. The GPS control station (on earth) is continually monitoring the trajectory of each satellite and calculating the best-fit elliptical orbit that matches the projected satellite trajectory for a 4 hour window. The parameters for this elliptical are then uploaded once per day to the satellite when it is overhead. The satellite updates sub-frames 2 and 3 of the Nav message with the current parameters every 2 hours.

The GPS receiver needs accurate Ephemeris parameters to calculate a position so this data is replicated throughout the Nav message to minimise the delay between a satellite starting to listen to the Nav message and it being able to calculate a ‘first fix’. The time-to-first-fix, TTFF, is important for runners, for example, as it is the time we all stand in the open with our watches pointing at the sky waiting for a satellite fix before we start our run.

To get a first-fix on a satellite, sub-frames 1,2 and 3 are needed (clock sync info in sub-frame 1 and Ephemeris data in sub-frames 2 and 3). If the receiver starts listening just as sub-frame 1 is starting then the TTFF is 18 seconds. If it starts listening just after sub-frame 1 has started then it needs to wait 36 seconds (6 seconds for sub-frame 1 to pass through and be discarded – it missed the start, then 30 more seconds for sub-frames 2,3,4,5 and then 1 again).

Sub-frames 4 and 5

These contain an almanac of coarse orbit and status information for each satellite in the constellation, ionospheric model parameters, and information to relate GPS derived time to Coordinated Universal Time (UTC).

Each frame contains a part of the almanac (in subframes 4 and 5) and the complete almanac is transmitted by each satellite in 25 frames total (requiring 12.5 minutes). The almanac serves several purposes:

  1. To assist in the acquisition of satellites at power-up by allowing the receiver to generate a list of visible satellites based on stored position and time.
  2. To relate time derived from the GPS (called GPS time) to the international time standard of UTC.
  3. To allow a single-frequency receiver to correct for ionospheric delay error by using a global ionospheric model.

The Almanac data is calculated by the ground station and, like the Ephemeris data, loaded up to the satellite. Because it contains much less accurate versions of satellite position data the GPS SLA says it will be updated at least every 6 days.

The Almanac and the Ephemeris

The Ephemeris data is specific to the satellite sending it; while the Almanac data is about the entire GPS satellite constellation so each satellite broadcasts the same data. When first constructed the idea for the receiver was:

  • Listen to and construct an Almanac from almanac data.
  • Then, work out which satellites should be visible and listen one at a time for these and acquire Ephemeris data from each.
  • Start position monitoring.

Things have moved on since then and the concept of the Almanac is a little dated. Modern devices are capable of listening on multiple channels for satellites simultaneously. If the NAV message was to be designed now it would be completely different.

The CNAV Message

A slightly different navigation message is broadcast on L2 and L5, called the CNAV. Its structure is more flexible than the NAV message and it contains more precise versions of data, but in essence it contains the same type of information.

Basic Location Calculation

gps__26

Consider the following setup with a set of satellites, each with a known set of x, y, z coordinates, and a receiver with unknown X, Y, Z coordinates. The time interval the signal takes to travel at speed, c is \delta t

Its possible to setup a series of equations for each of the distances between the receiver and each satellite:

d_1 = c.\delta t_1 = \sqrt ((X - x_1)^2 + (Y - y_1)^2 + (Z - z_1)^2)

d_2 = c.\delta t_2 = \sqrt ((X - x_2)^2 + (Y - y_2)^2 + (Z - z_2)^2)

d_3 = c.\delta t_3 = \sqrt ((X - x_3)^2 + (Y - y_3)^2 + (Z - z_3)^2)

d_4 = c.\delta t_4 = \sqrt ((X - x_4)^2 + (Y - y_4)^2 + (Z - z_4)^2)

Some points to note:

  1. This is the general situation for using GPS, 4 satellites need to be in view to calculate  the receiver’s position. Each satellite gives details in one of the above four equations for which there are 4 unknowns (X, Y, X, T). These equations would be solved iteratively, for example on a GPS chip within a watch or smartphone, for example.
  2. If more than 4 satellites are available then a best fit calculation can be performed using all available satellites.
  3. If the clock at the GPS receiver is synchronised with the satellites then \delta t is known and only 3 satellites are needed for the receiver’s position to be calculated. This would be the case for the ground station controlling the network but not for normal GPS receivers.
  4. If one of the receivers’ coordinates is known, for example the receiver is on a boat on the sea where, lets say Z = 0 (for sea level), then one fewer satellites are needed, so 3 rather than 4.

Satellite Time

Accurate time measurement is essential for GPS calculations. Here is why: the satellite signal travels at a speed of c = 299,792,458 metres/second.

So, lets say the clock is accurate to 1/1000 of a second (this is what Formula 1 lap times are measured in). In this case, an error of 1/1000 of a second would equate to a distance error of 300 km! This would be useless.

If the clock was accurate to say 3 nano-seconds then that would equate to a distance error of about 1m; which is much more acceptable.

The satellites carry on board, multiple atomic clocks to be able to timestamp the signal before it is sent, as accurately as possible. Low end receivers, like phones and watches need some sort of internal clock but this is not used in the position calculation, so no need for an atomic clock on your wrist!

The US government produce an annual report on GPS performance, as do the FAA. Looking at the latest FAA report, they compared the satellite atomic clock time to the reference atomic clock the US maintain to get the graph below.

Screen Shot 2018-04-27 at 08.18.51

Using the 95% time of 10.4 nano-seconds equates to positional user range error of 3.1m.

How do Atomic Clocks Work?

The principle used is that electrons in an atom have very well defined energy levels. If an atom is irradiated with radiation of the correct frequency, an electron will move between its ground state and the next level. From a beam of atoms, the proportion with electrons in an excited state is detected and the frequency of the radiation used to irradiate the atomic beam is varied until a peak in excited atoms is detected. The frequency of radiation producing the peak corresponds to the difference in energy between atoms with electrons in the ground state and the excited state.

For caesium, for example, this frequency is 9,192,631,770 cycles per second. Or, put another way, counting from zero, when the 9,192,631,770th wave passes, this marks the passing of 1 second.

Relativistic Effects

GPS is a great test of Einstein’s theory of relativity as the effects, although in some senses small, are pronounced enough to have a major effect on the GPS system’s accuracy. Without correcting for these relativistic effects, GPS would be unusable.

There are two components of relativity;

  • Special Relativity, proposed by Einstein in 1905, deals with the structure of spacetime and how observers in relative motion perceive phenomena.
  • General Relativity, proposed by Einstein between 1907 and 1915, is a theory about gravitation.

Special Relativity

From the perspective of a receiver on the earth’s surface, a satellite in an elliptical but  near circular orbit (radius r_o) around the earth twice per day is moving with speed:

v = \frac {2 \times \pi.r_o} {12 \times 60 \times 60}

where r_o = 20,000 km + RadiusOfEarth (6,371 km)

v = \frac {2 \times \pi \times 26,371 \times 10^3} {12 \times 60 \times 60} = 3,836 m/s

One of the effects of special relativity is that time for observers moving at different speeds ticks at different rates. This is nothing to do with the clock being used to measure the time interval, it is to do with the nature of time itself. The faster an objects travels to the speed of light, c, the more time slows down, or dilates.

The standard, Lorentz factor, \gamma equating a time interval as measured by two observers moving relative to each other at speed, v, is:

\gamma = \frac {1} { \sqrt (1 - (\frac {v} {c})^2)}

Over the course of 24 hours, the time dilation would be:

24 \times 60 \times 60 \times \gamma = \frac {24 \times 60 \times 60} { \sqrt( 1 - (\frac {3,836} {299,792,458})^2} = 7 microseconds

An error in timing of 7 microseconds would equate to a distance error of over 2km !

So, obviously, this effect needs to be adjusted for. The GPS specification for anyone developing a receiver includes an algorithm to adjust the time received in the GPS signal to account for this special relativity time dilation. The exact orbit parameters of the satellite, or ephemeris data, is part of the message broadcast by the satellite.

General Relativity

Mass curves spacetime, the larger the mass, the more spacetime is curved. A large mass, like the earth, distorts spacetime quite significantly. For a spherical object like the earth, the force, g, a distance, d, away from the centre of the earth is given by:

g = \frac {G \times M} {r^2}

where G is the gravitational constant: 6.674 \times 10^{-11}

M is the mass of the earth: 5.972 \times 10^{24} kg

On the surface of the earth, r = 6,371km:

g = 9.8 m/s^2

On a GPS satellite, r = 26,371km:

g = 0.57 m/s^2

So, you can see that there is a significant difference in the gravitational effect experienced on earth versus that experienced on a satellite.

One of the predictions of General Relativity is that clocks closer to a massive object will seem to tick more slowly than those located further away. The gravitational time dilation factor is given by:

\delta t = \sqrt (1 - \frac {2 \times G \times M} {r \times c^2})

So, on the earth’s surface there is a bigger time dilation than onboard the satellite. Running the above calculation for the earth’s surface and the satellite and running the effect over 24 hours gives

\delta t = 45 microseconds

This is an even bigger effect than the Special Relativity time dilation!

This effect is corrected onboard the satellite itself by adjusting the frequency of the atomic clocks relative to the those at the base station on earth so that when they are compared the adjustment offsets the gravitational time dilation.

543px-Orbit_times.svg

This is a nice graph showing the two opposing effects of time dilation from Special Relativity (Orbital Speed Slowdown) and General Relativity (Gravity Speedup).

An interesting side effect, is that as you get closer to the centre of the earth, so gravity increases and so the gravitational time dilation increases. It has been estimated that the centre of the earth is a year or two younger than the surface; our planet really is young at heart!

Sagnac Effect

A related adjustment that is necessary in GPS is due to the Sagnac Effect. This relates to reference frames. If we used a reference frame for the calculation that was not moving, or inetial, for example, the centre of the earth, then there would be no Sagnac Effect. GPS, however, uses the WGS84 frame (more on this later). This frame is based on the surface of the earth and rotates with the Earth. This is convenient for map makers but means that GPS needs to translate position calculations into a rotating frame of reference.

And this is where the Sagnac Effect comes in. Light propagates in straight lines in inertial frames, in a rotating reference frame it propagates as a spiral. So, a way for the receiver to solve the position calculations is to translate satellite positions at the time of a signal broadcast to an inertial, earth centred, reference frame.

Adjustment then needs to be made for the motion of the receiver on the earth’s surface, rotating at 463 m/s. If each satellite sends a signal at exactly the same time, they will all arrive at the receiver at different times (since they are different distances from the receiver). The receiver will have moved different distances when different signals arrive and this needs to be corrected for in the receiver.

For example, a series of signals from several satellites all send at the same time could arrive 18 milliseconds apart. Over this time, the receiver itself, will have moved due to the earth’s rotation, by over 8 metres.

Dilution of Precision (DOP)

440px-Geometric_Dilution_Of_Precision.svg

Consider an example of two satellites, red and blue in figure A. A receiver calculates the distance it is away from the red satellite based on the time it takes for the signal to arrive. This is a circle (sphere in 3D) centred on the satellite. Repeating the process for blue results in an intersection of the red and blue circles.

Now, we know that there are some errors in the satellite time calculation that can be mapped to positional errors, so in B we have shown the range of circles corresponding to the error, from the red satellite as grey circles around the red and the same for blue. The green shape in B represents the receiver’s possible location.

C is the same process but the geometry of the red and blue satellites is different, resulting in a quite different green area of possible locations.

This simple example illustrates that the location of the receiver is somewhere in a complex shape in three dimensional space, and it also illustrates that that shape and its area are dependent upon the geometry of the satellites and the receiver.

DOP can be expressed as a number of separate measurements:

  • HDOP – horizontal dilution of precision
  • VDOP – vertical dilution of precision
  • PDOP – position (3D) dilution of precision
  • TDOP – time dilution of precision
  • GDOP – geometric dilution of precision (combination of PDOP and TDOP)

URE-vs-user-accuracy

The DOPs are setup as scaling factors that convert the User Range Errors (URE) to position errors. Many components add errors into the GPS system, for example, the atomic clocks have a few nanoseconds of error in them. This can be converted into an equivalent URE.

PDOP = \frac {\delta (UserAccuracy)} { \delta (URE)}

The DOPs are related as follows:

PDOP^2 = HDOP^2 + VDOP^2

GDOP^2 = PDOP^2 + TDOP^2

Some points to note:

  1. GPS satellites are only visible if they are above the horizon (the weak radio waves do not travel through the earth) so less than half the satellites are visible at any one time.
  2. The more widely spread the visible satellites are the smaller the 3D space the receiver is located in, or put another way the more accurate the position will be.
  3. Conversely, the closer together the satellites are, the less accurate the position will be.
  4. Note, the 3D space that bounds the location of the receiver, is a complex shape and the errors are different in different directions depending on the satellite geometry. In particular, because all visible satellites are above the horizon, the geometry is worse at calculating height than horizontal position.

The smaller the dilution of precision, the more accurate the satellite geometry. Here are some examples:

Screen Shot 2018-04-17 at 20.49.37

In the above, HDOP will always be lower (more accurate) than VDOP. Combining HDOP and VDOP gives PDOP and adding in time gives GDOP. The point to note is that DOP varies all the time as the satellite geometry changes. Here is the plot for the same location the previous day:

Screen Shot 2018-04-17 at 20.53.29

Now, the above calculations have assumed we have good visibility of the sky, from 10 degrees from the horizontal, for example in an open field. Now, if we have reduced visibility, e.g. 20 degrees to the horizontal.

Screen Shot 2018-04-17 at 20.57.29

DOP gets worse as we are now seeing fewer satellites and they are concentrated in a smaller part of the sky. The bad peaks get significantly worse. Adding in the GLONASS constellation improves things as there are more satellites in the sky.

Screen Shot 2018-04-17 at 20.59.36

Note that although there are more satellites visible, the DOP is still worse than the original graph with just GPS (no GLONASS) with a wider field of vision. This illustrates the point that more satellites is better, but a wider field of view is even better.

Atmospheric Effects on GPS Signals

The speed of light in a vacuum is a constant, but the GPS signals need to travel through the earth’s atmosphere before they reach the receiver on the ground. And this introduces complexity.

Ionospheric Delay

The ionosphere is the zone of the terrestrial atmosphere that extends from 60 km to more than 2,000 km from the earth’s surface. It contains a partially ionised medium, as result of the X and UV rays of Solar Radiation and the incidence of charged particles.

The speed of the GPS signals in the ionosphere depends on its electron density, which is driven by two main processes:

  1. During the day, the sun’s radiation causes ionisation of neutral atoms producing free electrons and ions.
  2. During the night, the recombination process prevails, where free electrons are recombined with ions to produce neutral particles, which leads to a reduction in the electron density.

So, the Ionospheric delay depends upon:

  1. The time of day.
  2. The sun’s activity (during solar flares there will be much more radiation hitting the ionosphere.
  3. The distance a GPS signal needs to travel to pass through the ionosphere depends on the slant angle between the satellite and the receiver

The effect of the ionosphere introduces a GPS signal delay of between 5 and 30 nanoseconds. This is about 1.5 and 9 metres.

There are 2 mechanisms GPS systems use to compensate for Ionospheric delay:

Dual Frequency Receivers

Dual frequency receivers are able to detect the same signal sent at the same time from the same satellite at different frequencies: e.g L1 and L2, or L1 and L5. The ionospheric delay is different for different frequencies and therefore the arrival time for L1 is different than L2. Using this time gap, it is possible to calculate the full ionospheric delay at the receiver and fully compensate for it.

This is the most accurate way of dealing with the ionospheric delay.

Single Frequency Receivers

GPS has built in an ionospheric model that can be used by single frequency receivers called the Klobuchar model. This assumes the ionosphere is a narrow layer 350km from the earth’s surface. It assumes a constant value at night and a cosine shape during the day. See the below diagram:

Klobuchar_Klobychar_slide

The GPS satellite sends the parameters for the Klobuchar model to the receiver so it can perform the calculation of ionospheric time delay and compensate accordingly.

The model is a very simplified one of the ionospheric delay and is a compromise between accuracy and calculation complexity at the receiver. It is estimated that it removes about 50% of the range error.

Tropospheric Delay

The troposphere is the atmospheric layer between the earth’s surface and an altitude of about 60 kilometres.

The effect of the troposphere on the GPS signals is to delay them. This delay depends on the temperature, pressure, humidity as well as the slant angle through the troposphere (as with the ionospheric delay).

The main feature of the troposphere is that it is a non dispersive media with respect to GPS signals, i.e., the tropospheric effects are not frequency dependent and cannot be removed by combinations of dual frequency measurements (as can be done with the ionosphere delay).

The only way to mitigate tropospheric effects is to use a model. Most start with the following equation for delay, d:

d = d_h^z.map_h + d_w^z.map_w

where d_h^z is the hydrostatic component at the zenith and map_h is the mapping function based on the geometry of the satellite and receiver, and d_w^z is the wet component at the zenith and map_w is the mapping function based on the geometry of the satellite and receiver.

There are two components to the delay:

  • Hydrostatic component delay makes up about 90% of the total tropospheric delay. This is caused by the dry gases present at the troposphere (78% N, 21% O, 0.9% Ar, etc.). Its effect varies with local temperature and atmospheric pressure in a predictable way, and its variation is less that the 1% in a few hours. The error caused by this component is about 2.3 meters in the zenith direction and 10 meters for lower elevations ( approximately).
  • Wet component delay is caused by the water vapour and clouds and, therefore, depends on weather conditions. The excess delay is small in this case, only some tens of centimetres, but this component varies faster than the hydrostatic component is difficult to model.

Screen Shot 2018-04-18 at 13.35.19

The graph above shows the hydrostatic (left) zenith component delay in cm and the wet (right) zenith component delay in cm.

The GPS system leaves compensation for the tropospheric delays to the receiver because the delay is fundamentally a feature of the local temperature, air pressure and weather.

There is a model proposed by Neill that does not require knowledge of the local weather and utilises the same zenith and angular approach as the Klobuchar model uses for Ionospheric compensation.

The US government’s GPS performance report suggests using a URE of 3.9m for the tropospheric delay, but more recent sources suggest using 0.5m. I guess it depends on how sophisticated the model is.

Multipath Effects on GPS Signals

Multipath_Fig_1

This diagram shows how the receiver can receive multiple copies of the same satellite signal; a direct signal and one or more reflected signals from the ground and nearby buildings, for example.

The direct signal with always arrive first as it has taken the shortest route to the receiver so if the signals are far enough apart to be detected as separate signals then the receiver can safely discard all but the first signal, safe in the knowledge that the other(s) are reflected signals.

However, if the direct and reflected signals arrive very close to each other, they will interfere and not appear as separate signals. This is shown below;

Screen Shot 2018-04-18 at 14.58.19

The net effect is that a signal waveform arrives at the receiver which is a composition of the direct signal and one or more reflected signals which now appears at a different time corresponding to a different position.

The chipping rate of the GPS L1 signal is 1.023MHz which corresponds to a wavelength of 293m. It should be able to relatively easy to discard reflected waves more than ¼ of a wavelength out but that still represents a range error of 73m.

GPS satellites have started broadcasting on L5 where the chipping rate is 10.23 MHz which scales the multi path errors down by a factor of 10. There are just about enough satellites currently functioning to make this an attractive option and GPS chip manufacturers are working on this; in late 2017 Broadcomm announced the BCM47755 chip which will process L1 and L5 from GPS, Galileo and QZSS.

There has been much research into how to compensate for the multipath effect. Logically, several options present themselves:

  • The GPS signal is right circularly polarised. When reflected the polarisation changes to left-handed. Although a double reflection would be back to right-handed. So detect right-handed polarised waves only.
  • The leading edge of the waveform is unaffected by multipath effects as the reflected waves always appear after the direct signal.
  • Decomposing the arriving waveform into a combination of possible waves and filter out the reflected waves from the signal. Not easy as there is ever present “noise” in the system.
  • Antenna design to minimise reflections from the earth below. This is fine for static receivers, as anyone who has tried to tune-in a TV with a directional aerial will know. Not so good for moving receivers though.
  • Discard satellites at low angles, say < 15 degrees from the horizontal. This obviously makes the DOP worse as satellites are taken out but removes a lot of ground reflections.

The responsibility for multi path correction rests with the receiver, but what measures are actually taken by the receiver manufacturers is a bit of a mystery. The US government’s GPS performance paper suggests a URE of somewhere between 0.2m and 2.4m for multipath effects.

software-avanzado-senal-generador-puede-crear-respuestas-complejas-senal-tales-como-mimico-dinamica-barranca-urbana-receptores-gps-cortesia-rohde-schwarz-1161-8445552

Another point about multipath errors is that sometimes the only signal arriving at the receiver comes from a reflection, because the direct line-of-sight signal is blocked (this is the blue line in the diagram).

This diagram represents the “urban canyon” problem that occurs in cities with tall buildings (although would equally apply to real canyons).

The signals arriving at the receiver become very complex with a corresponding degradation in GPS accuracy. This is one potential reason for the GPS position to jump around through building, etc.

Receiver Timings Errors

GPS receivers do not have the same level of timing accuracy as the satellites do with their atomic clocks. However they do need to measure the delay to the time of arrival of the incoming GPS signals. This is done electronically, typically, by comparing the signal arriving from the satellite with an internally generated, expected signal. The edges of the signal that corresponds to the ‘1s’ and ‘0s’ of the bit stream allow precise timing and therefore calculation of the delay used in the position calculations.

Again, the GPS receiver manufacturers are forever making the electronics more and accurate and, of course, patenting their work. Basically, however, the electronics is able to detect about 1% of the bit pulse.

For an L1 signal this corresponds to a URE of: \frac {1\% \times c} {ChippingRate} = \frac {1\% \times 299,792,458} {1.023 \times 10^6} = 2.9 metres

For an L5 signal the URE is: \frac {1\% \times c} {ChippingRate} = \frac {1\% \times 299,792,458} {10.23 \times 10^6} = 0.29 metres

Putting All The Errors Together

Assuming the contribution of each source of error is independent from all the others and that all the errors follow a gaussian distribution, it is simple to find the overall, or root mean square, error, \sigma, as follows:

\sigma_{RMS} = \sqrt (\sigma_1^2 + \sigma_2^2 + ... + \sigma_n^2)

So, for fun I’ve created a table of UREs assuming:

  • a basic GPS device tracking L1
  • a more sophisticated device tracking L1 but modelling ionosphere and troposphere errors.
  • a more sophisticated dual band device tracking L1 and L5
URE Source L1 Simple
Effect (±m)
L1 Complex
Effect (±m)
L1 & L5
Effect (±m)
Satellite clock errors 3.1 3.1 3.1
Relativity errors 0 0 0
Ephemeris errors 2.5 2.5 2.5
Ionospheric effects 5 2.5 0
Tropospheric effects 0.5 0.5 0.5
Multipath distortion 2.4 2.4 0.2
Receiver Timing Errors 2.9 2.9 0.29
RMS Error, \sigma_{RMS} 7.4 6.0 4.0

To get from RMS Error, \sigma_{RMS}, to GPS accuracy we need to multiple by the DOP. For example:

Horizontal accuracy, \delta_H = \sigma_{RMS} * HDOP

Vertical accuracy, \delta_V = \sigma_{RMS} * VDOP

3-D Position accuracy, \delta_P = \sigma_{RMS} * PDOP

In good, open conditions, the HDOP should be slightly less than 1. VDOP is typically 50% to 100% worse than HDOP. In worse conditions, the DOP can degrade substantially. The other thing to bear in mind is that these errors are 95% confidence, which means that there will be times when the errors are outside these numbers, potentially considerably outside.

So what do these errors and positional inaccuracies really mean? Well, for a start they are statistical in nature so the 95% confidence means that 5% of the time, the errors are bigger. How much bigger? Well they could be a lot bigger. Secondly, these errors are essentially random, like, for example, if you throw darts at the bulls-eye of a dartboard. Some will be near, maybe even in the bull-eye, but others will be essentially randomly scattered around the bulls-eye. Occasionally, one may be so far away, it misses the board! However, throw enough darts and measure where they all are and the average should be pretty close to the bulls-eye. Same with GPS, take enough measurements and the average should be more accurate that an individual measurement.

Augmented GPS

There are various method of assisting GPS to give a more accurate position. In the past the focus has been building ground stations whose locations are precisely known. These monitor the satellite signals and based on the actual data of the range, are able to calibrate models to accurately compensate for errors. These services tend to be continental region based, so the US has WAAS and Europe has EGNOS. This information can then be fed to receivers either via a geostationary satellite network or the internet. The receiver then uses the data to improve accuracy compared to raw GPS data.

These services are often developed with civil aviation in mind, but potentially can be used by anyone with an enabled device providing they are in the correct region.

More recently, devices have started incorporating sensors like gyroscopes to determine device motion and orientation. This data can also be used to assist the raw GPS data to come up with a better position estimate. For example, if the raw GPS data indicates a movement to the left and this is not supported by the accelerometer data, then the raw GPS data may be overridden.

Software

The raw GPS position data can be processed in many ways dependent upon the type of application. For example, for car based GPS devices when position is displayed on a map, the software may well “snap” location to a road even if the raw data puts the vehicle off the road.

For sports devices like running watches, the software is likely to monitor the last few seconds of data to give context to what the runner is doing. The raw data may well be showing zig-zagging along a path but the software may well be showing a fairly straight run. Similarly, when the runner starts a turn, the software may initially not respond to the turn, but only when the number of measurements breaks a threshold to indicate a turn, will the software respond. How, the software then retrospectively looks at the where the turn started is upto the software designers.

The software needs to be able to deal with satellites dropping out and coming back into view; going under bridges where temporarily no satellites may be visible; multi path effects coming and going as the runner runs past buildings; signals being attenuated in forests, etc. Over time manufacturers continue to build more sophisticated GPS processors to get more accuracy from the raw numbers.

GPS Maintenance and Outages

As with all complex pieces of engineering, two things happen:

  1. There is scheduled maintenance. Satellites can be individually marked as unhealthy and taken out of service whilst maintenance is carried out. GPS considers 24 satellites as the minimum number required for an operational constellation, so taking the odd one offline out of the 31 in orbit doesn’t do much harm,
  2. There are unplanned outages where something fails and causes a problem. If its an individual satellite this is unlikely to cause a significant issue. Occasionally, other things do go wrong, though, for example, on 26 January 2016, an incorrect time offset was uploaded to half the GPS satellites which messed out the calculations for several hours. On 1st April, 2014, GLONASS broadcast incorrect data causing position calculations to be out by hundreds of kilometres for several hours. Still, most of the time, GPS just works.

If you want to see the current operational state of the constellation, have a look here.

GPS Device Characteristics

Time-To-First-Fix

GPS devices typically have 3 modes:

  1. Cold start. Out of the box with no current satellite information or if no parameters have been loaded, the device will undergo a cold start. The device will need a full NAV message to load the Almanac. It will need to lock onto each visible satellite.
    • Worst case. 12.5 minutes to download the Almanac then 18 to 36 per satellite to get a lock on each. Most devices would lock onto each satellite in parallel so TTFF would be about 13 minutes.
    • Better case. Process the first 4 satellites as they are identified over the Almanac, somewhere between 2 minutes and 12.5 minutes depending on where in the message broadcast the receiver turns on. TTFF would be variable between 2.5 and 13 minutes.
  2. Warm start. The device persists the Almanac which is valid for about 6 days. This is either from the last GPS session or loaded onto the watch from the internet. Garmin, for example, do this via a file called EPO.bin than is loaded everytime the device is synchronised with their software. So on startup what is needed is to get the Ephemeris data from the visible satellites. TTFF would be 18 to 36 seconds.
  3. Hot start. The device persists Almanac and Ephemeris data between sessions. The Ephemeris data is valid for 4 hours (although GPS recommend loading every 2 hours). If a new session is started within 2 or 4 hours (device dependent) of the end of the previous session, then the persisted data could be used giving a much  faster TTFF (just the bootup time for the electronics and to get synchronisation with the satellites). Would typically be a couple of seconds.

Most devices store the last known position and satellite time when a session is ended. On startup, this data would be used in a warm or hot start to get the first fix. If there is a problem and the satellites are not where the device is expecting it will force a cold start. In my experience this happens if you move more than a couple of hundred miles from the last session or the device runs out of power and needs to be recharged where the satellite time may be lost. This is all manufacturer depended.

GPS Tracks Different for the Same Run

This is a popular complaint, that when someone run the same route multiple times the GPS trace is different each time. The point is that the satellite configuration is different each day so the DOP is different for every run, the weather and ionospheric conditions will be different, etc., so the accuracy will always be different. If you want to get a view on accuracy do multiple runs and looks for averages; or, if possible, wear two watches to compare on the same run.

Bad GPS Tracks

Without doubt there are areas where GPS struggles to accurately locate you. Usually this is a combination of multipath and a poor DOP configuration. Over time, device manufacturers have built more sophistication into dealing with these scenarios. The fact is that some devices are better at dealing with certain edge conditions than others. As a device user there is not much you can do if your watch has you swerving about when you are moving in a straight line.

GLONASS

GLONASS is a similar network to GPS, but with 24 satellites. It has become popular to allow a combination of GPS and GLONASS to enhance positional accuracy. My own opinion here is that the manufacturers treat it like an add-on so may or may not put as much effort into integrating the GLONASS constellation as they would for basic GPS.

I have tried GPS on its own and GPS+GLONASS and have not seen much difference. I think this is because:

  • If the DOP is good with GPS then adding in GLONASS will not make much improvement.
  • If the DOP is bad it could be because, either
    • it is a poor GPS configuration (see the DOP section). In this case adding GLONASS may significantly improve the overall DOP and therefore the position accuracy, or
    • the receiver is in a poor location like a canyon. Adding more satellites with GLONASS in the same geometry as GPS will only make a small improvement (what is needed here is visibility on the hidden satellites that would improve the DOP.
  • From what I’ve read the clocks on the GLONASS satellites are not quite as accurate as the newer GPS clocks so adding in GLONASS add more satellites but these satellites are slightly less accurate.

The Future

Galileo

Galileo is the EU satellite constellation that is in the process of becoming operational. Each satellite has two hydrogen masers and two rubidium atomic clocks. The intention is that one of the hydrogen masers provides the primary source of timing data, backed up by a rubidium clock in hot standby. The hydrogen maser is accurate to 1ns or 30cm; the rubidium clock is 4 times less accurate.

GPS chip manufactures are starting to include support for Galileo. It has the potential to improve accuracy so will be interesting to see how things develop.

From a running perspective, however, I am not sure what I would do with better accuracy. Most of my runs are in areas where satellite reception is quite good so getting a more accurate trace would not change anything for me.

Dual Band Receivers

These have been around for a long time, but it looks like cheaper chip manufactures are ready to make these available in low end devices like phones and watches. For example, Broadcomm’s BCM47755 chip which will process L1 and L5 from GPS, Galileo and QZSS. This will result in much more accurate positioning through better ionospheric and multi-path correction, and with Galileo, more accurate atomic clocks.

2-Way Communication

Currently GPS is for most people is 1-way; satellite to receiver. More services are planned that will allow 2-way communication between receiver and satellite for things like SOS situations. These services exist today over telephony links but are obviously limited to situations where a telephony link exists. This will change.

Augmented GPS

Further development of augmentation services is likely more low end devices could end up having these services enabled.

The integration of gyroscope / accelerometers and other device sensors with GPS data is likely to grow and as the software to manage this improves, so will accuracy levels.