Keywords: 6, 9 WiFi data acquisition program interfaces, path

GPS has long been used for accurate and reliable location determination, navigation and time synchronization in outdoor environments. However, since GPS signals are too weak to penetrate building roofs, walls and other objects, it cannot operate in indoor environments, which suggests developing indoor localization methods that can provide seamless and ubiquitous services for mobile users.

In this thesis, indoor localization is realized making use of received signal strength fingerprinting technique based on the existing GSM networks, which can be adopted by standard mobile phones and eliminates the time and labor consuming deployment and maintenance of network infrastructures. A room is defined as the minimum location unit, and support vector machine are used as a mean to discriminate the rooms by classifying received signal strengths from very large number of GSM carriers. At the same time, multiple sensors, such as accelerometer, gyroscope and magnetic field, are widely available for modern mobile devices, which provide additional information that helps location determination. The hybrid indoor localization that combines the GSM fingerprinting results with mobile sensor information and building layout constraint using a particle filter provides a more accurate and fine-grained localization result.

The approaches were tested on datasets acquired under realistic conditions in both a laboratory building and a railway station. Experimental results demonstrate that correct room number can be obtained 94% of the time provided the derived model is used before significant received signal strength drift sets in. Furthermore, if the training data is sampled over a few days, the performance of the indoor room-level localization system can remain stable exceeding 80% over a period of months, and can be further improved with various post-processing techniques. Moreover, including the mobile sensors allows the system to localize the mobile trajectory coordinates with high accuracy and reliability.

Indoor localization approaches in this thesis rely only on GSM received signal strength Abstract fingerprint and multiple mobile sensors that are easy to obtain with the growing popularity of mobile phones, and in this sense can be considered ready for a practical implementation. vi Résumé L'objet de cette thèse est l'étude de la localisation et de la navigation à l'intérieur de bâtiments à l'aide des signaux disponibles dans les systèmes mobiles cellulaires et, en particulier, les signaux radio-fréquences GSM. Le système GPS est aujourd'hui couramment utilisé en extérieur pour déterminer la position d'un objet mobile, fournir une aide à la navigation et permettre la synchronisation temporelle. Mais les signaux GPS ont une puissance trop faible pour traverser les toits et les murs des bâtiments et ils ne sont pas adaptés à la localisation en intérieur. Il est donc nécessaire d'envisager d'autres méthodes pour pouvoir fournir aux utilisateurs de systèmes mobiles ces services de manière uniforme dans le temps et dans l'espace. Dans cette thèse, la localisation en intérieur est obtenue à partir de la technique des «empreintes» de puissance des signaux reçus sur les canaux utilisés par les réseaux GSM. Ces signaux sont bien évidemment reçus par tous les téléphones cellulaires ainsi qu'un certain nombre de tablettes, et ils présentent l'avantage d'être disponibles sans qu'il soit nécessaire d'installer ou d'entretenir une infrastructure spécifique. La localisation est réalisée à l'échelle de la pièce. La classification est e ectuée à partir de machines à vecteurs supports et les descripteurs utilisés sont les puissances de toutes les porteuses GSM. De nombreux autres capteurs, tels qu'accéléromètre, gyromètre, magnétomètre, disponibles dans les téléphones portables, fournissent également des informations qui peuvent être utilisées pour déterminer la position ou le déplacement de l'utilisateur. Ces informations, ainsi que la cartographie de l'environnement, sont associées aux résultats obtenus à partir des «empreintes» GSM au sein de filtres particulaires. Il est ainsi possible d'obtenir une localisation plus précise, sous forme de coordonnées continues, et non plus seulement au niveau de la pièce. Les méthodes proposées ont été testées en conditions réelles sur des données recueillies d'une part dans les sept pièces du laboratoire où s'est déroulée cette thèse et d'autre part, dans une gare. Les résultats obtenus montrent que la technique de localisation basée sur les empreintes Résumé GSM seules permet de déterminer la pièce correcte dans 94% des cas lorsque les données sont collectées sur une durée courte. Il est également montré que les performances restent stables pendant plusieurs mois, de l'ordre de 80%, si les données d'apprentissage sont enregistrées sur quelques jours. De plus, si l'on associe la cartographie du lieu aux données de classification au sein d'un filtre bayésien, dans le cadre d'un suivi de déplacement, les résultats sont encore améliorés. Enfin les informations issues des autres capteurs permettent d'obtenir les coordonnées de la trajectoire du système mobile avec une bonne précision et une bonne fiabilité. L'approche de localisation en intérieur adoptée dans cette thèse repose uniquement sur l'utilisation des empreintes de puissance des signaux GSM et des informations fournies par les capteurs embarqués dans la plupart des téléphones portables. Elle peut donc permettre d'en envisager la réalisation pratique et l'utilisation courante.

List of Figures

Location based applications and services

Localization is the determination of the location of a mobile target, which is a basic need for a lot of scenarios and supports a variety of services and applications based on location information.

Location Based Services (LBS) can be defined as services that integrate a mobile device's location or position with other information in order to provide added value to a user [START_REF] Schiller | Location-based services[END_REF]. Figure 1.1 illustrates the categories of diverse LBS.

Among these services and applications, the digital map is the most fundamental yet most important service, which has become a native application in most smart phones. In addition to the basic map-related services like localization, navigation, routing and tracking, more importantly, it provides an interface upon which a great majority of LBS are based. Another important application of localization is information services, which allow mobile users to easily obtain the local information of interest such as weather, tra c, catering and location-based to-do list and reminders. Furthermore, content providers, public agencies and advertisers can deliver content, information and advertisements in a more targeted way to audiences based on their locations.

Location based map services and information services are often linked to each other, supporting a further variety of LBS.

Public safety, such as emergency services of police, fire and ambulance, have turned out to be a very important application field. Localization techniques facilitate such services in locating the site of the incident and people waiting for rescue, tracking and navigating security agents and trapped people, which can save a lot of time and resources.

Every year, an estimated 240 million emergency "911" calls are made in the United States estimated that about 70% of "911" calls are placed from wireless phones, and that percentage is growing [START_REF]wireless services[END_REF]. The same case in Europe, statistics reveal that 65% of the approximate 320 million emergency calls made in European Union each year originate from mobile phones [START_REF] Eena | use of the GNSS to determine caller location in the context of 112 emergency calls[END_REF]. In most cases users will not know their position precisely enough to guide emergency personnel to the correct locations, and as a result wireless service providers are usually required to report the location information of the emergency callers via other means. At present, the supplied localization accuracy in outdoor scenarios is far from su cient, and the situation in indoor environments is even more problematical. Consequently, more e cient and timely public security services must be developed including localization techniques that can provide more accurate information and which operate well in indoor environments.

Social networking has been another big market and LBS are booming in this application field. With the development of mobile Internet, smart devices and localization techniques, social activities become more and more location based. Existing location based social networking applications like check in, friend finder and messaging services are already very popular, and such services are continuously growing.

In addition to the typical applications in the areas of public safety and social networking, more diverse LBS can be found in both public and private settings. Berg Insight estimates that about 50% of all mobile subscribers in Europe were frequent users of at least one LBS at the end of 2013. In North America, an estimated 60% of all handset users now access LBS regularly [START_REF] Insight | Mobile location based services[END_REF]. The increase in usage of LBS and the number of active users has resulted in 1.2. The indoor localization problem significant revenue growth, mainly from collecting, managing and distributing spatial information and imagery. If manufacturing and developing of devices and software for creating, visualizing, sharing and analyzing geographic information are included, it is an even larger industry. Despite rapid growth and widespread impact, however, LBS remain an emerging industry.

The main barrier that hinders the development and application of LBS is the inability to achieve su ciently accurate indoor localization. According to Strategy Analytics, people spend 80-90% of their time indoors and 70% of cellular calls and 80% of data connections originate from indoors [START_REF]Strategy Analytics[END_REF]. Along with an improvement of performance, future generations of indoor positioning systems will find even more applications which are at the present time not feasible. Satellites based localization techniques like GPS have played an important role in LBS, but will not be able to meet the requirements of higher accuracy and seamless localization of both indoor and outdoor.

The indoor localization problem

E orts have been made over decades to obtain accurate, reliable and pervasive localization in di erent environments. For outdoor environments, satisfactory localization has been achieved by the Global Navigation Satellite Systems (GNSS), which utilize a fleet of satellites around the Earth providing global coverage with high accuracy and high availability. The most well-known GNSS is the Global Positioning System (GPS) developed by the United States, serving worldwide users with high accuracy localization and navigation in all weather conditions [START_REF] Hofmann-Wellenhof | Global positioning system: Theory and practice[END_REF]. Localization based on the GPS necessitates no less than four satellites to accurately locate a receiver, while in some conditions signals from some of the satellites are too weak or obstructed.

Functioning in indoor environments is a critical challenge for localization, where GPS is infeasible because there is no Line Of Sight (LOS) between mobile receivers and satellites.

Moreover, due to the smaller scale and more complicated geometries of indoor environments, better accuracy will be required as compared to outdoor localization. The inability of GPS receivers to function adequately in indoor environments has launched a search for new techniques of indoor localization that can provide seamless and ubiquitous service for mobile users. These approaches can be divided into:

• Beacon based solutions, which determine a mobile's location by measuring some physical quantities of wireless signals that changes with the position; and

• Beacon free solutions, which use mobile sensors to detect position changes using a so-called

Chapter 1. Introduction dead-reckoning technique.

The complexity of indoor environments, with a large number of walls and obstacles, causes problems for beacon based solutions, where shadowing and multipath propagation e ects of radio signals are common. The received signal, in most situations, will not be from the direct LOS signal, but will contain many Non Line Of Sight (NLOS) components. Thus, time synchronization and propagation time measurement will be less inaccurate, which handicaps systems relying on time measurement to operate in indoor environments. Received Signal Strength (RSS) is another common measured quantity for indoor localization because of its ease of access. However, RSS in indoor environments, as the superimposition of multipath signals of varying phases, are also unstable. Furthermore, it is extremely di cult to model the indoor signal propagation, since indoor environments are much less regular than outdoor environments. Such models, usually based on a propagation path and known obstacles, are scenario specific, while a genuine indoor environment can vary dramatically, from the open halls of factory to narrow corridors in o ce buildings, for example. In addition, minor indoor changes in the organization of furniture, or the presence of persons can render a signal propagation model invalid in short order.

At the same time, beacon free localization techniques, which rely only on mobile sensors such as accelerometers, gyroscopes, magnetometers, and barometer, can track users by continuously estimating their displacement from a known starting point. Sensor dead-reckoning, however, is not likely to be a standalone solution for indoor localization, as it is always necessary to know the starting position, and furthermore, the inherent low precision of mobile sensors, and the necessity to integrate sensor readings in order to measure a position will result in an unacceptable accumulation of error. However, as multiple sensors sensitive to position changes are increasingly popular in mobile devices, it is possible to include them in hybrid localization solutions combining the advantages of a variety of location estimation techniques sources, which has now become the general trend for indoor localization solutions.

The thesis work

The objective of this thesis is to develop a practical indoor localization system that can be used with standard mobile devices. Unlike many of the indoor localization systems that are implemented using such technologies as infrared, Bluetooth, Radio-Frequency Identification (RFID), Wireless Local Area Networks (WLAN), Ultra-Wide Band (UWB), acoustic signals, etc., the thesis investigates indoor localization based on the RSS from GSM networks, which eliminates 1.3. The thesis work time and labor consuming infrastructure deployment. A vector containing a set of RSS values at di erent positions is referred to as an RSS fingerprint, as will be discussed in more detail later.

The widespread coverage, near-ubiquity and relative stability of GSM networks are attractive for practical indoor localization.

In the thesis, the characteristics of GSM RSS are first examined, showing the location specific nature and relative time robustness of GSM RSS, followed by an exploration of the functional relationship between RSS and position using regression techniques., No smooth functional relationship between RSS and position is found, however, for the indoor environment, indicating from the start that interpolation and extrapolation schemes based on RSS measurements at a small number of reference points are not going be viable for indoor localization.

Room-level indoor localization, i.e., estimation of the room in a building in which a mobile node is located, is then studied using Support Vector Machines (SVM) to classify RSS from all the available GSM carrier frequencies. Previous results using GSM for indoor localization suggested that accurate and e cient indoor localization can be achievable using RSS fingerprints containing very large numbers of GSM channels [START_REF] Varshavsky | GSM indoor localization[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF]. However, those studies did not yet present a genuinely practical solution, since RSS values were only explored over a limited set of points within each room. The thesis applies a more general scanning strategy, in which RSS examples are acquired during a "random walk" throughout the inside each room of interest, enabling a user can be localized at room level regardless of his or her exact position within a room.

A further advancement provided by this thesis, as compared to earlier work on GSM, is a study of the evolution of localization performance over a rather significant time period. Due to variations in shadowing, multipath, and environmental e ects such as building geometry changes, variable network tra c, presence or not of individuals in the vicinity under study, and atmospheric conditions, even mean RSS values can vary over time, leading to unacceptable performance degradation. In this thesis, several prescriptions are made to counteract these e ects and maintain performance levels, including re-training of the localization model and semi-supervised learning using transductive inference. The ultimate solution is found by going back to the basics of RSS characteristics, which are known to fluctuate on a variety of time scales. By recording RSS examples dispersed over a long time window, rather than in short spurts, it reduces substantially the rate at which performance degradation occurs.

In addition to the studies on indoor localization based on GSM, this thesis also studies mobile Chapter 1. Introduction sensor dead-reckoning and particle filter hybrid scheme that combine multiple sensors with GSM indoor localization. Using step detection and an orientation estimate based on mobile sensors applied to an adaptive stride length model, a hybrid localization system can accurately respond to small displacement of a mobile user over small time steps. A building layout map is furthermore employed to forbid solutions in which a mobile user moves to an inaccessible region, or crosses a wall, for example. In this way, room-level GSM fingerprinting results provide an absolute, but error-prone, position estimation, which can be combined with relative movements detected by mobile sensors, in order to obtain a more precise estimation of user location along a trajectory.

Structure of the thesis

In this chapter, after an initial introduction to the rich variety of location based applications and services, the indoor localization problem is discussed, wherein challenges for both beaconbased and beacon-free indoor localization techniques are explained. Then the thesis work is summarized, highlighting the contributions and improvements as compared with the previous solutions.

Chapter 2 discusses the fundamentals of indoor localization, including the measurement techniques upon which localization relies, as well as the location calculation and estimation algorithms to be explored. As there are a variety of technologies that can be used for indoor localization, there are as well di erent types of location estimation techniques. Common performance metrics are also presented in this chapter, which constitute a criterion for evaluating localization systems for use indoors.

Chapter 3 presents the characteristics of GSM signals, which are the basis of the indoor localization method developed in this thesis. This chapter first gives an overview of the GSM network concerning architecture, radio air interface, channel functions, and signal propagation.

Then the two types of RSS measurement devices used in this thesis are introduced, followed by an evaluation of the location-specific nature and temporal properties of RSS measurements. As indoor localization in this thesis is based on using RSS fingerprints, in the last part of this chapter, RSS "fingerprint distance" is compared to standard geometric distance.

In chapter 4, the main indoor localization algorithms based on GSM fingerprints are investigated, wherein an exploration of the functional relationship between GSM fingerprints and location is first presented. Room-level indoor localization is then studied, in which di erent rooms within a building are distinguished by using SVM to classify measured GSM fingerprints.

Structure of the thesis

The degradation of system performance over time is also evaluated here, and solutions to preserve the performance are proposed. Finally, a post-processing technique using Bayesian filtering is proposed, to employ a priori information about indoor layout and mobile's trajectory to improve the performance of the raw SVM classification.

In chapter 5, the dead-reckoning approach using mobile sensors is investigated and particle filtering is introduced, in order to combine in a unique solution information from GSM classification, sensor dead-reckoning, and map layout information.

Chapter 6 presents some complementary work that has been done within this thesis, including experiments at additional sites, GSM carrier selection, and post-processing techniques for the SVM classification. RSS from WiFi networks, as another widely available wireless signals, are also studied in the context of indoor localization.

The last chapter concludes the thesis, outlining the lessons drawn from our study, its limitations, and proposing directions for future research.

Chapter 2

Indoor localization fundamentals

Introduction

Prior to the development of modern positioning technology, various physical "signs" were used to obtain position information. An animal in a forest might leave an odor marking, for example, for use in recognizing an approximate location later on. It has long been common for man to use the positions of stars and the earth's magnetic field in order to establish directions and thereby estimate their locations.

The evolution of such "signs" is an important driving force in the development of positioning Better performance is the constant pursuit of the researcher, and is also an urgent need for many location based applications and services, particularly for indoor applications. Accuracy might be the most important performance indicator of such a system, while meanwhile other parameters, such as coverage, complexity, robustness and cost also need to be taken into account.

Indoor and outdoor environments are of course fundamentally di erent, which influences in a crucial way the adoption of particular localization solutions for indoor environments.

In this chapter, the common location estimation algorithms are first discussed, followed by a review of the underlying technologies of localization. Gradually, by comparing the performance metrics of localization systems based on di erent technologies, the field can be whittled down, allowing the methods adopted in this thesis to be selected -bearing in mind, of course, that our targeted approach is that of an RF-based system, potentially coupled with additional, complementary techniques.

Location estimation algorithms

The location of an object in space is determined by measuring some physical quantities that change accordingly to changes in position of the object. Based on the measured physical quantity that the localization approaches use, there are a variety of location estimation algorithms adapted to di erent localization technologies. The main categories of algorithms include proximity, triangulation, fingerprinting and dead-reckoning, each of which has its own advantages and disadvantages.

Proximity

Proximity, also known as connectivity or cell based localization, refers to a class of methods that provide symbolic relative location information if an object is present within the vicinity of a sensor. The proximity of the subject can be detected through physical contact, the presentation of a device such as a magnetic band to an appropriate reader, or by monitoring of a physical quantity in the vicinity of the sensor, for instance, a magnetic field.

In proximity based systems, when a mobile target is detected by a single reference point, the mobile position is associated to it. When a target is detected by more than one reference point,

Location estimation algorithms

the mobile target's position might be referred to the reference point having the strongest signal.

Centroid determination can improve results by calculating the centroid of a set of reference point positions, or alternatively a weighted centroid location can be computed, using RSS values or connectivity values as weights.

To achieve a good localization accuracy, proximity approaches rely on a dense deployment of reference points. Therefore, proximity approaches are typically implemented in systems that can detect the presence of a target but cannot obtain RSS or time measurements. In particular, the systems using Wireless Sensor Networks (WSN) [START_REF] Brida | On the accuracy of weighted proximity based localization in wireless sensor networks[END_REF], Bluetooth Low Energy (Bluetooth LE or simply BTLE) [START_REF] Chawathe | Beacon placement for indoor localization using Bluetooth[END_REF][START_REF] Chawathe | Low-latency indoor localization using Bluetooth beacons[END_REF][START_REF]Apple. iOS: understanding iBeacon[END_REF], RFID [START_REF] Montaser | RFID indoor location identification for construction projects[END_REF] and Near Field Communication (NFC) [START_REF] Ozdenizci | Development of an Indoor navigation system using NFC technology[END_REF] are often based on this method. Another example is cell-identification or Cell ID, which is widely used in long range cellular networks. Cell ID uses a unique code to identify the Base Transceiver Station (BTS) in use, and the known BTS position, stored in a database, adopted as an approximate mobile node location. The advantages of Cell ID approach are that it is simple and ubiquitous and can be used without additional requirements by any device supporting cellular network technology.

Triangulation

TOA

The TOA technique computes the distance between two devices by measuring the one way propagation time between them, knowing a priori the signal propagation speed. To perform 2D localization of a mobile device, at least three TOA measurements from di erent reference points are required. The location estimate can be obtained using a geometric method to compute the intersection point of circles with centers at the reference points and radii corresponding to the Chapter 2. Indoor localization fundamentals In real conditions, however, where multipath and shadowing e ects occur, inaccurate distance estimation results in an area of uncertainty rather than a single intersection point. Least Squares (LS) and Maximum Likelihood (ML) estimation are the two common solutions to minimize these errors and get the best estimate of the mobile location.

Let (x m ,y m ) denote the unknown mobile target's location coordinates in a 2D Cartesian coordinate system. Also, denote the three known reference coordinates as (x 1 ,y 1 ), (x 2 ,y 2 ) and (x 3 ,y 3 ). Since the wireless signal travels at the speed of light, the distance between the mobile target and the reference point i is given by

r i = (t i ≠ t 0 )c (2.1)
where t 0 and t i are the time instant of signal transmission and signal reception respectively, and c = 3 ◊ 10 8 m/s is the speed of light. According to the geometric relationship, the following set of equations is obtained:

d 2 1 = (x 1 ≠ x m ) 2 + (y 1 ≠ y m ) 2 (2.2) d 2 2 = (x 2 ≠ x m ) 2 + (y 2 ≠ y m ) 2 (2.3) d 2 3 = (x 3 ≠ x m ) 2 + (y 3 ≠ y m ) 2 (2.4)

Location estimation algorithms

LS is an approach to solve this over-determined nonlinear system of equations. Let d i = r i and subtract (2.2) from (2.3) and (2.4), whence it gives:

r 2 2 ≠ r 2 1 = x 2 2 ≠ 2x 2 x m + y 2 2 ≠ 2y 2 y m ≠ x 2 1 + 2x 1 x m ≠ y 2 1 + 2y 1 y m (2.5) r 2 3 ≠ r 2 1 = x 2 3 ≠ 2x 3 x m + y 2 3 ≠ 2y 3 y m ≠ x 2 1 + 2x 1 x m ≠ y 2 1 + 2y 1 y m (2.6)
The above equations can be rewritten in matrix form as

C x 2 ≠ x 1 y 2 ≠ y 1 x 3 ≠ x 1 y 3 ≠ y 1 D C x m y m D = 1 2 C K 2 2 ≠ K 2 1 ≠ r 2 2 + r 2 1 K 2 3 ≠ K 2 1 ≠ r 2 3 + r 2 1 D (2.7)
where

K 2 i = x 2 i + y 2 i (2.8)
Then, (2.7) can be written as

Hx = b (2.9)
where

H = C x 2 ≠ x 1 y 2 ≠ y 1 x 3 ≠ x 1 y 3 ≠ y 1 D x = C x m y m D b = 1 2 C K 2 2 ≠ K 2 1 ≠ r 2 2 + r 2 1 K 2 3 ≠ K 2 1 ≠ r 2 3 + r 2 1 D
If more than three TOA measurements are available, it can be verified that (2.9) still holds with

H = S W W W U x 2 ≠ x 1 y 2 ≠ y 1 x 3 ≠ x 1 y 3 ≠ y 1 . . . . . . T X X X V b = 1 2 S W W W U K 2 2 ≠ K 2 1 ≠ r 2 2 + r 2 1 K 2 3 ≠ K 2 1 ≠ r 2 3 + r 2 1 . . . T X X X V
Applying the LS solution, the final estimation has the following form:

x = (H T H) ≠1 H T b (2.10)
Alternatively, the location of a mobile target can be estimated via maximum likelihood based

Chapter 2. Indoor localization fundamentals on TOA measurements. The ML estimator maximizes the probability of observing the distances r 1 , r 2 and r 3 giving the target location in x as:

x = argmax{P (r 1 , r 2 , r 3 |x)} (2.11)
With the assumption that r 1 , r 2 and r 3 are independent of each other, the joint conditional probability P (r 1 , r 2 , r 3 |x) has the form:

P (r 1 , r 2 , r 3 |x) = P (r 1 |x)P (r 2 |x)P (r 3 |x)
The distance estimations between the mobile target and the reference point i are commonly considered to have a Gaussian error distribution N (r i , ‡ i ). Consequently, the ML estimator (2.11) can be written:

x = argmax A 1 Ô 2fi ‡ 1 e ≠ (d 1 ≠r 1 ) 2 2 ‡ 2 1 1 Ô 2fi ‡ 2 e ≠ (d 2 ≠r 2 ) 2 2 ‡ 2 2 1 Ô 2fi ‡ 3 e ≠ (d 3 ≠r 3 ) 2 2 ‡ 2 3 B = argmin 3 ÿ i=1 (d i ≠ r i ) 2 ‡ 2 i
where r i and d i are defined as in equations (2.1), (2.2), (2.3) and (2.4) above. The ML estimator thus turns out to be the well-known Non-linear Least Squares (NLS) estimator, which can be obtained by gradient descent algorithms, or via linearization techniques such as the Taylor series expansion [START_REF] Ca Ery | Wireless location in CDMA cellular radio systems[END_REF][START_REF] Kim | The interior-point method for an optimal treatment of bias in trilateration location[END_REF].

TOA techniques can provide high localization accuracy, but they require precise time synchronization for system transmitters and receivers. Also, the NLOS propagation of radio signals a ects the time measurement accuracy, thus compromising the accuracy of TOA based localization systems. TOA techniques are commonly used in UWB systems [START_REF] Alsindi | Spatial characteristics of UWB TOAbased ranging in indoor multipath environments[END_REF][START_REF] Alsindi | Measurement and modeling of ultrawideband TOA-based ranging in indoor multipath environments[END_REF][START_REF] Dardari | Ranging with ultrawide bandwidth signals in multipath environments[END_REF][START_REF] Irahhauten | Investigation of UWB ranging in dense indoor multipath environments[END_REF][START_REF] Lee | Ranging in a dense multipath environment using an UWB radio link[END_REF], which have the inherent advantage of good penetration and insensitivity to multipath e ects.

TDOA

TDOA techniques determine the relative position of a mobile target by comparing the di erence of arrival time from multiple reference points. Unlike TOA systems measuring directly the time of arrival from all the reference points and calculating the distances, TDOA systems calculate the distance di erences between mobile target and reference points based on time di erence measurements, as shown in Figure 2.2. From the geometric point of view, given a TDOA measurement the mobile target must lie on a hyperboloid with a constant range Following the symbol definitions of the mobile target and reference points above in TOA systems, the di erence of distance to reference points and to the reference point where the signal first arrives is

Location estimation algorithms

d ij = r i ≠ r j = (t i ≠ t j ) c = Ò (x i ≠ x m ) 2 + (y i ≠ y m ) 2 ≠ Ò (x j ≠ x m ) 2 + (y j ≠ y m ) 2
(2.12)

where t i and t j are the time instant of signal reception from reference point i and j respectively. Similar to the solutions for the TOA, location estimation based on TDOA measurements can be obtained by solving non-linear LS problems or ML estimation.

The advantage of TDOA systems, compared with TOA systems, is that only the reference points needs to be time synchronized. The TDOA scheme is widely used in indoor localization systems based on GPS [START_REF] Barnes | High precision indoor and outdoor positioning using LocataNet[END_REF][START_REF] Jardak | Indoor positioning based on GPS-repeaters: Performance enhancement using an open code loop architecture[END_REF], television (TV) [START_REF] Rabinowitz | A new positioning system using television synchronization signals[END_REF], WSN [START_REF] Moore | Robust distributed network localization with noisy range measurements[END_REF] and UWB [START_REF] Ye | UWB TDOA localization system: Receiver configuration analysis[END_REF][START_REF] Prorok | Accommodation of NLOS for ultra-wideband TDOA localization in single-and multi-robot systems[END_REF]. It is also widely applied in 3G and 4G cellular network based indoor localization, since the base stations are time-synchronized in these networks [START_REF] Borkowski | Enhanced performance of Cell ID+RTT by implementing forced soft handover algorithm[END_REF][START_REF] Medbo | Propagation channel impact on LTE positioning accuracy: A study based on real measurements of observed time di erence of arrival[END_REF][START_REF] Fischer | Observed Time Di erence Of Arrival ( OTDOA ) positioning in 3GPP LTE[END_REF].

RTOF

The RTOF technique, which is also known as two-way ranging, determines the distance between the mobile target and the reference point by measuring the complete round-trip TOF of signal between the transmitter and the receiver. RTOF processing is algorithmically identical to that used in radar systems, although in RTOF systems the receiver unit performs some signal processing instead of simply reflecting a radar pulse.

Chapter 2. Indoor localization fundamentals

The RTOF technique is widely used in UWB systems [START_REF] Crepaldi | UWB receiver design and two-way-ranging simulation using VHDL-AMS[END_REF]. Similarly to TOA, RTOF uses the absolute signal propagation time to calculate the distance. Location estimation algorithms for TOA can be directly applicable to RTOF; however, precise clock synchronization is not required for RTOF systems, as it is for TOA based systems.

RSS-based lateration

The RSS-based approach estimates the distance between the mobile target and multiple reference points using the attenuation of the emitted signal strength. Time synchronization is di cult to obtain for a wide variety of devices that are not dedicated exclusively to localization; however the received signal power measurement function is relatively standard, since mobile devices need to regularly assess the quality of signals they receive in order to establish e ective wireless communication links. As a result, RSS-based lateration is very popular in WiFi [START_REF] Tarrio | A new positioning technique for RSS-Based localization based on a weighted least squares estimator[END_REF][START_REF] Yang | Indoor localization using improved RSS-based lateration methods[END_REF][START_REF] Chintalapudi | Indoor localization without the pain[END_REF], Bluetooth [START_REF] Subhan | Indoor positioning in Bluetooth networks using fingerprinting and lateration approach[END_REF], RFID [START_REF] Ko | RFID 3D location sensing algorithms[END_REF] and UWB [START_REF] Waadt | Positioning in multiband OFDM UWB utilizing received signal strength[END_REF].

RSS-based methods attempt to estimate the signal path loss due to propagation. For outdoor environments, the relation between signal strength and distance can be approximated by the Log Distance Path Loss (LDPL, see section 3.2.4) model [START_REF] Seidel | 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings[END_REF]. However, for indoor environments, the shadowing and multipath environment becomes very complex. Consequently, long range signals are not well-suited to RSS-based lateration, since pathloss attenuation is di cult to determine.

For short range signals, propagation path modeling can be modified to take into account obstacles in order to improve the performance by better estimating distances.

Once the distances are estimated based on RSS, the rest of the location estimation procedure is the same as in TOA based systems.

AOA

AOA is an angulation technique used for localization that estimates the location of a mobile target as the intersection point of pairs of hypothetical signal paths along particular angles, as shown in Figure 2.3. To localize a target in a 2D plane, the AOA approach requires only two reference points, while for for 3D localization, three are needed. To improve accuracy, three or more reference points can also be used, in a technique referred to as multi-angulation. To obtain angle measurements, a directional antenna or antenna array is required [START_REF] Nokia | High accuracy indoor positioning[END_REF][START_REF] Zhou | Two-dimension localization of passive RFID tags using AOA estimation[END_REF].

The advantage of AOA systems is that they require fewer reference points, as compared with lateration techniques, to determine the location of a mobile target. In addition, time synchronization between transmitters and receivers is not needed. However, AOA systems

Location estimation algorithms

Fingerprinting

The above-mentioned localization techniques rely heavily on the estimation of distances between mobile target and the references. Obtaining time and angle measurements is a function that is absent from most mobile devices in everyday use. Moreover, the complex indoor environments make it di cult to accurately derive distances from measurements made on narrow band signals. Nevertheless, in many indoor environments, some location dependent signal characteristics tend to remain relatively stable over time. The fingerprinting technique is based on this observation, attempting to match real time characteristics of an RF signal to a previously constructed map of RF environment in a particular area. RSS is the measured quantity most often associated with fingerprint based systems, although propagation time, channel impulse response, or inquiry response rate measurements, and the like, can also be used.

The fingerprinting approach is performed in two phases. The first is o ine and is known as Chapter 2. Indoor localization fundamentals the training or calibration phase. In this phase, position-tagged RSS values over a wide range of positions are recorded, and used to construct a model relating RSS to position. The locations at which measurements are performed can correspond to grid points, specific reference points, or regions, depending on the targeted application and desired accuracy. The second phase is the online localization phase, in which measurements are recorded online and sent to the localization model previously developed in the o ine phase, which provides a location estimation.

Fingerprinting techniques commonly make use of classification algorithms such as Bayesian inference, k-Nearest Neighbors (k-NN), neural networks, or support vector machines, in order to supply a location estimate for a fingerprint example.

Fingerprinting is widely used in the localization systems based on WiFi, Bluetooth, RFID and cellular networks, since RSS measurements are easier to access than precise time measurements like TOA, TDOA and RTOF. An important drawback of fingerprinting techniques is the necessity of creating and maintaining a localization model. The entire site of interest needs to be surveyed in advance for this purpose, recording the RSS and labeling the location, which is of course a time and labor consuming task. And since the signal measurements acquired are quite variable and noisy, it is necessary to record as many measurements as possible in each location area, so that the training set takes into account as much as possible the large diversity of possible fingerprints and adequately models their distributions. Moreover, due to changes in environmental e ects, such as building geometry, network tra c, presence of people, atmospheric conditions, etc., RSS is expected drift over time, which can degrade localization performance.

Dead-reckoning

Dead reckoning is the process of estimating an unknown current position based on the last determined position modified by a displacement calculated from velocity and heading information over an elapsed time step, as shown in Figure 2.4. Dead-reckoning has drawn increasing attention for indoor localization, since it relies only on sensors which are widely available in standard modern mobile devices.

Inertial navigation is based on the dead-reckoning principle, whereby speed is computed based on accelerometer readings, and orientation is determined by gyroscopes and magnetic field measurements.

The time integral of acceleration yields a continuous estimate of the instantaneous speed of the target, if the initial speed is known. With a second integration the 2.2. Location estimation algorithms displacement with respect to a starting point can be obtained as:

≠ ae p (t) = ⁄ t 0 ≠ ae v (• )d• = ⁄ t 0 ⁄ • 0 ≠ ae a (x)dxd• (2.13)
where ≠ ae p (t) is the displacement vector, ≠ ae v (• ) is the instantaneous speed and ≠ ae a (x) is the acceleration from the sensor reading. The heading can be obtained in the same way by integrating the gyroscope sensor readings as:

◊(t) = ⁄ t 0 Ê(• )d• (2.14)
where ◊(t) is the angle of rotation with respect to the previous azimuth angle and Ê(• ) is the angular velocity obtained from the sensor reading.

At the same time, magnetic field provides an absolute angle value between target heading and the geomagnetic North Pole. Usually the magnetic field orientation is robust over time, but susceptible to interference, while gyroscope readings, although very sensitive, su er from severe error accumulation due to integrating angular velocity over long time periods. In practice these two sensors are combined using complementary filters to generate a more accurate azimuth angle estimation.

Unlike the conventional inertial navigation systems used in aircraft, indoor dead-reckoning is quite di erent in both speed and orientation estimation. While walking in indoor environments, the mobile device moves about following the rhythm of a walking pace, and, consequently, the accelerometer will record periodic up-an-down accelerations, rather than a gradual change as might be expected for a jet or rocket engine. This fact allows displacements to be estimated via Chapter 2. Indoor localization fundamentals step detection and stride length estimation. In addition to displacement estimation, orientation is also needed to determine the mobile location, which, for mobile sensors, is the same as that of the conventional inertial navigation systems. Nevertheless, the orientation obtained by the embedded sensors corresponds to the mobile device itself, and is not necessarily the same as the orientation of the user, who may carry in a pocket, or in the hand in various configurations, which adds another challenge to the localization problem.

The technologies for localization

The technologies for localization can be categorized into RF, light wave, acoustic wave and MEMS sensor based, which are categorized in

GPS

GPS is thus far the most successful dedicated localization system, which provides worldwide users with accurate and reliable positioning and navigation services in outdoor spaces [START_REF] Hofmann-Wellenhof | Global positioning system: Theory and practice[END_REF].

However, the poor coverage of GPS signal in indoor environments makes it unusable in indoor environments. As a result, di erent approaches were proposed to overcome the shortcoming of GPS indoors, and render it feasible for indoor localization.

Early e orts focused on improvement of the sensitivity of GPS receivers to help track weak signals, including new hardware designs and assisted GPS techniques [START_REF] Van Diggelen | Indoor GPS theory & implementation[END_REF][START_REF] Vittorini | Optimizing indoor GPS performance[END_REF][START_REF] Dovis | An assisted highsensitivity acquisition technique for GPS indoor positioning[END_REF][START_REF] Schön | On the capability of high sensitivity GPS for precise indoor positioning[END_REF]. These e orts improved the localization accuracy of the GPS, allowing, in one test, to obtain an accuracy of 6 to 16 meters inside a residential building consisting mostly of wood and concrete stucco [START_REF] Zandbergen | Positional accuracy of assisted GPS data from high-sensitivity GPS-enabled mobile phones[END_REF]. Such approaches, however, are far from adequate in more complex indoor environments where GPS signals are totally blocked. Another type of solution is to deploy local stations and antennas that repeat GPS-like, signals, known as GPS pseudolites and repeaters [START_REF] Samama | Global positioning: Technologies and performance[END_REF]. GPS pseudolites transmit signals with code-phase, carrier-phase, and data components in the same timing and format as the GPS signals. An indoor GPS receiver can then acquire this signal and derive code-phase, pseudo-ranges or carrier-phase measurements for localization exactly as it would outdoors. Subcentimeter indoor localization accuracy was reported in [START_REF] Barnes | High precision indoor and outdoor positioning using LocataNet[END_REF] indicating such approach is promising for accurate indoor localization. As the name implies, GPS repeater solutions broadcast ranging signals in indoor environments by replicating the GPS constellation's functions. In [START_REF] Jardak | Indoor positioning based on GPS-repeaters: Performance enhancement using an open code loop architecture[END_REF], using sequential switching GPS repeaters and a modified open delay-lock loop GPS receiver architecture, sub-metrical accuracy was achieved.

Though GPS pseudolites and repeaters are accurate for indoor localization, they are somewhat specialized as of today; furthermore they require precise time synchronization, and su er from the multipath signal propagation problem common to narrow band signals. Among the cellular networks, GSM is thus far the most widely deployed cellular telephony standard in the world. GSM systems employ the Frequency Division Multiple Access (FDMA) scheme to divide the frequency band into a number of GSM channels. RSS is a simply measurable quantity for GSM signals, featuring strong spatial variability and relative consistency over time [START_REF] Varshavsky | GSM indoor localization[END_REF].

Cellular networks

Zimmermann et al. [START_REF] Zimmermann | Database correlation for positioning of mobile terminals in cellular networks using wave propagation models[END_REF] proposed a database correlation method for positioning mobile terminals in urban outdoor environments based on GSM networks, which compares the measured RSS from the current serving cell and six neighbor cells with a RSS-position look-up-table defined a priori, during the network planning process. The location accuracy of [START_REF] Zimmermann | Database correlation for positioning of mobile terminals in cellular networks using wave propagation models[END_REF] tested in the urban scenario is in the range of 80 meters in 67% of the measurements and 192 meters for the 95% percentile. In [START_REF] Varshavsky | GSM indoor localization[END_REF], indoor localization was achieved using the k-NN technique to match online GSM fingerprints to a fingerprint database recorded o ine prior to the experiment, where each fingerprint was made up of the RSS values from 35 GSM channels. A median localization accuracy ranging from 1.94 to 4.07 meters was achieved in large buildings, within a single floor, and the approach was able to identify the floor correctly 60% of the time, and be correct within 2 floors fully 98% of the time.

A study in [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] went further, incorporating RSS from carriers of the entire 900 MHz and 1800 MHz GSM bands into the fingerprint, using SVM classifiers to handle the high dimensionality while classifying fingerprints with room labels. In this case, the correct room could be determined, in two separate indoor environments, 98% to 100% of the time, but only with a limited number of fixed positions within the rooms.

In

WiFi

WiFi is technically an industry term that represents a type of WPAN protocol based on the The vast majority of indoor localization based on WiFi networks involves using the two-stage fingerprinting technique, i.e., an o ine "training" step followed by "online" testing [START_REF] Bahl | RADAR: An in-building RF-based user location and tracking system[END_REF][START_REF] Wu | WLAN location determination in e-home via support vector classification[END_REF][START_REF] Saha | Location determination of a mobile device using IEEE 802.11b access point signals[END_REF][START_REF] Xiang | A wireless LANbased indoor positioning technology[END_REF][START_REF] Ji | ARIADNE: A dynamic indoor signal map construction and localization system[END_REF][START_REF] Reyero | Always best located, a pervasive positioning system[END_REF][START_REF] Wu | WILL: Wireless indoor localization without site survey[END_REF]. The o ine WiFi fingerprint database is typically made up of RSS values from a number of WiFi Access Points (AP). In [START_REF] Xiang | A wireless LANbased indoor positioning technology[END_REF], the fingerprints were recorded in four orientations to help di erentiate locations and roughly estimate user orientation, since the human body a ects the propagation of WiFi signals, and the RSS recorded facing di erent orientations will be di erent.

Location estimation is usually based on finding the best match between an online recorded RSS fingerprint and a fingerprint stored in the training database [START_REF] Bahl | RADAR: An in-building RF-based user location and tracking system[END_REF][START_REF] Ji | ARIADNE: A dynamic indoor signal map construction and localization system[END_REF][START_REF] Reyero | Always best located, a pervasive positioning system[END_REF][START_REF] Xiang | A wireless LANbased indoor positioning technology[END_REF][START_REF] Wu | WILL: Wireless indoor localization without site survey[END_REF]; however, more complex classification techniques such as neural networks [START_REF] Saha | Location determination of a mobile device using IEEE 802.11b access point signals[END_REF] and SVM [START_REF] Wu | WLAN location determination in e-home via support vector classification[END_REF] can also be used.

The main drawback of any fingerprinting approach is that it requires the time and labor

The technologies for localization

consuming site survey training stage; however, crowd-sourcing and "calibration-free" solutions have been proposed to help circumvent this di culty. Rai et al., for example, [START_REF] Rai | Zee: Zeroe ort crowdsourcing for indoor localization[END_REF] proposed an inertial sensor based crowd-sourcing approach, which uses a particle filter to track mobile devices as they traverse an indoor environment, while simultaneously performing WiFi scans. Wu et al.

[61] designed a wireless indoor localization system without site survey, which uses the room map and a accelerometer to help recognize di erent rooms.

There are also WiFi indoor localization approaches based on signal propagation modeling instead of fingerprinting calibration [START_REF] Tarrio | A new positioning technique for RSS-Based localization based on a weighted least squares estimator[END_REF][START_REF] Yang | Indoor localization using improved RSS-based lateration methods[END_REF][START_REF] Chintalapudi | Indoor localization without the pain[END_REF]. These commonly adopt the LDPL model to estimate distances from RSS values, finally using triangulation to estimate the location of a mobile node. The parameters of the LDPL model were hard-coded in [START_REF] Tarrio | A new positioning technique for RSS-Based localization based on a weighted least squares estimator[END_REF], linearly fitted in [START_REF] Yang | Indoor localization using improved RSS-based lateration methods[END_REF],

