`Evans et al.
`
`I 1111111111111111 11111 lllll lllll 111111111111111 1111111111 1111111111 11111111
`US006327535Bl
`US 6,327,535 Bl
`Dec. 4, 2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) LOCATION BEACONING METHODS AND
`SYSTEMS
`
`(74) Attorney, Agent, or Firm-Lee & Hayes, PLLC
`
`(57)
`
`ABSTRACT
`
`(75)
`
`Inventors: Stephen S. Evans, Redmond; Gopal
`Parupudi, Issaquah; Burdette J.
`Holtgrewe, Bellevue; Edward F. Reus,
`Woodinville; Gregory Burns, Seattle,
`all of WA (US)
`
`(73) Assignee: Microsoft 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 O days.
`
`(21) Appl. No.: 09/543,646
`
`(22) Filed:
`
`Apr. 5, 2000
`
`Int. Cl.7 ...................................................... G06F 17/10
`(51)
`(52) U.S. Cl. .......................... 701/300; 701/207; 701/214;
`701/216; 342/357.09
`(58) Field of Search ..................................... 701/200, 201,
`701/202, 206, 207, 214, 216, 300; 379/220,
`221; 342/357.01, 357.02, 357.08, 357.09
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,499,032 * 3/1996 Kelley et al. ........................ 701/207
`5,806,017 * 9/1998 Hancock .............................. 701/209
`5,917,911 * 6/1999 Dabbish et al.
`....................... 380/21
`6,028,551 * 2/2000 Schoen et al. .................. 342/357.16
`6,216,087 * 4/2001 Want et al.
`.......................... 701/207
`* cited by examiner
`
`Primary Examiner-William A. Cuchlinski, Jr.
`Assistant Examiner-Gertrude Arthur
`
`Context-aware computing systems and methods are
`described. In particular embodiments, location aware sys(cid:173)
`tems and methods are described. In the described
`embodiments, hierarchical tree structures are utilized to
`ascertain a device context or location. The tree structures can
`be stored on or accessible to mobile computing devices so
`that the devices can determine their own particular context
`or location. In one embodiment, one of the tree structures
`comprises a Master World tree structure that contains nodes
`that represent geographical divisions of the Earth. Another
`of the tree structures can comprise a so-called Secondary
`World that contains nodes that represent physical or logical
`entities that are organization or company specific views of
`the world. A computing device can automatically determine
`its context or location by ascertaining a node on one or more
`of the tree structures and then traversing the tree structure to
`ascertain the complete context. A unique device architecture
`is described that permits context aware computing. The
`device architecture comprises a context service module, a
`common interface, and one or more context providers. The
`context providers provide information, through the common
`interface, that pertains to the context of a device, and the
`context service module processes the information to device
`the device's context. An application program interface
`(API)/events layer is provided through which various appli(cid:173)
`cations can call the device to ascertain the device's location
`so that location dependent goods or services can be ren(cid:173)
`dered. A privacy manager is also provided in some embodi(cid:173)
`ments to enforce privacy thereby protecting the granularity
`of the location information that is provided to the applica(cid:173)
`tions. In addition, unique location beacons are described that
`transmit information that can be used by the computing
`device to ascertain its location.
`
`53 Claims, 9 Drawing Sheets
`
`172
`
`142
`
`Processing Unit
`
`174
`
`:(RAM
`
`Operating
`System 158
`
`Application
`Programs160
`
`Video
`Adapter
`
`Other Program )
`Modules 162)
`
`( Program DaiJ
`
`: .• ··: :·:·:: :·::·:··· .. :·:·:···::·:::.: _·._ ·- ! '. .. : • • • - -·- - - -·-·
`
`Operating
`S stem
`
`Other
`Modules
`160
`
`Program
`Data
`162
`
`164
`
`Keyboard
`
`i'\pplication
`Pro rams
`
`Exhibit 1007
`IPR2022-00426
`Page 1 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`
`'"""' 0 ....,
`~ ....
`rF.J. =(cid:173)~
`
`'"""'
`0
`0
`N
`~,J;..
`ri
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`178
`
`~OI
`
`Proarams
`' 'Application
`
`160
`
`Network
`
`Modem Wide Area· •(cid:173)
`
`Keyboard
`
`164
`
`I gsa,c182') iO'
`
`,:::::,,,c
`
`176
`184
`
`146
`
`-----·-------·-·---·-------·-·-·-·-------·-·-·-·-·-· .· ....... -·---·-------
`
`·-·-·-·-•-·.;'
`
`·-.
`
`Interface
`/Mouse
`Keyboard
`
`SCSI Interface
`
`.....
`
`172
`
`1
`'JUJ,
`! ~1D
`
`!
`
`170
`
`Bus
`
`136
`
`174
`
`I
`
`Processing Unit
`
`132
`
`130
`
`i
`
`1
`
`!
`·
`i
`!
`; ~-----;
`!
`i
`!
`·
`i (RA~x·-·-·--·-·-·------······1·4cf"·j
`142
`i
`)
`1 i (ROM)
`138 i
`1--c-~~~~1-1;!!!Q!Y!J_t;J4
`
`Programs 160
`Application
`
`System 158
`Operating
`
`BIOS
`
`:
`[ (
`
`i
`;
`;
`;
`;
`;
`;
`i
`;
`i
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`;
`
`i
`
`Exhibit 1007
`IPR2022-00426
`Page 2 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`N
`~ ....
`'JJ. =(cid:173)~
`
`'"""'
`0
`0
`N
`~,J;..
`ri
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`7'9, 2
`
`Rooms
`Floors
`Buildings
`Campuses
`Regions
`Divisions
`Company
`
`206
`
`~204
`
`_A_
`
`\
`\.
`',,
`
`Secondary World
`
`.....
`
`--- link
`
`Non-physical locations
`Public Places
`Road Intersections
`Postal Codes
`Populated Places
`Counties
`Area Codes
`States
`Time Zones
`Regions
`Countries
`Continents & Oceans
`Earth
`
`202 ------. ~ ~ 200
`
`Master World
`
`Exhibit 1007
`IPR2022-00426
`Page 3 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`~
`
`\0
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`'"""'
`0
`0
`N
`~,J;..
`ri
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`'Ju;, 3
`
`projector
`
`video
`
`room 1342
`Conference
`
`room 3173
`Conference
`
`2nd floor
`
`3rd floor
`
`Zip= 98052
`
`Building 24
`
`Building 26
`
`Redmond
`
`Way
`
`1 Microsoft
`
`Campus
`Redmond
`
`Washington
`
`United States
`
`Microsoft
`
`World
`
`~302
`
`World
`
`Secondary
`
`Master World
`
`300--...
`
`Exhibit 1007
`IPR2022-00426
`Page 4 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`~ ....
`'JJ. =-~
`
`,J;..
`
`'"""'
`0
`0
`N
`~,J;..
`
`~ ri
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`504
`
`502
`
`500
`
`7'9,5
`
`hierarchical tree structure
`
`Link one node to a node of another
`
`~'
`
`hierarchical tree structure
`
`Process information to define
`
`, '
`
`Receive input from a source
`
`7'9, 4
`
`402
`
`Traverse multiple nodes to determine
`
`context
`
`i
`
`structures
`
`400
`
`Access first/second hierarchical tree
`
`Exhibit 1007
`IPR2022-00426
`Page 5 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`Ul
`~ ....
`'JJ. =(cid:173)~
`
`'"""'
`0
`0
`N
`~,J;..
`ri
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`Information
`
`Source
`Context
`
`606
`
`Information
`
`Source
`Context
`
`606
`
`Information
`
`Source
`Context
`
`606
`
`604
`
`~~· ---
`
`.,,..,,,-Secondary
`
`Master/
`
`Context Providers
`
`Module
`
`Context Service
`
`602 ~ O
`
`e
`
`600 ~
`
`Computing Device O
`0
`
`7'9, 6
`
`Application
`
`608
`
`Application
`
`608
`
`Application
`
`oO
`
`0
`
`608
`
`Exhibit 1007
`IPR2022-00426
`Page 6 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`O'I
`
`'"""'
`0
`0
`N
`~,J;..
`ri
`~
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`-0
`a.>
`~
`
`'> e
`
`_J
`0
`(.)
`Cll
`:;:;
`0
`C
`D...
`
`606
`
`/
`
`Providers
`
`Future
`
`[ 802.11 AP r 606
`
`Beacon
`Location
`
`v-606
`
`)
`
`]
`
`GPS
`
`6067
`
`Cell ID
`
`606 l Cache
`
`606 ~ Mobile Phone
`
`Manager
`Privacy
`
`704
`
`606
`
`700
`
`602
`
`702
`
`IP/Subnet
`
`Location UI
`
`Location Provider Interface
`
`Location Service Module
`
`Events
`
`Application Program Interface/
`
`606
`
`0 u
`C
`>
`a.>
`'§
`0
`C
`
`_J
`0
`(.)
`Cll
`:;:;
`0
`C
`
`0 u
`E
`::::, a.
`:;:;
`C
`Ol
`
`'> a.> o
`
`(.)
`a.>
`
`7'9, 7
`
`Applications
`
`Disc.
`
`Service
`
`Outlook
`
`608
`
`Site
`Web
`
`608
`
`706
`
`608
`
`600
`
`708
`
`Exhibit 1007
`IPR2022-00426
`Page 7 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`-..J
`~ ....
`'JJ. =(cid:173)~
`
`'"""'
`0
`0
`N
`~,J;..
`~ ri
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`Update current context
`
`818
`
`from context providers
`upon context information
`Determine context based
`
`es
`
`y
`
`predefined level of trust
`
`,
`
`Select context providers with~
`
`814
`
`context appears to be correct
`
`Determine whether current
`
`context providers
`
`Order active and valid
`
`7'9-K 810
`
`808
`
`804
`
`current context over time
`Decrease confidence in
`806\
`
`--------~
`
`valid context providers
`
`Determine current active and
`
`---------
`
`802
`
`Get current context
`
`800
`
`Exhibit 1007
`IPR2022-00426
`Page 8 of 26
`
`
`
`i,-
`~
`(It
`~
`11.
`-...,l
`N
`~
`O'I
`rJ'J.
`e
`
`\0
`0 ....,
`00
`~ ....
`'JJ. =-
`
`~
`
`'"""'
`0
`0
`N
`~,J;..
`~ ri
`~
`
`=
`......
`~
`......
`~
`~
`•
`r:JJ.
`d •
`
`7'9-10
`
`one or more applications
`
`Receive context queries from
`
`mobile computing device
`Determine context of a
`
`nodes in a hierarchical tree
`
`Assign privacy levels to
`
`904 ----------I Receive calls from one or l
`
`more applications
`
`1006 ----------
`
`of the device
`
`1004
`
`ascertain the current context
`
`and with the device to
`
`----------
`
`I Process the information on
`
`902
`
`1002 ----------
`
`of the device
`
`level
`
`has a corresponding privacy
`associated with a node that
`
`corresponding privacy level
`
`find a node with a
`
`1012 l Return context information
`
`Traverse hierarchical tree to
`
`1010
`
`7'9-9
`
`device's context
`
`information that pertains to
`
`Supply application with
`
`906 ----------
`
`application(s)
`
`associated with the
`
`1008~ Determine a privacy level
`
`Define privacy levels
`
`1000
`
`pertains to a current context
`
`Receive information that
`
`900 ----------
`
`Exhibit 1007
`IPR2022-00426
`Page 9 of 26
`
`
`
`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 9 of 9
`
`US 6,327,535 Bl
`
`en
`I...
`.....
`Cl)
`C
`0 a..
`"O co
`0
`..--..
`C
`,,__J
`_J 0::: Cl) 3::
`0::: :::)
`I... 0
`:::) -.a 0
`-0 co Cl)
`0
`-
`C "O
`:::) 0) 0
`w _J · -
`-
`._, ._, (/) ()
`
`(
`
`©o
`
`O—
`—
`
`C
`0
`() co
`Cl)
`co
`
`Exhibit 1007
`IPR2022-00426
`Page 10 of 26
`
`
`
`US 6,327,535 Bl
`
`5
`
`2
`There is an unsolved need to be able to create context(cid:173)
`aware computing in which computing devices can partici(cid:173)
`pate in their particular context. In specific circumstances,
`there are needs to provide relational position awareness
`among physical locations in both public and private views of
`the world. To date, however, there is no one standardized
`view of the world that would unlock the potential of context(cid:173)
`aware computing. Context-aware computing is much more
`than just position awareness-although this is a very big
`10 field in and of itself.
`This invention arose out of concerns associated with
`developing a standardized, context-aware infrastructure and
`related systems to unlock the potential of context-aware
`computing.
`
`1
`LOCATION BEACONING METHODS AND
`SYSTEMS
`TECHNICAL FIELD
`This invention relates to generally to the area of context-
`aware computing or ubiquitous computing.
`BACKGROUND
`The World Wide Web (WWW) was created to make
`content available from any source in any location around the
`world. Users of the Web are able to generally access a
`seemingly infinite number of resources via the Web. The
`Web has been highly successful in this regard. Yet, with the
`evolution of the Web, certain needs remain largely unmet.
`Specifically, people continue to have a need to access
`information that has a contextual aspect to it. That is, often 15
`times, individuals will find themselves in a computing
`environment that carries with it a certain context. Yet, the
`context of the environment cannot be easily incorporated
`into the present computing environment. As an example,
`consider the context of location. People generally have a 20
`need to access information, data, resources and the like, that
`have geographic dimensions to them. For example, indi(cid:173)
`viduals may desire to take advantage of services or products
`that are close in proximity to where they currently are
`located. In this regard, it is desirable to understand the 25
`individual's contextual location so that services, goods and
`the like can be made available to the individual. As "eCom(cid:173)
`merce" continues to grow in importance, the necessity of
`bringing people, places, services and goods together in an
`efficient manner will become critically important.
`To date, many attempts have been made to bring people,
`places, services and goods together. These various attempts
`have generally approached the problem from different direc(cid:173)
`tions in an often times incompatible manner. As an example,
`consider the context of location. Some services have 35
`attempted to bring people and services together by defining
`large databases that maintain information about the services.
`For example, a list of restaurants may be maintained in a
`web accessible database where each restaurant is associated
`with a zip code in which the restaurant is located. When a 40
`user desires to locate a particular restaurant, they might
`simply enter the zip code where they are located to see a list
`of corresponding restaurants in that zip code. From the list
`of restaurants, they might be able to select one or two
`restaurants of interest. This approach is undesirable for a 45
`number of reasons. First, the operation of the system is
`dependent upon a central server that is responsible for
`receiving user queries and executing the queries to return the
`information to the user. In the event the server fails, so too
`does the service. In addition, this particular service might be 50
`suited to finding restaurants, but possibly not other busi(cid:173)
`nesses. In addition, the granularity with which the results are
`returned to the user may foist some of the search burden on
`the user (i.e. the user gets a list of restaurants in a nearby zip
`code, but has to further explore the list to select which ones
`are of interest). Further, the list of restaurants may include
`some restaurants that are blocked by some type of a physical
`barrier (i.e. a river, mountain, etc.) that makes the distance,
`as the crow flies, unroutable.
`Providers of services and products want to be connected
`to nearby end-users. End-users want to consume these
`services and goods at the closest and most convenient
`location. Acquiring the services of a dentist or a plumber that
`lives somewhere "out on the net" is not appropriate if you
`need them to fill a cavity or unclog a sink. Looking for the
`nearest hotdog while in a stadium requires you to stay in the
`stadium.
`
`SUMMARY
`
`30
`
`Context aware computing systems and methods are
`described. In the described embodiment, one or more hier(cid:173)
`archical tree structures are defined that uniquely identify
`geographical divisions of the Earth and/or physical or logi(cid:173)
`cal entities. Each tree has multiple nodes and at least one
`node from each tree is linked. Goods and services can be
`associated with individual nodes on the tree, the nodes
`providing a universal reference when attempting to locate or
`consume the goods or services.
`In one embodiment, a computing device (such as a
`stationary or mobile computing device) has access to one or
`more of the tree structures and can utilize the tree structures
`to ascertain its current context. The device determines its
`context by traversing one or more of the tree structures to
`ascertain information that is associated with the individual
`nodes of the tree structure. In a particular embodiment, the
`context is the device location and the device is capable of
`autonomously determining its location within a Master
`World and one or more Secondary worlds. Once the com(cid:173)
`puting device has determined its location, it can then take
`part in location-dependent scenarios.
`In one embodiment a Master World is defined and is a
`hierarchical tree structure that represents a universally
`acceptable description of the world. One or more Secondary
`Worlds can be defined and constitute company- or
`organization- specific views of the world that link with the
`Master World. A Secondary World can describe the location
`tree of an organization.
`In one embodiment, a device architecture includes a
`common interface, a location service module, a plurality of
`location providers, and an application program interface
`(API) or events layer. Various location providers can call the
`common interface with location information that is pro(cid:173)
`cessed by the location service module to ascertain the
`device's current location. The location providers provide
`hints about the current location and the location service
`module turns the hints into a nodal location on one or more
`55 of the hierarchical tree structures. The location service then
`traverses one or more of the tree structures to ascertain a
`complete device location. Various applications can call the
`API layer to ascertain location information from the location
`service module. By knowing where a device is located
`60 within a hierarchical structure, the applications can present
`location-dependent goods or services to the user. Thus, a
`user is able to actively participate in their current computing
`environment.
`In other embodiments, the location service module is able
`65 to determine, to a degree of certainty, the location of the
`device. It does so through the use of confidence and accu(cid:173)
`racy parameters that are assigned to the information that is
`
`Exhibit 1007
`IPR2022-00426
`Page 11 of 26
`
`
`
`US 6,327,535 Bl
`
`5
`
`3
`provided by the location providers. Additionally, a trust
`parameter can be assigned by the location service module to
`the location providers and provides a measure of the trust
`that is associated with a particular location provider. The
`location service module can then consider all of the param(cid:173)
`eters in deciding which location information to use and how
`to use it in determining a device location.
`In another embodiment, privacy issues are addressed by a
`privacy manager that functions to modulate the information
`that is provided to the various applications as a function of 10
`the applications' identities and security policies on the
`device.
`In yet another embodiment, a unique beacon provider is
`described. A beacon can be located in various places and
`transmits context information that (in the case of location
`information) can be directly used to ascertain the device's
`location relative to a tree structure node. This provides direct
`information about the device's location within the defined
`hierarchical infrastructure.
`
`4
`to determine the relative location of a place anywhere in the
`world and at any definable granularity.
`Once an individual's location or a place an individual is
`interested in is determined, various services that reference
`the location can be offered to the individual based on their
`location. That is, value is provided by the Master World
`model in the ability to tie services to nodal locations in the
`Master World.
`Building on this concept, two additional concepts add
`value-the concept of so-called Secondary Worlds and a
`"geozone."
`A Secondary World is a powerful computing mechanism
`whereby individual entities (such as businesses or
`organizations) can define their own particular worlds that
`15 need not necessarily conform to the Master World view of
`the world. That is, while the Master World is essentially a
`physical hierarchical representation of the world, the Sec(cid:173)
`ondary Worlds can be physical and/or logical representa(cid:173)
`tions of each individual entities' world view. One particu-
`20 larly useful aspect of the Secondary World is that it links, at
`at least one point, into the Master World. Thus, within any
`Secondary World, a user's location not only within the
`Secondary World, but the Master World as well can be
`determined. Various services can be attached to the nodes of
`25 the Secondary World. Based upon a user's calculated
`position, these various services that are associated with
`Secondary World nodes can be offered to the user. In
`addition, because the user's context is determined relative to
`the Master World, other services that may not be associated
`30 with a particular Secondary World can be offered.
`A geozone is essentially a spatial indexing mechanism by
`which the Master World is subdivided into individual zones.
`In the described embodiment, the zones are subdivided
`through the use of a quadtree algorithm that is dependent on
`35 a density function ( although many other spatial index
`approaches can also be used). Once a desired density level
`is achieved ( density might be defined in terms of points of
`interest per zone), each node on the Master World is
`assigned a particular geozone. Geozones enable proximity
`40 calculations to be computed in a fast and straight forward
`manner.
`A useful aspect of the Master and Secondary Worlds are
`that they are "reachable" from various computing devices
`such as stationary (i.e. desktop devices) or mobile comput(cid:173)
`ing devices (i.e. cell phones, laptops etc.). That is, the Master
`World ( or at least a portion of it) and one or more Secondary
`Worlds can be either locally maintained on the computing
`device, or accessed, e.g. via the Web or some other
`mechanism, so that a user can derive their context. For
`50 example, the Secondary World can be downloaded onto the
`computing device so that a user can derive their context
`within the Secondary World. Once a user's context is
`determined from the Master World and one or more Sec(cid:173)
`ondary Worlds, a various robust collection of context-aware
`55 solutions become available to the user. For example, specific
`Secondary World services can be offered or Master World
`services can be offered. Additionally, services from other
`Secondary Worlds might also be offered since the user's
`location may be known ( or made known) to these other
`60 Secondary Worlds. In this way, the Master World can link
`two or more Secondary Worlds together.
`Another aspect is that the described embodiments harness
`the computing power of each computing device in deter(cid:173)
`mining the device's location. Here, by virtue of having the
`65 Master World and one or more Secondary Worlds reachable
`by the device (and possibly locally maintained on the
`device), the device itself determines its own context.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a diagram of an exemplary computing device
`that can be used in accordance with the described embodi(cid:173)
`ments.
`FIG. 2 is a conceptual diagram of an exemplary Master
`World and an exemplary Secondary World in accordance
`with the described embodiment.
`FIG. 3 is an exemplary specific view of a Master World
`and a Secondary World and their relation to one another.
`FIG. 4 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`FIG. 5 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`FIG. 6 is a high level diagram of an exemplary computing
`device architecture.
`FIG. 7 is a somewhat more specific view of an exemplary
`computing device architecture.
`FIG. 8 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`FIG. 9 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`FIG. 10 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`FIG. 11 is a side elevational view of an exemplary
`location beacon in accordance with one embodiment.
`
`DETAILED DESCRIPTION
`
`Overview
`To provide a standardized solution, embodiments
`described just below provide a uniform definition of the
`world. The uniform definition is defined in terms of a
`hierarchical tree of nodes, where each node represents some
`aspect of the world. Each node is connected to at least one
`other node by a branch. An exemplary classification of nodes
`takes place on a physical level ( e.g. physical locations such
`as political entities, infrastructure entities and public places),
`as well as a non-physical level (e.g. military APOs). This
`hierarchical nodal structure is referred to as the Master
`World, and is a standardized view worldwide. Each node of
`the Master World has various attributes associated with it
`that assist in context-aware computing. Exemplary attributes
`include a unique ID, name, geographic entity class, latitude/
`longitude, relative importance, contextual parents to name
`just a few. The Master World is useful because it can be used
`
`45
`
`Exhibit 1007
`IPR2022-00426
`Page 12 of 26
`
`
`
`US 6,327,535 Bl
`
`10
`
`5
`One embodiment provides a client side device that is
`configured to utilize the context-aware structures that are
`discussed above, i.e. the Master and one or more Secondary
`Worlds. The Master World or a portion thereof can be locally
`available on the device or can be accessible at another
`location, e.g. via the Web. In this embodiment, the client
`device has a location service embodied thereon. The
`described location service is a software module that can
`determine the location of the device and can answer queries
`from various applications ( either executing on the device or
`off the device). The location service determines the location
`of the device by using the Master World and one or more
`Secondary Worlds. The applications query the location ser(cid:173)
`vice through one or more Application Program Interfaces
`(APis) or Events to get location information that is used by 15
`the applications to render a service.
`The location service makes use of one or more location
`providers that convey information to the device. This infor(cid:173)
`mation can be information that is specific to the location
`provider, or can be information that can be mapped directly 20
`into a node of the Master World or Secondary Worlds.
`Exemplary location providers can include Global Position(cid:173)
`ing Service (GPS) providers, cell phone providers (cell
`providers), Bluetooth providers, a user interface provider
`and the like. The location providers provide information that 25
`gives some aspect of a device's current location. This
`information is used by the location service to ascertain the
`location of the device.
`One particularly advantageous feature of the client device
`is a standard or common location provider interface. The
`location provider interface enables the various location
`providers to provide information to the location service so
`that the location service can use the information to deter(cid:173)
`mine its location. Essentially, the multiple location provider
`interface is a common interface that enables multiple dif(cid:173)
`ferent location providers to provide location information ( or
`hints) about location to a location service that is on a device.
`The location providers can provide the location information
`constantly, at intervals, or when polled by the device. The
`location information can be provided with confidence and 40
`accuracy estimates to enable the location service to evaluate
`the relative quality of the information before it is used. The
`various providers also have the ability to self-monitor them(cid:173)
`selves which assists in the providers' ability to intelligently
`convey information to the location service. By having a 45
`common interface, the collection of location providers is
`dynamically extensible-that is location providers can be
`added or removed from the collection of location providers
`without any interference of the functionality performed by
`the location service or device. The location providers can be 50
`added or removed while the device is operating. This is
`particularly useful in accommodating location providers that
`are developed in the future. In this particular embodiment,
`two levels of abstraction are provided i.e. (1) the provider
`interface that receives information from the location pro- 55
`viders and (2) the APl/events layer that enables applications
`to get at the various information.
`One focus of this embodiment is a device that can collect
`context information (e.g. location information) from a vari(cid:173)
`ety of different sources, determine the device's current
`context from that information, and provide the current
`context at some level to one or more applications that can
`use the device's context to render a service or enable the
`device to participate in its context environment.
`In the described embodiment, the device receives location
`information or hints about its location. This information is
`collated and mapped by the location service into a node in
`
`6
`the Master World and/or Secondary World. The hierarchical
`trees can then be traversed to determine the device's accu(cid:173)
`rate location in both the Secondary World and the Master
`World. At this point, the device has determined its context.
`5 The information that is collected can be subject to arbitration
`to ensure that only highly trusted information is used to
`determine context. The location information can be cached
`to provide "current location information" which, for a defin(cid:173)
`able period of time will be accurate to some degree. Thus,
`if for some reason other location providers are unavailable,
`the cache can be used to ascertain location.
`Once a device's location is determined, the device can
`apply a security policy to the information. Once this is done,
`the device can begin to answer queries from various appli(cid:173)
`cations.
`One aspect of the described embodiment is a "favorite
`locations" aspect in which the device can be automatically
`configured, when it determines its context, so that it can
`adjust to the different locations.
`Further, various types of location providers can convey
`different types of information. For example, a so-called "thin
`provider" provides location information that is translated by
`the location service into the appropriate node information. A
`so-called "thick provider" includes logic that takes location
`information and provides it in a form that can map directly
`into the Master World or Secondary World.
`In another embodiment location translation services are
`provided that are directed to determining, as accurately as
`possible, the context or location of the device. In this
`30 embodiment, information is received from the various loca(cid:173)
`tion providers. This information includes location, accuracy
`and confidence ( all of which are provided by the location
`provider), trust (which is assigned to a location provider by
`the device or a user) and a timestamp (which helps to age the
`35 location information). The location translation processing
`involves determining which of the location providers are
`valid and active. The location providers can be ranked in
`accordance with the confidence and trust levels. This defines
`an ordered list of location providers. Provision is made for
`a situation in which all of the location providers may go
`inactive. If so, a "current location" is used as a location
`provider whose confidence decreases over time.
`In the event that information from two or more of the
`location providers conflicts, then measures can be taken to
`use information for which there is a higher level of trust. The
`information that is provided by all of the location providers
`(assuming no conflict) can then be used to determine a tree
`structure and a node's entity ID (EID). The tree might be the
`Master World and the EID is a node on the Master World.
`The tree might also be a Secondary World and the EID ( or
`location unique indentifier or "LUID") is a node on the
`Secondary World. Once this information is collected, com(cid:173)
`plete location information can be determined by simply
`traversing the tree(s). Once a device's location is
`determined, a cache can be updated with the current location
`(including a time stamp).
`In another embodiment, privacy issues in the context(cid:173)
`aware computing environment are addressed. In this
`embodiment, the location service has acquired location
`60 information that pertains to the location of a particular
`device. A privacy manager determines what level of infor(cid:173)
`mation to provide to applications that might request the
`information. The privacy manager can reside on the com(cid:173)
`puting device itself, or can be proxied by a trusted third
`65 party.
`According to this embodiment, a scale of privacy levels
`are defined. Each level is defined to include more or less
`
`Exhibit 1007
`IPR2022-00426
`Page 13 of 26
`
`
`
`US 6,327,535 Bl
`
`7
`specific information about the location of a particular
`device. A user is abl