Indoor navigation in large buildings with Beacon technology
Tags: beacons, beacon, tech, technology
Published: 2017-08-07 13:09:14

---
layout: post
title: "Indoor navigation in large buildings with Beacon technology"
published: true
tags: beacons, beacon, tech, technology
cover_image: "https://thepracticaldev.s3.amazonaws.com/i/8zzqajq827gqktt2d5tu.jpg"
---

<b>1). What is Beacon technology?</b>
 
</span><a href="https://en.wikipedia.org/wiki/Beacon"><span style="font-weight: 400;">Beacon</span></a><span style="font-weight: 400;"> is a protocol developed by Apple and introduced at the WWDC in 2013. It is based on Bluetooth low energy proximity sensing by transmitting a universally unique identifier, picked up by a compatible app or operating system.

The identifier and several bytes sent with it can be used to determine the device’s physical location, track customer’s’ location, or trigger a location-based action on the device such as a check-in on social media or a push notification.

 

<b>2). How can we use Beacon technology for indoor navigation?</b>
 
Depending on the application we may need different accuracy of the estimated position. For indoor navigation in a big shopping center or airport, it would be enough to find a room where a user is located, while some other apps would need centimeter‑level accuracy.

So, a first case is pretty straight-forward. It would be enough to have only one beacon for each room. We will just need to find the beacon with the highest `proximity` value and in most cases, it will define a user’s location.

Though there may be a false result when the user is relatively far from the beacon in a large room, but is close to the wall, where another beacon is located. 

In this case, the distance causes more attenuation of the true beacon’s signal, then obstacle does to the false one. To avoid it we can just put several beacons in relatively big rooms.

When high-level accuracy is needed, we can put more beacons in each room and solve and estimate user’s location by triangulating its position against known beacons’ locations. This is very similar to one of the ways of mobile network geolocation, where positions of cell towers are used instead.

Here is a simplified idea of the algorithm. Distance to each tower defines a circle of possible user locations. The intersection of two circles determines only two possible locations and a third circle defines one of them. 

A real-world case is a bit more complex since due to measurement error we have to deal with rings of some width instead of ideal circles.

 
<b>In order to solve triangulation problem we need to:</b>

- Place at least three beacons in each room, ideally without obstacles.
- Estimate the distance for each beacon in range.
 
Unfortunately, iOS SDK doesn’t provide any estimation of the physical distance to the detected beacon. All we can use is rssi (signal strength), accuracy (one sigma horizontal accuracy in meters) and proximity, which may have one of the following values:
 

<b>Unknown:</b>  The proximity of the beacon could not be determined.

<b>Immediate:</b> The beacon is in the user’s immediate vicinity.

<b>Near:</b> The beacon is relatively close to the user.

<b>Far:</b> The beacon is far away.

 
But can we roughly estimate the distance using rssi value? It depends on the distance and obstacles between a mobile device and Beacon itself. Let’s imagine an ideal world without obstacles for a moment.

We can measure rssi values at different distances and then find the best fit curve to match the data points. This dependency may then be used to estimate distance for a particular rssi value.

You may wonder how does the environment affect the rssi values we get? Well, if the user is inside a steel building, there may be internal reflections, which will cause a slower fading of the signal depending on a distance. 

On the contrary, if there is a water (or human body) between transmitter and mobile device then the signal will be attenuated.

So, in the real world, we will end up with equations based on distances to beacons, which don’t necessarily have a mathematical solution. This problem may be partially solved by increasing the number of beacons in each room and picking the most accurate of them based on `accuracy` property of CLBeacon object.

 

<b>3). Technology limitations and recommendations</b>
 
As described above, a distance estimation highly depends on the environment, primarily on the obstacles between device and transmitters. In order to minimize these effects and make results more accurate, we should follow the following recommendations:

Make sure that at least three beacons are available in a line of sight for each point in a room. This means that we will need more than three beacons for non-convex rooms.

Place beacons to the ceiling, so that signal doesn’t interfere with furniture and other obstacles

Calibrate each type of beacons separately. Signal strength also depends on the model
 

<b>4). Pathfinding</b>
 
Ok, we have estimated user’s location, what’s next? How can we guide him/her from point A to point B? In other words, how to solve pathfinding problem?

In general case, this problem is defined on a weighted graph, but for the sake of simplicity let’s assume that we have a map defined by passable and non-passable squares.


Learn more about </span><a href="https://smartym.pro/blog/inside-navigation-in-large-buildings-with-ibeacon-technology/"><span style="font-weight: 400;">ensuring effective indoor mapping in large buildings</span></a><span style="font-weight: 400;">.