Publication Name Towards Optimal TDMA Frame Size in Wireless Sensor Networks  
Publication Type Technical Report  
Publication Date March, 2007  
Bibliography Entry Kevin L. Bryan, Tiegeng Ren, Lisa DiPippo, Timothy Henry, Victor Fay-Wolfe Towards Optimal TDMA Frame Size in Wireless Sensor Networks, University of Rhode Island, Technical Report, TR-324, March 2007  
Download Publication downloads/opttdma-uri.pdf  
This paper describes 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 Hueristic (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 paper describes a centralized TDMA slot assignment algorithm, Centralized Slot Assignment (CSA-CCH), that uses CCH and assumes knowledge of the entire network topology. It then describes 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) is also presented. The paper shows through simulations that our algorithms performs 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.

Copyright © 2005. All rights reserved.
Department Of Computer Science and Statistics
Univeristy Of Rhode Island