RX: Receiver RMSE: Root Mean Square Error RTT: Round Trip Time WLS: Weighted Least Squares DV: Distance Vector APIT: Approximate Point In Triangulation LQI

Keywords: Link Quality Indicator SNR: Signal to Noise Ratio TOF: Time of Flight SQP: Sequential Quadratic Programming method signal frequency. P L: path loss. η: exponent factor Localisation, RSSI, Réseau de capteurs dans fils, Trilatération, Poursuite Localization, RSSI, WSNs, Trilateration, Tracking

v w : velocity of wave in the relevant transmission medium. t: propagation time. (x i , y i ): coordinates of the ith landmark or node. h i : minimum hop count value. Size i : averaged size for one hop. τ : time delay

During the three years, many people have helped me and supported me. I am very grateful for their help, encouragement and support. This work would not have been completed without the support of my supervisors, colleagues, friends, and parents.

First and foremost, I would like to express my utmost gratitude to my supervisor Professor Jean-François Diouris and co-supervisor Professor Yide Wang for their continuous support, patience, and guidance throughout this work. With their help, I have learned how to define research problems and formalize them; how to find solutions and improve them; how to design system and how to write scientific paper. I also want to thank them for their help in my daily life. I feel very lucky and proud to have met them in my life.

I would also like to thank my friends and every colleague in the lab, for their help and tolerance. I had a good time for my PhD life in France.

Furthermore, I would like to thank China Scholarship Council (CSC) for the financial support.

Finally, I would express my appreciation to my parents for their selfless love and support.

List of Abbreviations

Introduction

Recent advances in wireless communications and micro electro-mechanical system (MEMS) technologies have enabled the development of low-cost, low-power and small size wireless sensor nodes. Wireless sensor networks (WSNs) which are composed of a large number of sensor nodes, have become a current hot spot of networking area and have been used for various applications, such as oceanic resource exploration, pollution monitoring, tsunami warnings and mine reconnaissance. For all these applications, it is essential to know the locations of the sensor nodes. Localization algorithms for wireless sensor networks (WSNs) have been designed to find location information of every sensor node, which is a key requirement in many applications of WSNs [1].

In this dissertation, we focus on the indoor localization techniques in the wireless sensor networks (WSNs). Firstly, it is necessary to define the main characteristics of WSNs, including its principles, characteristics and applications. In the second part, we will summarize the localization techniques which can be applied to WSNs, and finally, we will describe the thesis contributions and the structure of the dissertation. 11

Wireless sensor networks

Wireless sensor networks (WSNs) are novel and interdisciplinary research field, closely associated with modern sensor technology, microelectronics and communications technology, embedded computing system and distributed information processing technology [2]. In the following subsections, we will revisit the principles, main characteristics and applications of WSNs. Typically, as illustrated in Figure 1.1, a traditional wireless sensor network consists of the following four parts: sensor nodes, sink node, satellite or wireless communication base station, and remote monitoring center [3]. The sensor nodes are scattered randomly or deployed artificially in the area to be monitored. A wide variety of information in the monitored environment, such as temperature, illumination, soil moisture content, hazardous gases, soil internal pressure and so on, can be perceived by the sensor nodes. Thereafter, the acquired data will be forwarded to the sink node through a single hop or multihop. Consequently, by means of satellite or cellular network, such as GSM/3G/4G communication infrastructure, the sensor data are transmitted to the remote data monitoring center, where the collected data will be processed and analyzed comprehensively.

Principles of WSNs

Inversely, the monitoring center can send the special control message to the bottom nodes in a reverse transmission path.

Development and applications of WSNs

Wireless sensor networks, initiated by American scholars in the 1970s, were soon afterwards applied in the military and civilian fields successfully [4]. In the light of potentially enormous military significance and business benefits, the wireless sensor networks draw great attention all over the world. As a result, many countries funded the research and application on this emerging areas. After entering the twenty-first century, there have been considerable progress in the wireless sensor networks, aided with the developments of the microelectronics and cloud computing technologies. Consequently, WSNs have been introduced into many aspects of social life.

In a taxonomic manner, the utilization of WSNs can be mainly classified into two categories: target tracking and event monitoring [5]. As described in Figure 1.2, target tracking involves object movement tracking, observation of human behavior, animal activity tracking, motion displacement calculation and so on. Similarly, the event monitoring comprises the following points: military situation surveillance, species habit observation, health status monitoring, industrial process control, commercial operation supervision, environmental changes perception etc.

Characteristics and focuses of WSNs

Promoted by the development of microelectronics, embedded systems and telecommunication technologies, WSNs have gained increasing popularity in the humanity lives for numerous applications. For example, sensors nodes can be integrated into a wireless body area network (WBAN), a new enabling technology for health monitoring [START_REF] Otto | System architecture of a wireless body area sensor network for ubiquitous health monitoring[END_REF]. Furthermore, the Internet of things (IOT), which is based on wireless sensor networks, makes it possible to access remote sensor data and to control the physical world from a distance [START_REF] Kopetz | Internet of things[END_REF].

The advance in technology enables miniaturization, low power consumption, low cost, easy deployment and so on. Even if the technology is well developed, some issues related to network topology, routing protocol, energy optimization, localization, clock [START_REF] Ian F Akyildiz | A survey on sensor networks[END_REF][START_REF] Ian F Akyildiz | Wireless sensor networks: a survey[END_REF] are still important research topics.

-Routing. In some application scenarios, the sink and certain nodes can alter its position autonomously or will be moved by external forces from the environment, contributing to the transformation of the network architecture. Simultaneously, routing difficulties appear. Indeed, to fulfill the objectives of reliable data transmission, timeliness of data delivery, sharing the resources fairly, utilizing the energy efficiently, and maximizing the lifetime of network, it is vital to design optimal routing strategy for WSNs. Currently, there are many routing algorithms in the scientific community introduced by the researchers, to name only a few, flooding protocol [START_REF] Paruchuri | Optimal flooding protocol for routing in ad-hoc networks[END_REF], gossip protocol [START_REF] Verma | Controlling gossip protocol infection pattern using adaptive fanout[END_REF], direct diffusion protocol [START_REF] Intanagonwiwat | Directed diffusion: a scalable and robust communication paradigm for sensor networks[END_REF], SPIN [START_REF] Akkaya | A survey on routing protocols for wireless sensor networks[END_REF], GPSR [START_REF] Karp | Gpsr: Greedy perimeter stateless routing for wireless networks[END_REF], LEACH [START_REF] Junping | A time-based cluster-head selection algorithm for leach[END_REF], SAR [START_REF] Sharma | Qos-based routing protocol in wsn[END_REF]. Based on the aforementioned fundamental routing protocols, a multiple types of routing strategies have been presented in the past years. -Clock synchronization. In some time sensitive application, for instance, in forest fire monitoring, a forest fire can be detected by different sensors at different points in time. Sensor readings and timestamps are recorded to find time elapsed since the fire was first spotted and its direction [START_REF] Zhang | Wireless sensor networks time synchronization based on gps[END_REF]. It is essential to maintain rigorous and uniform time schedule in these disaster monitoring applications. Pursue the time synchronization rapidly and accurately is the anticipated direction on this issue. -Security. For most applications, security of datas or communication must be guaranted. In a general way, no network can avoid this problem. In the state of the art of WSNs, hardware protection and software encryption, or the combination of the two methods, are employed. However, there are yet many challenging works to be done on the security. -Localization. In the previous section, we have seen that the localization of nodes is essential for numerous applications. As it is the main subject of our work, this topic will be discussed in detail in the following sections. In summary, there are still many issues in this field, that must be deep investigated and are waiting scholars to further study.

Localization in WSNs

Wireless sensor networks have been applied in many military and civilian applications to monitor environmental change and detect abnormal events [START_REF] Boukerche | Localization systems for wireless sensor networks[END_REF]. Specifically, the node position information is essential to some localization sensitive applications. Determining the positions of sensor nodes precisely is a vital issue as the collected data are closely related with the location information.

Researchers have made much efforts to solve the localization problem by adopting other positioning systems into the WSNs. To sum up, the following means can be employed:

-GPS -Cellular network -Infrared device -Ultrasonic wave -Micro inertial navigation A common feature shared in the above positioning strategies is that extra modules are integrated in sensor nodes, which leads to increase the power consumption and communication overhead but also the deployment cost. To solve this problem, scholars tried to acquire the location without additional devices by using only received signal information which can be available in the radio transceiver used for the communication. This information can be time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA) and received signal strength indicator (RSSI) [START_REF] Anindya | Rssi-based indoor localization and tracking using sigma-point kalman smoothers[END_REF].

The advantages and disadvantages of these methods will be discussed in Chapter 2. The RSSI is the most common information, available in every transceiver. In this thesis, we have worked on solving indoor localization problems by using algorithms based on the RSSI. As the RSSI is not an accurate parameter to determine distances, we have worked on improving the localization accuracy of the proposed algorithms.

Thesis Contribution

In this dissertation, we focus on RSSI based localization algorithms for indoor applications. The main contributions of this thesis involve the following three aspects.

1. Firstly, an experimental localization system has been built to get real RSSI data.

From the measurements, a RSSI channel model has been deduced, which is consistent with the popular lognormal shadowing path loss model. Much more data have been acquired to observe the relationship between the variance of noise and distance. Based on the obtained data, it has been showed that the standard deviation of the noise increases with the distance. To confirm this tendency, a ray tracing system for an environment similar to the experimental environment, has been used to simulate the receive and transmit process of RSSI data.

2. Secondly, we have proposed three novel indoor localization algorithms based on multilateration and averaged RSSI, called Three minimum Distances Method (TDM), Weighted Three minimum distances Method (WTM) and Weight values Adjustment Method (WAM). These algorithms deal with the poor accuracy of the distances deduced from RSSI. Using the experimental channel model deduced from measurements, the performance of the proposed algorithms has been verified and compared in realistic conditions.

3. Finally, a RSSI based parameter tracking strategy for constrained position localization has been proposed. To estimate channel model parameters, Least Mean Squares method (LMS) has been associated with the trilateration method. In the context of applications where the positions are constrained on a grid, a novel tracking strategy has been proposed to determine the real position and obtain the actual parameters in the monitored region. The proposed tracking strategy has also been evaluated using the channel model deduced from the experimentations.

Dissertation structure

The dissertation is composed of 6 Chapters.

In Chapter 2, we introduce the state of the art of localization techniques in WSNs, including the extra modules aided and extra modules free approaches. Some important methods for our work such as linear least squares (LLS), non linear least squares (NLS), projection onto convex sets (POCS) and semidefinite programming (SDP) are particularly detailed.

Chapter 3 deals with channel model which is a fundamental part of RSSI based localization algorithms. An experimental channel model is deduced from RSSI data acquired by a real localization system developed during this PhD work.

In Chapter 4, three localization methods: TDM, WTM and WAM are presented. The accuracy and calculation time of the proposed methods are compared with LLS, NLS and POCS.

The accuracy of the channel model is fundamental for the proposed RSSI based localization algorithms. A parameter tracking strategy is proposed in Chapter 5 which can be applied to applications where the mobile positions are constrained to a grid. Quantitative criteria are provided to guarantee the efficiency of the proposed tracking strategy by providing a tradeoff between the grid resolution and parameter variations.

Finally, the conclusion and future work directions are discussed in Chapter 6.

Conclusion

In this Chapter, we have firstly presented the main principles and applications of WSNs and the induced research topics that remain important in that field. Then we have introduced the problem of localization in WSNs. Finally, we have summarized the main contributions of our work and described structure of the thesis.

The following Chapter is dedicated to the state of the art of localization strategies and particularly to the techniques which can be applied to WSNs.

Localization strategies in WSNs

As mentioned in the previous chapter, for numerous applications of WSN, the localization of the nodes is a fundamental information which must be associated to the sensor measurements. As a bridge between the physical world and the digital world, WSNs are widely used to deal with sensitive information in many fields. Application scenarios of WSNs include military, industrial, household, medical, marine and other fields, especially in natural disasters monitoring, early warning, rescuing and other emergency situations. For example, by a smart dust network, suspended nodes in the air space can detect pressure, temperature and other information of different positions to monitor the quality of the atmosphere. Sensor nodes buried under the bed at different depths can collect temperature, pressure and other data to observe the activity of the glacier [START_REF] Mihaela I Chidean | Scalable data-coupled clustering for large scale wsn[END_REF]. Sensor nodes in birds' nests can help users to further research the living habits of birds [START_REF] Wendi B Heinzelman | An application-specific protocol architecture for wireless microsensor networks[END_REF]. In above mentioned applications, all collected information is based on the accurate location of sensor nodes. Therefore, localization is one of the basic and core technologies in WSNs [START_REF] Theodore S Rappaport | Wireless communications: principles and practice[END_REF].

In this chapter, the localization principle and process are discussed. A classification of localization strategies in WSNs is provided, and some typical approaches are revisited and detailed.

Localization process

The objective of a localization process is to determine the position of an object of interest through a specific system. According to the application specific requirements, appropriate algorithms can be chosen among existing localization techniques.

For applications which require only coarse localization, the position is obtained directly, by determining the proximity to an anchor or by using hop count methods or finger printing [START_REF] Lazos | Serloc: Secure range-independent localization for wireless sensor networks[END_REF]. It should be noticed that coarse localization methods are simple means to provide an initial estimate for a more accurate localization method.

For applications requiring a better accuracy, the localization methods include two steps: distance measurement and position calculation. As illustrated in Figure 2.1, the first block estimates distance or angles of arrival (AOA) from the received signal information: time of arrival (TOA), time difference of arrival (TDOA), received signal strength indication (RSSI) and other available features. The second stage processes the distance and angular information and estimates the position through several positioning methods associated with optimization approaches.

All the relevant measurement techniques mentioned above: TOA, TDOA, DOA, RSSI, and localization algorithms: Triangulation, Trilateration, Multilateration will be described further.

Measurement Techniques

Location Calculation

Signal Information

Measured Distances Angles of Arrival

Localization strategies overview in WSNs

Numerous methods have been proposed for localization in WSNs. From a hardware perspective, the positioning strategies can be divided into two categories: extra modules aided approaches and extra modules free approaches, as illustrated in Figure 2.2.

A detailed explanation of the two strategies will be addressed in the subsequent section.

Extra modules aided approaches

For this class of methods, a specific hardware is dedicated to the localization. This approach includes GPS method, cellular network method, infrared method, ultrasonic wave method, micro inertial navigation method, to name just a few [START_REF] Amundson | A survey on localization for mobile wireless sensor networks[END_REF]. In the following, we will briefly address the above-mentioned localization techniques and discuss the combination of these techniques and WSNs from a practical perspective.

