# Travel Route Planning with Optimal Coverage in Difficult Wireless Sensor Network Environment
## 4 Our Presented TRP-MC Algorithm
### Coverage Optimization Using PSO  
In order to further optimize the number of SPs and the travel route length, we introduce PSO to find the best position for the SPs. Particle swarm optimization (PSO) is a searching algorithm inspired by the hunting process of birds [41]. It can achieve the near-optimal solution in the searching space by iteration. As tour scheduling for the mobile collector has been verified as an NP-hard problem, it is difficult to figure out the optimal solution. Therefore, PSO is very suitable for the tour scheduling in WSNs. We use the virtual particles to represent the location of SPs, and each particle denotes a whole solution for the SPs selection. Due to the fixed dimension of particles in PSO, first we need to confirm the number of SPs. First, we assume that SPs can make full use of the wireless communication space and the number of SPs can be calculated using Formula (13). Different number of SPs will be discussed in the next section. \[spn=\left\lceil\frac{S}{\pi r^{2}}\right\rceil \tag{13}\]  
where \(S\) denotes the total area of the sensor field, and \(r\) denotes the transmission range of the sensors. Then we can construct the particles using a matrix with \(pn\times(2\cdot\)\(spn)\) dimension which is shown as Formula (14) and \(pn\) denotes the number of particles. Figure 7: Hexagon division. \[P=\left[ \begin{array}{c}p^{1}\\ p^{2}\\ p^{2}\\ \vdots\\ p^{pn}\end{array} \right]=\left[ \begin{array}{c}x_{sp_{1}}^{1},y_{sp_{1}}^{1},x_{ sp_{2}}^{1},y_{sp_{2}}^{1}\ldots\ldots x_{sm}^{1},y_{sm}^{1}\\ x_{sp_{1}}^{2},y_{sp_{1}}^{2},x_{sp_{2}}^{2},y_{sp_{2}}^{2}\ldots\ldots x_{sm}^{2 },y_{sm}^{2}\\ x_{sp_{1}}^{3},y_{sp_{1}}^{3},x_{sp_{2}}^{3},y_{sp_{2}}^{3}\ldots\ldots x_{sm}^{3 },y_{sm}^{3}\\ \vdots\\ x_{sp_{1}}^{pn},y_{sp_{1}}^{pn},x_{sp_{2}}^{pn},y_{sp_{2}}^{pn}\ldots\ldots x_{ sm}^{pn},y_{sm}^{pn}\end{array} \right] \tag{14}\]  
where a 2-tuple \(\left(x_{sp_{i}}^{k},y_{sp_{i}}^{k}\right)\) denotes the location of the \(i\)-th SP in the \(k\)-th particle. We set the restrictions for the moving speed of the particles in each dimension and the location of the particles. The restrictions are shown as Formulas (15) and (16). \[\text{restriction}\left(v_{i}^{k}\right)=\left[-20,20\right] \tag{15}\]  
\[\text{restriction}\left(x_{sp_{i}}^{k},y_{sp_{i}}^{k}\right)=\left[0,L\right] \tag{16}\]  
where \(v_{i}^{k}\) denotes the speed of the \(i\)-th dimension of the \(k\)-th particles. Formula (15) ensures that the particles will not move too fast and Formula (16) guarantees the particles will not move away from the sensor field. Next, we define the fitness function for the PSO. As \(r_{cover}\) and \(r_{overlap\_cover}\) are both positive numbers, we adopt Formula (17) which is transformed from Formula (8) as the fitness function and our goal is to minimize the fitness function. \[\text{Fitness}=\frac{r_{overlap\_cover}}{r_{covered}} \tag{17}\]  
Then we execute the PSO algorithm using the following steps. **Step 1:** We initialize the particles \(P\) and the speed of the particles \(v\) with random numbers and they both satisfy the above restrictions. **Step 2:** The value of the fitness function is calculated according to Formula (17). Then each particle compares the current fitness value with its previous optimal fitness value and chooses the smaller one as its local optimal solution which is denoted as \(L_{best}\). In the same way, the previous optimal fitness value of all particles is compared with its current fitness value and the smaller one is chosen as the global optimal solution which is denoted as \(G_{best}\). **Step 3:** Then, we use Formulas (18) and (19) to update the speed and the location of the particles respectively. \[V(t+1)=\lambda V(t)+\alpha\text{-random}\cdot\left(L_{best}-P(t)\right)+\beta \text{-random}\left(\right)\cdot\left(G_{best}-P(t)\right) \tag{18}\]  
\[P(t+1)=P(t)+V(t+1) \tag{19}\]  
where \(\lambda\) represents the inertia coefficient and the function of \(\text{random}()\) is to generate a random number which is between zero and one.