# UAV Path Optimization for Precision Agriculture Wireless Sensor Networks
## 2 System Model
### Path Planning  
The first step for gathering sensory data from SNs is to perform the UAV path planning. Thus, it is necessary to previously define a route between them, so the UAV must fly over each SN coverage area. However, mathematically there are countless potential trajectories, making it possible to create more economical routes in terms of flight distance. The TSP algorithm that provides the lowest path cost among all SNs has NP-Hard [20; 27] complexity; therefore, several studies propose heuristic models that may offer results as good as TSP, but with a much lower computational complexity. We used as a benchmark the Nearest Neighbor (NN) heuristic TSP model without optimization, which forces the UAV to fly over the coordinates of each SN. In our research, we specifically adopted the Directional NN Algorithm Directed to the Next Nearest Node--DDNN route optimization model. According to the author in [28], the NN offers the most direct representation of a heuristic model for the TSP which generates fairly close results to the optimal route. The DDNN model, on the other hand, still offers greater reduction due to the fact that it uses the limit of the SN communication radius as an entry point to the UAV.  
The DDNN [28] path optimization model calculates the current UAV position in a straight line to its next sensor, always using the intersection of its trajectory with the SN coverage radius. The model always adopts the closest sensor to the UAV current position as next hop. The algorithm implementation is simple and has a low computational cost for the UAV, which is important since it is necessary to constantly reschedule the route as it flies over the SNs. The result of the application of the DDNN model generates a pair of coordinates called _nearest point_ (\(N_{p}\)).  
Figure 2 illustrates the _nearest point_ geometrical concept, where we assume that the UAV is located at the \(A\) vertex of a right triangle, whose coordinates are defined by \(A=(a_{x},a_{y})\). We can calculate the Euclidean distance for the next SN located at point \(B=(b_{x},b_{y})\), \(d_{A,B}=\sqrt{(b_{x}-a_{x})^{2}+(b_{y}-a_{y})^{2}}\). Note that this is an approximation (although very tight) for the flight distance calculation because we are considering very low altitude flight. The nearest point \(N_{p}\) is located between vertices \(A\) and \(B\). The \(n_{x}\) and \(n_{y}\) coordinates of the _nearest point_ are calculated using the Thales intercept theorem [29],  
\[n_{x}=a_{x}+\frac{(b_{x}-a_{x})(d_{A,B}-r)}{d_{A,B}}\qquad\qquad n_{y}=a_{y}+ \frac{(b_{y}-a_{y})(d_{A,B}-r)}{d_{A,B}}, \tag{1}\]  
where the parameter \(r\) denotes the SN communication radius. However, if we consider higher altitudes, it is important to take the UAV flight height on the equation.  
Using the DDNN model, we can calculate the UAV flight distance (\(D_{n}\)), from its origin to the \(n\)-th sensor (\(S_{n}\)). The flight distance is  
\[D_{n}=\sum_{i=1}^{n}d_{i-1,i} \tag{2}\]  
where \(d_{i-1,i}\) is the distance between the \((i-1)\)th and \(i\)th SNs, except \(d_{0,1}\) which is the distance between the UAV initial position (BS location) and the nearest point of its first target destination (SN closest to the BS). Figure 3 illustrates the nearest points (\(N_{p}\)) and the resulting pre-calculated UAV route following the DDNN model. The authors in [28] performed comparisons between different heuristic TSP algorithms. Remarkably, they claim that the DDNN model presents a good trade-off between complexity and path delay reduction.