`I IIIII IIIIIIII
`
`US 20070005243A 1
`
`110) United States
`t12) Patent Application Publication
`rm) Pub. No.: US 2007/0005243 Al
`.Jan. 4, 2007
`Horvitz et al.
`(43) Pub. Date:
`
`(54) LK-\Rl\l'l(i, STOH.l'IG, AI\ALYZl'l(i, Al\D
`RK\SOJ\ING ,\BOUT TIIE LOSS OF
`1,0( :xnoN-IDE'ITIFYII\G
`SIGNAi .S
`
`Publication ( 'lassitication
`
`(51 i Int. Cl.
`@IS 1/00
`(2006.01)
`(521 ll.S. Cl. ...................................... 701/213: 342/357.06
`
`(75)
`
`Invmtors: Eric J. Jlonitz, Kirkland, KA. (US):
`.John C. Krumm, Redmond, WA (US)
`
`(57)
`
`ABSTRACT
`
`Com;spondence Address:
`A'11N. TUROCY & C.\LVl'I, LLP
`24III ROOR. NATIONAL CITY CENTER
`1900 K\ST J\J'ITH STREET
`CLEVELA'ID, OH 44U4 (l/S)
`
`(73) Assignee: Microsoft Corporation, Redmoud, WA
`(US)
`
`(21) Appl. No.:
`
`ll/171,N9 I
`
`122) filed:
`
`.Jun. 29, 2005
`
`A]m;ation-cenlric signal shadow mapping and storing archi(cid:173)
`tect11re thiit cremes m:Jps ,,here signals. such :1s ( ,PS, c:Jnn01
`be seen \\ ith case because uf natural or synthctii.: features
`such as groups of tall buildings. Such maps are used with
`other infornwtion. such as the dyu:.unii.:s of the sensed
`velocity that had been seen before the loss of the signals. to
`reason about the location and likely acti\ities being carried
`m1t by one or more people. lnfrrcnces ran be made based on
`information .ibout organizutions and services associated
`with structures and locations proximal to the locations where
`signals were lost. .\!so, such reasoning can be used to tum
`off ur to reduce the power consumed bv the receivers of the
`locntion infomrntion. potentially with the joint use of ,1cccl(cid:173)
`ernmders lo identili• when signi[icant acceleraliuns occur .
`
`GPS SATELLITE SYSTEM
`
`1ls508
`
`"'500
`
`522
`
`514
`
`SHADOW
`PROCESSING
`SYSTEM
`
`516
`
`SI IADOW MAPPING
`DATA STORE
`
`504
`
`LOCATION A
`
`IPR2020-01192
`Apple EX1039 Page 1
`
`
`
`Patent Ap11lication Publication
`
`Jan. 4, 2007 Sheet 1 of 10
`
`US 2007/0005243 Al
`
`rtoo
`
`RECEIVING
`COMPONENT
`
`.,,.--104
`
`J ~
`
`' ,.
`SHADOW
`PROCESSING
`COMPONENT
`
`' '
`
`V
`
`.,,.--102
`
`SHADOW ANALYSIS ,- 106
`COMPONENT
`
`FIG. I
`
`IPR2020-01192
`Apple EX1039 Page 2
`
`
`
`Patent Ap11lication Publication Jan. 4, 2007 Sheet 2 of 10
`
`US 2007/0005243 Al
`
`START
`
`RECEIVE A GEOGRAPHIC LOCATION
`RECEIVING DEVICE THAT PROVIDES .,,,- lOO
`DEVICE LOCATION DATA
`
`1 •
`
`PROCESS DEVICE LOCATION DATA TO
`DETERMINE SHADOW DATA AS DEVICE MOVES V- 202
`THROUGH SHADOW-PRODUCING STRUCTURES
`
`PROCESS SHADOW DATA INTO A
`SHADOW MAP THAT
`APPROXIMATES SHADOW SHAPE
`
`V 204
`
`MAP AND STORE SHADOW MAPS
`FOR OTHER SHADOW-PRODUCING .,,,- 206
`STRUCTURES
`
`, ..
`
`STOP
`
`FIG. 2
`
`IPR2020-01192
`Apple EX1039 Page 3
`
`
`
`Patent Application Publication Jan. 4, 2007 Sheet 3 of 10
`
`US 2007/0005243 A 1
`
`START
`
`, .
`
`RECEIVE PORTABLE DEVICE HAVING
`GEOGRAPHIC LOCATION TECHNOLOGY ,,,,-300
`TO PROVIDE DEVICE LOCATION DATA
`AND DEVICE HEALTH DATA
`, .
`TRANSMIT DEVICE HEALTH DATA AND
`DEVICE LOCATION DATA TO SHADOW ,,,,-302
`PROCESSING SYSTEM AS DEVICE IS
`MOVED AMONG STRUCTURES
`
`w
`PROCESS DEVICE DATA TO DETERMINE v- 304
`INTEGRITY OF DEVICE LOCATION DATA
`
`' ,
`GENERA TE SHADOW MAP OF
`STRUCTURES BASED ON TEMPORAL ,.,,-306
`INFORMATION AND DEVICE LOCATION
`DATA
`
`' ,
`STORE SHADOW MAP FOR NETWORK ,,,,-308
`ACCESS
`
`, .
`( STOP
`
`FIG. 3
`
`IPR2020-01192
`Apple EX1039 Page 4
`
`
`
`Patent Ap11lication Publication Jan. 4, 2007 Sheet 4 of 10
`
`US 2007/0005243 Al
`
`GPS SATELLITE SYSTEM
`
`410_j.
`
`.,:-404
`
`~406
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`400
`
`~402
`
`412
`
`I
`I
`I
`I
`I
`I
`I
`I
`
`FIG.4
`
`IPR2020-01192
`Apple EX1039 Page 5
`
`
`
`DATA STORE
`
`SHADOW MAPPING
`
`516
`
`514
`
`SYSTEM
`
`PROCESSING
`
`SHADOW
`
`FIG. 5
`
`LOCATION A
`
`504
`
`522
`
`(') = --· 0 =
`Q = ""C = O" -·
`""C = -t"e = -~ -= --· ~ = ::t.
`
`~500
`
`OPS SATELLITE SYSTEM
`
`IPR2020-01192
`Apple EX1039 Page 6
`
`
`
`FIG.6
`
`LOCATJON2
`
`°' 0 --0
`
`~ --· 0 =
`"'d = O'" --· n
`~ --· 0 =
`"C -;::;·
`
`"C
`;....
`
`SHDIM12
`
`SHDIM11
`
`DEVDIR23
`
`DID23
`
`DHD23
`
`DLD23
`
`STRUCT2
`
`TIME23
`
`EDGE2
`
`EDGE1
`
`DEVDIR1:
`
`DID22
`
`DHD22
`
`DLD22
`
`STRUCT1
`
`TIME22
`
`DID21
`
`DHD21
`
`DLD21
`
`STRUCT1
`
`TIME21
`
`SHDIM12
`
`EDGE3
`
`DEVDIR23
`
`DIDn
`
`DHDn
`
`. . .
`
`DLD13
`
`STRUCT2
`
`TIME13
`
`I AREA2
`
`SHD1Mi1
`
`EDGE2
`
`EDGE1
`
`DEVDIR12
`
`DID12
`
`DHD12
`
`DLD,2
`
`STRUCT1
`
`TIME12
`
`DID11
`
`DHD11
`
`DLD11
`
`STRUCT1
`
`TIME11
`
`AREA1
`
`I
`
`LOCATION1
`
`r6oo
`
`IPR2020-01192
`Apple EX1039 Page 7
`
`
`
`Patent Ap11lication Publication Jan. 4, 2007 Sheet 7 of 10
`
`US 2007/0005243 Al
`
`.,:-700
`
`r 702
`DEVICE DATA -
`SHADOW -
`/ -
`LEARNfNG AND -
`
`ANALYSIS
`COMPONENT
`
`/
`
`RULES
`COMPONENT
`
`REASONING /
`COMPONENT
`
`708
`
`710
`
`712
`
`SHADOW MAPPING
`SYSTEM
`
`PROCESSING /
`COMPONENT
`
`706
`
`704
`~
`
`I DEVICE1 I
`I DEVICE2 I
`I DEVICE, :
`.
`.
`.
`I DEVICEN I
`
`~
`
`r
`
`.
`.
`.
`I
`
`FIG. 7
`
`IPR2020-01192
`Apple EX1039 Page 8
`
`
`
`0 --0
`
`00
`
`~ --· 0 =
`"'d = O'" --· n
`~ --· 0 =
`::s --;::;·
`
`;....
`
`FIG. 8
`
`Measurement
`
`t
`
`(t-1 .. f)
`
`Mean velocity
`
`f
`
`Temperature
`
`Measured
`
`Report
`
`Outside Temperature,_,~~,
`
`Web-Based
`
`(lat,long,altitude)
`
`--... Location t
`
`---
`
`---
`
`-----------------------
`
`---
`
`---
`
`802~
`
`rsoo
`
`IPR2020-01192
`Apple EX1039 Page 9
`
`
`
`Patent Application Publication Jan. 4, 2007 Sheet 9 of 10
`
`US 2007/0005243 Al
`
`r9oo
`
`902
`
`_________ c 930 ----..,
`
`l OPERATING SYSTEM_:
`r932
`_
`________
`1
`1 APPLICATIONS :
`~---~----------J
`,--------£ 934 _
`, ______________ ..
`I MODULES
`:
`,,-936
`- _ J_ - - - - -
`DATA
`
`---
`
`:
`
`PROCESSING
`UNIT
`
`904
`
`906
`
`SYSTEM
`MEMORY
`
`RAM
`
`ROM
`
`,- --
`I
`L-
`
`-
`
`--------
`
`920
`
`922
`
`FDD
`
`DISK
`
`OPTICAL
`DRIVE
`DISK
`
`VIDEO
`ADAPTOR
`
`INPUT
`DEVICE
`INTERFACE
`
`NETWORK
`ADAPTOR
`
`942 (VlIRED/WIRELESS)
`958
`
`MODEM
`
`(WIRED/WIRELESS)
`
`FIG. 9
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`-
`
`- _ ..
`
`( ______ y
`.... --
`I EXTERNAL I
`-----
`'-
`HOD
`.,,
`
`914
`
`944
`
`MONITOR
`
`938
`
`KEYBOARD
`
`940
`
`MOUSE
`
`948
`
`REMOTE
`COMPUTER(S)
`
`950
`
`MEMORY/
`STORAGE
`
`IPR2020-01192
`Apple EX1039 Page 10
`
`
`
`Patent Application Publication Jan. 4, 2007 Sheet 10 of 10
`
`US 2007/0005243 A 1
`
`1002
`
`CLIENT(S)
`
`rIOOO
`
`1004
`
`SERVER(S)
`
`1008
`
`1010
`
`CLIENT DA TA STORE(S)
`
`SERVER DATA STORE(S)
`
`FIG. 10
`
`IPR2020-01192
`Apple EX1039 Page 11
`
`
`
`US 2007 /0005243 Al
`
`Jan. 4, 2007
`
`I
`
`LEARNING, STORING, ANALYZING, AND
`REASONING ABOUT THE LOSS OF
`LOCATION-IDENTIFYING SIGNALS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`[0001] This application is related to pending U.S. patent
`application Ser. No.
`(Atty. Dkt. No. MSFTP923US)
`entitled "INTEGRATION OF LOCATION LOGS, GPS
`SIGNALS, AND SPATIAL RESOURCES FOR IDENTI(cid:173)
`FYING USER ACTIVITIES, GOALS, AND CONTEXT"
`filed on
`
`BACKGROUND
`[0002] As computing moves off the desktop into the hands
`of mobile users, it is becoming ever important for mobile
`devices to be aware of the user context. Important pieces of
`context include user's location, activities, nearby people and
`devices, and mode of transportation, if any. This knowledge
`can in tum be employed by mobile devices to display
`reminders, to configure themselves for use with other
`devices, and to behave in a manner that is appropriate for the
`surrounding envirom11ent ( e.g., turn off cell phone ringer) or
`subcontexts of the surrounding enviromnent such as whether
`particular states or transitions among states are occurring
`within the enviromnent.
`
`[0003] One aspect of context concerns whether or not the
`user (and the device) is inside or outside of a building or
`structure. For example, knowledge of such infomrntion can
`be used to facilitate determining the user's location (e.g., in
`a building or structure, in a particular building or structure,
`or in one of a set of known buildings or structures) and the
`user's mode of transportation (e.g., in a bus, car or airplane).
`Such knowledge can also be utilized to conserve power on
`systems that do not provide useful services inside buildings
`or outside.
`
`[0004] Another aspect of the relevance of the loss of
`signals to a user's context and activities is related to a larger
`scale, that is, "urban canyons"-where GPS reception is
`poor because of surrounding structures. The loss of signals
`when a user moves from an area where signals are known to
`be receivable into an area where signals are known to be
`hard to receive can provide knowledge of where the user has
`traveled, currently is, and is potentially heading in an urban
`canyon. Urban canyons can be created by structures such as
`multi-story buildings (principally, and whether the user is
`inside or outside of the building), but also include trees,
`hills, and tunnels (generally). Knowledge of where GPS
`signals are lost can be of value to the user and to companies
`that seek to benefit economically by knowledge of the user
`location. To date, the loss ofGPS signals or "GPS shadows"
`caused by structures has been considered a nuisance and
`deficiency. The GPS shadows are areas where a terrestrial
`receiver ( e.g., a handheld receiving device) cannot receive
`adequate GPS signals due to signal blockage or degradation
`by any of the aforementioned structures (buildings, bridges,
`trees, hills, tunnels, etc.). There are currently unrealized
`benefits that can be obtained from the knowledge of shadow
`information and locations.
`
`SUMMARY
`[0005] The following presents a simplified summary in
`order to provide a basic understanding of some aspects of the
`
`disclosed im10vation. This summary is not an extensive
`overview, and it is not intended to identify key/critical
`elements or to delineate the scope thereof. Its sole purpose
`is to present some concepts in a simplified form as a prelude
`to the more detailed description that is presented later.
`[0006] This invention pertains to reasoning about the loss
`of signals as a valuable complement to reasoning about
`signals that provide information about the location of an
`object or person. In one example, focus is on the loss ofGPS
`signals, but the loss of "GPS" signals or detection of "GPS
`shadows" can be taken to mean the loss of GPS or any other
`location-centric signals, such as IEEE 802.11 WiFi signals,
`GSM (global system for mobile communications) signals,
`conunercial broadcast signals, and even the loss of the
`signaling infrastructure used by a device to communicate
`with a central server or another monitoring system via one
`or more signaling modalities.
`[0007] The detection of the loss of signals carries with it
`potentially valuable information about a user's activities and
`location. The loss of signals also indicates that particular
`modalities or usages may become irrelevant. For example,
`GPS typically fails to operate inside buildings because
`satellite signals are significantly attenuated inside buildings.
`Thus, determination of the likelihood that a user is inside can
`be used to tum off a power-consuming GPS system or put
`the system into a mode where it probes for satellite signals
`periodically at a static or variable rate with the changing of
`the likelihood so as to conserve the batteries of the GPS
`system.
`
`[0008] The invention disclosed and claimed herein, in one
`aspect thereof, comprises a shadow mapping architecture
`that maps connnunications shadows (e.g., GPS shadows)
`associated with structures at various geographic locations.
`This is beneficial in the context of urban canyons where
`there is a high incidence of shadows affecting the commu(cid:173)
`nications of user devices (e.g., cell phones, and PDAs). The
`invention includes a shadow processing component that
`processes location infonnation received from a wireless
`receiving device, and a shadow analysis component that
`generates a shadow map of shadows in the locations or
`areas.
`
`[0009] In yet another aspect thereof, a machine learning
`and reasoning component is provided that employs a proba(cid:173)
`bilistic and/or statistical-based analysis to prognose or infer
`an action that a user desires to be automatically perfom1ed.
`In still another aspect of the invention, a logic-centric policy
`component is provided for the generation and/or processing
`of rules or policies. With respect to another feature, a
`shadow mapping subsystem disposed as a network node can
`be employed that stores shadow information to be utilized
`for learning, processing, analyzing and storing shadow
`information.
`
`[001 O] To the accomplishment of the foregoing and related
`ends, certain illustrative aspects of the disclosed innovation
`are described herein in connection with the following
`description and the annexed drawings. These aspects are
`indicative, however, of but a few of the various ways in
`which the principles disclosed herein can be employed and
`is intended to include all such aspects and their equivalents.
`Other advantages and novel features will become apparent
`from the following detailed description when considered in
`conjunction with the drawings.
`
`IPR2020-01192
`Apple EX1039 Page 12
`
`
`
`US 2007 /0005243 Al
`
`Jan. 4, 2007
`
`2
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0011] FIG. 1 illustrates a shadow processing system.
`
`[0012] FIG. 2 illustrates a methodology of shadow map(cid:173)
`ping.
`
`[0013] FIG. 3 illustrates a methodology of shadow map(cid:173)
`ping by utilizing device information.
`
`[0014] FIG. 4 illustrates a diagram ofGPS shadow move(cid:173)
`ment and mapping.
`
`[0015] FIG. 5 illustrates a diagram of a system that facili(cid:173)
`tates shadow mapping.
`
`[0016] FIG. 6 illustrates an exemplary shadow mapping
`data store table.
`
`[0017] FIG. 7 illustrates a system that employs learning
`and reasoning which facilitates automating one or more
`features.
`
`[0018] FIG. 8 illustrates another but more detailed
`dynamic Bayesian network for inferring location and activ(cid:173)
`ity, employing Web-based location resources.
`
`[0019] FIG. 9 illustrates a block diagram of a computer
`operable to execute the disclosed architecture.
`
`[0020] FIG. 10 illustrates a schematic block diagram of an
`exemplary computing environment.
`
`DETAILED DESCRIPTION
`
`[0021] The innovation is now described with reference to
`the drawings, wherein like reference numerals are used to
`refer to like elements throughout. In the following descrip(cid:173)
`tion, for purposes of explanation, numerous specific details
`are set forth in order to provide a thorough understanding
`thereof. It may be evident, however, that the innovation can
`be practiced without these specific details. In other
`instances, well-kuown structures and devices are shown in
`block diagram form in order to facilitate a description
`thereof.
`
`[0022] As used in this application, the terms "component"
`and "system" are intended to refer to a computer-related
`entity, either hardware, a combination of hardware and
`software, software, or software in execution. For example, a
`component can be, but is not limited to being, a process
`nmning on a processor, a processor, a hard disk drive,
`multiple storage drives ( of optical and/or magnetic storage
`medium), an object, an executable, a thread of execution, a
`program, and/or a computer. By way of illustration, both an
`application nmning on a server and the server can be a
`component. One or more components can reside within a
`process and/or thread of execution, and a component can be
`localized on one computer and/or distributed between two or
`more computers.
`
`[0023] As used herein, terms "to infer" and "inference"
`refer generally to the process of reasoning about or inferring
`states of the system, environment, and/or user from a set of
`observations as captured via events and/or data. Inference
`can be employed to identify a specific context or action, or
`can generate a probability distribution over states, for
`example. The inference can be probabilistic-that is, the
`computation of a probability distribution over states of
`interest based on a consideration of data and events. Infer(cid:173)
`ence can also refer to techniques employed for composing
`
`higher-level events from a set of events and/or data. Such
`inference results in the construction of new events or actions
`from a set of observed events and/or stored event data,
`whether or not the events are correlated in close temporal
`proximity, and whether the events and data come from one
`or several event and data sources.
`
`[0024] Referring initially to the drawings, FIG. 1 illus(cid:173)
`trates a shadow processing system 100 in accordance with
`the subject inuovation. The system 100 includes a shadow
`processing component 102 that facilitates reception of geo(cid:173)
`graphic location signals from a receiving component 104,
`which can be a portable wireless device (e.g., a cell phone,
`PDA, or the like) that includes the capability of receiving
`and processing at least such geographic location signals. It
`is to be appreciated, however, that the receiving component
`104 can be any suitable wired/wireless receiving device or
`system capable of receiving and processing geographic
`location signals in accordance with the embodiments
`described herein.
`
`In one implementation, the geographic location
`[0025]
`signals can be of a GPS. Currently, GPS consists of a
`constellation of twenty-four satellites each in its own orbit
`approximately 11,000 miles above the earth-each of the
`satellites orbits the earth in about twelve hours, and the
`positions of which are monitored by ground stations. The
`satellites each include atomic clocks for extremely accurate
`timing (e.g., within three nanoseconds of each other) that
`provides the capability to locate the receiver on the earth
`within, in some applications, one meter resolution. When
`receiving geographic location signals from several of the
`GPS satellites, the receiving component 102 can calculate
`the distance to each satellite of the collllmmicating satellites
`and then calculate its own position, on or above the surface
`of the earth. However, when the signals are interrupted or
`degraded due to terrestrial structures, such interrupt time and
`position information can be usefol in mapping GPS shad(cid:173)
`ows. A shadow is an area of communications interruption or
`total blockage. In the context of GPS, shadows are areas
`where a terrestrial receiver ( e.g., a handheld receiving
`device) canuot receive adequate GPS signals due to signal
`blockage or degradation by any of many types of structures
`that include buildings, bridges, trees, hills, water (when
`submerged) and tunnels, for example.
`
`[0026] The system 100 also includes a shadow analysis
`component 106 that analyzes the GPS location information
`and processes the analyzed information in order to develop
`and store GPS shadow information. As described infra, the
`data can be stored in the fonn of tables accessible as a
`network node. The GPS location information can be
`received from the receiving component 104 via, for
`example, wireless assisted GPS (WAGPS). WAGPS facili(cid:173)
`tates the transmission of the GPS location information from
`the receiving component 104 to a remote location such as the
`shadow processing component 102. Generally, this can
`occur through a cellular network (not shown) where the
`receiving component 104 is a cellular telephone, to an IP
`network (not shown) (e.g., the Internet), and terminating at
`the shadow processing component 102 as a node on the
`Internet or on a subnet thereof.
`
`[0027] Given the approximate location of the receiving
`component 104 and the time at which the GPS shadow is
`entered and departed, and the velocity at which a user was
`
`IPR2020-01192
`Apple EX1039 Page 13
`
`
`
`US 2007 /0005243 Al
`
`Jan. 4, 2007
`
`3
`
`seen to enter a shadow can be mapped at least according to
`some characteristics such as to a leading edge (when the
`device enters the shadow and loses signal) and trailing edge
`(the device leaves the shadow and again reacquires suitable
`GPS signals). Such basic infonnation can be analyzed and
`processed to generalize on a shadow at that location, and in
`association with a structure. Receiving such information
`from a plurality of WAG PS devices over time provides more
`data points in which to define desired characteristics of the
`shadow. Thus, in accordance with the invention, a data store
`of shadow maps can be generated and stored in association
`with structures of urban canyons, for example. Once the
`shadow maps are defined, then a substantial amount of
`information can be obtained and analyzed with respect to the
`user of the WAGPS device such as activities, intentions,
`direction of travel, advertising and reminders that can be
`presented in anticipation of user travel, and so on. The
`personal and economic benefits to uses of such information
`are significant.
`
`[0028] FIG. 2 illustrates a methodology of shadow map(cid:173)
`ping. While, for purposes of simplicity of explanation, the
`one or more methodologies shown herein, e.g., in the form
`of a flow chart or flow diagram, are shown and described as
`a series of acts, it is to be understood and appreciated that the
`subject innovation is not limited by the order of acts, as some
`acts may, in accordance therewith, occur in a different order
`and/or concurrently with other acts from that shown and
`described herein. For example, those skilled in the art will
`understand and appreciate that a methodology could alter(cid:173)
`natively be represented as a series of interrelated states or
`events, such as in a state diagram. Moreover, not all illus(cid:173)
`trated acts may be required to implement a methodology in
`accordance with the innovation.
`
`[0029] At 200, a receiving device is provided that is
`capable of receiving and processing device location infor(cid:173)
`mation. At 202, the device location information is processed
`to detern1ine shadow data as the device moves through
`shadow-producing structures (e.g., buildings in an urban
`canyon). At 204, the received device location data is ana(cid:173)
`lyzed and processed along with other data ( e.g., temporal
`data) to generalize on the structure ( or shape) of the shadow
`to form a shadow map. At 206, map and store shadow maps
`for other shadow-producing structures.
`
`[0030] Referring now to FIG. 3, there is illustrated a
`methodology of shadow mapping by utilizing device infor(cid:173)
`mation. At 300, a wireless portable device is received that
`includes geographic location teclmology (e.g., GPS) to
`provide device location data and device health data. At 302,
`device health data and device location data is transmitted as
`the device moves among structures that cause conummica(cid:173)
`tions shadows. At 304, the device health data is processed to
`determine the integrity of the device location data. At 306,
`a shadow map of the structures is generated based on
`temporal information and the device location data. At 308,
`the shadow map is stored with other related information for
`access.
`
`[0031] FIG. 4 illustrates a diagram ofGPS shadow move(cid:173)
`ment and mapping. A structure 400 ( e.g., a building) is
`provided that causes a GPS shadow 402 in relation to a GPS
`satellite system 404 that orbits the earth twice per day. In that
`the satellite system 404 moves in relation to the earth, and
`thus, in relation to the structure 400, the shadow 402 will
`
`move accordingly to some extent based on signal coverage
`of the multi-satellite GPS system 404. In other words, when
`the satellite system 404 is in a first position 406, a first
`position shadow 408 of a shape and size can be cast on the
`earth's surface by the structure 400. Similarly, when the
`satellite system 404 is in a different position 410, a corre(cid:173)
`sponding second position shadow 412 can be cast on the
`earth's surface, and which can be of a different shape and
`size than the first position shadow 408.
`
`[0032] It is to be appreciated that the size of the shadow
`402 as ultimately mapped will change according to the speed
`and direction of a WAGPS device 406 moving through the
`shadow 402. In other words, moving the device 414 in a
`direction substantially perpendicular through the first posi(cid:173)
`tion shadow 408 will result in a more accurate determination
`of a leading edge 416 and trailing edge 418 of the first
`position shadow 408 at a given time. Thus, the shadow
`mapping process can occur incrementally such that phases
`of the shadow 402 are mapped over short durations of time
`and stored accordingly. Thereafter, some or all of the
`mapped phases can be combined to provide comprehensive
`shadow map for the structure 400 over a longer duration of
`time.
`
`[0033] FIG. 5 illustrates a diagram of a system 500 that
`facilitates shadow mapping. A wireless device 502 of a user
`504 receives geographic location signals 506 from a satellite
`system 508 (e.g., GPS). The device 502 processes the
`geographic location signals 504 in order to determine its
`location. Additionally, the device 502 is capable of conunu(cid:173)
`nicating with a wireless network 510 (e.g., a cellular net(cid:173)
`work) such that device location data can be transmitted from
`the device 502 to the wireless network 510. An IP network
`512 (e.g., the Internet) cmmects to the wireless network 510
`to provide IP services accessible thereon. The device loca(cid:173)
`tion data can be co1lllllunicated over the IP network 512 to
`a shadow processing system 514 that learns, processes,
`analyzes, and stores data that facilitates defining shadow
`maps. Such information is stored on a shadow mapping data
`store 516.
`
`[0034] As described supra, the device 502 can also process
`and transmit device data that indicates a status of the device.
`For example, when the device 502 is moved from a non(cid:173)
`shadow area where the device location data can be deter(cid:173)
`mined into a GPS shadow 518 such that GPS signals can no
`longer be received at a suitable level, the change can be
`determined to be an edge of the GPS shadow 518. However,
`it is to be appreciated that the loss of GPS signals 506 can
`also be from device failure, for example. Thus, device
`information can also be transmitted that confinns whether
`the change is valid or not. Ifthe device 502 sends device data
`that indicated the device 502 if folly operational, the change
`can be considered to be reliable, and stored as a shadow
`edge.
`
`[0035] Alternatively, ifno device data is received with the
`device location data, then the change can be inferred likely
`be unreliable, since the device may have failed or become
`unreliable in some way. Thus, as the user 504 moves the
`device 502 in and out of the shadow 518, the shadow 518
`can be mapped to some extent. Greater shadow features can
`be detennined and mapped as more devices 506 are moved
`into and out the shadow 518. Over time, based on repeated
`
`IPR2020-01192
`Apple EX1039 Page 14
`
`
`
`US 2007 /0005243 Al
`
`Jan. 4, 2007
`
`4
`
`measurements of the structure shadow 518, the shadow
`features (e.g., shape and size) can be mapped with a higher
`degree of accuracy.
`[0036] In an urban canyon, structures are likely to be more
`closely situated. For example, a tree 520 (or other shadow(cid:173)
`producing structure that causes the shadow 518) is likely to
`be in close proximity to other shadow-producing structures
`such as a second strncture 522 ( e.g., a building) that casts a
`second shadow 524. As a result, the communications shad(cid:173)
`ows (518 and 524) can exhibit some overlap. When ulti(cid:173)
`mately mapped, the map of the two shadows (518 and 524)
`for the two structures (520 and 522) can be learned, ana(cid:173)
`lyzed, processed and stored to be a single map.
`[0037] With respect to velocity, for example, the loss of
`the reported GPS signal when the device was seen to be
`traveling at 65 miles per hour, in conjunction with informa(cid:173)
`tion that the device is working fine and has battery power,
`etc., provides evidence that the loss of a signal was probably
`not because of a user stopping within a structure associated
`with a specific economic activity, like purchasing an item at
`a retail business. Instead, it probably means that a user has
`entered an urban canyon. Seeing a drop in velocity to a stop
`or near stop before a signal is lost is evidence that a user is
`probably stopping at a location to perform an activity.
`[0038] The location can be correlated with a map of
`location-based resources to identify the type of activity that
`the user is engaged in-and the return of the signal, coupled
`with an accelerating velocity away from the location is
`evidence that the activity associated with the location-and
`structure, which caused the blockage of the signal, has
`ended.
`
`[0039] Inferences can be made about the probability of
`different activities, given the pattern of approach into the
`lost-signal situation, and about the information gleaned
`about the location associated with the loss of GPS signals.
`For example, a probability distribution over activities can be
`associated with the identified type of business or organiza(cid:173)
`tion associated with the structure. The type of organization
`can be detem1ined by linking the address or location to type
`of organization via a lookup in an online yellow pages or via
`general search on addresses on the Web. The activities can
`be considered to be continuing while the signal remains lost,
`and can be considered to have shifted or ended when GPS
`is re-attained.
`
`[0040] In many cases, GPS might be turned off until there
`are signs of fast accelerations as might be detected by a
`less-power hungry accelerometer. That is, if a signal is lost
`for a significant amount of time shortly after the velocity of
`a user is seen to decelerate from 60 miles per hour to 40 to
`30 to 10 to 5 to 2 miles per hour, and there is no knowledge
`of a GPS shadow in this region, per a previously assembled
`"GPS shadow map", then there is a good evidence that a user
`has approached the building with a vehicle capable of going
`60 miles per hour, and the user or user and vehicle is
`currently inside a building. The GPS system can be turned
`off, to save power, and only tum it on again ifthere is a sign,
`perhaps coming from an accelerometer that the user has
`accelerated significantly, for example, the kinds of accelera(cid:173)
`tions that would only be seen in an automobile. At this time,
`the GPS can be turned back on again and when the GPS
`signal detected again, make inferences that the user has left
`the structure, and that the probability distribution over the
`
`activities associated with the strncture is changing to a
`probability distribution associated with driving to another
`location.
`
`[0041] The shadow mapping processing system 514 and
`associated store 516 can be employed for mapping and
`storing up known shadows by many users or devices that
`establish a shadow map, for example. With respect to using
`a shadow map in real time, for example, it can be inferred
`that a user who enters a known shadow while traveling on
`a highway at 70 mph, is likely going to appear at the place
`where the highway intersects with the shadow in the direc(cid:173)
`tion that the user is heading. In contrast, a user whose
`reported GPS signal is lost ( e.g., as monitored by a service
`that is receiving a live feed of intermittent updates about the
`GPS infomiation) after that user has significantly slowed
`down to "parking" or "building parking structure entry"
`speeds or frankly stopping, is probably doing something
`associated with the location (e.g., park) or structure (e.g., a
`shopping mall), until the GPS appears again, at which time
`the activity is probably now completed. The loss of a signal
`in the latter case coupled with knowledge that there are no
`GPS shadows in the area, and also potentially, where it is
`received via some standard signal and encoding, that the
`device is radioing back via a web service, that tells the server
`that it has power and is healthy, but callllot see GPS.
`
`[0042] Referring now to FIG. 6, there is illustrated an
`exemplary shadow mapping data store table 600. Various
`levels of categorization can be utilized to learn, track and
`store data related to the acquisition and processing of at least
`device information, device location information, and
`shadow information. In the context of an urban canyon, for
`example, the table 600 can include generalized location
`information of a first location (denoted LOCATION1) to be
`mapped, such as a city, county, or block, etc. Associated with
`the first location is a first area (denotedAREA1) that further
`defines an area within the first location that is mapped. In
`this example, the first area can be a cross