Project Logs

Collapse

• Still Coding Away

  Trademark • 11/06/2016 at 22:11 • 0 comments

  I love coding, but sometimes you hit the point where it gets laborious. I'm slogging through thousands of lines of code, trying to implement what works so well in simulation. The whole point of simulation is that you remove some variables, and you can build a controlled, full-scale environment in which to test certain aspects of the project. Moving from simulation to hardware means putting in some of those variables, giving up much of that control, and not having a full-scale environment for testing.

  The major variables that I'm working with include:

  • Packet structure
  • Object structure (in RF24* libs)
  • Simultaneous transmissions
  • Dropped packets
  • Multi-platform compatibility

  My C# simulator was just over 1500 LOC. This included the algorithms that would run on the nodes themselves as well as the topology generator and environment simulation code. The libraries with which I'd like to integrate total nearly 20k lines of code, and actually require more memory than the Arduino UNO has -- just 2k. After I get a bit more things working in the code, I'll need to trim down the size just to be able to run it on the Arduino at all. That's truly a difficult challenge, but it's not the one I'm working on just now.

  First, there is the challenge of just sending a packet successfully. Now that I've ripped out much of the code from the original libraries, I'm trying to put my own in and make it work. There is a certain level of coupling between the layers I'd like to change (RF24Mesh, somewhat RF24Network) and the layers I don't, (RF24, RF24Ethernet). It's something like trying to swap the engine of a Toyota into the drivetrain of a Ford. Things don't line up, the controls don't work the same, and the hood won't close properly. These things can be fixed, but it won't be easy...at all.

  Next, there is the issue of hardware. Hardware is weird, but fortunately some of the libraries TMRh20 has done take out some of the weirdness. As I modify those libraries and remove/rearrange various parts of them, the weirdness comes creeping in from everywhere. It's not trivial to send a packet, let alone pause in the algorithm just long enough to listen for responses to some request you've just made. Do you listen for a set delay time? No, because that's inefficient and makes the process slow. Do you wait till you hear *something* and then move on? What if another node needed to respond but took longer? Did you hear all of the responses you were supposed to hear? These questions plague the code implementation, and I'm only just learning the techniques to solve them.

  A note on my project(s): I do these projects as a learning experience. All of them are designed to primarily teach me something I want to learn. Often they do that and then proceed to teach me some things I didn't know I needed to learn. This project is not designed to create a marketable product, nor is it guaranteed to produce a working prototype. The project ends when I've learned all I can from it, which sometimes may be when it works, and sometimes may be when I realize that I've made some critical mistake (usually caused by some misconception I held at the beginning of the project). All this to say, I'm new to the field and you're reading the logs of a learning-experience. Now, go off and do something educational :)
  

• New Algorithm Time!

  Trademark • 10/11/2016 at 19:31 • 0 comments

  Main revision:

  I have implemented a new algorithm for mapping the mesh. Instead of each node doing BFS, I’ve decided to have one node do BFS, then send its map to the others. I coded up a method that will locally calculate the best paths through the network based on the tree structure given.

  Results:

  • On a network of 100 nodes (<=6 edges per node) the new algorithm is usually near 98% more efficient based on count of packets transmitted.For similar networks of 100 nodes with <=6 edges per node, the old algorithm transmitted around 3.5 million packets. The new algorithm transmits around 72,000 packets. This packet count does not account for packet fragmentation which would certainly need to take place, but that is handled at a different layer. Actual packet count would be higher when fragmentation is accounted for in the real world.
  • Notably, the old algorithm’s linear trend line was y=13.213x whereas the new one is showing numbers around y=2.9493x meaning that this new algorithm is actually reasonable for large networks.

  • Update: On a network of 254 nodes with <= 6 edges per node, the new algorithm uses around 490k packets compared to 70 million packets on the old algorithm. That's just 0.7% of the previous traffic.

  Worst case performance:

  • Assuming that an undirected graph can have edges, and that my maximum supported network size is 254 nodes (for implementation reasons) I should have a maximum complexity network consisting of 254 nodes and 32,131 edges. My implementation of storing and sending the network map requires this many bytes (where n = node count and e = edge count)If we substitute in the max edges we have a maximum byte count of:
  • This works out to 64770 bytes. Assuming a maximum packet payload of 32 bytes, that’s 2025 packets. After adding in the other packet header info (14 to 17b) for 2025 packets, the actual byte count is 34,425 + 64770 = 99195b. On a best-case scenario of 200kbps throughput, this might allow the full map to be transmitted from one node to another in 0.49597s, and (since in this case each node can see every other node because we are doing max edges) it would be propagated to the rest of the nodes in 2.09min (excluding the tree processing time taken between propagation steps).

  • Two minutes sounds slow, but to think that the network is fully decentralized and has 250+ layers of redundancy is remarkable. Note that this figure is propagation time, not including initial mapping time (this would also be a significant amount of time due to network complexity.
  • For clarity's sake, the above "worst case" is basically when you stick 254 nodes in a single room where they're all in range of each other and then you turn them all on. Hopefully you're not going to actually turn on more than 5 or 6 nodes in a single room (why waste more?) which would be virtually instantaneous to map.

  Challenges:

  • The simulator is currently experiencing a stack overflow problem for very large networks on the new algorithm only when debug messages are turned on. If debugging is set false (it is by default) then no problems occur. I’m planning to talk with some CS friends to see if we can make that go away.
  • This implementation will be a little trickier to implement in hardware, so I’ll need to familiarize myself a bit more with the existing libraries for smooth integration.

  I'll continue doing some work on getting this into hardware as I can. I'm trying to get much of this code into the RF24Network library because that's a pretty robust starting point.

  Source Code:
  

  The source code for the new algorithm simulator is available on GitHub under master/AlgorithmTwo. Enjoy!
  

• Reality

  Trademark • 08/27/2016 at 22:29 • 0 comments

  Almost there...
  

  I am continuing the process of porting the algorithm from the simulator (C#) to the Arduino (C++). Translation is actually fun. I'm learning some of the cool differences between C++ and C#. Dictionaries are now maps, Lists are now vectors, and queues are now deques. Oh, and Stack Overflow is super helpful :D

  Not all is smooth sailing, unfortunately. The simulation is a "perfect" environment. Every packet will be delivered, in non-simultaneous fashion, with zero latency (except for the time the processor takes). Moving to hardware introduces problems like dropped packets, simultaneous transmissions, and latency. This means that I'm having to tweak the code a wee bit to get it to cooperate. For instance, if an algorithm sends out a request there should be a response. In hardware, that response might take a few ms to come through, but the code will keep going. The algorithm will be finished before the packet actually arrives at the radio. For this reason, I'm working to add "CheckForPackets" points in the code so that we can at least give them a chance to respond properly. I'm still having some trouble with this and with simultaneous transmissions (to one receiving node). The receiving node will (in this case) simply act like it heard nothing at all (this is maddening). I'm reaching out for help on that point, so maybe my contact will know how to avoid that issue.

  There's also an issue with the mapping algorithm. It gets very slow after about 60 nodes. Mapping a mesh is profoundly complicated, and providing each node with the opportunity to map the network for itself multiplies the problem by n. While I'd like to get the algorithm better (and I have some ideas on how to do it) I have elected to proceed with implementing the current algorithm. I can always go back and modify it later to create a faster algorithm. That will require a separate process of forking the simulator, testing it (a lot) and then implementing it in C++ again. I'm already most of the way through that process with the current algorithm so I'm going to finish it out as-is and then start over if I believe the algorithm can be improved upon.
  

  For up to two nodes (because of that simultaneous transmission bug mentioned above) the network works perfectly. A total transaction of 13 packets occurs to map the two nodes, and everything looks just like it does in the simulation. I am optimistic that once the current issues are solved, I will be very close to having a set of nodes that can map reliably and quickly. I have hardware enough for six nodes at the moment, so I can only test on a limited scale. If all goes well I might purchase enough hardware to cover my college campus in a mesh, which would be pretty cool, obviously.
  

  Look for updates soon! I have a pretty cool one planned next.

  
  

• Release All the Codes!

  Trademark • 07/01/2016 at 02:14 • 0 comments

  Update

  The MeshSim program is basically done. It does all the things that I want it to do for the time being. The code is heavily commented, but I still need to clean it up a bit and make it nice and user-friendly. I figured it was time to release the code so you can compile and get the general idea anyway.

  Download
  

  https://github.com/trademark18/MeshSim
  

  Description
  

  The MeshSim program can generate a network of a specified size (or random size within a range) of up to 254 nodes. The simulator integrates my new version of the Breadth-First Search algorithm. Once a network is generated, you can turn nodes on and off to see the network map itself, heal itself, etc. You can trigger heartbeats, send packets around manually, save/load network topology and more! It is great fun, and it really makes a good test bed for these algorithms. Even if you aren't into RF, this is a cool case study on mesh mapping in general.
  

• Research

  Trademark • 06/15/2016 at 21:32 • 0 comments

  I'm doing tons of research on RF protocols. The nRF24L01+ actually uses some pretty complicated protocols. It appears that the packet structure of the real protocol does not quite match the structure of the packet object in the simulator. Perhaps I'll need to all the mapping data inside the payload of the real packet. Alas, the protocol is developed. It is just the mapping that remains. I am still working through node addressing. That stuff is complicated.

• I Had It, Then...

  Trademark • 06/08/2016 at 01:05 • 0 comments

  Well folks, as I said in the last log, I had a few goals in mind. I ran into some trouble with the example code, and so I turned to Github to contact the developer. He responded within 18 hours to alert me that the issue I was experiencing was a known bug that was fixed in the most recent version. I downloaded the new one and tried it.

  It worked. The RPi was connected to the nRF24L01 radio which could talk to another Arduino/nRF module running example web server code. From back on the Pi, the software adds a soft NIC to the Pi and then a static route is added. The RF radios are on the 10. network and the pi is on my 192. network, so this allows me to ping the remote Arduino at 10.10.2.4 IP from the Pi's terminal. On my home router I also added a static route for the 10.10.2.0 network via the IP of my Pi 192.168.1.149. I also made a DHCP reservation for the Pi and set the address to be static on the Pi's etc/network/interfaces file. Adding this static route on the LAN means I can ping the Arduino from any machine on my LAN just like it was another WiFi device. That was pretty cool.

  I was starting to look at why it was so slow (only 50% ICMP success usually) and so I started poking around the soft NIC stuff and broke something. I'm currently waiting on my Pi's SD card to be written with a new install of Raspbian. We'll try that again and be more careful next time. All part of the process. Live and learn :)

• Pain and Suffering

  Trademark • 06/07/2016 at 01:34 • 0 comments

  After adding a couple last features to the simulator (manual packet creation, node on/off, etc.) I have decided that it is done (for now) and that I need to move on to hardware implementation. I'm working though the RF24Mesh, RF24Ethernet, RF24Gateway, RF24Network, and RF24 Arduino libraries. They're really complicated. They total several thousand lines of C++. The RF24Mesh (and maybe the Ethernet one) were done by TMRh20. He has done a lot of hard work, and you should check it out.

  The Plan:

  1. Get the examples going from RF24Mesh and RF24Gateway libraries
  2. Ping nodes by IP via Raspberry Pi
     1. Quick side note: The Raspberry Pi is connected to its own NRF24L01 module and it can act as a gateway to connect the mesh network together with IP addresses and also route them out to the LAN. Pretty cool.
  3. Ping the nodes by IP via something else on the LAN
  4. Start to dig into the RF24Network library and replace the network mapping algorithm with my own
  5. That should pretty much take the rest of my life...I'd better not add a 5th step...

  And you thought I didn't have a plan!

• Adjustments

  Trademark • 05/29/2016 at 03:37 • 0 comments

  I discovered a bug in my program discussed in the previous log. It has since been eradicated, and I'm moving on. I did discover, much to my dismay, that the network generator has a chance of generating two separate networks in one go. This is because there is no check done on the randomly-generated network to ensure that each node is actually accessible form each other node. The solution is to allow several neighbors to be created for each node, thus allowing for better coverage and interconnection. My current solution is to ignore the problem and simply generate a new network if one happens to be fouled up.

  In other news, I found that when I save my network to XML out of the program, it is very close to being graphml format. I wrote an XSL transformation that changes the XML of my saved network into graphml format so I can look at the network in graphical format in yEd (free graphing software)

  I'll do a more detailed log later, but check out these cool maps of a 254 node network!

• Simulator

  Trademark • 05/27/2016 at 03:03 • 0 comments

  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!
  

• Range

  Trademark • 05/15/2016 at 21:49 • 0 comments

  Tonight I did an informal test of the range on the NRF24L01+PA+LNA modules. I tested with a base station node (which wasn't in a case) and didn't bother to guarantee LOS. There were some cars, structures, etc. obstructing the LOS at various times. I took another node and started walking.

  I managed to get to around 170-200m (guesstimating) away from the base node. I believe they are on the max power setting, so this is obviously a bit under the rating from the datasheet. Honestly I'm not too disappointed. Think of it, we are still transmitting at 200m with a $2.50 radio. The entire node costs 6$ (plus power source). For that cost, who cares how many you need to buy to cover your area. So maybe covering a respectable part of my college campus just went from 6 to 10. Not a big deal at this price point.

  A note on placement: These guys are very reliant upon LOS availability. I was surprised how clear the line is. It might be just a meter behind an obstruction, but connection comes and goes like a switch. When I place these around a campus area, it will be incredibly important to have LOS to all the places I want to serve off of that node.

  A note on progress: I still haven't touched code for this project. These are all just results based on the library examples. I will be doing significant work on the software and the results may or may not different in the end.

  I'll have some new updates coming along this week.
  

View all 14 project logs