Minimizing the Number of Mobile Chargers to Keep Large-Scale WRSNs Working Perpetually

Abstract

Wireless Rechargeable Sensor Networks, in which mobile chargers ( $M C$ s) are employed to recharge the sensor nodes, have attracted wide attention in recent years. Under proper charging schedules, the $M C$ s could keep all the sensor nodes working perpetually. Since $M C$ s can be very expensive, this paper tackles the problem of deciding the minimum number of $M C$ s and their charging schedules to keep every sensor node working continuously. This problem is NP-hard; we divide it into two subproblems and propose a GCHA (Greedily Construct, Heuristically Assign) scheme to solve them. First, the GCHA greedily addresses a Tour Construction Problem to construct a set of tours to 1-cover the WRSN. Energy of the sensor nodes in each of these tours can be timely replenished by one $M C$ according to the decision condition derived from a Greedy Charging Scheme (GCS). Second, the GCHA heuristically solves a Tour Assignment Problem to assign these tours to minimum number of $M C$ s. Then each of the $M C$ s can apply the GCS to charge along its assigned tours. Simulation results show that, on average, the number of $M C$ s obtained by the GCHA scheme is less than 1.1 over a derived lower bound and less than 0.5 over related work.

1. Introduction

During the past decades, Wireless Sensor Networks (WSNs) have been the focus of the research community. WSNs can be widely used in scientific and military data gathering, environmental surveillance, targets monitoring and tracking, and health care, among others. WSNs are composed of many small-sized sensor nodes. Due to cost and size limitations, however, the battery volume of each sensor node is very small. Therefore, energy problem poses a barrier for large-scale deployment of WSNs. To prolong the lifespan of WSNs, methods of energy conservation [1], incremental deployment [2], energy harvesting [3], and wireless charging are proposed. Among these methods, wireless charging is the most promising in removing the energy bottleneck of WSNs [4]. By applying the technique of wireless charging, which refers to magnetic resonant coupling [5] in this paper, a new paradigm of Wireless Rechargeable Sensor Networks (WRSNs) is proposed and immediately received wide attention. In WRSNs, mobile chargers ( $M C$ s) with high volume batteries are employed to replenish the depleted energy of rechargeable sensor nodes. The batteries of the $M C$ s can be quickly renewed at a service station ( $S$ ). In this way, lifespan of WRSNs can be significantly prolonged, or theoretically speaking, to infinity. Applications include sustainable WRSNs in smart grids [6] and underground sensor networks powered by UAVs [7].

Most existing works on WRSNs only use one $M C$ to conduct charging. However, an open issue in these works is their poor scalability. Even when the $M C$ can simultaneously charge all sensor nodes within its charging area, the maximum network size is still limited by its charging power, moving speed, and total energy. Therefore, multiple $M C$ s are employed to address the problem.

Since an $M C$ can be very expensive, the first and foremost issue in designing a WRSN with multiple $M C$ s is to decide the minimum number of $M C$ s required, so that no sensor node will die. This problem, named Minimum Mobile Chargers Problem (MMCP) [8], is closely related to the Distance-Constrained Vehicle Routing Problem (DVRP) [9]. Given a network $G = (E, V)$ and a distance bound D, the DVRP [9] is to find a minimum cardinality set of tours originating from a depot that covers all the vertices in V. Each tour is required to have length at most D. Since $M C$ s are also energy-constrained, researchers reduce MMCP to DVRP, so that solutions for DVRP can be applied to address MMCP [8]. We, however, argue that DVRP is only a subproblem of MMCP. This is because an $M C$ can conduct charging on several tours.

To demonstrate this viewpoint, consider a demo WRSN shown in Figure 1, in which 12 sensor nodes are uniformly deployed along a circle with radius r. Suppose that in this WRSN, due to energy limitation of the $M C$ s, any $M C$ is not able to charge all the sensor nodes in one tour. Instead, at most 3 sensor nodes can be charged within one tour. Then at least 4 tours are needed to cover the whole WRSN, as shown in the figure. Therefore, in this scenario, the answer to the varied DVRP is 4. Suppose the time of charging along each tour is at most t, while the lifetime of any sensor node is at least $4 t$ ; then only one $M C$ is required: the $M C$ charges along tour $R_{i}$ during time $[(4 k + i - 1) \cdot t, (4 k + i) \cdot t]$ ( $1 \leq i \leq 4$ , $k = 0,1, 2, \dots$ ). In this way, energy of all the sensor nodes can be timely replenished. In summary, in this case, the answer to the varied DVRP is 4, while the answer to the MMCP is 1.

Figure 1

A 12-node ring-type WRSN.

Therefore, in this paper, we divide the MMCP into two subproblems, that is, a Tour Construction Problem (TCP) and a Tour Assignment Problem (TAP). The TCP is to construct minimum number of schedulable tours to cover a WRSN. The TAP is to assign the obtained tours to minimum number of $M C$ s, so that all sensor nodes can be charged before their batteries are used up. These two problems are closely coupled. We propose a two-step solution named GCHA (Greedily Construct, Heuristically Assign). First, we construct the shortest Hamilton cycle through $S$ and all the sensor nodes in a WRSN. Based on a decision condition, we greedily split the cycle into several schedulable subtours. Second, we prove that the TAP is NP-hard and propose a heuristic algorithm to solve it. Following these two steps, we finally solve the MMCP.

The objectives of this paper are to decide the minimum number of $M C$ s needed to keep all the sensor nodes in a WRSN working continuously and to construct a valid charging schedule accordingly. The contributions of the paper are the following. (i)

We illustrate the essential difference between the MMCP and the DVRP and divide the MMCP into two NP-hard subproblems.

(ii)

We derive an efficient decision condition of whether a sequence of sensor nodes can be charged by one $M C$ in one tour. The decision condition can be used to construct a set of schedulable tours to cover a WRSN. Charging schedule of charging along each tour can be easily obtained by applying the Greedy Charging Scheme (GCS, first proposed in [10]).

(iii)

We propose a heuristic algorithm to assign a set of schedulable tours to minimum number of $M C$ s. The developed heuristic rules can minimize the conflict ratio of an $M C$ , so that it can charge along maximum number of tours.

(iv)

We develop a lower bound for MMCP. The lower bound is used to evaluate the performance of our solution.

The remainder of the paper is organized as follows. Section 2 introduces latest related work. Section 3 describes model assumptions and the problem under study. The solutions of the TCP and the TAP are detailed in Sections 4 and 5. Section 6 evaluates performance of the GCHA scheme, and Section 7 concludes the paper.

2. Related Work

Most existing works employ only one $M C$ for charging. Peng et al. [11] presented the design and implementation of a wireless rechargeable sensor system and especially studied the charging planning problem. Xie et al. [10] constructed a renewable energy cycle of a WRSN by solving an optimization problem, with the objective of minimizing the overall energy consumption. Hu et al. [12] fully considered the influence of imbalanced energy consumption in WRSNs and proposed an on-demand charging scheme and a method of deploying $S$ . He et al. [13] laid a theoretical foundation for the on-demand mobile charging problem, where individual sensor nodes request charging from the mobile charger when their energy runs low. Wang et al. [14] provided stochastic analysis of wireless energy replenishment and proposed battery-aware energy replenishment strategies with corresponding sensor activation schemes. In addition, literatures [15–17] assume that the $M C$ can function as a mobile sink. Zhao et al. [15] designed an adaptive solution that jointly selects the sensors to be charged and finds the optimal data gathering scheme, such that network utility can be maximized while maintaining perpetual operations of the network. Guo et al. [16] studied the problem of joint wireless energy replenishment and mobile data gathering for WRSNs. The target was to maximize the overall network utility in terms of data gathered by the $M C$ . Shi et al. [17] aimed to jointly optimize a dynamic multihop data routing, a traveling path, and a charging schedule such that the ratio of the $M C$ 's vacation time over the cycle time could be maximized.

Nevertheless, these works can only address the energy problem in small-scale WRSNs. To address the scalability problem, many researchers utilize the technique of simultaneous power transfer [18], so that an $M C$ can simultaneously charge all sensor nodes within its charging area. Tong et al. [19] considered monitoring a field with multiple posts of interest, where at least one sensor node was deployed. They addressed problems of node deployment and routing generation, with the target of minimizing the total charging cost. Xie et al. extended the concept of renewal cycle to multinode case in [20]. Li et al. [21] optimized the usage of the entire energy reserve on the $M C$ by heuristic solutions. Fu et al. [22] planned the optimal movement strategy of the $M C$ , which was meanwhile a RFID reader, such that the time to charge all nodes in the network above their usable energy threshold was minimized.

