Categories

Surprises

Well, since we give the project. I’ve been occupied to organized some surprise, I hope you’ll enjoy this…

Tomorrow…. 😉

Welcome to the Jungle

Before reading this post, you might want to make sure you have read this one, and this one. Just saying.

The purpose of this post is to describe the algorithm known as Jungle and the problem is solves.

Synchronization

Making WaDeD a little bit more abstract that what it actually is–which, conveniently for me, makes all the electronics disappear ;-)–, you can see it as follows: a single device holds a set of messages. When two devices meet, we want them to synchronize their sets, so that when walking away from one another their internal states are the same. Since the interaction might be short, we want this to be as fast as possible. We also want to reduce the energy costs of the whole interaction as much as possible. The energy cost of using the radio, as much in transmitter mode than in receiver mode, is orders of magnitude higher than the cost of CPU cycles or FRAM access over SPI, so we must critically minimize the number of radio packets transmitted. However, once you have started transmitting, the energy cost of adding an extra byte is not really significant, so as much as energy is regarded the size of the packets is of minor importance (it actually is pretty much important, but for reasons of radio transactions efficiency and packets integrity). Furthermore, since any number of devices can be in the same area, the communication should not isolate devices. Instead they should all talk together, so that exchanged messages do not need to be repeated.

Put in other words, we want to compute the symmetric difference of two sets of messages (that is, the elements that they do not have in common) and then exchange those messages, while minimizing the number of times a device communicates with another.

Data storage

In order to do this, we need to be able to quickly compare the state of the memories of two devices. As mentioned in a previous post, hash trees are really convenient data structures to do integrity checks and compare data, provided they are organised precisely in the same way, regardless of the device, their order of arrival and the other data that the device is holding.

This is a very strong constraint: if the messages are stored differently, the trees might have to make more comparisons (consuming energy), or, even worse, they might never completely synchronize, and be stuck in comparing their hashes forever. Can we find a way to organize data so that the same two message will end up being stored in the same place, regardless of what other data is present and the order they were inserted? It appears we can, using a very common structure, namely open hash tables: each leaf of the tree will point to a chained list. Given the 64-bits identifiant of a single message, we determine in which list it should be inserted. The leaf pointing to a list contains a hash of the concatenation of the IDs of the list. The lists are sorted by ID, so the hashes of their leaves differ if and only if the lists differ.

hashtree

That’s it, here is our structure. Messages are stored in small lists, which form the leaves of a hash tree. It is deterministic in its insertion, and comparison can be fast because of the hash tree structure.

The algorithm

Say two devices meet. We want to design a procedure which, at the end, leave the two devices with the same messages in memory, while making them communicate as few as possible, and we can use the augmented hash trees that we have implemented.

In the following description, we need a bit of terminology. The nodes of the tree are divided in two categories: the leaves, which have no sons, and the internal nodes, which have sons. Among those, the penultimate layer (that is, the internal nodes whose sons are leaves) will deserve special treatment. When we talk about broadcasting an internal node, we mean transmitting an information about its position in the tree, and its hash. When we talk about broadcasting a leaf, we mean transmitting an information about its position, and the IDs of all the elements in the list that corresponds to the leaf.

Here are the rules that drive the behaviour of a WaDeD in its communication:

  1. If nothing has happened over a certain period of time, broadcast your root.
  2. If getting a root, compare it with your own. If the hash match, do nothing, otherwise broadcast all the sons of the root.
  3. If getting a node, compare it with the corresponding nodes in your own tree. If they match, do nothing. Otherwise:
    • If the node is not on the penultimate layer, broadcast its sons.
    • If  it is on the penultimate layer, its sons are leaves. For each son, broadcast the leaf.
  4. If getting a leaf, compare it with the matching list in your own tree. For every ID that you hold and is not in the distant list, broadcast the corresponding message. If no message was broadcasted, broadcast your own corresponding leaf.
  5. If getting a message, check whether a message with this ID already exists in memory. If it does, do nothing, otherwise insert it in memory and update the tree.

