\documentclass{bmcart}
%\documentclass[twocolumn]{bmcart}
%\smartqed  % flush right qed marks, e.g. at end of proof
%
\usepackage[utf8]{inputenc}
%\usepackage{graphicx} 
%\usepackage{hyperref} 
\usepackage{multirow} 
\usepackage{tabularx} 
\usepackage{color} 
\usepackage{amsmath} 
\usepackage{amssymb} 
\usepackage{amsfonts}
\usepackage{amstext} 
\usepackage{amsxtra} 
\usepackage{wasysym} 
\usepackage{isomath} 
\usepackage{mathtools} 
%\usepackage{txfonts} 
\usepackage{upgreek} 
\usepackage{enumerate} 
\usepackage{tensor} 
\usepackage{pifont} 
\usepackage{eurosym}
%\usepackage{subfig}
\usepackage{verbatim}

\def\includegraphic{}
\def\includegraphics{}

%%% Put your definitions there:
\startlocaldefs
\endlocaldefs

\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}

\newcolumntype{R}{>{\raggedleft\arraybackslash}X}


%%% Begin ...
\begin{document}

\begin{frontmatter}

\begin{fmbox}
\dochead{Research}

\title{Cost-effective joint Optimisation of BBU Placement and Fronthaul Deployment in Brown-field Scenarios}

%\titlerunning{Short form of title}        % if too long for running head

\author[
   addressref={aff1},                   % id's of addresses, e.g. {aff1,aff2}
   corref={aff1},                       % id of corresponding address, if any                      % id's of article notes, if any
   email={andrea.marotta@univaq.it}   % email address
]{\inits{A}\fnm{Andrea} \snm{Marotta}}
\author[
   addressref={aff2},
   email={luis.m.correia@tecnico.ulisboa.pt}
]{\inits{LM}\fnm{Luis M.} \snm{Correia}}

