A Long-Distance First Matching Algorithm for Charging Scheduling in Wireless Rechargeable Sensor Networks

Abstract

In large wireless rechargeable sensor networks (WRSNs), the limited battery capacity of sensor nodes and finite network lifetime are commonly considered as performance bottlenecks. Previous works have employed wireless mobile vehicles (vehicles) to charge sensor nodes (nodes), but they face limitations in terms of low speed and offroad terrain. The rapid development of wireless charging drones (drones) brings a new perspective on charging nodes; nevertheless, their use is limited by small capacity batteries and cannot cover large regions alone. Most existing works consider the charging of nodes only with vehicles or drones. However, these solutions may not be robust enough, as some nodes’ energy will have run out before vehicles’ or drones’ arrival. Considering the merits and demerits of vehicles and drones comprehensively, we propose a novel WRSN model whose charging system integrates one vehicle, multiple drones and one base station together. Moreover, a charging strategy named long-distance first matching (LDFM) algorithm to schedule the vehicle and multiple drones collaboratively is proposed. In the proposed scheme, drones that are carried by the vehicle start from the base station. According to distance and deadline of nodes with charging requests, LDFM prioritizes nodes with the longest matching distance for allocation to drones. As a result, the proposed scheme aims to minimize the moving distance of charging scheduling of the WCV on premise of satisfying charging requests with the cooperation of WCVs and drones. Our proposed scheme is thus designed to maximize the efficiency of drone usage and shares the charging burden of the vehicle, which makes WRSNs work well in large and complex terrain regions, such as a hill, natural disaster areas or war zones. Simulation results confirm that our proposed scheme outperforms hybrid scheme in previous work with respect to total number of charging nodes and network energy consumption. Especially with heavy traffic load, the proposed scheme can charge more than 10% additional nodes compared to the hybrid. Moreover, the proposed scheme achieves a reduction of over 50% in the moving distance compared to the hybrid.

1. Introduction

Charging sensor nodes (nodes) with a wireless mobile vehicle (vehicle) is a crucial aspect of wireless rechargeable sensor networks (WRSNs) since it can enhance multiple aspects of network performance. Given the limited residual energy of nodes, it is essential to develop charging scheduling for vehicles as a top priority in WRSNs. Nodes typically transmit data to the base station via one or multiple relay nodes, as specified by the routing protocol [1]. As a result, nodes that are geographically closer to the base station often have to forward significantly more data from remote nodes, which consumes additional energy. Failure to charge these nodes on time can lead to the energy hole phenomenon [2,3], negatively impacting the network’s normal operation. Significant research efforts have been devoted to addressing this issue, including fixed vehicle trajectories [4,5,6,7,8] in periodical schemes. In these schemes, the trajectory is predefined; the vehicle travels along the trajectory to charge each node in a network. However, due to a lack of flexibility, this approach is unable to fully address the problem.

A promising approach to maintaining the perpetual operation of WRSNs is to plan dynamic trajectories for vehicles using an on-demand architecture [9,10,11,12,13,14,15,16] that provides control over the trajectory. In general, nodes send charging request packets to the base station when their residual energy falls below a preset threshold. Vehicles then perform the charging tasks along a dynamic trajectory determined by the base station according to a scheduling scheme. This dynamic trajectory planning is considered as charging scheduling, which not only reduces energy consumption during vehicle movement, but also extends the network’s lifetime to some degree. However, charging nodes solely with vehicles has some disadvantages, including low speed and offroad limitations. These disadvantages can negatively impact the continuous operation of the network when it is deployed in a large and complex terrain region under heavy load, as numerous simultaneous charging requests cannot be met.

Recently, the rapidly growing application of drones is advancing to a new paradigm, which considers charging nodes with wireless charging drones (drones) carrying a wireless charging device [17,18,19,20,21,22]. Drones have high flight speed, more than five times that of vehicles [23]. Additionally, they can fly over obstacles without having to take a detour. Although drones can overcome the disadvantages of vehicles, their small battery capacity still limits the flight distance and the number of charging nodes, thereby restricting their application in a large sensing region.

After comprehensively considering the merits and demerits of vehicles and drones, we first propose a new WRSN model based on on-demand architecture that includes one vehicle, multiple drones, one base station and a set of nodes within a specified sensing region. In this scheme, it is assumed that the base station will plan the most efficient hybrid charging scheduling for both the vehicle and the drones at the same time. However, the novel WRSN model still faces some new challenges. First, an optimal scheduling for one vehicle for visiting predetermined places usually is an NP-hard problem [13,24]. Moreover, scheduling one vehicle and multiple drones at the same time is even more complicated and challenging, and it is hard to find an optimal solution in an efficient way.

This work presents a charging strategy named the long distance first matching (LDFM) algorithm to collaboratively schedule a vehicle and multiple drones in an efficient way. First, LDFM matches nodes with charging requests according to the distance between nodes and their deadline, then allocates the nodes that require the long distance to drones by applying a matching algorithm. The matching algorithm chooses the maximum matching greedily according to the number of drones carried by the vehicle.

