Optimizing Charging Efficiency and Maintaining Sensor Network Perpetually in Mobile Directional Charging

Abstract

Wireless Power Transfer (WPT) is a promising technology to replenish energy of sensors in Rechargeable Wireless Sensor Networks (RWSN). In this paper, we investigate the mobile directional charging optimization problem in RWSN. Our problem is how to plan the moving path and charging direction of the Directional Charging Vehicle (DCV) in the 2D plane to replenish energy for RWSN. The objective is to optimize energy charging efficiency of the DCV while maintaining the sensor network working continuously. To the best of our knowledge, this is the first work to study the mobile directional charging problem in RWSN. We prove that the problem is NP-hard. Firstly, the coverage utility of the DCV’s directional charging is proposed. Then we design an approximation algorithm to determine the docking spots and their charging orientations while minimizing the number of the DCV’s docking spots and maximizing the charging coverage utility. Finally, we propose a moving path planning algorithm for the DCV’s mobile charging to optimize the DCV’s energy charging efficiency while ensuring the networks working continuously. We theoretically analyze the DCV’s charging service capability, and perform the comprehensive simulation experiments. The experiment results show the energy efficiency of the DCV is higher than the omnidirectional charging model in the sparse networks.

1. Introduction

Wireless power transfer is a promising technology to replenish energy to sensors in Rechargeable Wireless Sensor Networks (RWSN), to keep the network working continuously [1]. Wireless Power Transfer (WPT) is mainly using magnetic resonance coupling [1,2,3] or RF radiation technology [4,5]. To achieve efficient energy transfer in RF radiation technology, it generally requires directional transmission by using high-gain and directional antennas for power transmitters and receivers to focus the energy in narrow energy beams [6]. It has a more stable and higher efficiency of power transfer compared with omnidirectional charging [7]. Consequently, in the mobile directional charging scenario in RWSN, a rechargeable sensor can only receive power from a mobile charging vehicle equipped with a directional power transmitting antenna, or called directional charging vehicle (DCV), when they are located in the covered sector of the DCV’s directional antennas.

Products from Powercast [8] carry out wireless charging by leveraging the electromagnetic radiation technique, with which energy transmitters broadcast the RF energy and receivers capture the energy and convert it to DC. Applications of the electromagnetic radiation technique for wireless charging have been reported in References [9,10,11]. As more and more applications of wireless charging technology have been envisioned, the Wireless Power Consortium [12] has been established to start the efforts of setting an international standard for interoperable wireless charging.

Recently, most research works of mobile charging in RWSN adopted the omnidirectional power transfer model [13,14,15,16,17]. Although some works have studied the directional charger’s deployment problem in RWSN [9,18,19,20], to the best of our knowledge, there is no literature that has studied the mobile directional charging problem. However, a directional antenna provides significant enhancement over the omnidirectional antenna in terms of direction beam [21]. Moreover, when charging distributed sensor nodes, a directional antenna, rather than an omnidirectional antenna, is more energy-efficient because of the smaller proportion of off-target radiation [22]. Inspired by the research issues in the literature on mobile omnidirectional wireless charging scheduling [13,14,15,16,17], and directional charger’s deployment [9,18,19,20], we propose the directional wireless charging optimization problem in this paper. The complex factors of RF power transmission in practical environment are simplified in our research problem.

In this paper, we investigate the mobile directional charging optimization problem in wireless sensor networks. As shown in Figure 1, the data collection sensor network is deployed in a 2D plane area. The sensors transmit data to the sink node through multiple hops route. The charger’s base station serves for the DCV. The DCV starts from the base station and moves along the planned docking spots and path to replenishing energy for all sensors in a charging cycle. The mobile directional charging optimization problem is how to determine the DCV’s docking spots and charging directions in the 2D plane, and plan the moving path through all docking spots to replenish energy for the sensor network. The objective is to optimize Energy Charging Efficiency (ECE) of the DCV while maintaining the sensor network working continuously. The ECE is the ratio of the energy received by all sensors to the energy consumed by the DCV in a charging cycle. This problem is named as Charging Efficiency Optimization Problem (CEOP) of mobile directional charging in RWSN.

The CEOP problem has two main technical challenges. The first challenge is that since both the DCV’s docking spots and its charging orientations are continuous values, it is hard to determine the DCV’s docking spots and charging orientations to meet the charging coverage for all sensors. The second challenge is how to plan a DCV’s moving path that ensures no sensors will run out of energy during the charging cycle.

The CEOP is an NP-hard problem and it is difficult to design a global optimal solution. We consider dividing the CEOP problem into two sub-problems: (1) How to determine the appropriate docking spots of the DCV in the 2D plane and the DCV’s charging direction at each docking spot; (2) How to plan the DCV’s moving path and charging time at each docking spot to meet the network’s energy requirements and optimize the DCV’s energy charging efficiency.

We model the charging docking point planning on the 2D plane as a location optimization of mobile charging with the objective of minimizing the number of docking points under the constraints and of maximizing the charging coverage utility locally. Then, we use the TSP optimization to minimize the charging path loop and maximizing energy charging efficiency for the whole network.

The main contributions are as follow:

• As far as we know, this is the first work investigating the mobile directional charging problem in WRSN aiming to maximize the energy charging efficiency and maintain the networks working continuously.
• We prove that the problem is NP-hard.
• We propose the coverage utility of the DCV’s directional charging, and design an approximation algorithm to determine the docking spots and their charging orientations while minimizing the number of the DCV’s docking spots and maximizing the charging coverage utility. It ensures the mobile charging coverage for all the sensors in the network and improves the energy charging efficiency locally.
• We propose a moving path planning algorithm for the DCV’s mobile charging to optimize the DCV’s energy charging efficiency while ensuring the networks working continuously.
• We theoretically analyze the DCV’s charging service capability, and perform the comprehensive simulation experiments. The experiment results show that energy charging efficiency is higher than omnidirectional charging model in the data collection network.

The remainder of the paper is organized as follows: In Section 2, we review the related work of RWSN; In Section 3, we present the description of directional charging model, network energy consumption and problem definition; In Section 4, we propose the optimization algorithms; In Section 5, we give analysis of network size and area size that one DCV can serve; In Section 6, we present simulation result; Section 7 concludes this paper.

2. Related Works

The existing wireless energy transfer can be divided into Single-Input Single-Output energy transfer model [23,24,25,26,27,28,29,30,31,32,33,34] and Single-Input Multiple-Output energy transfer model [13,14,15,16,17,31,32,33,34,35]. Energy transfer optimization problems can be divided into static charging stations’ deployment [11,18,19,20,35,36,37,38] and mobile charging vehicles’ dispatching problems [13,14,15,16,17,23,24,25,26,27,28,29,30,31,32,33,34].

