Skyhook Wireless, Inc. v. GOOGLE, INC.

Filing 62

Joint Claim Construction and Prehearing Statement by Skyhook Wireless, Inc.. (Attachments: # 1 Exhibit 1, # 2 Exhibit 2, # 3 Exhibit 3, # 4 Exhibit 4, # 5 Exhibit 5, # 6 Exhibit 6, # 7 Exhibit 7, # 8 Exhibit 8, # 9 Exhibit 9, # 10 Exhibit 10, # 11 Exhibit 11, # 12 Exhibit 12, # 13 Exhibit 13, # 14 Exhibit 14, # 15 Exhibit 15, # 16 Exhibit 16, # 17 Exhibit 17, # 18 Exhibit 18, # 19 Exhibit 19, # 20 Exhibit 20, # 21 Exhibit 21, # 22 Exhibit 22, # 23 Exhibit 23, # 24 Exhibit 24, # 25 Exhibit 25, # 26 Exhibit 26, # 27 Exhibit 27, # 28 Exhibit 28, # 29 Exhibit 29, # 30 Exhibit 30, # 31 Exhibit 31, # 32 Exhibit 32, # 33 Exhibit 33, # 34 Exhibit 34, # 35 Exhibit 35, # 36 Exhibit 36, # 37 Exhibit 37, # 38 Exhibit 38, # 39 Exhibit 39, # 40 Exhibit 40, # 41 Exhibit 41, # 42 Exhibit 42, # 43 Exhibit 43, # 44 Exhibit 44, # 45 Exhibit 45, # 46 Exhibit 46, # 47 Exhibit 47, # 48 Exhibit 48, # 49 Exhibit 49)(Lu, Samuel)

EXHIBIT 1

111111111111111111111111111111111111111111111111111111111111111111111111111
US007305245B2

United States Patent

(10)

Alizadeh-Shabdiz et al.

(12)

(45)

(54)

LOCATION-BASED SERVICES THAT
CHOOSE LOCATION ALGORITHMS BASED
ON NUMBER OF DETECTED ACCESS
POINTS WITHIN RANGE OF USER DEVICE

(75)

Inventors: Farshid Alizadeh-Shabdiz, Wayland,
MA (US); Russel Kipp Jones, Roswell,
GA (US); Edward James Morgan,
Needham, MA (US); Michael George
Shean, Boston, MA (US)

(73)

Notice:

2006/0095348
2006/0095349
2006/0200843
2006/0217131

Filed:

Primary Examiner-Danh Le
(74) Attorney, Agent, or Firm-Wilmer Cutler Pickering
Hale & Dorr LLP
(57)

Prior Publication Data
US 2006/0217131 Al

Sep. 28, 2006

Related U.S. Application Data
(60)

Provisional application No. 60/623,108, filed on Oct.
29,2004.

(51)

Int. Cl.
H04Q 7/20
(2006.01)
U.S. Cl.
455/456.6; 455/456.5;
455/456.1; 370/328; 342/357.02; 340/572.4
455/456.6,
Field of Classification Search
455/456.5,456.1; 370/328; 342/357.02;
340/572.4
See application file for complete search history.

(52)
(58)

References Cited

(56)

ABSTRACT

A location beacon database and server, method of building
location beacon database, and location based service using
same. Wi-Fi access points are located in a target geographical area to build a reference database of locations of Wi-Fi
access points. At least one vehicle is deployed including at
least one scanning device having a GPS device and a Wi-Fi
radio device and including a Wi-Fi antenna system. The
target area is traversed in a programmatic route to avoid
arterial bias. The programmatic route includes substantially
all drivable streets in the target geographical area and solves
an Eulerian cycle problem of a graph represented by said
drivable streets. While traversing the target area, periodically receive the GPS coordinates of the GPS device. While
traversing the target area, detecting Wi-Fi signals from
Wi-Fi access points in range of the Wi-Fi device and
recording identity infonnation of the detected Wi-Fi access
point in conjunction with GPS location information of the
vehicle when the detection of the Wi-Fi access point was
made. The location information is used to reverse triangulate
the position of the detected Wi-Fi access point; and the
position of the detected access point is recorded in a reference database.

Oct. 28, 2005

(65)

Jones et al.
Morgan et al.
Morgan et al.
Alizadeh-Shabdiz et al.

(Continued)

Appl. No.: 111261,988

(22)

5/2006
5/2006
9/2006
9/2006

U.S. Appl. No. 11/261,848, filed Oct. 25, 2005, Morgan et al.

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

(21)

Al
Al
Al
Al

OTHER PUBLICATIONS

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

( *)

Patent No.:
US 7,305,245 B2
Date of Patent:
Dec. 4, 2007

U.S. PATENT DOCUMENTS
6,888,811 B2

10 Claims, 11 Drawing Sheets

5/2005 Eaton et al.

Scan
Request
Scanner
902

List of MAC addresses
and signal charactcnstlcs
~~l'ii;i;'i~~~=---.J

I

Looku MAC

Locations ofknown
accesspomts

Location
Application
901

ocation delivered via API
Application
interface
910

Loea ion delivered
VIa MEAstream

L

.

. .

.

..__.
103

..__..

.

_

US 7,305,245 B2
Page 2
OTHER PUBLICATIONS
U.S. Appl. No. 11/359,154, filed Feb. 22, 2006, Morgan et al.
U.S. Appl. No. 11/359,144, filed Feb. 22, 2006, Morgan et al.
U.S. Appl. No. 11/359,271, filed Feb. 22, 2006, Morgan et al.
U.S. Appl. No. 111430,079, filed May 8, 2006, Alizadeh-Shabdiz et
al.
U.S. Appl. No. 11/430,224, filed May 8, 2006, Alizadeh-Shabciz et
al.
U.S. Appl. No. 111430,222, filed May 8, 2006, Alizadeh-Shabdiz et
al.
U.S. Appl. No. 111429,862, filed May 8, 2006, Alizadeh-Shabdiz et
al.
U.S. Appl. No. 111730,064, filed May 8, 2006, Alizadeh-Shabdiz et
al.
"Delta Encoding", Wikipedia, retrieved from http://en.wikipedia.
org/wiki/Delta_encoding, 2006.
Griswold et aI., "ActiveCarnpus-Sustaining Educational Communities through Mobile Technology." UCSD CSE Technical Report
#CS200-0714,2002.
Hellebrandt, M., et al., "Estimating Position and Velocity of Mobile
in a Cellular Radio Network," IEEE Transactions on Vehicular
Technology, vol. 46, No.1, Feb. 1997.
Hazas, M., et aI., "Location-Aware Computing Comes of Age,"
IEEE, vol. 37, Feb. 2004.

"Huffman Coding", Wikipedia, retrieved from http://en.wikipedia.
org/wiki/Huffman_coding, 2006.
Kawabata, K., "Estimating Velocity Using Diversity Reception,"
IEEE, 1994.
Kim, M., et aI., "Risks of using AP locations discovered through war
driving," Lecture Notes in Computer Science, vol. 3968, 2006.
Kirsner. S.. "One more way to find yourself," The Boston Globe,
May 23, 2005. Retrieved from www.boston.com.
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.
Kwan, M., "Graphic Progranuning Using Odd or Even Points,"
Chinese Math. 1, 1962.
LaMarca, A., et aI., "Place Lab: Device Positioning Using Radio
Beacons in the Wild," Intel Corporation, 2004.
Muthukrishnan, K., et aI., "Towards Smart Surroundings: Enabling
Techniques and Technologies for Localization," Lecture Notes in
Computer Science, vol. 3479, May 2005.
"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.

e
•

7J).

