Details

Autor(en) / Beteiligte

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

Titel

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

Ist Teil von

• ACM Symposium on Parallel Algorithms and Architectures: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures; 09-11 June 2007, 2007, p.260-269

Ort / Verlag

ACM

Erscheinungsjahr

2007

Link zum Volltext

Quelle

ACM Digital Library Complete

Beschreibungen/Notizen

• 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.