METHOD TO ESTIMATE AND COMPENSATE FOR NLOS BIAS IN TIME DIFFERENCE OF ARRIVAL ESTIMATE

Abstract

Devices, systems, and method for compensating for non-line-of-sight (NLOS) bias in time difference of arrival (TDOA) estimates between a first anchor and a second anchor in a network having an obstacle in the line-of-sight therebetween are provided. The systems and methods include transmitting a first packet from a first anchor; indirectly receiving the first packet by a second anchor, then transmitting a second packet by the second anchor; indirectly receiving the second packet by the first anchor; and receiving the first packet and the second packet by a mobile node. The true fly-time of the first or second packets between the first anchor and the second anchor and the bias in time of flight of the first or second packets between the first anchor and the second anchor are estimated. The time difference of arrival at the mobile device between a direct path and an indirect path is further estimated and the NLOS bias in the time difference of arrival estimated at the mobile device is corrected.

Claims

1. A method for compensating for non-line-of-sight (NLOS) bias in time difference of arrival (TDOA) estimate between a first anchor and a second anchor in a network having an obstacle in the line-of-sight therebetween, the method comprising: transmitting a first packet from a first anchor; indirectly receiving the first packet by a second anchor, then transmitting a second packet by the second anchor; indirectly receiving the second packet by the first anchor; receiving the first packet and the second packet by a mobile node; estimating the true fly-time of the first or second packets between the first anchor and the second anchor; estimating the bias in time of flight of the first or second packets between the first anchor and the second anchor; estimating the time difference of arrival at the mobile device between a direct path and an indirect path; correcting the NLOS bias in the time difference of arrival estimated at the mobile device.

2. The method of claim 1, wherein the estimating and correcting is performed by the first and second anchors.

3. The method of claim 1, wherein the estimating of fly-time is performed by the first anchor.

4. The method of claim 1, wherein correcting the NLOS bias in the time difference of arrival is performed by the mobile device.

5. The method of claim 1, wherein the estimated bias is filtered.

6. The method of claim 1, wherein the true locations of the first anchor and the second anchor are known.

7. The method of claim 1, wherein the estimated bias is embedded in a packet and transmitted.

8. The method of claim 1, wherein the bias between the first and second anchors is compensated, according to:
R.sub.AB=t.sub.AB*cR.sub.AB=t.sup.A/2*cR.sub.AB, where t.sub.AB is the time of travel of the first packet from the first anchor to the second anchor, and wherein R.sub.AB is the direct path between the first and second anchors.

9. The method of claim 1, wherein the estimated bias between anchors is used directly in estimating a corrected distance difference, according to:
R.sup.C.sub.AB=R.sup.M.sub.ABR.sub.AB wherein R.sup.M.sub.AB is the original distance difference measured at the mobile device.

10. The method of claim 1, wherein the true fly-time between the first and second anchor is embedded in a first packet and transmitted.

11. The method of claim 1, wherein the true locations of one or both of the first and second anchors are unknown.

12. The method of claim 1, wherein the NLOS bias between the first and second anchors is estimated and updated a plurality of times.

13. The method of claim 1, wherein the NLOS bias between the first and second anchors is estimated during the initial setup of the network.

14. The method of claim 1 further comprising, estimating the position of the mobile device in an external computing device.

15. A method to compensate for non-line-of-sight (NLOS) bias in a time difference of arrival estimate, using an uplink time difference of arrival (UL-TDOA) scheme, the method comprising: transmitting a first packet by a mobile device; receiving the first packet by at least one first anchor and then transmitting a second packet by the at least one first anchor; receiving the first packet and the second packet by at least one second anchor in range of the mobile device and at least one first anchor; estimating the time differences of arrival at the at least one second anchor; and correcting the time differences of arrival at the at least one second anchor by subtracting the NLOS bias between the at least one first anchor and at least one second anchor.

16. The method of claim 15 further comprising, estimating the position of the mobile device using the corrected time differences of arrival.

17. The method of claim 16, wherein estimating the position of the mobile device is done in an external computing device.

