Showcasing Kent, Ohio and the surrounding
Northeastern Ohio Region.

Computational Thinking

Time For Location, Location, Location

Paul Wang, Computational Thinking 8, A World of 1's and 0's. Photo at Kent Free Library Kent, Ohio, by photographer Matt Keffer.

Visit Paul's website
The book From Computing to
Computational Thinking

can be ordered at: computize.org

Paul Wang From Computing to Computational Thinking.

In the information age, a wonderful thing is the automatic navigation for automobile driving. This much appreciated capability results from the convergence of advanced computing and space technologies. The core technology is the Global Navigation Satellite System (GNSS) that can precisely fix positions anywhere on/near Earth. In fact GNSS is a global infrastructure that enables applications in many areas, making our economies more efficient and effective.

At present, there are four GNSSs: the US GPS (Global Positioning System), the EU Galileo, the Russian GLONASS, and the Chinese BeiDou.

A GNSS has three main components: a space component (a constellation of orbiting satellites), a control component (ground-based devices for system monitor and control), a user/application component (any device to receive the satellite signals for some purpose).

As part of our Computational Thinking blog (computize.org/ctblog), this post focuses on a basic understanding of satellite-based positioning, how it works and its important applications.

GPS for cars

These days in America, GPS is widely used for road navigation. With it you simply follow turn-by-turn directions to drive to any desired destination, for the first time or otherwise. Compared to looking for street signs, highway exits, and door numbers, GPS navigation makes life so much easier and safer, especially when driving at night or in an unfamiliar area. Some cars come with built-in GPS navigation. Otherwise, you can use a portable device which is dedicated to GPS or just a smartphone free navigation apps available). Bring it with you so you can get directions while driving, biking and walking.

Enabling technologies for GPS navigation include the following.

• The GPS, a US owned and operated GNSS.

• A receiver (user’s device) to capture and process GPS satellite signals. The received data can be used to determine the receiver’s current location, given in latitude, longitude, and elevation for example.

• A software application to place any given current position on a road map for directions and navigation. The map includes road/street names, traffic regulations (such as one-way streets and speed limits), addresses of houses/buildings, distances, and other data for the target travel area.

Now let’s see how locations are determined based on satellite signals from GPS or any other GNSS. The principles are the same.

How Satellite Positioning Works

A GNSS consists of many, often 30 or so, individual satellites, orbiting Earth in such a pattern that, at any moment, at least four of them are visible from virtually any point on the globe.

Think of these satellites as lighthouses in the sky that can help you find your own location and navigate accordingly. Surely, you need a device able to receive the satellite signals.

To make our descriptions more specific, we will use the US GPS system as an example.

According to Wikipedia “GPS satellites fly in medium Earth orbit at an altitude of approximately 20,200 Kilometers. Each satellite circles Earth twice a day. The satellites in the GPS constellation are arranged so that users can view at least four satellites from virtually any point on the planet.” A GPS satellite body is roughly a 2.5-meter cube and weighs like a pick up truck.

Here is an animated picture from the US Jet Propulsion Laboratory (JPL).

The GPS satellite constellation

Each GPS satellite continuously broadcast radio (microwave) signals that carry data indicating the satellite’s clock time and precise position in space. The precise position of each satellite is determined by ground control which tracks and maintains all the orbiting satellites. The signal data enable any receiving device (on/near Earth) to determine the receiver’s range (distance) from the particular satellite. It is important that all satellites transmit their data signals in unison, at precisely synchronized times. Remember, all the satellites and, most likely, the receiver are moving.

Let’s see how a receiver can determine its current position using four satellites within view at once. The geometric method is called trilateration. It is easier if we talk about one of these four satellites at a time.

First of all, with signal from just one satellite, a receiver can determine the satellite’s distance from the receiver as follows.

We know light and radio signals travel at a constant speed C = 186000 miles per second or C = 299792458 meters per second. Let the signal travel time from the satellite to the receiver be δ seconds where δ =(signal arriving receiver clock time)−(signal sending satellite synchronized time). With GPS, typical values for δ is about 0.06738 seconds. Then, R = (C × δ) is the distance of the satellite to the receiver.

In other words, the receiver, on Earth or in space, is somewhere on the surface of a sphere S1 with radius R centered at the satellite location the instant when the data signal was sent.

