Robust optimal deployment in mobile sensor networks with peer-to-peer communication

This paper presents a distributed robust deployment algorithm for optimal coverage by a mobile sensor network (MSN). Much past research has focused on versions of the coverage problem that partition the workspace into regions, and then assign exactly one sensor to cover each region. For this case it has been shown that the optimal partition is the Voronoi partition, and that Lloyd´s algorithm converges to the optimal solution, with each sensor located at the centroid of its Voronoi region. In this paper, we consider the case in which k sensors are assigned to each region in the partition, in order to obtain coverage that is robust to sensor failure. For this case, we prove that the optimal workspace partition is the order-k Voronoi partition, with each sensor assigned to those order-k Voronoi regions for which it is a generator. The collection of these regions for a given sensor defines its effective sensing region (ESR), and we prove that in the optimal configuration each sensor is located at the centroid of its ESR. Finally we introduce a distributed algorithm for our optimal sensor placement problem that requires only simple peer-to-peer (P2P) communications. We show via simulation results that our algorithm converges in finite time, and provides competitive coverage performance in the presence of individual node failures.