\address[id=aff1]{%                           % unique id
  \orgname{DISIM, University of L'Aquila}, % university, etc
  \street{Via Vetoio, 1},                     %
  \postcode{67100}                                % post or zip code
  \city{L'Aquila},                              % city
  \cny{Italy}                                    % country
}
\address[id=aff2]{%
  \orgname{IST/INESC-ID, University of Lisbon},
  \street{Rua Alves Redol, 9, 1E},
  \postcode{1000-029}
  \city{Lisbon},
  \cny{Portugal}
}

\end{fmbox}% comment this for two column layout

\begin{abstractbox}

\begin{abstract}
In this work one proposes a model to evaluate the optimal deployment of Centralised Radio Access Network (C-RAN) architecture elements, i.e. Base Band processing Units (BBUs) and fronthaul links, in a brownfield scenario in which traditional base stations are already deployed and a physical network is present. The proposed optimisation framework jointly optimises BBU placement and access network infrastructures deployment. It clusterises Remote Radio Heads in the scenario through a Multicommodity Flow approach and solves the minimum cost fronthaul network deployment through a Rooted Delay-Constrained Minimum Spanning Tree approach. Optical fibre and microwave links are considered as fronthaul infrastructures. The proposed optimisation framework is validated through a comparison with a theoretical output for a canonical scenario then it is applied to a real scenario. A cost analysis for different scenario configurations is illustrated, and tradeoff and guidelines for a cost optimal deployment of C-RAN are provided. The analysis of results for the real scenario of the city of Lisbon and its surrounding areas shows that the delay budget in the fronthaul network highly impacts on capital expenditures as well as on operational ones. It is shown that a larger delay budget enables an annual cost reduction up to 72\% in urban areas and 54\% in rural ones.
\end{abstract}

\begin{keyword}
\kwd{C-RAN}
\kwd{Fronthaul}
\kwd{Optimisation}
\kwd{Deployment}
\end{keyword}

\end{abstractbox}

\end{frontmatter}
%\end{fmbox}% uncomment this for twcolumn layout
\section{Introduction}

Network evolution towards 5G involves several solutions and techniques proposed with the general intent of improving users' quality of experience in a variety of services. This global objective is mapped onto very demanding requirements in terms of expected throughout, latency, scalability and automation. 

In order to satisfy traffic growth, mobile operators must significantly increase their network capacity to provide  broadband to the users. However, in an intensifying competitive marketplace, high saturation levels, rapid technological changes and declining voice revenue, operators are challenged with the deployment of traditional Base Stations (BSs) as cost is high and return is not high enough. The Average Revenue Per User is already affecting  operators' profitability, and new architectures are being proposed in order to allow them to remain profitable and competitive. 

The C-RAN architecture splits traditional BSs into a radio unit, called Remote Radio Head (RRH), and a Base Band processing Unit (BBU). This represents an efficient solution in order to overcome the aforementioned problems. As a consequence of splitting a traditional BS into two functional units, C-RAN introduces a new connectivity segment called ''fronthaul''. In \cite{NGMN}, a more in-depth analysis of the C-RAN architecture can be found. The flexibility related to the software implementation of mobile functionalities enables a dynamical management of several network aspects, such as load balancing among BBUs \cite{CRANload}, multicell association \cite{CRANmulti} and efficient Coordinated Multi Point (CoMP) transmission \cite{CRANcomp}. 

Recently, new 5G fronthaul interfaces and requirements have been put forward in terms of maximum supported latency and bandwidth for the fronthaul segment \cite{3GPP}. This work focuses on a C-RAN functional split that corresponds to Option 8 (PHY-RF split) where the RF functionality is in the distributed unit (i.e. RRH) and upper layers are in the central one (i.e. BBU). Moreover, several activities are currently ongoing in the investigation of possible functional split implementations and fronthaul interfaces \cite{NGFI,ecpri}.

The deployment of the physical infrastructures supporting C-RAN architectures is crucial from the operators viewpoint, since it affects CAPital EXpentiture (CAPEX) and OPerating EXpenditure (OPEX) and impacts on economical sustainability. Several strategies for the placement of RRHs \cite{ToniniICC} and BBUs \cite{Musumeciwdm} have been proposed. Moreover,  models for the estimation of the economical impact of deployment of C-RANs for different scenarios configuration \cite{LisiICC} and deployment strategies \cite{DeandraCost,luis} have been investigated.

Recently, relevant aspects related to C-RAN deployment have been investigated. In \cite{resilient} survivability strategies for link and node failures in C-RAN are studied with different optimisation objectives. A novel technique to compute the optimal deployment of BBUs based on machine learning is proposed in \cite{ML} with the objective to minimise bandwidth and computing resources consumption. Finally, in \cite{mmw} millimeter wave wireless fronthaul links are used in order to support fronthaul requirements with different functional splits. However, the joint utilisation of optical fibre and wireless links for the mobile fronthaul in brown-field scenarios has not yet been extensively  studied.

In this work, one proposes a model to obtain the optimal deployment of BBUs and RRHs, in a brownfield scenario in which just traditional BSs are already deployed and a physical network is present. In order to minimise CAPEX, the proposed model considers already deployed optical fibre and microwave links as possible fronthaul infrastructures. The novelty of the proposed optimisation framework is that it jointly optimises BBU placement as well as access deployment. To achieve an efficient use of available physical links, cascading links between RRHs are taken into consideration, resulting in a tree based architecture between BBU and served RRHs that minimises deployment cost. The proposed model is designed to address the C-RAN deployment planning, hence, not considering traffic or delay variations (which are handled at the network management level) and coverage and interference probabilities (since one takes base stations locations as an input, given that it is a brown-field scenario assumption). It is intended to be a tool for the analysis of the influence of different parameters (e.g. delay constraint, size of the area to serve, and deployment strategy) on the deployment configurations. It enables relative comparisons over many scenarios and deployment configurations, which can be suitable from the operators' viewpoint in network deployment planning.

In Section~\ref{sec:methods}, a formal problem definition is provided and the system model is presented. An Integer Linear Programming optimisation problem for minimum cost of deployment is formulated. In Section~\ref{sec:resu}, an analysis of the results for a canonical scenario is conducted in order to validate the proposed model. Furthermore, three reference real scenarios, namely urban, suburban and rural are illustrated, showing the impact of different factors on C-RAN deployment. Conclusions are presented in Section~\ref{sec:conclusion}.

\section{Methods}\label{sec:methods}
\subsection{Model Overview}\label{sec:model}
\subsubsection{Problem description}
The problem addressed in this work is the optimal deployment of BBU pools and fronthaul network in urban, suburuban and rural scenarios, in which traditional BSs and backhaul infrastructures are already present. One assumes that all BSs sites are converted to RRHs ones. The introduction of the fronthaul implies that network time constraints must incorporate the time for the transportation of data through the fronthaul segment. The delay constraint for transportation represents a key aspect for deployment optimisation, because it has a direct impact on the maximum length of the links between RRHs and BBUs. 

Designing a solution for an urban scenario raises an important requirement: not all locations that could be considered optimal for BBU pool positions are able to host its infrastructure, because operators cannot locate equipment in arbitrary locations. The adopted approach to avoid this problem is to consider a subset of the RRHs locations as the set of feasible positions for the BBUs.

Based on the former considerations, the problem that one addresses is to find which BSs' positions can be elected as possible BBU pools ones, given a constraint of delay between BBU and RRH, and minimising the number of BBU pools to reduce costs. This problem can be interpreted as the well-known Set Covering Problem, which is known to be NP-complete \cite{OptimalPackNP}. This problem has been studied extensively due to its wide applicability in facility location and in wireless networks.
 
One has to find an optimal deployment of links considering the different technologies available in the service area and considering delay constraint and links capacity. In order to do this, one provides an Integer Linear Programming (ILP) \cite{Handbookglobalopt} that minimises the total network cost in terms of kilometres of optical fibre and of number of microwaves links to be deployed, takes into consideration the reuse of existent infrastructures, and considers cascading links among RRHs for the connection towards the serving BBU. A graphical view is given in Fig.~\ref{fig:Fig1}.

One defines the group of RRHs served by a single BBU as a \emph{cluster}, hence, one has to find an optimal clusterisation of RRHs to be connected to the serving BBUs, and to find, on a per-cluster base, a deployment tree connecting a BBU with every served RRH with the minimum deployment cost and respecting the maximum delay constraint. The clusterisation objective can be obtained by modelling the problem as a Multi Commodity Flow Problem (MCFP) \cite{Multicomm}. By considering the cluster of RRHs served by a BBU as a graph, and by using a Rooted Delay-Constrained Minimum Spanning Tree (RDCMST) \cite{RDCMST} approach for each cluster adopting the BBU as root, ensures that each RRH will be connected to a BBU using a series of physical links that introduce a delay lower than the maximum one.

It is important to notice that the adoption of a spanning tree approach allows to use a single link for several connections among the BBU and its served RRHs, as illustrated in  Fig.~\ref{fig:Fig1}. One assumes that each physical link serves at most one BBU cluster. Fig.~\ref{fig:Fig1} shows how the physical links that transport several BBU-RRH connections have higher capacity requirements.

From a high-level perspective, one can summarise the inputs and outputs for the model. The proposed optimisation model takes as input a set of possible positions for the BBUs. Since the objective is the minimisation of costs and reutilisation of existing infrastructures, another input are the links already present in the scenario to be reused, in order to avoid newly deployed links with a high cost for the operator. The split of the BS calls for high capacity requirements on the fronthaul segment, which are related to the characteristics of the RRH site. The optimisation problem takes as input the data rate required by each RRH, in order to enable possible supporting links for the connection to the BBU. The delay constraint represents a key decision aspect in the design of the network. From the operator side, the adoption of a lower delay budget implies intuitively higher costs, but, on the other hand, it makes the deployment ready for the future evolution of technology and network requirements. 

As output of the problem, the optimisation model yields the location of the infrastructures hosting the BBU pools, together with the set of RRHs served by each BBU site. For the connection between the RRHs and the BBUs an optimal set of links is given, including the already existing links and newly deployed ones. Moreover, an estimation of the deployment cost of the C-RAN architecture in terms of CAPEX and OPEX is provided as well.

\subsubsection{Problem Statement}\label{sec:probstat}
\paragraph{Input parameters}

In order to model the maximum delay constraint for the communication between a BBU and an RRH, one defines $\tau_{max}$ as the one-way maximum delay of the fronthaul segment.
One assumes that each BS site will be converted to an RRH one, defining:

\begin{itemize}
\item $N_{RRH}$: number of RRHs sites;
\item $N_{pBBU}$: number of possible BBU sites.
\end{itemize}

Since one looks for BBU positions within the set of RRHs sites, but not all RRH sites will be taken as feasible locations for BBUs, one has 
\begin{equation}
N_{pBBU}\leq N_{RRH}
\end{equation}

Starting from a real scenario where a backhaul network is already deployed,  one has to consider the presence of fibre and microwave links already serving the sites.  In order to model link availability, one introduces several matrices that define if fibre/microwave links are already present in the scenario and which kind of links are deployable among RRHs sites. 

One introduces the sparse and symmetric matrix $\mathbf{P}_{[N_{RRH}\times N_{RRH}]}$ that models the general link presence between couples of RRHs sites without caring about the physical medium used, and with each element being given by:
\begin{equation}
P_{ij}=
\begin{cases} 1, & \text{if a link is deployed from RRHs } i \text{ to } j\\
0, & \text{otherwise}
\end{cases} 
\end{equation}

One defines the sparse and symmetric matrices $\mathbf{P}_{\mathbf{f}/\mathbf{m}[N_{RRH}\times N_{RRH}]}$ that model fibre/microwave link presence between couples of RRHs sites. One is using $\mathbf{P}_{\mathbf{f}/\mathbf{m}}$ as a notation to denote two possible matrices $\mathbf{P}_{\mathbf{f}}$ and $\mathbf{P}_{\mathbf{m}}$, and this notation is used throughout the paper, with each element as:
\begin{equation}
P_{f/m,ij}=
\begin{cases} 
1, & \text{if a fibre/microwave link is deployed from} \\ & \text{RRHs } i \text{ to } j \\
0, & \text{otherwise}
\end{cases} 
\end{equation}

One imposes for the introduced matrices 
\begin{equation}
P_{ij}=1 \Rightarrow (P_{f,ij}=1) {\veebar} (P_{m,ij}=1) \label{eq:P6}
\end{equation}
since just one technology (fibre or microwave) is used for the link between RRH $i$ and RRH $j$. 

An optimal C-RAN deployment can require the deployment of new fibre or microwave links not already present in the area. However, given two RRHs sites, it may not always be possible to connect them, given operational restrictions, such as impossibility to deploy fibres or the low capacity of microwave links. The deployment of new links is therefore subject to deployability conditions that one models using deployability matrices. The sparse and symmetric matrices $\mathbf{D}_{\mathbf{f}/\mathbf{m} [N_{RRH}\times N_{RRH}]}$ model fibre/microwave links deployability between couples of RRHs sites, with each element as:
\begin{equation}
D_{f/m,ij}=
\begin{cases} 1, & \text{if a fibre}/\text{microwave link is deployable from} \\
& \text{RRHs } i \text{ to }j\\
0, & \text{otherwise}
\end{cases} 
\end{equation}

It is important to notice that: 
\begin{equation}
P_{f/m,ij}=1\Rightarrow D_{f/m,ij}=0
\end{equation}
which means that $\mathbf{D}_{\mathbf{f/m}}$ contains the links that are not already deployed but still deployable.


One introduces the sparse and symmetric matrix $\mathbf{D}_{[N_{RRH}\times N_{RRH}]}$ that models general link deployability between couples of RRHs sites, with each element as:
\begin{equation}
D_{ij}=
\begin{cases} 
1,\ & \text{if a link is deployable from RRHs } i\text{ to }j\\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}
imposing
\begin{equation}
D_{ij}= 1 \Rightarrow (D_{f,ij}=1) {\veebar} (D_{m_ij}=1) \label{eq:P7}
\end{equation}
to obtain the links that are deployable. 

As illustrated in Fig.~\ref{fig:Fig1}, one considers pedestrian path distance for fibre links and straight line distance for microwave ones. The matrices $\mathbf{d}_{\mathbf{f/m}[N_{RRH}\times N_{RRH}]\left [\text{km}\right ]}$ express distances between couples of RRHs sites connected through fibre/microwave: 

\begin{itemize}
\item $d_{f,ij\left [\text{km}\right ]}$: pedestrian path distance from RRHs $i$ to $j$
\item $d_{m,ij\left [\text{km}\right ]}$: straight-line distance from RRHs $i$ to $j$
\end{itemize}

\sloppy In order to check if the delay of the connection between BBU and RRH is lower than $\tau _{max}$, one needs to take into consideration the delay introduced by the links between the considered sites. Two input matrices fibre/microwave links delay $\mathbf{T_{f/m}}_{[N_{RRH}\times N_{RRH}]\left [\upmu \mathrm{s}\right ]}$ are introduced, where:
\begin{itemize}
\item $T _{f/m,ij\left [\upmu \mathrm{s}\right ]}$: delay introduced by the link from RRH $i$ to RRH $j$ using fibre/microwave.
\end{itemize}

Link capacity is given by matrices $\mathbf{C}_{\mathbf{f/m}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$, expressing the bandwidth available for each fibre/microwave link, where:
\begin{itemize}
\item $C_{f/m,ij\left [\text{Mbps}\right ]}$: capacity of the link from RRHs $i$ to $j$ using fibre/microwave.
\end{itemize}

The main aspect that impacts on the design of C-RAN is CAPEX. The choice between fibre and microwave links is based on the cost of deployment, since different technologies have different costs for the realisation of the links, and impact significantly on the initial investment of the operator, i.e. CAPEX. Matrices $\mathbf{K}_{\mathbf{f/m}[N_{RRH}\times N_{RRH}][\text{\euro}]}$ represent the cost of deployment of fibre/microwave links, where:
\begin{itemize}
\item $K_{f/m,ij[\text{\euro}]}$: cost of the link deployment from RRHs $i$ to $j$ using fibre/microwave.
\end{itemize}

The link deployment cost is related to the presence of the link in the scenario. Trivially, to deploy a totally new link for the operator will imply a cost that is significantly higher than to use an already existing one. 
One assumes that the use of an existing link does not require an increase of CAPEX, therefore
\begin{equation}
P_{f/m,ij}=1\Rightarrow K_{f/m,ij}=0
\end{equation}

One also has to take into consideration BBU deployment related costs, which are modelled through vector $\mathbf{K}_{\mathbf{BBU}[N_{pBBU}\times 1] [\text{\euro}]}$, where:  
\begin{itemize}
\item $K_{BBU,i [\text{\euro}]}$ is the deployment cost of a BBU in site $i$. 
\end{itemize}

In this work, one considers the cost of each RRH as constant and defines $K_{RRH\textit{\euro}}$ as the cost of an RRH.

\paragraph{Output variables}
Among all possible BBU positions, the proposed model leads to the subset of nodes that is able to serve all RRHs minimising deployment cost and balancing load among BBUs, consequently 
\begin{equation}
N_{BBU} \leq N_{pBBU}
\end{equation}
where
\begin{itemize}
\item $N_{BBU}$: number of elected BBU sites for the optimal deployment.
\end{itemize}

One of the outputs is the decision if a specific RRH site is elected as a BBU one, represented by vector $\mathbf{B}_{[N_{pBBU}\times 1]}$, where:
\begin{equation}
B_{i}=
\begin{cases}
1,\ & \text{if a possible BBU site }i \text{ is chosen } \\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}

Another output is the assignment of RRHs to BBUs, defining the clustering of RRHs, with matrix $\mathbf{S}_{[N_{pBBU}\times N_{RRH}]}$:
\begin{equation}
S_{ij}=\begin{cases} 
1,\ & \text{if RRH }j\text{ is served by BBU } i\\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}

