Clock Synchronization Algorithms on a Software Defined CAN Controller: Implementation and Evaluation

Serkan Yalçın, M.S. Thesis, Defense date:  September 2019, Co-advised with Prof. Dr. Klaus Werner Schmidt 

Abstract:

Many advanced driver-assistance systems (ADAS) and in-vehicle applications require coordination for their safety-critical tasks. To achieve such a coordination, different electronic control units (ECUs) in the system should synchronize their clocks in order to share a global time. Although the controller area network (CAN) is the most widely used communication bus for the information exchange among ECUs, it does not support the required clock synchronization. Moreover, even several advanced clock synchronization methods for CAN have been suggested in the literature, they require modifications of the CAN driver, which is generally implemented in hardware and not accessible to modifications. The first aim of this thesis is the implementation of a software-defined CAN controller (SDCC) which enables modifications to the standard CAN driver. This SDCC is compatible to standard CAN controllers. The second aim of the thesis is the realization of new clock synchronization algorithms for CAN based on the SDCC including modifications to the classical CAN driver. The performance of the new algorithms is evaluated and compared to existing clock synchronization algorithms for CAN.
 


Train Communication Network, Multifunction Vehicle Bus, Scheduling, Integer Linear Programming, Heuristics

Mustafa Çağlar Güldiken, M.S. Thesis, Defense date:  September 2019, Co-advised with Prof. Dr. Klaus Werner Schmidt 

Abstract:

Train communication network comprises different standards such as the Wire Train Bus (WTB) for the data exchange among different vehicles and the Multifunction Vehicle Bus (MVB) for the data communication within vehicles. Specifically, MVB is a highly robust real-time field bus specifically designed for control systems built into rail-vehicles. MVB supports both periodic process data and sporadic message data transfers in the form of telegrams.

In order to achieve timely and efficient data exchange on MVB, the available bandwidth has to be used efficiently. Accordingly, the main focus of this thesis is the development of systematic scheduling approaches for periodic telegrams on MVB. In this respect, the thesis provides four main contributions. First, the thesis proposes an original integer linear programming (ILP) formulation for the schedule computation on MVB. Second, the thesis develops 5 basic heuristic algorithms for the fast computation of feasible MVB schedules. Third, the thesis introduces several swap operations for improving the schedules obtained from the basic heuristics. Finally, the thesis presents a comprehensive evaluation of the developed scheduling methods. This evaluation shows that, different from the proposed heuristics, the ILP formulation cannot provide solution schedules for large telegram sets with reasonable run-times. Specifically, two of the proposed heuristics and two of the developed swap operations are found most suitable as a practical solution to the MVB scheduling problem.


 C³: Configurable CAN FD Controller: Design, Implementation and EvaluationMehmet Ertuğ Afşin, M.S. Thesis, Defense date:  February 2018, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

Abstract:

CAN FD (Controller Area Network with Flexible Data Rate) is a new communication standard, compatible with CAN. Different from CAN, CAN FD switches to high data rate during data transmission and allows payloads up to 64 bytes. In this thesis, we propose C3: Configurable CAN FD Controller which features up to fully configurable 96 TX and 96 RX buffers organized as mailboxes. Each RX buffer has dedicated acceptance filters. The host MCU sees C3 as a memory mapped device and interfaces with it via SPI protocol which is designed and developed in the scope of this thesis. Different from existing CAN FD Controllers, C3 provides run time configurable number of buffers and individual buffer sizes which makes it best use of a single hardware for every application. Furthermore, it provides efficient and flexible usage of a limited embedded memory. C3 is implemented on a Xilinx Virtex 5 FPGA demo board as an IP Core and its functions are verified at 2Mbps and the response time measurements are performed to evaluate the timing performance.
 

Thesis overview  Demo video

 


Controller Area Network with Offset Scheduling: Improved Offset Assignment Algorithms And Computation Of Response Time Distributions

Ahmet Batur, M.S. Thesis, Defense date: February 2018, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

 

Abstract:

The Controller Area Network (CAN) is the most widely-used in-vehicle communication bus in the automotive industry. CAN enables the exchange of data among different electronic control units (ECUs) of a vehicle via messages. The basic requirement for the design of CAN is to guarantee that the worst-case response time (WCRT) of each message is smaller than its specified deadline. Hereby, it is generally desired to achieve small WCRTs that leave sufficient slack to the message deadline. In addition, it has to be noted that it might be very unlikely that a message experiences the WCRT when being transmitted on CAN. That is, instead of only considering the message WCRT for the design of CAN, it is beneficial to determine the actual response-time distribution of each message, which indicates the probability of experiencing a certain response time. In order to achieve small WCRTs, the idea of offset scheduling has been introduced. In this setting, messages on CAN are released with offsets in order to avoid message bursts that lead to undesirably large response times. In order to use offset scheduling efficiently, it is required to assign a suitable offset to each message. To this end, a load distribution (LD) algorithm is proposed in the existing literature. The first contribution of this thesis is the development of new algorithms for the offset assignment on CAN. Evaluating different example scenarios, the thesis shows that the proposed algorithms outperform the existing LD algorithm in most of the cases. As the second contribution, the thesis studies the computation of response time distributions. First, an algorithm for determining the exact response-time distribution of each message on CAN is proposed. Since this algorithm comes with a high computational complexity, it cannot be applied if there are too many messages on a CAN bus. Moreover, experimental results show that the response time distribution depends mostly on the initial phasing of the nodes. Therefore exact response time distribution as computed is not observed in the measurements. In response to this observation, the thesis proposes the computation of a local response time distribution and develops and implements a weak synchronization method which bounds the phase shift between the nodes. The resulting computed local response time distribution shows a very tight match with measured response time distributions.
 

Thesis overview  

 


An End-To-End Communication Architecture for Intelligent Transportation Systems: Design, Implementation and Latency Analysis

Çağatay Bağcı, M.S. Thesis, Defense date:  February 2018

 

Abstract:

Vehicle to anything (V2X) communication is a very significant component of Intelligent Transport Systems (ITS) applications. This thesis proposes an application layer communication architecture, ITSVeCon for V2X communications which enables communication among the end-hosts which can be vehicle Electronic Control Units (ECU)’s, Road Side Units (RSU)s, computers, smart phones or third party service providers. All these end-hosts are bi-directionally connected to the ITSVeCon Server where this server carries out application layer switching realizing unicast or multicast communication. The architecture consists of a layered software and network protocol stack with message formats and rules, which are implemented in the end-hosts and the ITSVeCon server. To this end, this thesis presents the ITSVeCon realization on the vehicle On Board Unit (OBU) and the ITSVeCon server. The OBU realization further fulfills the gateway functionality between the in-vehicle CAN network and the Internet. The ITSVeCon implementation features WebSockets carrying messages in JSON format, Publish and Subscribe pattern and NTP synchronization to enable V2X communications for real time ITS applications. To this end, the proposed architecture allows the seamless running on different ITS applications on different types of host devices. This thesis proposes the cellular communications as the wireless communication technology for the vehicle. To this end, the end-to-end communication path in ITSVeCon consists of cellular access and IP core network over multiple nodes and network segments. A very important contribution of the thesis is the measurement set-up, detailed experiment scenarios and measurement results of the end-to-end delay components. The measured end to end delay values are close to 100 ms with embedded component delays under 4 ms and large cellular network access delay under 3G network. Hence, a complementary short range wireless interface is proposed in this thesis as the second option to improve communication and functional tests of this option is carried out. With the improvements in technology, around 10 ms end to end delay value can be achieved with 4G and 1 ms end to end delay value is expected to be accomplished with 5G. .
 

Thesis overview  Demo video

 


Efficient algorithms for the frame packing and slot allocation of FlexRay v3.0

Cumhur Çakmak, M.S. Thesis, Defense date: February 2017, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

Abstract:

Contemporary vehicles employ a large number of Electronic Control Units (ECUs), sensors and actuators that exchange signals over an in-vehicle network (IVN). These signals are packed in frames which are transmitted according to a precomputed schedule to satisfy the stringent real time requirements of the vehicle operation. Both the signal packing and scheduling algorithms affect the utilization and timing properties of the IVN and hence the entire vehicle electronic system. Despite the offline computation, the run-time of these algorithms might become prohibitively long as the number of signals increases.

This thesis proposes signal packing and scheduling algorithms for the Static Segment of the FlexRay IVN standard which is dedicated to the transmission of periodic signals. The proposed algorithms achieve high bandwidth utilization, fulfill the timing requirements and run in feasible times. To this end, the first contribution of the thesis is an Integer Linear Program (ILP) formulation to pack signals into FlexRay frames based on their period properties. The second contribution is a post-processing algorithm to improve the bandwidth utilization. The third contribution is adapting an existing scheduling algorithm to the new version FlexRay v3.0 to achieve feasible schedules under the developed packing methods. The proposed algorithms are applied to signal sets with different properties to demonstrate their advantages compared to previous work in the literature.

 Thesis overview


