A comparison of deterministic and probabilistic methods for indoor localization

Abstract

Received signal strength indication fingerprinting (RSSIF) is an indoor localization technique that exploits the prevalence of wireless local area networks (WLANs). Past research into RSSIF systems has seen the development of a number of algorithmic methods that provide effective indoor positioning. A key limitation, however, is that the performance of these methods is heavily dependent on practical implementation parameters and the nature of the test-bed environment. As a result, past research has tend to only compare algorithms of the same paradigm using a specific test-bed, and thus making it difficult to judge and compare their performance objectively. There is, therefore, a critical need for a study that addresses this gap in the literature. To this end, this paper compares a range of RSSIF methods, drawn from both probabilistic and deterministic paradigms, on a common test-bed. We evaluate their localization efficiency and accuracy, and also propose a number of improvements and modifications. In particular, we report on the impact of dense and transient access points (APs) – two problems that stem from the popularity of WLANs. Our results show methods that average the distance to the k nearest neighbors in signal space perform well with reduced dimensions. Moreover, we show the benefits of using the standard deviation of RSSI values to exclude transient APs. Other than that, we outline a shortcoming of the Bayesian algorithm in uncontrolled environments with highly variable APs and RSSI values, and propose an extension that uses a mode filter to restore its accuracy with increasing samples.

Introduction

In the last decade, there has been a substantial increase in the number of mobile, networked devices. This has created a demand for a new generation of smart, context-aware applications that rely on localization to provide users with value added services. For example, they may rely on outdoor systems such as Global Positioning System (GPS) (Getting, 1993) and E911 (Zagami et al., 1998) to provide targeted advertisements, or to pinpoint a person's location during an emergency. For indoors, these applications may use Active Badge (Wang et al., 1992), Cricket (Priyantha et al., 2000), Active Bat (Harter et al., 1999), Smart Floor (Orr and Abowd, 2000), AwareMedia and AwarePhone (Bardraml et al., 2006). The main limitation of these systems is that they require specialized hardware and in many cases the installation of a new and independent infrastructure to support localization sensors. For example, Cricket requires the installation of beacons whereas AwareMedia and AwarePhone require existing wired networks to be augmented with Bluetooth (Haartsen et al., 1998). Active Bat and Active Badge require the installation of a new wired network. In particular, Active Bat requires sensors to be placed in a grid pattern on the ceiling.

To address the aforementioned limitation, the authors of Bahl and Padmanabhan (2000) propose a system, called RADAR, that uses the access points (APs) in wireless local area networks (WLANs) for localization. Specifically, referring to Fig. 1, there are two phases. In the offline phase, the system designer builds a map of RSSI fingerprints for a given building or floor. For example, a fingerprint can be collected and associated with each cell of a floor that has been divided into a grid of 1 m × 1 m cells. This information is then used by users who want to obtain their location in the online phase. Their portable device will first record a number of RSSI readings, so called fingerprints, from multiple APs, and with the use of the map, attempts to find a location or cell that has a similar fingerprint. The matching location or cell is then returned to the users. Note that RSSI is preferred over signal to noise ratio (SNR) because it is a stronger function of location than SNR. This is because SNR suffers from random fluctuation due to noise and interference from other devices operating in the same frequency band (Bahl and Padmanabhan, 2000). In addition, RSSI is available readily from all wireless network interface cards. Interestingly, besides WLANs, one can also use signals from base stations (Varshavsky et al., 2007). This is particularly advantages in indoor environments with little or no APs.

Advantageously, RADAR does not require the installation of new hardware and rely solely on software. On the other hand, its key disadvantage stems from the use of RSSI values, which are inherently noisy and varies over time due to non-negligible multipath fading, especially in indoors environments. As a result, the precision and accuracy of the system depends on how far apart fingerprints are in signal space, rather than physical space. Just because two fingerprints are far apart in physical space, does not necessarily mean they are very far apart in signal space. In fact, they may be very close. Apart from that, system designers need to spend a significant amount of time initially to build the map or fingerprint database of a given environment. To this end, researchers have considered the use of strategically positioned anchors, theoretical modeling of signal space, and calibration to quickly build the database (Barsocchi et al., 2009, Lim et al., 2006). Nonetheless, the construction of the RSSIF database is a once off cost but accuracy of different classes of localization algorithms remains a key issue.

To this end, as shown in Table 1, researchers have proposed a number of solutions, which can be divided into deterministic and probabilistic methods. Deterministic techniques, such as k-nearest neighbor (see Section 2.1), provide acceptable performance given their simplicity. In general, probabilistic methods offer superior localization performance. This, however, is achieved at the expense of higher computational requirements as they rely on a higher number of RSSI samples taken per position, which effects their training time and cost. In addition, the total number of positions in the search space also has a significant impact on their computation time. Table 1 also shows the impact of APs on accuracy and precision. RSSI system performance ranges from an accuracy of within 2.2 m 38% of the time if there are a minimum of three APs (Bahl and Padmanabhan, 2000) to within 2.5 m 90% of the time using 10 APs (Roos et al., 2002).

From Table 1, it is clear that previous research has demonstrated the effectiveness of RSSIF techniques for indoor localization using deterministic and probabilistic methods. However, there is very little quantitative comparison between these two paradigms under the same experimental condition, which makes it difficult for context-aware applications developers to determine the best approach to employ. In addition, prior works have not outlined an effective strategy for the inclusion of APs in fingerprint databases. This is of importance because we found APs tend to drift in and out of range frequently. As a result, a number of APs may be missing during data collection and localization. Moreover, we found each fingerprint contain an average of 17.5 APs. Hence, in the interest of computation overheads and reliability, we must ensure only a subset of APs are used for localization. This is in contrast to prior works that only have a small number of anchors in each fingerprint; e.g. (Barsocchi et al., 2009). Lastly, we showed that the Bayesian method does not work well in environments with high variability. In particular, we found that its accuracy does not improve with additional samples. Henceforth, this paper makes the following contributions:

• We objectively compare both deterministic and probabilistic methods on the same test-bed.

• We study the impact and provide solutions to the following key issues: (i) high number of APs, (ii) transient APs, and (iii) highly variable RSSI values.

• We propose four new variants that address a key shortcoming with methods that compute a position estimate using k nearest neighbors.

• We evaluate the benefits of combining k-nearest neighbor methods with those that use the probability distribution of RSSI values.

• We show the effectiveness of using the standard deviation of RSSI values in order to exclude transient APs.

• We modified the Bayesian algorithm to use a mode filter in order to address its shortcomings in environments with high variability.

In the next section, we will first describe existing deterministic and probabilistic methods. After that, in Section 3, we present our testbed, and the methodology used to collect and sanitize RSSI data. This is followed by experimental results, and discussion in Section 4. Finally, Section 5 presents our conclusions.