# A UAV-Enabled Time-Sensitive Data Collection Scheme for Grassland Monitoring
Edge Networks

Dongbin Jiao12, Zihao Wang1, Wen Fan1, Weibo Yang5, Peng Yang34, , Zhanhuan
Shang6, and Shi Yan1  1School of Information Science and Engineering, Lanzhou
University, Lanzhou, 730000, P. R. China (e-mail: {jiaodb, wangzihao2020,
fanw20, yanshi}@lzu.edu.cn).  2Key Laboratory of Tourism Information Fusion
Processing and Data Ownership Protection, Ministry of Culture and Tourism,
Lanzhou University, Lanzhou, 730000, P. R. China.  3Guangdong Provincial Key
Laboratory of Brain-inspired Intelligent Computation, Department of Computer
Science and Engineering, Southern University of Science and Technology,
Shenzhen, 518055, P. R. China (e-mail: yangp@sustech.edu.cn).  4Department of
Statistics and Data Science, Southern University of Science and Technology,
Shenzhen 518055, P. R. China.  5School of Automobile, Chang’an University,
Xi’an, 710064, P. R. China (e-mail: wbyang@chd.edu.cn).  6State Key Laboratory
of Grassland Agro-Ecosystem, College of Ecology, Lanzhou University, Lanzhou,
730000, P. R. China (e-mail: shangzhh@lzu.edu.cn).

###### Abstract

Grassland monitoring is essential for the sustainable development of grassland
resources. Traditional Internet of Things (IoT) devices generate critical
ecological data, making data loss unacceptable, but the harsh environment
complicates data collection. Unmanned Aerial Vehicle (UAV) and mobile edge
computing (MEC) offer efficient data collection solutions, enhancing
performance on resource-limited mobile devices. In this context, this paper is
the first to investigate a UAV-enabled time-sensitive data collection problem
(TSDCMP) within grassland monitoring edge networks (GMENs). Unlike many
existing data collection scenarios, this problem has three key challenges.
First, the total amount of data collected depends significantly on the data
collection duration and arrival time of UAV at each access point (AP). Second,
the volume of data at different APs varies among regions due to differences in
monitoring objects and vegetation coverage. Third, the service requests time
and locations from APs are often not adjacent topologically. To address these
issues, We formulate the TSDCMP for UAV-enabled GMENs as a mixed-integer
programming model in a single trip. This model considers constraints such as
the limited energy of UAV, the coupled routing and time scheduling, and the
state of APs and UAV arrival time. Subsequently, we propose a novel
cooperative heuristic algorithm based on temporal-spatial correlations (CHTSC)
that integrates a modified dynamic programming (MDP) into an iterated local
search to solve the TSDCMP for UAV-enabled GMENs. This approach fully takes
into account the temporal and spatial relationships between consecutive
service requests from APs. Systematic simulation studies demonstrate that the
mixed-integer programming model effectively represents the TSDCMP within UAV-
enabled GMENs. Moreover, the proposed CHTSC algorithm outperforms two superior
algorithms across twelve different scale instances.

###### Index Terms:

Unmanned Aerial Vehicle (UAV), grassland monitoring, time-sensitive, data
collection, temporal-spatial correlations, dynamic programming (DP).

##  I Introduction

Grasslands are among the largest terrestrial biomes, covering more than $25\%$
of the terrestrial earth’s surface, and serve as significant hotspots of
biodiversity in various regions [1]. These ecosystems have very high
conservation value and provide essential ecosystem services, including food
and fodder, water regulation and supply, erosion control, pollinator
promotion, and carbon sequestration [2]. However, grassland biodiversity and
the ecosystem services they offer are severely threatened, making their
conservation and restoration top priorities [3]. Grassland monitoring is
crucial for the scientific utilization and rational development of grassland
resource, as well as for maintaining ecological balance, which is central to
effective grassland management [4].

Internet of Things (IoT), as a crucial next-generation information technology,
has been widely applied to various aspects of grassland monitoring. It plays
an irreplaceable role in obtaining meteorological, soil, and biological data,
studying ecological change patterns, evaluating ecological quality, and
maintaining the sustainable development of grassland ecosystems [5].
Nevertheless, unlike other application areas of IoT, grassland IoT demands
higher requirements for monitoring depth, scope, and frequency. These devices
are primarily used for fine online monitoring of grassland respiration, snow
thickness, desertification, CO_2 content, light, gas exchange, leaf area, and
microorganisms. Consequently, they generate vast amounts of monitoring data
which are of great significance for exploring the ecological characteristics
of grasslands over time, making it imperative to avoid any data loss.
Moreover, the complex and harsh ecological environment of grasslands, the
extensive monitoring range, and the lack of information technology facilities
pose significant challenges in deploying IoT on grasslands. These factors
result in high data collection costs, significant network transmission delays,
and substantial equipment energy consumption. Therefore, designing a feasible
network and collecting extensive grassland monitoring data have become
significant challenges.

Fortunately, Unmanned Aerial Vehicle (UAV) offers new opportunities for data
collection in IoT networks due to their high agility, flexibility, and low
cost [6]. Moreover, mobile edge computing (MEC) has emerged as a widely
studied technology in recent years, demonstrating excellent performance in
computation-intensive and latency-critical applications on resource-limited
mobile devices [7]. Inspired by these advancements, this work employs a three-
tier network architecture consisting of sensor nodes, access points (APs), and
a UAV to collect grassland monitoring data. We consider a scenario in which a
UAV with limited energy is periodically dispatched to collect monitoring data
from each AP only once in the monitored grassland area. The UAV carrying the
collected monitoring data must return to the base station before depleting its
energy.

Due to the heterogeneous functionality of sensors used for grassland
monitoring, the sensor nodes may collect varying amounts of data at each AP.
This can result in data overflow at certain APs where the collected data
exceeds their capacity. What is more, data collection requests are sent to the
UAV from APs distributed across various locations and at diverse time
intervals as runtime progresses. A UAV with limited energy may not be able to
collect all data from each AP sequentially during a single trip within a
grassland monitoring region. Therefore, it becomes crucial to determine which
APs’ data should be prioritized for collection by the UAV? Questions arise
about the optimal order and duration for data collection at each AP to
maximize the total volume of collected data while minimizing or avoiding data
overflow. In other words, the primary question is how the UAV incorporates
both data collection deadlines (i.e., data overflow time) and diverse data
collection locations into its decision-making process.

Motivated by these issues, this paper investigates the time-sensitive data
collection maximization problem (TSDCMP) within UAV-enabled grassland
monitoring edge networks (GMENs). To the best of our knowledge, no existing
work explores such models specifically tailored for UAV-enabled GMENs.
Consequently, we formulate the TSDCMP in the context of UAV-enabled GMENs as a
mixed-integer programming model. This model accounts for constrains including
the limited energy of UAV, the coupled routing and time scheduling, and the
state of APs and UAV arrival time. Further analysis of the problem reveals
several key features. Firstly, the total amount of data collected is highly
dependent on both the data collection duration and the arrival time at each
AP. Secondly, the volume of data at each AP typically varies among regions due
to differences in monitoring objects and vegetation coverage. Thirdly, the
time and location of service requests from two APs are often not adjacent
topologically.

Taking the above features and challenges into consideration, this work
proposes a novel cooperative heuristic algorithm based on temporal-spatial
correlations (CHTSC) to solve the TSDCMP for UAV-enabled GMENs. The core idea
of CHTSC algorithm is to jointly optimize the flight trajectory, arrival time,
and data collection duration for the UAV at each AP. This approach fully
considers the temporal and spatial relationships between consecutive service
requests from APs. The overarching goal is to minimize the occurrence of data
overflow while simultaneously maximizing the volume of data collected from
APs, all within the realistic constraints.

The main contributions of this work are summarized as follows:

  1. 1.

We first present the TSDCMP within UAV-enabled GMENs and then formulate a
mixed-integer programming model for the TSDCMP under realistic constraints.

  2. 2.

We propose a novel CHTSC algorithm to solve the TSDCMP for UAV-enabled GMENs,
which fully considers the temporal and spatial relationships between
consecutive service requests from APs.

  3. 3.

Simulation studies demonstrate that the mixed-integer programming model
effectively represents the TSDCMP within UAV-enabled GMENs. Moreover, the
proposed CHTSC algorithm outperforms two superior algorithms across twelve
different scale instances.

The rest of this work is structured as follows. Section II reviews related
work on the UAV-enabled time-sensitive data collection and relevant solutions.
Section III presents the system model and problem formulation. Section IV
details the proposed algorithm for optimizing data collection. Section V
discusses the experimental setup and results. Finally, Section VI concludes
this paper and suggests directions for future research.

##  II Related Work

This work focuses on two aspects: the modeling of UAV-enabled time-sensitive
data collection for grassland monitoring and the development of a CHTSC.
Therefore, the related literature is reviewed from the these perspectives.

In recent year, UAVs have increasingly been utilized for time-sensitive data
collection in various practical scenarios. Samir  _et al._ [8] investigate the
maximizing the number of served IoT devices by jointly optimizing the
trajectory of a UAV and the radio resource allocation under a data upload
deadline. In addition, Zhan  _et al._ [9] design a novel framework for multi-
UAV-enabled mobile-edge-computing (MEC) to provide flexible computational
assistance to IoT devices with strict deadlines. Wang  _et al._ [10] address a
priority-oriented trajectory planning problem for a UAV-aided time-sensitive
heterogeneous IoT network, providing a solution that ensures the network’s
latency tolerance within a specific time period. Liu  _et al._ [11] tackle the
UAV-enabled data collection problem to ensure high information freshness in
wireless sensor networks. The information freshness is measured by the age of
information (AoI) for each sensor node. Tran  _et al._ [12] propose a time-
sensitive data collection scheme using a UAV relay-assisted IoT model. This
scheme considers the latency requirement for both uplink and downlink channels
to enhance the freshness of information. Liu  _et al._ [13] investigate the
UAV trajectory planning problem in a UAV-enabled environmental monitoring
system, focusing on the AoI limitations of data in monitoring areas. Zeng  _et
al._ [14] propose a relay-assisted UAV data collection method that takes into
account the freshness of collected data in the large-scale disaster area. Cao
_et al._ [15] consider a priority-oriented UAV-aided data collection problem
in a time-sensitive IoT network with movable sensor nodes. Liu  _et al._ [16]
propose a multi-UAV assisted wireless power transmission space-air-ground
power IoT framework for data acquisition and computation, aiming to minimizing
the average AoI of power devices. Moreover, Messaoudi  _et al._ [6] provide a
comprehensive review of the scenarios and key technologies for UAV-assisted
data collection in IoT applications and discuss UAV-based time-sensitive data
collection. However, these works overlook both the spatial and temporal data
correlations. This oversight results in excessive energy consumption by UAV
due to round-trip data collection and causes data overflow at sensor nodes due
to untimely collection.

Meanwhile, relatively little work focuses on UAV data collection based on
temporal and spatial correlations. Li  _et al._ [17] propose a blockchain-
enhanced spatiotemporal data aggregation model to reduce data redundancy in
UAV-assisted wireless sensor networks. In this model, the UAV must collect
data to recover the original raw data in each cluster. However, this approach
may not be feasible and can lead to data overflow in some clusters due to the
UAV’s limited energy, as there may not be sufficient time for collection.
Moreover, Guo  _et al._ [18] introduce a fine-grained spatiotemporal model to
minimize redundant sensing data transmissions in energy-harvesting sensor
networks. Fattoum  _et al._ [19] propose an adaptive sampling rate algorithm
that uses the spatiotemporal correlation of sampled data and the residual
energy of sensor nodes to reduce data acquisition in periodic wireless sensor
networks. Xie  _et al._ [20] study a geographical correlation-based RF-data
collection protocol. Xu  _et al._ [21] investigate the maximizing accumulative
utility for collected data problem by determining an optimal data collection
trajectory for a UAV with limited energy. This accumulative utility evaluates
the quality of data, which is spatiotemporally correlated and gathered from
various clusters. Although references [18, 19, 20, 21] examine the temporal
and spatial correlations of data, they do not consider the time-sensitive
aspects of UAV data collection, and also difficult to extend these methods to
our work.

