Jad Oueis
email: jad.oueis@insa-lyon.fr

Vania Conan

Damien Lavaux

Hervé Rivano

Razvan Stanica

Fabrice Valois

Herve Rivano

Core Network Function Placement in Self-Deployable Mobile Networks

Keywords: Mobile Networks, Self-deployable, Core Network, Placement, Flow Centrality, Limited Backhaul

Introduction

Since the appearance of the Global System for Mobile Communications (GSM), at the beginning of the 1990s, until the latest release of the Long Term Evolution (LTE), mobile networks have mainly relied on a xed, hierarchical, and standardized architecture [1]. Careful planning and deployment strategies are implemented by mobile operators in order to provide coverage and data services to users. The planning phase usually includes, among others, the base stations (BSs) placement, as well as the backhaul network dimensioning [START_REF] Sesia | LTE -the UMTS Long Term Evolution[END_REF].

Recent technology advances allowed reducing the size and weight of wireless network equipment, notably the BS. This led to the design of rapidly deployable BSs, that are easy to congure and move, potentially in an autonomous manner, as opposed to a xed classical BS. Consequently, novel out-of-the-box approaches emerged in mobile networks deployment [START_REF] Chandrasekharan | Designing and Implementing Future Aerial Communication Networks[END_REF]. In this context, notable eorts have been made in both research and industry to develop rapidly deployable BSs, and propose innovative deployment platforms. Indeed, several projects are currently studying the use of aerial platforms in providing wireless services [START_REF] Chandrasekharan | Designing and Implementing Future Aerial Communication Networks[END_REF]. For example, Google launched the Loon project consisting of a eet of balloons operating at an altitude around 20 km, providing network coverage to large geographical areas with high bit rates [4]. Similarly, drones equipped with BSs are being used to supply network services to users. Engineering ight tests were recently conducted by mobile operators, such as Verizon, using a so-called ying cell site aboard a drone [START_REF] Bor-Yaliniz | The New Frontier in RAN Heterogeneity: Multi-Tier Drone-Cells[END_REF]. Other low-altitude unmanned aerial platforms, such as helikites, are also being tested to act as BSs [START_REF] Valcarce | Airborne Base Stations for Emergency and Temporary Events[END_REF]. On the other hand, terrestrial platforms of rapidly deployable BSs recently emerged [START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF]. For example, lightweight, easy to move BSs that can be mounted on terrestrial vehicles were recently developed, as well as ultra-compact wearable BSs that can be worn as backpacks [8].

These platforms provide users with coverage and data services in a variety of use cases. One usage is to ensure easy and cheap coverage in isolated areas with low population density, where no coverage or network infrastructure exists (e.g., oshore drilling). Moreover, these platforms allow increasing the original network capacity in case of a surge in user demand, during public events with large crowds (e.g., festivals, sport events). Furthermore, in mission-critical situations, following man-made or natural disasters, these platforms can serve for the fast deployment of a dedicated communication network for rst responders (e.g., paramedics, reghters, police ocers).

Such networks can be deployed in emergencies as a replacement or a complement of the original network, in case the latter was damaged or completely destroyed [START_REF] Liebhart | LTE for public safety[END_REF].

The usage of such BSs introduces new challenges. Several BSs need to interconnect to cover wider areas, with minimal human intervention and operator control. Indeed, neighboring BSs must at least be able to discover each other, coordinate, and setup a backhaul link with the core network for data and signaling trac exchange [START_REF] Favraud | Toward moving Public Safety Networks[END_REF]. In other words, both the radio access network and the backhaul network should self-congure and self-organize.

Consequently, we refer in this paper to such networks as self-deployable mobile networks.

Several dissimilarities distinguish self-deployable mobile networks from classical mobile networks. Scale-wise, self-deployable networks are relatively smaller, with fewer number of BSs and smaller coverage areas. They comprise few interconnected BSs (generally less than 10), depending on the needed coverage area, and serve a limited number of users, depending on the scale of the situation in question. From an architecture point of view, in classical mobile networks, the BSs are dependent on several separate entities (physical or logical), usually located in the core network (denoted hereafter as Evolved Packet Core (EPC), as per the LTE nomenclature). The EPC entities provide key functionalities, such as authentication, session management and routing, to name a few [START_REF] Sesia | LTE -the UMTS Long Term Evolution[END_REF]. Each BS usually has a dedicated backhaul link towards the core network. For ease of deployment, the architecture of a self-deployable network must be simpler, and the BSs are supposed to be as autonomous as possible. In this sense, a strong physical dependency between the access and the core network may limit the autonomy of the BS, as well as its exibility and resiliency [START_REF] Gomez | Enabling Disaster-Resilient 4G Mobile Communication Networks[END_REF]. Furthermore, having a physical separate core network requires additional hardware on one hand, and bandwidth provisioning for the backhaul between each BS and the core network, on the other hand. Hence, in a self-deployable network, a BS does not necessarily have a dedicated backhaul connection to a traditional EPC [START_REF]Technical Specication Group Services and System Aspects; Isolated Evolved Universal Terrestrial Radio Access Network (E-UTRAN) operation for public safety (Release 13)[END_REF]. Instead, a BS is co-located with, or at least has access to a Local EPC. This is an entity analogous to the traditional EPC, providing the same basic functionalities as the latter, in addition to housing the application servers. Unlike a traditional EPC, the Local EPC can be co-located with the BS using function virtualization technologies [START_REF]Technical Specication Group Services and System Aspects; Study on architecture enhancements to support isolated Evolved Universal Terrestrial Radio Access Network (E-UTRAN) operation for public safety (Release 13)[END_REF][START_REF] Gomez | Enabling Disaster-Resilient 4G Mobile Communication Networks[END_REF].

Hence, in a self-deployable network with multiple interconnected BSs, one of the BSs must be co-located with a Local EPC in order to provide the necessary core network functionalities (Fig. 1). The other BSs in the network must then be able to reach the designated BS co-located with the Local EPC. First, we argue that a Local EPC should be placed in a way that allows it to receive the maximum trac from each BS in the network, under certain capacity and load distribution constraints. To that end, we propose a novel centrality metric in a network, denoted ow centrality. This metric measures the capacity of a node in the network (i.e., a BS in our case) in receiving the total amount of ows. The ow centrality of a node is represented by the maximum trac that can be sent simultaneously by all the other nodes in the network towards this node, while respecting link capacity constraints.

It is based on an underlying linear optimization problem. We propose to co-locate the Local EPC with the BS having the maximum ow centrality in the network.

Second, we elaborate an analytical study allowing the computation of ow centrality in canonical non-random graphs, such as path graphs and balanced trees. Then, building on extensive simulations with dierent parameter settings, we further deduce general properties of the ow centrality metric, such as the dependence between the latter and the backhaul network properties, and the position of the node with the maximum ow centrality in a network. Third, we benchmark the ow centrality metric by comparing it to different state of the art centrality metrics. We consider dierent types of graphs, modeling dierent network topologies. We highlight the loss in the total amount of trac received by the Local EPC, when the latter is placed on a node not having the maximum ow centrality. Results validate the advantages of placing the Local EPC on the node with the maximum ow centrality, as the trac loss occurring otherwise is signicant, reaching 55% in some cases.

The remainder of the paper is organized as follows. In Sec. 2, we discuss related work with an overview of state of the art centrality metrics and placement problems in radio networks. In Sec. 3, the network model, on which this work is based, is described. We introduce the ow centrality metric in Sec. 4, and the corresponding analytical study in non-random graphs in Sec. [START_REF] Bor-Yaliniz | The New Frontier in RAN Heterogeneity: Multi-Tier Drone-Cells[END_REF]. We analyze the underlying properties of the ow centrality metric in Sec. 6, and then compare it in Sec. 7 with other relevant network centrality metrics. Finally, we conclude the paper and discuss future work in Sec. 8.

Related Work

Being relatively novel, multiple aspects of self-deployable mobile networks are currently being researched and developed [START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF]. Regarding deployable BSs, Gomez et al. [START_REF] Gomez | Enabling Disaster-Resilient 4G Mobile Communication Networks[END_REF] designed a software architecture with a set of protocols allowing the virtualization of the EPC functions and their placement closer to the BS. On the other hand, Cao et al. [START_REF] Cao | Spectrum Awareness Scheme of the Rapidly Deployable eNodeB for Unexpected and Temporary Events[END_REF] proposed cognitive radio techniques to quickly adapt the deployable BSs to a complex radio spectrum environment, in unexpected and temporary events. Furthermore, self-deployable networks recently appeared in the 3rd Generation Partnership Program (3GPP) LTE for public safety standard, in which the Isolated E-UTRAN Operation for Public Safety (IOPS) concept was standardized. IOPS aims at guaranteeing communication between public safety agents, via deployable BSs co-located with a Local EPC [START_REF]Technical Specication Group Services and System Aspects; Study on architecture enhancements to support isolated Evolved Universal Terrestrial Radio Access Network (E-UTRAN) operation for public safety (Release 13)[END_REF]. This isolated mode of operation is usually required following disasters, completely destroying or damaging the infrastructure, and in out of coverage areas [START_REF]Technical Specication Group Services and System Aspects; Isolated Evolved Universal Terrestrial Radio Access Network (E-UTRAN) operation for public safety (Release 13)[END_REF]. Seeing the novelty of the IOPS concept in the mobile networks eld, several development prospects still lie ahead [START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF]. In this work, we answer one of the many IOPS hanging questions, which is where to place the Local EPC serving the network, once multiple BSs are interconnected.

Centrality in Networks

With the objective of maximizing the trac received by the Local EPC from all the nodes in the network, it seems logical that the Local EPC should be placed on a central node. However, there are several ways to measure node centrality in a network, each one highlighting a dierent characteristic of the node, and its relative importance in the network [START_REF] Borgatti | Centrality and Network Flow[END_REF].

Among the many centrality metrics, we present in the following a nonexhaustive list of those that are most relevant to our work. Let G(V, E) be an undirected graph, and c(u, v) the capacity of the edge (u, v) ∈ E, linking nodes u, v ∈ V .

The degree centrality of a node is equal to the degree of the node, i.e., the number of links the node has with other nodes [START_REF] Freeman | Centrality in Social Networks: Conceptual Clarication[END_REF]. While the degree centrality gives an idea on the node connectivity in the network, it does not take into consideration the limited link capacities. Hence, a node with the maximum degree centrality is not necessarily capable of receiving high amount of ows.

The weighted degree is dened as the sum of the weights (e.g., capacity) of the links connecting the node to its direct neighbors.

W (u) = v∈V c(u, v) (1)
The node with the maximum weighted degree is potentially capable of receiving the maximum amount of trac. However, this trac is not necessarily achievable, since the amount of ows actually received depends on the whole network topology, and on the other potentially limited links routing these ows.

The closeness centrality of a node measures how close a node is to all the other nodes in the network [START_REF] Bavelas | Communication Patterns in Task Oriented Groups[END_REF]. Formally, the closeness centrality of a node is dened as the reciprocal of the sum of all the shortest distances from that node to all the other nodes in the network. If we denote by d(u, v) the shortest path between nodes u and v, then the closeness centrality is dened as:

C(u) = 1 v∈V d(u, v) (2)
The node with the maximum closeness centrality is a geographically central node. This position gives the node a relative advantage for easily communicating with all the other nodes in the network, making it seem the most adequate for the Local EPC placement. However, the limited link capacities leading to this central node could limit the amount of trac it is capable of receiving.

The betweenness centrality of a node quanties the number of times a node belongs to the shortest path between two other nodes [START_REF] Freeman | A Set of Measures of Centrality Based on Betweenness[END_REF]. Let α(v, w) be the total number of shortest paths from node v to node w, and β(u, v, w) the number of those paths that pass through node u, then the betweenness centrality of a node u is dened as:

B(u) = v,w∈V β(u, v, w) α(v, w) (3)
The node with the maximum betweenness centrality can be seen as an anchor node, well placed for forwarding communications between the nodes.

However, once again, the limitation of this centrality, in our case, resides in the fact that link capacities around the node with the maximum betweenness centrality may limit its ability to forward trac.

In this paper, we further highlight the inadequacy of these centrality measures for the Local EPC placement. We show in Sec. 7 how placing the Local EPC on a node maximizing one of these centralities notably reduces the amount of trac the Local EPC is capable of receiving.

Placement Problems in Wireless Networks

The placement problem appears in literature under dierent forms. Notably, the gateway placement problem in wireless networks is the most relevant to our work. There have been numerous studies addressing this problem in multi-hop wireless networks [START_REF] Wong | Gateway Placement for Latency and Energy Ecient Data Aggregation[END_REF][START_REF] Qiu | Optimizing the Placement of Integration Points in Multi-hop Wireless Networks[END_REF], and specically in wireless mesh networks [START_REF] Muthaiah | Single Gateway Placement in Wireless Mesh Networks[END_REF][START_REF] Aoun | Gateway Placement Optimization in Wireless Mesh Networks with QoS Constraints[END_REF]. As opposed to our work, where only the placement of one

Local EPC is needed in the network, several gateways can be placed in a wireless mesh network. Usually, the main objective is to minimize the number of deployed gateways, while optimizing their placement, under dierent quality of service (QoS) constraints, such as: guaranteeing nodes bandwidth requirements [START_REF] Aoun | Gateway Placement Optimization in Wireless Mesh Networks with QoS Constraints[END_REF][START_REF] Qiu | Optimizing the Placement of Integration Points in Multi-hop Wireless Networks[END_REF], and ensuring delay constraints [START_REF] Aoun | Gateway Placement Optimization in Wireless Mesh Networks with QoS Constraints[END_REF][START_REF] Wong | Gateway Placement for Latency and Energy Ecient Data Aggregation[END_REF]. Furthermore, Muthaiah et al. [START_REF] Muthaiah | Single Gateway Placement in Wireless Mesh Networks[END_REF] studied optimizing a single gateway placement in a wireless mesh network, with the aim of maximizing the minimum network throughput. They proposed a heuristic, hereafter referred to as the weighted path heuristic, using a shortest path algorithm to compute the minimum weighted path from any node to one destination node. In their heuristic, a link weight represents the likelihood of transmission failure on that link. Then, the gateway is placed on the destination node that minimizes the sum of the weights of all the shortest paths from all the nodes to that destination. We further adapt the weighted path heuristic to our model, and compare it in Sec. 7 to our proposed metric, along with the other centrality metrics.

Another placement problem deals with placing the sink in a wireless sensor network (WSN) [START_REF] Das | Multiple-sink Placement Strategies in Wireless Sensor Networks[END_REF]. An analogy could be made between the sink, re- Finally, with the evolution of the network functions virtualization for network services deployment and management, several works tackled the placement of virtualized network functions (VNF) in a network [START_REF] Bouet | Cost-based Placement of vDPI Functions in NFV Infrastructures[END_REF]. Similarly to the Local EPC placement, all the ows in the network might be required to pass through a certain network function. Bouet et al. [START_REF] Bouet | Cost-based Placement of vDPI Functions in NFV Infrastructures[END_REF] formulated the VNF placement problem as a cost minimization problem, and proposed an adapted centrality measure derived from the betweenness centrality. However, their approach was on a per-ow basis, placing the VNF as a middlepoint between a source node and a destination. Conversely, we consider in our work the overall trac of a source node, encompassing all of the ows, with the Local EPC as an endpoint.

ceiving

Network Model

We consider a self-deployable network consisting of BSs having no backhaul connectivity to a traditional EPC. All these BSs must access a Local EPC in order to be able to serve users. There is a single Local EPC in the network, and it is co-located with one of the BSs. A Local EPC provides the same functionalities as the traditional EPC, supports bearer services, and houses the application servers. In case a BS is not co-located with, nor can reach a Local EPC instance, it cannot serve users. We consider that the BSs are interconnected, meaning two BSs can be directly connected via a link.

As the local EPC is co-located with one of the BSs, the inter-BS links are referred to as backhaul links, since they will be responsible of forwarding The design of inter-BS links is out of the scope of this paper. Without loss of generality, we consider that, regardless of the used wireless technology, there is no contention between the inter-BS backhaul links for resource utilization. We assume that interfering wireless links are operating on distinct channels, allowing parallel transmissions on the dierent links, with no interference [START_REF] Aoun | Gateway Placement Optimization in Wireless Mesh Networks with QoS Constraints[END_REF]. We suppose that the backhaul bandwidth is limited, meaning the amount of trac that can be routed on these links, from both data ows and signaling messages, is limited.

Mathematical Notation

Let G(V, E) be an undirected graph modeling the network, with |V | = n nodes, and |E| = m edges. Each BS is a node of the graph, and the inter-BS links are the graph edges. The BS co-located with the Local EPC serving the network, denoted by d, is considered as the destination node in the graph, while all the other BSs in the network are sources. Let S, T ⊆ V be the set of sources and destinations of G, respectively. In this case, we have S = V \ {d}, and T = {d}. To model the inter-BS links with limited bandwidth, we consider graph edges with limited capacities. The capacity of an edge c : E → R + represents the maximum amount of trac that can pass through that edge (in units of trac). We denote by c(u, v) the capacity of the edge (u, v) ∈ E. The ow f through this edge, such as f :

E → R + , is denoted by f (u, v).

Local EPC Placement Criteria

In a mobile network, the EPC must be able to handle the entire user trac, meaning it must be able to receive (resp. transmit) all the data and signaling trac generated by (resp. destined to) the BS. Hence, the local EPC placement in a self-deployable network depends on the amount of trac routed in the network, which in turn depends on the number of users to be served, or the number of user requests. Trac is aggregated and forwarded by intermediate BSs towards the Local EPC. We assume that BSs do not have capacity constraints. The limited link capacities set a threshold on the amount of trac that can be transported. In this case, the load of the congested inter-BS links is upper bounded by their respective limited capacities, creating a bottleneck. Consequently, the placement of the Local EPC must take into consideration the links between the BSs, their capacity, and their quality, in order to ensure that all user trac can circulate in the network without losses.

On the other hand, the number of users in the network and their requests are dynamic. Hence, the optimal position of the Local EPC might change depending on the trac of each BS. Since such information may not be available at the early deployment phase, we propose to place the Local EPC at rst in a general way, allowing us to cover the largest number of scenarios.

Once deployed and operational, a migration of the Local EPC could be envisaged in order to adapt to network dynamicity. This, however, is out of the scope of this paper. We treat all BSs as equals, and uniformly maximize the amount of trac they can send. We suppose that each BS in the network can send an amount of trac z(v, d) = λ(d) towards the Local EPC co-located with node d, and we recommend placing the Local EPC in such a way that λ(d) is maximized. This maximizes the possible amount of trac that all BSs are capable of forwarding to the Local EPC simultaneously, while respecting the limited link capacities.

Flow Centrality

We propose ow centrality as a novel centrality metric measuring the capacity of a node in receiving the total amount of ows in the graph. The ow centrality of a node is represented by the maximum trac that can be generated by all the other nodes in the graph, and directed towards this node if it were the only destination. To compute the ow centrality of node d, it is sucient to compute the maximum amount of trac that node d can receive from all the other nodes in the graph if it were the unique destination node.

The total amount of ows received at destination node d must be equal to the total ows sent by all the sources. As each node v ∈ V has a supply z(v, d) = λ(d) to send towards d, then the total ow value received at node d is:

|f | d = v∈S z(v, d) = (n -1) • λ(d) (4)
We denote by λ(d) the maximum achievable value of λ(d). When the supply λ(d) is maximized, the total ow received at d is maximum, such that:

|f | dmax = (n -1) • λ(d) (5)
Eventually, the ow centrality of a node d is dened as λ(d). The maximum ow centrality is then expressed as:

λ max = max d∈V λ(d) (6)
Practically, this new metric distinguishes the node that, when set as destination, is capable of receiving the largest amount of ows, equally from all the other nodes, in comparison to when other nodes are set as destination. Hence, in order to better serve the network, the Local EPC must be co-located with the BS having the maximum ow centrality.

Computing Flow Centrality

To compute the ow centrality of a node d, we rst suppose that node d is the unique destination of the graph, and all the other nodes are sources that can send the same amount of trac λ(d) towards node d. As stated previously, the ow centrality of a node d is dened as λ(d), the maximum achievable value of λ(d).

Linear Optimization Problem

One way to compute the ow centrality of a node, λ(d), is through a linear optimization problem. The objective is to maximize λ(d) (Eq. 7), subject to the following constraints:

• the xed supply constraint, where all sources in the graph have a xed supply equal to λ(d) (Eq. 8);

• the link capacity constraint, where the ow on each edge in the graph must not surpass the edge capacity (Eq. 9);

