Skyhook Wireless, Inc. v. GOOGLE, INC.

Filing 45

DECLARATION of Susan Baker Manning in Support of Google Inc.'s Motion for Summary Judgement of Indefiniteness And, In the Alternative, Opening Claim Construction Brief by GOOGLE, INC.. (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F)(Manning, Susan)

EXHIBIT F

111111111111111111111111111111111111111111111111111111111111111111111111111
US007474897B2

United States Patent

(10)

Morgan et al.

(12)

(45)

(54)

CONTINUOUS DATA OPTIMIZATION BY
FILTERI~GAND POSITIONING SYSTEMS

(75)

Inventors: Edward J. Morgan, Needham, MA
(US); Michael G. Shean, Boston, MA
(US); Farshid Alizadeh-Shabdiz,
Wayland, MA (US); Russel K. Jones,
Roswell, GA (US)

(73)

Assignee: Skyhook Wireless, Inc., Boston, MA
(US)

(*)

Notice:

Patent No.:
US 7,474,897 B2
Date of Patent:
Jan. 6,2009

6,888,811
6,978,023
7,123,928
7,167,715
7,167,716
7,305,245
7,397,424
7,403,762

B2
B2
B2
B2
B2
B2
B2
B2

5/2005
12/2005
10/2006
1/2007
1/2007
12/2007
7/2008
7/2008

Eaton et al.
Dacosta
Moeglein et al.
Stanforth
Kimet al.
Alizadeh-Shabdiz et al.
Houri
Morgan et al.

(Continued)

Subject to any disclaimer, the term of this
patent is extended or adjusted under 35
U.S.c. 154(b) by 491 days.

OTHER PUBLICATIONS
u.S. Appl. No. 111625,450, Alizadeh-Shabdiz.

(21)

Appl. No.: 11/359,271

(22)

Filed:

(Continued)

Feb. 22, 2006

(65)

Primary Examiner-Danh C Le
(74) Attorney, Agent, or Firm-Wilmer Cutler Pickering Hale
& DorrLLP

Prior Publication Data
US 2006/0240840 Al

Oct. 26, 2006
ABSTRACT

(57)
Related U.S. Application Data
(63)

Continuation-in-part of application No. 111261,988,
filed on Oct. 28, 2005, now Pat. No. 7,305,245.

(60)

Provisional application No. 60/654,811, filed on Feb.
22,2005.

(51 )

Int. Cl.
H04Q 7/20
U.S. Cl.

(52)

Methods and systems of continuously optimizing data in
WiFi positioning systems. A location-based services system
for WiFi-enabled devices calculates the position of WiFienabled devices. A WiFi-enabled device communicates with
WiFi access points within range of the WiFi-enabled device
so that observed WiFi access points identifY themselves. A
reference database is accessed to obtain information specifYing a recorded location for each observed WiFi access point.
The recorded location information for each of the observed
WiFi access points is used in conjunction with predefined
rules to determine whether an observed WiFi access point
should be included or excluded from a set of WiFi access
points. The recorded location information of only the WiFi
access points included in the set are used and the recorded
location information of the excluded WiFi access points are
excluded when calculating the geographical position of the
WiFi-enabled device.

(2006.01)
. 455/456.5; 455/456.6; 455/456.1;
340/539.13; 7011209

(58)

Field of Classification Search
455/456.5,
455/456.1,456.3; 340/539.13; 7011209
See application file for complete search history.

(56)

References Cited
U.S. PATENT DOCUMENTS
6,272,405
6,678,611
6,799,049
6,862,524

Bl
B2
Bl *
Bl *

8/2001
112004
9/2004
3/2005

Kubota et al.
Khavakh et al.
Zellner et al.
Nagda et al

,

AP

455/456.1
7011209

MAC

4 Claims, 6 Drawing Sheets

Access Point Evaluation: Data Flows

2
J

•
5

•
7

Observed APs compared

8---

against database

-79

~II observed A~~~;S Points 501
AP MAC address
1

OD:l1:~:Od:a9:5lJ

RSs1SiiIiiiS

/

Liltltude Lon itude

-75

42.677S4 -71.24573

Known

}-"~~-~SUSpectAccesSPoint504

L

