Maximizing heterogeneous coverage in over and under provisioned visual sensor networks

We address “heterogeneous coverage” in visual sensor networks where coverage requirements of some randomly deployed targets vary from target to target. The main objective is to maximize the coverage of all the targets to achieve their respective coverage requirement by activating minimal sensors. The problem can be viewed as an interesting variation of the classical Max-Min problem (i.e., Maximum Coverage with Minimum Sensors (MCMS)). Therefore, we study the existing Integer Linear Programming (ILP) formulation for single and k-coverage MCMS problem in the state-of-the-art and modify them to solve the heterogeneous coverage problem. We also propose a novel Integer Quadratic Programming (IQP) formulation that minimizes the Euclidean distance between the achieved and the required coverage vectors. Both ILP and IQP give exact solution when the problem is solvable but as they are non-scalable due to their computational complexity, we devise a Sensor Oriented Greedy Algorithm (SOGA) that approximates the formulations. For under-provisioned networks where there exist insufficient number of sensors to meet the coverage requirements, we propose prioritized IQP and reduced-variance IQP formulations to capture prioritized and group wise balanced coverage respectively. Moreover, we develop greedy heuristics to tackle under provisioned networks. Extensive evaluations based on simulation illustrate the efficiency and efficacy of the proposed formulations and heuristics under various network settings. Additionally, we compare our methodologies and algorithm with two state-of-the-art algorithms available for target coverage and show that our methodologies and algorithm substantially outperform both the algorithms.