Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 1 of 15 PageID #: 368
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 1 of 15 PageID #: 368
`
`
`
`
`
`
`
`EXHIBIT 2
`
`EXHIBIT 2
`
`
`

`

`US008618984B2
`
`(12) United States Patent
`Lin et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,618,984 B2
`Dec. 31, 2013
`
`(54) SELECTING BEACONS FOR LOCATION
`NFERENCE
`
`(75) Inventors: Jyh-Han Lin, Mercer Island, WA (US);
`Lon-Chan Chu, Redmond, WA (US);
`Aravind Krishnamachari Seshadri,
`Redmond, WA (US); Prasanta Ghosal
`s
`...
`s
`RNR S.Schifteels Anup
`s
`s
`s
`Kashinath Pachlag, Bothell, WA (US)
`
`(73) Assignee: Msion Corporation, Redmond, WA
`US
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 323 days.
`
`7/2008 Houri
`7,397,424 B2
`1/2009 Morgan et al. ............. 455,456.5
`7,474,897 B2 *
`8, 2009 Taschereau
`7,577,244 B2
`7,750,848 B2 * 7/2010 Normarket al. ......... 342,357.25
`2004/0203904 A1* 10, 2004 Gwon et al. ............... 455,456.1
`2007/0001867 A1* 1/2007 Rowe et al. .............. 340,825.49
`2007/0210961 A1
`9/2007 Romijn
`2008/017.6583 A1* 7/2008 Brachet et al. ............. 455,456.3
`2008/0238767 A1 10, 2008 Zhou
`2008/0252511 A1 10, 2008 Jacotot
`2008/0280624 A1 1 1/2008 Wrappe
`2010, 0013704 A1
`1/2010 Coutel et al. ............. 342,357.04
`
`OTHER PUBLICATIONS
`Olson et al., “Robust Range-Only Beacon Localization.” IEEE AUV,
`2004.
`
`Continued
`(Continued)
`
`(21) Appl. No.: 12/727,901
`(22) Filed:
`Mar 19, 2010
`(65)
`Prior Publication Data
`
`Sep. 22, 2011
`
`(2010.01)
`
`US 2011 FO227791 A1
`(51) Int. Cl.
`GOIS 5/02
`(52) U.S. Cl
`CPC
`
`G0IS 5/0252 (2013.01); G0IS5/0278
`• us
`(2013.01)
`
`- - - - - - - - - - - - -
`
`58 F. fo - - - - - ificati- - - - - -s - - - - - - - h- - - - - - 342/451: 342/464
`(58) is:
`assification s386. 450, 451, 463,464
`S
`licati - - - - - file? - - - - -
`1
`s
`hhi s
`s
`ee application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`Primary Examiner — Gregory C Issing
`
`ABSTRACT
`
`57
`(57)
`Location inference using selected beacons. Data is received
`representing a set of beacons observed by a computing
`device. The beacons are located withina first geographic area.
`geograp
`A Subset (e.g., a clique) of the beacons is selected based on a
`coverage area of each of the beacons, where each of the
`beacons in the selected subset has a coverage area that over
`laps with the coverage area of each of the other beacons in the
`selected Subset. Using known or estimated positions of the
`beacons, a second geographic area is defined based on the
`selected subset of beacons and the beacon reference data and
`the coverage areas associated therewith. The second geo
`graphic area, Smaller than the first geographic area, represents
`an aroproximate location of the computing device. In some
`pp
`pulung
`embodiments, the computing device is calculated to be within
`the second geographic area with 95% probability.
`
`5,936,572 A *
`6,776,334 B1
`
`8, 1999 Loomis et al. ........... 342.357.29
`8/2004 Garg
`
`20 Claims, 5 Drawing Sheets
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 2 of 15 PageID #: 369
`
`ISEE C1C3, W1
`AND W3. FIND
`MYPOSITION?
`
`INFER USERS
`POSITION
`RATIVETO
`C1 C3, W1 AND
`W3
`
`
`
`POSITIONING
`SYSTEM
`
`

`

