However, WSNs still have some intrinsic problems. A WSN is composed of wireless sensors and some relay nodes. Each sensor node will sense various kinds of information and then transfer it to the relay nodes. All of these actions will consume power, but a sensor’s power is limited by battery capacity so that its power will be exhausted. Many sensors collect multimedia data, and their power consumption will be more obvious. Note that these sensors may be placed in the dangerous places we just mentioned, so that we cannot immediately replace the batteries; therefore, the WSN will be paralyzed if the relay node dies. In view of this, researchers have proposed some methods to solve the network lifetime problem [9,10,11,12]. Some scholars think that all of the sensors should not work at the same time because it will cause power to be wasted unnecessarily. Scheduling sensor working time can make efficient use of the power of sensors. However, the lifetime of the WSN still depends on the upper bound of a battery’s capacity 12; this is a fact which cannot be changed.

WRSNs can be roughly divided into two types: those that operate in indoor environments, and those that operate in outdoor environments. The deployment strategy of the chargers needs to consider various impacts from those different environments. Most studies discuss outdoor scenarios; too few studies consider indoor scenarios. Actually, wireless sensor networks are very helpful indoors as well [17,18]; for example, they can help factories control production for better quality and provide disaster prevention and relief. Life will become more convenient if sensors never run out of power. This is one of the main reasons why the wireless rechargeable sensor network is increasingly popular. In this paper, the deployment scenario is the indoor environment; it entails a complex problem because the charger deployment strategy will be affected by the sensors’ positions, RF interference and the charger’s efficiency, since those metrics have very frequent trade-off relationships. We have to balance each factor and then make sure the resultant deployment strategy can provide more charging efficiency. In previous work, we proposed the moveable-charger-based algorithm (MCBA) [19] to achieve a good charger deployment strategy. First, find the candidate nodes for charger deployment through mapping. Calculate the number of sensors that each candidate node can cover. Then, select candidate nodes in order from large to small by sorting until all sensors are covered. However, MCBA still has some defects, such as the MCBA being a greedy-based algorithm, so it has more of an opportunity to fall into the local optimum. The charger deployment has been proven to be an NP-hard problem. Since charger deployment has been proven to be an NP-hard problem, it is inefficient to solve this problem by using brute-force algorithms [17]. In order to solve this problem and to reduce deployment costs as much as possible to achieve optimization, we used a metaheuristic algorithm to design a charger-deployment algorithm.

Although metaheuristic algorithms are potential methods to find better solutions [20,21], the optimal solution can only be found through a large number of iterations, thereby costing more computational time to converge. Therefore, excluding non-essential solutions is a necessary step. This paper makes two major contributions: (1) we used four metaheuristic algorithms to design the strategy for charger deployment; (2) we proposed a layoff algorithm to improve these metaheuristic algorithms and analyzed each algorithm to determine in which scenario it is suitable for the application.

The sections of this study are as follows. In Section 2, the background knowledge of wireless rechargeable sensor networks and related research papers are briefly described, analyzed and discussed. In Section 3, problem definition is introduced. The proposed schemes are presented in Section 4. The simulation results are shown in Section 5. Finally, the conclusions are discussed and future developments are proposed.

Wireless charging technologies can be divided into two categories according to their power sources. The first category involves using the power of nature, such as wind power and solar power. The power of nature will be changed to alternating current to power equipment. However, it will be limited in the environment; the sensor will die if the natural power is gone because it is not always sunny or windy. The second category involves power which is less influenced by the environment. The common charging techniques are as follows: (1) magnetic induction [22], (2) magnetic resonance [23], (3) laser light sensor [24] and (4) micro-wave conversion [25].

Some scholars mapped the charging problem as a Hamilton cycle and let the whole environment be divided into multiple clusters. They also proposed a greedy-based 26 algorithm to find a shortest path for charging. However, this method did not consider that some sensors have too little energy so that they will run out of energy before charging vehicles arrive [26]. In [27], the authors took Washington as an example. They tried to detect the number of pedestrians from infrared images and then figured out which area of pedestrians is the most intensive. The major goal of this work was to improve the survival rate of terminal devices. However, statistics-based methods usually do not have good environmental adaptability. In [28], the authors used unmanned aerial vehicles (UAVs) for charging. They can be used in the extremely rough terrain which cannot be traversed by self-propelled vehicles. The authors also divided the sensors into multiple clusters. The data of sensors were transmitted when the UAV was arriving for charging. Their proposed one-side matching algorithm considers the remaining power and distance of UAV flight to calculate the optimal charge-priority order. In addition, some scholars considered the collision avoidance [29], minimum number of disjoint shortest trees [30] and multiple self-propelled vehicles [31] to design a better charging plan. Most works adopted intermittent charging. This means that the charging process only begins when the self-propelled vehicle has arrived, and then it will stay in there until the termination condition is met. However, sensors will sense current as long as the self-propelled vehicle passes by them. In [32], the authors proposed a real-time charging method to extend network lifetime. The authors proposed a spatial-temporal discretization method in which each time block is independently assigned based on travel speed and the distance from the sensors. In other words, this method can optimize where to go to charge the sensors. For the indoor scenario, the authors of [19] proposed a greedy-based method to quickly deploy chargers. In [33], the authors adopted the concept of a center of gravity to find the best charging position and proposed a charging-schedule algorithm to increase the remaining-use durations of sensor nodes. In [34], the authors proposed a particle swarm charger-deployment algorithm that utilizes the local optimal result and the global optimal result to adjust locations and antenna orientations of chargers.

