Self-organizing hybrid indoor location system

• US 9,791,540 B2
• Filed: 12/14/2015
• Issued: 10/17/2017
• Est. Priority Date: 12/14/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Want, Roy, Jain, Ravi
• Primary Examiner(s): SIVJI, NIZAR N
• Application Number:
  US14/967,477
• Publication Number:
  US 20170168135A1
• Time in Patent Office: 673 Days
• CPC Class Codes: G01S 1/042 Transmitters
• CPC Class Codes: G01S 1/74 Details
• CPC Class Codes: G01S 11/16 using difference in transit time between electrical and acoustic signals
• CPC Class Codes: G01S 5/02585 at least one of the measurements being a non-radio measurement
• CPC Class Codes: G01S 5/0269 Inferred or constrained positioning, e.g. employing knowledge of the physical or electromagnetic environment, state of motion or other contextual information to infer or constrain a position
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: G01S 5/10 Position of receiver fixed by co-ordinating a plurality of position lines defined by path-difference measurements , e.g. omega or decca systemsG01S5/12 takes precedence ; beacons and receivers cooperating therewith G01S1/306, G01S1/308
• CPC Class Codes: G01S 5/14 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: G01S 5/30 Determining absolute distances from a plurality of spaced points of known location
• CPC Class Codes: H04W 4/33 for indoor environments, e.g. buildings
• CPC Class Codes: H04W 4/40 for vehicles, e.g. vehicle-to-pedestrians [V2P]

Abstract

Systems and methods for identifying device location are provided. The method can include providing, by a mobile computing device, at least a first ultrasonic signal to a first and a second self-organizing beacon device. The method can include receiving, by the mobile computing device, a first radio frequency signal including the location of the first beacon device and a second radio frequency signal including the location of the second beacon device. The method can further include determining a first time-of-flight associated with the first beacon device and a second time-of-flight associated with the second beacon device. The method can include determining a location of the mobile computing device based at least in part on the first time-of-flight, the second time-of-flight, the location of the first beacon device, and the location of the second beacon device.

Claims

1. A computer-implemented method of identifying device location, comprising:

providing, by a mobile computing device, at least a first ultrasonic signal to a first beacon device and a second beacon device, wherein the first beacon device and the second beacon device are a portion of a plurality of beacon devices,

wherein the first beacon device is configured to determine a first location of the first beacon device by communicating with one or more other beacon devices of the plurality of beacon devices that comprises the first beacon device, and

wherein the second beacon device is configured to determine a second location of the second beacon device by communicating with one or more other beacon devices of the plurality of beacon devices that comprises the second beacon device;

receiving, by the mobile computing device, a first radio frequency signal from the first beacon device, wherein the first radio frequency signal comprises information associated with the first beacon device, wherein the information associated with the first beacon device comprises the first location of the first beacon device;

receiving, by the mobile computing device, a second radio frequency signal from the second beacon device, wherein the second radio frequency signal comprises information associated with the second beacon device, wherein the information associated with the second beacon device comprises the second location of the second beacon device;

determining, by the mobile computing device, a first time-of-flight associated with the first beacon device and a second time-of-flight associated with the second beacon device;

determining, by the mobile computing device, a third location of the mobile computing device based at least in part on the first time-of-flight, the second time-of-flight, the information associated with the first beacon device, and the information associated with the second beacon device, and providing information indicative of the location of the mobile device.

2. The computer-implemented method of claim 1, wherein the beacon-locating signals comprise ultra-wideband (UWB) signals.

3. The computer-implemented method of claim 1, wherein the first radio frequency signal and the second radio frequency signal respectively comprise Bluetooth low energy packets.

4. The computer-implemented method of claim 1, wherein the information associated with the first beacon device and the information associated with the second beacon device respectively comprise a condition of an environment around the respective beacon device.

5. The computer-implemented method of claim 1, wherein determining, by the mobile computing device, the third location of the mobile computing device comprises:

determining, by the mobile computing device, a first potential location and a second potential location of the mobile computing device based at least in part on the first time-of-flight, the second time-of-flight, the information associated with the first beacon device, and the information associated with the second beacon device; and

identifying, by the mobile computing device, the first potential location or the second potential location as the third location of the mobile computing device based at least in part on data describing a floorplan of an interior of a building within which the first and the second beacon devices are located.

6. The computer-implemented method of claim 1, wherein the first and the second beacon devices are within a common area and wherein determining, by the mobile computing device, the third location of the mobile computing device comprises:

determining, by the mobile computing device, a first potential location and a second potential location of the mobile computing device based at least in part on the first time-of-flight, the second time-of-flight, the information associated with the first beacon device, and the information associated with the second beacon device; and

identifying, by the mobile computing device, the first potential location or the second potential location as the third location of the mobile computing device by determining which of the first potential location or the second potential location is associated with the common area.

7. The computer implemented method of claim 1, wherein the information associated with the first beacon device comprises a first transmission time of the first radio frequency signal from the first beacon device and the information associated with the second beacon device comprises a second transmission time of the second radio frequency signal from the second beacon device, and

wherein determining, by the mobile computing device, the first time-of-flight associated with the first beacon device and the second time-of-flight associated with the second beacon device, comprises:

determining, by the mobile computing device, a first receipt time for the first radio frequency signal and a second receipt time for the second radio frequency signal, wherein the first receipt time indicates a first time at which the first radio frequency signal is received by the mobile computing device and the second receipt time indicates a second time at which the second radio frequency signal is received by the mobile computing device;

determining, by the mobile computing device, the first time-of-flight associated with the first beacon device based at least in part on the first transmission time of the first radio frequency signal and the first receipt time of the first radio frequency signal; and

