# Data Collection System of IoT Based on the Coordination of Drones and Unmanned Surface Vehicle

Authors: Zhigang Wang; Liqin Tian; Lianhai Lin; Jianfei Xie; Wenxing Wu; Yinghua Tong
Journal: Journal of Advanced Transportation
 (2023)

---

## Abstract

With the continuous renewal and rise of various flight equipment, this article designs a method of water data collection, which is realized through the coordination of an unmanned surface vehicle (USV) carrying unmanned aerial vehicles (UAVs, commonly called drones). In reality, multiple UAVs take-off and landing sites, energy consumption, and other complex issues closely related to USV recovery, UAVs must be considered. If mixed integer linear programming (MILP) is used directly, it is difficult to get satisfactory results in an acceptable time range. Therefore, a heuristic algorithm is proposed to solve the problem of data collection by these devices, which can not only quickly solve the large-scale collaborative optimization problem, but also rationally utilize the total energy consumption of the equipment. The effectiveness of the proposed algorithm is verified and analyzed by experimenting a different number of monitoring nodes, different number of UAVs and different task time. It can not only shorten the cycle of data acquisition task, but also reduce the waiting time of the UAV and USV.


---

## Body

## 1. Introduction

Unmanned equipment with strong flexibility and extensibility has been extensively utilized in monitoring the field [1, 2]. This article focuses on their application in monitoring the field, especially the use of unmanned aerial vehicles (UAVs) [3, 4] and unmanned surface vehicle (USV) [5, 6]. In recent years, environmental monitoring, water management, water emergency search and rescue, and resource exploration based on unmanned equipment have become a popular research direction [7–9]. The USV is capable of operating in hazardous areas, shallow water, and other locations inaccessible to UAVs [10], and can expand the search area in limited time. By mounting high-definition multifunctional cameras, high-precision multispectral equipment, and hyperspectral equipment on the UAVs, real-time monitoring data can be transmitted to the monitoring station, and the management department can efficiently combine monitoring equipment such as satellites to further use the collected data [10].Although UAVs have limited cruising ability, they have larger monitoring view compared to the USV [11, 12]. USV-mounted monitoring equipment has a better performance in monitoring the target area only in close proximity [13]. Therefore, coupling these two unmanned devices and creating a joint system to collect data through multidirectional monitoring developed a new direction for data collection over water [14–16]. In this joint USV-UAV platform, the data information from UAVs can be sent to the relay station of the USV for processing before forwarding. When UAVs are low on energy, it can land on the USV for charging, battery change, or refueling operations. By complementing each other’s strengths in this way, it has ensured that they can accomplish monitoring tasks in more complex and larger areas.The MFSTSP problem of UAVs on land in coordination with unmanned vehicles is an extension of the classic “Last Mile” problem, which was first proposed in [17]. In recent years, more and more scholars have studied the MFSTSP problem and put forward different precise solutions and heuristic algorithms to solve the MFSTSP problem of unmanned vehicles and multiple UAVs. In this article, the multiflight sidekick data collection problem (MFSDCP) is proposed, inspired by the data collection problem of UAV-USV joint monitoring waters and the MFSTSP problem. In MFSDCP, each UAV can be launched from the USV to collect data from sensor monitoring points, and drones can look for landing spots ahead of time under permitted high energy conditions. The goal of the problem is to complete data acquisition tasks at all monitoring sites and return to the monitoring stations in the shortest time using UAVs and USVs.For environmental monitoring and data acquisition of lakes, rivers, and oceans, the collaborative multiview approach of UAVs and USVs has attracted extensive attention. The “Last Mile” distribution coordination method has significant effectiveness in distribution. The combination of the two methods can improve the efficiency of water area monitoring and management. However, the cooperative execution of multiple UAVs and USVs is a complicated task planning problem, which needs to consider the arrival of UAVs and USVs, whether USVs can recover UAVs in advance and energy consumption, and so on. This article establishes the architecture of MFSDCP for this problem. The main contributions of this article are as follows:(1)
An IoT monitoring model based on USVs and UAVs is designed. A function with the completion time and waiting time of UAVs and USVs as the objective is established in the model, and the formulas of each phase are provided.(2)
The heuristic method for UAVs and USVs to cooperate to complete data acquisition task is established, including the path query method of USVs, the cruise sequence of UAVs, and the final solution strategy of both cooperation.(3)
The strategy of UAVs’ early landing recovery is further studied to save the overall energy consumption of UAVs and improve the mission efficiency. Simulation experiments were designed to compare the performance of the proposed algorithm with that of the exact solution method. The effectiveness of the proposed heuristic method in large-scale MFSDCP problems was verified by simulation experiments.The rest of this article is structured as follows: Section2 briefly describes the application of UAVs in the field of monitoring and the progress in USVs. Section 3 establishes the MFSDCP problem model based on monitoring. Section 4 establishes the objective function and formula conditions. Section 5 proposes a heuristic method to solve the cooperative monitoring between UAVs and USVs. Section 6 designs the simulation experiment and discusses the result. Followed by concluding the work of this article in Section 7.


## 2. Related Work

UAVs have become very popular in nonmilitary applications, such as water resource exploration [18], smart city [19], agricultural monitoring [20], terrain exploration [21], water quality measurement [20], and many other mature studies. As drones are not restricted by congested roads, they have received great attention in parcel delivery. The collaborative delivery of trucks and UAVs can be regarded as the promotion of VRP, a classic vehicle routing problem, in [21], but it is far more complicated than VRP. Murray and Chu [17] defined the FSTSP for the first time for UAVs and truck delivery, and designed a special heuristic algorithm to serve the target point.Due to the rapid development of UAVs, collaborative delivery on land combined with UAVs has become a hot research topic [24]. The combination problem of UAVs and ground vehicle is divided into three basic models according to the change of the number. These models are defined as traveling salesman problem with drone (TSP-D), traveling salesman problem with multiple drones (TSP-mD), and multiple traveling salesman problem with drones (MTSPD). In this article, UAVs and unmanned ship is a derivative problem of these three models. All these research studies will focus on solving the traveling salesman problem, but different fields involve different emphases. For example, [25, 22] solve freight vehicle routing with reliable link travel times, travel time forecasting, and dynamic routes design for emergency vehicles.Firstly, Murray and Chu [17] first proposed that this collaborative model belongs to single-vehicle mapping model. This case became the basis for the problem of collaboration, in which a drone completes a mission at a target point by rendezvousing with an unmanned vehicle at the next target point. Furthermore, on the premise of sharing most of the assumptions, [23] changed the method of taking flight distance as a formula in the original scheme, adopted UAVs flight time as a formula, and adopted dynamic programming and local search to solve the problem.In the TSP-mD model, Mourelo Ferrandez et al. [24] developed time-saving and energy-efficient methods to optimize the number of UAVs, but the flight and landing of UAVs must be unified. Salama and Srinivas [25] use the method of recovering drones at different locations. In [26], a single vehicle was used as a mobile warehouse to cover a larger cluster as possible, and a collaborative distribution problem of 100 customers was realized by using the heuristic method and k-means clustering. In [27], a multipoint access UAV system is designed to balance the carrying capacity and endurance of UAVs and carrying out different collaborative schemes for service areas with different densities.The complexity of MTSPD in the multitruck multi-UAV mode is much higher than that of TSP-mD. Due to the multiple UAVs and vehicle problem, the complexity increases dramatically when the single-vehicle problem is extended to the multivehicle problem. Therefore, most studies do not consider the task assignment relationship between vehicles and UAVs, and only need to consider the mapping between them to confirm the return of vehicles.From the view of the logic method of UAVs and the vehicle combining site, TSPD can be divided into four basic operating modes [32], the drones are completed by vehicles start distribution and must be returned to the same car, UAVs starting from vehicles’ complete distribution return different vehicles, UAVs starting from the warehouse return, and the return of the UAV from the warehouse. However, in practical application, it may be combined by a variety of modes, but there are few research studies on this mode, and the research and expansion space of mode combination is very large. In addition to the flight restrictions of such UAVs, [17, 23] have solved the time problem of collaborative task execution to varying degrees, but they cannot solve some problems of multi-UAVs collaboration. However, [27] solved the problem of UAV energy consumption, but could not solve the problem of how to coordinate multiple UAVs at multiple points. It can be seen that the research of UAV collaborative planning task needs to be constantly improved.It can be seen that the combination of UAVs and truck is relatively easy to implement, but the prospect of fully automated research is still broad. Fully automated distribution or monitoring of the USV for other tasks is a difficult but meaningful problem. In terms of underwater UAVs, [28] designed a stochastic optimization aided energy-efficient information collection in Internet of underwater things’ network systems. Hou et al. [29] proposed the environment-aware AUV trajectory design and resource management for multitier underwater computing. The equipment that supports working on the water is constantly being updated, DJI listed DJI Airport in February 2022, consolidating the problem of coordinated distribution on land. It can also be seen that one reason why UAVs and USVs are rarely studied is that, unlike the four degrees of freedom on the ground, it is very difficult to accurately land on USVs by controlling high dimensions. For the UAVs landing combination problem, RTK-GPS method, GPS-INS method, and UGV-UAV method were proposed in [30–32]. However, they cannot be directly used to solve the problem of USV landing. Shao et al. [14] proposed the method of USV-UAV to solve the problem of precise landing, and designed the detailed equipment structure as shown in Figure 1. In more complex monitoring environments, [33] designed UAV-USV-UUV networks for cooperative target hunting.Figure 1
USV-UAV structure.Due to the urgent application requirements, the application of USV-UAV combination in water appeared for the first time in the field of emergency response [8], and the USV-UAV combination system was proposed for the first time. It is necessary to design a framework to simulate paths and route choices of freight vehicles as described in [34] because there is no accurate mission framework for UAVs and USVs. As UAV is the main equipment for data monitoring and transmission, there have been some research studies on the reliability of UAV data transmission. In order to ensure the safe transmission of UAVs during the execution of tasks, NOMA-based network and reinforcement learning are proposed in [35, 36]. AR. Drone technology is used to simulate the control of USVs and UAVs for different tasks [37]. In [38], separate control of USVs and UAVs is used for image acquisition, and later, fusion analysis of the two data is performed. It can be seen that the mission of using multiple UAVs and USVs to collect data over a large area has not been thoroughly studied so far. However, nowadays UAV-assisted MEC technology, as referred to in [39], has been gradually matured to facilitate more efficient data acquisition.In terms of the “one-kilometer problem” on the ground, where conditions are relatively easy to meet, the cooperation between UAVs and unmanned vehicle is a relatively new problem for material distribution in 2015. The use of unmanned vehicles and unmanned aerial vehicles is just beginning, and collaboration with multiple UAVs and USVs is a new field. Therefore, in the initial stage of UAV and USV cooperative planning research, the challenge is not only the development and innovation of hardware equipment, but also the design and simulation of optimization theory of the cooperative process.