and calculated when the GPS is available, for example, when near a window [START_REF] Chintalapudi | Indoor localization without the pain[END_REF].

WiFi indoor localization accuracy presented in the literatures is commonly of the order of a few meters in some 90% of the time (4 meters in 95% of the time [START_REF] Wu | WLAN location determination in e-home via support vector classification[END_REF], 3.3 meters in 98% of the time [START_REF] Saha | Location determination of a mobile device using IEEE 802.11b access point signals[END_REF], and 2 meters in 90% of the time [START_REF] Xiang | A wireless LANbased indoor positioning technology[END_REF]). The biggest challenge for such approaches, however, is the non-stationarity of WiFi RSS [START_REF] Mok | Location determination using WiFi fingerprinting versus WiFi trilateration[END_REF][START_REF] Varshavsky | GSM indoor localization[END_REF]. This is reflected in the RSS-distance relationship, in that while the mean RSS versus distance over a large number of examples may fit the LDPL model well, the distance obtained from a single RSS measurement could in fact have a very large error. Thus, as in the case of WiFi fingerprinting, the instability of WiFi signals results in the failure of the RSS-to-distance function, requiring time and labor consuming re-calibration.

Bluetooth

Bluetooth is another wireless standard for WPAN and also operates in the 2.4 GHz ISM band. It has a wide variety of applications, and has boosted the convenience and functionality of portable devices by providing a simple way for them to interact with each other. Bluetooth employs frequency hopping technique with 1 MHz wide channels, which is less sensitive to strong narrow band interference [START_REF] Ferro | Bluetooth and Wi-Fi wireless protocols: A survey and a comparison[END_REF]. However, Bluetooth su ers severe interference from other devices operating in the same radio bands.

Many of the localization techniques used on WiFi networks are also applied to Bluetooth, with RSS based fingerprinting and triangulation the two principal techniques adopted for Bluetooth indoor localization [START_REF] Altini | Bluetooth indoor localization with multiple neural networks[END_REF][START_REF] Raghavan | Accurate mobile robot localization in indoor environments using bluetooth[END_REF][START_REF] Subhan | Indoor positioning in Bluetooth networks using fingerprinting and lateration approach[END_REF]. In [START_REF] Altini | Bluetooth indoor localization with multiple neural networks[END_REF], RSS and the mobile's orientation were measured as a mobile device connects to each Bluetooth node; multiple neural networks were then used to build a localization model. Subhan et al. [START_REF] Subhan | Indoor positioning in Bluetooth networks using fingerprinting and lateration approach[END_REF] proposed a hybrid approach that combines RSS Chapter 2. Indoor localization fundamentals fingerprinting and RSS-based lateration. In [START_REF] Subhan | Indoor positioning in Bluetooth networks using fingerprinting and lateration approach[END_REF], RSS fingerprinting results are used to estimate the parameters of the LDPL propagation model, and coordinate positions are obtained by RSSbased lateration using the obtained LDPL model. Compared with WiFi, Bluetooth uses a lower transmit power (below 10 dBm), has a shorter nominal range (around 10 meters) and is lower in price, which allows for dense deployment of Bluetooth tags for indoor localization. For example, Chawathe [START_REF] Chawathe | Beacon placement for indoor localization using Bluetooth[END_REF] used a large number of inexpensive Bluetooth beacons to make a cell-based indoor localization system that determines the intersection area of visible beacon ranges. Nonetheless the localization accuracy of Bluetooth rivals that of WiFi [START_REF] Altini | Bluetooth indoor localization with multiple neural networks[END_REF][START_REF] Raghavan | Accurate mobile robot localization in indoor environments using bluetooth[END_REF][START_REF] Subhan | Indoor positioning in Bluetooth networks using fingerprinting and lateration approach[END_REF]. The clearest challenge for Bluetooth systems is latency, as standard Bluetooth requires more than 10 seconds to carry out an inquiry process [START_REF] Chawathe | Low-latency indoor localization using Bluetooth beacons[END_REF]. Too, supplying power supply to a set of densely deployed Bluetooth tags can be problematical.

Perhaps more promising for indoor localization is the recently introduced BTLE [START_REF] Heydon | Bluetooth low energy: The developer's handbook[END_REF]. As the name implies BTLE features ultra-low peak, average and idle mode power consumption, thereby extending the use of Bluetooth wireless technology to devices that are powered by small, coin-cell batteries such as those used in smart watches and wearable sports and health care devices. In indoor localization, BTLE technology makes it possible to operate localization tags for more than a year on such batteries. Another improvement is that BTLE greatly reduces the inquiry time, using only three channels for advertising, messages, and establishing a connection in only a few milliseconds. In addition, BTLE provides an enhanced range, which can be optimized for di erent application scenarios.

Apple iBeacon [START_REF]Apple. iOS: understanding iBeacon[END_REF]

The technologies for localization

WSN

WSN consist of small nodes, which are low-power devices equipped with processor, storage, a power supply, a transceiver, and one or more sensors and, in some cases, with an actuator.

Each node is able to sense the environment, perform simple computations and communicate with other nodes or to a centralized serving unit. Typically the deployment of a WSN is obtained by "scattering" the nodes throughout some space of interest, thus making the network topology random. Ad hoc networking techniques are often employed, thus obviating the need for a central router or wireless base station. WSN can use a number of o the shelf wireless technologies, such as Bluetooth, ZigBee, WiFi, UWB, although most applications make use of IEEE 802.15.4 and ZigBee [START_REF] Sohraby | Wireless sensor networks: Technology, protocols, and applications[END_REF].

Localization is an important application aspect and also a basic need for WSN. In WSN, some sensor nodes, known as anchors, are aware of their own positions, while the localization problem is to determine the location of other nodes based on the location references obtained from the anchors [START_REF] Mao | Localization algorithms and strategies for wireless sensor networks[END_REF]. Quite a number of studies using WSN for localization have appeared in the literature [START_REF] Alippi | A RSSI-based and calibrated centralized localization technique for wireless sensor networks[END_REF][START_REF] Moore | Robust distributed network localization with noisy range measurements[END_REF][START_REF] He | Range-free localization schemes for large scale sensor networks[END_REF][START_REF] Kannan | Simulated annealing based wireless sensor network localization[END_REF][START_REF] Gholami | Upper bounds on position error of a single location estimate in wireless sensor networks[END_REF][START_REF] Savic | Belief consensus algorithms for fast distributed target tracking in wireless sensor networks[END_REF][START_REF] Brida | On the accuracy of weighted proximity based localization in wireless sensor networks[END_REF]. Localization in WSN commonly consists of estimating distances or angles between nodes and combining these in a location estimation algorithm.

Measured quantities include connectivity, RSS, timing, and angle, while the most popular location combination algorithms are trilateration and ML estimation [START_REF]Localization algorithms in wireless sensor networks: Current approaches and future challenges[END_REF].

RFID and NFC

An RFID system is commonly composed of a reading device that can wirelessly obtain the electronically stored information of tags present in the environment in the recognizable region. RFID systems share most of the deployment schemes and positioning algorithms cited for short range Bluetooth and WSN introduced above, and have comparable localization accuracy [START_REF] Zhou | RFID localization algorithms and applications -a review[END_REF][START_REF] Bouet | RFID tags: Positioning principles and localization techniquesc[END_REF].

In [START_REF] Montaser | RFID indoor location identification for construction projects[END_REF], Montaser and Moselhi adopted a weighted proximity approach to localize a moving RFID Chapter 2. Indoor localization fundamentals reader, where RSS from passive RFID tags are used as weights to calculate a barycenter. Ni et al. [START_REF] Ni | LANDMARC: Indoor location sensing using active RFID[END_REF] presented the LANDMARC localization system based on the RSS fingerprinting approach using k-NN algorithm. Ko et al. [START_REF] Ko | RFID 3D location sensing algorithms[END_REF] developed a 3D location sensing algorithm using RFID technology based on RSS. The distances between a target tag and multiple RFID readers are first estimated based on the RSS, and then tag location is calculated based on the gradient descent method. In [START_REF] Zhou | Two-dimension localization of passive RFID tags using AOA estimation[END_REF], a passive UHF RFID system was proposed based on AOA, where, instead of using RSS, the more robust phase characteristics were used to estimate the angles.

NFC, as a specialized branch within the family of RFID technologies, specifically the HF RFID, has drawn attention recently since it is now available in the majority of mobile phones.

NFC is designed to be a secure form of data exchange over very short distance (5 centimeters or less). Localization can be accomplished with NFC by putting a number of tags at places of interest, where location is reported simply by touching the tag with an NFC equipped device [START_REF] Ozdenizci | Development of an Indoor navigation system using NFC technology[END_REF].

NFC also supports two-way communication and can be used for peer-to-peer content sharing. It is thus attractive for application scenarios such as in museums, which, in addition to letting the visitors localize themselves, can provide the information about exhibitions as well.

UWB

UWB transmits very low power radio signals using extremely short electrical pulses, typically in the picosecond range, which have a very broad spectral profile, of 500 MHz or more. An emitted radio wave is considered to be UWB if its bandwidth exceeds 500 MHz or 20% of the carrier frequency. The high bandwidth allows UWB to support high wireless data rates of 480

Mbps up to 1.6 Gbps, over distances of several meters.

UWB has inherent advantages for indoor localization. First of all, UWB typically consumes very little power. Also, unlike narrow band signals, UWB systems can also penetrate e ectively through dense materials, and the very short duration of UWB pulses renders them less sensitive to the multipath e ect as well [START_REF] Gezici | Localization via ultra-wideband radios: A look at positioning aspects for future sensor networks[END_REF]. Location estimation based on UWB waves can be very accurate due to the possibility of precise time measurements of the propagation times of UWB pulses.

Bocquet et al. [START_REF] Bocquet | Millimeter wave up-converted UWB based positioning system[END_REF] proposed an Enhanced TDOA (E-TDOA) measurement technique for indoor localization, considering a Di erential Impulse Response (DIR) in the TDOA domain, which mitigates the multipath to only measure the LOS TDOA contribution. Localization precision less than 1 meter has been reported [START_REF] Alsindi | Spatial characteristics of UWB TOAbased ranging in indoor multipath environments[END_REF][START_REF] Alsindi | Measurement and modeling of ultrawideband TOA-based ranging in indoor multipath environments[END_REF][START_REF] Dardari | Ranging with ultrawide bandwidth signals in multipath environments[END_REF][START_REF] Irahhauten | Investigation of UWB ranging in dense indoor multipath environments[END_REF][START_REF] Lee | Ranging in a dense multipath environment using an UWB radio link[END_REF][START_REF] Ye | UWB TDOA localization system: Receiver configuration analysis[END_REF][START_REF] Prorok | Accommodation of NLOS for ultra-wideband TDOA localization in single-and multi-robot systems[END_REF]. In addition, RSS-based lateration approach based on UWB infrastructure is reported to have the equivalent accuracy, between 0.1

The technologies for localization

and 0.2 meters [START_REF] Waadt | Positioning in multiband OFDM UWB utilizing received signal strength[END_REF]. In [START_REF] Kilic | An experimental study of UWB device-free person detection and ranging[END_REF], a passive person-detection and localization approach is proposed using o -the-shelf UWB devices. UWB appears to have a bright future for accurate indoor localization, but for the present is not in widespread use on standard mobile devices.

MEMS

MEMS is a technology that combines computers with tiny mechanical devices such as sensors, valves, gears, mirrors, and actuators embedded in semiconductor chips. Traditional inertial navigation devices such as the accelerometers and gyroscopes used in navigation for decades are too bulky to use in indoor localization. MEMS enables localization applications by integrating multiple sensors into a small chip embedded in mobile devices such as smart phones and wearable devices.

Indoor localization based on inertial sensors is referred to as sensor dead-reckoning, which makes use of the same techniques as those developed for airplanes and ballistic missiles. The current position of a target is calculated based on a previously determined position plus a displacement estimated over elapsed time and path step. The relevant timescales of inertial events in embedded applications, of course, are entirely di erent from those encountered in navigation. When users walk in an indoor environment, their speed is comparatively slow, and there are alternative intervals of walking and rest. As a result, vertical acceleration changes are usually greater than horizontal ones, with the result that accelerometers are commonly used for step detection rather than speed estimation. Acceleration-based step detection typically relies on the peak detection [START_REF] Levi | Dead reckoning navigational system using accelerometer to measure foot impacts[END_REF] or zero-crossing [START_REF] Cho | Sensor fusion and error compensation algorithm for pedestrian navigation system[END_REF] approaches, which can be improved through the use of time and amplitude thresholds [START_REF] Jin | A robust dead-reckoning pedestrian tracking system with low cost sensors[END_REF][START_REF] Li | A reliable and accurate indoor localization method using phone inertial sensors[END_REF]. There are also gyroscope based step detection approaches [START_REF] Feliz | Pedestrian tracking using inertial sensors[END_REF], in which a foot-mounted gyroscope detects the swing of leg. The displacement of a mobile user is estimated based on step detection, step length estimation, and the detected direction of movement. Since step lengths may vary from person to person, and any given person may adopt di erent walking modes, a constant step length value can result in the accumulation of very large errors over time. In [START_REF] Jin | A robust dead-reckoning pedestrian tracking system with low cost sensors[END_REF] step length estimation is based on a model constructed with the amplitude of acceleration, and in [START_REF] Cho | Sensor fusion and error compensation algorithm for pedestrian navigation system[END_REF][START_REF] Li | A reliable and accurate indoor localization method using phone inertial sensors[END_REF] on the walking speed.

Orientation can be obtained from the magnetic field value or by integrating gyroscope readings for foot-mounted sensors; however it remains a challenge for sensor dead-reckoning using standard mobile devices. In [START_REF] Jin | A robust dead-reckoning pedestrian tracking system with low cost sensors[END_REF] the accuracy of orientation estimation was improved by using two or more set of sensors carried by one person and performing sensor fusion. Li et al. [START_REF] Li | A reliable and accurate indoor localization method using phone inertial sensors[END_REF] Chapter 2. Indoor localization fundamentals considered a special case when the mobile phone is in a trouser pocket, using the acceleration zero-crossing as a ground truth to compute the heading orientation while walking.

In short time period, the location estimation based on sensor dead-reckoning can be very accurate, but with increasingly severe error accumulation caused by drift of sensors and misdetection of steps. As a consequence, MEMS sensors are unlikely to be a standalone solution for indoor localization, but it is interesting to combine it with other localization approaches being a hybrid approach to produce a more accurate location estimation. Alternatively, map information is usually used as a constraint to exclude impossible locations estimated based on sensor dead-reckoning. In [START_REF] Perttula | Distributed indoor positioning system with inertial measurements and map matching[END_REF] and [START_REF] Bao | A novel map-based dead-reckoning algorithm for indoor localization[END_REF], particle filters are introduced for map matching, which combines sensor dead-reckoning results and the map layout information.

The performance metrics

As introduced above, there are a variety of technologies and techniques that can be adopted to build an indoor localization system. Localization performance is the crucial element for both localization service providers and users. Accuracy of location estimates, although very important, is not the only performance indicator. Indeed, robustness, complexity, scalability and cost in the adopted solutions are also crucial metrics to be considered.

Accuracy and precision

The accuracy of a localization system relates to the di erence, defined in some metric, between a location estimate and the true target location. The precision relates to reproducibility and repeatability, and indicates the degree to which repeated location estimates, under unchanged conditions, will produce identical results.

Mean distance error or Root Mean Squared Error (RMSE) is usually used as the accuracy indicator, revealing the potential bias or systematic o set of a localization system. The accuracy of a localization system is desired to be high, but to attain high accuracy is usually costly. For example, in fingerprinting scenarios, the higher the accuracy, the more finely the location units need to be subdivided and surveyed in order to make a radio map. Consequently, there is often a trade o between accuracy and other practical considerations.

Precision provides the knowledge of how consistently a system works. It indicates how convergent the localization results can be over many trials. Theoretically, location precision is the performance indicator of the location estimation itself, which has no relationship to the true 2.4. The performance metrics location. However, usually location estimates are assumed to follow a Gaussian distribution, with the mean centered at the true location. Under this assumption, higher precision means a larger fraction of location estimates are will be located near the true location. Indeed, a preferable approach to indicate the degree to which location estimates accumulate near the true value of the position, is the Cumulative Distribution function (CDF). The CDF describes the distribution of the distance error between the estimated location and the true location. Thus when two positioning techniques are compared, if their accuracies are the same, we shall prefer to exploit the CDF of them.

Robustness

Robustness of a localization system is very important, as it allows the system to function normally without human intervention when the operating environment changes. For example, some signal transmitters could be out of service occasionally; or, room layout changes could cause some signals to no longer propagate in an LOS fashion. RSS is time varying due to environmental e ects. In such a case, localization systems are obliged to deal with incomplete or noisy information in order to estimate location. Creating and maintaining a localization system is expensive in terms of time, labor and monetary cost. Thus, when such a localization system is built, the hope is that it will continue to operate properly for a long time. Robustness can be achieved, for example, by introducing redundant information into a location estimation. Thus for triangulation, rather than using the minimum required number of reference points, including many supplementary points can help make the system more robust. Fingerprinting approaches, in turn, can adopt a larger set of RSS values in order to increase robustness.

Complexity

The complexity of a localization system concerns both hardware and software. As for hardware, it will depend on the adopted technology and chosen measured quantity. As for software, complexity is in part reflected in the computation load represented by the calculations required to perform localization. If the execution of the positioning algorithm is carried out on a centralized server, the positioning could be calculated quickly due to its powerful processing capability and abundant power supply. If it is instead carried out on the mobile unit itself, the e ects of complexity could be more evident, as most mobile units employ less powerful processors powered by batteries. Sometimes, complexity must be compromised in favor of other desirable characteristics, such as high accuracy, for example.

Scalability

A localization system with good scalability is supposed to function normally when the scale of required positioning capability increases. When an indoor localization system is constructed, it of course provides services in a limited area. Or, in some cases, its user capacity could be limited by bandwidth and processing time considerations. At some future time, though, an upgrade might be needed, to extend coverage or increase user capacity, let us say. Scalability means that the system does not need to be taken down and totally rebuilt in such a scenario. Typically, the coverage areas of localization systems based on proximity and triangulation are easy to expand by simply adding additional, identical hardware, or increasing transmit power. Fingerprint based systems, however, which necessitate an o ine site survey stage, have relatively low scalability.

Adding new signals into fingerprints, for example, would necessitate a re-calibration of the entire system.

Cost

The cost of a localization system refers not only to monetary outlay, but also to questions of time, e ort, space and energy. It depends on many factors, including how the system is built, the required accuracy, and the size of desired coverage area. Some signals such as GSM and WiFi have already been extensively deployed for other purposes, but can still be used for localization.

If a localization system is based on existing infrastructure, substantial savings in infrastructure costs can be realized. The time and e ort factor relates to system installation and maintenance procedures. Consequently, if a localization system is robust and scalable, a saving in time and 2.5. Summary labor may be possible. Space is another consideration in that many indoor localization systems require a dense deployment of dedicated beacons, which may be di cult to realize in certain indoor environments. Power consumption is also a critical issue, for both fixed reference nodes and mobile nodes. Due to the space constraints, the reference nodes may not always be plugged into mains, and battery life is always a concern for mobile users. There are many factors involved in power consumption considerations. For example, Bluetooth is less power hungry than WiFi.

Also, if the location estimation is carried out on the server side, the power consumption of the mobile devices can be reduced. Finally, the desired system accuracy and location update rates will also influence battery life.

Summary

This chapter reviews the technologies that indoor localization can be based on, the fundamental methods for location estimation and some key metrics to evaluate a localization system.

Indoor localization is a challenging task and various technologies are considered to deal with this challenge in complex indoor environments. Current indoor localization systems are mainly based on the radio frequency technologies such as GPS, cellular networks, WiFi, Bluetooth, RFID and UWB, but there are also solutions based on light waves and acoustic waves. In addition, mobile sensors are becoming more and more popular in mobile devices, and can provide an additional complementary source of information for beacon based systems. The adoption of location calculation and estimation algorithms depends predominantly on the selection of a localization technology and a set of physical quantities to measure (time, RSS, etc.). There are four categories of location estimation approaches: proximity; triangulation; fingerprinting; and sensor dead-reckoning. Performance metrics are used to evaluate a localization system in di erent aspects, determined by the chosen localization technology, the measured quantities selected, and the location estimation algorithm adopted. As some performance metrics are conflicting, it is reasonable to make some compromises in a practical deployment of an indoor localization system.

Of course, not all technologies and measuring quantities are easily available on standard mobile devices, even though these may achieve very good localization performance in many respects using their inherent capabilities. Among the variety of possible RF technologies that common mobile devices support, this thesis adopts the use of the GSM system, to explore its feasibility and

Chapter 2. Indoor localization fundamentals performance as a practical indoor localization system. Indeed, compared with other solutions, indoor localization based on GSM has the following advantages:

• GSM signals are near pervasive, much more so than the typical 3G and 4G signals. The 4G networks operating in the 800 MHz could also be viable, but deployment of these networks is very recent.

