Near-Optimal Radio Use For Wireless Network Synchronization

In this paper, we consider the model of communication where wireless devices can either switch their radios off to save energy (and hence, can neither send nor receive messages), or switch their radios on and engage in communication. The problem has been extensively studied in practice, in the setting such as deployment and clock synchronization of wireless sensor networks. We distill a clean theoretical formulation of minimizing radio use and present near-optimal solutions. Our base model ignores issues of communication interference, although we also extend the model to handle this requirement. We assume that nodes intend to communicate periodically, or Current address: Mathematics of Networks and Communications, Bell Laboratories, Alcatel-Lucent, 600 Mountain Avenue, Murray Hill, New Jersey 07974, USA. Email: milan@research.bell-labs.com. 2 Research supported in part by NSF grants 0830803, 09165174, 1016540, 1065276, 1118126 and 1136174, US-Israel BSF grant 2008411, grants from OKAWA Foundation, IBM, Lockheed-Martin Corporation and the Defense Advanced Research Projects Agency through the U.S. Office of Naval Research under Contract N00014-11-1-0392. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. Preprint submitted to Theoretical Computer Science October 18, 2011 1