Mobile omnidirectional wireless charging problem. All existing works considering the mobile wireless charging adopt the omnidirectional power transfer model. Unlike the omnidirectional charging problem, we should not only determine the charging stop point and plan the charging path, but also determine the charging direction at each charging stop point. Yi et al. [13] investigate how to schedule the omnidirectional charging vehicle to maximize its vacation time and achieve higher charging efficiency of sensor networks. Xie et al. [17] investigate the mobile charging problem of co-locating the mobile base station on the wireless charging vehicle. Wu et al. [15] studied the omnidirectional charger vehicle dispatch problem to maximize the network lifetime and improve the energy efficiency for large-scale WSNs. Khelladi et al. [14] modeled the omnidirectional charger dispatching problem as a charging path optimization problem, and aimed to minimize the number of stop locations in the charging path and reducing the total energy consumption of the mobile charger. Jiang et al. [16] consider the on-demand mobile charging problem which schedules the omnidirectional charger to maximize the covering utility.

Directional wireless chargers deployment problem. All existing charging works which adopt the directional power transfer model only concern the directional chargers’ deployment problem in RWSN, rendering them not applicable to our problem. Dai et al. [9] investigated directional chargers’ deployment problem to optimize charging utility for the sensor network. Dai et al. [18] proposed the notion of omnidirectional charging and studied the omnidirectional chargeability under the deterministic deployment of chargers and random deployment of chargers. The goal is to achieve that at any position in the area with any orientation can be charged by directional chargers with power being no smaller than a given threshold. Jiang et al. [19] studied the wireless charger deployment optimization problem, which is to deploy as few as possible chargers to make the WRSN sustainable. Ji et al. [20] further investigated the deployment optimization problem of wireless chargers equipped with 3D beamforming directional antennas, and achieve the deployment of as few as possible chargers to make the WRSN sustainable.

To best of our knowledge, this is the first work to study the mobile directional charging problem in RWSN. The closest to our work is mobile omnidirectional charging and deployment of directional charger. Compared with omnidirectional power transfer model, there are two strengths to introduce directional power transfer model in mobile charging application in RWSN. The first is that in the sparse sensor networks, using high gained RF radio directional power transfer antenna can reduce energy transmission waste and improve energy charging efficiency. The second is that the directional charger can cover longer distance and transfer more stable energy.

3. Problem Formation

Table 1. Symbol and Notations.

Symbol	Meaning
$s_k$	Coordinate of docking spot $k$
$o_i$	Coordinate of sensor node $i$
$\overrightarrow{{\theta }_{s_k}}$	DCV’s charging orientation at docking spot $k$
$\mathrm{d}\left(s_k,o_i\right)$	Euclidean distance between sensor node $o_i$ and the docking spot $s_k$
$P_{k,i}\left(s_k,o_i\right)$	DCV’s energy transfer function at docking spot $s_k$ for sensor node $o_i$
$A$	Charging angle of DCV (°)
$v$	The moving speed of DCV ($\mathrm{m}/\mathrm{s}$)
$D$	Effective charging distance of DCV (m)
$P_{out}$	Energy transmit power of DCV ($\mathrm{J}/\mathrm{m}$)
${\omega }_c$	Moving energy consumption of DCV ($\mathrm{J}/\mathrm{m}$)
$C_{max}$	Energy capacity of DCV
${\omega }_{o_i}$	Energy consumption of sensor node $i$
$e^s$	Energy consumption for sensing one unit data
$e^t$	Energy consumption for transmitting one unit data
$e^r$	Energy consumption for receiving one unit data
$R_{o_i}$	Sensing data generation rate of sensor node $i$
L × L	Size of the area

describes the symbols used in this paper.

3.1. Directional Charging Model

As shown in Figure 2, we introduce the DCV’s directional power transfer model as follows. When the effective charging distance of directional charger is $D$ and charging coverage angle is A, the effective charging coverage area is a sector determined by its docking spot $s_k$ and charging orientation vector $\overrightarrow{{\theta }_{kj}}$.

For a sensor node $o_i$ is located at $z_{o_i}$, in order to determine whether the node $o_i$ can be charged by the DCV stopped at docking spot $s_k$ with charging orientation vector $\overrightarrow{{\theta }_{s_k}}$, we have two judgment conditions: (1) The node $o_i$ is within the coverage angle A of the charger, denotes as inequality (1); and, (2) The distance between node $o_i$ and charger is less than D, denotes as inequality (2).

$$\left( \overrightarrow{s_k-z_{o_i}}\right)\times \overrightarrow{{\theta }_{s_k}}\ge \parallel s_k{z}_{o_i}\parallel \times cos\left(\frac{A}{2}\right)$$

(1)

where $\parallel s_k{z}_{o_i}\parallel$ denotes the distance between the location of the charger $s_k$ and the location of sensor node $z_{o_i}$.

$$\parallel s_k{z}_{o_i}\parallel \le D$$

(2)

We refer the RF wireless charging model in Reference [11] to calculate a node’s energy received from a wireless charger:

$$P_r=\frac{G_s{G}_r\eta }{L}{\left(\frac{\lambda }{4\pi \left(d+\beta \right)}\right)}^2{P}_{out}$$

(3)

where $d$ is the distance between a sensor node and a wireless charger, $P_{out}$ is the charger’s transmission power, $G_s$ is the transmitting antenna gain, $G_r$ is the node’s receiving antenna gain, $L$ is polarization loss, $\lambda$ is the wavelength, $\eta$ is rectifier efficiency, and $\beta$ is a parameter to adjust the Friis’ free space equation for short distance transmission. Except for distance $d$, all other parameters in Equation (3) are constant values based on the environment and device settings. Therefore, we simplify the charging model in Equation (3) as Equation (4).

$$P_r=\frac{\alpha }{{\left(d+\beta \right)}^2}$$

(4)

where $d$ is the distance from a sensor node to the DCV, and $\alpha$ represents other constant environmental parameters including $P_{out}$, $G_s$, $G_r$, $L$, $\lambda$ and $\eta$ in Equation (3).

From Equation (4), we can deduce $P_{k,i}\left(s_k,o_i\right)$, the effective charging power of the sensor node $o_i$ received from the DCV which stopped at docking spot $s_k$ with charging orientation vector $\overrightarrow{{\theta }_{s_k}}$:

$$P_{k,i}\left(s_k,o_i\right)=\{\begin{array}{c}\begin{array}{cc}\frac{\alpha }{{\left(d\left(s_k,o_i\right)+\beta \right)}^2},& \begin{array}{c}\parallel s_k{z}_{o_i}\parallel \le D and\\ \begin{array}{c}\left(\overrightarrow{s_k-z_{o_i}}\right)\times \overrightarrow{{\theta }_{s_k}}\ge \\ \parallel s_k{z}_{o_i}\parallel \times cos\left(\frac{A}{2}\right)\end{array}\end{array}\end{array}\\ \begin{array}{cc}0,& others\end{array}\end{array}$$

(5)

3.2. Network Energy Consumption Model

We consider that each sensor node consumes energy for data sensing, transmission, and reception. We assume sensor node $o_i$ generates sensing data with a rate $R_{o_i}$($\mathrm{b}/\mathrm{s}$). Assuming $PSN\left(o_i\right)$ is the set of previous sensor nodes that use sensor node $o_i$ on the routing path to the sink node. Equation (6) shows the total energy consumption of sensor node $o_i$.

$${\omega }_{o_i}={{\displaystyle \sum }}_{o_{l\in PSN\left(o_i\right)}}\left(e^t+e^r\right)\times R_{o_l}+\left(e^t+ e^s\right)\times R_{o_i}$$

(6)

Here $e^s$, $e^t$, and $e^r$ represent the energy consumption of one unit data for sensing, transmitting, and receiving respectively [15].

Then we determine the data routing of the network through the minimum energy routing [39]. As shown in Figure 3, nodes $o_1$,$o_2$,$o_3$,$o_4$, and $o_5$ sending data to the sink node through node $o_6$. Then, we have $PSN\left(o_6\right)=\left\{o_1,o_2,o_3,o_4,o_5\right\}$.

3.3. Problem Formulation

We consider a set of wireless rechargeable sensor nodes $O=\left\{o_1,o_2,\dots ,o_N\right\}$ randomly distributed on a $L\times L$ 2D area, each sensor node $o_i$ generates sensing data with a rate $R_{o_i}$($\mathrm{b}/\mathrm{s}$), $i\in N$. There is a sink node located at Base Station which gathers the data from all sensors in the sensor network. A Multi-hop data routing tree is constructed for forwarding all sensing data to the sink node, as shown in Figure 4.

Aiming to keeping the network working continuously, a DCV with an energy capacity of $C_{max}$ is periodic dispatched to travel through a set of Docking Spots ($DS=\left\{s_1,s_2,\cdots ,s_M\right\}$), $M$ denotes the number of docking spots. The DCV stops at each docking spot and rotates its RF charging antenna to a specific orientation to charging the nearby sensors.

In a charging cycle, the DCV starts from the base station, moves through each docking spot and finally returns back to the base station to wait for the next charging cycle. The charging cycle T consists of the moving time $T_{mov}$, the charging time $T_{cha}$, and the time rest at the base station $T_{res}$. The moving time $T_{mov}$ is determined by the length $L_c$of the DCV’s moving path and moving speed v. The charging time $T_{cha}$ is the sum of the dwell times at all docking spots, denote as $T_{cha}=\{t_1+\dots +t_k+\cdots +t_M\}$. The remaining time of each cycle is the DCV’s rest time $T_{res}$.

$$T=T_{res}+T_{mov}+T_{cha}=T_{res}+\frac{L_c}{v}+{\displaystyle \sum }_{k=1}^M{t}_k$$

(7)

Here $\raisebox{1ex}{$L_c$}\!\left/ \!\raisebox{-1ex}{$v$}\right.$ denotes moving time of the DCV, $t_k$ denotes the DCV’s charging time at docking spot $s_k$, the sum of $t_k$ denotes the total charging time of the DCV.

Assume the DCV travels through DS to charging the sensor network. The DCV stops at a docking spot $s_k$ and rotates to a specific charging orientation vector$\overrightarrow{{\theta }_{s_k}^l}$. The sensor nodes which are effectively covered by the DCV denote as $SN{C}_k^l\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$. The DCV’s dwell time is $t_k$ at docking spot $s_k$.

For a DCV’s charging Path, $CP=BS⇢s_{p1}⇢\cdots s_{pk}⇢\cdots s_{pM}\},s_{pk}\in DS$, we define $E_{ECE}$, the Effective Charging Energy received by all sensor nodes from DCV in a charging cycle T as follows:

$$E_{ECE}={{\displaystyle \sum }}_{s_k\in DS}{{\displaystyle \sum }}_{o_i\in SN{C}_k^l\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{P}_{k,i}\left(s_k,o_i\right)\times t_k$$

(8)

Here $P_{k,i}\left(s_k,o_i\right)$ denotes the receiving power of the sensor node $o_i$ when the DCV is at docking spot $s_k$; and $SN{C}_k^l\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$ denotes the sensor set covered by the DCV at $s_k$ and charging direction $\overrightarrow{{\theta }_{s_k}^l}$.

In a charging cycle T, the DCV’s energy consumption includes moving and charging energy, denote as $E_{mov}$ and $E_{cha}$ respectively. Charging consumption is determined by charging time and the DCV’s output power $P_{out}$. Moving energy consumption is determined by the length of path $L_c$ and its energy consumption per unit of moving length ${\omega }_c$. Then the DCV’s Energy Consumption, $E_{DCV}$ is denoted as Equation (9).

$$E_{DCV}=E_{mov}+E_{cha}=P_{out}{\displaystyle \sum }_{k=1}^M{t}_k+{\omega }_c\times L_c$$

(9)

Here $t_k$ denotes the DCV’s charging time at docking spot $s_k$, $L_c$ denotes the DCV’s length of moving path, ${\omega }_c$ denotes DCV’s consumption power of moving.

We define the DCV’s Energy Charging Efficiency as follows.

Energy Charging Efficiency$\eta$: the ratio of effective charging energy received by the network to the DCV’s total energy consumption in a charging cycle $T$, denoted as Equation (10):

$$\eta =\raisebox{1ex}{$E_{ECE}$}\!\left/ \!\raisebox{-1ex}{$E_{DCV}$}\right.$$

(10)

Here $E_{ECE}$ denotes the Effective Charging Energy received by all sensor nodes from DCV in a charging cycle which can be calculated by Equation (8), and $E_{DCV}$ denotes the DCV’s energy consumption in a charging cycle which can be calculated by Equation (9).

We define the residual energy value of node $o_i$ at the time $\tau$ as $e_{o_i}\left(\tau \right)$ in a charging cycle. The node’s residual energy value at any time should be not lower than minimum value $E_{min}$, and not greater than maximum value $E_{max}$.

The variation of node’s residual energy value in a cycle is divided into three stages: 1) before charging; 2) charging stage; 3) after charging. For a sensor node $o_i$, $e_{o_i}\left(\tau \right)$ varied in a charging cycle T as shown in Figure 5. $c_k$ denotes the arrival time of the DCV at docking spot $s_k$ in the first cycle T, $t_k$ denotes the DCV’s dwell time at docking spot $s_k$.

The DCV carries limited energy $C_{max}$, so we have to make sure that the energy consumed by the charging car is no more than $C_{max}$ in a cycle.

We define the CEOP problem of mobile directional charging as follow:

For the set of wireless rechargeable sensor nodes $O=\left\{o_1,o_2,\dots ,o_N\right\}$ randomly distributed on a $L\times L$ 2D area, how to plan the charging docking spots and charging path where the DCV moves along the path to replenishing energy for all sensors and maintains the sensor network working continuously. The objective is to maximize the DCV’s energy charging efficiency while maintaining the network working continuously.

CEOP problem is formulated as follow:

$$\begin{gathered} \begin{array}{cc}max& \eta \end{array}=\raisebox{1ex}{$E_{ECE}$}\!\left/ \!\raisebox{-1ex}{$E_{DCV}$}\right. \\ \begin{array}{cc}s.t.& E_{min}\le e_{o_i}\left(\tau \right)\le E_{max}\end{array},o_i\in O,0\le \tau \le \omega T \\ {e}_{o_i}\left(\tau \right)=\{\begin{array}{c}{e}_{o_i}\left(\omega T\right)-{\omega }_{o_i}\times \tau ,\tau \in \left[\omega T,\omega T+c_k\right]\\ E_{min}+\left(P_{k,i}\left(s_k,o_i\right)-{\omega }_{o_i}\right)\times \tau ,\tau \in (\omega T+c_k,\omega T+c_k+t_k]\\ E_{max}-{\omega }_{o_i}\times \tau ,\tau \in (\omega T+c_k+t_k,\left(\omega +1\right)T]\end{array} \\ {E}_{ECE}={{\displaystyle \sum }}_{s_k\in DS}{{\displaystyle \sum }}_{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{P}_{k,i}\left(s_k,o_i\right)\times t_k \\ {E}_{DCV}=P_{out}{\displaystyle \sum }_{k=1}^M{t}_k+{\omega }_c\times L_c \\ {E}_{DCV}\le C_{max} \end{gathered}$$

(11)

Here $\eta$ denotes Energy Charging Efficiency,$E_{max}$ denotes the maximum capacity of node, $E_{min}$ denotes minimum energy value of node. $e_{o_i}\left(\tau \right)$ denotes residual energy value of node $o_i$ at the time $\tau$,when $\tau \in \left[\omega T,\omega T+c_k\right]$, $e_{o_i}\left(\tau \right)=e_{o_i}\left(\omega T\right)-{\omega }_{o_i}\times \tau$, $e_{o_i}\left(\tau \right)$ denotes the remaining energy of the node before charging, when $\tau \in (\omega T+c_k,\omega T+c_k+t_k]$, $e_{o_i}\left(\tau \right)=E_{min}+\left(P_{k,i}\left(s_k,o_i\right)-{\omega }_{o_i}\right)\times \tau$, $e_{o_i}\left(\tau \right)$ denotes the remaining energy of the node during charging, when $\tau \in (\omega T+c_k+t_k,\left(\omega +1\right)T]$, $e_{o_i}\left(\tau \right)=E_{max}-{\omega }_{o_i}\times \tau$, $e_{o_i}\left(\tau \right)$ denotes the remaining energy of the node after charging. $E_{ECE}$ denotes the Effective Charging Energy received by all sensor nodes from the DCV in a charging cycle, $E_{DCV}$ denotes the DCV’s energy consumption in a charging cycle, $C_{max}$ denotes maximum energy capacity of the DCV.

4. Design and Analysis of Algorithms

It is difficult for the CEOP problem to be solved directly. We solve the problem in two steps and divide it into two sub-problems:

(1)

First, we find the set of Docking Spots ($DS=\left\{s_1,s_2,\cdots ,s_M\right\}$) and their corresponding Charging Orientation ($CO=\left\{\overrightarrow{{\theta }_{s_1}},\overrightarrow{{\theta }_{s_2}},\cdots ,\overrightarrow{{\theta }_{s_M}}\right\}$) to maximize the charging coverage utility and ensure the mobile charging coverage of the network (Section 3.1).

(2)

Second, we plan the DCV’s charging path to travel through all docking spot in DS and the charging residence time at each docking spot to optimize the overall energy charging efficiency while maintaining the sensor network working continuously (Section 3.2).

4.1. Find Charging Docking Spots and Charging Directions

For the 2D plane on which the sensors are randomly deployed, we divide it into grids, and take grid vertices as the DCV’s possible docking spots. Then we find the minimum number of the DCV’s candidate docking spots and their charging directions to optimize the charging coverage utility locally while achieving mobile charging coverage for the whole network.

We define the DCV’s Charging Coverage Utility at docking spot $s_k$ on the charging orientation $\overrightarrow{{\theta }_{s_k}^l}$ as the sum of received power of the charging covered nodes:

$$U\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)={{\displaystyle \sum }}_{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{P}_{k,i}\left(s_k,o_i\right)$$

(12)

where $SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$ denotes the sensor nodes covered at docking spot ${\mathrm{s}}_{\mathrm{k}}$ in charging orientation $\overrightarrow{{\theta }_{s_k}^l}$.

Suppose at the docking spot $s_k$, the DCV has $Q_k$ optional charging directions, i.e., {$\overrightarrow{{\theta }_{s_k}^1}$,$\overrightarrow{{\theta }_{s_k}^2}$,…$,\overrightarrow{{\theta }_{s_k}^{Q_k}}$}. The maximum charging coverage utility at docking spot $s_k$ is $U_{max}\left(s_k\right)$:

$$U_{max}\left(s_k\right)=max\left\{U\left(s_k,\overrightarrow{{\theta }_{s_k}^1}\right),U\left(s_k,\overrightarrow{{\theta }_{s_k}^2}\right)\cdots U\left(s_k,\overrightarrow{{\theta }_{s_k}^{Q_k}}\right)\right\}$$

(13)

Here $U\left(s_k,\overrightarrow{{\theta }_{s_k}^{Q_k}}\right)$ denotes charging coverage utility at docking spot ${\mathrm{s}}_{\mathrm{k}}$ in charging orientation $\overrightarrow{{\theta }_{s_k}^l}$.

For $num$ grid points on the discrete 2D plane, we get the vertex set of grids: $CS=\left\{cd{s}_1,\cdots ,cd{s}_k,\cdots ,cd{s}_{num}\right\}$,$cd{s}_k$ is coordinates of vertexes. We have to choose a set of candidate docking spots $S=\left\{s_1,\cdots ,s_k,\cdots ,s_M\right\},s_k\in CS$, and their corresponding charging direction $\theta =\left\{{\theta }_{s_1},\cdots ,{\theta }_{s_k},\cdots ,{\theta }_{s_M}\right\},{\theta }_{s_k}\in \left\{{\theta }_{s_k}^1,\dots ,{\theta }_{s_k}^{Q_k}\right\}$, where $s_k$ has $Q_k$ possible charging directions. We use $U_{sum}^{max}\left(s\right)$ denotes the maximum coverage utility of the set S of candidate docking spots as Equation (14).

$$\begin{gathered} U_{sum}^{max}\left(S\right)={\displaystyle \sum }_{k=1}^M{U}_{max}\left(s_k\right) \\ S=\left\{s_1,\cdots ,s_k,\cdots ,s_M\right\}, s_k\in CS \\ \theta =\left\{{\theta }_{s_1},\cdots ,{\theta }_{s_k},\cdots ,{\theta }_{s_M}\right\}, {\theta }_{s_k}\in \left\{{\theta }_{s_k}^1,\dots ,{\theta }_{s_k}^{Q_k}\right\} \end{gathered}$$

(14)

As shown in Figure 6, there are three candidate docking spots $s_1$, $s_2$, and $s_3$. The docking spot $s_1$ can choose two possible orientation {$\overrightarrow{{\theta }_{s_1}^1}$, $\overrightarrow{{\theta }_{s_1}^2}$}, the docking spot $s_2$ can choose two possible orientation {$\overrightarrow{{\theta }_{s_2}^1}$, $\overrightarrow{{\theta }_{s_2}^2}$}, and the docking spot $s_3$ can choose orientation {$\overrightarrow{{\theta }_{s_3}^1}$}. Therefore, there are five different coverage utility of different combinations of docking spots and orientation vectors. We can calculate the possible coverage utilities at $s_1$, $s_2$, and $s_3$ according to Equation (12). For $s_1$, two possible coverage utilities are presented as Equation (15). For $s_2$, two possible coverage utilities are presented as Equation (16). For $s_3$, one possible coverage utility is presented as Equation (17).

$$\{\begin{array}{c}U\left(s_1,\overrightarrow{{\theta }_{s_1}^2}\right)=P_{1,4}\left(s_1,o_4\right)\\ U\left(s_1,\overrightarrow{{\theta }_{s_1}^1}\right)=P_{1,1}\left(s_1,o_1\right)+P_{1,1}\left(s_1,o_2\right)\end{array}$$

(15)

$$\{\begin{array}{c}U\left(s_2,\overrightarrow{{\theta }_{s_2}^1}\right)=P_{2,1}\left(s_2,o_4\right)+P_{2,5}\left(s_2,o_5\right)\\ U\left(s_2,\overrightarrow{{\theta }_{s_2}^2}\right)=P_{1,6}\left(s_2,o_6\right)\end{array}$$

(16)

$$U\left(s_3,\overrightarrow{{\theta }_{s_3}^1}\right)=P_{3,2}\left(s_3,o_2\right)+P_{3,3}\left(s_3,o_3\right)+P_{3,6}\left(s_3,o_6\right)$$

(17)

As shown in Figure 6, we can get $U_{max}\left(s_1\right)$ and $U_{max}\left(s_2\right)$ respectively, as Equations (18) and (19).

$$U_{max}\left(s_1\right)=U\left(s_1,\overrightarrow{{\theta }_{s_1}^1}\right)$$

(18)

$$U_{max}\left(s_2\right)=U\left(s_2,\overrightarrow{{\theta }_{s_2}^1}\right)$$

(19)

Then we get the maximum coverage utility of candidate set $S=\left\{s_1,s_2,s_3\right\}$ and their related charging directions $\theta$ ={${\theta }_{s_1}^1,{\theta }_{s_2}^1,{\theta }_{s_3}^1$}, $U_{sum}^{max}\left(S\right)=U\left(s_1,\overrightarrow{{\theta }_{s_1}^1}\right)+U\left(s_2,\overrightarrow{{\theta }_{s_2}^1}\right)+U\left(s_3,\overrightarrow{{\theta }_{s_3}^1}\right)$.

The DCV’s energy loss includes charging energy loss and moving energy costs. At each docking spot, we aim to reduce the DCV’s charging loss and get higher charging effectiveness. By minimizing the number of docking spots, we can reduce the DCV’s moving energy cost in the process of mobile charging. Additionally, maximizing charging coverage utility can reduce the charging energy loss at each docking spot. Hence it finally improves the energy charging efficiency in mobile directional charging.

To find the candidate docking spots and their charging directions for improvement of the mobile charging energy efficiency, we propose the two-objective optimization problem as Equation (20), that is Minimizing the number of Stop points and Maximizing charging Coverage Utility under the constraint of charging coverage of all sensors, called the MSMCU (Minimizing the number of Stop points and Maximizing charging Coverage Utility) problem.

$$\begin{gathered} \begin{array}{cc}min& {\displaystyle {\displaystyle \sum }_{k=1}^{num}}{a}_k\\ max& {\displaystyle {\displaystyle \sum }_{k=1}^{num}}U\left(s_k,\overrightarrow{{\theta }_{s_k}}\right)\\ s.t.& {\displaystyle {\displaystyle \sum }_{k=1}^{num}}{a}_k\times x_{i,k}\ge 1, 1\le i\le N\end{array} \\ {x}_{i,k}=\{\begin{array}{c}1,if o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)\\ 0,if o_i\notin SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)\end{array} \end{gathered}$$

(20)

where $a_k$ is a binary decision variable that is equal to 1 if region $s_k$ belongs to the minimum stops, and to 0 otherwise. Additionally, the $n$ inequality constraints ensure that every node must belong to at least one stop region in the minimum stops. We analysis Equation (20), give Theorem 1 and the proof of Theorem 1.

Theorem 1.

The MSMCU problem of finding specified docking spots and orientations with minimum the number of stops and maximum coverage utility is NP-hard.

Proof of Theorem 1.

We prove Theorem 1 by giving a special instance of the problem and explaining that the instance is NP-hard.

Instance. We assume that the coverage utility is the maximum as long as a sensor is covered, then the problem can be reduced to solve the Minimum Set Covering Problem. Because the Minimum Set Covering Problem is NP-hard, the MSMCU problem is also NP-hard. □

Then we propose a Greedy approximation algorithm of Maximum Coverage Utility (GMCU). GMCU algorithm firstly divides a 2D plane into grids. Secondly, it takes each grid vertex as a possible stop point and computes its optimal charging Direction and Maximum Coverage Utility (DMCU). Finally, it selects a set of candidate stop points to achieve overall maximum utility and network charging coverage. Let us first introduce the GMCU algorithm, and then introduce the DMCU algorithm.

(1) GMCU algorithm

In the GMCU algorithm, we divide the plane into grids, and take each vertex as a possible docking spot. The coverage of the charger is a 90° sector with radius D. The DCV only chooses one orientation to charge each time it stops, so if the grid’s size is too large, some nodes will be missed. The grid’s size $d$ must satisfy Equation (21)

$$d\le \sqrt{2}/2\times D$$

(21)

The GMCU algorithm firstly divides a 2D plane into grids, take each grid vertex as a possible docking spot, denoted as $CS$, and $cd{s}_i$ represents coordinates of vertexes. Put each $cd{s}_i$ into the DMCU algorithm to calculate the maximum coverage utility and the covered nodes set. Choose the docking stops with the maximum value of coverage utility until all nodes are covered. The outputs are the docking spot set ($DSS$) and the set of covered nodes set ($SANC$) at corresponding directions.

The procedure of GMCU algorithm is presented in

Table 2. The Procedure of the GMCU (Greedy approximation algorithm of Maximum Coverage Utility) Algorithm.

GMCU algorithm: find candidate docking spots and their charging directions

Input: The length of area: L; Farthest distance DCV can reach: D; Charging angle of DCV: A Discrete the L x L plane into grids, get the vertex set of grids: $CS=\left\{cd{s}_1,cd{s}_2,\cdots ,cd{s}_k,\cdots ,cd{s}_{num}\right\}$,$cd{s}_k$ is coordinates of vertexes $DDS=\varnothing$, $SANC=\varnothing$, $k=0$ //$DDS$ candidate docking spots //$SANC$ set of cover set which associated with DDS While$O\ne \varnothing$ // O set of sensor nodes   $SN{C}_{temp}=\varnothing$, $U_{temp}=0$, $CD{S}_{temp}=0$   //find a stop point with max cover utility   While $k<len\left(CS\right)$    Call DMCU($cd{s}_k$) to get max coverage utility    $U_{max}\left(cd{s}_k\right)$, cover set $SN{C}_k$ at docking    point $cd{s}_k$ with charging direction $\overrightarrow{{\theta }_{s_k}}$    If $U_{max}\left(cd{s}_k\right)>U_{temp}$    $U_{temp}=U_{max}\left(cd{s}_k\right)$    $SN{C}_{temp}=SN{C}_k$    $CD{S}_{temp}=cd{s}_k$   End If   $k=k+1$  End While  $SANC=SANC{{\displaystyle \cup }}^{ }\left\{SN{C}_{temp}\right\}$  $DDS=DDS{{\displaystyle \cup }}^{ }\left\{CD{S}_{temp}\right\}$  $O=O-SN{C}_{temp}$  CS = CS $–$ {$CD{S}_{temp}\}$  k = 0 End While Output: set of docking points $DDS$ and set of charging cover sets $SANC$ at related charging directions

.

(2) The DMCU algorithm

The DMCU algorithm is used to find the charging direction with maximum coverage utility at each docking spot.

Take Figure 7 as an example to illustrate the process of DMCU algorithm: (1) The DCV rotates counter-clockwise with each different node as initial boundary; (2) Calculate the coverage utility of each orientation.

Six different coverage utility values can be obtained; the output is orientation with maximum coverage utility of a docking spot and the sensor nodes set that the combination of docking spot and this charging orientation can cover. Figure 7a–f show the set of nodes covered by the DCV at dock spot $s_k$ in each orientations ($\overrightarrow{{\theta }_{s_k}^1}~\overrightarrow{{\theta }_{s_k}^6}$), $SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^1}\right)~SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^6}\right)$ represent the corresponding nodes sets.