GPS method

The Global Positioning System, abbreviated as GPS, is a satellite based positioning system developed by the American military authorities in the 1970s. In the following four decades, GPS has been widely used in both military and civilian fields for navigation, communications and monitoring. Similarly, the European Union and Russia have build their position systems, named Galileo and Glonass Systems respectively. In recent years, China has establishing the BeiDou Navigation Satellite System for pursuing a higher precision and extensive applications [START_REF] Nabil M Drawil | Gps localization accuracy classification: A context-based approach[END_REF].

In order to accomplish the task of tracking the displacement of a sensor, GPS modules can be integrated into the nodes. However, there exist some drawbacks and limitations in it. In some environments, like underground parking, underwater sites or indoor environments, GPS receiver can not communicate with the satellites [START_REF] Kaplan | Understanding GPS: principles and applications[END_REF]. Consequently, it is unfeasible to use GPS in these environments. Besides, high energy consumption is also a drawback in employing GPS modules. Therefore, using GPS for localization in WSNs has some fundamental limitations, which make us steering to other techniques.

Cellular network method

A cellular network is a communication network where the last link is wireless and used for mobile communication. In that case it is an extra module free method because the cellular modem is also used for communication.

The Global System for Mobile Communication is abbreviated as GSM, is a standard developed by the European Telecommunications Standards Institute (ETSI) to describe the protocols for second-generation digital cellular networks [START_REF] Ellis | Investigation of outbreaks of highly pathogenic h5n1 avian influenza in waterfowl and wild birds in hong kong in late 2002[END_REF]. In the recent years, with the advent of third-generation and fourth-generation (4G) technologies, mobile communications went up to a higher level [START_REF] Varshavsky | Are gsm phones the solution for localization?[END_REF]. In cellular wireless location systems, a plurality of base stations receive signals from a mobile terminal simultaneously, and then the cellular network accomplishes the localization process based on the measured parameters.

In WSNs, the sensor nodes can be equipped with the relevant modules and localized by cellular network . However, there are many limitations and drawbacks in this method. Most importantly, it provides an unsatisfactory localization precision, ranging from the order of tens of meters to hundreds of meters. In addition, the cellular network module is energy consuming, which contradicts the low cost objectives in WSNs. Therefore, there are still many multi-aspects and challenging issues in this direction to be fixed.

Infrared method

Infrared ray is another kind of electromagnetic wave, whose wavelength ranges from the microwave to the visible light wavelength. Due to its thermal effect and highly penetrating ability, infrared ray is extensively used in medical treatment and industrial detection and control. With the advance of microelectronics and optical fiber communication, infrared transducer became a low cost device which can be employed for object detection and vehicle tracking [START_REF] Zamorano | Interactive intraoperative localization using an infrared-based system[END_REF].

When propagating in the space, the infrared ray would undergo deviations like reflection, refraction, scattering, interference and absorption [START_REF] David | Maps of dust infrared emission for use in estimation of reddening and cosmic microwave background radiation foregrounds[END_REF]. Due to these effects, it is nearly impossible to use infrared transducer into WSNs for localization when the environment is complex. On the contrary, the sensor nodes with infrared transducer in WSNs can be used with success for detection. To sum up, the use of infrared technology for localisation in WSNs remains an open issue.

Ultrasonic wave method

Ultrasonic wave is a part of sound waves, whose frequency is beyond 20kHz [START_REF] Joseph | Ultrasonic waves in solid media[END_REF]. Distinctly different from the ordinary sound waves, the ultrasonic wave has the following characteristics: superior directionality, longer transmission range, strong reflectivity and penetrability [START_REF] Silk | The propagation in metal tubing of ultrasonic wave modes equivalent to lamb waves[END_REF]. Due to the above-described features, the ultrasonic wave is introduced successfully into engineering and health-care fields.

The principle of ultrasonic wave based localization can be addressed concisely as follows. The receiver estimates the time of arrival or the difference of time of arrival and measures the propagation time t. The distance between the sender and receiver can be estimated as (2.1):

s = v w t (2.1)
where v w is the velocity of the ultrasonic wave in the relevant transmission medium.

Since the ultrasonic wave suffers from interference and distortion in harsh environment with a variety of obstructions, it is impractical to estimate displacement by means of ultrasonic wave based localization techniques extensively [START_REF] Silk | The propagation in metal tubing of ultrasonic wave modes equivalent to lamb waves[END_REF]. On the contrary, the ultrasonic wave can propagate steadily in the water, which enables the ultrasonic wave based localization techniques to some specific application fields. In the marine environment monitoring, ultrasonic wave based localization technique is considered as an advisable method. Many researchers are trying to integrate ultrasonic module into sensor nodes and exploring the application in marine monitoring and navigation.

Micro inertial navigation method

Mainly based upon the acceleration sensor, direction sensor and gyroscope sensor, micro inertial navigation is identified as an accurate navigation system estimating the movement parameters from the data sensed by the above mentioned devices. A distinct feature is its independent estimation, namely, the localization process uses only internal equipment without the help of outside systems [START_REF] Oliver | An introduction to inertial navigation[END_REF]. This technique is originally employed for missile guidance, and then aircraft and submarine navigation.

To overcome the limitations in GPS system and improve the localization accuracy, the researchers introduced the micro inertial navigation method into WSNs. In the process of movement, the acceleration sensor obtains the acceleration of the node movement and the orientation sensor obtains the node posture instantaneously. After the acceleration data and the direction angles of the node are acquired, the displacement of the node's movement can be calculated through integral calculation. Micro inertial navigation system provides a satisfying accuracy in short term but can exhibit deviation in long period. So, it can be used in addition to other localization systems (GPS or cellular networks) when they become periodically unavailable. Despite that micro inertial navigation can gain a higher precision in short range, a heavy energy consumption is inevitable. Therefore, it is imperative to make a trade-off in practical applications to meet the diverse requirements [START_REF] Bortz | A new mathematical formulation for strapdown inertial navigation[END_REF].

Extra modules free approaches

Compared to the extra modules aided approaches, extra modules free approaches require no additional components to assist the localization process. Namely, rather than supported by external localization systems and internal mounted components, the ex-tra modules free approaches carry out the localization task merely by its own network parameters.

Extra modules free approaches are typically divided into two aspects: range free methods and range based methods [START_REF] Alizadeh | Range-based estimation of stochastic volatility models[END_REF]. Compared to range-free localization, rangebased localization provides higher precision. There are many range-based localization techniques, such as those based on the measurement of TOA [START_REF] Jamalabdollahi | Toa ranging and layer thickness computation in nonhomogeneous media[END_REF][START_REF] Catovic | The cramer-rao bounds of hybrid toa/rss and tdoa/rss location estimation schemes[END_REF], AOA [START_REF] Tomic | 3-d target localization in wireless sensor networks using rss and aoa measurements[END_REF][START_REF] Niculescu | Ad hoc positioning system (aps) using aoa[END_REF], TDOA [START_REF] Velasco | Tdoa matrices: Algebraic properties and their application to robust denoising with missing data[END_REF][START_REF] Cong | Non-line-of-sight error mitigation in tdoa mobile location[END_REF], RSSI [START_REF] Abouzar | Rssi-based distributed self-localization for wireless sensor networks used in precision agriculture[END_REF] and so on.

RSSI-based algorithms have the following characteristics: low power consumption, simple hardware but high sensitivity to environment. RSSI value heavily depends on the propagation channel. Signal reflection, multipath propagation, noise and signal scattering have great influence on the received RSSI. Therefore, in practical applications, establishing an accurate channel model to deduce the distance from the received RSSI value is crucial to the performance of localization algorithms.

An in depth explanation for the two types of methods will be addressed in the following section.

Range free methods

Contrary to range-based algorithms, range-free algorithms accomplish localization through network and devices features, such as network connectivity graph, device power consumption and conservation, geometric relationship and many more, instead of ranging the distance between target and anchor nodes. In the sequel, several classical localization algorithms: distance vector hop (DV hop) [START_REF] Sakiyama | Kineosporia babensis sp. nov., isolated from plant litter in vietnam[END_REF], approximate point-in-triangulation test (APIT) [START_REF] Butzke | Cloning and biochemical characterization of apit, a new l-amino acid oxidase from aplysia punctata[END_REF] and centroid algorithm [START_REF] Chen | Fringe order identification in optical fibre white-light interferometry using centroid algorithm method[END_REF], will be revisited.

DV hop

Inspired by the classical distance vector routing scheme, DV-Hop algorithm is proposed in [START_REF] Niculescu | Ad hoc positioning system (aps)[END_REF]. It involves three steps in the localization process as follows:

1. In the initial step, an information table is built for each node according to the landmark broadcast location and hop data. The data package is exchanged between node and its neighbors. The table is denoted as (x i , y i , h i ), where (x i , y i ) is the coordinates of the ith landmark and h i is the minimum hop count value from the ith landmark to the target node who maintains this table.

Figure 2.3: Error analysis on DV hop count measurement 2. Secondly, the averaged size for one hop is estimated based on the distance calculated between a landmark and other landmarks. The averaged size is estimated by:

Size i = (x i -x j ) 2 + (y i -y j ) 2 h i , i = j (2.2)
where (x j , y j ) is the position of landmark j. In this step, the target node calculates the distance based on the hop size value and the hop count number from at least three landmarks.

3. Finally, when the distance values are obtained, the relevant positioning method, such as mutilateration, trilateration, linear least squares (LLS), non-linear least squares (NLS) and so on [START_REF] Rigazio | An optimal bhattacharyya centroid algorithm for gaussian clustering with applications in automatic speech recognition[END_REF], can be employed to find the position.

As shown in Figure 2.3, the dotted line denotes the actual distance between two nodes, and the solid line indicates the hop direction and estimated distance by DV hop algorithm. Obviously, the DV-hop algorithm provides a low accuracy due to the imprecise distance estimation.

A high density nodes deployment can provide a better accuracy. However, owing to its simplicity, this method can be applied into some rough localization.

APIT

APIT is a range free localization algorithm, presented in [START_REF] He | Range-free localization and its impact on large scale sensor networks[END_REF]. The core idea of this method is to associate Point-In-Triangulation Test (PIT) with area-based scheme to search the most likely target position. PIT is adopted for narrowing the possible region where the target is located. We assume that many anchor nodes, whose location is known by other means, are scattered in a wireless sensor networks. As illustrated in Figure 2.4, in every trial, three anchors are selected to form a triangle and whether the position of the target is in this triangle or not is decided. This process is repeated until all the triangles are considered. After finishing all the tests, the center point of intersection area will be regarded as the estimated position. The localization accuracy of APIT depends on the test number which is directly related with the anchor number. Unavoidably, the power and time consumptions increase with number of anchors [START_REF] Tan | Research and implementation of apit positioning algorithm in wsn[END_REF].

Centroid algorithm

Centroid localization algorithms estimate the position via geometric relationship between the landmarks and the unknown nodes, instead of calculating the corresponding distance. These algorithms are suitable for the wireless sensor networks with a certain number of landmarks whose positions are recognized by other complementary schemes. Periodical packets containing position information are broadcasted among the networks. When the number of received packets exceed a predefined threshold value, a stable transmission link is established between a node and a landmark. An unknown node will be connected with many landmarks. Assuming that the number of landmarks is more than 3, a polygon is formed by these landmarks. Then, the centroid position is considered as the unknown node location.

As illustrated in Figure 2.5, scholars presented centroid localization algorithm based on tetrahedron. A tetrahedron is limited by four anchor nodes L1, L2, L3, L4, which are connected with the target to be localized. Then, the centroid of this tetrahedron is considered as the coordinates of the target. In [START_REF] Bulusu | Gps-less low-cost outdoor localization for very small devices[END_REF], simulations were performed to compare this method and the classical centroid algorithm. The results indicate that the tetrahedron algorithm gives a higher accuracy than the traditional method in spite that larger calculation time is required due to many estimation rounds. Other researchers in [START_REF] Chen | Novel centroid localization algorithm for three-dimensional wireless sensor networks[END_REF][START_REF] Blumenthal | Weighted centroid localization in zigbee-based sensor networks[END_REF][START_REF] Pivato | Accuracy of rss-based centroid localization algorithms in an indoor environment[END_REF][START_REF] Zhu | An improved centroid localization algorithm for wireless sensor network[END_REF] tried to improve the centroid algorithm by assigning weighted factors to each anchors or associating correction schemes to reduce the localization error.

Range based methods

Contrary to the previous methods, range based methods perform position computation after distance estimation. These methods involves two stages: distance measurement and position calculation.

Many techniques have been employed for distance measurement, for example, the techniques based on time of arrival (TOA), time difference of arrival (TDOA), angle of arrival (AOA) and received signal strength indicator (RSSI) [START_REF] Han | Localization algorithms of wireless sensor networks: a survey[END_REF]. After acquiring the distance measurement, geometric relationship is used to compute the node position by triangulation, multilateration, trilateration, hyperbolic and so on.

In the next section, these techniques are discussed in detail.

1 L 2 L 3 L 4 L M O D

Distance measurement techniques

Firstly, we will present the methods that can be used for the distance measurement step. These methods are based on the measurement of the angle or distance, including TOA, TDOA, RSSI and AOA.

TOA

In TOA and TDOA methods, the distance is ranged from the transmission time between the transmitter and the receiver [START_REF] James | A new approach to the geometry of toa location[END_REF]. The time of flight (TOF) recorded between two terminals can be is used to estimate the distance by a simple multiplication by the transmitting velocity. The schemes for measuring elapsed time are classified into two categories: one-way scheme and two-way scheme.

In one-way scheme, the transmitter sends signal to the receiver and the time delay

CHAPTER 2. LOCALIZATION STRATEGIES IN WSNS

for this transmission is measured. The transmitter sends message at time t 1 and the receiver gets the message at time t 2 . Then a decoding delay or synchronization time t c is required to accomplish the time record. Therefore, the time delay τ can be written:

τ = (t 2 + t c ) -t 1 (2.
3)

The one-way scheme is simpler, but it is essential to synchronize the two terminal clocks to reduce the errors. High accurate clock synchronization is a challenging task and clock bias results in measurement errors. This remark explains why two-way scheme is generally privileged.

