Many-to-many wireless network ranging technique

Disclosed are methods, systems, and computer-readable medium to perform operations comprising periodically broadcasting, by a first wireless device, outgoing ranging packets on a measurement channel of a wireless network; receiving, by the first wireless device on the measurement channel and from a second wireless device, a plurality of incoming ranging data packets; and calculating, by the first wireless device and using a three ranging packet exchange with the second wireless device, a range to the second wireless device.

TECHNICAL FIELD

This disclosure relates to wireless network ranging techniques.

BACKGROUND

A wireless device can use various positioning systems to determine its location. For example, the wireless device can use the Global Positioning System (GPS) or other satellite-based systems. The wireless device may also share its determined position with other devices. However, in various scenarios, such as when there is poor satellite connectivity, the wireless device may not be able to use positioning systems to determine its location.

SUMMARY

For various reasons, it is useful for wireless devices to determine ranges to other nearby wireless devices (called peer devices). For example, a wireless device can determine the locations of the nearby wireless devices based on the ranges to those devices. One way for wireless devices to determine the range to one another is to exchange packets and determine the range based on the time-of-flight (ToF) of the exchanged packets. Existing ToF ranging techniques are one-to-one ranging techniques, where one device exchanges two packets with another device to determine the ToF to that device. Such ranging techniques may be successful when there are two devices involved. However, if more than two devices are involved, then these ranging techniques are subject to collisions that may cause the techniques to fail. For example, if two devices try to simultaneously determine a range to a third device, only one of the two devices may succeed. Given the potential number of wireless devices that may be in proximity, existing ranging techniques may not be sufficient. Existing ranging techniques also suffer from other deficiencies, such as requiring a central coordinator and consuming a significant amount of resources (e.g., battery power, computing power, and time).

This disclosure describes techniques for performing ToF-based ranging between many wireless devices (e.g., on the order of 3, 5, 10, or more devices) that are in proximity (e.g., in a range in which the devices can exchange packets). In a full mesh technique, a device determines respective ranges to multiple other wireless devices. In some embodiments, each device accesses a measurement channel of a wireless network (e.g., a Wi-Fi network) for a measurement period. During the measurement period, a participating device periodically broadcasts one or more ranging packets and listens for ranging packets that are broadcast by the other devices. A wireless device then uses three ranging packet exchanges with other devices to calculate the ranges to the other devices. For example, a first device uses a three ranging packet exchange with a second device to calculate a range to the second device, and vice versa. The ranging calculation is based on transmit/receive times of the three ranging packets exchanged between the devices. In order for each device to have the necessary values to perform the ranging calculations, each device includes, in the ranging packets that it broadcasts, information about the ranging packets that the device has previously received and/or transmitted.

In accordance with aspects of the present disclosure, a method for ranging by a first wireless device is disclosed. The method involves periodically broadcasting outgoing ranging packets on a measurement channel of a wireless network at respective broadcast intervals; receiving, on the measurement channel and from a second wireless device, a plurality of incoming ranging data packets at respective receive times; and calculating, using a three ranging packet exchange with the second wireless device, a range to the second wireless device.

The previously-described implementation can be performed using a computer-implemented method; a non-transitory, computer-readable medium storing computer-readable instructions to perform the computer-implemented method; a processor including circuitry to execute one or more instructions that, when executed, cause the processor to perform the computer-implemented method; and a computer system including a computer memory interoperably coupled with a hardware processor configured to perform the computer-implemented method or the instructions stored on the non-transitory, computer-readable medium. These and other embodiments may each optionally include one or more of the following features.

In some implementations, the first and second wireless devices are configured to access the measurement channel for a measurement period in response to a trigger.

In some implementations, the three ranging packet exchange comprises three subsequent ranging packets including: (i) first and second outgoing ranging packets broadcast by the first wireless device, and (ii) an incoming ranging packet broadcast by the second wireless device and received by the first wireless device.

In some implementations, calculating the range based on a transmit time (t1) of the first outgoing ranging packet, a receipt time (t2) of the first outgoing ranging packet at the second wireless device, a transmit time (t3) of the incoming ranging packet by the second wireless device, a receipt time (t4) of the incoming ranging packet at the first wireless device, a transmit time (t5) of the second outgoing ranging packet, and a receipt time (t6) of the second outgoing ranging packet at the second wireless device.

In some implementations, calculating the range to the second wireless device based on t1, t2, t3, t4, t5, and t6 comprises: calculating a roundtrip time (RTT) to the second wireless devices using: RTT: (t4−T1)(1+PPM)−(t3−t2), and RTT: −(t5−T4)(1+PPM)+(t6−t3); and calculating, based the RTT, the range to the second wireless device, wherein PPM is a clock offset between the first wireless device and the second wireless device.

In some implementations, the method further involves: calculating, using the three ranging packet exchange with the second wireless device, a clock offset with the second wireless device.

In some implementations, a first outgoing ranging packet of the outgoing ranging packets comprises: (i) an egress report that includes information indicative of one or more previously broadcast outgoing ranging packets sent by the first wireless device, (ii) a peer ingress report that includes information indicative of one or more previously received incoming ranging packets from at least the second wireless device, and (iii) one or more local receive times associated with the one or more previously received incoming ranging packets.

