Ramkumar Ganapathy
^{}
Christopher Thron
^{}*
^{}

Author Information

Texas A&M University-Central Texas, Killeen, TX 76549, USA

*

Authors to whom correspondence should be addressed.

Received: 12 January 2024 Accepted: 30 May 2024 Published: 12 June 2024

© 2024 The authors. This is an open access article under the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/).

ABSTRACT:
We consider a remote sensing system in which fixed sensors
are placed in a region, and a
single drone flies over the region to collect information from cluster heads. We assume that the drone has a fixed
maximum range and that the energy
consumption for information transmission from the cluster heads increases with
distance according to a power law. Given
these assumptions, we derive local optimum conditions for a drone path that
either minimizes the total or maximum energy required by the cluster
heads to transmit
information to the drone. We show
how a homotopy approach can produce a family of solutions for different drone path lengths so that a locally optimal
solution can be found for any drone range. We implement the homotopy solution in Python
and demonstrate the tradeoff between drone range and cluster head power
consumption for several geometries. Execution
time is sufficiently rapid for the computation to be performed in real time so
that the drone path can be recalculated on the fly. The solution is shown to be globally optimal for sufficiently long drone path lengths. A proof of concept
implementation in Python is available on GitHub. For future work, we
indicate how the solution can be modified to accommodate moving sensors.

Keywords:
Wireless sensor network; Drone; Path planning; Information collection; Power-efficient; Extended lifetime; Optimization

There are many critical applications for remote sensing in low-resourced areas. Some of these include agricultural monitoring of crops and/or forests for fire and/or disease; wildlife monitoring to track wildlife movement and detect poachers; free-range livestock monitoring to track herd movement and to prevent cattle rustling; and early warning of terrorist or bandit activity. In low-resourced situations especially, the system cost is of huge importance and spells the difference as to whether or not the system may be implemented. Sensors in area-monitoring networks typically are battery-powered and must be replaced when their batteries are exhausted. This can be both difficult and costly, particularly in inaccessible locations. For this reason, reducing the power consumption of sensors in the field is a key factor in designing such remote sensing systems.
One possible approach to reducing power consumption, which has been investigated by a number of researchers, is to supplement the WSN with unmanned aerial vehicles (UAV) such as drones fitted with receiving antennas and either information storage or transmit capabilities. Such drones can serve as moveable sinks or relays, travelling to or near the transmitting elements within the network in order to reduce transmission distance, hence power expenditure.
Previous authors have investigated practical use cases for using drones to collect information from WSN’s. [1,2] have provided comprehensive surveys of drone-assisted data collection from wireless sensor networks. The integration of UAVs into surveillance systems involving WSNs and other technologies is discussed in [3]. Several previous papers have dealt specifically with drone path planning in various scenarios. References [4,5] assess several metaheuristic algorithms for path planning in the context of disaster management and pre-planning. [6] gives a heuristic algorithm to decide which node within a cluster to fly to so as to gather information from the cluster. [7] uses a boustrophedon-type (i.e., back-and-forth) flight path for a sensor network located in a region divided into square cells. [8] considers the problem of minimizing the flight time of an information-gathering drone in the case where sensors are in a straight line, and the time required for information transfer from each sensor is an important consideration. [9] considers the impact of drone path shape on information transmission from sensors to drones. [10] uses particle-swarm optimization to arrive at an optimal path. [11] presents an efficient joint data collection and sensor positioning scheme for WSN supported by multiple UAVs.
In low-resource situations, expense is a paramount concern in systems design. Systems with multiple drones may not be feasible because of the expense. On the other hand, systems with a single drone must accommodate the limiteddrone range. If the drone takes several trips to reach all sensors, this delays the receipt of information and reduces the thoroughness of coverage. In such cases, it may be preferable to design a drone tour of all sensors that approaches the sensors as closely as possible.
In this paper, we consider a hybrid WSN-drone system for remote sensing, in which a single drone of limited range is used to collect information from wireless sensors that have fixed locations in the field (see Figure 1). The drone harvests information from all sensors during a single tour. The system design is posed as a constrained optimization problem. Our novel solution approach involves using a Lagrange multiplier to construct a differential equation in which the Lagrange multiplier is the independent variable. Since our approach reduces the problem to the numerical solution of a multivariate ordinary differential equation (ODE), it can make use of efficient, highly developed algorithms for solving ODEs, thus reducing execution time and making it possible to compute optimal trajectories on-the-fly for very large WSNs.

- (
*x*,_{j}*y*),_{j}*j*= 1...*J*: positions of the cluster heads that are sending the information; *L*: Maximum path length for the drone;*p*: Power loss exponent.

