WLAN Location Determination via Clustering and Probability Distributions
We present a WLAN location determination technique, the Joint Clustering technique, that uses (1) signal strength probability distributions to address the noisy wireless channel, and (2) clustering of locations to reduce the computational cost of searching the radio map. The Joint Clustering technique reduces computational cost by more than an order of magnitude, compared to the current state of the art techniques, allowing non-centralized implementation on mobile clients. Results from 802.11-equipped iPAQ implementations show that the new technique gives user location to within 7 feet with over 90% accuracy.
As ubiquitous computing becomes more popular, the importance of context-aware applications increases. This in
turn fuels the need to determine user location, with which
the system can provide location-speciﬁc information and
Many systems over the years have tackled the problem of determining and tracking the user position. Examples include GPS , wide-area cellular-based systems , infrared-based systems [18, 3], ultrasonic-based
systems , various computer vision systems , physical contact systems , and radio frequency (RF) based
systems . Of these, the class of
RF-based systems that use an underlying wireless data network [4, 20, 14, 5, 13, 10], such as 802.11, to estimate user
location has gained attention recently, especially for indoor
application. Unlike infrared-based systems, which are limited in range, RF-based techniques provide more ubiquitous
coverage and do not require additional hardware for user
location determination, thereby enhancing the value of the
wireless data network.
RF-based systems usually work in two phases: ofﬂine training phase and online location determination phase. During the ofﬂine phase, the signal strength received from the access points at selected locations in the area of interest is tabulated, resulting in a so-called radio map. During the location determination phase, the signal strength samples received from the access points are used to “search” the radio map to estimate the user location. RF-based systems need to deal with the noisy characteristics of the wireless channel. Those characteristics cause the samples measured in the online phase to deviate significantly from those stored in the radio map, thereby limiting the accuracy of such systems. Moreover, in order to preserve user privacy and to make the location system scalable, the location determination code should be run on the mobile unit. Since mobile devices are energy-constrained, it is important to reduce the computational requirement of the location determination system. In this paper, we present an accurate and scalable system for determining the user location with low computational requirements in an 802.11 wireless LAN (WLAN) framework. The system has two key features: (1) It uses probability distributions to enhance accuracy and tackle the noisy nature of the wireless channels. (2) It uses clustering of map locations to reduce the computational requirements. We call our technique the Joint Clustering (JC) technique. We have evaluated the system in an indoor space spanning a 20,000 square foot. Results obtained show that the Joint Clustering technique gives the user location with over 90% accuracy to within 7 feet with very low computational requirements.