# Extending Wireless Reschargeable Sensor Network Life without Full Knowledge
## 9 Full Knowledge Optimal Algorithm  
In this section, we describe the optimal full knowledge algorithm used as a baseline for comparing the performance of our algorithms. This algorithm requires full knowledge of all the power levels of all the sensor nodes in the WRSN. Given the full knowledge of the power levels of the WRSN, it is possible to identify the set of lowest power nodes in the network. Charging a node involves three main factors: the cost to localize (concentrically align the MCR with it), the cost to reach it, and finally the cost to bring its power level to the target level. When the charging list is determined, the total cost can be computed, and, then, comparing the available power to the total cost identifies the feasibility of charging. Using the Charging Algorithm 2, the target node is the next node after the set of charged nodes, \(v\), and the \((k-1)\) nodes that may be dropped. Identifying the target node enables us to identify the network's new minimum power level, thereby allowing us to estimate the life extension of the WRSN. We take a top-down approach in our realization of an optimal solution, presented in Algorithm 6. Assume the highest possible life increase, while highly improbable, and gradually reduce the life increase until we hit the highest possible one. We start by considering localization cost; knowing the localization power cost, we can identify the highest possible number of nodes to charge, \(u\), ignoring all other factors (line 3). Since it is only after \(k\) nodes deplete their power that the network dies, we can skip charging \(k-1\) nodes. This makes the target node the \(N_{u+k}\) node (lines 4-5). This is highly unlikely to be a target, since we are assuming the use of all available power only for localization. Given this target, we compute the needed charging and moving power (line 6). If the existing power is enough to satisfy all power needed for moving, charging, and localization then we are done finding a target (line 7). Otherwise, revert to the next highest power node as a target. This removes a node from the charging list, the second highest node, reducing total localization cost and charging cost. Repeat the power feasibility test until a solution can be found (lines 7-12). The algorithm execution complexity is \(O(n^{2}log\ n)\). ```
1:\(E_{C}\)\(\triangleright\) Maximum MCR power
2:\(\lambda\)\(\triangleright\) Localization cost in terms of power
3:\(k\)\(\triangleright\) Number of possible nodes to drop
4:\(N\)\(\triangleright\) List of network nodes
5:procedureFindOptimalTimeIncrease(\(N\))
6:\(sorted\gets E_{C}/sort(N)\)\(\triangleright\) Sort the nodes based on power
7:\(u\gets E_{C}/\lambda\)\(\triangleright\) Number of nodes in charge list
8:\(targetIdx\gets u+k\)\(\triangleright\) Index of target node
9:\(targetPower-sortedN_{targetIdx}\)\(\triangleright\) Highest possible target
10:\(C,M\gets ComputeNeedPowers(N,targetPower,u)\)\(\triangleright\) Power needed to charge and move
11:while\(E_{C}<C+M+(u\times\lambda)\)\(\triangleright\) Power of \(u\)
12:\(targetIdx\gets targetIdx-1\)\(\triangleright\) If not enough power exists then pick a lower target
13:\(targetPower\gets sortedN_{targetIdx}\)\(\triangleright\) Reduce number of charged nodes by one
14:\(u\gets u-1\)\(\triangleright\) Reduce number of charged nodes by one
15:\(C,M\gets ComputeNeededPowers(N,targetPower,u)\)
16:endwhile
17:\(timelIncrease\leftarrow(targetPower-sortedN_{k})/r\)\(\triangleright\) Time is how long the extra power can be consumed
18:return\(timelIncrease\)
19:endprocedure
```  
**Algorithm 6** Find Optimal Time Increase. To compute the time increase, we simply compare the amount of added power to the \(k^{th}\) lowest power node. The time increase will be the time it takes to consume the extra power added to the \(k\) lowest power sensor nodes. This time increase is the lowest possible time increase. A more accurate value will involve the probability of a sensor node discharge.