Ontwikkeling van een indoorlokalisatiesysteem op basis van het Viterbi-algoritme

Ontwikkeling van een indoorlokalisatiesysteem op basis van het Viterbi-algoritme Jens Trogh

Promotoren: prof. dr. ir. Wout Joseph, prof. dr. ir. Luc Martens Begeleider: dr. ir. David Plets Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: elektrotechniek

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2013-2014

Ontwikkeling van een indoorlokalisatiesysteem op basis van het Viterbi-algoritme Jens Trogh

Promotoren: prof. dr. ir. Wout Joseph, prof. dr. ir. Luc Martens Begeleider: dr. ir. David Plets Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: elektrotechniek

Vakgroep Informatietechnologie Voorzitter: prof. dr. ir. Daniël De Zutter Faculteit Ingenieurswetenschappen en Architectuur Academiejaar 2013-2014

Voorwoord Het kiezen van een masterproef is niet vanzelfsprekend, mijn interesse in draadloze telecommunicatie en nieuwe technologieën in het algemeen hebben me uiteindelijk naar dit onderwerp geleid. Het was een interessant en uitdagend project, dat mij altijd heeft kunnen motiveren. Ik had graag nog een kort dankwoord gehouden voor alle mensen die me hebben geholpen bij het tot stand komen van deze thesis. Vooreerst mijn begeleider David Plets, die me altijd van snelle feedback en nieuwe invalshoeken kon voorzien, Bart Jooris en Stefan Bouckaert voor de hulp met het testbed en de mobiele node, Kris Vanhecke voor het opzetten van de visualisatietool en mijn promotoren Wout Joseph en Luc Martens voor het mogelijk maken van deze masterproef. Als laatste moet ik natuurlijk ook mijn ouders, familie en vrienden bedanken, voor hun steun tijdens deze thesis en mijn studies in het algemeen.

Jens Trogh, juni 2014

Toelating tot bruikleen De auteur geeft de toelating deze masterproef voor consultatie beschikbaar te stellen en delen van de masterproef te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze masterproef.

Jens Trogh, juni 2014

Ontwikkeling van een indoorlokalisatiesysteem op basis van het Viterbi-algoritme door Jens TROGH Masterproef ingediend tot het behalen van de academische graad van Master of Science in de ingenieurswetenschappen: elektrotechniek Academiejaar 2013-2014 Promotoren: Prof. Dr. Ir. Wout Joseph, Prof. Dr. Ir. Luc Martens Begeleider: Dr. Ir. David Plets Faculteit Ingenieurswetenschappen en Architectuur Universiteit Gent Vakgroep Informatietechnologie Voorzitter: Prof. Dr. Ir. Daniël De Zutter

Samenvatting In deze thesis wordt een indoorlokalisatiesysteem ontwikkeld dat gebaseerd is op het Viterbialgoritme, in plaats van enkel de meest waarschijnlijke huidige positie te voorspellen, wordt het meest waarschijnlijke traject geconstrueerd. Op deze manier wordt bij iedere voorspelling het verleden van een traject in rekening gebracht.

Trefwoorden Indoorlokalisatiesysteem, Viterbi-algoritme, Padverliespredictiealgoritme, RSSI Fingerprinting, Wireless Sensor Network, WiFi

Development of an indoor localization system based on the Viterbi-algorithm Jens Trogh Supervisor(s): Wout Joseph, Luc Martens, David Plets Abstract— In this work an indoor localization system based on the Viterbi-algorithm is developed. Instead of determining just the most likely current position, the most likely sequence of locations is determined. The developed algorithm is tested by simulation and implemented on a wireless testbed for real-life testing. Next the algorithm is adjusted to work in realtime and finally a sensitivity analysis is conducted to examine the influence of all parameters. Keywords—Indoor Localization, Viterbi-algorithm, Path loss prediction algorithm, Wireless Sensor Network, RSSI fingerprinting

I. I NTRODUCTION N door localization systems have applications in many domains, think of the healthcare sector, military sector, industrial sector,. . . Examples of these applications are: tracing of elderly, navigation through a building, equipment tracking, museum guidance,. . . To perform the localization of an object, a tracking device that broadcasts beacons is often used. The location is estimated based on the comparison of the measured signal strength with reference values. Due to the complexity of many indoor environments there can be a large variability on these measured signal strengths which often results in an insufficient accuracy of the localization algorithm. By using new and advanced techniques this accuracy can be improved.

I

II. PATH LOSS MODELS A. RSSI To determine the path loss, the Received Signal Strength Indicator (RSSI) is used, this value gives an indication of the received power level in dB. We will use these RSSI values, averaged over a certain time-interval, to calculate the path losses from this certain moment. These measurements will be used as input for the localization algorithm, where they are compared with the reference values from the fingerprint database, to find the most likely next position. This fingerprint database is constructed with four different path loss models. B. Path loss models A free-space, one-slope, two-slope and the WiCa Heuristic Indoor Propagation Prediction Tool (WHIPP) [2] will be used for prediction of the path losses. Because of the difference between the measured RSSI values and the predicted path losses, all four models are calibrated once. By broadcasting packets on five different places in the testbed the ideal shift is determined (this testbed is further explained in Section IV). C. Offline phase In the offline phase all reference path losses for all gridpoints are calculated and stored in the fingerprint database. These grid-

points are the possible locations on the floor plan where the object, that is being traced, can be located. III. L OCALIZATION ALGORITHM A. Simple algorithm A simple localization system is used to compare and estimate the improvement of the developed localization algorithm. This standard localization algorithm makes no use of the history of the current trajectory or the tracings object’s environment. Only the Mean Square Error (MSE) is used to determine the most likely current position (gridpoint), this MSE is calculated between the measured path losses and the reference path losses of a gridpoint from the fingerprint database. MSE =

N 1X 2 (P Lavg,n − P Lref,n ) n n=1

(1)

Where PLavg,n is the average measured path loss from a node n and PLref,n is the reference path loss from the fingerprint database for the same node n. B. Developed algorithm As already mentioned, the developed localization algorithm is based on the Viterbi-algorithm [3]. This comes down to determining the most likely sequence of positions instead of only the most likely current position. This is done by keeping the measurements of the past and include them in the calculation of the new most likely location. With each location update (by processing the measurements of the last moment), the possible trajectories and their associated total costs are updated in the memory of the location algorithm. The last position of the trajectory with the lowest total cost in that moment is taken as most likely current position. Besides including the past of a trajectory, it is ensured that the reconstructed trajectories are physically possible: no wallcrossing, using the doors to leave a room and an adjustable maximum speed. In this way no impossible jumps are made along a traveled path. IV. T ESTBED IMPLEMENTATION A. w-iLab.t The w-iLab.t is an experimental, generic, heterogeneous wireless testbed from iMinds, located in Zuiderpoort (Ghent), it is used for developing and testing wireless applications [1]. All (fixed) wireless nodes are connected to a wired backbone network for management, logging and processing of the measured data during an experiment.

B. Mobile node Two kinds of mobile nodes are used to conduct the experiments, both broadcast beacons with a send rate of 10 packets per second but use a different wireless technology: ZigBee and WiFi. The mobile nodes have an antenna with a gain of 5 dBi. These broadcasted packets are received by the fixed nodes from the testbed and are, after preprocessing, used as input for the localization algorithm. C. Real-time visualization For visualizing the trajectory in real-time, there are two MySQL databases used, one for logging and reading the measured RSSI values from the testbed (this database is always used) and another database for storing the current most likely trajectory. The WHIPP web service gets regular updates from the second database to plot the trajectory in the visualization tool. V. R ESULTS A. Accuracy and standard deviation

The column Viterbi Huidig is the trajectory consisting of the locations, that where most likely on a current moment along the walked path, whereas Viterbi is the final most likely trajectory (all measurements considered). Both score better than the simple algorithm, the accuracy has improved by 0.94 m and the standard deviation even by 1.86 m (averaged over ZigBee and WiFi). This can be explained by considering all previous locations in combination with the maximum speed parameter which does not allow huge (irregular) jumps along a path. B. Visualization Besides the absolute performance measures, the reconstructed trajectories can also be plotted on the floor plan to have a visual interpretation of the performance differences between the simple and the developed localization algorithm. In Figures 1 - 2, the visualization of the reconstructed trajectory with the simple and developed algorithm is shown (made with the mobile ZigBee node). The red, green and black trajectory are the ground truth, simple and developed algorithm respectively. The starting point is indicated with a circle.

To validate the developed algorithm, two performance measures are used: the accuracy and the standard deviation of this accuracy. The accuracy is the average error between the predicted trajectory and the ground truth. The ground truth is the trajectory with the exact locations of the object that is being traced. The accuracy and standard deviation are calculated for each location update and averaged over all locations from the considered trajectory. T q 1X 2 2 (xgt,t − xpred,t ) + (ygt,t − ypred,t ) T t=1 (2)

erroravg =

v u T u1 X 2 σ=t (errort − erroravg ) T t=1

(3)

Where erroravg is the average accuracy along a trajectory, T is total number of location updates (time steps) from an experiment, (xgt,t , ygt,t ) and (xpred,t , ypred,t ) are the coordinates from the ground truth and the predicted location at time step t, σ is the standard deviation and errort is the accuracy at time step t. In total nine test trajectories are used, taken at normal speed and with an average length of 87 m. The averaged results over all locations from all test trajectories for ZigBee and WiFi are summarized in Table I (whilst using the WHIPP path loss model, which gave best results). TABLE I ACCURACY (A) AND S TANDARD DEVIATION (S) Algorithm →

Simple

Viterbi Huidig

Fig. 1. Visualization with the simple algorithm

Viterbi

Mobile node ↓

A [m]

S [m]

A [m]

S [m]

A [m]

S [m]

ZigBee

2.94

3.32

2.83

1.94

2.26

1.44

WiFi

3.89

3.45

3.29

2.23

2.7

1.62

Fig. 2. Visualization with the developed algorithm

It can immediately be seen that the trajectory of the simple algorithm is not physically possible, many walls are crossed and irregular jumps are present (which will lead to a high standard deviation on the accuracy), whereas the trajectory of the developed algorithm is a regular one. Towards the end, the reconstructed path finds itself in the wrong room but the average error remains under 3 m. The exact accuracy and standard deviation can be found in Table II. It is confirmed that the simple al-

TABLE III G LOBAL OPTIMUM

gorithm has indeed a much higher standard deviation: 4.82 m compared to 1.54 m. Algorithm →

TABLE II ACCURACY (A) AND S TANDARD DEVIATION (S) FOR F IGURES 1 - 2

Path loss model ↓ WHIPP

Algorithm →

Simple

Testpath number ↓ 1

Viterbi

A [m]

S [m]

A [m]

S [m]

3.61

4.82

2.77

1.54

free-space

C. Sensitivity analysis In this analysis the influence of noise (variations on the measurements, for example caused by multipath fading), number of fixed nodes, memory usage, execution time, sample rate, walking speed, radiation power, different cost functions and a more accurate modeling of the floor plan are tested. The accuracy and standard deviation of the localization algorithm were tested whilst increasing the variations on the measurements by simulation (parameter stdDev [dB]), there was averaged over the same nine test trajectories, each five times simulated (see Figure 3). The performance of the simple algorithm was degrading at a faster rate than the developed algorithm, which was more robust to noise. Simple Viterbi Huidig Viterbi

12

Viterbi Huidig

Viterbi

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

ZigBee

2.96

3.63

2.58

1.7

2.18

1.31

WiFi

3.38

3.13

2.45

1.69

2.2

1.46

ZigBee

3.45

3.4

3.04

1.87

2.61

1.5

WiFi

3.59

2.12

3.46

2.03

3.35

1.96

the standard deviation of the accuracy improved a lot. By using the advanced path loss model (WHIPP) there is always progress compared to the results with the free-space path loss model, only with the simple algorithm it has to give in a little on the standard deviation. VI. C ONCLUSION We can conclude that the usage of the past and environment of a trajectory can improve the accuracy and standard deviation of a (random) indoor localization system. Visual inspection of the reconstructed trajectories showed realistic paths. In the sensitivity analysis it was shown that the robustness against measurement variations improved and that decent results with only few fixed nodes could be obtained, which was not the case for the simple algorithm. Overall the developed localization algorithm kept performing better than the simple algorithm, with accuracies around 2.2 m. R EFERENCES

10

accuracy [m]

Simple

Mobile node ↓

[1] Stefan Bouckaert, Wim Vandenberghe, Bart Jooris, Ingrid Moerman, Piet Demeester, The w-iLab. t testbed, Testbeds and Research Infrastructures. Development of Networks and Communities, pp. 145-154, Stockholm, Springer, 2011. [2] David Plets, Wout Joseph, Kris Vanhecke, Emmeric Tanghe, Luc Martens, Coverage prediction and optimization algorithms for indoor environments, EURASIP Journal on Wireless Communications and Networking, pp. 1-23, Springer, 2012. [3] Andrew J. Viterbi, Error bounds for convolutional codes and an asymptotically optimum decoding algorithm, Information Theory, IEEE Transactions on, vol. 13, pp. 260-269, IEEE, 1967.

8

6

4

2

0 0

2

4

6

8

10

12

14

16

18

20

stdDev [dB] Fig. 3. Influence of noise (simulation)

It was also shown that with less fixed nodes, still a good result could be obtained with the developed localization algorithm. For the memory usage: there is no need to retain all possible trajectories during the localization, because the performance saturated upwards retaining the 100 best trajectories at each location update. The average execution time for a location update was 345.02 µs, which makes it suited to work in real-time. A sample rate between 1 s-1 and 2.5 s-1 , which means a new input every 0.4 s - 1 s, gave the best results. The influence of walking speed and radiation power was negligible. A more detailed floor plan, which included the state of a door (open or closed) resulted in a small improvement. The ultimate performance with these ideal parameters for both the free-space and the WHIPP path loss model can be found in Table III. As expected the developed localization algorithm resulted in a better for performance for both path loss models, especially

INHOUDSOPGAVE

x

Inhoudsopgave Extended abstract

x

Lijst met afkortingen

xiii

1 Inleiding

1

1.1

Probleemstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Doelstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.3

Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2 Literatuur 2.1

2.2

3

Algemeen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2.1.1

Rangingtechnieken en draadloze technologieën

. . . . . . . . . . . . . . .

3

2.1.2

Driehoeksmeting en statistische methoden . . . . . . . . . . . . . . . . . .

4

