Capacity augmentation of 3G cellular networks: a deep learning approach

• US 10,217,060 B2
• Filed: 04/14/2017
• Issued: 02/26/2019
• Est. Priority Date: 06/09/2016
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Yousefi'zadeh, Homayoun, Albanna, Amr
• Primary Examiner(s): Roberts, Brian S
• Application Number:
  US15/488,330
• Publication Number:
  US 20170359754A1
• Time in Patent Office: 683 Days
• Field of Search: None
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 24/10 Scheduling measurement reports ; Arrangements for measurement reports

Abstract

Optimal enhancement of 3G cellular network capacity utilizes two components of learning and optimization. First, a pair of learning approaches are used to model cellular network capacity measured in terms of total number of users carried and predict breakpoints of cellular towers as a function of network traffic loading. Then, an optimization problem is formulated to maximize network capacity subject to constraints of user quality and predicted breakpoints. Among a number of alternatives, a variant of simulated annealing referred to as Block Coordinated Descent Simulated Annealing (BCDSA) is presented to solve the problem. Performance measurements show that BCDSA algorithm offers dramatically improved algorithmic success rate and the best characteristics in utility, runtime, and confidence range measures compared to other solution alternatives. Accordingly, integrated iterative method, program, and system are described aiming at maximizing the capacity of 3G cellular networks by redistributing traffic from congested cellular towers to non-congested cellular towers.

Claims

1. A method of redistributing traffic from congested cellular towers to non-congested cellular towers in a 3G cellular network for the purpose of increasing the capacity of said cellular network wherein said cellular network comprises clusters, clusters comprise sites, and sites comprise cellular towers, and wherein the method comprises:

a. importing per cellular tower information including neighbor handover, traffic demand, traffic carried, average transmit power, and minimum acceptable quality;

b. waiting for the expiration of a refresh timer;

c. importing additionally collected learning measurements since the previous expiration of said refresh timer;

d. applying an MLPDL technique to predict breakpoints of the plurality of both congested and non-congested cellular towers one cellular tower at a time, wherein a breakpoint reflects the maximum load limit of associated cellular tower;

e. applying inputs to the BCDSA algorithm including imported topology information and predicted breakpoints;

f. performing the BCDSA algorithm to generate CPiCH and CIO values of the plurality of both congested and non-congested cellular towers; and

g. going back to step b to wait again for the expiration of said refresh timer.

2. The method of claim 1, wherein the MLPDL technique utilizes a fixed structure fully connected perceptron network for predicting the plurality of the breakage points of each cellular tower one cellular tower at a time.

3. The method of claim 2, wherein the fixed structure comprises an input layer, one or more hidden layers, and an output layer, and wherein each layer comprises a number of processing elements.

4. The method of claim 3, wherein data flow through each processing element comprises generating the output of processing element after applying a nonlinear function to individually weighted inputs of said processing element.

5. The method of claim 3, wherein inputs of a processing element comprise the outputs of all processing elements in the adjacent layer below the layer in which the processing element is located.

6. The method of claim 3, wherein the set of inputs to the processing elements of the input layer comprise collected historical data of the plurality of cellular towers within the cellular network.

7. The method of claim 2, wherein the MLPDL technique provides an iterative learning process to improve the accuracy of the predicted breakpoint of each cellular tower individually calculated as the error between the actual value of the breakpoint and the output of MLPDL.

8. The method of claim 7, wherein the stoppage criterion of iterative learning process comprises reaching a maximum number of iterations or an error below a small threshold of accuracy.

9. The method of claim 7, wherein each learning iteration is comprised of a forward propagation of the input followed by a backward propagation of the output error.

10. The method of claim 9, wherein during forward propagation of each iteration inputs are propagated from the input layer toward the output layer through hidden layers one layer at a time to set all input and output states of all processing elements.

11. The method of claim 9, wherein during back propagation of each iteration the output error is propagated back toward the input layer through hidden layers one layer at a time to adjust the weighting function between each processing element and individual processing elements in the layer below.

12. The method of claim 1, wherein the BCDSA algorithm applies changes to power CPiCH and handover threshold CIO of individual cellular towers as decision variables to reduce congestion.

13. The method of claim 12, wherein reducing the control power CPiCH of a cellular tower results in reducing the coverage boundary of said cellular tower hence shifting users connected to said cellular tower far from its center to neighboring cellular towers, and allocating said reduced power from control channel to traffic channel results in serving more users closer to the center of said cellular tower thereby reducing the overall congestion of said cellular tower.

14. The method of claim 12, wherein increasing the CIO of a cellular tower results in increasing the handover boundary of said cellular tower and shifting users from congested neighboring cellular towers to said cellular tower thereby reducing the congestion of congested neighboring cellular towers.

15. The method of claim 12, wherein the BCDSA algorithm provides a nested iterative process, in which the inner iterative process stops after reaching a maximum number of iterations and the outer iterative process stops after an initial temperature reaches a final temperature as the result of getting sequentially multiplied by a cooling factor with a value smaller than one.

16. The method of claim 15, wherein the BCDSA algorithm partitions the decision variables to two sets comprising a set of CPiCH variables and a set of CIO variables and optimizes one set of decision variables in each iteration of the inner iterative process while keeping the other set fixed at that iteration.

17. The method of claim 16, wherein the BCDSA algorithm changes the capacity of a cellular network in each iteration of the inner iterative process, comprising the steps of:

a. choosing a random cell i;

b. if optimizing CPiCH, subtracting a random value selected from within a range of predefined values from the current CPiCH value of cell i;

c. else if optimizing CIO, adding a random value selected from within a range of predefined values to the current CIO value of cell i;

d. calculating the change in the total capacity of said cellular network as the result of applying CPiCH or CIO change;

e. accepting the new solution, if the change is positive;

f. performing the following test, if the change is negative;

i. generating a random number R in the range [0,1];

ii. accepting the new solution, if the exponential value of the ratio of the change and the current temperature is more than R;

or

iii. rejecting the new solution, otherwise.

18. The method of claim 17, wherein the BCDSA algorithm alternates between the set of CPiCH and the set of CIO decision variables within the inner iterative process based on comparing the previous and current values of the total capacity of the cellular network against freezing thresholds thereby reflecting minor improvements.

19. The method of claim 18, wherein freezing thresholds are set dynamically aiming at maximizing step improvement and minimizing run time.

20. A computer program product stored in a non-transitory computer readable storage medium to redistribute traffic from congested cellular towers to non-congested cellular towers in a 3G cellular network for the purpose of increasing the capacity of said cellular network wherein said cellular network comprises clusters, clusters comprise sites, and sites comprise cellular towers, and wherein the computer program comprises:

a. code for importing per cellular tower information including neighbor handover, traffic demand, traffic carried, average transmit power, and minimum acceptable quality;

b. code waiting for the expiration of a refresh timer;

c. code for importing additionally collected learning measurements since the previous expiration of said refresh timer;

d. code for applying a Machine Learning Regression and an MLPDL technique to predict breakpoints of the plurality of both congested and non-congested cellular towers one cellular tower at a time, wherein a breakpoint reflects the maximum load limit of associated cellular tower;

e. code for applying inputs to the BCDSA algorithm including imported topology information and predicted breakpoints;

f. code for performing the BCDSA algorithm to generate CPiCH and CIO values of the plurality of both congested and non-congested cellular towers; and

g. code for going back to step b to wait again for the expiration of said refresh timer.

21. The computer program of claim 20, wherein the MLPDL technique utilizes a fixed structure fully connected perceptron network for predicting the plurality of the breakage points of each cellular tower one cellular tower at a time.

22. The computer program of claim 21, wherein the fixed structure comprises an input layer, one or more hidden layers, and an output layer, and wherein each layer comprises a number of processing elements.

23. The computer program of claim 22, wherein data flow through each processing element comprises generating the output of processing element after applying a nonlinear function to individually weighted inputs of said processing element.

24. The computer program of claim 22, wherein inputs of a processing element comprise the outputs of all processing elements in the adjacent layer below the layer in which the processing element is located.

25. The computer program of claim 22, wherein the set of inputs to the processing elements of the input layer comprise collected historical data of the plurality of cellular towers within the cellular network.

