# Joint Deployment of Sensors and Chargers in Wireless
## 4 Solutions
### Approximate Algorithms for Deploying Sensors  
Based on the result of area discretization, the GHDSAE solution in Algorithm 1 is proposed to deploy sensors. In Algorithm 1, two principles are adopted to iteratively select the optimal deployment location: (1) always choose a location that can cover the maximum number of PoIs that have not yet been covered; (2) based on the principle one, always choose a location closer to the deployed sensors.  
Specifically, Line 1 initializes some key parameters, where \(Q\) is an intermediate parameter indicating the number of PoIs that have been covered by deployed sensors. In Line 2, the candidate location set \(S^{\prime}\) is calculated by the discretization method in Section 4.2. Lines 3-9 of Algorithm 1 are the iterative deployment phase. In Lines 4-6, for each candi  
Figure 3: An illustration of grid discretization for sensor deployment.  
date location in \(S^{\prime}\), the number of uncovered PoIs that the location can cover within \(\tau_{max}\) time slots is calculated. In Line 7 the location with the highest number of covered PoIs is chosen as the optimal location to deploy a new sensor. If there exist multiple best locations, the distance between these locations and the deployed sensors are further compared, and the location with the smallest distance is chosen. In Line 8, all related variables are updated. Finally, in Line 10, the deployment of sensor \(S\) and the scheduling scheme for all sensors \(S_{T}\) are outputted.  
```
Input: A set \(\alpha_{i}\) of \(O,\) the maximum working time slot \(\tau_{max}\), Output: The deployment of sensors \(S,\) the scheduling scheme of all sensors \(S_{T}\)
1:\(Q=0,\)\(N\), \(S_{T}\leftarrow\)\(\mathcal{Q},\)\(S\leftarrow\mathcal{O}\);
2: Calculate the \(S^{\prime}\);
3:While\(Q\leq N\)do
4:For each \(s^{\prime}_{i}\in S^{\prime}\)do
5: Calculate the maximum number of uncovered PoIs for the previous \(\tau_{max}\) slots;
6:Endfor
7: Find the candidate location of sensor \(s^{\prime}_{i}\) with the largest number of effectively covering Pols and the smallest distance to already deployed sensors;
8: Update \(Q,\)\(S_{T},\)\(S\gets S\bigcup\left\{s^{\prime}_{i}\ \right\},\)\(S^{\prime}\gets S^{\prime}-\left\{s^{\prime}_{i}\right\};\)
9:Endwhile
10:Return\(S,\)\(S_{T}\)
```  
**Algorithm 1**Details of the GHDSAE for sensor deployment  
In Algorithm 1, the number of PoIs is \(N\). Firstly, the time complexity of the candidate location of sensors is \(O\left(NL_{s}^{2}\right)\). Then the time complexity of calculating the coverage effect of candidate locations is \(O\left(NL_{s}^{2}(JN+\tau_{max})\right)\), and the complexity of selecting the best candidate location is \(O\left(N^{2}L_{s}^{4}+NL_{s}^{2}\right)\). Finally, the time complexity of deploying sensors and updating \(S_{T}\) is \(O(NJ)\). The final time complexity is:  
\[O\left(NL_{s}^{2}\right)+O\left(NL_{s}^{2}(JN+\tau_{max})\right)+O\left(N^{2} L_{s}^{4}+NL_{s}^{2}\right)+O(NJ)=O\left(N^{2}\right) \tag{13}\]  
The approximation rate of Algorithm 1 is similar to that in [38], which is ignored here.  
To analyze the impact of the sensor aggregation effect on the charger deployment, we further eliminate the sensor aggregation effect in Line 7 of Algorithm 1, and this modified approach is referred to as the greedy heuristic solution for deploying sensors (GHDS).