Accurate and Low-cost Location Estimation Using Kernels

1 Introduction

Location estimation is a major area of pervasive computing applications that range from context-dependent content delivery to people monitoring . However, accurate location information may not be always available. For example, many buildings cannot be reached by location-determination devices such as GPS. In such environments, a commonlyused technique is to leverage the signal strength values of a wireless network such as the IEEE 802.11b wireless LAN network (WLAN). Many systems utilize the signal strength values received from the access points to infer the location of mobile devices, based on deterministic or probabilistic techniques [Ladd et al., 2002; Gentile and Berndt, 2004; Youssef et al., 2003; Bahl and Padmanabhan, 2000; Ni et al., 2003]. Similarly, in a sensor network, the location information must also be inferred from signals received from various deployed sensors. A major issue in these applications is how to build an accurate mapping between the signal space and the physical space while incurring minimal human effort.

In general, location-estimation systems using (RF)-based signal-strength values function in two phases: an offline training phase and an online, localization phase. In the offline phase, a probabilistic model is trained by considering the signal strength values received from the access points at selected locations in the area of interest. These values comprise the training data gathered from a physical region, which are used to calibrate a probabilistic location-estimation system. In the online localization phase, the real-time signal strength samples received from the access points are used to estimate the current location based on the learned model.

In the training phase, the learned model is essentially a mapping function f(S,P) between the signal space S and the physical location space P. Deterministic techniques build such a mapping function by assuming a signal propagation model based on properties of electro-magnetic fields. These signal-propagation models often cannot accurately describe a realistic environment due to uncertainty in the devices and the obstacles in the signal paths. Probabilistic techniques are often more accurate by directly handling the uncertainty. These techniques construct the function f(·, ·) by maximizing the likelihood of the observation given the probabilistic distribution of the training data used for calibration.

However, the probabilistic methods suffer from several major shortcomings. First, these techniques require a huge amount of labeled data for the trained model to be accurate. In reality, the data collection is a time-consuming process. In our experience, for example, in our earlier test it took many hours to collect and label the signal-strength data in a limited indoor environment. Second, the mapping between the signal and physical spaces are very difficult to construct due to nonlinearity. Nonlinearity exists when similar locations have very different signal signatures. Therefore, a direct mapping between the two spaces may not always work well, even when much data are collected. Third, many probabilistic techniques adopt a classification-based approach, by treating the locations as discrete classes to be classified. However, this approach ignores the important information inherent in the physical proximity of the locations. Furthermore, previous methods that apply regression based techniques treat the physical dimensions (x, y) separately, they cannot fully exploit the geometric information imparted by considering x and y together.

In this paper, we present a similarity-based approach to building a mapping function. Our main intuition is to perform a kernel-based transformation of the signal and physical spaces to capture the nonlinear relationship between the signals and locations. Furthermore, we perform a kernel canonical correlation analysis (KCCA) in the two spaces for feature extraction. This allows the pairwise similarity of samples that are measured in both spaces to be maximally correlated. We apply a Gaussian kernel to adapt the noisy characteristic of signal strength and use a Mat´ern kernel to sense the change in physical locations.

A major advantage of our proposed technique is that we can obtain higher accuracy while reducing the training cost by requiring only a fraction of the labeled samples as compared to previous methods. We demonstrate this result in a series of tests on WLAN location estimation using the data collected in a realistic environment.

2 RelatedWork

2.1 Location Estimation

Location-estimation systems are an integral component for probabilistic plan-recognition systems in AI [Liao et al., 2004; Bui et al., 2002]. In general, they operate in two phases: an offline training phase and an online localization phase. During the offline phase, a radio map is built which tabulates the signal strength received from the access points at selected locations in the area of interest. During the localization phase, the signal strength samples received from the access points are used to search the radio map to estimate a user's location. In building the radio maps, two techniques have been attempted: deterministic and probabilistic.

