Speed-Grading Mobile Charging Policy in Large-Scale Wireless Rechargeable Sensor Networks

Abstract

As the technological breakthrough is made in wireless charging, the wireless rechargeable sensor networks (WRSNs) are finally proposed. In order to reduce the charging completion time, most existing works use the “mobile-then-charge” model—the Wireless charging vehicles (WCV) moves to the charging spot first and then charges nodes nearby. These works often aim to reduce the node’s movement delay or charging delay. However, the charging opportunities during the movement are overlooked in this model because WCV can charge nodes when it goes from one spot to the next. In order to use the charging opportunities, a speed grading method is proposed under the circumstance of variable WCV speed, which transformed the problem of final charging delay into a traveling salesman problem with speed grading. The problem was further solved by linear programming method. The simulation experiments show that, compared with the existing charging methods, the proposed method has a significant improvement in charging delay.

This research work was supported by Natural Science Foundation under Grant NO. 61662018; Natural Science Foundation of Guangxi province under Grant NO 2015GXNSFBA139254 and Natural Science Foundation of Guangxi province under Grant NO 2018GXNSFAA294061.

1 Introduction

The energy issue is one of the key impediment in wireless sensor large-scale applications and deployment today, most existing sensor networks are powered by batteries with limited capacity [1,2,3], which results in their limited life cycle and the inability to complete data collection and communication tasks successfully. With the breakthrough of wireless charging technology by Zeng et al. [4, 5], it provides a promising alternative to the traditional power supply for sensor nodes. We expect that new WRSNs will be widely used in our daily lives in the near future, such as smart furniture, internet of things, artificial intelligence.

Recently, in order to improve the charging efficiency of WRSNs, most works have focused on the internal design of microelectronics [6,7,8], while improving the underlying microelectronics technology is important for wireless transmission systems, in practice, we have found that the charging time of a single wireless rechargeable node is not negligible, and it plays an important role in the performance of the entire wireless charging system. For typical wireless rechargeable sensor nodes, such as the Wireless Identification and Sensing Platform (WISP) developed by Intel [9], the sensor node requires that the wireless charging energy must exceed a certain threshold for proper operation of various sensing, computing, and communication component tasks. Due to the limited wireless charging speed, the charging process is usually time consuming. For example, it requires about 155 s to fully charge a WISP node [10] in 10 m distance, which greatly affects the performance of WRSNs, especially in large-scale sensor networks. The mentioned problem of low charging efficiency mainly emphasizes the design improvement inside the microelectronics and neglects the effective optimization of the delay in the charging process. In fact, the charging completion time can be shortened by reasonable and effective optimization in the charging process. This plays an important role in the overall performance of WRSNs. In recent years, the optimization on charging completion time for WRSNs has been raised with more and more attentions for us to research on it. For example, Fu proposed to use the method of planning the optimal path to minimize the charging delay and solve the delay by linear programming method [11]. Most of the previous research work is based on the “move-then-charge” model: the WCV moves to each charging spot and then charges the sensor nodes near the spot [12], which goes until all networks nodes are fully charged. However, the charging opportunities during the movement are overlooked in this model, because the WCV can charge nodes when it goes from one spot to the next. This kind of charging scheme can better reduce the charging completion time. In order to further explore the charging opportunities during the movement, the speed of WCV becomes an important factor. There is a paradox about the speed of WCV. On the one hand, in order to charge more nodes in the network, in principle, the speed is slower, because the nodes in the network can get more energy, but on the other hand, in order to reduce the moving time, the speed is required to be as fast as possible. Therefore, the speed of WCV has a great influence on charging delay.

This paper discusses the problem about the WCV speed grading in WRSNs, and the goal is to reduce the charging completion time. In order to achieve the goal, we propose a speed grading scheme based on joint consideration of movement and charging delay. First, the nodes in the sensor network are clustered, and the nodes are divided into clusters of specific values (the values set according to the situation). After the combination, the charging spots are obtained, and then the distance of two neighbor spots in the running path are calculated. The WCV traverses all the spots and charges the rechargeable nodes around the spot, this problem can be transformed into a Traveling Salesman Problem with speed grading. We use the K-nearest Neighbor algorithm to solve this TSP problem and get the proper charging path. The nodes are charged at different speeds in different operating intervals, which ultimately reduces the total charging delay, improves the charging efficiency, and prolongs the life cycle of the sensor network.