`US 8,618,984 B2
`Page 2
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`Meneses, et al., “Enhancing the Location-Context through Inference
`over Positioning Data'. Retrieved at{<http://ubicomp.algoritimi.
`uminho.pt/csmu? proc/meneses-135.pdf>>, Jun. 2006, pp. 10.
`Sinha, et al., “A Beacon Selection Algorithm for Bounded Error
`Location Estimation in Ad Hoc Networks'. Retrieved at <<http://
`ieeexplore.ieee.org/stamp? stamp.jsp?arnumber 4127348&isnum
`ber=4127326>, Mar. 5-7, 2007, pp. 6.
`
`Lieckfeldt, et al. An Algorithm for Distributed Beacon Selection,
`Retrieved at<http://ieeexplore.ieee.org/stamp? stamp.jsp?arnum
`ber=4517414&isnumber=45.17341>>, Sixth Annual IEEE Interna
`tional Conference on Pervasive Computing and Communications,
`Mar. 17-21, 2008, pp. 318-323.
`Bahl, et al., “RADAR: An In-Building RF-based User Location and
`Tracking System”. Retrieved at{<http://www.cs.indiana.edu/~con
`nelly/Docs/radar.pdf>>, 2000, pp. 10.
`
`* cited by examiner
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 3 of 15 PageID #: 370
`
`

`

`U.S. Patent
`
`Dec. 31, 2013
`
`Sheet 1 of 5
`
`US 8,618,984 B2
`
`
`
`5) NINOILISOd
`
`
`
`VNE LSÅS
`
`CINV INA’S O’IOCINI—. "9MA CIN\/
`
`
`
`
`
`
`
`9 MW?NOI LISOd XIN
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 4 of 15 PageID #: 371
`
`I "5ÐI
`
`ZO
`
`

`

`U.S. Patent
`
`Dec. 31, 2013
`
`Sheet 2 of 5
`
`US 8,618,984 B2
`
`
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 5 of 15 PageID #: 372
`
`Z '5ÐI
`
`

`

`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 6 of 15 PageID #: 37337
`6e
`aP12/B
`652t
`R.J.27
`C
`d
`g
`
`
`
` mm0.eVtHa2P20ws.aU
`
`n3emm2w1,O3DceGD
`
`baHmS
`
`5m.m03
`
`,mm
`
`32#.BmMm9,awP65l}18
`
`
`
`
`
`<._.<n_mozmmmu—mmzoo/Em
`
`TRmUH>m_n_
`
`
`
`memmmuofi63%03:5on
`
`
`
`<m_~_<>m_O_>_m__>_
`
`momgmm.OHn—
`
`
`
`
`
`2%._.m_mmm__n__._.2m_n__zoo<mm
`
`
`
`._.2m_zOn__>_Oomo<n_w_m_._.z_
`
`
`
`._.Zm_zon__>_oomm._..__n_
`
`
`
`._.2m_zon__>_ooMDOZO
`
`
`
`._.2m_zOn__>_OomozmmmEZ
`
`
`
`<mm<moém>8EEmEzEfiezoo/mm.
`
`E5.
`
`2%magma
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 31, 2013
`
`Sheet 4 of 5
`
`US 8,618,984 B2
`
`FIG. 4
`
`
`
`
`
`RECEIVE BEACONNO
`FINGERPRINT FROM
`MOBILEDEVICE
`
`404
`
`406
`
`4.08
`
`410
`
`REMOVE OUTLYING BEACONS
`
`SELECT CLIQUE OF BEACONS
`
`INFER GEOGRAPHICAREA OF
`MOBILE DEVICE BASED ON
`SELECTED BEACONS
`
`PROVIDE THE INFERRED
`GEOGRAPHICAREA TO THE
`MOBILE DEVICE AS THE
`APPROXIMATE LOCATION OF THE
`MOBILE DEVICE
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 7 of 15 PageID #: 374
`
`

`

`U.S. Patent
`
`Dec. 31, 2013
`
`Sheet 5 of 5
`
`US 8,618,984 B2
`
`FIG.5
`
`
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 8 of 15 PageID #: 375
`
`

`

