# Wireless Energy Harvesting for Internet-of-Things Devices Using Directional Antennas
## 4 Energy Harvesting Using Directional Antenna
### 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.  
```
0: The set of the sector \(S\), The set of the battery energy level \(B_{n}\)
0:\(X\), \(T\), \(WE\)
1:\(T=0\), \(WE=0\), \(X=[]\)
2:for each \(s_{j}\in S\)do
3:if\(s_{j}\) is not the last sector then
4:\(set=s_{j}\)
5:\(set^{\prime}=s_{j+1}\)
6:if\(set-set^{\prime}\
eq\emptyset\)then
7:\(wfn=set-set^{\prime}\)
8: compute \(t\) by Equ(1)
9:\(T+=t\)
10: Harvest(\(set\),\(t\))
11:\(X\).append(\(t\))
12:endif
13:else
14:if\(s_{j}==\emptyset\)then
15:\(t=0\)
16:else
17:\(wfn=set\)
18: compute \(t\) by Equ(1)
19:\(T+=t\)
20: Harvest(\(set\),\(t\))
21:\(X\).append(\(t\))
22:endif
23:endif
24:endfor
25:\(WE\) = WasteEnergy(\(X\))
26:return\(X\), \(T\), \(WE\)
```  
**Algorithm 1** Greedy  
Figure 4: An example of the proposed greedy algorithm.