SenSys147 CO-GPS.pdf

(6280 KB) Pobierz
Energy Efficient GPS Sensing with Cloud Offloading
f liuj,bodhip,tedhar g
f hramos,loureiro g
Location is a fundamental service for mobile computing.
Typical GPS receivers, although widely available, consume
too much energy to be useful for many applications. Ob-
serving that in many sensing scenarios, the location infor-
mation can be post-processed when the data is uploaded to
a server, we design a Cloud-Offloaded GPS (CO-GPS) solu-
tion that allows a sensing device to aggressively duty-cycle
its GPS receiver and log just enough raw GPS signal for post-
processing. Leveraging publicly available information such
as GNSS satellite ephemeris and an Earth elevation database,
a cloud service can derive good quality GPS locations from a
few milliseconds of raw data. Using our design of a portable
sensing device platform called CLEO, we evaluate the accu-
racy and efficiency of the solution. Compared to more than
30 seconds of heavy signal processing on standalone GPS
receivers, we can achieve three orders of magnitude lower
energy consumption per location tagging.
1 Introduction
Location is a fundamental service in mobile sensing. In
outdoor applications such as wildlife tracking [28, 26], par-
ticipatory environmental sensing [20], and personal health
and wellness applications, GPS is the most common modal-
ity for tagging data samples with their locations. GPS receiv-
ing, although becoming increasingly ubiquitous and lower in
cost, is processing-intensive and energy-consuming.
Take ZebraNet sensor nodes [28] as an example. On av-
erage, one GPS location fix requires turning on the GPS chip
for 25 seconds at 462mW power consumption, which domi-
nates its energy budget. As a result, the unit is equipped with
a 540-gram (1.2 pound) solar cell array and a 287-gram (0.6
pound) 2A-h lithium-ion battery in order to support one GPS
position reading every 3 minutes. Power generation and stor-
age accounts for over 70% of the sensor unit’s total weight
of 1151 grams (2.5 pounds).
Recent mobile sensing applications, especially those
leveraging participatory sensing paradigms, typically use
smart phones as sensors. While smart phones have built-
in GPS and cellular-based communication capabilities, their
battery life is rarely longer than a few days. A typical smart
phone will completely drain its battery in about 6 hours if the
GPS is running continuously [14, 21]. This prevents them
from being used in unattended deployments for long periods
of time.
As we will elaborate in section 2, there are two reasons
behind the high energy consumption of GPS receivers: 1) the
time and satellite trajectory information (called Ephemeris)
are sent from the satellites at a data rate as low as 50bps.
A standalone GPS receiver has to be turned on for up to 30
seconds to receive the full data packets from the satellites for
computing its location. 2) The amount of signal processing
required to acquire and track satellites is substantial due to
weak signal strengths and Doppler frequency shifts. As a
result, a GPS chip cannot easily be duty-cycled for energy
saving. In addition, it requires a powerful CPU for post-
processing and least-square calculation.
In this paper, we address the problem of energy consump-
Categories and Subject Descriptors
BASED SYSTEMS]: [Real-time and embedded systems]
General Terms
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. To copy otherwise, to republish, to post on servers or to redistribute
to lists, requires prior specific permission and/or a fee.
SenSys’12,November 6–9, 2012, Toronto, ON, Canada.
Copyright c 2012 ACM 978-1-4503-1169-4 ...$10.00
935609302.041.png 935609302.042.png 935609302.043.png 935609302.044.png
tion in GPS receiving by splitting the GPS location sensing
into a device part and a cloud part.
cesses satellite signals, in order to motivate our solution.
Section 3 describes the principle of CO-GPS. We evaluate
performance of CO-GPS using real GPS traces in section 4.
Finally, section 5 presents the design of the CLEO sensor
node and evaluates its energy consumption in GPS receiv-
2 GPS Receiving Overview
A GPS receiver computes its location by measuring the
distance from the receiver to multiple GNSS satellites (also
called space vehicles, or SVs for short). Ultimately, it needs
to infer three pieces of information:
A precise time T ;
A set of visible SVs and their locations at time T ;
The distances from the receiver to each SV at time T ,
often called the pseudoranges.
Typically, these are obtained from processing the signals and
data packets sent from the satellites. With them, a receiver
can use least-square (LS) minimization to estimate its loca-
To make this paper self-contained and to motivate our so-
lution, we give a brief (and much simplified) description of
the GPS receiving process. We start with standalone GPS re-
ceiving and then discuss Assisted GPS (A-GPS) and in par-
ticular a technique called coarse-time navigation. For a more
formal treatment of the principles of GPS and A-GPS, please
refer to [12, 27].
2.1 GPS Signals
There are 31 (plus one for redundancy) GNSS satellites
in the sky, each orbiting the Earth about two cycles a day.
A set of ground stations monitor the satellites’ trajectory
and health, and send the satellite parameters to the satellites.
These parameters include two kinds of trajectory informa-
tion: the almanac, which contains the coarse orbit and status
information, and the ephemeris, which contains the precise
values of the satellite’s trajectory. All satellites are time-
synchronized to within a few microseconds, and after clock
correction, their time stamps can be synchronized within a
few nanoseconds.
The satellites simultaneously and continuously broad-
cast time and orbit information through CDMA signals at
L 1 =1:575 GHz towards the Earth. The bit-rate of data pack-
ets is a mere 50 bps, but the bits are modulated with a higher
frequency (1MHz) signal for detecting propagation delays.
A full data packet from a satellite broadcast is 30 seconds
long, containing 5 six-second-long frames, as shown in Fig-
ure 1. A frame always starts with a preamble (called Teleme-
try Word, or TLM) and a time stamp (called Handover Word,
or HOW). Each data packet contains the ephemeris of the
transmitting satellite and the almanac of all satellites. In
other words, a precise time stamp can be decoded every 6
seconds, and the high accuracy satellite trajectory can be de-
coded every 30 seconds. This low data rate explains why a
standalone GPS, as seen in vehicles, can take up to a minute
to acquire its first location, a metric called time to first fix
(TTFF). The ephemeris information is constantly updated by
the ground stations. In theory, the ephemeris data included
in the SV broadcast is only valid for 30 minutes.
We take advantage of
several key observations.
Many mobile sensing applications are delay-tolerant.
Instead of determining the location at the time that each
data sample is obtained, we can compute the locations
off-line after the data is uploaded to a server. This is
quite different from the design required by turn-by-turn
navigation in standalone GPS devices.
Much of the information necessary to compute the loca-
tion of a GPS receiver is available through other chan-
nels. For example, NASA publishes satellite ephemeris
through its web services, so the device does not have to
stay on long enough to decode them locally from satel-
lite signals. The only information that the device needs
to provide is a rough notion of time, the set of visible
satellites, and the “code phase” information from each
visible satellite, as we will explain in section 2. Fur-
thermore, code phases can be derived from every mil-
lisecond of baseband signals. Thus, there is significant
opportunity to duty-cycle the receivers if the location
computation is moved to the cloud.
In comparison to the constraints on processing power
and energy consumption, storage is relatively cheap to
put on sensor devices, so we can liberally store raw GPS
baseband signals together with sensor data.
Due to the split between local and cloud processing, the
device only needs to run for a few milliseconds at a time to
collect enough GPS baseband signals and tag them with a
rough time stamp. A cloud service can then process the sig-
nals off-line, leveraging its much greater available process-
ing power, online ephemeris, and geographical information
to disambiguate the signals and to determine the location of
the receiver.
We call this approach Cloud-Offloaded GPS
The CO-GPS idea also bears several challenges. For ex-
ample, for an energy and processing cycle constrained em-
bedded sensor, we cannot maintain a real-time clock that is
synchronized to the satellites. Secondly, it is hard to get
a nearby reference location (whose importance will be ex-
plained in section 2) as proposed in [23]. Finally, because of
aggressive duty cycling, the signal quality may suffer from
temporary degradation. In this paper, we evaluate the ac-
curacy of CO-GPS using real GPS traces and show that the
time synchronization requirement is not very high and the
amount of data needed for off-line processing is only a few
kilobytes. We built a sensor node, called CLEO, based on
the CO-GPS principle using a GPS receiving front end chip
MAX2769 and a WWVB-based time synchronization mech-
anism [19]. Through measurements, we show that it takes
less than 0.5mJ to collect a GPS data point, in comparison to
the order of 1J for GPS sensing on mobile phones – or more
than three orders of magnitude energy efficiency gain on de-
vices. In other words, with a pair of AA batteries (2Ah),
CLEO can theoretically sustain continuous GPS sensing (at
1s/sample granularity) for 1.5 years.
The rest of the paper is organized as follows. In section 2,
we first give an overview of how a typical GPS receiver pro-
935609302.001.png 935609302.002.png 935609302.003.png 935609302.004.png 935609302.005.png 935609302.006.png 935609302.007.png 935609302.008.png 935609302.009.png
300 bits (10 words)
to each other, a visible satellite will show a spike in the cor-
relation results, and an invisible satellite will not cause any
detectable spike.
A challenge in acquiring satellites is the Doppler fre-
quency shift caused by the motion of the satellite and by
any movement of the receiver on the ground. For example,
a rising GPS satellite can move at up to 800m/s towards a
receiver, causing a frequency shift of L 1 800=c=4:2kHz,
where c is the speed of light. A shift of the same magnitude
occurs in the opposite direction for a setting satellite. To
reliably compute a correction under this shift, the receiver
must generate the C/A code within 500Hz of the shifted fre-
quency. Therefore, in the frequency dimension, the receiver
needs to search up to 18 bins. Most GPS receivers use 25 to
40 frequency bins to accommodate local receiver motion and
to provide better receiver sensitivity.
After compensating for the Doppler frequency shifts, the
receiver must determine code phase delays. Because the re-
ceiver does not have a clock synchronized with the satellite,
and because the signal propagation delay can be affected by
atmospheric conditions, the receiver must search over the de-
lay dimension. The receiver usually over samples the 1023
bps C/A code. Assuming that the receiver samples the base-
band signal at 8 MHz, in a brute force way, the receiver will
search 8184 code phase positions to find the best correlation
peak. Figure 3 shows an example of such correlation result
in the frequency and code phase search space that indicates
a successful satellite acquisition.
Code phases change over time as the satellites and the
device on the ground move. In continuous operation, GPS
receivers use a tracking mode to adjust previously acquired
Doppler frequency shifts and code phases to the new ones.
This is a relatively inexpensive process, using feedback
loops. So, once a GPS produces its first location fix, sub-
sequent location estimates become fast. However, once the
GPS receiver stops tracking, the utility of previously known
Doppler shifts and code phases diminishes quickly. Typi-
cally, after 30 seconds of non-tracking, the GPS receiver has
to start all over again.
Clock corrections and SV health
Ephemeris parameters
Ephemeris parameters
Almanac, ionospheric model, dUTC
preamble time stamp
Figure 1. The frame content of a GPS packet of length
1500 bits
While the precise time and satellite locations are decoded
from the packets, the pseudorange from each SV to the re-
ceiver is obtained using much lower-level signal processing
techniques. For that, we need to understand GPS signal mod-
50 bps
1023 kbps
repeat every 1ms
Figure 2.
An illustration of GPS signal modulation
As illustrated in Figure 2, each satellite encodes
its signal (CDMA encoded) using a satellite-specific
coarse/acquisition (C/A) code of length 1023 chips at
1023 kbps. Thus, the C/A code repeats every millisecond,
resulting in 20 repetitions of the C/A code for each data bit
sent. The purpose of the C/A code is to allow a receiver
to identify the sending satellite and to estimate how long it
took the signal to propagate from that satellite to the receiver.
Typically, the GPS signals take from 64 to 89 milliseconds
to travel from a satellite to the Earth’s surface. Since light
travels at 300 km/ms, in order to obtain an accurate distance
measurement, the receiver must estimate the signal propaga-
tion delay to the microsecond level. The millisecond (NMS)
and sub-millisecond (subMS) parts of the propagation time
are derived very differently: the NMS is decoded from the
packet frames, while the subMS propagation time is detected
at the C/A code level using correlations.
2.2 Acquisition
When a GPS receiver first starts up, it needs to detect what
satellites are in view. This is done by detecting the presence
of the corresponding C/A codes in the received signal, typ-
ically by correlating the signal with each known C/A code
template. Since the C/A codes are designed to be orthogonal
Figure 3. An example of acquisition result.
935609302.010.png 935609302.011.png 935609302.012.png 935609302.013.png 935609302.014.png 935609302.015.png 935609302.016.png 935609302.017.png 935609302.018.png 935609302.019.png 935609302.020.png 935609302.021.png 935609302.022.png 935609302.023.png 935609302.024.png 935609302.025.png 935609302.026.png 935609302.027.png 935609302.028.png 935609302.029.png
Acquisition is an expensive operation as it must search
through 30+ frequency bins times 8,000+ code phase pos-
sibilities for every single satellite. If the receiver has some
prior information about the satellites, it may be able to do
less work. Examples are:
Cold Start. When the receiver has no prior knowledge
of the satellites and its own location, it has to search the
entire space. Usually, GPS receivers do not buffer the
raw data to perform the search, rather they perform one
code phase search per millisecond as the signal streams
in. Although there are hardware correlators that per-
form acquisition in parallel, it still takes a few seconds
to acquire one satellite. This is one of the main rea-
sons for the slow initial position fix and high energy
consumption for standalone GPS devices.
Warm Start. When the receiver has a previous lock
to the satellites, it can start from the previous Doppler
shift and code phases and search around them. In gen-
eral, if the previous lock is less than 30 seconds old, a
warm start can quickly find the new lock. Otherwise,
the receiver has to revert to the cold start process.
Hot Start. When the previous satellite locks are within
a second, the receiver can skip the acquisition process
and start directly from tracking to refine the Doppler
and code phases. In this mode, all information that the
receiver needs is already in place. This is the reason
that in mobile phones, “continuous GPS sampling” is
defined as one location sample per second.
A-GPS. There are multiple ways that an infrastructure
can help the GPS receiver start up faster. In partic-
ular, in the Mobile-Station Based A-GPS (or AGPS-
B) mode, the infrastructure provides the up-to-date
ephemeris data so that the GPS receiver does not have
to decode them from the satellite signals. The first suc-
cessful decoding of HOW is enough to provide a loca-
tion fix. In this case, the TTFF is usually around 6 sec-
onds. In the Mobile-Station Assisted A-GPS (or AGPS-
A) mode, the infrastructure is given the estimated lo-
cation, so it can provide initial values for Doppler and
code phase searches. This allows the receiver to jump
directly into the warm start process.
2.3 Location Calculation
An important output of satellite acquisition and track-
ing processes is the code phase produced by the correla-
tion peaks. It gives the sub-millisecond level propagation
delay. If the receiver has decoded the satellite time stamps
(HOW), it knows the time that the signals have left the satel-
lites. Then, it can add these sub-millisecond delays to obtain
the whole propagation delay and thus the pseudoranges.
With correct tracking, the receiver can decode the packets
sent by the SVs. In general, without assistance information,
the receiver needs to decode SV ephemeris every 30 min-
utes (its valid time span) and time stamps every 6 seconds.
Decoding is energy consuming since it has to run tracking
continuously for the packet duration in order to receive all
the bits. With A-GPS, the receiver is not required to decode
ephemeris, but it must still decode HOW.
Next, given ephemeris, the propagation delays obtained
from code phases, and HOW, the GPS receiver performs po-
sition calculation using constraint optimization techniques
such as Least Squares minimization. Usually, the local clock
at the receiver does not know the precise satellite time, so it
is treated as one variable in the minimization solver. With the
receiver’s latitude, longitude, altitude, and the precise satel-
lite time as optimization variables, typical receivers must
have at least 4 SVs in view.
Notice that once the satellites are acquired, distance mea-
surements, and thus the location of the receiver, can be es-
timated every millisecond. A typical GPS receiver will av-
erage over multiple Least Square solutions to further reduce
noise and improve location accuracy.
Finally, we discuss how much data is necessary for satel-
lite acquisition. Since the baseband C/A code repeats ev-
ery millisecond, in the ideal case, 1ms of data is enough for
satellite acquisition. Assume a 8 MHz baseband sampling
frequency, the minimum amount of data needed for acqui-
sition is 8*1023 = 8184 samples. For most GPS receiver
chips, each sample is two bits (one bit sign and one bit mag-
nitude), thus the storage requirement for 1ms of baseband
data is 2046 bytes. One corner case that deserves special at-
tention is the bit transition in the middle of the 1ms signal.
Since the C/A code is used to modulate the data packets at
50bps, for every 20ms, there is a possibility of a bit transi-
tion. If the transition is in the middle of the 1ms sample, then
the acquisition of the corresponding satellite will fail. So, in
practice, 2ms is more reliable for satellite acquisition.
2.4 Coarse-Time Navigation
The above discussion assumes that the receiver is stan-
dalone with no assistance information. A-GPS receivers re-
ceive assistance information from servers to improve their
TTFF. Typically, the assistance information includes the
ephemeris data so the receivers do not have to decode them
from the satellite signals. Some A-GPS approaches also pro-
vide Doppler shift and code phase guesses to the receiver so
their acquisition searches do not start blindly.
One A-GPS mechanism called Coarse-Time Navigation
(CTN) is particularly relevant to this paper. With this
method, the receiver does not require the timestamp (HOW)
decoded from the satellite. Instead, it only needs a coarse
time reference and treats common clock bias (i.e. the differ-
ence between the receiver clock and the ideal satellite clock)
as a variable in Least Square minimization. This method is
first described in [27] and further exploited in [23] to reduce
mobile phone GPS energy consumption.
Without decoding the HOW, the receiver cannot synchro-
nize to the satellites’ transmission times. So, a key idea
in using CTN is to leverage a nearby landmark to estimate
NMS. Since light travels at 300 km/ms, two locations within
150km of each other will have the same millisecond part of
the propagation delay, rounded to the nearest integer. For
mobile phones, it is natural and convenient to use cell tower
locations as the landmarks [23]. A cell tower usually covers
a radius less than 10km.
Although the millisecond part of the pseudorange can be
estimated by using the landmark location, the lack of a syn-
chronized clock presents an additional challenge. Since the
935609302.030.png 935609302.031.png
satellites move in the sky, a wrong estimate of time results
in using a wrong value for the satellite location and thus
the calculations yield an erroneous receiver location. Integer
rollover is the main source of such errors in CTN. Van Digge-
len [27] proposes the following method to reconstruct the full
pseudoranges while avoiding the integer rollover problem.
The signal travel time can be written as
NMS (k) +j (k) =t (k) d (k)
landmarks. For embedded sensors without cellular connec-
tions that are expected to have high mobility over their life-
times, it is not always possible to provide nearby landmarks.
Our key idea is to leverage the computing resources in the
cloud to generate a number of candidate landmarks and then
use other geographical constraints to filter out the wrong so-
3.1 Shadow Locations
The CO-GPS solution assumes a simple flow of informa-
tion. In addition to application-specific functionality such as
sensing, the device has three main components for location
sensing — a GPS receiving module, a time synchronization
module, and a data storage space.
In this section, we assume that the device is reasonably
synchronized with a global clock, which we will elaborate
upon further in section 5.2. When the device needs to sense
its location, it simply turns on the GPS receiving front end
and records a few milliseconds of GPS baseband signal. As
we discussed in the previous section, we require at least 2ms
worth of data to avoid possible bit boundaries.
The challenge of deriving receiver location with no refer-
ence landmark is the possible outliers, which we call shadow
locations. Figure 3.1 illustrate the reason behind it using two
satellites. Here, we model the pseudoranges from each SV
as a set of waves, each 1 light-ms apart. Clearly, these waves
intersect at multiple locations. Since we do not know the
exact millisecond part of the propagation delay, all intersec-
tions, A;B;C;D;:::are feasible solutions, even though only
one of them is real. When more satellites are visible, more
constraints are added to the triangulation, which helps re-
solve the ambiguity. However, the number of satellites alone
is not enough.
t +b+e (k)
= ˆ t (k) d (k) d (k)
t +b+e (k)
where NMS (k) andj (k) are the millisecond and sub-milli-
second components, respectively, of the transmission delay
from SV k,t (k) is the actual travel time of the signal leav-
ing SV k,d (k t is the satellite clock errors obtained from the
ephemeris at the a priori coarse time for the satellite k, and
e (k) represents some unknown errors (tropospheric model er-
ror and other stochastic errors). The common clock bias b is
the unknown to be eliminated.
Ast (k) is unknown, it can be written ast (k) = ˆ t (k) d (k) ,
where ˆ t (k) is the estimated travel time from the a priori posi-
tion at the coarse time of transmission, and d (k) is the error in
ˆ t (k) . The method involves the selection of a reference satel-
lite, k=0, where NMS (0) =round( ˆ t (0) j (0) )is the mil-
lisecond part of the pseudorange of the reference SV 1 . This
value is used to reconstruct the millisecond travel time of
all other satellites relative to the reference satellite. Thus, if
we subtract the Eq. (2) from the reference satellite full travel
time we get
NMS (k) =NMS (0) +j (0) j (k)
t +b+e (k)
ˆt (0) d (0) d (0)
ˆt (k) d (k) d (k)
t +b+e (0) (3)
We still do not know the values of d (0) and d (k) , but con-
sidering that we have an initial position and coarse time close
to the correct values (about 100 km and 1 min), the order of
magnitude of(d (k) +e (k) +d (0) e (0) )is far less than 1=2
second, thus, we can correctly estimate NMS (k) by
NMS (k) =round
NMS (0) +j (0) j (k)
+(ˆt (k) d (k t )(ˆt (0) d (0 t ) : (4)
Now, the full pseudorange is estimated by using NMS as
the millisecond part, and the sub-millisecond is obtained by
the code phase estimate. So, with CTN, the only device-
dependent data are the acquisition results, which can be com-
puted with as little as 1ms of raw signal. This is the key
observation to move the location computation completely to
the cloud.
3 CO-GPS Design
The design of Cloud-Offloaded GPS (CO-GPS) leverages
the CTN principle but removes the dependency on nearby
Figure 4. An illustration of multiple feasible solutions
under NMS ambiguity.
To illustrate this effect, we take a 1ms real GPS trace
and apply CTN with an array of landmarks across the globe.
There are 6 satellites in view. The landmarks are generated
by dividing the latitude and longitude with a 1 o resolution
around the globe. In other words, we picked 180360=
64800 landmarks with adjacent distance up to 111km on the
equator . Figure 5 shows the total of 166 converged points.
1 [27] recommends the use of the highest satellite in view as reference,
and provides a good reason for that.
935609302.032.png 935609302.033.png 935609302.034.png 935609302.035.png 935609302.036.png 935609302.037.png 935609302.038.png 935609302.039.png 935609302.040.png
Zgłoś jeśli naruszono regulamin