04.03.2010Prof. Dr. H. Ingensand Geodätische Messtechnik und Ingenieurgeodäsie

Innenraumpositionierung mit dem Cricket-System

(Indoor Positioning using Crickets)

Rainer Mautz

Freitag, 05. März 2010, 8:30 HIL C 71.3

Projektarbeit Bachelorstudiengänge D-BAUGInstitute of Geodesy and Photogrammetry (IGP)

Der Kurs besteht aus eigenständiger Arbeit an einem Projekt. Die Durchführung findet in Gruppen von 4 Studenten statt.

Leitung: Hilmar Ingensand HIL D 47.2

Organisation, Übungen:

Rainer Mautz (Hauptansprechpartner)D 45.2 mautz@geod.baug.ethz.ch 044 633 78 27

Pascal Theiler46.2 theilerp@geod.baug.ethz.ch 044 633 30 39

Organisation

Weitere ETH-Ansprechpartner:

Tobias Kohoutek kohoutek@geod.baug.ethz.ch 044 633 3041(Mindstorms Roboter)

Paul Sorber (Elektronik)C 61.3 sorber@geod.baug.ethz.ch 044 633 68 51

Hanspeter Oesch (Messlabor)HIL C 61.1 oesch@geod.baug.ethz.ch 044 633 36 01

Jules Fenner (Vermessungsmaterial)HIL C 61.1 fenner@geod.baug.ethz.ch 044 633 30 57

Organisation

Anwesenheit: Pflichtveranstaltung an den folgenden Terminen Fr 5.3., Fr 12.3., Fr 19.3., Fr 26.3., Fr 23.4., Fr 4.6.Die übrigen Freitage stehen als Sprechstunde und zur Arbeit an den Projekten zu Verfügung.

Examen:kein Examen, jedoch Vorführung des Projektes und Abgabe eines Posters und Kurzberichtes (max.12Seiten).

Dokumente: Alle Informationen befinden sich im Web unter: http://www.geometh-data.ethz.ch/projektarbeit_basisjahr/

Organisation

Organisation

Organisation

Freitag, 5.3.2010 8:30-12 UhrEinführungsveranstaltungVorlesung und Einführung in Wireless Networks, Installation der Cricket

Software : Hyperterminal, MatlabBetreuer: Rainer Mautz

13-17 Uhr:Bestimmung von Positionen aus Distanzmessungen Betreuer: Pascal Theiler

2. Woche Fr 12.3.2010 Anbringen von einigen Crickets an die Decke des Raums HIL C 71.3.

Geodätische Einmessung der Crickets (Messband + Lot oder Tachymeter)

Organisation

Herausforderung - Cricket

Anwendung des Cricket Systems

-500

50100

-50

0

50-50

0

50

Z

01

Clustersize: 5 nodes

07

06

04

08

Herausforderungen:

Installation eines Positionierungssystems

Berechnung der 3D Positionen aus Streckenmessungen

Visualisierung der Bewegungen

Kreativität gefordert für mögliche Anwendungen:

z.B. Verfolgung eines Roboters

Aufgabe und Lerneffekte

- Verständnis von drahtloser Positionierung

- Einblick in die englischsprachige Literatur

- Einmessung von Punkten mit konventionellen Methoden, Einsicht dass die Navigation bekannte Referenzpunkte (Satelliten, Ankerpunkte, Beacons) erfordert

- Problematik der Streckenmessung mittels Zeitlaufverfahren

- Installation von Software – professionelle (MATLAB) aber auch Bastelsoftware

- Verkabelte und unverkabelte Kommunikation verschiedener Geräte (PC, Cricket, WLAN, Bluetooth)

- Protokolle(TPC/IP) und Schnittstellen (RS323 – USB – COM-Port)

- Realisierung eines Systems, tiefere Auseinandersetzung mit den technischen, softwaretechnischen und prinzipiellen Zusammenhängen

- Weiterentwicklung des Systems: mittels eigenem Projekt Verbesserung der Funktionalität (z.B. durch Eichung, Erfassung von Systematiken) oder Entwicklung neuer Funktionalitäten (Roboter oder mobiles Gerät, dessen Kenntnis der Position genutzt wird).

Positionierung im Aussenraum

Navigation mit Hilfe von Satelliten: GPS, GLONASS

Streckenmessung zwischen Satellit und Empfänger

Alternativen für Innenräume?

Welche Möglichkeiten gibt es zur Indoor-Positionierung?

Wireless Positioning Technologies using existing infrastructure

Assisted/Aided-GNSS (A-GNSS, A-GPS)

“Hot Start” all data for a fix handy – except ranges

High power needs for high sensitivity GPS and relatively high costs

Critical Issues: Assistance Data Persistance versus Maximum Tolerable Latency

Introduction in Wireless Positioning

• Global System for Mobile Communication (GSM) can be used for positioning. Accuracies using (Methods: GCI or TA), e.g. 100m up to 10km

• Wireless Local Area Network (WLAN): Cell sizes 35-50m, Predicted Accuracy: few meters, Signal Strength Methods not reliable, need to relocate and ad access points for overlap

Positioning Technologies using existing infrastructure

Introduction in Wireless Positioning

Indoor Positioning – Wozu?

- Informationsdienste (Location Based Services)

- Tracking von Objekten (Produkte in Industrieanlagen, Facility Managment)

- Automatisierung (Robotersteuerung, Umgebungssteuerung)

- Sensor Netzwerke

- Fußgänger Navigation (Krankenhäuser, Feuerwehr, Sehbehinderte)

- Augmented Reality (Einblendung von Zusatzinformationen, Gaming)

- Messsystem

Systeme zur Indoor-Lokalisierung

• Basisverfahren:

Tracking: Benutzer trägt eine Marke (Bat oder Badge), die von einem Sensornetz erkannt und verfolgt wird

Positioning: das Endgerät (Listener) empfängt Signale von einem Sendern (Beacons) und berechnet seine aktuelle Position selbst

Indoor-Positionssysteme

Infrarot

• Active Badge

• WIPS

Funk Ultraschall visuell

• RFID

• Spot On

• Bluetooth

• Active Bat

• Cricket

• visual

04.03.2010Prof. Dr. H. Ingensand Geodätische Messtechnik und Ingenieurgeodäsie

Bewertung der Verfahren

Erreichbare Genauigkeit

Skalierbarkeit

Active Badge Raum Sensoren-Netzwerk; ein Sensor pro Zimmer, ein Badge pro Person

WIPS Raum Ein Sender pro Zimmer, ein Empfänger pro Person

SpotOn 3m Aktive RF-ID-Tags und -Leser

Bluetooth 2m Bluetooth-Geräte im max. Abstand von 8m

Active Bat 10cm Sensoren-Netzwerk, Bats

Cricket 1-2 cm beliebig, z.B. Sensor pro 1,44m2

von: Irene Ehrlich, Wirtschaftsinformatik Münster

Beispielanwendung

A screen shot of an interactive version of the Doom game

Cricket

System aus batteriebetriebenen „Grillen“ die mit Ultraschall und Radiosignalen ihre gegenseitigen Distanzen bestimmen

Time Difference Of Arrival (TDOA) Methode

Entwicklung des MIT

Hersteller: Crossbow Technologies

10 + 5 Netzknoten vorhanden

Reichweite: ca. 10m

Streckengenauigkeit : ca. 1 - 2 cm

Cricket Netzknoten

Installiertes Cricket System

Cricket Unit

Messprinzip und Parameters von Cricket

Cricket consists of location beacons that are attached to the ceiling of a building,

and receivers, called listeners, attached to devices that need location.

Each beacon periodically transmits information in an RF message.

At the same time, the beacon also transmits an ultrasonic pulse. The listeners listen to beacon transmissions and measure distances to nearby beacons,

This active-beacon passive-listener architecture is scalable with respect to the number of users, and preserves user privacy.

System Parameters:Beacon frequency 1 HzRF frequency 436 MHzRF transmit power -3 dBm (typical for indoor environment)RF data rate 19.2 kbpsUS frequency 40 KHzUS pulse duration 150 µs

The listener must be attached to an RS232 serial interface configured as follows:

Transmission speed 115200 bits/second Data format 8 bits, no parity Flow control Xon/Xoff (“software”) Stop bits 1

Once the beacon or the listener is attached to a host, commands can be issued using a standard serial port utility such as HyperTerminal.

Communication with a Cricket Node

Distance Measurement Techniques

Time-of-flight (TOF)

This technique measures the time t taken for some signal to traverse the path between two points (the reference point and the object). If the speed of the signal is v, the distance d is given by

d = v * t.

For example, GPS uses the time of flight of RF signals to estimate the distance between GPS satellites and the GPS receiver.

Time-Difference-of-Arrival (TDOA)

TDOA-based schemes measure the distance between given two points using two signals with different speeds that traverse the same path between the two points.

Cricket uses TDOA of RF and ultrasonic signals to measure distance to the reference points.

Consider two signals A and B with speeds vA and vB sent simultaneously by a transmitter. If vA > vB, then signal B lags behind signal A as they propagate. Let t denote this time lag at a receiver located at a distance d from the transmitter.

Distance Measurement Techniques

At normal room temperature and humidity, the speed of sound, vus ≈ 344 m/s, and speed of light, vrf ≈ 3 × 108 m/s.

vRF << vUS, d ≈ Δt · vus

In completely dry air with no humidity, the speed of sound (in meters per second) depends mostly on the absolute temperature T (in Kelvin), and is given by

vUS = SQRT(20.05 T).

The speed of sound (and the measured distance) changes by ≈ 0.18% per degree Celsius

Each Cricket measures temperature; use t = (tA + tB ) / 2. Accuracy of ±10C.

Distance Measurement Techniques

distance measurement error as a function of the distance angle to each other

Calibration of Distance Measurements

Warum müssen die Crickets (Beacons) eingemessen werden?

Koordinaten der Ankerpunkte Beacons werden benötigt, um mittels Strecken die Position des Listernes zu rechenen

Wie ermittelt man die Koordinaten der Ankerpunkte? GPS steht in Innenräumen leider nicht zur Verfügung. Die Bestimmung der Beacon-Koordinaten muss eine Magnitude genauer sein als das Cricket System (1-2 mm).

Die Ankerpunkte (Beacons)

Localisation Problem

Given a set of ranges between nodes, positions and variances need to be calculated.

Basic principle: 3D-Trilateration

Given: Coordinates of 3 known points P1, P2, P3 and 3 ranges r1, r2, r3 to the unknown Point P

solve for : P (x, y, z)

( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) 2

32

32

32

3

22

22

22

22

21

21

21

21

rzzyyxx

rzzyyxx

rzzyyxx

=−+−+−

=−+−+−

=−+−+−

P1

P2

P3 P

Trilateration

Ambiguity and Singularity Problems

Examples:

a) Nodes with 3 ranges

- mirroring ambiguity position for P

- no redundancy and reliability of position

b) Anchor nodes collinear (3D: in one plane)

c) Error budget to high to allow lateration

d) Nodes with only connectivity information

P1

P2P3

P?

P?

P is on either side of the plane P1,P2,P3

P1 P2 P3

P?

Mehrdeutigkeitsproblem

Principle of Wireless Positioning: Multi-Lateration

known node

unknown node

range measurement

Multilateration

Lateration Methods

Multilateration:

Initial anchor

Step 1:

Step 2:

Step 3:

becomes anchor

becomes anchor

becomes anchor

Iterative Multilateration:

Collaborative (n-hop) Multilateration:

Multilateration in Netzen

Connectivity (degraded) Mode

P?

P1 P2

2D bounding box:

Unterbestimmung bei zu wenigen Messungen

1

32

4

5

1

32

4

5’

1

32

4

5(a) (b) (c)

1

32

4

5

1

32

4

5’

1

32

4

5(a) (b) (c)

Ambiguity problem when creating the smallest rigid structure

Positioning Using Ad-hoc Communication

d45 - d45’

1

3

2

4

5

5’

d55’

r45

d45 - d45’

1

3

2

4

5

5’

d55’

r45

Solving flip ambiguity in the presence of noise

Positioning Using Ad-hoc Communication

Method to Create Anchor Nodes

known mobile node

unknown static nodes

t1t2

Dynamic Positioning

unknown mobile node

unknown static nodes

t1

t2

Mobile Assisted Positioning

Dynamic Positioning

Verteilung der Referatsthemen:

1.Möglichkeiten zur Ankerpunktbestimmung (z.B. Mobile Assisted, Manuell, Freie Netze) Wie viele Ankerpunkte sind notwendig und welche Geometrie ist günstig?

2. Streckenmessung mit Ultraschall und Radiosignalen, Einflussgrößen, Kalibrierung T,p,e, Distanzmessung mit Crickets, TDOA

3. Systemarchitektur von Crickets - Software und Hardware Komponenten

4. Prinzipien und aktueller Stand der satellitengestützten Positionierungssysteme und Alternativen – wo lässt sich Crickets einordnen?

Referate folgen am Freitag in 2 Wochen

Jede Gruppe von 4 Studierenden hat jeweils 45 Minuten Zeit das jeweilige Thema zu referieren. Ein Thema sollte so geteilt werden, dass jeder Referent ca. 10-15 Minuten vorträgt. Anschliessend Fragerunde

Referate - Informationen

Themenvorschläge für Projektarbeit

Realisierung eines dynamischen „Listeners“ z.B.

Modellbagger (Baumaschinensteuerung),

Planierraupe (Baumaschinensteuerung),

Roboter (Lego Mindstorms Roboter System RCX 1.5 und NXT, Sony Roboterhund Aibo),

nachführendem Tachymeter (Absolute Positionierung)

Roboter-Staubsauger (Wegoptimierung durch automatischer Steuerung)

ferngesteuertes Fahrzeug (Tracking)

Aufbau eines Distanz- und Positionmesssystems durch Cricket-Pointer

Automatische Ansteuerung des Mobilen „Listeners“ über Funkmodule mittels Steuerbefehlen vom Laptop.

Themenvorschläge für Projektarbeit

Weitere Themen:

Kalibrierung des Systems

Klimakammer, Interferometerbahn, Distanzkalibrierung mit überbestimmtem System d.h. mehr Beacons als notwendig, Untersuchung des Systems auf Abhängigkeit von Wind und Temperatur

Eliminierung grober Fehler bei der Distanzmessung (Multipath)

Berechnung der 3D Positionen aus eintreffenden Laufzeitmessungen vom „Listener“ (theoretisch-geometrische Überlegungen), Darstellung der Positionen in Realtime (Tracking)

Untersuchung der räumlichen Keule der Signale zur Streckenmessung, Ermittlung der Additionskonstante – auf der Messbahn oder mit Messband oder mit Nivellierlatten auf Stativen (z.B. 4 -5 Distanzkombinationen), Untersuchung auf streckenabhängige Systematik, Temperaturabhängigkeit (Klimakammer), lineare Regression

Datenübertragung mit WLAN oder Bluetooth

Mobil-Telefon Positionierung, A-GPS Positionierung

Literatur: http://www.geometh-data.ethz.ch/projektarbeit_basisjahr/

Cricket v2 User Manual http://cricket.csail.mit.edu/ Wireless Sensor Networks – Getting Started Guide, Rev. A,

September 2005, Crossbow Technology Nissanka Bodhi Priyantha, The Cricket Indoor Location System,

PhD Thesis at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY June 2005

Die gefährlichen Örter der Pseudostreckenortung von Thomas Alexander Wunderlich DGK Nr.190

Lorenz Moser, “Weiterentwicklung eines Simulators für die Positionierung in wireless ad hoc Netzwerken”, Semesterarbeit, Tutor: Jan Beutel, Supervisor: Prof. Dr. Lothar Thiele, ETHZ, Institut für Technische Informatik und Kommunikationsnetze, 2002

Literatur

The command format is: <directive> <command> <parameters>

<directive> “G” for “get” and “P” for “put”.

Configure a Cricket unit to be a beacon 1. Type P MD 1 <return> (P MD 2 configures cricket at a listener) 2. Type P SP Beacon4 <return> to set the beacon’s space ID to

“Beacon4” (or to any other string). The maximum length of the space ID is 8 bytes.

3. Type G CF <return> to check the current configuration; you should find the new space ID and the beacon setting.

4. Save the new configuration to the flash by sending P SV <return>. If you don’t save the configuration, the new settings will only remain until the Cricket unit is powered off.

Communication with a Cricket Node

G CF<return> Result: Cricket configuration: Software version: 2.0 // Cricket software version Mode: Listener / / Running mode (Listener/Beacon) Unique id: 1:c8:6a:b3:a:0:0:dc // Unique Cricket ID Space id: BEACON6 // User-defined space ID Uptime: 16:32:14 // Uptime of Cricket from last power cycle Ultrasound attenuation time(us): 45000 // Time for ultrasound to attenuate Timer Offset(us): 550 // Offset processing time Minimum beacon interval(ms): 668 // Minimum wait time between messages Maximum beacon interval(ms): 1332 // Maximum wait time between messages

Get Cricket Configuration

Average beacon interval(ms): 1000 // Average interval between beacon messages

Compensation value(µs): 48 // Time data to travel over the Cricket radio Distance Units: Metric // Units used to display (DB) Local temperature value: disabled // Temperature from the onboard sensor Speed of sound value(m/s): not used // Speed of sound based on temperature Test switch status: On // Position of the test switch on the Cricket Event output format: 3 // Event reporting format Output variable(s): VR ID DB DR SP TM TS // Variables output

VR = Software VersionID = Unique Node IDDB = Distance [cm]DR = Duration [msec]SP = Space ID (user defined)TM = Time of flight (without temperature comensation)TS = System Timesee Cricket Manual Page 22

Cricket Configuration

1. Connect and turn on a Cricket configured as a listener to your host.2. Turn on a Cricket configured as a beacon.3. You should now see distance measurements appear in your terminal

every time the listener hears from the beacon. The output has many fields; the “DB” field gives the distance to the beacon. The default units are centimeters

4. Make sure both Crickets are turned on and the test switch is off

Example Message:VR=2.0,ID=01:dd:be:be:09:00:00:95,SP=BE-2,DB=224,DR=6479,TM=6789,TS=455424

If the above steps work, you can now use your Crickets to write and run applications!

Test distance measurements