AF: Small: Bounded-Contention Coding for Wireless Networks

AF：小型：无线网络的有界竞争编码

• 批准号: 1217506
• 负责人: Nancy Lynch
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217506&HistoricalAwards=false
• 关键词: AF; Small; Bounded; Contention; Coding

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.

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