Marie Garin
email: marie.garin@ens-paris-saclay.fr

Theodoros Evgeniou

Nicolas Vayatis

Weighting Scheme for One-Shot Federated Learning

This paper focuses on one-shot aggregation of statistical estimations made across disjoint data sources for federated learning, in the context of empirical risk minimization. We exploit the role of each local sample size for this problem to develop a new weighting scheme for one-shot federated learning. First, we provide upper bounds on the local errors and biases from which we derive an upper bound for the plain federated learning parameter. Then, by casting an optimization problem based on the bias-variance decomposition of the MSE, we develop a simple weighting scheme based only on the local sample sizes. The proposed procedure can be embedded in a wide variety of algorithms used for federated learning. Finally, we evaluate our procedure in the context of large-scale estimation of linear models with ridge regression and compare it to the typical choice of weights in federated learning. We observe that, due to unbalanced sample sizes across the data sources, the proposed weighting scheme outperforms the standard one and converges faster to the performance of a centralized estimator.

Introduction

To handle the rapidly increasing amount of data produced possibly from a very large number of sources, researchers study alternatives to centralized architectures. Distributed learning has recently emerged as an important approach to efficiently process very large datasets. Distributed optimization algorithms generally alternate local improvement steps with communication steps in order to optimize the computation time and the efficiency of the final output. The communication step involves a central server and a chosen number of compute nodes, called "machines". In this setting, the full sample of size N , first held by the central server, is equally split among the m machines. Therefore, each machine holds n " t N m u independent identically distributed (i.i.d.) observations. Since the centralized data are evenly distributed across machines, in distributed learning, there was no need to study the effect of varying sample sizes as they are identical throughout the machines. The output computed by the machines is, most of the time, a gradient, a prediction, or a parameter value. These outputs are computed locally and then aggregated by the central server to provide a global outcome. We point out that for such a distributed estimator, the aggregation step may combine the computations performed on the m machines over one round (one-shot setting) or over several rounds of communications Preprint. Under review.

(multi-round setting). More recently, federated learning [6; 7] has stood out as a promising field of growing emphasis, also advocating for an alternative to centralized learning. Federated learning relies on both local data storage and local model training. Indeed, the primary specificity of this setting, and where it differs from distributed learning -in which the samples are first centralized and then distributed among several compute nodes -is that data are never shared and are only stored locally. Above and beyond the computational gains this can lead to, the benefit of keeping the samples locally is twofold. On the one hand, it preserves privacy, which is often critical as its endangerment entails potentially insidious societal effects such as self-censorship [START_REF] Penney | Chilling effects: Online surveillance and wikipedia use[END_REF]. 1 On the other hand, it enables to collaboratively learn when sharing data is impractical -if not illegal. In the federated learning literature, the compute and storage nodes are often called devices or clients. In an attempt to be representative of the diversity of applications where the choice of a federated architecture could be promising, we will use the term of "nodes" in the federated setting (instead of "machines" for the distributed setting). Thus, each of the m nodes owns n i observations, with the distribution of those sample sizes possibly being unbalanced across the nodes, i.e., n i with considerable ranges of variation. This entails also that the distribution of the sample sizes is no longer uniform and raises new statistical challenges.

In this paper, we focus on one-shot federated learning -meaning, only one round of communication between the nodes and the central server -when the nodes deliver a parameter varying in a Euclidean space (as it is the case of linear regression models for instance). One-shot federated learning is yet an under-exploited topic especially since the multi-round setting is subject to many challenges and limitations, the first one arising from costs and limitations of communications. If there is a significant number of nodes, communications between the nodes and the server can be expensive, including possible security breaches or bottlenecks due to bandwidth limitations. Moreover, recent work indicates that even sharing of model parameters (not the raw data) can leak private information [START_REF] Phong | Privacy-preserving deep learning via additively homomorphic encryption[END_REF]. Thus, the fewer rounds of communication there are, the less information is shared and the more privacy-preserving the overall system is. The benefits of reducing communication rounds also appear to be crucial at a time when the community is becoming aware of the environmental impacts of machine learning, particularly in terms of energy consumption and carbon footprint. To take just one recent glimpse, Strubell et al. [START_REF] Strubell | Energy and policy considerations for deep learning in nlp[END_REF] estimated CO2 emissions of the training phase of some NLP algorithms on which one emits more than 300 trans-American flights. This is why we advocate for more sober and responsible models, while being aware that the emphasis on privacy and environmental friendly models can be double edged. It can lead to ethic-washing and invisibilize other broader ethical issues that are societal choices (see the notion of "small ethics" defended by the philosopher Mark Hunyadi). Despite these limitations, there is currently only a limited body of work delving into one-shot federated learning. This may be because one-shot aggregation of estimations suffers from an important limiting factor: the local sample size, n, must be larger than the number of machines, m, to ensure similar behavior to the centralized estimator, the one with full access to all samples. In the distributed setting, the samples are first gathered at the central server level and then distributed, so n and m can be controlled and this constraint can be handled by choosing an appropriate number of machines, m. However, we recall that in the federated setting, the samples are only kept at the node level, allowing no control over n i . In order to address this possible limitation, Guha et al. [START_REF] Guha | One-shot federated learning[END_REF] browse through ensemble learning methods like selecting nodes whose sample size exceeds a certain threshold to participate in the training -which shows similarities with the results presented in this article. Zhou et al. [START_REF] Zhou | Distilled one-shot federated learning[END_REF] consider a rather heteroclite approach where the training operates on a centralized server which collects synthetic data distilled by the nodes. Salehkaleybar et al. [START_REF] Salehkaleybar | One-shot federated learning: theoretical limits and algorithms to achieve them[END_REF] consider a setting, closer to distributed learning, where the sample sizes are the same across the nodes and investigate the effect of the number of bits of the message that a node is allowed to transmit to the central server. They propose an algorithm were each node sends an approximation of derivatives of the global objective function over a neighborhood of the sought parameter.

Our objectives in the present work are to address the following two questions: piq what are the consequences of the distribution of the sample sizes?, and piiq how can we overcome this issue by optimizing the weighting scheme of the federated learning models across all nodes? Another major issue in federated learning is to deal with non-i.i.d. sampling. However, as this paper focuses on the effect of the distribution of sample sizes, the framework is restricted to an i.i.d. hypothesis in order to derive initial results and provide some insights. Our main contributions are as follows. We answer to the first question piq by providing, in Section 3, upper bounds on the local errors and biases from which we derive an upper bound on the mean-squared error (MSE) of the one-shot federated parameter in a very general setting of empirical risk minimization (ERM). This analysis is the first one, to the best of our knowledge, to formally highlight the crucial role of the sample sizes in the federated learning setting. Our work is motivated by the work of Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF], thus, our assumptions are quite similar to theirs, although alleviated -another contribution of our work is the improved readability of their proof and the reduction of their Assumption 2.4. We also translate the minimum sample size constraint encountered in distributed learning to federated learning setup. Our next contribution is to address the other issue piiq by proposing a procedure to aggregate the local estimations based on a minimization of an upper bound of the MSE, resulting in a closed-form formula. However, the obtained weights are theoretical and cannot be computed. We therefore propose an approximation of those weights, derived from the previous theoretical results, depending only on the local sample size. This simple and communication-efficient weighting scheme relies upon a water-filling structure, implying that only a fraction -the nodes with the largest sample sizes -participate to the final aggregated parameter. We note that the resulting procedure is consistent with the data selection strategy of ensemble learning, where a node participates if its sample size exceeds a predetermined baseline value [START_REF] Guha | One-shot federated learning[END_REF]. Even though this weighting scheme is developed in a one-shot setting, we believe that the proposed practice can be embedded in a wide variety of algorithms used in federated learning -instead of the standard averaging scheme.