The procedure of DMCU algorithm is presented in

Table 3. The Procedure of the DMCU Algorithm.

DMCU algorithm: Find the max utility, cover set and charging orientation at$s_k$

Input: Sensor node set: $O=\left\{o_1,o_2,\cdots ,o_i,\cdots ,o_N\right\}$; Coordinates of certain docking spot $s_k$: $\left(c_x,c_y\right)$; Farthest charging distance DCV can reach: D; Charging angle of DCV: A $OCS=\varnothing$ // OCS sensors’ set possible covered by $s_k$ $i=0$ While$i<N$: //find sensors’ set OCS at docking spot $s_k$   Calculate Euclidean distance between sensor $o_i$   and docking spot$d_i$   If $d_i<D$:    $OCS=OCS{{\displaystyle \cup }}^{ }\left\{o_i\right\}$   End If   $i=i+1$ End While If$OCS\ne \varnothing$:   $L=len\left(OCS\right)$   Calculate the all possible charging angles:   $\phi =\left\{{\gamma }_1,{\gamma }_2,\cdots ,\gamma ,\cdots ,{\gamma }_L\right\}$   Sort sensors in set $OCS$ in ascending order   according to the value of angles.   $DCS=\varnothing ,k=0$   // calculate L directions’ cover sets   While $k<L$    $m=0$,$SN{C}_{tmp}=\varnothing$    While $\mathrm{m}<\mathrm{L}$     If ${\gamma }_k\le {\gamma }_m\le \left({\gamma }_k+A\right)\%360$:      $SN{C}_{tmp}=SN{C}_{tmp}{{\displaystyle \cup }}^{ }\left\{o_m\right\}$      End If     m = m + 1    End while    $DCS=DCS{{\displaystyle \cup }}^{ }\left\{SN{C}_{tmp}\right\}$    $k=k+1$   End while   $CU{S}_{tmp}=\varnothing ,SN{C}_{tmp}=\varnothing ,j=0$, ${\gamma }_{tmp}=0$   // find the cover set with max utility   While $j<len\left(DCS\right)$    Calculate cover utility $CUS\left[j\right]$ of $DCS\left[j\right]$     If $CUS\left[j\right]>CU{S}_{tmp}$     $CU{S}_{tmp}=CUS\left[j\right]$     $SN{C}_{temp}=DCS\left[j\right]$     ${\gamma }_{tmp}=$ $\phi \left[j\right]$     End If    j = j +1   End While   $U_{max}=CU{S}_{tmp}$, $SNC=SN{C}_{temp}$, $\gamma ={\gamma }_{tmp}$ End If Output: max utility $U_{max}$, covered set $SNC$, direction $\gamma$

