Collision-minimizing csma and its applications to wireless sensor networks

1048

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 22, NO. 6, AUGUST 2004

Collision-Minimizing CSMA and Its Applications to Wireless Sensor Networks
Y. C. Tay, Kyle Jamieson, and Hari Balakrishnan, Member, IEEE
Abstract—Recent research in sensor networks, wireless location systems, and power-saving in ad hoc networks suggests that some applications’ wireless traffic be modeled asan event-driven workload: a workload where many nodes send traffic at the time of an event, not all reports of the event are needed by higher level protocols and applications, and events occur infrequently relative to the time needed to deliver all required event reports. We identify several applications that motivate the event-driven workload and propose a protocol that is optimal for thisworkload. , is nonpersistent Our proposed protocol, named carrier sense multiple access (CSMA) with a carefully chosen nonuniform probability distribution that nodes use to randomly select contention slots. We show that is optimal in the sense that is the unique probability distribution that minimizes collisions between contending stations. has knowledge of . We conclude with an exploration of how couldbe used to build a more practical medium access control protocol via a probability distribution with no knowledge of that approximates .

CSMA

CSMA

CSMA

Index Terms—Carrier sense multiple access (CSMA), medium access control (MAC), nonpersistent, performance, poisson process, sensor networks.

2) Power-Saving in Ad Hoc Networks: In a mobile ad hoc network, some coordinator nodes stayawake and form a routing backbone, while other nodes power down most of the time, and cannot communicate [4]. Consider the following protocol for noncoordinator neighbor discovery when one of the sleeping nodes becomes backlogged. The node wakes up unaware of its neighbors, who might have changed since it went to sleep. It sends a poll message. All coordinators within range of the sleeping noderespond to the poll at the same time, but only one response is needed to start routing traffic from the waking source. 3) Indoor Location Systems: In the Cricket location system [5], many beacons, attached to walls and ceilings, broadcast their locations so that a handheld listener can determine its location. For fault tolerance and protection against RF or ultrasound fading, many beacons should becodeployed geographically. However, only two or three such beacons need be heard by a listener and minimizing their latency is crucial for fast update of real-time applications like navigation. We wish to reexamine MAC design with these traffic patterns in mind. In these examples, latency, not throughput, is the performance-limiting factor. Hence, we propose the goal of minimizing the latency of thefirst few successful transmissions in an event-based traffic pattern that exhibits the following characteristics. 1) An event can trigger a synchronized burst of transmissions from a large number of sensor nodes. Note that this characteristic specifically invalidates the Poisson arrival assumption. 2) Although a large number of nodes may decide to transmit a packet, the application at the data sinkmay need only a few of these packets. Earlier work, based on packet radio, LAN, or WAN scenarios, treats all packets as equally important. 3) In any region of space, the number of transmitting nodes can quickly change. This follows from (1), as well as the shrinking size of sensor nodes [6] and the benefits of deploying redundant sensors. This workload leads us to the following goal for maximizingthe performance of nonpersistent carrier sense multiple access (CSMA) in sensor networks. If sensors simultaneously and independently pick one of slots at some point in time, what is the probability distribution on slots that yields the maximum probability of a collision-free transmission? This probability in the rest of this paper, distribution, which we refer to as is optimal in the sense that...