NSF Research Grant

Efficient and Localized Broadcasting in Ad Hoc Wireless Networks 

Project Summary 

An ad hoc wireless network, or simply ad hoc network, is a special type of wireless multi-hop network without infrastructure or centralized administration. Unlike cellular networks where nodes interact through a centralized base station, nodes in an ad hoc network interact in a peer-to-peer fashion. As a result of the mobility of their nodes, ad hoc networks are characterized by dynamically changing topologies. The applications of ad hoc networks range from civilian (e.g., distributed computing, sensor networks) to disaster recovery (search-and-rescue), and military (battlefield). 

Collective communication represents a set of important communication functions that involve multiple senders and receivers. Four basic types of collective communication services include: multiple one-to-one communication, one-to all communication (broadcasting), all-to-one communication (reduction or aggregation), and all-to-all communication. Among them, broadcasting is one of the fundamental operations and has extensive applications, including the route discovery process in reactive routing protocols, naming and addressing, and dense-mode multicasting. Due to the broadcast nature of wireless communication, blind flooding of the broadcast message may cause serious contention and collision, resulting in the broadcast storm problem. 

We propose to study the challenge of efficient and localized broadcasting by offering a generic framework that can capture many existing localized broadcast algorithms and, in addition, some efficient solutions can be derived from this framework. The framework is built on the theory developed by the PI that global coverage and connectivity can be achieved through local coverage and connectivity based on the notion of local view. Another salient feature is that the framework can easily integrate other objectives such as energy-efficient design and reliability that ensures broadcast coverage. Our preliminary results indicate that the proposed approach is promising to address the broadcast storm problem by selecting a small forward node set without global information/infrastructure or location information of nodes. This approach can be implemented either in a static view which is independent of a particular broadcast or in a dynamic view during a broadcast process. 

The goals of the proposed research are the following: (1) Provide a more generic framework for deterministic and localized broadcasting in ad hoc networks. (2) Derive additional cost-effective broadcast schemes from the generic framework. (3) Reduce excessive broadcast redundancy through energy-efficient design, by using adjustable transmission ranges at each node. (4) Explore the use of broadcasting as a basic building block to support other types f collective communication, such as all-to-one and all-to-all. (5) Ensure broadcast coverage with modest redundant transmission without solely relying on ACK/NACK. (6) Integrate different components and fine tune the system through an empirical study based on a set of well-defined quantitative performance metrics. 

We envision that the insights and results from this research will provide guidelines for efficient and localized algorithms for a wide range of applications. This research will also exploit and contribute to theoretical studies in graph theory and distributed algorithms. The results obtained from this project are believed to be useful in various applications of ad hoc networks such as defense, law enforcement, health facilities, academic institutions, and disaster recovery. We believe that the proposed study will contribute to make these networks more practical. 

Contador    Since July 2003