The simulator lives! After many hours of finals-week type mental anguish, I have completed the basic functionality of the network simulation software. It can generate a network of random size (# of nodes) and then the nodes can search through the mesh and build local directories of how to reach any other node. I designed the algorithm to consume more resources during the mapping phase and build a directory that is optimized for quick lookups. This will make latency times very low for the average packet traversing the network.
As the final test on the algorithm, I mapped a network of 254 nodes (with up to ~4 neighbors each) and the process took around 7 minutes or so to spill out all the transmissions onto my terminal screen. There were 1.14 million packets transmitted and processed successfully.
The algorithm works on the principle that each node doesn't necessarily need to know the structure of the entire mesh. Practically speaking, each node only needs to know where to send a given packet next. This algorithm is a modification of Breadth-First Search (BFS, discussed in a previous log) and has been modified to result in a Dictionary of nodeID's to next nodes. This means that a node has something like this in its local memory:
This way, when someone is trying to send a packet across the network, we don't have to receive it, go diving recursively through a tree structure, find the next hop, and pass it on. All we have to do is look at a tiny Dictionary of target/next-hop pairs and fire it off.
Next I'll start working on some more features for the simulator to help develop protocols for the network's transmissions. Eventually I will port it over to something that can run on the Arduino.
Yes, the MeshSim software is going to be open-source once I clean it up a bit. Check back soon!