# A Clustering WSN Routing Protocol Based on k-d Tree Algorithm
## 3 Background and Preliminaries
### The LEACH Protocol  
The Low-Energy Adaptive Clustering Hierarchy protocol (LEACH) uses a cluster-based routing scheme to minimize total network energy consumption. In LEACH, nodes deployed in an area are organized into clusters, with each cluster having a CH node, as shown in Figure 1. The communication process is divided into two phases: the configuration phase and the stable state phase [10]. During the configuration phase, the CH nodes and member nodes of each cluster are selected. During the stable state phase, nodes are added to the CH node and remain in waiting to initiate data transmission to the Base Station (BS) node, using the sequence shown in Figure 2. In the literature, many authors refer to the base node as Sink node [38], which we refer to from this point on as Sink/BS node. The duration of the stable state phase is longer than the configuration phase, due to the processing work performed in it. Consequently, energy consumption during the stable state phase is higher. Figure 1: LEACH protocol topology. Figure 2: LEACH protocol phases. During the configuration phase, the nodes that will become CH nodes for the current round are selected independently and randomly, with the requirement that their energy is greater than zero and a lower threshold. The capacity to become a CH node is determined by the generation of a random number \((R_{n})\) where \(R_{n}\in[0,1]\). The CH node is selected if \(R_{n}\leq T(n)\), where \(T(n)\) is a threshold value obtained from Equation (1). The CH node will transmit its nomination to the nodes in the cluster. The nodes in the cluster are selected by their distance to the CH node and, in some cases, this is measured through the received signal strength indicator (RSSI) [39]:  
\[t(n)=\left\{ \begin{array}{cc}\frac{p}{1-p\cdot(r\cdot mod-\frac{1}{p}))},& \quad\text{if }n\in G,\\ 0,&\quad\text{another }\text{ case}.\end{array} \right. \tag{1}\]  
where \(p\) is the probability for a node to become CH node over all the nodes in the network, \(r\) is the current number of selection rounds, and \(G\) is the set of nodes that were not selected as CH nodes before \(\frac{1}{p}\) rounds. The CH nodes selected for each cluster will reserve a free slot for data transmission of the member nodes by using a distribution of a TDMA programming table that will indicate each CH node the data transmission sequence, giving CH nodes the possibility of staying in repose for the longest possible time. Using TDMA for data transmission prevents collisions within each cluster [40]. In the steady state phase, CH nodes compile data from the nodes in each cluster and send them to the \(\text{Sink}/\text{BS}\) node. Data redundancy may occur during this phase. The redundant packets being processed and transmitted to the \(\text{Sink}/\text{BS}\) node result in an increase in unnecessary network traffic and overall network bandwidth, which directly affects energy consumption. The more redundant data is processed, the more energy will be wasted. Data transmission to CH nodes saves energy in comparison to direct data transmission from the nodes to the \(\text{Sink}/\text{BS}\) node. Therefore, to avoid the early death of CH nodes, all the nodes in the network will elect other CH nodes, repeating both phases for every round during the lifetime of the network. For every node, we used the energy model described in [41], which is shown in Figure 3. This assumes that the wireless channel is completely symmetrical, so the energy used in transmitting a message through the round-trip route between a network node and the \(\text{Sink}/\text{BS}\) node through the CH node, \(v_{i}\) and \(v_{j}\) is equal. The free space channel model used is \(d^{2}(v_{i},v_{j})\), as the nodes are located in a plane and remain static and we assume that there is a direct line of sight between the network nodes and the \(\text{Sink}/\text{BS}\) node.