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