Lagrangian relaxation for the directional sensor coverage problem with continuous orientation

We present a mixed integer nonlinear programming formulation of the Directional Sensors Continuous Coverage Problem (DSCCP), where a given set of targets on a plane are to be covered by a set of sensors whose locations are known. Sensors are supposed to be directional, that is characterized by a discrete set of possible radii and aperture angles. The orientation (which is a continuous variable), the radius and the aperture angle of each sensor are to be decided, taking into account possibility of keeping one or more sensors switched off. The objective is to minimize cost coverage. We incorporate into the objective function penalty cost for possibly uncovered targets. We prove NP-hardness of DSCCP and introduce a Lagrangian relaxation model. We design a dual ascent procedure based on acting on a single multiplier at a time accompanied by a heuristics to find a feasible solution at each ascent iteration. We report also the results of the method on several test problems.