1、Distributed localization in wireless sensor networks: a quantitative comparisonABSTRACTThis paper studies the problem of determining the node locations in ad-hoc sensor networks. We compare three distributed localization algorithms （Ad-hoc positioning, Robust positioning, and N-hop multi late ration
2、） on a single simulation platform. The algorithms share a common, three-phase structure: （1） determine nodeanchor distances, （2） compute node positions, and （3） optionally refine the positions through an iterative procedure. We present a detailed analysis comparing the various alternatives for each
3、phase, as well as a head-to-head comparison of the complete algorithms. The main conclusion is that no single algorithm performs best; which algorithm is to be preferred depends on the conditions （range errors, connectivity, anchor fraction, etc.）. In each case, however, there is significant room fo
4、r improving accuracy and/or increasing coverage1 INTRODUCTIONWireless sensor networks hold the promise of many new applications in the area of monitoring and control. Examples include target tracking, intrusion detection, wildlife habitat monitoring, climate control, and disaster management. The und
5、erlying technology that drives the emergence of sensor applications is the rapid development in the integration of digital circuitry, which will bring us small, cheap, autonomous sensor nodes in the near future.New technology offers new opportunities, but it also introduces new problems. This is par
6、ticularly true for sensor networks where the capabilities of individual nodes are very limited. Hence, collaboration between nodes is required, but energy conservation is a major concern, which implies that communication should be minimized. These conflicting objectives require unorthodox solutions
7、for many situations.A recent survey by Akyildiz et al. discusses a long list of open research issues that must be addressed before sensor networks can become widely deployed. The problems range from the physical layer （low-power sensing, processing, and communication hardware） all the way up to the
8、application layer （query and data dissemination protocols）. In this paper we address the issue of localization in ad-hoc sensor networks. That is, we want to determine the location of individual sensor nodes without relying on external infrastructure （base stations, satellites, etc.）.The localizatio
9、n problem has received considerable attention in the past, as many applications need to know where objects or persons are, and hence various location services have been created. Undoubtedly, the Global Positioning System （GPS） is the most well-known location service in use today. The approach taken
10、by GPS, however, is unsuitable for low-cost, ad-hoc sensor networks since GPS is based on extensive infrastructure （i.e., satellites）. Likewise solutions developed in the area of robotic and ubiquitous computing are generally not applicable for sensor networks as they require too much processing pow
11、er and energy.Recently a number of localization systems have been proposed specifically for sensor networks. We are interested in truly distributed algorithms that can be employed on large-scale ad-hoc sensor networks （100+ nodes）. Such algorithms should be:self-organizing （i.e., do not depend on gl
12、obal infrastructure）,robust （i.e., be tolerant to node failures and range errors）, energy efficient （i.e., require little computation and, especially, communication）.These requirements immediately rule out some of the proposed localization algorithms for sensor networks. We carried out a thorough se
13、nsitivity analysis on three algorithms that do meet the above requirements to determine how well they perform under various conditions. In particular, we studied the impact of the following parameters: range errors, connectivity （density）, and anchor fraction. These algorithms differ in their positi
14、on accuracy, network coverage, induced network traffic, and processor load. Given the （slightly） different design objectives for the three algorithms, it is no surprise that each algorithm outperforms the others under a specific set of conditions. Under each condition, however, even the best algorit
15、hm leaves much room for improving accuracy and/or increasing coverage.The main contributions of our work described in this paper are:we identify a common, three-phase, structure in the distributed localization algorithms.we identify a generic optimization applicable to all algorithms.we provide a de
16、tailed comparison on a single （simulation） platform.we show that there is no algorithm that performs best, and that there exists room for improvement in most cases.Section 2 discusses the selection, generic structure, and operation of three distributed localization algorithms for large-scale ad-hoc
17、sensor networks. These algorithms are compared on a simulation platform, which is described in Section 3. Section 4 presents intermediate results for the individual phases, while Section 5 provides a detailed overall comparison and an in-depth sensitivity analysis. Finally, we give conclusions in Se
18、ction 6.2 LOCALIZATION ALGORITHMSBefore discussing distributed localization in detail, we first outline the context in which these algorithms have to operate. A first consideration is that the requirement for sensor networks to be self-organizing implies that there is no fine control over the placem
19、ent of the sensor nodes when the network is installed （e.g., when nodes are dropped from an airplane）. Consequently, we assume that nodes are randomly distributed across the environment. For simplicity and ease of presentation we limit the environment to 2 dimensions, but all algorithms are capable
20、of operating in 3D. Fig. 1shows an example network with 25 nodes; pairs of nodes that can communicate directly are connected by an edge. The connectivity of the nodes in the network （i.e., the average number of neighbors） is an important parameter that has a strong impact on the accuracy of most loc
21、alization algorithms （see Sections 4 and 5）. It can be set initially by selecting a specific node density, and in some cases it can be set dynamically by adjusting the transmit power of the RF radio in each node.In some application scenarios, nodes may be mobile. In this paper, however, we focus on
22、static networks, where nodes do not move, since this is already a challenging condition for distributed localization. We assume that some anchor nodes have a priori knowledge of their own position with respect to some global coordinate system. Note that anchor nodes have the same capabilities （proce
23、ssing, communication, energy consumption, etc.） as all other sensor nodes with unknown positions; we do not consider approaches based on an external infrastructure with specialized beacon nodes （access points） as used in, for example, the GPS-less location system and the Cricket location system. Ide
24、ally the fraction of anchor nodes should be as low as possible to minimize the installation costs, and our simulation results show that, fortunately, most algorithms are rather insensitive to the number of anchors in the network.The final element that defines the context of distributed localization
25、is the capability to measure the distance between directly connected nodes in the network. From a cost perspective it is attractive to use the RF radio for measuring the range between nodes, for example, by observing the signal strength. Experience has shown, however, that this approach yields poor
26、distance estimates. Much better results are obtained by time-of- flight measurements, particularly when acoustic and RF signals are combined; accuracies of a few percent of the transmission range are reported. Our simulation results provide insight into the effect of the accuracy of the distance mea
27、surements on the localization algorithms.It is important to realize that the main three context parameters （connectivity, anchor fraction, and range errors） are dependent. Poor range measurements can be compensated for by using many anchors and/or a high connectivity. This paper provides insight in
28、the complex relation between connectivity, anchor fraction, and range errors for a number of distributed localization algorithms.2.1 GENERIC APPROACHFrom the known localization algorithms specifically proposed for sensor networks, we selected the three approaches that meet the basic requirements for
29、 self-organization, robustness, and energy-efficiency: Ad-hoc positioning by Niculescu and Nath , N-hop multilateration by Savvides et al, and Robust positioning by Savarese et al.The other approaches often include a central processing element, rely on an external infrastructure, or induce too much
30、communication. The three selected algorithms are fully distributed and use local broadcast for communication with immediate neighbors. This last feature allows them to be executed before any multi hop routing is in place, hence, they can support efficient location-based routing schemes like GAF.Alth
31、ough the three algorithms were developed independently, we found that they share a common structure. We were able to identify the following generic, three-phase approach 1 fordetermining the individual node positions：1. Determine the distances between unknowns and anchor nodes. 2. Derive for each no
32、de a position from its anchor distances.3. Refine the node positions using information about the range （distance） to, and positions of neighboring nodes.The original descriptions of the algorithms present the first two phases as a single entity, but we found that separating them provides two advantages. First, we obtain a better understanding of the combined behavior by studying intermediate results. Second, it becomes possible to mix-and-match alternatives for both phases to tailor the localization algorithm to the external conditions. The refinement p
