# A PSO-Based Uneven Dynamic Clustering Multi-Hop Routing Protocol for Wireless Sensor Networks
## 1 Introduction  
Wireless sensor networks (WSNs) have attracted widespread attention in recent years. Due to the low cost, small size and self-organization of sensors [1], WSNs have been adopted in diverse application fields, such as military, crime prevention, environmental monitoring, health care services, vehicular movements, etc. [2; 3; 4] As sensor nodes are supplied by non-rechargeable batteries [5], designing an energy-efficient routing protocol to prolong the network lifetime is a vital issue in WSNs. A number of routing protocols have been proposed to reduce the energy consumption of WSNs. Among them, the clustering scheme has better flexibility and scalability, and is considered to be one of the most effective solutions in this regard. Therefore, most of the current researches on routing protocols are based on the clustering scheme, such as LEACH (Low-Energy Adaptive Clustering Hierarchy) [6], PEGASIS(Power-Efficient GAthering in Sensor Information Systems) [7], HEED (Hybrid Energy-Efficient Distributed clustering) [8], EEMC (Energy-Efficient Multi-level Clustering) [9] and so on. Clustering can improve energy efficiency, but it can cause hotspot problems [10; 11]. Many energy-efficient clustering routing algorithms have been proposed to solve the hotspot problem. Reference [12] proposed a gravitational search algorithm (GSA) based clustering and routing algorithm. GSA uses formulae to elect CH nodes and assign nodes to address the hotspot problem. The UCCGRA (Unequal Clustering and Connected Graph Routing Algorithm) algorithm [13] considers the clustered network with unequal size based on sensor energy used for the transmission. The workhighlights the concept of balancing the node energy for inter and intra cluster communication. In UCCGRA, the vote based selection of CH nodes creates more control message overheads during re-clustering, which cause unnecessary energy depletion. Grid-based clustering protocols, such as [14; 15; 16], form clusters by dividing the network area into grids. The size of the grids away from the BS is larger than the size of the grids near the BS, which can alleviate the hotspot problem to some extent. However, for a network environment with uneven node distribution, grid-based clustering is unreasonable. Because there may be a large difference in the number of nodes in the same size grids. The aforementioned protocols improve the energy efficiency of WSNs. However, not all the protocols carefully consider the distribution of nodes. Moreover, most of these algorithms focus only on the selection of CH nodes. They do not carefully consider the distribution and scale of clusters. The protocols suffer from an energy imbalance across the network. The hotspot problem still exists to a certain extent and some protocols cannot be applied to large-area network environments. This paper proposes a PSO-based uneven dynamic clustering multi-hop routing protocol (PUDCRP), which alleviates the hotspot problem and achieves better energy balance. We use an improved PSO algorithm to determine the circular area where candidate CH nodes are located. We introduce a multi-objective fitness function to select CH nodes. We also propose a connecting line aided route construction method to achieve an energy efficient routing. Simulation results proved that PUDCRP has a better performance in network lifetime and energy consumption of the network. The major contributions of this paper can be summarized as follows. * We propose a PSO-based uneven dynamic clustering method which divides the network area into circles with unequal sizes based on the distribution of nodes. The circles far away from the BS are larger than the ones near the BS, which can alleviate the hotspot problem. * We introduce a multi-objective function to select CH nodes from the circles. The function considers nodes' residual energy, the number of neighbor nodes, and distances from the nodes to the BS. Therefore, the intra-cluster energy consumption is minimized.