Cell Phone Trilateration Algorithm

Mobile phone tracking is a process for identifying the location of a mobile phone, whether stationary or moving. Localisation may occur either via multilateration of radio signals between several cell towers and the phone, or simply via GPS.

Mobile positioning is used by telecommunications companies to approximate the location of a mobile phone and enables to offer location-based services and/or information to the mobile user.

Cell Phone Trilateration / Multilateration

Cell tower trilateration (sometimes referred as triangulation) is used to identify the location of the phone. A cell phone constantly emits roaming radio signals that may be picked up by three or more cell towers enabling the triangulation to work. Trilateration calculations estimate the coordinates of a mobile device using the coordinates (longitude,latitude) of nearby cell towers as well as the estimated distance of the device from the cell towers (e.g. either based on signal strength or by measuring the time delay that a signal takes to return back to the towers from the phone).

In this challenge we will investigate the math equations used in trilateration calculations. We will simplify the process by using a 2D model of the problem based on (x,y) coordinates (as an alternative to longitude/latitude coordinates).

On the diagram above, each circle represents all the possible locations of a mobile phone at a given distance (radius) of a cell tower. The aim of a trilateration algorithm is to calculate the (x,y) coordinates of the intersection point of the three circles. Each circle is defined by the coordinates of its center e.g. (x₁,y₁) and its radius e.g. r₁.

The following steps will help us calculate these (x,y) coordinates:

Step 1
The three equations for the three circles are as follows:

Step 2:
We can expand out the squares in each of these three equations:

Step 3:
Now let’s subtract the second equation from the first:

Likewise, we can now subtract the third equation from the second:

Step 4:
Let’s rewrite these two equations using A, B, C, D, E, F values. This would result in the following system of 2 equations:

Step 5:
The solution of this system is:

Python Implementation

Now that we understand the math needed in a trilateration calculation, let’s implement these equations in a Python algorithm using a function that will take 9 parameters (x₁,y₁r₁,x₂,y₂r₂,x₃,y₃r₃) and return the (x,y) coordinates of the intersection point of the three circles.

Your task is to complete the code of the trackPhone() function that we have started for you:

GPS Positioning

Note that GPS satnav systems use a similar approach but need to be more accurate by:

• Estimating the distance between a GPS satnav device and at least three GPS satellites. This is done by measuring the time delay that a signal takes to be sent from the satellite to the GPS satnav, and converting this time delay into a distance,
• Using more advanced multilateration formulas based on a 3D model rather than a 2D model.