Journal of the Korea Society of Computer and Information (한국컴퓨터정보학회논문지)

Korean Society of Computer Information (한국컴퓨터정보학회)
권호 표지
DOI QR코드

DOI QR Code

Minimum Network Connection Cost Algorithm for Partially Survivable Networks Problem of Cellular Telecommunication Systems

  • Lee, Sang-Un (Dept. of Multimedia Engineering, Gangneung-Wonju National University)
  • Received : 2015.06.24
  • Accepted : 2015.10.15
  • Published : 2016.01.30
Download PDF
⟨ Previous Next ⟩

Abstract

This paper suggests heuristic algorithm with O(mn) polynomial time complexity using Excel for partially survivable networks optimization problem of cellular telecommunication systems with m cells and n hubs. This problem only can be get the solution using linear programming or LINGO software package. The proposed algorithm connects the cell to hubs in ring network with minimum cost as the connection diversity of each cell. If the traffic of ring network (T) is T>2K for ring capacity (K), we adjust the maximum cost hub to MTSO that has a ascending order of (D/DC)/${\Delta}^+$ cell with each cell traffic demand (D) and ${\Delta}^+$=(MTSO cost-maximum cost hub) than we get the $T{\leq}2K$. Finally, we adjust MTSO to the removed maximum cost hub for the cell with 2K-$T{\geq}$(D/DC) and $_{max}{\Delta}^-$. While we using like this simple method, the proposed algorithm can be get the same optimal solution for experimental data as linear programing and LINGO software package.

Keywords

References

  1. C. Gueret, X. Prins, and M. Sevaux, "Applications of Optimization with Xpress-MP: 12.2 Dimensioning of a Mobile Phone Network," Dash Optimization Ltd., pp. 176-179, Feb. 2005.
  2. A. Dutta and P. Kubat, "Design of Partially Survivable Networks for Cellular Telecommunications Systems," European Journal of Operational Research, Vol. 118, No. 1, pp. 52-64, Feb. 1999. https://doi.org/10.1016/S0377-2217(98)00281-1
  3. M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NPCompleteness," W. H. Freeman & Co., New York, USA, 1990.
  4. F. A. Potra, "Interior Point Methods: Twenty Years After," Department of Mathematics and Statistics, University of Maryland Baltimore County, Baltimore, USA, NIST, Sep. 2003.
  5. R. Khandekar, "Lagrangian Relaxation Based Algorithms for Convex Programming Problems," Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, Degree of Doctor of Philosophy, Mar. 2004.
  6. P. Kubat and R. Vachani, "Facilities Planning for Cellular Networks," 13th International Teletraffic Congress - Discussion Circles, Copenhagen, Denmark, Elsevier, Amsterdam, pp. 263-266, 1990.
  7. A. Ruiz, J. A. Herrerra, and A. J. Gomez, "Optimization of the Interconnection Links in Cellular Telephone Networks," Fourth INFORMS Telecommunication Conference, Boca Raton, Florida, 1998.
  8. R. H. Cardwell, C. L. Monma, and T. H. Wu, "Computer Aided Design Procedures for Survivable Fiber Optic Telephone Networks," IEEE Journal of Selected Areas in Communications, Vol. 7, No. 8, pp. 1188-1197, Oct. 1989. https://doi.org/10.1109/49.35564
  9. J. Sosonsky and T. H. Wu, "SONET Ring Applications for Survivable Fiber Loop Networks," IEEE Communications Magazine, Vol. 29, No. 6, pp. 51-58, Jun. 1991. https://doi.org/10.1109/35.79402
  10. T. H. Wu and W. I. Way, "A Novel Passive Protected SONET Bi-directional Self-healing Ring Architecture," IEEE Journal of Lightwave Technology, Vol. 10, No. 9, pp. 1314-1322, Sep. 1992. https://doi.org/10.1109/50.156884
  11. T. H. Wu, "Fiber Network Service Survivability," Artech House, Boston, 1992.
  12. P. Asnaghi, R. Cislaghi, and S. Rigobello, "Transmission Network Protection and Reconfiguration by means of Digital Cross-Connect Systems: L. Lada (Ed.), Network Planning in the 1990s," Elsevier, North- Holland, Amsterdam, pp. 335-378, 1989.
  13. A. Shulman, R. Vachani, P. Kubat, and J. Ward, "Multicommodity Flows in Ring Networks," INFORMS Journal on Computing, Vol. 8, No. 3, pp. 235-242, Aug. 1996. https://doi.org/10.1287/ijoc.8.3.235
  14. J. E. Goldman, "Applied Data Communications," 2nd ed., Wiley, New York, 1998.
  15. W. C. Y. Lee, "Mobile Cellular Telecommunications Systems," McGraw-Hill, New York, 1989.