## 3. The Problem Model

This section provides a formal model of MFSDCP. Since this problem has the same core characteristics as the path planning problem, it can be seen that MFSDCP is a NP-hard problem. The critical issue of UAVs and USVs is that they monitor target points and assign tasks, and UAVs can be recovered in advance. This article makes the following assumptions:(1)
This article does not consider the details of UAVs and USV hardware design, including materials, engine type, and waterproofing level, and only uses some important equipment characteristics, such as speed and power consumption(2)
The mechanical operations of UAVs taking off and landing on the USV do not need to be given in detail, only the time they consume need to be known(3)
Different from the “one-kilometer problem,” the USV in the MFSDCP problem no longer carries packages of different weights, and the speed of departure and recovery is no longer affected by whether there is a load balance(4)
Since the USV’s path is almost impervious to obstacles over water, the path between adjacent points is closer to a straight line than it is on landLetM be the set of monitoring sites, each monitoring site is monitored once during the cruise, where M=1,2…,m. Each monitoring site must perform sensing tasks through one of the heterogeneous UAVs represented by set D. A particular monitoring site i∈M is said to be “drone-able” by UAVs d∈D, and therefore the monitoring site meets the formula conditions perceived by D; it belongs to the M^v. This classification can be a function of several factors, including the length of stay at the monitoring site, the weight of the monitoring equipment, and the battery capacity of the monitoring equipment.Although each drone’s hardware may be different, each drone can fly to more than one monitoring site at a time as long as its power permits. The drones can be launched directly from the warehouse for surveillance missions, and they need to be launched from the USV, after the USV leaves the monitoring station. While each drone can be launched multiple times after being recharged or recharged on the USV, it can only be launched once from each monitoring site that the USV receives. Similarly, a drone can be retrieved from the monitoring station, or by the USV at the monitoring site, but not from the location where it was launched. When a drone returns to the USV, it can either be loaded onto the USV or relaunched from the USV. It is assumed that the USV can transport all available UAVs at once, although the USV can only launch or retrieve one UAV at a time. Because the USV can launch and retrieve (and relaunch) multiple UAVs from particular monitoring sites, it is important to carefully coordinate these activities to avoid mid-air collisions.To characterize the basic route structure of the MFSDCP, we define the set of all sites in the route asN=0,1,…,m+1, sites 0 and m+1 represent all USV segments departing and returning from the USV. And the USV can only start at site 0 and must return to site m+1. The set of sites from which the USV can leave is expressed as N0=0,1,…,m, while N+=1,2,…,m+1 describes all sites’ sets that the USV may access. Table 1 presents the symbol and variable associated with USVs.Table 1
The symbol and variable table for USV.
Symbolic nameMeaningxijThe path of the USV from nodei to node j, xij=1 indicates that the path exists, and xij=0 does not existτijSThe time of the USV from nodei∈N0 to node j∈N+σsThe unit time the USV needs to collect datauiIt represents the order in which it arrives at nodei∈N+tilSThe time of the USV arrival at monitoring sitei∈N0ti,kcSIt represents the time the USV was at the monitoring sitesi∈N0 and k∈N+titSThe time the unmanned boat left the monitoring siteThe travel time of the USV along the route from nodei∈N0 to node j∈N+ is τijS. Similarly, τijD represents the time for the UAVs to fly from node i∈N0 to node j∈N+.When UAVsd∈D is launched from node i∈N0, it takes sv,iL units of time. This launch time is indexed to d to include UAVs with loading time differences. The launch time is also indexed on the launch site; launching from the monitoring station may take a different amount of time (e.g., maybe the drone has already automatically replaced a new battery in the monitoring station). For UAVs d∈D retrieved at node k∈N+, the recovery time is also defined as sv,kR. Table 2 presents the symbol and variable associated with UAVs.Table 2
The symbol and variable table for UAV.
Symbolic nameMeaningpijIt represents whether the travel of UAVs from nodei∈N0 to node j exists. If so, pij=1; otherwise, pij=0.yijkDIt represents whether the travel of UAVs from nodei∈N0 to node i∈N0 and then to point k exists. If this travel exists, yijkD=1; otherwise, yijkD=0.τijDThe time of the UAV from nodei∈N0 to node j∈N+.σdj′The unit time the UAVd∈D needs to collect data at site j∈N+.sv,iLThe time consumed when the UAVd∈D is launched from node i∈N0.sv,kRThe time consumed when the UAVd∈D is recovered from node k∈N0.d,i,j,k∈FIt represents the sequence set of monitoring tasks performed by UAVs.edijkThe duration of a drone flight.EdavailTotal UAV energy.EdijkminA drone needs the least amount of energy to perform a sequence mission.TdijkminThe time taken by the UAV to perform a sequential task.ϑThe power consumed by the drone.tilDThe drone’s landing time at the monitoring sitei∈N0.ti,kcDIt represents the time for the UAV to fly from monitoring pointi∈N0 to k∈N+.titDThe time the drone takes off from the monitoring sitei∈N.zd1,d2,kRzd1,d2,kR = 1 means d1∈D lands before d2∈D arrives, otherwise zd1,d2,kR = 0.zd1,d2,kLzd1,d2,kL means d1∈D take off before d2∈D arrives, otherwise zd1,d2,kR = 0.At the nodek∈N+, the USV needs to consume σk units of time to collect data, and when the base station has no data to collect σm+1≡0. Similarly, UAVs v∈V requires σvk′ units time to perform the data collection task at node k∈N+, where σv,m+1′≡0. The UAV monitoring sequence is v,i,j,k∈F.The UAV can only be recovered or launched when the USV is stopped, and cannot be launched until the USV has left the base monitoring station. The USV can perform missions or navigate water while the UAV flies to a target site. Referring to the traditional cooperative delivery problem, if the UAV reaches the next destination before the USV, it must hover and wait for the UAV to arrive. This is bound to consume a lot of energy in practical application. Since the energy consumption of the drone while waiting is not low [40], the power of the drone is very restricted. When the USV reaches its next destination ahead of the schedule, it needs to wait for the mission or UAVs in flight. Apparently, which UAVs’ waiting depends on how long it takes them to complete their task and how fast they travel. When the UAV is more than just one, the sequence of UAVs and USV tasks at all nodes must be calculated in detail to ensure that the UAV can perform monitoring tasks with limited power. Wireless electrical signal transmission is used between the UAV and the USV to execute instructions, and specific operations when they perform node data collection can be specially set according to different needs, such as image data collection or sensor data detection. A feasible solution for data acquisition by 2-UAVs and USV is shown in Figure 2.Figure 2
Coordination of drones and unmanned surface vehicles.In this article, the endurance time of the UAVs is expressed byevijk. When the UAV cruises from the launch site to the recovery site, the time cannot exceed evijk. The farther the UAV flies, the faster it consumes energy. In addition, the work in [31] obtained the linear function of the flight speed, weight, and operation time of the UAV with load.


## 4. Model of the MFSDCP

The MFSDCP problem proposed in this article is an extension of the FSTSP, which is further improved to accommodate data collection. To collect data simultaneously in more scenarios (hyperspectral, infrared imaging, and meteorological) and complete the acquisition task faster. The objective function with minimum time cost and the formulas of path and time allocation are designed. Prior to the work, we defined some binary variables:xij=1 indicates the travel of the USV from node i to node j, 0 if this is not the case; pij=1 indicates the travel of the USV from node i∈N0 to node j, otherwise 0; yvijk=1 indicates the travel of the d from node i∈N0 to node j; the arrival time of node i∈N0 of the USV is defined as tilS; the landing time of node i∈N0 of the UAV is defined as tilD; ticS indicates the time of data collection at node i∈N+; and ticD indicates the time of data collection at node i∈N0. The completion time of node i∈N of the USV is titS; the completion time of node i∈N of the UAV is titD; zd1,d2,kR equals 1 indicates d1∈D recovers before d2∈D at k∈N+, otherwise 0; zd1,d2,kL equals 1 indicates the d1∈D launched before d2∈D at k∈N+, otherwise 0; and ui indicates the visit order of node i∈N+. In this case, the time needed to fly the UAVs from node i to node k is divided into the following stages:(1)Tdijkmin=tdklD−tditD.We will provide a method calculation method of UAVs waiting USV. In each phase of flight, the energy consumed by each UAV is different. Therefore, when the UAV completes a cruise, the minimum energy consumption isEvijkmin. Assuming that the total energy of a UAV is Evavail, the endurance value of the UAV is calculated by the obtained Evavail−Evijkmin.(2)edijk=Tdijkmin+1ϑ∗Edavail−Edijkmin.Here, ϑ represents the power consumed by the UAV while waiting for the USV. So Evavail and Edijkmin calculation of the UAV waiting time must meet the condition Edavail≥Edijkmin.


### 4.1. Objective Function

According to the problem description of data collection by UAVs and USVs, the objective function is to minimize the time to complete the acquisition task, that is, the time when all UAVs and USVs return to the monitoring station. To make the objective function more efficient in this kind of problem, [33] divides the objective function into two parts. Therefore, this article also designs an equivalent function for the target of the data acquisition task. One part is the travel time of the USV during the entire mission, and the other part is the waiting time generated during the mission.(3)minz=∑i,j∈NxijτijD+∑i∈Nwi,(4)wi≥tilS−titS.Formula (3) represents the objective function of completing the collaborative acquisition task, namely the total time of flight and waiting. Formula (4) represents the formula on the waiting time.


### 4.2. Routing and Sortie Constraint

In this section, we model the USV route formulas and the UAV flight formulas.(5)∑i∈N0i≠jxij+∑i∈N0,k∈N+,d∈Dd,i,j,k∈FyijkD=1∀j∈M,(6)∑j∈N+x0j=1,(7)∑i∈N0xi,m+1=1,(8)∑i∈N0i≠jxij=∑k∈N+k≠jxjk=1∀j∈M,(9)∑j∈Mj≠i∑k∈N+d,i,j,k∈Fydijk≤1∀i∈N0,∀d∈D,(10)∑i∈N0,j∈Mi≠k,d,i,j,k∈Fydijk≤1∀k∈N+,∀d∈D(11)2yijkD≤∑h∈N0h≠ixhi+∑l∈Ml≠kxlk∀d∈D,i∈M,j∈M:j≠k,k∈N+:d,i,j,k∈F,(12)y0jkD≤∑h∈N0h≠kxhk∀d∈D,j∈M,k∈N+:d,0,j,k∈F,(13)uk−ui≥1−m+21−∑j∈Md,0,j,k∈FyijkD∀d∈D,∀i∈M,k∈N+:k≠i,(14)ui−uj+1≤m+21−xij∀i∈M,j∈N+:j≠i,(15)ui−uj≥1−m+2pij∀i∈M,j∈M:j≠i,(16)uk−ui≤m+21−pij−1−m+2∀i∈M,j∈M:j≠i,(17)pij+pji=1∀i∈M,j∈M:j≠i.Formula (5) ensures that every task node can be collected once. Formulas (6) and (7) require the USV to leave or return to the monitoring station only once. Similarly, the use of formulas (9) and (10) for UAVs stipulates that each UAV can only be launched and retrieved once from a monitoring node or station. In order to ensure the conservation of flow, formula (8) restricts the entry and exit balance from which the USV can only start again from the visiting node during the cruise. Formula (11) indicates that the node of launching and receiving UAVs must be the node of USV cruise. Formula (12) ensures that node k that the UAV arrives at after leaving the monitoring station is also the cruise node of the USV. Formula (13) ensures the sequence in which the USV visits the launching UAV node i and the collecting UAV node k. The ui and pij in formulas (15)–(17) ensure the travel order of the USV.


### 4.3. Timing Constraint

#### 4.3.1. UAVs’ Timing Constraint

The UAV’s flight time is limited, so we use the following formulas to determine the time when the UAV will depart from the USV or monitoring station to the monitoring site and return:(18)tdltD≥tdklD−M3−∑j∈Md,0,j,k∈Fj≠lyijkD−∑m∈Mm≠im≠km≠l∑n∈N+d,0,j,k∈Fn≠in≠kylmnD−pil∀d∈D,∀i∈N0,k∈N+:k≠i,l∈M:l≠i,l≠k,(19)tditD≥tdilD+sd,iL−M1−∑j∈Mj≠i∑k∈N+d,0,j,k∈FyijkD∀d∈D,i∈N0,(20)tditD≥tilS+sd,iL−M1−zd,0,iL∀d∈D,i∈N0,(21)tditD≥ticS+sd,iL−M1−z0,d,iL∀d∈D,i∈N0,(22)tditD≥td2itD+sd,iL−M1−zd2,d,iL∀d∈D,d2∈D:d2≠d,i∈N0,(23)td2itD≥tdilD+sd2,iL−M1−zd,d2,i″∀d∈D,d2∈D:d2≠d,i∈M.To prevent UAVs sorties from overlapping, formula (18) is used to restrict the UAV from the next node l of i to start earlier. This formula only works if the drone is recovered at point k, and there is a launch point l. When the UAV is ready to take off to collect data, formulas (19)–(23) ensure the start time of UAVs’ launch before data collection. Formula (19) states that the UAV cannot take off until the USV arrives, and the arrival time of node tdilD is an invalid value when a UAV is carried by the USV to point i. Formula (20) states that the USV cannot launch until the USV arrives at the acquisition point i and until the data collection is completed. Formula (21) states that the UAVs cannot launch from i while the USV is collecting data until the truck has completed data acquisition. Formula (22) ensures that d launches after d2 is launched. Formula (23) ensures that d2 launches after d is landed.(24)tdjlD≥tditD+τdij′−M1−∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,i∈N0:i≠j,(25)tdjtD≥tdjlD+σdj′∑i∈N0i≠j∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,(26)tdklD≥tklS+sd,kR−M1−zd,0,kR∀d∈D,k∈N+,(27)tdklD≥t¯d+sd,kR−M1−z0,d,kR∀d∈D,k∈N+,(28)tdklD≥td2klD+sd,kR−M1−zd2,d,kR∀d∈D,d2∈D:d2≠d,k∈N+,(29)tdklD≥td2klD+sd,kR−M1−zd2,d,k′∀d∈D,d2∈D:d2≠d,k∈M,(30)tdklD≥tdjtD+τjkD+sd,kR−M1−∑i∈N0d,0,j,k∈FyijkD∀d∈D,k∈N+,j∈M:j≠k,(31)tdklD−sd,kR−tditD≤eijkD+M1−yijkD∀d∈D,i∈N0,k∈N+:d,0,j,k∈F.For the monitoring point of UAVs, in the process of flying fromi to task site j and from j to k, formulas (24) and (25) control the time when the UAV arrives at the current node and returns to the next node during data collection. When the UAV reaches a rendezvous point with the USV, formula (26) states that the arrival of the USV first is a necessary condition for the UAV to land. If the USV is collecting data, formula (27) requires that the USV collect data before landing. The imminent landing of d colliding with d2, formula (28) states that the arrival time of d is later than the arrival time of d2. Formula (29) states that d arrives later than d2 has started. For a drone surveillance sequence yijkD, formula (30) stipulates that d cannot directly land on node k, but must take off and travel from node j. Formula (31) limits the endurance of the UAV from node i to node k through j.


#### 4.3.2. USV Timing Constraint

When the USV arrives at the monitoring node, the formula conditions for data collection and departure from the monitoring node are as follows:(32)tjlS≥titS+τijS−M1−xij∀i∈N0,j∈N+:j≠i,(33)tkcS≥tklS+σk∑j∈N0j≠kxjk∀k∈N+,(34)tkcS≥tdklD+σk−M1−zd0kR∀d∈D,k∈N+,(35)tkcS≥tklS+σk−M1−zd0kL∀d∈D,k∈M.When the UAV arrives at the monitoring node, formula (32) states that the USV can only travel to j when it leaves i. Formula (33) ensures that the USV completes the data collection later than the time it arrives at the monitoring node. Formula (34) stipulates the sequence of data acquisition and UAVs’ recovery by USVs. If zv,0,kR=1, the UAV needs to be recovered first. Formula (35) specifies the sequence in which USV performs data acquisition and UAVs’ recovery. If zv,0,kL=1, the UAV needs to be launched first.(36)tktS≥tkcS∀k∈N+,(37)tktS≥tdklD−M1−∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,(38)tktS≥tdktD−M1−∑l∈Ml≠k∑m∈N+d,0,j,k∈FyijkD∀d∈D,k∈N0.When the UAV leaves the monitoring node, formula (36) prevents the USV service from leaving the monitor node k before completion. Formula (37) prevents the USV from leaving early if a UAV needs to land. Formula (38) prevents the USV from leaving early if there is a UAV to start.


### 4.4. Sequencing of Retrievals, Launches, and USV Service

This section establishes formulas on binary decision variables to determine the order of execution at each monitoring point. In the preceding decision variables, we use thezR decision variable representing UAVs’ recovery, which needs to meet the following formulas:(39)z0dkR+zd0kR=∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,(40)zd,d2,kR≤∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,d2∈D:d2≠d,(41)zd,d2,kR≤∑i∈N0i≠k∑j∈Md,0,j,k∈Fyd2ijk∀d∈D,k∈N+,d2∈D:d2≠d,(42)zd,d2,kR+zd2,d,kR≤1∀d∈D,k∈N+,d2∈D:d2≠d,(43)zd,d2,kR+zd2,d,kR+1≥∑i∈N0i≠k∑j∈Md,0,j,k∈Fyijkd+∑i∈N0i≠k∑j∈Md2,0,j,k∈Fyijkd2∀d∈D,k∈N+,d2∈D:d2≠d.Formula (39) specifies whether there is a USV that needs to be landed on the k node retrieval. Formula (40) states that zd,0,kR cannot be 1 without retrieving d2. Formula (41) states that zd,0,kR cannot be 1 if d2 is not retrieved. Formula (42) declares that either d or d2 is retrieved at k, otherwise neither is retrieved. Formula (43) states that only one can be retrieved before the other when retrieving d and d2.


## 4.1. Objective Function

According to the problem description of data collection by UAVs and USVs, the objective function is to minimize the time to complete the acquisition task, that is, the time when all UAVs and USVs return to the monitoring station. To make the objective function more efficient in this kind of problem, [33] divides the objective function into two parts. Therefore, this article also designs an equivalent function for the target of the data acquisition task. One part is the travel time of the USV during the entire mission, and the other part is the waiting time generated during the mission.(3)minz=∑i,j∈NxijτijD+∑i∈Nwi,(4)wi≥tilS−titS.Formula (3) represents the objective function of completing the collaborative acquisition task, namely the total time of flight and waiting. Formula (4) represents the formula on the waiting time.


## 4.2. Routing and Sortie Constraint

