  Sensor networks are ubiquitously used for detection and tracking and as a
result covering is one of the main tasks of such networks. We study the problem
of maximizing the coverage lifetime of a barrier by mobile sensors with limited
battery powers, where the coverage lifetime is the time until there is a
breakdown in coverage due to the death of a sensor. Sensors are first deployed
and then coverage commences. Energy is consumed in proportion to the distance
traveled for mobility, while for coverage, energy is consumed in direct
proportion to the radius of the sensor raised to a constant exponent. We study
two variants which are distinguished by whether the sensing radii are given as
part of the input or can be optimized, the fixed radii problem and the variable
radii problem. We design parametric search algorithms for both problems for the
case where the final order of the sensors is predetermined and for the case
where sensors are initially located at barrier endpoints. In contrast, we show
that the variable radii problem is strongly NP-hard and provide hardness of
approximation results for fixed radii for the case where all the sensors are
initially co-located at an internal point of the barrier.
