# FTUC: A Flooding Tree Uneven Clustering Protocol for a Wireless Sensor Network
## 5 FTUC Algorithm
### Flooding Tree Subnetwork  
In this phase, the objective is to find the global distances in the network, without flooding all the WSN. We then rely on the creation of a tree along which information is propagated. This leads to energy savings, safe operations, and supports large area networks. Even if this approach is time-consuming, it has to be noticed that it is performed once for static networks. The details of the algorithm are shown in the Algorithm 1 pseudo-code. At each step of the algorithm, a time-out mechanism permits one to not stay blocked waiting for a message, not shown for the sake of clarity.  
In the network, the base station is the root node. The nodes at the end of the network are called leaf nodes. The other nodes are called branched nodes. At the beginning, all the nodes are initialized as leaf nodes and then set the variable 'leaf = true' (line 8), except the base station, which is identified as the root note (i.e., id = id root), Algorithm 1.  
```
Input:id root Output:leaf
1:id = getId()
2:if (id == id root) then
3: leaf = false
4: once = true
5: message = (T1, id)
6: send(message, *)
7:else
8: leaf = true
9: once = false
10: end if
11: while (true) do
12: (type, rid) = read()
```  
**Algorithm 1** Building the tree sub-network  
At the beginning of the process, the root node broadcasts 'T1 information' to all nodes within its radio range (line 5). When the neighboring node first receives the message, it is set as 'once = true' to indicate that it has received the message. This node then sends back 'T2 information' to the source of the received 'T1 information' to acknowledge the reception (line 13-18). This process enables one to create a path between the nodes throughout the network. If a node receives the 'T2 message', then it is not a leaf node, and is set as the variable 'leaf = false', indicating that it is a branched node. Parallel to this acknowledgment, the node broadcasts the 'T1 information' to its neighborhood until reaching the end of the network. If a node receives the 'T1 message' twice, it simply discards the message. As we only monitor the first received T1 message, the tree branches are created using the fastest paths. When all the nodes have received the 'T1 information', meaning that the tree network has been built, all the nodes that have not received the 'T2 message' are leaves. In this way, the tree network is created with a unique path from all nodes to the BS.  
The process of tree sub-network creation is illustrated in Figure 3. Figure 3a shows the network initialization process and the propagation of T1 messages is shown in Figure 3b. Figure 3c shows the network at the end of the broadcasting phase, while the finalized tree is shown in Figure 3d.  
Finding the distances values of each branch of the tree sub-network is then obvious. The leaf nodes send the 'distance information' to their previous nearest branched node (the one from which they received the T1 message). This node compares all the distance values it receives and finds the smallest and the greatest ones. It then transmits these values to the next branched node until the root node. Finally, the root node receives the local minimum distance value of each branch of the tree network and can select the global minimum and maximum values. These values are then redistributed to all nodes through the tree, for the competition radius computation.  
Our algorithm is more reliable than its counterparts to determine the maximum and minimum values while transmitting a smaller number of messages, as discussed in Section 5.