|
|
|
|
|
|
|
Nous considérons le problème de diffusion des messages dans les réseaux radio dont les noeuds sont sujets aux pannes permanentes aux endroits inconnus. Nous considérons deux cas: les noeuds sont situés soit aux points entiers de la ligne, soit aux points d'une grille carrée ou hexagonale. Les noeuds envoient des messages en rondes synchronisées. Chaque noeud v a le même rayon R de transmission. Tous les noeuds situés dans ce rayon peuvent recevoir les messages de v, mais un noeud situé dans le rayon de deux noeuds qui transmettent simultanément, ne peut pas recevoir les messages et n'entend que du bruit. Les noeuds défectueux ne reçoivent ni n'envoient aucun message.
Nous présentons des algorithmes de diffusion dont le temps de fonctionnement en pire cas est de l'ordre optimal et nous prouvons les bornes inférieures correspondantes. Dans le cas des algorithmes non adaptatifs, cet ordre est O(D+t) et dans le cas adaptatif il est O(D+ log(min(R,t)), où t est la borne supérieure du nombre de pannes et D est le diamètre de la composante connexe fonctionnelle de la source.
|
|
|
|
|
|
|
|