License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
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://dagstuhl.sunsite.rwth-aachen.de/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:
09005.AmmarMostafa.2303.pdf (0.2 MB)

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 =		{10.4230/LIPIcs.FSTTCS.2009.2303},
  annote =	{Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization}
}

Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization
Collection: 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 | Privacy Published by LZI