Ye Tian
email: ye.tian@etu.upmc.fr

Bruce Denby
email: denby@ieee.org

Iness Ahriz
email: iness.ahriz@cnam.fr

Pierre Roussel
email: pierre.roussel@espci.fr

Gérard Dreyfus
email: gerard.dreyfus@espci.fr

Fast, Handset-Based GSM Fingerprints for Indoor Localization

Keywords: localization, indoor, fingerprint, machine learning, support vector machine I

Accurately localizing users in indoor environments remains an important and challenging task. The article presents new results on room-level indoor localization, using cellular Received Signal Strength fingerprints collected with a standard cellular handset programmed to perform fast scans of the 900 and 1800 Megahertz GSM bands as a user explores an indoor environment at a normal walking pace. Support Vector Machines are used to deal with the high dimensionality of the fingerprints. The study demonstrates that an appropriately programmed standard cellular handset can provide a simple, inexpensive solution for accurate room-level indoor localization.

INTRODUCTION

The inability of GPS receivers to function adequately in "urban canyon" and indoor environments has prompted a search for new techniques of indoor localization that can provide seamless and ubiquitous service for mobile users. Accurately and reliably locating persons and objects in indoor environments is a challenging, but attractive, goal that holds promise for a variety of location-based services and applications [START_REF] Küpper | Location-Based Services: Fundamentals and Operation[END_REF]. For many such services, room-level precision, in which the localization system discriminates between rooms rather than estimating coordinates per se, is an adequate goal; this is the approach that will be adopted here.

A variety of indoor localization techniques have been proposed. Methods based on Received Signal Strength (RSS), in Wi-Fi and Bluetooth networks, for example, or using infrared or acoustic signals, appear promising [START_REF] Ladd | On the feasibility of using wireless ethernet for indoor localization[END_REF][START_REF] Yang | Estimating location using Wi-Fi[END_REF][START_REF] Fang | Location fingerprinting in a decorrelated space[END_REF][START_REF] Fang | Indoor location system based on discriminantadaptive neural network in IEEE 802.11 environments[END_REF][START_REF] Hong | Localization algorithm in wireless sensor networks with network mobility[END_REF][START_REF] Kuo | A scrambling method for fingerprint positioning based on temporal diversity and spatial dependency[END_REF]. A drawback of these approaches, however, is that they necessitate the deployment and maintenance of an infrastructure, which can be time consuming and costly.

In addition to such short-range signals, indoor localization based on fingerprints from wide-area radiotelephone networks, such as GSM and CDMA, have also been proposed [START_REF] Otsason | Accurate GSM indoor localization[END_REF][START_REF] Ur Rehman | CILoS, a CDMA indoor localization system[END_REF][START_REF] Denby | High-performance indoor localization with full-band GSM fingerprints[END_REF][START_REF] Ahriz | Carrier relevance study for indoor localization using GSM[END_REF][START_REF] Ahriz | Full-band GSM fingerprints for indoor localization using a machine learning approach[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF]. The full coverage, near-ubiquity and relative stability of GSM networks may provide an attractive alternative for indoor localization.

Recent results have suggested that accurate and efficient indoor localization can be achieved using RSS information acquired from very large numbers of GSM channels [START_REF] Denby | High-performance indoor localization with full-band GSM fingerprints[END_REF][START_REF] Ahriz | Carrier relevance study for indoor localization using GSM[END_REF][START_REF] Ahriz | Full-band GSM fingerprints for indoor localization using a machine learning approach[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF]. Those studies, however, did not represent a genuinely practical solution since the RSS scanning devices operated without user intervention only at a small number of representative points within each room. In this work, we present a more realistic solution, in which a user can be localized at room level regardless of his exact position in a room. This is achieved using a handheld acquisition deviceactually a standard cellphone with a software modificationthat can obtain an RSS fingerprint of the entire 900 and 1800 MHz GSM bands in only about 300 milliseconds. This enables the collection of large amounts of data on a reasonable timescale, at points throughout the interiors of the rooms, rather than at only a few representative points, while moving at a normal walking pace.