In this section, we model the USV route formulas and the UAV flight formulas.(5)∑i∈N0i≠jxij+∑i∈N0,k∈N+,d∈Dd,i,j,k∈FyijkD=1∀j∈M,(6)∑j∈N+x0j=1,(7)∑i∈N0xi,m+1=1,(8)∑i∈N0i≠jxij=∑k∈N+k≠jxjk=1∀j∈M,(9)∑j∈Mj≠i∑k∈N+d,i,j,k∈Fydijk≤1∀i∈N0,∀d∈D,(10)∑i∈N0,j∈Mi≠k,d,i,j,k∈Fydijk≤1∀k∈N+,∀d∈D(11)2yijkD≤∑h∈N0h≠ixhi+∑l∈Ml≠kxlk∀d∈D,i∈M,j∈M:j≠k,k∈N+:d,i,j,k∈F,(12)y0jkD≤∑h∈N0h≠kxhk∀d∈D,j∈M,k∈N+:d,0,j,k∈F,(13)uk−ui≥1−m+21−∑j∈Md,0,j,k∈FyijkD∀d∈D,∀i∈M,k∈N+:k≠i,(14)ui−uj+1≤m+21−xij∀i∈M,j∈N+:j≠i,(15)ui−uj≥1−m+2pij∀i∈M,j∈M:j≠i,(16)uk−ui≤m+21−pij−1−m+2∀i∈M,j∈M:j≠i,(17)pij+pji=1∀i∈M,j∈M:j≠i.Formula (5) ensures that every task node can be collected once. Formulas (6) and (7) require the USV to leave or return to the monitoring station only once. Similarly, the use of formulas (9) and (10) for UAVs stipulates that each UAV can only be launched and retrieved once from a monitoring node or station. In order to ensure the conservation of flow, formula (8) restricts the entry and exit balance from which the USV can only start again from the visiting node during the cruise. Formula (11) indicates that the node of launching and receiving UAVs must be the node of USV cruise. Formula (12) ensures that node k that the UAV arrives at after leaving the monitoring station is also the cruise node of the USV. Formula (13) ensures the sequence in which the USV visits the launching UAV node i and the collecting UAV node k. The ui and pij in formulas (15)–(17) ensure the travel order of the USV.


## 4.3. Timing Constraint

### 4.3.1. UAVs’ Timing Constraint

The UAV’s flight time is limited, so we use the following formulas to determine the time when the UAV will depart from the USV or monitoring station to the monitoring site and return:(18)tdltD≥tdklD−M3−∑j∈Md,0,j,k∈Fj≠lyijkD−∑m∈Mm≠im≠km≠l∑n∈N+d,0,j,k∈Fn≠in≠kylmnD−pil∀d∈D,∀i∈N0,k∈N+:k≠i,l∈M:l≠i,l≠k,(19)tditD≥tdilD+sd,iL−M1−∑j∈Mj≠i∑k∈N+d,0,j,k∈FyijkD∀d∈D,i∈N0,(20)tditD≥tilS+sd,iL−M1−zd,0,iL∀d∈D,i∈N0,(21)tditD≥ticS+sd,iL−M1−z0,d,iL∀d∈D,i∈N0,(22)tditD≥td2itD+sd,iL−M1−zd2,d,iL∀d∈D,d2∈D:d2≠d,i∈N0,(23)td2itD≥tdilD+sd2,iL−M1−zd,d2,i″∀d∈D,d2∈D:d2≠d,i∈M.To prevent UAVs sorties from overlapping, formula (18) is used to restrict the UAV from the next node l of i to start earlier. This formula only works if the drone is recovered at point k, and there is a launch point l. When the UAV is ready to take off to collect data, formulas (19)–(23) ensure the start time of UAVs’ launch before data collection. Formula (19) states that the UAV cannot take off until the USV arrives, and the arrival time of node tdilD is an invalid value when a UAV is carried by the USV to point i. Formula (20) states that the USV cannot launch until the USV arrives at the acquisition point i and until the data collection is completed. Formula (21) states that the UAVs cannot launch from i while the USV is collecting data until the truck has completed data acquisition. Formula (22) ensures that d launches after d2 is launched. Formula (23) ensures that d2 launches after d is landed.(24)tdjlD≥tditD+τdij′−M1−∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,i∈N0:i≠j,(25)tdjtD≥tdjlD+σdj′∑i∈N0i≠j∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,(26)tdklD≥tklS+sd,kR−M1−zd,0,kR∀d∈D,k∈N+,(27)tdklD≥t¯d+sd,kR−M1−z0,d,kR∀d∈D,k∈N+,(28)tdklD≥td2klD+sd,kR−M1−zd2,d,kR∀d∈D,d2∈D:d2≠d,k∈N+,(29)tdklD≥td2klD+sd,kR−M1−zd2,d,k′∀d∈D,d2∈D:d2≠d,k∈M,(30)tdklD≥tdjtD+τjkD+sd,kR−M1−∑i∈N0d,0,j,k∈FyijkD∀d∈D,k∈N+,j∈M:j≠k,(31)tdklD−sd,kR−tditD≤eijkD+M1−yijkD∀d∈D,i∈N0,k∈N+:d,0,j,k∈F.For the monitoring point of UAVs, in the process of flying fromi to task site j and from j to k, formulas (24) and (25) control the time when the UAV arrives at the current node and returns to the next node during data collection. When the UAV reaches a rendezvous point with the USV, formula (26) states that the arrival of the USV first is a necessary condition for the UAV to land. If the USV is collecting data, formula (27) requires that the USV collect data before landing. The imminent landing of d colliding with d2, formula (28) states that the arrival time of d is later than the arrival time of d2. Formula (29) states that d arrives later than d2 has started. For a drone surveillance sequence yijkD, formula (30) stipulates that d cannot directly land on node k, but must take off and travel from node j. Formula (31) limits the endurance of the UAV from node i to node k through j.


### 4.3.2. USV Timing Constraint

When the USV arrives at the monitoring node, the formula conditions for data collection and departure from the monitoring node are as follows:(32)tjlS≥titS+τijS−M1−xij∀i∈N0,j∈N+:j≠i,(33)tkcS≥tklS+σk∑j∈N0j≠kxjk∀k∈N+,(34)tkcS≥tdklD+σk−M1−zd0kR∀d∈D,k∈N+,(35)tkcS≥tklS+σk−M1−zd0kL∀d∈D,k∈M.When the UAV arrives at the monitoring node, formula (32) states that the USV can only travel to j when it leaves i. Formula (33) ensures that the USV completes the data collection later than the time it arrives at the monitoring node. Formula (34) stipulates the sequence of data acquisition and UAVs’ recovery by USVs. If zv,0,kR=1, the UAV needs to be recovered first. Formula (35) specifies the sequence in which USV performs data acquisition and UAVs’ recovery. If zv,0,kL=1, the UAV needs to be launched first.(36)tktS≥tkcS∀k∈N+,(37)tktS≥tdklD−M1−∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,(38)tktS≥tdktD−M1−∑l∈Ml≠k∑m∈N+d,0,j,k∈FyijkD∀d∈D,k∈N0.When the UAV leaves the monitoring node, formula (36) prevents the USV service from leaving the monitor node k before completion. Formula (37) prevents the USV from leaving early if a UAV needs to land. Formula (38) prevents the USV from leaving early if there is a UAV to start.


## 4.3.1. UAVs’ Timing Constraint

The UAV’s flight time is limited, so we use the following formulas to determine the time when the UAV will depart from the USV or monitoring station to the monitoring site and return:(18)tdltD≥tdklD−M3−∑j∈Md,0,j,k∈Fj≠lyijkD−∑m∈Mm≠im≠km≠l∑n∈N+d,0,j,k∈Fn≠in≠kylmnD−pil∀d∈D,∀i∈N0,k∈N+:k≠i,l∈M:l≠i,l≠k,(19)tditD≥tdilD+sd,iL−M1−∑j∈Mj≠i∑k∈N+d,0,j,k∈FyijkD∀d∈D,i∈N0,(20)tditD≥tilS+sd,iL−M1−zd,0,iL∀d∈D,i∈N0,(21)tditD≥ticS+sd,iL−M1−z0,d,iL∀d∈D,i∈N0,(22)tditD≥td2itD+sd,iL−M1−zd2,d,iL∀d∈D,d2∈D:d2≠d,i∈N0,(23)td2itD≥tdilD+sd2,iL−M1−zd,d2,i″∀d∈D,d2∈D:d2≠d,i∈M.To prevent UAVs sorties from overlapping, formula (18) is used to restrict the UAV from the next node l of i to start earlier. This formula only works if the drone is recovered at point k, and there is a launch point l. When the UAV is ready to take off to collect data, formulas (19)–(23) ensure the start time of UAVs’ launch before data collection. Formula (19) states that the UAV cannot take off until the USV arrives, and the arrival time of node tdilD is an invalid value when a UAV is carried by the USV to point i. Formula (20) states that the USV cannot launch until the USV arrives at the acquisition point i and until the data collection is completed. Formula (21) states that the UAVs cannot launch from i while the USV is collecting data until the truck has completed data acquisition. Formula (22) ensures that d launches after d2 is launched. Formula (23) ensures that d2 launches after d is landed.(24)tdjlD≥tditD+τdij′−M1−∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,i∈N0:i≠j,(25)tdjtD≥tdjlD+σdj′∑i∈N0i≠j∑k∈N+d,0,j,k∈FyijkD∀d∈D,j∈M,(26)tdklD≥tklS+sd,kR−M1−zd,0,kR∀d∈D,k∈N+,(27)tdklD≥t¯d+sd,kR−M1−z0,d,kR∀d∈D,k∈N+,(28)tdklD≥td2klD+sd,kR−M1−zd2,d,kR∀d∈D,d2∈D:d2≠d,k∈N+,(29)tdklD≥td2klD+sd,kR−M1−zd2,d,k′∀d∈D,d2∈D:d2≠d,k∈M,(30)tdklD≥tdjtD+τjkD+sd,kR−M1−∑i∈N0d,0,j,k∈FyijkD∀d∈D,k∈N+,j∈M:j≠k,(31)tdklD−sd,kR−tditD≤eijkD+M1−yijkD∀d∈D,i∈N0,k∈N+:d,0,j,k∈F.For the monitoring point of UAVs, in the process of flying fromi to task site j and from j to k, formulas (24) and (25) control the time when the UAV arrives at the current node and returns to the next node during data collection. When the UAV reaches a rendezvous point with the USV, formula (26) states that the arrival of the USV first is a necessary condition for the UAV to land. If the USV is collecting data, formula (27) requires that the USV collect data before landing. The imminent landing of d colliding with d2, formula (28) states that the arrival time of d is later than the arrival time of d2. Formula (29) states that d arrives later than d2 has started. For a drone surveillance sequence yijkD, formula (30) stipulates that d cannot directly land on node k, but must take off and travel from node j. Formula (31) limits the endurance of the UAV from node i to node k through j.


