Self-stabilizing TDMA algorithms for dynamic wireless ad-hoc networks. arXiv 1210.3061

We consider Medium Access Control (MAC) protocols for Dynamic wireless ad-hoc networks (DynWANs) that need to be autonomous, robust, and have high bandwidth utilization, a high predictability degree of bandwidth allocation, and low communication delay in the presence of frequent changes to the network topology. We propose an algorithmic design for self-stabilizing MAC protocols with a provable short convergence period, and by that, it can facilitate the sat-isfaction of severe timing requirements and possesses a greater predictability degree, while maintaining low communication delays and high throughput. We show that the algorithm facilitates the satisfaction of severe timing requirements for DynWANs. We consider transient faults and topological changes to the com-munication network, and demonstrate self-stabilization. Algorithm Description. The MAC algorithm in Fig. 1 assigns timeslots to nodes after the convergence period. The system consists of a set, P, of N anonymous communicating entities, which we call nodes. Denote every node pi ∈ P with a unique index, i. We assume that the MAC protocol is invoke