Boost Decentralized Federated Learning in Vehicular Networks by Diversifying Data Sources

Federated learning was originally proposed by [3] to preserve the privacy of data distributed on decentralized clients during model training. FedAvg and FedSGD [3, 15] were proposed as two most fundamental model averaging algorithms in FL. They can complete model training by exchanging model parameters between the PS and clients without accessing original data samples.

Since its inception, FL has received intensive research efforts, and has been applied in various systems. To fit in different applications, variants of FedAvg/FedSGD were devised to accelerate FL. Khalil et. al. extended FedAvg by introducing a new sampling and aggregation strategy to improve the convergence speed when training a federated recommendation model [16]. In [17], Chen et. al. proposed a federated transfer learning framework for wearable healthcare to achieve personalized model learning. In [18], Yu et. al. proposed a neural-structure-aware resource management approach with module-based FL framework to improve the resource efficiency. In [19], Nishio et. al. proposed algorithms to actively manage clients based on their resource conditions to accelerate FL procedure.

Regardless of application scenarios, the data diversity is always an important factor influencing the accuracy of FL. In FL, data samples are collected and privately maintained by distributed clients, which makes data sample selection and the estimation of data sample quality difficult. In view of this difficulty, research efforts have been dedicated to diversifying data sources to improve model accuracy. In [14], Pu et. al. proposed an efficient online data scheduling policy to alleviate the data skew issue caused by the capacity heterogeneity of training workers from the long-term perspective. In [13], Wang et. al. proposed a joint sampling and data offloading optimization problem subject to constraints on the network topology and device capacities to improve FL training accuracy. Considering the similarity of datasets collected across devices, a similarity-aware data offloading strategy was proposed in a distributed manner to optimize the data dissimilarity of each device. In [12], Li et. al. reported that a low content diversity can lead to severe model accuracy deterioration based on trace driven analysis. A client sampling method jointly considering the statistical homogeneity and content diversity was proposed to improve model accuracy.

However, all these mentioned works trying to improve the diversity of data sources failed to consider the decentralized FL scenario. Due to the lack of a centralized PS in DFL, it is rather difficult to collect necessary information to diversify data sources from a global perspective. In [6], FedAvg was extended to a DFL algorithm to enable learning in arbitrarily large scale networks. Same as FedAvg, the aggregation weight is proportional to the sample population failing to diversify data sources. In [20], Hu et. al. proposed a segmented gossip aggregation approach allowing each worker to pull different model segments from chosen peers. The objective is to optimize the utilization of the bandwidth resources between workers requiring high connectivity among workers. In [5], a broadcast-based algorithm was developed to minimize the sum of convex functions scatted throughout a collection of distributed nodes. The aggregation weight of each model is merely determined by the in-degree and out-degree of each worker, which cannot effectively diversify data sources.

To accommodate intelligent applications on vehicles, privacy preserved and efficient learning framework applicable for vehicular networks becomes extremely needed. It was reported in [21, 22] that FL can benefit many important applications in autonomous driving. The works [23, 24, 25] investigated how to support data- and computation-intensive applications with low communication overhead with a strong privacy guarantee in vehicular networks.

Nevertheless, it is costly to deploy a PS to conduct centralized model aggregation for FL in large-scale vehicular networks. In [26], an RSU (Road Side Unit) based model aggregation method was proposed to conduct FL. However, pervasively deploying RSUs can be very costly. Thereby, pure V2V solutions are extensively explored by [27, 28, 29, 30]. These works indicate the feasibility to implement DFL in vehicular networks by allowing each vehicle to aggregate models collected from neighbours directly. In [31, 32], blockchain-based FL was proposed to enable decentralized FL. Whereas, the FL efficiency of these works cannot be guaranteed.

Based on the above discussion, existing works on DFL in vehicular networks largely overlooked the influence of data source diversity when aggregating models. Consequently, it is hard for them to achieve high model accuracy on every individual vehicles.

Without loss of generality, we suppose that $n$ data samples $[(\mathbf{x}_{i},y_{i})]_{i=1}^{n}$ are distributed among $K$ clients in the FL system. The process to train a machine learning model can be regarded as the process to minimize a loss function. The loss function of a particular sample $i$ can be defined as $f_{i}(\mathbf{w})={l}(\mathbf{x}_{i},y_{i};\mathbf{w})$, where $\mathbf{w}$ represents model parameters to be learned. The objective of FL is to minimize the overall loss function defined as