## 4.3.2. USV Timing Constraint

When the USV arrives at the monitoring node, the formula conditions for data collection and departure from the monitoring node are as follows:(32)tjlS≥titS+τijS−M1−xij∀i∈N0,j∈N+:j≠i,(33)tkcS≥tklS+σk∑j∈N0j≠kxjk∀k∈N+,(34)tkcS≥tdklD+σk−M1−zd0kR∀d∈D,k∈N+,(35)tkcS≥tklS+σk−M1−zd0kL∀d∈D,k∈M.When the UAV arrives at the monitoring node, formula (32) states that the USV can only travel to j when it leaves i. Formula (33) ensures that the USV completes the data collection later than the time it arrives at the monitoring node. Formula (34) stipulates the sequence of data acquisition and UAVs’ recovery by USVs. If zv,0,kR=1, the UAV needs to be recovered first. Formula (35) specifies the sequence in which USV performs data acquisition and UAVs’ recovery. If zv,0,kL=1, the UAV needs to be launched first.(36)tktS≥tkcS∀k∈N+,(37)tktS≥tdklD−M1−∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,(38)tktS≥tdktD−M1−∑l∈Ml≠k∑m∈N+d,0,j,k∈FyijkD∀d∈D,k∈N0.When the UAV leaves the monitoring node, formula (36) prevents the USV service from leaving the monitor node k before completion. Formula (37) prevents the USV from leaving early if a UAV needs to land. Formula (38) prevents the USV from leaving early if there is a UAV to start.


## 4.4. Sequencing of Retrievals, Launches, and USV Service

This section establishes formulas on binary decision variables to determine the order of execution at each monitoring point. In the preceding decision variables, we use thezR decision variable representing UAVs’ recovery, which needs to meet the following formulas:(39)z0dkR+zd0kR=∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,(40)zd,d2,kR≤∑i∈N0i≠k∑j∈Md,0,j,k∈FyijkD∀d∈D,k∈N+,d2∈D:d2≠d,(41)zd,d2,kR≤∑i∈N0i≠k∑j∈Md,0,j,k∈Fyd2ijk∀d∈D,k∈N+,d2∈D:d2≠d,(42)zd,d2,kR+zd2,d,kR≤1∀d∈D,k∈N+,d2∈D:d2≠d,(43)zd,d2,kR+zd2,d,kR+1≥∑i∈N0i≠k∑j∈Md,0,j,k∈Fyijkd+∑i∈N0i≠k∑j∈Md2,0,j,k∈Fyijkd2∀d∈D,k∈N+,d2∈D:d2≠d.Formula (39) specifies whether there is a USV that needs to be landed on the k node retrieval. Formula (40) states that zd,0,kR cannot be 1 without retrieving d2. Formula (41) states that zd,0,kR cannot be 1 if d2 is not retrieved. Formula (42) declares that either d or d2 is retrieved at k, otherwise neither is retrieved. Formula (43) states that only one can be retrieved before the other when retrieving d and d2.


## 5. A Heuristic Solution for MFSDCP

The heuristic method is an effective method to find a feasible solution of the NP-hard problem. First, in order to reduce the speed of solving the objective function, the feasible nodes of UAVs and USVs are divided into two groups. The UAV has to be made by USV recycle, so the USV node number of initializationS0 should be unmanned aerial vehicle D+1 number of integer multiple of upwards. S0 represents the initial number of USV nodes, D represents the number of UAVs. For example, if there are 100 nodes to be monitored and there are 1 USV and 3 UAVs, then the USV is monitoring at least 25 nodes.This section presents the pseudocode (Algorithm1) for the heuristic method of the MFSDCP, the algorithm flow is shown in Figure 3. Firstly, we determine where the UAV will meet the USV and plan their flight routes. Secondly, tasks are assigned to the UAV as much as possible by switching positions between the UAV’s and the USV’s monitoring points. Finally, an advance landing strategy is used to reduce the waiting time of UAVs.Figure 3
A framework for MFSDCP heuristic.Algorithm 1: The MFSDCP heuristic algorithm.
Inputs: monitoring sites (nodes), monitoring station, drone’s parameter (number, speed, energy consumption), and USV parameter (number and speed)Outputs: USV route, UAVs sites, UAVs time series, USV time series, and reduce timeωInitial: monitoring sitesS0 for USV and objective value z=∞(1)
fors in S0,S1,…,M do(2)
Feasible programFP1←∅;(3)
USV route,USV sites,UAV sites←Algorithm2;(4)
lowerBound←USV route_time+wi # current minimum time;(5)
iflowerBound < objective function z then(6)
FP1←USV route,USV sites,UAV sites;(7)
whileFP1≠∅ do(8)
extractUSV route,USV sites,UAV sites from FP1;(9)
FP2←USV time series by Algorithm3;(10)
whileFP2≠∅ do(11)
FP2←UAV time series,objectivez,iD,insertion time;(12)
lowerBound←USV route time+wi+extra insertion time;(13)
iflowerBound < objectivez then(14)
ifUAV sites not feasible then(15)
USV route_current byGurobi←insertiDUSVsite;(16)
USV site_current←USV site∪iD;(17)
UAV site_current ← UAV site−iD;(18)
AddUSV route,USV sites,UAV sites to FP1;(19)
else(20)
forUAV time series do(21)
objective functionz,UAV time series←FP3;(22)
ifFP3is feasible then(23)
# Judgement premature landing(24)
UAV series_current←Algorithm4;(25)
ifUAV series current≠UAV series do(26)
UAV series←UAV series_current;(27)
return < USV route, UAVs sites, UAVs time series, USV time series, and reduce timeω>


### 5.1. Creating USV Route

In this section, we first establish the route for sites that can only be completed by the USV for data collection tasks. The exact USV route is obtained by using the method of getting TSP() in Gurobi. In order to minimize the time used by the data collection task, nodes are constantly added and deleted according to the saving index until it cannot be improved to a shorter time.Algorithm 2: Create USV route.
Inputs: monitoring sites (nodes), monitoring station, drone’s numberOutputs: USV route, UAVs sites, USV sitesInitial: monitoring sites S0 for USV and objective value z=∞(1)
USV route←get by GurobiUSV site(2)
while USV route is True do(3)
forj in UAVs site do(4)
The UAVs nodej convert into USV;(5)
if savings time >0 then(6)
USV site ←  USVsite∪jD;(7)
UAVs site ← UAVssite−jD;(8)
USV route←get by GurobiUSV site;(9)
forj in USV site do(10)
The USV nodej convert into UAVs;(11)
if savings time > 0 then(12)
UAVs site ← UAVssite∪jS;(13)
USV site ←  USVsite−jS;(14)
USV route←get by GurobiUSV site;(15)
whileFP1=∅ do(16)
Find satisfies viable solutions toS by Gurobi;(17)
update < USV site, UAVs site, UAVs route>;(18)
if UAVs route is not unique then(19)
USV site ⇌ UAVs site: <i, j, k, l> ⇌ <i, k, j, l>;(20)
select min-cost USV tour;(21)
update < USV site, UAVs site, and UAVs route>;(22)
return < UAVs route, USV site, and UAVs site>In Algorithm2, the number of nodes for the USV to collect data is ensured and the feasibility is estimated in the next step, that is, the existence of a valid flight sequence d,i,j,k∈F. Firstly, the feasible candidate UAVs’ sequence is successively added to the USV for route planning. Then, the USV nodes are replaced with UAV monitoring nodes, and the route is replanned until all feasible nodes are executed. For the adjacent monitored nodes of the UAV, swap the position, and the USV sequence with the minimum time consumption is returned.


### 5.2. UAV Sorties

Algorithm3 mainly completes the sorties d,i,j,k of each UAV monitoring node, that is to determine the value of the variable of yijkd. Taking the USV route in the above algorithm and the monitoring node served by the UAV as the input parameters of the next algorithm, the sum of the time of the USV performing the monitoring mission during the entire voyage and the time of recovering the UAV, which was also performing the monitoring mission, was calculated.Algorithm 3: Create USV time series.
Inputs: USV route, UAVs sites, and USV sitesOutputs: UAVs time series(1)
fori in UAVs num do(2)
forj in UAVs site do(3)
set all series ofyijkD;(4)
fors in site do(5)
waiting time←∞;(6)
fory in yijkD do(7)
if USV arrived early then(8)
calculate USV waiting time;(9)
else if(10)
calculate UAVs waiting time;(11)
if UAVs time series current < UAVs time series do(12)
UAVs time series current = UAVs time series;(13)
if waiting time←∞ then(14)
UAVs sorties-yijkD;(15)
else(16)
UAVssorties∪yijkD;(17)
return < USV site、UAVs site、UAVs route, and UAVs sorties>In Algorithm3, there are no additional USV nodes between the take-off and landing nodes, that is, the USV only passes the take-off and landing nodes while the UAV is flying, and there are no other USV in between nodes. If all UAVs are viable, Algorithm 4 is entered. In addition, if the Algorithm 3 is not established after the improvement of Algorithm 4, otherwise it returns to Algorithm 2.


### 5.3. Working Time Sequence

