Towards Optimal TDMA Scheduling for Robotic Swarm Communication

摘要

Initial results are presented on a new TDMA scheduling problem, which tries to minimise the duration of total information exchange throughout a multihop 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, and if the graph modelling the network is Hamiltonian. In fact, more recent results (see acknowledgements) show that a better upper bound is. Simulation results suggest that a tight upper bound is. 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 for arbitrary 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.