Fei Shen

Pin-Hsun Lin

Luca Sanguinetti

Merouane Debbah

Eduard A Jorswieck

AN ENERGY-AWARE AUCTION FOR HYBRID ACCESS IN HETEROGENEOUS NETWORKS UNDER QOS REQUIREMENTS

Keywords: ascending-bid auction, hybrid access, heterogeneous network, QoS requirement

We consider a heterogeneous network (HetNet) in which multiple small cell base stations (SBSs) aim to offload a quantity of macro cell user equipments (MUEs) to reduce the energy consumption of the network while guaranteeing the QoS requirements of all UEs. We design an ascending-bid auction mechanism to achieve this goal. Unique and closed form solutions for the demand and supply quantities of offloading MUEs are derived. When the MBS has knowledge about the utilities and strategies of the SBSs, the proposed auction can be formulated as a Stackelberg game where the clinching bid price is obtained in closed form. Numerical results verify the theoretical analysis for different scenarios and show that the proposed auction clinches fast at the unique clinching price, thereby resulting in a win-win solution that improves the energy consumption of the HetNet.

INTRODUCTION

Heterogeneous networks (HetNets) are considered as a key technology for 5G [START_REF] Chandrasekhar | Femtocell networks: a survey[END_REF]. This paper investigates the user equipment (UE) and base station (BS) association for a network with a single macrocell base station (MBS) and multiple small cell base stations (SBSs), where each UE has a rate-based QoS requirement to be guaranteed by the serving BS.

The three basic access control mechanisms for HetNets are closed, hybrid and open access [START_REF] Jo | Open, closed, and shared access femtocells in the downlink[END_REF][START_REF] De La Roche | Access control mechanisms for femtocells[END_REF]. Among them, the hybrid access is considered as the most promising for reducing the energy consumption of the network. Since the transmit power of each UE is highly related to the total number of UEs served in each cell, it is important for the MBS to stimulate the SBSs for the hybrid access. When multiple SBSs exist, auction is a powerful tool to model, analyze, and solve the problem for offloading the quantity of macrocell UEs (MUEs) in the hybrid access.

There exist several works in which resource allocation is performed using game theory and auction [START_REF] Bacci | Energy-aware competitive power allocation for heterogeneous networks under qos constraints[END_REF][START_REF] Naparstek | Fully distributed optimal channel assignment for open spectrum access[END_REF]. The user-cell association for massive MIMO networks is considered in [START_REF] Bethanabhotla | Optimal user-cell association for massive mimo wireless network[END_REF] and addressed using non-cooperative game theory. In [START_REF] Zhuang | Energy-efficient cell activation, user association, and spectrum allocation in heterogeneous networks[END_REF], the user association and spectrum allocation problems are addressed to stabilize the HetNet and to minimize the transmission delay. In [START_REF] Huang | Auction-based spectrum sharing[END_REF][START_REF] Huang | Auction-based resource allocation for cooperative communications[END_REF], two auction mechanisms for allocating the received power among a group of UEs subject to a constraint on the interference are proposed for Part of this research has been supported by the ERC Starting Grant 305123 MORE. relay selection and relay power allocation, leading to a weighted max-min fair allocation. To motivate an efficient and fair resource allocation for spectrum-sharing femtocell networks, Vickrey-Clarke-Groves (VCG) auction is proposed to ensure that small cell user equipments (SUEs) submit their utilities truthfully despite of their selfish nature [START_REF] Wang | Auction-based resource allocation for spectrum-sharing femtocell networks[END_REF]. The single cluster of macro-femtocell hybrid access is discussed in [START_REF] Shen | User-centric energy aware compensation framework for hybrid macro-femtocell networks[END_REF][START_REF] Shen | User-centric compensation framework with universal pricing for hybrid femtocell networks[END_REF] where a Stackelberg game is designed to maximize the system energy consumption. A compensation framework is proposed for motivating the hybrid access in conjunction with a time division multiple access (TDMA) strategy [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF].

In this work, the multiple SBSs are modelled as bidders that compete among each other to offload a certain number of MUEs and receive the corresponding compensation paid by the MBS. Two different scenarios are envisaged. In the first one, we assume that the MBS and SBSs belong to different operators and thus have no knowledge of the utilities and strategies of each other. In this context, a low-complexity ascending-bid auction is proposed, in which each SBS bids for the demand quantity of the offloading MUEs only based on their local information and the given bid price. The fast convergence of the clinching price at market clearance is guaranteed. In the second scenario, we assume that the MBS and SBSs belong to the same operator and exploit the knowledge of the utilities and strategies to formulate a Stackelberg game. This allows us to compute the clinching price in closed-form without the need of any iterative procedure.

The outline of the paper is as follows. In order to motivate the energy-aware hybrid access for the two-tier HetNet, an ascendingbid auction is proposed in Sec. 2. The utilities of the MBS and SBSs are provided as functions of the bid price and the quantity of offloading MUEs in Sec. 3.1. Unique and closed form solutions for the demand and supply quantities of offloading MUEs are derived in Sec. 3.2 by maximizing the utilities of the MBS and SBSs, respectively. A Stackelberg game is analyzed in Sec. 4 wherein a closed-form clinching price is derived. Numerical results are given in Sec. 5 to assess the performance of the proposed solutions and validate the analysis.

NETWORK MODEL

System model

We consider the uplink of a two-tier HetNet in which the MBS and SBSs operate over different frequency bands. We denote by M the number of MUEs that are served by the MBS and assume that N SBSs serve Li SUEs each. We assume also that all UEs and BSs are equipped with a single antenna and that a certain QoS require- ment u must be guaranteed to each UE (no matter it is served by the MBS or by the SBSs). Within this setting, we are interested in reducing the energy consumption of the network. To this end, we assume that the MBS is willing to compensate a given SBS for offloading a quantity of MUEs. Clearly, when N > 1 this gives rise to a competition among the SBSs, which is modelled and solved in this work through an ascending-bid auction mechanism as described in the next section.

We consider a block flat-fading channel model and denote by αi the channel gain of a generic UE i. Call Si the total number of UEs associated to the MBS or SBS serving UE i. Then, for a given Si the uplink power required by UE i to meet the rate requirement u is given by [START_REF] Shen | Universal non-linear cheat-proof pricing framework for wireless multiple access channels[END_REF] as

pi[Si] = 1 -2 -u αi 1 Si (2 -u -1) + 1 . (1)
We denote the Shannon rate log(1 + SIN Ri) as the criterion of the rate requirement u measured in [bit/s/Hz]. When all the UEs meet the rate requirement u with equality, pi[Si] is derived in a simple expression as [START_REF] Chandrasekhar | Femtocell networks: a survey[END_REF] where the CSI or SINR of other UEs is contained in u.

From the above equation, it follows that a positive power allocation and the feasibility of achieving u for all UEs in the HetNet are ensured only if the total number Si in the network is such that

0 ≤ Si ≤ 1 1 -2 -u .
(2)

Auction-based Hybrid Access

In a generic ascending-bid auction mechanism, the auctioneer calls a bid price and the bidders respond with demand quantities by maximizing their own utilities. Meanwhile, the auctioneer optimizes the supply at the given bid price in each round. The process iterates with increasing bid prices until the market clears or the demand is no less than the supply [START_REF] Ausubel | An efficient ascending-bid auction for multiple objects[END_REF]. The ascending-bid auction mechanism used in this work to offload MUEs operates as follows. The MBS acts as the auctioneer, which announces a bid price b to all the SBSs (the bidders) and calls for demand quantities {K ⋆ i ; i = 1, . . . , N }. Each K ⋆ i corresponds to the maximum number of MUEs that can be offloaded by SBS i in order to maximize its own utility function U S i while taking into account that the reward from the MBS is bK ⋆ i . At the same time, the MBS optimizes its supply quantity by computing the optimal number K ⋆ of offloading MUEs by maximizing its own utility U M . If the sum of the demand quantities is less than the supply, i.e., N i=1 K ⋆ i < K ⋆ , then the auctioneer increases the bid price b by a given quantity ∆b. The process continues until the market clinches or, equivalently, until the following condition is satisfied