Message Scheduling For The Static and Dynamic Segment of Flexray: Algorithms and Applications 

Özgur Kızılay, M.S. Thesis, Defense date: December 2015, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

Abstract:

Today's automobiles comprise an increasing number of electronic components. Some of these components are used for entertainment purposes and some of them are used for safety-critical application such as X-by-Wire that are implemented on electronic control units (ECUs). The safe data exchange among such ECUs has to be realized by a robust and reliable in-vehicle network protocol. In this context, FlexRay is one of the new generation in-vehicle network protocols which is already used in upper class series vehicles.

In principle, FlexRay enables the reliable transmission of periodic and sporadic messages that are generated by ECUs on two communication channels. Nonetheless, it is the user's responsibility to configure the FlexRay parameters. In particular, it is required to determine a message schedule such that each message meets its deadline.

In general, two types of messages -- periodic and sporadic messages -- are considered. In FlexRay, periodic messages are transmitted in the static segment and sporadic messages are transmitted in the dynamic segment. Since these two types of messages have different timing characteristics and the corresponding segments in FlexRay have different arbitration properties, their scheduling has to be performed by different types of algorithms.

In this thesis, we focus on the message scheduling on the static segment and the dynamic segment of FlexRay. We first analyze practical requirements for the static segment scheduling based on previous studies that involve the solution of a linear integer problem (LIP). In order to circumvent the requirement for an LIP solver, a new heuristic static segment scheduling algorithm is developed and implemented. Its performance is evaluated by several test cases. Next, we consider the FlexRay dynamic segment. We first propose an improvement of an existing algorithm for the worst-case response time analysis and then develop a new algorithm for the priority assignment on the FlexRay dynamic segment. The practicability of the presented algorithms is established by various examples.

Thesis overview


Controller Area Network (CAN) Response Time Analysis and Scheduling For Advanced Topics: Offsets, FIFO Queues and Gateways

Burak Alkan, M.S. Thesis, Defense date: February 2015, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

Abstract:

Controller Area Network (CAN) is the most widely used in-vehicle network for the communication among electronic control units (ECUs). CAN has a priority-based arbitration mechanism and the classical usage of CAN assumes the implementation of priority queues (PQs) on ECUs. Based on this assumption, the literature provides efficient algorithms for the computation of worst-case response times (WCRTs) of messages as well as for the appropriate assignment of priorities to messages in order to meet real-time guarantees such as message deadlines.

In contemporary CAN networks there are several extensions to the classical case. First, the addition of new functionality to vehicles requires adding new messages with appropriate priorities to existing CAN networks. Second, FIFO queues (FQs) might be used instead of PQs for easier implementation. Third, due to the ever-increasing bus load, CAN networks are usually divided into several segments that are connected via gateways to decrease the contention among messages. Fourth, a further measure is to distribute the message transmission of each ECU over time by assigning transmission offsets to messages. All of the stated extensions require new methods for WCRT analysis and priority assignment on CAN.

This thesis has a list of contributions that address the extensions for CAN as listed above. Regarding offset scheduling; different schedulability analysis methods for message sets with given offset and priority assignments are incorporated to a previous offset assignment algorithm. Then, a new algorithm which simultaneously assigns the message offsets and priorities is proposed. Regarding ECUs with FIFO queues; the previous schedulability analysis is improved to decrease its run time and then this analysis is used in an algorithm that assigns the priorities to the new messages that extend an existing CAN network. Regarding gateways; an algorithmic priority assignment is proposed for ECUs with priority queues and the schedulability analysis for CAN networks with gateways is extended to FIFO queues.

All of the algorithms that are used and developed in this thesis are implemented in C++ to integrate into a novel in-vehicle network analysis and design tool; AUTONET.

Thesis overview


A Frame Packing Method to Improve the Schedulability on CAN and CAN-FD

Gökhan Urul, M.S. Thesis, Defense date: February 2015, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

Abstract:

