Placement and Orientation of Rotating Directional Sensors

Abstract

We analyze several new problems that arise from the use of rotating directional sensors. The coverage region of a rotating directional sensor is restricted to a certain direction, and its orientation varies at constant speed. For already placed rotating directional sensors, we consider three problems for which the goal is to minimize the dark time (i.e. uncovered time) of all point in the area. We also consider the problem of placement and orientation of the minimum number of sensors, so to reduce to zero the dark time of all points. In addition, we study barrier coverage problems, in which the goal is to detect all intruders (or the largest number of them) that are trying to cross the monitored area. We show that these problems are NP-hard and some of them also NP-hard to approximate. We provide approximations algorithms that are easy to decentralize, and hence allow the sensors to self organize themselves.