Introduction to GNSS: Some Basics
This past Tuesday witnessed the launch of the final satellite in the Chinese BeiDou Navigation System. It’s been 20 years since the first launch for the BeiDou-1 system, which consists only 3 satellites with limited coverage; and now BeiDou-3 has global coverage, and I am impressed that China only used 5 years to build it up.
I’ve learned some basics of GNSS during my bachelor’s degree, and for the past half-year I’ve been focusing on GNSS-based localization, thus I think it will be good for me to review some of my knowledge and share it here as a celebration for Beidou as well.
GNSS vs. GPS
First things first, one might already be wondering, what is GNSS? Most people should be familiar with GPS, but many may not hear of GNSS often. GNSS stands for Global Navigation Satellite System, including all navigation systems which use satellites to provide autonomous geo-spatial positioning. GPS is the first GNSS launched in 1978 and developed by the U.S., and there are many satellite navigation systems out there established by other organizations. The below figure describes the relationship between GNSS and GPS.
Yesterday and Today
Before we go into how GNSS works, let’s first read a little bit of history which I find quite interesting. Just like many other great inventions, the first idea of satellite-based positioning originated during the Cold War, when two American scientists realized that they could pinpoint Soviet Union satellite along its orbit because of the Doppler effect. To solve the inverse problem — pinpointing the user’s location given the satellite’s location, U.S. developed TRANSIT. It was successfully tested in 1960, providing a navigational fix about once per hour, and became the first satellite navigation system in the world. Recall the fact that nowadays cellphone location can be determined in seconds, you will know how much progress we’ve made so far.
In 1978, the first experimental GPS satellite was launched. It is designed to have a low accuracy of about 100 meters for civilian users, and high accuracy only for military uses. But later on, with improved design for GPS receivers, the actual accuracy was about 20 to 30 meters, which far exceeded the expectation of the U.S. government. To avoid providing such unexpected accuracy, a technique known as “Selective Availability”, or SA, was introduced to deliberately degrade the accuracy for non-military users.
However, SA is outsmarted by outstanding scientists with the invention of Differential GPS (DGPS), and actually, it not only solved the SA problem, but also led to better accuracy within 5 meters, and even centimeter lever accuracy for best cases. Partly because of this, SA was turned off in 2000.
In 2005, GPS began transmitting its second civilian signal for enhanced user performance, and with the development of Assisted-GPS, GPS becomes an integral part of our daily life. Cost of GPS receivers has dropped dramatically throughout the time — from first commercial GPS receiver with a cost over $100,000 and a weight of 53 pounds (24 kg), down to the chips that only costs a couple of dollars in our cellphones nowadays.
Plans
Well, that’s far enough about history and let’s look at how GNSS works. I plan to write a few articles to answer the following questions.
- How to determine the user’s position?
- How to capture GPS signal, and why can’t we decode military signals?
- How did the DGPS technique render Selective Availability ineffective?
- …
Although we have many GNSSs, the basic ideas are almost the same, thus I will use GPS as an example to illustrate the principles.
Overview of GPS Positioning
This article will answer the first question. To understand the basics only high school mathematics is needed, and it would be even better if you still remember linear regression. But if not it’s still okay, so keep reading.
First let’s look at what GPS is consisted of. The system is made up of three segments: the space segment, the control segment, and the user segment. The space segment consists of a constellation of 24 operating satellites that transmits one-way signals that give current GPS satellite position and time. The satellites fly in circular orbits at an altitude of about 20,200 km and with a period of 12 hours. The control segment maintains the health and status of the satellite constellation and uploads navigational data which give essential information about satellite position. The user segment consists of the GPS receiver equipment, which receives GPS signals to calculate the user’s position and time.
GPS Signal to Distance
After the user successfully decodes the information of GPS signals sent by each visible satellite, it will have
- The three-dimensional position of each satellite pˢ
- Time tˢ when GPS signal is transmitted
Satellites are way above the sky, thus when GPS signal is received, it would be delayed by some time Δt, determined by the range it traveled across space (i.e. the distance of satellite and user)
- Time tᵣ when GPS signal is received, which can be read from user clock
- Distance 𝑅=cΔt=𝑐(tᵣ−tˢ), where 𝑐 is the speed of light (GPS signal speed)
Trilateration
Now let’s consider a simple case when the user has received GPS signals from three satellites and calculated the distances between each satellite R₁, R₂, R₃ with regard to satellite s₁, s₂, s₃.
Then it’s able to solve the user’s three-dimensional position pᵣ=(xᵣ, yᵣ, zᵣ) because there are three knowns R₁, R₂, R₃, and three unknowns. The process of determining the location by measurements of distances is called trilateration.
If there is only one satellite, then the user’s location couldn’t be determined, but it should locate somewhere on the surface of the sphere centered at the satellite s₁ with radius R₁, as shown in the left plot below.
If two satellites, the user would then be somewhere on the surface of both spheres, which is the perimeter of the plane of intersection denoted by the shaded circle in the middle plot.
With three satellites, the user is at the intersection of the perimeter of the circle and the surface of the third sphere, as shown in the right plot. This third sphere intersects the shaded circle perimeter at two points. For a user on Earth’s surface, the lower point should be true position (the other one is mirrored up above the plane decided by the three satellites).
But That’s Not All
However, user clock time may not be accurate enough. Remember the distance is calculated by time delay multiplied by the speed of light 𝑐? If the user clock is not accurate, let’s say it has an offset of only 1 μs compared with true time, then an error of 300 m would be introduced when calculating the distance between user and satellite (suppose satellite time is accurate).
To solve this problem, we have to know the user clock offset with regard to true time (or satellite time).
Let’s introduce a little bit of mathematics for better understanding. Consider a simple trilateration case:
R₁=c(tᵣ−tˢ₁)=‖pᵣ−pˢ₁‖
R₂=c(tᵣ−tˢ₂)=‖pᵣ−pˢ₂‖
R₃=c(tᵣ−tˢ₃)=‖pᵣ−pˢ₃‖
where ‖pᵣ−pˢ ‖ denotes the distance between pᵣ and pˢ. Signal reception time tᵣ is known from the reading of current user clock time, satellite position pˢ₁, pˢ₂, and pˢ₃ can be obtained from GPS signal, thus there are only three unknowns pᵣ=(xᵣ, yᵣ, zᵣ).
Add one more variable, user clock offset dt, into user time and rewrite as
R=c(tᵣ+dt−tˢ)=‖pᵣ−pˢ‖
Since there are four unknowns instead of three, then why not add one more satellite?
R₁=c(tᵣ+dt−tˢ₁)=‖pᵣ−pˢ₁‖
R₂=c(tᵣ+dt−tˢ₂)=‖pᵣ−pˢ₂‖
R₃=c(tᵣ+dt−tˢ₃)=‖pᵣ−pˢ₃‖
R₄=c(tᵣ+dt−tˢ₄)=‖pᵣ−pˢ₄‖
Problem Solved!
A minimum of four satellites is needed to determine the user’s location.
So what if we have more satellites? Then
R₁=c(tᵣ+dt−tˢ₁)=‖pᵣ−pˢ₁‖
…
Rᵢ=c(tᵣ+dt−tˢᵢ)=‖pᵣ−pˢᵢ‖
can be formulated as a non-linear least square problem and solved by the Gauss-Newton algorithm.
But do we need more satellites? Aren’t four satellites enough?
Measurement Errors
It’s indeed a long journey for GPS signal to travel through space, thus there are a lot of errors when measuring the distance through time delay.
Atmospheric effects
- Errors would be introduced when traveling across the earth’s atmosphere.
- Ionospheric delay, caused by traveling across the ionized atmosphere, and is frequency-dependent
- Tropospheric delay caused by humidity at the troposphere
- Atmospheric pressure delay
Multipath effects
- GPS signals can be blocked by surrounding terrain: buildings, trees, bridges, etc.
- GPS signals can be reflected by surrounding terrain: buildings, canyon walls, hard ground, etc.
- When the direct signal is blocked but the reflected signal is received, then the calculated distance will be larger than true distance.
Satellite ephemeris and clock errors
- Satellite ephemeris is used to calculate the current and predicted position of each satellite in its orbit (pˢ comes from here).
- Satellite ephemeris may be up to two hours old, might lead to inaccurate satellite position if not updated in time.
- Satellites’ atomic clocks experience noise and clock drift errors, and might not be able to be fully corrected.
Signal arrival time measurement
- Typically the user can measure time delay to within about one percent of a bit pulse width, which approximately 10 nanoseconds, representing an error of about 3 meters.
Position Uncertainty
Distance measurements would not be perfect due to these errors. If we only have four measurements, which is the bare minimum required to determine the user’s location, errors would be fully consumed in the solution. If we have more measurements, errors could be partly consumed by residuals after the least square estimation, thus rendering a solution with less error and more confidence.
Take linear regression as an example:
- With enough measurements, we can fit a line best describing the linear model (indicated as a red line in plot).
- Residual is the difference of one measurement (blue dot) with its predicted value (red dot)
- If the fitted line is 100% accurate, then measurement error = residual
As we know more measurements tend to lead to a more accurate fitted result, and the same conclusion can be drawn for non-linear cases.
Dilution of Precision (DOP)
We can also view the position uncertainty in another way. Considering a two-dimensional case, depicted in the plot below.
- A: the user has measured the distance to two landmarks, so its location should be at the intersection of two circles with the measured radius.
- B: the measurements have some errors, thus true location will lie anywhere in the green area.
- C: the measurement errors are the same, but the error on their position has grown considerably due to the different arrangement of the landmarks.
From the example, we know the arrangement of satellites makes a difference when determining the user’s location. Basically we hope the satellites can spread evenly throughout the space.
Notice that for a user located at earth’s surface, the received satellite signals can not come below the earth’s horizon. This is why the position given by GPS will always have larger vertical errors compared with horizontal ones.
Pseudorange
Distance R calculated based on time delay is not the geometric range between user and satellite but contains measurement errors, thus technically it’s called pseudorange, formulated as
R=c[tᵣ(T₂)−tˢ(T₁)]
where tˢ(T₁) is signal transmission time given by satellite clock s; tᵣ(T₂) is signal reception time given by user clock r.
The equation can be re-written in another way, using geometric range ρˢᵣ between user and satellite plus measurement errors.
R=c[tᵣ(T₂)−tˢ(T₁)]
=c[(tᵣ+dtᵣ)−(tˢ+dtˢ)]+ε
=c(tᵣ−tˢ)+c(dtᵣ−dtˢ)+ε
=(ρᵣˢ+Iᵣˢ+Tᵣˢ)+c(dtᵣ−dtˢ)+ε
=ρᵣˢ+c(dtᵣ−dtˢ)+Iᵣˢ+Tᵣˢ+ε
where tˢ and tᵣ are the true time of satellite and user clock, dtˢ and dtᵣ are the clock offsets, ε is the non-atmospheric measurement error (e.g., multipath), Iᵣˢ and Tᵣˢ are atmospheric error caused by Ionosphere and Troposphere.
Some Takeaways
- The principle idea behind GPS localization is simple — trilateration.
- Due to clock offset, a minimum of four satellites is needed to determine the user’s location.
- Pseudorange, calculated based on a time delay, is the distance from the satellite to the user including measurement errors.
- Horizontal accuracy is better compared with vertical due to DOP.
In the next story, I will introduce the basics of GPS signal structure and how the user can decode the bit information.
Reference
- https://www.gps.gov/systems/gnss/
- https://www.gps.gov/systems/gps/
- https://en.wikipedia.org/wiki/Global_Positioning_System
- https://en.wikipedia.org/wiki/Differential_GPS
- Elliott D. Kaplan. Understanding GPS: Principles and Applications. Boston: Artech House, 1996.
- https://en.wikipedia.org/wiki/Error_analysis_for_the_Global_Positioning_System
- https://en.wikipedia.org/wiki/Dilution_of_precision_(navigation)
- https://www.iconfont.cn/