The coverage problem in visual sensor networks

A visual sensor network (VSN) consists of a number of self-configurable visual sensors with adjustable spherical sectors of limited angle (often known as Field of View) that are meant to cover a number of targets randomly positioned over a deployment area. One of the fundamental problems of VSNs is to cover maximum number of targets using minimum number of sensors. This classical MinMax problem is known to be NP-hard. The existing heuristics have a number of weaknesses that influence their coverage. Therefore, we present novel centralized heuristics that provide near-optimal coverage by prioritizing the targets that are coverable by fewer cameras. We also provide approximation bounds for both existing heuristics and the proposed heuristics and theoretically proved that in certain scenarios, the proposed heuristics outperform the existing ones. Finally, we provide performance comparison of the new heuristics with other heuristics through extensive simulation experiments using synthetic data set of successively increasing size.