2 Network Model

Wireless Identification and Sensing Platform (WISP):

Intel’s WISP platform is the most representative platform in WRSNs. It has traditional RFID reading capabilities and also supports information acquisition and computing capabilities. The WISP nodes inherit the functionality of traditional RFID tags and also support perceptual and computational functions. When approaching an RFID reader, the WISP node can collect energy from the reader signal. The energy obtained by charging this node is stored in a capacitor and can be used for future data sensing, recording, calculation and transmission [13].

Energy Charging Model:

In this paper, we propose a wireless charging model as an energy charging model, which is expressed by the following formula:

$$ P_{r} = \frac{{G_{s} G_{r}\upeta}}{{L_{p} }}\left( {\frac{\uplambda}{4\pi (d + \beta )}} \right)^{2} P_{0} $$

Where $d$ is the distance between the WISP reader and the sensor node, $P_{0}$ is the transmit power of WISP, $G_{s}$ is the transmit antenna power, $G_{r}$ is the accept antenna power, $L_{p}$ is the polarization loss, $\uplambda$ is the charging wavelength, $\upeta$ is the rectifier efficiency, $\beta$ is the parameter to adjust the Friis’ free space equation for short distance transmission. Where d is the only variable in the formula, and the rest are constants based on the environment and device settings. The above model is based on the Friis’ free space equation and it is proved by experiments that this is a great approximation of the charging energy [14].

In order to simplify the description of the design part that follows, we simplify the formula 1, and the simplified formula is as follows:

$$ P_{r} = \frac{\upalpha}{{(d + \beta )^{2} }} $$

Where $d$ is the distance between the WCV and the sensor node, α represents the constants affected by the environment, Including $P_{0} ,\,G_{s} ,\,G_{r} ,\,L_{p} ,\,\uplambda,\,\upeta$ in formula 1.

The Network Charging Model:

In existing research, some special charging spots are selected for charging network nodes nearby. The spots can be obtained by clustering algorithms [15]. The WCV first moves to the charging spots and then charges the nodes in the surrounding charging range. When all of rechargeable nodes around the spot are charged completely, the WCV will move along the planned path to the next charging spot and charge the neighbor nodes, and this process will continue till all nodes in the network are fully charged.

Charging Radius:

Since the WCV relies on its own transmitting antenna to charge the node wirelessly, the charging radius of WCV is limited. In this paper, the charging radius of WCV is assumed as 15 m.

It is assumed that $N$ fixed rechargeable sensor nodes are deployed in the sensor network. The position of a single node $i$ in the network can be obtained by the positioning technique [16]. The node coordinates are expressed as $\left( {W_{x}^{i} ,W_{y}^{i} } \right)$. At the same time, it is assumed that the wireless charger can move at a certain speed by WCV in the deployment area. When the sensor node is in the charging radius of the charger, it charges the node wirelessly by using the internal storage energy carried by itself, when the energy obtained by the node is above a certain threshold $\updelta$ the deployed sensor nodes can complete works such as signal sensing, communication, and calculation. Therefore, in order to minimize the total charge cycle of all nodes in the network, we need to find an optimal charging strategy to minimize the charging delay. Especially, in this paper, the main goal is to find a suitable charging spot and the staying time at the spot by using the different ranges of the speed to achieve the purpose of minimizing the charging delay.

