With all the talk about radio links, I wonder if I could ask for some input on the following problem:
I am putting together a picaxe wireless and wired mesh. Data packets need to go from any node to any other node, and ideally it would be great for the mesh to be self configuring and to function without a supervisory PC. A simple solution is for all data packets to be forwarded to all nodes but this incurs two costs – firstly it consumes battery power from wireless nodes, and secondly it consumes radio bandwidth. To quote a practical example if a driveway sensor detects a car and wants to tell a porch light to turn on, there is no need for that packet to also go off to the water tank and pump.
The problem thus is for the mesh to discover the shortest paths to get a packet between nodes. Consider the diagram with four radio nodes. A can talk to B and C, but A can’t talk to D directly. The shortest path is ABD or ACD, but there are also quite valid paths ABCD or even ABCABCD. For a human with our fantastic visual cortex, the answers seem obvious when seen in a drawing. But it is harder when looking at things from the perspective of node B which can only see the nodes around it and has a packet it needs to forward on.
So I am thinking laterally here – instead of designing this from a visual perspective, could this be designed from a smell perspective? Assume node D was brewing some really nice coffee, and the smell of that coffee was percolating through all the other nodes, with the smell decreasing the further it traveled. A data packet would just follow its nose. Node C might smell of baking bread. Node B might be the perfume your first girlfriend wore on your first date etc.
So each node first makes contact with nodes it can talk to directly. These are simply radio data packets and they are never forwarded on – only bounced back to the sender. Node B might establish it can talk to node A and C and D. Node A might establish it can talk to node D, but only 10% of the time so that link is flagged as unreliable and is discarded.
Once these links are established (which might take a minute or two from a node being turned on), each node releases its specific scent. Node A releases the wonderful smell of cooking pizza with 10000 molecules of smell (in practice, a data packet with the number 10000.) Node A can talk to node B and C, so it sends 5000 molecules to B and 5000 to C. Node B can talk to node C and D. Each time a node processes some smell it loses some (this is important) – it is a bit like the pizza smell in a room with the windows open. So 5000 molecules arrive at node B but only 1000 are available to pass on. 500 go to C and 500 go to D. Molecules bounce around from A to C to B to D etc as well. Some go from D back to B and C but a lot less than were sent.
So node D wants to send a packet to node A. It notes there was an equal smell of pizza from node B and C so it picks one at random (or maybe some random noise is added to the exact values). The packet goes to B. Now there is a smell of pizza coming from node C, but there is a much stronger smell coming from node A. So the packet ends up taking the shortest path.
If a node is at the end of a chain it doesn’t pass on the smell. Molecules bounce around till there are none left. Each node loses a few molecules along the way and this prevents strong false pathways developing between two nodes like B and C bouncing molecules back and forth.
There probably is a mathematical formula to define the attenuation rate at each node which probably relates to the number of possible paths. I picked 1/5th as I’m expecting most messages to only go through 3-4 nodes.
Questions – is this the best model? Are there other models? Is there a formal mathematical discipline that studies this?
I think it comes in the same class as the travelling salesman problem http://en.wikipedia.org/wiki/Traveling_salesman_problem and certainly that example includes the ant colony problem, which uses the analogy of pheromones which would follow similar rules to smell. The challenge is to get the rules to fit in a picaxe (18X), but then again, an ant trail behaves as a complex organism but the ants themselves are following fairly simple rules as they rub antennae with each other and exchange pheromones.
Input would be very much appreciated as this has real practical applications for wireless picaxe comms.
I am putting together a picaxe wireless and wired mesh. Data packets need to go from any node to any other node, and ideally it would be great for the mesh to be self configuring and to function without a supervisory PC. A simple solution is for all data packets to be forwarded to all nodes but this incurs two costs – firstly it consumes battery power from wireless nodes, and secondly it consumes radio bandwidth. To quote a practical example if a driveway sensor detects a car and wants to tell a porch light to turn on, there is no need for that packet to also go off to the water tank and pump.
The problem thus is for the mesh to discover the shortest paths to get a packet between nodes. Consider the diagram with four radio nodes. A can talk to B and C, but A can’t talk to D directly. The shortest path is ABD or ACD, but there are also quite valid paths ABCD or even ABCABCD. For a human with our fantastic visual cortex, the answers seem obvious when seen in a drawing. But it is harder when looking at things from the perspective of node B which can only see the nodes around it and has a packet it needs to forward on.
So I am thinking laterally here – instead of designing this from a visual perspective, could this be designed from a smell perspective? Assume node D was brewing some really nice coffee, and the smell of that coffee was percolating through all the other nodes, with the smell decreasing the further it traveled. A data packet would just follow its nose. Node C might smell of baking bread. Node B might be the perfume your first girlfriend wore on your first date etc.
So each node first makes contact with nodes it can talk to directly. These are simply radio data packets and they are never forwarded on – only bounced back to the sender. Node B might establish it can talk to node A and C and D. Node A might establish it can talk to node D, but only 10% of the time so that link is flagged as unreliable and is discarded.
Once these links are established (which might take a minute or two from a node being turned on), each node releases its specific scent. Node A releases the wonderful smell of cooking pizza with 10000 molecules of smell (in practice, a data packet with the number 10000.) Node A can talk to node B and C, so it sends 5000 molecules to B and 5000 to C. Node B can talk to node C and D. Each time a node processes some smell it loses some (this is important) – it is a bit like the pizza smell in a room with the windows open. So 5000 molecules arrive at node B but only 1000 are available to pass on. 500 go to C and 500 go to D. Molecules bounce around from A to C to B to D etc as well. Some go from D back to B and C but a lot less than were sent.
So node D wants to send a packet to node A. It notes there was an equal smell of pizza from node B and C so it picks one at random (or maybe some random noise is added to the exact values). The packet goes to B. Now there is a smell of pizza coming from node C, but there is a much stronger smell coming from node A. So the packet ends up taking the shortest path.
If a node is at the end of a chain it doesn’t pass on the smell. Molecules bounce around till there are none left. Each node loses a few molecules along the way and this prevents strong false pathways developing between two nodes like B and C bouncing molecules back and forth.
There probably is a mathematical formula to define the attenuation rate at each node which probably relates to the number of possible paths. I picked 1/5th as I’m expecting most messages to only go through 3-4 nodes.
Questions – is this the best model? Are there other models? Is there a formal mathematical discipline that studies this?
I think it comes in the same class as the travelling salesman problem http://en.wikipedia.org/wiki/Traveling_salesman_problem and certainly that example includes the ant colony problem, which uses the analogy of pheromones which would follow similar rules to smell. The challenge is to get the rules to fit in a picaxe (18X), but then again, an ant trail behaves as a complex organism but the ants themselves are following fairly simple rules as they rub antennae with each other and exchange pheromones.
Input would be very much appreciated as this has real practical applications for wireless picaxe comms.
