Asymmetric Double-Sided Two-Way Ranging in an Ultrawideband Communication System

Abstract

In an ultra-wideband (UWB) communication system comprising a pair of UWB transceivers, an asynchronous two-way ranging method for closely estimating the time-of-flight between the transceivers after the exchange of only 3 messages between the transceivers. In an alternate asynchronous two-way ranging method, the time-of-flight between the transceivers may be closely estimated after the exchange of only 4 messages between the transceivers.

Claims

1. An asymmetric double-sided two-way ranging method using three messages, P.sub.1, P.sub.2, and P.sub.3, to complete a pair of round-trip delay measurements between a first device, A, having a first clock, C.sub.a, and a second device, B, having a second clock, C.sub.b, the method comprising the steps of: [1.1] in A, transmitting P.sub.1 at a selected point in time T.sub.0 relative to C.sub.a; [1.2] in B: [1.2.1] after an unknown time-of-flight, T.sub.f, receiving P.sub.1 at a time T.sub.1 relative to C.sub.b; and [1.2.2] after a first transmit delay, {circumflex over (D)}.sub.b, transmitting P.sub.2 at a time T.sub.2 relative to C.sub.b; [1.3] in A: [1.3.1] after a first response delay, {circumflex over (R)}.sub.a, relative to T.sub.0, receiving P.sub.2 at a time T.sub.3 relative to C.sub.a; and [1.3.2] after a second transmit delay, {circumflex over (D)}.sub.a, transmitting P.sub.3 at a time T.sub.4 relative to C.sub.a; and [1.4] in B: [1.4.1] after a second response delay, {circumflex over (R)}.sub.b, relative to T.sub.2, receiving P.sub.3 at a time T.sub.5 relative to C.sub.b; and [1.4.2] developing an estimate, {tilde over (T)}.sub.f, of T.sub.f in accordance with a selected one of: $\begin{matrix} [1.4 .Math. .2 .Math. .1] .Math. .Math. {\tilde{T}}_{fa} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}}; \\ [1.4 .Math. .2 .Math. .2] .Math. .Math. {\tilde{T}}_{fb} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{b} + {\hat{D}}_{b}}; and \\ [1.4 .Math. .2 .Math. .3] .Math. .Math. {\tilde{T}}_{fab} = \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a} + {\hat{R}}_{b} + {\hat{D}}_{b}} . \end{matrix}$

2. The method of claim 1 further including the step of: [1.4.3] developing an estimate of a distance between A and B as a function of {tilde over (T)}.sub.f.

3. An asymmetric double-sided two-way ranging method using four messages, P.sub.1, P.sub.2, P.sub.3 and P.sub.4, to complete a pair of round-trip delay measurements between a first device, A, having a first clock, C.sub.a, and a second device, B, having a second clock, C.sub.b, the method comprising the steps of: [3.1] in A, transmitting P.sub.1 at a selected point in time T.sub.0 relative to C.sub.a; [3.2] in B: [3.2.1] after an unknown time-of-flight, T.sub.f, receiving P.sub.1 at a time T.sub.1 relative to C.sub.b; and [3.2.2] after a first transmit delay, {circumflex over (D)}.sub.b, transmitting P.sub.2 at a time T.sub.2 relative to C.sub.b; [3.3] in A: [3.3.1] after a first response delay, {circumflex over (R)}.sub.a, relative to T.sub.0, receiving P.sub.2 at a time T.sub.3 relative to C.sub.a; [3.4] in B, transmitting P.sub.3 at a selected point in time T.sub.4 relative to C.sub.b; [3.5] in A: [3.5.1] after an unknown time-of-flight, T.sub.f, receiving P.sub.3 at a time T.sub.5 relative to C.sub.a; and [3.5.2] after a second transmit delay, {circumflex over (D)}.sub.a, transmitting P.sub.4 at a time T.sub.6 relative to C.sub.a; and [3.6] in B: [3.6.1] after a second response delay, {circumflex over (R)}.sub.b, relative to T.sub.4, receiving P.sub.4 at a time T.sub.7 relative to C.sub.b; and [3.6.2] developing an estimate, {tilde over (T)}.sub.f, of T.sub.f in accordance with a selected one of: $\begin{matrix} [3.6 .Math. .2 .Math. .1] .Math. .Math. {\tilde{T}}_{fa} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}}; \\ [3.6 .Math. .2 .Math. .2] .Math. .Math. {\tilde{T}}_{fb} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{b} + {\hat{D}}_{b}}; and \\ [3.6 .Math. .2 .Math. .3] .Math. .Math. {\tilde{T}}_{fab} = \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a} + {\hat{R}}_{b} + {\hat{D}}_{b}} . \end{matrix}$