Furthermore, team orienteering problem (TOP) with time-varying profit [22]
presents another significant research challenge. Yu  _et al._ [23] study a
variant of TOP with service and arrival-time-varying profit. They further
extend this work to a robust variant of TOP with decreasing profits, assuming
uncertain service times at customers [24]. These studies assume that the
accumulated data value decrease linearly with arrival time. Wan  _et al._ [25]
propose an attention-based deep reinforcement learning enabled multi-UAV
scheduling system for disaster data collection with time-varying data value,
where UAVs act as temporary and mobile relays. Subsequently, they also
introduce a hybrid heuristics-based multi-UAV route planning method for time-
dependent IoT data collection [26]. However, the aforementioned work do not
account for the specific factors affecting grassland monitoring scenarios,
making it challenging to directly apply these methods to address the grassland
monitoring data collection problem.

##  III System Model and Problem Formulation

In this section, we first describe the system models, which include the GMENs
model, UAV time-sensitive data collection model, and UAV energy consumption
model. Subsequently, we formulate the mathematical programming model for
TSDCMP within UAV-enabled GMENs. The notations of key parameters used in this
work are listed in Table I.

TABLE I: MEANINGS OF THE NOTATIONS Notation |  Meaning
---|---
$N$ |  The number of APs.
$T$ |  The maximum mission duration of UAV.
$E_{max}$ |  The battery capacity of UAV.
$t_{i}$ |  The arrival time at AP $i$.
$d_{ij}$ |  The distance between APs $v_{i}$ and $v_{j}$.
$T^{c}_{i}$ |  The amount of data collection time spent at AP $i$.
$T^{f}_{ij}$ |  The flight duration of UAV between any two adjacent APs $i$ and $j$.
$T^{o}_{i}$ |  The data overflow time of AP $i$.
$T^{h}_{i}$ |  The hovering duration of UAV at APs $i$.
$\tilde{H}$ |  The height between the UAV and the AP.
$\mathcal{L}$ |  The locations of these APs.
$\mathrm{v}$ |  The velocity of UAV.
$\mathcal{T}$ |  The set of time slots.
$\mathcal{T}^{f}$ |  The set of time slots for the UAV¡¯s flight state.
$\mathcal{T}^{c}$ |  The set of time slots for the UAV¡¯s data collection state.
$R$ |  The achievable transmission rate between AP and UAV follows the free-space path loss model.
$D_{i}(t)$ |  The data volume of AP $i$ in time slot $t$.
$C_{i}$ |  The total amount of data collected from AP $i$ by the UAV at the location $l_{i}$ during the data collection duration $T^{c}_{i}$.
$D_{max}$ |  The maximum capacity of each AP.
$D_{th}$ |  The threshold of each AP that requires data collection.
$\alpha^{s}_{i}(t)$ |  The self-growth rate of data for AP $i$ in time slot $t$.
$\alpha^{r}_{i}(t)$ |  The real-growth rate of data for AP $i$ in time slot $t$.
$O$ |  The total amount of data overflowed by the UAV during the data collection tour.
$C$ |  The total amount of data collected by the UAV during the data collection tour.

###  III-A Grassland Monitoring Edge Networks Model

In this work, the GMENS utilize a three-tier network architecture consisting
of sensor nodes, APs, and a UAV to collect grassland monitoring data, as
illustrated in Fig. 1. The heterogeneous sensors are deployed across the
grassland region, constantly gathering data on various aspects of vegetation
growth, including meteorology, soil conditions, microbe activity, soil
respiration, carbon dioxide levels, and leaf gas exchange [27]. Each
homogeneous AP equipped with a limited buffer and an edge sever processes the
raw-data collected from the nearby sensor nodes and stores the processed
metadata. Due to the continuous monitoring performed by the sensors, APs need
to store substantial volume of data. When the data volume at an AP reaches a
certain threshold, it sends a data collection request to the UAV. The UAV with
limited energy is periodically dispatched to collect data from $N$ APs within
the monitored grassland area. It is assumed that the UAV’s storage capacity is
sufficient to meet the data collection requirements. The UAV can access
information from each AP, including location, data volume, data collection
rate, and data collection status, at any time and from any location. The base
station handles various tasks, such as dispatching the UAV, charging its
batteries, and processing the collected monitoring data.

$\begin{array}[]{l}\includegraphics[width=202.35622pt]{Data-Collection-
UAV.pdf}\\\ \end{array}$

Figure 1: Three-tier network architecture for time-sensitive data collection
by a UAV in GMENs.

Let $\mathcal{N}_{a}=\\{v_{1},\ldots,v_{N}\\}$ denote the set of APs. The
locations of these APs are represented as
$\mathcal{L}=\\{l_{i}=(x_{i},y_{i},0)|1\leq i\leq N\\}$. Due to the uneven
terrain of the grassland, the altitude of the UAV relative to the ground is
fixed at constant for safety reasons. The UAV collects data from each AP only
once and subsequently delivers it to the data center for further processing
upon returning to the base station $v_{0}$ before exhausting its energy.
Therefore, the UAV’s trajectory for data collection must form a closed tour.
The GMENS can be described as a complete directed weighted graph
$G=(\mathcal{N},A)$, where $\mathcal{N}=\\{v_{0}\\}\cup\mathcal{N}_{a}$
represents the set comprising all APs and the base station $v_{0}$, and
$A=\\{(v_{i},v_{j})|v_{i},v_{j}\in\mathcal{N},i\neq j\\}$ denotes the set of
the paths connecting any two APs. Each arc $a\in A,a=(v_{i},v_{j})$ has an
associated non-negative weight value $d_{ij}$ that indicates the distance
between APs $v_{i}$ and $v_{j}$, i.e., $d_{ij}=\parallel
l_{i}-l_{j}\parallel$. For convenience, we interchangeably refer to AP $v_{i}$
as AP $i$ or $i$ in the remainder of this paper.

The maximum mission duration $T$ of UAV is divided into equal time slots, with
each time slot having a length of $\tau$. We assume that $\tau$ is
sufficiently small so that the UAV’s location change within $\tau$ is
negligible. Let $\mathcal{T}=\\{t|1\leq t\leq T\\}$ denote the set of time
slots.

To fully utilize solar energy for power supply, the height of APs is typically
set higher than the surface of grassland vegetation. Consequently, the
wireless channel between the UAV and AP is dominated by the line of sight
(LoS) link. In addition, considering the data collection rates and the energy
consumption associated with transmission distance, the data can be collected
from an AP only when the UAV hovers directly over it. This operational mode is
achieved by following the fly-hover-communication protocol [28]. The
achievable transmission rate $R$ between AP and UAV follows the free-space
path loss model. It can be defined by

$\small R=B\log_{2}(1+\frac{p\beta}{\sigma^{2}\tilde{H}^{2}}),$ (1)

where $B$ presents the channel bandwidth, $p$ is the transmit power of AP for
uploading data link, $\beta$ denotes the channel power gain when the reference
distance is set as 1 m, $\sigma^{2}$ denotes the noise power, and $\tilde{H}$
is the height between the UAV and the AP, where $\tilde{H}$ is greater than
the height from the UAV to the ground.

###  III-B Time-Sensitive Data Collection Model

To reduce the energy consumption of the UAV flying back and forth, we assume
that the UAV collects data from each AP only once. The data collection
duration of UAV at each AP can be expressed as a set
$\mathcal{T}^{c}=\\{T^{c}_{i}|T^{c}_{i}\geq 0,l_{i}\in\mathcal{L}\\}$ in term
of time slots. Meanwhile, the flight duration of UAV between any two adjacent
APs $i$ and $j$ can be expressed as a set
$\mathcal{T}^{f}=\\{T^{f}_{ij}|T^{f}_{ij}\geq 0,l_{i},l_{j}\in\mathcal{L}\\}$
in term of time slots.

Assume that the UAV keeps a fixed velocity $\mathrm{v}$. Thus the flight
duration of UAV between any two adjacent APs $i$ and $j$ can be calculated by

$\small T^{f}_{ij}=\frac{\parallel l_{i}-l_{j}\parallel}{\mathrm{v}\tau}.$ (2)

To ensure that the total duration of data collection and flight for the UAV
does not exceed $T$ time slots, we impose the following constraint:

$\small\sum_{T^{c}_{i}\in\mathcal{T}^{c}}T^{c}_{i}+\sum_{T^{f}_{ij}\in\mathcal{T}^{f}}T^{f}_{ij}\leq
T.$ (3)

The total amount of data collected from AP $i$ by the UAV at the location
$l_{i}$ during the data collection duration $T^{c}_{i}$ is denoted as $C_{i}$,
and it can be calculated as

$C_{i}=\tau T^{c}_{i}R.$ (4)

Note that the data volume of each AP dynamically grows over time during the
UAV’s data collection process. Let $\alpha^{s}_{i}(t)$ denote the self-growth
rate of data for AP $i$ in time slot $t$. This rate is constant for a given AP
but may vary between different APs due to the heterogeneity of the surrounding
sensor nodes. The real-growth rate $\alpha^{r}_{i}(t)$ of data in time slot
$t$ can be given as

$\small\alpha^{r}_{i}(t)=\begin{cases}\alpha^{s}_{i}(t),&\mbox{$t\in\mathcal{T}^{f}$}\\\
\alpha^{s}_{i}(t)-R,&\mbox{$t\in\mathcal{T}^{c}$},\end{cases}$ (5)

where $\mathcal{T}^{f}$ and $\mathcal{T}^{c}$ denote the set of time slots for
the UAV’s flight state and data collection state, respectively. Eq. (5) means
that the real-growth rate of data for AP $i$ is $\alpha^{s}_{i}(t)$ when the
UAV is in flight state, and otherwise it equals the difference between the
self-growth rate of data $\alpha^{s}_{i}(t)$ for AP $i$ and the data
collection rate $R$ by the UAV when it collects data from AP $i$. Therefore,
the data volume of AP $i$ in time slot $t$ can be calculated as follows:

$D_{i}(t)=D_{i}(t-1)+\alpha^{r}_{i}(t)\tau.$ (6)

Each AP operates continuously, and when the monitoring data collected from
neighbouring sensors exceeds its maximum capacity $D_{max}$, it results in
data overflow, leading to the loss of critical ecological information about
the grassland. Moreover, the varying volumes of data collected by each AP from
neighboring sensors result in different overflow time for each AP. To avoid
data overflow at APs with excessive data collected, the UAV must collect data
in real-time based on the service requests of each AP. Therefore, we set a
threshold $D_{th}$ for each AP. When the data volume of AP $i$ exceeds this
threshold, the AP will immediately send a data collection request to the UAV,
which will then schedule a response. Conversely, if the data volume of AP $i$
remains below the threshold $D_{th}$, data overflow will not occur.
Consequently, the volume of data collected by the UAV at AP $i$ satisfies

$D_{i}-D_{th}\leq C_{i}\leq D_{i}.$ (7)

$\begin{array}[]{l}\includegraphics[width=187.90244pt]{Real-Time-Data-
Collection-Path.pdf}\\\ \end{array}$

Figure 2: Example of real-time data collection by a UAV in GMENs: (a) The
shortest distance Hamiltonian cycle. (b) The path of real-time data
collection.

The real-time data collection scheme by the UAV is illustrated in Fig. 2. Fig.
2a depicts the shortest distance Hamiltonian cycle formed by seven APs based
on the distances between them. Fig. 2b shows the path of real-time data
collection in response to the data collection requests from the APs. The data
collection request signals sent from each AP are first stored in a response
queue $Q$ of the UAV in the order of their request service time, as shown in
Fig. 3. Assume that $Q$ is large enough to store all request signals. There is
an unequal time interval between two request signals before and after.
Subsequently, the UAV successively collects the monitoring data from each AP
based on the sequence in the queue $Q$.

$\begin{array}[]{l}\includegraphics[width=151.76744pt]{Queueing-Model.pdf}\\\
\end{array}$

Figure 3: Queueing model for real-time data collection scheme by a UAV.

Due to the different priorities of request service for each AP, the UAV should
collect data from each AP before it overflows. We define the data overflow
time of AP $i$ as $T^{o}_{i}$, which can be calculated as follows:

$\small T^{o}_{i}=\frac{D_{max}-D_{th}}{\alpha^{s}_{i}}.$ (8)

According to Eq. (2), the flight duration of UAV between any two APs $i$ and
$j$ in the response queue $Q$ is $T^{f}_{ij}$. Hence, for the UAV to collect
data from AP $j$ before its data overflows, the time of data collection at AP
$j$ must satisfy

$\small T^{c}_{j}=t+T^{c}_{i}+T^{f}_{ij}\leq T^{o}_{j}.$ (9)

Here the data collection delay is ignored compared to the time required for
data collection and flight.

###  III-C Energy Consumption Model for UAV

The rotary-wing UAVs typically operate for short durations due to the limited
energy capacity of their batteries. Moreover, the battery lifetime of a UAV is
influenced by several factors, including battery size, speed, weight, and
environmental conditions. In general, UAV energy consumption primarily
consists of two components: propulsion energy and communication energy.

Without loss of generality, the communication energy is negligible compared
with the propulsion energy and can be ignored in this work. For simplicity, we
also disregard the additional energy consumption caused by the UAV
acceleration or deceleration. This assumption is reasonable for the real-time
data collection scenario in this work since the UAV maneuvering time
constitutes only a small fraction of the total operation time. For propulsion
energy, the propulsion power consumption model for rotary-wing UAVs is adopted
in this work [28]. It is expressed as follows:

$\displaystyle P(\mathrm{v})=$ $\displaystyle
P_{0}\left(1+\frac{3\mathrm{v}^{2}}{U^{2}_{tip}}\right)+P_{i}\left(\sqrt{1+\frac{\mathrm{v}^{4}}{4\mathrm{v}^{4}_{0}}}-\frac{\mathrm{v}^{2}}{2\mathrm{v}^{2}_{0}}\right)^{\frac{1}{2}}$
(10) $\displaystyle+\frac{1}{2}d_{0}\rho sA\mathrm{v}^{3},$

where $P_{o}$ and $P_{i}$ are the blade profile power and induced power in
hovering status, respectively, $U^{2}_{tip}$ is the tip speed of the rotor
blade, $\mathrm{v}_{0}$ is the mean rotor induced speed in hover, and $d_{0}$
and $s$ are the fuselage drag ration and rotor solidity, respectively. Also,
$\rho$ and $A$ are the air density and rotor disc area, respectively.

For exposition purposes, the hovering duration and energy consumption at the
base station are assumed to be zero, namely $T_{0}=0$ and $E_{0}=0$. Thus, the
flight duration on the arc $(i,j)$ can be denoted as

$\displaystyle T_{ij}=$ $\displaystyle T^{h}_{i}+T^{f}_{ij}$ (11)
$\displaystyle=$ $\displaystyle\begin{cases}\frac{\parallel
l_{i}-l_{j}\parallel}{\mathrm{v}},&\mbox{$i=0,(i,j)\in A$}\\\
T^{c}_{i}+\frac{\parallel l_{i}-l_{j}\parallel}{\mathrm{v}},&\mbox{$i\neq
0,(i,j)\in A$},\end{cases}$

where the UAV hovering duration consists of the data collection duration
$\mathcal{T}^{c}$ and the hovering duration at the base station $T_{0}$, i.e.,
$\mathcal{T}^{h}=\mathcal{T}^{c}\cup\\{T_{0}\\}$.

Correspondingly, the energy consumption on the arc $(i,j)$ can be denoted as

$\displaystyle E_{ij}=$ $\displaystyle E^{h}_{i}+E^{f}_{ij}$ (12)
$\displaystyle=$ $\displaystyle\begin{cases}P^{f}\frac{\parallel
l_{i}-l_{j}\parallel}{\mathrm{v}},&\mbox{$i=0,(i,j)\in A$}\\\
P^{c}T^{c}_{i}+P^{f}\frac{\parallel
l_{i}-l_{j}\parallel}{\mathrm{v}},&\mbox{$i\neq 0,(i,j)\in A$},\end{cases}$

where $P^{c}$ denotes the power consumption of UAV during data collection in
hovering status with the velocity $\mathrm{v}=0$ and then
$P^{c}=P_{0}+P^{c}_{i}$.

###  III-D Problem Formation

The goal of the TSDCMP within UAV-enabled GMENs is to maximize the total
amount of data collected while minimizing the total amount of data overflowed
during the data collection tour within the limited energy capacity $E_{max}$.
To achieve this goal, the problem involves determining a single route for the
UAV that departs from and returns to the base station $v_{0}$. Furthermore, it
needs to allocate the appropriate duration of data collection at each visited
AP. In the following sections, we first detail the related notations necessary
to solve the problem, and then formulate a mixed-integer programming solution
for it.

Let $S(t_{i})$ denote the state of AP $i$ when the UAV arrives at it at time
$t_{i}$. There are two possible states, i.e., data collection state
$S(t_{i})=0$ and data overflow state $S(t_{i})=1$, satisfying

$\small S(t_{i})=\begin{cases}0,&\mbox{$t_{i}\leq T^{o}_{i}$}\\\
1,&\mbox{$t_{i}>T^{o}_{i}$},\end{cases}$ (13)

where $t_{i}$ and $T^{o}_{i}$ are the arrival time and the data overflow time
for AP $i$, respectively. Then, the total amount of data overflowed $O$ for
all APs can be expressed as

$\small O=\sum^{N}_{i=1}S(t_{i})(t-T^{o}_{i})\tau R.$ (14)

Meanwhile, the total amount of data collected by the UAV during the data
collection tour, eventually gathered from all APs, can be expressed as

$\displaystyle C=$
$\displaystyle\sum^{N}_{i=1}((1-S(t_{i})C_{i})+S(t_{i})\bar{C}_{i})$ (15)
$\displaystyle=$ $\displaystyle\sum^{N}_{i=1}((1-S(t_{i})\tau
T^{c}_{i}R)+S(t_{i})\tau\bar{T}^{c}_{i}R),$

where $\bar{C}_{i}$ and $\bar{T}^{c}_{i}$ respectively denote the amount of
data collected and the data collection duration by the UAV after the data
overflow at AP $i$. Eq. (15) means that when the AP $i$ is in the data
collection state at arrival time $t_{i}$, i.e., $S(t_{i})=0$, the amount of
data collected by UAV at time $t_{i}$ is $C_{i}(1-S(t_{i}))$, otherwise,
$C_{i}=\bar{C}_{i}S(t_{i})$.

To further understand and solve the TSDCMP within UAV-enabled GMENs, we
propose a mixed-integer programming formulation for the problem. This
formulation can be expressed as follows:

$\displaystyle\max\quad$ $\displaystyle C-\delta O$ (16a) s.t.
$\displaystyle\sum^{N}_{i=1}P(0)T^{c}_{i}+\sum^{N}_{i=0}\sum^{N}_{j\neq
i}x_{ij}P(\mathrm{v})T^{f}_{ij}\leq E_{max},\forall i,j\in\mathcal{N}_{a},$
(16b) $\displaystyle t_{i}+T^{c}_{i}+T^{f}_{ij}-t_{j}\leq M(1-x_{ij}),\forall
i,j\in\mathcal{N}_{a},$ (16c) $\displaystyle
t_{i}>T^{o}_{i}-M(1-S(t_{i})),\forall i\in\mathcal{N}_{a},$ (16d)
$\displaystyle t_{i}\leq T^{o}_{i}+MS(t_{i}),\forall i\in\mathcal{N}_{a},$
(16e) $\displaystyle D_{i}-D_{th}\leq C_{i}\leq D_{i},\forall
i\in\mathcal{N}_{a},$ (16f) $\displaystyle\sum^{N}_{j=1,j\neq
k}x_{kj}=y_{k},\forall k\in\mathcal{N}_{a},$ (16g)
$\displaystyle\sum^{N}_{i=0,i\neq k}x_{ik}=\sum^{N}_{j=0,j\neq k}x_{kj},$
(16h) $\displaystyle\sum^{N}_{j=1}x_{0j}=\sum^{N}_{j=1}x_{j0}=1,$ (16i)
$\displaystyle S(t_{i})\in\\{0,1\\},\forall i\in\mathcal{N}_{a},$ (16j)
$\displaystyle x_{ij}\in\\{0,1\\},\forall i,j\in\mathcal{N}_{a},$ (16k)
$\displaystyle y_{i}\in\\{0,1\\},\forall i\in\mathcal{N}_{a},$ (16l)
$\displaystyle T^{c}_{i},t_{i}\geq 0,\forall i\in\mathcal{N}_{a},$ (16m)

where $\delta$ is the penalty parameter; the binary variables $x_{ij}=1$ if
the UAV flies directly from AP $i$ to $j$, and $0$ otherwise; the binary
variables $y_{i}=1$ if AP $i$ is collected data by the UAV, and $0$ otherwise,
which is an auxiliary decision variable that is uniquely determined by
variables $x_{ij}$.

The objective function (16a) is to maximize the total amount of data collected
while minimizing the total amount of data overflowed for all APs by the UAV on
the data collection tour, where the total amount of data collected $C$ by the
UAV defined in Eq. (15) and the total amount of data overflow for all APs
defined in Eq. (14). Constraints (16b) ensure that the total energy
consumption of both data collection and flight in a scheduling cycle of UAV
cannot exceed the total energy capacity $E_{max}$. Constraints (16c) couple
routing decisions with the time scheduling, where $M$ is a large positive
constant [29]. The binary variables $x_{ij}=1$ if the UAV arrives at AP $j$
directly after departing from AP $i$, the arrival time at AP $j$ must be equal
to or greater than the sum of both arrival time and data collection time of AP
$i$, and flight time between APs $i$ and $j$. Constraints (16d) and (16e)
denote the state of AP $i$ when the UAV arrives at it at time $t_{i}$.
Constraints (16f) ensure that the amount of data collection by the UAV at each
AP is within a safe range. Constraints (16g) establish the relationship
between variables $x$ and $y$ and ensure that each AP can be collected data at
most once. Constraints (16h) are the flow conservation for each AP.
Constraints (16i) ensure that the UAV begins and ends its route at the base
station. Constraints (16j) show the state indicator variables at arrival time
$t_{i}$. Constraints (16k)–(16m) define the domain of the decision variables.

Further analysis of the optimization problem (16), we find that maximizing the
data collection efficiency of the UAV inherently involves minimizing the total
amount of data overflowed during the data collection tour. Furthermore, the
total amount of data collected and data overflowed depends on the duration of
data collection and the arrival time at each AP during the data collection
tour under the limited total energy capacity $E_{max}$. Minimizing the volume
of overflowed data necessitates precise scheduling decisions for the UAV. This
often lead to increased energy consumption for UAV flights, thereby
potentially reducing the total amount of data that can be collected by the
UAV. Therefore, finding a solution that maximizes the total amount of data
collected while minimizing the volume of overflowed data under the UAV’s
energy constraint is crucial. In the following section, we develop an
efficient algorithm based on temporal-spatial correlations to address this
problem.

###### Theorem 1

The TSDCMP within UAV-enabled GMENs is NP-hard.

###### Proof 1

We demonstrate that the TSDCMP within UAV-enabled GMENs is NP-hard by reducing
it from a classic NP-hard problem, namely the TOP with time-varying profit
[22, 23]. This reduction shows that the the TSDCMP within UAV-enabled GMENs
can be transformed into an TOP in $G$ as follows.

Given a node and an associated arc in complete directed weighted graph
$G(\mathcal{N},A)$, where each node $v_{i}\in\mathcal{N}$ has a positive
profit $p_{i}$, and a profit function $f_{i}(a_{i},s_{i})$ varying with the
arrival time $a_{i}$ and the duration of service time $s_{i}$. Nodes $v_{0}$
and $n+1$ correspond to the starting and ending the depots, respectively, and
do not generate profit. Each node can be visited at most once within a given
limited time $T_{max}$. The aim of the TOP with time-varying profit is to
determine a route that visits a subset of vertexes, and to determine the
duration of the arrival time and service time spent on each visited vertex, so
as to maximize the total collected profit under the given limited time
$T_{max}$.

We reduce the TOP with time-varying profit in $G(\mathcal{N},A)$ to the TSDCMP
within UAV-enabled GMENs as follows. The profit collected at each AP
$i\in\mathcal{N}$ is $C_{i}$ with the duration of service time
$T_{i}\in\mathcal{T}^{c}$, and the arrival time $a_{i}$ needs to be as early
as possible to meet the data overflow time $T^{o}_{i}$. The volume of data
stored $D_{i}$ at each AP varies significantly, which means that the hovering
duration $T_{i}$ of the UAV for data collection at each AP is different if the
data volume of each AP after data collection is at least below its threshold
$D_{th}$. Consequently, the amount of data collected $C$ by the UAV at each AP
also varies. Finally, the total amount of data collected by the UAV is
different in each data collection mission. The overall objective is to collect
as much data as possible while ensuring that the data collection duration of
UAV is within the mission duration $T$. Since the TOP with time-varying profit
is NP-hard [22, 23], the TSDCMP within UAV-enabled GMENs is NP-hard.

##  IV Cooperative Heuristic Algorithm Based on Temporal-Spatial Correlations

