The effects of synchronization on topology-transparent scheduling

Topology-transparent scheduling is an attractive medium access control technique for mobile ad hoc networks (MANETs) and wireless sensor networks (WSNs). The transmission schedule for each node is fixed and guarantees a bounded delay independent of which nodes are its neighbours, as long as the active neighbourhood is not too dense. Most of the existing work on topology-transparent scheduling assumes that the nodes are synchronized on frame boundaries. Synchronization is a challenging problem in MANETs and in WSNs. Hence, we study the relationships among topology-transparent schedules, expected delay, and maximum delay, for successively weaker models of synchronization: frame-synchronized, slot-synchronized, and asynchronous transmission. For each synchronization model, we give constructive proofs of existence of topology-transparent schedules, and bound the least maximum delay. Perhaps surprisingly, the construction for the asynchronous model is a simple variant of the slot synchronized model. While it is foreseen that the maximum delay increases as the synchronization model is weakened, the bound is too pessimistic. The results on expected delay show that topology-transparent schedules are very robust to node density higher than the construction is designed to support, allowing the nodes to cope well with mobility, and irregularities of their deployment. Wensong Chu received his M.S. in Applied Mathematics from Shanghai Jiao Tong University, China, in 1993; received his M.S. in Computer Networks (Electrical Engineering) from the University of Southern California in 2000; received his Ph.D. in Mathematics from the University of Southern California in 2002. He was with the Department of Computer Science and Engineering at Arizona State University as a post-doctoral fellow from 2002 to 2003. Currently he is doing research at the CMS Bondedge in California. His research interests include sequence designs for communications, combinatorial coding methods, mobile ad hoc networks and sensor networks, financial engineering and combinatorial design theory. Charles J. Colbourn was born in Toronto, Canada in 1953. He completed his B.Sc. degree at the University of Toronto in 1976, M.Math. at the University of Waterloo in 1978, and Ph.D. at the University of Toronto in 1980, all in computer science. He has held faculty positions at the University of Saskatchewan, the University of Waterloo, and the University of Vermont, and is now Professor of Computer Science and Engineering at Arizona State University. He is co-editor of the CRC Handbook of Combinatorial Designs and author of Triple Systems and The Combinatorics of Network Reliability, both from Oxford University Press. He is editor-in-chief of the Journal of Combinatorial Designs. His research concerns applications of combinatorial designs in networking, computing, and communications. Violet R. Syrotiuk earned the Ph.D. degree in Computer Science from the University of Waterloo (Canada) in 1992. She joined Arizona State University in 2002 and is currently an Assistant Professor of Computer Science and Engineering. Dr. Syrotiuk’s research is currently supported by three grants from the National Science Foundation, and contracts from Los Alamos National Laboratory, and the Defence Science and Technology Organisation in Australia. She serves on the Editorial Board of Computer Networks, and on the Technical Program Committee of several major conferences including MobiCom and Infocom. Her research interests include mobile ad hoc and sensor networks, in particular MAC protocols with an emphasis on adaptation, topology-transparency, and energy efficiency, dynamic spectrum utilization, mobile network models, and protocol interaction and cross-layer design. She is a member of the ACM and the IEEE.