A heuristics based approach for cellular mobile network planning

ABSTRACT

Designing and planning of the switching, signaling and support network is a fairly complex process in cellular mobile network. In this paper, the problem of assigning cells to switches in cellular mobile network, which is considered a planning problem, is addressed. The cell to switch assignment problem which falls under the category of the Quadratic Assignment Problem (QAP) is a proven NP--hard problem. Further, the problem is modeled to include an additional constraint in the formulation. The additional constraint is of the maximum number of switch ports that are used for a cell's Base Station Transceiver System (BTS) connectivity to the switch. The addition of the constraint on the number of ports on a switch has immense practical significance. This paper presents a non--deterministic heuristic based on Simulated Evolution (SimE) iterative algorithm to provide solutions. The methods adopted in this paper are a completely innovative formulation of the problem and involve application of Evolutionary Computing for this complex problem that may be extended to solutions of similar problems in VLSI design, distributed computing and many other applications.

REFERENCES

• 1: S. Pierre and F. Houeto. Assigning cells to switches in cellular mobile networks using taboo search. Systems, Man and Cybernetics, Part B, IEEE Transactions on, 32(3):351--356, June 2002.
• 2: Arif Merchant , Bhaskar Sengupta, Assignment of cells to switches in PCS networks, IEEE/ACM Transactions on Networking (TON), v.3 n.5, p.521-526, Oct. 1995 [doi>10.1109/90.469954]
• 3: S. Menon and R. Gupta. Assigning cells to switches in cellular networks by incorporating a pricing mechanism into simulated annealing. Systems, Man and Cybernetics, Part B, IEEE Transactions on, 34(1):558--565, February 2004.
• 4: A. Quintero and S. Pierre. A memetic algorithm for assigning cells to switches in cellular mobile networks. Communications Letters, IEEE, 6(11):484--486, November 2002.
• 5: S.J. Shyu, B.M.T. Lin, and T.S. Hsiao. An ant algorithm for cell assignment in pcs networks. IEEE International Conference on Networking, Sensing and Control, 2:1081--1086, 2004.
• 6: I.Demirkol, C. Ersoy, M.U. Caglayan, and H. Delic. Location area planning and cell-to-switch assignment in cellular networks. IEEE Transactions on Wireless Communications, 3(3):880--890, May 2004.
• 7: Y. Wu and S. Pierre. A new hybrid constraint-based approach for 3g network planning. Communications Letters, IEEE, 8(5):277--279, May 2004.
• 8: S. Salcedo-Sanz and Xin Yao. A hybrid hopfield network-genetic algorithm approach for the terminal assignment problem. IEEE Transactions on Systems, Man and Cybernetics, Part B,, 34(6):2343--2353, December 2004.
• 9: S. Nahar, S. Sahni, and E. Shragowitz. Simulated annealing and combinatorial optimization. International Journal of Computer-Aided VLSI Design, 1(1):1--23, 1989.
• 10: R.-M. Kling , P. Banerjee, ESP: a new standard cell placement package using simulated evolution, Proceedings of the 24th ACM/IEEE conference on Design automation, p.60-66, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37897]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

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

General Terms:
Algorithms, Design, Management

Keywords:
cell assignment, heuristics, network design, optimization, wireless networks