Categories

WAMI: Where AM I

Description

The aim of the project is to implement an indoor localisation system using ultrasounds.

The localisation system shall be able to locate a given cell phone in a 3D space of approximatively 50m * 50m * 20m (lets say the Amphitheatre Thevenin for instance).

The system  is composed of :

  • emitters who send ultrasound beeps
  • a receiver who computes his position thanks to the time difference of arrival of the beeps

Our receiver will be a cell phone implementing an android application. This choice has been made so that the project is easily portable and does not require any additionnal equipment.

 

Emission

We design our own PCB to be rather generic.

They have :

  • LEDs and buttons for control
  • a H-bridge to connect the tweeter and have an increase power of emission (x4 as compared to a normal connection)
  • a XBEE module for radio communication
  • USB and a micromatch concerning the interfaces

We also have a codec connected in case we need to record the ambient noise / beeps coming from the other emitters.

Communication protocol

In order for the system to work we need to synchronised our emitters.

This is the purpose of the presence of xbee modules.

One of the devices we made will be considered as the master and send synchronisation information to the other emitters. By considering that the time of flight of the radio waves to the different emitters is much smaller than the precision we need for beeping (which is true in reality), all the “slave twitters” are therefore synchronized.

 

Reception

The device we use for reception is a regular cell phone able to run an android application.
Regular micros on modern cell phone sample the sound at 44kHz which is enough to regognize ultrasounds (from 20kHz to 22kHz).

Detecting a pulse

We are curently working on several methods to detect the time of arrival of a pulse. To do that we need to get the energy associated to the 20kHz frequency.
We thought of implementing :

  • FFT
  • the Fourier coefficient associated to 20kHz frequency
  • a goertzel filter

We shall meet a signal teacher tomorow whose advice will be precious.

 

Finding position

To compute its position from the measures of the time difference of arrival, the receiver needs to associate each beep to a tweeter and to know the position of all of them.
The main incertainties in the algorithm is that we don’t know the speed of the ultrasounds (it varies a lot with respect to temerature, humidity, altitude). For instance a 5°C shift results in 3m/s diffenrence in the ultrasound speed.
We are currently using a least square algorithm with some adjustements to be able to find the proper position.

RoseRolls

What is RoseRolls?

RoseRolls is a spherical robot made by hacking a Sphero (from Orbotix). It’s aim is to create a both hardware and software add on for Sphero.

How it works?

Sphero is sold to be unbreakable. They provide a sdk to allow everyone to create applications to remote control it. But we want to change it’s hardware. We basically open the ball, and plug an additional pcb on top of his. We insert our mpu between sphero’s bluetooth chip and it’s stm32. This way we can intercept and forward any messages sent to him.  We use his api to send commands in order to control his base: make it roll and blink basically. This way we don’t have to redo ourselves the very complex navigation, balance and control system it uses.

What we add

Based on our observation that sphero isn’t really autonomous we will make roserolls more autonomous. Sphero can already know it’s position, detect collisions, make some visual feedback with it’s leds. But we will add more:

  • Transparent shell
  • Infrared communication/angle detection
  • buzzer
  • more leds: 3 RGB and 5 blue.
  • 3 axis magnetometer: sphero already has one but its too mixed up by the motors magnetic field. We add it just for test purposes

Our Architecture

Here is everything we will put on our board:

RoseRolls pcb TopRoseRolls Bottom pcb

IRDA

Irda is used to know the position of 2 spheros one relative to another: if A is emmitting and B is receiving on it’s left irda transceiver, we know that A is at the left of B. Furthermore, in the frond we put 2 IRDAs crossed in order to create a “mustache” like a mouse.

IR photodiode

Because IRDA transceivers don’t give the power received, we can’t use them to measure the reflected beam.
That’s why we added a photodiode coupled with some RC low pass filter in order to measure the distance of nearby objects. We don’t know if it will really work since the environment will be flooded with infrared.

Buzzer and leds

In order to enhance the emotion feedback we added some leds and a buzzer and we will give RoseRolls some kind of personality.

