TDMA scheduling algorithms for wireless sensor networks

By Sinem Coleri Ergen, Pravin Pratap Varaiya. Wirel. Networks, 2010

426 citations recorded by the source corpus.

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/b2e9643bba6857df1439e3d339d5f2a08e5562ac

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

Wireless Network Design for Control Systems: A Survey (2017, background): “Reference [82] formulates the delay minimization of the packet transmissions from the sensor nodes to the common access point.”