18. A method to compensate for the non-line-of-sight (NLOS) bias in a beacon synchronized time difference of arrival (BS-TDOA) estimate, the method comprising: transmitting a first packet by a first anchor; receiving the first packet by a mobile node and then transmitting a second packet by the mobile node; receiving the first packet and the second packet by at least one second anchor that is within range of the first anchor and the mobile node; and measuring the time differences of arrival between a direct packet transmission path and an indirect packet transmission path by the at least one second node; correcting the time differences of arrival with an estimated bias of fly-time between the first anchor and at least one second anchor.

19. The method of claim 18 further comprising, estimating the position of the mobile device using the corrected time differences of arrival.

20. The method of claim 19, wherein estimating the position of the mobile device is done in an external computing device.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0027] The following detailed description is provided with the accompanying drawings, in which:

[0028] FIG. 1 is a prior art schematic of localization network based on a downlink TDOA scheme;

[0029] FIG. 2(a) shows a prior art of a schematic of transmission and reception of wireless signals;

[0030] FIG. 2(b) shows a prior art timing diagram of the transmission and reception of the wireless signals;

[0031] FIG. 3(a) illustrates signal transmissions with NLOS path between anchors in a DL-TDOA scheme;

[0032] FIG. 3(b) illustrates the timing with NLOS path between anchors in a DL-TDOA transmission;

[0033] FIGS. 4(a)-(c) are the flow charts illustrating anchors and mobile device for a TDOA location operation;

[0034] FIG. 5 is a schematic of a bias compensation for network based on uplink TDOA scheme;

[0035] FIG. 6 is a schematic of a bias compensation for network based on beacon synchronized TDOA scheme;

[0036] FIG. 7 is a schematic of a prior art UL-TDOA scheme;

[0037] FIG. 8 is a schematic of a prior art BS-TDOA system

DETAILED DESCRIPTION

[0038] This present disclosure describes systems and methods to automatically estimate the fly-time bias for anchor pairs and compensate for it during the position estimate process. As a result, the system can deploy a TDOA network with anchors installed in arbitrary locations and without having to worry about introducing bias from non-line-of-sight packet transmissions. According to the present disclosure and two anchors within range of each other can be used as a TDOA pair. The present disclosure can significantly simplify the network planning process as it allows the network to be planned manually and at the same time reduces the total number of anchor devices, increases the location coverage, and offers more accurate position services.

[0039] FIG. 1 illustrates a prior art Time-of-Flight (TOF) based locationing system 1100 which consists of a number of anchor devices 1101 and mobile devices 1103. In a DL-TDOA configuration, as described in U.S. Patent Application Publication No. 2015/0156746, which is hereby incorporated by reference, anchor nodes are grouped in pairs (e.g., anchor pairs 1102). Each pair 1102 consists of two anchors 1101 that are within each other's range. For example, anchors A and B form a pair 1102. Further, anchors A, B, C, and D can additionally be paired into the following pairs {B,D}, {C,D}, {C,A}, {B,C} and {A,D} if those nodes are within each other's range. For TDOA location operation, all, or some of the anchor pairs can transmit using RF signals 1112. Alternatively, the present disclosure contemplates that additional signal types can be used without departing from the spirit of the present disclosure. The RF signals 1112 are received by the mobile devices 1103. The reception time of the signals 1112 are estimated and used to determine the distance difference from the mobile to anchors respectively. With the distance differences, and the anchor locations known, the position of the mobile device 1133 can be estimated.

[0040] The present application assumes that signals transmitted by radio devices are in the form of packets. Moreover, the anchors, radio nodes, and mobile devices can be Ultra-Wideband (UWB) radio devices. Alternatively, it is understood that other signal formats can be used as long as timing information can be extracted. The mobile devices, anchors, and other nodes can be formed together as a single network.

