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 analysis similar to the one for the line segment was provided for the unit square in @cite_14 . Our present paper focuses on the analysis of sensor displacement for a group of sensors placed uniformly at random on the @math dimensional unit cube, thus also generalizing the results of @cite_6 from @math to arbitrary dimension @math . In particular, our approach is the first to generalize the results of @cite_14 to the @math dimensional unit cube using as cost metric the @math -total movement, and also obtain sharper bounds for the case of the unit square.
@cite_14 @cite_6
1526254959 1163412417
Assume that n sensors with identical range r = f(n) 2n, for some f(n) > 1 for all n, are thrown randomly and independently with the uniform distribution in the unit interval [0,1]. They are required to move to new positions so as to cover the entire unit interval in the sense that every point in the interval is within the range of a sensor. We obtain tradeoffs between the expected sum and maximum of displacements of the sensors and their range required to accomplish this task. In particular, when f(n) = 1 the expected total displacement is shown to be Θ(√n). For sensors with larger ranges we present two algorithms that prove the upper bound for the sum drops sharply as f(n) increases. The first of these holds for f(n) ≥ 6 and shows the total movement of the sensors is O ( √In n (n)) while the second holds for 12 ≤ f(n) ≤ In n - 2 In In n and gives an upper bound of O(ln n f(n)ef(n) 2 ). Note that the second algorithm improves upon the first for f(n) δ In In n - In In Inn. Further we show a lower bound, for any 1 ω f(n) 0. For the case of the expected maximum displacement of a sensor when f(n) = 1 our bounds are (n -1 2) and for any e > 0, O(n-1 2+e). For larger sensor ranges (up to (1 - e)ln n n e > O) the expected maximum displacement is shown to be Θ(ln n n). We also obtain similar sum and maximum displacement and range tradeoffs for area coverage for sensors thrown at random in a unit square. In this case, for the expected maximum displacement our bounds are tight and for the expected sum they are within a factor of √ln n. Finally, we investigate the related problem of the expected total and maximum displacement for perimeter coverage (whereby only the perimeter of the region need be covered) of a unit square. For example, when n sensors of radius > 2 n are thrown randomly and independently with the uniform distribution in the interior of a unit square, we can show the total expected displacement required to cover the perimeter is n 12 + o(n). © 2013 ACM. Consider @math sensors placed randomly and independently with the uniform distribution in a unit square. 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 unit square is completely covered, i.e., every point in the squarei¾?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 thei¾? @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 square and @math . The main contribution of the paper is to show the existence of a tradeoff between the square sensing radius and @math -total movement and can be summarized as follows:1.If the square sensing radius is equal to @math and @math is the square of a natural number we present an algorithm and show that in expectation the @math -total movement is in @math .2.If the square sensing radius is greater than @math and @math is natural number then we present an algorithm and show that in expectation the @math -total movement is in @math . Therefore this sharp decrease from @math to @math in the @math -total movement of the sensors to attain complete coverage of the square indicates the presence of an interesting threshold on the square sensing radius when it increases from @math to @math . In addition, we simulate our algorithms above and discuss the results of our simulations.