TDCA: Improved Optimization Algorithm with Degree Distribution and Communication Traffic for the Deployment of Software Components Base on AUTOSAR Architecture

Kunpeng Zhang, Yanheng Liu, Jindong Zhang, Guanhua Zhang, Jingyi Jin, Yunhao Li, Fengmin TangResearch 2021 · DOI

Abstract

AUTOSAR (Automotive Open System Architecture) has become the global standard for automotive electronic software development, improving portability and development efficiency. However, the deployment of thousands of software components (SWCs) across Electronic Control Units (ECUs) presents a significant optimization challenge. This paper introduces the Traffic-Degree Clustering Algorithm (TDCA), which optimizes deployment by prioritizing components based on their communication "degrees" and data traffic. Experimental results show that TDCA significantly reduces bus load and improves ECU load balancing compared to traditional heuristic and linear optimization methods.

Introduction

Modern vehicles are increasingly defined by their software, running tens of thousands of components across dozens of ECUs. To manage this complexity, the industry relies on the layered AUTOSAR framework.

The layered AUTOSAR architecture, showing the separation between application software (ASW), the runtime environment (RTE), and basic software (BSW).

A critical bottleneck in this architecture is deployment: deciding which SWC resides on which ECU. Inefficient mapping leads to congested communication buses and unbalanced ECU utilization, which can compromise system reliability. This is an NP-hard optimization problem that previous approaches, such as the traffic-based CAT algorithm, often fail to solve optimally due to reliance on random initial placements.

Methodology

The proposed TDCA algorithm and its variant, TDSCA (Traffic-Degree-Subset-Cluster-Algorithm), introduce a structured approach to selecting "cluster centers" for deployment based on two primary metrics:

  1. Degree Distribution ($D_i$): Instead of random selection, TDCA calculates the "degree" of each SWC—the number of other components it communicates with. The algorithm selects the $k$ components with the highest degrees as initial anchors for the $k$ available ECUs.
  2. Communication Traffic ($ct$): Remaining SWCs are mapped to ECUs based on the volume of data exchanged. By keeping high-traffic pairs on the same ECU, the algorithm "internalizes" communication, keeping it off the shared vehicle bus.
Illustration of SWC degree distribution, where components are ranked by their number of communication links to serve as ECU anchors.

To ensure physical schedulability, TDCA utilizes a Dynamic Fitness Function based on Rate Monotonic (RM) scheduling theory, targeting a utilization threshold of 0.69. A penalty function dynamically balances the trade-off between reducing bus traffic and equalizing ECU processing loads.

Experimental Evaluation

The researchers evaluated TDCA using three distinct data models:

  • AIS Dataset: 904 atomic SWCs extracted from real-world AUTOSAR application examples.
  • PLP (Planted l-partition) Model: Synthetic connected graphs representing various software architectures.
  • RGE (Random Graph Exponential) Model: Synthetic models mimicking the exponential communication distribution found in actual automotive systems.

Key Results

Comparative testing against CAT, SPA (a heuristic algorithm), and Integer Linear Programming (ILP) variants demonstrated clear advantages for TDCA:

  • Bus Traffic Reduction: For the AIS dataset, TDCA maintained a bus traffic range of 700–1100, significantly lower than CAT (1200–1700) and ILP-based methods.
  • ECU Equalization: TDCA achieved the lowest standard deviation in ECU utilization, distributing the processing load more evenly than its competitors.
  • Stability and Speed: TDCA consistently delivered deployment plans faster than the more complex TDSCA and SPA algorithms, showing high stability as the number of SWCs and ECUs increased.

Conclusion

TDCA provides a robust solution for the deployment of software components in AUTOSAR architectures. By anchoring deployment on high-degree components, the algorithm effectively minimizes inter-ECU communication and balances hardware load. Future research will focus on incorporating strict end-to-end latency deadlines and addressing heterogeneous hardware environments in advanced vehicle architectures.

Summary updated

Abstract

Abstract AUTOSAR (Automotive Open System Architecture), as an open, standardized framework for automotive electronic software development, has gradually become the standard followed by major automotive manufacturers and automotive electronic device suppliers. The electronic software system problem improves the development efficiency and portability of the system by reducing the development cost of automotive electronic software while ensuring the quality of products and services, which is beneficial for subsequent upgrades and updates of the system. In order to improve the reliability of the software component deployment algorithm based on AUTOSAR architecture, we proposed the TDCA algorithm. During the execution of the algorithm, communication volume and communication degree are introduced to improve the accuracy of the deployment plan by optimizing the bus load and ECU balancing. Algorithm comparison experiments show that comparing heuristic and linear optimization algorithms, the TDCA algorithm proposed in this paper has significant advantages in reducing bus load and balancing ECU utilization. The algorithm can reduce the communication between cores and balance ECU load according to the constraints of AUTOSAR architecture.
BibTeX
@inproceedings{zhang2021tdca,
  author = {Kunpeng Zhang and Yanheng Liu and Jindong Zhang and Guanhua Zhang and Jingyi Jin and Yunhao Li and Fengmin Tang},
  title = {{TDCA: Improved Optimization Algorithm with Degree Distribution and Communication Traffic for the Deployment of Software Components Base on AUTOSAR Architecture}},
  booktitle = {Research},
  year = {2021},
  doi = {10.21203/rs.3.rs-1131775/v1},
}
Figure