Unraveling the Mathematical Approaches behind the Indoor Navigation App: Dijkstra’s Algorithm, Trilateration, and Trigonometry

Everything related to technology is just the tip of the iceberg where mathematics hides

Mathematical Approaches behind the Indoor Navigation App

Have you ever gotten lost when driving to a new place? I bet you would grab your smartphone in your hand and open Google Maps, Apple Maps, Waze, or other navigation apps. They will give you the best route recommendation, and then you’ll follow it. Poof! You arrive safely. It is really simple, yet it solves your problem.

However, have you ever encountered such a condition in an indoor setting? For instance, inside a huge museum with many artworks and multiple exit gates in every corner, or in the middle of a hectic public transportation station during rush hour when you don’t have any opportunities to ask the staff. What about the same concept of navigating that is brought into indoor settings? Imagine a mobile app that could navigate the best way for you to find your destination inside a building. Some of you may wonder what the app looks like. It might have a floorplan of the building with a line that represents the best route to reach your destination. The app would guide you on when and where to go straight, turn right, or turn left.

It sounds simple in a nutshell, but how does it work? What are the mathematical approaches behind the indoor navigation app? In my previous post, I tried to simplify a complex thing. However, in this post, I would like to examine the simple tool more scientifically, based on my exploration over the past two weeks.

In a brief explanation, the indoor navigation app implements Dijkstra’s algorithm, trilateration, and trigonometry. This combination of mathematical techniques is one of the proofs that informatics incorporates mathematical approaches at its core. Everything related to technology is just the tip of the iceberg where mathematics hides. Mathematics is closely connected with human life, playing a significant role in various aspects of our technological advancements.

iBeacon

A beacon is a wireless device used to broadcast radio signals to nearby devices. It relies on Bluetooth Low Energy (BLE) radio to transmit signals. Nowadays, two beacon types dominate the market: Apple iBeacon and Google Eddystone. In this article, we’re going to focus on the iBeacon. Although the terms iBeacon and beacon are widely interchanged, they are essentially dissimilar. The primary difference is that iBeacon leverages Apple’s proprietary technology for transmitting signals. It was integrated into iOS and allowed an iPad or iPhone to play dual roles, as a transmitter and receiver.

iBeacon as Transmitter and Receiver

Why does a beacon use Bluetooth Low Energy rather than a Bluetooth Classic radio? Bluetooth Low Energy remains in sleep mode unless a connection is initiated. The actual connection time only lasts for a few milliseconds, which is the time it takes to transfer a small amount of data. Thus, it provides a better, low-battery option for applications that only periodically exchange data.

Bluetooth Technology Overview

Why don’t we use GPS instead? GPS (Global Positioning System) doesn’t perform well in indoor settings. As cited from the Apple documentation, GPS shows its best performance when a device is in the open outdoors with an unobstructed line of sight to the orbiting GPS satellites. Location accuracy is represented by a blue circle surrounding the current location indicator. The larger the circle, the lower the accuracy.

GPS Performance in Indoor Settings

What differentiates an iBeacon from another? As cited from the Apple documentation, every iBeacon has a UUID, major, and minor as its unique identifier.

• UUID distinguishes iBeacons in our network from all other iBeacons in networks outside our control.
• Major defines a sub-region within a larger region defined by the UUID.
• Minor defines a further subdivision of the region.

These identifiers are only applied to iBeacons, as Eddystone’s unique identifier is made up of Namespace and Instance.

UUID, Major, and Minor

How is the distance to a device estimated by an iBeacon? An iBeacon transmits BLE radio at a constant rate. Other devices can detect this radio signal, measure their Received Signal Strength Indication (RSSI), and convert it into distance in meters. The formula for RSSI-based distance calculation, as cited from *RSSI Based Bluetooth Low Energy Indoor Positioning*, is:

where:

RSSI = obtained RSSI value

n = attenuation constant that takes a value between 2 and 4

d = distance between the transmitter and receiver

Tx = transmission strength at a distance of one meter

Then, we could obtain the distance between the transmitter and receiver if we knew the RSSI value.

