Today, we continued on our recent work : I worked on the algorithm and on the rotation of a block. The rotation works quite well now. The algorithm for this rotation is simple : When a communication between two blocks is stopped (due to the left of someone), the two blocks save their « interfaces » (aliases of the UARTs ). When there is a PING from a block, we check the saved interfaces in order to see if the block was a « friend » of this block. If it’s the case, we just calculate the rotation of the block.
The main problem is that a block can communicate with 4 others blocks at the same time. So, sometimes, we have to wait a little bit when we want to compare the interfaces.
Cédric noticed in the afternoon a bug in the IrDA functions and we fixed this. Now, the IrDA has more reliable and there are few problems in the network.
I still have problems when two networks meet with more than one block each involved in the « deal » but things are going better each day.
Benjamin worked on the launcher task. He thought of a remote block who can control the animation/game that will be played soon after.
Cédric continued the firmware transmission and the protocol is actually functional at good speed. But he is now facing problems with flash writing.
Here is a little video of the synchronization (running on the GLiPs but the MBLed are arriving soon):
Every block knows its i,j and minI, minJ, maxI, maxJ in the network. The block in the north-west shows a M; north-east a B; south-west LE: south-east D. If he is alone, he shows a M too.
That’s why sometimes in the video, there are 2 M : one of the block has encountered problems and reset himself.
For the synchronization, the leader gives the time every 20 PING (approximately every second), when a block receive that, it transmits it to his neighbor and so on.
Since yesterday, Guillaume worked on algorithm reliability, improving its performance and solving some problems such as information sharing (number of blocks in network, position…). Some loop-back which were over-charging the network have been deleted. He worked with Benjamin to improve the algorithm but some problems remain unsolved… In late afternoon, the algorithm was working rather well : in a 9 blocks network, blocks detected the good number of blocks, their position, the leader ID, the positions of the others in many cases. But sometimes, one block loses his IrDA connection so he has to start again the algorithm. When dividing a network in 2 networks, the blocks graph (developped with Benjamin) gives the blocks good informations.
Benjamin worked on improving the snake game, now it has a tail and if you cut it (meaning you disconnect blocks before the tail leaves) you lose. Some apples have shown their faces on the screen, but we must handle turn detection before evolving furthermore. He also worked with Guillaume on the implementation of a blocks graph in order to react faster when a block leaves the network. In fact, if a member leaves, blocks are able to calculate that every members of the branch also left. At last he tested synchronisation implemented by Guillaume displaying an animation on MB Leds, it is pretty quick and all blocks flash at once.
I have first worked on improving some aspect of IrDA like variable waiting time before a resend and size of packets in order to improve the payload . I have continued to implement firmware transmission and have begun testing it. Transmission seems a bit slow and tomorrow I will look for a way to improve its speed.
Since Saturday I have been working on Firmware transmission through IrDA and the use of SD Card.
Transmission protocol for firmware:
The firmware is stored on flash memory, so we are transmitting from flash to flash through IrDA.
As we have to write in flash by pages, we also have to transmit our firmware by pages and as pages important in size we cannot send it at once. Thus each firmware will be sent divided by pages which are divided into packets.
At the beginning of a transaction a first packet is sent with the data needed in order to store the firmware such as number of pages, number of packets sent by pages and for security purpose the id of the sender and the interface used. The bloc send an acceptance packet either it is already on transaction or not.
Then a PAGE_BEGIN packet is sent with its position in the firmware.
During page sending all data is stored in a buffer of 32-bits words.
At the end of a page a packet END_OF_PAGE is sent confirming its position and adding its CRC calculated thanks to CRC unit on STM32 and the CRC is checked(Note that in the IrDA task we already check the integrity of each packet). If everything is okay we write the buffer in flash, if not a request is sent to resend the page.
We continue till we arrive at the end of firmware with the packet END_TRANSACTION and the global integrity is checked. In case of success we send a TRANSACTION_OK packet, if not we have to do it again from the beginning.
For SD Card we will use FatFS, a free open source FAT file system module which has an implementation on STM32 thanks to Martin THOMAS. I adapt it to our system. I delayed testing because transmitting a huge amount of data seemed more important, SD card coming in second.
It is time to make a debriefing about last week achievement.
Colour gradient and intensity
Benjamin worked on the Led driver in order to display a picture and has fixed some problems with luminosity. He balanced green, blue and red and we are now able to display a white colour on our blocks (although a blue tint remains on videos). From now on, we also have a linear gradient of intensity for each primary colour. In order to obtain this gradient, we first tried to put a linear variation of intensity in registers, but it appeared linearity didn’t worked and he had to adjusted individually each step.
Electronic visual display:
An interruption is raised with a frequency of 10kHz and each time a new line is displayed. As our Led matrix has 8 lines, we have a electronic visual display at 1,25kHz. Each time we want to display a new line we connect to the Led driver through SPI sending it thanks to a vector of 288bits matching a 8 pixel line with three colour and 12 bit of gray control. Actually we only use 4 bit for each colour.
Yesterday I implemented acknowledgement system with IrDA transmission. First I needed to divide our sending queue into 2 queues: one for quick packets which don’t need ack such as PING, PONG and synchronizing messages sent at high frequency and allowing some losses; the other one is for important packet needing a safe transmission. These packet are sent to a task which could be seen as a buffer sending a packet (every 40ms) until it receives an ACK and then picking up the next one. In order to identify a packet an ACK transmit the ID of the sender and the ID of the packet it acknowledge and when an ACK packet is received, a message containing these information is send to the task managing output packets. In order to avoid loop waiting for an ACK , we use a counter and if a packet is not acknowledged after 10 tries we consider it as a lost packet (for ping messages, if we don’t receive one PONG for 10 of our PING, we consider the neighbour as gone). Once a neighbour is gone we empty the sending queues for this UART.
This system is not optimal, being slow, but at higher speed we got a lot corruption during transmission and more packet are lost.
We decided to rethink our algorithm after the reactions of yesterday’s post. We changed the algorithm when some block is leaving the network. If someone is missing, the block which notice that says it to the network. Every other block answer by « I’m still here ». If the leader doesn’t answer (probably he’s gone), there is an other election; those who don’t answer are considered to be out of the network. In this algorithm, the blocks keep in memory their position and orientation and we don’t have to start an election every time some block quits.
A little video showing up some features as the use of LED driver, election and direction:
NOTE: Now once a direction is decided, it is kept when the connection is lost.
As Samuel noticed that there is not formal description of the algorithm, I will do this now.
First of all, all the messages use the packet structure giving by Cédric here. So, they all have an ID and we know who is the sender. I will start by showing all the messages and then I’ll explain the algorithm.
List of the differents messages
There are a large number of messages and they all have specifics arguments.
For the algorithm, I use « interfaces » which are aliases of UARTs. The UARTs are used by the IrDA while the interfaces are used for the algorithm. For example, interface 0 represents the north (and is in reality UART 2), interface 1 is the east (but in reality it’s UART 5), etc.
All the blocks know :
their own ID (given by the STM32_ID),
their leader ID,
their orientation (which « interface » represents the north)
the number of member in their network
their « nearest » neighbors (who is in front of my UART2,3,4 and 5) : the Interface table.
They have a network table (for each ID, they know the position (i,j) and who was the leader when they had the information) and an election table (for each ID, they know his state in the election) . We will try to replace theses tables by a list in the future.
Every message except PING and PONG is answered by an ACK message. The PONG message contains the PING ID so it is itself a ACK. If there is no ACK, the message is resend.
When starting all of this, the block starts the timer 5 of the STM32 for the synchronization. (see section 4)
Each block sends PING messages in the 4 directions and start a timer for each direction.
When receiving a PING message, a block sends back a PONG message as fast as he can.
When it receives a PONG message, the block knows who is his neighbor and changes his Interface table. Furthermore, the block stops the timer.
If the block is aware that there was a neighbor but there is no answer at the end of the timer, it sends a RESET_NETWORK message (see section 5).
If this interface wasn’t ready before, the block has to check if he knew the neighbor (in order to notice a turn of the other block) or not (in order to start an election.)
Explanation of this check :
When receiving a PONG message from a « new neighbor », the block checks if the « new neighbor » was a neighbor before or not. This is checked by comparing the current interface table and the saved interface table.
If the interfaces tables don’t match, there is an election.
Else, the block sends to the block TURN (myID, rotation). The rotation is the difference of index between the current interfaces and the saved interfaces.
To compare the interfaces, the block waits a little bit for PONG message from all the interfaces.
3. The election
When it’s the first PONG from a new neighbor, an election takes place.
When starting an election, the block starts a timer. If his candidature isn’t refused at the end of the timer, he is elected and he broadcasts the information.
In the election, the blocks send messages for their « network » (all the blocks with the same leader). Here, the « network » can be a network of one block (so the leader ID is his ID).
The block sends a START message to his neighbors not in his « network » (and this is broadcast). All blocks sends a CANDIDATE message with his leaderID and the numbers of members in his network.
The winner of the election is the network with the larger number of blocks in his network. If this isn’t enough to decide , the lower leader ID is declared winner.
When receiving a CANDIDATE message, the block checks if the candidate can win or not. If he can’t, the block broadcasts a REJECTED message. If he cans, the block broadcasts the CANDIDATE message.
When receiving a REJECTED message with his leader ID, the block stops the timer : he can no longer win the election.
At the end of the timer, one network is the winner. It sends the ELECTED message and everyone broadcasts it.
4. After the election
After the election,the leader is in (0,0). If he was part of a network, he sends his information to the others by sending NETWORK messages.
For every NETWORK message received, the block analyzes it : if the leaderID of the NETWORK message isn’t his leaderID, it drops the message. Else, if the message contains a good information, the block changes his network table and transmits it.
Then he sends the POSITION message : [YOUR_POSITION leaderID, myOrientation, yourI, yourJ, myInterface]. The block which receive this calculate his new orientation (with « myOrientation », « myInterface ») and change his position in his network table. Then it calculate the position of his neighbors and sends the message.
The leader sends TIME messages (which are broadcasted if they are « young » enough.. That explains the synchroID) from times to times. In his TIME message, there is his current time (according to the STM32). The block that receive this message update his new « current time » (with a function which take into account the emission time) and then sends his current time to others, etc.
5. If someone leaves
If some block leaves the network, there is no PONG message to the PING message of his former neighbor. The former neighbor notices that and broadcasts a RESET_NETWORK message.
This message is broadcast to all the network and means that every data (leaderID, network table, …) must be restarted; the interface table is saved (for the TURN mechanism). A new election starts soon after. (plus the orientation, network information, synchro…).
The turn mechanism isn’t implemented yet and the ACK mechanism has to be implemented very soon.
Then, there will be messages for the applications (games, firmware upgrade, …).
Today Guillaume has worked with 9 GLiP blocks, trying our algorithm in order to elect the leader among the network and give positions to each block. He succeed in this when the network is slowly increasing but when all the blocks come in a random way, it is still difficult to have a consistent network. There is still no acknowledge with the IrDA and when some packet is corrupted, the algorithm fails. We have to fix this soon.
Cédric has resolved his problem with UART4&5 for emitting packet. After some tests with Alexis, he found a good value for the resistance(4.7KOhms) to control emission power so that the blocks would communicate only to the neighbors. All potentiometers will be replaced by classical resistances.
Now I can drive the LED matrix using the new driver TLC5951. I can display a 8×8 pixel on the matrix but I have to fix some problems of intensity. We knew that blue is more powerful than red and green and we try to avoid this problem. For the moment, we can’t obtain a perfect white but I’m in a good way to fix this problem.
Yesterday, Alexis gave us 3 MB Led so that we could check the IrDA of the blocks. So far, Cédric achieved to communicate through UART 2 and 3 without any problem. For UART 4 and 5, he encountered problems to receive messages due to missing characters in the UART data register.
Benjamin started to check the LED driver so that we could light the MB Leds soon.
Both of them used the oscilloscope to understand signals from the component.
Meanwhile, I fixed some bugs in the algorithm and my tests were successful on the GLiP blocks. Thoses blocks can only communicate through UART 2 & 3 so my job is now to test the algorithm on fully operating GLiP blocks (with their 4 IrDA transceivers), waiting for Cédric to test on our MB Led blocks. It seems that FreeRTOS scheduler is blocked when I tried to launch 16 tasks at once. I would try to fix this without reducing the numbers of tasks, cause each one is important…
Actuellement, je m’occupe de fusionner mon code d’algorithmie avec le code de Cédric concernant l’IrDA. Nous avions quelques différences sur des fonctions d’envoi et de réception de données. J’ai du réécrire certaines fonctions pour que cela marche. Désormais, nous testons les résultats en utilisant la sonde JTAG qui nous pose certains problèmes (hier, on a passé pas mal de temps à ressouder des fils qui s’étaient déssoudés).
L’IrDA est désormais fonctionnel avec des envois à haute vitesse. Cédric a utilisé un ordonnanceur pour gérer cela. En attendant, j’ai réfléchi à une façon de détecter qu’un bloc a tourné. Les tests avec FreeRTOS et zmq sont concluants et il faut juste l’appliquer au code avec IrDA.
Hier, Alexis avec l’aide de Benjamin a soudé un bon nombre des MBLeds. Nous espérons les avoir bientôt pour que Benjamin puisse tester son code sur le driver LED. Benjamin a aussi réfléchi à deux jeux que nous voudrions implanter : un morpion et un snake. Il attend que la fusion soit finie pour tester cela.
Suite à la demande d’Alexis et Samuel, nous ajoutons des garants pour nos prochaines étapes:
- Contrôle de la matrice de LED. => 15 avril (Benjamin)
- Élection de leader sur un ensemble de bloc. => 15 avril (Guillaume)
- Affichage d’une image sur un ensemble de bloc. => 18 avril (Benjamin)
- Lecture de données sur la SD Card. => 18 avril (Cédric)
- Détection de la rotation d’un bloc (gauche, droite, demi-tour) => 20 avril (Guillaume)
- Mise à jour du firmware via IrDA fonctionnelle => 24 avril (Cédric)
- Possibilité de jouer au morpion sur 3×3 blocs => 26 avril (Benjamin)
Tout les paquets envoyés sont précédés de l’enchainement de caractères « MBL » qui marque le début d’un paquet. Par la suite, sont envoyés dans l’ordre:
FROM : 8 bits id de l’émetteur
Idpacket: 8 bits id du paquet nécessaire pour les acquittements.
Priority: 4 bits valeur entre 0 et 7
To: 4 bits permet de savoir à qui est adressé le message (voisin, broadcast, leader)
TTL: 8 bits duré de vie du message sur le réseau
Mode: 8 bits Contient la commande (PING, PONG, DATA_IMG….) le premier bit indique la présence de Data.
Size_of_data: 8 bit Taille de la Data majorée par MAX_DATA_SIZE
Data: Tableau de d’octet pouvant contenir ce que l’on souhaite.
Checksum : 16 bit.
Procédure de test:
Après avoir étudier l’implémentation de l’IrLAP pour Linux, il est devenu évident qu’il n’était pas nécessaire de l’implémenter. A la place je suis en train de mettre en place un processus de dialogue similaire à celui mis en place pendant le communication challenge.
Dans un premier temps les blocs émettent des PING jusqu’à recevoir un PONG. Dès lors ils associent l’identifiant du bloc à l’un des ports et commence le nécessaire pour l’algorithmie.
Pour le moment je suis en train de débugger cette phase en mettant deux blocs face à face. Dans un premier temps j’utilise un bloc en émission sur lequel je vérifie les paquets envoyés puis je place un second bloc en face et observe pas à pas la procédure de réception du paquet. Hier j’ai pu envoyer un paquet contenant de la data et ayant un TTL de n. Le bloc qui reçoit ce paquet le réémet avec un TTL de n-1. Ainsi on pouvait voir les deux blocs s’échanger ce paquet jusqu’à atteindre un TTL de 0.
Je m’attache maintenant à la réception de commandes, c’est à dire des paquets sans data tel qu’un PING ou un PONG. Je rencontre alors des problèmes, notamment avec le checksum et la réémission de ces paquets.