Paper Info
Title
Local strategies for maintaining a chain of relay stations between an explorer and a base station
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.
Year
DOI
Venue
2007
10.1145/1248377.1248420
SPAA
Keywords
Field
DocType
strategy go-to-the-middle,mobile explorer,maximum attainable speed,localization information,new strategy,stationary base station,chase-explorer strategy,base station,performance measure,near-optimal performance,local strategy,swarm robotics,self organization,distributed algorithm,ad hoc networks,ad hoc network,distributed algorithms
Base station,Computer science,Simulation,Odometry,Real-time computing,Distributed algorithm,Need to know,Wireless ad hoc network,Robot,Relay,Swarm robotics,Distributed computing
Conference
Citations 
PageRank 
References 
6
0.55
12
Authors
4
Name
Order
Citations
PageRank
Miroslaw Dynia1533.80
Jaroslaw Kutylowski2231.67
Friedhelm Meyer auf der Heide31744238.01
Jonas Schrieb4151.17