Analysis of topology-unaware TDMA MAC policies for ad-hoc networks under diverse traffic loads

ABSTRACT

The ever-changing nature of the ad-hoc networks, makes the design of efficient Medium Access Control (MAC) policies challenging. Topology-unaware MAC policies, that allocate slots deterministically or probabilistically have been proposed in the past and evaluated under heavy traffic assumptions. In this paper, the heavy traffic assumption is relaxed and the system throughput achieved by these policies is derived as a function of the traffic load. The presented analysis establishes the conditions and determines the values of the access probability for which the system throughput under the probabilistic policy is not only higher than that under the deterministic policy but it is also close to the maximum achievable, provided that the traffic load and the topology density of the network are known. In case the traffic load and/or the topology density are not known (which is commonly the case in ad-hoc networks), alternative values for the access probability are also derived which, although not the optimal (maximizing the system throughput), they do lead to a system throughput higher than that under the Deterministic Policy. Simulation results for a variety of topologies with different characteristics support the claims and the expectations of the analysis and show the comparative advantage of the Probabilistic Policy over the Deterministic Policy.

REFERENCES

• 1: IEEE 802.11, "Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications," Nov. 1997. Draft Supplement to Standard IEEE 802.11, IEEE, New York, January 1999.
• 2: P. Karn, "MACA- A new channel access method for packet radio," in ARRL/CRRL Amateur Radio 9th Computer Networking Conference, pp. 134--140, 1990.
• 3: 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
• 4: 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
• 5: J. Deng and Z. J. Haas, "Busy Tone Multiple Access (DBTMA): A New Medium Access Control for Packet Radio Networks," in IEEE ICUPC'98, Florence, Italy, October 5-9, 1998.
• 6: R. Nelson, L. Kleinrock, "Spatial TDMA, A collision-free Multihop Channel Access Protocol", IEEE Transactions on Communications, Vol. COM-33, No. 9, September 1985.
• 7: A. Ephremides and T. V. Truong, "Scheduling Broadcasts in Multihop Radio Networks," IEEE Transactions on Communications, 38(4):456--60, April 1990.
• 8: G. Wang and N. Ansari, "Optimal Broadcast Scheduling in Packet Radio Networks Using Mean Field Annealing," IEEE Journal on Selected Areas in Communications, VOL. 15, NO. 2, pp 250--260, February 1997.
• 9: 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
• 10: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 11: 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]
• 12: F. Borgonovo, A. Capone, M. Cesana, L. Fratta, "ADHOC MAC: a new MAC architecture for ad hoc networks providing efficient and reliable point-to-point and broadcast services," to appear in WINET Special Issue on Ad Hoc Networking.
• 13: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 14: Ji-Her Ju , Victor O. K. Li, An optimal topology-transparent scheduling method in multihop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.298-306, June 1998 [doi>10.1109/90.700893]
• 15: Serdar Boztaş, A robust multi-priority topology-independent transmission schedule for packet radio networks, Information Processing Letters, v.55 n.5, p.291-295, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00098-W ]
• 16: Imrich Chlamtac , András Faragó , Hongbiao Zhang, Time-spread multiple-access (TSMA) protocols for multihop mobile radio networks, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.804-812, Dec. 1997 [doi>10.1109/90.650140]
• 17: K. Oikonomou and I. Stavrakakis, "A Probabilistic Topology Unaware TDMA Medium Access Control Policy for Ad-Hoc Environments," Personal Wireless Communications (PWC 2003), 23--25 September, 2003, Venice, Italy.
• 18: K. Oikonomou and I. Stavrakakis, "Throughput Analysis of a Probabilistic Topology-Unaware TDMA MAC Policy for Ad-Hoc Networks," Quality of Future Internet Services (QoFIS), 1-3 October, 2003, Stockholm, Sweden.
• 19: K. Oikonomou and I. Stavrakakis, "Analysis of a Probabilistic Topology-Unaware TDMA MAC Policy for Ad-Hoc Networks," IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Quality-of-Service Delivery in Variable Topology Networks. Accepted for publication. To appear 3rd-4th Quarter 2004.
• 20: Konstantinos Oikonomou and Ioannis Stavrakakis, "Load Analysis of Topology-Unaware TDMA MAC Policies for Ad-Hoc Networks," Quality of Future Internet Services (QoFIS), September 29-1 October, 2004, Barcelona, Spain.
• 21: J. A. Stankovic, T. Abdelzaher, C. Lu, L. Sha, J. Hou, "Real-Time Communication and Coordination in Embedded Sensor Networks," Proceedings of the IEEE, 91(7): 1002--1022, July 2003.
• 22: R. Krishnan and J. P. G. Sterbenz, "An Evaluation of the TSMA Protocol as a Control Channel Mechanism in MMWN," Technical report, BBN Technical Memorandum No. 1279, 2000.
• 23: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

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

General Terms:
Design, Experimentation, Management, Measurement, Performance