(12)
`
`United States Patent
`Smith et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,312,752 B2
`Dec. 25, 2007
`
`USOO7312752B2
`
`(54) WIRELESS POSITION LOCATION AND
`TRACKING SYSTEM
`
`(75) Inventors: Derek M. Smith, San Diego, CA (US);
`James D. Adams, San Diego, CA (US);
`Nicolas C. Nierenberg, La Jolla, CA
`(US); Joseph C. Baker, Encinitas, CA
`US
`(US)
`(73) Assignee: Awarepoint Corporation, San Diego,
`CA (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 398 days.
`
`(21) Appl. No.: 10/968,814
`(22) Filed:
`Oct. 18, 2004
`
`(65)
`
`Prior Publication Data
`US 2007/O247366 A1
`Oct. 25, 2007
`Related U.S. Application Data
`(60) Provisional application No. 60/513,784, filed on Oct.
`i.Essign, prisis, N.
`3.
`60,572.690 filed O via 19, 2004 pp
`sy - ws
`y 19,
`(51) Int. Cl.
`(2006.01)
`GOIS3/02
`(2006.01)
`H04O 7/20
`52) U.S. Cl. .................................... 342/464; 455/456.5
`(58) Field of Classification Search ................ 342/463,
`342/.464, 465, 457; 455/4.56.1, 455, 456.5
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`6/1992 Heller ........................ 342/.480
`5,119, 104 A
`5,564,079 A * 10/1996 Olsson .................... 455,456.3
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`WOOOf 50918
`
`8, 2000
`
`(Continued)
`OTHER PUBLICATIONS
`
`Written Opinion Of The International Searching Authority for
`International Application No. PCT/US20004/034608, Sep. 19,
`2005.
`
`Continued
`(Continued)
`Primary Examiner—Gregory C. Issing
`(74) Attorney, Agent, or Firm—Clause Eight LLP; Michael
`Catania; Elaine Lo
`
`(57)
`
`ABSTRACT
`
`Techniques for accurate position location and tracking Suit
`able for a wide range of facilities in variable environments
`are disclosed. In one aspect, a system for position location
`comprises a plurality of sensors (e.g. a network monitor, an
`environment sensor) for generating a measurements of a
`plurality of sources, a plurality of objects or tags, each object
`generating measurements of the plurality of sources, and a
`processor for receiving the measurements and generating a
`position location for one or more objects in accordance with
`the received measurements. In another aspect, a position
`p
`p
`engine comprises a mapped space of a physical environ
`ment, and a processor for updating the mapped space in
`response to received measurements. The position engine
`may receive second measurements from an object within the
`physical environment, and generate a position location esti
`mate for the object from the received second measurements
`and the mapped space. Various other aspects are also pre
`sented.
`
`(Continued)
`
`2 Claims, 22 Drawing Sheets
`
`190A
`
`
`
`-ss
`BEACON
`EMTR
`i302
`NETWORK u-217
`MONITOR
`2A
`
`BEACON
`Mitt
`ER
`
`NCSE
`SOURCE
`352
`
`CBJECT
`172
`
`METAFORK
`-- MONITOR
`2203
`
`
`
`JAMMER
`1462
`
`NETWORK
`MONITOR
`i2OC
`
`BEACON
`EMITTER
`
`AR
`1808
`180B
`
`180A
`
`?
`
`-
`
`POSITIONING
`ENGINE
`112
`
`PosiTION (UERY
`
`-- POSITION RESPONSE
`
`co
`
`Page 1 of 43
`
`SAMSUNG EX-1047
`
`

`

`US 7,312,752 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`6.259,406 B1* 7/2001 Sugiura et al. ............. 342/457
`6,342,854 B1* 1/2002 Duffett-Smith et al. ..... 342/457
`6,529,164 B1
`3/2003 Carter ........................ 342/463
`6,674,403 B2
`1/2004 Gray
`6,799,047 B1 * 9/2004 Bahl et al. ............... 455,456.1
`7,053,830 B2 * 5/2006 Krumm et al. ............. 342/451
`2005.00751.18 A1* 4/2005 Lewis et al. ............. 455,456.5
`
`
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`WO
`
`WOO2/O548.13
`WO O3,O21851
`
`11 2002
`3, 2003
`
`OTHER PUBLICATIONS
`International Search Report for International Application No. PCT/
`US2004/034608, Sep. 19, 2005.
`International Search Report for PCT/US2004/034608, mailed Sep.
`19, 2005.
`RADAR: An In-Building RF-Based User Location and Tracking
`System. P. Bahl et al. IEEE Infocom 2000, pp. 775-784.
`Biatti, Roberto,et al. “Location-Aware Computing: a Neutral Net
`work Model for Determining Location in Wireless LANs.” Feb.
`2002. pp. 1-15.
`Liu Tong, et al. “Mobility Modeling, Location Tracking, and Tra
`jectory Prediction in Wireless ATM Networks.” IEEE Journal on
`Selected Areas in Comm. vol. 16, No. 6, Aug. 1998.
`Bahl, Paramvir, et al. "A Software System for Locating Mobile
`Users: Design, Evaluation and Lessons.” MSR-TR-2000-Feb. 12,
`2000. pp. 1-12.
`Bahl, Paramvir et al."RADAR: An In-Building RF-Based User
`Location & Tracking System”, in Proceedings of IEEE Infocom
`2000, Tel-Aviv, Isreal vol. 2, Mar. 2000, pp. 775-784.
`Krumm.John et al. “Minimizing Calibration Effort for an Indoor
`802.11 Device Location Measurement System.” MSR-TR 2003-82.
`U. of Maryland, Nov. 13, 2003.
`Youssef, Moustafa et al., “WLAN Location Determination Via Clus
`tering and Probability Distributions”. In IEEE PerCom Mar. 2003.
`pp. 1-8.
`Krishnan, P; Krishnakumar et al." A System for LEASE: Location
`Estimation Assisted by Stationary Emitters for Indoor RFWireless
`Network.” IEEE Infocom 2004. pp. 1-11.
`Gentile, Camillo et al. "Robust Location Using System Dynamics
`and Motion Constraints.” IEEE International Conference Journal,
`vol. 3, Jun. 24, 2004. pp. 1360-1364.
`Keimargungsi, Kamol & Krishnamurthy, Prashant, “Modeling of
`Indoor Positioning Systems Based on Location Fingerprinting.”
`IEEE InfoCom 2004, pp. 1-11.
`Youssef Moustafa, et al. “On the Optimality of WLAN Location
`Determination Systems.” Technical Report UMIACS-TR, U. of
`Maryland, College Park. 2003 pp. 1-6.
`Ganu, Sachin et al., “Infrastructure-Based Location Estimation in
`WLAN Networks.” Oct. 2003, pp. 1-5.
`
`Tao, Ping, et al. “Wireless LAN Location-Sensing for Security
`Applications.” Proceedings of the 2003 ACM Workshop on Wire
`less Security,2003. San Diego, CA. pp. 11-20.
`Ladd, Andrew M. et al. Robotics-Based Location Sensing using
`Wireless Ethernet. Proceedings of the Eighth ACM International
`Conference. Sep. 2002. Atlanta, GA.
`Smailagic, Asim, et al., “Determining User Location for Context
`Aware Computing Through the Use of a Wireless LAN Infrastruc
`ture.” Dec. 2000. pp. 1-8.
`Prasithsangaree, P. et al. "On Indoor Position Location with Wire
`less LANs.” Telecommunications Prog. & Dept. of Comp. Science.
`U. of Pittsburgh, 2001 pp. 1-5.
`Wallbaum, Michael, “Wheremops: An Indoor Geolocation System.”
`IEEE Int'l Symposium on Personal Indoor and Mobile Radio
`Communication. vol. 4, pp. 1-5, 2002.
`Betson, Andrew et al. “Cloudpoint: A WiFi Location Sensing Sys
`tem.” Final Report. Apr. 30, 2003. Waterford City, Ireland. pp.
`2-267.
`Tonteri, Teemu, “A Statistical Modeling Approach to Location
`Estimation.” May 25, 2001. Helsinki. pp. 1-53.
`Battiti,Roberto et al. “Statistical Learning Theory For Location
`Fingerprinting in Wireless LANs.” Oct. 2002. Trento, Italy. pp.
`1-11.
`Brunato, Mauro & Kall'O, Csaba Kiss, “Transparent Location
`Fingerprinting for Wireless Services.” Sep. 2002. Pante di Provo,
`Italy, pp. 1-4.
`Smailagic, Asim, et al. “Location Sensing and Privacy in a Context
`Aware Computing Environment.” Pervasive Computing.2001. pp.
`1-7.
`Myllymaki.P. et al. “A Probablilistic Approach to WLAN User
`Location Estimation.” Sep. 27, 2001. IEEE Workshop on Wireless
`LANs. pp. 1-12.
`Bahl, Paramvir & Padmanabhan, Venkata N. “User Location and
`Tracking in an In-Building Radio Network.” Feb. 1999. pp. 1-12.
`Bahl, Paramvir & Padmanabhan, Venkata N. “Enhancements to the
`RADAE User Location and Tracking System.” Microsoft Research
`Technical Report, Feb. 2000. pp. 1-13.
`Clark.Graham, National Scientific Corporation. “WiFi Tracker, TM
`Data Sheet.” Downloaded Aug. 29, 2004, pp. 1.2.
`Airespace Inc.. “Airespace Control System Location Tracking.”
`Copyright 2004. www.airespace.com pp. 1-3.
`AeroScout Enterprise Visibility Sollutions. “AeroScout Engine
`Data Sheet.” Copyright 2004. www.aeroscom. pp. 1.2.
`AeroScout Enterprise Visibility Solutions. “AeroScout T1 Tag Data
`Sheet.” Copyright 2002, www.aeroscout.com, pp. 1.2.
`AeroScout Enterprise Visiblity Sollutions. “AeroScout T2 Tag Data
`Sheet.” Copyright 2004. www.aeroscout.com pp. 1.2.
`Ekahau. Ekahau Positioning Engine(TM) 2.1 Data Sheet. Copyright
`2000-2004. www.ekahau.com pp. 1.2.
`PanCo Networks, “PanCo Proximity Platform. The Industry's First
`Intelligent Location Based System, Enabling Smarter 802.11 Wire
`less LANs.” Copyright 2003, pp. 1-2.
`* cited by examiner
`
`Page 2 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 1 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`BEACON
`EMITTER
`130A
`
`NETWORK
`MONITOR
`12OB
`
`190A
`
`BEACON
`EMITTER
`
`NOISE
`SOURCE
`150
`
`NETWO
`MONITOR
`12OC
`
`BEACON
`EMITTER
`
`13OB
`
`fia
`
`o
`
`POSITIONING
`ENGINE
`1 10
`
`
`
`POSITION QUERY
`
`POSITION RESPONSE
`
`Page 3 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 2 of 22
`
`US 7,312,752 B2
`
`4.
`220A
`
`4.
`22OB
`
`4. 220C
`
`- 220D
`
`22OE
`4.
`
`22OF
`
`230
`
`22O
`
`220.J
`
`4.
`
`22
`OG
`
`220K
`
`22OM
`4.
`
`22ON
`4.
`
`220O
`4.
`
`220H
`
`220L
`
`22OP
`
`PRIOR ART
`
`FIG. 2
`
`Page 4 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 3 of 22
`
`US 7,312,752 B2
`
`SENSOR
`INFORMATION
`
`NETWORK
`MONITOR
`NFORMATION
`
`
`
`
`
`NETWORK
`YER
`310
`
`MAPPED
`SPACE
`320
`
`OBJECT
`NFORMATION
`
`
`
`PROJECTION
`330
`
`LOCATION
`
`to
`
`FIG. 3
`
`Page 5 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 4 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TRANSMIT BEACONS
`410
`
`MEASURE BEACONS
`420
`
`TRANSMIT
`MEASUREMENTS TO
`POSITIONING ENGINE
`430
`
`UPDATE MAPPED
`SPACE IN RESPONSE
`TO MEASUREMENTS
`440
`
`4OO
`
`FIG. 4
`
`Page 6 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet S of 22
`
`US 7,312,752 B2
`
`
`
`MEASURE ONE OR
`MORE BEACONSAT
`ONE OR MORE MOBILE
`OBJECTS (TAGS)
`510
`
`TRANSMIT
`MEASUREMENS
`FROM ONE OR MORE
`TAGS TO POSITONING
`ENGINE
`520
`
`DETERMINE LOCATION
`OF ONE ORMORE
`TAGS IN ACCORDANCE
`WITH TRANSMITED
`MEASUREMENTS AND
`MAPPED SPACE
`530
`
`5OO
`
`f
`
`F.G. 5
`
`Page 7 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 6 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`NTERFACE
`620
`
`-
`
`m m- - -
`
`SENSORS
`
`630
`
`
`
`NETWORK
`NTERFACE
`650
`
`LPE 110
`
`PROCESSOR
`660
`
`MEMORY
`670
`
`FIG. 6
`
`to
`
`Page 8 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 7 of 22
`
`US 7,312,752 B2
`
`START
`
`RECEIVE ONE OR
`MORE BEACONS
`710
`
`COMPUTE SIGNAL
`MEASUREMENTS
`720
`
`MEASURE OTHER
`PARAMETERS
`730
`
`TRANSMIT
`MEASUREMENTS TO
`POSITONING ENGINE
`740
`
`
`
`
`
`
`
`750
`
`MEASURE AGAIN?
`
`7OO
`
`f
`
`FIG. 7
`
`Page 9 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 8 of 22
`
`US 7,312,752 B2
`
`TRANSCEIVER
`820
`
`SENSORS
`840
`
`MOTION
`DETECTOR
`850
`
`
`
`
`
`PROCESSOR
`830
`
`ADDITIONAL OUTPUTS
`ADDITIONAL INPUTS
`
`
`
`
`
`
`
`
`
`
`
`MEMORY
`870
`
`FIG. 8
`
`Page 10 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 9 of 22
`
`US 7,312,752 B2
`
`START
`
`WAKE UP
`910
`
`MEASURE RSS AND/
`OR OTHER
`MEASUREMENTS
`920
`
`TRANSMIT DATA
`930
`
`
`
`RECEIVE
`ACKNOWLEDGEMENT/
`OTHER REO UESTS
`940
`
`PROCESS REO UESTS
`950
`
`RETURN TO SLEEP
`960
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`900
`
`f
`
`FIG. 9
`
`Page 11 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 10 of 22
`
`US 7,312,752 B2
`
`RECEIVE BEACON
`SIGNAL
`1010
`
`GENERATE
`POSITIONING
`INFORMATION
`1 O20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`DETECT MOTION?
`
`1OOO f
`
`FIG. 10
`
`TRANSMIT
`POSITONING
`INFORMATION
`1040
`
`Page 12 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 11 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RECEIVE ONE OR
`MORE BEACONS
`710
`
`
`
`COMPUTE SIGNAL
`MEASUREMENTS
`720
`
`MEASURE OTHER
`PARAMETERS
`730
`
`TRANSMIT
`MEASUREMENTS TO
`POSITIONING ENGINE
`
`1140
`
`
`
`STATIONARY
`PREVIOUSLY?
`
`
`
`MOVING PREVIOUSLY?
`
`TRANSMIT MOVING
`MESSAGE
`1 150
`
`TRANSMIT
`STATIONARY MESSAGE
`1130
`
`ro-
`
`FIG. 11
`
`Page 13 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 12 of 22
`
`US 7,312,752 B2
`
`
`
`START
`CONFIGURATION
`1210
`
`BROADCAST
`CONFIGURATION
`REOUEST
`1220
`
`RECEIVE
`CONFIGURATION
`INFORMATION
`1230
`
`CONFIGURE DEVICE
`WITH NEW SETTINGS
`1240
`
`NORMALOPERATION
`1250
`
`F.G. 12
`
`Page 14 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 13 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`SIGNA
`GENERATOR
`131 O
`
`TRANSMITTER
`132O
`
`1330
`
`FIG. 13
`
`TO/FROM NETWORK
`
`
`
`
`
`
`
`NETWORK
`INTERFACE
`1410
`
`
`
`
`
`
`
`TRANSCEVER
`142O
`
`1430
`
`
`
`PROCESSOR
`1440
`
`MEMORY
`1450
`
`FIG. 14
`
`Page 15 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 14 of 22
`
`US 7,312,752 B2
`
`
`
`CREATE AND MANTAIN
`MAPPED SPACE
`1510
`
`1500
`
`f
`
`
`
`
`
`
`
`RECEIVE DATA FROM
`MOBILE DEVICE
`152O
`
`DETERMINE LOCATION
`OF MOBILE DEVICE IN
`RESPONSE TO
`RECEIVED DATA AND
`MAPPED SPACE
`1530
`
`FIG. 15
`
`RECEIVE MEASUREMENT DATA
`FROM SENSORS
`1610
`
`ADAPT PARAMETERS FOR ONE OR
`MORE MODELS IN RESPONSE TO
`MEASUREMENT DATA AND KNOWN
`LOCATIONS OF SENSORS
`1620
`
`UPDATE MAPPED SPACE
`1630
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`so-
`
`FIG. 16
`
`Page 16 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 15 of 22
`
`US 7,312,752 B2
`
`TAG OTHER
`DATA DATA
`
`DATABASE
`1710
`
`
`
`LOCATION OUERY
`
`LOCATION RESULT
`
`PARAMETER
`CALCULATION
`1730
`
`CONDITIONER DATA
`
`u?
`110
`
`OTHER
`DATA
`
`FIG. 17
`
`CONDITIONER
`MEASUREMENTS/
`DATA
`
`
`
`MOBILE DEVICE
`MEASUREMENTS/
`DATA
`
`reak
`
`ENGINE 1
`181OA
`
`.
`
`. also
`
`ENGINEN
`181ON
`
`MASTER POSTIONNG ENGINE
`1820
`
`LOCATION OUERY
`
`LOCATION RESULT
`
`ro-
`
`FIG 18
`
`Page 17 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 16 of 22
`
`US 7,312,752 B2
`
`
`
`DATABASE
`1910
`
`CONDITIONER
`MEASUREMENTS/
`DATA
`
`MOBILE DEVICE
`MEASUREMENTS/
`DATA
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COMPUTATION
`MODEL
`1920A
`
`O O.
`
`COMPUTATION
`MODEL
`192ON
`
`MASTER POSITONING ENGINE
`1930
`
`LOCATION GRUERY
`
`LOCATION RESULT
`
`ro-
`
`FIG. 19
`
`Page 18 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 17 of 22
`
`US 7,312,752 B2
`
`CONDITIONER
`MEASUREMENTS/
`DATA
`
`
`
`MOBILE DEVICE
`MEASUREMENTS/
`DATA
`
`... .
`
`X,Y POSITION
`ENGINE
`2010
`
`.
`
`
`
`.
`
`Z POSITION
`ENGINE
`2020
`
`POSITION LOCATION
`2O3O
`
`
`
`
`
`
`
`LOCATION OUERY
`
`LOCATION RESULT
`(X,Y,Z)
`
`110 u?
`
`FIG. 20
`
`Page 19 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 18 of 22
`
`US 7,312,752 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RECEIVE MOVEMENT
`FALSE MESSAGE
`21 1 O
`
`RECEIVE
`MEASUREMENTS
`212O
`
`
`
`COMPUTE LOCATION
`2130
`
`AVERAGE COMPUTED
`LOCATIONS
`2140
`
`2100
`
`f
`
`FIG. 21
`
`Page 20 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 19 of 22
`
`US 7,312,752 B2
`
`RECEIVE MEASUREMENTS FROM
`KNOWN LOCATIONS
`2210
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`COMPUTE LOCATION BASED ON
`MEASUREMENTS
`2220
`
`COMPUTE ERROR VECTORAS
`DIFFERENCE BETWEEN COMPUTED
`LOCATION AND KNOWN LOCATION
`2230
`
`
`
`APPLY VECTOR TO CORRECT
`OTHER COMPUTED
`MEASUREMENTS
`2240
`
`2200
`
`f
`
`FIG. 22
`
`Page 21 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 20 of 22
`
`US 7,312,752 B2
`
`2310
`
`FIG. 23
`
`
`
`RECEIVE DISPLACEMENT VECTOR
`2410
`
`COMPUTE NEW LOCATION (OR
`AREA) IN RESPONSE TO PREVIOUS
`LOCATION (OR AREA) AND
`DISPLACEMENT VECTOR
`2420
`
`2400
`
`f
`
`FG. 24
`
`Page 22 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 21 of 22
`
`US 7,312,752 B2
`
`2540AF
`
`EVALUATE IN CONEXT OF
`PROBABILITY OF MOVEMENT TO
`COMPUTED LOCATION
`262O
`
`INCLUDE
`HYPOTHESIS
`2640
`
`
`
`PROB. > THRESHOLD?
`
`REMOVE
`HYPOTHESIS
`2650
`
`2600
`
`f
`
`FIG. 26
`
`Page 23 of 43
`
`

`

`U.S. Patent
`
`Dec. 25, 2007
`
`Sheet 22 of 22
`
`US 7,312,752 B2
`
`2708
`27O6
`
`2704
`
`2702
`
`f
`
`27OO
`
`B)
`U 2712
`
`f
`
`2714
`
`2716
`
`2710
`
`2726
`
`c 2724
`
`272O
`
`f
`
`2722
`
`2730
`
`FIG. 27
`
`Page 24 of 43
`
`

`

`1.
`WRELESS POSITION LOCATION AND
`TRACKING SYSTEM
`
`US 7,312,752 B2
`
`2
`location of the mobile device. These systems require install
`ing a dedicated infrastructure of fixed devices for tracking,
`which may be difficult or expensive to deploy, and may lack
`flexibility.
`There is therefore a need in the art for an accurate position
`location and tracking system suitable for a wide range of
`facilities in variable environments.
`
`SUMMARY
`
`An accurate position location and tracking system Suitable
`for a wide range of facilities in variable environments is
`disclosed. In one aspect, a system for position location
`comprises a plurality of sensors, each sensor for generating
`a first plurality of measurements of a plurality of sources, a
`plurality of objects, each object generating a second plural
`ity of measurements of the plurality of Sources, and a
`processor for receiving one or more of the first pluralities of
`measurements and one or more of the second pluralities of
`measurements from the plurality of objects, and generating
`a position location for each one or more of the plurality of
`objects in accordance with the received first pluralities of
`measurements and the respective received second plurality
`of measurements.
`In another aspect, one or more tags may be deployed, each
`comprising a receiver for receiving a plurality of beacon
`signals, a processor for generating positioning information
`in response to the received plurality of beacon signals, and
`a transmitter for transmitting the positioning information.
`In another aspect, a sensor may comprise a network
`monitor comprising a receiver for receiving a plurality of
`signals from a plurality of sources, measurement circuitry
`for measuring one or more attributes of the plurality of
`received signals to produce a plurality of measurements, and
`a transmitter for transmitting the plurality of measurements
`to a remote position location estimation device. Such as a
`position engine.
`In another aspect, position engine comprises a mapped
`space of a physical environment, a receiver for receiving
`first measurements of the physical environment from one or
`more sensors, and a processor for updating the mapped
`space in response to the received measurements. In another
`aspect, the receiver further receives second measurements
`from an object within the physical environment, and the
`processor generates an object position location estimate for
`the object from the received second measurements and the
`mapped space.
`Various other aspects are also presented.
`
`50
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is an example embodiment of a system for position
`location and tracking;
`FIG. 2 depicts a prior art wireless tracking system;
`FIG. 3 depicts an example embodiment of a positioning
`engine;
`FIG. 4 is an example method for creating a mapped space;
`FIG. 5 is an example method for determining position
`location;
`FIG. 6 depicts an example embodiment of a network
`monitor,
`FIG. 7 is an example method for network monitoring:
`FIG. 8 depicts an example embodiment of a tag:
`FIG. 9 is an example method for updating a tag location;
`FIG. 10 depicts an example method for transmission of
`parameters in response to detected motion;
`
`55
`
`60
`
`65
`
`CLAIM OF PRIORITY UNDER 35 U.S.C. S 119
`The present Application for Patent claims priority to
`Provisional Application No. 60/513,784 entitled “WIRE
`LESS TRACKING DEVICE, filed Oct. 22, 2003, Provi
`sional Application No. 60/528,052 entitled “WIRELESS
`NETWORK MONITORING SYSTEM, filed Dec. 9, 2003,
`and Provisional Application No. 60/572,690 entitled
`“WIRELESS TRACKING DEVICE, filed May 19, 2004,
`all assigned to the assignee hereof, and all hereby expressly
`incorporated by reference herein.
`
`10
`
`BACKGROUND
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`1. Field
`The present invention relates generally communications,
`and more specifically to a wireless position location and
`tracking system.
`2. Background
`There is a well-established demand for the ability to track
`the location of various objects and/or persons within various
`environments. Owners of various assets may want to be able
`to locate those assets with precision at any time, in order to
`make efficient use of them (i.e. for deployment or re
`deployment in response to varying demand). Security appli
`cations may include locating missing equipment, or prevent
`ing the loss of equipment.
`Satellite tracking systems, such as the Global Positioning
`System (GPS), and others, may be used to provide location
`determination around the globe. Satellite tracking systems
`generally do not perform well inside buildings, or in other
`locations where the satellite signals are not readily receiv
`able.
`Radio Frequency Identification (RFID) systems are being
`developed to track and locate items within defined areas.
`Passive RFID systems are limited to detecting the presence
`of an item within range of a portal. Typically, a portal or
`interrogator sends out a query signal and any tag (i.e., a
`device included in or attached to an object to be tracked)
`within range responds. Passive RFID tags generally do not
`have a power source. Active RFID systems function in a
`similar manner, but the active tags have a power source,
`typically a battery, for longer range operation. RFID systems
`(active and passive) require installing a dedicated infrastruc
`ture of portals or interrogators for tracking which may be
`difficult or expensive to deploy, and may lack flexibility.
`Other systems employ RF fingerprinting, whereby mobile
`devices measure signal strength from one or more beacons
`and attempt to correlate those measurements with signature
`measurements taken throughout the defined area. One
`example is the RADAR system. (See P. Bahl and V. N.
`Padmanabhan, "Radar: An In-Building RF-based User
`Location and Tracking System', in Proceedings of the IEEE
`Infocom 2000, Tel-Aviv, Israel, vol. 2, March 2000, pp.
`775-784). One drawback of systems such as these is that the
`signature measurements are taken infrequently, and the
`measurement task may be cumbersome and expensive. The
`RF environment may change significantly throughout any
`given time period, and the accuracy of the location calcu
`lation will be degraded accordingly.
`Other systems employ triangulation, whereby fixed
`devices measure the signal strength or propagation delay of
`a mobile device and use this information in conjunction with
`the known location of the fixed device to compute the
`
`Page 25 of 43
`
`

`

`US 7,312,752 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`3
`FIG. 11 is an example method for use in a mobile device
`or tag to indicate whether it is in motion or stationary;
`FIG. 12 depicts an example method for configuration of
`a device Such as a mobile device or network monitor;
`FIG. 13 depicts an example embodiment of a beacon
`emitter;
`FIG. 14 depicts an example embodiment of an access
`point;
`FIG. 15 is an example method for performing position
`location;
`FIG. 16 depicts an example method for creating and
`maintaining a mapped space;
`FIG. 17 depicts an example embodiment of a positioning
`engine;
`FIG. 18 depicts an alternate embodiment of a positioning
`engine;
`FIG. 19 depicts yet another alternate embodiment of a
`positioning engine;
`FIG. 20 depicts another alternate embodiment of a posi
`tioning engine;
`FIG. 21 is an example embodiment of a method for
`determining an average location of a mobile device that is
`not moving:
`FIG. 22 depicts an example method for performing cor
`rection to computed measurements;
`FIG. 23 depicts a variety of techniques for using a
`displacement vector in determining a new computed loca
`tion;
`FIG. 24 is an example method for applying a displace
`ment vector to refine decision location results;
`FIG. 25 illustrates the use of known barriers to refine
`positioning estimates;
`FIG. 26 depicts an example method for selecting location
`hypotheses for use in making a computed location determi
`nation; and
`FIG. 27 depicts various examples of position results.
`
`DETAILED DESCRIPTION
`
`One or more exemplary embodiments described herein
`are set forth in the context of a wireless data communication
`system. While use within this context is advantageous,
`different embodiments of the invention may be incorporated
`in different environments or configurations. In general, the
`various systems described herein may be formed using
`Software-controlled processors, integrated circuits, or dis
`crete logic. The data, instructions, commands, information,
`signals, symbols, and chips that may be referenced through
`out the application are advantageously represented by Volt
`ages, currents, electromagnetic waves, magnetic fields or
`particles, optical fields or particles, or a combination thereof.
`In addition, the blocks shown in each block diagram may
`represent hardware or method steps. The word “exemplary’
`is used herein to mean 'serving as an example, instance, or
`illustration.” Any embodiment described herein as “exem
`plary” is not necessarily to be construed as preferred or
`advantageous over other embodiments.
`Position Location System
`According to one aspect of the invention, a model of an
`environment in which an object is to be located is main
`tained. The environment comprises a physically mappable
`space. One or more sensors may be deployed throughout the
`space to monitor the environment and provide feedback to
`what may be referred to as a "positioning engine', which
`may be a central or distributed computing resource for
`receiving feedback from one or more sensors and maintain
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`ing a mapping of the environment, referred to as a "mapped
`space'. An object to be located transmits information com
`prising one or more measurements to the positioning engine,
`which projects the object information onto the mapped space
`and determines the objects location therefrom.
`FIG. 1 depicts system 100 for position location of various
`devices within the system. In this example embodiment,
`object 170 provides information allowing its location to be
`determined within an area of a facility covered by system
`100. Positioning engine 110, detailed further below, may be
`used for determining the position of and tracking of one or
`more objects 170 within the system.
`Positioning engine 110 may receive a position query from
`an external application, or an end user. In response to a
`position query, positioning engine 110 provides a position
`response. The position response may include various infor
`mation, such as the coordinates of the object, which may be
`two-dimensional, in which case an (X, Y) position may be
`returned, or a three-dimensional position (X, Y, Z) may be
`returned. In addition, other parameters such as a confidence
`level for a position (or area within which a position is
`expected) may be returned. Various other types of position
`responses may be returned, examples of which are detailed
`further below.
`In the example embodiment, object 170 may be any object
`or asset for which tracking is desired. An object 170 may
`also be referred to herein as a mobile device or a tag. A tag
`may be a device that is attached to the object for which
`tracking is desired, example embodiments of which are
`detailed below. In an alternative embodiment, object 170
`may incorporate the circuitry required to perform wireless
`tracking, as described herein. Object 170 receives wireless
`signals transmitted from various beacon emitters 130. A
`plurality of beacon emitters 130 may be deployed for
`generating beacons, or more generically as Source signals,
`throughout some or all of the environment. Object 170, after
`receiving and measuring characteristics of the received
`beacon signals, and optionally measuring other environment
`parameters, transmits the measurements to positioning
`engine 110 via one of a variety of connections. In this
`example object 170 communicates with Access Point (AP)
`180B over wireless link 190B. Access points are well known
`in the art. In the example embodiment, an IEEE 802.11
`Wireless Local Access Network (WLAN) may be deployed.
`Example WLANs include IEEE standards 802.11 (802.11a
`g, for example), IEEE 802.15.4, and derivatives thereof.
`Any other wireless communications standard or specifi
`cation may also be deployed. Example cellular-based data
`systems include: (1) the “TIA/EIA-95-B Mobile Station
`Base Station Compatibility Standard for Dual-Mode Wide
`band Spread Spectrum Cellular System” (the IS-95 stan
`dard), (2) the standard offered by a consortium named "3rd
`Generation Partnership Project’ (3GPP) and embodied in a
`set of documents including Document Nos. 3G TS 25.211,
`3G TS 25.212, 3G TS 25.213, and 3G TS 25.214 (the
`W-CDMA standard), (3) the standard offered by a consor
`tium named "3rd Generation Partnership Project 2 (3GPP2)
`and embodied in “TR-45.5 Physical Layer Standard for
`cdma2000 Spread Spectrum Systems” (the IS-2000 stan
`dard), and (4) the high data rate (HDR) system that conforms
`to the TIA/EIA/IS-856 standard (the IS-856 standard).
`Access point 180B communicates with positioning engine
`110 over network connection 160B. It will be clear to those
`of skill in the art that any number of wireless and wired
`networks may be deployed, consistent with the principles
`disclosed herein. In this example, positioning engine 110
`communicates over two wired networks, 160A and 160B.
`
`Page 26 of 43
`
`

`

`US 7,312,752 B2
`
`10
`
`15
`
`30
`
`40
`
`25
`
`5
`Wireless network 160A connects the positioning engine 110
`with access point 180A, as well as a network monitor 120B.
`Network monitors 120, also referred to as conditioners,
`calibrators, or sensors, may be deployed throughout the
`facility covered by system 100 to monitor and measure
`various environmental parameters associated with the net
`work. The sensors 120 may measure one or more attributes
`of the signal (which may be any type of signal, including but
`not limited to an RF signal).
`The plurality of sensors 120 may measure the surrounding
`physical environment and report to the positioning engine
`110 any number of measurements, including temperature,
`humidity, signal characteristics of beacon emitters 130 and/
`or other noise or signal Sources, etc. The feedback may be
`provided over time, such that characterization of the envi
`ronment, correlated with one or more measurements, may be
`determined. For example, the effects of the reception of one
`or more beacons may be characterized as a function of
`temperature, humidity, or both. The feedback may be pro
`vided over any network or combination of networks, such as
`network 160 or 190.
`In an alternative embodiment, the environment may
`inherently contain one or more signal sources that the
`sensors may measure and send to the positioning engine 110.
`These inherent signal sources may change over time, and
`may or may not be designed for providing the signal for
`measurement. A source may be another communication
`system or device not associated with the location system, or
`it may be have no deliberate communication function, i.e. it
`may be a noise source 150 or what would otherwise be
`characterized as a jammer signal 140.
`A network monitor 120 delivers the measurements to
`positioning engine 110 over any type of network (i.e.
`wireless or wired networks). A network monitor is one type
`of sensor. In this example network monitor 120B commu
`35
`nicates with positioning engine 110 on wired network 160A.
`Note that network monitor 120C communicates with access
`point 180B over wireless link 190B. Network monitor 120A
`communicates with access point 180A over wireless link
`190A. The wireless links depicted need not conform to
`identical communication standards (i.e., one may be an
`802.11 standard, while another may conform to another
`standard or specification, such as a cellular data or other
`wireless data connection).
`Another example wireless LAN is the IEEE 802.15.4
`standard, which may be deployed in a mobile device for
`communication using lower power. In one embodiment, a
`low power 802.15.4 radio link may be used to communicate
`between objects 170, while simultaneous communication
`links with 802.11 access points may also be supported.
`In an alternate embodiment, not depicted in FIG. 1,
`detailed further below, an object 170 may communicate
`directly with a network monitor 120 over a wireless link. In
`such an example the wireless link between the object 170
`and the network monitor 120 may be a low power link, such
`55
`as an 802.15.4 link, while the network monitor 120 com
`municates with an access point 180, for ultimate communi
`cation with position engine 110, over another WLAN
`(802.11, for example).
`Also shown in FIG. 1 is a wireless link 190A between
`access point 180A and beacon emitter 130C. In one embodi
`ment, a beacon emitter may be programmable, so as to
`configure the type of beacon signal transmitted. A beacon
`emitter may also be configured to send any other informa
`tion that may be desirable to transmit or broadcast along
`with the beacon signal. This may be accomplished through
`a wired or wireless conne