Most studies on WRSNs involve an outdoor scenario planning the path for charging a car or airplane, so it is necessary to further charging technology, including the indoor scenario. In our previous work, we proposed the minimum-charging-based algorithm (MCBA) to deploy charging in an indoor scenario and a novel means of reducing the deployment cost. They have the advantages of centralized power and a large charging area.

The MCBA step can be divided into two parts. The first is finding a candidate charger. The IoT is located by aGPS. We then map the transmission range of the sensor nodes to the ceiling. This means that the sensor will be charged if the charger is deployed there. The second is finding the optimal position where the charger will be finally deployed. The increased overlapping area means that the charger can cover more sensors. We used this point to find the better solution.

The most important deployment problem is that the power consumption of each sensor node differs because each sensor has its own sensing function and power consumption. Therefore, we must calculate the received power of each sensor:

where $P_{i,j}^S\left(d\right)$ represents that the $j^{th}$ sensor’s power received from the $i^{th}$ charger; $P_{i,j}^C$ represents power transferred from the $j^{th}$ charger to the $i^{th}$ sensor; $G_c$ is a value of antenna gains of the chargers; $G_s$ represents a value of antenna gains of sensor nodes; $\eta$ is a value of rectifier efficiency; $L_p$ is polarization loss; $\lambda$ is the wavelength of RF; $\beta$ is a unique adjustable parameter in an indoor environment. To ensure each sensor can be charged, the first step is to find the amount of power which the most power-hungry sensor needs. If the provided power can meet the requirements of the most power-hungry sensor, all of the sensors can receive enough power in this scenario. In view of this, we further define the ECD, as shown in Equation (2)

where R is ECD; $W_{Max}$ is the maximum power consumption of all sensors; N is the number of chargers needed for the most power-hungry sensor. We assume $P_{i,j}^S\left(d\right)=W_{Max}$; it represents that the most power-hungry sensor will run out of power received from the chargers. In other words, all of sensors will receive enough power when the distance of sensor to charger is between R. According this assumption, R is also equal to $d_{i,j}$. We can deduce Equation (1) by Equation (2).

We assume that all of chargers will provide the same power to have better fairness. The charging efficiency is better when the effective charging distance is less than R, and vice versa.

In this paper, we follow the method of finding the position of a candidate charger by our previously proposed method, MCBA. In order to decrease the deployment cost and reduce the chance of falling into the local optimum, we use a metaheuristic algorithm to solve this problem. According to the above-mentioned expected goal, we define a linear programing model for this problem:

The first step is that SABC creates a number of $N_c$ bits; the values of the bits are represented by 1s or 0s randomly. A value of 1 means that the candidate charger can be deployed in this position, whereas 0 means that the charger is not deployed. We set the experimental group and control group fairly. However, in copying the L neighbor solution, L is a value which can be freely adjusted by the user. The next step is to randomly change the status of bits and calculate f(x). If the solution meets the threshold of acceptance, the experimental group will be replaced; this process is repeated until the termination criterion is met.

In this section, we show the pseudocode of the algorithm. In the first step, we set an initial temperature by the annealing schedule and randomly created an initial solution $N_c$, as shown in lines 1–2 of Algorithm 1. To compare the quality of solutions, f(x) will be calculated for any just found solution, as shown in line 3. The next step is randomly choosing $C_i$ from each solution and changing the status shown in line 5. Line 6 shows that the original solution and new solution will calculate their f(x). We can replace the original solution if the new solution is better, and the temperature, as shown in lines 7–9, is also adopted. The last step is to update the temperature according to the SA rule. This process is repeated until the termination criterion is met.

Algorithm 1 SA-based charging algorithm (SABC)

SA-Based Charging Algorithm (SABC)

Input: $V_c,V_s$ Outpus: $V_E$ 1. Set the initial temperature according to the annealing schedule

2. Create the initial solution Nc randomly

3. Calculate the f(x)

