Minimizing the number of wireless charging PAD for unmanned aerial vehicle–based wireless rechargeable sensor networks

Abstract

In wireless rechargeable sensor networks, most researchers address energy scarcity by introducing one or multiple ground mobile vehicles to recharge energy-hungry sensor nodes. The charging efficiency is limited by the moving speed of ground chargers and rough environments, especially in large-scale or challenging scenarios. To address the limitations, researchers consider replacing ground mobile chargers with lightweight unmanned aerial vehicles to support large-scale scenarios because of the unmanned aerial vehicle moving at a higher speed without geographical limitation. Moreover, multiple automatic landing wireless charging PADs are deployed to recharge unmanned aerial vehicles automatically. In this work, we investigate the problem of introducing the minimal number of PADs in unmanned aerial vehicle–based wireless rechargeable sensor networks. We propose a novel PAD deployment scheme named clustering-with-double-constraints and disks-shift-combining that can adapt to arbitrary locations of the base station, arbitrary geographic distributions of sensor nodes, and arbitrary sizes of network areas. In the proposed scheme, we first obtain an initial PAD deployment solution by clustering nodes in geographic locations. Then, we propose a center shift combining algorithm to optimize this solution by shifting the location of PADs and attempting to merge the adjacent PADs. The simulation results show that compared to existing algorithms, our scheme can charge the network with fewer PADs.

Keywords

Wireless rechargeable sensor networks unmanned aerial vehicle PAD deployment clustering coverage disk

Introduction

Wireless Rechargeable Sensor Networks (WRSNs) provide a promising approach to prolong the lifetime of sensor networks by introducing mobile chargers to recharge energy-hungry nodes.^1–3 In most research works, mobile chargers (MCs) are ground vehicles, such as mobile cars and intelligent robots. However, there are some limitations to use ground vehicle chargers. Commonly, sensor nodes may be deployed in complex and cross-distribution geographical conditions like rivers, land, islands, and rugged mountains. In these challenging scenarios, the harsh terrain may hinder the movement of ground vehicles from one node to another. However, the lightweight Unmanned Aerial Vehicle (UAV) with high speed can adapt to large-scale or challenging scenarios regardless of geographical constraints.^4,5

A few studies have considered introducing the UAV as a mobile charger in WRSNs.^4–7 The UAV works better than ground chargers for charging nodes in large-scale or challenging scenarios, but it consumes more energy in flight. It is impracticable to directly increase the battery size because of the negative impacts on cost and performance.⁸ Therefore, Choi et al.⁹ and Costea and Pleşca¹⁰ developed a Wireless Charging Station (PAD) to recharge the UAV automatically based on some special Wireless Power Transmission (WPT) systems.^11,12 By introducing PADs, the UAV can get energy supplements during charging flights in large-scale or challenging scenarios. Chen et al.¹³ first introduced PADs into UAV-based WRSNs and proposed four heuristic algorithms to minimize the number of PADs. However, these algorithms can only work in the network with uniform node distribution and the central base station (BS). Obviously, they are not practicable and adaptable for typical application scenarios of UAV-based WRSNs.

In this work, inspired by Chen et al.,¹³ we investigate the problem of introducing the minimal number of PADs in a UAV-based WRSN (Minimizing the Number of Deployed PADs, MNDP). Unlike the work in Chen et al.,¹³ our work aims to minimize the number of PADs in scenarios with arbitrary node distribution and arbitrary BS location to exploit the advantages of the UAV. We first define and formulize this problem and then propose a novel PAD deployment scheme, clustering-with-double-constraints and disks-shift-combining (CDC&DSC), to address this problem. CDC&DSC scheme works in two phases. In the first phase, we propose the CDC (clustering-with-double-constraints) algorithm to generate an initial solution to our problem. In the second phase, we propose the DSC (disks-shift-combining) algorithm to optimize the initial solution by shifting the locations of PADs to their nearest neighbors and trying to merge the adjacent PADs. Simulations show that our scheme can adaptively deploy fewer PADs in UAV-based WRSNs than any scheme in Chen et al.¹³

Literature review