26. The computer program of claim 21, wherein the MLPDL technique provides an iterative learning process to improve the accuracy of the predicted breakpoint of each cellular tower individually calculated as the error between the actual value of the breakpoint and the output of MLPDL.

27. The computer program of claim 26, wherein the stoppage criterion of iterative learning process comprises reaching a maximum number of iterations or an error below a small threshold of accuracy.

28. The computer program of claim 26, wherein each learning iteration is comprised of a forward propagation of the input followed by a backward propagation of the output error.

29. The computer program of claim 28, wherein during forward propagation of each iteration inputs are propagated from the input layer toward the output layer through hidden layers one layer at a time to set all input and output states of all processing elements.

30. The computer program of claim 28, wherein during back propagation of each iteration the output error is propagated back toward the input layer through hidden layers one layer at a time to adjust the weighting function between each processing element and individual processing elements in the layer below.

31. The computer program of claim 20, wherein the BCDSA algorithm applies changes to power CPiCH and handover threshold CIO of individual cellular towers as decision variables to reduce congestion.

32. The computer program of claim 31, wherein reducing the control power CPiCH of a cellular tower results in reducing the coverage boundary of said cellular tower hence shifting users connected to said cellular tower far from its center to neighboring cellular towers, and allocating said reduced power from control channel to traffic channel results in serving more users closer to the center of said cellular tower thereby reducing the overall congestion of said cellular tower.

33. The computer program of claim 31, wherein increasing the CIO of a cellular tower results in increasing the handover boundary of said cellular tower and shifting users from congested neighboring cellular towers to said cellular tower thereby reducing the congestion of congested neighboring cellular towers.

34. The computer program of claim 31, wherein the BCDSA algorithm provides a nested iterative process, in which the inner iterative process stops after reaching a maximum number of iterations and the outer iterative process stops after an initial temperature reaches a final temperature as the result of getting sequentially multiplied by a cooling factor with a value smaller than one.

35. The computer program of claim 34, wherein the BCDSA algorithm partitions the decision variables to two sets comprising a set of CPiCH variables and a set of CIO variables and optimizes one set of decision variables in each iteration of the inner iterative process while keeping the other set fixed at that iteration.

36. The computer program of claim 35, wherein the BCDSA algorithm changes the capacity of a cellular network in each iteration of the inner iterative process, comprising the steps of:

a. choosing a random cell i;

b. if optimizing CPiCH, subtracting a random value selected from within a range of predefined values from the current CPiCH value of cell i;

c. else if optimizing CIO, adding a random value selected from within a range of predefined values to the current CIO value of cell i;

d. calculating the change in the total capacity of said cellular network as the result of applying CPiCH or CIO change;

e. accepting the new solution, if the change is positive;

f. performing the following test, if the change is negative;

i. generating a random number R in the range [0,1];

ii. accepting the new solution, if the exponential value of the ratio of the change and the current temperature is more than R;

or

iii. rejecting the new solution, otherwise.

37. The computer program of claim 36, wherein the BCDSA algorithm alternates between the set of CPiCH and the set of CIO decision variables within the inner iterative process based on comparing the previous and current values of the total capacity of the cellular network against freezing thresholds thereby reflecting minor improvements.

38. The computer program of claim 37, wherein freezing thresholds are set dynamically aiming at maximizing step improvement and minimizing run time.

39. A system comprising processors and memory coupled to processors, the memory storing instructions readable by a computing device that, when executed by processors, cause processors to perform operations to redistribute traffic from congested cellular towers to non-congested cellular towers in a 3G cellular network for the purpose of increasing the capacity of said cellular network wherein said cellular network comprises clusters, clusters comprise sites, and sites comprise cellular towers, and wherein said operations comprise:

a. importing per cellular tower information including neighbor handover, traffic demand, traffic carried, average transmit power, and minimum acceptable quality;

b. waiting for the expiration of a refresh timer;

c. importing additionally collected learning measurements since the previous expiration of said refresh timer;

d. applying a Machine Learning Regression and an MLPDL technique to predict breakpoints of the plurality of both congested and non-congested cellular towers one cellular tower at a time, wherein a breakpoint reflects the maximum load limit of associated cellular tower;

e. applying inputs to the BCDSA algorithm including imported topology information and predicted breakpoints;