In two-way scheme, the transmission time between two nodes is measured. The distance is one-half of the measured time multiplied by the propagation velocity. The timing process of the two-way scheme is shown in The sender sends message to the responder at time t s1 . The responder receives the message at time t r1 . After knowing the processing time T r , the responder gives a feedback at time t r2 which is received by the sender at time t s2 . A clock bias ∆t exists between the sender and responder of two nodes. The propagation time is denoted as T p [START_REF] Guvenc | A survey on toa based wireless localization and nlos mitigation techniques[END_REF]. From the Figure 2.6 we can write:

t r1 = t s1 + T p + ∆t (2.4) t r2 = t r1 + T r (2.5) Finally, t s2 = t r2 + T p -∆t (2.6)
Then by subtracting t s2 and t s1 , we get the result

t s2 -t s1 = 2T p + T r . (2.7)
Then time T p can be calculated by

T p = t s2 -t s1 -T r 2 . (2.8)
As shown in the previous equation, the clock bias ∆t is eliminated by this process.

In two-way scheme, the transmission time is obtained by recording packet receiving and sending times. In spite that this two-way scheme does not need clock synchronization, inaccurate packet processing time in terminals results in measurement errors.

An alternative method called TDOA is proposed to measure time difference between two propagation processes [START_REF] Venkatraman | A novel toa location algorithm using los range estimation for nlos environments[END_REF]. A typical TDOA system will be discussed in detail in the following.

TDOA

The key concept of TDOA-based localization technique is to determine the location of the source by evaluating the difference in arrival time of the signal at spatially separated base stations [START_REF] Van De Beek | Ml estimation of time and frequency offset in ofdm systems[END_REF]. As shown in Figure 2.7, there are three signal receivers: RX1, RX2, and RX3, whose coordinates are known as (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ). The objective is to determine the position of the transmitter with unknown coordinates (x, y). The reception times in RX1, RX2 and RX3 are respectively t 1 , t 2 and t 3 . This values can be combined to obtain the following equation [START_REF] Paul | Emitter location accuracy using tdoa and differential doppler[END_REF]:

(x -x 2 ) 2 + (y -y 2 ) 2 -(x -x 1 ) 2 + (y -y 1 ) 2 = c × (t 2 -t 1 ) (x -x 3 ) 2 + (y -y 3 ) 2 -(x -x 1 ) 2 + (y -y 1 ) 2 = c × (t 3 -t 1 ) (2.9)
where c is the speed of light. By solving the above nonlinear equations, the position of TX can be determined.

RX2 TX RX1 RX3 (𝑥 1 , 𝑦 1 ) (𝑥 2 , 𝑦 2 ) (𝑥 3 , 𝑦 3 ) 𝑡 1 𝑡 2 𝑡 3 Figure 2.7: Terminals deployment of TDOA method
The main drawback of the TDOA technique is that the reception time difference can be fairly small, especially in short distance measurement, and the distance estimation is not precise [START_REF] Yamasaki | Tdoa location system for ieee 802.11 b wlan[END_REF]. To overcome this problem, the electromagnetic waves can be replaced by acoustic waves. The propagation velocity is much smaller and thus the time differences are largely increased.

As seen in Figure 2.8, ultrasound/acoustic and RF modules are simultaneously used in transmitter and receiver. The principle is to measure the time difference between the propagation times of the acoustic and radio signals [START_REF] Ho | Bias reduction for an explicit solution of source localization using tdoa[END_REF].

In the initial localization step, the transmitter sends at time t 0 the radio signal which is received by the receiver at time t radio . After a fixed time delay t delay , the transmitter sends the acoustic signal which is received at time t sound . Figure 2.9 shows the time delay computation model for this type of TDOA [START_REF] Dogancay | Bias compensation for least-squares multipulse tdoa localization algorithms[END_REF]. The two received times can be written :

t radio = t 0 + d v radio (2.
d = v radio v sound v radio -v sound (t sound -t radio -t delay ) (2.
12)

It must be noticed that the transmitter time t o is not present in this equation. Moreover, the two times t radio and t sound are measured in the receiver, and accurate synchronization between the transmitter and receiver is no more needed.

Since the radio signal propagates far faster than the acoustic wave in free space, the value of v radio -v sound is approaching to v radio , and t radio is also much smaller than t sound for short distances (i.e. indoor applications). For that reason, we can write [START_REF] Wing-Kin | Tracking an unknown time-varying number of speakers using tdoa measurements: A random finite set approach[END_REF]:

t 0 t radio (2.13) and d v sound (t sound -t radio -t delay ) (2.14)
where t sound and t radio are measured at the receiver. There is no need to synchronize the transmitter and receiver.

RSSI

The RSSI, which denotes the Received signal strength indicator, is a measurement of the receiver signal power. It is available in most of receivers and can be used for distance measurement as it can be expected that its value decreases with the distance [START_REF] Alippi | A rssi-based and calibrated centralized localization technique for wireless sensor networks[END_REF]. Many RSSI based algorithms have been presented for unknown target localization in wireless sensor networks. To characterize the relationship between the received signal strength and transmission distance, several path loss models are built based on experimental data. In free space propagation, the relationship between signal strength and transmission distance is expressed by Friis equation as [START_REF] Kaltiokallio | Distributed rssi processing for intrusion detection in indoor environments[END_REF]:

P r (d) = P t G t G r λ 2 4π 2 d η L , (2.15)
where -P r and P t are respectively the received and transmit powers, -G t and G r are the antenna gains of the transmitter and receiver, -L is the system loss, -d is the radio transmission distance, -η is the path loss exponent equal to 2 for free space, -λ is the radio wavelength defined by

λ = c f (2.16)
where c is the light speed and f is the signal frequency.

For simplicity, the values of G t , G r and L are set to 1. Equation (2.15) is simplified to:

P r (d) = P t λ 2 4π 2 d η (2.17)
From the relationship between the transmitted and received powers, we can define the path loss P L which denotes the power attenuation during the propagation [START_REF] Faheem | Improving rssi based distance estimation for 802.15. 4 wireless sensor networks[END_REF]:

P L = P t P r = ( 2π λ ) 2 d η (2.18)
Substituting (2.16) into (2.18), we get:

P L = P t P r = ( 2π c ) 2 f 2 d η (2.19)
This equation indicates that the pass loss is determined by two factors: radio frequency f and transmission distance d. Path loss increases with frequency f and distance d.

The path loss exponent η is determined by the transmission environment. In usual environments, the free space assumption is no longer verified. Multi-path and shadowing have great impact on factor η. A large number of experiments indicate that the value of η is generally between 2 and 4 [START_REF] Saxena | Experimental analysis of rssi-based location estimation in wireless sensor networks[END_REF].

A simplified formula for RSSI computation is proposed in [START_REF] David | Transmission equation for multiple cooperative transmitters and collective beamforming[END_REF]:

P r = P t (d 0 ) d η (2.20)
where d 0 is a reference distance usually equals to one meter. On the study of the received power in the receiver, the relation between RSSI and distance is interpreted as [START_REF] Wu | A 110-mhz 84-db cmos programmable gain amplifier with integrated rssi function[END_REF]:

P r (d) = P r (d 0 ) + 10ηlog( d d 0 ) + X σ (2.21)
where the powers are expressed in dBm and X σ is zero mean Gaussian distributed random variable whose mean value is zero. This variable reflects the local variations of the received power due to fading and shadowing [START_REF] Ahn | Environmental-adaptive rssi-based indoor localization[END_REF].

From the above equations, a popular RSSI channel model is presented as [START_REF] Wang | Bluetooth positioning using rssi and triangulation methods[END_REF]:

P r (dBm) = A(dBm) -10ηlog(d) + X σ (2.22)
where P r is the received signal power, A is the signal power at a distance of one meter. Many RSSI based localization algorithms are based on this channel model. These algorithms will be presented latter in this chapter.

AOA

Angle of arrival (AOA), which is also called as direction of arrival (DOA), can be used for location estimation [START_REF] Lc San | Experimental porphyria induced in rats by hexachloro-benzene. a study of the porphyrins excreted by urine[END_REF]. The AOA technique was firstly designed to estimate the location of objects in radar system, which is widely applied in military and civilian fields. The receiver with multiple directional antennas measure the angle from the signal reflected by the target 1 . Generally, the angle information is extracted by two means [START_REF] Abdalla Oa Ahmed | Development of a species-specific pcr-restriction fragment length polymorphism analysis procedure for identification ofmadurella mycetomatis[END_REF].

(1) On receiving the signal, the antenna arrays in the reference station have different phase informations. The angle of arrival can be calculated from the phase difference.

(2) The angle of arrival can also be estimated by calculating the signal amplitude at the main beam.

Algorithms developed by many authors make the direction of arrival estimation to become highly accurate and able to provide very high resolution results. The first attempt to automatically localize signal sources using an antenna array was proposed by Bartlett, which is referred to in the literature as the shift and sum beamforming method or Bartlett method. It is based on calculating the power of the beamforming output for all the possible directions [START_REF] Bartlett | Periodogram analysis and continuous spectra[END_REF]. The other conventional method is known as the Capon algorithm, which adds the constraint of making the gain of the array unity in the looking direction of arrival and then minimizing the output power in the other directions [START_REF] Capon | High-resolution frequency-wavenumber spectrum analysis[END_REF].

Location calculation

In the previous section, the methods to estimate the angle or distance, have been discussed. However, these informations need to be further processed by positioning algorithms to find the coordinates of the object.

The objective of the following sections is to present the algorithms that can be used to calculate the position, such as Triangulation, Multilateration, Trilateration, linear least squares (LLS), non linear least squares (NLS), projection onto convex sets (POCS) and semidefinite programming (SDP) [START_REF] Levenberg | A method for the solution of certain non-linear problems in least squares[END_REF]. When the angle of arrival is obtained, triangulation algorithm can be used for location estimation. As illustrated in Figure 2.10, the transmitter T sends signal to the base station i. The angle of arrival θ i is given by:

tanθ i = ( y -y i x -x i ) (2.23)
where (x i , y i ) is the coordinates of the base station i; (x, y) is the coordinates of trans-mitter T.

In triangulation, at least two base stations are needed for two-dimensional localization. The principle of triangulation is shown in Figure 2.11. The location of transmitter T can be computed from the two angles θ 1 and θ 2 by:

T (x, y) BS1 θ 1 X Y (x 1 , y 1 ) BS2 (x 2 , y 2 ) θ 2 Figure 2.11: Triangulation x = L tan(θ 2 ) tan(θ 2 ) -tan(θ 1 ) y = L tan(θ 1 )tan(θ 2 ) tan(θ 2 ) -tan(θ 1 ) (2.24)
where L is the distance between the two base stations, which can be calculated by:

L = (x 1 -x 2 ) 2 + (y 1 -y 2 ) 2 (2.25)
The accuracy of triangulation relies heavily on the measured angle of arrival. Improving the measurement precision on arrived direction is a way to guarantee a higher accuracy. Meanwhile, employing more base stations can also enhance the localization performance.

Compared to TOA method, AOA method has the following advantages. Time synchronization is not required for measuring angle of arrival. The error caused by time measurement inaccuracy is avoidable. Less base stations are needed to estimate the position in triangulation method. To find the position of one target, AOA needs two base stations but TOA needs at least three base stations with known position. Moreover, base stations can measure the arrived angle from the target without the cooperation of the target, which reduces the communication overhead and makes the localization process less complex.

However, the drawback in AOA method may cause some limitations when it is applied in practical localization process. When the distance between the target and base station is large, the measured angle value is not accurate due to the varying transmission characteristics in long path. It is hard to overcome this problem and the localization performance is reduced. Meanwhile, directional antennas or antenna array in base stations will bring additional cost for localization system. In view of these features, AOA method is more applicable in radar localization system.

Multilateration

Multilateration is a popular method for finding the position of a target. In this method, at least three anchor nodes are needed for 2-D space localization. The equations for multilateration is expressed as:

               (x -x 1 ) 2 + (y -y 1 ) 2 = d 2 1 (x -x 2 ) 2 + (y -y 2 ) 2 = d 2 2 . . . . . . . . . (x -x N ) 2 + (y -y N ) 2 = d 2 N (2.26)
where (x, y) is the coordinates of the reference or unknown nodes, (x 1 , y 1 ), (x 2 , y 2 ), • • • , (x N , y N ) are the coordinates of the N anchors. Then, this non-linear system of equations must be solved by adequate methods to obtain the unknowns x and y.

In real environment, the distance measured from signal information is inaccurate due to multi-path, reflection, shadowing and noise impact. Consequently, the position of the target can not be calculated exactly by multilateration. To find an optimal position, LLS, NLS and POCS methods have been employed and associated with multilateration. These methods will be elaborated in the following sections.

Trilateration

Anchor nodes As shown in Figure 2.12, when the number of anchors is 3, the multilateration is also called trilateration. Under minimum anchor configuration, the position can be found from three anchors, if they are not deployed in straight line. The relationship between the unknown node and three anchor nodes is written by [START_REF] Cassano | A performance comparison between roc-rssi and trilateration localization techniques for wpan sensor networks in a real outdoor testbed[END_REF]:

(x 1 , y 1 ) Unknown node (x 2 , y 2 ) (x 3 , y 3 ) (x, y)
         (x -x 1 ) 2 + (y -y 1 ) 2 = d 2 1 (x -x 2 ) 2 + (y -y 2 ) 2 = d 2 2 (x -x 3 ) 2 + (y -y 3 ) 2 = d 2 3 (2.27)
where (x, y) are the coordinates of the reference or unknown nodes, (x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 ) are the coordinates of the three anchors. By subtracting the first equation to the others, the system of equations (2.27) can be transformed into the following matrix form:

Qx = b (2.28)
where Q is a matrix of dimension 2 × 2, x is the coordinate vector, b is a vector of dimension 2.

Q = 2(x 1 -x 2 ) 2(y 1 -y 2 ) 2(x 1 -x 3 ) 2(y 1 -y 3 ) (2.29) x = x y (2.30) b = b 1 b 2 = x 2 1 -x 2 2 + y 2 1 -y 2 2 + d 2 2 -d 2 1 x 2 1 -x 2 3 + y 2 1 -y 2 3 + d 2 3 -d 2 1 (2.31)
By an adequate choice of the anchor position, we can make sure that matrix Q is invertible. So, the calculated position is:

x = Q -1 b where x = x y (2.32)
This solution for trilateration can also be written as:

x y = M x 2 1 -x 2 2 + y 2 1 -y 2 2 + d 2 2 -d 2 1 x 2 1 -x 2 3 + y 2 1 -y 2 3 + d 2 3 -d 2 1 , (2.33)
where M is a matrix of dimension 2 × 2, with the elements defined as follows.

M(1, 1) = 1 2 (y 1 -y 3 )/C (2.34) M(1, 2) = 1 2 (y 2 -y 1 )/C (2.35) M(2, 1) = 1 2 (x 3 -x 1 )/C (2.36) M(2, 2) = 1 2 (x 1 -x 2 )/C (2.37) C = x 1 y 2 -x 2 y 1 -x 1 y 3 + x 3 y 1 + x 2 y 3 -x 3 y 2 (2.38)

Hyperbolic method

When the distances from the base stations to the target are obtained, the hyperbolic method can also be used to calculate the position of the target by mathematical relationship [START_REF] Chan | A simple and efficient estimator for hyperbolic location[END_REF]. In geometry, there is a condition that the distance difference from one point to other two predefined points is a constant. All points meeting this condition will form a hyperbola. On the basis of hyperbola principle, two base stations can be set on two foci and the target is contained in the hyperbola.

T (x, y) BS1 (x 1 , y 1 ) BS2 (x 2 , y 2 ) d 1 d 2

Figure 2.13: Hyperbolic method

As shown in Figure 2.13, two base stations are on two foci of hyperbola. Their coordinates are (x 1 , y 1 ) and (x 2 , y 2 ). The position of the transmitter to be localized is denoted as (x, y). The relationship among the related positions are listed as follows:

x 2 a 2 - y 2 b 2 = 1 (2.39) a 2 = ( ∆d 2 ) 2 (2.40) b 2 = ( D 2 ) 2 -a 2 (2.41)
where a and b are two parameters for hyperbola equation, which can be provided by the measured distances. D is the distance between the two base stations. ∆d is the distance difference between the two distances d 1 and d 2 from the transmitter to the two base stations:

∆d = d 2 -d 1 (2.42)
where d 1 and d 2 are distances measured by other techniques.

It is obvious that at least three distances are needed for 2-D localization. The target position is the intersection point of two hyperbolas [START_REF] Johnson | An analysis of the discontinuous galerkin method for a scalar hyperbolic equation[END_REF].

In the previous methods, the number of equations is equal to the number of unknowns. As the measurements of distances or angle of arrival can be inaccurate, it can be interesting to increase the number of equations (by increasing the number of anchors) in order to deal with these uncertainty of the measures.

Using this idea, other methods have been developed to increase the localization accuracy, namely, linear least squares (LLS), non linear least squares (NLS) and projection onto convex sets (POCS). As said before, the price of using these methods is the increase of the number of anchors. In the next sections, these approaches will be detailed.

LLS

Assuming that in the localization process, the unknown node is ranged by N anchor nodes. The position of the unknown node is defined as (x, y) and the coordinates of all anchor nodes are denoted as (x k , y k ), k = 1, 2, ...N . The measured distance from anchor node k to the unknown node is dk . Owing to noise influence, dk is inaccurate, which can be expressed as [START_REF] Guvenc | Enhancements to linear least squares localization through reference selection and ml estimation[END_REF]:

dk = d k + n k (2.43)
where n k is an additive measurement error and d k is the real distance between the unknown node and anchor node k which is written by:

d k = (x -x k ) 2 + (ŷ -y k ) 2 (2.44)
Using dk instead of d k and according to the principle of multilateration, the estimated distances between N anchor nodes and the unknown can be written as [START_REF] Nemai | Chipless rfid tag localization[END_REF]:

(x -x 1 ) 2 + (ŷ -y 1 ) 2 = d2 1 (2.45) (x -x 2 ) 2 + (ŷ -y 2 ) 2 = d2 2 (2.46) . . . (x -x N ) 2 + (ŷ -y N ) 2 = d2 N (2.47)
where (x, ŷ) is the estimated position and d1 , d2 , ..., dN are the measured distances.

Similarly to the trilateration method, these equations are rewritten as [START_REF] Wang | Linear least squares localization in sensor networks[END_REF]:

x 2 1 -x 2 2 -2(x 1 -x 2 )x + y 2 1 -y 2 2 -2(y 1 -y 2 )ŷ = d2 1 -d2 2 (2.48) x 2 1 -x 2 3 -2(x 1 -x 3 )x + y 2 1 -y 2 3 -2(y 1 -y 3 )ŷ = d2 1 -d2 3 (2.49) . . . x 2 1 -x 2 N -2(x 1 -x N )x + y 2 1 -y 2 N -2(y 1 -y N )ŷ = d2 1 -d2 N (2.50)
These equations can be transformed into the following matrix form [START_REF] Cheung | Source localization: Algorithms and analysis[END_REF]:

Q 1 x = b (2.51)
where Q 1 is a matrix of dimension (N -1) × 2, x is the coordinate vector, b is a vector of dimension (N -1).

Q 1 =       2(x 1 -x 2 ) 2(y 1 -y 2 ) 2(x 1 -x 3 ) 2(y 1 -y 3 ) . . . . . . 2(x 1 -x N ) 2(y 1 -y N )       (2.52) x = x ŷ (2.53) b =       x 2 1 -x 2 2 + y 2 1 -y 2 2 + d2 2 -d2 1 x 2 1 -x 2 3 + y 2 1 -y 2 3 + d2 3 -d2 1 . . . x 2 1 -x 2 N + y 2 1 -y 2 N + d2 N -d2 1       (2.54)
We obtain an overdetermined system (N -1) equations and two unknowns with N > 3. Equation (2.51) can be solved by the following linear least squared problem [START_REF] Gezici | On the performance of linear least-squares estimation in wireless positioning systems[END_REF]:

M in Q 1 x -b 2 (2.55)
The solution is given by:

x = (Q T 1 Q 1 ) -1 Q T 1 b where x = x ŷ (2.56) (x, ŷ)
is the best position obtained by LLS.

NLS

This localization issue can be also settled by nonlinear least squares (NLS) approach [START_REF] Fanara | Quantitative analysis of nuclear localization signal (nls)-importin α interaction through fluo-rescence depolarization evidence for auto-inhibitory regulation of nls binding[END_REF]. Considering that the N anchors are included in the networks and their positions are known as x k = (x k , y k ), the cost function of the NLS method is expressed as: The meaning of this optimization problem is that we want to minimize the square error between the estimated distances and the distances between anchors and node. To solve this minimization function defined by (2.57), interior point method, sequential quadratic programming method (SQP), trust region reflective method, active set method and so on can be selected and employed [START_REF] Philip | Sequential quadratic programming methods[END_REF].

x = arg min x∈R 2 N k=1 [ x -x k -dk ] 2 (2.

POCS

A shortcoming of NLS method is the possible inaccuracy caused by the existence of saddle points and local minimums [START_REF] Alfred | Sensor network source localization via projection onto convex sets (pocs)[END_REF]. To search the optimal position in the possible areas, an alternative called projection onto convex sets (POCS) method is applied into target localization .

According to the previous assumption, the N anchor nodes estimate the distance to the target. N circles with center (x k , y k ) are generated by anchor nodes. For each measured distance, a disc can be defined as:

D k = {x ∈ R 2 x -x k ≤ dk k = 1, 2..., N } (2.58)
Generally, the target is located in the intersection region of the N discs. The intersection region is defined by:

x ∈ D = k=1,2...,N D k (2.59)
The localization problem is searching a position in this intersection region, which is denoted as D, as shown in Figure 2.14. As for this set D, in the presence of measurement noise, set D is equal to ∅. Considering this possible condition, the optimal position estimated by POCS minimizes the sum distances to sets D k . The minimization formulation is expressed as [START_REF] Blatt | Energy-based sensor network source localization via projection onto convex sets[END_REF]:

x = arg min x∈R 2 N k=1 x -P D k (x) (2.60)
where P D k (x) is the orthogonal projection of x onto sets D k , defined as:

P D k (x) = arg min y k ∈R 2 N k=1 x -y k (2.61)
where y k denotes all the points determined by the estimated distance d k .

Similarly, to solve the minimization function defined by (2.60), interior point method, sequential quadratic programming method (SQP), trust region reflective method, active set method and so on can be selected and employed.

SDP

SDP relaxation can also be applied to solve the localization problem in wireless sensor works [START_REF] Biswas | Semidefinite programming for ad hoc wireless sensor network localization[END_REF]. In the localization problem, non-convex constraints will give difficulties in optimization and reduce the localization accuracy. These constraints can be relaxed into semidefinite program which can approximate the position efficiently. According to the above definition, the relationship between the unknown node position x and anchor nodes position x k is expressed as [START_REF] Biswas | Semidefinite programming based algorithms for sensor network localization[END_REF]:

x -x k 2 = d 2 k k = 1, 2..., N (2.62)
where x and x k are denoted as:

x = x y (2.63)

x k = x k y k (2.64)
The minimization formulation is expressed as:

x = arg min x∈R 2 N k=1 [ x -x k -dk ] 2 (2.65)
The constraints defined by (2.62) can also be written as matrix form:

-x k 1 T I 2 x x T g -x k 1 = d 2 k (2.66)
where I 2 is an identity matrix with dimension 2 × 2, which is written as:

I 2 = 1 0 0 1 (2.67)
and g is defined as:

g = x T x = x 2 + y 2 (2.68)
Relax the above equations into a semidefinite program: change the constraint g = x T x in (2.68) to g x T x. This expression can be also modified as:

Z = I 2 x x T g 0 (2.69)
Equation (2.69) means matrix Z is a positive semidefinite matrix. Then the con-straints can also be written as its standard form:

-x k 1 T Z -x k 1 = d 2 k (2.70)
The minimization formulation in (2.65) is modified as:

Ẑ = arg min Z∈R 2 N k=1 -x k 1 T Z -x k 1 -d2 k (2.71)
Similarly, to solve the minimization function defined by (2.71), interior point method, sequential quadratic programming method (SQP), trust region reflective method, active set method and so on can be selected and employed.

RSSI-based localization algorithms

RSSI is a measurement of the power of the radio frequency signal received by a node, an access point or a router. This information is useful for determining if there is enough signal to get a good wireless connection. RSSI is a term used to measure the relative quality of a received signal to a client device, but has no absolute value. The IEEE 802.11 standard specifies that RSSI is quantified using a scale from 0 to 255 and that each chipset manufacturer can define their own maximum RSSI value. RSSI is available in most communication system: WiFi, Zigbee, Bluetooth etc. A detailed explanation of RSSI will be presented in Chapter 3.

In RSSI-based localization algorithm, accurately estimating the distance from the received signal strength value is significant to the localization precision. There exist mainly two types of RSSI based methods in the open literature. One is calibrating the channel model by RSSI value, with the help of some reference nodes. The other is building a RSSI fingerprint database for the localization area. Both methods have advantages and disadvantages. In order to calibrate the channel model, the algorithm requires multiple iterative computations, so large amount of energy is consumed. On the other hand, pre-established RSSI fingerprint does not need a large number of online operations. Therefore the localization efficiency is better. In the following section, several RSSI based localization algorithms will be presented.

Channel model based methods

RongHou Wu et al. [START_REF] Wu | Study of characteristics of rssi signal[END_REF] analyzed the main impact factors on RSSI value. Their study indicates that the multipath fading and complex environments have a significant impact on RSSI value. Through many experiments, they got the following conclusions. RSSI value has nothing to do with the measurement time. When enlarging the distance between the receive and the transmitter, the RSSI value is changed drastically. When placing some objects in the transmission path, the RSSI will decrease. The RSSI value has no regularity features in frequency domain. There is no relationship between the variance of RSSI and the transmission power. The variance is mainly determined by the environment complexity.

In [START_REF] Li | Rss-based location estimation with unknown pathloss model[END_REF], Li proposed an algorithm based on least square estimator to find RSSI channel model parameters. The simulation results indicate that the proposed algorithm can perform localization in variable environments.

A. Bahillo et al. [START_REF] Bahillo | Hybrid rss-rtt localization scheme for wireless networks[END_REF] proposed a hybrid localization method which employs RSSI value and round-trip time (RTT) simultaneously. The RSSI value is used to estimate the distance and RTT is a complementary information for channel refinement. To increase the localization accuracy, the median filter is adopted for removing some outliers [START_REF] Mazuelas | Robust indoor positioning provided by real-time rssi values in unmodified wlan networks[END_REF]. Simulation results show that this hybrid localization algorithm is superior over some RSSI based methods.

In [START_REF] Mukhopadhyay | Performance evaluation of localization techniques in wireless sensor networks using rssi and lqi[END_REF], B. Mukhopadhyay, S. Sarangi and S. Kar adopted three different estimators to calculate and predict the position of the unknown node. Besides static nodes, they also attempted to determine the position of mobile sensor nodes. From their localization results, the proposed estimators are efficient and have the least RMSE value.

To obtain a better localization performance, scholars proposed many algorithms to improve the distance estimation. F. Subhan, S. Ahmed and K. Ashraf [START_REF] Subhan | Extended gradient predictor and filter for smoothing rssi[END_REF] proposed a gradient based RSSI filter to acquire smooth value for increasing the localization accuracy. In their simulation, they compare the proposed gradient filter and the Kalman filter. Y. Tian, Z. Tang and Y. Yu [START_REF] Tian | Third-order channel propagation modelbased indoor adaptive localization algorithm for wireless sensor networks[END_REF] developed a third-order polynomial RSSI model for distance estimation. F. Yaghoubi and B. Maham [START_REF] Yaghoubi | Energy-efficient rssi-based localization for wireless sensor networks[END_REF] presented a new metric to estimate localization error bound in WSNs. They use an experimental lognormal path loss channel model to evaluate their approach. In [START_REF] Vaghefi | Cooperative received signal strength-based sensor localization with unknown transmit powers[END_REF], the authors proposed to associate Non linear Least Squares (NLS) and multilateration to find optimal position.

Fingerprint based methods

B. Turgut and R. P. Martin [START_REF] Turgut | Localization for indoor wireless networks using minimum intersection areas of iso-rss lines[END_REF] proposed a novel method based on RSSI value acquired from many anchor nodes in indoor environment. They draw RSSI surface for each anchor node from a large number of training data. After completing the whole RSSI surface, they extract the line with same RSSI value for each anchor nodes. They deduce from this study an indoor RSSI map data for the area of interest. In the localization process, the device measures the RSSI value from all the anchor nodes and get the corresponding same RSSI line from the map. Among all the lines, the most likely intersection point is found. They also presented a recursive method to search the optimal position of the unknown device. Based on experiments data, this method gives a better localization performance than some current localization methods.

Yin, J et al. [START_REF] Yin | Adaptive temporal radio maps for indoor location estimation[END_REF] presented a method to draw the relationship between the radio map and the time dimension to weaken the influence of the external environment variability. Instead of updating the signal maps continuously, they deploy specific devices in the location area which can be treated as reference nodes. On the basis of the analysis and calculation of the reference nodes, a signal map is built for the location estimation of the unknown node within this region. In their approach, a signal map together with the signal characteristics from both the reference nodes and the unknown target is constructed. During the localization stage, regression models are used to forecast the most likely coordinates of the mobile nodes.

According to the required accuracy, time constraints and complex environmental conditions, some tradeoff should be made. In [START_REF] Felipe | Calibration-free wlan location system based on dynamic mapping of signal strength[END_REF], De Morqes et al. proposed a system for detecting and localizing unknown wireless devices, without additional assistance from human beings or other remote clients. They build an architecture based on wireless sniffers which can be used for measuring the signal feature, such as the wireless signal average energy, the received signal strength indicator (RSSI), signal propagation delay and so on. In this way, with the help of the existing WLAN or GSM infrastructure in the vicinity of the deployed networks, some special equipment is no longer a must and the monitoring costs are reduced. In [START_REF] Yixuan Zhu | Spatiotemporal (st) similarity model for constructing wifi-based rssi fingerprinting map for indoor localization[END_REF], they presented a new RSSI fingerprint model. The developed model is applied to indoor WIFI localization system. The simulation results show that this model is superior over the traditional map models.

Conclusion

In this chapter, the localization principle and main algorithms have been discussed. A classification of localization strategies in WSNs has been provided, and some typical approaches have been detailed.

The localization means, such as, GPS method, cellular network method, infrared device method, ultrasonic wave method, and micro inertial navigation method have been introduced. The methods for measuring the angle or distance, including TOA, TDOA, RSSI and AOA, have been presented in detail. In addition, the positioning algorithms such as Triangulation, Multilateration, Trilateration, linear least squares (LLS), non linear least squares (NLS), projection onto convex sets (POCS) and semidefinite programming (SDP) have been introduced.

Finally, the state of the art of RSSI based methods has been presented, including the channel model based methods and the fingerprint based methods.

In our study, we focus on indoor localization algorithm based on RSSI channel model. So the first step is to characterize and model the RSSI. This is the main objective of the next chapter.

Theoretical channel model

Model-based RSSI localization techniques have been proposed in the literature for different radio technologies [START_REF] Mukhopadhyay | Novel rssi evaluation models for accurate indoor localization with sensor networks[END_REF]. Among the number of channel models proposed for outdoor and indoor environments (Nakagami, Rayleigh, Ricean, etc.), the most popular channel model for RSSI-based localization, thanks to its simplicity, is the lognormal shadowing path loss model [START_REF] Seon | Efficient and consistent path loss model for mobile network simulation[END_REF], which expresses the following relation between the received power and the transmitter-receiver distance:

RSSI(dBm) = A(dBm) -10ηlog(d) + v (3.1)
where A is a constant term which accounts for the transmission power of the node to be localized, d is the distance between transmitter and receiver, η is the path loss exponent and v is a zero-mean Gaussian random variable.

Suppose that the distance estimation is based on M samples of RSSI (k,i) , which represents the ith RSSI sample measured by the kth anchor node. Then, according to (3.1), we have:

RSSI (k,i) = A k -10η k log(d k ) + v (k,i) (3.2)
where d k is the distance from the unknown node to the kth anchor node, A k and η k are the model parameters of the kth anchor, v (k,i) is a zero-mean white Gaussian random variable with standard deviation σ k .

In the channel model, the noise is assumed to be Gaussian distributed. When a variable is Gaussian distributed, its mean value is equal to its median value. However, in practical condition, where some outliers may exist, it is better to use the median value to estimate the distance since it is more robust to outliers.

For getting a good performance, the median value of RSSI (k,i) is used to obtain the distance estimate: dk = 10

A k -RSSI k 10η k (3.3)
where RSSI k , the median RSSI value measured by the kth anchor, is given by:

RSSI k = M edian{RSSI (k,i) , i = 1, • • • , M } (3.4)
Finally, the estimated position is calculated by the multilateration method.

Experiment setup

Sensing Generally, many sensor nodes are deployed as a part of WSNs in a monitored region for collecting specific information. As illustrated in Figure 3.1, a typical sensor node includes four modules: sensing unit, processing unit, communication unit and power unit [START_REF] Vujovic | Raspberry pi as a wireless sensor node: performances and constraints[END_REF]. Sensing unit includes two parts: sensors and analog-to-digital converter (ADC). A variety of sensors, for example, light sensor, temperature sensor, humidity sensor, pressure sensor and so on, are included in the sensor nodes for acquiring relevant information. The analog signal is transformed into digital signal by an ADC before being processed and stored. Processing unit consists of processor and memory. After measured by sensor module, the related data are processed in the processor and saved in the memory if needed. Data transmission is performed by the transceiver. The power unit supplies energy to the other three units. These four parts work cooperatively to accomplish data collection, processing and transmission.

At present, there exist many sensor node platforms, such as Raspberry Pi, MicaZ, TelosB, Iris, Cricket, Lotus and so on. The main features of these sensor node platforms are illustrated in Table 3.1. There are also some drawbacks like high power consumption which is not compatible In our experiment, the Raspberry Pi is adopted to build the localization system. Raspberry Pi model A is shown in Figure 3.2, which is configured as an access point in our localization system and Raspberry Pi model B is shown in Figure 3.3, which is defined as a mobile node. The experiment has been done in a large hall. The testing scene is shown in Figure 3.4. The experimental testbed has been build using three wifi access points (AP) and a mobile wifi point. The three wifi access points represent the three anchor nodes and the mobile wifi point is considered as the unknown node. The schematic diagram of the testing localization system is shown in Figure 3.5. In this diagram, the mobile point can be considered as a server and three access points can be regarded as three clients.

The RSSI data acquisition process can be divided into the following procedures:

(1) Server initialization: the server starts up and waits clients to join.

(2) Three clients start up and try to connect to the access point.

(3) Connection is set up between server and three clients.

(4) Server sends signal to each client. After receiving the signal, all clients measure the received signal level and send related packet back to the server.

(5) Server accepts all the received signal levels and transforms them into RSSI values.

(6) Repeating procedures (1) -( 5), a large number of RSSI values are collected.

In the following, an explanation of RSSI and how to acquire the RSSI value from the localization system are discussed. Generally, the received signal strength is not expressed in milliwatts (mW), dBm but in percentage value. In the testing, the acquired percentage value is converted to dBm by the Cisco lookup table, shown in Table 3.2. In this lookup table, the percentage values, from 0% to 100%, are changed to a set of negative values in dBm, from -113 to -10. To simplify this transformation, in the measurement we adopt a fitting relationship, which is shown in Figure 3.6. This relationship can be approximated by: To acquire RSSI values, we have created a python program to read the quality level value. The data packets are illustrated in the Table 3.3. Among these data, the signal level can be extracted and converted to values in dBm.

P (dBm) =

Experimental channel model

To characterize the RSSI model in an indoor environment, measurements have been realized. The experiment has been done in a large hall. The testing scene is shown in Figure 3.4. The experimental testbed has been build using three wifi access points (AP) and a mobile wifi device. To establish the practical channel model in this hall, many measurements have been performed on different positions. To acquire a larger number of RSSI values, for each distance, the direction of the mobile point is changed 30 times. Repeating this measurement process, a large number of RSSI data are obtained by changing the distance from 1 meter to 10 meters with interval of 0.5 meters.

Based on the measured RSSI data, the median RSSI is calculated for one distance. Figure 3.7 presents the measured mean RSSI as function of the distance. As expected, we can find that the mean RSSI value decreases with the distance. From these results we can deduce the following channel model:

RSSI k = -9.40 -22.7log(d k ) + v k (3.6)
with v k a zero-mean random variable with standard deviation σ k . Therefore, based on the measured data, A k = -9.40, η k = 2.27 can be deduced for the experimental channel model.

Meanwhile, the standard deviation of the noise for each distance can be estimated

σk = 1 M M i=1 [RSSI (k,i) -RSSI k ] 2 (3.7)
where RSSI k is the mean value of RSSI (k,i) , given by:

RSSI k = 1 M M i=1 RSSI (k,i) (3.8)
The obtained results are shown in Figure 3.8. From the experimental results, the standard deviation of the noise, in terms of the distance from 1 to 10 m, can be expressed as:

σ(d) = -0.11d 2 + 2.18d -0.38 (3.9)
This expression will be used in the following study to provide the RSSI values using model (3.6) and to evaluate the localization algorithms. The variance model defined 9) is of course specific to our measurement condition but indicates that the RSSI variance tends to increase with distance which has been already observed in some works [START_REF] Xu | Distance measurement model based on rssi in wsn[END_REF]. It is worth noting that the relationship between the noise variance and distance depends on the environment size and complexity. To confirm this trend, simulation is done using a ray tracing system for an environment similar to the experimental environment. We have designed a ray tracing system whose simulation scenario is shown in Figure 3.9. As illustrated in this simulation scenario, there is a simulated workshop with two obstacles in it. A transmitter denoted by T X, sends signal to a mobile receiver denoted by RX, which moves from position 1 Figure 3.9: Simulation scenario of ray tracing system to position 2. In the simulation, the median RSSI value is calculated based on these simulated data. The relationship between the distance and standard deviation of noise for four cases are observed.

In this simulation, four cases are considered to observe different environment conditions. In the first two cases, we observe the relationship between the RSSI values and distance with no obstacle in the room. In others cases, we change the room size or put two obstacles in it. The detailed information for these four cases is illustrated in Table 3.4. In the simulation, for one position, 30 different RSSI values are measured and 180 positions are considered by changing the distance from 1 meter to 10 meters with interval of 0.05 meters. Similarly, the median RSSI is calculated for one distance and the relationship between the distance and RSSI is plotted for four cases. These results are shown in Figure 3 Moreover, the linear approximation for the four cases is plotted in Figure 3.14. Based on these simulated RSSI data, the values of parameters A and η for all cases are estimated and given in Table 3.5.

From these results, we can compare the parameters for four cases. In the first and second cases, there is no obstacle in the workshop. In the second case, we enlarge the room size. By comparing the parameters of case 1 and 2, we can find that A value increases from -100.20 to -99.99, which represents a very small evolution. Similarly, η value decreases from 1.95 to 1.99. This is because the reflected signal strength weakens when the room size is enlarged. In the third and fourth cases, we put two obstacles in the room, as shown in Figure 3.9. It indicates that η increases when obstacles are putting in the measurement space. This is because signal attenuates when there are obstacles between the transmitter and receiver. Besides, all η values based on measured data are larger than that based on the simulated data. The reason for this difference is firstly that the simulation scenario is simpler than the real measurement environment, and secondly that the simulator simplifies the physical phenomena of propagation. From the above analysis on the simulated RSSI data, it can be observed that the real and simulated data have a similar tendency in terms of the relationship between the noise standard deviation and distance. The noise standard deviation increases with distance. However, due to the complex environment, the standard deviation based on real data is larger than the simulated data.

Conclusion

In this chapter, the lognormal shadowing path loss model which is employed as the theoretical channel model for distance estimation has been introduced. In the experiment, the Raspberry Pi is adopted to build the localization system. The experiment has been done in a large hall. To establish the practical channel model in this hall, many measurements have been performed on different positions. Based on the acquired RSSI data, an experimental channel model has been constructed. To confirm this trend, simulation has done using a ray tracing system for an environment similar to the experimental environment.

In the following chapter, three proposed localization algorithms: Three minimum Distances Method (TDM), Weighted Three minimum distances Method (WTM) and Weight values Adjustment Method (WAM) based on NLS and multilateration will be developed. The comparison of TDM, WTM, WAM, LLS, NLS and POCS in terms of the localization accuracy and calculation time will be presented.

Localization algorithms

The last chapter has shown that the relationship between the RSSI value and distance can be written as:

RSSI(dBm) = A(dBm) -10ηlog(d) + v (4.1)
where A and η are channel parameters whose values change with the environment and v is a noise whose variance is also largely variable. So the RSSI is not a reliable information to deduce the distance. The objective of this chapter is to propose and evaluate some localization algorithms by taking into account the low accuracy of distances deduced from RSSI measurements. Three approaches called three minimum distances method (TDM), weighted three minimum distances method (WTM) and weight values adjustment method (WAM) are proposed. Using the testbed described in Chapter 3, experimental channel model is deduced in order to verify the performance of the proposed algorithms in realistic conditions. In the following parts, the proposed localization algorithms are detailed and performance comparison is presented.

Distance estimation from RSSI

All the proposed algorithms are based on the distance estimated from RSSI. So the first step of the study is to define a method to do this estimation and to evaluate the distance accuracy.

Suppose that the distance estimation is based on M samples of RSSI (k,i) , which represents the ith RSSI sample measured by the kth anchor node.

For getting a good performance, the mean value of RSSI (k,i) is used to obtain the distance estimate: dk = 10

A k -RSSI k 10η k (4.2)
where RSSI k , the mean RSSI value measured by the kth anchor, is given by:

RSSI k = 1 M M i=1 RSSI (k,i) (4.
3)

It should be noticed that the mean value can be replaced by the median value in practical situations with the advantage that the median value is less sensitive to outlets. In our model, because the RSSI (k,i) are Gaussian distributed, the mean value is equal to the median value.

Using channel model defined by (3.2) and substituting (4.3) to (4.2), we can deduce the estimated distance as:

dk = d k 10 -1 10η k 1 M M i=1 v (k,i) (4.4)
If the noise is small or the number of samples M is large, the estimated dk can be approximated by:

dk d k [1 - ln10 10η k 1 M M i=1 v (k,i) ] (4.5)
Then the measurement error can be evaluated by the following additive noise:

n e = -d k ln10 10η k 1 M M i=1 v (k,i) (4.6)
Its variance is given by :

σ 2 e = d 2 k σ 2 k ( ln10 10η k ) 2 1 M (4.7)
To confirm this theoretical derivation, simulations are performed to observe the relationship between the distance variance σ 2 e and the sample number M . In Figure 4.1, a distance value d k is given to be 5 and the relationship between the distance variance σ 2 e and the sample number is plotted. These results indicate that the simulation results match well with the deduced expression although there exists error caused by noise. With the increase of the sample number M , the error between the measured distance variance and theoretical value becomes smaller. When the distance value is set to 8, a similar result can be obtained which is illustrated in Figure 4.2. As expected, the distance variance becomes larger when the distance increases. From equation (4.7) we can deduce that the variance of the estimated distance depends on the distance and on the measurement noise variance. Form the previous study, we also know that the noise variance increases with the distance. It is clear that a large distance corresponds to a stronger estimation variance, giving a less precise estimation of the distance. Expression (4.7) provides some guidances to reduce the localization error, such as using the smallest distance from the unknown node to anchor nodes or increasing the sample number M . Another strategy is to exploit this property in the definition of the localization algorithms, which will be described in the following sections.

Localization methods

Multilateration

The multilateration algorithm is a basic positioning method, widely used in many localization systems [START_REF] Zheng | Localization algorithm based on rssi and distance geometry constrain for wireless sensor network[END_REF]. In this algorithm, at least three anchor nodes are needed for two dimension localization. The position of the anchor nodes is assumed to be known. The relationship between the unknown node position and N anchor nodes positions can

               (x -x 1 ) 2 + (y -y 1 ) 2 = d 2 1 (x -x 2 ) 2 + (y -y 2 ) 2 = d 2 2 . . . . . . . . . (x -x N ) 2 + (y -y N ) 2 = d 2 N (4.8)
where (x, y) is the coordinates of the reference or unknown nodes, (x 1 , y 1 ), (x 2 , y 2 ), • • • , (x N , y N ) are the coordinates of the N anchors.

In ideal conditions, in the absence of fading, noise and channel model error, the above equations represent N circles that will intersect at only one position. This intersected point is the actual position. Unfortunately, in practical condition, the N circles do not intersect at one position due to the fading and noise impact. For example, when the number of anchor is equal to 3, Figure 4.3 shows the three circles in ideal condition and in real condition. In the case of real condition, we need to find the most likely position in other ways.

Proposed methods

To approximate the most likely position, non-linear least square (NLS) has been proposed. This algorithm has been described in Chapter 2. The nonlinear optimization problem can be solved by using the sequence quadratic programming algorithm [START_REF] Mohammad | On geometric upper bounds for positioning algorithms in wireless sensor networks[END_REF].

In this thesis, we propose three novel methods based on NLS, called TDM, WTM and WAM. For these proposed methods, the objective minimization function is modified and the best position is given by:

(x, y) = argmin N k=1 α k [(x -x k ) 2 + (y -y k ) 2 -( dk ) 2 ] 2 (4.9)
where N is the number of anchors, (x k , y k ) is the coordinates of the kth anchor and dk the estimated distance from the median RSSI value at the kth anchor. We introduce a weight α k used for each estimated distance dk .

The weights are introduced to deal with the fact that the distance estimation variance increases with the distance. The weights values differ with different proposed methods.

In TDM, the three smallest estimated distances are selected from the N available distances. Thus, the weights are defined by:

α k =    1 k = m 1 , m 2 , m 3 0 k = m 1 , m 2 , m 3 (4.10)
where m 1 , m 2 and m 3 are the index of three selected minimum distances.

For WTM, firstly, the three smallest estimated distances are selected from the N available distances. Then, different weight values are assigned for the three selected distances. Therefore, the weight values α k are modified as:

α k =    1 d2 k σ2 k k = m 1 , m 2 , m 3 0 k = m 1 , m 2 , m 3 (4.11)
where m 1 , m 2 and m 3 are also the indices of the three smallest distances.

For WAM, all the distances are selected and the weight values in (4.9) are defined by:

α k = 1 d2 k σ2 k (4.12)
In the previous paragraph, we have determined the variance of dk that measures the dispersion of the estimated distance around the true distance. The values of the weights are chosen to be proportional to the inverse of this variance in (4.7). Hence, the uncertainty of the measured distances can be taken into account in the objective function.

The six different methods based on multilateration: TDM, WTM, WAM, LLS, NLS and POCS will be evaluated in the following section. Furthermore, the accuracy and calculation time of these six methods will be compared. When the number of anchors is three, the anchor nodes are located at A, B, and C.

Simulation and localization performance

When this number is four, the fourth node is located at D. In a similar letter order, more anchors positions can be determined.

In the simulation, the unknown node position is randomly selected from the intersection points of the grid, as shown in Figure 4.4. Then, for each position we calculate the root mean square error (RMSE) value defined as:

RM SE = 1 T T t=1 (x(t) -x(t)) 2 + (ŷ(t) -y(t)) 2 (4.13)
where (x(t), y(t)) is the real selected position. (x(t), ŷ(t)) is the position estimated by the compared localization methods. T is the number of randomly chosen positions. In the simulation, T is equal to 500. It should be noted that the sequence quadratic programming is used in NLS, POCS, TDM, WTM and WAM to search the optimal position in the possible region. In this special simulation scenario, the possible searched region is defined by the square area limited by A, B, C and D. As illustrated in Figure 4.5, when the number of anchors is 3, TDM and NLS are equivalent, so the accuracy of the two methods is identical. Similarly, a same accuracy is obtained by WTM and WAM as they have no difference when the number of anchors is 3. When the number of anchors is 4, 5, 6, 7, or 8, the RMSE value of TDM is smaller than that of LSM, which indicates that the accuracy of the proposed TDM is superior to that of LSM. Besides, WTM gives a higher localization accuracy than TDM and NLS. Among all the compared methods, WAM is the best one in terms of estimation accuracy.

Meanwhile, the simulation times (ST) for each method implemented in MATLAB software on a computer with processor unit (CPU) of 2.6 GHz and 16 GB of RAM are observed. As shown in Table 4.1, the influence of the number of anchors on simulation time is negligible. This time is almost the same for NLS, TDM, WTM and WAM. The calculation time for one single localization process of NLS, TDM, WTM and WAM is around 22ms. The calculation times of a single localization for LLS and POCS are 3ms and 36ms respectively.

Conclusion

In this chapter, three proposed localization algorithms: Three minimum Distances Method (TDM), Weighted Three minimum distances Method (WTM) and Weight values Adjustment Method (WAM) based on NLS and multilateration have been described. For getting a good performance, the median RSSI value is used to obtain the distance estimate. Multilateration is adopted in the position process. The comparison of TDM, WTM, WAM, LLS, NLS and POCS in terms of localization accuracy and calculation time has been presented.

In this chapter, we have assumed that the channel parameters (A and η) are perfectly known. The error in distance estimation is due to the noise v. In a real application, these parameters will change with time. Therefore, it is necessary to learn these parameters. In the next chapter, we will develop methods to acquire and track the evolution of the channel model.

In our work, we consider the localization of the target when the environment changes frequently and RSSI channel model parameters have variation. Different from the existing channel model based algorithms, we reduce the localization error caused from parameter variation by a grid based learning and tracking strategy. In the context of applications where the positions are constrained on a grid, a novel tracking strategy is proposed to determine the real position and obtain the actual parameters in the monitored region. Based on practical data acquired from the testbed described in Chapter 3, an experimental channel model is constructed to provide RSSI values and verify the proposed tracking strategy. The simulation results show a good behavior of the proposed tracking strategy in presence of space-time variation of the propagation channel. Compared with the existing RSSI based algorithms, the proposed tracking strategy exhibits better localization accuracy but consumes more calculation time. In addition, a tracking test is performed to validate the effectiveness of the proposed tracking strategy.

In the next sections, the proposed parameter tracking strategy and localization algorithm will be described. Localization and tracking results for assessing the performance of the proposed technique and analyzing its limitation will be provided. Furthermore, the localization performance comparison and tracking test will be presented.

An example of localization scenario

Moving robot (wire guided trolley or robot) In some industrial production applications, such as in an indoor workshop, a set of devices is arranged in the indoor space, as shown in Figure 5.1. The position of each device is precisely defined, and generally, these devices are regularly deployed on the ground following a certain rule. A robot is moving along the predefined lines in this working space and will stop at one of the predefined positions to check each device. This scenario can be modeled as a grid as shown in Figure 5.2, where we suppose that the mobile robot can only stop at one of the intersection dots of a grid. So the localization problem consists only in making a choice between the intersection points. The proposed technique, exploiting the a prior knowledge of the possible locations of the devices, allows localizing the robot in one of the intersection dots and tracking the trajectory of the robot and the variation of the channel parameters due to the changement of the environment. RSSI based localization method is a good option for this specific application but we have to check that (1) errors due to the channel model inaccuracy are less than the grid resolution, (2) small position error correction is possible and can be used to track in real time the channel variations.

These two conditions will be developed later in the following section. Without loss of generality, we consider in this study that the size of the grid is 10m × 10m. Anchors are placed on three dots, whose coordinates are (0, 0), (0, 10), (10, 0), respectively. In the coordinate scale, 1 denotes 1 meter. There exists a reference node in the center of this region, whose position is (5,5).

Distance estimation

Suppose that the distance estimation is based on M samples of RSSI (k,i) , which represents the ith RSSI sample measured by the kth anchor node. For getting a good performance, the median value of RSSI (k,i) is used to obtain the distance estimate:

dk = 10 A k -RSSI k 10η k (5.1)
where RSSI k , the median RSSI value measured by the kth anchor, is given by:

RSSI k = M edian{RSSI (k,i) , i = 1, • • • , M } (5.2)

Trilateration algorithm

In Chapter 2, many positioning methods have been described. Compared to other optimization methods, trilateration algorithm can compute the position directly and quickly on condition that three anchors are non-linearly placed. Therefore, in the proposed tracking strategy, to reduce the calculation time, the trilateration algorithm is employed to calculate the position. The trilateration algorithm is a basic positioning method, widely used in many localization systems [START_REF] Spencer | Modeling the statistical time and angle of arrival characteristics of an indoor multipath channel[END_REF]. In this algorithm, at least three anchor nodes are needed for positioning the target. The position of the anchor nodes is assumed to be known. As presented in Chapter 2, the relationship between the unknown node position and three anchor node positions can be expressed as [START_REF] Hamdoun | Comparative analysis of rssi-based indoor localization when using multiple antennas in wireless sensor networks[END_REF]:

         (x -x 1 ) 2 + (y -y 1 ) 2 + (z -z 1 ) 2 = d 2 1 (x -x 2 ) 2 + (y -y 2 ) 2 + (z -z 2 ) 2 = d 2 2 (x -x 3 ) 2 + (y -y 3 ) 2 + (z -z 3 ) 2 = d 2 3 (5.3)
where (x, y, z) are the coordinates of the reference or unknown node, (x 1 , y 1 , z 1 ), (x 2 , y 2 , z 2 ), (x 3 , y 3 , z 3 ) are the coordinates of the three anchors. Equations (5.3) can be written into the following matrix form:

Qx = b (5.4)
where Q is a matrix of dimension r × r, x is the coordinate vector, b is a vector of dimension r, r is the dimension of position coordinates.

For two dimensional problem considered in this study, Q with dimension 2 × 2 and b with dimension 2 are written respectively as:

Q = 2(x 1 -x 2 ) 2(y 1 -y 2 ) 2(x 1 -x 3 ) 2(y 1 -y 3 ) (5.5) b = x 2 1 -x 2 2 + y 2 1 -y 2 2 + d 2 2 -d 2 1 x 2 1 -x 2 3 + y 2 1 -y 2 3 + d 2 3 -d 2 1 (5.6)
Whether Q is invertible or not will depend on the determinant value of Q. Making a good choice of the anchor positions can guarantee that the matrix is invertible. In our localization scenario, three anchor nodes are placed at (0, 0), (0, 10), (10, 0), respectively. Under this deployment, it is easy to show that |Q| = 0, then Q is invertible. Consequently, the estimated position is given by:

x = Q -1 b = Pb where x = x ŷ (5.7)
where (x, ŷ) is the estimated position obtained by the trilateration method.

Channel model identification

To identify the channel model, LMS algorithm is employed in the tracking strategy. LMS algorithm can be considered as a basic machine learning algorithm, widely used for parameter estimation [START_REF] Tarrío | Weighted least squares techniques for improved received signal strength based localization[END_REF]. LMS allows finding the values of parameters of a function after several iterative calculations in a computationally efficient way [START_REF] Mishra | Analysis of lms, rls and smi algorithm on the basis of physical parameters for smart antenna[END_REF]. It is based on approximating the true gradient of the squared error of estimation by its instantaneous estimate. In the proposed tracking strategy, the error is minimized by recursively modifying A and η of the channel model. As illustrated in Figure 5.3, RSSI values related to the three anchor nodes are acquired by the reference or target node. At each iteration t, the related distances are measured by (5.1) with A(t -1) and η(t -1) estimated at iteration (t -1). Then, the trilateration algorithm calculates the estimated position (x(t), ŷ(t)). With the known real position of reference point (x, y), the localization error is formulated as:

ε(t) = (x(t) -x(t)) 2 + (ŷ(t) -y(t)) 2
(5.8)

where t denotes the iteration number.

This error serves as the input to the LMS algorithm, by adaptively minimizing the localization error, we obtain η as follows:

η(t) = η(t -1) -µ η ∂ε(t) 2 ∂η (5.9)
The derivative of ε(t) 2 with respect to η is:

∂ε(t) 2 ∂η = ∂[(x(t) -x(t)) 2 + (ŷ(t) -y(t)) 2 ] ∂η = 2[x(t) -x(t)] ∂ x(t) ∂η + 2[ŷ(t) -y(t)] ∂ ŷ(t) ∂η (5.10)
The derivatives of the estimated position x(t) and ŷ(t) with respect to η are given by:

∂ x(t) ∂η = -2P(1, 1) d1 ∂ d1 ∂η + 2P(1, 1) d2 ∂ d2 ∂η -2P(1, 2) d1 ∂ d1 ∂η + 2P(1, 2) d3 ∂ d3 ∂η (5.11) ∂ ŷ(t) ∂η = -2P(2, 1) d1 ∂ d1 ∂η + 2P(2, 1) d2 ∂ d2 ∂η -2P(2, 2) d1 ∂ d1 ∂η + 2P(2, 2) d3 ∂ d3 ∂η (5.12)
∂ dk ∂η = -ln(10)10

A-RSSI k 10η A -RSSI k 10 1 η 2 (5.13)
Similarly, we can get A from the following equation:

A(t) = A(t -1) -µ A ∂ε(t) 2 ∂A (5.14)
The derivative of ε(t) 2 with respect to A is:

∂ε(t) 2 ∂A = ∂[(x(t) -x(t)) 2 + (ŷ(t) -y(t)) 2 ] ∂A = 2[x(t) -x(t)] ∂ x(t) ∂A + 2[ŷ(t) -y(t)] ∂ ŷ(t) ∂A (5.15)
The derivatives of the estimated position x(t) and ŷ(t) with respect to A are given by:

∂ x(t) ∂A = -2P(1, 1) d1 ∂ d1 ∂A + 2P(1, 1) d2 ∂ d2 ∂A -2P(1, 2) d1 ∂ d1 ∂A + 2P(1, 2) d3 ∂ d3 ∂A (5.16) ∂ ŷ(t) ∂A = -2P(2, 1) d1 ∂ d1 ∂A + 2P(2, 1) d2 ∂ d2 ∂A -2P(2, 2) d1 ∂ d1 ∂A + 2P(2, 2) d3 ∂ d3 ∂A
(5.17)

∂ dk ∂A = ln(10)10 A-RSSI k 10η 1 10η (5.18)
where µ η and µ A are the adaptation step size, which can be adjusted experimentally.

Tracking strategy

The whole proposed tracking strategy and localization process are illustrated in Figure 5.3. In the proposed algorithm, this task is done in two steps: an initial channel estimation using a reference node followed by a tracking procedure using a grid correction based on the constrained positions.

In the first step, the mobile robot is positioned at a reference point whose position is known. Then the trilateration algorithm is used to estimate the location and LMS is employed to find the channel parameters  and η which minimize the positioning error.

After the acquisition step, a grid correction strategy is adopted for the localization and channel variation tracking. We subdivide this step into the following procedures.

1. Based on  and η obtained in the acquisition step, we estimate the unknown node position denoted by (x, ŷ).

2. After getting (x, ŷ), we calculate all the distance values between (x, ŷ) and the intersection points in the grid. The nearest intersection point will be selected as the most likely position, whose coordinates are ( ẋ, ẏ).

3. Knowing the most likely position ( ẋ, ẏ), we use LMS to track the space and time evolution of the channel parameters, the tracked parameters are denoted by Ȧ and η.

4. These procedures can be repeated in real time.

The process can be easily extended to a scenario where there are also non-anchor nodes in fixed positions that first localize themselves and then contribute to the tracking.

Localization results

After acquiring the channel model from the experimental data, we can evaluate the localization process using simulation. As shown in Figure 5.2, we set three anchor nodes in the three predefined positions with coordinates A(0, 10), B(0, 0), C(10, 0), respectively. In the simulation, the unknown node position is randomly selected from the intersection points of the grid. Then, for each position we calculate the RMSE value defined as [START_REF] Wang | An asymptotically efficient estimator in closed-form for 3-d aoa localization using a sensor network[END_REF]:

RM SE = 1 T T t=1 (x(t) -x(t)) 2 + (ŷ(t) -y(t)) 2 (5.19)
where (x(t), y(t)) is the actual selected position. (x(t), ŷ(t)) is the position estimated by the trilateration method. T is the number of randomly chosen positions. In the simulation, T is equal to 500. we can obtain A value very close to -10dBm. Similarly, the obtained η value is very close to 2.24. Furthermore, in the tracking step, we suppose that the true value of A is -11dBm and the true value of η is 2.20. In the same manner, we can get A value very close to -11dBm and η value very close to 2.20. So, the proposed strategy can track the variation of the parameters in the monitored region.

Limitation analysis

However, there exists a limitation in the grid correction. If the localization error is larger than the grid step size, it is no more guaranteed that the correction strategy will be efficient. Therefore, we need to analyse the relationship between the step size and parameter variation which gives us a criterion to choose an appropriate step size value. The localization error is defined as [START_REF] Cort | Advantages of the mean absolute error (mae) over the root mean square error (rmse) in assessing average model performance[END_REF]:

ε(t) = ( x(t) -x(t)) 2 + ( y(t) -y(t)) 2
(5.20)

where (x(t), y(t)) is the real position, ( x(t), y(t)) is the estimated position. As shown in Figure 5.6, the real position (x(t), y(t)) is located in the center. The distance from (x(t), y(t)) to its four possible nearest positions is equal to the grid step size s. If the estimated position ( x(t), y(t)) is located in the dark region, we can get a right correction. This region is defined by the following relationships:

   ( x(t) -x(t)) 2 < s 2 4 ( y(t) -y(t)) 2 < s 2 4 (5.21)
where s is the step size.

If ε(t) < s 2 , the estimated position ( x(t), y(t)) is located inside the circle in Figure 5.6. We are sure that the grid correction strategy is effective and it guarantees a satisfactory position correction. In the simulation, we perform 1000 estimation iterations in the predefined region and find gird step size s which meets the following probability relationship: In the simulation, η is set to be 2.27 and ∆η increases from 0.02 to 0.22 with interval 0.02. Similarly, Â is set to be -9.39 and ∆A increases from 0.5dB to 4dB with interval 0.5dB. The relationship between s and ∆η is shown in Figure 5.7. With the increase of ∆η, the needed step size becomes larger and larger. According to these simulation results for three different η values, for a same ∆η value, the needed step size increases inversely with η. When the value of ∆η is determined, we can find a threshold value of step size s threshold . As long as s is larger than s threshold , we can get a right correction. Similarly, the relationship of step size s and ∆A is shown in Figure 5.8. These results provide a criteria to guarantee that the proposed tracking strategy is effective by making the tradeoff between grid step size s and parameter variation. In practice, the grid step size is fixed by the application, this calculation could give us a mean to make an alarm on the possible failure of the tracking strategy by estimating the variation of parameters ∆η and ∆A in the monitored region.

P (ε(t) < s 2 ) > 0.95 (

Performance comparison

In this part, the localization performance of the proposed tracking strategy is compared with SDP [START_REF] Ouyang | Received signal strength-based wireless localization via semidefinite programming: Noncooperative and cooperative schemes[END_REF] and WLS [START_REF] Wang | On received-signal-strength based localization with unknown transmit power and path loss exponent[END_REF] in terms of accuracy and computational complexity. The channel model parameters in (3.2) and the standard deviation of noise in (3.9) deduced from the experimental data are used to provide RSSI values for assessing the compared algorithms. In the simulation, we suppose that the channel parameters are varying between the acquisition step and tracking step. In the proposed tracking strategy, the positioning is performed by trilateration after obtaining the tracked parameters Ȧ and η. The number of iterations is set to be 50 for the proposed tracking strategy in these accuracy comparisons. In the simulation, the unknown node position is randomly selected from the intersection points of the grid, as illustrated in Figure 5.2.

In the simulation, ∆η varies from 0.004 to 0.04 with interval 0.004. As shown in Figure 5.9, the RMSE value of the proposed method is noticeably smaller than that of SDP and WLS. When ∆A varies from 0.1dB to 1.0dB with interval 0.1dB, the simulation results are shown in Figure 5.10. Similarly, the proposed method exhibits better performance than SDP and WLS. The simulation results show that SDP and WLS give low localization accuracy in case of parameter variation. In fact, the localization error increases with ∆η and ∆A, due to the increase in the estimated distance error. By inversing the channel model, the distance is estimated from (4.2). We can find that the estimated distance error increases with the increase of the variation of model parameters. So, the localization error also increases with ∆η and ∆A. Therefore, the SDP and WLS can not provide good localization accuracy when the model parameters are changed. On the contrary, the proposed tracking strategy can track the parameters firstly and then perform the localization by trilateration. Therefore, the proposed method can give a higher accuracy. tion time is evaluated by a computer with a processor unit (CPU) of 2.6 GHz and 16 GB of RAM. In the proposed method, the position is calculated by trilateration directly. So, the computational overhead is mainly due to the number of iterations in the tracking step. A larger iteration number will give a higher accuracy but more localization time. The relation between the tracking time and number of iterations is given in Table 5.2. It indicates that the tracking time increases with the number of iterations. Based on the observation of parameters convergence process, the number of iterations in the tracking step is set to 50 in the performance comparison. The calculation time for three compared methods is shown in Table 5.3. The average time for a single localization of the proposed method is 0.384s, while the corresponding values for SDP and WLS are 0.032s and 0.024s respectively. We can find that the proposed method requires more calculation time than SDP and WLS, due to the tracking step. More tracking iterations will cause more calculation time. The tradeoff between the localization accuracy and the calculation time can be made according to the performance requirement.

Tracking test

In the tracking test, a large number of measurements have been done in the indoor hall as shown in Figure 3.4. Firstly, the mobile point is placed at (5,5). Position (5,5) is considered as a reference point and 300 RSSI samples are acquired in this position. Based on these RSSI data, the acquired parameter values are  = -9.39 and η = 2.27. Hereafter, we placed the mobile point at positions (6, 5), [START_REF] Kopetz | Internet of things[END_REF]5) and [START_REF] Ian F Akyildiz | A survey on sensor networks[END_REF]5) and 300 RSSI values are acquired for each position. In the data collecting process, signal transmission path is changed by modifying the device direction or putting obstacles in the measurement scenario. Based on the acquired RSSI data for each position, the estimated positions and tracked parameters by the proposed method are given in Table 5.4. As shown in Table 5.4, for position [START_REF] Otto | System architecture of a wireless body area sensor network for ubiquitous health monitoring[END_REF]5), the estimated position is (6.12, 5.26). This estimated position meets the grid correction and tracking condition. By using LMS method, the tracked parameters are Ȧ = -9.35 and η = 2.26. Furthermore, similar results are obtained for positions [START_REF] Kopetz | Internet of things[END_REF]5) and [START_REF] Ian F Akyildiz | A survey on sensor networks[END_REF]5). These results show that the proposed tracking strategy can be effective. When the mobile point is moving from position [START_REF] Otto | System architecture of a wireless body area sensor network for ubiquitous health monitoring[END_REF]5) to position [START_REF] Ian F Akyildiz | A survey on sensor networks[END_REF]5), parameters A and η are changing. In this specific tracking test, the parameters variation is not very large. If the parameters are changing largely, the grid step size should be increased to guarantee the effectiveness of the proposed tracking strategy, as shown in section 5.5.