Deterministic techniques rely on radio propagation models which take into account such environmental factors as pathloss functions [Roos et al., 2002a; Kaemarungsi and Krishnamurthy, 2004]. When this is possible to do where uncertainty is relatively low, signal distribution models can be derived with a relatively small number of samples using knowledge on propagation channels [Hashemi, 1993]. This also enables the nearest neighbor or triangulation techniques to be used [Bahl and Padmanabhan, 2000; Smailagic and Kogan, 2002; Bhasker et al., 2004]. For example, the RADAR system by Microsoft Research [Bahl and Padmanabhan, 2000] uses nearest neighbor heuristics and triangulation methods to infer a user's location. Each signal strength sample is compared against the radio map and the coordinates of the best matches are averaged to give location estimation. The accuracy of RADAR is about three meters with fifty percent probability. In [Bhasker et al., 2004], an online procedure based on feedback from users was employed to correct the location estimation of the system. A similar technique for sensor networks has been applied; for example, the LANDMARC system [Ni et al., 2003] utilizes the concept of reference tags to alleviate the effects caused by the fluctuation in RF signal strength. The method first computes the distance between the signal-strength vectors received from the tracking tags and those from different reference-tags' respectively. It then uses k nearest reference tags' coordinates to calculate the approximate coordinate of the tracking tag.

Probabilistic techniques confront the uncertainty in an indoor wireless environment, by constructing the signalstrength distributions over different locations in the radio map and use probabilistic inference methods for localization [Roos et al., 2002b; Youssef et al., 2003]. [Youssef et al., 2003] used a joint clustering technique to group locations together in order to reduce the computational cost of the system. The method first determines a most likely cluster within which to search for the most probable location, then applies a maximum likelihood estimation (MLE) method to infer the most probable location within the cluster.

More recently, intense research efforts have been spent to seek additional knowledge in order to boost the accuracy of the location determination systems. For example, to handle the sequential characteristic of user traces, [Ladd et al., 2002] suggest a sensor fusion model and shows a strong correlation between consecutive samples. The robotics-based location sensing system in [Ladd et al., 2002] applies Bayesian inference to compute the conditional probabilities over locations based on received signal-strength samples from various access points. Then a postprocessing step, which utilizes the spatial constraints of a user's movement trajectories, refines the location estimation and rejects the estimates that show significant changes in the location space. Depending on whether the postprocessing step is used or not, the accuracy of this method is 83% or 77% within 1.5 meters. [Yin et al., 2005; Ni et al., 2003] study the dynamic features of signal strength and build a regression model to adapt the change of radio map with reference points. A radio map is constructed using data mining methods in an effort to reduce the samples collected for calibration[Chai and Yang, 2005].

In contrast to the above works, our approach builds a similarity based mapping function by making full use of the continuous location information in kernel-based transformation. In the next section, we first review kernels and kernel canonical correlation analysis.

2.2 (Kernel) Canonical Correlation Analysis Canonical Correlation Analysis

Given two sets of variables, canonical correlation analysis (CCA) [Hotelling, 1936] attempts to find a basis for each set such that the correlation between the projections of the variables onto these basis vectors are mutually maximized. Mathematically, given n instances S = {(x1, y1), (x2, y2), . . . , (xn, yn)} of the pair (x, y), CCA finds directions (canonical vectors) wx and wy so that the transformed variables (canonical variates) (〈wx, x1〉, 〈wx, x2〉, . . . , 〈wx, xn〉) and (〈wy, y1〉, 〈wy, y2〉, . . . , 〈wy, yn〉), are maximally correlated. Now, define the total covariance matrix by

where ˆE[·] is the empirical expectation operator, Cxx,Cyy are the within-sets covariance matrices and Cxy = C′yx is the between-sets covariance matrix. It can be shown that wx can be obtained by solving the generalized eigenproblem CxyC-1 yy Cyxwx = λ2Cxxwx, and then subsequently obtain wy as wy = 1λ C-1 yy Cyxwx [Hardoon et al., 2004].

Kernel Canonical Correlation Analysis

A major limitation of CCA is that it can only exploit linear relationships between x and y. As is now well-known, the use of kernels offers an efficient, nonlinear extension of CCA. Kernel canonical correlation analysis (KCCA) [Hardoon et al., 2004] implicitly maps x and y to φx(x) and φy(y), and then performs traditional CCA in the two high-dimensional feature spaces. To control the flexibility of the projections, the norms of the associated weight vectors are penalized.

Using the dual representations for the projection directions wφx(x) and wφy(y):

