Wireless Energy Harvesting for Internet-of-Things Devices Using Directional Antennas

Abstract

With the rapid development of the Internet of Things, the number of wireless devices is increasing rapidly. Because of the limited battery capacity, these devices may suffer from the issue of power depletion. Radio frequency (RF) energy harvesting technology can wirelessly charge devices to prolong their lifespan. With the technology of beamforming, the beams generated by an antenna array can select the direction for wireless charging. Although a good charging-time schedule should be short, energy efficiency should also be considered. In this work, we propose two algorithms to optimize the time consumption for charging devices. We first present a greedy algorithm to minimize the total charging time. Then, a differential evolution (DE) algorithm is proposed to minimize the energy overflow and improve energy efficiency. The DE algorithm can also gradually increase fully charged devices. The experimental results show that both the proposed greedy and DE algorithms can find a schedule of a short charging time with the lowest energy overflow. The DE algorithm can further improve the performance of data transmission to promote the feasibility of potential wireless sensing and charging applications by reducing the number of fully charged devices at the same time.

1. Introduction

Nowadays, many devices have increased dramatically with the rapid development of the Internet-of-Things (IoT). Numerous sensing devices have been developed for the applications of smart homes/cities/offices [1]. Nevertheless, owing to the limited capacity of batteries, efficient energy saving to prolong the lifetime of devices is crucial. Traditional implementation focuses on reducing energy consumption using various energy-saving strategies. Recently, researchers have proposed various energy-harvesting technologies with different renewable energy resources, like conversions from piezoelectric energy, winds [2], solar energy [3], mechanical vibration [4], and electromagnetic energy. One of the most important technologies is wireless energy transfer (WET), in which devices can convert radio frequency (RF) into electrical energy to charge themselves [5]. The RF technology can be widely used in various networks, like sensor networks or cognitive radio networks. With the technology of RF energy harvesting, wireless sensor devices do not need to replace batteries.

RF energy harvesting can be performed based on two types of antennas: omnidirectional antenna or directional antenna. In general, the access point (AP) is equipped with antennas fixed at specific locations. Omnidirectional antenna can transmit energy in all directions; thus, all devices in the transmission range can receive RF energy at the same time. However, due to the lower antenna gain of the omnidirectional antenna, the transmission range is relatively short [6]. On the other hand, the directional antenna can transmit energy in only one direction each time. The area of radio transmission is called the direction sector. Devices in the sector receive RF energy from the power source. Because directional antennas usually have higher antenna gain, their transmission ranges are relatively long compared to omnidirectional antennas [7]. However, multiple directional antennas are required to cover all directions. Beamforming technology has been proposed to improve the implementation of RF energy harvesting. The technology of beamforming employs an antenna array composed of multiple antennas and exploits the spatial domain to gain extra degrees of freedom. Furthermore, it can generate pencil beams to focus the signal in a narrow direction [8]. In practice, an AP needs accurate knowledge of channel state information (CSI) from/to devices to increase energy beamforming gain. Although the design and implementation of the base station is complicated due to the requirements of CSI and the antenna array [9], the charging time of the devices can be significantly reduced.

With the technology of beamforming and WET, it is important to choose a series of appropriate directions for energy transmission. To charge devices to the target battery level, we should have a set of time periods for different directions. Furthermore, when the battery of a device is full, it may perform some specific tasks, e.g., transmitting data to the AP or performing some calculation or upgrading tasks. If a lot of devices are fully charged at the same time, the simultaneous data transmission may cause interference among different devices and the simultaneous computation/upgrade overhead may result in sensing service interruption. To avoid the above issues, it is desirous to gradually increase the number of fully charged devices. In terms of energy overflow of the battery, reducing overflow is equivalent to reducing the number of devices that are fully charged at the same time. To the best of our knowledge, none of the previous work addresses the problem of shortening the charging time and improving the performance of data transmission for charged devices.

In this work, we are motivated to propose two algorithms to shorten the recharging time and minimize battery overflow for devices. The proposed greedy algorithm selects a sector to be charged in a greedy manner, in which each sector may overlap with each other. By adaptively adjusting the overlapping area between two sectors, the charging efficiency can be improved to shorten the charging time. Our second algorithm based on DE further minimizes battery overflow while keeping the charging time short. The results of the experiment show that, compared with the baseline algorithms, the proposed greedy algorithm can shorten the charging time by up to 55% and the DE algorithm can reduce wasted energy by up to 70%. Furthermore, the DE algorithm can improve the data rate of the devices by more than 160%.

The main contributions of this work are summarized as follows.

• We proposed two algorithms, greedy and DE, for different purposes. The greedy algorithm is designed to minimize the charging time and the DE algorithm can achieve a better performance for energy overflow minimization. The greedy algorithm attempts to charge devices as early as possible by rotating the direction of the directional antenna’s beam. The DE algorithm jointly considers the issue of battery overflow to reduce the number of fully charged devices at the same time.
• To gradually increase the number of fully charged devices, the problem of minimizing both energy overflow and charging time is formulated as a joint optimization problem. Therefore, the algorithm proposed for the optimization problem can pursue a charging schedule that may reduce the number of fully charged devices at the same time.
• We conduct a comprehensive performance evaluation to demonstrate the performance of our scheme. The experimental results show that both greedy and DE algorithms can achieve a short charging time and the proposed DE algorithm can further reduce the amount of energy wasted by charged devices. We also show that, by reducing the number of fully charged devices at the same time, the performance of data transmission can be improved.

The remainder of this paper is organized as follows. In Section 2, we discuss some previous literature. In Section 3, we introduce our system model and formulate the research problem. In Section 4, we describe the proposed greedy and DE algorithms. Section 5 discusses the simulation results and Section 6 concludes this work.

2. Related Work

2.1. Energy Harvesting Applications

Energy harvesting technology is widely used in IoT and mobile edge computing (MEC) [1,2,3,5,6,7,8,9,10,11,12,13,14,15,16]. Owing to the capacity-limited battery, the lifetime of wireless devices or sensor devices is an important issue discussed in numerous studies. There are several sources of energy harvesting, namely renewable energy [3,11,12], radio frequency [1,5,6,7,8,9,12,13,14,15,16,17], resonant coupling [10], etc.

Park et al. proposed an AmbiMax system to perform maximum power point tracking to manage multiple power sources simultaneously and automatically [2]. Fan et al. proposed a method of fair and high throughput with solar energy [3]. Zhang et al. concluded that a node must collect RF energy for at least 150 s to support node activity within 100 ms by analyzing the lifetime of IoT nodes based on RF energy harvesting [13].

Galinina et al. discussed the difference between the omnidirectional antenna and the directional antenna and explored the feasibility of wireless-powered wearable devices [6]. To detect the underlying devices of the charge and activity sensor, Sandhu proposed kinetic energy harvesters as context sensors and energy sources simultaneously [11].

Wang et al. aimed to find the optimal path for a mobile charger [9]. They proposed a greedy bundle generation algorithm and a TSP-based solution by considering adjacent charging locations. Prawiro et al. proposed a SmartCharge system to meet the requirement of a community for wireless charging solutions without interfering with device usage and movement [10]. The system also allows multiple devices to be used simultaneously. Nguyen et al. proposed an energy-harvesting-aware routing algorithm to improve both the lifetime of sensor devices and QoS under dynamic traffic load and variable energy availability [12].

Bi et al. considered a multi-user MEC network powered by wireless power transmission [17]. Because of the combinatorial complexity of multi-user computation offloading, a coordinated descent method is proposed to optimize the decisions of computation offloading. Shi et al. considered a NOMA-based WET-MEC network and proposed a Dinkelbach-based iterative algorithm to maximize computation energy efficiency [8].

Tran et al. proposed a new idea of harvesting RF energy from Wi-Fi transmission combined with beamforming [1]. They applied the idea to a prototype wearable device that can capture and transmit accelerometer data. Wen et al. attempted to minimize the system energy consumption based on beamforming and computation offloading [14]. They also used relay technology to solve the degradation of transmission performance caused by long distances.

2.2. Improvement of Energy Harvesting

The efficiency of energy harvesting has been discussed in numerous studies [5,7,15,18,19,20,21,22,23,24,25]. Existing research includes hardware implementations [18,19] and software [5,7,15,20,21,22,23,24,25] implementations.

For hardware implementation, Lee et al. proposed a new approach to receive more energy in wide-angle convergence by using a hybrid power combining rectenna array [18]. Shen et al. showed that the shortcoming of average output DC power in ambient RF energy harvesting is nonlinearly dependent on antenna directivity and linearly dependent on the antenna port number [19]. Accordingly, they designed a directional 4-port pixel patch rectenna system to maximize average output DC power. For the directional energy transmission, Wang et al. aimed to decrease the energy consumption of IoT nodes [5].

In addition to proposing a node scheduling method to increase sleep nodes, an adaptive RF energy management method is proposed to automatically switch between data and energy modes, where the transmitter can monitor and control the voltage to adjust the charging intensity. Ko et al. proposed an observation-based directional energy transmission algorithm for dynamically distributed IoT nodes [7]. The method can measure the high energy-efficiency sector and transmit RF energy to the selected sector. It is divided into two stages, namely sensing and transmission. In order to improve efficiency of energy harvesting, the probability of a high-energy-efficiency sector is increased by the detection stage. Ko et al. proposed a phase-aware algorithm for the directional energy transmission based on multiple transmitters [15]. The RF energy waves can be combined either constructively or destructively by phase difference. The proposed method maximizes harvested energy with low energy consumption and a packet discard rate. There are several metaheuristic algorithms used for energy harvesting. Sun et al. utilized the DE algorithm to optimize the energy efficiency [20]. They established an object function related to the total number of transmitted bits and the total energy consumption of the system. Li et al. proposed the artificial fish swarm algorithm to identify the optimal scheduling under the constraint of transmission energy [22].

Recently, there have been several algorithms based on reinforcement learning. Min et al. proposed a reinforcement learning algorithm to learn the transmission rate, the current battery level of IoT devices, and predict the renewable energy harvesting model in order to determine the next decision [23]. Luo et al. ensured that the AP can use the collected energy efficiently [24]. Their method uses deep Q learning to control transmit power, meet the data-rate requirement of users, and ensure devices harvest enough energy. Ren et al. designed a two-layer Q-learning method to maximize the energy efficiency of AP and devices [25].

2.3. Beamforming

Recently, beamforming technology has been widely discussed and applied [26,27,28,29]. Alsaba et al. mentioned that beamforming is composed of multiple beams from the antenna array with four or eight antennas [26]. The antenna array can adjust the transmission direction by combining beams between antennas. Hiep et al. adopted the beamforming for transmitting information and energy to improve the performance of the NOMA multiuser systems [27]. Li et al. proposed an online energy consumption minimization algorithm with latency constraints in order to minimize the energy consumption of multiple devices [28]. Wang et al. considered a full-duplex wireless-powered communication network, in which the AP is equipped with an antenna array to transmit energy to devices and receive information from devices [29]. They proposed a wireless energy allocation scheme based on space division to optimize energy allocation between users under the max–min user fairness constraint. In summary, we attempt to combine the energy harvest with beamforming to improve the energy efficiency of wireless sensor devices.

2.4. Research Gap

We summarize the related works in

Table 1. Summary of previous works.

Reference	Beamforming	Battery	Research Goal
[5]	None	No	Minimizing energy consumption with single
			WET source
[7]	None	Yes	Optimizing sectors for single WET source
[15]	None	Yes	Optimizing directions and phases of multiple
			WET sources
[20,22]	None	Yes	Optimizing WET time period for computation
			Tasks
[23]	None	Yes	Predicting WET for computation tasks
[24]	None	Yes	Optimizing WET time period for data
			Transmission
[25]	None	Yes	Optimizing WET time period and avoiding
			energy overflow
[28]	Yes	Yes	Minimizing energy consumption with single
			WET source
[29]	Yes	No	Optimizing WET time period for data
			transmission

. Most previous works have focused on improving the performance of energy harvesting based on the demands of task computation or data transmission. However, these works do not attempt to improve the performance of data transmission by arranging the charging completion time of charged devices. We are thus motivated to reduce charging time and improve the performance of data transmission by minimizing the energy overflow.

3. System Model

3.1. Architecture of RF Energy Harvesting

Figure 1 shows the architecture of RF energy harvesting. There are two components in the RF energy-harvesting architecture: rechargeable devices, and the access point (AP). The rechargeable devices are equipped with an omnidirectional antenna and RF-DC converter around the AP. The omnidirectional antenna receives RF energy from the AP, and the RF-DC converter converts received RF energy to electricity. We assume that there are N devices located under the radio coverage of the AP. Due to the limitations of our model, the charge level of devices too close to the AP will be distorted, so there will be no devices within a range of 1 m. The AP is a base station that receives data from devices, and it is also a charging station equipped with an antenna array which can transmit RF energy to devices. The devices whose battery level is higher than a threshold value can transmit data to the AP. The AP and devices share the same frequency band by means of a time division duplex (TDD); namely, wireless energy transfer and data transmission do not take place at the same time.

In practice, beamforming requires accurate channel state information (CSI). Therefore, the AP needs to know the accurate CSI to achieve large energy beamforming gain. We assume that the AP may consume energy to estimate the CSI from a dedicated device.

3.2. Channel Model

RF energy is assumed to undergo path loss attenuation during transmission. Path loss attenuation is affected by $\alpha$, where $\alpha$ is a path loss exponent varying between 2 and 6. The value of $\alpha$ is influenced by the environment. We assume that $d_i$ is the Euclidean distance between the charged device i and the AP, and $d^{-\alpha }$ is the path loss attenuation. The channel gain of device i is indicated by $h_i$. $\mu$ is the energy conversion efficiency of converting RF energy to DC via a recharged device. The value of $\mu$ can be used to estimate the energy acquired by the device. In this work, we assume that the energy conversion efficiency is a constant to simplify the calculation. $P_t$ is the transmission power in Watts, and $P_r^i$, the power received by device i, can be expressed by Equation (1) [22,27,28]. The battery level of device i in Joules is updated by Equation (2), where $B_i\left(t\right)$ is the current battery level, and $B_i(t+1)$ is the battery level in the next time interval.

$$P_r^i=P_t{d}_i^{-\alpha }{h}_i{G}_t{G}_r\mu$$

(1)

$$B_i(t+1)=B_i\left(t\right)+P_r^i\times \mathit{one\; time\; unit}$$

(2)

3.3. Antenna Model

The omnidirectional antenna can receive the RF signal from all directions, so its antenna gain $G_r$ is one. Directional antennas can only receive RF signal in a fixed direction, so the antenna gain $G_t$ is expressed by Equation (3), where ${\theta }_t$ is the transmission angle. The value of ${\theta }_t$ is determined by the difference of two azimuth angles used to indicate the area covered by the RF signal.

$$G_t=\frac{2\pi }{{\theta }_t}$$

(3)

