United States Patent (19)
`Smith
`
`54 METHOD FOR LOCATING AMOBILE
`STATION
`
`75 Inventor: Adrian David Smith, Kirkland, Wash.
`
`*
`
`Notice:
`
`73 ASSignee: (IST Wireless Svcs. Inc., Redmond,
`S.
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent term provisions of 35 U.S.C.
`154(a)(2).
`
`USOO6167274A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,167,274
`*Dec. 26, 2000
`
`5,561,840 10/1996 Alvesalo et al..
`5,570,412 10/1996 LeBlanc.
`5,594,425
`1/1997 Ladner et al..
`5,613,205 3/1997 Dufour ................................... 455/33.2
`5,678,194 10/1997 Grube et al. ............................ 455/456
`5,844,522 12/1998 Sheffer et al. .......................... 342/457
`5,854,981 12/1998 Wallstedt et al. ....................... 455/439
`5,859,612
`1/1999 Gillhousen .............................. 342/457
`5,873,040 2/1999 Dunn et al. .
`455/456
`5,913,170 6/1999 Worthham ............................... 455/457
`5,946,611 8/1999 Dennison et al. ...................... 455/404
`5,960,341 9/1999 LeBlanc et al. ........................ 455/426
`5,970,414 10/1999 Bi et al. ..........
`455/456
`5.991,758 12/1999 Ellard .......................................... 707/6
`FOREIGN PATENT DOCUMENTS
`
`21 Appl. No.: 08/868,402
`2295591 8/1997 Canada.
`22 Filed:
`Jun. 3, 1997
`Primary Examiner Edward F. Urban
`
`51 Int. Cl." - H04Q 7/20 Assistant Examiner-Congvan Tran
`52 U.S. Cl. ...................... 455/456; 455/457; 342/357.01
`58 Field of Search ..................................... 455/404, 456,
`455/457, 517,521,524, 426; 342/357.01,
`457, 357.13
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,055,851 10/1991. Sheffer.
`5,208,756
`5/1993 Song ....................................... 364/449
`5,218,367 6/1993 Sheffer et al..
`5,327,144 7/1994 Stilp et al..
`5,388,147 2/1995 Grimes.
`5,394,158 2/1995 Chia
`5,396,540 3/1995 Gooch ....................................... 379/59
`5,508,708 4/1996 Ghosh et al..
`5,542,100 7/1996 Hatakeyama ........................... 455/56.1
`
`ABSTRACT
`57
`A method provides for the detection of the geographic
`location of a mobile station within a mobile network. The
`mobile Station detects signal characteristics for Signals gen
`erated by neighboring cells to create a report of Signal
`characteristics corresponding tO the location at which the
`mobile Station resides. This report is then compared against
`the database of Signal Signatures identifying geographic
`locations within the cell in which the mobile station is
`known to be positioned. The Signal Signatures are then used
`to detect either an exact match or an approximate match to
`give position information of the mobile station within the
`cell.
`
`6 Claims, 3 Drawing Sheets
`
`301
`
`302
`
`303
`
`304
`
`305
`
`
`
`
`
`
`
`
`
`SEND LIST OF NEIGHBOR
`CELL FREQUENCES
`
`RECEIVE REPORT OF
`SIGNAL PARAMETER(S)
`
`COMPARE REPORT TO
`POSITION LOCATION
`DATABASE
`
`RETRIEVE SIGNAL
`SIGNATURE FOR
`N CLOSEST MATCHES
`
`OUTPUT GPS COORDINATES
`CORRESPONDING TO
`MATCHING LOCATION
`
`EXTRAPOLATE LOCATION
`FROM LOCATION OF
`N CLOSEST MATCHES
`
`OUTPUT APPROXIMATED
`LOCATION
`
`
`
`
`
`306
`
`
`
`307
`
`
`
`308
`
`Page 1 of 7
`
`SAMSUNG EX-1026
`
`

`

`U.S. Patent
`
`Dec. 26, 2000
`
`Sheet 1 of 3
`
`6,167,274
`
`- - - - - - -
`
`- -
`
`- x
`
`x
`
`Y
`
`W
`
`1
`
`W
`
`a
`
`Y
`
`A.
`
`A.
`f
`
`f
`
`w
`W.
`w
`V
`
`w w
`W
`
`F1
`
`10
`
`F2
`
`v y
`Y.
`
`\
`
`w
`N
`
`Y
`
`w
`w
`
`w
`W
`w
`W
`w
`
`^
`
`a
`
`11
`
`1
`
`a
`
`a
`
`?
`
`f
`f
`
`FIG. 2
`
`
`
`FREQUENCY
`
`SIGNAL
`STRENGTH
`
`F
`F2
`F3
`
`Page 2 of 7
`
`

`

`U.S. Patent
`
`Dec. 26, 2000
`
`Sheet 2 of 3
`
`6,167,274
`
`FIC. 3
`
`
`
`30
`
`302
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SEND LIST OF NEIGHBOR
`CELL FREQUENCIES
`
`
`
`RECEIVE REPORT OF
`SIGNAL PARAMETER(S)
`
`COMPARE REPORT TO
`POSITION LOCATION
`DATABASE
`
`
`
`
`
`306
`
`RETRIEVE SIGNAL
`SIGNATURE FOR
`N CLOSEST MATCHES
`
`
`
`
`
`OUTPUT GPS COORDINATES
`CORRESPONDING TO
`MATCHING LOCATION
`
`305
`
`EXTRAPOLATE LOCATION
`FROM LOCATION OF
`N CLOSEST MATCHES
`
`OUTPUT APPROXIMATED
`LOCATION
`
`307
`
`
`
`308
`
`FIC. 4
`
`41
`
`42
`
`43
`
`44
`
`45
`
`46
`
`Page 3 of 7
`
`

`

`U.S. Patent
`
`Dec. 26, 2000
`
`Sheet 3 of 3
`
`6,167,274
`
`FIC. 6
`
`LONGITUDE/LATITUDE | NEIGHBORING CELL SIGNAL CHARACTERISTIC
`
`
`
`500
`
`50
`
`FIG. 6
`
`
`
`610
`
`601
`
`Page 4 of 7
`
`

`

`1
`METHOD FOR LOCATING AMOBILE
`STATION
`
`6,167,274
`
`5
`
`15
`
`25
`
`BACKGROUND OF THE INVENTION
`The present invention relates to a method for locating a
`mobile Station. More particularly, the present invention
`relates to detecting the position of a mobile Station in a cell
`area based on certain received signal characteristics.
`In emergency situations it is critical to know the location
`of the emergency and where help needs to be sent. This is
`easily done with communication Systems that are wired. For
`instance, it is well known that when a wire line Subscriber
`activates an emergency code Such as "911" facilities can
`determine the location of the user So that assistance can be
`Sent to that location.
`It is equally important to provide emergency assistance to
`those who may not have access to a wire line connection,
`Such as a perSon in a vehicle. Such perSons may utilize
`mobile communication devices Such as mobile cellular
`phones. However, it is more difficult to provide Such assis
`tance just by the nature of the communication instrument, in
`that the instrument can be moved to many different loca
`tions. Thus, it would be desirable to provide a method by
`which the location of a mobile station could be determined
`quickly and Simply.
`A number of prior Systems for mobile System location
`identification have detected Signal Strengths to perform
`triangulation. This is a complex Solution which requires real
`time calculations related to Signal Strength measurements. A
`more Simple Solution to the problem is desirable.
`SUMMARY OF THE INVENTION
`The present invention provides a method for locating
`mobile Stations which uses signal Strength information in a
`new manner. In particular, in an embodiment of the present
`invention a mobile Station is advised of the channel frequen
`cies of the neighboring cells. The Station then measures
`Signal parameters with respect to these neighboring cell
`frequencies. The compiled signal measurements are trans
`mitted back to a central processing Station via the mobile
`communications network. A database at that central proceSS
`ing Station Stores signal measurements corresponding to
`locations within the cell in which the mobile station is
`located. The central processor Searches the database for a
`45
`Signal measurement that matches the received signal mea
`Surements. If a match is found then the geographic location
`corresponding to the Signal measurement is Selected as the
`geographic location of the mobile Station. If, however, the
`central processor does not detect an exact match for the
`Signal Signature then the processor may select the closest
`matching Signal Signature and use the corresponding loca
`tion as being representative of the location of the mobile
`Station. Alternatively the processor could calculate an
`approximate location based on location information corre
`sponding to the N closest signal measurements.
`The present invention reduces the location operation to a
`Simple task of Searching a database for matching informa
`tion. Such a technique could also be used to enhance the
`accuracy of a triangulation technique.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 illustrates an example of a mobile cellular con
`figuration in which the present invention may be employed.
`FIG. 2 illustrates an example of a table of information
`which can be utilized in an embodiment of the present
`invention.
`
`35
`
`40
`
`50
`
`55
`
`60
`
`65
`
`2
`FIG. 3 illustrates a flow chart of a method in accordance
`with an embodiment of the present invention.
`FIG. 4 illustrates a Sample map of a region within a cell
`for purposes of explaining how to create a database to be
`used in conjunction with the present invention.
`FIG. 5 illustrates an example of a database entry in an
`embodiment of the present invention.
`FIG. 6 illustrates, in block diagram form, an example of
`a System employing the present invention.
`
`DETAILED DESCRIPTION
`FIG. 1 illustrates in schematic form the layout of a cellular
`network in which the present invention can be employed.
`Three cells are shown: cell 1, cell 2, and cell 3. Each cell has
`its own set of channels, for example a control channel and
`Voice channels, for providing over-the-air communications
`with mobile Stations. In the example shown, cell 1 has a
`channel having frequency f1, cell 2 has a channel with
`frequency f2 and cell 3 has a channel with frequency f3.
`Each cell may have multiple frequencies, but only one
`frequency is shown here for ease of description. In the
`example, a handheld device 10 is shown located within cell
`1.
`The present invention provides a method for locating the
`mobile Station 10 at Some geographic position within the
`geographic Serving area of the cellular System of cell 1.
`It is known in existing mobile Systems to advise the
`handheld device 10, while it is in cell 1, of the frequencies
`used by the cells neighboring cell 1, for example, frequency
`f2 for cell 2 and frequency f3 for cell 3. This information is
`useful in at least two situations.
`First, the mobile station may be registered in the mobile
`network, but may not presently be involved in a
`communication, that is, it is in an idle mode. In that mode
`the mobile Selects a control channel based on certain Signal
`criteria. Under those circumstances while the mobile is
`being moved, it is possible that a time will come when the
`mobile is located Such that it is more optimal to Select the
`control channel of either cell 2 or cell 3 rather than the
`control channel of cell 1. This is known as a re-Selection
`process. The mobile makes this determination by periodi
`cally measuring the Signal Strengths of the control channels
`of the neighboring cells. An algorithm is performed using
`those measurements and the mobile then determines whether
`to re-Select the frequency of one of the neighboring cells.
`This information can be sent back to the System to aid in
`channel allocation. This is referred to as Mobile Assisted
`Channel Allocation (MACA).
`A Second Situation in which the Signal characteristics of
`the neighboring cell channels are useful relates to those
`occasions when a mobile Station is involved in a commu
`nication while moving through a given cell and reaches the
`outer perimeter of that cell and needs to be handed-off to a
`neighboring cell. This is referred to as Mobile Assisted Hand
`Off (MAHO). In this situation, the mobile station detects
`Signal characteristics of the neighboring cells and transmits
`that characteristic information back to the cellular System So
`that the system can coordinate a hand-off of the mobile
`Station from one cell to another as it traverses cells.
`These two operations MACA and MAHO are described in
`detail in the IS-136 protocol specifications. (TIA/EIA/IS
`136.1-A October 1996).
`The present invention takes advantage of these known
`operations that detect the Signal Strength of Signals from
`neighboring cells. An embodiment of the present invention
`
`Page 5 of 7
`
`

`

