# A Clustering WSN Routing Protocol Based on k-d Tree Algorithm
## 1 Introduction  
Wireless Sensor Networks (WSN) have exploded in popularity in the last few years. Part of this growth is due to the popularization of the Internet of Things (IoT), where connectivity, sensitivity, interaction, and energy are elements of the systems in a WSN. In a WSN, a node is defined as the minimal functional unit of a network and is comprised of a sensor/actuator, a central processing unit (CPU), a memory bank, a wireless transceiver, and a power source. As a unit, the node suffers energy depletion of its internal battery as a result of sensing, processing, data transmission and reception. Interaction through wireless transmission in a WSN includes issues such as link viability, time to establish communication, data loss due to competition overuse of a wireless channel, data loss due to simultaneous transmission attempts, data loss due to repeated network flooding, and data loss due to transmission range. Network scalability problems are caused by the birth, reboot, and death of one or several nodes in the network. Link problems in WSNs include neighbor discovery, message, loss, latency, and congestion. WSNs also have routing problems such as communication path and loop discovery [1]. In general lines, WSNs have a wide range of problems, although most of them have been addressed through communication protocols. The aforementioned problems have been approached through flat and hierarchical routing structures. In a flat routing structure, all the nodes in the network play the same role in end-to-end routing protocols. In hierarchical routing structures, nodes are classified by functionality and the network is divided into groups or clusters, each of which chooses a leading node that is called Cluster Head node (CH). The CH node coordinates activities inside and outside the cluster with non-CH nodes. The main feature of flat routing structures is the ability to establish communication between any two nodes in the network without the participation of a central node. These networks, also called ad hoc networks, can operate in isolation, without connection to network infrastructure such as the Internet. A hierarchical routing structure organizes large-scale ad hoc networks into groups or clusters, with the objective of improving network efficiency beyond the attainable level of flat routing structures. Although hierarchical routing can increase control traffic, its topology allows for data traffic to be confined within each cluster. Nodes inside each cluster can organize to optimize communications and reduce interference caused by simultaneous data transmission. Cluster-based hierarchical routing presents some advantages in scalability and communication efficiency. Protocols based on this schema have been used to achieve routing efficiency in connection to node energy levels. That is, nodes with higher energy reserves are candidates to becoming CH nodes, and those with lower energy levels are used to monitor the environment. In this type of routing, CH nodes have specific functions to improve the scalability, lifetime, and energy efficiency of the network. Cluster-based routing structures represent a simpler approach to the issues of WSNs, lowering the complexity of flat routing structures [2]. However, cluster-based routing schemes are, in general, comprised of a cluster-formation and a CH-node selection mechanism. The behavior of the latter has an impact on the WSN's general performance since a high degree of variability in this mechanism creates a proportional variability of the network's response regarding delay, jitter, and throughput, and an inversely proportional response in energy levels. The cluster formation mechanism creates clusters of varying sizes and, as a consequence, of varying density. This cluster formation method has an impact on the behavior of the network, which responds according to its cluster formation type.