Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network
Speaker:Jiemin Zeng
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 10 September 2015
Duration:30 Minutes
Building:E1 4
We consider the 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 fixed 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 differ, 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.
Name(s):Mayank Goswami
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Created by:Mayank Goswami, 09/02/2015 12:13 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Mayank Goswami, 09/05/2015 06:37 PM
  • Mayank Goswami, 09/02/2015 12:13 PM -- Created document.