In some implementations, a first incoming ranging packet of the plurality of incoming ranging packets comprises: (i) an egress report that includes information indicative of one or more previously broadcast outgoing ranging packets sent by the second wireless device, (ii) a peer ingress report that includes information indicative of one or more previously received incoming ranging packets from at least the first wireless device, and (iii) one or more local receive times associated with the one or more previously received incoming ranging packets.

In some implementations, the method further involves: storing in a local database associated with the second wireless device: (i) local receive times of the plurality of incoming ranging data packets, (ii) the egress reports associated with the plurality of incoming ranging data packets, and (iii) the receive times at the second wireless device of the outgoing ranging packets broadcast by the first wireless device.

In accordance with other aspects of the present disclosure, another method to be performed by a first wireless device determining a range to a second wireless device is disclosed. The method involves broadcasting, on a measurement channel of a wireless network, a first ranging packet at a first time (t1), wherein the first ranging packet is received by the second wireless device at a second time (t2); receiving a second ranging packet from the second wireless device, the second ranging packet transmitted by the second wireless device at a third time (t3) and received by the first wireless device at a fourth time (t4) broadcasting a third ranging packet at a fifth time (t5), wherein the third ranging packet is received by the second wireless device at a sixth time (t6); and calculating a range to the second wireless device based on t1, t2, t3, t4, t5, and t6.

The previously-described implementation can be performed using a computer-implemented method; a non-transitory, computer-readable medium storing computer-readable instructions to perform the computer-implemented method; a processor including circuitry to execute one or more instructions that, when executed, cause the processor to perform the computer-implemented method; and a computer system including a computer memory interoperably coupled with a hardware processor configured to perform the computer-implemented method or the instructions stored on the non-transitory, computer-readable medium. These and other embodiments may each optionally include one or more of the following features.

In some implementations, calculating a range to the second wireless device based on t1, t2, t3, t4, t5, and t6 involves calculating a roundtrip time (RTT) to the second wireless device using: RTT: (t4−T1)(1+PPM)−(t3−t2), and RTT: −(t5−T4)(1+PPM)+(t6−t3); and calculating, based the RTT, the range to the second wireless device, wherein PPM is a clock offset between the first wireless device and the second wireless device.

In some implementations, the method further involves calculating a clock offset between the first wireless device and the second wireless device.

In some implementations, the method further involves receiving, a fourth ranging packet from the second wireless device, wherein the fourth ranging packet includes information indicative of t2, t3, and t6.

The subject matter described in this specification can be implemented to realize one or more of the following advantages. The disclosed ranging techniques can achieve ranging between many wireless devices (e.g., on the order of 3, 5, 10+ or 20+ devices), which cannot be achieved using existing ranging techniques. Additionally, by virtue of being a full mesh technique, the disclosed techniques do not have a single point of failure. Thus, even if a single device fails, the ranging calculations between the other devices are unaffected. The disclosed techniques also are resilient to hidden nodes. And compared to existing ranging techniques, the disclosed techniques have a shorter measurement duration, perform better in congested conditions, have better reliability and resiliency, use less power, and have greater ranging accuracy. Additionally, unlike existing techniques, the disclosed ranging techniques account for and calculate clock offsets between devices, which further improves the ranging accuracy.

DETAILED DESCRIPTION

This disclosure describes techniques for performing time-of-flight (ToF)-based ranging between multiple wireless devices (e.g., including 10 or more devices) that are in proximity. In these full mesh techniques, each device can determine respective ranges to other nearby wireless devices. In some embodiments, each device accesses a wireless measurement channel for a measurement period. During the measurement period, a device periodically broadcasts ranging packets and listens for ranging packets that are broadcast by other devices. The wireless devices then use three ranging packet exchanges with other devices to calculate the ranges to one another. For example, a first device uses a three ranging packet exchange with a second device to calculate a range to that device. The second device also can use a three ranging packet exchange with the first device to calculate a range to the first device. In particular, the ranging calculation is based on transmit/receive times of the three ranging packets that are exchanged between the devices. In order for each device to have the necessary information (e.g., transmit/receive times) for the ranging calculations, each device includes, in the ranging packets that it broadcasts, information about the ranging packets that the device has previously received and/or transmitted.

FIG.1illustrates a wireless communication system100, according to some implementations. As shown inFIG.1, the wireless communication system100includes a (“first”) wireless device102, a (“second”) wireless device104, and a (“third”) wireless device106that may wirelessly communicate with one another. As described herein, the wireless devices102-106may use the disclosed ranging techniques to determine ranges to one another. Note that the wireless communication system100is shown for illustration purposes only, as the wireless communication system100may include more or fewer wireless devices without departing from the scope of the disclosure.

