# Extending Wireless Reschargeable Sensor Network Life without Full Knowledge
## 7 Exploration and Charging Algorithm  
In this section, we discuss our algorithm, with three stopping methods. Our objective is to identify, without full knowledge of network power levels, the shortest distance the MCR should travel, \(\gamma\), and the set of nodes, \(v\), to charge that increases the life of a WRSN to, \(\psi\), near optimal increase. We start by describing our algorithm, and then show how the stopping decision can be made using three progressive methods: Naive approach, Minimum Only approach, and finally, our ANLPP approach. We then analyze the performance of the algorithm. Our Explore algorithm (Algorithm 1) successively explores the WRSN nodes sequentially, and performs three steps after visiting each new sensor node in the network:  
1. determine the subset of visited nodes to charge \(v\),
2. decide whether to move forward and visit more nodes or terminate exploration, define \(\gamma\),
3. when no more nodes are to be visited, return home and charge nodes in \(v\) on the way back. ```
1:\(\triangleright\) The traversing UAV
2:\(N\)\(\triangleright\) List of network nodes
3:\(v\)Nodes \(\leftarrow\) empty\(\triangleright\) List of visited nodes
4:\(v\)\(\leftarrow\) empty\(\triangleright\) List of nodes to charge
5:\(C\)\(\leftarrow\) zero\(\triangleright\) Charge power
6:for\(i\gets 1\)...sizeof\(N\)do
7:\(p\)\(\leftarrow\) Get \(MCR\) Power Level
8:\(h\)\(\leftarrow\) calculate power needed to return home
9:\(v\),\(C,l\)\(\leftarrow\)\(charge(vNodes,power-hp)\)\(\triangleright\) Get the charging list, power needed to charge, and new power level
10:\(p\)\(\leftarrow\)\(p\)\(\leftarrow\)\(p\)\(\triangleright\) Power left, after charging and returning home reserves
11:ifCANVSTMORNODES(\(pover,i\))then\(\triangleright\) Based on location and power level decide to continue or terminate
12: visit next node \(i\) and read node power
13: add node to\(vNodes\)
14:else
15: Break
16:endif
17:endfor
18:return to base and charge nodes in \(v\)
19:endprocedure
```  
**Algorithm 1** Find exploration termination point. The Explore algorithm (Algorithm 1) is an online algorithm, which starts when the MCR leaves \(B_{S}\) and terminates once the MCR returns to \(B_{S}\). It also lets the MCR know when it should go back to \(B_{S}\). The algorithm can cope with unpredicted power consumption by the MCR, since it monitors and updates the power availability as new sensor nodes are explored (line 6). The algorithm also reserves power facilitating the return to \(B_{S}\) at all times, \(hp\), and updates this value online (line 7). To identify \(v\)the algorithm invokes a charging algorithm (line 8). If the MCR has enough power left to visit another node, then the MCR is instructed to visit the next node and move forward. If the MCR does not have enough power to charge and return home, then the exploration is terminated, at \(\gamma\), and the MCR returns to \(B_{S}\) and charges the nodes in \(v\). Determining \(v\) is done by implementing a charging algorithm. Our Charge algorithm (Algorithm 2) is similar to the Greedy Plus algorithm from [12], but it differs in the knowledge requirements, discharge behaviour and localization cost. Greedy Plus was also demonstrated on a line topology. In Charge, knowledge builds up as the charging unit traverses the network. The Charge algorithm assumes a fast moving MCR, leading to a round trip from \(B_{S}\) back to \(B_{S}\) in less time than what is needed between two sensor node discharges. The Charge algorithm will sort the nodes based on their power level (line 2), and adds the low power nodes to the charging list sequentially (lines 13-15), until the MCR has no more power to bring the list of nodes proposed to be charged, \(v^{\prime}\), to the next power level (line 17). The time complexity of Algorithm 1 is \(O(n^{2}log\ n)\). The execution of lines 1-4 is constant time \(O(1)\). The _For_ loop in line 5 renders an \(O(n)\) execution time of everything inside the loop. Line 6, retrieving the MCU power level, is \(O(1)\).