- (
*u*,_{j}*v*),_{j}*j*= 1...*J*: Drone positions for harvesting information from cluster heads. Here, the order of points the drone takes is assumed to be (*u*,_{j}*v*) to (_{j}*u*_{j+1},*v*_{j+1}) for*j*= 1 ...*J*− 1. - (
*u*_{0},*v*_{0}), (*u*_{J+1},*v*_{J+1}): Drone starting and ending position, respectively.

```latexf(\vec{u},\vec{v})=\sum_{j=1}^J\left(\left(x_j-u_j\right)^2+\left(y_j-v_j\right)^2\right)^{p/2},```

The drone’s limited range imposes the constraint $$g(\vec{u},\vec{v})$$ ≤

```latex\vec{w}_{j}{:}=\vec{w}_{j}\big(u_{j},v_{j}\big)\,and\,\vec{z}_{J}{:}=\big(x_{j},y_{j}\big).```

```latex\left|\vec{w}_j+\delta\big(\vec{z}_j-\vec{w}_j\big)-\vec{z}_j\right|=(1-\delta)\big|\vec{w}_j-\vec{z}_j\big|<\big|\vec{w}_j-\vec{z}_j\big|,```

```latex\text{Minimize }f(\vec{u},\vec{v})\text{subject to }g(\vec{u},\vec{v})=L.```

```latex\lim_{p\to\infty}\bigl(a_{1}^{p}+\cdots+a_{J}^{p}\bigr)^{1/p}=\max_{j}a_{j}\quad if \,a_{j}>0\,\forall \,j,```

```latex\nabla f(\vec{u},\vec{v})=\lambda\nabla(g(\vec{u},\vec{v})-L),```

```latex\nabla h(\vec{u},\vec{v}){:}=\left(\frac{\partial f}{\partial u_{1}},...\frac{\partial f}{\partial u_{j}},\frac{\partial f}{\partial v_{1}},...\frac{\partial f}{\partial v_{j}}\right),```

```latex\frac{\partial f}{\partial u_{j}}=\lambda\frac{\partial g}{\partial u_{j}};\frac{\partial f}{\partial v_{j}}=\lambda\frac{\partial g}{\partial v_{j}},\quad(j=1\ldots J)```

```latexa_j:=u_j-x_j;b_j:=v_j-y_j;A_j:=a_j^2+b_j^2,```

```latexm_j:=u_j-u_{j+1};n_j:=v_j-v_{j+1};M_j:=\left(m_j^2+n_j^2\right)^{\frac{1}{2}}.```

Using this notation, we have:

```latex\frac{\partial f}{\partial u_{j}}=\frac{\partial f}{\partial A_{j}}\times\frac{\partial A_{j}}{\partial a_{j}}\times\frac{\partial a_{j}}{\partial u_{j}}=(\left(\frac{p}{2}\right)A_{j}^{\frac{p}{2}-1}\times2a_{j}=pa_{j}A_{j}^{q}```

```latex\frac{\partial g}{\partial u_{j}}=\frac{\partial g}{\partial M_{j-1}}\times\frac{\partial M_{j-1}}{\partial m_{j-1}}\times\frac{\partial m_{j-1}}{\partial u_{j}}+\frac{\partial g}{\partial M_{j}}\times\frac{\partial M_{j}}{\partial m_{j}}\times\frac{\partial m_{j}}{\partial u_{j}}=\\\left(\frac12\right)M_{j-1}^{-1}\big(2m_{j-1}\big)(-1)+\bigg(\frac12\bigg)M_j^{-1}\big(2m_j\big)=\frac{m_j}{M_j}-\frac{m_{j-1}}{M_{j-1}}.```

```latex\frac{\partial f}{\partial v_{j}}=pb_{j}A_{j}^{q};\frac{\partial g}{\partial v_{j}}=\frac{n_{j}}{M_{j}}-\frac{n_{j-1}}{M_{j-1}}.```

```latexpa_{j}A_{j}^{q}=\lambda\left(\frac{m_{j}}{M_{j}}-\frac{m_{j-1}}{M_{j-1}}\right);pb_{j}A_{j}^{q}=\lambda\left(\frac{n_{j}}{M_{j}}-\frac{n_{j-1}}{M_{j-1}}\right)\quad(j=1\ldots J).```

```latexp\frac{d}{ds}\big(a_{j}A_{j}^{q}\big)=\frac{d}{ds}\bigg(\lambda\frac{m_{j}}{M_{j}}-\lambda\frac{m_{j-1}}{M_{j-1}}\bigg),\\p\frac{d}{ds}\big(b_{j}A_{j}^{q}\big)=\frac{d}{ds}\bigg(\lambda\frac{n_{j}}{M_{j}}-\lambda\frac{n_{j-1}}{M_{j-1}}\bigg).```

