498
Optimization of Full-View Barrier Coverage with Rotatable Camera Sensors
Xiaofeng Gao, Rui Yang, Fan Wu, Guihai Chen and Jingguang Zhou
Shanghai Jiao Tong University, University of Illinois Urbana-Champaign, Shanghai Jiao Tong University, Shanghai Jiao Tong University, Shanghai Jiao Tong University

In all the researches in wireless sensor networks, cameras are increasingly utilized for their surveillance capabilities. In this paper, we elaborately discuss about the problem of Full-View Barrier Coverage with Rotatable Camera Sensors (FBR), including weakly and strongly connected versions. FBR is proven to be NP-hard in this paper by reducing Group Steiner Tree problem to it. Our goal is to reduce sensor number when guaranteeing the surveillance capabilities at the same time. Correspondingly, we introduce a novel weighed graph structure called Full-View Barrier Graph. We transform weak version problem into a pseudo one-dimension one and propose WGraProj algorithm with the help of dynamic programming; in strong version problem, we introduce two centralized algorithms (S-Dijkstra, S-Thorup), respectively aiming to save sensor number and to reduce time complexity. Moreover, we rigorously analyze the correctness and time complexity for each algorithm. In addition, the mass number of experiments are conducted to validate the efficiency of all algorithms, which prove that our structures and algorithms can construct a full-view barrier with fewer camera sensors compared with previous researches.