Content area
Full Text
Distrib. Comput. (2011) 24:187206 DOI 10.1007/s00446-010-0118-0
The abstract MAC layer
Fabian Kuhn Nancy Lynch Calvin Newport
Received: 30 October 2009 / Accepted: 30 August 2010 / Published online: 16 September 2010 Springer-Verlag 2010
Abstract A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by dening an abstract MAC layer. This service provides reliable local broadcast communication, with timing guarantees stated in terms of a collection of abstract delay functions applied to the relevant contention. Algorithm designers can analyze their algorithms in terms of these functions, independently of specic channel behavior. Concrete implementations of the abstract MAC layer over basic radio network models generate concrete definitions for these delay functions, automatically adapting bounds proven for the abstract service to bounds for the specic radio network under consideration. To illustrate this approach, we use the abstract MAC layer to study the new problem of Multi-Message Broadcast, a generalization of standard single-message broadcast in which multiple messages can originate at different times and locations in the network. We present and analyze two algorithms for Multi-Message Broadcast in static networks: a simple greedy algorithm and one that uses regional leaders. We then indicate how these results can be extended to mobile networks.
This work has been support in part by Cisco-Lehman CUNY A New MAC-Layer Paradigm for Mobile Ad-Hoc Networks, AFOSR Award Number FA9550-08-1-0159, NSF Award Number CCF-0726514, and NSF Award Number CNS-0715397.
F. KuhnUniversity of Lugano (USI), Lugano, Switzerland e-mail: fabian.kuhn@usi.ch
N. Lynch C. Newport (B)
MIT CSAIL, Cambridge, MA, USA e-mail: cnewport@csail.mit.edu
N. Lynche-mail: lynch@csail.mit.edu
Keywords Wireless networks Abstraction
Medium access control Broadcast
1 Introduction
The study of bounds for mobile ad hoc networks is complicated by the large number of possible communication assumptions: Do devices operate in slots or asynchronously? Do simultaneous transmissions cause collisions? Can collisions be detected? Is message reception determined by geographical distances or by more complex criteria such as signal-to-noise ratio? And so on. This situation causes problems. Results for one set of communication assumptions might prove invalid for a slightly different set of assumptions. In addition, these low-level assumptions require algorithm designers to grapple with low-level problems such as contention management, again and again, making it difcult to highlight...