•

W!
I

.........~

~

~

:

--"&02.11

acc~ss...point
102....'__'"

,

.

/ //" ,

!
i

...

.........~"

.
///

.

!

j
I

.....\e. '

/

access point

/f

/

102

=
~

c

('D

•

,

...

~

N

......:J

Database
104

-..

~

o
o

~
Reference

rFJ

=....
o
....
....
....
('D
('D

.....

•

1

'

" ...
......

~
.........
.........
i

,

'

I

802.11

802.11

access point

access point
102

Figure 1

~

~

/ '

....~

Positioning
software
103
I

/

/

User Device
101

~/~
802.11

access point

102

i
i

~

802.11

access point

i

'--.

102

802.11

102

d

rJl
......:J

W

=
t it

N

~

tit

=

N

7J).

~ GPS satell'ite

GPS satell'ite

.

e
•

204

..

"'':;;~2.

•

~

204

~

~

~

\

=
~

Horizon

c

,/

('D

~

...

~

N

o
o

access point/
203 /
802.11
access point
203

......:J

802.11
access point
203

rFJ

=-

('D
('D

.....

N

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

o

d

rJl

Scanning Vehicle
201

Figure 2

......:J

W

=
t it

N

~

tit

=

N

e
•

Figure 3: Example scanning scenario showing arterial bias

7J).

•

~

Calculated
location of
Access Point 303

~

~

~

=
~

•
~

o

802.11
Access Point
309

c

('D

~

...

~

Q

~
~

~

N

o
o

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

......:J

Street 306

rFJ

=-

('D
('D

.....

(.H

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

o
•

-Str.;~i307m--m_m--m ~ mmm~~~!_~?m __m.
()

802.1 1
Access Point

nQ;_1

V~~~:I:i~~1

1------·

~
d

rJl
......:J

W

=
U'l

N

~

U'l

=

N

e
•
.....

...

~

Calculated
&.
location of
Access Point 403

-~-

--

7J).

•

~

~

~

~

=

802.1 I

....

•

AC<jpoint

~

~

802.l!

0 •

Access Point
.40

-----------------------------.

I -----------------------------.

802.11
Access Point
409

~

c

('D

~

...

~

N

~ -----------------------------~

o
o

Public Streets

......:J

. . ~2.l!

~cessPoint

rFJ

=-

('D
('D

.....

...

80Nl

802.11°• •

•

Access Point

J\,/sPoint

....

I

......

•

I

802.11
Access Point
408

·
•
•
•
I

802.11 ~
Access Point

802.11.
Acces~int

d

I

rJl

I

I
I

,*

......:J

I

I

Physical Building

......

I

I

~.
.....

Scanning
Vehicle 401

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

o

( \ 802.11
"
Access Point

.....

I

•

W

=
U 'l

N

~

U'l

=

N

e
•

7J).

Figure 5: Lack of Reference Symmetry
Calculated
location of
Access Points

"'-.'. ~. . . . . .
i
~"""-~"-"""-'I""'"''-~'''''''''''''''''I'''''-''''''' ~. . . ~
:

502

.....

I

~...............

./

/./"

I

I
I

...

.

•

"..
....

~

I

~

~

~

=

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

~

I

/

./

/

OJ
//

Public Streets

I

I

.,

~

..n A.mnm...n............m
.~-----

!

I

c

('D

i

i

...

~

N

o
o

I

......:J

rFJ

Calculated
Location of
User

=-

('D
('D

.....

503

Ul

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

o

---.,..,..~

II

:
I

I
I

I
I

<>.
I

I

Physical Building

I

!O

\
Radio range
of user
device

d

rJl
......:J

W

=
t it

N

~

tit

=

N

Calculated
location of
Access Points
602

e
•

Figure 6: Positioning with R~fere-ne-e . ·S·Ylll!lletry

'I
:
I

-'

/

,

. ,. . . . . . . I ': I

....

:
I

0

I

~~, ,

I

1 . /

7J).

I:

I

i

i

i

I

o

Calculated
Location of
User
603

c

('D

~

...

~

......:J

, - - - ,~ - ~ - - - - - ' i

o

\

rFJ

\

=-

('D
('D

.....

0\

o

I

I
I
I

~

N

I

\
\
I

=
o
o

:\
I

~

"\

Ii 1<>0

I!

~

.~

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

Public Streets

~

~

......

.
:

<)

•

"\.

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

o

'..

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

........

i ·1
I

··· · · . · · ··· ··l.

I

<>
Physical Building

I
I

,
I
I
I
I

,
I

. ....,
~

<>

Ratlio range
of user
device
604

d

rJl
......:J

W
=
u-.
N
~
u-.

=

N

e
•

7J).

•

~
~

~

/

~

=
~

c

('D

~

j

I

...

~

I

/
802.11
access point,
707

/

802.11
access point
707

7

Directional
Antennas
709

N

o
o

!

802.11
access point
707

......:J

I

rFJ

=-

('D
('D

.....

......:J

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

o

Figure 7: Client
Scanning Device

Local
Storage

~

Scanning
Client
704

GPS Device
705
802.11 radio
706

ScanningDevice 702

d

rJl
......:J

Scanning Vehicle 701
I

i

W

=
t it

N

~

tit

=

N

e
•

Figure 8: Central Network Server

7J).

•

~

~

I
I
I
I
I

Fleet
Management
Module

Parser &
Filter

803

: ..... ~
I···
•••

806

..•.•• I
••••
I

•

Data

••
Communication .::.. .
Module
••••
•

.

Reverse
Triangulation

807

804
Regional
Data Pack
Builder

805

/

Central
Network
Database
802

Scanning
Vehicles
801

••••

.II····

.

~

=
~

c

('D

~

...

~

N

o
o

......:J

rFJ

=-

('D
('D

.....

I

QO

•• I
•••

•••I •••

Map
Builder

~

~

.... I I - ,

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

o

: ..... b---c}-J

808
I
I
I
I

d

rJl
......:J

W

=
t it

N

~

tit

=

N

e
•

7J).

•

Scan
Request

!
Request!\ .....

Scanner
902

802.11
Radio
903

List of MAC addresses
- and signal characteristics

Beacon
Probe

..

Beacon
Broadcast

Locatio~

~

802.11
Access
Points 904

~

~

~

=
~

!

!

!

!

LookuD MAC
addresses

!
!

Locations of known
access points

I

!
i

!
!

I'-':IV:)

=:1
c

Access
Point
Reference
.......... Database

('D

~

...

~

N

o
o

j

!

......:J

i

Location
Application
901

Locator
906

!

I
!

S~nd.

LIst

Bad data
filter
907

Send
List

Loca

Location
Calculati on
908

~

Location
Smoothing
909

rFJ

=-

!

I
I

('D
('D

.....

+.

\0

o

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

I
f

!
Location delivered via API
;

!

..

COM
Port
(911)

Location delivered
via ~MEA stream
i
,
L

_

Application
interface
910

_

_ _

_

_

foll-

_

d

_

103

Figure 9: Positioning Software

_

_

_

.

rJl
",......:I
W

=
t it

N

~

tit

=

N

e
•
~
~

EJ
EJ

7J).

r
!

MNN ••••• _ - _ ••••••• _ - _

_ •••••••••••••••• _ . _ •••• _ _ ••••••• · · _ · · · · · · · · ·••• ·N •• •

"

_ _ ••••• _ •• _

_

.

•

~

----------=-----::-::---""':'"':"=------------"

r,

_D_ata_M_anager-1-".I..::..OO;:.;I"--_--"
r

~

System Manager 1002

~

~

GPS
Radio

GPS
Recorder

1012

1013

o

Radio

1007

1009

lOIS

c

User
Interface
Controller

Scanning
Data

Wi-Fi
Recorder

Error
Handling
and Logging

Radio
Manager

File
ManagerlOl

802.11

=
~

Backup
Data

1008

1006

lOll

('D

~

...

~

System
Reset

N

o
o

1016

1014

......:J

~

rFJ

=....
o
o
....
....
....

Upload Manager 1003
Hotspot
Detector

Create
Connection

1017

1018

Hotspot
Authenticatio
n

1019

('D
('D

Check
New Client
Version

Upload &
Verify Data

1021

1022

.....

Install
New Version

1023

704
Central
Network
Server

1025

d

rJl
......:J

W

=
t it

Figure 10: Scanning Client

N

~

tit

=

N

Random Scanning Model

Chinese Postman Scanning Model

e
•

7J).

•

~

x

~

~

Raw scanning
readings of
Access Point
1103

Raw scanning
readings of
Access Point
1106 X X

X
XX X

X

~

% X

X X X \.

X X
X

x

Xx
X

=

X

X

~

Xx
X

Calculated
position of
~ccess Point
1102

X

X

X
X
X

l

150 meters

X

Access
Point
1101

X

Calculated
position of
Access Point
1105

X

lJ'
~.

~

X

o
iJ:/?'

~
X

X
X

N
0
0
......:J

=....
....
....
....
....

X XX

X

XX

rFJ

('D
('D

X
X
X
X

X
X

,j;o,.
~

X

Error =
10 meters

l
X
X

~

~

Access
Point
1104

X

C

('D

Xx X

X

X

.....

0

*
l
d

rJl
......:J

X

W

=
t it

X

Figure 11: comparison of scanning models

N

~

tit

=

N

US 7,305,245 B2
1

2

LOCATION-BASED SERVICES THAT
CHOOSE LOCATION ALGORITHMS BASED
ON NUMBER OF DETECTED ACCESS
POINTS WITHIN RANGE OF USER DEVICE

satellites. Interference can also be caused by a phenomenon
known as multi-path. The radio signals from the satellites
bounce off physical 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, multi-path 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 of the GPS satellites and the general location of
the 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 100
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 of Age. IEEE Computer, 37(2):95-97, February 2004 005, Pa005, Pages 350362.) 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 of the
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 reasonable 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. a!., 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 nnmber 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

CROSS-REFERENCE TO RELATED
APPLICATIONS
This application claims the benefit under 35 U.S.c. §119
(e) of U.S. Provisional Patent Application No. 60/623,108,
filed on Oct. 29, 2004, entitled Wireless Data Scanning
Network for Building Location Beacon Database, which is
herein incorporated by reference in its entirety.
This application is related to the following U.S. patent
applications (11/261848; 11/261988; 11/261987), filed on an
even date herewith, entitled as follows:
Location Beacon Database;
Server for Updating Location Beacon Database; and
Method and System for Building a Location Beacon Database.

10

15

20

BACKGROUND
1. Field of the Invention
The invention generally related to location-base services
and, more specifically, to methods and systems of determining locations of Wi-Fi access points and using such information to locate a Wi-Fi-enabled device.
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 oftheir 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 checkin 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
calculate 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 of these 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
Government 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

25

30

35

40

45

50

55

60

65

US 7,305,245 B2

3

4

important since over time access points can be moved or
taken ofiline. 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 of the strength of the 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., Krumm, J.:
Location-Aware Computing Comes of Age. IEEE Computer, 37(2):95-97, February 2004 005, Pa005, Pages 350362.) These systems are designed to address asset and
people tracking within a controlled environment 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 staff doesn'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 of techniques to
fine tnne their accuracy including conducting detailed site
surveys of every square foot of the 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 scenario.
There are numerous 802.11 location scarming 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 of802.11 access point signals they detect
and share them with each other. The management ofthis 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 of
any 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.

Perf011llance

Local Search!Advertising
E911
Turn-by-tum driving directions
10 Gaming
Friend finders
Fleet management
Indoor asset tracking

15

20

25

30

35

40

45

50

55

<100 meters
<150 meters
10-20 meters
<50 meters
<500 meters
<10 meters
<3 meters

Reliability
85%
95%
95%
90%
80%
95%
95%

of tbe
of tbe
of tbe
of tbe
of tbe
of tbe
of tbe

time
time
time
time
time
time
time

SUMMARY
The invention provides a location beacon database and
server, method of building location beacon database, and
location based service using same.
Under another aspect of the invention, a user-device
having a Wi-Fi radio may be located. A reference database
of calculated locations ofWi-Fi access points in a target area
is provided. In response to a user application request to
determine a location of a user-device having a Wi-Fi radio,
the Wi-Fi device is triggered to transmit a request to all
Wi-Fi access points within range of the Wi-Fi device.
Messages are received from the Wi-Fi access points within
range of the Wi-Fi device, each message identifying the
Wi-Fi access point sending the message. The signal strength
of the messages received by the Wi-Fi access points is
calculated. The reference database is accessed to obtain the
calculated locations for the identified Wi-Fi access points.
Based on the number of Wi-Fi access points identified via
received messages, choosing a corresponding location-determination algorithm from a plurality of location-determination algorithms, said chosen algorithm being suited for the
number of identified Wi-Fi access points. The calculated
locations for the identified Wi-Fi access points and the signal
strengths of said received messages and the chosen locationdetermination algorithm are used to determine the location
of the user-device.
Under another aspect of the invention, the calculated
locations for the identified Wi-Fi access points are filtered to
determine if the corresponding Wi-Fi access points have
moved since the time the information about the Wi-Fi access
points was included in the reference database.
Under another aspect of the invention, the plurality of
location-determination algorithms includes a simple signal
strength weighted average model.
Under another aspect of the invention, the plurality of
location-determination algorithms includes a nearest neighbor model.
Under another aspect of the invention, the plurality of
location-determination algorithms includes a triangulation
technique.
Under another aspect of the invention, the plurality of
location-determination algorithms includes an adaptive
smoothing technique based on the device velocity.
Under another aspect of the invention, the choice of
location-determination algorithm is further based on the user
application making the location request.

60

BRIEF DESCRIPTION OF DRAWINGS

65

In the drawing,
FIG. 1 depicts certain embodiments of a Wi-Fi positioning system;
FIG. 2 depicts scanning vehicles including scanning
devices according to certain embodiments of the invention;

US 7,305,245 B2

5

6

FIG. 3 depicts an example of a scanning scenario to
illustrate the problem of arterial bias in data collection;
FIG. 4 depicts an example using a programmatic route for
a scanning vehicle according to certain embodiments of the
invention;
FIG. 5 depicts an example scenario to illustrate the
problem of lack of reference symmetry of Wi-Fi access
points in locating a user device;
FIG. 6 depicts an example scenario to illustrate reference
symmetry of Wi-Fi access points in locating a user device;
FIG. 7 depicts scanning vehicles including scanning
devices according to certain embodiments of the invention;
FIG. 8 depicts a central network server including a central
database ofWi-Fi access points according to certain embodiments of the invention;
FIG. 9 depicts an exemplary architecture of positioning
software according to certain embodiments of the invention;
FIG. 10 depicts an exemplary architecture of a scanning
client according to certain embodiments of the invention;
and
FIG. 11 compares and contrasts the effects of a random
scanning model with one using a model from the Chinese
postman routing algorithm.

the access points the gathering system has collected. The
power profile is a collection of readings that represent the
power of the signal from various locations. Using these
known locations, the client software calculates the relative
position of the user device [101] and determines its geographic coordinates in the form of latitude and longitude
readings. Those readings are then fed to location-based
applications such as friend finders, local search web sites,
fleet management systems and E911 services.
The positioning software is described in greater detail
with reference to FIG. 9, which depict exemplary components of positioning software 103. Typically there is an
application or service [901] that utilizes location readings to
provide some value to an end user (example, driving directions). This location application makes a request of the
positioning software for the location of the device at that
particular moment. That request initiates the scanner [902],
which makes a "scan request" to the 802.11 radio [903] on
the device. The 802.11 radio sends out a probe request to all
802.11 access points [904] 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 signal
strength of each access point and sends that back to the
scanner.
The scanner passes this array of access points to the
Locator [906] which checks the MAC addresses of each
observed access point against the Access Point Reference
Database [905]. This database can either be located on the
device or remotely over a network connection. The Access
Point Reference Database returns the location data for each
of the observed access points that are known to the system.
The Locator passes this collection of location information
along with the signal characteristics returned from each
access point to the Bad Data Filter [907]. This filter applies
a number of comparison tests against each access point to
determine if any of the access points have moved since they
were added to the access point database. After removing bad
data records, the Filter sends the remaining access points to
the Location Calculation component [908]. Using the reference data from the access point database and the signal
strength readings from the Scanner, the Location Calculation
component computes the location of the device at that
moment. Before that location data is sent back to the
Locator, it is processed by the Smoothing engine [909]
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 [901]
through the Application Interface [910] which includes an
application progrannning interface (API) or via a virtual
GPS capability [911]. 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 of
the 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

10

15

20

DETAILED DESCRIPTION
25

Preferred embodiments of the present invention provide a
system and a methodology for gathering reference location
data to enable a commercial positioning system using public
and private 802.11 access points. Preferably, the data is
gathered in a programmatic way to fully explore and cover
the streets of a target region. The programmatic approach
identifies as many Wi-Fi access points as possible. By
gathering location information about more access points,
preferred embodiments not only provide a larger collection
of location information about access points, but the location
information for each access point may be calculated with
more precision. Subsequently this larger set of more precise
data may be used by location services to more precisely
locate a user device utilizing preferred embodiments of the
invention. Certain embodiments 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 use location-determination algorithms based on the context ofthe user device at the time the
user requests a location. For example, the location-determination algorithm will be based on the number of Wi-Fi
access points identified or detected when a location request
is made, or based on the application making the request.
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 computing device [101]. Throughout a particular coverage area
there are fixed wireless access points [102] that broadcast
information using control/common channel 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 from the 802.11 access points in range and calculates the geographic location of the computing device using
characteristics from the signal beacons. Those characteristics include the unique identifier of the 802.11 access point,
known as the MAC address, and the strengths of the signal
reaching the client device. The client software compares the
observed 802.11 access points with those in its reference
database [104] of access points, which mayor may not
reside on the device as well. The reference database contains
the calculated geographic locations or power profile of all

30

35

40

45

50

55

60

65

US 7,305,245 B2
7

8

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 of access 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 ofiline. 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 Kalman filters. The
velocity algorithms calculate device speed by estimating the
Doppler effect from the signal strength observations of each
access point.

thoroughfare. As a result, over time the random driving
covers more and more ground by the cumulative coverage
shows a bias to the main roads, or arteries at the expense of
the smaller and surrounding roads. In FIG. 3, arteries [304]
and [305] are heavily traversed by the scanning vehicles
resulting in a healthy amount of scanning data for those
streets. But streets [306] and [307] are rarely, if ever,
covered because there is no frequent destination on those
streets and the arteries are more optimal travel roads. The
result is that access points [308] and [309] are not scanned
at all by the scanning vehicles so the positioning system will
struggle to identify a user who is traveling on streets [306]
and [307]. The result is that when the system attempts to
calculate the location of the access point from the scan data
it is limited to a biased collection of input data. FIG. 11
shows the difference in resulting data quality. As the scanning vehicle drives near the Access Point [1101], it records
a reading and its location continuously. The positioning
system must then calculate the location of the Access Point
[1102] using the entire set of observed data [1103]. In the
Random Scanning model the set of data is limited to one
main road passing by the access point. That forces the
system to calculate the access point's location near that road
rather than close to the access point itself.
Another approach is develop routing algorithms that
include every single street in the target area so as to avoid
arterial bias in the resulting collection of data thus producing
a more reliable positioning system for the end users. FIG. 4
describes an optimized routing algorithm known as the
Chinese Postman to calculate the most efficient driving route
for covering every single street in a target area. The Chinese
Postman routing algorithm is a known technique used by
postal agencies, utilities and census agencies and is a variant
of the Eulerian cycle problem. The Eulerian cycle is a
problem asking for the shortest tour of a graph which visits
each edge at least once. (See, e.g., Kwan, M. K. "Graphic
Programming Using Odd or Even Points." Chinese Math. I,
273-277, 1962.) Preferred embodiments of the invention
include a methodology for identifYing a target region for
coverage and then using the Chinese Postman routing algorithm for planning the vehicle route. The scanning vehicle
[401] follows the optimal route according to the algorithm
showing no bias to any street ensuring that all observable
access points are detected and mapped by the system. So, by
way of example, access points [408] and [409] are added to
the access point database using the Chinese Postman model
but would have been missed using the Random model.
Referring back to FIG. 11, with the Chinese Postman
Scanning model, the vehicle travels every single road getting as complete a set of scanning records [1106] for the
Access Point [1104]. The system can then calculate the
location [1105] ofthe access point with less error since it has
a more nniform distribution of scan data for access point
1104 than for access 1102. So the Chinese Postman Scanning model not only gathers more access points nniformly
across a target area but the resulting data produces more
accurate calculations of access point locations.

10

15

20

25

30

Gathering of Scan Data to Build Reference
Database
FIG. 2 depicts the components used to gather location
information for the various access points. A large fleet of
vehicles [201] is deployed to build the reference database
(104 of FIG. 1) for the positioning system. These vehicles
201 follow a programmatic route through target scan areas
to gather data in the most optimal fashion producing the
highest quality data. The target scan areas typically represent
a large metropolitan area including every single drivable
street in 15-20 mile radius. These vehicles are equipped with
scanning devices [202] designed to record the locations and
characteristics of 802.11 signals while traversing the coverage area. The scanning devices track the location of the
scanning vehicle every second using signal from GPS satellites [204]. The scanning device also tracks the presence of
any 802.11 access point within range and records the radio
characteristics ofthat access point signal along with the GPS
location of the scanning vehicle. The quality of the data
collected is greatly affected by the scanning methodology
employed by the scanning vehicles. Each model has its own
benefits and limitations. One approach, known as the Random Model, places scanning devices in vehicles as they are
conducting daily activities for business or personal use.
These vehicles could be delivery trucks, taxi cabs, traveling
salesman or just hobbyists. The concept is that over time
these vehicles will cover enough streets in their own random
fashion in order to build a reliable reference database. The
model does in fact provide a simple means to collect data but
the quality of the resulting data is negatively affected due to
issues of "arterial bias". FIG. 3 describes the challenge ofthe
random model. When scanning vehicles traverse routes
designed to solve other problems than gathering data (e.g.
delivering packages, people commuting to and from work)
they tend to follow destination routes. A destination route is
when a driver needs to get from A to B and seeks the fastest
route to get there. So the driver looks for the shortest route
to the nearest main artery whether it be a highway or a main

35

40

45

50

55

Higher Quality AP Locations

60

65

Once collected (or partially collected), the scanning data
is uploaded back to a central access point database (described later in this application) where it is processed. The
raw observation points for each access point are used to
reverse triangulate the actual physical location of the access
points or create a power profile representing the radio
propagation of that access point. In order to produce the
most accurate calculated location for a particular access
points or to create the most accurate power profile, the
scanning vehicle must observe the access point from as

US 7,305,245 B2
9

10

many different angles as possible. In the random model
[FIG. 3], many access points are observed from only one
street forcing the system to calculate their location directly
on the street [303]. These locations exhibit a directional bias
and are significantly different than the actual locations of
these access points [302]. Errors are introduced into a
positioning system when its reference point locations are
inaccurate. So in this positioning system, the accuracy of the
access point locations playa large role in the accuracy of the
end user positioning accuracy. Using the Chinese Postman
model [FIG. 4] the scanning vehicles detect a particular
access point from as many sides as possible of the building
housing the access point. This additional data greatly
improves the results of the reverse triangulation formula
used to calculate the location of the access points [403].
More details on the access point location quality is described
in connection with FIG. 11.
The scanning data collected from this system represents a
reliable proxy for the signal propagation pattern for each
access point in its specific environment. Every radio device
and associated surrounding environment produces a unique
signal fingerprint showing how far the signal reaches and
how strong the signal is in various locations within the signal
fingerprint. This fingerprint data is used in conjnnction with
the calculated access point location to drive high accuracy
for the positioning system. This fingerprint is also known as
a "power profile" since the signal strengths at each position
is measured as signal power in watts. The positioning system
can interpret the fingerprint data to indicate that a particular
signal strength of an 802.11 access point radio is associated
with a particular distance from that access point. Signal
fingerprinting techniques are used in indoor Wi-Fi positioning but have proved difficult to replicate in the wider area
outdoor environments because the difficulty associated with
collecting the fingerprint data. When the fingerprints or
power profiles of multiple access points are overlayed, the
positioning system can determine a device location merely
by finding the one position where the observed signal
strengths match the combined fingerprints. Preferred
embodiments of this invention provide a reliable system for
obtaining this fingerprint data across a massive coverage
area with millions of access points in order to utilize
fingerprint-based positioning algorithms.

Scanning Device

Reference Symmetry
Positioning systems typically work by having three or
more reference points aronnd the device being tracked.
These positioning systems use the radio signals from these
reference points in various ways to calculate the device's
current location. Significant errors occur when there are an
insufficient number of reference points or when the reference points lack balance or symmetry aronnd the user. As
illustrated in FIG. 5, the arterial bias that emerges from the
random model introduces many scenarios where the end
user [501] moves into physical areas in which there are only
recorded access point locations [502] on one side of them.
This lack of symmetry in the distribution of reference points
around the end user causes the positioning algorithms to
calculate the device location [503] with a great deal of error.
With Chinese Postman model of scanning for access points,
the user typically enconnters a physical location [FIG. 6] in
which there are numerous access point locations [602] on all
sides of the user [601] within the range [604] of the device's
802.11 radio. The resulting position calculation [603] has
reduced location bias and is more accurate as a result. FIG.
11 is another example showing the impact of quality location
calculations.

10

15

20

25

30

35

40

45

50

55

60

65

FIG. 7 depicts the details of a preferred embodiment of a
scanning device 702 used to detect and identify the various
Wi-Fi access points. A scanning vehicle [701] contains a
scanning device [702] that continuously scans the airways
for radio signals from GPS satellites [708] and 802.11 access
points [707]. The scanning device runs the scanning client
software [704] that controls the entire process. The scanning
client activates both the GPS receiver [705] and the 802.11
radio [706]. The GPS receiver is set into a continuous
reception mode calculating the geographic location of the
device every second. That calculation is read by the scanning client and stored in the local data storage [703]. The
scanning client initiates the 802.11 radio and begins sending
out 802.11 probe requests using directional antennas [709].
Any 802.11 access point [707] within range of that probe
request responds with a signal beacon as per the 802.11
protocol. The responding signal beacons contains the network name of the access point (known as an SSID), the
MAC address of the access point device as well as other
meta information about the access point. The responding
signals reach each ofthe directional antennas with a different
strength of signal based on the vector of origin and the
proximity of the access point. That vector is recorded along
with the identifier of that particular antenna and the meta
information about the access point. This probe-receiverecord process occurs continuously every tenth of a second.
The scanning device deployed is a combination of the iPAQ
4155 Pocket PC and Powered GPS PDA Mount Cradle with
integrated SiRF II type GPS receiver with XTrac v. 2.0
firmware.
The Scanning Client 704 of certain embodiments is
described in connection with FIG. 10. The client consist of
three main components, the Data Manager [1001], the
System Manager [1002] and the Upload Manager [1003].
The Data Manager [1001] controls the operations of both the
GPS radio [1006] and the 802.11 radio [1007]. The Data
Manager controls when and how often these radios scan for
signals and process those signals. The GPS radio once
activated receives signals from GPS satellites [1004] and
calculates its geographic location. The GPS recorder [1008]
logs all of those readings every second and sends them to the
File Manager [1010]. The Wi-Fi Recorder [1009] activates
the 802.11 Radio to scan every tenth of a second, and
associates those 802.11 readings with the GPS readings
coming from the GPS radio and sends the resulting data to
the File Manager. The File Manager receives scan data from
both the GPS Recorder and Wi-Fi Recorder and creates
storage files on the device. This process continues the entire
time the device is operational and both radios are functioning
In the Upload Manager [1003] there is a Hotspot Detector
[1017] that monitors the 802.11 scanning results to look for
the configured network of public hotspots [1024] (e.g.
T-mobile) that the device is authorized to access. Once it
detects a valid Hotspot it notifies the user of its presence.
The user can select to connect to the hotspot by activating
the Create Connection component [1018]. This component
associates with the hotspot's access point and creates an
802.11 connection. Then the Hotspot Authentication module
[1019] supplies valid authentication information for the
device. The hotspot validates the acconnt and then provides
network access to the device. The Upload Manager then
initiates the Upload Server Authentication process [1020] to
connect to the Central Network Server [1025] and provides
valid authentication information. Once authenticated, the
Upload & Data Verification module [1021] is initiated. This
module retrieves the scan data from the Scanning Data store
[1011] and uploads the data to the Central Network Server

US 7,305,245 B2
11

12

using FTP. The Central Network Server initiates a process to
store all the data in the Central Access Point Database. After
the upload is complete the upload process moves the scan
data from the Scanning Data store [1011] to the Backup Data
store [1012] on the device. Once the upload is completed
and verified, the New Version module [1022] checks the
Central Network Server to determine if there is a new
version of the client software available for the device. If
there is a new version, the software is downloaded and the
New Version Installation [1023] process begins to upgrade
the client software. Once the installation process is completed the connection with the Central Network Server is
terminated, the connection with the hotspot is terminated
and the device returns to normal scanning operation.
Included in the Scanning Client 704 are a set of utilities
that help to manage the device and reduce system errors. The
Radio Manager [1013] monitors the operation of the GPS
Radio and the Wi-Fi Radio to make sure they are functioning
properly. If the Radio Manager encounters a problem with
one of the radios, it will restart the radio. The User Interface
Controller [1014] presents the tools and updates to the user
so they can operate the device effectively. The Error Handling and Logging [1015] records all system issues to the
device and alerts the user so they can address. The System
Restart module [1016] is called when issues cannot be
resolved. This module shuts down the device and restarts the
hardware, operating system and scanning client to ensure
proper operation.
The lflO of a second 802.11 scanning interval was chosen
since it provides the optimal scanning period for 802.11
under these conditions using offthe shelfhardware. 802.11 bl
gin operates using 14 channels of the unlicensed spectrum.
An individual access point broadcasts its signal beacon over
one ofthose channels at any given time. The scanning device
needs to survey each channel in order to observe as many
access points as possible. The scanning interval is correlated
with the average speed of the scanning vehicle to optimize
how the scanning client covers the frequency real estate of
a particular region.

the readings are 5 kilometers away then those outliers are
removed by the filter and stored in a corrupted table of the
database for further analysis. In particular, the system first
calculates the weighted centroid for the access point using
all reported data. It then determines the standard deviation
based on the distribution of the reported locations. The
system uses a definable threshold based on the sigma of this
distribution to filter out access points that are in error. Once
these error records are marked, the centroid is recalculated
with the remaining location records to determine the final
centroid using the Reverse Triangulation method described
below.
Note that the error records may be the result of an access
point that has moved. In this instance, the centroid for the
access points will quickly "snap" to the new location based
on the preponderance ofrecords. An additional enhancement
to the algorithm would include a weighting value based on
the age ofthe records such that new records represent a more
significant indication of the present location for a given
access point.
Once the parsing process has been completed the central
network system initiates the Reverse Triangulation model
[804] begins processing the new data. During this process 1)
new access points are added to the database and their
physical location is calculated and 2) existing access points
are repositioned based on any new data recorded by the
scanners. The reverse triangulation algorithm factors in the
number of records and their associated signal strengths to
weight stronger signal readings more than weaker signals
with a quasi weighted average model.
During data gathering, a WPS user is equipped with a
Wi-Fi receiver device which measures Received Signal
Strength (RSS) from all the available Wi-Fi access points,
and then extracts location information of corresponding
access points. RSS value of access points are shown as
follows:

10

15

20

25

30

35

Central Network Server
40

With reference to FIG. 8, the fleet of vehicles perform
their scanning routines while driving their pre-designed
routes. Periodically each vehicle [801] will connect to an
available 802.11 access point and authenticate with the Data
Communications Module [807] of the Central Network
Server. Typically the access points used for communicating
with the Central Network Server are public hotspots like
those operated by T-Mobile ensuring reliable and metered
access. The provisioning of this connection could be done
via any available public access point. The scanning vehicle
stops at a nearby hotspot location and begins the process of
connecting to the access point. Once authenticated, the
scanning client [704] identifies all the recently collected
scan data from the local storage [703] and uploads that data
to the Central Network Database [802].
Once the data has been uploaded to the database, the
Parser and Filter process [803] begins. The Parser and Filter
process reads all of the upload scanning data and loads it up
into the appropriate tables of the database. During this
exercise the data is evaluated for quality issues. In some
cases the GPS receiver may record erroneous or error
records for some period of time, which could negatively
affect the final access point location calculation. The parser
and filter process identifies these bad records and either
corrects them or removes them from the system. The filtering process users clustering techniques to weed out error
prone GPS readings. For example, if 90% ofthe readings are
within 200 meters of each other but the remaining 10% of

{RSS j, RSS b

...

RSS n }

If the corresponding recorded GPS location of access
point i is denoted by {Lat" Long,}, and the calculated access
point location is denoted by {Lat" Long,}, the triangulated
position is found by applying the algorithm as follows:
45

I~

lO R55 ;/10 !.at;

i=l

50

!.atu = - n = - - - - - -

L~

lO RSS;/10

i=l

55

I~

lO RSS;/10 Long;

i=l

Longu = - ' - - ' - - n - - - - -

L~

lO RSS;/10

i=l

60

65

The quad root of power is selected to ease the implementation of the algorithm, since quad root is synonymous to
taking two square roots.
The second point is referring to adjusting the dynamic
range of coefficients. If the dynamic range of coefficients is
a concern, the coefficient of the algorithm can be divided by
a constant number, e.g.,

US 7,305,245 B2
14

13

f' ~

lO R55 ;/10

U
C
Lat;
i=l
Lotu = -------,===-

!~
i=l

f' ~ 10

U

10

RS5 ;/10

C

Long;

i=l

Longu = --'--''------===~

!~
i=l

The Parameter C can be any number and it does not
impact the results, theoretically. Since, the weighted average
is based on the ratio of the coefficients and not the absolute
value, theoretically, dividing all the coefficients by a constant value, C, does not impact the results, but it changes the
dynamic range of the coefficient values.
This final {Lat" Long,} is then used as the final centroid
value for the location of that access point. The latitude and
longitude will then be stored in the database including a
timestamp to indicate the freshness of the triangulation
calculation.
After the Central Network Database has been updated and
each access point has been repositioned, the Data Pack
Builder [805] creates subsets of the database based on
regions of the country or world. The pack builder facilitates
distribution of the database for a variety of use cases in
which only region certain geographies are of interest. The
pack builder is configured with region coordinates representing countries, time zones and metropolitan areas. Utilizing this technique a user can download just the location
data for the west coast ofthe United States. The pack builder
segments the data records and then compresses them.
The Fleet Management Module [806] helps operations
personnel manage the scanning vehicles and ensure they are
adhering the routing procedures. This module processes all
the scan data and builds the location track for each vehicle
in the system. The operations manager can create maps of
the vehicle track using the Map Builder [808] to visually
inspect the coverage for a particular region. The GPS
tracking data from each device is reviewed with route
mapping software to verifY completion of coverage and to
identify missed areas. This ability to audit and verify uniform coverage ensures that the system is getting the best data
possible. The module also calculates the driving time of the
vehicle to determine average speed and to subtract any idle
time. These outputs are used to monitor efficiency of the
overall system and in planning of future coverage.
It will be appreciated that the scope of the present
invention is not limited to the above described embodiments, but rather is defined by the appended claims; and that

15

20

25

30

35

40

45

50

these claims will encompass modifications of and improvements to what has been described.
What is claimed is:
1. A method of locating a user-device having a Wi-Fi
radio, comprising:
providing a reference database of calculated locations of
Wi-Fi access points in a target area;
in response to a user application request to determine a
location of a user-device having a Wi-Fi radio, triggering the Wi-Fi device to transmit a request to all Wi-Fi
access points within range of the Wi-Fi device;
receiving messages from the Wi-Fi access points within
range ofthe Wi-Fi device, each message identifying the
Wi-Fi access point sending the message;
calculating the signal strength of the messages received
by the Wi-Fi access points;
accessing the reference database to obtain the calculated
locations for the identified Wi-Fi access points;
based on the number ofWi-Fi access points identified via
received messages, choosing a corresponding locationdetermination algorithm from a plurality of locationdetermination algorithms, said chosen algorithm being
suited for the number of identified Wi-Fi access points;
using the calculated locations for the identified Wi-Fi
access points and the signal strengths of said received
messages and the chosen location-determination algorithm to determine the location of the user-device.
2. The method of claim 1 wherein the calculated locations
for the identified Wi-Fi access points are filtered to determine if the corresponding Wi-Fi access points have moved
since the time the information about the Wi-Fi access points
was included in the reference database.
3. The method of claim 1 wherein the reference database
is located locally relative to the user-device.
4. The method of claim 1 wherein the reference database
is located remotely relative to the user-device.
5. The method of claim 1 wherein the location of the user
device is provided with latitude and longitude coordinates.
6. The method of claim 1 wherein the plurality of location-determination algorithms includes a simple signal
strength weighted average model.
7. The method of claim 1 wherein the plurality of location-determination algorithms includes a nearest neighbor
model.
8. The method of claim 1 wherein the plurality of location-determination algorithms includes a triangulation technique.
9. The method of claim 1 wherein the plurality of location-determination algorithms includes an adaptive smoothing technique based on the device velocity.
10. The method of claim 1 wherein the choice oflocationdetermination algorithm is further based on the user application making the location request.

* * * * *