Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Path Planning of Data Mules in Sensor Networks

Path Planning of Data Mules in Sensor Networks 1 Path Planning of Data Mules in Sensor Networks RYO SUGIHARA and RAJESH K. GUPTA, University of California, San Diego We study the problem of planning the motion of œdata mules  for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules signi cantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: nding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the bene t from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the of ‚ine plan using online http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Sensor Networks (TOSN) Association for Computing Machinery

Path Planning of Data Mules in Sensor Networks

Download PDF
27 pages

Loading next page...
 
/lp/association-for-computing-machinery/path-planning-of-data-mules-in-sensor-networks-51SYrvyTMD
Publisher
Association for Computing Machinery
Copyright
Copyright © 2011 by ACM Inc.
ISSN
1550-4859
DOI
10.1145/1993042.1993043
Publisher site
See Article on Publisher Site

Abstract

1 Path Planning of Data Mules in Sensor Networks RYO SUGIHARA and RAJESH K. GUPTA, University of California, San Diego We study the problem of planning the motion of œdata mules  for collecting the data from stationary sensor nodes in wireless sensor networks. Use of data mules signi cantly reduces energy consumption at sensor nodes compared to commonly used multihop forwarding approaches, but has a drawback in that it increases the latency of data delivery. Optimizing the motion of data mules, including path and speed, is critical for improving the data delivery latency and making the data mule approach more useful in practice. In this article, we focus on the path selection problem: nding the optimal path of data mules so that the data delivery latency can be minimized. We formulate the path selection problem as a graph problem that is capable of expressing the bene t from larger communication range. The problem is NP-hard and we present approximation algorithms for both single-data mule case and multiple-data mules case. We further consider the case in which we have only partial knowledge of communication range, where we design semionline algorithms that improve the of ‚ine plan using online

Journal

ACM Transactions on Sensor Networks (TOSN) – Association for Computing Machinery

Published: Aug 1, 2011

There are no references for this article.