N i=1 K ⋆ i = K ⋆ .
The above ascending-bid auction mechanism is summarized in Algorithm 1. Compute

K ⋆ = arg maxK∈0,1,...,M U M ; 8: until N i=1 K ⋆ i = K ⋆
When the auctioneer MBS has no knowledge about the utility and strategies of the SBSs, the auction is run as shown in Algorithm 1 until the market clears.

AUCTION FORMULATION AND SOLUTION

Next, we introduce the utility functions of MBS and SBSs for the propsoed auction framework and then provide its solution in a closed form. The bid b is provided by the auctioneer MBS for the quantity of offloading MUEs.

Auction Formulation

The utility functions U M and U S i commonly take the following form Utility = Revenue -Cost. In this work, we assume that U M is computed as

U M = v M -bK, (3)
where v M denotes the Revenue for the power saving for each remaining MUE due to the offloading of K MUEs and bK accounts for the total price (or cost) paid by the MBS to all SBSs. Denote M and M -K to be the sets of MUEs served by the MBS before and after using the hybrid access, respectively. Thereby, we obtain

v M = λ M (p i [M ] -p i [M -K]) αi 1 -2 -u = λ M 1 M (2 -u -1) + 1 - 1 (M -K)(2 -u -1) + 1 , (4)
where λ M denotes the equivalent revenue per unit of power saving of a single MUE i that remains in the service range of MBS. For each remaining MUE i in the system the term 1-2 -u α i remains the same for both sets M and M -K in (1). Therefore, 1-2 u α i is multiplied to ease the calculation. Note that both the Revenue and Cost of the MBS are increasing functions with respect to K, i.e., the supply quantity of offloaded MUEs.

The utility of SBS i is modelled as:

U S i = v S i + bKi -Ei (5)
where v S i accounts for the utility of the Li SUEs, bKi is the compensation received from the MBS, and Ei is the cost of additional energy of each registered SUE when additional Ki MUEs are offloaded to the SBS i. We let v S i = λ1Liu with λ1 being the revenue per unit of achievable rate whereas Ei is computed as

Ei = λ2 pi[Li + Ki] pi[Li] = λ2 Li(2 -u -1) + 1 (Li + Ki)(2 -u -1) + 1 (6)
with λ2 being the revenue per unit of power loss denoted by the ratio of power consumption for a single registered SUE. Observe that Ei is an increasing function of Ki. The utility U S i is a function of only the local information of each SBS and of the bid price b from the MBS. Therefore, there is no need of information exchange among SBSs.

Auction Solution

As depicted in Algorithm 1, for a given b the demand quantity of SBS i at each iteration is obtained as the solution of the following problem:

K ⋆ i = arg max K i ∈{0,1,...,M } U S i , (7)
where U S i takes the form

U S i = λ1Liu + bKi -λ2 (Li(2 -u -1) + 1) (Li + Ki)(2 -u -1) + 1 . (8)
The solution of the above problem can be obtained in a closed form as follows.

Proposition 1. For a given bid price b, the solution to (7) is

K ⋆ i = Li(2 -u -1) + 1 1 -2 -u - (Li(2 -u -1) + 1)λ2 b(1 -2 -u ) . ( 9
)
Proof. K * i in ( 9) is obtained by checking ∂U S i ∂K i = 0 by integer optimization and showing that U S i is a convex function of Ki. The optimal quantity Ki is obtained by solving the first derivative of (8) with respect to Ki, i.e.,

∂U S i ∂Ki = b + λ2(Li(2 -u -1) + 1)(2 -u -1) ((Li + Ki)(2 -u -1) + 1) 2 = 0, Ki = Li(2 -u -1) + 1 1 -2 -u - (Li(2 -u -1) + 1)λ2 b(1 -2 -u ) .( 10
)
Now we show that the utility function U S i in ( 8) admits global maximum by checking the second derivative,

∂ 2 U S i ∂ 2 Ki = -2(Li(2 -u -1) + 1)(2 -u -1) 2 ((Li + Ki)(2 -u -1) + 1) ((Li + Ki)(2 -u -1) + 1) 4 . ( 11
)
Given the restriction in (2),

∂ 2 U S i ∂ 2 K i < 0.
The integer-valued optimization result is achieved by using ⌊⌉.

As seen, for a given b the computation of K ⋆ i requires knowledge of local information as it only depends on the parameters Li, u, and λ2, which are independent of other SBSs.

The MBS determines the optimal supply of offloading MUEs by solving the following problem:

K ⋆ = arg max K∈{0,1,...,M } U M (12)
with

U M = λ M 1 M (2 -u -1) + 1 - 1 (M -K)(2 -u -1) + 1 -bK.
Proposition 2. For a given bid price b, the solution to [START_REF] Shen | User-centric compensation framework with universal pricing for hybrid femtocell networks[END_REF] is

K ⋆ = M + λ M b (1 -2 -u ) - 1 1 -2 -u . ( 13
)
Proof. The proof follows the same procedure as that for Proposition 1 and is thus omitted for space limitations.

With the constraint on the total number of offloading MUEs K ∈ {0, 1, . . . , M }, the bid price b should be provided in the following range.

Corollary 1. The rate requirement u can be ensured provided that the bid price

b is such that bmin ≤ b ≤ bmax with bmax = λ M (1 -2 -u ) (M (2 -u -1) + 1) 2 , ( 14
)
and bmin = max λ M (1 -2 -u ), λ2(1 -2 -u ) Li(2 -u -1) + 1 . ( 15
)
Proof. λ M (1 -2 -u ) ≤ b ≤ λ M (1-2 -u ) (M (2 -u -1)+1) 2 is proved by ensuring 0 ≤ K ≤ M . λ 2 (1-2 -u ) L i (2 -u -1)+1 ≤ b is to ensure 0 ≤ Ki ≤ M , therefore Corollary 1 is proved.

CLINCHING PRICE-STACKELBERG GAME

If the MBS and SBSs belong to the same operator, then it is possible for the MBS to gain knowledge about the utilities and strategies of the SBSs. The proposed ascending-bid auction can be formulated as a Stackelberg game. The MBS acts as the leader by providing the clinching bid price b * and the SBSs act as the followers by deciding the bid quantity of offloading MUEs given b * .

We now proceed computing the clinching bid price in a closed form. If the MBS acquires the information of the SBSs, then it can predict the bid b * without iterations. As described before, the auction mechanism is clinched if the market clears or, equivalently, if the supply is equal to the total demand, which amounts to saying that

K ⋆ = N i=1 K ⋆ i .
Then, from the results of Propositions 1 and 2 it follows that: Proposition 3. The clinching bid price b * can be obtained from the following equation If the MBS and SBSs belong to different operators, then the ascending-bid auction is run as shown in Algorithm 1. This is illustrated in the next section.

b * =   √ λ M + N i=1 λ2(Li(2 -u -1) + 1) 1 1-2 -u (1+ N i=1 Li(2 -u -1) + 1)-M √ 1 -2 -u   2 .
M =5, L 1 =2, L 2 =1 u =0.18 λ M =1 λ 1 =5 λ 2 =1 K * 1 K * 2 K * 1 + K *
M =5, L 1 =2, L 2 =1 u =0.3 λ M =1 λ 1 =5 λ 2 =1

NUMERICAL RESULTS

In order to illustrate the outcome of the proposed auction-based hybrid access, the scenario where two small cells exist within the coverage of the macrocell is simulated. However, the results are extendable to multiple small cells.

In the following, the identical rate requirement is set in the range such that it is achievable for all possible numbers of UEs in the twotier system no matter in the macrocell or the small cell.

We illustrate when the MBS has no knowledge about the SBSs, how the number of MUEs in both demand and supply changes with the bid price for different network parameters. In each round of the auction, both the auctioneer MBS and the bidders SBSs optimize their supply and demand quantities of offloading MUEs by maximizing their own utilities, respectively. U M is a decreasing function while U F i is an increasing function of b. The higher the bid price, the more compensation the MBS will pay to the SBSs and thus the lower its supply of MUEs. In contrast, the higher b, the more MUEs the SBSs are willing to serve. There exists a unique clinching price b * such that the market clears with K * = N i=1 K * i . And the step size ∆b can be chosen for fast convergence. We can see from the figures that the bid price clinches only after few iterations, which shows the fast convergence of Algorithm 1.