Controller Area Network(CAN) is the most widely used network in vehicles. Today systems can fill a CAN network's communication bandwidth to its limit. There two main constraints while constructing set of frames to use vehicle network more efficient; minimizing bandwidth consumption and keeping network schedulable which conclude a NP-hard problem on frame packing. The aim of this study is to explore the existing literature on frame packing problem and to solve the problem of generating a schedulable frame set which minimizes the bandwidth utilization on CAN and CAN-FD network. As a part of the solution, we propose an heuristic that solves the optimization problem for signals in CAN and also CAN-FD. The results of our systematically conducted experiments show that, our heuristic provides more effective results than existing techniques.

Thesis overview


A Generic and Extendable System Architecture for Intelligent Transportation Systems

Kaan Çetinkaya, M.S. Thesis, Defense date: January 2015

Abstract:

Intelligent Transportation Systems (ITS) are distributed systems with different communicating parties which are vehicles with ITS-supporting On Board Units (OBUs), Road Side Units (RSU) and user mobile devices. These parties collectively run application services that are developed and managed by different application service providers by communicating among each other under certain timing constraints. In the current state of art, hardware, software and communications that are required to implement a given ITS application are all specifically re-designed for each application service. This thesis presents a system architecture named as Car Content Delivery (CarCoDe) for ITS application development complete with a software stack and communication specifications. CarCoDe is generic and can be used by all ITS parties by defining the relevant specific features. It provides a simple software stack and supports both short range and long range communications over a third node. Furthermore, CarCoDe has been attached with great importance to flexibility and modularity features which make it extendable for future contributions. The features of CarCode are demonstrated by a realization of it for a vehicle OBU and implementing an icy road warning application.

Thesis overview  ITEA Presentation


 

An FPGA implementation of two-step trajectory planning for automatic parking

 

Halil Ertuğrul, M.S. Thesis, Defense date: September 2013, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

 

Abstract:

The main distinguishing feature of different automatic parking technologies is the method that determines a proper collision-free path. Hereby, the length of the path, the number of halts and the computation time for finding such path are the most relevant performance criteria. In this thesis, a two-step trajectory planning algorithm for automatic parking is considered. The algorithm finds a path that meets all kinematic constraints of the car from its initial position, to the target position while requiring a small number of vehicle halts. It first calculates a collision-free path from the initial position to the target position by maximizing the distance from any obstacle. Since this path usually does not respect the kinematic constraints of the vehicle, a second algorithmic step computes a path that is suitable for the vehicle. In both steps, a set of 48 optimal trajectories is used for the path computations and distance evaluations. Since the trajectory planning algorithm requires complex geometric calculations, it a microprocessor is not suitable for practicable computation times. Hence, an FPGA is chosen for the realization of the trajectory planning algorithm on hardware, enabling parallel processing of the trajectory computations. This thesis describes the hardware design for implementing the trajectory planning algorithm on FPGA. The performed analysis both via simulations and implementation on hardware shows that a speedup in the trajectory computation is obtained. Different from other hardware realizations that are restricted to either only parallel parking or vertical parking, our implementation can handle general parking situations. In addition, our implementation increases the driver comfort by reducing the number of vehicle halts.

Thesis overview Demo video


 Software tool development for the automated configuration of FlexRay networks for in-vehicle communication

Can Öztürk, M.S. Thesis, Defense date: January 2013, Co-advised with Associate Prof. Dr. Klaus Werner Schmidt 

 

Abstract:

The increasing use of electronic components in today’s automobiles demands more powerful in-vehicle network communication protocols. FlexRay protocol, which is expected to be the de-facto standard in the near future, is a deterministic, fault tolerant and fast protocol designed for in vehicle communication. The current de-facto in-vehicle communication standard, CAN, and the future in-vehicle communication standard FlexRay will exist together in future cars. Data exchange between these two standards will be performed via Gateway units. The configuration of such interconnected networks require setting a very large number of parameters in a consistent manner. In this thesis a software configuration tool with user interface support for such in-vehicle networks will be developed.

Thesis overview


A software tool for vehicle calibration, diagnosis and test via controller area network

Utku Civelek, M.S. Thesis, Defense date: September 2012

 

Abstract:

 

