Optimizing sensor deployment with line-of-sight constraints: Theory and practice

Various non-isotropic sensors, such as acoustic, visible light, and infrared sensors, heavily rely on the line of the sight signal propagation to achieve desired sensing and monitoring quality in a complex environment. Although researchers have tested these sensing systems in many real scenarios, there is still limited theory to guide the sensor deployment with realistic sensing characteristics. In this paper, we design deployment algorithms for robust coverage under specific angle of arrival sensing requirements. We formulate the optimal deployment problem as a robust variant of the Art Gallery Problem called robust guarding, i.e., placing minimum number of transmitters such that all points of the domain are covered by two sensors from sufficiently different directions. We prove that this problem is NP-hard and provide combinatorial upper and lower bounds for the number of sensors needed. Furthermore, we show that n/2 guards are always sufficient and sometimes necessary for rectilinear polygons. In the system evaluation, we developed a testbed using low cost off-the-shelf IR sensors for indoor device-free localization. Experiments with both simulation and real system show that our solution outperforms existing algorithms on sensing accuracy and coverage significantly with almost negligible overhead.