27-07-2012, 02:44 PM
TDMA Scheduling Algorithms for Wireless Sensor Networks
tdma.pdf (Size: 162.94 KB / Downloads: 47)
Introduction
Wireless sensor networks have been proposed for a wide range of
monitoring applications such as traffic and seismic monitoring, and
fire detection [1]. Such networks consist of a group of nodes, with
sensing, signal processing and wireless communication capabilities
and limited battery energy. The nodes must quickly report the
results to a data collection node or access point. Since the nodes
are battery-powered, the medium access control (MAC) protocol is
critical in determining network lifetime.
Network and transmission model
We consider a network comprising a single access point (AP) and
several sensor nodes that periodically generate data, possibly at different
rates, for transfer to the AP. Links are assumed to be bidirectional.
This is required for proper functioning of network protocols
such as distributed Bellman-Ford algorithms [25]. Bidirectionality
is achieved if all sensor nodes transmit at the same power.
The scheduling problem
Each node of G (except AP) generates a positive integer number
of packets at the beginning of the scheduling frame. Given the
interference graph C, the scheduling problem is to find a minimum
length frame during which all nodes can send their packets to AP.
Theorem 1 The scheduling problem is NP-complete.
Coloring the network
Any algorithm can be used to color the conflict graph GCc such
that nodes i and j are assigned different colors if (i, j) ∈ ECc.
Computing the chromatic number of a graph is NP-complete. Incremental
methods appear to be the heuristic choice of vertex coloring
[11]: Vertices are colored sequentially with the colors chosen
in response to colors already assigned in the vertex’s neighborhood.
These methods vary in how the next vertex is selected and how it
is assigned a color.
Scheduling the Network
A superslot in a node-based scheduling algorithm is a collection of
consecutive time slots such that each node with at least one packet
at the beginning of the superslot transmits at least one packet during
the superslot. Because two nodes assigned the same color can
transmit at the same time, the number of slots in a superslot is at
most equal to the total number of colors used for coloring the network.