For identified UAV routes and UAV sorties, the next step is to determine the sequence of data collection performed by UAVs and USVs and the time of each monitoring site.Figure4 shows a schematic diagram where the UAV can land in advance at point k′ when almost the USV route is not occluded, such as in the water environment. In Algorithm 4, it will make use of this feature to determine whether to land in advance.Figure 4
Midflight recovery strategy.Algorithm 4: UAVs landing in advance.
Inputs: USV route, UAVs sites, UAVs time series, and USV time seriesOutputs: USV route, UAVs sites, UAVs time series, USV time series, and reduce time ωInitial: reduce time ←0(1)
foryijkD in UAVs sorties do(2)
if UAVs wait the USV atk then(3)
if USV take off do:(4)
if the USV ati do:(5)
The estimated time after departure is used to calculate the best rendezvous location from the current location, before minus the USV service timetiDS;(6)
Calculate the distance the drone needs to fly;(7)
else(8)
According to the current position, calculate the time with speed and then calculate the best rendezvous position;(9)
Calculate the distance the drone needs to fly;(10)
ifeijkD cleared for premature landing do(11)
Calculate a seriesyijkD times for landing, collect data time, and take off time at node i;(12)
ω_current ←tijkD-tijkD_old;(13)
ifω_current > 0 do(14)
ω←ω+reduce time currently;(15)
return < USV route, UAVs sites, UAVs time series, USV time series, and reduce timeω>The purpose of Algorithm4 (modified) is to improve the target value of the solution by reducing the waiting time of the UAV. From the departure of the monitoring station, the UAV’s waiting time for the USV is identified. For each flight sequence, the UAV and the USV converge at point k, and calculate whether there is a halfway convergence point k′. At the original point k, the drone from point j to point k needs to wait for the unmanned boat. At point k′, the two devices can directly converge. Once all possible early landing points have been completed, new UAVs sorties with USV travel times and their movements will be output back, as described in Algorithm 1.


## 5.1. Creating USV Route

In this section, we first establish the route for sites that can only be completed by the USV for data collection tasks. The exact USV route is obtained by using the method of getting TSP() in Gurobi. In order to minimize the time used by the data collection task, nodes are constantly added and deleted according to the saving index until it cannot be improved to a shorter time.Algorithm 2: Create USV route.
Inputs: monitoring sites (nodes), monitoring station, drone’s numberOutputs: USV route, UAVs sites, USV sitesInitial: monitoring sites S0 for USV and objective value z=∞(1)
USV route←get by GurobiUSV site(2)
while USV route is True do(3)
forj in UAVs site do(4)
The UAVs nodej convert into USV;(5)
if savings time >0 then(6)
USV site ←  USVsite∪jD;(7)
UAVs site ← UAVssite−jD;(8)
USV route←get by GurobiUSV site;(9)
forj in USV site do(10)
The USV nodej convert into UAVs;(11)
if savings time > 0 then(12)
UAVs site ← UAVssite∪jS;(13)
USV site ←  USVsite−jS;(14)
USV route←get by GurobiUSV site;(15)
whileFP1=∅ do(16)
Find satisfies viable solutions toS by Gurobi;(17)
update < USV site, UAVs site, UAVs route>;(18)
if UAVs route is not unique then(19)
USV site ⇌ UAVs site: <i, j, k, l> ⇌ <i, k, j, l>;(20)
select min-cost USV tour;(21)
update < USV site, UAVs site, and UAVs route>;(22)
return < UAVs route, USV site, and UAVs site>In Algorithm2, the number of nodes for the USV to collect data is ensured and the feasibility is estimated in the next step, that is, the existence of a valid flight sequence d,i,j,k∈F. Firstly, the feasible candidate UAVs’ sequence is successively added to the USV for route planning. Then, the USV nodes are replaced with UAV monitoring nodes, and the route is replanned until all feasible nodes are executed. For the adjacent monitored nodes of the UAV, swap the position, and the USV sequence with the minimum time consumption is returned.


## 5.2. UAV Sorties

Algorithm3 mainly completes the sorties d,i,j,k of each UAV monitoring node, that is to determine the value of the variable of yijkd. Taking the USV route in the above algorithm and the monitoring node served by the UAV as the input parameters of the next algorithm, the sum of the time of the USV performing the monitoring mission during the entire voyage and the time of recovering the UAV, which was also performing the monitoring mission, was calculated.Algorithm 3: Create USV time series.
Inputs: USV route, UAVs sites, and USV sitesOutputs: UAVs time series(1)
fori in UAVs num do(2)
forj in UAVs site do(3)
set all series ofyijkD;(4)
fors in site do(5)
waiting time←∞;(6)
fory in yijkD do(7)
if USV arrived early then(8)
calculate USV waiting time;(9)
else if(10)
calculate UAVs waiting time;(11)
if UAVs time series current < UAVs time series do(12)
UAVs time series current = UAVs time series;(13)
if waiting time←∞ then(14)
UAVs sorties-yijkD;(15)
else(16)
UAVssorties∪yijkD;(17)
return < USV site、UAVs site、UAVs route, and UAVs sorties>In Algorithm3, there are no additional USV nodes between the take-off and landing nodes, that is, the USV only passes the take-off and landing nodes while the UAV is flying, and there are no other USV in between nodes. If all UAVs are viable, Algorithm 4 is entered. In addition, if the Algorithm 3 is not established after the improvement of Algorithm 4, otherwise it returns to Algorithm 2.


## 5.3. Working Time Sequence

For identified UAV routes and UAV sorties, the next step is to determine the sequence of data collection performed by UAVs and USVs and the time of each monitoring site.Figure4 shows a schematic diagram where the UAV can land in advance at point k′ when almost the USV route is not occluded, such as in the water environment. In Algorithm 4, it will make use of this feature to determine whether to land in advance.Figure 4
Midflight recovery strategy.Algorithm 4: UAVs landing in advance.
Inputs: USV route, UAVs sites, UAVs time series, and USV time seriesOutputs: USV route, UAVs sites, UAVs time series, USV time series, and reduce time ωInitial: reduce time ←0(1)
foryijkD in UAVs sorties do(2)
if UAVs wait the USV atk then(3)
if USV take off do:(4)
if the USV ati do:(5)
The estimated time after departure is used to calculate the best rendezvous location from the current location, before minus the USV service timetiDS;(6)
Calculate the distance the drone needs to fly;(7)
else(8)
According to the current position, calculate the time with speed and then calculate the best rendezvous position;(9)
Calculate the distance the drone needs to fly;(10)
ifeijkD cleared for premature landing do(11)
Calculate a seriesyijkD times for landing, collect data time, and take off time at node i;(12)
ω_current ←tijkD-tijkD_old;(13)
ifω_current > 0 do(14)
ω←ω+reduce time currently;(15)
return < USV route, UAVs sites, UAVs time series, USV time series, and reduce timeω>The purpose of Algorithm4 (modified) is to improve the target value of the solution by reducing the waiting time of the UAV. From the departure of the monitoring station, the UAV’s waiting time for the USV is identified. For each flight sequence, the UAV and the USV converge at point k, and calculate whether there is a halfway convergence point k′. At the original point k, the drone from point j to point k needs to wait for the unmanned boat. At point k′, the two devices can directly converge. Once all possible early landing points have been completed, new UAVs sorties with USV travel times and their movements will be output back, as described in Algorithm 1.


## 6. Experimental Analysis

In order to verify the effect of the MFSDCP solving in this article, the calculation effect of the MILP model established by the Gurobi precise solution and heuristic algorithm for the MFSDCP is compared experimentally. The reason is the high computational complexity in such multiconstrained collaborative cruise monitoring problems, where the exact solution cannot be obtained in effective time for a large number of nodes. Then, a heuristic algorithm is used to solve the problem for collaborative monitoring of large-scale nodes, and a detailed analysis of the monitoring effect as well as the UAV’s saving time is presented.This research use python to implement the proposed method. All the work is carried out on a laptop with i7-8750H processor, 16 GB RAM, and Win10 64 operating system. Meanwhile, Gurobi 9.5.0 was used to solve the MILP problem in this article. The coordinate point test data for environmental monitoring were used from [17]. In this experiment, assuming that the USV can carry 1 to 3 UAVs with a high performance speed of 31.3 m/s, and 100 cases of 8, 10, 25, 50, and 100 monitoring sites are selected, respectively. It is also set that the USV speed is 25 miles per hour. The number of USV monitoring sites should not be less than 10%, and the UAV’s monitoring equipment should not exceed 3 kg in weight. Assuming that the UAV and USV have different mission times at each monitoring node, the default is set to 30 s and 60 s (this value can be changed depending on the monitoring equipment).


### 6.1. Exact Solution Performance

The MFSDCP we presented in this article is a complex problem, and only test instances with no more than 8 monitoring points were possible to obtain accurate solutions within an acceptable time frame (1 hour). Therefore, in order to prove the accuracy and effectiveness of the heuristic method for the MFSDCP; this section compares the performance of the MFSDCP solution based on the exact solution and heuristic solution. In the small-scale problems of 8 monitoring points, the total time of completing tasks of UAVs and USVs is taken as the target. 20 experimental cases were included in the experiment at 8 monitoring sites. The total time of the objective function is shown in Figure5.Figure 5
Comparison of heuristic and exact solution times.Figure5 calculates the total running time of the objective function min z for 8 nodes. As can be seen from Figure 5, as the number of UAVs increases, only case 5 has an obvious effect, and the optimization effect of 2-UAVs and 3-UAVs is roughly the same. This is due to the smaller number of monitoring sites and the fewer drone sorties available. This article focuses on the waiting time of UAVs. Therefore, based on the advance recovery strategy proposed in this article, the recovery time saved by different number of UAVs is analyzed.Figure6 and Table 3 provide the solution accuracy of three UAV-USV collaborative heuristic algorithms compared with the exact solution when the number of UAVs is different. For the case of 1-UAV monitoring, the average accuracy is 95.42%, and the maximum accuracy is the same as the exact solution. In addition, it can be seen from Figure 6 that although the minimum accuracy point is only 77.02%, the accuracy is less than 90% only once, and the value is much higher in other instances. In the scenario of 2-UAVs cooperating with the USV, their mean value was the highest, with an accuracy of 99.07%. When the heuristic method and exact solution were the same in 1-UAV and 2-UAVs, they accounted for 10% and 50%, respectively, and the exact solution was found 60% of the total times by 3-UAVs. The stability of the solution effect of 3-UAVs is almost the same as that of 2-UAVs. The minimum accuracy of the solution in the case of 3-UAVs is superior to the other two cases, and the proportion of the same as the exact solution is the highest.Figure 6
Heuristic solution accuracy.Table 3
Small scale solving statistics.
Number of UAVsMinimum accuracy (%)Mean accuracy (%)Standard deviationOptimal solution ratio (%)177.0295.420.052610.00294.8899.070.014150.00395.5198.990.015360.00It can be seen from Figures7 and 8, the time saved by UAVs at different points varies greatly, especially in the case of 3-UAVs at monitoring point 8, reaching 2554.43 s, accounting for 44.2% of the total time z. The 1-UAV time at this time is 680.43 s, saving only 16.7% of the target time. Therefore, in most cases, the increase in the number of UAVs can increase the number of sorties deployed by UAVs, which will further increase the total waiting time of UAVs during monitoring. In only a few instances, such as cases 1 and 19, the increase in the number of UAVs reduced the total waiting time, but by a very small amount. This is because in the case of 8 monitoring points, the low number of monitoring sites, and the actual use of UAVs is limited, so the optimization effect of increasing UAVs is similar to that of 1-UAV.Figure 7
Time saved by drones based on heuristics.Figure 8
The ratio of time saved by drones to total time.