Because the realistic directional antenna model is complex and difficult to implement, we adopt a typical simplistic antenna model, a sector model, instead of a realistic directional antenna model, as shown in Figure 2. Given a transmission angle, ${\theta }_t$, the dotted line represents a realistic directional antenna’s beam. We can see that there are few beams behind the directional antenna. The solid line represents the beam of the sector model.

3.4. Sector Model

We express the harvesting environment topology in the Cartesian coordinate system. The directional antenna has a fixed transmission angle. We divide the coordinate into S transmission regions, as shown in Equation (4). The charging station transmits RF energy to each region iteratively. The devices in each sector are identified by response messages from devices receiving RF signals [7]. When a device is fully charged, it will also transmit a message to inform the AP.

We assume that the charging station can change the transmission direction without switching time. The charging sequence is performed in a counterclockwise direction. $\varphi$ is the angular coordinate representing the start end of the transmission direction based on polar coordinates. $\Delta$ is an offset angle. $\varphi$ will be changed by $\Delta$ counterclockwise until it completes one cycle. We show an example in Figure 3. Figure 3a indicates that the initial transmission direction is represented by $\varphi =0$ and ${\varphi }_t=90$. Figure 3b shows the next transmission direction, $\varphi =30$, where the angle offset $\Delta$ is 30.

$$S=\frac{360-{\theta }_t}{\Delta }+1$$

(4)

3.5. Problem Formulation

In this section, we formulate our research problem. We aim to jointly consider the total charging time consumed by the AP and the wasted energy in the charged devices. Our purpose is to find an appropriate schedule of per-sector charging time with minimized energy overflow. Because the charging time and energy overflow have different measures, we normalize the values of time and wasted energy between 0 and 1. The $N_t$ is the normalized time calculated using Equation (5). $x_j$ is the charging time of sector j, and the $t_{\max }$ is the longest charging time of all sectors, i.e., $t_{\max }=\max x_j,1\le j\le S$.

$$N_t=\frac{{\sum }_{j=0}^S{x}_j}{S\times t_{\max }}$$

(5)

The $N_e$ is the normalized energy overflow for D devices calculated using Equation (6). $e_i^w$ denotes the wasted energy of device i and $e_{max}$ is the most wasted energy among all devices, i.e., $e_{max}=\max e_i^w,1\le i\le D$. The value of $e_i^w$ is calculated in Equation (7), where device i is in sector j and $\beta$ is the battery capacity of a device.

$$N_e=\frac{{\sum }_{i=0}^N{e}_i^w}{S\times e_{\max }}$$

(6)

$$e_i^w=B_i+(P_r^i\times x_j)-\beta$$

(7)

Our object function is formulated as Equation (8):

$$\min N_t\times N_e,\mathrm{subject}\mathrm{to}$$

(8)

$$x_j\ge 0,e_i^w\ge 0,\forall i\in D,\forall j\in S$$

(9)

$$B_i+P_r^i\times x_j\ge \beta ,\forall i\in D,\forall j\in S$$

(10)

This paper aims to yield a battery-charging schedule with minimized energy overflow. Basically, a better solution has smaller values of the $N_t$ and $N_p$. The constraint in Equation (9) ensures that both values of harvesting time and wasted energy are positive. The constraint in Equation (10) requires that each device must be fully charged.

4. Energy Harvesting Using Directional Antenna

In this section, we propose two algorithms for charging time scheduling. First, we present a greedy algorithm to find a solution of minimized charging time. Then, we propose an algorithm of differential evolution (DE), a metaheuristic used to yield a better solution based on the solution generated by the proposed greedy algorithm.

4.1. Greedy Algorithm

When the AP starts up a cycle of wireless energy transfer, we assume that the energy transfer of the AP starts from the direction of 0 degrees on the x-axis and rotates the offset degree counterclockwise. In each sector, the devices receiving RF signals notify the AP by transmitting response messages. When a device is fully charged, it will also transmit a message to inform the AP. If there are devices on the current direction to be charged, the rotation is stopped in order to charge the devices on the current sector. Otherwise, the AP continues to rotate the direction of energy transfer.

The pseudo code of the proposed greedy algorithm is shown in Algorithm 1. Lines 2 to 24 show the process of the AP scanning a circle. First, we determine if the current sector is the last one. If the answer is negative, we record devices of the current and next sectors in line 4 and line 5. Moreover, if there are devices which will not be charged after the charging direction is rotated by the offset, these devices must be fully charged in lines 6 to 12. In addition, we record the charging time and update the battery levels of different devices. If the current sector is the final sector, we check if the sector is empty in line 14 to line 15. If the answer is negative, the remaining devices will be fully charged in lines 16 to 22. Similarly, we also record the charging time and update the battery levels of different devices. Then, we compute the overflow energy for all devices in line 25. Finally, the algorithm returns the schedule of charging time in each sector, the total charging time and total overflow energy in line 26.