Conclusion

In this chapter, a localization scenario with predefined constrained positions has been described to show the applications of the proposed tracking strategy. To track the variation of channel parameters, a novel tracking strategy with grid correction based on LMS has been developed to obtain the actual parameters in the monitored indoor region. The experimental RSSI channel model has been used to provide the RSSI values and evaluate the tracking strategy. The localization algorithm based on the trilateration algorithm and LMS has been presented. The relationship between the localization accuracy and sample number of RSSI has been discussed. The simulation results show the good behavior of the proposed tracking strategy in presence of space-time variation of the propagation channel. To deal with the limitation of the proposed grid correction, the relationship between the grid step size and parameter variation has been analyzed. Compared with the existing SDP and WLS, the proposed tracking strategy exhibits better localization accuracy but higher computational complexity. Moreover, the tracking test allows validating the effectiveness of the proposed tracking strategy. In the following chapter, the thesis will be concluded and future works will be presented.

Conclusions and perspectives

In this thesis, we focus on RSSI based localization algorithms for indoor applications.

In Chapter 1, the concept and applications of WSNs are described, in addition the research direction, the contribution and the organization of the dissertation are described.

In Chapter 2, the state of the art for localization strategies is introduced. The localization approaches in WSNs are classified into two categories: extra modules aided approaches and extra modules free approaches. The localization means, such as, GPS method cellular network method, infrared device method, ultrasonic wave method, and micro inertial navigation method are introduced. The methods for measuring the angle or distance, including TOA, TDOA, RSSI and AOA, have been discussed. In addition, the positioning algorithms and optimization methods, such as Triangulation, Multilateration, Trilateration, linear least squares (LLS) , non linear least squares (NLS), projection onto convex sets (POCS) and semidefinite programming (SDP) are presented.

