1 Introduction

Recently, wireless sensor network (WSN) is widely employed in surveillance [1] and maintenance system [2], message transportation [3] and so on. However, two major restrictions hinder further applications of WSN. First, the energy capacity of sensor nodes is limited. Second, the energy consumption rates of sensor nodes are different, which depend on the number of the events monitored around them. To prolong the lifetime of WSN, mobile chargers (MC) were introduced into WSN to charge sensor nodes and wireless rechargeable sensor network (WRSN) [4] came into being.

Benefited from the development of wireless power transportation (WPT) technology [5], MC can use WPT to charge sensor nodes wirelessly. There has been much effort devoted to optimize the charging performance of WRSN, such as minimizing charging time, reducing dead number of sensor nodes, etc [6,7,8].

Depending on how many sensor nodes can be charged simultaneously, the charging mode can be divided into two categories : one-to-one charging model [9] and one-to-many charging model [10]. Wu et al. and Ye and Liang [11,12,13] studied the MC scheduling with one-to-one charging model. One-to-one charging schedule problem is usually formulated into the classical or variant Travelling Salesman Problem (TSP) [14]. In sparse sensor network, the one-to-one charging method can ensure the survival rate of nodes. However, for dense sensor network, one-to-one charing model is not efficient. In the contrary, MC with one-to-many charging model can charge multiple sensor nodes within the charging radius simultaneously. Liu et al. [7] used one-to-many charging model to optimize the survival rate of sensor nodes and the effectiveness of energy usage to improve the lifetime of WRSN. Priyadarshani et al. [15] took spatial feature, remaining energy and the number of request nodes into account to improve reliability of WRSN.

The existing studies typically assume that the charging power of MC is fixed. In real scenarios, current MC has the ability to adjust power [16,17,18], while existing algorithms do not take advantage of it.

To improve the energy utilization rate of MC, in this paper, we take MC with adjustable power into consideration and formulate power level aware charging schedule (PACS) as an optimization problem. We comprehensively consider the charging position, charging time and charging power of MC, that are not considered by the existing research. When the charger receives several charging requests, we need to jointly optimize its charging place and power level to maximize charging utility. At the same time, it should be ensured that the charger has enough power to return back to Base Station (BS).

In the process of solving the PACS problem, we face the following challenges:

  • First, charging utility is nonlinear about the distance between sensor node and charger. Meanwhile, different charging power also affects charging utility, which makes PACS complicated.

  • Second, MC can be scheduled to move in the continuous network area and the PACS problem has infinite solution space. Thus it is difficult to find out several reasonable charging positions.

  • Third, even if the charging positions are determined, how to select suitable charging time to maximize charging utility and reduce the number of dead nodes is also a hard problem.

To tackle the aforementioned challenges, we discretize the network area and formulate the PACS problem as a monotone submodular optimization problemm, which is proved as NP-hard. Then we design a power level aware charging schedule algorithm to maximize the charging utility. In summary, the main contributions of this paper are as follows:

  • The existing works assume MC with fixed power, which is unreasonable in real scenarios. We propose the power level aware charging schedule (PACS) problem and formalize it.

  • We prove that the PACS problem is a monotone submodular optimization problem, which is proved as NP-hard. Thus, we present an area discretization method and propose a greedy algorithm to solve it.

  • Finally, we conduct experiments to prove that our scheme can improve the energy utility rate of MC than other typical algorithms and guarantee a high survival rate about sensor nodes.

The rest of this paper is organized as follows: we first review the related work in Section II. Section III introduces the formalization process of PACS. Next, we propose a power level aware charging schedule algorithm in Section IV. Finally, we conduct extensive experiments and provide experimental results and conclusions in Section V and Section VI respectively.

2 Related work

To prolong the lifetime of WRSN without losing flexibility, researches about different chargers and scheduling method have been studied many years. At present, most of existing technologies adopt wireless charging device equipped with WPT because of its convenient, maneuvering, easy to expand in performance and so on. In this section, we introduce these works from three aspects: charging model, charging way, schedule method.

