# Efficient Wireless Charger Deployment for Wireless Reshapeable Sensor Networks
## 4 Proposed Algorithms
\right|\) stands for the number of unmarked sensor nodes in \(NS\) covered by \(\textit{Cone}\left(\overset{\rightharpoonup}{u_{x}}\right)\). Moreover, \(\psi\left(\overset{\rightharpoonup}{u_{x}},\overset{\rightharpoonup}{u_{y}}\right)\) stands for the angle between the two vectors \(\overset{\rightharpoonup}{u_{x}}\) and \(\overset{\rightharpoonup}{u_{y}}\). In the GCC algorithm, for every grid point \(g\), a lower half sphere \(HS\) is obtained with \(g\) as the center and \(D\) as the radius. 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. However, 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 \(\overset{\rightharpoonup}{u_{1}},\ \overset{\rightharpoonup}{u_{2}},\ldots, \overset{\rightharpoonup}{u_{k}}\) going from \(g\) to \(s_{a_{1}},\ s_{a_{2}},\ldots,s_{a_{k}}\). Afterwards, the GCC algorithm compares the opening angle \(A\) with the angle \(B\) (i.e.,  
Figure 5: The greedy cone covering (GCC) algorithm. \(\psi\left(\overset{\rightharpoonup}{u_{x}},\overset{\rightharpoonup}{u_{y}}\right)\)) between any two vectors \(\overset{\rightharpoonup}{u_{x}}\) and \(\overset{\rightharpoonup}{u_{y}}\) associated with the two distinct sensor nodes \(s_{a_{x}}\) and \(s_{a_{y}}\). There are three cases for the comparison: \(B=A\), \(B>A\), and \(B<A\). The GCC algorithm performs the aforementioned angle comparison by projecting every vector and every cone onto the surface of a unit sphere centered at grid point \(g\). As shown in Figure 6, the projection of a vector is a point, while the projection of a cone is a circle of diameter \(d\). Referring to Figure 7a-c, for any pair of distinct sensor nodes \(s_{a_{x}}\) and \(s_{a_{y}}\), where, \(1\leq x,\ y\leq k\), let \(o_{x}\) and \(o_{y}\) be the projection points of \(\overset{\rightharpoonup}{g_{a_{x}}}\) and \(\overset{\rightharpoonup}{g_{a_{y}}}\) on the unit sphere \(O\) centered at grid point \(g\), and let \(d_{xy}\) be the Euclidean distance between the two points. There are three cases of the relationship between \(d_{xy}\) and \(d\), which correspond to the three relationship cases of \(A\) and \(B\). The three cases are elaborated below. Case (a) \(d_{xy}=d\). This case corresponds to the case of \(B=A\). For such a case, one candidate cone is generated. Note that \(o_{x}\) and \(o_{y}\) should be on the diameter of the projection circle of the cone. Case (b) \(d_{xy}>d\). This case corresponds to the case of \(B>A\). For such a case, two candidate cones taking \(\overset{\rightharpoonup}{g_{x}}\) and \(\overset{\rightharpoonup}{g_{y}}\) as directions are generated. Case (c) \(d_{xy}<d\). This case corresponds to the case of \(B<A\). For such a case, four candidate cones are generated. For two of the cones, \(o_{x}\) and \(o_{y}\) should be on the arcs of the projection circles (at the top and at the bottom) of the cones. For another cone, \(o_{x}\) should be on the projection circle (on the right), and the line \(\overline{o_{x}o_{y}}\) should go through the center of the circle. For yet another cone, \(o_{y}\) should be on the projection circle (on the left), and the line \(\overline{o_{x}o_{y}}\) should go through the center of the circle. Note that for Case (c), the GCC algorithm generates four candidate cones to cover sensor nodes \(s_{a_{x}}\) and \(s_{a_{y}}\). In practice, it greedily adjusts the cones to the extreme limitation with the purpose that the cones may at the same time cover as many as possible other sensor nodes. After generating candidate cones, the GCC algorithm greedily selects the qualified cone covering the most unmarked sensor nodes to deploy a charger. Note that if a sensor node's energy demand is met by the chargers already deployed, it is marked; otherwise, it is unmarked. In this way, chargers are deployed iteration by iteration until all sensor nodes are marked.