State of the art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3 Lokalisatiealgoritme 3.1

3.2

3.3

6

Simpel algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.1.1

Grondplan en roosterpunten . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.1.2

Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.1.3

Metriek: Mean Square Error . . . . . . . . . . . . . . . . . . . . . . . . .

7

Viterbi-algoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.1

Algemeen principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.2

Toegepast op lokalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.3

Eenvoudig voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2.4

Viterbi en Viterbi Huidig . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

Optimalisatie van het lokalisatiealgoritme . . . . . . . . . . . . . . . . . . . . . .

10

INHOUDSOPGAVE

3.4

xi

3.3.1

Muren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.3.2

Deuren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.3.3

Maximale snelheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.3.4

Robuustheid tegen verkeerde beginpositie . . . . . . . . . . . . . . . . . .

11

3.3.5

Selectie van padverliesmetingen . . . . . . . . . . . . . . . . . . . . . . . .

12

Prestatiemaat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.4.1

Constructie ground truth . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.4.2

Nauwkeurigheid en spreiding . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.4.3

Overige criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4 Padverliesmodellen

16

4.1

RSSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.2

Padverliesmodellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.2.1

Free-space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.2.2

One-slope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.2.3

TGn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.2.4

WHIPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Uitvoeringstijd offline-fase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.3

5 Implementatie in testbed

20

5.1

Eigenschappen testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

5.2

Mobiele node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.2.1

ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.2.2

WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

5.3

Calibratie padverliesmodellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5.4

Real-time implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

5.4.1

MySQL databank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

5.4.2

Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

6 Resultaten

25

6.1

Testpaden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

6.2

ZigBee: vergelijking padverliesmodellen . . . . . . . . . . . . . . . . . . . . . . .

27

6.3

ZigBee versus WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

6.4

Combinatie ZigBee en WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

INHOUDSOPGAVE

xii

6.5

Visualisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.6

Reproduceerbaarheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

6.7

Sensitiviteitanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

6.7.1

Ruis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

6.7.2

Selectie aantal access points . . . . . . . . . . . . . . . . . . . . . . . . . .

33

6.7.3

Beperkt aantal vaste nodes . . . . . . . . . . . . . . . . . . . . . . . . . .

34

6.7.4

Geheugen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

6.7.5

Uitvoeringstijd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.7.6

Sample rate en uitmiddeling . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.7.7

Wandelsnelheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

6.7.8

Zendvermogen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

6.7.9

Minimum padverlies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

6.7.10 Kostfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

6.7.11 Open en gesloten deuren . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Globaal optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.8

7 Toekomstig werk

44

7.1

RSSI alternatieven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

7.2

ZigBee en WiFi alternatieven . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

7.3

A-priori kennis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

7.4

Ruis en outlierfiltering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

7.5

Meerdere verdiepingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

7.6

Inbedding in indoornavigatiesysteem . . . . . . . . . . . . . . . . . . . . . . . . .

45

8 Conclusie

46

Bibliografie

48

Lijst van figuren

49

Lijst van tabellen

50

LIJST MET AFKORTINGEN

xiii

Lijst met afkortingen AoA

Angle of Arrival

AP

Access Point

DAoA

Difference Angle of Arrival

DSSS

Direct-Sequence Spread Spectrum

DToA

Difference Time of Arrival

IEEE

Institute of Electrical and Electronics Engineers

LoS

Line of Sight

MSE

Mean Square Error

PL

Path Loss

RFID

Radio-Frequency Identification

RSSI

Received Signal Strength Indication

ToA

Time of Arrival

USB

Universal Serial Bus

UWB

Ultra-Wide Band

WHIPP

WiCa Heuristic Indoor Propagation Prediction Tool

WiCa

Wireless & Cable

WiFi

Wireless Fidelity

WSN

Wireless Sensor Network

INLEIDING

1

Hoofdstuk 1

Inleiding 1.1

Probleemstelling

Indoorlokalisatiesystemen hebben toepassingen in vele domeinen, denk maar aan de zorgsector, bedrijvensector, industriële sector,. . . Voorbeelden van dergelijke toepassingen zijn: het traceren van ouderen, navigatie door een gebouw, equipment tracking, begeleiding doorheen een museum,. . . Om aan lokalisatie te doen, wordt meestal een tracking device gebruikt dat beacons uitzendt om, bijvoorbeeld via de gemeten signaalsterkte, zo de locatie te schatten. Maar door de fysieke complexiteit van vele indooromgevingen kan er een grote variabiliteit op de gemeten signaalsterkte zitten waardoor lokalisatiealgoritmen vaak nog niet voldoende nauwkeurig zijn. Door gebruik te maken van nieuwe en geavanceerde technieken kan deze accuraatheid worden verbeterd.

1.2

Doelstelling

De bedoeling van deze thesis is het ontwikkelen van een nauwkeurig algoritme voor indoorlokalisatiebepaling met behulp van het Viterbi-algoritme. Dit komt neer op het bepalen van de meest waarschijnlijke sequentie van posities in plaats van enkel de meest waarschijnlijke huidige positie. Hiervoor worden de meetwaarden uit het verleden bijgehouden en telkens opnieuw in rekening gebracht om zo de nieuwe meest waarschijnlijke positie te bepalen. Daarna is het de bedoeling om het ontwikkelde lokalisatiealgoritme te testen via simulaties en te valideren in real-life omstandigheden.

1.3 Overzicht

1.3

2

Overzicht

Eerst wordt er in Sectie 2 een overzicht gegeven van (indoor)lokalisatiealgoritmen en de huidige state of the art uit de literatuur. In Sectie 3 wordt er zowel een simpel als een op het Viterbialgoritme gebaseerd lokalisatiesysteem uiteengezet. De tweede zal telkens getoetst worden aan de eerste om de verbetering van het ontwikkelde lokalisatiealgoritme te kunnen onderzoeken in dezelfde omstandigheden. In Sectie 4 worden de gebruikte padverliesmodellen toegelicht, daarna in Sectie 5 komt de implementatie in het sensor lab van de Zuiderpoort (Gent) aan bod, gevolgd door een uitbreiding die in real-time het afgelegde traject visualiseert. De resultaten komen aan bod in Sectie 6, hier worden de prestaties van het ontwikkelde lokalisatiealgoritme en de sensitiviteitsanalyse van verscheidene parameters besproken. Er wordt afgesloten met toekomstig werk in Sectie 7 en een conclusie in Sectie 8.

LITERATUUR

3

Hoofdstuk 2

Literatuur 2.1

Algemeen

Indoorlokalisatiesystemen maken meestal gebruik van een vaste infrastructuur en een mobiel toestel (tracking device), waarbij er onderling signalen (beacons) kunnen worden uitgewisseld. Deze systemen onderscheiden zich van elkaar op volgende manieren [10]: • gebruikte rangingtechniek • gebruikte draadloze technologie • manier waarop de locatie wordt voorspeld

2.1.1

Rangingtechnieken en draadloze technologie¨ en

Met rangingtechniek wordt de karakterisatie van afstand, tijd of hoek die de beacons afleggen, bedoeld. De draadloze technologie is deze die wordt gebruikt om de beacons uit te zenden. De meest courante rangingtechnieken en draadloze technologieën worden samengevat in Tabel 2.1. De rangingtechnieken die gebruik maken van Time of Arrival (ToA) of Angle of Arrival (AoA) leveren nauwkeurige metingen op maar hebben extra hardware nodig, bijvoorbeeld in het geval van AoA worden er directionele antennes gebruikt die duurder zijn en relatief meer energie verbruiken. Methoden gebaseerd op ontvangen signaalsterkte maken meestal gebruik van Received Signal Strength Indication (RSSI) [17] en aangezien de meeste draadloze toestellen deze functionaliteit hebben ingebouwd, brengt dit geen extra kost met zich mee. Bij de draadloze technologieën heeft Ultra-Wide Band (UWB), zoals de naam al aangeeft, een veel hogere bandbreedte dan bijvoorbeeld WiFi en dus ook een veel hogere temporele resolutie, wat het dus

2.2 State of the art

4

geschikt maakt voor zeer nauwkeurige lokalisatie toepassingen [8]. Het nadeel van UWB is dat een groot deel van de huidige systemen nog niet zijn uitgerust met deze (nieuwe) technologie. Voor de voorspelling van de locatie kan men gebruik maken van driehoeksmeting of statistische methoden. Tabel 2.1: Rangingtechnieken en draadloze technologieën Rangingtechniek ToA DToA AoA

Time of Arrival: verschil in tijd tussen het zenden en ontvangen van een beacon Difference Time of Arrival Angle of Arrival: gebruikt directionele antennes om de hoek te bepalen

DAoA

Difference Angle of Arrival

RSSI

Received Signal Strength Indication: indicatie van ontvangen vermogen bij de ontvanger

Draadloze technologie

2.1.2

Afkorting / Beschrijving

Afkorting / Beschrijving

RFID

Radio-frequency identification

DSSS

Direct-sequence spread spectrum, wordt o.a. gebruikt door ZigBee

WiFi

Wireless Fidelity

UWB

Ultra Wide Band

Driehoeksmeting en statistische methoden

Bij lokalisatie met behulp van driehoeksmeting zijn er minstens 3 punten (metingen via een rangingtechniek) nodig, om de positie te bepalen. Een voorbeeld hiervan is geometrische multilateratie. Bij statistische methoden worden distributies van de afstanden gebruikt voor de locatie te voorspellen. Er zijn hoofdzakelijk drie aanpakken: statistische multilateratie, maximale likelihood schatters en Bayesiaanse schatters. Een overzicht van lokalisatie technieken met behulp van geometrische of statistische technieken wordt gegeven in [12].

2.2

State of the art

Enkele huidige state of the art algoritmen maken gebruik van a-priori kennis om bijvoorbeeld via probabilistische distributies de beweging van de mobiele node te modelleren. Deze a-priori kennis wordt in [9] met een gewichtsfactor in rekening gebracht om zo de meest waarschijnlijke huidige locatie te voorspellen. In [14] wordt semantische informatie geëxtraheerd uit de interactie van een gebruiker met zijn omgeving, deze informatie wordt in combinatie met RSSI als rangingtechniek gebruikt om aan lokalisatie te doen. Voor een indooromgeving is het interessant om het gebruikte propagatiemodel te tunen voor dit

2.2 State of the art

5

specifieke gebouw, maar dit is zeer tijdrovend omdat er veel metingen voor nodig zijn. In [15] wordt een empirisch model voor het padverlies opgesteld dat wordt gematcht aan een deterministisch ray tracing model, zodat er geen uitgebreide metingen nodig zijn. Er werd aangetoond dat dit veel sneller ging zonder veel aan nauwkeurigheid in te boeten. In [18] wordt een multipath gebaseerd indoornavigatiesysteem uiteengezet, meer bepaald werd hier de informatie van reflectiecomponenten expliciet gebruikt om virtuele anchors te plaatsen, die worden gebruikt als extra datapunten in het lokalisatiealgoritme. Dit indoornavigatiesysteem werd in [11] gevalideerd, een real-time implementatie werd ontwikkeld om de performantie en invloeden in verscheidene omgevingen te testen. De draadloze technologie UWB in combinatie met ToA als rangingtechniek levert in [2] zeer nauwkeurige resultaten op voor de lokalisatie van sensoren op het lichaam binnen een kleine test setting (1.5 x 1.5 m2 ). In [1] wordt een indoor radio channel simulation platform beschreven dat een volledig gevectoriseerde UWB ray tracing tool voor indoor scenario’s aanbiedt (gebaseerd op grafentheorie). Er wordt rekening gehouden met de positie op het lichaam en het stralingspatroon van de antenne evenals de beweging van het menselijke lichaam (gemodelleerd via een Multi Cylinders Model ). Dit levert zeer nauwkeurige predicties op die onder andere kunnen worden gebruik om referentiepadverliezen in een lokalisatiealgoritme te voorspellen. Netwerklokalisatie en navigatie in coöperatieve draadloze netwerken wordt onderzocht in [5]. Hierin wordt informatie over de omgeving, verkregen door waveforms te onderzoeken met channel state identification technieken, gebruikt om ranging errors weg te werken (range error mitigation). Dit resulteerde in een significante verbetering van de prestaties van location-aware networks. Deze thesis verschilt van de vorige technieken in het opzicht dat er geen gebruik wordt gemaakt van gebruikersinteractie om semantische informatie te verkrijgen of datasets om probabilistische distributies te modelleren maar enkel een eenvoudige calibratie, een gedetailleerd grondplan en het verleden van het afgelegde traject.

LOKALISATIEALGORITME

6

Hoofdstuk 3

Lokalisatiealgoritme 3.1 3.1.1

Simpel algoritme Grondplan en roosterpunten

Het vertrekpunt van het lokalisatiealgoritme is een grondplan van een gebouw of verdieping, in het geval van deze thesis is dat een grondplan van de derde verdieping van het Complex Zuiderpoort in Gent, waar ook het w-iLab.t testbed zich bevindt [4]. Op dit testbed zullen de real-life testen van het ontwikkelde algoritme en het valideren van de simulaties worden uitgevoerd. Dit grondplan meet 16.8 m bij 90 m en zowel de muren (beton of drywall ) als de deuren worden aangegeven, evenals de locaties van alle 57 access points (zie Figuur 3.1). Deze deuren zijn nodig voor de werking van het ontwikkelde lokalisatiealgoritme (zie Sectie 3.3.2).

Figuur 3.1: Grondplan

Dit grondplan wordt verdeeld in roosterpunten (gridpoints), een roosterpunt stelt een mogelijke positie op het grondplan voor (waar het tracking device zich kan bevinden). Het aantal roosterpunten per oppervlakte eenheid wordt bepaald door de roosterpuntresolutie. Deze roosterpuntresolutie zal dus de maximaal haalbare nauwkeurigheid voor een deel bepalen omdat

3.1 Simpel algoritme

7

op deze manier de locaties waar de te traceren mobiele node zich kan bevinden, alreeds worden vastgelegd. Om te starten wordt er een roosterpuntresolutie van 1 m gebruikt (zie Figuur 3.2).

Figuur 3.2: Roosterpuntresolutie van 1 m

3.1.2

Fingerprinting

