Inducing multiscale clustering using multistage MAC contention in CDMA ad hoc networks

ABSTRACT

This paper proposes a new principle for designing MAC protocols for CDMA-based ad hoc networks-inducing spatial clustering in contending transmitters/receivers. We first highlight the advantages of CDMA in handling quality of service (QoS) requirements, enhancing energy efficiency, and enabling spatial multiplexing of bursty traffic. Then, based on stochastic geometric models and simulation, we show how idealized contention resolution among randomly distributed nodes results in clustering of successful transmitters and receivers, in turn leading to efficient spatial reuse. This motivates the central idea of the paper which is to explicitly induce clustering among contending nodes to achieve even better spatial reuse. We propose two distributed mechanisms to realize such clustering and show substantial capacity gains over simple random access/ALOHA-like and even RTS/CTS-based protocols. We examine under what regimes such gains can be achieved, and how clustering and contention resolution mechanisms should be optimized to do so. We propose the design of ad hoc networks supporting hop-by-hop relaying on different spatial scales. By allowing nodes to relay beyond the set of nearest neighbors using varying transmission distances (scales), one can reduce the number of hops between a source and destination so as to meet end-to-end delay requirements. To that end we propose a multi-scale MAC clustering and power control mechanism to support transmissions with different ranges while achieving high spatial reuse. The considerations, analysis and simulations included in this paper suggest that the principle of inducing spatial clustering in contention has substantial promise towards achieving high spatial reuse, QoS, and energy efficiency in CDMA ad hoc networks.

REFERENCES

• 1: [1] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000.
• 2: 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]
• 3: [3] M. Haenggi and D. Puccinelli, "Routing in ad hoc networks: A case for long hops," IEEE Commun. Mag., vol. 43, no. 10, pp. 93-101, Oct. 2005.
• 4: [4] M. Stemm and R. H. Katz, "Measuring and reducing energy consumption of network interfaces in hand-held devices," IEICE Trans. Commun.--Special Issue Mobile Comput., vol. E80-B, no. 8, pp. 1290-1302, 1997.
• 5: [5] K. S. Gilhousen, I. M. Jacobs, R. Padovani, A. J. Viterbi, L. A. Weaver, and C. E. Wheatley, "On the capacity of a cellular CDMA system," IEEE Trans. Veh. Technol., vol. 40, no. 2, pp. 303-312, May 1991.
• 6: [6] M. Pursley, "The role of spread spectrum in packet radio networks," Proc. IEEE, vol. 75, no. 1, pp. 116-134, Jan. 1987.
• 7: Timothy J. Shepard, A channel access scheme for large dense packet radio networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.219-230, August 28-30, 1996, Palo Alto, California, United States
• 8: Steven Weber , Gustavo de Veciana, Rate adaptive multimedia streams: optimization and admission control, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1275-1288, December 2005 [doi>10.1109/TNET.2005.860105]
• 9: [9] F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler, "An ALOHA protocol for multihop mobile wireless networks," IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 421-436, Feb. 2006.
• 10: [10] T. ElBatt and A. Ephremides, "Joint scheduling and power control for wireless ad hoc networks," in Proc. IEEE INFOCOM, 2002, pp. 976-984.
• 11: [11] J. J. Garcia-Luna-Aceves and J. Raju, "Distributed assignment of codes for multihop packet-radio networks," in Proc. IEEE MILCOM, 1997, pp. 450-454.
• 12: [12] M. Joa-Ng and I. Lu, "Spread spectrum medium access protocol with collision avoidance in mobile ad hoc wireless network," in Proc. IEEE INFOCOM, 1999, pp. 776-783.
• 13: [13] J. P. Monks, V. Bharghavan, and W. Hwu, "A power controlled multiple access protocol for wireless packet networks," in Proc. IEEE INFOCOM , 2001, pp. 219-228.
• 14: Alaa Muqattash , Marwan Krunz, CDMA-based MAC protocol for wireless 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.778434]
• 15: [15] C. R. Lin and M. Gerla, "Adaptive clustering for mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 15, no. 7, pp. 1265-1275, Sep. 1997.
• 16: [16] V. Kawadia and P. Kumar, "Power control and clustering in ad hoc networks," in Proc. IEEE INFOCOM, 2003, pp. 459-469.
• 17: [17] B. Tavli and W. B. Heinzelman, "MH-TRACE: Multihop time reservation using adaptive control for energy efficiency," IEEE J. Sel. Areas Commun., vol. 22, no. 5, pp. 942-953, Jun. 2004.
• 18: [18] D. Stoyan, W. Kendall, and J. Mecke, Stochastic Geometry and Its Applications . Chichester, U.K.: Wiley, 1995.
• 19: [19] J. Stine and G. de Veciana, "A paradigm for quality of service in wireless ad hoc networks using synchronous signaling and node states," IEEE J. Sel. Areas Commun., vol. 22, no. 7, pp. 1301-1321, Sep. 2004.
• 20: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 21: [21] J. Stine, G. de Veciana, K. H. Grace, and R. C. Durst, "Orchestrating spatial reuse in wireless ad hoc networks using synchronous collision resolution (SCR)," J. Interconnection Networks, vol. 3, no. 3-4, pp. 167-198, Sep.-Dec. 2002.
• 22: Alaa Muqattash , Marwan Krunz, A single-channel solution for transmission power control in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989486]
• 23: R. Rozovsky , P. R. Kumar, SEEDEX: a MAC protocol for 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/501426.501427]
• 24: [24] E. S. Sousa and J. A. Silvester, "Optimum transmission ranges in a direct-sequence spread-spectrum multihop packet radio network," IEEE J. Sel. Areas Commun., vol. 8, no. 5, pp. 762-771, Jun. 1990.
• 25: [25] L. Kleinrock and J. Silvester, "Spatial reuse in multihop packet radio networks," Proc. IEEE, vol. 751, no. 1, pp. 156-167, Jan. 1987.
• 26: Lichun Bao , J.J. Garcia-Luna-Aceves, Transmission scheduling in ad hoc networks with directional antennas, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570652]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Management

Keywords:
Ad hoc network, CDMA, MAC, clustering, contention