Indoor Positioning with Wireless Local Area Networks (WLAN)

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Synonyms

WLAN localization; WLAN location estimation; WLAN location determination; WLAN geolocation; WLAN location identification; WLAN location discovery; Radiolocation; WLAN location sensing; Position location; Location based services

Definition

WLAN positioning refers to the process of locating mobile network devices, such as laptops or personal digital assistants, using a Wireless Local Area Network (WLAN) infrastructure. Positioning is carried out by exploiting the dependency between the location of a mobile device (MD) and characteristics of signals transmitted between the MD and a set of WLAN access points (APs). These characteristics are generally Time of Arrival (ToA), Time Difference of Arrival (TDoA), Angle of Arrival (AoA), and Received Signal Strength (RSS). RSS is the feature of choice in WLAN positioning systems as it can be obtained directly from Network Interface Cards (NIC) that are available on most handheld computers. This allows the implementation of positioning algorithms on top of existing WLAN infrastructures without the need for any additional hardware. The wide availability and ubiquitous coverage provided by WLANs makes this type of positioning a particularly cost effective solution for offering value-added location based services (LBS) in commercial and residential indoor environments.

Figure 1

Overview of steps involved in positioning

With accuracies in the range of 1–5 meters, WLAN positioning systems can be used to infer location information in two or three dimensional Cartesian coordinates with the third dimension representing a floor number. Location information can either be reported relative to a predefined coordinate system or symbolically (e. g., room number, floor number, etc.). Positioning may be performed by the infrastructure (network-based, remote positioning) or by the MD (terminal-based, self‐positioning). The former offers more computational power whereas terminal-based positioning enhances scalability and promotes privacy.

Historical Background

Cellular network infrastructures have served as a milieu for the development of positioning systems to deliver location-based emergency and commercial services, including location‐sensitive billing and advertising, to their users since the introduction of the E-911 mandate by the U.S. Federal Communications Commission in 1996. Another important positioning system is the Global Positioning System (GPS), which offers highly accurate positioning capability and is used in outdoor navigation and LBS.

More recently, advances in wireless communication technology have led to user mobility within indoor networks, inspiring location‐awareness and LBS in a wide range of personal and commercial applications geared toward indoor environments. Unfortunately, the positioning accuracy provided by existing cellular-based methods is not sufficient for such applications and coverage of the GPS system is limited in indoor environments.

With this in mind, various positioning systems have been proposed to address the problem of positioning specifically in indoor environments. These systems make use of a variety of technologies including proximity sensors, radio frequency (RF) and ultrasound badges, visual sensors, and WLAN radio signals, to carry out positioning.

Among the above methods, WLAN positioning systems have received special attention due to the fact that they can be cost‐effectively implemented on top of existing and widely deployed WLANs. Similar to “cell of origin” methods in cellular systems, early work in WLAN positioning estimated the position of an MD as that of the access point with the strongest signal based on the premise that this AP is closest to the MD in the physical space. With the advent of the IEEE 802.11 based wireless networks, the first fine-grained WLAN positioning systems were introduced in the year 2000 (see, for example, the pioneering RADAR system [1]). Soon thereafter, WLAN positioning solutions were commercialized for use in applications such as asset tracking, resource management, and network security [2].

Scientific Fundamentals

The main technical challenge in WLAN positioning is the determination of the dependency between the received signal strength (RSS) and the location of an MD. As the signal travels through an ideal propagation medium (i. e., free-space), the received signal power falls off inversely proportional to the square of the distance between the receiver and transmitter. Thus, given the measurements of transmitted and received powers, the distance between the transmitter and the MD can be determined. Given three such distances, trilateration can be used to estimate the position of an MD. Unfortunately, in real environments, the propagation channel is much more complicated than the ideal scenario presented above, leading to a much more complex position-RSS dependency. The difficulties arise as a result of severe multipath and shadowing conditions as well as non-line-of-sight propagation (NLOS) caused by the presence of walls, humans, and other rigid objects. Moreover, the IEEE 802.11 WLAN operates on the license-free band of frequency 2.4 GHz which is the same as cordless phones, microwaves, BlueTooth devices, and the resonance frequency of water. This leads to time-varying interference from such devices and signal absorption by the human body, further complicating the propagation environment. To make matters worse, WLAN infrastructures are highly dynamic as access points can easily be moved or discarded, in contrast to their base-station counterparts in cellular systems which generally remain intact for long periods of time.

