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.
Closely related to our work is @cite_14 , where algorithm @math was analysed. In this paper, @math sensors were placed in the unit interval uniformly and independently at random and the cost of displacement was measured by the sum of the respective displacements of the individual sensors in the unit line segment @math Lets call the positions @math , for @math , anchor positions. The sensors have the sensing radius @math each. Notice that the only way to attain complete coverage is for the sensors to occupy the anchor positions. The following result was proved in @cite_14 .
@cite_14
1526254959
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.