Distributed formation of broadcast transmission schedules for mobile ad hoc networks

Abstract: In a mobile ad hoc packet radio network using transmission scheduling, when a terminal boots and is ready to join the network it has no knowledge of the network’s current state. In order to send and receive packets without interference, the new terminal must have some means of notifying other terminals of its presence and exchanging information with them so that it can form a collision free broadcast transmission schedule. We demonstrate the performance of a distributed protocol designed to allow a new terminal to acquire sufficient information about its local environment to achieve collision free transmissions. Furthermore, we show that changes to the network are limited to the new terminal’s local neighborhood. As a result, the size of the overall network has very little effect on the performance of the protocol. The protocol is not only effective in adding a new terminal; it can also organize a group of terminals into a new network. This is demonstrated for the extreme case of all terminals powering up simultaneously. The overall performance of the algorithm depends primarily on the density of the network and rate at which changes occur in the network. 1