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.
Since July 2003 |