Consider @math sensors placed randomly and independently with the uniform distribution in a @math dimensional unit cube ( @math ). The sensors have identical sensing range equal to @math , for some @math . We are interested in moving the sensors from their initial positions to new positions so as to ensure that the @math dimensional unit cube is completely covered, i.e., every point in the @math dimensional cube is within the range of a sensor. If the @math -th sensor is displaced a distance @math , what is a displacement of minimum cost? As cost measure for the displacement of the team of sensors we consider the @math -total movement defined as the sum @math , for some constant @math . We assume that @math and @math are chosen so as to allow full coverage of the @math dimensional unit cube and @math . The main contribution of the paper is to show the existence of a tradeoff between the @math dimensional cube, sensing radius and @math -total movement. The main results can be summarized as follows for the case of the @math dimensional cube. If the @math dimensional cube sensing radius is @math and @math , for some @math , then we present an algorithm that uses @math total expected movement (see Algorithm 2 and Theorem 5). If the @math dimensional cube sensing radius is greater than @math and @math is a natural number then the total expected movement is @math (see Algorithm 3 and Theorem 7). In addition, we simulate Algorithm 2 and discuss the results of our simulations.
An important setting in considerations for barrier coverage is when the sensors are placed at random on the barrier according to the uniform distribution. Clearly, when the sensor dispersal on the barrier is random then coverage depends on the sensor density and some authors have proposed using several rounds of random dispersal for complete barrier coverage @cite_13 @cite_11 . Another approach is to have the sensors relocate from their initial position to a new position on the barrier so as to achieve complete coverage @cite_1 @cite_9 @cite_10 @cite_8 . Further, this relocation may be done in a centralized (cf. @cite_1 @cite_9 ) or distributed manner (cf. @cite_10 ).
@cite_13 @cite_8 @cite_9 @cite_1 @cite_10 @cite_11
2092860475 2125242971 1530465016 1965274367
We consider the k-barrier coverage problem, that is, the problem of deploying sensors on a border or perimeter to ensure that any intruder would be detected by at least k sensors. With random deployment of sensors, there is always a chance of gaps in coverage, thereby necessitating multiple rounds of deployment. In this paper, we study multi-round wireless sensor deployment on a border modeled as a line segment. We present two different classes of deployment strategies: complete and partial. In complete strategies, in every round, sensors are deployed over the entire border segment, while in partial strategies, sensors are deployed over only some part(s) of the border. First, we analyze the probability of k-coverage for any complete strategy as a function of parameters such as length of barrier to be covered, the width of the intruder, the sensing range of sensors, as well as the density of deployed sensors. Second, we propose two specific deployment strategies - Fixed-Density Complete and Fixed-Density Partial - and analyze the expected number of deployment rounds and expected total number of deployed sensors for each strategy. Next, we present a model for cost analysis of multi-round sensor deployment and calculate, for each deployment strategy, the expected total cost as a function of problem parameters and density of sensor deployment. Finally we find the optimal density of sensors in each round that minimizes the total expected cost of deployment for each deployment strategy. We validate our analysis by extensive 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. A set of sensors establishes barrier coverage of a given line segment if every point of the segment is within the sensing range of a sensor. Given a line segment I, n mobile sensors in arbitrary initial positions on the line (not necessarily inside I) and the sensing ranges of the sensors, we are interested in finding final positions of sensors which establish a barrier coverage of I so that the sum of the distances traveled by all sensors from initial to final positions is minimized. It is shown that the problem is NP complete even to approximate up to constant factor when the sensors may have different sensing ranges. When the sensors have an identical sensing range we give several efficient algorithms to calculate the final destinations so that the sensors either establish a barrier coverage or maximize the coverage of the segment if complete coverage is not feasible while at the same time the sum of the distances traveled by all sensors is minimized. Some open problems are also mentioned. Deploying wireless sensor networks to provide guaranteed barrier coverage is critical for many sensor networks applications such as intrusion detection and border surveillance. To reduce the number of sensors needed to provide guaranteed barrier coverage, we propose multi-round sensor deployment which splits sensor deployment into multiple rounds and can better deal with placement errors that often accompany sensor deployment. We conduct a comprehensive analytical study on multi-round sensor deployment and identify the tradeoff between the number of sensors deployed in each round of multi-round sensor deployment and the barrier coverage performance. Both numerical and simulation studies show that, by simply splitting sensor deployment into two rounds, guaranteed barrier coverage can be achieved with significantly less sensors comparing to single-round sensor deployment. Moreover, we propose two practical solutions for multi-round sensor deployment when the distribution of a sensor's residence point is not fully known. The effectiveness of the proposed multi-round sensor deployment strategies is demonstrated by numerical and simulation results.