Voor alle roosterpunten op het grondplan moet het padverlies tot alle vaste access points van het testbed worden berekend, zodat er referentiewaarden beschikbaar zijn waarmee de metingen kunnen worden vergeleken tijdens de online-fase (het effectief lokaliseren van de mobiele node). Deze fingerprintingmethode bestaat uit het aanmaken van een referentiedatabase met behulp van een padverliesmodel en wordt ook wel de offline-fase genoemd. De uitvoeringstijd van deze offline-fase wordt bepaald door het gebruikte padverliesmodel en door de ingestelde roosterpuntresolutie, aangezien er bij een fijnere resolutie voor meer roosterpunten het padverlies tot alle access points zal moeten worden berekend (zie Sectie 4.3). De gebruikte padverliesmodellen komen aan bod in Sectie 4.2.

3.1.3

Metriek: Mean Square Error

De online-fase bestaat uit het vergelijken van de gemeten padverliezen met deze uit de referentiedatabase om zo de meest waarschijnlijke positie te bepalen. Om te starten gebruiken we in dit simpele algoritme de Mean Square Error (MSE) tussen de laatste metingen en de referentiepadverliezen (van een roosterpunt) uit de fingerprintdatabase om zo de meest waarschijnlijke positie (roosterpunt) te bepalen: N

1X (P Lgem,n − P Lref,n )2 MSE = n

(3.1)

n=1

Waarbij PLgem,n het gemeten padverlies van een vaste node n voorstelt, PLref,n het padverlies van dezelfde vaste node n maar uit de referentiedatabase en N het totaal aantal vaste nodes in het testbed voorstelt.

3.2 Viterbi-algoritme

3.2

8

Viterbi-algoritme

In tegenstelling tot het simpele algoritme van Sectie 3.1 houden we hier wel rekening met het verleden van een traject en bepalen we de meest waarschijnlijke sequentie van locaties. Eerst wordt het algemene principe uitgelegd, daarna wordt dit toegepast op het lokalisatiealgoritme.

3.2.1

Algemeen principe

Het Viterbi algoritme is een in 1967 door Andrew Viterbi ontwikkeld algoritme [16]. Oorspronkelijk werd dit gebruikt voor het decoderen van een convolutionele code over een (ruizig) digitaal communicatiekanaal. Ondertussen heeft het echter een breed toepassingsgebied, onder andere in deep-space communicatie, bio-informatica en spraakherkenning. Het algoritme zoekt de meest waarschijnlijke sequentie van verborgen toestanden – het Viterbi pad – dat resulteert in de geobserveerde toestanden.

3.2.2

Toegepast op lokalisatie

Om dit principe toe te passen op een (indoor)lokalisatiesysteem, moeten we het Viterbi pad vrij letterlijk nemen. In plaats van op ieder moment met de huidige meetwaarden de beste nieuwe positie van de mobiele node te voorspellen (zoals in het simpele algoritme van Sectie 3.1), gaan we op ieder tijdstip het meest waarschijnlijke, tot nu toe afgelegde, traject bepalen. De vorige gemeten padverliezen worden in rekening gebracht door ook het verleden van een traject bij te houden en bovendien alle waarschijnlijke trajecten verder op te bouwen in het geheugen van het lokalisatiesysteem. Aan ieder traject zit een bepaalde kost gekoppeld, namelijk de som van alle MSE’s langs het traject in kwestie:

costi =

T X

M SEi,t

(3.2)

t=1

Waarbij costi de kost van traject i is, i is de nummer van een traject dat in het geheugen wordt opgebouwd, T is het aantal tijdstappen die tot nu toe zijn gepasseerd en MSEi,t stelt de Mean Square Error, zoals gedefinieerd in Sectie 3.1.3, van traject i op tijdstip t voor. De laatste locatie van het traject dat op dit moment, van alle bijgehouden trajecten, de laagste kost heeft, wordt als meest waarschijnlijke huidige locatie genomen. Het reconstrueren van het verleden van de huidige meest waarschijnlijke locatie (dus zijn traject) kan worden gezien als een vorm van backtracking.

3.2 Viterbi-algoritme

3.2.3

9

Eenvoudig voorbeeld

Om dit principe te illustreren wordt een vereenvoudigde situatie geschetst in Figuur 3.3. Het te traceren object kan zich enkel op een lijn voortbewegen (eendimensionaal), er zijn 5 mogelijke locaties (0 tot en met 4), het startpunt is locatie 2 en er kan maximaal 1 eenheid naar links of naar rechts worden bewogen per tijdstap. De input (metingen) zijn: 1, 0, 3, 4. Er zijn twee mogelijke trajecten getekend waarbij de kost per stap en de totale kost is berekend, bijvoorbeeld in de eerste stap is de input 1 en beide trajecten bewegen naar locatie 1 dus de kost is 0 (1 − 1 = 0), in stap 2 is de input 0 en het bovenste traject gaat naar locatie 0 (dus de totale kost blijft 0), maar het onderste traject keert reeds terug naar locatie 2 dus de totale kost wordt hier 2 (2 − 0 = 2). Omdat de totale kost als metriek wordt genomen, zal in de laatste stap het onderste traject toch als meest waarschijnlijke globale traject worden bekomen. Met huidige locatie wordt de huidige meest waarschijnlijke locatie bedoeld dus de output van het lokalisatiealgoritme bij iedere locatieupdate.

Figuur 3.3: Eenvoudig voorbeeld Viterbi principe

Ter vergelijking: in het ontwikkelde algoritme worden als input de padverliezen tot alle vaste nodes gebruikt i.p.v. een locatie, de kostfunctie is de MSE i.p.v. het verschil en de mogelijke locaties zijn de roosterpunten van het grondplan i.pv. de eendimensionale lijn.

3.2.4

Viterbi en Viterbi Huidig

Een ander verschil ten opzichte van het originele Viterbi-algoritme, namelijk het decoderen van een convolutionele code, is dat daar meestal enkel het globale resultaat van belang is (dus wanneer alle data is ontvangen). Bij lokalisatie in ware tijd, is het belangrijk dat er tijdens het verwerken van input er op ieder moment ook de meest waarschijnlijke positie als output kan

3.3 Optimalisatie van het lokalisatiealgoritme

10

worden weergeven. Om dit verschil te duiden, wordt er bij de resultaten (zie Sectie 6) onderscheid gemaakt tussen Viterbi en Viterbi Huidig, waarbij deze laatste de meest waarschijnlijke positie op het huidige moment als output neemt, terwijl met Viterbi het globale meest waarschijnlijke traject wordt bedoeld, dus wanneer alle verzamelde data van het experiment in rekening is gebracht. Concreet komt dit er op neer dat Viterbi wordt gelijkgesteld aan het traject dat op het einde van het experiment de laagste kost heeft, dus wanneer de eindlocatie is bereikt.

3.3

Optimalisatie van het lokalisatiealgoritme

Om de performantie van het lokalisatiealgoritme te verbeteren worden er enkele additionele beperkingen aan het gevolgde traject toegevoegd.

3.3.1

Muren

Op het grondplan van Sectie 3.1.1 zijn ook de muren aangegeven; om de nauwkeurigheid van het lokalisatiealgoritme te verbeteren, wordt ervoor gezorgd dat enkel daadwerkelijk afgelegde trajecten als output kunnen worden gegenereerd. Door de roosterpunten per kamer (de gangen worden hier ook als kamers gezien) in een aparte lijst te stockeren, is het mogelijk om realistische trajecten op te bouwen waarbij het te traceren object niet door muren kan.

3.3.2

Deuren

Een traject passeert doorgaans door meerdere kamers dus het moet mogelijk zijn om van een lijst van roosterpunten (refererend naar een kamer) te switchen naar de lijst van roosterpunten die overeenstemmen met een aangrenzende kamer. Hiervoor gebruiken we de deuren die op het grondplan zijn getekend. Met de instelbare parameter minDistDoor wordt aangegeven hoe dicht men zich bij een deur moet bevinden om in aanmerking te komen om de kamer te kunnen verlaten. Standaard wordt deze ingesteld op 2 m. Omdat deze 2 m ervoor kan zorgen dat het afgelegde traject schijnbaar toch door een muur gaat is ervoor geopteerd om bij het verlaten van een kamer het exacte midden van een deur als roosterpunt aan het afgelegde traject toe te voegen (zie Figuur 3.4). Dit is vooral belangrijk voor het visuele resultaat en dit extra roosterpunt wordt dan ook niet in rekening gebracht bij het bepalen van de gemiddelde error en standaardafwijking (zie Sectie 3.4.1). Een nadeel van deze aanpak is dat wanneer de deuren niet op het grondplan zouden zijn aangeduid, dit wel nog (manueel) moet gebeuren voor de werking van het algoritme. Dit kan wel op een snelle manier gebeuren omdat de minDistDoor parameter


11

een kleine fout op de aanduiding van een deur toelaat. Het belangrijkste is dat er een deur is getekend zodat het te traceren object niet vast komt te zitten in een kamer.

Figuur 3.4: Realistischer traject door toevoegen midden deur

3.3.3

Maximale snelheid

Omdat de mobiele node zich niet oneindig snel kan verplaatsen, is het ook mogelijk om een maximale snelheid (parameter maxSnelheid ) in te stellen. Samen met de parameter sampleRate (in deze context: het tempo waaraan nieuwe gemeten padverliezen als input aan het algoritme worden aangeboden), bepalen deze de maximaal toegestane verplaatsing (parameter maxDist) tussen twee opeenvolgende samples. Het is deze maxDist die de mobiele node maximaal kan afleggen per locatieupdate langs een traject:

maxDist =

maxSnelheid sampleRate

[m]

(3.3)

Bijvoorbeeld wanneer de maximale snelheid is ingesteld op 1.67 m/s (= 6 km/u) en de sample rate is ingesteld op 1 s-1 , is de maximale verplaatsing bij een locatieupdate gelijk aan 1.67 m. Aangezien de roosterpuntresolutie 1 m is, komt dit neer op 8 mogelijke volgende posities (zie Figuur 3.5).

3.3.4

Robuustheid tegen verkeerde beginpositie

Een nadeel van dit algoritme is dat de globale prestatie wel afhankelijk is van de beginpositie. Wanneer bijvoorbeeld het traceren begint in de buurt van een muur en het lokalisatiealgoritme voorspelt als initiële positie de andere kant van de muur, dan moet eerst een realistisch traject worden opgebouwd dat naar de juiste kamer leidt, vooraleer de predictie accuraat kan zijn. Wanneer er geen kort traject is naar de echte kamer kan het wel even duren vooraleer het algoritme zal stabiliseren. Een oplossing hiervoor is, om enkel bij de beginpositie, naburige


12

Figuur 3.5: Mogelijke volgende posities bij een bepaalde maxSnelheid en sampleRate

roosterpunten als extra startpunten toe te voegen en van daar ook trajecten op te bouwen in het geheugen. Deze methode (voegBeginPosToe) heeft 2 argumenten: aantalLevels en interDist. Per level worden er 8 roosterpunten toegevoegd, die op een cirkel rond de beste, voorspelde, beginpositie liggen en waarbij de levels een afstand interDist uit elkaar liggen. Omwille van de roosterpuntresolutie van 1 m, zullen de alternatieve beginposities niet exact op de cirkel liggen. Figuur 3.6 geeft een voorbeeld met de parameters aantalLevels = 2 en interDist = 1 m, dus vanaf het eerste tijdstip worden er hier 17 trajecten opgebouwd (2 · 8 + 1 = 17), dit aantal stijgt bij iedere locatieupdate omdat er steeds meer mogelijke trajecten bijkomen. Het aantal opgebouwde paden in het geheugen zal satureren wanneer dit gelijk is aan de parameter aantalPaden, vanaf dan wordt er steeds een selectie van beste trajecten gemaakt (om de uitvoeringstijd te beperken zodat het algoritme in ware tijd kan werken en om geheugen problemen te vermijden). De kost die aan elk roosterpunt van de extra beginposities wordt gehecht, is het verschil in MSE tussen de referentiewaarden van dit roosterpunt en deze van de metingen. Wanneer vanaf de tweede locatieupdate de metingen (en predicties) nauwkeuriger worden, kan het algoritme zich op deze manier snel corrigeren en zal een ander traject (en beginpositie) als meest waarschijnlijke worden bekomen.

3.3.5

Selectie van padverliesmetingen

Omdat de padverliesmodellen nauwkeurigere predicties geven voor de padverliezen tussen een roosterpunt en zijn nabije access points (APs), wordt er in het lokalisatiealgoritme meer belang gehecht aan de laagste padverliezen. De parameter aantalAPs geeft aan hoeveel van de sterkste metingen (laagste padverliezen) tot de vaste nodes in het testbed worden meegerekend voor de volgende meest waarschijnlijke locatie te bepalen. Hiervoor worden de padverliezen gesorteerd

3.4 Prestatiemaat

13

Figuur 3.6: Extra beginposities toevoegen voor robuustheid tegen foute initiële predictie

van klein naar groot. In Sectie 6.7.2 wordt de invloed en beste waarde van deze parameter onderzocht; standaard wordt deze op 15 ingesteld. Er wordt ook getest met scenario’s waarbij enkel een selectie van de vaste nodes uit het testbed werken (zie Sectie 6.7.3), het verschil met het vorige is dat daar normaal wel alle vaste nodes werken en er een selectie (aantalAPs) wordt gemaakt van de gemeten padverliezen. Voor het uiteindelijke algoritme in pseudocode zie Algoritme 1 op pagina 14.

3.4 3.4.1

Prestatiemaat Constructie ground truth

Om de prestaties en nauwkeurigheid van verschillende experimenten en scenario’s te kunnen vergelijken, is er nood aan een ground truth en een metriek. Met de ground truth worden de exacte locaties bedoeld, dus het effectief bewandelde traject. Voor de simulaties is dit eenvoudig omdat er eerst een traject wordt uitgestippeld en pas daarna de overeenkomstige padverliezen (uit de fingerprintdatabase) worden bepaald om als input te dienen (nadat er eventueel ruis is aan toegevoegd). Maar voor real-life testen ligt dit iets minder voor de hand omdat er tijdens het broadcasten van pakketten met de mobiele node continu wordt gewandeld, er vervolgens een uitmiddeling van de gemeten padverliezen over een bepaald tijdsinterval plaatsvindt, om dan als inputargumenten aan het algoritme te worden doorgegeven. Aangezien ook de invloed van de parameter sampleRate wordt onderzocht, zal niet elke test uit evenveel tijdstippen of locatieupdates bestaan. De testtrajecten worden bij benadering aan constante snelheid afgelegd en de grote lijnen van het afgelegde traject worden op het grondplan getekend. Een methode (maakExactePad ) deelt deze grote lijnen op in exact evenveel tijdstappen als er locatieupdates

3.4 Prestatiemaat

Algoritme 1 Ontwikkeld lokalisatiealgoritme in pseudocode maxDist ← maximale stapgrootte tussen 2 locatieupdates

minDistDoor ← minimum afstand tot een deur om er door te gaan

aantalAP s ← aantal beste access points in rekening te brengen bij MSE berekening

aantalP aden ← maximaal aantal paden die worden opgebouwd in geheugen aantalLevels ← aantal levels rond de beginpositie die worden toegevoegd

interDist ← afstand tussen de levels bij het toevoegen van extra beginposities

while nieuwe PLgem als input do

sorteer PLgem (voor selectie van beste APs bij MSE berekening) paden ← alle paden in het geheugen

padenCost ← bijhorende kost van alle paden for all pad in paden do huidigeP os ← laatste locatie van pad

huidigeRoom ← kamer waarin huidigePos zich bevindt huidigeT otalCost ← kost van dit pad

mogelijkeP os ← lege lijst voor mogelijke volgende posities in te stockeren for all roosterpunt in huidigeRoom do if afstand huidigePos tot roosterpunt ≤ maxDist then voeg roosterpunt toe aan lijst mogelijkePos

end if end for if afstand huidigePos tot een deur van huidigeRoom ≤ minDistDoor then voeg roosterpunten aan andere kant van deur toe aan lijst mogelijkePos

end if for all roosterpunt in mogelijkePos do bepaal MSE tussen PLgem en PLref van beste aantalAPs waarden tempCost ← huidigeT otalCost + M SE

stockeer link tussen roosterpunt en tempCost

end for sorteer tempCost if beginpositie then voegBeginPosToe(aantalLevels, interDist) end if update paden (hou beste aantalPaden bij, via tempCost) update padenCost if huidigeRoom van een pad is veranderd then voeg het midden van een deur toe als vorig roosterpunt end if end for end while

14

3.4 Prestatiemaat

15

zijn in de test (waarbij de hoekpunten altijd worden behouden). Op deze manier kan ieder experiment en scenario in absolute cijfers worden beoordeeld.

3.4.2

Nauwkeurigheid en spreiding

Eenmaal voor een testscenario de coördinaten van de ground truth zijn aangemaakt (zoals besproken in Sectie 3.4.1), kan de nauwkeurigheid en spreiding ten opzichte van de co¨ ordinaten van de predictie worden bepaald:

errorgem =

T T q 1X 1X (xgt,t − xpred,t )2 + (ygt,t − ypred,t )2 errort = T T t=1

(3.4)

t=1

v u T u1 X σ=t (errort − errorgemiddeld )2 T

(3.5)

t=1

Hierbij stelt errorgem de gemiddelde nauwkeurigheid voor, errort is de nauwkeurigheid (afwijking) op tijdstap t, T het aantal locatieupdates (tijdstappen) van een experiment, (xgt,t , ygt,t ) en (xpred,t , ypred,t ) zijn de co¨ ordinaten van respectievelijk de ground truth en de predictie op tijdstap t. De spreiding (standaardafwijking) wordt in de formule voorgesteld door σ.

3.4.3

Overige criteria

In deze thesis ligt de meeste nadruk op nauwkeurigheid en spreiding als criteria om het ontwikkelde algoritme te evalueren, daarnaast wordt er nog gekeken naar de rekencomplexiteit. Wanneer de klemtoon elders wordt gelegd, kunnen tal van andere factoren ook meespelen. Zo is energie-efficiëntie belangrijk voor wanneer alle gegevens in een mobiele node (met klein vermogen) moeten worden verwerkt. Bij toepassingen in grote gebouwen met veel verdiepingen of met zeer veel vaste nodes zal schaalbaarheid belangrijker worden.

PADVERLIESMODELLEN

16

Hoofdstuk 4

Padverliesmodellen 4.1

RSSI

RSSI staat voor Received Signal Strength Indicator en geeft een indicatie van het ontvangen power level uitgedrukt in dB. Bij de real-life testen van het lokalisatiealgoritme gebruiken we deze RSSI-waarden, uitgemiddeld over een bepaald tijdsinterval, om zo de padverliezen van een bepaald moment te berekenen. Deze worden dan gebruikt als input, waar ze worden vergeleken met de referentiewaarden (uit de fingerprintdatabase), om zo de meest waarschijnlijke volgende positie te bepalen. Alle gains en losses van het medium tussen zender en ontvanger zitten vervat in het link budget:

PRX = PTX + GTX − LTX − PL − LX + GRX − LRX

[dB]

(4.1)

Waarbij PRX het ontvangen vermogen is, PTX het zendvermogen, GTX en GRX de antenna gain van zender en ontvanger, LTX en LRX de verliezen in zender en ontvanger, PL is het padverlies en LX de overige verliezen (bijvoorbeeld door multipath fading). In dit lokalisatiealgoritme gebruiken we enkel het padverlies dus is er een calibratie van de metingen nodig om deze te kunnen vergelijken met de padverliezen uit de referentiedatabase (zie Sectie 5.3). Hierna volgt de beschrijving van vier verschillende padverliesmodellen en de principes waarop deze gebaseerd zijn. In Sectie 6.2 worden deze padverliesmodellen met elkaar vergeleken.

4.2 Padverliesmodellen

4.2 4.2.1

17

Padverliesmodellen Free-space

Het free-space padverliesmodel is het verlies in signaalsterkte van een elektromagnetische golf als gevolg van een line-of-sight (LoS) pad door free-space (meestal lucht), waarbij de elektromagnetische golf geen obstakels kruist en er dus geen rekening wordt gehouden met reflectie of diffractie. De formule voor dit free-space model:

PLfree-space = 20 log10

4π df c

[dB]

(4.2)

Waarbij PLfree-space [dB] het totale padverlies berekend met het free-space model is, c de snelheid is van het licht in vacu¨ um: 3 × 108 m/s, d [m] de afstand is tot de ontvangende of zendende node en f [Hz] de frequentie is van het uitgezonden signaal. Aangezien we hier een mobiele ZigBee en WiFi node gebruiken is deze frequentie gelijk aan 2.4 GHz.

4.2.2

One-slope

Een one-slope padverliesmodel ziet er als volgt uit:

PLone-slope = P L0 + 10n log10 (d)

[dB]

(4.3)

Waarbij PLone-slope [dB] het totale padverlies berekend met het one-slope model is. Dit model wordt gefit aan empirische data, waarbij de twee parameters: PL0 [dB] (het padverlies op een referentieafstand d0 [m]) en de padverliesexponent n [-] (slope) worden bepaald. In [3] werd dit gedaan voor de beschouwde verdieping van het testbed in de Zuiderpoort, beide parameterwaarden staan in Tabel 4.1. Tabel 4.1: Parameterwaarden one-slope padverliesmodel

4.2.3

PL0 [dB]

n [-]

27

2.85

TGn

Het TGn model is een two-slope padverliesmodel dat bestaat uit free-space padverlies (met slope n1 ) tot een bepaalde breekpuntafstand en vanaf daarna een bijkomend padverlies met slope n2 .

4.2 Padverliesmodellen

18

Deze breekpuntafstand is gerelateerd aan de antennehoogte bij welke de slope van het padverlies verandert [7]. Dit leidt tot de volgende formule:

PLTGn =