Most of the existing studies in WRSNs focused on using ground vehicles recharging nodes. Ren et al.¹ designed an algorithm to maximize charging throughput. Guo et al.² focused on the joint optimization of data gathering and energy replenishment. Moreover, Han et al.³ proposed a multi-chargers collaborative charging scheme to improve the shortages of a single charger in large-scale WRSNs. However, the speed limitations and moving obstructive challenges of ground chargers cannot adapt to large-scale or challenging scenarios. Inspired by the coordinated motion in ad hoc networks,¹⁴ a few works have attempted to provide energy replenishment for mobile chargers during the charging process. In this way, the chargers and nodes charging chargers can collaborate with each other to provide charging services for a large-scale scenario. Zhang et al.¹⁵ presented a collaborative mobile charging scheme for one-dimension sensor networks, in which one mobile charger not only charges the sensor node it is responsible for but also needs to charge the other MC that is moving further away than itself. Madhja et al.¹⁶ presented a hierarchical charging scheme for the networks with the uniform deployment of nodes by introducing a particular type of mobile chargers dedicate to charging the normal charging nodes that charge the sensor nodes. However, these collaborative charging schemes focused on the collaboration between ground charging vehicles and had strong assumptions about deploying sensor nodes.

Recent work applies the lightweight UAV in WRSNs to adapt to large-scale or challenging scenarios to overcome geographical barriers. Griffin and Detweiler¹⁷ developed a specialized WPT system that supports the UAV to transfer power to ground sensor nodes. Lin et al.⁴ proposed a spatial discretization scheme to obtain a UAV charging spot set and maximize the overall charging energy. Wu et al.⁵ considered the UAV hovering energy consumption based on the model by Zeng et al.¹⁸ to minimize the number of hovering points. Considering the shortages of a single UAV, Cetinkaya and Merrett⁷ discussed the multi-UAV charging problem to minimize the number of UAVs.

Although these above schemes have improved the energy efficiency of UAVs, it is still necessary to recharge UAVs during charging tasks to extend the working time and the working range, especially in large-scale or challenging WRSNs.⁸ Campi et al.¹¹ designed a lightweight and efficient WPT system to charge UAV and Cai et al.¹² achieved the larger charging area by multiple extended coils. Furthermore, some researchers developed a small-scale charging station that can be deployed flexibly. Choi et al.⁹ devised an automatic landing pad (PAD) to transfer energy wirelessly through a pair of lightweight induction coils when the UAV is hovering. Costea and Pleşca¹⁰ introduced two automatic charging platforms with direct contact way and wireless way to adapt to different kinds of UAVs.

Based on the above studies, Chen et al.¹³ introduced PADs into UAV-based WRSNs, so that the UAV with low residual energy can fly to a nearby PAD and replenish its energy. To minimize the number of PADs, Chen et al.¹³ proposed four heuristic algorithms for PAD deployment, namely, minimum set cover like (MSC), tree node coloring (TNC), graph node coloring (GNC), and disk cover (DC) algorithms. However, these algorithms only consider the central BS and the uniform distribution of nodes, and cannot verify the superiority of UAVs in large-scale scenarios or challenging scenarios.

Preliminaries

In this section, we first introduce the network model and the UAV consumption model, and then define and formulize the MNDP problem.

Network model

We consider a large monitoring area with a BS, N static sensor nodes, a UAV as the mobile charger, and several PADs. Let $S = {s_{1}, s_{2}, . . ., s_{N}}$ denotes the set of sensor nodes and $P = {p_{1}, p_{2}, . . ., p_{M}}$ denotes the set of PADs. Since BS and PADs similarly work when charging the UAV, they are sometimes collectively referred to as the charging stations in this work for convenience of description. Let $p_{0}$ denotes the BS, and $P' = {p_{0}, p_{1}, p_{2}, . . ., p_{M}}$ denotes the set of charging stations. We also use $p_{i} \in P'$ to denote the location of the PAD/BS deployed. To simplify the problem, the energy supply of each charging station (the BS or a PAD) is unlimited.

Each sensor node $s_{i} \in S$ is powered by a rechargeable battery with energy capacity e and deployed statically on a given location $l (s_{i})$ known by the BS and the UAV. However, the distribution of nodes is unknown. The BS is also deployed arbitrarily according to the network requirement, and it is responsible for data gathering, charging schedule, and serving the UAV.

UAV consumption model

The UAV is powered by a rechargeable battery with high capacity $E_{\max}$ . The UAV charges sensor nodes in the point-to-point charging pattern, which means the UAV has to hover over and fully charge only one node. The UAV flies at a constant speed $V_{U}$ between nodes, PADs, and the BS. The UAV has to fly to the nearest charging station before its energy runs off. During the charging process, the UAV can only get recharging from the charging stations. The UAV departs from a charging station with full energy to charge sensor nodes. We call the duration between the fully charged UAV leaving a charging station and landing at the next charging station for recharging as one charging flight.

The energy consumption of the UAV comprises of two parts, namely, the energy consumed by traveling $E_{travel}$ and the energy consumed by charging $E_{charge}$ . The traveling energy consumption can be divided into two parts: one is the energy consumption of flying between moving targets (nodes/BS/PADs) $E_{mov}$ and the other is the energy consumption of hovering over nodes to perform the energy transferring $E_{hov}$ . We have the UAV consumed energy $E_{consume}$ as follows

E_{c o n s u m e} = E_{t r a v e l} + E_{c h a r g e} = E_{m o v} + E_{h o v} + E_{c h a r g e}

(1)

Let us assume the energy transfer efficiency between the UAV and the charged node is $η$ . We have

E_{charge} = \frac{E_{rec}}{η}

(2)

where $E_{rec}$ is the total amount of energy that charged nodes need to be replenished.

We calculate the moving power $P_{mov}$ and the hovering power $P_{hov}$ of the rotary-wing UAV according to the propulsion power formula derived by Păun et al.¹⁴ The moving energy $E_{mov}$ and the hovering energy $E_{hov}$ for one charging flight can be calculated as follows

E_{hov} = P_{hov} t_{h} = (P_{0} + P_{i}) t_{h}

(3)

E_{mov} = P_{mov} t_{m}

(4)

where $t_{m}$ and $t_{h}$ are the flying time and the hovering time in the current charging flight, respectively. Since $e$ , the time that one sensor node gets fully charged can be approximate as a constant $Δ$ . Therefore, we have

t_{h} = n Δ

(5)

where $n$ is the number of charged nodes in the current charging flight. According to pre-defined $V_{U}$ and $E_{\max}$ , we calculate the maximum flight distance of the UAV $d_{\max}$ as follows

d_{\max} = \frac{E_{\max}}{P_{mov}} \times V_{U}

(6)

The problem definition

Let us first consider the case without introducing PADs. If no PADs are in the network, the UAV only can get charged at the BS. According to the last section, the flight radius of the UAV is $\frac{1}{2} d_{\max}$ . Considering the UAV has to have enough energy to return to the BS after charging one node, the distance $d_{cover}$ between the farthest rechargeable node and the BS has to satisfy the following equation

\frac{1}{2} d_{\max} > d_{cover} \geq \frac{1}{2} \frac{(E_{\max} - P_{hov} Δ - \frac{e}{η})}{P_{mov}} \times V_{U}

(7)

To be simplified, we can use equation (8) in our work

d_{cover} = \frac{1}{2} \frac{(E_{\max} - P_{hov} Δ - \frac{e}{η})}{P_{mov}} \times V_{U}

(8)

We call $d_{cover}$ as the charging coverage range of the UAV. Obviously, in the case without PADs, the UAV only can charge nodes in a cycle area with the location of BS as center and $d_{cover}$ as the radius. Therefore, to charge the nodes outside this cycle area of BS, we have to introduce PADs to replenish the energy of the UAV.

In our work, to easily depict, given a node $s_{i}$ and a charging station $p_{i}$ , if the distance between $s_{i}$ and $p_{i}$ is less than $d_{cover}$ , we call $s_{i}$ is covered by $p_{i}$ and denote this relationship as $s_{i} \in C (p_{j})$ , where $C (p_{j})$ is the set of all the nodes covered by $p_{j}$ . Let $A (p_{j})$ denotes the cycle area $p_{j}$ covered, we also call it the coverage disk of $p_{j}$ .

Once PADs are deployed, each node needs to be covered by at least one charging station to ensure it is chargeable. We call this requirement for PAD deployment as the coverage constraint.

However, since a single UAV is used in our case, the UAV needs to fly between two charging stations to ensure each node is chargeable. In this way, the UAV can charge the nodes in a new charging coverage area after charging all the nodes in the current charging coverage disk. This requirement can be represented as the following: let $dis (p_{i}, p_{j})$ denotes the distance between $p_{i}$ and $p_{j}$ . Given a graph $G = (V, E)$ , where $V = P'$ and $E = {(p_{i}, p_{j}) | dis (p_{i}, p_{j}) < d_{\max}}$ . The $G$ must be a connected graph. We refer to this requirement for PAD deployment as the connectivity constraint.

Based on the above analysis, we can define the problem of minimizing the number of deployed PADs in the UAV-based WRSN below.

Definition 1

The problem of minimizing the number of deployed PADs.

Given a monitoring area $Ω$ , a BS $p_{0}$ , a UAV, and a set of sensor networks (SNs) $S = {s_{1}, s_{2}, . . ., s_{N}}$ , the objective of the MNDP problem is to find some locations to deploy PADs $P = {p_{1}, p_{2}, . . ., p_{M}}$ which minimizes the number of PADs $M$ under the coverage constraint and the connectivity constraint. That is

Min M

(9)

dis (s_{i}, p_{j}) \leq d_{cover}, \forall s_{i} \in S, \exists p_{j} \in P'

(10)