In order to express this charging problem explicitly by formula, it is assumed that the charger stays at several different spots, for example, the coordinate at the spot $j$ near the node $i$ is $\left( {R_{x}^{j} ,R_{y}^{j} } \right)$, ${\text{t}}_{j}$ is the staying time, the distance between node $i$ and spot j is ${\text{d}}_{ij} = \sqrt {(W_{x}^{i} ,R_{x}^{j} )^{2} + (W_{y}^{i} ,R_{y}^{j} )^{2} }$, according to formula (2), the corresponding charging power is $P_{ij} = \frac{\alpha }{{(d_{ij} +\upbeta)^{2} }}$, the charging energy E obtained by the node $i$ at the spot $j$ is $P_{ij} t_{j}$. Given the interest area of $N$ nodes, the node charging energy threshold is δ, the charger can stay at any spots in this area, we can use mathematical formulas to represent this minimization of the charging node delay problem. It is computed as follows:

$$ \begin{aligned} {\hbox{min T}}\; = \;\sum {\frac{{p_{i} }}{{s_{i} }}} \; + \;\sum {t_{i} } \hfill \\ s.t.\left\{ {\begin{array}{*{20}c} {\forall n_{i} \; \in \;N,\;\sum {(\frac{{p_{i} }}{{s_{i} }}.e_{i} \; + \;t_{j} .e_{j} \; \gg \;\delta )} } \\ {\forall i,\;0\; \le \;s_{i} \; \le \;s_{T} } \\ {\forall i,\;t_{i} \; \ge \;0} \\ \end{array} } \right. \hfill \\ P_{ij} \; = \;\frac{\alpha }{{(d_{ij} +\upbeta)^{2} }},\;({\text{i}}\; \in \;{\rm N},\;{\rm j}\; \in \;(1.2.. \ldots \infty )) \hfill \\ {\text{d}}_{ij} \; = \;\sqrt {(W_{x}^{i} ,\;R_{x}^{j} )^{2} \; + \;(W_{y}^{i} ,\;R_{y}^{j} )^{2} } \hfill \\ \end{aligned} $$

The goal is to find the minimum of the formula (3) under the constraint conditions, and using the linear programming method to solve the final charge completion time.

3 WRSNs Charging Tour Planning Optimization Algorithm Under Speed Grading

3.1 Determining the Charging Spot

The charging power is first discretized into several different charging levels. After this processing, we reduce the search space of the Linear Programming (LP) planning problem in formula (3), and the potential spot position changes from infinite to finite. The optimal charging delay may consist of a large number of charging spots, but in the actual charging scenario, it is not practical for the charger to move in a large number of spots, so the number of spots should be reduced relative to the number of nodes deployed. We introduce a charging spot combination design, which can reduce the number of spots effectively within a certain threshold.

In order to combine the charging spot position and reduce the number of spots, we use the famous K-means clustering algorithm, Lloyd’s algorithm [17], combining chargers to multiple clusters based on geographic location. Lloyd’s clustering algorithm divides n observation points into k clusters, each of which belongs to the nearest cluster center. For the charger spot combination problem, the first n observation points are the total number of charging spots obtained by the charging power discrete processing. We set the k value according to the following rules. It starts with a smaller value and increments by one in each round of recalculation until the average distance between the clusters is less than a given threshold. After combining the charging spots, each sensor node is assigned to the nearest cluster center node, and the corresponding charging level is available through formula (5).

3.2 Generating Movement Path

The path selection problem can be transformed into a Traveling Salesman Problem with speed grading. We propose a greedy algorithm to solve this problem. The pseudocode of the algorithm will be given below. First, we add all the minimum closed spot sets to the path P, and then we add the nodes other than the path P in turn according to the algorithm.

In each round of node selection, we choose to traverse a node $V_{i}$ that can achieve the minimizing delay, then add the node to path P, and update the path to get $V_{i} + P$. For no spot, we calculate its expected delay at each insertion spot position $P_{i}$. By listing all possible nodes and insertion spots, we can pick the appropriate spot and the corresponding insertion position to achieve a minimum total charge completion time. This process continues until all nodes in the network are added to path P. The initial charging location can be selected as any charging spot and the total charging delay remains the same.

Obviously, calculating the total charging completion time involves the speed of WCV. We will describe the WCV speed grading in detail in the next section.

3.3 Speed Grading Process

For two neighbor spots, we refer to the line segment formed by their connection as edge, which is divided into several segments objects according to different charging levels, and the charger takes different speeds on different segments of the edge. Before introducing the speed grading scheme, we first introduce a theorem related to the charging energy of the sensor.

Theorem 1

: When the speed of WCV for different strategies in a segment changes, if the movement time at a given charging level is the same on each sub-segment, then the charging completion time is the same in this segment.

Using theorem 1, we can discretize each edge according to the charging level into different segments, they adopt different speeds $s_{i}$ and corresponding charging levels. The speed selection factor is related to the amount of energy received by the node being charged. When the energy of the sensor node is low, the energy received unit time during charging is high, and the corresponding charger speed should be slower, so that the node receives more energy during the movement. Correspondingly, when the energy of the node is sufficient, and the charging efficiency unit time is low, the charger should move at a faster speed to the spot to charge the neighbor nodes, because there are not any charging opportunities during the movement, and swift movement will be conducive to reduce exercise time. The definition of the total charge S in the unit time and the correlation with the speed is given below.

The total charge total S in the unit time is defined as: $S = \sum\nolimits_{i = 1}^{n} {P_{i} }$ (n is the rechargeable nodes around the spot). The relationship between S and v is as follows

$$ v = \frac{K}{S}(K = 1) $$

According to the obtained S-v curve, the speed is divided into the following five gradings (Fig. 1).

Fig. 1.

The relationship between S and v

The speed calculated by using this model is too large and not realistic, it cannot be used for speed grading.

The speed calculated by using this model is not obvious, which is not conducive to speed grading.

By comparing the above different sets of speed ranges, we finally use the speed scheme of Table 1. During the movement according to the path map, the WCV selects different speeds according to the different intervals of S, and charges the nodes around the spot.

Table 1. The relationship model between S and v is $v = \frac{K}{S} \left( {K = 1} \right)$

Obviously, different speeds have a significant impact on the charging efficiency and the final charging delay. The WCV matches different speeds according to different charging efficiencies during the movement from the previous spot to the next. For example, when the number of rechargeable nodes in the neighbor charging range is large, the WCV should select a low speed and move slowly, so that more sensor nodes can be charged, and using the charging opportunities as much as possible. When the neighbor nodes are too sparse, passing through at a high rate, which involves the balance between speed and charging efficiency. The charging efficiency can be approximated by the total amount of effective charging unit time in formula 7 (Tables 2 and 3).

Table 2. The relationship model between S and v is $v = \frac{K}{{S^{2} }}\left( {K = 1} \right)$

Table 3. The relationship model between S and v is $v = \frac{K}{\sqrt S }\left( {K = 1} \right)$

The Balance Between Optimal Solution and Complexity:

In a dense deployed network, the edge formed by two charging spots may contain multiple different charging levels. If all segments have different charging levels and assumed different speeds, then the computational complexity will be quite large. To solve this problem, we have designed a segment combination scheme that combines multiple segments into a new segment. The charging speed $s_{np}$ of the new segment is calculated as follows:

$$ s_{np} = \sum {E(d_{n} ,c_{{P_{i} }} ),i = 1,2,3} $$

$E(d_{n} ,c_{{P_{i} }} )$ represents the charging speed from segment $P_{i}$ to node n, it can be calculated by formula 1.

We set a threshold for multiple segments of each edge, and the above combination scheme adopts when the number of segments exceeds this threshold.

The pseudocode is as follows:

4 Simulation and Performance Evaluation

We conduct simulation experiments to evaluate the performance of speed grading scheme, and compared it with the scheme proposed in the literature [11] in terms of the charging completion time. The delay performance of the two schemes under different network topologies and parameter settings is further compared.

This paper evaluates the excellent performance of the two schemes by the following two indexes.

• (i) Completion time: the completion time refers to the time when the charger starts to move to the initial charging spot after the charging is completed.

• (ii) Charging energy variance: Obviously, when all nodes are charged but not overcharged, the minimizing completion time can be achieved. In addition, no energy is wasted, and when the variance becomes larger, more energy and charging time are wasted.

Simulation parameter setting: We set four charging levels for each node according to the charging model, and the network topology is generated randomly. We compare our scheme and the minimizing charging delay (MCD) scheme [11] under the same topology. The deployment area is within a two-dimensional square area of 100 m * 100 m, the maximum speed of WCV is v = 15 m/s, the maximum charging radius of WCV is r = 15 m. In the formula (2), α = 36, β = 30, d is the distance between the WCV and the sensor node. When using the speed grading method to control the movement of WCV, the step size of dividing edge into segments is taken as 2, the node energy threshold is 2 J (the charging energy more than 2 J is qualified), and the number of nodes initially deployed is 100.

The path map generation process in Fig. 2 is as follows. Firstly, the appropriate number of charging spots are obtained according to the clustering algorithm, and then the heuristic algorithm is used to obtain the path map for solving the TSP problem. The path map obtained by 100 random nodes, the generation path changes with the change in the qualification of K-means clustering algorithm, and it is also related to the initial deployment.

Fig. 2.

TSP optimization results of 30 charging spots

The above path optimization is only obtained by simple clustering, the final charging path and charging delay are not optimal solutions. We consider the clustering optimization scheme in the charging strategy of large-scale WRSNs, we cluster the nodes in the network by relying on the energy limitation of each node in WRSNs and other constraints.

The calculation of locating the charging spot obtained by the K-means clustering algorithm did not involve whether the number of the spots finally obtained has a large improvement on the charging efficiency of WCV. Therefore, we decided to further optimize the delay by adopting the method of splitting the charging cluster to improve the charging efficiency. The wireless charging transmission power depends on the distance between the node and the WCV, and the shorter distance can reduce the charging time of the sensor node. So, the charging cluster with a large number of nodes into multiple sub-charge clusters is tried to be split based on the previous K-means clustering to obtain the charging spot. If the total completion time of the multiple subtasks is less than the original charging task, confirming the splitting operation and updating the charging spot position list. The separation basis and method are as follows:

It is necessary to measure the travel time of the subtask aggregation when confirming whether the task or the calculation can be split within the task verification. The calculation process is as shown in formula 9:

When $\theta < w_{i}$, it indicates that splitting charging cluster can reduce the charging time, then we need to decide to split the number of new task subsets, the method can be given by the following pseudocode:

As shown in Fig. 3, it compares the charging delay of speed grading and MCD scheme [11] with different node numbers. We can get the following conclusions: (i) As the number of deployed nodes increases, the charging delay also begins to increase. However, the time delay of speed grading scheme is effectively reduced compared with the MCD scheme. The charging completion time is shortened, and the early delay reduction effect is obvious. But the improvement between comparisons is reduced as the number of deployment nodes increases. For possible reasons, the number of charging spots also increases when the number of deployment nodes increases, and the energy obtained by WCV during the movement is limited. Therefore, the later improvement is not obvious. (ii) The subsequent charging delays of two schemes are not increased greatly when the deployment node is larger than a certain number. For example, the subsequent charging delays of the two schemes are not increased much, and the delay growth tends to be slow when the number of nodes is 150. The possible reason is that there is overlap in the charging radius of all nodes and the number of charging spots does not have a linear relationship with the number of nodes when the deployment density increases. It may be a better choice for WCV to charge at the late stop.

Fig. 3.

Charging delay and node number

As shown in Fig. 4, it compares the charging delay of speed grading and MCD scheme [11] with different spot numbers. We can get the following three conclusions: (i) As the number of charging spots increases, the delay of both scheme begins to decrease. The reason is that when the number of charging spots increases, the path segment generated by it is also more, and the WCV has more charging opportunities during the movement, which is beneficial to reduce the delay. But the MCD scheme is when the number of charging spots increases, the charging time at the spot becomes longer, and the node obtains more charging energy than a small number of spots. The delay tends to be flat and limited. (ii) When the number of spots is same, the delay of the speed grading scheme is reduced compared with the MCD scheme, and the effect of the previous period reduction is obvious. The reason is that the speed grading scheme utilizes the charging opportunities during the movement, and the exquisite speed grading is beneficial to the charging of WCV, so that the charging opportunities are more and the charging is more reasonable. (iii) When the number of charging spots continues to increase in the later period, there is a possibility that a delay of a high number of charging spots is slightly larger or has the same delay than a low number of delays. The reason is that the nodes are deployed randomly, the charging spots obtained by the K-means clustering algorithm will have outliers. The position also changes when the number of charging spots changes. Some outliers and charging spots will combine and appear in a more appropriate position. This allows different numbers of charging spots to have the same delay or a higher number of it with a slightly longer delay than a lower number one.

Fig. 4.

Charging delay and spot number

After adopting the cluster splitting scheme, we recalculated the delay and made a comparison curve with the previous two schemes as shown in the Fig. 5. The red one is the delay curve after splitting the charging clusters. It can be found that it is similar to the previous law. As the number of charging spots increases, the charging delay also gradually decreases, and the downward trend in the early period is obvious. As the number of charging spots increases to a certain amount about 40, the decrease in the charging delay tends to be slow. The reason is that when the number of spots increase to a certain amount, the optimization scheme of dividing the charging cluster does not improve the charging efficiency significantly. It indicates that it is not suitable for splitting, and it is difficult to reduce the charging delay by continuing to increase the spots by cluster splitting scheme. Moreover, it can be seen from the Fig. 5 that compared with the scheme of speed grading processing, the cluster splitting scheme has no obvious fluctuation in the later period, and the delay has been reduced with the increase of the charging spots until it is slow. The reason is that the number of outliers is reduced by the cluster splitting, and the number of nodes gathered around the charging spot is more reasonable. There is no large charging loss when the WCV charges the neighbor nodes at the charging spot, and enhancing the efficiency of WCV.

Fig. 5.

Charging delay comparison with cluster splitting scheme

As shown in Figs. 6 and 7, they summarize the charging energy obtained by 60 nodes in two different charging schemes under the same deployment conditions. The following data is obtained through analysis and calculation. The MCD scheme [11] compare with the speed grading scheme, the average value of the charging energy of 60 nodes is reduced from 3.0455 J to 2.7136 J, and the variance is reduced from 0.7463 to 0.4357. This means that the proposed speed grading scheme can reduce the energy waste in the speed optimization process. The reason is that with a more exquisite division of the speed, the charging time of the charger at each charging spot can be more accurately scheduled, which further reduces the energy waste.

Fig. 6.

Node energy statistics for MCD scheme

Fig. 7.

Node energy statistics for Speed grading scheme

The following conclusions are obtained by comparing the above two figures: with the speed grading scheme, 60 sensor nodes deployed randomly meet the threshold of energy greater than 2 J. But there are still a few nodes that are overcharged—searching its coordinates and finding out that the overshoot nodes are neighboring in dense deployment area. Because there are some segments that are divided too much when dividing the edge, the speed changes little and the speed is too slow in these segments causing overshoot of the nodes, and these neighbor nodes are also in dense deployment areas.

It can be seen from the Fig. 8 that the delay has remained the same after the MCD scheme [11] is divided into edges. As the speed grading scheme increases with the division of the edge, the charging delay decreases, and the improvement over MCD scheme is obvious. However, when the number of divisions increases to a certain amount, the charging delay remains unchanged or increases slightly. This is because when the number of divided segments is increased to a certain amount, the difference in the number of different segments becomes smaller. As a result, the improvement of time delay is not obvious compared with the MCD scheme.

Fig. 8.

Charging delay and segmentation number

5 Conclusion

In this paper, the wireless charging sensor problem is identified as a charging planning problem under speed grading. In order to overcome the contradiction between the charging delay and the movement delay of the WCV, we propose to use the charging opportunities during the movement to achieve a great balance between them. This wireless sensor charging problem can be transformed into a Traveling Salesman Problem with speed grading. The charging delay is solved by the linear programming method, and through comparison of several simulation experiments, it can be found that the speed grading scheme which proposed by us can greatly improve the charging efficiency and reduce the total charging delay compared with the MCD scheme [11]. We will consider solving the problems of time delay optimization and efficiency improvement under different topology deployment when using multiple WCVs to charge sensor nodes.