The directional sensor coverage problem with continuous orientation

We present a mixed integer non linear programming formulation of the Directional Sensors Continuous Coverage Problem (DSCCP), where a given set of targets in a plane are to be covered by a set of sensors whose location is known in advance. Sensors are supposed to be directional, that is characterized by a discrete set of possible radii and aperture angles. Decisions to be made are about orientation (which in our approach can vary continuously), radius and aperture angle of each sensor, taking into account possibility of keeping one or more sensors switched o. The objective is to get minimum cost coverage of all targets. We incorporate into the objective function penalty cost for possibly uncovered targets. We prove NP-hardness of DSCCP and introduce a Lagrangian relaxation model. A dual ascent procedure is also presented. It is based on acting on one multiplier at a time and it is completed by a heuristics to nd a feasible solution at each ascent iteration. Finally we report the results of the implementation of the method on a set of test problems.