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