US007286835B1
`
`(12)
`
`United States Patent
`Dietrich et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,286,835 B1
`Oct. 23, 2007
`
`(54) ENHANCED WIRELESS NODE LOCATION
`USING DIFFERENTIAL SIGNAL STRENGTH
`METRIC
`
`(75) Inventors: Paul F. Dietrich, Seattle, WA (US);
`Gregg Scott Davi, Milpitas, CA (US)
`
`6,198,935 B1
`6,212,391 B1
`6,226,400 B1
`6,236,365 B1
`
`3/2001 Saha et a1.
`4/2001 Saleh et a1.
`5/2001 D011
`5/2001 LeBlanc et a1.
`
`(73) Assignee: Airespace, Inc., San Jose, CA (US)
`
`(COnIinued)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 320 days.
`
`EP
`
`FOREIGN PATENT DOCUMENTS
`0 930 514 A2
`7/1999
`
`(21) Appl. No.: 10/938,460
`
`(22) Filed:
`
`Sep. 10, 2004
`
`(Continued)
`OTHER PUBLICATIONS
`
`(51) Int. Cl.
`(200601)
`H04Q 7/20
`(52) US. Cl. ................................................. .. 455/456.1
`
`glcal Areas-locatlon enabllng the W1-F1 network. Apr.
`“Ekahau LO .
`.
`.
`.
`.
`,,
`4, 2003. Ekahau, Inc., Saratoga, CA. Company’s URL: WWW.
`ekahau?om,
`
`(58) Field of Classi?cation Search ........... .. 455/456.1,
`455/6701; 342/35701, 450
`See appl1cat1on ?le for complete search hlstory.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`3/1981 Davis et :11.
`4,254,467 A
`7/1991 Bankston et :11.
`5,028,848 A
`7/1994 Stilp et a1. ................ .. 342/387
`5,327,144 A *
`5,375,140 A 12/1994 Bustamante et a1.
`5,394,158 A
`2/1995 Chia
`5,396,582 A
`3/1995 Kahkoska
`5,564,079 A 10/1996 Olsson
`5,570,412 A 10/1996 LeBlanc ................ .. 455/4562
`5,666,662 A
`9/1997 Shibuya
`5,684,860 A 11/1997 Milani
`5,717,406 A
`2/1998 Sanderford et a1. ....... .. 342/457
`5,732,354 A
`3/1998 MacDonald
`5,945,948 A
`8/1999 Buford et :11.
`6,112,095 A
`8/2000 Wax et :11.
`6,115,605 A
`9/2000 Siccardo et :11.
`6,134,338 A 10/2000 Solberg et a1.
`6,134,448 A 10/2000 Shoji et :11.
`6,140,964 A 10/2000 Sugiura et 31.
`6,167,274 A 12/2000 Smith
`
`58
`
`_
`(Con?rmed)
`Primary ExamineriRafael PereZ_GutierreZ
`Assistant Examiner4Gary Au
`(74) Attorney, Agent, or F irmiMark J. Spolyar
`
`(57)
`
`ABSTRACT
`
`A Wireless node location mechanism that employs a differ
`ential signal strength metric to reduce the errors caused by
`variations in Wireless node transmit poWer, errors in signal
`strength detection, and/or direction-dependent path loss. As
`opposed to using the absolute signal strength or poWer of an
`RF signal transmitted by a Wireless node, implementations
`of the location mechanism compare the diiferences betWeen
`signal strength values detected at various pairs of radio
`receivers to corresponding diiferences characterized in a
`model of the RF environment. One implementation searches
`for the locations in the model betWeen each pair of radio
`receivers Where their signal strength is different by an
`observed amount.
`
`34 Claims, 5 Drawing Sheets
`
`Wireless Nude
`Location Module
`
`Page 1 of 18
`
`SAMSUNG EX-1045
`
`

`

`US 7,286,835 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`6/2001 Patel
`6,243,811 B1
`6/2001 Dupray
`6,249,252 B1
`7/2001 R210 et al.
`6,269,246 B1
`8/2001 Cromer et al.
`6,272,541 B1
`8/2001 Sugiura et al.
`6,275,190 B1
`8/2001 LBISSOII 6t
`6,282,427 B1
`10/2001 Sugiura et al.
`6,304,218 B1
`11/2001 Rappaport et al.
`6,317,599 B1
`11/2001 Kovach et al. ........ .. 455/456.5
`6,317,604 B1
`7/2002 Tekjnay
`6,414,634 B1
`7/2002 Koshima et a1,
`6,415,155 B1
`8/2002 McDonald
`6,441,777 B1
`9/2002 Dara-Abrams et a1,
`6,456,892 B1
`2/2003 Jang
`6,526,283 B1
`4/2003 Smith
`6,556,942 B1
`6/2003 Hills et 31,
`6,581,000 B2
`11/2003 Haymes et al. ........... .. 455/423
`6,650,896 B1
`12/2003 Moore et a1,
`6,664,925 B1
`l/2004 Gray et al. ............... .. 342/463
`6,674,403 B2
`3/2004 Johnson
`6,704,352 B1
`4/2004 D’SouZa et a1,
`6,728,782 B1
`6/2004 Won et a1,
`6,754,488 B1
`7/2004 Bims
`6,760,318 B1
`7/2004 Nessett et a1,
`6,766,453 B1
`9/2004 Bims
`6,788,658 B1
`9/2004 Bahl et al. ............. .. 455/456.1
`6,799,047 B1
`10/2004 Hsu
`6,804,394 B1
`2/2005 Rappapon et a1,
`6,850,946 B1
`8/2005 Proctor
`6,925,070 B2
`1/2006 Kaiser et al. ............. .. 702/150
`6,990,428 B1
`7,123,924 B2 10/2006 Cuffam
`2002/0036569 A1
`3/2002 Martin
`2002/0045424 A1
`4/2002 Lee ........................... .. 455/41
`2002/0102988 A1
`8/2002 Myllymaki
`2002/0115445 A1
`8/2002 Myllymaki
`2002/0118118 A1
`8/2002 Myllyrnaki et al.
`2002/0154134 A1 10/2002 Matsui
`2002/0168958 A1 11/2002 Ford et 31,
`2002/0174335 A1
`11/2002 Zhang et al.
`2002/0176366 A1
`11/2002 Ayyagari et a1,
`2002/0186723 A1 12/2002 ChOi
`2003/0023746 A1
`1/2003 Loguinov
`2003/0117985 A1
`6/2003 Fujii et 31,
`2003/0130987 A1
`7/2003 Edlund et al.
`2003/0135486 A1
`7/2003 Edlund et al.
`2003/0135762 A1
`7/2003 Macaulay
`2003/0188006 A1 10/2003 Bard
`2003/0198208 A1 10/2003 Koos, Jr. et al.
`2004/0066757 A1
`4/2004 Molteni et al. ........... .. 370/329
`2004/0075277 A1
`4/2004 Myllyrnaki et al.
`2004/0111397 A1
`6/2004 Chen et al.
`2004/0151377 A1
`8/2004 Boose et al.
`2004/0166878 A1
`8/2004 Erskine et al. ......... .. 455/4561
`2004/0176108 A1
`9/2004 Misikangas
`2004/0186847 A1
`9/2004 Rappaport et al.
`2004/0198373 A1 10/2004 Ford et a1~
`2004/0198392 A1 10/2004 Harvey et al. ......... .. 455/456.1
`2004/0203910 A1 10/2004 Hind et al. ............ .. 455/456.1
`2004/0236547 A1 11/2004 Rappaport et al.
`2004/0259554 A1 12/2004 RQPPaPOIT et a1~
`2004/0259555 A1 12/2004 RaPPaPOIt et a1~
`Zoos/0128139 A1
`6/2005 Misikangas et a1~
`Zoos/0131635 A1
`6/2005 MY1_1Ymakieta1~
`Zoos/0136944 A1
`6/2005 Mlslkangas et 31'
`2005/0185615 A1
`8/2005 Zegelin .................... .. 370/331
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`
`0 967 816 A1
`1018 457 A1
`1296 531 A1
`
`12/1999
`7/2000
`3/2003
`
`EP
`JP
`W0
`WO
`W0
`W0
`W0
`W0
`
`1 301 055 A1
`02044929
`WOW/33386
`WO98/41048
`WO99/08909
`WO 02/43425 Al
`W0 02/054813 Al
`W0 03/023443 A2
`
`4/2003
`2/1990
`9/1997
`9/1998
`2/l999
`5/2002
`7/2002
`3/2003
`
`OTHER PUBLICATIONS
`
`“Ekahau Positioning Engine 2.0: Product Overview.” Apr. 4, 2003.
`Ekahau, Inc., Saratoga, CA. URL: http://www.ekahau.com/prod
`ucts/positioningengine/.
`“Ekahau Positioning Engine 2.0: Data Sheet.” Apr. 4, 2003. Ekahau,
`Inc., Saratoga, CA. URL: http://www.ekahau.com/pdf/EPEi2.
`OLdatasheetPDF.
`“Indoor Positioning in 802.11b Networks.” Apr. 4, 2003. Ekahau,
`1110, Saratoga, CA. URL: httpr//WWW.ekahau.conVproducts/
`positioningengine/features.htrnl.
`“InFielder” Apr~ 22, 2003 Wireless Valley, Austin, TX. URL:
`http://www.wirelessvalley.com/Products/InFielder/InFielder.asp.
`“LANFielder.” Apr. 22, 2003. Wireless Valley, Austin, TX. URL:
`http://www.wirelessvalley.com/Products/LANFielder/LANFielder.
`asp.
`“Optimatic.” Apr. 22, 2003. Wireless Valley, Austin, TX. URL:
`http://www.wirelessvalley.com/Products/Optimatic/Optimatic.asp.
`“Predictor.” Apr. 22, 2003. Wireless Valley, Austin, TX. URL:
`http://www.wirelessvalley.com/Products/Predictor/Predictor.asp.
`“LANFielder Product Literature.” Feb. 10, 2004. Wireless Valley,
`Austin, TX. URL: http://www.wirelessvalley.com/Assets/bro
`ChureS/LanFielderpdf.
`Conley, C.. “Securing WLANS with Location-Enabled Networks.”
`Wireless Security Perspectives, vol. 5, No. 3. Mar. 2003. Organi
`zation’s URL: WWWcnp-Wireless.eon?wsphtml.
`“Company Information.” Apr. 6, 2004. Corsair Communications:A
`LightBridge Company, Burlington, MA. Company’s URL: www.
`lightbridgecom.
`“Corporate Fact Sheet.” Aruba Wireless Networks, San Jose, CA.
`Feb. 10, 2004. URL: http://www.arubanetworks.com/pdf/corporate
`fact sheetpdf.
`“Airwave Rogue Access Point Detection.” 2002. Airwave Wireless,
`Inc. San Mateo, CA. URL: http://airwave.com/features.html.
`Geier, J. “Identifying Rogue Access Points.” Jan. 6, 2003. Wi-Fi
`Planet Tutorials. URL: http://www.wi-?planet.com/tutorials/article.
`php/1564431.
`Brewin, B. “IBM Develops Tool to Detect Rogue Wireless LAN
`Access Points.” Jun. 17, 2002. Computerworld, Framingham, MA.
`URL: http://www.computerworld.com/mobiletopics/mobile/story/
`0,10801,72065,00.html.
`Bulusu, N., Heidemann, J., Estrin, D. “GPS-less Low Cost Outdoor
`Localization for Very Small Devices.” IEEE Personal Communi
`cations, Oct. 2000. URL: http://lecs.cs.ucla.edu/~bulusu/papers/
`Bulusu00a.pdf.
`“AeroScout WLAN Location System.” Downloaded on Nov. 10,
`2003 from http://www.bluesoft-inc.com/wlan.asp Bluesoft, Inc.,
`San Mateo, CA.
`“Cognio Announces Breakthrough Location Technology for WLAN
`Deployments,” Downloaded on NOV, 10, 2003 from httpy/WWW
`cogniogonl/pressidetail,aspiiitemlDi?) (jognio, Inc‘, Waltham,
`MA,
`“WhereNet Main Page.” Downloaded Nov. 10, 2003 from http://
`www.wherenet.com/ Wherenet, Santa Clara, CA.
`Small, J., Smailagic, A., and Siewiorek, D.P. “Determining User
`Location For Context Aware Computing Through the Use of a
`Wireless LAN Infrastructure.” Institute for Complex Engineered
`Systems, Carnegie_Me110n University, Pittsburgh, PA, 2000' Avai1_
`able at http://www-2.cs.cmu.edu/~aura/docdir/small00.pdf.
`Kishan, A., Michael, M., Rihan, S., and R. Biswas. “Halibut: An
`Infrastructure for Wireless LAN Location-Based Services.” Tech
`nical paper for Course CS444n, Computer Science Department,
`Stanford University, Stanford CA, Jun. 2001. Previously available
`at http ://fern2 .stanford.edu/cs444n/paper.pdf.
`
`Page 2 of 18
`
`

`

`US 7,286,835 B1
`Page 3
`
`Bahl, P. and Padmanabhan, V.N. “RADAR: An In-Building RF
`based User Location and Tracking System.” IEEE Infocom 2000,
`vol. 2, Mar. 2000, pp. 775-784.
`“Positioning in Wireless Networks Reference.” Downloaded on Jul.
`28, 2005 from http://binary.engin.brown/edu/. BINARY Group,
`Division of Engineering, Brown University, Providence, RI. Avail
`able
`online
`at
`http://binary.engin.brown.edu/publication/
`PositioningiRefpdf.
`Chirumamilla, Mohan K. and Ramamurthy, Byrav. “Agent Based
`Intrusion Detection and Response System for Wireless LANs.”
`IEEE Int’l Conference on Communications, 2003, vol. 1, pp.
`492-496.
`“IBM Research Demonstrates Industry’s First Auditing Tool for
`Wireless Network Security.” Jul. 12, 2001, Hawthorne, NY IBM
`Research News, ‘Online. URL: http://domino.research.ibm.com/
`comm/pr.nsf/pages/news.20010712iwireless.html.
`“IBM Researchers Demonstrate Industry’s First Self-Diagnostic
`Wireless Security Monitoring Tool.” Jun. 21, 2002, Hawthorne,
`NY IBM NIEUWS, ‘Online! URL: http://domino.research.ibm.
`com/comm/prnsf/pages/news.20020617idwsa.html.
`“Assessing Wireless Security with AiroPeek and AiroPeek NX.” A
`WildPackets Academy Tutorial from www.wildpackets.com,
`WildPackets Inc., Walnut Creek, CA. Jan. 16, 2003. URL: http://
`www.wildpackets.com/elements/whitepapers/AiroPeekiSecurity.
`pdf.
`“AiroPeek and Wireless Security: Identifying and Locating Rogue
`Access Points.” A WildPackets Academy Tutorial from www.
`wildpackets.com, WildPackets Inc., Walnut Creek, CA. Jan. 16,
`2003. URL: http://www.wildpackets.com/elements/whitepapers/
`RogueAccessPointspdf.
`Craiger, J. P. “802.11, 802.1X, and Wireless Security.” Jun. 23, 2002.
`From the SANS’ Information Security Reading Room on www.
`sans.org, The SANS Institute, Bethesda, MD. URL: http://www.
`sans.org/rr/papers/68/171.pdf.
`Baily, S. “Is IEEE 802.1X Ready for General Deployment?” Apr. 7,
`2002. From the SANS’ Information Security Reading Room on
`www.sans.org, The SANS Institute, Bethesda, MD. URL: http://
`www.sans.org/rr/papers/9/709.pdf.
`“Location Determination Papers”, List of publications maintained
`by Moustafa A. Youssef, Department of Computer Science, Uni
`versity of Maryland, College Park, MD 20742. Available online, and
`downloaded Feb. 9, 2006 at http://ww.cs.umd.edu/~moustafa/
`locationipapershtm.
`“Positioning in Wireless Networks Reference” BINARY Group,
`Division of Engineering, Brown University, Providence, RI 02912,
`Available online, and downloaded Feb. 9, 2006 as binary.engin.
`brown.edu/publication/PositioninggRefpdf.
`L.M. Ni, Y. Liu, YC. Lau and AP. Patil. “LANDMARC: Indoor
`Location Sensing Using Active RFID.” Proceedings of the First
`IEEE International Conference of Pervasive Computing and Com
`munications 2003 (PerCom ’03).
`G. Wol?e, R. Wahl, P. Wertz, P Wildbolz and F. Landstorfer.
`“Dominant Path Prediction Model for Indoor Scenarios.” German
`Microwave Conference (GeMIC) 2005, Ulm (Germany), Apr. 2005
`Paper.
`P. Wertz, G. Wol?e, R. Hoppe, D. Zimmermann and FM.
`Landstorfer. “Enhanced Localization Technique within Urban and
`Indoor Environments based on Accurate and Fast Propagation
`Models.” European Wireless, 2002, Florence, Italy.
`
`Steven Fortune, “Algorithms for prediction of indoor radio propa
`gation”, sjf@research.att.com, Jan. 7, 1998, Bell Laboratories,
`Murray Hill, New Jersey 07974.
`A. Rajkumar, B.F. Naylor, F. Feisullin and L. Rogers, “Predicting
`RF Coverage in Large Environments using Ray-Beam Tracing and
`Partitioning Tree Represented Geometry”, submitted to the ACM
`Journal of Wireless Networks after revision on Oct. 12, 1995, AT&T
`Bell Laboratories, Murray Hill, NJ 07974.
`Reinaldo A. Valenzuela, Steven Fortune, and Jonathan Ling,
`“Indoor Propagation Prediction Accuracy and Speed Versus Num
`ber of Re?ections in Image-Based 3-D Ray-Tracing”, 1998, Bell
`Laboratories, Lucent Technologies, Holmdel, NJ 07733.
`Bahl, P., Padmanabhan, V. and Balachandran, A. A Software System
`for Locating Mobile Users: Design, Evaluation and Lessons.
`Microsoft Research Technical Report MSR-TR-2000-12 [online],
`Apr. 2000 [retrieved on Jan. 26, 2006]. Retrieved from the Internet:
`<URL:
`http ://research .micro soft. com/~padmanab/papers/radar/
`pdf>.
`PCT Noti?cation of Transmittal of The International Search Report
`and The Written Opinion of the International Searching Authority,
`or the Declaration (PCT. Rule 44.1), dated Jan. 11, 2006, Interna
`tional Application No. PCT/US05/06608).
`1St Of?ce Action from US. Appl. No. 10/802,366, ?led Mar. 16,
`2004, entitled “Location of Wireless Nodes Using Signal Strength
`Weighting Metric”.
`2nd O?ice Action from US. Appl. No. 10/802,366, ?led Mar. 16,
`2004, entitled “Location of Wireless Nodes Using Signal Strength
`Weighting Metric”.
`Of?ce Action from US. Appl. No. 10/788,645, ?led Feb. 27, 2004,
`entitled “Selective Termination of Wireless Connections to Refresh
`Signal Information in Wireless Node Location Infrastructure”.
`Of?ce Action from US. Appl. No. 10/794,842, ?led Mar. 5, 2004,
`entitled “Selective Termination of Wireless Connections to Refresh
`Signal Information in Wireless Node Location Infrastructure”.
`Of?ce Action from US. Appl. No. 10/848,276, ?led May 18, 2004,
`entitled “Wireless Node Location Mechanism Featuring De?nition
`of Search Region to Optimize Location Computation”.
`PCT Noti?cation of Transmittal of The International Search Report
`and The Written Opinion of the International Searching Authority,
`or the Declaration (PCT Rule 44.1), dated Mar. 31, 2006, Interna
`tional Application No. PCT/USO5/05927).
`PCT Noti?cation of Transmittal of The International Search Report
`and The Written Opinion of the International Searching Authority,
`or the Declaration (PCT Rule 44.1), dated Apr. 28, 2006, Interna
`tional Application No. PCT/USO5/06528).
`PCT Noti?cation of Transmittal of The International Search Report
`and The Written Opinion of the International Searching Authority,
`or the Declaration (PCT Rule 44.1), dated Apr. 19, 2006, Interna
`tional Application No. PCT/U SO5/ 14062).
`International Standard, ISO/IEC 8802-11 ANSI/IEEE Std. 802.11,
`1999 Edition, Part II: Wirelss LAN Medium Access Control (MAC)
`and Physical Layer (PHY) speci?cations, pp. 122-137.
`“tcp-masq” Internet citation http://speed.cis.nctu.edu.tw/bandwith/
`opensource/, Daa Sheet Cisco Aironet 1200 Series Access Point, pp.
`1-13, posted Mar. 11, 2002.
`
`* cited by examiner
`
`Page 3 of 18
`
`

`

