Memoryless Techniques and Wireless Technologies for Indoor Localization With the Internet of Things

Sebastian Sadowski, Petros Spachos, Konstantinos N. Plataniotis

TL;DR

This paper tackles the challenge of accurate indoor localization for the Internet of Things (IoT) by comparing three common techniques (trilateration, K-Nearest Neighbors (KNN), and Naive Bayes) across three popular wireless technologies (Zigbee, BLE, and WiFi) in various interference environments. The findings highlight KNN as the most accurate and precise method, especially when combined with fingerprinting, offering a robust solution for smart building applications.

What Problem Does This Paper Address?

Indoor positioning systems (IPS) are crucial for enabling location-based services (LBS) in smart buildings and the broader Internet of Things (IoT). Unlike outdoor environments where GPS is readily available, indoor spaces present significant challenges due to multipath effects, signal reflections, and obstructions, leading to inaccurate location estimates. While various IPS exist, there's no universal standard, and the choice of localization technique and wireless technology can drastically impact performance. This paper aims to provide a comprehensive comparison of popular memoryless localization techniques and common IoT wireless technologies to guide the selection of the most effective approach for indoor environments.

Methods

The study compares three localization techniques:

  • Trilateration: A model-based approach that calculates a device's position by measuring its distance to multiple known reference points (anchors). The distances are derived from Received Signal Strength Indicator (RSSI) values using a path-loss model.
  • K-Nearest Neighbors (KNN): A fingerprinting technique. It involves creating a database of RSSI measurements at known locations (fingerprints). When an unknown location needs to be determined, its RSSI is compared to the database, and the location of the k nearest neighbors is used to estimate the position.
  • Naive Bayes: Another fingerprinting technique that uses Bayes' Theorem to calculate the probability of a device being at a certain location based on its RSSI measurements and a pre-existing database.

These techniques were evaluated using three wireless technologies:

  • Zigbee (IEEE 802.15.4): Known for its low power consumption and mesh networking capabilities.
  • Bluetooth Low Energy (BLE): Popular for its low power usage and widespread adoption in beacons.
  • WiFi (2.4 GHz): A ubiquitous wireless technology with high bandwidth.

The experiments were conducted in three distinct scenarios to simulate varying levels of interference: low, average, and high.

Datasets

The paper describes the creation of a dataset of RSSI data collected during extensive experimentation across multiple scenarios and wireless technologies. This dataset is made publicly available online. The experiments involved collecting RSSI measurements at specific "fingerprint" locations to build a database and at "evaluation" points to test the localization accuracy.

Key Insights and Ideas

  • Fingerprinting Reigns Supreme: The study strongly suggests that fingerprinting-based methods (KNN and Naive Bayes) significantly outperform traditional trilateration for indoor localization accuracy and precision. This is attributed to their ability to learn and adapt to the unique radio frequency characteristics of an environment, effectively mitigating the impact of signal fluctuations.
  • KNN's Simplicity and Accuracy: KNN emerged as the most accurate and precise technique. Its implementation is relatively straightforward, involving calculating Euclidean distances and averaging the positions of the nearest neighbors. This makes it a practical choice for many applications.
  • Wireless Technology Matters, But Less Than Technique: While the choice of wireless technology (Zigbee, BLE, WiFi) did influence results, the localization technique had a more profound impact on accuracy. BLE and WiFi generally performed well, with Zigbee showing slightly lower performance in some scenarios.
  • Interference is a Major Factor: The level of environmental interference directly impacted localization accuracy, particularly for trilateration. Higher interference levels led to larger errors. Fingerprinting techniques, however, proved more resilient to interference due to their reliance on learned patterns.
  • Database Density Trade-offs: For KNN, the density of fingerprints in the database has a complex relationship with accuracy and runtime. A denser database can lead to higher accuracy but also increases computation time. The study found that a well-placed, moderately sized database could yield optimal results.

Key Results

  • KNN Accuracy: KNN achieved the lowest average error across all scenarios and technologies, with an overall Mean Squared Error (MSE) of 1.602 meters and a variance of 0.6662 m.
  • Naive Bayes Performance: Naive Bayes was the second-best performing algorithm, with an overall MSE of 2.5672 m and a variance of 2.4675 m.
  • Trilateration's Weakness: Trilateration performed the worst, exhibiting the highest average error (3.2593 m) and variance (4.0421 m), making it unreliable for precise indoor localization.
  • Scenario-Specific Performance: BLE and WiFi generally showed better performance in low-interference environments, while WiFi excelled in the high-interference scenario.
  • Computational Complexity: Trilateration offered the best computational complexity (O(1)), making it the fastest. However, KNN and Naive Bayes, while more computationally intensive (O(mn)), provided superior accuracy.

Limitations and Future Work

  • Database Dependency: Fingerprinting techniques like KNN and Naive Bayes require the creation and maintenance of a database, which can be time-consuming and labor-intensive. Changes in the environment necessitate database updates.
  • Runtime for Fingerprinting: The runtime of KNN and Naive Bayes is dependent on the size of the database and the number of access points, which can be a limitation for real-time applications with very large environments.
  • Future Work: The authors suggest that the experimental results can serve as a guide for selecting appropriate indoor localization techniques for smart buildings. The open-source RSSI dataset is a valuable resource for further research and development in this area. Further exploration into optimizing database creation and reducing the computational overhead of fingerprinting techniques would be beneficial.

Summary updated

Abstract

In recent years, the Internet of Things (IoT) has grown to include the tracking of devices through the use of indoor positioning systems (IPSs) and location-based services (LBSs). When designing an IPS, a popular approach involves using wireless networks to calculate the approximate location of the target from devices with predetermined positions. In many smart building applications, LBS is necessary for efficient workspaces to be developed. In this article, we examine two memoryless positioning techniques, $K$ -nearest neighbor (KNN) and Naive Bayes, and compare them with simple trilateration, in terms of accuracy, precision, and complexity. We present a comprehensive analysis between the techniques through the use of three popular IoT wireless technologies: 1) ZigBee; 2) Bluetooth low energy (BLE); and 3) WiFi (2.4-GHz band), along with three experimental scenarios to verify results across multiple environments. According to experimental results, KNN is the most accurate localization technique as well as the most precise. The received signal strength indicator data set of all the experiments is available online.
BibTeX
@article{sadowski2021memoryless,
  author = {Sebastian Sadowski and Petros Spachos and Konstantinos N. Plataniotis},
  title = {{Memoryless Techniques and Wireless Technologies for Indoor Localization With the Internet of Things}},
  journal = {IEEE Internet of Things Journal},
  year = {2021},
  url = {https://openreview.net/forum?id=H3tn4X5dyi},
}
Figure