f. performing the BCDSA algorithm to generate CPiCH and CIO values of the plurality of both congested and non-congested cellular towers; and

g. going back to step b to wait again for the expiration of said refresh timer.

40. The system of claim 39, wherein the MLPDL technique utilizes a fixed structure fully connected perceptron network for predicting the plurality of the breakage points of each cellular tower one cellular tower at a time.

41. The system of claim 40, wherein the fixed structure comprises an input layer, one or more hidden layers, and an output layer, and wherein each layer comprises a number of processing elements.

42. The system of claim 41, wherein data flow through each processing element comprises generating the output of processing element after applying a nonlinear function to individually weighted inputs of said processing element.

43. The system of claim 41, wherein inputs of a processing element comprise the outputs of all processing elements in the adjacent layer below the layer in which the processing element is located.

44. The system of claim 41, wherein the set of inputs to the processing elements of the input layer comprise collected historical data of the plurality of cellular towers within the cellular network.

45. The system of claim 40, wherein the MLPDL technique provides an iterative learning process to improve the accuracy of the predicted breakpoint of each cellular tower individually calculated as the error between the actual value of the breakpoint and the output of MLPDL.

46. The system of claim 45, wherein the stoppage criterion of iterative learning process comprises reaching a maximum number of iterations or an error below a small threshold of accuracy.

47. The system of claim 45, wherein each learning iteration is comprised of a forward propagation of the input followed by a backward propagation of the output error.

48. The system of claim 47, wherein during forward propagation of each iteration inputs are propagated from the input layer toward the output layer through hidden layers one layer at a time to set all input and output states of all processing elements.

49. The system of claim 47, wherein during back propagation of each iteration the output error is propagated back toward the input layer through hidden layers one layer at a time to adjust the weighting function between each processing element and individual processing elements in the layer below.

50. The system of claim 39, wherein the BCDSA algorithm applies changes to power CPiCH and handover threshold CIO of individual cellular towers as decision variables to reduce congestion.

51. The system of claim 50, wherein reducing the control power CPiCH of a cellular tower results in reducing the coverage boundary of said cellular tower hence shifting users connected to said cellular tower far from its center to neighboring cellular towers, and allocating said reduced power from control channel to traffic channel results in serving more users closer to the center of said cellular tower thereby reducing the overall congestion of said cellular tower.

52. The system of claim 50, wherein increasing the CIO of a cellular tower results in increasing the handover boundary of said cellular tower and shifting users from congested neighboring cellular towers to said cellular tower thereby reducing the congestion of congested neighboring cellular towers.

53. The system of claim 50, wherein the BCDSA algorithm provides a nested iterative process, in which the inner iterative process stops after reaching a maximum number of iterations and the outer iterative process stops after an initial temperature reaches a final temperature as the result of getting sequentially multiplied by a cooling factor with a value smaller than one.

54. The system of claim 53, wherein the BCDSA algorithm partitions the decision variables to two sets comprising a set of CPiCH variables and a set of CIO variables and optimizes one set of decision variables in each iteration of the inner iterative process while keeping the other set fixed at that iteration.

55. The system of claim 54, wherein the BCDSA algorithm changes the capacity of a cellular network in each iteration of the inner iterative process, comprising the steps of:

a. choosing a random cell i;

b. if optimizing CPiCH, subtracting a random value selected from within a range of predefined values from the current CPiCH value of cell i;

c. else if optimizing CIO, adding a random value selected from within a range of predefined values to the current CIO value of cell i;

d. calculating the change in the total capacity of said cellular network as the result of applying CPiCH or CIO change;

e. accepting the new solution, if the change is positive;

f. performing the following test, if the change is negative;

i. generating a random number R in the range [0,1];

ii. accepting the new solution, if the exponential value of the ratio of the change and the current temperature is more than R;

or

iii. rejecting the new solution, otherwise.

56. The system of claim 55, wherein the BCDSA algorithm alternates between the set of CPiCH and the set of CIO decision variables within the inner iterative process based on comparing the previous and current values of the total capacity of the cellular network against freezing thresholds thereby reflecting minor improvements.

57. The system of claim 56, wherein freezing thresholds are set dynamically aiming at maximizing step improvement and minimizing run time.