`1.
`SELECTING BEACONS FOR LOCATION
`NFERENCE
`
`US 8,618,984 B2
`
`BACKGROUND
`
`Some existing positioning systems such as global position
`ing systems (GPS) determine the location of devices using
`satellites. Other systems such as collaborative positioning
`systems determine the location of the devices based on
`crowd-sourced data. The crowd-sourced data typically
`includes a list of beacons observed at a particular location
`along with identification of the particular location as obtained
`by mobile devices such as laptops, netbooks, and cellular
`telephones. The positions of the beacons are then used to
`estimate the location of devices (e.g., those lacking GPS
`capability or coverage) that request position information
`based on an observed list of beacons. The complexity and
`accuracy of the estimations depend in part on which beacons
`are selected for the estimations.
`
`10
`
`15
`
`SUMMARY
`
`Embodiments of the disclosure enable the selection of
`beacons from which to infer a location of a computing device.
`A computing device observes a set of beacons within a first
`geographic area. Data representing the set of beacons is
`received from the computing device. A subset of the beacons
`is selected based on a coverage area of each of the beacons
`such that each of the beacons in the selected subset has a
`coverage area that overlaps with the coverage area of each of
`the other beacons in the selected Subset. A second geographic
`area, Smaller than the first geographic area, is defined based
`on the selected Subset of beacons, beacon reference data, and
`the coverage areas to estimate the location of the computing
`device.
`This Summary is provided to introduce a selection of con
`cepts in a simplified form that are further described below in
`the Detailed Description. This Summary is not intended to
`identify key features or essential features of the claimed sub
`ject matter, nor is it intended to be used as an aid in determin
`ing the scope of the claimed Subject matter.
`
`25
`
`30
`
`35
`
`40
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is an exemplary block diagram illustrating a posi
`tioning system inferring a location of a mobile device based
`on a beacon fingerprint provided by the mobile device.
`FIG.2 is an exemplary block diagram illustrating receipt of
`a beacon fingerprint from a mobile computing device and
`calculation of a location for the mobile computing device
`based on the beacon fingerprint.
`FIG. 3 is an exemplary block diagram illustrating a com
`puting device selecting beacons from which to infera location
`of another device.
`FIG. 4 is an exemplary flow chart illustrating location
`inference based on selected beacons.
`FIG. 5 is an exemplary block diagram illustrating a beacon
`fingerprint having a maximally complete clique.
`Corresponding reference characters indicate correspond
`ing parts throughout the drawings.
`
`45
`
`50
`
`55
`
`60
`
`DETAILED DESCRIPTION
`
`Referring to the figures, embodiments of the disclosure
`enable selection of beacons from which to infer a location of
`a computing device. The beacons are selected based on their
`relationship to neighboring beacons. In some embodiments,
`
`65
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 9 of 15 PageID #: 376
`
`2
`the computing device detects a set of beacons b1, b, . . . .
`b}. Knowing the estimated positions and coverage areas of
`each of the beacons, aspects of the disclosure determine the
`Smallest circle Such that the location of the computing device
`is within the circle with 95% probability. The calculated
`location of the computing device is provided to the computing
`device.
`Referring again to FIG. 1, an exemplary block diagram
`illustrates the positioning system 106 inferring a location of a
`mobile device 102 based on a beacon fingerprint provided by
`the mobile device 102. The mobile device 102 (e.g., a mobile
`telephone) detects or observes one or more beacons including
`cellular towers (or sector if directional antennas are
`employed) and wireless fidelity (Wi-Fi) access points or other
`wireless access points (WAPs).
`The beacons detected by the mobile device 102 at a given
`point in time represent the beacon fingerprint. The beacon
`fingerprint may also include other attributes of the detection
`Such as signal strength. While aspects of the disclosure may
`be described with reference to beacons implementing proto
`cols such as the 802.11 family of protocols, embodiments of
`the disclosure are operable with any beacon for wireless
`communication. In the example of FIG. 1, the mobile device
`102 detects the presence of beacons C1, C3, W1, and W3.
`The mobile device 102 provides the detected beacon fin
`gerprint to the positioning system 106 via a network 104. The
`network 104 includes a wireless cellular network in some
`embodiments, but other types of networks such as Wi-Fi and
`those providing Internet access are contemplated in other
`embodiments.
`The positioning system 106 stores, or has access to, data
`describing the approximate location of one or more of the
`beacons. The data is referred to as beacon reference data 314
`and describes, for example, the longitude, latitude, and/or
`altitude of the beacons. In some embodiments, the beacon
`reference data 314 is stored in a beacon store 212. Using the
`approximate location of at least one of the beacons in the
`detected beacon fingerprint, the positioning system 106 oper
`ates to infer the location of the mobile device 102 relative to
`the detected beacon fingerprint, as described herein. The
`inferred location is provided to the mobile device 102.
`Referring next to FIG. 2, an exemplary block diagram
`illustrates receipt of a beacon fingerprint from a mobile com
`puting device and calculation of a location for the mobile
`computing device based on the beacon fingerprint. The sys
`tem illustrated in FIG. 2 represents an example of a location
`inference system or positioning system in accordance with
`aspects of the disclosure. However, other systems, elements,
`and configurations are contemplated and within the scope of
`embodiments of the disclosure.
`The inference engine 214 receives a beacon fingerprint
`from devices such as the mobile device 204. The inference
`engine 214 accesses the beacon reference data 314 stored in
`the beacon store and predicts the location of observation
`associated with the unresolved beacon fingerprint. The pre
`dicted location is provided to the mobile device 204. The
`operation of the inference engine 214 is next described with
`reference to FIG. 3.
`Referring next to FIG. 3, exemplary block diagram illus
`trates a computing device 304 selecting beacons from a bea
`con fingerprint and calculating a location of another device
`based on the selected beacons. In some embodiments, the
`computing device 304 is associated with the positioning sys
`tem 106. For example, the computing device 304 represents
`the inference engine 214.
`The computing device 304 receives data from one or more
`of the devices 302, such as device #1 through device iiM, via
`
`

`

