Collective communication represents a set of important communication functions that involve multiple senders and receivers. 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. This project studies the challenge of efficient and localized broadcasting in ad hoc wireless networks 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. This research has six thrusts: (1) Provide a more generic framework for deterministic and localized broadcasting in ad hoc networks, including constructing consistent views. (2) Derive cost-effective broadcast schemes from the framework. (3) Reduce excessive broadcast redundancy through energy-efficient design,. (4) Explore the use of broadcasting as a basic building block to support other types of collective communication. (5) Ensure broadcast coverage with controlled 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. The new framework can easily integrate other objectives such as energy-efficiency and reliability. The results of 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.
