Honderden roddeltantes houden samen treinstoelen in de gaten

22 september 2010

Het Myrianed-project van Devlab wil tienduizend apparaatjes laten samenwerken in een draadloos netwerk. Het initiatief onderscheidt zich door niet de individuele nodes als uitgangspunt te nemen maar het netwerk als geheel. Chess heeft de aanpak onlangs met succes gedemonstreerd in een zitplaatsreserveringssyteem voor de nieuwe Fyra-hogesnelheidstreinen.

In het kader van het Myrianed-project heeft Chess een proof of concept gebouwd van een draadloos netwerk met honderden knooppunten. Het gaat hierbij om een zitplaatsreserveringssyteem in de nieuwe Fyra-treinen van NS Hispeed. Dit houdt voor elk deel van het totale traject bij of een stoel is gereserveerd of niet. Een bedrade installatie van de zitplaatsindicatoren is om verschillende redenen niet gewenst, ook niet voor de energiedistributie. In plaats daarvan hebben we een efficiënt, energiezuinig, robuust, schaalbaar, zelforganiserend en zelfherstellend draadloos netwerk aangelegd met Myriadned-nodes.

Voor de proof of concept heeft NS Hispeed een trein van zes rijtuigen beschikbaar gesteld met in totaal ongeveer vijfhonderd stoelen. In slechts vier uur hebben we elke zitplaats voorzien van een Myrianode, het experiment en de demonstratie uitgevoerd, metingen gedaan en alles weer ontmanteld. Bij de uitrol van de indicatoren bij alle stoelen heeft het Myrianed-netwerk zichzelf ad hoc georganiseerd. Bij de demonstratie hebben we op willekeurig momenten de zitplaatsreserveringsinformatie geactualiseerd via een speciaal daarvoor ingerichte node. Het NS-personeel leverde de informatie aan en heeft deze ook bij de verschillende zitplaatsen geverifieerd. In werkelijkheid zal de informatie worden geactualiseerd bij het binnenrijden van een station.

Bij het ontwerp van de toepassing hebben we een en ander eerst gesimuleerd, met een pessimistische inschatting van systeemparameters en een zeer eenvoudig radiomodel. Hierbij bleek het gedrag van het systeem aan de gestelde eisen te voldoen: alle zitplaatsindicatoren kregen op tijd nieuwe informatie. Tijdens de demonstratie bleek het gedrag zelfs drie- tot vijfmaal beter dan gesimuleerd. Analyses achteraf tonen aan dat het onvoorspelbare gedrag van radioverbindingen in het Myrianed-concept juist leidt tot een betere totaalgedrag van het netwerk. Voor deze analyses hebben we elke indicator in het kader van dit experiment uitgerust met 4 Mbyte flash, waarin we alle relevante toestandsinformatie per communicatieronde opslaan. De tijdsrelatie tussen de afzonderlijke indicatoren hebben we vastgelegd met een global time protocol.

In slechts vier uur heeft Chess vijfhonderd Fyra-zitplaatsen voorzien van een Myrianode, het experiment en de demonstratie uitgevoerd, metingen gedaan en alles weer ontmanteld.

Gossip

Myrianed gaat uit van het netwerk en niet van de node. Met andere woorden: we werken top-down in plaats van bottom-up. Het executiemodel van het netwerk is locally asynchronous globally synchronous (Lags), wat wil zeggen dat de afzonderlijke Myrianodes de eigen processen asynchroon uitvoeren, terwijl de onderlinge uitwisseling van berichten volstrekt synchroon verloopt. Het kan dus zo zijn dat een node sensordata bemonstert of actuatordata genereert op een eigen lokale frequentie, die geheel onafhankelijk is van het ritme waarin hij met zijn omgeving communiceert.

Een Myrianode moet volstrekt autonoom kunnen werken. Dat betekent dat hij zichzelf moet initialiseren, samen met andere nodes een netwerk moet kunnen opzetten, dit moet kunnen onderhouden en problemen die zich voordoen, moet kunnen oplossen. Verder moet hij voorzien in zijn eigen energie. Vaak gebruikt hij daarvoor een batterij, maar soms ook een zonnecel of een ander systeem dat energie uit de omgeving haalt. Om de energieconsumptie zo laag mogelijk te houden, werkt de node met een duty cycle van 1 procent of minder, waarmee hij dus 1 procent van de tijd actief is en de rest van de tijd in een diepe slaap verkeert.

