Skyhook Wireless Inc. v. Google Inc.

Filing 1

COMPLAINT filed with Jury Demand against Google Inc. - Magistrate Consent Notice to Pltf. ( Filing fee $ 350, receipt number 17288.) - filed by Skyhook Wireless Inc. (Attachments: # 1 Exhibit A, # 2 Exhibit B, # 3 Exhibit C, # 4 Exhibit D, # 5 Exhibit E, # 6 Exhibit F, # 7 Exhibit G, # 8 Exhibit H, # 9 Exhibit I, # 10 Civil Cover Sheet, # 11 Acknowledgement of Consent Form)(eam)

111111

1111111111111111111111111111111111111111111111111111111111111
US008229455B2

United States Patent

(10)

Alizadeh-Shabdiz

c12)

(45)

(54)

(75)

Inventor:

(73)

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

( *)

Notice:

6,888,811
6,930,638
6,978,023
7,020,501
7,123,928
7,167,715
7,167,716
7,305,245
7,333,800
7,397,424
7,403,762
7,414,988
7,454,171
8,019,357

SYSTEM AND METHOD OF GATHERING
AND CACHING WLAN PACKET
INFORMATION TO IMPROVE POSITION
ESTIMATES OF A WLAN POSITIONING
DEVICE
Farshid Alizadeh-Shabdiz, Wayland,
MA(US)

Filed:

5/2005
8/2005
12/2005
3/2006
10/2006
112007
112007
12/2007
2/2008
7/2008
7/2008
8/2008
1112008
9/2011

Eaton eta!.
Lloyd et al.
Dacosta
Elliott et a!.
Moeglein et al.
Stanforth
Kim et al.
Alizadeh-Shabdiz eta!.
Gopinath
Houri
Morgan eta!.
Jones eta!.
Palin eta!. ................... 455/41.2
Alizadeh-Shabdiz eta!.

OTHER PUBLICATIONS
U.S. Appl. No. 11,625,450, Alizadeh-Shabdiz.

Appl. No.: 11/774,395

(22)

B2
B2
B2
B1
B2
B2
B2
B2
B1
B2
B2
B2
B2 *
B2

Jul. 24, 2012

(Continued)

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

(21)

US 8,229,455 B2

Patent No.:
Date of Patent:

(Continued)
Jul. 6, 2007

(65)

Prior Publication Data
US 2008/0008119 AI

Jan. 10,2008

Related U.S. Application Data
(60)

Provisional application No. 60/819,182, filed on Jul. 7,
2006.

(51)

Int. Cl.
H04W 24100
(2009.01)
H04W 4100
(2009.01)
U.S. Cl. ..................................... 455/456.1; 370/338
Field of Classification Search .................. 455/440,
455/456.1-456.6; 370/338
See application file for complete search history.

(52)
(58)

(56)

References Cited
U.S. PATENT DOCUMENTS
5,857,155
6,272,405
6,678,611
6,748,198
6,750,814

A
B1
B2
B1
B1

111999
8/2001
112004
6/2004
6/2004

Hill eta!.
Kubota eta!.
Khavakh et a!.
Salo
Nir eta!.

Primary Examiner- Michael Faragalla
(74) Attorney, Agent, or Firm- Wilmer Cutler Pickering
Hale and Dorr LLP

(57)

ABSTRACT

Methods and systems of gathering and caching WLAN
packet information to improve position estimates of a WLAN
positioning device. A device estimates the position of itself.
The device includes a WLAN radio module for receiving
WLAN signals transmitted by WLAN APs in range of said
device, extraction logic for extracting information from said
received WLAN signals to identifY the WLAN APs, and logic
to cooperate with a WLAN-based positioning system to estimate the position of the device based at least in part on the
extracted information identifYing the WLAN APs in the range
of said device. The extraction logic includes logic for caching
the extracted identities and logic for caching information
indicating the time of reception of the signals transmitted by
the corresponding WLAN AP. And, the logic to cooperate
considers the cached time information when providing
extracted and cached information to said WLAN -based positioning system.
12 Claims, 6 Drawing Sheets

List of detected APs categorized by
detected packet type
303
Broadcast
packets

301

302

Unicast
packets

Packets
withCRC
error

MAC,RSSI MAC,RSSI MAC,RSSI
MAC,RSSI MAC,RSSI MAC,RSSI
MAC,RSSI MAC,RSSI
MAC,RSSI

1
WLAN Positioning
System
304

US 8,229,455 B2
Page 2
U.S. PATENT DOCUMENTS
200110023446
2003/0119445
2003/0125045
2003/0225893
2004/0019679
2004/0039520
2004/0081133
2004/0087317
2004/0095894
2004/0137849
2004/0205234
2004/0259546
2004/0263388
2005/0020266
2005/0037775
2005/0059356
2005/0073979
2005/0096068
2005/0102504
2005/0130677
2005/0192024
2005/0276253
2006/0009235
2006/0078122
2006/0095348
2006/0095349
2006/0106850
2006/0154600
2006/0166699
2006/0197704
2006/0200843
2006/0217131
2006/0221918
2006/0227745

A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1

2006/0240840
2007/0004427
2007/0004428
2007/0046436
2007/0097511
2007/0126635
2007/0147317
2007/0150516
2007/0165845
2007/0183374
2007/0202888
2007/0232892
2007/0258408
2007/0258409
2007/0258420
2007/0258421
2007/0259624
2008/0008117
2008/0008118
2008/0008119
2008/0008120
2008/0008121
2008/0033646
2008/0132170
2008/0139217
2008/0176583
2008/0242305
2009/007 5672
2009/0149197

A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1

*

*

*

*

*

*

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