[0041] During a downlink TDOA (DL-TDOA) operation, each anchor 2201, 2202 in an anchor pair {A, B} can transmit one packet. FIG. 2(a) illustrates two anchors 2201, 2202 and one mobile device 2103 in the DL-TDOA operation. The first anchor 2201 can transmit an REQ packet 2208. The second anchor 2202 can receive the REQ packet 2208 and then can transmit an RSP packet 2209 immediately, or after a brief delay. A mobile node, or mobile device, 2103 can receive both the REQ packet 2208 and the RSP packet 2209. The mobile node can then measure the time delay between the reception of REQ (t.sup.M.sub.REQ) and RSP (t.sup.M.sub.RSP), t=t.sup.M.sub.RSPt.sup.M.sub.REQ.

[0042] The time-of-flight of the signals are illustrated in FIGS. 2(a) and 2(b). The REQ packet 2208 travels by distance R.sub.AM 2213 to reach a mobile device 2103. The REQ packet 2208 additionally travels by distance R.sub.AB 2212 to reach anchor B 2202. Upon receiving REQ packet 2208, anchor B 2202 transmits a packet RSP 2209. The transmitted signal RSP 2209 travels by distance R.sub.BM 2223 to reach the mobile device 2103. The path from anchor A 2201 to mobile M 2103 is defined as the direct path, and the path from anchor A 2201 to mobile M 2103 via a second anchor 2202 (e.g., anchor B) as the indirect path. The distance difference between the direct path and indirect path is R=(R.sub.AB+R.sub.BM)R.sub.AM. The distance difference from the mobile device 2103 to different anchors, e.g., R.sup.M.sub.AB=R.sub.BMR.sub.AM, can be used to estimate the position of the mobile device. The distance difference is estimated as follows:

R.sup.M.sub.AB=R.sub.BMR.sub.AM=(R.sub.AB+R.sub.BM)R.sub.AMR.sub.AB=t*cR.sub.AB(1)

where t (time difference of arrival) is the time elapsed from reception of REQ 2208 to the reception of RSP 2209 measured by the mobile device node M 2103; R.sub.AB, and t can be computed based on the known locations of anchor A and B. In case the turnaround time at the second anchor device 2202 is non-zero, it is subtracted from the measured time difference as well.

[0043] FIG. 2(b) shows the timing diagram of the packets. Where t.sub.AM is the fly-time of signal from anchor A 2201 to mobile device M 2103 directly (A.fwdarw.M), and where t.sub.AB, t.sub.BM are the fly-times of the signals via the indirect path (A.fwdarw.B.fwdarw.M). Again for simplicity, the turnaround time is assumed to be zero.

[0044] Equation (1) can be used to accurately estimate the distance difference R.sup.M.sub.AB. However, as shown in FIG. 3(a) a bias can be present in the location estimate when the anchors 201, 202 are not in line-of-sight (LOS) from each other. In the case where the LOS path R.sub.AB 112 between anchor A 201 and anchor B 202 is not available, the signal may reach anchor B 202 via a non-line-of-sight (NLOS) path. As shown in FIG. 3, the NLOS path consists of two segments R.sub.AC 311 and R.sub.BC 312 between anchors and a reflector 333 due to the presence of a physical obstacle 300. Obstacle 300 can be, for example, any of a wall, a display, goods, etc. The total travel distance of the signal is greater than the direct LOS path, i.e., R.sub.AC+R.sub.BC>R.sub.AB. As a result, the overall travel from the indirect path has a positive bias R.sub.AB=R.sub.AC+R.sub.BCR.sub.AB. This is reflected as a positive bias in the measured time difference of arrival (TDOA).

[0045] In the above discussed NLOS situation, if equation (1) is used directly, this bias R.sub.AB will be included in the overall time difference measurement t, and as a result, the position estimate can be significantly degraded. Estimating the bias R.sub.AB and compensating for it can therefore improve the position estimate accuracy.

[0046] FIG. 3(b) shows the timing diagram of the packet transmission and reception at the anchors 201, 202 and the mobile device 103. FIG. 3(b) additionally illustrates how to estimate the bias R.sub.AB. For example, the sequence of packet transmissions is unchanged, i.e., the first anchor A 201 transmits a REQ packet 208, the second anchor 202 receives the first REQ packet 208. The second anchor then transmits a RSP packet 209. The mobile device 103 receives the REQ packet 208, from anchor A 201, and the RSP packet 209, from anchor B 202. The mobile device 103 can then measure the difference between the direct path, and the indirect path via the second anchor 202.

