Energy-Efficient Rate-Adaptive GPS

Report
Energy-Efficient Rate-Adaptive
GPS-based Positioning for Smartphones
by Jeongyeup Paek, Joongheon Kim, and Ramesh Govindan
EECE354
Kyoungho An
Contents
• Introduction
• Problem
• Rate-Adaptive Positioning System
–
–
–
–
Movement
Space-Time History
Celltower-RSS Blacklisting
Bluetooth-based Positioning Synchronization
• Discussion
• Evaluation
Introduction
• Smartphone applications require position information
– GPS is preferred over GSM/WiFi
• more accurate but power hungry
• duty-cycle GPS
– Trades off positioning accuracy for lower energy
• RAPS (Rate-Adaptive Positioning System)
– GPS is less accurate in urban areas
• Turn on GPS only necessary to achieve the accuracy
– Use location-time history of the uses to estimate velocity and
uncertainty
– Use Bluetooth communication to reduce position uncertainty
– Use celltower-RSS blacklisting to detect GPS unavailability
• Evaluation of RAPS
– Increase phone life-times by more than a factor of 3.8 over an
approach where GPS is always on
Introduction
• GPS is accurate
– WPS (WiFi-based positioning system) is less accurate than GPS
– GSM-based positioning has an error as high as 300meters
• GPS is extremely power hungry
– Nokia N95 smartphones
• Internal GPS uses around 0.37 Watt
• 0.06 Watt idle power
• GPS activated would drain the 1200mAh battery on an N95
smartphones in less than 11 hours
Introduction
• The key insight that motivates the work
– GPS can exhibit errors in the rage of 100m
when used in urban areas
• Location-based applications
– deal with the errors using application-specific
methods
• map-matching
• map-snapping.
– If applications can tolerate the position error,
why not trade off some position accuracy for
reduced GPS energy usage?
• Periodic duty-cycle GPS
– The key challenge is to decide on a time period
Problem
• GPS is not accurate in urban areas
– GPS trace collected for a week using a smartphone that
continuously logged GPS positions every 1 second.
– ground truth path is labeled as A
– phanthom path labeled as B
– GPS was available for only 11.2% of the time
– GPS may provide inaccurate positioning as high as 100 meters
or more across a wide range of urban locations
Problem
•
Where do these errors come from?
– A GPS receiver requires signals from 4 satellites
– However, when GPS receiver do not have complete signals from all satellites,
then the errors can increase significantly
– When it guesses a position, a GPS receiver provides accuracy estimates, but low
confidence in its position results.
– Moreover, smaller antennae, carried in clothing or bags, indoors, frequent power-off
•
Can we cleverly activate GPS only when necessary and sacrifice a little accuracy in
exchange for reductions in energy usage by GPS?
Problem
• Simple solution is duty-cycle GPS
– Periodic duty-cycled GPS (3 mins)
• Less than 40 meters for 28%
• Often exceed 100 meters and go as high as 300 meters
• Uncertainty depends upon the movement pattern of the user
– Interval increases enabling lower energy usage,
the uncertainty increase linearly with no sweet spot
Problem
• Summary
– GPS is generally less accurate in urban areas
– Periodic duty-cycling with a fixed interval
can introduce significant, potentially
unbounded error without energy benefits
Rate-Adaptive Positioning System
(RAPS)
• User movement detection using a dutycycled accelerometer
• Velocity and uncertainty estimation using
space-time history
• GPS unavailability detection using
celltower-RSS blacklisting
• Position uncertainty reduction using
Bluetooth
Movement Detection
• Modern smartphones are equipped with
an accelerometer, and can be used to
detect whether the user is moving or not
• Use of the accelerometers in RAPS
– It is used to measure the activity ratio
• Activity ratio: the fraction of a given time
window during which the user is in motion
– Duty-cycle to save energy
Movement Detection
•
Onset detection technique
–
–
It is possible to detect whether a user is stationary or not
It does this by maintaining running estimates of the signal envelope and compares these
against the noise mean (1g)
•
•
•
Signal envelope: dynamic upper and lower bounds of the signal
RAPS uses this onset detection method and calculates activity ratio
However, RAPS cannot use the accelerometer continuously because of significant energy
usage.
–
–
30 seconds intervals: consumes 0.08 Watt which means that turning on the accelerometer for 5
minutes consumes more energy than activating GPS for 1 minute.
The method for deriving a good duty-cycling parameter is collecting continuous acceleration
measurements for five different human activities: stationary, frequent walking and stopping, fast
walking, driving in a car, and milling about in a coffee shop
Movement Detection
• For each trace, calculate activity ratio using the onset detector
• Performed offline analysis, and calculated the error in the activity
ratio respect to the reference always-on case.
• Duty-cycle parameter of 12.5% with 2 and 14 seconds ON/OFF
periods is selected
Movement Detection
•
•
•
Could we have used a similar accelerometer duty cycling technique to
estimate user speed (distance), rather than just activity?
It is not that attractive
– Calculation is roughly correct when the orientation of the phone does not change
too frequently and the acceleration is greater than the noise level during the period
of the movement.
– A duty cycle of 50% or more is required to estimate the distance within 10% error
RAPS uses only the activity if there is sufficient history and
distance estimation and the activity ration only if there is insufficient
history
Space-Time History
•
A key component of RAPS is the space-time table
•
Whenever RAPS needs to decide to active GPS
•
RAPS updates and uses the space-time history as follows
– Space-time table: records the past history of user movements
– Looks up the history of average user velocity and activity ratio
– Calculate the current position uncertainty based on the estimated current velocity
and the activity ratio
– For scaling reasons, it quantizes both the space and time dimensions
– RAPS associates with each grid box in this quantized coordinate system two
quantities: a history of average velocity and activity ration
Space-Time History
•
Example
– If a user moves into a position A, the user is stationary for 4 units of time and
moves out of position A in the next unit of time at velocity of 10m/s and activity
ratio of 0.5.
– Velocity is {0, 0, 0, 0, 10}
•
Average 2m/s
•
Average 0.1
•
•
the current activity ratio R(t) = 0
estimated velocity V(t) = 0
– Activity ratio is {0, 0, 0, 0, 5}
– If the user is stationary,
– If the user is moving out of position A with R(t) close to 0.5, V(t) becomes
2*0.5/0.1 = 10m/s.
•
This approach allows RAPS to cheaply estimate user movement,
activating GPS only when user movement may have exceeded the
accuracy bound
Celltower-RSS Balcklisting
•
•
GSM data can be retrieved without additional energy cost.
However, in practice, GSM data from all visible cell towers is not available to third party
application developers
–
•
•
•
•
•
Only one cell tower information is visible at a time
Needs to examined whether information from a single cell-tower can reliably detect user
movement
Distance between two consecutive GPS locations when there was a change in cellID.
Maximum distance between two positions within the same cellID
58.3% less than 10m difference in GPS positions
28.2% greater than 100m
These results imply that simply using the cellID itself provides insufficient information about
whether the user has moved a significant distance or not
Celltower-RSS Balcklisting
•
Signal strength difference with a cellID can be an indicator of change in position?
–
–
The average distance plot shows that increasing RSS difference correlates with increasing
distance,
but the variance of the distance is too high
A single cell-tower cannot reliably indentify user movement
Celltower-RSS Balcklisting
•
Since we are merely interested in determining whether and when GPS should be activated,
instead of using cell towers to detect motion, we directly detect whether uses are in an
environment or not.
–
•
Maintaining a history of GPS availability per cellId can help accurately predict GPS is avaiable.
–
–
•
GPS availability probability as a function of signal strength for two different cellId’s
Whenever a GPS reading is successfully obtained or the request has time-out, it stores this information
in a celltower-RSS blacklist.
Update RSS Good Thresh and RSS Bad Thread
When a getting GPS update, checks the blacklist.
–
If it is in the good and variable region, turns on GPS. Otherwise, wait until there is a change in GSM
data or maximum timeout
Bluetooth-based Positioning
Synchronization
• Use of Bluetooth to synchronize position information
between neighboring devices
• Consider a scenario where there are two
smarphones (A and B)
– If A has recently activated GPS, then
– B can get the position information from A without
activating GPS
• Bluetooth is a good for a positioning
synchronization
– Communication range is less than 10 meters
• Uncertainty is less than 10 meters
– Energy cost is less than GPS
– Available on almost all mobile phones
Bluetooth-based Positioning
Synchronization
•
•
•
•
•
Using Bluetooth, most of the power is consumed on the master node
During one synchronization cycle depicted in the figure, the slave node used 0.09J, and
the master node used 3.07J, averaging 1.58J per node.
For comparison, if a GPS receiver was turned on and stayed on for 60 seconds, it would
spend around 0.37W * 60sec = 22.2J.
43%reduction in energy usage
If there are 5 nodes,
–
–
–
GPS: 5*22.2J = 111J
BPS: 22.2 + 3.07 + 4*0.9 = 28.87J
74% reduction in energy
Bluetooth-based Positioning
Synchronization
• BPS works as follows
– Every node becomes slave node and stays in idle
– A node decides(master) to transmit its position and
uncertainty information.
– If any slave nodes exist, the master connects to all of
them, and broadcasts its position information.
– Each slave compares its uncertainty and updates its own
position if the received position has lower uncertainty.
– If the received uncertainty is higher than its own, the
slave replies to the master with better position and
uncertainty values.
– The uncertainty value of all connected devices are
synchronized.
Summarization
• Three details of RAPS
1. The user space-time history and the celltowerRSS blacklist must be populated for RAPS to
work efficiently
2. Velocity estimation based on activity ratio can
be misled by handset activity not related to
human motion
3. Accelerometers on smartphones may need a
one-time per-device calibration of the offset
and scaling before running RAPS
• Bluetooth-based position synchronization
requires user co-operation.
Evaluation - Setting
Evaluation - Lifetime
Evaluation – BPS
Evaluation – RSS blacklist
Evaluation – GPS Interval
Evaluation – Average Power
Evaluation – Median Distance
Evaluation – Median Distance
Evaluation –
Comparison with fixed duty-cycle
Evaluation –
Comparison with WPS
Conclusion
• Presented RAPS, rate-adaptive positioning
system for smartphones
– GPS is generally less accurate in urban areas,
so it suffices to turn on GPS as often as necessary
to achieve this accuracy
– Used a collection of techniques that could be
implemented on current generation of smartphones
to cleverly determine when to turn on GPS
• Evaluated RAPS through real-world experiments
– Increases lifetime by more than a factor of 3.8
relative to the case when GPS is always on.

similar documents