Balogh
Bromham et a!.
Riley eta!.
Roese eta!.
E eta!.
Khavakh et a!.
Smavatkul et al.
Caci
Eloranta eta!.
Kloper eta!. .............. 455/67.11
Barrack et a!.
Balachandran et al.
Krumm eta!.
Backes eta!.
Moeglein et a!.
Lee et al.
Barber eta!.
Bah! et al. .................. 455/456.1
Le eta!.
Meunier et a!.
Sheynblat
Ho eta!.
Sheynblat et a!.
Dacosta
Jones et al.
Morgan eta!.
Morgan eta!.
Ferris
Aghvami et al. .......... 455/552.1
Luzzatto et a!.
Morgan eta!.
Alizadeh-Shabdiz et a!.
Wang
Olvera-Hernandez
eta!. ............................. 370/331
Morgan eta!.
Morgan eta!.
Morgan eta!.
Tanaka
Das eta!.
Houri
Smith eta!. ................... 370/338
Morgan eta!.
Ye eta!.
Classon et a!.
Brachet et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Morgan eta!.
Alizadeh-Shabdiz et a!.
Alizadeh-Shabdiz et a!.
Brachet et a!.
Kahlert et a!. ................ 455/440
Jones et al.
Morgan eta!.

2009/0154371
2009/0175189
2009/0252138
2009/0303112
2009/0303113
2009/0303114
2009/0303115
2009/0303119
2009/0303120
2009/0303121
2009/0310585
2009/0312035
2009/0312036
201110012780
201110012784
201110021207
201110035420
201110045840
201110058495
201110074626
201110080317
201110080318
201110080841
201110164522
201110235532
201110235623
201110287783
201110298659
201110298660
201110298663
201110298664
201110306357
201110306358
201110306359
201110306360
201110306361

A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1
A1

6/2009
7/2009
10/2009
12/2009
12/2009
12/2009
12/2009
12/2009
12/2009
12/2009
12/2009
12/2009
12/2009
112011
112011
112011
212011
212011
3/2011
3/2011
4/2011
4/2011
4/2011
7/2011
9/2011
9/2011
1112011
12/2011
12/2011
12/2011
12/2011
12/2011
12/2011
12/2011
12/2011
12/2011

Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Morgan eta!.
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh -Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz
Alizadeh-Shabdiz

eta!.
eta!.
eta!.

eta!.
eta!.
eta!.
eta!.
eta!.
eta!.
eta!.
eta!.
eta!.
eta!.
eta!.

eta!.
eta!.
eta!.
eta!.
eta!.

OTHER PUBLICATIONS
Griswold et al., "ActiveCampus-Sustaining Educational Communities through Mobile Technology." UCSD CSE Technical Report
#CS200-0714, 2002.
Hazas, M., et a!., "Location-Aware Computing Comes of Age,"
IEEE, vol. 37, Feb. 2004.
Hellebrandt, M., eta!., "Estimating Position and Velocity of Mobile
in a Cellular Radio Network," IEEE Transactions on Vehicular Technology, vol. 46, No. 1, Feb. 1997.
International Search Report, International Application No. PCT/
US05/39208, mailed Jan. 29, 2008. (3 pages).
Kim, M., eta!., "Risks ofusingAP 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.
~mm, 'J., eta!., "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 a!., "Place Lab: Device Positioning Using Radio
Beacons in the Wild," Intel Corporation, 2004.
Muthukrishnan, K., eta!., "Towards Smart Surroundings: Enabling
Techniques and Technologies for Localization," Lecture Notes in
Computer Science, vol. 3479, May 2005 .

* cited by examiner

U.S. Patent

Jul. 24, 2012

US 8,229,455 B2

Sheet 1 of 6

d

802.1

J

access point

~02.!1

!02

access p.tlinl

!

102

l

User Device
1OJ
Positioning
software
103

R
1

+-----.;l
I

Reference
Database
104

i

f

!

I

~

Rfl2.1 i
I L _ J .
,

802.11
access point

I

102

Figure 1

ilCi;t:SS

point

102

U.S. Patent

Jul. 24, 2012

Sheet 2 of 6

Decode headers of all
received packets

201

,
Extract MAC addresses of
all the packets

202

,,
Organize MAC addresses
based on the type of packet
received

203

Send list of MAC addresses
toWPS

204

Figure 2

US 8,229,455 B2

U.S. Patent

Jul. 24, 2012

US 8,229,455 B2

Sheet 3 of 6

List of detected APs categorized by
detected packet type
303
Broadcast
packets

Unicast
packets

Packets
with CRC
error

MAC,RSSI MAC,RSSI MAC,RSSI
MAC,RSSI MAC,RSSI MAC,RSSI
MAC,RSSI MAC,RSSI
MAC,RSSI

301

302

WLAN Positioning
System
304

Figure 3

U.S. Patent

Jul. 24, 2012

Sheet 4 of 6

US 8,229,455 B2

Decode header of all
received packets
401

Extract MAC addresses of
packets with correct CRC
and flag as correct

Extract MAC addresses of
packets with CRC error and
flag as having an error

402

403

Organize MAC addresses
based on type of packet
received and status of CRC
flag.
404

Send list of MAC addresses
to WPS

405

Figure 4

U.S. Patent

Jul. 24, 2012

US 8,229,455 B2

Sheet 5 of 6

501

/
RF modules

502

Carrier sense
module

503
RF modules
Electronic
switch [507]

504

/
500

Figure 5

f--.

Baseband
module

505

__.

Packet
processing
module

506

U.S. Patent

Jul. 24, 2012

Sheet 6 of 6

US 8,229,455 B2

603

/
~

RF modules

602

Probe Request
Transmitter

-~

601

.
-,.

Receiver

604

Figure 6

600

US 8,229,455 B2
1

2

SYSTEM AND METHOD OF GATHERING
AND CACHING WLAN PACKET
INFORMATION TO IMPROVE POSITION
ESTIMATES OF A WLAN POSITIONING
DEVICE

