UC San Diego

We consider the problem of collecting data from stationary sensor nodes using controllable mobile nodes ("data mules") via wireless communication. Whereas the use of data mules can significantly reduce the energy consumption at sensor nodes, a drawback is an increased data delivery latency. Reducing the latency through optimizing the motion of data mules is critical for this approach to be useful. Since optimizing the motion of data mules is a hard problem in general, previous studies simplified the problem by using basic models for mobility and communications. These simplifications often lead to suboptimal solutions and also to algorithms that are only applicable to limited scenarios. To address these limitations, in this dissertation we present a problem framework that we call the Data Mule Scheduling (DMS) problem. The DMS problem captures the motion planning problem as the one composed of loosely connected subproblems. We first study the one dimensional case of the DMS (1-D DMS) problem, representing the speed control of data mule and the scheduling of data collection jobs. For different mobility models, we present optimal algorithms or non-existence of them, prove NP-hardness, and design an approximation algorithm to determine speed control and job schedule. We also design a heuristic algorithm for hard cases and demonstrate the good performance through simulation experiments by comparing with theoretical lower bounds. Furthermore, we show how the mathematical formulation of the 1-D DMS problem can be used as a proxy to solve speed scaling problems for dynamic power management of processors. For the two dimensional case that includes the planning of data mule's path, we formulate the path selection problem as a graph problem and design an approximation algorithm. We also explore the combination of data mule and multihop forwarding and demonstrate how this hybrid approach enable a flexible trade-off between node energy consumption and data delivery latency. In the end, we present some extensions of the DMS problem framework for the cases of multiple data mules and partially-known communication range. These cases allow the DMS framework to be applied to larger range of application scenarios under realistic radio environments.