a2) United States Patent
`US 6,327,535 B1
`(10) Patent No.:
`Dec. 4, 2001
`(45) Date of Patent:
`Evanset al.
`
`US006327535B1
`
`(54) LOCATION BEACONING METHODS AND
`SYSTEMS
`
`(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
`US.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/543,646
`
`(22) Filed:
`Apr. 5, 2000
`CSV) TBs C0 ne eeccesccsseessesesseeseeseeceecccenene GO06F 17/10
`(52) U.S. CU. ceececssssssssssensen 701/300; 701/207; 701/214;
`701/216; 342/357.09
`(58) Field of Search 0...eee 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 *
`5,806,017 *
`5,917,911 *
`6,028,551 *
`6,216,087 *
`
`3/1996 Kelley et al. wu 701/207
`9/1998 Hancock .......
`701/209
`
`oe 380/21
`6/1999 Dabbish et al.
`2/2000 Schoenetal. .
`.. 342/357.16
`
`4/2001 Want et al. ou. 701/207
`
`* cited by examiner
`
`Primary Examiner—Wilham A. Cuchlinski, Jr.
`Assistant Examiner—Gertrude Arthur
`
`(74) Attorney, Agent, or Firm—Lee & Hayes, PLLC
`
`(57)
`
`ABSTRACT
`
`Context-aware computing systems and methods are
`described. In particular embodiments, location aware sys-
`tems and methods are described.
`In the described
`embodiments, hierarchical
`tree structures are utilized to
`ascertain a device contextor 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 Worldtree 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 companyspecific views of
`the world. A computing device can automatically determine
`ils 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-
`cations can call the deviceto ascertain the device’s location
`so that location dependent goods or services can be ren-
`dered. A privacy manageris also provided in some embodi-
`ments to enforce privacy thereby protecting the granularity
`of the location information that is provided to the applica-
`tions. In addition, unique location beaconsare described that
`transmit
`information that can be used by the computing
`device to ascertain its location.
`
`53 Claims, 9 Drawing Sheets
`
`
`
`
`
`Local Area
`Interface
`Keyboard
`Network
`
`/Mouse
`| |(Other Program
`
`
`i
`Modules 1627
`
`
`
`
`
`Program Data
`|
`
`
`
`
`Network
`160
`
`Other
`Program
`
` Operating|Application
`
`
`Application
`
`System,|Programs,|Module: Data
`
`
`Programs
`Keyboard
`160
`162
`158
`164
`
`L.
`
`° ‘
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0001
`EXHIBIT 1026 - PAGE 0001
`
`Application
`Programs160
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 1 of 9
`
`US 6,327,535 B1
`
`cd
`L
`
`
`—Srll
`
`
`
`
`
`Bally|2907]
`
`
`
` |sHOMION=__|eauyopign,wopon
`
`pieoqhkey
`
`OS8PlA
`
`Jaydepy
`
`
`
`yup)Buissesoig
`
`sng
`
`OLt
`
`9e1
`
`paeogkoy
`
`esnoywy/
`
`Soea}U|
`
`
`
`eoeyeWUlISOS
`
`sb
`
`
`
`8S!waysks
`
`Buyesedo
`
`
`
`O09}swesbog
`
`uoneaddy
`
`
`
`Z9lsajnpo;
`
`
`
`weibolgJauIO
`
`79}
`
`Begweibold
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0002
`EXHIBIT 1026 - PAGE 0002
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 2 of 9
`
`US 6,327,535 B1
`
`sesndweg
`
`sbulpling
`
`SUOISIAIG
`
`suoibey
`
`SLUOOY
`
`SJOO]4
`
`902
`
`Auedwos
`v0Z-*
`
`
`
`pDWOAAAlepuoses
`
`002—*c0¢
`
`DUOJeISe//\
`
`yes
`
`SUued90PSjusUI}UOD
`
`
`
`suoedo|jeoIsAyd-uON
`
`
`
`saoe|dpeyejndod
`
`
`
`SOPO4|e}SOq
`
`
`
`SUOI]OaSI9}U|PEOY
`
`
`
`SODE|dIGNd
`
`SOUOZOWI]
`
`soaljunog
`
`suoibey
`
`
`
`SapoDdeBay
`
`sanunoy
`
`SOJE}S
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0003
`EXHIBIT 1026 - PAGE 0003
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 3 of 9
`
`US 6,327,535 B1
`
`pzBuipling €/L€WOO
`
`400]|}PUG
`
`JOO}PIES
`
`gzBuipying
`
`O@PIA
`
`Joyos{oid
`
`90UBIBJU0D
`
`cvelWOO
`
`Q9UBIAJUO)
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0004
`EXHIBIT 1026 - PAGE 0004
`
`YOSOIOIV||
`
`Aen
`
`puowpey
`
`sndwey
`
`PHOM
`
`Aiepuoosas
`
`zoe—*POM
`PHOJ9}SeN
`
`‘—00¢
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 4 of 9
`
`US 6,327,535 B1
`
`00S
`
`
`
`
`
`ao/nos&WO!INdUIaAIaNey
`
`0O0r
`
`
`
`98d}|EOIYDIEIAIYPUODES/SI|SSBDOV
`
`
`
`
`
`seinjoniys
`
`
`
`
`
`
`
`vOsJ@yjoueJOBpou&O}BpoUBuOyUIT
`
`
`
`BINJONIS8d}|BOIYDJIEISIY
`
`ZOSBUIJAP0}UOMELUOJU!SSBDO1q
`
`
`
`
`ZOvQUILLIZJOP0}SAPOUBjCNINWssJoAes|
`
`
`
`aINJONYSGed]|BoIyouesalY
`
`}X9]U09
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0005
`EXHIBIT 1026 - PAGE 0005
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 5 of 9
`
`US 6,327,535 B1
`
`jea\sel\|
`
`009
`
`
`
`G12BIBUNA
`
`nok
`
` 6©
`
`NS809
`
`uonesiddy
`
`uonesddy
`
`\N809
`
`809
`
`Auepuosas~~
`SPHOAAae
`
`—3|NpoW
`Buyndwog
`©c09e90IA0q
`
`BOAIAS}X9]U0D
`
`
`
`UONEWJOJU| 909
`
`}x9}JU0D
`
`g0JNOS
`
`}xE]UON
`
`30/NOS
`
`UONEWUOJU
`
`UON}BWOJU|
`
`yx9]Uu04y
`
`901N0S
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0006
`EXHIBIT 1026 - PAGE 0006
`
`uoneojddy
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 6 of 9
`
`US 6,327,535 B1
`
`Aseaud
`
`SIOPIAOI UONEIO7 Jobeuey
`
`
`
`
`
`ucoeeg
`
`ai1i29
`
`aunin4
`
`
`
`suoneajddy
`BdIAlES
`
`‘SIG
`
`809
`
`AOORNO
`
`809
`
`Gem
`
`BUS
`
`902
`
`80 9
`
`
`
`
`
`
`
`jeoepaju)wesBolguoieayjddy
`
`
`
`
`
`BINPO|WBolesUOHeD07
`
`$}U9Aq
`
`
`
`
`
`
`
`GOBL9}U|JOPIACLUOIEI07
`
`
`
`
`
`dVL1°c08
`youqnsS/dl
`SJOPIAQId
`uo}e907]
`
`aU0UdaIIGOW
` Nuones07MS
`
`UOISIBAUOD UONEI07
`
`eoiaeq Bulyndwos
`
`009
`
`802
`
`oAloW
`
`AioyoaJIQ
`
`gam
`
`Od1AIaS
`
`uol2907
`
`add
`
`J2U0S10g
`
`SO0B|q
`
`obL
`
`Vibe
`
`Z
`
`»
`
`bpe
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0007
`EXHIBIT 1026 - PAGE 0007
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 7 of 9
`
`US 6,327,535 B1
`
`
`
`
`
`SJBPIAGI}X9}UGO
`
`
`
`SJBPIAOIC|I'y
`
`éZ9anoeul
`
`
`
`pljeApuesanoeJOPIO
`
`
`
`
`
`
`
`SJSPIAOId}X9}UCDPI|eA
`
`
`}XO]U09JUAN18ho
`
`
`
`008
`
`
`UBSAI}DVJUBUND
`
`
`SUILWA}9poe}|U9}9C]208
`
`
`
`
`
`uleoUapIUODeseelDEq
`
`908
`
`
`
`
`
`
`
`OWI}JOAO1X9]UO9JUSIUND
`
` SUILUS]9S}yyey|19dOle’tl;§:e
`
`
`
`USJNDJOUJSUM
`
`
`
`
`
`
`
`
`poseq}x9o}U00SUIUIA}Eq
`
`}x9]U09JUaLINDayepdny
`
`
`
`UONEWOJU!yx<a}U09UOdN
`
`
`
`
`
`SU@PIAOJCJX8}UCDLUO)
`
`8L8
`
`
`
`
`
`}SNJjJOJaAe|peuyoepol
`
`
`
`P91099qO}SJeEBaaeJX9]U09
`
`cL8vLe
`
`
`
`
`
`
`
`YIMSJOPIAOIC}X9]U0D109/9S
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0008
`EXHIBIT 1026 - PAGE 0008
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`Sheet 8 of 9
`
`US 6,327,535 B1
`
`(s)uoneodde
`
`[QA9|
`
`\—ziot
`
`WoSalanb}x9]U09aAledoy
`
`
`
`
`
`
`
`
`AoeaudBuilpuodsa.o9esey
`
`0}89}(BO|YOIEJAIYSSUBACI|
`
`
`JY}SPOUeUYIMpejeloosse
`jaa}AoeaiidBuipuodsaioo
`
`99}JBdIYoIeJSIYBUlSopoU
`UONEWUUOJU!}X8]U09WIN}aY
`
`
`Jedd]ADBAUI&SUILUUE]EG
`
`aolAapBulyndwooajiqouw@JO}X9}U0D
`
`
`suoneojddeaiowJosuo
`
`O]SJ@A9|AoeAudubissy
`
`
`SUILUI9}0q
`
` seg]AoeAlidaulyeqNo~=0001
`8}YIMpsyeloosse
`eYMSpouepull
`NN8001
`\—oto
`
`
`
`
`1X9]U09JUauINOBy]Uleaose
`
`1X9]U09JUBINDe0}suIeed
`
`UOUO!BUWJOJU!BY}SSODO1q
`
`
`0}suleyiedyey}UOIeLWOjU!
`
`JOSUOWOS]]edBAISDOY
`
`
`JBY}UONBWWOJU!SAIsDeyY
`
`ymuoneoiddeAj\ddns
`0}SdIASP3}YIMpUue
`
`suoeoddeaiow
`
`}X9JUOD$,991AOp
`
`9001
`
`BOIASPAU}JO
`
`SOIABPBu}JO
`
`
`
`
`/
`
`N006
`
`NR606
`
`NR06
`
`N906
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0009
`EXHIBIT 1026 - PAGE 0009
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 4, 2001
`
`h
`
`f
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0010
`
`NO
`
`o
`
`

`

`US 6,327,535 B1
`
`1
`LOCATION BEACONING METHODS AND
`SYSTEMS
`
`TECHNICAL FIELD
`
`This invention relates to generally to the area of context-
`aware computing or ubiquitous computing.
`BACKGROUND
`
`10
`
`15
`
`‘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
`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
`need to access information, data, resources andthelike, that
`have geographic dimensions to them. For example,
`indi-
`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 5
`individual’s contextual location so that services, goods and
`the like can be made available to the individual. As “eCom-
`
`merce” continucs to grow in importance, the necessity of
`bringing people, places, services and goods together in an
`efficient manner will becomecritically 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-
`tionsin an often times incompatible manner. As an example,
`consider the context of location. Some services have
`
`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
`user desires to locate a particular restaurant,
`they might
`simply enter the zip code where theyare located to see a list
`of corresponding restaurants in that zip code. From the list
`of restaurants,
`they might be able to sclect one or two
`restaurants of interest. This approach is undesirable for a
`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
`suited to finding restaurants, but possibly not other busi-
`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
`somerestaurants 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 plumberthat
`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 youto stay in the
`stadium.
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`There is an unsolved need to be able to create context-
`
`aware computing in which computing devices can partici-
`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-
`aware compuling. Context-aware computing is much more
`than just position awareness—although this is a very big
`field in and ofitself.
`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.
`
`SUMMARY
`
`Context aware computing systems and methods are
`described. In the described embodiment, one or more hier-
`archical tree structures are defined that uniquely identify
`geographical divisions of the Earth and/or physical or logi-
`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 ofthe 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-
`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
`
`tree structure that represents a universally
`hierarchical
`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
`commoninterface, a location service module, a plurality of
`location providers, and an application program interface
`(APD)or events layer. Various location providers can call the
`common interface with location information that is pro-
`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
`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
`APIlayerto ascertain location information from the location
`service module. By knowing where a device is located
`within a hierarchical structure, the applications can present
`location-dependent goods or services to the user. Thus, a
`useris able to actively participate in their current computing
`environment.
`
`In other embodiments, the location service module is able
`to determine, to a degree of certainty, the location of the
`device. It does so through the use of confidence and accu-
`racy parameters thal are assigned to the information thatis
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0011
`EXHIBIT 1026 - PAGE 0011
`
`

`