U.S. Provisional Patent Application No. 60/819,218,
entitled Methods and Systems for Using WLAN Positioning
System in Assisted GPS Systems, filed Jul. 7, 2006;
U.S. Provisional Patent Application No. 60/830,624,
entitled Methods and Systems for Using WLAN Positioning
System in Assisted GPS Systems, filed on Jul.
13, 2006;
U.S. Provisional Patent Application No. 60/821,479,
entitled WLAN Positioning System User Location Pulling
Mode for Use in Client-Server Systems, filed on Aug. 4,
2006;
U.S. patent application Ser. No. 11/625,450, entitled System and Method for Estimating Positioning Error within a
WLAN Based Positioning System, filed on Jan. 22, 2007;
U.S. patent application Ser. No. 11/696,832, entitled Time
Difference of Arrival Based Estimation of Speed in a WLAN
Positioning System, filed on Apr. 5, 2007;
U.S. patent application Ser. No. 11/696,833, entitled Time
Difference ofArrival Based Estimation of Direction ofTravel
in a WLAN Positioning System, filed on Apr. 5, 2007;
U.S. patent application Ser. No. 11/774,387, entitled
Method and System for Employing a Dedicated Device for
Position Estimation by a WLAN Positioning System, filed on
Jul. 6, 2007;
U.S. patent application Ser. No. 11/774,392, entitled System and Method of Gathering WLAN Packet Samples to
Improve Position Estimates of WLAN Positioning Device,
filed on Jul. 6, 2007;
U.S. patent application Ser. No. 11/774,399, entitled Systern and Method of Improving Sampling of WLAN Packet
Information to Improve Estimates of Doppler Frequency of a
WLAN Positioning Device, filed on Jul. 6, 2007; and
U.S. patent application Ser. No. 11/774,400, entitled System and Method of Passive and Active Scanning ofWLANEnabled Access Points to Estimate Position of a WLAN Positioning Device, filed on Jul. 6, 2007.

5

CROSS-REFERENCE TO RELATED
APPLICATIONS
This application claims the benefit under 35 U.S.C. § 119
(e) to the following U.S. Provisional Patent Application, the
contents of which is incorporated by reference herein:
U.S. Provisional Patent Application No. 60/819,182,
entitled Use of a Client -Side Receive-Only WLAN Device In
a WLAN Positioning System, filed on Jul. 7, 2006.
This application is related to the following U.S. Applications:
U.S. patent application Ser. No. 11/261,848, entitled Location Beacon Database, filed on Oct. 28, 2005;
U.S. patent application Ser. No. 11/261, 898, entitled
Server for Updating Location Beacon Database, filed on Oct.
28, 2005;
U.S. patent application Ser. No. 11/261,988, entitled Location-Based Services that Choose Location Algorithms Based
on Number of Detected Access Points Within Range of User
Device, filed on Oct. 28, 2005;
U.S. patent application Ser. No. 11/261,987, entitled
Method and System for Building a Location Beacon Database, filed on Oct. 28, 2005;
U.S. patent application Ser. No. 11/365,540, entitled
Encoding and Compressing a WiFi Access Point Database,
filed on Mar. 1, 2006;
U.S. patent application Ser. No. 11/562,514, entitled Location Toolbar For Internet Search and Communication, filed on
Nov. 22, 2006;
U.S. patent application Ser. No. 11/359,154, entitled Continuous Data Optimization of Existing Access Points In Positioning Systems, filed on Feb. 22, 2006;
U.S. patent application Ser. No. 11/359,144, entitled Continuous Data Optimization ofNew Access Points In Positioning Systems, filed on Feb. 22, 2006;
U.S. patent application Ser. No. 11/359,271, entitled Continuous Data Optimization by Filtering and Positioning Systems, filed on Feb. 22, 2006;
U.S. patent application Ser. No. 111430,079, entitled Estimation Of Speed and Direction of Travel In A WLAN Positioning System, filed on May 8, 2006;
U.S. patent application Ser. No. 11/678,301, entitled Methods and Systems For Estimating a User Position In a WLAN
Position System Based On User AssignedAccess Point Locations, filed on Feb. 23, 2007;
U.S. patent application Ser. No. 11/430,224, entitled Calculation of Quality ofWLAN Access Point Characterization
for Use In a WLAN Positioning System, filed on May 8,
2006;
U.S. patent application Ser. No. 11/430,222, entitled Estimation of Position Using WLAN Access Point Radio Propagation Characteristics In a WLAN Positioning System, filed
on May 8, 2006;
U.S. patent application Ser. No. 11/429,862, entitled Estimation of Speed ofTravel Using the Dynamic Signal Strength
Variation of Multiple WLAN Access Points, filed on May 8,
2006;
U.S. patent application Ser. No. 111430,064, entitled Estimation of Speed and Direction of Travel In A WLAN Positioning System Using Multiple Position Estimations, filed on
May 8, 2006;

10

15

20

25

30

35

BACKGROUND OF THE INVENTION
40

45

50

55

60

65

1. Field of the Invention
The invention generally relates to WLAN-based positioning systems and, more specifically, to methods of using
devices specifically dedicated for the collection of WLAN
data for use by WLAN-based positioning system to estimate
a user's geographic position or optimize operation of the
WLAN-enabled device or to gather more samples ofWLAN
signals to improve position estimates.
2. Description 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 calculate their current geographic position and report that to a

US 8,229,455 B2
3

