On the end-to-end call acceptance and the possibility of deterministic QoS guarantees in ad hoc wireless networks

ABSTRACT

The issue of providing Quality of Service (QoS) guarantees in an Ad~hoc wireless network is a very challenging problem. In this paper, we make the following contributions: (i) analytically derive bounds for the end-to-end call acceptance rate using existing queueing theory methods, (ii) study the impact of the routing scheme on the end-to-end call acceptance rate, and (iii) propose a differentiated services scheme for deterministically providing QoS guarantees.Unlike existing studies which analyze the transport capacity, we focus on the end-to-end call acceptance. The framework that we assume is that of a TDMA-based Ad~hoc wireless network. The routing scheme employed influences the end-to-end call acceptance of the network. The metrics that we consider are the call acceptance probability and the system saturation probability (i.e., the probability that the network is in a state in which every new call is rejected). We derive general bounds on the call acceptance and the system saturation for the case of differentiated-classes of users in the network. These bounds indicate the number of calls of the highest priority class that can be admitted into the network.Simulation studies were carried out to study the effect of load, hopcount, and the influence of the routing protocol on the call acceptance. The increase in the call acceptance rate with the introduction of load-balancing highlights the importance of load-balancing in enhancing the system performance. From these studies, we arrive at the following results: (i) load-balancing leads to significant improvement in the end-to-end call acceptance rate, and is an important factor in attaining the maximum end-to-end call acceptance rate in a given network and (ii) it is indeed possible to provide deterministic QoS guarantees for a designated set of nodes which are characterized by "deterministic guarantee limit".

REFERENCES

• 1: P. Gupta and P. R. Kumar, "The Capacity of Wireless Networks", IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, March 2000.
• 2: P. Gupta and P. R. Kumar, "Towards an Information Theory of Large Networks: An Achievable Rate Region", IEEE Transactions on Information Theory, vol 49, no. 8, pp. 1877--1894, August 2003.
• 3: 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]
• 4: Ula? C. Kozat , Leandros Tassiulas, Throughput capacity of random ad hoc networks with infrastructure support, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938992]
• 5: T. Bheemarjuna Reddy, I. Karthigeyan, B. S. Manoj, and C. Siva Ram Murthy, "Quality of Service Provisioning in Ad hoc Wireless Networks: A Survey of Issues and Solutions", to appear in Ad Hoc Networks Journal.
• 6: P. Sinha, R. Sivakumar, and V. Bharghavan, "CEDAR: A Core-Extraction Distributed Ad~hoc Routing Algorithm", IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1454--1465, August 1999.
• 7: W. Liao, Y. Tseng, and K. Shih, "A TDMA-based Bandwidth Reservation Protocol for QoS Routing in a Wireless Mobile Ad hoc Network", in proceedings of IEEE ICC 2002, vol. 5, pp. 3186--3190, May 2002.
• 8: G. Barua and I. Chakraborty, "Adaptive Routing for Ad~hoc Wireless Networks Providing QoS Guarantees", in proceedings of IEEE ICPWC 2002, pp. 196--200, December 2002.
• 9: John G. Kemeny and J. L. Snell, Finite Markov Chains, Van Nostrand, New York, 1960.
• 10: Peter Buchholz , Gianfranco Ciardo , Susanna Donatelli , Peter Kemper, Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models, INFORMS Journal on Computing, v.12 n.3, p.203-222, July 2000 [doi>10.1287/ijoc.12.3.203.12634]
• 11: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 12: G. Bhaya, B. S. Manoj, and C. Siva Ram Murthy, "Ring-Based Routing Schemes for Load Distribution and Throughput Improvement in Multi-hop Cellular, Ad hoc, and Mesh Networks", in proceedings of HiPC 2003, LNCS 2913, pp. 152--161, December 2003.
• 13: Qingming Ma , Peter Steenkiste , Hui Zhang, Routing high-bandwidth traffic in max-min fair share networks, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.206-217, August 28-30, 1996, Palo Alto, California, United States

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: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Performance attributes

General Terms:
Algorithms, Performance, Theory

Keywords:
Markov process, QoS guarantees, QoS routing, TDMA, ad hoc wireless networks, call acceptance rate, load-balancing