Similarly, a second sphere S2 centered at the second satellite used is found. Now the receiver has to be on the intersection of the surfaces of S1 and S2. The intersection is a 2D circle as illustrated in the following diagram. Let’s designate this circular intersection C12, red line in Fig.1.

Fig. 1: Surface Intersection of Two Spheres

A third satellite adds sphere S3. The circular intersection of S1 and S3 is another circle C13 on which the receiver must be located. The circles C12 and C13 intersect at two points (the two yellow dots) as shown below.

Fig. 2: Surface Intersection of Three Spheres

You guessed it. Adding a fourth satellite narrows it down to a single point. That’s the position of the receiver. Location found, all faster than a few blinks of the eye! In fact if we assume the receiver is on the surface of Earth, then we can often pick one of the two points without needing a fourth satellite. But, to get precise elevation information and other finer time/position adjustments we want to use a 4th satellite.

Trilateration With Four Satellites

Common Sense View

Perhaps mathematics or geometry is not your favorite subject, that is understandable. So let’s see if we can put the GPS positioning method in layman’s terms—cutting oranges.

Let’s imagine a large orange as a sphere. Use a sharp flat knife and, with one straight cut, slice the orange into two pieces, a large part and a much smaller part. Notice the exposed cut surfaces will be flat and circular. Let’s imagine a satellite at the center of this orange and the signal receiver on the skin of the cut-off part before you sliced it off. Similarly, imagine, at the same time, the receiver on another orange centered at another satellite.

Now Fig. 1 earlier makes sense intuitively. The receiver must be on the circular curve common to these two oranges. Each orange represents a sphere centered at a GPS satellite.

Now look at Fig. 2 again, you will see two intersecting flat circles meeting at two points, candidates for the receiver’s position.

Precise Timing

An atomic clock can tell time to within three nanoseconds. A nanosecond is 10−9 second. Each GPS satellite uses more than one atomic clock, resulting in very precise time data in the GPS signals. Using such data, any GPS receiver can determine time to within 100 nanoseconds. Position accuracy depends on the receiver. Most receivers are correct to within 10 to 20 meters (33 to 66 feet).

Multiple receivers in close proximity can work together to increase the accuracy to within one centimeter.

Of course, GPS and other GNSS systems all have secret military aspects using encrypted signals and providing a degree of accuracy not available in civilian use. An example is guiding cruise missiles.

Location, Location, Location

The importance of location is not only in real estate. It affects many things. The ability to precisely know your location becomes important in many application areas. And this ability has been brought to us by a convergence of modern technologies—space, atomic clocks, satellites, computers, computing, data processing, networking, and smartphones, just to name some.

A GNSS has these five major user application areas:

Location: Determining positions on Earth or in Space

Navigation: Guiding users or objects to move from one location to another location

Tracking: Monitoring and managing moving objects

Mapping: Helping to make various types of maps

Precise timing: Keeping time using GNSS signals

According to gps.gov

“GPS boosts productivity across a wide swath of the economy, to include farming, construction, mining, surveying, package delivery, and logistical supply chain management. Major communications networks, banking systems, financial markets, and power grids depend heavily on GPS for precise time synchronization. Some wireless services cannot operate without it.”

Let’s shift our attention to another GNSS, the BeiDou-3 which became operational globally in June 2020.

BeiDou Navigation Satellite System (北斗卫星导航系统)

In 2015, China begun to launch satellites to build BDS-3 (third-generation BeiDou). It became the latest GNSS. The 35th and final satellite was launched into orbit on 23 June 2020, making BDS-3 fully operational.

BeiDou-3 currently offers more satellites in orbit than any other GNSS. BDS-3 offers all-weather and all-day positioning, navigation, timing, and search-and-rescue (SAR) services to its users.

The name 北斗 is Chinese for the Big Dipper which is easy to spot in the northern sky and can be used to locate the North Star. What an appropriate name for a modern GNSS from China.

The BeiDou-3 Satellite Constellation

Here are BeiDou-3’s main features.

• The BeiDou-3 constellation includes 35 satellites–five in geostationary orbit (GEO), three in inclined geostationary orbit (IGSO), and the remaining 27 in the medium Earth orbit (MEO). The US GPS constellation however, uses 6 equally spaced (by 60 degrees) MEO orbits each with 4 satellites.

