Optimisation des réseaux de capteurs sans fil
Classified in Technologie
Written at on 
français with a size of 2,92 KB.
Arêtes BLEU
Iteration 1:
Choisir les arêtes bleus entre les sommets (un noeud choisit le chemin de plus faible valeur vers un voisin).
Les sommets ayant des arêtes bleus se dirigeant l’une vers l’autre se transforment en fragment. Un leader est élu (ici le sommet arrivant en premier dans l’ordre alphabétique).
Les autres arêtes bleus se dirigeant vers un fragment sont intégrés une à une.
Iteration 2:
De nouvelles arêtes bleus sont choisis entre les fragments (les liens inter fragment ne compte plus).
Les fragments fusionnent (ceux avec la double arête en premier), un nouveau leader est choisis pour 2 fragments qui fusionnent avec un double arête (entre les 2 noeuds) qui font la liaison (ex: C et D pour la dernière figure).
Allocation TDMA
On cherche ici à allouer une couleur pour chaque noeud:
Chaque noeud possède un état (Identité, Etat) {Etat = Indécis / Colorié}
Faire en boucle jusqua resultat: Chaque noeud envoie le statut (Id, Indécis) à leurs voisins. On donne une couleur C1 au noeuds dont tous leurs voisins ainsi qu'eux même sont indécis et qu’aucun de leurs voisins ne possèdent un Id plus grand.
Approches proactives (par periode)
table de routage
OLSRP Optimized Link State Routing Protocol
Paquets Hello
Chaque nœud envoie la liste de ses voisins directs et connaît du la liste des ses voisins à un saut et à deux sauts
Noeud MPR
limite le nombre de transmission a faire pendant inondation, choisi de maniere a couvrir tous les nœuds qui sont à deux sauts de suite
Heuristique: Voisins indispensables, Voisins avec le plus de voisins à deux sauts
Trouver les MPR
Faire tableau (nom|voisin(1saut)|(2sauts)|MPR), voisin 1saut -> 2sauts, enlever superflu/redondant, reste est MPR, choisir les MPR avec les nom avec le plus de MPR
Approches réactives (quand on en a besoin)
DSR: pas de table de routage et quand une station veut envoyer un paquet a destination il fait une inondation et envoye le paquet par le chemin le plus court
Approches géographiques (planaire)
Algorithme Greedy: probleme, pas de voisin plus proche, obstacle, zone vide
Algorithme Face (planaire): cycle ne contenant pas de nœud ou d’arête
Algorithme Right Hand Rule Face: On tourne toujours dans le sens inverse des aiguilles d’une montre
Changement de face avant de croiser la droite
Utilisé dans le protocole Greedy Parimeter Stateless Routing
Capable de détecter les arêtes qui se croisent et de les enlever