# Joint Energy Supply and Routing Path Selection for
## 3 A Joint Algorithm of Energy Supply and Routing Selection
### Property Analysis and Implementation Guidlines  
In this section, we will provide the relevant performance observations and analysis of our joint algorithm, and offer a simple implementation. **Observation 1**. : _In the case of insufficient energy supply capacity of WCD, the fusion index \(\partial\) can optimize the distribution of recharge energy and extend the network lifetime, and the smaller the value, the higher the energy utilization efficiency._  
According to Definition 6, the energy replenishment capability can be expressed as the product of the charging speed and the charging duration. In the case of one-to-one charging, this paper assumes that the charging speed remains unchanged, so the charging duration is equivalent to the size of the energy supply capacity. Thus, the charging duration is less than the sum of the maximum chargeable times of all nodes when the energy supply capacity is insufficient, so all nodes cannot be fully charged after the first phase of energy supply in Section 3.1, that is, there exists \(\forall t^{\prime}_{i}<t_{i}\) for all \(i\). It should be noted that the network lifetime is determined by the survival time of the first dead node, while the node that dies first usually belongs to those nodes with large energy consumption and large maximum charging time. Without the second phase of the energy supply strategy, the energy added to those nodes with low-load energy consumption is actually wasted after the death of the network, which seriously affects the utilization efficiency of limited energy. In the second phase, we define an update strategy which transfers the energy, which is originally distributed to those nodes with enough remaining energy, to others that needs energy urgently, so as to delay the death time of as much as possible, especially, when the fusion index is set to 1, that is, it must be ensured that the node can survive until the next round of charging schedule, the effect of prolonging the network lifetime should be the best. **Observation 2**. : _It is obvious that different harmonic coefficients can achieve different network performances._  
The composite cost metric \(u_{ij}\) for routing is defined in the proposed algorithm, and we also adopt the harmonic coefficients \(\alpha\) to control the impact on the selection of next-hop node made by the transmission energy consumption \(C_{i,j}\) and the forward distance energy consumption \(C_{j,s}\). Among them, \(C_{i,j}\) will certainly affect the final average energy consumption of network, and \(C_{j,s}\) actually reflects the distance from the next hop node to the sink in some extent, which can affect the average number of hops. Thus, as it has been discussed in Section 3.1, we limit the sum of the harmonic coefficient \(\alpha\), \(\beta\) to 1, and the relative size of the harmonic coefficient reflects the bias towards energy consumption and hops during routing selection. Thereout, depending on different demands of the network hops and energy consumption in the real applications, the harmonic coefficient can be modestly changed. This is also confirmed and analyzed in the simulation part of Section 4. **Observation 3**. : _In a worst case, the time complexity of our algorithm is \(O(n^{2})\)._  
The original charging time of each node is calculated in the first stage of the energy supply strategy, and the required time complexity is \(O(n)\). The first step in the second stage is to sort all the nodes by the merge sort according to their remaining lifetime, and the required time complexity is \(O(n\log n)\). The second step is to update the charging time of each node, and the worst case is that all nodes need to be updated, so the required time complexity is \(O(n)\). Therefore, the worst time complexity of the energy supply strategy is \(O(n)\). The routing algorithm chooses one node from the forward neighbor nodes set as the next hop for each node. In the worst case, the number of forward neighbors of the node is \(n-1\), so the worst time complexity is \(O(n^{2})\).