M =5, L 1 =2, L 2 =1 u =0.18 λ M =1 λ 1 =5 λ 2 =2 K 1 * K 2 * K 1 * + K
By comparing Fig. 2 and Fig. 3, we observe that when the rate requirement u of each UE increases, the clinching bid price b * is higher and the market clearance quantity K * decreases. This is because the higher rate requirement, the less the acceptable number of UEs in each cell. Moreover, the SBSs need more compensation from the MBS in order to stimulate the acceptance of the additional MUEs.

When λ2 increases as shown in Fig. 4, the clinching bid price b * also becomes higher and the market clearance quantity K * decreases as well. The reason is that λ2 shows the importance of the energy loss for the SBSs when concerning to serve additional MUEs. If λ2 becomes higher, then less K * i MUEs could be served in order to make sure that the loss in power of the registered SUEs is not significant.

The theoretical analysis of b * , K * 1 , K * 2 and K * are verified by the simulation results. Both the utilities of the MBS and SBSs are maximized. Since there is no overhead on information exchange among different cells, the proposed ascending-bid auction is a lowcomplexity mechanism to apply for the hybrid access in HetNets.

After optimizing the offloading quantity of MUEs, the MBS can decide the exact MUEs with the shortest distance to the corresponding SBS in order to minimize the total energy consumption of the two-tier HetNet. However, this is beyond the scope of the current work. Therefore, the comparison of energy reduction remains in our future work.

CONCLUSION

In order to motivate the energy-aware hybrid access in the two-tier macro-small cell network, a novel ascending-bid auction-based algorithm is proposed.. The MBS in the macro-cell acts as the auctioneer and the SBSs in the small cells act as the bidders. The bid price is provided by the MBS to all the SBSs. The optimal supply and demand quantities and the clinching price are derived in closed form solutions. Numerical results illustrate that the auction clinches at the unique clinching price and the utilities of both the MBS and the SBSs are maximized, showing that the auction algorithm results in a win-win solution.

Fig. 1 .

 1 Fig. 1. The considered system model.

Algorithm 1

 1 Auction-based Hybrid Access 1: Input M , N , u, {Li}, ∆b, U M and {U S i }. 2: Output K ⋆ , {K ⋆ i }, b ⋆ . 3: Set b = 0; 4: repeat 5: Set b = b + ∆b; 6:Compute K ⋆ i = arg maxK i ∈0,1,...,M U S i ;7:

2 KClinchingFig. 2 .

 22 Fig. 2. Illustration of clinching bid price at market clearance with u = 0.18.

Fig. 3 .

 3 Fig. 3. Illustration of clinching bid price at market clearance with u = 0.3.

Fig. 4 .

 4 Fig. 4. Illustration of clinching bid price at market clearance with λ2 = 2.


Jelena Pozojevic

Ilaria Parenti

Luitgard Graul-Neumann

Sara Ruiz Gil

Erwan Watrin

Kerstin S Wendt

Ralf Werner

Tim M Strom

Gabriele Gillessen-Kaesbach

Dr Frank J Kaiser
email: frank.kaiser@uksh.de

Novel mosaic variants in two patients with Cornelia de Lange syndrome

Keywords: Cornelia de Lange syndrome, NIPBL, mosaicism

Cornelia de Lange syndrome (CdLS) is a dominantly inherited developmental disorder caused by mutations in genes that encode for either structural (SMC1A, SMC3, RAD21) or regulatory (NIPBL, HDAC8) subunits of the cohesin complex. NIPBL represents the major gene of the syndrome and heterozygous mutations can be identified in more than 65% of patients.

Interestingly, large portions of these variants were described as somatic mosaicism and often escape standard molecular diagnostics using lymphocyte DNA.

Here we discuss the role of somatic mosaicism in CdLS and describe two additional patients with NIPBL mosaicism detected by targeted gene panel or exome sequencing. In order to verify the next generation sequencing data, Sanger sequencing or pyrosequencing on DNA extracted from different tissues were applied. None of the pathogenic variants was originally detected by Sanger sequencing on blood DNA.

Patient 1 displays an unusual combination of clinical features: he is cognitively only mildly affected, but shows severe limb reduction defects. The second patient presents with a moderate phenotype. Interestingly, Sanger sequencing analysis on fibroblast DNA did not detect the disease-causing variant previously observed on the same DNA sample by exome sequencing. Subsequent analyses could confirm the variants by Sanger sequencing on buccal mucosa DNA. Notably, this is the first report of a higher mutational load in buccal mucosa than in fibroblast cells of a CdLS patient.

Detection of low-level mosaicism is of utmost importance for an accurate molecular diagnosis and a proper genetic counseling of patients with a clinical diagnosis of CdLS. Next-generation sequencing technologies greatly facilitate the detection of low-level mosaicism, which might otherwise remain undetected by conventional sequencing approaches.

Introduction