Let’s assume that the RSSI value is -61, and the attenuation constant is 2.4. The RSSI value at one meter is -44. The calculation of the distance between the transmitter and receiver would be:

Thus, the distance between the iBeacon and the device is 5.1 meters.

What is the optimal distance for iBeacon placement in an indoor setting? As cited from the Apple documentation, iOS 7 introduces a new set of APIs for determining the approximate proximity to a device using iBeacon technology, a process known as “ranging”. The four proximity states are Immediate, Near, Far, and Unknown.

Ranging

On average, an iBeacon could transmit up to 70 meters. However, it is expected to be accurate within an average radius of 3 to 5 meters. iBeacon works optimally in uniformly distributed installations, and minimizing the space between iBeacons would increase the accuracy.

• If there is a 10-meter spacing between the iBeacons, it can offer an average accuracy of 2 meters.
• If there is a 15-meter spacing between the iBeacons, it can offer an average accuracy of 4 meters.

For example, there is a floorplan shown below.

Floorplan

A, B, C, D, E, F, and G refer to the iBeacon locations, while U refers to the user’s current location. Assume that the user would like to reach E from their current location. In this case, the iBeacon placements might not be optimal, as we were more focused on the calculation process. Here are the steps to navigate a user to an ending point:

• Map all iBeacon locations in the imaginary two-dimensional space.
• Look for the shortest path to reach the endpoint from the starting point using Dijkstra’s algorithm.
• Calculate the user’s current location using Trilateration.
• Calculate the user’s direction using Trigonometry.
• Show the recommended direction to the user based on the calculation.

To make it easier in the next step, we need to map the user and all iBeacons’ positions in the imaginary two-dimensional space and assign a coordinate value to each of them. The mapping process is based on the distance calculation between one point and another.

Mapping in Two-dimensional Space

Dijkstra’s Algorithm

First things first, we need to determine the shortest path to reach an endpoint using Dijkstra’s algorithm, which operates on a weighted graph. In a graph, Vertices represent real-life objects (in this case, the user and iBeacons), and Edges connect two vertices. A graph is said to be weighted if each edge is assigned a ‘weight’, which, in this case, denotes the distance.

Here are the concepts of Dijkstra’s algorithm:

1. Begin at a vertex as the starting point and examine the adjacent vertices to find the shortest path to reach the endpoint.
2. Keep records of the currently known shortest paths from the starting point to each vertex and update these values if there is any shorter path.
3. Once the shortest path between the starting point and another vertex has been retrieved, that vertex is marked as ‘visited’ and included in the records.
4. Repeat these steps until the endpoint has been included in the records with the shortest possible path to reach each visited vertex.

Assuming that the user starts from U and aims to reach E, the steps are shown below:

Step 1: Start with a weighted graph.

Step 1

Step 2: Start from U as the starting vertex and assign infinity path values to all other vertices.

Step 2

Step 3: Update the path values of adjacent vertices to U.

Step 3

Step 4: Pick the vertex with the minimum path value. However, A (5) is a dead end and doesn’t lead to the endpoint. Thus, we need to pick vertex C (10) and update the path values of its adjacent vertices.

Step 4

Step 5: Pick the vertex with the minimum path value and avoid updating path values of already visited vertices. Thus, we pick vertex B (13) and update the path values of its adjacent vertices.

Step 5

Step 6: Pick the vertex with the minimum path value and avoid updating path values of already visited vertices. Thus, we pick vertex D (18) and update the path values of its adjacent vertices.

Step 6

Step 7: We have reached the endpoint, vertex E (28). However, it is not the vertex with the minimum path value. Vertex F (23) has a lower value than vertex E (28). Thus, we need to pick vertex F to check if there are any possibilities to reach vertex E with a lesser path value.

Step 7

Step 8: Vertex E (28) is less than vertex G (33), and it is the endpoint. Thus, we have already found the shortest path from vertex U to E, which is U-B-D-E, with path values = 13 + 5 + 10 = 28.

Step 8

Trilateration

By using at least three iBeacon distances, we can compute the exact position of the user through trilateration. Since we know the positions of the user and the iBeacons, we can also calculate the user’s direction.

