How does Indoor Positioning work?

Before addressing the issue of interior positioning, it is important to understand how outdoor positioning works. Basically, there are two ways to figure out one’s position. The first way is to compute a precise position at a given time; it’s called Absolute Positioning. Since Earth is a spherical object, the information is made of spherical coordinates composed of two angles called latitude and longitude and a distance called altitude.

For centuries, positioning was a difficult task for navigators; it took time and the calculated position was quite approximate. They needed to use a sextant to measure latitude (the angle between the horizon and the sun at noon) and a precise watch to determine longitude (the angular offset from the Greenwich meridian). Moreover, those techniques could only be used under good weather conditions and at certain times of day.

Since the 70’s for the military and the 80’s for the civilians a new technology called GPS (Global Positioning System) has appeared. The GPS uses a 32-satellite constellation for which the precise position is known. Each satellite embeds a very accurate and synchronized atomic clock. It broadcasts a unique radio wave signal that includes the clock timestamp. Any GPS compatible device on earth can simultaneously receive signals from several satellites. Since radio waves travel at known speed, the devices receive signals with different timestamps coming from several satellites. This way it is possible to compute distances between each satellite and the receiver.

Once the distances between the satellites and the device are defined, an algorithm called Trilateration is used to compute the current position. Trilateration allows position determination from 3 known distances on a plane or 4 known distances on a sphere. This algorithm is very important since it is used by almost every positioning technology whether indoors or outdoors. Trilateration should not be confused with Triangulation which is the algorithm used by surveyors to compute positions using angles instead of distances.

The second way to get one’s position consists in computing speed and direction from the last known point of departure; it is called relative positioning a.k.a. Dead Reckoning in the aviation industry. This technique usually relies on an equipment called Inertial Measurement Unit (IMU) that uses multiple gyroscopes and accelerometers to compute the covered distance. IMUs are used in most situations when a continuous precise position is needed: ships, aircrafts, spaces rockets, missiles, and cars.

How about indoor positioning?

Indoor positioning is a very complex matter since common outdoor technologies don’t work inside buildings. GPS waves are unable to properly reach receivers because of walls and roofs therefore resulting in an important accuracy loss that can reach several tens of meters. Moreover, the GPS is totally unable to figure out on which floor the receiver is located without mentioning that no signal at all is received underground. Classical dead reckoning is also nearly impossible to use indoors due to the size of inertial measurement unit (IMU). There is a direct link between the size of the IMU and its accuracy: the smaller the IMU, the poorer the accuracy. Since most of the indoor use cases involve people with smartphones, an alternative to classical IMUs that are too big to be embedded into smartphones, is strongly needed.

Indoor positioning technologies fit into the four main following categories: proximity, trilateration, fingerprinting and motion. Some of those technologies can be used alone but can also be combined to provide better accuracy.

Proximity positioning is either based on direct contact or on proximity between a receiver and a device. It is, most of the time, used on the client-side except for Wi-Fi that has server-side detection capabilities. Here are some possible technologies:

• QR Codes / NFC tags that can be read by smartphone cameras or NFC readers. QR Code / NFC stickers are then linked to a precise position in the building.
• Bluetooth Low Energy (BLE) devices a.k.a. beacons. A beacon sends a signal that can be read when the smartphone is located in the emission area. The more deployed beacons, the more accurate the position. User position is then associated to the location of the BLE device with the strongest signal.
• Visible Light Communication (VLC) devices a.k.a. Li-Fi. A led lamp sends an invisible signal that can be read either by smartphone cameras or by dedicated receivers. Since each lamp has a unique ID that can be read only right under the lamp, this makes it easy to provide an accurate position.
• Wi-Fi Access Points can be used to locate a smartphone or any kind of Wi-Fi aware device. The user position is determined the same way it would be it for BLE devices.
• Ultrasound devices are usually deployed on top of existing audio systems inside stores or shopping malls. Again, proximity location works the same way as BLE and Wi-Fi proximity positioning.

Trilateration positioning uses computed distances between several emitters and a receiver to compute position of the latter. Distances are determined either by RSSI or by ToF algorithms. RSSI stands for Relative received Signal Strength Indication. It allows distance calculation based on radio wave attenuation which follows the Inverse-Square Physical Law. Here, computing distances doesn’t involve complex calculus but the accuracy is poor due to the sensitivity to obstacles such as walls, doors or even people! Time-of-Flight a.k.a. ToF is a method that measures the distance between an emitter and a device and is based on the time difference between the emission of a signal and its return to the sender. Unlike RSSI, ToF involves roundtrip communication and complex signal processing that require dedicated chipsets. This comes with both a better accuracy and a higher cost. Here are technologies using trilateration:

• Bluetooth Low Energy (BLE) and Ultrasounds, albeit they are proximity technologies, they can still be used to provide trilateration-based positioning. Distances are computed on the client-side using RSSI.
• Wi-Fi can use trilateration either on the client-side (Android only) or on the server-side. The latter is far more accurate, but such location services are available only on premium Wi-Fi equipment (e.g. Cisco CMX, Cisco Meraki). Distances are usually computed using RSSI but an extension of the 802.11 standard will provide a ToF support in a near future.
• Ultra-Wide Band is another emerging technology which provides very accurate positions thanks to the use of ToF to compute distances between receiver and emitters. Nevertheless, this technology has several drawbacks: lack of standardization that results in no smartphone available and high cost.

Fingerprinting positioning technologies use signal measurements across buildings to compute one’s position. It is based on the assumption that for every position there is an almost unique signal that can be recorded. Then, it becomes possible to compare received signals with existing records to figure out current position. However, fingerprinting does have a flip side. First, it only works when in motion, and second, it requires stable signals over time. This technique can either be used alone or to improve the accuracy of other positioning technologies (usually those based on trilateration). Moreover, it is possible to simultaneously combine fingerprinting from multiple sources to increase accuracy. Here’s a list of technologies that can take advantage of fingerprinting:

• Bluetooth Low Energy (BLE) fingerprinting works very well because it can be performed on the client-side and because BLE signals prove to be stable over time.
• Wi-Fi fingerprinting works as well as BLE except it can’t be used on iOS devices due to Apple’s limitations. Which is why it is only used for Android smartphones and specific tracking devices used by intelligence and law enforcement agencies to bypass GPS jammers.
• Magnetic field fingerprinting uses unique variations of the earth magnetic field caused by steel parts inside building structures. It appears to work quite well but it proves unstable over time due to multiple factors (earth field variations, equipment moving, etc.).
• Photo fingerprinting is based on the image analysis of the building interior. It works well when there are significant differences between floors including furniture. It does not prove stable over time except when fingerprinting comes from high resolution permanent cameras able to frequently refresh records.

Motion positioning inside and outside buildings works on the same principles but with different technologies. Since it is not possible to use traditional IMUs, smartphone sensors are used to detect and quantify movements. Here is a list of sensors you can find in most smartphones: compass, accelerometers, barometers, pedometers. Algorithms such as Kalman filters process data that come from those sensors to compute relative movement. The issue with those techniques is poor accuracy resulting from small size sensors and cumulative errors. It goes without saying that the level of accuracy is far lower this way than it would be with IMUs. As for fingerprinting, motion positioning is best used to increase trilateration positioning rather than as a stand-alone technology.

Conclusion

Indoor positioning is a very complex matter that can’t be solved with a unique technology the way GPS does outdoors. The best providers rely on an approach called Sensor Fusion that is based on the use of a combination of technologies to provide the best possible accuracy. Most of the time they use Trilateration to obtain an absolute position, sometimes coupled with Fingerprinting to increase accuracy. Then, they use Motion positioning to move the blue dot until they have enough radio signal variation to compute another absolute position. This way, they can spare smartphone batteries since aggressively scanning radio signals (whether BLE or Wi-Fi) comes with a high energy cost. Proximity positioning is both a low-cost and a low-tech way of getting a position. Even if it’s very basic, it can be sufficient depending on the context because not every project really needs high accuracy; without mentioning the budget you need to get it. Finally, the current trend in indoor positioning is to reuse existing infrastructures instead of deploying new ones which limits overall costs. For instance, Wi-Fi access points can be used both to provide Internet Access and Indoor Positioning especially since most of them now have BLE chipsets within. It goes the same with Li-Fi lamps that can embed BLE chipsets and various sensors alike.

Key points to remember

• Positioning technologies either provide an absolute or relative position.
• Indoors, the GPS technology doesn’t work properly due to inadequate accuracy.
• Most providers rely on signal attenuation along with trilateration to compute one’s position.
• Fingerprinting and motion positioning are best used to increase accuracy of other indoor positioning systems.
• The best providers rely on sensor fusion meaning they use several technologies to provide better accuracy.

Originally published at www.mapwize.io.