~:(E:25:e8"':"~jl~.1I_Li~_~~~:~!~,5_~I":~~_~

1

OO:11:93:1f.24:!1

-71

Kt10Vlfl

~=C::·~O;~~'"502
AP MAC .dd,_

.5S S.'.

2

OO:11:93:0d:ae:l0 -83

§:_

~4!!:~g~~~21_~_
N~

11.

OO:06:25:eB:il3:55

Bad data filtered

42.6TI4S _71.24540

/
L....,. L,,, ,..d. /

•

New access points added
to database

New

+.-79

__

New

Newly Found Access Points

503
GSHFED_0000061

US 7,474,897 B2
Page 2

u.s. PATENT DOCUMENTS
2003/0125045
2003/0146835
2003/0225893
2004/0019679
2004/0039520
2004/0087317
2004/0124977
2004/0205234
2005/0020266
2005/0037775
2005/0192024
2005/0227711
2006/0009235
2006/0078122
2006/0092015
2006/0095348
2006/0095349
2006/0106850
2006/0128397
2006/0197704
2006/0200843
2006/0217131
2006/0240840
2007/0097511
2007/0126635
2007/0150516
2007/0202888
2007/0232892
2007/0258408
2008/0008117
2008/0008118
2008/0008119
2008/0008120
2008/0008121
2008/0033646
2008/0132170
2008/0139217
2008/0176583

Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al
Al

*

*

*
*

*

7/2003
8/2003
12/2003
112004
2/2004
5/2004
7/2004
10/2004
112005
2/2005
9/2005
10/2005
112006
4/2006
5/2006
5/2006
5/2006
5/2006
6/2006
9/2006
9/2006
9/2006
10/2006
5/2007
6/2007
6/2007
8/2007
10/2007
1112007
112008
112008
112008
112008
112008
2/2008
6/2008
6/2008
7/2008

Riley et al.
Carter ................... 340/539.13
Roese et al.
E et al.
Khavakh et al.
Caci
Biffar .................... 340/539.13
Barrack et al.
Backes et al.
Moeglein et al.
Sheynblat
Orwant et al. ............ 455/456.3
Sheynblat et al.
Dacosta
Agrawal et al.
340/539.13
Jones et al.
Morgan et al.
Morgan et al.
Choti et al ............... 455/456.1
Luzzatto et al.
Morgan et al.
Alizadeh-Shabdiz et al.
Morgan et al.
Das et al.
Houri
Morgan ct al.
Brachet et al.
Hirota
Alizadeh-Shabdiz et al.
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Morgan et al.
Alizadeh-Shabdiz et al.
Alizadeh-Shabdiz et al.
Brachct ct al.

OTHER PUBLICATIONS
International Search Report, International Application No. PCT/
US07/62721, mailed Nov. 9, 2007. (3 pages).

LaMarca, A., et aI., "Self-Mapping in 802.11 Location Systems,"
Intel Corporation, 2005.
U.S. Appl. No. 111261,848, Morgall et al.
U.S. Appl. No. 111359,154, Morgan et al.
U.S. Appl. No. 111359,144, Morgan et al.
U.S. Appl. No. 111359,271, Morgan et al.
U.S. Appl. No. 111430,079, Alizadeh-Shabdiz et al.
U.S. Appl. No. 111430,224, Alizadeh-Shabciz et al.
U.S. Appl. No. 111430,222, Alizadeh-Shabdiz et al.
U.S. Appl. No. 111429,862, Alizadeh-Shabdiz et al.
U.S. Appl. No. 111730,064, Alizadeh-Shabdiz et al.
Hellebrandt, M., et aI., "Estimating Position and Velocity of Mobile
in a Cellular Radio Network," IEEE Transactions on Vehicular Technology, vol. 46, No.1, Feb. 1997.
"Huffman Coding", Wikipedia, retrieved from http://en.wikipedia.
org/wiki/Huffman_coding, 2006.
Kim, M., et aI., "Risks ofusingAP locations discovered through war
driving," Lecture Notes in Computer Science, vol. 3968, 2006.
Krumm, J., et aI., "LOCADIO: Inferring Motion and Location from
Wi-Fi Signal Strengths," First Annual International Conference on
Mobile and Ubiquitous Systems: Networking and Services, Aug.
2004.
LaMarca, A., et aI., "Place Lab: Device Positioning Using Radio
Beacons in the Wild," Intel Corporation, 2004.
"Terminal Equipment and Protocols for Telernatic Services: Information Technology-Digital Compression and Coding of Continuous-Tome Still Images-Requirements and Guidelines."International Telecommunication Union, Sep. 1992.
Muthukrishnan, K., et aI., "Towards Smart Surroundings: Enabling
Techniques and Technologies for Localization," Lecture Notes in
Computer Science, vol. 3479, May 2005.
Kwan, M., "Graphic Progranmling Using Odd or Even Points," Chinese Math. 1, 1962.
Kirsncr, S., "One more way to find yourself," The Boston Globe, May
23, 2005, Retrieved from www.boston.com.
Kawabata, K., "Estimating Velocity Using Diversity Reception,"
IEEE,1994.
Hazas, M., et aI., "Location-Aware Computing Comes of Age,"
IEEE, vol. 37, Feb. 2004.
Griswold et aI., "ActiveCampus-Sustaining Educational Communities through Mobile Technology." UCSD CSE Technical Report
#CS200-0714,2002.
"Delta Encoding", Wikipedia, retrieved from http://en.wikipedia.
org/wiki/Delta_encoding, 2006.

* cited by examiner

GSHFED_0000062

~

7J).

•
·.•...•.

~

802.11
··········802.11

acc·~s.~...Point

i

102··· .

I

'~"
.~~./..._..._ / /../

access point
102

6-///'//

I

.
I

.,............•

~

802.11

access point
102

-,

.

User Device
101
•._...y

~,

802.11

•
. -

..............

access point
102

..../

,/

.,.,....../ .....

1

~

Reference
Database
104

....

Positioning
software
103
L.

=·

=

!

_ ._ '

_

a
'?"'
~

~C1\

N

~

~

I
!

\0

i
!

rJ1

I
j

....,.~

~

~

,

...." .....,..

=-

('D
('D

....

....
....
C1\

o

....•....•......•..•..........•

.........

.,..,.....•..•..
......."

(

,I

802.11
802.11
access point
102

G)
CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en
Co)

Figure 1

access point
102

d
r.n
......:J

~
......:J

~

00

\C
......:J

=
N

,.................................................................................................................................................................................................................................

.

j

l

l

i

,
!
Request: ......
Locationj

Scan
Request
Scanner
202

I....

---..
r'

Beacon
Probe

802.11
Radio
203

List of MAC addresses
and signal characteristics

!

~

Locations of known
access points

Locator

206

Send~

Quality Filter

List

i

•

~

~

Access
Points 204

~

~

=
~

"'"

201

I

f-

802.11

r

Beacon
... Broadcast

..-r--.

Look up MAC
addresses

Location
Application

.

~

7J).

I

-......,
./
"VJ

Access
Point
Reference

~

~

207

Send
List

Location
Calculation

r

208

Feedback File

...

212

I

'?"'
~

~C1\

N

.

,~

r

Location
Smoothing I -

I
I

209

~

~

\0

rJ1

=-

('D
('D

....
N

I
i

o

....

....

C1\

I
,
i

!

...

""

!Location delivered via API
Locltion delivered
via l'l'MEA stream
f

COM
Port

Application
interface

.....

210

d
r.n

I"'"

I

(211)

L

G)

..1

CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en
~

Figure 2

103

Positioning Software

......:J

~
......:J

~

00
\C
......:J

=
N

~

Device Centric Model

7J).

AAAAA
A AA
A

•

~
~

~

~

=
~

'?"'
~

Access PO;""

~C1\

102

N

~

~

\0

rJ1

~
Quality Filter 207

=-

