Pruning Local Schedules for Efficient Swarm Communication

Proceedings of the International Symposium on Underwater Technology, Tokyo, Japan, 2007

Felix Schill & Uwe R. Zimmer

Reliable wireless communication under water is a precondition for swarming technologies. This paper discusses a time division multiple access algorithm suitable for dynamic multi-hop wireless networks, which offers quick all-to-all information exchange (Omnicast), dense local schedules and predictable latencies. The algorithm is based on an earlier algorithm published by the authors in [Distributed Dynamical Omnicast Routing, Complex Systems (intl. journal) Volume 16, Issue 4, 2006]. The improvements presented here are a new mapping function for logical time slots to actual time slots, which balances sending frequencies between nodes, and a technique to reduce the average degree of the connection graph as seen by the scheduling algorithm. It is explained how this reduction of degree can be achieved without causing communication collisions, or disconnecting the graph. The results of experiments performed in a real time simulation show the performance of the algorithm, and the performance gain achieved by local reduction of the degree.

Introduction

The importance of distributed sensing and swarming vehicles has been increasingly recognized by the underwater community and ocean sciences. The Serafina submersible robot has been developed as a platform for swarming and distributed sensing applications. The small size (50 cm), low weight (5 kg) and low cost allows easy deployment of swarms of dozens of submersibles with affordable effort. One of the most important problems that had to be solved apart from the miniaturisation is the communication between members of the swarm. For reasons of scalability to large swarms, and also power consumption, a digital longwave radio transceiver has been developed, which can transmit data over up to 10 meter range with up to 8192 bit/sec. The transmitter uses differential binary phase shift keying on a fixed carrier frequency. As opposed to the majority of other wireless networks, in which communication is sporadic and usually point-to-point, swarms require a communication system optimised for continuous communication between all members, with quick local and global information exchange. The authors published in previous papers the Omnicast problem ([ref Taros Omnicast]), and a theoretical analysis based on a graph theoretical network model. A distributed algorithm adjusted to Omnicast communication in swarms was presented in [ref DDOR CS]. Experiments with the phase-modulated longwave radio modules revealed that the graph-theoretical network model commonly assumed in the literature is too conservative ([ref OCEANS]). In fact, if two or more transmitters send within the range of a receiver, the receiver will only observe a collision, if the closest nodes have very similar incoming signal strength. Otherwise the receiver will reliably receive the message with the highest signal strength. This paper shows how this fact can be used to speed up both local and global information exchange by virtually decreasing the local degree of the connection graph as seen by the scheduling algorithm. Experiments in a simulation show that global information exchange is faster for networks with lower density. In the case of a high local density (high degree), nodes can remove the k nodes with lowest signal strength from their local visible neigbourhood (the set of nodes within their range), if that does not disconnect the graph (the connectivity can be reconstructed from the schedules received from neighbours). It is shown in this paper how and to which degree this improves overall swarm communication efficiency.

Paper (pdf) | other publications