Raouf Kerkouche

Gergely Ács

Claude Castelluccia

Pierre Genevès

Constrained Differentially Private Federated Learning for Low-bandwidth Devices

Federated learning becomes a prominent approach when different entities want to learn collaboratively a common model without sharing their training data. However, Federated learning has two main drawbacks. First, it is quite bandwidth inefficient as it involves a lot of message exchanges between the aggregating server and the participating entities. This bandwidth and corresponding processing costs could be prohibitive if the participating entities are, for example, mobile devices. Furthermore, although federated learning improves privacy by not sharing data, recent attacks have shown that it still leaks information about the training data. This paper presents a novel privacy-preserving federated learning scheme. The proposed scheme provides theoretical privacy guarantees, as it is based on Differential Privacy. Furthermore, it optimizes the model accuracy by constraining the model learning phase on few selected weights. Finally, as shown experimentally, it reduces the upstream and downstream bandwidth by up to 99.9% compared to standard federated learning, making it practical for mobile systems.

INTRODUCTION

In Machine Learning, different entities may want to collaborate in order to improve their local model accuracy. In traditional machine learning, such collaboration requires to first store all entities' data on a centralized server and then to train a model on it. Such data centralization might be problematic when the data are sensitive and data privacy is required. In order to mitigate this problem, Federated learning, which allows different entities to learn collaboratively a common model without sharing their data, was introduced [Shokri andShmatikov, 2015, McMahan et al., 2016]. In-stead of sharing the training data, Federated Learning shares the model parameters between a server, which plays the role of aggregator, and the participating entities. Although Federated Learning improves privacy, model parameters can leak information about the training data. Indeed, [START_REF] Zhu | Deep leakage from gradients[END_REF], [START_REF] Zhao | idlg: Improved deep leakage from gradients[END_REF], [START_REF] Geiping | Inverting gradients -how easy is it to break privacy in federated learning?[END_REF] presented some attacks that allow an adversary to reconstruct pieces of the training data of some entities. [START_REF] Nasr | Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning[END_REF] define a membership attack that allows to infer if a particular record is included in the data of a specific entity. Similarly, [START_REF] Melis | Inference attacks against collaborative learning[END_REF] define an attack which aims at inferring if a subgroup of people with a specific property, like for example skin color or ethnicity, is included in the dataset of a particular participating entity. A solution to prevent these attacks and provide theoretical guarantees in to use a privacy model called Differential Privacy [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]. Differential Privacy has been applied to federated learning in order to protect either each record included in the dataset of any entity (record-level guarantee), or the whole dataset of any entity (client-level guarantee). Unfortunately, it is well-known that Differential Privacy drastically degrades the accuracy of the global model as it requires to add random noise to the gradients (record-level) or to the updates (client-level) of each client. Recent work by [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] shows that this accuracy penalty can be reduced if the model is compressed, as compression reduces the required amount of noise. Furthermore, [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] show that accuracy can be further improved by adding noise only to the largest update's values as adding noise on values close to 0 is likely to lead to random update values.

Following up on these results, we propose a novel differentially private federated learning solution that improves the model accuracy (1) by updating only a fixed subset of the model weights, and (2) by maintaining the other weights constant. The proposed scheme provides theoretical privacy guarantees, as it is based on Differential Privacy. Furthermore, it optimizes the model accuracy by constraining the model learning phase on a few selected weights. As all participants always update the same set of weights and transfer them to the server for aggregation, the proposal can be easily integrated with secure aggregation [START_REF] Bonawitz | Practical secure aggregation for federated learning on user-held data[END_REF], which allows parties to add less noise than other decentralized perturbation approaches such as randomized response [START_REF] Erlingsson | RAPPOR: randomized aggregatable privacy-preserving ordinal response[END_REF] used in local differential privacy. Moreover, it also reduces the upstream and downstream bandwidth by a factor of 1000 compared to standard federated learning, making it practical for mobile systems. The paper is structured as follows: In Section 2 we introduce the necessary background to understand the proposal, in Section 3 we define our solution called FL-TOP and in Section 3.2 its private extension called FL-TOP-DP.

BACKGROUND 2.1 FEDERATED LEARNING (FL-STD)

In federated learning [Shokri andShmatikov, 2015, McMahan et al., 2016], multiple parties (clients) build a common machine learning model from union of their training data without sharing them with each other. At each round of the training, a selected set of clients retrieve the global model from the parameter server, update the global model based on their own training data, and send back their updated model to the server. The server aggregates the updated models of all clients to obtain a global model that is re-distributed to some selected parties in the next round.

In particular, a subset K of all N clients are randomly selected at each round to update the global model, and C = |K|/N denotes the fraction of selected clients. At round t, a selected client k ∈ K executes T gd local gradient descent iterations on the common model w t-1 using its own training data D k (D = ∪ k∈K D k ), and obtains the updated model w k t , where the number of weights is denoted by n (i.e., |w k t | = |∆w k t | = n for all k and t). Each client k submits the update ∆w k t = w k t -w k t-1 to the server, which then updates the common model as follows:

w t = w t-1 + ∑ k∈K |D k | ∑ j |D j | ∆w k t ,
where |D k | is known to the server for all k (a client's update is weighted with the size of its training data). The server stops training after a fixed number of rounds T cl , or when the performance of the common model does not improve on a held-out data.

Note that each D k may be generated from different distributions (i.e., Non-IID case), that is, any client's local dataset may not be representative of the population distribution [McMahan et al., 2016]. This can happen, for example, when not all output classes are represented in every client's training data. The federated learning of neural networks is summarized in Alg. 4. In the sequel, each client is assumed to use the same model architecture.

The motivation of federated learning is three-fold: first, it aims to provide confidentiality of each participant's training data by sharing only model updates instead of potentially sensitive training data. Second, in order to decrease communication costs, clients can perform multiple local SGD iterations before sending their update back to the server. Third, in each round, only a few clients are required to perform local training of the common model, which further diminishes communication costs and makes the approach especially appealing with large number of clients. However, several prior works have demonstrated that model updates do leak potentially sensitive information [START_REF] Nasr | Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning[END_REF][START_REF] Melis | Inference attacks against collaborative learning[END_REF]. Hence, simply not sharing training data per se is not enough to guarantee their confidentiality.

DIFFERENTIAL PRIVACY

Differential privacy allows a party to privately release information about a dataset: a function of an input dataset is perturbed, so that any information which can differentiate a record from the rest of the dataset is bounded [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF].

Definition 1 (Privacy loss). Let A be a privacy mechanism which assigns a value Range(A ) to a dataset D. The privacy loss of A with datasets D and D at output

O ∈ Range(A ) is a random variable P(A , D, D , O) = log Pr[A (D)=O] Pr[A (D )=O]
where the probability is taken on the randomness of A .

Definition 2 ((ε, δ )-Differential Privacy [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF]). A privacy mechanism A guarantees (ε, δ )differential privacy if for any database D and D , differing on at most one record,

Pr O∼A (D) [P(A , D, D , O) > ε] ≤ δ .
Intuitively, this guarantees that an adversary, provided with the output of A , can draw almost the same conclusions (up to ε with probability larger than 1δ ) about any record no matter if it is included in the input of A or not. That is, for any record owner, a privacy breach is unlikely to be due to its participation in the dataset.

Moments Accountant. Differential privacy maintains composition; the privacy guarantee of the k-fold adaptive composition of A 1:k = A 1 , . . . , A k can be computed using the moments accountant method [START_REF] Abadi | Deep learning with differential privacy[END_REF]. In particular, it follows from Markov's inequality that Pr

[P(A , D, D , O) ≥ ε] ≤ E[exp(λ P(A , D, D , O))]/ exp(λ ε) for any out- put O ∈ Range(A ) and λ > 0. A is (ε, δ )-DP with δ = min λ exp(α A (λ ) -λ ε), where α A (λ ) = max D,D log E O∼A (D) [exp(λ P(A , D, D , O))]
is the log of the moment generating function of the privacy loss. The privacy guarantee of the composite mechanism A 1:k can be computed using that α A

1:k (λ ) ≤ ∑ k i=1 α A i (λ ) Abadi et al. [2016].
Gaussian Mechanism. A fundamental concept of all DP sanitization techniques is the global sensitivity of a function [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF].

Definition 3 (Global L p -sensitivity). For any function f : The Gaussian Mechanism [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] consists of adding Gaussian noise to the true output of a function. In particular, for any function f : D → R n , the Gaussian mechanism is defined as adding i.i.d Gaussian noise with variance (∆ 2 f • σ ) 2 and zero mean to each coordinate value of f (D).

D → R n , the L p -sensitivity of f is ∆ p f = max D,D || f (D) - f (D )|| p ,
Recall that the pdf of the Gaussian distribution with mean

µ and variance ξ 2 is pdf G (µ,ξ ) (x) = 1 √ 2πξ exp -(x-µ) 2 2ξ 2 .
In fact, the Gaussian mechanism draws vector values from a multivariate spherical (or isotropic) Gaussian distribution which is described by random variable

G ( f (D), ∆ 2 f • σ I n ),
where n is omitted if its unambiguous in the given context.

FEDERATED PRUNING

In the standard federated learning scheme (FL-STD, in Section 2), the server sends the latest updated model to a randomly selected set of clients (downstream), and each client sends back its complete model update after local training to the server (upstream) at each round. Knowing that a model has on average millions of parameters (each is a floating point value represented on 32 bits), the network can suffer from large traffic both upstream and downstream.

Our solution, called FL-TOP, aims to reduce the large amount of network traffic by reducing both downstream and upstream traffic. Moreover, a privacy-preserving extension of this scheme, called FL-TOP-DP, is also proposed, which provides Differential Privacy for the whole training data of every client.

In what follows, we first describe the non-private scheme FL-TOP and then the privacy-preserving FL-TOP-DP.

FL-TOP: FEDERATED PRUNING FOR COMPRESSION

FL-TOP is inspired by the pruning techniques proposed in [START_REF] Han | Dsd: Dense-sparse-dense training for deep neural networks[END_REF] (see Section 5 for more details), and it aims to reduce the amount of parameters exchanged downstream (from the server to the participating entities) and upstream (from the participating entities to the server). In our scheme, each client updates only a small subset, Top-K, of the model parameters (weights) at each round. Only the K weight values of these Top-K parameters are updated during training, and neither the clients nor the server need to transfer the values of the remaining n -K parameters, where n is the total number of parameters. The set of Top-K parameters do not change over the whole training and are identical for all clients. We experimentally show in Section 4 that, if these K parameters are chosen carefully, the performance penalty is negligible even if K = 0.005 • n, that is, 99.5% of the model parameters are pruned. Note that unlike standard pruning techniques, where the set of pruned weights are re-selected after each SGD iteration [START_REF] Han | Dsd: Dense-sparse-dense training for deep neural networks[END_REF], our scheme always updates the same K parameters.

These Top-K parameters are selected by the server at the beginning of the protocol. More specifically, the server initializes the model and trains that with some public data that have a similar distribution as the clients' training data. After a few SGD iterations, the server selects the K parameters which values changed the most.

FL-TOP is described in Alg. 1. First, the server uses public data to identify the set T of the Top-K parameters (K = |T|), before starting federated learning. In particular, starting from a public model w 0 , it accumulates the absolute value of gradients per parameter over T init SGD iterations, and selects the K parameters with the largest accumulated gradients.

After that, the values/updates1 of these parameters are the only ones exchanged during the rest of the training between the server and the clients.

At each round, each selected client k uses the K updated weights ŵt-1 received from the server to create a new weight vector w k t-1 of size n, such that w k t-1 is composed from the compressed vector ŵk t-1 of size K ≤ n (with coordinates in T) and n -K weights from the initialization vector w 0 . w 0 is identical for all participants and can be generated from a shared seed. Note that when K = |T| = n, the scheme is equivalent to FL-STD. The weight vector w k t-1 is used to train the client's model. However, only the weights in T are updated while the remaining ones are kept fixed. To do that, the weights not in T are reinitialized after each SGD iteration to w 0 . The server receives only the values from w k t -w k t-1 at coordinates T, denoted by C (w k t -w k t-1 ) for short, from every client k, and updates the common model w t with the average of these compressed updates (in Line 12).

FL-TOP-DP: DIFFERENTIALLY PRIVATE FEDERATED PRUNING

Privacy Model

We consider an adversary, or a set of colluding adversaries, who can access any update vector sent by the server or any clients at each round of the protocol. A plausible adversary is a participating entity, i.e. a malicious client or server, that wants to infer the training data used by other participants. The adversary is passive (i.e., honest-but-curious), that is, it follows the learning protocol faithfully.

Different privacy requirements can be considered depending on what information the adversary aims to infer. In general, private information can be inferred about:

• any record (user) in any dataset of any client (recordlevel privacy),

• any client/party (client-level privacy).

To illustrate the above requirements, suppose that several banks build a common model to predict the creditworthiness of their customers. A bank certainly does not want other banks to learn the financial status of any of their customers (record privacy) and perhaps not even the average income of all their customers (client privacy).

Record-level privacy is a standard requirement used in the privacy literature and is usually weaker than client-level privacy. Indeed, client-level privacy requires to hide any information which is unique to a client including perhaps all its training data.

We aim at developing a solution that provides client-level privacy and is also bandwidth efficient. For example, in the scenario of collaborating banks, we aim at protecting any information that is unique to each single bank's training data. The adversary should not be able to learn from the received model or its updates whether any client's data is involved in the federated run (up to ε and δ ). We believe that this adversarial model is reasonable in many practical applications when the confidential information spans over multiple samples in the training data of a single client (e.g., the presence of a group a samples, such as people from a certain race). Differential Privacy guarantees plausible deniability not only to any groups of samples of a client but also to any client in the federated run. Therefore, any negative privacy impact on a party (or its training samples) cannot be attributed to their involvement in the protocol run.

Operation

FL-TOP-DP is described in Alg. 3 is very similar to FL-TOP except that each client adds Gaussian noise to its Top-K model updates to guarantee client-level DP, and applies secure aggregation allowing the server to learn only the aggregated (and noisy) model update. More specifically, each client first calculates its compressed model update

∆w k t = C (w k t -w k t-1 ) (in Line 25) which is then clipped (in Line 26) to obtain ∆ ŵk t with L 2 -norm at most S. After that, random noise z k ∼ G (0, Sσ I/ √ K) is added to ∆ ŵk t such that the sum ∑ k∈K (∆ ŵk t + z k ) = ∑ k∈K ∆ ŵk t + G (0, Sσ I)
as the sum of Gaussian random variables also follows Gaussian distribution2 and then differential privacy is satisfied where ε and δ can be computed using the moments accountant described in Section 2.2. Recall that the Top-K coordinates in T are selected and distributed by the server, which is honest-but-curious by assumption.

However, as the noise is inversely proportional to √ K, z k is likely to be small if |K| is too large. Therefore, the adversary accessing an individual update ∆ ŵk t + z k can almost learn a non-noisy update since z k is small. Hence, each client uses secure aggregation to encrypt its individual update before sending it to the server. Upon reception, the server sums the encrypted updates as:

∑ k∈K c k t = ∑ k∈K Enc K k (∆ ŵk t + z k ) = ∑ k∈K ∆ ŵk t + ∑ k∈K z k = ∑ k∈K ∆ ŵk t + G (0, Sσ I) (1)
where [START_REF] Ács | I have a dream! (differentially private smart metering)[END_REF], [START_REF] Bonawitz | Practical secure aggregation for federated learning on user-held data[END_REF] for details). Here the modulo is taken element-wise and