`3
`provides that the mobile station is advised of the channel
`frequencies of the neighboring cells and is requested to
`perform a Signal measurement that detects certain parameter
`(S) that characterize the signals from the neighboring cells.
`An example of a table correlating the neighboring cell
`Signals (f1, f2, f3) to a signal parameter Such as signal
`strength is shown in FIG. 2. The present invention relies on
`the concept that each geographic location within a given cell
`Site has its own “signal Signature'. By this it is meant that
`given a Sufficiently large number of neighboring cell Signals,
`the detected Set of parameters of those Signals at a given
`location will be unique.
`A database for use in the location operation can be
`generated with this idea in mind. FIG. 4 illustrates a Sample
`cell area where there are six roads or routes shown (41 to 46)
`that are normally traversed by mobile stations. Each “X”
`marks a geographic location on one of the roads at which
`measurements can be made with respect to the Signals
`coming from neighboring cells. A network operator could
`collect this data during a normal course of drive testing
`along these roads within a cell. This would mean placing a
`call on a phone connected to a personal computer (PC)
`which gathers mobile assisted hand-off or mobile assisted
`channel allocation information. The computer would also
`have a global position system (GPS) card to collect latitude
`and longitude information to geographically fix the infor
`mation. The collection equipment could be automated and
`placed in taxi cabs, delivery vehicles, buses, or other
`vehicles which commonly traverse the cell.
`To improve the Signature which is associated with each
`geographic location, the data could be collected and aver
`aged So that real time variations in the Signal parameters
`Such as those owing to RF conditions, fading, tree leaves,
`trucks, buses, etc., would be removed from the data. It may
`be further beneficial to create a rolling time average to take
`into account changes in the landscape, Such as new building
`construction, which could effect the Signal parameters. In
`collecting information this way a database will be created
`that contains the latitude, longitude, frequency and Signal
`parameters of all of the test positions in the cell. Of course,
`this proceSS could then be repeated for each of the cells
`throughout the System. The result is that the database
`creates, for each cell, a Set of Signal signatures which
`Specifically identify geographic locations within the cell. It
`may be difficult to physically detect a Signal Signature for
`every location within a cell. In that circumstance the Signal
`Signature for particular locations may be detected and Sig
`natures for other locations may be extrapolated from the
`detected information.
`In the embodiment which is presently described the signal
`parameter which is measured by the mobile Station is the
`Signal Strength of the neighboring cell Site Signals. However,
`it is envisioned that other Signal parameters which may vary
`with location or distance from a given transmitter and which
`can be used to create a Substantially unique signal Signature
`for a geographic location could be used either in conjunction
`with Signal Strength or as alternatives to Signal Strength.
`FIG. 3 illustrates a flow chart for one embodiment of a
`method for detecting mobile Station location in accordance
`with the present invention. The method could be executed
`upon receipt of a distreSS or emergency call. Alternatively,
`the method could be executed in response to a location
`request from the mobile station. The method also has
`applicability in monitoring or tracking the location of a fleet
`of vehicles.
`First, a list of neighbor cell frequencies is sent to the
`mobile station, step 301. The central processor then receives
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,167,274
`
`4
`a report of Signal parameters for the cell frequencies from
`the mobile station, step 302. These parameters could include
`Such signal characteristics as Signal Strength. Once the
`central processor has received the report it compares the
`report to information in a position location database, Step
`303. Such a database can be generated as described above
`with reference FIG. 4.
`FIG. 5 illustrates an example of entries in such a position
`location database. Here a given position defined by
`longitude, latitude (500) is associated with a set of signal
`parameters, e.g., Signal Strengths of Signals of neighboring
`cells (510).
`The Searching operation determines whether there is a
`Signal Signature in the database which is an exact match for
`the received report, step 304. If such an exact match exists
`then the method proceeds to output the global position
`System (GPS) coordinates corresponding to that matching
`location and which are Stored in the database together with
`the Signal Signatures, Step 305. If, however, there is no exact
`match, then in the method shown in FIG. 3, the processor
`retrieves the Signal signature for the "N" (e.g., N=1, 2, 3,
`etc.) closest matches to the received report, step 306. The
`processor then extrapolates a location corresponding to
`Signal parameters in the received report from the locations of
`the N closest matches in accordance with a predetermined
`algorithm, Step 307. The System then outputs an approxi
`mate location based on the extrapolation, step 308. The
`number of closest matches can be Selected on the basis of
`various criteria Such as how closely the closest match in fact
`matches the report and the precision of the algorithm for
`extrapolating the location information. The algorithm could
`also take into account that the data is collected on the routes
`that were used to create the database. The algorithm can also
`consider whether the mobile stations were used inside of
`homes, offices or other buildings. The model can take into
`account path loSS models for the vicinity, hand-off bound
`aries and the position of the cell Sites relative to the point of
`collection. Other factors may also be considered in accor
`dance with the Signal characteristics which are being relied
`upon for representing the Signal signature of a geographic
`location. In one embodiment the location information could
`be extrapolated with a simple averaging technique relying
`on a number of geographic locations Surrounding the loca
`tion which has generated the reported Set of measurements.
`In an alternative arrangement the mobile Station could be
`approximated to be located at or about the position of the
`closest matching Signal Signature.
`Once the position is determined or approximated that
`information can be provided So as to dispatch assistance to
`the Subscriber at the station.
`FIG. 6 illustrates a block diagram representation of a
`System employing a present invention. Base Stations 601 are
`provided for a plurality of neighboring cells. The base
`Stations are connected to a mobile Switching center (MSC)
`602. A processor 603 associated with the MSC receives the
`signal measurements made by mobile stations 610. The
`processor then looks for a matching entry in database 604.
`The present invention therefore provides a simple data
`base look-up operation to determine the location of a mobile
`Station within a given area Serviced by the mobile network.
`What is claimed is:
`1. A method of locating a mobile Station within a given
`cell, the method comprising the Steps of
`transmitting to the mobile Station a list of neighbor cell
`Site frequencies,
`receiving from the mobile Station a set of measurements
`asSociated with Said list of neighbor cell Site frequen
`C1GS,
`
`Page 6 of 7
`
`

