Titre du
sujet: Minimum Energy Broadcasting in Ad Hoc wireless networks
Encadrant: Ralf Klasing, Mohamed Mosbah
Laboratoire et équipe de recherche: Combinatoire et Algorithmique
Description
détaillée:
Over the
last years the usage of wireless networks has seen
a huge
increase mostly because of the recent drop in equipment
prices and
due to the features provided by the new technologies.
Unlike
traditional wired networks where signals pass from one
device to
another through a finite set of existing physical
cables,
data transmissions occur in the open air and inside a
given
coverage area.
In this
scenario considerable attention has been devoted to the
so-called
Ad Hoc wireless networks, due to their potential
applications
in emergency disaster relief, battlefield, etc.
They do not
require any fixed infrastructure. The network is
simply a
collection of homogeneous nodes, that is, radio stations
equipped
with omnidirectional antennas for sending and receiving
signals.
Communication occurs by assigning to each station a
transmitting
power. In the most common power attenuation model,
the signal
power $P_s$ of a station s decreases as a function of
the
distance in such a way that at any station t at distance
dist(s,t)
it is received with a power $P_s/dist(s,t)^{\alpha}$,
where
$\alpha >= 1$ is a constant called the distance-power gradient
whose
typical value is between 2 and 5. The signal is correctly
received by
$t$ if $P_s/dist(s,t)^{\alpha} \geq \beta$, where
$\beta \in
\real^+$ is the threshold {\em transmission-quality
parameter}.
Therefore, if $s$ correctly transmits within a given
maximum
distance $r(s)$, called the range of $s$, the transmission
power $P_s$
of $s$ is equal to $\beta \cdot r(s)^{\alpha}$.
Due to the
nonlinear power attenuation, multi-hop transmission of
messages
through intermediate stations may result in energy
saving.
Thus, a naturally arising issue is that of
supporting
communication patterns that are typical of traditional
networks,
such as broadcasting (one-to-all), multicasting
(one-to-many)
and gossiping (all-to-all), with a minimum total
energy
consumption. This problem is generally called {\em Minimum
Energy
Routing} (MER).
References:
==========
[1] M.
Flammini, R. Klasing, A. Navarra, and S. P\x{00E9}rennes.
Improved approximation results for the
Minimum Energy
Broadcasting Problem. In 2nd ACM/SIGMOBILE
Annual
International Joint Workshop on Foundation
of Mobile
Computing (DIALM-POMC 2004), pages 85--91,
2004.
ACM Press.
[2] R.
Klasing, A. Navarra, A. Papadopoulos, and S. P\x{00E9}rennes.
Adaptive Broadcast Consumption (ABC), a new
heuristic and
new bounds for the Minimum Energy Broadcast
Routing Problem.
In Proc. 3rd FIP-TC6 Networking Conference
( Networking 2004),
volume 3042 of Lecture Notes in Computer
Science, pages 866--877,
2004. Springer-Verlag.
http://www-sop.inria.fr/mascotte/Publications/?lang=fr&to_inc=Author/KLASING-R.html