(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2005/0136845 A1
`(43) Pub. Date:
`Jun. 23, 2005
`Masuoka et al.
`
`US 2005O136845A1
`
`(54) METHOD AND APPARATUS FOR LOCATION
`DETERMINATION USING MINI-BEACONS
`
`(75) Inventors: Ryusuke Masuoka, Potomac, MD
`(US); Sasikanth Avancha, Baltimore,
`MD (US); Sohil Thakkar, Greenbelt,
`MD (US); Jonathan Agre, Brinklow,
`MD (US)
`Correspondence Address:
`STAAS & HALSEY LLP
`SUTE 700
`1201 NEW YORKAVENUE, N.W.
`WASHINGTON, DC 20005 (US)
`(73) Assignee: FUJITSU LIMITED, Kawasaki (JP)
`(21) Appl. No.:
`10/929,763
`(22) Filed:
`Aug. 31, 2004
`
`Related U.S. Application Data
`(60) Provisional application No. 60/503,878, filed on Sep.
`22, 2003.
`
`Publication Classification
`
`(51) Int. Cl. ................................................. H04B 17/00
`(52) U.S. Cl. ..................................... 455/67.14; 455/456.6
`(57)
`ABSTRACT
`A System and method uses wireleSS communication devices
`as beacons to determine the relative location of another
`target wireleSS communication device. The beacons transmit
`identifying information that the target device can use to
`determine the identity of the beacon. The target device can
`measure the received intensity of the beacon transmissions
`and determine an associated beacon that best Satisfies a
`Specified criteria (e.g., largest signal Strength) using a pro
`cedure of the present invention that discriminates between
`multiple beacons.
`
`102
`
`Deployment of
`Mini-BeaCons
`
`
`
`
`
`Unit for Measurement
`of Signal Strengths
`for Beacons
`
`
`
`User (or some
`other) feedback
`
`Radio Map
`Beacon Locations
`Emitting Power of Beacon
`
`103
`
`104
`
`106
`
`invoked or
`self-invoking
`
`Location/Motion Status/Direction/
`Speed/Acceleration, ...
`
`Page 1 of 35
`
`SAMSUNG EX-1056
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 1 of 17
`
`US 2005/0136845 A1
`
`102
`
`Deployment of
`Mini-Beacons
`
`Unit for Measurement
`of Signal Strengths
`for Beacons
`
`
`
`
`
`
`
`Radio Map
`Beacon Locations
`Emitting Power of Beacon
`
`106
`
`invoked or
`self-invoking
`
`
`
`User (or some
`other) feedback
`
`Location/Motion Status/Direction/
`Speed/Acceleration, ...
`
`FIGURE 1A
`
`Page 2 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 2 of 17
`
`US 2005/013.6845 A1
`
`
`
`FIGURE 1B
`
`Page 3 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 3 of 17
`
`US 2005/0136845 A1
`
`V.
`
`
`
`N="Jon's Office"
`
`V4 N4="Library"
`
`V2 N2="VIP Room"
`
`N3="Conference Room"
`
`200
`
`FIGURE 2
`
`Page 4 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 4 of 17
`
`US 2005/0136845 A1
`
`N="Jon's Office"
`
`
`
`N4="Library"
`
`Okay to have
`overlaps in
`Don't-Care
`363
`
`N2="VIP Room"
`
`N3="Conference Room"
`
`300
`
`FIGURE 3
`
`Page 5 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 5 of 17
`1 N
`
`US 2005/0136845 A1
`
`Communication
`Coverage Area
`
`
`
`
`
`FIGURE 4
`
`\-N1
`LOCation
`N-n Coverage
`Area
`
`
`
`s-(
`D
`
`GY Ne
`
`Page 6 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 6 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 5
`
`Page 7 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 7 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 6
`
`Page 8 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 8 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 7
`
`Page 9 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 9 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 8
`
`Page 10 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 10 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 9
`
`Page 11 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 11 of 17
`
`US 2005/0136845 A1
`
`
`
`1 OOO
`
`FIGURE 10
`
`Page 12 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 12 of 17
`
`US 2005/0136845 A1
`
`
`
`FIGURE 11
`
`Page 13 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 13 of 17
`
`US 2005/0136845 A1
`
`
`
`
`
`
`
`
`
`12O2
`
`Pick a parameterized
`model for observation
`
`
`
`Pick a history
`segment of data
`starting from current
`
`
`
`Find the model (i.e. set
`of Earl), is
`(Posterior probability is
`used for Our Case)
`
`1208
`
`1210
`
`1212
`
`Continue until we
`finish all the history
`Segments
`
`Pick the best model
`from the models
`picked for each
`history segment
`
`Use this user model
`to estimate Values
`
`FIGURE 12
`
`Page 14 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 14 of 17
`
`US 2005/0136845 A1
`
`
`
`
`
`
`
`1302
`
`
`
`Get n RSS samples from each
`mini-beacon and average
`
`1304
`
`Add avg. samples to the sample list.
`Apply smoothing algorithm.
`
`1306
`
`Compute optimal line parameters using
`Current and past samples to estimate
`next sample. Compute the slope
`
`1308
`
`Output RSS vector values
`estimated using line parameters.
`
`1310
`
`1300
`
`FIGURE 13
`
`Page 15 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 15 of 17
`
`US 2005/0136845 A1
`
`1402
`
`Sample data=Y
`
`
`
`NO
`
`Continuously low
`RSS Sample
`
`1408
`
`Discard Current Sample
`and put last-times
`estimate as Current
`sample.
`
`1410
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Yes
`
`Moving Average
`Filter
`
`Compute optimala & b
`Using Linear Model.
`
`
`
`Compute motion state by estimating
`average slope to get final slope value.
`
`RSS Vector and motion State
`
`1414
`
`1416
`
`14OO
`
`FIGURE 14
`
`Page 16 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 16 of 17
`
`US 2005/0136845 A1
`
`Given data vector
`Y and its length L
`
`1502
`
`
`
`
`
`
`
`
`
`Optimala-average(Y)
`Optimal b=0
`
`1506
`
`Let vector Yn=Y(1:n)
`For n=minLength:L
`Compute a(n), b(n) and e(n) using
`line fitting algorithm.
`
`Select length ithat minimizes e(i)'s,
`Then seta-a(i), b=b(i)
`
`1508
`
`1500
`
`FIGURE 15
`
`Page 17 of 35
`
`

