Given a set of directional visual sensors, the @math -coverage problem determines the orientation of minimal directional sensors so that each target is covered at least @math times. As the problem is NP-complete, a number of heuristics have been devised to tackle the issue. However, the existing heuristics provide imbalance coverage of the targets--some targets are covered @math times while others are left totally uncovered or singly covered. The coverage imbalance is more serious in under-provisioned networks where there do not exist enough sensors to cover all the targets @math times. Therefore, we address the problem of covering each target at least @math times in a balanced way using minimum number of sensors. We study the existing Integer Linear Programming (ILP) formulation for single coverage and extend the idea for @math -coverage. However, the extension does not balance the coverage of the targets. We further propose Integer Quadratic Programming (IQP) and Integer Non-Linear Programming (INLP) formulations that are capable of addressing the coverage balancing. As the proposed formulations are computationally expensive, we devise a faster Centralized Greedy @math -Coverage Algorithm (CGkCA) to approximate the formulations. Finally, through rigorous simulation experiments we show the efficacy of the proposed formulations and the CGkCA.
@cite_3: Visual sensor networks (VSNs) are becoming increasingly popular in a number of application domains. A distinguishing characteristic of VSNs is to self-configure to minimize the need for operator control and to improve scalability. One of the areas of self-configuration is camera coverage control that is, how should cameras adjust their field-of-views to cover maximum targetsq This is an NP-hard problem. We show that the existing heuristics have a number of weaknesses that influence both coverage and overhead. Therefore, we first propose a computationally efficient centralized heuristic that provides near-optimal coverage for small-scale networks. However, it requires significant communication and computation overhead, making it unsuitable for large-scale networks. Thus, we develop a distributed algorithm that outperforms the existing distributed algorithm with lower communication overhead, at the cost of coverage accuracy. We show that the proposed heuristics guarantee to cover at least half of the targets covered by the optimal solution. Finally, to gain benefits of both centralized and distributed algorithms, we propose a hierarchical algorithm where cameras are decomposed into neighborhoods that coordinate their coverage using an elected local coordinator. We observe that the hierarchical algorithm provides scalable near-optimal coverage with networking cost significantly less than that of centralized and distributed solutions.
@cite_7: Sensor nodes may be equipped with a "directional" sensing device (such as a camera) which senses a physical phenomenon in a certain direction depending on the chosen orientation. In this article, we address the problem of selection and orientation of such directional sensors with the objective of maximizing coverage area. Prior works on sensor coverage have largely focused on coverage with sensors that are associated with a unique sensing region. In contrast, directional sensors have multiple sensing regions associated with them, and the orientation of the sensor determines the actual sensing region. Thus, the coverage problems in the context of directional sensors entails selection as well as orientation of sensors needed to activate in order to maximize ensure coverage. In this article, we address the problem of selecting a minimum number of sensors and assigning orientations such that the given area (or set of target points) is k-covered (i.e., each point is covered k times). The above problem is NP-complete, and even NP-hard to approximate. Thus, we design a simple greedy algorithm that delivers a solution that k-covers at least half of the target points using at most M log(k|C|) sensors, where |C| is the maximum number of target points covered by a sensor and M is the minimum number of sensor required to k-cover all the given points. The above result holds for almost arbitrary sensing regions. We design a distributed implementation of the above algorithm, and study its performance through simulations. In addition to the above problem, we also look at other related coverage problems in the context of directional sensors, and design similar approximation algorithms for them.
@cite_12: We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.
There exist quite a few works using directional sensors. Jing and Abouzeid @cite_12 formulate the coverage problem using directional sensors as Maximum Coverage using Minimum Sensors (MCMS) problem, and provide both centralized and decentralized greedy solutions. In @cite_3 , Munishwar and Abu-Ghazaleh present new algorithm which improves the greedy approaches of @cite_12 . The optimal solution to @math -coverage problem has been proved to be NP-hard by Fusco and Gupta in @cite_7 . They also modelled the sensors to have a fixed viewing angle and overlapping pans. However, all of these works overlooked the coverage imbalance issue.