Techniques in Localization

Techniques in Localization

Ms. Asha B C Mr. Chetan Shetty

Dept of CSE Asst Prof, Dept of CSE SJBIT, Bangalore SJBIT, Bangalore

asha.b.chandru@gmail.com chetanshetty1986@gmail.com

Abstract-Localization systems have become very popular in recent years. These systems have been successfully used in many applications such as asset tracking and inventory management. Localization is of great importance for a range of pervasive applications, attracting many research efforts in the past two decades. Pervasive and mobile systems for context- aware computing are growing at a phenomenal rate. In most of todays applications such as pervasive Medicare, smart space, wireless sensor surveillance, mobile peer-to-peer computing etc., location is one of the most essential contexts. Pervasive computing, wireless indoor localization has been extensively studied and many solutions are proposed to provide room-level localization services, such as locating a person or a printer in an office building. Wireless information access is now widely available; there is a high demand for accurate positioning in wireless networks, including indoor. This paper presents the different types of localization techniques and the survey of the Wireless indoor Localization techniques and systems.

I INTRODUCTION

Wireless information access is now widely available; there is a high demand for accurate positioning in wireless networks, including indoor and outdoor environments. The process of determining a location is called location sensing, geo location, position location, or radiolocation, if it uses wireless technologies such as Wi-Fi, Bluetooth, Ultra Sound, and FM Signals. A growing number of mobile computing applications are centered on the users location. Numerous localization solutions based on Bluetooth, ultrasound and infrared technologies have been proposed.

1. Fingerprint based Localization

   Large body of indoor localization approaches adopts fingerprint matching as the basic scheme of location determination. The main idea is to fingerprint the surrounding signatures at every location in the areas of interests and then build a fingerprint database. The location is then estimated by mapping the measured fingerprints against the database. Researchers have striven to exploit different signatures of the existing devices or reduce the mapping effort. Most of these techniques utilize the RF signals. Fingerprint based localization is divided into two phases:

   1. Training

      In this phase, engineers record the Received Signal Strength (RSS) fingerprints (e.g., WiFi signal strengths from multiple Access Points, APs) at every position of an interesting area and accordingly build a fingerprint database.

   2. Serving

   In the serving phase, when a user sends a location query with its current RSS fingerprint, localization algorithms retrieve the fingerprint database and return the matched fingerprints as well as corresponding locations. Collecting the values from various base stations is called fingerprint for that location. Matching the observed RSS value with measured RSS value is called fingerprinting.

2. Model based Localization

Another type of localization approaches use geometrical models to figure out locations. In those methods, locations are calculated rather than searched from known reference data. For example, the log-distance path loss (LDPL) model is used to estimate RF propagation distances according to the measured RSS values.

Geometric models are also exploited for characterizing the relationship of signal transmitters and receivers. Wireless indoor positioning systems have become very popular in recent years. These systems have been successfully used in many applications such as asset tracking and inventory management.

The rest of the paper is organized as follows: section 1 contains the WILL: wireless indoor localization without site survey. Section 2 and 3 contains the GSM and Sound sense Localization and their architecture. Section 4 contains the survey on indoor localization. Section 5 contains the localization on Wireless sensor networks using the moving beacons.

II WILL: WIRELESS INDOOR LOCALIZATION WITHOUT SITE SURVEY

This is a based on fingerprinting Localization but without using the site survey. Site survey involves intensive cost on manpower and time. Here we are studying unexploited RF signal characteristics and leverage user motions to construct radio floor plan that is previously obtained by site survey. On this

Fig. 1: Abrupt signal changes through a wall. AP1 is deployed in Room I and AP2 in an adjacent Room II.

basis, we design WILL, an indoor localization approach based on off-theshelf WiFi infrastructure and mobile phones. WILL is deployed in a real building covering over 1600m2, and its deployment is easy and rapid since site survey is no longer needed.