[0047] To estimate the bias, the first anchor 201 measures the time elapsed between the transmission of the REQ packet to the reception of the RSP packet. The first anchor 201 can estimate the round trip fly-time of the signal via the NLOS path, as t.sup.A=2*t.sub.AB. The fly-time from anchor A 201 to anchor B 202 is t.sub.AB=t.sup.A/2. The distance bias is then computed as

R.sub.AB=t.sub.AB*cR.sub.AB=t.sup.A/2*cR.sub.AB(2)

[0048] Once the estimated bias R.sub.AB is calculated, anchor A 201 can broadcast this information. The estimated bias can be embedded into the following REQ packet sent by the anchor A 201. Assuming that anchors 201, 202 are stationary and their locations do not change over time, the bias between an anchor pair does not change. The anchors 201, 202 can improve the accuracy of the bias estimate by applying filtering to the estimated bias. The bias between anchor pairs {A, B} can be measured continuously, or during the initial network setup. Each anchor 201, 202 can store the bias estimates of its neighboring anchors. The estimated bias, when available, can be included in the REQ or RSP packets 208, 209.

[0049] The mobile node, after receiving the bias R.sub.AB, corrects the original TDOA measurement with the bias, as follows

R.sup.C.sub.AB=R.sup.M.sub.ABR.sub.AB(3)

[0050] As we can see, R.sup.C.sub.AB=R.sup.M.sub.ABR.sub.AB=t*c(R.sub.AB+R.sub.AB). Equation (3) can be rewritten as

R.sup.M.sub.AB=(tt.sup.A/2)*c(4)

[0051] Equation (4) expresses the relationship that the distance difference can be estimated using the measured time difference of arrival at a mobile device, and the measured flight time between anchors. It is not necessary to know the anchor locations to solve for the distance difference.

[0052] FIGS. 4(a)-4(c) illustrate flow diagrams describing the DL-TDOA scheme from the first anchor (initiating anchor), the second anchor (responding anchor) and the mobile device. The flow for each of the nodes, e.g. anchor A, anchor B, and the mobile device, can be summarized as follows: [0053] Initiating anchor (anchor A) [0054] transmits REQ packet 402, [0055] receives RSP packet 404, [0056] estimates the round trip delay t.sup.A and computes the distance bias R.sub.AB 406, [0057] processing the bias estimate 408, and [0058] broadcasts the bias (e.g., in the following REQ packet) 410. [0059] Responding anchor (anchor B) [0060] receives REQ packet 412 and [0061] transmits RSP packet 414. [0062] Mobile node (mobile device) [0063] receives REQ and RSP packets 416, [0064] receives anchor bias R or fly-time t.sup.A 418, [0065] measures fly-time difference t between the direct path and indirect path 420, [0066] correct the estimated fly-time difference with the anchor bias R 422, and [0067] estimates position using corrected distance differences for multiple anchor pairs 424.

[0068] The above described methods are applicable for other TDOA schemes. Except as described below, or as will be readily appreciated by one having ordinary skill in the art, the anchors 201, 202, the mobile device 103, and the physical obstacle 300 are substantially similar to the anchors 201, 202, mobile device 103, and the physical obstacle 300 described above. A detailed description of the structure and function thereof is thus omitted here for the sake of brevity. For example, in the case of UL-TDOA, a mobile device 103 can transmit a REQ packet 208 to all anchors within range of the mobile device 103. One or more of the anchors, e.g. 201, 202, upon receiving the REQ packet 208, can transmit RSP packets 209. Anchors 201, 202 receive the RSP packets 209. FIG. 5 illustrates the signal path and packet transmission between the two anchors A and B and a mobile device 103 during the UL-TDOA operation. As shown, mobile device 103 initially transmits a REQ packet 208; then anchor A 201 receives the REQ packet 208. Once anchor A 208 receives the REQ packet 208, anchor A 208 can then transmit a RSP packet 209. Subsequently, anchor B 202 can receive both the REQ and RSP packets 208, 209. As shown in FIG. 5, a physical obstacle 300 between at least anchors A and B 201, 202, that creates an NLOS bias between the anchors. The distance difference between the mobile device 103 to the two anchors 201, 202 is calculated as

