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

Authors: Cheng Hu; Yun Wang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Wireless Rechargeable Sensor Networks, in whichmobile chargers (MCs) are employed to recharge the sensor nodes, have attracted wide attention in recent years. Under proper charging schedules, the MCs could keep all the sensor nodes working perpetually. Since MCs can be very expensive, this paper tackles the problem of deciding the minimum number of MCs 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 MC 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 MCs. Then each of the MCs can apply the GCS to charge along its assigned tours. Simulation results show that, on average, the number of MCs obtained by the GCHA scheme is less than 1.1 over a derived lower bound and less than 0.5 over related work.


---

## Body

## 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 tomagnetic resonant coupling [5] in this paper, a new paradigm ofWireless Rechargeable Sensor Networks (WRSNs) is proposed and immediately received wide attention. In WRSNs,mobile chargers (MCs) with high volume batteries are employed to replenish the depleted energy of rechargeable sensor nodes. The batteries of the MCs can be quickly renewed at aservice 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 oneMC to conduct charging. However, an open issue in these works is their poor scalability. Even when the MC 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 MCs are employed to address the problem.Since anMC can be very expensive, the first and foremost issue in designing a WRSN with multiple MCs is to decide the minimum number of MCs required, so that no sensor node will die. This problem, namedMinimum Mobile Chargers Problem (MMCP) [8], is closely related to theDistance-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 MCs 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 MC can conduct charging on several tours.To demonstrate this viewpoint, consider a demo WRSN shown in Figure1, 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 MCs, any MC 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 4t; then only one MC is required: the MC charges along tour Ri during time [(4k+i-1)·t,(4k+i)·t] (1≤i≤4, k=0,1,2,…). 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, aTour Construction Problem (TCP) and aTour 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 MCs, 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 ofMCs 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 oneMC 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 theGreedy Charging Scheme (GCS, first proposed in [10]).(iii)
We propose a heuristic algorithm to assign a set of schedulable tours to minimum number ofMCs. The developed heuristic rules can minimize the conflict ratio of an MC, 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. Section2 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 oneMC 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 MC 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 MC. 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 MC’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 MC 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 MC by heuristic solutions. Fu et al. [22] planned the optimal movement strategy of the MC, 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 theMC. Therefore, multiple MCs are required to serve large-scale WRSNs. Dai et al. [8] studied the problem of minimizing the number of energy-constrained MCs 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 MCs with limited energy to charge a one-dimensional WRSN. They assumed that energy can be transferred among MCs with 100% efficiency and then proposed collaborative approaches to maximize the energy efficiency of the MCs. 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 multipleMCs to accomplish the charging mission in a WRSN, so that scalability problem can be settled. Literature [23] assumes 100% charging efficiency of MCs 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 MCs in a 2D WRSN, where MCs 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 MCs 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 nodesN={N1,N2,…,Nn} and MCs  M={M1,M2,…,Mm}. Each sensor node Ni (1≤i≤n) has a battery with capacity ES and consumes energy at a constant rate pi (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 MC. 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 theMCs can move freely in the WRSN at a constant speed v, without any constraint of movement tracks. The energy consumed by each MC for moving per meter is a constant qm. The MCs record the positions of all sensor nodes and can wirelessly charge the sensor nodes at a power rate qc with efficiency η. Suppose that each MC can only charge one sensor node at the same time. Since η drops rapidly as the charging distance increases, we let the MCs move to each sensor node to conduct charging. Consequently, qc and η are viewed as constants. Charging and moving activities of each MC are powered by the same battery with volume EM, which can be renewed at a service station S in an infinitely short period. To simplify the presentation, S is also denoted by N0.Thecharging mission in a WRSN is to schedule the charging activities of the MCs to ensure that all sensor nodes will never exhaust their energy. An MC 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 MCs periodically charge sensor nodes along a set oftoursR={R1,R2,…,Rz}. Define that Mk can charge along a set of tours Rk={R1,R2,…,Rzk} if Mk can ensure liveness of all the sensor nodes in Rk; then each of the tours is calledschedulable, and these tours can beassigned toMk. Suppose that all tours are independently charged along; that is, each MC must finish charging along one tour before it charges along the next. Acharging schedule determines when do the MCs charge which sensor nodes in what sequence and for how long. A charging schedule is calledvalid if it can be applied to accomplish the charging mission.TourRi=N0,N1,…,Nri determines an MC’s charging sequence of the ri sensor nodes. Obviously, the union of the sensor nodes in tours R should fully cover the WRSN:(1)⋃i=1zRi=N∪S.An MC periodically charges along tour Ri withcharging periodTi (1≤i≤z). As will be proved in Section 4, Ti of tour Ri ranges in a feasible region [Til,Tiu]. Assume that Ti is rational. Within each charging period Ti, the total time an MC spends in moving and charging states is called theworking time of Ri, denoted by Tiw (Tiw≤Ti). Consequently, we also use a tuple (Ti,Tiw) to substitute for Ri. However, if the charging period of Ri has not been determined, the tour can be denoted by a triple (Til,Tiu,ωi), where ωi is a working time function dependent on Ti. The three representations of Ri will be used interchangeably in the rest of the paper, where no ambiguity occurs.Supposezk tours Rk={R1,R2,…,Rzk} are assigned to Mk (1≤zk≤z); then we define theelement period of Mk, denoted by Gk, as the greatest common divisor of charging periods of these zk tours. Define theconflict ratio of Mk as(2)δk=∑i=1zkTiwGk,Gk=GCDT1,T2,…,Tzk,where function GCD(·) returns the greatest common divisor of the given numbers. Informally speaking, δk indicates the maximum work load of Mk within any element period Gk; during Gk, Mk charges along Ri∈Rk for at most once. We will prove that if δi of Mi is no more than 1, a valid charging schedule of charging along these k tours can be easily constructed. For instance, in Figure 2, R1=(7.5,1) and R2=(5,1.5) can be assigned to one MC. Because the element period of the MC is G=GCD(T1,T2)=GCD(7.5,5)=2.5, the conflict ratio of the MC is δ=T1w+T2w/G=1+1.5/2.5=1.Figure 2
AssigningR1 an R2 to one MC.Then the problem addressed in this paper can be formulated as follows.Minimum Mobile Chargers Problem (MMCP). Given n sensor nodes N={Ni(pi,ES)∣1≤i≤n} and their positions in a WRSN, decide the minimum size m of M={Mi(qc,qm,v,EM)∣1≤i≤m} to accomplish the charging mission.When obtaining the minimum number ofMCs, 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 MCs. Each MC 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 inR 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:(3)Ri∩Rj=⌀,Ri,Rj∈R,Ni≠Nj,Ni,Nj∈Rk,Rk∈R.Then we propose and address the following problem.Tour Construction Problem (TCP). Given n sensor nodes N={Ni(pi,ES)∣1≤i≤n} and their positions in a WRSN, construct minimum number of tours R, schedulable to MCs (qc,qm,v,EM), 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·ES→0; then the TCP can be reduced to a DVRP with distance constraint EM/qm. To address the TCP, we firstly propose a sufficient condition for an MC to be able to charge along a tour. The condition is derived from aGreedy 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 tourR=N0,N1,…,Nr (1≤r≤n), an M∈M applies the GCS as follows. In each period, M starts from N0, sequentially fully charges each sensor node, then returns to N0, quickly renews its battery, and rests until next period. Denote that M arrives at Ni at time ti and charges Ni for time τi; then we have(4)ti=∑j=0i-1τj+∑j=1idj-1,jv,1≤i≤r.In (4), di,j is the distance between Ni and Nj and τ0≥0 is the duration that M rests at S, and let t0=0 to simplify the presentation. Then M can periodically charge along R with charging period(5)T=∑j=0rτj+Dv,where D=∑j=1rdj-1,j+dr,0 is the total traveling distance of the tour. Then, within each charging period, the energy consumed by Ni can be fully replenished by M; that is,(6)τi·qc·η=pi·T,1≤i≤r.To ensure the sensor nodes are working continuously, their energy levels should never fall below 0 during T; that is,(7)ES-pi·T-τi≥0,1≤i≤r.Meanwhile, the total energy of M should be enough to conduct charging; that is,(8)D·qm+∑j=1r·qc·τj≤EM.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, namedTour Schedulable (TS) condition, can be used to construct schedulable tours to exactly 1-cover the WRSN.Equation (6) can be rewritten as(9)τi=pi·Tqc·η,1≤i≤r.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:(10)Tw=∑i=1nτi+Dv=psumqc·η·T+Dv.Obviously, Tw increases as T increases; however, Tw/T decreases as T increases. Literature [12] presented that Tw/T indicates the total energy consumption of M in charging along R; thus it should be minimized. Plugging (9) into (5) we have(11)T=τ0+∑i=1rpi·Tqc·η+Dv≥∑i=1rpi·Tqc·η+Dv,or, equivalently,(12)T≥D·qc·ηv·qc·η-psum,psum=∑i=1rpi.Let Tl=D·qc·η/v·(qc·η-psum); then feasible charging period of tour R cannot be less than Tl; 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: qc·η>psum.Plugging (9) into (7) we have(13)ES≥pi·qc·η-piqc·η·T,1≤i≤r.Since qc·η>psum>pi, the inequality is equal to(14)T≤Es·qc·ηpmx,pmx=max1≤i≤r⁡pi·qc·η-pi.Let Tu=Es·qc·η/pmx; then feasible charging period of R cannot exceed Tu, or some sensor node will run out of energy before it is charged. Combining (12) and (14) we have(15)D·qc·ηv·qc·η-psum≤Es·qc·ηpmxor, equivalently, v≥D·pmx/ES·(qc·η-psum), which is also a necessary condition for R to have feasible charging period. Plugging (9) into (8) we have(16)EM≥D·qm+psumη·T.Formula (16) shows the minimum energy required for an MC to charge along R with charging period T. Let T=Tu; we have EM≥ES·qc·psum/pmx+D·qm. By now, we have derived a sufficient condition for M to charge along R.TS Condition. An MC applying the GCS can charge along tour R=N0,N1,…,Nr if (a) qc·η>psum; (b) v≥D·pmx/ES·(qc·η-psum); (c) EM≥D·qm+psum·ES·qc/pmx.Note that in deriving the TS condition, we letT=Tu to decide the minimum energy requirement of an MC. One can set other feasible T to derive a new sufficient condition, or sayanchoring other values of T for short. In the next section, however, we will show that anchoring T=Tu can minimize the total energy consumption of the MCs, as well as the conflict ratio it generated.Although the TS condition is not necessary for a tour to be schedulable [26], qc·η>psum is a hard condition for any MC 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 MCs needed to solve the MMCP.Lower Bound
m
∗
. Given n sensor nodes N={Ni(pi,ES)∣1≤i≤n} and their positions in a WRSN, the minimum number of MCs (qc,qm,v,EM) needed to accomplish the charging mission is not less than m∗=∑i=1npi/qc·η.The lower boundm∗ is not tight, since it only considers the influence of charging. Obviously, an MC 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 Algorithm1 to decide whether a tour can be assigned to an MC (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 MC can charge along R.
Require:
R = N0,N1,…,Nr,  ES, qm, qc, v, EM, η;
Ensure:
Schedulability ofR; (Tl, Tu, ω).
(1)  calculate path length D of R;
(2)  inquire energy consumption rates {pi} of the sensor nodes in R;
(3) psum=∑i=1rpi;
(4) pmx=max1≤i≤r⁡pi⋅(qc⋅η-pi);
(5) if the conditions in Proposition 2 are not satisfied then
(6)  return unschedulable;
(7) end if
(8) Tl=D⋅qc⋅ηv⋅(qc⋅η-psum);
(9) Tu=Es⋅qc⋅ηpmx;
(10) ω(T)=psumqc⋅η⋅T+Dv;
(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 Algorithm2. First, we construct a Hamilton tour H through S and N by applying LKH algorithm [27] (lines (2)-(3)). Then we replace edges ei,i+1 and ej,j+1 by e0,i+1 and ej,0 (lines (5), (7)) and decide whether an MC can charge along tour N0,Ni+1,…,Nj 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 psum and pmx 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(n2.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 MCs is similar to an on-demand charging scheme using one MC. 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={Ni∣1≤i≤n};
Ensure:
R={Ri∣1≤i≤z};
(1)  z=1,i=1;
(2)  apply LKH on S∪N to obtain H;
(3)  renumber sensor nodes in H as N0,N1,…,Nn (N0=S);
(4)    while  i≤n  do
(5)     push N0 into Rz;
(6)     for  j=i  to  n  do
(7)      push Nj into Rz;
(8)      apply Algorithm 1 to decide the schedulability of Rz;
(9)      if  Rz is unschedulable  then
(10)      pop Nj from Rz;
(11)      i=j,z=z+1;
(12)      break;
(13)    end if
(14)   end for
(15) end whileFigure 3
Demonstration of the tour construction algorithm.


## 4.1. The Greedy Charging Scheme

When charging along a tourR=N0,N1,…,Nr (1≤r≤n), an M∈M applies the GCS as follows. In each period, M starts from N0, sequentially fully charges each sensor node, then returns to N0, quickly renews its battery, and rests until next period. Denote that M arrives at Ni at time ti and charges Ni for time τi; then we have(4)ti=∑j=0i-1τj+∑j=1idj-1,jv,1≤i≤r.In (4), di,j is the distance between Ni and Nj and τ0≥0 is the duration that M rests at S, and let t0=0 to simplify the presentation. Then M can periodically charge along R with charging period(5)T=∑j=0rτj+Dv,where D=∑j=1rdj-1,j+dr,0 is the total traveling distance of the tour. Then, within each charging period, the energy consumed by Ni can be fully replenished by M; that is,(6)τi·qc·η=pi·T,1≤i≤r.To ensure the sensor nodes are working continuously, their energy levels should never fall below 0 during T; that is,(7)ES-pi·T-τi≥0,1≤i≤r.Meanwhile, the total energy of M should be enough to conduct charging; that is,(8)D·qm+∑j=1r·qc·τj≤EM.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, namedTour Schedulable (TS) condition, can be used to construct schedulable tours to exactly 1-cover the WRSN.Equation (6) can be rewritten as(9)τi=pi·Tqc·η,1≤i≤r.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:(10)Tw=∑i=1nτi+Dv=psumqc·η·T+Dv.Obviously, Tw increases as T increases; however, Tw/T decreases as T increases. Literature [12] presented that Tw/T indicates the total energy consumption of M in charging along R; thus it should be minimized. Plugging (9) into (5) we have(11)T=τ0+∑i=1rpi·Tqc·η+Dv≥∑i=1rpi·Tqc·η+Dv,or, equivalently,(12)T≥D·qc·ηv·qc·η-psum,psum=∑i=1rpi.Let Tl=D·qc·η/v·(qc·η-psum); then feasible charging period of tour R cannot be less than Tl; 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: qc·η>psum.Plugging (9) into (7) we have(13)ES≥pi·qc·η-piqc·η·T,1≤i≤r.Since qc·η>psum>pi, the inequality is equal to(14)T≤Es·qc·ηpmx,pmx=max1≤i≤r⁡pi·qc·η-pi.Let Tu=Es·qc·η/pmx; then feasible charging period of R cannot exceed Tu, or some sensor node will run out of energy before it is charged. Combining (12) and (14) we have(15)D·qc·ηv·qc·η-psum≤Es·qc·ηpmxor, equivalently, v≥D·pmx/ES·(qc·η-psum), which is also a necessary condition for R to have feasible charging period. Plugging (9) into (8) we have(16)EM≥D·qm+psumη·T.Formula (16) shows the minimum energy required for an MC to charge along R with charging period T. Let T=Tu; we have EM≥ES·qc·psum/pmx+D·qm. By now, we have derived a sufficient condition for M to charge along R.TS Condition. An MC applying the GCS can charge along tour R=N0,N1,…,Nr if (a) qc·η>psum; (b) v≥D·pmx/ES·(qc·η-psum); (c) EM≥D·qm+psum·ES·qc/pmx.Note that in deriving the TS condition, we letT=Tu to decide the minimum energy requirement of an MC. One can set other feasible T to derive a new sufficient condition, or sayanchoring other values of T for short. In the next section, however, we will show that anchoring T=Tu can minimize the total energy consumption of the MCs, as well as the conflict ratio it generated.Although the TS condition is not necessary for a tour to be schedulable [26], qc·η>psum is a hard condition for any MC 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 MCs needed to solve the MMCP.Lower Bound
m
∗
. Given n sensor nodes N={Ni(pi,ES)∣1≤i≤n} and their positions in a WRSN, the minimum number of MCs (qc,qm,v,EM) needed to accomplish the charging mission is not less than m∗=∑i=1npi/qc·η.The lower boundm∗ is not tight, since it only considers the influence of charging. Obviously, an MC 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 Algorithm1 to decide whether a tour can be assigned to an MC (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 MC can charge along R.
Require:
R = N0,N1,…,Nr,  ES, qm, qc, v, EM, η;
Ensure:
Schedulability ofR; (Tl, Tu, ω).
(1)  calculate path length D of R;
(2)  inquire energy consumption rates {pi} of the sensor nodes in R;
(3) psum=∑i=1rpi;
(4) pmx=max1≤i≤r⁡pi⋅(qc⋅η-pi);
(5) if the conditions in Proposition 2 are not satisfied then
(6)  return unschedulable;
(7) end if
(8) Tl=D⋅qc⋅ηv⋅(qc⋅η-psum);
(9) Tu=Es⋅qc⋅ηpmx;
(10) ω(T)=psumqc⋅η⋅T+Dv;
(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 Algorithm2. First, we construct a Hamilton tour H through S and N by applying LKH algorithm [27] (lines (2)-(3)). Then we replace edges ei,i+1 and ej,j+1 by e0,i+1 and ej,0 (lines (5), (7)) and decide whether an MC can charge along tour N0,Ni+1,…,Nj 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 psum and pmx 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(n2.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 MCs is similar to an on-demand charging scheme using one MC. 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={Ni∣1≤i≤n};
Ensure:
R={Ri∣1≤i≤z};
(1)  z=1,i=1;
(2)  apply LKH on S∪N to obtain H;
(3)  renumber sensor nodes in H as N0,N1,…,Nn (N0=S);
(4)    while  i≤n  do
(5)     push N0 into Rz;
(6)     for  j=i  to  n  do
(7)      push Nj into Rz;
(8)      apply Algorithm 1 to decide the schedulability of Rz;
(9)      if  Rz is unschedulable  then
(10)      pop Nj from Rz;
(11)      i=j,z=z+1;
(12)      break;
(13)    end if
(14)   end for
(15) end whileFigure 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 ofMCs. To this end, we firstly formulate theTour 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 periodTi of tour Ri ranges from Til to Tiu, which also decides the working time Tiw of Ri in each period: Tiw=ωi(Ti)=psumi/qc·η·Ti+Di/v. Then the assignment problem can be formulated as follows.Tour Assignment Problem (TAP). Given z tours R={Ri=(Til,Tiu,ωi)∣1≤i≤z} and enough MCs (qc,qm,v,EM), assign tours R to minimum number of MCs.To prove the NP-hardness of the TAP, we firstly considerr tours with equal charging period T and investigate the sufficient and necessary condition of assigning these r tours to one MC.Proposition 1.
Givenr tours {Ri=(T,Tiw)∣1≤i≤r}, they can be assigned to one MC if and only if ∑i=1rTiw≤T.Proof.
Suppose thesek tours can be assigned to the same MC; then ∑i=1rTiw≤T. Otherwise the MC cannot finish charging along all tours within one charging period T, causing conflicts in the next period.
On the other hand, if∑i=1rTiw≤T, one can construct a valid schedule as follows. The MC charges sensor nodes in Ri during time [k·T+∑j=1i-1Tjw,k·T+∑j=1iTjw] (k=0,1,2,…). Since ∑i=1rTiw≤T, this schedule is valid.
Therefore, the proposition follows.Based on Proposition1, 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 whetherz tours can be assigned to m  MCs is NP-hard.Proof.
Considerz tours {Ri=(T,Tiw)∣1≤i≤z}, and suppose ∑i=1zTiw=2T. Let m=2; then the decision problem can be reformulated as whether {Ri} can be assigned to 2 MCs.
We now construct a set-partition problem as follows. Givenz numbers {a1,a2,…,az}, in which ai=Tiw/T (1≤i≤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 oneMC.We firstly generalize the assumption in Proposition1 and assume that tours have different charging periods. Then we derive a necessary condition for these tours to be assigned to the same MC. Suppose that the periods of all tours are rational numbers and their greatest common divisor is G (Gcan be a decimal); then we have the following proposition.Proposition 3.
Givenk set of tours: {Rij=(aj·G,Tij)∣1≤i≤rj,1≤j≤k}, where Rij is the ith tour of the jth set and {aj} are coprime integers, these tours can be assigned to one MC only if ∑j=1k∑i=1rjTij/aj≤G.Proof.
Suppose these tours can be assigned to oneMC, while ∑j=1k∑i=1rjTij/aj>G. Denote the least common multiple of a1,a2,…,ak by P. Multiplying both sides of the inequality by P, we have(17)Pa1·∑i=1r1Ti1+Pa2·∑i=1r2Ti2+⋯+Pak·∑i=1rkTik>G·P,where P/aj means how many times does the MC charge along tours {Rij} during G·P and ∑i=1rjTij is the total working time of the jth set of tours within each charging period aj·G. It means that the total working time of all the tours during G·P is larger than G·P, which is a contradiction.
Therefore, the proposition follows.Unfortunately, the condition is not sufficient, because it requires that thejth set of tours can be evenly partitioned into aj 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 {2T,2T/3}, {2T,T/3}, and {T,T/2} cannot be charged by one MC even if they satisfy Proposition 3. Besides, deciding whether the jth set of tours can be evenly partitioned into aj 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 MC.Proposition 4.
Givenr tours {Ri=(ai·G,Tiw)∣1≤i≤r}, where {ai} are coprime integers, they can be assigned to one MC if ∑i=1rTiw≤G.Proof.
Considerr tours {Ri′=(G,Tiw)∣1≤i≤r}; if they can be assigned to one MC, obviously {Ri} can be assigned to the same MC. Since ∑i=1rTiw≤G, according to Proposition 3, {Ri′} can be assigned to one MC. Therefore, {Ri} can be assigned to one MC.Note that Proposition4 is not necessary. For instance, consider tour RA=(T,T/2) and r tours {RiB=(r·T,T/2)∣r>1,1≤i≤r}. Since GCD(T,r·T)=T, and the total working time of the r+1 tours is (r+1)/2·T>T, the condition in Proposition 4 is not met. However, one can still assign them to one MC: let the MC charge along tour RA during time [j·T,(j+1/2)·T] and charge along tour RiB during time [(j·r+i-1/2)·T,(j·r+i)·T], j=0,1,2,…. It can be readily proved that the charging schedule is valid.Proposition4 inspires us to minimize the conflict ratio of each MC: δ=∑i=1rTiw/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 toursR1=(T1l,T1u,ω1) and R2=(T2l,T2u,ω2) are assigned to M, where (k-1)·T1u<T2l≤k·T1u≤T2u (k≥1); then the conflict ratio δ of M is minimized when T1=T1u and T2=k·T1u.Proof.
For each tourRi, ω(Ti)=psumi/qc·η·Ti+Di/v. To simplify the presentation, denote that ω(Ti)=ai·Ti+bi.
Considerδ when T2 varies within time interval [i·T1,(i+1)·T1] (i=1,2,…):(18)δ1=a1+i·a2+b1+b2T1,T2=i·T1,δ2=a1+i+1·a2+b1+b2T1,T2=i+1·T1,δ3=a1·T1+a2·T2G+b1+b2G,i·T1<T2<i+1·T1,where G=GCD(T1,T2). When i·T1<T2<(i+1)·T1, G≤T1/2, we hence have(19)δ3=a1·T1+a2·T2G+b1+b2G≥2a1+2i·a2+2b1+b2T1>a1+i+1·a2+b1+b2T1=δ2.In other words, δ1<δ2<δ3. Therefore, in this scenario, δ is minimized when T2=i·T1. Then δ=a1+i·a2+b1+b2/T1.
On the other hand,δ decreases as T1 increases. To minimize δ, we have T1=T1u. Since (k-1)·T1u<T2l≤k·T1u≤T2u, we have i=k; that is, T2=k·T1u.
In summary,δ is minimized when T1=T1u and T2=k·T1u; then the proposition follows.In fact, Proposition5 requires the element period G of M to be maximized. This is an important reason that we anchor T=Tu when deriving the TS condition. Note that one can set T=T′ (Tl≤T′<Tu) 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 MC according to Proposition 5. More importantly, anchoring smaller value of T will increase the total working time ratio (denoted by Φw) of the MCs:(20)Φw=∑i=1m∑j=1ziTjwTj=∑i=1zTiwTi.We have proved in [12] that the working time ratio of an MC indicates the total energy consumption of the MC in conducting charging. Therefore, Φw indicates the total energy consumption of all the MCs. Based on the above two reasons, we anchor T=Tu in deriving the TS condition. Comparisons of anchoring different values of T are made through simulations.Based on the heuristic rules formulated in Propositions4 and 5, we propose Algorithm 3 to greedily assign maximum number of tours to each MC. First, the tours obtained by Algorithm 2 are sorted by Tu in ascending order (line (2)). Then, for each MC, sequentially consider if tour Ri can be assigned to it (lines (3)–(18)). According to Proposition 5, the element period Gk of Mk is set to Tiu of its first assigned tour Ri (line (7)). For any subsequent tour Rj, it is assigned to Mk (lines (6), (13)) if(a)
Rj has not been assigned to any MC (lines (4), (9)),(b)
feasible period ofRj contains a multiple of Gk (lines (10)-(11)),(c)
after assigning, the conflict ratioδk of Mk is still no more than 1 (line (11)).Then charging period Tj of Rj 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(z2), where z is the number of tours.Algorithm 3:Sort tours R by Tu; greedily assign the tours to minimum MCs based on Propositions 4 and 5.
Require:
R={Ri∣1≤i≤z};
Ensure:
M={Mi∣1≤i≤m}, tour assignment of each MC;
(1)    m=0;
(2)    sort {Ri} by Tiu in ascending order;
(3)    for  i=1  to  z  do
(4)       if  Ri has not been assigned  then
(5)        m+=1;
(6)        assign Ri to Mm;
(7)        Gm=Ti=Tiu,  δm=ωiTiGm;
(8)        for  j=i+1  to  z  do
(9)        if  Rj has not been assigned  then
(10)        calculate the k described in Proposition 5;
(11)        if  k exists  and  δm+(ωjk⋅Tiu/Gm)≤1  then
(12)         Tj=k⋅Tiu,  δm+=ωjTjGm;
(13)         assign Rj to Mm;
(14)        end if
(15)     end if
(16)     end for
(17)     end if
(18) end forAfter tour assignment, eachMC applies the GCS to periodically charge along its assigned tours. Suppose zx tours Rx={Ri=(ai·Gx,Tiw)} are assigned to Mx (1≤i≤zx≤n, 1≤x≤m); then a valid charging schedule is that Mx charges Ri during time [k·ai·Gx+∑j=1i-1Tjw,k·ai·Gx+∑j=1iTjw] (k=0,1,2,…) and rests at S at other times. The details of the charging schedule are shown in Algorithm 4. However, when Mx charges Ri for the first time, since the sensor nodes are initially fully charged, the actual working time of tour Ri is less than Tiw. This may influence subsequent periods. To address this issue, one can make Mx stay at sensor node Nj in Ri for time pj·Ti/qc·η and leave with Nj fully charged. In this way, the actual working time of Ri is Tiw afterwards.Algorithm 4:Construct a valid charging schedule of Mk along its assigned tours Rk.
Require:
Rk={Ri∣1≤i≤zk};
Ensure:
{(Ri,tji,τji)∣1≤i≤zk,1≤j≤ri};
(1)    τ01=0;
(2)    for  i=2  to  zk  do
(3)     τ0i=τ0i-1+Ti-1w;
(4)    end for
(5)    for  i=1  to  zk  do
(6)     t0i=0;
(7)     τji=Ti⋅pjqc⋅η, 1≤j≤ri;
(8)     tji=tj-1i+τj-1i+dj-1,jv, 0≤j≤ri;
(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%ai=0  then
(15)    MC leaves S to charge along tour Ri at  time τ0i;
(16)    for  j=1  to  ri  do
(17)     MC arrives Nji at tji, and charges it for τii;
(18)    end for
(19)    MC returns to S, end of charging along tour Ri;
(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 Algorithm2 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 MC. Second, apply Algorithm 3 to decide the charging period of each tour, and assign these tours to mMCs. Then the MCs apply Algorithm 4 to conduct charging along their assigned tours. The computation complexity of the solution is dependent on Algorithm 2, which is O(n2.2).


## 5.1. The Tour Assignment Problem

According to the abovementioned analysis, feasible charging periodTi of tour Ri ranges from Til to Tiu, which also decides the working time Tiw of Ri in each period: Tiw=ωi(Ti)=psumi/qc·η·Ti+Di/v. Then the assignment problem can be formulated as follows.Tour Assignment Problem (TAP). Given z tours R={Ri=(Til,Tiu,ωi)∣1≤i≤z} and enough MCs (qc,qm,v,EM), assign tours R to minimum number of MCs.To prove the NP-hardness of the TAP, we firstly considerr tours with equal charging period T and investigate the sufficient and necessary condition of assigning these r tours to one MC.Proposition 1.
Givenr tours {Ri=(T,Tiw)∣1≤i≤r}, they can be assigned to one MC if and only if ∑i=1rTiw≤T.Proof.
Suppose thesek tours can be assigned to the same MC; then ∑i=1rTiw≤T. Otherwise the MC cannot finish charging along all tours within one charging period T, causing conflicts in the next period.
On the other hand, if∑i=1rTiw≤T, one can construct a valid schedule as follows. The MC charges sensor nodes in Ri during time [k·T+∑j=1i-1Tjw,k·T+∑j=1iTjw] (k=0,1,2,…). Since ∑i=1rTiw≤T, this schedule is valid.
Therefore, the proposition follows.Based on Proposition1, 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 whetherz tours can be assigned to m  MCs is NP-hard.Proof.
Considerz tours {Ri=(T,Tiw)∣1≤i≤z}, and suppose ∑i=1zTiw=2T. Let m=2; then the decision problem can be reformulated as whether {Ri} can be assigned to 2 MCs.
We now construct a set-partition problem as follows. Givenz numbers {a1,a2,…,az}, in which ai=Tiw/T (1≤i≤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 oneMC.We firstly generalize the assumption in Proposition1 and assume that tours have different charging periods. Then we derive a necessary condition for these tours to be assigned to the same MC. Suppose that the periods of all tours are rational numbers and their greatest common divisor is G (Gcan be a decimal); then we have the following proposition.Proposition 3.
Givenk set of tours: {Rij=(aj·G,Tij)∣1≤i≤rj,1≤j≤k}, where Rij is the ith tour of the jth set and {aj} are coprime integers, these tours can be assigned to one MC only if ∑j=1k∑i=1rjTij/aj≤G.Proof.
Suppose these tours can be assigned to oneMC, while ∑j=1k∑i=1rjTij/aj>G. Denote the least common multiple of a1,a2,…,ak by P. Multiplying both sides of the inequality by P, we have(17)Pa1·∑i=1r1Ti1+Pa2·∑i=1r2Ti2+⋯+Pak·∑i=1rkTik>G·P,where P/aj means how many times does the MC charge along tours {Rij} during G·P and ∑i=1rjTij is the total working time of the jth set of tours within each charging period aj·G. It means that the total working time of all the tours during G·P is larger than G·P, which is a contradiction.
Therefore, the proposition follows.Unfortunately, the condition is not sufficient, because it requires that thejth set of tours can be evenly partitioned into aj 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 {2T,2T/3}, {2T,T/3}, and {T,T/2} cannot be charged by one MC even if they satisfy Proposition 3. Besides, deciding whether the jth set of tours can be evenly partitioned into aj 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 MC.Proposition 4.
Givenr tours {Ri=(ai·G,Tiw)∣1≤i≤r}, where {ai} are coprime integers, they can be assigned to one MC if ∑i=1rTiw≤G.Proof.
Considerr tours {Ri′=(G,Tiw)∣1≤i≤r}; if they can be assigned to one MC, obviously {Ri} can be assigned to the same MC. Since ∑i=1rTiw≤G, according to Proposition 3, {Ri′} can be assigned to one MC. Therefore, {Ri} can be assigned to one MC.Note that Proposition4 is not necessary. For instance, consider tour RA=(T,T/2) and r tours {RiB=(r·T,T/2)∣r>1,1≤i≤r}. Since GCD(T,r·T)=T, and the total working time of the r+1 tours is (r+1)/2·T>T, the condition in Proposition 4 is not met. However, one can still assign them to one MC: let the MC charge along tour RA during time [j·T,(j+1/2)·T] and charge along tour RiB during time [(j·r+i-1/2)·T,(j·r+i)·T], j=0,1,2,…. It can be readily proved that the charging schedule is valid.Proposition4 inspires us to minimize the conflict ratio of each MC: δ=∑i=1rTiw/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 toursR1=(T1l,T1u,ω1) and R2=(T2l,T2u,ω2) are assigned to M, where (k-1)·T1u<T2l≤k·T1u≤T2u (k≥1); then the conflict ratio δ of M is minimized when T1=T1u and T2=k·T1u.Proof.
For each tourRi, ω(Ti)=psumi/qc·η·Ti+Di/v. To simplify the presentation, denote that ω(Ti)=ai·Ti+bi.
Considerδ when T2 varies within time interval [i·T1,(i+1)·T1] (i=1,2,…):(18)δ1=a1+i·a2+b1+b2T1,T2=i·T1,δ2=a1+i+1·a2+b1+b2T1,T2=i+1·T1,δ3=a1·T1+a2·T2G+b1+b2G,i·T1<T2<i+1·T1,where G=GCD(T1,T2). When i·T1<T2<(i+1)·T1, G≤T1/2, we hence have(19)δ3=a1·T1+a2·T2G+b1+b2G≥2a1+2i·a2+2b1+b2T1>a1+i+1·a2+b1+b2T1=δ2.In other words, δ1<δ2<δ3. Therefore, in this scenario, δ is minimized when T2=i·T1. Then δ=a1+i·a2+b1+b2/T1.
On the other hand,δ decreases as T1 increases. To minimize δ, we have T1=T1u. Since (k-1)·T1u<T2l≤k·T1u≤T2u, we have i=k; that is, T2=k·T1u.
In summary,δ is minimized when T1=T1u and T2=k·T1u; then the proposition follows.In fact, Proposition5 requires the element period G of M to be maximized. This is an important reason that we anchor T=Tu when deriving the TS condition. Note that one can set T=T′ (Tl≤T′<Tu) 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 MC according to Proposition 5. More importantly, anchoring smaller value of T will increase the total working time ratio (denoted by Φw) of the MCs:(20)Φw=∑i=1m∑j=1ziTjwTj=∑i=1zTiwTi.We have proved in [12] that the working time ratio of an MC indicates the total energy consumption of the MC in conducting charging. Therefore, Φw indicates the total energy consumption of all the MCs. Based on the above two reasons, we anchor T=Tu in deriving the TS condition. Comparisons of anchoring different values of T are made through simulations.Based on the heuristic rules formulated in Propositions4 and 5, we propose Algorithm 3 to greedily assign maximum number of tours to each MC. First, the tours obtained by Algorithm 2 are sorted by Tu in ascending order (line (2)). Then, for each MC, sequentially consider if tour Ri can be assigned to it (lines (3)–(18)). According to Proposition 5, the element period Gk of Mk is set to Tiu of its first assigned tour Ri (line (7)). For any subsequent tour Rj, it is assigned to Mk (lines (6), (13)) if(a)
Rj has not been assigned to any MC (lines (4), (9)),(b)
feasible period ofRj contains a multiple of Gk (lines (10)-(11)),(c)
after assigning, the conflict ratioδk of Mk is still no more than 1 (line (11)).Then charging period Tj of Rj 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(z2), where z is the number of tours.Algorithm 3:Sort tours R by Tu; greedily assign the tours to minimum MCs based on Propositions 4 and 5.
Require:
R={Ri∣1≤i≤z};
Ensure:
M={Mi∣1≤i≤m}, tour assignment of each MC;
(1)    m=0;
(2)    sort {Ri} by Tiu in ascending order;
(3)    for  i=1  to  z  do
(4)       if  Ri has not been assigned  then
(5)        m+=1;
(6)        assign Ri to Mm;
(7)        Gm=Ti=Tiu,  δm=ωiTiGm;
(8)        for  j=i+1  to  z  do
(9)        if  Rj has not been assigned  then
(10)        calculate the k described in Proposition 5;
(11)        if  k exists  and  δm+(ωjk⋅Tiu/Gm)≤1  then
(12)         Tj=k⋅Tiu,  δm+=ωjTjGm;
(13)         assign Rj to Mm;
(14)        end if
(15)     end if
(16)     end for
(17)     end if
(18) end forAfter tour assignment, eachMC applies the GCS to periodically charge along its assigned tours. Suppose zx tours Rx={Ri=(ai·Gx,Tiw)} are assigned to Mx (1≤i≤zx≤n, 1≤x≤m); then a valid charging schedule is that Mx charges Ri during time [k·ai·Gx+∑j=1i-1Tjw,k·ai·Gx+∑j=1iTjw] (k=0,1,2,…) and rests at S at other times. The details of the charging schedule are shown in Algorithm 4. However, when Mx charges Ri for the first time, since the sensor nodes are initially fully charged, the actual working time of tour Ri is less than Tiw. This may influence subsequent periods. To address this issue, one can make Mx stay at sensor node Nj in Ri for time pj·Ti/qc·η and leave with Nj fully charged. In this way, the actual working time of Ri is Tiw afterwards.Algorithm 4:Construct a valid charging schedule of Mk along its assigned tours Rk.
Require:
Rk={Ri∣1≤i≤zk};
Ensure:
{(Ri,tji,τji)∣1≤i≤zk,1≤j≤ri};
(1)    τ01=0;
(2)    for  i=2  to  zk  do
(3)     τ0i=τ0i-1+Ti-1w;
(4)    end for
(5)    for  i=1  to  zk  do
(6)     t0i=0;
(7)     τji=Ti⋅pjqc⋅η, 1≤j≤ri;
(8)     tji=tj-1i+τj-1i+dj-1,jv, 0≤j≤ri;
(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%ai=0  then
(15)    MC leaves S to charge along tour Ri at  time τ0i;
(16)    for  j=1  to  ri  do
(17)     MC arrives Nji at tji, and charges it for τii;
(18)    end for
(19)    MC returns to S, end of charging along tour Ri;
(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 Algorithm2 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 MC. Second, apply Algorithm 3 to decide the charging period of each tour, and assign these tours to mMCs. Then the MCs apply Algorithm 4 to conduct charging along their assigned tours. The computation complexity of the solution is dependent on Algorithm 2, which is O(n2.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 ES=10 kJ, qm=5 J/m, v=5 m/s, EM=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 Figure4, and set qc=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 MCs, and each MC 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.Figure7 depicts the energy consumption of each MC 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 R1~R6 nearly the same as their Tu, while it selects T of R7~R10 much smaller than their Tu. In consequence, when charging along R7~R10, the energy consumption of the MC is much less than EM. In turn, these tours contribute less conflict ratio of the MC, as shown in Figure 8, so that the MC can charge along more tours. The ratio of the grey area in a bar is the conflict ratio of an MC. It can be seen that M4 achieves a relatively low conflict ratio. This is caused by the greedy nature of our solution. Balanced energy consumption of MCs, however, is not a concern of this paper.Figure 7
Energy consumption when charging along each tour.Figure 8
Conflict ratios of eachMC.


### 6.2.  Performance Evaluation

We then compare the number ofMCs 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 ofMCs

The total energy consumption rate of the WRSN shown in Figure4 is psum=15.24 W, and the corresponding m∗=15.24/5=4. Therefore, we actually give an optimum solution in the demonstration, regarding number of MCs used. We further range charging power of the MCs 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 qc=4 W and qc=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 anchorT=Tu in deriving the TS condition. To verify its effectiveness, we anchor T={Tl,((Tl+Tu))/4,((Tl+Tu))/2,(3(Tl+Tu))/4,Tu} 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 MCs. It can be seen that m increases first and then decreases as T increases; m is minimum when T=Tu. 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 MC; thus more tours can be assigned to the same MC. 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 MC, leading to larger results of m. As for Φw, it monotonically increases as T increases. According to (10), Tw/T of each tour decreases as T increases. Furthermore, as T increases, the influence of the decrease in Tw/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 MCs.Figure 10
Results of anchoring different charging periods.In conclusion, the results validate the effectiveness of anchoringT=Tu 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 MCs to charge the requested sensor nodes. To use minimum number of MCs 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 MC; each of the subtrees can be assigned to one MC. Then it derives closed charging tours from the subtrees, and the number of the tours equals the number of MCs 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
⋅
η
⋅
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
⋅
η
⋅
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
⋅
η
⋅
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.020
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
⋅
η
⋅
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
⋅
η
⋅
m
∗
30
30
30
30
30
30
30
30
30
30Figure 11
Comparison between GCHA and NMV varying network size.Figure11 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 MCs 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 MCs are required for charging in these situations. While MCs applying the GCHA scheme charge the sensor nodes periodically, thus such situations never occur. (b) Due to aforementioned reason, many MCs applying the NMV scheme are idle in most cases, causing great waste of resources, while, in the GCHA scheme, charging ability of each MC is fully utilized, by assigning to it as many tours as possible.To analyze when does the GCHA scheme use moreMCs 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 qc·η·m∗ is very close to psum, 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 MC. In fact, the MCs also spend energy and time in moving. Therefore, if the total charging power of MCs 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∗.


## 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 Figure4, and set qc=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 MCs, and each MC 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.Figure7 depicts the energy consumption of each MC 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 R1~R6 nearly the same as their Tu, while it selects T of R7~R10 much smaller than their Tu. In consequence, when charging along R7~R10, the energy consumption of the MC is much less than EM. In turn, these tours contribute less conflict ratio of the MC, as shown in Figure 8, so that the MC can charge along more tours. The ratio of the grey area in a bar is the conflict ratio of an MC. It can be seen that M4 achieves a relatively low conflict ratio. This is caused by the greedy nature of our solution. Balanced energy consumption of MCs, however, is not a concern of this paper.Figure 7
Energy consumption when charging along each tour.Figure 8
Conflict ratios of eachMC.


## 6.2.  Performance Evaluation

We then compare the number ofMCs 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 ofMCs

The total energy consumption rate of the WRSN shown in Figure4 is psum=15.24 W, and the corresponding m∗=15.24/5=4. Therefore, we actually give an optimum solution in the demonstration, regarding number of MCs used. We further range charging power of the MCs 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 qc=4 W and qc=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 anchorT=Tu in deriving the TS condition. To verify its effectiveness, we anchor T={Tl,((Tl+Tu))/4,((Tl+Tu))/2,(3(Tl+Tu))/4,Tu} 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 MCs. It can be seen that m increases first and then decreases as T increases; m is minimum when T=Tu. 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 MC; thus more tours can be assigned to the same MC. 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 MC, leading to larger results of m. As for Φw, it monotonically increases as T increases. According to (10), Tw/T of each tour decreases as T increases. Furthermore, as T increases, the influence of the decrease in Tw/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 MCs.Figure 10
Results of anchoring different charging periods.In conclusion, the results validate the effectiveness of anchoringT=Tu 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 MCs to charge the requested sensor nodes. To use minimum number of MCs 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 MC; each of the subtrees can be assigned to one MC. Then it derives closed charging tours from the subtrees, and the number of the tours equals the number of MCs 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
⋅
η
⋅
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
⋅
η
⋅
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
⋅
η
⋅
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.020
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
⋅
η
⋅
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
⋅
η
⋅
m
∗
30
30
30
30
30
30
30
30
30
30Figure 11
Comparison between GCHA and NMV varying network size.Figure11 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 MCs 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 MCs are required for charging in these situations. While MCs applying the GCHA scheme charge the sensor nodes periodically, thus such situations never occur. (b) Due to aforementioned reason, many MCs applying the NMV scheme are idle in most cases, causing great waste of resources, while, in the GCHA scheme, charging ability of each MC is fully utilized, by assigning to it as many tours as possible.To analyze when does the GCHA scheme use moreMCs 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 qc·η·m∗ is very close to psum, 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 MC. In fact, the MCs also spend energy and time in moving. Therefore, if the total charging power of MCs 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∗.


## 6.2.1. Varying Charging Power ofMCs

The total energy consumption rate of the WRSN shown in Figure4 is psum=15.24 W, and the corresponding m∗=15.24/5=4. Therefore, we actually give an optimum solution in the demonstration, regarding number of MCs used. We further range charging power of the MCs 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 qc=4 W and qc=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 anchorT=Tu in deriving the TS condition. To verify its effectiveness, we anchor T={Tl,((Tl+Tu))/4,((Tl+Tu))/2,(3(Tl+Tu))/4,Tu} 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 MCs. It can be seen that m increases first and then decreases as T increases; m is minimum when T=Tu. 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 MC; thus more tours can be assigned to the same MC. 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 MC, leading to larger results of m. As for Φw, it monotonically increases as T increases. According to (10), Tw/T of each tour decreases as T increases. Furthermore, as T increases, the influence of the decrease in Tw/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 MCs.Figure 10
Results of anchoring different charging periods.In conclusion, the results validate the effectiveness of anchoringT=Tu 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 MCs to charge the requested sensor nodes. To use minimum number of MCs 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 MC; each of the subtrees can be assigned to one MC. Then it derives closed charging tours from the subtrees, and the number of the tours equals the number of MCs 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
⋅
η
⋅
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
⋅
η
⋅
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
⋅
η
⋅
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.020
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
⋅
η
⋅
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
⋅
η
⋅
m
∗
30
30
30
30
30
30
30
30
30
30Figure 11
Comparison between GCHA and NMV varying network size.Figure11 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 MCs 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 MCs are required for charging in these situations. While MCs applying the GCHA scheme charge the sensor nodes periodically, thus such situations never occur. (b) Due to aforementioned reason, many MCs applying the NMV scheme are idle in most cases, causing great waste of resources, while, in the GCHA scheme, charging ability of each MC is fully utilized, by assigning to it as many tours as possible.To analyze when does the GCHA scheme use moreMCs 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 qc·η·m∗ is very close to psum, 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 MC. In fact, the MCs also spend energy and time in moving. Therefore, if the total charging power of MCs 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 theMinimum Mobile Chargers Problem (MMCP) inWireless Rechargeable Sensor Networks. We divide the problem into two NP-hard subproblems: theTour Construction Problem (TCP) and theTour Assignment Problem (TAP). We propose theGreedily 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 theTour Schedulable (TS) condition, it greedily splits the cycle into schedulable subtours. Subsequently, these subtours are heuristically assigned to minimum number of MCs, so that the MCs can apply theGreedy Charging Scheme (GCS) to charge along their assigned tours. The computation complexity of the GCHA scheme is O(n2.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 MCs that are required by the NMV scheme. In most scenarios, our method generates optimum solutions for MMCP. Compared with theLower Boundm∗, 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 ofMCs into consideration. Consequently, the approximation ratio of our method will be theoretically analyzed. (b) The energy efficiency of MCs can be improved by carefully merging traveling paths of some tours. (c) Load balance between MCs will be studied.



---

*Source: 782952-2015-06-18.xml*