Katholieke Universiteit Leuven Faculteit Ingenieurswetenschappen Departement Computerwetenschappen
EEN DYNAMISCH AANPASBARE VIRTUELE MACHINE VOOR SENSORNETWERKEN
´ Wouter HORRE Eindwerk aangeboden tot het behalen van de graad van burgerlijk ingenieur in de computerwetenschappen 2005–2006 Promotoren :
Prof. Dr. ir. P. VERBAETEN Prof. Dr. ir. W. JOOSEN
Faculteit Ingenieurswetenschappen Departement Computerwetenschappen Celestijnenlaan 200A 3001 Leuven (016) 32 77 00
K.U. Leuven Academiejaar 2005–2006
Naam en voornaam student : Horr´e Wouter Titel : Een dynamisch aanpasbare virtuele machine voor sensornetwerken Engelse vertaling : A dynamically adaptable virtual machine for sensor networks ACM Classificatie: C.2.4, D.2.11 AMS Classificatie: 68M14 Korte inhoud : Sensornetwerken kunnen ingezet worden in tal van toepassingen en worden daarvoor vaak ge¨ıntegreerd in dienstenplatformen. Door deze integratie in dienstenplatformen krijgen sensornetwerkapplicaties een end-to-end karakter. De diensten waarvoor ze worden ingezet zijn zeer gevarieerd en evolueren in de tijd. Om dienstverleners toe te laten hun diensten op een sensornetwerk te wijzigen of nieuwe diensten te operationaliseren, moet er een middleware komen die zoveel mogelijk abstractie maakt van de hardware en de dienstverleners zo goed mogelijk ondersteunt door zoveel mogelijk generieke componenten aan te bieden. Deze thesis zet een eerste stap in de richting van zo’n middleware door de introductie van een dynamisch aanpasbare virtuele machine. De dynamische virtuele machine die deze thesis voorstelt, combineert de voordelen van twee bestaande aanpakken voor de ondersteuning van dynamische aanpassingen. Een virtuele machine maakt het mogelijk om heel effici¨ent een sensornetwerk te herprogrammeren via ge¨ınterpreteerde instructies. Modulaire besturingssystemen laten toe uitvoerbare modules te laden of te verwijderen en bieden zo een grotere flexibiliteit tegen een hogere kost. Door beide mechanismen te voorzien, biedt een dynamische virtuele machine het beste uit twee werelden. Deze thesis ontwikkelt een architectuur voor een virtuele machine die dynamisch aangepast kan worden via de voorzieningen van een modulair besturingssysteem. De architectuur wordt gevalideerd door middel van een prototype implementatie.
Eindwerk aangeboden tot het behalen van de graad van burgerlijk ingenieur in de computerwetenschappen Promotoren :
Prof. Dr. ir. P. Verbaeten Prof. Dr. ir. W. Joosen
Assessoren :
Dr. S. Michiels Dr. E. Truyen
Begeleider :
Dr. S. Michiels
Voorwoord Na tien maanden hard werken is hij eindelijk af: mijn thesis. Het was voor mij een heel boeiende en leerrijke ervaring. Ik kreeg de kans om me in te werken in een voor mij volledig nieuw domein van de computerwetenschappen en om er mijn eigen weg in te zoeken. Ik wil dan ook mijn promotoren, Prof. Dr. ir. Verbaeten en Prof. Dr. ir. Joosen, bedanken omdat ze mij de vrijheid hebben gegeven om zelf te bepalen welke richting ik uitging met deze thesis. Ik wil ook mijn begeleider, Sam Michiels, bedanken om mijn zoektocht in het boeiende domein van de sensornetwerken in de juiste richting te helpen sturen. Ik wil hem ook bedanken voor de vele constructieve opmerkingen die mij geholpen hebben om deze thesis beter te maken. Bart Elen bedank ik voor zijn hulp tijdens mijn eerste ervaringen met de MICAz-sensorknopen. Christophe Vandeplas wil ik graag bedanken voor het gebruik van zijn USB-naarRS232-convertor als vervanging voor de mijne, die niet goed wilde werken. Verder wil ik ook de SOS-ontwikkelaars bedanken voor hun hulp op de momenten dat ik problemen had met SOS. Ik wil hen ook bedanken voor de snelle implementatie van een verbeterde versie van het dynamisch geheugen. Zonder mijn ouders zou deze thesis er nooit gekomen zijn. Ze hebben mij de kans gegeven om te studeren en hebben mij altijd gesteund tijdens mijn studies. Mama en papa: bedankt voor alles! Mijn zussen, grootouders, tantes, nonkels, neven en nichten, bedank ik voor hun interesse in mijn werk, voor hun vele vragen: Hoe lukt het met de thesis? Mijn vriendin, Saartje, heeft meer dan eens mijn tandengeknars moeten verdragen. Saartje, bedankt voor je begrip in stressvolle tijden!
Je gezelschap heeft mij er dikwijls bovenop
geholpen toen het vele werk even wat te zwaar werd. Mijn kotgenoten bedank ik voor de verstrooiing tijdens het vele werken, voor de vele babbeltjes op de gang, de ontspannende momenten in de keuken, de avonturen van Freddy het paasei,. . . Mijn vrienden van de KTIW wil ik bedanken voor het begrip dat ze opbrachten toen ik verstek moest geven voor de activiteiten van de laatste weken. Bedankt ULYSSIS, voor de fantastische infrastructuur. Bedankt del voor subversion, fur voor de backups, amy en uma voor de ontspanning, de andere machines om niet te veel problemen te veroorzaken en mijn collega medewerkers om de gemiddelde responstijd van ULYSSIS op peil te houden, ondanks mijn soms trage reacties. Mijn andere vrienden, in het bijzonder mijn jaargenoten, bedank ik voor de vele toe, ontspannende momenten waarop ik mijn batterijen opnieuw kon opladen voor een verse porsie thesiswerk. Tot slot bedank ik Linus Torvalds en de hele
Free/Libre and Open Source Software commu-
nity voor de ontwikkeling van linux en de vele andere programma's die ervoor hebben gezorgd dat ik virus-, spyware- en crashvrij kon werken aan deze thesis.
i
Inhoudsopgave Voorwoord
i
Inhoudsopgave
ii
1 Inleiding
1
1.1
Waarom sensornetwerken? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Wat zijn sensornetwerken? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2.1
Fundamentele vereisten
1.2.2
Ad hoc netwerken
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3
Toepassingen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.4
Motivatie van de thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.5
Doelstellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.6
Structuur van de tekst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2 Context 2.1
2.2
2.3
8
Platformen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.1
Hiërarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.1.2
Hardware karakteristieken . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.1.3
Besturingssystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
Drie gezichtspunten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.2.1
De geïsoleerde sensorknoop
12
2.2.2
Een sensorknoop als deel van het geheel
. . . . . . . . . . . . . . . . . .
13
2.2.3
Sensornetwerken als dienstverleners . . . . . . . . . . . . . . . . . . . . .
13
Middleware
. . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3.1
Middleware als aggregator . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3.2
Middleware als coördinator
. . . . . . . . . . . . . . . . . . . . . . . . .
14
2.3.3
Middleware als integrator
. . . . . . . . . . . . . . . . . . . . . . . . . .
14
3 Middleware voor sensornetwerken
16
3.1
Traditionele middlewaresystemen . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.2
De uitdagingen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
3.3
Verschillende aanpakken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.3.1
Programmeerondersteuning
3.3.2
Programmeerabstractie
3.4
. . . . . . . . . . . . . . . . . . . . . . . . .
20
. . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Situering thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.4.1
Aanpasbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.4.2
Virtuele machines als aanpasbaar platform . . . . . . . . . . . . . . . . .
23
ii
iii
INHOUDSOPGAVE
4 Maté en Sensor Operating System 4.1
4.2
26
Maté . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
4.1.1
Een virtuele machine gebruiken . . . . . . . . . . . . . . . . . . . . . . .
27
4.1.2
Een virtuele machine bouwen
. . . . . . . . . . . . . . . . . . . . . . . .
28
4.1.3
De opbouw van een ASVM
. . . . . . . . . . . . . . . . . . . . . . . . .
30
4.1.4
Trickle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
4.1.5
Dynamische ASVMs?
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.1
Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
4.2.2
Laden en verwijderen van modules
. . . . . . . . . . . . . . . . . . . . .
35
4.2.3
Bescherming
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
4.2.4
Dynamisch geheugen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
4.2.5
Evaluatie
38
Sensor Operating System
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 Analyse
39
5.1
De grenzen van het systeem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
5.2
Belangrijkste aandachtspunten
. . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.3
Aanpasbare virtuele machines . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
5.3.1
Normaal gebruik
40
5.3.2
Functionaliteit aanpassen
5.3.3
Meerdere applicaties
5.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
Vereisten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.4.1
Functionele vereisten . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
5.4.2
Niet-functionele vereisten
43
. . . . . . . . . . . . . . . . . . . . . . . . . .
6 Architectuur 6.1
44
Het gedeelte op de sensorknopen
. . . . . . . . . . . . . . . . . . . . . . . . . .
44
6.1.1
Componenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
6.1.2
Interfaces
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
6.2
Toolchain
6.3
Sequentiediagrammen
6.4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3.1
Aankomst capsule
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
6.3.2
Aankomst van een VM beschrijving . . . . . . . . . . . . . . . . . . . . .
50
6.3.3
Operatiebibliotheek laden
6.3.4
Context uitvoeren
. . . . . . . . . . . . . . . . . . . . . . . . . .
50
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
7 Prototype implementatie 7.1
49
53
Uitwerking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
7.1.1
Hergebruik van bestaande code . . . . . . . . . . . . . . . . . . . . . . .
53
7.1.2
Algoritme voor gedistribueerde consistentie
. . . . . . . . . . . . . . . .
54
7.1.3
Ontkoppeling tussen instructiesets en operatiebibliotheken . . . . . . . .
54
7.1.4
Gelijktijdigheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
7.1.5
Gegevensstructuren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
7.1.6
Beperkingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
7.2
Platform en testomgevingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
7.3
Problemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
iv
INHOUDSOPGAVE
7.4
7.5
7.3.1
Geheugenfragmentatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
7.3.2
Laden van modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Gebruik
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
7.4.1
Een operatiebibliotheek laden . . . . . . . . . . . . . . . . . . . . . . . .
62
7.4.2
Een virtuele machine aanpassen, toevoegen of verwijderen . . . . . . . .
62
7.4.3
Een virtuele machine gebruiken . . . . . . . . . . . . . . . . . . . . . . .
63
Besluit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
8 Besluit
65
8.1
Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
8.2
Evaluatie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
8.3
Verder werk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
A Formele use cases
71
A.1
Laad operatiebibliotheek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
A.2
Wijzig VM
71
A.3
Nieuwe instructie(s)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
A.4
Nieuwe context(en) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
A.5
Nieuwe virtuele machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hoofdstuk 1
Inleiding Draadloze sensornetwerken (Wireless Sensor Networks) zijn een boeiend onderzoeksdomein dat steeds meer aandacht krijgt in de literatuur. Ze zijn tevens het centrale onderwerp van deze thesis. Maar waarom zijn draadloze sensornetwerken zo interessant? Wat zijn draadloze sensornetwerken juist (niet)?
Welke toepassingen zijn mogelijk met behulp van draadloze
sensornetwerken? Deze inleiding probeert op deze vragen een antwoord te formuleren. Daarna volgt een motivatie en de doelstellingen van het werk in deze thesis.
Tenslotte wordt de
structuur van de rest van de tekst toegelicht.
1.1
Waarom sensornetwerken?
Reeds lang streeft de mens ernaar zijn omgeving intelligenter te maken. Denken we bijvoorbeeld aan automatische verlichting, automatische zonnewering, . . . Ook recente toekomstvisioenen zoals de intelligente koelkast en het intelligente schilderij horen bij dit streven. Industriële systemen worden eveneens intelligenter.
Automatische procescontrole is hier een voorbeeld
van. Deze arti cieel intelligente systemen interageren met hun omgeving. Dit in tegenstelling tot de domme systemen die enkel ingrijpen in hun omgeving.
Om interactie mogelijk te
maken moeten arti cieel intelligente systemen gegevens over hun omgeving te weten komen. Niet alleen intelligente systemen hebben nood aan informatie over hun omgeving.
Ook
mensen zijn vaak geïnteresseerd in gegevens over hun onmiddellijke omgeving of over een bepaald gebied.
Een klimatoloog kan bijvoorbeeld in het kader van een onderzoek nood
hebben aan gedetailleerde informatie over de luchtvochtigheid in een gebied in de woestijn. Legerleidingen zijn maar al te vaak geïnteresseerd in de troepenbewegingen in vijandig gebied. De benodigde informatie kan worden bekomen door metingen.
Zoals zo vaak wordt ge-
zegd: meten is weten. De metingen worden typisch verzameld door een sensorsysteem. Een sensorsysteem bestaat uit sensoren, een communicatienetwerk en verwerkingseenheden. Een klassiek sensorsysteem heeft meestal de volgende karakteristieken [3]:
•
De sensoren bevinden zich relatief ver van het te meten fenomeen. Dit vereist gespecialiseerde sensoren die in staat zijn het fenomeen te onderscheiden van de ruis.
•
Er worden verschillende gespecialiseerde sensoren gebruikt die beperkt zijn tot metingen.
•
De posities van de sensoren en de topologie van het communicatienetwerk zijn vooraf precies vastgelegd. 1
HOOFDSTUK 1.
•
2
INLEIDING
De sensoren versturen opeenvolgende metingen naar centrale computers die instaan voor de verwerking van de metingen.
Deze klassieke aanpak heeft een aantal problemen. De haalbare nauwkeurigheid is beperkt, de kostprijs is vaak vrij hoog, de sensoren kunnen moeilijk verplaatst worden en sensoren delen tussen verschillende toepassingen is moeilijk.
Nauwkeurigheid
De afstand tot het te meten fenomeen zorgt ervoor dat, ondanks de ge-
specialiseerde sensoren, de haalbare nauwkeurigheid beperkt is. Het is dikwijls niet mogelijk om de sensoren dichter bij het te meten fenomeen te plaatsen.
Bijvoorbeeld bij de obser-
vatie van dieren in een moeilijk toegankelijk oerwoud of bij de observatie van vijandelijke troepenbewegingen is het haast onmogelijk om de afstand onbeperkt kleiner te maken.
Kostprijs
De kostprijs van klassieke sensorsystemen kan aanzienlijk worden.
Dit is het
gevolg van de nood aan gespecialiseerde sensoren. Bovendien worden de sensoren meestal via kabels verbonden met een centrale computer. De kabels zelf en het plaatsen ervan brengen eveneens een belangrijke kostprijs met zich mee.
Mobiliteit
Door de statische opbouw van het communicatienetwerk is de mobiliteit van
een sensor in een klassiek sensorsysteem heel beperkt. In veel gevallen vormt dit geen grote beperking, maar in minstens evenveel gevallen beperkt dit de mogelijke toepassingen of het comfortabel gebruik van het sensorsysteem. De beperkte mobiliteit is bijvoorbeeld bijzonder onaangenaam voor een hartpatiënt onder observatie, die hierdoor een paar dagen aan een ziekenhuisbed is gekluisterd.
Gedeelde middelen
Doordat de sensoren de metingen voor verwerking versturen naar
een vooraf gede nieerde centrale plaats, is het bijna onmogelijk om sensoren te delen tussen toepassingen. Beschouw bij wijze van voorbeeld het verwarmingssysteem en het air conditioningsysteem in een gebouw. Beide systemen hebben temperatuurmetingen nodig. Er is geen enkele reden waarom die metingen niet door dezelfde temperatuursensoren kunnen verzameld worden. Toch hebben beide systemen vaak hun eigen sensoren die de opgemeten temperatuur doorsturen naar de centrale computer van het systeem waartoe ze behoren.
1.2
Wat zijn sensornetwerken?
Draadloze sensornetwerken proberen een oplossing te bieden voor de problemen van klassieke sensorsystemen.
Tegelijkertijd creëren ze nieuwe mogelijkheden die nuttig kunnen worden
aangewend. David Culler en Wei Hong beschrijven sensornetwerken als volgt [9]: Sensor networks provide a new kind of instrument - call it a macroscope that enables us to observe and interact with physical phenomena in real time at a delity that was previously unobtainable.
Nauwkeurigheid
Met sensornetwerken kan een veel grotere nauwkeurigheid worden beko-
men dan voorheen omdat de sensorknopen dicht bij het te meten fenomeen worden geplaatst.
HOOFDSTUK 1.
3
INLEIDING
Deze sensorknopen zijn, in tegenstelling tot de sensoren in een klassiek sensorsysteem, voorzien van een eigen verwerkingseenheid. Om de nauwkeurigheid nog op te drijven, bestaat een sensornetwerk soms uit heel veel knopen, mogelijks enkele duizenden.
Kostprijs
Om de kostprijs van dergelijke grote sensornetwerken te beperken, zijn de sen-
sorknopen beperkt in hun mogelijkheden. De rekenkracht, opslagcapaciteit en communicatiesnelheden zijn beperkt tot het absolute minimum.
Mobiliteit
Om mobiliteit van de sensorknopen toe te laten, is het communicatienetwerk
draadloos en is de energievoorziening op de sensorknopen zelf aanwezig. Meestal gaat het om een batterij, maar ook andere technologieën zoals zonne-energie zijn mogelijk. Vanzelfsprekend zijn deze energievoorzieningen beperkt en in het geval van een batterij ook eindig.
Gedeelde middelen buitenwereld.
Een sensornetwerk staat op zichzelf en biedt zijn diensten aan aan de
Dit laat toe dat meerdere applicaties gebruik maken van dezelfde sensornet-
werkinfrastructuur. De middelen die een sensornetwerk ter beschikking heeft worden zo op een eenvoudige manier gedeeld.
1.2.1
Fundamentele vereisten
Als gevolg van de uiterst beperkte middelen is
e ciëntie een belangrijke vereiste voor sensor-
netwerksystemen. De uitvoeringsmechanismen, algoritmes, gegevensmodellen en protocollen moeten e ciënt gebruik maken van de uitvoeringstijd, het geheugen en de bandbreedte. Niet alleen de middelen zijn beperkt, maar ook de beschikbare energie om deze middelen te laten werken is klein en in sommige gevallen eindig. Om een langdurige, robuuste werking te garanderen, is
energiebewustheid daarom een belangrijk aandachtspunt bij de ontwikkeling
van sensornetwerken. De mobiliteit van de sensorknopen en de instabiele aard van draadloze netwerken vereisen een
dynamische netwerkorganisatie.
De netwerkprotocollen moeten rekening houden met
de variabele posities van de sensorknopen. De protocollen moeten ook robuust werken wanneer de connectiviteit in een deel van het netwerk vermindert of wegvalt. Tenslotte is
zelforganisatie een vereiste om autonoom te kunnen werken.
Het sensornet-
werk moet zonder tussenkomst van buitenaf in staat zijn zichzelf te organiseren zodat het zijn diensten kan aanbieden.
1.2.2
Ad hoc netwerken
Een ad hoc netwerk is een netwerk waarin de toestellen rechtstreeks met elkaar communiceren zonder de hulp van infrastructuur. In een mobiel ad hoc netwerk (MANET) bewegen de knopen willekeurig waardoor de netwerktopologie snel en onvoorspelbaar kan wijzigen. Dergelijke netwerken kunnen op zichzelf staan of kunnen verbonden zijn met het Internet. Een sensornetwerk voldoet aan de de nitie van een MANET. Toch zijn er enkele duidelijke verschillen ten opzichte van de traditionele MANETs die ervoor zorgen dat de netwerkprotocollen die daar worden gebruikt niet zonder meer toepasbaar zijn bij sensornetwerken. Het aantal knopen in een sensornetwerk is veel groter dan bij de traditionele ad hoc netwerken van laptops, pda's, spelconsoles, . . . Daarenboven zijn de middelen die de sensorknopen ter beschikking hebben veel kleiner. De grote knoopdichtheid en de beperkte middelen maken
HOOFDSTUK 1.
4
INLEIDING
het minder makkelijk om bijvoorbeeld ooding, een techniek die in traditionele MANETs vaak gebruikt wordt, toe te passen voor de ontdekking van knopen en diensten. De grote omvang van sensornetwerken en de beperkte opslagcapaciteit op de knopen maakt het bovendien haast onmogelijk om een globaal beeld van het netwerk op te bouwen. De mobiliteit van de knopen in een traditioneel MANET is in de praktijk meestal beperkt. Eens een laptopgebruiker zich heeft geïnstalleerd, zal hij zich niet zo vaak meer verplaatsen. Wijzigingen in de netwerktopologie zijn dan ook niet zo frequent. In sensornetwerken komt een grote mobiliteit echter wel voor. Samen met de grotere foutgevoeligheid van de sensorknopen zorgt dit voor een nog dynamischer netwerktopologie dan in traditionele MANETs. Tenslotte zijn de individuele knopen in een traditioneel MANET van groter belang dan bij een sensornetwerk. De knopen in een traditioneel MANET communiceren op individuele basis met elkaar en de buitenwereld. In een sensornetwerk is dit minder expliciet. De knopen werken samen om op basis van de verzamelde meetgegevens één of meerdere diensten aan de buitenwereld aan te bieden. Voor de buitenwereld is een sensornetwerk dan ook eerder één geheel dan een verzameling van knopen.
1.3
Toepassingen
Sensornetwerken kunnen gebruikt worden in een groot aantal domeinen [3].
Militaire toe-
passingen, toepassingen i.v.m. het leefmilieu, medische toepassingen, domotica, logistiek en transport . . . Dit zijn slechts enkele van de mogelijkheden. De eerste ontwikkelingen rond sensornetwerken kwamen uit militaire hoek. Sensornetwerken kunnen er gebruikt worden voor een heel gamma toepassingen. Observatie van troepen, uitrusting en munitie met behulp van sensornetwerken kan het werk van o cieren vergemakkelijken.
Sensornetwerken kunnen interessante terreinen in de gaten houden en belangrijke
informatie verstrekken over vijandelijke bewegingen.
Besturingen van intelligente munitie
kunnen sensornetwerken gebruiken om hun nauwkeurigheid te verhogen. Ook in burgerlijke toepassingen bewijzen sensornetwerken hun nut. Ze kunnen bijvoorbeeld gebruikt worden om de toestand van grote bouwwerken, zoals bruggen of wolkenkrabbers te observeren [8]. Dergelijke sensornetwerken houden voortdurend de structurele integriteit van het bouwwerk in het oog en kunnen zo bijdragen tot een snellere opsporing van bijvoorbeeld scheurvorming. Sensornetwerken kunnen ook nuttig gebruikt worden voor toepassingen i.v.m. het leefmilieu. In droge, bosrijke gebieden kunnen sensornetwerken snel brandhaarden opsporen en zo de verspreiding van bosbranden helpen voorkomen door de reactietijd van de hulpdiensten te verlagen. Onderzoekers gebruiken sensornetwerken om gegevens te verzamelen voor onderzoek naar verschillende natuurfenomenen, bijvoorbeeld vulkanen [41]. In de medische wereld worden sensornetwerken gebruikt voor observatie van patiënten. Een hartpatiënt hoeft zo niet langer dagen in een ziekenhuisbed door te brengen. Sensornetwerken kunnen ook helpen om personeel en patiënten in een ziekenhuis te traceren of om het beheer van de voorraad geneesmiddelen te vergemakkelijken. In een doorsnee huis zijn de toepassingen van sensornetwerken vooral gericht op automatisatie.
Domoticasystemen maken handig gebruik van sensornetwerken om gegevens te
verzamelen. Sensornetwerken kunnen ook helpen bij het verwezenlijken van de intelligente omgeving.
HOOFDSTUK 1.
5
INLEIDING
Een sensornetwerk aanbrengen in een groot gebouw opent tal van mogelijkheden voor het gebruik ervan.
De beveiligingsapplicatie kan er interessante voorwerpen mee traceren
als onderdeel van de diefstalpreventie. Zowel de verwarming als het air conditioningsysteem kunnen via het sensornetwerk gegevens opvragen over de temperatuur en de vochtigheidsgraad in de verschillende ruimtes. Deze toepassingen geven een voorsmaak van de mogelijkheden, er zijn echter nog tal van andere toepassingen denkbaar in deze en andere domeinen. Voor elke toepassing waar gegevens moeten worden verzameld over de omgeving komen sensornetwerken in aanmerking als deel van de oplossing.
1.4
Motivatie van de thesis
Het is duidelijk dat sensornetwerken kunnen ingezet worden in tal van toepassingen. zullen ze worden geïntegreerd in dienstenplatformen.
Vaak
Het sensornetwerk in een kantoorge-
bouw maakt bijvoorbeeld deel uit van de dienstverlening van een beveiligings rma. Ook de onderhouds rma integreert het sensornetwerk in haar dienstverlening.
De leverancier van
nutsvoorzieningen kan een gas-, water- en elektriciteitsmeter in het sensornetwerk integreren en zo haar dienstverlening van op afstand verzorgen. Door de integratie in dienstenplatformen krijgen sensornetwerkapplicaties een end-to-end karakter.
Een applicatieserver bij de dienstverlener communiceert via de traditionele net-
werkinfrastructuur met het sensornetwerk bij een klant.
Deze communicatie wordt moge-
lijk gemaakt door een gateway te voorzien die de brug vormt tussen het sensornetwerk en de traditionele netwerkinfrastructuur. Deze gateway functionaliteit kan in speciale gateway sensorknopen worden voorzien, maar ook een onderdeel van de traditionele infrastructuur, bijvoorbeeld een ADSL-modem, kan deze taak op zich nemen. De diensten waarvoor een sensornetwerk wordt ingezet zijn zeer gevarieerd en kunnen uiteraard evolueren in de tijd. Een sensornetwerk moet hierop voorzien zijn en in staat zijn mee te evolueren.
Een belangrijke factor hierbij is de mogelijkheid om de software op het
sensornetwerk dynamisch aan te passen.
Dit is nodig om de bestaande diensten van het
sensornetwerk te laten evolueren en nieuwe diensten te operationaliseren. Om toe te laten dat dienstverleners op een makkelijke manier hun diensten kunnen wijzigen of nieuwe diensten kunnen operationaliseren, moet er een middleware komen die zoveel mogelijk abstractie maakt van de hardware en de dienstverleners zo goed mogelijk ondersteunt door zoveel mogelijk generieke componenten aan te bieden. Om tot zo'n middleware te komen is nog veel onderzoek nodig. Deze thesis zet een eerste stap in de richting van zo'n middleware. Er wordt onderzocht hoe de software op een sensorknoop van buitenaf kan worden aangepast. Deze thesis toont aan dat dit soort exibiliteit kan bekomen worden met dynamisch aanpasbare virtuele machines.
1.5
Doelstellingen
Om de evolutie in de diensten die een sensornetwerk aanbiedt te kunnen volgen, moet de software op de sensorknopen kunnen aangepast worden.
Figuur 1.1 toont een vergelijking
tussen bestaande aanpakken voor dynamische updates en positioneert de aanpak die deze thesis voorstelt.
HOOFDSTUK 1.
6
INLEIDING
Figuur 1.1: Positionering van een dynamisch aanpasbare virtuele machine ten opzichte van bestaande aanpakken voor updates
De manier waarop dynamische updates worden ondersteund, is een afweging tussen de exibiliteit en de kost van een update. Wanneer men het ganse systeem vervangt (monolitische systemen) kan men ook het ganse systeem wijzigen, wat zorgt voor een grote exibiliteit. De omvang van een dergelijke update is echter aanzienlijk, wat ervoor zorgt dat de verspreiding in het netwerk veel energie vraagt. Aan het andere uiteinde vindt men de systemen die toelaten om parameters dynamisch te wijzigen.
Deze wijzigingen kunnen heel goedkoop gebeuren,
maar hebben een beperkte exibiliteit. Virtuele machines en modulaire systemen bevinden zich tussen deze twee uitersten. De virtuele machines bieden een geïnterpreteerde hoog niveau programmeerinterface waarmee het gedrag van de virtuele machine kan beïnvloed worden. Door de grote uitdrukkingskracht van de hoog niveau instructies, komt de kost om een update te versturen in de buurt van een parameterwijziging. De exibiliteit van het systeem is echter begrensd door de instructieset die de virtuele machine aanbiedt. Modulaire systemen laten toe om dynamisch uitvoerbare modules aan het systeem toe te voegen of uit het systeem te verwijderen. Deze aanpak ligt dichter in de buurt van de monolitische systemen voor zowel de exibiliteit als de kost van een update. De eerste doelstelling van deze thesis is de ontwikkeling van een hybride tussen virtuele machines en modulaire systemen:
een
dynamisch aanpasbare virtuele machine.
Een
dergelijke hybride combineert de voordelen van de modulaire systemen met die van de virtuele machines en biedt zo het beste van twee werelden. Voor wijzigingen die slechts een beperkte exibiliteit vereisen, bijvoorbeeld een kleine wijziging aan een bestaande dienstverlening, kan men gebruik maken van de hoog niveau interface van de virtuele machine.
Voor grotere
HOOFDSTUK 1.
7
INLEIDING
wijzigingen, die bijvoorbeeld nodig zijn om een nieuwe dienst te ondersteunen, past men de virtuele machine aan door een module toe te voegen of te verwijderen. Een tweede doelstelling van deze thesis is de ondersteuning van
chines op één sensorknoop.
meerdere virtuele ma-
Dit maakt het mogelijk om elke dienstverlener een eigen virtuele
machine ter beschikking te stellen. Op die manier worden de verschillende diensten op een sensornetwerk van elkaar geïsoleerd en kunnen zij elkaar niet hinderen.
1.6
Structuur van de tekst
De tekst is verder gestructureerd als volgt:
Hoofdstuk 2
bespreekt de verschillende sensorplatformen die beschikbaar zijn.
hardware als de besturingssystemen komen aan bod.
Zowel de
Vervolgens gaat het hoofdstuk
in op de drie manieren waarop een sensornetwerk bekeken kan worden: als individuele knopen, als een groep samenwerkende knopen en als een geïntegreerd dienstenplatform. Tenslotte wordt nagegaan hoe middleware in elk van deze gezichtspunten een nuttige bijdrage kan leveren.
Hoofdstuk 3
geeft het verschil aan tussen traditionele middleware en middleware voor sen-
sornetwerken. Daarna wordt ingegaan op de speci eke uitdagingen die in een middleware voor sensornetwerken moeten worden aangepakt. Het hoofdstuk gaat verder met een overzicht van de bestaande aanpakken die bij het ontwerpen van een middleware voor sensornetwerken worden gehanteerd.
Tenslotte geeft het hoofdstuk aan waarom dy-
namisch aanpasbare virtuele machines een goede onderzoekspiste zijn voor aanpasbare sensornetwerken.
Hoofdstuk 4
bespreekt Maté en Sensor Operating System (SOS). Maté is een bestaand
systeem dat toelaat virtuele machines te bouwen voor sensornetwerken. bouwt verder op het concept dat door Maté werd ontwikkeld.
Deze thesis
Om de verregaande
dynamische aanpasbaarheid te bekomen maakt deze thesis gebruik van het modulair besturingssysteem SOS.
Hoofdstuk 5
bakent de grenzen van het systeem af en gaat vervolgens op zoek naar welk
soort dynamische aanpasbaarheid nodig is om sensornetwerkapplicaties zo goed mogelijk te ondersteunen.
Dit mondt uit in functionele en niet-functionele vereisten voor het
systeem.
Hoofdstuk 6
presenteert de architectuur die ontwikkeld werd om aan de vereisten te voldoen.
Hoofdstuk 7
behandelt de prototype implementatie die werd gebouwd om de haalbaarheid
van de architectuur te valideren.
Hoofdstuk 8
vat de resultaten van de thesis samen en formuleert enkele conclusies. Er wordt
ook aangegeven waar verder onderzoek mogelijk is.
Hoofdstuk 2
Context Deze thesis zet een eerste stap in de richting van een aanpasbare middleware laag voor sensornetwerken. Deze middleware bevindt zich tussen het onderliggende platform en de sensornetwerkapplicatie. Dit hoofdstuk bespreekt de beschikbare platformen: de verschillende types en het hiërarchisch gebruik, de typische hardware en de besturingssystemen. Sectie 2.2 bekijkt vervolgens een sensornetwerk vanuit drie perspectieven. Tenslotte verduidelijkt Sectie 2.3 de rol van middleware in deze drie gezichtspunten.
2.1 2.1.1
Platformen Hiërarchie
De hardwareplatformen voor sensornetwerken variëren van speciaal ontwikkelde geïntegreerde schakelingen op millimeterschaal tot platformen van PDA-grootte. Het beperken van het energieverbruik is een kritiek aandachtspunt bij het ontwerp. In tegenstelling tot GSM's, PDA's en laptops is periodiek herladen van de energievoorzieningen vaak onmogelijk in sensornetwerken. De sensorknopen bevinden zich vaak jaren aan een stuk in een operationele opstelling zonder onderhoud of een andere vorm van menselijke interventie. Men kan de verschillende hardwareplatformen in vier klassen onderverdelen [20]. De gespecialiseerde sensorknopen worden ontworpen om zo klein en goedkoop mogelijk te zijn. Generische sensorknopen voorzien rijke uitbreidingsmogelijkheden om een exibele interactie met groepen eenvoudige sensoren mogelijk te maken. Breedbandsensorknopen hebben meer ingebouwde verwerkings- en communicatiemogelijkheden die het mogelijk maken complexe gegevensstromen, zoals video en spraak, te behandelen. Gateways tenslotte zijn voorzien van de hardware om een koppeling met de traditionele infrastructuur mogelijk te maken. De verschillende platformen worden typisch gebruikt in een hiërarchische opstelling (Figuur 2.1). Een voorbeeld is het best geschikt om dit te verduidelijken. We beschouwen het sensornetwerk in een kantoorgebouw dat onder andere gebruikt wordt voor de beveiliging van het gebouw.
Gespecialiseerde sensorknopen
Het beveiligingssysteem kan het sensornetwerk gebruiken
om mobiele voorwerpen of personeel te traceren. Op deze voorwerpen of personen wordt een sensorknoop van het gespecialiseerde type bevestigd. Deze kleine sensorknopen moeten heel lang kunnen overleven op heel weinig energie en moeten bovendien bijzonder klein en goedkoop
8
HOOFDSTUK 2.
9
CONTEXT
Figuur 2.1: Hiërarchisch gebruik van verschillende hardwareplatformen
gemaakt worden. Gespecialiseerde sensorknopen kunnen bijvoorbeeld gebruikt worden om te detecteren wanneer een voorwerp beweegt, iets wat kan wijzen op een diefstal. In tegenstelling tot RFID-tags (Radio Frequency Identi cation) hebben de gespecialiseerde sensorknopen een zekere intelligentie aan boord zodat ze zelf kunnen bepalen welke informatie ze doorsturen en wanneer ze dat doen.
RFID-tags daarentegen versturen altijd een unieke
identi catie wanneer ze in de buurt komen van een lezer. Deze lezer staat in voor de verwerking van deze informatie. Omdat de gespecialiseerde sensorknopen zelf intelligentie bevatten, worden ze ook wel eens intelligent stof (smart dust) [22] genoemd. Wanneer enkele knopen in het sensornetwerk worden uitgerust met een RFID-lezer kunnen de gegevens die de gespecialiseerde knopen verzamelen, worden aangevuld met RFID-gegevens om een voorwerp makkelijk te traceren wanneer een dief ermee door het gebouw beweegt.
Generische sensorknopen
De sensorknopen die op strategische plaatsen, zoals deuren
en ramen zijn aangebracht zijn van het generische type. speci ek.
Ze kunnen langdurig op batterijen overleven.
gingssensor aan boord om indringers te detecteren.
Hun taak is relatief eenvoudig en Ze hebben bijvoorbeeld een bewe-
Daarnaast hebben ze bijvoorbeeld een
contactsensor die detecteert wanneer een deur open gaat.
Breedbandsensorknopen
Een aantal knopen uit de breedband klasse worden voorzien
om geluiden en beelden te verwerken.
De rekenkracht op deze knopen is aanzienlijk groter
en soms is het nodig ze op het elektriciteitsnet aan te sluiten om hun langdurige werking te verzekeren. Deze knopen kunnen bijvoorbeeld gebruikt worden om personen te lokaliseren, of om bewijsmateriaal te verzamelen als een inbraak wordt vastgesteld door het systeem.
HOOFDSTUK 2.
10
CONTEXT
Klasse
Karakteristieken
Activiteitsgraad
Voorbeelden
Gespecia-
mm3 , <50Kbps radio, <5 MIPS, <0.1MiB Flash, <4KiB RAM 3 1-10cm , <100Kbps radio, <10 MIPS, <0.5MiB Flash, <10KiB RAM 3 1-10cm , 500Kbps radio, <50 MIPS, <10MiB Flash, <128KiB RAM >10cm3 , >500Kbps10Mbps, <100 MIPS, <32MiB Flash, <512KiB RAM
0.1-0.5%
Spec,
liseerd
Generisch
Breedband
Gateway
Human++
(IMEC),
sensoren
van ICSense 1-2%
Rene, MICA, MICA2,
Telos,
MI-
CAz
5-10%
BT Node, iMote
>50%
Stargate,
Inrysnc
Cerfcube,
PC104
nodes
Tabel 2.1: Karakteristieken van de vier klassen sensorknopen
Gateways
Het ganse sensornetwerk is met een aantal gateways verbonden met het lokale
netwerk van de beveiligingsdiensten van het gebouw.
Deze gateways zijn in staat om te
communiceren met zowel de andere knopen in het sensornetwerk als met de machines op het lokale netwerk. De middelen op deze systemen zijn een pak groter dan wat er op de andere knopen voor handen is.
Daardoor kunnen ze bijvoorbeeld ook een webapplicatie voor de
controle van het sensornetwerk aanbieden aan de computers op het lokale netwerk van de beveiligings rma.
2.1.2
Hardware karakteristieken
Tabel 2.1 toont de typische karakteristieken van de verschillende klassen en enkele voorbeelden van hardwareontwerpen in elk van de klassen.
De mogelijkheden van de platformen zullen
ongetwijfeld toenemen naarmate de technologie vordert. Het is echter zeer waarschijnlijk dat de vier klassen zullen blijven bestaan. Een belangrijk verschil met de traditionele platformen zoals pc's, PDA's en zelfs geïntegreerde systemen, is de extreme nadruk op energiebeheer. Om de energie e ciënt te kunnen beheren, kan elk onderdeel van het platform afzonderlijk worden in- en uitgeschakeld. Het heeft bijvoorbeeld enkel zin om de radio aan te schakelen tijdens actieve communicatie. Daarnaast is het ook mogelijk om de CPU uit te schakelen tijdens inactieve periodes. Tenslotte kunnen de sensor- en invoer/uitvoer-systemen uitgeschakeld worden als zij niet worden gebruikt.
2.1.3
Besturingssystemen
De belangrijkste taken van een sensornetwerkbesturingssysteem zijn energiebeheer en virtualisatie van verwerkings- en communicatiemiddelen.
Het besturingssysteem controleert de
activiteit en energietoestand van de verschillende subsystemen. Het beslist wanneer en voor hoe lang bepaalde subsystemen in een slaaptoestand worden gebracht.
Daarnaast voorziet
HOOFDSTUK 2.
11
CONTEXT
het besturingssysteem een zekere afscherming van de hardware om de overdraagbaarheid te garanderen en applicatieontwikkeling te vergemakkelijken. Dit gebeurt echter zonder de mogelijkheid tot precieze controle over de hardware op te geven. Dit is nodig om een hoge e ciëntie toe te laten. Het besturingssysteem moet uiteraard aangepast zijn aan de mogelijkheden van het platform. Naarmate de mogelijkheden van de hardware toenemen, stijgt de nood aan geavanceerde systeemdiensten, zoals die door traditionele besturingssystemen worden aangeboden. De ondersteuning voor precieze controle van de hardware ontbreekt echter meestal in deze besturingssystemen. De breedbandknopen en de gateways draaien dan ook meestal een gewijzigde vorm van een traditioneel besturingssysteem, bijvoorbeeld een gewijzigde linuxkernel.
Een klassiek sensorbesturingssysteem De taken die de gespecialiseerde en de generische knopen uitvoeren op hun beperkte hardware hebben minder nood aan geavanceerde systeemdiensten. Bovendien is het hardwareplatform zo speci ek dat traditionele besturingssystemen er niet kunnen op werken.
Men gebruikt
hiervoor dan ook een speciaal sensorbesturingssysteem. TinyOS [26] was één van de eerste besturingssystemen voor deze types sensorknopen en is nog steeds de de facto standaard. Andere besturingssystemen die voor deze klassen sensorknopen werden ontwikkeld bieden vaak gelijkaardige mechanismen en abstracties.
Uitvoeringsmodel
Een gebeurtenisgebaseerd uitvoeringsmodel past het best bij de modus
operandi van de meeste sensorknopen. Sensorknopen verwerken meestal meerdere informatiestromen tegelijkertijd. De berekeningen zijn daarbij eerder beperkt. De beperkte opslagcapaciteit zorgt ervoor dat de informatie verwerkt moet worden zodra ze beschikbaar wordt. Een gebeurtenisgebaseerd uitvoeringsmodel voorziet geen blokkerende operaties. De operaties zijn daarom opgesplitst in twee fasen: een niet-blokkerende aanvraag gevolgd door een gebeurtenis die het einde van de operatie signaleert. Dit mechanisme laat toe om meerdere parallelle activiteiten te ondersteunen met één stapel.
Modulariteit
Een modulaire opbouw laat toe dat het systeem aangepast wordt aan de
heterogeniteit van de hardware terwijl het voor applicaties toch mogelijk blijft om gebruik te maken van gemeenschappelijke softwarediensten en abstracties.
De modulariteit is vaak
gebaseerd op een componentmodel. Een component heeft meestal een speci eke taak en houdt ook alle toestandsinformatie bij die hiervoor nodig is. Een applicatie wordt dan samengesteld uit verschillende componenten die op een welbepaalde manier met elkaar interageren.
Systeemdiensten
De set systeemdiensten is meestal niet vast bepaald.
De applicaties
kunnen de systeemdiensten en hun implementatie zelf bepalen door de geschikte componenten op te nemen. Door deze aanpak vervaagt de grens tussen het systeem en de applicaties. Er kan echter wel een set systeemdiensten worden geïdenti ceerd die door bijna elke applicatie wordt gebruikt: timers, dataverzameling, energiebeheer en netwerkmogelijkheden. Deze set weerspiegelt de basisvereisten van een sensornetwerk: met beperkte energie periodiek gegevens verzamelen, eenvoudige verwerking ervan en, indien nodig, communicatie van de gegevens naar naburige knopen.
HOOFDSTUK 2.
12
CONTEXT
Statische optimalisatie
Een sensornetwerkbesturingssysteem wordt meestal samen met
een applicatie gecompileerd tot één binaire afbeelding (image). Dit laat toe het geheel statisch te optimaliseren en het benodigde geheugen statisch te alloceren. Deze monolitische aanpak is typisch voor de meeste geïntegreerde systemen.
Recentere aanpakken Recent zijn in de literatuur besturingssystemen verschenen die een andere aanpak hanteren dan de klassieke sensorbesturingssystemen. Deze afwijkingen situeren zich enerzijds bij het uitvoeringsmodel, anderzijds wordt de statische aanpak verlaten.
Threadgebaseerde uitvoeringsmodellen
Een gebeurtenisgebaseerd uitvoeringsmodel is
een natuurlijke manier voor reactieve berekeningen en interacties met hardware.
Het zorgt
er echter voor dat hoog niveau operaties ingewikkeld worden. Een sequentie die logisch gezien blokkerend is, moet namelijk geschreven worden op een manier die gelijkaardig is aan toestandsmachines. Om hieraan tegemoet te komen zijn besturingssystemen ontwikkeld met een threadgebaseerd uitvoeringsmodel. Dit type uitvoeringsmodellen is beter geschikt voor hoog niveau blokkerende operaties. Mantis [2] is een voorbeeld van een besturingssysteem met preemptive multithreading als uitvoeringsmodel. Contiki [10] heeft een gebeurtenisgebaseerd uitvoeringsmodel, maar biedt een afgeslankte versie van threads voor hoog niveau operaties [11]. Daarnaast ondersteunt Contiki ook volwaardige preemptive multithreading via een optionele bibliotheek.
Dynamische modules
Als gevolg van de statische optimalisatie bij de klassieke sensorbe-
sturingssystemen blijft de modulariteit beperkt tot statische modulariteit. Eens het systeem gecompileerd is, is de modulariteit verdwenen. Dit vermoeilijkt de ondersteuning van meerdere applicaties en verhindert incrementele updates. Om hieraan tegemoet te komen werden er besturingssystemen ontwikkeld die opgebouwd zijn uit modules.
Deze modules kunnen tijdens de uitvoering van het systeem geladen of
verwijderd worden. Sensor Operating System (SOS) [17] en Contiki hanteren een dergelijke dynamische aanpak.
2.2
Drie gezichtspunten
Zijn sensornetwerken een hoop alleenstaande sensorknopen? Of zijn het eerder sensorknopen die samenwerken aan complexere opdrachten?
Misschien moeten we sensornetwerken wel
zien als geïntegreerde dienstverleners? Deze sectie geeft aan dat deze drie manieren om een sensornetwerk te bekijken niet los staan van elkaar en dat ze alledrie nuttig kunnen zijn.
2.2.1
De geïsoleerde sensorknoop
Een eerste manier waarop men naar een sensornetwerk kan kijken is als een verzameling alleenstaande knopen. aggregeren.
Een sensorknoop op zich is in staat gegevens te verzamelen en te
HOOFDSTUK 2.
13
CONTEXT
Gegevens verzamelen doet de sensorknoop met behulp van de aanwezige sensoren. Gegevens kunnen eenmalig opgemeten worden. Het is echter meestal interessanter dit op regelmatige basis te doen. Een deursensor uit het voorbeeld kan met behulp van zijn contactsensor nagaan of de deur open of dicht is. Om echter een oordeel te kunnen vellen over het tijdstip waarop de deur is opengegaan, moet periodiek de toestand van de deur worden bekeken. Aggregatie van de verzamelde gegevens is een tweede belangrijke mogelijkheid die een enkele sensor heeft. Het is bijvoorbeeld mogelijk om van een periodiek opgemeten gegeven het maximum of een tijdsgemiddelde te bepalen. Wanneer de deursensoren ook gebruikt worden door de onderhoudsdienst van het gebouw, is het bijvoorbeeld interessant om een schatting te hebben van het gemiddelde aantal keer dat een deur per dag open en dicht gaat.
Deze
informatie kan gebruikt worden om te bepalen hoe vaak de scharnieren een smeerbeurt nodig hebben.
2.2.2
Een sensorknoop als deel van het geheel
Sensornetwerken worden pas echt een netwerk als men ze bekijkt als een groep samenwerkende sensorknopen. De verzamelde gegevens kunnen nu langs verschillende knopen tot buiten het netwerk worden gebracht. De collaboratie tussen knopen opent echter ook andere interessante mogelijkheden. De verzamelde en geaggregeerde gegevens moeten natuurlijk meegedeeld kunnen worden voor ze enig nut hebben. Een sensorknoop zal met de andere sensorknopen samenwerken om verzamelde gegevens naar de buitenwereld te kunnen communiceren. Samen bouwen ze een netwerktopologie uit die toelaat gegevens naar een zeker punt te brengen. Een deursensor zal proberen zo snel mogelijk een beveiligingsagent te waarschuwen als een deur wordt geopend op een moment waarop normaal niemand nog in het gebouw aanwezig is. De deursensor werkt samen met de andere knopen, zowel de generische als de breedbandknopen, om de waarschuwing via een gatewayknoop naar het lokale netwerk van de beveiligings rma te communiceren. Samenwerking tussen knopen biedt naast communicatie nog tal van andere mogelijkheden. Verschillende sensoren in een kamer kunnen samen een gemiddelde temperatuur van de kamer bepalen.
De klimaatregeling van het gebouw kan hier eventueel gepast op reageren.
De
beveiliging heeft interessante voorwerpen voorzien van gespecialiseerde sensorknopen om ze te kunnen traceren. Om tracering mogelijk te maken moeten deze tags samenwerken met andere knopen zoals de deur- en vensterknopen. Verschillende geluidssensoren kunnen door samenwerking een waargenomen geluid met een redelijke nauwkeurigheid lokaliseren.
2.2.3
Sensornetwerken als dienstverleners
Een sensornetwerk kan men ook bekijken als een geïntegreerd geheel dat zijn diensten aanbiedt aan de buitenwereld. De autonomie van het netwerk wordt in dit gezichtspunt heel belangrijk. Een sensornetwerk dat zich als autonome dienstverlener aan de buitenwereld presenteert maakt het makkelijker voor verschillende applicaties om gebruik te maken van hetzelfde sensornetwerk. Het sensornetwerk in het kantoorgebouw kan via zijn gatewayknopen diensten aanbieden aan het beveiligingssysteem, de klimaatregeling en het onderhoudssysteem van het gebouw. De diensten die aangeboden worden variëren daarom van het detecteren van activiteit en het traceren van voorwerpen voor het beveiligingssysteem, over het verzamelen van temperatuur-
HOOFDSTUK 2.
14
CONTEXT
gegevens voor de klimaatregeling, tot het in de gaten houden van de algemene toestand van deuren en ramen voor het onderhoudssysteem.
2.3
Middleware
In Sectie 2.2 kwamen drie manieren aan bod om naar een sensornetwerk te kijken. In deze sectie wordt duidelijk hoe middleware een rol speelt in deze drie gezichtpunten.
2.3.1
Middleware als aggregator
Het besturingssysteem op een sensorknoop regelt de werking van de hardware en voorziet basisabstracties die de hardware omvormen tot een bruikbaar platform. Het besturingssysteem is echter beperkt tot systeemdiensten die voor bijna elke applicatie nodig zijn. Functionaliteit die in veel applicaties nodig is, bijvoorbeeld voor de aggregatie van gegevens, wordt vaak in elke applicatie die ervan wenst gebruik te maken opgenomen.
Deze
functionaliteit wordt niet in het besturingssysteem opgenomen omdat ze niet algemeen genoeg is. Vaak hebben alleen een categorie van applicaties die functionaliteit nodig. Bovendien gaat het meestal om relatief hoog niveau functionaliteit die niet in een besturingssysteem thuishoort. De functionaliteit in de applicatie opnemen zorgt echter dikwijls voor duplicatie. Middleware kan hiervoor een oplossing bieden. De middleware wordt tussen het besturingssysteem en de applicaties geplaatst en kan dergelijke functionaliteit aanbieden. Dit vermijdt het dupliceren van die functionaliteit. Bovendien kan men makkelijker en sneller een applicatie ontwikkelen omdat men die functionaliteit niet opnieuw hoeft te implementeren. Daarnaast maakt deze aanpak het ook mogelijk een uniforme interface voor deze functionaliteit aan te bieden over verschillende platformen heen.
2.3.2
Middleware als coördinator
Samenwerking tussen sensorknopen biedt vele mogelijkheden, maar die samenwerking moet natuurlijk gecoördineerd worden. Het gedistribueerde karakter van deze coördinatie maakt dat het besturingssysteem niet de geschikte plaats is om deze functionaliteit te implementeren. De breedbandknopen en gateways gebruiken namelijk vaak een ander besturingssysteem dan de generische en gespecialiseerde knopen. Elke applicatie kan zelf de coördinatie verzorgen, maar dit zorgt opnieuw voor duplicatie van de functionaliteit. Ook hier kan middleware voor een oplossing zorgen.
De middleware verzorgt coördina-
tiediensten waarvan de applicaties gebruik kunnen maken. De middleware biedt bijvoorbeeld een dienst aan die tijdssynchronisatie tussen de knopen verzorgt.
Verschillende applicaties
kunnen vervolgens van de dienst gebruik maken om het klokverschil met hun buren te weten te komen.
2.3.3
Middleware als integrator
Een geïntegreerd netwerk moet in staat zijn zich naar de buitenwereld voor te doen als één geheel. Deze integratie vereist een abstractie van de individuele knopen en hun interacties. De buitenwereld is alleen geïnteresseerd in de diensten die worden aangeboden, niet in de manier waarop deze diensten tot stand komen.
HOOFDSTUK 2.
CONTEXT
15
Verschillende applicaties willen hun diensten aan de buitenwereld aanbieden. Middleware kan de ontwikkeling van deze applicaties vergemakkelijken en versnellen door een dienstgericht raamwerk te voorzien.
De middleware lost zo een aantal problemen bij het aanbieden van
diensten eens en voor altijd op. De applicaties kunnen deze functionaliteit daarna gebruiken om hun diensten beschikbaar te maken. De eindgebruikerapplicaties op de traditionele infrastructuur die de diensten van het sensornetwerk willen gebruiken nemen contact op met een gateway om te weten te komen welke diensten er beschikbaar zijn en om er gebruik van te maken.
Op de gateway worden deze
diensten geadverteerd en kan een dienst geïnitieerd worden. Deze interacties tussen de eindgebruikerapplicaties en het sensornetwerk kunnen eveneens via middleware verlopen.
Deze middleware is dan bedoeld om het aanspreken van één of
meerdere sensornetwerken makkelijker te maken voor de ontwikkelaars van de eindgebruikerapplicaties.
Hoofdstuk 3
Middleware voor sensornetwerken Sectie 2.3 verduidelijkt welke functies middleware kan vervullen in een sensornetwerk. Middlewaresystemen voor sensornetwerken delen een aantal doelstellingen met traditionele middlewaresystemen. Er zijn echter ook een aantal fundamentele verschillen. Traditionele middlewaresystemen kunnen een bron van inspiratie zijn, maar de verschillen zorgen voor een aantal typische uitdagingen bij de ontwikkeling van middleware voor sensornetwerken. De literatuur beschrijft talrijke middlewaresystemen die proberen deze uitdagingen zo goed mogelijk in te vullen. Sectie 3.3 geeft een overzicht zoals het in [15] wordt aangebracht. Deze thesis focust op (dynamische) aanpasbaarheid in sensornetwerken.
Sectie 3.4 schetst de plaats van deze
thesis in het algemene kader.
3.1
Traditionele middlewaresystemen
Traditionele gedistribueerde middleware is systeemsoftware die tussen de applicaties en de onderliggende besturingssystemen en netwerken wordt geplaatst en herbruikbare diensten aanbiedt die samengesteld, gecon gureerd en geoperationaliseerd kunnen worden om snel en robuust netwerkapplicaties te maken [6]. Middleware vervult meestal de volgende functies:
•
Het verbergen van het gedistribueerde karakter zodat applicaties transparant kunnen geplaatst worden over het netwerk.
•
Het verbergen van de heterogeniteit van de onderliggende platformen en netwerken. Op die manier worden de applicaties onafhankelijk van het onderliggende platform of netwerk.
•
Het voorzien van een uniforme, hoog niveau interface voor de applicatieontwikkelaars en -integrators, zodat applicaties makkelijker kunnen worden samengesteld, hergebruikt, geport en interoperabel gemaakt.
•
Het voorzien van een aantal gemeenschappelijke diensten om algemeen bruikbare functionaliteit uit te voeren. Zodoende wordt duplicatie vermeden en samenwerking tussen applicaties vergemakkelijkt.
De toenemende belangstelling voor commerciële kant en klare hardware (COTS, commercial o-the-shelve) en de verhoogde maturiteit van programmeertalen hebben gezorgd voor
16
HOOFDSTUK 3.
17
MIDDLEWARE VOOR SENSORNETWERKEN
toenemende belangstelling in COTS software componenten en architecturen. Verbeteringen in software raamwerken, componentmodellen, patronen en ontwikkelingsprocessen hebben het mogelijk gemaakt COTS middleware te ontwikkelen die nu succesvol wordt gebruikt in tal van domeinen. Middleware voor sensornetwerken deelt een aantal van de doelstellingen van deze COTS middleware.
Ze proberen eveneens herbruikbare diensten aan te bieden en de ontwikkeling
van sensornetwerkapplicaties te vergemakkelijken en te versnellen. COTS middleware systemen gaan er echter meestal van uit dat er statische connectiviteit, betrouwbare communicatiekanalen en relatief hoge bandbreedte voor handen zijn. Deze veronderstellingen gelden niet langer bij sensornetwerken. Bovendien is het veel moeilijker en in veel gevallen onwenselijk om de volledige netwerktopologie te verbergen voor de applicatieontwikkelaar. Er schuilen daarom nog een aanzienlijk aantal uitdagingen (zie Sectie 3.2) in de ontwikkeling van middleware voor exibele netwerkomgevingen zoals sensornetwerken.
3.2
De uitdagingen
In de literatuur [7, 35, 15] worden een hele resem uitdagingen geformuleerd waaraan middleware systemen voor sensornetwerken moeten voldoen. Deze uitdagingen zijn gedicteerd door enerzijds de karakteristieken van sensornetwerken en anderzijds door de aard van sensornetwerkapplicaties.
Omgaan met de beperkte energie en middelen De beschikbare energie en middelen in een sensornetwerk zijn beperkt tot het absolute minimum. De middleware moet in staat zijn hiermee om te gaan. E ciëntie en energiebewustheid blijven dus ook voor de middleware belangrijke aandachtspunten.
Ze kan hiervoor echter
deels gebruik maken van de diensten voor energiebeheer die het besturingssysteem aanbiedt. De middleware moet toelaten om de basisoperaties -meten, verwerken, communiceren- uit te voeren zonder dat de middelen daarbij worden uitgeput. Bij de hardwareplatformen die in sensornetwerken worden gebruikt, is er relatief gezien veel meer energie nodig om te communiceren dan om te rekenen. Het is dus wenselijk dat de middleware zoveel mogelijk gebruik maakt van lokale algoritmes. Lokale algoritmes communiceren enkel met de nabijgelegen sensorknopen.
Schaalbaarheid Sensornetwerken kunnen heel groot worden. De performantie van het netwerk moet binnen aanvaardbare grenzen blijven als het aantal knopen groeit of de afstand tussen de knopen kleiner wordt. De middleware moet de groei van een sensornetwerk kunnen opvangen zonder de performantie signi cant te beïnvloeden. Een ander aspect van de schaalbaarheid is de mate waarin het mogelijk is om enkel de essentiële delen van de middleware op te nemen. Zo wordt het mogelijk in een operationele opstelling een middleware te voorzien die alleen ondersteunt wat de applicaties echt nodig hebben. Dergelijke minimalisatie van de middleware draagt bij tot de e ciëntie (in geheugengebruik).
HOOFDSTUK 3.
18
MIDDLEWARE VOOR SENSORNETWERKEN
Kennis van het applicatiedomein De middleware in een sensornetwerk moet toelaten dat kennis over het applicatiedomein geïnjecteerd wordt.
Deze openheid laat de applicatieontwikkelaar bijvoorbeeld toe om de com-
municatienoden van de applicatie te mappen op netwerkparameters.
De mate waarin de
middleware generisch is -de mate waarin men de middleware kan aanpassen aan de applicatie in plaats van omgekeerd- bepaalt ook mee te schaalbaarheid van de middleware. Het is echter belangrijk te onthouden dat middleware bedoeld is om een rijke variatie applicaties te ondersteunen. Er moet onvermijdelijk een afweging gemaakt worden tussen de graad van applicatiespeci citeit en algemeenheid van de middleware.
Heterogeniteit De hardware in een sensornetwerk is zeer heterogeen. Zelfs binnen de vier klassen (zie Sectie 2.1.2) zijn verschillende ontwerpen beschikbaar. Om de mogelijkheden ten volle te benutten is het vaak noodzakelijk om de hardware via een laag niveau interface aan te spreken. De middleware moet allereerst in staat zijn haar werk te doen op de verscheidene hardware systemen. Daarnaast moet ze toelaten het ruwe potentieel van de hardware zo goed mogelijk te benutten. Het is ook belangrijk dat de middleware zo veel mogelijk onafhankelijk is van het onderliggende platform. De middleware wordt een stuk bruikbaarder als de overdraagbaarheid groot is. Ze is dan namelijk makkelijker toepasbaar in het ganse sensornetwerk. Dit laat een eenvoudige en snelle operationalisering toe.
Mobiliteit en dynamische netwerkorganisatie De mobiliteit van sensorknopen is een grote troef van sensornetwerken. Vanzelfsprekend moet de middleware deze mobiliteit toelaten en ondersteunen. Mobiliteit van sensorknopen geeft onvermijdelijk aanleiding tot een dynamische netwerktopologie. Ook de draadloze aard van het communicatienetwerk geeft aanleiding tot wisselende connectiviteit. Bovendien is het een essentiële eigenschap van draadloze sensornetwerken dat de topologie van het communicatienetwerk niet op voorhand bepaald is. De organisatie van het netwerk moet ook dynamisch aangepast kunnen worden aan de toestand van het netwerk. Het is bijvoorbeeld een slecht idee om berichten naar de gateways steeds te routeren langs dezelfde knopen. aanwezige energie in deze knopen.
Dit zou al snel leiden tot de uitputting van de
De middleware moet daarom bij de organisatie van het
netwerk rekening houden met de energietoestand en de andere beschikbare middelen van de individuele knopen.
Integratie in de reële wereld Om een grote nauwkeurigheid te bekomen zijn sensornetwerken heel sterk geïntegreerd in de reële wereld. Ze moeten dan ook in staat zijn in reële tijd met hun omgeving te interageren. Op het verkeerde moment reageren op gebeurtenissen in de omgeving kan een negatieve invloed hebben op de nauwkeurigheid en de consistentie van de resultaten. daarom diensten aanbieden in reële tijd.
De middleware moet
HOOFDSTUK 3.
19
MIDDLEWARE VOOR SENSORNETWERKEN
Belang van de data De densiteit van de knopen laat een grote nauwkeurigheid van de gemeten waarden toe. Ze veroorzaakt echter ook redundantie in de gemeten waarden van de sensorknopen in elkaars buurt. Aggregatie van de data vermindert deze redundantie en reduceert zo het energieverbruik voor het communiceren van overtollige gegevens. De fenomenen die door het sensornetwerk worden geobserveerd zijn voor de applicaties van cruciaal belang. Het sensornetwerk is slechts een middel, niet het doel. In sensornetwerkapplicaties is het centrale punt dikwijls de gegevens die door het sensornetwerk bekomen worden, eerder dan het netwerk zelf. De data moet daarom ook voor de middleware van groot belang zijn.
Datagebaseerde
communicatie, in tegenstelling tot adresgebaseerde communicatie, kan hierbij een belangrijke rol spelen. Op die manier is de data het centrale punt van de communicatie. De afzender en bestemmeling zijn minder van belang.
Kwaliteit van de dienstverlening Kwaliteit van de dienstverlening (Quality of Service - QoS) heeft bij sensornetwerken twee componenten. Ten eerste moet de goede werking van het netwerk gedurende lange tijd gegarandeerd worden. Ten tweede moet de kwaliteit van de resultaten aangepast kunnen worden aan de benodigde kwaliteit. Dit heeft op zijn beurt gevolgen voor de levensduur van het netwerk. In veel gevallen neemt de nauwkeurigheid van het resultaat toe naarmate er meer wordt gecommuniceerd. Veel communicatie heeft echter een onvermijdelijke negatieve impact op de levensduur van het netwerk en de snelheid waarmee het antwoord afgeleverd kan worden. Deze extra communicatie is zinloos als de applicatie de hoge nauwkeurigheid niet nodig heeft. De middleware moet de langdurige goede werking van een sensornetwerk bevorderen. Dit komt in grote mate neer op het beperken van het onnodige energieverbruik. Het is dus wenselijk dat de nauwkeurigheid van een resultaat kan afgewogen worden tegen het energieverbruik en de snelheid van het antwoord.
Veiligheid Sensornetwerken worden ook gebruikt om gevoelige gegevens te verzamelen. Denken we bijvoorbeeld aan de eerder geschetste toepassingen in de medische of militaire sector (Sectie 1.3). Het is belangrijk dat deze gegevens beschermd worden. Door de aard van de gebieden waarin sensornetwerken worden gebruikt, zijn ze vaak kwetsbaar voor intrusies of denial of service aanvallen. Daarenboven maakt het draadloze medium a uisteren van de communicatie makkelijker. Het is duidelijk dat beveiliging ook in sensornetwerken belangrijk is. De klassieke beveiligingstechnieken zijn echter vaak onbruikbaar door de beperkte middelen op de sensorknopen. Beveiliging wordt dus best van bij het begin van een middleware ontwerp in rekening gebracht.
Zo kunnen con dentialiteit, authenticatie, integriteit, versheid en beschikbaarheid
beter worden aangepakt.
3.3
Verschillende aanpakken
Er zijn veel verschillende aanpakken mogelijk om de uitdagingen uit Sectie 3.2 te realiseren. In de literatuur zijn dan ook tal van middleware systemen beschreven. Figuur 3.1 toont een
HOOFDSTUK 3.
20
MIDDLEWARE VOOR SENSORNETWERKEN
Figuur 3.1: Een mogelijke taxonomie voor de classi catie van middlewaresystemen
mogelijke taxonomie voor de classi catie van deze talrijke systemen [15]. De systemen worden hierbij onderverdeeld volgens de programmeerondersteuning of -abstracties die ze aanbieden. Dit is zeker niet de enige mogelijke opdeling. De systemen in de deelboom programmeerondersteuning van Figuur 3.1 leggen een grotere nadruk op een zekere programmeertechniek en de bijhorende ondersteuning van de applicatieprogrammeur. De systemen die gerangschikt worden onder programmeerabstractie benadrukken sterker de manier waarop naar het netwerk gekeken wordt. is vaak dun.
De grens tussen beide
Een programmeerondersteuning kan een kijk op het netwerk suggereren, een
programmeerabstractie maakt een zekere manier van programmeren makkelijker.
3.3.1
Programmeerondersteuning
Virtuele machine De sensornetwerkapplicaties binnen een toepassingsdomein gebruiken vaak dezelfde systeemdiensten en subsystemen, alleen zijn deze op een andere manier samengesteld. Virtuele machines voorzien een compacte manier om deze samenstelling aan te geven. Ze doen dit door de gemeenschappelijke subsystemen als bibliotheken van de virtuele machine te implementeren.
Deze bibliotheken kunnen vervolgens worden aangesproken via
een instructieset bestaande uit geïnterpreteerde bytecode. Deze techniek wordt overgenomen uit traditionele virtuele machines zoals de Java Virtuele Machine. Het spreekt voor zich dat dit op een heel e ciënte manier moet worden geïmplementeerd om te kunnen werken op de beperkte hardware van een sensorknoop. Verder wordt enkel de basistechniek overgenomen van de traditionele virtuele machines. Geavanceerde functionaliteit zoals onder meer garbage collection wordt weggelaten. De interpretatie van de instructies introduceert een zekere overhead. Bij toepassingen waar het netwerk frequent moet worden geherprogrammeerd, wordt het energieverlies gecompenseerd door de energiewinst bij het herprogrammeren. Door de compacte vorm die de bytecode biedt om applicaties te beschrijven vergt de verspreiding van een update veel minder energie. Naast compacte updates biedt deze aanpak nog enkele voordelen die kunnen toegeschreven worden aan het concept van virtuele machines. De hardware en het besturingssysteem worden geabstraheerd waardoor programma's voor de virtuele machine overgedragen kunnen worden naar een implementatie van de virtuele machine op een ander platform. Een virtuele machine kan daarnaast ook gebruikt worden om een veilige uitvoeringsomgeving te creëren. Een voorbeeld in deze categorie is Maté [25, 24].
HOOFDSTUK 3.
21
MIDDLEWARE VOOR SENSORNETWERKEN
Modulair programmeren Bij modulair programmeren worden de applicaties zo modulair mogelijk gemaakt. Dit vergemakkelijkt hun injectie en verspreiding in het netwerk onder de vorm van mobiele code. De omvang van een module is relatief klein waardoor het signi cant minder energie vraagt om een module te versturen dan om een volledige applicatie in het netwerk te verspreiden. Deze aanpak wordt onder meer gebruikt bij Impala [30].
Databank Het netwerk wordt in deze aanpak gezien als een virtuele databank. een gemakkelijk te gebruiken interface ondervraagd worden.
Het systeem kan via
De meeste systemen in deze
soort gebruiken hiervoor een SQL-achtige taal. Deze aanpak geeft echter meestal benaderende resultaten. Deze systemen zijn meestal ook niet in staat in reële tijd te werken. Daarvoor is het namelijk nodig om spatio-temporele relaties te leggen tussen gebeurtenissen. Cougar [44], TinyDB [31], SINA [37] en DsWare [28] vertegenwoordigen deze aanpak.
Applicatiegedreven De systemen in deze categorie hebben een architectuur die reikt tot de netwerk protocolstapel. Dit laat de applicatieprogrammeurs toe om het netwerk jn te regelen naar gelang hun behoeften. De applicaties bepalen hier in belangrijke mate de werking van het netwerk. Dit geeft voordelen voor de kwaliteit van de dienstverlening. Er schuilt echter ook een gevaar in de nauwe koppeling met de applicaties. Het gevaar bestaat dat de middleware te gespecialiseerd wordt en inboet op algemeenheid. Voorbeelden in deze categorie zijn Milan (Middleware Linking Applications and Networks) [19] en AutoSec (Automatic Service Composition) [18].
Berichtgeoriënteerd Berichtgeoriënteerde middleware gebruikt het publish-subscribe mechanisme om de communicatie tussen sensorknopen te vergemakkelijken. De grote kracht van dit mechanisme is de natuurlijke ondersteuning voor asynchrone communicatie. Dit laat een lage koppeling tussen de zender en de ontvanger van een bericht toe. In een omgeving waar de meeste toepassingen gebaseerd zijn op gebeurtenissen is dit mechanisme goed bruikbaar. Mires [36] is een voorbeeld van deze aanpak.
3.3.2
Programmeerabstractie
Globaal gedrag (macroprogrammeren) Bij deze aanpak programmeert men het sensornetwerk als één geheel. van het sensornetwerk wordt gespeci ceerd op hoog niveau.
Het globale gedrag
Het individuele gedrag van de
sensorknopen wordt daaruit automatisch afgeleid. Dit ontneemt de applicatieprogrammeurs de problemen bij het programmeren van het laag niveau gedrag van individuele knopen. In deze categorie vinden we onder andere Kairos [14], Regiment [32], Abstract Task Graph [4], Semantic Streams [43] en MagnetOS [5, 29].
HOOFDSTUK 3.
22
MIDDLEWARE VOOR SENSORNETWERKEN
Lokaal gedrag Veel sensornetwerkapplicaties zijn geïnteresseerd in de aard van de metingen. Dit gaat veel vaker over een gebied in het sensornetwerk dan over een individuele meting. Een applicatie zal bijvoorbeeld eerder geïnteresseerd zijn in een gebied waar de temperatuur een bepaalde waarde overschrijdt dan in een enkele temperatuurmeting. Deze regio's kunnen geometrisch of datagebaseerd zijn. In de datagebaseerde netwerken worden knopen geadresseerd volgens eigenschappen van de data die ze meten. In een traceerapplicatie zal men bijvoorbeeld spreken over alle knopen die voorwerp X op dit moment waarnemen. Abstract regions [40], EnviroTrack [1], Hood [42] en Generic role assignment [34] zijn allen voorbeelden van systemen met een lokale aanpak.
3.4
Situering thesis
Sectie 3.2 en Sectie 3.3 identi ceren de belangrijkste uitdagingen voor middleware voor sensornetwerken en de aanpakken die hiervoor worden beschreven in de literatuur. Deze sectie geeft aan waarom de focus van deze thesis vooral bij aanpasbaarheid ligt en hoe virtuele machines de gewenste aanpasbaarheid kunnen realiseren.
3.4.1
Aanpasbaarheid
Aanpasbaarheid is een aspect dat in meerdere uitdagingen uit Sectie 3.2 voorkomt. Het is een niet-functionele vereiste die tot ver in de software kan doordringen. Het is dan ook een goed idee om aanpasbaarheid te beredeneren op architectuurniveau [33, 13].
Dit maakt het een
stuk makkelijker om over wijzigingen na te denken. De wijzigingen kunnen in de architectuur op een consistente manier worden doorgevoerd. Daarna propageren ze naar het ontwerp en de implementatie. Men kan de aanpasbaarheid die nodig is in middleware voor sensornetwerken opsplitsen in twee categorieën: aanpasbaarheid aan de omstandigheden en aanpasbaarheid aan de applicatienoden. Daarnaast kan deze aanpasbaarheid zowel statisch als dynamisch zijn.
Aanpasbaarheid aan de omstandigheden
mische netwerkorganisatie en schaalbaarheid.
komt voort uit twee uitdagingen:
dyna-
Dynamische netwerkorganisatie vergt van de
middleware een grote mate van (zelf-)aanpasbaarheid aan de huidige toestand van het netwerk. Uit de schaalbaarheidsvereiste volgt de nood aan aanpasbaarheid aan schaalveranderingen van het netwerk. Grote toenames van het aantal sensorknopen of de knoopdichtheid moeten opgevangen kunnen worden door de middleware.
Aanpasbaarheid aan de applicatie
volgt ten eerste uit de vereiste dat kennis van
de applicatie in de middleware moet kunnen geïnjecteerd worden.
Ten tweede dicteert de
schaalbaarheidsvereiste ook een aanpassingsvermogen aan de applicatie. De kwaliteit van de dienstverlening moet eveneens kunnen aangepast worden aan de noden van de applicatie. Tenslotte zullen de beveiligingsvereisten verschillen van applicatie tot applicatie.
Statische aanpasbaarheid is de mogelijkheid om aanpassingen door te voeren voor het
operationeel worden van de middleware. De middleware kan bijvoorbeeld de mogelijkheid bieden om bij het compileren aan te geven welke delen moeten opgenomen worden. Bij heterogene netwerken kan de middleware op die manier statisch aangepast worden aan de verschillende hardwareplatformen. Voor de statische aanpasbaarheid kunnen heel wat traditionele technieken worden toegepast. Deze aanpassingen gebeuren namelijk voor het laden van de software
HOOFDSTUK 3.
23
MIDDLEWARE VOOR SENSORNETWERKEN
in de sensorknopen.
De beperkte middelen op de sensorknopen veroorzaken hier dus geen
beperking op de mogelijkheden. Bij
dynamische aanpasbaarheid
de werking van het systeem.
is het mogelijk aanpassingen door te voeren tijdens
De aanpassingen kunnen door het systeem zelf worden geïni-
tieerd. Men spreekt dan van zelfaanpasbaarheid of re exiviteit. Het is ook mogelijk dat de aanpassingen door een externe factor, bijvoorbeeld de gebruiker, worden geïnitieerd. Men kan dynamische aanpasbaarheid op twee manieren bekomen.
Men kan parameters
voorzien waarmee het systeem tijdens de uitvoering kan worden jngeregeld.
Dit laat toe
kleinere wijzigingen teweeg te brengen. Een techniek die hiervoor kan gebruikt worden is
implementaties 3.4.2
open
[23]. Voor grotere aanpassingen zijn echter vaak software updates nodig.
Virtuele machines als aanpasbaar platform
Voor grotere aanpassingen van een systeem zullen in veel gevallen software updates nodig zijn. De manier waarop het beheer van deze updates gebeurt, verschilt van systeem tot systeem. Toch valt er enige structuur op te merken in de verschillende aanpakken [16]. Een beheersysteem voor software updates in sensornetwerken bestaat uit een aantal componenten. Een gebruikersinterface voor de beheerder en een databank met gegevens over vorige en toekomstige updates horen in elk beheersysteem thuis. Typisch voor sensornetwerken zijn de data optimalisatie, het distributieprotocol en de uitvoeringsomgeving. Data optimalisatie is noodzakelijk om de communicatie voor updates te beperken.
Het
distributieprotocol zorgt voor de selectie van de knopen waar de update moet gebeuren, de verspreiding van de update naar de geselecteerde knopen en de veri catie van de uitvoering van de update. De uitvoeringsomgeving duidt op de combinatie van het besturingssysteem en eventuele middleware. Ze bepaalt in grote mate de mogelijkheden voor dynamische updates.
Uitvoeringsomgevingen en hun dynamische aanpasbaarheid De uitvoeringsomgevingen kunnen opgedeeld worden in drie categorieën (Figuur 3.2). Men onderscheidt monolitische omgevingen, modulaire omgevingen en virtuele machines. De eerste twee categorieën omvatten zowel besturingssystemen als middleware systemen. Virtuele machines zijn middleware systemen die boven een besturingssysteem uit één van de vorige categorieën wordt geplaatst.
Monolitisch
Bij de monolitische systemen worden de uitvoeringsomgeving en de applicatie
in één binaire afbeelding verweven. Men kan dit makkelijk statisch optimaliseren en de uitvoering is heel e ciënt. Een dergelijk systeem kan echter enkel geüpdatet worden door het volledige systeem te vervangen. De omvang van een update is daardoor vrij groot, wat ervoor zorgt dat er voor een update veel energie nodig is. Een update heeft daardoor een grote impact op de levensduur van het netwerk. TinyOS en Mantis (zie Sectie 2.1.3) zijn twee besturingssystemen die een monolitische aanpak hanteren.
De middlewaresystemen die boven deze systemen worden geplaatst zijn
daarom ook vaak monolitisch. Zij kunnen echter ook zelf een vorm van modulariteit of een virtuele machine voorzien. categorieën.
Zo komt de totale uitvoeringsomgeving terecht in de volgende
HOOFDSTUK 3.
MIDDLEWARE VOOR SENSORNETWERKEN
24
Figuur 3.2: De uitvoeringsomgeving bepaalt in grote mate de dynamische aanpasbaarheid
Modulair
Modulaire systemen bestaan uit een statisch deel, aangevuld met modules die
geladen en verwijderd kunnen worden. dan bij een monolitisch systeem.
De updates in een modulair systeem zijn kleiner
De energiekost voor een update wordt hierdoor beperkt.
De modulaire opbouw wordt gebruikt bij besturingssystemen zoals Sensor Operating System (SOS) en Contiki (zie Sectie 2.1.3) en de middleware systemen die de techniek van het modulair programmeren toepassen (zie Sectie 3.3).
Virtuele machine
De virtuele machines werden ook al in Sectie 3.3 besproken. Hun hoog
niveau instructies zorgen voor compacte updates die met een zeer lage energiekost in het netwerk verspreid kunnen worden. interpreteren van de instructies.
De prijs daarvoor is de extra uitvoeringskost voor het
Een virtuele machine kan men implementeren boven een
monolitisch besturingssysteem of boven een modulair besturingssysteem. In het eerste geval vergt een update aan de virtuele machine een kostelijke update van het monolitische systeem. Het tweede geval biedt de mogelijkheid de virtuele machine aan te passen door een nieuwe module te laden.
Maté (zie Sectie 3.3) is een middleware die toelaat monolitische virtuele
machines te genereren voor TinyOS.
Een dynamisch aanpasbare virtuele machine Welke uitvoeringsomgeving gepast is, wordt bepaald door een afweging van de uitvoeringskost tegenover de frequentie van de updates. Monolitische systemen hebben de laagste uitvoeringskost, maar updates zijn zeer kostelijk. De virtuele machines hebben de hoogste uitvoeringskost, maar bieden dan weer heel goedkope updates. De modulaire systemen zitten tussen deze twee uitersten in. Een modulaire virtuele machine biedt de voordelen van zowel de modulaire aanpak als die van de virtuele machines. Voor heel frequente, kleine updates kan men gebruik maken van compacte modules die in de instructieset van de virtuele machine worden uitgedrukt. Voor
HOOFDSTUK 3.
MIDDLEWARE VOOR SENSORNETWERKEN
25
grotere aanpassingen kan de instructieset van de virtuele machine uitgebreid of aangepast worden via de voorzieningen die het modulaire besturingssysteem biedt. Dergelijke dynamisch aanpasbare virtuele machine is in de literatuur niet terug te vinden. Deze thesis onderzoekt daarom de haalbaarheid van een dergelijke hybride tussen een modulair systeem en een virtuele machine. De thesis onderzoekt de vereisten voor zo'n systeem en presenteert een architectuur die deze vereisten aankan. gevalideerd door de bouw van een prototype implementatie.
Tenslotte wordt de architectuur
Hoofdstuk 4
Maté en Sensor Operating System Deze thesis is gebaseerd op Maté. Maté [25, 24] is een middleware voor sensornetwerken die de virtuele machine aanpak hanteert. Sectie 4.1 behandelt de belangrijkste concepten van Maté. Sensor Operating System (SOS) [17] is een modulair besturingssysteem voor sensornetwerkknopen van het generische type. De implementatie in deze thesis is gemaakt met behulp van SOS. Sectie 4.2 geeft een overzicht van de werking van SOS. Er wordt vooral aandacht besteed aan de ondersteuning die SOS biedt voor dynamisme.
4.1
Maté
Maté is een middleware voor TinyOS die toelaat om een applicatiespeci eke virtuele machine (ASVM) te bouwen.
Maté bestaat uit twee delen: de ASVM zelf, die op de sensorknopen
wordt geladen, en de toolchain, die een aantal tools bevat die op de computer van de gebruiker worden ingezet om de ASVM te bouwen en te gebruiken. De ASVM wordt door een tool uit de toolchain (VMBuilder) gegenereerd uit de ASVMtemplate en gebruikersgede nieerde uitbreidingen. De ASVM-template is het skelet van een ASVM. De functionaliteit van de template is gemeenschappelijk voor alle ASVMs. De uitbreidingen die de gebruiker heeft gede nieerd zijn aangepast aan de noden van de applicatie. Nadat de ASVM is opgebouwd, wordt ze gecompileerd en op de sensorknopen geïnstalleerd. Vanaf dit moment kan de ASVM niet meer worden aangepast. De enige manier om de ASVM nog te wijzigen is het volledig herprogrammeren van de sensorknopen. Het gedrag van de ASVM kan echter wel nog aangepast worden. De ASVM is een virtuele machine en biedt dus een geïnterpreteerde bytecode interface aan. Door bytecode scripts te laden in de virtuele machine kan bepaald worden wat de ASVM uitvoert. Om de gebruiker te helpen bij het gebruiken van de ASVM bevat de toolchain de Scripter.
Deze tool compileert scripts in een hoger niveau scriptaal naar de bytecode interface
van de ASVM. Vervolgens verpakt Scripter deze bytecode in capsules en injecteert ze in het sensornetwerk. De capsules die in het netwerk zijn geïnjecteerd, worden automatisch naar alle knopen in het sensornetwerk verspreid. Deze functionaliteit wordt aangeboden door de ASVM-template. Het algoritme dat hiervoor wordt gebruikt heet Trickle [27]. Sectie 4.1.1 legt uit hoe een ASVM kan gebruikt worden met behulp van de Scripter tool.
Vervolgens gaat Sectie 4.1.2 dieper in op de samenstellende delen van een ASVM en
legt uit hoe deze met behulp van de VMBuilder tool worden gecombineerd tot een ASVM.
26
HOOFDSTUK 4.
27
MATÉ EN SENSOR OPERATING SYSTEM
Figuur 4.1: Een virtuele machine gebruiken: Scripter
Daarna verduidelijkt Sectie 4.1.3 de werking van de ASVM-template en de manier waarop de uitbreidingen van de gebruiker hierin passen. Sectie 4.1.4 geeft vervolgens een beknopte uitleg over het Trickle algoritme. Tenslotte bespreekt Sectie 4.1.5 de link met deze thesis.
4.1.1
Een virtuele machine gebruiken
Een ASVM wordt geherprogrammeerd door capsules in het netwerk te brengen. De capsules bevatten de bytecode die de ASVM moet uitvoeren. Om de capsule in het netwerk te kunnen injecteren moet de gebruiker uiteraard met het sensornetwerk kunnen communiceren.
Dit
gebeurt via een sensorknoop die rechtstreeks verbonden is met de computer van de gebruiker. Deze basisknoop hangt bijvoorbeeld via een seriële interface aan de computer. De capsules worden door de gebruiker geschreven in een hoger niveau scripttaal.
Voor
deze in het netwerk kunnen worden gebracht, moeten ze eerst worden omgezet naar de binaire bytecode die de ASVM kan uitvoeren. We kunnen in dit proces drie stappen onderscheiden: de vertaling van de scripttaal naar de instructieset van de ASVM, de omzetting van de instructies in hun binaire voorstelling en uiteindelijk het injecteren hiervan in het sensornetwerk. De eerste twee stappen komen overeen met de compilatiefase en de assembleerfase in een traditioneel systeem.
Deze taken worden vervuld door een compiler en een assembler.
De
laatste stap is speci ek voor Maté. Hiervoor wordt een injector tool gebruikt die de bytecode inpakt in een capsule en a evert bij de ASVM op de basisknoop. Deze zorgt vervolgens voor de verdere verspreiding van de capsule in het netwerk. De Scripter tool (Figuur 4.1) uit de toolchain van Maté combineert deze drie stappen in één tool. Scripter neemt als invoer een script in de hoger niveau scripttaal, zet het om naar
HOOFDSTUK 4.
28
MATÉ EN SENSOR OPERATING SYSTEM
bytecode en injecteert een capsule met deze bytecode in het sensornetwerk. Voor de omzetting van de hoger niveau scripttaal naar bytecode maakt Scripter gebruik van informatie over de instructieset van de ASVM die door VMBuilder wordt gegenereerd bij het bouwen van een virtuele machine (Sectie 4.1.2).
4.1.2
Een virtuele machine bouwen
Een virtuele machine bouwen kan met behulp van de tool VMBuilder uit de toolchain van Maté. De werking wordt verduidelijkt in Figuur 4.2. VMBuilder neemt als invoer een beschrijving van de ASVM en genereert daaruit de ASVM in de vorm van een TinyOS-applicatie. Daarnaast genereert VMBuilder informatie die door de andere tools in de toolchain wordt gebruikt.
Invoer: beschrijving van een virtuele machine De beschrijving van een virtuele machine beschrijft welke uitbreidingen de gebruiker wenst toe te voegen aan de gemeenschappelijke ASVM-template. De ASVM-template structureert de gebruikersgede nieerde uitbreidingen en bepaalt onder andere het gelijktijdigsheidsmodel, het uitvoeringsmodel en het codepropagatiemodel (Sectie 4.1.3).
De uitbreidingen worden
ingepast in deze ASVM-template en bestaan uit operaties en contexten.
Operaties
De operaties zijn de eenheid van functionaliteit en kunnen worden onderverdeeld
in primitieven en functies. De primitieven zijn de operaties die nodig zijn om een hoger niveau scripttaal te ondersteunen. Ze implementeren met andere woorden de controleconstructies en het gegevensmodel van de scripttaal. Voorbeelden van primitieve operaties zijn: een conditionele sprong, een constante op de stapel plaatsen, een lokale variabele lezen of schrijven, . . . De functies implementeren de applicatiespeci eke functionaliteit en zijn in principe onafhankelijk van de scripttaal die gebruikt wordt. kunnen al dan niet een resultaat teruggeven.
Ze hebben één of meerdere argumenten en Voorbeelden zijn:
het gemiddelde van twee
waarden berekenen, twee waarden optellen, een bericht versturen, . . . Een operatie wordt geïmplementeerd in nesC [12], een uitbreiding van C die werd ontwikkeld voor gebruik in TinyOS. De operatie moet een aantal interfaces implementeren om de ASVM-template toe te laten ermee te interageren. Een operatie moet minstens de interface implementeren waarvan de ASVM-template gebruik maakt om een operatie uit te voeren. Wanneer een primitieve operatie toegang nodig heeft tot een gedeelde variabele, moet zij ook de interface implementeren waarlangs de ASVM-template hierover informatie opvraagt om het gelijktijdigheidsmodel te implementeren. Naast de implementatie omvat een operatie ook een beschrijving. Een functie wordt beschreven in een apart bestand. Een primitieve operatie wordt beschreven in de beschrijving van de taal die ze mee implementeert. De beschrijving van een operatie bevat alle informatie die nodig is over de operatie. Dit omvat onder andere informatie over het aantal en het type van de parameters, of de functie al dan niet een waarde teruggeeft, of een primitieve operatie toegang nodig heeft tot een gedeelde variabele, . . .
Contexten
Het uitvoeringsmodel dat de ASVM-template implementeert, is gebeurtenisge-
baseerd. Een context bepaalt op welke gebeurtenissen er gereageerd wordt met de uitvoering van een capsule. De context bepaalt tegelijk de omgeving waarin deze uitvoering plaatsvindt en is in dit opzicht vergelijkbaar met een proces in een traditioneel uitvoeringsmodel.
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
Figuur 4.2: Een virtuele machine bouwen: VMBuilder
29
HOOFDSTUK 4.
30
MATÉ EN SENSOR OPERATING SYSTEM
Een context omvat net als een operatie een implementatie en een beschrijving. De implementatie is gemaakt in nesC en bevat code om een gebeurtenis op te vangen. Deze code zal op de gebeurtenis reageren door de context door te geven aan de ASVM-template die vervolgens de uitvoering start van de capsule die met de context geassocieerd is. De beschrijving van een context bevat informatie over de naam en de identi catie van de context.
De beschrijving kan ook een verwijzing bevatten naar een operatie.
Dit is het
geval wanneer de gebeurtenis waarop gereageerd wordt het gevolg is van de uitvoering van een operatie. Een context die reageert op de verzending van een bericht heeft bijvoorbeeld weinig nut wanneer de virtuele machine geen operatie bevat om een bericht te versturen. De context zal daarom in zijn beschrijving aangeven dat de operatie om een bericht te versturen noodzakelijk is voor de context.
Uitvoer: ASVM De VMBuilder genereert de ASVM in de vorm van een TinyOS-applicatie.
Dit betekent
onder andere broncode in nesC en een Make le. Deze Make le bevat instructies om de ASVM te compileren. De compilatie resulteert in een binaire afbeelding (image) van de ASVM en TinyOS. Deze afbeelding kan met de tools die bij TinyOS worden geleverd op een sensorknoop worden geladen.
Uitvoer: ASVM speci eke toolondersteuning Naast de ASVM zelf genereert VMBuilder ook informatie die door andere tools van Maté wordt gebruikt. Er wordt bijvoorbeeld een Java klasse gegenereerd die constanten bevat die speci ek zijn voor de virtuele machine. Deze constanten beschrijven de mapping tussen namen van operaties en hun bytecode. Scripter (zie Sectie 4.1.1) gebruikt deze informatie om zijn taak te kunnen vervullen.
Ook worden er een aantal klassen gegenereerd die het formaat
encapsuleren van berichten die naar de ASVM kunnen gestuurd worden.
4.1.3
De opbouw van een ASVM
Een ASVM (Figuur 4.3) bestaat uit gebruikersgede nieerde capsules, operaties en contexten die worden toegevoegd aan de ASVM-template (Sectie 4.1.1, Sectie 4.1.2). De ASVM-template is het skelet van de ASVM waaraan de gebruiker zijn uitbreidingen ophangt.
De ASVM-
template bepaalt het gelijktijdigheidsmodel, het uitvoeringsmodel en het propagatiemodel en
hoe de activiteiten in een ASVM verlopen. uitgevoerd wordt en wanneer dat gebeurt. bepaalt zo dus
De gebruiker kan bepalen
wat er
Wat en wanneer? De gebruiker bepaalt op twee manieren wat er gebeurt in de ASVM. Enerzijds schrijft de gebruiker scripts die met behulp van de Scripter worden omgezet in bytecode en als capsules in het netwerk worden gebracht (zie Sectie 4.1.1). Anderzijds bepaalt de gebruiker de instructieset van de ASVM door aan te geven welke operaties opgenomen worden (zie Sectie 4.1.2). De gebruiker bepaalt wanneer de uitvoering in een ASVM start door de contexten te bepalen die in de ASVM worden opgenomen (zie Sectie 4.1.2).
Deze contexten de niëren
welke gebeurtenissen de uitvoering van een capsule tot gevolg hebben.
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
31
Figuur 4.3: Maté: opbouw van een ASVM
Hoe? Gelijktijdigheidsmodel deelde variabelen.
Sommige instructiesets kunnen ondersteuning hebben voor ge-
Dit kan lijden tot problemen wanneer meerdere contexten tegelijk uit-
voeren. Daarom worden contexten na een aanvraag tot uitvoering eerst door de Concurrency Manager onderzocht. De Concurrency Manager verzekert dat de uitvoering van contexten gebeurt zonder race conditions en deadlocks door locks bij te houden voor alle gedeelde variabelen. Wanneer een context niet veilig kan uitvoeren, plaatst de Concurrency Manager de context in een wachtrij. Wanneer de uitvoering wel veilig kan gebeuren wordt de context doorgegeven aan de Scheduler. Wanneer nieuwe bytecode aankomt, kunnen bepaalde variabelen zich in een inconsistente toestand bevinden. Het is echter niet opportuun om te wachten tot alle uitvoerbare contexten hun uitvoering hebben beëindigd. De nieuwe bytecode kan bijvoorbeeld bedoeld zijn om een oneindige lus te verhelpen.
De Concurrency Manager herstart daarom de virtuele machine
wanneer nieuwe bytecode aankomt.
Uitvoeringsmodel
Wanneer een context veilig kan uitvoeren, komt hij bij de Scheduler
terecht die de instructies één voor één decodeert en uitvoert. Wanneer meerdere contexten tegelijk aan het uitvoeren zijn, verdeelt de Scheduler de uitvoeringstijd over de verschillende contexten volgens een round robin algoritme. De ASVM-template legt ook op dat de parameters en terugkeerwaarden van functies doorgegeven moeten worden via een stapel. Deze stapel maakt deel uit van de context. De parameters worden op de stapel geplaatst met behulp van primitieve operaties die een geïntegreerde operand kunnen hebben.
HOOFDSTUK 4.
32
MATÉ EN SENSOR OPERATING SYSTEM
Propagatiemodel
De Capsule Store beheert de aanwezige capsules en zorgt voor de ver-
spreiding ervan in het sensornetwerk. De Capsule Store gebruikt het Trickle [27] algoritme om de verspreiding van de capsules te regelen.
4.1.4
Trickle
Voor de verspreiding van capsules in het netwerk gebruikt Maté Trickle [27]. Trickle gebruikt een vriendelijke gossip aanpak: de knopen broadcasten geregeld metadata die de toestand van hun code beschrijven, maar blijven stil wanneer ze recent identieke metadata hebben gehoord.
Wanneer een inconsistentie wordt gedetecteerd wordt de knoop met een oudere
versie up to date gebracht door zijn buren. Trickle heeft een heel lage overhead tijdens de stabiele toestand. Als alle knopen up to date zijn stuurt Trickle heel weinig pakketten omdat de knopen stil blijven als ze dezelfde metadata al eens hebben gehoord. De tijd tussen de broadcasts neemt toe (tot een maximale waarde) naarmate de stabiele toestand aanhoudt. In een single-hop netwerk zonder pakketverlies en met perfecte tijdssynchronisatie is het aantal verstuurde pakketten onafhankelijk van het aantal knopen. Deze ideale omstandigheden komen echter nooit voor. Wanneer deze ideale omstandigheden er niet zijn, neemt het aantal verstuurde pakketten in de stabiele toestand logaritmisch toe met het aantal knopen. Trickle slaagt er eveneens in de overhead voor het versturen van deze pakketten te spreiden over het ganse netwerk. Een knoop wacht altijd een willekeurige periode voor hij probeert zijn toestand te versturen. Dit zorgt ervoor dat op langere termijn elke knoop ongeveer evenveel keer zijn toestand verstuurt.
Zo wordt het energieverbruik voor het onderhouden van de
toestand gespreid over alle knopen. Zodra een inconsistentie in het netwerk wordt vastgesteld, verlaagt Trickle de tijd tussen twee broadcasts van de metadata. Dit laat toe om code snel te laten propageren doorheen een groot netwerk. Wanneer alle knopen terug up to date zijn, neemt de tijd tussen de broadcast weer toe om de lage overhead tijdens de stabiele toestand te bekomen.
4.1.5
Dynamische ASVMs?
Maté maakt gebruik van TinyOS als onderliggend besturingssysteem.
TinyOS hanteert de
monolitische aanpak (cfr. Sectie 2.1.3 op pagina 10). De ASVM wordt samen met TinyOS gecompileerd tot één binaire afbeelding. Deze afbeelding kan niet dynamisch gewijzigd worden. De dynamische aanpasbaarheid van de ASVM blijft daarom beperkt tot het wijzigen van de bytecode die in de ASVM wordt uitgevoerd.
Wanneer een wijziging aan de ASVM zelf
vereist is, moet de ASVM volledig vervangen worden. Sectie 2.1.3 beschrijft het ontstaan van een nieuwe generatie besturingssystemen die een modulaire aanpak volgen. Deze laten toe om een applicatie makkelijker aan te passen door nieuwe modules te laden. Dit zorgt voor nieuwe mogelijkheden bij de ontwikkeling van sensornetwerkapplicaties. Deze thesis onderzoekt of het haalbaar is om de voordelen van virtuele machines (compacte updates, veilige uitvoeringsomgeving, . . . ) te combineren met de exibiliteit van modulaire besturingssystemen. Dit gebeurt door het uitwerken van de architectuur voor een dynamisch aanpasbare virtuele machine.
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
33
Figuur 4.4: SOS: De statische kernel wordt aangevuld met dynamische modules
4.2
Sensor Operating System
Deze thesis onderzoekt de mogelijkheid om een dynamische virtuele machine te bouwen voor generische sensorknopen. Om dynamische wijzigingen aan de virtuele machine te ondersteunen is ondersteuning van het besturingssysteem nodig. De ondersteuning die nodig is van het besturingssysteem houdt twee zaken in. Ten eerste moet het mogelijk zijn dynamisch nieuwe code te laden via een vorm van modules.
Ten
tweede is er dynamisch geheugen nodig om de gegevensstructuren van de virtuele machines dynamisch te kunnen wijzigen. Sensor Operating System (SOS) [17] en Contiki [10] zijn de twee belangrijkste besturingssystemen die deze ondersteuning bieden. Deze thesis heeft gekozen voor SOS omwille van de goede ondersteuning voor het MICAzhardwareplatform. Dit is het hardwareplatform dat ter beschikking is voor het bouwen van een prototype implementatie (Hoofdstuk 7). Contiki biedt wel ondersteuning voor de AVRarchitectuur die in het MICAz-platform wordt gebruikt, maar heeft verder geen ondersteuning voor het platform. De volgende secties beschrijven het modulesysteem en de ondersteuning voor dynamisch geheugen van SOS. Tenslotte wordt kort ingegaan op de kost van deze dynamische aanpak. Het blijkt dat deze rijke functionaliteit geen aanleiding geeft tot onaanvaardbare gevolgen op de performantie en het energieverbruik van een sensornetwerk.
4.2.1
Modules
SOS bestaat uit een statische kernel en dynamisch laadbare modules (Figuur 4.4). De meeste ontwikkeling in SOS gebeurt op het niveau van modules. Zowel drivers, protocollen als applicatiecomponenten worden als modules verwezenlijkt. Veranderingen in de kernel moeten enkel gebeuren wanneer functionaliteit met betrekking tot de systeemdiensten moet gewijzigd worden.
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
34
Figuur 4.5: SOS: De interacties tussen modules: asynchroon (links) en synchroon (rechts)
Figuur 4.6: SOS: De interacties tussen een module en de kernel
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
35
De uitvoering kan op twee manieren een module binnenkomen (Figuur 4.5): via een bericht of via een oproep van een geregistreerde functie. De communicatie via berichten is asynchroon, terwijl de communicatie via geregistreerde functieoproepen synchroon gebeurt. De interacties met de kernel verlopen in twee fasen: een synchrone aanvraag en een asynchroon antwoord van de kernel (Figuur 4.6).
Asynchrone interacties
Wanneer module A asynchroon wil interageren met module B,
plaatst module A een bericht in de berichtenbuer van de SOS-scheduler door de postfunctie uit de kernel API op te roepen (Figuur 4.5, links). De SOS-scheduler handelt de berichten af in de volgorde dat ze in de buer komen. De SOS-scheduler levert een bericht af door de uitvoering te starten van een functie in de module waarvoor het bericht bestemd is.
Deze
functie krijgt een verwijzing naar het bericht als parameter mee en beslist op basis van het type van het bericht wat er gebeurt. Berichten kunnen een verwijzing bevatten naar een geheugenblok waarin extra gegevens staan.
Op deze manier kunnen extra parameters meegegeven worden of kan bijvoorbeeld
een buer worden doorgegeven van module naar module (dit is onder meer nuttig bij de implementatie van een netwerkstapel).
Synchrone interacties
Modules kunnen synchroon met elkaar communiceren via indirec-
te functieoproepen (Figuur 4.5, rechts).
Een module stelt een functie ter beschikking door
een registratieprocedure bij de kernel te doorlopen. De kernel maakt een functiecontroleblok aan waar gegevens over de functie worden bijgehouden:
een functieverwijzing, de module-
identi catie, de functie-identi catie, . . . Een module die een geregistreerde functie wil oproepen, moet zich eerst inschrijven voor de functie. Daarna kan de module de functie indirect oproepen via de SOS-kernel.
Interacties met de kernel
De modules spreken de kernel aan via een sprongtabel (Fi-
guur 4.6). De sprongtabel wordt op een vaste plaats in het geheugen gezet en introduceert een extra indirectie. Dit zorgt ervoor dat modules niet opnieuw moeten gecompileerd worden bij een nieuwe SOS-versie, zolang de sprongtabel ongewijzigd blijft. Dit laat ook toe een module te laden in een heterogeen netwerk waarin verschillende SOS-versies aanwezig zijn. Een interactie met de kernel gaat typisch in twee fasen: een niet-blokkerende aanvraag en een asynchroon antwoord van de kernel (Figuur 4.6). Wanneer er bijvoorbeeld om een sensormeting wordt gevraagd, keert de aanvraagfunctie direct terug nadat de kernel de aanvraag heeft doorgegeven aan de sensor via een hardwarespeci eke API. Wanneer de sensormeting beschikbaar is, genereert de sensor een interrupt waarna de kernel een systeembericht in een berichtenbuer plaatst. De buer met systeemberichten is verschillend van de buer voor de gewone berichten en heeft een hogere prioriteit. De SOS-scheduler levert eerst alle berichten in de systeembuer af vooraleer de andere berichten worden afgeleverd.
4.2.2
Laden en verwijderen van modules
Wanneer het distributieprotocol een aankondiging voor een module detecteert, wordt gecontroleerd of het gaat om een update voor een bestaande module of om een nieuwe module. Als het om een nieuwe module gaat waar de knoop interesse voor heeft en er is genoeg programmageheugen om de module te laden, dan wordt de module gedownload. SOS leest eerst de
HOOFDSTUK 4.
36
MATÉ EN SENSOR OPERATING SYSTEM
metadata in en controleert of er genoeg dynamisch geheugen voor handen is om de toestand van de module te bewaren. Zoniet, dan wordt het laden van de module afgebroken. Modules zijn onafhankelijk van de positie waar ze worden geladen. Dit is nodig omdat een module niet altijd op dezelfde plaats kan geladen worden. De plaatsen waar de uitvoering een module binnenkomt moeten natuurlijk gekend zijn voor deze kunnen opgeroepen worden. Daarom wordt bij de compilatie van een module de berichtafhandelingsfunctie telkens op dezelfde plaats ten opzichte van het begin van de module geplaatst. Tijdens het laden van de module maakt de kernel een controlestructuur voor de berichtscheduler waarin het absolute adres van deze functie wordt geplaatst. Op deze manier weet de berichtscheduler waar naar toe moet worden gesprongen om een bericht te laten afhandelen door een module. Voor de synchrone functieoproepen wordt het probleem opgelost door de positie van een functie mee te delen via de registratieprocedure.
De kernel plaatst een verwijzing naar de
functie in het functiecontroleblok. Een oproep van de functie gebeurt daarna indirect via dit functiecontroleblok. Een module verwijderen wordt geïniteerd door de kernel door het sturen van een
nal
bericht. Dit geeft de module de kans om de middelen die het bezit vrij te geven en afhankelijke modules te informeren. Daarna voert de kernel garbage collection uit om resterende middelen vrij te geven. Het distributieprotocol dat gebruikt wordt om modules te adverteren en te propageren in het netwerk is onafhankelijk van de SOS kernel.
Momenteel gebruikt SOS een publish-
subscribe protocol dat gelijkaardig is aan MOAP (Multihop Over-the-Air Programming) [38]. SOS kan echter ook gebruik maken van andere distributieprotocollen zoals bijvoorbeeld Deluge [21]. MOAP verspreidt code in een sensornetwerk volgens een rimpelprincipe. De code wordt geladen in een knoop die verbonden is met een computer. Deze knoop wordt nu de (originele) bron voor de code.
De bron adverteert de code door een publish bericht te versturen.
De
knopen in de buurt van de bron ontvangen dit bericht en vergelijken de versie van de geadverteerde code met de versie van de code die ze zelf hebben. Wanneer een knoop besluit dat het over nieuwe code gaat, stuurt hij een subscribe bericht naar de bron. Nadat de bron een subscribe bericht ontvangt wacht ze nog even om andere knopen de tijd te geven om een subscribe bericht te sturen. Daarna begint de bron te code te versturen. Wanneer een knoop de volledige code ontvangen heeft, wordt de knoop een secundaire bron en begint op zijn beurt publish berichten te versturen. Dit creëert een rimpeleect waardoor uiteindelijk het ganse sensornetwerk de code ontvangt.
4.2.3
Bescherming
De meeste sensornetwerkhardware heeft geen geheugenbeheereenheid. SOS kan daarom geen geheugenbescherming bieden.
SOS voorziet echter wel eenvoudige bescherming tegen veel
voorkomende fouten.
Foutieve berichten
Een foutief bericht is een bericht dat wordt afgeleverd aan een onbe-
staande module, of een bericht dat wordt afgeleverd bij een module die het bericht niet kan behandelen. Wanneer SOS vaststelt dat een bericht bestemd is voor een onbestaande module laat SOS het bericht gewoon vallen en geeft alle geheugen vrij dat normaal zou overgaan naar de module van bestemming. Een module kan zelf controleren wat er gebeurt wanneer ze een
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
37
bericht ontvangt dat ze niet kan verwerken. Meestal negeert de module het bericht en geeft een foutenboodschap terug. SOS geeft vervolgens opnieuw het nodige geheugen vrij.
Afhankelijkheidsfouten bij functieaanroepen
De afhankelijkheden tussen modules die
ontstaan door de mogelijkheid tot functieaanroepen kunnen eveneens aanleiding geven tot fouten. SOS biedt bescherming tegen een aantal van deze fouten. Het functiecontroleblok speelt hierin een belangrijke rol. Een module geeft bij de registratieprocedure aan welke argumenten de te registreren functie verwacht. Deze typering wordt opgeslagen in het functiecontroleblok. Wanneer een module inschrijft voor een functie geeft zij aan welke argumenten ze verwacht te kunnen meegeven. Deze informatie wordt vergeleken met de type-informatie in het functiecontroleblok.
Zo wordt voorkomen dat een verkeerde
implementatie van een functie wordt opgeroepen. Wanneer een module wordt verwijderd controleert SOS een referentieteller in het functiecontroleblok van de geregistreerde functies van de module. Wanneer deze teller aangeeft dat er geen modules meer ingeschreven zijn op een functie, verwijdert SOS het functiecontroleblok.
In het andere geval markeert SOS het functiecontroleblok als ongeldig zodat nieuwe
inschrijvingen voor de functie niet meer aanvaard worden. SOS vervangt de verwijzing naar de implementatie door een verwijzing naar een stub functie. Wanneer een module wordt vervangen door een nieuwe versie registreert deze module nieuwe versies van haar functies. Tijdens dit proces markeert SOS de functiecontroleblokken van de functies tijdelijk als ongeldig. Wanneer de typering ongewijzigd is gebleven veronderstelt SOS dat het om een nieuwe implementatie gaat en past de verwijzing aan zodat ze naar de nieuwe implementatie verwijst. Wanneer de typering gewijzigd is, wordt een nieuw functiecontroleblok aangemaakt. Het oude blok wordt blijvend ongeldig en de verwijzing wordt aangepast tot een verwijzing naar een stub functie.
4.2.4
Dynamisch geheugen
Besturingssystemen voor geïntegreerde systemen bieden vaak geen dynamisch geheugen. Statisch geheugen heeft echter enkele problemen. Buers hebben bijvoorbeeld een vaste lengte en moeten dus begroot worden voor het slechtste geval.
Om de beperkingen van statisch
geheugen op te lossen biedt SOS dynamisch geheugen. Ook bij de implementatie van het modulesysteem biedt dynamisch geheugen voordelen. Het geheugen voor de toestand van een module wordt dynamisch gealloceerd, waardoor problemen met statische referenties naar de toestand worden vermeden. Het dynamisch geheugensysteem in SOS is nog volop in ontwikkeling. Het systeem dat in de literatuur [17] wordt beschreven heeft een vast aantal geheugenblokken van drie verschillende blokgroottes. Het geheugen wordt toegewezen volgens een best- t strategie. De ontwikkelingsversie van SOS heeft een ander systeem voor het toekennen van dynamisch geheugen. Het geheugen wordt nu toegekend in veelvouden van een vaste blokgrootte. Voor het bepalen van een blok geheugen dat groot genoeg is, gebruikt het systeem een rst- t strategie. Dit systeem heeft in de laatste ontwikkelingsversies van SOS opnieuw wijzigingen ondergaan. Dit is het gevolg van een probleem dat gedetecteerd werd tijdens de prototype implementatie van deze thesis. Sectie 7.3.1 bevat een uitgebreide beschrijving van het probleem en de voorgestelde oplossing.
HOOFDSTUK 4.
MATÉ EN SENSOR OPERATING SYSTEM
Platform
Code
RAM
SOS kernel
20464 B
1163 B
(Dynamisch geheugen)
-
1536 B
TinyOS met Deluge
21132 B
597 B
Maté Bombilla
39746 B
3196 B
38
Tabel 4.1: Geheugengebruik van SOS, TinyOS en Maté Bombilla gecompileerd voor MICA2
4.2.5
Evaluatie
De dynamische aanpak van SOS resulteert niet in een veel grotere overhead. De auteurs van SOS presenteren in [17] een uitgebreide evaluatie van het energieverbruik en de CPU-overhead van SOS. Ze vergelijken de prestaties van SOS met die van TinyOS (gecombineerd met Deluge om het verspreiden en laden van nieuwe afbeeldingen te ondersteunen) en Maté Bombilla (de standaard ASVM van Maté). Ze concluderen dat SOS een gelijkaardige performantie heeft als TinyOS en Maté Bombilla. De energiekost om een applicatie te laden in een operationeel sensornetwerk is lager dan bij TinyOS (waar een volledige afbeelding moet verstuurd worden), maar hoger dan bij Maté Bombilla (waar slechts enkele capsules moeten verzonden worden). Het totale energieverbruik is op lange termijn echter bijna identiek voor zowel TinyOS, SOS en Maté Bombilla. Het geheugengebruik van SOS is eveneens aanvaardbaar. De auteurs vergelijken het geheugengebruik van SOS met dat van TinyOS en Maté Bombilla (Tabel 4.1). De grootte van de code van SOS is vergelijkbaar met de grootte van TinyOS. Maté Bombilla gebruikt ongeveer dubbel zoveel codegeheugen. SOS zit qua gebruik van RAM geheugen tussen TinyOS en Maté Bombilla in. Merk op dat het RAM geheugen bij SOS in twee stukken is verdeeld. Er is een stuk dat exclusief door de kernel wordt gebruikt en een stuk dat wordt gebruikt voor dynamisch gealloceerd geheugen. Dit laatste kan ook door de modules worden gebruikt.
Hoofdstuk 5
Analyse In Sectie 3.4.2 werd duidelijk dat de combinatie van een modulair besturingssysteem en een virtuele machine een interessante mogelijkheid vormt om de aanpasbaarheid van de uitvoeringsomgeving op sensorknopen te verhogen. Dit hoofdstuk bakent eerst de grenzen af van het systeem dat in deze thesis wordt ontwikkeld om een dergelijke virtuele machine aan te bieden. Daarna wordt onderzocht aan welke vereisten het ontwikkelde systeem moet voldoen.
5.1
De grenzen van het systeem
Het systeem dat in deze thesis wordt ontwikkeld heeft als doel dynamisch aanpasbare virtuele machines aan te bieden aan sensornetwerkapplicaties. De grenzen van het systeem zijn een modulair besturingssysteem langs de ene kant, en sensornetwerkapplicaties langs de andere kant (Figuur 5.1).
Modulair besturingssysteem
Het systeem kan er van uitgaan dat er een modulair be-
sturingssysteem aanwezig is. Dit modulair besturingssysteem laat toe om dynamisch nieuwe code toe te voegen aan het systeem wanneer dit nodig is. Daarnaast kan het systeem gebruik maken van de voorzieningen voor dynamisch geheugen om zijn gegevensstructuren dynamisch op te bouwen.
Applicaties
De sensornetwerkapplicaties maken gebruik van het systeem om hun taak te
vervullen. Ze gebruiken de diensten van het systeem en via het systeem ook onrechtstreeks de diensten van het besturingssysteem. Omdat het systeem in staat moet zijn diensten aan te bieden die onafhankelijk zijn van de applicatie hoort applicatielogica niet thuis in het
Figuur 5.1: De grenzen van het systeem
39
HOOFDSTUK 5.
40
ANALYSE
systeem. Er moet echter wel de mogelijkheid worden geboden aan de applicatieontwikkelaars om de kennis van hun applicatie in het systeem in te brengen. Kennis van de applicatie is namelijk één van de uitdagingen die in Sectie 3.2 werden aangegeven.
5.2
Belangrijkste aandachtspunten
Deze thesis richt zich vooral op aanpasbaarheid van het systeem. Aanpasbaarheid is belangrijk voor een heel aantal uitdagingen die in Sectie 3.2 aan bod kwamen.
Sectie 3.4.1 maakt
een onderscheid tussen aanpasbaarheid aan de omstandigheden en aanpasbaarheid aan de applicatie. Daarnaast werd duidelijk gemaakt dat aanpasbaarheid zowel statisch als dynamisch kon zijn. Deze thesis richt zich vooral op
dynamische aanpassingen die van buitenuit
geïnitieerd worden, zonder echter de algemene aanpasbaarheid uit het oog te verliezen. Het systeem situeert zich vooral in het gezichtspunt middleware als integrator (Sectie 2.3.3). Het presenteert het sensornetwerk naar de buitenwereld als een verzameling virtuele machines. Opdrachten en aanpassingen worden automatisch verspreid naar alle sensorknopen. Dit maakt het mogelijk het netwerk als een geheel te benaderen. Middleware diensten die zich richten op de twee andere gezichtspunten (aggregatie, coördinatie) kunnen door een gebruiker worden ingevoegd in de instructieset van de virtuele machines. Het systeem treedt dus op als integrator van deze diensten.
5.3
Aanpasbare virtuele machines
Het systeem biedt dynamisch aanpasbare virtuele machines.
Deze sectie beschrijft welke
aanpasbaarheid nodig is tijdens normaal gebruik van het systeem, wanneer de functionaliteit moet uitgebreid worden en wanneer meerdere applicaties van het systeem wensen gebruik te maken.
5.3.1
Normaal gebruik
De normale werking van het systeem vereist geen aanpassingen aan de virtuele machines, maar de opdrachten die ze uitvoeren zijn daarom niet noodzakelijk constant. Aanpasbaarheid houdt hier in dat het mogelijk moet zijn om het netwerk nieuwe opdrachten te geven. Men moet met andere woorden het netwerk kunnen herprogrammeren. Een beveiligingsapplicatie, bijvoorbeeld, die gebruik maakt van het sensornetwerk aanwezig in een kantoorgebouw, krijgt van het netwerk op geregelde tijdstippen informatie over de positie van belangrijke voorwerpen. Als de beveiligings rma plots merkt dat er vreemden in het gebouw aanwezig zijn, kan zij het netwerk opdragen de posities van deze voorwerpen frequenter te rapporteren. Zo kan sneller gedetecteerd worden dat een voorwerp wordt ontvreemd. De functionaliteit die hiervoor nodig is, is reeds op de sensorknopen aanwezig. Ze moet enkel op een andere manier worden aangewend. Dit soort aanpasbaarheid is reeds aanwezig in de huidige sensor virtuele machines, zoals bijvoorbeeld Maté. Nieuwe opdrachten kunnen in het netwerk worden gebracht onder de vorm van aangepaste scripts, geschreven in de instructieset van de virtuele machine.
HOOFDSTUK 5.
5.3.2
ANALYSE
41
Functionaliteit aanpassen
Wanneer blijkt dat de functionaliteit die wordt aangeboden via de instructieset van de aanwezige virtuele machine niet meer voldoet, moet de virtuele machine uitgebreid kunnen worden. Stel dat de beveiligings rma oordeelt dat de lokalisatie van personen aan de hand van geluidsmetingen te onnauwkeurig is en dat men voortaan een alternatief en nauwkeuriger algoritme wil gebruiken om personen te lokaliseren. Dit nieuwe algoritme moet ingepast worden in de instructieset van de virtuele machine. Pas daarna kan het algoritme worden gebruikt in de scripts die in het netwerk worden geïnjecteerd. Om dit mogelijk te maken moet de instructieset van de virtuele machine dynamisch aangepast of uitgebreid kunnen worden. Aanpassingen aan de instructieset van een virtuele machine kunnen ondersteund worden door bibliotheken te laden en te verwijderen die een deel van de instructieset implementeren. Om dit aan te bieden, kan het systeem steunen op het modulaire besturingssysteem dat toelaat nieuwe code aan het werkende systeem toe te voegen. Wanneer het nieuwe algoritme voor de lokalisatie van personen gebruik maakt van een type communicatie dat het oude algoritme niet gebruikte, bijvoorbeeld directe communicatie tussen twee knopen, is het mogelijk dat de virtuele machine geen ondersteuning heeft voor dit soort berichten. voorzien worden.
Door een uitbreiding van de instructieset kan ondersteuning hiervoor
Er moet echter ook de mogelijkheid zijn om de aankomst van dit type
bericht te signaleren en de uitvoering van een script te starten dat het bericht afhandelt. Dit kan door een nieuwe gebeurtenis en een overeenkomstige uitvoeringsomgeving (een context) aan de virtuele machine toe te voegen.
5.3.3
Meerdere applicaties
Een sensornetwerk moet verschillende applicaties gelijktijdig kunnen ondersteunen. Het sensornetwerk in een kantoorgebouw wordt bijvoorbeeld gebruikt voor zowel de beveiliging als de klimaatregeling van het gebouw. Deze verschillende applicaties mogen elkaar niet hinderen. Alle applicaties moeten de indruk krijgen dat ze het sensornetwerk voor zich alleen hebben. De noden van verschillende applicaties zullen in veel gevallen vrij sterk verschillen.
De
ideale instructieset voor de ene applicatie kan totaal ongeschikt zijn voor de andere applicatie. De instructieset moet dus ofwel heel algemeen blijven, ofwel moet het mogelijk zijn om aan elke applicatie een andere instructieset aan te bieden. Ondersteuning voor meerdere virtuele machines voldoet aan beide noden. De applicaties kunnen elk in hun eigen virtuele machines uitvoeren. Zo krijgen ze de indruk dat ze de enige applicatie in het sensornetwerk zijn. Tegelijkertijd kan de instructieset van de virtuele machine waarin een applicatie uitvoert, worden aangepast aan de speci eke noden van de applicatie.
5.4 5.4.1
Vereisten Functionele vereisten
Basisfunctionaliteit
Het spreekt voor zich dat de basisfunctionaliteit van traditionele vir-
tuele machines voor sensornetwerken, zoals Maté, zeker aanwezig moet zijn in het systeem. Het moet dus minstens mogelijk zijn om de virtuele machines te herprogrammeren met scripts die door het systeem automatisch worden verspreid naar alle knopen in het sensornetwerk.
HOOFDSTUK 5.
42
ANALYSE
Aanpasbare instructieset
Flexibele virtuele machines zoals wij ze beogen, hebben bo-
vendien een aanpasbare instructieset.
Er moeten zowel instructies kunnen toegevoegd als
verwijderd kunnen worden. Deze functionaliteit kan aangeboden worden via de dynamisch te laden en te verwijderen modules van het besturingssysteem. Elke instructie in een aparte module implementeren zou echter leiden tot een explosie van modules. De instructies worden dus best gegroepeerd in bibliotheken. Wanneer slechts één instructie moet aangepast worden, moet dan wel een ganse bibliotheek worden geladen via het netwerk.
Aanpassingen aan de instructieset zijn echter veel minder frequent nodig dan
wijzigingen aan de scripts die erin worden uitgedrukt.
Dynamische contexten
Bij traditionele virtuele machines, zoals Maté, kunnen de gebeur-
tenissen die de uitvoering van een script initiëren en de contexten waarin deze uitvoering gebeurt reeds statisch worden aangepast aan de noden van de applicatie. Wanneer de virtuele machines dynamisch kunnen gewijzigd worden, is het heel moeilijk om te voorspellen welke contexten nodig zullen zijn. Deze moeilijkheid kan verholpen worden door de contexten en de bijhorende gebeurtenissen dynamisch aanpasbaar te maken.
Meerdere virtuele machines
Meerdere virtuele machines bieden zoals hoger aangehaald
de mogelijkheid om applicaties van elkaar te isoleren. Bovendien kan zo de instructieset van elke virtuele machine worden aangepast aan de speci eke applicatie die er in draait. Om de mogelijkheden van meerdere virtuele machines volledig te kunnen benutten, moet het mogelijk zijn ze
dynamisch toe te voegen en te verwijderen.
Het is namelijk onmogelijk om
te voorspellen hoeveel en welke virtuele machines er nodig zullen zijn tijdens de levensduur van het sensornetwerk.
Verschillende instructiesets
De instructiesets van de verschillende virtuele machines moe-
ten kunnen verschillen. Dit kan gerealiseerd worden door de instructies van een virtuele machine dynamisch te koppelen aan de operatiebibliotheek die ze implementeert. Bovendien is het nodig dat deze koppeling kan aangepast worden tijdens de werking van het systeem. Wanneer een bibliotheek door twee virtuele machines wordt gebruikt, moet het namelijk mogelijk zijn de bibliotheek in één van beide virtuele machines te vervangen door een andere implementatie, zonder dat de andere virtuele machine hier iets van merkt. Wanneer de koppeling kan aangepast worden, dan kan dit gerealiseerd worden door een nieuwe bibliotheek te laden en de koppeling aan te passen zodat naar de nieuwe bibliotheek wordt verwezen.
Appendix A werkt enkele use cases uit die representatief zijn voor de functionaliteit die het systeem moet implementeren. Enkel use cases voor de functionaliteit die nieuw is ten opzichte van de traditionele virtuele machines voor sensornetwerken (zoals Maté) zijn opgenomen. Figuur 5.2 toont het use case diagram voor deze use cases.
Nieuwe instructie(s)
is een voorbeeld van een use case waarin de gebruiker de instructie-
set van een virtuele machine wenst aan te passen. secundaire use cases:
Wijzig VM
Laad operatiebibliotheek
Deze use case maakt gebruik van twee
beschrijft het laden van de operatiebibliotheek,
is nodig om de koppeling tussen de instructies en de bibliotheken te wijzigen. Het
verwijderen of aanpassen van een instructieset verlopen analoog.
Nieuwe context(en)
behandelt het wijzigen van de contexten van een virtuele machine.
Uiteraard is hiervoor de use case
Wijzig VM
nodig. Contexten verwijderen is analoog.
HOOFDSTUK 5.
43
ANALYSE
Figuur 5.2: Use case diagram
Laad nieuwe VM
beschrijft het toevoegen van een virtuele machine aan het systeem. Een
virtuele machine verwijderen verloopt volledig analoog.
5.4.2
Niet-functionele vereisten
Aanpasbaarheid
De functionele vereisten zijn heel sterk gericht op de aanpasbaarheid van
het systeem. Aanpasbaarheid is echter ook een belangrijke niet-functionele vereiste. Het is onmogelijk om alle eisen te voorzien die in de toekomst zullen opgelegd worden aan middleware voor sensornetwerken. Het is dan ook wenselijk hierop te anticiperen door het systeem zelf zo aanpasbaar mogelijk te bouwen. Op die manier kunnen wijzigende vereisten in de toekomst makkelijker worden aangepakt.
E ciëntie
Om de kostprijs en het energieverbruik te beperken is de hardware van sensor-
knopen beperkt (zie Sectie 2.1). Het is dus belangrijk dat de schaarse middelen zo e ciënt mogelijk gebruikt worden.
De e ciëntie waarmee het systeem de hardware aanwendt, be-
paalt ook het energieverbruik en beïnvloedt dus de levensduur van het sensornetwerk. Vooral communicatie is uitputtend voor de energievoorzieningen en moet dus zo e ciënt mogelijk gebeuren.
Beschikbaarheid
Een derde niet-functionele vereiste is de beschikbaarheid.
Terwijl één
virtuele machine wordt aangepast, moeten de andere virtuele machines beschikbaar blijven. Dit is noodzakelijk opdat de continuïteit van de applicaties die in de andere virtuele machines draaien gegarandeerd blijft.
Schaalbaarheid
Tenslotte moet er rekening worden gehouden met schaalbaarheid van de
gebruikte algoritmen. Wanneer het aantal sensorknopen in het netwerk toeneemt, moet het systeem in staat blijven om op e ciënte wijze de toestand van de virtuele machines in het netwerk te onderhouden.
Hoofdstuk 6
Architectuur Hoofdstuk 5 onderzocht de functionele en niet-functionele vereisten voor de dynamische virtuele machines die deze thesis beoogt. Dit hoofdstuk werkt een architectuur uit die toelaat de functionele vereisten te verwezenlijken en die zo goed mogelijk rekening houdt met de niet-functionele vereisten. De architectuur is gebaseerd op de architectuur van Maté, een traditionele virtuele machine voor sensornetwerken (Sectie 4.1). Net zoals bij Maté valt de architectuur uiteen in twee grote delen: de componenten die op de sensorknopen aanwezig zijn en een toolchain die zich op de computer van de gebruiker bevindt. Deze thesis concentreert zich vooral op het gedeelte dat op de sensorknopen werkt. Sectie 6.1 gaat uitgebreid in op de architectuur van dit gedeelte. Het systeem is echter moeilijk te gebruiken zonder tools om de functionaliteit van het gedeelte op sensorknopen aan te spreken. Deze tools komen aan bod in Sectie 6.2. Sectie 6.3 tenslotte bespreekt enkele sequentiediagrammen die de interacties tussen de verschillende componenten verduidelijkt.
6.1
Het gedeelte op de sensorknopen
Het deel van het systeem op de sensorknopen (Figuur 6.1) is verantwoordelijk voor twee zaken. Enerzijds verzorgt het de runtime ondersteuning van de virtuele machines. Anderzijds zorgt het er voor dat de toestand van het systeem consistent blijft in het ganse sensornetwerk. De eerste taak wordt verzorgd door vier componentengroepen:
Capsule store, VM store,
1 Operation store en Engine. De Viruscomponent neemt de tweede taak op zich. 6.1.1
Componenten
Runtime ondersteuning Capsule Store De Capsule Store omvat de capsules (bytecode fragmenten) en een Capsule Manager. De capsules zijn de bytecode versies van scripts die de gebruiker van het systeem geschreven heeft. Via de capsules kan de gebruiker de virtuele machines dynamisch herprogrammeren. De Capsule Manager verzorgt het beheer van de capsules. Hij houdt onder meer bij welke versie van welke capsules er aanwezig is.
1
De naamgeving is gebaseerd op de naam van de TinyOS-module in Maté die het Trickle algoritme imple-
menteert.
44
HOOFDSTUK 6.
ARCHITECTUUR
45
Figuur 6.1: De architectuur van het gedeelte op de sensorknopen
De Capsule Store is overgenomen uit de architectuur van Maté. In Maté had hij echter nog een bijkomende taak. De Capsule Store stond er ook in voor de gedistribueerde consistentie van de aanwezige capsules. Deze functionaliteit is nu in een nieuwe component ondergebracht (Virus, zie later) die dit ook voor de operaties en de virtuele machines doet.
Operation Store
De Operation Store is een component die niet aanwezig is in de archi-
tectuur van Maté.
In Maté zijn de operaties statisch verbonden met de virtuele machine.
Wanneer men dynamisch operatiebibliotheken wil toevoegen en verwijderen is er echter nood aan een component die dit in goede banen leidt. De Library Manager vervult deze taak en houdt daarvoor een boekhouding bij van de aanwezige bibliotheken. De operatiebibliotheken worden door de gebruikers van het systeem geladen in de Operation Store. Op die manier bepalen de gebruikers welke operaties aanwezig zijn en dus ook welke instructies in de instructiesets van de virtuele machines kunnen opgenomen worden. De operatiebibliotheken worden geïmplementeerd als modules voor het modulaire besturingssysteem.
De identi catie van deze modules zal verschillen van de identi catie die de
virtuele machines gebruiken voor een bibliotheek. De Library Manager houdt daarom ook bij welke module hoort bij welke bibliotheek.
VM Store
De VM Store bestaat uit de VM Manager en de Concurrency Manager. De VM
Manager beheert de verschillende virtuele machines die in het systeem aanwezig zijn. Uiteraard bestond deze component niet in de architectuur van Maté, aangezien Maté slechts één virtuele machine tegelijk ondersteunt. De virtuele machines bevatten alle informatie die nodig is voor hun werking. Dit houdt onder meer in dat er informatie is over de aanwezige contexten en
HOOFDSTUK 6.
46
ARCHITECTUUR
over de koppeling van de instructieset van de virtuele machine met de operatiebibliotheken. De Concurrency Manager vervult een gelijkaardige rol als bij Maté. Deze component zorgt ervoor dat contexten kunnen uitvoeren op een race- en deadlockvrije manier. De Concurrency Manager doet zijn werk nu echter voor alle virtuele machines die in de VM Store aanwezig zijn. De contexten van verschillende virtuele machines hinderen elkaar nooit en kunnen altijd in parallel worden uitgevoerd. Contexten van een zelfde virtuele machine die tegelijk uitvoerbaar zijn kunnen elkaar echter wel hinderen wanneer de instructieset globale variabelen toelaat.
Engine
De Engine omvat een Scheduler en een Event Manager.
De Scheduler regelt de
verdeling van de uitvoeringstijd over de uitvoerbare contexten van de verschillende virtuele machines. De taken van de Scheduler zijn dus analoog als bij Maté, alleen moet de Scheduler nu contexten van meerdere virtuele machines aankunnen. Contexten beginnen hun uitvoering na een gebeurtenis. De Event Manager biedt diensten voor het beheer van de gebeurtenissen over de grenzen van een virtuele machine heen.
De
Event Manager biedt bijvoorbeeld de mogelijkheid om een timer te starten en een opgegeven gebeurtenis te genereren wanneer die timer a oopt.
Gedistribueerde consistentie Virus Virus implementeert de logica om de instanties van het systeem op de verschillende knopen consistent te houden met elkaar.
Wanneer de toolchain informatie in het netwerk
injecteert, zorgt Virus er voor dat deze informatie verspreid wordt over alle knopen in het netwerk (zoals een virus). Wanneer een knoop een tijd onbereikbaar geweest is, of wanneer een nieuwe knoop aan het netwerk wordt toegevoegd, zorgt Virus ervoor dat de toestand van het systeem op deze knoop terug up to date wordt gebracht. Bij Maté was deze functionaliteit vervat in de Capsule Store omdat enkel capsules in het netwerk moesten verspreid worden.
Bij de dynamisch aanpasbare virtuele machines, moet
ook informatie over de virtuele machines en over de operatiebibliotheken worden verspreid. Daarom is deze functionaliteit in een aparte component ondergebracht. De component omvat echter alleen de functionaliteit voor de verspreiding van de informatie.
De informatie zelf
wordt bijgehouden in de Capsule Store, de VM Store en de Operation Store. De architectuur legt niet op welk algoritme Virus moet gebruiken om de gedistribueerde consistentie te bekomen. Het algoritme moet echter goed worden gekozen zodat de overhead die ermee gepaard gaat beperkt blijft.
Wanneer deze keuze niet zorgvuldig gebeurt kan ze
ervoor zorgen dat de schaalbaarheid van het volledige systeem in het gedrang komt.
6.1.2
Interfaces
Statusinterfaces voor Virus De Capsule Store, de VM Store en de Operation Store hebben allemaal een interface die door Virus gebruikt wordt om informatie te weten te komen over de toestand van het systeem: respectievelijk Capsule Status Interface (CSI), VM Status Interface (VMSI) en Operation Status Interface (OSI). Langs deze interfaces vraagt Virus informatie over het aantal en de versies van respectievelijk de capsules, de virtuele machines en de operatiebibliotheken. Virus gebruikt deze interface ook om bijvoorbeeld een capsule op te halen wanneer hij deze wil versturen naar een naburige knoop. Wanneer een update aankomt bij Virus, gebruikt Virus eveneens deze interfaces om de gepaste component daarvan op de hoogte te brengen.
HOOFDSTUK 6.
47
ARCHITECTUUR
Capsule Store De Capsule Store heeft naast de Caspule Status Interface nog twee andere interfaces. Deze worden beide gebruikt door de VM Store. De Capsule Interface (CI) bevat methodes om de capsules te benaderen, bijvoorbeeld om een byte op een bepaalde positie in een capsule op te halen. De Capsule Management Interface (CMI) is de toegang tot de capsule manager. Hij bevat methodes om een capsule toe te voegen aan of te verwijderen uit de Capsule Manager.
VM Store De VM Store is zowat de centrale draaischijf van het systeem en heeft dan ook heel wat interfaces naar de andere componenten.
Naast Virus gebruiken ook de Capsule Store, de
Operation Store en de Engine interfaces van de VM Store. De VM Retasking Interface (VMRI) bevat methodes die door de
Capsule Store gebruikt
worden wanneer een geüpdatete capsule aankomt. De interface laat toe dat de Capsule Store een virtuele machine stopt tijdens de aanpassing van een capsule en daarna de virtuele machine herstart. De Capsule Store gebruikt de interface ook om een nieuwe capsule door te geven aan de Concurrency Manager die onderzoekt welke gedeelde variabelen de capsule gebruikt. De interface die de VM Store aanbiedt aan de
Operation Store bevat methodes waarmee
de operatiebibliotheken toegang krijgen tot de virtuele machines.
Deze VM Data Interface
(VMDI) omvat methodes om een operand van de operandstapel te halen, methodes om een globale variabele te lezen of te schrijven, . . . De
Engine
gebruikt twee interfaces van de VM Store.
De Scheduler gebruikt de VM
Execution Interface (VMEI) om onder meer de volgende instructie op te halen die in een context moet uitgevoerd worden en om te weten te komen bij welke bibliotheek deze instructie ter uitvoering moet aangeboden worden.
De interface bevat ook een methode waarmee de
Scheduler kan laten weten wanneer de uitvoering van een context beëindigd is. De VM Event Signaling Interface (VMESI) wordt door de Event Manager gebruikt om gebeurtenissen te signaleren.
Operation Store De Operation Store heeft twee interfaces die door zowel de VM Store als de Engine worden gebruikt.
De Operation Interface (OI) is de interface die door de operatiebibliotheken
moet worden geïmplementeerd. Enerzijds biedt hij de mogelijkheid om de uitvoering van een instructie te starten.
Anderzijds kan de interface gebruikt worden om informatie over een
instructie op te vragen. Het systeem kan opvragen hoeveel bytes een instructie beslaat en of een instructie gebruik maakt van globale variabelen. De Library Management Interface (LMI) is de interface naar de Library Manager.
Hij
wordt gebruikt om op te vragen welke operatiebibliotheken aanwezig zijn. Via deze interface kan het systeem ook te weten komen door welke module een gegeven bibliotheek wordt geïmplementeerd.
Engine De Scheduler bevat een Scheduling Interface (SI) die door de VM Store wordt gebruikt om een context door te geven die uitgevoerd moet worden. Deze interface wordt daarnaast ook
HOOFDSTUK 6.
48
ARCHITECTUUR
Figuur 6.2: De tools om een operatiebibliotheek te laden (links) en een virtuele machine aan te passen (rechts)
door de operatiebibliotheken gebruikt om aan te geven dat de uitvoering van een operatie beëindigd is. Verder heeft Engine nog een Event Management Interface (EMI) die methodes bevat om de diensten aan te spreken die door de Event Manager geboden worden. Er zijn onder meer methodes om een timer te starten en methodes om gebeurtenissen te genereren.
6.2
Toolchain
De software op de knopen kan verschillende aanpassingen ondergaan. Deze aanpassingen moeten echter eerst in het netwerk gebracht worden. Deze taak wordt vervuld door de toolchain die de brug vormt tussen de gebruiker en de software op de sensorknopen.
Een virtuele machine gebruiken De opbouw van de tools om een virtuele machine te gebruiken blijft dezelfde als bij de Scripter tool van Maté (Figuur 4.1, pagina 27). De werking van de assembler is echter licht verschillend.
Bij de omzetting van de assembleerinstructies naar bytecode moet namelijk rekening
worden gehouden met de ontkoppeling tussen de instructieset van een virtuele machine en de operatiebibliotheken in het systeem. Een assembleerinstructie kan in verschillende virtuele machines door een verschillende bytecode worden voorgesteld.
Een virtuele machine wijzigen Het tweede grote deel van de toolchain van Maté behelst het bouwen van een virtuele machine uit zijn samenstellende delen.
Dit stuk van de toolchain is niet meer bruikbaar omdat het
systeem de virtuele machines dynamisch maakt. Er zijn andere tools nodig om de gebruiker toe te laten deze dynamische aanpassingen door te voeren.
Een operatiebibliotheek laden.
Figuur 6.2 toont aan de linkerkant hoe een operatie-
bibliotheek geladen wordt. Deze operatiebibliotheek is reeds in een uitvoerbare vorm. Deze uitvoerbare vorm kan bijvoorbeeld tot stand komen doordat een extra tool de uitvoerbare
HOOFDSTUK 6.
49
ARCHITECTUUR
Figuur 6.3: Aankomst capsule
vorm samenstelt uit een platformonafhankelijke beschrijving van de operaties, rekening houdend met informatie over het platform.
Deze thesis maakt echter verder abstractie van de
manier waarop de uitvoerbare vorm tot stand komt.
Een virtuele machine wijzigen.
De rechterzijde van Figuur 6.2 toont hoe de beschrij-
ving van een virtuele machine in het netwerk wordt gebracht. Deze beschrijving wordt gemaakt door de gebruiker van het systeem. Ze bevat informatie over de contexten die aanwezig zijn en over de operatiebibliotheken die in de instructieset zijn opgenomen. De Injectorcomponenten van al deze tools pakken de informatie in in berichten die in het netwerk kunnen gestuurd worden.
Deze berichten worden in het netwerk gebracht door ze
af te leveren bij de Viruscomponent op een knoop die verbonden is met de computer van de gebruiker. De Viruscomponent op deze gatewayknoop verspreidt de informatie vervolgens naar het ganse sensornetwerk.
6.3
Sequentiediagrammen
De verschillende componenten in de architectuur interageren via de beschreven interfaces om de gevraagde functionaliteit de realiseren. Deze sectie bespreekt deze interacties aan de hand
van enkele sequentiediagrammen. Aankomst capsule, Aankomst van een VM beschrijving en Operatiebibliotheek laden verduidelijken wat er gebeurt wanneer wijzigingen aan het systeem worden aangebracht. Een context uitvoeren gaat wat dieper in op de interacties tijdens de uitvoering van de bytecode in het systeem.
6.3.1
Aankomst capsule
De aankomst van een capsule (Figuur 6.3) bij Virus wordt geïnitieerd door de toolchain of door Virus op een andere knoop. Wanneer de volledige capsule aangekomen is, geeft Virus deze door aan de Capsule Manager. Capsule Manager stopt de virtuele machine waarvoor de capsule bestemd is.
Daarna
installeert Capsule Manager de capsule en laat ze analyseren door de Concurrency Manager.
HOOFDSTUK 6.
ARCHITECTUUR
50
Figuur 6.4: Aankomst van een VM beschrijving
De Concurrency Manager controleert welke globale variabelen de capsule gebruikt en slaat deze informatie op om ze later te gebruiken. Tenslotte herstart Capsule Manager de virtuele machine.
6.3.2
Aankomst van een VM beschrijving
Wanneer een virtuele machine wordt toegevoegd of er een wijziging wordt aangebracht aan een bestaande virtuele machine, komt er een beschrijving van de betreende virtuele machine aan bij Virus (Figuur 6.4).
Dit bericht komt van de toolchain of van Virus op een andere
knoop. Virus onderzoekt het bericht om het versienummer te controleren. Virus geeft de beschrijving van de virtuele machine door aan de VM Manager als de virtuele machine in de VM Store een lager versienummer heeft of de virtuele machine nog niet aanwezig is in het systeem. Als het een nieuwe virtuele machine betreft, maakt de VM Manager de virtuele machine aan en voegt ze toe in zijn gegevensstructuren. Daarna geeft hij de beschrijving door aan de nieuwe virtuele machine die nog in een standaard toestand is. De virtuele machine stopt haar werking en past haar toestand aan volgens de nieuwe beschrijving.
De verwijzingen naar de bibliotheken die in de instructieset van de virtuele
machine zijn opgenomen, worden aangepast en de nodige contexten worden verwijderd of toegevoegd. Daarna herstart de virtuele machine.
6.3.3
Operatiebibliotheek laden
Een operatiebibliotheek wordt geïmplementeerd als een module voor het besturingssysteem. Virus verspreidt de module en laadt ze op de knopen. Nadat de module geladen is, initialiseert
HOOFDSTUK 6.
51
ARCHITECTUUR
Figuur 6.5: Operatiebibliotheek laden
Virus de module. Vervolgens meldt de operatiebibliotheek zich aan bij de Library Manager (Figuur 6.5). De Library Manager verwerkt de aanmelding en brengt alles in gereedheid om de bibliotheek te kunnen gebruiken. Daarna brengt de Library Manager het systeem op de hoogte door een globale gebeurtenis te genereren via de Event Manager. De Event Manager brengt de VM Manager op de hoogte van deze gebeurtenis. De VM Manager reageert hierop door alle virtuele machines te herstarten die een bibliotheek missen.
6.3.4
Context uitvoeren
Een virtuele machine start de uitvoering van een context (Figuur 6.6) door de context door te geven aan de Concurrency Manager. De Concurrency Manager controleert of alle globale variabelen kunnen gereserveerd worden. Wanneer dit het geval is, wordt de context doorgegeven aan de Scheduler. In het andere geval plaats Concurrency Manager de context in een wachtrij. De Scheduler voert zijn scheduling algoritme uit om te bepalen uit welke context een instructie wordt uitgevoerd. De Scheduler vraagt vervolgens aan de virtuele machine waartoe de context behoort in welke bibliotheek de instructie moet uitgevoerd worden.
Vervolgens
raadpleegt de Scheduler de Library Manager om te weten te komen door welke module deze bibliotheek geïmplementeerd wordt. De Scheduler stuurt daarna de opdracht naar de operatiebibliotheek om de operatie uit te voeren. De bibliotheek brengt de Scheduler op de hoogte wanneer de uitvoering van de instructie beëindigd is.
Daarop voert Scheduler opnieuw het
scheduling algoritme uit en worden de vorige stappen herhaald. Wanneer een context de
halt
instructie heeft uitgevoerd, verwittigt Scheduler de Concur-
rency Manager. De Concurrency Manager geeft de reservaties van de context vrij en controleert of er contexten in de wachtrij staan die nu uitvoerbaar worden. Indien dit het geval is, worden deze doorgegeven aan de Scheduler.
HOOFDSTUK 6.
ARCHITECTUUR
52
Figuur 6.6: Context uitvoeren
6.4
Besluit
De architectuur die in dit hoofdstuk werd gepresenteerd bouwt verder op een architectuur die zijn degelijkheid reeds bewezen heeft. De architectuur van Maté, een traditionele virtuele machine voor sensornetwerken, werd uitgebreid om de bijkomende vereisten die werden vooropgesteld in Hoofdstuk 5 te kunnen ondersteunen. De architectuur laat toe om op een exibele manier de instructieset van een virtuele machine aan te passen. De architectuur maakt het eveneens mogelijk verschillende virtuele machines te ondersteunen en die van elkaar te isoleren, zonder daarom de gemeenschappelijke functionaliteit te dupliceren. Er werd naar gestreeft de verschillende belangen in aparte componenten onder te brengen om zo te komen tot een grote samenhang en een lage koppeling. Dit komt de aanpasbaarheid van de architectuur op lange termijn ten goede.
Hoofdstuk 7
Prototype implementatie Dit hoofdstuk beschrijft de prototype implementatie, DAViM
1 gedoopt, die gemaakt werd om
de architectuur uit Hoofdstuk 6 te valideren. Sectie 7.1 bespreekt hoe de architectuur verder werd uitgewerkt om tot de prototype implementatie te komen. De implementatie werd gemaakt met behulp van Sensor Operating System (SOS) en getest op MICAz-sensorknopen.
Sectie 7.2 bespreekt kort het hardwareplatform en de tools die
beschikbaar zijn om een SOS-implementatie te testen via simulatie. De implementatie was vooral geconcentreerd rond het gedeelte op de sensorknopen. Van de toolchain werd enkel een elementaire implementatie voorzien van de zaken die nodig zijn om het gedeelte op de knopen te kunnen testen. Sectie 7.4 legt aan de hand van een eenvoudig voorbeeld uit hoe het systeem gebruikt kan worden met behulp van deze basistools. Tenslotte formuleert Sectie 7.5 een besluit.
7.1
Uitwerking
Hoofdstuk 6 bespreekt de architectuur van het systeem. Deze sectie werkt deze architectuur verder uit en bespreekt enkele keuzes die gemaakt werden bij de bouw van de prototype implementatie.
7.1.1
Hergebruik van bestaande code
In de CVS-repository
2 van het Networked and Embedded Systems Lab (NESL) van de Uni-
versiteit van Californië in Los Angeles (UCLA), tevens het labo waar SOS wordt ontwikkeld, is een versie van Maté voor het SOS-besturingssysteem te vinden. Er is in de literatuur echter nog niets over dit systeem te vinden. Omdat de architectuur van het systeem in deze thesis signi cante wijzigingen heeft ondergaan ten opzichte van de architectuur van Maté, werd besloten om niet op dit systeem verder te bouwen, maar de prototype implementatie vanaf nul te beginnen. Er werd in de uitwerking van de architectuur echter wel rekening gehouden met het bestaan van deze code. De algoritmes werden zo gekozen dat de implementaties ervan in deze code konden worden hergebruikt. Meer in het bijzonder gaat het over algoritmes in Virus, Concurrency Manager en Scheduler. Verder werd de implementatie van een wachtrij overgenomen
1 2
Dynamisch Aanpasbare Virtuele Machines http://cvs.nesl.ucla.edu/cvs/viewcvs.cgi/ASVM/
53
HOOFDSTUK 7.
PROTOTYPE IMPLEMENTATIE
54
en werd code voor de locks die in een virtuele machine aanwezig zijn voor gebruik door de Concurrency Manager aangepast aan de gegevensstructuren van de prototype implementatie.
7.1.2
Algoritme voor gedistribueerde consistentie
De architectuur legt geen speci ek algoritme op dat gebruikt moet worden voor het bewaren van de gedistribueerde consistentie.
Er moet echter wel zorg voor gedragen worden dat de
schaalbaarheid van het systeem niet in het gedrang komt. Voor de prototype implementatie is dan ook gekozen voor twee algoritmes waarvan in de literatuur wordt bewezen dat ze de gevraagde functionaliteit leveren op een schaalbare manier. De operatiebibliotheken worden geïmplementeerd als modules voor het besturingssysteem, in dit geval SOS. Het algoritme dat SOS gebruikt om modules in het sensornetwerk te verspreiden, MOAP [38], biedt de gevraagde gedistribueerde consistentie en is voldoende schaalbaar. Er werd dan ook voor geopteerd om deze functionaliteit te hergebruiken voor het verspreiden van de operatiebibliotheken. Voor de verspreiding van capsules gebruikt Maté het Trickle-algoritme [27]. Zoals reeds in Sectie 4.1.4 werd aangehaald, geeft ook dit algoritme de gevraagde functionaliteit en schaalbaarheid. Dit algoritme werd dan ook gekozen voor gebruik in Virus om de capsules en de virtuele machines consistent te houden. Deze keuze had bovendien als voordeel dat de bestaande implementatie van dit algoritme (zie Sectie 7.1.1) voor een stuk kon worden hergebruikt.
7.1.3
Ontkoppeling tussen instructiesets en operatiebibliotheken
De ontkoppeling tussen de instructiesets van de virtuele machines en de operatiebibliotheken werd verwezenlijkt door de invoering van de notie lokale bibliotheek. Een lokale bibliotheek is een bibliotheek die binnen één enkele virtuele machine gekend is, en is niet meer dan een verwijzing naar een echte operatiebibliotheek. Door deze verwijzingen aan te passen kan de verzameling bibliotheken waaruit een instructieset bestaat dynamisch gewijzigd worden en kunnen bovendien de instructiesets van de verschillende virtuele machines gedierentieerd worden. Het is bijvoorbeeld mogelijk dat lokale bibliotheek L in een virtuele machine verwijst naar bibliotheek X en in een andere virtuele machine naar bibliotheek Y. De aanduiding van een lokale bibliotheek wordt gecodeerd in de bytecode van een instructie. Er werd gekozen om in de prototype implementatie 3 bits te voorzien voor de bibliotheekaanduiding. Dit laat toe om tot 8 lokale bibliotheken te hebben in een virtuele machine. Een bytecode is in de prototype implementatie 1 byte lang, dus blijven er voor het aanduiden van de operatie 5 bits over. Een operatiebibliotheek kan dus tot 32 instructies bevatten. Deze opsplitsing is een afweging tussen granulariteit en kost. Veel bits voor de bibliotheekaanduiding heeft tot gevolg dat er weinig operaties in een bibliotheek zijn. Op deze manier kunnen de operaties met een jne granulariteit gewijzigd worden. Dit geeft echter aanleiding tot meer modules en meer geheugen voor de verwijzingen in de virtuele machines.
7.1.4
Gelijktijdigheid
De Concurrency Manager zorgt ervoor dat de contexten van een virtuele machine race- en deadlock vrij kunnen uitvoeren. Hiervoor werd het algoritme dat Maté gebruikt overgenomen. Een deel van de implementatie ervan in het systeem dat in Sectie 7.1.1 aan bod komt, werd eveneens hergebruikt.
HOOFDSTUK 7.
55
PROTOTYPE IMPLEMENTATIE
Figuur 7.1: De dynamische gegevensstructuur van een virtuele machine
Het algoritme gebruikt een conservatieve twee fasen vergrendeling (conservative two phase locking) om te garanderen dat de uitvoering deadlock vrij is. Dit betekent dat een context geblokkeerd wordt tot alle locks vrij zijn die hij tijdens zijn uitvoering nodig zal hebben. Zodra al deze locks vrij zijn, worden ze atomisch toegekend aan de context en begint de context zijn uitvoering. Om de implementatie van het algoritme eenvoudig te houden, moet het aantal variabelen waarvoor locking nodig is, op voorhand bepaald zijn. Bij Maté gebeurt dit door een statische analyse van de virtuele machine.
In de prototype implementatie in deze thesis wordt er
bij compilatie een bovengrens vastgelegd voor het aantal locks per virtuele machine om de implementatie van de Concurrency Manager eenvoudig te houden.
7.1.5
Gegevensstructuren
Figuur 7.1 toont de gegevensstructuur voor een virtuele machine.
Deze gegevensstructuur
wordt dynamisch opgebouwd en/of aangepast wanneer een virtuele machine wordt toegevoegd, verwijderd of gewijzigd.
Virtuele machine
Een virtuele machine bevat een aantal verwijzingen naar globale varia-
belen en daarmee geassocieerd een lock voor de Concurrency Manager. Zoals in Sectie 7.1.4 werd toegelicht, is er een bovengrens op het aantal locks. De operatiebibliotheken kunnen deze beperking echter omzeilen. Ze kunnen namelijk het type bepalen van de globale variabelen waarnaar verwezen wordt. Ze kunnen dus meer globale variabelen voorzien door te verwijzen naar een rijtype. De verwijzingen in de virtuele machine bepalen dus enkel de granulariteit waarmee globale variabelen worden gereserveerd.
HOOFDSTUK 7.
56
PROTOTYPE IMPLEMENTATIE
De virtuele machine bevat ook de verwijzingen naar de bibliotheken. Per lokale bibliotheek, wordt een verwijzing bijgehouden naar de bibliotheek die ermee overeen komt. Uiteraard kan deze verwijzingstabel dynamisch gewijzigd worden.
Context
Een virtuele machine bevat ook verwijzingen naar de contexten die deel uit maken
van de virtuele machine.
Omgekeerd heeft een context ook een verwijzing naar de virtuele
machine waartoe hij behoort.
Dit is onder meer nodig voor de operatiebibliotheken die de
globale variabelen van de virtuele machine lezen of schrijven. Een instructie wordt uitgevoerd in een context, dus moet de operatiebibliotheek in staat zijn uit de context de virtuele machine af te leiden waar hij de globale variabele moet lezen of schrijven. Een context bevat ook informatie voor de Concurrency Manager. Deze informatie bestaat uit drie sets waarin informatie wordt bijgehouden over de locks die een context nodig heeft. De
heldSet
is de set locks die aan de context toegewezen zijn. De
die een context nog moet bekomen. De
releaseSet
acquireSet
is de set locks
tenslotte is de set locks die de context niet
meer nodig heeft en dus mogen vrijgegeven worden. De lokale variabelen die een context bijhoudt, zijn net als bij de globale variabelen verwijzingen naar variabelen van een onbepaald type. Het zijn opnieuw de operatiebibliotheken die het type bepalen. Ook de operandstapel van de context voorziet ruimte voor verwijzingen naar variabelen van een op voorhand onbepaald type.
Capsule een
De gegevensstructuur van een capsule bestaat uit ruimte voor de bytecode en
useSet.
Deze useSet wordt door Virus niet mee verspreid, maar is bestemd voor de
Concurrency Manager. Deze onderzoekt een capsule nadat ze is aangekomen op de knoop en slaat in de
7.1.6
useSet
informatie op over de globale variabelen die de capsule gebruikt.
Beperkingen
In de prototype implementatie wordt het aantal virtuele machines beperkt tot 8. Per virtuele machine zijn maximum 32 contexten mogelijk. Deze keuze is gemotiveerd vanuit de vaststelling dat deze beperking op de huidige platformen niet bindend is.
Het geheugen op de huidige
generische platformen is de beperkende factor. Er is namelijk voor elke virtuele machine en elke context een dynamische gegevensstructuur in het geheugen nodig. De implementatie is zo gemaakt dat deze keuze makkelijk kan aangepast worden als ze de beperkende factor wordt. Dit kan het geval worden wanneer de toekomstige hardwareplatformen genoeg geheugen aan boord hebben om meer dan 8 virtuele machines en/of meer dan 32 contexten per virtuele machine te ondersteunen. De keuze voor 8 bibliotheken in een virtuele machine (zie Sectie 7.1.3), gecombineerd met de keuze om 8 virtuele machines te ondersteunen, geeft aanleiding tot potentieel 64 verschillende operatiebibliotheken.
De prototype implementatie ondersteunt daarom maximaal 64
operatiebibliotheken. Wanneer het aantal virtuele machines wordt uitgebreid, kunnen er problemen ontstaan om het maximale aantal potentieel verschillende bibliotheken te ondersteunen omdat het aantal mogelijke modules in SOS beperkt is.
Er zal dan een beperking moeten opgelegd worden
die kleiner is dan dit maximum. De virtuele machines zullen dan voor een deel overlappen in hun bibliotheken.
Dit is geen onredelijke beperking omdat bepaalde functionaliteit door
heel veel applicaties nodig is. De verschillen zijn vaak beperkt tot een subset van de totale functionaliteit.
HOOFDSTUK 7.
PROTOTYPE IMPLEMENTATIE
57
Figuur 7.2: MICAz-sensorknoop (met MICA-sensorbord) ter grootte van 2 AA batterijen
Synchrone en asynchrone interacties Synchrone interactie verloopt in SOS via de oproep van een functie die door de doelmodule geëxporteerd is. Voor elke geëxporteerde functie is geheugen nodig in de SOS-kernel, namelijk de grootte van een pointer. Voor de avr architectuur die gebruikt wordt in de MICAz-knopen is dit 2 bytes. Bovendien gebruiken de functieoproepen ruimte op de stapel (stack). Er is dus een risico voor stapeloverloop (stack over ow). Daarom gebruikt de prototype implementatie zoveel mogelijk asynchrone communicatie via berichten. Deze berichten hebben de uitvoering van een afhandelingsfunctie in de ontvangende module tot gevolg. Ze zijn met andere woorden een vorm van asynchrone functieoproepen. Functieoproepen worden enkel gebruikt voor zaken die absoluut synchroon moeten gebeuren.
Voorbeelden zijn het stoppen van een virtuele machine of functieoproepen die een
resultaat teruggeven dat nodig is in de rest van de uitvoering van de oproepende methode.
7.2
Platform en testomgevingen
MICAz-sensorknoop De MICAz-sensorknoop (Figuur 7.2) is een hardwareplatform uit de generische klasse. Het platform wordt geproduceerd door Crossbow Technology Inc.
Het hardwareontwerp bouwt
voort op het ontwerp van de MICA-sensorknoop die ontwikkeld werd aan UC Berkeley. De MICAz-sensorknoop heeft een Atmel ATmega128 microcontroller (avr architectuur), 128 KiB programmageheugen en 4 KiB RAM geheugen. De radio is compatibel met IEEE 802.15.4/Zig-
HOOFDSTUK 7.
58
PROTOTYPE IMPLEMENTATIE
Bee en haalt een snelheid van 250 kbps. De verwerkingseenheid heeft een uitbreidingsconnector waarop verschillende sensorborden kunnen aangesloten worden (in Figuur 7.2 is een MICA-sensorbord op de connector aangesloten). Deze uitbreidingsconnector wordt eveneens gebruikt om de MICAz-sensorknoop op een interfacebord aan te sluiten. Het interfacebord laat toe de MICAz-sensorknoop te programmeren en ermee te interageren via een seriële interface. Door deze mogelijkheid om met de MICAz-sensorknoop te interageren tijdens de werking van het systeem, kan men hem ook gebruiken als gateway.
Simulatie Avrora [39] is een simulator voor de avr architectuur die simuleert op het niveau van individuele instructies (tot op een klokcyclus nauwkeurig). Avrora kan ook gebruikt worden om sensornetwerken met MICA2-sensorknopen te simuleren.
Het MICA2-hardwareplatform is
gelijkaardig aan het MICAz-platform, enkel de radio hardware verschilt. Avrora heeft ondersteuning voor gdb (de GNU debugger). Deze ondersteuning bleek echter niet altijd even goed te werken. Desondanks is avrora een handig hulpmiddel voor het testen van SOS-applicaties. SOS voorziet zelf ook de mogelijkheid om een applicatie te simuleren door ze te compileren voor een gesimuleerde sensorknoop op een pc platform.
De applicatie kan zo rechtstreeks
worden uitgevoerd op de computer van de ontwikkelaar. SOS ondersteunt in deze omgeving echter, net als avrora, het MICAz-platform niet. MICA2 wordt wel ondersteund. De SOS-simulatieomgeving laat toe om redelijk makkelijk een toepassing te testen en fouten op te sporen met gdb. De simulatie is echter geen precieze nabootsing van het hardwareplatform. Dit komt onder meer doordat de lengte van een pointer verschilt. Als gevolg daarvan is bijvoorbeeld de heap size in de simulatie omgeving groter gemaakt dan op het gesimuleerde platform het geval is. Tijdens de implementatie in deze thesis werd er vooral gebruik gemaakt van de SOSsimulatieomgeving om de applicatie te testen. Alvorens de applicatie daarna op de hardwareknopen te testen, werd er een simulatie in avrora gedaan. De gesimuleerde sensorknopen in avrora wijken minder af van de echte hardware, waardoor in deze omgeving soms nog fouten aan het licht kwamen die niet optraden bij de SOS-simulatieomgeving. De verschillen tussen de simulatieomgevingen en de werkelijke hardware die gebruikt werd, zorgen ervoor dat een applicatie die werkt in deze omgevingen niet gegarandeerd werkt op de sensorknopen. Dit maakt het opsporen van fouten in de implementatie een stuk moeilijker. Niet alle problemen zijn namelijk reproduceerbaar in de simulatieomgevingen.
Sectie 7.3.1
bespreekt een voorbeeld van een probleem dat slechts gedeeltelijk reproduceerbaar is in de SOS-simulatieomgeving.
7.3
Problemen
Tijdens de implementatie zijn enkele problemen opgedoken. Sectie 7.3.1 bespreekt een probleem met het dynamische geheugen van SOS. Sectie 7.3.2 gaat in op een probleem bij het laden van modules.
HOOFDSTUK 7.
7.3.1
59
PROTOTYPE IMPLEMENTATIE
Geheugenfragmentatie
Het probleem
Op een gegeven moment tijdens het testen van de implementatie, faalde
een geheugenaanvraag voor 38 bytes. Het systeem had op dat moment nog maar 451 bytes aangevraagd. SOS voorziet, op het MICAz-platform, echter 1536 bytes (1.5 kilobyte) voor de heap. Het systeem gebruikte dus lang niet alle geheugen. De SOS-simulatieomgeving biedt een makkelijke manier om het geheugengebruik te onderzoeken. De heap is in de SOS-simulatieomgeving echter dubbel zo groot. Daardoor kwam het probleem niet voor in de SOS-simulatieomgeving. De oorzaak kon dan ook slechts gedeeltelijk worden geanalyseerd in de SOS-simulatieomgeving. Nader onderzoek met behulp van avrora bracht de reden voor de gefaalde aanvraag aan het licht. Tabel 7.1 toont de toestand van het geheugen op het moment van de gefaalde aanvraag. Er zijn 145 blokken van 8 bytes toegewezen.
66 blokken zijn toegewezen aan modules van
SOS, 79 blokken zijn aan het systeem toegewezen. Er zijn nog 46 blokken vrij, ze zijn echter verspreid over de ganse heap. De heap is met andere woorden heel sterk gefragmenteerd. Dit zorgt ervoor dat er nergens nog 38 opeenvolgende bytes gevonden worden. Dit verklaart de gefaalde aanvraag. De fragmentatie van het geheugen komt tot stand door het dynamisch laden van modules. Zoals in Tabel 7.1 duidelijk te zien is, zijn heel veel van de vrije blokken te vinden net voor een blok dat toegekend is aan de SOS-scheduler. Bij het laden van een module alloceert SOS minstens drie zaken op de heap: een initialisatiebericht dat vlak na het laden naar de module wordt gestuurd, een gegevensstructuur voor de SOS-scheduler en de ruimte om de toestand van de module in te bewaren. Indien nodig alloceert SOS ook ruimte voor de gegarandeerde timers die de module aanvraagt bij het laden. De laatste drie types blokken worden gedurende lange tijd niet vrijgegeven. Het blok voor het initialisatiebericht komt terug vrij nadat het bericht is afgehandeld. Daardoor ontstaat telkens een gat ter grootte van een bericht.
Het probleem omzeilen
Er zijn twee manieren om het probleem te omzeilen. Enerzijds
2 door I C uit te schakelen en anderzijds door enkele modules statisch te registreren. In Tabel 7.1 2 2 is te zien dat de I C driver van SOS redelijk wat geheugen gebruikt. I C is een seriële bus die gebruikt kan worden om met externe hardware te communiceren.
Het systeem maakt
2
voorlopig echter geen gebruik dergelijke hardware en kan dus ook werken zonder I C. Men kan
2 bij het compileren I C uitschakelen, waardoor SOS deze driver niet meer laadt en het blok geheugen dus ook niet meer nodig is. Een andere manier om het probleem te omzeilen is enkele modules statisch registreren. Men moet dan zelf globaal geheugen voorzien voor de toestand van de module en voor de gegevensstructuur voor de SOS-scheduler. Deze twee blokken komen dan niet op de heap. Dit spaart enerzijds wat plaats op de heap uit, anderzijds vermindert het de fragmentatie. Er is namelijk geen langdurig gealloceerd geheugen meer, vlak na het initialisatiebericht dat slechts voor korte duur is gealloceerd. Men kan deze tweede techniek echter niet onbeperkt toepassen.
Het grootste deel van
het globale geheugen is namelijk al in gebruik door de SOS-kernel. Een meer fundamentele oplossing van het probleem dringt zich dan ook op.
De oplossing
Na een melding van het probleem aan de ontwikkelaars van SOS, hebben
zij een oplossing uitgewerkt en geïmplementeerd in SOS. De oplossing bestaat erin langdurig gealloceerde blokken te scheiden van andere blokken. De blokken voor de gegevensstructuur
HOOFDSTUK 7.
60
PROTOTYPE IMPLEMENTATIE
Adres
Groot- PID Module te
Adres
Groot- PID Module te
0x0172
3
11
0x0442
2
128
Basiclib
queue
0x0452
3
-
vrij
0x018a
3
-
vrij
0x046a
2
2
SOS scheduler
0x01a2
2
2
SOS scheduler
0x047a
1
193
Stack
0x01b2
3
4
SOS timers
0x0482
3
-
vrij
0x01ca
3
-
vrij
0x049a
2
2
SOS scheduler
0x01e2
17
65
I C driver
2
0x04aa
2
196
Context
SOS
message
0x026a
3
0x0282
3
11
SOS
vrij
0x029a
3
-
0x02b2
3
4
SOS timers
0x02ca
5
196
Context
0x02f2
1
-
vrij
0x02fa
2
2
SOS scheduler
0x030a
3
201
Scheduler
0x0322
3
-
0x033a
2
0x034a
0x04ba
3
-
vrij
0x04d2
2
2
SOS scheduler
queue
0x04e2
4
198
Concurrency
vrij
0x0502
1
197
VM
0x050a
2
-
vrij
0x051a
2
2
SOS scheduler
0x052a
7
197
VM
0x0562
3
11
SOS
vrij
0x057a
2
2
SOS scheduler
2
SOS scheduler
0x058a
11
192
Virus
1
202
Event Manager
0x05e2
3
4
SOS timers
0x0352
3
4
SOS timers
0x05fa
3
4
SOS timers
0x036a
3
-
vrij
0x0612
3
-
vrij
0x0382
2
2
SOS scheduler
0x062a
6
194
Capsule
0x0392
2
200
Library
0x065a
4
193
Stack
0x067a
2
195
Capsule Mana-
message
Mana-
ger
message
queue
0x03a2
3
-
vrij
0x03ba
2
2
SOS scheduler
0x068a
5
196
Context
0x03ca
4
195
Capsule Mana-
0x06b2
6
194
Capsule
ger
0x06e2
4
193
Stack
0x0702
2
195
Capsule Mana-
ger
0x03ea
3
-
vrij
0x0402
2
2
SOS scheduler
0x0412
1
194
Capsule
0x0712
3
-
vrij
0x041a
1
2
SOS scheduler
0x072a
6
192
Virus
0x0422
2
-
vrij
0x075a
2
-
vrij
0x0432
2
2
SOS scheduler
0x076a
-
-
SENTINEL
ger
Tabel 7.1: Geheugen op het moment van de problemen. Grootte in blokken (8 bytes/blok).
HOOFDSTUK 7.
61
PROTOTYPE IMPLEMENTATIE
van de SOS-scheduler, de toestand van de module en voor de gegarandeerde timers, worden nu achteraan de heap geplaatst. Voor de rest van de aanvragen blijft de SOS-kernel geheugen toekennen vanaf het begin van de heap. Deze oplossing zorgt ervoor dat de stukken geheugen die snel terug vrij komen, meer gegroepeerd zijn vooraan de heap. Daardoor kunnen deze blokken, nadat ze zijn vrijgegeven, terug samengesmolten worden tot één grote blok.
7.3.2
Laden van modules
De operatiebibliotheken worden geïmplementeerd als modules voor SOS. Om de instructieset van een virtuele machine dynamisch uit te breiden, moeten deze modules dynamisch kunnen toegevoegd worden aan het systeem.
Zoals in Sectie 7.1.2 werd besproken, wordt hiervoor
gebruik gemaakt van het mechanisme dat SOS hiervoor aanbiedt. Tijdens het testen van de implementatie bleek dat de modules die in het sensornetwerk geïnjecteerd werden, niet geladen werden op de knopen waarop het systeem geïnstalleerd was. Na een vraag hierover aan de ontwikkelaars van SOS werd duidelijk dat het probleem eenvoudig op te lossen was. De SOS-kernel bevat een constante die aangeeft waar het stuk codegeheugen begint waar dynamische modules geladen mogen worden.
De kern van het
systeem werd echter gecompileerd als een statische applicatie voor SOS. Daardoor was het stuk van het codegeheugen dat statisch werd toegewezen te groot zodat de constante midden in het statisch toegewezen stuk codegeheugen wees. Nadat deze constante werd verhoogd zodat ze buiten het statisch toegewezen codegeheugen wees, werkte het laden van modules echter nog steeds niet. Na verder onderzoek bleek dat de lader van SOS tijdens het laden van een module tijdelijk vrij veel geheugen nodig heeft. Daardoor liep het dynamisch geheugen vol en werd het laden van de module afgebroken. Dit probleem kan enkel opgelost worden door meer dynamisch geheugen te voorzien.
7.4
Gebruik
De implementatie voorziet enkele rudimentaire tools om het systeem te gebruiken. Deze tools bieden enkel de basisfunctionaliteit. Niet alle functionaliteit die ideaal in de toolchain aanwezig zou moeten zijn, is ook eectief aanwezig. De gebruiksvriendelijkheid van de aanwezige tools is minimaal. De tools voorzien enkel een commandoregel interface. Het gebruik hiervan is niet triviaal, daarom geeft deze sectie aan hoe deze tools gebruikt kunnen worden. De tools maken gebruik van SOS-server om met het sensornetwerk te communiceren. SOSserver is een tool die meegeleverd wordt met SOS en dient voor multiplexing van verschillende verbindingen over de seriële verbinding waarmee de computer met een sensornetwerk verbonden is.
SOS-server kan ook een verbinding maken met een gesimuleerd sensornetwerk.
De
SOS-simulatieomgeving en avrora gebruiken een TCP/IP-verbinding om de seriële verbinding te simuleren. Om SOS-server te gebruiken om gegevens naar het sensornetwerk te versturen, zetten tools een TCP/IP-verbinding op met SOS-server. De uitleg in deze sectie gebeurt aan de hand van een eenvoudige applicatie. Deze applicatie leest periodiek een meting uit van de lichtsensor en verstuurt deze meting vervolgens via het netwerk. De uiteenzetting gaat er van uit dat de ontwikkelingsversie van SOS geïnstalleerd is op de computer van de gebruiker.
HOOFDSTUK 7.
7.4.1
62
PROTOTYPE IMPLEMENTATIE
Een operatiebibliotheek laden
De eenvoudige applicatie maakt gebruik van een operatiebibliotheek die de instructie implementeert waarmee de meting wordt verstuurd via het netwerk. Als deze bibliotheek nog niet aanwezig is op de sensorknopen, moet ze eerst geladen worden voor ze gebruikt kan worden. De module waarin de bibliotheek geïmplementeerd is, moet eerst worden gecompileerd voor het doelplatform, waarna ze met de tools die SOS daarvoor voorziet geladen kan worden. Eerst wordt SOS-server gestart, daarna wordt de module geladen met het commando in Codevoorbeeld 7.1.
sos_insmod . sh netlib . sos Codevoorbeeld 7.1: Een operatiebibliotheek (netlib.sos) laden met behulp van de SOS-tools
7.4.2
Een virtuele machine aanpassen, toevoegen of verwijderen
Standaard bevat een knoop slechts 1 virtuele machine, die enkel een context bevat die uitgevoerd wordt wanneer de virtuele machine herstart. De instructieset van de virtuele machine omvat enkel een basisbibliotheek. De voorbeeldapplicatie heeft twee contexten nodig: één om de lichtsensor uit te lezen en de meting te verzenden en één om de timer te starten die ervoor zorgt dat deze taak periodiek wordt uitgevoerd. De voorbeeldapplicatie maakt bovendien gebruik van de bibliotheek die in Sectie 7.4.1 werd geladen. Daarom maken we een beschrijving voor een virtuele machine zoals in Codevoorbeeld 7.2. De beschrijving stelt dat de lokale bibliotheken 0 en 1 respectievelijk overeenkomen met bibliotheek 0 en bibliotheek 3 (We gaan ervan uit dat de bibliotheek voor het versturen van een bericht identi catie 3 heeft). De beschrijving zegt verder dat context 0 en context 1 aanwezig zijn in de virtuele machine.
Context 0 is de context die wordt
uitgevoerd na het herstarten van de virtuele machine. In deze context wordt een timer gestart die periodiek de uitvoering van context 1 veroorzaakt. Deze beschrijving moet omgezet worden in een binaire voorstelling voor ze in het netwerk kan worden geïnjecteerd. De zoals in Codevoorbeeld 7.3. met de
davim-injector
davim-vmgen
tool doet deze omzetting en wordt aangeroepen
Daarna wordt de binaire beschrijving in het netwerk gebracht
tool. Hij wordt opgeroepen zoals in Codevoorbeeld 7.4. Het laatste
argument is de identi catie van de virtuele machine. In dit geval gebruiken we een ongebruikt identi catienummer om ervoor te zorgen dat een nieuwe virtuele machine wordt toegevoegd. Een virtuele machine aanpassen verloopt volledig analoog, wanneer we bijvoorbeeld de standaard virtuele machine (met idenditi catienummer 0) willen aanpassen, moeten we enkel het laatste argument in Codevoorbeeld 7.4 vervangen door 0. Codevoorbeeld 7.5 toont hoe de
davim-injector
tool ook kan gebruikt worden om een virtuele machine te verwijderen.
LIB 0 0 LIB 1 3 CONTEXT 0 CONTEXT 1
Codevoorbeeld
7.2:
(voorbeeldvm.txt)
Tekstuele
voorstelling
van
een
eenvoudige
virtuele
machine
HOOFDSTUK 7.
63
PROTOTYPE IMPLEMENTATIE
davim - vmgen voorbeeldvm . txt voorbeeldvm . bin
Codevoorbeeld 7.3: Een binaire beschrijving van een virtuele machine genereren
davim - injector -- vm voorbeeldvm . bin 2
Codevoorbeeld 7.4: Een virtuele machine injecteren
davim - injector -- vmdel 2
Codevoorbeeld 7.5: Een virtuele machine verwijderen
7.4.3
Een virtuele machine gebruiken
Figuur 4.1 op pagina 27 toont de toolchain die Maté ter beschikking stelt om de virtuele machine te gebruiken. Deze tool omvat een compiler, een assembler en een injector. De implementatie in deze thesis voorziet enkel een assembler en een injector. De assembler ondersteunt slechts een beperkte instructieset. Wanneer een uitgebreidere instructieset nodig is, moet de assembler worden uitgebreid of moet een eigen assembler worden voorzien. Voor de eenvoudige applicatie hebben we twee scripts nodig.
Codevoorbeeld 7.6 toont
het script om periodiek een meting te doen met de lichtsensor en vervolgens het resultaat te verzenden via de radio. In Codevoorbeeld 7.7 is het script te zien om de timer te starten. Het eerste script heeft als eerste instructie een speciale aanduiding die aangeeft dat er een extra bibliotheek nodig is. Het tweede script gebruikt enkel de basisbibliotheek en bevat daarom geen dergelijke aanduiding. De assembler (
davim-as )
zet dergelijke scripts om in bytecode. Codevoorbeeld 7.8 toont
davim-injector ) verpakt
hoe hij wordt gebruikt om het eerste script om te zetten. De injector (
de uitvoer van de assembler vervolgens als een SOS-bericht en verstuurt het via SOS-server naar het sensornetwerk.
Het gebruik van
zien in Codevoorbeeld 7.9.
davim-injector
om een capsule te injecteren is te
De laatste twee parameters zijn de identi catie van de virtuele
machine en de context waarin de bytecode moet uitgevoerd worden.
INC NET GET_PHOTO_DATA POST_NET HALT
Codevoorbeeld 7.6:
Een script om een meting te doen en het resultaat te verzenden
(meetenzend.txt)
PUSH 100 SETTIMER0 REPEAT HALT
Codevoorbeeld 7.7: Een script om de timer te starten (zettimer.txt)
davim - as meetenzend . txt meetenzend . bc
Codevoorbeeld 7.8: Gebruik van de assembler
HOOFDSTUK 7.
PROTOTYPE IMPLEMENTATIE
64
davim - injector -- capsule meetenzend . bc 2 1
Codevoorbeeld 7.9: Gebruik van de injector om een capsule (meetenzend.bc) te injecteren in context 1 van VM 2
7.5
Besluit
De prototype implementatie die in dit hoofdstuk werd aangebracht, toont aan dat de architectuur uit Hoofdstuk 6 haalbaar is: de prototype implementatie ondersteunt aanpasbare virtuele machines en laat toe dat meerdere virtuele machines tegelijk op de knopen geladen zijn. Dit zijn de twee uitbreidingen, ten opzichte van de architectuur van Maté, die werden beoogd met de architectuur uit Hoofdstuk 6. Er is echter één beperkende factor: het dynamisch geheugen. Een dynamisch systeem heeft inherent nood aan een redelijke hoeveelheid dynamisch geheugen. De MICAz-sensorknopen hebben slechts 4 KiB RAM-geheugen en daarom voorziet SOS maar 1.5 KiB voor het dynamisch geheugen. Dit is te weinig om de prototype implementatie fatsoenlijk te laten werken. De bovengrens voor het aantal lokale en globale variabelen en de diepte van de operandstapels moet heel klein worden gezet om het systeem te laten werken. Een instructieset uitbreiden door een nieuwe operatiebibliotheek te laden is onmogelijk door een gebrek aan dynamisch geheugen (Sectie 7.3.2). Het geheugen moet echter niet met enkele grootteordes toenemen om het systeem te laten werken. Een snelle test wees uit dat het mogelijk is om een operatiebibliotheek te laden in het systeem als de Virus module wordt weggelaten. De toestand van de Virus module neemt, samen met het blok voor de SOS-scheduler, 112 bytes in beslag. Bovendien werkt het systeem wel behoorlijk in de SOS-simulatieomgeving. Rekening houdend met het feit dat een pointer op het pc platform waarop getest werd dubbel zoveel ruimte inneemt, is het dynamisch geheugen in de SOS-simulatieomgeving minder dan tweemaal zo groot dan op de MICAz-sensorknoop. Er zijn reeds sensorknopen beschikbaar die meer RAM-geheugen aan boord hebben dan de MICAz-sensorknopen. De opvolger voor de MICAz-knoop die Crossbow Technology Inc. heeft ontwikkeld, is de TelosB-sensorknoop. Deze sensorknoop heeft 10 KiB RAM-geheugen en SOS reserveert er daarvan 5 KiB voor het dynamisch geheugen.
De XYZ-sensorknoop,
ontwikkeld door het ENALAB van Yale University en Cogent Computer, biedt zelfs 32 KiB RAM. Het is zeer waarschijnlijk dat het prototype op deze recentere hardwareplatformen wel behoorlijk zou werken.
Hoofdstuk 8
Besluit Dit laatste hoofdstuk geeft een overzicht van de resultaten en conclusies die in deze thesis werden bekomen. Daarna worden relevante uitdagingen beschreven waarover nog verder onderzoek kan gedaan worden.
8.1
Resultaten
Deze thesis presenteert een architectuur voor dynamische virtuele machines voor sensornetwerken. Deze architectuur laat toe om een verregaand dynamisme te ondersteunen op de beperkte hardware van de hedendaagse sensorknopen. Deze ondersteuning wordt gerealiseerd door een combinatie van de ideeën van de traditionele statische virtuele machines en de dynamische besturingssystemen met een modulaire aanpak. Om tot de architectuur van dit middlewaresysteem te komen beschrijft de thesis eerst de context waarin middlewaresystemen voor sensornetwerken opereren.
Vervolgens wordt een
overzicht gegeven van de relevante onderzoeksuitdagingen voor deze middleware. De aanpak in deze thesis wordt geplaatst in een algemeen kader dat gecreëerd wordt door een overzicht van de aanpakken die in de literatuur zijn beschreven. De thesis beschrijft verder de architectuur en de werking van Maté en Sensor Operating System (SOS). Maté is een middleware die toelaat traditionele virtuele machines voor sensornetwerken te bouwen. SOS is een sensorbesturingssysteem dat ondersteuning biedt voor modules en dynamisch geheugen. Vervolgens beschrijft de thesis de functionele en niet-functionele vereisten waaraan de dynamisch aanpasbare virtuele machines moeten voldoen.
De architectuur realiseert deze
vereisten door de architectuur van Maté, die zijn degelijkheid reeds bewezen heeft, uit te breiden zodat het mogelijk wordt verregaand dynamisme te ondersteunen. Tenslotte valideert de thesis de ontwikkelde architectuur aan de hand van een prototype implementatie. De prototype implementatie werd ontwikkeld met behulp van SOS en getest op MICAz-sensorknopen.
8.2
Evaluatie
De architectuur die in deze thesis werd ontwikkeld, voldoet aan de vooropgestelde doelstellingen. De architectuur laat toe een virtuele machine dynamisch aan te passen en maakt de ondersteuning van meerdere virtuele machines op één sensorknoop mogelijk.
65
HOOFDSTUK 8.
66
BESLUIT
De prototype implementatie bevestigt dat het mogelijk is om een dergelijk verregaand dynamisme te ondersteunen.
Ze bracht echter ook aan het licht dat het geheugen op de
sensorknopen de beperkende factor is voor dit dynamisme.
Het MICAz-hardwareplatform,
waarop de testen werden uitgevoerd, biedt net iets te weinig geheugen om het prototype comfortabel te laten werken.
De recenste hardwareplatformen, zoals TelosB en Yale XYZ,
bieden echter reeds meer geheugen.
8.3
Verder werk
De prototype implementatie die in deze thesis werd ontwikkeld, werkt slechts moeizaam op het beperkte geheugen van het MICAz-hardwareplatform. Er zijn echter gefundeerde aanwijzingen dat het geheugen dat door recentere hardwareplatformen (zoals TelosB en Yale XYZ) wordt geboden, voldoende zou zijn om het prototype comfortabel te laten werken. Verder werk zou deze hypothese kunnen veri ëren. De toolchain die werd ontwikkeld bij de prototype implementatie is beperkt tot het strikt noodzakelijke om het prototype te kunnen testen. Verder werk zou deze toolchain kunnen uitbreiden en de gebruiksvriendelijkheid ervan verhogen. De assembler zou bijvoorbeeld in staat moeten zijn om de samenstelling van de instructieset van een virtuele machine uit een con guratiebestand af te leiden. De gebruiksvriendelijkheid zou gevoelig verhoogd kunnen worden door de ontwikkeling van gra sche gebruikersinterfaces voor de belangrijkste functionaliteit. De implementatie van het prototype werd bemoeilijkt door het gebrek aan goede foutopsporingsmogelijkheden (debugging support).
De mogelijkheden om fouten op de sporen
op de hardware zelf waren heel beperkt omdat er geen middelen beschikbaar waren om de JTAG-interface aan te spreken die toelaat breekpunten en andere foutopsporingstechnieken te gebruiken. De simulatieomgevingen die gebruikt werden bieden wel ondersteuning voor foutopsporing maar hun gedrag is niet altijd identiek aan het gedrag van de hardware. Bovendien ondersteunt geen van de gebruikte simulatieomgevingen het MICAz-platform en moest de foutopsporing daarom gebeuren op een gesimuleerd MICA2-platform dat licht afwijkt van het MICAz-platform. Verder werk kan ondersteuning voor het MICAz-platform in deze simulatieomgevingen inbouwen of onderzoeken hoe de foutopsporingsmogelijkheden op de hardware volledig kunnen worden benut. Verder werk kan ook onderzoeken hoe de architectuur die deze thesis ontwikkelde, aangewend kan worden voor de realisatie van geïntegreerde dienstenplatformen. De architectuur biedt een oplossing voor dynamische aanpasbaarheid, één van de uitdagingen die ontstaan bij deze integratie. Er zijn echter nog andere uitdagingen die moeten worden aangepakt om de geïntegreerde dienstenplatformen te kunnen verwezenlijken. Denken we bijvoorbeeld aan de beveiliging van de sensornetwerkinfrastructuur of de interactie tussen sensornetwerken en de traditionele infrastructuur.
Bibliogra e [1] Tarek F. Abdelzaher, Brian M. Blum, Qing Cao, Y. Chen, D. Evans, J. George, S. George, Lin Gu, Tian He, Sudha Krishnamurthy, Liqian Luo, Sang Hyuk Son, Jack Stankovic, Radu Stoleru, and Anthony D. Wood. Envirotrack: Towards an environmental computing paradigm for distributed sensor networks. In
ICDCS, pages 582589, 2004.
[2] Hector Abrach, Shah Bhatti, James Carlson, Hui Dai, Je Rose, Anmol Sheth, Brian Shucker, Jing Deng, and Richard Han. Mantis - system supports for multimodal networks on in-situ sensors. In
SenSys, pages 336337, 2003.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey.
Comput. Networks, 38(4):393422, 2002.
[4] Amol Bakshi, Viktor K. Prasanna, Jim Reich, and Daniel Larner. graph:
The abstract task
a methodology for architecture-independent programming of networked sensor
EESR '05: Proceedings of the 2005 workshop on End-to-end, sense-andrespond systems, applications and services, pages 1924, Berkeley, CA, USA, 2005. USEsystems.
In
NIX Association. [5] Rimon Barr, John C. Bicket, Daniel S. Dantas, Bowei Du, T. W. Danny Kim, Bing Zhou, and Emin Gün Sirer. On the need for system-level support for ad hoc and sensor networks.
SIGOPS Oper. Syst. Rev., 36(2):15, 2002.
[6] Gordon S. Blair, Andrew T. Campbell, and Douglas C. Schmidt. Guest editorial: Middleware technologies for future communication networks.
IEEE Network, 18(1):45, 2004.
[7] Jan Blumenthal, Matthias Handy, Frank Golatowski, Marc Haase, and Dirk Timmermann. Wireless sensor networks - new challenges in software engineering. [8] Krishna Chintalapudi, Tat Fu, Jeongyeup Paek, Nupur Kothari, Sumit Rangwala, John Carey, Ramesh Govindan, Erik Johnson, and Sami Masri. Monitoring civil structures with a wireless sensor network.
IEEE Internet Computing, 10(2):2634, 2006.
[9] David E. Culler and Wei Hong. Introduction.
Commun. ACM, 47(6):3033, 2004.
[10] Adam Dunkels, Bjorn Gronvall, and Thiemo Voigt. Contiki - a lightweight and exible
operating system for tiny networked sensors. In LCN '04: Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), pages 455462, Washington, DC, USA, 2004. IEEE Computer Society.
67
68
BIBLIOGRAFIE
[11] Adam Dunkels, Oliver Schmidt, and Thiemo Voigt. Using Protothreads for Sensor Node In Proceedings of the REALWSN'05 Workshop on Real-World Wireless Sensor Networks, Stockholm, Sweden, June 2005. Programming.
[12] David Gay, Philip Levis, Robert von Behren, Matt Welsh, Eric Brewer, and David Culler.
PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, pages 111, New York, NY, USA, 2003. ACM Press.
The nesc language: A holistic approach to networked embedded systems. In
[13] John C. Georgas and Richard N. Taylor. Towards a knowledge-based approach to archi-
WOSS '04: Proceedings of the 1st ACM SIGSOFT workshop on Self-managed systems, pages 5963, New York, NY, USA, 2004. ACM Press.
tectural adaptation management. In
[14] Ramakrishna
Gummadi,
Omprakash
Gnawali,
and
programming wireless sensor networks using kairos. In
Ramesh
Govindan.
Macro-
DCOSS, pages 126140, 2005.
[15] Salem Hadim and Nader Mohamed. Middleware challenges and approaches for wireless sensor networks.
IEEE Distributed Systems Online, 7(3), 2006.
[16] Chih-Chich Han, Ram Kumar, Roy Sea, and Mani Srivastava. Sensor network software update management: A survey.
International Journal of Network Management,
15(4),
July/August 2005. [17] Chih-Chieh Han, Ram Kumar, Roy Shea, Eddie Kohler, and Mani Srivastava. A dynamic operating system for sensor nodes. In MobiSys '05: Proceedings of the 3rd international conference on Mobile systems, applications, and services, pages 163176, New York, NY,
USA, 2005. ACM Press. [18] Q. Han and N. Venkatasubramanian. Autosec: An integrated middleware framework for dynamic service brokering. 2(7), 2001. [19] Wendi Beth Heinzelman, Amy L. Murphy, Hervaldo S. Carvalho, and Mark A. Perillo. Middleware to support sensor network applications.
IEEE Network, 18(1):614, 2004.
[20] Jason Hill, Mike Horton, Ralph Kling, and Lakshman Krishnamurthy. enabling wireless sensor networks.
Commun. ACM, 47(6):4146, 2004.
The platforms
[21] Jonathan W. Hui and David Culler. The dynamic behavior of a data dissemination proto-
SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems, pages 8194, New York, NY, USA, col for network programming at scale. In
2004. ACM Press. [22] J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: mobile networking
MobiCom '99: Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, pages 271278, New York, NY, for smart dust. In
USA, 1999. ACM Press. [23] Gregor Kiczales, John Lamping, Christina Videira Lopes, Chris Maeda, Anurag Mendhekar, and Gail Murphy.
Open implementation design guidelines.
In
ceedings of the 19th international conference on Software engineering, New York, NY, USA, 1997. ACM Press.
ICSE '97: Pro-
pages 481490,
69
BIBLIOGRAFIE
Proceedings of the 2nd USENIX/ACM Symposium on Network Systems Design and Implementation (NSDI),
[24] P. Levis, D. Gay, and D. Culler.
Active sensor networks.
In
May 2005. [25] Philip Levis and David Culler.
Maté: a tiny virtual machine for sensor networks.
In
ASPLOS-X: Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, pages 8595, New York, NY, USA, 2002.
ACM Press. [26] Philip Levis, Samuel Madden, David Gay, Joseph Polastre, Robert Szewczyk, Alec Woo, Eric A. Brewer, and David E. Culler. techniques in tinyos. In
The emergence of networking abstractions and
Proc. 1st Symposium on Networked Systems Design and Imple-
mentation (NSDI '04), pages 114, March 2004.
[27] Philip Levis, Neil Patel, David E. Culler, and Scott Shenker. Trickle: A self-regulating algorithm for code propagation and maintenance in wireless sensor networks. In
NSDI,
pages 1528, 2004. [28] Shuoqi Li, Sang Hyuk Son, and John A. Stankovic. Event detection services using data service middleware in distributed sensor networks. In
IPSN, pages 502517, 2003.
[29] Hongzhou Liu, Tom Roeder, Kevin Walsh, Rimon Barr, and Emin Gün Sirer. Design and
MobiSys '05: Proceedings of the 3rd international conference on Mobile systems, applications, and services, pages 149162, New York, NY, USA, 2005. ACM Press.
implementation of a single system image operating system for ad hoc networks. In
[30] Ting Liu and Margaret Martonosi. Impala: a middleware system for managing autonomic, parallel sensor systems. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 107118, New York, NY, USA, 2003. ACM Press. [31] Samuel R. Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. Tinydb: an acquisitional query processing system for sensor networks.
Syst., 30(1):122173, 2005.
ACM Trans. Database
[32] Ryan Newton and Matt Welsh. Region streams: functional macroprogramming for senIn DMSN '04: Proceeedings of the 1st international workshop on Data management for sensor networks, pages 7887, New York, NY, USA, 2004. ACM Press. sor networks.
[33] Peyman Oreizy, Michael M. Gorlick, Richard N. Taylor, Dennis Heimbigner, Gregory Johnson, Nenad Medvidovic, Alex Quilici, David S. Rosenblum, and Alexander L. Wolf. An architecture-based approach to self-adaptive software.
IEEE Intelligent Systems,
14(3):5462, 1999. [34] Kay Römer, Christian Frank, Pedro José Marrón, and Christian Becker. Generic role assignment for wireless sensor networks. In
Workshop, pages 712, September 2004.
Proceedings of the 11th ACM SIGOPS European
[35] Kay Römer, Oliver Kasten, and Friedemann Mattern. Middleware challenges for wireless sensor networks.
SIGMOBILE Mob. Comput. Commun. Rev., 6(4):5961, 2002.
70
BIBLIOGRAFIE
[36] Eduardo Souto, Germano Guimarães, Glauco Vasconcelos, Mardoqueu Vieira, Nelson Rosa, Carlos Ferraz, and Judith Kelner. sensor networks.
Mires:
a publish/subscribe middleware for
Personal Ubiquitous Comput., 10(1):3744, 2005.
[37] Chavalit Srisathapornphat, Chaiporn Jaikaeo, and Chien-Chung Shen. Sensor information networking architecture. In 2000 International Workshop on Parallel Processing (ICPP 2000), Toronto, Canada, August 2000.
[38] T. Stathopoulos, J. Heidemann, and D. Estrin.
A remote code update mechanism for
wireless sensor networks, 2003. [39] Ben Titzer, Daniel K. Lee, and Jens Palsberg. Avrora: scalable sensor network simulation with precise timing. In
IPSN, pages 477482, 2005.
[40] Matt Welsh. Exposing resource tradeos in region-based communication abstractions for sensor networks.
SIGCOMM Comput. Commun. Rev., 34(1):119124, 2004.
[41] Georey Werner-Allen, Konrad Lorincz, Matt Welsh, Omar Marcillo, Je Johnson, Mario Ruiz, and Jonathan Lees. Deploying a wireless sensor network on an active volcano.
Internet Computing, 10(2):1825, 2006.
IEEE
[42] Kamin Whitehouse, Cory Sharp, David E. Culler, and Eric A. Brewer. Hood: A neighborhood abstraction for sensor networks. In
MobiSys, 2004.
[43] Kamin Whitehouse, Feng Zhao, and Jie Liu. Semantic streams: A framework for composable semantic interpretation of sensor data. In
EWSN, pages 520, 2006.
[44] Yong Yao and Johannes Gehrke. The cougar approach to in-network query processing in sensor networks.
SIGMOD Rec., 31(3):918, 2002.
B¼lage A
Formele use cases A.1
Laad operatiebibliotheek
Belang: Secundair Primaire belanghebbende: Precondities: •
Gebruiker van het systeem
Het systeem is reeds geladen op de sensorknopen
Postcondities: •
De operatiebibliotheek is geladen en klaar voor gebruik
Hoofdscenario: 1 Het systeem verspreidt de operatiebibliotheek naar de knopen in het sensornetwerk 2 [Op elke knoop] Het systeem ontvangt de operatiebibliotheek 2.1 Het systeem laadt en initialiseert de operatiebibliotheek
Uitbreidingen: 2.1.a De operatiebibliotheek is al aanwezig 2.1.a.1 use case eindigt
A.2
Wijzig VM
Belang: Secundair Primaire belanghebbende: Precondities:
Gebruiker van het systeem
•
Het systeem is reeds geladen op de sensorknopen
•
Er is reeds een VM aanwezig op de sensorknopen
Postcondities: 71
BLAGE A.
•
FORMELE USE CASES
72
De wijzigingen aan de gevraagde VM zijn doorgevoerd
Hoofdscenario: 1 Het systeem verspreidt de wijziging naar de knopen in het sensornetwerk 2 [Op elke knoop] Het systeem ontvangt de wijziging 2.1 Het systeem voert de wijziging door aan de gevraagde VM
Uitbreidingen: 2.1.a De wijziging is ongeldig 2.1.a.1 use case faalt 2.1.b De wijziging is een nieuwe context 2.1.b.1 Het systeem maakt en initialiseert een nieuwe context 2.1.b.2 Het systeem voegt de context toe aan de gevraagde VM 2.1.c De wijziging is een nieuwe instructiebibliotheek 2.1.c.1 Het systeem past de verwijzing in de verwijzingstabel voor bibliotheken van de gevraagde VM aan
A.3
Nieuwe instructie(s)
Belang: Primair Gebruikt: •
laad operatiebibliotheek: zie A.1, pagina 71
•
wijzig VM: zie A.2, pagina 71
Primaire belanghebbende: Precondities:
Gebruiker van het systeem
•
Het systeem is reeds geladen op de sensorknopen
•
Er is reeds een VM aanwezig op de sensorknopen
Postcondities: •
De gevraagde virtuele machine is uitgebreid met de nieuwe instructie(s)
Hoofdscenario: 1 De gebruiker implementeert de operatiebibliotheek die overeenkomt met de nieuwe instructie(s) 2 De gebruiker vraagt het systeem de operatiebibliotheek te laden in het sensornetwerk: include use case laad operatiebibliotheek
BLAGE A.
FORMELE USE CASES
73
3 De gebruiker beschrijft de nieuwe instructiebibliotheek voor de VM 4 De gebruiker vraagt het systeem de instructiebibliotheek te laden in de juiste VM op het sensornetwerk: include use case wijzig VM
Uitbreidingen: 1.a De operatiebibliotheek is reeds geïmplementeerd 1.a.1 Ga naar stap 2 3.a De beschrijving bestaat reeds 3.a.1 Ga naar stap 4
A.4
Nieuwe context(en)
Belang: Primair Gebruikt: •
wijzig VM, zie A.2, pagina 71
Primaire belanghebbende: Precondities: •
Gebruiker van het systeem
Het systeem is reeds geladen op de sensorknopen
Postcondities: •
De context(en) is/zijn toegevoegd aan de virtuele machine
Hoofdscenario: 1 De gebruiker maakt een beschrijving van de nieuwe context(en) 2 De gebruiker vraagt het systeem de virtuele machine uit te breiden met de beschreven context(en) 3 include use case wijzig VM
Uitbreidingen: 1.a De beschrijving bestaat reeds 1.a.1 Ga naar stap 2
BLAGE A.
A.5
FORMELE USE CASES
Nieuwe virtuele machine
Belang: Primair Primaire belanghebbende: Precondities: •
74
Gebruiker van het systeem
Het systeem is reeds geladen op de sensorknopen
Postcondities: •
De virtuele machine is geladen op de sensorknopen en klaar voor gebruik
Hoofdscenario: 1 De gebruiker maakt een beschrijving van de virtuele machine 2 De gebruiker vraagt het systeem de virtuele machine te laden in het sensornetwerk 3 Het systeem verspreidt de beschrijving naar de sensorknopen 4 [Op elke knoop] Het systeem ontvangt een beschrijving 4.1 Het systeem maakt en initialiseert de virtuele machine op de sensorknoop 4.2 [Voor elke context] Het systeem maakt en initialiseert de context. 4.3 [Voor elke context] Het systeem voegt de context toe aan de nieuwe virtuele machine.
Uitbreidingen: 1.a De beschrijving bestaat reeds 1.a.1 Ga naar stap 2 2.a De beschrijving is ongeldig 2.a.1 Het systeem meldt de fout aan de gebruiker 2.a.2 use case faalt 4.1.a De virtuele machine is reeds aanwezig op de sensorknoop 4.1.a.1 use case eindigt