4. The method of claim 3 further including the step of: [3.6.3] developing an estimate of a distance between A and B as a function of {tilde over (T)}.sub.f.

5. An asymmetric two-way ranging circuit configured to perform the method of any preceding claim.

6. A wireless receiver comprising an asymmetric two-way ranging circuit according to claim 5.

7. A wireless transceiver comprising a wireless receiver according to claim 6.

8. A wireless communication system comprising a wireless transceiver according to claim 7.

9. A non-transitory computer readable medium including executable instructions which, when executed in a processing system, causes the processing system to perform the steps of a method according to any one of claims 1 to 4.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

[0026] Our invention may be more fully understood by a description of certain preferred embodiments in conjunction with the attached drawings in which:

[0027] FIG. 1 illustrates, in block diagram form, one embodiment of a receiver adapted for use in a UWB communication system;

[0028] FIG. 2 illustrates, in time flow form, one embodiment of a method adapted to determine ranging in accordance with our invention; and

[0029] FIG. 3 illustrates, in time flow form, one other embodiment of a method adapted to determine ranging in accordance with our invention.

[0030] In the drawings, similar elements will be similarly numbered whenever possible. However, this practice is simply for convenience of reference and to avoid unnecessary proliferation of numbers, and is not intended to imply or suggest that our invention requires identity in either function or structure in the several embodiments.

DETAILED DESCRIPTION OF THE INVENTION

[0031] Recall that we do not know the real delay times, D.sub.a and D.sub.b, or the round trip times, R.sub.a and R.sub.b. All we have are estimates which we know are in error by a much larger amount than the time of flight we are trying to estimate. Indeed, the amount of error in these estimates is impossible to know without access to a perfect clock.

[0032] We know from Eq. 4:

[00006] $\begin{matrix} D_{a} = \frac{{\hat{D}}_{a}}{k_{a}} & [Eq . .Math. 8 .Math. a] \end{matrix}$

[0033] And similarly:

[00007] $\begin{matrix} D_{b} = \frac{{\hat{D}}_{b}}{k_{b}} & [Eq . .Math. 8 .Math. b] \end{matrix}$

[0034] Then from Eq. 8a and Eq. 1:

[00008] $\begin{matrix} R_{a} = 2 .Math. T_{f} + \frac{{\hat{D}}_{b}}{k_{b}} & [Eq . .Math. 9 .Math. a] \end{matrix}$

[0035] And similarly:

[00009] $\begin{matrix} D_{b} = \frac{{\hat{D}}_{b}}{k_{b}} & [Eq . .Math. 9 .Math. b] \end{matrix}$

[0036] Then from Eq. 9a and Eq. 3a:

[00010] $\begin{matrix} {\hat{R}}_{a} = 2 .Math. k_{a} .Math. T_{f} + \frac{k_{a} .Math. {\hat{D}}_{b}}{k_{b}} & [Eq . .Math. 10 .Math. a] \end{matrix}$

[0037] Similarly, from Eq. 9b and Eq. 3b:

[00011] $\begin{matrix} {\hat{R}}_{b} = 2 .Math. k_{b} .Math. T_{f} + \frac{k_{b} .Math. {\hat{D}}_{a}}{k_{a}} & [Eq . .Math. 10 .Math. b] \end{matrix}$

[0038] In Eq. 10a and Eq. 10b, above, we have elapsed time periods, {circumflex over (R)}.sub.a, {circumflex over (R)}.sub.b, {circumflex over (D)}.sub.a and {circumflex over (D)}.sub.b, that we can measure using the respective, local clocks of A and B. But we have no convenient way of measuring k.sub.a or k.sub.b; and these clock skew errors swamp the value of T.sub.f. We have discovered, however, that if we multiply {circumflex over (R)}.sub.a by {circumflex over (R)}.sub.b, the bulk of the value of the product will be the product of {circumflex over (D)}.sub.a and {circumflex over (D)}.sub.b. Thus, for this term in the product, the k.sub.a and k.sub.b constants effectively cancel each other out. Let us see where this leads:

[0039] From Eq. 10a and Eq. 10b:

[00012] $\begin{matrix} {\hat{R}}_{a} .Math. {\hat{R}}_{b} = 4 .Math. k_{a} .Math. k_{b} .Math. T_{f}^{2} + \frac{k_{a} .Math. {\hat{D}}_{b}}{k_{b}} .Math. \frac{k_{b} .Math. {\hat{D}}_{a}}{k_{a}} + 2 .Math. k_{b} .Math. T_{f} .Math. \frac{k_{a} .Math. {\hat{D}}_{b}}{k_{b}} + 2 .Math. k_{a} .Math. T_{f} .Math. \frac{k_{b} .Math. {\hat{D}}_{a}}{k_{a}} & [Eq . .Math. 11] \\ .Math. {\hat{R}}_{a} .Math. {\hat{R}}_{b} = 4 .Math. k_{a} .Math. k_{b} .Math. T_{f}^{2} + {\hat{D}}_{a} .Math. {\hat{D}}_{b} + 2 .Math. T_{f} (k_{a} .Math. {\hat{D}}_{b} + k_{b} .Math. {\hat{D}}_{a}) & [Eq . .Math. 12] \\ .Math. {\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b} = 4 .Math. k_{a} .Math. k_{b} .Math. T_{f}^{2} + 2 .Math. T_{f} (k_{a} .Math. {\hat{D}}_{b} + k_{b} .Math. {\hat{D}}_{a}) & [Eq . .Math. 13] \end{matrix}$

[0040] Then from Eq. 10a and Eq. 13:

[00013] $\begin{matrix} \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}} = \frac{4 .Math. k_{a} .Math. k_{b} .Math. T_{f}^{2} + 2 .Math. T_{f} (k_{a} .Math. {\hat{D}}_{b} + k_{b} .Math. {\hat{D}}_{a})}{2 .Math. k_{a} .Math. T_{f} + \frac{k_{a} .Math. {\hat{D}}_{b}}{k_{b}} + {\hat{D}}_{a}} & [Eq . .Math. 14] \end{matrix}$

[0041] On the left hand side, taking out 2Tf and multiplying above and below by k.sub.b:

[00014] $\begin{matrix} \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}} = 2 .Math. T_{f} .Math. k_{b} .Math. \frac{2 .Math. k_{a} .Math. k_{b} .Math. T_{f} + k_{a} .Math. {\hat{D}}_{b} + k_{b} .Math. {\hat{D}}_{a}}{2 .Math. k_{a} .Math. k_{b} .Math. T_{f} + k_{a} .Math. {\hat{D}}_{b} + k_{b} .Math. {\hat{D}}_{a}} & [Eq . .Math. 15] \end{matrix}$

[0042] So finally:

[00015] $\begin{matrix} \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}} = 2 .Math. T_{f} .Math. k_{b} 2 .Math. T_{f} & [Eq . .Math. 16 .Math. a] \end{matrix}$

[0043] Similarly:

[00016] $\begin{matrix} \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{b}} = 2 .Math. T_{f} .Math. k_{a} 2 .Math. T_{f} & [Eq . .Math. 16 .Math. b] \end{matrix}$

[0044] So now we have two possible estimates for T.sub.f. Since k.sub.a and k.sub.b are very close to 1, i.e., 0.99998<k.sub.a, k.sub.b<1.00002, we can estimate T.sub.f as follows:

[00017] $\begin{matrix} {\tilde{T}}_{fa} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a}} & [Eq . .Math. 17 .Math. a] \\ {\tilde{T}}_{fb} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{b}} & [Eq . .Math. 17 .Math. b] \end{matrix}$

[0045] Note that these estimates are very close to the actual T.sub.f because k.sub.a and k.sub.b are very close to one, and, in particular, their accuracy is independent of the delays employed at A and at B.

[0046] Whether a system should best use Eq. 17a or Eq. 17b would depend on which clock it expects to be more accurate. For example, if the system consisted of devices with high accuracy clocks in Role B, above, and tags with low accuracy clocks in Role A, above, then it should use Eq. 17a. If it expects neither to be more accurate than the other and it cannot readily calculate the accuracy of either, it would be most accurate to use the average result from Eq. 17a and Eq. 17b since this will always be as good as, or better than, the worst of the two. We have found by experimentation with typical values of delay and clock offset that this average can be approximated by the following:

[00018] $\begin{matrix} {\tilde{T}}_{fab} = \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{R}}_{a} + {\hat{D}}_{a} + {\hat{R}}_{b} + {\hat{D}}_{b}} & [Eq . .Math. 18] \end{matrix}$