An RRH will be served by one and only one BBU, leading to: 
\begin{equation}
\sum _{i=1}^{N_{pBBU}}S_{ij}=1 \; \forall j  \in \{1,...,N_{RRH}\} \label{eq:N1}
\end{equation}

It follows from previous considerations that whenever an RRH is connected to another RRH, the latter becomes a BBU one,
\begin{equation}
S_{ij}\leq B_{i} \; \forall i \in \{1,...,N_{pBBU}\} ,j \in \{1,...,N_{RRH}\} \label{eq:N2}
\end{equation}

The output variables that represent the usage of fibre/microwave links for optimal deployment are sparse and symmetric matrices $\mathbf{U}_{\mathbf{f}/\mathbf{m}[N_{RRH}\times N_{RRH}]}$ where:
\begin{equation}
U_{f/m,ij}=
\begin{cases} 
1, & \text{if fibre/microwave is chosen as medium} \\
 & \text{for the link between RRHs site } i \text{ and }j \\
0, & \text{otherwise}
\end{cases} 
\end{equation}
and
\begin{equation}
U_{f/m,ij}=1\Rightarrow U_{m/f,ij}=0 \label{eq:P1}
\end{equation}
  in order to avoid that both fibre and microwave are chosen for the link between RRHs $i$ and $j$.

Moreover, one has to impose that 
\begin{equation}
\left (D_{f/m,ij}\veebar P_{f/m,ij}\right )=0\Rightarrow U_{f/m,ij}=0 \label{eq:P3}
\end{equation}
 in order to exclude from the final deployment the links that are not present and not deployable.


One can finally introduce the link usage sparse matrix $\mathbf{U}_{[N_{RRH}\times N_{RRH}]}$, where:
\begin{equation}
U_{ij}=
\begin{cases} 
1,\ & \text{if the link between sites }i\text{ and }j\text{ is used for}\\
& \text{the optimal deployment}\\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}
with 
\begin{equation}
U_{ij}=1 \Rightarrow (U_{f,ij}=1)\veebar (U_{m,ij}=1 ) \label{eq:P5}
\end{equation}
 in order to include into the final deployment both link types.
 
\paragraph{Internal variables}

\sloppy In order to formulate the MCFP, one introduces a 4-dimensional sparse matrix $\mathbf{U}_{\mathbf{c}[N_{RRH}\times N_{RRH}\times N_{pBBU}\times N_{RRH}]}$ that relates each link to the cluster that it serves, where:
\begin{equation}
U_{c,ijbr}=
\begin{cases} 1,\ & \text{if link }(i,j)\text{ is used for the connection}\\
& \text{between BBU }b\text{ and RRH } r\\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}

For each pair BBU-RRH $(b,r)$ there is a flow of one unit towards $b$ and the quantity of incoming flow in an intermediate node in the path is equal to the outgoing one, therefore one has to impose:%eq:N3
\begin{equation}
\label{eq:mfc}
\begin{multlined}
\sum _{i=1}^{N_{RRH}}U_{c,ijbr}-\sum _{i=1}^{N_{RRH}}U_{c,jibr}=\begin{cases} 
-S_{br} & \text{ if }j=b\\
S_{br} & \text{ if }j=r\\
0 & \text{otherwise}
\end{cases} \\ \forall j,r\in \{1,...,N_{RRH}\}, b \in \{1,..,N_{pBBU}  \}
\end{multlined}
\end{equation}

A link between two sites can be shared for connecting more than one RRH to the same serving BBU, allowing a more efficient links capacity use and reducing deployment costs, but each link serves at most one BBU cluster:
\begin{equation}
\sum _{b=1}^{N_{pBBU}}U_{c,ijbr}=1  \text{ } \; \forall i,j,r \in \{1,...,N_{RRH}\} \label{eq:N7}
\end{equation}

In order to have constraints in (\ref{eq:mfc}) affecting the final deployment, one imposes 
\begin{equation}
U_{c,ijbr}=1\Rightarrow U_{ij}=1,\; S_{br}=1 \label{eq:N5}
\end{equation} 

\sloppy Additional 4-dimensional sparse matrices $\mathbf{U}_{\mathbf{c,f/m}[N_{RRH}\times N_{RRH}\times N_{pBBU}\times N_{RRH}]}$ represent fibre/microwave usage:
\begin{equation}
U_{cf/m,ijbr}=
\begin{cases} 
1,\ & \text{if }\text{fibre/microwave link}\: \left (i,j\right )\: \text{is used for}\\
& \text{the connection between BBU}\: b\: \text{and RRH}\: r \\
0,\ & \text{otherwise}
\end{cases} 
\end{equation}
 
Delay matrix $\mathbf{T }_{[N_{RRH}\times N_{RRH}]\left [\upmu \mathrm{s}\right ]}$  represents the delay introduced by the link from RRHs $i$ to $j$:
\begin{equation}
T _{ij[\upmu s]}=T_{f,ij[\upmu s]}\cdot U_{f,ij}+T_{m,ij[\upmu s]}\cdot U_{m,ij}\label{eq:N11}
\end{equation}

