Geo-locating of wireless devices using a binning function
11709249 · 2023-07-25
Assignee
Inventors
- Mark Passler (Boca Raton, FL, US)
- Steven Romanow (North Lauderdale, FL, US)
- Graham Smith (Boca Raton, FL, US)
Cpc classification
G01S13/765
PHYSICS
International classification
Abstract
A method for determining a geo-location of a target station is provided. The method includes receiving a plurality of RTTs over a plurality of successive time intervals. Each successive time interval is equal to a predetermined amount of time. The plurality of RTTs is placed into a plurality of bins. Each bin has a predetermined time width and a count of RTTs placed in the bin. A bin with a highest count of RTTs (maxCb) and another bin with a next highest count of RTTs are selected and a maximum count ratio determined. The bin with maxCb to a maximum bin value is set based at least on a predetermined threshold of the maximum count ratio. During a next successive time interval, the RTTs that are placed in the bin that is set to the maximum bin value are selected to determine the geo-location of the target station.
Claims
1. A method for determining a geo-location of a target station using a plurality of round-trip times (RTTs) of signals transmitted by a measuring station to the target station, and response signals received from the target station corresponding to the transmitted signals, the plurality of RTTs being placed into a plurality of bins, each bin having a count of RTTs placed in the bin, the method comprising: selecting a bin with a highest count of RTTs (maxCb) and another bin with a next highest count of RTTs (nextCb); determining a maximum count ratio as maxCb/nextCb; setting the bin with maxCb to a maximum bin value based at least on a predetermined threshold of the maximum count ratio; and selecting the RTTs that are placed in the bin that is set to the maximum bin value to determine the geo-location of the target station.
2. The method of claim 1, wherein each bin of the plurality of bins has a predetermined time width (T.sub.W), and the method further includes: determining an average value of the RTTs in each bin of the plurality of bins, the average value corresponding to the bin; and for each RTT (RTT.sub.n) of the plurality of RTTs: placing the RTT.sub.n into the bin that corresponds to the average value if a difference between the RTT.sub.n and the average value is one of less than and equal to half of the T.sub.W of the bin.
3. The method of claim 2, wherein each RTT.sub.n has a receipt time, the receipt time being a time at which the corresponding RTT is received at the measuring station, the method further including: for each RTT in each bin: determining a time difference between a present time and the receipt time of the RTT; and removing, from each bin, each RTT for which the time difference is greater than a preset time interval; and updating the average value of the RTTs in each bin.
4. The method of claim 3, wherein at least one of: the determining of the time difference and the removing of each RTT are performed after a predetermined amount of time (T.sub.1) has elapsed; and the method further includes at least one of: receiving the plurality of RTTs over a plurality of successive time intervals, each successive time interval being equal to T.sub.1; selecting the bin with maxCb and another bin with nextCb is performed after T.sub.1 has elapsed.
5. The method of claim 2, wherein the method further includes: if the difference between the RTT.sub.n and the average value is greater than half of T.sub.W of each bin of the plurality of bins: creating a new bin and including the new bin in the plurality of bins; and adding the RTT.sub.n to the new bin.
6. The method of claim 1, wherein the method further includes: creating a first bin for a first RTT and including the first bin in the plurality of bins, the first RTT being an RTT that is first received by the measuring station; and placing the first RTT in the first bin.
7. The method of claim 1, the method further including: determining the geo-location of the target station based at least on the selected RTTs that are placed in the bin that is set to the maximum bin value.
8. The method of claim 1, wherein the RTTs that are placed in the bin that is set to the maximum bin value are selected during a next successive time interval associated with the plurality of RTTs.
9. The method of claim 1, wherein the measuring station is an airborne measuring station.
10. A wireless device, WD, configured to determine a geo-location of a target station using a plurality of round-trip times (RTTs) of signals transmitted by a measuring station to the target station and response signals received from the target station corresponding to the transmitted signals, the plurality of RTTs being placed into a plurality of bins, each bin having a count of RTTs placed in the bin, the WD comprising: processing circuitry configured to: select a bin with a highest count of RTTs (maxCb) and another bin with a next highest count of RTTs (nextCb); determine a maximum count ratio as maxCb/nextCb; set the bin with maxCb to a maximum bin value based at least on a predetermined threshold of the maximum count ratio; and select the RTTs that are placed in the bin that is set to the maximum bin value to determine the geo-location of the target station.
11. The WD of claim 10, wherein each bin of the plurality of bins has a predetermined time width (T.sub.W), and the processing circuitry is further configured to: determine an average value of the RTTs in each bin of the plurality of bins, the average value corresponding to the bin; for each RTT (RTT.sub.n) of the plurality of RTTs: place the RTT.sub.n into the bin, B, that corresponds to the average value, if a difference between the RTT.sub.n and the average value is one of less than and equal to half of the T.sub.W of the bin.
12. The WD of claim 11, wherein each RTT.sub.n has a receipt time, the receipt time being a time at which the corresponding RTT is received at the measuring station, the processing circuitry being further configured to: for each RTT in each bin: determine a time difference between a present time and the receipt time of the RTT; and remove, from each bin, each RTT for which the time difference is greater than a preset time interval; and update the average value of the RTTs in each bin.
13. The WD of claim 12, wherein at least one of: the determining of the time difference and the removing of each RTT are performed after a predetermined amount of time (T1) has elapsed; and the processing circuitry is further configured to at least one of: cause the WD to receive the plurality of RTTs over a plurality of successive time intervals, each successive time interval being equal to T.sub.1; select the bin with maxCb and another bin with nextCb is performed after T.sub.1 has elapsed.
14. The WD of claim 11, the processing circuitry being further configured to: if the difference between the RTT.sub.n and the average value is greater than half of T.sub.W of each bin of the plurality of bins: create a new bin and including the new bin in the plurality of bins; and add the RTT.sub.n to the new bin.
15. The WD of claim 10, wherein the processing circuitry is further configured to: create a first bin for a first RTT and including the first bin in the plurality of bins, the first RTT being an RTT that is first received by the measuring station; and place the first RTT in the first bin.
16. The WD of claim 10, the processing circuitry being further configured to: determine the geo-location of the target station based at least on the selected RTTs that are placed in the bin that is set to the maximum bin value.
17. The WD of claim 10, wherein the RTTs that are placed in the bin that is set to the maximum bin value are selected during a next successive time interval associated with the plurality of RTTs.
18. The WD of claim 10, wherein the measuring station is an airborne measuring station.
19. An airborne measuring station configured to determine a geo-location of a target station using a plurality of round trip times (RTTs) associated with the target station, the airborne measuring station comprising: processing circuitry configured to: place the plurality of RTTs into a plurality of bins, each bin, B, having a predetermined time width (T.sub.W) and a count of RTTs placed in the bin; select a bin with a highest count of RTTs (maxCb) and another bin with a next highest count of RTTs (nextCb); determine a maximum count ratio as maxCb/nextCb; set the bin with maxCb to a maximum bin value based at least on a predetermined threshold of the maximum count ratio; and select, during a next successive time interval, the RTTs that are placed in the bin that is set to the maximum bin value to determine the geo-location of the target station.
20. The airborne measuring station of claim 19, wherein each bin of the plurality of bins has a predetermined time width (T.sub.W), and the processing circuitry is further configured to: determine an average value of the RTTs in each bin of the plurality of bins, the average value corresponding to the bin; and for each RTT (RTT.sub.n) of the plurality of RTTs: place the RTT.sub.n into the bin that corresponds to the average value if a difference between the RTT.sub.n and the average value is one of less than and equal to half of the T.sub.W of the bin.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
(1) A more complete understanding of the present disclosure, and the attendant advantages and features thereof, will be more readily understood by reference to the following detailed description when considered in conjunction with the accompanying drawings wherein:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16) The combination of
(17)
(18)
DETAILED DESCRIPTION
(19) Methods, devices, and systems are disclosed that mitigate the need for a correlation threshold setting and determine the presence of wanted RTT measurements in the presence of many false RTTs. This Application incorporates U.S. patent application Ser. No. 16/589,627 and Ser. No. 16/708,923 by reference in their entireties. A presence of false RTT measurements may arise when the technique of correlation is used to determine if a received response packet is an expected response packet. A dynamic binning method is disclosed that, in the general sense, places received RTT measurements into bins which are examined in order to select the bin with the most entries and then determine if this bin contains the wanted RTTs. Based on the principle that the true RTT will be a consistent value, whereas the values of false RTTs, due to noise, will vary randomly, the bin of the true RTT may be identified. The disclosed binning method is independent of background noise level and enables sensitivities better than can be achieved by those restricted by a need to set a correlation threshold.
(20) As described above with reference to
(21)
(T2−T1)+(T3−T2)+(T4−T3)=(T4−T1)=td+SIFS+td=2*td+SIFS
Hence,RTT=(T4−T1) and TOF=td=(T4−T1−SIFS)/2 (2)
(22) Expression (2) is a simplified equation that is included to provide a basic idea of an example ranging transmission method. Note that the duration of the transmitted ranging packet and the response packet is not accounted for in equation (2). Note that in practice it is common that the timestamp of a packet is set to coincide with the end of the packet at the point where the frame check is completed.
(23)
(24) STA B 305 transmits the response packet 324 at time Te 423. Assuming that the response packet 324 is an ACK or an CTS packet in reply to the received ranging packet 312, time Te 423 ideally will be at a time t.sub.SIFS 432 after time Td 422, where t.sub.SIFS 432 is the SIFS time as defined in the IEEE 802.11 Standard. At time Tf 413, STA A 300 starts to receive the response packet 324. The time difference between Te 423 and Tf 413 is td 433, the propagation time for the packet to travel from STA to B 305 STA A 300 and is equal to the propagation time td 431. At time Tg 424, STA B 305 completes the transmission of the response packet 324 and at time Th 414, STA A 300 completes receiving the response packet 324. RTT 415 is the time, Th, that the response packet 324 was received at STA A 300, minus the time, Tc, that the ranging packet 312 was transmitted by STA A 300. Note that the time differences (Tb−Ta), (Td−Tc), (Tf−Te) and (Th−Tg) are all equal and have the value td 431 which is the propagation time for the ranging packet and response packet to travel between the two STAs.
(25) At STA A 300, the time of a packet at the point when the frame check has completed, may be recorded. Hence, if STA A 300 is the measuring station, the time for the transmission of ranging packet 312 that is recorded is Tc 412, and the time that is recorded for the reception of the response packet 324 is Th 414. In order to calculate the value of td, it is necessary to know the duration tr 434 of the response packet 324. As the details of the response packet 324 are predictable, based upon the details of the ranging packet 312, the duration tr 434 of the response packet is known. In practice therefore, STA A 300 can calculate the values of RTT 415 and td (TOF) from expression (3):
RTT=(Th−Tc) and td=(RTT−tr−t.sub.SIFS)/2=TOF (3)
and hence the corresponding distance, D=td*c (4)
(26) Stated another way, STA A 300 begins transmission of ranging packet 312 at a beginning transmission time Ta 411 and ends transmission of the ranging packet 312 at an ending transmission time Tc 412. STA A 300 begins receiving of the response packet 324 at a beginning reception time Tf 413 and receives the complete response packet 324 at an ending reception time Th 414, wherein RTT is measured as the time between the ending reception time Th 414 and the ending transmission time Tc 412, and TOF is RTT minus the duration of the response packet tr 434, minus t.sub.SIFS 432, divided by 2.
(27) A reception window Trw 460 may be defined which may be related to the range of the target, STA B 305. The reception window starts at time Ts 410 after the end of the transmission, Tc 412 of ranging packet 312 and ends at time Tt 420 after the end of the transmission, Tc 412 of ranging packet 312. As an example, consider the case where the target STA B 305 is considered to be at a range of, for example, 2 to 6 miles from STA A 300. In this example, the reception window Trw may be set to start at time Ts 410, 15 μs after time Tc 312, and end at time Tt 420, 65 μs after time Tc 312. In this example the duration of the reception window Trw 460 is 50 μs.
(28) In the general sense, ranging packets may be sent at either regular intervals or in bursts. The time Tp 450 is the time between successive ranging packets either within a burst or continuous.
(29)
(30) As mentioned previously, the packet exchange may be any pair of packets where an automatic response packet is sent. Commonly used packets in Wi-Fi include an RTS/CTS exchange and a Data (null)/Ack exchange.
(31) In some embodiments, the disclosed method applies to the reception of direct sequence spread spectrum DSSS ACK and CTS packets in response to data null and RTS packets respectively, in the 2.4 GHz band. In other embodiments, the disclosed method applies to the reception of OFDM ACK and CTS packets in response to data null and RTS packets respectively, in the 2.4 GHz and 5 GHz bands. A more complete understanding of the present disclosure, and the attendant advantages and features thereof, will be more readily understood by reference to the following detailed analysis of the reception of direct sequence spread spectrum DSSS ACK and CTS packets using correlation.
(32) In one non-limiting embodiment used to describe some of the functions and concepts herein, a DSSS CTS and a DSSS ACK packet consist of 304 bits.
(33) A 1 Mbps DSSS packet uses an 11 bit Barker code to spread the signal. Each bit is represented by the 11 bit code either as is, for a 1, or inverted for a 0. Hence there is a theoretical processing gain (PG) of approximately 10 dB (PG=10 log 11). The modulation is binary phase shift keying (BPSK).
(34) The probability of a bit error, Pb, for BPSK, is
Pb=0.5erfc√{square root over (E.sub.b/N.sub.0)} (5) where “erfc” is the Gauss complimentary error function E.sub.b is energy per bit N.sub.0 is noise per hertz
(35) For BPSK, E.sub.b/N.sub.0 is equal to the signal to noise ratio, SNR.
(36) The packet error rate (PER) is related to the bit error, Pb by the expression
PER=1−(1−Pb).sup.M, (6) where M is the number of bits in the packet
(37) For a packet error rate PER=0.7, with M=304,
(38) from equations (5) and (6), Pb=0.00386 and Eb/No=SNR=5.5 dB.
(39) With the 10 dB processing gain (11 bit Barker code), this is equivalent to an input SNR=−4.5 dB. The received signal level is calculated using the standard formula:
Pr=10 log(1000 K T)+10 Log BW+NF+SNR dBm (7) Where K is Boltzmann's constant T is temperature in degrees Kelvin BW is the occupied bandwidth, Hz NF is the noise figure, dB
(40) For T=20° Celsius, 10 log (1000 K T)=−174 dBm
(41) BW=20 MHz for DSSS and assuming NF=3 dB and SNR=−4.5 dB, from (7) Pr=−102.5 dBm.
(42) A receiver sensitivity of −102.5 dBm for a 70% PER represents a situation with no implementation losses.
(43) If all the bits of the CTS or ACK are known in advance, then the received bits may be compared to the expected bits. If enough of the bits match then a decision may be made that the CTS or ACK had indeed been detected. This technique is known as correlation where the decision may be based upon a correlation threshold.
(44) In the general sense, correlation works by passing the known pattern across the noisy pattern, and if the bits agree, they add, if not, the bits subtract.
(45) For a packet of M bits, M.Pb bits will not match and M (1−Pb) will match,
Hence Correlation %=100(Match−Mismatch)/Total
or Correlation %=100(M−2 M Pb)/M=100(1-2Pb) (8)
(46) Hence, for Pb=0.2, Correlation %=100 (1−2×0.2)=60%
(47) Note that for pure noise, Pb=0.5 and hence 152 bits will agree (match), 152 will not agree (mismatch) and correlation will be 0%.
(48) If the raw detected 304 bits of the DSSS CTS or DSSS ACK packets are correlated across the known bits of the complete packet, then it is possible to detect a CTS or ACK packet that is well below the noise level.
(49) For a given SNR, the bit error Pb may be calculated using equation (5) and the correlation % calculated using equation (8). The variance and standard deviation, σ, of the mismatched bits may be calculated:
σ.sup.2=M Pb(1−Pb)
σ=√{square root over (M Pb(1−Pb))} (9)
(50) For M bits, the number of mismatched bits is M.Pb, with a standard deviation of σ.
(51) Hence, mismatched bits=M.Pb±σ, and the number of matched bits is M−(M.Pb±σ).
(52) Thus, the correlation (%) from equation (8) expressed as mean±standard deviation, is given by:
(53)
(54) Comparing (10) to (8), the following associations can be made:
Correlation mean=(1-2Pb) (11)
and Correlation standard deviation=2σ/M. (12)
(55) Noise has a bit error rate, Pb=0.5 with a mean of zero and, from equation (9), σ=√{square root over (M/4)}, and from equation (12)
noise correlation standard deviation=√{square root over (1/M)} (13)
(56) Hence, the effective “3σ correlation” for thermal noise is
(57)
i.e., for M=304, thermal noise 3σ correlation=0.172 or 17.2%.
(58)
(59) As discussed above with reference to
(60) The probability, Pw, that the wanted correlation is greater than the peak noise correlation is
P.sub.W=∫u(x;μ,β).Math.[1−
(x)]dx (14)
(61) Where u(x; μ, β) is the Gumbel PDF of noise with location μ, scale β for a value of n,
(62) And [1−(x)] is the complement cumulative distribution function (1−CDF) of the normal distribution of the wanted signal correlation with mean and standard deviation as per equations (11) and (12).
(63) Table 1 shows the probability of the wanted correlation peak being higher than the maximum peak of the noise correlations as the correlation mean varies for thermal, lab and suburban noise conditions. The noise is assumed to be 3 dB higher than thermal for lab conditions, and 6 dB higher for suburban conditions.
(64) TABLE-US-00001 TABLE 1 Probability that the Wanted correlation is highest, Corr Prob Wanted Peak Wins % Mean% Thermal Lab Suburban 90 100 100 100 85 100 100 100 80 100 100 100 75 100 100 100 70 100 100 100 65 100 100 100 60 100 100 100 55 100 100 99 50 100 100 97 45 100 100 88 40 100 98 67 35 100 91 38 30 97 72 14 25 86 41 3 20 59 15 0 15 27 3 0 10 7 0 0 5 1 0 0
(65) Referring again to
(66)
(67)
(68) As discussed above with reference to
(69)
(70) A binning method is disclosed that mitigates the need for the use of a correlation threshold, does not require a calibration procedure, and enables a high signal sensitivity even in the presence of changing background noise levels.
(71) A more complete understanding of the present disclosure, and the attendant advantages and features thereof, will be more readily understood by reference first to an exemplar analysis of a general binning method.
(72) A number of bins, B, may be created as the RTT measurements are received. As discussed above with reference to
(73)
For example, if N=500 and B=10, the average count per bin will be 50 and σ=7.07. Counts in the bins due to noise, may be assumed to vary with a Poisson distribution and the bin with the top count, corresponding to 3σ, a probability of 0.2%, would have a value of about 72. Assuming that a percentage of the RTTs correspond to the target station 120, then these would all be added to one bin, which may be termed the “wanted” bin. For example, if 20% of the 500 RTTs, i.e., 100, corresponded to the target station 120, then 400 RTTs would be due to noise, resulting in an average count of 40 per bin and a standard deviation of 6.32, resulting in a count of 59 in the noise bin with the top count. With the average count due to noise of 40, and the number of true RTTs is 100, then the wanted bin will have a count of 140. In this example, the wanted bin will have a wanted to top noise bin count ratio of 140/59=2.37. If, in order to assess a minimum condition, it is assumed that the count due to noise in the wanted bin is equivalent to −σ, i.e., 34, then the wanted to top noise bin count ratio becomes 134/59=2.27.
(74)
(75)
(76) Stated another way, if a bin has a count equal to or greater than twice the count of any other bin, then that bin may be assumed to be the bin with the RTTs of the target station 120. Conversely, if no bin has a count equal to or greater than twice the count of any other bin, then it may be assumed that RTTs from the target station 120 are not present. Note also that the count ratio is independent of the actual signal strength of the received response packets 324 from the target station 120, and of the amplitude of the background noise. Setting the count ratio to a preset value, for example 2, effectively sets a threshold of the % RTTs from the target station 120, for example about 16%, and mitigates the requirement to set a correlation threshold. Other count ratio thresholds may be chosen, the higher the ratio the more likely that the bin with the maximum count is the one with the RTTs from the target station 120 but the effective sensitivity of the system will be less.
(77)
(78) With reference again to
(79) An analysis of the change of RTT values, the RTT difference, is provided below.
(80)
(81) Knowing the distance d, the antenna tilt angle ϕ1, the antenna yaw angle ϕ1, and the altitude A of the airborne measuring station 110 the difference R1−R2 may be calculated using standard trigonometry:
(82)
(83) From (16) and (20) the value of D2 is now known.
Then R1−R2=√{square root over (D1.sup.2+A.sup.2)}−√{square root over (D2.sup.2+A.sup.2)}
And RTT difference=2|R1−R2| (21)
(84)
(85)
(86) As discussed above with reference to
(87) As the value of the wanted RTT measurement is unknown, using fixed bins can result in the wanted RTT measurements being spread across more than one bin. A dynamic binning method, where the bins are set up according to the RTT measurement values as they are received, and where the center value of each bin may be adjusted with time, is described below.
(88) The basic concept of a dynamic binning method is that there are B bins, of bin width T.sub.W, each containing a count Cb of RTTs.
(89) RTTb,c represents the cth RTT in bin b, Where, b={1, 2, 3, . . . B,}. and where c={1,2,3 . . . Cb)}
(90) A burst of N RTTs is received, as described above with reference to
(91)
(92) If the value of RTTn is within T.sub.W/2 of the AveRTTb for any of the B bins, then RTTn is added to that bin and the count Cb in that bin will be incremented. If the value of RTTn is not within T.sub.W/2 of the AveRTTb for any of the B bins, then a new bin is created, and B is incremented. Hence,
(93)
(94) Bursts of N RTTs continue to be received, as described above with reference to
(95) At the end of a regular time interval of T.sub.1 all the existing bins may be examined to remove RTTs that were recorded at a time in the past that renders them out-of-date. An out-of-date time, t.sub.o, may be based on a fixed time or one that is calculated relative to the speed of the airborne measuring station 110, or the lesser of the two. Any RTT in any bin that is older than t.sub.o may then be discarded. The AveRTT of all the B bins may then be (re)calculated, AveRTTb.
(96) Also, at the end of a regular interval, T.sub.1, following the procedure to remove out-of-date RTTs, the bins may be examined to determine the bin with highest count, maxCb, of RTTs. The ratio of the count, maxCb, to the count, nextCb, in the bin with the next highest count of RTTs may then be determined: Ratio=maxCb/nextCb
(97) If the ratio exceeds a preset value, R, then the bin with highest count, maxCb, may be referred to as “BINmax”. For example, a value of 2 may be used for R. The (re)calculated RTT average values, AveRTTb, and BINmax, may then be used throughout the next T.sub.1 time interval.
(98) During the regular intervals T.sub.1, several bursts of N RTTs may be received. After each burst of N RTTs, if a BINmax is present (as determined for the previous T.sub.1 interval), then only those RTTs that are added to BINmax are passed on to the next stage for the calculation of the geo-location. The other RTTs are retained in their respective bins. If a BINmax is not present, then none of the N RTTs that have been received during that burst are passed on to the next stage for the calculation of the geo-location, but the N RTTs of that burst are all still retained in their respective bins. RTTs may only be deleted when they become out-of-date.
(99) The objective of the dynamic binning process, as disclosed above, is to reject RTTs due to noise and only pass on to the next stage of the geo-location calculation those RTTs that occur in the bin that corresponds to the RTTs from the wanted target station 120. As discussed above with reference to
(100)
(101) The transmitter receiver 1410 may transmit and/or receive radio frequency (RF) signals to and from the antenna assembly 1480. The GPS module 1440 output may be connected to the transmitter receiver 1410. The GPS module 1440 may provide the latitude, longitude, and altitude of the wireless communication device 1400. The transmitter receiver 1410 may append GPS information to any RF transmission and/or reception. The network switch 1450 may be connected to the Transmitter Receiver 1410, and the computer system 1430. The transmitter receiver 1410 may include a transmitter 1411 and a receiver 1412. The receiver 1412 may be connected to a correlator 1413 that may perform the correlation processes as described above with reference to
(102) The computer system 1430 may include an interface 1431. Interface 1431 may contain an Ethernet connection to the network switch 1450, the connection to a display 1436, a connection to a keyboard and mouse 1437 as well as interfacing to the processing circuitry 1435. In some embodiments the processing circuitry 1435 may include a processor 1432, a memory 1433 and a database 1434. The database 1434 may contain the ground mapping information of the area of interest and the processor 1432 and memory 1433 may be used to carry out all or part of the exemplar binning processes as described above with reference to
(103) Thus, in some embodiments, the processing circuitry 1435 may include the memory 1433 and a processor 1432, the memory 1433 containing instructions which, when executed by the processor 1432, configure the processor 1432 to perform the one or more functions described herein. In addition to a traditional processor and memory, the processing circuitry 1435 may comprise integrated circuitry for processing and/or control, e.g., one or more processors and/or processor cores and/or FPGAs (Field Programmable Gate Array) and/or ASICs (Application Specific Integrated Circuitry).
(104) The processing circuitry 1435 may include and/or be connected to and/or be configured for accessing (e.g., writing to and/or reading from) the memory 1433, which may include any kind of volatile and/or non-volatile memory, e.g., cache and/or buffer memory and/or RAM (Random Access Memory) and/or ROM (Read-Only Memory) and/or optical memory and/or EPROM (Erasable Programmable Read-Only Memory). Such memory 1433 may be configured to store code executable by control circuitry and/or other data, e.g., data pertaining to communication, e.g., configuration and/or address data of nodes, etc. The processing circuitry 1435 may be configured to control any of the methods described herein and/or to cause such methods to be performed, e.g., by the processor 1432. Corresponding instructions may be stored in the memory 1433, which may be readable and/or readably connected to the processing circuitry 1435. In other words, the processing circuitry 1435 may include a controller, which may comprise a microprocessor and/or microcontroller and/or FPGA (Field-Programmable Gate Array) device and/or ASIC (Application Specific Integrated Circuit) device. It may be considered that the processing circuitry 1435 includes or may be connected or connectable to memory, which may be configured to be accessible for reading and/or writing by the controller and/or processing circuitry 1435.
(105)
(106) In some embodiments, process 1500 may include five sub-processes:
(107) Sub-process 1 “Initializing”—Inputting values for T.sub.W, T.sub.1, t.sub.0, R and N. Receiving during a preset interval of T.sub.1 the first sets of RTTs, forming the initial set of bins, and determining their respective AveRTT values, (steps 1501 to 1527);
(108) Sub-process 2—Determining the ratio of the count maxCb, in the bin with the highest count of RTTs, to the count, nextCb, in the bin with the next highest count of RTTs. If the ratio exceeds a preset value, R, the bin with highest count of RTTs is “BINmax” (steps 1710 to 1714);
(109) Sub-process 3—Receiving RTTs, in bursts of N, checking their values against the AveRTT of all existing bins and placing them into either an existing bin or creating a new bin (steps 1601 to 1611);
(110) Sub-process 4—If a “BINmax” exists, as determined in Process 2, then only those RTTs received in each burst of N RTTs that are added to BINmax are passed on to the next stage. If a BINmax is not present, then none of the RTTs that have been received during that burst are passed on to the next stage (Steps 1620 to 1624);
(111) Sub-process 5—Examining all bins and removing RTTs that are out-of-date, i.e., older than t.sub.o, and then re-calculating the AveRTT for each bin (steps 1701 to 1708).
(112) The process 1500 may start at step 1501 where the values for Bin Width, T.sub.W, Time intervals T.sub.1 and t.sub.0, ratio R, and the number of packets in a burst N, may be inputted. These values may be inputted via the Keyboard/Mouse 1437 or may reside in the memory 1433 of the processing circuitry 1435. At step 1502 a timer may be started so as to initiate the time intervals T.sub.1 and t.sub.0 and at step 1502, the value B, number of bins, may be set to 1. At step 1505 the first RTT, RTT.sub.1, is received. Bin 1 may be created at step 1506 and RTT.sub.1 is added to it. RTT.sub.2 may then be received at step 1507.
(113) An RTT may be the result of an exchange of a ranging packet 312 transmitted by Transmitter 1411 and the reception of a response packet 324, from a target station 120, received by Receiver 1412 as discussed above with reference to
(114) At step 1508 the value of RTT.sub.2 may be compared to the value of RTT.sub.1 to check if it is within T.sub.W/2 of RTT 1, i.e. |RTT.sub.2−RTT.sub.1|<T.sub.W/2, and if true, at step 1509 RTT.sub.2 may be added to Bin 1 and a value for AveRTT.sub.1 calculated. If, at step 1508, |RTT.sub.2−RTT.sub.1|>T.sub.W/2, then at step 1511 a new bin, Bin 2, may be created and RTT.sub.2 added to it. Then at step 1512, the value of B, the number of bins, is incremented to 2 and, at step 1513, AveRTT2 may be set equal to the value of RTT.sub.2.
(115) A new RTT, RTTn, is received at step 1520 and at step 1521 the value of RTTn may be compared to the value of AveRTTb for each existing bin, Bin 1 to Bin B, to check if it is within T.sub.W/2 of the AveRTTb, i.e. |RTT.sub.n−RTT.sub.b|<T.sub.W/2, and, if true, at step 1522, RTT.sub.n may be added to that bin b, and a value for AveRTTb calculated, i.e., for b=1 to B, if |RTT.sub.n−AveRTT.sub.b|<T.sub.W/2 (step 1521), then RTTn is added to Bin b (step 1522). At step 1523 a new value for AveRTTb may then be calculated, i.e.,
(116)
where Cb is the number of RTTs in bin b. If, at step 1521, |RTT.sub.n−RTT.sub.b|>T.sub.W/2 for all bins, then at step 1524 a new bin, Bin B+1, may be created and RTT.sub.n added to that bin. Then, at step 1525, the value of B, the number of bins, may be incremented and, at step 1526, the AveRTTB may be set equal to the value of RTT.sub.n. At step 1527 a check is made of the time to determine if a time equal to or greater than T.sub.1 may have elapsed. If not, then the process may return to step 1520 where a new RTTn may be received.
(117) If at step 1527 it is determined that a time of T1 has elapsed, then the process may advance to
(118) At step 1601, a value n is initialized. A new RTT, RTTn, is received at step 1602 and at step 1603 the value of RTTn may be compared to the value of AveRTTb for each existing bin, Bin 1 to Bin B, to check if it is within T.sub.W/2 of the AveRTTb, i.e. |RTT.sub.n−RTT.sub.b|<T.sub.W/2, and, if true, at step 1604, RTT.sub.n may be added to that bin b, and a value for AveRTTb calculated, i.e., for b=1 to B, if |RTT.sub.n−AveRTT.sub.b|<T.sub.W/2 (step 1603), then RTTn is added to Bin b (step 1604). At step 1605 a new value for AveRTTb may then be calculated, i.e.,
(119)
where Cb is the number of RTTs in bin b. If, at step 1603, |RTT.sub.n−RTT.sub.b|>T.sub.W/2 for all bins, then at step 1606 a new bin, Bin B+1, may be created and RTT.sub.n added to that bin. Then, at step 1607, the value of B, the number of bins, may be incremented and, at step 1607, the AveRTTB may be set equal to the value of RTT.sub.n. At step 1610 the value of n may be checked against N, the number of RTTs in a burst. The number of RTTs in a burst is discussed above with reference to
(120) If at step 1610 it is determined that the burst of N RTTs has been received, then at step 1620 a check that a BINmax exists, as determined in step 1713, may be made. If a BINmax does exist then, at step 1621 all those RTTs that have been added to BINmax in the last burst of N RTTs, may be selected and these RTTs are outputted to the next stage of the geo-location calculations (step 1622). If, at step 1620, no BINmax exists, as determined in step 1714, then no RTTs from the last burst of N RTTs are outputted. At step 1623 a check is made of the time to determine if a time equal or greater than T.sub.1 may have elapsed. A value for T.sub.1 may be inputted at step 1501. If not, then the process may return to step 1601 where a new burst of N RTTs may be received. If, at step 1623, it is determined that a time of T.sub.1 has elapsed, then at step 1624 the timer T.sub.1 may be reset and then the process may advance to
(121) At step 1701, a value b may be initiated. At step 1702, the entry times of each of the RTTs in Bin b may be examined and if that time is greater than t.sub.0, then at step 1703, that RTT is deleted from Bin b. A value for t.sub.0 may be inputted at step 1501. At step 1704 a check that all the entries in bin b have been examined, c=Cb, and if not, the next c maybe selected at step 1705 and the next entry may be examined at step 1702. If, at step 1704, all the entries in bin b have been examined then at step 1706 it may be determined if all bins have been examined, i.e., b=B. If not, then at step 1707 the value of b may be incremented, and the next bin is checked at step 1702. Stated another way, at the end of a preset interval of T.sub.1, all bins may be examined and all RTTs that are out-of-date, i.e., older than t.sub.o, may be deleted (steps 1701 to 1707). When all bins, 1 to B, have been checked and out-of-date RTTs removed, then at step 1708 the AveRTT for each bin may be re-calculated and the method advances to step 1710 where the counts, Cb, of RTTs in all bins are examined and the highest count, “maxCb”, may be selected.
(122) The process 1500 may then continue through steps 1710 to 1714, 1601 to 1623, and back to 1710, as described above. The calculations and determinations as described above with reference to
(123)
(124) Process 1800 starts with Sub-process 1, 1810. Sub-process 1, 1810 includes and starts by step 1811 where the values for Bin Width, T.sub.W, Time intervals T.sub.1 and t.sub.0, ratio R, and the number of packets in a burst N, are inputted. The parameter B, the number of bins, is initialized and a timer started. As discussed above with reference to
(125)
where Cb is the number of RTTs in Bin b. If, |RTT.sub.n−RTT.sub.b|>T.sub.W/2 for all bins, then the value of B, the number of bins, is incremented, a new bin, Bin B, is created, RTT.sub.n added to that bin and the AveRTT.sub.B is set equal to the value of RTT.sub.n. Each RTT is the result of an exchange of a ranging packet 312 transmitted by Transmitter 1411 and the reception of a response packet 324, from a target station 120, received by Receiver 1412 as discussed above with reference to
(126) Sub-process 2, 1820, includes and starts by step 1821 where the counts, Cb, of RTTs in all bins are examined and the highest count, “maxCb”, and the next highest count, “nextCb” are selected. Sub-process 2 includes step 1822 where the ratio of maxCb to nextCb is calculated. If maxCb/nextCb>R then the bin with the count maxCb is selected, “BINmax”. If maxCb/nextCb<R then no “BINmax” is selected. The Process 1800 then advances to Sub-process 3, 1830.
(127) Sub-process 3 1830 includes and starts by step 1831 where a burst of N RTTs are received. As each RTTn, is received, where n=1 to N, the value of RTTn is compared to the value of AveRTTb for each existing bin, Bin 1 to Bin B, to check if it is within T.sub.W/2 of the AveRTTb, and, if true, then RTT.sub.n is added to that bin b, and the value for AveRTTb calculated, i.e. for b=1 to B, if |RTT.sub.n−AveRTT.sub.b|<T.sub.W/2, then RTTn is added to Bin b, and
(128)
where Cb is the number of RTTs in Bin b. If, |RTT.sub.n−RTT.sub.b|>T.sub.W/2 for all bins, b=1 to B, then the value of B, the number of bins, is incremented, and a new bin, Bin B, is created with RTT.sub.n added to that bin and the AveRTT.sub.B set equal to the value of RTT.sub.n. When all N RTTs have been received, then Process 1800 advances to Sub-process 4 1840.
(129) Sub-process 4, 1840, includes and starts by step 1841 where it is a checked if a BINmax exists, as determined in Sub-process 2, step 1822. If a BINmax does exist then, all those RTTs that have been added to BINmax in the last burst of N RTTs, from Sub-process 3 1830 step 1831, are selected and outputted to the next stage of the geo-location calculations. If no BINmax exists, then no RTTs from the last burst of N RTTs from Sub-process 3 1830, are outputted. Sub-process 4 1840 includes step 1842 where a check is made of the time to determine if a time equal or greater than T.sub.1 has elapsed. If BINmax exists, then for the time period T.sub.1, all RTTs added to BINmax will be outputted to the next stage. If not, then Process 1800 returns to Sub-process 3 1830 where a new burst of N RTTs are received. If, at step 1842, it is determined that a time of T.sub.1 has elapsed, then Process 1800 advances to Sub-process 5 1850. It may be noted that if BINmax exists, then for the time period T.sub.1, all RTTs added to BINmax will be outputted to the next stage.
(130) Sub-process 5 1850 includes and starts by step 1851 where the entry times of each of the RTTs in each Bin b, where b=1 to B, is examined and if the RTT is older than a time greater than t.sub.0, then that RTT is deleted from Bin b. Sub-process 5 1850 includes step 1852 where the AveRTT for each bin is re-calculated. Process 1800 then advances back to Sub-process 2 1820.
(131) Process 1800 then continues through Sub-process 2 1820, Sub-process 3 1830, Sub-process 4 1840 and Sub-process 5 1850, as described above.
(132) The settings of the parameters Bin Width, T.sub.W, Time intervals T.sub.1 and t.sub.0 are interrelated. As discussed above with reference to
(133) TABLE-US-00002 TABLE 2 Time Required to reach R = 2 for 16% wanted RTT, after delay BINS 5 10 20 DELAY, (and t.sub.0), seconds Time to x2 ratio, seconds 5 6 4 3 10 12 8 4 20 23 14 7 30 34 19 10
(134) With t.sub.0=5 seconds, the worst-case delay is 5 seconds, and 10 to 20 bins are possible, assuming a 100 μs reception window. As can be seen from Table 2, as soon as wanted RTTs arrive at a rate of 16%, the bin count ratio exceeds 2 in as little as 4 seconds. If a longer t.sub.0 is selected the number of bins reduces and also the time to overcome the worst-case delay becomes longer. A value for t.sub.0 of 5 seconds is a good compromise.
(135) The value for T.sub.1 should be chosen to be less than t.sub.0 and may be chosen based upon the processing time and overhead. A suitable value for T.sub.1 is 1 second.
(136) The lower the value of the ratio R, the more effective sensitivity is, but the higher the chance that the BINmax is due to noise. The higher the value for ratio R, the better the chance that the BINmax is correct. As discussed above with reference to
(137)
(138) As will be appreciated by one of skill in the art, the concepts described herein may be embodied as a method, data processing system, and/or computer program product. Accordingly, the concepts described herein may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects all generally referred to herein as a “circuit” or “module.” Furthermore, the disclosure may take the form of a computer program product on a tangible computer usable storage medium having computer program code embodied in the medium that can be executed by a computer. Any suitable tangible computer readable medium may be utilized including hard disks, CD ROMs, optical storage devices, or magnetic storage devices.
(139) Some embodiments are described herein with reference to flowchart illustrations and/or block diagrams of methods, systems and computer program products. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.
(140) These computer program instructions may also be stored in a computer readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer readable memory produce an article of manufacture including instruction means which implement the function/act specified in the flowchart and/or block diagram block or blocks.
(141) The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.
(142) It is to be understood that the functions/acts noted in the blocks may occur out of the order noted in the operational illustrations. For example, two blocks shown in succession may in fact be executed substantially concurrently or the blocks may sometimes be executed in the reverse order, depending upon the functionality/acts involved. Although some of the diagrams include arrows on communication paths to show a primary direction of communication, it is to be understood that communication may occur in the opposite direction to the depicted arrows.
(143) Computer program code for carrying out operations of the concepts described herein may be written in an object-oriented programming language such as Java® or C++. However, the computer program code for carrying out operations of the disclosure may also be written in conventional procedural programming languages, such as the “C” programming language. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer. In the latter scenario, the remote computer may be connected to the user's computer through a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).
(144) While the above description contains many specifics, these should not be construed as limitations on the scope, but rather as an exemplification of several embodiments thereof. Many other variants are possible including, for examples: the choices of the variables' values (T.sub.W, T.sub.1, t.sub.0, N, R), the averaging method used for the RTTs in each bin. Accordingly, the scope should be determined not by the embodiments illustrated, but by the claims and their legal equivalents.
(145) It will be appreciated by persons skilled in the art that the present invention is not limited to what has been particularly shown and described herein above. In addition, unless mention was made above to the contrary, it should be noted that all of the accompanying drawings are not to scale. A variety of modifications and variations are possible in light of the above teachings without departing from the scope of the following claims.