Energy efficient data collection with mobile robots in heterogeneous sensor networks

In this paper, we study the problem of constructing a path for a mobile data collecting robot such that the total data collection cost (i.e., sum of transmission energy of the sensor nodes and movement energy of the robot) in a sensor network is minimized. We assume that the sensor nodes can transmit within a certain region around their position, which is called the communication set. We model the communication set as a convex set to take into account asymmetric transmission systems (like directional antennas). We derive a necessary condition for the optimality of a mobile robot tour through the communication sets. Based on this condition, we design a three-step approach to compute a local minimum of the optimization problem. We prove that our solution is guaranteed to be within a constant factor of the global optimal solution. Our algorithm works for both 2-dimensional and 3-dimensional sensor networks where the sensor nodes are heterogeneous and can have directional communication properties. In contrast, existing algorithms for computing data collecting routes are for planar sensor networks and assume the communication sets to be discs. We also present simulation results depicting the performance of our algorithm.