Although charging multiple nodes simultaneously can relieve the scalability problem to some extent, the size of such WRSNs is still constrained by charging power, moving speed, and total energy of the $M C$ . Therefore, multiple $M C$ s are required to serve large-scale WRSNs. Dai et al. [8] studied the problem of minimizing the number of energy-constrained $M C$ s to cover a 2D WRSN. By conducting appropriate transformations, they casted the problem into DVRP and solved it by applying classical solutions for DVRP. Zhang et al. [23] used a number of $M C$ s with limited energy to charge a one-dimensional WRSN. They assumed that energy can be transferred among $M C$ s with 100% efficiency and then proposed collaborative approaches to maximize the energy efficiency of the $M C$ s. Liang et al. [24] studied the use of minimum number of mobile chargers to charge sensor nodes in a WRSN so that none of the nodes runs out of its energy, subject to the energy capacity imposed on mobile vehicles. They formulated an optimization problem of scheduling mobile vehicles to charge lifetime-critical sensors with an objective to minimize the number of mobile vehicles deployed, subject to the energy capacity constraint on each mobile vehicle. Then they devised an approximation algorithm with a provable performance guarantee.

Different from most existing works, this paper employs multiple $M C$ s to accomplish the charging mission in a WRSN, so that scalability problem can be settled. Literature [23] assumes 100% charging efficiency of $M C$ s and the objective is to maximize the ratio of the amount of payload energy to overhead energy, while we aim to minimize the number of $M C$ s in a 2D WRSN, where $M C$ s cannot transfer energy to each other. Literatures [8, 24] only solve the TCP, while we further propose and solve the TAP to reduce the number of $M C$ s used. (A previous work of this paper is presented in [25, 26].)

3. System Model and Problem Formulation

Consider a 2D WRSN with homogeneous rechargeable sensor nodes $N = {N_{1}, N_{2}, \dots, N_{n}}$ and $M C s$ $M = {M_{1}, M_{2}, \dots, M_{m}}$ . Each sensor node $N_{i}$ ( $1 \leq i \leq n$ ) has a battery with capacity $E_{S}$ and consumes energy at a constant rate $p_{i}$ (applying the techniques in [26], our methods can be used in situations where sensor nodes consume energy at random but bounded rates). The sensor nodes are equipped with wireless energy receivers, which can receive and store energy transferred from an $M C$ . Assume that charging and communication use different frequencies, such as the implementation in [11]; then a sensor node can communicate while being charged.

Suppose that the $M C$ s can move freely in the WRSN at a constant speed v, without any constraint of movement tracks. The energy consumed by each $M C$ for moving per meter is a constant $q_{m}$ . The $M C$ s record the positions of all sensor nodes and can wirelessly charge the sensor nodes at a power rate $q_{c}$ with efficiency η. Suppose that each $M C$ can only charge one sensor node at the same time. Since η drops rapidly as the charging distance increases, we let the $M C$ s move to each sensor node to conduct charging. Consequently, $q_{c}$ and η are viewed as constants. Charging and moving activities of each $M C$ are powered by the same battery with volume $E_{M}$ , which can be renewed at a service station $S$ in an infinitely short period. To simplify the presentation, $S$ is also denoted by $N_{0}$ .

The charging mission in a WRSN is to schedule the charging activities of the $M C$ s to ensure that all sensor nodes will never exhaust their energy. An $M C$ at any time must be in one of the following three states [12]: (a) moving state, that is, moving from one place to another; (b) charging state, that is, charging a sensor node; (c) resting state, that is, renewing its own battery and resting at $S$ . Note that it only consumes energy in moving and charging states. To accomplish a charging mission, we let the $M C$ s periodically charge sensor nodes along a set of tours $R = {R_{1}, R_{2}, \dots, R_{z}}$ . Define that $M_{k}$ can charge along a set of tours $R_{k} = {R_{1}, R_{2}, \dots, R_{z_{k}}}$ if $M_{k}$ can ensure liveness of all the sensor nodes in $R_{k}$ ; then each of the tours is called schedulable, and these tours can be assigned to $M_{k}$ . Suppose that all tours are independently charged along; that is, each $M C$ must finish charging along one tour before it charges along the next. A charging schedule determines when do the $M C$ s charge which sensor nodes in what sequence and for how long. A charging schedule is called valid if it can be applied to accomplish the charging mission.

Tour $R_{i} = 〈N_{0}, N_{1}, \dots, N_{r_{i}}〉$ determines an $M C$ 's charging sequence of the $r_{i}$ sensor nodes. Obviously, the union of the sensor nodes in tours $R$ should fully cover the WRSN:

\begin{matrix} ⋃_{i = 1}^{z} R_{i} = N \cup S . \end{matrix}

(1)

M C

periodically charges along tour

R_{i}

with charging period

T_{i}

(

1 \leq i \leq z

). As will be proved in Section 4,

T_{i}

of tour

R_{i}

ranges in a feasible region

[T_{i}^{l}, T_{i}^{u}]

. Assume that

T_{i}

is rational. Within each charging period

T_{i}

, the total time an

M C

spends in moving and charging states is called the working time of

R_{i}

, denoted by

T_{i}^{w}

(

T_{i}^{w} \leq T_{i}

). Consequently, we also use a tuple

(T_{i}, T_{i}^{w})

to substitute for

R_{i}

. However, if the charging period of

R_{i}

has not been determined, the tour can be denoted by a triple

(T_{i}^{l}, T_{i}^{u}, ω_{i})

, where

ω_{i}

is a working time function dependent on

T_{i}

. The three representations of

R_{i}

will be used interchangeably in the rest of the paper, where no ambiguity occurs.

Suppose $z_{k}$ tours $R_{k} = {R_{1}, R_{2}, \dots, R_{z_{k}}}$ are assigned to $M_{k}$ ( $1 \leq z_{k} \leq z$ ); then we define the element period of $M_{k}$ , denoted by $G_{k}$ , as the greatest common divisor of charging periods of these $z_{k}$ tours. Define the conflict ratio of $M_{k}$ as

\begin{matrix} δ_{k} = \frac{\sum_{i = 1}^{z_{k}} T_{i}^{w}}{G_{k}}, G_{k} = GCD (T_{1}, T_{2}, \dots, T_{z_{k}}), \end{matrix}

(2)

where function

GCD (\cdot)

returns the greatest common divisor of the given numbers. Informally speaking,

δ_{k}

indicates the maximum work load of

M_{k}

within any element period

G_{k}

; during

G_{k}

M_{k}

charges along

R_{i} \in R_{k}

for at most once. We will prove that if

δ_{i}

M_{i}

is no more than 1, a valid charging schedule of charging along these k tours can be easily constructed. For instance, in Figure 2,

R_{1} = (7.5,1)

and

R_{2} = (5,1.5)

can be assigned to one

M C

. Because the element period of the

M C

G = GCD (T_{1}, T_{2}) = GCD (7.5,5) = 2.5

, the conflict ratio of the

M C

δ = (T_{1}^{w} + T_{2}^{w}) / G = (1 + 1.5) / 2.5 = 1

Figure 2

Assigning $R_{1}$ an $R_{2}$ to one $M C$ .

Then the problem addressed in this paper can be formulated as follows.

Minimum Mobile Chargers Problem (MMCP). Given n sensor nodes $N = {N_{i} (p_{i}, E_{S}) | 1 \leq i \leq n}$ and their positions in a WRSN, decide the minimum size m of $M = {M_{i} (q_{c}, q_{m}, v, E_{M}) | 1 \leq i \leq m}$ to accomplish the charging mission.

When obtaining the minimum number of $M C$ s, a valid charging schedule should be constructed at the same time. To this end, the GCHA scheme constructs a set of schedulable tours that 1-covers the WRSN. Then it assigns the tours to minimum number of $M C$ s. Each $M C$ applies the GCS to charge along its assigned tours. The notations appearing in this paper are listed in Notations for readers’ convenience.

4. The Tour Construction Problem

Tours in $R$ should fully cover the WRSN; we consider a scenario that these tours form an exact 1-cover of the WRSN. In other words, intersection of any two tours is empty, and any sensor node can appear in any tour for at most once:

\begin{matrix} R_{i} \cap R_{j} = ⌀, R_{i}, R_{j} \in R, \\ N_{i} \neq N_{j}, N_{i}, N_{j} \in R_{k}, R_{k} \in R . \end{matrix}

(3)

Then we propose and address the following problem.

Tour Construction Problem (TCP). Given n sensor nodes $N = {N_{i} (p_{i}, E_{S}) | 1 \leq i \leq n}$ and their positions in a WRSN, construct minimum number of tours $R$ , schedulable to $M C$ s $(q_{c}, q_{m}, v, E_{M})$ , to exactly 1-cover the WRSN.

