Real-Time Networks for Robotics and Industrial applications: Research Challenges and Novel Solutions

(1)

Elettri a, Elettroni a e

Informati a

PhD in Systems, Energy, Computer and

Tele ommuni ation Engineering

XXIX Cy le

Real-Time Networks for Roboti s and

Industrial appli ations: Resear h

Challenges and Novel Solutions

Ing. Gaetano Patti

Coordinator

Prof. Paolo Arena

Tutor

(2)

(3)

The in reasing adoption of smart sensors and a tuators enables

in-dustrial appli ations to pro ess data in a de entralized way. In this

ontext, ommuni ation networks play a key role, as industrial

au-tomation appli ations require network ar hite tures and

ommuni- ation proto ols, wireless and wired, able to support the intera tion

between multiple devi es not only in a reliable way, but also

guar-anteeing the meeting of real-time onstrains of the supported

appli- ations. The distributed pro essing among oordinated automation

devi es in ludes the ooperation of robot teams. However,

oopera-tive robotnetworks imposeadditional ommuni ation onstraintsto

those requiredin the automation ontext.

This thesis originates from the ollaboration with

STMi roele -troni sand targets me hanisms,algorithmsand proto ols that meet

the ommuni ationrequirementsof ooperativerobotappli ationsin

the industrial automation s enario. With the aim to avoid the

de-nition of yet another proto ol, the work mainly fo uses on the

ex-isting ommuni ationte hnologiesadopted intheindustrial ontext.

In parti ular, innovative me hanisms, algorithm and proto ols built

uponstandard ommuni ationte hnologiesareinvestigated,withthe

aim to meet both the spe i requirements imposed by ooperative

robotappli ations(e.g.,mobilityandlowlaten y)andthosethatare

typi alof industrialautomation networks.

Inthethesis,innovativesolutionsforseveral ommuni ation

te h-nologies,bothwiredandwireless,arepresentedanddes ribed. Among

(4)

En-mentsonproof-of- on eptimplementationsarereported,whi hprove

(5)

I wish to express my sin ere gratitude to the people who supported

meduring these years asa PhD andidate.

IwouldliketothankSTMi roele troni s,inparti ular,Ing.

Nun-zioAbbate, Ing. AlessandroFaulisiand Ing. Mar o Bran iforte, for

their onden e and the support they provided me, not only

materi-allybutalsothroughtheirnovelideasandsuggestionsformyresear h

a tivities.

Many thanks to Prof. Giovanni Mus ato, with whom I had the

pleasure to ollaborate duringthese three years.

Many thanks to Prof. Johan Akerberg for the hospitality and

for giving me the possibility to spent a period of time ondu ting

resear ha tivities at ABB AB, Corporate Resear h, Sweden.

Most importantly, I wish to extend my warmest and sin erest

gratitude to my advisor Prof. Lu ia Lo Bellofor the opportunity to

livethisamazingexperien e. Iamgratefultoher fortheadvi es,the

time and the eorts she invested in my professional edu ation and

for the hallenging and inspiring onversations thanks to whi h we

(6)

(7)

List of A ronyms v

List of Publi ations vii

In luded publi ations . . . vii

Publi ations not in luded . . . viii

1 Introdu tion 1

1.1 Resear h hallenges and methodology . . . 4

1.1.1 Introdu ingthesupport foraperiodi real-time

tra over EtherCAT networks . . . 4

1.1.2 Lowdataratewirelesste hnologiesforreal-time

ommuni ation in automationand

roboti s . . . 5

1.1.3 Consumerwirelesste hnologiesforreal-time

om-muni ation inautomation and

roboti s . . . 8

2 S hedulingofAperiodi Real-TimeMessagesover

Ether-CAT Networks 11

2.1 The Priority-driven Swapping . . . 16

2.1.1 Implementing the Priority-driven Swapping . 19

2.2 Analyti Assessment . . . 20

2.2.1 Framepropagation and Timing . . . 20

(8)

2.3 Simulativeassessments . . . 30

2.3.1 SimulationModel Assessment . . . 30

2.3.2 Cy le Time assessment . . . 33

2.3.3 Comparisonwith the CAN-Like . . . 36

2.4 Con lusions . . . 38

3 Simulative assessments of the IEEE 802.15.4e DSME and TSCH proto ols 41 3.1 RelatedWork . . . 42

3.2 Overview of the 802.15.4e standard . . . 44

3.2.1 Low Laten y Determinist Network (LLDN) . 45 3.2.2 Deterministi and Syn hronous Multi- hannel Extension(DSME) proto ol . . . 45

3.2.3 TimeSlotted Channel Hopping (TSCH) . . . 49

3.3 SimulativeAssessment . . . 51

3.3.1 Reliability and delay assessment . . . 52

3.3.2 S alabilityAssessment . . . 56

3.4 Con lusionsand future works . . . 61

4 A Priority-Aware Multi hannel Adaptive Framework for the IEEE 802.15.4e-LLDN 63 4.1 RelatedWork . . . 65

4.2 LLDN: anoverview . . . 67

4.3 The Priority-based Multi hannel-LLDN . . . 69

4.3.1 Priority-aware s heduling. . . 69

4.3.2 Multi hannel ommuni ation. . . 70

4.3.3 Dynami hannel ongurationand bla klisting 73 4.4 S hedulability analysis . . . 74

4.4.1 Response-time analysis . . . 75

4.5 SimulationS enario . . . 81

4.5.1 S alabilityassessment . . . 83

(9)

5 A novel MAC proto ol for low datarate ooperative mobile robot teams 93 5.1 Related Work . . . 95

5.2 Design hoi es . . . 98

5.2.1 Boundeddelays . . . 98

5.2.2 S alability . . . 99

5.2.3 Node Mobility . . . 100

5.2.4 Advantages of the proposed approa h . . . 102

5.3 The RoboMACproto ol . . . 102

5.3.1 Physi alLayer. . . 103

5.3.2 Mediuma ess and syn hronization . . . 105

5.3.3 Clustering and routinglayer . . . 106

5.4 Experimentalassessment . . . 108

5.4.1 Pa ketLoss Ratio . . . 108

5.4.2 RoboMAC test ona real appli tion . . . 110

6 An Innovative Approa h to support S heduled Tra in Ad-ho Industrial IEEE 802.11 networks 115 6.1 Related Works. . . 117

6.2 Ba kground of the EDCA me hanism . . . 120

6.3 The S hedWiFi approa h. . . 121

6.3.1 S heduled Tra . . . 121

6.3.2 Sizingthe ST-Window . . . 123

6.3.3 Non-STtra . . . 124

6.3.4 Time-Aware Shaper (TAS) . . . 125

6.4 Performan e Evaluation . . . 126

6.4.1 SimulationS enario . . . 126

6.4.2 Tra Modeland EvaluationMetri s . . . 129

6.5 Results . . . 130

(10)

6.6 Con lusionsand future works . . . 138

7 A BluetoothLowEnergyreal-timeproto ol for indus-trial wireless mesh networks 141 7.1 RelatedWork . . . 142

7.2 A hieving Bounded Laten ies onBLE Networks . . . 143

7.2.1 Overview on BLE . . . 143

7.2.2 ConguringBLE to obtain bounded laten ies 145 7.3 Proto ol Design . . . 147

7.4 Timinganalysis and analyti al assessment . . . 151

7.4.1 Analyti al results . . . 152

7.5 Experimentalresults . . . 154

8 Con lusions and future works 159

(11)

AIFS Arbitration InterFrame Spa e

API Appli ation Program Interfa e

ARQ Automati RepeatreQuest

BLE Bluetooth LowEnergy

CAN Controller AreaNetwork

CAP Contention A essPeriod

CCA Clear ChannelAssessment

CCCD Client Chara teristi Conguration Des riptor

CFP Contention-Free Period

CPS Cyber-Physi al Systems

CSMA/CA Carrier Sense MultipleA esswithCollision Avoidan e

DCC Dynami ChannelConguration

DMR Deadline MissRatio

DSME Deterministi and Syn hronous Multi- hannel Extension

E2ED End-to-End Delay

EB Enhan ed Bea on

EDCA Enhan ed Distributed ChannelA ess

FIFO First-InFirst-Out

GTS Guaranteed TimeSlots

(12)

MAC Medium A essControl

MCCA MeshCoordinationFun tionControlledChannel A ess

MCU Mi roController Unit

NLM Network LinkMatrix

NSP Network SaturationPoint

PAN PersonalAreaNetwork

PCA PriorityChannelA ess

PLR Pa ketLoss Ratio

RSSI Re eivedSignal Strength Indi ator

RTE Real-Time Ethernet

SPI Serial Peripheral Interfa e

ST S heduled Tra

TAS Time-AwareShaper

TDMA Time DivisionMultiple A ess

TSCH Time Slotted ChannelHopping

(13)

In luded publi ations

- Publi ation A. L. Lo Bello, E. Bini, G. Patti, Priority-Driven

Swapping-Based S heduling of Aperiodi Real-Time Messages

Over EtherCAT Networks, IEEE Transa tions on Industrial

Informati s,vol. 11, issue 3,pp. 741-751,Aug. 2014.

- Publi ation B. G. Alderisi, G. Patti, O. Mirabella, L. Lo Bello,

SimulativeassessmentsoftheIEEE802.15.4eDSMEandTSCH

in realisti pro ess automation s enarios, Pro . of the IEEE

13th International Conferen e on Industrial Informati s

(IN-DIN), Cambridge, UK,July 2015.

- Publi ation C. G. Patti, L. Lo Bello, A Priority-Aware

Multi- hannel Adaptive Framework for the IEEE 802.15.4e-LLDN,

IEEE Transa tions on Industrial Ele troni s, vol. 63, no. 10,

pp. 6360-6370, O t. 2016.

- Publi ation D. G. Patti, G. Mus ato, N. Abbate, L. Lo Bello,

Towards Low-datarate Communi ations for Cooperative

Mo-bileRobots, Pro . of the IEEE World Conferen e on Fa tory

Communi ation Systems (WFCS), Palma de Mallor a, Spain,

05/2015.

- Publi ation E. G. Patti, G. Alderisi, L. Lo Bello, S hedWiFi:

(14)

Ad-tory Automation (ETFA),Luxembourg, Sept. 2015.

- Publi ation F. G. Patti, L. Leonardi, L. Lo Bello, A Bluetooth

LowEnergyreal-timeproto olforindustrialwirelessmesh

net-works, Pro . of the 42nd Annual Conferen e of IEEE

Indus-trial Ele troni s So iety (IECON),Floren e, Italy, O t. 2016.

Publi ations not in luded

•

M. Ashjaei,G.Patti, M. Behnam,T. Nolte, G.Alderisi, L. Lo Bello,S hedulability AnalysisofEthernet Audio Video

Bridg-ingNetworks with S heduled Tra Support, Real-Time

Sys-tems - The International Journal of Time-Criti al Computing

Systems , a epted Jan. 2017, toappear.

•

G.Patti, G.Alderisi,L.LoBello,Introdu ingmulti-level om-muni ationinthe IEEE802.15.4e proto ol: the

MultiChannel-LLDN, Pro . of the IEEE 19th International Conferen e on

EmergingTe hnologies and Fa tory Automation (ETFA),

Bar elona,Spain, 09/2014.

•

G.Patti,G.Alderisi,Anapproa htowardsadaptivityin wire-less sensor networks, Pro . of the International Conferen e

on Numeri al Analysis and Applied Mathemati s (ICNAAM),

Rhodes, Gree e,09/2014.

•

L. Lo Bello, G. Patti, G. Alderisi, V.D. Patti, O. Mirabella, A FlexibleMe hanism for E ient Transmission of Aperiodi

Real-Time Messages over EtherCAT networks, Pro . of the

IEEE InternationalWorkshoponFa toryCommuni ation

(15)

Introdu tion

Inthelastyearsthein reasingspreadofsmartsensors,abletoa quire

data frommultiple transdu ers,pro essing itand takethe

appropri-ate de isions (su h, for instan e, the a tivation of one or multiple

a tuators), has opened new frontiers for the investigation of more

and more omplex industrial appli ations. In fa t, the apability of

su h devi es topro ess data in ade entralizedway provides a

note-worthy potential for distributing on multiple nodes the pro essing

a tivitiestoperform omplextasks. Inthis ontext, ommuni ations

play a very importantrole, as they enable the oordination and the

ooperation of the a tors of automation appli ations (e.g., sensors,

a tuators, roboti arms, et ).

The oordinated a tion of sensors and a tuators in the

automa-tion eld requires network ar hite tures and ommuni ation

proto- ols,bothwirelessandwired,abletosupport theintera tionbetween

multipledevi esnot onlyinareliableway, butalsoguaranteeingthe

meetingof the real-time onstrains of the supported appli ations.

In this ontext of distributed pro essing among oordinated

au-tomationdevi es, teams of ooperating robots ome into play. This

isamajorimprovementinroboti s,as ooperationenablesrobotsto

gobeyond the limitationsof individuals,providingthe possibility to

(16)

perform alone.

This thesis stems from industrial needs and, more spe i ally,

fromthe ollaborationwith STMi roele troni s, with the aimof

en-abling the network te hnologies that are typi allyadopted in

indus-trialautomationtosupportalso ooperativerobotappli ationsinthe

industrialautomations enario.

Theheterogeneityofthesupportedappli ationsandtheir

require-mentsimposestheinvestigationofinnovative ommuni ationsystems

able to fulllall the appli ation needs. Forinstan e, the integration

ofmultiplemobilerobotsinanautomationnetworkalsorequires

mo-bilitysupporttogetherwithotherfeaturessu has,real-timebehavior

and reliability.

Intheindustrialautomation,theexibilityandadaptivityof

om-muni ation systems has also gained a remarkable interest. For

in-stan e, Germany started the so- alled fourth industrial revolution

