Distributed and adaptive TDMA algorithms for multiple-hop mobile networks

Time-division multiple-access (TDMA) protocols can support contention-free link-level broadcast transmissions in mobile, multiple-hop wireless networks. However, it is typically difficult to adapt TDMA assignments to dynamic topologies. The paper defines and discusses two algorithms for adjusting TDMA slot assignments to the dynamic changes of a mobile network. Our new protocols offer three significant advantages: (1) the information required by the protocols is gathered exclusively from a terminal´s local neighborhood; (2) global coordination is not required; (3) changes to the state information at a terminal do not need to be distributed to all terminals in the network. The operation of the algorithms is evaluated with an extensive simulation study using a large number of randomly generated networks in which the diameters, degrees, and number of nodes are varied. Results show that the efficiency of the algorithms, determined as the average number of transmission slots assigned per terminal, is better under static conditions than two cases chosen for reference; the efficiency does not degrade significantly under dynamic conditions for which the algorithms continually adjust to added and deleted links. For the networks considered, the algorithms typically converge in times on the order of several hundred slots and a convergence bound approximately four times larger is established. Convergence time is shown to increase in almost a linear fashion with terminal radius and it is relatively insensitive to the number of terminals.