On the scalability of ad hoc routing protocols

A novel framework is presented for the study of scalability in ad hoc networks. Using this framework, the first asymptotic analysis is provided with respect to network size, mobility, and traffic for each fundamental class of ad hoc routing algorithms. Protocols studied include the following: Plain Flooding (PF), Standard Link State (SLS), Dynamic Source Routing (DSR), Hierarchical Link State (HierLS), Zone Routing Protocol (ZRP), and Hazy Sighted Link State (HSLS). It is shown that PF and ZRP scale better with mobility, SLS and ZRP scale better with respect to traffic, and HSLS scales better with respect to network size. The analysis provides deeper understanding of the limits and trade-offs inherent in mobile ad hoc network routing. Our analysis is complemented with a simulation experiment comparing HSLS and HierLS. A important contribution of this paper is that HSLS is an scalable, easy-to-implement, alternative to hierarchical approaches for large ad hoc networks.