Co-Localization from Labeled and Unlabeled Data Using Graph Laplacian

1 Introduction

Accurately tracking mobile devices in wireless networks using radio-signal-strength (RSS) values is a useful task in robotics and activity recognition. It is also a difficult task since radio signals usually attenuate in a highly nonlinear and uncertain way in a complex environment where client devices may be moving. Existing approaches to RSS localization fall into two main categories [Ferris et al., 2006]: (1) radio propagation models [Maligan et al., 2005; Savvides et al., 2001], which rely on the knowledge of access point locations; (2) statistical machine learning models [Nguyen et al., 2005; Letchner et al., 2005; Bahl and Padmanabhan, 2000], which require a large amount of costly calibration.

However, in cities and large buildings where wireless networks are set up by different network suppliers, it is not easy to ask them to share the location information of all access points for business or privacy reasons. Besides, a mobile device may also want to locate access points for obtaining stable connections or to spot them in hostile areas. In all these cases, sufficient calibration (labeled) data on mobile devices and access points may not always be available due to the lack of GPS coverage or costly human effort.

In this paper, we address the problem of simultaneously recovering the locations of both mobile devices and access points, a problem which we call co-localization, using labeled and unlabeled RSS data from both mobile devices and access points. We take two steps for solving this problem.

In the first step, we assume that only unlabeled RSS data are given. In such case, we show that the problem can be solved by Latent Semantic Indexing (LSI) or Singular Value Decomposition (SVD) [Deerwester et al., 1990], techniques that are popular in information retrieval. Consequently, the relative locations of APs and mobile device trajectory can be determined. In the second step, we assume that a small amount of labeled RSS data from mobile devices and access points are given. To determine the absolute locations of the devices and access points, we apply a semi-supervised algorithm with graph Laplacian and manifold learning [Chung, 1997; Belkin and Niyogi, 2003; Ham et al., 2005]. Finally, we provide a unified framework for both the above unsupervised and semi-supervised solutions.

We tested our co-localization algorithms in different indoor environments using both static and mobile client devices. We also tested the algorithms with different hardware such as 802.11 Wireless Local Area Networks (WLAN), Wireless Sensor Networks (WSN) and Radio Frequency Identifiers (RFID). Experimental results showed that we can achieve a higher accuracy with much less calibration effort in different environments, motion patterns and with different hardware.

2 RelatedWorks

Propagation-model-based approaches are widely used for location estimation due to their simplicity and efficiency [Letchner et al., 2005]. These methods usually assume that access points are labeled, e.g., their locations are known. They estimate the distance of the mobile devices relative to some fixed access points based on signal strengths through models that predicts the signal propagation patterns [Savvides et al., 2001]. Researchers have also used Bayesian models to encode the signal propagation pattern [Letchner et al., 2005; Maligan et al., 2005] and infer the locations using Monte Carlo methods [Thrun et al., 2001]. A drawback of propagation-model-based methods is that these models may become inaccurate in a complex domain.

An alternative is to apply machine-learning-based algorithms. With these algorithms the labels of access points need not be known. Instead, they usually rely on models that are trained with RSS data collected on a mobile device and are labeled with physical locations [Letchner et al., 2005; Nguyen et al., 2005; Ni et al., 2003; Bahl and Padmanabhan, 2000]. The training data are usually collected offline. These signal values may be noisy and nonlinear due to environmental dynamics. Therefore, sufficient data shall be collected to power algorithms for approximating the signal to location mapping functions using K-Nearest-Neighbors [Bahl and Padmanabhan, 2000], kernels [Pan et al., 2005], Bayesian filters [Letchner et al., 2005] and Gaussian processes [Ferris et al., 2006]. A drawback of these models is that they may require much calibration effort.

A viable approach is to use both labeled and unlabeled data. For example, Bayesian frameworks can be applied to use both labeled and unlabeled access points [Letchner et al., 2005] and mobile device trajectory [Chai and Yang, 2005]. Our work differs from the above in that we treat mobile devices and access points in a completely symmetric manner: we use both the labeled and unlabeled data from mobile devices and access points to recover the locations of both of them rather than locating the mobile devices only. To the best of our knowledge, this is the first such work.