• Indoor localization based on GSM networks can leverage existing hardware and the network infrastructures. Most cellular mobile devices continue to support GSM, which enables GSM based indoor localization to serve large number of users without requiring additional hardware. The cellular networks are well deployed and maintained by network operators.

• GSM networks are operated in licensed frequency bands, which are not likely to have interference from nearby devices operating in the same band, as is the case with wireless signals like WiFi and Bluetooth operating in the very crowded ISM bands.

• GSM networks are robust in two important ways. First, cellular mobile stations are unlikely to evolve, change, or be frequently reconfigured, which leads to a stable signal environment that can be the basis for indoor localization system to function over a long period without additional calibration. Secondly, cellular systems are designed to continue functioning even in the case of a power supply failure, which allows a GSM based indoor localization system to work even in the event of an electrical system failure in a building.

These advantages indicate that according to the performance metrics introduced above, indoor localization based on the GSM networks would be with low cost, low complexity and high robustness, which benefits from the near-ubiquity and stable operating of GSM networks.

Though 4G LTE has arrived, GSM is slated to continue operating at least through 2021. In addition to the existing large amount of cellular mobile devices supporting GSM, MEMS sensors are increasingly popular in these devices, which allows for the potential hybrid approaches that combine GSM and inertial sensors. In regard to the low scalability which is a common shortcomings of fingerprinting based localization techniques, it is a compromise but not painful if necessary, since the calibration process is done o ine. Finally, earlier studies have shown that accurate indoor localization based on GSM is viable and promising [START_REF] Varshavsky | Are GSM phones the solution for localization? The 7th IEEE Workshop on Mobile Computing Systems & Applications[END_REF][START_REF] Varshavsky | GSM indoor localization[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF], which lay the groundwork for what will be studied in this thesis.

Chapter 3

Characteristics of GSM signals

Introduction

As mentioned in the previous chapter, this PhD work focuses on indoor localization based on the GSM networks, which distinguishes di erent indoor locations using RSS fingerprints, i.e. sets of RSS from a number of GSM channels.

In this chapter, an overview of GSM networks, the basis of the indoor localization approaches investigated in this thesis, is first presented, including the system architecture and radio air interface. An interesting aspect of the GSM norm, the fact that GSM mobiles must be able to rapidly measure RSS values of large sets of GSM channels, is stressed. An analysis of GSM signal properties is then presented, which aims to explain the causes of RSS variations over space and time. Indeed, to reliably di erentiate spatial locations, measured RSS values must be correlated with position, but relatively robust over time. The RSS of GSM signals are further explored using real measurements on two di erent types of data acquisition devices. It is demonstrated that RSS from a single GSM channel does not provide adequate location distinction, while fingerprints containing RSS from all available GSM channels do indeed show strong location-related properties, assuring us that accurate indoor localization based on RSS fingerprints will be viable.

An overview of GSM system

Architecture of GSM network

The GSM network architecture can be divided into three sub-systems: the Radio Subsystem The NSS is responsible for all functions required to handle the signaling protocols through 3.2. An overview of GSM system The OSS is in charge of remote operations and maintenance of the GSM network. The Authentication Center (AUC) is a strongly protected database that handles the authentication and encryption keys for all subscribers in the HLR and VLR. The Equipment Identity Register (EIR) is a database containing the identification of all devices registered on the GSM network.

In case a MS is reported stolen, the EIR can block the device based on its International Mobile Equipment Identity (IMEI).

GSM radio air interface

The radio air interface is the primordial interface of any mobile communication system, and is important for the quality and success of a mobile standard. It must make e cient use of available frequencies as the available spectrum is quite limited. Although there are a total of fourteen di erent recognized GSM frequency bands, GSM networks are mostly operated in the 900 MHz and 1800 MHz bands, details of which are shown in Table 3.1. As Frequency Division Duplex (FDD) is used in GSM system, the frequency are separated into the downlink and uplink with a duplex split of 45 MHz (GSM 900 band) or 95 MHz (GSM 1800 band). Multiple Access (TDMA) on the air interface, resulting in a two dimensional channel structure as shown in Figure 3.2. The FDMA scheme involves the division by frequency of the bandwidth into 200 kHz wide carrier frequencies, which are specified by their Absolute Radio Frequency Channel Number (ARFCN). There are 174 and 374 carriers in GSM 900 and GSM 1800 respectively. Each carrier is then additionally divided into time slots using a TDMA scheme, which accommodates di erent users on a single carrier frequency in di erent time slots, without mutual interference.

The smallest data subunit is the "burst", transmitted within a time slot. Each GSM time slot lasts for 0.577 ms, and eight time slots, numbered from 0 to 7, are grouped into a TDMA frame lasting approximately 4.615ms. In order to avoid frequency selective fading, and to mitigate adjacent-channel interference, GSM specifies an optional slow frequency hopping mechanism, in which MS and BTS change carrier frequency from frame to frame based on a known hopping sequence.

TDMA frames repeating indefinitely, with the recurrence of one of the eight time slots on a particular carrier frequency making up one physical channel. A physical channel is thus determined by the carrier frequency, or a number of carrier frequencies with a defined hopping sequence, and the time slot number. There are thus 8 physical channels per carrier frequency in GSM. Logical channels are defined according to the type of information they contain, for example, data or signaling information. Logical channels are mapped onto physical channels in specific ways as 3.2. An overview of GSM system

GSM sign on procedures

When a mobile station is switched on, after performing the initial boot up procedure of hardware initialization and software setup, its first task is to find a suitable BTS to access to the GSM network. As mentioned above, all BTS broadcast their beacon carriers via the BCCH channel. The mobile station must obtain a list of beacon carriers to find a suitable cell to camp on. This process is called cell selection. The mobile station may have stored a BCCH frequency list in its memory or SIM card when last switched o . In this case, the mobile station scans the BCCH frequency in the list, which reduces the time of cell selection. In some cases, though, where the list was not successfully stored or no BCCH frequency can be found in the list, the mobile station must to cover the entire frequency band and measure the Received Signal Strength Indication (RSSI) of all carrier frequencies. Once the scan completed, the carrier frequencies are arranged in a list with descending order of signal strength. Then the mobile station will tune to the strongest carrier frequency, checking if this is a BCCH carrier by looking for a frequency correction burst send by the Frequency Correction Channel (FCCH), a part of the BCCH suite, which is a burst of pure sine wave. The strongest carrier frequency, however, could be a TCH instead of a beacon. In this case, if an FCCH burst, which occurs every 10 frame intervals in the time slot 0 of a BCCH carrier, is not detected, the mobile station will go to the next strongest carrier in the list and repeat the procedure. Once an FCCH burst is found, the MS will try to decode the Synchronization Channel (SCH) information in order to read the Base Station Identity Code, BSIC.

Subsequently the MS will read the BCCH to recover system information such as Cell Global Identity (CGI), Location Area Identity (LAI), BCCH carriers of the neighboring cells, maximum output power allowed in the cell, and other broadcast messages. Then the mobile station can camp on this cell and go to idle mode, from which it wakes up periodically to listen to the CCCH and BCCH.

GSM signal strength

A measured RSS value will of course depend on the transmit power level of the BTS, which is defined in GSM 05.05 but may also be specified by the network operator according to needs.

The transmission power depends on the output power of the power amplifier and the losses from power amplifier to the antenna connector. Output power is a fundamental transmitter characteristic and is linked directly to range. Adaptive control of the RF transmit power of the BSS is also implemented in order to optimize link performance and minimize power consumption in the mobile station and co-channel interference. However, as mentioned earlier, the BCCH carrier is continuously transmitted on all TDMA frames without variation of RF power level.

Intuitively, RSS measurements on the fixed-power beacon channels would seem the best adapted for positioning applications. We shall return to this point later.

3.

2. An overview of GSM system The RSS is also influenced by path loss, shadowing and multipath e ects, as illustrated in

RSS measurement of GSM signals

Measuring RSS of GSM networks is the starting point for the fingerprinting based indoor localization studied in the thesis. As already mentioned, according to the GSM standard, any GSM mobile device must have the ability to measure the RSS on all carrier frequencies. In addition, in normal operation an MS will often move from one BTS to another during a handover if the quality of the link to the current base station becomes unacceptable. The handover protocol requires the handset to regularly provide measurements of the received power, not only of its current serving cell, but also of several neighboring cells, so that a list of possible handover targets may be assembled. Finally, the slow frequency hopping mechanism requires GSM phones must be able to jump from frequency to frequency quickly. It follows that any standard cell phone has the ability to measure the power level on any of the frequency carriers present in a typical GSM system (174 for GSM 900 and 374 for GSM 1800). It also must be able to synchronize with base stations at any of these frequencies, in order to recover network parameters such as the BSIC. To ensure the su cient accuracy for the correct functioning of the system, GSM standard requires the RSS be measured by the mobile stations over the full range of ≠110 dBm to ≠48 dBm.

RSS measurement devices

Although GSM mobile devices must have the ability to measure the RSS on all carrier frequencies, normally they are not able to save the RSS scan result to local storage for later analysis. Consequently, in this thesis, two types of data acquisition devices were used to record the GSM RSS, namely the Telit GM862 GSM/GPRS modules [START_REF]GM862-GPS module[END_REF] and the ASCOM TEMS

Pocket [START_REF]TEMS Pocket[END_REF].

The Telit GM862 GSM/GPRS module is a Machine to Machine (M2M) module, which is shown in Figure 3.4. It is made up of several components including a GSM chip with an antenna, a GPS chip, an ARM microcontroller, power supply unit and some accessories. The GSM chip is controlled by the ARM microcontroller to initiate scans of GSM RSS on multiple carriers using AT commands. It can perform a full scan recording the ARFCN and RSS level RxLev at all GSM carrier frequencies and decode the BSIC for all carriers in about three minutes. The scan results are recorded in a memory card installed on the board for later analysis. another aspect, which is that any standard mobile phone supporting GSM is potentially capable to get full carrier RSS scans, employing only a software modifications.

RSS measurement of GSM signals

Analysis of RSS measurements

The location fingerprinting technique discriminates locations based on location-dependent measured RSS values. Consequently, we would like RSS to be distinctive over di erent locations while remaining relatively consistent over time, thus ensuring a time-robust localization system.

In this section, the GSM signal strength characteristics, particularly its behavior over location and over time, are investigated, via measured data. All data here is acquired using the Telit GSM/GPRS module.