Controller Area Networks (CAN’s) in vehicles need highly sophisticated software tools to be designed and tested in development and production phases. These tools consume a lot of computer resources and usually have complex user interfaces. Therefore, they are not feasible for vehicle service stations where low-performance computers are used and the workers not very familiar with software are employed. In this thesis, we develop a measurement, calibration, test and diagnosis program -diaCAN- that is suitable for service stations. diaCAN can transmit and receive messages over 3 CAN bus channels. It can display and plot the data received from the bus, import network message and Electronic Control Unit (ECU) configurations, and record bus traffic with standard file formats. Moreover, diaCAN can calibrate ECU values, acquire fault records and test vehicle components with CAN Calibration Protocol functions. All of these capabilities are verified and evaluated on a test bed with real CAN bus and ECUs.

Thesis overview


 

Development of strategies for reducing the worst-case message response times on the controller area network

 

Vakkas Çelik, M.S. Thesis, Defense date: January 2012, Co-advised with Assistant Prof. Dr. Klaus Werner Schmidt 

Abstract:

The controller area network (CAN) is the de-facto standard for in-vehicle communication. The growth of time-critical applications in modern cars leads to a considerable increase in the message traffic on CAN. Hence, it is essential to determine efficient message schedules on CAN that guarantee that all communicated messages meet their timing constraints. The aim of this thesis is to develop offset scheduling strategies that find feasible schedules for higher bus load levels compared to conventional CAN scheduling approaches. We formulate the offset scheduling as a constraint optimization problem that maximizes the sum of message slacks where slack is defined as the difference between the deadline and the worst-case response time (WCRT) of a message. The constraint to ensure the feasibility of the schedules is keeping all slacks positive. In this respect we propose two heuristic offset scheduling algorithms which integrate an existing method for the WCRT analysis in the schedule computation. We apply our algorithms to various examples and compare the results with a well-known offset scheduling algorithm. The results show that our algorithms can generate feasible schedules at significantly high loads with run times shorter than 5 minutes.


Inter-connected FlexRay and CAN networks for in-vehicle communication: Gateway implementation and end-to-end performance study

Melih Alkan, M.S. Thesis, Defense date: May 2010

Abstract:

The increasing use of electronic components in today’s automobiles demands more powerful in-vehicle network communication protocols. FlexRay protocol, which is expected to be the de-facto standard in the near future, is a deterministic, fault tolerant and fast protocol designed for in vehicle communication. The current de-facto in-vehicle communication standard, CAN, and the future in-vehicle communication standard FlexRay will exist together in future cars. Data exchange between these two standards will be performed via Gateway units. In this thesis, end-to-end performance of a FlexRay-CAN network connected by a Gateway is evaluated as well as Gateway functionality and processing delay. The results of the experiments, which are performed for a realistic message set with various scheduling schemes, are presented and discussed.


Performance evaluation of FlexRay networks for in-vehicle communication

Ali Demirci, M.S. Thesis, Defense date: November 2009

Abstract:

The increasing use of electronic components in today’s automobiles demands more powerful in-vehicle network communication protocols. FlexRay protocol, which is expected be the de-facto standard in the near future, is a deterministic, fault tolerant and fast protocol designed for in vehicle communication. In the near future, safety critical X-by-Wire applications will be available in the automobiles and FlexRay networks can be used to provide communication for the Electronic Control Units (ECUs) that perform related functions of X-by-Wire applications. In this thesis the performance of the FlexRay networks with various communication scenarios is evaluated in a real time environment and the results are presented. Communication scenarios investigate both static and dynamic segment of the FlexRay and allow evaluating the capabilities of the protocol. Several performance metrics such as utilization, static slot allocation, jitter are defined for the evaluation of the results.


Time-triggered controller area network (TTCAN) communication scheduling: a systematic approach

Ugur Keskin, M.S. Thesis, Defense date: August 2008

Abstract:

Time-Triggered Controller Area Network (TTCAN) is a hybrid communication paradigm with combining both time-triggered and event-triggered traffic scheduling. Different from the standard Controller Area Network (CAN), communication in TTCAN is performed according to a pre-computed, fixed (during system run) schedule that is called as TTCAN System Matrix. Thus, communication performance of TTCAN network is directly related to structure of the system matrix, which makes the design of system matrix a crucial process. The study in this thesis consists of the extended work on the development of a systematic approach for system matrix construction. Methods for periodic message scheduling and an approach for aperiodic message scheduling are proposed with the aim of constructing a feasible system matrix, combining three important aspects: message properties, protocol constraints and system performance requirements in terms of designated performance metrics. Also, system matrix design, analyses and performance evaluation are performed on example message sets with the help of two developed software tools.