`U.S. Patent
`
`Oct. 23, 2007
`
`Sheet 1 0f 5
`
`US 7,286,835 B1
`
`59
`
`Wireless Node
`Location Module
`
`Page 4 of 18
`
`

`

`U.S. Patent
`
`Oct. 23, 2007
`
`Sheet 2 0f 5
`
`US 7,286,835 B1
`
`r—\
`Locate_Node
`
`102
`
`Select Top M
`IRTs
`V
`104
`Collect RSSI
`Measurements for J
`Selected IRTs
`W
`106
`Select RF Coverage j
`Maps based Selected
`IRTs
`
`/Fori=1t:(M~1) 130/0 108
`
`W
`110
`/ Forj = (1+1) to M Do k
`V
`112
`AS sij = ssi / J
`
`114
`
`’ J
`
`.
`
`l’
`
`=
`
`l
`
`116
`
`W
`End FOl‘j = (1+1) to M Do
`
`End For i = 1 to (M~1) Do
`
`120
`Select Location
`that /
`ErrSurfDiff
`Fig]
`
`Page 5 of 18
`
`

`

`U.S. Patent
`
`0a. 23, 2007
`
`Sheet 3 0f 5
`
`US 7,286,835 B1
`
`5O
`
`1O
`\
`I
`Central Control
`Element
`
`24
`
`14 [J
`Access j
`Element
`l
`
`54
`5 2
`
`[1‘)
`
`I
`ACCESS
`EkmEm \
`12
`
`K1 3
`ACC?SS
`Element
`l
`
`#15
`ACC€SS
`Element
`I
`
`I
`ACCESS
`Element \
`ll
`
`I
`Central Centrol
`Element
`k
`
`1 6
`
`Page 6 of 18
`
`

`

`U.S. Patent
`
`Oct. 23, 2007
`
`Sheet 4 0f 5
`
`US 7,286,835 B1
`
`/62
`
`Flag. Detector
`A
`
`V
`
`Data Path
`
`66
`
`k
`
`>
`
`C tr 1
`on 0
`\~ path
`K
`6 4
`
`70
`Wireless Node J
`Data Collector
`
`f 76
`68
`\
`Processor
`
`/90
`
`(
`<
`(
`
`Wireless
`Node
`Locator
`
`78
`\ AP Signal J
`’ Strength Matrix
`
`8O
`f
`RF Physical
`Model Database
`
`Page 7 of 18
`
`

`

`U.S. Patent
`
`Oct. 23, 2007
`
`Sheet
`5 0f 5
`
`US 7,286,835 B1
`
`Locate_Node
`
`___4
`
`Select Top M
`IRTs
`W
`Collect RSSI
`Measurements for
`Selected IRTs
`V
`Select RF Coverage
`Maps based Selected
`IRTs
`
`Ix.) O CD
`
`l
`Compute
`Differential Error /
`Surface
`J,
`
`Compute Error Surface
`Based On Absolute
`Signal Strength Values
`
`l
`
`Add Error Surface
`and Differential
`Error Surface
`V
`Estimate Location
`Based on Aggregated
`Error Surface
`
`Fig._5
`
`Page 8 of 18
`
`