An experiment was performed in a room of a 4th floor laboratory building (steel frame, In the experiment, the day-night e ects of RSS is also observed, as shown in Figure 3.9. It is seen the mean RSS have obvious fluctuation between day and night, higher in the night, and lower by day.

RSS changes with di erent locations are described in Figure 3.10, where the X axis are the locations from 1 to 8 (Figure 3.5) and Y axis are the RSS. In this figure, a beacon carrier (carrier index 537) and a non-beacon carrier (carrier index 46) are compared, which are drawn in blue line with squares and red line with circles respectively. In each location, the lower bound, upper bound and mean value are presented. Generally, the a carrier labeled "beacon" has higher RSS and less fluctuation compared with one labeled "non-beacon", although, again, we must interpret BSIC decoding with care. The figure shows that there is no clear distinction in RSS values among the eight di erent locations, neither for beacon nor for non-beacon carriers. We conclude that

RSS measurement of GSM signals

Location dependent properties of GSM fingerprints

As indicated above, a single carrier does not display any obvious correlation between RSS and locations. This chapter examines fingerprints incorporating RSS measurements at all carrier frequencies, which therefore contain much richer information about the local radio environment and may therefore provide superior location discrimination capability. The following describes an experiment done to explore the location-dependent properties of GSM fingerprints.

In the experiment, four Telit modules were placed in a group, at the four vertices of a square with the side length of one meter. This Telit module group was then put at four di erent locations successively as shown in Figure 3.11. In each location, data was collected consecutively over five days, and about 600 scans were obtained by each Telit module. The dataset recorded in group i was called C i , and accordingly the dataset recorded by Telit module j of group i was called as

C ij .
Fingerprint distance, defined as the Euclidean distance in the signal strength space, is

d i,j = î ı Ù N ÿ n=1 1 RSS n i ≠ RSS n j 2 2 (3.3)
where RSS n i is the nth entry of fingerprint RSS i and N is the size of the fingerprint, which in this thesis is 548. Accordingly, the average intra group fingerprint distance is defined as:

d Cij ,C ik = î ı Ù N ÿ n=1 1 RSS n Cij ≠ RSS n C ik 2 2 (3.4)
where RSS Cij is is defined as the average fingerprint of dataset C ij . And the average inter group fingerprint distance:

d Ci,Cj = î ı Ù N ÿ n=1 1 RSS n Ci ≠ RSS n Cj 2 2 (3.5)
where RSS Ci is is defined as the average fingerprint of dataset C i . Average fingerprint distances both intra group and inter group are shown in Figure 3.12.

As can be seen in the figure, though the fingerprint distance is not proportional to the geometric Figure 3.12 -Comparison of fingerprint distance and geometric distance. The intra-class distances (blue line) are the average fingerprint distances of each two datasets in the same group; the inter-class distances (red line) are the average fingerprint distances of all datasets in each two groups distance, the intra group fingerprint distances are smaller than the inter group fingerprint distance in most cases. This indicates that the GSM fingerprints in nearby locations have a certain level of similarity, which is the basis of indoor localization using GSM fingerprints. However, there is still one exception in which the intra group fingerprint distance is about the same as the inter group fingerprint distance. One might expect, however, that better discrimination could be obtained with a more sophisticated analysis, a point to which we will return in the upcoming chapters.

Summary

This chapter first introduces the GSM network, including the architecture, radio air interface, sign on procedures and signal strength and propagation, which are the basis of the indoor localization techniques investigated in this thesis.

Then, two types of data acquisition devices are introduced and the characteristics of RSS measurements are examined. RSS are stable over time in a certain location, but with some fluctuations. In addition, the day and night e ect is observed, which indicates that in the same position RSS are higher in the night and lower in the day. Considering the location related Chapter 4

Indoor localization using GSM fingerprints 4.1 Introduction

This thesis investigates indoor localization using very high dimensional GSM fingerprints containing RSS from all the GSM carriers. According to the performance metrics of a localization system introduced in section 2.4, the indoor localization system based on GSM networks will have the advantages of low cost, wide coverage, and simplicity. Nevertheless, accuracy and robustness are key parameters to a localization system: they determine how small an area the system can distinguish and how long the system can function properly. In this chapter, the focus is on the accuracy and robustness problem of indoor localization using GSM fingerprints.

Coordinate location from RSS is first studied, which tries to find a functional relationship between locations and the GSM fingerprints obtained in these locations. SVM regression is used to map the high dimensional GSM fingerprints to locations. The experimental results, however, show that no such relationship exists for the tested indoor environment, indicating that interpolation and extrapolation schemes based on RSS measurements at a small number of points will not be viable for localization. Then, indoor localization based on fingerprint classification is presented, in which the mobile's position is estimated by classifying sets of fingerprints, obtained from distinct spatial regions, making use of a model constructed in a previous training phase. As the RSS vary within di erent positions even in the same region and interpolation and extrapolation schemes do not work, a "space sampling" scheme is proposed to randomly acquire data at points throughout the interiors of the spatial regions of interest, rather than at only a few representative points. This is achieved using the TEMS Pocket data acquisition device, which enables the collection of large amounts of data on a reasonable timescale. Experimental results show that GSM fingerprints acquired in this way can be used to di erentiate rooms of about 10 square meters size in some 94% of cases, indicating that the classification method is promising. Meanwhile, the RSS fluctuate over time, making the localization performance decrease significantly after a period of time, which is observed by experiments spanning several months.

Attempt to obtain position coordinates from RSS fingerprints

In section 4.3.3, transductive inference is studied, which uses new, incoming unlabeled data to update SVM classifiers as a means of reducing performance degradation caused by RSS drift. In addition, a "time sampling" scheme is proposed in section 4.3.4: fingerprint examples are taken in di erent time slices over several days or even longer periods of time. Such a sampling scheme incorporates di erent types of RSS fluctuations and better represents the statistical properties of fingerprints. Long term experiments demonstrate that with the "time sampling" scheme the performance of the proposed localization system remains stable over months.

The post-processing of indoor localization is presented in the last section: it involves using Bayesian filtering to employ a priori information about the indoor layout and mobile's trajectory for the correction of possible errors in the raw classification results.

Attempt to obtain position coordinates from RSS fingerprints

The idea of obtaining coordinate location from RSS fingerprint comes from the relationship between fingerprint distance and geometric distance studied in section 3.3.3 where it is shown that the nearby locations have similar RSS fingerprints. If locations can be abstracted, using fingerprint examples taken at a small number of representative points, as a function of RSS fingerprints, coordinate locations can be determined according to such a function by mapping RSS fingerprints to locations. This is interesting in that not only coordinate locations can be obtained, but time and labor consuming site survey work can be significantly mitigated. In the thesis, the relationship between locations and RSS fingerprints is explored by a regression method using fingerprint examples taken at locations in a line. Since the number of variables in a fingerprint is very large (548 carriers) and the size of the training set is relatively limited, SVM regression is deemed appropriate because of its built-in regularization mechanism [START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods[END_REF][START_REF] Smola | A tutorial on support vector regression[END_REF].

SVM regression algorithms

Consider a given dataset of n RSS scans {(x 1 , y 1 ), (x 2 , y 2 ), • • • , (x n , y n )}, where x i is the fingerprint vector at location i and y i is the coordinate of the location (assuming that 1-D localization is performed). There exists a variety of Support Vector Regression (SVR) techniques, serving di erent purposes. Á ≠ SV R, which is used here, aims to find a parameterized function f (x, ◊) such that prediction errors ||y i ≠ f (x, ◊)|| do not exceed a given Chapter 4. Indoor localization using GSM fingerprints value Á for all elements of the training set, and, at the same time, is as regular as possible, i.e.

does not oscillate unnecessarily. Assume that we are looking for a linear relationship between the RSS fingerprint and the location. The function has the form:

f (x, ◊) = w • x + b (4.1)
where ◊ = [w b] T . The parameters are sought as solutions to the constrained optimization problem:

minimize 1 2 ||w 2 || subject to ||y i ≠ w • x i ≠ b|| AE Á (4.2)
The optimal solution, if it exists, can be shown to be of the form

f (x) = n ÿ i=1 - i y i (x i • x) + - 0 (4.3)
where the -

i (i = 0 • • • n) are solutions of a constrained quadratic optimization problem.
If such a solution does not exist, slack variables ' i and ' ú i can be introduced to relax the constraints for positive and negative training examples respectively, allowing some examples of the training set to be predicted with an error larger than Á. The problem becomes:

minimize 1 2 ||w 2 || + C n ÿ i≠1 (' i + ' ú i ) subject to Y _ _ _ _ ] _ _ _ _ [ y i ≠ w • x i ≠ b AE Á + ' i w • x i + b ≠ y i AE Á + ' ú i 'i ' i , ' ú i Ø 0 (4.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

f (x) = n ÿ i=1 - i y i K(x i • x) + - 0 (4.5)
where K(x, y) is called the kernel function. In experiments of this thesis, linear and nonlinear regressions (using Gaussian and polynomial kernels) were performed, using the Spider toolbox [START_REF]The Spider SVM toolbox[END_REF].

Evaluation of SVM regression for indoor localization 4.2.2.1 Data acquisition and datasets

Data was recorded in the same setting as introduced in 3.3.2. In the experiment, eight identical Telit modules were placed at fixed positions, in a line, spaced at an interval of 0.6 meter. A total of 600 GSM scans per module were recorded over 5 working days. Each scan includes the RSS of all 548 carriers in the GSM 900 and GSM 1800 bands, containing RSS values ranging from ≠108 dBm to ≠40 dBm. All the scans were labeled manually with locations from 0 to 4.2 meters indicating where the scan was made.

SVM regression results

The results of SVRs are estimated through the mean squared localization error as

1 8 8 ÿ k=1 î ı Ù 1 600 600 ÿ i=1 [y k ≠ f (x ik , ◊ ≠k )] 2 (4.6)
where y k is the position of measuring device k, x ik 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 4.1. The soft margin parameter C, polynomial degree d and the Gaussian kernel parameter were selected through cross-validation. The result from linear LS regression is also given for comparison.

Table 4.1 -SVM 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

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 fingerprint and the position in a small indoor environment can be found. 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.

Chapter 4. Indoor localization using GSM fingerprints

Room-level indoor localization

As an alternative scheme, the fingerprinting technique is used and the indoor localization problem is considered as a multiclass classification problem. As such, an indoor environment is divided into di erent locations, which are distinguished by separating surfaces in the fingerprint space. The main task of building a localization system is to determine the separating surfaces, based on fingerprint examples taken o ine. In the thesis, SVM classification technique is used to find the equations of the optimal separating surfaces between locations.

The locations at which measurements are performed can be grid points, specific reference points, or regions, depending on the targeted application and desired accuracy. For most indoor location based services, such as indoor navigation, advertising, rescue, etc., room-level is perfectly adequate. Furthermore, the fingerprinting classification method requires more detailed training data sets as region sizes are reduced, which is time and labor consuming, and results in increased computation time in both the training phase and localization phases. As a trade o between accuracy and ease of implementation, room-level localization was therefore chosen in the thesis.

SVM classification algorithms

There are plenty of statistical learning techniques, which aim to solve classification tasks like location fingerprinting: k-NN classifiers, Bayes classifiers, linear discriminant analysis classifiers, neural network classifiers, classification trees, SVM classifiers, etc. SVM classification techniques have proved very powerful [START_REF] Brunato | Statistical learning theory for location fingerprinting in wireless LANs[END_REF]. Reference [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] describes the first application of SVM classifiers to localization with a large number of GSM carriers. SVM classification techniques provide a good out-of-sample generalization, if the regularization parameters are chosen appropriately. Since the optimization problem solved for training SVM is convex, as explained in the next subsection, it delivers a unique solution. Moreover, it uses the "kernel trick" [START_REF] Cristianini | An introduction to support vector machines and other kernel-based learning methods[END_REF], which allows for transforming the linearly inseparable training data to some other spaces where the problem can be solved.

Regarding the specific localization problem, SVM is e ective for classifying high dimensional RSS fingerprints, and the computational complexity of SVM in the online localization phase is very low, as most of the computation is done in the o ine training phase.

Pairwise classifier

As a starting point for multi-class classification, a pairwise (also termed "two-class" or "binary") classifier is first introduced.

Room-level indoor localization

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

f (x) = M ÿ i=1 - i y i (x i • x) + - 0 (4.7)
where thei (i = 0 If the examples are not linearly separable, one resorts to nonlinear SVM, whereby the separation surface is of the form

f (x) = M ÿ i=1 - i y i K(x i • x) + - 0 (4.8)
where K(x, y) is a kernel function that must be positive semi-definite.

As for linear SVM, thei 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 trade o 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. 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 (4.7) or (4.8) for linear or nonlinear SVM classification respectively. x i is the ith fingerprint in a given dataset. In the indoor localization problem, a number of locations need to be distinguished, which is a typically multiclass classification problem.

Decision rules for multiclass discrimination

For the indoor localization problem which obviously needs to distinguish not only two, but multiple locations, 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. 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.

Room-level indoor localization

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.

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 the others. The data used in the experiments was obtained by scanning the entire GSM band in 7 rooms of the laboratory building, hereby named "laboratory site". In April of 2012, on a Saturday afternoon from 2 pm to 6 pm, 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 4.5. Each scan contains the RSS of all 548 carriers in the GSM 900 and GSM 1800 bands, with values ranging from ≠117 to ≠38 dBm. All scans were made during "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.

SVM classification results

The As can be seen in the table, the SVM room classifiers give correct results about 94% of the time with no significant di erence between linear and nonlinear kernels. As expected, results from k-NN classifiers are significantly poorer. We also note that the GSM 900 (174 carriers) and GSM 1800 (374 carriers) bands are complementary in that better localization accuracy is obtained when both bands are present in the fingerprint. In Chapter 4. Indoor localization using GSM fingerprints

The evolution of classification performance

These SVM classifiers work well on the data recorded in the same day, but a significant performance decrease was also observed after a period of time. After the model was constructed, subsequent experiments and verifications were performed for more than 6 months. Three datasets were recorded in the same setting as introduced in section 4. Indeed, due to shadowing, multipath and environmental e ects such as building geometry, network tra c, presence of people, and atmospheric conditions, RSS is expected to be nonlinear with distance, non-Gaussian, and time varying, which can lead to performance degradation over time. In addition to the short-term fluctuation and day-night variations presented in section 3.3.2, sudden shifts of RSS in some GSM channels were also observed in a long-term experiment over two months. Chapter 4. Indoor localization using GSM fingerprints approaches, since calibration has already been time and labor consuming. In this thesis, maintaining the localization performance over time is studied, by introducing 1) transductive inference to update the localization classifiers with new unlabeled data and 2) a more general sampling method, "time sampling".

Evaluation of transductive SVM

y i (w • x i + b) Ø 1 y ú j 1 w • x ú j + b 2 Ø 1 'i, j (4.10)
where x ú j is the unlabeled data and y ú j is the label corresponding to x ú j given by TSVM. Therefore, minimization must be performed with respect to w, b, x ú j and y ú j for j = 1 • • • N , in contrast to standard SVM 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 vector machines[END_REF][START_REF] Chen | Learning with progressive transductive support vector machine[END_REF]. The TSVM used in our study, were implemented using SVM Light [START_REF] Joachims | Advances in kernel methods. chapter Making large-scale support vector machine learning practical[END_REF].

Transductive SVM results

TSVM were applied to the four datasets presented in section 4. As can be seen in Table 4.4, when building the classifier with set S1 and testing it on sets S2, S3 and S4 taken in di erent 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 examples of each room with the TSVM, a substantial amount of the lost performance can be recovered.

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 su cient, 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. Chapter 4. Indoor localization using GSM fingerprints

Evaluation of the "time sampling" scheme

The "time sampling" scheme and datasets

As discussed in section 4.3.2.3, RSS su ers from fluctuations on di erent time scales. To counteract the e ect of these fluctuations, a "time sampling" scheme was also used in recording the datasets. On each day where measurements were made, fingerprints were recorded at di erent time periods from morning to evening. Such training data, over extended period of time, are thus expected to provide a better sampling of RSS fingerprint values.

Scans were recorded during random walks in all seven rooms shown of Figure 4.5 and manually labeled with the corresponding room numbers. While scanning a room, the TEMS Pocket was turned on and held in hand while walking; then, after a few minutes, the scan was stopped.

Datasets were recorded on thirty-four di erent days between December 15, 2012 and March 01, 2013.

Results of the "time sampling" scheme

Classification results using "time sampling" are shown in if the localization model is trained using data recorded in the first two days, the test performance afterwards is improved dramatically to between 70% and 80%, and stays reasonably constant. An even better performance is obtained by the model trained using a dataset of 8 days, which reaches 90% accuracy a few days after the model is built and, in most cases, retains a performance in excess of 80% even more than fifty days after training. Training during longer periods does not further increase the performance. of the updated classifier is relatively stable and consistent with the more gradual performance degradation observed before the network changes occurred.

Bayesian filter post-processing

Localization accuracy achieved by the current measurement can be improved by taking previous measurements into account. Due to the fast scanning property of TEMS Pocket, about three measurements per second can be obtained. In practical scenarios, updating the location every second is acceptable, since a mobile user does not move too far away in one second.

Hence, a simple approach to improve the localization accuracy is to apply a low-pass filter, either to the RSS measurements or to the raw results.

In this thesis, post-processing takes into account both the time constraints (the receiver moves with a finite velocity) and the space constraints (presence of walls and furniture, occupancy of the room, etc.). This is achieved by Bayesian filtering, which allows combining the current and previous SVM classifier outputs and taking into account space constraints [START_REF] Chen | Bayesian filtering: From kalman filters to particle filters, and beyond[END_REF].

Chapter 4. Indoor localization using GSM fingerprints

Recursive Bayesian filtering

For room-level indoor localization, let the state x t at discrete time t be the actual room number of the mobile target at time t, and the observation y t the output of the SVM classifier at the same time. We assume that the state at time t depends only on the state at time t ≠ 1. From Bayes' theorem [START_REF] Bernardo | Bayesian theory[END_REF], the probability of the target being in room x t given the past and present outputs of the SVM classifier is:

P (x
where P (y t |x t ) is the likelihood probability of receiving the label y t from the classifier, when the target is in room x t , and P (x t |y t≠1 ) is the probability of the target being in location x t given the label assigned by the SVM classifier at time t ≠ 1. For our room-level indoor localization, we have a finite number of rooms, i.e. finite number of states for filtering. Therefore, we can write:

P (x t |y t≠1 ) = N ÿ xt≠1=1 P (x t |x t≠1 )P (x t≠1 |y t≠1 ) (4.15)
where N is the number of states, and P (x t |x t≠1 ) is the state transition probability from x t≠1 to

x t , which is constrained by the prior information of room layout, target velocity, maximum room occupancy, etc, as described in the next subsection.

Finally we obtain:

P (x t |y t , y t≠1 ) = P (y t |x t ) N q xt≠1=1 P (x t |x t≠1 )P (x t≠1 |y t≠1 ) P (y t |y t≠1 ) (4.16)
It is assumed that the initial probabilities {P (x 0 |y 0 ) = P (x 0 ), x 0 = 1, • • • , N} of the state are known or taken equal to 1/N . Then, in principle, the posterior probabilities{P (x t |y t , y t≠1 ), x t = 1, • • • , N} are obtained, recursively, in two stages: prediction and update, as described in [START_REF] Eena | use of the GNSS to determine caller location in the context of 112 emergency calls[END_REF][START_REF] Insight | Mobile location based services[END_REF][START_REF]Strategy Analytics[END_REF][START_REF] Hofmann-Wellenhof | Global positioning system: Theory and practice[END_REF][START_REF] Varshavsky | GSM indoor localization[END_REF][START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF][START_REF] Brida | On the accuracy of weighted proximity based localization in wireless sensor networks[END_REF][START_REF] Chawathe | Beacon placement for indoor localization using Bluetooth[END_REF][START_REF] Chawathe | Low-latency indoor localization using Bluetooth beacons[END_REF][START_REF]Apple. iOS: understanding iBeacon[END_REF][START_REF] Montaser | RFID indoor location identification for construction projects[END_REF][START_REF] Ozdenizci | Development of an Indoor navigation system using NFC technology[END_REF] and (4-16) respectively. The final estimation of location is taken to be that of the state with the largest posterior probability:

xt = argmax xt P (x t |y t , y t≠1 ) (4.17

Prior information

In this work, the aim is to obtain the most probable location of the device. For the "laboratory site", the indoor environment is modeled as nodes and paths as shown in Figure 4.12. Rooms are the nodes numbered from 1 to 7, and the corridor is split into three sections and modeled as three additional nodes numbered from 8 to 10. The edges between nodes denote feasible paths between rooms. It is desired that the Bayesian filter provides a trajectory that uses feasible paths, and is consistent with the usual velocity of the target. ) is defined in this thesis as:

P (x t |x t≠1 ) = Y _ _ _ _ ] _ _ _ _ [ P 0 , if pathlength(x t , x t≠1 ) = 0 P 1 , if pathlength(x t , x t≠1 ) = 1 0, if pathlength(x t , x t≠1 ) > 1 (4.18)
where pathlength(i, j) is the length of the path from room i to room j. In this work, the lengths of all the paths that directly link two rooms are assigned the value 1.

Observation model

The observations in our case are the decisions of the SVM classification described above (section 4.3.1.2). The likelihood P (y t |x t ) in relation (4.16) can be estimated, given the available data, from the SVM confusion matrix, such as Table 4.3. In a confusion matrix, let C ij be the number of examples that are assigned to class i while the target is actually in room j. Then

P (y t = i|x t = j) ¥ C ij N q l=1 C il (4.

Datasets for Bayesian filtering

The datasets for Bayesian filtering were taken while a user, holding the TEMS mobile phone, walked between the seven rooms, continuously recording the RSS of the moving traces. The actual traces followed were recorded using the mobile phone camera. Nine such tracking datasets were recorded in our experiments. Datasets were recorded on nine di erent days between December 24, 2012 and February 03, 2013. A dataset for building the confusion matrix of ten states were recorded in April 15 and 17, 2013. We note that Bayesian filtering must unfortunately be applied o ine, as the TEMS Pocket does not allow us to access RSS fingerprints in real time.

Results of Bayesian filtering

Bayesian filtering results are shown in Table 4

Summary

In this chapter, indoor localization using RSS fingerprints from the GSM network is investigated, including an analysis of the relationship between signal strength and location, the proposed room-level indoor localization, the degradation of localization performance over time and its solutions, and the Bayesian filtering post-processing.

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 that use a certain number of reference points 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.

The SVM classification has been tested on a dataset acquired in a laboratory building under 4.5. Summary realistic conditions, and experimental results show that the percentage of correct room labeling can be up to 94% if the model is used when no significant RSS drift sets in.

A performance degradation over time is observed in experiments across several months. In order to cope with this 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 nine months, this approach proved capable of restoring a significant part of the lost performance. A more time and labor saving solution is studied, using a proposed "time sampling" scheme to collect RSS fingerprint examples in a more representative way. Experimental results indicate that the "time sampling" data collection scheme leads to a more robust localization, with performances relatively stable over a couple of months.

Bayesian filtering is investigated for localization post-processing, which combines the SVM classification outputs with the characteristics of user movements and the indoor layout constraints.

The indoor layout is modeled as nodes and paths, providing accessible tracks that a target can move in, and this model is consistent with the usual velocity of the target. Experimental results

show that the Bayesian filter substantially improved the raw classification results.

In addition to the experiments in a laboratory building, the proposed room-level indoor localization approach and Bayesian filtering post-processing were also tested in a completely di erent environment, the results of which will be presented in chapter 6.

Chapter 5

Combination of GSM fingerprinting and mobile sensors

Introduction

With the popularity of smart devices such as mobile phones and tablets, more and more mobile sensors are now built into mobile devices. The multiple mobile sensors have the advantages of rapid response rate, light weight and low power consumption. Such mobile sensors as accelerometer and gyroscope provide additional location sources, which are potentially viable for improving indoor localization. Sensor dead-reckoning can be useful for indoor localization by estimating the displacement of a pedestrian accurately over a short distance; however, it is not a usable standalone solution, since it needs a known starting point to integrate the displacement. Sensor drift, noise and disturbances can influence the accuracy of sensor dead-reckoning, and mobile sensors provide information about the mobile device itself, which can di er from those of the user. In this chapter, the thesis investigates the combination of the GSM classification technique with mobile sensor dead-reckoning, acquiring the merits of both techniques and forming a bridge between discrete, room-level localization and continuous coordinate-level localization.

The mobile sensor readings are first introduced, as they are critical to indoor location estimation. The characteristics of three location related mobile sensors, accelerometer, gyroscope and magnetic field sensor, are examined. Then, the fundamentals of sensor dead-reckoning, step detection, stride length and orientation estimation respectively are studied.

Steps are detected by monitoring the peaks and troughs of the acceleration amplitude, plus extra time and amplitude thresholds that prevent step misdetections. A stride length model adaptation technique is proposed to automatically estimate the best parameters for di erent Chapter 5. Combination of GSM fingerprinting and mobile sensors users and environments. Both the gyroscope and the magnetic field sensor are used for accurate and reliable orientation estimations, using a complementary filter. In addition, device positions related to the user in practical scenarios, e.g., in a hand or a pocket, are investigated and a solution is provided to handle arbitrary position changes of the mobile device.

Particle filters have become a powerful tool in location estimation and target tracking systems: they allow combining localization data from a variety of sources -for example, beacon data, embedded smartphone sensors, and building layout constrains. Particle filter data fusion is investigated in section 5.3. It uses room-level positioning results from GSM fingerprinting to correct for accumulated inertial dead-reckoning errors, while also referring to a building map to exclude inaccessible regions and forbid unreasonable movements such as crossing a wall. With this approach, the localization system produces accurate coordinate locations rather than room labels.

Mobile sensor dead-reckoning

As introduced in section 2.2.4, sensor dead-reckoning is the process of estimating the unknown current position based on the last estimated position by adding the displacement computed from the heading direction and the speed information over the elapsed time. For mobile devices, dead-reckoning mainly consists of step detection, stride length determination and orientation estimation, which are based on the mobile sensor readings of the accelerometer, gyroscope and magnetic field sensor.

Mobile sensor readings

Mobile sensor dead-reckoning

Accelerometer

The accelerometer measures the acceleration of a mobile device along three axes. When the mobile device is put in the pocket or held in hand, user movements or gestures are reflected in the acceleration measurements. If the mobile device is placed on a stationary object, the accelerometer measures the acceleration of gravity. A sample of accelerometer readings was taken when the tablet was held in hand walking a small distance. The accelerations along the three axes are shown in Figure 5.2.

It is seen in Figure 5.2 that accelerations fluctuate while walking, exhibiting an approximately periodic rhythm. Since the acceleration of gravity is decomposed into di erent coordinate axes, the mean accelerations on the di erent axes are at di erent levels. As expected, the fluctuations on the Z axis are much larger than on the other axes, which is a result of user walking.

Gyroscope

The gyroscope measures angular velocity around three axes. An example of the gyroscope sensor readings was recorded while the tablet was held in hand walking and turning, as shown in

Magnetic field sensor

The magnetic field sensor measures the direction and strength of the magnetic field along the three axes of the mobile device. An example of the three axes magnetic field sensor readings recorded simultaneously with the gyroscope readings is shown in Figure 5.5

For indoor localization these measurements are converted into a direction, known as the azimuth angle. The advantage of the magnetic field sensor measurement is that it can provide absolute orientation of the mobile device. However, the measurements of the magnetic field sensor have quite a low precision and experience a lot of disturbances in indoor environments.

The absolute orientation from the magnetic field sensor and the relative orientation from the gyroscope can be used together to result in a better orientation measurement.

Chapter 5. Combination of GSM fingerprinting and mobile sensors

Step detection

Step detection is a basic but key part of sensor dead-reckoning, which is commonly based on accelerometer information. Though a variety of step detection algorithms exist in the literature, the peak and trough search approach is reliable and widely used. While walking, position of the mobile device fluctuates with the rhythm of the walking pace, and the accelerometer periodically outputs such fluctuations as up and down acceleration values. If the acceleration value goes from a peak to a trough or vice versa, it is assumed the mobile user has taken one step. The peak and trough seeking algorithm implemented for step detection consists of the following four steps:

1. Initialize the step detector: Set a max = a min = g, where a max is the current maximum acceleration magnitude, a min is the current minimum acceleration magnitude and g is the acceleration value due to gravity.

Compute the magnitude of the acceleration a

i , for current sample i from the measurements using:

a i = Ò a x i 2 + a y i 2 + a z i 2 (

Adaptive stride length model

A stride length value is required in order to estimate the displacement associated with a step.

However, stride length varies significantly for di erent persons and walking styles. The literature the "bounce" of the hip, which we shall refer to as the "frequency model" and "bounce model" [START_REF] Weinberg | Using the ADXL202 in pedometer and personal navigation applications[END_REF][START_REF] Zijlstra | Assessment of spatio-temporal parameters during unconstrained walking[END_REF], respectively.

To verify these, we performed an experiment in which subjects walked a specified path several times at di erent walking speeds.

Step numbers and durations were recorded, while the length of the path was known in advance. The results are shown in Figure 5.7. As seen in the figure, the stride length has a linear relationship with both the step frequency and the acceleration amplitude, indicating that the models are reasonable. Most dead-reckoning solutions using existing models must choose the parameters or estimate them by training on di erent users and environments.

The "frequency model" requires an estimate of the step frequency over a previous period of time, which introduces a delay if no step is detected. By contrast, the accuracy of "bounce model" is easily influenced by environmental di erences, such as going up and down stairs. As there is no stride length model that fits all subjects and environments, we propose to use a particle filter (section 5.3) to adaptively select the best parameters from a range of parameters. The "bounce model" is used in our experiments and we define:

Ï = p(a max ≠ a min ) + q (5.3)
where Ï is the stride length of the current step, p and q are the two parameters that will be estimated in the particle filter.

Orientation estimation

The orientation of a mobile user in our system was estimated based on the accelerometer, gyroscope and magnetic field sensor. Both magnetic field sensor and gyroscope can provide orientation information, but neither gives accurate and reliable moving orientation. The turn rate from a gyroscope can be integrated into an angle increment and the orientation can be obtained by adding it to a known initial azimuth angle; however, integration over long time can introduce an unacceptable cumulative error. Orientation from a magnetic field sensor has no cumulative error, but the magnetic field sensor measurement has slow response rate and poor accuracy, especially in indoor environments where field disturbances always exist. For these reasons, a complementary filter was applied to combine these two orientation sources.

The principle of the complementary orientation filter is shown in Figure 5.8. Suppose the real orientation of the mobile phone at time t is  t . The orientation obtained from the magnetic field sensor  mag t and gyroscope  gyr t containing high and low frequency noises can be denoted as  t + ‡ hf t and  t + ‡ lf t respectively. On one hand, a low pass filter is applied to the orientation obtained from the magnetic field sensor, which filters the high frequency noises and has the Laplace transfer function as:

ˆ mag (s) = 1 1 + T s 1 (s) + hf (s) 2 ¥ 1 1 + T s (s) (5.4)
where mag (s), (s) and hf (s) are the Laplace transforms of  mag t ,  t and ‡ hf t . On the other hand, a high pass filter is applied to the orientation obtained from the gyroscope, which filters the low frequency noises and has the transfer function as:

ˆ gyr (s) = T s 1 + T s 1 (s) + lf (s) 2 ¥ T s 1 + T s (s) (5.5)
where gyr (s) and lf (s) are the Laplace transforms of  gyr t and ‡ lf t . The final orientation estimation takes to be the combination of the outputs of the low pass filter and high pass filter. The transfer function reads: As sensor readings are all discrete time series, a simple implementation of low pass filter, with output y t and input x t at time t, has the form:

ˆ (s) = ˆ mag (s) + ˆ gyr (s) ¥ 1 + T s 1 + T s (s) = (s) (5.6)
y t = -y t≠1 + (1 ≠ -) x t (5.7)
where the output y t is the orientation output, andis a parameter determined by the desired cut-o frequency. Since the low pass filter is applied to magnetic field sensor readings, the input x t here is the orientation given by the magnetic field sensor  mag t .

On the other hand, a simple implementation of discrete-time high pass filter with the same cut-o frequency has the form:

z t = -z t≠1 + -(u t ≠ u t≠1 ) (5.8)
where the output z t is the orientation output, and since the low pass filter is applied to gyroscope readings, the input u t here is the orientation obtained by integrating gyroscope readings, i.e. While walking, a mobile device can be held in the hand or pocket in a variety of di erent orientations, which is very challenging for accurate orientation estimation, an issue largely ignored in most previous studies. Unlike foot-mounted or head-mounted inertial measurement units a xed to the body, the orientation of a mobile device is not always consistent with the user's orientation, depending on the relative motion of mobile device and user. Here, a "switching" scheme is introduced to handle arbitrary position changes of mobile devices, considering the following three situations:

(
• When the mobile device is held with the screen upwards, typically meaning the user is checking content, the orientation of the mobile device and the user are assumed to be consistent. In this case, the orientation of the user is estimated using the complementary filter as introduced above. The orientations obtained in such conditions can be used as reference orientations to calibrate the system.

• When the orientation of gravity changes with respect to the mobile device, as shown in Figure 5.9, the mobile device is assumed to be changing its orientation. In this situation, the orientation estimate stops and the particle filter draws random orientations for each particle to estimate the location.

• When the mobile device is not held with screen upward and the orientation of gravity is not changing axis, the mobile device is assumed to be held stationary or placed in a pocket. In this situation, the complementary filter stops and the orientation is estimated only using the gyroscope:

◊ t = ◊ t≠1 + Â gyr t t
(5.10)

Particle filter data fusion

We aim to obtain the best position estimate of a mobile user at each time step by combining both the GSM fingerprinting result and the sensor dead-reckoning result. The idea behind this is to take the advantage of sensor dead-reckoning that accurately estimates coordinate locations The state space filtering approach is used in order to combine the information from di erent sources and sequentially estimate the variables of interest. Since the posterior distribution is non-Gaussian, the particle filter is thought to be more appropriate and robust than extended or unscented Kalman filters.

System model

Y _ _ _ _ _ ] _ _ _ _ _ [ x t = x t≠1 + Ï t≠1 cos(◊ t≠1 ) + w x t≠1 y t = y t≠1 + Ï t≠1 sin(◊ t≠1 ) + w y t≠1 p t = p t≠1 + w p t≠1 q t = q t≠1 + w q t≠1 (5.11)
where Ï t≠1 is the stride length (equation (5.3)), ◊ t≠1 is the orientation estimation, and w x t≠1 , w y t≠1 , w p t≠1 and w q t≠1 model noise and disturbances. Not all the state transitions based on sensor dead-reckoning are feasible, for example, the state transition may suggest that the mobile user passed through a wall, which is usually due to an erroneous orientation estimate. Map layout information is used to remove these transitions, as explained in the following particle filter procedures.

P (h t = i|room(s t = j)) ¥ c ij q M l=1 c il (5.12)
where room(s t ) is the room number associated to location (x t , y t ) and M is the number of rooms.

Particle filter recursion

The particle filter is a technique that uses the Monte Carlo method to implement recursive Bayesian filtering. In section 4.4. Particle filters use a finite number of random samples (called particles) with associated weights that provide a discrete approximation of the posterior density [START_REF] Gustafsson | Particle filters for positioning, navigation, and tracking[END_REF]. If the number of particles is very large, the discrete approximation approaches the true posterior density with arbitrary accuracy. The particle filter uses a set of particles taken from the previous time step

) pt 1 t≠1 , pt 2 t≠1 , • • • , pt n t≠1 ≥ p(s t≠1 |h t≠1 )
* and the most recent observation h t to produce a set of particles approximately following the distribution of p(s t |h t ). The particle filter algorithm used in our system is implemented in the following four steps:

1. Initialize the particles: Since sensor dead-reckoning requires a starting position for integration, N particles are sampled, based on the output of the SVM classifiers, all with the same weight 1/N . The coordinates (x, y) of the particles are distributed uniformly in each room, while the number of particles in each room depends on the observation distribution p(h 0 |s 0 ). The stride length model parameters p 0 and q 0 are drawn from a uniform distribution over a suitable range.

2. Make predictions based on the system model: When a step is detected, each particle is moved using sensor dead-reckoning results. Map information is used in this step to remove impossible movements. As shown in Figure 5.10, if a particle made a movement that crosses a wall or enters an inaccessible region, it is removed, which, in filtering, is realized by setting the weight of the particle to 0.

Results

Raw GSM fingerprinting results are shown in Figure 5.12, where the X axis gives the sample number along the trajectory and the Y axis the SVM classifier outputs. As seen in the figure, the SVM classifier gives the correct room numbers for most of the test examples, but there are still misclassifications especially in adjacent rooms. The percentage of overall correct classification is 70%. (This result was obtained with a small training set and is not considered to be optimized). Figure 5.13 shows the sensor dead-reckoning results and the results of a particle filter that combines sensor dead-reckoning and map layout constraints. The dashed line in the figure shows the actual trajectory provided for comparison. It can be seen that multiple sensor dead-reckoning, even given a correct starting position, makes many mistakes due to the sensor drift and inaccurate stride length. In a more realistic case, of course, the starting position is unknown. The magenta dot line in Figure 5.13 shows the particle filter results, where only map layout constraints are applied, and the initial locations of particles distribute evenly in room 7. It can be seen in the figure, after a few mistakes at the beginning of the trace, the particle filter quickly outputs the correct location and moving direction of the target. This is due to the map layout constraints, which eliminates all the particles with impossible movements. However, the particle filter makes some mistakes between corridor 8 and room 1, which is the limits of only using map layout constraints. When there are more than one accessible paths, due to inaccurate step detection, stride length or orientation estimation, particles may move to a incorrect path, and thus the Moreover, mobile orientation with respect to user orientation is automatically detected by accelerometer and gyroscope, which estimate orientation by picking the correct orientation coordinate.

The proposed particle filter uses a number of particles to represent the distribution of the current location. The movement of particles is derived from the sensor dead-reckoning, while unreasonable movements such as traversing a wall are eliminated based on the map layout constraints. The location is updated integrating the GSM fingerprinting results when available.

This hybrid approach, which uses GSM fingerprints and multiple sensors that are easily obtainable due to the growing popularity of smart phones, is potentially ready for a practical implementation. Experimental results show that this approach can determine a mobile user's trajectory in coordinate locations with good accuracy.

The core elements of this thesis on GSM fingerprinting for indoor localization have been covered now. The overall conclusions and perspectives will be outlined in the final chapter.

Chapter 6

Complementary Experiments

Introduction

In addition to the main body of work that is presented in the previous chapters, a number of complementary experiments were also carried out.

Firstly, the SVM RSS fingerprint classification technique was also tested in outdoor environments, in order to see whether the approach was viable there. The results indicate that the strength of the RSS fingerprinting approach lies in its application in complex indoor environments. The approach was also evaluated in a railway and subway transfer station, where it was quite successful, demonstrating that it can provide accurate and reliable indoor localization in practical, dynamic underground environments.

In the thesis, indoor localization is done by classifying RSS vectors from a large number of GSM carriers. In another experiment, carrier selection techniques were studied to remove GSM carriers that are less relevant for distinguishing di erent locations. It was found that carrier selection helps in simplifying the system, but does not improve performance. Performance however could be improved using post-processing schemes.

Finally, indoor localization based on WiFi was also studied, since WiFi is increasingly ubiquitous, from outdoor public environments to indoor private spaces. Here, indoor localization is investigated based on the RSS of WiFi, which can be obtained easily using standard mobile devices.

Chapter 6. Complementary Experiments

Work related to the SVM classification 6.2.1 Experiments in other sites

The outdoor space

The good performance of indoor localization using RSS fingerprints is based on the assumption that, due to the complexity of indoor environments, shadowing and multipath e ects render RSS fingerprint distinctive even for fingerprints taken at relatively nearby points.

It follows that in outdoor space, where variations of RSS are mainly attributed to the path loss, accurate localization might be di cult to achieve. Zimmermann et al. [START_REF] Zimmermann | Database correlation for positioning of mobile terminals in cellular networks using wave propagation models[END_REF] employed sparse GSM fingerprints, containing RSS from the current serving cell and six neighbor cells, to do outdoor localization, resulting in an accuracy of 80 meters within 67% of the time in the urban scenario. In [START_REF] Varshavsky | Are GSM phones the solution for localization? The 7th IEEE Workshop on Mobile Computing Systems & Applications[END_REF], the accuracy of GSM fingerprinting in outdoor environments was reported as 75 meters, compared to 2 to 5 meters they obtained in indoor environments. To study the phenomenon using our method, an outdoor experiment was conducted.

Data was acquired in the outdoor space of the campus where the "laboratory site" mentioned earlier in the thesis is located. Seven location cells were defined in which to record the RSS, as shown in Figure 6.1. Each location cell is a square with side length of around 4 meters, which is roughly equivalent to a room-level classification. On November 21 and 22, 2013, twenty one datasets were recorded; the distribution of datasets in time and place is shown in Table 6.1, where an "◊" represents that data is recorded in the given time and location, containing about 600 GSM fingerprint measurements. As the outdoor space is a public parking area, in some time periods, parked cars prevented certain measurements, leading to some irregularities in the datasets.

The underground space

The proposed localization technique was validated in an underground environment, the "Gare de Lyon" railway and subway transfer station located in southeast Paris. This experiment was

Carrier selection

Carrier selection is the process of selecting a subset of relevant carriers for use in model

Gram-Schmidt feature selection

The Gram-Schmidt feature selection uses the Gram-Schmidt orthogonalization procedure for ranking the variables of a model that is linear with respect to its parameters.

Consider a dataset with M candidate features containing N measurements with known labels.

The dataset has the form of an (N, M) matrix, where the ith column

x i = # x i 1 , x i 2 , • • • , x i N $
is the vector of sample values of feature i. The labels can be denoted by an N -vector y. Let the Chapter 6. Complementary Experiments (N, M) matrix fingerprint dataset be denoted as X. The linear model can then be written as y = X◊, where ◊ is the vector of the parameters of the model. To rank the carriers, the first step is to find the most relevant carrier, i.e. the feature vector that best matches the labels. The problem amounts to finding the smallest angle between the feature vectors and the label vector in the N -dimensional space of observations. The angle computation can be done using the following equation

cos 2 1 x i , y 2 = ! x i • y " 2 ||x i || 2 ||y|| 2 , i oe {1, 2, • • • , M} (6.1)
After the first carrier is selected, all remaining feature vectors and the label vector are projected onto the null subspace (dimension M ≠1) of the selected carrier to discard the part of the variation that has been explained by the first selected vector. In that subspace, the projected input vector that best explains the projected output is selected with the same technique as described above, and the M ≠ 2 remaining feature vectors are projected onto the null subspace of the first two ranked vectors. The procedure terminates when all M input feature vectors are ranked, or when a termination criterion is met.

SVM Recursive feature elimination

The SVM recursive feature elimination approach ranks the relevant GSM carriers based on the weights of SVM classification model. As introduced in section 4.3.1.1, a linear SVM classification model defines the separating surface as

f (x) = n ÿ i=1 - i y i (x i • x) + - 0 (6.2)
wherei is the weight of carrier i. If the weight of a carrier is very small, the contribution of this carrier to the overall function value is small. It follows that removing such a carrier does not cause much impact to the separating function.

To rank the carriers using the SVM recursive feature elimination technique, the classifier is trained recursively to pick out the carrier with the smallest weight and put it in a "ranking array" at each time. As a result, for M GSM carriers, in all M ≠ 1 sessions of SVM training need to be performed to rank the carriers. Though this is quite time consuming, all the work is done o ine and does not influence the real-time online localization. There are several approaches to estimate posterior probabilities from SVM results, and in this thesis the method of Platt is applied [START_REF] Platt | Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods[END_REF]. In this method, the posterior probability is approximated by a sigmoid function

Work related to the SVM classification

P (y = +1|x) ¥ P A,B (f ) = 1 1 + exp (Af + B) (6.4)
where f is the output of the SVM classifier. where N + and N ≠ are the numbers of positive and negative examples. In the post-processing stage, two rejection thresholds are set for the binary SVM classifiers:

• Threshold 1: If the function values of all the classifiers are smaller than this threshold, this example is not to be classified into any of the classes with a high degree of belief.

However, the multiclass decision rule has to pick out a class among them, which is unreliable and as a result rejected.

• Threshold 2: If more than one SVM classifier outputs very high values, the decision is also suspicious. Therefore, if the di erence of the two largest values is below this threshold, the example is rejected.

Experimental results of this post-processing approach are shown in Figure 6.7. In a test where the correct classification rate of SVM classification is 80%, if the rejection rate is set to 10%, the performance improves to 83%. Applying this post-processing procedure considerably improves

WiFi indoor localization

WiFi is at present the most widely used wireless local area network technology. WiFi hotspots are extensively deployed in home, shop, o ce and public spaces, and WiFi is a standard feature on nearly all the mobile devices. As a consequence, WiFi has been widely explored as a means for localization in both indoor and outdoor environments.

For outdoor localization, WiFi is complementary to GPS localization, when the GPS signal is too weak or blocked in the urban canyons. Since the accuracy requirement in outdoor space is not very high, a proximity technique is often used, which simply assigns to the mobile user the location of WiFi access point with the highest received power. Alternatively, a centroid or weighted centroid of several WiFi access points is used to get a more accurate location estimate. For indoor environments, proximity approaches are not appropriate in most cases, and although WiFi is nearly ubiquitous, it has been deployed not for localization services, but for data transmission.

As a consequence, localization techniques using WiFi have been developed, but the performance In this section, indoor localization based on RSS from an existing WiFi network is studied.

The experimental setups are first introduced, followed by an analysis of the RSS characteristics of WiFi. Two indoor localization approaches, using fingerprinting and triangulation techniques, respectively, are presented and discussed at the end of the section.

Experimental setups

The WiFi indoor localization experiments were done in the same laboratory building as the laboratory site introduced in section 4.3.2.1. Inside the building are three WiFi AP which are part of the campus wireless local area network and have known positions. In addition, there are also many WiFi AP in other buildings outside the laboratory. The positions of these WiFi AP are unknown, but the signals are available inside the laboratory building. Figure 6.8 shows the experimental site and the locations of the known-position WiFi AP, labeled from one to three. Data was recorded using a HTC ChaCha smartphone with an Android open source operating system. The data acquisition program was developed using Java programming language and Android SDK, and the main interface of the program is shown in Figure 6.9. The program can scan RSS and MAC address from all the available WiFi AP at a rate of ten RSS and MAC pairs per second. In the first position, RSS were recorded when the data acquisition smartphone was put on a desk, while in the second position, the smartphone was held in hand. It is seen in the figure, WiFi RSS is not stable in either of the positions, and especially when the smartphone was held in hand, the RSS have severe fluctuations. The standard deviations of the RSS in the two positions are 1.5 dBm and 4.6 dBm respectively. Meanwhile, the RSS do not show much distinction between the two di erent positions in the figure, indeed the RSS values from two AP overlap in some instances. This indicates that RSS from an individual WiFi channel is not reliable for distinguishing di erent locations.

The comparison between RSS from WiFi and GSM are presented in Figure 6.11, where it can be seen that WiFi RSS have much larger variation.

Fingerprinting

Most of the existing WiFi localization techniques are fingerprint based, using a two stage process as introduced in section 2.2.3. The localization accuracy using WiFi RSS fingerprinting is reported to achieve a few meters in some 90% of the time (4 meters in 95% of the time [START_REF] Wu | WLAN location determination in e-home via support vector classification[END_REF], 3.3 meters in 98% of the time [START_REF] Saha | Location determination of a mobile device using IEEE 802.11b access point signals[END_REF], and 2 meters in 90% of the time [START_REF] Xiang | A wireless LANbased indoor positioning technology[END_REF]). To obtain knowledge about the wall attenuation e ect, RSS are first examined at di erent distances without wall attenuation in the LOS signal propagation path. Measurements were acquired by the mobile phone held in hand, walking away from the access point. During the whole measuring process, the access point is visible. Figure 6.13 shows the RSS measurements with di erent distances to the access point, where the relationship between distance and RSS is clear.

A distance-RSS function model was obtained using the least square polynomial approximation.

In the figure, the red star points are the distance predictions from the RSS measurements.

The distance predictions from RSS indicates that without wall attenuation e ect a smooth functional relationship between distance and RSS can be obtained, i.e., weaker RSS correspond to greater distances. In the general case including NLOS, walls need to be taken into account for estimating the distances from an access point. In the thesis, a piecewise functional model was built based on the number of walls between the access point and receiver, using a machine learning method. Figure 6.14 shows the samples and models obtained for the three access points 6.4. Summary Figure 6.13 -Relationship between distance and RSS in LOS propagation path and di erent numbers of walls. It is seen in the figure, for di erent numbers of walls, that the relationships between distance and RSS are quite di erent, and using multiple models based on the number of walls between WiFi AP and receivers accordingly can output more reliable distance estimation from RSS. However, even when separated by an equal number of walls, the RSS at a given distance still has a wide distribution. It follows that RSS, used in this way, is not a reliable distance indicator, which can be used for simple but not very accurate indoor localization.

Nevertheless, if there are more WiFi access points to provide redundant distance estimations, the performance could certainly be improved.

Summary

This chapter encompasses the fragmented work that is done during the thesis, including the work related to the SVM classification and indoor localization based on WiFi networks.

The indoor localization approach proposed in this thesis is tested in outdoor and underground spaces. Experimental results demonstrate that such an approach can be accurate and reliable in indoor and underground environments, while in outdoor spaces it is not ideal.

Chapter 7

Conclusions and perspectives

Conclusions

The inability of GPS receivers to function adequately in indoor environments has launched an ongoing search for new techniques of indoor localization that can provide seamless and ubiquitous service for mobile users. Indeed, accurately and reliably locating mobile users and objects in indoor environments is an attractive and challenging goal that holds promise for many location based services and applications.

A wide variety of solutions have been proposed in the literature, the great majority involving measuring physical quantities associated to radio networks of various kinds, independently, or in combination with inertial sensors in hybrid schemes. Most, however, require the deployment and maintenance of a specific radio network infrastructure, which is costly and time consuming.

The common logic has tended to say that cellular radiotelephony networks would be somehow less useful for indoor localization, perhaps due to discouraging results obtained in some early studies. This thesis was undertaken to capitalize on more recent work exploiting RSS measurements from the GSM standard in order to investigate the possibility of creating a genuinely useful, accurate, and reliable indoor localization system based on radiotelephony signals. Indeed the ability to measuring RSS rapidly is a primordial task in any mobile cellular device, and consequently the focus of this work has been on exploring the possibility of installing such an indoor localization system on a standard mobile device, such as a smartphone or tablet.

Although raw RSS values are noisy, methods to prevent performance decreases engendered by these fluctuations have been demonstrated, as well as a technique to improve accuracy and enhance reliability by combining RSS with information from inertial and other types of sensors common in mobile devices today, as well as map layout information of the site under study.

Chapter 7. Conclusions and perspectives

The characteristics of GSM signals were first examined, outlining the location-dependent and time varying properties of GSM RSS. In general, RSS are quite stable in certain locations but with fluctuations in di erent time scales. RSS from a single GSM carrier, either a beacon channel or a non-beacon channel, does not reveal much location distinction. However, a whole set of RSS from a number of GSM channels, known as a GSM fingerprint, indicates location-dependent attribute that the fingerprint distance is quite related to the geometric distance between di erent locations.

In complex indoor environments, a valid GSM signal propagation model is di cult to obtain, as RSS is the e ect of superimposition of signals from multiple paths with rapidly varying phases. In the initial e ort to seek a functional relationship between RSS fingerprint and coordinate position using regression techniques, no such relationship could be discovered, implying that location interpolation schemes based on RSS measurements at a small number of points are probably not useful.

From there, the study embarked on associating high dimensionality cellular telephone network RSS fingerprints to distinct spatial regions. The indoor localization problem, in this work, was considered as a classification problem, where spatial regions are discriminated by classifying the RSS fingerprints taken from these regions. Based on the building structure, the room is defined as the minimum location unit and data was collected using a standard cellular handset while randomly moving in each room at normal walking speed, with fingerprint scanning performed at a large number of points over the entire room rather than at only a few representative points.

A localization model, consisting of a group of binary SVM classifiers and a multiclass decision rule, is constructed o ine based on the fingerprint examples, which will be used to determine the room number of an online collected test example. When tested under realistic conditions in seven rooms of an o ce building, experimental results demonstrated that out of a total of 17500 test fingerprints, the correct room number was obtained 94% of the time, with only some minor di culties in distinguishing adjacent rooms.

A formidable challenge for the two-stage (o ine training and online testing) fingerprinting techniques is the severe, performance-degrading fluctuations to which radiotelephony RSS values are susceptible. Since frequently rebuilding the localization model is time and labor consuming, the thesis attempted to apply semi-supervised learning to update the localization model with unlabeled fingerprints. Tested on data sets collected over 6 months, this approach, though capable to restore a significant part of the lost performance, is still a trade-o between performance decrease and cost of total retraining.

Conclusions

A better solution was discovered by examining the time-varying characteristic of GSM RSS, which fluctuate on di erent time scales. As a result, when fingerprint examples were taken in a more general way that spread examples over a long time rather than concentrating in a short time period, the performance of the indoor room-level localization system remained stable over a period of months.

Obtained localization accuracy can be improved by taking into account a priori information and other location sources. Considering room-level indoor localization, the physical indoor space can be abstracted into a topological structure, in which a target moves from one room to another room via feasible paths with finite velocity. Bayesian filtering was applied to employ the information about indoor environment and mobile's trajectory, which, in tests on datasets recorded in di erent scenarios, was able to correct most of the localization errors made by the room classifier.

In parallel we remarked that mobile sensors such as accelerometer, gyroscope and magnetic field are increasingly popular for smart phones, which provide additional location sources such as detecting steps, determining moving orientations, etc. Mobile sensor dead-reckoning alone, of course, is not a reliable indoor localization approach, as it necessitates a known starting position and accumulates errors from the sensor measurements over time. The thesis investigated combining room-level classification results with sensor dead-reckoning using a particle filter, which estimates the mobile location based on the sensor dead-reckoning, while obtaining the starting position and correcting localization errors based on GSM room classification results coupled with map constraints. Results showed that without additional deployment of beacons, reliable and accurate indoor localization can indeed be achieved. This is the principle new result of this thesis, that is, to demonstrate that the so-called "common logic" about cellphone signals is incorrect: radiotelephony RSS measurements are indeed a rich and promising source of indoor location-dependent information, which can be coupled with onboard sensors found in mobile devices in ways similar to those used in the more frequently seen WiFi or Bluetooth based indoor localization solutions.

In addition to the main work presented, a study on room-level GSM classification also includes evaluations of the proposed techniques in outdoor and underground environments, carrier selection schemes, and post-processing of support vector classification. As another widely available wireless signal, indoor localization based on WiFi RSS is studied, showing that RSS fingerprinting is still an e ective approach, although it is di cult to model signal propagation in complex indoor

1. 1

 1 Categories of location based services . . . . . . . . . . . . . . . . . . . . . 2.1 Localization based on TOA measurements . . . . . . . . . . . . . . . . . . 2.2 Localization based on TDOA measurements . . . . . . . . . . . . . . . . . 2.3 Localization based on AOA measurements . . . . . . . . . . . . . . . . . . 2.4 Location estimation based on sensor dead-reckoning . . . . . . . . . . . . . 2.5 Categories of the main technologies for indoor localization . . . . . . . . . 3.1 Architecture of a GSM system . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 GSM FDMA channels, TDMA frame and time slots . . . . . . . . . . . . . 3.3 Path loss, shadowing and multipath versus distance . . . . . . . . . . . . . 3.4 RSS measurement devices: a) Telit module and b) TEMS pocket connected to a laptop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Experimental setup for RSS measurements . . . . . . . . . . . . . . . . . . 3.6 RSS in all the carrier frequencies of GSM 900 and GSM 1800 . . . . . . . . 3.7 Received signal strength over time . . . . . . . . . . . . . . . . . . . . . . . 3.8 The coe cient of variation of RSS over time . . . . . . . . . . . . . . . . . 3.9 RSS changes over day and night . . . . . . . . . . . . . . . . . . . . . . . . 3.10 RSS of beacon and non-beacon channels in di erent positions . . . . . . . . 3.11 Experimental setup of testing the fingerprint distance . . . . . . . . . . . . 3.12 Comparison of fingerprint distance and geometric distance. The intraclass distances (blue line) are the average fingerprint distances of each two datasets in the same group; the inter-class distances (red line) are the average fingerprint distances of all datasets in each two groups . . . . . . . 4.1 The overall localization algorithm . . . . . . . . . . . . . . . . . . . . . . . 4.2 An example of SVM classification . . . . . . . . . . . . . . . . . . . . . . . 4.3 One-vs-one classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 One-vs-all classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Layout of the laboratory where the classification datasets were recorded . . 4.6 Classification results as a function of fingerprint size . . . . . . . . . . . . . 4.7 Classification results as a function of training set size . . . . . . . . . . . . 4.8 Performance evolution of SVM classification . . . . . . . . . . . . . . . . . 4.9 RSS in channel 135 and 278 in room 1. . . . . . . . . . . . . . . . . . . . . 4.10 Classification results based on models using di erent training period of time. 4.11 Classification results after removing 20 unstable GSM channels. . . . . . . 4.12 Node and path model abstracted from the experimental site . . . . . . . . 4.13 Target tracking results of trace December 30 . . . . . . . . . . . . . . . . .

[ 2 ]Figure 1 . 1 -

 211 Figure 1.1 -Categories of location based services

  Triangulation is a technique to estimate the target's location based on the geometric properties of triangles, which has two implementations: lateration and angulation. The lateration technique estimates the location of a mobile target by measuring the distances from multiple reference points. The distances can be obtained from measuring quantities like RSS and time-of-flight, which are known to be distance dependent. Quite a number of time-based estimators can be used, including Time Of Arrival (TOA), Time Di erence Of Arrival (TDOA) and Round-Trip Time Of Flight (RTOF), also known as two way ranging. The angulation technique locates an object by computing angles relative to multiple reference points, which is commonly referred to as AOA.

Figure 2 . 1 -

 21 Figure 2.1 -Localization based on TOA measurements

Figure 2

 2 Figure 2.2 -Localization based on TDOA measurements

Figure 2 . 3 -

 23 Figure 2.3 -Localization based on AOA measurements

Figure 2 . 4 -

 24 Figure 2.4 -Location estimation based on sensor dead-reckoning

  Figure 2.5. Since the thesis aims to study indoor localization approaches based on the RF and MEMS sensors, an overview of the localization solutions based on these technologies is emphasized.

Figure 2 . 5 -

 25 Figure 2.5 -Categories of the main technologies for indoor localization

802. 11

 11 IEEE network standard, operating in the 2.4 and 5 GHz Industrial, Scientific and Medical (ISM) radio bands. It is the most popular means of communicating data wirelessly and is widely used for home, enterprise and public hot spots. It currently operates at a data rates of up to 1300 Mbit/s and has a range of approximately 70 meters. With the increasingly deployment of WiFi hot spots in both home and public indoor environments, indoor localization using WiFi infrastructures is being intensively studied.

  is a typical application that extends location services in Apple mobile devices based on the BTLE technology. It uses a proximity technique, which, instead of giving longitude and latitude coordinates, determines if a mobile device is in or out of the range of an iBeacon and monitors the distance as their proximity changes over time. The iBeacon technology is not unique to Apple, however, as all recent Android devices also support such solutions. For instance, the TI SensorTag[START_REF]SensorTag development kit[END_REF] is a generic BTLE product supporting both Apple iBeacon and Android mobile devices. In addition to the solutions based on standard BTLE tags, NOKIA research center[START_REF] Nokia | High accuracy indoor positioning[END_REF] developed a High Accuracy Indoor Positioning (HAIP) technology based on AOA of Bluetooth signals. It uses a modified version of BTLE with custom antennas to enable cost e cient and highly accurate indoor positioning, achieving 0.5 meter positioning accuracy.

  The reader contains a transceiver to transmit RF signals and read the data emitted from the tags. The tags present in the environment reflect the signal, modulating it by adding a unique identification code. The tags can be passive, drawing energy from the incoming radio signal, or it can be powered by a battery. RFID systems operate in four frequency bands: Low Frequency (LF) (125 kHz), High Frequency (HF) (13.56 MHz), Ultra-High Frequency (UHF) (433, 868-915 MHz), and microwave frequency (2.45 GHz, 5.8 GHz). As RFID can detect and recognize nearby tagged objects, it can be used for localization and tracking.

(

  RSS); the Network and Switching Subsystem (NSS); and the Operation and Support Subsystem (OSS), as illustrated in Figure3.1. Each subsystem is an entity composed of one or more pieces of physical equipment to carry out a specific task. The connection between the BSS and the NSS is through the A interface (solid lines) and the connection to the OSS through the O interface (dashed lines).The RSS controls the radio part of GSM network, including the radio specific elements including the Mobile Stations (MS), the BTS and the Base Station Controller (BSC). A MS is comprised of the mobile device or terminal and its Subscriber Identity Module (SIM). A BTS, which contains the signal processing modules, antennas, amplifiers, etc., necessary for radio transmissions, serves users within its radio cell, the basic subunit of a cellular network. The cellular structure allows for frequency reuse in non-overlapped cells, which increases considerably the capacity of the cellular system. Normally several BTSs are controlled by a single BSC. The size of GSM cells can vary considerably in radius, from 100 m to 35 km.

Figure 3 . 1 -

 31 Figure 3.1 -Architecture of a GSM system

Figure 3 .

 3 Figure 3.2 -GSM FDMA channels, TDMA frame and time slots

Figure 3 . 3 -

 33 Figure 3.3 -Path loss, shadowing and multipath versus distance

Figure 3 . 3 .

 33 Figure 3.3.The transmitted signal attenuates with distance since the energy is spread in the space around the transmitting antenna. This e ect is named the path loss, which can be represented by the common LDPL model:

Figure 3 . 4 -

 34 Figure 3.4 -RSS measurement devices: a) Telit module and b) TEMS pocket connected to a laptop

  concrete and plaster walls) in central Paris, France. In the experiments, eight identical Telit modules with nominally identical specifications and technical parameters were used. During data collection, the Telit modules were placed at fixed positions, in a line, spaced at an interval of 0.6 meter, as illustrated in Figure3.5. Around 700 GSM scans for each module were recorded over 5 working days. Each scan contains the RSS of all 548 carriers in the GSM 900 and GSM 1800 bands, and consists of RSS values ranging in value from ≠108 dBm to ≠40 dBm. Since there are gaps of ARFCN between GSM 900 and GSM 1800 bands, in this thesis the carriers are numbered from 0 to 548, which we call carrier index, in which 1-125 corresponds to the ARFCN 0-124 of GSM 900, 126-500 corresponds to ARFCN 512-885 of GSM 1800 and 501-548 corresponds to ARFCN 975-1023 of GSM 900.