In this section, we propose a novel CHTSC to solve the TSDCMP within UAV-
enabled GMENs. The problem can be partitioned into two subproblems, namely the
trajectory planning and the data collection duration scheduling. The former
determines the flight trajectory of UAV during data collection, while the
latter focuses on allocating the arrival time and data collection duration at
each AP. Subsequently, an iterated local search is adopted to plan the
trajectory of UAV. Given the vast number of trajectories generated by iterated
local search, it is particularly crucial to quickly solve the UAV data
collection duration scheduling subproblem. To address this, we design an
efficient algorithm modified from the dynamic programming (DP) algorithm.

In the following paper, we detail the CHTSC called the iterated local search
with modified DP (ILS-MDP) to tackle the TSDCMP within UAV-enabled GMENs.

###  IV-A Framework of ILS-MDP for TSDCMP

ILS-MDP is a hybrid heuristic algorithm that aptly solves the TSDCMP within
UAV-enabled GMENs by leveraging the cooperation between ILS and MDP. The
framework of ILS-MDP for solving the problem is illustrated in Algorithm 1.
The ILS comprises perturbation and local search. At the beginning of ILS, we
initialize a feasible data collection scheme $S=\\{(V,T^{c})\\}$ and then
perform perturbation and local search on $S$. In each iteration, a
perturbation is employed to generate an improved UAV flight trajectory.
Subsequently, the solution is explored and improved by the local search, which
consists of several neighborbood structures. In each neighborbood structure,
the search operators such as _or-opt, swap, and 2-opt_ [30] are applied to the
current routing decisions until the best routing is found. The MDP algorithm
is utilized to evaluate each improved routing $V$, and to determine the data
collection duration $T^{c}$ as well as the objective function value
$f(V,T^{c})$. Finally, the algorithm terminates when the optimal solution can
no longer be further improved within the termination criteria $T_{max}$.

Input: A feasible route $V$ and the termination criteria $T_{max}$;

Output: Optimal time-sensitive data collection scheme $S^{*}$;

1 Initialize a feasible data collection scheme $S=\\{(V,T^{c})\\}$, let
$S^{*}\leftarrow S$ and $t\leftarrow 0$ by calling Algorithm 2;

2 while  _$t <T_{max}$_ do

3 $S^{\prime}$ $\leftarrow$ _Perturb_ $(S^{*})$ by calling Algorithm 3;

4 if  _No new route generated_ then

5 continue ;

6 $t\leftarrow t+1$;

7 end if

8 $S^{\prime\prime}$ $\leftarrow$ _LocalSearch_ ($R$, $S^{\prime}$, MDP);

9 if  _$f(S^{\prime\prime}) >f(S^{*})$_ then

10 $S^{*}\leftarrow S^{\prime\prime},t\leftarrow 0$;

11 else

12 $t\leftarrow t+1$;

13 end if

14

15 end while

Algorithm 1 The framework of ILS-MDP for TSDCMP.

We present the details on the initialization, perturbation, and local search
of ILS-MDP in the following sections.

###  IV-B Initialization for ILS-MDP

Through in-depth investigation on the TSDCMP within UAV-enabled GMENs, we
realize that the shortest distance Hamiltonian cycle is not necessarily the
best solution and even the infeasible, despite its potential to minimize the
UAV’s energy data collection energy consumption. Conversely, a more general
solution, which may not produce the shortest distance Hamiltonian cycle or
minimize energy consumption, could be feasible and potentially optimal for the
UAV. This discrepancy arises because the data collection request signals of
APs in a response queue $Q$ are sorted by their service request order. This
sorting introduces a temporal correlation between adjacent service requests in
$Q$. Typically, the APs at the front of $Q$ are prioritized on the data
collection tour. To enhance the algorithm’s decision-making efficiency, we
leverage the data collection deadlines (i.e., data overflow time) of the APs
to construct a Hamiltonian cycle. This cycle, referred to as the shortest time
Hamiltonian cycle $H$, is illustrated in Fig. 4a.

$\begin{array}[]{l}\includegraphics[width=202.35622pt]{Passer-By-Data-
Collection.pdf}\\\ \end{array}$

Figure 4: Example of the local search strategy based on temporal-spatial
correlations for passer-by APs: (a) The shortest time Hamiltonian cycle. (b)
The APs data collection based on temporal-spatial correlations.

On the basic of the shortest time Hamiltonian cycle $H$, we need to select a
feasible route for data collection by the UAV. Intuitively, two APs with
adjacent priorities of request service may not be spatially adjacent.
Therefore, to reduce excessive energy consumption from the UAV flying back and
forth [30], the route should be optimized within the shortest time hamiltonian
cycle $H$, taking into account both the priority of service time and spatial
proximity, i.e., _temporal-spatial correlations_. In specific, we optimize the
data collection order of APs without violating the UAV’s energy constraint to
minimize data overflow. This involves ensuring that APs with similar service
priorities are as close as possible spatially, thereby reducing energy
consumption and maximizing the amount of data collection by the UAV.

In light of the aforementioned discussion, we assign a score to evaluate the
order in which each AP is served during the initialization for ILS-MDP. The
scoring mechanism fully considers both the time-sensitivity and geographical
proximity among APs. More specifically, an AP with an earlier service time and
shorter required flight time will have a higher priority to be serviced first.
The score $\omega_{i}$ of AP $i$ is calculated as follows:

$\small\omega_{i}=\frac{1}{i\Delta T_{i}},$ (17)

where $i$ denotes the order in which AP $i$ is served in the shortest time
Hamiltonian cycle $H$, and $\Delta T_{i}$ is the increased time after
inserting AP $i$ into the current sequence of APs $V$.

A complete feasible solution $S$ can be denoted as
$S=\\{(V,T^{c})|V=\\{v_{0},v_{1},\ldots,v_{n},v_{0}\\},T^{c}=\\{0,T_{1}^{c},\ldots,T_{n}^{c},0\\}\\}$
for the shortest time Hamiltonian cycle $H$ constructed by the response
sequence $Q$, where $V$ and $T^{c}$ are the visited sequence of APs and the
corresponding data collection duration for these APs, respectively. Firstly,
we initialize the visited sequence of APs $V$ consisting only of the BS
$v_{0}$. Secondly, we attemp to select AP $i$ with the highest score
$\omega_{i}$ to be added to the visited sequence $V$ and calculate the arrival
time $t_{i^{*}}$ for AP $i^{*}$. If the UAV successfully reaches AP $i^{*}$
before its data overflow time $T^{o}_{i^{*}}$, then AP $i^{*}$ is inserted
into the visited sequence $V$. Subsequently, the data collection duration is
calculated and the relevant information is updated. Otherwise, if the UAV does
not reach AP $i^{*}$ before its data overflow time $T^{o}_{i^{*}}$, AP $i^{*}$
is successively inserted into each possible position within the visited
sequence $V$. If the status of all APs in $V$ remains unchanged after the
insertion of AP $i^{*}$ into a specific position, the insertion is
successfully, and the related information is updated accordingly. If the AP
$i^{*}$ fails to insert $V$, it is added to the end of the visited sequence
$V$, and the related information will be updated simultaneously. The detailed
process is displayed in Algorithm 2.

Input: The set of all APs $\mathcal{N}_{a}$ and BS $v_{0}$, the self-growth
rate of data for each AP $\alpha^{s}_{i}(t)$, and the UAV’s battery capacity
$E_{max}$;

Output: A feasible data collection scheme $S$;

1 Generate the shortest time Hamiltonian cycle $H$ based on the response queue
$Q$, i.e., $H\leftarrow Q$;

2 Let $S=\\{(V,T^{c})|V=\\{v_{0},v_{0}\\},T^{c}=\\{0,0\\}\\}$;

3 while  _$H\neq\emptyset$_ do

4 for  _$i\leftarrow 1$ to $|H|$_ do

5 $\omega_{i}\leftarrow\frac{1}{i\Delta T_{i}}$;

6 end for

7 $i^{*}\leftarrow\arg\max_{i\in\mathcal{N}_{a}}\omega_{i}$;

8 Calculate the arrival time $t_{i^{*}}$ for $i^{*}$;

9 if  _$t_{i^{*}}\leq T^{o}_{i^{*}}$_ then

10
$T^{c}_{i^{*}}\leftarrow\frac{D_{i^{*}}+\alpha^{s}_{i}t_{i^{*}}-D_{th}}{R}$;

11 $V\leftarrow V\cup\\{i^{*}\\}$;

12 $H\leftarrow H\backslash\\{i^{*}\\}$;

13 $T^{c}\leftarrow T^{c}\cup\\{T^{c}_{i^{*}}\\}$;

14 $S(t_{i^{*}})\leftarrow 0$;

15 else

16 foreach  _AP $j\in V$_ do

17 Insert $i^{*}$ next to $j$;

18 if  _APs in $V$ have no status changes_ then

19 Execute the same operation as lines 10-15 and update the related
information for subsequent nodes;

20 break;

21

22 end if

23

24 end foreach

25 if  _Node $i^{*}$ insertion failed_ then

26 $V\leftarrow V\cup\\{i^{*}\\}$;

27 $H\leftarrow H\backslash\\{i^{*}\\}$;

28 $T^{c}\leftarrow T^{c}\cup\\{T^{c}_{i^{*}}\\}$;

29 $S(t_{i^{*}})\leftarrow 1$;

30

31 end if

32

33 end if

34

35 end while

Algorithm 2 Initialize a feasible data collection scheme.

###  IV-C Perturbation and Local Search Based on Temporal-Spatial Correlations

####  IV-C1 Perturbation

The perturbation method plays a crucial role as an integral component of ILS-
MDP, aimed at enhancing the algorithm’s search capabilities by disrupting
local optimal solutions. The core idea of the perturbation method is to remove
a subset of visited APs and then insert unvisited APs to generate a
diversified solution.

We define a perturbation strength parameter $\xi$ to denote the number of APs
to be removed from the route. Considering the temporal-spatial correlations
between APs, we set $\xi=|V|/10+1$, where $|V|$ is the number of APs in the
current route. Algorithm 3 describes the perturbation method process. Firstly,
the $\xi$ visited APs are randomly selected and removed from the route $V$,
and then the removed $\xi$ APs are randomly reinserted into the current route
$V$. If all inserting positions satisfy the UAV’s energy constraint and yield
a higher the objective function value compared to the original solution, the
perturbation of the solution $S$ is considered successful, and solution $S$ is
updated with the perturbed solution $S^{*}$. Otherwise, the perturbation of
solution $S$ is deemed unsuccessful. After perturbation, the algorithm enters
the local search phase.

Input: A feasible solution $S$;

Output: A feasible new solution $S^{*}$ generated after disturbance;

1 Randomly select and remove $\xi$ visited APs from $V$;

2 Randomly reinsert $\xi$ removed APs into $V$;

3 if  _$E(S^{*})\leq E_{max}$ and value $(S)$ $\leq$ value $(S^{*})$_ then

4 $S\leftarrow S^{*}$;

5 return true;

6else

7 No feasible solution $S^{*}$;

8 return false;

9 end if

Algorithm 3 Perturb generate a diversified solution.

####  IV-C2 Local Search

Local search is another key component in ILS-MDP. The basic idea of local
search is to start with a current solution and iteratively explore neighboring
solutions by employing several neighborbood structures based on the
characteristics of the TSDCMP. The neighborbood structure defines the set of
neighboring solutions that can be obtained by utilizing the search operators
to the current solution. Specific to this problem, a given solution can be
improved by adjusting the order of APs’ request service to reduce data
overflow and increase data collection. In this work, we adopt three classical
search operators (i.e., _2-opt_ , _swap_ , and _or-opt_) for the flight
trajectory problem. They are described as follows:

  * •

_2-opt_ : Remove two non-adjacent edges from the current solution and
reconnecting them in a different way to generate a new solution.

  * •

_swap_ : Exchange the positions of two APs in the current route.

  * •

_or-opt_ : Remove a subsequence of $\delta$ consecutive of APs and reinsert
them at a different position, and the value of $\delta$ is set to 1, 2, or 3
in this work.

The three neighborhood search operators work within the same route. The goal
of these operators is to increase the total amount of data collected while
minimizing the total amount of data overflowed by adjusting the order of
visiting APs within a single route. This adjustment fully considers the
temporal-spatial correlations of the TSDCMP. In each iteration, the three
neighborhoods are carried out in the given sequence of APs. For each
neighborhood, the best improvement strategy is adopted to exploit the best
improved neighborhood found so far and then continue searching for a better
solution.