2 Setup and main assumptions

One-shot aggregation

The distribution of the computations driven by the widening of parallel, distributed and federated approaches raises questions on the behaviour of the resulting statistical estimation. Focusing on the one-shot setting -allowing only one round of communication -one crucial issue is the one of the aggregation of the local outputs. In the parallel and distributed literature, the aggregation procedure of the majority of works lies on considering the average of the local outputs -a uniform weighting scheme. As the considered setting is typically i.i.d. with the local sample sizes uniformly allocated, this choice seems appropriate, although other combination patterns are explored [START_REF] Dobriban | Wonder: Weighted one-shot distributed ridge regression in high dimensions[END_REF]. In the federated literature, the aggregation procedure systematically consists in the following: each local output is weighted proportionally to its sample size. As a rule, the canonical aggregation procedure thus consists in generating a convex combination of these local outputs. Mann et al. [START_REF] Mann | Efficient large-scale distributed training of conditional maximum entropy models[END_REF] proposed one of the first theoretical analysis of the averaged parameter in the distributed setting, named mixture weight method, in a statistical learning perspective. The work by Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] was the first to formally prove that this averaged parameter, termed average mixture (AVGM) by the authors, generally works better than the parameter obtained on a single machine. The authors provide, under some regularity assumptions, a bound on the MSE decaying as O `1 N `1 n 2 ˘in a very general setting of empirical risk minimization. We recall that, under some classical regularity assumptions, the MSE of the centralized estimator decays as Op 1 N q. Then, the distributed estimator reaches the performance of the centralized one when n " Ωpmq, meaning that each machine must hold, at least, as many observations as there are machines. We highlight this fundamental limit faced by one-shot distributed learning on synthetic data by plotting the MSE of the distributed and the centralized estimator on Figure 2 in the appendix. The centralized estimator refers to the one learned with access to the full sample of N observations. An interesting development can be found in Rosenblatt and Nadler [START_REF] Rosenblatt | On the optimality of averaging in distributed statistical learning[END_REF], both on the theoretical and interpretative levels, where the authors provide asymptotically exact expressions for the estimation error in the low and high-dimensional regimes, notably highlighting two different behaviors. Moreover, they deliver a noticeable interpretation regarding the effect of averaging: it reduces the variance, but not the bias. This clarification enables, at a later stage, the interpretation of the weights derived from the minimization of an upper bound of the MSE.

Aggregated estimation in federated learning

Setup of federated learning. We consider the following general statistical setting: in this work, the class of model is reduced to a set of functions parameterized by θ P Θ with Θ Ă R d , with d, the dimension of the parameter space. The regime considered here is low-dimensional. We remind that our focus lies on the effect of the distribution of sample sizes, thus the framework is restricted to an i.i.d. hypothesis in order to derive initial results, i.e. all nodes are sampled according to the same distribution. Let Z be a random variable, defined on an instance space Z. All along this work, the letter C stands for a constant. Indeed, the same letter is used to refer to different constants for the sake of readability. Definition 2.1 (Federated setting). For a set of m nodes, the federated setting is defined as follows. Each node i P rms owns an i.i.d. sample of size n i of the random variable Z, tz ij P Z : j P rn i su. Given a loss function ℓ : Θ ˆZ Ñ R `, the risk is defined as Rpθq :" Erℓpθ; Zqs. Lastly, we set θ ˚P arg min θPΘ Rpθq.

Empirical risk minimization. In this work, we aim at estimating θ ˚. Since we do not have access to the distribution of the random variable Z, we use the empirical risk defined, in the centralized setting, as Rpθq :" 1 N ř N j ℓpθ; z j q. A widespread approach to solve this problem is the empirical risk minimization (ERM) and can be reformulated as follows, with θc being the centralized parameter: θc P arg min θPΘ Rpθq. In one-shot federated learning, each node i estimates its local parameter θi P arg min θPΘ Ri pθq, defining the local empirical risk as the following: Ri pθq :"

1 ni ř ni j ℓpθ; z ij q.
The final aggregated parameter is usually a convex combination of the local estimates: θw :" ř m i"1 w i θi . This general definition embraces both the averaging scheme, i.e. w i " 1 m , and the plain federated weighting scheme, i.e. w i " ni N . We denote the federated parameter by θs :"

ř i ni N θi .
Main result of the paper: weighting scheme for one-shot federated learning. The proposed weighting scheme relies both on the minimization of an upper bound of the MSE and on one key result of this work, Theorem 3.1. Our result, admitting an informative closed-form formula, implies that only a portion K out of the m nodes -the nodes with the largest sample sizes -participates to the final aggregated parameter. The proposed weighting scheme, is the following:

ŵpiq " $ & % n piq 2 2`ř K j 1 n pjq ř K j n pjq ´1 2n piq , @i ď K 0, @i ą K,
where n piq are the reordered n i , i.e., n p1q ě ¨¨¨ě n pmq with ŵpiq , the corresponding value for n piq , i.e., if n piq " n p , then ŵpiq " ŵp . We define

K " arg max kPrms $ & % 1 n 2 pkq ď 2 `řk j 1 n pjq ř k j n pjq , .
-.

The federated estimate with statistical correction is then obtained as θŵ :" ř m i"1 ŵpiq θpiq where the θpiq are the corresponding value for n piq .

Regularity assumptions

An important step in this paper is to provide an upper bound on the MSE: Er} θw ´θ˚}2 s. Our attention was therefore drawn to similar works done in the context of distributed learning. Following Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] and Jordan et al. [START_REF] Jordan | Communication-efficient distributed statistical inference[END_REF], we assume the following assumptions which are classical in the framework of statistical analysis of M-estimators.

Assumption 2.2 (Unicity)

. There exists a unique parameter θ ˚P intpΘq such that θ ˚" arg min θPΘ Rpθq, with intpΘq, the interior of Θ. Assumption 2.3 (Parameter space). The parameter space Θ Ď R d is assumed to be compact and convex. Moreover, the parameter space is bounded by R ą 0, i.e. R " sup θPΘ }θ ´θ˚} 2 .

The assumption below is considered for moments of order 8 in Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] and of order 16 in Jordan et al. [START_REF] Jordan | Communication-efficient distributed statistical inference[END_REF]. One of the contributions of this paper is the reduction of these assumptions to order 4.

Assumption 2.4 (Loss function smoothness). The loss function ℓ : Θ ˆZ Ñ R `is assumed convex and twice differentiable with respect to θ. There exist a function L : Z Ñ R `and a constant L P R such that, for all z P Z, ∇ 2 ℓp¨, zq is Lpzq-Lipschitz continuous within a Euclidean ball centered at θ ˚and of radius ρ ą 0, B ρ pθ ˚q :" tθ : }θ ´θ˚} ď ρu, i.e. for all θ, θ

3 Federated estimation with statistical correction

Upper bounds on local MSE and local bias

In order to decompose the global MSE, our attention is therefore focused on Er} θi ´θ˚}2 s, the local MSE and on }Er θi s ´θ˚}2 , the local bias. Drawing on the work of Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] by alleviating the assumptions and improving the readability of the proof, we reached the result above. Our final result is somewhat different because we took a different approach regarding the control of the the bias term. It is this part of the result that allows us to ease the proof (9 pages in total with the proofs of the lemmas in the original paper) and to reduce the assumptions. We recall that all along this work, the letter C stands for a constant and the same letter is used to refer to different constants. Theorem 3.1. Under assumptions 1 to 4 and with θi as previously defined, for any node i, we have the following result:

Er} θi ´θ˚}2 s ď CG 2 λ 2 n i `Op 1 n 2 i q and }Er θi s ´θ˚}2 ď 1 n 2 i ´C logp2dqH 2 G 2 λ 4 `CL 2 G 4 λ 6 `C logp4dqH 4 λ 4 ¯.
Returning to the MSE of the one-shot aggregated parameter, we consider the MSE bias-variance decomposition. With tr(.) being the trace operator and V(.) denoting the variance matrix, by independence and using that trpVp θi qq " Er} θi ´θ˚}2 s ´}Er θi s ´θ˚}2 , we get the following result:

Er} θw ´θ˚}2 s " Er} ÿ i w i θi ´θ˚}2 s " ÿ i w 2 i trpVp θi qq `} ÿ i w i pEr θi s ´θ˚q } 2 ď ÿ i w 2 i trpVp θi qq `m ÿ i w 2 i }Er θi s ´θ˚}2 by Cauchy-Schwarz ď ÿ i w 2 i Er} θi ´θ˚}2 s `pm ´1q ÿ i w 2 i }Er θi s ´θ˚}2 .
A direct application of Theorem 3.1 leads us to the following proposition:

Proposition 3.2. Under assumptions 1 to 4 and with θi as previously defined, for any node i, we have the following result:

Er} θw ´θ˚}2 s ď CG 2 λ 2 ÿ i w 2 i n i `´C logp2dqH 2 G 2 λ 4 `CL 2 G 4 λ 6 `C logp4dqH 4 λ 4 ¯m ÿ i w 2 i n 2 i `O ˜ÿ i w 2 i n 2 i ¸.
Roughly, we can see that the MSE has a first term of order O ´ři

w 2 i ni ¯and a second one of order O ´m ř i w 2 i n 2 i ¯.
We remark that the first term, corresponding to the aggregation of the local variances (or local MSE), is reduced by aggregation. The second one, corresponding to the aggregation of the local biases, presents a factor m, is then not reduced. We would like to point out that it is on the basis of this intuition that Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] proposed the algorithm (SAVGM) based on the reduction of the bias of each local estimator. Besides, this work focuses on the weighting of local estimators but does not exclude that additional processing can be done on the estimators. For instance, it is possible to couple the two approaches. Considering the standard federated parameter, i.e. with w i " ni N , we get the following result: Corollary 3.3. Under assumptions 1 to 4 and with θi as previously defined, for any node i, we have the following result:

Er} θs ´θ˚}2 s ď CG 2 λ 2 1 N `m2 N 2 ´C logp2dqH 2 G 2 λ 4 `CL 2 G 4 λ 6 C logp4dqH 4 λ 4 ¯`O ´m N 2 ¯.
We observe that the main term is the one of order O ´m2 N 2 ¯and corresponds to the non-reduced variance (or equivalently MSE) term.

Optimization of the weights

In this work, we aim at aggregate each local parameter θi through a weighting scheme minimizing the upper bound on the global MSE. We start from the MSE bias-variance decomposition and apply Jensen's inequality:

Er} ÿ i w i θi ´θ˚}2 s " ÿ i w 2 i trpVp θi qq `} ÿ i w i pEr θi s ´θ˚q } 2 ď ÿ i w 2 i trpVp θi qq `ÿ i w i }Er θi s ´θ˚}2 .
Therefore, we want to solve the following optimization problem:

arg min wľ0, w T 1"1 # m ÿ i"1 w 2 i trpVp θi qq `m ÿ i"1
w i }Er θi s ´θ˚}2

+ . (5)
The following proposition gives the form of the optimal solution of the problem, bringing us to a waterfilling structure. Further explanations on the water-filling problem are detailed in Subsection 3.4.

Solving the optimization problem

We solve this optimization problem through the Lagrangian operator and KKT conditions. We want to minimize a function of the form ř i w 2 i a i `wi b i with the inequality constraint being w ľ 0 (non-negative weights) and the equality constraint being w T 1 " 1 (the weights sum to 1). Proposition 3.4. Assuming a i ą 0 for all i P rms, the optimal solution of the following convex optimization problem arg min wľ0, w T 1"1 -.

␣ř m i w 2 i a i `wi b i ( is w piq " $ & % 1 2a piq 2`ř K j b pjq a pjq ř K j 1 a pjq ´bpiq 2a piq , @i ď K 0, @i ą K,
The theoretical weighting scheme obtained can be interpreted as follows: only the nodes admitting the lowest local biases participate to the final aggregated parameter. This interpretation is consistent with the previous observation. Since the global variance is reduced by aggregation but not the global bias, the aggregation scheme focuses on reducing the bias through the selection of participating nodes, keeping only the nodes with the lowest bias. We obtain a closed-form solution enabling the computation of the theoretical weights w i with a i " trpVp θi qq and b i " }Er θi s ´θ˚}2 . This result leads to the oracle federated parameter with statistical correction θw ˚.

Since these two quantities are not known, they must be estimated. To this end, we use the behavior of the upper bound in terms of sample size of the local MSE and local bias derived from Theorem 3.1. We propose to take a i " 1 ni and b i " 1

n 2 i
for all node i. The choice to leave out the constants is heuristic and is not supported with mathematical arguments but rather on an experimental validation. From Proposition 3.4, we get that the optimal solution of the estimated optimization problem arg min

wľ0, w T 1"1 ! ř m i w 2 i ni `wi n 2 i )
is the following:

ŵpiq " $ & % n piq 2 2`ř K j 1 n pjq ř K j n pjq ´1 2n piq , @i ď K 0, @i ą K,
where n piq are the reordered n i , i.e., n p1q ě ¨¨¨ě n pmq with ŵpiq , the corresponding value for n piq , and where we define

K " arg max kPrms $ & % 1 n 2 pkq ď 2 `řk j 1 n pjq ř k j n pjq , .
-.

We thus propose the following algorithm:

Algorithm 1 Federated Estimation with Statistical Correction (FESC)

Require: m the number of nodes for i P rms do node i sends to the server n i and θi end for the server derives w piq from Proposition 3.4 with a i " 1 ni and b i " 1 n 2 i the server computes θŵ :" ř i ŵpiq θpiq Return θŵ

We define θpiq as the parameter estimated on the node with a sample size of rank i, i.e. n piq . The resulting estimate is the federated parameter with statistical correction θŵ . Since the calculation of the weights depends only on the sample sizes, it is also possible to proceed in two steps if the context requires it (especially when d is large). First, the nodes send their sample size to the server, which activates the nodes chosen by the weighting scheme. Then, the K selected nodes send their local parameters to the server. In the end, only a portion K ă m will have sent their parameter, which can reduce the number of expensive communication.

Discussion

Sample size constraint in federated learning

We recall that the main term of Corrolary 3.3 is of order O ´m2 N 2 ¯. We now consider the randomness with respect to the sample size of the nodes. Assuming that the sample size of the nodes are sampled according to η, a random variable with values in N, 1 m ř i n i can be seen as the empirical mean of η, denoted by η m . Thus, regarding the condition on the sample size of the nodes, we immediately have the following result: Corollary 3.5. The federated estimator θs reaches the behavior of the centralized one when η m " Ωpmq.

Thus, we find a result corresponding, in a way, to the distributed setting, requiring at least as many observations per node as there are nodes. The difference here is that this condition is required on average. One key message of this article is that, in the one-shot federated learning, the sample size constraint is still effective, this is why it can be relevant to select the nodes participating in the learning. This selection can be made through ensemble learning methods [START_REF] Guha | One-shot federated learning[END_REF] , weighting schemes or handcrafter rules for instance.

Water-filling problem

We observe that the optimization problem ( 5) is part of the following set of convex optimization:

arg max wľ0, w T 1ďP # m ÿ i f i pw i q

+

where P ą 0 and the functions f i are real-valued, increasing, strictly concave and with continuous first order derivative. This kind of optimization problem is typical of the ones faced in the literature of wireless communications and is related to resource allocation problems. It is well known that the solution of such problem has a water-filling structure [START_REF] Xing | New viewpoint and algorithms for water-filling solutions in wireless communications[END_REF]. The canonical problem being the one with P " 1 and f i pw i q " logp1 `αi w i q, referred to as water filling problem, comes from information theory. It models the problem of allocating power to a set of communication channel and admits this nice interpretation: we have a total quantity of water equal to one, to pour over a pool with fluctuating bottom, see Figure 3. The development of the resolution of the water filling problem can be found page 245 of Boyd et al. [START_REF] Boyd | Convex optimization[END_REF]. Remarkably, we note that the resulting procedure is consistent with the data selection strategy of ensemble learning, where a node participates if its sample size exceed a predetermined baseline value [START_REF] Guha | One-shot federated learning[END_REF].

Limitations

One crucial limitation of this work is the i.i.d. sampling process hypothesis. We hope that now that we have addressed the i.i.d. case, further studies will build on this work to examine the non-i.i.d. case. Indeed, the main difficulty is that if the sampling is non identically distributed, θ ˚is different across the nodes. However, we mention that under the following two conditions, all the results of this paper remains valid: piq the non identically distributed assumption is embodied in a label and/or feature distribution skew, meaning that the conditional distribution between feature and label is shared among nodes (see Kairouz et al. (2019) section 3.1); piiq the model is well-specified, i.e. the Bayes predictor belongs to the class of functions of interest, parametric functions in this work for instance. Indeed, in that case, the local oracle minimizers are the same across the nodes. Hence part of the arguments developed in our paper could be relevant as a partial argument to address non-i.i.d. sampling processes. The second limitation of this work lies in the choice based on heuristics regarding the estimation of a i and b i . The estimated weighting was crafted thanks to empirical calibration in order to have a consistent weighting. As the experiments were conducted on a well-specified problem (ridge regression on a linear model, see Section 4), it is possible that this preliminary estimation may be limited in a misspecified setting. For more complex models, we encourage the exploration of methods for estimating these local quantities such as bootstrap procedures.

Numerical experiments

We report here the experiments realized on synthetic data. We compare the MSE of the 4 following parameters: the centralized θc , the federated θs , the oracle federated with statistical correction θw ånd the federated with statistical correction θŵ . For each of our experiments, we set a fixed number of nodes m " 500. We recall that our work aim to highlight the key role of the local sample sizes. We denote by η the random variable associated to their distribution and express the mean of η according to powers of m, i.e. Erηs " m γ . Experiments are realized in a supervised setting, i.e. Z " pX, Y q, with X a random variable with values in R d and Y with values in R. We assume a linear model: Y " X T θ ˚`ϵ, with ϵ sampled according to a standard normal distribution. Specifically, we generate the synthetic data, with d " 50, as follows. θ ˚is sampled according to a multivariate uniform distribution with support r0, 1s d , X according to a multivariate standard normal distribution. η is generated by taking the integer value of a lognormal random variable, such that logpηq has variance σ 2 " 1. For each of the 50 runs and for all γ between 0.2 and 1.2, with a step size of 0.1, we perform the following. First, we generate the m samples sizes and the associated samples. We then estimate the central and the local parameters through a ridge regression, with the regularization parameter equal to the inverse of the squared root of the sample size. We derive the local variances and MSE from the known closed-form formulas of bias and variance of the ridge estimate, using the knowledge of θ ˚. Using the closed-form expression of the optimization problem, we compute the oracle weights and the approximated weights. Finally, by aggregation, we get the different parameters. Using the exact value of θ ˚, we derive the corresponding MSE.

Here, we can define an asymptotic regime corresponding to γ Ñ 8. We observe that the parameter obtained with FESC outperforms the standard federated one for all the observed value of γ and converges faster to the centralized parameter. By testing different distribution for η, we observed that, at fixed mean, the greater the variance of the distribution is, the more accurate θw ˚and θŵ are. We have developed an online demo based on the method presented in the paper. For a broad collection of distributions on node-level sample size, the demo displays the MSE for the three estimators considered (FESC, the plain federated one and the centralized one). For the sake of computation time, the MSE are estimated only in one run ( unlike the article where the estimation is done on 50 runs). In this demo, we observe that indeed, when the chosen distribution has a high variance (lognormal, pareto, weibull), FESC converges faster to the centralized estimator than the classical federated estimator. An intuitive explanation for this phenomenon is that only the nodes with the largest sample sizes are retained. So when the variance increases, the probability of observing large sample sizes increases and so does the statistical power of the selected nodes. In the appendix, Figure 4, we can see that the fraction of activated node grows as the mean sample size increases. Node selection enables artificially lowering the number of nodes to reduce the effects of the constraint on the sample size observed in distributed learning. Finally, experimentations on FEMNIST can be found in the appendix.

Conclusion

In this paper, we provide upper bounds on the local MSE and bias and derived the one of the plain federated parameter in a very general setting of ERM. The key message of our work is the crucial role of the sample sizes in the one-shot federated learning setting. We also translate the minimum sample size constraint faced in distributed learning to federated learning. We propose a procedure to aggregate the local estimations based on a minimization of an upper bound of the MSE, resulting in a closed-form formula. This simple and communication-efficient weighting scheme implies that only a fraction -the nodes with the largest sample sizes -participate to the final aggregated parameter. Even though this weighting scheme is developed in a one-shot setting, we believe that the proposed practice can be embedded in a wide variety of algorithms used in federated learning instead of the standard averaging scheme. We also tested FESC on the image classification federated dataset FEMNIST. In this dataset, data are sorted out based on the writer of the digit/character (corresponding to a node) from original MNIST data [START_REF] Caldas | Leaf: A benchmark for federated settings[END_REF]. After discarding the nodes that do not have at least one sample of each of the 10 digits, we then estimate the central and the local parameters through a ridge regression, with the regularization parameter equal to the inverse of the squared root of the sample size. Then, from the known sample sizes, we compute the weights of FESC and of the federated estimator to generate the aggregated parameters. Finally, we simulate the error ratio of the classification task on the test set for FESC, the federated estimator and the centralized estimator.