Trilateration Concept

Trilateration is the process of determining the coordinates of a point based on its distance from at least three known coordinates.

Are trilateration and triangulation the same thing? No, they are totally different. Triangulation and trilateration are two methods used in land surveying to determine horizontal measurements. The basic difference between triangulation and trilateration is that triangulation involves the measurement of angles, while trilateration involves the measurement of length.

What method does GPS utilize? GPS utilizes trilateration to determine the user’s current location, not triangulation. GPS satellites send out time information (based on atomic clocks) and their coordinates. By measuring the TOA (Time of Arrival) of those signals, a GPS receiver in our phone calculates its distance from three or more GPS satellites to figure out where we are.

Trilateration

Let’s consider finding the coordinates of point B, while already knowing the coordinates of points P1, P2, and P3. By measuring r1, the distance between B and P1, this places the coordinates of B on the circumference of a circle with radius r1. Then, by measuring r2, the distance between B and P2, the exact coordinates of point B can be found at either A or B, which represents the intersection points of the two circles formed by r1 and r2. Lastly, when the distance r3 is measured (the distance between B and P3), the coordinates of B are determined as the intersection of the three circles.

The equations for the three circles are as follows.

By applying some algebra calculations to these three equations, we could got the value of (x,y) which is the coordinates of B.

In this case, we will narrow down our focus to the user (U) and three iBeacons placed on A, B, and C. Our objective is to determine the coordinates of the user (U). Once we have obtained the user’s coordinates, we can apply the same concept in the next steps.

Trilateration Case

For A(0,6): x1 = 0, y1 = 6, r1 = 5

For B(8,14): x2 = 8, y2 = 14, r2 = 13

For C(9,-6): x3 = 9, y3 = -6, r3 = 10

Until this step, we’ve got 3 equations as follows:

Then, subtract the second equation from the first:

Then, subtract the third equation from the second:

Then, subtract the fifth equation from the fourth:

After that, substitute value of to the fifth equation:

Thus, the coordinates of U(x,y) = (3,2).

Trigonometry

The next step after determining the position of the user is to ascertain their direction, which could be either going straight, turning left, or turning right. However, how could we determine the user’s direction if we didn’t know where they are heading to? They might be moving towards the iBeacon, going in the opposite direction, or any other direction. To solve this problem, we will use the concept of trigonometry. Our main focus will be on the angle, and we will use a compass to measure their angle, which allows us to determine the correct direction.

Does the Compass app still work on the iPhone when GPS is turned off? As cited from the iPhone User Guide, the Compass app on the iPhone shows information about bearings, coordinates, and elevation. It does use GPS to track the user’s current location. However, it still works even when the GPS is turned off. It just wouldn’t be able to show longitude, latitude, and location anymore. Thus, even when the GPS doesn’t work in indoor settings, it still functions as a compass.

In the case of trilateration, we have three iBeacons, but our focus is solely on one labeled as B, positioned at coordinates (8,14). As in the Dijkstra’s algorithm, we need to visit vertex B to reach vertex E with the shortest path. We can apply the same concept in the next steps.

Trigonometry Case

The actual angle is 67 degrees, and the user must rotate themselves to the right and go straight. However, some possible scenarios might occur.

Scenario 1: If the user is already heading north (0 degree on the compass), and the iBeacon is placed on their right side, the user must rotate themselves to the right side and go straight.

Scenario 1

Scenario 2: If the user is heading south (180 degrees on the compass), and the iBeacon is placed on their left side, they have an angle of 247 degrees towards the iBeacon, which lies in the third quadrant. In this scenario, the user must rotate themselves to the rear left side and then go straight.

Scenario 2

Limitation

The discussed topics above were assumed to happen in the ideal conditions where the RSSI was stable. As cited from the Apple documentation, RSSI is very vulnerable to any attenuator, such as physical materials and the human body. Further calculation is needed to filter the fluctuated RSSI values to obtain an accurate one.

Attenuator

© 2023 Nadya Tyandra. All Rights Reserved.