ACP Algorithm Evaluation and Efficiency Improvement

Опубликовано в журнале: Научный журнал «Интернаука» № 21(197)
Автор(ы): Sergi Gogokhia
Рубрика журнала: 3. Информационные технологии
DOI статьи: 10.32743/26870142.2021.21.197.283845
Библиографическое описание
Sergi G. ACP Algorithm Evaluation and Efficiency Improvement // Интернаука: электрон. научн. журн. 2021. № 21(197). URL: https://internauka.org/journal/science/internauka/197 (дата обращения: 22.12.2024). DOI:10.32743/26870142.2021.21.197.283845

Авторы

ACP ALGORITHM EVALUATION AND EFFICIENCY IMPROVEMENT

Sergi Gogokhia

PhD Student, Georgian Technical University,

Georgia, Tbilisi

 

ABSTRACT

Mobile network operators having hard times keeping up with the exponential network growth as they deploy more sectors and carriers increasing network capacity. Older ACP algorithms are taking more time to find best and optimized settings due to increased system complexity. Therefore, finding better approach that can improve the existing solutions could dramatically improve the efficiency and reduce the completion time for whole system. ACP/SON modules use couple of algorithms: Brute Force, Sorting, Clustering, etc. This work describes the efficiency improvement by splitting the cluster into smaller bins and ranking them by performance, identifying the value ranges in advance that can degrade the system quality and excluding them from brute force iterations. Reducing the variables decreases the time and space complexity and that improves the system efficiency. Study and detailed description are given below.

 

Keywords: Geolocation, SON, 5G, ACP, O Notation, time complexity, space complexity, tilt, LTE, automation.

 

1. Introduction

Mobile network operators trying to increase ACP/SON systems deployment that helps to reduce OPEX and increase their network spectral efficiency without increasing the human resources. New mobile services require more capacity that in fact increase the number of the cells that gives us possibility to describe cellular coverage planning as a large, multi-variable equation [1]. Large scale mathematical equation having limiting behavior while argument tending towards infinity can be simply formulated with Big O notation [2], which was invented by Paul Bachmann and Edmund Landaus [3] and is also called as asymptotic or Bachmann–Landau notations. It mostly classifies algorithms to calculate how much time or space grow when the inputs are scaled. Using the big O notation, we can also find the upper and lower bounds and calculate the approximation of the function. Big O notation describes the system growth rates which is also referred to function order. There are multiple types of notations that is given in the table below, which are sorted ascended by growth rate:

Table1.

Big O Notation Types

Notation

Name

O(1)

Constant

O(Logn)

logarithmic

O(n)

Linear

O(nLogn)

LogLinear

O(n^2)

Quadratic

O(n^c)

Polinomial

O(c^n)

Exponential

O(n!)

Factorial

 

Chart below shows the comparison of the different notations and their growth rates:

 

Figure 1. Big O Notation Growth Rates

 

2. Problem formulation

In order to show the ACP algorithm is improving the system performance, we need to have a baseline that can be later used for comparison. The easiest and simplest algorithm that was used in ACP systems was the Brute-Force [4] method that requires all parameters to be tried with all possible values. This approach gives us the possibility to choose the best from all options but is not scalable and takes ages for large systems. If the number of cells in the cluster is n and the number of different possible parameters for each cell is t, then the Big O Notation formula which in this case is exponential is following:

If we want to introduce some other parameters, the Big O notation formula will be changed as follows:

As we can see, the brute force requires a large amount of computation resources. For example, regular 4G or 5G cluster with 100 base station having 15-24 cells each with 10 different tilt values will require 6.3x1033 iteration. Brute-Force algorithm is based on the fact that each cell is affected by all cells in the whole area but in reality, there are only few of them that can change the outcome.

Figure 2. Area Splitting - Binning

 

So, if we split the whole area into smaller clusters (bins) as it is shown on the figure above, and apply the brute-force [5] on those isolated bins independently, then the Big O notation can be formulated as follows:

If we consider the fact that number of the cells is big and the whole area is split into with the linear ratio n/c=b, c is also close to the number n, then the Big O can be represented with following formula:

As it is shown in the formula above, we improve [6] the system inefficient exponential Big O notation with the linear O notation.

ACP/SON systems require heuristic method to choose the best from all available options in order to achieve best Signal to Interference and Noise Ratio value and improve overall QoS [7]. We also need to use classical gradient ascent methodology, which allows us to find best configuration for base stations that affects the overall interference for both internal and external bins.

3. Conclusion

Main idea of this paper was assessing existing ACP/SON algorithms and come up with the new approach that can improve system efficiency. The theoretical comparison between existing brute-force and proposed binning algorithm using the big o notations showing significant improvement in both time and space complexity that will improve system computation time, stability and decrease duration and CPU/memory load. We showed the brute-force algorithm-based ACP system limitations for large systems and its inability for scaling [8]. Therefore, new improved algorithm of binning algorithm that splits the area into smaller clusters which also can be analyzed in parallel can improve the performance even more.

Acknowledgements

I express my gratitude to my supervisor Prof. Nikoloz Abzianidze and Prof. Jemal Beridze for giving me the opportunity to work on this scientific paper.

 

References:

  1. Gelfand, Izrail Moiseevich, “Calculus of Variations”, Dover, Feb. 1963
  2. Bachmann, Paul, “Analytic Number Theory”, Leipzig, 1894
  3. Landau, Edmund, “Handbook on the theory of the distribution of the primes” Leipzig, 1909
  4. Devlin, Keith, "What Exactly is Multiplication?" Texas, USA Jan. 2011.
  5. Gogokhia S, Abzianidze, N, “Use of Geolocation in ACP Systems”, Mar. 2020.
  6. Catedra, M. F., Perez-Arriaga, J, “Cell Planning for Wireless Communications”, Artech House, 1999.
  7. Jarvis, Leslie A, “Geolocation of LTE subscriber stations based on the timing advance ranging parameter”, 2010
  8. Farhana Afroz, Ramprasad Subramanian, Roshanak Heidary, Kumbesan Sandrasegaran, Solaiman Ahmed, SINR, RSRP, RSSI and RSRQ measurements in Long Term Evolution networks, Aug. 2015