(

P L0 + 10n1 log10 (df )

d ≤ dBP

d P L0 + 10n1 log10 (df ) + 10n2 log10 ( 0.01 )

d > dBP

[dB]

(4.4)

Waarbij PLTGn [dB] het totale padverlies berekend met het TGn model is, PL0 [dB] het padverlies is op een afstand d0 , n1 [-] de eerste padverliesexponent, n2 [-] de bijkomende padverliesexponent, d [m] de afstand tot de ontvangende of zendende node, d0 [m] is een referentieafstand, dBP [m] de breekpuntafstand en f [Hz] de frequentie van het uitgezonden signaal. De parameterwaarden staan in Tabel 4.2. Tabel 4.2: Parameterwaarden TGn padverliesmodel

4.2.4

PL0 [dB]

n1 [-]

n2 [-]

d0 [m]

dBP [m]

32.4

2

3.5

10

10

WHIPP

De WiCa Heuristic Indoor Propagation Prediction Tool (WHIPP model) is het meest geavanceerde padverliesmodel van de vier en wordt beschreven in [13]. Dit heuristische algoritme is speciaal ontwikkeld voor een indooromgeving en bestaat uit drie bijdragen: distance loss, cumulated wall loss en interaction loss. Dit resulteert in de volgende formule:

PLWHIPP = P L0 + 10n log10 | {z

distance loss

d d0

}

+

X

LWi

i

| {z }

cumulated wall loss

+

X

LB,j

[dB]

(4.5)

j

| {z }

interaction loss

Waarbij PLWHIPP [dB] het totale padverlies berekend met het WHIPP model is, PL0 [dB] het padverlies is op een afstand d0 , n [-] is een padverliesexponent, d [m] is een afstand tussen zender en ontvanger en d0 [m] is een referentieafstand. De eerste twee termen stellen het padverlies door de afgelegde afstand van het signaal voor (distance loss), de derde term (cumulated wall loss) is de som van de verliezen wanneer het signaal door een muur propageert en de vierde term (interaction loss) houdt rekening met het verlies als gevolg van het veranderen van propagatierichting langs het propagatiepad tussen zender en ontvanger.

4.3 Uitvoeringstijd offline-fase

4.3

19

Uitvoeringstijd offline-fase

De uitvoeringstijden van de offline-fase, dus het aanmaken van de fingerprintdatabase met referentiepadverliezen gegenereerd door deze vier modellen, uitgevoerd op een laptop met Intel Core i7 3610QM 2.4 GHz processor en 4 GB DDR3-SDRAM, staan in Tabel 4.3. Verdubbeling van de roosterpuntresolutie (van 1 m naar 2 m) zal de uitvoeringstijd door 4 delen, aangezien het grondplan tweedimensionaal is. Tabel 4.3: Uitvoeringstijden offline-fase voor alle padverliesmodellen Padverliesmodel →

free-space

one-slope

TGn

WHIPP

Uitvoeringstijd [s]

0.0307

0.0397

0.0880

971.76

Enkel met het WHIPP padverliesmodel neemt dit een niet verwaarloosbare tijd in beslag. Aangezien deze waarden voor alle experimenten kunnen worden hergebruikt, worden ze eenmalig berekend en vervolgens lokaal gestockeerd om dan bij het begin van een experiment opnieuw te worden ingeladen. Op deze manier is de duur van de opstartfase van het lokalisatiealgoritme altijd te verwaarlozen.

IMPLEMENTATIE IN TESTBED

20

Hoofdstuk 5

Implementatie in testbed 5.1

Eigenschappen testbed

Het w-iLab.t is een experimenteel, generic, heterogeen draadloos testbed van iMinds in de Zuiderpoort (Gent), dat is uitgerust met ongeveer 200 sensor en WiFi nodes [4]. Het gebouw bestaat uit verscheidene kantoorruimtes, vergaderzalen, PC-klassen,. . . Het wordt gebruikt voor het ontwikkelen en testen van draadloze applicaties, zowel WiFi gebaseerde mesh als ad-hoc netwerken. Alle draadloze nodes zijn aangesloten op een wired backbone netwerk voor het beheer, verwerken en loggen van gegevens tijdens een experiment. Op deze manier kunnen de resultaten ook achteraf worden geanalyseerd. In deze thesis worden de experimenten op de derde verdieping uitgevoerd, zie Figuur 5.1.

Figuur 5.1: Derde verdieping van het w-iLab.t testbed

5.2 Mobiele node

5.2

21

Mobiele node

Om het ontwikkelde algoritme te valideren in een real-life omgeving, gebruiken we een mobiele node die beacons uitzendt aan een tempo van 10 pakketten per seconde. Er worden twee draadloze technologieën gebruikt: ZigBee en WiFi. Beide gebruiken een externe antenne met een gain van 5 dBi (niet isotroop dus de oriëntatie van de antenne heeft invloed op de ontvangen signaalsterkte) en hebben een indoor range van ongeveer 100 m. De mobiele nodes worden gevoed met een batterij van 19 Volt, deze kan tegelijkertijd beide nodes van stroom voorzien: de ZigBee node via USB en de WiFi node via een gewone kabel (zie Figuur 5.2).

Figuur 5.2: Mobiele nodes (links WiFi, rechts ZigBee en batterij)

5.2.1

ZigBee

ZigBee is een draadloze technologie gebaseerd op de IEEE 802.15 standaard met het oog op een open globale standaard voor het opzetten van low-power, low-cost, wireless mesh netwerken. Het device om beacons te verzenden is een TMote Sky sensor node [6] uitgerust met een Chipcon CC2420 radio chip die werkt bij een frequentie van 2.4 GHz, meer specifiek wordt channel 26 van ZigBee gebruikt (2480 MHz). Deze mobiele node draait RadioPerf voor het verzenden van pakketten. De node heeft een zendvermogen van 5 dBm (exclusief antenne) en de gebruikte bandbreedte is 2 MHz.

5.2.2

WiFi

WiFi is eveneens een draadloze technologie maar is gebaseerd op de IEEE 802.11 standaard en vooral bekend van de WLAN-toepassingen om toegang tot het internet te verlenen. Het

5.3 Calibratie padverliesmodellen

22

mobiele toestel is hier een iNode, dit is een embedded PC met een WiFi interface. Het heeft een patched kernel die phyclick draait met madwifi als wireless driver. Er wordt gebruik gemaakt van channel 1 van WiFi (2412 MHz). Het zendvermogen van deze mobiele node is instelbaar van 0 dBm tot en met 23 dBm en de gebruikte bandbreedte is 20 MHz.

5.3

Calibratie padverliesmodellen

Zowel voor de ZigBee als de WiFi mobiele node wordt een calibratie uitgevoerd omdat de RSSImetingen onder andere afhankelijk zijn van het uitgezonden vermogen en er in het algoritme enkel naar het padverlies wordt gekeken (zie Sectie 4.1). Er wordt een vaste shift verondersteld dus de calibratie wordt slechts eenmaal uitgevoerd. Hiervoor wordt op vijf locaties, verspreid over het testbed, gedurende 30 seconden beacons gebroadcast aan een tempo van 10 pakketten per seconde dus in totaal 300 RSSI-metingen per locatie. Het gemiddelde van deze 300 RSSI-metingen wordt, voor alle vier de padverliesmodellen uit Sectie 4.2, gematcht aan hun referentiepadverliezen. De gemiddelde shift van deze vijf locaties nemen we als ideale shift. Zo hebben we dus vier ideale shiften, één voor elke padverliesmodel (zie Tabel 5.1). Tabel 5.1: Ideale shift voor de vier padverliesmodellen Padverliesmodel

free-space

one-slope

TGn

WHIPP

Ideale shift (ZigBee) [dB]

17.472

20.949

9.542

11.927

Ideale shift (WiFi) [dB]

106.204

103.984

117.962

113.653

De ideale shiften voor de mobiele WiFi node zijn veel groter, omdat de padverliezen hier op een andere manier worden gelogd als bij de mobiele ZigBee node. Bijvoorbeeld: een groot padverlies bij de ZigBee node is ongeveer −90, terwijl dit bij de WiFi node dan 10 is en een klein padverlies bij de ZigBee node is ongeveer −40, terwijl dit bij WiFi node dan 60 is. Beide zouden moeten worden gemapped naar −100 en −50 voor groot en klein referentiepadverlies respectievelijk, voor het WHIPP padverliesmodel is deze shift ongeveer 10 en 110 voor ZigBee en WiFi respectievelijk: −90 − 10 = −100 en 10 − 110 = −100.

5.4

Real-time implementatie

Voor de visualisatie in ware tijd wordt bij iedere locatieupdate de meest waarschijnlijke positie, samen met zijn trajectverleden, naar een databank weggeschreven en vervolgens uitgelezen door

5.4 Real-time implementatie

23

de WHIPP webservice. Het trajectverleden van de huidige meest waarschijnlijke positie wordt telkens mee weggeschreven omdat dit gaandeweg kan veranderen.

5.4.1

MySQL databank

Om de trajecten naar een MySQL databank weg te schrijven, wordt het java.sql package gebruikt. De databank tabel heeft 1 kolom en een entry heeft de volgende structuur: x1,y1,x2,y2,type Dit stelt een lijnstuk voor waarbij (x1,y1) de vorige locatie is, (x2,y2) de positie die deze entry voorstelt en type kan exact, simple of viterbi zijn (zie Tabel 5.2). Tabel 5.2: Verklaring types type

Uitleg

exact

Het traject dat de ground truth voorstelt

simple

Het traject gegenereerd met het simpele lokalisatiealgoritme

viterbi

Het traject gegenereerd met het ontwikkelde lokalisatiealgoritme

Deze drie types worden gebruikt om het traject in een andere kleur weer te geven zodat het onderscheid kan gemaakt worden tussen de ground truth (zie Sectie 3.4.1), het simpele algoritme (zie Sectie 3.1) en het ontwikkelde algoritme (zie Sectie 3.2). Deze drie types worden in de visualisatietool weergegeven in het rood, groen en zwart respectievelijk. Op deze manier wordt een heel traject opgebouwd uit meerdere lijnstukken (één extra per locatieupdate en per type), Figuur 5.3 geeft een voorbeeld van hoe deze drie soorten trajecten worden weergegeven in de visualisatietool van de WHIPP webservice.

Figuur 5.3: Visualisatie van de drie soorten trajecten

5.4 Real-time implementatie

5.4.2

24

Delay

De vertraging tussen effectief op een bepaalde positie staan en de locatieupdate in de visualisatietool, is van meerdere factoren afhankelijk. De RSSI-metingen worden weggeschreven naar een databank, vanaf er bijvoorbeeld 10 nieuwe metingen zijn (komt overeen met 1 seconde wanneer de mobiele node aan een tempo van 10 pakketten per seconde broadcast), worden deze uitgelezen door het lokalisatiealgoritme en wordt het gemiddelde ervan berekend. Vervolgens wordt de nieuwe meest waarschijnlijke positie berekend en wordt het volledige verleden van dit traject geconstrueerd via backtracking. Dit traject wordt uiteindelijk weggeschreven naar een andere databank, waar de visualisatietool om de 2 seconden een update uit haalt. De processing delay van het lokalisatiealgoritme zelf wordt onderzocht in Sectie 6.7.5 en zal te verwaarlozen blijken ten opzichte van de andere factoren zoals de communicatiedelay. Deze variërende communicatiedelays zijn moeilijk te voorspellen maar gemiddeld gezien lag de totale vertraging van de visualisatietool in de praktijk rond de 4 seconden.

RESULTATEN

25

Hoofdstuk 6

Resultaten 6.1

Testpaden

In totaal worden er negen testpaden gebruikt (zie Figuur 6.1), het startpunt van ieder testpad wordt aangegeven met een rode cirkel. De afgelegde afstand van de testpaden varieert van 50 m tot 100 m, er werd aan normale snelheid gewandeld en er werd nergens stilgestaan (zie Tabel 6.1). Ter referentie: 1.11 m/s komt overeen met 4 km/u. De trajecten werden afgelegd met de mobiele node in de hand op een hoogte van ongeveer 1.5 m, deze werd hierbij zo ver mogelijk van het lichaam gehouden om de eventuele invloed van het lichaam op het signaal te beperken. Tabel 6.1: Eigenschappen testpaden Testpad nummer

Afstand [m]

Gemiddelde snelheid [m/s]

1

84.46

1.24

2

111.0

0.74

3

76.17

1.07

4

70.07

1.09

5

68.06

1.05

6

45.73

1.14

7

89.83

1.18

8

99.05

1.25

9

138.56

1.15

Gemiddeld

86.99

1.10

6.1 Testpaden

26

(a) Testpad 1

(b) Testpad 2

(c) Testpad 3

(d) Testpad 4

(e) Testpad 5

(f) Testpad 6

(g) Testpad 7

(h) Testpad 8

(i) Testpad 9

Figuur 6.1: Testpaden

6.2 ZigBee: vergelijking padverliesmodellen

6.2

27

ZigBee: vergelijking padverliesmodellen

In Tabel 6.2 staan de nauwkeurigheid en spreiding (in het vervolg afgekort met N en S) voor de vier padverliesmodellen uit Sectie 4.2, waarbij voor ieder padverliesmodel zijn ideale shift is toegepast (zoals berekend in Sectie 5.3). Er is uitgemiddeld over de data van de negen testpaden, afgelegd met de mobiele ZigBee node, en de gebruikte instellingen van het ontwikkelde algoritme staan in Tabel 6.3. De parameter aantalPaden geeft aan hoeveel trajecten er in het geheugen worden opgebouwd (en bijgehouden) en staat standaard op 1000, in Sectie 6.7.4 wordt de invloed van deze parameter onderzocht. Tabel 6.2: Vergelijking vier padverliesmodellen Algoritme →

Padverliesmodel ↓

Simpel

Viterbi Huidig

Viterbi

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

free-space

3.48

3.39

3.17

2.0

2.61

1.59

one-slope

4.05

3.44

3.89

2.26

2.97

1.77

TGn

5.68

4.31

5.34

2.45

4.04

2.31

WHIPP

2.94

3.32

2.83

1.94

2.26

1.44

Tabel 6.3: Instellingen lokalisatiealgoritme Instelling

Waarde

maxSnelheid

1.67 m/s

sampleRate

1 sample/s

minDistDoor

2m

aantalAPs

15

aantalPaden

1000

aantalLevels

5

interDist

1m

Het WHIPP predictie model scoort zowel voor het simpele als het ontwikkelde algoritme altijd het best en het TGn model overal het minst. Het free-space model is iets beter dan het one-slope model (door de ideale shift wordt het verschil tussen deze twee vooral bepaald door de slope, deze is 2 voor free-space en 2.85 voor one-slope). Verder is het ontwikkelde algoritme, zowel Viterbi als Viterbi Huidig (zie Sectie 3.2.4 voor het verschil tussen beiden), voor alle padverliesmodellen nauwkeuriger dan het eenvoudige algoritme (Simpel ). Naast een nauwkeuriger resultaat is er ook een aanzienlijk verschil in spreiding (standaardafwijking op de nauwkeurigheid), deze trend zal zich in alle resultaten verder zetten. Onderling is Viterbi

6.3 ZigBee versus WiFi

28

ook altijd beter dan Viterbi Huidig wat te verklaren is doordat alle data in rekening werd gebracht voor het globaal beste traject te bepalen. In de volgende secties zal steeds het WHIPP padverliesmodel worden gebruikt. De procentuele verbetering die dit padverliesmodel oplevert, wordt in Sectie 6.8 berekend ten opzichte van het free-space model omdat dit de tweede beste resultaten gaf.

6.3

ZigBee versus WiFi

Naast de mobiele ZigBee node, is er ook getest met een mobiele WiFi node. Om te vergelijken zijn testpaden 1, 7 en 9 ook afgelegd met deze WiFi node. De vergelijking tussen de twee mobiele nodes (uitgemiddeld over dezelfde drie testpaden) staat in Tabel 6.4, dezelfde instellingen uit Tabel 6.3 werden gebruikt samen met WHIPP als padverliesmodel. Tabel 6.4: Vergelijking ZigBee met WiFi als draadloze technologie Algoritme →

Draadloze technologie ↓

Simpel

Viterbi Huidig

Viterbi

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

ZigBee

3.0

4.44

2.61

1.76

2.16

1.54

WiFi

3.89

3.45

3.29

2.23

2.7

1.62

De mobiele ZigBee node scoort op alle vlakken iets beter, buiten de spreiding bij Simpel. De overige trends zetten zich ook bij de mobiele WiFi node voort: er is verbetering bij het ontwikkelde algoritme ten opzichte van het simpele algoritme en Viterbi komt er als beste van de drie uit.

6.4

Combinatie ZigBee en WiFi

Bij het combineren van beide mobiele nodes, kunnen de signalen interfereren omdat deze in dezelfde frequentieband werken. Om de interferentie tot een minimum te beperken, zijn de gebruikte kanalen zo ver mogelijk uit elkaar gekozen. Voor de sensor node gebruikten we dus ZigBee channel 26 (2480 MHz) en voor de WiFi node gebruikten we WiFi channel 1 (2412 MHz). Het zendvermogen van de mobiele WiFi node wordt, net zoals de ZigBee node, op 5 dBm ingesteld. Indien een vaste node uit het testbed beide signalen ontvangt, is er een extra datapunt als input voor het algoritme. De resultaten (nauwkeurigheid en spreiding, uitgemiddeld over testpaden 1, 7 en 9) worden samengevat in Tabel 6.5, waarbij de rijen ZigBee en WiFi de

6.5 Visualisatie

29

resultaten zijn van hetzelfde experiment (dus met de twee mobiele nodes tegelijk wandelen) maar apart bekeken. Dit verklaart het verschil met Sectie 6.3. Tabel 6.5: Combinatie ZigBee en WiFi Algoritme →

Simpel

Viterbi Huidig

Viterbi

mobiele node ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

ZigBee

4.64

3.51

5.12

2.77

2.81

1.6

WiFi

3.35

2.88

3.2

1.99

2.68

1.62

ZigBee + WiFi

3.41

2.81

3.78

2.06

2.55

1.48

De nauwkeurigheid en spreiding van ZigBee+WiFi is bij Viterbi net iets beter dan deze van ZigBee of WiFi apart, maar de verbetering blijft beperkt. In vergelijking met Tabel 6.4 valt vooral op dat de prestatie van de mobiele ZigBee node minder goed is wanneer het experiment met twee mobiele nodes tegelijkertijd wordt uitgevoerd. Beide mobiele nodes worden tijdens het afleggen van de trajecten ongeveer een halve meter uit elkaar gehouden (want worden tegelijk door één persoon gedragen), dit zou de prestaties kunnen be¨ınvloeden.

6.5

Visualisatie

Naast de absolute maatstaven om het ontwikkelde algoritme te beoordelen, kunnen de trajecten ook op het grondplan worden geplot om een visueel beeld te krijgen van de prestaties en verschillen met het eenvoudige lokalisatiealgoritme. Zie Figuren 6.2a – 6.2d voor de visualisatie van testpad 1, eens met en zonder gesimuleerde ruis, voor zowel het eenvoudige als het ontwikkelde algoritme (in Sectie 6.7.1 wordt uitgelegd hoe deze ruis wordt gesimuleerd). De visualisatie van hetzelfde testpad maar afgelegd met de mobiele ZigBee node (dus geen simulatie) kan worden teruggevonden in Figuren 6.2e – 6.2f. De gebruikte instellingen zijn opnieuw deze uit Tabel 6.3, alleen staat bij de simulatie de parameter maxSnelheid op 2 m/s, omdat het anders soms voorviel dat het beste roosterpunt nog net niet kon worden bereikt. Wanneer er geen ruis wordt toegevoegd (geen afwijkingen op de referentiepadverliezen), is het meest waarschijnlijke traject niet exact gelijk aan de ground truth (van Sectie 3.4.1) omdat een gereconstrueerde traject zich enkel via de roosterpunten kan voortbewegen (terwijl de ground truth enkel uit rechte lijnen bestaat), vandaar dat de gevonden nauwkeurigheid en spreiding niet exact nul zullen zijn. De gereconstrueerde trajecten bij de simulaties geven in het geval zonder ruis voor beide

6.5 Visualisatie

30

(a) Simulatie zonder ruis

(b) Simulatie zonder ruis

(c) Simulatie met ruis (stdDev = 12 dB)

(d) Simulatie met ruis (stdDev = 12 dB)

(e) Mobiele ZigBee node

(f) Mobiele ZigBee node

Figuur 6.2: Visualisatie van testpad 1 onder verschillende omstandigheden (links Simpel, rechts Viterbi ) lokalisatiealgoritmen zo goed als hetzelfde resultaat (alleen bij een van de laatste locatieupdates is er een klein verschil). Wanneer er wel ruis (variatie op de padverliezen) wordt toegevoegd, werkt Viterbi duidelijk beter, het gereconstrueerde traject vertoont geen onregelmatig sprongen of outliers zoals bij het eenvoudige lokalisatiealgoritme (Simpel ). Voor het experiment met de mobiele ZigBee node zien we een gelijkaardig resultaat alleen bevinden beide lokalisatiealgoritmen zich op het einde in de verkeerde kamer en zit er een nog grotere variatie op het traject van Simpel. De bijhorende nauwkeurigheid en spreiding van de zes visualisaties staan in Tabel 6.6 en bevestigen deze resultaten. Bij dit traject van de mobiele ZigBee node is ook de werking van de methode voegBeginPosToe (uit Sectie 3.3.4) zichtbaar: oorspronkelijk begint Viterbi op

6.6 Reproduceerbaarheid

31

dezelfde plaats als Simpel maar in het uiteindelijke traject, is deze beginpositie iets opgeschoven naar de exacte beginpositie (de beginposities zijn met een cirkel aangeduid). De oorspronkelijke bedoeling van deze methode was om worst case scenario’s met foute beginposities te vermijden maar ook bij mindere afwijkingen, kan het een (lichte) verbetering geven. Tabel 6.6: Nauwkeurigheid en spreiding van de visualisaties uit Figuur 6.2 Algoritme →

6.6

Simpel

Viterbi

Situatie ↓

N [m]

S [m]

N [m]

S [m]

Simulatie zonder ruis

0.39

0.14

0.4

0.15

Simulatie met ruis (stdDev = 12 dB)

3.31

3.0

1.97

1.69

Mobiele ZigBee node

3.61

4.82

2.77

1.54

Reproduceerbaarheid

De testtrajecten zijn eens met de mobiele ZigBee node, eens met de mobiele WiFi node en eens met beide mobiele nodes tegelijk afgelegd. Om de invloed van de omgeving of aanwezige mensen op het resultaat te onderzoeken, zijn testtrajecten 1 en 2 (zie Figuur 6.1) vijfmaal met de mobiele ZigBee node afgelegd. De gemiddelde resultaten (G) en de afwijking op deze resultaten (A) staan voor beide trajecten in Tabel 6.7. Tabel 6.7: Reproduceerbaarheid van de resultaten Algoritme →

Simpel

Viterbi Huidig

Viterbi

Testtraject ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

1 (G)

3.538

4.518

3.514

2.094

2.77

1.598

1 (A)

0.517

2.203

0.271

0.326

0.320

0.387

2 (G)

3.81

3.144

3.714

2.072

2.93

1.544

2 (A)

0.469

1.782

0.244

0.186

0.188

0.159

De gemiddelde afwijking op de nauwkeurigheid en spreiding is voor het ontwikkelde algoritme slechts 0.256 m en 0.265 m respectievelijk, terwijl dit voor het simpele algoritme 0.493 m en 1.992 m is. Dus vooral op de spreiding (S) bij het simpele algoritme zit een relatief grote variatie voor de vijf metingen.

6.7 Sensitiviteitanalyse

6.7 6.7.1

32

Sensitiviteitanalyse Ruis

Om de invloed van afwijkingen van de ideale padverliezen op de nauwkeurigheid van de predictie te onderzoeken, bijvoorbeeld door multipath fading, wordt er aan de ideale input, via simulatie, ruis met een zekere standaardafwijking (parameter stdDev [dB]) toegevoegd. Met ideale input worden de referentiepadverliezen van de exacte posities langs een testpad bedoeld. Hiervoor wordt een nieuwe ruiswaarde voor ieder padverlies tot een vaste node gegenereerd met het java.util.Random package: j a v a . u t i l . Random r = new j a v a . u t i l . Random ( ) ; L i s t PL input = new A r r a y L i s t ( ) ; f o r ( double PL ref : t e s t p a d P L r e f ){ PL input . add ( P L r e f + r . n e x t G a u s s i a n ( ) ∗ stdDev ) ; } Waarbij PL input de input voor het lokalisatiealgoritme is, testpad PL ref de lijst met de exacte padverliezen van een tijdstap langs het testpad en stdDev de te variëren parameter is. Opnieuw worden de negen testpaden uit Sectie 6.1 gebruikt. De gebruikte instellingen zijn voor alle ruisniveaus en alle testpaden dezelfde (zie Tabel 6.3), alleen staat de parameter maxSnelheid opnieuw op 2 m/s om dezelfde reden als in Sectie 6.5. De invloed van ruis (variatie op de metingen) op de prestaties van zowel het simpele als het ontwikkelde algoritme wordt getest met de parameter aantalAPs op 15 en 57, in dat laatste geval worden dus de metingen van alle vaste nodes uit het testbed bij iedere locatieupdate gebruikt (zie Figuren 6.3a – 6.3b). De x-as stelt het toegevoegde ruisniveau in dB voor (parameter stdDev, stapgrootte 2 dB) en op de y-as staat de nauwkeurigheid met de spreiding als errorbars (uitgemiddeld over de simulaties van alle negen testpaden, vijf keer herhaald). De prestaties van Simpel verslechteren aan een sneller tempo dan deze van Viterbi of Viterbi Huidig. Wanneer de metingen van alle beschikbare access points worden gebruikt bij de voorspelling, is het resultaat voor het eenvoudige algoritme gemiddeld 1.06 m en 1.07 m beter en voor het ontwikkelde algoritme is dit 0.85 m en 0.75 m (voor de nauwkeurigheid en spreiding respectievelijk). Het verschil wordt groter naarmate er meer variatie aan de metingen wordt toegevoegd, bij stdDev = 20 dB, is dit verschil voor het eenvoudige algoritme reeds 2.04 m en


33

Simpel Viterbi Huidig Viterbi

12

10

nauwkeurigheid [m]

10

nauwkeurigheid [m]


12

8

6

4

8

6

4

2

2

0

0 0

2

4

6

8

10

12

14

16

18

20

0

2

4

6

stdDev [dB]

(a) aantalAPs = 15

8

10

12

14

16

18

20

stdDev [dB]

(b) aantalAPs = 57

Figuur 6.3: Invloed van ruis op nauwkeurigheid (simulatie) 1.91 m en voor het ontwikkelde algoritme 1.95 m en 1.78 m (voor de nauwkeurigheid en spreiding respectievelijk). Maar in realiteit zal de stelling dat op iedere meting evenveel ruis zit (zoals bij de simulatie), los van hoe ver de vaste node zich bevindt, niet opgaan. In de volgende Sectie wordt de optimale waarde van deze parameter aantalAPs bepaald met real-life experimenten.

6.7.2

Selectie aantal access points

Wanneer het zendvermogen van de mobiele node voldoende sterk is, ontvangen meestal ongeveer 20 vaste nodes (access points) de beacons. In het geval van de mobiele WiFi node, met een maximaal zendvermogen van 23 dBm, kunnen alle 57 vaste nodes uit het testbed de beacons opvangen, waar de mobiele node zich ook bevindt. Het padverliesmodel voorspelt meestal een betrouwbaarder padverlies voor de dichtstbijzijnde access points (APs), daarom wordt eerst een selectie gemaakt van de aantalAPs laagste padverliezen (waarbij aantalAPs een getal is). Vervolgens wordt er enkel met deze meetwaarden rekening gehouden bij het voorspellen van de nieuwe meest waarschijnlijke positie. Zowel voor de mobiele ZigBee als WiFi node wordt dit optimale aantal bepaald, door de nauwkeurigheid en spreiding in functie van aantalAPs te onderzoeken (zie Figuur 6.4). Opnieuw werd de data van alle negen de testpaden, afgelegd met de mobiele ZigBee node, en de data van testpaden 1, 7 en 9, afgelegd met de mobiele WiFi node, gebruikt. Bij de ZigBee node stagneert de nauwkeurigheid vanaf een aantalAPs waarde van 10, voor de WiFi node ligt dit aantal bij 16. Dit komt omdat er bij de mobiele WiFi node een sterker zendvermogen werd gebruikt (23 dBm versus 5 dBm), dus het signaal propageert verder waardoor er


34

Invloed van aantalAPs (ZigBee) 10

8

6

4

2

0


10

nauwkeurigheid [m]

nauwkeurigheid [m]

Invloed van aantalAPs (WiFi) Simpel Viterbi Huidig Viterbi

8

6

4

2

0 2

4

6

8

10

12

14

16

18

aantalAPs [−]

20

2

4

6

8

10

12

14

16

18

20

aantalAPs [−]

Figuur 6.4: Sensitiviteitsanalyse van aantalAPs meer metingen zijn die een extra bijdrage tot de nauwkeurigheid en spreiding leveren. Aangezien het resultaat stagneert vanaf een bepaalde waarde (en niet slechter wordt), kunnen eigenlijk alle metingen worden gebruikt maar dit is in principe overbodig en zal de uitvoeringstijd van een locatieupdate enkel doen toenemen.

6.7.3

Beperkt aantal vaste nodes

In ideale omstandigheden werken alle 57 vaste nodes uit het testbed, maar tijdens een experiment kunnen sommige nodes down zijn door node failure, maintenance,. . . In deze sectie wordt de robuustheid tegen steeds meer wegvallende vaste nodes onderzocht of voor gebouwen waar veel minder vaste nodes zijn ge¨ınstalleerd. Er worden vijf scenario’s onderzocht, de configuraties van scenario 1 tot en met 4 zijn afgebeeld in Figuur 6.5 (waarbij de nodes die down zijn in het grijs staan). Scenario 5 gebruikt alle (beschikbare) vaste nodes. De resultaten voor de mobiele ZigBee en WiFi node staan in Tabel 6.8. Bij ZigBee werd er uitgemiddeld over alle negen testpaden en bij WiFi over testpaden 1, 7 en 9, opnieuw met de instellingen uit Tabel 6.3. Omdat er bij scenario’s 1 en 2 minder dan 15 APs werken, wordt de aantalAPs parameter hier automatisch aangepast naar 5 en 10 respectievelijk. Beide mobiele nodes geven, zoals verwacht, het beste resultaat wanneer alle vaste nodes worden gebruikt. De ZigBee node is, op scenario 1 na, altijd beter dan de WiFi node. Dit is te verklaren omdat bij scenario 1, het aantal vaste nodes zeer schaars is maar de mobiele WiFi node deze nog wel altijd allemaal kan bereiken. Verder valt op dat in deze omstandigheden met weinig vaste nodes het eenvoudige algoritme met de mobiele ZigBee node veel slechter presteert in vergelijking met het ontwikkelde algoritme. Bijvoorbeeld bij scenario 2 is Viterbi 5.43 m


35

(a) Scenario 1

(b) Scenario 2

(c) Scenario 3

(d) Scenario 4

Figuur 6.5: Scenario’s met verschillend aantal werkende vaste nodes uit het testbed nauwkeuriger en zit er 12.2 m minder spreiding op de resultaten ten opzichte van Simpel, terwijl dit bij scenario 5 nog maar 0.68 m en 1.88 m is. Dus het ontwikkelde algoritme heeft vooral een meerwaarde in omstandigheden met weinig beschikbare vaste nodes (bij de ZigBee node).

6.7.4

Geheugen

Beperkt aantal paden Het geheugengebruik wordt vooral bepaald door het aantal paden die in het geheugen worden bijgehouden en opgebouwd. Dit is enkel van belang voor het ontwikkelde algoritme aangezien het simpele algoritme enkel de laatste meting gebruikt. In Figuur 6.6a wordt de nauwkeurigheid uitgezet in functie van de parameter aantalPaden op een logaritmische schaal (uitgemiddeld over de negen testpaden en overige instellingen zoals uit Tabel 6.3). Het simpele algoritme blijft dus over de hele lijn constant omdat er geen rekening wordt gehouden met het verleden. De nauwkeurigheid van het ontwikkelde algoritme blijft constant vanaf ongeveer 100 paden maar zelfs bij 1000 paden is de processing delay nog te verwaarlozen ten opzichte van de andere factoren dus dit is geen beperkende factor (zie verder Sectie 6.7.5). Enkel recent verleden Wanneer een node een zeer lange tijd moet worden getraceerd, kan het interessant zijn om enkel het recente verleden in rekening te brengen, zodat niet alle data uit het verleden moet worden bijgehouden. In deze sectie wordt gezocht naar het minimum aantal locaties uit het verleden die men nodig heeft om een bepaalde nauwkeurigheid en spreiding te halen. Om dit te


36

Tabel 6.8: Nauwkeurigheid en spreiding voor de verschillende scenario’s ZigBee

Algoritme →

Simpel

Viterbi Huidig

Viterbi

scenario ↓

#vaste nodes ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

1

5

8.28

11.45

7.25

10.28

5.02

7.7

2

10

8.81

15.31

4.73

3.88

3.38

3.11

3

20

4.67

7.72

3.51

2.27

2.82

1.84

4

30

3.73

5.4

3.22

2.22

2.53

1.62

5

57

2.94

3.32

2.83

1.94

2.26

1.44

1

5

4.97

3.43

5.21

3.67

3.52

2.24

2

10

4.63

2.94

4.88

2.93

4.1

2.54

3

20

3.65

2.25

3.88

2.56

3.12

2.04

4

30

3.53

2.62

3.51

2.59

2.74

1.69

5

57

3.89

3.45

3.29

2.23

2.7

1.62

WiFi

bekijken wordt wel het volledige pad bijgehouden (om achteraf de nauwkeurigheid en spreiding te kunnen bepalen) maar worden de beste paden geselecteerd op basis van de kost van de laatste aantalRecentVerleden posities. De nauwkeurigheid wordt uitgezet in functie van deze parameter aantalRecentVerleden, zie Figuur 6.6b (opnieuw uitgemiddeld over de negen testpaden en overige instellingen zoals uit Tabel 6.3). In een intiële fase van het algoritme, kunnen er natuurlijk maar zoveel posities uit het verleden in rekening worden gebracht als er locatieupdates zijn geweest. Simpel Viterbi Huidig Viterbi

20 18

18

16

16

nauwkeurigheid [m]

nauwkeurigheid [m]


20

14 12 10 8 6

14 12 10 8 6

4

4

2

2

0

0 0

10

1

2

10

10

aantalPaden [−]

(a) Invloed van aantalPaden

3

10

2

4

6

8

10

12

14

16

18

20

aantalRecentVerleden [−]

(b) Invloed van aantalRecentVerleden

Figuur 6.6: Invloed van geheugen op prestatie Vooral het Viterbi traject is afhankelijk van deze parameter omdat Viterbi Huidig steeds kan verspringen van traject en Simpel geen rekening houdt met het verleden. Vanaf dat er rekening


37

wordt gehouden met de laatste 14 metingen om de nieuwe positie te bepalen, treedt er nog maar weinig verbetering meer op bij de nauwkeurigheid en spreiding van Viterbi.

6.7.5

Uitvoeringstijd

De uitvoeringstijd wordt vooral bepaald door het aantal paden dat in het geheugen worden opgebouwd. Het gemiddeld aantal microseconden nodig voor het berekenen van een locatieupdate (terwijl alle andere paden in het geheugen eveneens verder worden opgebouwd) is uitgezet in functie van de parameter aantalPaden in Figuur 6.7. Zowel de x-as als de y-as hebben een logaritmische schaal. Aangezien in Sectie 6.7.4 al werd aangetoond dat 1000 paden ruimschoots volstaat, nemen we dit als bovengrens. Een locatieupdate met het ontwikkeld lokalisatiealgoritme neemt dan, op een laptop met Intel Core i7 3610QM 2.4 GHz processor en 4 GB DDR3-SDRAM geheugen, gemiddeld 345.02 µs in beslag, dit volstaat ruimschoots om in ware tijd te kunnen werken. De uitvoeringstijd bij het simpele algoritme wordt niet be¨ınvloed door aantalPaden en was uitgemiddeld over dezelfde negen testpaden gelijk aan 4.86 µs met een standaardafwijking van 0.83 µs.

2

uitvoeringstijd [µs]

10

1

10

0

10

0

10

1

10

2

10

3

10

aantalPaden [−]

Figuur 6.7: Uitvoeringstijd in functie van de parameter aantalPaden

6.7.6

Sample rate en uitmiddeling

De mobiele nodes zenden 10 beacons per seconde uit, met sample rate bedoelen we hier de parameter (sampleRate) die aangeeft aan welk tempo het lokalisatiealgoritme nieuwe input (metingen) te verwerken krijgt. Meer uitmiddeling resulteert in nauwkeurigere metingen maar ook minder snel een locatieupdate en dus ook grotere stappen tijdens het traject wat de prestaties


38

opnieuw kan be¨ınvloeden. Aangezien er tijdens het afleggen van de testpaden continu wordt gewandeld is er ergens een sweet spot (een optimale zone dat een afweging is tussen meer locatieupdates en meer uitmiddeling). Er wordt getest met 10 verschillende waarden voor sampleRate en telkens wordt de nauwkeurigheid en spreiding berekend (zie Figuur 6.8). Vanaf een bepaalde waarde van sampleRate (bij constante waarde van maxSnelheid ) wordt de maximaleVerplaatsing kleiner dan 1 m (zie Sectie 3.3.3); aangezien de roosterpuntresolutie op 1 m staat, zal het algoritme vast komen te zitten op een bepaalde positie. Om deze reden wordt de maximaleVerplaatsing altijd op minstens 1 m ingesteld. De resultaten zijn uitgemiddeld over testpaden 1, 7 en 9 afgelegd met de mobiele WiFi node omdat hier de pakketten werden gelogd per 100 ms zodat er voldoende vrijheid is om sampleRate te kiezen (bij de ZigBee node werd er al voor het wegschrijven naar de databank, uitgemiddeld over 10 metingen oftewel 1 seconde). 12 Simpel Viterbi Huidig Viterbi

nauwkeurigheid [m]

10

8

6

4

2

0 0

1

10

10

sample rate [s−1]

Figuur 6.8: Invloed van sample rate en uitmiddeling op nauwkeurigheid

De beste resultaten worden verkregen met de parameter sampleRate tussen 1s-1 en 2.5s-1 , dit komt overeen met een nieuwe input om de 0.4 tot 1 seconde (dus uitmiddeling over 4 tot 10 pakketten). Voor de werking in ware tijd kan het eerste de beste keuze zijn want er is dan iets minder vertraging, in omstandigheden met veel variatie op de metingen is het tweede waarschijnlijk de betere keuze want meer uitmiddeling.

6.7.7

Wandelsnelheid

Een tragere wandelsnelheid laat een grotere uitmiddeling of meer locatieupdates toe. Om de invloed hiervan te onderzoeken werd testpad 9, tegen drie snelheden afgelegd (traag, normaal, snel) tegen respectievelijk: 0.67 m/s, 1.14 m/s en 1.74 m/s met uitmiddeling over: 1, 2, 5, 10


39

en 20 pakketten. De resultaten zijn samengevat in Tabel 6.9. Om de grootte van de tabel te beperken wordt enkel de gemiddelde nauwkeurigheid van het ontwikkelde algoritme (Viterbi ) over het volledige traject weergeven (Simpel en Viterbi Huidig zijn achterwege gelaten). De parameter maxSnelheid wordt aangepast aan de wandelsnelheid: 1 m/s, 1.67 m/s en 2 m/s voor de drie wandelsnelheden respectievelijk. Tabel 6.9: Nauwkeurigheid en spreiding bij verschillende snelheden en uitmiddeling Uitmiddeling →

1 pakket

2 pakketten

5 pakketten

10 pakketten

20 pakketten

Snelheid ([m/s]) ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

traag (0.67)

2.77

1.65

2.62

1.66

2.28

1.42

2.91

1.48

2.99

1.76

normaal (1.14)

2.89

1.78

2.59

1.72

2.34

1.57

2.34

1.63

3.12

1.96

snel (1.74)

2.75

1.64

2.41

1.32

2.46

1.36

3.4

2.3

4.31

2.88

Bij traag wandelen wordt het beste resultaat verkregen bij een uitmiddeling over 5 pakketten, dus het lokalisatiealgoritme krijgt een nieuwe input om de halve seconde (want er worden 10 beacons gebroadcast per seconde). Bij normaal en snel wandelen scoren twee opties ongeveer even goed: uitmiddelen over 5 of 10 pakketten bij normaal wandelen en uitmiddelen over 2 of 5 pakketten bij snel wandelen. Bij uitmiddeling over 2 pakketten kan er sneller een update worden gegenereerd, waar snel wandelen dus een voordeel uit kan halen. De verschillen blijven wel zeer klein dus we kunnen stellen dat de wandelsnelheid maar weinig impact heeft op de prestaties van het lokalisatiealgoritme.

6.7.8

Zendvermogen

Het maximale zendvermogen van de mobiele WiFi node is 23 dBm, bij een groter zendvermogen zullen meer vaste nodes het signaal oppikken. Het nadeel van een groter zendvermogen is dat de batterij sneller leeg gaat en dat andere gebruikers (die in dezelfde frequentieband opereren) meer interferentie zullen ervaren. Deze twee factoren hebben wel geen invloed op de prestatie van het lokalisatiealgoritme. Testtraject 9 werd zes keer afgelegd met een verschillend zendvermogen en de nauwkeurigheid en spreiding werden voor alle zendvermogens voor dezelfde scenario’s als in Sectie 6.7.3 onderzocht (zie Figuur 6.5). De resultaten worden samengevat in Tabel 6.10. Opnieuw wordt enkel de nauwkeurigheid en spreiding van Viterbi weergeven teneinde de grootte van de tabel te beperken. De verschillen zijn klein vanaf een zendvermogen van 5 dBm of meer, indien het energieverbruik dus in rekening wordt gebracht, is een zendvermogen van 5 dBm een goede keuze. Het


40

Tabel 6.10: Nauwkeurigheid en spreiding bij verschillende zendvermogens en scenario’s Scenario →

1

2

3

4

5

Zendvermogen [dBm] ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

0

3.71

1.6

3.27

1.97

3.41

1.86

2.87

1.9

3.8

2.82

5

2.67

1.5

3.26

2.09

2.94

1.72

2.78

1.69

2.67

1.6

10

3.45

1.96

4.75

2.74

3.65

2.13

2.83

1.84

2.75

1.83

15

2.84

1.67

4.29

2.65

3.2

1.84

2.52

1.59

2.64

1.77

20

3.14

1.63

4.31

2.5

3.23

1.73

2.78

1.54

2.7

1.54

23

2.97

1.71

4.48

2.54

2.8

1.73

2.45

1.69

2.64

1.65

meest nauwkeurige resultaat wordt nog wel altijd verkregen met een zendvermogen van 23 dBm terwijl het grootste deel van de vaste nodes werken, maar verschillen blijven miniem.

6.7.9

Minimum padverlies

Wanneer men zich exact onder een vaste node bevindt, zullen de padverliesmodellen −∞ voorspellen en zal deze locatie nooit als meest waarschijnlijke positie worden gekozen. Met de mobiele ZigBee node werd onder 5 vaste nodes gebroadcast om het minimale experimentele padverlies te bepalen, uitgemiddeld kwam dit neer op 47.1 dB (waarbij de ideale shift al is doorgevoerd). De nauwkeurigheid en spreiding werd voor alle testpaden, afgelegd met de mobiele ZigBee node, opnieuw berekend (met dezelfde instellingen uit Tabel 6.3) en vergeleken met het geval zonder ondergrens op de referentiepadverliezen (PLref ), zie Tabel 6.11. Tabel 6.11: Nauwkeurigheid en spreiding zonder en met ondergrens voor PLref Algoritme →

Simpel

Viterbi Huidig

Viterbi

Minimum PL ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

Zonder ondergrens

2.94

3.32

2.83

1.94

2.26

1.44

Met ondergrens

2.89

3.29

2.67

1.85

2.31

1.46

Er is verbetering bij Simpel en Viterbi Huidig maar deze blijft wel miniem, dit is deels te verklaren door de roosterpuntresolutie van 1 m waardoor de kans al klein is dat het te traceren object zich exact onder een vaste node bevindt.

6.7.10

Kostfunctie

In het lokalisatiealgoritme werd tot nu toe steeds de MSE tussen de gemeten en de referentiepadverliezen gebruikt als kostfunctie. Een andere mogelijkheid is het gemiddelde verschil in


41

absolute waarde:

ABS =

N 1 X |P Lgem,n − P Lref,n | N

(6.1)

n=1

Hierbij is ABS de absolute waarde, N het totaal aantal metingen, PLgem,n het gemeten padverlies van een vaste node n en PLref,n het referentiepadverlies van een vaste node n. Nog een optie is om het verschil tussen het gemeten en het referentiepadverlies nog eens te delen door het padverlies zelf zodat metingen met een lager padverlies zwaarder door wegen:

MSEgewogen

N 1 X (P Lgem,n − P Lref,n ) 2 = N P Lgem,n

(6.2)

n=1

Hierbij is MSEgewogen de gewogen Mean Square Error en zijn de overige parameters hetzelfde als bij de absolute waarde als kostfunctie. De resultaten, uitgemiddeld over alle negen testpaden en met de instellingen van Tabel 6.3, kunnen worden teruggevonden in Tabel 6.12. Tabel 6.12: Nauwkeurigheid en spreiding voor verschillende kostfuncties Algoritme →

Kostfunctie ↓

Simpel

Viterbi Huidig

Viterbi

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

MSE

2.94

3.32

2.83

1.94

2.26

1.44

Absolute Waarde

3.15

3.44

2.89

1.96

2.24

1.39

Gewogen MSE

2.94

3.31

2.86

1.91

2.24

1.42

Het valt meteen op dat er geen significante verschillen zijn tussen deze 3 kostfuncties.

6.7.11

Open en gesloten deuren

Tot nu toe werden alle deuren op het grondplan gemodelleerd als gesloten, uit hout gemaakte, deuren. Het grondplan kan nog worden aangepast aan de situatie tijdens het afleggen van de testpaden: deuren die open stonden, werden gemodelleerd met een 0 dB lijn voor accuratere predicties van de padverliezen. In deze sectie wordt de impact hiervan onderzocht, opnieuw door de gemiddelde nauwkeurigheid en spreiding van alle negen testpaden in de twee gevallen te berekenen (met de instellingen van Tabel 6.3). De resultaten staan samengevat in Tabel 6.13. Het aangepast grondplan heeft gemiddeld gezien een hogere nauwkeurigheid en spreiding maar het verschil blijft klein.

6.8 Globaal optimum

42

Tabel 6.13: Aangepast grondplan Algoritme →

6.8

Simpel

Viterbi Huidig

Viterbi

Grondplan ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

Gesloten deuren

2.94

3.32

2.83

1.94

2.26

1.44

Aangepast aan situatie

3.0

3.57

2.75

1.86

2.18

1.36

Globaal optimum

Wanneer voor elke parameter de waarde wordt gekozen, die in de sensitiviteitsanalyse meest ideaal bleek, verkrijgen we de instellingen van in Tabel 6.14. Er wordt dus niet alleen naar de nauwkeurigheid gekeken maar ook naar de minimale uitvoeringstijd die deze nauwkeurigheid kan halen. De uiteindelijke nauwkeurigheid en spreiding (uitgemiddeld over alle testpaden) voor zowel het free-space als het WHIPP padverliesmodel en voor zowel de mobiele ZigBee als WiFi node staan samengevat in Tabel 6.15. De procentuele verbeteringen van Viterbi ten opzichte van Simpel en WHIPP ten opzichte van free-space, uitgemiddeld over de mobiele ZigBee en WiFi node, kunnen worden teruggevonden in Tabel 6.16. Tabel 6.14: Globaal optimale instellingen Instelling

ZigBee

WiFi

maxSnelheid

1.67 m/s

1.67 m/s

sampleRate

1 sample/s

2.5 sample/s

minDistDoor

2m

2m

aantalAPs

10

16

aantalPaden

100

100

aantalLevels

5

5

interDist

1m

1m

minPL

47.1 dB

47.1 dB

kostfunctie

MSE

MSE

aangepast grondplan

ja

ja

Zoals verwacht levert het ontwikkelde lokalisatiealgoritme zowel bij het WHIPP als free-space padverliesmodel betere resultaten op voor zowel de nauwkeurigheid als de spreiding, er is zelfs een verbetering van 59% bij deze laatste. Onderling is de verbetering ten opzichte van Simpel voor Viterbi groter dan deze van Viterbi Huidig, wat ook te verwachten was. Door gebruik te maken van het geavanceerde padverliesmodel (WHIPP) is er altijd verbetering van de nauwkeurigheid ten opzichte van het free-space padverliesmodel. Bij Viterbi en Viterbi

6.8 Globaal optimum

43

Tabel 6.15: Globaal optimum Algoritme →

Padverliesmodel ↓ WHIPP free-space

Simpel

Viterbi Huidig

Viterbi

Mobiele node ↓

N [m]

S [m]

N [m]

S [m]

N [m]

S [m]

ZigBee

2.96

3.63

2.58

1.7

2.18

1.31

WiFi

3.38

3.13

2.45

1.69

2.2

1.46

ZigBee

3.45

3.4

3.04

1.87

2.61

1.5

WiFi

3.59

2.12

3.46

2.03

3.35

1.96

Tabel 6.16: Procentuele verbeteringen Verbetering van ↓

ten opzichte van ↓

bij ↓

Nauwkeurigheid [%]

Spreiding [%]

Viterbi

Simpel

WHIPP

31

59

Viterbi

Simpel

free-space

16

32

Viterbi Huidig

Simpel

WHIPP

20

50

Viterbi Huidig

Simpel

free-space

8

25

WHIPP

free-space

Viterbi

25

19

WHIPP

free-space

Viterbi Huidig

22

13

WHIPP

free-space

Simpel

10

-27

WHIPP + Viterbi

free-space + Simpel

ZigBee

37

61

WHIPP + Viterbi

free-space + Simpel

WiFi

39

31

Huidig verbetert ook de spreiding op de resultaten maar bij Simpel gaat deze er wel op achteruit. Maximale verbetering wordt verkregen bij het vergelijken van de combinatie van WHIPP als padverliesmodel met Viterbi als lokalisatiealgoritme ten opzichte van free-space met Simpel : 37 % nauwkeuriger en 61 % minder spreiding op deze nauwkeurigheid.

TOEKOMSTIG WERK

44

Hoofdstuk 7

Toekomstig werk 7.1

RSSI alternatieven

De principes waarop het algoritme gebaseerd zijn, staan los van de gebruikte rangingtechniek. Zoals reeds aangehaald in Sectie 2.1.1, kan in de plaats van RSSI ook (D)ToA, (D)AoA of een hybride techniek worden gebruikt. De fingerprintdatabase zal eveneens moeten worden aangepast aan de gebruikte rangingtechniek, dus het behaalde voordeel met het WHIPP padverliesmodel valt weg. Maar voor de meeste rangingtechnieken zijn er wel padverliesmodellen beschikbaar.

7.2

ZigBee en WiFi alternatieven

Vooral UWB lijkt veelbelovend om de nauwkeurigheid van indoorlokalisatiesystemen op te drijven. Net zoals hierboven reeds het geval was, is de werking van het algoritme ook onafhankelijk van de gebruikte draadloze technologie. Het testen op een testbed met ondersteuning voor deze nieuwe technologieën lijkt dan ook veelbelovend.

7.3

A-priori kennis

Tot nu toe werd het verleden van een traject gebruikt om de meest waarschijnlijke sequentie van locaties en eveneens een realistisch traject te bepalen. Wanneer men beschikt over voldoende data van waarschijnlijke trajecten, kan men hier distributies voor modelleren en kan het verleden van het huidige traject hieraan worden gematcht. Deze (statistische) a-priori kennis kan dan bijvoorbeeld gewogen in rekening worden gebracht, om zo de nauwkeurigheid van de voorspelling te verbeteren.

7.4 Ruis en outlierfiltering

7.4

45

Ruis en outlierfiltering

Aangezien het verleden van een traject beschikbaar is, kan men nieuwe meetwaarden vergelijken met deze uit de fingerprintdatabase die overeenkomen met de laatste locatie. Wanneer het verschil tussen deze twee een bepaalde threshold overschrijdt, is de kans groot dat het om een outlier of een met ruis behepte meting gaat. Vervolgens kan er minder belang worden gehecht aan deze meting of kan deze zelfs compleet worden genegeerd indien er voldoende andere metingen beschikbaar zijn. Indien de vorige locatie niet overeenkwam met de werkelijkheid, werkt deze manier van filtering natuurlijk averechts, dus het algoritme kan best eerst stabiliseren en dan na een bepaald aantal tijdstappen kan deze techniek worden ingeschakeld.

7.5

Meerdere verdiepingen

Het ontwikkelde lokalisatiealgoritme is enkel ge¨ımplementeerd voor de werking op één verdieping maar kan makkelijk worden uitgebreid naar alle verdiepingen van een gebouw. Tot nu toe werden de deuren gebruikt om de overgang tussen twee kamers te verwezenlijken, de locatie van een lift kan deze werking overnemen voor naar een andere verdieping te gaan. Bijkomend kunnen ook de vaste nodes van meerdere verdiepingen tegelijk worden gebruikt, zodat er meer metingen beschikbaar zijn en de prestaties verder kunnen worden verbeterd.

7.6

Inbedding in indoornavigatiesysteem

Om het ontwikkelde lokalisatiealgoritme echt tot zijn nut te laten komen, kan het worden ingebed in een indoornavigatiesysteem dat bijvoorbeeld compatibel is met een smartphone. De smartphone zal dan de rol van tracking en processing device op zich nemen, dus zowel het zenden van beacons als het verwerken van de data. Met het ontwikkelde algoritme kan dan de beste huidige locatie worden bepaald om zo instructies te kunnen geven aan de gebruiker om te navigeren naar een opgegeven plaats in het gebouw. Indien dit teveel zou eisen van de batterij van de smartphone, kan er ook voor worden geopteerd om bijvoorbeeld een extern tracking device te gebruiken en de smartphone enkel als thin client aan te wenden waarbij het ontwikkelde algoritme op een server draait en locatieupdates of navigatie instructies via een mobiele applicatie naar de gebruiker kunnen worden gestuurd. Indien dit zou werken, kan het eveneens worden gebruikt om data te loggen om zo distributies te modelleren van waarschijnlijke trajecten die dan kunnen worden gebruikt om de voorspelling te verbeteren zoals vermeld in Sectie 7.3.

CONCLUSIE

46

Hoofdstuk 8

Conclusie In deze masterproef werd een indoorlokalisatiesysteem ontwikkeld dat in ware tijd werkt. Door het verleden van een traject in rekening te brengen, kunnen de prestaties van een (willekeurig) lokalisatiealgoritme worden verbeterd, zowel de nauwkeurigheid als de spreiding. Verder werd er aangetoond dat het ontwikkelde lokalisatiealgoritme ook robuuster is tegen variaties op de metingen ten opzichte van een standaard lokalisatiesysteem en dat er met een beperkt aantal vaste nodes in een gebouw al een goede nauwkeurigheid kan worden behaald, dit is interessant om de installatiekosten te beperken. Een ander voordeel is dat er voor het opzetten van het indoorlokalisatiesysteem in een (nieuw) gebouw maar weinig extra tweaking nodig is, zodat het snel toepasbaar is. Het eenmalig kalibreren van de padverliezen volstaat, wel is er nood aan een (gedetailleerd) grondplan. In een uitgebreide sensitiviteitsanalyse werd de invloed van alle parameters op de prestaties onderzocht, zodat voor een zekere toepassingen bepaalde afwegingen eenvoudig kunnen worden gemaakt. Naast het in rekening brengen van het verleden van een traject werd ook voor gezorgd dat de geconstrueerde paden realistisch (fysisch mogelijk) zijn, door gebruik te maken van de omgeving en een maximale snelheid waarmee een te traceren object zich kan voortbewegen. Bovendien biedt de werking in ware tijd, de mogelijkheid om het ontwikkelde indoorlokalisatiesysteem te inbedden in een navigatiesysteem.

BIBLIOGRAFIE

47

Bibliografie [1] Nicolas Amiot, Meriem Mhedhbi, Stphane Avrillon, and Bernard Uguen. Pylayers: An indoor propagation tool for studying localization in wban context. http://www.pylayers. org, 2014. [2] Richa Bharadwaj, Clive Parini, and Akram Alomainy. Indoor tracking of human movements using uwb technology for motion capture, 2014. [3] Stefan Bouckaert. Design and evaluation of a self-configuring wireless mesh network architecture. PhD thesis, Ghent University, 2010. [4] Stefan Bouckaert, Wim Vandenberghe, Bart Jooris, Ingrid Moerman, and Piet Demeester. The w-ilab. t testbed. In Testbeds and Research Infrastructures. Development of Networks and Communities, pages 145–154. Springer, 2011. [5] Andrea Conti, Matteo Guerra, Davide Dardari, Nicolo Decarli, and Moe Z Win. Network experimentation for cooperative localization. Selected Areas in Communications, IEEE Journal on, 30(2):467–475, 2012. [6] Moteiv Corporation. Ultra low power ieee 802.15.4 compliant wireless sensor module. http: //www.crew-project.eu/sites/default/files/tmote-sky-datasheet.pdf, 2006. [7] Vinko Erceg, Larry J Greenstein, Sony Y Tjandra, Seth R Parkoff, Ajay Gupta, Boris Kulic, Arthur A Julius, and Renee Bianchi. An empirically based path loss model for wireless channels in suburban environments. Selected Areas in Communications, IEEE Journal on, 17(7):1205–1211, 1999. [8] Sinan Gezici, Zhi Tian, Georgios B Giannakis, Hisashi Kobayashi, Andreas F Molisch, H Vincent Poor, and Zafer Sahinoglu. Localization via ultra-wideband radios: a look at

BIBLIOGRAFIE

48

positioning aspects for future sensor networks. Signal Processing Magazine, IEEE, 22(4):70– 84, 2005. [9] Akis Kokkinis, Marios Raspopoulos, Loizos Kanaris, Antonio Liotta, and Stavros Stavrou. Map-aided fingerprint-based indoor positioning. In Personal Indoor and Mobile Radio Communications (PIMRC), 2013 IEEE 24th International Symposium on, pages 270–274. IEEE, 2013. [10] Hui Liu, Houshang Darabi, Pat Banerjee, and Jing Liu. Survey of wireless indoor positioning techniques and systems. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 37(6):1067–1080, 2007. [11] Paul Meissner, Erik Leitinger, Manuel Lafer, and Klaus Witrisal. Real-time demonstration of multipath-assisted indoor navigation and tracking (mint), 2014. [12] David Munoz, Frantz Bouchereau Lara, Cesar Vargas, and Rogerio Enriquez-Caldera. Position location techniques and applications. Academic Press, 2009. [13] David Plets, Wout Joseph, Kris Vanhecke, Emmeric Tanghe, and Luc Martens. Coverage prediction and optimization algorithms for indoor environments. EURASIP Journal on Wireless Communications and Networking, 2012(1):1–23, 2012. [14] Alessandro Polo, Federico Viani, Enrico Giarola, Giacomo Oliveri, Paolo Rocca, and A. Massa. Semantic wireless localization enabling advanced services in museums, 2014. [15] Zoltan Szalay and Lajos Nagy. Indoor localization using ism band radio modules, 2013. [16] Andrew J Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. Information Theory, IEEE Transactions on, 13(2):260–269, 1967. [17] Xinwei Wang, Ole Bischoff, Rainer Laur, and Steffen Paul. Localization in wireless ad-hoc sensor networks using multilateration with rssi for logistic applications. Procedia Chemistry, 1(1):461–464, 2009. [18] Klaus Witrisal and Paul Meissner. Performance bounds for multipath-assisted indoor navigation and tracking (mint). In Communications (ICC), 2012 IEEE International Conference on, pages 4321–4325. IEEE, 2012.

LIJST VAN FIGUREN

49

Lijst van figuren 3.1

Grondplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2

Roosterpuntresolutie van 1 m . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.3

Eenvoudig voorbeeld Viterbi principe . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.4

Realistischer traject door toevoegen midden deur . . . . . . . . . . . . . . . . . .

11

3.5

Mogelijke volgende posities bij een bepaalde maxSnelheid en sampleRate . . . . .

12

3.6

Extra beginposities toevoegen voor robuustheid tegen foute initiële predictie . . .

13

5.1

Derde verdieping van het w-iLab.t testbed . . . . . . . . . . . . . . . . . . . . . .

20

5.2

Mobiele nodes (links WiFi, rechts ZigBee en batterij) . . . . . . . . . . . . . . . .

21

5.3

Visualisatie van de drie soorten trajecten . . . . . . . . . . . . . . . . . . . . . .

23

6.1

Testpaden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

6.2

Visualisatie van testpad 1 onder verschillende omstandigheden (links Simpel, rechts Viterbi ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

6.3

Invloed van ruis op nauwkeurigheid (simulatie) . . . . . . . . . . . . . . . . . . .

33

6.4

Sensitiviteitsanalyse van aantalAPs . . . . . . . . . . . . . . . . . . . . . . . . . .

34

6.5

Scenario’s met verschillend aantal werkende vaste nodes uit het testbed . . . . .

35

6.6

Invloed van geheugen op prestatie . . . . . . . . . . . . . . . . . . . . . . . . . .

36

6.7

Uitvoeringstijd in functie van de parameter aantalPaden . . . . . . . . . . . . . .

37

6.8

Invloed van sample rate en uitmiddeling op nauwkeurigheid . . . . . . . . . . . .

38

LIJST VAN TABELLEN

50

Lijst van tabellen 2.1

Rangingtechnieken en draadloze technologieën . . . . . . . . . . . . . . . . . . . .

4

4.1

Parameterwaarden one-slope padverliesmodel . . . . . . . . . . . . . . . . . . . .

17

4.2

Parameterwaarden TGn padverliesmodel . . . . . . . . . . . . . . . . . . . . . . .

18

4.3

Uitvoeringstijden offline-fase voor alle padverliesmodellen . . . . . . . . . . . . .

19

5.1

Ideale shift voor de vier padverliesmodellen . . . . . . . . . . . . . . . . . . . . .

22

5.2

Verklaring types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

6.1

Eigenschappen testpaden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

6.2

Vergelijking vier padverliesmodellen . . . . . . . . . . . . . . . . . . . . . . . . .

27

6.3

Instellingen lokalisatiealgoritme . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

6.4

Vergelijking ZigBee met WiFi als draadloze technologie . . . . . . . . . . . . . .

28

6.5

Combinatie ZigBee en WiFi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

6.6

Nauwkeurigheid en spreiding van de visualisaties uit Figuur 6.2 . . . . . . . . . .

31

6.7

Reproduceerbaarheid van de resultaten . . . . . . . . . . . . . . . . . . . . . . . .

31

6.8

Nauwkeurigheid en spreiding voor de verschillende scenario’s . . . . . . . . . . .

36

6.9

Nauwkeurigheid en spreiding bij verschillende snelheden en uitmiddeling . . . . .

39

6.10 Nauwkeurigheid en spreiding bij verschillende zendvermogens en scenario’s . . . .

40

6.11 Nauwkeurigheid en spreiding zonder en met ondergrens voor PLref . . . . . . . .

40

6.12 Nauwkeurigheid en spreiding voor verschillende kostfuncties . . . . . . . . . . . .

41

6.13 Aangepast grondplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.14 Globaal optimale instellingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.15 Globaal optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

6.16 Procentuele verbeteringen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Ontwikkeling van een indoorlokalisatiesysteem op basis van het Viterbi-algoritme

Recommend Documents