Voor de radiocommunicatie gebruiken we het Time Division Multiple Access-principe (TDMA). Elke Myrianode wordt op (bijna) hetzelfde moment wakker. Dit betekent dat de communicatiesloten van het TDMA-schema ook allemaal synchroon lopen en dat de gegevensuitwisseling zeer efficiënt en energiezuinig kan verlopen. Op elke node draait een gedistribueerd synchronisatiealgoritme, dat het moment van wakker worden adaptief bijstelt op basis van de gemeten tijdsverschuiving van de ontvangen berichten. Alle nodes hebben een 32 kHz tijdsreferentie met dezelfde nauwkeurigheid als een polshorloge. Het synchronisatiealgoritme hoeft daarom steeds maar een kleine correctie uit te voeren om het hele netwerk netjes in de pas te laten lopen. Uit wetenschappelijk onderzoek en grootschalige experimenten met duizend Myrianodes is gebleken dat dit prima werkt.

Berichten worden altijd als broadcast verzonden. Dat heeft een aantal redenen. Ten eerste is dit het natuurlijke gedrag van een radio. Ten tweede komt het goed overeen met het communicatiegedrag van levende wezens. Mensen praten op een broadcast-manier in hun omgeving, nemen informatie waar uit deze omgeving en besluiten daar wel of niet iets mee te doen. De Myrianode werkt op een soortgelijke manier.

Een andere metafoor die we hebben overgenomen, is de verspreiding van nieuwsberichten door middel van roddelen: een Myrianode herhaalt berichten die hij zelf heeft waargenomen zonder die noodzakelijkerwijs zelf te interpreteren. Berichten propageren door het netwerk zonder dat er een route nodig is en replicatie zorgt voor inherente robuustheid. De verspreiding gaat uitermate snel. De groep van Maarten van Steen aan de VU in Amsterdam doet hier onderzoek naar. De roddel- en andere communicatiefunctionaliteit hebben we op de Myrianode geïmplementeerd in de GMac, een Media Access Controller die is geoptimaliseerd voor gossip-toepassingen.

Een ander experiment heeft de Myrianed-aanpak aangetoond voor een draadloos netwerk met duizend knooppunten.

Myriacore

De ontwikkeling van de netwerktoepassing gebeurt op netwerkniveau. Hoe dat het beste kan, daar wordt nog volop onderzoek naar gedaan. Wij hebben ervoor gekozen de Myrianodes een tussentaal te laten spreken, de Token Machine Language (TML). Hierin programmeren we de netwerktoepassing. Dat doen we nu nog handmatig voor de verschillende nodes, maar in de toekomst zullen we daar een netwerkcompiler of synthesizer voor gebruiken. Het Myrianed-netwerk gedraagt zich als één Distributed Token Machine, waarbij elke node een TML-interpreter bevat om de tokens en de geassocieerde dataobjecten te evalueren.

Omdat we een Lags-executiemodel hanteren, is het eenvoudig om zoiets als globale tijd te implementeren. De elementaire resolutie van deze tijd is gelijk aan de frametijd waarin elke node een volledige cyclus van 100 procent duty cycle doorloopt. Daarbinnen kunnen we lokaal op fracties timen.

De GMac, de TML-interpreter en andere elementaire functies zijn samengebracht in de Myriacore. Deze draait één enkele executiethread, de Token Machine. Daarnaast is er nog een interruptthread, die onder meer de radiocommunicatie, timing en eventuele sensor- en actuatoractiviteiten verzorgt. Ook die sensoren en actuatoren handelen we af met tokens en ondersteunen we volgens het Lags-model.

Omdat we een aantal elegante en eenvoudige principes hebben gebruikt, is de implementatie van de Myriacore bijzonder efficiënt. De basisconfiguratie vergt slechts 8 kbyte flash en 1 kbyte SRam. De uiteindelijke geheugenfootprint is afhankelijk van de tokens die de netwerktoepassing moet ondersteunen.

Frits van der Wateren is als lid van het innovatieteam van Chess betrokken bij het Myrianed-project. Tijdens Bits&Chips 2010 Embedded Systemen op 11 november verzorgt hij een presentatie over de gevolgde aanpak.

Frits van der Wateren

Terug naar overzicht