TDMA scheduling algorithms for wireless sensor networks |
| |
Authors: | Sinem Coleri Ergen Pravin Varaiya |
| |
Affiliation: | (1) Wireless Sensor Networks Lab, sponsored by Pirelli and Telecom Italia, Berkeley, USA;(2) University of California, Berkeley, USA |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|