`

`Patent Application Publication Jun. 23, 2005 Sheet 17 of 17
`
`US 2005/0136845 A1
`
`1614
`
`sy.
`
`1612
`
`
`
`
`
`
`
`1602
`1606
`
`1608
`
`802.11
`RF Front End
`
`802.11
`Baseband
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Enclosure
`
`802.11 Chipset
`
`1610
`
`102
`
`FIGURE 16
`
`Page 18 of 35
`
`

`

`US 2005/O136845 A1
`
`Jun. 23, 2005
`
`METHOD AND APPARATUS FOR LOCATION
`DETERMINATION USING MINI-BEACONS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`0001. This application is related to, and claims the benefit
`of priority to, U.S. Provisional Application No. 60/503,878,
`filed Sep. 22, 2003, the contents of which are incorporated
`herein by reference.
`
`BACKGROUND OF THE INVENTION
`0002) 1. Field of the Invention
`0003. The present invention generally relates to a system
`and method of using wireleSS communication devices as
`beacons to allow a target wireleSS communication device to
`determine its location, and, more particularly, the present
`invention relates to using a collection of beacon devices that
`communicate using a wireleSS channel and a common pro
`tocol with a target device using this channel and protocol.
`0004 2. Description of the Related Art
`0005. In mobile computing, the location of the user
`becomes a fundamental parameter in many applications and
`Services. The ability to automatically and accurately obtain
`the location of a user or other communicating devices in a
`wireleSS networked environment is an enabling Step in the
`development of many new-applications and Services Such as
`tour-guide Systems, people/animal/object tracking, inven
`tory management, healthcare, area monitoring and digital
`Shopping assistants (Jonathan Agre, Adedeji Akinyemi,
`Lusheng Ji, Ryusuke Masuoka, and Pankaj Thakkar, "A
`Layered Architecture for Location-based Services in Wire
`less Ad Hoc Networks," IEEE Aerospace Conference,
`March, 2002, Big Sky, Mont., USA.).
`0006. The E911 requirements proposed by the U.S. Fed
`eral Communications Commission in which cellular tele
`phone carriers are required to implement a System for
`location determination of a wireleSS telephone that is used to
`dial an emergency 911 call, to a Specified accuracy, is one
`prominent example of a location-aware Service (Reed, J. H.,
`Krizman, K. J., Woerner, B. D., and Rappaport, T. S., “An
`Overview of the challenges and progreSS in meeting the
`E-911 requirement for location service,” IEEE Communi
`cations Magazine, Vol. 36, No. 4, pp 30-37, April, 1998).
`0007. There are many methods of automatically deter
`mining the location of an object. These methods range from
`Global Positioning System (GPS)-solutions, acoustic, infra
`red or radio-frequency Sensors, to inertial navigation SyS
`tems. Each method has advantages and disadvantages in
`various environments (e.g., indoors, outdoors), yielding
`differences in metricS Such as accuracy, repeatability, com
`putational complexity, power consumption, ease of use, cost
`and infrastructure requirements. In addition, different meth
`ods have advantages or disadvantages in Supporting require
`ments for client privacy and control of location information.
`In many applications of interest, ease of use and deployment
`are more important than high degrees of accuracy. Since
`there is no one technology that can address all environments
`and requirements, it is likely that many different determi
`nation methods will be needed to Support various location
`aware applications.
`
`0008 Some location-determination schemes can be fully
`implemented in an isolated client device, Such as a GPS
`navigation device, although there is a large cost in infra
`Structure and deployment of the Satellites. Other Systems
`determine the client location in System servers, Such as those
`employed at base Stations in cellular telephone Systems.
`Location information is often considered Sensitive and pri
`Vate and in general, a client-based Scheme is deemed to offer
`better privacy control for the user.
`0009. A particular location determination method may or
`may not depend on a two-way communications infrastruc
`ture as an integral part. In many Systems, a two-way com
`munication network is already incorporated in the devices
`for interaction with the remote location-aware applications.
`This communication capability can then also be used for
`location determination (as in base station Solutions to the
`E911 problem). In these cases, there can be a cost and
`System complexity advantage, if there is a radio transmitter
`and receiver on the device, and these can also be used for
`location measurements.
`0010) A beacon is a device at a known location that emits
`a signal that is used by a client to determine its location.
`Some examples of beacons include lighthouses, LORAN
`transmitters and GPS satellites. Various techniques are used
`in conjunction with the beacon Signal to actually obtain a
`“fix' or precise knowledge of the client position. These
`techniques can be as simple as proximity to the beacon (as
`with a lighthouse and a map) or as complex as estimating
`range to multiple beacons and then using triangulation or
`multilateration.
`0011. There exist many different approaches to location
`determination based on different technologies Such as radio
`frequency (RF) communication, infra-red (IR), visual,
`acoustic, electromagnetic field change, gyroscopic (inertial
`navigation), laser ranging and radar techniques. Each tech
`nology has inherent Strengths and weaknesses depending on
`many factors: accuracy, environment (e.g., temperature,
`pressure, wind, ambient light), power, infrastructure require
`ments, Susceptibility to noise, etc.
`0012. A target (or client) is an item whose location is to
`be found. In different Schemes, the target can be completely
`passive, or either a Source (transmitter) or a sink (receiver)
`or both. The basic techniques used by these technologies can
`be broadly classified in the following four categories:
`0013 1. Geometric: This typically involves taking mul
`tiple measurements between different transmitter-receiver
`Sets and the target. When the measurements are used to find
`the distance or range between a transmitter and the receiver,
`the method is called triangulation via lateration (or multi
`lateration) and when those are used to find angles, the
`method is called triangulation via angulation.
`0014 2. Proximity: Measure the nearness of a target to a
`known set of points. The nearneSS is a relative term as
`opposed to a range estimate. For example, if a target is
`communicating with a base Station, it must be Somewhere
`within the geographic coverage area of that Station.
`0015 3. Pattern recognition: The system is set up by
`taking measurements in the area of interest over a large
`number of grid points using transmitter/receiver pairs and
`Storing them in a map file. A measurement is made of the
`target and then Statistical methods are used to determine the
`target's most likely position.
`
`Page 19 of 35
`
`