```latex\frac{dg}{ds}=-1\Rightarrow\sum_{j=0}^J\frac{dM_j}{ds}=-1.```

```latex0=pA_{j}^{q}\frac{da_{j}}{ds}+pqa_{j}A_{j}^{q-1}\frac{dA_{j}}{ds}-\frac{\lambda}{M_{j}}\frac{dm_{j}}{ds}+\frac{\lambda}{M_{j-1}}\frac{dm_{j-1}}{ds}+\\\frac{\lambda m_{j}}{M_{j}^{2}}\frac{dM_{j}}{ds}-\frac{\lambda m_{j-1}}{M_{j-1}^{2}}\frac{dM_{j-1}}{ds}-\frac{m_{j}}{M_{j}}\frac{d\lambda}{ds}+\frac{m_{j-1}}{M_{j-1}}\frac{d\lambda}{ds}```

```latex\begin{gathered}\frac{da_{j}}{ds}=\frac{du_{j}}{ds}; \\\frac{dA_{j}}{ds}=2a_{j}\frac{du_{j}}{ds}+2b_{j}\frac{dv_{j}}{ds}; \\\frac{dm_{j}}{ds}=\frac{du_{j}}{ds}-\frac{du_{j+1}}{ds}; \\\frac{dM_{j}}{ds}=M_{j}^{-1}\left(m_{j}\left(\frac{du_{j}}{ds}-\frac{du_{j+1}}{ds}\right)+n_{j}\left(\frac{dv_{j}}{ds}-\frac{dv_{j+1}}{ds}\right)\right) \end{gathered}```

Using various algebraic manipulations and the fact that:

```latex1-\frac{m_j^2}{M_j^2}=\frac{n_j^2}{M_j^2}```

```latex\begin{gathered} 0=\frac{du_{j}}{ds}\left(pA_{j}^{q}\left(1+\frac{2qa_{j}^{2}}{A_{j}}\right)-\frac{\lambda n_{j-1}^{2}}{M_{j-1}^{3}}\right)-\frac{\lambda n_{j}^{2}}{M_{j}^{3}} \\+\frac{du_{j-1}}{ds}\biggl(\frac{\lambda n_{j-1}^{2}}{M_{j-1}^{3}}\biggr)+\frac{du_{j+1}}{ds}\biggl(\frac{\lambda n_{j}^{2}}{M_{j}63}\biggr) \\+\frac{dv_{j}}{ds}(2pqa_{j}b_{j}A_{j}^{q-1}+\frac{\lambda m_{j-1}n_{j-1}}{M_{j-1}^{3}}+\frac{\lambda m_{j}n_{j}}{M_{j}^{3}}) \\-\frac{dv_{j-1}}{ds}\biggl(\frac{\lambda m_{j-1}n_{j-1}}{M_{j-1}^{3}}\biggr)-\frac{dv_{j+1}}{ds}\biggl(\frac{\lambda m_{j}n_{j}}{M_{j}^{3}}\biggr) \\+\frac{d\lambda}{ds}\biggl(-\frac{m_{j}}{M_{j}}+\frac{m_{j-1}}{M_{j-1}}\biggr),j=1\ldots J \end{gathered}```

The entire system of 2

```latexH\frac{d\mathbf{u}}{ds}=z\Rightarrow\frac{d\mathbf{u}}{ds}=H^{-1}\vec{z}```

```latex\mathbf{u}:=[\vec{u},\vec{v},\lambda]^{T};\\\mathbf{z}:=[0,....0,-1]^{T}```

```latexH=\begin{bmatrix}H_{11}&H_{12}&\overrightarrow{h_1}\\H_{21}&H_{22}&\overrightarrow{h_2}\\\overrightarrow{h_1^T}&\overrightarrow{h_2^T}&0\end{bmatrix}```

```latex\begin{pmatrix}u_j,v_j\end{pmatrix}=\begin{pmatrix}x_j,y_j\end{pmatrix}+\vec{\epsilon}_j.```

```latex\begin{gathered}\nabla f(u_{j},v_{j})=p\left(\left(x_{j}-u_{j}\right)^{2}+\left(y_{j}-v_{j}\right)^{2}\right)\left[(x_{j}-u_{j}),\left(y_{j}-v_{j}\right)\right] \\=p\big|\overrightarrow{\epsilon}_{j}\big|^{p-2}\overrightarrow{\epsilon}_{j} \\=p\big|\overrightarrow{\epsilon}_{j}\big|^{p-1}\widehat{\epsilon}_{j} \end{gathered}```