3 Methodology

3.1 ProblemDefinition

Consider a two-dimensional co-localization problem. Assume that a user holds a mobile device and navigates in an indoor wireless environment C ⊆ R2 of n access points, which can periodically send out beacon signals. At some time ti, the RSS values from all the n access points are measured by the mobile device to form a row vector si = [si1 si2 . . . sin] ∈ Rn. A sequence of m signal strength vectors form an m × n matrix S = [s′1 s′2 . . . s′m]′ , where "prime" is used to denote matrix transposition. Here, the locations of some access points and the mobile devices at some time t are known or labeled, while the rest are unlabeled.

Our objectives are stated as follows: We wish to estimate the m × 2 location matrix P = [p′1, p′2, . . . , p′m]′ where pi = [pi1 pi2] ∈ C is the location of the mobile device at time ti and the n × 2 location matrix Q = [q′1 , q′2 , . . . , q′n ]′ where qj = [qj1 qj2] ∈ C is the location of the j access points. Our objectives are to determine the locations of all of the remaining access points and the trajectory of the mobile device. We call this problem co-localization.

Example 1 As an example, Figure 1(a) shows an indoor 802.11 wireless LAN environment of size about 60m× 50m. It is equipped with n = 5 access points. A user with an IBM T42 notebook that is equipped with an Intel Pro/2200BG internal wireless card walks from A through B, . . . , E to F at time tA, tB, . . . , tF . m = 6 signal strength vectors are extracted and the 6 × 5 matrix S is shown in Table 1. By walking from A to B, . . . , E and finally to F in the hallways, we collected 500 signal strength vectors from 5 access points. Note that the blank cells denote the missing values, which we can fill in a small default value, e.g., -100dBm.

Our task is to estimate the trajectory matrix P of the mobile device at all times and to determine the location matrix Q of the access points AP1, AP2, . . . , AP5.

3.2 SVD-based Relative Co-Localization

Given unlabeled data only, we can determine the relative locations of the mobile device and the access points. This problem is called relative co-localization. Intuitively, we may observe the following characteristics of the data (see Table 1):

(All values are rounded for illustration)

1. Considering two rows of the data, the mobile device at two different time may spatially close to each other if their signal strengths are similar when received from most access points, e.g., the time tA and tE.
2. Considering two columns of the data, two access points may be spatially close to each other if the signal strengths to the mobile device be similar most of the time, e.g., AP1 and AP4.
3. Considering a single cell sij of the data, the mobile device and the j access point may spatially close to each other at time ti if the signal be strong, e.g., the mobile device is close to AP3 at time tD.

The above observations enabled us to relate co-localization with information retrieval. Not surprisingly, the colocalization is closely related to the Latent Semantic Indexing (LSI) [Deerwester et al., 1990]. In this view, we treat an access point as a term and a mobile device at some time as a document. The above three observed characteristics would be mapped to the similarities of document-document, termterm and document-term respectively. Estimating the positions of the mobile device and the access points corresponds to discovering the latent semantics of documents and terms in some concept space.

More specifically, we can estimate the relative coordinates by performing Singular Value Decomposition (SVD).

1. Transform the signal matrix S = [sij]m×n to a nonnegative weight matrix A = [aij ]m×n by a linear function aij = sij - smin where smin is the minimal signal strength detected, e.g., the noise level or -100dBm.
2. Normalize the weight matrix by AN = D-1/2 1 AD-1/2 2 . Here, D1 and D2 are both diagonal matrices such that D1 = diag(d11, d12, . . . , d1m) where d1i = ∑nj=1 aij and D2 = diag(d21, d22, . . . , d2n) where d2j = ∑mi=1 aij .
3. Perform SVD on the normalized weight matrix by AN ≈ Um×rΣr×rV ′n×r . The columns of Um×r = [u1 . . . ur] and Vn×r = [v1 . . . vr] are the left and right singular vectors. The singular values of the diagonal matrix Σr×r = diag(σ1, σ2, . . . , σr) are ranked in nonincreasing order.
4. The (latent) location matrices of the mobile device P and that of the access points Q can be estimated using P = D-1/2 1 [u2 u3] and Q = D-1/2 2 [v2 v3]. Note that we skip the first singular vectors u1 and v1 which mostly capture some constant since matrix AN is not centering.

