A scalable model for channel access protocols in multihop ad hoc networks

ABSTRACT

A new modeling framework is introduced for the analytical study of medium access control (MAC) protocols operating in multihop ad hoc networks. The model takes into account the effect of physical-layer parameters on the success of transmissions, the MAC protocol on the likelihood that nodes can access the channnel, and the connectivity of nodes in the network. A key feature of the model is that nodes can be modeled individually, i.e., it allows a per-node setup of many layer-specific parameters. Moreover, no spatial probability distribution or a particular arrangement of nodes is assumed; the model allows the computation of individual (per-node) performance metrics for any given network topology and radio channel model. To show the applicability of the modeling framework, we model multihop ad hoc networks using the IEEE 802.11 distributed coordination function and validate the results from the model with discrete-event simulations in Qualnet. The results show that our model predicts results that are very close to those attained by simulations, and requires seconds to complete compared to several hours of simulation time.

REFERENCES

• 1: R. Gallager, "A perspective on multiaccess channels," IEEE Trans. Information Theory, vol. IT-31, pp. 124--142, Mar 1985.
• 2: A. Ephremides and B. Hajeck, "Information theory and communication networks: An unconsumated union," IEEE Trans. Information Theory, vol. 44, pp. 2416--2434, Oct 1998.
• 3: Marcelo M. Carvalho , J. J. Garcia-Luna-Aceves, Delay Analysis of IEEE 802.11 in Single-Hop Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.146, November 04-07, 2003
• 4: G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination function," IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, pp. 535--547, March 2000.
• 5: Scalable Network Technologies, Inc, Qualnet Simulator, Version 3.5.
• 6: N. Abramson, "The ALOHA system---another alternative for computer communications," in AFIPS Conf. Proc. FJCC, 1970, vol. 37, pp. 281--285.
• 7: N. Abramson, "The throughput of packet broadcast channels," IEEE Trans. on Communications, vol. COM-25, no. 1, pp. 117--128, Jan 1977.
• 8: L. Kleinrock and F. A. Tobagi, "Packet switching in radio channels: Part I - carrier sense multiple-access modes and their throughput-delay characteristics," IEEE Transactions on Communications, vol. COM-23, no. 12, pp. 1400--1416, 1975.
• 9: F. A. Tobagi and L. Kleinrock, "Packet switching in radio channels: Part II - the hidden terminal problem in carrier sense multiple-access modes and the busy-tone solution," IEEE Transactions on Communications, vol. COM-23, no. 12, pp. 1417--1433, 1975.
• 10: Lawrence G. Roberts, ALOHA packet system with and without slots and capture, ACM SIGCOMM Computer Communication Review, v.5 n.2, p.28-42, April 1975 [doi>10.1145/1024916.1024920]
• 11: L. Kleinrock and S. S. Lam, "Packet switching in a multiaccess broadcast channel: Performance evaluation," IEEE Trans. on Communications, vol. COM-23, no. 4, pp. 410--423, Apr 1975.
• 12: A. Colvin, "CSMA with collision avoidance," Computer Commun., vol. 6, no. 5, pp. 227--235, 1983.
• 13: W. F. Lo and H. T. Mouftah, "Carrier sense multiple access with collision detection for radio channels," in IEEE 13th Int'l Commun. and Energy Conf., 1984, pp. 244--247.
• 14: P. Karn, "MACA - a new channel access method for packet radio," in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, 1990, pp. 134--140.
• 15: Vaduvur Bharghavan , Alan Demers , Scott Shenker , Lixia Zhang, MACAW: a media access protocol for wireless LAN's, Proceedings of the conference on Communications architectures, protocols and applications, p.212-225, August 31-September 02, 1994, London, United Kingdom
• 16: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Floor acquisition multiple access (FAMA) for packet-radio networks, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.262-273, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 17: Chane L. Fullmer , J. J. Garcia-Luna-Aceves, Solutions to hidden terminal problems in wireless networks, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.39-49, September 14-18, 1997, Cannes, France
• 18: D. Raychauduri, "Performance analysis of random access packet-switched code division multiple access systems," IEEE Trans. Commun., vol. COM-29, no. 6, pp. 895--901, Jun 1981.
• 19: D. H. Davis and S. A. Gronemeyer, "Performance of slotted ALOHA random access with delay capture and randomized time of arrival," IEEE Trans. Commun., vol. COM-28, no. 5, pp. 703--710, May 1980.
• 20: M. Musser and J. Daigle, "Throughput analysis of an asynchronous code division multiple access (CDMA) system," in Proc. ICC'82, Philadelphia, PA, Jun 1982.
• 21: M. Pursley, "Throughput of frequency-hopped spread spectrum communications for packet radio networks," in Proc. 1983 CISS, John Hopkins Univ., Baltimore, MD, USA, 1983.
• 22: J. C. Arnbak and W. Van Blitterswijk, "Capacity of slotted aloha in rayleigh-fading channels," IEEE Journal on Selected Areas in Communications, vol. SAC-5, no. 2, pp. 261--269, Feb 1987.
• 23: Frederico Calì , Marco Conti , Enrico Gregori, Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit, IEEE/ACM Transactions on Networking (TON), v.8 n.6, p.785-799, Dec. 2000 [doi>10.1109/90.893874]
• 24: C. Foh and M. Zukerman, "Performance analysis of the IEEE 802.11 MAC protocol," in Proc. of the European Wireless 2002 Conference, Florence, Italy, February 2002, pp. 184--190.
• 25: Hwangnam Kim , Jennifer C. Hou, Improving protocol capacity with model-based frame scheduling in IEEE 802.11-operated WLANs, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939005]
• 26: Z. Hadzi-Velkov and B. Spasenovski, "The influence of flat rayleigh fading channel with hidden terminals and capture over the IEEE 802.11 WLANs," in Proc. 54th IEEE Vehicular Technology Conference, 2001, vol. 2, pp. 972--976.
• 27: Z. Hadzi-Velkov and B. Spasenovski, "On the capacity of IEEE 802.11 DCF with capture in multipath-faded channels," International Journal of Wireless Information Networks, vol. 9, no. 3, pp. 191--199, July 2002.
• 28: I. Gitman, "On the capacity of slotted ALOHA networks and some desigh problems," IEEE Trans. on Communications, vol. COM-23, no. 3, pp. 305--317, Mar 1975.
• 29: F. A. Tobagi, "Analysis of a two-hop centralized packet radio network---part I: Slotted ALOHA," IEEE Trans. Commun., vol. COM-28, no. 2, pp. 196--207, Feb 1980.
• 30: F. A. Tobagi, "Analysis of a two-hop centralized packet radio network---part II: Carrier sense multiple access," IEEE Trans. Commun., vol. COM-28, no. 2, pp. 208--216, Feb 1980.
• 31: R. R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin, "Throughput analysis in multihop CSMA packet radio networks," IEEE Trans. on Communications, vol. COM-35, no. 3, pp. 267--274, Mar 1987.
• 32: F. A. Tobagi and J. M. Brazio, "Throughput analysis of multihop packet radio network under various channel access schemes," in Proc. INFOCOM'83, San Diego, CA, Apr 1983.
• 33: 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
• 34: Harshal S. Chhaya , Sanjay Gupta, Performance modeling of asynchronous data transfer methods of IEEE 802.11 MAC protocol, Wireless Networks, v.3 n.3, p.217-234, 1997 [doi>10.1023/A:1019109301754]
• 35: Yu Wang , J. J. Garcia-Luna-Aceves, Performance of Collision Avoidance Protocols in Single-Channel Ad Hoc Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.68-77, November 12-15, 2002
• 36: Lin Wu , Pramod K. Varshney, Performance analysis of CSMA and BTMA protocols in multihop networks: (I). Single channel case, Information Sciences—Informatics and Computer Science: An International Journal, v.120 n.1-4, p.159-177, Nov.1.1999 [doi>10.1016/S0020-0255(99)00047-X]
• 37: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. on Information Theory, vol. 46, no. 2, pp. 388--400, Mar 2000.
• 38: 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]
• 39: M. Gastpar and M. Vetterli, "On the capacity of mobile ad hoc networks with delay constraints," in Proc. of IEEEINFOCOM, Jun 2002, vol. 3, pp. 1577--1586.
• 40: Su Yi , Yong Pei , Shivkumar Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778429]
• 41: Christina Peraki , Sergio D. Servetto, On the maximum stable throughput problem in random networks with directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778426]
• 42: S. Toumpis and A. J. Goldsmith, "Capacity regions for wireless ad hoc networks," IEEE Trans. Wireless Communications, vol. 2, no. 4, pp. 736--748, Jul 2003.
• 43: R. Moraes, H. Sadjadpour, and J. J. Garcia-Luna-Aceves, "Making ad-hoc networks scale using mobility and multi-copy forwarding," in Proc. of IEEE Globecom, Nov 2004, To appear.
• 44: A. El Gamal, E. Uysal, and B. Prabhakar, "Energy-efficient transmission over a wireless link via lazy packet scheduling," in Proc. of IEEE INFOCOM, Apr 2001, vol. 1, pp. 386--394.
• 45: A. Fu, E. Modiano, and J. Tsitsiklis, "Transmission scheduling over a fading channel with energy and deadline constraints," in Proc. Conference on Information Sciences and Systems, Mar 2002.
• 46: L. Tong, Q. Zhao, and G. Mergen, "Multipacket reception in random access wireless networks: From signal processing to optimal medium access control," IEEE Commun. Mag., vol. 39, no. 12, pp. 108--112, 2001.
• 47: A. Maharshi, L. Tong, and A. Swami, "Cross-layer designs of multichannel reservation mac under rayleigh fading," IEEE/ACM Trans. Signal Processing, vol. 51, no. 8, pp. 2054--2067, Aug 2003.
• 48: Michele Zorzi, Mobile radio slotted ALOHA with capture, diversity and retransmission control in the presence of shadowing, Wireless Networks, v.4 n.5, p.379-388, Aug. 1998 [doi>10.1023/A:1019129012116]
• 49: J. H. Kim and J. K. Lee, "Capture effects of wireless csma/ca protocols in rayleigh and shadow fading channels," IEEE Trans. Veh. Tech., vol. 48, no. 3, pp. 1277--1286, Mar 1999.
• 50: Gordon L. Stüber, Principles of mobile communication (2nd ed.), Kluwer Academic Publishers, Norwell, MA, 2001
• 51: C. T. Lau and C. Leung, "Capture models for mobile packet radio networks," IEEE Transactions on Communications, vol. 40, no. 5, pp. 917--925, May 1992.
• 52: F. A. Tobagi, "Modeling and performance analysis of multihop packet radio networks," Proc. IEEE, vol. 75, no. 1, pp. 135--155, Jan 1987.
• 53: IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, Nov 1997, P802.11.
• 54: S. J. Oh and K. M. Wasserman, "Dynamic spreading gain control in multiservice CDMA networks," IEEE Journal on Selected Areas in Communications, vol. 17, no. 5, pp. 918--927, 1999.
• 55: D. Tse and S. Hanly, "Linear multiuser receivers: Effective interference, effective bandwidth and user capacity," IEEE Trans. Information Theory, vol. 45, no. 2, pp. 641--657, Mar 1999.
• 56: G. H. Golub and C. F. Van Loan, Matrix Computations, The John Hopkins University Press, third edition, 1996.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Performance, Theory

Keywords:
ad hoc networks, medium access control, modeling, performance evaluation