`3
`a network 306. The devices 302 include, for example, mobile
`computing devices such as mobile device 102. However, the
`devices 302 may include any device executing instructions
`(e.g., application programs) to provide data. The data
`includes beacon fingerprints.
`In some embodiments, the devices 302 include portable
`computing devices such as laptops, netbooks, gaming
`devices, and/or portable media players. Further, each of the
`devices 302 may represent a group of processing units or
`other computing devices.
`Exemplary networks 306 include wired and/or wireless
`networks, and may represent local area networks or global
`networks such as the Internet. In embodiments in which the
`network 306 includes wireless networks, the computing
`device 304 and the devices 302 may be enabled with technol
`ogy such as BLUETOOTH brand wireless communication
`services (secured or unsecured), radio frequency identifica
`tion (RFID), Wi-Fi such as peer-to-peer Wi-Fi, ZIGBEE
`brand wireless communication services, near field communi
`cation (NFC), and other technologies that enable short-range
`or long-range wireless communication.
`The computing device 304 has at least one processor 308
`and one or more computer-readable media Such as a memory
`area 310. The processor 308 includes any quantity of process
`ing units, and is programmed to execute computer-executable
`instructions for implementing aspects of the disclosure. The
`instructions may be performed by the processor 308 or by
`multiple processors executing within the computing device
`304, or performed by a processor external to the computing
`device 304 (e.g., by a cloud service). In some embodiments,
`the processor 308 is programmed to execute instructions such
`as those illustrated in the figures (e.g., FIG. 4).
`The memory area 310 includes any quantity of media asso
`ciated with or accessible to the computing device 304. The
`memory area 310 may be internal to the computing device
`304 (as shown in FIG. 3), external to the computing device
`304 (not shown), or both (not shown).
`The memory area 310 stores beacon identifier sets 312,
`such as beacon identifier set #1 through beacon identifier set
`iN. Each set 312 of beacon identifiers corresponds to a bea
`con fingerprint observed by one of the devices 302. Each of
`40
`the beacon identifiers within each of the sets 312 corresponds
`to one of the observed beacons. For example, each Wi-Fi
`beacon has a Basic Service Set Identifier (BSSID). In another
`example, each Global Service for Mobile communications
`(GSM) cellular tower includes a mobile country code (MCC),
`mobile network code (MNC), location area code (LAC), and
`a cell identifier. Universal Mobile Telecommunication Sys
`tem (UMTS) towers have beacon identifiers composed of
`MCC, MNC, and a cell identifier. Carrier Division Multiple
`Access (CDMA) towers have beacon identifiers composed of
`a system identifier, network identifier, and a base-station
`50
`identifier.
`The memory area 310 further stores beacon reference data
`314. The beacon reference data 314 for one of the beacons
`describes a position of the beacons. In some embodiments
`such as shown in FIG. 2, the beacon reference data 314 is
`stored on computer-readable media separate or remote from
`the computing device 304 (e.g., stored in the beacon store
`212). For example, the beacon reference data 314 may be
`stored by a cloud computing service, and the computing
`device 304 accesses the beacon reference data 314 via a web
`service.
`The memory area 310 further stores, or has access to,
`coverage area data 315. The coverage area data 315 includes
`coverage areas associated with the beacons represented by the
`beacon identifier set 312. Each of the beacons has a particular
`coverage area associated therewith. The coverage area may
`correspond to, for example, a circle or other shape. In some
`embodiments, the coverage area data 315 corresponds to
`
`30
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 10 of 15 PageID #: 377
`
`45
`
`55
`
`60
`
`65
`
`US 8,618,984 B2
`
`10
`
`15
`
`25
`
`35
`
`4
`signal strength. Further, in Some embodiments, the coverage
`area data 315 may be part of the beacon reference data 314.
`The coverage area may be described by, for example, a radius
`or range of the beacons.
`The memory area 310 further stores one or more computer
`executable components for implementing aspects of the dis
`closure. Exemplary components include an interface compo
`nent 316, filter component 318, clique component 320, and
`inference component 322. Operation of the components is
`discussed below with reference to FIG. 4.
`At least a portion of the functionality of the various ele
`ments in FIG.3 may be performed by other elements in FIG.
`3, or an entity (e.g., processor, web service, server, applica
`tion program, computing device, etc.) not shown in FIG. 3.
`Referring next to FIG. 4, an exemplary flow chart illus
`trates location inference based on beacons selected from a
`beacon fingerprint. The beacon fingerprint represents a set of
`beacons in a geographic area (e.g., a first geographic area) as
`observed by a device such as device 302 at a particular instant
`in time while the device 302 is at a particular geographic
`location (e.g., the point of observation). Upon receipt of the
`beacon fingerprint at 402 from device 302, a computing
`device Such as computing device 304 analyzes the beacon
`fingerprint. For example, the computing device 304 may
`receive a request to calculate the point of observation, or
`location, of the beacon fingerprint. The computing device 304
`may also receive, or already have access to, beacon reference
`data 314 and coverage area data 315 associated with the
`beacons in the beacon fingerprint.
`At 404, one or more outlying beacons may be removed
`from the beacon fingerprint (e.g., from the beacon identifier
`set 312). The outlying beacons represent the beacons in the
`beacon fingerprint that are on the edge, boundary, or outskirts
`of the geographic area (e.g., the first geographic area) covered
`by the beacon fingerprint. The outlying beacons also repre
`sent the beacons that have moved, or are out of place. The
`outlying beacons are identified based on the beacon reference
`data 314 associated with the beacons. Alternatively, the bea
`cons near the center of the geographic area are selected for
`further processing (thus excluding the outlying beacons).
`At 406, a clique of beacons is selected from the beacons
`remaining after the operation at 404. The clique represents a
`subset of the beacons where each of the beacons in the subset
`has a coverage area that overlaps with the coverage area of
`each of the other beacons in the subset. In some embodiments,
`the Subset of beacons is modeled or represented as an undi
`rected graph with the beacons as nodes and where the beacons
`with overlapping coverage areas are connected by an edge
`between the respective nodes. In such embodiments, the
`clique is described as the subset of beacons where any two
`beacons in the Subset are connected by an edge. Some
`embodiments determine the maximally complete clique of
`beacons. Alternatively, some embodiments may calculate the
`maximum complete clique of beacons. Determining the
`maximally complete clique is often less computationally
`intensive than determining the maximum complete clique.
`Further, adding another beacon to a maximally complete
`clique may not make the intersected area Smaller to improve
`the accuracy of the location estimation. If there is more than
`one maximally complete clique, aspects of the disclosure
`select the clique with the most beacons to attempt to obtain a
`Smaller intersected area.
`At 408, a second geographic area is inferred or defined
`based on the clique of beacons, along with the beacon refer
`ence data 314 and coverage area associated with the clique of
`beacons. For example, a circle may be inferred. The second
`geographic area represents an area in which the computing
`device that provided the beacon fingerprint is located (e.g.,
`the point of observation). By reducing the quantity of beacons
`
`

`

`US 8,618,984 B2
`
`5
`from which to infer the second geographic area, the second
`geographic area as defined by the clique is smaller than the
`first geographic area.
`At 410, the second geographic area is provided or identi
`fied to the computing device as an approximate location of the
`computing device. For example, the boundaries of the second
`geographic area are provided to the computing device. In
`another example, a center of the second geographic area is
`determined and provided to the computing device as the
`approximate location of the point of observation of the com
`puting device.
`10
`In an example in which there are at least three beacons from
`which the second geographic area is determined, the second
`geographic area is determined by triangulation.
`In some embodiments, the operations illustrated in FIG. 4
`are performed by the computing device 304. In other embodi
`ments, one or more of the operations illustrated in FIG. 4 are
`performed by another computing device (e.g., as a web ser
`vice). In still other embodiments such as peer-to-peer
`embodiments, one or more of the operations illustrated in
`FIG. 4 are performed by the devices 302.
`Further, the operations illustrated in FIG. 4 may be imple
`mented as software instructions encoded on a computer-read
`able medium, in hardware programmed or designed to per
`form the operations, or both. As an example, the operations in
`FIG. 4 may be implemented as computer-executable compo
`nents or other software such as in the components illustrated
`25
`in FIG. 3. In such an example, the interface component 316,
`when executed by the processor 308, causes the processor
`308 to receive data representing a set of beacons observed by
`a computing device. The beacons are located within a first
`geographic area. The filter component 318, when executed by
`the processor, causes the processor to select no more than a
`first predefined quantity of the beacons based on the coverage
`areas of the beacons. For example, the filter component 318
`may select seven of the beacons having the smallest coverage
`areas. In some embodiments, a small coverage area for one of
`35
`the beacons represents a high degree of accuracy or confi
`dence in the beacon reference data 314 corresponding to the
`beacon.
`
`15
`
`30
`
`6
`The clique component 320, when executed by the proces
`Sor, causes the processor to identify no more than a second
`predefined quantity of the selected beacons each having over
`lapping coverage areas (e.g., where each of the identified
`beacons has a coverage area that overlaps with the coverage
`areas of each of the other identified beacons). For example,
`the clique component 320 may select three of the beacons
`with overlapping coverage areas to enable triangulation. To
`reduce the computation complexity, some embodiments stop
`searching for additional or larger cliques once a clique of
`three beacons has been found.
`The inference component 322, when executed by the pro
`cessor, causes the processor to define the second geographic
`area based on the beaconsidentified by the clique component
`320, and based on the beacon reference data 314 and coverage
`area data 315.
`Referring next to FIG. 5, an exemplary block diagram
`illustrates a beacon fingerprint having a maximally complete
`set of beacons. In the example of FIG. 5, a device such as
`device 302 has observed beacons b,b,b,b,bs, be, and b,
`that constitute the beacon fingerprint. The circles around each
`of the beacons represent the coverage areas associated with
`the beacons.
`There are two cliques in FIG. 5, one is maximum and the
`other is maximal. The maximum clique includes beacons b,
`b2 b, and be, while the maximal clique includes beacons b,
`b. and b.
`An example for selecting beacons for determining a loca
`tion of the device 302 is next described with reference to FIG.
`5.
`An exemplary algorithm, flow, or pseudo code for imple
`menting aspects of the disclosure as computer-executable
`instructions is next described. In the example algorithm
`below, the input is a beacon fingerprint {b, b, ..., b}. The
`output is a circle C centered at c with radius R. An exemplary
`pre-condition of the algorithm is that for each i, if b, is
`detected at y, then y is within C, with 95% probability. As a
`result, the true position x of the device is in C with 95%
`probability.
`
`1.
`
`2.
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 11 of 15 PageID #: 378
`
`1.3.
`
`2.2.
`2.3.
`2.4.
`
`2.4.2.
`
`Eliminate beacon outliers, based on the typical coverage area of
`beacon
`, by
`Find the median m of{b, b, ...
`1.1.
`Filter by tile membership
`1.2.
`1.2.1. Remove beacons not in the tile for minor in its neighboring
`tiles, if applicable
`Filter by distance to the median
`1.3.1. Remove b, such that Dist(b, m) > max beacon distance
`(e.g. 500 meters for Wi-Fi beacon, 20 kilometers for cellular
`beacon
`Select beacons for inference, using 95% confidence circles
`{b1, b2,..., b} are the beacons remaining from operation 1 above
`2.1.
`sorted by radius in non-decreasing order (r, s , for all i <j)
`If K = 0 return “Location not found' (beacons are too dispersed)
`If K = 1, set C to C1 (e.g., c = b, R = r)
`If K is greater than 1 (e.g., at least two beacons)
`Model the beacon set as an undirected graph, where each
`2.4.1.
`node is a beacon and two nodes are connected if their circles
`intersect.
`Find all maximally complete components or cliques (e.g.,
`maximally complete subgraphs in which all pairs of nodes are
`directly connected). The circles in a complete component
`intersect on at least one point.
`2.4.2.1. Initialize G = {G = G(b)={{b}}; S = {b-..... bk}
`2.4.2.2. For each b, in S, check component G, in G, from lower
`indexed to higher indexed, if{b}UG, is still a complete
`component
`2.4.2.2.1.
`
`2.4.2.2.2.
`
`If so, add b, to first G,({b}UG, is a complete
`component
`If no component G, exists in G such that
`{C}UG, is a complete component, then start a new
`component G.-G(b)={b} and append it to G
`
`

`

`US 8,618,984 B2
`
`7
`
`-continued
`
`2.4-3. If there is more than one complete component in G, select
`the component with the maximum number of nodes; select the
`Smallest indexed component if there is a tie in the number of
`nodes
`Infer the circle, using the complete component selected in operation 1
`above
`3.1.
`
`3.
`
`3.2.
`3.3.
`
`3.4.
`
`Kb1, b2,..., b} are the L beacons in the selected complete
`component from operation 1 above and assume the beacons are
`sorted by radius in non-decreasing order (r, s , for all i <)
`If L is 1 (e.g., only one beacon), set C to C1 (e.g., c = b, R = r)
`If L is 2 (e.g., only two beacons), set C = Jointcircle(C1, C2)
`3.3.1. If Dist(b,b)s Sqrt{r^-r) set C = C,
`3.3.2. else
`Find the two intersetion points P and P
`3.3.2.1.
`Set c to the intersetion point of Line(P1, P2) and
`3.3.2.2.
`Line(b1, b)
`3.3.2.3. Set R to Max(Dist(c., P1), 50 meters)
`If Le 3 (e.g., there are more than two beacons)
`3.4.1. Select the first 3 beacons with the smallest radius or
`strongest signal strength
`3.4.1.1. Check C1, C2, C3 for pair-wise inclusion; if found,
`remove the containing circle and go to operation 3.3 with
`the remaining two circles; otherwise continue
`3.4.1.2. Check if (Ci?nC, CCs) or (C?hCCC) or (C-?hCC
`C), if so, remove the containing circle and go to 3.3 with
`the remaining two circles; else continue
`3.4.1.3. If(CCCUCs), set C to C; otherwise continue
`3.4.1-4. Find the three intersection points Pi, P., Ps
`3.4.1.5. Set c to the center of circumcircle (e.g., c is
`equidistant to P1, P2, P3)
`3.4.1.6. Set R to Max(Dist(c., P1), 50 meters)
`
`In the above example, the minimum radius is set to 50
`meters to reflect a typical radius since it is possible that the
`calculated R value could be less than 50.
`
`Additional Examples
`
`Another exemplary algorithm, flow, or pseudo code for
`implementing aspects of the disclosure as computer-execut
`able instructions is next described. In this example, the quan
`tity of beacons analyzed is limited to seven to reflect one
`
`30 serving cell and six neighboring cells. Further, the maximum
`clique size is limited to three to enable triangulation yet avoid
`unnecessary computation. In the example algorithm below,
`the input is a beacon fingerprint {b, b, ..., by}. The output
`is a circle C centered at c with radius R. An exemplary
`pre-condition of the algorithm is that for each i, if b, is
`detected at y, then y is within C, with 95% probability. As a
`result, the true position X of the device is in C with 95%
`probability.
`
`35
`
`1.
`
`Case 2:21-cv-00072-JRG Document 25-3 Filed 04/23/21 Page 12 of 15 PageID #: 379
`
`1.3.
`
`Eliminate beacon outliers, based on the typical coverage area of
`beacon
`1.1.
`Find the median m of{b1, b2,..., by}
`1.2.
`Filter by tile membership
`1.2.1. Remove beacons not in the tile form nor in its neighboring
`tiles, if applicable
`Filter by distance to the median
`1.3.1. Remove b, such that Dist(b, m) > max beacon distance
`(e.g. 500 meters for Wi-Fi beacon, 20 kilometers for cellular
`beacon)
`Select beacons for inference
`{b1, b2,...,b) are the beacons remaining from operation 1 sorted
`2.1.
`by radius in non-decreasing order (r, sr, for all i <)
`2.1.1. If K > 7, set K = 7 (e.g., truncate to the first 7 beacons)
`If K = 0 return “Location not found (e.g., beacons are too
`dispersed)
`If K = 1, set C to C1 (e.g., c = b, Rc = r)
`If 2s. Ks 7
`2.4.1. Model the beacon set as an undirected graph, where each
`node is a beacon and two nodes are connected if their circles
`intersect.
`2.4.2. For all 3-tuples {b,b,b}, i < j<k
`2.4.2.1. If{b,b,b} is a complete subgraph (or 3-clique), go to
`operation 3 with {b,b,b); otherwise continue
`2.4.3. If no 3-clique found, for all pair {bib,}, i <
`2.4.3.1. If{b,b,} is a complete subgraph (or 2-clique), go to
`operation 3 with {b,b,}; otherwise continue
`2.4.4. If no 2-clique or 3-clique found, go to operation 3 with {b}
`
`2.2.
`
`23.
`2.4.
`
`

`

`US 8,618,984 B2
`
`10
`
`9
`-continued
`
`3.
`
`3.4.
`
`Infer the circle, using the beacons selected from operation 2 (at most 3
`beacons selected)
`3.1.
`Kb1, ..., b} are the L beacons selected and sorted by radius in non
`decreasing order (r, s , for all i <j)
`3.2.
`If L = 1, set C to C (e.g., c = b, R = r)
`If L = 2, then C = JointCircle(CC)
`3.3.
`3.3.1. If Dist(b,b)s Sqrt{r^-r) set C = C,
`3.3.2. else
`3.3.2.1. Find the two intersection points P and P2.
`3.3.2.2. Set c to the intersection point of Line(P1, P2) and
`Line(b,b)
`3.3.2.3. Set R to Max(Dist(c., P1), 50 meters)
`If L = 3
`3.4.1.1. Check C1, C2, C3 for pair-wise inclusion; if found,
`remove the containing circle and go to operation 3.3 with
`the remaining two circles; otherwise continue
`3.4.1.2. Check if (C1 ?hCCC) or (C?hCCC) or (Ca?hCC
`C), if so, remove the containing circle and go to 3.3 with
`the remaining two circles; else continue
`3.4.1.3. Check if (CCCUCs), if so set C to C; otherwise
`continue
`3.4.14. Find the three intersection points P1, P2, Ps
`3.4.1.5. Set c to the center of circumcircle (equal-distance
`point to P1, P2, Ps)
`3.4.1.6. Set R to Max(Dist(c., P1), 50 meters)
`
`25
`
`35
`
`40
`
`In the above example, the minimum radius is set to 50
`meters to reflect a typical radius since it is possible that the
`calculated R value could be less than 50.
`In some embodiments, the operations illustrated in FIG. 4
`executed on a mobile device enabled with BLUETOOTH
`30
`brand communication technology. Application programs
`such as gaming application programs executing on the mo