## 3 Comparison among the Routing Protocols and Open Issues  
Our survey shows that each of the various routing protocols has its own strengths and weaknesses, the chief reason being that the design of protocols depends mainly on the different objectives. We summarize recent results on routing protocols in large-scale WSNs in Table 1. The table shows how different routing protocols fall under different categories, and also compares them according to different metrics. A brief explanation for these metrics follows:  
**Message Complexity**. An inevitable consideration in the scalability of routing protocols is the complexity properties of routing protocols. Especially message complexity, which represents the number of the exchanged messages needed for route discovery, plays a significant role in the assessment of the scalability of routing protocols. In general, the total number of messages exchanged for route discovery depends on the overall network size, such as the total number of the nodes in the network or the total diameter (in terms of number of wireless hops) of the network. For instance, \(o(n)\) describes the message complexity when each node has to rebroadcast a packet, and the complexity \(o(\sqrt{n})\) represents that a particular or several routing path are followed. A polynomial \(o(n)\) is related to parameter \(n\) representing the number of the nodes in the network, and that means the polynomial is linear with the network size. However, to the best of our knowledge, the existing formally analyzed routing protocols do not scale well with the total network size. There is a protocol named cluster overlay broadcast (COB) [46] used in mobile _ad-hoc_ networks (MANETs); its message complexity is quadratic in the shortest source-destination distance and independent of the total number of nodes in the network, and this protocol is proved more scalable in large-scale network. Although COB was originally applied for MANET, it was extended to the scenario of WSNs [47]. Reducing the message complexity and overhead, this heuristic idea deserves to be considered in the routing protocol design for large-scale WSNs. **Memory Requirement**. The memory requirements of the whole network depend on whether each node has to store some data or routing information, such as the data packets which are waiting to be forwarded, neighbor information, cluster information, route information and so on. This can be represented by a polynomial which is related to the parameter \(n\) concerning the number of the nodes. For instance, if each node has to store its neighbor information, the memory requirement can be described by \(o(n)\). Please note that the result of the memory requirement represents the worst network case discussed in this paper. For instance, a method of event-based clustering is proposed in ARPEES [30] and this method requires the nodes nearby the event store their neighbor information, we assume that the events occurs in the whole network, and thus all the nodes of the network need to store the neighbor information instead of particular nodes. With the network density enhancing caused by the increase of the network size, the nodes need to store many more information. Due to the limited memory capacity of the large-scale WSNs, however, how to efficiently utilize these storage resources is of great significance for enhancing the scalability of the routing protocols. **Localization**. Position information is of great help to enhance the accuracy and the efficiency of routing protocols, and generally this information can be acquired by GPS. In 2L-OFFIS [28], the nodes can get the position information, and that makes the directed transmission substitute for broadcast communication of the control packet. Therefore the control overhead is decreased. However, the utilization of GPS increases the economic costs, which makes the use of GPS in large-scale deployment of sensors impractical. **Data Aggregation**.