Our results show that GSM fingerprints acquired in this way can be used to differentiate rooms of about 10 square meters size in some 94% of cases, indicating that the method may indeed be used as part of a simple, practical, inexpensive indoor localization system. The data collection procedure employed is described in section II, and the room classification algorithms in section III. Results are presented in section IV, while conclusions and future perspectives appear in the final section.

II. DATA COLLECTION AND DATASETS

The data used in the experiments was obtained by scanning the entire GSM band in 7 rooms of a 4 th floor laboratory building (steel frame, concrete and plaster walls) in central Paris, France. The data acquisition device used was the GSM trace mobile "TEMS Pocket", which is in fact a standard Sony Ericsson W995 mobile phone to which network investigation software has been added by the manufacturer [14]. In April of 2012, on a Saturday afternoon from 2pm to 6pm, 5500 scans (representing about one half hour of recording per room) were recorded in each of the 7 unoccupied rooms and manually labeled with the corresponding room numbers, as illustrated in Figure 1. Each scan contains the RSS of all 548 carriers in the GSM900 and GSM1800 bands, with values ranging from -117 to -38dBm. All scans were made via "random walks" in the 7 rooms with the TEMS Pocket handheld by the user. The exact positions of the individual scans within a room were not recorded; indeed all points in a given room are treated as belonging to that room, consistent with the room-level indoor localization approach adopted here.

CLASSIFICATION ALGORITHMS

The room-level indoor localization problem is considered as a multi-class classification problem, where each room is a class. As is usual in data-driven classification problems, the algorithm works in a two-stage process. The first stage is offline training, in which the equations of the discriminant functions are determined using training data with known labels. The second stage is on-line testing, in which, given a fingerprint that is not present in the training dataset, the classifier must provide the label of the room where it was measured, using the previously defined separating surfaces. Only the first off-line stage may require heavy computations, the second stage merely needs to compute the values of the discriminant functions. As a starting point for multi-class classification, a pairwise (also termed "two-class or "binary") classifier is introduced first.

A. Pairwise Classifier

Since the number of variables is very large and the size of the training set is relatively limited, Support Vector Machine (SVM) classifiers were deemed appropriate because of their built-in regularization mechanism [START_REF] Cristianini | Support Vector Machines and Other Kernel-Based Learning Methods[END_REF]. Consider a set of M examples of items belonging to either of two classes A and B, each example being described by a p-dimensional vector x i . Further assume that the examples are linearly separable, i.e. that there are, in descriptor space, linear surfaces of equation f(x) = 0 that separate all examples without error: f(x i ) > 0 for all examples i belonging to class A and f(x i ) < 0 otherwise. It can be proved that f(x) can be written under the form If the examples are not linearly separable, one resorts to nonlinear SVMs, whereby the separation surface is of the form 0 1 ( ) ( )

0 1 ( ) ( )       M i i i i f y x x x (1
      M i i i i f y K x x x (2)
where K(x, y) is a kernel function that must be such that the (M, M) matrix of general term K(x i , x j ) is positive semidefinite. As for linear SVMs, the  i are obtained by solving a quadratic optimization problem under constraints. If the constraints can be satisfied only if a large proportion of examples are support vectors, i.e. if the classifier has a large number of nonzero parameters, the constraint that all examples are classified without error and lie outside the margin can be relaxed; that "soft-margin" approach reduces the complexity of the classifier by performing a tradeoff between accuracy of classification of the training examples and ability to generalize; the price to pay is the introduction of a "regularization" constant whose value must be chosen appropriately.

There exists a repertoire of valid kernel functions, among which the RBF kernel [START_REF] Yang | Estimating location using Wi-Fi[END_REF] with appropriate width , is used in the present study. The values of  and the regularization constant are chosen by crossvalidation

To summarize, a GSM environment described by the fingerprint x is assigned to room A or room B according to the sign of f(x), defined by (1) or (2) depending for linear or nonlinear SVM classification respectively. x i is the fingerprint dataset entry i, i.e. row i of RSS, GSM900 or GSM1800 depending on the fingerprint used by the classifier.

The SVMs used in our study, both with linear and RBF kernels, were implemented using the Spider toolbox [START_REF]The Spider[END_REF].

In order to obtain a "baseline" result, nearest neighbor (1-NN) and k-nearest neighbor (k-NN) classifiers using the Euclidean distance in RSS-space were also implemented. The hyper parameter k was determined by the same cross-validation procedure as for the hyper parameters of SVMs.

B. Decision Rules for Multiclass Discrimination

When the discrimination problem involves more than two classes, it is necessary, for pairwise classifiers such as SVM, to define a method that allows combining multiple pairwise classifiers into a single multiclass classifier. This can be done in two ways: one-vs-one and one-vs-all.

1) One-vs-one

This approach decomposes the multiclass problem into the set of all possible one-vs-one problems. Thus, for an n-class problem, classifiers must be designed. Figure 2 illustrates the architecture associated with this method.

The decision rule in this case is based on a vote. First, the outputs of all classifiers are calculated. Now let C ij be the output of the classifier specializing in separating class i from class j. If C ij is 1, the tally for class i is increased by 1; if it is -1, the class tally of class j is increased by 1. Finally, the class assigned to the example is that having the highest vote tally.

A disadvantage of the one-vs-one technique is of course the increase in the number of classifiers required as compared to one-vs-all discussed below. In our case of seven classes, 21 classifiers are required, which still remains manageable.

C 1 vs C 2 C 1 vs C 3 C 1 vs C 4 C N-1 vs C N

Decision Rule

Predicted Class RSS of the example to be localized

2) One-vs-all

