A performance study of a distributed algorithm for dynamic channel allocation

ABSTRACT

Recent demand for mobile telephone service have been growing rapidly while the electro-magnetic spectrum of frequencies allocated for this purpose remain limited. Any solution to the channel assignment problem is subject to this limitation, as well as the interference constraints between adjacent channels in the spectrum. Channel allocation schemes provide a flexible and efficient access to bandwith in wireless and mobile communication systems. In this paper, we present an efficient distributed algorithm for dynamic channel allocation based upon multual exclusion model, where the channels are grouped by the number of cells in a cluster and each group of channels can not be shared concurrently within the cluster. We describe the algorithm, and report its performance several channel systems using different types of call arrival patterns. Our results indicate that significant low denial rate, low message complexity and low acquisition time can be obtained using our algorithm.

REFERENCES

• 1: Peter Alleyne , Carl Tropper, On the parallel simulation of fixed channel allocation algorithms, Mobile Networks and Applications, v.5 n.3, p.209-218, Sept. 2000 [doi>10.1023/A:1019164730055]
• 2: B. R. Badrinath , Arup Acharya , Tomasz Imieliński, Impact of mobility on distributed computations, ACM SIGOPS Operating Systems Review, v.27 n.2, p.15-20, April 1993 [doi>10.1145/155848.155853]
• 3: A. Boukerche, S. Hong, and T. Jacob, "Efficient distributed algorithm for dynam b..nnl 11e. cation", TR-06-00, Dept. of Computer Sciences, UNT 2000.
• 4: G. Cao and M. Singhal "Distributed faulttolerant channel allocation for mobile cellular networks", IEEE INFOCOM'99, pp. 584-591, Mar. 1999.
• 5: Manhoi Choy , Ambuj K. Singh, Efficient fault-tolerant algorithms for distributed resource allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.535-559, May 1995 [doi>10.1145/203095.203101]
• 6: "Efficient distributed algorithm for dynamic channel assignment", Proceedings of 7th IEEE Intl' Symp. on Personal, Indoor and Mobile Radio Communication, 1996.
• 7: Sajal K. Das , Sanjoy K. Sen , Rajeev Jayaram, A novel load balancing scheme for the tele-traffic hot spot problem in cellular networks, Wireless Networks, v.4 n.4, p.325-340, July 1998 [doi>10.1023/A:1019120810299]
• 8: Sajal K. Das , Sanjoy K. Sen , Rajeev Jayaram, A dynamic load balancing strategy for channel assignment using selective borrowing in cellular mobile environment, Wireless Networks, v.3 n.5, p.333-347, Oct. 1997 [doi>10.1023/A:1019181923135]
• 9: G. H. Forman and J. Zahorjan, "The challenges of mobile computing", Tech. Report, Comp. Science and Eng., Univ. of Washington, 1994.
• 10: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 11: William C. Y. Lee, Mobile Cellular Telecommunications Systems, McGraw-Hill, Inc., New York, NY, 1990
• 12: P. Tsigas, N. Garg, M. Papatriantafilou, "Distributed list coloring: How to dynamically allocate", Tech. report, Max-Planck Institute for Computer Science, Saarbrucken, Germany, 1996.
• 13: James A. Payne, Introduction to Simulation: Programming Techniques and Methods Analysis, McGraw-Hill, Inc., New York, NY, 1982
• 14: Ravi Prakash , Niranjan G. Shivaratri , Mukesh Singhal, Distributed dynamic channel allocation for mobile computing, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.47-56, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224970]
• 15: Pradeep K. Sinha, Distributed Operating Systems: Concepts and Design, Wiley-IEEE Press, 1996
• 16: A. Thesen and L. E. Travis, "Simulation for declsloi, mkmg, Wst Publishing Co., 1992.
• 17: Michael Townsend, Discrete Mathematics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
channel/resource allocation, distributed algorithm, mutual exclusion, wireless/mobile communications