Effizientes Routing von Nachrichten

For position-based routing nodes are identified by their unique geographical positions. The task is to deliver a message from a source node to a target node identified by its position in an unknown wireless ad hoc network.  We try to optimize the number of messages and the time to perform this task in a worst case setting. One obstacle for efficient position based routing is the lack of knowledge about the network structure available at the beginning. In particular, reactive routing protocols that do not know any network structure in advance fail to solve this problem efficiently.

As complexity measures we consider time and traffic for delivering the message from source to target cell. Time is the number of rounds until the message reaches the destination if the node is accessible. Traffic is the total number of messages sent between cells. We investigate the time and traffic under a competitive measure. This research nicely extends to robot motion planning if we restrict ourselves to a single message.