('D
('D

Local AP
Database

301

Data Exchange Component
303

Reference
Database

205

....

(.H

o

....

C1\

Calculation 208

INew APs 3021 ~
d
r.n

Feedback Files

212

......:J

G)
CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en

01

......:J

~

WPS Location
Enabled Client Device (103)

Figure 3

~

00

\C
......:J

=
N

~

7J).

Network Centric Model

•

~

~

~

~

=
~

A

AA

'?"'
~

~C1\

Access pOiny
102 .

N

~

~

. . ."17 /

\0

I

I

Scanner 202 I

I Locator 20 1

11

rJ1

=-

Real-time Network interfaces 401

('D
('D

....

~

Reference
~ I Database

Quality Filter 2071-1
Feedback Data

~

~

....

0

C1\

205

d
r.n
......:J

~

G)
CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en
en

WPS Location
Enabled Client Device (103)

Figure 4

......:J

~

00
\C
......:J

=
N

IApmrMAC address---TRSS I
'1
iOO:1193:0d:a9:50 -75 '
2_~~11 :93:0d:ae:l0 -B3
3
jOO.Oc.41.0c.24.1f -B6
4 iOO:11 :93:0d:aa:1O -85
5 ,00:06:25:eB:c4:bb -B7
6 jOO:40:96:34:a6:23 -B5
7 100: 11 :93: H:24:1O
8 100:06:25:88: d3:55
9
100:40:96:31 :46:c6
MM'

J

~-_

•••••,.,••••

••• ~" •••••• MMM

j.M

,.,.,.,.,., _ __._

HHH ••••• H

,._..

,-_ -

_-_

~

Access Point Evaluation: Data Flows

7J'l
•
~
~

~

~

Observed APs compared
against database

.

•••••• _ •••••. __ •••••••• _ •• _

I

~

~C1\

lRsslSiiJiUS.---n:.atitl.deILongitude

'W

I

42. 67754

~

'?"'

All observed Access Points 501
lAP MAC address
OO:11 :93:0d:a9:50 1-75 IKnown

=
N

1-7 1.24573'

~

~

\0

:g~~~~-~~}~~~~~'~M~mj~'''142.6i720~7i:i14901suspect Access Point 504
5
..... _--7

OO:06:25:eB:c4:bb_ -B7
_.__ _
Inn·11 ·0':l·1

Known_

rJ1

_+....................... .

Bad data filtered

v>4:1lJ 1-71 IKnown

=-

('D
('D

....

Ul

9

100:40:96:31 :46:c6 1-94 IKnown

o

....

42,677771 -71.24510

C1\

Known Access Points 502
[APlMAcaiidress-IRssTstatUsiLaiitlicllil Longitude
I
j
.--L..-.---l--'

6-1
2

OO:11:93:0d:ae:l0~
m

-

I

New access points added
to database

d
r.n
......:J

G)
CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en
......

6 JlQ~4Q.:~§J4:a6:23 1-85

~
......:J

INew

~._.. JQ!LQ§.:~?:~~:.~}.:55_._I.~I9. __ JN~~

.......L ...._.... ......_J....
Newly Found Access Points 503

~

00
.........._......J

Figure 5

\C
......:J

=
N

- _ _ _ _ _ _ _ _.._ _ _-..-

.. .. .. ..
/

",

.. ..
",

/

..

.. .. .. .. .. ..

.. .. ..

~

.......

7J).

...........

/

/.,

/

///-------

//

//

I

. ~. '. ,

•

:

..'

/

•

i

i•
i

\
\
\

\.
"

\

/
G)
CJ)

:::I:
"T1

m

1°
o
o
o
o
o

en

00

i

\ "
"

\
\.

"

Max Threshold 604
Access points outside
this range are marked
as suspect

A!

i

~C1\

\,

\

!

I

i

;

Figure 6

=-

....

C1\

o

....

C1\

I

",/
/ ../.

/