Cornelia de Lange syndrome (CdLS, OMIM #122470, 300590, 610759, 300882, and 614701) is a rare developmental disorder, clinically and genetically heterogeneous. Besides the distinctive facial features, the syndrome is characterized by growth retardation, cognitive delay with behavioral problems and multiple congenital abnormalities [START_REF] Kline | Cornelia de Lange syndrome: Clinical review, diagnostic and scoring systems, and anticipatory guidance[END_REF]. To date, approximately 75% of patients with CdLS carry mutations in structural components (SMC1A, SMC3, RAD21) or regulators (NIPBL, HDAC8) of the cohesin complex [START_REF] Krantz | Cornelia de Lange syndrome is caused by mutations in NIPBL, the human homolog of Drosophila melanogaster Nipped-B[END_REF][START_REF] Tonkin | NIPBL, encoding a homolog of fungal Scc2-type sister chromatid cohesion proteins and fly Nipped-B, is mutated in Cornelia de Lange syndrome[END_REF][START_REF] Musio | X-linked Cornelia de Lange syndrome owing to SMC1L1 mutations[END_REF][START_REF] Deardorff | Mutations in Cohesin Complex Members SMC3 and SMC1A Cause a Mild Variant of Cornelia de Lange Syndrome with Predominant Mental Retardation[END_REF]Deardorff et al. 2012a,b). Cohesin plays a fundamental role in the maintenance of genomic stability, since it is involved in the regulation of sister chromatid cohesion, gene expression, DNA repair and chromatin remodeling [START_REF] Watrin | The cohesin complex is required for the DNA damageinduced G2/M checkpoint in mammalian cells[END_REF][START_REF] Merkenschlager | Cohesin: A global player in chromosome biology with local ties to gene regulation[END_REF]Dorsett and Strom, 2012). In addition to cohesin, variants in other chromatin regulators such as ANKRD11, AFF4, EP300, KMT2A, SETD5 or subunits of the SWI/SNF chromatin-remodeling complex were described in nearly 1% of patients with CdLS (Woods et individuals in a cohort of patients originally reported to be mutation-negative by conventional Sanger sequencing approaches on DNA isolated from blood samples [START_REF] Huisman | High rate of mosaicism in individuals with Cornelia de Lange syndrome[END_REF].

These mosaic variants are of particular interest, because they often escape routine molecular diagnostics, since the sensitivity of Sanger sequencing only allows detection of 15-20% of aberrant alleles or because of a focused molecular diagnostics restricted to blood DNA samples.

Here we will discuss and expand the crucial role of somatic mosaicism in CdLS and present two additional patients with mosaic disease-causing variants in NIPBL.

Somatic mosaicism

Somatic mosaicism is a well-known biological phenomenon, occurring not only in humans, but also in other species. It indicates existence of at least two different genotypes in the same individual and can occur for any type of mutation, either at the chromosomal or DNA sequence level. It is difficult to predict clinical consequences of mosaicism, as they depend on the timing of the mutation events, type of mutation, percentage of mutated cells and tissue distribution of the genetic change. Patients with mosaic mutations sometimes show milder phenotypical presentation of the disease, but are also often not distinguishable from those patients with non-mosaic heterozygous variants. In other cases, mosaic individuals appear healthy, without any distinguishable phenotype and mosaicism is revealed only upon molecular testing. Many alterations can occur only in a mosaic form, as the mutation is lethal when present in every cell [START_REF] Spinner | Mosaicism and clinical genetics[END_REF]. In favor of this hypothesis speaks the fact that only ~30% of conceptions result in live births and that majority of pre-and postimplantation pregnancy losses are associated with chromosomal abnormalities in the gametes and embryo [START_REF] Macklon | Conception to ongoing pregnancy: The "black box" of early pregnancy loss[END_REF].

Mosaic mutations can be present in somatic, germinal cells or both, but typically only mutations in the soma have phenotypic consequences and can be detected by current

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT

sequencing techniques. Germline mosaicism is instead speculated only in the presence of several affected offspring of apparently unaffected parents. However, molecular detection of germline mosaicism is limited by inability to obtain germline DNA, especially in females [START_REF] Youssoufian | Mechanisms and consequences of somatic mosaicism in humans[END_REF][START_REF] Freed | Somatic mosaicism in the human genome[END_REF].

The first mosaic chromosomal abnormality was reported in 1960 [START_REF] Hirschhorn | Human Intersex with Chromosome Mosaicism of Type XY/XO[END_REF], while the first suggestion of chromosomal mosaicism in patients with CdLS was reported in 1965 [START_REF] Payne | The Cornelia de Lange syndrome: clinical and cytogenetic interpretations[END_REF]. In this report, translocations and deletions were visible only in some of the analyzed karyotypes of patient cells, while the other cells appeared normal.

The first patient with a mosaic mutation in NIPBL was reported by Castronovo and colleagues [START_REF] Castronovo | Somatic mosaicism in Cornelia de Lange syndrome: A further contributor to the wide clinical expressivity?[END_REF]. Since then, somatic mosaicism has been described for all five CdLS Interestingly, very low levels of somatic mosaicism for some of the CdLS genes have been reported also in few unaffected parents of patients with CdLS: Slavin and colleagues described low-levels of a mosaic mutation in SMC1A in the blood DNA of an unaffected father of two affected sisters [START_REF] Slavin | Germline mosaicism in Cornelia de Lange syndrome[END_REF]. In addition, our group recently reported an unaffected mother of two siblings with CdLS, mosaic for an HDAC8 variant in her urine (19%) and blood DNA (2%) (Parenti et al., 2016b). Few cases with gonadal NIPBL mosaicism have also been described [START_REF] Niu | Paternal gonadal mosaicism of NIPBL mutation in a father of siblings with Cornelia de Lange syndrome[END_REF][START_REF] Weichert | Cornelia de Lange syndrome: antenatal diagnosis in two consecutive pregnancies due to rare gonadal mosaicism of NIPBL gene mutation[END_REF][START_REF] Slavin | Germline mosaicism in Cornelia de Lange syndrome[END_REF]. However, a recent study showed that a portion of de novo mutations presumed to be germline actually either occurred post-zygotically in the embryo or were inherited from the mother or father with low-level mosaicism (Acuna-Hidalgo et al., 2015).

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 6

Here we report two patients with the clinical diagnosis of CdLS, who were found to be negative for pathogenic variants in the five CdLS genes by conventional Sanger sequencing approaches on blood DNA. The disease-causing variants were subsequently identified by means of next generation sequencing techniques.

Patients

Patient 1 (Fig. 1a) is a 32 years old German male being the first child born to healthy parents.

The pregnancy was uneventful and he was born after 42 weeks of gestation. Birth length was 48 cm (-2.25 SD), birth weight 3170 g (-1.35SD), occipital frontal circumference (OFC) 32 cm (-2.93 SD), and Apgar score were 6/9/10, respectively. He has not displayed any feeding difficulties. The patient presents with facial features typical for CdLS, namely synophrys, long eyelashes, depressed nasal bridge, upturned nose, thin upper lip, low set ears and low anterior hairline. He also presents with split hand deformity on the left hand and ulnar oligodactyly with missing fifth finger on the right hand. His left leg is 1.3 cm shorter than the right leg, due to pronounced hip dysplasia, corrected by orthopedic shoes. He was able to sit alone at the age of 9 months and to walk independently at the age of 20 months. He spoke his first words when he was almost one year old and he is able to communicate by using only a few words, but he is not able to produce longer sentences. The patient is capable to write and read with certain limitations, to swim, ride a bike, solve puzzles and to use modern media such as a digital camera. He is able to take care of himself and works in a carpenter´s shop.

He occasionally suffers from headaches and has excessive amount of saliva.

At the current age (32 years), the patient's height is 156 cm (-0.8 SD), his weight is 40 kg (-0.3 SD) and his OFC is 52.8 cm (-2.4 SD).

Buccal DNA of the patient was analyzed by targeted CdLS-panel, which was performed on the Personal Genome Machine (Ion Torrent PGM, Life Technologies, Darmstadt, Germany)

M A N U S C R I P T A C C E P T E D

ACCEPTED MANUSCRIPT 7 as previously described [START_REF] Braunholz | Hidden mutations in Cornelia de Lange syndrome limitations of Sanger sequencing in molecular diagnostics[END_REF]. By this, we identified a nonsense mutation in NIPBL (RefSeq NM_133433), namely c.4399A>T; p.(Lys1467*), in 30% of the sequencing reads. The variant was confirmed by Sanger sequencing on buccal DNA, as well as on DNA obtained from epithelial urine cells, whereas it was not detectable on blood DNA (Fig. 1c).

Parents were not available for testing, but the variant was not present in the Genome Aggregation Database (gnomAD).

Patient 2 (Fig. 1b) is a female, the only child born to a German mother and a Syrian father.

Family history comprises Lupus erythematosus and vitamin D deficiency. Additionally, the mother had terminated a previous pregnancy due to the presence of trisomy 21. The pregnancy of the index patient was unremarkable, albeit prenatal brachycephaly was described. The delivery was vacuum-assisted, birth weight was 3140 g (-0.79 SD), birth length was 50 cm (-0.77 SD), occipital frontal circumference (OFC) was 35 cm (0.08 SD), Apgar scores were 9/9/10 and pH of umbilical arteries was 7.18. The patient showed early feeding difficulties, which required a high-caloric diet. She was able to walk independently at 18 months. She was diagnosed with patent foramen ovale with right to left shunt and X-ray of her hands showed shortening of the first metacarpal. She presents with a friendly behavior.

Array-CGH, MLPA for NIPBL and Sanger sequencing on blood DNA for NIPBL, SMC1A, RAD21 and HDAC8 could not detect any disease-causing variant. For this reason, the patient was selected to undergo a trio-based exome sequencing analysis, which was performed on the HiSeq 2500 system (Illumina, San Diego, CA, USA) as previously described [START_REF] Parenti | Mutations in chromatin regulators functionally link Cornelia de Lange syndrome and clinically overlapping phenotypes[END_REF]. This analysis, which was performed on DNA extracted from fibroblasts, led to the identification of the de novo missense mutation c.5483G>A, p.(Arg1828Gln) in NIPBL in 15% of the sequencing reads. The variant was not present in the Genome Aggregation Database (gnomAD). Interestingly, we were not able to confirm this mutation by Sanger sequencing neither on blood nor on fibroblast DNA (Fig. 1d). However, the electropherogram performed on fibroblasts displayed a small mutant peak underneath the wild type base. As

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 8
next, we performed pyrosequencing on blood and fibroblast DNA of the patient. The ratio between the mutant and the wild type allele was found to be 14:86 on fibroblasts DNA and 2:98 on blood DNA (Fig. 1e), hence explaining why the mutation was not detected by Sanger sequencing. We subsequently obtained DNA from a third tissue, namely buccal mucosa. In this tissue, the pathogenic-variant could be detected by conventional Sanger sequencing (Fig. 1d), and pyrosequencing analysis revealed a mutant:wild type ratio of 17:83 (Fig. 1e). We previously demonstrated that fibroblasts represent the best source of DNA for mutation detection through Sanger sequencing [START_REF] Braunholz | Hidden mutations in Cornelia de Lange syndrome limitations of Sanger sequencing in molecular diagnostics[END_REF]. Thus, our patient represents the first case in which cells from buccal mucosa show a higher percentage of the mutant allele than fibroblasts.

Discussion

Somatic mosaicism has been proven to play a very important role in the pathogenesis of several disorders [START_REF] Freed | Somatic mosaicism in the human genome[END_REF]. However, patients with mosaic mutations show variable phenotypes and it is not possible to predict in advance, based on clinical features, if a mutation will be found in a mosaic state or not. Thus, there is usually no clear correlation between the mutation load and the phenotype. For instance, severe limb reduction defects as seen in patient 1 are restricted to CdLS patients with variants in NIPBL and almost exclusively caused by truncating variants or null alleles. While the severe malformation of the left arm is in agreement with the genotype, a mild cognitive impairment as seen in patient 1 is rather unique and has never been reported in a patient with this type of NIPBL mutation.

Based on our findings that indicate absence of the mutation in blood and only 30% in buccal mucosa DNA, it is tempting to speculate that some other tissues, especially neuronal tissues, might show only small portions of the variant, which may explain the mild cognitive impairment. In a previous report another mildly affected CdLS patient with severe limb defects was reported as negative for a disease-causing variant in NIPBL using DNA from [START_REF] Bhuiyan | Genotype-phenotype correlations of 39 patients with Cornelia De Lange syndrome: the Dutch experience[END_REF]]. Based on our findings it is tempting to speculate if this patient is also mosaic for a disease-causing variant in NIPBL.

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 9 lymphocytes [
Blood leukocytes have been the gold standard material for molecular analysis for decades.

Nevertheless, mosaic mutations are frequently not detected in these samples, meaning that DNA of additional tissues is required for a comprehensive and proper molecular testing, especially of those patients with clear clinical diagnosis, but negative results. Previously, we have described three patients with somatic variants in NIPBL identified by conventional Sanger sequencing approaches on DNA extracted from fibroblast cells, but not on DNA from buccal mucosa or blood cells [START_REF] Braunholz | Hidden mutations in Cornelia de Lange syndrome limitations of Sanger sequencing in molecular diagnostics[END_REF]. Therefore, fibroblasts from skin biopsies were recommended as the most suitable tissue for molecular diagnostics. In contrast to our previous report, here we describe a somatic mosaicism that was detected by conventional Sanger sequencing on DNA from buccal mucosa, but not detected using fibroblast DNA. However, highly sensitive pyrosequencing approaches could identify the pathogenic variant in DNA samples of both tissues. Based on these findings, we recommend the use of sensitive next generation sequencing approaches with high numbers of sequencing reads that should not be restricted to DNA from blood samples. Only the combination of sensitive sequencing technologies and DNA from sources other than blood allow an appropriate molecular diagnostics of patients with clinical diagnosis of CdLS.

The identification of low-level mosaicism is of great importance for an accurate diagnosis and proper genetic counseling. Therefore, we strongly recommend integration of modern and highly sensitive sequencing techniques into the routine molecular diagnostics of CdLS. With increasing costs and availability of next generation sequencing technologies, we believe that high-coverage exome sequencing will be the most efficient and most suitable technology for appropriate molecular diagnostics of CdLS. Furthermore, to confirm and quantify putative mosaic variants represented by small numbers of total sequencing reads, we suggest additional sensitive targeted sequencing technologies such as pyrosequencing.

  al., 2014; Izumi et al., 2015; Yuan et al., 2015; Parenti et al., 2016a; Parenti et al., 2017). Notably, pathogenic variants in all these genes have been described as genetic causes of other developmental syndromes which share phenotypical features with CdLS, thus indicating that chromatin dysregulation is crucial for understanding the pathogenesis of this group of clinically overlapping disorders. Despite the newly identified causative genes, NIPBL remains the major CdLS gene (Mannini et al.,2013), with disease-causing variants detected in nearly 65% of CdLS patients. Mutations in NIPBL tend to be associated with more severe phenotypes and with a higher frequency of limb reduction defects in comparison to variants in other cohesin-related genes (Deardorff et al., 2012a,b; Gervasini et al., 2013; Kaiser et al., 2014; Gil-Rodriguez et al., 2015; Parenti et al., 2016b). However, the portion of NIPBL mutations even increases by taking into account the role of somatic mosaicism. Mosaic variants in NIPBL were identified in more than 20% of M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT 4

  genes, though the vast majority affects NIPBL (Hoppman-Chaney et al., 2012; Slavin et al., 2012; Huisman et al., 2013; Braunholz et al., 2015; Ansari et al., 2014; Gil-Rodriguez et al., 2015; Parenti et al., 2016b). The phenotypical spectrum of patients with mosaic variants in NIPBL is very broad, ranging from mildly to severely affected individuals. Therefore, distinct clinical features indicating somatic mosaicism have not been described so far.