Let $\mathcal{N}_{k}$ denote the set of data samples owned by client $k$ and $n_{k}=|\mathcal{N}_{k}|$. The objective in Eq. (1) can be rewritten as

FederatedAveraging (FedAvg) minimizes the loss function by conducting multiple global iterations (a.k.a epochs) with the assistance of the PS. The learning process consists of the following steps.

• •

  The PS randomly and uniformly selects $m$ clients, denoted by $\mathcal{P}_{t}$, to participate local model update in the $t$-th global iteration. This client selection scheme can ensure the diversity of data sources for model aggregation.

• •

  Each participating client $k$ downloads the latest global model²²2The global model in the first global iteration can be randomly initialized by the PS. from the PS to perform $E$ local updates according to the formula of each local update as below with local data samples.

  $$\mathbf{w}^{k}\leftarrow\mathbf{w}^{k}-\eta\nabla F_{k}(\mathbf{w}^{k},\mathcal{B}_{k}),\quad\forall k,$$

  (3)

  where $\eta$ is the learning rate and $\mathcal{B}_{k}$ is a batch of samples selected from $\mathcal{N}_{k}$. Then, the updated model parameters are uploaded to the PS.

• •

  The PS aggregates all updated models from participating clients as

  $$\mathbf{w}_{t+1}\leftarrow\sum_{k\in\mathcal{P}_{t}}\alpha_{k,t}\mathbf{w}_{t+1}^{k}.$$

  (4)

  Here $\alpha_{k,t}$ represents the weight of participating client $k$ for model aggregation in the $t$-th global iteration. It is usual to set $\alpha_{k,t}$ proportional to $n_{k}$.

• •

  Repeat the above three steps until the model converges.

Decentralized FedAvg can be easily extended from FedAvg by enabling each client to collect model parameters from its neighbour clients directly. It is equivalent to implementing the function of the PS on each client. Many existing works can be perceived as variants of decentralized FedAvg such as the sub-gradient push algorithm proposed in [5].

Nevertheless, it is tricky to properly set $\alpha_{k,t}$ when deploying DFL in vehicular networks. Considering the constraints of vehicle routes and communication distances, an individual vehicle cannot uniformly and randomly select other vehicles as its neighbours to diversify data sources contributed to its model training. Consequently, it becomes a challenging problem to properly set $\alpha_{k,t}$ for DFL in vehicular networks. In [5, 8], it was proposed to set $\alpha_{k,t}$ according to in-degrees and out-degrees of client $k$, which has ignored the influence of data source diversity on the model accuracy. We will further explore the deficiency to implement such algorithms in vehicular networks with a simulation study in the next section.

We study a vehicular network with $K$ vehicles. Each vehicle owns a dataset $\mathcal{N}_{k}$. Each vehicle is equipped with certain computation and communication capacity. It can either park or move along roads. We consider a synchronized DFL system. Each vehicle $k$ conducts $E$ local iterations according to Eq. (3) with its own dataset $\mathcal{N}_{k}$ and its model $\mathbf{w}^{k}_{t}$ in the $t$-th global iteration. When local iterations are completed, all vehicles make efforts to contact other vehicles in their proximity. Then, two vehicles can exchange model parameters if their distance is within the communication range. Let $\mathcal{M}_{k,t}$ denote the set of neighbor vehicles, which can exchange models with vehicle $k$ for the $t$-th round of model aggregation. Let $\mathcal{P}_{k,t}=\mathcal{M}_{k,t}\cup\{k\}$ denote the set of all vehicles involved in the $t$-th round of model aggregation on vehicle $k$. After collecting model parameters from vehicles in $\mathcal{M}_{k,t}$, vehicle $k$ conducts aggregation according to Eq. (4). With refined parameters, vehicles proceed to the next round of global iteration.

To facilitate the understanding of our work, frequently used notations are summarized with brief explanations in Table I.

