Joint optimal access point selection and channel assignment in wireless networks

ABSTRACT

In wireless cellular networks or in other networks with single-hop communication, the fundamental access control problem pertains to access point (AP) selection and channel allocation for each user. For users in the coverage area of one AP, this involves only channel allocation. However, users that belong in the intersection of coverage areas of more than one AP can select the appropriate AP to establish connection and implicitly affect the channel assignment procedure. We address the joint problem of AP selection and channel assignment with the objective to satisfy a given user load vector with the minimum number of channels. Our major finding is that the joint problem reduces to plain channel allocation in a cellular network that emerges from the original one after executing an iterative and provably convergent clique load balancing algorithm. For linear cellular networks, our approach leads to minimum number of required channels to serve a given load vector. For 2-D cellular networks, the same approach leads to a heuristic algorithm with a suboptimal solution due to the fact that clique loads cannot be balanced. Numerical results demonstrate the performance benefits of our approach in terms of blocking probability in a dynamic scenario with time-varying number of connection requests. The presented approach constitutes the basis for addressing more composite resource allocation problems in different context.

REFERENCES

• 1: [1] I. Koutsopoulos and L. Tassiulas, "Joint base station and channel allocation in mobile cellular networks," in Proc. IEEE Int. Conf. Communications , 2000, pp. 1558-1562.
• 2: [2] I. Katzela and M. Naghshineh, "Channel assignment schemes for cellular mobile telecommunication systems: A comprehensive survey," IEEE Pers. Commun., vol. 3, no. 3, pp. 10-31, Jun. 1996.
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: [4] K. N. Sivarajan, R. J. McEliece, and J. W. Ketchum, "Channel assignment in cellular radio," in Proc. IEEE Vehicular Technology Conf., 1989.
• 5: [5] C. W. Sung and W. S. Wong, "Sequential packing algorithm for channel assignment under cochannel and adjacent-channel interference constraint," IEEE Trans. Veh. Technol., vol. 46, no. 3, pp. 676-686, Aug. 1997.
• 6: [6] R. Mathar and J. Mattfeldt, "Channel assignment in cellular radio networks," IEEE Trans. Veh. Technol., vol. 42, no. 4, pp. 647-655, Nov. 1993.
• 7: [7] M. Frodigh, "Bounds on the performance of DCA algorithms in highway microcellular systems," IEEE Trans. Veh. Technol., vol. 43, no. 3, pp. 420-427, Aug. 1994.
• 8: [8] D. Everitt and D. Manfield, "Performance analysis of cellular mobile communication systems with dynamic channel assignment," IEEE J. Sel. Areas Commun., vol. 7, pp. 1172-1180, Oct. 1989.
• 9: [9] P. A. Raymond, "Performance analysis of cellular networks," IEEE Trans. Commun., vol. 39, no. 12, pp. 1787-1793, Dec. 1991.
• 10: [10] B. Hajek, "Performance of global load balancing by local adjustment," IEEE Trans. Inf. Theory, vol. 36, no. 6, pp. 1398-1414, Nov. 1990.
• 11: M. Alanyali , B. Hajek, On simple algorithms for dynamic load balancing, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 1)-Volume, p.230, April 02-06, 1995
• 12: [12] R. Yates and C. Y. Huang, "Integrated power control and base station assignment," IEEE Trans. Veh. Tech., vol. 44, no. 3, pp. 638-644, Aug. 1995.
• 13: Symeon Papavassiliou , Leandros Tassiulas, Joint optimal channel base station and power assignment for wireless access, IEEE/ACM Transactions on Networking (TON), v.4 n.6, p.857-872, Dec. 1996 [doi>10.1109/90.556343]
• 14: [14] S. Papavassiliou and L. Tassiulas, "Improving the capacity in wireless networks through integrated channel base station and power assignment," IEEE Trans. Veh. Technol., vol. 47, no. 2, pp. 417-427, May 1998.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.3 Network Operations
          Subjects: Network management
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Management, Performance

Keywords:
access point (AP) assignment, channel allocation, load balancing, wireless access