1. Introduction 1.1. Background and Motivation
Wireless sensor networks (WSNs) have a wide range of applications, such as military surveillance, environmental monitoring, disaster relief, smart home, etc. [1,2,3]. In the traditional wireless sensor network, the energy of the sensor node is provided by the battery. However, the capacity of the battery is limited by the size of the node, and the available energy of the sensor node is extremely insufficient, which greatly limits the application of the WSNs [4]. At the same time, the sensor node is often not easily accessible, and the cost of replacing the battery is often large, even is impossible sometimes. In order to make wireless sensor networks more practical, there are many works on the self-sustainability of the wireless sensor network [5,6]. The rechargeable sensor network offers a promising opportunity for the WSN [7,8,9].
In the rechargeable sensor network, many kinds of energy from the environment are used by the wireless sensor nodes, such as heat energy, solar energy, wind energy, and so on. In Reference [10], authors assume that sensors can harvest energy from natural energy source during the working period. Furthermore, Reference [11] considers the spatiotemporally coupled constraint in wireless rechargeable sensor networks (WRSNs) and proposes a distributed algorithm to get the optimal sampling rate to maximize network utility. By considering the time-varying recharging rate caused by the unreliable natural energy resource, an effective algorithm is proposed in Reference [12] to maintain the battery at the desired target level through optimizing the sampling rate and end-to-end routing path.
However, the natural energy often varies with the time and environment and the variation is unpredictable and uncontrollable, and sensor nodes are in the risk of unstable and insufficient energy supply. Different from the energy-harvesting technique, wireless energy transfer technology with magnetic resonance coupling [13] or electromagnetic effect [14] can provide a stable energy supply, which is a promising solution for extending the lifetime of wireless sensor networks. The result in Reference [15] shows that the wireless energy transfer technology is not only efficient but also immune to its surrounding environment. Industry research further demonstrates that it is possible to transfer 60 W of power over a distance of up to two to three feet with an energy transfer efficiency of 75% [16]. In the wireless rechargeable sensor network (WRSN), a wireless energy transfer technology realized by a mobile wireless charging vehicle (WCV) is applied to power sensor nodes. The results show that the lifetime of the WRSN is extremely extended [17]. The adoption of the WCV can provide high and stable charging rates to sensors. Thus, the cost of sensors and the complexity of energy management in WRSN is significantly reduced.
In this paper, we study the use of the WCV to replenish energy to sensor nodes in WRSNs. Some works have been done on the wireless sensor network with wireless energy transfer technology. In References [18,19,20], solutions for mobile charger scheduling and charging infrastructure deployment of rechargeable nodes are proposed. In Reference [21], the author assumes that the power of each charger is adjustable, and then finds a charger placement and a corresponding power allocation. Authors in Reference [22] study an on-demand energy replenishment problem and formulate it as an optimization problem with an objective of maximizing the number of charged sensors per tour. In Reference [23], the author assumes that each sensor node can be partially charged so that more sensor nodes can be charged by the WCV before their energy is depleted. Besides, the WCV not only serves as an energy transmitter to charge the static sensor nodes but also serves as a data collector in some works, such as [24,25,26,27]. Different from References [24,25,26] which focus on extending network lifetime, Reference [27] considers the problem of scheduling minimum mobile devices to periodically charge and collect data from sensors. The traveling path planning of the WCV is an important factor in the performance of WRSNs. Reference [28] aims to minimize the traveling cost of the WCV based on the energy monitoring and reporting protocols. In Reference [29], the author first analyzes the optimization opportunity and then proposes a novel charging strategy by modeling the problem as traveling salesman problem (TSP) with neighborhood. The model is able to exploit the wireless charging ability and reduce the moving delay of the charger at the same time. In Reference [30], the association between the WCV charging cycle and operational lifetime of sensor nodes is considered. A novel periodic charging algorithm is proposed which jointly considers charging tour planning and the WCV depot positioning. As the wireless energy transferring is over the wireless channel, the charging efficiency is sensitive to the Charging Channel Quality (CCQ). However, this factor has not been considered in the above works.
The distance between nodes is one of important factors influencing the CCQ. In Reference [31], the influence of the distance is considered. However, authors assumed that the capacity of the WCV is infinite, which is impossible in many cases in real life. In this paper, the WRSN is charged by a WCV which has limited capacity, at the same time, the influence of the CCQ on the energy replenishment of the sensor node is also considered. As the capacity of the WCV is finite, how to efficiently utilize the limited energy is important. To estimate the energy efficiency, we propose a metric named waste rate. Then, an algorithm is proposed to minimize the waste rate through finding optimal charging sensor nodes.
1.2. Contribution
As the WCV has limited capacity, minimizing waste rate is an important and realistic problem in the WRSN. To address this problem, through finding optimal sensor nodes charged by the WCV, the energy waste rate is reduced. The main contribution can be summarized as follows.
First, we take the limited capacity of WCV and the channel quality between the WCV and rechargeable sensor nodes into consideration and model the minimizing waste rate as an optimization problem. Then, we propose a method to find the optimal charging sensor nodes and use the nearest neighbor algorithm to get the traveling path of WCV. Furthermore, we also propose an extended node dynamic replacement strategy, which can avoid the death of uncharged sensor nodes and coverage holes. The experimental results demonstrate that our proposed solution can effectively reduce the waste rate and the total charging time comparing with the baseline scheme.
1.3. Paper Organization
The remaining sections are organized as follows. Section 2 introduces the system model in detail. In Section 3, we formulate the problem and provide a solving method. An extended node dynamic replacement strategy (ENDRS) is also proposed to avoid the death of uncharged nodes in Section 3. The simulation result is provided in Section 4. At last, we conclude the whole paper in Section 5. The main notations used in our paper are listed in Table 1.
2. System Model 2.1. Network Model
In this paper, we consider a set of sensor nodes, which is denoted byV, distributed over a limited two-dimensional area. The two-dimensional coordinate of sensor nodevi∈Vis(xi,yi). In the sensor network, there is a fixed base station S, which is also a sink node used to collect sensing data. We assume that the energy of S is unlimited comparing to sensor nodes. The set E constitutes the edges between two nodes which are in the transmission range of each other. Each sensor nodeviis equipped with a battery whose capacity isEmax. The initial energy level of sensor nodeviisEi,0andEi,0=Emax. NotationEi,tdenotes the residual energy of nodeviat timet, andEi,t=Ei,0whent=0. The minimum energy level for regular operations isEmin, hence the sensor nodes would stop working if the residual energy is lower thanEmin.
The energy consumed by sensor nodevican be divided into three parts:ei,t,ei,s, andei,r, which represent the energy consumed by sensor nodeviin sending data, sensing data, and receiving data during [0,t], respectively. Among them,ei,tandei,rinclude: <1> The energy consumed by receiving and sending data from its own nodes; <2> As the network works in the multi-hop pattern, some energy is used to receive and transmit data from neighboring sensor nodes. The energy consumption rate of the sensor nodeviis defined as the energy consumed by the sensor nodeviwithin unit time. The energy consumption rate of the sensor nodevibefore time t is denoted asεi,t, which can be calculated as
εi,t=ei,t+ei,r+ei,st
The operation of the WCV in the network is introduced in the following. The WCV with limited capacity leaves from the base station and charges the optimal sensor nodes which are selected by our proposed algorithm one by one. After charging these sensor nodes, it would back to the base station, and the traveling path of the WCV forms a cycle path.
NotationPi,crepresents the charging rate of the WCV to sensor nodevi, and the charging delayTi,dis the time that the WCV charges the sensor nodevi, which is defined as
Ti,d=Ei,0−Ei,t−Ti,d∗εi,tPi,c
LetT(i−1),idenote the total charging time from the moment that the WCV leaves sensor nodevi−1to the moment that the WCV leaves sensor nodevi, which is expressed as
T(i−1),i=Ti,d+Ttravel(i−1→i)=Ti,d+hi−hi−1Vc,
whereTtravel(i−1→i)is the time spent by the WCV from sensor nodevi−1to the sensor nodevi, which is a function of the distance and the velocity. We usehi=(xi,yi)to denote the coordinate of sensor nodevi, andhi−hi−1to denote the horizontal distance between sensor nodevi−1and sensor nodevi, which is defined by Euclidean distance. Hence,hi−hi−1=(xi−xi−1)2+(yi−yi−1)2. The WCV moves with a constant velocity which is denoted byVc . According to Reference [32], we letVc= 5 m/s in the simulation.
In practical, due to the limited capacity of the WCV, the WCV may not be able to meet the charging requirement of all sensor nodes. Thus, choosing proper sensor nodes to be charged by the WCV is important. The CCQ is an important factor which influences the charging quality from the WCV to sensor nodevi. A good charging strategy should make the WCV with limited capacity charge more sensor nodes with better CCQ. To better measure the energy efficiency of the WCV, we innovatively propose the concept of waste rate, which also can be used in maximizing the efficiency of wireless charging at each node.
To support wireless power transmission, we assume that a receiving coil is installed on each sensor node. The CCQ between the sensor nodevi and the WCV is related to many factors, such as the distance between the sensor node and the WCV, the noise, obstacle, and so on. In this paper, to simplify the model, we assume that the CCQ is only related to the distance. The waste rate is defined as the energy loss of the WCV to the sensor node when the CCQ is determined by the distance. The waste rate is an increasing function of distance. With the increase of distance, the waste rate increases exponentially [33]. Let D denote the charge range of the WCV.
2.2. Cellular Structure
We assume that the wireless rechargeable sensor area is a two-dimensional plane. For better zoning, we partition the two-dimensional plane into many hexagonal cells. Under the cellular structure, we denotedias the distance from sensor nodevito its cell center. The sensor nodes in a cell constitute a cluster. In the remaining paper, we use the cluster to represent the cell and sensor nodes in the cell. The number of sensor nodes in a cluster is a random variable which is no less than 1. Some sensor nodes will send the charging requests to the base station which containsNRcandEc−i,t, whereNRcis the number of sensor nodes which send the charging request in thecthcluster, and0≤NRc≤ρ,ρis the maximum number of sensor nodes in thecthcluster;Ec−i,tis the residual energy of the sensor nodeviwhich is in thecthcluster at timet. According to the residual energy of the sensor node which sends charging request in cluster, we divide these sensor nodes into three types:a,b, and k, where a represents the sensor nodes whose residual energy is greater thanEminand less than0.1*Ei,0at timet,brepresents the sensor nodes whose residual energy is greater than0.1*Ei,0and less than0.2*Ei,0at timet, andkrepresents the sensor nodes whose residual energy is greater than0.2*Ei,0and less than0.3*Ei,0at timet. The number of different types of sensor nodes in thecthcluster is denoted asac,bc, andkcrespectively. When the residual energy is larger than0.3*Ei,0, the sensor node does not send the charging request, thusNRc=ac+bc+kc.
We assume that when the WCV reaches the charging working place, each sensor node can send its own CCQ to the WCV. After the WCV arrives in the cluster, it can stop and charge at any position. Therefore, there are infinite stopping points in the cluster, which leads to high complexity of finding the optimal stopping position. Since the size of the cell is small, the difference in the traveling cost of the WCV caused by different stopping points is very small. To simplify the model, we assume that the stopping point of the WCV is the center of the cell.
2.3. Limited Rechargeable Clusters
In our paper, we consider the limited capacity of the WCV, the WCV may not have enough energy to charge all sensor nodes which send charging requests in the clusters. Combining the cellular structure, we define the priority level of each cluster and useweightcto denote the weight value of thecthcluster. The priority of thecthclusterweightcis defined as
weightc=ωNRc+χ[αac+βbc+γkc],
where ω, χ, α, β, and γ are harmonic coefficients, which satisfy
ω+χ=1
α+β+γ=1
From Equation (4), it can be found that different design goals can be achieved through adjusting the value of harmonic coefficients during cluster selection. Whenωhas a larger value, the number of sensor nodes which send charging requests is a main influence of cluster selection. Whenχis larger, the distribution of residual energy becomes more uniform. The values ofα,β, andγmainly affect the preference of three types of sensor nodes. For example, whenαis larger, we prefer to choose the cluster with more nodes of typea.
Clusters sending charging requests are sequentially stored in setAaccording to weight values.A={c1,c2,⋯,cNum}, whereNumrepresents the number of clusters sending charging requests. Due to the limited capacity of the WCV, not all required charging clusters can be charged in a charging cycle. Therefore, the cluster with larger weight value should be selected first. This means that clusters with less energy and more sensor nodes sending charging requests often have a higher charging priority. At the same time, we assume that the WCV can only charge one sensor node in a cluster. This means that the number of selected charging clusters equals to the number of optimal charging sensor nodes. The selected cluster is stored in setB={c1,c2,⋯,cNc}, whereNcthe number of selected charging clusters. Obviously,Nc≤Num. The WCV will charge optimal sensor nodes in these clusters according to the Hamiltonian circle. The number of selected charging clusters is related toTp,max, which is the maximum time used by the WCV in a charging cycle. The relation between charging timeT(i−1),iand the maximum timeTp,maxis
∑i=1NcT(i−1),i≤Tp,max.
When the traveling path is determined, the traveling time of the WCV is constant which is expressed byNc TtravelwhereTtravelis the average value ofTtravel(i−1→i). According to Equation (2), the charging time is proportional to the residual energy of the charged sensor node. Hence, when the remaining energy of all sensor nodes sending charging requests in the cluster is0.3*Ei,0, the total charging value gets the maximum. When the remaining energy of all sensor nodes sending charging requests in the cluster is the thresholdEmin, the total charging time is the minimum value of∑i=1NcT(i−1),i. Thus, the range of the charging time can be expressed as
Nc(0.7∗Ei,0+Ti,d∗εi,tPi,c+Ttravel)≤∑i=1NcT(i−1),i≤Nc(Ei,0+Ti,d∗εi,tPi,c+Ttravel)
By transforming Equation (8), the range ofNCcan be obtained as
∑i=1NcT(i−1),i(Ei,0+Ti,d∗εi,tPi,c+Ttravel)≤Nc≤∑i=1NcT(i−1),i(0.7∗Ei,0+Ti,d∗εi,tPi,c+Ttravel)
According to the relationship betweenT(i−1),iandTp,maxin Equation (7), we derive the upper bound of the number of selected charging clusters, which is expressed as
Nc≤Tp,max(0.7∗Ei,0+Ti,d∗εi,tPi,c+Ttravel)
Furthermore, we can also use the capacity of the WCV,Ti,d, and the initial energy of the sensor node to calculateNCwhich is given as
Bc,maxEi,0+Ti,d*εi,t+Etravel(i−1→i)≤Nc≤Bc,max0.7*Ei,0+Ti,d*εi,t+Etravel(i−1→i),
whereBc,maxis the capacity of the WCV.
To demonstrate the above calculation, here is an example shown in Figure 1. It can be found that the number of clusters sending charging requests is 10, e.g.,NRc=10.
As shown in Figure 1, each cluster has a random number of some sensor nodes and the number is in the range of [1,6]. According to the energy setting, in the4thcluster,a4=2,b4=1,k4=1. Letω=0.2,χ=0.8,α=0.7,β=0.2, andγ=0.1, respectively. Using Equation (4), we can obtain the weight value of4thcluster:weight4 is 2.16. Similarly, the weight values of other clusters can be calculated, which are given in Table 2.
According to the weight value of each cluster, the clusters sending charging requests are sorted as follows:c7>c2>c1>c4>c9>c3>c6>c10>c8>c5. That is,A={c7 ,c2 ,c1 ,c4 ,c9 ,c3 ,c6 ,c10 ,c8 ,c5}. Then, we use Equation (10) to find the prior charging clusters whenNCis assumed to be5, and obtain setB={c7,c2,c1,c4,c9}. Therefore, the WCV will charge the optimal sensor nodes in the 7th cluster, the 2th cluster, the 1th cluster, the 4th cluster, and the 9th cluster firstly.
As the capacity of the WCV is limited, the traveling path should be designed to reduce unnecessary energy waste on the journey. We make the WCV to charge along the Hamilton circle. The schematic diagram is shown in Figure 2.
The WCV starts from the base station and charges sensor nodes according to the Hamilton circle. In this paper, we use the nearest neighbor algorithm to get the optimal charging tour.
3. Problem Formulation and Solution 3.1. Problem Analysis
As discussed in Section 2, the CCQ between the WCV and the sensor node is only related to the distance. The waste ratePi,wasteat sensor nodeviis defined as
Pi,waste=Ui,full−Ui,inUi,full,
whereUi,fullis the output charging power from the WCV andUi,inis the charging power received by sensor nodevi. The charging powerUi,incan be expressed as
Ui,in=ϖ(di)∗Ui,full,
whereϖ(di)is a function of distancediand0<ϖ(di)<1, which is used to expressed the CCQ.
By combining Equations (12) and (13), the relation between the waste rate andϖ(di)is
Pi,waste=1−ϖ(di).
According to Equation (14), it can be found that the energy waste rate is closely related to the CCQ. Because the CCQ between the WCV and the sensor node is only related to the distance, the waste ratePi,wastedepends on the distance. This means that energy efficiency is related to the distance. As improving energy efficiency can be realized through minimizing the energy waste rate, we optimize the distance between the WCV and the sensor node to minimize the energy waste rate. For the optimal object, we propose an algorithm to find the optimal traveling path of the WCV and optimal charging sensor nodes.
Due to the large number of sensor nodes, to estimate the waste rate of all selected sensor nodes, we define the average of energy waste rate of optimal sensor nodes as
Pwaste=1Nc∑i=1NcPi,waste<1.
According to Equations (14) and (15), the waste ratePi,wasteat sensor nodeviand the average waste rate of sensor nodesPwasteare less than 1.
Based on the above analysis, we model minimizing energy waste rate as an optimal problem, which is given by:
minPwaste=1Nc∑i=1NcPi,waste
s.t.1Nc∑i=1NcPi,waste<1
∑i=1NcT(i−1),i≤Tp,max
Pi,waste=1−ϖ(di)<1
The constraint in Equation (16b) indicates that the average of waste rate should be less than 1 while Equation (16c) indicates that the total charging time is less than the maximum time of the WCV in a charging cycle.
As the different traveling path affect the energy consumed by the WCV moving from one sensor node to another one, the number of chargeable sensor nodes is influenced by the traveling path of the WCV. Besides, according to constraint (16d), the waste rate depends on the distance between the sensor node and the WCV. Hence, the minimum value can be achieved by choosing the optimal sensor node. To solve the problem in Equation (16a), we proposed two algorithms to plan the traveling path of the WCV and select the optimally charged sensor node, respectively.
3.2. The Traveling Path Planning
According to the above discussion, the different traveling paths results in different traveling distances, the time and the energy spent on different traveling paths will be different, thus the optimal traveling path of the WCV should be proposed to reduce the unnecessary energy waste. Though the path planning has been researched in some previous works, such as Reference [17], the energy waste suffered by the traveling path of the WCV has not been considered. The traveling path not only affects the energy waste rate but also has an influence on the charging time for each node. In order to avoid unnecessary energy waste, we optimize the traveling path of the WCV to minimize the energy waste rate. We assume that the WCV travels along the Hamiltonian circle, which is a traveling salesman problem (TSP) [34]. Analogous details of proof process could be found in Reference [17].
To solve the required Hamiltonian circle, the nearest neighbor algorithm is proposed. The detail of the nearest neighbor algorithm is provided in Algorithm 1.
| Algorithm 1. The nearest neighbor algorithm. |
| Input:[xi,yi],0≤i≤Nc |
| Output: The traveling path of the WCV |
|
1: Calculate the distance between each priority cluster and the base station, and sort the distance in ascending order. Select the clusterccountwhich is closest to the base station. The initial value of count is 1. 2: Calculate the distance of the remaining clusters from the clusterccount, then select the clusterccount+1which is closest to the clusterccount,count=count+1. 3: Repeat step 2 untilcount=Nc,Ncis the number of selected clusters. 4: The WCV drive from the clustercNcto base station. |
To illustrate Algorithm 1, we use an example shown in Figure 3. Assume that there are five to-be-charged clusters in the network at some time point (see Figure 3a). First, we calculate the distance between each cluster and the base station, and sort the distance in ascending order which isd1 <d2 <d3 <d4 <d5. The nearest clusterc1 is first selected (see Figure 3b). Then we calculate the distance of the remaining clusters from the clusterc1, and the order isd2 <d3 <d4 <d5. The clusterc2is selected since it is closest to the clusterc1 (see Figure 3c). Similarly, the remaining clusters are selected one by one (see Figure 3d,e). Finally, after charging clusterc5 (see Figure 3f), the WCV will return to the base station to recharge itself. A charging tour according to the nearest neighbor algorithm is formed.
3.3. The Selection of Optimal Charging Nodes
According to the above discussion, the energy efficiency is related to the distance. As improving energy efficiency can be realized through minimizing the energy waste rate, the distance between the WCV and the sensor node is optimized to reduce the energy waste rate. To minimize the energy waste, based on the results of Algorithm 1, we propose a node selection algorithm shown in Algorithm 2.
| Algorithm 2. Procedure of solution for our problem. |
| Input: Two-dimensional coordinates of sensor nodes[xi,yi], the distance between each sensor nodeviin thecthpriority cluster and the WCVdi, the number of selected charging nodesNc, the density of nodesρ, initial energy of each sensor nodeEi,0and the remaining energyEi,t, the speed of the WCVVc. |
| Output: Energy average waste ratePwaste, the total charging timeTper, the traveling path of the WCV. |
|
1: Partition the two-dimensional plane with hexagonal cells. When the residual energy of nodesEi,treaches the charging threshold, each node sends a charging request in units of clusters. The clusters are sorted according to the weight values.weightcwhich is obtained by Equation (4),Ncprior charging clusters are selected and thenNcoptimal sensor nodes are selected for charging. 2: Sort the waste ratePi,wastebetween the WCV and sensor nodeviafter the WCV enters the cluster which is determined by the distance between the WCV and the sensor nodesdi. 3: Find the optimal charging sensor nodes by considering their waste rate, which means that the sensor nodes with better CCQ are selected for charging. 4: Calculate the corresponding charging timeTperand achieve the traveling path of the WCV according to Algorithm 1. |
To illustrate the execution of Algorithm 2, we use a similar example shown in Figure 4. Assume that there are some clusters sending charging requests in the network at some time point (see Figure 4a). The clusters are sorted according to the weight value of thecthclusterweightcby Equation (4), which isc7<c5<c4<c6<c1<c3<c2. We assumeNc=3 which can be obtained by Algorithm 1 and Equation (10), it means the WCV can only charge 3 clusters (see Figure 4b). According to Algorithm 1, the WCV will charge clusterc1first, after entering clusterc1, there are three to-be-charged sensor nodesv1,1,v1,2andv1,3. Sort the waste ratePi,wastewhich is determined by the distance between the WCV and sensor nodesdi, and the order isP1,waste<P2,waste<P3,waste . As sensor node v1,1 has better CCQ, it is selected to be charged (see Figure 4c). Then, the WCV leaves clusterc1to clusterc2, the order of waste ratePi,wasteof sensor nodesv2,1andv2,2isP2,waste<P1,waste. Thus, the nodev2,2 is selected (see Figure 4d). Similarly, the optimal charging sensor nodev3,1in clusterc3 can be found (see Figure 4e). Finally, the WCV will return to the base station and the charging round of the WCV is finished (see Figure 4f).
First, we prove Theorem 1 to illustrate sensor nodes obtained by Algorithm 2 are optimal sensor nodes. Then, we study the complexity of Algorithm 2.
Theorem 1.
Through Algorithm 2, we can get the optimal charging sensor nodes which can minimize the energy waste rate.
Proof.
Assumption: Given an optimal solutionψ*=(V*,T*,Pwaste*), where some of the sensor nodes selected are not optimal. Then we could construct a new solutionψ∧=(V∧,T∧,Pwaste∧)where all the selected sensor nodes are optimal. With the assumption,V*inψ*is the set of these selected charging sensor nodes, while some of nodes such asVi*andVj*are not optimal, and we assume that theNcinψ*andψ∧is same, that is,Nc*=Nc∧. Then the new solutionψ∧could be constructed as follows. LetV∧is the set of selected optimal charging sensor nodes andT∧is the related total charging time per cycle. Because all nodes inV∧is optimal, we can getPi,waste∧≤Pi,waste*,Pj,waste∧≤Pj,waste*, from Equation (16d), where thePi,waste∧,Pj,waste∧andPi,waste*,Pj,waste*represent the waste rate of sensor nodesvi,vjin theψ*andψ∧, respectively. ForNc*=Nc∧, we can get that in theψ*andψ∧, the average waste rate of sensor nodes is different, that is,Pwaste∧≤Pwaste*. At the same time, the difference in waste rate results in the difference of charging efficiency, thus results in the difference of total charging time with different solutions. From Equation (2), we can getT∧≤T*. Then it can be found that the solutionψ∧could provide an improved objective. □
Next, we show that the solutionψ∧is feasible for our optimal problem. To verify feasibility, we need to show thatψ∧satisfy constraints Equations (16b–d). Since theψ∧is a feasible solution for our problem, it should satisfy the constraints Equations (16b–d). ForT∧≤T*, from Equation (16c),T*<Tp,max, we can getT∧≤Tp,max, which could satisfy Equation (16c). ForP∧waste≤Pwaste*, it can be straightforwardly found thatP∧waste≤Pwaste*<1, which satisfy Equation (16b). We assume that sensor nodesviin theψ*is not optimal, thusPi,∧waste≤Pi,waste*. BecausePi,waste*<1, we can getP∧i,waste≤Pi,waste*<1, which satisfies Equation (16d).
Thus, the solutionψ∧=(V∧,T∧,P∧waste)is a feasible solution, which could provide an improved objective comparing to the optimal solutionψ*.
Theorem 2 shows an analysis of the time complexity of our algorithm.
Theorem 2.
The time complexity of the Algorithm 2 is bounded inO((lRc)2+n+Nc2) , where l, n, Nc denote the side length of the sensor field, the number of deployed sensors, and the number of optimal charging sensor nodes, respectively.
Proof.
Because l is the length of the sensor field, the division of the sensor field requires at mostO((lRc)2). n sensor nodes are considered for calculating related CCQ for the selection of the optimal charging sensor nodes, the complex of the nodes is O(n). Nc selected optimal charging sensor nodes are considered in turn to obtain the traveling path of the WCV. For example, at first, there are Nc optimal charging sensor nodes are considered to calculate the traveling path of the WCV, the complex is O(Nc).Then, there are Nc − 1 selected optimal charging sensor nodes are considered to calculate the traveling path of the WCV, the complex is O(Nc − 1)., at the end of the algorithm, there is only one sensor node, the complex is O(1),. Thus, the complex of the optimal charging sensor nodes isO(Nc+Nc∗(Nc−1)/2), that is,O(Nc)2. So, the complexity of the Algorithm 2 is bounded inO((lRc)2+n+Nc2). This completes the proof. □
3.4. Extend Node Dynamic Replacement Strategy
According to the description of Algorithm 2, the optimal charging sensor node in a cluster may not be the one with the least energy. The sensor node whose residual energy is close to the thresholdEminis named the life-critical sensor node. Since the WCV does not charge the life-critical sensor node timely, the residual energy will be exhausted in a short time and the sensor node will be dead due to the shortage of energy. To avoid the death of sensor nodes whose charging requests are not satisfied, we also proposed the extended node dynamic replacement strategy (ENDRS).
According to the above discussion, the optimal charging sensor node in a cluster may not be the one with the least energy. To avoid the death of nodes in this charging cycle, the life-critical sensor node will go to sleep and its work will be transferred to the optimal charging sensor node. In the next round of the charging cycle, the sleep node will be considered according to the ENDRS which is based on Algorithm 1 and Algorithm 2. The detail of the ENDRS can be described as follows.
After choosing optimal charging nodes, clusters which have sleep sensor nodes are recorded. In the next charging round, the values of harmonic coefficients in Equation (4) during prior cluster selection are changed. This change should ensure that the cluster with sleep nodes has more chance to be selected. After the WCV enters a cluster with the sleep node, the tradeoff between the charging efficiency and the lifetime of the sensor node is considered during the optimal charging sensor node selection. We define the weight of optimal charging sensor node selection asζdi+(1−ζ)Ec−i,t, where different goals can be achieved through adjusting the value of the harmonic coefficientζ. When(1−ζ) has a larger value, the residual energy is a main influence of selection. This means that the WCV prefers to choose the life-critical node to ensure the connectivity of network. To further illustrate the ENDRS strategy, we provide an example in Figure 5.
As shown in Figure 5, there is a cluster constituting of 5 sensor nodes. According to Algorithm 2, the WCV selects node 1 which has 12% energy, instead of node 2 which has 5% energy. The node 2 will die soon, which may lead to coverage holes in this area. Moreover, the connectivity and stability of the network may be degraded. If the ENDRS strategy is adopted, node 2 will go to sleep and the work of node 2 is transferred to node 1. In the next round of the charging cycle, node 2 will have chance to be charged by adjusting the harmonic coefficient and the weight in the ENDRS, which ensures the connectivity and stability of the network.
4. Simulation Evaluation
In this section, some simulation results are provided to evaluate the performance of the proposed algorithm. Through studying these results, the impact of the network parameter on the network performance is obtained.
4.1. Parameter Setting
We assume that each cell contains a random number of sensor nodes, and defineρas the density of the sensor node. The density of the sensor node is defined as the maximum number of sensor nodes in a cell, e.g.,ρ≥1 . When the density of the sensor node increases, the total number of sensor nodes in the network also increases. By using MATLAB software, a network scenario in which the density of the sensor node is 2 are generated, which is shown in Figure 6.
In order to prevent the WCV from running out of energy and being unable to drive back to the base station, we set that the WCV can charge for 25 nodes in a charging cycle. The size of each hexagon cell is 3 m. The consumption rate of each sensor node is set asrand(1)/1011J, and the initial energy of each sensor node isE0=0.02J. The WCV moves at a constant speed ofVc= 5 m/s with an energy consumption rate ofEv=1/1012J/m. The base station is the origin(0,0) . According to the curve fitting experiment in Reference [35], we definePi,waste=−0.095812∗di 2−0.03771∗di+1.0. When the distance of charging is more than 3 m, we assume that the charging efficiency of the WCV is0, that is, the waste ratePi,wasteis1 . According to Equation (14), we draw the relation between the energy waste rate and the distance, which is given in Figure 7.
The result in Figure 7 indicates that the energy waste rate increases with the increasing of the distance, which is consistent with Equation (14). In order to decrease the waste rate, the distance between the sensor node and the WCV should be short as much as possible. Furthermore, this one-to-one correspondence relationship makes the distance be replaced by the waste rare during parameter setting of the simulation.
4.2. Results and Analysis
Under the same constant density of the sensor node, we study the impacts of energy waste rate and the capacity of WCV on the number of chargeable sensor nodes in a charging cycle. We first observe the number of chargeable sensor nodes when the energy waste rates are 0.24, 0.34, 0.44, 0.54, 0.64, 0.74, and 0.84, respectively. The results are shown in Figure 8 when the capacity of WCVBc,maxis 0.6 J, 0.8 J, 1.0 J, and 1.2 J, respectively.
From Figure 8, it can be found that the number of chargeable sensor nodes increases with the decreasing of the energy waste rate or the increasing of the capacity of the WCV. This phenomenon can be explained by using Equation (11). Take the right side of the equation, the number of chargeable sensor nodes isNc=Bc* ,max0.7*Ei,0+Ti,d*ρi,t+Etravel(i−1→i), whereBc,max*=(1−Pi,waste)*Bc,maxrepresents the energy actually used. The original formula is changed into:Nc=ψ∗(1−Pi,waste), whereψ=Bc,max0.7*Ei,0+Ti,d*εi,t+Etravel(i−1→i).
The density of the sensor nodeρhas a great impact on the number of sensor nodes in the work. Next, we study the impact of the density of the sensor node on the average energy waste ratePwaste. In the simulation, the density of the sensor nodeρ is 2, 3, 4, 5, 6, 7, 8, 9, and 10, respectively. The comparison results of three different algorithms is given in Figure 9. In Figure 9, the proposed algorithm is expressed by “OfWR”, “energy only” represents the algorithm only considers the impact of residual energy of sensor nodes, and “Random” denotes sensor nodes are randomly choose to be charged according to the Random algorithm. In the energy only algorithm, the WCV will choose the node which has the least residual energy to charge. In the Random algorithm, the WCV randomly choose one of sensor nodes which send the charging request. From the results in Figure 9, it can be found that the energy waste of the OfWR is the least and the decreases with the increasing of the density of the sensor node. Hence, the proposed algorithm can achieve better performance in the energy waste rate, especially when the density of the sensor nodes is higher. It indicates that our proposed algorithm can achieve higher energy efficiency in the network with a large density of the sensor node.
Furthermore, we compare the charging time when the WCV can charge for 25 sensor nodes in a round. The variation of total charging time in terms of the density of the sensor nodes is shown in Figure 10.
The results in Figure 10 shows that the total charging time of the proposed algorithm is less than half time of other algorithms when the density of the sensor node is 2. With the increasing ofρ, the difference between the proposed algorithm and the other algorithms is enlarged. It indicates that our proposed algorithm can reduce the charging time in the network with a large density of the sensor node.
Finally, we observe the total charging time varying with the speed of the WCV under different densities of the sensor node, and the result is in Figure 11. The result in Figure 11 shows that the total charging time decreases with the increasing of the speed of the WCV, and the difference among different densities of the sensor node is not obvious. This result indicates that the total charging time can be decreased through increasing the speed of the WCV, and when the speed of the WCV is more than 20 m/s, the proposed algorithm can achieve the almost same performance of the charging time under a smaller density of sensor node.
According to the analysis in Section 3, to optimize the traveling path of the WCV, the WCV should travel along the Hamiltonian circle, which is a traveling salesman problem. By using the nearest neighbor algorithm, the traveling path of the WCV can be found. In the simulation, the traveling path of the WCV obtained by Algorithm 1 is shown in Figure 12. The result in Figure 12 demonstrates that the WCV moves according to the Hamilton circle.
5. Conclusions
In this paper, we consider that the mobile WCV charges sensor nodes in clusters to achieve a self-sustainable rechargeable wireless sensor network. Due to the limited capacity of WCV, it may be impossible to charge all sensor nodes which send the charging request within a charging round. To maximize energy efficiency, we model an optimization problem with the object of minimizing the average energy waste rate when the limited capacity of the WCV and the imperfect CCQ are considered. The problem is solved by using two proposed algorithms: Algorithm 1 and Algorithm 2. Algorithm 1 is used to attain the traveling path of WCV while Algorithm 2 is used to find the optimally charged sensor node. An extended node dynamic replacement strategy is further proposed to avoid the death of uncharged life-critical sensor nodes. The simulation result shows that the proposed algorithms can reduce the energy waste rate and the total charging time, especially when the density of the sensor node is large.
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
[Image omitted. See PDF.]
| Symbols | Definition |
|---|---|
| Ei,0 | The initial energy level of sensor nodevi |
| Ei,t | The residual energy of nodeviat time |
| Emax | The capacity of the sensor nodevi |
| Emin | The minimum energy required by the regular operation |
| εi,t | The energy consumption rate of sensor nodevibefore timet |
| Ti,d | The charging time of sensor nodevi |
| T(i−1),i | The total charging time from sensor nodevi−1to sensor nodevi |
| Ttravel(i−1→i) | The time spent by the WCV from sensor nodevi−1to sensor nodevi |
| Tper | The total charging time during a charging circle |
| Vc | The speed of the WCV |
| Nc | The number of selected charging clusters |
| NRc | The number of sensor nodes which send the charging request in thecthcluster |
| Num | The number of clusters which send the charging request |
| Tp,max | The maximum time of the WCV in a charging round |
| Ec−i,t | The residual energy of sensor nodeviin thecthcluster at timet |
| Bc,max | The capacity of the WCV |
| Pi,waste | The waste rate of sensor nodevi |
| ρ | The density of the sensor node |
| Cluster Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| weight | 2.24 | 2.52 | 1.36 | 2.16 | 0.64 | 1.04 | 2.84 | 0.64 | 1.52 | 1 |
Author Contributions
Conceptualization, M.T. and W.J.; methodology, M.T.; software, J.L.; validation, formal analysis, and investigation, M.T. and W.J.; resources, J.L.; data curation, S.M.; writing—original draft preparation, M.T.; writing—review and editing, visualization, supervision, project administration, and funding acquisition, W.J.
Funding
This work was supported by the National Natural Science Foundation of China (NO. 61701241), Natural Science Foundation of Jiangsu Province (NO. BK20170935), and Natural Science Foundation of the Jiangsu Higher Education Institutions (NO. 17KJB510030).
Conflicts of Interest
The authors declare no conflict of interest.
1. Kahn, J.; Katz, R.; Pister, K. Next Century Challenges: Mobile Networking for Smart Dust. In Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, Seattle, WA, USA, 15–19 August 1999; pp. 271–278.
2. Alsayyari, A.; Kostanic, I.; Otero, C.E.; Aldosary, A. An empirical path loss model for wireless sensor network deployment in a sand terrain environment. In Proceedings of the 2017 IEEE Sensors Applications Symposium (SAS), Glassboro, NJ, USA, 13–15 March 2017.
3. Kumar, P.; Kumari, S.; Sharma, V.; Sangaiah, A.K.; Wei, J.; Li, X. A certificateless aggregate signature scheme for healthcare wireless sensor network. Sustain. Comput. Inform. Syst. 2018, 18, 80–89.
4. Sheikhi, M.; Kashi, S.S.; Samaee, Z. Energy provisioning in wireless rechargeable sensor networks with limited knowledge. Wirel. Netw. 2019, 25, 3531–3544.
5. Akhtar, F.; Rehmani, M.H. Energy replenishment using renewable and traditional energy resources for sustainable wireless sensor networks: A review. Renew. Sustain. Energy Rev. 2015, 45, 769–784.
6. Djenouri, D.; Bagaa, M. Energy-Aware Constrained Relay Node Deployment for Sustainable Wireless Sensor Networks. IEEE Trans. Sustain. Comput. 2017, 2, 30–42.
7. Sun, G.; Liu, Y.; Yang, M.; Wang, A.; Zhang, Y. Charging Nodes Deployment Optimization in Wireless Rechargeable Sensor Network. In Proceedings of the IEEE Global Communications Conference, Singapore, 4–8 December 2017.
8. Jiang, F.; He, S.; Cheng, P.; Chen, J. On Optimal Scheduling in Wireless Rechargeable Sensor Networks for Stochastic Event Capture. In Proceedings of the 2011 IEEE Eighth International Conference on Mobile Ad-Hoc and Sensor Systems, Valencia, Spain, 17–22 October 2011.
9. Zhu, J.; Feng, Y.; Liu, M.; Chen, G.; Huang, Y. Adaptive online mobile charging for node failure avoidance in wireless rechargeable sensor networks. Comput. Commun. 2018, 126, 28–37.
10. Bhaskar, A.; Champawat, R.; Bhaskar, S. Current Developments of Energy Scavenging, Converting and Storing in WSNs. Int. J. Comput. Appl. 2015, 125, 6–12.
11. Zhang, Y.; He, S.; Chen, J. Data Gathering Optimization by Dynamic Sensing and Routing in Rechargeable Sensor Networks. IEEE/ACM Trans. Netw. 2016, 24, 1632–1646.
12. Liu, R.S.; Sinha, P.; Koksal, C.E. Joint energy management and resource allocation in rechargeable sensor networks. In Proceedings of the IEEE INFOCOM, San Diego, CA, USA, 14–19 March 2010; pp. 1–9.
13. Cheon, S.; Kim, Y.; Kang, S.; Lee, M.L.; Zyung, T. Wireless Energy Transfer System with Multiple Coils via Coupled Magnetic Resonances. ETRI J. 2012, 34, 527–535.
14. Talla, V.; Kellogg, B.; Ransford, B.; Naderiparizi, S.; Gollakota, S.; Smith, J.R. Powering the next billion devices with wi-fi. In Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies, Heidelberg, Germany, 1–4 December 2015.
15. Sangare, F.; Han, Z.; Xiao, Y.; Niyato, D. Mobile Charging in Wireless-Powered Sensor Networks: Optimal Scheduling and Experimental Implementation. IEEE Trans. Veh. Technol. 2017, 66, 7400–7410.
16. Kurs, A.; Karalis, A.; Moffatt, R.; Joannopoulos, J.D.; Fisher, P.; Soljačić, M. Wireless power transfer via strongly coupled magnetic resonances. Science 2007, 317, 83–86.
17. Shi, Y.; Xie, L.; Hou, Y.T.; Sherali, H.D. On renewable sensor networks with wireless energy transfer. In Proceedings of the 2011 IEEE INFOCOM, Shanghai, China, 10–15 April 2011.
18. Xie, L.; Shi, Y.; Hou, Y.T.; Sherali, H.D. Making Sensor Networks Immortal: An Energy-Renewal Approach With Wireless Power Transfer. IEEE/ACM Trans. Netw. 2012, 20, 1748–1761.
19. Zhang, S.; Qian, Z.; Kong, F.; Wu, J.; Lu, S.; Sheng, Z. P3: Joint optimization of charger placement and power allocation for wireless power transfer. In Proceedings of the 2015 IEEE Conference on Computer Communications (INFOCOM), Hong Kong, China, 26 April–1 May 2015; pp. 2344–2352.
20. Liu, Q.; Cai, W.; Shen, J.; Fu, Z.; Liu, X.; Linge, N. A speculative approach to spatial temporal efficiency with multi objective optimization in a heterogeneous cloud environment. Secur. Commun. Netw. 2016, 78, 4002–4012.
21. Zhang, S.; Qian, Z.; Wu, J.; Kong, F.; Lu, S. Wireless Charger Placement and Power Allocation for Maximizing Charging Quality. IEEE Trans. Mob. Comput. 2017, 17, 1483–1496.
22. Ren, X.; Liang, W.; Xu, W. Maximizing charging throughput in rechargeable sensor networks. In Proceedings of the 2014 23rd International Conference on Computer Communication and Networks (ICCCN), Shanghai, China, 4–7 August 2014.
23. Xu, W.; Liang, W.; Jia, X.; Xu, Z. Maximizing Sensor Lifetime in a Rechargeable Sensor Network via Partial Energy Charging on Sensors. In Proceedings of the 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), London, UK, 27–30 June 2016.
24. Xie, L.; Shi, Y.; Hou, Y.T.; Lou, W.; Sherali, H.D. On traveling path and related problems for a mobile station in a rechargeable sensor network. In Proceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing, Bangalore, India, 29 July–1 August 2013.
25. Zhao, M.; Li, J.; Yang, Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks. IEEE Trans. Mob. Comput. 2014, 13, 2689–2705.
26. Xie, L.; Shi, Y.; Hou, Y.; Lou, W.; Sherali, H.; Midkiff, S.F. Bundling mobile base station and wireless energy transfer: Modeling and optimization. In Proceedings of the IEEE INFOCOM 2013, Turin, Italy, 14–19 April 2013; pp. 1636–1644.
27. Liu, B.H.; Nguyen, N.T.; Pham, V.T.; Lin, Y.X. Novel methods for energy charging and data collection in wireless rechargeable sensor networks. Int. J. Commun. Syst. 2017, 30, e3050.
28. Wang, C.; Li, J.; Ye, F.; Yang, Y. Netwrap: An DND based real-time wireless recharging framework for wireless sensor networks. IEEE Trans. Mob. Comput. 2014, 13, 1283–1297.
29. Chen, F.; Zhao, Z.; Min, G.; Wu, Y. A Novel Approach for Path Plan of Mobile Chargers in Wireless Rechargeable Sensor Networks. In Proceedings of the 2016 12th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN), Hefei, China, 16–18 December 2016.
30. Jiang, G.; Lam, S.-K.; Sun, Y.; Tu, L.; Wu, J. Joint Charging Tour Planning and Depot Positioning for Wireless Sensor Networks Using Mobile Chargers. IEEE/ACM Trans. Netw. 2017, 25, 1–17.
31. Xie, L.; Shi, Y.; Hou, Y.T.; Lou, W.; Sherali, H.D.; Midkiff, S.F. Multi-Node Wireless Energy Charging in Sensor Networks. IEEE/ACM Trans. Netw. 2014, 23, 437–450.
32. Rao, X.; Yang, P.; Yan, Y.; Zhou, H.; Wu, X. Optimal Recharging with Practical Considerations in Wireless Rechargeable Sensor Network. IEEE Access 2017, 5, 4401–4409.
33. Fu, L.; Cheng, P.; Gu, Y.; Chen, J.; He, T. The Optimal Charging in Wireless Rechargeable Sensor Networks. IEEE Trans. Veh. Technol. 2016, 65, 278–291.
34. Padberg, M.; Rinaldi, G. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Rev. 1991, 33, 60–100.
35. Kurs, A.; Moffatt, R.; Kurs, A.; Soljačic, M. Simultaneous mid-range power transfer to multiple devices. Appl. Phys. Lett. 2010, 96, 44102.
The College of Information Science and Technology, Nanjing Forestry University, Nanjing 210037, China
*Author to whom correspondence should be addressed.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
© 2019. This work is licensed under https://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Abstract
Recently, wireless energy transfer technology becomes a popular way to address energy shortage in wireless sensor networks. The capacity of the mobile wireless charging car (WCV) and the wireless channel between the WCV and the sensor are two important factors influencing the energy efficiency of the wireless sensor network, which has not been well considered. In this paper, we study the energy efficiency of a wireless rechargeable sensor network charged by a finite capacity WCV through an imperfect wireless channel. To estimate the energy efficiency, we first propose a new metric named waste rate, which is defined as a function of the charging channel quality. Then, energy efficiency optimization is modeled as minimizing the waste rate. Through optimizing the distance between the WCV and sensor nodes, the set of optimal charging sensor nodes is obtained. By using the Hamiltonian circle, the nearest neighbor algorithm is proposed to find the traveling path of the WCV. Furthermore, to avoid the untimely death of sensor nodes and the coverage hole, an extended node dynamic replacement strategy is proposed. The simulation results show that the proposed method can reduce the waste rate and the total charging time; i.e., the sum of traveling time and charging delay can be significantly reduced, which indicates that the proposed algorithm can improve the energy efficiency of the network.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer