## 2 Routing Protocols in Large-Scale WSNs
### Control Overhead Reduction Algorithms
The function of the ONCP server is to compute the \"coarse grain\" global routing, which consists of a sequence of regions. During the delivery of sensing task along the global routing, a \"fine grain\" local routing is performed by the local sensor nodes. By this tiered routing approach, wide dissemination of network control messages is avoided. As depicted in Figure 3, the sensing area is pre-partitioned into regions, in which each sensor node maintains a never changed region ID. Figure 3: Network and application model of ONCP. The nodes periodically update the ONCP server with information about the residual energy in the region and the inter-connectivity metrics between regions. The latter is defined as the residual energy of the sensor nodes having direct connection with the ones in the neighboring region. Based on these updates, the server is able to compute the most energy-optimal global routes from each region to an appropriate base station upon receiving sensing requests from users. It should be noted that the global route consists of a sequence of regions from the source region to an appropriate base station. The sensing task request is source routed to the desired region using the region-level global route and the local routes computed on-demand during the propagation. Then the target sensors start generating data at the specified rate, and send the data to the appropriate base station along the global route and the local routes outlined above in the reverse order. Min-hop routing and MaxMin routing [27] are used to compute the global route in order to minimize the end-to-end energy consumption and evenly distribute the energy consumption loads on regions to avoid traffic hot-spots. For a given base station and target sensing region, first the MaxMin value of paths is found, and then the smallest hop-counts path among them is chosen. During the construction of local routes, clustering is adopted as a technique to avoid redundant broadcasts and too much overhead introduction. A cluster head originates and broadcasts a local route request message, which contains the originating cluster head ID, the originating region ID, the target region ID, and a hop-count field. After receiving the message from its own region, the cluster head increments the hop-count of the message and re-floods the message. When the message arrives at a neighboring region that is not the target region, the receivers will discard the message. When the message arrives at the target region, the cluster head replies a local route reply message, which is to be forwarded back to the originating cluster head through the reverse pointers set up during the route request message flooding. By this way, the control message is constrained in the sequence regions of the global route. An advantage of ONCP is that the control overhead incurred during the construction of \"fine grain\" and local route will not grow exponentially as the network expands by computing the \"coarse grain\" global route, because the overhead in the area of sequence regions of global route is limited. Therefore ONCP scales well with growing network size. However, its benefits could be sustained only when the overhead of network status update and sensing task dissemination is lower than the control overhead of global route creation message flooding in other competing approaches. In addition the pre-configuration of region ID in each sensor node adds implementation complexity of ONCP. _2L-OFFIS._ In order to prolong the network lifetime, [PERSON] _et al._[28] proposed a two-layer OFFIS (2L-OFFIS) based on Optimized Forwarding by Fuzzy Inference System (OFFIS) [29] presented earlier. In 2L-OFFIS, the cluster structure inherited from LEACH is adopted, but with either intra-cluster or inter-cluster multi-hop routing during data transmission. A fuzzy inference system is introduced to consider a collection of metrics such as distance, power and link usage in deriving the optimal path from the source to the destination.