On the displacement for covering a square with randomly placed sensors
Consider n sensors placed randomly and independently with the uniform distribution in a unit square. 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 unit square is completely covered, i.e., every point in the square 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:= Σn i=1 da i, for some constant a > 0. We assume that r and n are chosen so as to allow full coverage of the square and 0 < a ≤ 4. The main contribution of the paper is to show the existence of a tradeoff between the square sensing radius and a-total movement and can be summarized as follows: 1. If the square sensing radius is equal to 1/2√n and n is the square of a natural number we present an algorithm and show that in expectation the a-total movement is in O(n1-a/4). 2. If the square sensing radius is greater than 2√3/√n and n is natural number then we present an algorithm and show that in expectation the a-total movement is in O(n1-a/2(ln n)a/4). Therefore this sharp decrease from O(n1-a/4) to O(n1-a/2(ln n)a/4) in the a-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 1/2√n to 2√3/√n. In addition, we simulate our algorithms above and discuss the results of our simulations.
|Keywords||Displacement, Random, Sensors, Unit square|
Kapelko, R. (Rafał), & Kranakis, E. (2015). On the displacement for covering a square with randomly placed sensors. doi:10.1007/978-3-319-19662-6_11