Energy-constrained ferry route design for sparse wireless sensor networks

WANG Yong(王勇), PENG Wei(彭伟), DOU Qiang(窦强), GONG Zheng-hu(龚正虎)

(College of Computer, National University of Defense Technology, Changsha 410073, China)

Abstract:In recent years, using message ferries as mechanical carriers of data has been shown to be an effective way to collect information in sparse wireless sensor networks. As the sensors are far away from each other in such highly partitioned scenario, a message ferry needs to travel a long route to access all the sensors and carry the data collected from the sensors to the sink. Typically, practical constraints (e.g., the energy) preclude a ferry from visiting all sensors in a single tour. In such case, the ferry can only access part of the sensors in each tour and move back to the sink to get the energy refilled. So, the energy-constrained ferry route design (ECFRD) problem is discussed, which leads to the optimization problem of minimizing the total route length of the ferry, while keeping the route length of each tour below a given constraint. The ECFRD problem is proved to be NP-hard problem, and the integer linear programming (ILP) formulation is given. After that, efficient heuristic algorithms are proposed to solve this problem. The experimental results show that the performances of the proposed algorithms are effective in practice compared to the optimal solution.

Key words:message ferry; energy-constrained route design; integer linear programming; wireless sensor networks