1. INTRODUCTION

With the rapid evolution of new technologies related to the Internet of Things (IoT) [1] and the fifth generation of mobile communications (5G) [2], the performance of communication networks has to be in constant improvement. New techniques and paradigms must be proposed and implemented in order to fulfill the growing requirements of such technologies. For instance, many IoT devices have limited resources for storage, computing, and communication. To overcome this issue, a solution called mobile cloud computing (MCC) was proposed [3]. MCC solved the problem of limited capabilities of end devices by allowing them to offload the heaviest tasks to centralized servers located in huge data centers, i.e., in the “cloud.” MCC proved to work well, but since these central servers (clouds) are usually far away from the end users/devices, new challenges are introduced, especially regarding latency, network congestion, and privacy, among others.

In order to handle the mentioned issues of MCC, in 2015, the European Telecommunications Standards Institute (ETSI) Industry Specification Group (ISG) introduced the concept of mobile edge computing [4], which aims to transfer most of the functionalities of MCC to the edge of the cellular networks [5]. In 2017, the ETSI changed the word “mobile” in mobile edge computing to “multi-access,” giving rise to the actual concept of MEC (multi-access edge computing), which is the focus of this paper. The objective of this name change was not only to consider mobile technologies in edge computing, but also other technologies such as fixed networks and Wi-Fi.

MEC is a promising technology with several benefits compared to classical cloud computing. MEC servers are located in MEC data centers (MEC-DCs) placed at the edge of the network. Since MEC servers are located at a shorter distance from end users, this paradigm improves multiple aspects of MCC such as latency, privacy, and network congestion [6,7].

Emerging IoT services, some of them related to autonomous driving, Industry 4.0, or virtual/augmented reality, are demanding offloading tasks to MEC (or to the cloud) according to their requirements, especially in terms of latency [8,9].

Cyber-physical systems (CPSs) are integrated networks of physical objects, sensors, and computational elements. They enable real-time communication and interaction between the digital and physical worlds, optimizing processes and enhancing efficiency in various domains. Edge computing has proven to be a potential solution for CPSs in terms of improving service latency and saving scarce bandwidth [10].

To be able to offer its potential benefits, MEC servers should be located within a certain distance from the user equipment; therefore, a constraint arises when defining the placement of the servers in MEC network planning. The MEC placement problem is not trivial, and many research works have been carried out to solve it, as we will discuss in Section 2.

Since MEC is still an emerging technology, it is not yet widely deployed. Furthermore, most of its applications require advanced technology and communications infrastructure. Most of the studies and deployments of MEC have been performed in urban and densely populated environments, given the availability of infrastructure and the high potential revenue or return of investment.

Although a priori urban environments seem the most appropriate scenario to deploy MEC networks in the short term, in sparsely populated environments the advantages of MEC will also be required in the medium/long term. Moreover, if the new advances in technology continue to be focused in urban areas, the problem of depopulation of rural areas and concentration in urban ones may be exacerbated [11]. This implies a challenge because, assuming a traditional private service provider model, the required investment for deployments in sparsely populated areas is higher, but the potential return is lower because there is less population. Moreover, some verticals such as Connected Vehicles and Industry 4.0 will also drive the adoption of MEC technologies in rural environments.

The main goal of this work is to propose a new green field planning method to deploy MEC networks that reach all populations (including urban and rural areas), minimizing the network deployment cost directly related to CAPEX. In our study we consider that this cost is composed of two main factors: the cost of the MEC servers, and the cost of the optical cabling to be deployed. Other factors such as the cost of the transceivers and the operational costs (OPEX) are out of the scope of this work.

In MEC network planning, not only the cost of the edge servers must be considered, but the associated costs of deploying the connections between the servers, the base stations (BSs), and the wide area network (WAN) gateway also play an important role. When it comes to sparsely populated areas, with longer distances between nodes, these connections are more expensive; thus, the importance of proper planning is higher.

The remaining part of this paper is structured as follows. Section 2 presents related works on MEC networks deployment. Section 3 introduces the problem and the scenario considered in this work. Section 4 describes the main proposal of this paper for fiber and MEC network planning. Section 5 explains a clustering method for overcoming scalability issues of the proposal. Then, a set of results when applying the proposed method in a case study scenario and some comparisons against other proposals are presented in Section 6. Finally, Section 7 draws some conclusions, and some potential future research lines are also discussed.

2. RELATED WORK