[0047] Note that the value of {circumflex over (R)}.sub.a is close to the value of {circumflex over (D)}.sub.b, since {circumflex over (D)}.sub.b makes up most of the time for this particular round trip measurement. This means that in the denominator of formulas Eq. 17a, Eq. 17b and Eq. 18, {circumflex over (D)}.sub.b can be used instead of {circumflex over (R)}.sub.a or {circumflex over (R)}.sub.a can be used instead of {circumflex over (D)}.sub.b without greatly reducing the accuracy. Similarly, {circumflex over (D)}.sub.a can be used instead of {circumflex over (R)}.sub.b and {circumflex over (R)}.sub.b can be used instead of {circumflex over (D)}.sub.a, leading, e.g., to:

[00019] $\begin{matrix} {\tilde{T}}_{fD} = \frac{1}{2} .Math. \frac{{\hat{R}}_{a} .Math. {\hat{R}}_{b} - {\hat{D}}_{a} .Math. {\hat{D}}_{b}}{{\hat{D}}_{a} + {\hat{D}}_{b}} & [Eq . .Math. 19] \end{matrix}$

Systems which Benefit from Flexible Response Delays

[0048] By way of example, let us assume that one device device sends a packet, P1, to many, say 5, tags. Each tag then responds with a packet to this device in successive responses: Tag 1 responds with packet 2a after time t; Tag 2 responds with packet 2b after time 2t; Tag 3 responds with packet 2c after time 3t; Tag 4 responds after time with packet 2d 4t; and Tag 5 responds with packet 2e after time St. Now, the device closes off the round with a final packet 3. Each tag can now calculate its distance from the device after a sequence of just 7 messages. If the device had used SDS-TWR, it would be forced to have the same delay for each tag interaction and a minimum of 3 messages per tag, or 15 messages would be required. In accordance with our invention, the number of packets required is N+2 instead of 3N. By thus allowing asymmetric delays, our invention results in a significant reduction in airtime and power consumption.

[0049] Consider now a system with a mobile tag (on an asset, say) that sends a packet P1 received by many fixed devices in an infrastructure, where three of which reply in turn with packets P2a, P2b, P2c, after which the tag sends P3 received by all three devices. Then, using our invention, each of the three devices independently calculates its distance to the tag. These three distances can then be combined in an infrastructure-based-solver to locate the tag by triangulation. This allows the tag/asset to be located after sending 2 messages and receiving 3. If symmetric timings were needed, as in the prior art, then this process would require a minimum of 6 transmissions and 3 receptions to complete.

[0050] In the case of a peer-to-peer network of N mobile nodes where each node wants to find its distance to every other peer node as part of solving their relative location, then this is N(N1) distance measurements. For example, for a 5 node system, this consists of 10 distinct distance measurements. With the prior art symmetric double-sided ranging, this requires 3 messages per distance measurement. In some cases, there may also be a need to send an additional message to communicate the results, which could be 1 per distance measurement or just 1 per node containing all the results which that node calculated. This is then a total of 35 to 40 messages in the 5 node example case. Using our asymmetric ranging invention, as illustrated in FIG. 2, the ranging exchanges can be combined and completed with just two transmissions per node, i.e., 10 messages in the case of the 5 node example. This is achieved as follows:

[0051] Let us define the three messages of the ranging exchange as: the Poll, P, sent by the initiator; the Response, R; and the Final message, F, that completes the two round trips; and, further, define the result communicated as a time-of-flight report message, T. If we enumerate these messages as P, R, F and T, with subscripts indicating the source and destination node addresses, and number the nodes from 1 to 5, then the 10 ranging exchanges for the 5 nodes can be achieved with the 10 messages listed in table 1:

TABLE-US-00001 TABLE 1 Example 5 node peer-to-peer optimized ranging solution Message Sender Message # Node Content Description 1 1 P.sub.12 P.sub.13 P.sub.14 P.sub.15 Initiating Poll from node 1 to the others. 2 2 R.sub.21 P.sub.23 P.sub.24 P.sub.25 This message is the Response to node 1, and, also serves as node 2's initiating Poll to nodes 3, 4 and 5. 3 3 R.sub.31 R.sub.32 P.sub.34 P.sub.35 Responses to nodes 1 and 2, and also serves an Initiating Poll to nodes 2 and up. 4 4 R.sub.41 R.sub.42 R.sub.43 P.sub.45 Node 4's Responses to nodes 0, 1 and 2, and Poll to node 5. 5 5 R.sub.51 R.sub.52 R.sub.53 R.sub.54 Gives Response to nodes 0, 1, 2 and 3. 6 1 F.sub.12 F.sub.13 F.sub.14 F.sub.15 Final Messages completing the ranging exchange between node 1 and each of the other nodes 2 to 5. 7 2 T.sub.21 F.sub.23 F.sub.24 F.sub.25 TOF message reporting the node-1 to node-2 distance. And the Final Messages completing the ranging exchanges between node 2 and each of the other nodes 3 to 5. 8 3 T.sub.31 T.sub.32 F.sub.34 F.sub.35 TOF messages reporting node 3's distances to nodes 1 and 2. And the Final Messages completing the ranging exchanges between node 3 and each of the other nodes 4 and 5. 9 4 T.sub.41 T.sub.42 T.sub.43 F.sub.45 TOF messages reporting node 4's distances to nodes 1, 2 and 3. And the Final Message completing the ranging exchange between node 4 and node 5. 10 5 T.sub.51 T.sub.52 T.sub.53 T.sub.54 TOF messages reporting node 5's distances to nodes 1, 2, 3 and 4.

[0052] As can be seen, this then is a substantial saving on message traffic (saving battery power and air-time). However, the ranging exchanges are highly asymmetric: in the Table 1 example, above, the ranging exchange between node 1 and node 5 starts with the poll from node 1 at message #1, then the response from node 5 is at message #5 and the final from node 1 is message #6. If these message times are in units approximately 200 s, then these two round trips are asymmetric with timings of approximately 800 s versus 200 s. This scheme then only works well when the asymmetric nature of the communications does not lead to a large ranging error. Fortunately, however, there are many other examples where flexible response delays are an advantage.

Possible Ranging Schemes

[0053] As noted above, FIG. 2 illustrates a two-way ranging exchange using three messages to complete a pair of round-trip delay measurements. In this scheme, a first device, A, transmits a first message, P.sub.1, at a selected point in time (step 10). After an unknown time-of-flight, T.sub.f, a second device, B, receives P.sub.1 (step 12). After a first delay, {circumflex over (D)}.sub.b, that is characteristic of B, B transmits a second message, P.sub.2 (step 14). After T.sub.f, A receives P.sub.2 (step 16). After a second delay, {circumflex over (D)}.sub.a, that is characteristic of A, A transmits a third message, P.sub.3 (step 18). Finally, after T.sub.f, B receives P.sub.3 (step 20). Using a selected one of either Eq. 17a and Eq. 17b, or, perhaps, using only Eq. 18, we can now calculate a reasonably close estimate of T.sub.f.

[0054] As shown in FIG. 3, our asymmetric ranging method can also be performed using four messages to comprise two pairs of round-trip measurements, where each pair is separated in time by some relatively small but otherwise arbitrary interval. In accordance with this alternative scheme, the first round-trip measurement consists of a first message, P.sub.1 (steps 22 and 24) and a first response, P.sub.2 (steps 26 and 28), and the later, second round-trip measurement also consists of a second message, P.sub.3 (steps 30 and 32) and a second response, P.sub.4 (steps 34 and 36), but sent in the opposite direction to those of the first round-trip measurement. Again, using a selected one of either Eq. 17a and Eq. 17b, or, perhaps, using only Eq. 18, we can now calculate a reasonably close estimate of T.sub.f.

[0055] Thus it is apparent that we have provided an improved method and apparatus for use in the receiver of a wireless communication system to determine ranging. Although we have so far disclosed our invention only in the context of a packet-based UWB communication system, we appreciate that our invention is broadly applicable to other types of wireless communication systems, whether packed-based or otherwise, that perform ranging using response time stamps. Further, we submit that our invention provides performance generally comparable to the best prior art techniques but more efficiently than known implementations of such prior art techniques.

Asymmetric Double-Sided Two-Way Ranging in an Ultrawideband Communication System

Assignee

Inventors

Cpc classification

Classification Explorer

G01S13/785

PHYSICS

Classification Explorer

G01S13/767

PHYSICS

Classification Explorer

G01S13/20

PHYSICS

Classification Explorer

H01Q5/25

ELECTRICITY

Classification Explorer

G01S13/765

PHYSICS

International classification

Classification Explorer

G01S13/76

PHYSICS

Classification Explorer

G01S13/20

PHYSICS

Classification Explorer

H01Q5/25

ELECTRICITY

Abstract

Claims

Description