Francisco Manuel Pozo Pérez försvarar sin doktorsavhandling i datavetenskap

Disputationer och licentiatseminarier

Datum: 2019-10-24
Tid: 13.30
Plats: sal Milos, MDH Västerås

Francisco Manuel Pozo Pérez vid akademin för innovation, design och teknik (IDT), försvarar sin doktorsavhandling i datavetenskap den 24 oktober klockan 13.30 i sal Milos, MDH Västerås.

Titel: “Methods for Efficient and Adaptive Scheduling of Next-Generation Time-Triggered Networks”.

Serienummer: 296.

Oppontent är professor professor Petru Eles, Linköpings universitet.

Betygsnämnden utgörs av professor Roman Obermaisser, University of Siegen, professor Franz Wotawa, Graz University of Technology och doktor Liliana Cucu-Grosjean, INRIA.

Reserv: professor Björn Lisper, MDH.

Sammanfattning:

Många datorbaserade system består av noder som för att fullfölja sina uppgifter kommunicerar via meddelanden som skickas över nätverk. I vissa system räcker det inte med att informationen är korrekt, även timingen för kommunikationen är viktig. Dessa system kallas för realtidssystem. Ett exempel är självkörande bilar. Om en autonom bil bromsar för tidigt eller försent kan den orsaka en olycka medförande alvarliga skador på såväl människor som fordon. En etablerad metod för att uppnå korrekt timing är via tidsstyrd kommunikation där det vid systemets design skapas ett schema som styr när meddelanden skickas. Typisk skickas meddelandena periodiskt, t.ex. var tionde millisekund. Vid drift följer systemnoderna schemat för att försäkra sig om att alla meddelanden skickas när det är tänkt. Man kan jämföra detta med tågtidtabeller som ser till att tåg kan ta sig från punkt A till punkt B via ett antal mellanliggande stationer utan kollisioner med andra tåg och så att passagerarna (i vårt fall informationen) kommer fram till rätt plats vid rätt tid.

Många existerande och tidigare realtidssystem är relativt små, och hittas t.ex. i bilar, plan, tåg eller industriella maskiner. Komplexiteten för dessa tillämpningar har kontinuerligt växt, och framtidens realtidssystem, t.ex. i fabriker med ett stort antal samarbetande produktionsceller eller för styrning och kontroll av trafik och energianvändning i smarta städer, förväntas vara betydligt mer komplexa än dagens. Denna avhandling behandlar två huvudproblemen som uppstår när man applicerar tidsstyrd kommunikation i stora system: hög komplexitet och låg flexibilitet.

Att ta fram det statiska schema som är kärnan i tidsstyrd kommunikation är ett mycket komplext problem. En metod är att översätta schemaläggningsproblemet till ett motsvarande matematiskt problem, för att sedan mata in det i en så-kallad SMT lösare, som returnerar överföringstiderna för alla meddelanden. Att lösa detta problem för system som är tiofalt större en dagens. I denna avhandling presenterar vi en lösning där problemet delas upp i mindre, mer hanterbara problem. För att t.ex. skapa ett schema för en hel timme, kan vi dela upp problemet i 60 scheman som vardera omfattar en minut. Den bristande flexibiliteten har sin grund i schemaläggningens bristande förmåga att stödja förändringar i systemet, såsom att lägga till nya komponenter eller hantera fel som uppstår. En möjlig lösning för felhantering, som t.ex. används i flygplan, är kommunikation över tre olika nätverk – om fel uppstår i ett av nätverken så kommer informationen fram i ett av de andra nätverken, men för nätverk som t.ex. spänner över en hel stad så är den typen av lösning alldeles för kostsam. Ett alternativ är att vid fel utarbeta ett nytt schema som kringgår problemet. Men att ta fram ett nytt schema för ett stort system tar flera timmar, vilket är alltför lång tid. Vi föreslår en metod som bara ändrar den del av schemat som påverkas av felet, vilket kan göras betydligt snabbare.

Vi har utvärderat våra metoder för schemaläggning och felhantering i ett stort antal scenarier. Resultaten är mycket lovande och indikerar att vi kan hantera tio gånger så stora system jämfört med vad som kan hanteras med existerande metoder. Vi kan dessutom med mycket stor sannolikhet justera schemat vid kommunikationsfel utan att störa driften.