## 2 Routing Protocols in Large-Scale WSNs
### Energy Balance Algorithms
###### Meleach-L  
Based on LEACH and More Energy-efficient LEACH (MELEACH [42]), [PERSON] _et al._ in [43] proposed an expanded routing protocol, called More Energy-efficient LEACH for large-scale WSNs (MELEACH-L). MELEACH-L makes the major functions of MELEACH applicable to large-scale WSNs. Through controlling the size of each cluster and separating the cluster heads from the backbone nodes, MELEACH-L solves the problems of the channel assignment among neighbor clusters and the cooperation among cluster heads during data collection. The procedure of MELEACH-L is divided into rounds. Each round consists of sequentially tetradic phases: the Cluster Head Selection, the Backbone Tree Construction, the Spanning Tree Construction and the Data Collection. And the time-line of the procedure is shown in Figure 7.  
In MELEACH-L, the transceiver of each sensor node is assumed to switch its channel among a set of 20 channels, which range from Channel 0 to Channel 19. Channel 0 is used as the common channel, on which every sensor node and the BS work in the beginning of every round. The detailed procedures may be listed as follows:  
(1) Cluster Head Selection. First of all, sensor nodes initialize the channel set \(C_{i}\)= {1, 2... 19}, and set up a timer \(T_{i}\). When \(T_{i}\) expires, node \(i\) becomes a CH and broadcasts an Advertisement Message (ADV\({}_{i}\)), including the node ID and its geographical coordinate and the serial number of the intra-cluster channel used in the cluster that node \(i\) dominates, with the maximum power of its radio. Eventually, if a node \(j\) hears ADV\({}_{i}\) and the distance between \(i\) and \(j\) is greater than \(R\)/2 (\(R\) is the maximum transmission radius of the radio), \(j\) will not join the cluster and delete the channel \(i\) from \(C_{j}\); or else, \(j\) clears \(T_{j}\) and becomes a non-CH node. 2. Backbone Tree Construction. Based on the Energy-aware Virtual Backbone Tree (EVBT) algorithm, some of non-CH nodes are selected to construct an EVBT. The sink node initiates an EVBT Construction Request (ECR) at the beginning of the procedure. The EVBT grows from the sink and spans the entire sensor network. The EVBT algorithm aims to build an energy efficient tree throughout the network. It has three characteristic objectives: the energy consumption for data delivery along the EVBT is minimized; the energy consumption for the EVBT construction is minimized; the tree nodes should have high energy levels. 3. Spanning Tree Construction. When the backbone tree is constructed, each CH selects the closest EVBT node as its upstream node according to the geographical coordinate information. Each client node, which is the node neither a CH nor an EVBT node, chooses the closest CH as its leader according to the information in the ADV messages. 4. Data Collection. Following the TDMA schedule, each cluster member carries out collection and transmission of messages in corresponding time slots. In the schedule, the time slot when a sensor node \(i\) transmits the aggregated data to its parent node is always after the slots when the children of \(i\) transmit aggregated data to \(i\). In MELEACH-L, the massively redundant nodes are utilized to deliver the data messages, and that can alleviate CHs' energy consumption. The adoption of EVBT further improves the balanced energy consumption, and also make the network lifetime become much longer. Moreover the interference  
Figure 7: Time-line of MELEACH-L.  
restraints between clusters which are working on different channels increase the network throughput. However, the utilization of multiple channels increases economic cost taking much frequency spectrum, and the cluster, the backbone tree and the spanning tree must be rebuilt periodically due to the assumption that every node must know the coordinate information of the entire network. The former makes the protocol uneconomical and the latter incurs much overhead. **ASN**.