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

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

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.