• the ow conservation constraint, where the ow entering a node must be equal to the ow exiting a node (Eq. 10);

• the supply constraint, where the total ow value received at the destination node is equal to the sum of all the supplies of the sources (Eq. 11).

The problem is formulated as follows:

Maximize:

λ(d)∈[0,∞) λ(d) (7) subject to z(v, d) = λ(d), ∀ v ∈ S (8) f (u, v) ≤ c(u, v), ∀ (u, v) ∈ E (9) u∈S f (u, v) = w∈S f (v, w), ∀ v ∈ S ( 10
) v∈V f (v, d) = (n -1) • λ(d) (11)
After computing the ow centrality of each of the nodes, the node d * with the maximum ow centrality is the node for which the supply λ(d) that can be generated by all the other nodes in the graph is maximum, such that:

d * = arg max d∈V λ(d) (12)

Finding Minimum Cut Value

Another approach to computing the ow centrality of a node is through the minimum cut problem, i.e., nding the cut of minimum value that separates the node from the others, as detailed in the following. A cut in the graph is a partition of the graph nodes into two non-empty disjoint subsets, joined by at least one edge.

We denote by C = (A, B) a cut that partitions V into 2 subsets A, B ⊂ V , such that d ∈ B. We dene the size of a cut as |C| = |A|, i.e., the number of nodes in the subset not containing the destination. We dene the capacity of a cut, γ(C), as the sum of the capacities of the edges traversed by that cut, such that:

γ(C) = (u,v)∈E:u∈A,v∈B c(u, v) (13)
We dene the trac of a cut, τ (C), as the sum of the trac sent by nodes v ∈ A towards the destination node d ∈ B, such that:

τ (C) = v∈A z(v, d) = λ(d) • |C| (14)
The capacity of a cut γ(C) must be able to support the trac of a cut τ (C), hence:

γ(C) ≥ τ (C) (15)
Which leads to:

λ(d) ≤ γ(C) |C| (16)
We dene the cut value as the ratio between the capacity of a cut and its trac γ(C) |C| .

Finding λ(d) is equivalent to nding the cut C = (A, B), with the minimum cut value. Therefore:

λ(d) = min C γ(C) |C| (17)
In this case, the node with the maximum ow centrality d * is the node such that:

d * = arg max d∈V min C γ(C) |C| (18)

Flow Centrality in Canonical Topologies

As previously detailed in Sec. 4.3, computing the ow centrality of a node in the graph requires solving a linear optimization problem, or nding a minimum cut. In this section, we show how in some graphs, such as path graphs and balanced trees, some properties emerge, allowing the computation of the ow centrality of a node via analytical expressions.

Path Graph

A path graph is a trail of distinct nodes (Fig. 2). It is a sequence of n nodes, denoted by v 0 , v 1 , ..., v n-1 . Two adjacent nodes, v i and v i+1 , are linked with an edge of capacity

c i = c(v i , v i+1 ) ∀ i ∈ [0, n -2].
We consider that link capacities follow a certain distribution, such that c i ∈ [c min , c max ]. In a path graph, a node v i has i nodes to its left, and n -i -1 nodes to its right. The ow centrality of a node v i on the path is equal to the maximum trac λ(v i ) that can be generated by all the other nodes on the path, and directed towards this node. For a node v i = v 0 , each node v k to the left of node v i , such that k ∈ [0, i -1], has a trac λ(v i ) to send towards v i . Consequently, each edge (v k , v k+1 ) of capacity c k is responsible of forwarding the totality of the trac generated by the k + 1 nodes on its left towards node v k . Thus, the total trac generated by the k + 1 nodes arriving at each edge (v k , v k+1 ) is upperbounded by the limited capacity c k of that edge, such that:

c 0 c 1 c n-3 c n-2 v 0 v 1 v 2 v n-3 v n-2 v n-1 v i i nodes n-1-i nodes λ(v i ) λ(v i ) λ(v i ) λ(v i ) λ(v i ) λ(v i )
λ(v i ) ≤ c k k + 1 , ∀ k ∈ [0, i -1] (19)
Similarly, for a node v i = v n-1 , each node v j to the right of node v i , such that j ∈ [i + 1, n -1], has a trac λ(v i ) to send towards v i . Consequently, each edge (v j-1 , v j ) of capacity c j-1 is responsible of forwarding the totality of the trac generated by the n-j nodes on its right towards node v j . Thus, the total trac generated by the n -j nodes arriving at each edge (v j-1 , v j ) is upper-bounded by the limited capacity c j-1 of that edge, such that:

λ(v i ) ≤ c j-1 n -j , ∀ j ∈ [i + 1, n -1] (20)
Since both expressions in Eq. 19 and Eq. 20 upper bounding λ(v i ) must be veried, the ow centrality of a node v i , i.e., the maximum value of λ(v i ), is:

λ(v i ) =          min j∈[1,n-1] c j-1 n-j if i = 0 min k∈[0,i-1] j∈[i+1,n-1] c k k+1 , c j-1 n-j if 0 < i < n -1 min k∈[0,n-2] c k k+1 if i = n -1 (21)

Uniform Capacities

We consider now the particular case where links in the path graph have uniform capacities, i.e., c(v i , v i+1 ) = c , ∀ i ∈ [0, n -2]. Based on Eq. 21, we get:

λ(v i ) = min k∈[0,i-1] j∈[i+1,n-1] c k + 1 , c n -j = min c, c 2 , ..., c i , c n -i -1 , c n -i -2 , ..., c 2 , c = min c i , c n -i -1 (22)
From Eq. 22, we can deduce that, in a path graph with uniform capacities, the node(s) at the center of the path is (are) always the node(s) with maximum ow centrality. When the number of nodes is odd, i.e., n = 2x + 1, the maximum value of λ(v i ) is achieved for i = x. Thus, the node with the maximum ow centrality is node v x . When the number of nodes is even, i.e., n = 2x, the maximum value of λ(v i ) is achieved for i = x-1 and i = x. Thus, two nodes have the maximum ow centrality: v x-1 and v x , respectively. In both cases, the maximum ow centrality is:

λ max = c x (23)

Balanced Tree

A balanced tree is a rooted tree having all its leaves at a distance h from the root. The left and right subtrees of any node have the same height. In a tree with a branching factor r, all nodes, except the leaves, are branched into r subtrees. All the nodes have a degree r + 1, except the root which has a degree r, and the leaves which have a degree 1. Fig. 3 shows an example of a balanced tree of height h = 4 and a branching factor r = 2. Let i be the depth of a node within the tree, such that i ∈ [0, h -1]. The node at depth i = 0 is the root, and nodes at depth i = h -1 are the leaves. At each depth i ∈ [0, h -1], there are r i nodes, denoted by v ij , such that j ∈ [0, r i -1]. Each node v ij is linked to its parent via a single link, of capacity c i-1,j . The number of descendants of a node at depth i, denoted by des(i), is:

des(i) = 0 if i = h -1 h-1-i k=1 r k if 0 ≤ i < h -1 (24)
If we suppose that all nodes in a tree have trac to forward towards one destination node, then each link exiting at a node must be able to forward the total trac aggregated by this node, i.e., its trac and the trac of all its descendants. Let us consider the example shown in Fig. 4 of a node v ij at a depth i, in a balanced tree of branching factor r. The node v ij is branched into r symmetrical subtrees, and has des(i) descendants in total (Eq. 24), divided equally among the subtrees. Thus, each subtree has des(i) r nodes. Each link with a capacity c i,k exiting one of the subtrees and going towards v ij is responsible of forwarding the total trac of all the nodes in that subtree. If we denote by λ the trac of each node, then the following expression must be veried:

λ ≤ r • c(i, k) des(i) , ∀ k ∈ [r • j, r(j + 1) -1] (25)
In the following, we formulate analytical expressions to compute the ow centrality of nodes in a balanced tree of height h and branching factor r. The ow centrality value of a node depends on the depth i at which the node is within the tree. As an illustrative example, we consider the balanced tree with height h = 4 and branching factor r = 2, shown in Fig. 3. A rst step in ow centrality computation of a node v ij is to consider that this node is the unique destination in the tree. In the following, we rst explain the analytical expressions of the ow centrality of nodes at depths i = 0 and i = 1, before deducing the general expression for a node at depth i.

Node at depth i = 0

When computing the ow centrality of the root v 00 at depth i = 0, all the nodes in the tree, except the leaves, are branched into r symmetrical subtrees, and match the case shown in Fig. 4. Consequently, the expression in Eq. 25 applies to all the links in the tree, such that:

λ ≤ r c i,k des(i) , ∀ i ∈ [0, h -2] , ∀ k ∈ [0, r i+1 -1] (26)
From Eq. 26, we deduce that the ow centrality of node v 00 is:

λ(v 00 ) = min i∈[0,h-2] k∈[0,r i+1 -1] r c i,k des(i) (27)

Node at depth i = 1

We compute in the following the ow centrality of nodes at depth i = 1. As an example, we rst compute the ow centrality of node v 10 . We that v 10 is the unique destination node in the tree. Fig. 5 shows the corresponding tree structure. In this case, node v 10 is branched into r + 1 subtrees:

• r balanced subtrees that encompass all the descendants of v 10 (in the original tree), whose number is equal to des(1). Each of the subtrees has des(1) r nodes.

• One subtree, denoted X (see Fig. 5), that encompasses v 00 and all its descendants (in the original tree), except the subtree started by v 10 . Thus, the number of nodes in X is n -des(0) r . X is linked to v 10 via a link of capacity c 00 . This link is responsible of forwarding the total trac of all the nodes in X . If we denote by λ the trac forwarded by each node, then the following expression must be veried:

λ ≤ c 00 n -des(0) r (28)
All the nodes in the tree in Fig. 5, except v 00 , v 10 and the leaves, are branched into r symmetrical subtrees, and match the case shown in Fig. 4 Consequently, the expression in Eq. 25 applies to all of the links in the tree except c 00 . Following the same reasoning as Eq. 25, we deduce:

λ ≤ r c i,k des(i) , ∀ i ∈ [0, h -2] , ∀ k ∈ [0, r i+1 -1], (i, k) = (0, 0) (29)
From Eq. 28 and Eq. 29, we deduce that the ow centrality of node v 10 is:

λ(v 10 ) = min i∈[0,h-2] k∈[0,ri+1-1] (i,k) =(0,0) c 0,0 n -des(0) r , r c i,k des(i) (30)
This could be generalized to all nodes v 1j at depth i = 1, with j ∈ [0, r -1]. The ow centrality of node v 1j is:

λ(v 1j ) = min i∈[0,h-2] k∈[0,r i+1 -1] (i,k) =(0,j) c 0,j n -des(0) r , r c i,k des(i) , ∀ j ∈ [0, r -1] (31)

General case, at depth i

To generalize, we follow the same reasoning at each depth i ∈ [1, h -1]. We dene E[x] as the function that gives the integer part of x. x as the oor function that gives the greatest integer less than or equal to x. To compute the ow centrality of a node v ij at depth i, this node is considered as unique destination. All the nodes in the tree, except those lying on the path between v ij and the original root v 00 are branched into r symmetrical subtrees, and match the case shown in Fig. 4. Consequently, the expression in Eq. 25 applies to all of the links in the tree except the following links that are on the path between v ij and the original root v 00 :

(0, j r i-1 ), (1, j r i-2 ), ...,

(i -2, j r ), (i -1, j) . Let w(k) = j r i-1-k . Each link (k, w (k)) is responsible of forwarding the total trac of n -des(k) r nodes.
Eventually, the ow centrality of a node v ij is:

λ(v ij ) = min p∈[0,h-2] q∈[0,r p+1 -1] k∈[0,i-1] (p,q) =(k,w(k)) c k,w(k) n -des(k) r , r c p,q des(p) , ∀ i ∈ [1, h -1] , ∀ j ∈ [0, r i -1] (32)

Uniform Capacities

We consider now the particular case where all links in the tree have uniform capacities. In this case, the ow centrality values of nodes at the same depth are identical. We consider at rst the node v 00 . Since des(0

) > des(k), ∀ k ∈ [1, h -2],
we deduce from Eq. 27:

λ(v 00 ) = r c des(0) = r c n -1 . (33) For nodes v ij ,∀ i ∈ [1, h -1] , ∀ j ∈ [0, r i -1], the ow centrality is: λ(v ij ) = min p∈[0,h-2] k∈[0,i-1] c n -des(k) r , r c des(p) = c n -des(i-1) r (34) However, r c n-1 > c n- des(i-1) r , ∀ i ∈ [1, h -2].
Consequently, the maximum ow centrality is:

λ max = max i∈[0,h-1] λ(v ij ) = λ(v 00 ) = r c n -1 (35)
Thus, the root v 00 of a balanced tree with uniform capacities is the node with the maximum ow centrality.

Flow Centrality Properties

After detailing the computation methods of the ow centrality metric, we provide in this section some insights on its properties. We rst consider a random network topology of 10 BSs, and show a numerical example of ow centrality computation, leading to the Local EPC placement in the network.

Then, by varying the inter-BS backhaul links properties, i.e, the link capacities distribution, the average link capacity, and the link capacities range, we deduce several properties on the dependence between the backhaul network, the ow centrality values, and the position of the node with the maximum ow centrality. Note that further evaluation of the proposed ow centrality metric, and a comparison with state the art centrality metrics will follow in Sec. 7.

A Numerical Example

Let us consider now a common example of a network topology, with BSs served by a Local EPC. We represent in Fig. 6 the network by a random geometric graph with 10 nodes, such that two nodes are connected by a link if and only if their distance is smaller than a certain radius η. In this example, we consider a surface of one unit square, with a network radius η = 0.2, and randomly distributed link capacities such that c ∈ [0, 100] (in units of trac). A null capacity c = 0 means that the link is not usable. Fig. 7 shows the computed ow centrality value λ(d) of each node d of the network. The ow centrality of each node d represents the amount of trac each of the other nodes can send simultaneously if the Local EPC is co-located with node d. We compute the ow centrality value of each node by solving the linear optimization problem in Sec. 4.3 (Eq. 7-Eq. 11), using the CPLEX software package [START_REF]IBM ILOG CPLEX Optimization Studio V12.7.0 Documentation[END_REF]. Results show that node 2 has the maximum ow centrality, hence λ max = λ(2). This means that the Local EPC in this network must be co-located with node 2. Indeed, if the Local EPC was colocated with node 1, for example, it would be able to support only half the amount of trac supported when co-locating it with node 2.

For this network with a relatively small number of nodes, the computation time is in the order of milliseconds. This small number of nodes correspond to the nature of such networks, where only a few BSs are needed. Nevertheless, it should be noted that, with the increase of the number of nodes, the computation time increases accordingly, but remains in the order of seconds even for networks with 100 nodes. Larger scale networks are further studied in Sec. 7.2.1.

Max Flow Centrality

Max Degree, Weighted Degree, Closeness, Betweenness Centrality

Link Capacities Distribution

Depending on the link capacities distribution, the ow centrality value and the node with the maximum ow centrality do not remain the same, even for the same topology.

We show in Fig. 6 the values of the ows routed on each link, in comparison with the maximum link capacity, when the Local EPC is placed at node 2, and each node sends a trac equal to λ max towards the Local EPC. We can notice that, while some links are saturated, others are under-used.

The saturated links are the ones that play a major role in upper bounding the value of λ max . In Fig. 6, these are the links (9, 3), (5, 2), [START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF][START_REF] Valcarce | Airborne Base Stations for Emergency and Temporary Events[END_REF] and [START_REF] Valcarce | Airborne Base Stations for Emergency and Temporary Events[END_REF][START_REF] Sesia | LTE -the UMTS Long Term Evolution[END_REF].

For this specic topology, and this specic capacity distribution, those are the links that control the value of λ max . We observe that by increasing (decreasing) the capacity of those links, the value of λ max increases (decreases) respectively.

Other links, such as (0, 6) and (0, 2), which are only responsible of delivering the ow of node 0, have enough capacity in this case to not upper bound the value of λ max . We should note that, since node 0 is directly linked to node 2 co-located with the Local EPC, it is practically capable of forwarding more trac than λ max , without aecting the other nodes trac, since c(0, 2) allows it.

On the other hand, link (8, 9), for example, is not used at all. Removing this link would not aect the position of the node with the maximum ow centrality, nor its value. The capacity of link (1,[START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF], which is only used to route trac from node 1, is under-used. However, increasing the trac of node 1 renders the total ow unfeasible, due to other saturated links leading to destination node. Moreover, due to the position of node 1 in the network, increasing the capacity of link (1,[START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF] would not have any eect on the value of the maximum ow centrality. Therefore, even for the same network topology, the nodes ow centrality values and the position of the node with the maximum ow centrality are impacted by the link capacities distribution.

Link Capacities Average

From the previous results, we know that the value of the ow centrality of a node d, λ(d), is signicantly aected by the links capacities. In fact, as shown in Sec. 4.2, and illustrated in the previous example, the value of λ(d) of a node d is dictated by the capacity of most of the links leading to that node, as well as by the capacity of all the links in the graph. We further show in this section that there exists a proportional relation between the link capacities and the maximum ow centrality value.

We consider a sample of random geometric graphs of radius η, with uniform link capacities distribution such that c(u, v) ∈ [c min , c max ]. We denote by c avg the average link capacity, such that c avg = c min +cmax 2 , and by ∆c the capacity range, such that ∆c = c max -c min . To highlight the existing relation between the maximum ow centrality λ max and the link capacities, we show in Fig. 8 the average value of λ max function of the average link capacity c avg . We vary the values of c avg , but keep a constant interval ∆c. We show this variation for dierent values of the graph radius η. We remind that the more η increases, the higher the number of links is in the network.

Results show that the average value of lambda max increases almost linearly with c avg . For η = 1, where almost all pairs of nodes are connected, the value of λ max is approximately equal to c avg . This suggests that the value of the maximum ow centrality is upper bounded by the average link capacity. Moreover, as the radius η decreases, the number of edges decreases, and the value of λ max decreases accordingly.

Indeed, for the same value of c avg , the less there are links in the network, the less trac can circulate. Furthermore, the linear relation between c avg and λ max comes in accordance with the analytical expressions obtained in Sec. 5 that show a linear relation between the maximum ow centrality and the link capacities.

Link Capacities Range

We observe now the variation of λ max function of c avg , for dierent values of capacity intervals ∆c. Fig. 8a and Fig. 8b correspond to two constant capacity intervals, ∆c = 5 and ∆c = 10, respectively. We notice that the value of λ max and its variation depending on c avg are very similar in both cases. Thus, while the value of λ max depends on the average link capacity, the capacity range is practically irrelevant for λ max .

However, we show in the following that the capacity range does have an impact on the position of the node that achieves λ max . Indeed, let us consider the same topology as in Fig. 6, but with a capacity range ∆c = 0, i.e., with uniform link capacities c. In Fig. 9, we x link capacities to c = 50, which is equal to the average link capacity in Fig. 6. Unlike Fig. 6, nodes 2, 6, 8, and 9 have the maximum ow centrality. Selecting any of these nodes as destination would only change the ow distribution on the links. For ∆c = 0, only the maximum ow centrality value is dependent on the numerical value of c in graphs with uniform links. However, the network characteristics are the same independently of the value of c. The ow distribution illustrated in Fig. 9

λ (u) = λ max -λ(u) λ max (36)
We consider two types of graphs (grid and random geometric), modeling dierent network topologies, with random link capacities. We x the average link capacity c avg to a constant value, and vary the capacity range ∆c. In the following, all the results are averaged on samples of 100 randomly generated graphs, with condence intervals at 95%.

Grid Graphs

In a grid graph, the node at the center of the grid has the maximum degree, closeness, and betweenness centrality, independently of the link capacities. When the link capacities are uniform, the center node is also the node with the maximum weighted degree. Nevertheless, when links in the graph have dierent capacities, any node can have the maximum weighted degree, depending on the link capacities distribution.

In the following, we consider grid graphs with n = x × y nodes. We investigate grids such that n = {2 × 5, 3 × 3, 3 × 4, 4 × 4}, with random link capacities c ∈ [c min , c max ], and a constant average capacity c avg = 50. Upper and lower bounds of c are determined by the range capacity ∆c, such that ∆c = {0, 10, 40, 100}. Since, in this topology, the node having the maximum closeness centrality is identical to the one with the maximum degree and betweenness centrality, the shown results corresponding to the closeness centrality are the same for the other two centralities. Fig. 10a shows, for dierent grid dimensions, the percentage of cases where the node with maximum ow centrality is identical to the node with the maximum closeness centrality, on one side, and to the node with the maximum weighted degree centrality, on the other. Similarly, Fig. 10b shows this matching percentage between the node maximizing the ow centrality, and the node selected by the weighted path heuristic. It is clear in Fig. 10, that for ∆c = 0 (when link capacities are uniform), the matching percentage is 100%. This means that the node with the maximum ow centrality is identical to the node which maximizes both closeness and weighted degree centralities, as well as the node selected by the weighted path heuristic, i.e., the node central to the grid. However, if links in the graph have dierent capacities, i.e., ∆c = 0, then these nodes are not necessarily identical. The central node, having the maximum closeness centrality, does not necessarily have the maximum weighted degree centrality, due to the random link capacities. On the other hand, having the maximum weighted degree centrality does not necessarily mean that the node is capable of receiving the maximum amount of trac from all the other nodes. Moreover, we notice, in some cases, changes in the value of the matching percentage for dierent values of ∆c. This is in accordance with the observation in Sec. 6, where we showed that ∆c aects the position of the node with the maximum ow centrality. Fig. 10a shows that it is more likely for the node with the maximum ow centrality to be identical to the node with the maximum weighted degree, than to the one with maximum closeness centrality. This is notably the case as the grid dimension increases. These conclusions are rather consistent for the dierent grid dimensions. From Fig. 10b, we can deduce that, in most cases, the weighted path heuristic rarely selects the same node as the one with the maximum ow centrality. This is however not true for the particular 3 × 3 grid with smaller values of ∆c.

For a better comparison of the ow centrality to the other metrics, we compute the relative trac loss λ (Eq. 36), if the Local EPC was placed on the node with the maximum closeness centrality, or on the node with the maximum weighted degree centrality, or the one selected by the weighted path heuristic. The results in Fig. 11 show that the relative loss is important, with an average value ranging between 35% and 55%, for both centralities, and for the weighted path. Interestingly, even tough the node with the maximum weighted degree had higher matching percentages with the one maximizing the ow centrality, the relative loss when the two nodes are dierent is slightly higher than the loss corresponding to the closeness centrality.

Random Geometric Graphs

We consider now the case of random geometric graphs with 10 nodes, on a total surface of one unit square, and a radius η = 0.2. We vary the link capacities such that ∆c = {0, 10, 40, 100}, with a constant average capacity c avg = 50.

Following an extensive study of dierent topologies, with dierent link capacities distribution, some guidelines emerge on the distinction between the maximum ow centrality and the other centrality metrics. Indeed, nodes at the network edges, usually linked to fewer nodes than the others, have lower ow centrality values due to their isolated position. Such links are not central, nor have the maximum ow centrality. On the other hand, a node having a central position, i.e., maximizing the closeness centrality, or well served by links, i.e., maximizing the weighted degree, but that has one (or more) link(s) used only by a single node, cannot be the node with the maximum ow centrality. This can be seen in the example shown in Fig. 6, where we identify node 7 as the node having the maximum weighted degree centrality, the maximum betweenness centrality, the maximum closeness centrality, and the maximum degree centrality, simultaneously. It is also the node selected by the weighted path heuristic. However, having the link (1,[START_REF] Oueis | Overview on LTE Isolated E-UTRAN Operation for Public Safety[END_REF] of relatively high capacity only used by node 1 prevents this node from having the maximum ow centrality. In this example, it is node 2 that has the maximum ow centrality and not node 7. Placing the Local EPC on node 7 instead of node 2 would cause a signicant relative trac loss, such that λ (7) = 41%.

To generalize, we show in Fig. 12 the percentage of generated topologies where the node with maximum ow centrality is identical to the nodes maximizing the other centrality metrics, or to the node selected by the weighted path heuristic. We notice that, unlike grid graphs, even with uniform link capacities, i.e., ∆c = 0, the node with the maximum ow centrality can be dierent from the nodes that maximize the other centralities. On the other hand, when link capacities are randomly distributed, results in Fig. 12 show that, for all values of ∆c, the closeness centrality is the closest to the ow centrality in terms of matching percentage. For example, for ∆c = 100, the node with maximum ow centrality matches the node with the maximum closeness centrality in 95% of the cases. Regarding the weighted path heuristic, Fig. 12 shows that, in most cases, the selected node for EPC placement is identical to the node maximizing the ow centrality. For example, the matching percentage reaches 94% for ∆c = 0.

However, even when the matching percentage is high, what validates if a metric is a good substitute of the maximum ow centrality, is the trac loss that occurs when a node, determined by that metric, is selected for the Local EPC placement instead of the one maximizing the ow centrality. In Fig. 13, we show this relative trac loss λ (Eq. 36) when the Local EPC is not placed on the node with the maximum ow centrality. Indeed, even though nodes with maximum closeness centrality had the highest matching percentage with the nodes with maximum ow centrality, results show that the average trac loss incurred when these nodes are dierent is relatively high. Fig. 13 shows that placing the Local EPC on the node with the maximum closeness centrality instead of the node with the maximum ow centrality would cause a relative trac loss of 46.5%, which is the highest loss in comparison with the other centrality measures. On the other hand, the relative losses incurred by the other centrality measures are lower, but still important, around 30% on average. Likewise, the relative trac loss incurred by placing the Local EPC on the node selected by the weighted path heuristic reaches an average of 32%. This further highlights the advantages of placing the Local EPC on the node with the maximum ow centrality, as the trac loss occurring otherwise is signicant.

Larger scale networks

Until now, we limited our study to smaller networks corresponding to our specic use case of self deployable networks, where only few BSs are needed.

In order to thoroughly study the ow centrality metric and distinguish it from other centralities, we vary in the following the number of nodes in the network. We observe in Fig. 14 the matching percentage between the node with the maximum ow centrality and the nodes maximizing other centrality metrics, function of the number of nodes n.

We notice, in Fig. 14, that for all metrics, except the weighted degree centrality, the matching percentage decreases with the increase of the number of nodes. For larger values of n, this matching percentage is negligible.

Conversely, the matching percentage is conserved for the weighted degree centrality, even with the increase of n. In Fig. 15, we show the average trac loss occurring when the Local EPC is placed on the node maximizing one of the other metrics, instead of the ow centrality. As n increases, the average trac loss increases accordingly. Indeed, with the increase of n, it is more likely for the two nodes to be dierent (Fig. 14), having dierent inherent properties. This further distinguishes the node with the maximum 33 ow centrality by its ability to receive the maximum ow in the network, as opposed to the other metrics.

Conclusion

In this paper, we studied the placement of a Local EPC in a self-deployable network consisting of BSs having no backhaul connectivity to a traditional core network. We dened ow centrality, a novel centrality metric that measures a node capacity of receiving the total ow in the network. We showed that co-locating the Local EPC with the BS having the maximum ow centrality maximizes the total amount of trac that the Local EPC is capable of receiving simultaneously from all the BSs. We presented a detailed analytical study on dierent ow centrality computation methods, in dierent graph topologies. We further highlighted the existing dependencies between the ow centrality metric and the backhaul network properties (i.e., the limited backhaul link capacities), notably aecting the position of the node with the maximum ow centrality. We compared the ow centrality to other state of the art centrality metrics, and highlighted the loss incurred when the Local EPC is not placed on the node with the maximum ow centrality. We showed that in some cases, this relative trac loss can be as high as 55%.

  Consequently, the Local EPC placement problem arises, questioning where should the Local EPC be placed in the network. In other words, with which of the BSs must the Local EPC be co-located. Since the BSs are interconnected and the local EPC is co-located with one of them, all trac (e.g., data and signaling), usually exchanged between each BS and the standalone core network, is now routed locally on the links interconnecting the BSs. Hence, those inter-BS links form the backhaul network of the system. Being set up in an ad-hoc manner, and potentially having a limited bandwidth (i.e., limited link capacities), this backhaul network can represent a bottleneck by limiting the amount of trac that can be exchanged between the BS and the Local EPC. The limited backhaul bandwidth plays an essential role in determining where the Local EPC should be placed. In this work, we tackle the Local EPC placement problem in a selfdeployable mobile network. The contributions of this paper are threefold.

Figure 1 :

 1 Figure 1: An example of a self-deployable network topology, comprising 10 interconnected BSs, with a Local EPC co-located with one BS.

  All data and signaling trac from a BS is forwarded to the Local EPC. Hence, all the BSs in the network have a certain amount of trac to route on the backhaul links connecting them to the Local EPC. To model this trac, we dene the supply function z : S × T → R + , such that z(v, d) is the ow that a source node v ∈ S sends towards the destination d.

  4. Flow Centrality: A Metric For Local EPC PlacementAs one of the BSs must be co-located with a Local EPC serving the other BSs in the network, the Local EPC placement problem questions with which of the BSs must the Local EPC be co-located. In this section, we rst list the key Local EPC placement criteria in a self-deployable mobile network. In order to meet those criteria, we propose a novel centrality metric in a network, called ow centrality, such that a Local EPC is placed on the node having the maximum ow centrality. Then, we formulate in details the dierent computation methods for this ow centrality metric.

Figure 2 :

 2 Figure 2: Path graph with n nodes.

Figure 3 :

 3 Figure 3: A balanced tree rooted at v 00 , with height h = 4 and branching factor r = 2.

1 Figure 4 :

 14 Figure4: A node v ij at depth i within a balanced tree, branched into r symmetrical subtrees, each having a height h -i -1, and comprising des(i)/r nodes.

27 XFigure 5 :

 275 Figure 5: Tree structure with node v 10 set as unique destination in the tree for ow centrality computation.

Figure 6 :

 6 Figure 6: A random geometric graph topology, with random link capacities c ∈ [0, 100]. All nodes transmit λ max = 18 units of trac towards the Local EPC co-located with node 2. The values on the links represent f (u, v)/c(u, v).

Figure 7 :

 7 Figure 7: The ow centrality values of the network nodes corresponding to the topology in Fig. 6.

Figure 8 :

 8 Figure 8: Variation of the average maximum ow centrality λ max function of the average link capacity c avg , in random geometric graphs, for dierent values of the radius r, with a constant capacity range ∆c.

Figure 10 :

 10 Figure 10: The percentage of scenarios where the node with maximum ow centrality is identical to: (a) the nodes with the maximum closeness centrality, and the maximum weighted degree centrality, respectively ; (b) the node selected by the weighted path heuristic, for grids of dierent dimensions, and for dierent capacity ranges, with constant average capacity c avg = 50.

Figure 11 :

 11 Figure 11: Relative trac loss when the Local EPC is placed on the node maximizing the closeness centrality, the weighted degree centrality, and the node selected by the weighted path heuristic, for grids of dierent dimensions, for ∆c = 100.

Figure 12 :

 12 Figure 12: The percentage of scenarios where the node with maximum ow centrality is identical to the nodes maximizing other centralities, in random geometric graphs, for dierent capacity ranges, with constant average capacity c avg = 50.

Figure 13 :Figure 14 :

 1314 Figure 13: Relative trac loss when Local EPC is placed on the node maximizing centrality metrics other than the ow centrality, in random geometric graphs, for ∆c = 100.

Figure 15 :

 15 Figure 15: The average relative trac loss when the Local EPC is placed on the node maximizing centrality metrics other than the ow centrality, function of the number of nodes in random geometric graphs.

  .

			c 00	v 00	c 01
	c 10	v 10	c 11		c 12	v 11	c 13
	v 20		v 21		v 22		v 23
	v 30	v 31	v 32	v 33	v 34	v 35	v 36	v 37

  corresponds to the case where node 2 is selected as destination node, and co-located with the Local EPC. As we focus on the Local EPC placement problem, we are mostly interested in checking if the node having the maximum ow centrality is the same as the node maximizing one of the other centralities, presented in Sec. 2.1. We also check if the node with the maximum ow centrality is the same as the node selected by the weighted path heuristic[START_REF] Muthaiah | Single Gateway Placement in Wireless Mesh Networks[END_REF], described in Sec.2.2. Moreover, we study whether one of the centrality metrics, or the weighted path heuristic, could be directly used for the Local EPC placement instead of the ow centrality. Hence, we compute the total trac received by the Local EPC if the latter was placed on a node maximizing one of these centrality metrics, but not the ow centrality. If λ max is the maximum ow centrality in the graph, and λ(u) is the ow centrality of a node u, then placing the Local EPC on node u, instead of the node with the maximum ow centrality, causes a relative trac loss λ (u), such that:

	7. Benchmarking Flow Centrality
	As discussed in Sec. 2, several centrality metrics were proposed in the
	literature. In this section, we compare our proposition, the ow centrality
	metric, with other state of the art centrality metrics that appear to be the
	closest to it.
	Max Flow Centrality
	Max Degree, Weighted Degree, Closeness, Betweenness Centrality
	14.28	14.28	14.28		1	14.28
	4
	14.28	8	7	50/50		14.28
	9		50/50	6
			Local EPC			0
	3			2		14.28
	14.28	5
		14.28
	Figure 9: A random geometric graph topology, with link capacities c = 50, on each link
	(u, v). All nodes transmit λ max = 14.28 units of trac towards the Local EPC co-located
	with node 2.

$ Funding: This work was supported by the French Programme d'Investissements d'Avenir (PIA) project Fed4PMR.

In this work, we treated the BSs in the network equally by maximizing their capabilities in the same way. This is suitable for a network where the Local EPC is statically planned for initial deployment, when no sucient information on the BSs demands is available, or when the Local EPC position is xed for the entire network operation. However, in practical deployments, during network operation, BSs may have dierent demands, which directly aects the Local EPC optimal position. Hence, for future work, non-uniform BS demands and possible migrations of the Local EPC must be studied. Another important aspect in the communication between the BSs and the Local EPC is the end-to-end delay. Delay constraints must be further included in the Local EPC placement criteria. Eventually, co-locating a virtualized EPC with a BS opens up new perspectives on having the EPC functionalities distributed in the network, rather than centralized on a single BS.