## 2 Routing Protocols in Large-Scale WSNs
### Energy Balance Algorithms
###### Meleach-L
There is not a definite method which can be used to address the problem of communication between the CH and the BS in LEACH or other protocols based on LEACH. Most of LEACH-alike protocols assume that a CH can communicate directly with the BS, but it is always not the case. Consequently a multi-hop transmission scheme is utilized in [44]. In order to alleviate the effect of self-induced black hole, an alternative sensor nodes (ASN) is also proposed in this work. The operation of this routing algorithm is separated into rounds. Each round includes a set-up phase for constructing clusters and a steady-state for transmitting data from sensor nodes to the BS via CHs. To be more specific, the algorithm is divided into five steps for completing the process of communication in every round:  
1. Counting hop number. At the beginning of communication, the BS broadcasts a message including hop-count parameter, and then the nodes which receive the message forward it to their neighbors until every node receives the message. When the broadcasted messages are received by a sensor node through different paths, the sensor node caches all the routes towards the BS into the routing table in the memory space. 2. Hierarchicalizing sensor nodes. In order to hierarchicalize sensor nodes into different layers to set the level of sensor nodes, the sensor nodes which communicate with the BS via the same hop-count are set into the same layer. 3. Clustering in the system. Each node uses a value within 0 and 1 to compare with a threshold \(\mathit{r(n)}\) which is a function related with the desired percentage of CH nodes during a round. The value has been selected at the start of the round. The node becomes a CH autonomously when its value is smaller than \(\mathit{r(n)}\), and then the node broadcasts an announcement message to its neighbors. Based on the received signal strength form the CH, other non-cluster nodes decide which cluster to join. Additionally, some specially located sensor nodes may not be able to find a cluster in their transmission range, and thus they elect themselves as CH nodes. 4. Transmission and scheduling in a cluster. A CH node schedules all the sensor nodes in its cluster with TDMA scheme to avoid collision. 5. Selecting transmission routes. There are numerous routes from each node to the BS, and the routes with the least hops will be selected for each node. But there may be many routes with the minimum hops. In this case the route with the highest value of the lowest node's energy parameter will be selected from these routes. Eventually, the search of the alternative sensor node and the data transmission is proceeding at the same time. If a relay node \(a\) finds a node \(b\) in its transmission range \(R\) and the distance between them is smaller than \(R\)/2 and the residual energy of node \(a\) is smaller than node \(b\), node \(b\) will become an ASN and take the role of the relay node \(a\). By using ASN to balance the loads of the sensor nodes which are close to the BS, the effect of self-induced black holes is greatly alleviated. This protocol is devised based on LEACH, so it also inherits the advantages of LEACH, for example the TDMA scheme can reduce the inter-cluster and intra-cluster collisions. However, a large overhead is generated due to the clustering of every round. The replacement of relay nodes by ASN accompanies the data transmission whenever possible, so the frequent switching of nodes also incurs numerous overhead. _MuMHR_. [PERSON] _et al._ in [45] proposed a robust and efficient routing protocol named Multi-path Multi-hop Hierarchical Routing (MuMHR). This protocol is superior to LEACH in terms of load balance and reliability. In order to prevent energy depletion resulting from the same path being constantly occupied for transmission or particular nodes being cluster-heads for a long duration, traffic multiplexing over multiple paths of network level and periodical rotation of the cluster-heads of cluster level were proposed.