# Joint Power Charging and Routing in Wireless
## 3 Optimization Algorithms
### Heuristic Algorithm for Optimal Charging  
In this subsection, We assume the routing tree can be predetermined by some existing approaches, such as the Dijkstra routing algorithm or the minimum spanning tree (MST) routing algorithm. The optimization model can be transformed as the following:  
\[ \begin{array}{l}\max\frac{\tau_{\text{Int}}}{\tau}\\ s.t.(8)\sim(12)\end{array}  \tag{14}\]  
From the description of Equation (14), we know that the optimal charging efficiency is related to the resident locations \(\mathcal{M}\) and the total moving distance \(\sum_{m=1}^{\text{M}-1}\frac{d_{m,m+1}}{\overline{\
u}}+\frac{d_{\mathcal{M}1} }{\overline{\
u}}\). This total moving distance should be the shortest Hamiltonian cycle among all the resident locations. Otherwise, more time is spent on traveling. In addition, according to Equation (11), as a result of the lower left power, more time is needed to charge the sensors. Thus, the optimal charging efficiency is only related to the resident locations. According to Equations (8)-(12), these resident locations should cover all the sensors within its charging radius. Additionally, the Hamiltonian cycle among these locations should be the smallest. To satisfy these requirements, we therefore propose a heuristic algorithm shown in Algorithm 1 to find the optimal resident locations with the predefined routing tree. In our algorithm, we first introduce the following two definitions:  
**Definition 1**. : _If a node has no neighbor nodes within a circle of radius \(2R_{\
u}\), this node is defined as an isolated node._  
**Definition 2**. : _If a node has neighbor nodes within a circle of radius \(2R_{\
u}\), this node is defined as a non-isolated node._  
We design the following two strategies to select the resident location for nodes of a different type. The first strategy is for isolated nodes. We first line an isolated node with the previous selected residentlocation; then, the location along this line and with a distance of \(R_{v}\) to that isolated node is selected as the current resident location. The second strategy is for non-isolated nodes. We first select a node with the maximum distance to this non-isolated node within a distance \(2R_{v}\). After that, the midpoint between these two nodes is selected as the resident location. ```
Initialization: Obtain the location of service station \(\{x_{0},y_{0}\}\), the set of uncharged sensors \(\mathcal{N}\), and the working period \(\tau\). Set the previous resident location \(Rl_{p}=\{x_{0},y_{0}\}\), and set the resident location set \(\mathcal{M}=\{Rl_{p}\}\). Set the counter for the resident location as \(m=1\). while\(\mathcal{N}\
eq\varnothing\)do  Find a sensor \(i^{*}\in\mathcal{N}\) satisfying \(d_{i^{*},p}<d_{k,p}\), \(\forall k\in\mathcal{N}\). Determine the type of sensor \(i^{*}\). if\(i^{*}\) is a isolated nodethen  Select resident location \(Rl_{m}\) according to the first strategy. else  Select resident location \(Rl_{m}\) according to the second strategy. end if \(\mathcal{M}=\mathcal{M}\cup Rl_{m}\). \(Rl_{p}=Rl_{m}\). \(\mathcal{S}_{m}=\{n|n\in\mathcal{N}\)&&\(d_{n,m}\leq R_{v}\}\). Calculate charging time \(\tau_{m}\) for \(\mathcal{S}_{m}\) as \(\tau_{m}=\max_{i\in\mathcal{S}_{m}}\frac{\tau P_{i}}{P_{m}}\). \(\mathcal{N}=\mathcal{N}-\mathcal{S}_{m}\). \(m=m+1\). end  Calculate the shortest Hamiltonian cycle among \(\mathcal{M}\). Calculate the objective value \(\frac{\tau_{m}}{\tau}\) with \(\{\tau_{m}\}\) according to Equations (4)-(7) and  Equations (9)-(12). ```  
**Algorithm 1**Heuristic algorithm for resident location selection  
As an example, Figure 2 shows how to select the resident location for different types of nodes. First, as shown in Figure 1(a), node \(n_{1}\) is selected as the first node near the service station, by judging its type as non-isolated. Node \(n_{2}\) is selected, for the reason that \(n_{2}\) has the maximum distance to \(n_{1}\) within a distance \(2R_{v}\).