Academiejaar 2013–2014
Faculteit Ingenieurswetenschappen en Architectuur Valentin Vaerwyckweg 1 – 9000 Gent
Het benchmarken, evalueren en vergelijken van positioneringsalgoritmen met visuele front-end applicatie.
Masterproef voorgedragen tot het behalen van het diploma van Master in de industriële wetenschappen: informatica
Jonathan DE BAERE Promotoren:
Geert VAN HOOGENBEMT Ingrid MOERMAN
Begeleiders:
Tom VAN HAUTE Eli DE POORTER Jen ROSSEY
Inhoud Dankwoord ......................................................................................................................... 3 Abstract .............................................................................................................................. 4 Abstract (English) ............................................................................................................. 4 Lijst van figuren ................................................................................................................ 5 Lijst van tabellen............................................................................................................... 7 1
Introductie ............................................................................................................... 8 1.1
Lijst van begrippen ............................................................................................ 9
1.2
Indoor lokalisatie ............................................................................................. 10
1.3
Het belang van onderzoek voor indoor lokalisatie. ................................... 10
1.4
Lokalisatie technieken .................................................................................... 11
1.4.1
Ranging ...................................................................................................... 12
1.4.2
Location Estimation ................................................................................. 13
1.5
Metrieken........................................................................................................... 15
1.5.1
Puntaccuraatheid ..................................................................................... 16
1.5.2
Ruimteaccuraatheid ................................................................................ 16
1.5.3
Vertraging ................................................................................................. 17
1.5.4
Energieverbruik........................................................................................ 17
1.5.5
Deployment ............................................................................................... 18
2
Applicatie ............................................................................................................... 19 2.1
Doelstelling en minimale eisen van de applicatie ...................................... 19
2.1.1
Selectie van experimenten ..................................................................... 20
2.1.2
Kaartweergave van experimenten ....................................................... 21
2.1.3
Vergelijking van de metrieken .............................................................. 22
2.1.4
Scoreberekening voor de algoritmen................................................... 23
2.2
Details van de uitwerking ............................................................................... 24
2.3
Mogelijke uitbreidingen.................................................................................. 24
2.4
Technologie en implementatie. ..................................................................... 25
2.4.1
Protocol Buffers ........................................................................................ 25
1
2.4.2
Back-end in JSF ......................................................................................... 26
2.4.3
Front-end ................................................................................................... 27
2.4.4
Klassendiagram ........................................................................................ 29
2.5
Databank structuur .......................................................................................... 33
2.5.1
Experimenten cache in de databank .................................................... 33
2.5.2
Applicatie parameters in de databank. ................................................ 33
2.6
Aandachtspunten ............................................................................................. 35
2.6.1
JSON data-omvang beperken ................................................................. 35
2.6.2
Weergave van grafieken ......................................................................... 36
3
Analyse van algoritmen ...................................................................................... 38 3.1
Gebruik van robuuste statistieken ................................................................ 38
3.2
Scoreberekening ............................................................................................... 41
3.2.1 3.3
Afbeeldingsfunctie ................................................................................... 41
Applicatie in gebruik: beoordeling van algoritmen. ................................. 44
3.3.1
Uitzonderingen op basis van tijd .......................................................... 44
3.3.2
Uitzondering op basis van plaats .......................................................... 45
3.3.3
Uitzonderingen af te leiden uit statistiek............................................ 47
3.4
Applicatie in gebruik: Hybride RSSI algoritme. .......................................... 48
4
Besluit ..................................................................................................................... 54
5
Bibliografie ............................................................................................................ 56
6
Bijlagen ................................................................................................................... 58 6.1
Klassendiagram................................................................................................. 58
2
Dankwoord Ik wil graag iedereen bedanken voor het spenderen aan tijd en inbrengen van kennis om me te helpen bij deze masterproef. Ik dank bijzonder mijn begeleiders Geert Van hoogenbemt, Tom Van Haute, Jen Rossey en Eli De Poorter voor de vele deskundige begeleiding. Ik heb veel bijgeleerd op verschillende vlakken, en ik ben dankbaar dat ik aan dit interessante project kon meewerken. Dank aan familie en vrienden die mij moed gaven voor de vele uren die ik aan de masterproef heb gespendeerd. Ik dank ook mede studiegenoot Cédric Verstraeten voor het zorgvuldig nalezen van mijn tekst.
3
Abstract Om binnenshuis te positioneren zijn er veel verschillende algoritmen en technieken uitgedacht. Deze masterproef legt zich toe op het uniform vergelijken van deze algoritmen. Door middel van statistische analyse kunnen algoritmen worden gequoteerd. Niet enkel de accuraatheid is van belang, diverse gebruiksomgevingen stellen specifieke eisen. Daarom moeten alle meetresultaten in rekening worden gebracht. Voor deze masterproef wordt een applicatie ontwikkeld die met visuele uitvoer de analyse mogelijk maakt. Samen met de eisen van een gebruiksomgeving kan een geschikt algoritme worden gezocht.
Abstract (English) Many algorithms and techniques are being developed to perform indoor positioning. This thesis tries to uniformly compare these algorithms; by analyzing them statistically, they can be benchmarked and compared. Accuracy is not the only important detail; different use cases require specific demands. All possible measurements should be taken into account. An application is being developed for this thesis; its purpose is to visualize the algorithm’s results for further analyzing. With the use case in mind, an appropriate algorithm and system can be found.
4
Lijst van figuren Figuur 1: voorbeeld van indoor positioning op de smartphone. ......................................... 8 Figuur 2: snijdende hyperbolen door 2 koppels ontvangers met TDOA [5] ..................... 12 Figuur 3: intersectie van de rechten met behulp van AoA [5] ........................................... 12 Figuur 4: schematische voorstelling van het gebruik van metrieken om een vergelijking te maken tussen algoritmen .............................................................................. 15 Figuur 5: selectie van beschikbare experimenten ................................................................ 20 Figuur 6: geografische weergave van het uitgevoerde algoritme ..................................... 21 Figuur 7: vergelijking van de metrieken in functie van de tijd .......................................... 22 Figuur 8: vergelijking per metriekgemiddelde ..................................................................... 22 Figuur 9: berekening van de score en visuele weergave ..................................................... 23 Figuur 10: codefragment protobuff message......................................................................... 25 Figuur 11: ondersteunde versies van jQuery [16] ................................................................. 27 Figuur 12: samenvatting van klassendiagram ....................................................................... 29 Figuur 13: structuur van de databasetabellen. ...................................................................... 34 Figuur 14: voorbeeldcode van een grafiek in SVG opgemaakt ........................................... 36 Figuur 15: metriek in functie van de tijd. De eerste meting is een uitschieter. .............. 44 Figuur 16: weergave op de kaart van verschillende positioneringen. De zwarte lijnen zijn verbindingen tussen de echte en de geschatte locatie (respectievelijk halve en volle bollen). ................................................................................................................................ 45 Figuur 17: alle werkelijke punten verwijzen naar één enkel geschatte locatie, hier gaat iets fout. ........................................................................................................................................ 46 Figuur 18: gewichten tussen vaste nodes worden gebruikt in de berekening. [22] ....... 48 Figuur 19: het testbed met vaste en mobiele nodes. [22] .................................................... 48 Figuur 20: gemiddelde positioneringsfout per uitgevoerd uitzendvermogen................ 49 Figuur 21: verdeling van de positioneringsfout (in meter) van de vier experimenten. 50 Figuur 22: verdeling van de positioneringsfout (in meter) van de vier experimenten met kleinere intervalklassen. ................................................................................................... 50 Figuur 23: verdeling van de vertraging (in milliseconden) van de vier experimenten. 50 Figuur 24: lokalisatiefout in de kamers dicht bij de nodes ................................................. 51 Figuur 25: lokalisatiefout in de hall ver van de nodes ......................................................... 51 Figuur 26: lokalisatiefout in functie van de tijd .................................................................... 51 Figuur 27: klassendiagram: JSF Beans ..................................................................................... 58 Figuur 28: klassendiagram: data-klassen................................................................................ 59 Figuur 29: klassendiagram: dataklassen voor de front-end ................................................ 60 5
Figuur 30: klassendiagram: hulpklassen ................................................................................. 60 Figuur 31: klassendiagram: metrieken en profielen ............................................................ 61 Figuur 32: klassendiagram: testbedden en nodes. ................................................................ 61
6
Lijst van tabellen Tabel 1: metrieken ...................................................................................................................... 16 Tabel 2: voorbeeld van ruimte-accuraatheid matrix ........................................................... 17 Tabel 3: belangrijkste browsers en hun versie die SVG ondersteunt. .............................. 36 Tabel 4: distributie van de reeksen getallen. ......................................................................... 39 Tabel 5: Analyse van de getallen per reeks. ........................................................................... 39 Tabel 6: uitvoer van de functie (a) bij enkele invoerwaarden. ........................................... 43 Tabel 7: zendvermogen voor de vier experimenten [23] .................................................... 49 Tabel 8: statistische gegevens van de positioneringsfouten. ............................................. 49
7
1 Introductie In het alledaagse leven is de digitale connectiviteit overal vertegenwoordigd. Meer dan één op twee verkochte telefoons is een smartphone [1]. Dankzij het telefoonnetwerk of de talrijke hotspots is een verbinding met het internet altijd verzekerd. Veel nieuwe toepassingen maken gebruik van die connectiviteit en bieden de gebruikers nuttige informatie of entertainment. Voor veel van deze nieuwe toepassingen is de context van de gebruiker belangrijk. De locatie of positie is een cruciaal gegeven [2]. Denk hierbij aan een winkelcentrum met binnenruimtes en winkels. Toepassingen op de smartphone kunnen informatie of aanbiedingen voorstellen van de winkel waar de gebruiker zich bevindt. Er zijn veel technieken om met de bestaande technologieën en infrastructuur de locatie van de gebruiker te bepalen. In openlucht is GPS (of alternatieven zoals GLONASS) een zeer goede oplossing. Binnenshuis echter, worden de nodige signalen vaak geblokkeerd en is er nood aan betere systemen. Daarom wordt er onderzoek verricht naar nieuwe technologieën en algoritmen. In deze masterproef worden enkele aspecten van het onderzoek aan het licht gebracht. Er wordt een tool ontwikkeld die nuttig kan zijn in het onderzoek. De tool is een applicatie die een grondige analyse van nieuwe systemen mogelijk maakt en die verschillende systemen met elkaar kan vergelijken.
Figuur 1: voorbeeld van indoor positioning op de smartphone.
8
1.1 Lijst van begrippen Benchmark
Letterlijk een meetspijker; een testprocedure om systemen of apparaten met elkaar te kunnen vergelijken.
Metriek
Door de werking en de uitvoer van de algoritmen te analyseren kunnen verschillende metrieken worden berekend, rechtstreeks of onrechtstreeks uit de meetwaarden. Ze kenmerken de performantie van het algoritme. Voorbeelden van metrieken zijn: accuraatheid, vertraging, energieverbruik, etc. [3]
SUT
System Under Test. Het geheel van lokalisatiealgoritme en werkwijze dat op de proef wordt gesteld tijdens een experiment.
Score
Een getal dat wordt toegekend als resultaat van een metriek. Met de scores kunnen lokalisatiealgoritmen met elkaar worden vergeleken.
Testbed
Een faciliteit die voorzien is van apparatuur om benchmarking te kunnen uitvoeren. In deze context is een testbed een gebouw met draadloze sensoren.
Node
Een autonoom deeltje in het systeem, dat zelf taken kan uitvoeren. Maar door een netwerk van nodes wordt een systeem gebouwd. Nodes in lokalisatie kunnen de draadloze sensoren zijn. Mobiele nodes zijn ook objecten die gelokaliseerd kunnen worden.
Experiment
Een algoritme dat wordt uitgevoerd op een testbed. Het resultaat van een experiment bevat meerdere gelokaliseerde punten van een vaste of een mobiele node.
Ground Truth
De gekende ware positie van een te lokaliseren object. Het geldt als referentie voor de foutberekening.
9
1.2 Indoor lokalisatie Positiebepaling voor binnenshuis verschilt op veel vlakken van het veel gebruikte en bekende GPS-systeem. Doordat de satellieten een signaal uitsturen met een laag vermogen is dit onbruikbaar zonder directe zichtverbinding [4]. Binnenshuis moet vooral worden rekening gehouden met obstakels, interferentie en andere storende elementen. Om positiebepaling mogelijk te maken binnen een gebouw kan gebruik gemaakt worden van een WSN (Wireless Sensor Network) [5]. Dat zijn apparaten (nodes) op vaste bekende plaatsen in het gebouw, die met één of meerdere draadloze technologieën in staat zijn om te communiceren met de lokaliseerbare apparaten (ook nodes genoemd). Een goed voorbeeld van een bruikbare technologie is Wi-Fi (IEEE 802.11), dit wordt duidelijk in sectie 1.4.1. De positiebepaling gebeurt in twee fasen. Eerst wordt er de afstand tussen de nodes berekend door het draadloze signaal te analyseren, dit heet ranging. Daarna kan men die afstanden gebruiken om een schatting (estimation) te maken van de positie. Dit wordt verder uitgelegd in sectie 1.4.
1.3 Het belang van onderzoek voor indoor lokalisatie. De context van de gebruiker kan van nut zijn voor veel nieuwe toepassingen, bij fysieke toepassingen of op het internet (zoals sociale media). Door kennis van de positie kunnen allerlei taken worden geautomatiseerd. Er is al veel onderzoek verricht naar indoor lokalisatie, maar dat zijn individuele experimenten die niet altijd even bruikbaar zijn voor commerciële doeleinden. Een van de grootste nadelen van het grote aantal individuele onderzoeken is dat ze worden geëvalueerd in niet vergelijkbare en niet reproduceerbare omstandigheden. Daarom is het EVARILOS (Evaluation of RF-based Indoor Localization Solutions) project opgestart, als onderdeel van Europees wetenschappelijk onderzoek (FP7). Het EVARILOS project wil een betrouwbare vergelijking maken tussen verschillende indoor positioneringsalgoritmen [6]. Het omschrijft hiervoor een benchmarking methodologie. Hierbij wordt niet enkel rekening gehouden met de accuraatheid, maar ook met robuustheid, vertraging, energieverbruik, etc. Deze bijkomende aspecten zijn zeker belangrijk bij ontwikkeling van commerciële toepassingen, want de meest accurate algoritmen zijn niet altijd de beste. Om de algoritmen te kunnen uittesten in levensechte situaties wordt een testbed gebouwd die rekening houdt met mogelijke randfactoren uit echte omgevingen (zoals interferentie, type muren…). De EVARILOS benchmark methodologie is al geïmplementeerd op twee testbedden: TWIST in de TUB (Berlijn),en w-iLab.t in iMinds (Gent). Beide testbedden zijn voorzien van vaste draadloze nodes die beschikken over 10
IEEE 802.11, IEEE 802.15.1 en IEEE 802.15.4 technologie. Tijdens het uitvoeren van een experiment kunnen zowel mobiele als vaste nodes gelokaliseerd worden. De nodes sturen periodiek alle mogelijke meetresultaten door naar de centrale databank. De typische gebruiksscenario’s [3] waar het onderzoek zich op richt zijn de volgende:
Hospitaal Indien de zorgen over de privacy van de patiënten buiten beschouwing worden gelaten, kan binnenhuis lokalisatie nuttig zijn voor de veiligheid van de patiënt. Lokalisatie kan in het hospitaal op verschillende manieren gebruikt worden. Een voorbeeld is draagbare alarmknop om de verpleegsters te waarschuwen. De verpleegsters worden gealarmeerd en krijgen informatie over de locatie van de patiënt. Doordat de nieuwe ziekenhuiscomplexen heel groot worden, en doorgaans voorzien zijn van een uitgebreide technologische infrastructuur is dit een belangrijke doelgroep voor het onderzoek.
Mijn Ondanks de grote zorg voor veiligheid, kan er in een mijn altijd een ongeval voorkomen waardoor mijnwerkers opgesloten geraken in de mijnschacht. Dankzij de indoorlokalisatie kan worden bijgehouden wie en wat er zich achter de obstakels bevindt. Bij de normale werking van de mijn kan de indoor lokalisatie ook dienen om efficiënt gebruik van de machines te plannen, en om de machines terug te vinden.
1.4 Lokalisatie technieken In een praktische implementatie van lokalisatie met draadloze netwerksensoren wordt er bijna altijd gebruik gemaakt van geschatte afstanden om een positionering te berekenen. Er zijn ook andere technieken die geen gebruik maken van afstanden, zoals “nabijheid”: recentelijk bracht Apple met iBeacon een commerciële toepassing uit [7]. Nadat de afstanden tussen verschillende nodes bekend zijn (ranging), kan de positie berekend worden (location estimation). Dit kan gebeuren met driehoeksmeetkunde, maar ook met statistische gegevens uit een leerproces. Om de achtergrond te schetsen worden de technieken hier kort samengevat in de volgende subsecties. De meeste technieken zijn overgeërfd uit andere toepassingen, bijvoorbeeld het schatten van de afstand voor het afvuren van kanonnen.
11
1.4.1 Ranging Verschillende draadloze technologieën stellen hun eigen specifieke ranging technieken beschikbaar. Wi-Fi (IEEE 802.11) is voor bijna alle technieken bruikbaar. Hier volgt een opsomming van verschillende technieken om afstand te schatten op basis van draadloze signalen [5] [8]:
RSSI (Received Signal Strength Indication) is de meest eenvoudige informatie die kan uitgelezen worden van draadloze sensoren. Aan de hand van de signaalsterkte wordt afgeleid hoe ver het signaal moest reizen tot bij de ontvangende sensor, de signaalsterkte is omgekeerd evenredig met de kwadraat van de afstand. Signalen verzwakken over de afstand, maar ook als ze door obstakels gaan.
ToA (Time of Arrival) of ToF (Time of Flight) berekent het tijdsverschil tussen verzenden en ontvangen van het signaal. Het tijdsverschil is lineair met de afstand. De berekening is eenvoudig, maar heel het systeem moet nauwkeurig afgesteld worden aangezien de snelheid van de draadloze signalen de snelheid van het licht in vacuüm benadert. De vluchttijd van het signaal is zo kort (67 nanoseconden voor 20 meter) dat de klok van de verzender en ontvanger zeer synchroon moeten lopen om dit correct te kunnen meten.
TDoA (Time Difference of Arrival) werkt gelijkaardig aan vorige techniek maar vereist geen precieze synchronisatie van de klok op het lokaliseerbare object. Wel moeten er meerdere draadloze sensoren zijn. Een koppel sensoren geeft (in twee dimensies) een hyperbool als resultaat. Een ander koppel van sensoren biedt een tweede hyperbool die kruist met de eerste (Figuur 2). De kruising is het gelokaliseerde punt. Zoals de vorige oplossing moeten de klokken van de vaste sensoren nauwkeurig worden afgesteld.
Figuur 2: snijdende hyperbolen door 2 koppels ontvangers met TDOA [5]
Figuur 3: intersectie van de rechten met behulp van AoA [5]
AoA (Angle of Arrival) krijgt via antennes informatie over de hoek van het inkomende signaal. Vaak wordt gebruik gemaakt van antennearrays (of 12
stelsels). Een positie van de antenne en de berekende hoek leveren een rechte op in de tweedimensionale ruime. De intersectie van twee of meerdere rechten is de geschatte locatie, de kruising is niet exact indien er ruis voordoet zoals in Figuur 3.
DTDoA (Differential Time Differences of Arrival) gebruikt het verschil in TDoA-metingen. Zo kunnen problemen met tijdsynchronisatie voorkomen worden. Hiervoor is nog minstens een vierde sensor nodig die een speciaal bericht moet initialiseren.
Hybride technieken combineren bovenstaande technieken.
1.4.2 Location Estimation De afstandsmeting (ranging) kan verwerkt worden door methodes die kunnen opgedeeld worden in twee categorieën:
Methodes met of zonder fingerprinting [9] [10]. Bij fingerprinting (letterlijk vingerafdrukken) wordt het algoritme getraind en worden resultaten (of hun fingerprint) bewaard in een databank. De training vooraf kan veel tijd innemen. Er moeten genoeg gegevens worden verzameld voor het algoritme gebruikt kan worden. Tijdens de gebruiksfase worden de resultaten vergeleken met die uit de databank. De opgeslagen gegevens die het best overeenkomen met de nieuwe meting duiden de mogelijke locatie aan. Methodes zonder fingerprinting hebben geen training nodig en zijn dus sneller op te zetten, deze methodes gebruiken enkel realtime gegevens.
Geometrische of statistische methodes [6]. Bij de eerste soort wordt met driehoeksmeetkunde van minstens drie referentiepunten een positie berekend. Bij statistische methodes zijn er drie belangrijke groepen: o Statistische multilateratie [11] minimaliseert de som van de kwadraten van de positioneringsfouten. o Meest aannemelijke schatter [12] gebruikt een kostfunctie en probeert de kost te minimaliseren (meest aannemelijke positie). In [13] wordt een lineaire regressie gebaseerd op de kostfunctie voorgesteld, geïntroduceerd door iMinds. o Bayesiaanse statistiek gebruikt het theorema van Bayes [14].
De berekeningen kunnen worden uitgevoerd in ‘de cloud’. Het WSN of een server berekent de locatie en geeft die door naar de vragende partij (een achterliggend systeem of de gelokaliseerde apparaten zelf). De berekeningen kunnen ook gebeuren op het gelokaliseerde apparaat zelf. Indien dit een apparaat is van een toevallige, occasionele gebruiker moet worden rekening gehouden met:
Hoger energieverbruik op het toestel: de berekeningen vragen meer tijd op de processor of communicatiechip. 13
Extra software te installeren: indien de lokalisatieoplossing niet standaard is geïmplementeerd in het besturingssysteem, moet extra software worden geïnstalleerd. Dit vertraagt het eerste gebruik en kan te omslachtig zijn voor eenmalig gebruik.
Hardware compatibiliteit: op oudere of goedkopere toestellen kan de ondersteuning voor nieuwe technologie ontbreken.
Privacy: toevallige gebruikers die met een nieuw systeem verbinden weten niet wat er met de verzamelde data kan gebeuren.
14
1.5 Metrieken Om de performantie van de algoritmen te analyseren wordt gebruik gemaakt van metrieken [3]. De metrieken zijn een representatie van de kenmerken van het System Under Test (SUT). Elk meetresultaat kan rechtstreeks of onrechtstreeks worden omgezet naar een metriek. De metrieken zijn getallen die kunnen gebruikt worden om een score te berekenen en algoritmen met elkaar te vergelijken, hoe de metriek wordt omgezet in een score wordt verder uitgelegd in sectie 3.2.1. Een globale vergelijking wordt gemaakt door gewogen scores op te tellen, de gewichten zijn bepaald door de prioriteit van de metriek. De metrieken hebben een andere prioriteit indien ze gebruikt worden in een andere omgeving. In Figuur 4 is in schematische vorm een voorstelling weergegeven van het gebruik van metrieken.
Figuur 4: schematische voorstelling van het gebruik van metrieken om een vergelijking te maken tussen algoritmen
Elke metriek wordt berekend op zijn eigen manier. Metrieken kunnen worden ingedeeld in twee groepen: primaire en afgeleide metrieken. De eerste groep volgt rechtstreeks uit metingen, de metrieken worden dan berekend met een wiskundige formule. De secundaire (of afgeleide) metrieken worden berekend met de data van de primaire. In Tabel 1 worden beide groepen opgesomd.
15
Primaire metrieken
Secundaire metrieken
Puntaccuraatheid
Interferentie bestendigheid
Ruimteaccuraatheid
Omgeving bestendigheid
Vertraging
Mobiliteit
Energieverbruik
Schaalbaarheid
Herhaalbaarheid
Tabel 1: metrieken
De eerste groep van metrieken is vooral van belang voor de probleemstelling in deze masterproef, daarom worden deze afzonderlijk kort toegelicht.
1.5.1 Puntaccuraatheid Het resultaat van de positionering is een punt (x1,y1,z1) met coördinaten in de drie ruimtelijke dimensies. Het berekende punt P wordt vergeleken met de Ground Truth G, dit is de werkelijke positie (x2,y2,z2) van het gelokaliseerde punt. De fout op de positionering is bijgevolg de euclidische afstand tussen de werkelijke positie en de gelokaliseerde positie. 𝑑(𝑃, 𝐺) = √(𝑥2 − 𝑥1 )2 + (𝑦2 − 𝑦1 )2 + (𝑧2 − 𝑧1 )2 Tijdens het uitvoeren van het algoritme kan deze afstand d(P,G) voor elk gelokaliseerd punt worden berekend. Over de gehele uitvoer van een algoritme kunnen statistische gegevens worden opgesteld met deze afstand: het gemiddelde, de mediaan, de variantie… Deze metriek is voor de meeste toepassingen het belangrijkste gegeven, indien de puntaccuraatheid niet voldoet kan het positioneringssysteem geen meerwaarde bieden aan de gebruikers. Om een universele compatibiliteit te behouden gebruiken we voor deze maat van lengte de meter, omdat het de SI-eenheid is. De meter wordt gebruikt voor zowel de coördinaten als de positioneringsfout.
1.5.2 Ruimteaccuraatheid De ruimteaccuraatheid is wel verwant met de voorgaande metriek, maar heeft een eigen beoordelingsmethode nodig. De ruimteaccuraatheid stelt voor hoe goed de kamer wordt bepaald waarin het gelokaliseerde punt zich bevindt. Hier is de Ground Truth de werkelijke ruimte of kamer waar het gelokaliseerde punt zich bevindt. Om deze metriek te analyseren wordt een kruistabel opgemaakt, met als invoer de werkelijke ruimte, als uitvoer de bepaalde ruimte en hoeveel keer deze werd geschat. In de Tabel 2 staat een voorbeeld uitgeschreven, hierbij werden telkens 10 meetpunten verzameld voor elke kamer. 16
Werkelijke ruimte
Geschatte ruimte Kamer 101
Kamer 102
Kamer 103
Kamer 104
Kamer 101
6
3
1
0
Kamer 102
1
7
1
1
Kamer 103
0
2
8
0
Kamer 104
0
1
0
9
Tabel 2: voorbeeld van ruimte-accuraatheid matrix
Het cijfer op de diagonale as van de matrix is het aantal keer dat de kamer juist bepaald werd. De verhouding van de juiste bepalingen tot het totaal aantal schattingen vormt het succespercentage van het algoritme. Met de gegevens van bovenstaande tabel wordt dit: 𝑠𝑢𝑐𝑐𝑒𝑠𝑝𝑒𝑟𝑐𝑒𝑛𝑡𝑎𝑔𝑒 =
6+7+8+9 = 75% 4 ∗ 10
1.5.3 Vertraging Een System Under Test (SUT) kan worden geprogrammeerd om periodiek de positie te berekenen. Maar de vertraging (latency) die hier als metriek wordt gebruikt is het verschil in tijd tussen de start van de berekening en het verkrijgen van een gelokaliseerd punt. Een kleinere vertraging laat niet alleen een betere resolutie van het lokaliseren toe, maar garandeert ook dat het systeem snel genoeg kan reageren op gebeurtenissen. Deze metriek kan ook statistisch worden geanalyseerd. De SI-eenheid voor tijd is seconde. Omdat in deze toepassingen vaak waarden voorkomen kleiner dan één seconde, zal hiervoor milliseconde worden gebruikt.
1.5.4 Energieverbruik Als alle nodes in het draadloze sensor netwerk (WSN) enkel draadloos werken, is het energieverbruik een zeer belangrijk aspect. Ook de lokaliseerbare node is meestal mobiel en de capaciteit van een batterij is beperkt. Het energieverbruik is afhankelijk van veel verschillende factoren. De node zal meer energie verbruiken bij het uitzenden van draadloze signalen, maar ook bij het uitvoeren van berekeningen. De energie (Joule) die wordt gemeten, wordt in context geplaatst van de tijd (seconden), daarom wordt er gebruik gemaakt van Watt (=Joule/seconde) om de eenheid uit te drukken. Per gelokaliseerd punt hoort een energiewaarde, dus deze
17
gegevens kunnen ook statistisch worden geanalyseerd over het verloop van een experiment.
1.5.5 Deployment Deze metriek behoort niet tot de primaire of secundaire metrieken die hier vooraf besproken werden, maar het is een groep op zichzelf. Deze metriek wordt ook niet berekend op basis van de uitvoerresultaten van de System Under Test (SUT), maar stellen de randgegevens voor die belangrijk zijn om het systeem op te stellen:
De kostprijs van de installatie
De nodige hardware
Training-fase van het algoritme
Onderhoud van het systeem
…
18
2 Applicatie De opdracht van deze masterproef bestaat erin om een front-end applicatie te ontwikkelen waarmee de experimenten kunnen worden gevisualiseerd en geanalyseerd. Het is de bedoeling dat algoritmen met elkaar kunnen worden vergeleken. Dan kan daaruit worden afgeleid welke algoritmen het best geschikt zijn voor een bepaalde gebruiksomgeving.
2.1 Doelstelling en minimale eisen van de applicatie De analyse en de vergelijking van experimenten kan in 3 stappen gebeuren: 1.
Het geografisch visueel controleren: hierbij wordt typisch een experiment afzonderlijk bekeken en ziet men op een grondplan snel de nauwkeurigheid van de lokalisatie.
2.
Meetresultaten vergelijken: bij elke periodieke meting zijn er gegevens over de afwijking, het energieverbruik en de vertraging. Deze kunnen worden weergegeven in de gepaste grafiek zodat men in functie van de tijd het verloop van die meetresultaten kan vergelijken. Over de totale duur van het experiment kunnen er van alle waarden statistische gegevens worden opgesteld. Die laatste gegevens laten een goede vergelijking toe van het gedrag van verschillende experimenten.
3.
Een uiteindelijke conclusie: als een algoritme wordt beoordeeld, worden alle meetresultaten vergeleken met de aanvaardbare waarden die een gebruiksomgeving vereist. Deze vormen samen een “profiel” van eisen. Een gebruiksomgeving legt voor elke waarde van meetresultaten een ideaal bereik op. Met dit bereik kan een wiskundige functie worden opgesteld die een score geeft. Aan de hand van het profiel wordt een score berekend voor een algoritme.
In de volgende secties volgt een oplijsting van de verschillende luiken die door de applicatie verwezenlijkt worden.
19
2.1.1 Selectie van experimenten
Figuur 5: selectie van beschikbare experimenten
Om een vergelijking tussen de verschillende experimenten mogelijk te maken, moet de gebruiker deze kunnen selecteren. Een lijst van de beschikbare experimenten kan lang worden, daarom is er nood aan een filtering. Deze filtering laat toe om een bepaald experiment sneller terug te vinden, maar ook om vergelijkbare experimenten naast elkaar te plaatsen. Het selectiescherm is het eerste wat de gebruiker te zien krijgt, want zonder geselecteerde experimenten kan er niets worden gevisualiseerd. Het zal vaak voorkomen dat de gebruikers een eerder gekozen selectie willen opvragen, zodat ze kunnen verder werken waar ze vorige keer waren gestopt. Daarom moet dit kunnen worden opgeslagen. De werking van dit deel en alle andere delen moeten voor zichzelf spreken. Bij een gebruiksvriendelijk ontwerp is er geen nood aan een handleiding en dit bespaart veel tijd en frustraties.
20
2.1.2 Kaartweergave van experimenten
Figuur 6: geografische weergave van het uitgevoerde algoritme
Om het gedrag van een bepaald experiment nauwkeurig te bekijken, wordt gebruik gemaakt van een visuele kaart. De kaart bevat het grondplan van een geselecteerd testbed en daarbovenop staan de gelokaliseerde punten. Zowel de gelokaliseerde punten als de Ground Truth worden samen weergegeven zodat de afwijking ertussen duidelijk wordt. Met een tijdslijn kan een beperkt interval worden geselecteerd. Dit heeft verschillende voordelen:
Met teveel informatie wordt de kaart onduidelijk; een tijdslijn laat toe om een selectie van de data te maken.
Door de tijdslijn te verschuiven verkrijgt men een simulatie van hoe het algoritme reageert in functie van de tijd.
Gegevens die in een opstartfase van het algoritme liggen, kunnen een vertekend beeld geven en kunnen worden weggefilterd.
Teveel punten in de weergave zouden het toestel van de gebruiker kunnen overbelasten en dat maakt de applicatie minder gebruiksvriendelijk. 21
Het is mogelijk om verschillende experimenten op één kaart te vergelijken. Met verschillende kleuren kunnen ze van elkaar worden onderscheiden.
2.1.3 Vergelijking van de metrieken
Figuur 7: vergelijking van de metrieken in functie van de tijd
Om experimenten met elkaar te vergelijken wordt er gebruik gemaakt van grafieken die de metrieken visualiseren. In Figuur 7 is een grafiek getekend die in het verloop van de tijd de metriek weergeeft. Het is nog meer van belang om het gemiddelde en de variantie van de metrieken te kunnen vergelijken. Per metriek wordt een grafiek opgemaakt. Bij alle gebruikte primaire metrieken is een staafdiagram een goede manier om de performantie af te lezen.
Figuur 8: vergelijking per metriekgemiddelde
De variantie of standaardafwijking wordt weergegeven als “foutmarge”. Het is niet de absolute fout, maar maakt duidelijk hoe variabel de resultaten zijn. Hoe groter de variantie, hoe meer verschil er tussen elke meting zit. Dit geeft aan hoe stabiel de lokalisatie is.
22
2.1.4 Scoreberekening voor de algoritmen
Figuur 9: berekening van de score en visuele weergave
De uiteindelijke conclusie van de benchmarking wordt weergegeven als een score. De totale score van het algoritme is een verzameling van de (gewogen) scores die elke metriek krijgt. De quotering van de metrieken zijn afhankelijk van het gebruiksscenario. De wensen van dat scenario zitten vervat in een “profiel”. Het profiel bepaalt voor elke metriek een gewenste minimum- en maximumwaarde, in sectie 3.2 wordt uitgelegd hoe de metriek wordt omgevormd naar een score. Het profiel bepaalt ook hoe belangrijk elke metriek is, zodat deze metrieken samen met hun gewicht tot een totaalscore komen. Het algoritme met de hoogste totaalscore is het meest geschikt voor het gebruiksscenario van het profiel. Om een betere analyse mogelijk te maken, moeten de profielen ook bewerkbaar zijn door de gebruiker. Fijne aanpassingen kunnen betere analytische resultaten opleveren in het vergelijken van gelijkaardige of uiteenlopende algoritmen. 23
2.2 Details van de uitwerking De volgende items werden geïmplementeerd om de applicatie beter en gebruiksvriendelijker te maken.
Gebruikers kunnen zelf profielen aanmaken ter berekening van de score. Naast de voorgeprogrammeerde profielen van gebruiksomgevingen, kunnen de gebruikers ook de parameters aanpassen, zodat metrieken een andere prioriteit krijgen in de berekening van de score.
De bediening van de webapplicatie kan meer geoptimaliseerd worden voor smartphone- en tabletgebruik als er ondersteuning is voor touchscreenbediening. Om de weergave mogelijk te maken wordt zoveel mogelijk cross-platform technologie gebruikt. Zo hoeft de applicatie slechts één keer ontwikkeld worden, om gebruikt te worden op verschillende apparaten.
De gebruiker kan zelf zoveel mogelijk configureren, om te bepalen wat er getekend wordt op de grafieken en visuele voorstellingen. Zodat hij de informatie krijgt die hij wil en niet overspoeld wordt door de rest. Om een bepaald gedrag te analyseren kan het nuttig zijn om bijvoorbeeld het pad van de gelokaliseerde punten te volgen.
Een cache houdt eigenschappen van beschikbare experimenten bij, met het oog op de performantie van het inlezen van bestanden. Eenvoudig beheer is ook noodzakelijk, om bijvoorbeeld experimenten te verwijderen.
2.3 Mogelijke uitbreidingen De volgende items zouden ook kunnen geïmplementeerd worden.
Tijdens de uitvoering van het experiment, zijn de tijdstippen van de lokalisatiepunten niet periodiek. De selectieve tijdlijn moet daarom een tijdstempel kunnen uitlezen om het tijdsverloop van de experimenten lineair weer te geven. Dit kan vooral moeilijk worden als er twee verschillende experimenten op één tijdlijn moeten.
De sessie van de bezoeker kan worden opgeslagen zodat hij later kan verder kijken hoe hij bezig was. In een sessie kan worden bijgehouden welke experimenten er geselecteerd waren.
Experimenten kunnen in real-time worden bekeken.
24
2.4 Technologie en implementatie. De applicatie moet kunnen draaien op een willekeurige moderne computer. Daarom werd er gekozen om de applicatie te bouwen als een webapplicatie. Dit maakt het mogelijk om de applicatie te gebruiken op veel verschillende soorten apparaten, zonder dat er extra software moet geïnstalleerd worden. De enige factor waar rekening mee moet worden gehouden is de manier waarop de applicatie zijn data binnen krijgt. Om experimenten beschikbaar te stellen is er gekozen voor het Protocol Buffers-formaat.
2.4.1 Protocol Buffers Protocol buffers (protobuff) is een gegevensstructuur door Google ontwikkeld. [15] De structuur biedt een manier om data uit te wisselen tussen verschillende programmeeromgevingen. Het gebruik ervan is vergelijkbaar met XML, maar de structuur is ontworpen met het oog op betere performantie. Google biedt een API aan voor C++, Java en Python. Om een correcte implementatie te verkrijgen bij alle deelnemers van de gegevensstructuur, is een message (bericht) opgesteld. Dit is een specificatie die vastlegt hoe de doorgestuurde berichten er zullen uitzien. De message wordt geschreven in een .proto-bestand en schrijft neer welke velden er voorkomen en wat ze doen.
Figuur 10: codefragment protobuff message
De message moet worden gecompileerd om te worden gebruikt in code. Het compileren gebeurt met een tool door Google, de uitvoer daarvan zijn klassen die kunnen worden geïmporteerd in het codeproject. Eenmaal de klassen gecompileerd zijn, kan de code niet meer bewerkt worden. De messages kunnen wel meerdere versies aannemen. Indien een nieuwe berichtspecificatie is vastgelegd moeten de klassen opnieuw gecompileerd worden om in de code de aanpassingen door te voeren. De berichten zullen altijd achterwaarts-compatibel zijn met de vorige versies, het zal dus nooit een bestaand programma minder functioneel maken.
25
2.4.2 Back-end in JSF Voor de implementatie van de applicatie wordt gekozen voor het Java ServerFacesframework. De webapplicatie wordt beschikbaar gesteld door een server; een Tomcatserver op een Linux-systeem voert Java-code uit. In samenwerking met een MySQL databank vormt dit de back-end. De eerste reden voor de keuze van JavaServer Faces is de Java programmeeromgeving, waardoor de protobuff-API door Google kan gebruikt worden. Dankzij de populariteit van Java bestaan er heel wat bibliotheken die van pas kunnen komen in de verdere ontwikkeling van deze applicatie. Daarnaast zijn met JSF versie 2.2 alle kinderziektes verdwenen, en is het een goede manier om een webapplicatie op te bouwen. JavaServer Faces is een framework die veel tijdsbesparing oplevert en waarbinnen op een nette manier kan worden geprogrammeerd. Gelijkaardig aan het MVC (Model-View-Controller) designpattern is er een scheiding tussen de presentatielaag en de logica. Dit laat generieke code toe, wat hergebruik bevordert, vooral binnen de applicatie zelf. Voor sommige doeleinden waarbij formulieren en actieknoppen weinig nut hebben, legt het gebruik van JSF een beperking op. Maar voor deze applicatie, waarbij voornamelijk gegevensverwerking gebeurt, is het ideaal. De voor- en nadelen van JSF worden kort overlopen: Voordelen van JSF
Grote bedrijven (vooral Oracle) zitten achter de ontwikkeling, dit garandeert goed werkende componenten en veel support.
Conceptueel laat het framework hergebruik van code eenvoudig toe.
Er zijn veel componenten standaard beschikbaar, maar ook derde partijen kunnen componenten aanbieden.
Voor de koppeling tussen presentatielaag en logische code worden “Expression Language”-uitdrukkingen gebruikt, die zorgen voor een goede leesbaarheid in de code.
JavaScript code zit ingebed in componenten, sommige logica kan worden uitgevoerd client-sided zonder een nieuwe HTML-request te versturen.
Nadelen
Een steile leercurve voor beginnende programmeurs; was niet echt een nadeel tijdens de ontwikkeling in deze masterproef. Het is wel een nadeel voor latere aanpassingen door programmeurs zonder ervaring met JSF.
Java-code wordt uitgevoerd binnen een Java Virtual Machine. Deze benadering is veilig, maar verlaagt de performantie. De applicatie zou niet geschikt zijn om grote aantallen gebruikers te bedienen. De applicatie kan niet geschaald worden. 26
2.4.3 Front-end Voor de front-end is HTML5 en JavaScript een logische keuze. Het biedt een crossplatform ondersteuning out-of-the-box. Op zowel computers als tablet moet dan geen extra software worden geïnstalleerd om de webapplicatie te kunnen gebruiken. Data moet maar één keer worden doorgespeeld naar de front-end waarna de gebruiker de weergave kan manipuleren zoals hij wil. Er zijn veel JavaScript bibliotheken vrij beschikbaar die gegevens van getallen visueel kunnen weergeven. Zo kan er heel wat bestaande code worden overgenomen. De volgende bibliotheken kunnen gebruikt worden:
jQuery (http://jquery.com/). Dit zorgt ervoor dat er veel sneller kan geprogrammeerd worden in JavaScript en zorgt voor een grotere compatibiliteit met de verschillende browsers. Andere JavaScript bibliotheken steunen ook vaak op jQuery.
Raphaël (http://raphaeljs.com/) vereenvoudigt het tekenen in HTML5. Hiermee kan de kaart worden getekend om een geografische voorstelling te geven. De uitvoer zijn vector-afbeeldingen en laten nog interactiviteit met de gebruiker toe.
D3.js (http://d3js.org/). Hiermee kunnen de overige gegevens worden gepresenteerd in grafieken. De strategie achter deze bibliotheek is het koppelen van data aan svg-elementen.
De bibliotheken maken het programmeren van de front-end veel eenvoudiger en robuuster. Tijdens het programmeren moet geen rekening worden gehouden met ouder versies van de browsers. jQuery belooft alle belangrijke browsers te ondersteunen (Figuur 11) en ondersteunt Internet Explorer vanaf versie 6. Internet Explorer 6 werd uitgebracht in 2001.
Figuur 11: ondersteunde versies van jQuery [16]
27
Bijkomende voordelen van jQuery zijn [17]:
Gebruiksgemak: voor de programmeur wordt het veel eenvoudiger om een programma te schrijven in vergelijking met de standaard JavaScript bibliotheek omdat de syntax veel eenvoudiger en korter is.
Grote bibliotheek: JavaScript heeft een hele reeks extra functies die vaak gebruikte handelingen uitvoeren. In plaats van de handelingen zelf te programmeren, moet dan enkel de functie worden aangeroepen.
Opensource community: gebruikers over het hele internet kunnen plugins schrijven en functionaliteit toevoegen aan jQuery.
Goede documentatie en tutorials: deze zijn beschikbaar op de jQuery-website zelf.
AJAX-support: dit is niet belangrijk voor de applicatie, maar heeft wel voordelen in andere applicaties.
Er is enkel één nadeel aan het gebruik van de jQuery-bibliotheek: er moet een bestand minimaal 90 kB worden meegestuurd in de applicatie. Dit zorgt voor een langere laadtijd, maar deze is te verwaarlozen op moderne computers met hoge snelheidsverbinding.
28
2.4.4 Klassendiagram In Figuur 12 is de globale structuur van alle klassen samengevat. Een paar hoogtepunten worden verder besproken. De gedetailleerde klassendiagrammen zijn te vinden in sectie 6.1, in de bijlagen. evarilos.bench.data evarilos (protobuf generated) <
> ExperimentDataProvider
CachedExperiment
Measurement_point
<<use>>
<<use>> Experiment
ExperimentDA
ExperimentJsonProvider
ExperimentFileProvider
<<use>> Scenario_description
<<use>> <<use>>
<<use>>
Primary_metrics
<<use>>
evarilos.bench.testbed FixedNode
FixedNodeDA
<<use>>
evarilos.bench.helper
evarilos.bench.data.visual
Config
ExperimentFilter
<<use>> <<use>>
VisualExperiment
AverageMetrics VisualFixedNodes
evarilos.bench.profile ProfileDA
Profile
evarilos.bench.beans <<use>>
<<use>>
TestbedBean
ScoreBean
ExperimentsBean
Metric
UploadBean
<<use>>
Figuur 12: samenvatting van klassendiagram
29
De klasse: Experiment De klassen die de data van de experimenten voorstellen worden gegenereerd en gecompileerd door een tool geleverd door Google. Deze tool zet de berichtomschrijving van de protobuf-structuur om in Java-klassen. Deze klassen kunnen later niet meer worden bewerkt en er kan ook niet worden van overgeërfd; dit legt een beperking op. Indien de berichtomschrijving zou veranderen, dan kan deze applicatie niet dynamisch nieuwe velden ontdekken. Daarom zal de berichtomschrijving best in een zo goed mogelijke eindstaat zijn als de applicatie wordt afgewerkt. De klasse bestaat uit velden die het experiment identificeren. Daarnaast zijn er nog verschillende subklassen:
Scenario_description Deze subklasse bevat velden met informatie over hoe het experiment werd uitgevoerd: System Under Test, omstandigheden…
Primary_metrics De statistische gegevens over het verloop van het experiment die al berekend zijn, zijn opgeslagen in deze subklasse.
Measurement_point Voor elke locatiebepaling is een object van deze klasse toegevoegd in een collectie. Deze objecten bevatten zoveel mogelijk informatie over een enkele berekening.
Naast deze klasse, stellen de klassen VisualExperiment en AverageExperiment ook een experiment voor, maar deze klassenstructuur is meer geschikt voor het gebruik van serialisatie van de gegevens. Dit staat verder verklaard in sectie 2.6.1. De Experiment klasse is niet geschikt om naar de databank te schrijven, er zijn te veel velden. Daarom is er nog een klasse CachedExperiment nodig om samenvattende informatie te schrijven in de databank. De databank dient hier enkel als “cache”, om sneller een experiment te kunnen filteren en selecteren. De JSF-beans In de JSF strategie, worden beans gebruikt als koppeling tussen weergave en data. De beans stellen de data beschikbaar voor de view. De beans in deze applicatie zijn ingesteld om te werken op session-niveau, de objecten blijven bestaan zolang de gebruiker bezig blijft op de applicatie. Dit laat toe om eenvoudig geselecteerde parameters te onthouden en dat reeksen data niet steeds opnieuw moeten verwerkt worden. Er zijn verschillende beans, ze zijn elk verantwoordelijk voor het leveren van bepaalde gegevens. Ze stellen de data van de experimenten beschikbaar als JSONstring, die tekst wordt dan ingebed in de “view” en kan dan meegestuurd worden als antwoord op de HTTP-request. De verschillende beans zijn:
30
ExperimentBean Deze bean levert een lijst van beschikbare experimenten die kunnen geselecteerd worden door de gebruiker. De selectie lijst bevat enkel een samenvatting van het experiment. Enkel de experimenten die dan geselecteerd zijn, worden in hun geheel opgeladen en doorgegeven naar de front-end applicatie voor de visuele voorstellingen.
TestbedBean Om de parameters en vaste nodes van de testbedden in de applicatie te programmeren worden deze in de databank bewaard. De TestbedBeanklasse geeft opdracht aan de bevoegde dataklassen om de gegevens op te halen. De beanklasse zorgt ervoor dat deze beschikbaar zijn in de front-end.
ScoreBean Deze klasse doet werk analoog aan de TestbedBean-klasse, maar verwerkt gegevens van de scores en profielen.
UploadBean Deze verzorgt afhandeling van nieuw toegevoegde experimenten.
Om kort de werking van de beans te demonstreren volgt een codevoorbeeld waarin de gebruiker een testbed kan selecteren. De bean stelt een lijst van selecteerbare elementen beschikbaar, alsook een getalwaarde waarin het geselecteerde identificatiecijfer in terecht zal komen:
Deze publieke methodes kunnen benaderd worden in de view (opgemaakt in XHTML) door middel van EL-notering (Expression Language). De component “selectItems” zet voor elke item uit de lijst een “selectItem” in de “selectOneMenu”. Dit laatste component stelt een keuzelijst voor in de webbrowser:
31
Als de gebruiker op de knop “select” drukt, wordt het XHTML formulier gepost naar de server. Het JSF-framework zorgt er zelf voor dat de geselecteerde waarde (value) terecht komt in het veld van de bean waar hij aan gekoppeld was. De waarde kan vervolgens gebruikt worden door andere functies. De acties die de applicatie moet uitvoeren beginnen als een functie in de beans, ze kunnen de acties doorgeven aan andere klassen, maar hun eigen uitvoer bepaalt het verdere verloop van de applicatie. Naargelang de waarde wordt er een andere “view”(weergave) getoond aan de gebruiker. De klassen: VisualExperiment en VisualFixedNodes. Deze klassen zijn enkel bedoeld om reeksen data voor te bereiden op het gebruik in de front-end van de applicatie. Ze bevatten primitieve arrays, zodat de data zonder overhead kan worden doorgestuurd naar het toestel van de gebruiker. Het omvormen van de data naar een andere structuur kan sneller gebeuren op de server. Dit zal ervoor zorgen dat JavaScript de data eenvoudiger kan gebruiken. In plaats een veld op te vragen uit een object dat wordt opgeroepen uit een tabel, kan nu gewoon een getal uit een tabel worden opgeroepen.
32
2.5 Databank structuur Het gebruik van een databank is voor deze applicatie geen noodzaak, alles kan hard geprogrammeerd worden of uit bestanden worden ingelezen. Maar een databank is zeker een meerwaarde voor het snel en goed functioneren. Er zijn twee doelen in het gebruik van de databank: 1. Om de applicatie meer generisch te maken worden alle inleesbare parameters voor het functioneren van de applicatie zelf, in een databank bewaard. Op die manier kunnen ze worden aangepast zonder het wijzigen van programmacode. 2. De bestanden van de Experimenten blijven als bestand op de server. Maar een samenvatting van de omschrijving wordt bijgehouden in de databank zodat er sneller kan gefilterd worden. Dit levert een grote winst op vlak van snelheid en belasting van de server. In Figuur 13 staat de structuur van de gebruikte database in schematische vorm opgesteld. De verschillende tabellen worden verder besproken in sectie 2.5.2.
2.5.1 Experimenten cache in de databank De experimenten worden opgeslagen in bestandsformaat. Dankzij de mogelijks grote aantallen positioneringsobjecten, kunnen de experimenten snel tientallen kilobytes in beslag nemen. Dit is te groot voor in SQL databanken op te slaan. Ook zijn ze beter transporteerbaar in bestandsformaat, de protobuff-API van Google voorziet ook veel ondersteuning voor het inlezen en uitschrijven van bestanden. Toch heeft het bijhouden van de bestanden wel een groot nadeel. Om een lijst te kunnen weergeven van alle beschikbare experimenten (al dan niet gefilterd), zouden alle bestanden moeten worden ingelezen. Daarom wordt in de databank een samenvatting bewaard van elk experiment. Een experimentobject wordt omgezet in een instantie van CachedExperiment, waarvan de velden overeenkomen met de kolommen in de databasetabel proto_cache. Al deze velden maken het mogelijk om te filteren en geven ook informatie mee aan de gebruiker. Bijkomstig aan de velden wordt ook een bestandsnaam bewaard zodat het programma de volledige versie van het experiment kan terugvinden in zijn bestandsstructuur.
2.5.2 Applicatie parameters in de databank. De applicatie leest zo veel mogelijk functionele gegevens uit de databank. Op die manier kan eenvoudig een aanpassing worden gemaakt zonder programmacode te wijzigen. De gebruikers en beheerders van de applicatie hebben genoeg kennis over 33
databanken zodat ze zelf veranderingen kunnen doorvoeren, zonder dat er extra software moet worden gemaakt. Volgende tabellen bevinden zich in de databank (Figuur 13):
testbed dient voor het opslaan van ondersteunde testbedden. De applicatie moet naast een naam en beschrijving ook weten hoe groot het testbed is en waar het referentiepunt ligt.
fixed_node heeft een referentiesleutel naar de tabel ‘testbed’. Voor elk testbed zijn er meerdere records, die de vaste nodes voorstellen (1 op veel relatie). De informatie over de vaste nodes wordt weergegeven op de kaartfunctie van de applicatie.
bench_profile vertegenwoordigt de profielen voor de benchmarking.
In metric worden alle mogelijke metrieken beschreven, die met de tabel profile_metric worden gekoppeld aan elk profiel (veel op veel relatie). Elk profiel legt voor elke metriek een minimum en maximum waarde op.
Figuur 13: structuur van de databasetabellen.
34
2.6 Aandachtspunten Een goede applicatie vereist niet alleen het goed functioneren van alle onderdelen, maar is ook eenvoudig in gebruik. De gebruiker moet zelf zijn weg eenvoudig vinden en daarom moet de applicatie gebruiksvriendelijk worden ontworpen. Maar gebruiksvriendelijkheid houdt ook in dat de applicatie snel reageert. Een aantal punten om de applicatie beter te maken worden hieronder verklaard.
2.6.1 JSON data-omvang beperken Als de data van de experimenten wordt meegegeven in de HTML response naar de client (JavaScript), dan wordt er gebruik gemaakt van JSON. Dit wordt ondersteund door zowel JSF als JavaScript. Gewone Java objecten omzetten naar JSON blijkt echter niet zomaar een goede oplossing te zijn, volgende knelpunten kwamen bovendrijven:
De ruwe data in de back-end bevat veel meer informatie dan nodig is in de front-end.
Een wederkerend subobject met velden zorgde ervoor dat de sleutel van het veld altijd opnieuw vernoemd werd.
Een sleutel wordt altijd omringd door “aanhalingstekens”, daarboven worden de aanhalingstekens gecodeerd in “"e;”.
De combinatie van alle bovenstaande resulteerde in een gigantische overhead (tot 300 kB voor het weergeven van een enkel experiment). Volgende maatregelen werden genomen om deze overhead te beperken (tot 25 kB voor dezelfde data):
Er werden extra klassen gemaakt die voor elk gebruik in de applicatie enkel de benodigde data bevatten. De nieuwe klassen kunnen beschouwd worden als een gereduceerde versie van de originele.
Alle velden van een wederkerend subobject worden vervangen door een primitieve array (of tabel) van waarden. Per experiment wordt de sleutel van het veld dan slechts één keer vernoemd. Alle omslachtige “"es;” worden hier ook door vermeden. De waarden van het veld zijn meestal getallen en hebben geen aanhalingstekens nodig.
35
2.6.2 Weergave van grafieken Er werd veel aandacht besteed aan de manier waarop de data visueel wordt voorgesteld. Aan de hand van wat de gebruiker selecteert, moeten grafieken en kaarten worden gegenereerd. Dit gebeurt dynamisch in de front-end met data die wordt meegegeven uit de back-end. Het omzetten van data in grafieken zou in de front-end niet eenvoudig gaan met de klassieke HTML uit vorig decennium. Samen met de komst van HTML5 worden meer open standaarden gebruikt om media naar de gebruiker te brengen via de browser. Zo is SVG (Scalable Vector Graphics) een bestandsformaat voor vectorafbeeldingen, gebaseerd op XML. Met behulp van SVG kunnen vectorafbeeldingen worden ingebed in HTML5 terwijl ze dynamisch aanpasbaar blijven. Browser
Versie
Uitgebracht
Internet Explorer
9.0
03/2009
Firefox
4
03/2011
Chrome
7
10/2010
5.1
07/2011
Safari
Tabel 3: belangrijkste browsers en hun versie die SVG ondersteunt.
In Tabel 3 staan de belangrijkste desktopbrowsers en hun eerste versie die SVG ondersteunt [18]. Dit maakt SVG zeer geschikt voor deze toepassing, want de gebruiker zal met grote waarschijnlijkheid geen software moeten installeren om de applicatie te kunnen gebruiken.
Figuur 14: voorbeeldcode van een grafiek in SVG opgemaakt
Zoals in Figuur 14 te zien is, wordt de grafiek opgebouwd door afzonderlijke elementen. Het aanmaken van die elementen kan eenvoudiger worden met behulp van een JavaScript bibliotheek “D3.js”.
36
De JavaScript bibliotheek: D3.js De strategie achter deze bibliotheek is om data te “binden” [19] aan de DOM-objecten (Document Object Model). Deze bibliotheek belooft grote hoeveelheden data performant te behandelen en de moderne browsers te ondersteunen. Dit bespaart veel tijd in het testen en ontwikkelen van de software. De data voor de grafieken werden al voorbereid in de back-end zodat ze integraal kunnen gebruikt worden in de front-end. Deze data wordt doorgegeven aan een functie van de bibliotheek. Als voorbeeld wordt hier beschreven hoe de staafgrafiek uit Figuur 8 werd gegenereerd:
Per metriek wordt een grafiek gemaakt en voor die metriek wordt de data-array uit de globale array gehaald.
Samen met een nieuw DOM object wordt ook een JavaScript object aangemaakt die de grafiek voorstelt. Er kunnen verschillende parameters worden meegegeven, zoals de breedte en hoogte van de grafiek. De breedte is hier relatief zodat het scherm optimaal kan gevuld worden.
Het object dat de grafiek voorstelt wordt aangeroepen om nieuwe elementen aan toe te voegen. Per getal in de array wordt er een staaf toegevoegd in de staafgrafiek. Een staaf kan worden getekend als een rechthoek: een “rect”-element in SVG. De positie van de rechthoek is afhankelijk van het volgnummer van het getal (i). De afmetingen van de rechthoek zijn afhankelijk van de waarde van het getal. De functie ‘y’ in het codefragment is een voorbeeld van een hulpfunctie die D3.js aanbiedt. De functie neemt de waarde van het getal en beeldt hem lineair af tussen het bereik van de data.
37
3 Analyse van algoritmen In dit hoofdstuk worden enkele aspecten van benchmarking onderzocht. Benchmarking start bij het analyseren van de resultaten van de verschillende algoritmen. Om een goed zicht te krijgen op de resultaten wordt gebruik gemaakt van statistiek. Statistiek brengt het gedrag van het algoritme in een samenvatting die vervolgens kan worden geïnterpreteerd om de conclusie te vormen. Na de toelichting van de berekeningen wordt ook beschreven hoe de applicatie voor benchmarking kan gebruikt worden in sectie 3.3.
3.1 Gebruik van robuuste statistieken De gebruikelijke statistische schatters zijn heel gevoelig aan uitschieters. Er kunnen zich tijdens een experiment omstandigheden voordoen die verkeerde data leveren in een beperkte fase van het experiment. Dit vertekent de kenmerkende statistische gegevens, zoals het gemiddelde, misschien onterecht.
Tijdens de opstartfase van het experiment kan het zijn dat er nog niet voldoende data verzameld werd om correct te lokaliseren.
Als de lokalisatie gedeeltelijk gebeurt buiten het grid van nodes is het niet de oorzaak van het algoritme zelf als er slechte resultaten zijn.
Deze en andere ongelukkigheden brengen de experimenten slechts tijdelijk in de war en zijn niet representatief voor de werking van het algoritme. Om dit te beperken kunnen andere statistische schatters worden gebruikt of er kunnen uitschieters van de waarden worden gefilterd. Anderzijds stelt er zich de vraag of uitschieters misschien wel typerend kunnen zijn voor de algoritmen. Om het effect van de uitschieters te bekijken zijn een aantal reeksen met getallen geanalyseerd. De eerste reeks bevat 300 getallen genormeerd normaal verdeeld. In de andere reeksen zijn dezelfde waarden opgenomen, maar zijn enkele willekeurige getallen vervangen door manueel ingevoerde getallen die de uitschieters voorstellen. In Tabel 4 wordt voor elke reeks een distributiegrafiek weergegeven waarop de uitschieters duidelijk zichtbaar zijn. Merk op dat de meetresultaten van de algoritmen niet altijd in een normaal verdeeld zullen zijn. Wel zullen de uitschieters met grote waarschijnlijkheid altijd aan één kant van de verdeling liggen. Een uitschieter is meestal een minder gunstige waarde, want er zijn weinig gevallen waar een algoritme willekeurig veel beter presteert.
38
80
70
70
60
60
50
50
frequentie
frequentie
80
40 30
40 30
20
20
10
10
0
0 -4 -3,5 -3 -2,5 -2 -1,5 -1 -0,5 0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 interval
-4
-3
-2
-1
0
80
80
70
70
60
60
50
50
40 30
3 4 interval
5
6
7
8
9
10
5
6
7
8
9
10
5
6
7
8
9
10
40 30
20
20
10
10
0
0 -4
-3
-2
-1
0
1
2
3 4 interval
5
6
7
8
9
10
-4
-3
-2
-1
0
Reeks C
1
2
3 4 interval
Reeks D
80
80
70
70
60
60
50
50
frequentie
frequentie
2
Reeks B
frequentie
frequentie
Reeks A
1
40 30
40 30
20
20
10
10
0
0 -4
-3
-2
-1
0
1
2
3 4 interval
5
6
7
8
9
10
-4
-3
-2
-1
Reeks E
0
1
2
3 4 interval
Reeks F Tabel 4: distributie van de reeksen getallen.
REEKS gemiddelde mediaan getrimd gemiddelde standaard afwijking eerste kwartiel derde kwartiel interkwartiel afstand mediaan absolute deviatie scheefheid
A 0,00 -0,03 0,00 0,97 -0,66 0,68 1,34 0,03 -0,03
B 0,53 0,09 0,14 2,37 -0,56 0,87 1,42 0,09 3,10
C 0,71 0,20 0,44 2,26 -0,47 1,04 1,51 0,20 2,21
Tabel 5: Analyse van de getallen per reeks.
39
D 0,66 0,20 0,54 1,96 -0,47 1,04 1,51 0,20 1,46
E 0,69 0,24 0,65 1,74 -0,45 1,33 1,78 0,24 0,80
F 0,89 0,24 0,71 2,21 -0,45 1,33 1,78 0,24 1,44
Per reeks worden een aantal statistische gegevens berekend, ze staan uitgeschreven in Tabel 5. Volgende statistische gegevens worden besproken:
Het gemiddelde is zeer gevoelig aan elke kleine uitschieting van waarden. Reeks C en E leveren op een heel andere manier eenzelfde afwijking aan het gemiddelde. In reeks C zijn de uitschieters verspreid over een groot bereik, de uitschieters in reeks E bevinden zich zeer geconcentreerd in één intervalklasse. Het is dus zeer moeilijk om uit het gemiddelde alleen af te lezen waar de uitschieters zijn en hoeveel er zijn. Een klein aantal grote uitschieters heeft ongeveer hetzelfde effect als meerdere kleine uitschieters.
De mediaan is veel stabieler en verschuift minder snel dan het gemiddelde. Het zou een goede schatter kunnen zijn voor de metriek waarvan je de uitschieters wilt filteren. De mediaan krijgt vooral een verandering indien er een groot aantal uitschieters zijn, de waarde van de uitschieters speelt een kleine rol.
Het getrimd gemiddelde is hier getrimd op 10%. De laagste en hoogste 5% waarden worden weggelaten uit de reeks zodat nog 90% van de getallen overblijft. Er kan natuurlijk ook op een ander percentage worden geknipt, maar indien meer dan 5% van de getallen uitschieters zijn, kan men misschien concluderen dat uitschieters typerend zijn aan de resultaten.
De standaard afwijking verklapt snel dat er uitschieters of onstabiele gegevens zijn. De standaardafwijking maakt gebruik van de afstand tot het gemiddelde, omdat deze snel verschuift kunnen we misschien beter gebruik maken van een robuuste variant. De MAD of de mediane absolute deviatie [20] maakt gebruik van de afstand tot de mediaan welke stabieler is. Er kan ook gebruik gemaakt worden van de interkwartielafstand.
De interkwartielafstand; dit is de afstand tussen het eerste en het derde kwartiel, zodanig dat dit interval 50% van de binnenste gesorteerde getallen bevat. De uitschieters maken hierbij geen deel uit van de berekening. Maar doordat de getallen gesorteerd worden, ligt het de interkwartielafstand meer verschoven naar de hogere getallen hoe meer uitschieters er zijn. Men kan de interkwartielafstand (50%) vergelijken met de standaardafwijking (34%). Uit deze vergelijking kan men afleiden of er weinig grote uitschieters of veel kleine uitschieters zijn.
Als de gegevens veel uitschieters bevatten omwille van een tijdelijke storing die duidelijk zichtbaar is bij manuele inspectie, is het een goed idee om die uitschieters te verwijderen voordat de gegevens verder worden geanalyseerd. Onregelmatige uitschieters zijn wel degelijk kenmerkend aan het algoritme, dus door de vergelijking van de robuuste en niet-robuuste statistieken kan worden uitgemaakt hoeveel uitschieters er zijn en hoe groot ze zijn.
40
3.2 Scoreberekening Om een vergelijking te kunnen maken tussen experimenten, kunnen de statistische gegevens over hun metrieken worden vergeleken. Per metriek kan een verschil worden vastgelegd. Dit kan beschouwd worden als een betere prestatie voor de ene SUT (System Under Test). Alternatief aan de vergelijking van de metrieken zelf, kunnen ook scores worden toegekend aan de metrieken. Een relatieve score (tussen 0 en 100%) zegt meer dan de ruwe cijfers van de metriek in hun eigen eenheid. Bijkomstig kan voor elke metriek (en zijn score) een prioriteit worden ingesteld, sommige metrieken zijn in een gebruikscenario belangrijker dan andere metrieken. De score van één bepaalde metriek is afhankelijk van het gewenst bereik van de metriek. Het bereik wordt begrensd door een maximum en minimum waarde. De meest gunstige waarde van deze twee grenzen krijgt de maximumscore (100%), en de minst gunstige krijgt de minimumscore (0%). De andere waarden kunnen worden berekend met behulp van een afbeeldingsfunctie.
3.2.1 Afbeeldingsfunctie Om een metriek op een score af te beelden, wordt er gebruik gemaakt van een afbeeldingsfunctie (mappingfunctie). Als invoer gebruikt men de waarde van de metriek en als uitvoer een score tussen 0 en 100%. De eenvoudigste benadering levert een functie op uit meerdere delen: een lineair deel die tussen het gewenste bereik op een score afbeeldt, een deel onder het gewenst bereik die een nul-score levert en een deel boven het bereik die de maximum-score teruggeeft. De functie kan beschreven worden als: 𝑓(𝑥) = (𝑥 − 1)𝐻(𝑥 − 1) − (𝑥 − 2)𝐻(𝑥 − 2)
Waarbij de functie H(x) de Heaviside-functie voorstelt. Dit geeft een goede relatie van een metriek naar een score, maar het heeft nog een tekort: indien twee 41
algoritmen beiden buiten het ideale bereik vallen, dan is er geen vergelijking mogelijk, aangezien ze dezelfde score krijgen. Terwijl de ene nog altijd beter zou kunnen presteren dan de andere. Daarom kan een aangepaste sigmoid-functie een betere oplossing bieden, het middelste deel is bijna lineair, maar aan de grenzen van het bereik vindt er zich een meer geleidelijke overgang plaats. 𝑓(𝑥) =
1 1 + 𝑒 −𝑥
Een gewone sigmoid-functie is niet zo praktisch. Door de afhankelijke variabele te schalen en verschuiven is deze bruikbaar om het bereik van de metriek als invoer te gebruiken. 𝑓(𝑥) =
1 1 + 𝑒 5(−0.5+𝑥)
De meest gebruikte metrieken moeten een betere score krijgen bij een kleinere waarde, daarom schalen we de afhankelijk variabele x negatief indien het nodig is. Met een schaling van factor 5 en een verschuiving x-0.5 krijgen we een functie die 92% van zijn verloop kent binnen het gewenste bereik van de metriek. Buiten het gewenst bereik kunnen metrieken alsnog worden vergeleken met elkaar, maar zal geen grote invloed geven op de score. 42
Om de metriek rechtstreeks als invoer te gebruiken van de functie kunnen we de afhankelijke veranderlijke x vervangen door: x − offset bereik In volgend voorbeeld vallen de ideale waarden van de metriek tussen 5 en 15. Enkele waarden van de functie worden uitgeschreven in Tabel 6. 1
𝑓(𝑥) = 1+𝑒
(−5+𝑥) 5(−0.5+ 10 )
(a)
Invoer (waarde v.d. metriek)
Uitvoer (score in %)
0
99,33%
5
92.41%
10
50%
15
7.59%
20
0.67% Tabel 6: uitvoer van de functie (a) bij enkele invoerwaarden.
43
3.3 Applicatie in gebruik: beoordeling van algoritmen. Het gedrag van de resultaten van de algoritmen kan uit verschillende hoeken worden bekeken. De onderdelen van de applicatie kunnen elk hun deel van problemen of uitzonderlijke gebeurtenissen aan het licht brengen.
3.3.1 Uitzonderingen op basis van tijd
Figuur 15: metriek in functie van de tijd. De eerste meting is een uitschieter.
Deze gedragspatronen kunnen het best bekeken worden door de metingen op een grafiek te plaatsen in functie van de tijd, zoals weergegeven in Figuur 15; verschillende experimenten kunnen tegelijk worden weergegeven. Er kan rekening worden gehouden met volgende punten:
De opstartfase van het algoritme kan onregelmatige data bevatten. Men kan op de grafiek duidelijk een paar “slechte” waarden aflezen doordat ze gesorteerd zijn in de tijd.
Ondanks dat twee experimenten een gelijkaardig gemiddelde kunnen hebben voor een bepaalde metriek, kunnen de gegevens toch op een heel andere manier tot dat gemiddelde leiden. Uit de stabiliteit van de grafiek is af te lezen hoeveel variantie op de meetwaarden zit. De stabiliteit kan veranderen in het verloop van het experiment, gelijkaardig aan de opstartfase. De statistische analyse kan ook de variantie berekenen, maar het verloop in opeenvolgende punten bekijken kan een meerwaarde hebben.
Door de grafiek te bekijken in een groot tijdsverloop worden de punten dichter bij elkaar getekend. Gelijkaardig aan een schuivend gemiddelde worden tijdelijke gedragspatronen zichtbaar. Ook kunnen patronen voorkomen in de grootteorde van de tijdsduur van het hele experiment. Zo kan het energieverbruik blijven stijgen hoe langer het experiment duurt, dat kan het gevolg zijn van programmeerfouten.
44
Het naast elkaar zetten van verschillende metrieken kan relaties tussen metrieken verklaren. Een vertraging in de berekening (latency) gaat soms gepaard met slechtere accuraatheid. Is de vertraging verantwoordelijk voor een slechte berekening? Of is de slechte berekening verantwoordelijk voor de vertraging? De uitlopers van de vertraging kunnen ook de oorzaak zijn van hoger energieverbruik.
Indien de lokalisatie slechter presteert als het lokaliseerbare object sneller beweegt, dan heeft het algoritme een slechte mobiliteit. De snelheid van het object kan tijdens het experiment veranderen, dus om het verband te zien moeten de gegevens in functie van de tijd worden gelezen.
3.3.2 Uitzondering op basis van plaats
Figuur 16: weergave op de kaart van verschillende positioneringen. De zwarte lijnen zijn verbindingen tussen de echte en de geschatte locatie (respectievelijk halve en volle bollen).
Op de kaart kunnen geografische onregelmatigheden worden verklaard. De problemen kunnen verschillend zijn van omgeving tot omgeving. Kaarten kunnen ook niet alle mogelijke factoren weergeven, misschien is er niet voldoende informatie beschikbaar over mogelijk storende elementen. Hier volgt een opsomming van enkele elementen die wel eenvoudig zichtbaar zijn:
De vorm van het testbed en vooral de muren zijn een storende factor voor de radio signalen die het systeem gebruikt. Muren kunnen signalen afzwakken, terugkaatsen of afbuigen naargelang de vorm en constructie; het is dus heel omgevingsafhankelijk. Op de kaart kan er bijvoorbeeld worden afgelezen dat bepaalde kamers in het testbed veel beter lokaliseerbaar zijn dan andere. 45
De vorm van het grid zijn de nodes die op een bepaalde manier zijn geplaatst in het testbed. Het is soms onmogelijk en ook niet noodzakelijk om de nodes met een gelijkmatigheid over het testbed te verdelen. De keuze van de plaatsing kan verschillende effecten hebben: o Op plaatsen met een hogere dichtheid van sensoren, kan beter worden gepositioneerd. Kleinere ruimtes zullen ook een hogere dichtheid nodig hebben. o De structuur van de plaatsing van de nodes kan op sommige plaatsen een slechtere of betere plaatsbepaling geven. Een honinggraatstructuur biedt de beste overlappende dekking voor radio signalen [21]. Als bijvoorbeeld op de kaart de horizontale afstand tussen de nodes veel korter is dan de verticale afstand, dan zal de accuraatheid in de respectievelijke richtingen van de positionering beter en slechter zijn. In Figuur 16 staan de vaste nodes in het midden van de kaart verder uit elkaar. Een verkeerde positionering resulteert meteen in een grotere foutafstand in het gebied van mindere dekking.
Figuur 17: alle werkelijke punten verwijzen naar één enkel geschatte locatie, hier gaat iets fout.
Slecht functionerende nodes kunnen onverwacht opduiken op de kaart, terwijl ze onzichtbaar blijven in de statistische resultaten. In Figuur 17 lijkt iets fout te zijn met één zekere node, die alle positiebepalingen naar zich toe trekt.
Terwijl de gemiddelde fout hoog blijft kan het geschatte pad (met verplaatsende nodes) toch parallel lopen met het werkelijk afgelegde pad. De verschuiving van gegevens kan worden gecompenseerd met een correctie. 46
Om de herhaalbaarheid van een algoritme te controleren kunnen verschillende positioneringen van één niet-mobiel object worden gemaakt en worden bekeken op dezelfde weergave. Indien de geschatte locaties geen verband kennen met elkaar is het algoritme slecht herhaalbaar.
3.3.3 Uitzonderingen af te leiden uit statistiek De resultaten van een algoritme bevatten vaak verschillende uitschieters. Als de oorzaak van deze uitschieters kan gevonden worden, kan het systeem worden verbeterd.
Uitschieters in puntaccuraatheid zijn een complexe som van alle parameters die meespelen. Deze kunnen niet eenvoudig afgeleid worden uit de statistische analyse.
Indien er zich uitschieters bevinden in de vertraging (latency), kan een verband worden gezocht met de uitschieters in de accuraatheid. De oorzaak die tot gevolg leidt kan in beide richtingen worden gecontroleerd.
Het energieverbruik van nodes of systemen kunnen op hun beurt rechtstreeks of onrechtstreeks afhangen van de accuraatheid en vertraging. Een langdurige berekening van het algoritme of het krachtig uitsturen van een radiosignaal zijn voorbeelden voor een hoger energieverbruik in de nodes.
47
3.4 Applicatie in gebruik: Hybride RSSI algoritme. In deze sectie worden de resultaten van een algoritme besproken [22]. Het algoritme is een hybride oplossing en combineert twee technieken.
De eerste techniek maakt gebruik van gewogen RSSI (zie sectie 1.4.1) waarden. De gewichten worden bepaald uit de afstanden tussen de vaste nodes. Zoals te zien is in Figuur 18.
Figuur 18: gewichten tussen vaste nodes De tweede techniek is nabijheid. Hier worden gebruikt in de berekening. [22] worden de RSSI waarden genegeerd. Er wordt enkel vanuit gegaan dat een node een bepaald zendbereik heeft (van bijvoorbeeld 10 meter). Indien het signaal wordt ontvangen door een vaste node, dan is de mobiele node nabij. Er kunnen meerdere vaste nodes zijn die het signaal ontvangen, dan wordt meetkundig het zwaartepunt van alle ontvangende nodes berekend.
Figuur 19: het testbed met vaste en mobiele nodes. [22]
Een experiment wordt opgesteld met dit hybride algoritme. Op voorhand werden de posities van de mobiele nodes vastgelegd. Enkele mobiele nodes bevinden zich in een kamer (waar vaste nodes dichtbij in het bereik zijn), en andere bevinden zich in de gang (waar geen vaste nodes zijn). De gele bollen in Figuur 19 zijn de mobiele nodes en de gebruikte vaste nodes zijn met een blauwe punt aangeduid.
48
Het experiment werd vier keer uitgevoerd met elke keer een ander zendvermogen, in Tabel 7 staan de niveaus opgesomd. In elk experiment worden de mobiele nodes achtereenvolgens verschillende keren gelokaliseerd. Tx power level
Output power [dBm]
3
-25
7
-15
19
-5
31
0
Tabel 7: zendvermogen voor de vier experimenten [23]
Zoals in [22] onderzocht, is hier in Figuur 20 een duidelijk verband tussen het gebruikte zendvermogen en de positioneringsfout. Door de onderzoeksmethode uit secties 3.1 en 3.3 kan de data verder worden geanalyseerd. Figuren Figuur 24-Figuur 26 zijn schermopnames van de benchmarkingapplicatie. Figuren Figuur 21-Figuur 23 zijn grafieken die de distributie van de getallen uitzetten in intervalklassen. In Tabel 8 zijn de statistische gegevens van de positioneringsfout in tabel geplaatst.
Figuur 20: gemiddelde positioneringsfout per uitgevoerd uitzendvermogen.
REEKS gemiddelde mediaan getrimd gemiddelde standaard afwijking eerste kwartiel derde kwartiel interkwartiel afstand mediaan absolute deviatie scheefheid
TX3 4,63 4,39 4,57 2,20 3,23 6,19 2,96 2,20 0,20
TX7 7,08 6,81 6,90 3,15 4,78 8,54 3,75 3,36 0,89
TX19 7,98 7,55 7,85 3,94 5,15 10,43 5,28 5,86 0,44
Tabel 8: statistische gegevens van de positioneringsfouten.
49
TX31 8,31 8,63 8,16 4,04 5,02 11,16 6,14 3,13 0,42
250
frequentie
200
150
TX31 TX3 TX7
100
TX19 TX31 50
0 0
1
2
3
4 5 intervalklasse
6
7
8
9
Figuur 21: verdeling van de positioneringsfout (in meter) van de vier experimenten. 140
120
frequentie
100
80
TX31
TX3 TX7
60
TX19 TX31 40
20
0 0
1
2
3
4
5
6
7
8
9
10
11
12 13 14 intervalklasse
15
16
17
18
19
20
21
22
23
24
stop
Figuur 22: verdeling van de positioneringsfout (in meter) van de vier experimenten met kleinere intervalklassen. 160 140
frequentie
120 100
TX3
80
TX7
60
TX19
40
TX31
20 0
0
50
100
150 intervalklasse
200
250
Figuur 23: verdeling van de vertraging (in milliseconden) van de vier experimenten.
50
300
Figuur 24: lokalisatiefout in de kamers dicht bij de nodes
Figuur 25: lokalisatiefout in de hall ver van de nodes
Figuur 26: lokalisatiefout in functie van de tijd
51
De volgende opmerkingen kunnen gemaakt worden:
In Figuur 21 staan de waarden van de positioneringsfout van de vier experimenten, verdeeld in 10 intervalklassen, uitgezet. Deze verdelingen lijken op een gaussverdeling. Bij de experimenten met hoger uitzendvermogen is er een scheefheid te bemerken, dit is de oorzaak van de hogere gemiddelde waarde van de metriek bij hoger uitzendvermogen. Als de verdeling wordt uitgezet in kleinere intervalklassen dan krijgt men in Figuur 22 een heel ander resultaat te zien. Er lijkt een sinusfunctie door de verdeling heen te gaan. Dit effect kan worden verkregen door de beperkte mogelijkheid aan foutafstanden, aangezien de fout zich enkel kan bevinden tussen de vooraf gekende punten. Een andere verklaring is dat de foutafstanden in hun eindpunten een cirkel omschrijven met als middelpunt de mobiele node, zoals te zien in Figuur 25. Omdat die foutafstanden dan allemaal ongeveer gelijk zijn (en binnen dezelfde klasse vallen) veroorzaakt dit een piek op die waarde.
Op ruimtelijk vlak is te zien dat de locatiebepalingen nauwkeuriger zijn op plaatsen waar er een hogere dichtheid is aan vaste nodes. In Figuur 25 worden punten gelokaliseerd in de gang, waar geen vaste nodes hangen. De lijnen op de figuur duiden de foutafstand aan. Die lijnen zijn beduidend langer dan de lokalisatie in Figuur 24, in een kamer met meerdere vaste nodes.
Op Figuur 26 staat de metriek ‘error 2D’ uitgetekend in functie van de tijd. Omdat een heel groot tijdsbereik is genomen staan de afzonderlijke waarden dicht op elkaar, en worden patronen zichtbaar. Er zijn 10 punten die na elkaar worden gelokaliseerd en bij elk punt kenmerkt een eigen patroon. De patronen lijken periodiek te zijn.
Op de verdelingsfuncties op Figuur 21 en Figuur 22 is te zien dat er op de experimenten met een hoger zendvermogen in kleine mate uitschieters zijn. Deze hogere waardes resulteren in een grotere standaardafwijking en interkwartielafstand, te zien in Tabel 8. De waarden zijn niet extreem en daarom blijft het gemiddelde (geen robuuste schatter) dicht bij de mediaan (wel een robuuste schatter).
52
53
4 Besluit Indoor positionering is een belangrijk onderwerp voor onderzoek. Nieuwe intelligente applicaties in allerlei sectoren kunnen gebruik maken van de positionering. Om een goed werkend systeem te vinden moeten verschillende algoritmen en technieken op een realistische manier kunnen worden vergeleken, systemen die in echte situaties worden gebruikt, worden blootgesteld aan omgevingsfactoren. Er werd een benchmarking methodologie opgesteld om de algoritmen op een gelijke manier te analyseren. Metrieken worden gebruikt om de kenmerken van het algoritme voor te stellen. Voorbeelden van metrieken zijn: puntaccuraatheid, ruimteaccuraatheid, vertraging, energieverbruik en opstartkosten. Alle metrieken samengenomen kunnen een globale conclusie leveren, daarom worden de metrieken omgezet in scores (met behulp van een sigmoid-afbeeldingsfunctie). Om de ontwikkeling van de algoritmes te verbeteren kunnen alle metrieken afzonderlijk worden geanalyseerd. Zowel op basis van tijd als ruimte kunnen er zich onregelmatigheden tonen (al dan niet visueel). De onregelmatigheden kunnen inzichten verwerven om het algoritme of de infrastructuur te verbeteren. Onregelmatigheden kunnen ook toevallig zijn, zonder betekenis. Daarom werden robuuste statistieken vergeleken met de traditionele schatters. Het is echter belangrijk om beiden te bekijken, zodat kan worden achterhaald in welke mate de onregelmatigheden optreden. Beide de vergelijking en analyse van algoritmen werden opgenomen als doel van een grafische tool. De tool werd ontwikkeld als een web applicatie met het oog op eenvoudig gebruik. De applicatie geeft de mogelijkheid om experimenten van een testbed, die omvat zijn in Protocol Buffers (van Google), in te laden. De experimenten kunnen worden beheerd in een database en met een gefilterde selectie terug worden opgeroepen. De geselecteerde experimenten kunnen worden geanalyseerd: de metrieken worden uitgezet in de tijd of in de ruimte. Indien er meerdere experimenten geselecteerd zijn worden de metrieken naast elkaar geplaatst in een grafiek. De visuele uitvoer van de metrieken gebeurt met behulp van JavaScript bibliotheken en stelt een afbeelding beschikbaar in SVG. Op die manier is de applicatie bruikbaar op alle moderne toestellen met een internetbrowser. De afbeeldingen blijven dynamisch en zijn interactief met de acties van de gebruiker. Het laatste deel van de applicatie maakt een eindscore op van de algoritmen op basis van een profiel. Het profiel is een verzameling van vereiste kenmerken van het algoritme. Een profiel vertegenwoordigt een gebruiksscenario die eisen stelt aan de metrieken van de algoritmen. Volgens die eisen worden de metrieken omgezet in een
54
score. Alle scores krijgen een gewicht en worden opgeteld om de totale score te berekenen. Tijdens het gebruik van de applicatie kwamen er nog nieuwe mogelijke aspecten van de analyse van algoritmen naar boven. Het werd ook duidelijk welke extra functies nog een meerwaarde kunnen bieden. De applicatie is klaar voor dagelijks gebruik, maar kan nog eenvoudig worden uitgebreid.
55
5 Bibliografie [1]
„Al meer dan 1 miljoen smartphones verkocht in 2012,” De Standaard, 12 september 2012.
[2]
D. Davis, „Mobile Statistics - More smartphone owners rely on location-based services, but fewer check in,” 12 september 2013. [Online]. Available: http://www.internetretailer.com/2013/09/12/more-smartphone-owners-relylocation-based-services. [Geopend december 2013].
[3]
T. Van Haute en andere, „EVARILOS Delivarble 2.1 Initial version of the EVARILOS benchmarking handbook,” 2013.
[4]
Gramin Ltd., „Gramin | What is GPS?,” [Online]. http://www8.garmin.com/aboutGPS/. [Geopend januari 2013].
[5]
G. Mao en andere, „Wireless sensor network localization techniques,” Computer Networks, nr. 51, p. 2529–2553, 2007.
[6]
T. Van Haute, E. De Poorter, J. Rossey, I. Moerman en andere, „The EVARILOS Benchmarking Handbook: Evaluation of RF-based Indoor Localization Solutions,” Dublin, 2013.
[7]
„iBeacon Wikipedia,” 12 januari 2014. [Online]. http://en.wikipedia.org/wiki/IBeacon. [Geopend januari 2014].
[8]
F. Vanheel, Ontwerp van lokalisatie-algoritmen voor draadloze sensornetwerken, Gent, 2013.
[9]
P. Bahl en V. Padmanabhan, „RADAR: An In–building RF–based User Location,” In Proceedings of the IEEE INFOCOM, volume 2, pp. 775-784, Maart 2000.
[10]
M. Azizayan, I. Constandache en R. R. Choudhury, „SurroundSense: Mobile Phone Localization via Ambience Fingerprinting.,” in MobiCom, Bejing, China, 2009.
[11]
D. Munoz, F. Bouchereau, C. Vargas en R. Enriquez, Position Location Techniques and Applications, Burlington, MA: Academic Press, 2009.
[12]
Y. M. Kwon, K. Mechitoch, S. Sundresh, W. Kim en A. G., „Resilient Localization for Sensor Networks in Outdoor Environments,” Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS’05), OH, USA, pp. 643652, 2005.
[13]
F. Vanheel, J. Verhaevert, E. Laermans, I. Moerman en P. Demeester, „A Linear Regression Based Cost Function for WSN Localization,” SOFTCOM, Split, 2011.
[14]
N. Gordon, D. Salmon en A. Smith, „Novel Approach to Nonlinear/non-Gaussian Bayesian State Estimation,” in IEE proceedings-F, Vol. 140, No. 2, 1993. 56
Available:
Available:
[15]
Google, „Protocol Buffers - Google Developers,” 2 april 2012. [Online]. Available: https://developers.google.com/protocol-buffers/. [Geopend september 2013].
[16]
„Browser Support | jQuery,” The jQuery Foundation, [Online]. Available: http://jquery.com/browser-support/. [Geopend januari 2014].
[17]
JScripters.com, „JQuery: advantages and disadvantages,” [Online]. Available: http://www.jscripters.com/jquery-disadvantages-and-advantages/. [Geopend januari 2014].
[18]
„Compatibility tables for support of HTML5, CSS3, SVG and more in desktop and mobile browsers.,” [Online]. Available: http://caniuse.com/#feat=svg-html5. [Geopend december 2013].
[19]
M. Bostock, „D3.js - Data-Driven Documents,” [Online]. http://d3js.org/#introduction. [Geopend september 2013].
[20]
P. J. Rousseeuw, „Least Median of Squares Regression,” Journal of the American Statistical Association, pp. 871-880, 1984.
[21]
H. Z. Hou en J. C., „Maintaining Sensing Coverage and Connectivity in Large Sensor Networks,” in Ad Hoc & Sensor Wireless Networks, Old City Publishing, 2005, p. 89–124.
[22]
T. Van Haute en andere, „EVARILOS Deliverable 2.2 Report on Experiments Without Interference,” 2013.
[23]
Moteiv Corporation, „Tmote Sky: Datasheet,” 2006.
[24]
M. Keshtgary, M. Fasihy and Z. Ronaghi, Performance Evaluation of Hopbased Range-free Localization Methods in Wireless Sensor Networks, 2011.
57
Available:
6 Bijlagen 6.1 Klassendiagram
Figuur 27: klassendiagram: JSF Beans
58
Figuur 28: klassendiagram: data-klassen
59
Figuur 29: klassendiagram: dataklassen voor de front-end
Figuur 30: klassendiagram: hulpklassen
60
Figuur 31: klassendiagram: metrieken en profielen
Figuur 32: klassendiagram: testbedden en nodes.
61
