Positioning terms and topic history
To help you understand how in-door positioning works, we would love to give you a quick tour to the history of a topic as well as define some basic terms and red flags. Before addressing the issue of interior positioning, it is important to understand how outdoor positioning works. Basically, there are two ways to figure out the position: to compute a precise position at a given time (it’s called Absolute Positioning) and another approach 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).
Absolute Positioning explained: 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.
Relative Position (a.k.a. Dead Reckoning in the aviation industry) explained: 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, space 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 with 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 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 the 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 the 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 the 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.
Nowadays: Blue Dot jumping and a way to fix it
In-door positioning and wayfinding nowadays become more and more popular for practical usage in malls, hospitals, airports and other public buildings, storage and campus building applications. Several companies working on in-door location SDKs development and offering different integration models for client apps. All of them facing similar problems, f.i. so-called “Blue Dot jumping”. Blue Dot is a common industry term for in-door map marker showing current user location. Jumping is an effect of location marker “jumps” to the wrong/correct location, mostly happening if only BLE-based location calculation is used: jumping happens due to unstable signal emission and doesn’t correlate significantly with the location algorithm (three becons triangulation, most signal strength relation etc,) used . There are several techniques used for eliminating this effect. One if it is based on device sensors usage for algorithms similar to out-door ‘’Dead Reckoning". Idea is user location, obtained using BLE beacons, “corrected” with device location changing vector, obtained from sensors. Pretty impressive demonstration of a user motion tracking using sensors only can be seen in Navisens product. Our team incorporates knowledge on how to prevent Blue Dot Jumping with the technique inspired by Navisens and some smoothing techniques.
Promising results for Blue Dot Jumping fixing also obtained using Machine Learning techniques with Filter Partitioning Machine Learning Classifier (FPMLC). We recently concentrated on studying these techniques and opportunities they are open for the field.
Future of in-door location
Apple announced the U1 chip with improved UWB on board for iPhone 11 and iPhone 11 Pro. UWB is a short-range, wireless communication protocol that – like Bluetooth or Wi-Fi – uses radio waves. But it differs substantially in that it operates at a very high frequency. As its name denotes, it also uses a wide spectrum of several GHz. One way to think of it is as a radar that can continuously scan an entire room and precisely lock onto an object like a laser beam to discover its location and communicate data.
In the early 2000s, UWB saw limited use in military radars and covert communications and was used briefly as a form of medical imaging, such as remote heart monitoring systems. Its adoption lagged until recently when commercial interests began exploring potential uses.
Currently UWB systems can provide +/- 30cm accurate indoor positioning with positioning updates every 50ms. A huge improvement compared with the accuracy delivered by WiFi or Bluetooth based systems.
List of Android supporting UWB similarly to recent iPhones 11 still to be clarified, but what we can be sure is top vendors such as Samsung, Huawei, Xiaomi and others will follow Apple's direction and with healthy competition in-door positioning will be significantly improved in several next years.
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
- Pure positioning technologies either provide an absolute or relative position. Several techniques can be combined to achieve best results in each concrete business case.
- 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.
Read and Try More
https://locatify.com/blog/what-is-the-new-apple-u1-chip-and-why-is-it-important/
https://www.computerworld.com/article/3490037/ultra-wideband-explained-and-why-its-in-the-iphone-11.html
https://www.mapwize.io/posts/how-indoor-positioning-works.html
https://www.macobserver.com/link/android-devices-to-get-ultra-wideband-tech-like-iphone-11/
https://towardsdatascience.com/kalman-filter-an-algorithm-for-making-sense-from-the-insights-of-various-sensors-fused-together-ddf67597f35e
https://www.navisens.com/
https://www.researchgate.net/publication/307849839_Enhancing_indoor_positioning_based_on ...