A multiobjective evolutionary algorithm for surveillance sensor placement

Automated or semiautomated surveillance monitoring involves movement tracking and sensor handoff. In order to track moving objects over a large area, sensor coverage needs to overlap significantly. Overlapping coverage can be modeled using the concept of backup coverage, a location modeling approach that seeks to maximize primary and backup coverage simultaneously. This kind of sensor placement problem belongs to the class of NP-hard combinatorial optimization problems, so computational difficulty is expected when solving large problem instances, not to mention the need for dealing with multiple objectives. Beyond this, backup coverage for supporting sensor placement actually brings about confounding problem instances for branch-and-bound approaches because of the trade-off between primary and backup coverage. To address these difficulties, this paper develops a multiobjective evolutionary algorithm for the backup coverage problem to support sensor placement. The solutions of this algorithm are evaluated in terms of computational requirements and solution quality.