Algorithm

The project is about modules communicating via IrDA.
We used distributed systems algorithms for our algorithm.

We needed someone to give the common direction and to synchronize others. So, we decided to implement a leader election.

First of all, all the messages use a particular packet structure of the IrDA. 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.

* PING ()
* PONG (membersInMyNetwork, myInterface)
* ACK (from, idPacket)
* START_ELECTION
* CANDIDATE (leaderID, membersInNetwork)
* REJECTED (leaderID, membersInNetwork)
* ELECTED (leaderID, membersInNetwork)
* YOUR_POSITION (directionID, leaderID, myOrientation, yourI, yourJ, myInterface)
* NETWORK (blockID, hisI, hisJ, hisLeaderID)
* MISSING (blockID)
* TURN (myRotation)
* TIME(time, synchroID)
* CMD_DATA

1. Generalities

For the algorithm, we 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 direction (which « interface » represents the north)
* the number of members 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. If there is no ACK, the message is resent.

When starting all of this, the block starts the timer 5 of the STM32 for the synchronization. (see section 4)

You can read the schema …

… or read the explanations. 🙂

2.The identification

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 MISSING 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 directionID,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 directionID is increased by the leader every time he sends a POSITION message; it’s only used to avoid redundancy.

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 receives 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 MISSING message. He builds a graph of the network and cut the branch with the missing block. If the leader was part of that branch, the block decides that the smallest ID is the new leader.

This message is broadcast to all the network and everyone cuts the branch and check if the leader is still part of his network