On synchronization and orientation in distributed barrier coverage with relocatable sensors

Abstract Consider n identical relocatable sensors, with sensing range r and visibility range 2r, initially placed at arbitrary positions on a line segment barrier; each sensor can detect the presence of an intruder in its sensing range, and is said to cover the portion of the barrier that intersects with its sensing range. Sensors operate in Look-Compute-Move cycles: in a cycle a sensor determines the positions of sensors in its visibility range, it computes its next position (within its visibility range), and then moves to the calculated position. The barrier coverage problem we consider is for the sensors to independently make decisions and movements so to reach final positions whereby they collectively cover the barrier; in particular we are interested in oblivious (or memoryless) sensors, and focus on the impact that the level of synchrony and the presence/absence of orientation (i.e., global notion of “left-right”) have on the solvability of the problem. It is known that without orientation, oblivious sensors can solve the problem if they are fully synchronous (i.e., they operate in synchronous rounds and are all active at every round). In this paper, we prove that orientation is critical to being able to solve the problem if we relax the assumption of full synchronization. We first show that if sensors are unoriented, then barrier coverage is unsolvable even in the semi-synchronous setting. In contrast, if sensors agree on a global orientation, then we give an algorithm for barrier coverage, even in the completely asynchronous setting. Finally, we extend the existing result of Cohen and Peleg and show that convergence to barrier coverage by unoriented sensors in the semi-synchronous model is possible with bounded visibility range 2 r + ρ (for arbitrarily small ρ > 0 ) and bounded mobility range r.