# Exact and Approximation Algorithms for Data Mule Scheduling in a
Sensor Network

## Jiemin Zeng, Stony Brook University

## February 9, 2016

We consider the fundamental problem of scheduling data mules for
managing a wireless sensor network. A data mule tours around a sensor
network and can help with network maintenance such as data collection
and battery recharging/replacement. We assume that each sensor has a
ﬁxed data generation rate and a capacity (upper bound on storage
size). If the data mule arrives after the storage capacity is met,
additional data generated is lost. In this paper we formulate several
fundamental problems for the best schedule of single or multiple data
mules and provide algorithms with provable performance. First, we
consider using a single data mule to collect data from sensors, and we
aim to maximize the data collection rate. We then generalize this
model to consider k data mules. Additionally, we study the problem of
minimizing the number of data mules such that it is possible for them
to collect all data, without loss. For the above problems, when we
assume that the capacities of all sensors are the same, we provide
exact algorithms for special cases and constant-factor approximation
algorithms for more general cases. We also show that several of these
problems are NP-hard. When we allow sensor capacities to diﬀer, we
have a constant-factor approximation for each of the aforementioned
problems when the ratio of the maximum capacity to the minimum
capacity is constant.