## 2 Routing Protocols in Large-Scale WSNs
### Control Overhead Reduction Algorithms  
_DECROP_. A simple but efficient routing protocol named Distributed and Effective Cluster Routing Protocol (DECROP) is proposed in [24] with the purpose of decreasing the number of control messages, shortening the average end-to-end delay and satisfying other requirements such as data aggregation _etc._ DECROP includes three processes: initialization with distributed cluster formation, data transmission and route maintenance. During the initialization period, a cluster is formed simultaneously to aggregate data packets from cluster members and to reduce transmission power during the delivery to the base station (BS). The initialization aims at making each sensor confirm its neighbor nodes and the pre-hop node along the path to the BS which is node 0 in Figure 2. Initially the BS broadcasts an initialization message. The node receiving the message for the first time takes the transmitter as the pre-hop node, and renews the transmitting ID in the message with its own ID and rebroadcasts the message. Then the receiver will ignore the subsequent messages. In the end, all the nodes build the forwarding path as Figure 2 shows. During the initialization and after collecting its neighbor information, the local sensor will announce itself as cluster head (CH) by broadcasting a declaration message when its total neighbor count reaches \(N\). \(N\) is a network parameter associated with communication radius and nodes deployment. The one-hop neighbors start to join the cluster by sending request messages and the two-hop neighbors have to resort to the one-hop neighbors by delivering request messages. Therefore, the clusters are created in two hops instead of the club structure (one hop). It is possible that some nodes are far away from the cluster head and have not joined any cluster. As shown in Figure 2, the red double-head arrow represents that node 21 is a single node that has not joined any cluster. During data transmission, the cluster head aggregates data packets from the cluster members, tags the packets with cluster head information, and delivers them to the pre-hop nodes which are confirmed during initialization process. During the delivery of the packets, the intermediate nodes could record the path backwards to the specific cluster head. By this way, it is convenient to route packets from the BS to the destinations according to its cluster head information. As a special case shown in Figure 2,  
Figure 2: Distributed cluster forming process in DECROP. node 21 is sending its data packets directly to the pre-hop node instead of any cluster head. When these packets arrive at a cluster head, node 21 will be incorporated in its cluster. If some links are broken, the route maintenance process is triggered. The downstream node will broadcast an error message including the unreachable pre-hop node and its hop count towards the BS. One of the receivers will reply the message and act as the new pre-hop node if the unreachable node is not its own pre-hop node and its hop count towards the BS is less than that recorded in the error message. After the initialization process, all the nodes will have constructed the forwarding path thus saving a large amount of time and overhead for building routes. The adoption of the cluster model enables the data aggregation. In the cluster, the nodes are organized by two hops instead of the conventional club way (such as the single-hop communication in LEACH [9]) and the amount of clusters is reduced accordingly. However, when the cluster is larger, the energy consumption of the cluster head is increased considerably. Another disadvantage is that the tree route makes the nodes closer to the BS consume energy faster which will reduce the overall network lifespan. _ONCP_. [PERSON] _et al._ in [25,26] proposed a routing solution called Off-Network Control Processing (ONCP) that achieves control scalability in large-scale sensor networks by handing over certain amount of routing functions to an \"off-network\" server.