Startseite > Publikationen > Publikationen

Publikationen

Dynia, Miroslaw;Kutylowski, Jaroslaw;Meyer auf der Heide, Friedhelm;Schrieb, Jonas:

Local strategies for maintaining a chain of relay stations between an explorer and a base station.

In: SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, S. 260-269, New York, NY, USA, 1. Jan. 2007, ACM Press, New York, NY, USA

Abstract

We discuss strategies for maintaining connectivity in a system consisting of a stationary base station and a mobile explorer. For this purpose we introduce the concept of mobile relay stations, which form a chain between the base station and the explorer and forward all communication. In order to cope with the mobility of the explorer, relay stations must adapt their positions. We investigate strategies which allow the relay stations to self-organize in order to maintain a chain of small length. For a plane without obstacles, the optimal positions are on a line connecting the base station with the explorer; in a setting with obstacles it is a curve around some of the obstacles. Our goal is to keep the relay stations as close to this line/curve as possible. A crucial requirement for strategies is that they are able to work with imprecise or without localization and odometry information. Furthermore, strategies should be local, i.e., relay stations should not need to know about the state of the system as a whole. The performance measures for strategies are the number of relay stations used (in comparision to the optimal number) and the allowed speed of the explorer (in comparision to its maximum attainable speed). We contribute by analyzing the performance of an already known strategy Go-To-The-Middle. This strategy assumes a very weak robot model and needs hardly any localization information, but sacrifices perfomance. Our main contribution is a new strategy, the Chase-Explorer strategy, and its analysis. It needs more advanced robots than Go-To-The- Middle, but achieves near-optimal performance. We further extend it to exploring terrains with obstacles.

Weblink

http://doi.acm.org/10.1145/1248377.1248420

Dateien

hni2837.pdf



Bibtex

@inproceedings{hniid=2837,
author = {Dynia, Miroslaw and Kutylowski, Jaroslaw and Meyer auf der Heide, Friedhelm and Schrieb, Jonas},
title = {Local strategies for maintaining a chain of relay stations between an explorer and a base station},
booktitle = {SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures},
pages = {260-269},
address = {New York, NY, USA},
publisher = {ACM Press, New York, NY, USA},
month = {1~} # jan,
year = {2007},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/2837