Dynamic Location Discovery in Ad Hoc Networks

Dynamic Location Discovery in Ad Hoc Networks

This paper, authored by Andreas Savvides, Athanassios Boulis, and Mani B. Srivastava, explores the topic of location discovery in ad hoc networks

  • Uploaded on | 0 Views
  • faraj faraj

About Dynamic Location Discovery in Ad Hoc Networks

PowerPoint presentation about 'Dynamic Location Discovery in Ad Hoc Networks'. This presentation describes the topic on This paper, authored by Andreas Savvides, Athanassios Boulis, and Mani B. Srivastava, explores the topic of location discovery in ad hoc networks. The key topics included in this slideshow are . Download this presentation absolutely free.

Presentation Transcript

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