Liu Y,Yang Z,Wang X et al.Location,localization,and localizability.JOURNAL OF COMPUTER SCIENCE AND TECHNOL0GY25(2):274-297Mar.2010 Location,Localization,and Localizability Yunhao Liu(刘云浩)，Member,.ACM,Senior Member,IEEE.Zheng Yang(杨铮)，Student Member,.ACM.IEEE Xiaoping Wang(王小平)，Student Member,IEEE,and Lirong Jian(简丽荣)，Student Member,,IEEE Department of Computer Science and Engineering,Hong Kong University of Science and Technology,Hong Kong,China E-mail:fliu,yangzh,xiaopingwang,jlrphx@cse.ust.hk Received October 28,2009;revised January 6,2010. Abstract Location-aware technology spawns numerous unforeseen pervasive applications in a wide range of living,pro- duction,commence,and public services.This article provides an overview of the location,localization,and localizability issues of wireless ad-hoc and sensor networks.Making data geographically meaningful,location information is essential for many applications,and it deeply aids a number of network functions,such as network routing,topology control,coverage, boundary detection,clustering,etc.We investigate a large body of existing localization approaches with focuses on error control and network localizability,the two rising aspects that attract significant research interests in recent years.Error control aims to alleviate the negative impact of noisy ranging measurement and the error accumulation effect during coope- rative localization process.Network localizability provides theoretical analysis on the performance of localization approaches, providing guidance on network configuration and adjustment.We emphasize the basic principles of localization to under- stand the state-of-the-art and to address directions of future research in the new and largely open areas of location-aware technologies. Keywords location-based services (LBS),localization,error control,localizability,wireless ad-hoc and sensor networks Location Indoor (Local) Indoor/Outdoor Outdoor(Global) Bluetooth GSM (2G) The proliferation of wireless and mobile devices has UWB WiFi ZigBee GPS fostered the demand for context-aware applications,in Intrared UMTS(3G) which location is viewed as one of the most signifi- Personal Wireless Wireles Telecommu Area Satellite cant contexts.For example,pervasive medical care WLAN Ad-H 15 nication Based Networks Nerwork Networks Nenworks is designed to accurately record and manage patient movements1-21;smart space enables the interaction be- Location-Based Services (LBS) tween physical space and human activities3-4;mod- ern logistics has major concerns on goods transporta- Fig.1.Location-based services for a wide range of wireless net- tion,inventory,and warehousing-6;environmental works. monitoring networks sense air,water,and soil quality and detect the source of pollutants in real timel7-11j. becomes critically essential and indispensable.The and mobile peer-to-peer computing encourages content overwhelming reason is that WSNs are fundamentally sharing and contributing among mobile hosts in the intended to provide information on spatial-temporal vicinity[12-13).In brief,location-based service (LBS) characteristics of the physical world;hence,it is impor- is a key enabling technology of these applications and tant to associate sensed data with locations,making widely exists in nowadays wireless communication net- data geographically meaningful.For example,a num- works from the short-range Bluetooth to the long-range ber of applications,such as object tracking and environ- telecommunication networks,as illustrated in Fig.1. ment monitoring,inherently rely on location informa- Recent technological advances have enabled the de- tion.A detailed survey on location-based applications velopment of low-cost,low-power,and multifunctional can be found in14-15. sensor devices.These nodes are autonomous devices Location information also supports many fundamen- with integrated sensing,processing,and communi- tal network services,including network routing,topol- cation capabilities.With the rapid development of ogy control,coverage,boundary detection,clustering, wireless sensor networks (WSNs).location information etc.We give a brief overview as follows. Survey C)2010 Springer Science+Business Media,LLC Science Press,China
Liu Y, Yang Z, Wang X et al. Location, localization, and localizability. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 25(2): 274–297 Mar. 2010 Location, Localization, and Localizability Yunhao Liu (刘云浩), Member, ACM, Senior Member, IEEE, Zheng Yang (杨 铮), Student Member, ACM, IEEE Xiaoping Wang (王小平), Student Member, IEEE, and Lirong Jian (简丽荣), Student Member, IEEE Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong, China E-mail: {liu, yangzh, xiaopingwang, jlrphx}@cse.ust.hk Received October 28, 2009; revised January 6, 2010. Abstract Location-aware technology spawns numerous unforeseen pervasive applications in a wide range of living, production, commence, and public services. This article provides an overview of the location, localization, and localizability issues of wireless ad-hoc and sensor networks. Making data geographically meaningful, location information is essential for many applications, and it deeply aids a number of network functions, such as network routing, topology control, coverage, boundary detection, clustering, etc. We investigate a large body of existing localization approaches with focuses on error control and network localizability, the two rising aspects that attract significant research interests in recent years. Error control aims to alleviate the negative impact of noisy ranging measurement and the error accumulation effect during cooperative localization process. Network localizability provides theoretical analysis on the performance of localization approaches, providing guidance on network configuration and adjustment. We emphasize the basic principles of localization to understand the state-of-the-art and to address directions of future research in the new and largely open areas of location-aware technologies. Keywords location-based services (LBS), localization, error control, localizability, wireless ad-hoc and sensor networks 1 Location The proliferation of wireless and mobile devices has fostered the demand for context-aware applications, in which location is viewed as one of the most signifi- cant contexts. For example, pervasive medical care is designed to accurately record and manage patient movements[1-2]; smart space enables the interaction between physical space and human activities[3-4]; modern logistics has major concerns on goods transportation, inventory, and warehousing[5-6]; environmental monitoring networks sense air, water, and soil quality and detect the source of pollutants in real time[7-11]; and mobile peer-to-peer computing encourages content sharing and contributing among mobile hosts in the vicinity[12-13]. In brief, location-based service (LBS) is a key enabling technology of these applications and widely exists in nowadays wireless communication networks from the short-range Bluetooth to the long-range telecommunication networks, as illustrated in Fig.1. Recent technological advances have enabled the development of low-cost, low-power, and multifunctional sensor devices. These nodes are autonomous devices with integrated sensing, processing, and communication capabilities. With the rapid development of wireless sensor networks (WSNs), location information Fig.1. Location-based services for a wide range of wireless networks. becomes critically essential and indispensable. The overwhelming reason is that WSNs are fundamentally intended to provide information on spatial-temporal characteristics of the physical world; hence, it is important to associate sensed data with locations, making data geographically meaningful. For example, a number of applications, such as object tracking and environment monitoring, inherently rely on location information. A detailed survey on location-based applications can be found in [14-15]. Location information also supports many fundamental network services, including network routing, topology control, coverage, boundary detection, clustering, etc. We give a brief overview as follows. Survey ©2010 Springer Science + Business Media, LLC & Science Press, China
Yunhao Liu et al:Location,Localization,and Localizability 275 ·Routing Clustering brings numerous advantages on network op- Routing is a process of selecting paths in a net- erations,such as improving network scalability,local- work along which to send data traffic.Most routing izing the information exchange,stabilizing the network protocols for multi-hop wireless networks utilize physi- topology,and increasing network life time.Among all cal locations to construct forwarding tables and deliver possible solutions,location-based clustering approaches messages to the node closer to the destination in each are greatly efficient by generating non-overlapped clus- hop[16).Specifically,when a node receives a message, ters.In addition.location information can also be used local forwarding decisions are made according to the to rebuild clusters locally when new nodes join the net- positions of the destination and its neighboring nodes. work or some nodes suffer from hardware failurel24). Such geographic routing schemes require localized infor- mation,making the routing process stateless,scalable, 2 Localization and low-overhead in terms of route discovery. Network localization has attracted a lot of research ·Topology Control efforts in recent years.One method to determine the Topology control is one of the most important tech- location of a device is through manual configuration, niques used in wireless ad-hoc and sensor networks for which is often infeasible for large-scale deployments or saving energy and eliminating radio interferencel17-181. mobile systems.As a popular system,Global Position- By adjusting network parameters (e.g.,the transmit- ing System(GPS)is not suitable for indoor or under- ting range),energy consumption and interference can ground environments and suffers from high hardware be effectively reduced;meanwhile some global net- cost.Local Positioning Systems (LPS)rely on high- work properties (e.g.,connectivity)can still be well density base stations being deployed,an expensive bur- retained.Importantly,using location information as den for most resource-constrained wireless ad hoc net- a priori knowledge,geometry techniques (e.g.,spanner works. subgraphs and Euclidean minimum spanning trees)can be immediately applied to topology controll7l. The limitations of existing positioning systems mo- tivate a novel scheme of network localization.in which ·Coverage some special nodes (a.k.a.anchors or beacons)know Coverage reflects how well a sensor network observes their global locations and the rest determine their loca- the physical space;thus,it can be viewed as the quali- tions by measuring the geographic information of their ty of service (QoS)of the sensing function.Previ- local neighboring nodes.Such a localization scheme for ous designs fall into two categories.The probabilistic wireless multi-hop networks is alternatively described approaches]analyze the node density for ensuring as“cooperative'”,“ad-hoc”,“in-network localization” appropriate coverage statistically,but essentially have or"self localization",since network nodes cooperatively no guarantee on the result.In contrast,the geometric determine their locations by information sharing. approaches22]are able to obtain accurate and reliable In this section,we first review the state-of-the-art lo- results,in which locations are essential. calization approaches from two aspects:physical mea- ●Boundary Detection surements and network-wide localization algorithms. Boundary detection is to figure out the overall We then discuss a number of techniques for controlling boundary of an area monitored by a WSN.There are localization errors caused by noisy physical measure- two kinds of boundaries:the outer boundary showing ments and algorithmic defects. the under-sensed area,and the inner boundary indica- Almost all existing localization algorithms consist of ting holes in a network deployment.The knowledge of two stages:1)measuring geographic information from boundary facilitates the design of routing,load balanc- the ground truth of network deployment;2)computing ing,and network management23).As direct evidence, node locations according to the measured data.Geo- location information helps to identify border nodes and graphic information includes a variety of geometric re- further depict the network boundary. lationships from coarse-grained neighbor-awareness to ·Clustering fine-grained inter-node rangings (e.g.,distance or an- To facilitate network management,researchers of- gle).Based on physical measurements,localization al- ten propose to group sensor nodes into clusters and gorithms solve the problem that how the location infor- organize nodes hierarchically24.In general,ordinary mation from beacon nodes spreads network-wide.Gen- nodes only talk to the nodes within the same cluster, erally,the design of localization algorithms largely de- and the inter-cluster communications rely on a special pends on a wide range of factors,including resource node in each cluster.which is often called cluster head. availability,accuracy requirements,and deployment re- Cluster heads form a backbone of a network,based strictions;and no particular algorithm is an absolute on which the network-wide connectivity is maintained favorite across the spectrum
Yunhao Liu et al.: Location, Localization, and Localizability 275 • Routing Routing is a process of selecting paths in a network along which to send data traffic. Most routing protocols for multi-hop wireless networks utilize physical locations to construct forwarding tables and deliver messages to the node closer to the destination in each hop[16]. Specifically, when a node receives a message, local forwarding decisions are made according to the positions of the destination and its neighboring nodes. Such geographic routing schemes require localized information, making the routing process stateless, scalable, and low-overhead in terms of route discovery. • Topology Control Topology control is one of the most important techniques used in wireless ad-hoc and sensor networks for saving energy and eliminating radio interference[17-18] . By adjusting network parameters (e.g., the transmitting range), energy consumption and interference can be effectively reduced; meanwhile some global network properties (e.g., connectivity) can still be well retained. Importantly, using location information as a priori knowledge, geometry techniques (e.g., spanner subgraphs and Euclidean minimum spanning trees) can be immediately applied to topology control[17] . • Coverage Coverage reflects how well a sensor network observes the physical space; thus, it can be viewed as the quality of service (QoS) of the sensing function. Previous designs fall into two categories. The probabilistic approaches[19-21] analyze the node density for ensuring appropriate coverage statistically, but essentially have no guarantee on the result. In contrast, the geometric approaches[22] are able to obtain accurate and reliable results, in which locations are essential. • Boundary Detection Boundary detection is to figure out the overall boundary of an area monitored by a WSN. There are two kinds of boundaries: the outer boundary showing the under-sensed area, and the inner boundary indicating holes in a network deployment. The knowledge of boundary facilitates the design of routing, load balancing, and network management[23]. As direct evidence, location information helps to identify border nodes and further depict the network boundary. • Clustering To facilitate network management, researchers often propose to group sensor nodes into clusters and organize nodes hierarchically[24]. In general, ordinary nodes only talk to the nodes within the same cluster, and the inter-cluster communications rely on a special node in each cluster, which is often called cluster head. Cluster heads form a backbone of a network, based on which the network-wide connectivity is maintained. Clustering brings numerous advantages on network operations, such as improving network scalability, localizing the information exchange, stabilizing the network topology, and increasing network life time. Among all possible solutions, location-based clustering approaches are greatly efficient by generating non-overlapped clusters. In addition, location information can also be used to rebuild clusters locally when new nodes join the network or some nodes suffer from hardware failure[24] . 2 Localization Network localization has attracted a lot of research efforts in recent years. One method to determine the location of a device is through manual configuration, which is often infeasible for large-scale deployments or mobile systems. As a popular system, Global Positioning System (GPS) is not suitable for indoor or underground environments and suffers from high hardware cost. Local Positioning Systems (LPS) rely on highdensity base stations being deployed, an expensive burden for most resource-constrained wireless ad hoc networks. The limitations of existing positioning systems motivate a novel scheme of network localization, in which some special nodes (a.k.a. anchors or beacons) know their global locations and the rest determine their locations by measuring the geographic information of their local neighboring nodes. Such a localization scheme for wireless multi-hop networks is alternatively described as “cooperative”, “ad-hoc”, “in-network localization”, or “self localization”, since network nodes cooperatively determine their locations by information sharing. In this section, we first review the state-of-the-art localization approaches from two aspects: physical measurements and network-wide localization algorithms. We then discuss a number of techniques for controlling localization errors caused by noisy physical measurements and algorithmic defects. Almost all existing localization algorithms consist of two stages: 1) measuring geographic information from the ground truth of network deployment; 2) computing node locations according to the measured data. Geographic information includes a variety of geometric relationships from coarse-grained neighbor-awareness to fine-grained inter-node rangings (e.g., distance or angle). Based on physical measurements, localization algorithms solve the problem that how the location information from beacon nodes spreads network-wide. Generally, the design of localization algorithms largely depends on a wide range of factors, including resource availability, accuracy requirements, and deployment restrictions; and no particular algorithm is an absolute favorite across the spectrum
276 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 2.1 Physical Measurements and Single-Hop The least squares method is used to assign a value to Positioning (o y)that minimizes This problem can be solved by a numerical solution to an over-determined Clearly,it is difficult,if not infeasible,to do localiza- linear system(251. tion without knowledge of the physical world.Accord ing to the capabilities of diverse hardwares,we classify the measuring techniques into six categories(from fine- grained to coarse-grained):location,distance,angle, area,hop count,and neighborhood,as shown in Fig.2. Fine-Grained Coarse-Grained Location Distance Angle Area Hop Count Neighbor- (a) (b) hood Fig.3.Trilateration.(a)Measuring distance to 3 reference nodes Ranging -Connectivity- (b)Ranging circles. Fig.2.Physical measurements. The over-determined linear system can be obtained Among them,the most powerful physical measure- as follows.Rearranging and squaring terms of the ac- tual distances,we have n such equations: ment is directly obtaining the position without any fur- ther computation.GPS is such a kind of infrastructure. x+7-d=2x0z+20贴-(x话+) The other five measurements are used in the scenarios of positioning an unknown node by given some refer- By subtracting out the n-th equation from the rest, ence nodes..The terms of“reference'”and“"unknown we have n-1 equations of the following form: nodes refer to the nodes being aware and being NOT aware of their locations,respectively.Distance and an- x+-x品-2-d+d哈=2(x-xn)x0+2(贴-n)0 gle measurements are obtained by ranging techniques which yields the linear relationship Hop count and neighborhood are basically based on ra- dio connectivity.In addition,area measurement relies Ax=B on either ranging or connectivity,depending on how the where A is an(n-1)x 2 matrix,such that the i-th row area constrains are formed. of A is [2(i-n)2(vi-Un)],x is the column vector 2.1.1 Distance Measurements representing the coordinates of the unknown location [zo yolT,and B is the (n-1)element column vector The distances from an unknown node to several ref- whose i--th term is(z号+f-x品-y-+d).Prac erences constrain the presence of this node,which is the tically,we cannot determine B,since the real distances basic idea of the so called multilateration.Fig.3 shows are not known to us,so computation is performed on an example of trilateration,a special form of multilat- B',which is the same as B with d substituting for eration which utilizes exact three references.A to-be- di.Now the least square solution is an estimate for located node (node 0)measures the distances from itself that minimizes Az'-B'2,which is provided by to three references (nodes 1,2,3).Obviously,node 0 '=(ATA)-1ATB'. should locate at the intersection of three circles centered So far,for distance-based positioning,the only thing at each reference position.The result of trilateration is omitted is how to measure distances in the physical unique as long as three references are non-linear. world.Many ranging techniques are proposed and de- Suppose the location of the unknown node is(ro,yo) veloped;among them,the radio signal strength based and it is able to obtain the distance estimates d,to the and time based ranging are two of the most widely used i-th reference node locating at (xi,yi),1 <i<n.Let ones in existing designs. di be the actual Euclidean distance to the i-th reference (a)Radio Signal Strength Based Distance Measure- node,i.e., ment Radio Signal Strength(RSS)based ranging tech- d:=V(x-x0)2+(-0)2 niques are based on the fact that the strength of radio signal diminishes during propagation.As a result,the The difference between the measured and the actual understanding of radio attenuation helps to map the distances can be represented by pi=d-di.Owing signal strength to the physical distance.In theory,ra- to ranging noises in di,Pi is often non-zero in practice. dio signal strengths diminish with distance according to
276 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 2.1 Physical Measurements and Single-Hop Positioning Clearly, it is difficult, if not infeasible, to do localization without knowledge of the physical world. According to the capabilities of diverse hardwares, we classify the measuring techniques into six categories (from finegrained to coarse-grained): location, distance, angle, area, hop count, and neighborhood, as shown in Fig.2. Fig.2. Physical measurements. Among them, the most powerful physical measurement is directly obtaining the position without any further computation. GPS is such a kind of infrastructure. The other five measurements are used in the scenarios of positioning an unknown node by given some reference nodes. The terms of “reference” and “unknown” nodes refer to the nodes being aware and being NOT aware of their locations, respectively. Distance and angle measurements are obtained by ranging techniques. Hop count and neighborhood are basically based on radio connectivity. In addition, area measurement relies on either ranging or connectivity, depending on how the area constrains are formed. 2.1.1 Distance Measurements The distances from an unknown node to several references constrain the presence of this node, which is the basic idea of the so called multilateration. Fig.3 shows an example of trilateration, a special form of multilateration which utilizes exact three references. A to-belocated node (node 0) measures the distances from itself to three references (nodes 1, 2, 3). Obviously, node 0 should locate at the intersection of three circles centered at each reference position. The result of trilateration is unique as long as three references are non-linear. Suppose the location of the unknown node is (x0, y0) and it is able to obtain the distance estimates d 0 i to the i-th reference node locating at (xi , yi), 1 6 i 6 n. Let di be the actual Euclidean distance to the i-th reference node, i.e., di = p (xi − x0) 2 + (yi − y0) 2. The difference between the measured and the actual distances can be represented by ρi = d 0 i − di . Owing to ranging noises in d 0 i , ρi is often non-zero in practice. The least squares method is used to assign a value to (x0, y0) that minimizes Pn i=1 ρ 2 i . This problem can be solved by a numerical solution to an over-determined linear system[25] . Fig.3. Trilateration. (a) Measuring distance to 3 reference nodes. (b) Ranging circles. The over-determined linear system can be obtained as follows. Rearranging and squaring terms of the actual distances, we have n such equations: x 2 i + y 2 i − d 2 i = 2x0xi + 2y0yi − (x 2 0 + y 2 0 ). By subtracting out the n-th equation from the rest, we have n − 1 equations of the following form: x 2 i +y 2 i −x 2 n −y 2 n −d 2 i +d 2 n = 2(xi −xn)x0 + 2(yi −yn)y0 which yields the linear relationship Ax = B where A is an (n−1)×2 matrix, such that the i-th row of A is [2(xi − xn) 2(yi − yn)], x is the column vector representing the coordinates of the unknown location [x0 y0] T, and B is the (n − 1) element column vector whose i-th term is (x 2 i + y 2 i − x 2 n − y 2 n − d 2 i + d 2 n ). Practically, we cannot determine B, since the real distances are not known to us, so computation is performed on B 0 , which is the same as B with d 0 i substituting for di . Now the least square solution is an estimate for x 0 that minimizes kAx0 − B 0 k 2 , which is provided by x 0 = (A TA) −1A TB 0 . So far, for distance-based positioning, the only thing omitted is how to measure distances in the physical world. Many ranging techniques are proposed and developed; among them, the radio signal strength based and time based ranging are two of the most widely used ones in existing designs. (a) Radio Signal Strength Based Distance Measurement Radio Signal Strength (RSS) based ranging techniques are based on the fact that the strength of radio signal diminishes during propagation. As a result, the understanding of radio attenuation helps to map the signal strength to the physical distance. In theory, radio signal strengths diminish with distance according to
Yunhao Liu et al:Location,Localization,and Localizability 277 a power law.A generally employed model for wireless microphones detect the chirp patter,they again record radio propagation is as follows26]: the current time,tsound.Once they have tradio,tsound, and tdelay,the receivers can compute the distance d to P(d)=P(do)-n10log d +X。 the transmitter by do Uradio·Usound where P(d)is the received power at distance d,P(do) d= .(tsound -tradio -tdelay), Uradio -Usound the received power at some reference distance do,n the path-loss exponent,and Xo a log-normal random where vradio and Usound denote the speeds of radio and variable with variance o2 that accounts for fading ef- sound waves respectively.Since radio waves travel sub- fects.Hence,if the path-loss exponent for a given envi- stantially faster than sound in air,the distance can be ronment is known,the received signal strength can be simply estimated as d=Usound(tsound-tradio-tdelay). translated to the signal propagation distance. If the design is transmitting radio and acoustic signals In practice,however,RSS-based ranging measure- simultaneously,i.e.,tdelay =0,the estimation can be ments contain noises on the order of several meters. further simplified as Usound (tradio -tsound). The ranging noise occurs because radio propagation tends to be highly dynamic in complicated environ- ideay ments. Transmitter On the whole,RSS based ranging is a relatively "cheap"solution without any extra devices,as all net- RF Acoustic work nodes are supposed to have radios.It is believed that more careful physical analysis of radio propaga- Receiver /radio sound tion may allow better use of RSS data.Nevertheless, the breakthrough technology is not there today. Fig.5.TDoA computation model. (b)Time Difference of Arrival (TDoA) TDoA methods are impressively accurate under line- A more promising technique is the combined use of of-sight conditions.For instance,it is claimed in [25] ultrasound/acoustic and radio signals to estimate dis- that distance can be estimated with error no more than tances by determining the Time Difference of Arrival (TDoA)of these signals(25.27-281.In such a scheme,each a few centimeters for node separations under 3 meters. The cricket ultrasound systeml27 can obtain close to node is equipped with a speaker and a microphone,as centimeter accuracy without calibration over ranges of illustrated in Fig.4.Some systems use ultrasound while up to 10 meters in indoor environments. others use audible frequencies.The general ranging Being accurate,TDoA systems suffer from high technique,however,is independent of particular hard- cost and are constrained by the line-of-sight condition, ware. which can be difficult to meet in some environments. In addition,TDoA systems perform better when they Transmitter Receiver are calibrated properly,since speakers and microphones never have identical transmission and reception charac- Acoustic/ Acoustic/ teristics.Furthermore,the speed of sound in air varies Ultrasound Ultrasound Module Module with air temperature and humidity,which introduce in- accuracy into distance estimation.Acoustic signals also show multi-path propagation effects that may affect the accuracy of signal detection.These can be mitigated to RF Module RF Module a large extent using simple spread-spectrum techniques, like those described in 29.The basic idea is to send a pseudo-random noise sequence as the acoustic signal and use a matched filter for detection,instead of using Fig.4.TDoA hardware model. a simple chirp and threshold detection The idea of TDoA ranging is conceptually simple, Recently,researchers observe that two intrinsic un- as illustrated in Fig.5.The transmitter first sends a certainties in TDoA measuring process can contribute radio signal.It waits for some fixed internal of time. to the ranging inaccuracy:the possible misalignment tdelay(which might be zero),and then produces a fixed between the sender timestamp and the actual signal pattern of "chirps"on its speaker.When receivers emission,and the possible delay of a sound signal ar- hear the radio signal,they record the current time rival being recognized at the receiver[301.Indeed,many tradio,and then turn on their microphones.When their factors can cause these uncertainties in a real system
Yunhao Liu et al.: Location, Localization, and Localizability 277 a power law. A generally employed model for wireless radio propagation is as follows[26]: P(d) = P(d0) − η10 log ³ d d0 ´ + Xσ where P(d) is the received power at distance d, P(d0) the received power at some reference distance d0, η the path-loss exponent, and Xσ a log-normal random variable with variance σ 2 that accounts for fading effects. Hence, if the path-loss exponent for a given environment is known, the received signal strength can be translated to the signal propagation distance. In practice, however, RSS-based ranging measurements contain noises on the order of several meters. The ranging noise occurs because radio propagation tends to be highly dynamic in complicated environments. On the whole, RSS based ranging is a relatively “cheap” solution without any extra devices, as all network nodes are supposed to have radios. It is believed that more careful physical analysis of radio propagation may allow better use of RSS data. Nevertheless, the breakthrough technology is not there today. (b) Time Difference of Arrival (TDoA) A more promising technique is the combined use of ultrasound/acoustic and radio signals to estimate distances by determining the Time Difference of Arrival (TDoA) of these signals[25,27-28]. In such a scheme, each node is equipped with a speaker and a microphone, as illustrated in Fig.4. Some systems use ultrasound while others use audible frequencies. The general ranging technique, however, is independent of particular hardware. Fig.4. TDoA hardware model. The idea of TDoA ranging is conceptually simple, as illustrated in Fig.5. The transmitter first sends a radio signal. It waits for some fixed internal of time, tdelay (which might be zero), and then produces a fixed pattern of “chirps” on its speaker. When receivers hear the radio signal, they record the current time, tradio, and then turn on their microphones. When their microphones detect the chirp patter, they again record the current time, tsound. Once they have tradio, tsound, and tdelay, the receivers can compute the distance d to the transmitter by d = vradio · vsound vradio − vsound · (tsound − tradio − tdelay), where vradio and vsound denote the speeds of radio and sound waves respectively. Since radio waves travel substantially faster than sound in air, the distance can be simply estimated as d = vsound ·(tsound −tradio −tdelay). If the design is transmitting radio and acoustic signals simultaneously, i.e., tdelay = 0, the estimation can be further simplified as vsound · (tradio − tsound). Fig.5. TDoA computation model. TDoA methods are impressively accurate under lineof-sight conditions. For instance, it is claimed in [25] that distance can be estimated with error no more than a few centimeters for node separations under 3 meters. The cricket ultrasound system[27] can obtain close to centimeter accuracy without calibration over ranges of up to 10 meters in indoor environments. Being accurate, TDoA systems suffer from high cost and are constrained by the line-of-sight condition, which can be difficult to meet in some environments. In addition, TDoA systems perform better when they are calibrated properly, since speakers and microphones never have identical transmission and reception characteristics. Furthermore, the speed of sound in air varies with air temperature and humidity, which introduce inaccuracy into distance estimation. Acoustic signals also show multi-path propagation effects that may affect the accuracy of signal detection. These can be mitigated to a large extent using simple spread-spectrum techniques, like those described in [29]. The basic idea is to send a pseudo-random noise sequence as the acoustic signal and use a matched filter for detection, instead of using a simple chirp and threshold detection. Recently, researchers observe that two intrinsic uncertainties in TDoA measuring process can contribute to the ranging inaccuracy: the possible misalignment between the sender timestamp and the actual signal emission, and the possible delay of a sound signal arrival being recognized at the receiver[30]. Indeed, many factors can cause these uncertainties in a real system
278 J.Comput.Sci.Technol..Mar.2010,Vol.25,No.2 such as the lack of real-time control,software delay,in- compute the intersection of all overlapping coverage re- terrupt handling delay,system loads,etc.These two gions and choose the centroid as the location estimate. delays,if not carefully controlled,can easily add up Along with the increasing number of constraining areas. to several milliseconds on average,which translates to higher localization accuracy can be achieved. several feet of ranging error.BeepBeep(301,a recently According to how area is estimated,we classify the designed high-accuracy acoustic-based ranging system, existing approaches into two categories:single reference achieves the localization accuracy as good as one or two area estimation and multi-reference area estimation. centimeters within a range of more than ten meters (a)Single Reference Area Estimation which is so far the best ranging result for off-the-shelf In this case,constraining areas are obtained accord- cell phones. ing to a single reference.For instance,the region of ra- In conclusion,many localization algorithms use dio coverage may be upper-bounded by a circle of radius TDoA simply because it is dramatically more accurate Rmax.In other words,if node B hears node A,it knows than radio-only methods.The tradeoff is that nodes must be equipped with acoustic transceivers in addi- that it must be no more than a distance Rmax from A. If an unknown node hears from several reference nodes, tion to radio transceivers,significantly increasing both it can determine that it must lie in the geometric region the complexity and the cost of the system. described by the intersection of circles of radius Rmax 2.1.2 Angle Measurement centered at these nodes,as illustrated in Fig.6(a).This can be extended to other scenarios.For instance.when Another approach for localization is the use of both lower bound Rmin and upper bound Rmax can be angular estimates instead of distance estimates.In determined,the shape of a single node's coverage is trigonometry and geometry,triangulation is the process an annulus,as illustrated in Fig.6(c);when an angu- of determining the location of a point by measuring an- lar sector (Omin,0max)and a maximum range Rmax can gles to it from two known reference points at either end be determined for some radio antennas,the shape for a of a fixed baseline,using the law of sines.Triangulation single node's coverage would be a cone with given angle was once used to find the coordinates and sometimes and radius,illustrated in Fig.6(d). the distance from a ship to the shore. The Angle of Arrival (AoA)data is typically gath- ered using radio or microphone arrays,which allow a receiver to determine the direction of a transmitter. Suppose several(3~4)spatially separated microphones hear a single transmitted signal.By analyzing the phase or time difference between the signal arrivals at different microphones,it is possible to discover the AoA of the signal. (a Those methods can obtain accuracy within a few degrees31.A straightforward localization technique. involving three rotating reference beacons at the boun- dary of a sensor network providing localization for all interior nodes,is described in [32].A more detailed de- scription of AoA-based triangulation techniques is pro- vided in 33. Unfortunately,AoA hardware tends to be bulkier Fig.6.Area measurements. and more expensive than TDoA ranging hardware, Localization techniques using geometric regions are since each node must have one speaker and several mi- first described by [34].One of the nice features of these crophones.Furthermore,the need of spatial separation techniques is that not only can the unknown nodes use between microphones is difficult to be accommodated the centroid of the overlapping region as a specific lo- in small size sensor nodes. cation estimate if necessary,but also they can deter- 2.1.3 Area Measurement mine a bound on the location error using the size of this region.When the upper bounds on these regions If the radio or other signal coverage region can be are tight,the accuracy of this geometric approach can described by a geometric shape,locations can be es- be further enhanced by incorporating "negative infor- timated by determining which geometric areas that a mation"about which reference nodes are not within node is in.The basic idea of area estimation is to rangel351.Although arbitrary shapes can be potentially
278 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 such as the lack of real-time control, software delay, interrupt handling delay, system loads, etc. These two delays, if not carefully controlled, can easily add up to several milliseconds on average, which translates to several feet of ranging error. BeepBeep[30], a recently designed high-accuracy acoustic-based ranging system, achieves the localization accuracy as good as one or two centimeters within a range of more than ten meters, which is so far the best ranging result for off-the-shelf cell phones. In conclusion, many localization algorithms use TDoA simply because it is dramatically more accurate than radio-only methods. The tradeoff is that nodes must be equipped with acoustic transceivers in addition to radio transceivers, significantly increasing both the complexity and the cost of the system. 2.1.2 Angle Measurement Another approach for localization is the use of angular estimates instead of distance estimates. In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from two known reference points at either end of a fixed baseline, using the law of sines. Triangulation was once used to find the coordinates and sometimes the distance from a ship to the shore. The Angle of Arrival (AoA) data is typically gathered using radio or microphone arrays, which allow a receiver to determine the direction of a transmitter. Suppose several (3∼4) spatially separated microphones hear a single transmitted signal. By analyzing the phase or time difference between the signal arrivals at different microphones, it is possible to discover the AoA of the signal. Those methods can obtain accuracy within a few degrees[31]. A straightforward localization technique, involving three rotating reference beacons at the boundary of a sensor network providing localization for all interior nodes, is described in [32]. A more detailed description of AoA-based triangulation techniques is provided in [33]. Unfortunately, AoA hardware tends to be bulkier and more expensive than TDoA ranging hardware, since each node must have one speaker and several microphones. Furthermore, the need of spatial separation between microphones is difficult to be accommodated in small size sensor nodes. 2.1.3 Area Measurement If the radio or other signal coverage region can be described by a geometric shape, locations can be estimated by determining which geometric areas that a node is in. The basic idea of area estimation is to compute the intersection of all overlapping coverage regions and choose the centroid as the location estimate. Along with the increasing number of constraining areas, higher localization accuracy can be achieved. According to how area is estimated, we classify the existing approaches into two categories: single reference area estimation and multi-reference area estimation. (a) Single Reference Area Estimation In this case, constraining areas are obtained according to a single reference. For instance, the region of radio coverage may be upper-bounded by a circle of radius Rmax. In other words, if node B hears node A, it knows that it must be no more than a distance Rmax from A. If an unknown node hears from several reference nodes, it can determine that it must lie in the geometric region described by the intersection of circles of radius Rmax centered at these nodes, as illustrated in Fig.6(a). This can be extended to other scenarios. For instance, when both lower bound Rmin and upper bound Rmax can be determined, the shape of a single node’s coverage is an annulus, as illustrated in Fig.6(c); when an angular sector (θmin, θmax) and a maximum range Rmax can be determined for some radio antennas, the shape for a single node’s coverage would be a cone with given angle and radius, illustrated in Fig.6(d). Fig.6. Area measurements. Localization techniques using geometric regions are first described by [34]. One of the nice features of these techniques is that not only can the unknown nodes use the centroid of the overlapping region as a specific location estimate if necessary, but also they can determine a bound on the location error using the size of this region. When the upper bounds on these regions are tight, the accuracy of this geometric approach can be further enhanced by incorporating “negative information” about which reference nodes are not within range[35]. Although arbitrary shapes can be potentially