4. While the termination criterion is met choice $C_i$ randomly

5.  Fitness Function (Nc, Ci)

6.  If quality is better and temperature is adapted

7.   Replace the solution

8.   Update temperature

9. End

 If f(x) is better and didn’t same with tabu list

The first step is to create L chromosomes. A difference from SA and TS is that the GA needs different chromosomes to evolve, so genes of the chromosomes have different statuses. In the second step, we need to calculate fitness function f(x). The third step is selection, which can choose a better solution by f(x). The fourth step is crossover. The fifth step is mutation. All of the above steps will repeat until the termination criterion is met.

 Randomly create the initial chromosome which length is N_c

      Choice the position by f_{ant (x)} and calculate f(x)

      update the online pheromone and update the S_covered

 Find the best solution and add the pheromone

Although metaheuristic algorithms can find the better solutions, they still have some defects. For example, they will require a lot of computational time to converge. As metaheuristic algorithms will continue to repeatedly match all of the solutions to find the best solution, this process will waste computation. The solution has a chance of falling into a local optimum when using a metaheuristic algorithm. As the deployment problem is a continuity problem, the candidate chargers which are deployed in the beginning can cover a greater area and have fewer overlapping areas. The coverage area will be smaller when the candidate charger continues to be deployed. This phenomenon will apparently occur when the sensor nodes are increased in number, so we propose using the layoff algorithm (LA) to solve it.

The concept of the LA has two parts. The first part involves removing useless candidate chargers to reduce the computational time. The second part is to ensure that the sensor nodes will be covered in each iteration. According to this concept, not only can the quality of the solution be promised, but it can also ensure that the lost-covered-sensor problem will not happen. We define fitness function as follows:

In the LA, the first step is randomly firing the candidate chargers and updating the CCL. If the CCL complies with the standard, the $S_{overlapping} \mathrm{i}\mathrm{s}$ calculated. If the CCL does not comply with the standard, it will randomly choose new $C_i$. The next step is to calculate $f\left(x\right)$. It can evaluate the quality of the solution.

Figure 2A,B show the deployment of SABC and LSABC; the blue points are sensor nodes. Green circles are charger areas. There were 400 sensor nodes randomly deployed. The simulation shows that SABC can cover most of sensor nodes, but the sensor node in the upper left corner is ignored. Conversely, LSABC can cover all of the sensor nodes. This means that SABC still cannot completely avoid falling into a local optimum.

The deployment of both ACOBC and LACOBC is shown in Figure 2G,H. The concepts of ACOBC and LACOBC completely differ. Ants will choose the best candidate charger in the ACOBC. In the LACOBC, ants will choose which candidate charger should be laid off. There was a problem when all of sensor nodes were covered: the ant would stop seeking the next node in GABC. In each iteration, the ants could not find all of nodes; this led to a worse solution.

In this section, we compare the number of chargers while the number of sensor nodes increased from 50 to 400. The x-axis represents the number of sensors, and the y-axis represents the number of chargers. To ensure objectivity and accuracy, all of the algorithms performed 1000 iterations.

Figure 3 shows a comparison of the number of chargers for SABC and LSABC. In the LSABC, if the number of sensor nodes increases, the curve of LSABC will tend to signify an exponential function. This phenomenon shows that the LSABC can effectively avoid falling into a local optimum. SABC’s deployment cost will increase when the number of sensor nodes increases.

The growth curves of LTSBC and TSBC are like those of LSABC and SABC. According to the coding method of SA and TS, they can be classified as a single solution. The layoff algorithm can help the single solution to have better quality; the benefit will be notable when the number of sensor nodes increases because the most important concept of the layoff algorithm is that all the sensor nodes will be covered in each iteration. The original solution is randomly created in SABC and TSBC. If the sensor nodes cannot be covered in the beginning, it is hard to guarantee that the sensor nodes can be covered in some other iteration.

Moreover, LGABC can strongly reduce the number of deployed chargers compared to GABC. To have better convergence in every iteration, the status of the candidate charger can only change from zero to one. In LGABC, the selection step will perform better in the condition of convergent data. Conversely, many deployed chargers will lead to a worse solution in the selection step; that is the reason why the number of chargers of GABC is double that in LGABC.

We can see that the simulation shows that LACOBC can reduce the deployment cost by at least a third, proving that the layoff algorithm can enhance the ACOBC’s ability to find a better solution. In ACOBC, the pheromones retain any candidate charger that is a good choice for next path, but ants will stop searching when all of the sensor nodes are covered. In other words, the sensor cannot check most of the paths. The deployment problem is continuous. This means that there are many combinations of paths, and ACOBC cannot check most of them, which is why ACOBC cannot converge.