where Sφx(x) = [φx(x1), . . . , φx(xn)]′ Sφy(y) = [φy(y1), . . . , φy(yn)]′ , and α, β ∈ Rn . Denote the corresponding kernel functions by kx(·, ·) and ky(·, ·), and the kernel matrices (defined on all n instances) by Kx and Ky. It can be shown that α can be obtained by solving the generalized eigenproblem

where I is the identity matrix and κ is a user-defined regularization parameter. Subsequently, β can be obtained as

Given any ˜x, its projection on wφx(x) is given by

where k˜x = [kx(˜x, x1), kx(˜x, x2), . . . , kx(˜x, xn)]′ . Similarly, the projection of any ˜y onto wφy(y) is Py(˜y) = k′˜yβ, where k˜y = [ky(˜y, y1), ky(˜y, y2), . . . , ky(˜y, yn)]′ .

The generalized eigenproblem in (2) can be solved by using the (complete) Cholesky decomposition. However, the kernel matrices Kx and Ky are of size n, and so obtaining the Cholesky decomposition can become computational expensive for large training sets. In that case, the incomplete Cholesky decomposition or the partial Gram-Schmidt orthogonalization can be used instead [Hardoon et al., 2004].

3 Location Estimation using KCCA

3.1 Motivation

Consider the two-dimensional location estimation problem 1 . Its goal is to obtain a mapping between the space of signal strengths obtained at p access points S = {s ≡ [s1, s2, . . . , sp]′ ∈ Rp } and the physical space P = {ℓ ≡ [x, y]′ ∈ R2 }. Traditional approaches typically learn the two mappings, S → {x} and S → {y}, independently [Brunato and Battiti, 2004]. In this paper, we consider x and y together and emphasize the correlation between signal and physical spaces, observing that the pairwise similarity in the signal space should match the pairwise similarity in the physical space. For example, in Figure 1, signal SA should be more similar to SB than SC, since A is closer to B in the physical space. Consequently, we consider both x and y together and use KCCA to learn the mapping between the two spaces.

3.2 The LE-KCCAAlgorithm

Offline Training Phase

In the training phase, the following steps are taken:

1 Extension to the three-dimensional (or even higherdimensional) case is straight-forward

1. Signal strengths are collected at various grid locations.
2. KCCA, with appropriate choices for the two kernels (Section 3.3), is used to learn the relationship between the signal and physical spaces. In particular, λi's and αi's are obtained from the generalized eigenproblem in (2), and the corresponding βi's from (3).
3. For each training pair (si, ℓi), its projections

on the T canonical vectors are obtained from (4).

Online Localization Phase

In the localization phase, the location of a new signal strength vector ˜s is estimated as follows:

1. Use (4) to project ˜s onto the canonical vectors and obtain P (˜s) = [P1(˜s), P2(˜s), . . . , PT (˜s)]′ .
2. Among the projections (5) from the training samples, find the M neighbors closest to P(˜s). In this paper, the weighted Euclidean distance di = ∑Tj=1 λj (Pj (˜s)- Pj(si))2 is employed.
3. Interpolate these neighbors' physical locations to predict the physical location of ˜s. In this paper, we simply output the median (or mean for continuous location estimation) of the (x, y) coordinates of these M neighbors.

3.3 Choice of Kernels

Signal-strength values are often noisy. The empirical distribution (radio map) is difficult to obtain, especially when the training samples are scarce. As a first approximation, the Gaussian distribution has been used in characterizing the nonlinearity of the signal strengths [Roos et al., 2002b]. Hence, in this paper, we also use the Gaussian kernel G(x1, x2):

for the S space. Here, wG is a user-defined parameter that reflects the smoothness of the radio map.

On the other hand, measurements of the physical locations are relatively clean. As in [Schwaighofer et al., 2004], we adopt the Mat´ern kernel M(x1, x2) (Figure 2):

where ν is a smoothness parameter, Γ(ν) is the Gamma function and Kν(r) is the modified Bessel function of the second kind. It can be shown that when ν → ∞, the Mat´ern kernel degenerates to the Gaussian kernel, and to the exponential kernel exp(-√2w‖x1 - x2‖) when ν = 0.5. Note that both the Gaussian and Mat´ern kernels are isotropic and so are invariant to the location of origin and to arbitrary rotation.

||x -x′ ||

Figure 2: The Mat´ern kernel.

4 Experiments

