Clique-based randomized multiple access for energy-efficient wireless ad hoc networks

A fundamental tradeoff in MAC protocol design for wireless ad hoc networks is between proactive and reactive coordination, where the latter is used to resolve access conflicts whose severity is determined by the former. In this paper, we describe clique-based randomized multiple access (CRMA), a distributed MAC protocol for wireless ad hoc network applications. Of the many objectives in MAC design for this application, CRMA places strongest emphasis on energy efficiency and reliance only on local (one-hop) connectivity information. CRMA forms collection of nodes, or cliques, separated by one hop, and provides the proactive coordination required for clique members to synchronize their wake-sleep cycles. Each clique selects a slot in the clique's frame pseudo-randomly, so that no proactive coordination between cliques required. To limit potential access conflicts CRMA can exploit bandwidth via frequency hopping or spread spectrum coding; these also provide robustness to multi-channel radios to increase performance. With a slight amount of additional proactive coordination, CRMA can also employ what we call predictive conflict resolution, wherein clique members predict access conflicts and resolve them ahead of time.