06-02-2013, 03:40 PM
Local Broadcast Algorithms in Wireless Ad Hoc Networks: Reducing the Number of Transmissions
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. Therefore, we wish to know whether
local broadcast algorithms based on the dynamic
2012
approach can achieve a constant approximation factor
without using position information. We answer this
question in the positive—we design a local broadcast
algorithm in which the status of each node is decided
“on-the-fly” and prove that the algorithm can achieve
both full delivery and a constant approximation to the
optimum solution.
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. Therefore, we wish to know whether
local broadcast algorithms based on the dynamic
2012
approach can achieve a constant approximation factor
without using position information. We answer this
question in the positive—we design a local broadcast
algorithm in which the status of each node is decided
“on-the-fly” and prove that the algorithm can achieve
both full delivery and a constant approximation to the
optimum solution.