(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2007/0133487 A1
`Wang et al.
`(43) Pub. Date:
`Jun. 14, 2007
`
`US 20070133487A1
`
`(54) MOBILE LOCATION METHOD FOR
`WLAN-TYPE SYSTEMS
`
`(75) Inventors: Shu-Shaw Wang, Arlington, TX (US);
`Marilynn P. Green, Pomona, NY (US)
`Correspondence Address:
`WARE FRESSOLAVANDER SLUYS &
`ADOLPHSON, LLP
`BRADFORD GREEN, BUILDING 5
`755 MAIN STREET, PO BOX 224
`MONROE, CT 06468 (US)
`
`(73) Assignee: Nokia Corporation
`(21) Appl. No.:
`11/302,311
`
`(22) Filed:
`
`Dec. 12, 2005
`
`Publication Classification
`
`(51) Int. Cl.
`(2006.01)
`H04Q 7/24
`(52) U.S. Cl. .............................................................. 370/338
`(57)
`ABSTRACT
`hod
`d uni
`Th
`id
`e present invention provides a new and unique metho
`and apparatus for providing an estimate of a mobile location
`of a wireless node, point or terminal in a wireless local area
`network (WLAN) or other suitable network, the estimate
`being based on a correlation of a radio frequency (RF) signal
`strength measurement and a grid point in a signal strength
`database or radio map. The signal strength database or radio
`map is built using a signal strength fingerprint algorithm.
`The signal strength fingerprint algorithm includes selecting
`and measuring a set of grid points in the wireless local area
`network (WLAN) or other suitable network.
`
`
`
`is zes seas assi
`
`er seas
`... .
`P
`roastate Atly
`Ap2:00F6SE6:1755
`P. onoposes 1179
`o
`Ap:00.OF63E8:59:25
`s seasessessscree
`at
`ico
`Tris roup
`
`in r
`a
`s. sass tely
`:
`Aps: oogFes;E8:51:00
`APs; oozoFS6:E8:18:F
`ar: oof 66E8:08:19: .
`
`.
`
`Page 1 of 20
`
`SAMSUNG EX-1070
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 1 of 10
`
`US 2007/0133487 A1
`
`
`
`Extended Service Set (ESS).
`
`Figure 1: 802.11 Wireless Local Area Network (WLAN)
`
`(Prior Art)
`
`Page 2 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 2 of 10
`
`US 2007/O133487 A1
`
`
`
`Figure 2b: The 3GPP Network in More Detail
`(Prior Art)
`
`Page 3 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 3 of 10
`
`US 2007/0133487 A1
`
`pisodes DB24D AP.
`AP2:00.0F6Sea-17s' -
`AP3;
`F63ES:
`risis. ses as as a cate as el-ass
`orra sp. seas ceras
`issa
`
`: .
`
`.
`
`was urge in a sa is
`reas
`
`R
`
`w
`
`
`
`
`
`
`
`aeus a susta so sea leg us is a coca
`w
`Researcassessessenes 3.
`
`>
`
`-
`
`Ri
`
`As ofsissip
`AP8: 00Fs:E8: 8F
`AP7:ogofsissios: 19
`
`- IE e
`
`- R - PRRR-FR- - - - - - - - - - - a -a -a -- - - - - - - -
`
`
`
`ng 3rd Floor Plan
`/ () . Figure 3: WLAN System Deployed on AWK Buildi
`- - - - - - -
`
`;
`
`---------
`
`:
`
`- -
`
`- - - - - - -
`
`Page 4 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 4 of 10
`
`US 2007/0133487 A1
`
`
`
`Apply linear regression method to
`estimate propagation channels
`
`
`
`
`
`Estimate propagation channels
`at each grid points
`
`
`
`Preprocessed result:
`Signal strength database
`
`
`
`
`
`Best location estimate
`
`T
`
`2
`
`Figure 4 : Flow diagram for estimating mobile location.
`
`Page 5 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 5 of 10
`
`US 2007/O133487 A1
`
`as ass as
`
`x
`
`a sea as as elee." "
`assassisterexpress
`x
`-
`al
`ch -y
`ooge:25 DB24;n AP
`s
`is
`terell- al w
`E.
`Ps :
`
`to 10s to: ''
`
`is as a seat a near
`
`"
`
`APS: oboF65.E8:51:00
`TEAPs; ooof:66:E8:18:F1.
`.
`Aroorisescs is
`
`AP
`
`
`
`eigers
`
`Figure is WLAN system. Deployed on AWK Building 3rd Floor Plan
`(with measurement points) 3.
`
`Page 6 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 6 of 10
`ŠS/ S. %2.
`
`
`
`NS
`
`US 2007/0133487 A1
`
`le
`
`50
`
`Figure 6: The Geometrical Distribution of Location Error based on 7 APs in Figure5.
`
`Page 7 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 7 of 10
`
`US 2007/0133487 A1
`
`In-building floor map
`
`
`
`
`
`
`
`C
`-----
`
`CDFS for 7 APS
`==
`
`
`
`5
`
`0.4
`
`O.3
`
`0.
`
`
`
`b
`
`C
`
`d
`
`r
`
`Key:
`a - 2 Points
`b - 4 Points
`C - 9 Points
`d - 17 Points
`e - 34 Points
`f - 69 Points
`: g - 138 Points
`
`
`
`O
`
`5
`
`10
`
`15
`2O
`25
`Location Error(meters)
`
`30
`
`35
`
`40
`
`Figure 8 t. The location error using CDF representation with 7 APs.
`
`Page 8 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 8 of 10
`
`US 2007/0133487 A1
`
`*
`
`
`
`N a CDFs for 5 APs
`
`an
`E
`5
`C)
`9.
`g2
`C
`
`0.5-
`
`b-7
`E.
`
`f
`04 el ()
`x4
`WE)
`
`b
`C)
`E
`c)
`0.3-
`l C
`
`b
`4-
`
`d
`
`C-
`
`Key:
`a - 2 Points
`b - 4 Points
`c - 9 Points
`d - 17 Points
`e - 34 Points
`if - 69 Points
`| g - 138 Points
`
`- - - -
`
`b
`
`0.2
`
`La
`0.12
`
`A-
`
`O
`O
`
`5
`
`15
`
`20
`25
`30
`10
`Location Error(meters)
`ir
`-
`Figure 9: The location error using CDF representation with 5 APs.
`
`35
`
`40
`
`45
`
`-
`
`-
`
`-
`
`-
`
`-
`
`50
`
`Page 9 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 9 of 10
`
`US 2007/0133487 A1
`
`f
`
`CDFs for 3 APs
`
`-
`
`-
`
`---
`
`t
`
`O
`
`e
`
`
`
`0.9
`
`0.8
`
`2.
`
`2/ 292 e
`2
`- -
`O
`b
`
`?
`
`b
`
`0.7
`
`s
`8 c)
`3 0.6
`f
`S.
`
`0.5
`
`o
`
`9.
`s
`3
`
`0.4
`
`O.3
`d
`0.2
`
`f
`
`b
`
`E.
`e
`0.15 g
`
`g
`
`O
`O
`
`b
`
`C
`
`4.
`C.
`
`-
`
`Ke
`y
`a - 2 Points .
`b - 4 Points
`c - 9 Points
`d - 7 Points
`e - 34 Points
`f - 69 Points
`g – 138 Points
`
`1-
`20
`
`--- t-
`30
`40
`Location Error(meters)
`
`l
`50
`
`60
`
`(or
`
`1.--
`10
`
`Figure 10: The location error using CDF representation with 3 APs.
`
`Page 10 of 20
`
`

`

`Patent Application Publication Jun. 14, 2007 Sheet 10 of 10
`
`US 2007/O133487 A1
`
`100
`
`Request
`Oil
`MOole
`Location
`
`/07
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Access Point
`(AP)
`
`Estimation
`Module
`
`Other
`Access
`Point
`Modules
`
`Figure. 11: The Access Point (AP)
`
`Page 11 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`MOBILE LOCATION METHOD FOR WLAN-TYPE
`SYSTEMS
`
`BACKGROUND OF THE INVENTION
`
`0001)
`1. Field of Invention
`0002 The present invention is related to a wireless local
`area network (WLAN) or other suitable network; and more
`particularly, to a new and unique method and apparatus for
`providing an estimate of a mobile location of a wireless
`node, point or terminal in an 802.11 WLAN.
`0003 2. Description of Related Art
`0004 FIG. 1 shows, by way of example, typical parts of
`an IEEE 802.11 WLAN system, which is known in the art
`and provides for communications between communications
`equipment such as mobile and secondary devices including
`personal digital assistants (PDAs), laptops and printers, etc.
`The WLAN system may be connected to a wire LAN system
`that allows wireless devices to access information and files
`on a file server or other suitable device or connecting to the
`Internet. The devices can communicate directly with each
`other in the absence of a base station in a so-called “ad-hoc'
`network, or they can communicate through a base station,
`called an access point (AP) in IEEE 802.11 terminology,
`with distributed services through the AP using local distrib
`uted services (DS) or wide area extended services, as shown.
`In a WLAN system, end user access devices are known as
`stations (STAs), which are transceivers (transmitters/receiv
`ers) that convert radio signals into digital signals that can be
`routed to and from communications device and connect the
`communications equipment to access points (APs) that
`receive and distribute data packets to other devices and/or
`networks. The STAS may take various forms ranging from
`wireless network interface card (NIC) adapters coupled to
`devices to integrated radio modules that are part of the
`devices, as well as an external adapter (USB), a PCMCIA
`card or a USB Dongle (self contained), which are all known
`in the art.
`0005 FIGS. 2a and 2b show diagrams of the Universal
`Mobile Telecommunications System (UMTS) packet net
`work architecture, which is also known in the art. In FIG. 2a,
`the UMTS packet network architecture includes the major
`architectural elements of user equipment (UE), UMTS Ter
`restrial Radio Access Network (UTRAN), and core network
`(CN). The UE is interfaced to the UTRAN over a radio (Uu)
`interface, while the UTRAN interfaces to the core network
`(CN) overa (wired) Iu interface. FIG.2b shows some further
`details of the architecture, particularly the UTRAN, which
`includes multiple Radio Network Subsystems (RNSs), each
`of which contains at least one Radio Network Controller
`(RNC). In operation, each RNC may be connected to
`multiple Node Bs which are the UMTS counterparts to GSM
`base stations. Each Node B may be in radio contact with
`multiple UEs via the radio interface (Uu) shown in FIG.2a.
`A given UE may be in radio contact with multiple Node Bs
`even if one or more of the Node Bs are connected to different
`RNCs. For instance, a UE1 in FIG. 2b may be in radio
`contact with Node B2 of RNS1 and Node B3 of RNS2 where
`Node B2 and Node B3 are neighboring Node Bs. The RNCs
`of different RNSs may be connected by an Iur interface
`which allows mobile UEs to stay in contact with both RNCs
`while traversing from a cell belonging to a Node B of one
`RNC to a cell belonging to a Node B of another RNC. The
`
`convergence of the IEEE 802.11 WLAN system in FIG. 1
`and the (UMTS) packet network architecture in FIGS. 2a
`and 2b has resulted in STAs taking the form of UEs, such as
`mobile phones or mobile terminals. The interworking of the
`WLAN (IEEE 802.11) shown in FIG. 1 with such other
`technologies (e.g. 3GPP, 3GPP2 or 802.16) such as that
`shown in FIGS. 2a and 2b is being defined at present in
`protocol specifications for 3GPP and 3GPP2.
`0006. The IEEE 802.11 WLAN system in FIG. 1 and the
`(UMTS) packet network architecture in FIGS. 2a and 2b,
`and the convergence thereof, must meet certain require
`ments, including those set forth by the Federal Communi
`cations Commission (FCC). In particular, the FCC has
`recently defined a set of accuracy requirements for E-911
`calls, which are collectively known in the industry as the
`E-911 Phase II mandate. The mandate states that handset
`based solutions should locate the E-911 caller to within 50
`meters for 67% of the calls and to within 150 meters for 95%
`of the calls. The new ALI (Automatic Location Identifica
`tion)-capable handsets must fulfill the FCC's E-911 Phase II
`location accuracy requirement.
`0007. Several location systems have been designed for
`wide-area cellular systems in the art. Two of the most
`prevalent technologies are the AFLT (Advanced Forward
`Link Trilateration) and AGPS (Assisted GPS) methods.
`While these systems have been found to be promising for
`outdoor environments, their effectiveness in indoor environ
`ments is limited by the severe indoor multipath effect and
`in-building penetration loss, which, in particular, limits the
`reception of GPS transmissions. There are also some indoor
`location systems that rely on specialized hardware solutions,
`such as IR (infrared) and RFID-based technologies. How
`ever, these indoor location systems typically Suffer from
`limited range and they also require extensive deployment of
`an infrastructure whose sole purpose is to locate people.
`0008. The present invention provides a new and effective
`approach for meeting the requirements of the E-911 Phase II
`mandate as well as the Voice/data communications.
`
`SUMMARY OF THE INVENTION
`0009. In its broadest sense, the present invention provides
`a new and unique method and apparatus for providing an
`estimate of a mobile location of a wireless node, point or
`terminal in a wireless local area network (WLAN) or other
`suitable network, wherein the estimate is based on a corre
`lation of a radio frequency (RF) signal strength measure
`ment and a grid point in a signal strength database or radio
`map.
`0010. The signal strength database or radio map is built
`using a signal strength fingerprint algorithm, which includes
`steps of selecting and measuring a set of grid points in the
`wireless local area network (WLAN) or other suitable
`network. The signal fingerprint algorithm includes using
`linear regression parameters to estimate mobile received
`signal strengths at each assigned grid point, as well as
`recording grid positions and signal strength measurements.
`0011 The signal strength fingerprint algorithm may
`include one or more of the following steps: placing access
`points (APs) in the wireless local area network (WLAN) or
`other Suitable network and recording their coordinates;
`taking signal strengths measurements in areas of interest in
`
`Page 12 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`the wireless local area network (WLAN) or other suitable
`network; applying a linear regression method to estimate
`propagation channels; estimating propagation channels at
`each grid point; and/or processing the results so as to form
`the signal strength database or radio map.
`0012. The data structure entry for each grid point is
`defined as
`
`R
`-
`
`P(x, yi, (i)
`SS, ...i
`
`where i represents an identification number (ID) for each
`grid point, R is the estimated received information at the i-th
`grid point, P(x, y, z) is the physical location of the i-th grid
`point, and SS, is the average received signal strengths from
`the j-th AP's transmission at the i-th grid point.
`0013 In operation, in response to a request from the
`wireless node, point or terminal, a gradient search is used to
`determine the estimate.
`0014. The grid point may include an access point (AP) in
`the wireless local area network (WLAN) or other suitable
`network.
`0.015 The wireless node, point or terminal may include a
`station (STA), as well as user equipment (UE) such as a
`mobile terminal, phone, laptop computer, personal digital
`assistant, etc.
`0016. The steps of method may be implemented via a
`computer program running in a processor, controller or other
`Suitable module in one or more network nodes, points,
`terminals or elements in the wireless local area network
`(WLAN) or other suitable network.
`0017. The present invention also includes apparatus that
`may take the form of a wireless local area network (WLAN)
`or other Suitable network having a network node, point or
`element with a module for providing an estimate of a mobile
`location of a wireless node, point or terminal therein,
`wherein the estimate is based on a correlation of a radio
`frequency (RF) signal strength measurement and a grid point
`in a signal strength database or radio map, as well as a
`network node, point or element for operating in Such a
`wireless local area network (WLAN) or other suitable
`network, where the network node, point or element has a
`module for providing Such an estimate of the mobile loca
`tion of the wireless node, point or terminal in the wireless
`local area network (WLAN) or other suitable network,
`consistent with that described herein.
`0018. The present invention also includes a computer
`program product with a program code, which program code
`is stored on a machine readable carrier, for carrying out the
`steps of a method comprising one or more steps for provid
`ing an estimate of a mobile location of a wireless node, point
`or terminal in a wireless local area network (WLAN) or
`other suitable network, the estimate being based on a cor
`relation of a radio frequency (RF) signal strength measure
`ment and a grid point in a signal strength database or radio
`map, when the computer program is run in a module of
`either a node, point or terminal. Such as an Access Point
`(AP) or other suitable grid point, in the wireless local area
`network (WLAN) or other suitable network.
`
`0019. The present invention also includes a method for
`building a database using a signal strength fingerprint algo
`rithm for use in providing an estimate of a mobile location
`of a wireless node, point or terminal in a wireless local area
`network (WLAN) or other suitable network arranged in a
`geographic location, including steps for placing access
`points (APs) or other suitable grid points in the wireless
`local area network (WLAN) or other suitable network and
`recording their coordinates in the geographic location; tak
`ing signal strengths measurements in areas of interest in the
`wireless local area network (WLAN) or other suitable
`network; applying a linear regression method to estimate
`propagation channels; estimating propagation channels at
`each access or other Suitable grid point; and processing the
`results so as to form the signal strength database or radio
`map.
`0020. In effect, the present invention provides a design of
`a WLAN system architecture that is simpler, faster, more
`robust, and more relatively accurate mobile-location-esti
`mate than the existing Solutions. The new location scheme is
`also related to the use of signal strength fingerprinting
`concept for the localized wireless area. According to the
`present invention, the key concept of the fingerprinting
`algorithm is to build a signal strength database (or “radio
`map’) at each grid point in the area of interest, then to use
`this radio map to correlate an RF signal strength measure
`ment to one of the grid points.
`0021. In addition, the present invention provides a soft
`ware-only location solution that uses “off-the-shelf. WLAN
`data transmission equipment. Since the presence of multi
`path makes the time-of-arrival technique unsuitable for
`indoor applications, an RF signal strength pattern-matching
`technique (or RF fingerprinting method) is designed to
`locate the mobile user. The present invention provides a
`method that (1) significantly reduces the number of signal
`strength measurements to less than 10 test points for a
`building area of 40 meters by 50 meters, and (2) provides
`fast estimates of the mobile's coordinates using a gradient
`search method. The results of experiments show that the
`mobile location error of our invention method can be less
`than 10 meters of 67%-tier with three access points in a
`building area of 40-meters by 50-meters. Accordingly, this
`method provides a simpler, faster, more robust, and more
`accurate mobile-location-estimate than the existing solu
`tions.
`
`BRIEF DESCRIPTION OF THE DRAWING
`0022. The drawing includes the following Figures, which
`are not necessarily drawn to scale:
`0023 FIG. 1 shows typical parts of an IEEE 802.11
`WLAN system, which is known in the art.
`0024 FIGS. 2a and 2b show diagrams of the Universal
`Mobile Telecommunications System (UMTS) packet net
`work architecture, which is also known in the art.
`0.025
`FIG. 3 is a floor plan of the third floor of the
`Atwater Kent Engineering Building at the Worcester Poly
`technic Institute with a WLAN system according to the
`present invention.
`0026 FIG. 4 shows a flow diagram for estimating mobile
`location according to the present invention.
`
`Page 13 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`0027 FIG. 5 is the floor plan of the third floor of the
`Atwater Kent Engineering Building at the Worcester Poly
`technic Institute shown in FIG. 3, having points 1-138 for
`modeling the method and apparatus according to the present
`invention.
`0028 FIG. 6 shows a geometrical distribution of location
`error based on 7 APs shown in FIG. 5.
`0029 FIG. 7 shows an example of in-building floor map
`top view for grid-points design according to the present
`invention.
`0030 FIG. 8 shows the location error using a Cumulative
`Distribution Function (CDF) representation with 7 APs
`according to the present invention.
`0031 FIG. 9 shows the location error using a CDF
`representation with 5 APs according to the present inven
`tion.
`0032 FIG. 10 shows the location error using a CDF
`representation with 3 APs according to the present inven
`tion.
`0033 FIG. 11 shows an access point (AP) or other
`Suitable network node, point or element having an estima
`tion module according to the present invention.
`
`BEST MODE OF THE INVENTION
`0034. The present invention provides a new and unique
`method and apparatus for providing an estimate of a mobile
`location of a wireless node, point or terminal in a wireless
`local area network (WLAN) or other suitable network that
`includes, for example, access points AP01, AP02, AP03,
`AP04, AP05, AP06, AP07 on a floor generally indicated as
`10 of a building or other suitable geographic location Such
`as that shown in FIG. 3 (which is a floor plan of the third
`floor of the Atwater Kent Engineering Building at the
`Worcester Polytechnic Institute). According to the present
`invention, the estimate of the mobile location of the wireless
`node, point or terminal is based on a correlation of a radio
`frequency (RF) signal strength measurement and a grid point
`in a signal strength database or radio map, consistent with
`that shown and described herein.
`0035 FIG.3 also shows a mobile phone or terminal, for
`example, at the mobile location marked by an “X” and
`labelled 12 in Room 113. In operation, when the user of the
`mobile phone or terminal calls “911, the wireless local area
`network (WLAN) or other suitable network has a network
`node, point or element having a module for providing the
`mobile phone or terminal, or the local police, or other
`governmental or commercial agency, or other Suitable party
`requesting the same, with the estimate of the mobile location
`of the mobile phone or terminal, including but not limited to
`for the case shown in FIG. 3 the address of the building, the
`floor and the room, etc., so that help may be sent to that
`location as soon as possible. The scope of the invention is
`not intended to be limited in any way to the type or kind of
`information that forms part of the estimation, or to who the
`information is provided, or to when the information is
`provided, or by how the information is provided, etc.
`0036). According to the present invention, the signal
`strength database or radio map is built using a signal strength
`fingerprint algorithm, which includes steps of selecting and
`measuring a set of grid points in the WLAN or other suitable
`
`network as described below. The signal fingerprint algorithm
`includes using linear regression parameters to estimate
`mobile received signal strengths at each assigned grid point,
`as well as recording grid positions and signal strength
`measurementS.
`0037. By way of example, FIG. 4 shows a flow diagram
`generally indicated as 20 for estimating mobile locations,
`having steps that form part of the signal strength fingerprint
`algorithm, including a step 22 for placing access points
`(APs) in the WLAN or other suitable network and recording
`their coordinates; a step 24 for taking signal strengths
`measurements in areas of interest in the wireless local area
`network (WLAN) or other suitable network; a step 26
`applying a linear regression method to estimate propagation
`channels; a step 28 estimating propagation channels at each
`grid point and a step 30 for processing the results so as to
`form the signal strength database or radio map. These steps
`are described in more detail in relation to FIGS. 5-10 below.
`0038. In response to a mobile user request of its location
`indicated in step 32, or similarly in response to a request
`from any authorized party, including the local police, other
`governmental or commercial agency, or other Suitable party
`requesting the same, a gradient search of the mobile's
`location is performed in step 34 in order to determine the
`estimate of the mobile location of the wireless node, point or
`terminal based on the correlation of the radio frequency (RF)
`signal strength measurement and the grid point in the signal
`strength database or radio map. The search is performed
`until a best location estimate is determined in step 36.
`
`Measurement Data for Location Error Analysis
`0039. In order to appreciate the method for creating the
`signal strength or radio map database, important observa
`tions/results that have been deduced from real measurements
`are set forth below.
`0040 First, two sets of measurement results were ana
`lyzed that were taken on the third floor of the Atwater Kent
`Engineering Building at the Worcester Polytechnic Institute
`seen the floorplan seen in FIG. 3. The seven AP signals were
`detected and their location coordinates (x, y, z) were
`recorded. As best shown in FIG. 5, receiver signal strength
`were collected with respect to all seven APs at 138 different
`measurement points (i.e., P1, P2, P3, . . . . P138). Each
`measurement point (e.g., at point P1) collects 100 instanta
`neous signal strengths (or samples) from each of APs (i.e.,
`AP1, AP2, ..., AP7). So that, each measurement point can
`be described by a histogram distribution (or a CDF curve) as
`well as an average received signal strength that is the mean
`value of the 100 signal strength samples.
`0041) Second, by applying linear regression to the two
`sets of measurement data (i.e., Campaign 1 data set and
`Campaign 2 data set are measured on different days and at
`different times-of-day) based on the floor plan of FIG. 5, one
`can find seven different linear regression curves to represent
`the path loss for seven different APs. This set the framework
`for the indoor geolocation method according to the present
`invention that is based on average signal strength modeling.
`A linear regression method was applied as the model for
`signal strength and this model has been applied to the two
`sets of measurement data (i.e., Campaign 1 data and Cam
`paign 2 data). The statistical model for signal propagation
`developed here is used to assess the geolocation error that is
`
`Page 14 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`incurred when using signal strength-based methods. The
`location error is a function of the position of a mobile client
`and the set of AP positions. This error analysis provides the
`error bound which is used to determine optimal locations of
`the set of APs and evaluate the range of location error
`geometrically. The detailed error bound analysis is as fol
`lowing. It is important to note that linear regression methods
`and techniques are known in the art, and the Scope of the
`invention is not intended to be limited to any particular type
`or kind thereof either now known or later developed in the
`future.
`
`Linear Regression Analysis
`0042 An empirical signal propagation model of the
`received signal is given by:
`
`where P(r) is the received power at a mobile device whose
`distance from a given AP transmitter is r, and P(r) is the
`signal power at the reference point, ro. The parameter C. is
`the path loss exponent value.
`0043) One can estimate the unknown parameters P(ro)
`and d. by applying linear regression analysis and using the
`minimum least squares estimation method:
`0044) Let us define:
`
`where p=-10 log(r/ro).
`0045. The cost function is defined as:
`
`M
`12
`Pw(r)- Pw(r)
`
`(3)
`
`y
`y
`
`=XPi(r)-2X Pw(r)(Pro) + 6p.)+X (Pro) + ap)
`
`i
`
`=
`
`i
`
`=
`
`i
`
`
`
`= i
`
`0046 where m is the number of samples. Taking the
`derivative of the cost function with respect to the path loss
`exponent and the received power, and equating it Zero, we
`derive the following two relations:
`
`0047 Combining these two equations, we obtain the
`following four (equivalent) feasible solutions:
`
`(6)
`
`(7)
`
`and P(ro)dBm) = PwdBm – 6p
`1
`where O = iX, P: and PwdBm
`
`i=l
`
`Multiple Regression Analysis
`0048 Multiple regression is an extension of linear regres
`sion analysis. It takes into account the effects of more than
`one predictor variable on the dependent variable. We can
`determine the two factors (P(ro), C.) simultaneously by using
`one predictor variable (the distancer). The multiple regres
`sion model is:
`
`P = GB
`where
`
`P(r)
`P(r)
`P= .
`
`P(r)
`1 - 10log(r) fro)
`1 - 10log(r2 fro)
`G = .
`
`1 - 10log(r. fro)
`
`Pro)
`
`and B
`
`(8)
`
`(9)
`
`(10)
`
`I
`
`i
`
`a = 0 = 2, Pw(r)-(Pro) + 6p.)p;
`
`r
`
`r
`
`and
`
`I
`
`i
`r
`a Pro)
`( X. w(r)-(Pro) + 6p.)
`= 0 = (-2) XP (r) - (Pro) + 6 p.
`
`(4)
`
`(5)
`
`0049. The least-square estimate of the unknown param
`eter vector, f, is given by:
`
`The standard deviation of the predicted signal strength is
`given by
`
`Page 15 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`O =
`
`1
`
`r
`
`(P - B G). (P - BG)
`
`M A
`
`0050. One can use this result on the standard deviation to
`estimate the location error, as illustrated in the next section.
`
`Estimation of Location Error
`0051 One can determine the relation between the loca
`tion error and error in signal strength prediction by applying
`a differential operation from Equation (5) with respect to the
`X and y coordinates.
`
`16
`(16)
`
`(17)
`
`(18)
`
`10a; x - x;
`dP(x, y) = - ;
`Wi
`dy
`In 10
`r?
`--
`
`-y;
`y sidy
`r?
`
`where i=1, 2, . . . , N.
`Equation (20) can be written in matrix form as:
`
`P= H .
`where
`
`*
`
`dP(r)
`dP(r)
`
`P =
`
`dP(ry)
`10a1 x - x1
`In 10 ri
`10a2 x - x2
`in 10
`
`|
`
`10a w x - ww
`In 10
`re.
`dy
`dr= dy
`
`10a1y-y1
`In 10 ri
`10a2 y - y2
`in10
`3,
`
`10a w y - yN
`In 10 ri
`
`and C., C. . . . . CN in the H matrix are based on the linear
`regression calculations based on measurements made from
`AP1, AP2, . . . , APN.
`
`By considering the least square estimation, one can relate the
`location error to an error in power estimation, dP.
`
`di = (HH). H'dP.
`Oi
`()
`()
`Since Cov(dP, dP,) = 0 or
`0
`0
`0 O,
`
`Cov(di) = E{di. di}
`= E{(H'H) H'dP. dP' HI(H'H)
`Oi
`()
`()
`= (HH) 'H'. O ori
`()
`O
`O O2 p3
`
`- H(HH).
`
`(19)
`
`(20)
`
`The standard deviation of location error is finally estimated
`aS
`
`(21)
`o-V o, ho?
`0052 By using Equations (20) and (21), the resulting
`Geometrical Distribution of Location Error with 7 APs
`based on the FIG. 5 floor plan has been shown in FIG. 6.
`FIG. 6 is the difference of the location error between
`Campaign 1 data set and Campaign 2 data set. The result
`shows that the maximum location error is close to 1 meter.
`0053. In summary, the location error estimated using the
`average signal strength scheme is almost no different when
`comparing results from Campaign 1 data to Campaign 2
`data. This implies that this average signal strength method is
`a robust method to estimate the mobile. If one uses the
`histogram distribution (or, using CDF curve) instead of
`using average signal strength method to estimate location
`error, than it is no longer a time-invariant system and the
`CDF distribution fingerprinting method fails to estimate the
`mobile location. However, the average signal strength fin
`gerprinting method may be used and it provides simple and
`robust mobile location estimation.
`
`CDF Location Error Representation
`0054 First, consistent with the present invention, in the
`experiment 7 access points (APs) were arranged in a WLAN
`system as in FIG. 5. 138 signal strength measurement points
`were used to determine the linear regression curve with
`respect to each different AP propagation channel. These
`linear regression curves were used to estimate (or predict)
`mobile received signal strengths at each assigned grid point
`(e.g., the grid point is distributed in every 2-meter by
`2-meter on the area of interest and the concept is presented
`in FIG. 7. Since the signals received at each point (P1, P2,
`.
`.
`.
`. P138) are measured and each point coordinates is
`known, one can use these points as test points to calculate
`the CDF location error curve. For example, one can take P1
`as a test point and use gradient search method to find the
`minimum signal strengths by moving the mobile location.
`The location error is a CDF curve based on the 138 test
`points. In FIG. 8-10, one can uniformly select 138, 69. 34.
`17, 9, 4, 2 signal strength measurement points to determine
`the linear regress curve. It is noteworthy that the location
`error CDF curves are similar by using 138 points or 9 points
`to calculate linear regression for even 3 APs seen in FIG. 10.
`
`Page 16 of 20
`
`

`

`US 2007/O 133487 A1
`
`Jun. 14, 2007
`
`These results lead to the conclusion that the method accord
`ing to the present invention is an effective mobile location
`method. Moreover, CDF methods and techniques are known
`in the art, and the scope of the invention is not intended to
`be limited to any particular type or kind thereof either now
`known or later developed in the future.
`
`Estimated Data Base Creation
`0.055 Due to the measurement data analysis above, one
`only needs to uniformly select and measure less than 10
`points in a typical 40-meter by 50-meter building. If the
`building area is larger than this typical 40 m by 50 m
`building, then one may need to add several measurement
`points. One can just use these measurement points (i.e., less
`than 10 measurement points) to calculate the linear regres
`sion parameters (no non-linear regression calculation is
`needed). Then, one can use these linear regression param
`eters to estimate (or predict) mobile received signal
`strengths at each assigned grid point which is distributed in
`every 2-meter by 2-meter square on the area of interest.
`