### 6.2. Heuristics Solution Performance

In this section, we get a step further on using the MFSDCP heuristic method to conduct experimental analysis on collaborative monitoring of larger monitoring sites. Firstly, according to the objective function proposed in this article, the cruise monitoring effects of five different scale nodes are analyzed. Then, the time saved and UAVs’ flight distance are analyzed in detail.


#### 6.2.1. Object Analysis of Data Collection Time

In Table4, we summarize the results of node monitoring and data collection of 5 different scales. By equipping different number of UAVs, the average time saved in the same process was counted and the proportion of time to complete the monitoring task was calculated in one step.Table 4
Large scale solving statistics.
SitesNumber of UAVsAverage time saving (s)Average USV travel time (s)Time saving ratio (%)Mean of objective function (s)Extra average flight distance (m)81358.9262471.7680.1452112.8422516.6312676.0422266.7880.2981590.7464496.9853832.6512280.3180.3651447.6675059.348101237.2102695.5930.0882458.3832614.4642593.6202563.0740.2321969.4544803.4923828.9182539.8200.3261710.9026568.0292511245.7396939.9940.1805694.2554499.31722081.0396276.6430.3324195.60412172.65833331.0276083.5070.5482752.4821736.8085011043.86010831.2460.0969787.3864908.21822469.1199528.3940.2597059.27513929.98834269.9199089.680.4704819.76126864.02410012000.35516724.5240.12014724.1694599.28623908.31115002.5440.26111094.23313487.45536403.20914450.0890.4438046.8827269.869It can be seen from Table4 that with the increase of the number of UAVs, the average saving time of different nodes increases in different ways. Compared with the saving time of 1-UAV, the increase result is shown in Figures 9 and 10. Figure 10 shows an increase in the proportion of time as the number of UAVs increases compared to 1-UAV. However, it can be seen from Figure 10 that the saving time of 25 nodes equipped with 3-UAVs is greater than that of 50 nodes and 100 nodes equipped with 1-UAV.Figure 9
UAV time saving.Figure 10
UAV time saving ratio.


#### 6.2.2. Time Saving Analysis

In Figure11, the time saving statistics of a single UAVs at 8, 10, 25, 50, and 100 monitoring points are given. It can be seen that with the increase of the number of monitoring points, the total time saved by UAVs at monitoring points shows an upward trend. 8 nodes are closer to ten nodes because the number of nodes differs by only two, but the median time savings are still higher across 20 instances.Figure 11
UAV time saving ratio.In Figures12–14, the abscissa represents the number of monitoring points, and the ordinate represents the increased distance of UAVs flight in 20 instances of this number. In the experiment of 8 monitoring points and 10 monitoring points with fewer nodes, the increase of flight distance has little changes with the increase of the number of UAVs. However, the increase value of flight distance of nodes 25, 50, and 100 varies greatly, and the increase value of flight distance of each additional UAVs is about two times.Figure 12
1-UAV time saving ratio.Figure 13
2-UAVs time saving ratio.Figure 14
3-UAVs time saving ratio.Interestingly (as is shown in Figure15), the flight range of three sizes of UAVs is maintained at 4,500 meters with 1-UAV, 13,000 meters with 2-UAVs, and around 25,000 meters with 3-UAVs multiflight. Combined with Table 4 (previous flight time), it means that in the experiment case, with the same number of UAVs and the number of monitoring nodes of different scales, the saved average flight waiting time increases significantly, while the change of average flight distance is not obvious under the same conditions. This is because as the number of nodes increases, the number of mission nodes assigned to UAVs increases, and the waiting time for flight increases accordingly. However, as the density of monitoring points increases, the distance between them shortened, the distance between adjacent nodes on the USV navigation route shortened, and the distance between UAVs’ monitoring points and two continuous monitoring points of USVs shortened. Therefore, the number of UAV sorties increases, but the distance of UAV’s each flight shortened. Although the energy consumption of UAVs in high-speed flight is greater than that in hover, in the 1-UAV flight experiment, the flight distance of UAVs from 25 monitoring points to 50 and 100 monitoring points increases by 9.1% and −6.29%, while the average flight time increases by 56.07% and 54.4%. In the 2-UAV flight experiment, the flight distance of UAVs from 25 monitoring sites to 50 and 100 monitoring sites increased by 14.43% and 3.17%, while the average flight saving time increased by 51.81% and 57.45%. Meanwhile, in the 3-UAV flight experiment, the flight distance of UAVs increases by 23.59% and 1.51%, respectively, while the average flight time increases by 49.42% and 58.97%, respectively.Figure 15
UAV extra flight distance.Therefore, it can be concluded that the flight strategy of early landing proposed in this article is more cost-effective in the case of more monitoring points because the extra flight distance is not significantly increased while time is saved. This shows that the doubling of the number of UAV nodes does not mean a sharp increase in the flight distance, and in the case of 1-UAV, the distance of multiflight at 50 monitoring points is greater than the flight distance of 100 nodes, which further demonstrates the applicability of the scheme proposed in this article with more nodes.


## 6.1. Exact Solution Performance

The MFSDCP we presented in this article is a complex problem, and only test instances with no more than 8 monitoring points were possible to obtain accurate solutions within an acceptable time frame (1 hour). Therefore, in order to prove the accuracy and effectiveness of the heuristic method for the MFSDCP; this section compares the performance of the MFSDCP solution based on the exact solution and heuristic solution. In the small-scale problems of 8 monitoring points, the total time of completing tasks of UAVs and USVs is taken as the target. 20 experimental cases were included in the experiment at 8 monitoring sites. The total time of the objective function is shown in Figure5.Figure 5
Comparison of heuristic and exact solution times.Figure5 calculates the total running time of the objective function min z for 8 nodes. As can be seen from Figure 5, as the number of UAVs increases, only case 5 has an obvious effect, and the optimization effect of 2-UAVs and 3-UAVs is roughly the same. This is due to the smaller number of monitoring sites and the fewer drone sorties available. This article focuses on the waiting time of UAVs. Therefore, based on the advance recovery strategy proposed in this article, the recovery time saved by different number of UAVs is analyzed.Figure6 and Table 3 provide the solution accuracy of three UAV-USV collaborative heuristic algorithms compared with the exact solution when the number of UAVs is different. For the case of 1-UAV monitoring, the average accuracy is 95.42%, and the maximum accuracy is the same as the exact solution. In addition, it can be seen from Figure 6 that although the minimum accuracy point is only 77.02%, the accuracy is less than 90% only once, and the value is much higher in other instances. In the scenario of 2-UAVs cooperating with the USV, their mean value was the highest, with an accuracy of 99.07%. When the heuristic method and exact solution were the same in 1-UAV and 2-UAVs, they accounted for 10% and 50%, respectively, and the exact solution was found 60% of the total times by 3-UAVs. The stability of the solution effect of 3-UAVs is almost the same as that of 2-UAVs. The minimum accuracy of the solution in the case of 3-UAVs is superior to the other two cases, and the proportion of the same as the exact solution is the highest.Figure 6
Heuristic solution accuracy.Table 3
Small scale solving statistics.
Number of UAVsMinimum accuracy (%)Mean accuracy (%)Standard deviationOptimal solution ratio (%)177.0295.420.052610.00294.8899.070.014150.00395.5198.990.015360.00It can be seen from Figures7 and 8, the time saved by UAVs at different points varies greatly, especially in the case of 3-UAVs at monitoring point 8, reaching 2554.43 s, accounting for 44.2% of the total time z. The 1-UAV time at this time is 680.43 s, saving only 16.7% of the target time. Therefore, in most cases, the increase in the number of UAVs can increase the number of sorties deployed by UAVs, which will further increase the total waiting time of UAVs during monitoring. In only a few instances, such as cases 1 and 19, the increase in the number of UAVs reduced the total waiting time, but by a very small amount. This is because in the case of 8 monitoring points, the low number of monitoring sites, and the actual use of UAVs is limited, so the optimization effect of increasing UAVs is similar to that of 1-UAV.Figure 7
Time saved by drones based on heuristics.Figure 8
The ratio of time saved by drones to total time.


## 6.2. Heuristics Solution Performance

In this section, we get a step further on using the MFSDCP heuristic method to conduct experimental analysis on collaborative monitoring of larger monitoring sites. Firstly, according to the objective function proposed in this article, the cruise monitoring effects of five different scale nodes are analyzed. Then, the time saved and UAVs’ flight distance are analyzed in detail.


### 6.2.1. Object Analysis of Data Collection Time