A Appendix

B Appendix

In this appendix we prove Theorem 3.1: Theorem 3.1. Under assumptions 1 to 4 and with θi as previously defined, for any node i, we have the following result:

Er} θi ´θ˚}2 s ď CG 2 λ 2 n i `Op 1 n 2 i q and }Er θi s ´θ˚}2 ď 1 n 2 i ´C logp2dqH 2 G 2 λ 4 `CL 2 G 4 λ 6 `C logp4dqH 4 λ 4 ¯.
Proof. We begin by defining three good events that enable to bound the Lipschitz constant, the gradient of the empirical risk at θ ˚and, finally, the distance between the empirical risk and the true risk in θ ˚. These events allow us to show that the local empirical risk minimizer θi is within a ball of radius smaller than ρ. Moreover, they guarantee the continuity of ∇ Ri between θ ˚and θi , providing the needed assumptions to perform a Taylor expansion under the Lagrange form. Let define E 0,i :"

# 1 n i ÿ j LpZ j q ď 2L + E 1,i :" " ~∇2 Ri pθ ˚q ´∇2 Rpθ ˚q~ď ρλ 2 * E 2,i :" " }∇ Ri pθ ˚q} ď p1 ´ρqλδ ρ 2 * with δ ρ :" min ´ρ, ρλ 4L ¯. Defining E i :" E 0,i Ş E 1,i Ş E 2
,i , we then state the following lemma:

Lemma B.1. Under assumptions 1 to 4 and under E i , Ri is p1 ´ρqλ-strongly convex over B δρ pθ ˚q and the minimizer θi belongs to B δρ pθ ˚q. In particular, it yields the following inequality:

} θi ´θ˚} ď 1 p1 ´ρqλ }∇ Ri pθ ˚q} under E i . (6)
Then, we decompose the difference between θ ˚and θi with the objective of carrying out a Taylor expansion of ∇ Ri between θ ˚and θi since θi belongs to B δρ pθ ˚q and hence to B ρ pθ ˚q under E i : θi ´θ˚" p θi ´θ˚q 1 Ei `pθ i ´θ˚q 1 Ei .

Moreover, under E i , there exists θ between θi and θ ˚such that:

∇ Ri p θi q " ∇ Ri
Therefore, we now focus on these three terms and bound them by means of two lemmas. The first one is borrowed from Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF] (Lemma 7) and is thus not demonstrated. Lemma B.2. Under assumptions 1 to 4, there exist two constants both termed C such that:

Er}∇ Ri pθ ˚q} 4 s ď CG 4 n 2 i (10) Er~P i ~4s ď C log 2 p2dqH 4 n 2 i . (11)
Combining the first two lemmas, i.e., Equations 6 and 10, we obtain the following inequality:

Er} θi ´θ˚}4 1 Ei s ď 1 p1 ´ρq 4 λ 4 Er}∇ Ri pθ ˚q} 4 1 Ei s ď 1 p1 ´ρq 4 λ 4 Er}∇ Ri pθ ˚q} 4 s ď CG 4 λ 4 n 2 i . (12)
The next lemma enables to control the term associated to Q i :

Lemma B.3. Under assumptions 1 to 4 and under E i ,

}Q i p θi ´θ˚q } 2 ď 4L 2 } θi ´θ˚}4 . (13)
We can now go back to Equation 9. The first term is controlled by Equation 10 using Jensen's inequality. For the second one, we use Cauchy-Schwarz inequality and Equation 12. There exists a constant C such that:

Er}P i p θi ´θ˚q } 2 1 Ei s ď Er~P i ~2} θi ´θ˚}2 1 Ei s ď a Er~P i ~4s b Er} θi ´θ˚}4 1 Ei s ď C logp2dqH 2 G 2 λ 2 n 2 i . (14)
Finally, the last term is given by Equations 12 and 13:

Er}Q i p θi ´θ˚q } 2 1 Ei s ď 4L 2 Er} θi ´θ˚}4 1 Ei s ď CL 2 G 4 λ 4 n 2 i . (15)
Therefore, there exist constants termed C such that Equation 9 boils down to: Which proves the first part of Theorem 3.1. Lastly, we turn our attention to the local bias }Er θi s´θ ˚}2 . We use that θ ˚is the minimizer of each local risk implying that ∇R i pθ ˚q " 0. Moreover, under the event E 2,i , ∇ Ri pθ ˚q is bounded. Thus, we can interchange the derivative and the expectation resulting to Er∇ Ri pθ ˚qs " 0. Embedding ρ, δ ρ and R in the constants for more readability, we can now conclude that:

E " } ´∇

D appendix

In this appendix, we prove Proposition 3.4.

Proposition 3.4. Assuming a i ą 0 for all i P rms, the optimal solution of the following convex optimization problem arg min Proof. We solve this optimization problem through the Lagrangian operator and KKT conditions. We want to minimize a function of the form ř i w 2 i a i `wi b i with the inequality constraint being w ľ 0 (non-negative weights) and the equality constraint being w T 1 " 1 (the weights sum to 1). Lpw, λ, νq " -.

ÿ i w 2 i a i `wi b i ´ÿ i λ i w i `ν ˜ÿ i w i ´1B L Bw i " 2w i a i `bi ´λi `ν BL Bw i " 0 ô w i " λ i ´bi ´ν 2a i λ i w i " 0 ô " if b i ď ´ν, λ i " 0, w i " ´bi´ν

  where b piq are the reordered b i , i.e., b p1q ď ¨¨¨ď b pmq with a piq , w piq , the corresponding values for b piq , and where we define K " arg max kPrms

Figure 1 :

 1 Figure 1: MSE variation of the 4 parameters according to γ such that each node holds n i observations sampled from a distribution with mean m γ . Ridge regression with m " 500 and d " 50 over 50 runs.

Figure 2 :

 2 Figure 2: Illustration of the constraint on the sample size of the machines in distributed learning. Each of the m " 500 machines performs a ridge regression on n " m γ observations of dimension d " 50, sampled according to a linear model, over 50 runs -y-axis: MSE of the centralized and the distributed parameters on a logarithmic scale according to γ (x-axis).

Figure 3 :

 3 Figure 3: Illustration of the interpretation of the water-filling structure solution. The pool is fooled to a level ν, corresponding to a total quantity of water equal to one.

Figure 4 :

 4 Figure 4: Variation of the fraction of nodes activated during the weighting scheme according to γ.

  2a piq , @i ď K 0, @i ą K, where b piq are the reordered b i , i.e., b p1q ď ¨¨¨ď b pmq with a piq , w piq , the corresponding values for b piq , and where we define K " arg max kPrms

  2a piq , @i ď K 0, @i ą K where b piq are the reordered b i , i.e., b p1q ď ¨¨¨ď b pmq with a piq , w piq , the corresponding values for b piq , i.e., if b piq " b p , then a piq " a p and w piq " w p . We define K " arg max kPrms

  B ρ pθ ˚q: ˇˇˇˇˇˇ∇ 2 ℓpθ 1 , zq ´∇2 ℓpθ, zq ˇˇˇˇˇˇď Lpzq}θ ErLpZq 4 s ď L 4 and ErpLpZq ´ErLpZqsq 4 s ď L 4 (2) Moreover, there exists G P R `such that Er}∇ℓpθ; Zq} 4 s ď G 4 for all θ P B ρ pθ ˚q. Assumption 2.5 (Risk function smoothness). The global risk function R is twice differentiable and there exists λ such that ∇ 2 Rpθ ˚q ľ λI d . Moreover, there exists H ě 0 such that: Er~∇ 2 ℓpθ; Zq ´∇2 Rpθq~4s ď H 4 for all θ P B ρ pθ ˚q.

	1	´θ}	(1)
	with (3)

