SenSys147 CO-GPS.pdf

Energy Efﬁcient GPS Sensing with Cloud Ofﬂoading

JieLiu,BodhiPriyantha,TedHart

MicrosoftResearch

Redmond,WA98039,USA

f liuj,bodhip,tedhar g @microsoft.com

HeitorS.Ramos,AntonioA.F.Loureiro

FederalUniversityofMinasGerais

BeloHorizonte,MG,

f hramos,loureiro g @dcc.ufmg.br

QiangWang

HarbinInstituteofTechnology

Harbin,China

wangqiang@hit.edu.cn

Abstract

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-Ofﬂoaded 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 efﬁciency 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 ﬁx 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

C.3 [SPECIAL-PURPOSE AND APPLICATION-

BASED SYSTEMS]: [Real-time and embedded systems]

General Terms

Design

Keywords

location,

assisted

GPS,

cloud-ofﬂoading,

coarse-time

navigation

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 proﬁt or commercial advantage and that copies bear this notice and the full citation

on the ﬁrst page. To copy otherwise, to republish, to post on servers or to redistribute

to lists, requires prior speciﬁc permission and/or a fee.

SenSys’12,November 6–9, 2012, Toronto, ON, Canada.

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-

ing.

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-

tion.

To make this paper self-contained and to motivate our so-

lution, we give a brief (and much simpliﬁed) 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 ﬁrst location, a metric called time to ﬁrst ﬁx

(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 signiﬁcant

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-Ofﬂoaded GPS

(CO-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 efﬁciency 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 ﬁrst give an overview of how a typical GPS receiver pro-

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 ﬁnd 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 ﬁrst location ﬁx, 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.

TLM

HOW

Clock corrections and SV health

TLM

HOW

Ephemeris parameters

TLM

HOW

Ephemeris parameters

TLM

HOW

Almanac, ionospheric model, dUTC

TLM

HOW

Almanac

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-

ulation.

50 bps

1023 kbps

repeat every 1ms

1.575GHz

Figure 2.

An illustration of GPS signal modulation

scheme.

As illustrated in Figure 2, each satellite encodes

its signal (CDMA encoded) using a satellite-speciﬁc

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 ﬁrst 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

Correlation

Figure 3. An example of acquisition result.

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 ﬁx 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 ﬁnd 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 reﬁne 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

deﬁned 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 ﬁrst suc-

cessful decoding of HOW is enough to provide a loca-

tion ﬁx. 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

ﬁrst 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

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 ﬁlter out the wrong so-

lutions.

3.1 Shadow Locations

The CO-GPS solution assumes a simple ﬂow of informa-

tion. In addition to application-speciﬁc 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)

(1)

= ˆ t (k) d (k) d (k)

t +b+e (k)

(2)

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-Ofﬂoaded 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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: