Slide 1OverviewMobile Location ServicePurposeObservationObservation (cont.)a-LocSystem OverviewAccuracy ModelsAccuracy Models (cont.)Accuracy Models (cont.)Accuracy Models (cont.)Energy ModelsEnergy Models (cont.)Energy Models (cont.)Energy Models (cont.)Energy Models (cont.)Energy Models (cont.)Selection AlgorithmSelection AlgorithmSelection Algorithm (cont.)System PerformanceSystem Performance (cont.)Case StudyCase Study (cont.)Case Study (cont.)ConclusionQuestionsReferencesA L B E R T PA R KE E L 6 7 8 8 : A D VA N C E D T O P I C S I N C O M P U T E R N E T W O R K SEnergy-Accuracy Trade-off for Continuous Mobile DeviceLocation, In Proc. of the 8th International Conference on Mobile Systems, Applications, and Services (MobiSys)Lin, K., Kansal, A., Lymberopoulos, D., and Zhao, F., 2010, pp. 285-298Energy-accuracy Trade-offOverviewMobile Location ServicePurposeObservationDesignCase StudyMobile Location ServiceMethods for current mobile device localizationGPSWiFiCell-tower signature based location servicePurposeDevelop location as a system service that automatically manages location sensor availability, accuracy, and energy.Allows the system to optimize battery life by intelligently managing the location energy and accuracy trade-offs based on available sensor.Ensure long battery life for acceptable user experience.ObservationTwo observationsFirst, location applications do not always need the highest available accuracy provided by GPS.Second, a phone has multiple modalities to sense location aside from the GPS: WiFi triangulation, cell-tower triangulation, Bluetooth vicinity, and audio or visual sensing.Observation (cont.)Highest accuracy not always neededa-Loc Adaptive location service for mobile deviceAutomatically determines the dynamic accuracy requirement for mobile search applications Continually tune the energy expenditure using the available sensorA Bayesian estimation framework is used to model user location and sensor errorsAndroid G1 and Nokia N95System OverviewFigure 1. System block diagramAccuracy ModelsDynamic Accuracy RequirementThis block provides the location accuracy needed by the applications. The dynamic sensor models characterize the accuracy and its variation with location.GPSWiFiBluetoothCell-towerAccuracy Models (cont.)GPSA GPS receiver typically reports its estimate of error as horizontal dilution of precision (HDOP).HDOP 6 or below: translates to less than 12m of location errorFigure 2. Experimentally measured GPS accuracyAccuracy Models (cont.)WiFiThe error is expressed as a function of the number of access points visible over time. As an alternative, an error estimate for WiFi localization is also provided by Google location service are used on Android.Figure 3. WiFi location error with Android G1Accuracy Models (cont.)BluetoothLocation based on finding at least one static Bluetooth device within its radio range.The error is taken to be the Bluetooth range and infinity at other locations.Cell-TowerRadio stack in the device maintains cell-towers list.With only one tower’s identity, the location error is essentially equal to the size of the cell.Use the cell-size based on typical cell tower densityEnergy ModelsSensor Energy Model These models characterize the energy used by each available location sensor for obtaining location. In some cases, the energy spent depends on the location where the observation is made and experimentally measure this effect.Energy Models (cont.)WiFi TriangulationExternal factor to affect the energy is number of visible APsEnergy cost does not vary significantly with number of APsFigure 4. Measured power profile for WiFiFigure 5. Energy usage for WiFiEnergy Models (cont.)Bluetooth VicinityKnown static device location can determine user’s locationLower power usage than WiFi, but longer scanningEnergy depends on the number of visible devicesFigure 6. Bluetooth power usage during scanFigure 7. Bluetooth energy usage variationEnergy Models (cont.)GPSEnergy usage depends on locationGPS power drawn measurements Android:230mW, Nokia:324mWWarm-start: 1425mJ, Cold-start: 5700mJFigure 8. Measured GPS power profileFigure 9. GPS energy usage (cold start)Energy Models (cont.)Cell-Tower AssociationMobile phone maintains a list of cell-towers that are visible to its radio receiver.Based on this information the phone can determine its location. The energy consumption is negligible that it only consists as reading data available on the local device which measured less than 20mJ (average) over multiple readings.Energy spent on various modalitiesEnergy Models (cont.)Figure 10. Relative energy costs of location modalitiesSelection AlgorithmSensor Selection Algorithm The sensor selection algorithm determines the location sensor to be used at each time step. The algorithm includes a method to model the user location trajectory and uses the sensor data as available to improve the location estimates.Selection AlgorithmDetermine the most energy efficient sensor to be usedAlso maintains an estimate of the user’s location that is based on a prediction of user movementsHelps select the appropriate location for the sensor energy and accuracy modelHelp avoid sensing when predicted location has a high confidenceSelection Algorithm (cont.)Uses Hidden Markov Model (HMM)Uses the past two observed locations to yield a distribution of predicted locations. A second order model takes the direction of motion into account, significantly improving prediction performance over a first order of HMM.Figure 11. Select Sensor AlgorithmSystem PerformanceThe sensor accuracy models are assumed to be learned before the performance of the system is measured.HMM parameters are learned in real-time as the user moves.System Performance (cont.)Alternative strategies (for comparison)Static Model: The parameters used are the typical accuracies expected from different sensors (Bluetooth, WiFi, Cell-Tower, and GPS)Periodic Model: Use a single location sensor periodically.GPS and WiFiPerfect Model: As the system is used by more users, more data may be collected to refine a hypothetical perfect accuracy model for all locationsCase StudyReal world scenario (San Diego) Significant slack in accuracy exists showing sensors other than
View Full Document