Energy efficient data gathering with mobile sinks in hybrid sensor networks

The potential benefits of utilizing mobile sink(s) to prolong the wireless sensor network lifetime have aroused widespread attention. However, few provably theoretical results remain are developed in view of the complexity caused by time-dependent network topology. In this work, we investigate energy efficient hybrid sensor network design using mobile sink(s), which can be motivated by the practical GreenOrbs system application. In our model, the movement of mobile sinks is constrained to be on some predefined road-segments. Two different network structures are investigated: the one-hop structure in which each static sensor can be reached by the mobile sink at some stage of the movement, and the multi-hop structure where some sensors need the relay by other sensors to reach the sink. The challenge is to find a movement schedule of mobile sink that will minimize the energy cost while meet other constraints. In this work, we first show that the problem is NP-hard and then design an efficient movement scheme and theoretically prove that the total cost is within a constant factor of the optimum. We further present a scheduling solution using integer program for multi-hop structure, which can be computed in polynomial time. Particularly, we extensively study and evaluate the energy consumption for data gathering with multiple mobile sinks. Finally, we conduct extensive study of our method in a real wireless sensor network deployment composed of hundreds of static sensors. Extensive experiments validate the theoretical findings of our solution.