The one-vs-all approach consists of dividing the n-class problem into an ensemble of n pairwise classification problems, each of which is specialized in separating one class from all others. Figure 3 illustrates the procedure. In the first stage, each of the n classifiers is trained separately, and in the second stage, the following decision rule is applied : the outputs of all n classifiers are first calculated and, following the conventional procedure, the predicted class is taken to be that of the classifier with the largest magnitude of f(x) (relation ( 1) or ( 2)) [START_REF] Lee | Multicategory support vector machines: theory and application to the classification of microarray data and satellite radiance data[END_REF]. The one-vs-all technique is advantageous from a computational standpoint, in that it only requires a number of classifiers equal to the number of classes, in our case, 7.

C 1 vs all C 2 vs all C 3 vs all C N vs all

Decision Rule

Predicted Class RSS of the example to be localized As can be seen in the table, the SVM room classifiers give correct results about 94% of the time with no significant difference between linear and nonlinear kernels. As expected, results from nearest-neighbor classifiers are significantly poorer. We also note that the GSM900 (174 carriers) and GSM1800 (374 carriers) bands are complementary in that better localization accuracy is obtained when both bands are present in the fingerprint. In Figure 4 we also show how the accuracy improves with fingerprint size, for the linear one-vsall algorithm, by increasing the number of carriers in steps of 50, according to the ordered sequence numbers of the GSM carriers. V. CONCLUSIONS AND PERSPECTIVES We have presented an approach for indoor localization based on the use of RSS with very large numbers of GSM carriers, which has been tested on a dataset acquired in a laboratory building under realistic conditions. Data was collected in such a way as to explore the entire surface area of a room, using a standard cellular handset as the acquisition device. Experimental results demonstrate that out of a total of 17500 (2500*7) test fingerprints, the correct room label was obtained 94% of the time, thus indicating that the method can indeed serve as the basis for a simple, inexpensive indoor localization system. Future tests will involve studying how performance evolves over longer periods of time, as well as experimenting with different methods for combining the scans from the two GSM bands used, and investigating whether W-CDMA network data or other types of variables can also be incorporated into our scans. Also, the experiments reported here were performed during a weekend, so that the presence of people in the environment will need to be investigated. We note that only one TEMS pocket device was used in these tests; in the future, will want to perform tests with several terminals, to verify device independence of our results. Finally we intend to try integrating a priori information and notions of physical trajectories into our location estimation algorithms, via particle or other types of filters. Such an approach will allow considering the entire indoor environment, not only rooms.