There are multiple works addressing the MEC placement problem in the published literature. Most of them deal with the association between BSs and MEC servers, in such a way that each MEC server handles the service requests coming from users connected to an associated BS (or from a set of associated BSs) [12–23]. There are also many papers proposing techniques for fiber deployment [24–27]. However, there are very few papers that deal with both problems together [28–31]. Our work focuses on the deployment of MEC networks that include rural areas, where fiber infrastructure may be non-existent and the distances to be interconnected are large. Thus, the consideration of these connections is of particular importance. In some areas, especially rural ones, even though there are BSs, they are connected through radio links, which may not have enough capacity to supply all the MEC services, and therefore, a fiber deployment is needed.

Table 1 presents a summarized comparison of different network planning approaches proposed in the literature. The table specifies four aspects for each proposal: first, whether the work solves the server placement problem; second, whether the proposal solves the fiber deployment problem; third, the type of environment in which the proposal is implemented (urban or rural); and fourth, the objective considered by the proposal.

Shao et al. [12] propose a scheme to find the optimal locations to deploy a fixed number of edge servers to minimize their distance to their associated BSs using stochastic simulation, a neural network, and a genetic algorithm. Lähderanta et al. [13] minimize the sum of distances between the edge servers and their corresponding access points (APs), considering the workload of each AP and the capacity constraints of each server. The work in [13] uses and implements the concept of “fractional membership,” which allows the possibility of splitting the traffic from a BS among multiple MEC-DCs. We also use fractional membership in our proposal, as will be presented in Section 4. Cao et al. [14] combine an integer linear programming (ILP) formulation for server placement, and a game-theory-based method to deal with the dynamic characteristic of user movement. To solve the placement problem, Wang et al. [15] balance the workload among edge servers and minimize the access delay between BSs and edge servers. Li et al. [16] use K-means to solve the placement problem minimizing the average completion time of the system (the total latency), which includes calculation time, network delay (upload and download), and task queuing time. The work presented by Li and Wang [17] proposes an energy-aware edge server placement algorithm based on particle swarm optimization. In [18], Lee et al. present a heuristic approach that deploys MEC servers as small as possible while ensuring a certain service latency. The proposal by Meng et al. [19] minimizes the total cost, which is defined as the weighted sum of the service cost of requests and the opening cost of edge servers. In this scenario, due to the limited computing capacity of the edge servers, an AP may need to offload a portion of assigned requests to the remote cloud. In [20], Chen et al. propose an edge server placement method based on an immune optimization algorithm in order to find the optimal edge server location through the workload balance between edge servers and minimize the access delay to edge servers. Zhang et al. [21] present a model to maximize the “overall profit,” which is defined as the difference of the incomes caused by replicas of the services, and the cost caused by system delay. Gong [22] focuses on the edge server and virtual machine placement assignment problems and minimizes the access delay between BSs and edge servers. In order to balance workload and minimize access delay, Kasi et al. [23] propose to find the optimal locations of edge servers by using a genetic algorithm and local search optimization techniques, such as hill climbing and simulated annealing.

Table 1. Related Work

View Table | View all tables in this article

Besides the mentioned works regarding the MEC placement problem, we also review here some works dealing with optical network planning. Zukowski et al. [24] examine different fiber to the home (FTTH) deployment strategies for rural areas that should be used depending on the expected customer take-up rate to reduce the investment risk. Pedersen and Riaz [25] discuss the necessity of providing fast broadband access, preferably FTTH, to rural areas, and show how and why FTTH is being deployed in Denmark, even in the countryside. A heuristic aiming to reduce the deployment costs of passive optical networks (PONs) compared to an intuitive random-cut sectoring approach is proposed by Li and Shen [26]. In that proposal, they use a minimum spanning tree (MST) to exploit the benefits of cable conduit sharing, reducing the costs of PON deployment. In [27], Agata and Nishimura use a combination of the Steiner tree and a clustering technique to generate a suboptimal network in terms of the total cable deployment construction length based on the forecasted demand and a real road map. A greedy algorithm for placing MEC servers and connecting them to the appropriate radio access networks using a clustering approach is proposed in [32]. In [33], Liu et al. formulate the edge server placement problem, considering both workload distribution and user-to-server latency. Next, they introduce a placement strategy that merges cluster-based techniques with heuristics. The problem of optimal edge server placement is addressed by Khamari et al. in [34], where they design a methodology to reduce the cost of deploying of edge servers, combining the achievement of the desired latency threshold with workload balancing between edge servers.

There are few proposals to solve both the server placement and fiber deployment problems. Zhang et al. [28] propose a heuristic design of the deployment of a long-reach passive optical network (LR-PON) and a set of micro data centers (Micro DCs). Santoyo-González and Cervello Pastor [29] propose a method to assign computing capacity to edge nodes (ENs) that are connected to the traffic generators (TGs) through a link. Therefore, a star topology is established between TGs and ENs. However, they did not consider the links between ENs and the WAN gateway, which have significant implications in cost, especially for rural deployments. In [30], we presented an ILP formulation, from now on denoted as FibMEC-Star, to deploy the fiber and MEC network deploying dedicated paths and cables as required between BSs, MEC-DCs, and a WAN gateway, and without taking action for reducing the number of MEC-DCs. An improvement, hereafter referred to as FibMEC-Shared, was proposed in [31]. FibMEC-Shared takes the ILP formulation in [30] as the starting point, but the connection paths obtained when solving that formulation are redesigned, allowing path sharing between BSs and MEC-DCs, and introducing a ring topology connecting MEC-DCs and the WAN gateway.

In this paper, we present a new proposal for joint MEC and fiber deployment that improves these previous works [30,31]. Instead of solving a single mixed integer linear programming (MILP) formulation, it consists of three sequential steps for minimizing the civil work, the number of MEC servers, and the number of MEC-DCs, respectively. The proposal is explained in detail in Section 4. The simulation study presented in Section 6 shows that the proposal in this paper considerably reduces the total deployment cost when compared to both FibMEC-Star and FibMEC-Shared. The main contributions of this paper are summarized below:

3. PROBLEM STATEMENT

Let us assume that the location of a set of BSs has been planned to ensure coverage and access to services in a sparsely populated area. Most of these BSs are connected to WAN by insufficient radio links to fulfill the requirement of future applications. Considering a MEC network, and planning in the medium/long term, each BS should have fiber connectivity to at least one MEC-DC, i.e., a node equipped with a set of MEC servers, to support emerging services. Moreover, the distance between BSs and MEC-DCs is limited by the maximum delay supported by the services. We assume that MEC-DCs are collocated with BSs. In addition, MEC-DCs will be connected to the core network (WAN gateway) through a fiber backhaul network that ensures enough bandwidth for the services. The use of fiber technology for this segment is also a must due to the required bandwidth: fibers provide huge bandwidth and low attenuation compared with other technologies. Figure 1 depicts the described network architecture.

 

Fig. 1. General network architecture.

Download Full Size | PDF

The highest cost when deploying fiber links/networks is the civil work. Therefore, instead of installing a single fiber, cables composed of several fibers (12, 24, or more) are installed, as the cost difference is small compared to single fiber cables. Consequently, it is possible to reduce the deployment cost using path sharing: fibers to different destinations can use the same cables (and ducts) along their paths. Figure 2 illustrates the idea of path sharing.

 

Fig. 2. Multi-fiber cables used for path sharing.

Download Full Size | PDF

Figures 1 and 2 are general representations of an optical-MEC network. However, the path sharing strategy illustrated in Fig. 2 is especially suitable for rural and sparsely populated areas, since in such scenarios the optical connections are usually long. By sharing the paths, the deployment cost can be considerably reduced, considering that the civil work for fiber deployment (ducting) is the most expensive component of the network.

The complete MEC-placement problem for sparsely populated areas can be described as follows.

Given:

The objective is to find the cheapest solution that provides:

Subject to the following assumptions and constraints:

The proposal of [30], FibMEC-Star, also assumes this scenario but does not consider the possibility of sharing paths among different connections.

Regarding the cost of the joint fiber and MEC network deployment, three components are considered: ducting, cable, and servers. The ducting cost refers to the civil work needed to lay the optical fiber. The cable cost is the cost of a cable that contains a set of fibers. The server cost is the cost required to acquire the MEC servers. Therefore, the total deployment cost (${C_{\rm{Total}}}$) is calculated using Eq. (1):

4. MST-S-DC: A NEW METHOD FOR FIBER AND MEC NETWORK PLACEMENT IN SPARSELY POPULATED AREAS

As mentioned in Section 2 (Related Work), the proposal of this paper improves two previous works: FibMEC-Star [30] and FibMEC-Shared [31]. A simplified scheme of each of these two works is presented in Fig. 3. As shown in the figure, FibMEC-Shared provides a modification of a planning given by FibMEC-Star.

 

Fig. 3. Simplified scheme of previous works. (a) FibMEC-Star [30], (b) FibMEC-Shared [31].

Download Full Size | PDF

In this paper, we propose a new method, called MST-S-DC (minimum spanning tree with minimum MEC servers and data centers), to solve the fiber deployment and the MEC placement problems in sparsely populated areas with the aim of minimizing the total cost. The method splits the problem into three phases, which are sequentially solved. The order of the phases has been chosen according to their contribution to the final cost. As shown in [30], the cost of fiber deployment is the most important one, followed by the cost of MEC servers in sparsely populated areas. Finally, the lower the number of MEC-DCs, the easier it is to manage the networks (an issue that was not considered in previous works) [30].

The optimization process has been split into three phases given that solving MILP formulations is computationally expensive, and smaller problems are more likely to be solved in a reasonable amount of time. Moreover, combining the three phases in a single one results in a non-linear formulation, which makes it even more difficult to solve. Dividing the problem into three subproblems may lead to a solution with a higher economic cost than if all subproblems were solved jointly, since the deployment of optical connections, the location of MEC-DCs, and the number of servers in each MEC-DC are related elements. However, the splitting approach has been carefully designed to reduce any potential deterioration by giving priority in the optimization process to the costliest components, as we will later explain. Solving the three subproblems jointly would require the use of techniques different from those employed in this paper.

Figure 4 depicts the process of the three phases described in this section. Phase 1, MST, determines the ducting topology considering the BS locations database. This ducting topology is then processed by a MILP formulation in phase 2, which computes the minimum number of servers needed. Finally, phase 3 uses that information to solve the complete problem minimizing the number of required MEC-DCs. As we have mentioned, we solve the problem using three sequential phases given that combining them in a single formulation, including the spanning tree step, introduces a non-linearity to the model. Moreover, solving simpler and lighter phases separately reduces the computational cost, making it possible to solve bigger scenarios.

 

Fig. 4. MST-S-DC three-phase model.

Download Full Size | PDF

A. Phase 1: Fiber Duct and Cable Planning Based on a Minimum Spanning Tree

A MST is a well-known problem in graph theory that consists of finding the minimum-cost network that interconnects a given set of nodes. The spanning tree of a graph $G$ is a connected undirected graph with no cycles, which includes every vertex of $G$ and whose edges all belong to $G$. The main reason for setting the planning of the fiber duct and cabling as a MST problem is the usually high cost of the civil work required to deploy optical fiber links. According to [25], the civil engineering costs are around 80%–90% of the total cost of the network deployment when installing fiber in rural areas. Since the use of a MST minimizes the total length of the civil work to be done, it is considered the most appropriate approach.

The considered network model assumes that all BSs must be connected to at least one MEC-DC (located in BSs), and the MEC-DCs must be connected to the WAN gateway. Therefore, the MST fulfils this objective as all BSs can reach each other by following the MST. In the network planning scenario, the nodes of the graph are the BSs at their respective locations and the WAN gateway. The weights of the edges are the distances between each pair of nodes (BSs). Then, the Kruskal’s algorithm [35] is used to obtain the MST. Notice that the ducts, and thus the civil work, are defined by the paths of the MST, and there may be shared paths, i.e., some paths can contain multiple fiber cables. The amount of fiber cables needed for each edge or link of the MST is determined by the next phases.

B. Phase 2: Mixed Integer Linear Programming Formulation for the MEC Placement Problem

Once the MST is obtained, a MILP formulation is solved to determine the minimum number of MEC servers that can be deployed to comply with the network requirements.

As can be seen in Fig. 4, phase 2 is only used to compute the minimum number of servers required. Table 2 summarizes the notation used in the formulation. All symbols correspond to known values (inputs), except for the last three sets (${{x}_{{ij}}}$, ${{X}_{{ij}}}$, and ${{y}_{i}}$), which are the variables (outputs) of the problem.

Table 2. Model Notations

View Table | View all tables in this article

The number of MEC servers in the MEC-DC of ${{\rm BS}_{i}}$ is ${{y}_{i}}$. Thus, if ${{y}_{i}} = 0$, ${{\rm BS}_{i}}$ is not equipped with a MEC-DC, and therefore, its traffic requiring edge computing must be served by a MEC-DC placed in another BS. This formulation allows fractional membership, which means that a BS can use resources from multiple MEC-DCs if needed. The real variable ${{x}_{{ij}}}$ defines the fraction of the traffic (requiring edge computing) from ${{\rm BS}_{i}}$ that is served by the MEC-DC located in ${{\rm BS}_{j}}$. The variable ${{X}_{{ij}}}$ is a binary version of ${{x}_{{ij}}}$; therefore, if ${{x}_{{ij}}} \gt 0$, then ${{X}_{{ij}}} = 1$ and an optical fiber must be laid between those two BSs (following the path defined by the MST). Otherwise, ${{X}_{{ij}}} = 0$. Similarly, if ${{\rm BS}_{j}}$ is equipped with MEC resources, ${{y}_{j}} \gt 0$ and an optical fiber cable connecting ${{\rm BS}_{j}}$ and the WAN gateway should be deployed. Although phase 2 obtains a full network configuration with the minimum number of MEC servers, it is only a particular solution to the problem. Then, we only use phase 2 to get the minimum number of servers required and use it as input of phase 3 to find the solution with both minimum servers and MEC-DCs.

The objective function of the MILP formulation is shown in Eq. (2). Since the fiber connection paths are defined by the MST obtained in phase 1, the MILP formulation focuses on minimizing the total cost associated with MEC servers, which is equivalent to minimizing the number of servers to be deployed (since all servers are assumed to have the same configuration as previously stated). Therefore, the MILP formulation is as follows:

In this formulation, the distance ${{d}_{{ij}}}$, which is an input to the MILP formulation, is the length of the path between ${{\rm BS}_{i}}$ and ${{\rm BS}_{j}}$ following the MST, as expressed in Eq. (7):

C. Phase 3: MEC-DC Minimization

The previous two phases determine, respectively, the civil work required for the deployment of the optical network (i.e., the set of paths between BSs along the MST), and the minimum number of servers needed to meet user demands. Note that the minimum number of servers required, $S$, can be computed using Eq. (2) once the previous MILP formulation is solved. This information is used as input for the third phase to ensure that these characteristics are maintained. Then, the third phase solves a variation of the MILP formulation used in the second phase, now with the objective of minimizing the number of MEC-DCs (but ensuring that the same minimum number of servers in the network and the same civil work are maintained).

The motivations for minimizing the number of MEC-DCs (where the edge servers are hosted) are as follows:

A new binary variable ${{Y}_{i}}$, is introduced in the MILP formulation for phase 3. It takes a value of 1 if ${{\rm BS}_{i}}$ is equipped with a MEC-DC (and, thus, has MEC servers) and 0 otherwise. Then, the MILP formulation for phase 3 is:

minimize

Constraint (9) makes ${Y_i}$ to be 1 whenever ${{y}_{i}} \gt 0$, and Constraint (10) forces ${Y_i}$ to be 0 if ${{y}_{i}} = 0$. Constraint (11) ensures that the number of servers is equal to the minimum number computed in phase 2.

Although phases 2 and 3 could be combined in a single formulation, it becomes more complex, translating into a much slower resolution than splitting into two independent subproblems. This is especially important in scenarios with a high number of BSs.

After executing the three phases, a model that reduces the civil work (ducting), the number of servers, and the number of MEC-DCs is obtained. Regarding the cost, in the FibMEC-Star method presented in [30], the three components of the cost (${l_D}$, ${l_C}$, and ${n_S}$) are obtained from the formulation, whereas in the MST-S-DC scheme proposed in this paper, ${l_D}$ is obtained from the first phase, ${n_S}$ from the second one, and ${l_C}$ from the third phase.

Finally, it should be noted that Constraint (6) ensures that the distance between a base station and the location of the computing resources that it will use (and thus the associated delay) does not exceed a limit. However, if needed, it is also possible to minimize the delay by including it in the objective function of phase 2 or 3. Nevertheless, there is a tradeoff between delay and cost, in such a way that lower delay usually implies the need for more servers and MEC-DCs. In summary, should it be necessary to optimize the delay, the objective function can be replaced by a linear combination of the current function and the total delay, assigning weights to each term depending on the importance given to each one.

5. MST-S-DC WITH RADIAL CLUSTERING

MILP problems are, in general, NP-hard, which means that no polynomial-time algorithms are known to solve them. Therefore, as the number of variables and constraints grows, it becomes increasingly difficult and time-consuming to find an optimal solution.

Even though MST-S-DC is a fast method for small and medium scenarios, it has difficulties solving large scenarios due to the above mentioned scalability problem of MILP formulations. To solve this problem, we have also designed a clustering method to divide large scenarios into smaller parts that are easier to process by MST-S-DC. We call this method radial clustering.

Algorithm 1 describes the proposed radial clustering scheme. It takes as input the locations of the BSs in the scenario, their respective workloads, and the desired number of clusters, $K$. The locations of the BSs (latitude and longitude) are transformed to polar coordinates to get the angle at which each BS is placed with respect to the position of the WAN gateway. Then, the BSs list is sorted by angle and the process to create the clusters is initiated. Beginning with the BS with the lowest angle, we include it in the first cluster, and keep appending BSs into this cluster until the total estimated workload of the cluster reaches a $K$th part of the total workload of the scenario. Then the process is repeated for the next cluster until we obtain $K$ clusters with similar workloads.

With the BSs distributed into clusters, the MST-S-DC process is applied to each cluster. These processes can be launched in parallel to save time. Then the result is a set of trees, one for each cluster, and each one having its own MEC locations and optical connections defined.

Algorithm 1. Radial Clustering

View Table | View all tables in this article

6. PERFORMANCE EVALUATION

The performance of our proposals has been analyzed assuming the scenario of the Spanish region of Castilla y León, with ${94}{,}{226}\;{{\rm km}^2}$ and 2,302,253 inhabitants, where 1576 BSs of a specific network operator (Telefónica) are located. Given these characteristics, Castilla y León is suitable for the study of sparsely populated areas. Since the complete scenario cannot be solved with MST-S-DC due to MILP scalability limitations, we perform first an analysis in the Valladolid province of Castilla y León. Then, a second analysis takes the results of each of the nine provinces of the region separately, and finally, we analyze the results for all Castilla y León applying the radial clustering method.

The population of each city or village was obtained from [37] while the location of the BSs was obtained from [38]. We assume that the workload of each BS is proportional to its associated population. In our model, the population of each village is equally distributed among the BSs located in that village, and if a village does not have a BS, its population, and hence its workload, will be assigned to the nearest BS. In [39], we have made accessible the combined dataset so that it can be used by other researchers in the area.

A study of network capabilities and requirements of MEC hosts is presented in [36], from where we extracted the number of simultaneous users that a MEC server can handle. According to [36], we assume a mixed traffic profile composed of 70% of video traffic, 15% of car traffic, 10% of smart factory, and 5% of augmented/virtual reality and consider that a server is composed of 16 machines of 4 cores at 3.4 GHz. Given the mentioned traffic and server characteristics, the number of simultaneous users that a MEC server can handle is ${U_{{\max}}} = {75}\;{\rm users/server}$.

Regarding the cost of the MEC network deployment, we considered the three components presented before. We assumed a ducting cost, ${C_D}$, of 15,000 € per km [40]. We also considered single-mode 24-fiber optical cable, whose cost per km, ${C_C}$, is 1100 €/km in a specific provider shop [41]. For the cost of a MEC server, ${C_S}$, we considered the current cost of 16 Dell R340 machines of 4 cores at 3.4 GHz, which is approximately 30,000 € [42]. The numerical costs we used in the study are summarized in Table 3. Notice that these values are used to give a numerical idea of the total cost.

Table 3. Deployment Component Costs

View Table | View all tables in this article

For all the tests described in this section, the value of ${{D}_{{\max}}}$ in Constraint (6) was set to 50 km.

To implement and assess the models, we used the Python-based Pyomo optimization tool, with the IBM CPLEX optimizer.

 

Fig. 5. Effect of phase 3 on MEC-DCs.

Download Full Size | PDF

A. Effect of MEC-DC Minimization (Phase 3) for Valladolid Province

This section presents the results of multiple tests performed in the Valladolid province of Castilla y León (Spain), comparing different approaches. To begin with the results, the proposed method, MST-S-DC, is applied to the 218 BSs of Valladolid (province of Castilla y León), and the effect of the third phase (MEC-DCs minimization) is studied. Figure 5 shows the amount of MEC-DCs required for different values of the percentage of maximum simultaneously connected population ($\alpha$). We only consider values of α ranging from 0.1% to 3%, since we are assuming the simultaneous demand of advanced services (so just a small portion of the population is expected to demand these services, simultaneously, in the short and medium term), and since we are only considering the base stations of a single network operator, which will not have the entire population as subscribers. We compare the outcomes when only phases 1 and 2 of the model are executed (denoted by MST-S) with the results when phase 3 is also applied (MST-S-DC). Note that the needed ducting and total number of MEC servers are the same in both options. The results show that the inclusion of the third phase in the method allows for an important decrease in the number of MEC-DCs, and it is more evident as α increases.

As can be seen in Fig. 6, the reduction of MEC-DCs implies a reduction in the needed optical fiber cable, due to the fact that each MEC-DC is connected to the WAN gateway. Since both ducting and number of servers are equal for MST-S and MST-S-DC, the observed cable reduction implies a reduction as well in the overall cost.

 

Fig. 6. Effect of phase 3 on fiber.

Download Full Size | PDF

In addition, it should be noted that, although not quantified in this paper, the reduction in the number of MEC-DCs, besides reducing the needed cable, implies more advantages. In order to adapt a BS for hosting a MEC-DC, infrastructure modifications are needed. Moreover, since MEC-DCs have valuable equipment and the servers may store valuable information, a physical security scheme must be implemented for each MEC-DC. Therefore, the reduction in the number of MEC-DCs translates into additional cost savings.

Finally, as an example, a graphical representation of the result for the Valladolid province after applying the three phases of the proposed method, assuming a simultaneously connected population $\alpha = {3}\%$, is shown in Fig. 7. The red points on the map are the MEC-DCs, and the numbers next to them represent the number of servers in each node. Each BS without servers (blue points) has a fiber connection (blue lines) to a MEC-DC, and all MEC-DCs are connected to the WAN gateway in Valladolid city, at the center of the map, represented by a red star.

 

Fig. 7. Obtained network for Valladolid province.

Download Full Size | PDF

 

Fig. 8. Total cost average for the nine provinces.

Download Full Size | PDF

B. Comparison of Proposals When Applied to the Nine Provinces of Castilla y León

Once we have demonstrated the effectiveness of the third phase of the model, we perform a comparison of MST-S-DC with two other approaches:

To compare the three approaches, we applied the methods to the BSs of the nine provinces of Castilla y León (considering each province individually), and we computed the average of the results as well as the 95% confidence interval. In Fig. 8, the total cost of the three methods is represented, including ducting, fiber, and servers, following Eq. (1). The confidence intervals are represented with vertical lines in the graph, and they are relatively large due to the high difference of the characteristics (and thus results) of the nine provinces. As shown in Fig. 8, the previous proposals, FibMEC-Star and FIbMEC-Shared, lead to considerably higher costs than MST-S-DC, which is the clear winner in terms of deployment cost, with around 50% of the cost of FibMEC-Star and 40% of FibMEC-Shared. The cost for the three approaches increases with the percentage of connected population, since for more users, more servers are needed. However, the most significant component of the cost is ducting, and it remains constant when the percentage of connected population increases. Separate analyses are shown for ducting, MEC-DCs, and servers in Fig. 9, Fig. 10, and Fig. 11, respectively.

 

Fig. 9. Ducting comparison.

Download Full Size | PDF

 

Fig. 10. MEC-DCs comparison.

Download Full Size | PDF

 

Fig. 11. Total servers to deploy.

Download Full Size | PDF

Since the studied scenario covers long distances, ducting represents the most important factor of the cost. Figure 9 represents the required ducting (in km) for the three approaches. As shown there, the required ducting for MST-S-DC is less than half of that required for FibMEC-Star and is around 70% of the ducting required by FibMEC-Shared solution. This great saving is due to the MST-based connections topology, which permits using ducts for multiple cables.

When comparing the number of MEC-DCs obtained by each technique (Fig. 10), MST-S-DC presents again the best results, which proves the convenience of the proposal. Since MST-S-DC is the only method that puts effort in reducing the number of MEC-DCs through the phase 3, it clearly outperforms the other approaches in this sense.

As illustrated in Fig. 11, regarding the total number of servers to be deployed, the FibMEC-Star and FibMEC-Shared approaches deploy more servers than MST-S-DC, especially for small values of α. MST-S-DC finds a solution with fewer servers than the other two proposals because, in phase 2, the objective function focuses on minimizing the number of servers, whereas in FibMEC-Star, the objective function minimizes the total cost (assuming dedicated ducts), and results are thus significantly influenced by the optical network. On the other hand, it should be noted that the number of servers is the same in FibMEC-Star and in FibMEC-Shared.

The time spent by the system in solving the different formulations is represented in Fig. 12. When comparing the elapsed time of the other two solutions, we find out that MST-S-DC is solved in less time for high values of connected population. This result shows that MST-S-DC presents better scalability than the other two proposals when the population increases. The reason for this behavior is that MST-S-DC splits the problem into three smaller and easier to solve sub-problems, while the other two proposals have a more complex formulation that solves the whole problem in a single step.

 

Fig. 12. Elapsed time.

Download Full Size | PDF

C. Results of MST-S-DC with Radial Clustering in All of Castilla y León

The last set of tests focuses on the whole region of Castilla y León, which consists of 1576 BSs. For each test, if no solution was found within 24 h of processing, we discarded the test and assumed that the problem could not be solved under the given conditions. Since the complete scenario could not be solved directly with MST-S-DC due to the scalability limitations of the MILP formulation, the radial clustering approach is used first. A minimum number of six clusters was needed for the formulation to be solved. Thus, as an initial example, six clusters have been created using Algorithm 1 (later, we will show results for other numbers of clusters). Then, the MST-S and the MST-S-DC methods were used for each of the clusters, assuming a simultaneously connected population $\alpha = {3}\%$. Figures 13 and 14 illustrate the results when using MST-S and MST-S-DC, respectively. In the illustrations, each cluster is presented with a different color, and each sub-tree is connected to the WAN gateway. By comparing the two figures, the effect of the third phase can be graphically seen. There are considerably more red points (MEC-DCs) in Fig. 13 than in Fig. 14. Moreover, the required cable is less after the execution of phase 3; this is represented by the widths of the lines in the graphs, which are proportional to the number of cables running through the ducts.

 

Fig. 13. Result obtained with MST-S (phases 1-2) for Castilla y León with radial clustering.

Download Full Size | PDF

 

Fig. 14. Result obtained with MST-S-DC (phases 1-2-3) for Castilla y León with radial clustering.

Download Full Size | PDF

A quantitative comparison between the shown outcomes of the MST-S and MST-S-DC methods is presented in Table 4. The required servers and ducting are the same, since these components are defined by phases 1 and 2, respectively, but the reduction in cable is considerable (36.08%) and even bigger is the reduction in MEC-DCs (86.77%). The reduction in costs is 4.08%, which translates into a significant monetary saving, considering the budgets that are being considered. Moreover, as previously mentioned, the reduction of MEC-DCs implies additional cost savings (related to setting up and maintaining those sites), although they have not been quantified in the calculation.

Table 4. Comparison of Phases 2 and 3

View Table | View all tables in this article

In Fig. 15, the total costs of FibMEC-Star, FibMEC-Shared, and MST-S-DC for the whole region of Castilla y León, when applying the clustering method with six clusters, are shown. The advantage of MST-S-DC is even more evident for this larger scenario than for the implementation in single provinces because of the increased duct lengths and the importance of minimizing them. This demonstrates that the new proposal, MST-S-DC, is especially suitable for wide areas and long distances to be interconnected.

 

Fig. 15. Total costs for Castilla y León.

Download Full Size | PDF

Figure 16 presents a comparison of the total costs of MST-S-DC for different numbers $K$ of clusters. The clustered network is still a spanning tree, but not the minimum spanning tree anymore; therefore, a larger value of $K$ implies a cost increase, but if $K$ is too small, the formulation cannot be solved in a reasonable time. In our Castilla y León scenario, the minimum value of $K$ that could be solved in reasonable time is 6. In Fig. 16 we can see the increase in cost that implies a higher $K$. For small values of $K$, the differences are relatively small (see $K = {6}$ and $K = {7}$), but for larger values the increment in cost becomes considerable. To offer a clearer idea of the relative differences, we summarize in Table 5 the average cost (when considering the different values of $\alpha$) for each case, as well as the comparison in terms of percentage compared to the $K = {6}$ case. Thus, the values for each case, i.e., for each value of $K$ in the table, are calculated by averaging the costs shown in Fig. 16 for different values of simultaneously connected population when considering that value of $K$.

 

Fig. 16. Number of clusters ($K$) comparison.

Download Full Size | PDF

Table 5. Average Cost Increments

View Table | View all tables in this article

7. CONCLUSIONS

In this paper, we have presented a proposal for cost-aware MEC and optical network deployment. The combination of a MST for paths definition and the use of a MILP formulation to determine server locations has proved to be convenient under the test circumstances. Most works regarding MEC server placement only consider the server locations, but not the connections needed. The planning of the connections is especially important when it comes to sparsely populated or rural areas, given that the distances to interconnect the points are larger. The new proposal, MST-S-DC, considers the costs of deploying optical fiber as well as the cost of MEC servers. Additionally, it minimizes the number of MEC-DCs. Moreover, we have also proposed and implemented a clustering algorithm, which improves scalability and the distribution of connections of MST-S-DCs. The proposal has been compared with two methods previously published, FibMEC-Star [30] and FibMEC-Shared [31], showing cost reductions of around 50% and 40%, respectively.

The quantitative results presented in this paper have focused on reducing the implementation cost of the MEC network, only considering the expenditures related to servers and fiber deployment. However, as discussed in the paper, the amount of MEC-DCs to be implemented affects the cost of the network, both during the implementation (due to required structural modifications to BSs to host the MEC-DC), and during the working period of the MEC-DC (security and operational expenditures). On the other hand, the proposed technique only cares about ensuring connectivity and availability of computing processing for the required demand and cost but does not consider protection or techniques for resiliency against link/node failures, which can be especially concerning in a MST topology. In future works, we plan to include the mentioned missing aspects: the quantification of MEC-DCs cost and the inclusion of protection schemes.

On the other hand, all tests included in this paper have been made assuming a greenfield scenario, where we have proved the effectiveness of the proposed technique. However, it should be noted that the proposed model can also be easily extended to brownfield scenarios, where some optical fibers may already exist. In the case that some fibers and ducts are available beforehand, the first phase (MST) would only define the missing connections to complete the graph, and the rest of the model (phases 2 and 3) would run in the same way as in the greenfield scenario. Nevertheless, the analysis of brownfield scenarios is another future research line.