南京大学：《物联网技术导论 Introduction of Internet of Things》课程教学资源（参考文献）Location, Localization, and Localizability

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 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

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 measure￾ment. (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 connecti￾vity information. Based on that work, REP[41] is pro￾posed to deal with the “distance mismatch” problem in anisotropic networks. 2.1.5 Neighborhood Measurement The radio connectivity measurement can be con￾sidered 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 non￾overlapping) 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 ad￾vantage 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 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. 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 neigh￾bor proximity approach; while at the same time, it pro￾vides 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 ac￾curacy, 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 Computa￾Cost 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 tech￾nology 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 rela￾tive 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 rang￾ing accuracy of centimeter-level. UWB has a combination of attractive properties for in-building location systems. First, it is a non-line-of￾sight technology with a range of a few tens of meters, which makes it practical to cover large indoor areas; sec￾ond, it is easy to filter the signal to minimize the multi￾path distortions that are the main cause of inaccuracy in RF based location systems. With conventional RF, reflections in in-building environments distort the di￾rect path signal, making accurate pulse timing difficult; while with UWB, the direct path signal can be distin￾guished 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 cus￾tomized application of Multi-Dimensional Multiple Ac￾cess (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 trans￾mitted 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 can￾cel out the requirements for clock synchronization. This solution provides protection against multi-path propa￾gation and noise by its CSS modulation. To eliminate the effect of clock drift and offset, ranging measure￾ments are taken by both the tag and the reader to pro￾vide 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 environ￾ments. 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 al￾gorithms based on their computational organization. Centralized algorithms are designed to run on a cen￾tral machine with powerful computational capabilities. Network nodes collect environmental data and send back to a base station for analysis, after which the com￾puted positions are delivered back into the network. Centralized algorithms resolve the computational limi￾tations 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 inter￾node communication to compensate for the lack of cen￾tralized computing power, while at the same time to re￾duce the expensive node-to-sink communications. Dis￾tributed algorithms often use a subset of the data to locate each node independently, yielding an approxima￾tion of a corresponding centralized algorithm where all the data are considered and used to compute the posi￾tions of all nodes simultaneously. There are two impor￾tant 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 ap￾proaches, location information diffuses from beacons to the border of a network, which can be viewed as a top￾down manner. The second group of approaches per￾forms in a bottom-up manner, in which localization is originated in a local group of nodes in relative coordi￾nates. 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 in￾tuition 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 ) algo￾rithm 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