1
\$\begingroup\$

I am playing with the idea of mesh network path finding. The goal is that each node can find the most efficient path through other node to a hub.

One way I could approach it is by flooding the network so each node can decide which node is best to connect with. See the following pseudo code that each node runs

Ping out my ID
Wait for responses (all nodes that heard the ping reply their ID and to-hub 'cost')
Ignore replys with no to-node cost, they aren't connected to hub yet
Record ID and Connection Quality + to-hub cost
Pair with lowest cost node
Record as Parent
  Wait for connections from other nodes, record as child
  Forward data from children to parent

The only problem is that when a node pings, multiple nodes may hear it and respond at the same time, possibly creating interference, and giving the node no time to record neighbours.

Possible solution: Each node is delayed by a factor of its ID and time it takes to respond

How else may I limit the amount of interference in my network?

\$\endgroup\$
  • \$\begingroup\$ Ping is perhaps the wrong term to use as it is an end point focused query. What you should say is a broadcast. You don't say what the protocol is or the packet construction, but most modern systems have unique ID's for broadcast etc. The problem you are describing has been covered with CDMA (Collsion Detect Multiple Access) system with variable backoff. But of course your RF based system will add an additional layer of complexity. The original ALOHA system design considerations might also inform your design. \$\endgroup\$ – placeholder Sep 13 '14 at 14:46
  • \$\begingroup\$ It is important to note that routing cost is not only a function of the number of hops but also the link strength: a node directly connected to the base but far from it or obstaculized might be a poorer choice as router than a two-hop node strongly connected to its 'parent' and with lots of parent choices in case theirs goes missing. \$\endgroup\$ – Guillermo Prandi Sep 17 '14 at 2:05
  • \$\begingroup\$ @GuillermoPrandi Yes, forgot to mention that in the code. \$\endgroup\$ – liamdiprose Sep 17 '14 at 2:10
0
\$\begingroup\$

This sort of protocol can be really difficult to solve. I'll say a few words about a project I was involved with years ago.

A "new node" didn't ping rather it listened - basically it picked-up on any nearby node that was already a member (it was listening for the node_members regular hub transmission). Doing it this way means the new_node didn't interfere with anything and, could silently choose the optimum "parent" i.e. the node_member with the most efficient transmission to the hub (master).

At regular intervals (obviously recognizable by the new_node), each node_member had a small timeslot to accept a "new node" request (should one come along). Basically this worked because there was always a "spare" receive time slot "offered" by only one node_member at a time that could be used for the new_node to make its presence known.

Once the parent (node_member) adopted the new_node, the whole network then had to accomodate space for the new guy to become a bona fide node_member and this does take some thinking about.

It's an interesting problem and probably best solved and developed by writing a PC program that simulates a variable system with random path losses and drop-outs. That's what we started to do but, the job fell-through for commercial reasons that I don't need to go into.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.