14-02-2013, 09:39 AM
Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of Transmissions
Local Broadcast Algorithms.pdf (Size: 341.97 KB / Downloads: 37)
Abstract
There are two main approaches, static and dynamic,
to broadcast algorithms in wireless ad hoc networks. In the static
approach, local algorithms determine the status (forwarding/nonforwarding)
of each node proactively based on local topology
information and a globally known priority function. In this
paper, we first show that local broadcast algorithms based on the
static approach cannot achieve a good approximation factor to
the optimum solution (an NP-hard problem). However, we show
that a constant approximation factor is achievable if (relative)
position information is available. In the dynamic approach, local
algorithms determine the status of each node “on-the-fly” based
on local topology information and broadcast state information.
Using the dynamic approach, it was recently shown that local
broadcast algorithms can achieve a constant approximation
factor to the optimum solution when (approximate) position
information is available. However, using position information
can simplify the problem. Also, in some applications it may
not be practical to have position information.
INTRODUCTION
Wireless ad hoc networks have emerged to support applications,
in which it is required/desired to have wireless
communications among a variety of devices without relying on
any infrastructure or central management. In ad hoc networks,
wireless devices, simply called nodes, have limited transmission
range. Therefore, each node can directly communicate
with only those within its transmission range (i.e., its neighbors)
and requires other nodes to act as routers in order to
communicate with out-of-range destinations.
One of the fundamental operations in wireless ad hoc networks
is broadcasting, where a node disseminates a message
to all other nodes in the network. This can be achieved
through