Project topics and materials
Get Complete Project Material File(s) Now! »
Low-complexity algorithms for constrained resource allocation problem in C-RAN
C-RAN is a novel mobile network architecture which consists in centralizing the baseband processing in common edge data centers (sometimes referred to as Next Generation-Point of Presence (NG-PoP)) and then sharing the computing resources among different antennas (RRHs). This enables network operators to achieve efficient network utilization and cost savings. However, such gains can only be achieved by finding best strategies in the assignment of the edge data centers to the heterogeneous antennas demands while jointly reducing the resource utilization and the communication latency on the fronthaul network between RRHs and edge data centers. In this contribution, we propose a complete mathematical model based on Integer Linear Programming (ILP) formulation to identify the most appropriate strategies concerning antennas demands assignment to the available edge data centers. The proposed ILP formulation optimizes jointly the latency (transmission delay) on the fronthaul network and the resource consumption (expressed in terms of active edge data centers). Our proposed optimization model provides optimal solutions for small and medium problem instances. Thus, for larger problem instances, we propose three approximation algorithms, based on exact theories and approaches, that scale well, converge reasonably fast and provide good strategies of RRH-BBU assignment :
• Matroid-based approach : we propose a new approximation algorithm based on Matroid theory [25]. This approach models the constrained resource allocation problem as a graphic matroid representation to find good strategies to assign the edge data centers to the antennas demands. In fact, the objective of this approach is to achieve an optimal assignment, when jointly minimizing communication latency and resource consumption.
• b-Matching algorithm : we investigate an algorithm based on b-matching approach [26] that aims to find the minimum weight matching between antennas and edge data centers, with limited capacity of processing (CPU cores), when satisfying the expected communication latency. The proposed b-matching algorithm can reach optimal or near-optimal solutions for large network sizes. • Multiple knapsack-based approach : another approximation algorithm will be proposed using multiple knapsack formulation which is very used in the literature to solve many variants of resource allocation problem (for instance [27], [28], [29] and [30]). Hence, the proposed multiple knapsack formulation will be used to evaluate the performance of the above heuristic algorithms.
Mathematical programming approach for full network coverage optimization in C-RAN
In C-RAN, network operators will increase the density of existing cells by deploying more antennas in order to enhance the network capacity and coverage and enlarge the network spectrum. However, cells densification comes with an increasing of inter-cell interference which causes serious degradations of the provided networks’ QoS. Hence, network operators need new approaches to reduce inter-cell interference and maintain a full network coverage jointly. Our contribution consists in proposing a Branch-and-Cut algorithm to reach a good tradeoff between interference elimination/ reduction and network coverage optimization in the context of C-RAN. In fact, we propose a mathematical description modeling the problem according to the RIPS approach based on simplicial homology [33] (more details can be found later in Chapter 2). Our mathematical model describes the convex hull of the discussed problem and allows to reach optimal solutions even for large problem instances. This description is then enlarged by new valid inequalities and cutting planes to better precise the polytope containing the optimal solution. This contribution based on polyhedral approaches optimization is new and has never been addressed in the literature to cope with the full coverage hole problem in C-RAN. To reach the above objectives, our contribution is described as follows :
• Minimize the number of coverage holes in the cellular network.
• Reduce or eliminate the inter-cell interference by adjusting the coverage radius of antennas without creating coverage holes in the final network.
• Rapid (polynomial time) detection of coverage holes.
Cost-efficient and scalable algorithms for BBU function split placement in C-RAN
As it was already mentioned, the main functionality of C-RAN consists in centralizing the baseband processing from multiple base stations into BBU pools (common data centers). This enables network operators to achieve many benefits in terms of cost savings and capacity increasing. However, the deployment of C-RAN requires very high capacity and low latency on the fronthaul links to connect antennas (RRH) to the centralized data centers (BBUs). Thus, the challenge is to find an optimal split of baseband processing between BBUs and RRHs in order to reach good tradeoff between benefits of centralization and high transport requirements. In this context, various functional splits have been proposed, each of which imposes different throughput and delay requirements. This contribution considers 3GPP RAN split [5] that is outlined as the best option in the 3GPP and it consists in splitting the baseband functions into three components : i) PHY layer ii) MAC and RLC layers and iii) PDCP layer. Accordingly and based on this split configuration, we aim to propose new optimization algorithms to determine optimal locations of baseband functions when considering strict transport requirements on the fronthaul network in terms of latency.
We propose an exact approach based on ILP formulation to optimally deploy BBU functions from multiple cells on the centralized data centers while jointly minimizing the network resource consumption and the end-to-end latency. The exact approach provides the optimal solution for small and medium problem sizes. For larger problem instances, we propose new heuristic algorithms based on the construction of an extended multi-stage graph to rapidly determine the optimal placement of the baseband processing functions when jointly meeting their CPU and latency requirements. These algorithms are benchmarked using different simulation scenarios to evaluate the efficiency and scalability of our algorithms as well as their ability to achieve optimal solutions in acceptable times.
Table of contents :
List of Figures
List of Tables
List of Acronyms
Introduction
1 Context, motivations and contributions
1.1 Context and motivations : Cloud-Radio Access Network (C-RAN)
1.1.1 C-RAN architecture
1.1.2 C-RAN benefits
1.1.3 C-RAN challenges
1.2 Contributions
1.2.1 Low-complexity algorithms for constrained resource allocation problem in C-RAN
1.2.2 Mathematical programming approach for full network coverage optimization in C-RAN
1.2.3 Cost-efficient and scalable algorithms for BBU function split placement in C-RAN
1.3 Publications
2 C-RAN optimization: mathematical background and state-of-theart
2.1 Introduction
2.2 Mathematical background
2.2.1 Combinatorial optimization : techniques and algorithms
2.2.2 Simplicial homology background
2.3 C-RAN optimization : state-of-the-art
2.3.1 Constrained resource allocation problem
2.3.2 Network coverage optimization problem
2.3.3 BBU functions split and placement problem
2.4 Conclusion
3 Constrained resource allocation in C-RAN
3.1 Introduction
3.2 Problem statement
3.2.1 System model
3.2.2 Problem complexity
3.3 Proposed algorithms
3.3.1 Integer linear programming formulation
3.3.2 Matroid-based approach
3.3.3 b-Matching formulation
3.3.4 Multiple knapsack-based approach
3.4 Performance evaluation
3.4.1 Simulation settings and parameters
3.4.2 Performance metrics
3.4.3 Performance analysis
3.5 Conclusion
4 Full network coverage optimization in C-RAN
4.1 Introduction
4.2 Problem statement
4.2.1 System model and problem description
4.2.2 Problem complexity
4.3 Branch-and-Cut formulation
4.3.1 Convex hull characterization
4.3.2 New valid inequalities
4.3.3 Complete mathematical formulation
4.4 Performance evaluation
4.4.1 Simulation parameters and settings
4.4.2 Performance metrics
4.4.3 Simulation results and performance analysis
4.5 Conclusion
5 BBU function split placement in C-RAN
5.1 Introduction
5.2 Problem statement
5.2.1 BBU function split modeling
5.2.2 Network topology description
5.2.3 System model
5.2.4 Problem complexity
5.3 Exact mathematical approach
5.4 Approximation approaches : multi-stage graph algorithms
5.5 Performance evaluation
5.5.1 Simulation parameters and settings
5.5.2 Performance metrics
5.5.3 Simulation results and performance analysis
5.6 Conclusion
6 Conclusions and perspectives
Bibliography
