Inducing spatial clustering in MAC contention for spread spectrum ad hoc networks

ABSTRACT

This paper proposes a new principle for designing MAC protocols for spread spectrum based ad hoc networks -- inducing spatial clustering in contending transmitters/receivers. We first highlight the advantages of spread spectrum 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 ranges (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 spread spectrum ad hoc networks.

REFERENCES

• 1: F. Baccelli, B. Blaszczyszyn, and P. Muhlethaler. A spatial reuse aloha MAC protocol for multihop wireless mobile networks. In Proc. of Annual ALLERTON Conference on Communication., 2003.
• 2: 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]
• 3: T. ElBatt and A. Ephremides. Joint scheduling and power control for wireless ad-hoc networks. In Proc. of IEEE INFOCOM, 2002.
• 4: K. S. G. et. al. On the capacity of a cellular CDMA system. IEEE Trans. on Veh. Technology, 40(2):303--12, May 1991.
• 5: J. Garcia-Luna-Aceves and J. Raju. Distributed assignment of codes for multihop packet-radio networks. In Proc. of IEEE MILCOM, 1997.
• 6: 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]
• 7: P. Gupta and P. Kumar. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications, Birkhauser, Boston, pages 547 -- 566, 1998.
• 8: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, March 2000.
• 9: M. Joa-Ng and I. Lu. Spread spectrum medium access protocol with collision avoidance in mobile ad-hoc wireless network. In Proc. of IEEE INFOCOM, 1999.
• 10: L. Kleinrock and J. Silvester. Spatial reuse in multihop packet radio networks. Proceedings of the IEEE, 751(1):156--167, January 1987.
• 11: 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]
• 12: M. Pursley. The role of spread spectrum in packet radio networks. Proceedings of the IEEE, 75(1):116--134, 1987.
• 13: 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]
• 14: 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
• 15: E. Sousa and J. Silvester. Optimum transmission ranges in a direct-sequence spread-spectrum multihop packet radio network. IEEE Journal on Selected Areas in Communications, 8(5):762--771, June 1990.
• 16: M. Stemm and R. H. Katz. Measuring and reducing energy consumption of network interfaces in hand--held devices. IEICE Trans. on Communications -- Special Issue on Mobile Computing, E80--B(8):1290--1302, 1997.
• 17: J. Stine and G. de Veciana. A paradigm for quality of service in wireless ad hoc networks using synchronous signaling and node states. IEEE JSAC Special Issue on Quality of Service Delivery in Variable Topology Networks, 22(7):1301--1321, September 2004.
• 18: D. Stoyan, W. Kendall, and J. Mecke. Stochastic Geometry and its Applications. J. Wiley & Sons, Chichester, 1995.
• 19: S. Weber, X. Yang, G. de Veciana, and J. Andrews. Transmission capacity of CDMA ad hoc networks. In Proc. of IEEE ISSSTA, September 2004.
• 20: X. Yang and G. de Veciana. Designing MAC protocols for spread spectrum ad hoc networks: Thinning versus spatial state-dependent packing. In Proc. of CISS, March 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

General Terms:
Algorithms, Design, Performance

Keywords:
CDMA, MAC, ad hoc networks, clustering, spread spectrum