# Energy-Aware Adaptive Weighted Grid Clustering Algorithm for Renewable Wireless Sensor Networks
## 5 Weighted Grid Clustering Algorithm
### Construction of the Hop Tree  
The area of the grid is assumed to be a square with length of size, s. A division of the square-based grid helps easy coordination among the nodes. Each node in a specific grid calculates its grid coordinates (X, Y) according to the node's location (x, y) with the help of the following equation:  
\[X=\frac{X}{s},\ Y=\frac{Y}{s} \tag{11}\]  
Figure 2: Weighted grid clustering routing design diagram.  
The location of the node (x, y) is found using a GPS. Four technical roles for different nodes have been assigned during the whole procedure of cluster routing [39]. These are as follows:  
**Sink**: A node which is responsible for accumulating data from the following defined coordinator and collaborator nodes.  
**Relay**: These nodes receive data from the coordinator and forward it to the sink.  
**Collaborator**: If there is some data from any node, then these nodes are responsible for sending this data towards the coordinator.  
**Coordinator**: This node accumulates all the data from the collaborator and sends the result towards the sink. These roles of the sensor nodes are shown in Figure 3.  
The pseudo code of this process is given in Algorithm 1.  
```
1. At this stage, sink node broadcasts Hop Configuration Message with initial HopToTree value = 1
2. HopToTree = 1 // u is the member node from the set S // S is the set of node that receives the HCM // HCM is the broadcast message to all the member nodes of the network
3. u \(\in\) S,
4. **For** each, u \(\in\) N do
5. HopToTree(u) > HopToTree(HCM)&&FirstSending(u) \(\leftarrow\) true
6. **then**,
7. NextHop(u) \(\leftarrow\) NID(HCM) // NID is the part of HCM which contains the identification number of the next node
8. HopToTree(u) \(\leftarrow\) HopToTree(HCM) + 1;
9. NID(HCM) \(\leftarrow\) ID(u)
10. HopToTree(HCM) \(\leftarrow\) HopToTree(u);
11. FirstSending \(\leftarrow\) false
12. **else**
13. Delete HCM
14. **End**
```  
**Algorithm 1** Building of the Hop Tree  
Construction of the Hop tree phase calculates the distance between the nodes and the sink. This distance is calculated by the number of hops between them. The sink node initiates this stage with a  
Figure 3: Roles of nodes in the clustered environment.  
Hop Configuration Message (HCM) to all the member nodes of the entire renewable sensor network. This HCM is comprised of two fields, namely the Node Identifier (NID) and HopToTree (HTT). NID carries the identification of the next node, whereas HTT stores the distance from nodes to sink in several hops. At the start of the tree construction, the HTT value for the sink node is stored as 1 whereas the HTT values for remaining nodes are stored as infinity. After receiving the HCM message, each node compares if the value of HTT in the HCM message is less than the value of the HTT which is already stored as 1. At the same time, if the first sending of any member node u is also true then the condition of our algorithm proves true. Then each member node updates the storedvalue of the NextHop variable with the value of the HCM (HTT and NID). On the contrary, the value of the HCM message will also be updated regarding the NextHop variable, HTT and NID as described on line 6-9 of Algorithm 1. Inversely, if the condition is false, the node deletes the received HCM and HTT. The stored values of HCM and HTT remain the same. This procedure repeatedly occurs to configure the complete network.