1 P

Table 1 :

 1 Error percentage of the 3 parameters on FEMNIST when performing ridge regression with d " 784 and m " 3366 and an average of 101 samples per node.

	FESC	0.6823
	Federated	0.6789
	Centralized 0.7713

  pθ ˚q `∇2 Ri pθqp θi ´θ˚q 0 " ∇ Ri pθ ˚q `p∇ 2 Ri pθq ´∇2 Ri pθ ˚qqp θi ´θ˚q `p∇ 2 Ri pθ ˚q ´∇2 Rpθ ˚qqp θi ´θ˚q `∇2 Rpθ ˚qp θi ´θ˚q θi ´θ˚" ´Ipθ ˚q∇ Ri pθ ˚q `Ipθ ˚qp∇ 2 Ri pθ ˚q ´∇2 Ri pθqqp θi ´θ˚q `Ipθ ˚qp∇ 2 Ri pθ ˚q ´∇2 Rpθ ˚qqp θi ´θ˚q θi ´θ˚" Ipθ ˚qp´∇ Ri pθ ˚q `pP i `Qi qp θi Ri pθ ˚q ´∇2 Rpθ ˚q and Q i " ∇ 2 Ri pθ ˚q ´∇2 Ri pθq. Thus, Ei s `Er} θi ´θ˚}2 |E i sPpE i q ď Er}Ipθ ˚qp´∇ Ri pθ ˚q `pP i `Qi qp θi ´θ˚q q} 2 1 Ei s `R2 PpE i q ď ~Ipθ ˚q~2Er} ´∇ Ri pθ ˚q `pP i `Qi qp θi ´θ˚q } 2 1 Ei s `R2 PpE i q by submultiplicativity of the operator norm. Using twice that }a `b} 2 ď 2}a} 2 `2}b} 2 , we get that Er} ´∇ Ri pθ ˚q `pP i `Qi qp θi ´θ˚q } 2 1 Ei s ď2Er}∇ Ri pθ ˚q} 2 1 Ei s `4Er}P i p θi ´θ˚q } 2 1 Ei s `4Er}Q i p θi ´θ˚q } 2 1 Ei s.

				´θ˚q q	(8)
	with Ipθ ˚q " `∇2 Rpθ	˚q˘´1	, P i " ∇ 2
	Er} θi	´θ˚}2 s " Er} θi	´θ˚}2 1 Ei s `Er} θi ´θ˚}2 1 Ei s
		" Er} θi	´θ˚}2 1

  Ri pθ ˚q `pP i `Qi qp θi ´θ˚q } 2 1 Ei It only remains to ensure that the event E i occurs with a sufficiently low probability to conclude on the local MSE term Er} θi ´θ˚}2 s. Lemma B.4. Under assumptions 1 to 4, there exist constants termed C such that

							ı
		ď	CG 2 n i	`C logp2dqH 2 G 2 λ 2 n 2 i	`CL 2 G 4 λ 4 n 2 i
		ď	CG 2 n i	`Op	1 i n 2	q.
		P `Ei	˘ď C n 2 i	`C logp4dqH 4 ρ 4 λ 4 n 2 i	`CG 4 λ 4 δ 4 ρ n 2 i	.	(16)
	Recalling that ~Ipθ ˚q~2 ď 1 λ 2 , we finally obtain
	Er} θi	´θ˚}2 s ď	ˆCG 2 λ 2 n i	`C logp2dqH 2 G 2 λ 4 n 2 i	i λ 6 n 2 `CL 2 G 4	Ṙ2
						ˆC n 2 i	`C logp4dqH 4 ρ 4 λ 4 n 2 i	λ 4 δ 4 ρ n 2 i `CG 4	ď
						CG 2 λ 2 n i	`Op	1 i n 2	q.

  Starting in a similar way to Equations 7 and 8: θi ´θ˚" Ipθ ˚qp´∇ Ri pθ ˚q `pP i `Qi qp θi ´θ˚q q1 Ei `pθ i ´θ˚q 1 Ei Er θi s ´θ˚" Ipθ ˚qErpP i `Qi qp θi ´θ˚q 1 Ei s `Erp θi ´θ˚q 1 Ei s }Er θi s ´θ˚}2 ď 2}Ipθ ˚qErpP i `Qi qp θi ´θ˚q 1 Ei s} 2 `2}Erp θi ´θ˚q 1 Ei s} 2 ď 2~Ipθ ˚q~2Er}pP i `Qi qp θi ´θ˚q 1 Ei } 2 s `Er} θi ´θ˚}2 1 Ei s by Jensen's inequality ď 4~Ipθ ˚q~2 ´Er}P i p θi ´θ˚q } 2 1 Ei s `Er}Q i p θi ´θ˚q } 2 1 Ei s ¯`2R 2 PpE i q

	ď	C logp2dqH 2 G 2 λ 4 n 2 i	`CL 2 G 4 λ 6 n 2 i	`R2	ˆC n 2 i	`C logp4dqH 4 ρ 4 λ 4 n 2 i	`CG 4 λ 4 δ 4 ρ n 2

i ṫhrough Equations 14, 15, and 16 for the last line.

It is well-known that pseudonymization is far from being a solid guarantee for preserving privacy, indeed the re-identification of de-identified data is often within reach[START_REF] Sweeney | Matching known patients to health records in washington state data[END_REF].

Acknowledgments and Disclosure of Funding

This work was supported by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH. Part of this work has been founded by the Industrial Data Analytics And Machine Learning chairs of ENS Paris-Saclay.

}Er θi s ´θ˚}2 ď

Which proves the second part of Theorem 3.1.

C Appendix

In this section, we prove the lemmas used in Appendix B.

Lemma B.1. Under assumptions 1 to 4 and under E i , Ri is p1 ´ρqλ-strongly convex over B δρ pθ ˚q and the minimizer θi belongs to B δρ pθ ˚q. In particular, it yields the following inequality:

Proof. The proof stating that Ri is p1 ´ρqλ-strongly convex is borrowed from Zhang et al. [START_REF] Zhang | Communication-efficient algorithms for statistical optimization[END_REF]: let θ be in B δρ pθ ˚q, we use the local strong convexity of R around θ ˚, δ ρ being smaller than ρ. Starting from the decomposition below, we just need to minimize the second term in term of matrix partial order to obtain the strong convexity of Ri .

