TDMA scheduling in fault tolerant wireless sensor networks

In this paper a fault-tolerant ring topology is suggested to provide energy efficient and real time operation using Time Division Multiple Access (TDMA) in sensor networks. The fault tolerant behaviour requires search for an extended type of Hamiltonian cycle in the connectivity graph. Since the problem in general is NP-complete, heuristics based upon the topology are used to aid the search algorithms. Cluster and region-based algorithms are proposed which are able to find solutions in large networks even when other algorithms fail.