USOO7397424B2
`
`(12) United States Patent
`Houri
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,397,424 B2
`Jul. 8, 2008
`
`(54) SYSTEMAND METHOD FOR ENABLING
`CONTINUOUS GEOGRAPHC LOCATION
`E.ON FOR WIRELESS COMPUTING
`
`(75) Inventor: Cyril Houri, New York, NY (US)
`
`(*) Notice:
`
`(73) Assignee: Mexens Intellectual Property Holding,
`LLC, New York, NY (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 56 days.
`(21) Appl. No.: 11/170,337
`(22) Filed:
`Jun. 29, 2005
`
`9, 1999 Merriman et al.
`5.948,061 A
`6,047.234 A * 4/2000 Cherveny et al. ........... TO1,200
`6,151,631 A 1 1/2000 Ansell et al.
`6,289.341 B1
`9/2001 Barney
`6,377.987 B1
`4/2002 Kracht
`6,412,014 B1
`6/2002 Ryan
`6.425,007 B1
`7/2002 Messinger
`
`(Continued)
`OTHER PUBLICATIONS
`
`Place Lab: Device Positioning Using Radio Beacons in the Wild, by
`Anthony LaMarca et al., Pervasive 2005, Munich, Germany.
`
`(65)
`
`Prior Publication Data
`US 2006/O 170591 A1
`Aug. 3, 2006
`
`Related U.S. Application Data
`(60) final application No. 60/649,180, filed on Feb.
`
`(Continued)
`Primary Examiner Thomas H. Tarcza
`Assistant Examiner Harry Liu
`(74) Attorney, Agent, or Firm—Brian Roffe
`(57)
`ABSTRACT
`
`51) Int. Cl.
`System and method for enabling a wireless computing device
`(2006.01)
`(51)
`oIS 5/14
`to continuously determine its position includes a wireless
`(200601)
`GIC 2L/
`computing device and a wireless positioning system Substan
`(200 6,015
`H04O 7/20
`tially collocated therewith. The wireless positioning system
`has a first positioning mode in which it communicates with a
`(52) U.S. Cl. .................. 342/357.14; 701.2009,
`wireless positioning network to enable the geographic loca
`7.
`(58) Field of Classification Search .......455/67. 3.oo tion of the computing device to be determined upon reception
`S
`lication file f
`1
`hhi s
`of signals from the positioning network and a second posi
`ee application file for complete search history.
`tioning mode in which it enables the geographic location of
`References Cited
`the wireless computing device to be determined upon recep
`tion of signals from one or more of the wireless beacons and
`analysis of the signals in light of positional information about
`wireless beacons contained in a database. The wireless posi
`tioning system Switches between the positioning modes
`depending on reception of signals from the wireless position
`ing network.
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`2, 1993 Wu
`5,185,860 A
`5,675,741 A 10/1997 Aggarwal et al.
`5,835,720 A 11/1998 Nelson et al.
`5,918,181 A * 6/1999 Foster et al. ............. 455,456.1
`5,944,790 A
`8/1999 Levy
`5.948,055 A
`9/1999 Pulsipher et al.
`
`
`
`27 Claims, 3 Drawing Sheets
`
`Position 3
`<X3,Y3,S3
`
`X,Y,Sl
`
`"Position 2
`
`Page 1 of 12
`
`SAMSUNG EX-1032
`
`

`

`US 7,397.424 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,507,869
`6,508,710
`6,665,715
`6,847,892
`7,000,015
`2003, OO69693
`2004/OO87317
`2004/0174297
`2004/02145.50
`2004/O23O370
`2004/O23O374
`2005/O105600
`2005/O135292
`2005/O136845
`2005/0227689
`2005/0278756
`2005/02787.58
`2005/0282558
`
`1, 2003
`1, 2003
`12, 2003
`1/2005
`2, 2006
`4, 2003
`5, 2004
`9, 2004
`10, 2004
`11, 2004
`11, 2004
`5/2005
`6, 2005
`6, 2005
`10, 2005
`12, 2005
`12, 2005
`12, 2005
`
`Franke et al.
`Paravia et al.
`Houri
`Zhou et al. .................. TO1,213
`Moore et al. ...
`... 709,224
`Snapp et al. ...
`... 701 (213
`Caci ...........
`455/4.56.1
`Cho ..
`342,357.14
`Jenkins .......
`... 455,403
`TZamaloukas .
`701, 200
`TZamaloukas .
`701 217
`Culum et al. ..
`375,150
`Graumann .................. 370,328
`Masuoka et al. ......... 455/67.14
`Jewett ...........
`455,433
`Bodlaender .
`... 725/89
`Bodlaender .
`... 725/89
`Choi et al. ............... 455,456.1
`
`
`
`2006/0170591 A1* 8, 2006 Houri .................... 342,357.14
`2006/0224319 A1 * 10/2006 Rogers ....................... TO1,213
`OTHER PUBLICATIONS
`Challenge: Ubiquitous Location-Aware Computing and the “Place
`Lab' Initiative, by Bill N. Schillitet al., Proceedings of the First ACM
`International Workshop on Wireless Mobil.
`A Case Study in Building Layered DHT Applications, by Yatin
`Chawathe et al., Jan. 2005.
`Accuracy Characterization for Metropolitan-scale Wi-Fi Localiza
`tion, by Yu-Chung Cheng et al., Proceedings of Mobisys 2005, Jan.
`2005.
`Social Disclosure of Place: From Location Technology to Commu
`nication Practices, by Iam Smith et al., Pervasive 2005, Munich,
`Germany.
`Privacy and Security in the Location-enhanced WorldWideWeb, by
`Jason I. Hong et al., Proceedings of Ubicomp 2003, Seattle, WA, Oct.
`2003.
`* cited by examiner
`
`Page 2 of 12
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 1 of 3
`
`US 7,397.424 B2
`
`FIG. 1
`
`
`
`
`
`
`
`
`
`Wireless
`Positioning
`System
`14
`
`
`
`GPS device
`12
`
`Switch 16
`
`Computing
`device
`10
`
`Page 3 of 12
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 2 of 3
`
`US 7,397,424 B2
`
`FIG. 2
`
`CD
`
`
`
`Position 3
`-X3,Y3,S3
`
`Position war" Position 2
`X1, Y1,Sl
`X2,Y2,S2
`
`FIG. 3
`
`Page 4 of 12
`
`

`

`U.S. Patent
`
`Jul. 8, 2008
`
`Sheet 3 of 3
`
`US 7,397.424 B2
`
`For each beacon
`referenced by its unique
`id, the scanner records a
`series of (Xi,Yi,Si)
`
`
`
`
`
`Calculation
`algorithm
`
`
`
`Estimated location of the
`beacon (X,Y)
`
`
`
`
`
`Store location of beacon
`in database
`
`FIG. 5
`
`
`
`The device reads the signal
`received by the surrounding
`beacons (ld, Si)
`
`This data is submitted to
`the database to retrieve the
`geographic position (Xi,Yi)
`of each beacon to form
`(Xi,Yi,Si)
`
`Calculation
`algorithm
`
`Estimated location of the
`device (X,Y)
`
`Page 5 of 12
`
`

`

`US 7,397,424 B2
`
`1.
`SYSTEMAND METHOD FOR ENABLING
`CONTINUOUS GEOGRAPHC LOCATION
`ESTMATION FOR WIRELESS COMPUTING
`DEVICES
`
`CROSS REFERENCE TO RELATED
`APPLICATION
`
`This application claims priority under 35 U.S.C. S 119(e) of
`U.S. provisional patent application Ser. No. 60/649,180 filed
`Feb. 3, 2005, the specification of which is incorporated by
`reference herein.
`
`10
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to a system and
`method for enabling a wireless computing device to deter
`mine its position using a wireless positioning network, e.g., a
`satellite-based positioning system, irrespective of the recep
`tion of positioning signals from the wireless positioning net
`work by the computing device.
`The present invention also relates to a system and method
`for passively building a database of wireless beacons by
`means of wireless computing devices equipped with position
`ing systems and disseminating the database to other comput
`ing devices.
`The present invention also relates to a system and method
`ascertaining the geographical locations of wireless comput
`ing devices based on a database of wireless beacons and a
`system and method for creating the database of wireless bea
`COS.
`
`15
`
`25
`
`30
`
`BACKGROUND OF THE INVENTION
`
`2
`to the beacons' positions. Additional information about Place
`Lab is found in: Place Lab: Device Positioning Using Radio
`Beacons in the Wild, by Anthony LaMarca et al., Pervasive
`2005, Munich, Germany; Challenge: Ubiquitous Location
`Aware Computing and the “Place Lab' Initiative, by Bill N.
`Schillit et al., Proceedings of The First ACM International
`Workshop on Wireless Mobile Applications and Services on
`WLAN (WMASH 2003), San Diego, Calif. September 2003:
`A Case Study in Building Layered DHT Applications, by
`Yatin Chawathe et al., January 2005: Accuracy Characteriza
`tion for Metropolitan-scale Wi-Fi Localization, by Yu-Chung
`Cheng et al., Proceedings of Mobisys 2005, January 2005;
`Social Disclosure of Place: From Location Technology to
`Communication Practices, by Ian Smith et al., Pervasive
`2005, Munich, Germany; and Privacy and Security in the
`Location-enhanced World WideWeb, by Jason I. Hong et al.,
`Proceedings of Ubicomp 2003, Seattle, Wash. October 2003.
`Another positioning system is that of Skyhook Wireless
`which uses a database of known Wi-Fi access points to cal
`culate the precise location of any Wi-Fi enabled device. For
`this system, known Wi-Fi networks are mapped, e.g., by
`having hired drivers travel every street in a neighborhood, and
`auser's location is calculated based on the Wi-Fi networks the
`Wi-Fi enabled device detects at a given moment using pro
`prietary software. If the device can identify three networks, it
`can determine its position, e.g., using triangulation. The more
`networks the device detects simultaneously, the more accu
`rate the locational fix.
`It would be desirable to provide a single positioning system
`for a wireless computing device which is capable of continu
`ously determining the position of the wireless computing
`device using both a wireless positioning network and a data
`base of wireless beacons to enable optimum positional deter
`mination.
`
`OBJECTS AND SUMMARY OF THE
`INVENTION
`
`It is an object of the present invention to provide a new
`system and method for enabling a wireless computing device
`to determine its position using a wireless and/or satellite
`based positioning system irrespective of the reception of posi
`tioning signals therefrom by the computing device.
`It is yet another object of the present invention to provide a
`new system and method for geographically locating wireless
`computing devices using signals broadcast by wireless bea
`COS.
`It is still another object of the present invention to provide
`a new system and method for passively building a database of
`wireless beacons by means of wireless computing devices
`equipped with positioning systems and disseminating the
`database to other computing devices.
`Still another object of the present invention is to provide a
`new system and method ascertaining the geographical loca
`tions of wireless computing devices based on a database of
`wireless beacons and a system and method for creating the
`database of wireless beacons.
`In order to achieve one of the above objects and others, a
`system for enabling a wireless computing device to continu
`ously determine its position in accordance with the invention
`includes a wireless computing device and a wireless position
`ing system substantially collocated therewith. The wireless
`positioning system has a first positioning mode in which it
`communicates with a wireless positioning network to enable
`the geographic location of the wireless computing device to
`be determined upon reception of signals from the wireless
`positioning network and a second positioning mode in which
`
`35
`
`As portable wireless computing devices proliferate, there
`is a growing demand to continuously and accurately know the
`geographic location of the computing devices. There are basi
`cally two different ways to determine the geographic loca
`tions of a computing device, either using a wireless position
`ing network Such the GPS system or using a database of
`40
`wireless beacons and determining position using this data
`base.
`The first technique suffers from the difficulty in continu
`ously obtaining signals, e.g., from a network of satellite, to
`enable the position of the computing device to be determined.
`It is recognized that Such difficulties commonly arise in
`enclosed areas and confined areas, such as in areas with a
`large concentration of tall buildings and in tunnels.
`The second technique requires the creation of a database of
`wireless beacons, and the computing device to be within
`range of a plurality of such wireless beacons. In the absence
`of wireless beacons within range, the position of the comput
`ing device cannot be determined.
`For the second technique, several systems are being used to
`enable wireless computing devices to determine their posi
`tion. One such system is Place Lab. Place Lab is software
`providing low-cost, easy-to-use device positioning for loca
`tion-enhanced computing applications. The Place Lab
`approach is to allow wireless computing devices such as
`notebook computers, PDAs and cell phones, to locate them
`selves by listening for radio beacons such as 802.11 access
`points, GSM cell phone towers, and fixed Bluetooth devices
`that exist in the Surrounding environment. These beacons all
`have essentially unique identifications, for example, a MAC
`address. The devices compute their own location by hearing
`65
`one or more IDs, looking up the associated beacons' positions
`in a stored map, and estimating their own position referenced
`
`45
`
`50
`
`55
`
`60
`
`Page 6 of 12
`
`

`

`3
`it enables the geographic location of the wireless computing
`device to be determined upon reception of signals from one or
`more of the wireless beacons and analysis of the signals in
`light of positional information about wireless beacons con
`tained in a database. The wireless positioning system
`Switches between the first and second positioning modes to
`obtain a determination of its geographic location depending
`on reception of signals from the wireless positioning network.
`Since the locational information in the first positioning mode,
`i.e., that from the wireless positioning network, is more accu
`rate, when Such information is available it is used and when
`unavailable, a database-derived location is provided. The
`Switch may be implemented as a Software-switch.
`In the second positioning mode, the wireless beacons pro
`vide identification information which is associated with data
`about the strength of a signal therefrom and received by the
`wireless computing device. This identification and signal
`strength data is input into a calculation algorithm which deter
`mines the geographic location of the wireless computing
`device therefrom, the identification information being used to
`obtain positional information about the wireless beacons
`which is contained in the database.
`To create the database, particularly constructed wireless
`computing devices are used. Specifically, the wireless com
`puting devices is provided with a scanner arranged to com
`25
`municate with the wireless positioning network to enable its
`geographic location to be determined upon reception of sig
`nals from the wireless positioning network, for example,
`coupled to a GPS device. The scanner then obtains positional
`information about itself and identification and signal strength
`information about wireless beacons in order to derive the
`geographic location of the wireless beacons for inclusion in
`the database, using a calculation algorithm. In particular,
`Software in the Scanner analyzes the strength of signals
`received from the wireless beacons at a plurality of different
`positions of the Scanner and applies an algorithm to determine
`the position of the wireless beacons therefrom.
`A method for enabling a wireless computing device to
`continuously determine its position in accordance with the
`invention involves coupling the wireless computing device to
`a wireless positioning network to enable the geographic loca
`tion of the wireless computing device to be determined upon
`reception of signals from the wireless positioning network,
`providing a database of identification and positional informa
`tion about wireless beacons and enabling the geographic
`position of the wireless computing device to be continuously
`determined by obtaining a position signal derived from the
`signals from the wireless positioning network upon reception
`thereof and in the absence of reception of usable signals from
`the wireless positioning network, deriving a position signal
`from reception of signals from wireless beacons detected by
`the wireless computing device and analysis of the received
`signals using the database. The database is constructed by
`obtaining identification and signal strength data about each
`wireless beacon at a plurality of locations at which a signal
`from that wireless beacon is being received and applying an
`algorithm to determine positional information about the wire
`less beacons based on the signal strength data.
`A method for administering a database of wireless beacons
`in accordance with the invention entails maintaining a central
`database of wireless beacons, providing the central database
`to a plurality of wireless computing devices, enabling each
`wireless computing device to determine identification and
`positional information about wireless beacons not contained
`in the central database, periodically forwarding the identifi
`cation and positional information about wireless beacons not
`contained in the central database from the wireless computing
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,397,424 B2
`
`10
`
`15
`
`4
`devices to the central database, updating the central database
`to include the forwarded identification and positional infor
`mation, and periodically directing the updates of the central
`database to the plurality of wireless computing devices. Each
`wireless computing device can be designed to determine
`identification and positional information about wireless bea
`cons as described above with respect to use of the scanner.
`A related embodiment of the invention is a system for
`enabling a wireless computing device to continuously deter
`mine its position in which a central database is provided
`containing identification and positional information about
`wireless beacons and receives identification and positional
`information about wireless beacons not previously contained
`therein and generates database updates based thereon. Wire
`less computing devices each include a local database contain
`ing positional information about wireless beacons and wire
`lessly communicate with the central database to receive the
`database updates and add the database updates to the local
`database. A wireless positioning system is Substantially col
`located with each wireless computing device and enable the
`geographic location of the wireless computing device to be
`determined upon reception of signals from at least one wire
`less beacon and analysis of the signals in light of the posi
`tional information about wireless beacons contained in the
`local database. This location determination can be performed
`in any of the ways described above.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention, together with further objects and advan
`tages thereof, may best be understood by reference to the
`following description taken in conjunction with the accom
`panying drawings, wherein like reference numerals identify
`like elements, and wherein:
`FIG. 1 is a schematic of a general concept used in the
`invention for enabling position of a wireless computing
`device to be determined.
`FIG. 2 is a schematic showing a scanner used to create a
`database of wireless beacons in accordance with the inven
`tion.
`FIG. 3 is an illustration of multiple scanner readings
`obtained to create the database of wireless beacons.
`FIG. 4 is a flowchart showing the mapping of wireless
`beacons from the scanner readings.
`FIG. 5 is a flowchart showing the determination of the
`position of a computing device based on instantaneously
`received signals from wireless beacons and the database
`thereof.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`Referring first to FIG. 1, to provide a system and method
`for enabling a wireless computing device to determine its
`position using a wireless and/or satellite-based positioning
`system irrespective of the reception of positioning signals
`therefrom by the computing device, each computing device
`10 is coupled to a wireless or satellite-based positioning sys
`tems such as a GPS device 12 such that the computing device
`10 and GPS device 12 are effectively collocated. Using posi
`tional data provided by the GPS device 12 and data about
`wireless beacons, Wi-Fi access points, cell phone towers or
`other comparable systems (hereinafter referred to as beacons)
`within reception range of the computing device 10, the com
`puting device 10 creates a database of wireless beacons
`within a wireless positioning system 14 including the geo
`graphic location of each beacon (the exact manner in which
`such a database is formed is described below).
`
`Page 7 of 12
`
`

