Clock Synchronization Algorithms on a Software Defined CAN Controller: Implementation and Evaluation
Serkan Yalçın, M.S.
Thesis, Defense date: September 2019
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
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
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.
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.
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. .
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.
Ö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.
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.
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.
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.
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 di
fferent 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.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.
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.
Development of
strategies for reducing the worst-case message
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.