1. Overview

   WiFi technology has shown its great potentials for ubiquitous localization as it is available in a large amount of buildings through personal electronic devices like mobile phones and laptops. By investigating the temporal and spatial characteristics of indoor RF propagation of WiFi signals, we discover some easily overlooked but dramatically useful characteristics. A key observation is that signals may encounter a considerable drop while passing through a wall (as shown in Fig. 1). As a result, RSS of a same AP can vary significantly in two rooms. People have been observing this wall-penetrating effect of radio signals when using wireless routers in everyday life. Such characteristic, however, has not been fully exploited for positioning. As shown in Fig. 1, this variation of AP signal strength can be used to distinguish different rooms.

   On the other hand, smart phones integrate various types of sensors such as accelerometer, magnetometer, gyroscope, etc., offering new opportunities to capture environment signatures and to detect user behaviours. WILL exploits accelerometers to obtain user movements, which will be further utilized to assist localization. Tri-axial accelerometers provide apparent evidence of human walking patterns. As illustrated in Fig. 2, the acceleration variation for walking users is clearly different from those static. Amplitude of about 2m/s2 is caused by foot lifting and around 3m/s2 by foot down. This signature is deeply explored in WILL to detect user motions and collect user traces.

   Fig. 2: Acceleration signatures of 10 steps (each step marked with a cross).

   WILL provides human localization service through locating mobile phones. Even though mobile phones can integrate sensors like compasses, cameras, microphones, gyroscopes, WILL uses only accelerometers since no human participation is involved for such sensors. Moreover, different from many previous work using accelerometers for step counting or displacement estimation, WILL utilizes accelerometer sensors to explore reachability between different areas.

2. WILL Architecture

During the training phase (database construction), users in a building work with routine business while their mobile phones automatically measure WiFi signal strengths and record accelerometer readings.

Raw data are collected in the fingerprint collection module on the mobile phone side. All raw fingerprints (not tagged with a known location) are pre-processed in fingerprint processing module and divided into two types: space-continuous and space-discontinuous, according to users motion states when the fingerprints are measured. Both types of fingerprints are classified into differnt virtual rooms, which are virtual containers of fingerprints with high similarity.

A logical floor plan showing a view of relative location relationship (e.g., connectivity and reachability) between virtual rooms is then constructed by leveraging user trace information from the space-continuous data, which connect previously independent fingerprints. Afterwards, the logical floor plan is mapped to a given ground truth one by using a novel mapping method. By doing so, we associate the isolated fingerprints with physical rooms. Floor plan database stores these associated relationships. In the serving phase, when a user sends a location query with his/her currently measured data using mobile phone, WILL server will response the user with the estimated location.

Fig. 3: WILL architecture.

The query may contain a variety of information, including WiFi measurements and sensory data. The localization engine consults the fingerprint database to localize the virtual room and then obtains the corresponding physical room from floor plan database. The location estimation and, if possible, the floor plan that the user currently locates at are sent back to the user. The querying data can be simultaneously used as collected fingerprints to update the databases.

III GSM INDOOR LOCALIZATION

GSM is fingerprint based indoor localization technique. The key idea that makes accurate GSM based indoor localization possible is the use of wide signal-strength fingerprints. The wide fingerprint includes the 6-strongest GSM cells and readings of up to 29 additional GSM channels, most of which are strong enough to be detected, but too weak to be used for efficient communication. The higher dimensionality introduced by the additional channels dramatically increases localization accuracy.

GSM-based indoor localization has several benefits: (i) GSM coverage far exceeds the coverage of

802.11 networks; (ii) the wide acceptance of cellular phones makes them ideal conduits for the delivery of ubiquitous computing applications. A localization system based on cellular signals, such as GSM, leverages the phones existing hardware and removes the need for additional radio interfaces; (iii) because cellular towers are dispersed across the covered area, a cellular-based localization system would still work in situations where a buildings electrical infrastructure has failed. Moreover, cellular systems are designed to tolerate power failures. (iv) GSM, unlike 802.11 networks, operates in a licensed band, and therefore does not suffer from interference from nearby devices transmitting on the same frequency (e.g., microwaves, cordless phones); and (v) the significant expense and complexity of cellular base stations1 result in a network that evolves slowly and is only reconfigured infrequently.

