Delay-Constrained Client Selection for Heterogeneous Federated Learning in Intelligent Transportation Systems

Abstract

Federated learning has been claimed as a solution in intelligent transportation systems, which allows for the implementation of distributed machine learning while ensuring privacy and data security. However, federated learning suffers from training inefficiency in practical deployment due to the heterogeneity of the participating clients. In this paper, we investigate how to optimize client selection to improve the training efficiency of traffic flow prediction, by considering the number of clients involved in training. We first formulate a constrained optimization problem on client selection, which aims to maximize the number of clients while meeting the training deadlines. We then transform the optimization problem into a two-dimensional unbounded knapsack problem (2UKP). Subsequently, we propose a K-means and Dynamic Programming (KDP) algorithm to solve the 2UKP. Specifically, we cluster the clients based on their computational capacity and geographic distance to the server by K-means and adopt dynamic programming to obtain the set of the selected clients. We evaluate the performance of the proposed KDP algorithm on Caltrans Performance Measurement System (PeMS) dataset and Highways England dataset. Comprehensive experimental results show that our proposed KDP algorithm can obtain up to 56% improvement in the number of clients within a given deadline compared to random and greedy strategies, achieving prediction accuracy of up to 20% improvement under the PeMS dataset and 15% improvement under the Highways England dataset. Moreover, the proposed KDP with 30% as the straggler ratio can still outperform the baseline FedGRU.