4

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
Govermnent leverages dozens of orbiting satellites as reference points. Cell tower triangulation is another method used
by wireless and cellular carriers to determine a user or
device's location. Assisted GPS is another 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 cell towers.
WLAN location system is a new positioning system, which
uses WLAN access points to produce location of mobile
users. Metro wide WLAN based positioning systems have
been explored by a couple of research labs. The most important research efforts in this area have been conducted by
PlaceLab (www.placelab.com, a project sponsored by
Microsoft and Intel), University of California San Diego
ActiveCampus project (ActiveCampus-Sustaining Educational Cormnunities through Mobile Technology, technical
report #CS2002-0714), and the MIT campus wide location
system. There is only one cormnercial metropolitan WLAN
based location system in the market at the time of this writing,
and it is referred to as WLAN positioning system (WPS)
herein.
FIG. 1 depicts a WLAN positioning system based on WiFi
signals. The positioning system includes positioning software 103 that resides on a computing device 101. Throughout
a particular target geographical area, there are fixed wireless
access points 102 that transmit information using control/
common channel signals. The client device monitors these
transmissions. Each access point contains a unique hardware
identifier known as a MAC address. The client positioning
software receives transmissions from the 802.11 access
points in range and calculates the geographic location of the
computing device using characteristics from the radio signals. Those characteristics include the unique identifier of the
802.11 access point, known as the MAC address, Time of
Arrival (TOA), 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 may or may not reside on the device
as well. The reference database contains the calculated geographic locations and power profile of all the access points the
gathering system has collected. The power profile may be
generated from 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.
Indoor or outdoor WLAN based positioning systems have
leveraged existing off-the-shelf WLAN cards without any
modification other than to employ the logic to estimate position.

BRIEF SUMMARY OF THE INVENTION

10

15

20

25

30

35

40

45

The invention provides methods and systems of gathering
and caching WLAN packet information to improve position
estimates of a WLAN positioning device.
Under one aspect of the invention, a device estimates the
position of itself in response to gathering wireless signal
information from WLAN access points (APs ). The device
includes a WLAN radio module for receiving WLAN signals
transmitted by WLAN APs in range of said device, extraction
logic for extracting information from said received WLAN
signals to identifY the WLAN APs, and logic to cooperate
with a WLAN-based positioning system to estimate the position of the device based at least in part on the extracted
information identifYing the WLAN APs in the range of said
device. The extraction logic includes logic for caching the
extracted identities of the WLAN APs in range of the device
and logic for caching information indicating the time of
reception of the signals transmitted by the corresponding
WLAN AP. And, the logic to cooperate considers the cached
time information when providing extracted and cached information to said WLAN-based positioning system.
Under another aspect of the invention, the logic for caching
includes logic to cache identity information extracted from
normal data cormnunication between the device and other
access points, and logic to cache identity information
extracted from WLAN packets received by the device during
a mode to estimate the position of the device.
Under another aspect of the invention, the times of reception information and the extracted identify information are
cormnunicated to the WLAN-based positioning system to
improve tracking of said device.
Under another aspect of the invention, the caching logic
holds the cached information for a specified amount of time.
Under another aspect of the invention, the caching logic
holds the cached information for a specified amount of
entries.
Under another aspect of the invention, the cached information is organized based on the type of WLAN packets from
which the extracted information was derived.
Under another aspect of the invention, the device is responsive to a scan request to estimate position of said device and
wherein in response to the scan request the cached information is considered in estimating the position of the device.
BRIEF DESCRIPTION OF THE SEVERAL
VIEWS OF THE DRAWINGS

50

55

60

65

For a more complete understanding of various embodiments of the present invention, reference is now made to the
following descriptions taken in connection with the accompanying drawings in which:
FIG. 1 illustrates a high-level architecture of a WLAN
positing system;
FIG. 2 illustrates a process by which information is
extracted from wireless data packets for transmission to a
WLAN positioning system;
FIG. 3 illustrates information gathered by a dedicated
device for use by a WLAN positioning system;
FIG. 4 illustrates a process by which packet errors are
identified in information that is extracted from wireless data
packets;
FIG. 5 illustrates the configuration of a dedicated device
for gathering WLAN signal information for a WLAN positioning system for estimation of the geographic position of
the device; and

US 8,229,455 B2
5

6

FIG. 6 illustrates the configuration of a device having a
dedicated probe request transmitter for gathering WLAN signal information for a WLAN positioning system for estimation of the geographic position of the device.

The embodiments of the invention described below may be
used with the Wi-Fi based location services and methods
described in the related applications listed above, which are
herein incorporated by reference and with the methods disclosed herein. Those applications taught specific ways to
gather high quality location data for Wi-Fi access points so
that such data may be used to estimate the geographic position, speed, and bearing of a Wi-Fi-enabled device utilizing
such services and techniques of increasing the accuracy of the
various estimations.
Generally, as described in greater detail in the incorporated
applications, in the WLAN positioning system, the user's
WLAN-enabled mobile device scans for WLAN access
points in range of the mobile device. The mobile device
records information about the access points in range (e.g., the
access points' MAC addresses and received signal strengths)
and queries a database to receive the access points' geographic positions. This database can reside on the mobile
device or it can reside on a central server and accessed
remotely. Using the gathered information and the access point
positions, the WLAN positioning system estimates the user's
geographic position. The techniques of preferred embodiments enable additional signal information to be gathered by
the dedicated device. For example, packets that would be
ignored under conventional data communication technique
are now considered. Likewise, erroneous packets may be
used. This additional information enables the WPS to provide
improved and/or more accurate position, velocity, and bearing estimate, as described in detail below.
The WLAN positioning system can be implemented on a
client-server based architecture, in which the central database
resides on a server and there is a need for a connection to the
server to determine a client's position. This connection can be
implemented, for example, using a WLAN, or other radio
signal methods, such as one or more of the various mobile
telephone radio standards. In addition, the positioning system
can be implemented on a client device with no server interaction, in which case, the various databases, tables and algorithms are located on the dedicated device.
FIG. 2 illustrates a process by which information is
extracted from wireless packets for transmission to a WLAN
positioning system. This process can be implemented using a
WPS dedicated device without a transmitter. Upon receiving
the radio signal from the AP, the physical layer decodes the
header of all of the received packets (step 201). The logic then
extracts MAC addresses from the packets (step 202) and
organizes the MAC addresses based on the type of packet that
was received (step 203). For example, the packets may be a
broadcast, multicast, or unicast packet. This table of gathered
MAC addresses is sent to the WPS as a list of detected APs
(step 204), for use by the WPS to estimate the geographic
position of the dedicated device using, for example, the techniques disclosed in the above-incorporated applications.
In addition to extracting information from a more diverse
selection of packets, the dedicated device can detect weak
wireless signal by using diversity and combining multiple
packets. Received packets at a weak signal is subject to higher
probability of error and if they do not pass CRC check and at
least an error is detected in them, using this method, the
erroneous packets can be corrected by combing same information of different packets. The word "Diversity" here refers
to a concept of combining different packets with some percentage of the same information and reducing probability of
error by combining them. For example the received packets
may have only different sequence number and other fields
remain the same. Note that conventional definition of diversity is receiving multiple copies of the same transmitted

DETAILED DESCRIPTION OF THE INVENTION
Preferred embodiments of the invention provide a dedicated device that gathers wireless signal information for use
by clients of a WLAN positioning system (herein "WPS
dedicated device" or "dedicated device"). The dedicated
device detects WLAN access points (APs) and provides AP
signal information to a WPS for use in estimating the position,
the velocity, and direction of travel of the device. The dedicated device for use with a WPS is designed to collect information from as many detectable WLAN access point signals
as possible, while also minimizing power consumption and
device cost.
In one illustrative implementation, the receiver of a WPS
dedicated device extracts MAC address from all the packets,
including broadcast, multicast, unicast, and data packets,
which are detected on the air by the device's receiver to create
a list of surrounding APs. That is, even packets with target
addresses other than the dedicated device are detected and
used to estimate position of the dedicated device. In order to
detect WLAN APs surrounding a WPS user, source and destination addresses of packets, both are used. The IEEE 802.11
standard introduced two flags, To DS and From DS, which
define the type of MAC addresses in the header. These two
flags are used to identifY MAC address ofAP in the header. If
there is no indicator of type of MAC addresses in the header
and which one belongs to an AP, all the MAC addresses are
extracted and sent to WPS. Automatically, WPS only considers MAC addresses ofAPs, since only MAC addresses ofAPs
exist in the database of APs. Note that each WLAN device
including APs is assigned a unique MAC address. The
received signal strength of all the packets can also be measured and reported to the WPS along with the type of the
source packet, as explained below, from which the MAC
address is extracted. Preferred embodiments send the type of
the packet along with the RSSI (Received Signal Strength
Indicator) value to the WPS, because the transmit power of
some types of packets might not be known by the WPS. While
the exact transmit power of some data packets might not be
known by the device's receiver, some signals are transmitted
at a known power level, e.g., beacon signals are transmitted at
the maximum power at all times.
A typical WLAN -enabled device consists of a transmitter,
a receiver, and logic to support full duplex communication
between the WLAN and the WLAN-enabled device. In a
Wireless LAN the media is shared between all the users and
users contents to access the media and transmit information.
Therefore, each user has to decode all the packets to detect
and pick up packets destined to it. The logic of such a WLAN
communication device is configured to ignore certain types of
signals from WLAN access points (e.g. unicast signals
intended for other WLAN devices). In contrast, the dedicated
device of preferred embodiments does not ignore any packet
and extracts from each packet the MAC address, RSSI, and
other information useful to the WPS. The dedicated device
does not need many of the transmitter and receiver functions
that are present in a typical WLAN communication device.
The dedicated device, with logic dedicated solely for use with
a WPS, can be constructed more economically due to the
reduced hardware and software requirements. Further, the
power consumption of such a device can be lower than that of
a full duplex device.

10

15

20

25

30

35

40

45

50

55

60

65

US 8,229,455 B2
7

8

packet/information and combining them to improve the
incorrect. Increasing the number of detected APs improves
reception. There are different known/conventional methods
the accuracy and coverage of the position estimation.
FIG. 3 illustrates information gathered by a WPS dedicated
of combining packets, like maximum ratio combining, selective combining, or equal gain combining. Any combining
device for use by a WLAN positioning system. An access
point 301 transmits signals containing its MAC address.
method can be used here to combine the common part of
Mobile device 302 contains a WPS dedicated device. The
packets. Since the proposed method is based on combining
different packets with some percentage of common informadedicated device gathers information from APs in range,
including access point 301, and generates a list of detected
tion, there is a need to identify packets, which can be combined. This is done by finding similarity of the packets and if
APs 303. This list is sent to a WPS 304. The list of detected
the similarity is above a threshold, the combining is exam- 10 APs 303 contains MAC addresses, and optionally, Received
ined. Thus, while an individual packet may have been unusSignal Strength Indication values. The entries in the list are
able (e.g., because ofCRC error), the diversity and combining
categorized based on the type of packet that was the source of
the MAC address (e.g., broadcast, multicast, or unicast) and
techniques allow these otherwise unusable packet to be used
to improve position estimation (e.g., by providing more
whether or not the dedicated device detected any CRC errors.
15 This list is sent to a WLAN positioning system 304 to estiWLAN signal samples to the WPS).
mate the device's position.
This method increases receiver sensitivity by combining
the header information from multiple packets. By combining
FIG. 4 illustrates a process by which packet errors are
the header information from multiple packets, the dedicated
identified in information that is extracted from WLAN packdevice can take advantage of repetitive information in the
ets. In the initial step, all detectable packets are captured, and
multiple packets and detect erroneous bits, correct them, and 20 each packet's header is decoded (step 401). As the MAC
address of the AP originating the packet is extracted from the
effectively increase the sensitivity of the receiver of the dedicated device. Packets that are received at low power values are
header, packets passing a CRC check are flagged with a
subject to a higher probability of error. In a typical WLANcorrect flag (step 402), while packets failing a CRC check are
enabled device, as received power decreases, more and more
flagged with an error flag (step 403). Next, all of the MAC
packets are rejected at the physical layer because of errors in 25 addresses are organized based on the type of packet that was
packets. In contrast, when two or more packets originate from
the source of the MAC address (e.g., broadcast, multicast, or
the same WLAN AP or are destined to the same WLANunicast) and on whether or not the packet passed the CRC
enabled device (which need not be the dedicated device), the
check (step 404). Finally, the list is sent to a WLAN positioning system to estimate the device's position (step 405).
dedicated device combines the information in the packets to
The WPS dedicated device only needs to read headers of
detect errors and also correct errors present in the packets. 30
the packets in order to extract MAC address of APs. ThereThis technique enables detecting weaker signal fromAPs.
In other words, it increases sensitivity by taking advantage of
fore, the receiver of the dedicated device needs only be
additional signal information that would otherwise be disequipped with corresponding physical layer to decode headcarded by a typical WLAN-enabled device. Increasing the
ers. For example, because headers are transmitted at the base
number of detected APs improves the accuracy and coverage 35 rate, a WPS dedicated device need to decode the base rate.
The base rate is a transmission rate that is common between
of the position estimation. In order to detect APs, the dedidifferent versions of the WLAN standards. For example, the
cated device need only process the packet headers to extract
IEEE 802.11 standard provides multiple options at the physithe MAC address. If a series of packets that terminate at the
callayerto extend the data rate to 11 Mbps for version 'b' and
same WLAN device originate from the same WLAN device,
or are part of the same session, there is an extensive number of 40 54 Mbps for version 'a' and 'g' of the standard. However, the
header of these packets are always transmitted at the base rate
common fields in the headers. By considering multiple packof 1 Mbps. A more accurate measurement ofRSSI increases
ets with common fields, the dedicated device can help to
the accuracy of the estimation of position, velocity, and direcidentify the exact error(s) and potentially correct the error(s)
tion of travel (using, for example, the techniques disclosed in
in a mam1er sufficient to at least use the packet information for
45 the incorporated applications). However, measuring the RSSI
position estimation.
of the packets is not essential for operation of the WPS. For
There are many ways to perform data correction. In genexample, the WPS can assume a nominal power value for the
eral, all of the methods use common information transmitted
in the series of packets to identify the errors and correct them.
packets without the power measurement and can estimate the
For example, by receiving two copies of the same packet, the
position of the mobile devices based on the nominal power
device can identifY discrepancies between the two and pos- 50 value.
Under an alternate embodiment, a receive-only WPS dedisibly correct those errors. Even if the errors cam1ot be corcated device is provided that gathers WLAN access point
rected, identifYing an erroneous part of a header can be used
to ensure that the MAC addresses are correct. Note that the
signal information in a passive mam1er (i.e., the device
headers of 802.11 packets are protected using CRC (Cyclic
receives signals without the need to first transmit a request).
Redundancy Check) techniques. Therefore, CRC checking 55 In general, to enable a WPS to estimate the position of a client
device, the client device must detect WLAN access points in
used to detect errors.
the vicinity and, optionally, measure the RSSI values associIn addition to the implementation described above, the
ated with each detectedAP. The receive-only WPS dedicated
WPS dedicated device includes the MAC address extracted
device detects WLAN access points as discussed in the incorfrom headers containing errors, which cam1ot be corrected
after applying any method, in the list of detected APs, along 60 porated applications and may also detect packets by sniffing
with a flag indicating that the addresses were extracted from
packets originated by APs destined to other WLAN-enabled
devices or by receiving broadcast packets transmitted by the
erroneous packets. Therefore, the list of detectedAPs sent to
the WPS includes a list of AP MAC addresses extracted from
WLAN access points. The sniffing and broadcast techniques
are particularly useful for receive-only devices as they lack a
packets without error and a list of AP MAC addresses
extracted from packets with error. Thus, the WPS can use the 65 transmitter and cannot instigate an AP reply or response.
After sniffing a packet or receiving a broadcast packet, the
information associated with packets containing errors in such
receive-only WPS dedicated device need only read the MAC
a way as to allow for the fact that the information may be

US 8,229,455 B2
9

10

address of the AP embedded in the header of the packet and,
optionally, measure the associated signal power of the packet.
Power consumption of the WPS dedicated device can be
minimized by minimizing duration of time that the receiver is
active. The WPS dedicated device of preferred embodiments
is in low-power consumption mode (e.g. standby mode) and
is activated when a packet is detected on the wireless media.
Moreover, it is only activated for the duration of header size.
The WPS dedicated device only needs to receive the header
and decode it and may ignore rest of the packet. The WPS
dedicated device can be equipped with a simple carrier sense
module, which detects any activity on the WLAN channels.
The carrier sense module has low power consumption compared to the WLAN receiver module. The WLAN receiver
module can be optimized for WPS to only extract the MAC
addresses of detected APs and, optionally, to estimate the
associated RSSI value of the received signal. Upon receiving
a request for a position estimate, the device causes the carrier
sense module to monitor WLAN channels for signal activity.
When the carrier sense module detects any activity, it changes
the receiver module to active mode, which reads the packet
header and extracts the MAC addresses ofWLAN APs.
In addition, the carrier sense module can be designed with
passive electronic components to minimize power consumption. Furthermore, the carrier sense module can be designed
to operate at the RF band to eliminate the need for down
conversions of the radio frequency to the processor frequency. Thus, any part of the receiver circuit that is not needed
for carrier sensing can remain in a low power consumption
mode (for example, a standby mode) until needed. At which
time, the carrier sense module activates the receiver circuit
upon detecting a packet on any channel.
FIG. 5 illustrates a configuration of a receive-only WPS
dedicated device 500 for gathering WLAN signal information
for a WLAN positioning system for estimation of the geographic position of the device. The device 500 has an antenna
501 and RF modules 502, or parts of an RF module that are
needed only to detect a carrier, and a carrier sense module 503
to detect any activity on the WLAN channels. The device 500
also includes any other RF modules 504 that are required for
WLAN signal processing, a baseband module 505, and a
packet processing module 506 that processes the packet
header and extracts the MAC address and associated RSSI
values of the signals.
The RF modules 504 required for WLAN signal processing, the baseband module 505, and the packet processing
module 506 are needed only upon detection of a WLAN
signal. Thus, these modules are maintained in a low power
consumption mode (e.g., a sleep mode). When the carrier
sense module 503 detects any activity on a WLAN charmel,
the carrier sense module 503 changes all of the other modules
to an active mode via power mode control connections 508.
Also upon detection of a packet on the channel, the carrier
sense module 503 also routes the signal from the RF modules
502 to the rest of the receiver modules via electronic switch
507 to decode the header of the packet.
A "Beacon Detector" is one illustrative implementation of
a receive-only WPS dedicated device. A beacon is a signal
that is broadcast by WLAN access points periodically and
includes the MAC address of the access point. Thus, a Beacon
Detector is a simple receive-only device that extracts the
MAC address and, optionally, calculates the associated RSSI
values, from the beacon signals.
In another embodiment of the invention, a WPS dedicated
device is provided that includes a transmitter and a receiver
that are optimized for use in a WPS. In order to detect the
WLAN access points in the vicinity and the associated RSSI

values, the dedicated device actively probes WLAN APs by
broadcasting a probe request message and receiving probe
response from the WLAN APs in range. While "probe
response" and "probe request" refer to specific messages in
the IEEE 802.11 standard, embodiments of the invention also
encompass the general concept of active scanning for any
WLAN access points. Active scanning is a quick and power
efficient way of detecting WLAN APs because the duration of
scanning is short and the radio modules in the device are
powered on for only a short period of time, thereby consuming less power.
FIG. 6 illustrates one possible implementation of a WPS
dedicated device 600 in which the transmitter of the dedicated
device is designed to transmit only the probe request message. This greatly simplifies the configuration of the transmitter. For example, the base band modules of the transmitter
can be eliminated. Likewise, because the transmitter is
designed to only transmit a pre-defined probe request packet,
much of the software that would otherwise be required to
control the transmitter can be eliminated. In this illustrative
implementation, the probe request packet is pre-generated
and stored in a probe request transmitter module 601. Upon
receiving a command to perform active scarming, the probe
request packet can be fed to RF modules 602 directly. The RF
modules 602 transmit the probe request to surrounding
WLAN APs via an antenna 603.
The WLAN APs in range respond with probe responses,
which are passed by the antenna 603 and RF modules 602 to
a dedicated receiver module 604. The receiver module 604
extracts the MAC addresses from the probe responses and
calculates the associated RSSI values. The receiver module
604 does not need to be able to decode any other message
except the pro be responses. The IEEE 802.11 standard pro be
responses and probe requests are transmitted at the base rate.
Thus, the probe request transmitter module 601, RF modules
602, and receiver 604 need only support physical layer of
probe request and probe response. Optionally, the receiver
design can be extended to read all of the header files of all the
packets on the air, as described above, and compose a list of
the MAC addressed and RSSI values of the detectedAPs. In
such an implementation, the dedicated device has the dual
benefits ofbeing able to gather information from surrounding
WLAN AP on demand as well as being able to extract information from any detectable WLAN radio signal on the air.
The device may then consult a local database to perform
position estimation or use other forms of up-links to a remote
database (e.g., cellular link).
The typical approach for known WPS-enabled devices is to
leverage existing WLAN transceivers embedded in (or added
to) clients' devices (e.g., laptop, PDA, or cell phones). However, as described above, a WPS-enabled device of preferred
embodiments does not require all of the functionality of a
typical WLAN card in order to gather WLAN AP signal
information. When a user's device is not equipped with a
typical WLAN card, a WPS dedicated device can be added to
the user device (laptop, cell phone, or PDA) to make it WPSenabled. Thus, one potential application of embodiments of
the invention is to WPS-enable devices that are not equipped
with a standard off-the-shelfWLAN transceiver. This can be
achieved by adding a WPS dedicated device to user devices or
by integrating a WPS dedicated device into general purpose
integrated circuits. For example, GPS devices, laptops,
PDAs, and mobile telephones can be WPS-enabled by including a WPS dedicated device into the microprocessors and/or
chipsets of these devices.
Embodiments of the invention address some of the main
issues of integration with any mobile device general-purpose

10

15

20

25

30

35

40

45

50

55

60

65

US 8,229,455 B2
11

12

chipsets (e.g., GPS or microprocessors). Two general issues
that apply in nearly all integration cases are price and power
consumption. In addition, embodiments of the invention also
address specific issues that arise in the integration ofWLAN
transceivers into specific devices. For example, WLAN transceivers can cause interference with GPS devices. By eliminating the transmitter or limiting the use of the transmitter,
both as described above, potential interference is reduced or
eliminated. Likewise, by employing the techniques disclosed
herein, hardware cost and power consumption can be
reduced. Furthermore, when integrating a WPS dedicated
device into a GPS receiver, the GPS and WPS dedicated
device can share receiver hardware. For example, the receivers can share the antenna and/or local oscillators.
A WPS dedicated device can be purpose-built, or it can be
built by using an off-the-shelfWLAN card. In the later case,
the unnecessary modules and devices are not populated. In an
alternate configuration, the hardware of a standard off-theshelf WLAN card is fully populated, but unnecessary modules are disabled. In yet a further configuration, a typical
off-the-shelf WLAN-enabled device is customized for use
with a WPS. In such a case, the application programming
interface of the off-the-shelf interface is customized to perform the techniques described above. For example, as
described below, the WLAN -enabled device can be instructed
to detect as many WLAN APs as possible, perform extra
signal measurements, and/or expose some of the signal measurement to the WPS to increase the accuracy of position,
velocity, and direction of travel estimates.
Under another embodiment of the invention, the scanning
process of a WLAN-enabled device can be optimized by
combining passive and active scanning.
Passive and active scanning is part of the IEEE 802.11
standard. Hybrid scanning is proposed by some WLAN
device manufacturers, which is described as an active scan
followed by a passive scan of all the channels or an active scan
followed by a passive scan of the channel operating on. Upon
receiving a request to perform scanning, the WLAN -enabled
device performs active scanning on all the channels, followed
by passive scanning. Passive scanning can be performed on
the most used channels. For example, for IEEE 802.11 use in
the United States, passive scanning can be performed on
channels one, six, and eleven, as these are the most popular
channels. Furthermore, for the IEEE 802.11 standard implementation in the 2.4 GHz spectrum, twenty six MHz channels
are overlapped and separated only by 5 MHz. Therefore,
more than one channel can be scanned at a time for passive
and active scanning. The RF hardware can be designed, using
known methods, to enable the device to scan more than one
channel at a time. For example, the RF filters can be made to
have a wider bandwidth to enable the signal of more than one
channel to pass. If scanning process is divided to steps, which
are active scanning, passive scanning of the most used WLAN
channels and passive scanning of all the channels, scanning
can be further optimized based on the result of each step of
scanning. In other words, scanning can be stopped after each
step, if number ofretumedAPs is sufficient to estimate location of the end user. There is a balance between the minimum
number of required APs to estimate location of an end user
and power consumption. Increasing the minimum number of
required APs to estimate location of an end user, increases
probability of scanning more steps and consume more power,
but it increases overall accuracy of the end user.
Under an extension of the above embodiment of the invention, the process of scanning of WLAN APs surrounding a
WLAN -enabled device is optimized based on the status of the
WLAN-enabled device. The goal is minimizing power con-

sumption due to scanning for localization of the WLANenabled device by using information of the status of the
WLAN-enabled device. For example, if WLAN-enabled
device is in low-power consumption mode and not associated
with any AP, active scanning can be used which is short and
the device can go back to low power consumption mode
quickly. IfWLAN-enabled device is in low-power consumption mode but it is associated with an AP and goes to active
mode periodically as part of normal operation of the device,
the scanning for localization can be performed at the same
time that the WLAN-enabled device is activated for other
reasons. Tying scanning for localization and other activities
can also be conditioned to a maximum time difference
between the events. In other words, if the time of request to
scan for localization and other activities are more than a time
threshold, they can schedule independently, otherwise they
can be tied together and happen at the same time. If a WLANenabled device is active and it is associated with anAP, active
scanning followed by passive scanning can be performed,
since the WLAN device is active anyway. The word "Association" is introduced in the IEEE 802.11 standard and it
means a logic connection is established between the WLANenabled device and a WLAN AP.
Under another embodiment of the invention, WLAN
device logs any detectedAP and time tags it for the last given
period of time or up to the maximum number of recent
detected WLAN access points, locally.
In the normal operation of a typical WLAN-enabled
device, the device decodes packets to determine if the packets
are intended for the device or decodes beacon broadcast signal; MAC address of surrounding APs can be extracted from
decoded packets or beacon signals, but they are ignored or not
saved for later use. By modifYing the WLAN enabled device
the list of detected APs along with the time of detection is
saved locally.
Then, at a future time, the cached information can be sent
to a WPS, along with a time tag indicating the time of detection, in response to a request for a position estimate. Storing
history of detected APs is used to increase accuracy of position, velocity, and direction of travel estimation and it also
increases coverage in the case that the most recent scan does
not return any AP in the database.
The cached information and associated time tags enable
the WPS to take advantage of the history of the movement of
the user, to track the user, and to increase the accuracy of
position, velocity, and direction of travel estimates. In addition, if the WLAN-enabled device cannot detect any APs
when an AP scanning request is received, the cached signal
information can be used to predict a later position of WPSenabled device.
In a navigation system, two classes of position estimation
are introduced, namely position of an end user can be estimated with or without history of movement. Without history
is a single shot estimation and it is based on instantaneous
received signal. It is a one time estimation of position of end
user. With history of movement, past history of location of
user and pattern of user movement is known to the system and
current location of the user is not based solely on instantaneous view of the signal, but instead also considers all the
previous history of movement. This is also called position
estimation with tracking. Accuracy of estimation in case of
using history of movement is higher than one shot estimation.
History of movement can also be used to predict location of
user at future time. Therefore, the predicted location can be
reported if there is no signal available to locate user at the
current time and improve coverage of positioning system.

10

15

20

25

30

35

40

45

50

55

60

65

US 8,229,455 B2
13

14

Under another embodiment of the invention, multiple
extraction logic for extracting information from said
RSSI samples are provide for each packet. Each packet is
received WLAN signals to identify the WLAN APs; and
divided into multiple segments and RSSI is measured for each
logic to cooperate with a WLAN -based positioning system
to estimate the position of the device based at least in
segment, separately. These RSSI values are used to estimate
part on the extracted information identifYing the WLAN
Doppler frequency reference to each AP using known methods. For example, the bandwidth of the power spectral density
APs in the range of said device;
wherein said extraction logic includes logic for caching the
of the distribution of power variation due to multi-path is
extracted identities of the WLAN APs in range of the
equal to the Doppler frequency for Rayleigh and Rician disdevice, logic for caching information indicating the time
tribution. As in known, in order to estimate the bandwidth of
power spectral density of a Rayleigh or a Rician distribution, 10
of reception of the signals to identify the WLAN APs
ideally, a number of power samples should satisfy the Nyquist
transmitted by the corresponding WLAN AP, and logic
sampling theorem. Approaching the ideal Nyquist sampling
for generating movement information of the device from
the cached time information; and
rate increases the accuracy of Doppler estimation. Therefore,
the power sampling rate can be a limiting factor on the maxiwherein said logic to cooperate considers the cached time
mum Doppler frequency that can be measured in this way. 15
information and movement information when providing
extracted and cached information to said WLAN-based
The WPS dedicated device and the techniques described
above enable an increase in the sampling rate of the power
positioning system.
2. The device of claim 1 wherein said logic for caching
distribution by providing power readings for each packet it
includes logic to cache identity information extracted from
detects and/or by providing multiple power readings for a
given packet (e.g., one power reading associated with the first 20 normal data communication between the device and other
access points, and logic to cache identity information
half of the packet and another power reading associated with
extracted from WLAN packets received by the device during
the second half of the packet). The RSSI values of eachAP are
considered separate from other AP RSSI values.
a mode to estimate the position of the device.
3. The device of claim 1, wherein the times of reception
There are extensive work and research in estimating Doppler frequency based on power variation overtime. No known 25 information and the extracted identity information are comWLAN based positioning system uses these methods to estimunicated to the WLAN-based positioning system to
mate Doppler frequency, because power samples provided by
improve tracking of said device.
a WLAN enabled device is not frequent enough to estimate
4. The device of claim 1 wherein the caching logic holds
higher frequencies. Therefore, this method with off-the-shelf
the cached information for a specified amount of time.
5. The device of claim 1 wherein the caching logic holds
WLAN card can be used to estimate very small Doppler 30
frequencies or very small speeds, but in order to cover entire
the cached information for a specified amount of entries.
6. The device of claim 1 wherein the cached information is
range of practical user velocities, there is a need for more
power samples per second.
organized based on the type of WLAN packets from which
the extracted information was derived.
As explained above, the various embodiments and implementations of the invention can collect values of carrier fre- 35
7. The device of claim 1 wherein the device is responsive to
a scan request to estimate position of said device and wherein
quency along with the information contained in the received
packets and pass them to the WPS engine to estimate position,
in response to the scan request the cached information is
velocity, and bearing.
considered in estimating the position of the device.
It will be appreciated that the scope of the present invention
8. The device of claim 1 wherein said WLAN radio module
is not limited to the above-described embodiments, but rather 40 sniffs WLAN packets destined for WLAN devices other than
is defined by the appended claims, and these claims will
said device.
9. The device of claim 1 wherein said WLAN radio module
encompass modifications of and improvements to what has
been described. For example, embodiments have been
sniffs WLAN packets destined for WLAN APs.
10. The device of claim 1 wherein said WLAN radio moddescribed as having a client-server architecture. However,
embodiments of the invention can be implemented in the 45 ule sniffs WLAN packets originated by WLAN APs.
user's mobile device, in which the mobile device contains the
11. The device of claim 1 wherein said WLAN radio modaccess point location data and performs all techniques needed
ule receives broadcast packets from said WLAN APs.
to determine the user's location.
12. The device of claim 1 wherein said logic to cooperate
What is claimed is:
with a WLAN -based positioning system predicts future posi1. A device for estimating the position of itself in response so tion of the device based at least in part on the extracted
to gathering wireless signal information from WLAN access
information identifYing the WLAN APs in the range of said
device.
points (APs ), said device comprising:
a WLAN radio module for receiving WLAN signals transmitted by WLAN APs in range of said device;
* * * * *