## 2 Routing Protocols in Large-Scale WSNs
### Energy Balance Algorithms  
_GESC_. In [40] the authors proposed an energy-efficient distributed clustering protocol, named Geodesic Sensor Clustering (GESC). GESC aims to prolong the network lifetime by distributing energy consumption evenly, considering the localized network structure and the remaining energy of neighboring nodes. One of the main parts of the protocol is the estimation of the significance of the sensors relative to the network topology. The significance is calculated in the view of the local network at individual nodes. That means the significance of the same node is distinct respect to different local nodes. The view of the local network is defined as the sub-network associated with the set of vertices in \(N_{{}_{12}}\left(v\right)\) which is the combined set of one-hop neighbors and two-hop neighbors of node \(v\). And the node significance index \(NI\left(v\right)\) is calculated by:  
\[NI\left(v\right)=\sum_{{}_{u\in u\
eq uv\
eq v}}\frac{\sigma_{{}_{uv}}\left(v \right)}{\sigma_{{}_{uv}}} \tag{5}\]  
The denominator denotes the number of the minimum hop paths from \(u\in V\) to \(w\in V\) and the numerator denotes the number of the minimum hop paths from \(u\) to \(w\) that some vertex \(v\in V\) lies on. Larger values for the \(NI\) index of a node \(v\) indicate that node \(v\) can reach others on relatively short paths. The author has made some improvements in the calculation and achieved a complexity of \(O(n*m)\) for a network with \(n\) vertices and \(m\) edges. The clustering protocol is divided into rounds which are composed of a clustering formation procedure (CFP) and a network operation procedure (NOP), taking up time \(T_{CFP}\) and \(T_{NOP}\), respectively. CFP clustering is triggered to select new cluster heads. At the start, nodes exchange \"Hello\" messages which contain the list of their neighbors and their residual energy (\(E_{residual}\)) with their neighbors. By this means, every individual node is aware of the existence of its two-hop neighbors. Then the following detailed phases will be carried out:  
1. In this phase, after collecting one-hop and two-hop neighbors of node \(v\), node \(v\) executes _CalculateNodeImportanceIndex_ over its two-hop neighborhood. 2. Then node \(v\) runs a sorting algorithm to obtain a list of its neighbors, sorted in descending order of their \(NI\left(v\right)\). 3. Examine one-by-one the members of the list obtained in phase 2. If the currently examined one-hop neighbor \(u\) covers at least a two-hop neighbor, then designate the one-hop neighbor \(u\) as candidate cluster head node. * Obtain a list of its candidate cluster head nodes by sorting them based on \(E_{residual}\). And choose the node with maximum residual energy as the cluster head. On the occasion of the same residual energy, select the minimum set of one-hop neighbors that cover the two-hop neighborhood. During the first round, all four phases are executed, and after that only phase 4 will be executed until a neighboring node dies, given that the topology will never change due to the immobility scenario. After the network clustering process, each node transmits the sensed data to its cluster head and likewise the cluster head transmit it to its cluster head until the data reaches the information sink. Data aggregation is performed at cluster heads whenever they receive the data from neighboring nodes. The current cluster head will select as next cluster heads only those significant nodes that cover the two-hop neighborhood which is uncovered yet. The current cluster head delivers the message to the next hop after making sure there are not any one-hop neighbors who have already broadcast the message, otherwise it discards the message. When the energy consumed is more than 99.99% of its initial energy level, the node considers itself \"DEAD\" and transmits a \"DEAD\" message to one-hop neighbors, which will delete the dead node from the list and those two-hop neighbors is covered only by the dead node. Finally, they execute the CFP in order to elect new cluster heads.