Connected Wireless Camera Network Deployment with Visibility Coverage

We consider the problem of deployment of cameras inside a complex indoor setting for surveillance applications. We formulate the problem of the minimum guarding network that places a minimum number of cameras satisfying both visual coverage of the domain and wireless network connectivity. We prove that finding the minimum guarding network in both the geometric setting and discrete setting is NP-hard. We also give a 2-approximation algorithm to the geometric minimum guarding network. Motivated by the connection of this problem with the watchman tour problem and the art gallery problem, we develop two algorithms that generate satisfactory results in a prototype testbed and in our simulations.