`

`US 2005/O136845 A1
`
`Jun. 23, 2005
`
`0016 4. Scene analysis: Examines a scene in a sensor's
`field of view from a particular vantage point. This is
`typically done via cameras that use image processing to
`recognize changes in objects within their area of coverage
`and estimate location.
`0.017. Different methods use these technologies and cat
`egories individually or in combination to determine location.
`For example, GPS uses time-of-arrival (TOA) of radio
`frequency Signals from Several Satellite transmitters at a
`target's receiver to estimate range to the Satellites and then
`uses multi-lateration to determine position to within 20 m.
`Differential GPS uses the difference between the satellite
`and a local reference Signal to improve that accuracy to
`within 1 m. An example of a hybrid System uses a radio
`channel for Synchronization and a relatively slower ultra
`Sonic Signal TOA to compute range and then uses multi
`lateration. The RADAR system uses RF pattern analysis
`based on the minimum distance estimates obtained from a
`combination of Signal Strength, TOA and angle-of-arrival
`(AOA) (Bahl, P. and Padmanabhan, V., “Radar: An in
`building RF-based user location and tracking system,” IEEE
`Infocom, Tel Aviv, Isreal, pp. 775-784, March, 2000). A
`Survey of the State-of-the-art in location determination meth
`ods can be found in (Hightower, J. and Borriello, G.,
`“Location Systems for ubiquitous computing, IEEE Com
`puter, Vol. 34, No. 8, pp. 57-65, August, 2001).
`0.018
`RF-based schemes include a low cost of transmit
`ters and receivers and are unaffected by light, temperature,
`wind and non-metallic barriers. Also, if they can be com
`bined with the necessary RF communication components
`and infrastructure, then there are potential Savings in both
`Size and component cost.
`0019. There has been recent work on using cellular
`telephony RF-based schemes as part of the E-911 require
`ments (Reed, J. H., Krizman, K. J., Woerner, B. D., and
`Rappaport, T. S., “An Overview of the challenges and
`progreSS in meeting the E-911 requirement for location
`service, IEEE Communications Magazine, Vol. 36, No. 4,
`pp 30-37, April, 1998). These are either handset-based
`primarily using GPS and base-station-based Schemes. These
`include methods based on proximity, geometric Schemes
`using received signal strength (RSS), time of arrival (TOA)
`and angle of arrival (AOA), and pattern matching. Proximity
`and pattern matching are often combined. Time of arrival
`and Signal Strength are often combined to estimate range.
`Accuracy of the above schemes is around 150 m.
`0020. In many applications there is a need for indoor
`location methods and the accuracy required indoors is
`generally greater than outdoors. GPS is not effective
`indoors, although new technologies are being introduced
`that are Sensitive enough to operate in many indoor appli
`cations. Two of the main difficulties in indoor location
`methods are non-line of sight (walls) measurements and
`multipath due to reflections. A Survey describing the indoor
`channel and its signal propagation characteristics, as well as
`candidate channel models can be found in (Pahlavan, K., Li,
`X. and Makela, J. P., “Indoor Geolocation Science and
`Technology, IEEE Communications Magazine, pp. 112
`118, February, 2002). Some additional indoor schemes
`include Pseudo-lite GPS, augmented GPS, CDMA-based
`Schemes, Ultra-wideband and WLAN-based mechanisms.
`0021 One of the first indoor location systems (Wont, R.
`et al., “The Active Badge Location System,” ACM Transac
`
`tions on Information Systems, January 1992, pp. 91-102)
`relied on diffuse infrared technology. Following this, Several
`generations of indoor location Systems have been developed
`based on a combination of ultrasound and RF. The slower
`propagation rate of the ultrasonic Signal is easier to measure
`than RF. In one System, a preinstalled ceiling matrix of
`receivers and an RF base Station are used to locate a target
`transmitter. The RF base station polls the transmitter (user)
`periodically, and after being polled, sends an ultrasonic
`pulse to identify itself. The receiver matrix, which not only
`receives the ultrasonic pulse but also receives the RF poll
`Signal from the base-station, uses this information to find out
`the distance to the transmitter. In another System (Priyantha,
`N., Chakraborty, A. and Balakrishnan, “The Cricket Loca
`tion Support System.” Proc. 6-th Annual International Con
`ference on Mobile Computing and Networking (Mobicom
`00), ACM Press, New York, N.Y., 2000, pp. 32–43), the
`ceiling matrix is replaced with inexpensive beacon trans
`mitters. The transmitter (beacon) simultaneously transmits
`an RF and an ultra-Sonic pulse. The target receiver (listener)
`receives both types of Signal from the beacons and uses the
`RF for synchronization and the ultra-Sonic TOA to compute
`the distance, find the closest beacon and identifies its loca
`tion with that beacon. In yet another System that operates in
`the 900 MHz ISM band, signal strength is measured between
`nearby tags to estimate range and then determine location
`via lateration, in an ad hoc Situation with minimal infra
`structure (Hightower, J. and Want, R., “SpotON: Indoor 3-D
`Location Sensing from RF Signal Strength, Technical
`Report 2000-02-02, University of Washington, 2000).
`0022 Location Determination in WLANs is now dis
`cussed.
`0023 The rapid adoption of high speed wireless local
`area networks (WLANs) in the unlicensed ISM-band, such
`as 802.11b (a direct Sequence spread spectrum Scheme) and
`Bluetooth (a frequency hopped Scheme) had led to several
`investigations of WLAN-based positioning schemes for
`mobile computing applications. These Schemes typically use
`Signal Strength, TOA and/or AOA and can be classified as
`proximity, multilateration, triangulation and pattern match
`ing. Several algorithms have been developed that use trend
`ing or auxiliary knowledge to increase the accuracy of the
`underlying technology.
`0024. There are many localization technologies that use
`the readily available, measured Signal Strengths from
`WLAN communications to estimate range through Signal
`attenuation models or to perform pattern matching with a
`radio Signal Strength map of the area. Most of them use the
`measurements from multiple WLAN Access Points (WLAN
`AP's or just AP's) that are in fixed, known locations chosen
`for communication purposes. The measurement of Signal
`strength can be made either on the WLAN client side or at
`the WLAN APS to determine the location of a WLAN
`adapter (client).
`0025 These methods suffer in indoor environments
`where many obstacles Such as walls and furniture contribute
`to unpredictable radio channel characteristics and multipath
`interference. Specific knowledge of the building structure
`can often be used to improve the geometric methods.
`Another common method is to build a radio map of the area,
`match the current intensity readings to those in the radio
`map, and then determine the location based on closest
`
`Page 20 of 35
`
`

`

`US 2005/O136845 A1
`
`Jun. 23, 2005
`
`match. This usually gives better results than triangulation
`but it requires the user to build the radio map, a proceSS
`which can take many hours. Also, if the environment
`changes, such as new additions of WLAN AP's, this neces
`sitates a remapping effort.
`0026. In the indoor 802.11b environment, the pattern
`matching Schemes Seem to yield better accuracy than com
`peting methods, primarily as they do not depend on Struc
`tural knowledge of the building or on detailed modeling of
`the multipath environment. Typically, Signal Strength mea
`Surements are taken from multiple access points at known
`points covering the area of interest. Readings from two to
`more access points are usually needed to get the desired
`accuracy and then a pattern matching algorithm is applied.
`Many pattern matching Schemes are feasible: clustering,
`fuZZy logic, Bayesian, Markov, etc. Some examples of
`pattern matching WLAN based schemes are: Radar, Ekahau
`and a spinoff from work at Carnegie-Mellon University
`(Smailagic, A. et al., “Location Sensing and Privacy in a
`Context Aware Computing Environment,” Carnegie-Mellon
`University, Pittsburgh, Pa., September, 2001). A problem
`with pattern matching is the time consuming process of
`building the radio maps. If any of the access points are
`moved or there is rearrangement of furniture, than the area
`must be remapped. In addition, if there is a significant
`change in the environment Such as many people or bulky
`items, then the accuracy may decrease. There is also a
`problem with the accuracy and Stability of the measurement
`process on commercially available 802.11b chip sets.
`0.027 Other known technologies that use the proximity
`techniques are now discussed. Related art System 1 uses RF
`and ultraSonic pulses to estimate the distance between
`transmitter and receiver, and hence Special hardware is
`needed on the client Side. Related art System 2 also falls into
`this category. Here special hardware is used to identify the
`device. Beacons are transmitted by client devices and
`received at known fixed locations. The nearest receiver then
`notifies the client of its location. Related art system 3
`(Smailagic, A. and Siewiorek, D., “User Centered Interdis
`ciplinary Design of Wearable Computers,” ACM Mobile
`Computing and Communications Review, Vol. 3, No. 3,
`1999, pp. 43-52) does not require any hardware on the
`mobile user side and the location of the mobile client is
`determined by the closest access point the client is currently
`asSociated with. The data access point is used to infer
`location, and hence the accuracy is limited to placement of
`the access point. Related art System 4 puts pressure Sensors
`under the floor and then using user physical weight, one can
`track and identify the user. Again, the installment cost is
`high, Since one needs to construct the floor with Sensors
`beneath.
`0028. Types of beacon technologies are: 802.11b signal
`strength methods, IrDA Beacon methods, and Bluetooth
`Signal Strength methods.
`0029. An IrDA beacon includes both IrDA and Bluetooth
`communications and has several important features: 1) the
`device transmits programmable ID codes or local data using
`the IrDA standard communication channel and protocol, 2)
`angle and range (up to 7 m or 10 m) of IrDA can be adjusted
`horizontally (3 regions) or vertically (>55) into 6 regions.
`Another product is available as a kit and contains four
`detectors and four transmitters.
`
`0030 Yet a further system uses beacon devices that are
`placed in various locations either to represent that location
`or to represent an object present at that location and also to
`provide a URL web pointer for that location or object. The
`beacon periodically broadcasts a message containing the
`URL and any device that receives the message can access the
`web pages pointed to by the URL. The beacons use IR
`technology and the IrDA protocol.
`0031) A discussion of radio-frequency (RF) Signal
`Strength-based methods is now presented.
`0032 Conventional methods use either triangulation or
`pattern matching. In pattern matching a database of Signal
`measurements over the covered area is maintained. The
`contents of the database are called attributes and may
`contain RF characteristics Such as pilot Signal Strength,
`phase offset, time delay, angle of arrival, etc which can be
`used to differentiate the positions through the use of a
`location estimation algorithm. The database may be actually
`measured or it may be generated using mathematical mod
`eling.
`0033 Also in the cellular telephony domain, there are:
`U.S. Pat. Nos. 5,055,851; 4,891,650; 5,218,367 that use
`Signal Strength measurements. In the 851 and 650 patents,
`the Signal Strength is measured at the base Stations and used
`to estimate distance to four neighboring base Stations and
`then compute the location. In the 367 patent, the measure
`ments are made by the hand Set which transmits the values
`to a location computation unit.
`0034). In U.S. Pat. No. 5,960,341 “Positioning systems
`have an RF-measurements databank', by LeBlanc in 1999,
`an attribute database is constructed from a collection of
`measurements on uplink and downlink Signal Strength,
`transmitting power and other attributes for each basestation
`and a contour shape for each base Station is constructed
`using curve fitting techniques that account for non-unifor
`mity of the environment. When real time measurements are
`taken between a mobile unit and Surrounding base Stations,
`this is used to determine the interSecting contour shapes and
`thus location.
`0035). For example, in cellular telephony, U.S. Pat. No.
`6,263,208 “Geolocation estimation methods for CDMA ter
`minals based on pilot strength” by Chang in 2001, describes
`a Scheme in which a mobile unit at a Specific location
`measures the Signal Strength from all visible pilot Signals at
`that location and reports those values to a location compu
`tation unit. The location computation unit determines the
`location probability distribution using a Bayesian algorithms
`and an analytical model of the RF environment. This system
`is primarily used in an outdoor environment and relies on a)
`a set of measured values and b) an analytical model of the
`environment that includes propagation loSS, Shadow fading,
`fast fading and measurement errors.
`0036) A method for estimating the position and velocity
`of a mobile unit using downlink signal Strength of Six
`basestations was described in (Hellebrandt, “Estimating the
`position and velocity of Mobiles in Cellular Radio Net
`works,” IEEE Transactions on Vehicular Technology, Vol
`VT-26, No 1, February 1997, pp. 7-11.). The scheme uses an
`attribute database and estimates the location using a least
`Squares approach at the handset.
`0037. In U.S. Pat. No. 6,052,598 “Method for predicting
`the location of a mobile Station in a mobile communications
`
`Page 21 of 35
`
`