Proof.

LpZ j q ¯}θ ´θ˚} } θi ´θ˚} ď 2L} θi ´θ˚}2 since we are under E i .

Lemma B.4. Under assumptions 1 to 4, there exist constants termed C such that

PpE i q ď PpE 0,i q `PpE 1,i q `PpE 2,i q ď C n


Yann Busnel

à pair profite aux réseaux de capteurs très étendus ENVIRONNEMENT

Le modèle de pair

des stations de base. Ceux-ci ont plus de ressources matérielles et permettent de collecter et stocker les informations issues des capteurs.

L'intérêt de la recherche et de l'industrie pour ce domaine n'a cessé de s'intensifier dernièrement. Les raisons en sont multiples : la perspective d'une excellente fiabilité de ces systèmes, leur précision, leur flexibilité, leur faible coût, leur facilité de déploiement, etc. Les caractéristiques des WSN permettent en outre d'envisager de nombreuses applications d'observation réparties dans l'espace : observation de l'environnement naturel (pollution, inondation, etc.), suivi d'écosystèmes (surveillance de niches d'oiseaux, croissance des plantes, etc.), contrôle militaire (télésurveillance de champs de bataille, détection d'ennemis, etc.), analyses biomédicales et surveillance médicale (détection de cancer, rétine artificielle, taux de glucose, diabètes, etc.)… Le déploiement de ces réseaux de capteurs sans fil soulève diverses questions. Quelle sera la spontanéité, l'adaptabilité du réseau ou encore la dynamicité de la topologie ?

Qu'entend-on par dynamicité de la topologie ?

Ces éléments restent encore à définir. Compte tenu du nombre potentiellement important de capteurs participants et de leurs ressources réduites, il paraît indispensable de développer des solutions entièrement décentralisées, répartissant la charge entre les participants et permettant de passer à l'échelle. De nombreux procédés de systèmes distribués, et plus particulièrement ceux issus du modèle de pair à pair (P2P), apparaissent adaptables aux réseaux de capteurs sans fil.

Le modèle de communication pair à pair en particulier est doté d'une capacité qui lui est propre : le passage à l'échelle. Les systèmes reposant sur ce modèle -appelés systèmes P2P par la suite -sont totalement décentralisés, chaque noeud jouant à la fois le rôle de client et de serveur. La charge étant répartie sur tous les noeuds du système, augmenter le nombre de participants n'induit pas de goulot d'étranglement ni de point critique de défaillance, alors que ces phénomènes sont couramment observés lors de l'utilisation du modèle client/serveur. Par ailleurs, la vision uniquement locale des noeuds des systèmes P2P, synonyme d'une méconnaissance globale du système et d'une communication avec un sous-ensemble restreint de participants, rend avantageuse l'adaptation de ceux-ci aux WSN.

Alors qu'un grand nombre d'applications mettent en jeu des réseaux de capteurs sans fil, ceux-ci ont

Des défis communs à tous les réseaux de capteurs sans fil

Les protocoles de routage au sein des réseaux de capteurs sans fil sont influencés par plusieurs facteurs déterminants.

Premier défi : une consommation d'énergie sans perte d'efficacité. Les capteurs utilisent leur réserve d'énergie à des fins de calcul et de transmission de données. Leur durée de vie dépend donc essentiellement de celle de leur batterie. Dans un WSN, chaque noeud joue le rôle d'émetteur et de routeur. La moindre défaillance énergétique d'un capteur peut donc changer significativement la topologie du réseau et imposer une réorganisation coûteuse de ce dernier. Le deuxième défi à relever, la tolérance aux fautes, souligne le fait que certains noeuds peuvent être défaillants ou inhibés à cause d'un manque d'énergie, d'un dommage physique ou d'une interférence, mais cela ne doit bien entendu pas affecter la globalité de la tâche du réseau de capteurs. En cas de défaillance, de nouveaux liens et routes doivent pouvoir être établis pour assurer la collecte des données. La redondance peut également être utilisée, tout en veillant à conserver une faible consommation d'énergie. Enfin, le troisième défi que les WSN doivent remporter est la couverture. Dans ces réseaux de capteurs, chaque noeud perçoit uniquement une vue locale de son environnement, limitée par sa portée et sa précision. La couverture d'un vaste espace déterminé est donc composée de l'union de nombreuses couvertures de petite taille.

Les modèles de réseaux de capteurs présentés ici correspondent à des applications bien particulières.

Le déploiement de noeuds par exemple est un facteur dépendant de l'application qui affecte grandement les protocoles de routage. Ce déploiement peut être déterministe ou aléatoire. Dans le premier cas, les capteurs sont placés manuellement et les données peuvent donc être acheminées via des chemins prédéterminés. En revanche, avec une approche aléatoire, les capteurs sont éparpillés (lâchés d'un avion par exemple), ce qui peut alors nécessiter une stratégie de groupement (clustering).