In some embodiments, the wireless devices102-106may communicate using any of a number of wireless communication techniques. The wireless devices102-106can communicate using wireless local area networking (WLAN) communication technology (e.g., IEEE 802.11/Wi-Fi based communication) and/or techniques based on WLAN wireless communication. Additionally, the wireless devices102-106may communicate via one or more other wireless communication protocols, such as Bluetooth (BT), Bluetooth Low Energy (BLE), near field communication (NFC), GSM, UMTS (WCDMA, TDSCDMA), LTE, LTE-Advanced (LTE-A), 5G NR, 3GPP2 CDMA2000 (e.g., 1×RTT, 1×EV-DO, HRPD, eHRPD), among other wireless communication protocols.

The wireless devices102-106may each be implemented by a computing system, such as the computing system600ofFIG.6. More specifically, the wireless devices102-106may be any of a number of wireless device types. As an example, one or more of the wireless devices102-106may be a substantially portable wireless user equipment (UE) device, such as a smart phone, a hand-held device, a wearable device (e.g., a smart watch), a tablet, a motor vehicle, or any other type of wireless device. As another example, one or more of the wireless devices102-106may be a substantially stationary device, such as a set top box, media player (e.g., an audio or audiovisual device), gaming console, desktop computer, appliance, door, access point, base station, among other examples of stationary devices.

In some embodiments, wireless devices, e.g., the wireless devices102-106, may engage in a “many-to-many” ranging technique. In full mesh techniques, each wireless device determines or estimates a range (e.g., distance) to other wireless devices (also called peer devices). By enabling each wireless device to estimate the range to other wireless devices, the many-to-many ranging techniques allow each wireless device to accurately determine the locations of other wireless devices in the mesh. Note that in many-to-many ranging techniques, the wireless devices do not have to be connected to the same wireless network, let alone be connected to any wireless infrastructure network at all. Thus, the techniques can be implemented by any wireless devices in proximity, irrespective of whether the devices are on the same network.

In some embodiments, to implement a many-to-many ranging technique, the wireless devices access a channel of a wireless network that is designated as a measurement channel. Within examples, one of one or more triggers can cause the wireless devices to access the measurement channel in order to implement the ranging techniques. One example trigger is an amount of time elapsed since the wireless devices last accessed the measurement channel, such that the wireless devices periodically access the measurement channel. The periodicity at which the wireless devices access the measurement channel can be any period of time, e.g., on the order of less than a second, one or more seconds, one or more minutes, or tens of minutes. In an example, the wireless devices access the measurement channel every two minutes. The measurement channel can be any available channel in a wireless network. For example, in a Wi-Fi network, the channel can be Channel 6 (CH 6). However, any channel can be selected.

In some embodiments, the wireless devices access the measurement channel for a measurement period. The measurement period can by any period of time. By way of example, the measurement period can be on the order of milliseconds (ms), tens of ms, or hundreds of ms. In an example, the measurement period is 350 ms. During the measurement period, each wireless device periodically broadcasts ranging packets that can be received by other wireless devices. Additionally, each wireless device listens for and receives ranging packets from other wireless devices. The broadcasting period at which the wireless devices broadcast the ranging packets can be any period of time, By way of example, the broadcasting period can be on the order of ms, tens of ms, or hundreds of ms. In an example, the broadcasting period is 70 ms.

FIG.2illustrates an example200of ranging packets broadcast by a wireless device, according to some implementations. The wireless device (not illustrated inFIG.2) is configured to access a measurement channel (e.g., in response to one or more triggers) for a measurement period, tm. During the measurement period, the wireless device periodically broadcasts a ranging packet, e.g., every broadcasting period, tb. As shown inFIG.2, the wireless device broadcasts a first ranging packet202aat time t1, a second ranging packet202bat time t1+tb, a third ranging packet202cat time t1+2tb, and a fourth ranging packet202dat time t1+3tb. Note that the number of ranging packets that are broadcast during the measurement period is based on the lengths of the measurement and broadcasting periods. In addition to broadcasting ranging packets, the wireless device also can receive ranging packets broadcast by one or more of the wireless device's peer devices during the measurement period.

In some embodiments, a wireless device uses a three ranging packet exchange with a peer device in order to calculate the range to that peer device. The three ranging packet exchange is any three ranging packets that are exchanged between the wireless device and the peer device. As an example, a three ranging packet exchange can include two ranging packets broadcast by the wireless device and received by the peer device, and one ranging packet broadcast by the peer device and received by the wireless device (e.g., any 2×TX+1×RX packets). As another example, a three ranging packet exchange can include one ranging packet broadcast by the wireless device and received by the peer device, and two ranging packets broadcast by the peer device and received by the wireless device (i.e., any 2×RX+1×T1 packets).

In some embodiments, the wireless device can use transmit and receive times of the three ranging packets exchanged with the peer device in order to calculate a round trip time (RTT) to the peer device. In the example where a wireless device transmits two packets and receives one packet, the RTT calculation is based on six variables: a transmit time (t1) of a first ranging packet broadcast by the wireless device, a receipt time (t2) of the first ranging packet at the peer device, a transmit time (t3) of a second ranging packet by the peer device, a receipt time (t4) of the second ranging packet at the wireless device, a transmit time (t5) of a third ranging packet broadcast by the wireless device, and a receipt time (t6) of the third ranging packet at the peer device. From the calculated RTT, the wireless device calculates the ToF to the peer device. Using a three ranging packet exchange, e.g., as opposed to the two ranging packet exchange used in some existing techniques, allows the wireless device to calculate and compensate for a clock offset with the peer device. The clock offset can be expressed in any appropriate unit, such as parts per million (PPM).

