Method and apparatus for indoor location estimation among peer-to-peer devices

• US 9,980,097 B2
• Filed: 02/16/2016
• Issued: 05/22/2018
• Est. Priority Date: 05/15/2015
• Status: Active Grant

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Inventors: Narasimha, Murali
• Primary Examiner(s): Sarwar, Babar
• Application Number:
  US15/044,371
• Publication Number:
  US 20160337809A1
• Time in Patent Office: 826 Days
• Field of Search: 4554042, 4554121-4142, 455418-4221, 455436, 455444, 4554352-4353, 455440, 455443, 4555521, 4554561, 4554562, 4554563, 455457, 455 411- 412, 4555501, 455561, 370328, 370338
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/30 Services specially adapted for particular environments, situations or purposes
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Methods and apparatus perform location estimation among peer-to-peer devices. For the various methods, data of several different types, such as received signal strength, timing measurements, time stamps, actual transmit power, etc., is measured, stored, and propagated within a peer-to-peer network to enable each device in the peer-to-peer network to calculate positioning coordinates for one or more devices having unknown positioning coordinates.

Claims

1. A method performed by a first peer-to-peer device, the method comprising:

taking a first set of received signal strength measurements for a first set of signals received from at least one device within a group of devices that includes the first peer-to-peer device and a remaining number of peer-to-peer devices;

recording a first set of time stamps that indicate when the first set of received signal strength measurements were taken;

sending the first set of received signal strength measurements and corresponding first set of time stamps for propagating to the remaining peer-to-peer devices;

receiving a second set of received signal strength measurements taken by the remaining peer-to-peer devices and a second set of time stamps that indicate when the second set of received signal strength measurements were taken;

determining unknown positioning coordinates for at least one peer-to-peer device in the group of devices using at least the first and second sets of received signal strength measurements and the first and second sets of time stamps, wherein the determining comprises correlating the measurements in the first and second sets of received signal strength measurements using the first and second sets of time stamps to define constraints on distances between pairs of devices in the group of devices; and

wherein correlating the measurements in the first and second sets of received signal strength measurements using the first and second sets of time stamps comprises comparing the first set of time stamps to the second set of time stamps to identify multiple device trios each having a different combination of first, second, and third devices of the group of devices, wherein the first and second devices took overlapping received signal strength measurements of a signal sent by the third device, wherein the unknown positioning coordinates are further determined using the overlapping received signal strength measurements associated with each identified device trio.

2. The method of claim 1, wherein correlating the measurements in the first and second sets of received signal strength measurements using the first and second sets of time stamps comprises comparing the first set of time stamps and the second set of time stamps to identify received signal strength measurements that overlap in time, wherein the overlapping measurements are taken for a signal sent from a second peer-to-peer device and are taken by two or more of the other peer-to-peer devices, wherein constraints on distances between the second peer-to-peer device and the two or more of the other peer-to-peer devices are defined using the overlapping measurements.

3. The method of claim 1, wherein the second set of received signal strength measurements includes measurements taken by one or more of the remaining peer-to-peer devices of signals sent by one or more of the other remaining peer-to-peer devices.

4. The method of claim 1, wherein the unknown positioning coordinates are further determined using known positioning coordinates of multiple devices in the group of devices.

5. The method of claim 1 further comprising:

sending a second set of signals;

recording a first set of transmit power values used to send the second set of signals;

recording a third set of timestamps that indicate when the second set of signals was sent;

sending the first set of transmit power values for propagating to the remaining peer-to-peer devices;

wherein the unknown positioning coordinates are further determined using the first set of transmit power values and the third set of timestamps.

6. The method of claim 5 further comprising receiving a second set of transmit power values recorded by the remaining peer-to-peer devices, wherein the unknown positioning coordinates are further determined using the second set of transmit power values.

7. The method of claim 6, wherein correlating the measurements in the first and second sets of received signal strength measurements using the first and second sets of time stamps comprises:

comparing the received second set of time stamps to the recorded third set of time stamps to determine a first subset of the second set of received signal strength measurements that were taken for the second set of signals;

recording first correlations, between the first set of transmit power values and the first subset of the second set of received signal strength measurements, for a first set of peer-to-peer device pairs that each include the first peer-to-peer device;

