Quel est le meilleur algorithme pour la découverte de noeuds sans fil. Supposons que vous ayez un grand réseau sans fil ou bluetooth, chaque nœud a sa propre gamme de découverte.Découverte de nœud sans fil
Quel est le meilleur algorithme qui permette à un nœud de découvrir la topologie complète du graphe, c'est-à-dire que n'importe quel nœud connaîtra tous les autres nœuds du graphe?
Un peu de travail a été fait sur ce problème (et des problèmes similaires). Vous pouvez commencer par regarder quelques endroits comme:
MIT Grid Ad Hoc Networking Project
Wireless Grids Corporation
Berkeley
quelques recherches sur Google pour des choses comme devrait probablement se présenter plus « découverte du réseau sans fil ».
Dans le cas où un nœud découvre un nouveau nœud dans sa plage, il diffuse un message à tous les autres nœuds dans sa gamme sur la présence de ce nouveau venu. Dans le cas où un nœud reçoit un de ces messages, s'il n'a pas vu le message auparavant, il ajoute son propre identifiant à a au message, puis diffuse le nouveau message à tous les autres nœuds dans sa portée (comme si elle disait "Si tu as besoin de dire quelque chose à ce type, dis-le-moi d'abord parce que je pense que je suis plus proche de lui que toi"). Il doit également stocker l'identifiant du noeud dont il a reçu le message, de sorte qu'il puisse être récupéré par l'identifiant de noeud du nouveau venu.
Dans le cas où un nœud a besoin d'envoyer un message à un autre nœud, il recherche des identifiants de voisin, dans sa liste locale en utilisant l'identifiant de nœud du destinataire. il envoie ensuite le message au meilleur voisin. ce noeud voisin est maintenant responsable de l'envoi du message à son destinataire en utilisant sa propre liste locale. s'il ne trouve pas de voisins de cette manière, il envoie le message à tous les nœuds de son rayon d'action et espère le meilleur.
La liste locale que chaque nœud conserve indique les "premières étapes" à suivre pour obtenir un message à un destinataire donné. Les premiers pas sont bons car ils viennent du premier voisin d'un nœud pour avoir entendu parler d'un nouveau venu. la liste ne contient pas beaucoup de mauvaises premières étapes parce que les noeuds ne retransmettent pas les messages "présence de nouveaux arrivants" s'ils ont déjà vu le message, et cela ne peut arriver que si le message est arrivé par un itinéraire plus rapide.
J'espère que tout cela a du sens, je voudrais le coder en Python mais je n'ai pas le temps. Notez que ce système peut nécessiter un amorçage.