Low latency wireless ad hoc networking: power and bandwidth challenges and a solution

ABSTRACT

This paper is concerned with the scaling of the number of relay nodes (i.e., hops) individual messages have to transit through in a large-scale wireless ad hoc network (WANET); we call this hop-count as network latency (NL). A large network latency affects all aspects of data communication in a WANET, including an increase in delay, packet loss, and the power needed to process and store messages in nodes lying on the relay path. We consider network management and data routing challenges in WANETs with scalable network latency, e.g., when NL increases only polylogarithmically in the network size. On the physical side, reducing network latency imposes a significantly higher power and bandwidth demand on nodes, and are captured in a set of new bounds derived in this paper. On the protocol front, designing distributed routing protocols that can guarantee the delivery of data packets within a scalable number of hops is a challenging task. To solve this, we introduce multiresolution randomized hierarchy (MRRH), a novel power and bandwidth efficient WANET protocol with scalable network latency. MRRH uses a randomized algorithm for building and maintaining a random hierarchical network topology, which together with the proposed routing algorithm, can guarantee efficient delivery of data packets in the wireless network. For a network of size N, MRRH can provide an average latency of only O(log³ N). The power consumption and bandwidth requirements of MRRH are shown to be nearly optimal for the latency it provides. Therefore, MRRH is a provably efficient candidate for truly large-scale wireless ad hoc networking.

REFERENCES

• 1: [1] S. Giordano and I. Stojmenovic, "Position Based Routing Algorithms for Ad Hoc Networks: A Taxonomy," in Ad Hoc Wireless Networking. Boston, MA: Kluwer, 2004, pp. 103-136.
• 2: [2] R. Negi and A. Rajeswaran, "Capacity of power constrained ad hoc networks," in Proc. IEEE INFOCOM, Hong Kong, Mar. 2004.
• 3: [3] R. Nelson and L. Kleinrock, "The spatial capacity of a slotted ALOHA multihop packet radio network with capture," IEEE Trans. Commun., vol. COM-32, no. 6, pp. 684-694, 1984.
• 4: [4] T. C. Hou and V. O. K. Li, "Transmission range control in multihop packet radio networks," IEEE Trans. Commun., vol. COM-34, no. 1, pp. 38-44, 1986.
• 5: [5] H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. Commun., vol. COM-32, no. 3, pp. 246-257, 1984.
• 6: Xu Lin , Mouhsine Lakshdisi , Ivan Stojmenovic, Location based localized alternate, disjoint, multi-path and component routing schemes for wireless 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/501449.501461]
• 7: [7] M. Joa-Ng and I. Lu, "A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1415-1425, Aug. 1999.
• 8: Qun Li , Javed Aslam , Daniela Rus, Online power-aware routing in wireless Ad-hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.97-107, July 2001, Rome, Italy [doi>10.1145/381677.381687]
• 9: Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]
• 10: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 11: Susanta Datta , Ivan Stojmenovic , Jie Wu, Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks, Cluster Computing, v.5 n.2, p.169-178, April 2002 [doi>10.1023/A:1013985610753]
• 12: [12] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 13: [13] R. Meester and R. Roy, Continuum Percolation. Cambridge, U.K.: Cambridge Univ. Press, 1996.
• 14: [14] P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming, W. M. McEneaney, G. Yin, and Q. Zhang, Eds. Boston, MA: Birkhäuser, 1998.
• 15: Rajiv Gandhi , Srinivasan Parthasarathy , Arunesh Mishra, Minimizing broadcast latency and redundancy in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778442]
• 16: [16] C. Chou and A. Misra, "Low latency multimedia broadcast in multi-rate wireless meshes," in Proc. 1st IEEE Workshop on Wireless Mesh Networks (WIMESH), Sep. 2005.
• 17: Baruch Awerbuch , David Holmer , Herbert Rubens, The medium time metric: high throughput route selection in multi-rate ad hoc wireless networks, Mobile Networks and Applications, v.11 n.2, p.253-266, April 2006 [doi>10.1007/s11036-005-4477-x]
• 18: Abbas El Gamal , James Mammen , Balaji Prabhakar , Devavrat Shah, Optimal throughput-delay scaling in wireless networks: part I: the fluid model, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2568-2592, June 2006 [doi>10.1109/TIT.2006.874379]
• 19: Xiaojun Lin , Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, Degenerate delay-capacity tradeoffs in ad-hoc networks with Brownian mobility, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2777-2784, June 2006 [doi>10.1109/TIT.2006.874544]
• 20: [20] R. Negi and A. Rajeswaran, "Scheduling and power adaptation for networks in the Ultra Wide Band regime," in Proc. IEEE Globecom, Dallas, TX, Dec. 2004, pp. 139-145.
• 21: Eszter Kail , Gábor Németh , Zoltán Richárd Turányi, Throughput of ideally routed wireless ad hoc 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/501449.501457]
• 22: [22] IEEE Standard for Local and Metropolitan Area Networks: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification , IEEE Std 802.11-1997.
• 23: Power-Aware Localized Routing in Wireless Networks, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.371, May 01-05, 2000
• 24: Ivan Stojmenovic , Xu Lin, Loop-Free Hybrid Single-Path/Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.12 n.10, p.1023-1032, October 2001 [doi>10.1109/71.963415]
• 25: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 26: [26] B. A. Rezaei, N. Sarshar, and V. P. Roychowdhury, "Random walks in a dynamic small-world space: Low-latency optimal routing in large-scale sensor networks," ACM Trans. Sensor Networks, 2005, submitted for publication.
• 27: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 28: [28] S. Banerjee and A. Misra, "Energy efficient reliable communication for multi-hop wireless networks," in Proc. Wireless Networks (WINET'03).
• 29: [29] S. Banerjee and A. Misra, "Adapting transmission power for optimal energy reliable multi-hop wireless communication," in Proc. Wireless Optimization Workshop (WiOpt'03), Sophia-Antipolis, France, Mar. 2003.
• 30: [30] J. Kuruvila, A. Nayak, and I. Stojmenovic, "Hop count optimal position based packet routing algorithms for ad hoc wireless networks with a realistic physical layer," in Proc. IEEE MASS, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Management, Performance

Keywords:
multi-resolution randomized hierarchy, network latency, scalable routing, wireless ad hoc networks