Wireless devices are now ubiquitous, and their computation and communication capabilities are increasing rapidly.  However, writing programs for networks of wireless devices is still difficult.  A major reason is that wireless devices share radio communication channels, resulting in message collisions and losses.  Strategies are needed to manage contention.

This project has developed new abstraction layers called "Abstract MAC Layers", which provide the abstraction of a Reliable Local Broadcast service.  These layers hide complexities of collision management, and thus can aid programmers in writing software for wireless networks.  The approach is theoretical, with precise layer definitions, mathematically-defined algorithms, and rigorous analysis.

This work began by defining a basic Abstract MAC Layer, based on a network graph.  This layer supports message sending and delivery, plus an ``abort'' capability.  The layer supports both reliable and unreliable communication links, based on ``Dual Graphs''.  It guarantees two latency bounds:  an ``acknowledgment bound'' on the time for a sender's message to be received by all of its reliable graph neighbors, and a ``progress bound'' on the time for a receiver to receive some message, when some reliable neighbor is sending.  This work also demonstrated how such layers can be used in developing a simple algorithm for global multi message broadcast throughout a network.

Later work developed a probabilistic version of the abstract MAC layer, gave an algorithm to implement it over a standard ``Radio Network'' wireless platform, and used the layer in a higher-level algorithm for global multi-message broadcast.  Composing the two algorithms yields a global broadcast algorithm for the radio network model with costs comparable to  the best previously-known algorithms.  Moreover, using the abstract MAC layer greatly simplifies the design and analysis of the global broadcast algorithm.

Another algorithm was developed for implementing the probabilistic abstract MAC layer over a wireless network platform that supports network coding.  By composing algorithms at two levels, this yields an efficient algorithm for solving global broadcast over a network coding platform.

These layers can provide a rather general method of designing algorithms to solve higher-level problems over wireless platforms.  This project developed efficient algorithms to solve a variety of fundamental problems over abstract MAC layers, including neighbor discovery, leader election, and constructing Maximal Independent Sets (MISs).  One algorithm, for multi-message global broadcast, is notable in that it is designed to work for Dual Graphs, that is, in the presence of both reliable and unreliable links.  All these algorithms can be composed with lower-level implementations of abstract MAC layers to yield algorithms to solve problems directly over wireless platforms.

Additional implementations of the layer were developed for other wireless platforms, including a new ``Bounded-Contention Coding'' platform based on additive channels.  Notably, an efficient algorithm was developed for implementing the probabilistic layer over a radio network with unreliable communication links. This algorithm is ``scalable", in that all costs are based on purely local parameters, such as maximum node degree, rather than global parameters like network size.  The algorithm uses a new subproblem of ``Seed Agreement'', which enables nodes to share random numbers.

Another efficient algorithm was developed for implementing the probabilistic layer over a ``Signal-to-Interference-and-Noise Ratio (SINR)'' platform model.  The SINR platform is notoriously complicated to use for designing algorithms; abstract MAC layers simplify this task...

Please report errors in award information by writing to: awardsearch@nsf.gov.