`US 6,327,535 B1
`
`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 considerall of the param-
`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 managerthat functions to modulate the information
`that is provided to the various applications as a function of
`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 providesdirect
`information about the device’s location within the defined
`hierarchical infrastructure.
`
`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-
`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 diagramthat 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.
`
`10
`
`15
`
`30
`
`35
`
`40
`
`FIG.10 is a flow diagram that describes steps in a method
`in accordance with the described embodiment.
`
`45
`
`FIG. 11 is a side elevational view of an exemplary
`location beacon in accordance with onc 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 exemplaryclassification of nodes
`akes place on a physicallevel (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
`he Master World has various attributes associated with it
`
`hat assist in context-aware computing. Exemplaryattributes
`include a unique ID, name, geographicentity class, latitude/
`ongitude, relative importance, contextual parents to name
`just a few. The Master World is useful becauseit can be used
`
`
`
`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 ontheir
`location. That is, value is provided by the Master World
`modelin the ability to tie services to nodal locations in the
`Master World.
`
`two additional concepts add
`Building on this concept,
`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
`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-
`ondary Worlds can be physical and/or logical representa-
`tions of each individual entities’ world view. One particu-
`larly useful aspect of the Secondary World isthat it links, at
`at least one point, into the Master World. Thus, within any
`Secondary World, a uscr’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
`
`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
`with a particular Secondary World can be offered.
`A geozoneis 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
`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
`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.c. desktop devices) or mobile comput-
`ing devices(i.e. cell phones, laptopsetc.). Thatis, the Master
`World (orat least a portion ofit) 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
`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-
`
`ondary Worlds, a various robust collection of context-aware
`solutions becomeavailable 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
`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-
`mining the device’s location. Here, by virtue of having the
`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.
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0012
`EXHIBIT 1026 - PAGE 0012
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,327,535 B1
`
`5
`One embodiment provides a clicnt 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-
`vice through one or more Application Program Interfaces
`(APIs) or Events to get location information that is used by
`he applications to render a service.
`The location service makes use of one or more location
`providers that conveyinformation to the device. This infor-
`mation can be information that is specific to the location
`provider, or can be information that can be mapped directly
`into a node of the Master World or Secondary Worlds.
`Exemplary location providers can include Global Position-
`ing Service (GPS) providers, cell phone providers (cell
`providers), Bluetooth providers, a user interface provider
`andthe like. The location providers provide information that
`gives some aspect of a device’s current
`location. This
`information is used by the location service to ascertain the
`ocation of the device.
`
`
`
`Oneparticularly advantageousfeature of the client device
`is a standard or commonlocation provider interface. The
`ocation provider interface enables the various location
`providers to provide information to the location service so
`hat the location service can use the information to deter-
`mineits location. Essentially, the multiple location provider
`toterface is a common interface that enables multiple dif-
`ferent location providers to provide location information (or
`hints) aboutlocationto 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
`ocation information can be provided with confidence and
`accuracy estimates to enable the location service to evaluate
`he relative quality of the information beforeit is used. The
`various providers also have the ability to self-monitor them-
`selves whichassists in the providers’ ability to intelligently
`convey information to the location service. By having a
`common interface, the collection of location providers is
`dynamically extensible—that is location providers can be
`added or removed fromthe collection of location providers
`without any interference of the functionality performed by
`the location service or device. The location providers can be
`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 ie. (1) the provider
`interface that receives information from the location pro-
`viders and (2) the API/events layer that enables applications
`to get at the various information.
`Onefocusof this embodiment is a device that can collect
`context information (e.g. location information) from a vari-
`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 Sccondary World. The hicrarchical
`trees can then be traversed to determine the device’s accu-
`rate location in both the Secondary World and the Master
`World. At this point, the device has determined its context.
`The informationthat is collected can be subjectto 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-
`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. Oncethis is done,
`the device can begin to answer queries from various appli-
`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 informationthat 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 embodimentlocation translation services are
`provided that are directed to determining, as accurately as
`possible,
`the context or location of the device.
`In this
`embodiment, information is received from the various loca-
`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 (whichhelpsto age the
`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 andtrust levels. This defines
`
`an orderedlist 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 higherleveloftrust. The
`information that is provided byall 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 ELD is a node on the Master World.
`The tree might also be a Secondary World and the EID (or
`location unique indentificr or “LUID”) is a node on the
`Secondary World. Once this information is collected, com-
`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-
`aware computing environment are addressed.
`In this
`embodiment,
`the location service has acquired location
`information that pertains to the location of a particular
`device. A privacy manager determines what level of infor-
`mation to provide to applications that might request the
`information. The privacy manager can reside on the com-
`puting device itself, or can be proxied by a trusted third
`party.
`According to this embodiment, a scale of privacy levels
`are defined. Each level is defined to include more or less
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`APPLE
`APPLE
`EXHIBIT 1026 - PAGE 0013
`EXHIBIT 1026 - PAGE 0013
`
`

`

`US 6,327,535 B1
`
`7
`the location of a particular
`specific information about
`device. A user is able to assign a privacy levelto entities that
`might request location information. Additionally, each node
`of the Master World and a Secondary World can have a
`privacy level associated with it. When a query from an
`application is received, the privacy managerfirst determines
`whothe query is from and the privacy level associated with
`the application or entity. The privacy managerthen evaluates
`one or more of the Master World and the Secondary World
`to find a node that has a corresponding privacy level. When
`a corresponding nodeis found, informationat that particular
`granularity is provided to the requesting application or
`entity.
`In another embodimentsystems and methodsof providing
`a location provider in the form of a location beacon are
`described.In this embodiment, a location beaconis provided
`hat can be mounted in various areas (public/private areas)
`o beacon the location to any computing devices within
`ransmission range. The information that
`is transmitted
`enables a device to determine its location or context. The
`
`ocation beacon can transmit information that is specific to
`he location service that uses the information. Transmitted
`
`
`
`information can include an EID/URLpair, and a LUID/URL
`pair. The EID gives the node identification of a node in the
`Master World; and, the associated URL gives a protocol to
`communicate with the Master World. The URL might, for
`instance, link to a server that can provide additional context
`information that uses the EID. The indicates a node on a
`Secondary World that correspondsto a current location; and
`he URL gives a protocol to communicate with the Second-
`ary World. For example, the URL can link with a serverthat
`is hosting the Secondary World. This server can then be
`queried to discover more information about the Secondary
`World (ic. Secondary World tree structure,
`location of
`associated resources, etc.) With the EID and T.UID (along
`with the URLs), a device can nowtraverse the Master World
`or Secondary World to determineits location. Various tech-
`nologies can be used to implementthe beacon (wireless, RF,
`IR). The beacon can be a “program once” device to deter
`tampering. Programmable beacons can, however, be pro-
`vided. Security can also be provided in the form of a
`verifiable signature that is provided with the beacon infor-
`mation to assure the veracity of the transmitted information.
`Auseful context-aware computing aspect of the beacon is
`the concept of “location-enabled access”. Thatis, in addition
`to (or separately from) receiving location information, a
`beacon can transmit code download pointers that enable
`smart devices to access software code that allows the device
`
`to participate in its current context.
`Exemplary Computing System
`the term “computing
`In the context of this document,
`device”is used to refer generally to any type of computing
`device. Characteristics of exemplary computing devices are
`that
`they typically include one or more processors,
`computer-readable media (such as storage devices and
`memory), and softw