In some embodiments, the RTT from the wireless device to the peer device is calculated using Equations (1) and (2).
RTT:(t4−t1)(1+PPM)−(t3−t2)  Equation (1)
RTT: −(t5−t4)(1+PPM)+(t6−t3)  Equation (2)
Then, the wireless device uses Equation (3) to calculate the time of flight to the peer device.

ToF⁢:⁢RTT2Equation⁢⁢(3)
As shown in Equations (1) and (2), the round trip calculation accounts for the clock offset between the devices. The wireless device can also calculate the clock offset using Equations (1) and (2). Within examples, the wireless device can calculate the clock offset each time that the device calculates the RTT to the peer device, or can calculate the clock offset at periodic intervals (e.g., once every measurement period).

As stated above, the wireless device uses the transmit and receive times of the three ranging packets exchanged with the peer device in order to calculate the round trip time. However, the wireless device does not know the transmit/receive times at the peer device (e.g., t2, t3, and t6). In some embodiments, in order to facilitate for the wireless device to obtain the values necessary to perform the ranging calculation, each (or a subset) ranging packet includes reports indicative of the ranging packets that were sent and/or received prior to sending that ranging packet. In some scenarios, the reports may be included starting from the fourth ranging packet that is exchanged between the wireless device and the peer device. In an example, the reports of a ranging packet broadcast by the wireless device include: (i) identifiers of the reported ranging packets (e.g., sequence numbers), (ii) identifiers of the peer devices (e.g., a media access control address (MAC address)) that broadcasted the ranging packets received by the wireless device, (iii) receipt times of the received ranging packets, and (iv) transmit times of the ranging packets broadcast by the wireless device.FIG.4(described below) illustrates an example frame structure of a ranging packet.

In some embodiments, when a wireless device receives a ranging packet, the wireless device stores, e.g., in a local database, the reports included in the ranging packet. The stored information can be grouped by peer device and identified by a peer device identifier (e.g., a MAC address). For each peer device, the wireless device stores: (i) local receive times of the ranging packets broadcast by the peer device, (ii) the peer transmit times of the ranging packets broadcast by the peer device, and (iii) the receive times at the peer device of the ranging packets broadcast by the wireless device.FIG.4(described below) also illustrates a local database of a wireless device.

FIG.3AandFIG.3Beach illustrate a communication flow diagram between two wireless devices performing a disclosed ranging technique, according to some implementations. These figures illustrate how a first wireless device, e.g., the wireless device102, implements many-to-many ranging in order to calculate a range to at least a second wireless device, e.g., the wireless device104. Although the illustrated examples depict communication between two wireless devices, similar communication flows can occur between any device and any/all of the other devices participating in the ranging arrangement.

Turning toFIG.3A, the wireless devices102,104are configured to access a measurement channel for a measurement period. At time t1 during the measurement period, the wireless device102broadcasts ranging packet 1 (also labelled as packet302), which is received by the wireless device104at time t2. At time t3, the wireless device104broadcasts ranging packet 2 (also labelled as packet304), which is received by the wireless device102at time t4. At time t5, the wireless device102broadcasts ranging packet 3 (also labelled as packet306), which is received by the wireless device104at time t6.

Now that three ranging packets have been exchanged between the two devices, the wireless device104generates ranging packet 4 (also labelled as packet308) that includes reports indicative of: (i) the receipt time, t2, of the ranging packet 1, (ii) the transmit time, t3, of the ranging packet 2, (iii) and the receipt time, t6, of the ranging packet 3. Each time is identified by a respective identifier (e.g., sequence number) of the ranging packet with which the time is associated. For example, t2 is identified by a sequence number of the ranging packet 1, t3 is identified by a sequence number of the ranging packet 2, and t6 is identified by a sequence number of the ranging packet 3. Additionally, the times t2 and t6 are associated with an identifier of the wireless device102, which indicates that these two times are associated with ranging packets received from the wireless device102. The wireless device104then broadcasts the ranging packet 4 at time t7, which is then received by the wireless device102at time t8.

The wireless device102stores the information included in the ranging packet 4 in a local database. In particular, the wireless device102associates the stored information with an identifier of the wireless device104(e.g., a MAC address of the wireless device104). The wireless device102can use the stored information and its knowledge of times t1, t4, and t5 to calculate the RTT to the wireless device104, e.g., using Equations (1) and (2). From the calculated RTT, the wireless device102can calculate the ToF to the wireless device104, which, in turn, is used to calculate or estimate the range to the wireless device104. Additionally, the wireless device102can calculate a clock offset from the wireless device104.

