Titre du sujet: Bringing internet into villages using wireless communication.
Encadrant: Ralf Klasing, Olivier Beaumont
Laboratoire et équipe de recherche: Combinatoire et Algorithmique
Description
détaillée:
In radio networks
a set of radio devices communicate by using radio
transmissions
which, depending on the technology used, are subject to
different
interference constraints. This means that only certain
transmissions
can be performed simultaneously, therefore the devices
have to act
in a cooperative manner in order to achieve an effective
flow of
information in the network. In this context, we study a problem
proposed by
France Telecom, about "how to provide Internet to villages".
The houses
of the village are equipped with radio devices and they
want to
access the rest of the world via Internet. For that
purpose
they have to send (and receive) information via a gateway
where there
is a central antenna. This creates a special
many-to-one
information flow demand in which the access to the
gateway
must be provided. Therefore, we will consider a specific
traffic
pattern, similar to a single commodity flow with a
distinguished
node representing the gateway, called sink and
denoted
sink.
Nodes are
all equipped with a communication device that can be tuned
either to
transmit or to listen (exclusively). Unlike in wired networks,
when a node
u transmits a message it does not use a resource as simple
as some
capacity on a link; instead it produces a signal that may prevent
other
transmissions to occur. The set of possible concurrent transmissions
follows
from a complex n-ary interference relation which properly models
the idea
that the noise intensity must be small enough compared to the
signal intensity.
In order to get tractable models, a widely used
simplification
consists of associating to each node a transmission
area in
which it can transmit a message and an interference zone in
which it
produces a strong noise. Then, the
communication from a node
u to a node
v is possible if v is in the transmission area of u, and no
third node
transmitting has v in its interference zone. Note that, by
doing so,
we replace the n-ary relation with a binary relation: two
(possible)
transmissions (that we will denote calls) can be performed
concurrently
when they do not interfere.
References:
==========
[1] J.-C.
Bermond, J. Galtier, R. Klasing, N. Morales, and S. Pérennes.
Hardness and approximation of Gathering in
static radio networks.
In FAWN06, Pisa, Italy, March 2006.
[2] R.
Klasing, N. Morales, and S. Pérennes. On the Complexity of
Bandwidth Allocation in Radio Networks with
Steady Traffic Demands.
Technical report, INRIA Research Report
RR-5432 and I3S Research
Report I3S/RR-2004-40-FR, 2004.
http://www-sop.inria.fr/mascotte/Publications/?lang=fr&to_inc=Author/KLASING-R.html