determining, by the mobile computing device, the second time-of-flight associated with the second beacon device based at least in part on the second transmission time of the second radio frequency signal and the second receipt time of the first radio frequency signal.

8. The computer implemented method of claim 1, wherein the information associated with the first beacon device comprises a first receipt time that indicates when the first beacon device received the first ultrasonic signal, and the information associated with the second beacon device comprises a second receipt time that indicates when the second beacon device received the first ultrasonic signal, and

wherein determining, by the mobile computing device, the first time-of-flight associated with the first beacon device and the second time-of-flight associated with the second beacon device, comprises:

determining, by the mobile computing device, a transmission time of the first ultrasonic signal that indicates when the mobile computing device provided the first ultrasonic signal;

determining, by the mobile computing device, the first time-of-flight associated with the first beacon device based at least in part on the transmission time of the first ultrasonic signal and the first receipt time; and

determining, by the mobile computing device, the second time-of-flight associated with the second beacon device based at least in part on the transmission time of the first ultrasonic signal and the second receipt time.

9. The computer implemented method of claim 1, wherein the information associated with the first beacon device comprises a first time delay that indicates a time difference between when the first beacon device received the first ultrasonic signal and provided the first radio frequency signal, and the information associated with the second beacon device comprises a second time delay that indicates a time difference between when the second beacon device received the first ultrasonic signal and provided the second radio frequency signal, and

wherein determining, by the mobile computing device, the first time-of-flight associated with the first beacon device and the second time-of-flight associated with the second beacon device, comprises:

determining, by the mobile computing device, a transmission time of the first ultrasonic signal that indicates when the mobile computing device provided the first ultrasonic signal;

determining, by the mobile computing device, a first receipt time for the first radio frequency signal and a second receipt time for the second radio frequency signal, wherein the first receipt time indicates a first time at which the first radio frequency signal is received by the mobile computing device and the second receipt time indicates a second time at which the second radio frequency signal is received by the mobile computing device;

determining, by the mobile computing device, the first time-of-flight associated with the first beacon device based at least in part on the transmission time of the first ultrasonic signal, the first time delay, and the first receipt time; and

determining, by the mobile computing device, the second time-of-flight associated with the second beacon device based at least in part on the transmission time of the first ultrasonic signal, the second time delay, and the second receipt time.

10. A mobile computing device comprising:

one or more processors; and

one or more memory devices storing computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations, the operations comprising;

providing a plurality of first signals to two or more beacon devices, wherein the plurality of first signals comprise ultrasonic signals, wherein the two or more beacon devices are included in a plurality of beacon devices, and wherein each of the two or more beacon devices is configured to communicate with the plurality of beacon devices that includes the two or more beacon devices to determine its respective location, and

receiving a plurality of second signals from the two or more beacon devices, wherein the plurality of second signals comprise radio frequency signals, and wherein each of the plurality of second signals comprises data indicative of the location of one of the two or more beacon devices;

determining two or more times-of-flight respectively associated with the two or more beacon devices;

determining a location of the mobile computing device based at least in part on the two or more times-of-flight respectively associated with the two or more beacon devices and the locations of each of the two or more beacon devices, and providing information indicative of the location of the mobile device.

11. The mobile computing device of claim 10, wherein each of the two or more beacon devices is configured to communicate with the plurality of beacon devices to determine its respective location by sending and receiving a plurality of beacon-locating signals.

12. The mobile computing device of claim 11, wherein the beacon-locating signals are ultra-wideband (UWB) signals.

13. The mobile computing device of claim 10, wherein the second signals comprise Bluetooth low energy packets.

14. The mobile computing device of claim 10, wherein each of the two or more beacon devices are associated with a common area and wherein determining the location of the mobile computing device comprises:

determining a first potential location and a second potential location of the mobile computing device based at least in part on the two or more times-of-flight respectively associated with the two or more beacon devices and the locations of each of the two or more beacon devices; and

identifying, by the mobile computing device, the first potential location or the second potential location as the location of the mobile computing device by determining which of the first potential location or the second potential location is associated with the common area.

15. A beacon device, comprising:

an ultrasonic receiver;

a radio frequency transmitter;

one or more processors; and

one or more memory devices storing computer-readable instructions that when executed by the one or more processors cause the beacon device to perform operations, the operations comprising;

sending one or more first beacon-locating signals to one or more other beacon devices of a plurality of beacon devices that includes the beacon device;

receiving one or more second beacon-locating signals from the one or more other beacon devices of the plurality of beacon devices that includes the beacon device;

determining a location of the beacon device based, at least in part, on one or more of the first beacon-locating signals or the second beacon-locating signals;

receiving, by the ultrasonic receiver, one or more ultrasonic signals from a mobile computing device; and

providing, by the radio frequency transmitter, one or more radio frequency signals to the mobile computing device in response to the one or more ultrasonic signals, wherein the one or more radio frequency signals comprise data indicative of the location of the beacon device.

16. The beacon device of claim 15, wherein the first beacon-locating signals and the second beacon-locating signals are ultra-wideband (UWB) signals.

17. The beacon device of claim 15, wherein the radio frequency signals comprise Bluetooth low energy packets.

18. The beacon device of claim 15, wherein the beacon device comprises an anchor beacon device that has a reference location that has been confirmed relative to an existing coordinate system, the anchor beacon device configured to provide the one or more first beacon-locating signals that comprise the reference location of the anchor beacon.

19. The beacon device of claim 15, wherein the radio frequency signals further comprise data describing a floorplan of an interior of a building with which the beacon device is located.

20. The beacon device of claim 19, wherein the data describing the floorplan comprises data indicative of a particular area of the building in which the beacon device is located.