sending an indication of the first correlations for the first set of peer-to-peer device pairs for propagating to the remaining peer-to-peer devices;

receiving an indication of second correlations, between a first subset of the second set of transmit power values and the first set of received signal strength measurements, for a second set of peer-to-peer device pairs that each include the first peer-to-peer device;

receiving an indication of third correlations, between a remaining second subset of the second set of transmit power values and a remaining second subset of the second set of received signal strength measurements, for a third set of peer-to-peer device pairs that include the remaining peer-to-peer devices excluding the first peer-to-peer device;

wherein the unknown positioning coordinates are determined using the first, second, and third correlations.

8. The method of claim 7 further comprising determining a distance between the devices of each peer-to-peer device pair, associated with the first, second, and third correlations, as a function of a difference between the correlated transmit power value and received signal strength measurement for each peer-to-peer device pair, wherein the unknown positioning coordinates are determined based on the distances.

9. The method of claim 8, wherein the function is TX−

RSS=10n log₁₀d, where TX is the transmit power, RSS is the correlated received signal strength measurement, d is the distance, and n is a path-loss exponent.

10. The method of claim 1 further comprising:

sending a transmission;

recording the start time of the transmission;

receiving an anchor signal from an anchor device in the group of devices, wherein positioning coordinates of the anchor device are known;

recording a first timing measurement indicating a time difference between the start time of the transmission and a time of receipt of the anchor signal;

sending the first timing measurement for propagation to the remaining peer-to-peer devices;

wherein the unknown positioning coordinates are further determined using the first timing measurement.

11. The method of claim 10 further comprising:

receiving a set of timing measurements from the remaining peer-to-peer devices, each timing measurement in the set indicating a time difference between a start time of a signal sent by a different remaining peer-to-peer device and a time of receipt of the anchor signal;

wherein the unknown positioning coordinates are further determined using the set of received timing measurements.

12. The method of claim 11 further comprising:

determining, as a function of the first timing measurement and the set of received timing measurements, a set of propagation delay difference values with each propagation delay difference value indicating, for a different peer-to-peer device pair of the group of devices, a difference in first and second propagation delay values, wherein the first propagation delay value indicates a time of travel of the anchor signal from the anchor device to a first device of the pair, and the second propagation delay value indicates a time of travel of the anchor signal from the anchor device to a second device of the pair;

wherein the unknown positioning coordinates are determined using the set of propagation delay difference values.

13. The method of claim 12 further comprising:

determining, using the set of propagation delay difference values, a set of distance difference values with each distance difference value indicating, for a different peer-to-peer device pair of the group of devices, a difference between first and second distances, wherein the first distance is from the first device of the pair to the anchor device and the second distance is from the second device of the pair to the anchor device;

wherein the unknown positioning coordinates are determined using the set of distance difference values.

14. The method of claim 12 further comprising:

recording a first transmit power value used to send the transmission;

receiving a second set of transmit power values recorded by the remaining peer-to-peer devices;

determining, for each peer-to-peer device pair and using the first and second sets of received signal strength measurements, the first and second sets of time stamps, the first transmit power value, and the second set of transmit power values, a difference between a correlated transmit value and received signal strength measurement for a signal sent between the first and second devices of the pair,

determining, for each peer-to-peer device pair and using the difference between the correlated transmit value and received signal strength measurement, a device pair propagation delay value;

wherein the set of propagation delay difference values is determined using the device pair propagation delay values.

15. The method of claim 1, wherein the unknown positioning coordinates are determined based on a difference between the overlapping received signal strength measurements associated with each identified device trio.

16. The method of claim 15 further comprising determining, for each identified device trio and as a function of the difference between the overlapping received signal strength measurements, a distance ratio of a distance between the second and third devices to a distance between the first and third devices, wherein the unknown positioning coordinates are further determined based on the distance ratios.

17. The method of claim 16, wherein the function is Δ

RSS_D3=10n log₁₀(d₂₃/d₁₃), where Δ

RSS_D3 is the difference between the overlapping received signal strength measurements, d₂₃/d₁₃ is the distance ratio, and n is a path-loss exponent.