Diffusion dans les réseaux ad-hoc sans fil

On considère les réseaux sans fil dans lesquels les sommets ne peuvent communiquer que par diffusion : lorsqu’un sommet souhaite partager une information, tous les sommets à sa portée reçoivent cette information. La principale contrainte à prendre en compte lors de l’étude de la communication dans de tels réseaux est le phénomène d’interférences. À un instant donné, si un sommet reçoit simultanément deux informations de deux sommets voisins distincts, alors on considère ces informations perdues. Pour mieux appréhender le phénomène d’interférences, on considère que le temps est discrétisé, découpé en étapes (ou slots). On se place également sous l’hypothèse de communication synchrone : les étapes sont des fragments temporels élémentaires, et les communications qui auraient lieu durant le même fragment sont considérées comme simultanées. Le réseau est modélisé par un graphe non-orienté, et on suppose une connaissance parfaite du réseau à tout instant pour résoudre les problèmes de communication rencontrés. On s’intéresse dans ce chapitre à des problématiques liées à la diffusion dans ces réseaux sans-fil. Étant donné un sommet source possédant une information, planifier les émissions des sommets du réseau pour que tous les sommets reçoivent l’information. Dans certain cas, on a une vue d’ensemble du réseau pour résoudre ce problème ; on parle alors d’algorithme de diffusion centralisé. Dans d’autres cas, les noeuds n’ont pas connaissance les uns des autres et on doit concevoir des algorithmes distribués : chaque noeud a un ensemble d’actions qu’il peut entreprendre en fonction des messages qu’il reçoit.

Le problème de diffusion à distance d est une variante du problème de diffusion dans laquelle une partie seulement du réseau doit être informée. Étant donné un sommet — une source — et une distance d (en nombre d’arcs), planifier les émissions pour que tous les sommets à distance d de la source reçoivent l’information. On dit qu’un sommet est informé lorsqu’à une étape il reçoit l’information d’exactement un sommet lui-même déja informé. On s’intéresse dans la suite au problème de diffusion à distance 2 initialement étudié par Alon et collab. [2], Bar-Yehuda et collab. [3] puis, plus tard, Cogis et collab. [26]. Tous les sommets à distance 1 de la source peuvent être informés en une étape : la source émet seule.

Le problème consiste donc à planifier les émissions des sommets à distance 1 de la source pour informer tous les sommets à distance 2 strictement. On appellera émetteurs les sommets à distance 1 de la source et récepteurs les sommets à distance 2 strictement. On supposera que les récepteurs ne peuvent pas être utilisés pour informer d’autres récepteurs. Dans ces conditions, le problème de diffusion à distance 2 est simplifié : on peut supposer que le graphe induit par les sommets émetteurs et récepteurs est biparti. On appelle ce graphe biparti (dans lequel sont ignorées les arêtes entre émetteurs et entre récepteurs) le graphe biparti de diffusion.

Diffusion à Distance 2
Donnée : G = (X, Y, E) un graphe biparti de diffusion, k ∈ N
Question : Existe-t-il k ensembles d’émetteurs X1, …, Xk ⊂ X tels que :
∀y ∈ Y, ∃Xi : |N(y) ∩ Xi | = 1 ?

Une solution à ce problème est un schéma de diffusion en k (au plus) étapes, qui correspond à k ensembles d’émetteurs. Les résultats annoncés dans ce qui suit ne tiennent pas compte de la première étape triviale lors de laquelle la source communique l’information à ses voisins. Ainsi, lorsque l’on parlera de compléter une diffusion à distance 2 en, par exemple, trois étapes, il s’agira en fait de trois étapes pour informer les récepteurs après réception de l’information par les émetteurs : quatre étapes au total. On s’intéressera également au problème de la diffusion maximum en une étape qui consiste à maximiser le nombre de récepteurs informés en une étape d’émission.

Diffusion Maximum
Donnée : G = (X, Y, E) un graphe biparti de diffusion, p ∈ N
Question : Existe-t-il un ensemble d’émetteurs S tel que :
|{y ∈ Y : |N(y) ∩ S| = 1}| ≥ p ?

On s’intéresse dans ce chapitre à deux aspects des problèmes de diffusion à distance 2 et de diffusion maximum : leur complexité et les bornes sur le nombre d’étapes ou de sommets informés en une étape. On s’est penché sur ces aspects des deux problèmes dans trois cas particuliers :

— Lorsqu’il est possible d’ordonner les récepteurs pour que les voisinages des émetteurs forment des intervalles.

— Lorsqu’il est possible d’ordonner les récepteurs pour que les voisinages des émetteurs forment des intervalles circulaires.

— Lorsque les voisinages des émetteurs sont donnés par un graphe de disques unitaires.

Notons que le cas des intervalles circulaires généralise le cas des intervalles et que les résultats obtenus sur les bornes seront les mêmes. On décrit tout de même les résultats qui ont été d’abord obtenus sur les intervalles puis ceux dans les intervalles circulaires. L’intérêt est double : les preuves dans le cas des intervalles circulaires utilisent des mécanismes similaires aux preuves dans le cas des intervalles ; et les complexité des algorithmes ou réductions polynomiales utilisées sont moindres dans le cas des intervalles.

Le modèle de communication retenu est classique : graphe sous-jacent non-orienté, temps discrétisé, communication synchrone et connaissance parfaite du réseau à tout instant. De nombreuses études sous ces hypothèses ont vu le jour, comme par exemple .

Les travaux présentés dans ce chapitre sont principalement inspirés par Alon et collab. [2], Bar-Yehuda et collab. [3], Cogis et collab. [26], qui traitent du problème de diffusion à distance 2 dans des graphes sans structure particulière. Ils ont pu concevoir, indépendamment, des algorithmes polynomiaux produisant des schémas de diffusion en O(log² n) étapes, où n est le nombre de récepteurs. Ils montrent également que la borne supérieure de O(log² n) étapes est serrée en exhibant une famille de graphes infinie requérant log² n étapes pour compléter la diffusion à distance 2.

À notre connaissance, le problème de diffusion à distance 2 n’a pas été étudié dans le cas où le graphe sous-jacent n’est pas quelconque. Dessmark et Pelc [30] traitent du problème de diffusion (général) lorsque le graphe sousjacent est un graphe de disques. Ils proposent un algorithme centralisé de diffusion en O(D) étapes où D est le diamètre du graphe. On voit ici que l’hypothèse de ne pas utiliser les noeuds à distance 2 d’une source pour en informer d’autre est forte : sans cette hypothèse, la diffusion à distance 2 peut être complétée en O(1) étapes, or on montre que log n étapes peuvent être nécessaires dans notre cas. Notons également que la notation «grand O » dans le schéma de diffusion en O(D) étapes calculé par l’algorithme de Dessmark et Pelc [30] cache en fait une constante multiplicative d’environ 400. En pratique, pour toute instance que l’on peut être amené à manipuler,notre solution en 4 + 4 log n étapes sera meilleure.