Yunhao Liu et al:Location,Localization,and Localizability 275 ·Routing Clustering brings numerous advantages on network op- Routing is a process of selecting paths in a net- erations,such as improving network scalability,local- work along which to send data traffic.Most routing izing the information exchange,stabilizing the network protocols for multi-hop wireless networks utilize physi- topology,and increasing network life time.Among all cal locations to construct forwarding tables and deliver possible solutions,location-based clustering approaches messages to the node closer to the destination in each are greatly efficient by generating non-overlapped clus- hop[16).Specifically,when a node receives a message, ters.In addition.location information can also be used local forwarding decisions are made according to the to rebuild clusters locally when new nodes join the net- positions of the destination and its neighboring nodes. work or some nodes suffer from hardware failurel24). Such geographic routing schemes require localized infor- mation,making the routing process stateless,scalable, 2 Localization and low-overhead in terms of route discovery. Network localization has attracted a lot of research ·Topology Control efforts in recent years.One method to determine the Topology control is one of the most important tech- location of a device is through manual configuration, niques used in wireless ad-hoc and sensor networks for which is often infeasible for large-scale deployments or saving energy and eliminating radio interferencel17-181. mobile systems.As a popular system,Global Position- By adjusting network parameters (e.g.,the transmit- ing System(GPS)is not suitable for indoor or under- ting range),energy consumption and interference can ground environments and suffers from high hardware be effectively reduced;meanwhile some global net- cost.Local Positioning Systems (LPS)rely on high- work properties (e.g.,connectivity)can still be well density base stations being deployed,an expensive bur- retained.Importantly,using location information as den for most resource-constrained wireless ad hoc net- a priori knowledge,geometry techniques (e.g.,spanner works. subgraphs and Euclidean minimum spanning trees)can be immediately applied to topology controll7l. The limitations of existing positioning systems mo- tivate a novel scheme of network localization.in which ·Coverage some special nodes (a.k.a.anchors or beacons)know Coverage reflects how well a sensor network observes their global locations and the rest determine their loca- the physical space;thus,it can be viewed as the quali- tions by measuring the geographic information of their ty of service (QoS)of the sensing function.Previ- local neighboring nodes.Such a localization scheme for ous designs fall into two categories.The probabilistic wireless multi-hop networks is alternatively described approaches]analyze the node density for ensuring as“cooperative'”,“ad-hoc”,“in-network localization” appropriate coverage statistically,but essentially have or"self localization",since network nodes cooperatively no guarantee on the result.In contrast,the geometric determine their locations by information sharing. approaches22]are able to obtain accurate and reliable In this section,we first review the state-of-the-art lo- results,in which locations are essential. calization approaches from two aspects:physical mea- ●Boundary Detection surements and network-wide localization algorithms. Boundary detection is to figure out the overall We then discuss a number of techniques for controlling boundary of an area monitored by a WSN.There are localization errors caused by noisy physical measure- two kinds of boundaries:the outer boundary showing ments and algorithmic defects. the under-sensed area,and the inner boundary indica- Almost all existing localization algorithms consist of ting holes in a network deployment.The knowledge of two stages:1)measuring geographic information from boundary facilitates the design of routing,load balanc- the ground truth of network deployment;2)computing ing,and network management23).As direct evidence, node locations according to the measured data.Geo- location information helps to identify border nodes and graphic information includes a variety of geometric re- further depict the network boundary. lationships from coarse-grained neighbor-awareness to ·Clustering fine-grained inter-node rangings (e.g.,distance or an- To facilitate network management,researchers of- gle).Based on physical measurements,localization al- ten propose to group sensor nodes into clusters and gorithms solve the problem that how the location infor- organize nodes hierarchically24.In general,ordinary mation from beacon nodes spreads network-wide.Gen- nodes only talk to the nodes within the same cluster, erally,the design of localization algorithms largely de- and the inter-cluster communications rely on a special pends on a wide range of factors,including resource node in each cluster.which is often called cluster head. availability,accuracy requirements,and deployment re- Cluster heads form a backbone of a network,based strictions;and no particular algorithm is an absolute on which the network-wide connectivity is maintained favorite across the spectrum.Yunhao Liu et al.: Location, Localization, and Localizability 275 • Routing Routing is a process of selecting paths in a net￾work along which to send data traffic. Most routing protocols for multi-hop wireless networks utilize physi￾cal locations to construct forwarding tables and deliver messages to the node closer to the destination in each hop[16]. Specifically, when a node receives a message, local forwarding decisions are made according to the positions of the destination and its neighboring nodes. Such geographic routing schemes require localized infor￾mation, making the routing process stateless, scalable, and low-overhead in terms of route discovery. • Topology Control Topology control is one of the most important tech￾niques used in wireless ad-hoc and sensor networks for saving energy and eliminating radio interference[17-18] . By adjusting network parameters (e.g., the transmit￾ting range), energy consumption and interference can be effectively reduced; meanwhile some global net￾work properties (e.g., connectivity) can still be well retained. Importantly, using location information as a priori knowledge, geometry techniques (e.g., spanner subgraphs and Euclidean minimum spanning trees) can be immediately applied to topology control[17] . • Coverage Coverage reflects how well a sensor network observes the physical space; thus, it can be viewed as the quali￾ty of service (QoS) of the sensing function. Previ￾ous designs fall into two categories. The probabilistic approaches[19-21] analyze the node density for ensuring appropriate coverage statistically, but essentially have no guarantee on the result. In contrast, the geometric approaches[22] are able to obtain accurate and reliable results, in which locations are essential. • Boundary Detection Boundary detection is to figure out the overall boundary of an area monitored by a WSN. There are two kinds of boundaries: the outer boundary showing the under-sensed area, and the inner boundary indica￾ting holes in a network deployment. The knowledge of boundary facilitates the design of routing, load balanc￾ing, and network management[23]. As direct evidence, location information helps to identify border nodes and further depict the network boundary. • Clustering To facilitate network management, researchers of￾ten propose to group sensor nodes into clusters and organize nodes hierarchically[24]. In general, ordinary nodes only talk to the nodes within the same cluster, and the inter-cluster communications rely on a special node in each cluster, which is often called cluster head. Cluster heads form a backbone of a network, based on which the network-wide connectivity is maintained. Clustering brings numerous advantages on network op￾erations, such as improving network scalability, local￾izing the information exchange, stabilizing the network topology, and increasing network life time. Among all possible solutions, location-based clustering approaches are greatly efficient by generating non-overlapped clus￾ters. In addition, location information can also be used to rebuild clusters locally when new nodes join the net￾work or some nodes suffer from hardware failure[24] . 2 Localization Network localization has attracted a lot of research efforts in recent years. One method to determine the location of a device is through manual configuration, which is often infeasible for large-scale deployments or mobile systems. As a popular system, Global Position￾ing System (GPS) is not suitable for indoor or under￾ground environments and suffers from high hardware cost. Local Positioning Systems (LPS) rely on high￾density base stations being deployed, an expensive bur￾den for most resource-constrained wireless ad hoc net￾works. The limitations of existing positioning systems mo￾tivate a novel scheme of network localization, in which some special nodes (a.k.a. anchors or beacons) know their global locations and the rest determine their loca￾tions by measuring the geographic information of their local neighboring nodes. Such a localization scheme for wireless multi-hop networks is alternatively described as “cooperative”, “ad-hoc”, “in-network localization”, or “self localization”, since network nodes cooperatively determine their locations by information sharing. In this section, we first review the state-of-the-art lo￾calization approaches from two aspects: physical mea￾surements and network-wide localization algorithms. We then discuss a number of techniques for controlling localization errors caused by noisy physical measure￾ments and algorithmic defects. Almost all existing localization algorithms consist of two stages: 1) measuring geographic information from the ground truth of network deployment; 2) computing node locations according to the measured data. Geo￾graphic information includes a variety of geometric re￾lationships from coarse-grained neighbor-awareness to fine-grained inter-node rangings (e.g., distance or an￾gle). Based on physical measurements, localization al￾gorithms solve the problem that how the location infor￾mation from beacon nodes spreads network-wide. Gen￾erally, the design of localization algorithms largely de￾pends on a wide range of factors, including resource availability, accuracy requirements, and deployment re￾strictions; and no particular algorithm is an absolute favorite across the spectrum