`

`US 7,397,424 B2
`
`5
`A software switch 16 is interposed between the GPS device
`12 and the computing device 10 to vary the manner in which
`a determination by the computing device 10 of its position is
`made. Specifically, when the GPS device 12 receives an accu
`rate positioning signal, switch 16 would allow this GPS signal
`to be directed to the computing device 10 so that the comput
`ing device would consider its position that determined by the
`GPS signal. On the other hand, when the GPS device 12 is
`unable to provide an accurate GPS signal, switch 16 would
`allow a positioning signal derived from the wireless position
`ing system 14, and based on input from the computing device
`10 at that time, to be directed to the computing device 10 and
`the computing device 10 would consider its position that
`indicated by this positioning signal.
`Switch 16 would operate to revert back to allowing a GPS
`signal from GPS device 12 to be directed to computing device
`10 once GPS device 12 provides an accurate GPS signal.
`Accuracy of the GPs signal can be made in a manner known
`to those skilled in the art.
`Accordingly, the computing device 10 would be able to
`continuously know its position even in the absence of an
`accurate GPS signal. The computing device 10 could be
`designed to indicate the Source of its positioning signal, e.g.,
`an icon on a screen thereof could indicate either a satellite
`derived signal (a signal from GPS device 12) or a database
`derived signal (a positioning signal from wireless positioning
`system 14).
`Although represented as separate elements in FIG.1, this is
`for the purposes of explanation only and it should be under
`stood that computing device 10 can include wireless position
`ing system 14 and Switch 16 can be software implemented in
`the computing device 10. Moreover, GPS device 12 can also
`be incorporated into the computing device 10 So that a single
`hand-held or portable unit could include the entire system in
`accordance with this embodiment of the invention.
`The database of wireless beacons in wireless positioning
`system 14 can be considered a map which associates the fixed
`physical location of each wireless beacon, i.e., where they are
`geographically located, with a unique or semi-unique identi
`fication code of each wireless beacon. The location of each
`beacon can be expressed, for example, by latitude and longi
`tude, or possibly by another coordinate system.
`Construction of Such a map may be accomplished in a
`variety of ways, the simplest but most labor intensive being to
`place a positioning device, e.g., a GPS device, at the same
`location of each wireless beacon to thereby obtain the physi
`cal location of the wireless beacon from the GPS device. This
`however is highly impractical in view of the constant addition
`of wireless beacons and the manpower that would be
`required.
`A preferred and far simpler method would be to collect data
`about each wireless beacon based on information about the
`strength of a signal provided by each wireless beacon at a
`plurality of locations at which a signal from that wireless
`beacon is being received. Basically, the geographic location
`of each wireless beacon is determined based on analysis of the
`signal strength provided by that wireless beacon as a function
`of geographic location.
`To enable Such an analysis, a scanner 18 is equipped or
`collocated with a GPS device 20 and during movement of the
`scanner 18, a series of readings consisting of the position of
`the scanner 18, obtained using the GPS device 20, and the
`strength of the signal received at this position are obtained
`from a wireless beacon (see FIG. 2). The scanner 18 may be
`a hand-held computing device Such as a PDA or cell phone
`including a processor having software 22 designed to analyze
`the signal received via an antenna 24 from every single bea
`
`40
`
`45
`
`6
`con at different positions and estimate a geographic location
`thereof. A series of readings for each beacon will be stored in
`a database 26. Thus, if multiple beacons are being mapped,
`there will be multiple series of readings.
`Referring to FIG. 3, these readings will look like a series of
`data sets designated (Xi, Yi, Si) where Xi and Yi are the
`latitude and longitude, respectively, of the position of the
`scanner 18 and Si is the strength of a signal received at this
`position from wireless beacon 28. With the scanner 18 at
`position P1, a reading of (X1.Y1.S1) is obtained, with the
`scanner 18 at position P2, a reading of (X2.Y2.S2) is obtained
`and with the scanner 18 at position P3, a reading of (X3.Y3,
`S3) is obtained.
`Each series of readings, i.e., the readings obtained from
`each individual beacon 28, recorded by the scanner 18 may be
`stored in the scanner's memory. To obtain an estimated posi
`tion of each beacon, the series of readings relating only to that
`beacon is input to a calculation algorithm 30 that processes
`the readings to provide as output, an estimated position of the
`beacon 28 (see FIG. 4). If multiple series of readings are input
`to the algorithm, then the position of all of the beacons 28
`from which readings were obtained will be output.
`Note that at each position of the scanner 18, multiple read
`ings can be obtained, one for each beacon 28 in reception
`range of the scanner 18. These readings can be stored with an
`identification of the beacon 28 so that the readings can later be
`combined with other readings from the same beacon 28 in
`order to determine the location of the beacon 28.
`Different calculation algorithms 30 can be used in the
`invention to process each series of readings into the position
`of the beacon 28. These include Centroid, triangulation, New
`ton and the like. An exemplifying calculation algorithm 30,
`namely the Centroid algorithm, is described below. Gener
`ally, regardless of which algorithm 30 is used, approximately
`the same estimated position of the beacon 28 will be obtained
`and thus, the invention is not limited to use of any particular
`algorithm.
`It is important to bear in mind that scanner 18 can be and
`typically is the same as computing device 10 (in which case,
`GPS device 20 is the same as GPS device 12, the software 22
`and database 26 would be part of the wireless positioning
`system 14 and antenna 24 would be part of the wireless
`computing device 10). This embodiment will be considered
`hereinafter. In this case, computing device 10 would not only
`create and/or update the database 26 of wireless beacons in
`the wireless positioning system 14 via operation of the scan
`ning software 22 (when GPS signals from GPS device 12, 20
`are available) but would also use the same database 26 of
`wireless beacons it is updating to determine its position in the
`absence of an accurate GPS signal from the GPS device 12, 20
`(when GPS signals from GPS device 12, 20 are not available).
`Thus, when GPS signals are available and switch 16 is allow
`ing the GPS signal from the GPS device 12, 20 to be directed
`to the computing device 10, computing device 10 is working
`as scanner 18 to Scan the area around the computing device 10
`to determine the presence of (unmapped) wireless beacons
`and obtain geographic positional information about these
`unmapped wireless beacons for inclusion in the database 26
`of wireless beacons resident in the wireless positioning sys
`tem 14.
`After the estimated position of the beaconsis obtained, the
`final step in creating the database 26 of wireless beacons in
`wireless positioning system 14 is to store the positions of the
`beacons 28 in a database in a manner in which the position of
`the beacon is associated with an identification code. For
`example, the position of each beacon 28 can be stored in the
`database 26 in the form (Id, X, Y) where Id is a unique
`
`10
`
`15
`
`25
`
`30
`
`35
`
`50
`
`55
`
`60
`
`65
`
`Page 8 of 12
`
`

`

`7
`identification associated with or referencing the beacon 28
`and X, Y are the latitude and longitude coordinates, respec
`tively, of the beacon 28 as determined in the manner described
`above.
`The database creation step continues whenever a GPS sig
`nal is available and the position of the scanner 18 has
`changed. Thus, when the Scanner 18 is the same as computing
`device 10, movement of the computing device 10 in the pres
`ence of a GPS signal from GPS device 12, 20 can results in
`continuous updating of the database 26 of wireless beacons in
`wireless positioning system 14.
`In the exemplifying use described above with respect to
`FIG. 1, the database 26 of wireless beacons in wireless posi
`tioning system 14 is used only when a GPS signal from GPS
`device 12, 20 is unavailable. At this time, it is necessary to
`input data into the database26 to determine the position of the
`computing device 10.
`With reference to FIG. 5, determining the position of the
`computing device 10 using the database 26 of wireless bea
`cons in wireless positioning system 14 entails querying a
`receiver unit of the computing device 10, i.e., a network
`adapter or cell antenna 24, to find out which wireless beacon
`(s) 28 are “visible' and what is the strength of the signal
`received by the receiver from each wireless beacon 28. Vis
`ible beacons 28 are those from which the receiver receives a
`signal.
`From the antenna 24, the computing device 10 will obtain
`a series of readings each containing the unique identification
`associated with or referencing one of visible wireless beacons
`28 and the strength of the signal from that wireless beacon 28.
`This series of readings can be expressed in the form of (Id. Si)
`where Id is the unique identification of the wireless beacon 28
`and Si is the signal strength.
`The computing device 10 then submits this information to
`database26 in wireless positioning system 14 which contains
`the geographic location of the wireless beacons 28 in asso
`ciation with their identification. Using the data contained in
`the database 26, the corresponding, estimated geographic
`location of the wireless beacon 28 is obtained based on its
`identification contained in the information and is associated
`with the signal strength.
`After the location of the visible beacon(s) 28 associated
`with the antenna 24 is known, a series of (Xi, Yi, Si) records
`is provided to the calculation algorithm 30 to estimate the
`position of the antenna 24, i.e., the position of the computing
`device 10.
`As described above, a calculation algorithm 30 is used to
`determine the position of a wireless beacon 28 when creating
`the database 26 of wireless beacons and also to determine the
`position of the computing device 10 in the absence of a GPS
`signal from GPS device 12, 20.
`When determining the position of a wireless beacon 28 in
`the mapping mode from the series of readings (Xi.Yi,Si) to
`determine the position (X,Y) of the wireless beacon 28, the
`Centroid calculating algorithm averages the latitudes and lon
`gitudes recorded and adds the signal strength squared as a
`weight:
`
`where X and Y are the estimated position of the beacon 28 and
`the Si, Xi, Yi the information recorded by the scanner 18.
`When estimating the position of the computing device 10
`using the same formula, Xi, Yi would be the coordinates of the
`
`65
`
`US 7,397,424 B2
`
`8
`wireless beacons 28 referenced in the database 26 and Si
`would be the strength of the signal received from those same
`wireless beacons 28.
`Applying the database mapping technique described above
`using scanner 18, when incorporated into the wireless com
`puting device 10 with a common GPS device 12, it becomes
`possible to create a collaborative database. That is, a database
`which is continually being updated with data about new wire
`less beacons can be formed. Scanner 18 obtains identification
`and signal strength data about new, unmapped wireless bea
`cons when the GPS device 12 receives accurate positioning
`signals and determines the position of the unmapped wireless
`beacons for inclusion in the database of wireless beacons in
`the wireless positioning system 14 which is used when accu
`rate GPS signals from GPS device are not available. The same
`positional information about previously unmapped wireless
`beacons being directed to the database in the wireless posi
`tioning system 14 can also be directed to a central monitoring
`or administration facility which is charged with the respon
`sibility for providing an accurate database of wireless bea
`cons. The positional information can be forwarded to this
`facility periodically, such as every 24 hours. In conjunction
`with an upload of positional information about new wireless
`beacons, positional