CCF-AF: Abstract Medium Access Control Layers

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

The study of algorithms and lower bounds for wireless radio networks is complicated by the diversity and complexity of assumptions about network behavior, for example, about time synchronization, device reliability and mobility, signal propagation characteristics, and transmission collisions. This project will simplify this study by defining simple abstract models for Medium Access Control (MAC) layers in wireless networks. These layers will provide reliable local broadcast communication, with delays that are bounded by functions of the local contention. Algorithm designers should be able to develop and analyze algorithms in terms of these abstract layers, independently of the physical network behavior and the MAC layer implementation, yet obtain results that are realistic in terms of the physical networks. Likewise, theoreticians should be able to use these layers to prove simple but meaningful lower bounds. Specifically, the project will define and evaluate several possible abstract MAC layers, varying according to whether their guarantees are worst case or probabilistic, how they model signal propagation characteristics, and what they ensure in the presence of failures and other network changes. It will demonstrate how these layers can be implemented in physical radio networks, using a variety of contention-management methods such as carrier-sensing, collision detection, random transmission and backoff, and network coding. It will use these layers to study many problems in wireless networks, including basic problems such as neighbor discovery and regional leader election; intermediate problems such as network-wide communication, maintenance of network structures, and resource allocation; and high-level problems that arise in robot control and data-management applications.