# A PSO-Based Uneven Dynamic Clustering Multi-Hop Routing Protocol for Wireless Sensor Networks
## 4 Overview of PSO  
Before presenting the proposed algorithm, we give an outline of the particle swarm optimization (PSO) ([PERSON] et al. 1995) algorithm ([PERSON] et al. 1995). PSO is based on a swarm of particles of a predefined number (say \(N_{p}\)). Each particle \(P_{i}\) (\(1\leq I\leq N_{p}\)) provides a complete solution to a multidimensional optimization problem. Dimension \(D\) of all the particles is equal. Particle \(P_{i}\) has position \(X_{i,d}\) (\(1\leq d\leq D\)) and velocity \(V_{i,d}\) in the \(d\)th dimension of the multidimensional space. Let the \(i\)th particle \(P_{i}\) of the population be represented by Equation (3) as follows.  
\[P_{i}=[X_{i,1}(t),X_{i,2}(t),X_{i,3}(t),\ldots,X_{i,D}(t)] \tag{3}\]  
A fitness function is used to evaluate each particle to judge its quality of the solution to the problem. The personal best called \(\textit{Pbest}_{i}\) is the best position of each particle \(P_{i}\). The global best called \(\textit{Gbest}\) is the best position of all particles. In order to reach the global best position, each particle \(P_{i}\) follows its own best, i.e., \(\textit{Pbest}_{i}\) and \(\textit{Gbest}\) to update its own velocity and position. In each iteration, its velocity \(V_{i,d}\) and position \(X_{i,d}\) in dimension \(D\) is updated by using Equations (4), (5), respectively.  
\[V_{i,d}(t)=w\times V_{i,d}(t-1)+c_{1}\times r_{1}\times(\textit{Pbest}_{i,d}- X_{i,d}(t-1))+c_{2}\times r_{2}\times(\textit{Gbest}_{d}-X_{i,d}(t-1)) \tag{4}\]  
\[X_{i,d}(t)=X_{i,d}(t-1)+V_{i,d}(t-1) \tag{5}\]  
\[w=w_{\max}-\frac{w_{\max}-w_{\min}}{T_{R}}\times t \tag{6}\]  
where \(T_{R}\) is the maximum number of iterations, \(w\) (\(w_{\max}\) = 0.9, \(w_{\min}\) = 0.4) is self-adapting parameter, \(c_{1}\) and \(c_{2}\) (\(0\leq c_{1}\), \(c_{2}\leq 2\)) are the acceleration coefficients, and r\({}_{1}\) and r\({}_{2}\) (\(0<r_{1}\), r\({}_{2}<1\)) are the randomly generated values. The update process is repeated until an acceptable value of \(\textit{Gbest}\) is obtained or a fixed number of iterations (\(t_{max}\)) is reached. After getting a new updated position, the particle evaluates the fitness function and updates \(\textit{Pbest}_{i}\) as well as \(\textit{Gbest}\) for the minimization problem as follows.  
\[\textit{Pbest}_{i}=\left\{\begin{array}{ll}P_{i},&if(\textit{Fitness}(P_{i} )<\textit{Fitness}(\textit{Pbest}_{i}))\\ \textit{Pbest}_{i},&\textit{otherwise}\end{array}\right. \tag{7}\]\[\textit{Gbest}=\left\{\begin{array}{ll}P_{i},&\textit{if}(\textit{Fitness}(P_{i}) <\textit{Fitness}(\textit{Gbest}))\\ \textit{Gbest},&\textit{otherwise}\end{array}\right. \tag{8}\]  
Figure 1 shows how a particle explores in the multi-dimensional search space to achieve a global best solution. A particle \(P_{i}\) occupies position \(X_{i,d}(t)\) with velocity \(V_{i,d}(t)\) at a point of time and it is moving in a certain direction. Later the particle changes the direction and moves to another position using its memory. It then changes its direction again by the influence of the swarm and occupies a new position \(X_{i,d}(t+1)\).  
After a number of iterations, the particles will find the optimal solution in the searching space. The workflow of PSO is illustrated as Figure 2.