```latexp\big|\vec{\epsilon}_{j}\big|^{p-1}\widehat{\epsilon}_{j}=\lambda\nabla_{j}g(\vec{u},\vec{v}),```

```latex\nabla_{j}g(\vec{u},\vec{v}):=(\frac{\partial g}{\partial u_{j}},\frac{\partial g}{\partial v_{j}})```

```latex\nabla_{j}g(\vec{u},\vec{v})\approx\nabla_{j}g(\vec{u},\vec{v})|_{\vec{u}=\vec{x}},```

```latexp\left|\overrightarrow{\epsilon_{j}}\right|^{p-1}\widehat{\epsilon_{j}}=\lambda\overrightarrow{g_{j}}\\\Rightarrow\widehat{\epsilon_{J}}=\pm\widehat{g_{J}}\mathrm{~and}\left|\epsilon_{j}\right|=\left|\frac{\lambda}{p}\right|^{(\frac{1}{p-1})}\left|\overline{g_{J}}\right|^{(\frac{1}{p-1})}```

Figure 2, Figure 3 and Figure 4 display results from simulations of the test cases described in Section 2.10 using the Python code described in Appendix A.
Figure 2 contains a 6 × 2 grid of plots that shows results from the test scenarios listed above. Each plot shows solutions in the homotopy corresponding to different drone path lengths. The longest path in each homotopy is the travelling-salesman path that joins the cluster heads; while the shortest is the straight-line path that joins starting and ending points. The algorithm computes the vertices from longest path to shortest, according to the ODE in equation (25) with initial conditions $$(\vec{u},\vec{v})=(\vec{x},\vec{y})$$, where the (*x*_{j},*y*_{j} ) are in travelling salesman order. Initially, the paths roughly preserve the original shape as they shrink (in fact, it can be shown that as the path shrinks, the path vertices always move in the direction of the angle bisectors of the path polygon.) After several iterations, path vertices merge: for example, the first figure in the first row starts with a path containing 5 segments, which eventually becomes 4 and then 3 segments as the path length shrinks. Similar changes occur in the other figures.
The left-hand graph in Figure 3 plots the difference between the travelling salesman tour length and the length of the drone’s path (which for simplicity, we denote as the “path defect”) as a function of the iteration number in the ODE solution, for each of the test cases. The initial path length is equal to the tour length; hence, all graphs start from (0,0). The path defect increases more rapidly for scenarios with more cluster heads and longer travelling salesman tour lengths. For all scenarios, the rate of increase of path defect slows as the number of iterations increases. Eventually, the curves become flat when the homotopy reaches the minimum path that joins (*u*_{0},*v*_{0} ) and (*u*_{J+1},*v*_{J+1}).
The right-hand graph in Figure 3 shows the WSN’s energy expenditure as a function of step number. As expected, this increases with iteration number as the path length decreases.
There are noticeable bends in both graphs, which occur at the same iteration number. For example, in the curves for test-7, test-8 and test-9 there are concurrent bends in both the defect curve and the total energy curve, which occur near iteration numbers 75, 125, and 150, respectively. In the homotopy, the bend indicates the merger of two path vertices so that two cluster heads both correspond to a single vertex. This shows that vertex mergers slow down the algorithm’s progress.
The tradeoff between drone path length and energy expenditure is more clearly shown in Figure 4, which plots the *p*’th root of cluster head energy consumption on the vertical axis versus cluster head tour length minus drone path length on the horizontal axis. In our simulations *p* = 2, so the *p*’th root of energy is the ℓ^{2} norm of the vector $$[|\vec{z}_{1}-\vec{w}_{1}|,\ldots,|\vec{z}_{J}-\vec{w}_{J}|]$$ consisting of distances between cluster heads and corresponding drone path vertices. In the case where all distances $$|\vec{z}_{j}-\vec{w}_{j}|$$ are approximately equal, then the *ℓ*^{2} norm is nearly proportional to the mean distance between the cluster head and the corresponding drone vertex. The linear section of the graphs in Figure 4 indicates an initial linear dependence of the distance between cluster heads and drone vertices as the path defect increases. However, as the path defect increases (corresponding to a decrease in drone range), the dependence of total energy on path length becomes noticeably convex. Unlike the energy versus iteration and path defect versus iteration curves in Figure 3, there are no bends in these curves. This indicates that the bends reflect convergence issues for the numerical solution for the homotopy rather than a change in the trends in energy over the homotopy as the drone range is varied.
Figure 5 represents different runtime characteristics associated with the numerical solution of equation (15) for different numbers of cluster heads and different drone ranges. The three panels in Figure 5 represent the total runtime, number of Runge-Kutta iterations, and runtime per iteration for the 12 scenarios shown in Figure 2 for four different drone ranges, plotted as a function of the number of vertices in the solution path. For each of the 12 scenarios, we chose four evenly-spaced drone ranges of 0.2, 0.4, 0.6, and 0.8 times the minimum range required to reduce the objective function $$f(\vec{u},\vec{v})$$ to 0, which is equal to the length of the travelling salesman path joining the points {(*x*_{j},*y*_{j})}. The graphs show gradual increases in runtime as the number of cluster heads increases. The runtime per iteration does increase for more cluster heads (as expected, since more variables must be solved for), but this increase is offset by a concurrent general decrease in the number of iterations required for each drone range.
Although the full algorithm requires the initial solution of a travelling salesman problem in addition to the solution of (15), we do not include the runtimes for the travelling salesman problem in Figure 5. It is well known that an exact solution depends exponentially on the number of vertices. However, there are many algorithms with lower complexity (including both stochastic and heuristic algorithms) that can be used to obtain near-optimal tours.
**Figure 2. **Drone path homotopy solutions for 1 different test scenarios. The cluster head positions are indicated by X’s. The different colored lines are drone path solutions for different values of maximum drone range, with the drone start and end points as indicated.**Figure 3. **(<b>a</b>) Path defect (defined as the length of a tour of the cluster heads minus the length of the drone path) plotted as a function of number of iterations in the numerical solution of the matrix differential Equation (25). (<b>b</b>) Total energy expended by sensors for a single tour, as a function of iteration number. Both graphs show results for 2000 iterations for the 12 test scenarios shown in Figure 2.**Figure 5. **(<b>a</b>) Run times for the Runge-Kutta ODE for the 12 scenarios shown in Figure 2, plotted as a function of the number of cluster heads (equal to the number of path vertices), for different drone ranges. The drone range for each scenario is specified as a fraction of the length of the travelling salesman path joining the cluster heads. The four curves correspond to drone ranges equal to 20%, 40%, 60%, and 80% of the travelling salesman path (longer drone ranges take less time to compute). (<b>b</b>) Number of iterations (with step size <i>h</i> = 0.1) required for the Runge-Kutta algorithm to compute solutions with the specified drone ranges. (<b>c</b>) Execution time per iteration for the same set of solutions as the other two graphs. All simulations were performed using Google Colab.