The decision form of the TCP is NP-hard, since TCP contains DVRP as a subproblem [8]. A simple transformation is to let $n \cdot E_{S} \to 0$ ; then the TCP can be reduced to a DVRP with distance constraint $E_{M} / q_{m}$ . To address the TCP, we firstly propose a sufficient condition for an $M C$ to be able to charge along a tour. The condition is derived from a Greedy Charging Scheme (GCS). Then, based on the decision condition, we greedily split the shortest Hamilton cycle through $S$ and $N$ into minimum number of schedulable subtours. The procedure is elaborated below.

4.1. The Greedy Charging Scheme

When charging along a tour $R = 〈N_{0}, N_{1}, \dots, N_{r}〉$ ( $1 \leq r \leq n$ ), an $M \in M$ applies the GCS as follows. In each period, M starts from $N_{0}$ , sequentially fully charges each sensor node, then returns to $N_{0}$ , quickly renews its battery, and rests until next period. Denote that M arrives at $N_{i}$ at time $t_{i}$ and charges $N_{i}$ for time $τ_{i}$ ; then we have

\begin{matrix} t_{i} = \sum_{j = 0}^{i - 1} τ_{j} + \sum_{j = 1}^{i} \frac{d_{j - 1, j}}{v}, 1 \leq i \leq r . \end{matrix}

(4)

In (4),

d_{i, j}

is the distance between

N_{i}

and

N_{j}

and

τ_{0} \geq 0

is the duration that M rests at

S

, and let

t_{0} = 0

to simplify the presentation. Then M can periodically charge along R with charging period

\begin{matrix} T = \sum_{j = 0}^{r} τ_{j} + \frac{D}{v}, \end{matrix}

(5)

where

D = \sum_{j = 1}^{r} d_{j - 1, j} + d_{r, 0}

is the total traveling distance of the tour. Then, within each charging period, the energy consumed by

N_{i}

can be fully replenished by M; that is,

\begin{matrix} τ_{i} \cdot q_{c} \cdot η = p_{i} \cdot T, 1 \leq i \leq r . \end{matrix}

(6)

To ensure the sensor nodes are working continuously, their energy levels should never fall below 0 during T; that is,

\begin{matrix} E_{S} - p_{i} \cdot (T - τ_{i}) \geq 0, 1 \leq i \leq r . \end{matrix}

(7)

Meanwhile, the total energy of M should be enough to conduct charging; that is,

\begin{matrix} D \cdot q_{m} + \sum_{j = 1}^{r} \cdot q_{c} \cdot τ_{j} \leq E_{M} . \end{matrix}

(8)

Therefore, M can charge along tour R applying the GCS if and only if it satisfies (4)–(8).

4.2. Deriving the Decision Condition

According to the formulation of the GCS, we can derive an efficient decision condition to decide whether a tour is schedulable. The decision condition, named Tour Schedulable (TS) condition, can be used to construct schedulable tours to exactly 1-cover the WRSN.

Equation (6) can be rewritten as

\begin{matrix} τ_{i} = \frac{p_{i} \cdot T}{q_{c} \cdot η}, 1 \leq i \leq r . \end{matrix}

(9)

Thus the charging duration of each sensor node is dependent on its charging period T. In fact, T determines the charging schedule of M applying the GCS, according to (4) and (9). Furthermore, T also determines the working time of R:

\begin{matrix} T^{w} = \sum_{i = 1}^{n} τ_{i} + \frac{D}{v} = \frac{p_{sum}}{q_{c} \cdot η} \cdot T + \frac{D}{v} . \end{matrix}

(10)

Obviously,

T^{w}

increases as T increases; however,

T^{w} / T

decreases as T increases. Literature [12] presented that

T^{w} / T

indicates the total energy consumption of M in charging along R; thus it should be minimized. Plugging (9) into (5) we have

\begin{matrix} T = τ_{0} + \frac{\sum_{i = 1}^{r} p_{i} \cdot T}{q_{c} \cdot η} + \frac{D}{v} \geq \frac{\sum_{i = 1}^{r} p_{i} \cdot T}{q_{c} \cdot η} + \frac{D}{v}, \end{matrix}

(11)

or, equivalently,

\begin{matrix} T \geq \frac{D \cdot q_{c} \cdot η}{v \cdot (q_{c} \cdot η - p_{sum})}, p_{sum} = \sum_{i = 1}^{r} p_{i} . \end{matrix}

(12)

Let

T^{l} = (D \cdot q_{c} \cdot η) / (v \cdot (q_{c} \cdot η - p_{sum}))

; then feasible charging period of tour R cannot be less than

T^{l}

; otherwise M does not have enough time to charge all the sensor nodes in R. Note that, to make (12) work, a necessary condition should be met:

q_{c} \cdot η > p_{sum}

Plugging (9) into (7) we have

\begin{matrix} E_{S} \geq \frac{p_{i} \cdot (q_{c} \cdot η - p_{i})}{q_{c} \cdot η} \cdot T, 1 \leq i \leq r . \end{matrix}

(13)

Since

q_{c} \cdot η > p_{sum} > p_{i}

, the inequality is equal to

\begin{matrix} T \leq \frac{E_{s} \cdot q_{c} \cdot η}{p_{mx}}, p_{mx} = max_{1 \leq i \leq r} p_{i} \cdot (q_{c} \cdot η - p_{i}) . \end{matrix}

(14)

Let

T^{u} = (E_{s} \cdot q_{c} \cdot η) / p_{mx}

; then feasible charging period of R cannot exceed

T^{u}

, or some sensor node will run out of energy before it is charged. Combining (12) and (14) we have

\begin{matrix} \frac{D \cdot q_{c} \cdot η}{v \cdot (q_{c} \cdot η - p_{sum})} \leq \frac{E_{s} \cdot q_{c} \cdot η}{p_{mx}} \end{matrix}

(15)

or, equivalently,

v \geq (D \cdot p_{mx}) / (E_{S} \cdot (q_{c} \cdot η - p_{sum}))

, which is also a necessary condition for R to have feasible charging period. Plugging (9) into (8) we have

\begin{matrix} E_{M} \geq D \cdot q_{m} + \frac{p_{sum}}{η} \cdot T . \end{matrix}

(16)

Formula (16) shows the minimum energy required for an

M C

to charge along R with charging period T. Let

T = T^{u}

; we have

E_{M} \geq (E_{S} \cdot q_{c} \cdot p_{sum}) / p_{mx} + D \cdot q_{m}

. By now, we have derived a sufficient condition for M to charge along R.

TS Condition. An $M C$ applying the GCS can charge along tour $R = 〈N_{0}, N_{1}, \dots, N_{r}〉$ if (a) $q_{c} \cdot η > p_{sum}$ ; (b) $v \geq (D \cdot p_{mx}) / (E_{S} \cdot (q_{c} \cdot η - p_{sum}))$ ; (c) $E_{M} \geq D \cdot q_{m} + (p_{sum} \cdot E_{S} \cdot q_{c}) / p_{mx}$ .

Note that in deriving the TS condition, we let $T = T^{u}$ to decide the minimum energy requirement of an $M C$ . One can set other feasible T to derive a new sufficient condition, or say anchoring other values of T for short. In the next section, however, we will show that anchoring $T = T^{u}$ can minimize the total energy consumption of the $M C$ s, as well as the conflict ratio it generated.

Although the TS condition is not necessary for a tour to be schedulable [26], $q_{c} \cdot η > p_{sum}$ is a hard condition for any $M C$ to be able to charge along any tour. Furthermore, if the total charging power of $M$ is not larger than the total energy consumption rate of $N$ in the WRSN, the charging mission cannot be accomplished. Therefore, we obtain a lower bound of the number of $M C$ s needed to solve the MMCP.

Lower Bound $m^{*}$ . Given n sensor nodes $N = {N_{i} (p_{i}, E_{S}) | 1 \leq i \leq n}$ and their positions in a WRSN, the minimum number of $M C$ s $(q_{c}, q_{m}, v, E_{M})$ needed to accomplish the charging mission is not less than $m^{*} = ⌈\sum_{i = 1}^{n} p_{i} / (q_{c} \cdot η)⌉$ .

The lower bound $m^{*}$ is not tight, since it only considers the influence of charging. Obviously, an $M C$ also spends time and energy on moving. Therefore, a more rigorous lower bound should be not less than $m^{*}$ . However, determining $m^{*}$ is very simple and efficient; thus we use $m^{*}$ for performance evaluation in Section 4.

Based on the TS condition, we propose Algorithm 1 to decide whether a tour can be assigned to an $M C$ (lines (1)–(7)). If the tour is schedulable, then Algorithm 1 returns the feasible region of its charging period (lines (8)-(9)) and the corresponding working time function (line (10)).

Algorithm 1: Decide whether an $M C$ can charge along R.

Require:

R = $〈N_{0}, N_{1}, \dots, N_{r}〉$ , $E_{S}$ , $q_{m}$ , $q_{c}$ , v, $E_{M}$ , η;

Ensure:

Schedulability of R; $(T^{l}$ , $T^{u}$ , $ω)$ .

( $1$ ) calculate path length D of R;

( $2$ ) inquire energy consumption rates ${p_{i}}$ of the sensor nodes in R;

( $3$ ) $p_{sum} = \sum_{i = 1}^{r} p_{i}$ ;

( $4$ ) $p_{m x} = max_{1 \leq i \leq r} p_{i} \cdot (q_{c} \cdot η - p_{i})$ ;

( $5$ ) if the conditions in Proposition 2 are not satisfied then

( $6$ ) return unschedulable;

( $7$ ) end if

( $8$ ) $T^{l} = \frac{D \cdot q_{c} \cdot η}{v \cdot (q_{c} \cdot η - p_{s u m})}$ ;

( $9$ ) $T^{u} = \frac{E_{s} \cdot q_{c} \cdot η}{p_{m x}}$ ;

( $10$ ) $ω (T) = \frac{p_{s u m}}{q_{c} \cdot η} \cdot T + \frac{D}{v}$ ;

( $11$ ) return schedulable;

4.3. Obtaining Schedulable Subtours

Since TCP is NP-hard, based on the TS condition, we propose a greedy solution, as shown in Algorithm 2. First, we construct a Hamilton tour H through $S$ and $N$ by applying LKH algorithm [27] (lines (2)-(3)). Then we replace edges $e_{i, i + 1}$ and $e_{j, j + 1}$ by $e_{0, i + 1}$ and $e_{j, 0}$ (lines (5), (7)) and decide whether an $M C$ can charge along tour $〈N_{0}, N_{i + 1}, \dots, N_{j}〉$ using Algorithm 1 (line (8)). A subtour is constructed if no more sensor nodes can be inserted (lines (9)–(13)). Repeat the procedure until all sensor nodes are covered (line (4)). In this way, we greedily split H into z schedulable subtours. Figure 3 shows a demonstration of Algorithm 2, in which two schedulable tours are constructed to cover the 5-node WRSN. Computation complexity of verifying Proposition 2 is $O (r)$ . If variables such as $p_{sum}$ and $p_{mx}$ can be saved in the algorithm, the complexity of updating these information is $O (1)$ . Then lines (3)–(15) can be executed with complexity $O (n)$ . Therefore, the computation complexity of Algorithm 2 is dependent on that of LKH, which is $O (n^{2.2})$ [27]. Note that H is not necessarily the shortest Hamilton cycle through the WRSN. In fact, it only provides a sequence of sensor nodes. Therefore, H can be any permutation of the sensor nodes. For instance, H can be obtained by sorting the sensor nodes in ascending order of their energy consumption rates. In this way, sensor nodes in each constructed subtour have similar energy consumption rates and greatly relief the load imbalance phenomenon [12], which causes great waste in periodic charging schemes. From this viewpoint, a periodic charging scheme using multiple $M C$ s is similar to an on-demand charging scheme using one $M C$ . Nevertheless, total distance of each subtour should be minimized [10]. Therefore, it is a compromise that we made in designing Algorithm 2.

Algorithm 2: Construct a Hamilton tour H through $S$ and $N$ ; split H into z schedulable subtours.

Require:

$N = {N_{i} | 1 \leq i \leq n}$ ;

Ensure:

$R = {R_{i} | 1 \leq i \leq z}$ ;

( $1$ ) $z = 1, i = 1$ ;

( $2$ ) apply LKH on $S \cup N$ to obtain H;

( $3$ ) renumber sensor nodes in H as $N_{0}, N_{1}, \dots, N_{n}$ ( $N_{0} = S$ );

( $4$ ) while $i \leq n$ do

( $5$ ) push $N_{0}$ into $R_{z}$ ;

( $6$ ) for $j = i$ to n do

( $7$ ) push $N_{j}$ into $R_{z}$ ;

( $8$ ) apply Algorithm 1 to decide the schedulability of $R_{z}$ ;

( $9$ ) if $R_{z}$ is unschedulable then

( $10$ ) pop $N_{j}$ from $R_{z}$ ;

( $11$ ) $i = j, z = z + 1$ ;

( $12$ ) break;

( $13$ ) end if

( $14$ ) end for

( $15$ ) end while

Figure 3

Demonstration of the tour construction algorithm.

5. The Tour Assignment Problem

After obtaining schedulable subtours that 1-cover all the sensor nodes, we further assign these subtours to minimum number of $M C$ s. To this end, we firstly formulate the Tour Assignment Problem (TAP) and prove its NP-hardness. Then we propose a heuristic algorithm to solve the problem. Every tour discussed in this section is schedulable.

5.1. The Tour Assignment Problem

According to the abovementioned analysis, feasible charging period $T_{i}$ of tour $R_{i}$ ranges from $T_{i}^{l}$ to $T_{i}^{u}$ , which also decides the working time $T_{i}^{w}$ of $R_{i}$ in each period: $T_{i}^{w} = ω_{i} (T_{i}) = (p_{sum}^{i} / (q_{c} \cdot η)) \cdot T_{i} + D_{i} / v$ . Then the assignment problem can be formulated as follows.

Tour Assignment Problem (TAP). Given z tours $R = {R_{i} = (T_{i}^{l}, T_{i}^{u}, ω_{i}) | 1 \leq i \leq z}$ and enough $M C$ s $(q_{c}, q_{m}, v, E_{M})$ , assign tours $R$ to minimum number of $M C$ s.

To prove the NP-hardness of the TAP, we firstly consider r tours with equal charging period T and investigate the sufficient and necessary condition of assigning these r tours to one $M C$ .

Proposition 1.

Given r tours ${R_{i} = (T, T_{i}^{w}) | 1 \leq i \leq r}$ , they can be assigned to one $M C$ if and only if $\sum_{i = 1}^{r} T_{i}^{w} \leq T$ .

Proof.

Suppose these k tours can be assigned to the same $M C$ ; then $\sum_{i = 1}^{r} T_{i}^{w} \leq T$ . Otherwise the $M C$ cannot finish charging along all tours within one charging period T, causing conflicts in the next period.

On the other hand, if $\sum_{i = 1}^{r} T_{i}^{w} \leq T$ , one can construct a valid schedule as follows. The $M C$ charges sensor nodes in $R_{i}$ during time $[k \cdot T + \sum_{j = 1}^{i - 1} T_{j}^{w}, k \cdot T + \sum_{j = 1}^{i} T_{j}^{w}]$ ( $k = 0,1, 2, \dots$ ). Since $\sum_{i = 1}^{r} T_{i}^{w} \leq T$ , this schedule is valid.

Therefore, the proposition follows.

Based on Proposition 1, we reduce the TAP to a set-partition problem and consequently prove that the decision form of the problem is NP-hard.

Proposition 2.

Deciding whether z tours can be assigned to m $M C$ s is NP-hard.

Proof.

Consider z tours ${R_{i} = (T, T_{i}^{w}) | 1 \leq i \leq z}$ , and suppose $\sum_{i = 1}^{z} T_{i}^{w} = 2 T$ . Let $m = 2$ ; then the decision problem can be reformulated as whether ${R_{i}}$ can be assigned to 2 $M C$ s.

We now construct a set-partition problem as follows. Given z numbers ${a_{1}, a_{2}, \dots, a_{z}}$ , in which $a_{i} = T_{i}^{w} / T$ ( $1 \leq i \leq z$ ), then, according to Proposition 1, the above question is equivalent to whether the z numbers can be evenly partitioned into two sets. Since the set-partition problem is NP-hard, the original problem is also NP-hard.

5.2. The Heuristic Solution

We propose a heuristic method to decide (a) the charging period of each tour and (b) whether a set of tours with fixed charging periods can be assigned to one $M C$ .

We firstly generalize the assumption in Proposition 1 and assume that tours have different charging periods. Then we derive a necessary condition for these tours to be assigned to the same $M C$ . Suppose that the periods of all tours are rational numbers and their greatest common divisor is G (G can be a decimal); then we have the following proposition.

Proposition 3.

Given k set of tours: ${R_{i}^{j} = (a_{j} \cdot G, T_{i}^{j}) | 1 \leq i \leq r_{j}, 1 \leq j \leq k}$ , where $R_{i}^{j}$ is the ith tour of the jth set and ${a_{j}}$ are coprime integers, these tours can be assigned to one $M C$ only if $\sum_{j = 1}^{k} (\sum_{i = 1}^{r_{j}} T_{i}^{j} / a_{j}) \leq G$ .

Proof.