This algorithm has good properties: when two devices are in a conversation, they are strictly moving down their respective trees, so there can never be any loop in the conversation. A typical exchange will appear as this:

WaDeD A sends a ROOT
root: 1D5DD10E

WaDeD B sends a ROOT
root: B04424B1

WaDeD A sends a NODE N0
sons: 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F 21E5338F

WaDeD B sends a NODE N3
sons: EEDFA82 EEDFA82 3D7B7AC4 EEDFA82 EEDFA82 EEDFA82 EEDFA82 EEDFA82

WaDeD A sends a NODE N11
sons: 0 0 0 0 0 0 0 0

WaDeD B sends a LIST N144
list size: 1
Element 1: 1804A114 

WaDeD A sends a LIST N144
list size: 0

WaDeD B sends a MESSAGE
I'm a WaDeD!

WaDeD A sends a ROOT
root: B04424B1

WaDeD B sends a ROOT
root: B04424B1

This is an actual dump of two WaDeD synchronizing. You can see that the trees have eight sons. The synchronization process is extremely fast if the trees are similar to begin with, and not remarkably longer than a list comparison if the trees are hugely different.

Welcome to the Jungle

But another strong property of this algorithm is that it is stateless: everything is broadcast to everybody, and any device arriving in the middle of a synchronization can benefit from hearing a message. Potentially this leads to conversations dividing and many, many messages being exchanged–hence the name Jungle–, but the WaDeD always act upon messages it gets in a way that leads to increasing its knowledge of the environment. After a few seconds, the jungle calms down: all devices share the same memory state.

In conclusion, we have an algorithm that is extremely efficient when synchronizing two sets that are close and still very good when the sets differ a lot. It deals well when a lot of devices are communicating at the same time, and, since a given device can enter a conversation at any point, missed packets cannot do more harm than having to start the conversation a few messages before.

I think that’s pretty neat.

Hello Twitter

Hello awake people,

Last night,we made some final upgrading to the jungle protocol. Sacha and Patrick succeed to upgrade significantly the synchronisation time, of one message.

We also succeed to made our first tweets, from a WaDeD (follow @_WaDeD).

I mainly work on the presentation for this afternoon.

WaDeD it!

Yeah we did it!

Last night, 4 WaDeD has sync their messages, using the WaDeD PCB,  so the SX1231. It’s a relief, to see the basic but nonetheless complex, concept of the project working correctly.

For now on, we sync messages using the WaDeD protocol. The usb interface is ready, to be tested. But we are facing, ram overflow. The tree is currently in the ram, and takes too much place, for now some cleaning is currently being done.

Well I guess it’s all.

And follow on twitter @_WaDeD 😉

 

 

Hurray hurray!

A simple version of WaDeD with the jungle protocol is working for real!

Hurray hurray! Long life to WaDeD!

Sleepy WaDeD

The WaDeD that won’t be connected to an other system (such as a computer) but only to a battery must use very little energy, so we need to make them sleep.
Today we made the WaDeD take its first nap and wake up from it =)

USB, Y U NOT WORK!

First I would like to thank wordpress for saving the title of my draft after I finished it. It’s not like the content was useful…

So, again, this post is about the story of a connection between an Android and a WaDeD.

First, we had only an Android, and no WaDeD, so it was not possible to test the actual connection. But Google provided a simple API that was supposed to dialog easily with USB devices, for Android 3 and up. So we found an Android 4, but we could not test the connection with no device, and any attempt to simulate a USB connection was unsuccessful. No problem, we’ll wait for the WaDeD.

Then came the WaDeD. And it was easy to communicate though USB with it through a computer. But we had no adequate cable. No problem, we’ll wait for the cables.

Then came the cables. They sure were micro USB to micro USB cable, but one end was micro USB A, that no one uses. But that is the closest cable to what we want that exists. No problem, we’ll solder our own cable.

Then came the solder. With my legendary soldering skills (not!) and the help and advice from Hubert, we made the cable we wanted. But it did not work, even with applications from Google Live that worked for other. No problem, we’ll find a On The Go cable.