The solution described above for finding optimal drone information-harvesting paths is locally and globally optimal for sufficiently long drone ranges. The numerical solution algorithm executes quickly enough that it can be implemented in real-time, and execution time grows slowly with the size of the system. The solution can be used either to optimize total transmit power consumption and maximum power consumption by cluster heads. However, there are limitations in that the speed of execution slows considerably when the drone range decreases below a certain point (i.e., when path vertices begin to merge), and global optimality for comparatively short drone ranges is uncertain.

The following future work is proposed in order to improve upon this research.

- The proposed algorithm supposes that the cluster head positions are predetermined. Alternatively, it is possible to use the algorithm as a component in a more comprehensive algorithm that does co-optimization of cluster head positions and drone path in systems where alternative cluster heads are a possibility.
- Equation (5) does not take into account various environmental factors such as obstacles or wind speed. It is also not robust to possible sensor node failures. The equation would need to be elaborated to include terms that reflect these factors. Also, the equations are limited to optimization criteria
*O*_{1}and*O*_{2}. Different optimization criteria can be accommodated by modifying the Equation (1) for the function $$f(\vec{u},\vec{v})$$, which then requires recalculation of the partial derivatives $$\frac{\partial f}{\partial u_{j}}$$ and $$\frac{\partial f}{\partial v_{j}}$$ which appear in Equations (9) and following. - The numerical homotopy solution code has not been fully optimized to decrease execution times. In particular, existing solver packages and/or variable step-size solution algorithms may be explored. In addition, we have remarked that the algorithms slow down after drone path vertex mergers. Future work may explore ways to avoid this slowdown. One possibility is to modify the algorithm so that when path vertices merge, the two associated cluster heads may be replaced by a single virtual cluster head that produces the same power loss. Then, the homotopy solution can be continued with vectors $$\vec{u}$$, $$\vec{v}$$ that each have one less component.
- The algorithm can be modified to accommodate moving cluster heads, by expressing $$\vec{x}$$,$$\vec{y}$$,$$\vec{u}$$, and $$\vec{v}$$ as functions of time
*t*, and then inverting the time dependence of $$\vec{u}$$ and $$\vec{v}$$ to obtain $$\vec{x}$$ and $$\vec{y}$$ as functions of $$\vec{u}$$ and $$\vec{v}$$. Then the same homotopy approach can be used with modified equations for the derivatives of $$\left\{a_{j}\right\}_{j=1...J}$$ and $$\{b\}_{j=1...J}$$ in (13) and following. - Further explorations of the question of global optimality may be pursued. As the proof in Appendix B shows, any globally optimal solution must be part of a homotopy that includes some ordering of the cluster head points. It follows that in some cases, better solutions may be found by computing homotopies for different orderings of the cluster heads.

