中英文对照外文翻译文献
(文档含英文原文和中文翻译)
原文：
Distributed localization in wireless sensor networks: a
quantitative comparison
ABSTRACT
This 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) on a single simulation platform. The algorithms share a common, three-phase structure: (1)
determine node–anchor 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 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 for improving accuracy and/or increasing coverage
1 INTRODUCTION
Wireless 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 underlying 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 particularly 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 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 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 localization 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 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 power 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 global 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 sensitivity 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 position 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 algorithm 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 detailed 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 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 Section 6.
2 LOCALIZATION ALGORITHMS
Before 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 placement 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 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 localization 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 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 (processing, 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. Ideally 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 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 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 measurements 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 the complex relation between connectivity, anchor fraction, and range errors for a number of distributed localization algorithms.
2.1 GENERIC APPROACH
From the known localization algorithms specifically proposed for sensor networks, we selected the three approaches that meet the basic requirements for 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 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.
Although 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 for
determining the individual node positions：
1. Determine the distances between unknowns and anchor nodes.
2. Derive for each node 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 phase is optional and may be included to obtain more accurate locations.
In the remainder of this section we will describe the three phases (distance, position, and refinement) in detail. For each phase we will enumerate the alternatives as found in the original descriptions. Table 1 gives the breakdown into phases of the three approaches. When applicable we also discuss (minor) adjustments to (parts of) the individual algorithms that were needed to ensure
compatibility with the alternatives. During our simulations we observed that we occasionally operated (parts of) the algorithms outside their intended scenarios, which deteriorated their performance. Often, small improvements brought their performance back in line with the alternatives.
2.2 PHASE: DISTENCE TO ANCHORS
In this phase, nodes share information to collectively determine the distances between individual nodes and the anchors, so that an (initial) position can be calculated in Phase 2. None of the Phase 1 alternatives engages in complicated calculations, so this phase is communication bounded. Although the three distributed localization algorithms each use a different approach, they share a common communication pattern: information is flooded into the network, starting at the anchor nodes. A network-wide flood by some anchor A is expensive since each node must forward as information to its (potentially) unaware neighbors. This implies a scaling problem: flooding information from all anchors to all nodes will become much too expensive for large networks, even with low anchor fractions. Fortunately a good position can be derived in Phase 2 with knowledge (position and distance) from a limited number of anchors. Therefore nodes can simply stop forwarding information when enough anchors have been ‗‗located‘‘. This simple optimization presented i n the Robust positioning approach proved to be highly effective in controlling the amount of communication (see Section 5.3). We modified the other two approaches to include a flood limit as well.
2.2.1 SUM-DIST
The simple solution for determining the distance to the anchors is simply adding the ranges encountered at each hop during the network flood. This is the approach taken by the N-hop multi late ration approach, but it remained nameless in the original description; we name it Sum-dist in this paper. Sum-dist starts at the anchors which send a message including their identity, position, and a path length set to 0. Each receiving node adds the measured range to the path
length and forwards (broadcasts) the message if the flood limit allows it to do so. Another constraint is that when the node has received information about the particular anchor before, it is only allowed to forward the message if the current path length is less than the previous one. The end result is that each node will have stored the position and minimum path length to at least flood limit anchors.
2.2.2 DV-HOP
A drawback of Sum-dist is that range errors accumulate when distance information is propagated over multiple hops. This cumulative error becomes significant for large networks with few anchors (long paths) and/or poor ranging hardware. A robust alternative is to use topological information by counting the number of hops instead of summing the (erroneous) ranges. This approach was named DV-hop by Niculescu and Nath, and Hop-TERRAIN by Savarese et al. Since the results of DV-hop were published first we will use this name.
DV-hop essentially consists of two flood waves. After the first wave, which is similar to Sum-dist, nodes have obtained the position and minimum hop count to at least flood limit anchors. The second calibration wave is needed to convert hop counts into distances such that Phase 2 can compute a position. This conversion consists of multiplying the hop count with an average hop distance. Whenever an anchor a1 infers the position of another anchor a2 during the first wave, it computes the distance between them, and divides that by the number of hops to derive the average hop distance between a1 and a2. When calibrating, an anchor takes all remote anchors into account that it is aware of. Nodes forward (broadcast) calibration messages only from the first anchor that calibrates them, which reduces the total number of messages in the network.
2.2.3 EUCLIDEAN
A drawback of DV-hop is that it fails for highly irregular network topologies, where the variance in actual hop distances is very large. Niculescu and Nath have proposed another method, named Euclidean, which is based on the local geometry of the nodes around an anchor. Again anchors initiate a flood,
but forwarding the distance is more complicated than in the previous cases. When a node has received messages from two neighbors that know their distance to the anchor, and to each other, it can calculate the distance to the anchor. Fig. 2 shows a node (_Self_) that has two neighbors: n1 and n2 with distance estimates to an anchor. Together with the known ranges c, d, and e, Euclidean arrives at two possible values (r1 and r2) for the distance of the node to the anchor. Niculescu describes two methods to decide on which, if any, distance to use. The neighbor vote method can be applied if there is a third neighbor (n3) that has a distance estimate to the anchor and that is connected to either n1 or n2. Replacing n2 (or n1) by n3 will again yield a pair of distance estimates. The correct distance is part of both pairs, and is selected by a simple voting. Of course, more neighbors can be included to make the selection more accurate.
The second selection method is called common neighbor and can be applied if node n3 is connected to both n1 and n2. Basic geometric reasoning leads to the conclusion that the anchor and n3 are on the same or opposite side of the mirroring line n1–n2, and similarly whether or not self and n3 are on the same side. From this it follows whether or not self and the anchor lay on the same side.
To handle the uncertainty introduced by range errors Niculescu implements a safety mechanism that rejects ill-formed (flat) triangles, which can easily derail the selection process by ‗neighbor vote‘ and ‗common neighbor‘. This check verifies that the sum of the two smallest sides exceeds the largest side multiplied by a threshold, which is set to two times the range variance. For example, the triangle Self-n1–n2 in Fig. 2 is accepted when c + d > (1 + 2RangeVar) * e. Note that the safety check becomes as strict as the range variance increases. This leads to a lower coverage, defined as the percentage of non-anchor nodes for which a position was determined
2.3 PHASE: NODE POSITION
In the second phase nodes determine their position based on the distance estimates to a number of anchors provided by one of the three Phase 1
alternatives (Sum-dist, DV-hop, or Euclidean).The Ad-hoc positioning and Robust positioning approaches use late ration for this purpose. N-hop multi late ration, on the other hand, uses a much simpler method, which we named Min –max. In both cases the determination of the node positions does not involve additional communication.
2.3.1 LATERATION
The most common method for deriving a position is late ration, which is a form of triangulation. From the estimated distances and known positions of the anchors we derive the following system of equations:
The unknown position is denoted by. The system can be lined by subtracting the last equation from the first n _ 1 equations
Reordering the terms gives a proper system of linear equations in the form Ax=b, where
The system is solved using a standard least-squares approach. In exceptional cases the matrix inverse cannot be computed and late ration fails. In the majority of the cases, however, we succeed in computing a location estimate. We run an additional sanity check by computing the residue between the given distances and the distances to the location estimate
A large residue signals an inconsistent set of equations; we reject the
location ^x when the length of the residue exceeds the radio range.
2.3.2 MIN-MAX
Late ration is quite expensive in the number of floating point operations that is required. A much simpler method is presented by Savvides et al. as part of the N-hop multi late ration approach. The main idea is to construct a bounding box for each anchor using its position and distance estimate, and then to determine the intersection of these boxes. The position of the node is set to the center of the intersection box. Fig. 3 illustrates the Min–max method for a node with distance estimates to three anchors. Note that the estimated position by Min–max is close to the true position computed through late ration (i.e., the intersection of the