We propose efficient distributed algorithms to aid navigation of a user through a geographic area covered by sensors. The sensors sense the level of danger at their locations and we use this information to find a safe path for the user through the sensor field. Traditional distributed navigation algorithms rely upon flooding the whole network with packets to find an optimal safe path. To reduce the communication expense, we introduce the concept of a skeleton graph which is a sparse subset of the true sensor network communication graph. Using skeleton graphs we show that it is possible to find approximate safe paths with much lower communication cost. We give tight theoretical guarantees on the quality of our approximation and by simulation, show the effectiveness of our algorithms in realistic sensor network situations.
The concept of minimum exposure path were introduced by Meguerdichian et. al. @cite_6 . Veltri et. al. @cite_8 has given heuristics to distributedly compute minimal and maximal exposure paths in sensor networks. Path planning in the context of sensor networks was addressed by Li et. al. @cite_3 where they consider the problem of finding minimum exposure path. Their approach involves exhaustive search over the whole network to find the minimal exposure path. Recently Liu et.al. @cite_2 have used the concept of searching a sparse subgraph to implement algorithms for resource discovery in sensor networks. This work, which was carried out independently of us, however doesn't address the problem of path finding when parts of the sensor network is blocked due to danger. Some of our work is inspired by the mesh generation problem @cite_4 @cite_5 in computational geometry.
@cite_4 @cite_8 @cite_3 @cite_6 @cite_2 @cite_5
2167477163 1991523989 2128445255 2125242971
Sensor networks not only have the potential to change the way we use, interact with, and view computers, but also the way we use, interact with, and view the world around us. In order to maximize the effectiveness of sensor networks, one has to identify, examine, understand, and provide solutions for the fundamental problems related to wireless embedded sensor networks. We believe that one of such problems is to determine how well the sensor network monitors the instrumented area. These problems are usually classified as coverage problems. There already exist several methods that have been proposed to evaluate a sensor network's coverage.We start from one of such method and provide a new approach to complement it. The method of using the minimal exposure path to quantify coverage has been optimally solved using a numerical approximation approach. The minimal exposure path can be thought of as the worst-case coverage of a sensor network. Our first goal is to develop an efficient localized algorithm that enables a sensor network to determine its minimal exposure path. The theoretical highlight of this paper is the closed-form solution for minimal exposure in the presence of a single sensor. This solution is the basis for the new and significantly faster localized approximation algorithm that reduces the theoretical complexity of the previous algorithm. On the other hand, we introduce a new coverage problem - the maximal exposure path - which is in a sense the best-case coverage path for a sensor network. We prove that the maximal exposure path problem is NP-hard, and thus, we provide heuristics to generate approximate solutions.In addition, we demonstrate the effectiveness of our algorithms through several simulations. In the case of the minimal single-source minimal exposure path, we use variational calculus to determine exact solutions. For the case of maximal exposure, we use networks with varying numbers of sensors and exposure models. Wireless ad-hoc sensor networks will provide one of the missing connections between the Internet and the physical world. One of the fundamental problems in sensor networks is the calculation of coverage. Exposure is directly related to coverage in that it is a measure of how well an object, moving on an arbitrary path, can be observed by the sensor network over a period of time. In addition to the informal definition, we formally define exposure and study its properties. We have developed an efficient and effective algorithm for exposure calculation in sensor networks, specifically for finding minimal exposure paths. The minimal exposure path provides valuable information about the worst case exposure-based coverage in sensor networks. The algorithm works for any given distribution of sensors, sensor and intensity models, and characteristics of the network. It provides an unbounded level of accuracy as a function of run time and storage. We provide an extensive collection of experimental results and study the scaling behavior of exposure and the proposed algorithm for its calculation. We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits. In particular, using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution Δ in localizing a target's trajectory is of the order of 1overρ R, where R is the sensing radius and ρ is the sensor density per unit area. Using an Occam's razor approach, we then design a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a "lowpass" approximation of the trajectory is attainable, and explore the implications of this obervation for estimating the target's velocity.We show through simulation the effectiveness of the geometric algorithm in tracking both the trajectory and the velocity of the target for idealized models. For non-ideal sensors exhibiting sensing errors, the geometric algorithm can yield poor performance. We show that non-idealities can be handled well using a particle filter based approach, and that geometric post-processing of the output of the Particle Filter algorithm yields an economical path description as in the idealized setting. Finally, we report on our lab-scale experiments using motes with acoustic sensors to validate our theoretical and simulation results. We study the problem of achieving maximum barrier coverage by sensors on a barrier modeled by a line segment, by moving the minimum possible number of sensors, initially placed at arbitrary positions on the line containing the barrier. We consider several cases based on whether or not complete coverage is possible, and whether non-contiguous coverage is allowed in the case when complete coverage is impossible. When the sensors have unequal transmission ranges, we show that the problem of finding a minimum-sized subset of sensors to move in order to achieve maximum contiguous or non-contiguous coverage on a finite line segment barrier is NP-complete. In contrast, if the sensors all have the same range, we give efficient algorithms to achieve maximum contiguous as well as non-contiguous coverage. For some cases, we reduce the problem to finding a maximum-hop path of a certain minimum (maximum) weight on a related graph, and solve it using dynamic programming.