Contention-Free MAC protocols for Wireless Sensor Networks



A MAC protocol specifies how nodes in a sensor network coordinate their communication over a shared communication channel. Owing to the limited capabilities of sensor nodes, the desired properties of a MAC protocol are: it should be \emph{distributed} and avoid collisions; it should \emph{self-stabilize} to changes in the network (such as arrival of new nodes), and these changes should be \emph{contained}, i.e., affect only the nodes in the vicinity of the change; it should not assume that nodes have a global time reference, i.e., nodes may not be time-synchronized. We give the first MAC protocols that satisfy all of these requirements. In particular, we provide distributed, contention-free, self-stabilizing MAC protocols which do not assume a global time reference. In a stable state, our protocols ensure that a node's throughput is inversely proportional to the \emph{local} density of nodes, hence a localized bottleneck will not affect the entire network. The communication complexity until stabilization is small: \math{O(\log n)} control messages per node, of size at most \math{O(\log n)} bits (\math{n} is the size of the sensor network). The time it takes for the protocol to stabilize depends on the maximum density of the nodes. Further, in the event that the network changes, only nodes in the neighborhood of the change get affected.