###  IV-D Modified DP Algorithm for Data Collection Duration Scheduling
Problem

When a UAV’s trajectory is generated employing the ILS, the data collection
duration for the given UAV trajectory must be determined by solving the data
collection duration scheduling problem (DCDSP). Considering the key
characteristic of the DCDSP, we propose a novel variation of the modified
dynamic programming (MDP) algorithm to effectively tackle the problem. The MDP
extends the DP by incorporating the temporal and spatial correlations of APs
into the scheduling process for UAV data collection.

The basic DP approach is initially proposed by Bellman. The core idea of DP is
to solve a complex problem using a divide-and-conquer strategy [31].
Specifically, the DP approach decomposes the complex original problem into
overlapping subproblems and subsequently solves them recursively. This
recursive methodology avoids redundant recalculations of solutions, enhancing
computational efficiency.

We adopt the MDP algorithm to address the DCDSP. For any
$k\in\\{1,\ldots,N\\}$ and $j\in\\{0,\ldots,T\\}$, let $f(k,j)$ denote the
maximum total amount of data collected by selecting the first $i$ APs, with a
total available service time equal to $j$ and benefit $p_{k}$. That is, let

$\displaystyle f(k,j)$ (18) $\displaystyle=$
$\displaystyle\begin{cases}\max\\{f(k-1,j),f(k-1,j-T_{i})+p_{k}\\}&\text{if
}j\geq T_{i},\\\ f(k-1,j),&\text{otherwise}.\end{cases}$

This is the MDP recursive function for the DCDSP, which enables us to compute
$f(k,j)$ using Algorithm 4.

The algorithm 4 outlines the general framework of the MDP algorithm for
solving the DCDSP. Initially, the parameters for both the DCDSP and the MDP
algorithm are input (lines 1-3). Subsequently, the MDP algorithm is then
utilized to compute the amount of data collected by the UAV, the data overflow
for each AP, and the flight time between the APs (lines 4-24). Finally, the
flight time $T^{f}$ is updated, and the optimal data collection during for the
UAV at each AP is determined based on the state transition path (lines 27-30).

Input: The sequence of APs $V=\\{v_{0},v_{1},\ldots,v_{0}\\}$ in a given
route, the total remaining service time $T$, the maximum service time per AP
$\check{T}$, and $\epsilon$ is a relatively small positive real number.

Output: The optimal data collection duration for each AP $\check{T}^{*}$

1 Initialize the total time spent in flight $T^{f}\leftarrow 0$, the data
collection duration for each AP $T_{i}^{c}\in\check{T}$,
$Trace\leftarrow\emptyset$, $DP[0:N,0:T]\leftarrow\epsilon$,
$Data[0:N,0:N]\leftarrow\emptyset$;

2 Initialize $Data[0:N,0:N]\leftarrow 0$ to record the amount of data
collected and overflow for each state;

3 Initialize the benefits of each state $p$;

4 for  _$i\leftarrow 1$ to $N$_ do

5 Update the flight time $T^{f}$;

6 while  _$j\leq i*\check{T}$ and $j\leq T$_ do

7 for  _$k\leftarrow 1$ to $j$_ do

8 $t\leftarrow T^{f}+j-k$;

9 Calculate the amount of data stored $D_{i}$ by node $i$ in the state;

10 if  _$D_{i}-\alpha_{i}*k >D_{th_{i}}$_ then

11 continue

12 end if

13 if  _$DP[i-1][j-k]==\epsilon$_ then

14 continue

15 end if

16 $p\leftarrow value(Data[i-1][j-k],t,v_{i})$;

17 if  _$p >DP[i][j]$_ then

18 $DP[i][j]\leftarrow p$;

19 $Trace[i][j]\leftarrow p$;

20 Update $Data[i][j]$;

21

22 end if

23

24 end for

25

26 end while

27

28 end for

29Select the data collection duration $T$ corresponding to the maximum
benefits in DP;

30 for  _$i\leftarrow N$ to $1$_ do

31 Update the flight time $T^{f}$;

32 $\check{T}^{*}[i]\leftarrow Trace[i][T]$;

33 $T\leftarrow T\setminus Trace[i][T]$;

34

35 end for

Algorithm 4 MDP Algorithm for the DCDSP

##  V Simulation Studies

In this section, we present simulation experiments to assess the effectiveness
of the developed model and the performance of the proposed solution approach
for the TSDCMP.

###  V-A Simulation Settings

The simulations are conducted on a workstation equipped with an AMD Ryzen
Threadripper 3970X 32-Core CPU running at 3.79GHz, 192GB RAM, and operating on
Ubuntu 20.04.4 LTS using a single thread. All simulation programs were
developed using C++ programming language. It is important to note that all
variables in this work are assigned uniform units for simplicity.

####  V-A1 Instance Generation

Given the absence of an established benchmark for the TSDCMP, we adapt a
subset of Solomon’s instances to create the test dataset for this study111The
Solomon instances are obtained from http://neo.lcc.uma.es/vrp/vrp-instances/.,
wherein we proportionally magnify the coordinates in original instances by ten
times. In addition, to tailor the dataset for the TSDCMP, we included
pertinent parameters pertaining to both the UAV and each AP, such as the UAV’s
battery energy and the AP’s storage capacity. The dataset consists of
instances with cluster-located APs (C), random-located APs (R), and random-
cluster-located APs (RC). The number of APs belongs to $\\{15,20,30,40\\}$.
Therefore, there are a total of 12 instances. Each instance is named as “Type
$|N|$”, for example, “C15” refers to the instances with fifteen cluster-
located APs. The details of these instances can be obtained from
https://sites.google.com/view/dbjiao/homepage.

####  V-A2 Compared Algorithms

Due to the lack of existing algorithms for solving the TSDCMP, we compare the
proposed algorithm _ILS-MDP_ with following two modified high-performance
algorithms, namely _ILS-MCS_ [23] and _CHPBILM_ [30]. These serve as benchmark
algorithms within the same framework, differing only in allocation of arrival
time and data collection duration. This enables their application to our
problem, thereby verifying the effectiveness of the proposed model and
algorithm in this work.

  * •

_ILS-MCS_ is a hybrid heuristic algorithm that integrates a modified
coordinate search (MCS) into an iterated local search. Specifically, the
iterated local search is adopted to construct and improve the routes, while
the MCS is employed to determine the service time at each AP.

  * •

_CHPBILM_ is a cooperative memetic algorithm that integrates that an efficient
heuristic algorithm, variant population-based incremental learning (PBIL), and
a maximum-residual-energy-based local search (MRELS) strategy. Specifically,
the efficient heuristic algorithm is employed to improve the flight trajectory
of the UAV, while the PBIL with MRELS is utilized to determine the number of
restored unit circles for each degraded area on the grasslands.

It is worth noting that MCS optimizes continuous time variables in the
original problem, while time is treated as a discrete variable in our
scenario. To adapt MCS to our problem, we round down the results obtained by
MCS to obtain a solution. In addition, we represent integer solutions directly
in binary form in PBIL. We determine the optimal value for each binary bit
through a search process, and ultimately convert the binary value to decimal
to obtain the final solution.

####  V-A3 Performance Metrics

We adopt the following four performance metrics to evaluate the effectiveness
of the proposed model and algorithm.

  * •

_Objective function value_ is to maximize the total amount of data collected
while minimizing the total amount of data overflowed for all APs by the UAV
during the data collection tour, as defined by Eq. (16a) in Section III-D.

  * •

_Data collection efficiency_ $\eta$ is the ratio of the total amount of data
collected by the UAV, as defined by Eq. (15), to the sum of both the total
amount of data collected by the UAV and the amount of data overflow for all
APs, as defined by Eq. (14), during the data collection tour in Section III-D.
This metric is defined as follows:

$\small\eta=\frac{C}{C+O}.$ (19)

  * •

_Ratio of data collection time_ $\mu$ is defined as the proportion of the
total data collection time to the sum of the total flight time of the UAV and
the data collection time. This metric is defined as follows:

$\mu=\frac{T^{c}}{T^{c}+T^{f}}.$ (20)

  * •

_Algorithm runtime_ refers to the running time of each algorithm for each
instance.

####  V-A4 Parameter Settings

In the system model described in the Section III, the parameters of the UAV
are set according to the values employed in [28]: $P_{o}=79.85$,
$U_{tip}=120$, $\mathrm{v}_{0}=4.03$, $d_{0}=0.6$, $\rho=1.225$, $s=0.05$, and
$A=0.503$. Additionally, the UAV speed $\mathrm{v}$ is set to 10. The battery
capacity carried by the UAV is set to 37000, 46000, 132000, and 141000
depending on different types of networks. The penalty parameter $\eta$ is set
to 15 to determine the best-performing solutions, the data collection
thresholds varies from 0.75 to 0.90 in increasing steps of 0.05 based on the
size of the networks, and the signal-to-noise ratio range from 2.4 to 6.4. In
addition, the other communication-related parameters are set as follows,
consistent with [8]: $B=1000$, $\beta=-50$, $\sigma^{2}=-110$, $\tau=1$, and
$\tilde{H}=1$. The transmit power $p$ of AP for uploading data link varies
depending on different instances, with values ranging from $p\in(5.52,14.36)$.

We conducted preliminary experiments to fine-tune the hyper-parameter for all
algorithms to determine the best-performing configurations. In ILS-MDP, the
maximum number generation $T^{DMP}_{max}$ is set to $15$. Moreover, in the
comparison algorithms, the parameters of the ILS-MCS are set based on the
values used in [23]: $\alpha=10$, $\alpha_{min}=1$, and
$\|\vec{e_{i}}\|=0.01$. In ILS-PBIL, the population size and maximum iteration
number of PBIL are respectively set to $P=30$ and $T^{PBIL}_{max}=300$. The
learning rate is set to $\alpha=0.4$ and the proportion of elite solution
$\theta$ is set to $33\%$. The PBIL algorithm utilizes binary encoding with 5
bits, indicating that the maximum data collection time for each AP is 31. The
maximum execution time of all algorithms is limited to 1800 seconds.

In the simulations, each algorithm runs independently ten times in each
scenario222In this work, the instance and scenario can be used
interchangeably. to minimize the influence of randomness on the test results
as much as possible. The average values of these ten runs are taken as the
simulation results, providing a more reliable assessment of the algorithm’s
performance.

###  V-B Simulation Results

We first evaluate the performance of different algorithms by varying the
number of APs from 15 to 40 across three different network types in Table II.
For solving the TSDCMP using ILS-MDP, ILS-MCS, and ILS-PBIL separately, we
present the best, worst, and average objective function values; the standard
deviation among ten runs; and the average total computing time in seconds for
ten runs. Boldface is used to highlight the best value, as well as the
shortest computing time among the different algorithms.

TABLE II: Comparison of the objective function values among the three
different algorithms for 12 instances.

Instance |  | ILS-MCS |  | ILS-PBIL |  | ILS-MDP
---|---|---|---|---|---|---
| Best | Worst | Avg. | Std. | Time (s) |  | Best | Worst | Avg. | Std. | Time (s) |  | Best | Worst | Avg. | Std. | Time (s)
C15 |  | 195667 | 195667 | 195667 | 0.00 | 0.92 |  | 165701 | 143921 | 155556 | 6091.06 | 1148.56 |  | 212973 | 212973 | 212973 | 0.00 | 0.76
C20 |  | 222053 | 222053 | 222053 | 0.00 | 10.64 |  | 213080 | 186701 | 201146 | 8216.21 | 2437.15 |  | 234621 | 234621 | 234621 | 0.00 | 3.01
C30 |  | 263381 | 263381 | 263381 | 0.00 | 140.29 |  | 171183 | 159411 | 165999 | 4304.71 | 5249.83 |  | 301694 | 301694 | 301694 | 0.00 | 27.66
C40 |  | 457536 | 457536 | 457536 | 0.00 | 917.67 |  | 58404 | 58404 | 58404 | 0.00 | 6184.15 |  | 523513 | 523513 | 523513 | 0.00 | 134.11
R15 |  | 7437 | 7437 | 7437 | 0.00 | 4.82 |  | 27922 | 5883 | 12959 | 7637.82 | 1887.31 |  | 10824 | 10824 | 10824 | 0.00 | 0.95
R20 |  | 128470 | 128470 | 128470 | 0.00 | 10.28 |  | 120169 | 96385 | 111683 | 7144.84 | 2657.99 |  | 134937 | 134937 | 134937 | 0.00 | 3.09
R30 |  | 174107 | 174107 | 174107 | 0.00 | 222.04 |  | -1123740 | -1126140 | -1124940 | 120000 | 3022.29 |  | 219612 | 182080 | 193696 | 13075.21 | 49.27
R40 |  | 8636 | -92528 | -1474 | 30352.93 | 936.94 |  | -1838772 | -1838772 | -1838772 | 0.00 | 6522.08 |  | 199404 | 199404 | 199404 | 0.00 | 177.55
RC15 |  | 171462 | 171462 | 171462 | 0.00 | 2.21 |  | 176951 | 162727 | 167699 | 3639.13 | 1236.33 |  | 181299 | 175524 | 180723 | 1735.50 | 0.76
RC20 |  | 157095 | 157095 | 157095 | 0.00 | 13.86 |  | 145139 | 128080 | 134852 | 4709.21 | 1919.86 |  | 161469 | 161469 | 161469 | 0.00 | 2.09
RC30 |  | 92709 | 92709 | 92709 | 0.00 | 126.13 |  | -244860 | -258871 | -251879 | 7004.50 | 2018.17 |  | 153827 | 153827 | 153827 | 0.00 | 34.27
RC40 |  | 15871 | 15871 | 15871 | 0.00 | 390.59 |  | -151144 | -151144 | -151144 | 0.00 | 7025.09 |  | 445480 | 445480 | 445480 | 0.00 | 126.43

  * 1

