# Efficient Wireless Charger Deployment for Wireless Reshapeable Sensor Networks
## 4 Proposed Algorithms  
Two algorithms, namely the GCC algorithm and the ACC algorithm, are proposed to solve the WCDO problem efficiently. The algorithms have different time complexity and achieve different approximate solutions to the WCDO problem. The details of the two algorithms are described below. For a WSRN with \(n\) sensor nodes and with chargers being deployed on some of \(m\) grid points, the set of sensor nodes is denoted by \(NS=\{s_{1},\ s_{2},\ \ldots,\ s_{n}\}\) and the set of grid points is denoted by \(GS=\{g_{1},\ g_{2},\ \ldots,\ g_{m}\}\), where \(m=\big{(}\left\lfloor\frac{t}{S}\right\rfloor+1\big{)}\times\big{(}\left\lfloor \frac{W}{S}\right\rfloor+1\big{)}\), \(S\) is the separation of grid points, and \(L\), \(W\) and \(H\) are the length, width, and height of the sensor node deployment cuboid, respectively. Note that we assume each sensor node \(s_{i}\) in \(NS=\{s_{1},\ s_{2},\ \ldots,\ s_{n}\}\) has energy requirement \(e_{i}\) in \(ES=\{e_{1},\ e_{2},\ \ldots,\ e_{n}\}\). There are two forms of energy requirements: coverage requirement and power requirement. For the coverage requirement, \(e_{i}\) is a positive integer 1, 2, \(\ldots\), indicating sensor node \(s_{i}\) needs the coverage of \(e_{i}\) chargers to fulfill its energy demand. For the power requirement, \(e_{i}\) is of the unit mW, indicating \(s_{i}\) needs to capture \(e_{i}\) mW of power to make itself sustainable. The coverage requirement is actually about extreme cases. Specifically, a node's coverage requirement can be derived by calculating the ratio of the node's power requirement over the power harvested by the extreme point \(E\), as indicated in Figure 3.  
Both algorithms have two phases. The first one is the cone generation phase to generate candidate cones to be selected; the second one is the cone selection phase to select some candidate cones for deploying chargers. In the first phase, the algorithms generate cones by taking every grid point as the apex of cones. As shown in Figure 4, for every grid point, the algorithms first generate a half sphere (\(HS\)) centered at the point and calculate the sensor set (\(SS\)) of sensor nodes covered by \(HS\) (i.e., within \(HS\)). Afterwards, the first algorithm generates candidate cones on a node-pair-by-node-pair basis (i.e., for every pair of nodes in \(SS\)), while the second algorithm, on a node-by-node basis (i.e., for every node in \(SS\)). For generating better candidate cones, the algorithms greedily adjust cones so that every single cone can cover as many as sensor nodes or can charge sensor nodes more efficiently. Figure 4: The illustration of the lower half sphere \(HS\) centered at \(g\) with radius \(D\). In the second phase, both algorithms first unmark all sensor nodes. Note that a sensor node is unmarked if its energy requirement is not satisfied; otherwise, it will be marked. The algorithms then run iteration by iteration, and greedily select the qualified cone covering most unmarked sensor nodes, where a cone is said to be qualified if it takes a grid point \(g\) as its apex and \(g\) is totally taken by no more than \(Q\) selected cones as their apex. A selected cone corresponds to a deployed charger. For every newly selected cone, the algorithms marks every sensor node whose energy requirement is satisfied by the cone. And the algorithms continue until all sensor nodes are marked. In this way, the WCDO problem can be solved near-optimally. The pseudo code of the GCC algorithm is shown in Figure 5. In the code, \(\overset{\rightharpoonup}{u_{x}}\) stands for a vector going from grid point \(g\) to sensor node \(s_{a_{x}}\), and \(\textit{Core}(\overset{\rightharpoonup}{u_{x}})\) stands for a cone which takes \(g\) as the apex, takes \(\overset{\rightharpoonup}{u_{x}}\) as the symmetrical axis (or the _direction_), and has an effective charging distance \(D\) and an effective charging angle \(A\). Also note that \(\left| \begin{array}{c}\textit{Cone}\left(\overset{\rightharpoonup}{u_{x}} \right)\end{array}