`

`S
`comparing Said Set of measurements to a position location
`database comprising a plurality of positional informa
`tion within the given cell, wherein Said location data
`base contains a set of measurements associated with the
`list of neighbor cell Site frequencies for each of a
`plurality of geographic location coordinates within the
`given cell, and includes Searching Said location data
`base for a set of measurements most closely matching
`the set of measurements received from the mobile
`Station; and
`identifying, an approximate geographic location of the
`mobile Station based on the results of the comparing
`operation.
`2. The method of claim 1 wherein said step of identifying
`comprises the Step of reading out from Said database the
`geographic location coordinates corresponding to the Set of
`measurements most closely matching the Set of measure
`ments received from the mobile station.
`3. The method of claim 1 wherein said step of identifying
`comprises the Step of extrapolating geographic location
`coordinates from the geographic location coordinates cor
`responding to the Set of measurements most closely match
`ing the Set of measurements received from the mobile
`Station.
`4. The method of claim 1 wherein Said Step of comparing
`comprises the Step of Searching Said location database for a
`predetermine number of Sets of measurements most closely
`matching the Set of measurements received from the mobile
`Station.
`
`1O
`
`15
`
`25
`
`6,167,274
`
`6
`5. The method of claim 4 wherein said step of identifying
`comprises the Step of extrapolating geographic location
`coordinates from the geographic location coordinates cor
`responding to predetermined number of Sets of measure
`ments most closely matching the Set of measurements
`received from the mobile station.
`6. A method for generating a geographic location direc
`tory for a given cell Site comprising the Steps of:
`determining a list of frequencies for cell Sites neighboring
`the given cell site;
`measuring Signal characteristics of the frequencies from
`Said list at a plurality of geographic coordinates within
`the cell Site,
`compiling Said measured signal characteristics in a data
`base whereby a set of measurements of the Signal
`characteristics of the frequencies for the neighboring
`cell sites is correlated with a location defined by
`geographic coordinates from Said plurality of geo
`graphic coordinates within the cell site;
`extrapolating Signal characteristics for a geographic loca
`tion from Said compiled measured Signal characteris
`tics, and
`Storing Said extrapolated Signal characteristics for Said
`geographic location in Said database.
`
`Page 7 of 7
`
`