(a) WLAN Test-bed

-0.08 -0.06 -0.04 -0.02

0

0.02

0.04

0.06

-0.06 -0.04 -0.02

0

0.02

0.04

0.06

0.08

(b) (Nonlinear) SVDCo-Localization

y (unit : m)

x (unit : m)

(c) Manifold-based Co-Localization

Figure 2: 802.11Wireless LAN test in an indoor environment

As an example, after performing SVD on data in Example 1, we obtained the latent coordinates of the mobile device and the access points, which are shown in Figure 2(a). In this example, it is easy to see that the hallway structure is not well preserved by comparing the true location sequence shown in Figure 1(a). This is because SVD assumes a linear subspace, while the correlation of RSS values and distance to APs is often nonlinear [Nguyen et al., 2005].

A better solution is using Kernel SVD or simply transforming signal strengths to weights by some nonlinear function. More specifically, we transform the signal matrix S = [sij ]m×n to a new weight matrix A = [aij ]m×n by a Gaussian kernel aij = exp(-|sij - smax|2 /2σ2A) where smax is the maximal signal strength detected, e.g., the signal strength around an access point or -30dBm. Figure 2(b) plots the co-localization result using P and Q. Intuitively, the reconstructed hallway structure and the locations of access points are better than that shown in Figure 2(a) while referring to the ground truth illustrated in Figure 1(a).

3.3 Manifold-based Absolute Co-Localization

When the physical locations of some access points and the mobile device at some time are known, we can ground the unknown coordinates by exploiting the geometry of the signal distribution. More specifically, we can use manifold-based learning, which generally assumes that if two points are close in the intrinsic geometry of the marginal distribution, their conditional distributions are similar [Belkin et al., 2005; Ham et al., 2005]. This implies that the mobile device shall be spatially close to each other if their signal vectors are similar along some manifold structure [Patwari and Hero, 2004; Pan et al., 2006]. For example, the mobile device at time tA and tE shall be spatially close to each other (Figure 1(a)) since their signal strengths are similar (Table 1).

When the manifold assumption holds, the optimal solution is give by f ∗ = arg min Σli=1 |fi - yi|2 +γf T Lf [Ham et al., 2005] where the first term measures the fitting error and the second term poses the smoothness along the manifold and L is the graph Laplacian [Chung, 1997]. For our problem, the objective is to optimize:

Here, P is the coordinate matrix of the mobile device to be determined; JP = diag(δ1, δ2, . . . , δm) is an indication matrix where δi = 1 if the coordinate of the mobile device at time ti is given and otherwise δi = 0; YP = [y′1 , y′2 , . . . , y′m]′ is an m× 2 matrix supplying the calibration data where yi is the given coordinate of the mobile device at time ti if δi = 1 and otherwise the value of yi can be any, e.g., yi = [0 0]; γP controls the smoothness of the coordinates along the manifold; LP = DP - WP is the graph Laplacian; WP = [wij]m×m is the weight matrix and wij = exp(-‖si - sj‖2/2σ2P ) if si and sj are neighbors along the manifold and otherwise wij = 0; DP = diag(d1, d2, . . . , dm) and di = ∑mj=1 wij .

Setting the derivative of Equation (1) to zero, the optimal solution is given by [Ham et al., 2005]

Similarly, the coordinates of the access points are given by

and

where LQ = DQ -WQ is the graph Laplacian, WQ is the weight matrix and DQ is constructed from WQ.

Thus, when the locations of the mobile device and the access points are partially known, we can co-localize them by solving Equations (2) and (4) respectively. Alternatively, we can combine them into a single equation as