1. WIRELESS INDOOR POSITIONING TECHNIQUES

   1. Different types of location information

      1. Symbolic Location: Symbolic location expresses a location in a natural-language way, such as in the office, in the third-floor bedroom, etc.

      2. Absolute Location: Absolute location uses a shared reference grid for all located objects.

      3. Relative Location: Relative location depends on its own frame of reference. Relative location information is usually based on the proximity to known reference points or base stations.

      Various wireless technologies are used for wireless indoor location. These may be classified based on:

      • The location positioning algorithm, i.e., the method of determining location, making use of various types of measurement of the signal such as Time Of Flight (TOF), angle, and signal strength;

      • The physical layer or location sensor infrastructure, i.e., the wireless technology used to communicate with the mobile devices or static devices. In general, measurement involves the transmission and reception of signals between hardware components of the system.

      An indoor wireless positioning system consists of at least two separate hardware components: a signal transmitter and a measuring unit. The latter usually carries the major part of the system intelligence.

   2. Different system topologies for positioning system

      1. Remote positioning system: The first one is the remote positioning system; whose signal transmitter is mobile and several fixed measuring units receive the transmitters signal. The results from all measuring units are collected, and the location of the transmitter is computed in a master station.

      2. Self positioning System: The second is self-positioning in which the measuring unit is mobile. This unit receives the signals of several transmitters in known locations, and has the capability to compute its location based on the measured signals.

      3. Indirect Remote positioning system: If the wireless data link is provided in a positioning system, it is possible to send the measurement result from a self-positioning measuring unit to the remote side, and this is called indirect remote positioning, which is the third system topology.

      4. Indirect Self positioning System: If the measurement result is sent from a remote positioning side to a mobile unit via a wireless data link, this case is named indirect self positioning, which is the fourth system topology.

      Fig 4: Positioning based on AOA measurement.

   3. Measurement principle and positioning

   It is not easy to model the radio propagation in the indoor environment because of severe multipath, low probability for availability of line-of-sight (LOS) path, and specific site

   parameters such as floor layout, moving objects, and numerous reflecting surfaces. There is no good model for indoor radio multipath characteristic so far. Except using traditional triangulation, positioning algorithms using scene analysis or proximity are developed to mitigate the measurement errors. Targeting different applications or services, these three algorithms have unique advantages and disadvantages. Hence, using more than one type of positioning algorithms at the same time could get better performance.

   1. Triangulation

      Triangulation uses the geometric properties of triangles to estimate the target location. It has two derivations: lateration and angulation.

      Angle of Arrival (AOA):

      In AOA, the location of the desired target can be found by the intersection of several pairs of angle direction lines, each formed by the circular radius from a base station or a beacon station to the mobile target. As shown in Fig. 4, AOA methods may use at least two known reference points (A, B), and two measured angles 1, 2 to derive the 2-D location of the target P. Estimation of AOA, commonly referred to as direction finding (DF), can be accomplished either with directional antennae or with an array of antennae. The advantages of AOA are that a position estimate may be determined with as few as three measuring units for 3-D positioning or two measuring units for 2-D positioning, and that no time synchronization between measuring units is required.

      The disadvantages include relatively large and complex hardware requirement(s), and location estimate degradation as the mobile target moves farther from the measuring units. For accurate positioning, the angle measurements need to be accurate, but the high accuracy measurements in wireless networks may be limited by shadowing, by multipath reflections arriving from misleading directions, or by the directivity of the measuring

      Fig. 5: Positioning based on TOA/RTOF measurements.

      aperture. Some literatures also call AOA as direction of arrival (DOA).

   2. Trilateration:

   Trilateration estimates the position of an object by measuring its distances from multiple reference points. So, it is also called range measurement techniques.

   Instead of measuring the distance directly using received signal strengths (RSS), time of arrival (TOA) or time difference of arrval (TDOA) is usually measured, and

   the distance is derived by computing the attenuation of the emitted signal strength or by multiplying the radio signal velocity and the travel time. Roundtrip time of flight (RTOF) or received signal phase method is also used for range estimation in some systems. Angulation locates an object by computing angles relative to multiple reference points. In this survey, we focus on the aforementioned measurements in the shorter range, low-antenna, and indoor environment.

   Time Of Arrival (TOA):

   The distance from the mobile target to the measuring unit is directly proportional to the propagation time. In order to enable 2-D positioning, TOA measurements must be made with respect to signals from at least three reference points, as shown in Fig. 5.

   For TOA-based systems, the one-way propagation time is measured, and the distance between measuring unit and signal transmitter is calculated. In general, direct TOA results in two problems. First, all transmitters and receivers in the system have to be precisely synchronized. Second, a timestamp must be labelled in the transmitting signal in order for the measuring unit to discern the distance the signal has travelled. TOA can be measured using different signaling techniques such as direct sequence spread- spectrum (DSSS) or ultrawide band (UWB) measurements.

   Time Difference of Arrival (TDOA)

   The idea of TDOA is to determine the relative position of the mobile transmitter by examining the difference in time at which the signal arrives at multiple measuring units, rather than the absolute arrival time of TOA.

   Fig 6: Positioning based on TDOA measurements.

   For each TDOA measurement, the transmitter must lie on a hyperboloid with a constant range difference between the two measuring units. A 2-D target location can be estimated from the two intersections of two or more TDOA measurements, as shown in Fig. 6. Two hyperbolas are formed from TDOA measurements at three fixed measuring units (A, B, and C) to provide an intersection point, which locates the target P.

