# Efficient Wireless Charger Deployment for Wireless Reshapeable Sensor Networks
## 4 Proposed Algorithms
Also note that we use function \(EP\left(c,\ s_{i}\right)\) to estimate the energy provision between the charger \(c\) and the sensor node \(s_{i}\). Figure 6: The projection of a cone (respectively, vector) onto a unit sphere surface is a circle (respectively, point). Figure 7: Three cases for the GCC algorithm to generate candidate cones. Corresponding to the coverage requirement, \(EP\left(w,\ s_{i}\right)\) returns 0 or 1, indicating the cone or the charger \(c\) can or cannot cover the sensor node \(s_{i}\). Corresponding to the power requirement, \(EP\left(c,\ s_{i}\right)\) returns the power (in the unit of mW) received by \(s_{i}\) from the energy emitted by charger \(c\). As will be shown in Section 5, the received power can be calculated by interpolating power regression expressions derived from practical experimental data. The pseudo code of the ACC algorithm is shown in Figure 8. Like the GCC algorithm, the ACC algorithm first derives, for every grid point \(g\), a lower half sphere \(HS\) centered at \(g\) with the radius \(D\). If \(HS\) covers only one sensor node \(s_{a_{1}}\), then the algorithm generates one candidate cone taking the vector going from \(g\) to \(s_{a_{1}}\) as the direction. If \(HS\) covers \(k,k>1\), sensor nodes \(s_{a_{1}},\ s_{a_{2}},\ldots,s_{a_{k}}\), then the algorithm generates \(k\) unit vectors \(\overrightarrow{u_{1}},\ \overrightarrow{u_{2}},\ldots,\overrightarrow{u_{k}}\) going from \(g\) to \(s_{a_{1}},\ s_{a_{2}},\ldots,s_{a_{k}}\). The ACC algorithm constructs candidate cones on a node by node basis. In practice, the ACC algorithm initially constructs a candidate cone \(\mathit{Cone}(\overrightarrow{u_{x}})\) to cover sensor node \(s_{a_{x}}\) for \(1\leq x\leq k\). Besides covering node \(s_{a_{x}}\), the ACC algorithm adaptively and greedily adjusts \(\overrightarrow{u_{x}}\) so that \(\mathit{Cone}(\overrightarrow{u_{x}})\) can cover as many as possible other sensor nodes. This is achieved by adjusting the direction of \(\overrightarrow{u_{x}}\) by composing \(\overrightarrow{u_{x}}\) and \(\overrightarrow{u_{y}}\) for every vector \(\overrightarrow{u_{y}}\), where \(1\leq y\leq k\) and \(x\
eq y\) (Figure 9). The direction adjustment (Lines 12-14) proceeds on a node-by-node basis. Certainly, the direction adjustment should guarantee that the number of sensor nodes covered by \(\mathit{Cone}(\overrightarrow{u_{x}})\) is increasing and that the sensor node \(s_{a_{x}}\) is still covered by \(\mathit{Cone}(\overrightarrow{u_{x}})\) whatever the adjusted \(\overrightarrow{u_{x}}\) is. Figure 8: The adaptive cone covering (ACC) algorithm. In the GCC and the ACC algorithms, \(US\) stands for the set of unmarked sensor nodes with unsatisfied energy requirement. For most cases, the two algorithm stop and return \(CS\)* and \(US\), with \(US\) is empty. For such cases, the cones in \(CS\)* can be used to deploy chargers to satisfy the energy requirements of all sensor nodes. On the contrary, when the algorithms terminate and return a non-empty set of \(US\), they should re-run by setting \(NS=US\), and the re-running should proceed until \(US\) is empty. The re-running is to satisfy the pending energy requirements of unmarked nodes. When \(US\) is empty, the requirements of all sensor nodes are satisfied and all the cones ever reported in \(CS\)* by running and re-running the algorithms are the final selected cones for deploying chargers. However, the re-running algorithms will report an error if it finds that no available grid point exists, where an available grid point is a grid point that no more than \(Q\) selected cones take as their apex. For such an error condition, we may need to decrease \(S\), the separation of grid points, to increase the total number of grid points for more possible locations for deploying chargers to satisfy sensor nodes' energy requirements.