The RDCMST delay constraint is performed in what follows, imposing that the sum of the links delays in a connection between RRH $r$ and its serving BBU $b$ is lower than $\tau_{max}$,
\begin{equation}
\label{eq:del}
\begin{split}
\sum _{i=1}^{N_{RRH}}\sum _{j=i+1}^{N_{RRH}}T_{ij\left [\upmu \mathrm{s}\right ]}\cdot U_{c,ijbr}\leq \tau _{\mathit{\max } \left [\upmu \mathrm{s}\right ]} \\ \forall  b \in \{1,..,N_{pBBU}\}, r\in \{1,...,N_{RRH}\}
\end{split}
\end{equation}

The available capacity matrix $\mathbf{C}_{\mathbf{A}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$ is related to the capacity of fibre/microwave links $\mathbf{C}_{\mathbf{f/m}\left [N_{RRH}\times N_{RRH}][\text{Mbps}\right ]}$ matrices:
\begin{equation}
C_{A,ij\left [\text{Mbps}\right ]}=C_{f,ij\left [\text{Mbps}\right ]}\cdot U_{f,ij}+C_{m,ij\left [\text{Mbps}\right ]}\cdot U_{m,ij}\label{eq:N10}
\end{equation}

The required bandwidth on each link matrix $\mathbf{C}_{\mathbf{R}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$ is the required capacity between RRHs $i$ and $j$:
\begin{equation}
C_{R,ij\left [\text{Mbps}\right ]}=\sum _{b=1}^{NpBBU}\sum _{r=1}^{\mathrm{N}_{\text{RRH}\: }}C_{r\left [\text{Mbps}\right ]}\cdot U_{c,ijbr}  \; \forall i,j \in \{1,...,N_{RRH}\} \label{eq:N8}
\end{equation}

The required capacity on a link has to be lower than the available one,
\begin{equation}
C_{R,ij\left [\text{Mbps}\right ]}\leq C_{A,ij\left [\text{Mbps}\right ]} \; \forall i,j \in \{1,...,N_{RRH}\}  \label{eq:N9}
\end{equation}

Finally, the link cost matrix $\mathbf{K}_{[N_{RRH}\times N_{RRH}][\text{\euro}]}$ satisfies:
\begin{equation} 
K_{ij[\text{\euro}]}=K_{f,ij [\text{\euro}]}\cdot U_{f,ij}+K_{m,ij[\text{\euro}]}\cdot U_{m,ij} \label{eq:E1}
\end{equation}

\subsection{Optimisation Problem}
\label{sec:optprob}
In this subsection, firstly the different metrics that allow to evaluate the effectiveness of the proposed model are described, and then the mathematical entities and the objective function of the optimisation model are presented.

\subsubsection{Performance Metrics}\label{sec:permetr}
\paragraph{Latency}

Latency is one of the main constraints for the fronthaul, determining the maximum length for the link between an RRH and a BBU. One of the factors that impact the delay introduced by the fronthaul link is the physical medium adopted to implement it. Fibre links are normally deployed into cable ducts that are constructed in a way to be easily accessible for maintenance (e.g. along streets), while microwave links are deployed taking line of sight radio propagation. In order to calculate the links length, one takes the pedestrian path distance for fibre links and a straight-line for microwave ones.

The roundtrip propagation time for a link is:
\begin{equation}
T _{f/m,ij\left [\upmu \mathrm{s}\right ]}~ =\frac{d_{f/m,ij\left [\text{km}\right ]}\cdot 2}{\nu _{f/m \left [\text{km}/\mathrm{s}\right ]}}\cdot 10^{6}
\end{equation}
where:
\begin{itemize}
\item $\nu _{f/m}$:  fibre/microwave propagation speed;
\item $d_{f/m,ij}$ is the fibre/microwave link length.

\end{itemize}

The different latency contributions, presented in Fig.~\ref{fig:del}, can be expressed as:
\begin{equation}
\delta _{BBU-RRH\left [\upmu \mathrm{s}\right ]}~ =\sum _{l=1}^{N_l}T_{l\left [\upmu \mathrm{s}\right ]}+ 2 \cdot \delta _{s\left [\upmu \mathrm{s}\right ]}
\end{equation}
where:
\begin{itemize}
\item $T_{l}$: link propagation delay, round trip time
\item $N_{l}$: number of links used for the connection between an RRH and a BBU
\item $\delta _{s}$: switching delay
\end{itemize}

\paragraph{Link capacity}

The fronthaul link required capacity depends on the maximum traffic demand that is required by the RRH site, which depends on the number and type of cells that the site possesses, being calculated as \cite{pizzinat}:
\begin{equation}
\label{eq:capacity}
C_{R[\text{Mbps}]}=  (M \cdot S_{[\text{sample/s}]} \cdot W_{[\text{bit/sample}]} \cdot 2 \cdot F) \cdot 10^{-6}
\end{equation}
where:
\begin{itemize}
\item $M$: number of antennas used at the RRH 
\item $S$: sampling rate for the RRH 
\item $W$: sample width for the RRH 
\item $F$: coding factor for the RRH 
\end{itemize}
Factor $2$ is introduced to take in-phase and quadrature data into account. It is worth to mention that parameters $M$, $S$, $W$ and $F$ are related to the radio access technology, e.g. LTE, UMTS or GSM.

\paragraph{Economical Cost}
A key aspect for the design of C-RAN is represented by CAPEX, which is considered to be related to the deployment of links, BBU pools and RRHs.

In a brown-field scenario, a new link increases CAPEX while the usage of an already deployed one contributes to OPEX, being taken as a percentage of the related initial deployment cost.

The link CAPEX is related to the adopted physical medium, being modelled for fibre as:
\begin{equation}
K_{f,ij[\text{\euro}]}=k_{f[\text{\euro}/\text{km} ]}\cdot d_{f,ij [\text{km}]}
\end{equation}
where:
\begin{itemize}
\item $k_{f}$: cost per kilometre of fibre link,
\item $d_{f,ij}$: pedestrian path link length.
\end{itemize}

The cost of a microwave link $k_{m[\text{\euro}/\text{link}]}$ is not related to distance, being modelled by the cost of equipment.

Another important factor that influences CAPEX is represented by the cost related to the deployment of a BBU. The deployment cost of a BBU pool site is taken as a fix component related to the characteristics of the site, plus a variable one related to the requirements imposed by network design, such as the number of RRHs to be served by the BBU pool, expressed by vector $\mathrm{K}_{BBU[N_{pBBU}\times 1][\text{\euro}]}$
\begin{equation}
K_{BBU,i[\text{\euro}]}=K_{vBBU,i[\text{\euro}]}+K_{fBBU,i[\text{\euro}]}
\end{equation}
where:
\begin{itemize}
\item $K_{vBBU,i}$: variable cost of possible BBU site $i$
\item $K_{fBBU,i}$: fix cost of possible BBU site $i$
\end{itemize}

The variable cost of the BBU site is the sum of the costs of the equipment needed to serve each connected RRH: 
\begin{equation}
K_{vBBU,i[\text{\euro}]}=N_{sRRH,i}\cdot K_{bRRH[\text{\euro}]} 
\end{equation}
where:
\begin{itemize}
\item $N_{sRRH,i}$: number of RRHs served by the BBU $i$
\item $K_{bRRH}$: cost associated to the equipment required at BBU pool site to serve a single RRH

\end{itemize}
Considering that 
\begin{equation}
N_{sRRH,i} = \sum _{\mathrm{j}=1}^{\mathrm{N}_{\text{RRH}\: }}S_{ij} \; \forall i \in \{1,...,N_{pBBU} \}
\end{equation}  
one can model the deployment cost of a BBU as:
\begin{equation} \label{eq:bbu}
\begin{split}
K_{BBU,i[\text{\euro}]}=N_{sRRH,i}\cdot K_{bRRH[\text{\euro}]}+  K_{fBBU,i[\text{\euro}]}= \\ 
=\Bigl(\sum_{j=1}^{N_{RRH}} S_{ij}\Bigr) \cdot K_{bRRH[\text{\euro}]}+K_{fBBU,i[\text{\euro}]}
\end{split}
\end{equation}

Finally, considering that one can express the RRHs CAPEX as $ N_{RRH} \cdot K_{RRH[\text{\euro}]}$ one can express the total CAPEX as:
\begin{equation} \label{eq:capex}
\begin{split}
K_{tot[\text{\euro}]}=\sum_{i=1}^{N_{pBBU}}B_{i}\cdot K_{BBU,i[\text{\euro}]}+\sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{ij}\cdot K_{ij[\text{\euro}]} + \\ + N_{RRH} \cdot K_{RRH[\text{\euro}]}
\end{split}
\end{equation}
where the first term represents BBUs-related CAPEX, the second one the links' CAPEX and the third one is RRHs deployment cost.

\subsubsection{Integer Linear Programming Model}
In this subsection, one provides the ILP formulation for the problem under consideration. The objective function is represented by the CAPEX expressed in (\ref{eq:capex}).

Since one is interested in obtaining a cost-optimal deployment, the objective of the ILP can be written as:
\begin{equation} \label{eq:obj}
\min \Bigg( K_{tot[\text{\euro}]} \Bigg)
\end{equation}

%In the following linear formulations of constraints illustrated in \ref{sec:probstat} are provided. 

Given (\ref{eq:bbu}), the first term of the function becomes:
\begin{equation} \label{eq:obj2}
\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot \left [\left (\sum _{j=1}^{N_{RRH~ }}S_{ij}\right )\cdot ~ K_{bRRH[\text{\euro}]}+K_{fBBU,i[\text{\euro}]}\right ]
\end{equation}
which becomes nonlinear, because $B_{i}$ and $S_{ij}$ are output variables. Since (\ref{eq:obj2}) can be rewritten as: 
\begin{equation}
\label{eq:nl}
\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot \left (\sum _{j=1}^{N_{RRH~ }}S_{ij}\cdot ~ K_{bRRH[\text{\euro}]}\right )+\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot K_{fBBU,i[\text{\euro}]}
\end{equation}
and noticing that 
\begin{equation}
\sum _{\mathrm{i}=1}^{N_{pBBU\mathrm{~ }}}B_{i}\cdot \mathrm{~ }\left (\sum _{\mathrm{j}=1}^{N_{RRH}}S_{ij}\mathrm{~ }\cdot K_{bRRH[\text{\euro}]}\right ) = N_{RRH~ }\cdot \mathrm{~ }K_{bRRH[\text{\euro}]}
\end{equation}
one can rewrite (\ref{eq:nl}) as:
\begin{equation}
N_{RRH~ }\cdot ~ K_{bRRH[\text{\euro}]}+\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot K_{fBBU,i[\text{\euro}]}
\end{equation}
where the first term is constant, and the second one is variable. Moreover, the term $N_{RRH} \cdot K_{RRH[\text{\euro}]}$ in (\ref{eq:capex}) is also constant. Given that a constant contribution can be ignored in the minimisation expressed in (\ref{eq:obj}), one can write the objective function as: 
\begin{equation}
\begin{split}
\min  \bigg(\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot K_{fBBU,i[\text{\euro}]}+\sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{ij}\cdot K_{ij[\text{\euro}]} \bigg) 
\end{split}
\end{equation}

Furthermore, one can observe that 
\begin{equation}
\sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{ij}\cdot K_{ij[\text{\euro}]}
\end{equation}
given (\ref{eq:E1}), can be written as: 
\begin{equation}
\sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{ij}\cdot \left (K_{f,ij[\text{\euro}]}\cdot U_{f,ij}+K_{m,ij[\text{\euro}]}\cdot U_{m,ij}\right )
\end{equation}

Observing that the constraint in (\ref{eq:P5}) can be expressed as
\begin{equation}
U_{ij}\geq U_{f,ij}+U_{m,ij} \; \forall i,j \in \{1,...,N_{RRH} \}
\end{equation}
the problem becomes again nonlinear. 

In order to avoid this nonlinearity, one has to extend the MCFB illustrated in (\ref{eq:mfc}) and to consider into the optimal flow accommodation also microwave and fibre usage using matrices $U_{cf/m,ijbr}$.

This requires to add some additional constraints. One has to impose that 
\begin{equation}
U_{c,ijbr}=1 \Rightarrow (U_{cf,ijbr}=1)\veebar (U_{cm,ijbr}=1) \label{eq:P8}
\end{equation}
and 
\begin{equation}
U_{cf/m,ijbr}=1\Rightarrow U_{cm/f,ijbr}=0 \label{eq:P9}
\end{equation} 
which means that a single link can be deployed using either fibre or microwave. Moreover, one has to impose that 
\begin{equation}
U_{cf/m,ijbr}=1\Rightarrow  U_{f/m,ij}=1 \label{eq:P11}
\end{equation}  
to force the inclusion of the link into the final deployment. 

Therefore, one can finally write the linear objective function: 
\begin{equation}
\begin{split}
\min \biggl(\sum _{i=1}^{N_{pBBU~ }}B_{i}\cdot K_{fBBU,i[\text{\euro}]}+\sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{f,ij}\cdot K_{f,ij[\text{\euro}]}+ \\ + \sum _{j=1}^{N_{RRH}}\sum _{\mathrm{i}=\mathrm{j}+1}^{N_{RRH}}U_{m,ij}\cdot K_{m,ij[\text{\euro}]} \biggl)
\end{split}
\end{equation}

The above nonlinearity impacts also on the constraint in (\ref{eq:del}). One can rewrite the RDCMST delay constraint in (\ref{eq:del}) as:
\begin{equation}
\begin{split}
\sum _{i=1}^{N_{RRH}}\sum _{j=i+1}^{N_{RRH}}T_{f,ij\left [\upmu \mathrm{s}\right ]}\cdot U_{cf,ijbr}+\\+\sum _{i=1}^{N_{RRH}}\sum _{j=1+1}^{N_{RRH}}T_{m,ij\left [\upmu \mathrm{s}\right ]}\cdot U_{cm,ijbr} \leq \tau _{\mathit{\max } \left [\upmu \mathrm{s}\right ]} \\ \forall b\in\{1,...,N_{pBBU} \}, r \in \{1,...,N_{RRH} \}
\end{split}
\label{eq:N4}
\end{equation}

The involved parameters and variables can be divided into three categories: physical, i.e. all the entities related to the physical constraints and to the infrastructural deployment; network, i.e. entities related to network design decision, such as delay, capacity, and BBU-RRHs connections; economical, i.e. entities related to costs.

The list of input parameters and internal variables required for problem formulation is presented in Table \ref{tab:inppar}.

Moreover, several internal variables are involved in the proposed optimisation model. Analogously to the input parameters, internal variables can be categorised into physical, network and economical variables, as illustrated in Table \ref{tab:intvar}. 

The constraints of the problem can be categorised as well into three classes: network (\ref{eq:N1}), (\ref{eq:N2}), (\ref{eq:mfc}), (\ref{eq:N7}), (\ref{eq:N5}), (\ref{eq:N11}), (\ref{eq:N10}), (\ref{eq:N8}), (\ref{eq:N9}),  (\ref{eq:N4}), physical (\ref{eq:P6}), (\ref{eq:P7}), (\ref{eq:P1}),  (\ref{eq:P3}), (\ref{eq:P5}), (\ref{eq:P8}), (\ref{eq:P9}), (\ref{eq:P11}), and economical (\ref{eq:E1}).

The output variables of the optimisation problem are: $K_{tot[\text{\euro}]}$, $\mathbf{B}$, $\mathbf{U}$, $\mathbf{S}$.

\section{Results and Discussion} \label{sec:resu}
\subsection{Canonical Scenario Analysis}\label{sec:cano}
\subsubsection{Canonical Scenario Description}\label{subsec:cano}
The scenario adopted for the evaluation of the proposed optimisation model is represented by a hexagonal grid of cells, Fig.~ \ref{fig:refR}, considering different configurations with three key parameters $R_{S},R_{B},R_{C}$ where:

\begin{itemize}
\item $R_{S\left [\text{km}\right ]}$: radius of the service area 
\item $R_{B\left [\text{km}\right ]}$: radius of the BBU area
\item $R_{C\left [\text{km}\right ]}$: radius of the cell
\end{itemize}

These three parameters have a different impact on the number of cells and the number of required BBUs. An increase of $R_{S}$ implies an increase of the number of cells, while an increase of $R_{C}$ reduces the number of cells. $R_{B}$ is strictly related to the maximum BBU-RRH delay $\tau _{max}$, since the higher is the delay budget, the higher is the area covered by a single BBU, thus, intuitively, the lower is the number of BBUs required to serve all RRHs.

Regarding $R_{S}$, three values resulting in the three configurations were taken, Fig.~\ref{fig:refs}, and Table~\ref{tab:refs}.

In the following, without loss of generality and in order to obtain a theoretical behaviour comparable with the optimisation model, one considers that all the cells are already connected via a network of fibre links. Pedestrian path distance is assumed to be $1.5$ times the straight line distance, but one can assume a different factor without loss of generality for the whole model. One assumes null switching delay, all RRHs sites as feasible BBU ones, i.e.:
\begin{equation}
N_{pBBU}=N_{RRH}
\end{equation} 
and that all RRHs sites are trisector cells, each one offering LTE 20MHz MIMO 2x2 and requiring a link capacity of 2.4 Gbps (therefore, the total required link capacity for the RRH site is 7.2 Gbps (derived from (\ref{eq:capacity})). 

Moreover, regarding costs, one adopts as reference the values listed in Table~\ref{tab:refv}. CAPEX is calculated according to (\ref{eq:capex}) and OPEX (which includes power cost, personnel expenses and site maintenance and rental) is taken as an annual expenditure of 10\% of CAPEX.

\subsubsection{Theoretical Output}\label{sec:theoout}
The assumptions illustrated in Section \ref{subsec:cano} allow to formulate the problem of obtaining a theoretical number of required BBUs as a well-known cellular planning problem. One can consider the number of required BBU sites as the ratio between the total number of RRH sites in the scenario, $N_{RRH}$, and the number or RRHs servable by a single BBU defined as $N_{sRRH}$:
\begin{equation}
N_{BBU}=\ceil*{\frac{N_{RRH}(R_S,R_C)}{N_{sRRH}(R_S,R_C)}}
\end{equation}
where: 
\begin{itemize}
\item $N_{BBU}$ is the number of required BBUs
\end{itemize}

Assuming the scenario as a hexagon and that the cell and BBU coverage are hexagons, and given that the area of the hexagon is \cite{Agrawal}:
\begin{equation} 
A_{H\left [\mathrm{k}\mathrm{m}^{2}\right ]}=~ \frac{3\sqrt{3}}{2}\times R_{H}^{2}
\end{equation}
where:
\begin{itemize}
\item $R_{H\left [\text{km}\right ]}$: radius of the hexagon
\end{itemize}
one can express $N_{RRH}(R_{S},R_{C})$ as a ratio of areas:
\begin{equation}
N_{RRH}(R_{S},R_{C}) = \ceil*{\frac{A_{Rs}}{A_{Rc}}}=\ceil*{\frac{R_{S}^{2}}{R_{C}^{2}}}
\end{equation}
where:
\begin{itemize}
\item $A_{Rs\left [\mathrm{k}\mathrm{m}^{2}\right ]}$: area of the service hexagon
\item $A_{Rc\left [\mathrm{k}\mathrm{m}^{2}\right ]}$: area of the cell hexagon
\end{itemize}
and similarly 
\begin{equation}
N_{sRRH} (R_{B},R_{C})=\ceil*{\frac{A_{R_B}}{A_{Rc}}}=\ceil*{\frac{R_{B}^{2}}{R_{C}^{2}}}
\end{equation}
where $A_{R_B\left [\mathrm{k}\mathrm{m}^{2}\right ]}$ is the area of the BBU coverage, leading to: 
\begin{equation}
\label{eq:theo}
N_{BBU}= \ceil*{\frac{R_{S}^{2}}{R_{B}^{2}}}
\end{equation}

\subsubsection{Analysis of maximum latency impact}\label{sec:theodelay}

One evaluates the proposed optimisation model considering maximum BBU-RRH delay values spanning from $1.25\; \upmu \mathrm{s}$ up to $12.5\; \upmu \mathrm{s}$, which correspond to maximum BBU-RRH distance ($R_{B} $) values spanning from $250\; \mathrm{m}$ up to $2.5 \;\text{km}$.



Fig.~\ref{fig:numbbu} shows the number of required BBU sites for the three considered configurations and $R_{C}=0.25\;\text{km}$. One compares the output of the proposed optimisation model with the expected theoretical behaviour illustrated in \ref{sec:theoout}. The obtained results adopting the proposed model are in line with the theoretical output calculated as in (\ref{eq:theo}), with some discrepancies explainable by the discrete nature of the problem. Fig.~\ref{fig:numbbu} shows that by increasing the maximum delay $\tau _{max}$ the number of required BBU sites decreases, which is explainable by observing that an increase of $\tau _{max}$ corresponds to an increase of $R_{B}$ and therefore an increase of $N_{sRRH}$, resulting in a lower number of BBU sites required to cover the whole scenario. The maximum value of the number of BBUs is equal to 19, i.e. 1 BBU per RRH, while the minimum is 1 corresponding to 1 BBU serving all RRHs.

Fig.~\ref{fig:servrrhs} shows the proportional relation between the maximum delay and the number of served RRHs per BBU. Since when increasing maximum delay the number of BBUs decreases, each BBU must serve a higher number of RRHs. The maximum value is trivially reached when just one BBU is deployed, i.e. 19. 

Fig.~\ref{fig:capextheo} shows the trend of CAPEX, calculated according to (\ref{eq:capex}), considering different values of maximum BBU-RRH delay. It can be noticed how low values of $\tau _{max}$ require a high CAPEX for the operator, given the higher number of required BBUs; CAPEX remains constant from $5 \; \upmu \text{s}$ onward, i.e. when the number of BBUs is equal to 1. Moreover, RRHs contribution to CAPEX remains constant since it is related to the number of RRHs that is constant. Since one assumed an optical network already deployed, there is no contribution of fibre and microwave links because no new links deployment is required. 

In the case of OPEX, although negligible, a minor contribution from fibre links is present, due to annual expenditures for the maintenance of the physical network. However, it can be noticed that the economic sustainability of the CRAN architecture is related mainly to the annual cost of BBUs and RRHs operation, since links OPEX represents less than 1\% of the network annual costs. Fig.~\ref{fig:opextheo} shows that the trend of OPEX is analogous to CAPEX one, since it is mainly influenced by the number of BBU sites. Analogously to CAPEX, RRHs OPEX represents the main contribution when the number of BBUs is equal to 1.


\subsubsection{Canonical scenario results overview}\label{sec:theoover}

Fig.~\ref{fig:theoover} shows the number of BBUs as a function of the maximum fronthaul delay and the radius of the scenario. It highlights that the number of BBU sites is proportional to the scenario size, since the higher is the area to cover the higher is the number of required BBUs. On the other hand, as previously shown, there is an inverse proportional relation between the maximum delay constraint and the number of BBUs, since the higher is $\tau_{max}$ the higher is the number of RRHs servable by a single BBU. 

\subsection{Real Scenario Analysis}\label{sec:real}
\subsubsection{Real scenario description}
In this subsection, one analyses the proposed model for a real scenario, i.e. the city of Lisbon and its surroundings. In Fig.~\ref{fig:lisb}, one represents the cell sites from a mobile operator covering an area at the north of the Tagus river, spanning for 40 km from the city centre.

Three coverage areas with different radius and density of cell characteristics are considered for the validation of the proposed model: urban ($R_S = 0.65 $ km), suburban ($R_S = 1.5 $ km) and rural ($R_S = 7 $ km). In the three scenarios, 18 RRHs are involved. In the following, one adopts the reference simulation parameters illustrated in Section \ref{sec:cano}.

\subsubsection{Analysis of maximum latency impact}\label{sec:latereal}
One evaluates the proposed optimisation model considering $\tau_{max}$ varying in different ranges for the different scenarios: $[0.65,6.5]\; \upmu\text{s}$ for urban, $[1.5,15]\; \upmu\text{s}$ for suburban, and $[7,70]\; \upmu\text{s}$ for rural.

In Fig.~\ref{fig:delreal}, the results for the different scenarios are illustrated. The results obtained adopting the real scenarios appear to be in line with the canonical one, with some discrepancies explainable by the discrete nature of the problem. It can be noticed that in all three scenarios the maximum number of BBUs, i.e. 18, is not reached for small values of $\tau _{\mathit{\max } \left [\upmu \mathrm{s}\right ]}$. This is explainable by the non-regular disposition of RRHs in the scenario and by the presence of very near RRHs used to cover more populated areas. However, Fig.~\ref{fig:delreal} shows that when increasing the maximum delay $\tau _{max}$ the number of required BBU sites decreases, as expected. 

Fig.~\ref{fig:capexreal} and \ref{fig:opexreal} show CAPEX and OPEX for the considered scenarios calculated according to (\ref{eq:capex}). Results show that as in the canonical scenario there is an inverse relation between maximum delay constraint and costs. 
CAPEX variation is mainly influenced by the number of BBUs, since RRHs contribution is constant and links intial investment is negligible.

For the three considered scenarios, the maximum CAPEX ranges between $1.32\;\text{M\euro}$ and $1.54\;\text{M\euro}$ and is obtained for minimum values of $\tau_{max}$, a small variation being related to the different maximum number of BBUs, as shown in Fig.~\ref{fig:delreal}. To consider higher $\tau_{max}$ values reduces CAPEX to $0.35 \;\text{M\euro}$ for the urban scenario and $0.37 \;\text{M\euro}$ for suburban and rural ones, thus achieving a reduction of  76\% and 74\% respectively.

In the OPEX case, it can be noticed that passing from urban to rural scenarios increases the contribution of links maintenance. In fact, in the rural scenario, physical links OPEX becomes the major contribution to the operating costs for higher values of the maximum delay. Since in rural areas the density of cells is lower, intercell distance is generally higher and longer physical links are required, thus it requires higher maintenance costs and increases OPEX contribution. 
In the suburban case, links' OPEX becomes equal to BBUs cost for high values of delay, when only 1 BBU is required. In the rural scenario, the links' OPEX grows more rapidly and links' OPEX reaches BBUs' OPEX for lower values of delay, when BBUs number is still greater than 1, and becomes the highest annual cost contribution when only one BBU is taken.

The maximum OPEX ranges between $132\;\text{k\euro}$ and $155\;\text{k\euro}$ while the minimum one is equal to $36.56\;\text{k\euro}$ in the urban scenario, $40.88\;\text{k\euro}$ in the suburban one and $60\;\text{k\euro}$ in the rural one. Thus, the reduction of OPEX related to $\tau_{max}$ is equal to 73\% in the urban scenario, 75\% in the suburban one and is reduced to 62\% in the rural case. This highlights the impact of links mantainance annual cost on rural areas.

The three considered real scenarios are characterised by different sizes of the served area, thus, one can analyse C-RAN costs in terms of expenditures per square kilometre. The urban area requires $0.99\; \text{M\euro /km} ^{\mathrm{2}}$ maximum CAPEX, being significantly higher with respect to the suburban scenario ($0.22\; \text{M\euro /km} ^{\mathrm{2}}$) and the rural one ($0.01\; \text{M\euro /km} ^{\mathrm{2}}$). Analogously, in the OPEX case the annual expenditure per square kilometre in the urban scenario is equal to $99\; \text{k\euro /km} ^{\mathrm{2}}$, $22\; \text{k\euro /km} ^{\mathrm{2}}$ in the suburban one, and $1.01\; \text{k\euro /km} ^{\mathrm{2}}$ in the rural one.

\subsubsection{Microwave deployability impact}\label{sec:mwdeplo}

In this subsection one analyses the impact of microwave radio links deployability. The comparison between different scenarios is conducted by adopting different percentages of new deployable microwave radio links with respect to the total number of newly deployable ones. 

Fig.~\ref{fig:capexmw} shows the trend of CAPEX for two different values of $\tau _{max}$ , i.e. 3 $\upmu \mathrm{s}$ and 15 $\upmu \mathrm{s}$ in the suburban scenario. For $ \tau_{max}= 3\; \upmu \mathrm{s}$ the possibility to deploy new microwave radio links enables a significant reduction of CAPEX, since it allows to reduce the number of required BBUs. On the other hand, a small increase in microwave radio links deployment cost is required. Microwave links allow to reduce up to 35\% CAPEX while requiring an investment equal to 4\% of initial CAPEX in microwave links deployment. For $\tau _{max} = 15\; \upmu \mathrm{s}$, the number of required BBUs is already minimum, therefore no BBUs-related CAPEX reduction is introduced by microwave links. In this case, for different microwave deployability indexes one can notice a conversion of CAPEX from fibre links investment to microwave one.
\vspace{-3mm}
\section{Conclusion}\label{sec:conclusion}
Cloud Radio Access Network architecture represents a viable solution to address the problems related to the increase of traffic, and also the increase of deployment and operation costs. It splits traditional BSs into Remote Radio Heads and Base Band processing Units, which introduces the front-haul segment of the mobile network that requires a new approach to the deployment on network architecture.

This work proposes an optimisation model for the deployment of C-RAN architectures in a brown-field scenario where traditional BSs are already present. The proposed model minimises deployment costs by optimising BBUs placement as well as links deployment. The proposed optimisation framework takes into account physical, network and economical aspects. The clusterisation of RRHs is modelled through a Multicommodity Flow approach. The links deployment reuses existing access infrastructures and interconnects BBUs and RRHs through a Rooted Delay-Constrained Minimum Spanning Tree approach where the delay constraint is given by the BBU-RRH maximum RTT budget.

The key input parameters considered are cost of links, BBUs and RRHs as well as links' delay and capacity. The key output parameters are CAPEX, BBU placement, BBU-RRHs connections and physical links setup. For the optimisation, an integer linear programming approach that minimises the CAPEX is considered. 

Regarding the sensitivity of the objective function to the input parameters, results show the inverse relation between CAPEX and delay budget. CAPEX grows linearly with the cost of links, BBUs and RRHs, thus there are not critical values for the calculation of the cost-optimal deployment. This allows to adopt the proposed model as a tool for relative comparisons over many scenarios and deployment configurations that can be suitable from the operators viewpoint in network deployment planning.

One evaluated the proposed model using a canonical hexagonal grid coverage in order to compare the results obtained with the proposed approach with theoretical output calculated by adopting well-know cellular planning approach. The coherence of the results between the two approaches validates the proposed model. Results show an inverse relation between the number of BBU Pools and the maximum accepted fronthaul delay. 

Real scenarios represented by the deployment of BSs of a real operator in the city of Lisbon and its suburban area are considered. Moreover, optimal deployments for different maximum delay constraints are compared in order to show operator's trade-off between CAPEX and future proof ability of network deployment. 

The analysis of urban, suburban and rural real scenarios confirms the inverse relation between delay budget and number of BBUs. This impacts significantly on CAPEX, since RRHs contribution is shown to be constant and links intial investment is negligible. The adoption of different maximum delay constraints in the fronthaul allow a CAPEX reduction between 74\% and 76\%. Regarding OPEX, results show that to adopt higher values of delay allows a reduction of costs up to 72\% in urban areas and 62\% in rural ones. The lower reduction with respect to CAPEX is explained by the fact that when passing from urban to rural scenarios the links' operating costs impact are higher. 

The considered scenarios are compared in terms of expenditures per square kilometre. Results show that a dense urban area requires $0.99\; \text{M\euro /km} ^{\mathrm{2}}$ CAPEX and $99\; \text{k\euro /km} ^{\mathrm{2}}$ OPEX, while moving to rural areas with lower density of customers and cells reduces CAPEX to $0.01\; \text{M\euro /km} ^{\mathrm{2}}$ and OPEX to $1.01\; \text{k\euro /km} ^{\mathrm{2}}$.

Finally, the impact of microwave deployability in a suburban scenario has been analysed. Results show that microwave represent a convenient choice for the operator enabling a reduction of 35\% of total CAPEX, while requiring an increase of investment of 4\%, when capacity aspects are not at stake.

\begin{backmatter}
\section*{Abbreviations}
BBU: Base Band Unit; BS: Base Station; C-RAN: Centralised Radio Access Network; CAPEX: CAPital EXpentiture; CoMP: Coordinated Multi Point; ILP: Integer Linear Programming; MCFP: Multi Commodity Flow Problem; OPEX: OPerating EXpenditure; RDCMST: Rooted Delay-Constrained Minimum Spanning Tree; RRH: Remote Radio Head.

\section*{Availability of data and materials}
The datasets used in the current study are available from the authors, in an anonymised version, upon request.

\section*{Competing interests}
The authors declare that they have no competing interests.

\section*{Author's contributions}
The authors have contributed jointly to the manuscript. All authors have
read and approved the final manuscript.

\section*{Funding}This work was partially supported by the Italian Government under CIPE resolution no. 135 (December 21, 2012), project INnovating City Planning through Information and Communication Technologies (INCIPICT).

\bibliographystyle{bmc-mathphys}
\bibliography{biblio}

\section*{Figures}

\newpage
\begin{figure}[h!]%01
\centering
%\includegraphics{01.eps}
\caption{\csentence{General deployment view.}}
\label{fig:Fig1}
\end{figure}

\begin{figure}[h!]%02
\centering
%\includegraphics{02.eps}
\caption{\csentence{Delay contributions along the fronthaul.}}
\label{fig:del}
\end{figure}

\begin{figure}[h!]%03
\centering
%\includegraphics{03.eps}
\caption{\csentence{Canonical scenario configuration.}}
\label{fig:refR}
\end{figure}

\begin{figure}[h!]%04
\centering
%\includegraphics{04.eps}
\caption{\csentence{Reference canonical scenarios.}}
\label{fig:refs}
\end{figure}

\begin{figure}[h!]%05
\centering
%\includegraphics{05.eps}
\caption{\csentence{Number of BBUs vs. Maximum delay.}}
\label{fig:numbbu}
\end{figure}

\begin{figure}[h!]%06
\centering
%\includegraphics{06.eps}
\caption{\csentence{Served RRHs per BBU vs. Maximum delay.}}
\label{fig:servrrhs}
\end{figure}

\begin{figure}[h!]%07
\centering
%\includegraphics{07.eps}
\caption{\csentence{CAPEX vs. Maximum delay (1 km scenario size).}}
\label{fig:capextheo}
\end{figure}

\begin{figure}[h!]%08
\centering
%\includegraphics{08.eps}
\caption{\csentence{OPEX vs. Maximum delay (1 km scenario size).}}
\label{fig:opextheo}
\end{figure}

\begin{figure}[h!]%09
\centering
%\includegraphics{09.eps}
\caption{\csentence{Canonical scenario results overview.}}
\label{fig:theoover}
\end{figure}

\begin{figure}[h!]%10
\centering
%\includegraphics{10.eps}
\caption{\csentence{Urban, suburban and rural scenarios.}}
\label{fig:lisb}
\end{figure}

\begin{figure}[h!]%11
\centering
%\includegraphics{11.eps}
\caption{\csentence{Number of BBUs vs. Maximum Latency for different scenarios.}}
\label{fig:delreal}
\end{figure}

\begin{figure}[h!]%12
\centering
% \includegraphics{12.eps} 
      \caption{\csentence{CAPEX (Suburban scenario).}}
      \label{fig:capexreal}
\end{figure}

\begin{figure*}[h!]%13
  \centering
%\includegraphics{13.eps}
  \caption{\csentence{OPEX for different scenarios.}}
  \label{fig:opexreal}
\end{figure*}

\begin{figure*}[h!]%14
  \centering
 %      \includegraphics{14.eps}
  \caption{\csentence{CAPEX for different microwave deployability indexes and $\tau_{max}$ values.}}
  \label{fig:capexmw}
\end{figure*}

\newpage
\section*{Tables}
\begin{table}[h]
\centering
\caption{Input parameters.}
\label{tab:inppar}
\begin{tabularx}{\columnwidth}{|X|X|X|} \hline
\textbf{Physical} & \textbf{Network} & \textbf{Economical} \\
\hline

$\mathbf{P}_{\mathbf{f}[N_{RRH}\times N_{RRH}]}$, 

 $\mathbf{D}_{\mathbf{f}[N_{RRH}\times N_{RRH}]}$, 
 
 $\mathbf{P}_{[N_{RRH}\times N_{RRH}]}$,
 
 $\mathbf{P}_{\mathbf{m}[N_{RRH}\times N_{RRH}]}$, 
 
 $\mathbf{D}_{\mathbf{m}[N_{RRH}\times N_{RRH}]}$, 
 
 $\mathbf{D}_{[N_{RRH}\times N_{RRH}]}$, 
 
 $\mathbf{d}_{\mathbf{f}[N_{RRH}\times N_{RRH}] [\text{km}]}$, 
 
 $\mathbf{d}_{\mathbf{m}[N_{RRH}\times N_{RRH}] [\text{km}]}$ 
 &
 
 $\tau _{max\left [\upmu \mathrm{s}\right ]}$, 

 $\mathbf{T }_{f[N_{RRH}\times N_{RRH}]\left [\upmu \mathrm{s}\right ]}$, 

 $\mathbf{T }_{m[N_{RRH}\times N_{RRH}]\left [\upmu \mathrm{s}\right ]}$,  

 $\mathbf{C}_{\mathrm{m}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$, 

 $\mathbf{C}_{\mathrm{f}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$
 
 &

$\mathbf{K}_{\mathbf{f}[N_{RRH}\times N_{RRH}][\text{\euro}]}$, 

$\mathbf{K}_{\mathbf{m}[N_{RRH}\times N_{RRH}][\text{\euro}]}$, 

$\mathbf{K}_{\mathbf{fBBU}[1\times N_{pBBU}][\text{\euro}]}$, 

$K_{RRH[\text{\euro}]}$, 

$k_{f[\text{\euro}/\text{km}]}$, 

$k_{m[\text{\euro}/\text{link}]}$
\\
\hline

\end{tabularx}
\end{table}

\begin{table}[h]
\centering
\caption{Internal variables.}
\label{tab:intvar}
%\begin{tabularx}{\columnwidth}{|X|X|X|} \hline
\begin{tabular}{|p{3cm}|p{5cm}|p{3cm}|} \hline
\textbf{Physical} & \textbf{Network} & \textbf{Economical} \\
\hline

$\mathbf{U}_{\mathbf{f}[N_{RRH}\times N_{RRH}]}$,

 $\mathbf{U}_{\mathbf{m}[N_{RRH}\times N_{RRH}]}$
 &
 
 $\mathbf{U}_{\mathbf{c}[N_{RRH}\times N_{RRH}\times N_{pBBU}\times N_{RRH}]}$, 
 
 $\mathbf{U}_{\mathbf{cf}[N_{RRH}\times N_{RRH}\times N_{pBBU}\times N_{RRH}]}$, 
 
 $\mathbf{U}_{\mathbf{cm}[N_{RRH}\times N_{RRH}\times N_{pBBU}\times N_{RRH}]}$, 
 
 $\mathbf{C}_{r[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$, 
 
 $\mathbf{C}_{\mathbf{A}[N_{RRH}\times N_{RRH}]\left [\text{Mbps}\right ]}$
 &
 
 $\mathbf{K}_{[N_{RRH}\times N_{RRH}][\text{\euro}]}$, 
 
 $\mathbf{K}_{\mathbf{BBU}[1\times N_{pBBU}][\text{\euro}]}$ \\
 \hline
%\end{tabularx}
\end{tabular}
\end{table}

\begin{table}[h]
\centering
\caption{Average number of RRHs per scenario.}
\label{tab:refs}
\begin{tabular}{|r|r|r|r|} 
\hline & \textbf{Scenario 1} & \textbf{Scenario 2} & \textbf{Scenario 3} \\
\hline $\boldsymbol{R_{S[km]}}$ & 0.5 & 1.0 & 1.5 \\
\hline $\boldsymbol{N_{RRH}}$ & 7 & 19 & 37 \\
\hline
\end{tabular}
\end{table}

\begin{table}[h]
\centering
\caption{Reference cost values.}
\label{tab:refv}
\begin{tabular}{|c|r|} \hline 
\textbf{Parameter} & \textbf{Value} \\
\hline $k_{f [\text{k\euro}/\text{km} ]}$ & 5 \\
\hline $k_{m [\text{k\euro}/\text{link} ]}$ & 12 \\
\hline $K_{\text{RRH} [\text{k\euro} ]}$ & 3 \\
\hline $K_{fBBU [\text{k\euro} ]}$ & 75 \\
\hline $K_{bRRH [\text{k\euro} ]}$ & 0 \\
\hline 
\end{tabular}
\end{table}

\end{backmatter}

\end{document}
