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 ef￾fects. Hence, if the path-loss exponent for a given envi￾ronment is known, the received signal strength can be translated to the signal propagation distance. In practice, however, RSS-based ranging measure￾ments contain noises on the order of several meters. The ranging noise occurs because radio propagation tends to be highly dynamic in complicated environ￾ments. On the whole, RSS based ranging is a relatively “cheap” solution without any extra devices, as all net￾work nodes are supposed to have radios. It is believed that more careful physical analysis of radio propaga￾tion 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 dis￾tances 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 hard￾ware. 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 sub￾stantially 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 line￾of-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 charac￾teristics. Furthermore, the speed of sound in air varies 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 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 un￾certainties 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 ar￾rival being recognized at the receiver[30]. Indeed, many factors can cause these uncertainties in a real system