Suppose these tours can be assigned to one $M C$ , while $\sum_{j = 1}^{k} (\sum_{i = 1}^{r_{j}} T_{i}^{j} / a_{j}) > G$ . Denote the least common multiple of $a_{1}, a_{2}, \dots, a_{k}$ by P. Multiplying both sides of the inequality by P, we have

\begin{matrix} \frac{P}{a_{1}} \cdot \sum_{i = 1}^{r_{1}} T_{i}^{1} + \frac{P}{a_{2}} \cdot \sum_{i = 1}^{r_{2}} T_{i}^{2} + \dots + \frac{P}{a_{k}} \cdot \sum_{i = 1}^{r_{k}} T_{i}^{k} > G \cdot P, \end{matrix}

(17)

where

P / a_{j}

means how many times does the

M C

charge along tours

{R_{i}^{j}}

during

G \cdot P

and

\sum_{i = 1}^{r_{j}} T_{i}^{j}

is the total working time of the jth set of tours within each charging period

a_{j} \cdot G

. It means that the total working time of all the tours during

G \cdot P

is larger than

G \cdot P

, which is a contradiction.

Therefore, the proposition follows.

Unfortunately, the condition is not sufficient, because it requires that the jth set of tours can be evenly partitioned into $a_{j}$ parts, such that the total working time of tours in each part is the same. Otherwise these tours are not surely schedulable. For example, tours ${2 T, 2 T / 3}$ , ${2 T, T / 3}$ , and ${T, T / 2}$ cannot be charged by one $M C$ even if they satisfy Proposition 3. Besides, deciding whether the jth set of tours can be evenly partitioned into $a_{j}$ parts is NP-hard, since it can be easily reduced to a set-partition problem. Therefore, we propose the following sufficient condition for efficiently deciding whether r tours can be assigned to one $M C$ .

Proposition 4.

Given r tours ${R_{i} = (a_{i} \cdot G, T_{i}^{w}) | 1 \leq i \leq r}$ , where ${a_{i}}$ are coprime integers, they can be assigned to one $M C$ if $\sum_{i = 1}^{r} T_{i}^{w} \leq G$ .

Proof.

Consider r tours ${R_{i}^{'} = (G, T_{i}^{w}) | 1 \leq i \leq r}$ ; if they can be assigned to one $M C$ , obviously ${R_{i}}$ can be assigned to the same $M C$ . Since $\sum_{i = 1}^{r} T_{i}^{w} \leq G$ , according to Proposition 3, ${R_{i}^{'}}$ can be assigned to one $M C$ . Therefore, ${R_{i}}$ can be assigned to one $M C$ .

Note that Proposition 4 is not necessary. For instance, consider tour $R^{A} = (T, T / 2)$ and r tours ${R_{i}^{B} = (r \cdot T, T / 2) | r > 1, 1 \leq i \leq r}$ . Since $GCD (T, r \cdot T) = T$ , and the total working time of the $r + 1$ tours is $((r + 1) / 2) \cdot T > T$ , the condition in Proposition 4 is not met. However, one can still assign them to one $M C$ : let the $M C$ charge along tour $R^{A}$ during time $[j \cdot T, (j + 1 / 2) \cdot T]$ and charge along tour $R_{i}^{B}$ during time $[(j \cdot r + i - 1 / 2) \cdot T, (j \cdot r + i) \cdot T]$ , $j = 0,1, 2, \dots$ . It can be readily proved that the charging schedule is valid.

Proposition 4 inspires us to minimize the conflict ratio of each $M C$ : $δ = \sum_{i = 1}^{r} (T_{i}^{w} / G)$ . If it is no more than 1, valid charging schedule can be readily constructed. Based on this idea, we propose the following heuristic rule to determine the charging period of each tour.

Proposition 5.

Suppose tours $R_{1} = (T_{1}^{l}, T_{1}^{u}, ω_{1})$ and $R_{2} = (T_{2}^{l}, T_{2}^{u}, ω_{2})$ are assigned to M, where $(k - 1) \cdot T_{1}^{u} < T_{2}^{l} \leq k \cdot T_{1}^{u} \leq T_{2}^{u}$ ( $k \geq 1$ ); then the conflict ratio δ of M is minimized when $T_{1} = T_{1}^{u}$ and $T_{2} = k \cdot T_{1}^{u}$ .

Proof.

For each tour $R_{i}$ , $ω (T_{i}) = (p_{sum}^{i} / (q_{c} \cdot η)) \cdot T_{i} + D_{i} / v$ . To simplify the presentation, denote that $ω (T_{i}) = a_{i} \cdot T_{i} + b_{i}$ .

Consider δ when $T_{2}$ varies within time interval $[i \cdot T_{1}, (i + 1) \cdot T_{1}]$ ( $i = 1,2, \dots$ ):

\begin{array}{l} δ_{1} = a_{1} + i \cdot a_{2} + \frac{b_{1} + b_{2}}{T_{1}}, T_{2} = i \cdot T_{1}, \\ δ_{2} = a_{1} + (i + 1) \cdot a_{2} + \frac{b_{1} + b_{2}}{T_{1}}, T_{2} = (i + 1) \cdot T_{1}, \\ δ_{3} = \frac{a_{1} \cdot T_{1} + a_{2} \cdot T_{2}}{G} + \frac{b_{1} + b_{2}}{G}, \\ i \cdot T_{1} < T_{2} < (i + 1) \cdot T_{1}, \end{array}

(18)

where

G = GCD (T_{1}, T_{2})

. When

i \cdot T_{1} < T_{2} < (i + 1) \cdot T_{1}

G \leq T_{1} / 2

, we hence have

\begin{array}{l} δ_{3} = \frac{a_{1} \cdot T_{1} + a_{2} \cdot T_{2}}{G} + \frac{b_{1} + b_{2}}{G} \\ \geq 2 a_{1} + 2 i \cdot a_{2} + \frac{2 (b_{1} + b_{2})}{T_{1}} \\ > a_{1} + (i + 1) \cdot a_{2} + \frac{b_{1} + b_{2}}{T_{1}} = δ_{2} . \end{array}

(19)

In other words,

δ_{1} < δ_{2} < δ_{3}

. Therefore, in this scenario, δ is minimized when

T_{2} = i \cdot T_{1}

. Then

δ = a_{1} + i \cdot a_{2} + (b_{1} + b_{2}) / T_{1}

On the other hand, δ decreases as $T_{1}$ increases. To minimize δ, we have $T_{1} = T_{1}^{u}$ . Since $(k - 1) \cdot T_{1}^{u} < T_{2}^{l} \leq k \cdot T_{1}^{u} \leq T_{2}^{u}$ , we have $i = k$ ; that is, $T_{2} = k \cdot T_{1}^{u}$ .

In summary, δ is minimized when $T_{1} = T_{1}^{u}$ and $T_{2} = k \cdot T_{1}^{u}$ ; then the proposition follows.

In fact, Proposition 5 requires the element period G of M to be maximized. This is an important reason that we anchor $T = T^{u}$ when deriving the TS condition. Note that one can set $T = T^{'}$ ( $T^{l} \leq T^{'} < T^{u}$ ) in deriving the TS condition. In this way, the number of subtours may be reduced in Algorithm 2. Nevertheless, these tours are harder to be assigned to one $M C$ according to Proposition 5. More importantly, anchoring smaller value of T will increase the total working time ratio (denoted by $Φ_{w}$ ) of the $M C$ s:

\begin{matrix} Φ_{w} = \sum_{i = 1}^{m} \sum_{j = 1}^{z_{i}} \frac{T_{j}^{w}}{T_{j}} = \sum_{i = 1}^{z} \frac{T_{i}^{w}}{T_{i}} . \end{matrix}

(20)

We have proved in [12] that the working time ratio of an

M C

indicates the total energy consumption of the

M C

in conducting charging. Therefore,

Φ_{w}

indicates the total energy consumption of all the

M C

s. Based on the above two reasons, we anchor

T = T^{u}

in deriving the TS condition. Comparisons of anchoring different values of T are made through simulations.

Based on the heuristic rules formulated in Propositions 4 and 5, we propose Algorithm 3 to greedily assign maximum number of tours to each $M C$ . First, the tours obtained by Algorithm 2 are sorted by $T^{u}$ in ascending order (line (2)). Then, for each $M C$ , sequentially consider if tour $R_{i}$ can be assigned to it (lines (3)–(18)). According to Proposition 5, the element period $G_{k}$ of $M_{k}$ is set to $T_{i}^{u}$ of its first assigned tour $R_{i}$ (line (7)). For any subsequent tour $R_{j}$ , it is assigned to $M_{k}$ (lines (6), (13)) if (a)

$R_{j}$ has not been assigned to any $M C$ (lines (4), (9)),

(b)