`

`US 2005/O136845 A1
`
`Jun. 23, 2005
`
`network,” by Rudrapatna, determines the approximate posi
`tion of a mobile unit using Signal Strength measurements.
`Using a Series of Signal Strength measurements the Velocity
`(speed and direction) can be determined. This is used for
`predicting handoff times. The technique Smoothes the Signal
`Strength using a rolling window. The changes in Signal
`Strength over time are estimated. Differing outdoor propa
`gation models for each base Station are used.
`0.038. These techniques all have problems operating in
`indoor areas. Some also require compilation of a large
`attribute database which is a tedious and time consuming
`process. In addition the database must be changed if any
`environmental characteristics are changed (e.g., Seasons).
`There also are the problems of relating distance to Signal
`Strength or other attributes in a general fashion. This is a
`complex and difficult task due to the internal Structure of
`interior Spaces.
`0039. Additional problems in related art include: 1) dif
`ficulty of System deployment and operation, 2) use in indoor
`environments as well as outdoor areas, 3) privacy control by
`client (target) with regard to disbursement of location data,
`4) high total cost of operation due to device and infrastruc
`ture requirements, and 5) collection and maintenance of
`calibration data or radio maps when environment changes.
`0040 Moreover, signal intensity-based methods exist
`that rely on the construction of a signal intensity map based
`on extensive measurements made in the environment prior
`to deployment. But, if the configuration of transmitterS/
`receivers is changed, then the area needs to be re-measured.
`
`SUMMARY OF THE INVENTION
`0041. The apparatus of the present invention, referred to
`as mini-beacons, and the methods for deployment and
`location calculation of the present invention, Solve the
`above-mentioned problems.
`0042. It is an aspect of the present invention to provide a
`System and method of using wireless communication
`devices as beacons to allow a target wireleSS communication
`device to determine its location.
`0043. It is another aspect of the present invention to
`provide a System and method of using a collection of beacon
`devices that communicate using a wireleSS channel and a
`common protocol with a target device using this channel and
`protocol.
`0044) It is a further aspect of the present invention to
`provide a target device capable of measuring the received
`Signal intensity of the beacon transmissions and executing a
`location determination procedure to determine the beacon
`that best Satisfies a pre-specified criteria.
`004.5 The above aspects can be attained by the system
`and method for using wireleSS communication devices as
`beacons to determine the relative location of a target wire
`leSS communication device. The beacons transmit identify
`ing information that the target device can use to determine
`the identity of the beacon. The target device can measure the
`received intensity of the beacon transmissions and determine
`an associated beacon that best Satisfies a Specified criteria
`(e.g., largest signal strength) using a procedure of the present
`invention that discriminates between multiple beacons.
`
`0046) The target device includes equipment used for
`mobile computing device with wireleSS capabilities Such as
`a laptop computer, a personal digital assistant (PDA), a
`cellular telephone or a similar device.
`0047 The beacon devices are placed in areas of interest
`and their transmissions are shaped to provide coverage for
`that interest area by adjusting the intensity of the beacon
`transmissions and by using Specially designed enclosures
`and antennas. The location of each beacon is known and
`made available to the target device, either directly by
`communication from the beacon or through external infor
`mation.
`0048. Further, the present invention includes an architec
`ture for an indoor/outdoor location determination System for
`mobile computing users that employs a multitude of beacon
`transmitters as location indicators.
`0049. The present invention further includes a scheme for
`deploying Such beaconS and for determining their operating
`parameterS Such as transmission power.
`0050. In addition, the present invention further includes
`Schemes for calculating which beacon to Select, based on
`various criteria Such as received signal Strength. The client
`location is then reported as the location of this associated
`mini-beacon. The calculation can be accomplished locally
`by the mobile computing user providing greater privacy
`protection or by a location Server. Further, a specific design
`for an apparatus that is a low cost, small size and low power
`radio-frequency beacon, called a mini-beacon, that is based
`on the IEEE 802.11 wireless local area networking standard
`in one aspect of the present invention. A similar device based
`on the IEEE 802.15.1 radio standard or Bluetooth is anoth
`aspect of the present invention.
`0051 More particularly, the mini-beacon approach
`Solves the problems of the related art through a combination
`of the use of low cost mini-beacons and Standard commu
`nication protocols and Standard communication hardware
`technologies, the mini-beacon deployment and the location
`calculation procedure. In general, whenever a difficult Spa
`tial area needs to be covered, one would simply add addi
`tional low-cost, mini-beacon devices. Some of the difficul
`ties that are overcome include: 1) operating with non-line
`of-site deployments, 2) collection and maintenance of
`building Signal intensity maps, 3) need for a priori knowl
`edge of building construction materials, 4) need to overcome
`multipath interference, and 5) need to limit density of
`mini-beacons. In addition, when implemented as a client
`Solution, the client has a greater degree of control on the
`dissemination of its location, providing enhanced privacy
`protection.
`0052 The method of the present invention provides
`cubicle-level (2-3 meter) resolu