Patent Publication Number: US-2013250791-A1

Title: Indoor Positioning System for Standards-Based Narrowband mobile Radios Using Spectrally Overlapping Transmissions

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a continuation-in-part application of U.S. patent application Ser. No. 13/602,451, filed Sep. 4, 2012 (the “&#39;451 application”), which is a continuation-in-part application of U.S. patent application Ser. No. 13/355,557, filed Jan. 22, 2012 (the “&#39;557 application”), now U.S. Pat. No. 8,265,011, which is a continuation-in-part application of U.S. patent application Ser. No. 13/286,649, filed Nov. 1, 2011 (the “&#39;649 application”), now U.S. Pat. No. 8,179,816. This application claims the benefit of U.S. Provisional Patent Application No. 61/652,399 filed May 29, 2012. The &#39;451 application claims the benefit of U.S. Provisional Patent Application No. 61/564,418 filed Nov. 29, 2011. The &#39;557 application claims the benefit of U.S. Provisional Patent Application No. 61/435,269 filed Jan. 22, 2011. The &#39;649 application claims the benefit of U.S. Provisional Patent Application No. 61/409,123 filed Nov. 2, 2010 and U.S. Provisional Patent Application No. 61/421,641 filed Dec. 10, 2010. All of the above mentioned applications are incorporated by reference herein in their entireties. 
    
    
     INTRODUCTION 
     The &#39;649 application describes a method for high-resolution channel sounding that can be used to combat multipath in indoor wireless time-of-flight-based positioning systems. Using this technique, referred to herein as Time-Frequency Offset Wideband (TF-WB) signaling, a transmitter device sends a sequence of narrowband packets to a receiver device at different times and frequencies in order to span a desired bandwidth, where it is assumed that the time, frequency and carrier phase differences among the signal transmissions are known to the receiver. The receiver listens for the transmissions at the known times and frequencies while digitizing and storing them for post-processing, then uses the stored receive signals and the known time, frequency and carrier phase differences to obtain a high-resolution time-of-arrival estimate of the received signals at its antenna. 
     Although it enjoys significant advantages over state-of-the-art wideband and ultra-wideband signaling systems, the technique described in the &#39;649 application requires both transmit and receive devices to have knowledge of TF-WB and to collaborate in order to make it work. Since there are literally billions of wireless devices shipped each year, there is a clear motivation to require only one side of the link—the network side—to have this knowledge. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The skilled artisan will understand that the drawings, described below, are for illustration purposes only. The drawings are not intended to limit the scope of the present teachings in any way. 
         FIG. 1  shows spectral and temporal characteristics of MB-OFDM. 
         FIG. 2  shows spectral and temporal characteristics of TF-WB, in accordance with various embodiments. 
         FIG. 3  is a block diagram of a time-of-flight (ToF)-based positioning system, in accordance with various embodiments. 
         FIG. 4  is a block diagram of a 3-input TF-WB-capable receiver, in accordance with various embodiments. 
         FIGS. 5-7  are exemplary plots that show Wiener filters for each of the 3 antenna paths from  FIG. 4 , in accordance with various embodiments. 
         FIG. 8  is an exemplary flowchart showing a method for calculating the time-of-arrival of a wireless signal through a wireless channel using a receiver device, in accordance with various embodiments. 
         FIG. 9  illustrates an exemplary sequence of narrowband packets that partially overlap in the frequency domain used to facilitate time and carrier phase offset estimation, in accordance with various embodiments. 
         FIG. 10  is an exemplary mathematical model of the exemplary sequence of  FIG. 9 , in accordance with various embodiments. 
         FIG. 11  illustrates an exemplary approach for staggering Tx and Rx phase changes, in accordance with various embodiments. 
         FIG. 12  is an exemplary diagram illustrating exemplary sequences having monotonically increasing vs. non-monotonically increasing packet transmit center frequencies, in accordance with various embodiments. 
     
    
    
     Before one or more embodiments of the present teachings are described in detail, one skilled in the art will appreciate that the present teachings are not limited in their application to the details of construction, the arrangements of components, and the arrangement of steps set forth in the following detailed description or illustrated in the drawings. Also, it is to be understood that the phraseology and terminology used herein is for the purpose of description and should not be regarded as limiting. 
     DESCRIPTION OF VARIOUS EMBODIMENTS 
     Time/frequency offset wideband (TF-WB) signaling is described in the &#39;649 application, which is incorporated by reference herein in its entirety. TF-WB is a technique that allows the time-of-arrival (ToA) of multiple narrowband signals sent sequentially in time and at different center frequencies to be calculated with the same accuracy as a wideband signal spanning the same bandwidth. Although there are other known protocols such as Multi-band OFDM (also referred to as MB-OFDM or ECMA-368, an ultra-wideband or UWB standard) that use a similar means of generating wideband signals to facilitate high-resolution ToA estimates, a key advantage TF-WB provides over such techniques is that TF-WB is designed specifically to be used with pre-existing wireless standards such as IEEE 802.11/WiFi, Bluetooth, GSM/GPRS/EDGE, CDMA, etc. Techniques like those prescribed by MB-OFDM, on the other hand, require very specific changes to the physical layer representation of each data packet and as such cannot be applied more generally to other wireless standards. These conceptual differences are illustrated in  FIGS. 1 and 2 , which show the physical layer characteristics of MB-OFDM and TF-WB, respectively. 
       FIG. 1  highlights the spectral and temporal characteristics  100  of MB-OFDM. With MB-OFDM, each data packet  120  is transmitted as a sequence of OFDM symbols  140  that are frequency-hopped across a bandwidth that is three times as wide as that of an OFDM symbol. Since each packet  115  spans the entire 3× bandwidth as shown in plots  110  and  130 , an optimal ToA estimate can be obtained by receiving only one packet. Very little is gained by receiving additional packets. With MB-OFDM, the “narrowband signals transmitted sequentially in time and at different center frequencies” are the OFDM symbols  140  that comprise each of its data packets  115 . 
       FIG. 2  highlights the spectral and temporal characteristics  200  of TF-WB, in accordance with various embodiments. With TF-WB the “narrowband signals” are the data packets themselves, and frequency hopping is used between packets, as shown in plot  210 —not during each packet as with MB-OFDM, as shown in plot  130  of  FIG. 1 . Returning to  FIG. 2 , TF-WB allows each data packet to be transmitted in its entirety at a fixed frequency using any desired modulation scheme—to accommodate pre-existing wireless standards. Also to accommodate pre-existing standards, TF-WB allows for arbitrary (not necessarily uniformly or precisely spaced) time differences between the data packets  220 . MB-OFDM, on the other hand, demands fixed, uniformly and precisely spaced time-differences between the OFDM symbols  140  of  FIG. 1 . Finally, MB-OFDM demands each of the OFDM symbols to be transmitted using the same carrier phase. TF-WB, on the other hand, allows each of its data packets to be transmitted with arbitrarily different carrier phases—again to accommodate pre-existing standards (most of these standards don&#39;t require the carrier phase to remain constant over different transmit frequencies). 
     In summary, unlike other known methods of transmitting multiple narrowband signals sequentially in time and at different center frequencies to improve ToA accuracy, TF-WB allows data packets to be transmitted at fixed center frequencies and with arbitrary time and carrier phase offsets. These key differences come from its being designed specifically to facilitate high-resolution ToA measurements using pre-existing wireless protocols. 
     In various embodiments, legacy time/frequency offset wideband (LTF-WB) signaling allows a network of wireless receivers to locate a mobile transmitter using TF-WB signaling techniques without requiring the mobile to know anything about TF-WB, or even that it&#39;s being located. LTF-WB allows, for example, a network of LTF-WB-capable IEEE 802.11 WiFi Access Points to locate any WiFi mobile device—even if it doesn&#39;t support TF-WB per se. 
     While the techniques described herein can be applied to a broad class of wireless protocols (including cellular, 3G, WiMax, etc.), the following examples relate to the IEEE 802.11 Wireless LAN (WiFi) standard. 
     System Overview 
       FIG. 3  is a block diagram of a ToF-based positioning system  300 , in accordance with various embodiments. System  300  includes a mobile Client device  20 , a plurality of sensor/emitter (SE) devices  30  and a Server  40 . Client device  20  is typically a battery-powered mobile device such as a smartphone or a laptop computer containing a wireless communication chipset that complies with a wireless standard, which for the purposes of this discussion it is assumed to be IEEE 802.11/WiFi. 
     SE devices  30 , typically the size of a WiFi Access Point (AP), are placed in various known positions in an indoor environment such as a hospital, retail store or a shopping mall. A primary function of SE devices  30  is to measure the ToAs of LTF-WB transmissions received from Client device  20  in order to estimate its position. All SE devices  30  in a network are coarsely time synchronized to a common time base in order to simultaneously receive, digitize, and store incoming transmissions from Client device  20 . SE devices  30  also perform 802.11 transmit functions in order to spoof the Client devices  20 , as is discussed below. 
     Server  40  is used to control the behavior of the Client devices  20  and SE devices  30  during the ToA measurements and to estimate the position u of Client device  20  based on ToA measurements received from the SE devices  30  by solving 
     
       
         
           
             
               
                 u 
                 ^ 
               
               = 
               
                 
                   
                     
                       arg 
                        
                       
                           
                       
                        
                       min 
                     
                      
                     
                         
                     
                   
                   u 
                 
                  
                 
                   
                     min 
                     t 
                   
                    
                   
                     
                       ∑ 
                       
                         n 
                         = 
                         1 
                       
                       N 
                     
                      
                     
                       
                          
                         
                           
                              
                             
                               u 
                               - 
                               
                                 u 
                                 n 
                               
                             
                              
                           
                           - 
                           
                             c 
                              
                             
                               ( 
                               
                                 
                                   t 
                                   n 
                                 
                                 - 
                                 t 
                               
                               ) 
                             
                           
                         
                          
                       
                       2 
                     
                   
                 
               
             
             , 
           
         
       
     
     where u n  is the known [x y z] position of the nth SE, c is the speed of light, t n  is the nth SE&#39;s ToA estimate, and t is the unknown transmission time of the Client&#39;s LTF-WB location signal. 
     As described in the &#39;649 application, the basic steps for TF-WB transmission, reception, and ToA estimation are as follows:
         1. Transmitter sends a sequence of narrowband signals at different times and frequencies to the receiver. It is assumed that the time, frequency and carrier phase differences among the signal transmissions are known to the receiver.   2. Receiver listens for the transmissions at the known times and frequencies while digitizing and storing them for post-processing.   3. Receiver uses the stored receive signals and the known time, frequency and carrier phase differences of the transmissions to obtain a high-resolution estimate of the time-of-arrival of the received signals at its antenna.       

     In various embodiments, the steps for LTF-WB transmission, reception, and ToA estimation are as follows:
         1. Receiver (i.e., the SE) spoofs the transmitter into sending a sequence of narrowband signals at different times and frequencies to the receiver by sending it a special message.   2. Transmitter (i.e., the Client) accepts the spoof directive and sends a sequence of narrowband signals at different times and frequencies to the receiver.   3. Receiver (SE) listens for the narrowband signal transmissions at the known times and frequencies while digitizing and storing them for post-processing.   4. Receiver (SE) knows the sequence of frequencies and the approximate time differences among transmissions, but in most cases does not know and must therefore estimate the specific time and carrier phase differences.   5. Receiver (SE) uses the stored receive signals, the known approximate time and frequency differences, and the estimated specific time and carrier phase differences to obtain a high-resolution estimate of the time-of-arrival of the received signals at its antenna.       

     In various embodiments, Client device  20  is an IEEE 802.11 WiFi Client. Methods for spoofing a WiFi Client include, but are not limited to:
         1. SE sends Client an 802.11 DISASSOCIATE message, causing the Client to dissociate from the network and start an Active Scan, sending Probe Request messages on each one of its supported RF frequencies in sequence.   2. If the Client supports 802.11k, the SE could send it an 802.11k BEACON REQUEST message, causing it to respond by sending back PROBE REQUEST messages at each frequency in a set of AP-specified channels in sequence. This approach is preferred over the previous one, since in this case the Client is not forced to disassociate from the network.   3. If the Client supports 802.11v, the SE could send it an 802.11v LOCATION CONFIGURATION REQUEST message, giving the Client a list of frequencies at which to send LOCATION TRACK NOTIFICATION messages. This approach is preferred over the 802.11k approach, since it gives the SE more control over the specific set of frequencies and the time the Client spends on each frequency.       

     Time-of-Arrival Estimation 
     In various embodiments, a mathematical representation of the sequence of transmissions leaving the Client&#39;s antenna in response to the SE&#39;s spoof message is 
     
       
         
           
             
               
                 
                   
                     
                       x 
                        
                       
                         ( 
                         t 
                         ) 
                       
                     
                     = 
                     
                       Re 
                        
                       
                         { 
                         
                           
                             ∑ 
                             
                               k 
                               = 
                               1 
                             
                             K 
                           
                            
                           
                             
                               
                                 x 
                                 k 
                               
                                
                               
                                 ( 
                                 
                                   t 
                                   - 
                                   
                                     τ 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                                
                               
                                 
                                   j 
                                    
                                   
                                       
                                   
                                    
                                   2 
                                    
                                   
                                     π 
                                      
                                     
                                       ( 
                                       
                                         
                                           f 
                                           c 
                                         
                                         + 
                                         
                                           f 
                                           k 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   t 
                                 
                                 + 
                                 
                                   jφ 
                                   k 
                                 
                               
                             
                           
                         
                         } 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     where Re(z) represents the real part of the complex number z, K is the number of narrowband waveforms transmitted, and x k (t) is the complex envelope of the kth narrowband waveform transmitted at time τ k , carrier frequency f c +f k  and carrier phase φ k . The transmission time τ 1  of the first waveform can be assumed to be zero without loss of generality. This way, the remaining τ k  can be viewed as time offsets relative to transmit time of the first waveform. The waveform described by equation (1) above is referred to as a LTF-WB waveform. 
     In various embodiments, an SE device  30  uses the following high-level steps to estimate the time-of-arrival of a received, downconverted, digitized, and stored LTF-WB waveform:
         1. Digitally upconverts the received narrowband observation waveforms to their known offset frequencies and sums, yielding a wideband observation waveform.   2. Synthesizes a reference waveform corresponding to each of the received narrowband observation waveforms using the known (and optionally decoded) portions of the data packets and the rules prescribed by the wireless standard.   3. Given the narrowband reference waveforms, the known offset frequencies, and a hypothetical set of the following parameters: time and carrier phase offsets between narrowband LTF-WB transmissions, channel impulse response, and channel propagation delay; defines a model to generate a “wideband model output waveform”—a most-likely guess for what the wideband observation waveform would look like given the known information and that choice of parameters.   4. Using an iterative multi-dimensional search, finds the set of parameters (time and carrier phase offsets, channel impulse response, and channel propagation delay) that most closely match the wideband model output and wideband observation waveforms.       

     The resulting channel propagation delay from this process is the estimated time-of-arrival. 
     These steps are again described in greater detail and with more mathematical rigor:
         1. Digitally upconvert the received narrowband observation waveforms y k (nT) to their known offset frequencies f k , yielding the wideband observation waveform       

     
       
         
           
             
               y 
                
               
                 ( 
                 nT 
                 ) 
               
             
              
             
               = 
               Δ 
             
              
             
               
                 ∑ 
                 
                   k 
                   = 
                   1 
                 
                 K 
               
                
               
                 
                   
                     y 
                     k 
                   
                    
                   
                     ( 
                     
                       n 
                        
                       
                           
                       
                        
                       T 
                     
                     ) 
                   
                 
                  
                 
                    
                   
                     j2π 
                      
                     
                         
                     
                      
                     
                       f 
                       k 
                     
                      
                     n 
                      
                     
                         
                     
                      
                     T 
                   
                 
               
             
           
         
       
         
         
           
             2. For each received narrowband observation waveform y k (nT), synthesize a corresponding narrowband reference waveform {circumflex over (x)} k (nT) by encoding and modulating known portions of the waveform (including the physical layer preamble and any known data bits) as specified by the wireless standard. The receiver may optionally choose to demodulate and decode other unknown portions of the packet and add the decoded data to the known information that gets encoded and modulated to generate the narrowband reference waveform {circumflex over (x)}′ k (nT) as well. If the receiver decides not to include the decoded information in the narrowband reference waveform, it sets the corresponding portions of that waveform to zero. 
             3. Given the narrowband reference waveforms {circumflex over (x)} k (nT), the known frequency offsets f k  and a set of parameters {τ 0 , φ, τ}, with τ [0 τ 2  . . . τ K ] T  and φ  [0 φ 2  . . . φ K ] T  being the time and carrier phase offsets between transmissions, respectively and τ 0  being the channel propagation delay, generate a wideband reference signal defined by 
           
         
       
    
     
       
         
           
             
               
                 
                   x 
                   ^ 
                 
                  
                 
                   ( 
                   
                     
                       n 
                        
                       
                           
                       
                        
                       T 
                     
                     , 
                     
                       τ 
                       0 
                     
                     , 
                     φ 
                     , 
                     τ 
                   
                   ) 
                 
               
                
               
                 = 
                 Δ 
               
                
               
                 
                   ∑ 
                   
                     k 
                     = 
                     1 
                   
                   K 
                 
                  
                 
                   
                     
                       
                         x 
                         ^ 
                       
                       k 
                     
                      
                     
                       ( 
                       
                         
                           n 
                            
                           
                               
                           
                            
                           T 
                         
                         - 
                         
                           τ 
                           k 
                         
                         - 
                         
                           τ 
                           0 
                         
                       
                       ) 
                     
                   
                    
                   
                      
                     
                       
                         j 
                          
                         
                             
                         
                          
                         2 
                          
                         π 
                          
                         
                             
                         
                          
                         
                           
                             f 
                             k 
                           
                            
                           
                             ( 
                             
                               
                                 n 
                                  
                                 
                                     
                                 
                                  
                                 T 
                               
                               - 
                               
                                 τ 
                                 0 
                               
                             
                             ) 
                           
                         
                       
                       + 
                       
                         j 
                          
                         
                             
                         
                          
                         
                           φ 
                           k 
                         
                       
                     
                   
                 
               
             
             , 
           
         
       
         
         
           
              The first elements of the τ and φ vectors are zero because the only relevant factors are the timing and phase differences of the 2 nd , 3 rd , etc. burst relative to the first burst; and it is assumed without loss of generality that τ 1 =φ 1 =0. It should also be noted that with a noise and multipath-free channel and with the correct choice of candidates {τ 0 , φ, τ}, the wideband reference and wideband observation waveforms should be identical. 
             4. Find the Wiener filter that best matches the wideband reference signal {circumflex over (x)}(nT, τ 0 , φ, τ) generated in the previous step to the wideband observation signal y(nT), then filter the wideband reference signal through the Wiener filter. Mathematically speaking, the Wiener filter is given by 
           
         
       
    
         h=h (τ 0 ,φ,τ) [ R   XX (τ 0 ,φ,τ)] −1   R   XY (τ 0 ,φ,τ),
          where R XY (τ 0 , φ, τ) is the cross correlation vector between the wideband reference and observation signals, and R XX (τ 0 , φ, τ) is the autocorrelation matrix for the wideband reference signal. Note that each candidate  2 K+1-tuple {τ 0 , φ, τ} will produce a different Wiener filter h, hence the alternative notation h(τ 0 , φ, τ) used above.    It should be noted that with a noise-free channel and with the correct choice of candidates {τ 0 ,φ,τ}, (a) the Wiener filter output and the wideband observation waveforms should be identical, and (b) the frequency response of the channel and the Wiener filter should be identical over all active RF transmit frequencies.   5. Iteratively repeat steps 3 and 4 using various choices of {τ 0 ,φ,τ} to find the candidates {{circumflex over (τ)} 0 ,{circumflex over (φ)},{circumflex over (τ)}} that jointly minimize the mean-square error between the Wiener filter output and the wideband observation waveform; the value of {circumflex over (τ)} 0  that results from this process is the ToA estimate. This step can be written mathematically as follows:       

     
       
         
           
             
               
                 
                   τ 
                   ^ 
                 
                 0 
               
               = 
               
                 
                   
                     arg 
                      
                     
                         
                     
                      
                     min 
                   
                   
                     τ 
                     0 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     
                       
                           
                       
                        
                       min 
                     
                     
                       φ 
                       , 
                       τ 
                     
                   
                    
                   
                     
                       ∑ 
                       n 
                     
                      
                     
                       
                          
                         
                           
                             y 
                              
                             
                               ( 
                               
                                 n 
                                  
                                 
                                     
                                 
                                  
                                 T 
                               
                               ) 
                             
                           
                           - 
                           
                             
                               
                                 x 
                                 ^ 
                               
                                
                               
                                 ( 
                                 
                                   
                                     n 
                                      
                                     
                                         
                                     
                                      
                                     T 
                                   
                                   , 
                                   
                                     τ 
                                     0 
                                   
                                   , 
                                   φ 
                                   , 
                                   τ 
                                 
                                 ) 
                               
                             
                             * 
                             
                               h 
                                
                               
                                 ( 
                                 
                                   
                                     τ 
                                     0 
                                   
                                   , 
                                   φ 
                                   , 
                                   τ 
                                 
                                 ) 
                               
                             
                           
                         
                          
                       
                       2 
                     
                   
                 
               
             
             , 
           
         
       
         
         
           
              where the asterisk in the above formula represents the convolution operator. Any one of a number of well-known multi-dimensional minimization techniques can be used to minimize the number of iterations required to find the optimal set of candidates, including the Simplex method, Newton&#39;s method, BFGS, etc. 
           
         
       
    
     Learning and Remembering How Different Manufacturer&#39;s Chipsets Behave 
     Since there are only a handful of manufacturers of WiFi chipsets, in various embodiments the behavior of each manufacturer&#39;s chipset is measured and characterized in response to the spoof messages in order to optimize the efficiency of the AP/Client exchange. For example, the order at which the Client visits the frequencies, the time it spends on each frequency, and/or the number of times it transmits at each frequency can be measured, since some of this information is not clearly specified in the 802.11 standard and left up to the Client manufacturer&#39;s discretion. This vendor-specific information could then store be stored in a database and later retrieved by the AP when it&#39;s online, using the vendor ID portion of the Client&#39;s MAC address to determine the Client manufacturer&#39;s identity. 
     Other useful information that could be stored in such a database includes:
         1. Time offset between transmissions—the Client&#39;s time between transmissions at different frequencies can be carefully measured, and the results tabulated using a histogram. The AP could use the histogram to optimize its iterative parameter search in Step 5 above.   2. Carrier phase offsets between transmissions—the carrier phase offsets between Client transmissions at different frequencies can be measured, and the results tabulated using a histogram, stored in the database, and used to optimize the search in Step 5 as well.       

     Exploiting Time-of-Departure Information from Clients that Support 802.11v 
     The IEEE 802.11v standard supports a time-stamp mechanism in which the PHY loads the contents of a high-speed timer into the TIME-OF-DEPARTURE field of each packet immediately before transmission. In various embodiments, an LTF-WB-capable AP can decode from the packets received from the Client and subtract the time-stamps to obtain the actual time offsets, i.e., the vector τ defined in Step 3 above. This removes τ as an unknown from Step 5 and simplifies the search considerably. More specifically, using τ act  to denote the actual time differences computed by decoding and subtracting the time-stamps, the multidimensional search in Step 5 would simplify to the following (note that the minimization is now only over φ and not φ and τ): 
     
       
         
           
             
               
                 τ 
                 ^ 
               
               0 
             
             = 
             
               
                 
                   arg 
                    
                   
                       
                   
                    
                   min 
                 
                 
                   τ 
                   0 
                 
               
                
               
                   
               
                
               
                 
                   
                       
                   
                    
                   min 
                 
                 φ 
               
                
               
                 
                   ∑ 
                   n 
                 
                  
                 
                   
                     
                        
                       
                         
                           y 
                            
                           
                             ( 
                             
                               n 
                                
                               
                                   
                               
                                
                               T 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               x 
                               ^ 
                             
                              
                             
                               ( 
                               
                                 
                                   n 
                                    
                                   
                                       
                                   
                                    
                                   T 
                                 
                                 , 
                                 
                                   τ 
                                   0 
                                 
                                 , 
                                 φ 
                                 , 
                                 
                                   τ 
                                   act 
                                 
                               
                               ) 
                             
                           
                           * 
                           
                             h 
                              
                             
                               ( 
                               
                                 
                                   τ 
                                   0 
                                 
                                 , 
                                 φ 
                                 , 
                                 
                                   τ 
                                   act 
                                 
                               
                               ) 
                             
                           
                         
                       
                        
                     
                     2 
                   
                   . 
                 
               
             
           
         
       
     
     Multi-Input Receivers and Joint Time/Angle of Arrival Measurements 
     Nearly all IEEE 802.11n-compatible APs and some Clients are equipped with multi-input receivers, allowing them to receive, downconvert and digitize signals through up to 4 antenna paths simultaneously. In various embodiments, a multi-input receiver can be leveraged to improve the accuracy of the ToA estimates in indoor environments. The improved performance comes from having additional uncorrelated (or loosely correlated) observations of the ToA through the new antenna paths. 
     If a multi-input receiver is used to receive a LTF-WB signal, that receiver downconverts, digitizes, and stores each incoming narrowband transmission through each of its M antenna paths simultaneously. For ToA estimation, it computes wideband observation waveforms and Wiener filters for each antenna path, and uses the following formula to estimate the ToA, which is a generalization of the formula in Step 5 above for multiple antenna paths: 
     
       
         
           
             
               
                 
                   
                     
                       τ 
                       ^ 
                     
                     0 
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         τ 
                         0 
                       
                     
                      
                     
                         
                     
                      
                     
                       
                         
                             
                         
                          
                         min 
                       
                       
                         φ 
                         , 
                         τ 
                       
                     
                      
                     
                       
                         
                           ∑ 
                           
                             m 
                             = 
                             1 
                           
                         
                         M 
                       
                        
                       
                         
                           ∑ 
                           n 
                         
                          
                         
                           
                             
                                
                               
                                 
                                   
                                     y 
                                     
                                       〈 
                                       m 
                                       〉 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       n 
                                        
                                       
                                           
                                       
                                        
                                       T 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     
                                       x 
                                       ^ 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           n 
                                            
                                           
                                               
                                           
                                            
                                           T 
                                         
                                         , 
                                         
                                           τ 
                                           0 
                                         
                                         , 
                                         φ 
                                         , 
                                         τ 
                                       
                                       ) 
                                     
                                   
                                   * 
                                   
                                     
                                       h 
                                       
                                         〈 
                                         m 
                                         〉 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           τ 
                                           0 
                                         
                                         , 
                                         φ 
                                         , 
                                         τ 
                                       
                                       ) 
                                     
                                   
                                 
                               
                                
                             
                             2 
                           
                           
                             σ 
                             m 
                             2 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     where y &lt;m&gt; (nT) and h &lt;m&gt; (τ 0 ) are the wideband observation waveform and Wiener filters, respectively, and σ m   2  is the average noise power per sample in the mth antenna path. This can be shown to be a maximum-likelihood estimate for the ToA τ 0  given the system model described herein. The estimator can be described in words as follows:
         For each candidate combination of ToA, timing offsets and carrier phase offsets
           for each antenna path
               compute the mean-square error (MSE) between the observed and model output waveforms for that candidate ToA   normalize the MSE by the noise power in that antenna path   
               sum normalized MSEs for each antenna path   
           Find the candidate combination of ToA, timing offsets and carrier phase offsets that produces the lowest summed MSE over all antenna paths. The ToA estimate {circumflex over (τ)} 0  is the ToA element of that combination.       

     An alternative to the approach described above of summing the MSE&#39;s for each antenna path at each candidate ToA would be to estimate the ToA for each antenna path using steps 1-5 above (or any other technique) and combine these ToAs into a final ToA estimate by computing their mean, max, min, median, mode, etc. 
     It should be noted that the multi-input ToA estimator described above can be used to enhance the performance of any single-antenna path ToA estimator—not just one that uses LTF-WB signaling. In other words, for any system that transmits a known reference waveform {circumflex over (x)}(nT, τ 0 ) through a multipath additive white Gaussian noise channel with propagation delay τ 0  and receives through a multi-input receiver yielding observation waveforms y &lt;m&gt; (nT), m=1, . . . , M for each of the M antenna paths, the approach described above can be shown to provide the optimum ToA estimate. 
     In addition to improving the time-resolution of indoor time-of-arrival (ToA) measurements, LTF-WB can also be used to improve the accuracy of indoor angle-of-arrival (AoA) measurements as well. A multi-input receiver is required for AoA. 
       FIG. 4  is a block diagram of a 3-input LTF-WB-capable receiver  400 , in accordance with various embodiments. The received LTF-WB signals from each antenna path are downconverted  260 , digitized  265 , adjusted for gain dependent group delay and phase shift  270 , and stored  275 - 277 . To estimate the AoA  310 , the ToA of the received LTF-WB signals is found first using equation (2) above, then the phase angle of the incoming transmission on each antenna path is estimated by computing the phase angle of Wiener filter at the tap corresponding to the LOS path. The three phase angles computed in this step can then be converted into an AoA estimate  320  based on the physical geometry of the antennas. The advantage of using LTF-WB signaling for the AoA measurements is multipath suppression. The high time resolution allows the Wiener filter to discriminate the LOS from other paths, so the phase angle shown is the phase of the signal coming in the direction of the LOS path only—not other paths. For lower bandwidth signals, the LOS path would be summed with multipath reflections from other paths, yielding distorted phase estimates. 
       FIGS. 5-7  are plots of signal level produced by Wiener filters for the three antenna paths of the receiver shown in  FIG. 2 , in accordance with various embodiments. 
     Alternatives to Spoofing 
     Instead of spoofing the client into sending an LTF-WB sequence, one may use software on the client to get it to send the sequence. For example, the operating system used on Google Android smartphones provides a function in its application programming interface (API) which when executed, causes the smartphone to perform an 802.11 Active Scan, sending 802.11 Probe Request messages on each of its supported RF frequencies in sequence. This, for example, would allow a programmer to write a Google Android application that can generate LTF-WB sequences by doing 802.11 Active Scans on command from the network. Unlike spoofing, this would obviously require a modification to the client device to support this new functionality, but the change is only in software; no hardware changes to the client are necessary. Note however that without hardware changes on the client side, the time offsets and carrier phase differences between the narrowband transmissions will not generally be available to the client software, and so will have to be estimated by the LTF-WB-enabled receiver on the network side in order to estimate the ToA of the received sequence. 
     Receiver Calibration 
     Most digital receivers use some sort of automatic gain control (AGC) to adjust their received signal level entering the analog-to-digital converter (ADC). The gain control circuit is often implemented as a set of variable gain amplifiers (VGAs) in series that can be either switched on and off depending on the value of an input gain control word. When a VGA stage is turned on vs. off, it can create a carrier phase and/or group delay change. If the receiver changes its AGC setting to receive the narrowband transmissions at different frequencies, the phase shifts and group delay changes will create distortion in the received waveforms. 
     Fortunately, these phase and group delay vs. Rx gain variations don&#39;t change much across time and temperature, so they can be calibrated (i.e., measured at the time of manufacturing), stored in a table, and compensated for during data digitization and data storage. 
     LTF-WB Receiver System 
     Referring to  FIG. 4 , a system for calculating the time-of-arrival of a wireless signal through a wireless channel includes receiver device  400 . Receiver device  40  can include, but is not limited to, an access point, a smartphone, a laptop computer, or a wireless smart tag. Receiver device  1200  can include hardware, software, or a combination of hardware and software. 
     Receiver device  400  receives two or more data packets transmitted through a wireless channel. The two or more data packets are a result of two or more transmissions that are made sequentially in time at different center frequencies in order to span a desired bandwidth. Each data packet of the two or more data packets is transmitted at a single center frequency. 
     Receiver device  400  estimates time differences among the two or more transmissions and/or carrier phase differences among the two or more transmissions. 
     Receiver device  400  calculates a time-of-arrival of one or more data packets of the two or more data packets using each data packet of the two or more received data packets and one or more of the estimated time differences, the different center frequencies, and the estimated carrier phase differences. 
     The two or more data packets are different data packets, for example. In various embodiments, the two or more data packets are the same data packets. 
     In various embodiments, the two or more data packets conform to the IEEE 802.11 (Wi-Fi™) standard, the Bluetooth™ standard, or the Global System for Mobile Communications (GSM) standard. 
     In various embodiments, the two or more data packets include IEEE 802.11 Probe Request packets, path loss measurement packets, or IEEE 802.11v or Cisco CCX™ path loss measurement packets sent at different times and frequencies. 
     In various embodiments, receiver device  400  further calculates an angle of arrival of at least one data packet of the two or more data packets. Receiver device  400  receives the two or more data packets through two or more antenna paths  250 ,  280 , and  290  simultaneously. Receiver device  400  estimates carrier phases of the two or more data packets received through each antenna path. Receiver device  400  converts the estimated carrier phases into an angle-of-arrival estimate. 
     In various embodiments, at least one additional receiver device is included that receives the two or more data packets. The at least one additional receiver device calculates an additional time-of-arrival for the two or more data packets. The time-of-arrival and the additional time-of-arrival are used to calculate a location for a device that transmitted the two or more data packets. 
     In various embodiments, the estimated time offsets and/or estimated carrier phase offsets and/or center frequencies of two or more data packets associated with a group of devices that share a common vendor ID in their MAC address are stored in a database. The information is later retrieved from the database using the decoded vendor IDs from the two or more data packets. The retrieved information is then used in the time-of-arrival calculation. 
     In various embodiments, receiver device  400  sends a spoof message before receiving the two or more data packets that causes the two or more transmissions. The spoof message includes an 802.11 DISASSOCIATE message and the two or more transmissions include PROBE REQUEST messages, for example. In various embodiments, the spoof message includes an 802.11k BEACON REQUEST message and the two or more transmissions include PROBE REQUEST messages. In various embodiments, the spoof message includes an 802.11v LOCATION CONFIGURATION REQUEST message that provides the different center frequencies and the two or more transmissions include LOCATION TRACK NOTIFICATION messages. 
     In various embodiments, receiver device  400  further receives two or more calibration data packets before receiving the two or more data packets. Receiver device  400  uses the two or more calibration data packets to construct a calibration table. The calibration table stores measured changes in group delay and phase shift over a set of receiver gain settings and/or RF center frequencies. Receiver device  400  later uses the calibration table contents in time-of arrival and/or angle-of-arrival calculations. 
     In various embodiments, the two or more data packets are 802.11v data packets that include time-stamps. Receiver device  400  uses differences among the time-stamps as the estimated time differences. 
     In various embodiments, the two or more data packets are received simultaneously through a plurality of antenna paths  250 ,  280 , and  290 . A time-of-arrival is calculated for each antenna path producing a plurality of time-of-arrival values. The plurality of time-of-arrival values are combined into a final time-of-arrival estimate. 
     In various embodiments, the two or more data packets are received simultaneously through a plurality of antenna paths  250 ,  280 , and  290 . The steps of estimating and calculating are based on received data packets from each antenna path of the plurality of antenna paths. 
     In various embodiments, receiver device  400  sends a message to a transmitter device (not shown) before receiving the two or more data packets causing application software running in the transmitter device to perform an 802.11 Active Scan. The transmitter device is a smartphone and the application software is an application running on the smartphone operating system, for example. 
     LTF-WB Receiver Method 
       FIG. 8  is an exemplary flowchart showing a method  800  for calculating the time-of-arrival of a wireless signal through a wireless channel using a receiver device, in accordance with various embodiments. 
     In step  810  of method  800 , two or more data packets transmitted through a wireless channel are received using a receiver device. The two or more data packets are a result of two or more transmissions that are made sequentially in time at different center frequencies in order to span a desired bandwidth. Each data packet of the two or more data packets is transmitted at a single center frequency. 
     In step  820 , time differences among the two or more transmissions and/or carrier phase differences among the two or more transmissions are estimated. 
     In step  830 , a time-of-arrival of one or more data packets of the two or more data packets is calculated using each data packet of the two or more data packets and one or more of the estimated time differences, the different center frequencies, and the estimated carrier phase differences. 
     Alternative ToA Estimation Techniques 
     One alternative ToA estimation technique to those described herein combines the mean-square-error (MSE) vs. candidate ToA curves for each received narrowband transmission and chooses the ToA candidate with the minimum combined MSE as the estimated ToA. This can be described mathematically as follows:
         1. For each received narrowband transmission y k (.), compute the MSE vs. candidate ToA curve       

     
       
         
           
             
               
                 
                   ɛ 
                   k 
                 
                  
                 
                   ( 
                   t 
                   ) 
                 
               
               = 
               
                 
                   min 
                   
                     
                       h 
                       k 
                     
                      
                     
                       ( 
                       n 
                       ) 
                     
                   
                 
                  
                 
                   
                     ∑ 
                     n 
                   
                    
                   
                     
                        
                       
                         
                           
                             y 
                             n 
                           
                            
                           
                             ( 
                             
                               n 
                                
                               
                                   
                               
                                
                               T 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               x 
                               k 
                             
                              
                             
                               ( 
                               
                                 
                                   n 
                                    
                                   
                                       
                                   
                                    
                                   T 
                                 
                                 , 
                                 
                                   
                                     τ 
                                     k 
                                   
                                   - 
                                   t 
                                 
                               
                               ) 
                             
                           
                           * 
                           
                             
                               h 
                               k 
                             
                              
                             
                               ( 
                               n 
                               ) 
                             
                           
                         
                       
                        
                     
                     2 
                   
                 
               
             
             , 
           
         
       
         
         
           
              over some appropriate interval tε(T min , T max ) containing the actual ToA with high confidence. The MSE curve ε k (t) is computed as follows: for each ToA candidate tε(T min , T max ), the complex envelope of the kth transmitted narrowband reference waveform x k (.) is delayed by the candidate ToA t plus its transmit time offset τ k , then filtered through the Wiener filter h k (n) that best matches the time-adjusted reference waveform samples x k (nT−τ k −t) to the observation y k (nT). The Wiener filter output is then subtracted from the observation y k (nT), yielding an error signal from which a norm-squared operation is computed, yielding the MSE curve ε k (t). If the transmit time offsets τ k  are unknown to the receiver, they can be estimated, for example, by cross correlating the observation waveforms with their corresponding reference waveforms, and finding the time differences between the correlation peaks. Without noise or multipath each of the MSE curves ε k (t) will achieve their minimums at the actual ToA t=T act . 
             2. Sum the MSE curves together. The ToA estimate is the time t that produces the smallest summed MSE, i.e., 
           
         
       
    
     
       
         
           
             
               
                 τ 
                 ^ 
               
               act 
             
             = 
             
               
                 
                   arg 
                    
                   
                       
                   
                    
                   min 
                 
                 t 
               
                
               
                   
               
                
               
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                   
                   K 
                 
                  
                 
                   
                     ɛ 
                     k 
                   
                    
                   
                     ( 
                     t 
                     ) 
                   
                 
               
             
           
         
       
     
     An alternative technique estimates the ToA of each narrowband observation y k (nT) and subtracts the known time offset relative to the first transmission, yielding a set of K preliminary estimates of the desired ToA τ act . The preliminary estimates are then combined into a final estimate using their mean, median, minimum, maximum, mode, etc. The steps are detailed as follows:
         1. Estimate the ToA of the kth narrowband transmission. To estimate the ToA one may cross-correlate the known narrowband transmit waveform x k (nT) with the narrowband observation waveform y k (nT) and find the time of the first peak exceeding a threshold. Another approach would be to use the MMSE solution:       

     
       
         
           
             
               
                 
                   t 
                   ^ 
                 
                 k 
               
               = 
               
                 
                   
                     arg 
                      
                     
                         
                     
                      
                     min 
                   
                   
                     t 
                     k 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     
                         
                     
                      
                     min 
                   
                   
                     h 
                      
                     
                       ( 
                       
                         t 
                         k 
                       
                       ) 
                     
                   
                 
                  
                 
                   
                     ∑ 
                     n 
                   
                    
                   
                     
                        
                       
                         
                           
                             y 
                             k 
                           
                            
                           
                             ( 
                             
                               n 
                                
                               
                                   
                               
                                
                               T 
                             
                             ) 
                           
                         
                         - 
                         
                           
                             
                               x 
                               k 
                             
                              
                             
                               ( 
                               
                                 
                                   n 
                                    
                                   
                                       
                                   
                                    
                                   T 
                                 
                                 - 
                                 
                                   t 
                                   k 
                                 
                               
                               ) 
                             
                           
                           * 
                           
                             h 
                              
                             
                               ( 
                               
                                 t 
                                 k 
                               
                               ) 
                             
                           
                         
                       
                        
                     
                     2 
                   
                 
               
             
             , 
           
         
       
         
         
           
              or, in words, the MMSE ToA estimate {circumflex over (t)} k  is the time shift applied to the known transmit signal x k (nT) that after Wiener filtering best matches the observation y k (nT) in the MSE sense. 
             2. Subtract from each {circumflex over (t)} k  the time offset τ k  between the 1 st  and kth transmissions, yielding K preliminary estimates of τ act , the propagation delay between the transmitter and the receiver (assume τ 1 =0): 
           
         
       
    
       {circumflex over (τ)} act,k     {circumflex over (t)}   k −τ k ≅τ k +τ act −τ k =τ act  
          If the transmit time offsets τ k  are unknown to the receiver, they can be estimated, for example, by cross correlating the observation waveforms with their corresponding reference waveforms, and computing the time differences between the correlation peaks.   3. Combine the preliminary estimates into one estimate for {circumflex over (τ)} act  using their mean, median, max, min or mode, i.e.,       

       {circumflex over (τ)} act     C{{circumflex over (τ)}   act,1 ,{circumflex over (τ)} act,2 , . . . ,{circumflex over (τ)} act,K },
          where C=max, min, mean, median or mode.       

     Spectrally Overlapping Transmissions 
     One way to simplify the process of estimating the time and phase offsets is to use spectrally overlapping transmissions. This allows the receiver to use the information received in the overlapping portions of the spectrum to estimate the offsets.  FIG. 9  illustrates an exemplary sequence  900  of narrowband packets that partially overlap in the frequency domain used to facilitate time and carrier phase offset estimation, in accordance with various embodiments. Specifically, the Legacy mobile device transmits a sequence of narrowband (e.g., IEEE 802.11/WiFi) packets  910  at partially overlapping center frequencies  920  to a receiver device. The receiver device then estimates the unknown time  930  and carrier phase  940  offsets from the received sequence. The estimated offsets are then used to estimate the TOA of the received sequence. The boxes outlined with dashed lines  950  indicate where the receiver is tuned during each packet transmission.  FIG. 10  is an exemplary mathematical model  1000  of the exemplary sequence  900  of  FIG. 9 , in accordance with various embodiments. 
     Referring to  FIGS. 9 and 10 , in various embodiments, the Fourier transform (FT) of y n (t), the nth packet  1070  received, can be written 
         Y   n ( f )= X ( f ) H ( f+f   n ) G ( f ) e   −j2πfτ     n     −jθ     n     +Z   n ( f ), | f|≦B   (3)
 
     where X(f) is the FT of the transmitted baseband reference packet x(t)  1010  which is bandlimited to |f|&lt;B Hz (for simplicity it is assumed that the same x(t) is transmitted for all packets), H(f)  1030  is the wideband channel frequency response, G(f)  1060  is the frequency response of the Rx baseband filter (which is assumed to be known to the receiver), f n    920  is the channel center frequency (in Hz) for the nth transmitted packet, θ n =θ Rx,n −θ Tx,n  is the difference between the RF local oscillator (LO) phases of the transmitter and receiver when tuned to frequency f n  (both of which are unknown for most legacy radios, and almost always change in a random way each time either radio is tuned), and Z n (f) is the FT of zero-mean complex additive white Gaussian noise  1050  received while packet n is received after filtering through the receiver&#39;s baseband filter  1060 . The channel spacing between consecutive transmissions is assumed to be f n+1 −f n =(1−α)·2B for n=1, . . . , N−1 where 0&lt;α&lt;1 specifies the amount overlap between consecutive transmissions (α=0 means no overlap, α=1 means 100% overlap). 
     In various embodiments, the FT of Rx packet n+1 can be written 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                               Y 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                              
                             
                               ( 
                               f 
                               ) 
                             
                           
                           = 
                             
                            
                           
                             
                               
                                 X 
                                  
                                 
                                   ( 
                                   f 
                                   ) 
                                 
                               
                                
                               
                                 H 
                                  
                                 
                                   ( 
                                   
                                     f 
                                     + 
                                     
                                       f 
                                       
                                         n 
                                         + 
                                         1 
                                       
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 G 
                                  
                                 
                                   ( 
                                   f 
                                   ) 
                                 
                               
                                
                               
                                  
                                 
                                   
                                     
                                       - 
                                       j2π 
                                     
                                      
                                     
                                         
                                     
                                      
                                     f 
                                      
                                     
                                         
                                     
                                      
                                     
                                       τ 
                                       
                                         n 
                                         + 
                                         1 
                                       
                                     
                                   
                                   - 
                                   
                                     jθ 
                                     
                                       n 
                                       + 
                                       1 
                                     
                                   
                                 
                               
                             
                             + 
                             
                               
                                 Z 
                                 
                                   n 
                                   + 
                                   1 
                                 
                               
                                
                               
                                 ( 
                                 f 
                                 ) 
                               
                             
                           
                         
                         , 
                       
                     
                     
                       
                           
                          
                         
                           
                              
                             f 
                              
                           
                           ≤ 
                           B 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               X 
                                
                               
                                 ( 
                                 f 
                                 ) 
                               
                             
                              
                             
                               H 
                                
                               
                                 ( 
                                 
                                   f 
                                   + 
                                   
                                     f 
                                     n 
                                   
                                   + 
                                   
                                     γ 
                                      
                                     
                                         
                                     
                                      
                                     B 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               G 
                                
                               
                                 ( 
                                 f 
                                 ) 
                               
                             
                              
                             
                                
                               
                                 
                                   
                                     - 
                                     j 
                                   
                                    
                                   
                                       
                                   
                                    
                                   2 
                                    
                                   π 
                                    
                                   
                                       
                                   
                                    
                                   f 
                                    
                                   
                                       
                                   
                                    
                                   
                                     τ 
                                     
                                       n 
                                       + 
                                       1 
                                     
                                   
                                 
                                 - 
                                 
                                   jθ 
                                   
                                     n 
                                     + 
                                     1 
                                   
                                 
                               
                             
                           
                           + 
                           
                             
                               Z 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                              
                             
                               ( 
                               f 
                               ) 
                             
                           
                         
                       
                     
                     
                       
                           
                          
                         
                           
                              
                             f 
                              
                           
                           ≤ 
                           B 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     where γ=2(1−α). 
     In various embodiments, replacing f in (4) with f−γB gives 
     
       
         
           
             
               
                 
                   
                     
                       
                         Y 
                         
                           n 
                           + 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           f 
                           - 
                           
                             γ 
                              
                             
                                 
                             
                              
                             B 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         X 
                          
                         
                           ( 
                           
                             f 
                             - 
                             
                               γ 
                                
                               
                                   
                               
                                
                               B 
                             
                           
                           ) 
                         
                       
                        
                       
                         H 
                          
                         
                           ( 
                           
                             f 
                             + 
                             
                               f 
                               n 
                             
                           
                           ) 
                         
                       
                        
                       
                         G 
                          
                         
                           ( 
                           
                             f 
                             - 
                             
                               γ 
                                
                               
                                   
                               
                                
                               B 
                             
                           
                           ) 
                         
                       
                        
                       
                          
                         
                           
                             
                               - 
                               j 
                             
                              
                             
                                 
                             
                              
                             2 
                              
                             
                               π 
                                
                               
                                 ( 
                                 
                                   f 
                                   - 
                                   
                                     γ 
                                      
                                     
                                         
                                     
                                      
                                     B 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               τ 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                           
                           - 
                           
                             j 
                              
                             
                                 
                             
                              
                             
                               θ 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   , 
                   
                     + 
                     
                       
                         Z 
                         
                           n 
                           + 
                           1 
                         
                       
                        
                       
                         ( 
                         
                           f 
                           - 
                           
                             γ 
                              
                             
                                 
                             
                              
                             B 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         ( 
                         
                           γ 
                           - 
                           1 
                         
                         ) 
                       
                        
                       B 
                     
                     ≤ 
                     f 
                     ≤ 
                     
                       
                         ( 
                         
                           γ 
                           + 
                           1 
                         
                         ) 
                       
                        
                       B 
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     In various embodiments, from equation (3) the following equation (6) can be derived 
     
       
         
           
             
               
                 
                   
                     
                       H 
                        
                       
                         ( 
                         
                           f 
                           + 
                           
                             f 
                             n 
                           
                         
                         ) 
                       
                     
                     ≈ 
                     
                       
                         
                           
                             Y 
                             n 
                           
                            
                           
                             ( 
                             f 
                             ) 
                           
                         
                         
                           
                             X 
                              
                             
                               ( 
                               f 
                               ) 
                             
                           
                            
                           
                             G 
                              
                             
                               ( 
                               f 
                               ) 
                             
                           
                         
                       
                        
                       
                          
                         
                           
                             j2π 
                              
                             
                                 
                             
                              
                             f 
                              
                             
                                 
                             
                              
                             
                               τ 
                               n 
                             
                           
                           - 
                           
                             j 
                              
                             
                                 
                             
                              
                             
                               φ 
                               n 
                             
                           
                         
                       
                     
                   
                   , 
                   
                     
                        
                       f 
                        
                     
                     ≤ 
                     B 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     and from (5) the following equation (7) can be derived 
     
       
         
           
             
               
                 
                   
                     
                       H 
                        
                       
                         ( 
                         
                           f 
                           + 
                           
                             f 
                             n 
                           
                         
                         ) 
                       
                     
                     ≈ 
                     
                       
                         
                           
                             Y 
                             
                               n 
                               + 
                               1 
                             
                           
                            
                           
                             ( 
                             
                               f 
                               - 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 B 
                               
                             
                             ) 
                           
                         
                         
                           
                             X 
                              
                             
                               ( 
                               
                                 f 
                                 - 
                                 
                                   γ 
                                    
                                   
                                       
                                   
                                    
                                   B 
                                 
                               
                               ) 
                             
                           
                            
                           
                             G 
                              
                             
                               ( 
                               
                                 f 
                                 - 
                                 
                                   γ 
                                    
                                   
                                       
                                   
                                    
                                   B 
                                 
                               
                               ) 
                             
                           
                         
                       
                        
                       
                          
                         
                           
                             j2π 
                              
                             
                                 
                             
                              
                             
                               ( 
                               
                                 f 
                                 - 
                                 
                                   γ 
                                    
                                   
                                       
                                   
                                    
                                   B 
                                 
                               
                               ) 
                             
                              
                             
                                 
                             
                              
                             
                               τ 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                           
                           - 
                           
                             j 
                              
                             
                                 
                             
                              
                             
                               φ 
                               
                                 n 
                                 + 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       
                         ( 
                         
                           γ 
                           - 
                           1 
                         
                         ) 
                       
                        
                       B 
                     
                     ≤ 
                     f 
                     ≤ 
                     
                       
                         ( 
                         
                           γ 
                           + 
                           1 
                         
                         ) 
                       
                        
                       
                         B 
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     If the time and phase offsets are known for one of the two overlapping transmissions they can be estimated for the other by selecting the offsets that minimize the mean-square-error between equations (6) and (7) over their region of overlap, i.e., (γ−1)B≦f≦B. A procedure for doing this is described below. Without loss of generality, it is assumed that the time and phase offsets τ n  and φ n  of the nth transmission are known to the receiver, and that T n+1  and φ n+1  are to be estimated.
         1. Estimate the frequency response of the nth narrowband channel using equation (6). This can be done, for example, by taking the FT of the Rx signal y n (t) and dividing it by the product of the FTs of the baseband transmit reference signal x(t) and the baseband filter response g(t). W n (f) can be used to refer to this frequency response estimate and that W n (f)≈H(f+f n )e −j2πfτ     n     +jθ     n   .   2. Multiply the narrowband channel frequency response estimate W n (f) by e j2πfτ     n     −jφ     n   . This adjusts the response to account for the known time and phase offsets τ n  and φ n  of the transmitted baseband reference signal x(t), leaving an estimate of the wideband channel frequency response H(f) for f n −B≦f≦f n +B.   3. Estimate the frequency response of the n+1st narrowband channel using the same procedure as step 1, although in this case replace y n (t) with y n+1 (t). W n+1 (f) can be used to refer to this frequency response estimate and that       

         W   n+1 ( f )≈ H ( f+f   n+1 ) e−j2πfτ     n+1     +jφ     n+1     =H ( f+f   n   +γB ) e   −j2πfτ     n+1     +jφ     n+1   .
          Also note that a second overlapping estimate of the wideband channel frequency response H(f), this time over the interval f n +(γ−1)B≦f≦f n (γ+1)B, can be obtained by multiplying W n+1 (f) by e j2πfτ     n+1     −jφ     n+1   .   4. Using a 2-D search an equivalent means, find the time and phase offset estimates {circumflex over (τ)} n+1  and {circumflex over (φ)} n+1  that minimize the mean-square-error between the two estimates of the wideband frequency response over their region of overlap, i.e.,       

     
       
         
           
             
               
                 
                   
                     
                       τ 
                       ^ 
                     
                     
                       n 
                       + 
                       1 
                     
                   
                   , 
                   
                     
                       
                         φ 
                         ^ 
                       
                       
                         n 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         
                           arg 
                            
                           
                               
                           
                            
                           min 
                         
                         
                           
                             τ 
                             
                               n 
                               + 
                               1 
                             
                           
                           , 
                           
                             φ 
                             
                               n 
                               + 
                               1 
                             
                           
                         
                       
                        
                       
                         
                           ∫ 
                           
                             
                               ( 
                               
                                 γ 
                                 - 
                                 1 
                               
                               ) 
                             
                              
                             B 
                           
                           B 
                         
                          
                         
                           
                             
                                
                               
                                 
                                   
                                     
                                       W 
                                       n 
                                     
                                      
                                     
                                       ( 
                                       f 
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         j2π 
                                          
                                         
                                             
                                         
                                          
                                         f 
                                          
                                         
                                             
                                         
                                          
                                         
                                           τ 
                                           n 
                                         
                                       
                                       - 
                                       
                                         jφ 
                                         n 
                                       
                                     
                                   
                                 
                                 - 
                                 
                                   
                                     
                                       W 
                                       
                                         n 
                                         + 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         f 
                                         - 
                                         
                                           γ 
                                            
                                           
                                               
                                           
                                            
                                           B 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         
                                           j2π 
                                            
                                           
                                             ( 
                                             
                                               f 
                                               - 
                                               
                                                 γ 
                                                  
                                                 
                                                     
                                                 
                                                  
                                                 B 
                                               
                                             
                                             ) 
                                           
                                         
                                          
                                         
                                             
                                         
                                          
                                         
                                           τ 
                                           
                                             n 
                                             + 
                                             1 
                                           
                                         
                                       
                                       - 
                                       
                                         jφ 
                                         
                                           n 
                                           + 
                                           1 
                                         
                                       
                                     
                                   
                                 
                               
                                
                             
                             2 
                           
                            
                           
                               
                           
                            
                           
                             
                                
                               f 
                             
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     Equation (8) can be simplified from a 2-D to a 1-D search as follows: 
     
       
         
           
             
               
                 
                   
                     
                       τ 
                       ^ 
                     
                     
                       n 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       
                         arg 
                          
                         
                             
                         
                          
                         min 
                       
                       
                         τ 
                         
                           n 
                           + 
                           1 
                         
                       
                     
                      
                     
                       
                         ∫ 
                         
                           
                             ( 
                             
                               γ 
                               - 
                               1 
                             
                             ) 
                           
                            
                           B 
                         
                         B 
                       
                        
                       
                         
                           
                              
                             
                               
                                 
                                   
                                     W 
                                     n 
                                   
                                    
                                   
                                     ( 
                                     f 
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     
                                       j2π 
                                        
                                       
                                           
                                       
                                        
                                       f 
                                        
                                       
                                           
                                       
                                        
                                       
                                         
                                           τ 
                                           ^ 
                                         
                                         n 
                                       
                                     
                                     - 
                                     
                                       j 
                                        
                                       
                                         
                                           φ 
                                           ^ 
                                         
                                         n 
                                       
                                     
                                   
                                 
                               
                               - 
                               
                                 
                                   
                                     W 
                                     
                                       n 
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       f 
                                       - 
                                       
                                         γ 
                                          
                                         
                                             
                                         
                                          
                                         B 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     
                                       
                                         j2π 
                                          
                                         
                                           ( 
                                           
                                             f 
                                             - 
                                             
                                               γ 
                                                
                                               
                                                   
                                               
                                                
                                               B 
                                             
                                           
                                           ) 
                                         
                                       
                                        
                                       
                                           
                                       
                                        
                                       
                                         τ 
                                         
                                           n 
                                           + 
                                           1 
                                         
                                       
                                     
                                     - 
                                     
                                       
                                         jφ 
                                         
                                           
                                             n 
                                             + 
                                             1 
                                           
                                           , 
                                           opt 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           τ 
                                           
                                             n 
                                             + 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                              
                           
                           2 
                         
                          
                         
                             
                         
                          
                         
                           
                              
                             f 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         φ 
                         ^ 
                       
                       
                         n 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         φ 
                         
                           
                             n 
                             + 
                             1 
                           
                           , 
                           opt 
                         
                       
                        
                       
                         ( 
                         
                           
                             τ 
                             ^ 
                           
                           
                             n 
                             + 
                             1 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     where for each candidate τ n+1  the optimal estimate for φ n+1  can be shown to be 
     
       
         
           
             
               
                 
                   
                     
                       φ 
                       
                         
                           n 
                           + 
                           1 
                         
                         , 
                         opt 
                       
                     
                      
                     
                       ( 
                       
                         τ 
                         
                           n 
                           + 
                           1 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       - 
                       arg 
                     
                      
                     
                       
                         ∫ 
                         
                           
                             ( 
                             
                               γ 
                               - 
                               1 
                             
                             ) 
                           
                            
                           B 
                         
                         B 
                       
                        
                       
                         
                           
                             W 
                             
                               n 
                               + 
                               1 
                             
                           
                            
                           
                             ( 
                             
                               f 
                               - 
                               
                                 γ 
                                  
                                 
                                     
                                 
                                  
                                 B 
                               
                             
                             ) 
                           
                         
                         * 
                         
                           
                              
                             
                               
                                 - 
                                 j2π 
                               
                                
                               
                                   
                               
                                
                               
                                 ( 
                                 
                                   f 
                                    
                                   
                                       
                                   
                                   - 
                                   
                                     γ 
                                      
                                     
                                         
                                     
                                      
                                     B 
                                   
                                 
                                 ) 
                               
                                
                               
                                 τ 
                                 
                                   n 
                                   + 
                                   1 
                                 
                               
                             
                           
                           · 
                           
                             
                               W 
                               n 
                             
                              
                             
                               ( 
                               f 
                               ) 
                             
                           
                         
                          
                         
                            
                           
                             
                               j2π 
                                
                               
                                   
                               
                                
                               f 
                                
                               
                                   
                               
                                
                               
                                 
                                   τ 
                                   ^ 
                                 
                                 n 
                               
                             
                             - 
                             
                               j 
                                
                               
                                 
                                   φ 
                                   ^ 
                                 
                                 n 
                               
                             
                           
                         
                          
                         
                             
                         
                          
                         
                           
                              
                             f 
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     In words, if the time and phase offsets are known for the nth transmission, they can be estimated at the receiver for the n+1 st  (or for that matter any other spectrally overlapping transmission) by (1) estimating the frequency responses of the narrowband channels occupied by the two transmissions, (2) for the channel having the known time and phase offsets, removing those offsets from that channel&#39;s narrowband frequency response estimate, yielding an estimate of a portion of the wideband channel frequency response, (3) removing candidate time and phase offsets from the partially overlapping channel&#39;s narrowband frequency response estimate, yielding an estimate of a portion of the wideband channel frequency response that partially overlaps with the other estimate, and (4) finding the candidate offsets that minimize the mean-square error between the two wideband channel frequency response estimates over the spectrally overlapping portion of these estimates. 
     It should be noted that other cost-functions can be used to find the best candidate offsets, such as maximum error magnitude over the overlapping interval, mean error magnitude over that same interval, weighted mean-square-error, etc. 
     The above procedure can be applied iteratively to estimate the time and phase offsets for an entire sequence of spectrally overlapping LTF-WB transmissions. In various embodiments, the iterative procedure is given below.
         1. Compute FTs Y n (f) for all N time-domain Rx signals y n (t). Let {circumflex over (τ)} 1 ={circumflex over (θ)} 1 =0 be the time and phase offset estimates for the first packet in the sequence.   2. Set n=1.   3. Estimate the narrowband channel frequency response W 1 (f) of the 1 st  channel, e.g., by dividing Y 1 (f) by X(f)G(f).   4. Estimate the narrowband channel frequency response W n+1 (f) of the n+1st channel, e.g., by dividing Y n+1 (f) by X(f)G(f).   5. Use equation (8) or (9-11) to find the time and phase offset estimates {circumflex over (τ)} n+1 , {circumflex over (φ)} n+1  that minimize the mean-square error between the offset-corrected overlapping spectral estimates W n (f) and W n+1 (f).   6. Increment n and repeat steps 4-5 until all N time and phase offsets have been estimated.       

     Once the time and phase offset estimates {circumflex over (τ)} n ,{circumflex over (φ)} n , n=1, . . . , N have been computed, an estimate for the broadband channel frequency response H (f) over the range of frequencies f 1 −B≦f≦f N +B spanned by the N transmissions can be found by dividing each of the narrowband frequency responses W n (f) computed in step 4 above by e −j2πf{circumflex over (τ)}     n     +j{circumflex over (φ)}     n    (yielding estimates for H(f) over the segment f n −B≦f≦f n +B), and concatenating the results together to form the desired broadband estimate. 
     It should be noted that the above procedure is subject to error propagation. One can mitigate these effects by starting at the middle of the sequence (i.e., at n=N/2) instead of at the beginning and working outwards to the beginning and end of the sequence, or by using trellis-based sequence estimation instead of instantaneous estimates. 
     Also, step 5 in the procedure treats the time and carrier phase offsets as continuous random variables when in reality, this is usually not the case. The time offsets are usually integer multiples of the transmitter&#39;s digital-to-analog converter (DAC) sampling period (e.g., usually 12.5 ns for 40 MHz wide 802.11n packets) and the phase offsets are often integer multiples of some fixed phase angle (e.g., 90 degrees). When the time and phase offsets are known to be discrete RVs, one can exploit this fact to improve the performance of the estimators. In this case, the argmin function in (8) would be implemented as a search over the discrete set of known time and phase offset candidates. One could also quantize the phase offset estimates from (9) to their nearest known discrete values. 
     In some situations it may be advantageous to estimate the transmit phase offsets θ Tx,n  and receiver phase offsets θ Rx,n  separately rather than estimating their difference.  FIG. 11  illustrates an exemplary approach  1100  for staggering Tx and Rx phase changes, in accordance with various embodiments. The idea is for the transmitter to transmit each packet twice at each frequency. The receiver tunes its radio frequency after packets  1110 ,  1130 ,  1150 , . . . ,  1180  and the transmitter tunes after packets  1120 ,  1140 , . . . ,  1170 . This allows the receiver to measure its phase changes after receiving packets  1120 ,  1140 , . . . ,  1170  and the transmitter phase changes after receiving packets  1110 ,  1130 ,  1150 , . . . ,  1180 . 
     The exact order of frequencies visited by the transmitter isn&#39;t important as long as all the frequencies are covered.  FIG. 12  is an exemplary diagram  1200  illustrating exemplary sequences having monotonically increasing (top graph  1210 ) vs. non-monotonically increasing (bottom graph  1220 ) packet transmit center frequencies, in accordance with various embodiments. The top graph  1210  in the figure shows the packets being transmitted with monotonically increasing center frequencies over time—just like the exemplary sequence  900  in  FIG. 9 . The bottom graph  1220  shows a reordering of these same center frequencies. 
     If the frequency ordering was done per the top graph  1210 , the receiver would use the procedure described above in steps 1-7 to first estimate (τ 2 ,θ 2 ) from Y 1 (f), Y 2 (f) and (τ 1 ,θ 1 ) [assumed to be (0,0)]; then estimate (τ 3 ,θ 3 ) from Y 2 (f),Y 3  (f) and the estimate for (τ 2 ,θ 2 ), and so on, until (τ e ,θ 5 ) from Y 4 (f), Y 5 (f) and the estimate for (τ 4 ,θ 4 ). 
     If the frequency ordering was done per the bottom graph  1220 , the receiver would first estimate (τ e ,θ 5 ) from Y 3 (f), Y 5 (f) and an initial estimate (θ 3 ,θ 3 ) [assumed to be (0,0)]; then estimate (τ 1 ,θ 1 ) from Y 1 (f),Y 5 (f) and the estimate for (τ 5 ,θ 5 ); then estimate (τ 4 ,θ 4 ) from Y 1 (f),Y 4 (f) and the estimate for (τ 1 ,θ 1 ); then estimate (τ 2 ,θ 2 ) from Y 2 (f),Y 4 (f) and the estimate for (τ 4 ,θ 4 ); and finally estimate (τ 2 ,θ 2 ) from Y 2 (f),Y 4 (f) and the estimate for (τ 4 ,θ 4 ). 
     In general, for a monotonically increasing set of transmit center frequencies f 1 &lt;f 2  . . . &lt;f N , the idea is to first estimate the offsets for the packet transmitted at frequency f 2  in terms of the (partially overlapping) observation data and estimates from frequency f 1 , then to estimate the offsets for the packet transmitted at frequency f 3  in terms of the (partially overlapping) observation data and estimates from frequency f 2 , and so on. 
     It&#39;s also possible to take the same idea and apply it to virtually any ordering of the frequencies, not just f 1 , f 2 , . . . , f N  with f 1 &lt;f 2  . . . &lt;f N . As long as the transmissions span a contiguous block of spectrum and are spectrally overlapping, all of the required information is available to solve the problem yielding the same performance as if they were ordered monotonically. If a sequence is transmitted with a non-monotonic ordering, the packets in the received sequence can be re-ordered to appear to the receiver as if they were transmitted using the monotonic ordering, and then the time and phase offsets can be computed using the techniques described herein. 
     While the present teachings are described in conjunction with various embodiments, it is not intended that the present teachings be limited to such embodiments. On the contrary, the present teachings encompass various alternatives, modifications, and equivalents, as will be appreciated by those of skill in the art. 
     Further, in describing various embodiments, the specification may have presented a method and/or process as a particular sequence of steps. However, to the extent that the method or process does not rely on the particular order of steps set forth herein, the method or process should not be limited to the particular sequence of steps described. As one of ordinary skill in the art would appreciate, other sequences of steps may be possible. Therefore, the particular order of the steps set forth in the specification should not be construed as limitations on the claims. In addition, the claims directed to the method and/or process should not be limited to the performance of their steps in the order written, and one skilled in the art can readily appreciate that the sequences may be varied and still remain within the spirit and scope of the various embodiments.