Optimal Deployment of Energy-Harvesting Directional Sensor Networks for Target Coverage

The technology of harvesting energy from the natural environment can be used to overcome the energy limitation of wireless sensor networks. In this paper, we consider the problem of deploying energy-harvesting directional sensor networks for optimal target coverage. It involves the directional sensing coverage, communication route selection, and energy neutral operation. We formulate it as a mixed integer linear programming model, and propose three heuristics to solve it, i.e., a linear program-based heuristic (LPBH), a two-stage heuristic (TSH), and a sensing- and routing-integrated greedy heuristic (SRIGH). Their approximation upper bounds and time complexities are analyzed. Finally, we conduct extensive simulation experiments to evaluate and compare them. Simulation results show that TSH is the fastest one among them, but achieves the lowest success rate and solution quality. LPBH and SRIGH can achieve roughly equal success rate and solution quality, and LPBH is the most time-consuming.