Figure 1 provides an outline of the steps involved in a positioning system. Each of the components are described in sections that follow.

Modeling of Rss-Position Dependency

Existing WLAN positioning techniques can be classified into model-based and fingerprinting approaches based on how the RSS-position dependency is determined. The approaches are discussed next.

Model-Based Methods

The first class of methods aim to characterize the RSS-position dependency using theoretical models whose parameters are estimated based on training data [3]. Given an RSS measurement and this model, the distances from the MD to at least three APs are determined and trilateration is used to obtain the MD position as shown in Fig. 2.

Figure 2

Model-based WLAN positioning techniques use a propagation model to obtain distances to at least three APs and trilaterate the position of the mobile device

A model for relating RSS and the distance to an AP can be constructed by considering the fact that in real environments, in addition to the distance traveled, two additional mechanisms contribute to variations in the propagation channel, namely, large scale and small scale fading. Large scale fading is due to path loss and shadowing effects. Path loss is related to dissipation of signal power over distances of 100–1000 meters. Shadowing is a result of reflection, absorption, and scattering caused by obstacles between the transmitter and receiver and occurs over distances proportional to the size of the objects [4]. Due to uncertainties in the nature and location of the blocking objects, the effects of shadowing are often characterized statistically. Specifically, a log-normal distribution is generally assumed for the ratio of transmit-to-receive power. The combined effects of path loss and shadowing can be expressed by the simplified model below [4]:

$$ \begin{aligned} {P_{\text{r}}} (\text{dB}) =&\ {P_{\text{t}}} (\text{dB}) + 10\log_{10}K\\ &- 10\gamma \log_{10}\left(\frac{d}{d_0}\right) - \psi (\text{dB})\,. \end{aligned} $$

(1)

In Eq. (1), P _r and P _t are the received and transmitted powers respectively, K is a constant relating to antenna and channel characteristics, d ₀ is a reference distance for antenna far-field, and γ is the path loss exponent. Typical values of this parameter are γ = 2 for free-space and 2 ≤ γ ≤ 6 for an office building with multiple floors. Finally, $\psi\sim{\mathcal{N}}(0,\sigma^2_{\psi})$ reflects the effects of log-normal shadowing in the model.

Small scale fading is due to constructive and destructive addition from multiple signal paths (multipath) and happens over distances on the order of the carrier wavelength (for WLANs, $\lambda=\frac{c}{2.4\,\text{GHz}}=12.5\,\text{cm}$). Small-scale fading effects can lead to Rayleigh or Rician distributions depending on the presence or absence of a line-of-sight, respectively [4].

In indoor areas, materials for walls and floors, number of floors, layout of rooms, location of obstructing objects, and the size of each room have a significant effect on path loss. This makes it difficult to find a model applicable to general environments. Other limitations of model-based approaches include their dependence on prior topological information, assumption of isotropic RSS contours and invariance to receiver orientation [5].

Fingerprinting-Based Methods

As an alternative to model-based methods, the RSS-position dependency can be characterized implicitly using a training-based method known as location fingerprinting. A location fingerprint is a vector r _i (t) = [r _i ¹(t), … r _i ^L(t)] of RSS measurements from L APs at time t at spatial point p _i . The symbol p _i  = (x _i ,y _i ) or p _i  = (x _i ,y _i ,z _i ) represents a point in the two or three dimensional Cartesian coordinates.

Fingerprints are usually generated offline. This is done by collecting a set of measurements r _i (t), t = 1, … ,n _i , at a set of training locations {p ₁, …, p _N } with the purpose of obtaining a sufficient representation of spatio‐temporal RSS properties in the given environment. The database of these location fingerprints together with their respective coordinates is known as a radio map. The main challenges in the construction of the radio map include the placement and number of survey points as well as determination of the number of time samples needed for a sufficient representation at each point.

Preprocessing

Figure 3

Fingerprinting-based WLAN positioning techniques estimate the position of the mobile device as a combination of training points whose fingerprint record best matches the observation RSS. The dashed line delineates the training points used to form the estimate