(Industrie4.0 [2℄), whi h foresees the Internet onne tivity of

indus-trialassets[3℄. A ording tothe Industrie4.0 vision,industry shall

develop networks integrating ma hinery, sensors, plants with nodes

able toautonomously ex hange information,trigger a tions,and

o-operate with ea h other withouthuman intervention. This not only

applies to eld devi es or ma hines, but also to the mobile robots

that, for instan e, automati ally transports various types of goods

onthefa tory oororhandle materialsinautomatedmanufa turing

systems.

The typi al requirements of industrial automation

ommuni a-tions are summarized inthe following.

- Reliability: Automationnetworkshavetoprovideasuitable

relia-bilitylevelforthetransmissions,i.e.,alowerrorprobability. To

ope with this requirement, some of the me hanisms adopted

are retransmissions(with orwithout a knowledgement),

relay-ing(i.e.,thetransmissionofamessageovermultiplepathsfrom

thesour etothedestination),andAutomati RepeatreQuests

(17)

astopofsomehoursentailshigh ostsfortheindustry. Forthis

reason,fault-toleran e me hanisms (su h as,node redundan y

and re overy, repli ation of fun tions) have to be provided.

- Real-Time: Networks have to meet the timing onstraints of the

supportedappli ations. Thismeansthat the end-to-enddelays

ofmessages, i.e., the delivery times fromthe sour etothe

des-tination,have to be bounded and predi table. Hen e, suitable

deadline-aware Medium A ess Control(MAC) me hanismsto

avoid unpredi tability in ommuni ations and s heduling

poli- ies have to be investigated.

The above mentioned requirementshavea generalsigni an e in

automation networks. However, appli ations impose dierent

on-straints. In parti ular, ooperative multi-robot appli ations require

networks able tosupport additional onstraints,e.g.,

- Low message laten y: Due to the fast dynami s of this kind of

systems,messagesnotonlyhavetobedeliveredwithina ertain

deadline (real-time requirement), but also need low message

laten ies (i.e., from hundreds of mi rose onds to hundreds of

millise onds).

- S alability: Cooperative multi-robotnetworks are typi ally

real-ized with a high numberof nodes. However, some of the most

adopted medium a ess me hanisms in industrial automation

are TDMA-based. Su h a me hanism is well known to be not

very s alable,asahigh numberof nodes entailsahighnumber

of timeslots in the ommuni ation y le, thus in reasing the

messagelaten y.

- Mobility: Theintrodu tionofmobilerobots inthe industrial

s e-nario entails additionalrequirements onthe networks. In

par-ti ular,thestandardwireless ommuni ationte hnologies,su h

(18)

support node mobility. For these reasons, several me hanisms,

whi hmodify thestandard spe i ation,were proposed [4℄,[5℄.

However, the support for mobility should not lash with the

otherrequirements des ribed above.

- Support to multiple tra lasses: The integration of the

In-ternet te hnologies in roboti s appli ations and also in

indus-trialnetworksrequiresthe supportforthe transmissionof

mul-tiple tra types, with dierent timing onstraints, in an

ef- ient way and without ompromising the transmission of the

ontrol tra (that is generally the most riti alone).

This thesis proposes innovative me hanisms that build upon the

existing ommuni ation te hnologies used in automation and enable

themtosupporttheneedsofreal-timeindustrialappli ations,

in lud-ing the ones based on teams of ooperating robots. The aim of the

work is tomeet the requirements of mobility,lowlaten y and

s ala-bility that are imposed by ooperative robot appli ations and those

of reliability,fault-toleran e and real-time that are typi al of

indus-trialautomationnetworks. Innovativesolutions are investigated and

novelme hanisms,proto olsandalgorithmsfordierentte hnologies

are proposed.

1.1 Resear h hallenges and methodology

Theresear h hallenges addressed inthisthesis are variousand refer

toboth wired and wirelesste hnologies.

1.1.1 Introdu ing the support for aperiodi

real-time tra over EtherCAT networks

The EtherCAT proto olis areal-timeEthernet standard adopted in

multipleautomations enarios(substationautomationinsmartgrids,

(19)

and meets the requirements of industrial real-time ommuni ations.

Among the RTE proto ols, the EtherCAT standard is suitable for

motion ontrol and losed-loop ontrol appli ations, whi h require

very short y le times. One important limitation for event-driven

roboti s appli ations is that, as EtherCAT was spe i ally devised

for periodi tra , aperiodi real-time transmissions are far from

being e ient and entaillong y le times.

To over ome this limitation, the rst resear h hallenge of this

thesis is therefore introdu ing the support for aperiodi real-time

tra over EtherCAT networks. The solution proposed is a general

frameworkforpriority-drivenswapping-baseds hedulingofaperiodi

real-timemessages overEtherCAT networks,whi h uniformly overs

bothdynami andstati priorityandallowsforveryshort y letimes.

Chapter 2 provides a des ription of the priority-driven swapping

framework, a s hedulability analysis for both stati priority and

dy-nami prioritys heduling,andsimulativeassessments,obtainedthrough

OMNeT++simulations.

1.1.2 Low datarate wireless te hnologies for

real-time ommuni ation in automation and

roboti s

These ondresear h hallengeregardsthesuitabilityof extending

in-dustriallowdataratewirelesste hnologiesforsupporting ooperative

robotsappli ations. The resear ha tivities startwith anassessment

ofexisting wireless ommuni ation te hnologies, inorderto evaluate

their suitability for supporting ooperative robot appli ations. The

fo us is on the proto ols of the IEEE 802.15.4e standard, as they

are novel and promising. Then, the resear h work ontinues with

the investigationof me hanisms toimprovethe s alability,the

fault-toleran e,andtointrodu emessageprioritizationintheLow-Laten y

Deterministi Network(LLDN) proto ol. Next,alow-datarateMAC

proto ol spe i ally devised for ooperative mobile robot

(20)

mentionedproto olonSTMi roele troni sSub-GHzdevi es(i.e.,

de-vi esoperating onfrequen ies lower than 1GHz) is presented.

Step 1. Performan e assessment of the IEEE 802.15.4e

pro-to ols. Thisstepaddressesthe assessmentofthewirelessproto ols

dened in the IEEE 802.15.4e standard for low datarate Industrial

Wireless Sensor Networks (IWSNs). The IEEE 802.15.4 standard

is not able to ope with the requirements whi h are found in many

appli ation domainsthat require lowlaten y, robustness, and

deter-minism. Forthis reason, the IEEE 802.15.4e amendment was

intro-du ed,whi hprovidesnovelMAC-layerprolesthatareoptimizedfor

abroadrange ofappli ation domains,in ludingpro ess automation.

The rst step fo uses on two of these proles, i.e., the

Determinis-ti and Syn hronous Multi- hannelExtension(DSME)andthe Time

Slotted Channel Hopping (TSCH). The aim of this work is twofold.

First, assessing their behavior in realisti pro ess automation

s e-narios. Se ond, omparing their performan e in terms of end-to-end

delay,reliabilityands alability. Theultimateaimoftheworkis

iden-tifying the limitsof those proto ols, thus paving the way to further

work addressing suitableapproa hes to ta kle them.

Chapter 3 presents the des ription of the proto ols, dened in

the IEEE 802.15.4e standard, the assessed s enario and simulative

results.

Step2. Improvingtheexistingte hnologies: theLow-Laten y

Deterministi networks. TheLLDNproto olisintendedfor

fa -toryautomationappli ationsthat requireverylowlaten y and large

networks,su has automotivemanufa turingand roboti s. However,

LLDN does not provide priority support to properly deal with

real-timetra ordynami hannel onguration apabilitiesto opewith

unreliable hannels. Moreover, it oers a limited s alability, as the

y le time grows linearly with the number of network nodes. This

thesis therefore proposes the priority-aware multi- hannel adaptive

(21)

s heduling,multi hannel ommuni ation,adaptive hannelsele tion,

and hannelbla klisting. PriMulAsupports ahigher numberof

net-worknodes thanthe LLDNproto olwhilekeepingshort y le times.

Inaddition,PriMulAavoids deadlinemiss andimprovesthe network

reliability. It maintains the interoperability with LLDN standard

nodes and an beimplemented on ommer ial o-the-shelf devi es.

Chapter 4 presents the PriMuA framework, the s hedulability

analysis, omparative simulations to assess the performan e, and a

proof-of- on eptimplementation.

Step 3. A novel solution: the RoboMAC proto ol. The

PriMulA framework meets the requirements of real-time, reliability,

fault-toleran e,lowlaten yand s alabilityimposed by theindustrial

and ooperating robot appli ations. For this reason it is a suitable

solution for the appli ations that donot require mobility. However,

PriMulAis not suitablefor mobilerobotappli ations, asit doesnot

support the node mobility. Moreover, re ent ooperative robot

ap-pli ationsenvisage the supportof lowdatarate ommuni ation

te h-nologies,as this hoi e isbene ialin terms of energy onsumption,

weight redu tion and integration with WSNs. Forthese reasons, the

resear hworktargetsaninnovativelowdatarateproto ol,spe i ally

devised for ooperative mobile robots appli ations, that operates on

lowdatarate networks and isable toprovide bounded laten ies,

mo-bility and s alability.

Chapter 5 presents the RoboMAC proto ol and its

implementa-tion on Sub-GHz devi es produ ed by STMi roele troni s.

Exper-imental assessments prove the proto ol suitability for ooperating

(22)

1.1.3 Consumerwirelesste hnologiesforreal-time

ommuni ation in automation and

roboti s

The third resear h hallenge is the introdu tion of a me hanism to

support real-time transmissions over wireless mesh networks. The

a tivitiesforesees twosteps relatedtothe IEEE802.11 proto oland

the Bluetooth Low Energy proto ol, respe tively.

Step 1. Introdu ing s heduled tra over IEEE 802.11

ad-ho networks. The spreaduse ofIEEE 802.11 networksin

indus-trialautomationraisetheneedtosupportmultipletra lasseswith

dierent requirements. The work targets a novel approa h, alled

S hedWiFi, that provides exible support to the s heduled tra

lass, i.e., a high priority tra lass that is transmitted a ording

to a xed s hedule, over IEEE 802.11 ad-ho industrial networks.

S hedWiFi operates on the IEEE 802.11n physi al layer, thus

pro-vidinghighdatarate,andsupportsmultipletra lasseswith

dier-ent priorities. S hedWiFi modies the Enhan ed Distributed

Chan-nelA ess(EDCA)me hanismallowingtotransmits heduled tra

withoutrequiring any predened superframe stru ture, ortimeslots,

thusallowingfor more exible s hedule of non-STtra .

Chapter 6presents theS hedWiFiproto oland asimulative

per-forman eassessment in realisti s enarios.

Step 2. Introdu ing real-time ommuni ation in Bluetooth

Low Energy mesh networks. The large diusion of hand-held

devi es opens new frontiers in the human intera tion with the

in-dustrial plant and its robots. The Bluetooth Low Energy (BLE)

proto ol is an attra tive solution for implementing low- ost IWSN

with redu ed energy onsumption and high exibility. However, the

urrent BLE standard does not provide real-time support for data

pa kets and is limited to a star topology. This thesis presents R

(23)

isdeveloped ontop of the BLE and over omes these limitations.

Chapter 7des ribes the RT-BLE proto oland provides a timing

analysis, a proof-of on ept implementation on STMi roele troni s

BlueNRG-MSdevi es, analyti al and experimentalresults.

Chapter 8 gives the on lusions of this thesis and provides the

(24)

(25)

S heduling of Aperiodi

Real-Time Messages over

EtherCAT Networks

The integration of heterogeneous appli ations with dierent

infor-mationows and requirements requiresnetworks apabletosupport

multi-servi e ommuni ations. In parti ular, modern industrial

net-worksmust oersupport forboth time-driven and event-driven

on-trolappli ations. In time-driven appli ations, messages are

periodi- allytransmittedand ontrola tionsaretaken at onstantrate[6,7℄,

while in event-driven appli ations, messages are transmitted when

one or more trigger events o ur (e.g., if the ontrolled variable

ex- eeds a given threshold) [8,9℄. For example, losed-loop ontrol

ap-pli ationstypi ally generate periodi messages with deadlines of

ap-proximately 1 ms [7℄. However, these appli ations may also require

the transmissionofaperiodi real-timemessages, that haveto be

a - ommodatedintheoverall tra s hedulewithoutae tingperiodi

messages. Aperiodi real-timetransmissionsarealsofoundin

Cyber-Physi alSystems (CPSs), as they typi ally operate inunpredi table

environments [1012℄.

(26)

be- ome in reasingly popular, as they oer high bandwidth, meet the

requirementsofindustrialreal-time ommuni ationandallowfor

ver-ti alintegrationofthedierentlevelsintheautomationpyramid[14℄.

Re ent literature highlighted the properties of industrial Ethernet

networksabletosupportvarioustra lasses[15℄andtemporal

on-straints [16℄. One example is Pronet IRT, whose bandwidth

man-agementand s hedulingare addressed in [17℄ and [18℄, respe tively.

Another interesting real-time Ethernet proto ol is TTEthernet [19℄,

whi hoersthreedierenttra lassestosupportthetemporaland

bandwidth onstraints of a broadrange of appli ations.

This hapterfo usesontheEtherCATproto ol,whi hisin luded

inboththeIEC61158[20℄and IEC61784[13℄standards. EtherCAT

is suitable for motion ontrol and losed-loop ontrol appli ations,

whi h require veryshort y le times,where the y le time is dened

asthetimene essary toex hangetheinput/outputdatabetweenthe

ontrollerand all the networked devi es on e [21,22℄.

EtherCAT provides a daisy- hain topology and a master/slave

ar hite ture in whi h the master periodi ally transmits a standard

EthernetframethatembedsanEtherCATframe ontainingmultiple

telegrams (as shown in Figure2.1). Slaves read and/or write data in

the telegram by pro essing the frame on-the-y, so when a byte

arrives to a slave it is pro essed and transmitted to the next slave

without waiting for the omplete re eption of the Ethernet frame.

The last slave in the hain transmits the frame ba k to the master

by exploiting the full-duplex apability of Ethernet.

As shown in Fig.2.1, the EtherCAT frame used for transmitting

pro ess data ontains one or multiple telegrams, whi h start with a

header ontainingthe ommand ode(i.e.,read,writeorread/write),

the addressing elds, and the payload length. Telegrams end with

aWorking Counter (WKC) eld, whi h is in remented by the slaves

everytimetheysu essfullyreadand/orwritedataintothetelegram.

The WKC isalsoused forerror dete tion.

In order toallowslaves totransmitperiodi real-timetra ,the

(27)

instan e, the master may send EtherCATframes ontaining atleast

onetelegramforea hslavethatmighthaveaperiodi real-timetra

totransmit.

However, su h a me hanism would entaillong y le times, asthe

mastermust provideroominthe EtherCAT framefor anyslavethat

hasthe potentialtotransmitaperiodi real-timetra ,regardlessof

whethersu haslavea tuallyhastra totransmit. Forinstan e, in

anetworkwith 20slaves, ea h withthe potentialfortransmitting32

bytelongaperiodi real-timemessages, themastershouldprovide20

telegramsforea h y le. Thiswouldresultinanin reaseinthe y le

time durationof 70.4

µs

, with the probability that most of the time su h telegrams would not a tually be used, due to the event-driven

natureof aperiodi tra generation.

Standard Ethernet Frame

EtherCAT Frame

EtherCAT Telegram

Ethernet Payload (42 - 1500 bytes)

Ethernet Header (22 bytes)

FCS (4 bytes)

EtherCAT Header (2 bytes)

EtherCAT Telegram

Header (10 bytes)

Data

Working Counter (2 bytes)

...

Figure2.1: Stru tureofanEtherCATframe ontainingmultiple

tele-grams

In additiontothe y le time in rease, the needfor handling

ape-riodi real-timemessages by a polling me hanism performed by the

masterwouldalsointrodu e,inthe aseofevent-triggered ontrol

ap-pli ations,abandwidthwastethat wouldredu ethemain advantage

of the event-triggered ontrol, that is, the low bandwidth demand.

Some works in the re ent literature address methods to redu e

the y le timesin theEtherCATnetworks. In[23℄ periodi and

(28)

guaranteed bandwidth for the slave transmissions. In [24℄ a swit h

operating at the EtherCAT telegram level is proposed, but su h a

solutiondoes not fo us onaperiodi tra s heduling.

The work in[25℄ proposes anarbitration-baseda ess s heme for

aperiodi real-time messages whi h introdu es new aperiodi

tele-grams that are ontented by the slaves for transmitting aperiodi

messages. The slave with the highest priority among the ones

om-peting for the aperiodi telegrams willoverwrite on-the-y the

in- omingaperiodi message.

The me hanismin [25℄ foresees that the master transmitsa opy

of the aperiodi message re eived. In this way, the slave that

trans-mittedthemessagerealizesthat itwassu essfuland sothemessage

an be safely removed from its queue. Conversely, the other slaves

know that they did not su eed and must try again. This approa h

redu es the y le timefortransmittingaperiodi messages ompared

withthe EtherCAT standard, butstillsuers fromsome limitations.

The main one is that low priority messages may experien e long

de-lays due tothe interferen e fromhigh priorityones, with apotential

for starvation.

Thesameauthorsin[26℄addedthe apabilityforembedding

mul-tiple aperiodi messages in one telegram. In this new approa h, a

slave has to re eive a umulative a knowledgement message from

the master before removing the transmitted message from the lo al

queue. The purpose ofsu h amessage istwofold. It isa noti ation

of su essful transmission and alsoa way to allowa slave toremove

the aperiodi message fromits lo alqueue.

Inspired by the Slot Swapping Proto ol (SSP) [2729℄, in [30℄

dynami prioritiesare exploitedto swap between anin oming lower

priority aperiodi messageand a higher priority messagepending at

the urrent slave. This is a hieved by dening anew telegramtype,

ontented amongtheslavesthathaveanaperiodi real-timemessage

totransmit.

Contention is ruled by omparing the absolute deadlines of the

(29)

on- ontention, itisswapped andrepla ed by themessagewith themost

urgentdeadlineinthelo alqueue. Swappingdoesnot entailmessage

loss,be ausethe slavewhi hhas swapped the in omingmessagewill

be in harge of transmitting itwhenever possible.

Contributions of this hapter In this hapter a Priority-driven

swapping-based me hanism to deal with the problem of providing

support for aperiodi real-time tra over EtherCAT networks is

presented. As previously explained, the EtherCAT standard does

notoerthis support. ThePriority-driven swapping-basedapproa h

ombines the arbitration me hanism in[26℄ with thedeadline-driven

swappingproposedin[30℄. Inparti ular, this workextends the work

in[30℄,whi honlyaddressesEDFs heduling, inageneralframework

for priority-driven swapping-based s heduling of aperiodi real-time

messages overEtherCATnetworks, whi h uniformly overs both

dy-nami and stati priority. The proposed me hanism allows slaves to

transmitmultipleaperiodi real-timemessages inasingleEtherCAT

frame,while maintaining ompatibilitywiththe EtherCATstandard

and a hieving y le times in the order of

100µs

.

The target is to a hieve short y le times while ensuring the

s hedulability of aperiodi real-time messages. For this reason, the

hapter provides s hedulability onditions that enable the network

designer to ongure the network parameters (e.g., the number of

aperiodi telegrams in the EtherCAT frame) soas to avoiddeadline

miss. The Priority-driven Swapping here proposed is implementable

with minor modi ations in the EtherCAT proto ol state ma hine

and maintains ompatibility with EtherCAT standard devi es, so

there isa lear potentialfor industrialexploitation.

This hapter is organized as follows. Se tion 2.1 des ribes the

Priority-driven Swapping approa h here proposed and dis usses its

implementation. Se t. 2.2 presents the timing analysis of the

ap-proa h, under stati and dynami priorities, respe tively. Se t. 2.3

(30)

approa hand dis usses its performan e. Finally,Se t. 2.4 on ludes

the hapter and giveshints forfuture work.

2.1 The Priority-driven Swapping

InthePriority-drivenSwappingapproa hhereproposedtoe iently

supportaperiodi tra underbothstati anddynami priority

s hedul-ing, a novel telegram has been introdu ed. The aperiodi telegram,

whi h is shown in Figure 2.2, is ontented among the slaves

a ord-ing toa preemptive poli y that enables the slaves to send aperiodi

messages when needed. This is possible as the daisy- hain topology

ofEtherCATallows formessagepreemptionby hangingon-the-y

thetelegrampayloadofanin omingframewhentheframestraverses

aslave.

Telegram HDR

(CMD = DDS)

ApM_PRIO

ApM_ADR

ApM_LEN

ApM_PAYLOAD

PADDING

(if needed)

WCK

Bytes

10

6

4

2 ApM_LEN

2 ApM Header

ApM

Ethernet Header

Header EtherCAT

Telegram

Aperiodic Telegram

FCS

Figure 2.2: Aperiodi Telegram stru ture

Ea hslavemaintainsalo alqueueofaperiodi messages(ApMs),

ordered a ording to a priority. The network an work under either

stati ordynami prioritys heduling, but the hoi e has tobe made

duringthe ongurationphase, through a suitablesetting.

In order tomaintain ompatibility withthe EtherCATstandard,

the aperiodi telegramis mapped into the standard EtherCAT

tele-gram asshown inTable 2.1.

The CMD eld of the telegram header ontains the 0x10 value

whi h indi atesan aperiodi telegram, while the ADR eld ontains

the address of the slave that generated the last re eived ApM. The

(31)

Table 2.1: Aperiodi Telegram elds.

Data Field DataType Des ription/Value

CMD Unsigned8 Command: (PdS)0x10

IDX Unsigned8 Index

ADR DWORD SlaveaddressofthelastApM

LEN Unsigned11 DATAeldLength

RESERVED Unsigned3 0x00

C Unsigned1 Cir ulatingframe

NEXT Unsigned1 0ifthelasttelegramintheframe

IRQ WORD Reservedforfutureuse

DATA O te tString Data

WKC WORD WorkingCounter

The DATA eld ontains an ApM, whi h is the aperiodi message

ontaining the data transmitted by a slave. The ApM is omposed

of an ApM header and a payload. The header elds are spe ied as

follows:

•

ApM_PRIO: the message priority.

•

ApM_ADR:theaddressoftheslavethattransmittedtheApM.

•

ApM_LEN: the ApM payload lengthin bytes.

The master periodi allytransmits one EtherCAT frame

ontain-ingbothstandardtelegramsfortheperiodi dataandoneormultiple

aperiodi telegrams. A slave, with a ready-to-transmit ApM, upon

re eivingthe aperiodi telegram,storesthe lo alApMwiththe

high-est priority (

M

loc

)inthe outputbuer (Out_Buf)andthe in oming ApM(

M

in

)intheinputbuer (In_Buf). When therst byteof

M

in

arrives, the ontention starts and the slave ompares byte by byte

theprioritiesof

M

loc

and

M

in

. Themessagewiththehighestpriority value is transmitted, while the other one is stored in the slave lo al

queue.

For priority omparison, due to serial ommuni ation, the six

(32)

most to the least signi ant byte. The omparison works as follows.

The i-th byte of the priority of the in oming message

M

in

(i.e., the ApM_PRIO eld of the ApM),

B

i,in

, for i=0...5, is ompared with the orrespondingbyteofthe ApM_DLeldoftheApM ofthelo al

message

M

loc

,

B

i,loc

. The in oming message

M

in

is swapped if the following inequality (2.1) holds (here we assume that the lower the

value, the higher the priority):

B

i,loc

< B

i,in

(2.1)

otherwise

M

in

is forwarded to the next slave. No swapo urs if the in omingApM has the same priorityas the lo alApM. If a ording

to inequality (2.1) a swap o urs, while the lo al message

M

loc

is transmittedto the next slaveand removed fromthe lo alqueue, the

swapped message has to be entirely re eived and is then inserted in

the lo al queue a ording to its priority. Su h a me hanism annot

be implemented in the upper layer of the Data Link, as it requires

on-the-y pro essing of the frame.

Compared to the EtherCAT standard [20℄, the Priority-driven

swappingprovidesthepossibilityforslavestotransmitaperiodi

mes-sageswithoutthe need forthe mastertoprovideroomfor ea hslave

with a potential for transmitting, thus redu ing the y le time. In

fa t,asingleaperiodi telegram anbe ontentedamongalltheslaves

that intend to transmit an aperiodi message. If ompared to the

me hanism proposed in [26℄, the Priority-driven swapping provides

two advantages. First, it allows a slave to embed more aperiodi

telegrams into a single EtherCAT frame. This is possible be ause

the slavewhi hhas swapped the in omingmessagewillbe in harge

of transmitting it whenever possible. Se ond, thanks to this

me ha-nism,aslavewhi htransmittedanApM anremoveitfromthelo al

queue rightafter ompleting thetransmission withoutwaiting foran

a knowledgement message,asnoaperiodi messagewillbelostdue

topreemption fromother messages.

This is not the ase for the CAN-like approa h in [26℄, where a

(33)

before removing the transmitted message from the lo al queue, so

the same slave annotsend more than one aperiodi message in the

same telegram. The se ond advantage ompared to [26℄, whi h only

addresses stati prioritiesinaCAN-likefashion,is thatthe

Priority-driven swapping uniformly overs both dynami and stati priority

s heduling,therefore,atthe ongurationstep,the mostappropriate

s heduling poli y for the appli ation at hand an be hosen on a

ase-by- ase basis.

An example of dynami priority s heduling is the Earliest

Dead-line First (EDF) algorithm [31℄, in whi h the messages with loser

absolutedeadlinespreempt thosewithlessimminentones. To

imple-ment EDF in the Priority-driven swapping approa h here proposed,

the absolutedeadline ountsthe mi rose ondselapsedsin e January

1, 2000 (the date refers to the EtherCAT system time [32℄) and a

slave generating an ApM al ulates the absolutedeadlineby adding

tothe systemtime therelativedeadlineofthe messagere eived from

the upperlayers. Su h a me hanism relies onthe lo k

syn hroniza-tion, whi h is also provided with the EtherCAT standard with an

a ura yin the order of

100ns

[32℄.

2.1.1 Implementing the Priority-driven Swapping

Ea hEtherCATslave onsists of three layers, i.e.:

•

Appli ationlayer,whi h ontainstheHostController. This an beimplemented, for instan e, in ami ro ontroller.

•

Data Link Layer, whi h ontains the EtherCAT Slave Con-troller (ESC). This an be implemented either in hardware

(FPGA,ASIC) or insoftware [33℄.

•

Physi alLayer, whi himplementsthe physi al interfa e tothe network.

The Priority-driven Swapping approa h requires an additional

(34)

a prioritized lo al queue ontaining the lo al ApMs, two buers for

the in oming and out oming ApMs, and an 8-bit omparator. All

these omponents an be implemented in hardware in the ase of

FPGA/ASICESC. The hardware implementation ofthe buers and

the omparator is simple and, as far as the prioritized lo al queue

is on erned, in the literature several hardware implementations of

prioritized lo al queues are proposed [34℄ (e.g., Shift register

priori-tized queue or Systoli array prioritized queue). The module an be

alsoimplemented in software in the ase of software ESC, as shown

in [33℄. Some slight modi ation in the EtherCAT proto ol state

ma hine has alsoto be added in order to handle the novel telegram

type.

Application Layer

Physical Layer

Data Link Layer

EtherCAT Slave Controller (ESC)

Prioritized

Local

Queue

InBuf

OutBuf

Comparator

<=

Standard ESC

Modules

Network Interface

Host Controller

Figure2.3: Modules implementingthe Priority-driven Swapping

2.2 Analyti Assessment

2.2.1 Frame propagation and Timing

In EtherCAT networks, if the data to be embedded in the Ethernet

(35)

Ethernet frames will have to be transmitted by the master to

om-plete a y le. However, this hapter addresses the ase of veryshort

y le times (e.g., in the order of

100µs

), and a maximum payload Ethernet frame has a y le time of

150µs

. Hen e, here only a single frame y le is onsidered.

Figure 2.4 illustratesthe propagation of the Ethernet frameand

therelatedterminologyandnotations(alsosummarizedinTable2.2).

The Figure shows a s enario with an Ethernet frame that is

trans-mittedbythemastertoa hainofthreeslaves, andthengoesba kto

the master a ording to the daisy hain topology. In Figure2.4 the

master is represented twi e to illustrate separately the transmission

(top-side) and the re eption (bottom-side). The propagation of the

Ethernetheaderand theFrameChe kSequen e (FCS)eldisdrawn

inlight gray.

The Ethernet payloadis drawn intwoshades of gray (gray/dark

gray). In the payload, we highlightin darkgray the EtherCAT

tele-grams(threeinthegure)dedi atedtothetransmissionofaperiodi

messages (ApMs). All the notations are des ribed in Table 2.2.

The master periodi ally sends an Ethernet frame, with period

P

. Ea h frame then propagates to the slaves through the network. Slaves are labeled following the frame re eption order, so slave

1

is the one that re eives the frame rst, while slave

m

is the last. The time elapsing from the transmission of a frame by the master to its

re eption,asaresponse[20℄,isequaltothetimeneededby thesignal

topropagatethrough themedium(

T

pr

), plusthe timeneeded bythe

m

slavesto pro ess the frame(

T

de

).

From Figure 2.4 it is possible to observe that the slaves pro ess

theframeon-the-y,i.e.,ea hframestartstobetransmittedbefore

ithasbeenfully re eived fromthe pre edingnode. This allows alow

end-to-end laten y and enables the transmission of an ApM even if

the external event generating the ApM arrives during the re eption

ofthe Ethernetframe. Atanyslave,theinstantatwhi hthe highest

priority ApM is transmitted is the start of the re eption of the next

(36)

Table 2.2: Summaryof notation

Symbol Denition

m

Thenumberofslavesinthe hain

ℓ

k

Lengthofthe able onne tingthe

k

-thslavetothe

(k + 1)

-thslave.

ℓ

0

isthe lengthofthe able onne tingthemastertoslave

1

,while

ℓ

m

thelengthofthe able onne tingslave

m

ba ktothemaster.

P

ThetransmissionperiodoftheEthernetframe.

T

c

The minimum y le time, i.e., the minimumtimetaken by all the network nodesto ex hange their input/output data on e. In Figure2.4,

T

c

= T

et

+

T

ec

+ T

pr

+ T

de

+ T

if

.

T

et

Thesumofthe transmissiontimesofthe Ethernet header andFrameChe k Sequen e(FCS)elds(

a

+ c

inFig.2.4).

T

ec

Thetimene essarytotransmittheEtherCATframe.

u

The propagation delay per unit of length over the medium(that is 5 ns/m a ordingtotheEtherCATstandard).

T

pr

Thepropagationdelayoverthe ommuni ationmediumthatisequalto

T

pr

=

u

P

m

_k=0

ℓ

k

.

T

sv

thetimetakenbyea hslavetopro esstheframe.

∆

k

thedelayfromthere eptionofaframeatslave

k

tothere eptionofthesame frameatthemaster,thatis

(m − k + 1)T

sv

+ u

P

m

i=k

ℓ

i

.

T

de

Theframedelaythatis

mT

sv

.

T

if

Theinter-framegap,i.e.,the timebetween theendofthetransmissionofan Ethernetframeandthestartofthetransmissionofthenextone.

p

Numberofaperiodi telegramsintheframe(

p

= 3

inFig.2.4).

T

ap

ThetimebetweenthestartofthetransmissionoftheEthernetframeandthe startofthetransmissionoftherstaperiodi telegram(

a

+ b − pq

inFig.2.4).

n

ThenumberofApMs.

π

i

Theindexoftheslavewherethe

i

-thApMisgenerated.

pri(i)

Priorityofthe

i

-thApM.

T

i

Theminimuminterarrivaltimebetween two onse utiveinstan esofthe

i

-th ApM.

D

i

Therelativedeadlineofthe

i

-thApM.

S

Thetimeforre eivinganaperiodi telegram(

q

inFig.2.4).

A

Timeelapsingfromthestartofthere eptionoftherstaperiodi telegramto theendofthere eptionoftheframe(

pS

+ c

inFig.2.4).

(37)

d

r

master

slave 1

slave 2

slave 3

master

a+c

b

e+g+k+o

f+h+n

a

b

c

d

e f g h k n o

r

q

c

_time

PSfrag repla ements Ethernet header/FCS Ethernet payload

Aperiodi EtherCATtelegrams

T

et

=

T

ec

=

T

pr

=

T

de

=

T

if

=

T

ap

=

T

c

A

P

Figure2.4: EtherCATframe pro essingsequen e

aperiodi telegrams must be arefully analyzed,as illustrated in the

following.

2.2.2 Timing Analysis

In real-timesystems, inwhi h the fo us is onmeeting the deadlines

inthe worst ase,the analysisismadebydeterminingtheworst ase

forboth theresour e availabilityandtheresour erequest[35℄. Inthe

analysis the samenumberof aperiodi telegramsfor ea hEtherCAT

frameis assumed.

In this ontext, the resour e is the start time of an aperiodi

telegram. Hen e, the worst ase for the resour e availability is

de-termined by omputing the minimum number

s(t)

of start times of aperiodi telegrams whi h may o ur inany intervalof length

t

. As illustrated in Fig. 2.5, the worst- ase interval (that is the one

on-taining the minimum number of start times of aperiodi telegrams)

(38)

instant(pleaserefertoFig.2.5wherethebla k dotsdenotethestart

timeoftheaperiodi telegrams overtime),thetime aslavemayhave

towaitbeforeanotheraperiodi telegramstartsis

P −(p−1)S

. Then

p

aperiodi telegramswillstart,spa ed

S

,andthepatternwillrepeat with period

P

.

7

6

5

4

3

2

1

PSfrag repla ements

s(t)

t

S

P

P−(p−1)S

2P

P

Figure2.5: Exampleoftheminimumnumberofstarttimes

s(t)

,with

p = 3

aperiodi telegrams ina frame.

The formalexpression of

s(t)

an then be writtenas follows

s(t) =

p

X

j=1

t + (j − 1)S

P

,

(2.2)

whi h a ounts for the fa tthat:

•

the start times of the

p

aperiodi telegrams in the same frame are separated by

S

;

•

onse utive aperiodi telegrams at the same position in the frameare separated by

P

.

In the example shown in Figure 2.5, we have

p = 3

aperiodi tele-grams ina frame.

(39)

2.2.3 Response-time analysis

For omputing the longest response time of an ApM, we adopt the

lassi busy-intervalapproa h[36℄, whi hwasextended tothe

event-stream task model [37℄ by Rit her et al [38℄. To apply this method,

itis ne essary to ompute the longest time

w(N)

aslavehas towait tosee

N

onse utivestart times of aperiodi messages. Bythis de-nition,

w(N)

is given by

w(N) = sup{x ∈ R : s(x) < N}.

(2.3)

By denition,

w(N)

then is the longest time interval in whi h less than

N

aperiodi telegrams may start.

Inthespe ial aseof

s(t)

of(2.2), onse utiveaperiodi telegrams in the same frame are separated by

S

, while the last aperiodi tele-gramintheframeandtherstoneinthenextframeareseparatedby

P − (p − 1)S

,sothat aperiodi telegrams atthesame positioninthe frameare separated exa tly by

P

. As also illustrated in Figure 2.5, this ondition implies that

w(N)

in reases by

P − (p − 1)S

when

N

isamultipleof

p

,whileitin reasesby

S

atallothervaluesof

N

(not multipleof

p

). Hen e

w(N)

an bewritten as

w(N) = (Q + 1)P − (p − 1 − Z)S

(2.4)

with

Q

and

Z

, respe tively,quotientand remainderof theEu lidean divisionof

N − 1

by

p

,thatis

N − 1 = Qp + Z

with

Z ∈ {0, 1, . . . , p −

1}

. Forexample,if

p = 3

(asillustratedinFig. 2.5)and

N = 1

,then the result of the Eu lidean division is

Q = 0

and

Z = 0

. For this hoi e, from (2.4) we nd

w(1) = P − 2S

, whi h orre tly is the longest separation between two onse utive aperiodi telegrams. If,

for example,

N = 3

, then

Q = 0, Z = 2

and

w(3) = P

. With these denitions in mind, we an ompute the response time of an ApM,

byapplyingthe lassi albusy-periodapproa h. First,wedene

I

j

(t)

as the largest number of messages of the

j

-th ApM whi h an be generated in any interval of length

t

. For example, in the lassi al exampleofsporadi ApMwithminimuminterarrivaltime

T

j

,wehave

(40)

I

j

(t) =

l

t

T

j

m

. Then, we ompute the largest number

N

i

of aperiodi telegrams, whi h may be needed to transmit the

i

-th ApM, as the smallestxed point of the following iteration











N

_i

(0)

= 1

N

_i

(k+1)

= 1 +

P

pri(j)>pri(i)

I

j

(w(N

i

(k)

))

+

P

pri(j)=pri(i)

π

j

<π

i

I

j

(w(N

i

(k)

))

+

P

pri(j)=pri(i)

π

j

=π

i

,j6=i

1.

(2.5) The expression of

N

(k+1)

i

a ounts for the fa t that in the time in-terval

w(N

(k)

i

)

we must onsider the following possible sour es of interferen e:

•

the ApMs with higher priority, represented by the rst sum with

j

su h that

pri(j) > pri(i)

;

•

the ApMs with the same priority as the

i

-th, but generated at pre eding slaves (as des ribed earlier, an in oming ApM with

thesamepriorityoftheApMatthelo alslaveisnotswapped),

represented by the sum over

pri(j) = pri(i), π

j

< π

i

;

•

the ApMs at the same slave with the same priority, whi h, however, may interfere only on e, sin e ApMs with the same

priority are s heduled FIFO within the same slave (the last

term inthe sum of (2.5)).

Note that, if messages have minimum interarrival time

T

j

, the above des ribed iterative denition is proved to onverge [36℄ if the

maximumnumberofneededaperiodi telegramsislessthanthe

avail-able ones, that is

X

pri(j)>pri(i)

1 T

j

<

p

P

.

(2.6)

On e

N

i

is omputed,the response time (

R

i

) of the

i

-thApM is

(41)

with the following interpretation:

• ∆

π

i

is the maximum time fromthe slave

π

i

tothe master;

• w(N

i

)

is the time the

i

-th ApM may have to wait tohave one telegramavailable;

• A

is the time from the re eption of the aperiodi telegram at the masterto the instantthe messageis a tuallyread.

2.2.4 EDF analysis

If the ApMs have a deadline

D

i

between their release at the slave andthe deliverytimeatthe master,andApM prioritiesare assigned

basedonEDF,soitisthenpossibletotightentheanalysisby

adapt-ingthe lassi EDF guarantee test [39℄.

Theorem 1. A set of

n

aperiodi messages (ApMs), ea h one trig-gered by events with minimum interarrival time

T

i

are guaranteed to be re eived at the master within

D

i

from their release time when s heduled by EDF, if:

∀t > 0,

n

X

i=1

max

0,

t − (D

i

− ∆

π

i

− A)

T

i

+ 1

≤ s(t).

(2.8)

Proof. Sin e the priority of ApMs is assigned a ording to EDF, we

adapt the guarantee test based on the demand bound fun tion [39℄.

Dierently than a lassi CPU s heduling problem, the resour e to

bes heduledisnottheCPUtimebut rathertheaperiodi telegrams.

Asalsoillustratedby thedarkgraybandinFigure2.4,thesame

ape-riodi telegramis available atdierent times for dierent slaves. To

removethis slave-dependent time shift,weset the ommonreferen e

timeatthe re eptionside ofthe master(illustratedasthe horizontal

lineat the bottom of Figure 2.4). The arrival of any ApM at time

t

atslave

k

an be equivalently represented by the arrivalof the same message at time

t + ∆

k

at the master. Then, if the

i

-th ApM has

(42)

deadline

D

i

fromthearrivalatslave

π

i

tothere eptionatthemaster, it an be equivalently represented by a message arriving dire tly at

the masterwithdeadline

D

i

− ∆

π

i

. In addition,the assumptionthat the latest time totransmitthe ApMs is atthe start of the re eption

ofthein omingaperiodi telegram,whilethereadingoftheaperiodi

messageis made onlyat the end of the re eption of the entire frame

at the master, implies that all ApM deadlines must be de remented

by an amount

A = T

et

+ T

ec

− T

ap

(also represented in Figure 2.4 by

pq + c

). In on lusion, the demand boundfun tion [39℄, whi h in this ase isthe largest possiblenumber of ApMswith arrival properly

translated tothe referen e timeat the masterand deadline within an

interval of length

t

,is given by the following expression:

n

X

i=1

max

0,

t − (D

i

− ∆

π

i

− A)

T

i

+ 1

(2.9)

Sin e the minimum possiblenumberofaperiodi telegrams

avail-able in any interval of length

t

is represented by

s(t)

, then Condi-tion (2.8) holds, be ause EDF an s hedule any task set for whi h

the demand bound fun tion does not ex eed the available resour e

for all

t ≥ 0

. Hen e, the Theorem is proved.

Condition (2.8) alsoimplies the ne essary ondition

n

X

i=1

1 T

i

≤

p

P

(2.10)

whi hisequivalenttothe lassi ne essary onditionofanon-overloaded

pro essorin CPU s hedulingproblems.

Theorem 1 provides a test whi h is not pra ti al. In the next

Lemma,followingthe idea by Baruah etal[40℄, we redu ethe set in

whi h the inequality of (2.8) needsto be tested toa nite one.

Lemma1. Asetof

n

aperiodi messages(ApMs),ea honetriggered byevents with minimum interarrivaltime

T

i

are guaranteed to be re- eivedatthemaster within

D

i

from theirreleasetimewhens heduled

(43)

by EDF, if:

n

X

i=1

1 T

i

<

p

P

(2.11) and

∀t ∈ D,

n

X

i=1

max

0,

t − φ

i

T

i

≤ s(t)

(2.12) with

φ

i

= D

i

− ∆

π

i

− A − T

i

(2.13)

L

∗

_{= max}

ℓ=0,...,n

p

P

(P − (p − 1)S) −

P

ℓ

i=1

φ

i

T

i

p

P

−

P

ℓ

i=1

T

1 i

(2.14)

D = {d : d = φ

i

+ kT

i

, i = 1, . . . , n, k ∈ N, d < L

∗

},

(2.15)

and assumingthat ApMs are sorted by an in reasing value of

φ

i

. Proof. Weobserve that

s(t)

of(2.2) an belowerbounded asfollows

s(t) ≥

p

X

j=1

t + (j − 1)S

P

− 1

=

p

P

(t − P )+

S

P

p

X

j=1

(j − 1)

=

p

P

(t − P ) +

S

P

p(p − 1) =

p

P

(t − (P − (p − 1)S)).

The left-hand side (LHS) of (2.8), whi h we denote for simpli ity

dbf(t)

to re all the demand bound fun tion of EDF s heduling [39℄, an be upperbounded asfollows

dbf(t) ≤

n

X

i=1

max

0,

t − φ

i

T

i

= max

ℓ=0,...,n

ℓ

X

i=1

t − φ

i

T

i

,

sin e the ordering

φ

1 ≤ φ

2 ≤ . . . ≤ φ

n

holds. From the lower bound of

s(t)

and the upper bound of

dbt(t)

, it follows that

dbt(t) ≤ s(t)

(44)

for all

t

satisfyingthe next ondition

dbf

(t) ≤ max

ℓ=0,...,n

ℓ

X

i=1

t − φ

i

T

i

≤

p

P

(t − (P − (p − 1)S)) ≤ s(t)

∀ℓ = 0, . . . , n,

ℓ

X

i=1

t − φ

i

T

i

≤

p

P

(t − (P − (p − 1)S))

∀ℓ = 0, . . . , n,

p

P

(P − (p − 1)S) −

ℓ

X

i=1

φ

i

T

i

≤ t(

p

P

−

ℓ

X

i=1

1 T

i

)

∀ℓ = 0, . . . , n, t ≥

p

P

(P − (p − 1)S) −

P

ℓ

i=1

φ

i

T

i

p

P

−

P

ℓ

i=1

T

1 i

t ≥ max

ℓ=0,...,n

p

P

(P − (p − 1)S) −

P

ℓ

i=1

φ

i

T

i

p

P

−

P

ℓ

i=1

T

1 i

= L

∗

_.

NotethatdividingLHSand right-handside(RHS)by

p

P

−

P

ℓ

i=1

1 T

i

is

possible, thanks tothe hypothesis of (2.10).

Then

∀t ≥ L

∗

is always

dbf(t) ≤ s(t)

. If, instead,

t < L

∗

the

ondition(2.8)needstobeexpli itly he ked. However, itissu ient

to he kitonlyatthedis ontinuityoftheLHS,whi haretheabsolute

deadlines of allApMs not larger than

L

∗

, all ontained in

D

.

2.3 Simulative assessments

2.3.1 Simulation Model Assessment

To assess the performan e of the proposed approa h,a suitable

sim-ulation model was developed using the OMNeT++ framework. In

the simulation model two kinds of nodes are implemented, i.e., the

EtherCAT Master and the EtherCAT Slave. The EtherCAT

Mas-ter is omposed ofa MasterDLL moduleand a MasterPHY module.

The rst moduleperiodi allygenerates Ethernet frames and olle ts

(45)

pa kets and transmits ea h byte every

0.08µs

(i.e., the byte time of the 100Mb/s Ethernet). In this way, the timing of the simulation

modelis ompliantwiththatof theEtherCATstandard. The

Ether-CATSlavemoduleprovidesseveral fun tionalities. Amongthem,the

EtherCATDLL,whi hsupportsboththeperiodi telegramsforeseen

bythestandardandtheaperiodi telegramsoftheproposed

Priority-driven swappingapproa h, the forwarding me hanisms for in oming

pa kets, theread/writeandmanagementfun tionsoftheApMslo al

queue, and the slave Appli ationlayer.

The simulation modelwas assessed by omparing the EtherCAT

timing parameters al ulated as in Se t. 2.2 with those obtained in

thesimulation. Inparti ular,forthesimulations,atypi alnetworked

ontrolsystemformotion ontrolwassimulated. Thesystem onsists

of one ontroller (the master), 5 devi es (the slaves), 6 joints and 4

wheels. Three slaves are in harge of 2 axesea h, and the other two

slavesmanage4wheels(2wheelsforea hslave). Forthejoint ontrol

48-bytedata is y li allyex hangedwithaperiodof

50µs

,arealisti value for these appli ations [41℄. The wheels are ontrolled in an

event-triggered way, so the tra is sporadi (i.e., hara terized by

a minimum interarrivaltime). The data transmission period for the

wheel ontrolis

500µs

[42℄anddatasize attheappli ationlayeris32 bytes. Thewheel ontroltra israndomlygeneratedbetween

500µs

and

1000µs

using a uniform distribution. The relative deadline

D

i

is hosen equal to the minimum interarrival time (i.e.,

500µs

). The slavesmayalsotransmitevent noti ationmessages hara terizedby

T

i

= 1000µs

and

D

i

= 1000µs

. Thedistan ebetweentwo onse utive network nodes is2m, sothe overall distan e overedbythe Ethernet

frames is 20m. The relevant simulation parameters and timing are

summarizedin Table 2.3.

In the simulation, the slaves 1 and 2 manage the wheels, while

the slaves 4,5, and 6 are in harge of the 6 joints. Table 2.4 shows

the ApMs parameters. An ApM set indi ates the ApMs with the

same interarrival time

T

i

and the same relativedeadline

D

i

, and

∆

k

isthe delay fromthe re eption of aframeatslave

k

tothe re eption

(46)

Table 2.3: Simulation I - Network parameters and timings

Net. params Value/range

T

sv

1µs

T

pr

50ns

T

c

46.33µs

P

41.28µs

A

3.84µs

p

1

Payloadsizeofanaperiodi telegram

44

bytes Numberofperiodi telegrams

7

Payloadsizeofaperiodi telegram

48

bytes

of the same frame at the master (as dened in Table 2.2). With

theseparameters,the onditionsofLemma1aremet. Therefore,the

s hedulingof the ApMset isfeasible.

Table 2.4: Sporadi Tra parameters of simulationI

ApMsSet Slave

π

i

T

i

D

i

∆

k

1

1 500µs

500µs

5.040µs

1

2 500µs

500µs

4.030µs

2

1 1000µs

1000µs

5.040µs

2

2 1000µs

1000µs

4.030µs

2

3 1000µs

1000µs

3.020µs

2

4 1000µs

1000µs

2.010µs

2

5 1000µs

1000µs

1.000µs

A simulation run of 10s, orresponding to a generation of about

20000 ApMs, was performed and simulations were repeated 5 times

varyingtheseedoftherandomgenerators. The al ulated y letime

is

46.33µs

as required from the appli ation. Results show that the response timevalues obtained by the simulationmat hthe ones

al- ulatedusingthe analysis des ribed inSe tion2.2. In Figure2.6the

Cumulative Per entage Distribution of the message response times,

denedastheper entageofApMswiththe responsetime lowerthan

(47)

0

20

40

60

80

100

120

140

0

10

20

30

40

50

60

70

80

90

100 Response Time (us)

Cumulative Percentage Distribution (%)

ApM1 (D: 500us)

ApM2 (D: 1000us)

Figure 2.6: Cumulative Per entage Distribution of the ApM

Re-sponse Times.

This orresponds to the results of the analysis that proved the

feasibility of the onsidered ApM set (i.e., that the ApM response

timesarealwayslowerthantheirrelativedeadlines)intheaddressed

s enario. The same simulationwas performed usingstati priorities.

Results also mat h with the values obtained with the analysis in

Se t. 2.2.3.

2.3.2 Cy le Time assessment

To assess the y le times whi h an be rea hed using the proposed

approa h and to ompare it with the standard EtherCAT, a set of

simulationswere performed. The goalof these simulationsis tond

theminimumnumberofaperiodi telegramsrequiredtotransmitthe

ApMs while maintaining the Deadline Miss Ratio (DMR) (i.e., the

numberofdeadlinemissesoverthenumberofgeneratedApMs)lower

than 0.1%.

Ea h slave generated ApMs with three dierent priorities (or

deadlinesinthe aseofEDFs heduling). ApMsweregeneratedwith

exponentially distributed random generation periods with a given

(48)

a-ble 2.5 shows the simulation parameters. Lambda is given as an

intervalbe auseforea hsimulationrundierentlambdavalueswere

used. This hoi ewas madein ordertoevaluate the proto ol

perfor-man ewith varying mean generationperiods.

Tohaverealisti framesizes, 20periodi telegramswere

transmit-ted, in additionto the aperiodi telegrams, every y le. This entails

an in rease of

70.4µs

in the y le time. Ea h simulation run was repeated 5times varying the seed. In ea h simulation the simulated

time was hosen to olle t statisti sover 50000ApMs.

Table 2.5: Parameters of SimulationII

Parameters Values/Range

Numberofslaves

10

Numberofperiodi telegrams

20

Payloadsizeofaperiodi telegram

32

bytes Numberofaperiodi telegrams(

p

) from

1

to

8

Payloadsizeofanaperiodi telegram

32

bytes

ApMsdeadlines

300µs, 600µs, 900µs

λ

from

186µs

to

1515µs

Repetitions

5

repetitionsvaryingtheseed

In reasing the number of aperiodi telegrams embedded in the

EtherCAT frameentailsanin rease in the y le time. Forthe

simu-lated s enario, the y le time values as a fun tion of the number of

aperiodi telegrams are shown in Table 2.6.

Table 2.6: Cy le Time asa fun tionof the number of aperiodi

tele-grams inthe EtherCATframe

p

T

c

p

T

c

1

87.62µs

5

101.70µs

2

91.14µs

6

105.22µs

3

94.66µs

7

108.74µs

4

98.18µs

8

112.26µs

Figure 2.7 ompares the simulation results obtained by the