We implement a simulator to conduct DFL experiments in vehicular networks for our study. The SP algorithm introduced in [5] is implemented on each vehicle. Specifically, in the $t$-th global iteration, each vehicle $k$ conducts a round of local iteration with its local samples to update the model. Meanwhile, it maintains two intermediate quantities: a vector variable $\mathbf{x}_{k}(t)$, and a scalar variable $y_{k}(t)$. In SP, $\mathbf{x}_{k}(t)$ represents model parameters contributed from client $k$. However, $\mathbf{x}_{k}(t)$ must be adjusted by the scalar $y_{k}(t)$ for model aggregation. Each vehicle evenly broadcasts two quantities $\mathbf{x}_{k^{\prime}}(t)/p_{k^{\prime},t}$ and $y_{k^{\prime}}(t)/p_{k^{\prime},t}$ to all neighbour vehicles $\forall k^{\prime}\in\mathcal{P}_{k,t}$, where $p_{k^{\prime},t}=|\mathcal{P}_{k^{\prime},t}|$, after conducting a local iteration. Then, $\mathbf{x}_{k}(t)$ and $y_{k}(t)$ are utilized to update model parameters. For detailed derivation of $\mathbf{x}_{k}(t)$ and $y_{k}(t)$, please refer to [5].

We leverage a microscopic traffic simulator SUMO [33] to generate grid topology and random topology as the road networks as well as vehicle trajectories. We generate 100 vehicles moving along roads in road networks based on the Manhattan mobility model [34]. Each vehicle can only communicate to other vehicles within the communication range of 100 meters. Two public datasets, CIFAR-10 with 50k/10k training/test images and MNIST with 60k/10k training/test images, are adopted to conduct our experiments. In each experiment, the training samples are distributed to 100 vehicles in a balanced and non-IID manner. In other words, each vehicle is assigned with 500 training images of CIFAR-10 or 600 training images of MNIST, selected from 2 to 4 out of 10 labels. Two CNN models are adopted for the image classification tasks. The CNN models for CIFAR-10 and MNIST have 33,834 and 21,840 parameters, respectively.³³3These models are from the public code repository at https://github.com/AshwinRJ/Federated-Learning-PyTorch We train the CNN models for 3,000 iterations on CIFAR-10 and 300 iterations on MNIST.

We collect the final model accuracy of each vehicle (evaluated on test datasets) in our experiments. Then, we plot the cumulative distribution functions (CDF) of the final model accuracy of individual vehicles in Fig. 2. From the CDF curves of the final model accuracy, we can observe that: 1) Along vehicles’ routes (randomly generated), a vehicle can only exchange model parameters with neighbour vehicles. As a result, there exist giant discrepancies of the final model accuracy on different vehicles. The accuracy can reach 70% on CIFAR-10 or 95% on MNIST for some lucky vehicles. In contrast, the model accuracy can be lower than 30% on CIFAR-10 or 85% on MNIST for some unlucky vehicles. 2) The network topology can severely affect the final model accuracy. The model accuracy obtained on the random topology is much worse than that on the grid topology because there exist vehicles with a low connectivity with other vehicles in random topology impeding the exchange of model parameters between vehicles.

This measurement result indicates that it is insufficient to merely consider the in-degrees and out-degrees of vehicles to determine weights, i.e., $\alpha_{k,t}$’s, for decentralized model aggregation in DFL. It calls for a more sophisticated aggregation method considering data source diversity to achieve consistent high model accuracy across all vehicles in the system.

To explore the underlying reason resulting in poorer model accuracy for unlucky vehicles, we further investigate the relationship between model accuracy and data source diversity. The challenge is how to measure the data source diversity since only model parameters are maintained as vehicles exchange and aggregate models with their neighbours. To tackle this problem, we propose to maintain state vectors on individual vehicles to track the contribution weight from each data source. The metric to measure the diversity of data sources is based on the state vector maintained by each vehicle.

Specifically, let $\mathbf{s}_{k,t}=\{s^{k}_{1,t},s^{k}_{2,t},\dots,s^{k}_{K,t}\}$ denote the state vector of vehicle $k$ in the $t$-th global epoch where $s^{k}_{k^{\prime},t}$ represents the contribution weight from vehicle $k^{\prime}$ to vehicle $k$’s model. For example, if there are $K=4$ vehicles in the system and the state vector of vehicle $1$ is $\mathbf{s}_{1,t}=\{0.25,0.25,0.25,0.25\}$. It implies that the model of vehicle $1$ is equally contributed from all vehicles. Otherwise, if $\mathbf{s}_{1,t}=\{0.50,0.01,0.01,0.48\}$, it means that the model on vehicle $1$ is mainly contributed from vehicle $1$ and $4$, which probably is not diversified enough.

