AF:Small: Distributed Protocols for Information Dissemination in Ad-Hoc Radio Networks

当安装有线网络基础设施不可行或不经济时，例如在无法进入的环境中或当网络涉及移动或以前未知的实体时，可以部署无线网络以支持有效的通信。无线网络的显著特征是它的节点不能选择性地与其他节点通信——相反，每个节点通过共享的无线信道传输信息，这种传输到达位于其范围内的所有节点。这带来了独特的挑战，例如，需要处理当两个附近节点同时传输时发生的信号冲突。这样的挑战在ad-hoc网络中尤其严重，ad-hoc网络可能是自发形成的，其节点没有关于网络连接的信息。能源消耗也是一个关键问题，因为通过无线网络连接的设备通常是电池供电的。该项目研究无线网络的基本特性，将其建模为拓扑结构最初未知的有向图。主要目标是开发有效的信息传播协议，特别注意信息收集任务，其中所有节点同时尝试向某些指定的目标节点发送消息。考虑了两种效率度量：完成任务所需的时间和所需的能量消耗。互补的目标是通过建立这两种效率度量的下界来研究这种网络的固有局限性。该项目侧重于自组织无线网络中的信息传播协议，其中缺乏拓扑信息和信号碰撞阻碍了通信。这种自组织无线网络模型的开发是为了研究无线设备分散网络的基本方面，包括传感器网络等。在高层次上，目标是阐明有关此类网络的能力和局限性的基本问题。这些问题解决了信息广播和收集的时间复杂性、反馈的作用以及运行时间和能量之间的权衡之间明显的二分法。为了调查这些问题，该项目将侧重于开发更快的协议和更好的基本通信传播原语的下限，包括广播、收集和八卦。对于其中的一些问题，其运行时间的下限和上限之间仍然存在显著的差距，研究者的工作将有助于缩小或减少这些差距。相对而言，人们对自组织无线网络协议的能量复杂性知之甚少。针对这种知识的缺乏，研究者将对能源复杂性进行系统的研究。目标包括设计节能协议，在能源复杂性和运行时间之间建立权衡。在此过程中，研究人员还将致力于开发设计自组织无线网络有效协议的通用技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Radio networks can be deployed to support efficient communication when installing a wired network infrastructure is not feasible or economical, for example in inaccessible environments or when the network involves mobile or previously unknown entities. The distinguishing feature of a radio network is that its nodes cannot selectively communicate with other nodes — instead, each node transmits information via a shared radio channel and this transmission reaches all nodes located within its range. This creates unique challenges, for example the need to deal with signal collisions that occur when two nearby nodes transmit simultaneously. Such challenges are particularly acute in ad-hoc networks, which may be formed spontaneously and whose nodes have no information about the network’s connectivity. Energy consumption is also a critical concern, because the devices connected by radio networks are often battery operated. This project investigates fundamental properties of radio networks, modeled as a directed graph whose topology is initially unknown. The main objective is to develop efficient protocols for information dissemination, with special attention given to the task of information gathering, where all nodes simultaneously attempt to send messages to some specified target node. Two measures of efficiency are considered: the time to complete the task, and the required energy consumption. The complementary goal is to study inherent limitations of such networks by establishing lower bounds on these two efficiency measures.This project focuses on information-dissemination protocols in ad-hoc radio networks, where lack of information about the topology and signal collisions hinder communication. This model of ad-hoc radio networks was developed to study fundamental aspects of decentralized networks of wireless devices, including, for example, sensor networks. At a high level, the goal is to shed light on fundamental questions about capabilities and limitations of such networks. These questions address the apparent dichotomy between the time complexity of information broadcasting and gathering, the role of feedback, and the tradeoff between running time and energy. To investigate these questions, the project will focus on the development of faster protocols and better lower bounds for basic communication-dissemination primitives, including broadcasting, gathering, and gossiping. For some of these problems there are still significant gaps between the lower and upper bounds on their running time, and the investigator's work will contribute to closing or reducing these gaps. Relatively little is known about energy complexity of ad-hoc radio network protocols. Addressing this lack of knowledge, the investigator will conduct a systematic study of energy complexity. The goals include designing energy-efficient protocols and establishing tradeoffs between energy complexity and running time. Along the way, the investigator will also work on developing general techniques for designing efficient protocols for ad-hoc radio networks.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.