We use an example with 10 devices in Figure 4 to illustrate the proposed greedy algorithm. The transmission direction of the AP starts from the direction of 0 degrees on the x-axis. If there are devices covered by the current sector that are not covered by the next sector, these devices will be fully charged. The other devices in the same sector are also charged at the same time. Then, the fully charged devices are skipped by the next sector. In Figure 4a,b, we can observe that nodes 1 and 2 should be fully charged in the first sector. Another three devices are also charged in the sector at the same time. After rotating the transmission direction with the offset degree as shown in Figure 4c,d, we can observe that node 3 is the one to be fully charged, but it has been fully charged with nodes 1 and 2. As a result, the transmission direction is rotated again to skip this iteration. In the next iteration, nodes 4 and 5 will be fully charged, and so on. We note that the process of charging different sectors is controlled by the AP. Since the AP can communicate with devices, a sector with only fully charged devices can be skipped because no device will ask for charging.

Algorithm 1 Greedy

Require:  The set of the sector S, The set of the battery energy level $B_n$ Ensure:  X, T, $WE$ 1: $T=0$, $WE=0$, $X=\left[\right]$ 2: for each $s_j\in S$ do 3:     if $s_j$ is not the last sector then 4:         $set=s_j$ 5:         $se{t}^{\prime }=s_{j+1}$ 6:         if $set-se{t}^{\prime }$$\ne \varnothing$ then 7:             $wfh=set-se{t}^{\prime }$ 8:             compute t by Equ(1) 9:             $T+=t$ 10:            Harvest($set$, t) 11:            X.append(t) 12:       end if 13:   else 14:       if $s_j==\varnothing$ then 15:           $t=0$ 16:       else 17:           $wfh=set$ 18:           compute t by Equ(1) 19:           $T+=t$ 20:           Harvest($set$, t) 21:           X.append(t) 22:       end if 23:   end if 24: end for 25: $WE$ = WasteEnergy(X) 26: return X, T, $WE$

4.2. Differential Evolution

Differential evolution is a classic metaheuristic algorithm for complex optimization problems [21]. There are three main functions in the DE algorithm, namely mutation, crossover, and selection, as shown in Figure 5. They are performed sequentially and iteratively to efficiently search the solution space. The differential evolution algorithm is performed upon a set of solutions, in which each solution is an individual and the solution set is the population. Each solution yielded by the differential evolution algorithm is evaluated by the fitness function. Next, we describe each component of the differential evolution algorithm in detail.

As shown in Figure 6, an individual of the DE algorithm is composed of genes, and the population is composed of individuals, where NP is the population size. The increase in the NP can improve the diversity of the population and enhance the quality of the best solution. Nevertheless, a higher value of NP also increases the computation overhead to degrade the convergence performance. In contrast, reducing the value of NP can improve the convergence speed, but also lead to a higher probability of only yielding locally optimal solutions.

Fitness value represents the quality of an individual. Our fitness value is calculated by Equation (8), in which an individual with smaller fitness has a better performance. The variation among fitness values of the population could determine the diversity of the differential evolution algorithm. Next, we introduce the operation of each step of the DE algorithm.

4.2.1. Initialization

Each individual in the population is initialized by Equation (11), where ${x_i}^j\left(g\right)$ is $i_{th}$ individual, $j_{th}$ dimension and $g_{th}$ generation. ${L{B}_i}^j$ and ${U{P}_i}^j$ are the lower and upper bounds of the $i_{th}$ individual and $j_{th}$ dimension. Rand(0, 1) is a random number uniformly distributed in [0, 1]. We also include an individual generated by the proposed greedy algorithm.

$$x_i^j\left(0\right)=L{B}_i^j+\mathrm{Rand}(0,1)\ast \left(U{P}_i^j-L{B}_i^j\right)$$

(11)

4.2.2. Mutation

The mutation strategy we used is a random approach, DE/rand/1, where three individuals, r1, r2, and r3, are randomly chosen from [1, 2, 3 … NP]. Moreover, these individuals must have distinct values. A mutual vector, $v_i^j$, is calculated using Equation (12):

$$v_i^j(g+1)=x_{r1}^j\left(g\right)+F\left(x_{r2}^j\left(g\right)-x_{r3}^j\left(g\right)\right),$$

(12)

where $x_{r2}^j\left(g\right)-x_{r3}^j\left(g\right)$ is a difference vector. F is a scaling factor used to control the value of the difference vector. The value of the scaling factor is usually between [0, 2]. A small value of F can reduce the convergence speed of the differential algorithm, and a large value of F may keep the population from convergence. If the generated individual, $v_i^j$, is out of the boundary vector, it is adjusted according to the boundary vector in Equation (13).