2.1 One-to-one and one-to-many charging model

We can divide mobile chargers into two types according to the number of sensor nodes that can be charged simultaneously. There are two wireless charging models: one-to-one charging and one-to-many charging.

In one-to-one charging model, the charger can only charge one sensor node at the same time, Tomar et al. [19] proposed an effective path planning algorithm to maximize charging utility according to fuzzy logic. In [20], the network was divided into several regions according to the proposed partitioning algorithm based on the minimum spanning tree to minimize the energy consumption. However one-to-one charging model is inefficient to charge multiple sensor nodes. To reduce the number of dead nodes and improve charging efficiency, one-to-many charging has been put forward [10].

In one-to-many charging model, charger can charge a set of sensor nodes simultaneously within its charging radius. Rao et al. [21] scheduled charger to maximize charging utility while satisfying deadline constraint. Xu et al. [6] considered simultaneous scheduling of multiple chargers and propose a novel longest delay minimization algorithm. However, these studies did not consider that the charging power can be adjusted to save energy.

2.2 Full and partial charging way

According to how much energy the charger releases, there are two charging ways: full charging and partial charging.

In full charging, sensor nodes are fully charged every time after they issue charging requests. Lin et al. [22] took temporal and spatital feature into consideration and designed a global optimization algorithm. In addition, Chen et al. [23] combined charging node selection with dispatch path feasibility, which took into account the moving cost about different locations and energy-driven charging priority to ensure the charging efficiency. Full charging can guarantee the long-term reliability of the charged node. However, long charging time may cause other nodes to die without being charged.

In order to improve survival rate of sensor nodes, partial charging is proposed. In partial charging, sensor node can be charged multiple times to reduce charging delay. More flexible energy allocation of MC can also improve survival rate. However, unreasonable charging schedule may cause low charging utility and spend too much energy on travel. Thus, how to determine the charging time becomes very important. Xu et al. [24] improved the lifetime of nodes by shortening the moving distance of the charger. A Multi-node Time-Space Partial Charging algorithm is proposed in [7] to minimize the number of dead nodes and maximize energy efficiency.

2.3 Static schedule and non-static schedule

In WRSN, there are two schedule methods: static schedule and non-static schedule.

In terms of static schedule, the chargers are placed in some charging positions calculated in advance according to the optimization goal. Li et al. [25] formulated the problem with a specific stay-move behavior pattern and deploy charger to minimize the charging service budget. In [26], Wang et al. took obstacles into consideration and use discretization method to solve it.

Non-static schedule means dynamically determining charging strategies according to the status of sensor nodes. Soni and Shrivastava [27] used reinforcement learning technique to optimize the routing energy loss and the energy consumption of mobile WSN. To respect the diversity of needed energy, Ye and Liang [13] advocated MC scheduling driven by collaborative tasks. Lin et al. [28] considered the temporal and spatial collaborative charging with multiple charger scheduling to prolong the lifetime of sensor nodes.

All the above works assume that the power of charger is fixed, which is inconsistent with the fact. However, adjustable power has been applied to many fields. Estepa et al. [29] used IoT devices with adjustable transmit power to compose WSN to different power to transmit different packages in order to reduce energy consumption. Dai et al. [30] proposed a charger deployment scheme for wireless chargers with electromagnetic radiation safety concern according to different power. Li et al. [31] took both the charging time periods and the adjustable power into account to prolong the wireless static charger’s working time. In this paper, we propose the power level aware charging schedule (PACS) problem and take the adjustable power into consideration to improve the energy utilization of MC.

3 Problem modeling

In this section, first we introduce our network and charging model, charging utility model and then formulate the problem about PACS. The symbols and definitions in our paper are listed in Table 1.

Table 1 Symbols and Definitions
Full size table

3.1 Network and charging model