rJ1
('D
('D

.

/./

•..._------_. -----_ ....• __..- - - / / ..-/.......
.._ .. _ .._ .._ .._ .._ .._ ..- ..- .. -

i

:

Access Points 602

\0

\

:
I

/

~

'

/

..-..--/

~

j

/

A

N

, '

1 :

•..•

..... ..........

~

,

!

,..

.............

'?"'

'.

!

i

'

..•,...

."."

~

\

"'----... .•.._--------///

..,..,..,..,..

=

, ..,..,\

\\\.

User Device
/
\ calculated location
.../
601'/

'.

~

\,

\

:
l :
I i !

\

~

' \ ' "'
" ,

(

\

~

\\

"

i . /
'

!

~

~

""'\.

l

J

",

-_._----_._-_.~-----,.,

//'A·----··---·-.....,

i'

,I

\..

..........

/.,

././

A

•

./
Adaptive Filter 603
expands outward until
the number of access
points exceeds the
minimum needed

d
r.n
-.l

~
-.l

~

00
\C
-.l

=
N

US 7,474,897 B2
1

2

CONTINUOUS DATA OPTIMIZATION BY
FILTERING AND POSITIONING SYSTEMS

culate their current geographic position and report that to a
user or to a service. Some examples of these services include
local weather, traffic updates, driving directions, child trackers, buddy finders and urban concierge services. These new
location sensitive devices rely on a variety of technologies
that all use the same general concept. Using radio signals
coming from known reference points, these devices can mathematically calculate the user's position relative to these reference points. Each ofthese approaches has its strengths and
weaknesses based on the radio technology and the positioning algorithms they employ.
The Global Positioning System (GPS) operated by the US
Govemment leverages dozens of orbiting satellites as reference points. These satellites broadcast radio signals that are
picked up by GPS receivers. The receivers measure the time it
took for that signal to reach to the receiver. After receiving
signals from three or more GPS satellites the receiver can
triangulate its position on the globe. For the system to work
effectively, the radio signals must reach the received with
little or no interference. Weather, buildings or structures and
foliage can cause interference because the receivers require a
clear line-of-sight to three or more satellites. Interference can
also be caused by a phenomenon known as multi-path. The
radio signals from the satellites bounce offphysical structures
causing multiple signals from the same satellite to reach a
receiver at different times. Since the receiver's calculation is
based on the time the signal took to reach the receiver, multipath signals confuse the receiver and cause substantial errors.
Cell tower triangulation is another method used by wireless
and cellular carriers to determine a user or device's location.
The wireless network and the handheld device communicate
with each other to share signal information that the network
can use to calculate the location of the device. This approach
was originally seen as a superior model to GPS since these
signals do not require direct line of site and can penetrate
buildings better. Unfortunately these approaches have proven
to be suboptimal due to the heterogeneous nature of the cellular tower hardware along with the issues of multi-path signals and the lack of uniformity in the positioning of cellular
towers.
Assisted GPS is a newer model that combines both GPS
and cellular tower techniques to produce a more accurate and
reliable location calculation for mobile users. In this model,
the wireless network attempts to help GPS improve its signal
reception by transmitting information about the clock offsets
ofthe GPS satellites and the general location ofthe user based
on the location of the connected cell tower. These techniques
can help GPS receivers deal with weaker signals that one
experiences indoors and helps the receiver obtain a 'fix' on the
closest satellites quicker providing a faster "first reading".
These systems have been plagued by slow response times and
poor accuracy-greater than I00 meters in downtown areas.
There have been some more recent alternative models
developed to try and address the known issues with GPS,
A-GPS and cell tower positioning. One of them, known as
TV-GPS, utilizes signals from television broadcast towers.
(See, e.g., Muthukrishnan, Maria Lijding, Paul Havinga,
Towards Smart Surroundings: Enabling Techniques and
Technologies for Localization, Lecture Notes in Computer
Science, Volume 3479, Jan 2Hazas, M., Scott, J., Krumm, J.:
Location-Aware Computing Comes ofAge. IEEE Computer,
37(2):95-97, February 2004 005, Pa005, Pages 350-362.) The
concept relies on the fact that most metropolitan areas have 3
or more TV broadcast towers. A proprietary hardware chip
receives TV signals from these various towers and uses the
known positions of these towers as reference points. The
challenges facing this model are the cost ofthe new hardware
receiver and the limitations of using such a small set of
reference points. For example, if a user is outside the perimeter of towers, the system has a difficult time providing rea-

CROSS-REFERENCE TO RELATED
APPLICATIONS
This application claims the benefit under 35 U.S.c. §119
(e) to the following Provisional Patent Application, the contents of which are incorporated herein in its entirety by reference:
U.S. Provisional Patent Application No. 60/654,811, filed
on Feb. 22, 2005, entitled Continuous Data Optimization in
Positioning System.
This application is a continuation-in-part of and claims the
benefit under 35 U.S.c. §120 to the following application, the
contents of which are incorporated herein in its entirety by
reference:
U.S. patent application Ser. No. 11/261,988, filed on Oct.
28, 2005, entitled Location-Based Services that Choose
Location Algorithms Based on Number of Detected Access
Points Within Range of User Device.
This application is related to the following U.S. patent
applications, filed on an even date herewith, entitled as follows:
U.S. patent application Ser. No. 11/359,154 Continuous
Data Optimization of Moved Access Points In Positioning
System; and
U.S. patent application Ser. No. 11/359,144 Continuous
Data Optimization of New Access Points in Positioning Systems.
This application is related to the following U.S. Patent
Applications filed on Oct. 28, 2005, entitled as follows:
U.S. patent application Ser. No. 11/261,848, Filed on Oct.
28, 2005, entitled Location Beacon Database;
U.S. patent application Ser. No. 11/261,898, Filed on Oct.
28,2005, entitled Server for Updating Location Beacon Database; and
U.S. patent application Ser. No. 11/261,987, Filed on Oct.
28, 2005, entitled Method and System for Building a Location Beacon Database.
This application is related to U.S. Provisional Patent Application No. 60/658,481, filed on Mar. 4, 2005, entitled Encoding and Compressing the Access Point Database.

10

15

20

25

30

35

40

BACKGROUND
1. Field of the Invention
The invention is generally related to location-based services and, more specifically, to methods ofcontinuously optimizing or improving the quality ofWiFi location data in such
systems.
2. Discussion of Related Art
In recent years the number of mobile computing devices
has increased dramatically creating the need for more
advanced mobile and wireless services. Mobile email,
walkie-talkie services, multi-player gaming and call following are examples of how new applications are emerging on
mobile devices. In addition, users are beginning to demand!
seek applications that not only utilize their current location
but also share that location information with others. Parents
wish to keep track of their children, supervisors need to track
the location of the company's delivery vehicles, and a business traveler looks to find the nearest pharmacy to pick up a
prescription. All of these examples require the individual to
know their own current location or that of someone else. To
date, we all rely on asking for directions, calling someone to
ask their whereabouts or having workers check-in from time
to time with their position.
Location-based services are an emerging area of mobile
applications that leverages the ability of new devices to cal-

45

50

55

60

65

GSHFED_0000069

US 7,474,897 B2

3

4

sonable accuracy. The classic example is a user along the
shoreline. Since there are no TV towers out in the ocean, there
is no way to provide reference symmetry among the reference
points resulting in a calculated positioning well inland of the
user.
Microsoft Corporation and Intel Corporation (via a
research group known as PlaceLab) have deployed a Wi-Fi
Location system using the access point locations acquired
from amateur scanners (known as "wardrivers") who submit
their Wi-Fi scan data to public community web sites. (See,
e.g., LaMarca, A., et. aI., Place Lab: Device Positioning
Using Radio Beacons in the Wild.) Examples include
WiGLE, Wi-FiMaps.com, Netstumbler.com and NodeDB.
Both Microsoft and Intel have developed their own client
software that utilizes this public wardriving data as reference
locations. Because individuals voluntarily supply the data the
systems suffer a number of performance and reliability problems. First, the data across the databases are not contemporaneous; some of the data is new while other portions are 3-4
years old. The age of the access point location is important
since over time access points can be moved or taken offline.
Second, the data is acquired using a variety of hardware and
software configurations. Every 802.11 radio and antenna has
different signal reception characteristics affecting the representation ofthe strength ofthe signal. Each scanning software
implementation scans for Wi-Fi signals in different ways
during different time intervals. Third, the user-supplied data
suffers from arterial bias. Because the data is self-reported by
individuals who are not following designed scanning routes,
the data tends to aggregate around heavily traffic areas. Arterial bias causes a resulting location pull towards main arteries
regardless of where the user is currently located causing
substantial accuracy errors. Fourth, these databases include
the calculated position of scanned access points rather than
the raw scanning data obtained by the 802.11 hardware. Each
of these databases calculates the access point location differently and each with a rudimentary weighted average formula.
The result is that many access points are indicated as being
located far from their actual locations including some access
points being incorrectly indicated as if they were located in
bodies of water.
There have been a number of commercial offerings of
Wi-Fi location systems targeted at indoor positioning. (See,
e.g., Kavitha Muthukrishnan, Maria Lijding, Paul Havinga,
Towards Smart Surroundings: Enabling Techniques and
Technologies for Localization, Lecture Notes in Computer
Science, Volume 3479, Jan 2Hazas, M., Scott, J., Krnmm, J.:
Location-Aware Computing Comes ofAge. IEEE Computer,
37(2):95-97, February 2004 005, Pa005, Pages 350-362.)
These systems are designed to address asset and people tracking within a controlled enviroument like a corporate campus,
a hospital facility or a shipping yard. The classic example is
having a system that can monitor the exact location of the
crash cart within the hospital so that when there is a cardiac
arrest the hospital staffdoesn't waste time locating the device.
The accuracy requirements for these use cases are very
demanding typically calling for 1-3 meter accuracy. These
systems use a variety oftechniques to fine tune their accuracy
including conducting detailed site surveys of every square
foot ofthe campus to measure radio signal propagation. They
also require a constant network connection so that the access
point and the client radio can exchange synchronization information similar to how A-GPS works. While these systems are
becoming more reliable for these indoor use cases, they are
ineffective in any wide-area deployment. It is impossible to
conduct the kind of detailed site survey required across an
entire city and there is no way to rely on a constant communication channel with 802.11 access points across an entire
metropolitan area to the extent required by these systems.

Most importantly outdoor radio propagation is fundamentally
different than indoor radio propagation rendering these
indoor positioning algorithms almost useless in a wide-area
scenano.
There are numerous 802.11 location scanning clients available that record the presence of 802.11 signals along with a
GPS location reading. These software applications are operated manually and produce a log file of the readings.
Examples of these applications are Netstumber, Kismet and
Wi-FiFoFum. Some hobbyists use these applications to mark
the locations of 802.11 access point signals they detect and
share them with each other. The management of this data and
the sharing of the information is all done manually. These
application do not perform any calculation as to the physical
location of the access point, they merely mark the location
from which the access point was detected.
Performance and reliability of the underlying positioning
system are the key drivers to the successful deployment ofany
location based service. Performance refers to the accuracy
levels that the system achieves for that given use case. Reliability refers to the percentage of time that the desired performance levels are achieved.

10

15

20

Performance

25
Local Search/Advertising
E911
Turn-by-turn driving directions
Gaming
Friend finders
30
Fleet management
Indoor asset tracking

35

40

45

50

55

60

65

Reliability

85%
<150 meters 95%
10-20 meters 95%
<50 meters 90%
<500 meters 80%
<10 meters 95%
<3 meters 95%
<100 meters

of the time
of the time
of the time
of the time
of the time
of the time
of the time

SUMMARY
The invention provides methods and systems of continuously optimizing data in WiFi positioning systems. For
example, data is monitored to infer whether a WiFi access
point has moved or is new. In this fashion, data is continuously optimized. Likewise, suspect data may be avoided
when determining the position of the WiFi-enabled device
using such a system.
Under one aspect of the invention, a location-based services system for WiFi-enabled devices calculates the position
ofWiFi-enabled devices. A WiFi-enabled device communicates with WiFi access points within range of the WiFi-enabled device so that observed WiFi access points identifY
themselves. A reference database is accessed to obtain information specifying a recorded location for each observed WiFi
access point. The recorded location information for each of
the observed WiFi access points is used in conjunction with
predefined rules to determine whether an observed WiFi
access point should be included or excluded from a set of
WiFi access points. The recorded location information of
only the WiFi access points included in the set are used and
the recorded location information of the excluded WiFi
access points are excluded when calculating the geographical
position of the WiFi-enabled device.
Under another aspect of the invention, signal strength
information for WiFi access points included in the set is
recorded and the signal strength information is used when
calculating the geographical position of the WiFi-enabled
device.
Under another aspect ofthe invention, the predefined rules
include rules to determine a reference point and to compare
the recorded location information for each of the observed
WiFi access points to the reference point, and wherein WiFi
access points having a recorded location within a predefined

GSHFED_0000070

US 7,474,897 B2

5

6

threshold distance of the reference point are included in the
set and wherein WiFi access points having a recorded location
in excess ofthe predefined threshold distance ofthe reference
point are excluded from the set.
Under another aspect of the invention, the reference point
is determined by identifYing a cluster ofWiFi access points
and determining an average position ofthe WiFi access points
in the cluster.

the current access point locations in the Access Point Reference Database by comparing the observed readings against
the recorded readings in the database. If the client determines
that the observed readings fall outside the bounds of what
should be expected based on the recorded readings, then the
access point is marked as suspect. That suspect reading is
logged into a feedback system for reporting back to the centrallocation Access Point Reference Database.
Under another embodiment of the invention, a WPS client
device D.lters identified suspect access points out oflhe triangulation calculation ofthe WPS client device in real time so as
not to introduce bad data into the location calculation.
Under another embodiment of the invention, a WPS client
device scans for access points to determine the physicallocation ofthe device and identifies access points that do not exist
in the current Access Point Reference Database. After the
known access points are used to calculate the device's current
location, those newly found access points are recorded back
to the centrallocationAccess Point Reference Database using
the calculated location of the known access points to help
determine their position, along with the observed power reading.
Under another embodiment of the invention, a device centric WPS client device periodically connects to the central
location Access Point Reference Database to download the
latest access point data. The WPS client device also uploads
all feedback data about newly observed access points and
suspect access points. This data is then fed into the central
10cationAccess Point Reference Database processing to recalibrate the overall system.
Under another embodiment of the invention, a network
centric WPS client device directly records feedback data
about newly observed access points and suspect access points
into the central location Access Point Reference Database in
real time.
By enlisting the WPS client device to continuously update
the Access Point Reference Database with information on
new and suspect access points, the WiFi positioning system
provides higher quality data than a system scanned solely by
the provider. Over time, WiFi access points are continually
added and moved. Embodiments of the described invention
provide systems and methods to ensure that the Access Point
Reference Database is self-healing and self-expanding, providing optimal positioning data that continually reflects additions and changes to available access points. As more user
client devices are deployed, the quality of the Access Point
Reference Database improves because information in the
database is updated more frequently.
FIG. 1 depicts a portion of a preferred embodiment of a
Wi-Fi positioning system (WPS). The positioning system
includes positioning software [103] that resides on a usercomputing device [101]. Throughout a particular coverage
area there are fixed wireless access points [102] that broadcast
information using control/common charmel broadcast signals. The client device monitors the broadcast signal or
requests its transmission via a probe request. Each access
point contains a unique hardware identifier known as a MAC
address. The client positioning software receives signal beacons or probe responses from the 802.11 access points in
range and calculates the geographic location of the computing device using characteristics from the received signal beacons or probe responses.
The positioning software is described in greater detail with
reference to FIG. 2, which depicts exemplary components of
positioning software 103. Typically, in the user device
embodiment of FIG. 1 there is an application or service [201]
that utilizes location readings to provide some value to an end
user (for example, driving directions). This location application makes a request ofthe positioning software for the location of the device at that particular moment. The location

I3RIEr DESCRIPTION or DRAWINGS

In the drawing,
FIG. 1 depicts certain embodiments ofa Wi-Fi positioning
system;
FIG. 2 depicts an exemplary architecture of positioning
software according to certain embodiments of the invention;
FIG. 3 depicts the data transfer process in certain client
device centric embodiments;
FIG. 4 depicts the data transfer process in certain network
centric embodiments;
FIG. 5 depicts the data flows for the quality filtering and
feedback process; and
FIG. 6 depicts the operation ofthe Adaptive Filter in certain
embodiments.
DETAILED DESCRIPTION
Preferred embodiments of the present invention provide a
system and a methodology for continuously maintaining and
updating location data in a WiFi positioning system (WPS)
using public and private 802.11 access points. Preferably,
clients using location data gathered by the system use techniques to avoid erroneous data in determining the Wi-Fi positions and use newly-discovered position information to
improve the quality of previously gathered and determined
position information. Certain embodiments communicate
with the central location Access Point Reference Database to
provide the location ofnewly discovered access points. Other
embodiments notifY the central location Access Point Reference Database of access points whose readings fall outside
the bounds of what should be expected, based on previous
readings of their location. Access points whose readings fall
outside ofwhat should be expected can be marked as suspect
and filtered out of the triangulation formula so as not to
introduce bad data into the location calculation.
Preferred embodiments of the invention build on techniques, systems and methods disclosed in earlier filed applications, including but not limited to U.S. patent application
Ser. No. 11/261,988, filed on Oct. 28, 2005, entitled LocationBased Services that Choose Location Algorithms Based on
Number of Detected Access Points Within Range of User
Device, the contents of which are hereby incorporated by
reference in its entirety. Those applications taught specific
ways to gather high quality location data for WiFi access
points so that such data may be used in location based services
to determine the geographic position of a WiFi-enabled
device utilizing such services. In the present case, new techniques are disclosed for continuously monitoring and
improving such data, for example by users detecting new
access points in a target area or inferring that access points
have moved. The present techniques, however, are not limited
to systems and methods disclosed in the incorporated patent
applications. Instead those applications disclose but one
framework or context in which the present techniques may be
implemented. Thus, while reference to such systems and
applications may be helpful, it is not believed necessary to
understand the present embodiments or inventions.
Under one embodiment of the invention, a WPS client
device scans for access points to determine the physicallocation ofthe WPS client device, then it calculates the quality of

10

15

20

25

30

35

40

45

50

55

60

65

GSHFED_0000071

US 7,474,897 B2
7

8

application can be initiated continuously every elapsed period
of time (every 1 second for example) or one time on demand
by another application or user.
In FIG. 2, the location application makes a request of the
positioning software to interrogate all access points within
range at a particular moment and to determine which access
points are suspect because the observed data does not correspond to the calculated location in the Reference Database.
The information on suspect access points collected by the
location application is used to optimize the position information in the Access Point Reference Database either in real time
or at some later time.
In the embodiment depicted in FIG. 2, the location application or service request initiates the scanner [202], which
makes a "scan request" to the 802.11 radio [203] on the
device. The 802.11 radio sends out a probe request to all
802.11 access points [204] within range. According to the
802.11 protocol, those access points in receipt of a probe
request will transmit a broadcast beacon containing information about the access point. That beacon includes the MAC
address of the device, the network name, the precise version
of the protocol that it supports and its security configuration
along with information about how to connect to the device.
The 802.11 radio collects this information from each access
point that responds, calculates the received signal strength
("RSS") of each access point observed, and sends the identification and RSS information back to the scanner.
The scanner passes this array of access points to the Locator [206] which checks the MAC addresses of each observed
access point against the Access Point Reference Database
[205]. This database can either be located on the device or
remotely over a network connection. The Access Point Reference Database contains the raw 802.11 scanning data plus
the calculated location for each access point that is known to
the system. FIG. 5 describes the access point evaluation process in more detail. The list ofobserved access points [501] is
obtained from the Scanner and the Locator [206] searches for
each access point in the Access Point Reference Database.
For each access point found in the Access Point Reference
Database the recorded location is retrieved [502]. The Locator passes this collection of location information for known
access points [502] along with the signal characteristics
returned from each access point to the Quality Filter [207].
This filter determines if any of the access points have moved
since they were added to the Access Point Reference Database and works continually to improve the overall system.
The Quality Filter marks access points that fail the quality
algorithm as "suspect" [504]. After removing bad data
records, the Filter sends the remaining access points to the
Location Calculation component [208]. Using the set ofvalidated reference data from the Access Point Reference Database and the signal strength readings from the Scanner, the
Location Calculation component computes the location ofthe
device at that moment. The Location Calculation component
also calculates the position of any newly observed access
points [503] not found in the Access Point Reference Database. The raw scanning data and the location of new access
points are stored in the Feedback File [212] as can be seen in
FIG. 2. This feedback is either saved locally on the device for
later transmission to the server or sent to the server in real
time. Before location data for known access points is sent
back to the Locator, it is processed by the Smoothing engine
[209] which averages a past series of location readings to
remove any erratic readings from the previous calculation.
The adjusted location data is then sent back to the Locator.
The calculated location readings produced by the Locator
are communicated to these location-based applications [201]
through the Application Interface [210] which includes an
application programming interface (API) or via a virtual GPS
capability [211]. GPS receivers commnnicate their location

readings using proprietary messages or using the location
standard like the one developed by the National Marine Electronics Association (NMEA). Connecting into the device
using a standard interface such as a COM port on the machine
retrieves the messages. Certain embodiments ofthe invention
include a virtual GPS capability that allows any GPS compatible application to communicate with this new positioning
system without have to alter the communication model or
messages.
The location calculations are produced using a series of
positioning algorithms intended to turn noisy data flows into
reliable and steady location readings. The client software
compares the list of observed access points along with their
calculated signal strengths to weight the location of user to
determine precise location of the device user. A variety of
techniques are employed including simple signal strength
weighted average models, nearest neighbor models combined
with triangulation techniques and adaptive smoothing based
on device velocity. Different algorithms perform better under
different scenarios and tend to be used together in hybrid
deployments to product the most accurate final readings. Preferred embodiments of the invention can use a number of
positioning algorithms. The decision of which algorithm to
use is driven by the number ofaccess points observed and the
user case application using it. The filtering models differ from
traditional positioning systems since traditional systems rely
on known reference points that never move. In the model of
preferred embodiments, this assumption of fixed locations of
access points is not made; the access points are not owned by
the positioning system so they may move or be taken offline.
The filtering techniques assume that some access points may
no longer be located in the same place and could cause a bad
location calculation. So the filtering algorithms attempt to
isolate the access points that have moved since their position
was recorded. The filters are dynamic and change based on
the number of access points observed at that moment. The
smoothing algorithms include simple position averaging as
well as advanced Bayesian logic including particle filters.
The velocity algorithms calculate device speed by estimating
the Doppler effect from the signal strength observations of
each access point.

10

15

20

25

30

35

40

Optimizing the Quality of Current Access Point Data
45

50

55

60

65

The Quality Filter [207] component compares the data
from the observed access points against the known access
points in a local or remote Access Point Reference Database.
For those observed access points whose MAC address is
located in the Access Point Reference Database, the Quality
Filter component then compares the information observed
with the location of the access points stored in the database.
The Quality Filter's [207] high level functionality is to
remove suspect access points from location calculation and as
the result, increase the accuracy of location estimation. The
Quality Filter uses only access points that are located in the
Access Point Reference Database. In some cases the Quality
Filter will have no current client device location history to
utilize for quality determination. The process for identifying
suspect access points for a no-history location estimation is
based on the location of the biggest cluster of the access
points stored in the database. The location of all the observed
access points that are recorded in the Access Point Reference
Database is considered and the average location ofthe biggest
cluster of access points is used as the reference point. A
cluster refers to distance-based clustering, which is a group of
access points with the distance of each access point from at
least one more access point in the cluster less than a threshold.

GSHFED_0000072

US 7,474,897 B2

9

10

The clustering algorithm is shown as follows and it is read as
"Node n belongs to cluster K, ifthere is at least one element
in cluster K like ni , which its distance from n is less than the
threshold";

and treats the next instance of location determination as a
no-history case and returns back to the clustering filter
described previously.
Real-Time Filtering of Suspect Access Points

3n i E (clusterK),ln-nil<d'hre'hold =>n E (clusterK)

Ifno cluster can be found then the mathematical median ofthe
access points serves as the best estimate of the distance average of a majority of the access points.
If the distance of any individual access point to the reference point is calculated to be more than a given distance, it is
ruled as a suspect access point and recorded in the Feedback
File to be sent back to the Access Point Reference Database.
Those suspect access points are then removed from the list of
access points used to calculate the location ofthe user device.
IdentifYing suspect access points for a client device when
there is a history of user movement is based on the previous
location ofthe client device. An exemplary implementation of
this determination is shown in FIG. 6. In an embodiment
where there is location history, the client device location
calculation is calculated continuously every period of time,
usually once every second. If the distance of any individual
observed access point [602] to that historical reference point
(the prior location calculation) is more than a given distance
[603], then it is ruled as a suspect access point, added to the
Feedback File and removed from calculation. The intent of
this filter is to try and use the access points that are nearest to
the user/device [601] to provide the highest potential accuracy. This filter is called an adaptive filter since the threshold
distance to filter suspect access points is changed dynamically. The threshold distance, which is used to identifY suspect access points, is changed dynamically based on the number of access points that are considered of good quality to
calculate location ofthe client device. Therefore, the adaptive
filter contains two factors, I) the minimum number of
required access points to locate a user device and 2) the
minimum threshold of distance to identify suspect access
points. The adaptive filter starts with the minimum threshold
of distance. If number of access points within that distance is
above the minimum number of access points necessary to
calculate the client location, then location of the device is
calculated. For example, if we find five access points which
are within 20 meters ofthe prior reading, then we filter out all
observed access points greater than 20 meters. If the filter
criteria is not met then the adaptive filter threshold [603] of
the distance is increased until the minimum number of access
points is considered or the maximum acceptable distance is
reached, and then the access points within the threshold distance are used to locate the user device. If no access point can
be located within the maximum threshold of distance [604]
from the previous location, then no location is calculated.
The positioning software continues to attempt to locate the
device based on its previous location up to a maximum given
duration of time. During this timeout period, if no location
can be determined, the maximum threshold of distance is
adjusted using the calculated velocity of the device. If the
vehicle is known to accelerate at a maximum of 6 mn/sls and
it was previously calculated as traveling at 20 mph, then it
would not possible be more than 42 meters away from the last
location two seconds later. This 42 meter distance limit is
used to adjust the outer boundary of the distance threshold if
the earlier time period adapter filters did not work. If it is too
difficult to calculate the actual velocity of client device, then
a maximum velocity threshold is used. If any access point is
calculated to be more than the maximum threshold of distance away from the reference point, it is marked as "suspect"
and logged to the Feedback File. If no access point can be
located within the maximum threshold ofthe distance during
the timeout period, then the adaptive filter ignores the history

10

15

20

25

30

Suspect access points are removed from the inputs into the
triangulation calculation and only valid access point locations
are used to triangulate the device position [502]. The inputs to
the triangulation algorithm are the set of valid access points
returned from the Quality Filter [207]. The triangulation component reads in the list of valid observed access point locations along with their respective signal strengths and calculates a latitude and longitude along with a Horizontal Position
Error (an estimate ofthe accuracy error at that moment). The
triangulation process also takes into consideration priorpositions to add additional filters to the scanning in order to apply
a smoothing process. By filtering out suspect access points we
provide the triangulation algorithm a more reliable set of
reference points to calculate against. Since access points can
move at any time, Positioning Software must account for the
dynamic nature of the reference points. Without conducting
filtering, the calculated location could result in a position
hundreds or thousands of miles away.
Suspect access points are not discarded completely. Rather
their newly observed locations are added backto the database
via the Feedback File [212] with different attributes indicating it as suspect, allowing the server to determine whether to
move the official location ofthat access point orjust keep it on
hold until its new location can be verified. By keeping it on
hold, this access point will not corrupt any other user's location calculation.
Adding New Access Point Data

35

40

45

50

55

60

Observed access points found in the Access Point Reference Database of known access points are used to calculate
the location of the client device after the elimination of suspect access points. Observed access points whose MAC
address are not found in the Access Point Reference Database
represent new access points [302][503] added since the database was created or updated. Those observed access points
not found in the known Access Point Reference Database are
added to the Feedback File as new access points. Those newly
found access points arc marked with the location ofthe client
device calculated by the positioning system itself along with
the observed signal strengths. This situation can occur in a
number of scenarios. In many cases a new access point is
purchased and deployed in the vicinity since the last physical
scauning by the scanning fleet. This is most often the case due
to the rapid expansion ofWi-Fi. In other cases, an access point
may be situated deep in the center of a building and the
scauning fleet was unable to detect that access point from the
street. Another example is that an access point may be located
up on a high floor of a tall building. These access points may
be difficult to detect from down on the street where the scanning fleet operates, but may be received by client devices that
pass closer to the building by users on foot or that enter the
building itself.
By having the system "self-expand" in this manner, the
coverage area of the system slowly expands deep into buildings and upwards in tall buildings. It also leverages the large
number of new access points that are deployed every day
across the world.
Updating the Central Database Server

65

With reference to FIG. 3, in some embodiments the Access
Point Reference Database of known access points will be
located on a central network server remote from the client

GSHFED_0000073

US 7,474,897 B2
11

12

device. The provisioning ofthis connection could be done via
any available network connection and is managed by the Data
Exchange Component [303]. Once authenticated, the client
device [103] identifies all the suspect and new access point
data from the local storage Feedback Files [212] and uploads
that data to the Access Point Reference Database [205].
In other embodiments the client device is connected to the
Access Point Reference Database all the time using a network
connection. FIG. 4 describes how the Network Centric
embodiment works. Rather than store the reference data
locally, the Locator [201] uses a set of Real-Time Network
interfaces [401] to communicate with the Access Point Reference Database. The Locator sends the list of observed
access points to the network interface which returns the list of
observed access points and whether the database has recorded
locations or whether the access points are newly found. The
process continues as before with the Quality Filter marking
suspect access points but the list of suspect access points is
sent to the Access Point Reference Database in real-time.
After the Calculation module determines the user device's
location, the list of newly found access points is marked with
the current location and sent back to the database in real-time.
This allows the database to be up to date at all times and to
remove the need for a Data Exchange Component.
After receiving feedback data, in either the device centric
or the network centric model, the Access Point Reference
Database determines whether to place suspect access points
'on hold' so as to prevent them from corrupting another user
device's location request. There are a number of techniques
being explored to optimize how this feedback data of suspect
access points will be used to improve the overall quality ofthe
database. There may be a voting scheme by which access
points are moved to new positions if more than one user
locates the access point in its new location. If only one user
has marked the access point as suspect then the access point is
marked as a low quality reading in its new position. Once its
new position is validated by another user then the quality
attribute of the access point is increased to reflect the higher
level of confidence the system has in the new position. The
more people who corroborate the access point's new position
the higher the quality level. The system's client software then
favors access points with high quality ratings over those that
have lower quality ratings.
In either the device centric or the network centric model,
the Access Point Reference Database collects the access point
identifying information, client device location and access
point signal strength information ofnewly discovered access
points from client devices. Once an acceptable number of
readings ofnewly discovered access points is collected by the
Access Point Reference Database, it can calculate a location

for the new access points based on the systems and methods
described in the related applications. The newly discovered
access points can then be supplied to client devices for use in
their location calculation.
It will be appreciated that the scope ofthe present invention
is not limited to the above-described embodiments, but rather
is defined by the appended claims; and that these claims will
encompass modifications of and improvements to what has
been described.
What is claimed is:

10

15

20

25

30

35

40

45

1. In a location-based services system for WiFi-enabled
devices, a method ofcalculating the position ofWiFi-enabled
devices comprising the acts of:
a) a WiFi-enabled device communicating with WiFi access
points within range of the WiFi-enabled device so that
observed WiFi access points identify themselves;
b) accessing a reference database to obtain information
specifYing a recorded location for each observed WiFi
access point;
c) using the recorded location information for each of the
observed WiFi access points in conjunction with predefined rules to determine whether an observed WiFi
access point should be included or excluded from a set of
WiFi access points;
d) using the recorded location information ofonly the WiFi
access points included in the set and omitting the
recorded location information of the excluded WiFi
access points to calculate the geographical position of
the WiFi-enabled device.
2. The method ofclaim 1 further including recording signal
strength information for WiFi access points included in the set
and using the signal strength information when calculating
the geographical position of the WiFi-enabled device.
3. The method of claim 1 wherein the predefined rules
include rules to determine a reference point and to compare
the recorded location information for each of the observed
WiFi access points to the reference point, and wherein WiFi
access points having a recorded location within a predefined
threshold distance ofthe reference point are included in theset
and wherein WiFi access points having a recorded location in
excess of the predefined threshold distance of the reference
point are excluded from the set.
4. The method of claim 3 wherein the reference point is
determined by identifying a cluster ofWiFi access points and
determining an average position of the WiFi access points in
the cluster.

* * * * *

GSHFED_0000074