A Graph-Theoretic Approach to MAC and Network Protocols for Wireless Sensor Networks

Lisa DiPippo
Computer Science and Statistics,
University of Rhode Island

Friday 6th April 2007
11:00 a.m. - 12:00 p.m.
Fuller Labs 320

This talk will describe a set of TDMA MAC protocols for wireless sensor networks that can achieve near optimal throughput and good latency for regular periodic data delivery. The protocol is based on a novel graph coloring technique called the Color Constraint Heuristic (CCH), which is presented in this paper. The CCH creates a near optimal reduction in the number of colors, which in turn produces near-optimal periodic data throughput, as measured by the reduction of the number of TDMA slots. The talk will present a centralized TDMA slot assignment algorithm, Centralized Slot Assignment (CSA-CCH), that uses CCH and assumes knowledge of the entire network topology. It will also describe a distributed version of the algorithm, Distributed Slot Assignment (DSA-CCH), that does not assume any prior knowledge of the network. A further refinement of DSA that is designed for query tree aggregation applications (DSA-AGGR) will also be presented. Simulations show that these algorithms perform closer to the optimal bound on data throughput than several prominent TDMA slot assignment protocols for wireless sensor networks. In addition, the CCH-based algorithms carefully order the coloring to provide good latency for data delivery.

______

Dr. Lisa Cingiser DiPippo is an Associate Professor at the University of Rhode Island where she leads the URI Wireless Sensor Network Research Group. She graduated with a BS in Computer Science from Lafayette College, and an MS in Computer Science and PhD in Applied Mathematical Sciences from the University of Rhode Island. Her research interests include sensor network protocols, real-time systems, middleware for real-time embedded systems, and application of real-time scheduling to wireless sensor networks.

Host: Craig Wills

Refreshments will be served.