In this Section, experiments are performed to measure the accuracy of LE-KCCA, and also test whether this is useful in reducing calibration effort. For comparison, we also run: (1) support vector machine (SVM) [Brunato and Battiti, 2004]; (2) maximum likelihood estimation (MLE) [Youssef et al., 2003]; and (3) RADAR [Bahl and Padmanabhan, 2000].

4.1 Setup

Experiments are performed based on the office layout in the Department of Computer Science , The Hong Kong University of Science and Technology (Figure 3). There are four hallways with a total of 99 grids, where each grid measures 1.5m × 1.5m. There are only three access points in Figure 3, though a total of eight access points (including some from other floors) are detected. Each sample is thus an 8dimensional signal strength vector, with the measurements averaged in one second. 100 such samples are collected at the center of each grid, with a total of 9,900 samples obtained. We randomly use 65% of the 9,900 samples for training and the rest for testing. To reduce statistical variability, results here are based on averages over 10 repetitions.

We set wG in (6) to 0.1, wM in (7) to 0.05, and M (the number of neighbors used in the localization phase) to 17. Preliminary studies show that the accuracy only changes slightly (within 1%) when M varies in the range 7 to 31. Moreover, ν in (7) is set to 0.5, and thus the Mat´ern kernel degenerates to the exponential kernel.

4.2 Location Estimation Accuracy

Figure 4 plots the average testing accuracies (and the corresponding standard deviations) at different acceptable error distances. At an error distance of 3.0m, the accuracy of LEKCCA is 91.6% while those of SVM, MLE and RADAR are 87.8%, 86.1% and 78.8% respectively. Thus, by utilizing the pairwise distance similarities in physical locations, LEKCCA obtains better performance than the other methods.

4.3 Reduction in Calibration Effort

In the first experiment, we use all the 99 grid locations but only a random subset of the signal samples available at each location for training. Figure 5 shows the testing accuracies at error distances of 1.5m or 3.0m. As can be seen, by using only 10-15 random training samples at each location, LE-KCCA can already outperform the other methods that use a full set.

In the second experiment, we select a subset of the available grid locations, and then use all the training signal samples at those selected locations for training. Evaluation is performed on both the unseen signal samples at the selected grid locations and also at the unseen locations. Again, Figure 6 shows that LE-KCCA yields better performance. Thus, LE-KCCA, by maximizing the correlation between signal and physical spaces, can reduce the calibration effort dramatically. With the physical location similarity as feedback, samples from the same locations move closer together, while those from different locations are pushed away under the feature-space mapping built by LE-KCCA.

We believe that LE-KCCA performs well. To validate this claim, we conduct another three experiments for comparison. The first one treats all the grid locations separately, which can be achieved by using a large value for wM in the Mat´ern kernel (in this experiment, we set wM = 50). This is denoted as Isolated-KCCA in the sequel. Another extreme case is to modify the LE-KCCA algorithm so that the signal space is correlated with x and y separately (denoted 1D-KCCA). A third experiment is to modify both Gaussian and Mat´ern kernels to linear ones (Linear CCA). Experiments are performed in the same setting as for Figure 5. As can be seen in Figure 7, all three variants lead to degraded performance as expected.

Linear CCA has an accuracy that is lower than 60% on every test set, and so its results are not shown in the figure.

5 Conclusions and FutureWork

This paper focuses on using KCCA to improve the accuracy of location estimation in wireless LANs. We have found that kernel transformation and CCA allow the construction of an accurate mapping between the physical space and the signal space. One advantage is the higher accuracy obtained in localization with much less calibration effort. We use a Gaussian kernel for the signal space to adapt to the noisy characteristic of radio-propagation channels, and a Mat´ern kernel for the physical space. The advantage of KCCA is shown through extensive experimental tests in a realistic environment. In this paper, we constructed the mapping without considering the additional information of user motion profiles. In the future, we plan to take the user-motion profiles into account, which may lead to higher accuracy with even less calibration effort. Likewise, we wish to experiment more with other environmental and contextual factors to boost the performance.

Acknowledgment

We would like to thank Hong Kong RGC for supporting this work under grant HKUST6187 / 04E. We would also like to thank Jie Yin and Xiaoyong Chai for their effort in collecting the data and discussing the research problems.