Here, R = [P ′ Q′ ]′ is the coordinate matrix of the mobile device and the access points; Y = [Y ′P Y ′Q]′ gives the label information; J = [ JP 0 0 JQ ] is the indicationmatrix; LB = [ LP 0 0 0 ] and LC = [ 0 0 0 LQ ] are the graph Laplacians.

In practice, the graph Laplacians LB and LC in Equation (5) are normalized [Belkin and Niyogi, 2003; Shi and Malik, 2000]. Figure 2(c) shows an example of the manifoldbased co-localization when the locations of the mobile device at time tA, tB, tC, tD, tE, tF and the access pointsAP2, AP3, AP4 are known. As can be seen, the trajectory of the mobile device is well grounded when compared to the ground truth shown in Figure 1(a). However, due to the limited number of access points, their locations are estimated badly, e.g., the location of AP5.

In the following, we will combine the SVD-based and the Manifold-based co-localization together so that we can align the mobile device and the access points to the ground truth and to each other.

3.4 AUnifying Framework

So far, we have formulated the unsupervised co-localization based on SVD and the semi-supervised co-localization based on the manifold assumption using Equation (5) by exploiting the correlation within the mobile device and the access points. In this section, we integrate them through a unifying theory. Essentially, performing SVD on AN is equivalent to solving the generalized eigenvalue problem [Dhillon, 2001]

where LA = DA-WA is the graph Laplacian [Chung, 1997], WA = [ 0 A A′ 0 ] and DA = [ D1 0 0 D2 ]. The eigenvalues of the diagonal matrix Λ = diag(λ1, λ2, . . . , λm+n) are ranked in non-decreasing order. Z = [z1, z2, . . . zm+n] are the eigenvectors. [P ′ Q′ ]′ = [z2 z3]. Note that we skip the first eigenvector z1 since the solution is trivial. Furthermore, it is interesting to see that we have λi = 1 - σi where i = 1, 2, . . . , r [Dhillon, 2001]. Detailed analysis and comparison of LSI, SVD and graph Laplacian can be found in Latent Semantic Indexing [Deerwester et al., 1990; Dhillon, 2001; Hendrickson, 2006].

Putting these together, our objective is to optimize:

The first term measures the fitting error and the second term constrains the smoothness among the mobile device and the access points. L = γALA + γBLB + γCLC = D - W . The solution is given by:R∗ = (J + γL)-1JY (8)

In practice, the graph Laplacian L is normalized. An example of applying the above co-localization algorithm using Equation (8) is shown in Figure 3 when the locations of the mobile device at time tA, tB, tC, tD tF and the access point AP4 are known. As can be seen, most of the locations are correctly recovered while using less calibration data than that in Figure 2(c).

4 Experiments

We evaluated the performance of the co-localization algo-

rithm on three sets of different devices and test-beds: (1) Wireless Local Area Network (WLAN): a person carrying an IBM c© T42 notebook, which is equipped with an Intel c© Pro/2200GB internal wireless card, walked in an indoor environment of about 60m× 50m in size as shown in Figure 1(a). A total of 2000 examples are collected with sample rate 2Hz. The ground-truth location labels are obtained by referring to landmark points such as doors, corners and dead-ends. The localization area is composed by one-dimensional hallways. (2) Wireless Sensor Network (WSN): We used a number of MICA2 sensors from Crossbow c© for experiments. As can be seen from Figure 1(b), 8 static nodes (AP) were placed in a room of size 5m × 4m. One mobile node (MD) was attached on the top of a robot that moved around freely in this domain. A total of 4000 examples are collected with sample rate 2Hz. The ground-truth location labels of the mobile node were supported by the cameras deployed on the ceiling. The localization area is a two-dimensional plane.

(3)Radio Frequency Identification (RFID): We used 4 Mantis readers (AP) and 30 tags (MD) from RF Code c©. They were all deployed as stationary nodes, which is shown in Figure 1(c). A total of 2000 examples were collected. The ground truth locations were marked down manually.