R.sup.M.sub.AB=R.sub.BMR.sub.AM=R.sub.BM(R.sub.AM+R.sub.AB)+R.sub.AB=t*cR.sub.AB(5)

where t is the measured time elapsed from the reception of REQ packet 208 to the reception of RSP packet 208 at anchor B 202.

[0069] The NLOS bias has similar impact on the overall estimate of distance difference as described above. The NLOS bias can be corrected similarly, provided the bias is measured. The anchors 201, 202 can perform the bias measurements prior to the UL-TDOA operation, for example during the initialization of the system. Alternatively, the anchors 201, 202 can perform the bias measurements by transmitting an additional packet from anchor B 202 back to anchor A 201 at any time.

[0070] If the true fly-time between anchors is known, the NLOS bias can be compensated for. To compensate for the NLOS bias, equation (5) can be rewritten as

R.sup.C.sub.AB=R.sub.BMR.sub.AM=t*c+(R.sub.AB+R.sub.AB)(6)

or

R.sup.C.sub.AB=R.sub.BMR.sub.AM=(t+t.sup.A/2)*c(7)

[0071] In a further alternative system, the above described bias compensation can be applied to BS-TDOA scheme. Except as described below, or as will be readily appreciated by one having ordinary skill in the art, the anchors 201, 202, the mobile device 103, and the physical obstacle 300 are substantially similar to the anchors 201, 202, mobile device 103, and the physical obstacle 300 described above. A detailed description of the structure and function thereof is thus omitted here for the sake of brevity. In a BS-TDOA scheme, as shown in FIG. 6, a first anchor, or beacon, A 201 can transmit a REQ packet 208. The mobile device 103 can receive the REQ packet 208 and in response can transmit a RSP packet 209. Other anchors within range, e.g. anchor B 202, can receive both the REQ packet 208 from anchor A 201, and the RSP packet 209 from the mobile device 103. FIG. 6 illustrates one example that includes only one additional anchor B 202. The locations of both anchors 201, 202 is known, therefore anchor B 202 can estimate the distance difference between the direct path (A.fwdarw.B) and the indirect path (A.fwdarw.M.fwdarw.B) based on the time difference of arrival measured at anchor B 202 as t,

t*c=R.sub.BM+R.sub.AMR.sub.AB(8)

or

R.sub.BM+R.sub.AM=t*c+R.sub.AB(9)

[0072] If the path between the anchor A 201 and the anchor B 202 is non-line-of-sight, (NLOS), a bias R.sub.AB is present in the total distance traveled by the signal. This bias is present in the measurement of time of flight.

[0073] The correction of the NLOS bias can be applied as

R.sub.BM+R.sub.AM=t*c+(R.sub.AB+R.sub.AB)(10)

or

R.sub.BM+R.sub.AM=t+t.sup.A/2)*c(11)

[0074] Again, the distance, or time, bias between two anchors in systems where no line of sight exists between nodes can be estimated offline prior to the BS-TDOA transmissions, or during the BS-TDOA operation by letting the second anchor B 202 transmitting an additional packet. Anchor A 201 can then receive this additional packet, that itself transmitted, and then estimates the round trip delay bias.

[0075] The systems and methods described herein can effectively compensate the bias in the time of flight estimation in NLOS channels between anchors. With the calculated bias, the estimated time of flight can be significantly reduced and subsequently, the position estimate based on the time-of-flight or time-difference-of-arrival is more accurate. Using this technology, anchors in a real time location system can be used in buildings or locations where non-line-of-sight conditions exist while maintaining high accuracy of position estimates of mobile devices based on TDOA schemes.

[0076] Although systems and methods have been described by way of examples of preferred embodiments, it is to be understood that various adaptations and modifications may be made within the spirit of the scope of the concepts described herein.