Data Mule Scheduling in Sensor Networks: Scheduling under Location and Time Constraints

Ryo Sugihara and Rajesh Gupta
CS2007-0911
October 29, 2007

Unlike multi-hop forwarding, an alternative and relatively new approach for efficient data collection in sensor networks is to exploit the mobility. Particularly, we consider collecting data from static sensor nodes using a “data mule” via wireless communication. A data mule is a mobile node that has wireless communication capability and also a sufficient amount of storage to store the data from the sensors in the field. A data mule travels across the sensing field and collects data from each sensor node when the distance is short, and later deposits all the data to the base station. In this way, each sensor node can conserve a significant amount of energy, since it only needs to send the data over a shorter distance and has no need to forward other sensors’ data all the way to the base station. In this paper, we are interested in the following problem: “how to control a data mule such that it collects data from all the nodes in the minimal amount of time”. We call it the data mule scheduling problem, as we formulate it as a scheduling problem, viewing communication from each node as a job. We can control the movement of the data mule (path, speed) as well as its communication (i.e., which node it collects data from at certain time duration), where the latter corresponds to job allocation in classical scheduling problems. Despite the similarities, one of most notable differences from real-time scheduling is that the data mule scheduling problem has location constraints as well as time constraints. Availability of each job is determined by the range of wireless communication, which primarily depends on the distance from a node and thus serves as a location constraint. On the other hand, by assuming the bandwidth of wireless communication is constant, we also have a time constraint for each node necessary for transmitting the data to a data mule. The movement of data mule determines how the location constraints map to time constraints and produces different real-time scheduling problems.


How to view this document


The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.


[ Search ]


NCSTRL
This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu