Constructing Belt-barrier Providing -Quality of Monitoring with Minimum Camera Sensors

Abstract—A wireless sensor network is said to form a belt-barrier for a region if it is able to detect any object moving from outside the region to inside. Recently, Cheng and Tsai found if camera sensors are used to form a belt-barrier, the breadth of the barrier becomes an important quality factor to ensure high quality of monitoring (QoM). Then, they proposed the minimum-breadth belt-barrier construction problem ( (, 1)-B3CP) whose goal is to select a minimum number of camera sensors to form a-breadth belt-barrier, which ensures the width of the picture of any object which moves through the barrier is at least . In this paper, we perform more thorough investigation of the problem and introduce a new polynomial time exact algorithm for the problem under the assumption that the angle of each camera is fixed. Our simulation result shows our algorithm outperforms Cheng and Tsai’s algorithm. We also introduce a variation of (, 1)-B3CP, namely (; k)-B3CP, which aims to construct k node-disjoint-breadth belt-barrier for fault-tolerance purpose, propose a new heuristic algorithm for it, and conduct simulations to evaluate its performance. Index Terms—Wireless sensor network, camera sensor net-work, exact algorithm, graph theory, quality of monitoring. I