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

Hyongju Park, Seth Hutchinson

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Article number6907154
Pages (from-to)2144-2149
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - Sep 22 2014
Event2014 IEEE International Conference on Robotics and Automation, ICRA 2014 - Hong Kong, China
Duration: May 31 2014Jun 7 2014

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Robust optimal deployment in mobile sensor networks with peer-to-peer communication'. Together they form a unique fingerprint.

Cite this