`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘
`
`Petitioner's Exhibit 1011
`EX" 1 O1 1
`Page 1 0f32
`
`Petitioner's Exhibit 1011
`Page 1 of 32
`
`

`

`Eandbeekei New/edged
`and Embedded;
`
`€enim1 Byaieme
`
`Dimitrios Hxistu—Varsakehs
`Wi11iam S. Levine
`
`Editors
`
`Editorial Board
`Raj eeV Alur
`Kan—Erik Arzén
`John B ai11ieu1
`
`Toni Henzinger
`
`Birkhauser
`Boston o Basel 8 Berlin
`
`
`
`Petitioner's Exhibit 1011
`
`Page 2 of 32
`
`Petitioner's Exhibit 1011
`Page 2 of 32
`
`

`

`Dimitrios Hristu—Varsakelis
`Department of Applied Informatics
`University of Macedonia
`Thessalomekl’ 54006
`Greece
`;
`
`-
`
`William S. Levine.
`.
`Department Of Electrical and
`Computer Engineering
`University of Maryland
`College Park, MD 20742
`USA
`
`
`
`Library of Congress Cataloging-in-Publication Data
`Handbook of networked and embedded control systems / Dimitrios Hristu~Varsakelis,
`William S. Levine, editors.
`p. cm. — (Control engineering)
`Includes bibliographical references and index.
`ISBN 0-8176-3239—5 (alk. paper)
`
`1. Embedded computer systems. I. Hristu-Varsalcelis, Dimitrios. :I. Levine, W. S. III.
`Control engineering (Birkh'auser)
`
`TK7895.E42H29 2005
`629.8’ 9—d022
`
`2005041046
`
`ISBN-10 0-8176—3239—5
`ISBN—13 978-0—8176—3239~7
`
`e~BSN 0—8176—4404—0
`
`Printed on acid-free paper.
`
`©2005 Birkhauser Boston
`
`All rights reserved. This Work may not be translated or copied in whole or in part without the writ—
`ten permission of the publisher (Birkhauser Boston, c/o Springer Science+Business Media Inc., 233
`Spring Street, New York, NY, 10013, USA), except for brief excerpts in connection with reviews
`or scholarly analysis. Use in connection with any form of information storage and retrieval, elec—
`tronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter
`developed is forbidden.
`The use in this publication of trade names, trademarks, service marks and similar terms, even if they
`are not identified as such, is not to be taken as an expression of opinion as to whether or not. they are
`subject to proprietary rights.
`
`'
`
`Printed in the United States of America.
`
`(ILS/MP)
`
`987654321
`
`SPlN10925324
`
`www. birkhauser. com
`
`Petitioner's Exhibit 101 l
`
`Page 3 of 32
`
`Petitioner's Exhibit 1011
`Page 3 of 32
`
`

`

`
`
`(Jornxanms
`
` i,
`
`i
`
`3
`
`ix
`Preface ........................................................
`
`Part I Filndarnentals
`
`7 Fundamentals of Dynamical Systems
`William S. Levine. .
`.
`.l ............................................
`Control of Single—Input Single—Output Systems
`Dimitrios HTista—Varsakelis, William S. Levine .
`.
`.
`.
`.
`Basics of Sampling and Quantization
`Mohammed S. Santina, Allen R. Stubberad .......................... 45
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`i 21
`
`Discrete—Event Systems
`Christos G. Cassandias ........................................... 71
`
`Introduction to Hybrid Systems.
`.
`Michael S. Branicky .............................................. 91
`
`‘ Finite Automate
`1%. V. Lawson .
`.’................................................. 117
`
`Basics of Computer Architecture
`ChaTles B. Silio, J7"............................................... 145
`
`Real—Time Scheduling for Embedded Systems
`‘
`Marco 'C’accamo, Theodore Baker, Alan Barns, Giorgio Batlazzo,
`LuiSWa..H: .............................................. f¢fl..173
`NetworkFundamentals -
`it
`David M. Aaslande'r, Jean—Dominique Decotignie ..................... 197
`
`Petitioner's Exhibit 101 1
`
`Page 4 of 32
`
`Petitioner's Exhibit 1011
`Page 4 of 32
`
`

`

`al
`lil
`
`
`
`vi
`
`Contents
`
`
`Part II 'HardWare
`
`‘ Basicsiibf Data Acquisition and Control
`M. Ohlddmbaram .....................................‘ ........... 227
`Programmable Logic. Controllers
`Gustaf Olsson ................................................... 259
`
`Digital Signal Processors
`Rainer Lenpers, Gerd Aschez’d ..................................... 279
`
`lVIicrocontrollers
`Steven F.'Barrett, Daniel J. Pack; .................................. 295
`
`SOPCs: Systems on Programmable Chips
`William M. Hawkins ............................................. 323
`
`
`Part III Software
`
`Fundamentals of RTOS—Based Digital Controller
`Implementation
`Qing Ll ......................................................... 353
`Implementation—Aware Embedded Control Systems
`Karl-Erik lime/n, Anton Cermn, Dan Henriksson. .
`.
`.
`.
`.
`.
`.
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`1
`
`.
`
`.
`
`. .377
`
`From Control Loops to Real—Time Programs
`Paul Caspi, Odecl Maler ........................................... 395
`Embedded Real—Time 'Control Via NIATLAB, Simulink, and
`XPC Target
`Pieter J. Moslerman, Sameer Prabhu, Andrew Dowd, John Glass, Tom
`Erkhz’nen, John Kluza, Rohz’t Shenoy ................................ 419
`LabVIEW Real—Time for Networked/Embedded Control
`John Limroth, Jeanne Sullivan Falcon, Dafna Leonard, Jenifer Loy .
`
`.
`
`.
`
`. 447
`
`Control Loops in RTLinuX
`Victor Yodalken, Matt ShererfEdgar Hilton ......................... 471
`
`
`Part IV Theory
`
`
`An Introduction to Hybrid Automata
`Jean~Fran§ols Raskz'n ............................................. 491
`
`Petitioner's Exhibit 101 1
`
`Page 5 of 32
`
`Petitioner's Exhibit 1011
`Page 5 of 32
`
`

`

`Contents
`
`Vii
`
`An Overview of Hybrid Systems Control
`John Lygems .................................................... 519
`Temporal Logic NIodel Checking
`Edmund Clarke, Ansgar Fehnker, Snmz't Kamar Jha, Helmut Venn ..... 539
`
`Switched Systems
`Daniel Liberzon .................................................. 559
`Feedback Control with Communication Constraints
`Dimitrios Hrista Varsakelis ....................................... 575
`Networked Control Systems: A lVIodel—Based Approach
`Luis A. ll/Iontest'r‘uque and Panos J. Antsaklis ....................... 601
`Control Issues in Systems with Loop Delays
`Leonid Miriam, Zalman J. Palmor .................................. 627
`
`
`Part V Networking
`
`Network Protocols for Networked Control Systems
`F.—L. Lian, J. R. Mayne, D. M. Tilbnry ............................ 651
`Control Using Feedback over Wireless Ethernet and Bluetooth
`A. Sari, J. Baillieul, D. V. Raghnnathan.‘......................... .. .677
`
`_ Bluetooth in Control
`B0 Bernhardsson, Johan Eker, Joakz'm Persson ...................... 699
`
`Embedded Sensor Networks
`John Heidemann, Ramesh Gom'ndan ............................... 721
`
`
`Part VI Applications
`
`Vehicle Applications of Controller Area Network
`Karl Henrik Johansson, Mmm T6'rngren, Lars Nielsen ............... 741
`
`Control of Autonomous Niobile Robots
`Magnus Egerstedt .
`.
`; ............................................. 767
`
`VVireless Control with Bluetooth
`Vladimeros Vladimerou, Gen“ Dnllemd .......................fl. ..... 779
`5"
`The Cornell RoboCup Robot Soccer Team: 1999-2003
`Rafiaello D’Andrea .............................................. 793
`Index .......................................................... 805
`
`Petitioner's Exhibit 101 1
`Page 6 of 32
`
`Petitioner's Exhibit 1011
`Page 6 of 32
`
`

`

`
`
`Preface.
`
`
`
`This handbook was motivated in part by our experience (and that of others) in
`performing research and in teaching about networked and embedded control
`systems (NECS) as well as in implementing such systems. Although NECS—
`along with the technologies that enable themfihave become ubiquitous, there ‘
`are few, if any, sources where a student, researcher, or developer can gain a
`‘ sufficiently broad view of the subject. Oftentimes, the needed information is
`scattered in articles, websites, and specification sheets. Such dificulties are
`perhaps to be expected, given the relative newness of the subject and the
`diversity of its constitutive disciplines. From control theory and communica—
`tions, to computer science and electronics, the variety of approaches, tools,
`and language used by experts in each field often acts as a barrier to under—
`standing how ideas fit within the broader context of networked and embedded
`control.
`'
`With the above in mind, we have gathered a collection of articles that
`provide at least an introduction to the important results, tools, software, and
`technologies that shape the area of NECS. Our goal was to present the most
`important knowledge about NECS in a book that would be useful to anyone
`who wants to learn about any aspect of the subject. We hope that we have
`succeeded and that every reader will find valuable information in the book.
`We thank the authors of each of the chapters. They are all busy people and
`we are extremely grateful to them for their outstanding work. We also thank
`Tom Grasso, Editor, Computational Sciences and Engineering at Birkhauser
`Boston, for all his [help indeveloping the handbook, and Regina Gorenshteyn,
`Assistant Editor,» for guiding the editorial and production aspects of the vol—
`ume. Lastly, we thank Torrey Adams whose copyediting greatly improved the
`book.
`We gratefully acknowledge the Support of our wives, Maria K. Hristu and
`Shirley Johannesen Levine, and our families.
`
`4,
`
`College Park, MD
`April 2095
`
`Dimitrios Hm'stu— Vb’rsakelz’s
`William S. Levine
`
`Petitioner's Exhibit 101 1
`
`Page 7 of 32
`
`Petitioner's Exhibit 1011
`Page 7 of 32
`
`

`

`
`
`u
`
`Vehicle Applications of '
`Controller Area Network
`
`Karl Henrik Johansson,1’* Martin Téj'rngren,2d and Lars Nielsen3
`1 Department of Signals, Sensors and Systems, Royal Institute of Technology,
`Stockholm, Sweden, kallej©s3.kth:se
`'
`
`2 Department of Machine Design, Royal Institute of Technology, Stockholm,
`Sweden, martin©damek.kth. se
`'
`3 Department of Electrical Engineering, Link‘oping University, Sweden,
`lars©isy.liu. se
`
`1 Introduction
`
`The Controller Area Network (CAN) is a serial buscommunicationsproto—
`col developed by Bosch in the early 19808. It defines a standard for efficient
`and reliable communication between sensor, actuator, controller, and other
`nodes in real—time applications. CAN is the de facto standard in a large vari—
`ety of networked embedded control systems. The early CAN development was
`mainly supported by the vehicle industry: CAN is found in a variety of passen—
`‘ger cars, trucks, boats, spacecraft, and other types of vehicles. The protocol is
`also widely used today in industrial automation and other areas of networked
`embedded control, with applications in diverse products such as production
`machinery, medical equipment, building automation, Weaving machines, and
`wheelchairs.
`.
`In the automotive industry, embedded control has grown from stand—alone
`systems to highly integrated and networked control systems [7,11]. By net—
`working electro—mecham'cal subsystems,
`it becomes possible to modularize
`functionalities and hardware, which facilitates reuse and adds capabilities.
`Fig. 1 shows an example of an electronic control unit (ECU) mounted on a
`diesel engine of a Scania truck. The ECU handles the control of engine, turbo,
`fan, etc. but also the CAN communication. Combining networks and mecha—
`tronic modules makes it possible to reduce both the cabling and the number
`5;.
`
`*The work of K. H. Johansson was partially supported by the European Com~
`mission through the ARTIST2 Network of Excellence on Embedded Systems Design,
`by the Swedish Research Council, and by the Swedish Foundation for Strategic Re—¢,
`search through an Individual Grant for the Advancement of Research Leaders.
`.
`lThe work of M. Torngren was partially supported by the European Commission"
`through ARTIST2 and by the Swedish Foundation for Strategic Research through
`the project SAVE.
`.
`,
`
`Petitioner's Exhibit 101 1
`
`Page 8 of 32
`
`Petitioner's Exhibit 1011
`Page 8 of 32
`
`

`

`742
`
`K. H. Johansson, M. T'cirng‘ren, and L. Nielsen
`
`ECU cunnectcrs
`
`Fig. 1. An ECU mounted directly on a diesel engine of a Scania truck. The arrows
`indicate the ECU connectors, which are interfaces to the CAN. (Courtesy of Scania
`
`A3.)
`
`
`
`
`
`of connectors, which faciitates production and increases re-iability. Introduc—
`
`ing networks in vehicles also makes it possible to more eficiently carry out
`diagnostics and to coordnate the operation of the separate subsystems.
`The CAN protocol standardizes the physical and data link layers, which
`are the two lowest layers of the open systems interconnection (OSI) communi—
`cation model (see Fig. 2). For most systems, higher—layer protocols are needed
`to enable efficient development and operation. Such protocols are needed for
`defining how the CAN protocol should be used in applications, for example,
`how to refer to the configuration of identifiers with respect to application mes—
`sages, how to package application messages into frames, and how to deal with
`start—up and fault handl'ng. Note that in many cases only a few of the OSI
`layers are required. Note also that real—time issues and redundancy manage—
`ment are not covered by the 081 model. The adoption of CAN in a variety
`of application fields has .ed to the development of several higher—layer proto—
`cols, including SAE J1939, CANopen, DeviceNet, and CANKingdom. Their
`characteristics reflect diferences in requirements and traditions of application
`areas. An example is the adoption of certain communication models, such as
`
`either the client—server model or the distributed data—30w model [13].
`'
`The progress and success of CAN are due to a number of factors. The
`evolution of microelectronics paved the way for introducing distributed con—
`trol in vehicles. In the early 1980s there was, however, a lack of low—cost and
`standardized protocols suitable for real—time control systems. Therefore, in
`1983 Kiencke started the development of a new serial bus system at Bosch,
`
`
`
`,‘
`
`Petitioner's Exhibit 101 1
`
`Page 9 of 32
`
`
`
`Petitioner's Exhibit 1011
`Page 9 of 32
`
`

`

`1l
`
`
`
`743
`
`Vehicle Applications of Controller Area Network
`
`Application
`Presentation
`Session
`
`Transport
`Network
`
`I Data link
`
`' CAN
`Physical
`
`
`
`
`
`
`
`Fig. 2. The CAN protocol defines the lowest two layers of the 081 model. There exist
`several CAN—based higher—layer protocols that are standardized The user choice
`depends on the application.
`
`
` 400 1 l I I l
`
`
`
`
`
`
`
`
`
`
`
`
` 300 r
`
`
`
`
`
`350_ Million CAN nodes sold per year
`
`250 ~
`
`. 200-
`
`150‘
`j 1
`
`100—
`
`
`
`50
`
` 2003
`
`2001
`
`
`
`2
`
`1999
`
`2000
`
`Fig. 3. The number of CAN nodes sold per year is currently about 400 million.
`(Data from the association, CAN in Automation [3].)
`
`which was presented as CAN in 1986 at the SAE congress in Detroit [8]. The
`CAN protocol was internationally standardized in 1993 as ISO 11898—1. The
`development of CAN was mainly motivated by the need for new functionality,
`but it also reduced the need for wiring. The use of CAN in the automotive
`industry has caused mass production of CAN controllers. Today, CAN C015“:
`trollers are integrated on many microcontrollers and available at a low cost".
`Fig. 3 shows the number of CAN nodes that were sold during 1999e2003.
`
`Petitioner's Exhibit 1011
`
`Page 10 of 32
`
`Petitioner's Exhibit 1011
`Page 10 of 32
`
`

`

`744
`
`K. H. Johansson,‘M. Torngren, and L. Nielsen
`
`
`
`Fig. 4. Three nodes connected through a CAN bus
`
`The purpose of this chapter is to give an introduction to CAN and some
`of its vehicle applications. The outline is as follows. Section 2 describes the
`CAN protocol, including its message formats and error handling. The section
`is concluded by a brief history of CAN. Examples of vehicle application ar—
`chitectures based on CAN are given in Section 3. A few specific control loops
`closed over CAN buses are discussed in Section 4. The paper is concluded
`with some perspectives in Section 5, where current research issues such as
`X-by—wire, and standardized software architectures are considered. The exam—
`ples are described in more detail in [14]. A detailed description of CAN is
`given in the; textbook [6]. Another good resource for further information is
`the homepage of the organization CAN—in—Automation (CiA) [3]. The use of
`CAN as a basis for distributed control systems is discussed in [13].
`
`2 Controller Area Network
`
`The Controller Area Network (CAN) is a serial communications protocol
`suited for networking sensors, actuators, and other nodes in real-time syS—
`terns. In this section, we first give a general description of CAN including its
`message formats, principle of bus arbitration, and error—handling mechanisms.
`Extensions of CAN, such as application—oriented higher—layer protocols and
`time—triggered CAN, are described, followed by a brief history of CAN.
`
`2.1 Description
`A CAN bus with three nodes is depicted in Fig. 4. The CAN Specification [4]
`defines the protocols for the physical and the data link layeIS, which enable
`the communication between the network nodes. The application process Of a
`node, e;g., a temperature sensor, decides when it should request the trans-
`mission of a message frame. The frame consists of a data field and overhead;
`
`
`such as identi"er and control fields. Since the application processes in gen:
`
`
`eral are asynchronous, the bus has a mechanism for resolving conflicts. F0r
`CAN, it is based on a non—destructive arbitration process. The CAN pro’GOCO1 7'
`therefore belongs to the class of protocols denoted as carrier senselmu‘ltiple
`access/collision avoidance (CSMA/CA), which means that the protocol hs‘UeDS
`
`Petitioner's Exhibit 1011
`
`Page 11 of 32
`
`Petitioner's Exhibit 1011
`Page 11 of 32
`
`

`

`Vehicle Applications of Controller Area Network
`
`,SOF
`
`identifier
`
`RTR
`
`Control
`
`Data
`
`CRC
`
`ACK
`
`
`
`745
`
`
`
`Fig. 5. CAN message name
`
`to the network in order to avoid collisions. CSNLA/CD protocols like Ether—
`net have instead a mechanism to deal with collisions once they are detected.
`CAN also includes various methods for error detection and error handling.
`The communication rate of a network based on CAN depends on the physical
`distances between the nodes. If the distance is less than‘40 m, the rate can be
`up to 1 Mbps.
`
`‘
`
`i
`
`
`
`
`
`
`
`
`
`
`
`
`
`Nlessage formats
`
`
`
`
`
`CAN distinguishes four message formats: data, remote, error, and overload
`ames. Here we limit the discussion to the data frame, shovni in Fig. 5. A data
`
`Lame begins with the start«of—fiame (SOP) bit. It is followed by an eleven—bit
`
`
`
`'denti°er and the remote transmission request (RTE) bit. The. identrier and
`
`
`the RTE bit form the arbitration field. The control field consists of six bits
`andindicates how many bytes of data follow in the data field. The data field
`can be zero toeight bytes. The cata :ield is followed by the cyclic redundancy
`
`
`checksum (CBC) field, which enables the receiver to check if the “eceived bit
`
`
`
`sequence was corrupted. The two—bit acknowledgment (ACK) "elc is used
`
`by the transmitter to receive an acknowledgment of a valid frame from any
`
`
`receiver. The end of a message " ame is signaled through a seven—bit end—of—
`
`arne EOF). There is also an extended data frame with a twenty—nine—bit
`
`
`
`
`
`
`'denti"er (instead of eleven bits).
`
`Arbitration
`
`
`
`
`
`
`
`
`
`
`Arbitration is the mecha ism that handles bus access con "icts. Whenever the
`
`CAN bus is free, any
`'t can start to transmit a message. Possible conflicts,
`
`due to more than one uni; starting to transmit simu‘aneously, are resolved by
`
`bit—wise arbitration using the identifier of each unit. During the arbitration
`phase, each transmitting unit transmits its identi"er and compares it. with
`the level monitored on the bus. If these levels are ecual, the unit continues to
`transmit. lithe unit detects a dominant level on the bus, while it was trying to
`transmit a recessive level, then it quits transmitting (and becomes a receiver).
`The arbitration phase is performed over the whole arbitration field. VVnen it
`is over, there is only one transmitter left on the bus.
`The arbitration is illustrated by the following example with three nodes
`‘ (see Fig. 6). Let the recessive level c0rrespond to “1” and the dominantwlevel
`
`
`
`to “0”, and suppose the three nodes have identi "ers Ii, 7; : 1, 2, 3, equal to
`
`
`
`‘
`
`Petitioner's Exhibit 1011
`
`Page 12 of 32
`
`Petitioner's Exhibit 1011
`Page 12 of 32
`
`

`

`746
`
`K. H. Johansson, M. Torngren, an
`identifier
`
`Bus
`
`Node 2
`
`Node 3
`
`
`
`
`
`d L. Nielsen
`
`ContrOI
`
`
`
`33-133
`
`
`
` Node; ‘
`
`Fig. 6. Example illustrating
`their SOF bi‘s simultaneous
`transmit one (recessive level), and 1
`these instances, Nodes 1 and
`the identifier has been transmitted, the bus belongs
`transmitting its control field, data field, etc. ’
`I3 : 11001011001.
`I1 : 11001101010,
`I2 : 11001011011,
`bitration process illus—
`If the nOdes start transmitting simultaneously, the at
`trated inthe figure takes place. First all three nodes send their 8013‘ bit. Then,
`they start transmitting their
`they are equal. The sixth bit of I1 is at th
`spending bits are at the dominant level of I2 and I3. Therefore, Node 1 stops
`transmitting immediately and continues only listening to the bus. This listen—
`ing phase is indicated in Fig. 6 with the grey field. Since the tenthbit of I2
`is at the recessive level while it is dominant for I3, Node 3 is the transmitter
`s after the arbitration phase and thus continues with
`that has access to the bu
`the transmission of the control and data fields, etc.
`ation addresses in CAN. Instead each
`There is no notion of message destin
`y node. needs to filter out
`node picks up all traffic on the bus. Hence, ever
`‘
`the interesting messages on the bus. The arbitratio
`_
`u
`.
`t, of
`an effective way to resolve bus conflicts. Note that a
`‘
`l information has to ,
`address data is transmitted and that no extra bus contro
`be’transmitted‘. A conseque
`he arbitration mechanism, however, is thatare
`nce of t
`units with low priority may exp
`ncy if high—priority units
`erience large late
`
`hIee no
`
`des st art transmitting
`on as they
`
`ntinue as long as
`
`.
`‘
`
`i
`
`very active.
`
`Error handling
`
`Error detection and error handling are important for the performance of CAN- ‘
`ntary error detection mechamsms the probability ofhaV ‘
`Because of compleme
`ing an undetected error is very s
`
`in five differell
`
`Petitioner's Exhibit 1011
`
`Page 13 of 32
`
`Petitioner's Exhibit 1011
`Page 13 of 32
`
`

`

`
`
`Vehicle Applications of Controller Area Network
`
`747
`
`ways in CAN: bit monitoring and bit stuffing, as well as frame check, ACK
`check, and CRC. Bit monitoring simply means that each transmitter monitors
`the bus level, and signals a bit error if the level does not agree with the trans—
`mitted signal. (Bit monitoring is not done during the arbitration phase.) After
`
`having :ransmitted five identical bits, a node will always transmit the oppo—
`
`site bit. This extra bit is neglected by the receiver. The procedure is called
`bit stuffing, and it can be used to detect errors. The frame check consists of
`
`
`
`checking that the xed bits of the frame have the values they are supposed
`
`to have, e.g., EOF consists of seven recessive bits. During the ACK in the
`message frame, all receivers are supposed to send a dominant level. If the
`transmitter, which transmits a recessive level, does not detect the dominant
`level, then an error is signaled by the ACK check mechanism. Finally, the
`CEO is that every receiver calculates a checksum based on the message and
`compares it with the CRC field of the message.
`.
`‘
`Every receiver node obviously tries to detect errors within each message. If
`an error is detected, it leads to an immediate and automatic retransmission of
`the incorrect message, In comparison to other network protocols, this mech—
`anism leads to a high data integrity and a short error recovery time. CAN
`thus provides elaborate procedures for error handling, including retransmis—
`sion and reinitialization. The procedures have to be studied carefully for each
`application to ensure that the automated error handling is in line with the
`system requirements.
`
`2.2 Protocol extensions
`
`' CAN provides the basic functionality described above. In many situations,
`it is desirable to use standardized protocols that define the communication
`layers on top of the CAN. Such higher—layer protocols are described below to—
`gether with CAN gateways and the time—triggered extension of'CAN denoted
`TTCAN, which allows periodic access to the communication bus with a high
`degree of certainty.
`
`Higher-layer protocols
`The CAN protocol defines the lowest two layers Of the 081 model in Fig. 2.
`In order to use CAN, protocols are needed to define the other layers: Field—
`bus protocols usually do not define the session and presentation layers, since
`they are not needed in these applications. The users may either decide to
`define their own software for handling the higher layers, or they may use a
`standardized protocol. Existing higher—layer protocols are often tuned to a
`certain application domain. Examples of such protocols include SAE J193§¥n
`CANopen, and DeviceNet. It is only SAE J1939 that is specially deveIOped’é'
`for vehicle applications. Recently, attempts have been made to interface CAN
`and Ethernet, which is the dominant technology for local area networks and
`widely applied for connecting to the Internet.
`
`Petitioner's Exhibit 101 1
`
`Page 14 of 32
`
`Petitioner's Exhibit 1011
`Page 14 of 32
`
`

`

`
`
`‘
`i’
`
`'
`
`748
`
`.
`
`K. H. Johansson, M. T'orngren, and L. Nielsen
`SAE 11939 is a protocol that defines the higher—layer communication con— i
`trol. It. was developed by the American Society of Automotive Engineers u
`(SAE) and is thus targeted to the automotive industry. The advantage of
`having a standard is considerable, since it enables independent development
`.
`of the individual networked components, which also allows vehicle manufac— ‘
`
`turers to use components from different suppliers. SAE J1939 specifies, e.g.,
`‘
`,
`how toread and write data, but also how-to calibrate certain subsystems.
`The data rate of SAE J1939 is about 250 kbps, which gives up to about 1850 1
`“
`messages per second [6] Applications of SAE J1939 include truck—and—trailer
`communication, vehicles in agriculture and forestry, as well as navigation sys— ‘
`tems'in marine applications.
`.
`CANopen is a standardized application defined on top of CAN and widely :
`used in Europe for the application of CAN in distributed industrial automaé
`tion. It is a standard of the organization CAN in Automation (CiA)
`[3].
`CANopen specifies communication profiles and device profiles, which enable 1
`an application—independent use of CAN. The communication profile defines
`the underlying communication mechanism. Device profiles exist for the most
`common devices in industrial automation, such as digital and analog I/O
`components, encoders, and controllers. The device can be configured through
`.
`CANopen independent of its manufacturer. CANopen distinguishes real—time
`data exchange and less critical data exchange. It provides standardized com—
`munication objects for real—time data, configuration data, network manage— ”
`ment data, and certain special functions (e.g., time stamp and synchronization
`messages).
`'
`DeviceNet is another standardized application defined on top of CAN for
`distributed industrial automation. It is mainly used in the USA. and Asia
`and was originally developed by Rockwell Automation. DeviceNet, Control-
`Netkand transmission control protocol/Internet protocol (TOP/1P) are open .
`network technologies that share upper layers of the communication protocol,
`‘
`but are based on lower layers: DeviceNet is built on CAN, ControlNet on a i
`token~passingbus protocol, and TCP/IP on Ethernet.
`‘
`CANKingdorn is a high—layer protocol used for motion control systems-
`It is also used in the maritime industry, as described in a boat example in 1
`Section 3. CANKingdom allows the changing of network behavior at any time,
`1
`including while the system is running. For example, CANKingdom allows the
`system troubleshooter to turn off individual nodes. The CAN node identifierS
`and the triggering conditions for sending messages can be changed while the ‘
`system is running. One instance when real—time network reconfiguration is ‘
`used is during failure conditions. An example is a loss of a radio link ECU }
`in a maritime application. The network monitor, also known as the Kira;
`in that casefirst shuts off the radio node to. keep it from sending any more
`commands, and then tells the appropriate nodes to get data from the King.
`This operation eliminates the problem of a node receiving two Simultafleéus ‘
`but conflicting commands. It also eliminates the problem of two nodes sendlng .
`the same CAN id.
`
`‘
`
`‘
`
`Petitioner's Exhibit 1011
`
`Page 15 of 32
`
`Petitioner's Exhibit 1011
`Page 15 of 32
`
`

`

`
`
`
`
`Vehicle Applications of Controller Area Network
`749
`
`The high—level protocols described above have been developed with difier—
`ent applications and traditions in mind, which is reflected, for example, in their
`support for real—time control. Although SAE J1939 is used for implementing
`control algorithms, it does not provide explicit support for time—constrained
`messaging. In contrast, such functionalities are provided by CANKingdom
`
`and CANopen, which handle explicit support for inter—node synchronization.
`
`
`CANKingdom and CANopen allow static and dynamic con"guration of the
`network, whereas SAE J1939 provides little flexibility.
`
`CAN gateways
`
`Gateways and bridges enable CAN—based networks to be linked’together or
`linked to networks with other protocols. A gateway between a CAN and
`another communication network maps the protocols of the individual net—
`works. There exist many different types of CAN gateways, e.g., CAN—RS232
`and CAN—TCP/lP gateways. The latter can provide remote access to a CAN
`through the Internet, which allows worldwide monitoring and maintenance.
`The networks connected through a gateway or a bridge are disconnected in
`terms of their real—time behavior, so obviously the, timing and performance
`of the complex inter—connected network can be hard to predict even if the
`individual networks are predictable.
`'
`Ethernet (or rather Ethernet/1P) is quite a different communication proto—
`col compared to CAN, but is still of growing importance in industrial automa~
`tion either in constellations with CAN or on its own. Traditionally, Ethernet
`is used in office automation and multimedia applications, while CAN domi—
`‘ nates in vehicles and in certain industrial automation systems. The strength
`of Ethernet is the ability to quickly move large amounts of data over long
`distances and that the number of nodes in the network can be large. CAN, on
`the other hand, is optimized for transmitting small messages over relatively
`short distances. A drawback with a network based on the Ethernet protocol
`is that the nodes need to be quite powerful and complex (and therefore more
`expensive) in order to handle the communication control. Another drawback
`with Ethernet is that during network traffic congestion the delay jitter can be
`severe and unpredictable], although at low network load Ethernet gives almost
`
`_ no delay.
`
`Time—triggered communication on CAN
`rTraditional CAN communication is event based: asynchronous events are trig—
`gered by node applications that initialize each transmission session. In many
`cases, this strategy is an efficient way to share the network resource. Therfé'
`are a variety of applications, however, that require a guaranteed access to the
`communication bus with a fixed periodic rate. This constraint is typical for
`sampled—data feedback control systems. In the automotive industry, x—by—wire
`
`
`
`Petitioner's Exhibit 101 1
`
`Page 16 of32
`
`Petitioner's Exhibit 1011
`Page 16 of 32
`
`

`

`Nielsen
`
`750
`K. H. Johansson, M. T'orngren, and L.
`systems are examples of such control systems with deterministic communica—
`tion behavior during regular operation.
`,
`- By introducing the notion of global network time, the standard ISO 11898—
`4 definefi the extension Time-triggered communication on CAN (TTCAN).
`triggered CAN protocol and en—
`It is built on top of the traditional event—
`ables existing CAN nodes to work in parallel with TTCAN nodes. The global
`clock requires hardware implementation; otherwise, TTCAN is a pure soft—
`ware extension of CAN. The synchronization in TTCAN takes place through
`CAN nodes recognize and use to
`a periodic reference message, which all TT
`synchronize their clocks. The nodes are configured to know when to send their
`message after the reference message. The period time of the transmission of a
`periodic node should be a multiple of the reference period. Traditional CAN
`nodes (or event—based TTCAN nodes) compete for the access of the free win—
`the line of the conventional CAN
`dows between the reference messages, along
`protocol. This mechanism is thus the reason why time—triggered and event—
`triggered scheduling is possible simultaneously in TTCAN.
`The sender of the reference message is obviously a crucral node in TTCAN
`to guarantee clock synchronization. Therefore, an automatic procedure is pro—
`vided for letting another node take over ifthe reference sender fails, an