The proposed scheme constructs some matching pairs sets by the algorithm presented later in this work. The matching pair with the longest distance is selected first, and two paired nodes are removed from the set. The above process iterates until the number of selected pairs achieves the number of drones being carried by the vehicle, or the node set becomes empty or a single node. In each of a matching pair, the node closer to the base station is allocated to the vehicle, and the other node is allocated to one of the drones. After allocating the nodes, the schedule of the assigned nodes for the vehicle is planned with NJNP starting from the base station, which always considers the nearest sensor to be charged first. Therefore, in the nodes allocated to the vehicle, the node closest to the base station is selected first to be charged by the vehicle in the proposed scheduling algorithm.

Under the premise of charging as many nodes as possible, LDFM can minimize the moving distance of charging scheduling of the WCV, that is to say, it can reduce energy consumption upon moving, improving charging efficiency. Our previous work [25] proposed a hybrid scheme that allocated charging tasks to different vehicles by dividing the sensing region into three circles: inner, middle and outer. Different from the hybrid scheme, LDFM considers the longest distance to be allocated first to significantly reduce the moving distance of the WCV. Also note that the proposed algorithm allows the vehicle to carry multiple drones to charge far away and urgent nodes so that the total traveling time or distance of the low-speed vehicle can be minimized.

Figure 1 depicts the new proposed WRSN system, which integrates one vehicle and multiple drones carried by the vehicle together to construct a more efficient charging system. In the proposed system, the charging requests from sensor nodes are sent to the base station, and the base station computes and plans the charging scheduling tours for the vehicle and drones. When receiving a charging task, the nodes within the flight distance of the base station are charged directly by the drones from the base station, and the residual nodes are allocated to the vehicle or the drones according our proposed LDFM scheme. The vehicle carrying a set of drones departs from the base station and travels along the predefined tour route to visit nodes allocated to it. When the vehicle arrives at a sensor node having a long matching node, a drone takes off and flies toward the target node and hovers around to charge it. After finishing the charging task, the vehicle returns to the base station to wait for the next task.

This scheme maximizes the efficiency of drone usage and significantly shares the charging burden of the vehicle. In large WRSN applications, WRSNs are usually deployed in certain constrained conditions and harsh environments, such as hills, natural disaster areas or war zones. It is difficult for vehicles to move close to some sensor nodes and charge them. Nevertheless, the proposed scheme not only enables the vehicle to charge the sensor nodes in safe area, but also makes the drones charge the nodes in remote and harsh areas. Therefore, the proposed scheme expands the application scenarios of WRSNs, and greatly increases the reliability of WRSNs. Extensive simulations were conducted to evaluate the performance of the proposed scheme. The proposed scheme is compared to a typical hybrid scheduling scheme [25]. Simulation results show that the proposed scheme outperforms the hybrid scheduling scheme with varying configurations with respect to network metrics such as number of nodes being charged in time and network charging efficiency. Especially under heavy traffic load, the proposed scheme can charge more than 10% of additional nodes compared to the hybrid. Moreover, the proposed scheme achieved a reduction of over 50% in moving distance compared to the hybrid.

The contributions of this work are listed below:

• A new proposed WRSN system, which integrates one vehicle and multiple drones carried by the vehicle together to construct a more efficient charging system.
• This work presents a charging strategy called the LDFM algorithm to collaboratively schedule the vehicle and multiple drones in an efficient way.
• LDFM can minimize the moving distance of charging scheduling of the WCV, that is to say, it can reduce energy consumption upon moving, improving charging efficiency.
• Extensive simulations were conducted to evaluate the performance of the proposed scheme. Simulation results show that the proposed scheme outperforms the hybrid scheduling scheme with varying configurations with respect to network metrics such as number of nodes being charged in time and network charging efficiency.

The remainder of this paper is organized as follows: In the Related Work section, we provide a brief overview of current research on WRSNs. Next, in Preliminaries section, we introduce the novel network model proposed in this work, along with the problem statement. We explain our proposed scheme in detail in the Proposed Scheme section. In the Simulation section, we verify the performance of the proposed scheme through simulation. Finally, a conclusion is provided in Section 6.

2. Related Work

Traditional wireless sensor networks (WSNs) are mainly powered by batteries. However, the increasing demand for WSNs has resulted in higher energy consumption of sensor nodes. Their limited battery capacity hinders the development of WSNs. Due to infeasibility and danger of replacing sensors’ batteries in many applications [17,26], previous studies have aimed to maximize network lifetime through energy conservation [27]. Additionally, extending the lifetime of the network can be achieved through mobile data collection methods that balance energy consumption [28,29,30].

Energy consumption and mobile data collection can only prolong the lifetime of network to a limited degree. Therefore, harvesting energy from environmental sources, such as solar power [31,32], to recharge sensor batteries is a promising scheme. However, due to their dynamic nature, energy harvesting is too unpredictable to provide stable energy for sensors.

Wireless power transfer technology (WPT) has recently emerged as a reliable and convenient method for replenishing energy for sensors, resulting in the development of WRSNs, which have attracted significant research attention. Various studies have focused on supplementing nodes via mobile chargers, such as wireless charging vehicles (i.e., vehicle carrying wireless device). In monitoring tasks where environmental parameters remain relatively constant, the energy consumption of nodes can be estimated using historical data, making periodic schemes a popular choice. Lyu et al. [4] proposed a hybrid particle swarm optimization genetic algorithm for periodic charging planning in vehicle with limited energy, ensuring optimal energy utilization and the avoidance of node failures. Tomar et al. [5] designed optimal trajectories for a given number of vehicles based on the routing loads of nodes to maximize the overall network’s lifetime. Liu et al. [6] developed a scheduling algorithm to mitigate data loss by considering node energy and connectivity criticality. Na et al. [7] formulated an NP-hard energy consumption minimization problem for charging IoT devices and proposed an efficient algorithm named best charging efficiency (BCE) to solve it. Jiang et al. [8] jointly considered charging tour planning and mobile charger depot positioning for largescale WSNs, solving the problem through three stages: charging tour planning, candidate depot identification and reduction, and depot deployment and charging tour assignment.

In certain applications, dramatic environment parameters make predicting nodes’ charging demand difficult, necessitating path scheduling schemes based on on-demand charging. For instance, Lin et al. [9] developed a temporal–spatial charging scheduling algorithm aimed at minimizing dead nodes while maximizing energy efficiency to prolong network lifetime, along with a primary and passer-by scheduling algorithm outlined in [16]. Zhao et al. [10] investigated how to schedule vehicles and allocate charging time for each requesting node simultaneously. Tomar et al. [11] proposed a fuzzy logic-based scheduling scheme that blends residual energy, distance to vehicle, and critical node density to plan scheduling. Dong et al. [12] developed their charging strategy from the clustering method, selecting nodes to be charged, charging path, and charging schedule in four aspects. Cheng et al. [13] applied a genetic approach based on sensor deadlines and distance to vehicle to schedule multiple vehicles efficiently. Xu et al. [14] utilized a novel vehicle equipped with multiple battery cells, allowing for unloading battery cells on site with the sensor to save on waiting time during charging. Lastly, Kaswan et al. [15] proposed an efficient method based on a gravitational search algorithm by presenting a novel agent representation scheme and an efficient fitness function combining spatial and temporal constraints.

The rapid development of drone charging technology [23,24] has opened up a new possibilities to charge sensor nodes, making charging scheduling more efficient and flexible. Many researchers have started considering the use of drones to charge sensors wirelessly in sensor networks. For example, due to space constraints on vehicles, Johnson et al. [17] explored the uses of drones to replenish nodes in bridge monitoring. Zorbas et al. [22] investigated the possibility of charging nodes using drones equipped with wireless chargers while minimizing the number of drone positions by adjusting their altitude, which affects power harvesting. Wu et al. [18] described a multi-drone wireless charging method that jointly optimizes the route association and charging routes to maximize total charging utility and devised an efficient approximation algorithm with a 1/3α approximation ratio to solve the bounded route association problem, which is proven to be NP-hard. Wu et al. [19] proposed a novel data collection scheme using drones as mobile collectors, capable of meeting requirements in both small- and largescale scenarios. Wang et al. [20] focused on wirelessly charging sensor nodes via drones and optimized the scheduling of drones to maximize the minimum energy received by all nodes. Lin et al. [21] presented a method using drones to charge nodes for their proposed concept of the period area coverage problem. Chen et al. [25,33] proposed hybrid charging considering the metrics of both drones and vehicles, enabling a WRSN equipped with a collaborative charging system to be applied in large and complex regions.

Although some research has focused on charging nodes using vehicles or drones, there are still some shortcomings, such as offroad and speed constraints for vehicles, and limited battery capacity for drones. To overcome these limitations, this work proposes a novel scheme that employs a single vehicle and multiple drones to charge nodes simultaneously. Furthermore, we designed a charging schedule for hybrid charging modes based on on-demand architecture.

This work is different from the previous work. To the best of our knowledge, we are the first to consider a charging system including vehicles and drones with the LDFM scheduling scheme.

Table 1. Comparison of the proposed model with the previous literature.

Literatures	Vehicle	Drone	Pad	Scheduling Scheme
Proposed model	Used	Used	Not used	LDFM
[33]	Used	Used	Used	K-mean, greedy, static
[25]	Used	Used	Not used	Hybrid
[13]	Used	Not used	Not used	Genetic
[15]	Used	Not used	Not used	Gravitational search
[20]	Not used	Used	Not used	Iterative

compares the charging vehicles and scheduling methods used in our proposed model with those in the previous literature.

3. Preliminaries

To achieve permanent operation of a WRSN, timely replenishment of energy for sensors after sending charging requests is necessary, ensuring all nodes can work steadily during network operations. Moreover, allocating requests for replenishment by the vehicle or drones is a key issue for the novel WRSN model. To reduce the number of nodes that run out of energy, some nodes with an urgent need for charging or located far from the base station should be arranged to be charged by drones. Therefore, finding an optimal allocation scheme of nodes to satisfy all the charging requests is the main issue that needs resolving.

3.1. Network Model