In Table4, we summarize the results of node monitoring and data collection of 5 different scales. By equipping different number of UAVs, the average time saved in the same process was counted and the proportion of time to complete the monitoring task was calculated in one step.Table 4
Large scale solving statistics.
SitesNumber of UAVsAverage time saving (s)Average USV travel time (s)Time saving ratio (%)Mean of objective function (s)Extra average flight distance (m)81358.9262471.7680.1452112.8422516.6312676.0422266.7880.2981590.7464496.9853832.6512280.3180.3651447.6675059.348101237.2102695.5930.0882458.3832614.4642593.6202563.0740.2321969.4544803.4923828.9182539.8200.3261710.9026568.0292511245.7396939.9940.1805694.2554499.31722081.0396276.6430.3324195.60412172.65833331.0276083.5070.5482752.4821736.8085011043.86010831.2460.0969787.3864908.21822469.1199528.3940.2597059.27513929.98834269.9199089.680.4704819.76126864.02410012000.35516724.5240.12014724.1694599.28623908.31115002.5440.26111094.23313487.45536403.20914450.0890.4438046.8827269.869It can be seen from Table4 that with the increase of the number of UAVs, the average saving time of different nodes increases in different ways. Compared with the saving time of 1-UAV, the increase result is shown in Figures 9 and 10. Figure 10 shows an increase in the proportion of time as the number of UAVs increases compared to 1-UAV. However, it can be seen from Figure 10 that the saving time of 25 nodes equipped with 3-UAVs is greater than that of 50 nodes and 100 nodes equipped with 1-UAV.Figure 9
UAV time saving.Figure 10
UAV time saving ratio.


### 6.2.2. Time Saving Analysis

In Figure11, the time saving statistics of a single UAVs at 8, 10, 25, 50, and 100 monitoring points are given. It can be seen that with the increase of the number of monitoring points, the total time saved by UAVs at monitoring points shows an upward trend. 8 nodes are closer to ten nodes because the number of nodes differs by only two, but the median time savings are still higher across 20 instances.Figure 11
UAV time saving ratio.In Figures12–14, the abscissa represents the number of monitoring points, and the ordinate represents the increased distance of UAVs flight in 20 instances of this number. In the experiment of 8 monitoring points and 10 monitoring points with fewer nodes, the increase of flight distance has little changes with the increase of the number of UAVs. However, the increase value of flight distance of nodes 25, 50, and 100 varies greatly, and the increase value of flight distance of each additional UAVs is about two times.Figure 12
1-UAV time saving ratio.Figure 13
2-UAVs time saving ratio.Figure 14
3-UAVs time saving ratio.Interestingly (as is shown in Figure15), the flight range of three sizes of UAVs is maintained at 4,500 meters with 1-UAV, 13,000 meters with 2-UAVs, and around 25,000 meters with 3-UAVs multiflight. Combined with Table 4 (previous flight time), it means that in the experiment case, with the same number of UAVs and the number of monitoring nodes of different scales, the saved average flight waiting time increases significantly, while the change of average flight distance is not obvious under the same conditions. This is because as the number of nodes increases, the number of mission nodes assigned to UAVs increases, and the waiting time for flight increases accordingly. However, as the density of monitoring points increases, the distance between them shortened, the distance between adjacent nodes on the USV navigation route shortened, and the distance between UAVs’ monitoring points and two continuous monitoring points of USVs shortened. Therefore, the number of UAV sorties increases, but the distance of UAV’s each flight shortened. Although the energy consumption of UAVs in high-speed flight is greater than that in hover, in the 1-UAV flight experiment, the flight distance of UAVs from 25 monitoring points to 50 and 100 monitoring points increases by 9.1% and −6.29%, while the average flight time increases by 56.07% and 54.4%. In the 2-UAV flight experiment, the flight distance of UAVs from 25 monitoring sites to 50 and 100 monitoring sites increased by 14.43% and 3.17%, while the average flight saving time increased by 51.81% and 57.45%. Meanwhile, in the 3-UAV flight experiment, the flight distance of UAVs increases by 23.59% and 1.51%, respectively, while the average flight time increases by 49.42% and 58.97%, respectively.Figure 15
UAV extra flight distance.Therefore, it can be concluded that the flight strategy of early landing proposed in this article is more cost-effective in the case of more monitoring points because the extra flight distance is not significantly increased while time is saved. This shows that the doubling of the number of UAV nodes does not mean a sharp increase in the flight distance, and in the case of 1-UAV, the distance of multiflight at 50 monitoring points is greater than the flight distance of 100 nodes, which further demonstrates the applicability of the scheme proposed in this article with more nodes.


## 6.2.1. Object Analysis of Data Collection Time

In Table4, we summarize the results of node monitoring and data collection of 5 different scales. By equipping different number of UAVs, the average time saved in the same process was counted and the proportion of time to complete the monitoring task was calculated in one step.Table 4
Large scale solving statistics.
SitesNumber of UAVsAverage time saving (s)Average USV travel time (s)Time saving ratio (%)Mean of objective function (s)Extra average flight distance (m)81358.9262471.7680.1452112.8422516.6312676.0422266.7880.2981590.7464496.9853832.6512280.3180.3651447.6675059.348101237.2102695.5930.0882458.3832614.4642593.6202563.0740.2321969.4544803.4923828.9182539.8200.3261710.9026568.0292511245.7396939.9940.1805694.2554499.31722081.0396276.6430.3324195.60412172.65833331.0276083.5070.5482752.4821736.8085011043.86010831.2460.0969787.3864908.21822469.1199528.3940.2597059.27513929.98834269.9199089.680.4704819.76126864.02410012000.35516724.5240.12014724.1694599.28623908.31115002.5440.26111094.23313487.45536403.20914450.0890.4438046.8827269.869It can be seen from Table4 that with the increase of the number of UAVs, the average saving time of different nodes increases in different ways. Compared with the saving time of 1-UAV, the increase result is shown in Figures 9 and 10. Figure 10 shows an increase in the proportion of time as the number of UAVs increases compared to 1-UAV. However, it can be seen from Figure 10 that the saving time of 25 nodes equipped with 3-UAVs is greater than that of 50 nodes and 100 nodes equipped with 1-UAV.Figure 9
UAV time saving.Figure 10
UAV time saving ratio.


## 6.2.2. Time Saving Analysis

In Figure11, the time saving statistics of a single UAVs at 8, 10, 25, 50, and 100 monitoring points are given. It can be seen that with the increase of the number of monitoring points, the total time saved by UAVs at monitoring points shows an upward trend. 8 nodes are closer to ten nodes because the number of nodes differs by only two, but the median time savings are still higher across 20 instances.Figure 11
UAV time saving ratio.In Figures12–14, the abscissa represents the number of monitoring points, and the ordinate represents the increased distance of UAVs flight in 20 instances of this number. In the experiment of 8 monitoring points and 10 monitoring points with fewer nodes, the increase of flight distance has little changes with the increase of the number of UAVs. However, the increase value of flight distance of nodes 25, 50, and 100 varies greatly, and the increase value of flight distance of each additional UAVs is about two times.Figure 12
1-UAV time saving ratio.Figure 13
2-UAVs time saving ratio.Figure 14
3-UAVs time saving ratio.Interestingly (as is shown in Figure15), the flight range of three sizes of UAVs is maintained at 4,500 meters with 1-UAV, 13,000 meters with 2-UAVs, and around 25,000 meters with 3-UAVs multiflight. Combined with Table 4 (previous flight time), it means that in the experiment case, with the same number of UAVs and the number of monitoring nodes of different scales, the saved average flight waiting time increases significantly, while the change of average flight distance is not obvious under the same conditions. This is because as the number of nodes increases, the number of mission nodes assigned to UAVs increases, and the waiting time for flight increases accordingly. However, as the density of monitoring points increases, the distance between them shortened, the distance between adjacent nodes on the USV navigation route shortened, and the distance between UAVs’ monitoring points and two continuous monitoring points of USVs shortened. Therefore, the number of UAV sorties increases, but the distance of UAV’s each flight shortened. Although the energy consumption of UAVs in high-speed flight is greater than that in hover, in the 1-UAV flight experiment, the flight distance of UAVs from 25 monitoring points to 50 and 100 monitoring points increases by 9.1% and −6.29%, while the average flight time increases by 56.07% and 54.4%. In the 2-UAV flight experiment, the flight distance of UAVs from 25 monitoring sites to 50 and 100 monitoring sites increased by 14.43% and 3.17%, while the average flight saving time increased by 51.81% and 57.45%. Meanwhile, in the 3-UAV flight experiment, the flight distance of UAVs increases by 23.59% and 1.51%, respectively, while the average flight time increases by 49.42% and 58.97%, respectively.Figure 15
UAV extra flight distance.Therefore, it can be concluded that the flight strategy of early landing proposed in this article is more cost-effective in the case of more monitoring points because the extra flight distance is not significantly increased while time is saved. This shows that the doubling of the number of UAV nodes does not mean a sharp increase in the flight distance, and in the case of 1-UAV, the distance of multiflight at 50 monitoring points is greater than the flight distance of 100 nodes, which further demonstrates the applicability of the scheme proposed in this article with more nodes.


## 7. Conclusion

In this article, a collaborative optimization problem of multiple flying sidekicks data collection is proposed. The premise is to use a wireless sensor monitoring environment based on the Internet of Things, a USV equipped with multiple UAVs is used for data acquisition.The completion time and waiting time saving of USVs and UAVs are studied. The monitoring sequence of UAVs and USVs and the calculation of the convergence point are the main components. In order to solve these problems, a heuristic method is applied to establish the allocation of USV path monitoring nodes, and the strategy of UAVs’ landing on the way of USVs is proposed. The effect of UAV flight distance and flight time saving under different number of UAVs and monitoring nodes was evaluated. It is interesting to find that as the number of drones increases, the time saved increases at a much slower rate than the distance flown. Experiments prove that the UAV’s early recovery strategy can save UAVs’ resources in large-scale monitoring problems in the MFSDCP, which will reduce a lot of monitoring costs and improve monitoring efficiency under the condition that feasible solutions are obtained.Although MFSDCP in this article has been able to meet the task planning preset in different scenarios in the experiment, the road condition in the real application scenario is uncertain. Therefore, it is very necessary for future research work to carry out real-time planning for routes and how to change the order of sites execution tasks. In addition, the MFSDCP model can be extended in future research work, such as increasing the number of USVs, which may achieve more efficient work in the large-scale monitoring range.



---

*Source: 3426932-2023-02-20.xml*