Robust optimal deployment of mobile sensor networks

A common algorithm for deployment of a mobile sensor network in a bounded domain moves each sensor toward the centroid of its Voronoi cell. This algorithm is optimal for a particular cost function that is expressed as a sum over Voronoi cells, where the placement of a sensor in its own cell has no effect on cost in other cells. We provide a probabilistic interpretation of this “partitioned” cost function in the context of a target detection task, where each sensor has a chance of seeing the target that decreases monotonically with distance and where the goal is to minimize the total probability of missed detection. We show that the partitioned cost function is exactly the probability of missed detection given that a sensor can only see a target in its own Voronoi cell. We derive the probability of missed detection in the general case - where each sensor might see the target anywhere - and show that optimal sensor placement changes. Finally, we derive the probability of missed detection given the possibility of sensor failure, producing a robust measure of cost with respect to which optimal sensor placement is different yet again. Our results are illustrated by several examples in simulation.