Analysis of the Threshold for Energy Consumption in Displacement of Random Sensors

The fundamental problem of energy-efficient reallocation of mobile random sensors to provide full coverage without interference is addressed in this paper. We consider n mobile sensors with the identical sensing range placed randomly on the unit interval and on the unit square. The sensors move from their initial random positions to the final locations so that: (a) every point on the unit interval or on the unit square is within the range of a sensor; (b) each pair of sensors is at a Euclidean distance greater than or equal to s; (c) the energy consumption for the movement of the sensors to the final positions is minimized. As a cost measure for the energy in the movement of sensors, we consider a-total movement defined as the sum [Formula: see text] , for some constant [Formula: see text] , provided that the i-th sensor is displaced the distance [Formula: see text]. The main contribution is summarized as follows: (1) if the sensors are placed on the unit interval, we explain the sharp increase around the sensing radius equal to [Formula: see text] and the interference distance equal to [Formula: see text] for the expected minimal a-total displacement; (2) if the sensors are placed on the unit square, we explain the sharp increase around the square sensing radius equal to [Formula: see text] and the interference distance equal to [Formula: see text] for the expected minimal a-total displacement. We designed and analysed three algorithms. The probabilistic analysis of our protocols is based on a novel mathematical theory of the Beta distribution.