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
Yunhao Liu et al:Location,Localization,and Localizability 279 computed in this manner,a computational simplifica- inter-node distances.The local connectivity informa- tion to determine this bounded region is to use rect- tion provided by the radio defines an unweighted graph, angular bounding boxes as location estimates.The where the vertices are wireless nodes and edges repre- bounding-box algorithm is a computationally efficient sent direct radio links between nodes.The hop count method to localize nodes given their ranges to several hij between nodes si and sj is then defined as the length references.Essentially,it is assumed that each node lies of the shortest path from si to sj.Obviously,the phys- within the intersection of its reference bounding boxes ical distance between si and si,namely,dij,is less than (b)Multi-Reference Area Estimation R x hij,the value which can be used as an estimate of Another approach of area estimation is the appro- dii if nodes are densely deployed. ximate point in triangle (APIT)(36).Its novelty lies in It turns out that a better estimate can be made if how the regions are defined.Actually,bounding tri- we know nlocal,the expected number of neighbors per angles are obtained according to any group of three node.As shown by Kleinrock and Silvester371,it is reference nodes,rather than the coverage of a single possible to compute a better estimate for the distance node. covered by one radio hop APIT consists of two key processes:triangle inter- section and point in triangle (PIT)test.Nodes are dhop = R(I+e-nocal_ -(mocal/)arccost-tv1-1dt assumed to hear a fairly large number of beacons.A node forms some number of "reference triangles":The triangle formed by three arbitrary references.The node Then di≈hi×dhop:Experimental studies3g then decides whether it is inside or outside a given tri- show that the equation above can be quite accurate angle by PIT test.Once this process is complete,the when nocal grows above 5.However,when nocal >15, node simply finds the intersection of the reference tri- dhop approaches R,so the equation of dhop becomes angles that contains it and chooses the centroid as its less useful.Nagpal et als]demonstrate by algorithm position estimate,as illustrated in Fig.6(b).In this pro- that even better hop-count distance estimates can be cess.APIT does not assume that nodes can really range computed by averaging distances with neighbors.This to these beacons. benefit does not appear until nocal>15;while,it can The PIT test is based on geometry.For a given tri- reduce hop-count error down to as little as 0.2R. Another method to estimate per-hop distance is to angle with points A,B,and C,a point M is outside triangle ABC,if there exists a direction such that a employ a number of reference nodes,as illustrated in point adjacent to M is further/closer to points A,B, Fig.7(a).Since the locations of reference nodes are and C simultaneously.Otherwise,M is inside triangle known,the pairwise distances among them can be com- ABC.Unfortunately,given that typically nodes cannot puted.Hence,if the hop count hij between two refer- move,an approximate PIT test is proposed based on ences(si and sj)and the distance dij are available,the two assumptions.The first one is that the range mea- per-hop distance can be estimated by dhop=dij/hij. surements are monotonic and calibrated to be compara Due to the hardware limitations and energy con- ble but are not required to produce distance estimates. straints of wireless devices,hop count based localiza- The second one assumes sufficient node density for ap tion approaches are cost-effective alternatives to rang- proximating node movement.If no neighbor of M is ing based approaches.Since there is no way to measure further from/closer to all three anchors A,B,and C si- physical distances between nodes,existing hop-count multaneously,M assumes that it is inside triangle ABC based approaches largely depend on a high density of seeds Otherwise,M assumes it resides outside this triangle In practice,however,this approximation does not re- Most existing approaches,however,would fail alize the PIT test well.Nevertheless,APIT provides in anisotropic network topologies,where holes exist a novel point of view to conduct localization based on among wireless devices,as shown in Fig.7(b).In anisotropic networks[391,the Euclidean distance be- area estimation. tween a pair of nodes may not correlate closely with 2.1.4 Hop Count Measurements the hop count between them because the corresponding shortest path may have to curve around intermediate Based on the observation that if two nodes can com- holes,leading to poor distance estimation.Unfortu- municate by radio,their distance from each other is less nately.anisotropic networks are more likely to exist in than R(the maximum range of their radios)with high practice for several reasons.First,in many real appli- probability,many delicate approaches are designed for cations,sensor nodes/seeds can rarely be uniformly de- accurate localization.In particular,researchers have ployed over the field due to the geographical obstacles found "hop count"to be a useful way to compute Second,even if we assume that the initial sensor
Yunhao Liu et al.: Location, Localization, and Localizability 279 computed in this manner, a computational simplification to determine this bounded region is to use rectangular bounding boxes as location estimates. The bounding-box algorithm is a computationally efficient method to localize nodes given their ranges to several references. Essentially, it is assumed that each node lies within the intersection of its reference bounding boxes. (b) Multi-Reference Area Estimation Another approach of area estimation is the approximate point in triangle (APIT)[36]. Its novelty lies in how the regions are defined. Actually, bounding triangles are obtained according to any group of three reference nodes, rather than the coverage of a single node. APIT consists of two key processes: triangle intersection and point in triangle (PIT) test. Nodes are assumed to hear a fairly large number of beacons. A node forms some number of “reference triangles”: The triangle formed by three arbitrary references. The node then decides whether it is inside or outside a given triangle by PIT test. Once this process is complete, the node simply finds the intersection of the reference triangles that contains it and chooses the centroid as its position estimate, as illustrated in Fig.6(b). In this process, APIT does not assume that nodes can really range to these beacons. The PIT test is based on geometry. For a given triangle with points A, B, and C, a point M is outside triangle ABC, if there exists a direction such that a point adjacent to M is further/closer to points A, B, and C simultaneously. Otherwise, M is inside triangle ABC. Unfortunately, given that typically nodes cannot move, an approximate PIT test is proposed based on two assumptions. The first one is that the range measurements are monotonic and calibrated to be comparable but are not required to produce distance estimates. The second one assumes sufficient node density for approximating node movement. If no neighbor of M is further from/closer to all three anchors A, B, and C simultaneously, M assumes that it is inside triangle ABC. Otherwise, M assumes it resides outside this triangle. In practice, however, this approximation does not realize the PIT test well. Nevertheless, APIT provides a novel point of view to conduct localization based on area estimation. 2.1.4 Hop Count Measurements Based on the observation that if two nodes can communicate by radio, their distance from each other is less than R (the maximum range of their radios) with high probability, many delicate approaches are designed for accurate localization. In particular, researchers have found “hop count” to be a useful way to compute inter-node distances. The local connectivity information provided by the radio defines an unweighted graph, where the vertices are wireless nodes and edges represent direct radio links between nodes. The hop count hij between nodes si and sj is then defined as the length of the shortest path from si to sj . Obviously, the physical distance between si and sj , namely, dij , is less than R × hij , the value which can be used as an estimate of dij if nodes are densely deployed. It turns out that a better estimate can be made if we know nlocal, the expected number of neighbors per node. As shown by Kleinrock and Silvester[37], it is possible to compute a better estimate for the distance covered by one radio hop: dhop = R ³ 1+e −nlocal− Z 1 −1 e −(nlocal/π)arccos t−t √ 1−t 2 dt ´ . Then dij ≈ hij × dhop. Experimental studies[38] show that the equation above can be quite accurate when nlocal grows above 5. However, when nlocal > 15, dhop approaches R, so the equation of dhop becomes less useful. Nagpal et al. [38] demonstrate by algorithm that even better hop-count distance estimates can be computed by averaging distances with neighbors. This benefit does not appear until nlocal > 15; while, it can reduce hop-count error down to as little as 0.2R. Another method to estimate per-hop distance is to employ a number of reference nodes, as illustrated in Fig.7(a). Since the locations of reference nodes are known, the pairwise distances among them can be computed. Hence, if the hop count hij between two references (si and sj ) and the distance dij are available, the per-hop distance can be estimated by dhop = dij/hij . Due to the hardware limitations and energy constraints of wireless devices, hop count based localization approaches are cost-effective alternatives to ranging based approaches. Since there is no way to measure physical distances between nodes, existing hop-count based approaches largely depend on a high density of seeds. Most existing approaches, however, would fail in anisotropic network topologies, where holes exist among wireless devices, as shown in Fig.7(b). In anisotropic networks[39], the Euclidean distance between a pair of nodes may not correlate closely with the hop count between them because the corresponding shortest path may have to curve around intermediate holes, leading to poor distance estimation. Unfortunately, anisotropic networks are more likely to exist in practice for several reasons. First, in many real applications, sensor nodes/seeds can rarely be uniformly deployed over the field due to the geographical obstacles. Second, even if we assume that the initial sensor
280 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 when the density of reference nodes is sufficiently high so that there are often multiple reference nodes within the range of an unknown nodel421.Let there be k refer- ence nodes within the proximity of the unknown node As shown in Fig.8,we use the centroid of the polygon constructed by the k reference nodes as the estimated position of the unknown node.This is actually a k- nearest-neighbor approximation in which all reference nodes have equal weights. (a) Fig.8.k-neighbor proximity. This centroid technique has been investigated using a model with each node having a simple circular range R in an infinite square mesh of reference nodes spaced a distance d apart3).It is shown through simulation that,as the overlap ratio R/d is increased from 1 to 4, 。 the average error in localization decreases from 0.5d to 。 0.25d. . The k-neighbor proximity approach inherits the (b) merit of computational simplicity from the single neigh- bor proximity approach;while at the same time,it pro- Fig.7.Hop count measurement.(a)Per-hop distance measure- vides more accurate localization results statistically. ment.(b)Distance mismatch. 2.1.6 Comparative Study and Directions of Future network is isotropic,unbalanced power consumption Research among nodes will easily create holes in the network. Recently,a distributed methodtol has been proposed A comparative study is presented in this subsection to detect hole boundary by using only the connecti- for existing physical measurement approaches.Table 1 vity information.Based on that work,REPl is pro- provides an overview of these approaches in terms of ac- posed to deal with the "distance mismatch"problem in curacy,hardware cost,and environment requirements. anisotropic networks. All approaches have their own merits and drawbacks, making them suitable for different scenarios. 2.1.5 Neighborhood Measurement Recent technical advances foster two novel ranging The radio connectivity measurement can be con- sidered economic since no extra hardware is needed. Table 1.Comparative Study of Physical Measurements Perhaps the most basic positioning technique is that of one neighbor proximity,involving a simple decision Physical Measurements Accuracy Hardware Computa- of whether two nodes are within the reception range Cost tion Cost Distance RSS of each other.A set of reference nodes is placed in Median Low Low TDoA the network with some non-overlapping (or nearly non- High High Low overlapping)sub-regions.Reference nodes periodically Angle AoA High High Low emit beacons including their location IDs.Unknown Area Single reference Median*Median* Median nodes use the received locations as their own location, Multi-reference Median*Median*High achieving a course-grained localization.The major ad- Hop Count Per-hop distance Median Low Median vantage of such a neighbor proximity approach is the Neighborhood Single neighbor Low Low Low simplicity of computation. Multi-neighbor Low Low Low The neighborhood information can be more useful *depends on the diverse geometric constrains
280 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 Fig.7. Hop count measurement. (a) Per-hop distance measurement. (b) Distance mismatch. network is isotropic, unbalanced power consumption among nodes will easily create holes in the network. Recently, a distributed method[40] has been proposed to detect hole boundary by using only the connectivity information. Based on that work, REP[41] is proposed to deal with the “distance mismatch” problem in anisotropic networks. 2.1.5 Neighborhood Measurement The radio connectivity measurement can be considered economic since no extra hardware is needed. Perhaps the most basic positioning technique is that of one neighbor proximity, involving a simple decision of whether two nodes are within the reception range of each other. A set of reference nodes is placed in the network with some non-overlapping (or nearly nonoverlapping) sub-regions. Reference nodes periodically emit beacons including their location IDs. Unknown nodes use the received locations as their own location, achieving a course-grained localization. The major advantage of such a neighbor proximity approach is the simplicity of computation. The neighborhood information can be more useful when the density of reference nodes is sufficiently high so that there are often multiple reference nodes within the range of an unknown node[42]. Let there be k reference nodes within the proximity of the unknown node. As shown in Fig.8, we use the centroid of the polygon constructed by the k reference nodes as the estimated position of the unknown node. This is actually a knearest-neighbor approximation in which all reference nodes have equal weights. Fig.8. k-neighbor proximity. This centroid technique has been investigated using a model with each node having a simple circular range R in an infinite square mesh of reference nodes spaced a distance d apart[43]. It is shown through simulation that, as the overlap ratio R/d is increased from 1 to 4, the average error in localization decreases from 0.5d to 0.25d. The k-neighbor proximity approach inherits the merit of computational simplicity from the single neighbor proximity approach; while at the same time, it provides more accurate localization results statistically. 2.1.6 Comparative Study and Directions of Future Research A comparative study is presented in this subsection for existing physical measurement approaches. Table 1 provides an overview of these approaches in terms of accuracy, hardware cost, and environment requirements. All approaches have their own merits and drawbacks, making them suitable for different scenarios. Recent technical advances foster two novel ranging Table 1. Comparative Study of Physical Measurements Physical Measurements Accuracy Hardware ComputaCost tion Cost Distance RSS Median Low Low TDoA High High Low Angle AoA High High Low Area Single reference Median* Median* Median Multi-reference Median* Median* High Hop Count Per-hop distance Median Low Median Neighborhood Single neighbor Low Low Low Multi-neighbor Low Low Low ∗: depends on the diverse geometric constrains
Yunhao Liu et al:Location,Localization,and Localizability 281 approaches.Ultra-WideBand (UWB)is a radio tech- Centralized algorithms are designed to run on a cen- nology that can be used at very low energy levels for tral machine with powerful computational capabilities short-range high-bandwidth communications by using Network nodes collect environmental data and send a large portion of the radio spectrum44l.It has rela- back to a base station for analysis,after which the com- tive bandwidth larger than 20%or absolute bandwidth puted positions are delivered back into the network. of more than 500 MHz.Such wide bandwidth offers Centralized algorithms resolve the computational limi- a wealth of advantages for both communications and tations of nodes.This benefit,however,comes from ranging applications.In particular,a large absolute accepting the communication cost of transmitting data bandwidth offers high resolution with improved rang- back to a base station.Unfortunately,communication ing accuracy of centimeter-level. generally consumes more energy than computation in UWB has a combination of attractive properties for existing network hardware platforms. in-building location systems.First,it is a non-line-of- In contrast,distributed algorithms are designed to sight technology with a range of a few tens of meters run in network,using massive parallelism and inter- which makes it practical to cover large indoor areas;sec- node communication to compensate for the lack of cen ond,it is easy to filter the signal to minimize the multi- tralized computing power,while at the same time to re- path distortions that are the main cause of inaccuracy duce the expensive node-to-sink communications.Dis- in RF based location systems.With conventional RF tributed algorithms often use a subset of the data to reflections in in-building environments distort the di- locate each node independently,yielding an approxima- rect path signal,making accurate pulse timing difficult: tion of a corresponding centralized algorithm where all while with UWB,the direct path signal can be distin- the data are considered and used to compute the posi- guished from the reflections.These properties provide tions of all nodes simultaneously.There are two impor- a good cost-to-performance ratio of all available indoor tant categories of distributed localization approaches. location technologies. The first group,beacon-based distributed algorithms, The second promising technique is Chirp Spread typically starts a localization process with beacons and Spectrum(CSS)designed by Nanotron Technologiesl45] the nodes in vicinity of beacons.In general,nodes and adopted by IEEE 802.15.4a.CSS is a cus- obtain distance measurements to a few beacons and tomized application of Multi-Dimensional Multiple Ac then determine their locations.In some algorithms, cess(MDMA)for the requirements of battery-powered the newly localized nodes can become beacons to help applications,where the reliability of the transmission locating other nodes.In such iterative localization ap- and low power consumption are of special importance. proaches,location information diffuses from beacons to CSS operates in the 2.45 GHz ISM band and achieves a the border of a network,which can be viewed as a top- maximum data rate of 2 Mbps.Each symbol is trans- down manner.The second group of approaches per- mitted with a chirp pulse that has a bandwidth of forms in a bottom-up manner,in which localization is 80 MHz and a fixed duration of 1 us. originated in a local group of nodes in relative coordi- Nanotron Technologies have developed a ToA nates.After gradually merging such local maps,entire method that employs a ranging signal sent by a reader network localization is achieved in global coordinates. and an acknowledgement sent back from the tag to can- 2.2.2 cel out the requirements for clock synchronization.This Centralized Localization Approaches solution provides protection against multi-path propa- (a)Multi-Dimensional Scaling (MDS) gation and noise by its CSS modulation.To eliminate Multi-Dimensional scaling (MDS)146]was originally the effect of clock drift and offset,ranging measure developed for use in mathematical psychology.The in- ments are taken by both the tag and the reader to pro- tuition behind MDS is straightforward.Suppose there vide two measurements that can then be averaged.This are n points,suspended in a volume.We do not know ranging result is reasonably accurate with no more than the positions of the points,but we know the distances 1 meter error,even in the most challenging environ- between each pair of points.MDS is an O(n3)algo- ments.The method is called Symmetric Double Sided rithm that uses the law of cosines and linear algebra to Two Way Ranging,or SDS-TWR. reconstruct the relative positions of the points based on the pairwise distances.The algorithm has three stages: 2.2 Network-Wide Localization 1)Generate an n x n matrix M,whose (i,j)entry 2.2.1 Computation Organization contains the estimated distance between nodes i and j (simply run Floyd's all-pairs shortest-path algorithm). This subsection defines taxonomy for localization al- 2)Apply classical metric-MDS on M to determine gorithms based on their computational organization. a map that gives the locations of all nodes in relative
Yunhao Liu et al.: Location, Localization, and Localizability 281 approaches. Ultra-WideBand (UWB) is a radio technology that can be used at very low energy levels for short-range high-bandwidth communications by using a large portion of the radio spectrum[44]. It has relative bandwidth larger than 20% or absolute bandwidth of more than 500 MHz. Such wide bandwidth offers a wealth of advantages for both communications and ranging applications. In particular, a large absolute bandwidth offers high resolution with improved ranging accuracy of centimeter-level. UWB has a combination of attractive properties for in-building location systems. First, it is a non-line-ofsight technology with a range of a few tens of meters, which makes it practical to cover large indoor areas; second, it is easy to filter the signal to minimize the multipath distortions that are the main cause of inaccuracy in RF based location systems. With conventional RF, reflections in in-building environments distort the direct path signal, making accurate pulse timing difficult; while with UWB, the direct path signal can be distinguished from the reflections. These properties provide a good cost-to-performance ratio of all available indoor location technologies. The second promising technique is Chirp Spread Spectrum (CSS) designed by Nanotron Technologies[45] and adopted by IEEE 802.15.4a. CSS is a customized application of Multi-Dimensional Multiple Access (MDMA) for the requirements of battery-powered applications, where the reliability of the transmission and low power consumption are of special importance. CSS operates in the 2.45 GHz ISM band and achieves a maximum data rate of 2 Mbps. Each symbol is transmitted with a chirp pulse that has a bandwidth of 80 MHz and a fixed duration of 1 µs. Nanotron Technologies have developed a ToA method that employs a ranging signal sent by a reader and an acknowledgement sent back from the tag to cancel out the requirements for clock synchronization. This solution provides protection against multi-path propagation and noise by its CSS modulation. To eliminate the effect of clock drift and offset, ranging measurements are taken by both the tag and the reader to provide two measurements that can then be averaged. This ranging result is reasonably accurate with no more than 1 meter error, even in the most challenging environments. The method is called Symmetric Double Sided Two Way Ranging, or SDS-TWR. 2.2 Network-Wide Localization 2.2.1 Computation Organization This subsection defines taxonomy for localization algorithms based on their computational organization. Centralized algorithms are designed to run on a central machine with powerful computational capabilities. Network nodes collect environmental data and send back to a base station for analysis, after which the computed positions are delivered back into the network. Centralized algorithms resolve the computational limitations of nodes. This benefit, however, comes from accepting the communication cost of transmitting data back to a base station. Unfortunately, communication generally consumes more energy than computation in existing network hardware platforms. In contrast, distributed algorithms are designed to run in network, using massive parallelism and internode communication to compensate for the lack of centralized computing power, while at the same time to reduce the expensive node-to-sink communications. Distributed algorithms often use a subset of the data to locate each node independently, yielding an approximation of a corresponding centralized algorithm where all the data are considered and used to compute the positions of all nodes simultaneously. There are two important categories of distributed localization approaches. The first group, beacon-based distributed algorithms, typically starts a localization process with beacons and the nodes in vicinity of beacons. In general, nodes obtain distance measurements to a few beacons and then determine their locations. In some algorithms, the newly localized nodes can become beacons to help locating other nodes. In such iterative localization approaches, location information diffuses from beacons to the border of a network, which can be viewed as a topdown manner. The second group of approaches performs in a bottom-up manner, in which localization is originated in a local group of nodes in relative coordinates. After gradually merging such local maps, entire network localization is achieved in global coordinates. 2.2.2 Centralized Localization Approaches (a) Multi-Dimensional Scaling (MDS) Multi-Dimensional scaling (MDS)[46] was originally developed for use in mathematical psychology. The intuition behind MDS is straightforward. Suppose there are n points, suspended in a volume. We do not know the positions of the points, but we know the distances between each pair of points. MDS is an O(n 3 ) algorithm that uses the law of cosines and linear algebra to reconstruct the relative positions of the points based on the pairwise distances. The algorithm has three stages: 1) Generate an n × n matrix M, whose (i, j) entry contains the estimated distance between nodes i and j (simply run Floyd’s all-pairs shortest-path algorithm). 2) Apply classical metric-MDS on M to determine a map that gives the locations of all nodes in relative
282 J.Comput.Sci.Technol.,Mar.2010,Vol.25,No.2 coordinates. distance-vector algorithm is used to determine the dis- 3)Transform the solution into global coordinates tance corresponding to the shortest distance path be- based on some number of fixed anchor nodes. tween the unknown nodes and reference nodes. MDS performs well on RSS data,getting perfor- 3)Iterative localization:One variant of above ap- mance on the order of half the radio range when the proaches is indirect use of beacon nodes.Initially an neighborhood size nocal is higher than 121471.The main unknown node,if possible,is located based on its neigh- problem with MDS,however,is its poor asymptotic per- bors by multilateration or other positioning techniques formance,which is O(n3)on account of stages 1 and 2. After being aware of its location,it becomes a refer- (b)SemiDefinite Programming(SDP) ence node to localize other unknown nodes in the sub- The semidefinite programming(SDP)approach was sequent localization process.This step continues iter- pioneered by Doherty et al.34 In their algorithm,ge atively,gradually turning the unknown nodes to the ometric constraints between nodes are represented as known.The process of iterative localization is illus linear matrix inequalities (LMIs).Once all the con- trated in Fig.9. straints in the network are expressed in this form,the LMIs can be combined to form a single semidefinite program,which is solved to produce a bounding region for each node.The advantage of SDP is its elegance 女女4 on concise problem formulation,clear model represen- tation,and elegant mathematic solution. Solving the linear or semidefinite program has to be Fig.9.Iterative localization. done centrally.The relevant operation is O(k2)for an- gle of arrival data,and O(k3)when radial (e.g.,hop Iterative trilateration only involves local information count)data is included,where k is the number of con- (information within neighborhood)and accordingly re- vex constraints needed to describe the network.Thus. duces communication cost.Nevertheless.the use of lo- the computation complexity of SDP is likely to preclude calized unknown nodes as reference nodes inherently itself in practice. introduces substantial cumulative error.Some works Unfortunately,not all geometric constraints can be characterize the error propagation in multihop locali- expressed as LMIs.In general,only constraints that zation approaches and make efforts to control error accumulation[50-51] form convex regions are amenable to representation as an LMI.Thus,AoA data can be represented as a trian- Experimental studies show that multilateration- gle and hop count data can be represented as a circle, based algorithms require an average node degree be- but precise range data cannot be conveniently repre- yond 10 to properly localize most of the nodes in a ran sented,as rings cannot be expressed as convex con- domly deployed networkl521.When the average degree strains.This inability to accommodate precise range is below 8,iterative multilateration will fail for most of data might prove to be a significant drawback. the nodes,since it makes the nodes form a chain of de- pendence and a single-point failure on one node would 2.2.3 Distributed Localization Approaches lead to further failures on a set of subsequent nodes. To make localization applicable for sparse networks, (a)Beacon Based Localization Sweeps[53)partially relaxes the requirement of node de- Beacon based localization approaches utilize esti- pendence.In contrast to the traditional unique position mates of distances to reference nodes that may be se- computation,Sweeps introduces a novel concept of fi- veral hops awayl4s-49.These distances are propagated nite localization which locates a target node to a set from reference nodes to unknown nodes using a basic of possible positions,called candidate positions.Finite distance-vector technique.Such a mechanism can be localization guarantees that the ground truth position seen as a top-down manner due to the progressive pro- of a node is one of its candidate positions.Further. pagation of location information from beacons to an Sweeps adopts a new positioning scheme,called bilate- entire network.There are three types as follows ration,to compute the candidate positions of a node by 1)DV-hop:In this approach,each unknown node utilizing only two ranging measurements.As shown in determines its distance from various reference nodes by Fig.10,bilateration produces two candidate positions multiplying the least number of hops to the reference for a node and one of them is the ground truth posi- nodes with an estimated average distance per hop that tion.Similar to multilateration,the finitely localized depends upon the network density. node,called swept node,can act as a reference node to 2)DV distance:If inter-node distance estimates localize other nodes.The only difference is that all can- are directly available for each link in the graph,the didate positions of the swept node are enumerated for
282 J. Comput. Sci. & Technol., Mar. 2010, Vol.25, No.2 coordinates. 3) Transform the solution into global coordinates based on some number of fixed anchor nodes. MDS performs well on RSS data, getting performance on the order of half the radio range when the neighborhood size nlocal is higher than 12[47]. The main problem with MDS, however, is its poor asymptotic performance, which is O(n 3 ) on account of stages 1 and 2. (b) SemiDefinite Programming (SDP) The semidefinite programming (SDP) approach was pioneered by Doherty et al. [34] In their algorithm, geometric constraints between nodes are represented as linear matrix inequalities (LMIs). Once all the constraints in the network are expressed in this form, the LMIs can be combined to form a single semidefinite program, which is solved to produce a bounding region for each node. The advantage of SDP is its elegance on concise problem formulation, clear model representation, and elegant mathematic solution. Solving the linear or semidefinite program has to be done centrally. The relevant operation is O(k 2 ) for angle of arrival data, and O(k 3 ) when radial (e.g., hop count) data is included, where k is the number of convex constraints needed to describe the network. Thus, the computation complexity of SDP is likely to preclude itself in practice. Unfortunately, not all geometric constraints can be expressed as LMIs. In general, only constraints that form convex regions are amenable to representation as an LMI. Thus, AoA data can be represented as a triangle and hop count data can be represented as a circle, but precise range data cannot be conveniently represented, as rings cannot be expressed as convex constrains. This inability to accommodate precise range data might prove to be a significant drawback. 2.2.3 Distributed Localization Approaches (a) Beacon Based Localization Beacon based localization approaches utilize estimates of distances to reference nodes that may be several hops away[48-49]. These distances are propagated from reference nodes to unknown nodes using a basic distance-vector technique. Such a mechanism can be seen as a top-down manner due to the progressive propagation of location information from beacons to an entire network. There are three types as follows. 1) DV-hop: In this approach, each unknown node determines its distance from various reference nodes by multiplying the least number of hops to the reference nodes with an estimated average distance per hop that depends upon the network density. 2) DV distance: If inter-node distance estimates are directly available for each link in the graph, the distance-vector algorithm is used to determine the distance corresponding to the shortest distance path between the unknown nodes and reference nodes. 3) Iterative localization: One variant of above approaches is indirect use of beacon nodes. Initially an unknown node, if possible, is located based on its neighbors by multilateration or other positioning techniques. After being aware of its location, it becomes a reference node to localize other unknown nodes in the subsequent localization process. This step continues iteratively, gradually turning the unknown nodes to the known. The process of iterative localization is illustrated in Fig.9. Fig.9. Iterative localization. Iterative trilateration only involves local information (information within neighborhood) and accordingly reduces communication cost. Nevertheless, the use of localized unknown nodes as reference nodes inherently introduces substantial cumulative error. Some works characterize the error propagation in multihop localization approaches and make efforts to control error accumulation[50-51] . Experimental studies show that multilaterationbased algorithms require an average node degree beyond 10 to properly localize most of the nodes in a randomly deployed network[52]. When the average degree is below 8, iterative multilateration will fail for most of the nodes, since it makes the nodes form a chain of dependence and a single-point failure on one node would lead to further failures on a set of subsequent nodes. To make localization applicable for sparse networks, Sweeps[53] partially relaxes the requirement of node dependence. In contrast to the traditional unique position computation, Sweeps introduces a novel concept of fi- nite localization which locates a target node to a set of possible positions, called candidate positions. Finite localization guarantees that the ground truth position of a node is one of its candidate positions. Further, Sweeps adopts a new positioning scheme, called bilateration, to compute the candidate positions of a node by utilizing only two ranging measurements. As shown in Fig.10, bilateration produces two candidate positions for a node and one of them is the ground truth position. Similar to multilateration, the finitely localized node, called swept node, can act as a reference node to localize other nodes. The only difference is that all candidate positions of the swept node are enumerated for
Yunhao Liu et al:Location,Localization,and Localizability 283 the location computation of the target node.Moreover. 3)Finally,merge sub-regions using a coordinate sys- after each bilateration,Sweeps checks the consistency tem registration procedure.Coordinate system regis- among the candidate position sets and deletes those in- tration finds a rigid transformation that maps points compatible items.Under this mechanism,Sweeps can in one coordinate system to a different coordinate sys- locate a large proposition of theoretically localizable tem.Thus,step 3)places all the sub-regions into a nodes in a network.However,the worst case computa- single global coordinate system.Many algorithms do tion complexity of this design grows exponentially with this step suboptimally,since there is a closed-form,fast the number of nodes. and least-square optimal method of registering coordi- nate system. Fig.12.Robust quadrilateral. Moore et al52]outline an approach that produces (a) (b) more robust local maps.Rather than using three ar- bitrary nodes,they use "robust quadrilateral"(robust Fig.10.Bilateration.(a)Measuring distance to 2 reference nodes. quads)to define a map.As shown in Fig.12,a robust (b)Bilateration creates two possible locations quad consists of four subtriangles (AABC,AADC, (b)Coordinate System Stitching △ABD,△BCD)that satisfy: Coordinate system stitching is a different way to ad- dress the same problem.It has attracted a lot of re- b×sin2(0)>dmin search efforts recently[48,52.54.It works in a bottom-up manner,in which localization is originated in a local where b is the length of the shortest side,0 is the small- group of nodes in relative coordinates.By gradually est angle,and dmin is a predetermined constant based merging such local maps,it finally achieves entire net- on average measurement error.The idea is that the work localization in global coordinates,as illustrated in points of a robust quad can be placed correctly with Fig.11. respect to each other (i.e.,no "flips"[551).Moore et al. demonstrate that the probability of a robust quadrila- teral experiencing internal flips given zero mean Gaus- sian measurement error can be bounded by setting dmin appropriately.In effect,dmin filters out quads that have too much positional ambiguity to be localized with con- fidence.The appropriate level of filtering is based on the amount of uncertainty in distance measurements. Unfortunately,coordinate system stitching suffers from error propagation caused by local map stitching.Moore et al.prove the probability of their algorithm construct- ing correct local maps and prove error lower bound on the local map positions.Furthermore,these techniques have a tendency to orphan nodes,either because they could not be added to a local map or because their lo- Fig.11.Coordinate system stitching. cal map failed to overlap sufficiently with neighboring maps.Moore et al.argue that this is acceptable be- Coordinate system stitching works as follows: cause the orphaned nodes are the nodes most likely to 1)Split the network into small overlapping sub- display high error.They point out that "for many ap- regions.Very often each sub-region is simply a single plications,missing localization information for a known node and its one-hop neighbors. set of nodes is preferential to incorrect information for 2)For each sub-region,compute a“local map”, an unknown set".However,this answer may not be which is essentially an embedding of the nodes in the satisfactory for some applications,many of which can- sub-region into a relative coordinate system. not use nodes without locations for sensing,routing
Yunhao Liu et al.: Location, Localization, and Localizability 283 the location computation of the target node. Moreover, after each bilateration, Sweeps checks the consistency among the candidate position sets and deletes those incompatible items. Under this mechanism, Sweeps can locate a large proposition of theoretically localizable nodes in a network. However, the worst case computation complexity of this design grows exponentially with the number of nodes. Fig.10. Bilateration. (a) Measuring distance to 2 reference nodes. (b) Bilateration creates two possible locations. (b) Coordinate System Stitching Coordinate system stitching is a different way to address the same problem. It has attracted a lot of research efforts recently[48,52,54]. It works in a bottom-up manner, in which localization is originated in a local group of nodes in relative coordinates. By gradually merging such local maps, it finally achieves entire network localization in global coordinates, as illustrated in Fig.11. Fig.11. Coordinate system stitching. Coordinate system stitching works as follows: 1) Split the network into small overlapping subregions. Very often each sub-region is simply a single node and its one-hop neighbors. 2) For each sub-region, compute a “local map”, which is essentially an embedding of the nodes in the sub-region into a relative coordinate system. 3) Finally, merge sub-regions using a coordinate system registration procedure. Coordinate system registration finds a rigid transformation that maps points in one coordinate system to a different coordinate system. Thus, step 3) places all the sub-regions into a single global coordinate system. Many algorithms do this step suboptimally, since there is a closed-form, fast and least-square optimal method of registering coordinate system. Fig.12. Robust quadrilateral. Moore et al. [52] outline an approach that produces more robust local maps. Rather than using three arbitrary nodes, they use “robust quadrilateral” (robust quads) to define a map. As shown in Fig.12, a robust quad consists of four subtriangles (∆ABC , ∆ADC , ∆ABD, ∆BCD) that satisfy: b × sin2 (θ) > dmin, where b is the length of the shortest side, θ is the smallest angle, and dmin is a predetermined constant based on average measurement error. The idea is that the points of a robust quad can be placed correctly with respect to each other (i.e., no “flips”[55]). Moore et al. demonstrate that the probability of a robust quadrilateral experiencing internal flips given zero mean Gaussian measurement error can be bounded by setting dmin appropriately. In effect, dmin filters out quads that have too much positional ambiguity to be localized with con- fidence. The appropriate level of filtering is based on the amount of uncertainty in distance measurements. Unfortunately, coordinate system stitching suffers from error propagation caused by local map stitching. Moore et al. prove the probability of their algorithm constructing correct local maps and prove error lower bound on the local map positions. Furthermore, these techniques have a tendency to orphan nodes, either because they could not be added to a local map or because their local map failed to overlap sufficiently with neighboring maps. Moore et al. argue that this is acceptable because the orphaned nodes are the nodes most likely to display high error. They point out that “for many applications, missing localization information for a known set of nodes is preferential to incorrect information for an unknown set”. However, this answer may not be satisfactory for some applications, many of which cannot use nodes without locations for sensing, routing