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 in￾compatible items. Under this mechanism, Sweeps can locate a large proposition of theoretically localizable nodes in a network. However, the worst case computa￾tion 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 ad￾dress the same problem. It has attracted a lot of re￾search 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 net￾work 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 sub￾regions. 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 sys￾tem registration procedure. Coordinate system regis￾tration finds a rigid transformation that maps points in one coordinate system to a different coordinate sys￾tem. 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 coordi￾nate system. Fig.12. Robust quadrilateral. Moore et al. [52] outline an approach that produces more robust local maps. Rather than using three ar￾bitrary 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 small￾est 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 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￾cal map failed to overlap sufficiently with neighboring maps. Moore et al. argue that this is acceptable be￾cause the orphaned nodes are the nodes most likely to display high error. They point out that “for many ap￾plications, 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 can￾not use nodes without locations for sensing, routing