`

`US 7,286,835 B1
`
`1
`ENHANCED WIRELESS NODE LOCATION
`USING DIFFERENTIAL SIGNAL STRENGTH
`METRIC
`
`CROSS-REFERENCE TO RELATED PATENT
`APPLICATIONS
`
`This application makes reference to the following com
`monly oWned US. patent applications and/ or patents, Which
`are incorporated herein by reference in their entirety for all
`purposes:
`US. patent application Ser. No. 10/ 155,938 in the name
`of Patrice R. Calhoun, Robert B. O’Hara, Jr. and Robert J.
`Friday, entitled “Method and System for Hierarchical Pro
`cessing of Protocol Information in a Wireless LA ,”
`US. patent application Ser. No. 10/ 183,704 in the name
`of Robert J. Friday, Patrice R. Calhoun, Robert B. O’Hara,
`Jr., Alexander H. Hills and Paul F. Dietrich, and entitled
`“Method and System for Dynamically Assigning Channels
`Across Multiple Radios in a Wireless LA ,”
`US. patent application Ser. No. 10/407,357 in the name
`of Patrice R. Calhoun, Robert B. O’Hara, Jr. and Robert J.
`Friday, entitled “Method and System for Hierarchical Pro
`cessing of Protocol Information in a Wireless LAN,”
`US. patent application Ser. No. 10/407,370 in the name
`of Patrice R. Calhoun, Robert B. O’Hara, Jr. and David A.
`Frascone, entitled “Wireless Network System Including
`Integrated Rogue Access Point Detection,” and
`US. patent application Ser. No. 10/447,735 in the name
`of Robert B. O’Hara, Jr., Robert J. Friday, Patrice R.
`Calhoun, and Paul F. Dietrich and entitled “Wireless Net
`Work Infrastructure including Wireless Discovery and Com
`munication Mechanism,” and
`US. patent application Ser. No. 10/788,645 in the name
`of Robert J. Friday and Alexander H. Hills, entitled “Selec
`tive Termination of Wireless Connections to Refresh Signal
`Information in Wireless Node Location Infrastructure,”
`US. patent application Ser. No. 10/ 802,366 in the name
`of Paul F. Dietrich, Gregg Scott Davi and Robert J. Friday,
`entitled “Location of Wireless Nodes Using Signal Strength
`Weighting Metric,” and
`US. patent application Ser. No. 10/848,276 in the name
`of Paul F. Dietrich, Gregg Scott Davi and Robert J. Friday,
`entitled “Wireless Node Location Mechanism Featuring
`De?nition of Search Region to Optimize Location Compu
`tation.”
`
`FIELD OF THE INVENTION
`
`The present invention relates to estimating the location of
`Wireless nodes in Wireless netWork environments and, more
`particularly, to a differential signal strength metric directed
`to improving the accuracy of Wireless node location mecha
`nisms.
`
`BACKGROUND OF THE INVENTION
`
`Market adoption of Wireless LAN (WLAN) technology
`has exploded, as users from a Wide range of backgrounds
`and vertical industries have brought this technology into
`their homes, o?ices, and increasingly into the public air
`space. This in?ection point has highlighted not only the
`limitations of earlier-generation systems, but the changing
`role WLAN technology noW plays in people’s Work and
`lifestyles, across the globe. Indeed, WLANs are rapidly
`changing from convenience netWorks to business-critical
`netWorks. Increasingly users are depending on WLANs to
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`improve the timeliness and productivity of their communi
`cations and applications, and in doing so, require greater
`visibility, security, management, and performance from their
`netWork.
`The rapid proliferation of lightWeight, portable computing
`devices and high-speed WLANs enables users to remain
`connected to various netWork resources, While roaming
`throughout a building or other physical location. The mobil
`ity afforded by WLANs has generated a lot of interest in
`applications and services that are a function of a mobile
`user’s physical location. Examples of such applications
`include: printing a document on the nearest printer, locating
`a mobile user or rogue access point, displaying a map of the
`immediate surroundings, and guiding a user inside a build
`ing. The required or desired granularity of location infor
`mation varies from one application to another. Indeed, the
`accuracy required by an application that selects the nearest
`netWork printer, or locates a rogue access point, often
`requires the ability to determine in What room a Wireless
`node is located. Accordingly, much effort has been dedicated
`to improving the accuracy of Wireless node location mecha
`nisms.
`The use of radio signals to estimate the location of a
`Wireless device or node is knoWn. For example, a Global
`Positioning System (GPS) receiver obtains location infor
`mation by triangulating its position relative to four satellites
`that transmit radio signals. The GPS receiver estimates the
`distance betWeen each satellite based on the time it takes for
`the radio signals to travel from the satellite to the receiver.
`Signal propagation time is assessed by determining the time
`shift required to synchroniZe the pseudo-random signal
`transmitted by the satellite and the signal received at the
`GPS receiver. Although triangulation only requires distance
`measurements from three points, an additional distance
`measurement from a fourth satellite is used for error cor
`rection.
`The distance betWeen a Wireless transmitter and a receiver
`can also be estimated based on the strength of the received
`signal, or more accurately the observed attenuation of the
`radio signal. Signal attenuation refers to the Weakening of a
`signal over its path of travel due to various factors like
`terrain, obstructions and environmental conditions. Gener
`ally speaking, the magnitude or poWer of a radio signal
`Weakens as it travels from its source. The attenuation
`undergone by an electromagnetic Wave in transit betWeen a
`transmitter and a receiver is referred to as path loss. Path loss
`may be due to many effects such as free-space loss, refrac
`tion, re?ection, and absorption.
`In business enterprise environments, most location-track
`ing systems are based on RF triangulation or RF ?ngerprint
`ing techniques. RF triangulation calculates a mobile user’s
`location based upon the detected signal strength of nearby
`access points (APs). It naturally assumes that signal strength
`is a factor of proximity, Which is true a majority of the time.
`HoWever, the multipath phenomenon encountered in indoor
`RF environments does present certain di?iculties in locating
`Wireless nodes, since re?ection and absorption of RF signals
`affects the correlation betWeen signal strength and proxim
`ity. RF ?ngerprinting compares a mobile station’s vieW of
`the netWork infrastructure (i.e., the strength of signals trans
`mitted by infrastructure access points) With a database that
`contains an RF physical model of the coverage area. This
`database is typically populated by either an extensive site
`survey or an RF prediction model of the coverage area. For
`example, Bahl et al., “A SoftWare System for Locating
`Mobile Users: Design, Evaluation, and Lessons,” http://
`research.microsoft.com/~bahI/Papers/Pdf/radarpd?
`
`Page 9 of 18
`
`

