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

University Of California-Riverside, Riverside CA

Investigators

Abstract

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.