# An Equilibrium Strategy-Based Routing Optimization Algorithm for Wireless Sensor Networks
## 3 ESRA Routing Algorithm
### Path Optimization Based on Edge-Cutting Strategy  
If the data are transmitted along the minimum routing graph, the average energy consumption and hops of the whole network can be effectively reduced. However, due to ignoring the loads of nodes, this routing strategy will easily lead to load unbalance and large differences of residual energy between nodes, thus reducing the network lifetime. Therefore, as it is shown in Algorithm 2, this section proposes an edge-cutting strategy to \"trim\" the minimum routing graph. In this edge-cutting strategy, in order to avoid a large amount of data influx into some nodes at the same period, all nodes in the minimum routing graph dynamically select the candidate parent nodes with the smallest load as the next hop, which can promote the balance of energy and traffic of each node. Furthermore, it can improve energy efficiency and prolong network lifetime simultaneously. As it can be seen from Section 3.2, a node may have multiple shortest paths. In order to make each node evenly undertake data forwarding tasks and avoid node congestion, the candidate parent node with smaller node load should be selected as the next hop as much as possible, and dynamically adjust it as the load changes. First, for the convenience of the following description, each node in the minimum routing graph needs to be layered, that is, all nodes in the minimum routing graph that are one hop from the sink node are defined as the first level \(l_{1}\), and the nodes in the two-hop distance from the sink node are defined as the second level \(l_{2}\), and so on. In this way, similar operation is completed until finding the layer that contains the most peripheral nodes. Besides, it should be specified that one node only belongs to one layer. Finally, a hierarchical set \(L\) containing all nodes is obtained, namely:  
\[L=\{l_{1},l_{2},...,l_{max}\} \tag{7}\]  
In the process of implementing the edge-cutting strategy, we start from the first layer \(l_{1}\), and the load sizes of all nodes in the same layer are sorted. Here, it is divided into the following two cases:  
* _Case 1_ When there is only one node \"_a_\" with the least load in this layer, if the child nodes of node \"_a_\" have multiple candidate parent nodes, the link between the child nodes of node \"_a_\" and other candidate parent nodes are cut off. If the child nodes of node \"_a_\" only have one candidate parent node, the edge-cutting operation is not performed. Then, node \"_a_\" is removed from this layer and all nodes' loads are updated. * _Case 2_ When there are multiple nodes with the least load simultaneously, the smaller the load product of all the nodes on the shortest path which is from this node to the sink, the larger the residual energy of this node, thus the smaller the amount of data transfer undertaken by this path. That is, the advantage of this node as next hop is greater. Here the \"node product\", expressed as: \[LCN(i)=\frac{\prod_{\zeta\in path^{is}_{tf}-sink}LN(\zeta)}{E_{i}}\] (8) where \(path^{is}_{tf}\) is the final shortest path left by the node i after the previous edge-cutting operation, and \(\zeta\) represents all nodes on this final shortest path except the sink node. Based on Equation (8), the node with smallest node product is set to \"_a_\", if the child nodes of node \"_a_\" have multiple candidate parent nodes, then the link between the child nodes and their other candidate parent nodes are cut off. If there is only one candidate parent node of node \"_a_\", no edge trimming is performed. Then, node \"_a_\" is removed from the layer and all nodes loads are updated. The same operation is used to traverse other nodes in the same layer until all nodes in this layer complete the edge-cutting. Meanwhile, this strategy will be performed on other layers until all layers complete the edge-cutting. Here, in order to explain the working process of edge-cutting strategy more clearly, this paper takes a simple network topology in Figure 2 as an example.