2006 | OriginalPaper | Chapter
Recent Advances on Approximation Algorithms for Minimum Energy Range Assignment Problems in Ad-Hoc Wireless Networks
Author : David Peleg
Published in: Combinatorial and Algorithmic Aspects of Networking
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Ad-hoc wireless networks have no wired infrastructure. Instead, they consist of a collection of radio stations
S
={1,2,...,
n
} deployed in a given region and connected by wireless links. Each station is assigned a transmission range, and a station
t
can correctly receive the transmission of another station
s
if and only if
t
is within the range of
s
. The overall range assignment,
r
:
S
→
R
+
, determines a (directed) transmission graph
G
r
. The transmission range of a station depends on the energy invested by the station. In particular, the power
P
s
required by a station
s
to correctly transmit data to another station
t
must satisfy the inequality
$P_s \ge {\tt dist}(s,t)^{\alpha}$
, where
dist
(
s
,
t
) is the Euclidean distance between
s
and
t
and
α
≥1 is the
distance-power gradient
. The value of
α
may vary from 1 to more than 6 depending on the environment conditions at the location of the network (see [16]).