As shown in Fig. 1, there are N static sensor nodes \(O=\{o_1,...,o_n,...,o_N \}\) (\(1\le n\le N\)) distributed in a 2D plane \(\Omega\). We also use \(o_n\) to denote the location of the sensor node in \(\Omega\). MC is equipped with multiple levels of power \(P=\{P_1,...,P_i,...,P_l\}\) (\(1\le i\le l\)). When some sensor nodes issue charging requests, MC will start from base station to charge these nodes and return back before it exhausts energy.

Fig. 1
figure 1

The scenario of mobile charging

Full size image

In this paper, one-to-many charging model is adopted and we specifically use the WISP-reader charging model [32]. When MC moves to the charging position \(p_k\), the receving power \(P_{k,i}^n(d(o_n,p_k),P_i)\) of sensor node \(o_n\) can be calculated as below:

$$\begin{aligned} P_{k,i}^n(d(o_n,p_k),P_i) = \left\{ \begin{array}{cc} \frac{\alpha }{(\beta +d(o_n,p_k) )^2 } \times P_i &{} {d(o_n,p_k)\leqslant R_i}\\ 0 &{} {d(o_n,p_k)>R_i}\\ \end{array} \right. \end{aligned}$$
(1)

where \(d(o_n,p_k)\) denotes the distance between the sensor node \(o_n\) and the charging position \(p_k\). \(R_i\) is the maximum charging radius, which is related to the i-th level of source power \(P_i\) of MC [33]. \(\alpha\) and \(\beta\) are two predetermined constants depending on surrounding environment and hardware settings of MC.

3.2 Charging utility model

To judge the efficiency of charging, we present the charging utility \(U_k(Q_k,T_k,P_i)\) of charging position \(p_k\) with source power \(P_i\) as:

$$\begin{aligned} U_k(Q_k,T_k,P_i)=\frac{Q_k}{T_k\times P_i+r_k\times c} \end{aligned}$$
(2)

where \(Q_k\) denotes the total received energy. \(T_k\) is the charging time after MC moves to the k-th charging position \(p_k\). \(r_k\) and c represent the travel time and the moving cost per unit time respectively.

Because of one-to-many charging model, all the sensor nodes within the charging radius \(R_i\) can be charged simultaneously. In practice, the charging power \(P_{k,i}^n\) of fully charged node \(o_n\) typically has an upper bound, which is equal to the energy consumption rate \(C_n\) of sensor node. Moreover, to improve the survival rate of sensor nodes, we assign the charging weight w to dead node (\(E_n\)=0) to ensure that it can be charged as early as possible. Thus the received energy \(q_n\) of sensor node \(o_n\) is:

$$\begin{aligned} q_n = \left\{ \begin{array}{rcl} w \times P_{k,i}^n \times T_k &{} &{} {E_n=0}\\ P_{k,i}^n\times T_k &{} &{} {0<E_n<E_{max}^n}\\ C_n\times T_k &{} &{} {E_n=E_{max}^n}\\ \end{array} \right. \end{aligned}$$
(3)

where \(P_{k,i}^n\) and \(C_n\) are the receiving power and consuming rate of the sensor node \(o_n\) respectively. \(T_k\) is the charging time at charging position \(p_k\). w is the charging weight when the sensor node \(o_n\) is dead.

Then we can get the total received energy \(Q_k\) of nodes within charging radius \(R_i\) at the charging position \(p_k\) as follows:

$$\begin{aligned} Q_k=\sum _{d(o_n,p_k)<R_i} q_n \end{aligned}$$
(4)

where \(d(o_n,p_k)<R_i\) denotes that sensor node \(o_n\) is located within the i-th level of charging radius \(R_i\).

3.3 Problem formulation

Our goal is to maximize the energy utility of charging while MC cannot run out of energy during the charging periods. When MC receives charging requests from sensor nodes, it should select optimal charging positions and power levels according to the optimization goal. Thus the power level aware charging schedule (PACS) problem can be formulated as:

$$\begin{aligned} max\sum _{k = 1}^{K}U_k(Q_k,T_k,P_i) \end{aligned}$$
(5)

s.t.

$$\begin{aligned} \sum _{k = 1}^{K}( T_k\times P_i+(r_k + r_{BS}) \times c) \leqslant E_{max}^c \end{aligned}$$
(6)
$$\begin{aligned} \forall Q_k< T_k \times P_i \;,\; \forall p_k \in \Omega \end{aligned}$$
(7)

where \(T_k\) denotes the charging time at position \(p_k\). \(P_i\) is the i-th level of charging power. \(r_k + r_{BS}\) is the travel time from the current position to \(p_k\) and then from \(p_k\) to BS. c denotes the moving cost per unit time. Equation (6) ensures that MC can return back to BS at any point. And the received energy \(Q_k\) should be less than the energy released by MC according to Eq. (7).

Fig. 2
figure 2

The solution workflow

Full size image

The theorem below shows the hardness of PACS.

Theorem 1

The PACS problem is NP-hard.

Proof of Theorem 1 We sketch the proof here due to space limit. Consider the special case where the charging radius \(R_i\) and the charging time \(T_k\) are fixed. Moreover, we suppose that the receiving power of node is constant. Then each node can be seen as a point, and the charging area can be seen as a disk. Therefore, the PACS problem can be transformed to the problem of identifying a tour of minimum travel cost to cover most points, which is exactly the geometric covering salesman problem [34]. Meanwhile, it is proved to be NP-hard. Therefore, PACS is also NP-hard.

4 Solution

In this section, we propose a power level aware charging schedule algorithm (PACSA) to maximize charging utility. The workflow of PACSA is shown in Fig. 2. First we present an area discretization method to reduce solution space. Then we discretize the charging power with guaranteed approximation ratio and use a greedy algorithm to solve PACS.

4.1 Network area discretization

Because network area \(\Omega\) is a continuous area, which implies that the number of the charging positions is infinite. Thus, we propose an area discretization method to reduce the solution space from infinite to finite. As shown in Fig. 3, we discretize network area into several grids with side of length \(\delta\) and consider the intersections as the charging positions. Thus we obtain \(\varGamma =\left\lceil \frac{\left|\Omega \right|}{\delta ^2} \right\rceil\) grids and \(K=(\varGamma -1)^2\) charging positions. The charging positions is denoted by \(S=\{p_1,...,p_k,...,p_K\}\).

4.2 Charging power discretization

To reduce the computation overhead, we use a piecewise constant function \(\widetilde{P_{k,i}^n}(l_j,P_i)\) to discretize charging power as:

$$\begin{aligned} \widetilde{P_{k,i}^n}(l_j,P_i)=\left\{ \begin{array}{rcl} P_{k,i}^n(l_1,P_i) &{} &{} {d=l_0} \\ P_{k,i}^n(l_j,P_i) &{} &{} {l_{j-1}<d \leqslant l_j } \\ 0 &{} &{} {d>R_i} \end{array} \right. \end{aligned}$$
(8)

where \(l_0\) = 0, \(j=\){1, ..., J} and \(l_J\) = \(R_i\). \(R_i\) is the charging radius with the i-th level of charing power.

Fig. 3
figure 3

Network area and charging power discretization

Full size image

Take Fig. 3 as an example, the charging radius \(R_i\) is divided into three segments \(l_1\), \(l_2\), \(l_3\). The received power of sensor nodes \(o_3\) located between \(l_1\) and \(l_2\) can be approximated to \(\widetilde{P_{k,i}^n}(l_2,P_i)\). In the same way, each node located between \(l_j\) and \(l_{j+1}\) has the same constant approximation power.

To bound the approximation error of piecewise constant approximation, we propose a constant threshold \(\varepsilon\) and offer the sufficient condition to ensure that the approximation error is less than \(\varepsilon\).

Theorem 2

Setting \(l_0\) = 0, \(l_J\) = \(R_i\) and \(l_j = \beta ((1+\varepsilon )^{j/2}-1)\) (\(j = 1,...,J-1\)), the approximation error is subject to:

$$\begin{aligned} 1\leqslant \frac{P_{k,i}^n(d,P_i)}{\widetilde{P_{k,i}^n}(d,P_i)} \leqslant 1+\varepsilon \end{aligned}$$
(9)

Proof of Theorem 2 The approximation error is proportional to the distance between the node and the charger. Thus we have \(l_{j-1}<d \leqslant l_j\), the maximum error can be calculated by \(\frac{P_{k,i}^n(l_j,P_i)}{\widetilde{P_{k,i}^n}(l_{j-1},P_i)}=1+\varepsilon\).

4.3 Problem reformalization

After network area discretization, the charging positions are discretized from infinite to finite. Meanwhile we discretize the charging power with guaranteed approximation ratio and reformulate the PACS problem as below:

$$\begin{aligned} max\sum _{k = 1}^{K}U_k(Q_k,T_k,P_i) \end{aligned}$$
(10)

s.t.

$$\begin{aligned} \sum _{k= 1}^{K}(T_k\times P_i+(r_k + r_{BS})\times c)\leqslant E_{max}^c \end{aligned}$$
(11)
$$\begin{aligned} \forall Q_k< T_k \times P_i \;,\; \forall p_k \in S \end{aligned}$$
(12)
$$\begin{aligned} Q_k=\sum _{d(o_n,p_k)<R_i} q_n \end{aligned}$$
(13)

where,

$$\begin{aligned} q_n = \left\{ \begin{array}{rcl} w \times \widetilde{P_{k,i}^n}(l_j,P_i) \times T_k &{} &{} {E_n=0}\\ \widetilde{P_{k,i}^n}(l_j,P_i)\times tT_k &{} &{} {0<E_n<E_{max}^n}\\ C_n\times T_k &{} &{} {E_n=E_{max}^n}\\ \end{array} \right. \end{aligned}$$
(14)

We utilize charging power discretization and introduce Eq. (8) to further simplify the calculation and reformulate the problem. At the same time, we introduce the charging weights \(\omega\) for the dead sensor nodes and obtain Eq. (14). \(q_n\) is the receiving energy of sensor node \(o_n\) within the charging redius.

4.4 Optimization problem analysis

After utilizing both network area and charging power discretization, we found that the object function of PACS problem is a monotone submodular function about charging time.

Theorem 3

\(\sum _{k = 1}^{K}U_k(Q_k,T_k,P_i)\) is monotonously nondecreasing submodular function for \(T_k\).

Proof of Theorem 3 First, note that the set function \(\sum _{k = 1}^{K}U_k(Q_k,T_k,P_i)\) is the sum of a number of \(U_k(Q_k,T_k,P_i)\). Given two sets of selected charging positions \(\chi '\), \(\chi ''\) and \(\chi ' \subset \chi ''\), we have \(\sum _{k = 1}^{\chi ''}U_k(Q_k,T_k,P_i)>\sum _{k = 1}^{\chi '}U_k(Q_k,T_k,P_i)>0\). Thus the objective function is nonnegative and monotone.

To prove the submodularity, we should prove the property of diminishing marginal utility in our formulated objective function [35]. We only need to compare the marginal utility \(\Delta U_\mu ^{''}(Q_\mu ,T_\mu ,P_i)=\sum _{k = 1}^{\chi ''\bigcap s_{\mu }}U_k(Q_k,T_k,P_i) - \sum _{k = 1}^{\chi ''}U_k(Q_k,T_k,P_i)\) and \(\Delta U_\mu ^{'}(Q_\mu ,T_\mu ,P_i)=\sum _{k = 1}^{\chi '\bigcap s_{\mu }}U_k(Q_k,T_k,P_i) - \sum _{j = 1}^{\chi '}U_k(Q_k,T_k,P_i)\).

We assume that MC finishes charging at \(p_{\chi '}\) after time T and finishes charging at \(p_{\chi ''}\) after time \(T+\Delta T\). There are two cases according to the selection of the charging position \(p_\mu\):

  1. 1.

    When MC moves to \(p_\mu\), there is no sensor node that has been charged in \(\chi ''-\chi '\). After charging time \(T_\mu\), we have \(\Delta U_\mu ^{''}(Q_\mu ,T_\mu ,P_i) = \Delta U_\mu ^{'}(Q_\mu ,T_\mu ,P_i)\).

  2. 2.

    When MC moves to \(p_\mu\), there are sensor nodes that has been charged in \(\chi ''-\chi '\). There is such a situation that the node within charging radius \(R_l\) has been fully charged during the charging time \(T_\mu\). When the node is fully charged, the max power it received is equal to its energy consumption rate \(C_n\) according to Eqs. (3) and (4), which lead to \(Q_\mu ^{''}<Q_\mu ^{'}\) and \(\Delta U_\mu ^{''}(Q_\mu ,T_\mu ,P_i) < \Delta U_\mu ^{'}(Q_\mu ,T_\mu ,P_i)\).

In summary, the set function \(\sum _{k = 1}^{K}U_k(Q_k,T_k,P_i)\) is monotonously nondecreasing submodular.

4.5 Approximate algorithm

As demonstrated in the previous section, the PACS problem can be formulated as a monotone submodular optimization problem, which allows a greedy algorithm to achieve a good approximation [36]. The detailed algorithm of PACSA is as follows:

After network area and charging power discretization, the number of charging positions becomes finite. And the charging power is approximated to be constant in each segment. Consequently, we only need to consider the coverage relationship between MC and sensor nodes, which depends on different charging radii. Algorithm 1 shows how to get coverage sets of nodes \(\varPsi\). For example, suppose there are three charging radii \(R_0<R_1<R_2\). When the distance \(d(o_n,p_k)<R_0\), we put \(o_n\) into the \(set_{k,0}\{ o_n\}\), \(set_{k,1}\{ o_n\}\), \(set_{k,2}\{ o_n\}\). When the distance \(R_0<d(o_n,p_k)<R_1\), we put \(o_n\) into the \(set_{k,1}\{ o_n\}\) and \(set_{k,2}\{ o_n\}\). When the distance \(R_1<d(o_n,p_k)<R_2\), we put \(o_n\) into \(set_{k,2}\{ o_n\}\). Finally, we can obtain the coverage sets \(\varPsi =\{set_{1,0},set_{1,1},set_{1,2},...,set_{k,1},set_{k,2} \}\).

figure g

Algorithm 2 describes the process of strategy selection for charging by implying a greedy algorithm. When MC receives the charging requests \(Q=\{req_1,req_2,...,req_m\}\) \((m\le N)\), it can filter out the request coverage sets \(\varPsi _R\) that contain charging request nodes. According to Eq. (14), the charging power has upper bound when the node is fully charged, which leads to the charging utility decrease. Thus the charging time \(T_k\) is based on the fastest fully charged node in the request coverage set. According to different power levels, we can calculate the corresponding charging utility. Moreover, we consider the moving cost on the travel and \(CanBack(p_k)=1\) denotes that MC has the ability to return back to BS after charging. MC selects the charging strategy with the largest charging utility to charge according to greedy mind.

figure h

4.6 Computational complexity

In this section, we analysis the computational complexity of our algorithm.

PACSA is composed of two algorithms: extracting coverage sets and calculating charging position and source power. Because the network (denoted by \(\Omega\)) is continuous, the number of the charging position is infinite. We propose an area discretization method to reduce the solution space. As shown in Fig. 3, we divide the area into \(\varGamma =\left\lceil \frac{\left|\Omega \right|}{\delta ^2} \right\rceil\) grids and get \(K=(\varGamma -1)^2\) charging positions, where \(\delta\) is the side length of each grid. Then we traverse all the charging positions and sensor nodes to calculate the coverage sets. The number of power levels depend on the hardware setting of MC, which is a constant. Thus the time complexity of the first algorithm of calculating coverage sets is \(O((\left\lceil \frac{\left|\Omega \right|}{\delta ^2} \right\rceil - 1)^2 \times N)\). When MC receives m charging requests \(Q=\{req_1,req_2,...,req_m\}\) \((m\le N)\). Then we will traverse all the charging requests to filter the coverage sets and the time complexity is \(O(K \times m)\). In the worst case, the number of charging requests m is close to the number of sensor nodes N. Thus, the total time complexity taken by the proposed scheme is \(O((\left\lceil \frac{\left|\Omega \right|}{\delta ^2} \right\rceil - 1)^2 \times N + K \times m)\) and the worst time complexity is \(O((\left\lceil \frac{\left|\Omega \right|}{\delta ^2} \right\rceil - 1)^2 \times N + K \times N)\).

5 Simulation experiments

In this section, we conduct experiments to evaluate the performance of PACSA. We compare PACSA with different schedule schemes by analyzing the impact of different parameters.

5.1 Evaluation setup

In our simulation, we use the ONE simulator [37] to conduct experiments on a system enabled with 16 GB RAM and AMD Ryzen 7 4800U processor. The ONE simulator is a typical simulation platform specifically for evaluating path planning algorithm. Meanwhile we add the charging model in [32] to simulate the charging process of MC. In our paper, we consider the WRSN consisting of 50 sensor nodes that are randomly deployed in a 200m \(\times\) 200m square. For the location of sensor nodes, we consider two types of distribution: uniform distribution and nonuniform distribution. The energy capacity of MC and sensor node are initialized \(E_{max}^c = 2000KJ\) and \(E_{max}^n = 50KJ\) respectively. MC has three power levels \(P_l=\{ 50,70,90\}\). The charging request threshold \(E_d=30KJ\). We set \(\alpha =100\), \(\beta =50\) in Eq (1). Moreover, the moving speed v of MC is 5m/s. Energy consumption rate of sensor node is random value in \(\left[ 0.1,0.2\right] KJ/s\).

5.2 Baseline setup

To evaluate the performance of PACSA, we choose the classical mTS [28] algorithm and state-of-the-art CSGP [15] algorithm for comparison. mTS considers the combination of the temporal requirement and the spatial feature of charging requests to make charging decisions. CSGP uses one-to-many charging model. It take spatial feature, remaining energy and the number of request nodes into consideration to make charging decisions. Then it proposed partial charging scheme to calculate each halting point. As there is no mobile charging schedule algorithm concerning the adjustable power at present, we also develop two comparison algorithms named Adjustable Power without Dead Priority (APDP) and Simple Greedy with Constant Power (SGCP). Different from PACSA, APDP only chooses the charging strategy with the highest charging utility in each iteration without considering the number of dead nodes. In SGCP, once the MC reaches the charging position, it releases energy with a fixed charging power. It’s way to calculate the charging utility and choose the charging strategy is same as PACSA. For each of the above algorithms, we performed it in two environments: (1) uniform environment: sensor nodes are distributed uniformly, and (2) nonuniform environment: sensor nodes are distributed nonuniformly.

Fig. 4
figure 4

Charging utility as time goes by

Full size image
Fig. 5
figure 5

Survival rate as time goes by

Full size image

5.3 Evaluation results and analysis

Figure 4 shows the charging utility as time goes by. PACSA outperforms APDP, SGCP, mTS and CSGP. It can be observed that PACSA maintains a good stability in both uniform and non-uniform distributions. Figure 5 shows the survival rate as time goes, we can find that PACSA can also maintain a good survival rate for sensor nodes. The survival rate of APDP and SGCP is lower than that of PACSA. This is because APDP does not consider dead nodes, SGCP does not take the adjustable power into consideration. Due to the partial charging scheme adopted by CSGP, more energy is wasted on the journey, which results in fluctuations in the survival rate of sensor nodes. In mTS, the survival rate of nodes drops rapidly with the time goes.

  1. 1.

    Impact of energy capacity of sensor nodes \(E_{max}^n\) : To evaluate the impact of \(E_{max}^n\) on the charging utility and the survival rate, we increase the energy capacity of sensor nodes from 50 to 100 in both uniform and nonuniform environment. As shown in Fig. 6, PACSA performs better than others in terms of \(E_{max}\). The charging utility of APDP, SGCP, mTS and CSGP fluctuate uniformly as \(E_{max}\) grows, the charging utility of PACSA is always larger than them. Moreover, in the case of non-uniform distribution, the charging utility of PACSA is further improved than others. Figure 7 shows that the survival rate of PACSA is always better than other algorithms. As the battery capacity of the charging node increases, the survival rate of sensor nodes becomes better. mTS and CSGP is relatively lower than others. This is because mTS and CSGP make MC waste too much power on the cost of travel.

  2. 2.

    Impact of the number of sensor nodes N : To evaluate the impact of N on the charging utility and the survival rate, we increase the number of sensor nodes from 50 to 100. Figure 8 shows that on average, the charging utility of PACSA outperforms others as the number of sensor nodes increases. The charging utility of PACSA, APDP, SGCP and CSGP grows steadily as N increases because the one-to-many charging mode they use increases as the sensor nodes become denser. The charging utility of mTS increases slowly with small fluctuations because it uses one-to-one charging mode. Figure 9 shows that with the increases in the number of sensor nodes, the survival rate decreases. PACSA has the smallest trend of decreasing as the number of sensor nodes increases in both uniform and nonuniform environments. mTS and CSGP cannot satisfy multiple charging requests at the same time, so the survival rate of sensor nodes drops rapidly.

  3. 3.

    Impact of energy capacity of charger \(E_{max}^c\) : To evaluate the impact of \(E_{max}^c\) on the charging utility and the survival rate, we increase the energy capacity of charger from 1000 to 6000. Figure 10 shows that on average, the charging utility of PACSA performs better than others. In nonuniform environment, PACSA can still maintain a good stability than other algorithms and improve the charging utility in nonuniform environment. Figure 11 shows that the survival rate of sensor nodes varies with \(E_{max}^c\). As the increase energy capacity of charger, the survival rate of PACSA is still better than APDP, SGCP and mTS. Since sensor nodes are denser in partial area under the nonuniform environment, the performance of APDP and SGCP are similar, and the CSGP becomes better than mTS because of adopting one-to-many charging model.

Fig. 6
figure 6

\(E_{max}^n\) vs. charging utility

Full size image
Fig. 7
figure 7

\(E_{max}^n\) vs. survival rate

Full size image
Fig. 8
figure 8

N vs. charging utility

Full size image
Fig. 9
figure 9

N vs. survival rate

Full size image
Fig. 10
figure 10

\(E_{max}^c\) vs. charging utility

Full size image
Fig. 11
figure 11

\(E_{max}^c\) vs. survival rate

Full size image

6 Conclusion

In this paper, we propose the power level aware charging schedule (PACS) problem in WRSN. We first formalize PACS as an optimization problem, which is proved to be NP-hard. Then we utilize network area and power level discretization to reformulate PACS as a monotone submodular optimization problem and design an effective algorithm to solve it. Finally, we conduct experiments and show that our scheme achieves a better performance than existing algorithms in improving charging utility and survival rate. As our future work, we will focus on optimizing the computational complexity and taking the scenarios with restricted roads into account to further improve the charging utility.