.

OCS represents a coverage set of a candidate docking spot, the initial value is null. If the distance between the node and the candidate stop is not greater than D, then add the node into OCS. ${\gamma }_j$ in $\phi$ represents the angle formed by each node in $OCS$ at each candidate dock spot. $DC{S}_k$ represents a coverage set of candidate stop with kth charging direction, and the $CU{S}_{\mathrm{j}}$ indicates the corresponding coverage utility value. The DMCU algorithm finally outputs the maximum value $U_{s_k}^{max}$in $CU{S}_j$ and the set of covered nodes $SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$ covered at this docking spot $s_k$ with corresponding direction $\overrightarrow{{\theta }_{s_k}^l}$.

As shown in Figure 8, we randomly deploy 100 nodes in the 20 × 20 m² area and run the GMCU algorithm to determine specified docking spots and orientations with maximum coverage utility and minimum the number of docking spots.

4.2. Plan Moving Path and Charging Residence Time

In this section, we plan the DCV’s charging moving path to travel through all candidate docking spots chosen by the GMCU algorithm and the charging residence times at each docking spot to maintain the network’s continuous working and optimize the overall charging energy efficiency.

Firstly, we introduce the charging cycle $T$. As shown in Figure 9, the charging cycle $T$ consists of the DCV’s moving time, the charging residence time at each docking spot, and the rest time at the base station. The moving time is determined by the length of charging path. The charging residence time at each docking spot is determined by charging energy requirement of sensors covered by the DCV.

To achieve the goal of maintaining network perpetually, the charging process can be repeated periodically. Then this periodical charging cycle must meet two requirements:

(1)

The energy received by a sensor is greater or equal to the energy consumed in a charging cycle;

(2)

The residual energy value of a node will not be lower than $E_{min}$ during a charging cycle.

The cover sets charged by the DCV at dock spot $s_k$ on charging orientations $\overrightarrow{{\theta }_{s_k}^l}$: SNC$\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$=$\left\{o_1^{k_l},o_2^{k_l},\cdots ,o_m^{k_l}\right\}$. We can derive the minimal charging residence time $t_k$ according to the charging cover sets $SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$ at docking spot $s_k$:

$$t_k=\underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{\max }\left\{\frac{{\omega }_{o_i}}{P_{k,i}\left(s_k,o_i\right)}\right\}\times T$$

(22)

Here ${\omega }_{o_i}$ denotes the energy consumption of sensor node $o_i$, $P_{k,i}\left(s_k,o_i\right)$ denotes the receiving power of the sensor node $o_i$ when the DCV is at docking spot $s_k$.

We denote $c_k$ as the arrival time of the DCV at docking spot $k$ in the first cycle. Denote $d_{0,1}$ as the distance between the base station and the first docking spot, $d_{l,l+1}$ as the distance between $l\mathrm{th}$ and $\left(l+1\right) th$ docking spot.

$$c_k={\displaystyle \sum }_{l=0}^{k-1}\frac{d_{l,l+1}}{v}+{\displaystyle \sum }_{l=1}^{k-1}{t}_l$$

(23)

Here $t_l$ denotes the DCV’s charging time at docking spot $s_l$.

According to Figure 5, we can derive from Equation (22):

$$E_{max}-\underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{\min }\left\{e_{o_i}\left(c_k\right)\right\}\ge E_{max}-\underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{\min }\left\{e_{o_i}\left(T\right)\right\}$$

