Topology control and routing in ad hoc networks: a survey

ABSTRACT

An ad hoc wireless network, or simply an ad hoc network, consists of a collection of geographically distributed nodes that communicate with one other over a wireless medium. An ad hoc network differs from cellular networks in that there is no wired infrastructure and the communication capabilities of the network are limited by the battery power of the network nodes. One of the original motivations for ad hoc networks is found in military applications. A classic example of ad hoc networking is network of war fighters and their mobile platforms in battlefields. Indeed, a wealth of early research in the area involved the development of packet-radio networks (PRNs) and survivable radio networks [16]. While military applications still dominate the research needs in ad hoc networking, the recent rapid advent of mobile telephony and plethora of personal digital assistants has brought to the fore a number of potential commercial applications of ad hoc networks. Examples are disaster relief, conferencing, home networking, sensor networks, personal area networks, and embedded computing applications [37].The lack of a fixed infrastructure in ad hoc networks implies that any computation on the network needs to be carried out in a decentralized manner. Thus, many of the important problems in ad hoc networking can be formulated as problems in distributed computing. However, there are certain characteristics of ad hoc networks that makes this study somewhat different than traditional work in distributed computing. In this article, we review some of the characteristic features of ad hoc networks, formulate problems and survey research work done in the area. We focus on two basic problem domains: topology control, the problem of computing and maintaining a connected topology among the network nodes, and routing. This article is not intended to be a comprehensive survey on ad hoc networking. The choice of the problems discussed in this article are somewhat biased by the research interests of the author.The remainder of this article is organized as follows. In Section 2, we describe various aspects relevant to modeling ad hoc networks. In Section 3, we discuss topology control. Since the nodes of an ad hoc network are often associated with points in 2-dimensional space, topology control is closely tied to computational geometry; we will briefly review this relationship and extant work in the area. In Section 4, we discuss routing protocols for ad hoc networks. After a brief overview of the many protocols that have been proposed, we discuss alternative approaches based on the adversarial network model.

REFERENCES

• 1: Micah Adler , Christian Scheideler, Efficient communication strategies for ad-hoc wireless networks (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.259-268, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277692]
• 2: S. Agarwal, S. Krishnamurthy, R. Katz, and S. Dao. Distributed power control in ad-hoc wireless networks. In Proceedings of PIMRC, 2001.
• 3: William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167250]
• 4: A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
• 5: Sunil Arya , Michiel H. M. Smid, Efficient Construction of a Bounded Degree Spanner with Low Weight, Proceedings of the Second Annual European Symposium on Algorithms, p.48-59, September 26-28, 1994
• 6: Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564910]
• 7: P. Berenbrink , A. Brinkmann , C. Scheideler, Simple Routing Strategies for Adversarial Systems, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.158, October 14-17, 2001
• 8: B. Awerbuch, A. Brinkmann, and C. Scheideler. Unicasting and multicasting in adversarial systems. Unpublished manuscript, November 2001.
• 9: Baruch Awerbuch , Tom Leighton, Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.487-496, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195238]
• 10: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 11: Bonnie Berger , John Rompel , Peter W. Shor, Efficient NC algorithms for set cover with applications to learning and geometry, Journal of Computer and System Sciences, v.49 n.3, p.454-477, Dec. 1994
• 12: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
• 13: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 14: D. Eppstein. Spanning trees and spanners. In J. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425-461. Elsevier, Amsterdam, 2000.
• 15: Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
• 16: James A. Freebersyser , Barry Leiner, A DoD perspective on mobile Ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 17: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 18: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 19: Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001 [doi>10.1145/568438.568451]
• 20: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 21: P. Gupta and P. Kumar. Capacity of wireless networks. IEEE Transactions on Information Theory, IT-46:388-404, 2000.
• 22: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 23: Yehuda Hassin , David Peleg, Sparse communication networks and efficient routing in the plane (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.41-50, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343514]
• 24: L. Jia, R. Rajaraman, and T. Suel. An efficient distributed algorithm for constructing small dominating sets. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing, pages 33-42, August 2001.
• 25: D. Johnson and D. Maltz. Dynamic source routing in adhoc wireless networks. In T. Imielinski and H. Korth, editors, Mobile Computing, pages 153-181. Kluwer Academic Publishers, 1996.
• 26: F. Kamoun and L. Kleinrock. Stochastic performance evaluation of hierarchical routing for large networks. Computer Networks, 3(5):337-353, 1979.
• 27: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 28: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 29: Shay Kutten , David Peleg, Fast distributed construction of small k-dominating sets and applications, Journal of Algorithms, v.28 n.1, p.40-66, July 1, 1998 [doi>10.1006/jagm.1998.0929]
• 30: T. Kwon and M. Gerla. Clustering with power control. In Proceedings of MILCOM, volume 2, pages 1424-1428, 1999.
• 31: C. Lau and C. Leung. Capture models for mobile packet radio networks. IEEE Transactions on Communications, 40:917-925, 1992.
• 32: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 33: B. Liang and Z. Haas. Virtual backbone generation and maintenance in ad hoc network mobility management. In Proceedings of the 2000 IEEE INFOCOM, March 2000.
• 34: J. McQuillan. Adaptive routing algorithsm for distributed computer networks. Technical Report 2831, Bolt Beranek & Newman, May 1974.
• 35: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 36: C. Perkins. Adhoc on demand distance vector (AODV) routing. Internet draft, draft-ietf-manet-aodv-04.txt, October 1999.
• 37: Charles E. Perkins, Ad hoc networking: an introduction, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 38: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 39: C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory of Computing Systems, 32:241-280, 1999.
• 40: Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
• 41: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 42: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 43: V. Rodoplu and T. Meng. Minimum energy mobile wireless networks. IEEE Journal Selected Areas in Communications, 17:1333-1344, August 1999.
• 44: J. Ruppert and R. Seidel. Approximating the d-dimensional complete Euclidean graph. In Proceedings of the 3rd Annual Canadian Conference on Computational Geometry, pages 207-210, 1991.
• 45: Jeffrey S. Salowe, Euclidean spanner graphs with degree four, Discrete Applied Mathematics, v.54 n.1, p.55-66, Sept. 26, 1994 [doi>10.1016/0166-218X(94)90133-3]
• 46: Christian Scheideler, Models and Techniques for Communication in Dynamic Networks, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.27-49, March 14-16, 2002
• 47: Martha Steenstrup, Cluster-based networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 48: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 49: G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261-268, 1980.
• 50: Jean Walrand , Pravin Varaiya, High-performance communication networks (2nd ed.), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 51: P. Wan, G. Calinescu, X. Li, and O. Frieder. Minimum-energy broadcast routing in static ad hoc wireless networks. In Proceedings of the IEEE INFOCOM Conference, 2001.
• 52: Yu Wang , Xiang-Yang Li, Distributed Spanner with Bounded Degree for Wireless Ad Hoc Networks, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.120, April 15-19, 2002
• 53: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed topology control for power efficient operation in multihop wireless ad hoc networks. In Proceedings of IEEE Infocom, 2001.
• 54: J. Wieselthier, G. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of IEEE Infocom, 2000.
• 55: Yu Wang Xiang-Yang Li, Peng-Jun Wan and Ophir Frieder. Sparse power efficient topology for wireless networks. Journal of Parallel and Distributed Computing, 2002.
• 56: A. Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing, 11(4):721-736, 1982.