User stories

  • Use a RoseRolls as a Sphero: it must be compatible with already existing smarpthone applications
  • RoseRolls can take control remotely of a sphero and make it dance
  • Avoid obstacles while being remote controled
  • Play some music: because 8 bit music makes us nostalgic
  • Make a choreography using several RoseRolls
  • Automatically arrange some RoseRolls in a certain pattern: line, grid etc.
  • Have a RoseRolls following another one and form a snake
  • Solve a carboard maze by exploring it and find the shortest path from center to exit
  • Use mbleds as a invisible beacon or barrier.

What is WaDeD?

What is WaDeD?

WaDeD stands for Walking Dead Drops. A dead drops is an espionage method, which point is to leave a message in a secret location, known by only the receiver, and he will come and take the message at the specific place. WaDeD takes this concept and improves it, with the advantages of the wireless technologies. WaDeD is composed of two kinds of modules, some fixed and some mobiles carried by users. The users use the mobiles one connected to their Android, and thanks to an app, they will be able to send a message to someone and leave it in a fixed module. But wireless technologies offers more, and even spies would rather not move to get a message. So we are going to use every WaDeD modules as a drop box and will stock every message send. The network don’t have a fixed structure, we have no idea were the receiver is located or if he is even reachable, so every message will flood the network increasing the chance to deliver the message.

WaDeD is a mesh-network, allowing friends to communicate between them, without using 3G network, or any usual paying network.

In the following description of the project the fixed modules will be called Stones and the mobiles one Zombies.

This article will be changed depending of what we decide about the project.

Our Specifications

  • We need the Stones to be independent, so we have to reach incredible low power consumption level, in order that the Stones can last as long as we can with no maintenance.
  • The Zombies need to have an autonomy of an expedition (1 or 2 days).
  • We want a Radio Frequency protocol that have the best range with the lowest consumption. We want that the precise locations of the stones stay hidden. So we want the basics users to received the message by being in the biggest possible sectors.

The Messages

We choose to limit the message size up to 140 characters, just like a Tweet or a SMS (remember the time where you haven’t unlimited SMS?). We know it’s not a lot, but millions of Tweeter users can say it’s already enough. But we are going to implements other type of messages to specific situations (see Use cases), in order to say more with less data.

Use Cases

Here a description of several use cases we want to implement in WaDeD

  • Communicate with a friend

The user will just want to sent a text message to a friend, to just chat or say how cool where he stands is. Only the other user should be able to see the message.

  • Set up a meeting

The user wants to invite one or more users to a meeting. She will communicate the place and time at which the meeting takes place. She may want to know whether her message got through or not. Only the selected receivers will see the messages.

  • Acknowledge a meeting

The response to an invitation. The user may accept or decline a meeting.

  • Communicate with everyone

The user wants to announce a gather up of some kind, or signal something. Every other user should be able to see the message.

  • When two users meet

They want to exchange their addresses and public keys to be able to exchange messages in the future.

  • Trace another user

The user may want to know when is the last time a certain other user was there. She should be able to ask the stone (see “broadcast location”).

  • Battery status (administration privileges)

Get the battery status of the stones. Each stone may for instance communicate its battery status each time it encounters an user. When propagating, newer data about the stone should replace older data. Recognizing a stone should be easy for the administrator, so he should be able to list them by name.

  • Firmware update (administration privileges)

An administrator may want to broadcast a new firmware to the stones. Stones should pass the update through the network automatically in packets. When a stone has a complete update, it should reboot automatically on the new firmware.
As this induces vulnerability, the security of this procedure should be dealt with extra care.

  • Broadcast to surrounding (for stones only)

The stone sends a message to every user around, a warning for instance.
This message is not the be relayed.

  • Send battery status (for stones only)

See the similar part for the administration uses

  • Broadcast location (for stones only)

Send a message to everyone each time a user come saying that this user was
here.

Architecture

   For more information about our choice I invite you to check up the component survey we made.

Microprocessor Unit

   We are going to use a STM32L151CB, the low power version of the STM32. It’s among the lowest level of consumption and we are already familiar with the STM32 family.

Flash Memory for Messages

   We choose to use a FRAM (FM25V20 by Ramtron). Communicating on SPI Bus, this type of RAM offers speed and non volatility of the data as a Flash. It offers also good consumption characteristics.

Radio Frequency Solutions

DASH7 (433MHz)

   The 433MHz offers range and consumption level characteristics very interesting. The tests was quite satisfying but not as much as JP Norair or the Wikipedia page of the DASH7 announced. Anyway this looks like the best solution, the test was based on WizziMotes by WizziLab, we hope to increase the range and consumption level, by using the SX1231 by Semtech.

   The SX1231 is a transceiver sub-1GHz able to transmit up to +17dBm, we are not going to use it at +17dBm because of technical conditions for the PCB that are too strict. But we can at least use it at +13dBm.  It also show very interesting consumption level. (Recall, you can check out our survey here). We have succeeded to implement a radio layer based on Dash7 protocol, and the CSMA in order to reduce the interfered messages.

Here is the Schematic of the architecture, and what our PCB looks like.

Architecture WaDeD _ Solution 1PCB SX1232 1

BIE515c1aa3c6ef0_04SAMSUNG

The main objective on this architecture are to make the radio layer, that works for the WaDeD software.

Wake-up Circuits

   You should have notice it  on the schematics. We offer a micromatch plug where we will be able to connect wake-up circuits. The STM32L has 2 wake-up pin, that can wake-up it from sleep state. The micromatch has 6 pins, two for each wake-up pin, one for the ground, one for a constant power supply, and two connected to GPIOs of the STM32L, to supply power only when the we want (or other . We give to us all the tools to do the best wake-up circuits  for where the stone will be.

We have already made tests for a Light wake-up circuits, and a Audio one.

The WaDeD Protocol

First of all, there no guaranty that a message will be delivered.

Wake-up Policy

   The stones wake-up when the wake-up circuits indicates to wake-up or periodically (time to determinate). The Zombies have less consumption problems so they will wake-up periodically.

Stateless communication:

    The main idea of this communication is that each WaDeD when receiving a message has no idea which messages were sent before. Each WaDeD will only send one message spontaneously, a message composed by the sons of the top hash node. All other messages will be answers for a message received.

The Hash tree

5 levels:

    Level 0:     Top hash. We’re going to a solution where there is two top hash

    Level 1 to 3:     Node with 8 sons

    Level 4:    Messages lists

   The top hash is virtual, in the messages that we sent, to sync, we send directly the two sons of the top hash, instead of the top hash. The parse of the two hashes has the same purpose as the top hash.

   Nodes are identified by a number 0 to 146 (8 bits)

   Messages are identified 0 to 1023 (10 LSB bites of the 64 that compose its hash

   As said, all WaDeD will have trees with the same structure, the only thing that can change in each tree are the values given to each node (which represents different messages that needs to be transmitted). Ideally, every node will also have the same value, which means they have the same messages, so no message exchange is needed.

 

Conflict policy

    There may have conflict when we add a message in hash tree, two different WaDeD may have set a message at the same place in the hash tree, and when we try to merge them, a conflict appears.

    The location in the hash tree is set by the 10 bits LSB of the hash that is associated to the message. It could appears that several messages have these 10 same bits. So they have the same position in the  hash tree.

   The solution is to put them at the same position, and using a chained list ordering the messages. there should be few collisions so the comparison of the lists, quick.

 

How the communication works:

   Each WaDeD will only send one message by themselves, which is a message containing the Top hash. Actually it will contains the two sons of the top hash, sending the two sons or the  top hash is the same, except that the top hash only doesn’t indicates which branch has the differences. All other messages will be created in response to a received one.

   Once a WaDeD receives a message, it will interpret it, and send a proper answer if needed. Once the answer is send, the WaDeD forgets which was the question, and also forgets that he has answered something.

 

First part: Synchronising the trees

   If we receive a message that represents a node from our tree, but has a different value than ours, we’ll check which of our sons have the different value, and will send a message that will be composed of it’s sons. When we receive a message that represents a node from the tree, our answer will never be an upper node,

   If the different son is a leaf, we analyse the hashes, two situations can be concluded :

  1- We have leafs that the other doesn’t or we both have the leaf, but not the same hash. We start the synchronisation of the associated chained list.

   2- The other WaDeD have leafs that we don’t have, so we send our sons from the same node, so when the other WaDeD receives the message, it will fall in his first case.

    If we happen to fall in both states in the same time, the first one is has the priority, which means we’ll first synchronise the leaf that we have and only then we send our sons. It’s in order to avoid the situation where two WaDeD keep sending their sons to each other and no message is send to change their state, leaving them stuck in a loop.

 

    Other important point: When we receive a message that represents a node from the tree, our answer will never be an upper node, if that happened we could enter in a loop state since the answer could trigger the same message that generated it. The only case that we don’t move down in the tree is the case 2 explained above (which don’t generate an infinite loop).

 

Second part: synchronisation of a chained list

   A chained list is identified by a hash, made from the parse of all the hash of the messages containing in the list.

   In order to sync the list, if the list is composed by only one element, the WaDeD that analysed that the message has to be sent, send directly the message, and let the others analysed, conclude if there is something to do, and add it in there hash trees.

   Else, we send the hashes of the messages contained in the list.

   Same as above, if the other realise that he is the one that need to receive message, he will send the hashes of his list, to the other.

   The send of a message analysed as “to be sent” has the priority above all messages.

 

A small sequence of messages:

   We have two WaDeDs, ‘A’ and ‘B’. ‘A’ has no messages and ‘B’ has only 1 message.

   ‘A’ or ‘B’ will send the only message send spontaneously, their top node and it’s two sons.
We’ll suppose ‘A’ was the first one to talk. ‘A’ Sends a message with it’s top node and it’s 2 sons. B will receive it, and will realise that his top node hash is different from the one he received (he has no idea who sended him that top hash)

 

Type of messages :

 – Top Hash  (level 0)

        MAC | 0 | Top Hash (optional) | Son hash 1 | Son hash 2

– Nodes for level 1 to 3

MAC | father’s number | father hash (optional) | son hash 1 | son hash 2 | son hash 3 | son hash 4 | son hash 5 | son hash 6 | son hash 7 | son hash 8

 

– Leaf (level 4)

    MAC | leaf number | leaf hash (optional) | hash message 1 | hash message 2 | ..

– Message

    MAC | Hash | msg type | msg

Erasing policy

We though about using a tombstone policy. The point is once the message is delivered, the receiver send a “Tombstone” that acknowledge that the message is received and that we don’t need to sync this message anymore.  It implies to only sync the ID and replace the pointer in the leaf by the NULL pointer (or a specific value that indicates that this is a tombstone).
In this case we shorten length of the radio synchronisation.

To free up memory  of the tombstones or undelivered messages. Every message has a expiration date and the program will often check for expired message, and erase them from his memory.

For now we will only implements the expiration date, without tombstone.

The Android Application

The Android application is the interface between the stone and the user. It will communicate the user unique ID to the Zombie his connected to (the equivalent of a telephone number) and the Zombie  will deliver the messages addressed to this ID to the Android application.
The user will only see a typical message application: he will receive his messages and send some and will have a contact list.
The contact list will contain the name, ID, and public key of a friend.
Thanks to the status messages the application could display a map of last seen people.

The WaDeD group

What’s a hash tree?

In this post I am going to talk about hash functions, hash tables, Merkle Trees and data structure choices for WaDeD. Feel free to skip any section.

What’s a hash table?

A hash table is a data structure that provides an associative array: it stores values in buckets, each bucket being uniquely mapped to an index, or key of fixed size. It does so by using a hash function (more on that in a minute) to compute the key from the original data. Hash tables are usually very efficient in terms of access times, and are one of the most common data structures.

Example of a simple hash table
We usually want to be able to insert values into the table, with at most one value linked to a key: the table must not be ambiguous. Since we use an algorithm to compute the key from the original value and that there usually are more possible values than possible keys, it may happen that the algorithm produces the same result for two different values: it will try to map two different values to the same key. This is called a collision, and any self-respecting hash table must take these into account and define a policy of dealing with hash collisions. These can be not storing the new value, creating a linked chain from the original bucket, storing the value in a neighbouring bucket, etc., depending on the way the hash table is effectively implemented and what behaviour we expect from it.

Illustration of a hash conflict

What’s a hash function?

Hash tables use hash functions to compute the keys it will associate to its values. A hash function is any algorithm that takes input from a data set, and maps it to a smaller data set of which all elements have the same size. The operator “Modulo n” for a given integer n, or truncation to the n last bits of data (which is really the modulo 2n+1 operation), or the constant function equal to four are simple examples of hash functions.

Cryptographic hash functions have additional properties. The goal is to provide security about the original value. We want it to be highly discontinuous: small changes of an entry should greatly change the output value. We call this property the “avalanche effect”.

Illustration of the avalanche effect in the SHA-1 hash function

In order to be secure, a cryptographic hash function should also be unpredictable (one should not be able to design an entry that will have a given hash), irreversible (one should not be able to retrieve the original value from its hash) and, in practise, should be collision-free. This is, obviously, a theoretical impossibility; however all outdated cryptographic hash functions have been depreciated because ways of designing collisions in practise have been found. It has been shown theoretically that we could design collisions in the used cryptographic hash function, the SHA-1 algorithm, so its days could be over soon whenever somebody figures out how to go from theory to practise.

Because of their good properties, cryptographic hash functions have a lot of applications. They are commonly used to encrypt passwords: storing a password is unsafe and dangerous, but since it cannot be retrieved from its hash, it can be safely stored on a distant server. When trying to connect to the service, the input password is hashed and compared to the stored hash, instead of direct password comparison. Because in practise cryptographic hash functions can be considered as injectives, we can use their hash to check for integrity of a file. This is why Linux distributions always provide hashes of the installation files: after the download, the user can run a hash algorithm on the file. Any corruption, accidental or intentional, will result in a different hash and the file can be discarded. Finally, we can use cryptographic hashes to “fingerprint” a sequence: it is a simple, low cost way of giving a unique identifier to something. Git uses the SHA-1 algorithm to identify commits. If we have a big hash table, using a cryptographic hash function is a good way to minimize collisions.

What’s a hash tree?

When exchanging files over a network, integrity checks are crucial: we want to protect our computer from installing bad software, and want to be able to ask for data again if it was corrupted during transmission. Therefore there is a need to do quick, efficient integrity checks. We already saw that cryptographic hash functions are good tools to do so, but the way we use them can make a big difference.

A hash tree is a structure that can be used to rapidly check differences between parts of a file. It is a tree whose leaf nodes are data, packets we want to store independently, and whose internal nodes are hashes of the concatenation of their son nodes.

Principle of a hash tree

Say I have two copies of the same file, stored as hash trees (the files are split into small chunks which are stored into the leafs) and I want to check whether they are really copies. If the top hash match, then I know that the whole tree does, and therefore the leafs do: the files are the same. If they differ, not only do I know that the files differ, but by going down the tree I can identify exactly which parts of the files are identical and which ones are not.

This is exactly how bittorrent works: when downloading a file with bittorrent, the user first gets the top hash of the file through a secure source. Then she can get the tree through any user, since having a valid top hash ensures the whole tree is valid. Then she can freely communicate with other users on the network who pretend to have parts of the file. As she downloads the packets, she compares the tree that builds up with the copy of the tree she first got, knowing when to discard false or damaged packets. When she has all the packets, the hash tree of her file matches the one she got in the first place, and she knows she successfully downloaded the file.

Comes in WaDeD

So what do we do with all this?

In WaDeD, modules have to store packets to be transmitted on the network. We want two modules that meet to synchronize all their messages, so that each one can retransmit packets that were held by the other. Therefore we want to be able to quickly know what the symmetrical difference between the two lists of messages is. A hash tree seems like a good idea for this: if two modules already have a lot of packets in common, we can expect them to have huge subtrees in common and minimize the number of comparisons.

This is harder than it first appears. In order for the hash trees to work, two users who have packets in common have to store them at the same place in the tree: otherwise the similarities will not appear when comparing hashes. In a worst case scenario, two modules could have all their messages in common and have different top hash, provided the order of only one stored message differs. This is because the usual application case of hash trees is checking integrity of fixed files, not to compute symmetrical differences of two sets whose content and size. If we want to use hash trees, we need two users who carry the same files to store them in the same place of the tree, independently of any other factor.

An acceptable solution to this problem is to consider the leaf layer of the tree as a hash table: the leafs are buckets in which we place packets according to their hash value. This gives us certainty that two almost similar sets of packets will produce almost similar trees, at some costs:

  • The number of packets that we can store is limited by the number of buckets (the tree cannot adapt its size). This is not really an added cost, since we already have strong memory constraints (limiting the number of stored packets) and that we want to avoid dynamic memory allocation (forcing us to use buckets anyway).
  • Hash tables, especially fixed size ones, always induce a risk of collision. It is inversely proportional to the size of the table.

Is it worth it?

Two modules that meet will always have to compare their packets lists, so that is a common operation. We intend to store at most around a thousand packets, so that is up to a thousand comparisons at every meeting if they want to compare their lists directly. That means a thousand hashes over the radio. Radio communication is slow and the highest energy cost of the whole application, so that is something we absolutely want to avoid.

An amelioration is to have a “top hash” representing the state of a list of messages. This cuts the cost of the 1k radio communications when the lists are the same, but if they differ, we still have to exchange the whole list of hashes, which remains costly.

A hash tree allows us to minimize the amount of data we will exchange on the radio, at the cost of a few more CPU cycles and a 1/1000 collisions chance, which will cost us a few more CPU cycles to deal with, so this seems more than reasonable. A hash tree it will be, then.

In another post I will explain which choices we have to make concerning the effective implementation of the hash tree in memory.

HARP

What is HARP?

The aim of our project is to design an embedded system able to display numerical 3D animations at a speed up to 16 frames per second.

How it works ?

The basic principle is the same than  ROSE 2012’s project, RoseAce, which used retinal persistence.

By controlling a RGB LED matrix fixed on a rotating PCB and showing a different image for numerous positions around the axis,  we will get an hologram-like look.

Considering the complexity of 3D processing, the conversion of 3D animations  into processable data for our embedded system will be done on a computer. The conversions will be done using python scripts under Blender.

The HARP system

The HARP system

Architecture

HARP's Architecture

HARP’s Architecture

Our system will be composed of a GumStix running Linux. The system will be booted from the SD Card. Animations data and instructions will be transferred via Wifi. Data will be then stocked in RAM.

Concerning the display:

At each position detected by the Incremental captor, we display the corresponding data from the RAM. The sending speed depends of the rotating speed read by the captor.

Dual-supply bus transceivers  are used between LED drivers and the GumStix because its pins need to be connected at 1.8V.

The 8 pins connected from the GumStix to the LED matrix allow us to choose which line is to be displayed. Transistors are here to increase the luminosity.

Routed PCB

Routed PCB

ROLED’s Cube

Our project is to make an interactive cube of LED.

We have a cube of 12x12x12 LED (45cm x 45cm), commanded through a stm32 which is in charge of the display. We add in the cube some sensors, we will detect the presence of the hands nearby wires added in the cube and detect the rotation of the cube thanks to a gyroscope. The stm32 is also in charge of collecting information on the sensors. We can communicate with this stm32 thanks to USB.

We have a beagleboard at the base of the cube, linked with the stm32. Here we can create animations or games using the two types of sensors and display it on the cube. What’s more we will add a Kinect connected on the beagleboard, we can reproduce an object in the cube, we can play games such as Rubik’s cube in the cube of LED through the Kinect.

We have chosen USB because if we want we can connect the stm32 directly to a computer or a mobile phone, and create a program on it to play with the cube.

Let’s concentrate a bit on our LED. We will have 1728 RGB LED, so 6912 wires to connect. It seems quite a lot to connect on a PCB, so we will use multiplexing. Our LED are with a common anode, on each floor we link all anodes, and on each columns we link all “red cathode” together, all “blue cathode” together and all “green cathode” together. So we will light one by one each 12 floors, quickly enough to see the whole image.

Talking about our PCB, we don’t want 444 wires to connect on the PCB so we want a huge PCB as big as the base of our cube and plant our cube in it. On it we only will have the drivers and the links between the base of each column and the driver, so we will make this PCB in the school with only one side (in reality we will make six more little PCB side by side). And for the rest of the electronic we will have a little, normal, PCB.

Here is our architecture:

architecture