Then came the On The Go Cable. There is no easier. Just plug for instance an USB key and it is detected but the Android. At least it is supposed to. Because Google decided to disable this functionality in its devices. Well we were not able to make it work with any Android device we had.

So it seems we won’t be able to connect the WaDeD to an Android.

So what are our alternatives:

  • We could use a USB to Bluetooth board, that makes the bridge from USB to Bluetooth. This solution is close to what we wanted. But since we have no time to make this board, we’ll have to use a computer instead…
  • Since we have to use a computer, why bother using the Android at all. We could just have a program on the computer. But this is far from what we wanted, but in a second hypothetical time we would just have to make a small LCD + keyboard device to replace the computer.

Well, this is a sad time for WaDeD, and we did not see it coming, since the Internet seemed to acknowledge the fact that Android devices can be used as USB host. But not with our Android devices…

 

Flashnews: using Issam’s smartphone, we were able to detect an USB key! But the WaDeD was undetected… Anyway we won’t work on Issam smartphone, so it just prove that it is not our fault if we can make any connection.

 

WaDeD Alpha news

It has been a while since I said something here, but I came with good news.
The Waded Alpha is done!

We have finished to make a program to the tp boards that implements all the dead drops concept.
Even though the program is a dumb version of the WaDeD that is to come, it is still a smart one.

WaDeD alpha consist in an almost stateless node that stock messages in a simple linked list.

The program sends from time to time 8 message IDs from his list, the other nodes that will check which ID they have or not.
They will ask for them in case they don’t have it, will send their tombstones in case they’re already dead. And, case neither case is true, he will check in his list that someone have already made those nodes broadcast, so they won’t send it in their next ID broadcast.

The Alpha is also conscious of its network, if it plans to send a message, and someone send that same message, or a similar one, he’ll avoid repeating needless information.

Alpha user interface:
Since it’s connected trough USB, it uses this bus to send and receive commands from the user. Commands are strings made by human readable characters finished by a linefeed.
The commands already implemented are:
ping
send_txt1 – this command is followed by the message and destiny id and the message itself. Used to insert messages in the network
send_txt2 – same as above, but creates an ID himself
set_id – followed by the ID the user wish to have.
WaDeD answers:
ack
nack – returned when an error occurred. this message is followed by an error value
rec_txt – message destined to the user. It’s followed by the source’s id and the message
rec_tombstone – tombstone delivered to a message which has the user as source. This way the user can know if a message he sent was received.

Next steps: adaptations!!!
Adapt the code to run in the WaDeD boards.
Change the radio functions to use the transceiver
Change the way messages are stored from a list to a tree.

There is still a long way to go, but I’m proud of the Alpha state!
(obs: I’m really amazed by the teachers participation in the project, I have never seen a teacher make a white night helping students)
(obs2: That led cube is freaking amazing!!)

Sending large messages

For two days, I worked on sending large messages with the SX1231, after a very annoying detail that have make me lost a lot of time I finally succeed.

Now, I work on using EXT events on the DIOs,

Then I will work on the CSMA for the Radio communications.

WaDeD simulation

Here is the first results of the WaDeD environment simulator. Until now it has only be usefull to test and debug the  memory function in a more realistic environment than just battery tests. But here is some result of the WaDeD environment working.

What the simulator does:

  • It simulates some fix WaDeD placed in a grid, far enough not to communicate with each other
  • It simulates one WaDeD moving in this environment.
  • It uses as much as possible the same code as the embedded one.

What the simulator does not yet:

  • It does not simulate the “jungle protocol”, meaning how the WaDeD will synchronize with each other. For now, the synchronization is just a lot of dumb insertions in the Merkel trees.

So what happens in this simulation, is that all WaDeD start with one message of its own, different for each. And then the moving WaDeD goes from the top left to the bottom right, in diagonal.

The result expected is that the moving WaDeD will gather all the messages from the fix WaDeD close to the diagonal, and that this WaDeD will have a portion of this gathering, more and more important as we go down and left.

And this is exactly what we get! So all the bugs are resolved and all is working for now.

Continue reading WaDeD simulation