Dynamic QoS Prediction Algorithm Based on Kalman Filter Modification

Yunfei Yan, Peng Sun, Jieyong Zhang, Yutang Ma, Liang Zhao, Yueyi QinSensors 2022 · DOI

TL;DR

This paper introduces MFDK, a novel dynamic QoS prediction model that tackles the challenge of sparse historical QoS data. By combining non-negative Tucker decomposition for data imputation, a CNN-BiLSTM deep learning model for prediction, and a Kalman filter for real-time correction, MFDK significantly improves prediction accuracy in dynamic service environments.

What Problem Does This Paper Address?

In the world of Service-Oriented Architectures (SOA), a vast number of services offer similar functionalities but vary greatly in their Quality of Service (QoS). For users, selecting the best service can be a daunting task, as evaluating the QoS of every available option is often prohibitively expensive and time-consuming. This is further complicated by the dynamic nature of QoS, which can fluctuate due to network conditions and service load. Existing QoS prediction methods often struggle with sparse historical data and fail to effectively incorporate real-time observations. This paper aims to bridge this gap by developing a robust dynamic QoS prediction algorithm that can handle sparse data and leverage real-time feedback for improved accuracy.

Methods

The proposed MFDK model is a three-stage approach:

  1. Missing Data Filling (Non-Negative Tucker Decomposition): To address the sparsity of historical QoS data, the paper employs a non-negative Tucker decomposition. This method decomposes the user-service-time tensor into core and factor matrices, effectively filling in missing values while ensuring that the imputed values remain non-negative, which is crucial for QoS metrics.
  2. Deep Learning Model Training (CNN-BiLSTM): The imputed historical QoS data is then used to train a deep learning model. The authors utilize a combination of Convolutional Neural Networks (CNNs) for extracting local temporal features and Bidirectional Long Short-Term Memory (BiLSTM) networks for capturing global temporal dependencies in the time series data. This hybrid approach aims to learn complex patterns in QoS evolution.
  3. Kalman Filter-Based Correction: To further enhance prediction accuracy, the model incorporates a Kalman filter. This filter takes the predictions from the CNN-BiLSTM model and fuses them with real-time QoS observations. The Kalman filter dynamically adjusts the predictions based on the confidence it has in the model's output versus the observed data, effectively correcting for real-time fluctuations and improving the final prediction. An optimization strategy is also proposed to handle sparse real-time observations.

Datasets

The experiments were conducted using the WS-DREAM dataset. This dataset is a widely used benchmark in QoS prediction research and contains response time data for 142 users interacting with 4500 web services over 64 time slices. The authors processed this data by constructing a user-service-time tensor and then expanding it into time series vectors.

Key Insights and Ideas

  • The Power of Imputation: The paper highlights that effectively filling in sparse historical QoS data is a critical first step for accurate dynamic prediction. Non-negative Tucker decomposition proves to be a suitable method for this task, ensuring realistic data imputation.
  • CNN-BiLSTM Synergy: Combining CNNs for local feature extraction with BiLSTMs for global temporal modeling provides a powerful framework for capturing the complex dynamics of QoS over time.
  • Real-time Correction is Key: Integrating real-time QoS observations through a Kalman filter significantly boosts prediction accuracy by allowing the model to adapt to immediate changes in service performance.
  • Robustness to Sparsity: The MFDK model demonstrates good performance even when real-time observations are sparse, indicating its practical applicability in real-world scenarios.

Key Results

The MFDK model demonstrated superior performance compared to several baseline methods, including ARIMA, TCN, WSPred, CLUS, and PMF, across various tensor densities. Specifically:

  • Improved Accuracy: MFDK achieved significantly lower RMSE and MAE values compared to baseline models, especially in sparse data scenarios. For instance, at a tensor density of 0.1, MFDK's RMSE was considerably lower than other methods.
  • Ablation Study Success: Model ablation experiments showed that both the non-negative matrix decomposition and the Kalman filter correction components contribute substantially to MFDK's overall performance, with the combined approach yielding the best results.
  • Observation Sparsity Impact: The experiments on observation sparsity indicated that MFDK's prediction accuracy generally improves with increased observation density, and the model remains effective even with sparse observations.

Limitations and Future Work

The authors acknowledge that while their model shows promising results, there are avenues for further improvement:

  • Enhanced Data Filling: Future work could focus on improving the sparse QoS data filling capability by incorporating additional information, such as user geographic location and user-service similarity relationships, to make the historical data filling more accurate.
  • Deep Learning Network Enhancement: Further research could explore enhancing the deep learning network to better capture time series features, potentially leading to even more accurate predictions.

Summary updated

Abstract

With the widespread adoption of service-oriented architectures (SOA), services with the same functionality but the different Quality of Service (QoS) are proliferating, which is challenging the ability of users to build high-quality services. It is often costly for users to evaluate the QoS of all feasible services; therefore, it is necessary to investigate QoS prediction algorithms to help users find services that meet their needs. In this paper, we propose a QoS prediction algorithm called the MFDK model, which is able to fill in historical sparse QoS values by a non-negative matrix decomposition algorithm and predict future QoS values by a deep neural network. In addition, this model uses a Kalman filter algorithm to correct the model prediction values with real-time QoS observations to reduce its prediction error. Through extensive simulation experiments on the WS-DREAM dataset, we analytically validate that the MFDK model has better prediction accuracy compared to the baseline model, and it can maintain good prediction results under different tensor densities and observation densities. We further demonstrate the rationality of our proposed model and its prediction performance through model ablation experiments and parameter tuning experiments.
BibTeX
@inproceedings{yan2022dynamic,
  author = {Yunfei Yan and Peng Sun and Jieyong Zhang and Yutang Ma and Liang Zhao and Yueyi Qin},
  title = {{Dynamic QoS Prediction Algorithm Based on Kalman Filter Modification}},
  booktitle = {Sensors},
  year = {2022},
  doi = {10.3390/s22155651},
}
Figure