Channel model is elaborated in Chapter 3. The experimental channel model is deduced from RSSI data acquired by real localization system. An experimental localization system is built to get real RSSI data. From the observation of RSSI behavior, an experimental RSSI channel model is deduced, which is consistent to the popular 101 lognormal shadowing path loss model. Much more data are acquired to observe the relationship between the noise variance and distance. Based on the obtained data, it is indicated that the noise standard deviation increases with the distance. To confirm this tendency, a ray tracing system for an environment similar to the experimental environment is designed to simulate the receiving and transmitting process of RSSI data.

In Chapter 4, three proposed localization algorithms: Three minimum Distances Method (TDM), Weighted Three minimum distances Method (WTM) and Weight values Adjustment Method (WAM) based on NLS and multilateration are introduced. For getting a good performance, the median value of RSSI is used to obtain the distance estimate. Multilateration is adopted in the position process. The comparison of TDM, WTM, WAM, LLS, NLS and POCS, in terms of localization accuracy and calculation time, is presented.

To determine the real predefined position and obtain the actual parameters in the monitored region, a RSSI based parameter tracking strategy for constrained position localization is proposed in Chapter 5. To estimate channel model parameters, Least Mean Squares method (LMS) is associated with the trilateration method. Quantitative criteria are provided to guarantee the efficiency of the proposed tracking strategy by adjusting grid resolution according to parameter variation. The simulation results show a good behavior of the proposed tracking strategy in presence of space-time variation of the propagation channel. Compared with the existing SDP and WLS, the proposed tracking strategy exhibits better localization accuracy but higher computational complexity. Moreover, the tracking test validates the effectiveness of the proposed tracking strategy.