La capture d'information et la couverture des données requises quant à elles, dépendent essentiellement de l'application considérée. Elles peuvent être classées selon différents modèles : en fonction du temps (surveillance périodique), des événements (réaction à l'occurrence d'un événement particulier), des requêtes (réponse à une demande d'une station de base) ou de manière hybride (combinaisons des précédentes approches).

Dans les nombreuses études réalisées, tous les capteurs d'une application sont considérés comme homogènes : ils ont donc une même capacité de calcul, de communication et d'énergie. Néanmoins, en fonction de l'application, certains capteurs peuvent avoir des rôles différents, générant une architecture hétérogène. Dans un WSN hiérarchique par exemple, certains capteurs sont déclarés « chef » de leur groupe, ce qui leur permet de traiter le routage vers les stations de base. Étant donné que le nombre de capteurs déployés peut être de l'ordre de la centaine ou du millier, et vraisemblablement plus dans un futur proche, les algorithmes de routage doivent être capables de fonctionner efficacement avec une grande quantité de capteurs et de traiter un grand nombre d'événements sans pour autant être saturés.

La plupart des architectures réseau reposent sur des capteurs statiques.

Qu'est-ce-qu'une architecture réseau ?

Pourtant, la mobilité des stations de base et/ou des capteurs est nécessaire dans de nombreuses applications. La capture peut être aussi bien statique (traque d'ennemis) que dynamique (surveillance de feux de forêts). Quant à la transmission de messages en provenance d'un noeud mobile ou vers ce dernier, il s'agit là d'un autre défi.

Nombreux sont les WSN qui possèdent une densité importante de capteurs, excluant ainsi l'isolement de noeuds. Toutefois, le déploiement, la mobilité et les défaillances font varier la topologie du réseau, dont la connexité n'est pas toujours assurée. De nombreux capteurs peuvent générer de la redondance dans les mesures effectuées. L'agrégation de paquets similaires en provenance de différents noeuds permet de réduire le nombre de transmissions (suppression de duplicata, minimum, moyenne, maximum, etc.). Le traitement d'un signal peut également être effectué pour l'agrégation, par fusion de données (conformation de faisceaux, ou beamforming).

Certaines applications nécessitent que la donnée soit transmise dans une certaine plage de temps, Utilité du P2P : surcharge des serveurs sur Internet. © Yann Busnel après quoi, elle devient caduque. Or, dans la plupart des cas, la durée de vie du réseau est favorisée au détriment de la qualité d'émission des données. Les protocoles de routage assurant une qualité de service et prenant en compte la gestion de l'énergie représentent un défi nouveau et stimulant.

L'approche pair à pair

Plusieurs approches permettant de construire un système issu du modèle de pair à pair ont récemment émergé, formant ainsi des systèmes distribués de grande taille ayant la capacité de passer à l'échelle. Contrairement aux approches client-serveur, les noeuds sont connectés directement entre eux par des liens logiques (audessus du réseau physique) et jouent potentiellement à la fois les rôles de client et de serveur. Ces systèmes permettent notamment d'agréger les ressources et les services de tous les noeuds du système. Chaque noeud ne possède qu'une connaissance locale du système, permettant ainsi de développer des applications ayant des propriétés d'auto-organisation et de tolérance aux défaillances particulièrement adaptées à la grande taille des nouveaux systèmes distribués.

L'objectif des systèmes P2P est de tirer profit des ressources inutilisées des noeuds du réseau (mémoire, temps processeur, etc.). Un processus nécessitant un calcul considérable est divisé en de nombreuses petites tâches, chacune répartie sur les différents noeuds du réseau. Une unité centrale de coordination des tâches est le plus souvent utilisée pour diviser, répartir et collecter les résultats (Seti@home, Genome@home…).

Les architectures pair à pair sont présentes dans de nombreuses applications. Parmi elles, certaines classes comme la communication et la collaboration par exemple, regroupent les systèmes fournissant une infrastructure de communication et de collaboration directe entre les différents acteurs du réseau, le plus souvent en temps-réel. Le système de messagerie instantanée Jabber en est un exemple.

Par ailleurs, la plupart des systèmes P2P appartiennent à la classe d'application « distribution de données », laquelle comprend les systèmes et infrastructures conçus pour le partage de médias numériques et autres données entre les utilisateurs. La distribution de données P2P balaie un large spectre, partant d'un simple système de partage de fichier direct jusqu'à des systèmes complexes construisant une infrastructure de stockage distribuée permettant la publication, l'organisation, l'indexation, la recherche, la mise à jour et la récupération de données via KaZaA, Oceanstore, Pastry, CAN, Mnemosyne, etc.

Un grand nombre d'applications issues des infrastructures pair à pair ont ainsi émergé, proposant divers services internet tels que la diffusion multipoint, la gestion des indirections, ou encore la protection contre les dénis de service. D'importants travaux ont été menés sur la conception de base de données distribuées. Philip A. Bernstein, du centre de recherche Microso# à Redmond, et ses collègues, ont proposé le modèle relationnel local (LRM), dans lequel l'ensemble des données est stocké sur un réseau de pair à pair en de multiples bases de données locales, possédant des dépendances sémantiques entre elles. PIER par exemple, est un moteur de recherche grande échelle, construit au-dessus d'un réseau de pair à pair. D'autres propositions telles que Piazza (infrastructure de web sémantique) ou Edutella (meta-données et système de requêtes pour applications P2P) existent aussi.

Des techniques pleines de promesses

La mise en oeuvre des techniques pair à pair pour les réseaux de capteurs est un axe de recherche stimulant, prometteur et non trivial. En effet, les caractéristiques de connexions et de vision locale permettent de mettre en évidence les similarités de ces deux domaines. D'autre part, les faibles ressources des capteurs et leur voisinage imposé par leur portée de communication rendent difficile une application directe. Plusieurs facteurs entrent en jeu, notamment l'adaptation des méthodes P2P aux contraintes énergétiques, et ainsi, une maximisation de la durée de vie du réseau. Les systèmes P2P sont de manière inhérente auto-organisables, résistants aux défaillances et capables de passer à l'échelle. De nombreux axes de recherche émergent à la frontière de ces deux domaines et se focalisent actuellement sur des objectifs tels que la diffusion, l'agrégation, la collecte mais aussi la base de données physiques.

La diffusion d'information dans les WSN se fait souvent par inondation (flooding) induisant une forte consommation d'énergie, surtout autour du point d'entrée de la donnée diffusée. L'utilisation d'un protocole épidémique P2P est une solution envisageable pour diffuser de manière équitable l'information tout en conservant une rapidité de convergence.

Quant aux techniques d'agrégation de données, plusieurs existent déjà dans les réseaux de capteurs. Néanmoins, l'utilisation de techniques P2P dans l'agrégation en environnement à forte mobilité est un objectif encourageant.

En environnement dynamique et mobile, sans matériel de localisation précise des noeuds -un GPS par exemple -, l'envoi des données vers la station de base est coûteuse car le plus souvent effectuée par inondation. Une possibilité serait d'intégrer une information sur chaque noeud, mise à jour de manière épidémique, permettant d'estimer la position de la station de base sans mécanisme coûteux (en temps, en énergie,…).

La vision d'un capteur dépend du rayon de réception de son module de communication. © Yann Busnel

	plusieurs restrictions que ces applications doivent
	contourner. Par exemple, une faible puissance de
	calcul, une réserve d'énergie limitée et une bande
	passante réduite aux connexions sans fil entre
	capteurs. Un des principaux objectifs dans la
	conception de réseaux de capteurs sans fil est la
	transmission fiable de données en mettant l'accent
	sur la préservation d'énergie et la prévention de
	perte de connectivité (aucun noeud isolé par
	exemple). Ceci est assuré par le recours à une
	politique stricte de gestion d'énergie. En effet, la
	principale source de consommation d'énergie d'un
	capteur est l'utilisation du réseau sans fil via son
	module de radiocommunications.

Par ailleurs, un intérêt émergeant dans la communauté des réseaux de capteurs est la mise en place de bases de données physiques. Dans cette application, chaque capteur représente une entrée de la base de données, et les requêtes sur la base se traduisent par une collecte et/ou une agrégation de d'information provenant des noeuds participants. Dans ce cas, une base de données n'est plus la mutualisation de données physiques, mais ces dernières elles-mêmes forment la base de données. Par exemple, dans la gestion des stocks d'un grand magasin, le décompte des produits serait automatique, et continuellement à jour. Domaine émergent, aux frontières de l'étude des systèmes informatiques, des réseaux numériques et du traitement du signal, l'attrait pour les réseaux de capteurs sans fil s'accroît considérablement. Il a été présenté ci-avant les propriétés souhaitées de ces réseaux, tout en mettant en évidence leurs limitations physiques, technologiques, etc. L'avancée récente dans le développement de systèmes pair à pair et leurs similitudes avec les réseaux de capteurs ouvrent de grandes perspectives. L'intégration du modèle de pair à pair aux WSN est un objectif attrayant et prometteur. À l'heure actuelle, peu de travaux rapprochant ces deux domaines ont été publiés mais l'essor est déjà grandissant. En particulier, une nouvelle équipe de chercheurs a notamment été créée à l'IRISA de Rennes, pour étudier ce domaine. Parmi les défis présentés dans cet article, la diffusion et les bases de données physiques sont au coeur de mes recherches personnelles.Quelques références vous sont proposées pour en savoir plus sur les réseaux de capteurs.