Algorithms for Message Ferrying on Mobile ad hoc Networks

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

doi:10.4230/LIPIcs.FSTTCS.2009.2303

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: https://drops.dagstuhl.de/opus/volltexte/2009/2303/

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}
}

14.12.2009

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

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