Bounded-Contention Coding for Wireless Networks

Interference in wireless networks often prevents nodes from receiving messages that are within transmission range. This is because communication occurs through broadcast channels rather than point-to-point links -- a node that is close to more than one transmitter receives a signal that is a mixture of the signals originally transmitted. Avoiding collisions basically requires some type of symmetry breaking among the nodes that want to transmit, to prevent them from transmitting at the same time, and has been the subject of many important studies.

This project will focus on wireless network scenarios in which the contention is bounded and introduce a framework for coping with collisions rather than avoiding them. It will consist of two main contributions. First, the PI will introduce a new coding framework for additive networks called Bounded-Contention Coding (BCC), which allows a receiver to uniquely decode colliding transmissions, and the PI will devise efficient codes within this framework. Second, the PI will design algorithms that use these codes for communicating in wireless networks, in order to solve many fundamental distributed problems. The PI will complement this study with corresponding lower bounds in order to understand the limitations on communicating and computing in such an environment. The PI will also consider several extensions and modifications of the basic model, determine their impact on the algorithms, and propose new solutions for problems in these models as well.

The results of this project can have impact on the design of real wireless networks, in which bounded-contention scenarios are common. For example, in a large-scale system of phones, only a few calls are typically active at one time. Another example is when nodes in a wireless sensor network receive measurement data from the environment periodically and send it to a central location in the network. The times at which the sensor nodes transmit their measurements could be scheduled in a way that bounds the number of concurrently active transmissions. In both of these examples, although the contention is limited, interference may still occur, implying the necessity to resolve colliding transmissions. For examples such as these, the coding methods and algorithms can lead to new, efficient implementations, and our lower bound results can lead to a better understanding of the inherent limitations.