```latexu_{j},v_{j}=j^{th}\mathrm{turning~point~of~drone~j=1~...J}\\a_{j}=u_{j}-x_{j}\\b_{j}=v_{j}-y_{j}\\A_{j}=a_{j}^{2}+b_{j}^{2}\\m_{j}=u_{j}-u_{j+1}\\n_{j}=v_{j}-v_{j+1}\\M_{j}=m_{j}^{2}+n_{j}^{2}\\H_{j}=M_{j}^{3/2}\\q=\frac{p}{2}-1\\r=1/2```

```latex\begin{gathered}S_{j1}=\lambda\frac{M_{j-1}-m_{j-1}^{2}}{H_{j-1}} \\S_{j2}=-\lambda\frac{m_{j-1}n_{j-1}}{H_{j-1}} \\S_{j3}=2pqa_{j}^{2}A_{j}^{q-1}+pA_{j}^{q-1}-\lambda\frac{H_{j}\Big(M_{j-1}-m_{j-1}^{2}\Big)+H_{j-1}(M_{j}-m_{j}^{2})}{H_{j-1}H_{j}} \\S_{j4}=2pqa_{j}b_{j}A_{j}^{q-1}+\lambda\frac{m_{j-1}n_{j-1}H_{j}+m_{j}n_{j}H_{j-1}}{H_{j-1}H_{j}} \\S_{j5}=\lambda\frac{M_{j}-m_{j}^{2}}{H_{j}} \\S_{j6}=-\lambda\frac{m_{j}n_{j}}{H_{j}} \end{gathered}```

```latex\begin{gathered}w_{j}= \frac{-m_{j-1}\sqrt{M_{j}}+m_{j}\sqrt{M_{j-1}}}{\sqrt{M_{j-1}M_{j}}} \\t_{j1}=-\lambda\frac{m_{j-1}n_{j-1}}{H_{j-1}} \\t_{j2}=\lambda\frac{M_{j-1}-n_{j-1}^{2}}{H_{j-1}} \\t_{j3}=2pqa_{j}b_{j}A_{j}^{q-1}+\lambda\frac{m_{j-1}n_{j-1}H_{j}+m_{j}n_{j}H_{j-1}}{H_{j-1}H_{j}} \\t_{j4}=2pqb_{j}^{2}A_{j}^{q-1}+pA_{j}^{q}-\lambda\frac{H_{j}\big(M_{j-1}-n_{j-1}^{2}\big)+H_{j-1}(M_{j}-n_{j}^{2})}{H_{j-1}H_{j}} \\t_{j5}=-\lambda\frac{m_{j}n_{j}}{H_{j}} \\t_{j6}=\lambda\frac{M_{j}-n_{j}^{2}}{H_{j}} \\z_{j}=\frac{-n_{j-1}\sqrt{M_{j}}+n_{j}\sqrt{M_{j-1}}}{\sqrt{M_{j-1}M_{j}}} \end{gathered}```

```latex\begin{gathered}s_{j1}\frac{du_{j-1}}{ds}+s_{j2}\frac{dv_{j-1}}{ds}+s_{j3}\frac{du_{j}}{ds}+s_{j4}\frac{dv_{j}}{ds}+s_{j5}\frac{du_{j+1}}{ds}+s_{j6}\frac{dv_{j+1}}{ds}-c1\frac{d\lambda}{ds}=0 \\t_{j1}\frac{du_{j-1}}{ds}+t_{j2}\frac{dv_{j-1}}{ds}+t_{j3}\frac{du_{j}}{ds}+t_{j4}\frac{dv_{j}}{ds}+t_{j5}\frac{du_{j+1}}{ds}+t_{j6}\frac{dv_{j+1}}{ds}-c2\frac{d\lambda}{ds}=0 \\\frac{dg}{ds}=-1\Rightarrow\sum_{j=1}^{J}\left(\frac{\partial g}{\partial u_{j}}\frac{du_{j}}{ds}+\frac{\partial g}{\partial u_{j}}\frac{dv_{j}}{ds}\right)=-1 \end{gathered}```

```latexKD=C```

