Cloud-coordinated location system using ultrasonic pulses and radio signals

• US 9,609,482 B1
• Filed: 12/07/2015
• Issued: 03/28/2017
• Est. Priority Date: 12/07/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Want, Roy, Schilit, William Noah
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US14/961,029
• Time in Patent Office: 477 Days
• US Class Current: 1/1
• CPC Class Codes: G01S 11/16 using difference in transit time between electrical and acoustic signals
• 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: H04L 67/01 Protocols
• CPC Class Codes: H04W 12/06 Authentication
• CPC Class Codes: H04W 36/322 by location data
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 40/244 using a network of reference devices, e.g. beaconing
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

In general, this disclosure describes location techniques for a mobile device. A mobile device may request permission from a server device to perform a ranging operation. Responsive to receiving an indication of allowance, the mobile device may output a first data packet via a radio signal, which is received by a beacon device that activates an ultrasonic transponder upon receipt of the first data packet. The mobile device then outputs a second data packet via an ultrasonic pulse. The beacon device receives the ultrasonic pulse and outputs a third data packet via a second radio signal that includes information identifying the beacon device. The mobile device calculates a time difference between outputting the ultrasonic pulse and receiving the second radio signal and determines its location based on the third data packet and the time difference.

Claims

1. A method comprising:

outputting, by a mobile computing device, a first radio signal that includes a first data packet, wherein the first data packet includes information indicating that the mobile computing device is requesting initiation of a ranging operation, wherein the ranging operation comprises an operation performed by the mobile computing device to determine a location of the mobile computing device;

after outputting the first radio signal, outputting, by the mobile computing device, an ultrasonic pulse that includes a second data packet;

after outputting the ultrasonic pulse, receiving, by the mobile computing device, a second radio signal that includes a third data packet from a beacon device, wherein the third data packet includes information identifying the beacon device as a source of the third data packet;

determining, by the mobile computing device, a time difference between outputting the ultrasonic pulse and receiving the second radio signal; and

determining, by the mobile computing device and based at least in part on the third data packet and the time difference, the location of the mobile computing device.

2. The method of claim 1, wherein the first data packet activates an ultrasonic transponder operatively connected to the beacon device.

3. The method of claim 1, further comprising:

prior to outputting the first radio signal;

sending, by the mobile computing device, a request to perform the ranging operation to a server device; and

receiving, by the mobile computing device and from the server device, an indication that the mobile computing device is permitted to perform the ranging operation.

4. The method of claim 3, wherein outputting the first radio signal comprises outputting the first radio signal responsive to receiving the indication that the mobile computing device is permitted to perform the ranging operation from the server device.

5. The method of claim 1, wherein determining the location of the mobile computing device comprises:

multiplying, by the computing device, the time difference by an output speed of the ultrasonic pulse to determine a distance radius;

determining, by the computing device, a location of the beacon device based at least in part on the information in the third data packet; and

determining, by the computing device, the location of the mobile computing device based at least in part on the distance radius and the location of the beacon device.

6. The method of claim 5, wherein the beacon device is a first beacon device, the method further comprising:

after outputting the ultrasonic pulse, receiving, by the mobile computing device, a third radio signal that includes a fourth data packet from a second beacon device, wherein the fourth data packet includes information identifying the second beacon device as a source of the fourth data packet;

after outputting the ultrasonic pulse, receiving, by the mobile computing device, a fourth radio signal that includes a fifth data packet from a third beacon device, wherein the fifth data packet includes information identifying the third beacon device as a source of the fifth data packet;

determining, by the mobile computing device, a second time difference between outputting the ultrasonic pulse and receiving the third radio signal;

determining, by the mobile computing device, a third time difference between outputting the ultrasonic pulse and receiving the fourth radio signal;

multiplying, by the computing device, the second time difference by the output speed of the ultrasonic pulse to determine a second distance radius;

multiplying, by the computing device, the third time difference by the output speed of the ultrasonic pulse to determine a third distance radius;

determining, by the computing device, a location of the second beacon device based at least in part on the information in the fourth data packet; and

determining, by the computing device, a location of the third beacon device based at least in part on the information in the fifth data packet,

wherein determining the location of the mobile computing device comprises determining, by the computing device, the location of the mobile computing device based at least on the first distance radius, the location of the first beacon device, the second distance radius, the location of the second beacon device, the third distance radius, and the location of the third beacon device.

7. The method of claim 1, wherein the first data packet and the second data packet further include information identifying the mobile computing device as a source of the first data packet and the second data packet and a coarse-grained location of the mobile computing device.

8. The method of claim 1, wherein the first radio signal and the second radio signal are Bluetooth low energy signals.

