TRAVEL PATTERN DISCOVERY USING MOBILE DEVICE SENSORS

• US 20130260791A1
• Filed: 04/02/2013
• Published: 10/03/2013
• Est. Priority Date: 04/02/2012
• Status: Active Grant

• Current Assignee: University of Washington
• Original Assignee: Through Its Center For Commercialization University of Washington
• Inventors: Wang, Yinhai, Malinovskiy, Yegor
• Granted Patent: US 9,374,661 B2
• Time in Patent Office: Days
• US Class Current: 455/456.1
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

A facility comprising methods and systems for discovering travel patterns based at least in part on data collected from a plurality of dynamic and/or mobile sensor devices is disclosed. The mobile sensor devices sense or detect the presence of nearby devices and record information about each detection, such as the location, the date and time, and an identifier of the detected device and provide this information to the facility. Thus, the facility can leverage the communication capabilities of existing mobile devices and networks to provide a broad, wide-ranging, scalable sensor network that detects the presence of individual devices. By recording and analyzing the encounter data received from various mobile sensor devices, the facility can ascertain or estimate the path of devices and their associated users. Given the availability of mobile devices and mobile networks, the disclosed techniques can be deployed without a substantial investment in infrastructure and maintenance.

Claims

1. A method, performed by a computing system having a processor, for estimating the travel path of a plurality of devices, the method comprising:

receiving, from each of a plurality of mobile sensor devices, encounter data comprising a plurality of encounters, each encounter specifying an indication of a device detected by the mobile sensor device, a location, and a time,

wherein encounter data received from a first mobile sensor device and encounter data received from a second mobile sensor device each include at least one encounter specifying an indication of a first device;

based at least in part on the received encounter data, identifying a plurality of devices detected by the mobile sensor devices; and

for each of the identified detected devices,

determining at least one trajectory for the identified detected device based at least in part on the received encounter data, each trajectory comprising two encounters,

based at least in part on the at least one trajectory determined for the identified detected device, determining at least one trip for the identified detected device, and

estimating a route for the determined at least one trip,

wherein at least one trajectory for the first device comprises a first encounter received from a first mobile sensor device and a second encounter received from a second mobile sensor device.

2. The method of claim 1 wherein each of the mobile sensor devices comprises a mobile telephone.

3. The method of claim 1 wherein at least one of the mobile sensor devices is configured to detect a first device based at least in part on information broadcast by the first device.

4. The method of claim 3 wherein the information broadcast by the first device comprises an address associated with the first device.

5. The method of claim 4 wherein the address is a media access control address.

6. The method of claim 1 wherein the location specified by at least one encounter comprises GPS coordinates.

7. A computer-readable storage medium storing instructions that, if executed by a computing system having a processor, cause the computing system to perform operations comprising:

identifying a plurality of unique devices detected by at least one of a plurality of mobile sensor devices; and

for each of the identified unique detected devices,

determining at least one trajectory for the identified detected device based at least in part on the received encounter data, each trajectory comprising two encounters,

wherein at least one trajectory for the first device comprises a first encounter received from a first mobile sensor device and a second encounter received from a second mobile sensor device,

based at least in part on the at least one trajectory determined for the identified device, determining at least one trip for the identified device, and

estimating a route for the determined at least one trip.

8. The computer-readable storage medium of claim 7, the operations further comprising:

receiving, from a first mobile sensor device, first encounter data comprising a plurality of encounters, each encounter specifying an indication of a detected device, coordinates, and a timestamp;

receiving, from a second mobile sensor device, second encounter data comprising a plurality of encounters, each encounter specifying an indication of a detected device, coordinates, and a timestamp.

9. The computer-readable storage medium of claim 8, wherein the first encounter data comprises at least one first encounter specifying a first detected device and wherein the second encounter data comprises at least one second encounter specifying the first detected device.

10. The computer-readable storage medium of claim 9, the operations further comprising:

generating a trajectory comprising the first encounter and the second encounter.

11. The computer-readable storage medium of claim 7, wherein estimating a route for the determined at least one trip comprises:

identifying a plurality of potential routes for the at least one trip, each route having a plurality of associated route segments;

for each of the identified plurality of potential routes,

for each of the route segments associated with the potential route,

determining a cost for the route segment,

determining a popularity for the route segment, and

determining a score for the route segment based at least in part on the determined cost and the determined route,

determining a route score for the potential route based at least in part on the scores determined for the route segments associated with the potential route; and

selecting a route from among the potential routes based at least in part on the determined route scores.

12. The computer-readable storage medium of claim 7, wherein at least one of the plurality of unique devices detected by at least one of the plurality of mobile sensor devices comprises at least one of a watch, a media player, a notebook computer, or a tablet.

13. A computing system, having a memory and a processor, comprising:

a component configured to receive encounter data from each of a plurality of mobile sensor devices, the encounter data comprising a plurality of encounters, each encounter specifying an indication of a device detected by the mobile sensor device, a location, and a time;

a component configured to determine trajectories for each of a plurality of detected devices based at least in part on the received encounter data; and

a component configured to identify, for each of the detected devices, at least one trip comprising a plurality of trajectories and estimate a route for the at least one trip.

14. The computing system of claim 13, further comprising:

a component configured to cluster the determined trajectories for at least a first detected device based at least in part on a speed associated with each trajectory.

15. The computing system of claim 13, further comprising:

a component configured to cluster the determined trajectories for at least a first detected device based at least in part on a location associated with each trajectory.

16. The computing system of claim 13, wherein at least one of the trajectories comprises a first encounter detected by a first mobile sensor device and a second encounter detected by a second mobile sensor device, wherein the first mobile sensor device is different from the second mobile sensor device.

17. The computing system of claim 13, wherein at least one of the devices detected by a first mobile sensor device comprises at least one of a headset, an in-vehicle system, a valve cap, or a thermometer.

18. The computing system of claim 13, wherein at least one of the devices detected by a first mobile sensor device is a mobile sensor device.