feasible period of $R_{j}$ contains a multiple of $G_{k}$ (lines (10)-(11)),

(c)

after assigning, the conflict ratio $δ_{k}$ of $M_{k}$ is still no more than 1 (line (11)).

Then charging period

T_{j}

R_{j}

is determined according to Proposition 5 (lines (7), (12)). It can be readily proved that the worst case computation complexity of Algorithm 3 is

O (z^{2})

, where z is the number of tours.

Algorithm 3: Sort tours $R$ by $T^{u}$ ; greedily assign the tours to minimum $M C$ s based on Propositions 4 and 5.

Require:

$R = {R_{i} | 1 \leq i \leq z}$ ;

Ensure:

$M = {M_{i} | 1 \leq i \leq m}$ , tour assignment of each $M C$ ;

( $1$ ) $m = 0$ ;

( $2$ ) sort ${R_{i}}$ by $T_{i}^{u}$ in ascending order;

( $3$ ) for $i = 1$ to z do

( $4$ ) if $R_{i}$ has not been assigned then

( $5$ ) $m + = 1$ ;

( $6$ ) assign $R_{i}$ to $M_{m}$ ;

( $7$ ) $G_{m} = T_{i} = T_{i}^{u}$ , $δ_{m} = \frac{ω_{i} (T_{i})}{G_{m}}$ ;

( $8$ ) for $j = i + 1$ to z do

( $9$ ) if $R_{j}$ has not been assigned then

(10) calculate the k described in Proposition 5;

( $11$ ) if k exists and $δ_{m} + (ω_{j} (k \cdot T_{i}^{u}) / G_{m}) \leq 1$ then

(12) $T_{j} = k \cdot T_{i}^{u}$ , $δ_{m} + = \frac{ω_{j} (T_{j})}{G_{m}}$ ;

(13) assign $R_{j}$ to $M_{m}$ ;

(14) end if

(15) end if

(16) end for

(17) end if

( $18$ ) end for

After tour assignment, each $M C$ applies the GCS to periodically charge along its assigned tours. Suppose $z_{x}$ tours $R_{x} = {R_{i} = (a_{i} \cdot G_{x}, T_{i}^{w})}$ are assigned to $M_{x}$ ( $1 \leq i \leq z_{x} \leq n$ , $1 \leq x \leq m$ ); then a valid charging schedule is that $M_{x}$ charges $R_{i}$ during time $[k \cdot a_{i} \cdot G_{x} + \sum_{j = 1}^{i - 1} T_{j}^{w}, k \cdot a_{i} \cdot G_{x} + \sum_{j = 1}^{i} T_{j}^{w}]$ ( $k = 0,1, 2, \dots$ ) and rests at $S$ at other times. The details of the charging schedule are shown in Algorithm 4. However, when $M_{x}$ charges $R_{i}$ for the first time, since the sensor nodes are initially fully charged, the actual working time of tour $R_{i}$ is less than $T_{i}^{w}$ . This may influence subsequent periods. To address this issue, one can make $M_{x}$ stay at sensor node $N_{j}$ in $R_{i}$ for time $(p_{j} \cdot T_{i}) / (q_{c} \cdot η)$ and leave with $N_{j}$ fully charged. In this way, the actual working time of $R_{i}$ is $T_{i}^{w}$ afterwards.

Algorithm 4: Construct a valid charging schedule of $M_{k}$ along its assigned tours $R_{k}$ .

Require:

$R_{k} = {R_{i} | 1 \leq i \leq z_{k}}$ ;

Ensure:

${(R_{i}, 〈t_{j}^{i}〉, 〈τ_{j}^{i}〉) | 1 \leq i \leq z_{k}, 1 \leq j \leq r_{i}}$ ;

( $1$ ) $τ_{0}^{1} = 0$ ;

( $2$ ) for $i = 2$ to $z_{k}$ do

( $3$ ) $τ_{0}^{i} = τ_{0}^{i - 1} + T_{i - 1}^{w}$ ;

( $4$ ) end for

( $5$ ) for $i = 1$ to $z_{k}$ do

( $6$ ) $t_{0}^{i} = 0$ ;

( $7$ ) $τ_{j}^{i} = \frac{T_{i} \cdot p_{j}}{q_{c} \cdot η}$ , $1 \leq j \leq r_{i}$ ;

( $8$ ) $t_{j}^{i} = t_{j - 1}^{i} + τ_{j - 1}^{i} + \frac{d_{j - 1, j}}{v}$ , $0 \leq j \leq r_{i}$ ;

( $9$ ) end for

( $10$ ) $k = 0$ ;

( $11$ ) while ++k do

( $12$ ) set current time to 0;

( $13$ ) for $i = 1$ to z do

( $14$ ) if $k % a_{i} = 0$ then

( $15$ ) $M C$ leaves $S$ to charge along tour $R_{i}$ at time $τ_{0}^{i}$ ;

( $16$ ) for $j = 1$ to $r_{i}$ do

( $17$ ) $M C$ arrives $N_{j}^{i}$ at $t_{j}^{i}$ , and charges it for $τ_{i}^{i}$ ;

( $18$ ) end for

( $19$ ) $M C$ returns to $S$ , end of charging along tour $R_{i}$ ;

( $20$ ) end if

( $21$ ) end for

( $22$ ) end while

5.3. The Complete Procedure of the GCHA Solution

To summarize, the complete procedure of the GCHA solution is presented as follows. First, apply Algorithm 2 to construct z schedulable tours to 1-cover the WRSN. During this step, Algorithm 1 is constantly called to decide whether a tour of sensor nodes can be timely charged by one $M C$ . Second, apply Algorithm 3 to decide the charging period of each tour, and assign these tours to $m M C$ s. Then the $M C$ s apply Algorithm 4 to conduct charging along their assigned tours. The computation complexity of the solution is dependent on Algorithm 2, which is $O (n^{2.2})$ .

6. Numerical Results

In this section, we evaluate the performance of the GCHA solution. To this end, WRSNs are randomly generated over a 1000 m × 1000 m square area. The sink node and service station are located at the center of the area. The sensor nodes generate data at a random rate within $[10,100]$ kbps, and their communication radius is 200 m. The energy consumption model is adopted from [10], in which only energy consumption of sending and receiving data is considered. Particularly, energy consumption of receiving a bit of data is a constant, while energy consumption of sending a bit of data is additionally dependent on the transmitting distance. The routing scheme is the well known GPSR [28], which is well scalable and also based on location information. By default, we set $E_{S} = 10$ kJ, $q_{m} = 5$ J/m, $v = 5$ m/s, $E_{M} = 40$ kJ, and $η = 1$ , which are adopted from [10] or with reasonable estimation.

6.1. Demonstration of the GCHA Solution

To better demonstrate the procedures of the GCHA solution, we randomly generate a 100-node WRSN, as shown in Figure 4, and set $q_{c} = 5$ W. The $S$ and sink node are located at the center of the WRSN. According to Algorithm 2, we firstly apply LKH algorithm to construct a Hamilton tour H through $S$ and $N$ , as shown in Figure 5. Then, based on the decision results returned by Algorithm 1, we greedily split H into 10 schedulable subtours, as shown in Figure 6. It can be found that the tours nearer to the sink cover fewer sensor nodes, because sensor nodes around the sink can be exhausted faster due to larger forwarding burden. Then we call Algorithm 3 to assign these tours to 4 $M C$ s, and each $M C$ applies Algorithm 4 to conduct charging along its assigned tours.

Figure 4

Routing of the 100-node WRSN.

Figure 5

Shortest Hamilton cycle of the 100-node WRSN.

Figure 6

Schedulable subtours to cover the 100-node WRSN.

Figure 7 depicts the energy consumption of each $M C$ when charging along each tour within one charging period, in which the lighter grey part of a bar indicates the energy consumption of charging, while the darker grey part of a bar indicates the energy consumption of moving. The figure shows that the energy consumed in charging along different tours varies greatly. This is because, in the assigning procedure, the GCHA scheme selects T of $R_{1} ~ R_{6}$ nearly the same as their $T^{u}$ , while it selects T of $R_{7} ~ R_{10}$ much smaller than their $T^{u}$ . In consequence, when charging along $R_{7} ~ R_{10}$ , the energy consumption of the $M C$ is much less than $E_{M}$ . In turn, these tours contribute less conflict ratio of the $M C$ , as shown in Figure 8, so that the $M C$ can charge along more tours. The ratio of the grey area in a bar is the conflict ratio of an $M C$ . It can be seen that $M_{4}$ achieves a relatively low conflict ratio. This is caused by the greedy nature of our solution. Balanced energy consumption of $M C$ s, however, is not a concern of this paper.

Figure 7

Energy consumption when charging along each tour.

Figure 8

