20150101
On the displacement for covering a square with randomly placed sensors
Publication
Publication
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 ith 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 atotal 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 atotal 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 atotal movement is in O(n1a/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 atotal movement is in O(n1a/2(ln n)a/4). Therefore this sharp decrease from O(n1a/4) to O(n1a/2(ln n)a/4) in the atotal 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.
Additional Metadata  

Keywords  Displacement, Random, Sensors, Unit square 
Persistent URL  dx.doi.org/10.1007/9783319196626_11 
Citation 
Kapelko, R. (Rafał), & Kranakis, E. (2015). On the displacement for covering a square with randomly placed sensors. doi:10.1007/9783319196626_11