Figure 1 .

 1 Figure 1. Layout of the laboratory where the data set was recorded

  ) where the  i (i = 0..M) are parameters whose values are estimated from the examples, y i = +1 if example i belongs to class A and y i = 1 otherwise. A linear SVM is a linear classifier such that the minimum distance between the separation surface f(x) = 0 and the examples that are closest to it (called support vectors) is maximum, thereby guaranteeing the best generalization given the available data. The values of the parameters  i of such a classifier are obtained by solving a quadratic optimization problem under linear inequality constraints. The support vectors are the only examples whose  i are nonzero.

Figure 2 .

 2 Figure 2. One-vs-one classification

Figure 3 .

 3 Figure 3. One-vs-all classification IV. RESULTS The performance of each classifier is presented as the percentage of correctly classified test examples. In our dataset, in each room, the first 3000 examples are used off-line for training the classifiers (quadratic optimization under constraints) and finding the appropriate values of the hyper parameters by cross-validation. The final 2500 of the 5500 scans make up the test set. Testing involves the computation of the sign of f(x) from relations (1) or (2), which is very fast. Experimental results are shown in Table I. The soft margin parameter C and RBF kernel parameter  are selected through cross-validation, giving C = 10 -4 in linear one-vs-one and linear one-vs-all classifiers, C = 10 -4 and  = 100 in RBF one-vs-one and one-vs-all classifiers. Results for 1-NN and k-NN classifiers are also given for comparison, where the parameter k was optimized by cross validation.

Figure 4 .

 4 Figure 4. Classification results as a function of fingerprint size In figure 5 we examine the effect of increasing the number of training examples for each of the 7 rooms, again using the linear one-vs-one algorithm. The figure plots the percentage of correct room classifications as a function of the training set size. We see that a rather substantial reduction in training set size gives only a very moderate degradation in performance. For example, 93% of the test examples were correctly classified using only 1000 training examples. This is a very interesting result as far as acquisition time is concerned, as the TEMS Pocket requires less than 10 minutes to record 1000 training examples.

Figure 5 .

 5 Figure 5. Classification results as a function of training set size Table II presents the confusion matrix for the case of the linear one-vs-one algorithm, showing how the mis-classified

TABLE I .

 I PERCENTAGE OF CORRECT CLASSIFICATION ON TEST SET

	Classifier	GSM900	Fingerprint Type GSM1800	Both Bands
	1-NN	56.2%	54.4%	62.7%
	k-NN	62.4%( k=77)	61.2%( k=21)	67.9%(k=14)
	Linear 1-vs-1	86.3%	83.2%	93.9%
	Linear 1-vs-rest	87.1%	85.0%	94.2%
	RBF 1-vs-1	85.5%	84.6%	93.0%
	RBF 1-vs-rest	87.2%	85.7%	94.1%

TABLE II .

 II CONFUSION MATRIX FOR 7 ROOMS CLASSIFICATION

	Predicted			True Class
	Class	1	2	3	4	5	6	7
	1	91.1%	4.7%	4.2%	0%	0%	0%	0%
	2	3.9%	94.9%	1.2%	0%	0%	0%	0%
	3	2.6%	1.7%	95.7%	0%	0%	0%	0%
	4	0%	0%	0%	96%	1.1%	0%	2.9%
	5	0%	0%	0%	0.8% 97.1%	0.5%	1.6%
	6	0%	0%	0%	0%	0%	99.9% 0.1%
	7	0%	0.6%	0%	4.1%	4.3%	3%	88%

ACKNOWLEDGMENT

The authors wish to acknowledge the support of the China Scholarship Council.


Ye Tian
email: ye.tian@etu.upmc.fr

Bruce Denby
email: denby@ieee.org

Iness Ahriz
email: iness.ahriz@cnam.fr

Pierre Roussel

Rémi Dubois

Gérard Dreyfus

Practical Indoor Localization using Ambient RF

Keywords: localization, indoor, fingerprint, transductive support vector machine I

The article presents a simple, practical approach for indoor localization using Received Signal Strength fingerprints from the GSM network, including an analysis of the relationship between signal strength and location, and the evolution of localization performance over time. Support Vector Machine regression applied to very high dimensional fingerprints does not reveal any smooth functional relationship between fingerprints and position. Classification using Support Vector Machines however provides very good results on discriminating different rooms in an indoor environment, albeit with performance that degrades over time. Transductive inference, introduced as a means of updating models to overcome degradation over time, provides hints that accurate indoor localization can be achieved by applying classification methods to cellular Received Signal Strength fingerprints, performance robustness being maintained via model updating and refining.

INTRODUCTION

Indoor localization systems are an important extension to Location Based Services (LBSs), for assisted living scenarios, tracking of Alzheimer's patients, and in more general situations [START_REF] Küpper | Location-Based Services: Fundamentals and Operation[END_REF]. As GPS receivers are unable to function in indoor environments, a variety of indoor localization strategies have been proposed to try to tackle this challenging task [START_REF] Ladd | On the feasibility of using wireless ethernet for indoor localization[END_REF][START_REF] Zhou | Indoor Elliptical Localization Based on Asynchronous UWB Range Measurement[END_REF][START_REF] Yang | Estimating location using Wi-Fi[END_REF][START_REF] Fang | Location fingerprinting in a decorrelated space[END_REF][START_REF] Fang | Indoor location system based on discriminantadaptive neural network in IEEE 802.11 environments[END_REF][START_REF] Hong | Localization algorithm in wireless sensor networks with network mobility[END_REF][START_REF] Otsason | Accurate GSM indoor localization[END_REF][START_REF] Ur Rehman | CILoS, a CDMA indoor localization system[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF][START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF]. Methods based on the measurement of Received Signal Strength (RSS) in RF networks such as Wi-Fi and Bluetooth networks, for example, have proven to be effective [START_REF] Ladd | On the feasibility of using wireless ethernet for indoor localization[END_REF][START_REF] Zhou | Indoor Elliptical Localization Based on Asynchronous UWB Range Measurement[END_REF][START_REF] Yang | Estimating location using Wi-Fi[END_REF][START_REF] Fang | Location fingerprinting in a decorrelated space[END_REF][START_REF] Fang | Indoor location system based on discriminantadaptive neural network in IEEE 802.11 environments[END_REF]. However, time and labor intensive deployment and maintenance of these networks is a drawback that reduces the impact of these techniques.

Aside from these specially deployed networks, indoor localization based on ambient radiotelephone networks, such as GSM and CDMA, has also been studied [START_REF] Otsason | Accurate GSM indoor localization[END_REF][START_REF] Ur Rehman | CILoS, a CDMA indoor localization system[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF]. In the past few years, methods based on the use of RSS fingerprints acquired from large numbers of GSM channels have appeared promising [10, and references therein]. Recent results also suggest that an appropriately programmed standard cellular mobile phone can provide a simple, inexpensive solution for accurate room-level indoor localization [START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF].

The studies proposed in [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF][START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF], however, were preliminary for two reasons. First, they did not attempt to explore the distribution of measured RSS values, or to discover a functional relationship between RSS and position in indoor environments. Secondly, no prescription was made for correcting for RSS drifts over time, which is a well-known challenge in RSS based systems, particularly for long-range signals [START_REF] Vw | Transferring localization models over time[END_REF]. Indeed, due to shadowing, multipath and environmental effects such as building geometry, network traffic, presence of people, and atmospheric conditions, RSS is expected to be nonlinear with distance, non-Gaussian, and time varying [START_REF] Ladd | On the feasibility of using wireless ethernet for indoor localization[END_REF], which can lead to performance degradation over time.