Acknowledgements:

The authors are grateful to the patients and their families for generously donating samples and clinical information. This work was funded by the German Federal Ministry of Education and Research (BMBF) (CHROMATIN-Net: to F.J.K. and G.G.K.), by E-Rare-2 TARGET-CdLS (to F.J.K, K.W. and E.W.) and by the Medical Faculty of the University of Lübeck (J09-2017 to I.P.). Figure titles and legends: Figure 1. Phenotype of the patients and sequencing results. (a) Phenotype of patient 1, with a detail of the anomalies of the upper limbs. (b) Facial features of patient 2, including a detail of the small and widely spaced teeth. To be noted the presence of hirsutism.(c-d) Sanger sequencing of DNA obtained from different tissues ofpatient 1 (c) and patient 2 (d). (e) Pyrosequencing results from different tissues of patient 2.

References:

1) Acuna-Hidalgo, R., Bo, T., Kwint, M.P., Van De Vorst, M., Pinelli, M., Veltman, J.A., Hoischen, A., Vissers, L.E.L.M., Gilissen, C., 2015. Post-zygotic Point Mutations Are an Underrecognized Source of de Novo Genomic Variation. Am. J. Hum. Genet. 97, 67-74. doi:10.1016/j.ajhg.2015.05.008 2) Ansari, M., Poke, G., Ferry, Q., Williamson, K., Aldridge, R., Meynert, A.M., Bengani, H., Chan, C.Y., Kayserili, H., Avci, Ş., Hennekam, R.C.M., Lampe, A.K., Redeker, E., Homfray, T., Ross, A., Falkenberg Smeland, M., Mansour, S., Parker, M.J., Cook, J.A., Splitt, M., Fisher, R.B., Fryer, A., Magee, A.C., Wilkie, A., Barnicoat, A., Brady, A.F., Cooper, N.S., Mercer, C., Deshpande, C., Bennett, C.P., Pilz, D.T., Ruddy, D., Cilliers, D., Johnson, D.S., Josifova, D., Rosser, E., Thompson, E.M., Wakeling, E., Kinning, E., Stewart, F., Flinter, F., Girisha, K.M., Cox, H., Firth, H. V, Kingston, H., Wee, J.S., Hurst, J.A., Clayton-Smith, J., Tolmie, J., Vogt, J., Tatton-Brown, K., Chandler, K., Prescott, K., Wilson, L., Behnam, M., McEntagart, M., Davidson, R., Lynch, S.-A., Sisodiya, S., Mehta, S.G., McKee, S.A., Mohammed, S., Holden, S., Park, S.-M., Holder, S.E., Harrison, V., McConnell, V., Lam, W.K., Green, A.J., Donnai, D., Bitner-Glindzicz, M., Donnelly, D.E., Nellåker, C., Taylor, M.S., FitzPatrick, D.R., 2014. Genetic heterogeneity in Cornelia de Lange syndrome (CdLS) and CdLS-like phenotypes with observed and predicted levels of mosaicism. J. Med. Genet. 51, 659-668. doi:10.1136/jmedgenet-2014-102573

M A N U S C R I P T A C C E P T E D ACCEPTED MANUSCRIPT