(24)

That is to say $e_{o_i}\left(m\times T+c_k\right)$ is the minimum value of $e_{o_i}\left(\tau \right)$. To have $e_{o_i}\left(\tau \right)\ge E_{min}$, it is sufficient to have:

$$e_{o_i}\left(m\times T+c_k\right)=e_{o_i}\left(m\times T\right)-c_k\times {\omega }_{o_i}\ge E_{min},o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)$$

(25)

while $\mathrm{m}\ge 1$:

$$\begin{gathered} e_{o_i}\left(m\times T+c_k\right)=e_{o_i}\left(m\times T\right)-c_k\times {\omega }_{o_i} \\ =e_{o_i}\left(\left(m-1\right)\times T+c_k+t_k\right)-\left\{m\times T-\left[\left(m-1\right)\times T+c_k+t_k\right]\right\}-c_k\times {\omega }_{o_i} \\ =e_{o_i}\left(\left(m-1\right)\times T+c_k+t_k\right)-\left(T-t_k\right)\times {\omega }_{o_i} \\ =E_{max}-\left(T-t_k\right)\times {\omega }_{o_i} \end{gathered}$$

(26)

Therefore, if Equation (27) holds, we have $e_{o_i}\ge E_{min}$, the sensor $s_k$ can working continuously.

$$E_{max}-\left(T-t_k\right)\times {\omega }_{o_i}\ge E_{min}$$

(27)

We can get the Charging Cycle $T$ when the two periodical charging requirements are met. Then we plan the DCV’s charging moving path.

When the DCV moves along the shortest Hamiltonian circle, we can achieve the maximum energy efficiency $\eta$.

We can proof this based on contradiction. Suppose the shortest travel route for the Hamilton Circle is $L=\left\{s_1⇢s_2⇢\cdots ⇢s_M\right\}$, and there exists a move route $L^{^}=\left\{s_3⇢s_2⇢\cdots ⇢s_M⇢s_1\right\}$. Assume that ${\eta }^{^}\ge \eta$ is established.

$${\eta }^{^}=\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$E_{DCV}^{^}$}\right.=\raisebox{1ex}{${{\displaystyle \sum }}_{k=1}^M{{\displaystyle \sum }}_{i=1}^N{P}_{k,i}\left(s_k,o_i\right)\times t_k^{^}$}\!\left/ \!\raisebox{-1ex}{$P_{out}\times {{\displaystyle \sum }}_{k=1}^M{t}_j+{\omega }_c\times L^{^}$}\right.$$

(28)

$$\eta =\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$E_{DCV}$}\right.=\raisebox{1ex}{${{\displaystyle \sum }}_{k=1}^M{{\displaystyle \sum }}_{i=1}^N{P}_{k,i}\left(s_k,o_i\right)\times t_k$}\!\left/ \!\raisebox{-1ex}{$P_{out}\times {{\displaystyle \sum }}_{k=1}^M{t}_k+{\omega }_c\times L$}\right.$$

(29)

The energy received by the node in this cycle is equal to the energy consumed. The numerator of Equations (28) and (29) are equal. Because $L\le L^{^}$,${\eta }^{^}\le \eta$, thus leading to a contradiction. Therefore, we can dispatch the DCV moving along the shortest Hamiltonian circle to achieve the maximum energy efficiency.

We redefine Equation (11) as Equation (30)

$$\begin{gathered} \begin{array}{cc}max& \eta \end{array} \\ \begin{array}{cc}s.t.& t_k=\underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{\max }\left\{\frac{{\omega }_{o_i}}{P_{k,i}\left(s_k,o_i\right)}\right\}\times T\end{array} \\ {E}_{max}-\left(T-t_k\right)\times {\omega }_{o_i}\ge E_{min} \\ T=T_{res}+T_{TSP}+{\displaystyle \sum }_{k=1}^M{t}_k \\ {P}_{out}{\displaystyle \sum }_{k=1}^M{t}_k+{\omega }_c\times L_c\le C_{max} \end{gathered}$$

(30)

Here $\eta$ denotes Energy Charging Efficiency, ${\omega }_{o_i}$ denotes the energy consumption of sensor node $o_i$, $P_{k,i}\left(s_k,o_i\right)$ denotes the receiving power of the sensor node $o_i$ when the DCV is at docking spot $s_k$, $t_k$ denotes the DCV’s charging time at docking spot $s_k$, $T_{res}$ denotes rest time of the DCV, $T_{TSP}$. denotes the moving time of the DCV, the sum of $t_k$ denotes the total charging time of the DCV.

Finally, we get the charging residence time at each docking spot and energy efficiency by solving the planning problem.

5. Analysis of the DCV’s Service Capability

We use only one DCV with energy capacity of $E_{max}$ to maintain WRSN perpetually. Therefore, the network size and area size are limited. This section will specifically analyze the service capability of the DCV.

Assume that the number of stops is $M$, the charging time of each stop is $t_k$, the distance between adjacent stops is $d_{k-1,k}$, the length of the return route is $d_{back}$. Two constraints must be satisfied for each round of charging: (1) the energy received by each node is not less than the energy consumed, formulated as Equation (31); and (2) the DCV should not run out of energy in a round, formulated as Equation (32).

$$\underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{min}\left\{P_{k,i}\left(s_k,o_i\right)\right\}\times t_k\ge \underset{o_i\in SNC\left(s_k,\overrightarrow{{\theta }_{s_k}^l}\right)}{max}\left\{{\omega }_{o_i}\right\}\times \left(\left(t_1+\cdots +t_M\right)+\frac{d_{1,2}+\cdots +d_{M-1,M}+d_{back}}{v}\right),0\le k\le M$$

(31)

$$P_{out}\times \left(t_1+\cdots +t_k+\cdots +t_M\right)+\left(d_{1,2}+d_{2,3}+\cdots +d_{M-1,M}+d_{back}\right)\times {\omega }_c\le C_{max}$$

(32)

Here,$P_{out}$ is the charger’s transmission power, $v$ denotes the moving speed of the DCV,${\omega }_c$ denotes DCV’s consumption power of moving, $C_{max}$ denotes maximum energy capacity of the DCV.

We first analyze the maximum size of area. Assuming that there are only two nodes in the network and they are on the diagonal line of the network, the consuming power is the minimum ${\omega }_{min}$, the DCV stops at the nodes respectively, and the receiving power of the nodes is both $P_{out}$. Then the number of stops is two ($M=2$), the shortest distance of moving route is $2\sqrt{2}\ast l$, $l$ denotes length of the network ,then we can get Equation (33)

$$l_{max}=\frac{C_{max}\times \left(P_{out}-2\times {\omega }_{min}\right)}{2\sqrt{2}\times \left(\frac{P_{out}\times {\omega }_{min}}{v}+{\omega }_c\times \left(P_{out}-2\times {\omega }_{min}\right)\right)}$$

(33)

Secondly, we analyze the minimum size of area. Assume that the nodes are evenly distributed in the network, the consuming power is the maximum ${\omega }_{max}$, the DCV stops at the nodes respectively, and the receiving power is all the minimum $P_{min}$. Then the number of stops is formulated as Equation (34).