FIG.3Billustrates a detailed communication flow diagram310between the wireless devices102,104. In the communication flow diagram310, each ranging packet is identified by a respective sequence number. Additionally, the subscript of each time is indicative of the iteration number of a three ranging packet exchange with which the time is associated. For example, a subscript of 1 indicates that the time is associated with a first three ranging packet exchange between the wireless device102,104. Note that because any three ranging packets can constitute a three ranging packet exchange, a time may be associated with more than one three ranging packet exchange.

The communication flow diagram310starts at time t1(1)at which the wireless device102broadcasts a ranging packet312(also identified by sequence number 1). The subscript of t1(1)indicates that the time is associated with a first three ranging packet exchange. The ranging packet312is received by the wireless device104at time t2(1). The wireless device104broadcasts a ranging packet314(also identified by sequence number 11) at time t3(1)or t1(11). The subscript 1 of t3(1)indicates that the time is a third time of the first three ranging packet exchange and the subscript 11 of t1(11)indicates that the time is also a first time of a second three ranging packet exchange. The wireless device102receives the ranging packet314at time t4(1), t2(11). The wireless devices102,104then exchange ranging packet316(also identified by sequence number 2), which is broadcast at time t1(2), t3(11), t5(1)and received at time t2(2), t4(11), t6(1). Now that the first three ranging packet exchange is complete, the wireless device104includes t2(1), t3(1), t6(1)in the next ranging packet that is broadcasts. As shown inFIG.3B, the ranging packet318(also identified by sequence number 12) includes t2(1), t3(1), t6(1). Additionally, the ranging packet318includes an identifier of the wireless device102, which is used to identify t2(1)and t6(1)as being associated with ranging packets broadcast by the wireless device102.