Philippe Ezran
email: ezran@g.jct.ac.il

Yoram Haddad

Mérouane Debbah

Availability Optimization in a Ring-Based Network Topology

Keywords: Cellular networks, topology, ring, availability, resiliency

Cellular networks are nowadays considered as a major critical infrastructure.

Resiliency to failure due to disasters, weather based disruptions or malicious activities is essential. In the case of ring topology, because of delay and availability requirements, a wireless network connected to an aggregation node must sometimes be split into several rings. In this paper, we study the availability optimization in a ring-based network topology for a given number of cellular sites and a given size of rings. We prove that if each ring includes 3 nodes, the problem can be solved in a polynomial time, while for bigger rings, the problem is NP-hard. In this latter case, we provide approximation methods based on linear programming in order to converge to the solution.

Introduction

The choice of a network technology is mainly a matter of cost, availability and resiliency. For a given technology, these parameters will also impact the choice of the topology.

While fiber is capital intensive (cost function of distance) and offers limited availability, wireless is highly cost effective and flexible [START_REF]Microwave Backhauling -Meeting the Capacity Challenges of 4G/LTE and Beyond[END_REF]. Besides, fiber is more expensive in urban areas. The choice of fiber in urban areas may be cost-effective for very short distances only. However, this comparison must be considered cautiously: a large part of capex expenses for fiber is civil engineering. Civil engineering costs can represent up to 80% of total cost, especially in urban areas. In many cases and particularly in developing areas, these civil engineering expenses must be done anyway for infrastructure investment (road, rail, pipeline, electricity). Therefore, the relevant parameter which has to be taken into consideration for the fiber/wireless cost comparison is the additional cost generated by the fiber.

Availability is a key parameter which quantifies network performance. This parameter is closely related to reliability. The difference between these two concepts is that reliability refers to failure-free operation during an interval, while availability refers to failure-free operation at a given instant of time [START_REF] Al-Kuwaiti | A comparative analysis of network dependability, fault-tolerance, reliability, security, and survivability[END_REF].

Unavailability is generally defined as the sum of the unavailabilities of the network nodes [START_REF] Lehpamer | Microwave Transmission Networks[END_REF]. According to this definition, an unavailability which impacts a great number of nodes in the network gets a higher ponderation than an unavailability which impacts a small number of nodes. However, this definition may lead to unavailabilities greater than 100%. For this reason, in this paper, we define the unavailability as the percentage of time for which all or part of the network is down.

While the availability of an optical fiber connection is all or nothing, lineof-sight and propagation considerations must be taken into account in wireless links. Automatic Coding Modulation enables a microwave link to use lower modulations in degraded conditions. This difference has an impact on the network resiliency, which is the ability of the network to provide and maintain an acceptable level of service in the face of faults and challenges to normal operations [START_REF] Sterbenz | Resilience and survivability in communication networks: Strategies, principles, and survey of disciplines[END_REF].

In the case of a radio network, the main parameters which come into account are propagation factors and infrastructural considerations. The most common topologies used in radio backhaul networks are trees and rings or a combination of both. Since tree topology generally offers shorter paths and lower costs, while ring topology generally ensures a better availability, a ring-tree combination can be an efficient solution to cumulate the advantages of both technologies [START_REF] Nadiv | Wireless Backhaul Topologies: Analysing Backhaul Topology Strategies[END_REF].

Various causes of a network failure are identified in [START_REF] Sterbenz | Resilience and survivability in communication networks: Strategies, principles, and survey of disciplines[END_REF]: unusual traffic load, accidents and human mistakes, large-scale disasters, malicious attacks, environmental challenges and failures at a lower layer. A relevant network availability strategy must reduce as much as possible the failure probability of any link in the network and add redundancy in order to minimize the impact of a single link failure on the availability of the network nodes.

Statistical approaches have been proposed in order to optimize availability [START_REF] Gertsbakh | Statistical Reliability Theory[END_REF], [START_REF] Jiang | Availability maximization under partial observations[END_REF] for systems subject to random failures. These approaches are based upon maintenance considerations for a partially observable system.

Backhaul can be made of fiber or microwave radio. In both cases, the goal is to connect the base stations (BS) to the core network. In some cases, when the gateway to the core is not far, this can be performed in one hop. But in rural areas or in Ultra Dense Networks, where there are a huge number of small BS to connect, this can require multiple hops. In this paper, we consider the Microwave Radio technology as the medium to perform the backhaul. We assume that we have a large number of BS to be connected to a single aggregation node which itself will be connected to the core network. This latter connection is assumed to be wired and therefore out of the scope of this paper. Making a single large ring raises serious delay issues since the Backhaul for a BS might require several hops. In addition, it might raise serious availability issues since the disconnection of two links can affect a large number of BS. Therefore, it could be preferable to split the network into several rings.

In this paper, we will study the question of topology optimization from the point of view of availability maximization. Given an aggregation node and n cellular sites, what is the best topology based on rings, each one of them including the aggregation node, which maximizes availability?

Simplified model

In a first step, we build a simplified model, based on the following five assumptions. Though the last two assumptions of this model are not realistic, this simplified approach will enable us to draw basic conclusions regarding backhaul network topologies.

Assumptions:

• the network includes n cellular sites (in addition to the aggregation node);

• the network topology is made of k rings;

• for 1 ≤ i ≤ k ring i includes n i cellular sites and the aggregation node;

n 1 ≥ n 2 ≥ • • • ≥ n k ≥ 2;
• same failure probability for all links: p;

• failure events are uncorrelated.

n and n i are related by the following equation:

n = k i=1 n i (1)
Availability: the condition for availability is that all cellular sites are connected to the aggregation node. This condition is fulfilled if there is no more than one failure in each ring.

A = k i=1 (1 -p) ni+1 + (n i + 1)p(1 -p) ni (2)
If p 1, this expression can be approximated by its second-order Taylor development:

A = 1 -n p 2 2 - p 2 2 k i=1 n i 2 + o(p 2 ) (3)
Therefore,

A = 1 -n p 2 2 - p 2 2 kV (n i ) + n 2 k + o(p 2 ) ( 4
)
where V (n i ) is the empirical variance of the n i distribution:

V (n i ) = 1 k k i=1 n i - n k 2 = 1 k k i=1 n i 2 - n k
sites in the rings are as close as possible to n k . Let q and r be the quotient and the remainder of the Euclidean division of n by k:

n = qk + r; 0 ≤ r ≤ k -1 (6) Then, n 1 = • • • = n r = q + 1 and n r+1 = • • • = n k = q.
Therefore, the best availability is:

A k,p = (1 -p) q+2 + (q + 2)p(1 -p) q+1 ) r ((1 -p) q+1 + (q + 1)p(1 -p) q k-r (7)
A k,p = 1 -n p 2 2 - p 2 2 r(q + 1) 2 + (k -r)q 2 + o(p 2 ) (8) A k,p = 1 - p 2 2 (n + kq 2 + 2rq + r) + o(p 2 ) (9)
A k,p is an increasing function of k and a decreasing function of p. Of course, since the total number of antennas is 2n + 2k, increasing k increases the cost.

The results above are illustrated with the following numerical application:

p = 0.01 n = 100 2 ≤ k ≤ 50
The cost and the availability are growing functions of the number of rings k. This defines a curve of feasible. According to the price the operator is ready to pay for a given level of availability, it is possible to define an acceptable set.

Any point of the feasible curve which is inside the acceptable set is a relevant choice for the operator (Fig. 2). It should be noted that this conclusion cannot be generalized to n rings, each one of them including one cellular node: in this case, the network topology would be a star topology and a cellular site would be unavailable in case of 115 single failure. The availability of a star topology network including n cellular sites is:

A = (1 -p) n = 1 -np + o(p) (10)
As a consequence, availability is maximized when all the rings include 2 nodes, in addition to the aggregation node. Assuming that n is even, then

k = n 2 and 120 A = (1 -p) 3 + 3p(1 -p) 2 n 2 = (1 -3p 2 + 2p 3 ) n 2 = 1 - 3 2 np 2 + o(p 2 ) (11)

General model

We now assume that links may have various failure probabilities. The network includes one aggregation node (O) and n cellular sites M 1 ,M 2 ,...,M n .

Let p i be the failure probability of the link OM i and p ij the failure probability of the link M i M j .

Assuming that each ring includes the aggregation node, a ring may be defined by an ordered sequence of cellular sites.

Let us define:

V = {M 1 , M 2 , ..., M n }.
R: the set of rings including the aggregation node and cellular sites of V .

A ring r of R can be defined with an m-tuple (M i1 , M i2 , ..., M im ), made from the ordered list of the nodes of r starting from the agregation node but not including it.

The availability of r is:

A(r) = (1-p i1 )(1-p im ) m-1 l=1 (1-p i l i l+1 )+p i1 (1-p im ) m-1 l=1 (1-p i l i l+1 )+p im (1-p i1 ) m-1 l=1 (1-p i l i l+1 ) + (1 -p i1 )(1 -p im ) m-1 l=1 (1 -p i l i l+1 ) m-1 j=1 p ij ij+1 1 -p ij ij+1 (12)
For a given s ≤ n, we try to maximize the following expression:

max r1∪...∪rs=V ri∩rj =∅ k i=1 A(r i )
Particular case. n 2 rings, each one including the aggregation node and two cellular sites

In this section, we assume the following:

• n is an even number;

• the network includes n 2 rings, each one including the aggregation node and 2 cellular sites;

• for 1 ≤ i ≤ n, p i is the failure probability of the link OM i ;

• for 1 ≤ i, j ≤ n, p ij is the failure probability of the link M i M j ;

• failure events are uncorrelated.

We can calculate the availability of the ring OM i M j .

A ij = 1 -p i p j -p i p ij -p j p ij + 2p i p j p ij (13)
We try to maximize the expression:

(O,Mi,Mj )∈R A ij (14)
which is equivalent to maximize the expression:

(O,Mi,Mj )∈R log A ij (15)
The problem can be regarded as a search of a perfect matching in a weighted graph: given G = (V, E, w) an undirected weighted graph, the goal is to compute a perfect matching (ie a subset of edges E ⊆ E such that each node in V has exactly one incident edge in E ) for a maximum total weight w(E ).

The maximum 2-ring division problem can be solved efficiently (in polynomial time) as followed: given a network as described above, an undirected weighted graph G = (V, E) should be constructed where V = {M 1 , M 2 , . . . , M n } and E = (M i , M j )|1 ≤ i < j ≤ n (a full graph). The weight function w : E → R is defined as followed: ∀i, j, 1 ≤ i < j ≤ n, w(M i , M j ) = log A ij . Then, due to [START_REF] Gabow | Implementation of algorithms for maximum matching on nonbipartite graphs[END_REF], finding a maximum 2-ring division in the original network is equivalent to finding a matching M in G such that for each matching M in G,

(Mi,Mj )∈M w(M i , M j ) ≥ (Mi,Mj )∈M w(M i , M j ).
This problem is a well-known problem called maximum weighted matching.

In 1964, Jack Edmonds was the first to develop a polynomial time algorithm to solve this problem [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1 vertices[END_REF]. A straight forward implementation of Edmonds' algo- Over the years, several variants, implementations and improvements of Edmonds' idea where suggested, some of them in [START_REF] Gabow | Implementation of algorithms for maximum matching on nonbipartite graphs[END_REF], [START_REF] Gabow | An efficient implementation of Edmonds' algorithm for maximum matching on graphs[END_REF], [START_REF] Gabow | Data structures for weighted matching and nearest common ancestors with linking[END_REF]. Overall, the best know algorithm for a full graph has a running time complexity of O(|V | 3 ) [10], [START_REF] Gabow | Data structures for weighted matching and nearest common ancestors with linking[END_REF], [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. Now, solving the maximum 2-ring division problem is done in 2 phases:

1. Computing logA ij for each i,j, 1 ≤ i < j ≤ n and constructing an undirected weighted full graph G, as described earlier.

2. Solving the weighted maximum matching problem on G.

The running time complexity of phase 1 is n 2 Θ(1) + Θ(n 2 ) = Θ(n 2 ). The running time complexity of phase 2 is O(n 3 ). Therefore, the running time complexity of the proposed algorithm for solving the maximum 2-ring division problem is O(n 3 ). Hence, the decision problem corresponding to the maximum 2-ring division problem is in P.

Conclusion: it is possible to connect an even number n of cellular sites with n/2 rings, each of one including 2 cellular sites and the aggregation node. The running time is O(n 3 ).

General case. n k rings, each one including the aggregation node and k cellular sites; k ≥ 3

In this section, we assume the following:

• n is a multiple of k;

• the network includes n k rings, each one including the aggregation node and k cellular sites;

• for 1 ≤ i ≤ n, p i is the failure probability of the link OM i ;

• for 1 ≤ i, j ≤ n, p ij is the failure probability of the link M i M j ;

• failure events are uncorrelated. well-known NP-Complete problem [START_REF] Kolmogorov | Blossom V: a new implementation of a minimum cost perfect matching algorithm[END_REF], [START_REF] Hazan | On the complexity of approximating k-set 325 packing[END_REF].

We define the maximum production [0, 1) weighted k-set packing (MPWSP) as followed: given a family F = P k (n) where n = mk for some m ∈ N and a weight function w : F → [0, 1), the MPWSP problem is to find a k-set packing S of {1, 2, . . . , n} such that for each k-set packing S of F , u∈S w(u) ≥ u∈S w(u).

Let d -M P W SP denote the corresponding decision problem to MPWSP.

d -M SP is a particular case of d -M P W SP with: Given an algorithm to solve the MPWSP problem, it can be used to solve the general maximum k-ring division problem as followed: let A max i1i2...i k be the highest availability of all the rings including the k nodes i 1 , i 2 ,..., i k and the aggregation node:

• w(X) = 1 for X ∈ F • w(X) = 0 for X / ∈ F Therefore, d -M P W SP
A max i1i2...i k = max(A j1j2...j k |j 1 j 2 . . . j k is a permutation of i 1 i 2 . . . i k ) (16) and c i1i2...i k = log(A max i1i2...i k ) (17)
An instance of MPWSP could be constructed by defining a family of sets

F = P k (n) and a weight function w(i 1 , i 2 , , i k ) = A max i1i2...i k .
Clearly, a solution to the constructed MPWSP instance yields a solution to the original maximum k-ring division problem.

Reciprocally, let us consider the following particular case: In this particular case, the aggregation node is connected to all the nodes of U 1 and no other node. Every connection between the aggregation node and 210 anyone of the nodes of U 1 is assumed to be free of failure-risk. A node in a given subset U i can be connected only to the nodes belonging to the adjacent sets U i-1 and U i+1 .

V = U 1 ∪ ... ∪ U k |U 1 | = ... = |U k | = n k ∀u ∈ U 1 , p u = 0 ∀u ∈ U 2 ∪ ... ∪ U k , p u = 1 ∀u i ∈ U i , ∀u j ∈ U j , |j -i| = 1 → p ij = 1 ∀u i ∈ U i , ∀u j ∈ U j , |j -i| = 1 → p ij ∈ [0, 1]
Then, the maximization of c i1i2...i k is a k-dimensional matching problem, which is known to be NP hard [START_REF] Polyakovskiy | The three-dimensional matching problem in Kalmanson matrices[END_REF] for k ≥ 3. Therefore, the general problem is

215

NP hard for k ≥ 3.

Approximation methods

Since the general maximum k-ring division problem is NP-hard for k ≥ 3, we propose hereafter approximation methods in order to converge to the solution.

Formalization as an Integer Linear Programming Problem

We can present the k-ring division problem as an ILP: the idea is to define binary variables which correspond to a k-ring.

P = max {i1,i2,...,i k }∈P k (n) c i1i2...i k x i1i2...i k (18) subject to {i1,i2,...,i k }∈P k (n) j∈{i1,i2,...,i k } x i1i2...i k = 1, ∀j ∈ {1, 2, . . . , n} (19)
x i1i2...i k ∈ {0, 1}, ∀{i 1 , i 2 , . . . , i k } ∈ P k (n) ( 20
)
The purpose of this method is to characterize the network topology by binary values: x i1i2...i k = 1 if the nodes i 1 , i 2 , . . . , i k , together with the aggregation node, form a ring, and x i1i2...i k = 0 else.

Constraints ( 19) and (20) forces each node j to be in exactly one k-ring.

General ILP is known to be NP-Hard [START_REF] Schrijver | Theory of linear and integer programming[END_REF]. However, linear programming can be solved in polynomial time. By replacing constraint (20) in (18) with the constraint:

x i1i2...i k ≥ 0, ∀{i 1 , i 2 , . . . , i k } ∈ P k (n) (21)
(also known as LP relaxation) we get a polynomial-time solvable linear program.

Without loss of generality, we can assume that c i1i2...i k > 0 for each {i 1 , i 2 , . . . , i k } ∈ P k (n), since we can always add any constant to all the coefficients c i1i2...i k . Doing that does not change the set of vectors that maximizes the problem, because due to the constraints, each feasible vector contains exactly n k ones and n k -n k zeros. Therefore, adding K to all the coefficients c i1i2...i k is equivalent to adding the constant K n k to the original objective function.

Lemma 4.1. Assuming c i1i2...i k > 0 for each {i 1 , i 2 , . . . , i k } ∈ P k (n), a vector

x which maximizes the system

P = max {i1,i2,...,i k }∈P k (n) c i1i2...i k x i1i2...i k (22) subject to {i1,i2,...,i k }∈P k (n) j∈{i1,i2,...,i k } x i1i2...i k ≤ 1, ∀j ∈ {1, 2, . . . , n} (23)
x i1i2...i k ∈ {0, 1}, ∀{i 1 , i 2 , . . . , i k } ∈ P k (n) ( 24
)
is feasible to (18).

Proof. All we need to show is that {i1,i2,...

,i k }∈P k (n) j∈{i1,i2,...,i k } x i1i2...i k = 1, ∀j ∈ {1, 2, . . . , n}.
Assume by contradiction that there is a j for which {i1,i2,...

,i k }∈P k (n) j∈{i1,i2,...,i k } x i1i2...i k = 0
(there is no other possibility since x satisfies constraint (24); this means that there is a node j that is not in any k-ring). Since n is a multiplier of k, there are k -1 other nodes that are not in any k-ring, therefore, a new ring can be added to the sum contradicting the fact that x maximizes P . Then, max c ijl x ijl subject to (19), ( 21) is obtained only for:

x 124 = x 135 = x 236 = x 456 = 1 2 ; all other x ijl = 0 (27)

Power method

In order to favour the emergence of a maximum which has exclusively integer coordinates, we introduce an exponent α. The purpose of this exponent is penalize potential non-integer solutions.

For each α > 0 we define:

P α = max {i1,i2,...,i k }∈P k (n) c i1i2...i k x α i1i2...i k (28) subject to {i1,i2,...,i k }∈P k (n) j∈{i1,i2,...,i k } x i1i2...i k ≤ 1, ∀j ∈ {1, 2, . . . , n} (29)
x i1i2...i k ≥ 0, ∀{i 1 , i 2 , . . . , i k } ∈ P k (n) (30)
We also define x α a vector in R ( n k ) which maximizes (28) (can be one of many if there is more than one vector which maximizes P α ). Proof. x α is obviously feasible to (22). Assume by contradiction that there is y which satisfies (23) and (24) for which P (y) > P (x α ). Since all coordinates of x α and y are 0 or 1, P (x α ) = P α (x α ) and P (y) = P α (y). Therefore, P α (y) > P α (x α ), contradicting the fact that x α maximizes (28). The second equality derives from the fact that constraints (29) and (30) force that 0 ≤ x i1i2...i k ≤ 1. Hence:

• if x i1i2...i k = 1, then c i1i2...i k x α i1i2...i k = c i1i2...i k x i1i2...i k α = c i1i2...i k

• if x i1i2...i k < 1, then lim α→∞ c i1i2...i k x i1i2...i k α = 0 and c i1i2...i k x i1i2...i k α = 0 Theorem 4.5. Assuming c i1i2...i k > 0 for each {i 1 , i 2 , . . . , i k } ∈ P k (n), as α → ∞, x α maximizes (18).

Proof. From lemma (4.4), we conclude that x α maximizes (28). Then, from lemma (4.3), we conclude that x α maximizes (22). Finally, from lemma (4.2), we conclude that x α maximizes (18).

Theorem (4.5) offers an alternative way to solve (18) for a large α and select the floor values of the elements in x α .

Conclusion

Availability is maximized when the number of rings is high and the ring size distribution is regular. In this paper, we show that the partition of a network including an aggregation node and n cellular sites into n 2 rings, each one including the aggregation node and 2 cellular sites, can be solved in a time of O(n 3 ). Regarding a partition with larger rings, the problem is similar to a k-set partition problem, which is NP-hard for k ≥ 3. We propose an approximation method, based on linear programming and use of an exponent aimed to accelerate the convergence.

Figure 1 :

 1 Figure 1: Backhaul network. The aggregation node handles all the traffic produced by and to nodes M1, M2, M3.

Figure 2 :

 2 Figure 2: Cost-Availability balance.

  rithm will have a running time complexity of O(|V | 2 |E|), and hence in our problem O(|V | 4 ) (because the constructed graph is fully meshed. i.e. E = Θ(|V | 2 )).

  At first, we investigate the relation between the general maximum k-ring division problem and an NP-Complete problem. Let P k (n) be the set of k-combinations of {1, 2, . . . , n}. Given a family of sets F ⊆ P k (n) for k ≥ 3, a k-set packing of {1, 2, . . . , n} is a set S ⊆ F such that ∀s 1 , s 2 ∈ S, s 1 ∩ s 2 = ∅. The maximum k-set packing problem (MSP) is to find a k-set packing S of {1, 2, . . . , n} such that for each k-set packing S of {1, 2, . . . , n}, |S| ≥ |S |. The corresponding decision problem (d -M SP ) is a

  is as least as hard as d -M SP . Thus, d-MPWSP is NP-Hard (and in fact, d-MPWSP is NP-Complete).

Figure 3 :

 3 Figure 3: Particular case of k-ring division.

Lemma 4 . 2 .

 42 Assuming c i1i2...i k > 0 for each {i 1 , i 2 , . . . , i k } ∈ P k (n), a vector x which maximizes (22) maximizes (18).Proof. Straight from Lemma (4.1) and from the fact that any feasible vector in (18) is a feasible vector in (22). However, not each solution to the relaxation yields a solution to the original problem. Consider the following example: n = 6; k = 3 (25) c 124 = c 135 = c 236 = c 456 = 1; all other c ijl = 0 (26)

Lemma 4 . 3 .

 43 If x α ∈ {0, 1} ( n k ) , then x α maximizes (22).

Lemma 4 . 4 .

 44 lim α→∞ P α (x α )=lim α→∞ P α ( x α ) Proof. lim α→∞ P α (x α ) = lim α→∞ xi 1 i 2 ...i k coordinates of xα c i1i2...i k x α i1i2...i k = lim α→∞ xi 1 i 2 ...i k coordinates of xα c i1i2...i k x i1i2...i k α = lim α→∞ P α ( x α ) (31)

[START_REF] Nadiv | Wireless Backhaul Topologies: Analysing Backhaul Topology Strategies[END_REF] Therefore, increasing the number of rings reduces the maximum path length and unavailability. On the other hand, it requires more antennas. In any case, given the number of rings, it is preferable that the empirical variance of the ring size distribution be as small as possible.For a given number of rings k, the maximum availability is obtained when the empirical variance is minimized, which means when the numbers of cellular

Acknowledgments

The authors would like to thank Yosef Pogrow for his highly valuable contribution to this work and to acknowledge the contribution of the COST action TD1207. The authors alone are responsible for the content. This research was funded by the Office of the Chief Scientist of the Israel Ministry of Economy under the Neptune generic research project. Neptune is the Israeli consortium for network programming.