$${\lceil \frac{l}{\raisebox{1ex}{$\sqrt{2}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\times D}\rceil }^2$$

(34)

The longest distance of move route is formulated as Equation (35).

$$2\times \left(M-1\right)\times \sqrt{2}\times D$$

(35)

We bring Equations (34) and (35) into Equations (31) and (32) to get Equations (36).

$$\begin{gathered} M=\frac{-b\pm \sqrt{b^2-4\times a\times c}}{2\times a} \\ \{\begin{array}{c}a=2\sqrt{2}\times {\omega }_{max}\times D\times P_{min}\\ \begin{array}{c}b=2\sqrt{2}\times D\times {\omega }_c\times v\times \left(P_{min}-{\omega }_{max}\right)\\ -2\sqrt{2}\times {\omega }_{max}\times D\times P_{min}\end{array}\\ c=v\times \left(P_{min}-{\omega }_{max}\right)\times \left(C_{max}+2\sqrt{2}\times D\times {\omega }_c\right)\end{array} \end{gathered}$$

(36)

Therefore, the minimum length of area is $L_{min}$, formulated as Equation (37).

$$L_{min}=\lfloor \sqrt{d^2\times M}\rfloor$$

(37)

When the network area is the smallest, assuming that the charger can charge $CN$ nodes simultaneously at most, the number of nodes can reach the maximum. Then the maximum number of nodes is $CNS$, formulated as Equation (38).

$$CNS=M\times CN$$

(38)

In summary, when the size of the area is between $L_{min}$ and $L_{max}$ and the size of network is less than $CNS$, the proposed charging model and approximate algorithm can satisfy the two constraints: 1) the energy received by each node is not less than the energy consumed; and 2) the DCV should not run out of energy in a round.

6. Simulation Experiments

In this section, we describe comprehensive simulation experiments to investigate the algorithms’ performance under different influence factors, such as grid size, area size, and network size. In the existing literature, there are no related works that study mobile directional charging problem in WRSN. Therefore, we conducted simulations experiments and compared charging efficiency with mobile omnidirectional charging models [14]. The simulation experiments were performed on a 64-bit Windows 10 system; the programming languages were C++ and Python. The algorithms were realized in the C++ language. Additionally, the visualization of deployment results was realized in Python. In the simulation experiments, we set up the parameters of the DCV and rechargeable sensor network, as in

Table 4. Parameter Setting.

Parameter	Value
$E_{max}$	10,000 J
$P_{ou}$	3 $\mathrm{J}/\mathrm{s}$
${\omega }_c$	0.3$\mathrm{J}/\mathrm{m}$
$D$	3$\mathrm{m}$
$v$	0.5$\mathrm{m}/\mathrm{s}$
$R_{o_i}$	randomly generated in References [1,10] b/s
$e^s$	0.01$\mathrm{mJ}/\mathrm{b}$
$e^t$	0.06$\mathrm{mJ}/\mathrm{b}$
$e^r$	0.05$\mathrm{mJ}/\mathrm{b}$
$\mathsf{\alpha },\mathsf{\beta }$	10
The number of sensor nodes	20, 40, 60, 80, 100, 120, 140, 160, 180,200
The size of area	15 × 15 m2, 20 × 20 m2, 25 × 25 m2, 30 × 30 m2, 35 × 35 m2,

.

6.1. Comparison Experiments on Different Grid Size

In our approach, we discretized the continuous 2D plane with gridding. We investigated how grid size affects the algorithm’s performance. We randomly deployed 20, 40 and 60 nodes in the 15 × 15 m² area, changed the grid size, and explored the variation of energy efficiency and docking spots number. Figure 10 shows that with the decrease of grid size, the energy efficiency of the DCV increase. Additionally, a stable grid size tends to be 0.2 m. Figure 11 shows that with the decrease of grid size, the number of specified docking spots decreases. Additionally, it tends to be stable when grid size is .2 m.

6.2. Comparison Experiments on Different Network Size And Area Size

We investigated how network size affects the algorithm’s performance. We randomly deployed 20, 40, 60, 80, 100, 120, 140, 160, 180, 200 nodes in 15 × 15 m², 20 × 20 m², 25 × 25 m², 30 × 30 m², 35 × 35 m² plane areas respectively, and explored the variation in the energy efficiency of DCV. It can be seen in Figure 12 that as the number of nodes increases, the energy efficiency increases; because the number of nodes increases in the same area, the number of nodes can be covered by the DCV increases, so more energy is received by the nodes, and the energy efficiency is improved. As shown in Figure 13, when the number of nodes remains unchanged and the area becomes larger, the energy efficiency decreases. This is because as the area becomes larger, the distance between nodes becomes larger, the moving path of the DCV becomes longer, and the energy consumed on moving increases, which leads to the decrease of the energy efficiency of the DCV.

6.3. Comparison Experiments on Mobile Omnidirectional and Directional Charging

In the existing literature, there are no related works that use directional charging model for mobile charging in WRSN. Therefore, we conducted simulation experiments and compared charging efficiency with mobile omnidirectional charging [14]. We randomly deployed 20, 40, 60, 80, 100, 120, 140, 160, 180 and 200 nodes in 15 × 15 m², 20 × 20 m² and 25 × 25 m² areas. In experiments, we used DCV and omnidirectional charging vehicle respectively to charge the network according to the algorithms proposed in this paper, and compare their energy efficiency. Figure 14, Figure 15 and Figure 16 show the variation of energy efficiency in different area size and network size. The experiments show that the energy efficiency of DCV is higher than that of omnidirectional charging vehicle in the network with sparse nodes. As the node density increases, the energy efficiency of DCV and omnidirectional charging vehicle will gradually converge. Hence our mobile directional charging algorithm is more suitable in a network with sparse nodes compared with mobile omnidirectional charging.

7. Conclusions

In this paper, we investigated the DCV’s charging efficiency optimization problem in RWSN while maintaining sensor network working continuously. We proved that the problem is NP-hard. Firstly, we proposed the coverage utility of directional charging. Then we transformed the finding of candidate docking spots and their charging directions on the 2D plane into a two-objective optimization problem of minimizing number of stop points and maximizing charging coverage utility. Additionally, we proposed a greedy approximation algorithm to solve the two-objective optimization problem and find the set of candidate stop points of the DCV. Finally, we planned the DCV’s charging moving path to travel through all candidate docking spots to maintain the network’s continuous working and optimize the overall energy charging efficiency. We theoretically analyzeed the DCV’s charging service capability, and performed the comprehensive simulation experiments. The simulation experiment results show that energy charging efficiency is higher than omnidirectional charging model in the sparse networks.

As stated in the literature [40], WPT has several limitations when applied to a WSN. First, it has very low energy transfer efficiency as distance increases. Second, it is sensitive to obstruction between an energy source and a receiver. Therefore, this technology is only suitable in the ultra-low-power WSN scenario. In future work, we will further investigate more practical energy replenishment optimization problem in WSN, in which we can use a hybrid energy replenishing scheme, such as wireless charging for ultra-low-power sensor nodes and solar energy harvesting for high-power sensor nodes in the network.