Enc K k (∆ ŵk t + z k ) = ∆ ŵk t + z k + K k mod p and ∑ k K k = 0 (see
p = 2 log 2 (max k ||∆ ŵk t +z k || ∞ |K|) . Let γ k t = 1/ max 1, ||∆w k t || 2 S . Then, ∑ k∈K ∆ ŵk t = ∑ k∈K γ k t ∆w k t = ∑ k∈K γ k t C (w k t -w k t-1 , T) = C ( ∑ k∈K γ k t (w k t -w k t-1 ), T) (2)
where the last equality comes from the linearity of the compression operation. Indeed, recall that each client selects the values of the same Top-K coordinates from T. Plugging Eq. (2) into Eq. ( 1). we get that

∑ k∈K c k t = C ( ∑ k∈K γ k t (w k t -w k t-1 ), T) + G (0, Sσ I)
Privacy analysis: The server can only access the noisy aggregate which is sufficiently perturbed to ensure differential privacy; any client-specific information that could be inferred from the noisy aggregate is tracked and quantified by the moments accountant, described in Section 2.2, as follows.

Let

η 0 (x|ξ ) = pdf G (0,ξ ) (x) and η 1 (x|ξ ) = (1 -C)pdf G (0,ξ ) (x) + Cpdf G (1,ξ ) (x) where C is the sampling probability of a single client in a single round. Let α(λ |C) = log max(E 1 (λ , ξ ,C), E 2 (λ , ξ ,C)) where E 1 (λ , ξ ,C) = R η 0 (x|ξ ,C) • η 0 (x|ξ ,C) η 1 (x|ξ ,C) λ dx and E 2 (λ , ξ ,C) = R η 1 (x|ξ ,C) • η 1 (x|ξ ,C) η 0 (x|ξ ,C) λ dx. Theorem 1 (Privacy of FL-TOP-DP). FL-TOP-DP is (min λ (T cl • α(λ |C) -log δ )/λ , δ )-DP.
Given a fixed value of δ , ε is computed numerically as in [START_REF] Abadi | Deep learning with differential privacy[END_REF], [START_REF] Mironov | Rényi differential privacy of the sampled gaussian mechanism[END_REF].

for each client k in K do c k t = Client k (C (w t-1 , T)) end w t = w 0 j = 1 for each coordinate i in T do w t [i] = w t-1 [i] + ∑ k c k t [ j] |K| j = j + 1 end end Output: Global model w t
Client k ( ŵk t-1 ):

w k t-1 = w 0 j = 1 for each coordinate i in T do w k t-1 [i] = ŵk t-1 [ j] j = j + 1 end w k t = Top k SGD(D k , w k t-1 , w 0 , T gd , T) Output: Model update C (w k t -w k t-1 , T)

Remarks

The magnitude of the added Gaussian noise is proportional to the clipping threshold S, which is in turn calibrated to the norm of the model update. However, the norm of the model update increases if the model size increases [START_REF] Zhu | Voting-based approaches for differentially private federated learning[END_REF], and hence S should be chosen sufficiently large to guarantee fast convergence with large accuracy. On the other hand, too large S also increases the perturbation error caused by the added noise.

FL-TOP aims to diminish this perturbation error by reducing S via compression which also increases the L 2 -norm of the compressed update vector. This is illustrated in Figure 1, which shows that the norm of the Top-K coordinates with FL-TOP tend to be larger than with FL-STD (i.e., when all coordinates get updated not only the Top-K). Therefore, besides decreasing the magnitude of the added noise, FL-TOP also decreases the relative error on the retained parameters. These together decrease the perturbation error caused by the added noise.

Notice that there exist other alternatives to identify the Top-K coordinates in a privacy-preserving manner than using a public dataset. For example, every client can select the Top-K parameters with the largest magnitude during the first More specifically, each client creates a parameter vector with size n, where the Top-K coordinates are set to 1 while the rest are kept 0. Then, these binary vectors are noised and aggregated by the server like in Section 3.2.2. In the rest of the training, all participants exchange only the updates and weights of the these Top-K parameters like in FL-TOP. However, aside from consuming more privacy budget, this approach also has lower accuracy than our proposal according to our tests. Moreover, it has larger communication cost in the initialization phase when the Top-K parameters are identified and the whole binarized parameter vector is sent for aggregation.

EXPERIMENTAL RESULTS

The goal of this section is to evaluate the performance of our proposed schemes FL-TOP and FL-TOP-DP on a benchmark dataset and a realistic in-hospital mortality prediction scenario. We aim at evaluating their performance with different levels of compression and comparing them with the performance of the following learning protocols3 :

• FL-STD: The Standard Federated Learning scheme as described in Section 2.1 (see Alg. 4).

• FL-BASIC: A Federated Learning scheme that updates a random subset of parameters instead of the Top-K parameters at each SGD iteration. This subset is reselected at the beginning of each new round. The nk non-selected parameters are still reinitialized after each SGD update as in FL-TOP.

• FL-CS: A Federated Learning scheme that uses Compressive sensing (CS) to compress model updates from [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF]. See Section 5 for more details.

Note that all compression operators in the baselines are linear (just like FL-TOP-DP), and hence they can also be used with secure aggregation. Similarly to FL-TOP-DP, the

for each client k in K do c k t = Client k (C (w t-1 , T)) end w t = w 0 j = 1 for each coordinate i in T do w t [i] = w t-1 [i] + ∑ k c k t [ j] |K| j = j + 1 end end Output: Global model w t
Client k ( ŵk t-1 ):

w k t-1 = w 0 j = 1 for each coordinate i in T do w k t-1 [i] = ŵk t-1 [ j] j = j + 1 end w k t = Top k SGD(D k , w k t-1 , w 0 , T gd , T) ∆w k t = C (w k t -w k t-1 , T) ∆ ŵk t = ∆w k t / max 1, ||∆w k t || 2 S Output: Enc K k (G (∆ ŵk t , SIσ / |K|))
private extensions (i.e., FL-STD-DP, FL-BASIC-DP and FL-CS-DP) also clip and then noise the compressed updates.

We evaluate the above learning algorithms on the wellknown Fashion-MNIST dataset [START_REF] Xiao | Fashionmnist: a novel image dataset for benchmarking machine learning algorithms[END_REF] and on the Premier Healthcare Database, which is a real-world medical dataset of 1.2 millions of US hospital patients 4 . More details can be found in Appendix A.1 and Appendix B.1.

Recall that the Top-K weights are selected before starting the federated learning process using public data. For Fashion-MNIST, we randomly select a batch with size 10 from MNIST dataset [LeCun and Cortes, 2010] described in Appendix B.2. For the medical dataset, we did not find any public dataset with the same features as ours, and for this reason, we selected randomly from the dataset a batch of 356 patients 5 . This set is used only by the server and never by any client. Afterwards, the server performs T init SGD iterations starting from the model parameters w 0 on the same batch to identify the Top-K weights. We experi-4 https://www.premierinc.com/newsroom/education/premierhealthcare-database-whitepaper 5 Reduced to 24 patients when we train via downsampling with 12 patients for each class mentally show later that even these small batches are enough for the server to find a good set of Top-K weights.

In order to select the clipping threshold S, the server executes a single training round locally, which is composed of T gd SGD iterations starting from the model parameters w 0 , using the batch from the public data. The clipping threshold S is set to the L 2 -norm of the Top-K weight update obtained for this single training round. For FL-BASIC-DP, the same steps are repeated for 100 times, where a new random set of trainable weights with size K are selected each time, which yields 100 L 2 -norm values. S is set to the median of these L 2 -norm values. We think that this approach is more fair, because the set of trainable weights is re-selected at each round in FL-BASIC-DP. The computed values of S can be found in Table 6 and Table 7 for Fashion-MNIST and Medical dataset, respectively. More information about the model architectures and the hyper-parameter selection can be found in Appendix A.

RESULTS

Figure 1 displays the distribution of the Top-K updated weights for FL-TOP and FL-STD at the end of the training. We select the weights when each scheme reached the best accuracy over 200 and best balanced accuracy6 over 100 rounds for fashion-MNIST and the medical dataset, respectively. We choose the smallest compression ratio r that leads to the best accuracy for the FL-TOP-DP scheme. Table 1 shows that FL-TOP-DP reaches the best accuracy, 0.81, when r = 0.5% on fashion-MNIST and reaches the best accuracy, 0.69, when r = 0.1% on the medical dataset. Both figures validate the intuition that by constraining the model to update only a small set K of the total weights, these Top-K become more important and reach larger values. This result is important when differential privacy is used as it leads to larger value-to-noise level and therefore better performance.

Table 1 represents the best accuracy over 200 rounds for each scheme on the Fashion-MNIST dataset. Round corresponds to the round when the best accuracy is reached and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round ×C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = |T| n , |T| is the compressed model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy. These tables show that the proposed non-private scheme FL-TOP has similar accuracy than the standard scheme FL-STD but reduces the bandwidth cost significantly. For example, with the Fashion-MNIST dataset, the FL-TOP accuracy reaches 0.85 when the compression ratio r = 10%. In comparison, the standard FL-STD scheme reaches an accuracy of 0.86% but consumes 10 times more bandwidth. Furthermore, although FL-CS reaches the same accuracy than FL-TOP and consumes slightly less bandwidth upstream (9% less), its required downstream bandwidth is about 10 times larger (See Table 1 for more details). The results on the medical dataset are quite similar. In fact, FL-TOP achieves its best balanced accuracy (0.74) and AUROC (0.82) when r = 10% while the FL-STD scheme obtains similar performance but required about 11 times more upsteam and downstream bandwidth cost. FL-CS achieves similarly accuracy at r = 10% as FL-TOP but its downstream required bandwidth is about 11 times larger (see Table 2 for more details).

The results also show that not only our privacy-preserving solution FL-TOP-DP provides strong privacy guarantee (with ε values smaller than 1) but that it outperforms the other schemes in term of accuracy and bandwidth, for both datasets. For example, with Fashion-MNIST, our scheme achieves an accuracy of 0.81 when r = 0.5% while the baseline scheme, FL-BASIC-DP, achieves an accuracy of 0.79 when r = 10% and requires 189 times more downstream bandwidth and 18 times more upstream bandwidth. With the medical dataset, FL-TOP-DP reaches the best balanced accuracy 0.69 and best AUROC 0.76 for a compression ratio of r = 0.1% while FL-BASIC-DP and FL-CS-DP achieves the same performance at r = 5%. Note that FL-STD-DP performs very poorly as noise has to be added to the all weights of the model and the sensitivity is large (see Table 2).

RELATED WORK

Privacy of Federated Learning: The concept of Clientbased Differential Privacy has been introduced in McMahan et al. [2018] and [START_REF] Geyer | Differentially private federated learning: A client level perspective[END_REF], where the goal is to hide any information that is specific to a single client's training data. These algorithms noise the contribution of a single client instead of a single record in the client's dataset. The noise is added by the server, hence, unlike our solution, these works assume that the server is trusted.

Recently, [START_REF] Liu | Fedsel: Federated sgd under local differential privacy with top-k dimension selection[END_REF] also proposed to add noise only to the update of the Top-K model parameters a la local-DP.

In local-DP, each client adds larger noise that what is necessary to guarantee DP for the aggregated model update without using secure aggregation. Therefore, the common model is less accurate than with our scheme. In addition, [START_REF] Liu | Fedsel: Federated sgd under local differential privacy with top-k dimension selection[END_REF] uses two epsilon budgets; one for selecting Top-K parameters per client, and the second for perturbing these selected Top-K parameters. By contrast, we select the Top-K parameters via public data without sacrificing any privacy budget. Finally, their solution is also less bandwidth efficient than ours: as the Top-K parameters differ for each client and at each round, the client cannot send only the Top-K parameters values because the server will not be able to identify which value corresponds to which Top-K parameter.

For this reason, the client has to send a sparse vector with only Top-K perturbed values and all remaining parameters set to 0. Therefore, the quantization of the non-Top-K parameters is performed only during the upstream (from client to server) without compressing any downstream traffic. As opposed to this, in our solution, only the weights/updates of the Top-K parameters are transferred downstream/upstream.

Recently, [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] proposed to use Compressive sensing (CS) in the context of federated learning in order to compress model updates meanwhile providing client-level DP. Assuming that the model update is already sparse in the time domain, the noise is added to its largest Fourier coefficients in a distributed manner, and the noisy aggregate is reconstructed with standard optimization techniques. Likewise our solution, this work also uses secure aggregation by exploiting the linearity of CS. However, the reconstruction process can be slow for large models, and therefore our solution is more scalable. Moreover, it can only compress the upstream traffic.

Bandwidth Optimization in Federated Learning: Different quantization methods have been proposed to save the bandwidth and reduce the communication costs in federated learning. They can be divided into two main groups: unbiased and biased methods. The unbiased approximation techniques use probabilistic quantization schemes to compress the stochastic gradient and attempt to approximate the true gradient value as much as possible [START_REF] Alistarh | QSGD: randomized quantization for communicationoptimal stochastic gradient descent[END_REF][START_REF] Wen | Terngrad: Ternary gradients to reduce communication in distributed deep learning[END_REF], Wang et al., 2018[START_REF] Jakub Konecný | Federated learning: Strategies for improving communication efficiency[END_REF]. However, biased approximations of the stochastic gradient can still guarantee convergence both in theory and practice [START_REF] Bernstein | signsgd: compressed optimisation for non-convex problems[END_REF][START_REF] Lin | Deep gradient compression: Reducing the communication bandwidth for distributed training[END_REF][START_REF] Seide | 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns[END_REF]. SignSGD [START_REF] Bernstein | signsgd: compressed optimisation for non-convex problems[END_REF] a quantization protocol allows to compress during downstream and upstream traffic but requires the use of all the clients at each round which is not realistic in the context of federated settings because each client is available only during few rounds [START_REF] Kairouz | Advances and open problems in federated learning[END_REF].

A different line of works exploit the sparsity of model updates to compress them. Amiri and Gündüz [2019a,b] proposed to use a compressive sensing for federated learning in order to compress model updates without privacy guarantees. However, they assume that all clients participate in each round (as they maintain an error accumulation vector at each client due to the compression scheme), but as discussed in [START_REF] Kairouz | Advances and open problems in federated learning[END_REF] this assumption is not always realistic. Sketching was adapted to federated learning for the purpose of compressing model updates in [START_REF] Ivkin | Communication-efficient distributed sgd with sketching[END_REF] and [START_REF] Rothchild | Fetchsgd: Communication-efficient federated learning with sketching[END_REF]. The authors proposed to use Count-Sketch from [START_REF] Charikar | Finding frequent items in data streams[END_REF] to retrieve the largest weights in the update vector on the server side. However, it is unclear how these works can be extended with privacy guarantees. Moreover, unlike our technique, they do not compress downstream traffic.

Constraining the weights to have a specific distribution has already been studied. In [START_REF] Han | Dsd: Dense-sparse-dense training for deep neural networks[END_REF], for example, the authors use pruning techniques to create a sparse model at the end of the training. After each SGD iteration, the authors zero-out all the weights with an absolute value smaller than a threshold. Iterating the process leads to a sparse model with only some absolute weight values larger than 0. Similarly, [START_REF] Courbariaux | Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 or -1[END_REF] aim to create a model with binary weights such that at the end of the training all the weights are close to 1 or -1. After each SGD update, the authors take the sign of the weights before the next update. After some iterations, the weight values become close to the interval limits -1 and 1.

In [START_REF] Frankle | The lottery ticket hypothesis: Training pruned neural networks[END_REF], a new hypothesis claims that there exists a sub-network which, if trained separately, can achieve similar performance as the complete network model which contains that. To find such a sub-network, one has to follow a simple iterative procedure: train the complete network, prune the smallest weights, and then reinitialize the remaining weights to their original values. These steps are repeated iteratively. This approach was extended to federated learning in [START_REF] Li | Lotteryfl: Personalized and communication-efficient federated learning with lottery ticket hypothesis on non-iid datasets[END_REF].

CONCLUSION

This paper presents a novel privacy-preserving federated learning scheme that reduces bandwidth, latency and therefore power consumption. The proposed scheme is based on Differential Privacy and therefore provides theoretical privacy guarantees. Furthermore, it optimizes the model accuracy by constraining the model learning phase on few selected weights. We show experimentally, using a public dataset called Fashion-MNIST and a real world medical dataset of 1.2 millions of US hospital patients, that it reduces the upstream and downstream bandwidth by up to 99.9% compared to standard federated learning, making it practical for constrained and mobile devices.

A MEDICAL DATA: DATA PRE-PROCESSING & EXPERIMENTAL SETUP DETAILS

This section describes our medical dataset and the experimental setting which is used to evaluate the accuracy and the privacy of our proposals.

A.1 MEDICAL DATASET

A.1.1 The In-hospital Mortality Prediction Scenario

The ability to accurately predict the risks in the patient's perspectives of evolution is a crucial prerequisite in order to adapt the care that certain patients receive [START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF].

We consider the scenario where several hospitals are collaborating to train models for in-hospital mortality prediction using our Federated Learning schemes. This well-studied real-world problem consists in trying to precisely identify the patients who are at risk of dying from complications during their hospital stay [START_REF] Avati | Improving palliative care with deep learning[END_REF][START_REF] Rajkomar | Scalable and accurate deep learning with electronic health records[END_REF][START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF]. As commonly found in the literature [START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF], for such predictions, we focus on hospital admissions of adults hospitalized for at least 3 days, excluding elective admissions.

A.1.2 The Premier Healthcare Database

We used EHR data from the Premier healthcare database7 which is one of the largest clinical databases in the United States, collecting information from millions of patients over a period of 12 months from 415 hospitals in the USA [START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF]. These hospitals are supposedly representative of the United States hospital experience [START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF]. Each hospital in the database provides discharge files that are dated records of all billable items (including therapeutic and diagnostic procedures, medication, and laboratory usage) which are all linked to a given patient's admission [Fejza et al., 2018, Makadia and[START_REF] Makadia | Transforming the premier perspective® hospital database into the observational medical outcomes partnership (omop) common data model[END_REF].

The initial snapshot of the database used in our work (before pre-processing step) comprises the EHR data of 1,271,733 hospital admissions. Electronic Health Record (EHR) is a digital version of a patient's paper chart readily available in hospitals. For developing supervised learning and specifically deep learning models, we focus on a specific set of features from EHR data. The features of interest that capture the patients information are summarized in Table 3. There is a total of 24,428 features per patient, mainly due to the variety of drugs possibly served. As in [START_REF] Avati | Improving palliative care with deep learning[END_REF],

we also removed all the features which appear on less than

The Medication regimen complexity index (MRCI) [START_REF] Mcdonald | Automating the medication regimen complexity index[END_REF] is an aggregate score computed from a total of 65 items, whose purpose is to indicate the complexity of the patient's situation. The minimum MRCI score for a patient is 1.5, which represents a single tablet or capsule taken once a day as needed (single medication). However the maximum is not defined since the number of medications increases the score [START_REF] Mcdonald | Automating the medication regimen complexity index[END_REF]. In our case, after statistical analysis of our dataset, we consider the MRCI score as ranging from 2 to 60.

Most real datasets like ours are generally imbalanced with a skewed distribution between the classes. In our case, the positive cases (patients who die during their hospital stay) represent only 3% of all patients. Table 4 gives more details about this distribution after the pre-processing step which is discussed in A.2. To deal with this well-known problem, we have decided to use downsampling technique [More, 2016, He and[START_REF] He | Learning from imbalanced data[END_REF], a standard solution used for this purpose, as used in [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF].

A.2 PREPROCESSING

1. Features normalization: we extract from the dataset the values of each feature represented in Table 3. For gender, we use one-hot encoding: Male, Female and Unknown. Similarly, for admission type we use 4 features: Emergency, Urgent, Trauma Center, and Unknown8 . For drugs, we extract 24,419 features which correspond to the different drugs (name and dosage). A given patient receives only a few of the possible drugs served, resulting in a very sparse patient's record. We use a MinMax normalization for age and MRCI in order to rescale the values of these features between 0 and 1 (using MinMaxScaler class of scikit-learn9 ). The labels that we consider are boolean: true means that the patient died during his hospital stay while false means she survived.

Patients filtering:

We consider patient and drug information of the first day at the hospital so that we can make predictions 24 hours after admission (as commonly found in the literature [START_REF] Rajkomar | Scalable and accurate deep learning with electronic health records[END_REF][START_REF] Fejza | Scalable and interpretable predictive models for electronic health records[END_REF]). We filter out the pregnant and new-born patients because the medication types and admission services are not the same for theses two categories of patients. Our model prediction is built without patients' historical medical data. This has the advantage to require minimum patient's information and to work for new patients.

Hospitals filtering:

The dataset contains 415 hospitals for a total size of 1,271,733 records. We split randomly the dataset into disjoint training and testing data (80% and 20% respectively). The final dataset for testing contains 254,347 patients, with 7,882 deceased patients and 246,465 non-deceased patients (see Table 4). Using Client-Level differential privacy requires to add more noise than Record-Level differential privacy, because the privacy purposes are not the same as detailled in Section 2. To reduce the noise (when ε is fixed) and then improve the utility, we have to reduce the number of iterations or to reduce the sampling probability which are the parameters used to compute ε.

We therefore have two options to reduce the sampling probability:

-Reducing the number of clients selected at each round |K|. However this option also decreases the amount of data, and hence have a negative impact on the utility. We therefore preferred to use the next option. -Increasing the total number of clients N: we created more hospitals by splitting randomly the training data over 5010 "virtual" hospitals. We also, took care to have at least one in-hospital dead patient per hospital. Each hospital contains 203 patients. 356 patients are used as public dataset to define the Top-K updated weights. We created 5010 hospitals in order to have approximately the same number of patients per hospital, each of them with some in-hospital dead patients.

In practise, Client-Level differential privacy is more adapted to an environment with a large set of clients as explained in [START_REF] Mcmahan | Learning differentially private recurrent language models[END_REF], [START_REF] Geyer | Differentially private federated learning: A client level perspective[END_REF].

A.3 IMBALANCED DATA

The dataset of each hospital is imbalanced because the proportion of patients that leave the hospital alive is, fortunately, much larger than in-hospital dead patients. To deal with this well-known problem, we have decided to use downsampling technique [More, 2016, He and[START_REF] He | Learning from imbalanced data[END_REF], a standard solution used for this purpose. 10

A.4 PERFORMANCE METRICS

We use the following metrics:

10 We have also tested weighted loss function and oversampling techniques. But, we noticed experimentally that downsampling technique outperforms the other techniques for all the schemes.

• Balanced accuracy [START_REF] Henning Brodersen | The balanced accuracy and its posterior distribution[END_REF][START_REF] Bekkar | Evaluation measures for models assessment over imbalanced data sets[END_REF] is computed as 1/2 • ( TP P + TN N ) =

TPR +TNR 2 and is mainly used with imbalanced data. True Positive Rate (TPR ) and True Negative Rate (TNR ): TPR = TP P and TNR = TN N , where P and N are the number of positive and negative instances, respectively, and TP and TN are the number of true positive and true negative instances. We note that traditional ("non-balanced") accuracy metrics such as TP +TN P +N can be misleading for very imbalanced data [START_REF] Akosa | Predictive accuracy: a misleading performance measure for highly imbalanced data[END_REF]: in our dataset, the minority class has only 3% of all the training samples (see Table 4), which means that a biased (and totally useless) model always predicting the majority class would have a (non-balanced) accuracy of 97%.

• The area under the ROC curve (AUROC ) is also a frequently used accuracy metric. The ROC curve is calculated by varying the prediction threshold from 1 to 0, when TPR and FPR are calculated at each threshold. The area under this curve is then used to measure the quality of the predictions. A random guess has an AUROC value of 0.5, whereas a perfect prediction has the largest AUROC value of 1.

A.5 EVALUATION METHOD.

First, we split randomly the dataset of each hospital into disjoint training and testing data (80% and 20% respectively).

An entire federated run is executed with this split, and all the metrics are evaluated in every round on the union of all clients' testing data. All metric values of the round with the best balanced metric are recorded.

A.5.1 Model architecture

As in [START_REF] Avati | Improving palliative care with deep learning[END_REF], [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF], we use a fully connected neural network model with the following architecture: two hidden layers of 200 units, which use a Relu activation function followed by an output layer of 1 unit with sigmoid activation function and a binary cross entropy loss function. This results in 1,496,601 parameters in total. We tune η from 0.01 to 0.5 with an increment value of 0.005. As in [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF], we fix the momentum parameter ρ to 0.9 and the global learning rate η G to 1.0. The number of chunks is set to P = 100 (refers to [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] for details). The hyperparameters used by each of the considered schemes are summarized in

B.3 PREPROCESSING

The pixel of each image is an unsigned integer in the range between 0 and 255. We rescale them to the range [0,1] instead.

B.4 MODEL ARCHITECTURE

For Fashion-MNIST, we use a model McMahan et al. [2016], [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] with the following architecture: a convolutional neural network (CNN) with two 5x5 convolution layers (the first with 32 filters, the second with 64, each followed with 2x2 max pooling), a fully connected layer with 512 units and ReLu activation, and a final softmax output layer. This results in 1,663,370 parameters in total. We tune η from 0.01 to 0.5 with an increment value of 0.005. As in [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF], we fix the momentum parameter ρ to 0.9 and the global learning rate η G to 0.35. Same for the number of chunks used P = 200 (refers to [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF] for more details). The hyperparameters used by each of the considered schemes are summarized in Table 5.

C COMPUTATIONAL ENVIRONMENT

Our experiments were performed on a server running Ubuntu 18.04 LTS equipped with a Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz, 192GB RAM, and two NVIDIA Quadro P5000 GPU card of 16 Go each. We use Keras 2.2.0 Chollet et al. [2015a] with a TensorFlow backend 1.12.0 [START_REF] Abadi | TensorFlow: Large-scale machine learning on heterogeneous systems[END_REF] and Numpy 1.14. 3 Oliphant [2006] to implement our models and experiments. We use Python 3.6.5 and our code runs on a Docker container to simplify reproducibility.

D FURTHER EXPERIMENTS

The goal of this section is to compare the performance of our proposed schemes FL-TOP and FL-TOP-DP with several baselines according to different compression ratios. More specifically, we consider the following additional baselines:

• FL-BAS-2: As in FL-BASIC, only a randomly selected set of parameters are selected and sent to the server at each round. Importantly, none of the parameters are reinitialized during training.

• FL-BAS-3: This baseline is the same as FL-BASIC, except that the set of random parameters is fixed over all the rounds.

• FL-BAS-4: Same as FL-BAS-2, except that the set of random parameters is the same over all the rounds.

• FL-TOP-BIS: Similarly to FL-TOP, it uses the same Top-K parameters over the whole training. The only difference is that the n -K non-Top-K parameters are not re-initialized after each SGD iteration. As in FL-TOP, after T gd SGD iterations, clients send the update of the Top-K parameters to the server.

Note that all compression operators in the new baselines are still linear (just like FL-TOP-DP), and hence they can also be used with secure aggregation. Their private extensions (i.e., FL-BAS-2-DP, FL-BAS-3-DP, FL-BAS-4-DP and FL-TOP-BIS-DP) also clip and then noise the compressed updates as in FL-TOP-DP. The selection of sensitivity S happens similarly to FL-TOP-DP and FL-BASIC-DP using the public data as described in Section 4.

D.1 RESULTS

Table 8 shows the best accuracy over 200 rounds for each scheme on the Fashion-MNIST dataset. Round corresponds to the round when the best accuracy is achieved and Cost is the average bandwidth consumption calculated as: r × n × 32 × Round ×C, where 32 is the number of bits necessary to represent a float value, n is the uncompressed model size, r = |T| n , |T| is the compressed model size, C is the sampling probability of a client, and Round is the round when we get the the best accuracy.

Table 9 and Table 10 display the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AUROC corresponds to the AUROC value when the best balanced accuracy is reached, Round is the round when we get the best balanced accuracy, and finally, Cost is the average bandwidth consumption calculated as for the Fashion-MNIST dataset described above.

On the medical data (see Table 9 and 10), our schemes FL-TOP and FL-TOP-DP reach 0.64 of balanced accuracy and 0.70 of AUROC for r = 0.01%, while FL-TOP-Bis and FL-TOP-Bis-DP, which are the best baselines, have 8% less of balanced accuracy and 10% less of AUROC for identical compression ratios. Furthermore, for larger compression ratios, FL-TOP and FL-TOP-DP have similar results to that of FL-TOP-Bis and FL-TOP-Bis-DP. However, above r = 1%, FL-TOP outperforms FL-TOP-BIS. The same holds for FL-TOP-DP, which outperforms FL-TOP-Bis-DP when r is more than 0.05%.

On Fashion-MNIST, FL-TOP performs better than other schemes below r = 10%. For r = 10%, FL-CS and FL-TOP have the same accuracy of 0.85. FL-TOP-DP is the best DP scheme independently of the compression ratio r.

Notice the the larger the compression ratio r is the smaller the performance gap between our schemes and the baselines FL-BAS-1, FL-BAS-3. The same holds for their DP counterparts. This is mainly due to the fact that the larger r is the more likely that all schemes update the same Top-K parameters.

FL-CS and FL-CS-DP fail to improve their model accuracy when r = 0.01% on the medical dataset. The same holds for FL-BAS-3-DP when r = 0.1% on the Fashion-MNIST dataset.

On Fashion-MNIST, there is a decrease of accuracy for each of FL-TOP-DP, FL-TOP-BIS-DP and FL-CS-DP from r = 5% to r = 10%. Indeed, as suggested in [START_REF] Kerkouche | Compression boosts differentially private federated learning[END_REF], it may be due to the increase of sensitivity S which will also increase the noise and therefore its negative impact on convergence.

k t = Client k (w t-1 ) 7 end 8 w t = w t-1 + ∑ k |D k | ∑ j |D j | ∆w k t end Output: Global model w t 10 11 Client k (w k t-1 ): 12 w k t = SGD(D k , w k t-1 , T gd ) Output: Model update (w k t -w k t-1 ) Algorithm
∆ wk t = Client k (w t-1 ) 7 end 8 w t = w t-1 + 1 |K| ∑ k ∆ wk t 9 end 10 Client k (w k t-1 ): 11 ∆w k t = SGD(D k , w k t-1 , T gd ) -w k t-1 12 ∆ ŵk t = ∆w k t / max 1, ||∆w k t || 2 S Output: Enc K k (G (∆ ŵk t , SIσ / |K|))

  for all D, D differing in at most one record, where || • || p denotes the L p -norm.

Algorithm 1 :

 1 FL-TOP: Federated Learning Server: Initialize common model w 0 Select set T of Top-K updated weights' coordinates via public dataset for t = 1 to T cl do Select K clients uniformly at random

Algorithm 2 :

 2 Top k -Stochastic Gradient Descent Input: D : training data, T gd : local epochs, w : weights, w 0 : first weights' initialization, T : set of Top-K values coordinates . 1 for t = 1 to T gd do 2 Select batch B from D randomly 3 u = -η∇ f (B; w) 4 for each coordinate i in T do 5 w[i] = w[i] + u[i] Model w rounds locally, and send them to the server for aggregation.

Algorithm 3 :

 3 FL-TOP-DP: Federated Learning Server: Initialize common model w 0 Select set T of Top-K updated weights' coordinates via public dataset for t = 1 to T cl do Select K clients uniformly at random

Figure 1 :

 1 Figure 1: Distributions of the Top-K weight values (after convergence) for both FL-TOP and FL-STD schemes with the Fashion-MNIST dataset (left) and the medical dataset (right).

  1 to T cl do 4 Select K clients uniformly at random 5 for each client k in K do 6 ∆w

  5: Stochastic Gradient Descent Input: D : training data, T gd : local epochs, w : weights 1 for t = 1 to T gd do 2 Select batch B from D randomly 3 w = w -η∇ f (B;

Fashion-MNIST dataset C

 dataset = 1/60; N = 6000; T cl = 200; T gd = 5; |B| = 10; |D k | = 10; n = 1, 663, 370; δ = 10 -5 ; SGD(η = 0.215); η G = 0.35; ρ = 0.9; P = 200; σ = 1.54; T init = 5 Medical dataset C = 100/5010; N = 5010; T cl = 100; T gd = 40; n = 1, 496, 601; δ = 10 -5 ; SGD(η = 0.1); η G = 1.0; ρ = 0.9; P = 100; σ = 1.49; T init = 40

Table 2

 2 represents the best balanced accuracy over 100 rounds for each scheme on the Medical dataset. AUROC (area under the receiver operating characteristic curve -see Appendix A.4) corresponds to the AUROC value when the best balanced accuracy is reached.

Table 1 :

 1 Summary of results on Fashion-MNIST dataset.

					Performance							Performance
	r	Algorithms	Accuracy Round	Downstream Upstream Cost Cost	ε	r	Algorithms	Bal_Acc AUROC Round	Downstream Upstream Cost Cost	ε
					(Kilobyte)	(Kilobyte)							(Kilobyte)	(Kilobyte)
		FL-BASIC	0.65	193	21402.03	107	N/A		FL-BASIC	0.51	0.51	99	11829.42	11.82	N/A
		FL-CS	0.57	185	20514.9	102.56	N/A		FL-CS	0.53	0.55	100	11948.91	11.94	N/A
		FL-TOP	0.82	200	110.88	110.88	N/A		FL-TOP	0.69	0.76	68	8.12	8.12	N/A
	0.5%	FL-BASIC-DP FL-CS-DP	0.59 0.53	200 200	22178.27 22178.27	110.88 110.88	1 1	0.1%	FL-BASIC-DP FL-CS-DP	0.50 0.51	0.49 0.51	100 99	11948.91 11829.42	11.94 11.82	1 1
		FL-TOP-DP	0.81	200	110.88	110.88	1		FL-TOP-DP	0.69	0.76	85	10.15	10.15	0.97
		FL-BASIC	0.78	196	21734.70	1086.73	N/A		FL-BASIC	0.72	0.80	100	11948.91	597.45	N/A
		FL-CS	0.82	200	22178.27	1108.91	N/A		FL-CS	0.73	0.81	98	11709.93	585.5	N/A
		FL-TOP	0.84	200	1108.91	1108.91	N/A		FL-TOP	0.72	0.80	95	567.57	567.57	N/A
	5%	FL-BASIC-DP FL-CS-DP	0.76 0.78	195 160	21623.81 17742.61	1081.18 887.13	0.99 0.94	5%	FL-BASIC-DP FL-CS-DP	0.69 0.69	0.76 0.76	100 100	11948.91 11948.91	597.45 597.45	1 1
		FL-TOP-DP	0.81	152	842.77	842.77	0.92		FL-TOP-DP	0.68	0.75	23	137.41	137.41	0.79
		FL-BASIC	0.81	196	21734.70	2173.47	N/A		FL-BASIC	0.74	0.81	100	11948.91	1194.89	N/A
		FL-CS	0.85	182	20182.22	2018.22	N/A		FL-CS	0.74	0.82	100	11948.91	1194.89	N/A
		FL-TOP	0.85	199	2206.74	2206.74	N/A		FL-TOP	0.74	0.82	90	1075.40	1075.40	N/A
	10%	FL-BASIC-DP FL-CS-DP	0.79 0.72	189 167	20958.46 18518.85	2095.85 1851.89	0.98 0.95	10%	FL-BASIC-DP FL-CS-DP	0.69 0.69	0.76 0.76	99 96	11829.42 11470.95	1182.94 1147.09	1 0.99
		FL-TOP-DP	0.80	157	1740.99	1740.99	0.93		FL-TOP-DP	0.68	0.74	23	274.82	274.82	0.79
	100%	FL-STD FL-STD-DP	0.86 0.56	200 60	22178.27 6653.48	22178.27 N/A 6653.48 0.76	100%	FL-STD FL-STD-DP	0.74 0.66	0.82 0.72	99 62	11829.42 7408.32	11829.42 N/A 7408.32 0.91

Table 2 :

 2 Summary of results on Medical dataset.

Table 5 .

 5

	B FASHION-MNIST DATA: DATA
	PRE-PROCESSING &
	EXPERIMENTAL SETUP DETAILS
	B.1 DATA DESCRIPTION
	Fashion-MNIST database of fashion articles consists of
	60,000 28x28 grayscale images of 10 fashion categories,
	along with a test set of 10,000 images Xiao et al. [2017]
	Chollet et al. [2015b].
	B.2 PUBLIC DATA DESCRIPTION
	The MNIST database of handwritten digits. It consists of
	28 x 28 grayscale images of digit items and has 10 output
	classes. The training set contains 60,000 data samples while
	the test/validation set has 10,000 samples LeCun and Cortes
	[2010] Chollet et al. [2015b].

Table 3 :

 3 Descriptions of featuresFeatures DescriptionsAge Value in the range of 15 and 89 Gender Male, Female or Unknown Admission type Emergency, Urgent, Trauma Center: visits to a trauma center/hospital or Unknown MRCI Medication regimen complexity index score (ranging from 2 to 60)Drugs and ICD9 codesDrugs given to the patient on the 1 st day of hospitalization. The ICD9 codes are composed of procedures and diagnosis codes, the first gives details about the medical procedures performed on the patient and the second about the doctor's diagnosis of the patient. There is a total of 24,419 possible drugs and ICD9 codes[START_REF] Marta | Icd-9-cm: International classification of diseases, ninth revision, clinical modification[END_REF].

Table 4 :

 4 Number of instances for our case study. The Medical dataset contains in total 1,271,733 records.

	Data Positive cases Negative cases Ratio	Total
	Train	32,106	985,280	3.16% 1,017,386
	Test	7,882	246,465	3.10%	254,347
	Datasets		Common Parameters

Table 5 :

 5 Common environment between the schemes. ρ, η G and P are only used with FL-CS and FL-CS-DP.

	Algorithms	Compression ratio (r) 0.1% 0.5% 1% 5% 10%
	FL-BASIC-DP	0.05	0.12 0.16 0.34 0.45
	FL-BAS-2-DP	0.07	0.16 0.23 0.52 0.75
	FL-BAS-3-DP	0.05	0.11 0.16 0.33 0.44
	FL-BAS-4-DP	0.06	0.15 0.21 0.51 0.74
	FL-CS-DP	0.21	0.26 0.32 0.57 0.79
	FL-TOP-BIS-DP 1.25	1.59 1.79 2.18 2.34
	FL-TOP-DP	0.50	0.61 0.64 0.87	1.0

Table 6 :

 6 Sensitivity S used for each scheme and for different compression ratio r on Fashion-MNIST. For FL-STD-DP, S is set to 2.40.

	Algorithms	Compression ratio (r) 0.01% 0.05% 0.1% 0.5% 1%	5% 10%
	FL-BASIC-DP	0.01	0.03	0.05	0.11 0.16 0.34 0.46
	FL-BAS-2-DP	0.01	0.03	0.04	0.09 0.14 0.31 0.44
	FL-BAS-3-DP	0.01	0.04	0.06	0.12 0.18 0.35 0.49
	FL-BAS-4-DP	0.02	0.03	0.05	0.12 0.15 0.31 0.44
	FL-CS-DP	0.002	0.005 0.006 0.01 0.02 0.04 0.06
	FL-TOP-BIS-DP	0.60	0.73	0.81	1.03 1.13 1.31 1.32
	FL-TOP-DP	0.23	0.46	0.59	1.03 1.18 1.31 1.32

Table 7 :

 7 Sensitivity S used for each scheme and for different compression ratio r on the medical dataset. For FL-STD-DP, S is set to 1.40.

	Compression ratio (r)	Algorithms	Performance Accuracy Round Downstream Cost (Kilobyte) Upstream Cost (Kilobyte)	ε
		FL-BASIC	0.14	111	12308.94	12.31	N/A
		FL-BAS-2	0.16	185	20514.9	20.51	N/A
		FL-BAS-3	0.27	200	22.17	22.17	N/A
		FL-BAS-4	0.17	200	22.17	22.17	N/A
		FL-CS	0.37	200	22178.27	22.17	N/A
		FL-TOPK-BIS	0.59	198	21.95	21.95	N/A
	0.1%	FL-TOP FL-BASIC-DP	0.78 0.14	199 167	22.06 18518.85	22.06 18.51	N/A 0.95
		FL-BAS-2-DP	0.14	124	13750.53	13.75	0.88
		FL-BAS-3-DP	-	-	-	-	-
		FL-BAS-4-DP	0.15	137	15.19	15.19	0.90
		FL-CS-DP	0.36	197	21845.59	21.84	1
		FL-TOPK-BIS-DP	0.59	196	21.73	21.73	0.99
		FL-TOP-DP	0.76	199	22.06	22.06	1
		FL-BASIC	0.65	193	21402.03	107	N/A
		FL-BAS-2	0.46	196	21734.70	108.66	N/A
		FL-BAS-3	0.73	200	110.88	110.88	N/A
		FL-BAS-4	0.41	197	109.22	109.22	N/A
		FL-CS	0.57	185	20514.9	102.56	N/A
		FL-TOPK-BIS	0.76	200	110.88	110.88	N/A
	0.5%	FL-TOP FL-BASIC-DP	0.82 0.59	200 200	110.88 22178.27	110.88 110.88	N/A 1
		FL-BAS-2-DP	0.38	200	22178.27	110.88	1
		FL-BAS-3-DP	0.56	200	110.88	110.88	1
		FL-BAS-4-DP	0.33	200	110.88	110.88	1
		FL-CS-DP	0.53	200	22178.27	110.88	1
		FL-TOPK-BIS-DP	0.68	184	102.01	102.01	0.97
		FL-TOP-DP	0.81	200	110.88	110.88	1
		FL-BASIC	0.71	194	21512.92	215.12	N/A
		FL-BAS-2	0.59	200	22178.27	221.77	N/A
		FL-BAS-3	0.76	200	221.77	221.77	N/A
		FL-BAS-4	0.56	195	216.23	216.23	N/A
		FL-CS	0.69	200	22178.27	221.77	N/A
		FL-TOPK-BIS	0.79	197	218.45	218.45	N/A
	1%	FL-TOP FL-BASIC-DP	0.83 0.65	200 197	221.77 21845.59	221.77 218.45	N/A 1
		FL-BAS-2-DP	0.62	198	21956.48	219.56	1
		FL-BAS-3-DP	0.66	198	219.56	219.56	1
		FL-BAS-4-DP	0.52	198	219.56	219.56	1
		FL-CS-DP	0.66	189	20958.46	209.58	0.98
		FL-TOPK-BIS-DP	0.70	174	192.94	192.94	0.96
		FL-TOP-DP	0.81	183	202.92	202.92	0.97
		FL-BASIC	0.78	196	21734.70	1086.73	N/A
		FL-BAS-2	0.72	199	22067.38	1103.36	N/A
		FL-BAS-3	0.81	199	1103.36	1103.36	N/A
		FL-BAS-4	0.76	196	1086.73	1086.73	N/A
		FL-CS	0.82	200	22178.27	1108.91	N/A
		FL-TOPK-BIS	0.83	196	1086.73	1086.73	N/A
	5%	FL-TOP FL-BASIC-DP	0.84 0.76	200 195	1108.91 21623.81	1108.91 1081.18	N/A 0.99
		FL-BAS-2-DP	0.72	195	21623.81	1081.18	0.99
		FL-BAS-3-DP	0.76	199	1103.36	1103.36	1
		FL-BAS-4-DP	0.75	191	1059.01	1059.01	0.99
		FL-CS-DP	0.78	160	17742.61	887.13	0.94
		FL-TOPK-BIS-DP	0.71	152	842.77	842.77	0.92
		FL-TOP-DP	0.81	152	842.77	842.77	0.92
		FL-BASIC	0.81	196	21734.70	2173.47	N/A
		FL-BAS-2	0.78	199	22067.38	2206.74	N/A
		FL-BAS-3	0.82	195	2162.38	2162.38	N/A
		FL-BAS-4	0.79	200	2217.83	2217.83	N/A
		FL-CS	0.85	182	20182.22	2018.22	N/A
		FL-TOPK-BIS	0.84	196	2173.47	2173.47	N/A
	10%	FL-TOP FL-BASIC-DP	0.85 0.79	199 189	2206.74 20958.46	2206.74 2095.85	N/A 0.98
		FL-BAS-2-DP	0.77	189	20958.46	2095.85	0.98
		FL-BAS-3-DP	0.79	183	2029.31	2029.31	0.97
		FL-BAS-4-DP	0.78	195	2162.38	2162.38	0.99
		FL-CS-DP	0.72	167	18518.85	1851.89	0.95
		FL-TOPK-BIS-DP	0.69	138	1530.30	1530.30	0.90
		FL-TOP-DP	0.80	157	1740.99	1740.99	0.93
	100%	FL-STD FL-STD-DP	0.86 0.56	200 60	22178.27 6653.48	22178.27 6653.48	N/A 0.76

Table 8 :

 8 Summary of results on Fashion-MNIST dataset.

weight values for downstream and update/gradients for upstream traffic

More precisely, ∑ i G (ν i , ξ i ) = G (∑ i ν i , ∑ i ξ 2 i )

More baselines are considered but due to the lack of space, we have decided to present only those which return the best results. All other results can be found in the appendix( Section D).

See Appendix A.4 for more details.

https://www.premierinc.com/newsroom/education/premierhealthcare-database-whitepaper 100 patients' records, hence, the number of features was reduced to 7,280 features.

https://www.resdac.org/cms-data/ variables/claim-inpatient-admission-typecode-ffs

9 https://scikit-learn.org/ stable/modules/generated/ sklearn.preprocessing.MinMaxScaler.html


Lafdal Abdelwedoud

Anthony Busson

Isabelle Guérin-Lassous

Use of a Weighted Conflict Graph in the Channel Selection Operation for Wi-Fi Networks

Keywords: IEEE 802.11, channel allocation, conflict graph

Allocation algorithms in IEEE 802.11-based WLAN, that consist to associate to each AP a channel, are mainly based on a conflict graph that represents the conflicts (interference, CCA detection, etc.) between APs. In this paper, we propose to use an enriched version of the conflict graph, namely a weighted conflict graph. This latter models the CCA detection that can be total (all transmissions are detected) or partial. Beside, a model is given to compute the throughput of each AP for a given allocation. This model is combined to a greedy algorithm that aims to find the allocation that maximizes the proportional fairness. Simulations based on the recent IEEE 802.11ax amendment are carried out for small WLANs with a few APs and very dense networks. Results show that when the network is dense or constrained, there is a gain to consider partial detection.

I. INTRODUCTION

The management of a Wi-Fi network is a crucial step to provide the best possible quality of experience to users and to efficiently use the network's resources. This step relies, among others, on the network monitoring, the band and channel selection, the users' association to the access points (APs) and the load balancing among the network. Providing an efficient management is still a challenge and a concern for Wi-Fi vendors. Several management operations are often based on the network's conflict graph. Such a conflict graph models the conflicts between devices (APs and/or stations). The conflicts can represent the conflicts in the medium access triggered by the use of the CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) approach and/or the possible interference between transmitting devices. The conflict graph can be inferred from the network monitoring operation.

In most cases, the conflict graph is considered as a nonweighted graph. It means that two devices are always or never in conflict. We show in [START_REF] Abdewedoud | A passive method to infer the weighted conflict graph of an ieee 802.11 network[END_REF] that, in practice, this is not the case and that the conflict graph of a Wi-Fi network is partial. It means that two devices may be sometimes in conflict and sometimes not, even though they are static and without a radical change in the environment. Therefore, the use of a non-weighted conflict graph may lead to misleading management operations resulting in a suboptimal use of the network resources.

In this paper, we propose to use a weighted conflict graph representing the partial conflicts between the network's devices in the management operations. We focus our study on the channel selection operation. A large set of channel allocation solutions are based on a non weighted conflict graph like, for instance, in [START_REF] Riihijarvi | Performance evaluation of automatic channel assignment mechanism for ieee 802[END_REF]- [START_REF] Chieochan | Channel assignment schemes for infrastructure-based 802.11 wlans: A survey[END_REF]. Our contributions are twofold: i) we propose a solution that allocates channels to access points knowing the weighted conflict graph between the APs of the network ; ii) we compare the network performance obtained thanks to this allocation with a classical channel allocation using a simple non-weighted conflict graph.

The paper is organized as follows: in Section II, we describe the problem studied in this paper. The proposed channel allocation based on a weighted conflict graph is described in Section III. The simulation results obtained with the proposed allocation are given in Section IV. We also compare our solution with a channel allocation solution based on a classical non weighted conflict graph. We conclude in Section V.

II. PROBLEM STATEMENT

In this study, we only consider the conflicts between APs. The users' stations are not considered as they can appear and disappear within a short time scale whereas the APs have a more permanent situation in the network. We consider that AP A is in conflict with AP B when AP A can detect, via the CCA (Clear Channel Assessment) mechanism, the transmission of AP B preventing AP A from transmitting. Such a conflict is often modeled by a graph in which the two APs are represented by two nodes in the graph and the conflict with an edge (directed or not) between these two nodes.

Usually the conflict graph is considered as non-weighted. It means that if there is an edge between two nodes then the conflict is considered as permanent between the two considered APs and arising all the time. We have shown in [START_REF] Abdewedoud | A passive method to infer the weighted conflict graph of an ieee 802.11 network[END_REF] that an AP may sometimes detect the transmission of another AP and may sometimes not even if these two APs are static. This can be explained by the fast fading that can occur on Wi-Fi channels. It means that the conflict is not permanent but partial. Such a partial conflict can be modeled by a weighted conflict graph in which the weight on an edge (directed or not depending if the conflict is considered as asymmetrical or not) represents the fraction of time during which the AP (at one end of the considered edge) senses the activity of the AP (at the other end of the edge) when this latter transmits all the time (in saturation).

We claim that using a non weighted conflict graph in the management of a Wi-Fi network may lead to a suboptimal use of the network's resources. To support this statement, let's consider a toy example with 3 APs as shown in Fig. 1. In this example, the APs are located such that AP 2 is always in conflict with APs 1 and 3 (the weights of the corresponding edges are 1) and AP 1 and AP 3 have a partial conflict of 0.36 (meaning that they detect each other 36% of the time). Let's assume that only 2 orthogonal channels can be used for this example. When considering the non weighted conflict graph, a classical channel allocation can set APs 1 and 2 on the same channel and AP 3 on the other channel. When considering the weighted conflict graph, the channel allocation obtained with the solution described in Section III sets APs 1 and 3 on the same channel and AP 2 on the other one. Simulations obtained with the ns-3 simulator (the simulation parameters are described in more details hereafter) show that with the second allocation the overall throughput increases with a percentage ranging from 24% to 12% as function of the distance between the stations and their AP (from 1 to 17 meters). This is explained by the fact that allocating the same channel to APs with partial detection will enable more transmissions, leading to a better overall throughput. If the partial detection is not modeled in the conflict graph, then the channel allocation solution will not be aware of this possibility and may not boost the use of the same channel on partial links.

III. MODEL AND CHANNEL ALLOCATION ALGORITHM

We consider a Wi-Fi network composed of N APs and n stations. We assume that each station is associated to exactly one AP of the network. The variable x k,i indicates if station k is associated to AP i (x k,i = 1) or not (x k,i = 0). A channel allocation is represented through a vector C of size N where the i th element is the channel number allocated to AP i. Our solution is based on an estimation of the throughput that can be obtained by each AP for a given channel allocation.

A. A model to evaluate a channel allocation

We extend the model proposed in [START_REF] Amer | Association Optimization in Wi-Fi Networks based on the Channel Busy Time Estimation[END_REF] to estimate the throughput of each AP under a given channel allocation. This model relies on a non-weighted conflict graph denoted S. The second parameter used by the model is the matrix (r k,j ) k,j where r k,j is the achievable throughput between AP j and station k. We define the achievable throughput between AP j and station k as the maximum throughput that is obtained between these two devices in absence of other Wi-Fi nodes. This model assumes that the network is saturated, i.e. an AP has always a frame to send, and that an AP, in average, sends the same number of frames to each of its associated stations.

Our extension consists in introducing the partial detections. The coefficients of the matrix S are substituted by the coefficients w j,i (0 ≤ w j,i ≤ 1) that represent the partial CCA detection between APs. In [START_REF] Abdelwedoud | Inference of a clear channel assessment based conflict graph[END_REF], we describe a method to infer the weighted conflict graph of an infrastructure-based Wi-Fi network. The coefficient w j,i depends on the AP location, the radio environment and the channel allocation as two APs using two orthogonal channels do not interfere with each other. The matrix of these weights is denoted W (C). Thus, given a channel allocation and the underlying weighted conflict graph of the network, the mean throughput of AP i is modeled as:

throughput(AP i , C, W (C)) = 1 n k=1 x k,i × 1 N j=1 w j,i n k=1
x k,j n k=1

x k,j r k,j

A channel allocation C can be evaluated through the proportional fairness (PF) metric that offers a good trade-off between throughput and fairness. It is defined as:

P F (C, W (C)) = N i=1 ln(throughput(APi, C, W (C))) (2)
Our optimization problem aims at finding the channel allocation that maximizes the proportional fairness, given a fixed number of available channels:

max C P F (C, W (C)) (3)

B. A greedy channel allocation

The solution (Algorithm 1) to the optimization problem defined in Eq. 3 is based on a local search algorithm. It starts from a random channel allocation. At each step, an AP i is selected. For this particular AP, the PF metric is evaluated for each channel. The channel that offers the best PF metric is assigned to this AP (if it was not already assigned). Then, another AP is chosen and so on. When all APs have been selected, the algorithm performs a new round. The algorithm stops when there is no improvement for a whole round. In terms of complexity, the most costly instruction is the computation of the PF metric which has an upper bound complexity of O(N.n 2 ). Therefore the overall complexity of the algorithm is O(k.|C|.N 3 .n) if k rounds of the algorithm is executed. Note that the complexity of Algorithm 1 is the same when a weighted conflict graph is used as when a non weighted conflict graph is used. The proposed approach is validated through a large set of realistic simulations. We performed ns-3 simulations to validate i) the accuracy of our model with regard to realistic simulations and ii) to evaluate the gain of using a weighted conflict graph to allocate channels. We changed the physical layer of ns-3.31 by adding a log-normal fading to the propagation model leading to partial detection between 43 and 60 meters. The different simulation parameters are given in Table I. For all the scenarios, we apply Algorithm 1 to perform two allocations: one based on the non weighted conflict graph and the other based on the weighted one. We evaluate the allocations in saturated mode where each AP has always a frame to send.

a) Small topologies: The gain of using a weighted conflict graph can be important for a small topology as it has been shown in Section II. In order to consider more generic topologies, we generate 40 random topologies from 4 to 7 APs distributed in a ball of radius 50 meters, leading to a simulated area of approximately 8000 m 2 . For these simulations, we use the ISM band and 3 orthogonal channels. For each AP, one associated station downloads data. Table II gives the mean throughput gain, computed as the sum of throughputs over all APs when considering a weighted conflict graph minus the sum of throughputs with a non-weighted conflict graph. The gain is significant as it varies between 70 Mb/s and 114 Mb/s. Beside, considering weighted conflict graph improves the PF of a factor between 1.67 and 3.5.

b) Dense scenarios: In this section, we focus on a dense Wi-Fi network to explore the limit of the use of weighted conflict graphs. The scenario corresponds to a stadium where the APs cover the bleachers and users of a side of the stadium. In such a scenario, the Wi-Fi network is very dense and each AP covers a limited number of users to ensure a high quality of experience. The APs are located on a 10 × 6 grid (60 APs). 10 stations are associated to each AP leading to 600 users downloading data at the same time. The simulated network is an IEEE 802.11ax network in the 5GHz band.

Figs 2 shows the theoretical and the simulations results when the distance between two adjacent APs in the grid varies. The distances are chosen to have neighbors in the grid detected at 100% and 2-hop neighbors partially detected. It leads to distances between 10 and 26 meters. For greater distances the conflict graph does not present any partial detection. For small distances, the error in the PF estimation is quite important between the model and the simulations. It is mainly due to the high contention that causes starvation for a few APs. The nature of the PF function makes it very sensitive to small values leading to this error. But as the distance increases, starvation becomes rare and the error decreases significantly. Note that this error is smaller when considering the mean throughput per AP (Fig. 2). In terms of performance, the difference between the two PF values (with and without the weighted conflict graph) varies from 3 to 10 (and thus of several order of magnitude in its linear form). The throughput gain is approximately of 10% per AP for distances up to 22 meters and is negligible for greater distances. The gain between the two approaches is thus clearly in terms of fairness between APs rather than throughput. We observe the same trend in Fig. 3 when the number of available channels increases. The PF metric is significantly greater when using a weighted conflict graph and when the number of channels if less than 7 (the network is then more constrained). For a greater number of channels, the performance becomes similar for the two allocations.

When the number of channels is low, as for the ISM band, there is thus an important gain to use weighted conflict graph. In the 5GHz band where there are up to 23 orthogonal channels, there is no real benefit to use a weighted conflict graph. But, if channels are aggregated (40 MHz or 80 MHz), the allocation is more constrained. For instance, results for the 40MHz width channel in the 5GHz band are shown in Table III for 4 channels (UNII-1 and UNII-2 band) and 12 channels (where UNII-2 extended and UNII-3 are added). The table shows that there is a clear benefit to use the weighted conflict graph in particular for the 12 channels case.

