On the Displacement for Covering a d−dimensional Cube with Randomly Placed Sensors
Consider n sensors placed randomly and independently with the uniform distribution in a d−dimensional unit cube (d≥2). The sensors have identical sensing range equal to r, for some r>0. We are interested in moving the sensors from their initial positions to new positions so as to ensure that the d−dimensional unit cube is completely covered, i.e., every point in the d−dimensional cube is within the range of a sensor. If the i-th sensor is displaced a distance di, what is a displacement of minimum cost? As cost measure for the displacement of the team of sensors we consider the a-total movement defined as the sum Ma:=∑i=1ndia, for some constant a>0. We assume that r and n are chosen so as to allow full coverage of the d−dimensional unit cube and a>0. The main contribution of the paper is to show the existence of a tradeoff between the d−dimensional cube, sensing radius and a-total movement. The main results can be summarized as follows for the case of the d−dimensional cube. If the d−dimensional cube sensing radius is 2n1/d1 and n=md, for some m∈N, then we present an algorithm that uses O(n1−2da) total expected movement (see Algorithm 2 and Theorem 5). If the d−dimensional cube sensing radius is greater than (31/d−1)(31/d−1)33/d2n1/d1 and n is a natural number then the total expected movement is O(n1−2da(nlnn)2da) (see Algorithm 3 and Theorem 7). In addition, we simulate Algorithm 2 and discuss the results of our simulations.