We summarize our three experimental setups in Table 2.

For comparison, we also run the following baseline algorithms (1) LANDMARC, a nearest-neighbor weighting based method designed for RFID localization [Ni et al., 2003]; (2) Support Vector Regression (SVR), a simplified variant of a kernel-based method used for WSN localization [Nguyen et al., 2005]; (3) RADAR, a K-Nearest-Neighbor method for WLAN localization [Bahl and Padmanabhan, 2000].

In each experiment, we randomly pick up 500 examples for training and the rest for testing. The training data is further split into labeled and unlabeled parts. The results shown in Figure 4 are averaged over 10 repetitions for reducing statistical variability. All results are measured in relative error distances, which are error distances in percentage while referring to the maximal error distance in each figure for easy comparison. All parameters are determined from a validation subset. LANDMARC, RADAR and SVR use the labeled part of training data only.

In contrary, the co-localization method used both labeled and unlabeled data. We will show how our algorithm benefits from the additional unlabeled data and reduces calibration effort. In all, we tested on two configurations for the co-localization method: (1) 'Co-Localization no AP' uses partially labeled data from mobile devices for training, in which we tries to recover the locations of the access points; and (2) 'Co-Localization with AP' repeats the same experiments with the locations of all access points known.

Figures 4(a), 4(b) and 4(c) show the localization error of different mobile devices by varying the number of labeled examples in a training subset which size is fixed to be 500. The three figures could be read in two directions. First, if we compare the results vertically in each figure, we can see how the unlabeled data help improve the result in the proposed methods. For example in Figure 4(c), most compared methods have a relative error distance of around 80% when using 50 labeled examples. In contrary, the proposed methods have an error of around 40% by employing additional 450 unlabeled examples. Secondly, if we compare the results horizontally in each figure, we can find how our methods reduce calibration effort. For example in Figure 4(a), most compared methods have a relative error distance of around 60% when all 500 examples are labeled. The proposed 'Co-Localization with AP' has a similar performance when using 50 labeled and 450 unlabeled examples. We save the calibration effort.

We found that the mobility of the mobile device and the environment complexity are two main factors that affected the performance of the co-localization algorithm. In a static and plane-shaped test-bed (Figure 4(a)), the radio signals are less noisy and the 'Co-Localization no AP' configuration demonstrated similar performance as RADAR, LANDMARC and SVR when the number of labeled examples is small. In a mobile and complex environment, as shown in (Figure 4(c)), the radio signal is more noisy and the 'CoLocalization no AP' performed much better and more robust than the compared methods. We have also tried some other combinations of experiments that led to a similar conclusion, such as using RFIDs in a mobile scenario.

While comparing the results of 'Co-Localization no AP' and 'Co-Localization with AP' in Figures 4(a), 4(b) and 4(c), we can find that knowing the locations of access points is more helpful for localizing the mobile devices in a static and planar scenario (Figure 4(a)) than in a mobile and complex environment (see Figure 4(c)).

Similarly, we can see from Figures 4(d), 4(e) and 4(f) that knowing the locations of mobile devices are more helpful for localizing access points in a static and plane-shaped scenario rather than a mobile and complex environment.

5 Conclusion

We have developed a novel graph Laplacian approach to solve the problem of simultaneously recovering the locations of both mobile devices and access points. In our co-localization framework, we find the relative locations of mobile devices and access points by exploiting a SVD based method, and find the absolute locations using a small collection of labeled data through graph Laplacian methods. Our extensive experiments in three different configurations showed that we can achieve high performance with much less calibration effort as compared to several previous approaches. The significance of the work is that we can leverage both the knowledge of the access point locations and the mobile device trajectories to obtain more accurate localization. Indeed this is one of our future works. Besides, we would try to evaluate the performance in a large-scale and dynamic environment, e.g., in a city level and in different time. We may also vary more parameters such as number of access points and their deployment density and study the robustness.

Acknowledgement

We thank NEC China Lab (NECLC05/06.EG01) for their generous support of this research.