Yunhao Liu et al:Location,Localization,and Localizability 285 Table 2.Comparative Study of Localization Algorithms Localization Algorithm Accuracy Node Beacon Computation Communication Error Density Percentage Cost Cost Propagation Centralized MDS High Low Low High High Low SDP High High Median High High Low Distributed Beacon based Low High High Low Low High* Coordinate stitching Low High Low Median Median High *in case of iterative localization In conclusion,a number of typical localization ap- software.While the extrinsic one is more unpredictable proaches are surveyed and evaluated with various me- and challenging during real deployments,the intrin- trics in this section.All approaches have their own sic one causes many complications when using multi- merits and drawbacks,making them suitable for differ- hop measurements to estimate node locations.Results ent applications.Hence,the design of a localization al- from field experiments demonstrated that even rela- gorithm should sufficiently investigate application pro- tively small ranging errors can significantly amplify the perties,as well as take into account algorithm gener- error of location estimates52);thus,dealing with such ality and flexibility.In present and foreseeable future errors is an essential issue for high-accuracy localization study,obtaining a Pareto improvement is a major chal- algorithms. lenge.That is,increasing the performance of one of the (a)Errors in Distance Measurements metrics without degradation on others. Table 3 lists the typical measuring (intrinsic)error In all localization algorithms discussed above,nodes of a range of nowadays ranging techniques:TDoA,RSS should participate actively during a localization pro- in AHLoS25],Ultra Wideband system59),RF Time of cess,i.e.,sending or receiving radio signals,or mea- Flight ranging systemsl60l,and Elapsed Time between suring physical data.For some applications,however, the two Time of Arrival(EToA)in BeepBeepl301.In the to-be-locate objects cannot participate in localiza- general,RF-based techniques,e.g.,RSS,UWB and RF tion and it is also difficult to attach networked nodes ToF,can achieve the meter-level accuracy in a range to them.One typical application is intrusion detection, of tens of meters.Time-related methods have more ac- in which it is impossible and unreasonable to equip in- curate results in the order of centimeters,but require truders with locating devices.To tackle this issue,re- extra hardware and energy consumption. cently a novel concept of Device-Free Localization,also On the other hand,extrinsic errors are caused by en- called Transceiver-Free Localization,is proposed(57-581. vironmental factors or unexpected hardware malfunc- Device-free localization is envisioned to be able to de- tion,leaving difficulties on characterizing them.We will tect,localize,track,and identify entities free of devices. briefly discuss the state-of-the-art works on controlling and works by processing the environment changes col- the intrinsic and extrinsic errors in the following sub- lected at scattering monitoring points.Existing work sections of location refinement and robust localization, focuses on analyzing RSSI changes,and often suffers respectively. from high false positives.How to design a device-free localization system which can provide accurate loca- Table 3.Measurement Accuracy of Different tions is a challenging and promising research problem. Ranging Techniques Technology System Accuracy 2.3 Error Control for Network Localization Range TDoA AHLOS 2cm 310m 2.3.1 Noisy Distance Measurement RSS AHLOS 24m 30100m UWB PAL UWB 1.5m N/A Many localization algorithms are range-based and RF ToF RF ToF 13m 100m adopt distance ranging techniques,in which measur- EToA BeepBeep 1~2cm 10m ing errors are inevitable.Generally,these errors can be classified into two categories:extrinsic and intrin- (b)Negative Impact of Noisy Ranging Results sic.The extrinsic error is attributed to the physical Errors in distance ranging make localization more effects on the measurement channel,such as the pre- challenging in the following three aspects: sence of obstacles,multipath and shadowing effects, Uncertainty.Fig.14 illustrates an example of tri- and the variability of the signal propagation speed due lateration under noisy ranging measurements.Trila- to environmental dynamics.On the other hand,the teration often meets the situation that the three circles intrinsic error is caused by limitations of hardware and do not intersect at a common point.In other words,Yunhao Liu et al.: Location, Localization, and Localizability 285 Table 2. Comparative Study of Localization Algorithms Localization Algorithm Accuracy Node Beacon Computation Communication Error Density Percentage Cost Cost Propagation Centralized MDS High Low Low High High Low SDP High High Median High High Low Distributed Beacon based Low High High Low Low High* Coordinate stitching Low High Low Median Median High ∗: in case of iterative localization In conclusion, a number of typical localization ap￾proaches are surveyed and evaluated with various me￾trics in this section. All approaches have their own merits and drawbacks, making them suitable for differ￾ent applications. Hence, the design of a localization al￾gorithm should sufficiently investigate application pro￾perties, as well as take into account algorithm gener￾ality and flexibility. In present and foreseeable future study, obtaining a Pareto improvement is a major chal￾lenge. That is, increasing the performance of one of the metrics without degradation on others. In all localization algorithms discussed above, nodes should participate actively during a localization pro￾cess, i.e., sending or receiving radio signals, or mea￾suring physical data. For some applications, however, the to-be-locate objects cannot participate in localiza￾tion and it is also difficult to attach networked nodes to them. One typical application is intrusion detection, in which it is impossible and unreasonable to equip in￾truders with locating devices. To tackle this issue, re￾cently a novel concept of Device-Free Localization, also called Transceiver-Free Localization, is proposed[57-58] . Device-free localization is envisioned to be able to de￾tect, localize, track, and identify entities free of devices, and works by processing the environment changes col￾lected at scattering monitoring points. Existing work focuses on analyzing RSSI changes, and often suffers from high false positives. How to design a device-free localization system which can provide accurate loca￾tions is a challenging and promising research problem. 2.3 Error Control for Network Localization 2.3.1 Noisy Distance Measurement Many localization algorithms are range-based and adopt distance ranging techniques, in which measur￾ing errors are inevitable. Generally, these errors can be classified into two categories: extrinsic and intrin￾sic. The extrinsic error is attributed to the physical effects on the measurement channel, such as the pre￾sence of obstacles, multipath and shadowing effects, and the variability of the signal propagation speed due to environmental dynamics. On the other hand, the intrinsic error is caused by limitations of hardware and software. While the extrinsic one is more unpredictable and challenging during real deployments, the intrin￾sic one causes many complications when using multi￾hop measurements to estimate node locations. Results from field experiments demonstrated that even rela￾tively small ranging errors can significantly amplify the error of location estimates[52]; thus, dealing with such errors is an essential issue for high-accuracy localization algorithms. (a) Errors in Distance Measurements Table 3 lists the typical measuring (intrinsic) error of a range of nowadays ranging techniques: TDoA, RSS in AHLoS[25], Ultra Wideband system[59], RF Time of Flight ranging systems[60], and Elapsed Time between the two Time of Arrival (EToA) in BeepBeep[30]. In general, RF-based techniques, e.g., RSS, UWB and RF ToF, can achieve the meter-level accuracy in a range of tens of meters. Time-related methods have more ac￾curate results in the order of centimeters, but require extra hardware and energy consumption. On the other hand, extrinsic errors are caused by en￾vironmental factors or unexpected hardware malfunc￾tion, leaving difficulties on characterizing them. We will briefly discuss the state-of-the-art works on controlling the intrinsic and extrinsic errors in the following sub￾sections of location refinement and robust localization, respectively. Table 3. Measurement Accuracy of Different Ranging Techniques Technology System Accuracy Range TDoA AHLoS 2 cm 3∼10 m RSS AHLoS 2∼4 m 30∼100 m UWB PAL UWB 1.5 m N/A RF ToF RF ToF 1∼3 m 100 m EToA BeepBeep 1∼2 cm 10 m (b) Negative Impact of Noisy Ranging Results Errors in distance ranging make localization more challenging in the following three aspects: • Uncertainty. Fig.14 illustrates an example of tri￾lateration under noisy ranging measurements. Trila￾teration often meets the situation that the three circles do not intersect at a common point. In other words