AF: Small: Bounded-Contention Coding for Wireless Networks

无线网络中的干扰通常会阻止节点接收传输范围内的消息。这是因为通信是通过广播信道进行的，而不是点对点链路--靠近多个发射机的节点接收的信号是最初发射的信号的混合。避免冲突基本上需要在希望传输的节点之间打破某种类型的对称性，以防止它们同时传输，这是许多重要研究的主题。本项目将专注于竞争有限的无线网络场景，并引入一个框架来应对冲突而不是避免冲突。它将由两个主要贡献组成。首先，PI将为加性网络引入一种新的编码框架，称为有界竞争编码(BCC)，它允许接收方唯一地解码冲突的传输，并且PI将在该框架内设计高效的代码。其次，PI将设计使用这些代码在无线网络中进行通信的算法，以解决许多基本的分布式问题。PI将用相应的下限来补充这项研究，以了解在这样的环境中通信和计算的限制。PI还将考虑对基本模型的几种扩展和修改，确定它们对算法的影响，并针对这些模型中的问题提出新的解决方案。该项目的结果可能会对实际无线网络的设计产生影响，在实际无线网络中，有界竞争的场景很常见。例如，在大规模电话系统中，一次通常只有几个呼叫处于活动状态。另一个例子是当无线传感器网络中的节点周期性地从环境中接收测量数据并将其发送到网络中的中央位置时。传感器节点传输它们的测量的时间可以以限制并发活动传输的数量的方式来调度。在这两个示例中，尽管争用有限，但仍可能发生干扰，这意味着必须解决冲突传输。例如，我们的编码方法和算法可以导致新的、有效的实现，而我们的下限结果可以更好地理解内在的限制。

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, our 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.