Figure 3 .Figure 3 . 5 -

 335 Figure 3.6 shows one scan of RSS over all carrier frequencies recorded by the first Telit module, with the red star indicating the beacon carriers, where we recall that the Telit modules automatically decode BSIC information. It should be noted that the absence of a valid BSICdoes not necessarily mean that a given carrier is a tra c channel rather than a beacon. The BSIC decoding of a genuine beacon can in some cases fail. A common example is when a beacon resides in the channel adjacent in frequency to the carrier currently being scanned. It is seen in

Figure 3 .

 3 Figure 3.7 shows the evolution of RSS recorded by the same Telit module as in Figure 3.6 over five days. As is shown in the figure, the fluctuation of RSS is not severe over a duration of five days, in both beacon and non-beacon channels. The Coe cient of Variation (CV) of RSS is illustrated in Figure 3.8, which, analogously to Signal-to-Noise Ratio (SNR), presents the ratio between standard deviation of RSS and the mean value of RSS over time. It is seen that the largest value of CV is 0.16, but values of CV in most of the carriers are below 0.05. Thus for an RSS in one channel of ≠80 dBm, the standard deviation remains below 4 dB, which is relatively stable.

Figure 3 . 8 -Figure 3 . 10 -

 38310 Figure 3.8 -The coe cient of variation of RSS over time

3. 3 .Figure 3 . 11 -

 3311 Figure 3.11 -Experimental setup of testing the fingerprint distance

Figure 4 .

 4 Figure 4.1 depicts the complete location estimation algorithm, which consists of an o ine training phase, an online localization phase and a post-processing phase. As the fingerprinting approach introduced in section 2.2.3, an o ine training is first performed, involving region labeling of the site, RSS data acquisition, and training and validation to develop a localization model. The

Chapter 4 .

 4 Indoor localization using GSM fingerprints

Figure 4 . 1 -

 41 Figure 4.1 -The overall localization algorithm

Figure 4 .

 4 Figure 4.2 is an example of an SVM classifier with two classes in a two-dimensional descriptor space, where the squares are examples of class A, and circles are examples of class B. Squares and circles in red outline indicate the support vectors.

Chapter 4 .

 4 Indoor localization using GSM fingerprints

Figure 4 .

 4 Figure 4.2 -An example of SVM classification

Figure 4 . 3 -

 43 Figure 4.3 -One-vs-one classification

Figure 4 .

 4 Figure 4.3 illustrates the architecture associated with this method.

Figure 4 .

 4 4 illustrates the procedure. Once the n classifiers are trained, the following decision rule is applied: the outputs of all n classifiers are first computed and, following the conventional procedure, the predicted class is taken to be that of the classifier with the largest magnitude of f (x) (relation (4.7) or (4.8)). The one-vs-all technique is advantageous 4.3. Room-level indoor localization

Figure 4 . 5 -

 45 Figure 4.5 -Layout of the laboratory where the classification datasets were recorded

  performance of each classifier is presented as the percentage of correctly classified test examples. In the dataset, in each room, the first 3000 examples are used o ine for training the classifiers 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 Chapter 4. Indoor localization using GSM fingerprints f (x) from relations (4.7) or (4.8), which is very fast. Experimental results are shown in Table 4.2. 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 k-NN and 1-NN (k = 1 for k-NN) classifiers are also given for comparison.

Figure 4 .

 4 [START_REF]Strategy Analytics[END_REF] we show how the accuracy improves with fingerprint size, for the linear one-vs-all algorithm, by increasing the number of carriers in steps of 50, according to the ordered sequence numbers of the GSM carriers.In figure4.7 we examine the e ect 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. Table 4.3 presents the confusion matrix for the case of the linear one-vs-one algorithm, showing how the mis-classified examples are distributed. It can be seen that most confusions occur between adjacent rooms, as could be expected. Rooms located on opposite sides of the corridor are easily discriminated.

  3.2.1, 22, 56, and 148 days respectively after that dataset. These three datasets, together with the dataset introduced in 4.3.2.1 are hereafter named S1 (5500 scans in each room), S2 (2000 scans in each room), S3 (1000 scans in each room) and S4 (1000 scans in each room). The evolution of performance was examined using these four datasets, which are shown in Figure 4.8. It can be seen in the figure, the performance has a sharp decline after the localization model is built. Compared with testing the "fresh" data that more than 94% of the test examples can be correctly labeled, after 22 days, the performance decrease to 60%. Only 40% of the test examples recorded after about two months can be correctly classified. This is the biggest challenge for fingerprinting based GSM indoor localization, since the localization model decays quite fast. In addition, such performance degradation problem were not taken into consideration by previous work on GSM indoor localization.

Figure 4 .

 4 [START_REF] Oussar | Indoor localization based on cellular telephony RSSI fingerprints containing very large numbers of carriers[END_REF] shows the sudden shifts of RSS of two GSM channels (carrier index 135 and 278), which were probably caused by an update or upgrade of local base stations. This unpredictable performance decrease is a common problem of all fingerprinting techniques. However, it largely influences the prospects of fingerprinting based localization 4.3. Room-level indoor localization

Figure 4 . 8 -

 48 Figure 4.8 -Performance evolution of SVM classification

TSVM overcome in part

  the performance decrease due to RSS drift by taking some unlabeled data and re-training the model. However, this is a remedial action, which still necessitates time and labor consuming sample measurement and model training with limited success. As for the data-driven classification problems, it is not necessary the more samples for training the better performance can be achieved. If most of the fingerprint examples are identically duplicate, the performance of localization system based on such training samples will not improve. Furthermore, a model constructed based on a large number of training samples can be quite e ective for the "current" test examples, but it is not tolerant for the RSS changes over time. As a result, to make the localization model robust over time, it is necessary to collect training examples in a more representative way that incorporating as much as possible of the RSS fluctuations.

Figure 4 .

 4 10, where we present the percentage of correctly classified test examples as a function of time for di erent sizes of the training set (one day, two days and eight days for training respectively). The classifier used was a set of linear one-vs-all SVM with regularization constant C = 0.01. It can be seen that the larger the training data set, the better the results obtained. When the localization model is trained using a dataset in only one day, the correct classification rates afterward are around 50%. In contrast,

Figure 4 .

 4 Figure 4.10 also shows that after about fifty days, two sharp decreases in classification accuracy occurred in our experiments. These can be traced back to significant RSS shifts of some GSM channels as discussed in section 4.3.2.3, where sudden shifts of RSS of two GSM channels (carrier index 135 and 278) were observed. Such shifts are quite simple to detect, which suggests a simple scheme, such as a fixed RSS monitoring installation, which could be introduced to render performance robust against such changes. Figure4.11 shows the results of retraining the models

Figure 4 .Figure 4 . 10 -

 4410 Figure 4.10 -Classification results based on models using di erent training period of time.

Figure 4 . 11 -

 411 Figure 4.11 -Classification results after removing 20 unstable GSM channels.

  )

Figure 4 . 12 -

 412 Figure 4.12 -Node and path model abstracted from the experimental site

19

 19

  )

4. 4 .

 4 Bayesian filter post-processing 4.4.4 Evaluation of Bayesian filtering post-processing 4.4.4.

  .5, where the raw results of SVM classification are compared with the results obtained after Bayesian filtering. The classification model used here was trained on datasets obtained within the first two days of the "time sampling" experiments (section 4.3.4.2), i.e. the triangle line in Figure 4.10. The results presented only consider test examples actually recorded within rooms. In the actual traces, some fingerprints were in fact acquired in the corridor, and thus were not taken into account, since the SVM only classifies the 7 rooms. The results obtained from SVM classification without Bayesian filtering are similar to those presented on Figure 4.10 in the same conditions (training period of two days). It is clearthat Bayesian filtering provides a substantial improvement over raw classification results, even though the classifier is optimally trained using a large dataset. In addition, the results are stable over time.

Figure 4 . 13 -

 413 Figure 4.13 -Target tracking results of trace December 30

Figure 4 .

 4 Figure 4.13 presents the results on one test trace (December 30), showing the real position, SVM classification results and Bayesian filtering results. Locations 1 to 7 correspond to rooms 1 to 7, while location 8 to 10 are the sections of the corridor illustrated in Figure 4.12. The Bayesian filtering method correctly tracked the moving target, except for a few mistakes in the corridor.

  Figure 5.1.

Figure 5 . 1 -

 51 Figure 5.1 -Coordinate definition of the Google Nexus 7 tablet

Figure 5 . 3 .

 53 Figure 5.3.

Figure 5 . 2 -Figure 5 . 3 -Figure 5 . 4 -

 525354 Figure 5.2 -The accelerometer readings

Figure 5 . 5 -

 55 Figure 5.5 -The magnetic field sensor readings

5 . 1 ) 3 .Figure 5 . 6 - 4 .

 513564 Figure 5.6 -Step determination using acceleration amplitude

Figure 5 . 7 -

 57 Figure 5.7 -Stride length with step frequency and acceleration amplitude

Figure 5 . 8 -

 58 Figure 5.8 -Complementary filter for orientation estimate

Chapter 5 .Figure 5 . 9 -

 559 Figure 5.9 -Acceleration changes reflect mobile device position changes

3 . 4 .

 34 Update the weights based on observation model: When SVM classifier result is received, the likelihood p(h t |s t ) is applied to each particle to update the weight. Resample particles based on their weights: Through previous steps, the number of particles reduces and the weights of particles diminishes and the weights of the particles change considerably. To better represent the posterior density p(s t |h t ), particles are resampled to the same number N with probabilities equal to their weights.The final location estimate is taken to be the centroid of all particles.

Figure 5 . 10 - 4 Evaluation 5 . 4 . 1

 5104541 Figure 5.10 -Elimination of particles based on map layout

Figure 5 .

 5 Figure 5.11 -Experimental site

Figure 5 . 13 -Figure 5 . 15 -

 513515 Figure 5.13 -Results of sensor dead-reckoning and a particle filter that only combines sensor dead-reckoning and map layout constraints (case 1)

6. 2 .Figure 6 . 1 -

 261 Figure 6.1 -The outdoor experimental site

Figure 6 .

 6 Figure 6.2 -The underground experimental site and the location cell definition

6. 2 .Figure 6 . 3 -

 263 Figure 6.3 -Experimental results of underground demo trace

  construction. Since a GSM fingerprint contains RSS from a large number of carriers and the GSM fingerprint examples are relatively limited, a carrier selection technique can be tried to exclude redundant or less relevant carriers. One might also expect to reduce the training time and avoid overfitting by applying carrier selection. In this work, two carrier selection schemes were evaluated: Gram-Schmidt feature selection, and recursive feature elimination (RFE).

Figure 6 . 5 -

 65 Figure 6.5 -Post-processing results with di erent sizes of window

6. 3 .

 3 Figure 6.7 -Post-processing result after rejection as a function of rejection rate

Figure 6 . 8 -

 68 Figure 6.8 -WiFi access point and data acquisition positions

6. 3 .Figure 6 . 9 -

 369 Figure 6.9 -WiFi data acquisition program interfaces

Figure 6 .

 6 Figure 6.10 shows RSS from AP2 in two di erent positions (P1 and P2 in Figure 6.8) over ten minutes. The distances from the AP to the two positions are 20 meters and 25 meters respectively.

Figure 6 .

 6 Figure 6.10 -WiFi RSS with di erent distances to the access point

Chapter 6 .

 6 Figure 6.14 -The piecewise model construction between distance and RSS

  RF is the most widely used technologies for indoor localization, including broadcast Wide

	2.3. The technologies for localization
	include GPS, cellular networks, TV and FM radio signals, while WiFi, Bluetooth, WSN and UWB
	belong to the WPAN family.
	Area Networks (WAN), Wireless Personal Area Networks (WPAN), RFID tags, NFC etc. WAN