Finally, future work directions are listed as follows:

-A real localization scenario, not very different from the experimental setup, will be constructed to evaluate the proposed tracking strategy and localization algorithms. -In the tracking strategy, the grid can be replaced by other constraint, such as a map. -Joint techniques will be considered to increase the localization accuracy and reduce the calculation time. In the future, we will try to joint TOA, DOA and RSSI techniques together, such as exploring joint TOA/RSSI-based algorithm or joint DOA/RSSI-based algorithm, to get a better localization performance.

A Résumé en français des travaux présentés A.1 Introduction

Avec l'essor des standards de communications et les progrès d'intégration des systèmes électronique, les réseaux de capteurs sans fils peuvent être couramment déployés dans de nombreuses applications. Lorsque les noeuds du réseau sont mobiles, leur position doit être estimée car la mesure d'une donnée physique est le plus souvent associée à la localisation du capteur.

Pour répondre à cette problématique, cette thèse traite d'algorithmes de localisation basés sur la mesure du RSSI (Received Signal Strength Indicator) dans le contexte des réseaux de capteurs sans fil. L'étude des caractéristiques du RSSI à partir d'un système de localisation expérimental permet de construire un modèle nécessaire à la définition et à l'évaluation des algorithmes. Pour faire face à la faible précision des distances déduites du RSSI, nous proposons trois nouveaux algorithmes de localisation basés sur la multilatération et exploitant des mesures de RSSI moyennées. Ces algorithmes prennent en compte les distances mesurées en fonction de leur fiabilité supposée. Nous dévelop- Il est possible d'identifier les paramètres du modèle (A.1) à partir des mesures obtenues. Un résultat important est que la variance du bruit gaussien σ 2 augmente avec la distance. Cette caractéristique, déjà mise en évidence dans certains travaux, est également obtenue en utilisant un programme de tracé de rayons.