In this article, after an initial description of the data collection procedures used (section II), we turn our attention to seeking a functional relationship between GSM RSS and position, using Support Vector Machine (SVM) regression. The results, in fact, presented in section III, show that no such relationship exists for the indoor environments tested, indicating that interpolation/extrapolation schemes based on RSS measurements at a small number of points as in [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] will not be viable for localization. . On the other hand, because of the local nature of shadowing and multipath effects, RSS fingerprints acquired over entire rooms can potentially be useful for room-level classification, as proposed in [START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF]. The scheme is presented in section IV, using data collected during "random walks" that explore an entire area. This section also presents long term tests showing that the performance of our RSS based indoor localization method degrades over time. We introduce transductive inference, which uses new, incoming unlabeled data to update SVM classifiers as a means of reducing performance degradation caused by RSS drift. The use of small amounts of new labeled data as a model update scheme is also explored here. Overall conclusions and some perspectives appear in section V.

II. MEASUREMENT SITES AND DATASETS

Two types of datasets were collected, for regression and classification experiments, respectively, both recorded in a 4th floor laboratory building (steel frame, concrete and plaster walls) in central Paris, France (Fig. 1). The first set, which we shall call the regression set, was collected in a single room (office 7) using so-called machine-to-machine, or M2M, GSM/GPRS modules [START_REF]Telit GM862-GPS module[END_REF], which can be driven using standard and manufacturer-specific AT modem commands. We used 8 identical modules, with nominally identical specifications and technical parameters. During data collection, the M2M Figure 1. Layout of the laboratory where the datasets were recorded modules were placed at fixed positions, in a line, spaced at an interval of 0.6m, as illustrated in Fig. 1. A total of 600 GSM scans for each module were recorded over 5 working days. Each scan contains the RSS of all 548 carriers in the GSM900 and GSM1800 bands, and consists of RSS values ranging in value from -108dBm to -40dBm. All the scans were labeled manually with location from 0m to 4.2m indicating where the scan was made.

The second dataset, which will be used for SVM classification, was collected in 7 rooms of the laboratory as described in [START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF]. The data acquisition device in this case is a Sony-Ericsson mobile phone with embedded scanning software, which is able to obtain a scan of the entire GSM900 and GSM 1800 bands in about 300 milliseconds. Scans were recorded in each of the 7 rooms and manually labeled with the corresponding room numbers during "random walks". Four datasets were recorded during weekends over a period of six months in the same setting, hereafter called S1 (5000 scans in each room), S2 (2000 scans), S3 (1000 scans) and S4 (1000 scans).

III. POSITION FROM RSS

It was shown in [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] that the classification of RSS vectors recorded at fixed points works quite well. The objective here is to see if a regression method allows to measure locations at intermediate positions between the fixed points by finding a functional relationship between location and RSS in this indoor environment.

A. SVM Regression Algorithms

Since the number of variables is very large (548 carriers) and the size of the training set is relatively limited, SVM regression was deemed appropriate because of its built-in regularization mechanism [START_REF] Cristianini | Support Vector Machines and Other Kernel-Based Learning Methods[END_REF].

Consider a given dataset , where xi is the fingerprint vector at location i and yi is the coordinate of the location (assuming that 1-D localization is performed as described above). There exists a variety of Support Vector Regression (SVR) techniques, serving different purposes.

SVR  

, which was used in our experiments, aims to find a parameterized function ( , ) f x θ such that prediction errors   , i i yf  x θ do not exceed a given value  for all elements of the training set, and, at the same time, is as regular as possible, i.e. does not wiggle unnecessarily [START_REF] Smola | A Tutorial on Support Vector Regression[END_REF]. Assume that we are looking for a linear relationship between the RSS fingerprint and the location. The function has the form: ( , )

f b    x w x θ ( 1
)
where

  T b w θ =
. The parameters are sought as solutions to the constrained optimization problem:

  2 1 minimize 2 subject to ii yb      w wx (2)
The optimal solution, if it exists, can be shown to be of the form 0 1 ( ) ( )

n i i i i f y       x x x (3)
where 0 and all the i are solutions of a constrained quadratic

n ii i i i i i i i ii C yb b y i                         w wx wx (4)
where C is a hyperparameter called "regularization constant".