2.3.1.3 TV and FM radio

	Chapter 2. Indoor localization fundamentals	2.3. The technologies for localization
	random noise delays, which is potentially inadequate to distinguish large amount of locations. with standard deviation of 2.6 and 8 meters respectively, and in two indoor environments, the
	Furthermore, the poor indoor penetration is another challenge for the 3G network UMTS. median accuracies are 10.3 to 23.3 meters with standard deviation of 4.4 and 19.6 meters.
	Though in 3G and 4G networks timing based localization approaches and even dedicated Despite its considerable age, FM radio is still very popular. FM radio networks operate in the
	positioning reference signals are introduced, the localization accuracy is influenced by radio 100 MHz frequency band, with exact range varying from di erent regions. Like GSM systems,
	environment such as signal attenuation and multipath propagation, network topography FM radio uses the FDMA approach, which splits the band into a number of separate frequency
	(density of base stations) and geography, resulting in localization accuracy in some instances channels that are used by di erent radio stations. As a result, RSS fingerprinting technique is
	varying from tens to hundreds of meters [29, 30, 31]. Gentner et al. [50] however proposed an a common practice for FM radio based indoor localization [52, 53, 54], with the mean distance
	indoor localization solution with 3GPP-LTE femtocells, using a particle filter to correct TDOA error found to be 3 to 4 meters.
	measurement errors, and obtaining a median accuracy of 5.35 meters. The result is not The major drawback for TV and FM radio based indoor localization solutions, of course,
	appropriate for a generally practical scenario, since the four femtocells in the experiment are is that special antenna and devices are required, which severely limits the application of this
	hardware-customized and manually placed. A significant problem for indoor localization using
	3G and 4G networks, though, lies in the fact that 3G and 4G networks operate in relatively high
	frequency bands, and thus they have poor indoor penetration. While this thesis was in progress,
	however, 4G adopted the 800 MHz frequency band for the first time, on 29 August 2013, which
	could once again become interesting for indoor localization. It is predicted in [51] that precise
	localization can be harnessed in the coming 5G networks, achieving an accuracy on the order of
	one meter.
	TV and FM radio networks were obviously not originally designed for localization, but they can
	nevertheless be adapted to provide indoor localization services. They are in some ways similar
	to cellular networks, as the signal properties and geometrical arrangement of the TV and FM
	broadcast network have been designed to penetrate well indoors, and they clearly o er greater
	CDMA-based networks, such as the 3G network UMTS, transmit power is controlled in indoor coverage than GPS-based solutions. Implementation of a localization solution would also
	order to accommodate network load, which a ects RSS consistency and therefore limits the require no modification of the existing broadcast signal.
	practicality of traditional fingerprinting approaches based on RSS measurements for such As the TV transmission is becoming digital, synchronization signals are commonly included
	networks. Rehman et al. [49] nonetheless proposed a CDMA indoor localization system, named in TV networks, which can be used for accurate indoor and outdoor localization. Rabinowitz and
	CILoS, which applies fingerprinting technique based on signal delay rather than the RSS. Since Spilker [25] made use of considerable Digital TV infrastructure to achieve reliable and accurate
	CDMA base stations must remain tightly synchronized with each other, fingerprints in CILoS positioning. In order to obtain the precise timing of the TV synchronization signals for accurate
	consist of the relative time di erence at which signals emanating from di erent base stations are location computation, monitor units at known positions are used to independently monitor the
	received at a given location. With the k-NN technique, the location estimation had a median TV station clock o sets, in the cases when the TV transmitters do not broadcast the clock o set
	accuracy of 5 meters. However, the fingerprint in [49] is rather sparse, containing only 6 pseudo information. In the outdoor tests, 3.2 and 12.3 meters median accuracy was obtained in two sites

technique for mobile devices. In addition, with the emergence of Digital Audio Broadcasting as its next generation, FM radio could be replaced worldwide someday, as it has already in some countries.

  Chapter 2. Indoor localization fundamentals is relatively easy to obtain RSS with standard mobile devices, since this ability is typically needed for the routine functioning of such devices. Conversely, accurate time and angle measurements are not easy to obtain, which increases the complexity of a localization system.

	If a certain
	technology is already to a great extent present, with an existing infrastructure and a panoply of
	available mobile devices, it becomes simple to deploy and use. Cellular networks, WiFi and
	Bluetooth, for example, are generic wireless technologies, and most mobile devices support at

least one of them. In contrast, such technologies as UWB and ultrasound are not supported in standard mobile devices. If a localization system is to use UWB or ultrasound, most likely it is a dedicated system requiring proprietary equipment. Regarding the chosen measured quantity, it

  Chapter 3. Characteristics of GSM signals regard for the amount of voice tra c they would ultimately need to carry. As the subscriber base grew, these networks could no longer cope with the increasing tra c. The analog systems furthermore lacked reliability and adequate security measures.Moreover, each country developed its own system, in most cases incompatible with the equipment and operational methods used in other countries.To address these issues, the European Conference of Posts and Telecommunications Administrations (CEPT) established the Groupe Special Mobile to study and develop a digital public land mobile system for Europe. The system was expected to be compatible with Integrated Services Digital Network (ISDN), have good subjective speech quality, low terminal and service cost, e cient use of radio spectrum, and support international roaming. The new

	During the early 1980s, analog modulation telephone systems experienced rapid growth,

including AMPS in the United States, TACS in the United Kindom, C-Netz in Germany, Radiocom 2000 in France, and NMT in Scandinavia

[START_REF] Chen | Next generation wireless systems and networks[END_REF]

. These networks were planned to achieve maximum coverage with as few antennas as possible, but unfortunately insu cient digital standards were completed in the late 1980s, and deployment of GSM networks in Europe began in the early 1990s. Although initially standardized in Europe, GSM today has been is adopted and deployed worldwide. Now known as Global System for Mobile Communications, GSM is at present the most widely deployed cellular telephony standard in the world, with networks deployed in more than 220 countries by nearly 800 mobile operators

[START_REF]GSM roaming and coverage maps[END_REF]

.

Table 3 .

 3 1 -Frequency Division in 900 MHz and 1800 MHz GSM bands

	Band	ARFCN (n)	Uplink (f UL )	Downlink (f DL )
	GSM 900	0-124 975-1023	890+0.2n 890+0.2(n≠1024)	f	UL (n)+45
	GSM 1800	512-885	1710.2+0.2(n≠512)	f	UL (n)+95

GSM uses a combination of Frequency Division Multiple Access (FDMA) and Time Division

  • • • M ) are parameters whose values are estimated from the examples; y

		i = +1
	if example x 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 whosei are nonzero.

Table 4 .

 4 2 -Percentage of Correct Classification on Test Set

	Classifier	GSM 900	Fingerprint Type GSM 1800 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-All	87.1%	85.0%	94.2%
	RBF 1-vs-1	85.5%	84.6%	93.0%
	RBF 1-vs-All	87.2%	85.7%	94.1%

Table 4 .

 4 3 -Confusion Matrix for 7 Rooms Classification

	Predicted Class	1	2	3	True Class 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%

  Transductive inference is introduced to overcome the problem of performance decrease over time. As time goes on, the localization model may be outdated, because RSS in the same channels may have drifted. Transductive SVM (TSVM) can adjust the discriminant functions by taking some newly collected unlabeled data to update the classifiers.

	problem:	minimize	1 2 Y ||w 2 || ]
		subject to	[

4.3.3.1 Transductive SVM classifier

TSVM take unlabeled new examples into account and adjust the separating surface to separate both training examples and the new unlabeled examples with maximum margin. For a linearly separable data case, the separating surface is obtained by solving the following optimization

  3.2.3, namely S1, S2, S3 and S4. Experimental results are shown in Table 4.4. The performance is presented as the percentage of correctly classified test examples. The first 100 unlabeled examples of each room in S2, S3 and S4 sets were used for TSVM training to adjust the model, the remaining examples were used for testing. For SVM classifiers, we use the model trained on set S1 to test the test data in sets S2, 4.3. Room-level indoor localization S3 and S4. Only linear one-vs-all multi-class scheme was used because this method gave the best performance in section 4.3.2.2.

Table 4 .

 4 4 -Comparison of SVM and TSVM

	Test Set Training Set SVM TSVM
	S1 S2	S1 S1	94.2% 60.4% 78.4% ≠
	S3	S1	39.7% 58.8%
	S4	S1	32.3% 49.6%

Table 4 .

 4 5 -Comparison of SVM Classification and Bayesian Filtering

	Test Dataset	Classification accuracy before Bayesian filtering	Classification accuracy after Bayesian filtering
	Dec 24, 2012	74.3%	98.8%
	Dec 29, 2012	70.6%	99.1%
	Dec 30, 2012	72.4%	99.4%
	Jan 02, 2013	77.1%	99.6%
	Jan 03, 2013	75.9%	98.9%
	Jan 04, 2013	70.0%	98.4%
	Jan 06, 2013	83.2%	99.7%
	Jan 07, 2013	68.3%	97.1%
	Feb 03, 2013	77.7%	99.5%

  ) is determined by, in our system, both multiple sensor information and map layout information. When a step is detected, based on5.3. Particle filter data fusionmultiple sensor dead-reckoning, we have:

	Let s	t = [x	t , y	t , p t , q t , ] T be the state of the system, at time t, where x	t and y	t are the position
	coordinates of the mobile user, and p	t and q	t are the parameters of stride length model explained
	in section 5.2.3. The state transition model can be characterized in terms of a state transition
	density p(s

t |s t≠1 ). The state transition density p(s t |s t≠1

  The observation at time step t in our case is the fingerprint classifier output h t , i.e. the room number. The observation probability P (h t |s t ) describes the probability, given the state s t , that room number h t is obtained from GSM fingerprinting result. As described in section 4.4.3, such probability can be estimated based on the confusion matrix. Since the state s t here is continuous coordinate positions, rather than discrete room labels, equation (4.19) can be modified as:

  1, the discrete form of Bayesian filtering is applied, since the states are discrete variables. However, for the filtering problem discussed here, the states are continuous and infinite, and as a result, the task is to obtain the distribution of state s

	Chapter 5. Combination of GSM fingerprinting and mobile sensors
	2) update:
					p(s	t |h t ) =	p(h t |s p(h t |h t≠1 ) t )	p(s	t |h t≠1 )	(5.14)
	where p(h t |h t≠1 ) is the normalizing constant:
							⁄
				p(h t |h t≠1 ) =			p(h t |s	t ) • p(s	t |h t≠1 )ds	t	(5.15)
									t given
	the observations h t , which is the a-posteriori density of the state p(s	t |h t ). For a system with
	state transition density p(s	t |s	t≠1 ) and observation density p(h t |s	t ), the Bayesian filter recursively
	computing the current posterior density p(s	t |h t ) based on the posterior density of the previous
	state p(s	t≠1 |h t≠1 ) and the most recent observation h t , in two steps: 1) prediction:
						⁄
			p(s	t |h t≠1 ) =	p(s	t |s	t≠1 )p(s	t≠1 |h t≠1 )ds	t≠1	(5.13)

Table 6 .

 6 1 -Datasets of the outdoor experimentExperimental results are shown in Table6.2, where the percentage of correctly classified test

	Time	Location 1 2 3 4 5 6 7
	Nov. 21, AM ◊ ◊ ◊ ◊ ◊ ◊ Nov. 21, PM ◊ ◊ ◊ ◊ ◊ ◊ ◊ Nov. 22, AM ◊ ◊ ◊ ◊ Nov. 22, PM ◊ ◊ ◊ ◊

examples is presented. The SVM classifiers are trained with the same settings as in the indoor room-level classification. It is seen in the table that the performance in the outdoor space are much worse compared to the indoor experiments. SVM classification within the selected three

Table 6

 6

		.2 -Outdoor experimental results
	Training Set	Test Set	Locations	Result
	Nov. 21, AM Nov. 21, PM 1, 2, 3, 4, 5, 6 34.8 %
	Nov. 21 AM Nov. 21 PM	Nov. 22 AM Nov. 22 PM	1, 3, 6	88.1 %
	Nov. 21 PM	Nov. 22 PM	1, 3, 6, 7	56.0 %

Table 6 .

 6 3 -Post-processing results for di erent test datasets a test example into either of the two classes with the output +1 or ≠1. However, in some settings it is favorable to obtain an estimation of the probability of a test example x belonging to either of the two classes, i.e. the probability P (y = +1|x) or P (y = ≠1|x).

	Test Set Training Set SVM Post-processing
	S1	S1	94.2%	99.7%
	S2	S1	60.4%	71.6%
	S3	S1	39.7%	33.4%
	S4	S1	32.3%	30.1%

separates

International Symposium on Wireless Communication Systems

Fast, handset-based GSM fingerprints for indoor localization

IEEE International Instrumentation and Measurement Technology Conference

International Symposium on Wireless Communication Systems

Acknowledgments

projects, for their friendships as well as good advice and collaboration. I would like to thank the China Scholarship Council (CSS) and the ESPCI-ParisTech for

properties, RSS from a single GSM carrier, either beacon channel or non-beacon channel, does not provide much location distinction. However, RSS fingerprint, as a set of RSS from all the GSM carriers, has shown to be location dependent, which indicates indoor localization could be viable based on exploring the high dimensional RSS fingerprints.

Chapter 4. Indoor localization using GSM fingerprints

Evaluation of SVM classification for room-level localization 4.3.2.1 Data acquisition and datasets

For the room-level indoor localization, a user should be localized at the room level regardless of his exact position in a room. As the interpolation and extrapolation of locations using some reference points do not work, a space sampling scheme is proposed. To construct a "radio map" of the indoor environment, one needs to know the distribution of signal strengths in each location area, given that RSS values vary in space over the area. Since the room is used as the smallest location unit, space sampling is performed by collecting a large number of signal strengths in each room. This was done by recording the RSS with the TEMS Pocket held in hand during a "random walk" throughout the accessible space of each room, rather than, for example, using a grid or a set of special representative points. The fast scanning characteristic of TEMS Pocket final location estimations can be inaccurate. Another case is shown in Figure 5.14, where all particles are trapped in a small region based on map layout constraints. (As this thesis was being completed, a similar study appeared in [START_REF] Perttula | Distributed indoor positioning system with inertial measurements and map matching[END_REF] with promising results, albeit necessitating specialized torso-mounted hardware.)

In Figure 5.15, GSM fingerprinting, sensor dead-reckoning and map layout restrictions are combined. In this case, only a few mistakes are made at the beginning, due to the unknown starting position, since the SVM classifier only outputs room-level location, not a precise position.

The advantage of a system combining an absolute but noisy measure, GSM, with precise but local dead-reckoning, and map constraints, is clearly demonstrated.

Summary

Hybrid schemes are promising for indoor localization, which take advantage of di erent types of location sources that are available. In this chapter, a hybrid approach for indoor localization is presented using a particle filter to combine GSM fingerprinting room-level classification, sensor dead-reckoning, and map layout information.

Chapter 5. Combination of GSM fingerprinting and mobile sensors However, we wish to introduce some complementary experiments also carried out in the context of the thesis. This will be the subject of chapter 6.

Work related to the SVM classification

Comparison of carrier selection approaches

The two carrier selection approaches, Gram-Schmidt and RFE, are performed and tested on a dataset. Here the training is done using a relatively small number of fingerprint examples, which does not achieve as good performance as that shown in section 4.3.2.2, but the aim here is to compare the two carrier selection techniques. Figure 6.4 shows the performance with di erent number of carriers selected by the two approaches. As is seen in the figure, neither of the carrier selection approaches improves the performance by selecting a subset of high rank carriers. The performance of the two approaches is similar in general, and increases with the number of carriers.

The results indicates with only 50 carriers the performance is reaching steady and close to the top value obtained using the full carrier, which means there are a lot of redundant and irrelevant carriers providing no more information than the selected features. Removing these carriers will reduce the complexity of SVM classifiers, but could potentially decrease the robustness of the localization system. Since the computation load in the online localization stage is not high, we keep all the carriers in the localization system.

Post-processing

Post-processing involves the procedures that are applied to the raw results of SVM classifiers.

In section 4.4, a Bayesian filtering post-processing was investigated, while some more techniques are studied here.

Low pass filter

The first post-processing technique uses the principle of the low pass filter, which considers several successive SVM outputs to make one decision. Suppose the overall correct classification rate of a binary classifier is P , the probability of giving the correct class number. If N outputs are taken into account, the probability of obtaining a correct location will be

where [ú] is the smallest integer greater than ú, and N is the window size which is the number of fingerprint measurements used for post-processing. technique does not improve the performance but actually decreases it. This is consistent with the experimental results on real fingerprint measurements as shown in Table 6.3. This table compares the post-processing results with the raw SVM results using datasets as described in section 4.3.2.3.

It is seen in the table that for the test dataset S1 and S2, the raw results are 94.2% and 60.4%

respectively. After post-processing, which combines every three raw results into one, test results

for dataset S1 and S2 increase to 99.7% and 71.6% respectively. However, for the test dataset S3

and S4, the raw results are so low that the post-processing process does not improve but decrease the performance.

Probability based rejection

Another post-processing technique involves using the reject option of classification. The rejection here is based on the probabilistic output of SVM classification. A binary SVM classifier

WiFi indoor localization

In this thesis, location fingerprinting is also tested using RSS from WiFi networks. The experiment was done in the same seven rooms as for the GSM indoor localization discussed in The overall correct classification rate obtained is 82%, i.e. in 82% of the time, the correct room number can be obtained with a single WiFi fingerprint sample. This result is not bad considering the localization accuracy is achieved based on the WiFi signals that are not specially deployed.

Except the three AP with known positions, signals from the rest AP appear intermittently. The experiment also tested including additional WiFi beacons, where two wireless USB adapters were set into AP mode and put inside room H418 and room H414. The correct classification rate then improved to 91%. It is reasonable to assume that the presence of further WiFi AP would provide even better spatial discrimination.

The fingerprinting based approach is simple, does not require special hardware and can rely on the existing WiFi infrastructures. However, in many scenarios the number of available WiFi signals is not su cient to provide an acceptable localization accuracy, which in turn would require the deployment of additional WiFi AP. In addition, WiFi RSS is reported to be time varying [START_REF] Zheng | Transferring localization models over time[END_REF],

which leads to the localization performance decrease over time.

Triangulation

Another approach for indoor localization using WiFi RSS is triangulation, the technical fundamentals of which were introduced in section 2.2.2.4. In WiFi triangulation, location is estimated by computing the intersection point of circles with centers at the AP and radius equal to the estimated distances to the mobile target. The key to improve the triangulation performance is to obtain accurate distance estimates between mobile target and the WiFi AP.

Hence, the emphasis here is put not on location estimation algorithms, but on estimating distance from WiFi RSS.

As Figure 6.10 presented above, though they fluctuate significantly, the RSS of AP2 recorded in position P2 are generally lower than those in position P1, due to the position P2 is 5 meters further from the AP than position P1. However, estimating distance from RSS via an attenuation model is a challenge. Figure 6.12 shows the RSS recorded from AP1 in the same two positions Chapter 7. Conclusions and perspectives environments, even if taking account of walls could improve distance estimation from the RSS.

Perspectives

The study has o ered a promising approach to simple but practical indoor localization solution.

However, it also encountered certain limitations, as well as brought to light a number of new ideas, both of which could be addressed in future work.

• Firstly, RSS from all GSM channels, as the indoor localization basis in the thesis, were obtained using specialized network investigation engineering devices (e.g., TEMS Pocket).

The fact is that from a hardware standpoint, these are actually standard mobile phones with just a software modification, hence, any mobile cellular device thus modified should have the capability to obtain fast RSS scans in exactly the same way. This means that if cellphone manufactures can be convinced that GSM-based indoor localization is viable, it should be relatively inexpensive to create new products since they can be based upon existing ones with modified software. This also opens the door to being able to access RSS values in real time, in order to combine them with sensor information and map constraints, which, today, with TEMS products, is not possible. To date, unfortunately, cellphone manufacturers have yet to show a particular interest in opening up cellphone firmware to such developments. In such a case, an alternative could be to develop a system on chip, independent of the onboard cellphone processor, to scan RSS fingerprints, which could be embedded in mobile phones much in the same way the WiFi or Bluetooth modules are today. Either approach would provide the final impetus to extend the results obtained in the present study to a genuinely practical solution for indoor localization.

• Secondly, the RSS based approach benefits from the very large number of GSM carriers, and it has been shown that performance continues to increase as more are added to the fingerprint. Thus, incorporating RSS from other available signals, for instance combining several cellphone networks (including LTE), or cellphone plus WiFi/Bluetooth, FM radio, etc., could improve the localization performance even further.

• Thirdly, as in multipath indoor environments RSS fluctuate considerably, it could be interesting to attempt to improve robustness by including the channel impulse response into the fingerprints, in order to characterizing the multipath environment and use it as an additional variable related to position.

• Finally, although the presented study used a hybrid scheme that combines GSM

Perspectives

fingerprinting and mobile sensor dead-reckoning, hybrid schemes making use of mobile sensors could be explored even further, as the number and variety of sensors incorporated into mobile devices today is constantly growing as these devices become more intelligent and location aware.