Cette propriété du bruit a une conséquence sur l'estimation des distances: la précision a tendance à diminuer quand la distance augmente. Nous prendrons en compte cette remarque dans la définition de nouveaux algorithmes de localisation exploitant le RSSI.

-La méthode TDM, sélectionne les trois plus faibles distances estimées.

-La méthode WTM sélectionne les trois plus faibles distances estimées et leur affecte des pondérations inversement proportionnelles au carré de la distance estimée et à la variance du bruit estimée. -La méthode WAM pondère toutes les distances estimées avec des pondérations identiques à la méthode WTM. L'étude comparées des performances de ces méthodes et de méthodes concurrentes de la littérature montre que la méthode WAM fournit les meilleures performances sans que la complexité des calculs ne soit affectée.

A.5 Stratégie de poursuite

Dans les méthodes présentées, la précision du modèle liant le RSSI aux distances est essentiel. Dans un environnement réel les paramètres de ce modèle vont varier de façon importante en fonction de l'environnement. Dans cette partie nous proposons, dans un premier temps, d'utiliser une technique d'estimation des paramètres du modèle basée sur l'algorithme LMS et la présence de noeuds de référence (dont la position est connue). Nous proposons ensuite de réaliser une poursuite du modèle en supposant que la position du mobile est contrainte par exemple sur une grille.

Le principe est illustré à la figure A.3.

-Au départ l'acquisition du modèle est effectuée sur un noeud de référence en utilisant un algorithme LMS -Après cette phase d'acquisition, les distances sont estimées en utilisant le modèle de RSSI courant. -L'algorithme de trilatération permet d'estimer la position.

-Cette estimation est corrigée en tenant compte de la contrainte de la grille.

-L'estimation corrigée est utilisée à l'entrée de l'algorithme LMS pour corriger le modèle de RSSI. La correction de l'estimation de position n'est possible que si l'erreur d'estimation initiale est inférieure à la résolution de la grille. Nous avons donc cherché la relation entre la variation des paramètres du modèle et l'erreur de position. On peut en déduire la résolution minimale de la grille admissible pour notre algorithme en fonction de l'environnement.

A.6 Conclusion

L'objectif du travail présenté était d'étudier des techniques de localisation basées sur la mesure du RSSI. Nous avons étudié expérimentalement les propriétés du RSSI et en avons déduit un modèle mettant en évidence le fait que la variance du bruit de mesure du RSSI augmente avec la distance. Nous avons montré que la variance de l'estimation de la distance était inversement proportionnelle au carré de la distance et à la variance du bruit de mesure. Nous avons proposé des algorithmes basés sur la multilatération et prenant en compte l'imprécision des distances déduites du RSSI. Nous nous sommes intéressés à du modèle de canal et à sa poursuite pour des scénarios d'application où les positions est contraintes. L'algorithme proposé a été testé sur des données réelles.

Figure 1 . 1 :

 11 Figure 1.1: Architecture of a typical wireless sensor networks.

Figure 1 . 2 :

 12 Figure 1.2: Application classification for WSNs

Figure 2 . 1 :

 21 Figure 2.1: Two steps of localization process

Figure 2 . 4 :

 24 Figure 2.4: Principle of APIT algorithm

Figure 2 . 5 :

 25 Figure 2.5: Diagram of tetrahedron algorithm

Figure 2 Figure 2 . 6 :

 226 Figure 2.6: Timing process of the two-way scheme

Figure 2 . 8 :

 28 Figure 2.8: Hardware configuration of TDOA

Figure 2 . 9 :

 29 Figure 2.9: Time delay computation model for TDOA

Figure 2 . 10 :

 210 Figure 2.10: Angle of arrival measurement.

Figure 2 .

 2 Figure 2.12: Trilateration

4 DFigure 2 . 14 :

 4214 Figure 2.14: Projection onto Convex Sets

Figure 3 . 1 :

 31 Figure 3.1: Typical sensor node architecture

Figure 3 . 2 :

 32 Figure 3.2: Raspberry Pi model A

Figure 3 . 3 :

 33 Figure 3.3: Raspberry Pi model B

Figure 3 . 5 :

 35 Figure 3.4: Measurement scenario

Figure 3 . 6 :

 36 Figure 3.6: Fitting relationship between percentage values and dBm

Figure 3 . 7 :

 37 Figure 3.7: Relationship of the measured RSSI values and distance

Figure 3 . 8 :

 38 Figure 3.8: Relationship of the noise standard deviation and distance for measured data

. 10 ,

 10 Figure 3.11, Figure 3.12 and Figure 3.13.

Figure 3 . 10 :Figure 3 . 11 :Figure 3 . 12 :Figure 3 . 13 :Figure 3 . 14 :

 310311312313314 Figure 3.10: Relationship of the simulated RSSI values and distance for case 1

Figure 3 . 15 :Figure 3 . 16 :Figure 3 . 17 :Figure 3 . 18 :Figure 3 . 19 :

 315316317318319 Figure 3.15: Relationship of the noise standard deviation and distance based on simulated data for case 1

Figure 4 . 1 :

 41 Figure 4.1: Relationship between σ 2 e and M for d k = 5.

Figure 4 . 2 :

 42 Figure 4.2: Relationship between σ 2 e and M for d k = 8.

Figure 4 . 3 :

 43 Figure 4.3: Location relationships of three circles in ideal and real conditions

Figure 4 . 4 :

 44 Figure 4.4: Grid defining the intersection positions and anchor nodes positions

Figure 4 . 5 :

 45 Figure 4.5: Localization results for three methods

Figure 5 . 1 :

 51 Figure 5.1: An application scenario about indoor environment with a set of devices in it

Figure 5 . 2 :

 52 Figure 5.2: Grid defining the possible positions

Figure 5 . 3 :

 53 Figure 5.3: Diagram of tracking principle

Figure 5 . 4 :Figure 5 . 5 :

 5455 Figure 5.4: Convergence process of η.

Figure 5 . 6 :

 56 Figure 5.6: Relationship of step size and localization error

Figure 5 . 7 :

 57 Figure 5.7: Relationship between ∆η and s

Figure 5 . 8 :

 58 Figure 5.8: Relationship between ∆A and s

Figure 5 . 9 :Figure 5 . 10 :

 59510 Figure 5.9: Localization accuracy for three compared methods when ∆η varies from 0.004 to 0.04.

Figure A. 1 :

 1 Figure A.1: Classification des méthodes de localisation

Figure A. 3 :

 3 Figure A.3: Algorithme de localisation incluant l'estimation du modèle et la poursuite

  is the distance between the transmitter and the receiver and v radio and v sound

	Transmitter	Receiver
	and where d Acoustic/ Ultrasound module RF module	t sound = t 0 + t delay + Acoustic/ d v sound Ultrasound module RF module	10) (2.11)

Table 3 . 1 :

 31 Comparison of sensor node platforms

	Name	Processor	RAM	Operating system	Cost ($)
	Raspberry Pi	ARM BCM2835	256-512 M	RASPBIAN	25-35
	MicaZ	ATMEGA128	4 K	TINY OS, MOTE RUNNER	99
	TelosB	TI MSP430	10 K	TINY OS, MANTISOS	99
	Iris	ATMEGA1281	8K	TINY OS, MOTE RUNNER	115
	Cricket	ATMEGA128L	4 K	TINY OS	225
	Lotus	ARM NXP LPC1758	64 K	RTOS, TINY OS

Table 3 .

 3

		2: Convertion relationship between percentage value and dBm by Cisco
	(%)	dBm (%)	dBm (%)	dBm (%)	dBm (%)	dBm
	0	-113	21	-91	42	-68	63	-44	84	-22
	1	-112	22	-90	43	-67	64	-44	85	-20
	2	-111	23	-89	44	-65	65	-43	86	-19
	3	-110	24	-88	45	-64	66	-42	87	-18
	4	-109	25	-87	46	-63	67	-42	88	-17
	5	-108	26	-86	47	-62	68	-41	89	-16
	6	-107	27	-85	48	-60	69	-40	90	-15
	7	-106	28	-84	49	-59	70	-39	91	-14
	8	-105	29	-83	50	-58	71	-38	92	-13
	9	-104	30	-82	51	-56	72	-37	93	-12
	10	-103	31	-81	52	-55	73	-35	94	-10
	11	-102	32	-80	53	-53	74	-34	95	-10
	11	-101	33	-79	54	-52	75	-33	96	-10
	13	-99	34	-78	55	-50	76	-32	97	-10
	14	-98	35	-77	56	-50	77	-30	98	-10
	15	-97	36	-75	57	-49	78	-29	99	-10
	16	-96	37	-74	58	-48	79	-28	100	-10
	17	-95	38	-73	59	-48	80	-27
	18	-94	39	-72	60	-47	81	-25
	19	-93	40	-70	61	-46	82	-24
	20	-92	41	-69	62	-45	83	-23

Table 3 .

 3

		4: Environment information for four cases
	Case	Length(m)	Width(m)	Height(m)	Obstacle number
	Case1	15	8	5	0
	Case2	30	10	5.5	0
	Case3	15	8	5	2
	Case4	30	10	5.5	2

Table 3 .

 3

	5: Different parameter values for four cases
	Case	A(dBm)	η
	Case1	-100.20	1.95
	Case2	-99.99	1.99
	Case3	-99.92	2.01
	Case4	-99.70	2.04

Table 4 .

 4 1: Simulation time for one localization process in milliseconds

	Anchor number	3	4	5	6	7	8
	LLS_ST	3	3	3	3	3	3
	NLS_ST	22	22	22	22	22	22
	POCS_ST	36	36	36	36	36	36
	TDM_ST	22	22	22	22	22	22
	WTM_ST	22	22	22	22	22	22
	WAM_ST	22	22	22	22	22	22

Table 5 .

 5 As illustrated in Table5.1, with the increase of sample number M , the RMSE values of localization algorithm decrease, which indicates that the accuracy of localization gets better. To guarantee the efficiency of the tracking strategy, in the following tracking step and simulations, the sample number M is set to 300.

		1: Localization accuracy
	Sample number M 30	50 200 300 500 1000
	RMSE (m)	0.78 0.56 0.33 0.25 0.14 0.10
	5.7 Parameter convergence

Table 5 . 2 :

 52 Relationship between tracking time and number of iterations

	Number of iterations	30	50	80	100	150	200	300
	Tracking time (s)	0.205 0.382 0.617 0.846 1.287 2.133 2.907

Table 5 .

 5

	3: Calculation time for three compared methods
	Method	Proposed method SDP WLS
	Average time (s)	0.384	0.032 0.024

Table 5 .

 5

	4: Localization results and tracked parameters
	Real position Estimated position	Ȧ	η
	(6, 5)	(6.12, 5.26)	-9.35 2.26
	(7, 5)	(6.98, 5.13)	-9.41 2.28
	(8, 5)	(8.20, 5.08)	-9.32 2.25

In classical radar systems the angle of arrival is determined by a rotary antenna.

Acknowledgments

RSSI channel model

In this thesis, we have chosen the RSSI based localization methods due to the following reasons:

(1) Most of the wireless communications networks provide a straightforward access to the RSSI values, which has made the RSSI-based localization one of the most attractive network-based localization approaches.

(2) The advantage of the RSSI-based localization is that it can be implemented easily on low-cost, battery-powered nodes with small memory size and low processing capabilities.

As seen in the previous chapter, some localization algorithms estimate the distances based on RSSI channel model. It is essential to construct an accurate RSSI channel model in practical application. In this chapter, the theoretical channel model for distance estimation will be discussed. To characterize RSSI channel model, an experimental localization system is designed. Based on the acquired RSSI data, an experimental channel model is deduced. pons également une stratégie d'acquisition et de suivi des paramètres du canal pour la localisation dans les applications où la position est contrainte.

A.2 Etat de l'art des méthodes de localisation pour les réseaux de capteurs L'objectif d'une méthode de localisation est de déterminer la position d'un objet dans une zone d'intérêt. Les exigences en terme de précision dépendent de l'application. Certaines ne nécessitent qu'une précision relativement faible (présence dans une pièce par exemple). Dans ce cas il existe des méthodes de proximité, des approches utilisant les relais du système de communication ou des méthodes par enregistrement d'empreintes (finger printing).

Pour les applications nécessitant une meilleure précision, la figure A.2 propose une classification des méthodes disponibles. Certaines approches sont basées sur des dispositifs spécifiques, d'autres utilisent des équipements déjà présents, comme les fonctions de communication.

Dans le document complet, nous décrivons de façon succincte le principe de ces méthodes. Celles exploitant le RSSI sont présentées en incluant les algorithmes basés sur un modèle du canal et ceux utilisant des empreintes.

Le RSSI est disponible dans la plupart des modules de communications radio. Il est donc intéressant d'exploiter cette information pour concevoir une méthode de localisation à moindre coût. C'est la raison pour laquelle nous avons basé nos travaux sur les méthodes de localisation utilisant le RSSI.

A.3 Caractérisation et modélisation du RSSI

Les méthodes de localisation basées sur le RSSI (hors Fingerprint) nécessitent un modèle permettant de déduire la distance de la puissance reçue. Le modèle couramment proposé dans la littérature s'écrit : Les méthodes de localisation proposées sont basées sur la multilatération et prennent la forme suivante:

où x k , y k et dk sont les positions et la distance estimée de la base k, N est le nombre de bases. Les pondérations α k sont différents en fonction de la méthode.

List of Figures

Thèse de Doctorat

Abstract

In this thesis, the author focused on RSSI based localization algorithms for indoor applications in wireless sensor networks. Firstly, from the observation of RSSI behavior based on an experimental localization system, an experimental RSSI channel model is deduced, which is consistent to the popular lognormal shadowing path loss model. Secondly, this thesis proposes three indoor localization algorithms based on multilateration and averaged RSSI. In these algorithms, the measured distances are weighted according to their assumed accuracy. Lastly, a RSSI based parameter tracking strategy for constrained position localization is proposed. To estimate channel model parameters, least mean squares method (LMS) is associated with the trilateration method. Quantitative criteria are provided to guarantee the efficiency of the proposed tracking strategy by providing a tradeoff between the constraint resolution and parameter variation. The simulation results show a good behavior of the proposed tracking strategy in presence of space-time variation of the propagation channel. Compared with the existing RSSI based algorithms, the proposed tracking strategy exhibits better localization accuracy but consumes more calculation time. In addition, experimental tracking test is performed to validate the effectiveness of the proposed tracking strategy.