Wireless Node Discovery

what is the best algorithm for wireless node discovery. suppose you have a large wireless or bluetooth network, were every node has its own range of discovery.

what is the best algorithm that开发者_运维知识库 makes any node discover about the full graph topology, ie any node will know about all other nodes in the graph?

---

Quite a bit of work has been done on this (and similar) problems. You might want to start by looking a few places like:

MIT Grid Ad Hoc Networking Project
Wireless Grids Corporation
Berkeley

Some Googling for things like "wireless grid discovery" should probably turn up more.

---

In the event that a node discovers a new node in it's range, it broadcasts a message to every other node in it's range about the presence of that newcomer.

In the event that a node receives one of these messages, if it has not seen the message before, it appends it's own identifier to a to the message, then broadcasts the new message to all the other nodes in it's range (as if it was saying "If you need to tell this guy something, tell me first because I think I'm nearer to him than you"). It must also store the id of the node it received the message from, such that it can be retrieved by the node id of the newcomer.

In the event that a node needs to send a message to another node, it looks for neighbor ids, in its local list using the node id of the recipient. it then sends the message to the best neighbor. that neighbor node is now responsible for getting the message to it's recipient using it's own local list. if it cannot find any neighbors in this way, it sends the message to every node within it's range and hopes for the best.

The local list each each node keeps indicates good "first steps" to get a message to a given recipient. the first steps are good because they came from the first of a node's neighbors to have heard about a particular newcomer. the list will not contain many bad first steps because nodes do not re-broadcast "presence of newcomer" messages if they have seen the message before, and this could only happen if the message got there by a faster route.

Hope all that makes sense, I would like to code it up in Python but I don't have the time. Note that this system might require some bootstrapping.