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 sensorYunhao Liu et al.: Location, Localization, and Localizability 279 computed in this manner, a computational simplifica￾tion to determine this bounded region is to use rect￾angular 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 appro￾ximate point in triangle (APIT)[36]. Its novelty lies in how the regions are defined. Actually, bounding tri￾angles 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 inter￾section 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 tri￾angle by PIT test. Once this process is complete, the node simply finds the intersection of the reference tri￾angles that contains it and chooses the centroid as its position estimate, as illustrated in Fig.6(b). In this pro￾cess, APIT does not assume that nodes can really range to these beacons. The PIT test is based on geometry. For a given tri￾angle 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 mea￾surements are monotonic and calibrated to be compara￾ble but are not required to produce distance estimates. The second one assumes sufficient node density for ap￾proximating node movement. If no neighbor of M is further from/closer to all three anchors A, B, and C si￾multaneously, M assumes that it is inside triangle ABC. Otherwise, M assumes it resides outside this triangle. In practice, however, this approximation does not re￾alize 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 com￾municate 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 informa￾tion provided by the radio defines an unweighted graph, where the vertices are wireless nodes and edges repre￾sent 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 phys￾ical 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 com￾puted. Hence, if the hop count hij between two refer￾ences (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 con￾straints of wireless devices, hop count based localiza￾tion approaches are cost-effective alternatives to rang￾ing 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 be￾tween 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. Unfortu￾nately, anisotropic networks are more likely to exist in practice for several reasons. First, in many real appli￾cations, sensor nodes/seeds can rarely be uniformly de￾ployed over the field due to the geographical obstacles. Second, even if we assume that the initial sensor