Towards Optimal TDMA Scheduling for Robotic Swarm Communication

Proceedings of the TAROS (Towards Autonomous Robotic Systems) intl. conference, September 12-14, 2005, London

Felix Schill, Uwe R. Zimmer & Jochen Trumpf

Initial results are presented on a new TDMA scheduling problem, which tries to minimise the duration of total information exchange throughout a multi-hop wireless network. A new network communication mode omnicast is introduced, which implements many-to-many communication, and is similar to a concurrent multiple broadcast from every node to every other node. It can be shown that the lower bound for this problem for arbitrary connected networks with n nodes is n time steps, a general upper bound is (n^2-n), and (2n-1) if the graph modelling the network is Hamiltonian. Simulation results suggest that a tight upper bound is n. Furthermore, it turns out that allowing collisions improves the results, meaning that collision-free solutions are in general suboptimal. A TDMA scheme which optimizes omnicast, will minimise the time span from where new information is released into the network, until every node received it. It also automatically solves the broadcast and convergecast problem forarbitrary senders, and provides consistent response times and bandwidth for realtime operation. The main application lies in robotic swarm communication, where global parameters and environmental information have to be exchanged and updated with minimal and bounded latency. It will be shown how such a TDMA scheme can be applied to a swarm of autonomous miniature submersibles.

Paper (pdf) | other publications