`

`US 7,286,835 B1
`
`20
`
`25
`
`30
`
`35
`
`3
`describes an RF location system (the RADAR system) in a
`WLAN environment, that allows a mobile station to track its
`oWn location relative to access points in a WLAN environ
`ment.
`The RADAR system relies on a so-called Radio Map,
`Which is a database of locations in a building and the signal
`strength of the beacon packets emanating from the access
`points as observed, or estimated, at those locations. For
`example, an entry in the Radio Map may look like (x, y, Z,
`ssl- (iIl .
`.
`. n)), Where (x, y, Z) are the physical coordinates
`of the location Where the signal is recorded, and ssl- is the
`signal strength of the beacon signal emanating from the ith
`access point. According to Bahl et al., Radio Maps may be
`empirically created based on heuristic evaluations of the
`signals transmitted by the infrastructure radios at various
`locations, or mathematically created using a mathematical
`model of indoor RF signal propagation. To locate the
`position of the mobile user in real-time, the mobile station
`measures the signal strength of each of access points Within
`range. It then searches a Radio Map database against the
`detected signal strengths to ?nd the location With the best
`match. Bahl et al. also describe averaging the detected signal
`strength samples, and using a tracking history-based algo
`rithm, to improve the accuracy of the location estimate. Bahl
`et al. also address ?uctuations in RF signal propagation by
`using multiple Radio Maps and choosing the Radio Map
`Which best re?ects the current RF environment. Speci?cally,
`one access point detects beacon packets from other access
`points and consults a radio map to estimate its location, and
`evaluates the estimated location With the knoWn location.
`The RADAR system chooses the Radio Map Which best
`characterizes the current RF environment, based on a sliding
`WindoW average of received signal strengths.
`While the RADAR system Works for its intended obj ec
`tive, even in this system, location accuracy decreases With
`the error in detecting the strength of RF signals. For
`example, individual differences as to hoW tWo different
`Wireless nodes detect and report signal strength can cause
`errors in location, since the Radio Maps assume no error in
`such measurements. Accordingly, tWo Wireless nodes in the
`same location that detect different signal strengths Will
`compute different estimated locations. Still further, While the
`RADAR system alloWs a mobile station to track its oWn
`location, it does not disclose a system that alloWs the WLAN
`infrastructure to track the location of Wireless nodes, such as
`45
`rogue access points. Such a system is desirable as it obviates
`the need for special client softWare to be installed on the
`mobile stations.
`This paradigm shift, hoWever, presents certain problems.
`As discussed above, the Radio Maps in the RADAR system
`are constructed from the point of vieW of a Wireless node in
`an RF environment that includes access points in knoWn
`locations. In other Words, the Radio Maps are constructed
`based on heuristic and/or mathematical evaluations of the
`propagation of signals from the access points to a Wireless
`node at a given location. Accordingly, the RADAR system
`need not assume symmetry of path loss betWeen a given
`location and the access points in the RADAR system, since
`the mobile station detects the signal strength of the access
`points and computes its oWn location. In addition, since the
`location of a Wireless node is based on path loss, the transmit
`poWer of the radio transmitters used to determine location
`must also be knoWn. In the RADAR system, this is not
`problematic, since the signals used to determine location are
`transmitted by access points, Whose transmit poWer can be
`controlled or easily determined. Estimating location based
`on signals transmitted by a Wireless node, hoWever, can be
`
`40
`
`50
`
`55
`
`60
`
`65
`
`4
`problematic, since transmit poWer can vary among Wireless
`device manufacturers, and/or may be individually con?g
`ured by the mobile user. Furthermore, the more complicated
`issue of variable transmit poWer exists not only due to the
`device or intended application itself, but also due to place
`ment of the Wireless node (e.g., a RFID tag, etc.) placed
`among or inside of other objects, or located Within or behind
`various physical barriers or obstructions.
`One approach to this problem is to assume symmetry in
`path loss betWeen a given location in an RF environment and
`the radio transceivers used to detect signals transmitted by
`the Wireless nodes. Furthermore, these approaches also
`assume a uniform transmit poWer for the Wireless nodes in
`light of the fact that legal regulations, as Well as current chip
`set technology, generally places an upper limit on transmit
`poWer. These tWo assumptions, hoWever, can signi?cantly
`impact the accuracy of locating a Wireless node. As dis
`cussed above, the RADAR system, for example, ?nds the
`location coordinates in the Radio Map that are the best ?t
`based on the detected signal strengths. That is, for each point
`in the Radio Map, the location metric computes the Euclid
`ean distance betWeen the detected signal strength values and
`the values in the Radio Map.
`The folloWing equation provides an illustrative example,
`assume for didactic purposes that a given Wireless node is
`detected by three access points. The signal strength samples
`are RSSIapl RSSIap2, and RSSIap3, While the RF coverage
`maps for each of the access points are denoted as MAPapl,
`MAPap2, MAPap3, Where the coverage maps include access
`point signal strength values detected or computed for dif
`ferent locations in a de?ned region. Again, assuming path
`loss symmetry and a uniform transmit poWer, individual
`error surfaces for each access point can be created based on
`the signal strength detected at each access point, (RSSIapl,
`etc.) and the signal strength values in the individual cover
`age maps (e.g., MAPapl, etc.). That is, the error surface is
`the difference betWeen the observed signal strength at a
`given access point less the signal strength values in the
`coverage map. The locations in this coverage map Where the
`difference is Zero are the most likely locations. In many
`situations, hoWever, the measured signal strengths, RSSIap1
`RSSIap2, and RSSIap3, do not match the signal strengths
`recorded in the coverage maps MAPapl, MAPap2, MAPap3
`at any one location. In this case, it is desirable to ?nd the
`location that is “closest” to matching RSSIap1 RSSIap2, and
`RSSIap3iin other Words, the location that minimiZes some
`function of MAPapl, MAPap2, MAPap3, RSSIap1
`RSSIap2, and RSSIap3. Bahl et al., supra, describe several
`Ways in Which this function is created, including minimum
`mean squared error, minimum distance, and minimum Man
`hattan grid distance. Furthermore, a total error surface,
`ErrSurf, can be computed based on the sum of the squares
`(to neutraliZe positive and negative differences) of the
`individual error surfaces (i.e., the difference betWeen the
`detected signal strength values and the signal strength values
`in each coverage maps), as folloWs:
`ErrSu?KRSSIapl-MAPapl)"2+(RSSIap2-MAPap2)
`"2+(RSSIap3-MAPap3)"2]/3
`
`In one implementation, the estimated Wireless node location
`is derived from the minimum or minimum of this total error
`surface.
`HoWever, a change in the Wireless node’s effective trans
`mit poWer (or, in the RADAR system, inaccuracies in
`detecting signal strength by the Wireless nodes) Will
`adversely affect the accuracy of this metric. For example, an
`N dB difference betWeen the actual and assumed transmit
`
`Page 10 of 18
`
`

`

`US 7,286,835 B1
`
`5
`power of a Wireless node Would cause a N dB change in the
`detected signal strengths. Rather than merely shifting the
`individual signal strength differences for each point in the
`individual error surfaces up by some ?xed amount, the
`individual differences betWeen the detected signal strengths
`and the signal strength values in the error surface can change
`quite dramatically. Indeed, each point in the individual error
`surfaces are shifted an amount proportional to the dB error.
`This circumstance moves some areas of the total e