If we want to look for a non-linear relationship between the RSS fingerprint and the location, non-linear regression can be realized by first performing a nonlinear transformation of the variables that defines a more suitable feature space, in which linear regression is performed. The final solution is in the form

  0 1 ( ) , n i i i i f y K      x x x (5)
where K(., .) is called the kernel function. In our experiments, linear and nonlinear regression (using Gaussian and Polynomial kernels) were performed, using the Spider toolbox [START_REF]The Spider[END_REF].

B. Results

The results of SVRs are estimated through the mean squared localization error where yk is the position of measuring device k, xik is the RSS vector measured during scan i taken at location k, and  -k is the parameter vector found by training from the data pertaining to all locations except location k.

The results for linear and non-linear regressions are shown in Table I. The soft margin parameter C, polynomial degree d and Gaussian kernel parameter  were selected through crossvalidation. Results from linear least squares regression (LS-Regression) are also given for comparison.

As shown in the table, the mean positioning error of all the regression methods is so large as to be unexploitable. The regression error is approximately equal to the average distance between the 8 locations, meaning that no linear or non-linear relationship between RSS and the position in a small indoor environment is evident. This appears to rule out using full-band RSS GSM vectors obtained in this way to interpolate between fixed positions in an indoor localization method.

IV. ROOM LEVEL CLASSIFICATION AND RSS DRIFT

An alternative scheme, first introduced in [START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF], is to perform room-level classification based on RSS measurements made during "random walks". In this case, we use classifiers to perform room-level indoor localization, where each room is a class. Data-driven classification problems are often solved in two stages: off-line training; and on-line testing. In the off-line training stage, discriminant functions are determined using training data and known labels, while in the on-line testing stage, a new test fingerprint is presented to the classifier and given a label based on the discriminant functions.

The RSS-based room level SVM classifiers in [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] gave good results when training and test data were obtained over the same one-month period. Here, we explore the time dependence of the "random walk" approach, proposing transductive inference to continuously adjust a discriminant function with newly collected unlabeled data, in order obtain an updated classifier.

A. SVM Classifier

SVM classifiers were used in our experiments, since they are deemed appropriate to deal with the high dimensional RSS fingerprints for the same reasons as described above for SVRs.

n i i i i f y       x x x (6)
where the i (i = 0 n) are parameters whose values are estimated from the examples; yi = +1 if example i belongs to class A and yi = 1 otherwise.

If the examples are not linearly separable, a "soft-margin" approach can be used to reduce the complexity of the classifier by introducing slack variables i  and performing a tradeoff between accuracy of classification of the training examples and ability to generalize; the price to pay is the introduction of a "regularization" constant C whose value must be chosen appropriately.

B. Transductive SVM Classifier

Transductive SVMs take unlabeled test examples into account and adjust the separating surface to separate both training examples and test examples with maximum margin. For a linearly separable data case, this leads to the following optimization problem [START_REF] Joachims | Transductive Inference for Text Classification using Support vecter Machines[END_REF]:

    2 ** 1 minimize 2 1 subject to , 1 ii jj yb ij yb             w wx wx (7)
where * j x is the unlabeled data and * j y is the label corresponding to * j x

given by TSVMs. Therefore, minimization must be performed with respect to w, b, xj * and yj * , j = 1…N, by contrast to standard SVMs where minimization must be performed with respect to w and b only. To be able to handle non-separable data, slack variables i  are introduced as in standard SVM classifiers. Algorithms for solving this optimization problem are described in [START_REF] Joachims | Transductive Inference for Text Classification using Support vecter Machines[END_REF][START_REF] Chen | Learning with Progressive Transductive Support Vector Machine[END_REF].

The transductive SVMs used in our study, were implemented using SVM light [START_REF]SVMlight Support Vector Machine[END_REF].

C. Results, and Comparison to "Re-Training"