ρ_{i, j} = {\begin{matrix} 1, if dis (p_{i}, p_{j}) \leq d_{\max} \\ 0, otherwise \end{matrix}

(11)

\begin{matrix} \sum_{| Ω |} (ρ_{i},_{Ω (1)} \times (Π_{k = 1}^{| Ω | - 1} ρ_{Ω (k), Ω (k + 1)}) \times ρ_{Ω (| Ω |), j}) \geq 1 \\ \forall p_{i}, p_{j} \in P' \end{matrix}

(12)

Formula (10) ensures the coverage for all nodes with PADs and the coverage radius is different from Chen et al.¹³ Formulas (11) and (12) demonstrate the connectivity for PADs, in equation (12) $Ω$ is a permutation of a subset of $P$ which means the UAV can fly from $p_{i}$ to $p_{j}$ through at least one path combined by other PADs. The problem is an NP-Hard problem deduced by Chen et al.¹³

CDC&DSC

We propose a PAD placement scheme, named CDC&DSC, to address the MNDP problem, which can automatically adapt to network scenarios with arbitrary node distribution and arbitrary BS location. The CDC&DSC scheme works in two phases, so we propose two algorithms, CDC algorithm and DSC algorithm, to accomplish the task of each phase separately. The task of Phase 1 is to generate the initial solution of the MNDP problem, which we achieve using the CDC algorithm. In the CDC algorithm, we first cluster all nodes based on geographic locations, then deploy a PAD at the center of each cluster, and then obtain the initial solution to our problem by adding new PADs to satisfy the coverage constraint and the connectivity constraint. The task of Phase 2 is to optimize the initial solution from Phase 1, which we complete using the DSC algorithm. In the DSC algorithm, we decrease the number of PADs by combing the PADs based on the triangle circumcircle principle after trying to shift each PAD to its nearest neighbor. In the rest of this section, we depict the details of the two algorithms one by one.

CDC algorithm

The goal of the CDC algorithm is to generate an initial solution to the MNDP problem. Essentially, the output of CDC should be a set of PADs with their coverage disks.

Considering the MNDP problem, we must cover all the nodes with as few PADs as possible. Intuitively, the ideal situation is that each node is covered by one and only one PAD. Furthermore, considering the coverage constraint, the geographical locations of nodes covered by the same PAD should be close. Based on the above considerations, we first use a clustering algorithm to cluster the nodes and deploy a PAD in the center of each cluster. Then, we can obtain an initial solution to the MNDP problem by adding some PADs to meet the coverage and connectivity constraints.

The goal of clustering nodes is to determine a series of locations to place PADs to cover the nodes in the network. The node $s_{i} \in C (p_{0})$ is surely covered by the BS. Thus, we only cluster the set of nodes $S' = S - C (p_{0})$ . In our case, we use the K-means algorithm to cluster the nodes. One problem with using the K-means algorithm is that we need to determine the parameter $K$ . We notice that isolated nodes may appear in the network scenarios since our goal is to handle scenarios with arbitrary node distribution and BS locations. The isolated nodes are more difficult to cover than the other nodes. Based on this consideration, we determine the value of $K$ by the number of isolated nodes. Let $d_{i}$ denotes the distance between node $s_{i}$ and its nearest neighbor node $n_{i}$ , and I is the set of isolated nodes. Besides, we denote $α$ as a parameter to adjust $K$ . We have

I = {s_{i} | d_{i} > \sum_{s_{j} \in S'} \frac{d_{j}}{| S' |}}

(13)

K = | α | I | |

(14)

We use the locations of isolated nodes as the initial points of K-means in Figure 1(b). After clustering, we place a PAD in the center of each cluster and generate a coverage disk for each PAD. Then, we check if all nodes are covered. If some nodes are not covered, we select the node farthest from its nearest neighbor node and deploy a PAD in its place $l (s_{i})$ . We repeat the process until all nodes are covered. For the connectivity constraint, we construct a connected graph from the BS with edge length not exceeding $d_{\max}$ . The PADs closest to the graph are added to the connected graph in turn. Suppose the distance between a PAD to be added and the nearest vertex in the graph exceeds $d_{\max}$ . In that case, a new PAD is generated on the line connecting the PAD to the corresponding vertex at a distance $d_{\max}$ from the vertex, until all PADs are added to the connected graph. The details of the CDC algorithm are shown in Algorithm 1.

Figure 1.

The working process of the CDC algorithm. (a) depicts the location of the nodes and BS in a network area, and (b) shows the PADs deployment after clustering the data in (a) and generating the coverage disk for each PAD, while (c) and (d) illuminate the results to meet the coverage constraint and the connectivity constraint, respectively.

Algorithm 1. CDC algorithm.
Input: a sensor node set $S = {s_{1}, s_{2}, . . ., s_{N}}$ , a BS
Output: an initial PAD set $P$
1: $P_{c} \leftarrow \emptyset$
2: $I = {s_{i} \| d_{i} > \sum_{s_{j} \in S'} d_{j} / \| S' \|}, K = \| I \| * α$
3: Calculate $P$ by K-means with $S'$ in which $K = \| I \| * α$ is the initial points
4: Update $C (p_{i})$ for each $p_{i} \in P$
5: $S' = S - ⋃_{p_{i} \in P} C (p_{i})$
6: while $S' \neq \emptyset$ do /Check coverage constraint/
7: Deploy a PAD $p'$ on $l (s_{i})$ with the largest $d_{i}$
8: $S' = S - C (p^{'}), P \leftarrow {p^{'}}$
9: end while
10: $G = (V, E), V \leftarrow {BS}, E \leftarrow \emptyset$
11: while $P \neq \emptyset$ do /Check connectivity constraint/
12: Select $p_{i} \in P$ with the minimal $d (p_{i}, p_{j}), p_{j} \in V$
13: if $d (p_{i}, p_{j}) > d_{\max}$ then
14: Deploy a PAD $p^{'}$ on the line connecting $p_{i}$ and $p_{j}$
15: $V \leftarrow {p'}, E \leftarrow {(p', p_{j})}$
16: else
17: $V \leftarrow {p_{i}}, E \leftarrow {(p_{i}, p_{j})}, P - {p_{i}}$
18: end if
19: end while
20: $P = V$

DSC algorithm

After obtaining a feasible solution $P_{c}$ , and we decrease the number of PADs in the DSC algorithm. To reduce computational complexity, we first delete some redundant PADs in $P_{c}$ . The PAD $p_{i}$ is redundant if the $P_{c}$ still satisfies two constraints after removing $p_{i}$ . We can observe some redundant PADs in Figure 1(d) deleted in Figure 2(a).

Figure 2.

The process to get the minimal PADs with the DSC algorithm: (a) after deleting redundant, (b) after shifting, and (c) after combining.

After deleting the redundant PAD, we merge the adjacent PADs to decrease the number of PADs. Before merging the PADs, we first try to reduce the distance between the PADs by a nearest neighbor shift method to facilitate the next merging operation. Let $Effect_C (p_{i})$ denotes the set of nodes only covered by the PAD $p_{i}$ . We select the PAD with the minimal $Effect_C (p_{i}), i \neq 0$ to perform the following operations. We first shift the PAD location with the step length $d_{Δ}$ toward its nearest neighbor PAD, generate a coverage disk at the new location, and then check the coverage constraint and the connectivity constraint. If these two constraints are not satisfied, we delete the new location and begin the other loop for the next PAD. Otherwise, we continue to shift this PAD with the step length $d_{Δ}$ . We repeat the above process until all PADs have been shifted. Figure 2(b) shows the result of shifting. After all the PADs are shifted, we try to re-delete the redundant PADs.

After the shifting operations, we can merge the adjacent PADs to get the minimal set of PADs. We attempt to perform the adjacent PAD merge operation in the following way. For each neighbor PAD $p_{i}$ of $p_{j}, i \neq 0, j \neq 0, i \neq j$ , we calculate the discrete point set $C (p_{i}, p_{j})$ , which is the set of nodes only covered by $p_{i}$ and $p_{j}$

C (p_{i}, p_{j}) = S - ⋃_{p_{k} \in P, k \neq i, k \neq j} C (p_{k})

(15)

We select the two most distant nodes in $C (p_{i}, p_{j})$ and try to merge $p_{i}$ and $p_{j}$ to a new PAD at the midpoint between these two selected nodes. Suppose the merging result cannot meet both the coverage constraint and the connectivity constraint, we check whether there is an enclosing circle of radius $d_{cover}$ covering $C (p_{i}, p_{j})$ . If there is, we merge $p_{i}$ and $p_{j}$ to a new PAD $p ″$ at the center of this enclosing circle.^19,20 We repeat the above steps until all the $p_{i}, i = 0$ have been tried the merging operation. We show the details in Algorithm 2.

Algorithm 2. DSC algorithm.
Input: an initial PAD set $P$
Output: a final PAD set $P'$
1: Check redundant PADs from $P$ and delete them
2: $P' \leftarrow \emptyset$
3: while $P \neq \emptyset$ do /Shifting PADs/
4: Select $p_{i}$ with the minimal $Effect_C (p_{i}), i \neq 0$
5: while Two constraints are satisfied do
6: Shift $p_{i}$ toward its nearest neighbor PAD with $d_{Δ}$
7: $P - {p_{i}}, P^{'} \leftarrow {p_{i}}$
8: end while
9: end while
10: $P = P'$ , Check redundant again
11: while $P \neq \emptyset$ do /Combining PADs/
12: $N_{i} = {p_{i} \| d (p_{i}, p_{j}) \leq d_{\max}, p_{j} \in P'}$
13: while $N_{i} \neq \emptyset$ do
14: Select $s_{a}$ , $s_{b}$ with the maximal $d (s_{a}, s_{b})$ , $s_{a}, s_{b} \in C (p_{i}, p_{j})$
15: Calculate the midpoint $p'$ of $s_{a}$ and $s_{b}$
16: $P ″ = P' - {p_{i}, p_{j}}, P ″ \leftarrow {p'}$
17: if $P ″$ satisfies two constraints then
18: $P - {p_{j}}, P' = P ″$
19: break
20: else
21: Select $s_{c}$ with the maximal $d (s_{c}, p')$ $s_{c} \in C (p_{i}, p_{j}), c \neq a, b$
22: Calculate circumcenter $p ″$ of triangle with three vertexes $s_{a}$ , $s_{b}$ and $s_{c}$
23: $P ″ - {p'}, P ″ \leftarrow {p ″}$
24: if $P ″$ satisfies two constraints then
25: $P - {p_{j}}, P' = P ″$
26: break
27: end if
28: end if
29: $N_{i} - {p_{j}}$
30: end while
31: $P - {p_{i}}$
32: end while

We give a demonstration of how the DSC algorithm works in Figure 2. Figure 2(a) presents the result of deleting redundant operation on the deployment result in Figure 1(d), while Figure 2(b) and (c) shows the results of shifting operations and merging operations, respectively.

Simulation result

In this section, we evaluate the performance of the proposed scheme. To illuminate the effectiveness of our proposed scheme, we compare it with the four algorithms in Chen et al.¹³ To the best of our knowledge, the work in Chen et al.¹³ and our scheme are the only two works investigating the PADs deployment in a UAV-based WRSN.

We carry out four groups of simulations by varying the size of the network region, the number of nodes, the UAV battery capacity, and the different node distributions, respectively. To verify the adaptability of the proposed scheme to arbitrary BS locations, we transform two BS locations for each group of simulations: the BS-center scenario, where the BS is surrounded by nodes in the center of the network area, and the BS-isolated scenario, where the BS is outside of the network area and the distance to any node is greater than $d_{\max}$ . Due to the algorithms in Chen et al.¹³ cannot work in the scenarios of BS-isolated, we compare our scheme with the four algorithms in the BS-center scenario first. Then, we compare the performance of our scheme in these two scenarios. We take the average results with 10 sets of data to smooth data in each simulation. The default parameters are shown in Table 1.

Table 1.

The default parameters.

Parameters	Value
Region size	16,000 m × 16,000 m
Number of nodes	200
$E_{\max} (10^{4} J)$	7.8
$d_{Δ}$	30
BS location	[8000, 8000] (central) [20,000, 20,000] (isolated)

BS: base station.

The impacts of the region size

Figure 3 presents the simulation results with varying the size of the network region from 10,000 m × 10,000 m to 25,000 m × 25,000 m. As expected, for all the algorithms, the number of PADs increases as the size of the network region increases. The reason is that as the network size increases, the distance between nodes increases, and more PADs are needed to satisfy the coverage constraint. Figure 3(b) shows that the BS-isolated scenario always requires more PADs than the BS-center scenario. This is because we need to introduce additional PADs to ensure the connectivity constraint in the BS-isolated scenario. From Figure 3(a), it is crucial to notice that the number of PADs deployed by the proposed scheme is always less than four comparison algorithms, and this advantage continues to grow as the network area increases. This changing trend demonstrates the proposed algorithm has advantages in WRSNs with large network regions.

Figure 3.

The results of varying the region size. In (a), The blue line is the result of the CDC&DSC algorithm and BS location is in the center. The orange line, the green line, the red line and the purple line represent results of DC, TNC, GNC and MSC algorithm respectively. (b) shows comparisons of the BS-isolated scenario and the BS-center scenario, the blue line denotes BS location is in the center and the orange line denotes BS location is isolated.

The impacts of the number of nodes

Figure 4 depicts the simulation results for varying the number of nodes from 100 to 1000. Comparing with Figure 3, for all the algorithms, the number of PADs is growing slowly as the node number increases in Figure 4. It is because the PAD deployment problem is essentially a coverage problem, and the number of PADs depends mainly on the coverage radius of the UAV and the size of the network while it is less affected by the node density. We also notice that the result of the DC algorithm is always 16 when the node number is over 200. One reason is that the DC algorithm always deploys PADs at the center of each cell after dividing the network area evenly into cells and then removes the PADs of the cells with no node. Therefore, when the node density is above the threshold value (all cells have nodes), the result of the DC algorithm will not change. The other approaches determine the locations of PADs from the geographic distributions of nodes, so an increase in node density has a slight effect on their results. Still, we can find that the proposed scheme achieves the best performance in Figure 4(a). From Figure 4(b), we conclude a similar conclusion within Figure 3(b). The BS-isolated scenario takes more PADs to ensure the connectivity constraint than in the BS-center scenario.

Figure 4.

The results of varying the number of nodes. In (a), The blue line is the result of the CDC&DSC algorithm and BS location is in the center. The orange line, the green line, the red line and the purple line represent results of DC, TNC, GNC and MSC algorithm respectively. (b) shows comparisons of the BS-isolated scenario and the BS-center scenario, the blue line denotes BS location is in the center and the orange line denotes BS location is isolated.

The impacts of the UAV battery capacity

We also vary the UAV battery capacity with the results presented in Figure 5. As the UAV battery capacity increases, the number of PADs of all the schemes decreases.

Figure 5.

The results of UAV energy with the uniform nodes. In (a), The blue line is the result of the CDC&DSC algorithm and BS location is in the center. The orange line, the green line, the red line and the purple line represent results of DC, TNC, GNC and MSC algorithm respectively. (b) shows comparisons of the BS-isolated scenario and the BS-center scenario, the blue line denotes BS location is in the center and the orange line denotes BS location is isolated.

The more energy the UAV itself carries, the larger $d_{\max}$ and $d_{cover}$ become. As a result, each PAD has a larger coverage disk, while the connectivity constraint can be satisfied by fewer PADs. The number of PADs in the proposed scheme is obviously 8–10 less than all the comparing algorithms. One reason is that the four comparison algorithms always deploy PADs at fixed locations: TNC, GNC, and MSC deploy PADs at nodal locations, while DC deploys PADs at the centers of some cells after celling the network area. Also, none of the four comparison algorithms attempted to merge adjacent PADs.

The impacts of the triple Gaussian mixture distribution

We further carry out some simulations to verify the adaptability of the proposed scheme to the arbitrary node distribution. We build a scenario with 300 nodes with a triple Gaussian mixture distribution. We divide 300 nodes into three groups, and each group of 100 nodes is deployed according to a Gaussian distribution. Since the expectation and variance of the three Gaussian distributions are random, the deployment areas of the three groups of nodes may or may not overlap. We vary the UAV battery capacity in this scenario with the results presented in Figure 6. For the DC approach and our proposed scheme, the results are an average of 10 sets of data. Since the TNC, GNC, and MSC may not work in the scenarios with three groups of nodes isolate from each other, for these algorithms, we only counted the results in scenarios where they could work. According to Figure 6(a), the number of PADs decreases as the battery capacity increases. The reason is the same as the previous simulation results in Figure 5(a). Comparing Figure 5(a), the numbers of PADs in this type of scenario are much smaller than in the scenarios with a uniform distribution of nodes. It can be explained as follows. When the mixed Gaussian distribution is obeyed, the nodes are clustered more closely than when the uniform distribution is obeyed. Consequently, the actual network area size becomes smaller, and the performances of all the approaches are improved in this type of scenario. Our proposed algorithm still achieves the minimum number of PADs in this type of scenario.

Figure 6.

The results of UAV energy with the mixed Gaussian distribution nodes. In (a), The blue line is the result of the CDC&DSC algorithm and BS location is in the center. The orange line, the green line, the red line and the purple line represent results of DC, TNC, GNC and MSC algorithm respectively. (b) shows comparisons of the BS-isolated scenario and the BS-center scenario, the blue line denotes BS location is in the center and the orange line denotes BS location is isolated.

In general, the CDC&DSC algorithm outperforms all the comparing algorithms. It can adapt to the scenarios with arbitrary node distribution and arbitrary BS location.

Conclusion

After years of research, the introduction of PADs for UAV energy replenishment has become a promising approach to improve the performance of UAV-based WRSNs. In this article, we investigated the PADs deployment problem for the UAV-based WRSNs. We proposed a novel PADs deployment scheme, named CDC&DSC, to adapt to the scenarios with arbitrary node distribution and arbitrary BS location. We proposed the CDC algorithm to generate an initial deployment of PADs, and then proposed the DSC algorithm to optimize this initial solution in an attempt to merge adjacent PADs and remove redundant PADs by shifting the locations of PADs. Finally, we compared the proposed scheme with four existing PADs deployment approaches through simulations. The results showed that our proposed scheme outperforms the existing methods in all aspects. However, our proposed algorithm deals with the deployment of PADs only to minimize the number of PAD without considering the charging scheduling. In the future, we plan to solve the PADs deployment problem to improve the global charging efficiency by taking the charging demand of nodes and the scheduling of UAVs into account.

Footnotes

Handling Editor: Miguel Acevedo

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Key R&D Program of China (2018YFC0832303).

ORCID iD

Feng Lin

References

Ren

Liang

. Maximizing charging throughput in rechargeable sensor networks. In: Proceedings of the 2014 23rd international conference on computer communication and networks (ICCCN), Shanghai, China, 4–7 August 2014, pp.1–8. New York: IEEE.

Guo

Wang

Yang

Joint mobile data gathering and energy provisioning in wireless rechargeable sensor networks. IEEE T Mobile Comput 2014; 13(12): 2836–2852.

Han

Wang

, et al. A multicharger cooperative energy provision algorithm based on density clustering in the industrial Internet of Things. IEEE Internet Things 2019; 6(5): 9165–9174.

Lin

Guo

Dai

, et al. Near optimal charging scheduling for 3-D wireless rechargeable sensor networks with energy constraints. In: Proceedings of the 2019 IEEE 39th international conference on distributed computing systems (ICDCS), Dallas, TX, 7–10 July 2019, pp.624–633. New York: IEEE.

Xiao

Sha

, et al. Trajectory optimization for UAVs’ efficient charging in wireless rechargeable sensor networks. IEEE T Veh Technol 2020; 69(4): 4207–4220.

Baek

Han

Optimal UAV route in wireless charging sensor networks. IEEE Internet Things 2020; 7(2): 1327–1335.

Cetinkaya

Merrett

. Efficient deployment of UAV-powered sensors for optimal coverage and connectivity. In: Proceedings of the 2020 IEEE wireless communications and networking conference (WCNC), Seoul, South Korea, 25–28 May 2020, pp.1–6. New York: IEEE.

Simic

Bil

Vojisavljevic

Investigation in wireless power transmission for UAV charging. Procedia Comput Sci 2015; 60(1): 1846–1855.

Choi

Jang

Lim

, et al. Automatic wireless drone charging station creating essential environment for continuous drone operation. In: Proceedings of the 2016 international conference on control, automation and information sciences (ICCAIS), Ansan, South Korea, 27–29 October 2016, pp.132–136. New York: IEEE.

10.

Costea

Pleşca

. Automatic battery charging system for electric powered drones. In: Proceedings of the 2018 IEEE 24th international symposium for design and technology in electronic packaging (SIITME), Iaài, 25–28 October 2018, pp.377–381. New York: IEEE.

11.

Campi

Cruciani

Feliziani

, et al. High efficiency and lightweight wireless charging system for drone batteries. In: Proceedings of the 2017 AEIT international annual conference, Cagliari, 20–22 September 2017, pp.1–6. New York: IEEE.

12.

Cai

Wang

Nie

, et al. Effective-configuration WPT systems for drones charging area extension featuring quasi-uniform magnetic coupling. IEEE T Transp Electr 2020; 6(3): 920–934.

13.

Chen

Ouyang

Efficient wireless charging PAD deployment in wireless rechargeable sensor networks. IEEE Access 2020; 8: 39056–39077.

14.

Păun

Rozenberg

Salomaa

(eds). Current trends in theoretical computer science. The challenge of the new century, vol. 1 (Algorithms and complexity). River Edge, NJ: World Scientific, 2004.

15.

Zhang

. Collaborative mobile charging for sensor networks. In: Proceedings of the 2012 IEEE 9th international conference on mobile ad-hoc and sensor systems (MASS’2012), Las Vegas, NV, 8–11 October 2012, pp.84–92. New York: IEEE.

16.

Madhja

Nikoletseas

Raptis

TP.

Hierarchical, collaborative wireless energy transfer in sensor networks with multiple Mobile Chargers. Comput Netw 2016; 97: 98–112.

17.

Griffin

Detweiler

Resonant wireless power transfer to ground sensors from a UAV. In: Proceedings of the 2012 IEEE international conference on robotics and automation, Saint Paul, MN, 14–18 May 2012, pp.2660–2665. New York: IEEE.

18.

Zeng

Zhang

Energy minimization for wireless communication with rotary-wing UAV. IEEE T Wirel Commun 2019; 18(4): 2329–2345.

19.

Nielsen

Nock

A fast deterministic smallest enclosing disk approximation algorithm. Inform Process Lett 2005; 93(6): 263–268.

20.

Wan

Cheng

, et al. An algorithm to optimize deployment of charging base stations for WRSN. EURASIP J Wirel Comm 2019; 2019: 63.