Abstract
As mobile ad hoc networks (MANETs) are emerging as important components in critical and large-scale applications, it is crucial to develop MANET routing mechanisms with provably low complexity. In this paper, we give a tutorial overview of the efficient use of elementary node clustering and route request broadcast mechanisms for low-complexity MANET routing. We explain these mechanisms with illustrative examples and discuss their theoretical performance characteristics. We demonstrate that node clustering with constant density and route request broadcasting with a doubling radius technique over the network of cluster leaders can be employed for MANET routing with theoretically proven low complexity. Moreover, we contrast these efficient elementary clustering and route request broadcast mechanisms with clustering and route information accumulation mechanisms in the widely studied AODV and DSR routing protocols and discuss the implications of these various mechanisms for scalable MANET routing.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abolhasan M., Wysocki T., Dutkiewicz E. (2004) “A Review of Routing Protocols for Mobile Ad Hoc Networks”. Ad Hoc Networks, 2(1): 1–22
Hong X., Xu K., Gerla M., (2002) “Scalable Routing Protocols for Mobile Ad Hoc Networks”. IEEE Network, 16(4): 11–21
Rajamaran R., (2002) “Topology Control and Routing in Ad Hoc Networks: A survey”. SIGACT News, 33:60–73
Sankar A., Liu Z., (2004) “Maximum Lifetime Routing in Wireless Ad-hoc Networks”, in Proc. of IEEE Infocom, Hong Kong
Santivanez C.A., McDonald B., Stavrakakis I., Ramanathan R., (2002) “On the Scalability of Ad Hoc Routing Protocols”, in Proc. of IEEE Infocom, New York, NY 1688–1697
A. Srinivas and E. Modiano, “Minimum Energy Disjoint Path Routing in Wireless Ad-hoc Networks”, in Proc. of ACM MobiCom, San Diego, CA pp. 122–133, 2003.
Sucec J., Marsic I., (2004) “Hierarchical Routing Overhead in Mobile Ad Hoc Networks”. IEEE Transactions on Mobile Computing, 3(1):46–56
Huang H., Richa A.W., Segal M., (2004) “Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad Hoc Networks”. Mobile Networks and Applications (MONET) 9(2):151–161
L. Ritchie, H.-S. Yang, A.W. Richa, and M. Reisslein, “Cluster Overlay Broadcast (COB): MANET Routing with Complexity Polynominal in Source-Destination Distance”, IEEE Transactions on Mobile Computing, Vol. 5, No. 6, pp. 653–667, 2006.
E.M. Belding-Royer, “Multi-level Hierarchies for Scalable Ad Hoc Routing” Wireless Networks, Vol. 9, No. 5, pp. 461–478, 2003.
Belding-Royer E.M., Perkins C.E., (2003) “Evolution and Future Directions of the Ad Hoc On-demand Distance-vector Routing Protocol”. Ad Hoc Networks 1(1):125–150
Ephremides A., Wieselthier J.E., Baker D.J. (1987) “A Design Concept for Reliable Mobile Radio Networks with Frequency Hopping Signalling”. Proceedings of the IEEE 75(1): 56–73
Gerla M., Tsai J.T.C. (1995) “Multicluster Mobile Multimedia Radio Networks”. ACM-Baltzer Journal of Wireless Networks, 1(3):255–256
C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” in Proc. IEEE Singapore Int. Conf. on Networks, Singapore pp. 197–211, 1997
Yu J.Y., Chong P.H.J., (2005) “A survey of Clustering Schemes for Mobile Ad Hoc Networks”. IEEE Communications Surveys and Tutorials 7(1):32–48
Liang O., Sekercioglu A., Mani N. (2006) “A Survey of Multipoint Relay based Broadcast Schemes in Wireless Ad Hoc Networks”. IEEE Communications Surveys and Tutorials 8(4):30–46
Viswanath K., Obraczka K., Tsudik G. (2006) “Exploring Mesh and Tree-based Multicast Routing Protocols for MANETs”. IEEE Transactions on Mobile Computing 5(1):28–42
Tseng Y.-C., Ni S.-Y., Chen Y.-S., Sheu J.-P. (2002) “The Broadcast Storm Problem in a Mobile Ad Hoc Network”. Wireless Networks 8(2–3):153–167
Williams B., Metha D., Camp T., Navidi W. (2004) “Predictive Models to Rebroadcast in Mobile Ad Hoc Networks”. IEEE Transactions on Mobile Computing 3(3):295–303
Wu J., Dai F., (2005) “Efficient Broadcasting with Guaranteed Coverage in Mobile Ad Hoc Networks”. IEEE Transactions on Mobile Computing 4(3):259–270
Lee S.-J., Belding-Royer E.M., Perkins C.E. (2003) “Scalability Study of the Ad Hoc On-demand Distance Vector Routing Protocol”. International Journal of Network Management, 13(2):97–114
K. Xu and M. Gerla, “A Heterogeneous Routing Protocol based on a New Stable Clustering Scheme”, in Proc. of IEEE Milcom, Anaheim, CA pp. 838–843, 2002.
Wu J., Dai F., (2006) “Virtual Backbone Construction in MANETs using Adjustable Transmission Ranges”. IEEE Transactions on Mobile Computing, 5(9):1188–1200
D.B. Johnson, D.A. Malts, and J. Broch, “DSR: The Dynamic Source Routing Protocol for Multi-hop Wireless Ad Hoc Networks”, in Ad Hoc Networking, Chapter 5, C.E. Perkins, Ed. Reading, MA: Addison–Wesley, pp. 139–172, 2001
Y. Qin and J. He, “The Impact on Throughput of Hierarchical Routing in Ad Hoc Wireless Networks”, in Proc. of IEEE ICC, Seoul, Korea pp. 3010–3014, 2005
Perkins C.E., Belding-Royer E.M., Das S.R., Marina M.K. (2001) “Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks”, IEEE Personal Communications, 8(1):16–28
X. Yu and Z. Kedem, “A Distributed Adaptive Cache Update Algorithm for the Dynamic Source Routing Protocol”, in Proc. of IEEE Infocom, Miami, FL, 2005, pp. 730–739.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yang, HS., Ritchie, L., Richa, A.W. et al. MANET Routing with Provably Low Complexity Through Constant Density Clustering and Route Request Broadcast. Wireless Pers Commun 43, 605–621 (2007). https://doi.org/10.1007/s11277-007-9252-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11277-007-9252-9