Data Delivery by Energy-Constrained Mobile Agents

Jérémie Chalopin, Shantanu Das, Matús Mihalák, Paolo Penna, Peter Widmayer

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingAcademicpeer-review

Abstract

We consider mobile agents of limited energy, which have to collaboratively deliver data from specified sources of a network to a central repository. Every move consumes energy that is proportional to the travelled distance. Thus, every agent is limited in the total distance it can travel. We ask whether there is a schedule of agents’ movements that accomplishes the delivery. We provide hardness results, as well as exact, approximation, and resource-augmented algorithms for several variants of the problem. Among others, we show that the decision problem is np-hard already for a single source, and we present a 2-approximation algorithm for the problem of finding the minimum energy that can be assigned to each agent such that the agents can deliver the data.
Original languageEnglish
Title of host publicationProceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)
PublisherSpringer Verlag
Pages111-122
Number of pages12
DOIs
Publication statusPublished - 2013
Externally publishedYes

Publication series

SeriesLecture Notes in Computer Science
Volume8243

Cite this