Next, we describe how to update state vectors with the progress of DFL. Initially, all values in a state vector are assigned with $0$. State vectors are updated when vehicles conduct local iterations or model aggregations. For a particular vehicle $k$, we have

where $\eta_{t}$ is the learning rate. In other words, by conducting a round of local iteration, vehicle $k$ increases its own contribution weight. Similarly, Eq. 5 is executed for $E$ times given that local updates are conducted for $E$ rounds. Then, the state vector is normalized as

By conducting a round of model aggregation, the state vector is further revised as

which is subject to $\sum_{k^{\prime}\in\mathcal{P}_{k,t}}\alpha_{k^{\prime},t}^{k}=1$. Here $\mathcal{P}_{k,t}$ represents the set of vehicles involved in model aggregation conducted on vehicle $k$ in the $t$-th global iteration and $\alpha_{k^{\prime},t}^{k}$ represents the aggregation weight assigned for the model contributed from vehicle $k^{\prime}$.

Based on Eqs. (5) and (7), the functionality of state vectors can be interpreted as below. For conducting local iterations via Eq. (5), a state vector incorporates the contribution of the local dataset weighted by the learning rate for $E$ rounds. As a vehicle aggregates its local model with other models from neighbour vehicles, its state vector is also mixed with state vectors from neighbours according to aggregation weights in Eq. (7). In this way, a state vector can track the contribution weight from each data source.

We embark on introducing how to measure data diversity based on state vectors. We first consider a homogeneous case to ease our explanation in which every vehicle has the same number of samples. It is well-known that entropy is effective in measuring diversity. Given the state vector $\mathbf{s}_{k,t}$, we define the entropy of the state vector $\mathbf{s}_{k,t}$ as

Apparently, $H(\mathbf{s}_{k,t})$ achieves its maximum value $\log_{2}K$ if $s_{1,t}^{k}=\dots=s_{K,t}^{k}$ and minimum value $0$ if $s_{k^{\prime},t}^{k}=1$ for some $k^{\prime}$.

With the diversity measure, we can examine the importance to diversify data sources in DFL. We measure the Pearson correlation between vehicles’ model accuracy and the diversity metrics of their state vectors in the experiment presented in Fig. 3. The results are plotted in Fig. 3, in which the x-axis represents the index of global iteration while the y-axis represents the Pearson correlation coefficient after each global iteration. In Fig. 3, we can observe that there is a strong positive correlation between model accuracy and the diversity metric under both network topologies, indicating that unlucky vehicles with poorer model accuracy fail to diversify their data sources. This experiment also manifests the potential to improve model accuracy by diversifying data sources in DFL.

In view of the importance of data source diversity on the final model accuracy, we design the DFL-DDS algorithm that maximizes the data source diversity when aggregating models collected from neighbour vehicles.

The entropy value of a state vector is based on a homogeneous system. Yet, vehicles possibly own different sizes of datasets in practice. To tackle the heterogeneity of dataset sizes across vehicles and make our algorithm more flexible for aggregation, we propose to employ KL (Kullback–Leibler) divergence to measure data source diversity for state vectors in our algorithm.

According to [3], if the sample distribution is heterogeneous, it is common to assign the contribution weight of a vehicle proportional to its dataset size, i.e., $n_{k}$. To take heterogeneous distribution into account, we define the target state vector as $\mathbf{g}=\{\frac{n_{1}}{n},\frac{n_{2}}{n},\dots,\frac{n_{K}}{n}\}$ and $g_{k}=\frac{n_{k}}{n}$, where $n=\sum_{k=1}^{K}n_{k}$. The KL divergence of a state vector $\mathbf{s}_{k,t}$ is defined as its distance to the target state vector, which is

The KL divergence achieves its minimum value when $\mathbf{s}_{k,t}=\mathbf{g}$. Intuitively speaking, the KL divergence takes both the diversity and the importance of each vehicle into account.