Experimental results are shown in Table II. The performance is presented as the percentage of correctly classified test examples. The results shown on the first row were published in [START_REF] Tian | Fast, Handset-Based GSM Fingerprints for Indoor Localization[END_REF] and reproduced here for comparison. The first 100 unlabeled test examples of each room in S1, S2 and S3 sets were used for TSVM training to adjust the model, the remaining examples were used for testing. In SVM classifiers, we use the model trained on set S1 to test the test data in sets S2, S3 and S4. Only linear one-vs-all multi-class scheme was used because this method gave the best performance when testing on set S1.

As can be seen in Table II, when building the classifier with set S1 and testing it on sets S2, S3 and S4 taken in different time periods, the performance varies dramatically, from about 94% for "fresh" data (S1 set), down to as low as 32% (S4 set). However, by using only 100 new unlabeled test examples of each room with the TSVM, a substantial amount of the lost performance can be recovered, with accuracies up to 78.4%. The first 100 scans of S3

The last 900 scans of S3 Linear one-vs-all 83.3%

The first 100 scans of S4

The last 900 scans of S4 Linear one-vs-all 77.4%

The TSVM approach is interesting because it presents a way of recovering some of the performance loss due to RSS drift, at the cost only of obtaining some recent unlabeled RSS measurements. In practice, such data might be obtained from scans performed on the handsets of users of the localization system, but without the need to manually label the data. Though the improvement obtained with the TSVM is still not sufficient, the results nevertheless suggest that any scheme that keeps the classifier model "current", by tracking the evolution of the RSS values, should be of interest to us. This hypothesis is supported by Table III, which presents the results of training a new classifier "from scratch" based on a small number of new labeled scans of each room. In this scenario, "hand" labeling of the update data is necessary, but could perhaps be performed by specially designated employees, or by volunteers in exchange for some "reward" (i.e., crowdsourcing). The table shows that even if the current model is too outdated to give good performance, the S3 and S4 sets for example, it can be trained using only a small amount of labeled data and give substantially improved performance.

V. CONCLUSIONS AND PERSPECTIVES

In a study of ambient RSS distribution in an indoor environment using SVM regression, no smooth functional relationship could be discovered between GSM RSS and position for the indoor environment tested, implying that interpolation-based techniques are not likely to be successful. The use of ambient GSM RSS-based classifiers trained with data collected throughout the areas of rooms, however, presents a viable alternative, and experimental results show that the percentage of correct room labeling can be up to 94% if the model is used before significant RSS drift sets in. In order to cope with performance degradation caused by RSS drift over time, transductive inference was introduced to update the SVM classifiers with new unlabeled data. When tested on data sets collected over 6 months, this approach proved capable of restoring a significant part of the lost performance. The use of small amounts of current labeled data to create "current" room classifiers also appears to be a promising approach, even if performance still needs to be improved.

In future work, we will continue to strive for a continuously updatable, high-performance indoor room classifier. We also intend to investigate the use of W-CDMA network data in our measurements.

  optimization problem. If such a solution does not exist, slack variables i  and * i  can be introduced to relax the constraints, allowing some examples of the training set to be predicted with an error larger than . The problem becomes:

  Consider a set of n examples of items belonging either to class A or class B, each example being described by a pdimensional vector xi. Further assume that the examples are linearly separable, i.e. that there exists a hyperplane of equation f(x) = 0 that separate all examples without error: f(xi) > 0 for all examples i belonging to class A and f(xi) < 0 otherwise. It can be proved that f(x) can be written under the form

TABLE I .

 I

	REGRESSION RESULTS
	Regression Method	Mean Squared Localization Error
	Linear LS-Regression	2.3m
	Linear SVM Regression	1.8m
	Polynomial SVM Regression (d = 5)	1.3m
	Gaussian SVM Regression	2.4m

TABLE II .

 II COMPARISON OF SVM AND TSVM

	Test Set	Training Set	SVM	TSVM
	S1		S1	94.2%	-
	S2		S1	60.4%	78.4%
	S3		S1	39.7%	58.8%
	S4		S1	32.3%	49.6%
	TABLE III.	RESULTS OF RE-TRAINING THE MODEL
	Training Data		Test Data	Algorithm	Result

ACKNOWLEDGMENT

The authors wish to acknowledge the support of the China Scholarship Council.