Finally, the simulation indicates that the layoff algorithm can enhance SA, TS, GA and ACO in the deployment problem to reduce deployment cost. The enhanced performance is obvious in the LGABC and LACOBC.

The computational time of LTSBC is less than that of TSBC. The reason is the same as for TSABC; the layoff algorithm can remove unnecessary candidate chargers to reduce computational time. In LTSBC and TSBC, most of the computational time is used for calculating covered sensor nodes and checking the tabu list, so it will take more computational time than TSABC.

In LGABC and GABC, the computational time is used for checking which sensor nodes are covered by candidate chargers. The computational time will increase if more candidate chargers are deployed. The layoff algorithm can improve the convergence of LGABC, so the computational time can be reduced at the same time.

The computational time of LACOBC is less than that of ACOBC; thus, LACOBC will record the CCL in the beginning. However, ACOBC will calculate the number of covered sensor nodes when ants arrive at a new node in every iteration, and it will require more computational time. The difference in computational time between LACOBC and ACOBC will be large if the sensor nodes increase. The layoff algorithm uses the CCL table to record the covered sensor nodes and change the method used to find the solution; this application reduces the computational time.

Obviously, LGABC and LACOBC will require more computational time than LTSABC and LSABC because they are complicated methods. In LTSBC or LSABC, there is only one solution in every iteration, whereas LGABC and LACOBC have multiple solutions in every iteration; therefore, they will require more computational time to find the best solution.

Figure 5 shows the comparison of the energy efficiency with original algorithms and layoff versions. The energy efficiency of LSABC is better than that of SABC because LSABC can use fewer chargers to deploy in this environment. In other words, each sensor node can receive enough energy, as there are no useless chargers to add for overlapping areas.

In the LGABC, the layoff algorithm ensures that all of the sensor nodes will be covered in each iteration, and it will remove useless chargers in the mutation. LGABC can find better solutions through the above-mentioned method. In other words, LGABC can decrease overlapping areas, and the energy efficiency will be increased at the same time.

LACOBC can efficiently decrease the overlapping area. The reason is that LACOBC can check the status of coverage of all the sensors and ensure that LACOBC will not remove the important candidate chargers. For example, there is a sensor node which is only covered by one candidate charger; therefore, we cannot remove this charger because all of sensor nodes should be covered. Obviously, the simulation shows that the LA can enhance ACOBC to find the better solution and decrease overlapping areas.

This simulation showed that the curve of energy efficiency will exhibit negative growth when the number of sensors decreases because the overlapping area will affect the quality of energy efficiency, and overlapping areas increase as the sensor nodes increase in number. The relationship of the number of chargers and energy efficiency is not a positive correlation. If there are many chargers and less overlapping area, it will still have high energy efficiency; this is the reason why energy efficiencies of LSABC and LTSBC will be close to those of SABC and TSBC.

The time complexity of SABC depends on several factors, such as the amount of input data, the cooling schedule, and the convergence criterion. The main steps of SABC include generating initial solutions, calculating their objective functions’ values, generating neighboring solutions by applying random perturbations and accepting or rejecting them based on a probability determined by the current temperature. The number of iterations required for SABC to converge to a near-optimal solution depends on the cooling schedule and the convergence criterion. The cooling schedule determines the rate at which the temperature is decreased during the search. A slower cooling schedule can result in a longer runtime but can also increase the probability of finding a near-optimal solution. On the other hand, a faster cooling schedule can result in a shorter runtime but can also decrease the probability of finding a near-optimal solution. The convergence criterion determines when the search is terminated. SABC is terminated when the temperature falls below a certain threshold or when a maximum number of iterations is reached. Overall, the time complexity of SABC can be approximated as O(kn), where n is the size of the input dataset and k is the number of iterations required to converge to a near-optimal solution.

The layoff algorithm can efficiently remove the solution that cannot lead to an optimal solution. It needs to be used with SABC, TSBC, GABC and ACOBC. The time complexity of layoff algorithm can be approximated as O(k), where k is the number of generations required to converge to a near-optimal solution and n is size of the input data. Compared with the algorithm before adding the layoff approach, time complexities are similar to the original algorithm. However, the layoff approach is more efficient in practice, due to its ability to remove unnecessary solutions.

In this paper, we aimed to solve on the indoor charging planning problem of WRSNs. Four metaheuristic algorithms and an optimization method were proposed. In the results, we can see that the proposed metaheuristic algorithms can achieve more efficient fixed charger deployment than the original method can. In addition, in the proposed enhancement method, the layoff algorithm can efficiently reduce the number of deployed chargers, guarantee coverage and get a faster convergence rate. Sometimes, some chargers may serve only a few sensors, so such charger deployment is not cost-effective. In future works, WRSN planning in dynamic environments will be considered.

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.