License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2303
URN: urn:nbn:de:0030-drops-23031
URL: http://drops.dagstuhl.de/opus/volltexte/2009/2303/
Go to the corresponding LIPIcs Volume Portal


Ammar, Mostafa ; Chakrabarty, Deeparnab ; Sarma, Atish Das ; Kalyanasundaram, Subrahmanyam ; Lipton, Richard J.

Algorithms for Message Ferrying on Mobile ad hoc Networks

pdf-format:
Document 1.pdf (206 KB)


Abstract

Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc Min-Max Buffer Problem} for the case when the nodes are onhierarchically separated metric spaces.

BibTeX - Entry

@InProceedings{ammar_et_al:LIPIcs:2009:2303,
  author =	{Mostafa Ammar and Deeparnab Chakrabarty and Atish Das Sarma and Subrahmanyam Kalyanasundaram and Richard J. Lipton},
  title =	{{Algorithms for Message Ferrying on Mobile ad hoc Networks}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{13--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2303},
  URN =		{urn:nbn:de:0030-drops-23031},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2303},
  annote =	{Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization}
}

Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009


DROPS-Home | Fulltext Search | Imprint Published by LZI