Categories

Congratulations to all and farewell!

This post closes this blog. Congratulations to all, you were amazing : WAMI who made their whole project work at the last minute, RoseRolls for your hack fun and your enthusiasm, HARP for your 3D POV which is clearly astonishing, Roled for the beauty and fun of your mega-cube, and WaDeD for such an innovative work – in the hardware as in the software and algorithmic parts.

There were good times, there were hard times, there were laughs, and sometimes a little tears. But you always kept moving forward, with motivation, pugnacity, and always keenness and good mood. This was a pleasure for us to work with you.

This is clearly an occurrence that we will not forget. Thanks to you all.

The Android application localizes !

On the last day, we’ve rebuilt the Android application completely from scratch and it works ! This screenshot has been made in the foyer of Telecom. In red are the tweeters, in black our position.

The application will be better tomorrow, stay tuned 😉

2013-05-03 00.20.48

last two weeks

It’s been a wild ride. In the past 2 weeks we worked more than ever and had some sleepless nights to get to where we are now. Many tests with the proximity detector (unfortunately we decided to leave them in the end because, although they work, they are ugly and not very stable). The animations are progressing and we try to use all the cube’s potential. We came back to the kinect and we got some cool surprises to show you even though we didn’t get much time on it.

We are finishing the presentation and rehearsing it. Hope to see you all tomorrow.

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.

The cube’s last moments…

Cube last moments

(I’m kidding of course, it’s perfectly fine ;-))

[HARP] Final days…

For the past few days I’ve been working hard with the team to finish everything on time. Our system is now running smoothly which is great! Until friday we’ll be focusing on making the best presentation we can on friday. It will feature impressive animated holograms and I hope the audience will enjoy it.

D-2

This post sums up all the work we have done in the last three weeks. It is an indirect reply to the other post http://rose.eu.org/2013/?p=1224.

We have tested each of the parameters on the transmission line between the tweeters and our receiver.

Here is a review of the tests we conducted :

Radio transmission :

System : the master sends a synchro messages to the tweeters and orders them to beep at the same time.
Signal observed : signal entering the tweeter
Result : a maximum of 200µs shift is observed
Conclusion : this is a negligeable parameter on the transmission line

Bip detection (here comes the hard part)

This is the main source of uncertainties.

Filtering

The filtered we have design thanks to Alexis Polti is resistant to type I and type II errors (false positive and false negative errors).
First we apply a pass band filter : to remove the noise from other frequencies.

  • band pass [20800Hz; 21200Hz]
  • stop band (40dB attenuation at least out of [20000Hz, 22000Hz]

We square each samples to get the power of our filtered signal and then we apply a low pass filter in order to get the enclosure of the power.

  • band pass [0Hz, 1600Hz]
  • cut-off 1800Hz

Triggering

The trigger is designed as follow :
If a point is above a given threshold it is a possible bip.
We consider it as a valid bip if for the bip_length 90% of the enclosure is above threshold level.
If the point is valid a debouncer to avoid echoes is then activated.

In the following example you can see the signal (light red), the power at 21kHz (dark red) and the enclosure (black).
Regular beeps are send every 1s. Beep lenght is 10ms.
Abscissa is time in seconds, ordinate is the amplitude of the signal

sound

This is a zoom on the second beep of the same recording.

sound1

Conclusion : we observe that the signal we get is not “clean” and as many echoes.
We also observe that the tweeter takes a some time to enter resonance which results in a possible 3ms shift.

This is a major concern. One possible improvement is calculate several position and apply a low pass-filter to get the position is several measures are alike.

Further development

Fo now we record a sample before analysing it.
We shall implement a “continuous” mode that enables doing all the computing part while recording the audio file.

Last lap.

Last week, last breath, last run… During the last week-end and the last day of the project, the groups managed to implement several key feature.

First of all, our display function is very complete, it contains double buffering, it does not blink at all, it is kind of “plug and play” with a USB connection with a PC. We have also implemented a gif reader script on the pc side.

On a second hand, we worked a lot on the interaction with the cube. Coralie and I build a grid that contains small PCB (now we have 12 PCB, of 3 different kinds). So we have one grid a presence detection of each side of the cube. Unfortunately, the I2C connection does not works now… Few days left. The other half of the group worked on the kinect. They detect if a hand is near or far of the cube, and so they can control the luminosity of the cube. Now they want to detect if your hand is at the right the left the top or the bottom, and so we control a snake (that will be a great game!!!).

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.