$$v_i^j=\left\{\begin{array}{c}LB,\mathrm{if}{v}_i^j<LB\\ UP,\mathrm{if}{v}_i^j>UP\\ v_i^j,\mathrm{elsewhere}\end{array}\right.$$

(13)

4.2.3. Crossover

After performing the operation of mutation, we use the crossover function to recombine two individuals, v and x, in order to generate the final trial vector, u, by Equation (14). The operation of the crossover can create new individuals. The new individuals inherit the excellent genes from their parent, so they can adapt to the environmental requirements better than the individuals of previous generations. $CR$ is the hybridization probability, which is a weight used to adjust the current and historical information. The value of $CR$ may affect the population diversity. A lower $CR$ value uses less information from the variation vector and increases the difficulty of finding the global optimal solution. In contrast, a higher $CR$ value may increase the population diversity to avoid the local optimal solution and yield a global optimal solution, but a high $CR$ value may keep the population from convergence. $j_{rand}$ is randomly chosen from $[1,2,3\cdots \mathrm{NP}]$.

$$u_i^j(g+1)=\left\{\begin{array}{c}{v}_i^j(g+1),\mathrm{if}\mathrm{Rand}(0,1)\le CR\mathrm{or}j=j_{rand}\hfill \\ x_i^j\left(g\right),\mathrm{elsewhere}\hfill \end{array}\right.$$

(14)

4.2.4. Selection

After performing the crossover function, we calculate the fitness values of u and x in Equation (15). According to the fitness value, the section function selects the best individuals by keeping them in the population. If the trial vector is better than the target vector, it replaces the target vector. Otherwise, the trial vector is abandoned.

$$x_i^j(g+1)=\left\{\begin{array}{c}{u}_i^j(g+1),\mathrm{if}f\left(u_i^j(g+1)\right)<f\left(x_i^j\left(g\right)\right)\hfill \\ x_i^j\left(g\right),\mathrm{elsewhere}\hfill \end{array}\right.$$

(15)

4.2.5. DE Algorithm

The pseudo code of the proposed DE algorithm is listed in Algorithm 2. Initially, the greedy algorithm in Algorithm 1 is executed to obtain a greedy solution in line 1. Then, line 2 generates feasible solutions to fill the population. Lines 3 to 8 are the core operations of DE, where the functions of mutation, crossover and selection are performed iteratively. The mutation function improves the diversity of solutions and the crossover function preserves better genes. Then, the selection function chooses the best individuals. The best solution with the minimum fitness value is recorded throughout all generations. Finally, lines 9 and 10 calculate the amount of overflow energy and total charging time.

Algorithm 2 DE

1:   $x_g$, $T_g$, $W{E}_g$ = call Algorithm 1 2:   Initialization(X,$x_g$) 3:   for $i=1$ to $iteration$ do 4:       mutation(X) 5:       crossover(X) 6:       selection(X) 7:       $bestX$ = the best individual with the minimum fitness 8:       $minf$= the fitness of $bestX$ 9:   end for 10: T = sum($bestX$) 11: $WE$ = WasteEnergy($bestX$) 12: return T, $WE$

5. Simulation Results

5.1. Experiment Settings

In our experiments, we measure the performance of charging time and overflow energy. The number of devices varies from 30 to 40 to 50. The minimum distance between user and AP is 1 m, and the maximum distance is $5\sqrt{2}$ m. Meanwhile, we set three different transmission-direction offsets, of 10, 5, and 3 degrees, and three transmission angles, of 90, 60, 30 degrees. The transmission power of the AP is 5 Watts, the battery capacity is 5 Joules, and the conversion efficiency is 60%. The parameters of our experiments are listed in

Table 2. Simulation Parameters.

Parameters	Value
Topology	Uniform
Number of Devices	$[30,40,50]$
The minimum device distance	1 m
The maximum device distance	$5\sqrt{2}$ m
Offset value	$[3,5,10]$ degree
Transmission angle	$[30,60,90]$ degree
$P_t$	5 W
$B_{max}$	5 J
Conversion rate $\mu$	$0.6$
Population size NP	50
Scaling factor F	$0.3$
Hybridization probability CR	$0.8$
Upper bound	$t_{max}$
Lower bound	0
Generation	1000

.

We show the performance of the proposed greedy and DE algorithms. We use the Python-based scikit-opt for the implementation of DE [30]. Our algorithm is compared with three methods, namely Random, Round Robin, and Fix. These methods are described below.

• Random (RAN): The AP randomly chooses any direction to transfer energy for one second until all devices are fully charged.
• Round Robin (RR): The AP transmits energy in counterclockwise order for one second until all devices are fully charged.
• Fix: The AP has one antenna for one fixed direction. The number of the sectors is equal to the number of antennas.

5.2. Parameters of DE

We first show the convergence performance of the proposed DE algorithm. Figure 7 shows the best fitness value of each generation. The curve in the figure gradually decreases as the number of generations increases. The result shows that the operations of our DE algorithm can yield better solutions. The proposed DE algorithm also has good convergence performance, in which the improvement of each generation is reduced after 150 generations and the best solution is yielded in about the 700th generation. The proposed DE algorithm can thus generate feasible results with reasonable computation cost.

We further show the performance of the DE algorithm with respect to different values of scaling factor. As shown in Figure 8, when the value of F is within the range from 0.1 to 0.3, we can observe that the fitness value decreases as the F value increases. The value of F is related to the step size of the next generated solution. If the step value is too small, the DE algorithm could be trapped in the locally optimal solution. When the value of F is within the range from 0.4 to 0.9, the fitness value is increased for a larger F value. However, a large step value could degrade the convergence performance. In the following experiments, we set the F value to 0.3.

Next, we show the performance of the DE algorithm for different values of hybridization probability, which can balance the tendency between global and local searches for the DE algorithm. As shown in Figure 9, when the value of CR is within the range from 0.1 to 0.7, the value does not fluctuate severely because a small CR value may cause the DE algorithm to become trapped in locally optimal solutions. When the value of CR is increased to the range from 0.8 to 0.9, the better solution could be yielded. However, a higher CR value may also lead to slow convergence. In the following experiment, we set the CR value to 0.8.

5.3. Comparative Performance Evaluation

In the section, we evaluate the performance of our algorithms as well as three methods: Fix, RAN and RR.

5.3.1. Different Number of Devices

We show the charging time of different schemes for different numbers of devices in Figure 10 by setting the transmission angle to 90 degrees and the offset value to 10. The results show that the proposed greedy algorithm has the shortest charging time compared to other methods. We also observe that the charging time of the DE method is slightly worse than that of the greedy algorithm for different numbers of devices. The charging time of the Fix method increases as the number of devices increases, where the charging time is about 60 s for different number of sensor devices. The RAN method may arbitrarily select a transmission direction to result in charging some devices that have been fully charged. The RR method has a similar problem to the RAN method. Both the RAN and RR methods suffer from a high charging time regardless the number of devices mainly because of the poor charging efficiency for those distance devices.

We show the performance of the overflow energy for different methods in Figure 11. The overflow energy is related to the charging time and the selected transmission directions. The Fix method results in the most overflow energy for 50 devices because the devices are more distant. Both RAN and RR methods lead to a higher amount of wasted energy because of redundant charging. The RR method slightly outperforms the RAN method because the RAN method repeatedly charges devices. Both the proposed greedy and DE algorithms outperform the other methods. Although the DE algorithm requires a slightly longer charging time than the proposed greedy algorithm in Figure 10, it achieves the least overflow energy. In particular, the DE algorithm improves the overflow energy of the greedy algorithm by 12.9%, 9%, and 7.8% for 30, 40, and 50 devices. The improvement decreases as the number of devices increases because having more devices in a sector may result in more devices with overflow energy. We believe that the tradeoff between a slightly longer charging time and less overflow energy is reasonable.

5.3.2. Different Transmission Angles

Next, we use three different transmission angles, 30, 60 and 90, to show the performance for different schemes. Figure 12 shows the charging time for 30 devices and the offset value, 10. We observe that the charging time of DE, RAN, RR decreases with smaller transmission angles. Because the antenna gain is related to the transmission angle, a small transmission angle can provide a narrow transmission beam to increase the antenna gain as well as the amount of energy received. Thus, the received energy of 30 degrees is higher than that of 60 and 90 degrees. However, a small transmission angle also results in more sectors. If the number of sectors increases, our DE algorithm may consume considerable computation time owing to the lengthy solution. All of these methods also require more charging iterations for all sectors. In particular, the charging time of DE is 54.1, 40.9, 31.9 s for 90, 60, and 30 degrees. The Greedy algorithm can still shorten the charging time effectively. Fix can improve its charging time efficiency with narrow transmission angle, so do RAN and RR.

We further show the overflow energy in Figure 13. We can see that the greedy algorithm also outperforms the Fix method because of the optimization of the charging time. Additionally, our DE algorithm can lower the ratios of overflow energy of the greedy algorithm by 12.9%, 16.4%, and 20.4% for 90, 60, and 30 degrees. It can thus decrease the number of fully charged devices by reducing overflow energy while maintaining a low charging time. A narrow transmission degree can significantly reduce the amount of energy wasted compared to that of other methods. Both RAN and RR also suffer from more overflow energy due to their inefficient charging schedules.

5.3.3. Different Offset Values

In the following experiment, we show the charging time and overflow energy for different schemes by using different offset angles. Figure 14 shows the charging time for three different offset angles, 10, 5 and 3, where the number of devices is 30 and the transmission angle is 90. The charging time of our greedy algorithm is 53.7, 51.6, and 51.4 s for 10, 5, and 3 degrees, while the charging time of DE is 54.1, 52.2, and 51.5 s. Because a smaller offset degree also indicates more transmission directions, the greedy algorithm can thus achieve a shorter charging time. Our DE algorithm also provides a performance comparable to that of the greedy algorithm. However, the charging efficiency of Fix, RAN and RR cannot be improved with a smaller offset. The RAN and RR methods have more sectors to choose from with a smaller offset and result in a longer charging time.

The overflow energy of different algorithms for different offsets is shown in Figure 15. The wasted energy of DE is better than Greedy by 12.9%, 7.4% and 1.6% for 10, 5 and 3 offset degrees, where DE achieves better improvements for larger offset. This is because the greedy algorithm can also benefit from a small offset to reduce overflow energy. The greedy algorithm outperforms the Fix method by 6.1–15%. Both RAN and RR still have the most overflow energy.

5.3.4. Different Topologies

In the following experiments, we use four different topologies with 30 nodes to evaluate the performance. The topologies are shown in Figure 16, where each topology is a region of 5 m × 5 m. These topologies are described below.

• Uniform (UN): The nodes are evenly distributed in the region.
• Power Law (PL): There are more nodes in the center area.
• BA: There are fewer nodes in the center area.
• ER: Nodes are uniformly distributed at the region while any two nodes are not close to each other.

Figure 17 and Figure 18 show the charging time and overflow energy of different algorithms for different topologies for the 30 devices, where the transmission angle is 90 and the offset is 10. The charging time of the DE algorithm is about 1% higher than that of the greedy algorithm for all topologies. Because the nodes in the topologies of BA and PL are close to each other, the greedy algorithm can thus achieve better performance. The Fix method has a better performance for these uneven topologies. All algorithms consume a longer charging time for both UN and ER topologies because the nodes in these topologies are uniformly distributed.

For the overflow energy, the DE algorithm still has the best performance among all schemes for all topologies. The improvement is relatively small for ER and UN topologies because of the even distribution of nodes. The Fix method suffers from more overflow energy for the PL topology because most nodes are located in the center area. When the nearby nodes are fully charged quickly, the distant nodes are still charged, resulting in high overflow energy. In contrast, the overflow energy of all algorithms decreases for the BA topology because there are only a few nodes in the center area.

5.3.5. Different Charging Ratios

Next, we discuss the performance for different charging ratios, where the charging ratio is the ratio of the charged battery power. Figure 19 and Figure 20 show the charging time and overflow energy of different algorithms for 30 devices with different charging ratios, where the transmission angle is 90 and the offset is 10. The charging time of the DE is about 1% longer than that of the greedy algorithm for all charging ratios. For all algorithms, when the charging ratio decreases, the charging time also decreases as well.

Figure 20 shows that, for all algorithms, the overflow energy significantly decreases as the charging ratio decreases, since the charging time is shortened. The greedy algorithm outperform the Fix method by 7% and the DE algorithm further outperforms the greedy algorithm by 13%.

5.4. Time Distribution of Fully Charged Devices

The last experiment shows the time distribution for fully charged devices. Figure 21 shows the number of fully charged devices in different iterations for different charging ratios, where the number of devices is 30, the transmission angle is 90, and the offset is 10. The results for Fix, RAN, and RR are not included because these methods need a longer charging time. We can observe that the DE algorithm can efficiently distribute the charging completion time of devices to different iterations. In Figure 21b, the fully charged devices of the greedy algorithm only occupy 8 iterations, but those of the DE algorithm occupy 17 iterations. Both Figure 21a,c show similar trend. This is because the DE algorithm postpones the charging completion time of a device by decreasing the charging time for the devices of each sector and increasing the charging time for the devices of the subsequent sectors. The DE algorithm can thus evenly distribute the fully charged devices to different iterations.

We further show the average data rate of fully charged devices in each iteration, where each device periodically transmits data to the AP when it is fully charged. The configuration of data transmission is based on our previous work [31]. It includes 10 MHz bandwidth and 100 mW transmission power. The background noise is −100 dbm and the channel gain is defined as $d_i^{-\alpha }$, where $d_i$ is the distance between device i and the AP. The path loss factor, $\alpha$, is set to four. However, there is only one wireless channel considered in this work since these sensor devices can only transmit data when they are fully charged.

As shown in Figure 22, the results show that the DE algorithm can provide a better transmission performance because it can transmit data in more iterations. Furthermore, in most iterations, the DE algorithm achieves a higher data rate because there are fewer fully charged devices in an iteration, as shown in Figure 21. For the iterations with more fully charged devices, the date rate of a device would be degraded because of the interference from more devices. As a result, the DE algorithm can improve the data rate of a fully charged device.

Figure 23 further shows the total data rate of fully charged devices in each iteration. The results reveal that the DE algorithm outperforms the proposed greedy algorithm by providing a higher total data rate of fully charged devices in most iterations. In particular, for the charging ratio 1, the DE algorithm can improve the average data rate by 160%. For the charging ratios, 0.6 and 0.8, the average data rate is further improved by 800%. In summary, although the DE algorithm requires a slightly longer charging time than the proposed greedy algorithm, it can effectively improve the performance of data transmission.

6. Conclusions

In this work, we combine beamforming and directional transmission technology to decrease the charging time and overflow energy. We propose two algorithms for RF energy harvesting. The proposed greedy algorithm is designed to minimize the charging time. The proposed differential evolution algorithm further reduces the overflow energy to distribute the completion time of fully charged devices. It also has the advantages of fast convergence and the ability to search for global optimal solutions. We verify the performance of the proposed algorithms with respect to different scenarios, including transmission and offset angles, different topologies, and charging ratios. The simulation results show that the proposed greedy algorithm can reduce the charging time by up to 55% compared to the baseline algorithms. Although the proposed DE algorithm requires about 10% longer charging time than the greedy algorithm, it also reduces the overflow energy by 10%. Moreover, by reducing the number of fully charged devices at the same time, the proposed DE algorithm can drastically improve the data rate of devices by 160% or more. In summary, the proposed greedy algorithm is suitable for applications without the demand of the massive data transmission. For applications which require a high data rate, the DE algorithm can lower the energy overflow to significantly improve the performance of data transmission.

In our future work, we will consider the computation offloading problem for the energy-harvesting devices. The lifetime of the devices will be jointly considered with their computation tasks. More practical limitations of energy-harvesting devices will also be considered, e.g., variable energy conversion efficiency and channel gain.