V. CONCLUSION

Many channel allocation algorithms rely on a conflict graph to model conflicts between APs. In this paper, we propose to use a weighted conflict graph capturing the level of CCA detection between APs and consequently their capacity to share a channel at the same time. We propose a channel allocation algorithm based on a local search approach, a weighted conflict graph and a model estimating the throughput per AP for a given channel allocation. Simulations of a large set of scenarios and using IEEE 802.11ax show that our model is able to accurately estimate objective functions based on throughput. Also, simulation results empirically show that an allocation considering a weighted conflict graph offers better results in terms of proportional fairness for a large set of topologies as soon as the network is dense or constrained. In this case, the algorithm tends to reuse a same channel between APs that partially detect each other.

Fig. 1 :

 1 Fig. 1: A toy example for the conflict graph.

Algorithm 1 :

 1 Local

Fig. 2 :

 2 Fig. 2: Comparison of the channel allocation performance with weighted and non-weighted conflict graphs in the 5GHz band and for 20MHz channels. The distance between two APs in the grid varies. 3 channels are used.

Fig. 3 :

 3 Fig. 3: Comparison of the channel allocation performance with weighted and non-weighted conflict graphs in the 5GHz band and for 20MHz channels. The number of channels varies. The distance between two APs in the grid is 25 meters.

TABLE I :

 I Simulation parameters

	Nb of APs	4	5	6	7
	Throughput gain (in Mb/s)	108 114	70	72
	PF gain (linear scale)	3,5	2	1.7	2.7

TABLE II :

 II Throughput and PF gains when using the weighted conflict graph

TABLE III :

 III Simulation results for IEEE 802.11ax and 40MHz channel width. The distance between APs in the grid is 27m.