9. The method of claim 1, wherein the mobile computing device comprises a radio antenna and an ultrasonic transponder.

10. The method of claim 9, further comprising:

after outputting the first radio signal, activating the ultrasonic transponder; and

after outputting the ultrasonic pulse, deactivating the ultrasonic transponder.

11. The method of claim 1, wherein the second data packet includes information identifying the mobile computing device as the source of the second data packet, and wherein the third data packet further includes the information identifying the mobile computing device, a temperature of an environment associated with the beacon device, a humidity of the environment associated with the beacon device, and a random time delay for processing the second data packet at the beacon device.

12. A method comprising:

receiving, by a beacon device using a radio antenna, a first radio signal that includes a first data packet, wherein the first radio signal is output by a mobile computing device, and wherein the first data packet includes information indicating that the mobile computing device is requesting initiation of a ranging operation, wherein the ranging operation comprises an operation performed by the mobile computing device to determine a location of the mobile computing device;

responsive to receiving the first radio signal that includes the first data packet, activating, by the beacon device, an ultrasonic transponder;

receiving, by the beacon device using the ultrasonic transponder, an ultrasonic pulse that includes a second data packet, wherein the ultrasonic pulse is output by the mobile computing device; and

responsive to receiving the second data packet, outputting, by the beacon device using the radio antenna, a second radio signal that includes a third data packet, wherein the third data packet includes information identifying the beacon device as a source of the third data packet.

13. The method of claim 12, wherein the third data packet further includes a geographical location of the beacon device, a temperature of an environment around the beacon device, a humidity of the environment around the beacon device, and a random time delay for processing the second data packet at the beacon device.

14. The method of claim 12, further comprising:

after outputting the second radio signal, deactivating, by the beacon device, the ultrasonic transponder.

15. The method of claim 12, wherein the second data packet further includes information identifying the mobile computing device as the source of the second data packet, and wherein the third data packet further includes the information identifying the mobile computing device.

16. A method comprising:

receiving, by a server device and from a first mobile computing device, a first request to perform a ranging operation, wherein the ranging operation comprises an operation performed by the respective mobile computing device to determine a location of the respective mobile computing device;

receiving, by the service device and from a second mobile computing device, a second request to perform the ranging operation;

determining, by the server device, a first starting time at which the first mobile computing device is permitted to perform the ranging operation;

determining, by the server device, a second starting time at which the second mobile computing device is permitted to perform the ranging operation, wherein the second starting time is later than the first starting time;

outputting, by the server device and to the first mobile computing device, a first indication that, at the first starting time, the first mobile computing device is permitted to perform the ranging operation; and

outputting, by the server device and to the second mobile computing device, a second indication that, at the second starting time, the second mobile computing device is permitted to perform the ranging operation.

17. The method of claim 16, wherein the second starting time is at least a predefined operational period after the first starting time.

18. The method of claim 17, further comprising:

outputting, by the server device and to the first mobile computing device, the first indication at the first starting time; and

after the predefined operational period has passed, outputting, by the server device and to the second mobile computing device, the second indication at the second starting time.

19. The method of claim 16, wherein the first request and the second request each include a coarse-grained location of the first mobile computing device and the second mobile computing device, wherein the coarse-grained location for the first mobile computing device is the same as the coarse-grained location for the second mobile computing device, wherein the method further comprises:

responsive to receiving the first request, storing, by the server device, an identifier of the first mobile computing device in a first area queue of a plurality of area queues, wherein each area queue is associated with a distinct coarse-grained location, and wherein the first area queue is associated with the coarse-grained location included in the first request and the coarse-grained location included in the second request;

responsive to receiving the second request, storing, by the server device, an identifier of the second mobile computing device in the first area queue;

responsive to outputting the first indication, dequeueing, by the server device, the identifier of the first mobile computing device from the first area queue; and

responsive to outputting the second indication, dequeueing, by the server device, the identifier of the second mobile computing device from the first area queue.

20. A method comprising:

receiving, by a server device and from a first mobile computing device, a first request to perform a ranging operation, wherein the ranging operation comprises an operation performed by the respective mobile computing device to determine a location of the respective mobile computing device;

receiving, by the service device and from a second mobile computing device, a second request to perform the ranging operation;

determining, by the server device, a first starting time at which the first mobile computing device is permitted to perform the ranging operation;

at the first starting time, outputting, by the server device and to the first mobile computing device, a first indication that the first mobile computing device is permitted to perform the ranging operation;

after outputting the first indication, receiving, by the server device and from the first mobile computing device, a second indication that the first mobile computing device has completed the ranging operation; and

responsive to receiving the second indication, at a second starting time, outputting, by the server device and to the second mobile computing device, a third indication that the second mobile computing device is permitted to perform the ranging operation.