2. CONCLUSION

This paper presents WILL, an indoor logical localization approach without site survey of AP locations and power settings. The main idea is to combine WiFi fingerprints with user movements. Fingerprints are partitioned into different virtual rooms and a logical floor plan. Localization is achieved by finding a matching between logical and ground truth floor plan. We implement WILL in a typical office

building and it achieves an average room-level accuracy of 86%, which is competitive to existing designs. We believe WILL demonstrates its advantage on low human cost, a long-standing and universal will in wireless indoor localization.

This paper demonstrated that accurate indoor GSM-based localization system identified the floor correctly in up to 60% of the cases and is within 2 floors in 98% of the cases. Our system is robust; it works for different network operators.

Survey of wireless indoor positioning techniques and systems surveys the current indoor positioning techniques and systems. In terms of scalability and availability, these positioning techniques and systems have their own important characteristics when applied in real environments.

REFERENCES

1. B. Xiao, H. Chen, and S. Zhou, Distributed localization using a moving beacon in wireless sensor networks, IEEE Trans.Parallel Distrib. Syst., vol. 19, no. 5, pp. 587600, May 2008.

2. A. Varshavsky, E. de Lara, J. Hightower, A. LaMarca, and V. Otsason, GSM indoor localization, Proceedings of the 5th IEEE Annual Conference on Pervasive Computing and Communications,vol. 3, no. 6, p. 698C720, 2007.

3. C. Wu, Z. Yang, Y. Liu, and W. Xi, WILL: Wireless indoor localization without site survey, in INFOCOM, 2012 Proceedings IEEE, march 2012, pp. 6472.

4. Chenshu Wu, Zheng Yang, Yunhao Liu, and Wei Xi, WILL: Wireless Indoor Localization Without Site Survey in transactions on parallel and distributed systems, vol. x, no. x, february 2012.

5. T. He, C. Huang, B.M. Blum, J.A. Stankovic, and T. Abdelzaher, Range-Free Localization Schemes for Large-Scale Sensor Networks, Proc. ACM MobiCom 03, pp. 81-95, 2003.

6. B. Xiao, H. Chen, and S. Zhou, A Walking Beacon-Assisted Localization in Wireless Sensor Networks, Proc. IEEE Intl Conf. Comm. (ICC 07), pp. 3070-3075, June 2007.

7. N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller, Mobile- Assisted Localization in Wireless Sensor Networks, Proc. IEEE INFOCOM 05, Mar. 2005.

8. A. Brooks, A.Makarenko, T. Kaupp, S.Williams, and H. Durrant- Whyte, Implementation of an indoor active sensor network, in Proc. 9th Int. Symp. Exp. Robot. 2004, Singapore, Jun.1821, 2004, pp. 37 46.

9. C. Savarese, J. M. Rabaey, and J. Beutel, Locationing in distributed ad-hoc wireless sensor networks, in Proc. IEEE ICASSP, May 2001, pp. 20372040.

10. ZigBeeTMAlliance. (2004, Dec.). Network specification version 1.0.Tech. Rep. 02130r10 [Online]. Available: http://www.zigbee.org

11. N. Patwari, A. O. Hero, M. Perkins, N. S. Correal, and R. J. ODea, Relative location estimation in wireless sensor networks, IEEE Trans. Signal Process., vol. 51, no. 8, pp. 21372148, Aug. 2003.