Conflict ratios of each $M C$ .

6.2. Performance Evaluation

We then compare the number of $M C$ s m obtained by our solution with the lower bound $m^{*}$ to evaluate the performance. Specifically, we evaluate the approximation ratio of our results over the lower bound: $α = m / m^{*}$ .

6.2.1. Varying Charging Power of $M C$ s

The total energy consumption rate of the WRSN shown in Figure 4 is $p_{sum} = 15.24$ W, and the corresponding $m^{*} = ⌈15.24 / 5⌉ = 4$ . Therefore, we actually give an optimum solution in the demonstration, regarding number of $M C$ s used. We further range charging power of the $M C$ s from 3 W to 9 W, and the comparison between m and $m^{*}$ is shown in Figure 9, where z is the number of subtours. It is clear that, in most cases, our method achieves optimum solutions of the MMCP. However, when $q_{c} = 4$ W and $q_{c} = 8$ W, our results are one more than $m^{*}$ . The reason will be explained later.

Figure 9

Results under different charging powers.

6.2.2. Varying Anchored Charging Period

We have explained the reason to anchor $T = T^{u}$ in deriving the TS condition. To verify its effectiveness, we anchor $T = {T^{l}, ((T^{l} + T^{u})) / 4, ((T^{l} + T^{u})) / 2, (3 (T^{l} + T^{u})) / 4, T^{u}}$ and compare the performance of these schemes. We randomly generate 10 200-node WRSNs to test each anchored value of T; the results are shown in Figure 10. The blue stars show the averaged results achieved by the GCHA scheme; the red dots show the mean values of total working time ratios of the $M C$ s. It can be seen that m increases first and then decreases as T increases; m is minimum when $T = T^{u}$ . This is because when T is smaller, each obtained subtour can cover a larger number of sensor nodes; thus the number of tours is smaller; when T is larger, each obtained subtour contributed less conflict ratio of its $M C$ ; thus more tours can be assigned to the same $M C$ . Consequently when anchoring intermediate values of T, the number of obtained tours is relatively large, and these tours are hard to be assigned to the same $M C$ , leading to larger results of m. As for $Φ_{w}$ , it monotonically increases as T increases. According to (10), $T^{w} / T$ of each tour decreases as T increases. Furthermore, as T increases, the influence of the decrease in $T^{w} / T$ is larger than that of the increase in tour numbers. Therefore, anchoring a larger value of T can reduce the total energy consumption of $M C$ s.

Figure 10

Results of anchoring different charging periods.

In conclusion, the results validate the effectiveness of anchoring $T = T^{u}$ in deriving the TS condition.

6.2.3. Varying Network Size

