## 1 Introduction  
Recent advances in micro-electro-mechanical systems and low power and highly integrated digital electronics have led to the development of micro-sensors. As the cost of the individual sensors has been reduced, it has become feasible to deploy large numbers of sensors in a relevant region, constituting large-scale wireless sensor networks (WSNs). In general, the application scenarios of a WSN include target field imaging, intrusion detection, weather monitoring, security and tactical surveillance, distributed computing, detecting ambient conditions such as temperature, movement, sound, light, or the presence of certain objects, inventory control, and disaster management [1]. Large-scale deployment of the nodes can increase the accuracy of the information and enhance the scope for detection, and so on. Therefore research focusing on large-scale WSNs has attracted much more attention. Compared with normal _ad hoc_ networks, there are some special considerations concerning routing protocol design for WSNs. First of all, because the individual sensor devices have limited power and battery replacement or recharging is typically not practical, any routing protocol must work in an energy-efficient manner. In addition, the nodes in the network are always randomly deployed and the position information is not available without a Global Positioning System (GPS) service for the sake of economic cost reduction. Especially in large-scale WSNs where the numbers of nodes can reach thousands or even more, the scalability objective of the routing protocol to handle the long distance which the sensed data must travel from sensors to collection nodes and the huge amount of network overhead must be taken into consideration. Normally, according to the underlying network structure, the traditional WSNs routing protocols fall into three classes known as flat, hierarchical and location-based [1]. In flat networks, all the nodes play the same role and coordinate to relay the sensed packets to specific sink nodes. The routing protocols belonging in this category include Sensor Protocols for Information via Negotiation (SPIN [2,3]), Directed Diffusion (DD [4]), Rumor Routing [5], Gradient-based routing (GBR [6]), Energy-Aware Routing (EAR [7]), and the Minimum Cost Forwarding Algorithm (MCFA [8]), _etc_. In hierarchical networks, all the nodes are divided into several groups with different responsibility levels. The high level nodes are responsible for aggregation and some management work, and the low level nodes for sensing the surroundings and collecting information. There are also plenty of routing protocols in this hierarchical family, such as Low Energy Adaptive Clustering Hierarchy (LEACH [9]), Threshold-Sensitive Energy Efficient Sensor Network Protocol (TEEN [10]), Minimum Energy Communication Network (MECN [11]), Self-Organizing Protocol (SOP [12]), Sensoraggregates routing [13], Virtual Grid Architecture routing (VGA [14]), and Hierarchical Power-Aware Routing (HPAR [15]), _etc._ Location-based protocols utilize positional information to relay data to some desired regions rather the whole network, while additional hardware devices for acquiring the location of other nodes is indispensable. The protocols falling into this part include Geographic Adaptive Fidelity (GAF [16]), Geographic and Energy Aware Routing (GEAR [17]), Greedy Other Adaptive Face Routing (GOAFR [18]), and Span [19], _etc._  
In the literature there are numerous and rich works surveying the routing protocols for WSNs from different points of view and with different concerns. They all analyze the strengths and weaknesses of the respective routing protocols, but none of the papers has focused on the scalability objective of the protocols especially designed for large-scale WSNs. For instance, [PERSON] _et al._ in [1] presented a comprehensive survey of routing techniques which are classified based on the network structure and protocol operation respectively, and outlined challenges and future research directions in this aspect.