# Travel Route Planning with Optimal Coverage in Difficult Wireless Sensor Network Environment
## 4 Our Presented TRP-MC Algorithm
### Travel Path Planning Using ACO  
After all the SPs are selected, the shortest loop is scheduled by ACO to connect all the SPs. ACO is a metaheuristic algorithm inspired by the food-seeking of ants [42]. Ants secrete pheromones on their moving path and the shorter path will be traveled by more ants. Then, higher concentration of pheromones will be focused on those paths. Therefore, ants can seek a shorter path by referring to the experience of other ants. We regard the network as a complete undirected graph which is denoted by \(G=<V,E>\), where \(V\) denotes the set of SPs and \(E\) denotes the virtual links between every two SPs. We use the matrix \(A\) with dimension \(m\times spn\) to record the journey of ants, where \(m\) denotes the number of ants and \(spn\) denotes the number of SPs. Matrix \(T\) with dimension \(spn\times spn\) is used to record the pheromone concentration of the virtual link. ACO algorithm is executed using the following steps.  
**Step 1:** We randomly distribute \(m\) ants in SPs and initialize matrix \(A\).  
**Step 2:** Then, we calculate the possibility of selecting SPs which are not visited as the next destination for each ant, according to the pheromone concentration and their distance. Ants visit all those SPs according to the possibility and record the journey in matrix \(A\). The possibility of SPs which are not visited can be calculated by Formula (20).  
\[p_{ij}^{k}(t)=\left\{\begin{array}{c}\frac{\varphi_{ij}^{a}(t) \cdot p_{ij}^{b}(t)}{\Sigma_{nstart}\varphi_{im}^{a}(t)\cdot p_{im}^{b}(t)}\ if\ j\in next\\ 0\quad\ otherwise\end{array}\right. \tag{20}\]  
where \(p_{ij}^{k}(t)\) represents the possibility of selecting the path from \(SP_{i}\) to \(SP_{j}\) for the \(k\)-th ant in the \(t\)-th iteration. \(\varphi_{ij}\) denotes the pheromone concentration of the path from \(SP_{i}\) to \(SP_{j}\) and \(\mu_{ij}\) denotes the reciprocal of the distance from \(SP_{i}\) to \(SP_{j}\). \(\alpha\) and \(\beta\) denote two different control factors for pheromone concentration and inspired factor. The set \(next\) denotes the SPs that the ant has not visited.  
**Step 3:** Next, we calculate the journey of each ant using Formula (21). Since our goal is to minimize the tour length of the mobile collector, we only evaluate the journey on its length.  
Figure 8: SPs selection using PSO.  
\[L\left(a^{k}\right)=\sum_{i,j\in\text{SPs}_{i}\
eq j}l_{ij}\cdot b_{ij} \tag{21}\]  
where \(l_{ij}\) denotes the distance from \(SP_{i}\) to \(SP_{j}\) and \(b_{ij}\) can be illustrated using Formula (22).  
\[b_{ij}=\left\{\begin{array}{cc}1&\text{if path from $SP_{i}$ to $SP_{j}$ is contained on $k-th$ ant's journey}\\ 0&\text{otherwise}\end{array}\right. \tag{22}\]  
**Step 4:** Finally, we update the concentration of the pheromone using the following formulas.  
\[\varphi_{ij}(t+1)=(1-\eta)\cdot\varphi_{ij}(t)+\Delta\varphi_{ij} \tag{23}\]  
\[\Delta\varphi_{ij}=\sum_{k=1}^{m}\Delta\varphi_{ij}^{k} \tag{24}\]  
\[\Delta\varphi_{ij}^{k}=\left\{\begin{array}{cc}\frac{Q}{L\left(a^{k}\right) }&\text{if the $k-th$ ant pass path}_{ij}\\ 0&\text{otherwise}\end{array}\right. \tag{25}\]  
where \(\eta\) denotes the volatilization rate of pheromone and \(Q\) denotes the total amount of pheromone secreted by one ant during one whole travel.  
**Step 5:** Steps 1-4 are repeatedly executed until the algorithm achieves its maximal iteration number.  
The same sample after executing ACO is shown in Figure 9.