# Data Gathering Techniques in WSN: A Cross-Layer View
## 5 Routing for Data Gathering in WSN
### Common WSN Routing Protocols for Data Gathering
#### 5.1.1 Cluster-Based Routing Protocols  
A significant milestone in WSN routing protocols is the low-energy adaptive clustering hierarchy (LEACH) protocol [105]. The basic LEACH protocol is an adaptive clustering-based protocol that dynamically selects sensor nodes as cluster-heads. Each cluster-head aggregates data from its cluster members and relays it to the sink. In order to distribute the high energy consumption imposed on cluster-heads between all the sensor nodes, the cluster-heads are dynamically selected according to a predefined probability that depends on the number of desired clusters. The resulting protocol causes continuous clustering hierarchy reelection, which facilitates energy balancing. The original version presented by [PERSON] et al. [105] considers a setup in which all sensor nodes can directly communicate with the sink; hence, each cluster-head can directly relay the collected information from its cluster members to the sink. However, as described in the paper, LEACH can be easily extended to a hierarchical cluster setup in which the cluster-head nodes of each tier are also organized in clusters such that each cluster-head relays its aggregated data to its higher-layer cluster-head, and so on up to the top layer of the hierarchy, at which point the data are sent to the sink. Since its publication in 2000, numerous protocols have relied on LEACH's clustering paradigm, suggesting enhancements and improvements for various setups and requirements. For instance, EE-LEACH [106; 107] aims at improving the energy efficiency of LEACH by considering the sensor's residual energy throughout the stages of the protocol. Specifically, EE-LEACH assumes that node deployment is implemented according to a two-dimensional Gaussian distribution. It forms clusters and selects their respective cluster-heads based on the residual energy of neighboring nodes. The relay nodes that forward the data aggregated by cluster-heads to the sink are selected based on their residual energy. A clustering procedure based on recursive rectangular partitioning of the network grid following the \(k\)-d tree algorithm is demonstrated by [PERSON] et al. [108]. The authors adjust a protocol that combines their clustering methods and report that it performs better than LEACH. Several surveys have summarized the successors of the LEACH protocol (e.g., [107]). Figure 4: Schematic partition of the papers discussed in this section into the main routing topics covered in the section. PEGASIS [109] was designed to address the overhead resulting from the cluster formation in LEACH. Specifically, PEGASIS replaces the clusters with a node-chain in which each node receives the data from its predecessor and transmits it to its successor in the chain. The data is gathered while getting fused along the chain until eventually, a designated node transmits it to the sink. PEGASIS relies on nodes having global knowledge of the network and shows that a simple greedy algorithm for the forwarding chain construction, in which nodes select their closest neighbors as the next hops in the chain, is sufficient to significantly reduce energy consumption. Similar to LEACH, and in order to balance the energy depletion in the network, different nodes transmit the fused data to the sink on each data-gathering round. P-LEACH [110] offers a hybrid between LEACH and PEGASIS that relies on cluster formation where cluster-heads collect and forward traffic. Rather than forward the traffic directly to the sink, or create a hierarchical cluster setup in which cluster-heads are also grouped into clusters with another cluster-head, P-LEACH adopts chain-based forwarding such that the cluster-heads are arranged in a chain along which the collected data is forwarded, as suggested by PEGASIS. Several LEACH enhancements have relied on bio-inspired algorithms. For example, [PERSON] et al. [111] utilize adaptive particle swarm optimization (APSO).