DOCUMENTATION
The Spohn
algorithm is organized in rounds that are explained below:
switch(roundcounter
% 10){
case 0:
//Broadcast the announcement. I will send an announcement to all of my one
hop neighbours. [Go to 1]
break;
case 1:
//Discover my neighbours. In round 1, we will
know who are one-hop neighbours. In this round we will discover who are my
r-hop neighbours. [Go to 2]
break;
case 2:
//Phase one. [Go
to 3]
break;
case 3:
//Send a LA message (Phase 2). Dominated
nodes will send a LA message only to their one-hop nodes. [Go to 4]
break;
case 4:
//Send NA message (Phase 2). If any nodes becomes dominating it has to send a NA message to its neighbours. [Go to 5]
break;
case 5:
//Send notification message (Phase 2). If a node has to sent any
notifications it is time to do it. [Go
to 6]
break;
case 6:
//Send NA message (Phase 2). Because of the
notification received a node can become dominating,
so that node has to send a NA message announcing that it is a dominating node. [Go to 7]
break;
case 7:
//Send join message (Phase 2). Any dominated
node sends a join message to its validated nodes. [Go to 8]
break;
case 8:
//Some nodes became gateways (Phase
2). If a node has to rout a packet, it becomes gateway. [Go to 9]
break;
case 9:
//End of algorithm (Phase 2). [Go to 10]
break;
default:
break;
}
1)
Broadcast the announcement
We will send five times a broadcast
announcement. We will repeat several times this announcement because of the
collisions sometimes the packet doesn’t arrive to all neighbours.
Once we
received an announcement packet, we will store that node as a next-hop in the oneHopNeighborListInt vector.
The
following draw illustrates the above. We have a random network and we want to
know for each sensor which are they one-hop neighbours.
|
|
One-hop neighbours
|
|
2)
Neighbour
discover process
The neighbour discover process takes r-1 rounds.
A node always sends the update list of neighbours to them (allocated in oneHopNeighborListInt vector).
When we received the neighbour list from
different neighbours at the same round, I will update the neighbourMatrix. This matrix has two aims. First to know all of my
r-hop neighbours and the second to know which is the next hop to reach any
neighbour. Now we have updated my neighbours list and we will send that list to
my one-hop sensors. If we repeat that process r-1 times all the information
about the neighbours spread to my r-hop neighbours (like a flooding).
An example of neighbourMatrix and how to read the data would be:
|
|
0 |
1 |
2 |
3 |
4 |
5 |
... |
MAX_NEIGHBOUR |
|
0 |
|
|
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
4 |
1 |
|
|
|
|
|
|
|
|
5 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
... |
|
|
|
|
|
|
|
|
|
MAX_ NEIGHBOUR |
|
|
|
|
|
|
|
|
The previous means that all of my r-hop
neighbours are nodes 0,1,3,4,5. Remember that if we want to know only my one
hop neighbours they are allocated in oneHopNeighbourListInt.
Furthermore we can deduce from the table that to reach node 0 the next-hop is
node 3. Besides to send a packet to node 4 I will do it t through node 0.
The next images show the 3-hop neighbours for
the node 0.
|
|
3-Hop Neighbours for node 0 |
|
3)
Phase
One
This phase
works like in the paper. The main important thing to understand in the code is
to keep in mind the following scheme. 
4)
Send
a LA messages
Dominating
nodes send a LA message to their one-hop neighbours. To know which my one-hop
motes are we will check the oneHopNeighborListInt
vector.
5)
Send
NA messages
It takes r
rounds. Dominating nodes will send a
NA message their one-hop neighbour. These nodes will validate the dominating node in its validatedNA vector and then it will
forward that NA message to its neighbours. That is the reason that this phase
takes r rounds, because the NA message has to be forwarded r times to reach
r-hop motes.
6)
Send
notification message
It takes r
rounds. Some nodes will send a notification messages (described in the paper).
It takes r rounds for the same reason as the previous point and that is due to
it is mandatory to forward the packet r times to reach r-hop nodes.
7)
Send
NA messages
The same as
point 5.
8)
Send
join messages
It takes r rounds.
All nodes have to forward all join packet that it receives. For each packet
that it receives the target node would be different. Thus for each join message
that we receive we will store the and how many join message I have received for
that node. The next graphic show us how it works:
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
... |
MAX_NEIGBOURS |
|
Target Node |
3 |
2 |
1 |
|
|
|
|
|
|
|
Num. Joins |
2 |
3 |
1 |
|
|
|
|
|
|
For the node
3 we have 2 join messages, for node 2 we have 3 messages and for node 1 only
one 2 message. After that I will forward this information to my neighbours. I
will send a message to node 3 with the number of joins. Another to node 2 and
so on. But we don’t send the message directly to node 3,2 and 1 because maybe
we can’t reach them. Thus we will check neighbourMatrix
and we will send the message to the next-hop to node 3,2 and 1.