Before the actual positioning is performed, some preprocessing may happen to reduce computational complexity and improve efficiency of the positioning algorithm. For example, [6] proposes two preprocessing methods. The first clusters the environment into grids that receive similar AP coverage and reduces the search space to a single cluster. The second involves an incremental trilateration technique where APs are used consecutively to reduce the subset of candidate locations. With the objective of power efficiency in mind, the work of [7] proposes an offline clustering method based on K-means that considers the similarity of AP values in addition to the covering sets. Lastly, [8] proposes an online spatial filtering technique to dynamically exclude irrelevant survey points from positioning calculations. The online preprocessing techniques are advantageous to their offline counterparts in terms of resiliency to loss of APs as the set of APs used during the real operation of the system may be different than that used during training.

AP Selection

Although two‐dimensional positioning can be carried out with as few as three APs, a mobile device may receive coverage from many more APs in large indoor environments with ubiquitous WLAN infrastructures. Clearly, using all available APs for positioning increases the computational complexity of the system. Moreover, depending on the relative distance of the MD and each AP and the topology of the environment in terms of obstacles causing NLOS propagation, correlated RSS readings may be received from subsets of APs, leading to biased estimates.

These problems motivate the design of an AP selection block whose function is to choose the best set of APs with the given minimum cardinality for positioning. The most commonly used selection scheme is to choose APs with the highest observation RSS to ensure coverage for survey points near the observation. Unfortunately, the time variance in RSS from an AP generally increases with its mean signal strength. In such cases, the observation may differ significantly from the training values and it becomes more difficult to distinguish neighboring points.

More recently, AP selection methods employing entropy-based techniques and divergence measures have been proposed in [7,8]. In particular, the work of [7] proposes the use of the Information Gain criterion to choose APs with the best discrimination ability across the survey points and experimentally demonstrates advantages over the traditional technique of the strongest APs. Because selection is performed during the offline training of the system and remains fixed for predetermined clusters of points, the method lacks flexibility in coping with loss of APs. An online and realtime selection technique is proposed in [8] to circumvent this problem. This method aims to select a set of APs with minimum correlation to reduce redundancy. Lastly, since distance calculations are performed on the AP set chosen by the selection component, it is important to consider the interplay among the selection strategy and distance measurement when designing these components [8].

Positioning

With reference to Fig. 1, the positioning step is initiated when a new RSS measurement from an MD is received during the online operation of the system. As previously mentioned, model-based techniques rely on trilateration for positioning. In contrast, fingerprinting-based methods compare the observation to fingerprints in the radio map and return a position estimate. In general, the estimate is a combination of survey points whose fingerprints most closely match the observation.

As shown in Fig. 3, the aim of positioning is to determine a position estimate as a function of the available survey points. That is, the goal is to find $\hat{\mathbf{p}}=h({\mathbf{p}}_1,\ldots, {\mathbf{p}}_{N})$ where $\hat{\mathbf{p}}$ denotes the position estimate and {p ₁, … ,p _N } is the set of survey points in the radio map. If h(·) is restricted to be a linear function of the survey points, the position estimate $\hat{\mathbf{p}}$ can be obtained as follows:

$$ \hat{{\mathbf{p}}} = \frac{1}{K}\frac{\sum_{i=1}^{K} w_i\mathbf{p}_{(i)}}{\sum_{K=1}^{N}w_i}\,, $$

(2)

where w _i is inversely proportional to the distance between the fingerprints at p _(i) and the observation and the set {p ₍₁₎, … ,p _(K)} denotes the ordering of survey points with respect to w _i .

There are three groups of positioning techniques in the existing literature, namely, deterministic, probabilistic, and kernel-based learning methods, based on how they determine the weights w _i . These are discussed in what follows.

In the simplest case, the survey points are ranked based on the Euclidean distance between the observation and the sample mean of the RSS training samples as in RADAR [1]. In this case, the position estimate is obtained as the average of the K nearest neighbors (KNN) and w ₁ = w ₂ = … = w _K.

In the more general case, the weights w _i are determined as functions of the distance between the observation RSS and the training RSS record at each survey point. For example, the weights can be chosen to be inversely proportional to the Euclidean distance above. Despite its simplicity, however, the Euclidean distance may fail to deliver adequate performance in cases where the distribution of RSS training vectors included in the fingerprints are non-convex and multimodal. Such distributions arise frequently in indoor WLAN settings due to NLOS propagation and presence of users [5].