We compare the GCHA scheme with the NMV scheme proposed in [24]. NMV is an on-demand charging scheme. In [24], when the residual lifetime of a sensor node falls in the predefined critical lifetime interval, the sensor node will send an energy-recharging request to $S$ for its energy replenishment. Once $S$ receives the requests from sensor nodes, it performs the NMV scheme to dispatch a number of $M C$ s to charge the requested sensor nodes. To use minimum number of $M C$ s to meet the charging demand, the NMV scheme firstly constructs a minimum-cost spanning tree of the network. Then it decomposes the tree into minimum number of subtrees based on energy constraints of each $M C$ ; each of the subtrees can be assigned to one $M C$ . Then it derives closed charging tours from the subtrees, and the number of the tours equals the number of $M C$ s required. Since the NMV scheme is designed for low-power WRSNs, we let the sensor nodes generate data at a random rate within $[5,30]$ kbps and range n from 100 to 500. With each size of n, we randomly generate 10 WRSNs for evaluation. The results are shown in Figure 11 and Table 1, in which $m^{'}$ is the results achieved by the NMV scheme.

Table 1

Approximation ratios of varying network size.

$n = 100$	$m^{*}$	1	1	1	1	1	2	2	2	2	2	$α = 1.067$
	m	1	1	1	2	2	2	2	2	2	2
	$p_{s u m}$	4.445	4.507	4.617	4.817	4.888	5.055	5.233	5.311	5.340	5.532
	$q_{c} \cdot η \cdot m^{*}$	5	5	5	5	5	10	10	10	10	10
$n = 200$	$m^{*}$	2	2	2	3	3	3	3	3	3	3	$α = 1.074$
	m	2	3	3	3	3	3	3	3	3	3
	$p_{s u m}$	9.397	9.605	9.991	10.122	10.218	10.362	10.399	10.555	11.055	11.073
	$q_{c} \cdot η \cdot m^{*}$	10	10	10	15	15	15	15	15	15	15
$n = 300$	$m^{*}$	3	4	4	4	4	4	4	4	4	4	$α = 1.026$
	m	4	4	4	4	4	4	4	4	4	4
	$p_{s u m}$	14.996	15.107	15.158	15.272	15.508	15.528	15.600	15.617	15.750	15.974
	$q_{c} \cdot η \cdot m^{*}$	15	20	20	20	20	20	20	20	20	20
$n = 400$	$m^{*}$	4	5	5	5	5	5	5	5	5	5	$α = 1.02$ 0
	m	5	5	5	5	5	5	5	5	5	5
	$p_{s u m}$	19.684	20.223	20.723	20.853	21.381	21.461	21.780	21.789	22.054	22.153
	$q_{c} \cdot η \cdot m^{*}$	20	25	25	25	25	25	25	25	25	25
$n = 500$	$m^{*}$	6	6	6	6	6	6	6	6	6	6	$α = 1.017$
	m	6	6	6	6	6	6	6	6	6	7
	$p_{s u m}$	25.765	26.522	26.810	26.810	26.880	27.043	27.044	27.196	27.432	29.071
	$q_{c} \cdot η \cdot m^{*}$	30	30	30	30	30	30	30	30	30	30

Figure 11

Comparison between GCHA and NMV varying network size.

Figure 11 shows that m is very close to $m^{*}$ and much smaller than $m^{'}$ . On average, the ratio of $m / m^{'}$ is less than 0.5. There are two main reasons that the NMV scheme uses much more $M C$ s than the GCHA scheme. (a) The NMV scheme is an on-demand charging scheme; it happens that a large number of sensor nodes are running out of energy; thus many $M C$ s are required for charging in these situations. While $M C$ s applying the GCHA scheme charge the sensor nodes periodically, thus such situations never occur. (b) Due to aforementioned reason, many $M C$ s applying the NMV scheme are idle in most cases, causing great waste of resources, while, in the GCHA scheme, charging ability of each $M C$ is fully utilized, by assigning to it as many tours as possible.

To analyze when does the GCHA scheme use more $M C$ s than the lower bound, we list the detailed results in Table 1. The inconsistent situations are bold. Although, in most cases, $m = m^{*}$ , in situations where $q_{c} \cdot η \cdot m^{*}$ is very close to $p_{sum}$ , $m - m^{*} = 1$ . This is because the lower bound $m^{*}$ only relates to the total energy consumption rate of a WRSN and the charging power of each $M C$ . In fact, the $M C$ s also spend energy and time in moving. Therefore, if the total charging power of $M C$ s is not significantly larger than the total energy consumption rate of the WRSN, $m^{*}$ may not be achievable, even though, according to the results, the average approximation ratio of our results is below 1.1 compared with the lower bound $m^{*}$ .

7. Conclusion and Future Work

In this paper, we exploit the Minimum Mobile Chargers Problem (MMCP) in Wireless Rechargeable Sensor Networks. We divide the problem into two NP-hard subproblems: the Tour Construction Problem (TCP) and the Tour Assignment Problem (TAP). We propose the Greedily Construct, Heuristically Assign (GCHA) scheme to solve the problems. The GCHA scheme firstly constructs the shortest Hamilton cycle through all nodes in a WRSN. Then, based on the Tour Schedulable (TS) condition, it greedily splits the cycle into schedulable subtours. Subsequently, these subtours are heuristically assigned to minimum number of $M C$ s, so that the $M C$ s can apply the Greedy Charging Scheme (GCS) to charge along their assigned tours. The computation complexity of the GCHA scheme is $O (n^{2.2})$ , which can be further reduced by applying a simpler TSP solution. Simulations are conducted to evaluate the performance of our solution. Numerical results show that the GCHA scheme only uses less than half of the $M C$ s that are required by the NMV scheme. In most scenarios, our method generates optimum solutions for MMCP. Compared with the Lower Bound $m^{*}$ , our method achieved an approximation ratio less than 1.1.

Future work includes the following aspects. (a) We will develop a more rigorous lower bound of MMCP, taking movement of $M C$ s into consideration. Consequently, the approximation ratio of our method will be theoretically analyzed. (b) The energy efficiency of $M C$ s can be improved by carefully merging traveling paths of some tours. (c) Load balance between $M C$ s will be studied.

Footnotes

Notations

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors sincerely thank the anonymous reviewers for their valuable comments that led to the present improved version of the original paper. This research work is partially supported by the NSF of China under Grant no. 60973122, the 973 Program in China, and the Scientific Research Foundation of Graduate School of Southeast University.

References

Anastasi

Conti

Di Francesco

Passarella

Energy conservation in wireless sensor networks: a survey

Ad Hoc Networks 2009 7 3 537 568

10.1016/j.adhoc.2008.06.003

2-s2.0-56449087483

Howard

Mataríc

M. J.

Sukhatme

G. S.

An incremental self-deployment algorithm for mobile sensor networks

Autonomous Robots 2002 13 2 113 126

10.1023/A:1019625207705

ZBL1012.68654

2-s2.0-0036736383

Sudevalayam

Kulkarni

Energy harvesting sensor nodes: survey and implications

IEEE Communications Surveys and Tutorials 2011 13 3 443 461

10.1109/surv.2011.060710.00094

2-s2.0-79959289243

Xie

Shi

Hou

Y. T.

Lou

Wireless power transfer and applications to sensor networks

IEEE Wireless Communications 2013 20 4 140 145

10.1109/mwc.2013.6590061

2-s2.0-84884572770

Kurs

Karalis

Moffatt

Joannopoulos

J. D.

Fisher

Soljačić

Wireless power transfer via strongly coupled magnetic resonances

Science 2007 317 5834 83 86

10.1126/science.1143254

MR2335122

2-s2.0-34447309715

Erol-Kantarci

Mouftah

H. T.

Suresense: sustainable wireless rechargeable sensor networks for the smart grid

IEEE Wireless Communications 2012 19 3 30 36

10.1109/mwc.2012.6231157

2-s2.0-84863741191

Griffin

Detweiler

Resonant wireless power transfer to ground sensors from a UAV

Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '12)

May 2012

2660 2665

10.1109/icra.2012.6225205

2-s2.0-84864479907

Dai

H. P.

X. B.

L. J.

Chen

Lin

Using minimum mobile chargers to keep large-scale wireless rechargeable sensor networks running forever

Proceedings of the IEEE 2013 22nd International Conference on Computer Communication and Networks (ICCCN '13)

August 2013

1 7

10.1109/icccn.2013.6614207

2-s2.0-84891456902

Nagarajan

Ravi

Approximation algorithms for distance constrained vehicle routing problems

Networks 2012 59 2 209 214

10.1002/net.20435

MR2880234

2-s2.0-84856877166

10.

Xie

Shi

Hou

Y. T.

Sherali

H. D.

Making sensor networks immortal: an energy-renewal approach with wireless power transfer

IEEE/ACM Transactions on Networking 2012 20 6 1748 1761

10.1109/tnet.2012.2185831

2-s2.0-84857126297

11.

Peng

Zhang

Prolonging sensor network lifetime through wireless charging

Proceedings of the IEEE 31st Real-Time Systems Symposium (RTSS '10)

November-December 2010

San Diego, Calif, USA

129 139

10.1109/RTSS.2010.35

12.

Wang

Zhou

Make imbalance useful: an energy-efficient charging scheme in wireless sensor networks

Proceedings of the International Conference on Pervasive Computing and Application (ICPCA '13)

December 2013

160 171

13.

Pan

Zhu

On-demand charging in wireless sensor networks: theories and applications

Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS '13

October 2013

Hangzhou, China

IEEE

28 36

10.1109/mass.2013.51

2-s2.0-84893314830

14.

Wang

Yang

Y. Y.

Stochastic mobile energy replenishment and adaptive sensor activation for perpetual wireless rechargeable sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '13)

April 2013

974 979

10.1109/wcnc.2013.6554696

2-s2.0-84881595989

15.

Zhao

Yang

Y. Y.

Joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks

Proceedings of the 23rd International Teletraffic Congress (ITC '11)

2011

238 245

16.

Guo

S. T.

Wang

Yang

Y. Y.

Mobile data gathering with wireless energy replenishment in rechargeable sensor networks

Proceedings of the 32nd IEEE Conference on Computer Communications (IEEE INFOCOM '13)

April 2013

1932 1940

10.1109/infcom.2013.6566993

2-s2.0-84883091846

17.

Shi

Han

J. H.

Han

Ding

Wei

The dynamic routing algorithm for renewable wireless sensor networks with wireless power transfer

Computer Networks 2014 74 34 52

18.

Kurs

Moffatt

Soljačić

Simultaneous mid-range power transfer to multiple devices

Applied Physics Letters 2010 96 4

044102

10.1063/1.3284651

2-s2.0-75749089557

19.

Tong

Wang

G. L.

Zhang

How wireless power charging technology affects sensor network deployment and routing

Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS '10)

June 2010

Genoa, Italy

IEEE

438 447

10.1109/icdcs.2010.61

2-s2.0-77955869152

20.

Xie

Shi

Hou

Y. T.

Lou

Sherali

H. D.

Midkiff

S. F.

On renewable sensor networks with wireless energy transfer: the multi-node case

Proceedings of the 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON '12)

June 2012

10 18

10.1109/secon.2012.6275766

2-s2.0-84867922457

21.

Luan

Shen

C.-C.

Qi-ferry: energy-constrained wireless charging in wireless sensor networks

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '12)

April 2012

2515 2520

10.1109/wcnc.2012.6214221

2-s2.0-84864334769

22.

L. K.

Cheng

Chen

Minimizing charging delay in wireless rechargeable sensor networks

Proceedings of the 32nd IEEE Conference on Computer Communications (IEEE INFOCOM '13)

April 2013

2922 2930

10.1109/infcom.2013.6567103

2-s2.0-84883080417

23.

Zhang

S. L.

Collaborative mobile charging for sensor networks

Proceedings of the IEEE 9th International Conference on Mobile Adhoc and Sensor Systems (MASS '12)

2012

84 92

24.

Liang

W. F.

W. Z.

Ren

X. J.

Jia

Lin

Maintaining sensor networks perpetually via wireless recharging mobile vehicles

Proceedings of the IEEE 39th Conference on Local Computer Networks (LCN '14)

September 2014

Edmonton, Canada

270 278

10.1109/LCN.2014.6925781

25.

Wang

Minimizing the number of mobile chargers in a large-scale wireless rechargeable sensor network

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '15)

March 2015

New Orleans, La, USA

26.

Wang

Schedulability decision of charging missions in wireless rechargeable sensor networks

Proceedings of the 11th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON '14)

June 2014

Singapore

450 458

10.1109/sahcn.2014.6990383

27.

Helsgaun

An effective implementation of the Lin-Kernighan traveling salesman heuristic

European Journal of Operational Research 2000 126 1 106 130

10.1016/S0377-2217(99)00284-2

MR1781609

ZBL0969.90073

2-s2.0-0034301999

28.

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MobiCom '00)

2000

243 254

Minimizing the Number of Mobile Chargers to Keep Large-Scale WRSNs Working Perpetually

Abstract

1. Introduction

2. Related Work

3. System Model and Problem Formulation

4. The Tour Construction Problem

4.1. The Greedy Charging Scheme

4.2. Deriving the Decision Condition

Algorithm 1: Decide whether an M C can charge along R.

4.3. Obtaining Schedulable Subtours

Algorithm 2: Construct a Hamilton tour H through S and N ; split H into z schedulable subtours.

5. The Tour Assignment Problem

5.1. The Tour Assignment Problem

Proposition 1.

Proof.

Proposition 2.

Proof.

5.2. The Heuristic Solution

Proposition 3.

Proof.

Proposition 4.

Proof.

Proposition 5.

Proof.

Algorithm 3: Sort tours R by T u ; greedily assign the tours to minimum M C s based on Propositions 4 and 5.

Algorithm 4: Construct a valid charging schedule of M k along its assigned tours R k .

5.3. The Complete Procedure of the GCHA Solution

6. Numerical Results

6.1. Demonstration of the GCHA Solution

6.2. Performance Evaluation

6.2.1. Varying Charging Power of M C s

6.2.2. Varying Anchored Charging Period

6.2.3. Varying Network Size

7. Conclusion and Future Work

Footnotes

Notations

Conflict of Interests

Acknowledgments

References

Algorithm 1: Decide whether an $M C$ can charge along R.

Algorithm 2: Construct a Hamilton tour H through $S$ and $N$ ; split H into z schedulable subtours.

Algorithm 3: Sort tours $R$ by $T^{u}$ ; greedily assign the tours to minimum $M C$ s based on Propositions 4 and 5.

Algorithm 4: Construct a valid charging schedule of $M_{k}$ along its assigned tours $R_{k}$ .

6.2.1. Varying Charging Power of $M C$ s