• BDS-3 satellites broadcast signals in five frequencies, namely B1I, B3I, B1C, B2a, and B2b. The B1C, B2a, and B2b are centered at 1575.420, 1176.450, and 1207.140 MHz, respectively. This helps the system to become more accurate. GPS satellite signals use only two to three frequencies.

• The BeiDou-3 is unique in supporting two-way communication with users, a capability not available in any other GNSS. BeiDou-compatible receiver devices can transmit data back to the satellites. This allows BeiDou-3 to know the current position of the user. The BDS-3 also uses inter-satellite links to help time synchronization and to enhance message communication services (MCS). BeiDou-3 MCS has a regional (Asia-Pacific region) single message length of 116,800 bits (1,200 Chinese characters) and can transmit text, voice and pictures. The global communication single message length is 560 bits.

Via Beidou-3 we can send data and messages anytime anywhere without depending on WiFi, Cell, or other signals. Thus, the search-and-rescue feature of BeiDou-3 brings the great global 911 or universal 120 concept a big step toward reality.

Here is a question: how do you tell if your smartphone can use BeiDou-3 navigation. Of course you can consult the specs of your phone. Or you can use a GPS testing app to see what GNSS signals you are getting. If you receive BeiDou signals then you can navigate by installing freely available BeiDou-3 navigation apps. In civilian use, any positioning or navigation app you choose on your phone should automatically pick the best GNSS signals to use. Increasingly, smartphones such as the Huawei Mate 20, Google Pixel 4, Samsung S10, have dual-frequency GNSS chipsets. True multi-GNSS phones can’t be too far off.

Summary

A GNSS uses time to determine location. Satellites serve as lighthouses in the sky with atomic clocks to deduce accurate locations of objects on or near Earth. A receiver requires signals from four GNSS satellites at once to determine its own location via trilateration. Currently, there are four GNSSs: GPS, Galileo, GLONASS, and BeiDou-3.

A GNSS is a global infrastructure that is revolutionary in human history. It has many uses and makes our lives easier and work more efficient in many ways.

The ability to obtain precise time and location information at any point on or near Earth is unprecedented. It offers an automatic 3D + time coordinate system for the entire globe. Isn't that wonderful? And that should directly change the way we think about the world and how to do things in it!

Someday in the not too distant future, we will be so heavily dependent that a GNSS failure would be catastrophic.

To find other interesting and illuminating CT articles, please visit my Computational Thinking blog (computize.org/ctblog) at any time.

ABOUT PAUL
A Ph.D. and faculty member from MIT, Paul Wang (王 士 弘) became a Computer Science professor (Kent State University) in 1981, and served as a Director at the Institute for Computational Mathematics at Kent from 1986 to 2011. He retired in 2012 and is now professor emeritus at Kent State University.

Paul is a leading expert in Symbolic and Algebraic Computation (SAC). He has conducted over forty research projects funded by government and industry, authored many well-regarded Computer Science textbooks, most also translated into foreign languages, and released many software tools. He received the Ohio Governor's Award for University Faculty Entrepreneurship (2001). Paul supervised 14 Ph.D. and over 26 Master-degree students.

His Ph.D. dissertation, advised by Joel Moses, was on Evaluation of Definite Integrals by Symbolic Manipulation. Paul's main research interests include Symbolic and Algebraic Computation (SAC), polynomial factoring and GCD algorithms, automatic code generation, Internet Accessible Mathematical Computation (IAMC), enabling technologies for and classroom delivery of Web-based Mathematics Education (WME), as well as parallel and distributed SAC. Paul has made significant contributions to many parts of the MAXIMA computer algebra system. See these online demos for an experience with MAXIMA.

Paul continues to work jointly with others nationally and internationally in computer science teaching and research, write textbooks, IT consult as sofpower.com, and manage his Web development business webtong.com

aroundkent is a local, regional website containing relevant information about Kent, Ohio and the surrounding area, including all of Northeast Ohio. Our focus is on art, music, food, family and everything in-between. Our content is sent to us by local professionals so it's both accurate and updated regularly. Our goal is simple: to showcase the amazing people, places and things in and around Kent, Ohio. We are also designers and photographers working in webflow and using a Nikon D810 camera.