The wireless device102uses the information received in the ranging packet318and t1(1), t4(1), t5(1)to calculate RTT(1). The subscript 1 of RTT(1)indicates that the RTT is calculated using the first three ranging packet exchange. Additionally, the wireless device102calculates a clock offset from the wireless device104. At time t1(3), t3(12), t5(2), the wireless device102broadcasts a ranging packet320(also identified by sequence number 3), which is received by the wireless device104at time t2(3), t4(12), t6(2). As shown inFIG.3B, the ranging packet320includes times associated with the first three ranging packet exchange (i.e., t1(1), t4(1), t5(1)and times associated with the second three ranging packet exchange (i.e., t2(11), t3(11), t6(11). Thus, the wireless device104can use the information received in the ranging packet320and t2(1), t3(1), t6(1)to calculate RTT(1)(i.e., the RTT based on the first three ranging packet exchange). Additionally, the wireless device104can use the information received in the ranging packet320and t2(11), t3(11), t6(11)to calculate RTT(11)(i.e., the RTT based on the second three ranging packet exchange). Further, the wireless device104uses the information received in the ranging packet320to calculate a clock offset from the wireless device102.

At time t1(13), t3(3), t5(12), the wireless device104broadcasts a ranging packet322(also identified by sequence number 13), which is received by the wireless device102at time t2(13), t4(3), t6(12). As shown inFIG.3B, the ranging packet322includes times associated with the first three ranging packet exchange (i.e., t2(1), t3(1), t6(1), times associated with the second three ranging packet exchange (i.e., t1(11), t4(11), t5(10), and times associated with a third three ranging packet exchange (i.e., t2(2), t3(2), t6(2)). Note that the wireless device104includes the times associated with the first three ranging packet exchange even though this information was previously sent in ranging packet318. Resending the information improves the reliability of the technique since the wireless device102can calculate RTT(1)even if packet318was not received by the device. The historical information is re-sent by each subsequent ranging packet until a data capacity of the ranging packet is reached. Then, the oldest historical information is dropped from the next ranging packet.

The exchange of ranging packets between the wireless devices102,104continues until the measurement period has ended. Once the measurement period has ended, both devices stop listening on the measurement channel until the next measurement period. Note that the devices may calculate more than one round trip time during a single measurement period. For example, in addition to calculating RTT(1), the wireless device102may also calculate RTT(11)and RTT(2)based on the information included in the ranging packet322. Calculating more than one RTT in a single measurement period improves the reliability and robustness of the ranging calculation. In some examples, statistical analysis is used to analyze the calculated RTTs in order to improve the accuracy of the calculation. For example, an average of the calculated RTTs may be used to calculate the time-of-flight to a peer device. Additionally, the wireless devices can calculate the clock offset each time that the device calculates the RTT to the peer device, or can calculate the clock offset at periodic intervals (e.g., once every measurement period).

Also note that during each measurement period, there is a multitude of measurements performed by each device to each of the other devices (that is, each three way packet combination). Thus, even with high packet drops, there is still sufficient measurements between each pair.

FIG.4illustrates a frame structure402of a ranging packet400and a local database404of a wireless device, according to some implementations. InFIG.4, it is assumed that the ranging packet400is being received by a wireless device that includes the local database404. For the purposes of this example, also assume that the ranging packet400is broadcast by the wireless device104and received by the wireless device102. For example, the ranging packet400may be ranging packet320ofFIG.3B.

As shown inFIG.4, the frame structure402includes egress reports406. Each egress report406includes information indicative of a ranging packet that was previously broadcast by the wireless device104(i.e., the device that broadcast the ranging packet400). The egress reports406may be arranged in chronological order, where ER0stores information associated with an oldest ranging packet broadcast by the wireless device and ERN-1stores information associated with the most recently broadcast ranging packet. Each egress report406includes an identifier field408and a transmit time field410. Specifically, the identifier field408stores a sequence number of the ranging packet reported in that egress report406. And the transmit time field410includes a transmit time of the reported ranging packet. In an example, the transmit time is reported as a 32 bit coarse and a 32 bit fine number.

Additionally, the frame structure402includes ingress peer fields412. Each ingress peer field412is associated with a respective peer device of the wireless device104. Further, each ingress peer field412includes a peer device identifier field416and ingress report fields. The ingress report fields include information indicative of the ranging packets that were previously received by the wireless device104from the respective ingress peer. To illustrate, assume that the ingress peer0field414is associated with the wireless device102. The ingress peer0field414includes a peer device identifier field416and ingress report fields. The peer device identifier field416includes an identifier of the wireless device102, such as a MAC address. The ingress report fields include information indicative of the ranging packets that were previously received by the wireless device104from the wireless device102. Each ingress report field includes a ranging packet identifier field418and a receive time field420. The ranging packet identifier field418includes a sequence number of the ranging packet that is reported in that ingress report and the receive time field420includes a receive time of the reported ranging packet. In an example, the receive time is reported as a 32 bit coarse and a 32 bit fine number.

Upon receipt of the ranging packet400, the wireless device102stores in a database the information included in the ranging packet. In an example, the wireless device102groups the stored information per peer. As such, the wireless device102includes a local database404per peer device. As shown inFIG.4, the information associated with a peer device is grouped together and identified by a peer MAC422. In an example, the information associated with a peer device includes: (i) peer egress reports that include information indicative of the ranging packets that were previously broadcast by the peer device, (ii) peer ingress reports that include information indicative of the ranging packets that were previously received by the peer device from the wireless device102, and (iii) local receive times for ranging packets received from the peer device. As shown inFIG.4, the peer egress reports406of the wireless device104are stored as T3, the peer ingress reports of the wireless device104are stored as T2, and the local receive times of ranging packets received from the wireless device104are stored as T4.

FIG.5Aillustrates a flowchart of an example method500, according to some implementations of the present disclosure. The method500can be performed by each of many wireless devices in proximity, such that each device determines the location of each of the other devices. For example, the method500can be performed by a first wireless device that is determining a range to a second wireless device. For clarity of presentation, the description that follows generally describes method500in the context of the other figures in this description. However, it will be understood that method500can be performed, for example, by any suitable system, environment, software, hardware, or a combination of systems, environments, software, and hardware, as appropriate. In some implementations, various steps of method500can be run in parallel, in combination, in loops, or in any order.

At step502, method500involves periodically broadcasting outgoing ranging packets on a measurement channel of a wireless network at respective broadcast intervals. The outgoing ranging packets are broadcast the first wireless device that is determining the range to the second wireless device.

At step504, method500involves receiving, on the measurement channel and from a second wireless device, a plurality of incoming ranging data packets at respective receive times.

At step506, method500involves calculating, using a three ranging packet exchange with the second wireless device, a range to the second wireless device.

In some implementations, the first and second wireless devices are configured to access the measurement channel for a measurement period in response to a trigger.

In some implementations, the three ranging packet exchange comprises three subsequent ranging packets including: (i) first and second outgoing ranging packets broadcast by the first wireless device, and (ii) an incoming ranging packet broadcast by the second wireless device and received by the first wireless device.

In some implementations, calculating the range based on a transmit time (t1) of the first outgoing ranging packet, a receipt time (t2) of the first outgoing ranging packet at the second wireless device, a transmit time (t3) of the incoming ranging packet by the second wireless device, a receipt time (t4) of the incoming ranging packet at the first wireless device, a transmit time (t5) of the second outgoing ranging packet, and a receipt time (t6) of the second outgoing ranging packet at the second wireless device.

In some implementations, calculating the range to the second wireless device based on t1, t2, t3, t4, t5, and t6 comprises: calculating a roundtrip time (RTT) to the second wireless devices using: RTT: (t4−T1)(1+PPM)−(t3−t2), and RTT: −(t5−T4)(1+PPM)+(t6−t3); and calculating, based the RTT, the range to the second wireless device, wherein PPM is a clock offset between the first wireless device and the second wireless device.

In some implementations, the method further involves: calculating, using the three ranging packet exchange with the second wireless device, a clock offset with the second wireless device.

In some implementations, a first outgoing ranging packet of the outgoing ranging packets comprises: (i) an egress report that includes information indicative of one or more previously broadcast outgoing ranging packets sent by the first wireless device, (ii) a peer ingress report that includes information indicative of one or more previously received incoming ranging packets from at least the second wireless device, and (iii) one or more local receive times associated with the one or more previously received incoming ranging packets.

In some implementations, a first incoming ranging packet of the plurality of incoming ranging packets comprises: (i) an egress report that includes information indicative of one or more previously broadcast outgoing ranging packets sent by the second wireless device, (ii) a peer ingress report that includes information indicative of one or more previously received incoming ranging packets from at least the first wireless device, and (iii) one or more local receive times associated with the one or more previously received incoming ranging packets.

In some implementations, the method further involves: storing in a local database associated with the second wireless device: (i) local receive times of the plurality of incoming ranging data packets, (ii) the egress reports associated with the plurality of incoming ranging data packets, and (iii) the receive times at the second wireless device of the outgoing ranging packets broadcast by the first wireless device.

FIG.5Billustrates a flowchart of an example method510, according to some implementations of the present disclosure. The method510can be performed by each of many wireless devices in proximity, such that each device determines the location of each of the other devices. For example, the method510can be performed by a first wireless device that is determining a range to a second wireless device. For clarity of presentation, the description that follows generally describes method510in the context of the other figures in this description. However, it will be understood that method510can be performed, for example, by any suitable system, environment, software, hardware, or a combination of systems, environments, software, and hardware, as appropriate. In some implementations, various steps of method500can be run in parallel, in combination, in loops, or in any order.

At step512, method510involves broadcasting, on a measurement channel of a wireless network, a first ranging packet at a first time (t1), wherein the first ranging packet is received by the second wireless device at a second time (t2).

At step514, method510involves receiving a second ranging packet from the second wireless device, the second ranging packet transmitted by the second wireless device at a third time (t3) and received by the first wireless device at a fourth time (t4).

At step516, method510involves broadcasting a third ranging packet at a fifth time (t5), wherein the third ranging packet is received by the second wireless device at a sixth time (t6).

At step518, method510involves calculating a range to the second wireless device based on t1, t2, t3, t4, t5, and t6.

In some implementations, calculating a range to the second wireless device based on t1, t2, t3, t4, t5, and t6 involves calculating a roundtrip time (RTT) to the second wireless device using: RTT: (t4−T1)(1+PPM)−(t3−t2), and RTT: −(t5−T4)(1+PPM)+(t6−t3); and calculating, based the RTT, the range to the second wireless device, wherein PPM is a clock offset between the first wireless device and the second wireless device.

In some implementations, method510further involves calculating a clock offset between the first wireless device and the second wireless device.

In some implementations, method510further involves receiving, a fourth ranging packet from the second wireless device, wherein the fourth ranging packet includes information indicative of t2, t3, and t6.

FIG.6is a block diagram of an example computer system600that can be used to provide computational functionalities associated with described algorithms, methods, functions, processes, flows, and procedures described in the present disclosure, according to some implemendtations of the present disclosure. In some implementations, the wireless device102-106can be the computer system600, include the computer system600, or include part of the computer system600.

The illustrated computer602is intended to encompass any computing device such as a server, a desktop computer, embedded computer, a laptop/notebook computer, a wireless data port, a smart phone, a personal data assistant (PDA), a tablet computing device, or one or more processors within these devices, including physical instances, virtual instances, or both. The computer602can include input devices such as keypads, keyboards, and touch screens that can accept user information. Also, the computer602can include output devices that can convey information associated with the operation of the computer602. The information can include digital data, visual data, audio information, or a combination of information. The information can be presented in a graphical user interface (UI) (or GUI). In some implementations, the inputs and outputs include display ports (such as DVI-I+2× display ports), USB 3.0, GbE ports, isolated DI/O, SATA-III (6.0 Gb/s) ports, mPCIe slots, a combination of these, or other ports. In instances of an edge gateway, the computer602can include a Smart Embedded Management Agent (SEMA), such as a built-in ADLINK SEMA 2.2, and a video sync technology, such as Quick Sync Video technology supported by ADLINK MSDK+. In some examples, the computer602can include the MXE-5400 Series processor-based fanless embedded computer by ADLINK, though the computer602can take other forms or include other components.

The computer602can serve in a role as a client, a network component, a server, a database, a persistency, or components of a computer system for performing the subject matter described in the present disclosure. The illustrated computer602is communicably coupled with a network630. In some implementations, one or more components of the computer602can be configured to operate within different environments, including cloud-computing-based environments, local environments, global environments, and combinations of environments.

At a high level, the computer602is an electronic computing device operable to receive, transmit, process, store, and manage data and information associated with the described subject matter. According to some implementations, the computer602can also include, or be communicably coupled with, an application server, an email server, a web server, a caching server, a streaming data server, or a combination of servers.

The computer602can receive requests over network630from a client application (for example, executing on another computer602). The computer602can respond to the received requests by processing the received requests using software applications. Requests can also be sent to the computer602from internal users (for example, from a command console), external (or third) parties, automated applications, entities, individuals, systems, and computers.

Each of the components of the computer602can communicate using a system bus. In some implementations, any or all of the components of the computer602, including hardware or software components, can interface with each other or the interface604(or a combination of both), over the system bus. Interfaces can use an application programming interface (API), a service layer, or a combination of the API and service layer. The API can include specifications for routines, data structures, and object classes. The API can be either computer-language independent or dependent. The API can refer to a complete interface, a single function, or a set of APIs.

The service layer can provide software services to the computer602and other components (whether illustrated or not) that are communicably coupled to the computer602. The functionality of the computer602can be accessible for all service consumers using this service layer. Software services, such as those provided by the service layer, can provide reusable, defined functionalities through a defined interface. For example, the interface can be software written in JAVA, C++, or a language providing data in extensible markup language (XML) format. While illustrated as an integrated component of the computer602, in alternative implementations, the API or the service layer can be stand-alone components in relation to other components of the computer602and other components communicably coupled to the computer602. Moreover, any or all parts of the API or the service layer can be implemented as child or sub-modules of another software module, enterprise application, or hardware module without departing from the scope of the present disclosure.

The computer602can include an interface604. Although illustrated as a single interface604inFIG.6, two or more interfaces604can be used according to particular needs, desires, or particular implementations of the computer602and the described functionality. The interface604can be used by the computer602for communicating with other systems that are connected to the network630(whether illustrated or not) in a distributed environment. Generally, the interface604can include, or be implemented using, logic encoded in software or hardware (or a combination of software and hardware) operable to communicate with the network630. More specifically, the interface604can include software supporting one or more communication protocols associated with communications. As such, the network630or the interface's hardware can be operable to communicate physical signals within and outside of the illustrated computer602.

The interface604may also include one or more antennas for communicating using one or more wireless communication protocols. In some cases, one or more parts of a receive and/or transmit chain may be shared between multiple wireless communication standards. For example, a device might be configured to communicate using either Bluetooth or Wi-Fi using partially or entirely shared wireless communication circuitry (e.g., using a shared radio or at least shared radio components). The shared communication circuitry may include a single antenna, or may include multiple antennas (e.g., for MIMO) for performing wireless communications.

Alternatively, the interface604may include separate transmit and/or receive chains (e.g., including separate antennas and other radio components) for each wireless communication protocol with which it is configured to communicate. As a further possibility, the computer602may include one or more radios or radio components which are shared between multiple wireless communication protocols, and one or more radios or radio components which are used exclusively by a single wireless communication protocol. For example, the computer602may include a shared radio for communicating using one or more of LTE, CDMA2000 1×RTT, GSM, and/or 5G NR, and separate radios for communicating using each of Wi-Fi and Bluetooth. Other configurations are also possible.

The computer602includes a processor605. Although illustrated as a single processor605inFIG.6, two or more processors605can be used according to particular needs, desires, or particular implementations of the computer602and the described functionality. Generally, the processor605can execute instructions and can manipulate data to perform the operations of the computer602, including operations using algorithms, methods, functions, processes, flows, and procedures as described in the present disclosure.

The computer602can also include a database606that can hold data for the computer602and other components connected to the network630(whether illustrated or not). For example, database606can be an in-memory, conventional, or a database storing data consistent with the present disclosure. In some implementations, database606can be a combination of two or more different database types (for example, hybrid in-memory and conventional databases) according to particular needs, desires, or particular implementations of the computer602and the described functionality. Although illustrated as a single database606inFIG.6, two or more databases (of the same, different, or combination of types) can be used according to particular needs, desires, or particular implementations of the computer602and the described functionality. While database606is illustrated as an internal component of the computer602, in alternative implementations, database606can be external to the computer602.

The computer602also includes a memory607that can hold data for the computer602or a combination of components connected to the network630(whether illustrated or not). Memory607can store any data consistent with the present disclosure. In some implementations, memory607can be a combination of two or more different types of memory (for example, a combination of semiconductor and magnetic storage) according to particular needs, desires, or particular implementations of the computer602and the described functionality. Although illustrated as a single memory607inFIG.6, two or more memories607(of the same, different, or combination of types) can be used according to particular needs, desires, or particular implementations of the computer602and the described functionality. While memory607is illustrated as an internal component of the computer602, in alternative implementations, memory607can be external to the computer602.

An application can be an algorithmic software engine providing functionality according to particular needs, desires, or particular implementations of the computer602and the described functionality. For example, an application can serve as one or more components, modules, or applications. Multiple applications can be implemented on the computer602. Each application can be internal or external to the computer602.

The computer602can also include a power supply614. The power supply614can include a rechargeable or non-rechargeable battery that can be configured to be either user- or non-user-replaceable. In some implementations, the power supply614can include power-conversion and management circuits, including recharging, standby, and power management functionalities. In some implementations, the power-supply614can include a power plug to allow the computer602to be plugged into a wall socket or a power source to, for example, power the computer602or recharge a rechargeable battery.

There can be any number of computers602associated with, or external to, a computer system including computer602, with each computer602communicating over network630. Further, the terms “client,” “user,” and other appropriate terminology can be used interchangeably, as appropriate, without departing from the scope of the present disclosure. Moreover, the present disclosure contemplates that many users can use one computer602and one user can use multiple computers602.