《无线传感器网络中英文对照外文翻译文献.docx》由会员分享，可在线阅读，更多相关《无线传感器网络中英文对照外文翻译文献.docx（26页珍藏版）》请在三一办公上搜索。
1、无线传感器网络中英文对照外文翻译文献中英文对照外文翻译文献 (文档含英文原文和中文翻译) 原文： 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 positioni
2、ng, Robust positioning, and N-hop multi late ration) on a single simulation platform. The algorithms share a common, three-phase structure: (1) 1 determine nodeanchor distances, (2) compute node positions, and (3) optionally refine the positions through an iterative procedure. We present a detailed
3、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.)
4、. 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 monito
5、ring, 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 opportu
6、nities, 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. Th
7、ese 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, proce
8、ssing, 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 infrast
9、ructure (base stations, satellites, etc.). 2 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 w
10、ell-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
11、 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 al
12、gorithms 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 localizat
13、ion 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 (densit
14、y), 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
15、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 3 algorithms. we identif
16、y 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 operat
17、ion 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
18、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 t
19、o 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
20、 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 a
21、n 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 appli
22、cation 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 4 nodes have a priori knowledge of their own position with respect to some globa
23、l 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, f
24、or 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 ne
25、twork. 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 s
26、ignal 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 simulati
27、on 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
28、 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 senso
29、r networks, we selected the three approaches that meet the basic requirements for self-organization, robustness, and energy-efficiency: 5 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
30、 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 p
31、lace, 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 positio
32、ns： 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 fi
33、rst 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 algori
34、thm 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
35、 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 6 compatibility with the alternatives. During our simulations we observed that we occasional
36、ly 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 di
37、stances 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 appr
38、oach, 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 info
39、rmation 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 informati
40、on when enough anchors have been located. This simple optimization presented in 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
41、 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 st
42、arts 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 7 length and forwards (broadcasts) the message if the flood limit allows it to do so. Another constraint is that when the node has received
43、 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-
44、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 h
45、ops 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 Su
46、m-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. Whe
47、never 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
48、. 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 ve
49、ry 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, 8 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:
