Dynamic Location Discovery in Ad Hoc Networks

Slide1http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 1 Dynamic Location Discovery in Ad-Hoc Networks Andreas Savvides, Athanassios Boulis and Mani B. Srivastava (asavvide,boulis,mbs@ee.ucla.edu) Networked and Embedded Systems Lab(NESL) http://nesl.ee.ucla.edu Electrical Engineering Department Session 7

Slide2http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 2 What is location discovery? • Given a network of sensor nodes where a few nodes know their location how do we calculate the location of the nodes? Known Location Unknown Location

Slide3http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 3 Why? • Support Location Aware Applications • Navigation • Track Objects • Sensor Networks  – report event origins – evaluate network coverage – assist with routing

Slide4http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 4 Basic Concepts • Distance measuring methods – Signal Strength • Uses RSSI readings and wireless propagation model – Time based methods • ToA, TDoA • Used with radio, IR, acoustic, ultrasound – Angle of Arrival (AoA) • Measured with directive antennas or arrays

Slide5http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 5 Basic Concepts II Hyperbolic Trilateration Triangulation Multi-lateration – Considers all available beacons A B C a b c Sines Rule Cosines Rule

Slide6http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 6 Existing Technologies INFRASTRUCTURE: • Automatic Vehicle Location system (AVL) – Base stations keep track of police cars ( uses time based and signal strength methods) • GPS, Loran • 911 Emergency Location System (ToA, TDoA) • BAT System(AT&T Cambridge Labs), Cricket (MIT) • RADAR  –  indoor, uses signal strength maps • RFID tags – IR proximity AD-HOC: • Picoradio (UC Berkeley) – indoor, based on signal strength maps • GPS-less outdoor localization (Bulusu et. al) – proximity based

Slide7http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 7 Location Discovery in Ad- Hoc Networks • No infrastructure support • GPS may not always work – Costly, Power Hungry, does not work everywhere • Our Approach – Use RSSI for measuring node separation – But how should the beacons be placed? • Multiple tradeoffs still an open problem

Slide8http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 8 Long Range Beaconing • Long Range Beaconing Advantages: – Multi-hop Coverage – Works well even in low densities • Disadvantages: – Low fault tolerance – Requires Dedicated Beacons – Some infrastructure is required B B B

Slide9http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 9 Our Approach • Single hop beaconing • Iterative multilateration • Dynamic estimate the wireless channel parameters • Can be done in conjunction with routing Advantages: • Data packets are also act as beacon signals • Distributed – relies on neighborhood information • Fault tolerant • Location discovery is almost free!! Beacon

Slide10http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 10 Iterative Multilateration • Start with a small number of beacons • Number of beacons increases as more nodes estimate their positions Initial Beacon Step 1: Step 2: Step 3: becomes  beacon becomes  beacon becomes  beacon

Slide11http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 11 Challenges • Multi-path and shadowing effects – Difficult to work in indoor environments • Beacon placement problem • Bad geometry can affect the quality of the solution • Variable wireless channel characteristics – signal propagation differs from place to place (n=1.5 ... 6)

Slide12http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 12 Solution • Setup as an over-constrained optimization problem and solve for – Wireless propagation model parameters – Node Locations

Slide13http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 13 Problem Setup Wireless Channel Model Error Distance Representation

Slide14http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 14 Optimization Problem • This is a non-linear optimization problem • Hard to compute in one step • We solve the problem in 2 phases over multiple iterations • Keep in mind beacon errors!

Slide15http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 15 Two-Phase Approach • Obtain a propagation model estimate based on initial set of beacons • Certainly of node estimates used as weights for the channel estimate • Follow a rip-up and retry method until a predefined set of constraints is met Channel Estimator Location Estimator Convergence Criteria? Reset Locations NO YES

Slide16http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 16 Simulations 100 Nodes 100 x 100 grid Range = 10 Beacons = 10

Slide17http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 17 Without Beacon Error

Slide18http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 18 With Beacon Error = 10 %

Slide19http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 19 Effect of Beacon Error

Slide20http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 20 Implementation & Measurements • Implemented Location Discovery Algorithm as part of DSDV routing protocol in SensorSim • Obtained RSSI measurements using RSC nodes in outdoor environments • Analyzing the results

Slide21http://nesl.ee.ucla.edu/http://nesl.ee.ucla.edu 21 Conclusions and Future Work • Radio signal strength methods can provide a low cost scalable location discovery • BUT does not work well indoors – experimenting with ultrasound • Exploring Collaborative Multilateration • Beacon placement problem needs to be explored