Standard deviation is abbreviated as “Std.”, and average value is abbreviated
as “Avg.”

  * 2

The algorithm running time is the average of 10 runs, rounded to two decimal
places.

  * 3

All average values are rounded.

(a) ILS-MCS (b) ILS-PBIL (c) ILS-MDP

Figure 5: Comparison of the average objective function value of different
algorithms by varying the number of APs from 15 to 40 across three different
network types.

Table II illustrates that the objective function value increases with the
number of APs for each of the three algorithms across different network types.
Meanwhile, from Fig. 5, we observe that in networks with the same number of
APs, the average objective function value of C-type networks is typically much
larger than that of other types, while the average objective function value of
R-type and CR-type networks depends on the distribution of AP locations. The
reason behind this phenomenon is that the UAV in the solution provided by the
different algorithms is more inclined to collect data from clusters with many
APs in C-type networks, considering the temporal-spatial correlations during
APs’ data collection. Consequently, more energy can be dedicated to data
collection, resulting in an increase in the objective function value.
Conversely, in the other two types of networks, the relatively scattered
distribution of AP locations leads to increased energy consumption for UAV
flying between different APs. In some cases, APs may even experience data
overflow due to delayed data collection, resulting in objective function
values that are not as large as those observed in C-type networks.

As the UAV’s energy increases proportionally, the presence of more APs and
higher network density leads to increased data collection by the UAV.
Consequently, data overflow decreases, resulting in a larger objective
function value. Moreover, as observed in Table II, the proposed algorithm ILS-
MDP demonstrates significantly superior performance compared with the other
two algorithms in terms of the best value, worst value, and average value,
except for instance R15. In addition, from the results shown in Table II, it
can be seen that the ILS-MDP could generally find better solutions than the
other two algorithms within considerably less computing time and also
demonstrates good stability. Furthermore, from Table II and Fig. 5, we
observed that when employing algorithms ILS-MCS and ILS-PBIL to tackle the
large-scale R30 and R40 instances, the objective function values appeared to
be negative. This occurred because within the maximal computing time, these
two algorithms, especially ILS-PBIL, converge slowly and prompt premature
termination of the iteration process, failing to produce high-quality
solutions.

TABLE III: Comparison of the UAV data collection efficiency among the three
different algorithms for 12 instances.

Instance |  | ILS-MCS |  | ILS-PBIL |  | ILS-MDP
---|---|---|---|---|---|---
| $C$ | $O$ | $\eta$ |  | $C$ | $O$ | $\eta$ |  | $C$ | $O$ | $\eta$
C15 |  | 238987 | 2888 | 0.988 |  | 209715 | 2934 | 0.986 |  | 261528 | 3237 | 0.987
C20 |  | 222053 | 0 | 1.000 |  | 213080 | 0 | 1.000 |  | 236046 | 95 | 0.999
C30 |  | 353951 | 6038 | 0.983 |  | 319728 | 9903 | 0.970 |  | 418499 | 7787 | 0.981
C40 |  | 585591 | 8537 | 0.986 |  | 387924 | 21968 | 0.946 |  | 627448 | 6929 | 0.989
R15 |  | 203697 | 13084 | 0.940 |  | 212872 | 12330 | 0.945 |  | 210984 | 13344 | 0.941
R20 |  | 260635 | 8811 | 0.967 |  | 268309 | 9876 | 0.964 |  | 251262 | 7755 | 0.970
R30 |  | 394397 | 14686 | 0.964 |  | 281806 | 93863 | 0.750 |  | 336297 | 7779 | 0.977
R40 |  | 501761 | 32875 | 0.939 |  | 311058 | 143322 | 0.684 |  | 451692 | 16819 | 0.964
RC15 |  | 192072 | 1374 | 0.992 |  | 198221 | 1418 | 0.992 |  | 200079 | 1252 | 0.993
RC20 |  | 197535 | 2696 | 0.987 |  | 182984 | 2523 | 0.986 |  | 197889 | 2428 | 0.989
RC30 |  | 409809 | 21140 | 0.951 |  | 390825 | 42379 | 0.902 |  | 364292 | 14031 | 0.963
RC40 |  | 582406 | 37769 | 0.939 |  | 587666 | 49254 | 0.923 |  | 585220 | 9316 | 0.984

  * 1

The data collection efficiency $\eta$ is the average of 10 runs, rounded to
three decimal places.

We then assess the algorithms’ performance by calculating the data collection
efficiency of UAV. Table III showcases the efficiency of UAV data collection
for each instance. It is evident that the data collection efficiency of UAV,
when using the proposed ILS-MDP algorithm, exceeds that of the other two
algorithms in over $75\%$ of the instances. This implies that the proposed
ILS-MDP algorithm can effectively utilize the temporal-spatial correlations
among APs for data collection. Consequently, the UAV’s flight energy
consumption is reduced, which in turn leaves more energy available for collect
data.

Moreover, we also investigate the algorithms’ performance by examining the
ratio of data collection time. As observed in Table IV, the proposed ILS-MDP
algorithm shows a slight advantage over ILS-MCS algorithm in terms of ratio of
data collection time, despite a slight performance gap in some instances.
However, when compared with the ILS-PBIL algorithm, the advantage is notably
significant. Moreover, when the UAV achieves maximum the amount of data
collection during a data collection process, specifically when the best
solution is reached, the best UAV path determined by each algorithm for each
instance is depicted in Fig. 6.

(a) C15 (b) R15 (c) RC15 (d) C20

(e) R20 (f) RC20 (g) C30 (h) R30

(i) RC30 (j) C40 (k) R40 (l) RC40

Figure 6: Visualization of the best paths generated by three different
algorithms in three different network scenarios for 12 instances. TABLE IV:
Ratio of effective data collection time among the three different algorithms
for 12 instances.

Instance |  | ILS-MCS |  | ILS-PBIL |  | ILS-MDP
---|---|---|---|---|---|---
| Flight | Service | $\mu$ |  | Flight | Service | $\mu$ |  | Flight | Service | $\mu$
C15 |  | 115 | 85 | 0.425 |  | 122 | 73 | 0.374 |  | 107 | 91 | 0.459
C20 |  | 130 | 80 | 0.381 |  | 133 | 78 | 0.370 |  | 123 | 85 | 0.410
C30 |  | 179 | 143 | 0.444 |  | 218 | 129 | 0.372 |  | 177 | 170 | 0.490
C40 |  | 325 | 258 | 0.443 |  | 462 | 170 | 0.269 |  | 307 | 277 | 0.474
R15 |  | 278 | 110 | 0.284 |  | 261 | 113 | 0.302 |  | 278 | 112 | 0.287
R20 |  | 307 | 152 | 0.331 |  | 336 | 157 | 0.318 |  | 312 | 142 | 0.312
R30 |  | 416 | 216 | 0.342 |  | 755 | 153 | 0.169 |  | 452 | 183 | 0.288
R40 |  | 692 | 263 | 0.276 |  | 907 | 158 | 0.148 |  | 552 | 234 | 0.298
RC15 |  | 164 | 96 | 0.369 |  | 162 | 97 | 0.374 |  | 164 | 96 | 0.369
RC20 |  | 221 | 106 | 0.324 |  | 222 | 97 | 0.304 |  | 224 | 105 | 0.319
RC30 |  | 450 | 214 | 0.322 |  | 760 | 197 | 0.206 |  | 436 | 186 | 0.300
RC40 |  | 747 | 256 | 0.255 |  | 814 | 247 | 0.232 |  | 566 | 254 | 0.310

  * 1

The ratio of data collection time $\mu$ is the average of 10 runs, rounded to
three decimal places.

Finally, to emphasize the advantages of our proposed algorithm and model, and
enhance the credibility of the experimental results, we perform a statistical
test. All comparisons are validated by using the nonparametric Wilcoxon rank-
sum test with significance level of $p=0.05$. The statistical outcomes are
detailed in Table V. From Table V, it is evident that the $p-$values are all
less than 0.05 except for the instances of R15 with the ILS-PBIL algorithm.
These statistical results suggest that the observed differences are
statistically significant.

TABLE V: Statistical testing of the performance among the three different
algorithms for 12 instances.

Algorithm pairs |  |  $p$-value
---|---|---
| C15 | C20 | C30 | C40 | R15 | R20 | R30 | 40 | RC15 | RC20 | RC30 | RC40
ILS-MDP $vs.$ ILS-PBIL |  | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.443($l$) | 0.0000 | 0.0001 | 0.0000 | 0.0001 | 0.0000 | 0.0000 | 0.0000
ILS-MDP $vs.$ ILS-MCS |  | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000 | 0.0000

  * 1

The Wilcoxon rank-sum test is conducted with significance level $p$ is $0.05$,
and $l$ indicates that the statistical result is nonsignificant.

##  VI Conclusion

This work addressed a variant of TOP with time-varying profits for the TSDCMP
within GMENs during a data collection tour. It represents the first research
effort to solve this problem by jointly optimizing the flight trajectory,
arrival time, and data collection duration for the UAV at each AP. The goal
was to determine how the UAV manages its limited energy, coupled routing and
time scheduling, and the state of APs and UAV arrival time to minimize the
volume of overflowed data while maximizing the volume of data collected for
APs. We formulated the TSDCMP for UAV-enabled GMENs as a mixed-integer
programming model in a single trip under the realistic constraints. To address
this problem, we developed a novel CHTSC algorithm, which integrates a
modified MDP into an iterated local search. This algorithm fully considers the
temporal and spatial relationships between consecutive service requests from
APs. The simulation results indicated that the mixed-integer programming model
accurately represents the characteristics of the TSDCMP within UAV-enabled
GMENs. Furthermore, the proposed CHTSC algorithm outperformed two superior
algorithms across twelve different scale instances.

Future research directions include exploring collaborative data collection
schemes using multiple UAVs to overcome the limitations of a single UAV’s data
collection capabilities. In addition, expanding the study to incorporate
autonomous decision-making framework that accounts for variable UAV altitudes
in complex grassland terrains is essential. What is more, the model and
solution framework developed here can be extended to other domains, such as
emergency rescue operations.

## Acknowledgment

This work was supported in part by National Natural Science Foundation of
China (Grant No. 62233003, 62176109, U21A20183, and 62272210), the Fundamental
Research Funds for the Central Universities (Grant No. lzujbky-2021-2 and
CHD300102223109), and the Natural Science Foundation of Gansu Province, China
(Grant No. 20JR10RA640).

The authors would like to thank Mr. Z. Guo and Dr. L. Yuan for kind help and
valuable discussions. We also thank the editors and anonymous referees for
their insightful comments and helpful suggestions which significantly improve
the manuscript’s quality.

## References

  * [1] P. Török, L. A. Brudvig, J. Kollmann, J. N Price, and B. Tóthmérész, “The present and future of grassland restoration,” _Restoration Ecology_ , vol. 29, p. e13378, 2021.
  * [2] J. Dengler, M. Janišová, P. Török, and C. Wellstein, “Biodiversity of palaearctic grasslands: a synthesis,” _Agriculture, Ecosystems & Environment_, vol. 182, pp. 1–14, 2014.
  * [3] B. O. Andrade, C. Koch, I. I. Boldrini, E. Vélez-Martin, H. Hasenack, J.-M. Hermann, J. Kollmann, V. D. Pillar, and G. E. Overbeck, “Grassland degradation and restoration: a conceptual framework of stages and thresholds illustrated by southern Brazilian grasslands,” _Natureza & Conservação_, vol. 13, no. 2, pp. 95–104, 2015.
  * [4] L. Ge, W. Juanle, W. Yanjie, and W. Haishuo, “Estimation of grassland production in central and eastern Mongolia from 2006 to 2015 via remote sensing,” _Journal of Resources and Ecology_ , vol. 10, no. 6, pp. 676–684, 2019.
  * [5] X. Wang, W. Xie, X. Song, T. Wan, and A. Liu, “Grassland ecological protection monitoring and management application based on ZigBee wireless sensor network,” _Mathematical Problems in Engineering_ , vol. 2022, no. 1, p. 2623183, 2022.
  * [6] K. Messaoudi, O. S. Oubbati, A. Rachedi, A. Lakas, T. Bendouma, and N. Chaib, “A survey of UAV-based data collection: Challenges, solutions and future perspectives,” _Journal of Network and Computer Applications_ , vol. 216, p. 103670, 2023.
  * [7] Z. Ning, H. Hu, X. Wang, L. Guo, S. Guo, G. Wang, and X. Gao, “Mobile edge computing and machine learning in the Internet of Unmanned Aerial Vehicles: a survey,” _ACM Computing Surveys_ , vol. 56, no. 1, pp. 1–31, 2023.
  * [8] M. Samir, S. Sharafeddine, C. M. Assi, T. M. Nguyen, and A. Ghrayeb, “UAV trajectory planning for data collection from time-constrained IoT devices,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 1, pp. 34–46, 2019.
  * [9] C. Zhan, H. Hu, Z. Liu, Z. Wang, and S. Mao, “Multi-UAV-enabled mobile-edge computing for time-constrained IoT applications,” _IEEE Internet of Things Journal_ , vol. 8, no. 20, pp. 15 553–15 567, 2021.
  * [10] N. Wang, Y. Xin, J. Zheng, J. Wang, X. Liu, X. Hou, and Y. Liu, “Priority-oriented trajectory planning for UAV-aided time-sensitive IoT networks,” in _2020 IEEE International Conference on Communications Workshops (ICC Workshops)_. IEEE, 2020, pp. 1–7.
  * [11] J. Liu, P. Tong, X. Wang, B. Bai, and H. Dai, “UAV-aided data collection for information freshness in wireless sensor networks,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 4, pp. 2368–2382, 2021.
  * [12] D.-H. Tran, V.-D. Nguyen, S. Chatzinotas, T. X. Vu, and B. Ottersten, “UAV relay-assisted emergency communications in IoT networks: Resource allocation and trajectory optimization,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 3, pp. 1621–1637, 2022.
  * [13] K. Liu and J. Zheng, “UAV trajectory optimization for time-constrained data collection in UAV-enabled environmental monitoring systems,” _IEEE Internet of Things Journal_ , vol. 9, no. 23, pp. 24 300–24 314, 2022.
  * [14] Z. Zeng and Y. Gao, “AoI-sensitive relay-assisted data collection via multi-UAV in the large-scale disaster area,” in _2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)_. IEEE, 2023, pp. 2159–2168.
  * [15] H. Cao, W. Zhu, Z. Chen, Z. Sun, and D. O. Wu, “Energy-delay tradeoff for dynamic trajectory planning in priority-oriented UAV-aided IoT networks,” _IEEE Transactions on Green Communications and Networking_ , vol. 7, no. 1, pp. 158–170, 2023.
  * [16] J. Liu, X. Zhao, P. Qin, S. Geng, Z. Chen, and H. Zhou, “Learning-based multi-UAV assisted data acquisition and computation for information freshness in WPT enabled space-air-ground PIoT,” _IEEE Transactions on Network Science and Engineering_ , vol. 11, no. 1, pp. 48–63, 2024.
  * [17] G. Li, B. He, Z. Wang, X. Cheng, and J. Chen, “Blockchain-enhanced spatiotemporal data aggregation for UAV-assisted wireless sensor networks,” _IEEE Transactions on Industrial Informatics_ , vol. 18, no. 7, pp. 4520–4530, 2022.
  * [18] Z. Guo, J. Peng, W. Xu, W. Liang, W. Wu, Z. Xu, B. Guo, and Y. I. Wu, “Minimizing redundant sensing data transmissions in energy-harvesting sensor networks via exploring spatial data correlations,” _IEEE Internet of Things Journal_ , vol. 8, no. 1, pp. 512–527, 2021.
  * [19] M. Fattoum, Z. Jellali, and L. N. Atallah, “Adaptive sampling approach exploiting spatio-temporal correlation and residual energy in periodic wireless sensor networks,” _IEEE Access_ , vol. 11, pp. 7670–7681, 2023.
  * [20] X. Xie, X. Liu, H. Qi, B. Xiao, K. Li, and J. Wu, “Geographical correlation-based data collection for sensor-augmented RFID systems,” _IEEE Transactions on Mobile Computing_ , vol. 19, no. 10, pp. 2344–2357, 2020.
  * [21] W. Xu, H. Shao, Q. Shen, J. Peng, W. Huang, W. Liang, T. Liu, X.-W. Yao, T. Lin, and S. K. Das, “Collect spatiotemporally correlated data in IoT networks with an energy-constrained UAV,” _IEEE Internet of Things Journal_ , vol. 11, no. 11, pp. 20 486–20 498, 2024.
  * [22] A. Gunawan, H. C. Lau, and P. Vansteenwegen, “Orienteering problem: A survey of recent variants, solution approaches and applications,” _European Journal of Operational Research_ , vol. 255, no. 2, pp. 315–332, 2016.
  * [23] Q. Yu, Y. Adulyasak, L.-M. Rousseau, N. Zhu, and S. Ma, “Team orienteering with time-varying profit,” _INFORMS Journal on Computing_ , vol. 34, no. 1, pp. 262–280, 2022.
  * [24] Q. Yu, C. Cheng, and N. Zhu, “Robust team orienteering problem with decreasing profits,” _INFORMS Journal on Computing_ , vol. 34, no. 6, pp. 3215–3233, 2022.
  * [25] P. Wan, G. Xu, J. Chen, and Y. Zhou, “Deep reinforcement learning enabled multi-UAV scheduling for disaster data collection with time-varying value,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 25, no. 7, pp. 6691–6702, 2024.
  * [26] P. Wan, S. Wang, G. Xu, Y. Long, and R. Hu, “Hybrid heuristic-based multi-UAV route planning for time-dependent data collection,” _IEEE Internet of Things Journal_ , vol. 11, no. 13, pp. 24 134–24 147, 2024.
  * [27] H. Wang, H. Liu, G. Cao, Z. Ma, Y. Li, F. Zhang, X. Zhao, X. Zhao, L. Jiang, N. J. Sanders _et al._ , “Alpine grassland plants grow earlier and faster but biomass remains unchanged over 35 years of climate change,” _Ecology Letters_ , vol. 23, no. 4, pp. 701–710, 2020.
  * [28] Y. Zeng, J. Xu, and R. Zhang, “Energy minimization for wireless communication with rotary-wing UAV,” _IEEE Transactions on Wireless Communications_ , vol. 18, no. 4, pp. 2329–2345, 2019.
  * [29] V. Cacchiani, C. Contreras-Bolton, and P. Toth, “Models and algorithms for the traveling salesman problem with time-dependent service times,” _European Journal of Operational Research_ , vol. 283, no. 3, pp. 825–843, 2020.
  * [30] D. Jiao, L. Wang, P. Yang, W. Yang, Y. Peng, Z. Shang, and F. Ren, “Unmanned Aerial Vehicle-enabled grassland restoration with energy-sensitive of trajectory design and restoration areas allocation via a cooperative memetic algorithm,” _Engineering Applications of Artificial Intelligence_ , vol. 133, p. 108084, 2024.
  * [31] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to algorithms_. MIT press, 2022.

|  Dongbin Jiao (Member, IEEE) received the B.S. degree in Information and
Computing Sciences from Lanzhou University of Technology, Lanzhou, China, in
2008, the M.Eng. degree in Software Engineering from Dalian Maritime
University, Dalian, China, in 2012, and the Ph.D. degree in Control Science
and Engineering at Xi’an Jiaotong University, Xi’an, China, in 2019. Since
March 2020, he has been an Lecture with the School of Information Science and
Engineering, Lanzhou University, China. His research interests include network
resource optimization, UAV networks, intelligent unmanned autonomous systems,
combinatorial optimization, evolutionary learning, and their application in
ecology and environment protection. He is currently a reviewer for more than
ten international journals, including TCOM, TTE, IoT-J, and serves as a TPC
member for several international conferences, such as IEEE ICC and ICCC.
---|---
|  Zihao Wang received the B.Eng. degree in Computer Science and Technology
from the Lanzhou University, China, in 2024. He is currently an engineer at
Geoming AI. His research interests include combinatorial optimization and
large language model.
---|---
|  Wen Fan received his B.Eng. degree in Computer Science and Technology from
Sichuan University, Chengdu, China, in 2019 and the M.Eng. degree in the same
major from Lanzhou University, Lanzhou, China, in 2024. He is currently an
engineer at Chery Automobile Co., Ltd. His research interests include IoT, UAV
path planning, and reinforcement learning.
---|---
|  Weibo Yang received the B.Eng. degree in Automation and the Ph.D. degree in
Control Science and Engineering from Xi’an Jiaotong University, Xi’an, China,
in 2013 and 2020, respectively. Since March 2022, he has been a Lecturer with
the School of Automobile, Chang’an University, China. His research interests
include vehicle routing problem, integer programming, and evolutionary
computation.
---|---
|  Peng Yang (Senior Member, IEEE) is a tenure-track assistant professor
jointly in the Department of Statistics and Data Science and the Department of
Computer Science and Engineering, Southern University of Science and
Technology (SUSTech), China. He received his B.Sc. and Ph.D. degrees in the
Department of Computer Science and Technology from University of Science and
Technology of China in 2012 and 2017, respectively. From 2017 to 2018, he was
a Senior Engineer in Huawei and then he joined SUSTech. His research interests
include Evolutionary Computation, Reinforcement Learning, and Multi-agent
Systems. He has published 37 papers in top journals and conferences. He has
served as the reviewer for top-tier journals (TEVC, TNNLS, TIE) and the PC
member of top conferences (NeurIPS, ICLR, and ICML). He is a member of IEEE
Computational Intelligence Society (CIS) Evolutionary Computation Technical
Committee.
---|---
|  Zhanhuan Shang is a full professor at College of Ecology, Lanzhou
University, China. His research interests include ecological restoration,
grassland management, rural sustainable development, carbon management, and
biodiversity on the Tibetan plateau. He has more than 200 publications in both
international and Chinese journals and books.
---|---
|  Shi Yan (Member, IEEE) received the B.S. and M.Eng. degrees from Lanzhou
University, Lanzhou, China, in 2001 and 2004, respectively, and the Dr.Eng.
degree from Akita Prefectural University, Akita, Japan, in 2010. From July
2004 to March 2007, he was an Assistant Professor with the School of
Information Science and Engineering, Lanzhou University. He was a Visiting
Researcher from January 2007 to March 2007 and a Visiting Research Fellow from
April 2010 to September 2010 with the Department of Electronics and
Information Systems, Akita Prefectural University. He was a Lecturer from
April 2007 to April 2012 and an Associate Professor from May 2012 to November
2020. He is currently a Professor with the School of Information Science and
Engineering, Lanzhou University. His research interests include uncertain
dynamical systems, robotics, machine learning, and multidimensional system
theory.
---|---


# Quantum Magnetic Properties, Entanglement for Antiferromagnetic Spin 1 and
3/2 Cluster Models

N. Ananikian<EMAIL_ADDRESS>AANL, Alikhanian Br. 2, 0036 Yerevan, Armenia
CANDLE, Acharyan 31, 0040 Yerevan, Armenia  Vl. V. Papoyan<EMAIL_ADDRESS>BLTP, JINR, 141980 Dubna, Russian Federation  Dubna State University, Dubna,
Russian Federation

###### Abstract

Entanglement, magnetization and magnetic susceptibility for 1D
antiferromagnetic spin $1$ and spin $\frac{3}{2}$ Heisenberg $XXX$ model with
Dzyaloshinskii-Moriya interaction, single-ion anisotropy and external magnetic
field on the finite chain are obtained.

##  I Introduction

Ferromagnetic and antiferromagnetic quantum magnetism has become an extremely
active area of research [1, 2]. Experimental data on the supramolecular
architecture, synthesis, magnetic susceptibility with dinuclear, tetranuclear,
heptanuclear, decanuclear, and polynuclear complexes of Cu2 ions in the
antiferromagnetic case are found [3]. The preparation of an antiferromagnetic
trinuclear Ni2 ionic complex with spin $1$ and magnetic susceptibility via
temperature have been obtained [4].

X-ray crystallographic structures, magnetic susceptibility from $2$ to $300K$
and the theoretical analysis of magnetism for a triangular and a tetranuclear
molecule consisting of linked high-spin cobalt (II) centers were described by
the inclusion of an antisymmetric exchange term (Dzyaloshinsky-Moriya
interaction) [5, 6].

Thermal non-classical correlations quantified by concurrence entanglement,
local quantum the uncertainty and quantum coherence in a four-qubit square
chain (tetranuclear copper (II) complex) of mixed ferromagnetic-
antiferromagnetic interactions between nearest neighboring spins with a
magnetic field were examined exactly in [7]. Magnetic susceptibility can
reveal spin entanglement between individual constituents of a solid, and
magnetization describes their local properties [8].

In this paper, we consider analytically the thermal entanglement,
magnetization and magnetic susceptibility of antiferromagnetic high-spin
dinuclear and trinuclear Ni2 (spin $1$) and Co2 (spin $\frac{3}{2}$) metal ion
complexes as a function of an external magnetic field and single-ion
anisotropy at low temperatures.

##  II Model and Definitions

The Hamiltonian for 1D antiferromagnetic Heisenberg XXX model with
Dzyaloshinskii-Moriya (DM) interaction and single-ion anisotropy in external
magnetic field given as

$\displaystyle H$ $\displaystyle=$ $\displaystyle
J\sum_{i=1}^{N}\vec{S}_{i}\vec{S}_{i+1}+G\sum_{i=1}^{N}(S_{i}^{x}S_{i+1}^{y}-S_{i}^{y}S_{i+1}^{x})+D\sum_{i=1}^{N}(S_{i}^{z})^{2}-B\sum_{i=1}^{N}S_{i}^{z}.$
(1)

where $J=1$ to fix the energy scale, $G$ is DM interaction parameter, $D$
represents uniaxial single-ion anisotropy, $B$ is the controlable parameter.
The local spin vector $S_{i}$ for each site has the components of the spin-1
operators:

$\displaystyle S_{x}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\begin{array}[]{lll}0&1&0\\\ 1&0&1\\\
0&1&0\end{array}\right),\hskip
11.38092ptS_{y}=\frac{1}{\sqrt{2}}\left(\begin{array}[]{lll}0&-i&0\\\
i&0&-i\\\ 0&i&0\end{array}\right),\hskip
11.38092ptS_{z}=\left(\begin{array}[]{lll}1&0&0\\\ 0&0&0\\\
0&0&-1\end{array}\right).$ (11)

The components of the spin $\frac{3}{2}$ operators are expressed as follows:

$\displaystyle S_{x}=\frac{1}{2}\left(\begin{array}[]{llll}0&\sqrt{3}&0&0\\\
\sqrt{3}&0&2&0\\\ 0&2&0&\sqrt{3}\\\ 0&0&\sqrt{3}&0\\\ \end{array}\right)\hskip
11.38092ptS_{y}=\frac{1}{2}\left(\begin{array}[]{llll}0&\sqrt{3}&0&0\\\
\sqrt{3}&0&2&0\\\ 0&2&0&\sqrt{3}\\\ 0&0&\sqrt{3}&0\\\ \end{array}\right)\hskip
11.38092ptS_{z}=\frac{1}{2}\left(\begin{array}[]{llll}3&0&0&0\\\ 0&1&0&0\\\
0&0&-1&0\\\ 0&0&0&-3\\\ \end{array}\right).$ (24)

Logarithmic negativity [9] is an entanglement measure defined as

$\displaystyle
LN=\log_{2}\left(\parallel\rho_{ab}^{T_{a}}\parallel_{1}\right)=\log_{2}\left(\sum_{k=1}|\lambda_{k}|\right)$
(25)

where $\lambda_{k}$ are the eigenvalues of the matrix $\rho_{ab}^{T_{a}}$.
$T_{a}$ denotes the partial pairwise transpose with respect to the first
system and $\rho_{ab}$ is partial trace of the density matrix of the whole
system between quantum states $a$ and $b$.

##  III Calculated Results

The entanglement of the 1D antiferromagnetic spin $1$ and spin $\frac{3}{2}$
Heisenberg $XXX$ model with Dzyaloshinskii-Moriya interaction, single-ion
anisotropy and an external magnetic field on finite chain with sizes $N=2$,
$N=3$ and $N=4$ is studied. The behavior of logarithmic negativity $LN$ as a
function of the external magnetic field parameter $B$ for spin $1$ and spin
$\frac{3}{2}$ is displayed in Fig. 1, for fixed $J=1$, $D=1$ and $G=1$. The
critical point $B_{c}$ at $B\geq B_{c}$ of the ground state, at which
entanglement disappears, is shown if $B>0$.

In Fig. 2 we present the behavior of logarithmic negativity $LN$ via DM
interaction parameter $G$ at fixed $J=1$, $D=1$ for spin $1$ at $B=5$ and for
spin $\frac{3}{2}$ at $B=9$. We fixed these values of $B$ near the $B_{c}$ for
spin $1$ and spin $\frac{3}{2}$ respectively.

In Fig. 1 and Fig. 2 (a, b, c) the upper curves show the logarithmic
negativity of $LN$ for spin $\frac{3}{2}$, and the lower curves for spin $1$
($N=2,3,4$). The same in plots (d, e, f) corresponds to a fixed temperature
$k_{B}T=0.1$.

Figure 1: The logarithmic negativity $LN$ versus of external magnetic field
parameter $B$ Figure 2: The logarithmic negativity $LN$ versus of DM
interaction parameter $G$

We found out also the phase diagrams of ground-state in the $D-B$ and the
$G-B$ planes at fixed value $J=1$ for $N=2$, see Fig. 3. The entanglement
region is located below the linear line and the adjacent curve for the
corresponding values of the parameter $G$ (Fig. 3 (a) and (b)). For example
for spin $1$ and $N=2$ at $G=1$ equations of the linear line and the adjacent
curve are obtained as follows:

$B=2+2\sqrt{2}+D\hskip
14.22636pt\left(\text{for}\,\,D>-\frac{2}{7}\left(2+3\sqrt{2}\right)\right),$
(26) $B=\frac{1}{2}\left(\sqrt{D^{2}-2D+17}+D+3\right)\hskip
14.22636pt\left(\text{for}\,\,D<-\frac{2}{7}\left(2+3\sqrt{2}\right)\right).$
(27)

The curve connecting the corner points shows the possible values $B$ and $D$
of the triple points for various quantities of $G$ and in the case of spin $1$
and $N=2$ is defined by:

$B=2\sqrt{\frac{1}{2}\left(D^{2}+\sqrt{(D+1)^{2}\left(D^{2}+1\right)}+D-1\right)+1}+D+2.$
(28)

Figure 3: Ground-state phase diagrams in the $D-B$ plane at fixed value $J=1$
and various values of $G$ (from top to bottom $G=1$, $G=\frac{1}{2}$, $G=0$),
plot (a) corresponds the spin $1$, plot (b) corresponds the spin
$\frac{3}{2}$. Plot (c) corresponds the ground-state phase diagrams in the
$G-B$ plane at fixed values $J=1$ and $D=1$. The entanglement area is between
the upper and lower curves for the spin $1$. The region between middle curves
corresponds the entanglement states, for the spin $\frac{3}{2}$.

The ground state of the system in the non entanglement region ($LN=0$) has a
wave function corresponding to the state with all spins down
($\Psi_{GS}=|\downarrow\downarrow....\downarrow\rangle$). The first nonzero
plateau ground state wave function for the spin $1$ for chain sizes $N=2$ and
$N=3$ is defined follow:

$\Psi_{GS}(N=2)=\frac{1}{\sqrt{2}}(|\downarrow
0\rangle+(\cos(\frac{\pi}{4})+i\cos(\frac{\pi}{4}))|0\downarrow\rangle)$ (29)
$\Psi_{GS}(N=3)=\frac{1}{\sqrt{3}}(|0\downarrow\downarrow\rangle+i|\downarrow
0\downarrow\rangle-|\downarrow\downarrow 0\rangle)$ (30)

The coefficients for the spin $\frac{3}{2}$ are the same with replacements in
the labels of vector of state $\downarrow$ by $-\frac{3}{2}$ and $0$ by
$-\frac{1}{2}$.

The entanglement values $LN$ as a function of temperature $T$ (from now on
$k_{B}=1$) at fixed $J=1$, DM interaction parameter $G=1$ and single-ion
anisotropy $D=1$ are shown in Fig. 4

Figure 4: The upper curves represent the behaviour of entanglement amount $LN$
for the spin $\frac{3}{2}$, and lowest curves show the same for the spin $1$.
Plots (a), (b), (c) correspond $N=2$, $N=3$, $N=4$, respectively.

The behavior of magnetization and magnetic susceptibility of the chain size
$N=2$ are presented in Fig. 5. As it was found, the plateau of magnetization
and the plateau of logarithmic negativity coincide. For chains of size $N=3$
and $N=4$, we get the results that are qualitatively similar.

Figure 5: The logarithmic negativity (red curve), magnetization (orange curve)
and magnetic susceptibility (blue curve) for $N=2$ as a function of $B$ at
$J=1$, $D=1$, $G=1$ and $k_{B}T=0.05$. Plots (a) and (b) corresponds spin $1$
and $\frac{3}{2}$, respectively.

N. A. acknowledges the receipt of the grant No. SCS 21AG-1C006.

## References

  * [1] T. Nagamiya, K. Yosida, R. Kubo, Antiferromagnetism, Advances in Physics 4 (13) (1955) 1-112. DOI.org/10.1080/00018735500101154.
  * [2] I. M. Georgescu, S. Ashhab, and F. Nori, Quantum Simulation, Rev. Mod. Phys. 86, 153 (2014). DOI: 10.1103/RevModPhys.86.153.
  * [3] S. S. Tandon, S. D. Bunge, N. Patel, E. C. Wang and L. K. Thompson, Self-Assembly of Antiferromagnetically-Coupled Copper(II) Supramolecular Architectures with Diverse Structural Complexities, Molecules 25 (2020) 5549(pp 31). DOI:10.3390/molecules25235549.
  * [4] N. M. Bonanno, A. J. Lough, M. T. Lemaire, Atrinuclear nickel(II) cluster containing a ditopic redox active ligand: Structural and magnetic properties, Polyhedron 183 (2020) 114536 (pp 6). DOI:10.1016/j.poly.2020.114536.
  * [5] J. F. Berry, F. A. Cotton, C. Y. Liu, T. Lu, C. A. Murillo, B. S. Tsukerblat, D. Villagran, and X. Wang,Modeling Spin Interactions in a Cyclic Trimer and a Cuboidal Co4O4 Core with Co(II) in Tetrahedral and Octahedral Environments, J. Am. Chem. Soc. 127 (13) (2005) 4895–4902. DOI: 10.1021/ja044185b.
  * [6] H. Arian Zad, R. Kenna and N. Ananikian, Magnetic and thermodynamic properties of the octanuclear nickel phosphonate-based cage, Physica A 538 (2020) 122841. DOI: 10.1016/j.physa.2019.122841.
  * [7] F. Benabdallah, S. Haddadi, H. A. Zad, M. R. Pourkarimi, M. Daoud, N. Ananikian Pairwise quantum criteria and teleportation in a spin square complex, Scientific Reports 12(1) (2022) 1-12, DOI: 10.1038/s41598-022-10248-2.
  * [8] M. Wieniak, V. Vedral and C. Brukner, Magnetic susceptibility as a macroscopic entanglement witness, New J. Phys. 7 (2005) 258 (pp 8). DOI: 10.1088/1367-2630/7/1/258.
  * [9] G. Vidal, R. F. Werner, A computable measure of entanglement. Phys. Rev. A. 65 (3) (2002) 032314 (pp11). DOI: 10.1103/PhysRevA.65.032314.