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