In Bayesian approaches, such as [6], the weights are directly proportional to the likelihood or posterior probabilities p(r|p _i ) and p(p _i |r). These probabilities can be estimated from the training data either parametrically, through the assumption of a specific form for the density (e. g., a Gaussian), or nonparametrically, using density estimates such as the histogram or the kernel density estimator (KDE) [2,9]. Using the probabilistic weights, the position estimate corresponds to the maximum likelihood (ML) or maximum a posteriori (MAP) estimate when K = 1, and the minimum mean square error estimate (MMSE) when K = N [9].

Motivated by the complexity of RSS patterns in this Euclidean space, the work of [8] proposes a kernelized distance for the calculation of the distance between an RSS observation and the fingerprints. This method nonlinearly maps the original fingerprint data to a high dimensional feature space where the distribution of RSS training vectors is simplified and carries out distance calculations in such a space. The weights are then obtained as inner products in the kernel‐defined feature space. The authors show that this position estimator can be interpreted as a multidimensional kernel regression as well as the MMSE estimator of position in the case where the empirical probability density estimate (epdf) is used as the prior f(p).

Another kernel method explored in the context of WLAN positioning is the kernel support vector machine (SVM) for both classification and regression [10], aiming to find the best set of weights for interpolating the survey points to minimize the training error while controlling the model complexity. Both of the classification and regression problems are solved independently for each dimension in the physical space. In contrast to this, the work of [11] proposes a multidimensional vector regression. In particular, a nonlinear mapping between the signal and physical spaces is built by observing that the pairwise similarity in these two spaces should be consistent. The distance between an observation and the fingerprint record is obtained as the distance between their projections onto a set of canonical vectors determined through Kernel Canonical Correlation Analysis (KCCA) and used to determine the weights in (2).

As an alternative to the use of Equation (2), decision trees are used in [7] to determine the position estimate by classifying the incoming observation as coming from one of the survey points by a series of efficient tests. Such a scheme is effective in reducing complexity and, hence, improves power efficiency on mobile devices.

An important consideration in designing training-based methods, such as the aforementioned regression techniques, is resiliency to loss of APs in WLAN infrastructures. Because APs can easily be discarded or moved, the dimensionality of the RSS vector may well be different in the training and realtime operation of the system and cannot be assumed to be fixed [8].

Tracking

Human motion is generally not random but correlated over time. Therefore, at any point in time, past position estimates can be utilized to adjust the current estimate. Such dynamic tracking solutions may simply entail a running average of previous estimates [6] or rely on more sophisticated methods such as the Kalman filter [9], Markov-model based solutions [12], and the particle filter [13].

Tracking need not be limited to the use of past position information. Predictions of future locations can also be used to proactively adjust system parameters. For example, in [9], predictions are utilized to dynamically generate subsets of the radio map for use in positioning.

Key Applications

Since its conception, WLAN positioning has been used as an enabling tool for offering location-based services in indoor environments. Three examples of specific applications are outlined below.

Network Management & Security:

WLAN positioning solutions can be used to offer a variety of location sensitive network services such as resource allocation, traffic management, and asset tracking. In addition, such technology can promote network security by introducing location-based authorization and authentication. Many such solutions are currently commercially available [2].

Information Delivery:

In order to provide mobile users with seamless and transparent access to information content, location-based personalization of information delivery is needed [14]. WLAN positioning is a particularly effective solution in such cases since the necessary infrastructure is widely available in both commercial and home settings.

Context‐Awareness:

As location is an important piece of contextual information, WLAN positioning and tracking can offer an effective solution for context-aware applications that not only respond, but proactively anticipate user needs [15].

Future Directions

Wireless local area networks provide a cost‐effective infrastructure for the implementation of positioning systems in indoor environments. As large urban cities turn into giant wireless “hotspots”, it becomes essential to consider the design of inexpensive outdoor WLAN positioning methods. Such solutions must be distributed and scalable to support entire cities and power‐efficient to allow implementation on a variety of mobile devices with different capabilities. Lastly, location information must be secured to prevent unauthorized usage.

Cross References

Indoor Positioning

Privacy Preservation of GPS Traces