CMPE 257 Wireless and Mobile Networking Spring 2005 Location management CMPE 257 Spring 2005 1 Announcements Homework 2 due tomorrow by midnight Stay tuned for homework 3 Class evaluations on Tuesday 05 31 Need campus volunteer Final exam on Thu June 2 In class closed books notes Project presentations on June 9th 4 7pm CMPE 257 Spring 2005 2 Today Finish reliable multipoint e2e Location management CMPE 257 Spring 2005 3 Location Management CMPE 257 Spring 2005 4 Why is location management needed In wired networks hosts don t move Constant association between host id address and its location In mobile wireless networks hosts can move Host id address no longer provides location information Need location tracking mechanism to deliver information destined to host CMPE 257 Spring 2005 5 Location for the Active Office Ward97 Indoor sensor system that tracks location of people active badge equipment equipment tags etc Requirements accurate within 15cm 3 dimensions scalable number of objects locatable area covered cost RF communication CMPE 257 Spring 2005 6 System components Transmitters attached to every locatable object Matrix of receiver elements in all rooms where objects are to be tracked Controller which polls one mobile object at a time CMPE 257 Spring 2005 7 Operation Periodically mobile node is polled Polled mobile broadcasts signal Controller synchronizes receivers who listen for some time to detect the peak of mobile s transmission Controller polls receivers for the measured time interval between the sync signal and the signal peak if any CMPE 257 Spring 2005 8 Distance computation Time measured by receiver composed of time to transmit the polling signal from controller to mobile time to transmit pulse function of distance being calculated processing time Distance between mobile and receiver calculated Empirically computed speed of sound in the room and service times CMPE 257 Spring 2005 9 Position calculation Triangulation using 4 receivers to determine a point in 3 dimensional space as estimate of position In this particular set up since all receivers are in the ceiling only 3 distances required Extra reported distances can be used for higher accuracy CMPE 257 Spring 2005 10 Evaluation Experiments with prototype show 95 of readings within 14cm accuracy Even better accuracy for averaged readings Addresses limit number of trackable objects Large number of receivers and ultrasound nature of transmission from mobile proved to pay off regarding accuracy Power savings mode minimizes maintenance Low interference levels from office equipment CMPE 257 Spring 2005 11 Testbed Single floor 10500 sq ft with 50 rooms 3 base stations covering entire floor Lucent WaveLAN RF technology 2 Mbps 1 2 ms one way delay 200m and 25m range open close environments CMPE 257 Spring 2005 12 RADAR Bahl et al Similar to the Ward97 paper Provide indoor location service RF Use received signal strength triangulation Low cost Off the shelf hardware CMPE 257 Spring 2005 13 Testbed Single floor 10500 sq ft with 50 rooms 3 base stations covering entire floor Lucent WaveLAN RF technology 2 Mbps 1 2 ms one way delay 200m and 25m range open close environments CMPE 257 Spring 2005 14 Operation Off line and real time functions Off line derive and validate accurate signal propagation models Real time user location CMPE 257 Spring 2005 15 What is being collected Signal strength in dBm s Watts 10 log10 s 001 dBm Signal to noise ratio SNR in dB SNR dB 10 log 10 s n dB For each received packet SS and SNR are recorded CMPE 257 Spring 2005 16 Data collection process Mobile broadcasts beacons periodically Base stations record SS and SNR Different than the ORL system Scalability Path asymmetry CMPE 257 Spring 2005 17 More on data collection All clocks synchronized Mobile broadcasts packets 4 pkt sec BS records t bs ss Off line mobile also provides its location by using a floor map Orientation is important LoS obstruction etc In off line phase collected SS in all 4 directions at 70 different floor locations For each x y d 20 ss samples d is direction N S E W CMPE 257 Spring 2005 18 Processing data Off line data used to build signal propagation model Validation of assumption that from signal strength location can be inferred How is location determined Signal strengths from 3 BSs Compare to floor layout energy map Pick location that minimizes Euclidian distance between measured and recorded set of SS s CMPE 257 Spring 2005 19 Results Empirical method performs better than random and strongest BS Error approx size of a room Taking k nearest neighbors shows some improvement Analysis of impact orientation number of data points and number of samples User tracking CMPE 257 Spring 2005 20 Radio propagation model Model of indoor signal propagation No need for empirical data Indoor propagation Reflection diffraction scattering Multipath effect Receiver gets signal from multiple paths Distorted signal Challenges dependency on layout material obstacles number and type etc CMPE 257 Spring 2005 21 Radio propagation model cont d Adaptation of existing model to single floor Consider effects of walls Signal strength varies with distance AND number and type of obstacles Empirical characterization of wall attenuation Use corrected empirical data and linear regression to determine other parameters Similar values for different BSs location surroundings etc Less accurate results than empirical model but more practical CMPE 257 Spring 2005 22 Localization in Sensor Networks Bulusu01 CMPE 257 Spring 2005 23 What are sensor networks Large number of small low power devices wirelessly connected Applications Monitoring surveillance tracking etc Typically ad hoc deployable unattended operation Data centric instead of node centric CMPE 257 Spring 2005 24 Localization Estimation of physical position coordinates Localization Why is this important Data usually identified by location temperature of a given area target tracking signal processing applications No a priori knowledge of location GPS CMPE 257 Spring 2005 25 Approaches Multilateration nodes measure enough pairwise distance estimates Combination of radio for time reference and acoustic time of flight for distance signals Proximity based beacon nodes periodically broadcast position nearby nodes then estimate their position Iterative multilateration beacon information propagated multi hop Beacon density sparse in some areas CMPE 257 Spring 2005 26 Self configuring localized algorithms Adjust to