Based on the defined KL divergence for each vehicle, we propose to generate weights $\alpha_{k^{\prime},t}^{k}$ when aggregating models by minimizing the local KL divergence between the current state and the target state in order to diversify the contribution of data sources and factor in the importance of each data source simultaneously. To facilitate the understanding of our algorithm, we exemplify the aggregation process in Fig. 4. In the example, it takes four steps for vehicle $k$ to update its state vector: 1) Exchange state vectors with neighbour vehicles along with the exchange of model parameters; 2) Generate weights $\alpha_{k^{\prime},t}^{k}$’s by minimizing the KL divergence of the state vector after aggregation; 3) Aggregate models based on aggregation weight $\alpha^{k}_{k^{\prime},t}$; 4) Update local state vector according to Eqs. (5) and (6) as local iterations are conducted. Similar to the example, the general update of state vectors can be embedded into the execution of local iterations. In particular, model parameters are aggregated according to the following rules in step 3).

Note that it is not reasonable to straightly set $\alpha_{k^{\prime},t}^{k}=g_{k^{\prime}}$ for a general road network without scrutinizing the state vector of $k^{\prime}$ because it overlooks the weights of data sources contributing to $\mathbf{w}_{t}^{k^{\prime}}$. To make it clearer, we reuse the example in Fig. 1 for illustration. In Fig. 1, there are two undirected communication paths: A-C-B and A-D. Assuming that the sample sizes in vehicles {A, B, C, D} are {100, 100, 10, 100}, respectively. Then, $\mathbf{g}=\{\frac{100}{310},\frac{100}{310},\frac{10}{310},\frac{100}{310}\}$. However, by only considering neighbour vehicles, vehicle A will straightly set the aggregation weight of C as $\frac{10}{210}$ because it can only contact vehicles C and D without taking vehicle B into account. This example illustrates the necessity for optimizing diversity via state vectors. The holistic overview of our DFL-DDS algorithm is sketched in Alg. 1.

To justify the feasibility of step 2) deducing $\alpha_{k,t}$ based on state vectors, we move on to prove that minimizing KL divergence can be solved efficiently by vehicles.

According to Eq. (7), the problem to minimize KL divergence is formulated as

It is known that the KL divergence as the objective of $\mathbb{P}1$ is a convex function. Meanwhile, all constraints in $\mathbb{P}1$ are linear functions. Hence, this is a convex optimization problem, which can be solved efficiently to optimally determine weights $\alpha_{k^{\prime},t}^{k}$’s for model aggregation.

It is worth noting that the problem $\mathbb{P}1$ minimizing the KL divergence of the local state vector is equivalent to maximizing the entropy value of the state vector when the sample distribution is balanced, i.e., $\mathbf{g}=\{\frac{1}{K},\dots,\frac{1}{K}\}$. For this special case, we have $D_{KL}(\mathbf{s}_{k,t}||\mathbf{g})=\sum_{k^{\prime}=1}^{K}{s_{k^{\prime},t}^{k}}\log_{2}{{s_{k^{\prime},t}^{k}}}-\log_{2}\frac{1}{K}=-H(\mathbf{s}_{k,t})+\log_{2}{K}.$

DFL-DDS is friendly for implementation in practice. Firstly, the computation and communication overhead incurred by DFL-DDS is negligible. Given $K$ vehicles in the system, exchanging state vectors only brings $O(K)$ communication overhead, which could be much less than the communication load for exchanging complicated CNN models between vehicles. The computation overhead lies in solving problem $\mathbb{P}1$, a small-scale convex optimization problem. It is still insignificant compared with the computation load to train CNN models. Secondly, the communication overhead can be further reduced if the system scale $K$ is large by maintaining dynamic state vectors on vehicles. In other words, each vehicle can adaptively adjust the size of its state vector $\mathbf{s}_{k,t}$ to only record weights from vehicles which have already contributed to its model training. Obtaining and distributing the target vector may consume extra communication traffic as well. Yet, the target state vector is static and limited with $O(K)$. It implies that a central coordinator can easily complete this task with low overhead.

Besides, our algorithm can be easily extended if RSUs are available for supporting DFL. An RSU can be regarded as a special static vehicle, which can also maintain a state vector to record the contribution weight of each vehicle. Thus, a vehicle can exchange information with an RSU to accelerate DFL as long as they are within effective communication distance.