In this appendix, we give a more extended presentation of the argument outlined in Section 2.8, which asserts that the homotopy solution found in Sections 2.5–2.7 is a globally optimal solution of (5) for drone ranges that are less than but close to the travelling salesman tour length. A completely rigorous mathematical argument would be tedious to present, but a step-by-step outline is as follows.
Suppose first we restrict to drone path solutions such that (*u*_{j},*v*_{j}) is in the same order of (*x*_{j},*y*_{j} ), *j* = 1,…*J* where (*x*_{j},*y*_{j}) is the travelling salesman order of cluster heads. Suppose also that $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is a globally optimal solution for the drone path satisfying the constraint $$g\big(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\big)$$ = *L*. Any globally optimal solution of (5) is also locally optimal: so $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is also locally optimal. Then $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ is part of a homotopy of solutions using the same construction we showed in Sections 2.5–2.7. The homotopy consists of locally optimal solutions $$\left(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\right)$$ satisfying $$g\big(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\big)$$ = *s*, where *s* can take values in a closed interval containing *L*. Define the function $$f_{(ts)}(s)=f\big(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\big)$$. The function *f*_{(ts)} decreases strictly as s increases, because if the drone path is lengthened, it is always possible to move closer to the cluster heads; and as long as *f*_{(ts)} (*s*) is positive, it is always possible to decrease *f*_{I} by increasing the path length. It follows that the minimum value of *f*_{(ts)} (*s*) on the homotopy cannot be positive, so $$\left(\vec{u}^{(ts)}(L),\vec{v}^{(ts)}(L)\right)$$ must be connected by a homotopy to ( $$\vec{x},\vec{y}$$) where the components of $$\vec{x}$$ and $$\vec{y}$$ are in travelling salesman order. So the solution in this homotopy whose length is equal to the travelling salesman tour length of cluster heads (denoted by $$L^{(ts)}$$) corresponds to a value of $$f_{(ts)}\big(L^{(ts)}\big)$$ = 0.
Now, we consider solutions where (*u*_{j},*v*_{j} ) receives the information from $$(x_{\sigma(j)},y_{\sigma(j)})$$ where *σ* is a permutation of (1,…*J*). By similar arguments as in the previous paragraph, any locally optimal solution corresponding to a path length *L* is part of a homotopy $$\left(\vec{u}^{(\sigma)}(s),\vec{v}^{(\sigma)}(s)\right)$$ with associated strictly decreasing function $$f_{\sigma}(s):=f\big(\vec{u}_{\sigma}(s),\vec{v}_{\sigma}(s)\big)$$, which includes a solution $$\left(\vec{u}^{(\sigma)}\big(L^{(\sigma)}\big),\vec{v}^{(\sigma)}\big(L^{(\sigma)}\big)\right)$$ for path length $$L^{(\sigma)}>L$$ such that $$f_{\sigma}\big(L^{(\sigma)}\big)=0$$. But this implies that $$\left(\vec{u}^{(\sigma)}\big(L^{(\sigma)}\big)_{j^{\prime}},\vec{v}^{(\sigma)}\big(L^{(\sigma)}\big)_{j}\right)=\big(x_{\sigma(j)},y_{\sigma(j)}\big)$$,*j* = 1,…*J*, which in turn implies that $$L^{(\sigma)}$$ is the length of the tour of the points $$\left\{\left(x_{j},y_{j}\right)\right\}_{j=1...J}$$ in the order given by *σ*. This means that $$L^{(\sigma)}\geq L^{(ts)}$$, and $$L^{(\sigma)}=L^{(ts)}$$ if and only if *σ* gives a travelling salesman ordering of the nodes in $$\vec{x},\vec{y}$$. Since the function *f*_{σ}(*s*) is strictly decreasing, it follows that $$f_\sigma(L^{(ts)})$$ > $$f_{opt}(L^{(ts)}$$ for all permutations σ for which $$(x_{\sigma(j)},y_{\sigma(j)})$$ is not a travelling salesman permutation. Let $$\tilde{f}:=\min_{\sigma\neq I}f_\sigma $$, where the minimum is taken over all non-travelling salesman permutations. Then we also have $$\tilde{f}\big(L^{(ts)}\big)>f_{(ts)}(L^{(ts)})$$. It follows by continuity that there is an $$\tilde{L}$$ with 0 < $$\tilde{L}$$ < $$L^{(ts)}$$ such that $$\tilde{f}(s)>f_{(ts)}(s)$$ for $$\tilde{L}\leq s\leq L$$. In other words, the solution $$\begin{pmatrix}\vec{u}^{(I)}(s),\vec{v}^{(I)}(s)\end{pmatrix}$$ is a local optimum such that $$f\left(\vec{u}^{(I)}(s),\vec{v}^{(I)}(s)\right)$$ is less than the value of f for any other local optimum. It follows that $$\left(\vec{u}^{(ts)}(s),\vec{v}^{(ts)}(s)\right)$$ is a global optimum for $$\tilde{L}$$ < s $$\leq L^{(ts)}$$.
Note that this proof does not give a practical, constructive method for finding $$\tilde{L}$$ it only shows that it exists. However, the proof does indicate that any global optimum will be part of some homotopy that includes the points {(*x*_{j},*y*_{j})},*j* = 1…*J* in some order. This fact indicates that other candidate global optimal solutions can be found by creating homotopies starting from other (non-travelling salesman) tours of the cluster heads points.

The authors wish to thank Dr. Aristide Tsemo for his thorough review of the equations in Section 2.6, which resulted in several corrections. We also wish to thank the reviewers of this paper, who made several valuable suggestions for improvements.

Conceptualization, R.G. and C.T.; Methodology, R.G. and C.T.; Software, R.G.; Validation, R.G. and C.T.; Formal Analysis, R.G. and C.T.; Investigation, R.G. and C.T.; Writing—Original Draft Preparation, R.G. and C.T.; Writing—Review & Editing, R.G. and C.T.; Visualization, R.G. and C.T.; Supervision, C.T.

Not applicable.

Not applicable.

This research received no external funding.

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

1.

Nguyen MT, Nguyen CV, Do HT, Hua HT, Tran TA, Nguyen AD, et al. UAV-assisted data collection in wireless sensor networks: A comprehensive survey.* Electronics*** 2021**,* 10,* 2603. [Google Scholar]

2.

Wei Z, Zhu M, Zhang N, Wang L, Zou Y, Meng Z, et al. UAV-assisted data collection for internet of things: A survey.* IEEE Int. Things J.*** 2022**,* 9,* 15460–15483. [Google Scholar]

3.

Memos VA, Psannis KE. UAV-based smart surveillance system over a wireless sensor network.* IEEE Commun. Stand. Mag.*** 2021**,* 5,* 68–73. [Google Scholar]

4.

Qadir Z, Zafar MH, Moosavi SKR, Le KN, Tam VW. Optimizing UAV path for disaster management in smart cities using metaheuristic algorithms. In *Computational Intelligence for Unmanned Aerial Vehicles Communication Networks*; Springer International Publishing: Cham, Switzerland, 2022; pp. 225–244.

5.

Qadir Z, Zafar MH, Moosavi SKR, Le KN, Mahmud MP. Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment.* IEEE Int. Things J. *** 2021**,* 9,* 12505–12514. [Google Scholar]

6.

Dac-Tu H, Esten IG, Tor AJ. Heuristic algorithm and cooperative relay for energy efficient data collection with a UAV and WSN. In Proceedings of the 2013 International Conference on Computing, Management and Telecommunications (ComManTel), Ho Chi Minh City, Vietnam, 21–24 January 2013, pp. 346–351.

7.

Liu S, Wei Z, Guo Z, Yuan X, Feng Z, Performance analysis of UAVs assisted data collection in wireless sensor network. In Proceedings of the 2018 IEEE 87th Vehicular Technology Conference (VTC Spring), Porto, Portugal, 3–6 June 2018, pp. 1–5.

8.

Gong J, Chang TH, Shen C, Chen X. Flight time minimization of UAV for data collection over wireless sensor networks.* IEEE J. Sel. Areas Commun. *** 2018**,* 36,* 1942–1954. [Google Scholar]

9.

Skiadopoulos K, Giannakis K, Tsipis A, Oikonomou K. Impact of drone route geometry on information collection in wireless sensor networks.* Ad. Hoc. Netw. *** 2020**,* 106,* 102220. [Google Scholar]

10.

Ho DT, Grøtli EI, Sujit PB, Johansen TA, De Sousa JB.Performance evaluation of cooperative relay and Particle Swarm Optimization path planning for UAV and wireless sensor network. In Proceedings of the 2013 IEEE Globecom Workshops (GC Wkshps), Atlanta, GA, USA, 9–13 December 2013, pp. 1403–1408.

11.

Zhu M, Wei Z, Qiu C, Jiang W, Wu H, Feng Z. Joint data collection and sensor positioning in multi-UAV-assisted wireless sensor network.* IEEE Sens. J.*** 2023**,* 23,* 23664–23675. [Google Scholar]

Ganapathy R, Thron C. Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network. *Drones and Autonomous Vehicles* **2024**, *1*, 10007. https://doi.org/10.35534/dav.2024.10007

Ganapathy R, Thron C. Optimized Real Time Single-Drone Path Planning for Harvesting Information from a Wireless Sensor Network. *Drones and Autonomous Vehicles*. 2024; 1(3):10007. https://doi.org/10.35534/dav.2024.10007

TOP