# Joint Deployment of Sensors and Chargers in Wireless
## 4 Solutions
### Approximate Algorithm for Deploying Chargers  
Based on the results of sensor deployment, the GH solution in Algorithm 2 and the PSO solution in Algorithm 3 are proposed to deploy the chargers. In Algorithm 2, the principles for iteratively selecting the optimal deployment locations for new chargers are: (1) preferentially deploy chargers for a sensor that has not yet been fully charged and has the most neighbor sensors that have not yet been fully charged; (2) based on the principle one, always choose the locations that can charge the maximum number of sensors that have not yet been fully charged. Specifically, the number of neighbor sensors is defined as the number of other sensors in a circle centered at the sensor with a radius of \(2*d_{th}\). The process of Algorithm 2 is as follows: in Line 1, the minimum charging power \(P_{min}^{s_{j}}\) of each sensor \(s_{j}\) in \(S\) is calculated according to the sensor scheduling \(S_{T}\) and Equation (5). In Line 2, the candidate location set \(C^{\prime}\) is calculated by the discretization method in Section 4.2. In Line 3, the candidate locations \(C^{\prime}\) are sorted in descending order based on the number of their covered sensors. The sensors \(S\) are sorted in descending order based on the number of neighbor sensors. Lines 4-9 are the iterative deployment phase. The \(k\) is the maximum number of chargers to be deployed to charge one sensor, and the \(Loop_{-}1\) is a temporary intermediate variable. In Line 6, the charging power \(P_{h}^{s_{j}/C}\) of \(s_{j}\) based on the currently deployed charger \(C\) is calculated. If the \(s_{j}\) is still not fully charged (\(P_{h}^{s_{j},C}<P_{min}^{s_{j}}\)and \(Loop\_1<k\), Lines 6 and 7 are executed to deploy new chargers for \(s_{j}\). In Lines 7 and 8, the charging power from the candidate locations for \(s_{j}\) is calculated, and the candidate chargers with the maximum \(P_{h}^{s_{j},C\cup Loop\_1}\) are deployed. Finally, In Line 11, the deployed chargers \(C\) is outputted. ```
0: A set \(s_{j}\) of \(S\), the scheduling scheme of all sensors \(S_{T}\) Output: The deployment of chargers \(C\)
1: Calculate the \(P_{min}^{s_{j}}\) for each sensor \(s_{j}\) in \(S\);
2: Calculate the \(C^{\prime}\);
3: Sort the \(C^{\prime}\) and \(S\) in descending order;
4:For\(s_{j}\in S\)do
5:\(Loop\_1=0\);
6:While\(P_{h}^{s_{j},C}<P_{min}^{s_{j}}\) && \(Loop\_1\leq k\)do
7: Find the candidate locations with the largest \(P_{h}^{s_{j},C\cup Loop\_1}\);
8: Update \(C,C^{\prime}\);
9:End While
10:End For
11:Return \(C\)
```  
**Algorithm 2**Details of GH for charger deployment  
In Algorithm 2, assuming there are \(M\) sensors, firstly, the time complexity of calculating the charging power of the sensors and the candidate location of chargers is \(O(M)\) and \(O(ML_{c}^{2})\) respectively. The time complexity of arranging the candidate chargers in descending order is \(O\big{(}M^{2}L_{c}^{2}+M^{2}L_{c}^{4}\big{)}\). The time complexity of arranging the sensors in descending order according to the number of neighbors of the sensor is \(O\big{(}M^{2}L_{c}^{2}+M^{2}\big{)}\). The time complexity of deploying chargers is \(O\big{(}kM^{2}L_{c}^{2}\big{)}\). The final time complexity is:  
\[O\Big{(}ML_{c}^{2}\Big{)}+O(M)+O\Big{(}M^{2}L_{c}^{2}+M^{2}L_{c}^{4}\Big{)}+O \Big{(}M^{2}L_{c}^{2}+M^{2}\Big{)}+O\Big{(}kM^{2}L_{c}^{2}\Big{)}=O\Big{(}M^{ 2}\Big{)} \tag{14}\]  
Algorithm 3 uses the PSO solution to deploy the chargers. To avoid falling into a local optimal solution, three improvements are made: (1) The sensors are arranged in descending order according to their neighbor sensors. The number of neighbor sensors is defined as the number of other sensors in a circle centered at the sensor with a radius of \(2*d_{th}\); (2): A square search area is established for each sensor. The search area is centered at the sensor with the side length of \(2*d_{th}\); (3): Deploy up to \(k\) chargers per sensor to achieve full charging; otherwise, deployment will fail.