Assume that a WRSN consists of a set of sensor nodes V, a fixed base station v₀, a single vehicle and multiple drones. A WRSN can be represented as a weighted graph G = (V $\cup$ {v₀}, W, E), where nodes sense, generate data and transmit data to the base station through a pre-generated multi-hop path using the adopted routing algorithm [1]. A _Wij in the set W represents Euclidean distances between a pair of node s_i and s_j, while E = {e₁, e₂, …, e_|E|} represents the initial energy of sensor nodes. When the energy of a sensor node falls below a predefined threshold, it sends charging request packets to the base station. The base station communicates directly with the vehicle and drones, which are used to replenish energy for remote nodes according to the charging requests. In a WRSN scenario, a vehicle carrying m drones departs from the base station, completes its task of replenishing energy or charging remote nodes with the help of drones, and returns to the base station to reload before the next mission.

3.2. Energy Consumption and Charging Model

In a WRSN, nodes are responsible for sensing and sending and forwarding data to the base station. Therefore, the energy consumption r_si of a node s_i is given by:

$$r_{si}=\rho {\displaystyle \sum _{k=1,k\ne i}^n{f}_{ki}+C{e}_{ij}({\displaystyle \sum _{k=1,k\ne i}^n{f}_{ki}}+f_i)+E{v}_i}$$

(1)

where ρ, Ce_ij and Ev_i denote the rates of energy consumption for receiving a unit of data, transmitting a unit of data from s_i to s_j and sensing data for s_i, respectively. The data flow rate from node s_k to s_i is denoted by f_ki, while f_i represents the time required for one unit of data of s_i.

The wireless energy charging model that we adopt in [7] is shown as follows:

$$p_r=\frac{G_s{G}_r\kappa }{L_p}{[\frac{\lambda }{4\mathsf{\pi }(d+\zeta )}]}^2{p}_0=\frac{\tau }{{(d+\zeta )}^2}{p}_0$$

(2)

where $\tau =\frac{G_s{G}_r\kappa {\lambda }^2}{16L_p{\mathsf{\pi }}^2}$, p₀ is the source power of charger, p_r is the received power of some node, d is the distance between charger and the node, G_s is the source antenna gain, G_r is the receiving antenna’s gain, L_p is the polarization loss, λ is the wavelength, κ is the rectifier efficiency and ζ is a parameter to adjust Friis’ free space equation for short-distance transmission.

The proposed system utilizes point-to-point energy transfer [34], whereby a wireless charger charges one node at a time by approaching it at the nearest distance to achieving maximum charging efficiency.

3.3. Time Constraint

To prevent the energy of nodes from falling below their minimum capacity e_{min_sn} (i.e., node will not work if its energy below e_{min_sn}), nodes are required to be charged before the residual energy falls below this threshold. When charging requests are sent, the residual lifetime $L_{s_i}$ of s_i is:

$$L_{s_i}=\frac{{\varphi }_{sn}-e_{\min \_sn}}{r_{s_i}}$$

(3)

where ${\varphi }_{sn}$ is the energy threshold of sensors, $e_{\min \_sn}$ of each sensor is the same initial value.

Let $s_{o(k)}$ denote the node index of the kth charged node in charging scheduling, while $s_{o(0)}$ denotes the base station. The moving tour of the vehicle is {base station = $s_{o(0)}$, $s_{o(1)}$, $s_{o(2)}$, …, $s_{o(m)}$, $s_{o(m+1)}$, …, $s_{o(0)}$}. If node s_i is charged by the vehicle, the arrival time ${\tau }_{arrive}^{s_i}$ of the vehicle is given by:

$${\tau }_{arrive}^{s_i^{}}={\displaystyle \sum _{k=1}^{m-1}\frac{e_{\max \_sn}-{\varphi }_{sn}-{\tau }_{arrive}^{s_{o(k)}^{}}{r}_{o(k)}}{r_c}}+{\displaystyle \sum _{k=0}^{m-1}\frac{dist(s_{o(k)},s_{o(k+1)})}{v_c}}$$

(4)

where r_c is the charging speed of vehicle or drone, v_c is the travelling speed of vehicle, dist(s_i, s_j) represents the Euclidean distance of s_i and s_j.

If s_i is charged by a drone, the arrival time ${\tau }_{arrive}^{s_i}$ of the vehicle is denoted by:

$${\tau }_{arrive}^{s_i^{}}={\displaystyle \sum _{k=1}^{m-1}\frac{e_{\max \_sn}-{\varphi }_{sn}-{\tau }_{arrive}^{s_{o(k)}^{}}{r}_{o(k)}}{r_c}}+{\displaystyle \sum _{k=0}^{m-1}\frac{dist(s_{o(k-1)},s_{o(k)})}{v_c}}+\frac{dist(s_{o(m-1)},s_i)}{v_d}$$

(5)

If ${\tau }_{arrive}^{s_i}\le L_{s_i}$, node s_i will be charged within the designated time.

3.4. Collaborative Charging Problem

The energy consumption rates of different nodes are assumed to be varied, as are the requesting nodes during the operation of the network. Scheduling the vehicle and drones appropriately is a complex collaborative problem in the proposed model. Note that while the vehicle charges some nodes, drones can charge other nodes simultaneously. Allocating charging tasks to satisfy all nodes with charging requests is a key issue in the proposed scheme. Moreover, charging as many nodes as possible within the designated time is the main goal of this work. Therefore, the charging problem can be expressed as follows:

Maximize:

$${\displaystyle \sum _{s_i\in S}{c}_i}$$

(6)

Subject to:

$$c_i=\{\begin{array}{c}1,\begin{array}{cc}{\tau }_{arrive}^{s_i}\le L_{s_i}& \end{array}\\ 0,\begin{array}{cc}{\tau }_{arrive}^{s_i}>L_{s_i}& \end{array}\end{array}$$

(7)

$$dist(s_j,s_i)\le \frac{e_{\max \_d}-(e_{\max \_sn}-{\varphi }_{sn}-{\tau }_{arrive}^{s_i^{}}{r}_k)}{r_d},\mathrm{for}\forall s_j\in S_{out\_d},\exists s_i\in S_v$$

(8)

$$dist(s_j,s_{o(0)})\le \frac{e_{\max \_d}-(e_{\max \_sn}-{\varphi }_{sn})}{2r_d},\forall s_j\in S_{in\_d}$$

(9)

As mentioned earlier, the scheduling objective is presented by Formula (6), and the constraints are listed in Formulas (7)–(9). Constraint (8) indicates that the distance between some segments of each charging path of the vehicle and a node charged by one drone cannot exceed the maximum flight distance. Constraint (9) indicates that the distance between the base station and a node charged by one drone starting from the base station cannot exceed half of the maximum flight distance since the drones can fly back to the base station directly after finishing their assigned charging task.

4. Proposed Scheme

The goal of this work is to design an effective charging scheduling scheme for the vehicle and drones. The scheme divides the sensing region into two subregions and consists of three steps: forming the inner circle, allocating charging tasks to the vehicle and drones, and establishing the vehicle’s trajectory. The above three steps are described in detail as follows:

4.1. Step 1: Forming the Inner Circle

Note that nodes located in proximity to the base station must forward packets from other nodes; therefore, the traffic of the whole network is converged to a specific area near base station, resulting in energy hole. This extra task puts a burden on these nodes that can be alleviated through the charging of nearby nodes by drones starting from the base station in the proposed scheme.

To prevent the energy hole phenomenon caused by traffic converging near the base station, the scheme constructs an inner circle with a radius D_dmax/2, centered on the base station. Here, D_dmax is defined as:

$$D_{d\max }=\frac{e_{\max \_d}-(e_{\max \_sn}-e_{\min \_sn})}{r_d}$$

(10)

In the proposed scheme, nodes located within the inner circle are placed in to set $S_{in\_d}$, and charged by drones waiting at the base station. Based on Equation (10), the drones always have sufficient energy to fly from the base station, charge nodes in $S_{in\_d}$ and then return to base station.

Algorithm 1 outlines the procedure for forming the inner circle.

Algorithm 1. Forming the inner circle

Input: A requesting node set S, base station s0, the maximum flight distance of drone Ddmax. Output: $S_{in\_d}$ Step 1: Compute the Euclidean distance from every node to s0 in S. Step 2: for each s in S          if d(s, s0) ≤ Ddmax/2,              $s\to S_{in\_d}$ Step 3: Output $S_{in\_d}$

4.2. Step 2: Allocating Charging Tasks to the Vehicle and Drones

This step involves creating an allocation for all the requesting nodes, with the exception of those within the inner circle. A crucial aspect of this stage is determining whether the nodes will be charged by the vehicle or by drones that are carried by the vehicle.

Theorem 1.

For any scheduling consisting of m (m < |S/S_d|) drones carried by the vehicle, at most m remote nodes can be charged by m drones, and the initial tour of the vehicle is formed with the NJNP [35] principle. If each of m drones is assigned with a single charging task, then the total movement distance of the vehicle achieves an optimal minimum.

Proof of Theorem 1.

Given a set of charging requests S, the subset of nodes that are designated for charging by either the vehicle or drones carried by the vehicle is represented by the set S/S_{in_d}. □

By way of contradiction, if m remote nodes are allocated to m drones carried by the vehicle, the resulting total movement distance l of the vehicle is not the optimal minimum. This implies that there is another total movement distance l’ less than l when m-i (where i = 1, 2, …, m−1) remote nodes are allocated to the drones.

Assuming there is a shortest tour base station = s_o(0)$\to$s_o(1)$\to$s_o(2)$\to$ …$\to$s_o(m)$\to$s_i$\to$s_o(m+1)$\to$ …$\to$ s_o(n) for the vehicle, as illustrated by the solid arrow in Figure 2, there must be an unassigned drone d carried by the vehicle. It is evident that the length of the tour l’ is:

$$l^{\prime }={\displaystyle \sum _{j=0}^{m}dist(s_{o(j)},s_{o(j+1)})}+dist(s_{o(m)},s_i)+dist(s_i,s_{o(m+1)})+{\displaystyle \sum _{j=0}^{o(n)}dist(s_{o(j)},s_{o(j+1)})}$$

(11)

Suppose $dist(s_i,s_{o(m+1)})\le D_{d\max }$. In this case, we can assign node s_i to drone d. Thereafter,

$$l={\displaystyle \sum _{j=0}^{m}dist(s_{o(j)},s_{o(j+1)})}+dist(s_{o(m)},s_{o(m+1)})+{\displaystyle \sum _{j=0}^{o(n)}dist(s_{o(j)},s_{o(j+1)})}$$

(12)

Nonetheless, the triangle inequality theorem states that $l^{\prime }>l$, which contradicts the hypothesis. Consequently, l is undoubtedly the optimal route for the vehicle.

According to Theorem 1, it is apparent that releasing all drones carried by the vehicle (i.e., assigning m nodes to m drones) results in the vehicle traveling the shortest possible distance. Consequently, the first guiding principle for allocating nodes with charging requests is to make full use of drones and distribute the vehicle’s charging task among them.

4.3. Description of the Steps of Allocating Charging Task

The algorithm for allocating charging tasks will be introduced in the following subsections. Firstly, the initial cover sets are constructed. The proposed scheme constructs some matching pairs sets by the following algorithm. Then, allocating which nodes to drones or to the vehicle needs to be discussed. In this step, the matching pair with the longest distance is selected first, and the two paired nodes are removed from the set. Iterate the above process until the number of selected pairs achieves the number of drones being carried by the vehicle, or the node set becomes empty or a single node. In each matching pair, the node closer to the base station is allocated to the vehicle, and the other node is allocated to a drone. Lastly, a final trajectory for the vehicle is established. After allocating the nodes, the schedule of the assigned nodes for the vehicle is planned with NJNP starting from the base station, which always considers the nearest sensor to be charged first.

(1)

Construct the initial cover sets.

This involves creating several initial cover sets based on the nodes with charging requests. To simplify the scheduling problem, we have defined a formal relationship called a “matched pair”, for releasing drones efficiently.

Definition 1 (matched pair).

If two nodes s_u and s_v, have charging requests, such that $dist(s_u,s_v)\le D_{d\max }$, then these nodes form a matched pair, denoted as (s_u, s_v).

Figure 3 provides an example of a matched pair of nodes. Specifically, node v_i and u_j form a matched pair in Figure 3a, but they do not form a matched pair in Figure 3b.

Additionally, Figure 4 demonstrates several matched pairs, including (u₁, v₁), (u₁, v₂), (u₂, v₂), (u₃, v₃), (u₄, v₄), (v₁, v₅). It is evident that the scheduling problem in this step can be reduced to a set cover-like problem.

Definition 2 (Cover).

If nodes v_i and u_j formed a matched pair, we said that they cover each other.

Definition 3 (Set cover-like problem).

Given a node set S, the set cover-like problem requires finding a subset C of set S to satisfy the following equation:

$$\underset{u\in C}{\cup }{A}_u=S-C$$

(13)

where  $A_u$ represents the set of nodes covered by node u.

Algorithm 2 describes the process for creating the cover sets. The computational complexity of this algorithm is O(n²), where n is the size of sensor nodes in the deployed network.

Algorithm 2. Forming of the cover set

Input: A = ∅, a requesting node set S-Sin_d, the maximum flight distance of drone Ddmax. Output: Each cover set Au and the cover set C. Step 1: for each u in S-Sin_d      for each v in S-Sin_d       if u! = v and dist(u, v) ≤ Ddmax          $u\to A_v$          $v\to A_u$ Step 2: for each u in S-Sin_d      $A=A\cup A_u$        C = S − $S_{in\_d}$ − A Step 3: Output the cover set C.

(2)

Assigning the nodes to drones or to the vehicle

This step adopts a greedy algorithm called long-distance first matching (LDFM) to select m matching pairs after computing the Euler distance of each pair. For example, as shown in Figure 4, the matched pairs from the cover set are {(u₁, v₁), (u₁, v₂), (u₂, v₂), (u₃, v₃), (u₄, v₄), (v₁, v₅)}. After computing the Euler distance of each pair, five matching pairs should be selected at most.

The pair set R is equal to $\underset{u\in C,v\in A_u}{\cup }(u,v)$. First, the pair in set R with the longest match distance is given priority for selection. After selecting the longest matched pair (u, v), the distances of node u and v to the base station are computed and compared. If node v is further from the base station than node u, it is assigned to a drone carried by the vehicle, while node u is allocated to the vehicle, and node u is used as a flying stop for the assigned drone for charging node v. Because node v is assigned a drone, it cannot be used as a flying stop; all matched pairs including node v should be removed from set R.

The above process is repeated until the maximum number of drones carried by the vehicle have been allocated or set R is empty.

Figure 4 shows an example of this selection process; matched pair (u₄, v₄) with the longest distance is sorted first, node u₄ is allocated to the vehicle and v₄ is allocated to a drone carried by the vehicle, then followed by (u₁, v₂), (u₁, v₁) and so on.

The process for assigning nodes to drones or the vehicle is described in Algorithm 3. According to Algorithm 3, Step 1 takes O(n) time at most, while Step 2 and Step 3 take O(n) time. Thus, the total computational complexity of Algorithm 3 is O(n²).

Algorithm 3. Assigning the nodes to the drones or vehicle

Input: A match pair R, the base station O1, the number of drones carried by the vehicle m, num = 0; Output: $S_{out\_d}$ and Sv. Step 1: Select the match pair r = (u, v) with the longest match distance in R Step 2: Compute dist(u, O1) and dist(v, O2) Step 3: if dist(u, O1) < dist(v, O2)   $u\to s_v$    $v\to S_{out\_d}$, num++, R/r   Remove the matched pairs, which include node v  else    $v\to s_v$    $u\to S_{out\_d}$, num++   R/r   Remove the matched pair, which includes node u Step 4: if num < m or $R\ne \varnothing$   Go to Step 1 Step 5: $S_v=S_v\cup (S-S_{in\_d}-S_{out\_d}-S_v)$ Step 6: Output $S_{out\_d}$ and Sv

4.4. Step 3: Establishing Finial Trajectory for the Vehicle

This step involves establishing the finial trajectory for the vehicle by selecting the nearest unvisited node in S_v one at a time using a greedy approach named NJNP [35]. NJNP always selects the nearest sensor from the waiting list as the next visiting node. Figure 5 illustrates an example of this process, with the finial trajectory of the vehicle being O₁$\to$v₁$\to$u₁$\to$u₂$\to$u₃$\to$u₄$\to$O₁.

Algorithm 4, which is described as follows, defines the process for establishing the vehicle’s trajectory. The computational complexity of this algorithm is O(n²).

Algorithm 4. Establishing trajectory for the vehicle

Input: A requesting nodes set Sd, the center of outer circle O1 Output: The trajectory $\prod$. Step 1: Set $\prod =\varnothing$, v = O1. Step 2: Choose a node u with the nearest distance in set Sd    $\prod \leftarrow \prod \cup \left\{u\right\}$    Sd = Sd / u    v = u Step 3: $\mathrm{if}{S}_d\ne \varnothing$   Go to Step 2 Step 4: Output $\prod$.

Finally, Figure 6 presents a flowchart of the LDFM scheme proposed in this work. The proposed LDFM scheme consists of Algorithms 1–4. Note that the time complexities of Algorithms 1–4 are O(n), O(n²), O(n²) and O(n²), respectively, where n is the number of sensor nodes deployed in the network. Therefore, the complexity of the proposed algorithm is O(n²).

5. Simulation

This section presents the results obtained from simulated studies of a WRSN to demonstrate the effectiveness of the proposed model and scheme.

5.1. Simulation Settings

The simulation settings involve using a square sensing area for the WRSN with a side length of 500 m, where 1000 sensor nodes are uniformly and randomly placed throughout the area. The base station is situated at the center of the area with coordinates (500, 500) m. We executed all of the simulations in Visual Studio C#2017, which builds a gradient routing tree based on the model proposed in [25]. The simulations use multi-hop topology in the WRSN. Packets were subsequently sent to the base station by nodes with multi-hop through the routing tree.

The simulations assigned a random traffic load to every node. The value of traffic load is uniformly distributed within range [0, x/n], where x/n represents that the probability x/n that each node senses and generates a packet per second. Three traffic loads, light (10/n), medium (50/n) and heavy (100/n), were set in the simulations. A larger value of x indicates a heavier traffic load. That is to say, the larger the value of x is, the heavier the sensing tasks of the nodes. Furthermore, we limited the network’s running time to 50,000 s. The system always runs, even if a node has died. In addition, the vehicles travel according to the predefined schedule during operation time. All simulation results are averaged from 30 simulations.

5.2. Impact of Drones and Network Parameters on the LDFM Scheduling Scheme

The first part of the simulations evaluates the impact of drones on the LDFM scheduling scheme.

(1)

Speed of drones

Specifically, we analyzed the effect of the drones by varying their speeds from 20 to 50 m/s under three different traffic loads, with the vehicle carrying twenty drones departing from the base station. The results of these simulations were measured and are depicted in Figure 7.

Figure 7a shows that the number of charging requests increases as the speeds of the drones increase, since more nodes can be charged at the same time, as demonstrated in Figure 7b. Under light traffic load, the number of charging requests from the sensors is less; the vehicle and the drones can fully meet the charging requests under different drone speeds, so the curve is kept stable, as well as number of nodes being charged within the given time. However, under medium and heavy traffic loads, the number of charging requests increases as the speeds of the drones increase, as well as the number of nodes being charged within the given time. Because the network is busier, there is greater a number of charging requests, and with the increasing speeds of the drones, more charging requests can be fulfilled. This means that the faster the speed of the drone, the timelier the charging of the matched nodes. As a result, the flight times between the matched pair nodes are shorter.

(2)

Impact of number of drones mounted on vehicle

To investigate the effect of the number of drones mounted on vehicle, we conducted simulations with drone numbers ranging from 5 to 30 under medium traffic load. The speed of the drones was fixed at 35 m/s, while the threshold was set at 0.40 (meaning that the residual energy of the nodes is below 0.40  $•$ e_{max_sn}). The resulting performance metrics are shown in Figure 8. Figure 8a shows that the number of charging request packets peak when the number of mounted drones reaches 20. Additionally, Figure 8b indicates that the number of nodes being charged within a given time increases with the number of drones, since more drones are available to share the charging tasks.

Moreover, under light traffic load, the number of charging requests from the sensors is less, the curve remains a near curve, and so do number of nodes being charged within a given time. This is because the network is not busy; thus, one vehicle and five drones can meet all the charging requests from the nodes. However, under medium and heavy traffic loads, more charging requests occur with the increasing number of drones because more drones can meet the charging requests, which keeps more nodes active in the WRSN, and more nodes can be charged within a given time. This means that adopting more drones is useful for improving the performance of the network. However, when the number of drones is more than 15, the performance of the network does not improve significantly because the number of matched pairs is limited to one charging circle.

5.3. Comparison with Another Hybrid Scheduling Scheme

This subsection presents simulations by comparing our proposed LDFM scheme with the hybrid scheduling scheme proposed in [25]. The hybrid scheduling scheme integrates vehicles and drones to allocate charging tasks by dividing the sensing region into three circular subregions (inner, middle and outer rings). Sensor nodes in the inner ring are directly charged by drones from the base station, those in the middle ring are charged by the vehicle and those in the outer ring are charged by drones carried by the vehicle. Notably, the number of drones and a single vehicle is consistent with our proposed scheme.

(1)

Impact of number of drones mounted on vehicle

To evaluate the impact of the number of drones mounted on the vehicle, we conducted simulations with drone numbers ranging from 5 to 30 under three traffic loads. The drone speed was held constant at 35 m/s, and the threshold was set to 0.40. The results are presented in Figure 9. As Figure 9a shows, the number of charging request packets increases as the number of drones increases. Notably, under light traffic load, the LDFM scheme generated the same number of charging request packets as the hybrid scheme. However, under medium and heavy traffic loads, the LDFM scheme generated more charging request packets than the hybrid scheme; in particular, the LDFM obviously performed better under heavy traffic load. Figure 9b demonstrates that the number of nodes charged within a given time increases with the increasing number of drones, and the LDFM scheme obviously outperforms the hybrid scheme because it can charge more nodes within the same time under all three traffic loads. Moreover, from Figure 9c, we can see that the average distance traveled by the vehicle of the LDFM scheme is less than the hybrid scheme under all three traffic loads, which shows that the LDFM scheme wastes less energy on travelling, achieving better charging efficiency. We also note that the average distance under light traffic load is more than under medium and heavy traffic load because the charging requests occur less and dispersedly in one mission under light traffic load but more and densely under heavy traffic load. Specifically, when the number of drones reaches 20, the average distance is kept stable.

The performance of the network obtained using the two schemes is improved with an increased number of nodes. The LDFM scheme obviously outperforms the hybrid scheme with respect to number of nodes being charged within the same time and the average distance under medium and heavy loads. Because the longest distance nodes are allocated to the drones, the time spent on one charging circle is less with LDFM.

(2)

Impact of Thresholds

This subsection presents simulation results for varying node thresholds (ranging from 0.30 to 0.45) under three traffic loads. Figure 10 displays the performance metrics of both schemes under different thresholds across all three traffic loads. The higher the threshold is, the more frequent the charging requests occur. Similarly, the lower the threshold, although the charging requests generated are fewer, the shorter the residual lifetime of the nodes, making the nodes potentially unable to wait for the vehicles’ or drones’ charging service.

As shown in Figure 10a, when the threshold is set at 0.38, the number of charging request packets and nodes being charged within a given time achieve the peak. In particular, the LDFM scheme generates more charging request packets than the hybrid scheme under heavy traffic load. This means that more nodes in the network with LDFM keep active. Furthermore, in Figure 10b,c, the LDFM scheme outperforms the hybrid scheme in terms of the number of nodes being charged within a given time and the average distance traveled by the vehicle under three different traffic loads. This is because, in LDFM scheme, the vehicle travels less distance in one charging circle, which makes the vehicle consume less energy upon travelling between nodes; thereby, the vehicle can return to the base station to wait for the next charging task within a shorter time than the hybrid scheme.

However, with the increasing traffic load, the curves of the performance obtained using the two schemes show fluctuations under medium and heavy loads. The LDFM is still superior to the hybrid. This means that LDFM has better performance.

6. Conclusions

Our work proposes a new WRSN model that employs one vehicle and multiple drones mounted on it for charging sensor nodes. To maximize the number of nodes charged in time, we formulated a collaborative problem and developed an optimal charging task allocation algorithm called LDFM. Our simulation results confirm the effectiveness of our proposed scheme by comparing it with a hybrid scheme from our previous work.

Compared to the previous literature, our proposed model’s use of one vehicle and multiple drones reduces charging costs and improves performance by optimizing charging time and reducing the number of exhausted nodes. In future, we plan to design more effective schemes for the charging task allocation problem. Moreover, an efficient algorithm for recollecting spare drones can be studied for a cost-saving charging system in a WRSN. And, based on the proposed scheme, more proper algorithms will be proposed and optimized and applied in large real-world scenarios with more complex factors.