Cluster Overlay Broadcast (COB): MANET Routing with Complexity Polynomial in Source-Destination Distance
|
Routing algorithms with time and message complexities that are provably low and independent of the total number of nodes in the network are essential for the design and operation of very large scale wireless mobile ad hoc networks (MANETs). In this paper, we develop and analyze Cluster Overlay Broadcast (COB), a low-complexity routing algorithm for MANETs. COB runs on top of a one-hop cluster cover of the network, which can be created and maintained using, for instance, the Least Cluster Change (LCC) algorithm. We formally prove that the LCC algorithm maintains a cluster cover with a constant density of cluster leaders with minimal update cost. COB discovers routes by flooding (broadcasting) route requests through the network of cluster leaders with a doubling radius technique. Building on the constant density property of the network of cluster leaders, we formally prove that, if there exists a route from a source to a destination node with a minimum hop count of \Delta, then COB discovers a route with at most O(\Delta) hops from the source to the destination node in at most O(\Delta) time and by sending at most O(\Delta^2) messages. We prove this result for arbitrary node distributions and mobility patterns and also show that COB adapts asymptotically optimally to the mobility of the nodes. In our simulation experiments, we examine the network layer performance of COB, compare it with Dynamic Source Routing, and investigate the impact of the MAC layer on COB routing.
[1] 653 R. Wattenhofer, “Ad-Hoc and Sensor Networks: Worst-Case vs. Average-Case,” Proc. Int'l Zurich Seminar Comm., pp. 156-159, 2004.
[2] M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A Review of Routing Protocols for Mobile Ad Hoc Networks,” Ad Hoc Networks, vol. 2, no. 1, pp. 1-22, Jan. 2004.
[3] X. Hong, K. Xu, and M. Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks,” IEEE Network, pp. 11-21, July/Aug. 2002.
[4] C.A. Santivanez, B. McDonald, I. Stavrakakis, and R. Ramanathan, “On the Scalability of Ad Hoc Routing Protocols,” Proc. IEEE Infocom, pp. 1688-1697, June 2002.
[5] A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, “Scalable Routing Strategies for Ad Hoc Wireless Networks,” IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1369-1379, Aug. 1999.
[6] R. Rajamaran, “Topology Control and Routing in Ad Hoc Networks: A Survey,” SIGACT News, vol. 33, pp. 60-73, 2002.
[7] B. Karp and H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proc. ACM MobiCom, pp. 243-254, Aug. 2000.
[8] Y.-B. Ko and N.H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” Wireless Networks, vol. 6, no. 4, pp. 307-321, 2000.
[9] S.-C.M. Woo and S. Singh, “Scalable Routing Protocol for Ad Hoc Networks,” Wireless Networks, vol. 7, no. 5, pp. 513-529, 2001.
[10] J. Broch, D. Maltz, D. Johnson, Y.-C. Hu, and J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” Proc. ACM Mobicom, pp. 85-97, Oct. 1998.
[11] A. Boukerche, “Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks,” Mobile Networks and Applications, vol. 9, pp. 333-342, 2004.
[12] I. Chlamtac, M. Conti, and J.J.N. Liu, “Mobile Ad Hoc Networking: Imperatives and Challenges,” Ad Hoc Networks, vol. 1, no. 1, pp. 13-64, July 2003.
[13] W. Choi and S.K. Das, “Design and Performance Analysis of a Proxy-Based Indirect Routing Scheme in Ad Hoc Wireless Networks,” Mobile Networks and Applications, vol. 8, no. 5, pp. 499-515, 2003.
[14] S.R. Das, R. Castaeda, and J. Yan, “Simulation-Based Performance Evaluation of Routing Protocols for Mobile Ad Hoc Networks,” Mobile Networks and Applications, vol. 5, no. 3, pp. 179-189, 2000.
[15] J.J. Garcia-Luna-Aceves, M. Mosko, and C. Perkins, “Efficient On-Demand Loop-Free Routing in Ad Hoc Networks,” Proc. ACM Symp. Principles of Distributed Computing (PODC), July 2003.
[16] S.-J. Lee, J. Hsu, R. Hayashida, M. Gerla, and R. Bagrodia, “Selecting a Routing Strategy for Your Ad Hoc Network,” Computer Comm., vol. 26, no. 7, pp. 723-733, May 2003.
[17] E.M. Belding-Royer and C.E. Perkins, “Evolution and Future Directions of the Ad Hoc On-Demand Distance-Vector Routing Protocol,” Ad Hoc Networks, vol. 1, no. 1, pp. 125-150, July 2003.
[18] S.J. Philip, J. Ghosh, S. Khedekar, and C. Qiao, “Scalability Analysis of Location Management Protocols for Mobile Ad Hoc Networks,” Proc. IEEE Wireless Comm. and Networking Conf., pp. 183-188, Mar. 2004.
[19] A. Sankar and Z. Liu, “Maximum Lifetime Routing in Wireless Ad-Hoc Networks,” Proc. IEEE Infocom, Mar. 2004.
[20] A. Srinivas and E. Modiano, “Minimum Energy Disjoint Path Routing in Wireless Ad-Hoc Networks,” Proc. ACM MobiCom, pp. 122-133, 2003.
[21] J. Sucec and I. Marsic, “Clustering Overhead for Hierarchical Routing in Mobile Ad Hoc Networks,” Proc. IEEE Infocom, pp. 1698-1706, June 2002.
[22] H. Wu and A. Abouzeid, “Cluster-Based Routing Overhead in Networks with Unreliable Nodes,” Proc. IEEE Wireless Comm. and Networking Conf. (WCNC), Mar. 2004.
[23] G. Pei, M. Gerla, X. Hong, and C. Chiang, “A Wireless Hierarchical Routing Protocol with Group Mobility,” Proc. IEEE Wireless Comm. and Networking, pp. 1538-1542, Sept. 1999.
[24] E.M. Belding-Royer, “Multi-Level Hierarchies for Scalable Ad Hoc Routing,” Wireless Networks, vol. 9, no. 5, pp. 461-478, 2003.
[25] C.-C. Chiang and M. Gerla, “Routing and Multicast in Multihop, Mobile Wireless Networks,” Proc. IEEE Int'l Conf. Universal Personal Comm., pp. 546-551, Oct. 1997.
[26] Z. Haas and M.R. Pearlman, “The Performance of Query Control Schemes for the Zone Routing Protocol,” IEEE/ACM Trans. Networking, vol. 9, no. 4, pp. 427-438, 2001.
[27] M. Jiang, J. Ji, and Y.C. Tay, “Cluster Based Routing Protocol,” internet draft, work in progress, 1999.
[28] P. Krishna, N.H. Vaidya, M. Chatterjee, and D.K. Pradhan, “A Cluster-Based Approach for Routing in Dynamic Networks,” SIGCOMM Computer Comm. Rev., vol. 27, no. 2, pp. 49-64, 1997.
[29] R. Ramanathan and M. Steestrup, “Hierarchically Organized Multihop Mobile Wireless Networks for Quality of Service Support,” Mobile Networks and Applications, vol. 3, no. 1, pp. 101-119, 1999.
[30] P. Sinha, R. Sivakumar, and V. Bharghavan, “CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algorithm,” Proc. IEEE Infocom, pp. 202-209, Mar. 1999.
[31] Y. Yi and M. Gerla, “Scalable AODV with Efficient Flooding Based on On-Demand Clustering,” ACM Mobile Computing and Comm. Rev., vol. 6, no. 3, pp. 98-99, 2002.
[32] S.-J. Lee, E.M. Belding-Royer, and C.E. Perkins, “Scalability Study of the Ad Hoc On-Demand Distance Vector Routing Protocol,” Int'l J. Network Management, vol. 13, no. 2, pp. 97-114, 2003.
[33] K. Xu and M. Gerla, “A Heterogeneous Routing Protocol Based on a New Stable Clustering Scheme,” Proc. IEEE Milcom, pp. 838-843, Oct. 2002.
[34] R. Castaneda and S. Das, “Query Localization Techniques for On-Demand Routing Protocols in Ad Hoc Networks,” Proc. ACM MobiHoc, pp. 186-194, 1999.
[35] H. Dubois-Ferriere, M. Grossglauser, and M. Vetterli, “Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages,” Proc. ACM MobiHoc, pp. 257-266, June 2003.
[36] J. Eriksson, M. Faloutsos, and S. Krishnamurthy, “Scalable Ad Hoc Routing: The Case for Dynamic Addressing,” Proc. IEEE Infocom 2004, Mar. 2004.
[37] C. Gui and P. Mohapatra, “SHORT: Self-Healing and Optimizing Routing Techniques for Mobile Ad Hoc Networks,” Proc. ACM MobiHoc, pp. 279-290, 2003.
[38] K. Alzoubi, P.-J. Wan, and O. Frieder, “New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks,” Proc. 34th Ann. Hawaii Int'l Conf. System Science (HICSS-35), 2002.
[39] D. Baker, A. Ephremides, and J.A. Flynn, “The Design and Simulation of a Mobile Radio Network with Distributed Control,” IEEE J. Selected Areas in Comm., vol. 2, no. 1, pp. 226-237, Jan. 1984.
[40] S. Basagni, “Distributed and Mobility-Adaptive Clustering for Multimedia Support in Multi-Hop Wireless Networks,” Proc. IEEE Vehicular Technology Conf., pp. 19-22, 1999.
[41] G. Calinescu, I.I. Mandoiu, P.-J. Wan, and A.Z. Zelikovsky, “Selecting Forwarding Neighbors in Wireless Ad Hoc Networks,” Mobile Networks and Applications, vol. 9, no. 2, pp. 101-111, 2004.
[42] M. Chatterjee, S.K. Das, and D. Turgut, “WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks,” Cluster Computing, vol. 5, no. 2, pp. 193-204, 2002.
[43] A.B. McDonald and T.F. Znati, “A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks,” IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1466-1487, Aug. 1999.
[44] X.-Y. Li, Y. Wang, P.-J. Wan, and O. Frieder, “Localized Low Weight Graph and Its Applications in Wireless Ad Hoc Networks,” Proc. IEEE Infocom 2004, Mar. 2004.
[45] O. Younis and S. Fahmy, “Distributed Clustering in Ad-Hoc Sensor Networks: A Hybrid, Energy-Efficient Approach,” Proc. IEEE Infocom 2004, Mar. 2004.
[46] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proc. IEEE Singapore Int'l Conf. Networks, pp. 197-211, 1997.
[47] H. Huang, A.W. Richa, and M. Segal, “Approximation Algorithms for the Mobile Piercing Set Problem with Applications to Clustering in Ad Hoc Networks,” Mobile Networks and Applications (MONET), vol. 9, no. 2, pp. 151-161, Apr. 2004.
[48] A.D. Amis and R. Prakash, “Load-Balancing Clusters in Wireless Ad Hoc Networks,” Proc. IEEE Symp. Application-Specific Systems and Software Eng. Technology, pp. 25-32, Mar. 2000.
[49] A. Safwat, H. Hassanein, and H. Mouftah, “Power-Aware Fair Infrastructure Formation for Wireless Mobile Ad Hoc Communications,” Proc. IEEE Globecom, pp. 2832-2836, Nov. 2001.
[50] D.B. Johnson, D.A. Malts, and J. Broch, “DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks,” Ad Hoc Networking, C.E. Perkins, ed., chapter 5, pp. 139-172, Addison-Wesley, 2001.
[51] D.B. Johnson, D.A. Malts, and Y.-C. Hu, “The Dynamic Source Rou-ting Protocol for Mobile Ad Hoc Networks (DSR),” IETF Internet Draft, technical report, July 2004, draft-ietf-manet-dsr-10.txt.
[52] M. Soyturk, E. Cayirci, and A.E. Harmanci, “Virtual Cell Layout Based Dynamic Source Routing Algorithm for the Mobile Subsystem of the Next Generation Tactical Communications Systems,” Proc. IEEE Milcom, pp. 541-545, Oct. 2002.
[53] Y. Yi, M. Gerla, and T.J. Kwon, “The Selective Intermediate Nodes Scheme for Ad Hoc On-Demand Routing Protocols,” Proc. IEEE Int'l Conf. Comm., pp. 3191-3195, May 2002.
[54] A. Muqattash and M.M. Krunz, “A Distributed Transmission Power Control Protocol for Mobile Ad Hoc Networks,” IEEE Trans. Mobile Computing, vol. 3, no. 2, pp. 113-128, Apr.-June 2004.
[55] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly, “Opportunistic Media Access for Multirate Ad Hoc Networks,” Proc. ACM/IEEE Mobicom, Sept. 2002.
[56] J.A. Stine and G. de Veciana, “A Paradigm for Quality-of-Service in Wireless Ad Hoc Networks Using Synchronous Signaling and Node States,” IEEE J. Selected Areas in Comm., vol. 22, no. 7, pp. 1301-1321, Sept. 2004.
[57] X. Yang and N. Vaidya, “On Physical Carrier Sensing in Wireless Ad Hoc Networks,” Proc. IEEE Infocom, Mar. 2005.
Index Terms:
One-hop clustering, algorithm/protocol design and analysis, message complexity, routing protocol, scalability, time complexity, wireless mobile ad hoc network.
Citation:
Luke Ritchie, Hyo-Sik Yang, Andr?a W. Richa, Martin Reisslein, "Cluster Overlay Broadcast (COB): MANET Routing with Complexity Polynomial in Source-Destination Distance," IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 653-667, June 2006, doi:10.1109/TMC.2006.73
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb