Indian Patents. 268652:A SYSTEM FOR THE TIME OF ARRIVAL (TOA) ESTIMATION IN WIRELESS COMMUNICATION SYSTEMS

Title of Invention	A SYSTEM FOR THE TIME OF ARRIVAL (TOA) ESTIMATION IN WIRELESS COMMUNICATION SYSTEMS
Abstract	A apparatus for determining the position of a moving person of terminal in a predetermined area by estimating the time of arrival of a signal by estimating the coarse timing and fine timing.

Full Text	FORM - 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 PROVISIONAL SPECIFICATION (See section 10 and rule 13) A SYSTEM FOR THE TIME OF ARRIVAL (TOA) ESTIMATION IN WIRELESS COMMUNICATION SYSTEMS TATA CONSULTANCY SERVICES LIMITED an Indian Company of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 001, Maharashtra, India, THE FOLLOWING SPEC IFICATION DESCRIBES THE INVENTION. This invention relates to a system for the Time of Arrival (TOA) estimation in wireless communication systems. Typically, the system in accordance with this invention is tailored for IEEE 802.11a OFDM systems, but it can be used in various communication systems where there is a known sequence (such as training or preamble sequence) in the transmit frame. Systems, which allow one to automatically locate people or objects (positioning), or to check the relative proximal location of another person or object are well known. One limitation of the prior art systems are they are only relevant to a confined local area and thus capable of local positioning. Typically, these systems deploy local positioning systems-like optical, ultrasound, radio frequency (RF). In recent times, wireless network systems (with their ability to support mobility) are widely deployed to provide different services. This invention envisages the use for the Time of Arrival (TOA) estimation in wireless network systems for accurate positioning of an object or person. 2 Particularly, this invention envisages a method and apparatus for estimation using short and long training sequences and a includes a system for reducing distortion in time of arrival estimation. The apparatus envisaged in accordance with this invention works on a novel setup which is suitable for any communication system. Indoor positioning requires high accuracy positioning (better than one meter) in harsh multipath environments and there is also a requirement for tracking fast-moving objects or people. Solutions based on Global Positioning System (GPS) or terrestrial cellular systems do not provide the required accuracy. In the prior art, different techniques are used for time of arrival estimation. These include simple correlation based techniques, their enhancements to sophisticated maximum-likelihood (ML) based techniques. Further, there are techniques tailored to specific systems like OFDM, Ultra Wideband (UWB). The performance of time estimator (usually the root mean square (rms) error) depends on various factors like signal-to-noise ratio (SNR) at the receiver, effective bandwidth (BW), the knowledge about the transmission channel, over sampling used, etc. In indoor scenarios, multipath and non line-of-sight (NLOS) conditions pose real challenge in the time estimation. This is particularly prevalent in narrow band systems, where it is brought out that accuracy well inside the coverage area is dominated by multipath. Further, the fundamental limit on the rms error depends on the sharpness of the transmitted signal autocorrelation function (around the turning point); in 3 mathematical terms the rms error for the autocorrelation function &) depends on^"(°). Thus, signals with good autocorrelation properties are desirable as demonstrated by the popularity of direct-sequence spread spectrum (DSSS) and UWB signals in localization. This invention teaches the possibility of arriving at localization systems in Wireless Local Area Networks (WLANs), typically in IEEE 802.1 la OFDM type systems. The systems can be based on received signal strength indication (RSSI), fingerprinting or/and time measurements. Although further discussion in this specification is restricted to this particular type of WLANs, the invention extends to all other LANS working on other known and yet to created systems. It has been recognized that the location awareness is a cornerstone for future wireless network systems. This will also provide context awareness for Ubiquitous Computing. Thus, RF based indoor location built on the existing wireless infrastructures can provide cost-effective implementations. It is well known that the time measurements between the unknown position (of a mobile terminal (MT) such as a mobile hand set ) and the fixed positions (access points (APs) or base stations (BSs) are converted to distance measurements and these are usqd in the process of multilateration to evaluate the position coordinates. In TOA envisaged in accordance with this invention, the estimation of the time of arrival is initialized by getting to know the transmitting time of the signal from the Mobile Terminal (for 4 instance through time stamping) and synchronization of the clocks of MT and the BSs. In accordance with an alternative embodiment of the invention, the start time measurement can be omitted by introducing an additional BS at a known position and measuring the TDOA at the receivers of a signal transmitted by the MT. In TDOA one still needs synchronization between the receivers, which can be further eliminated by using a differential time difference of arrival (DTDOA). In designing a time-based localization system, it is necessary to consider three main issues : (1) Base-station geometry and synchronization issues (2) Time of arrival estimation (3) and a system for multilateration. Once the base-station geometry and synchronization issues are decided upon, the time of arrival estimation is done very accurately, as even one nanosecond error translates into a distance error of 30 cm. The apparatus in accordance with this invention is shown in Figure 1 of the accompanying drawings. Figure 1 is a generic TOA estimation based localization setup which can be used for various communication systems where there is training or preamble information in the frame. The proposed distorted template algorithm working on the apparatus is also novel. 5 In IEEE 802.1 la, the OFDM transmission is based on 64 subcarriers, out of which 12 carriers form the guard band; the remaining 52 subcarriers include 4 pilot subcarriers. The 64 samples of the IFFT output comprise one OFDM symbol; the last 16 samples are copied and added to form the cyclic prefix at the beginning of each OFDM symbol. The training sequence is transmitted at the beginning of each frame to help the receiver accomplish synchronization and channel estimation. It consists of ten short training symbols (STS), each of which is 0.8 mS, followed by two long training symbols (LTS), each of which is 3.2 mS, plus a 1.6/^ prefix which precedes the long training symbol. The STSs are responsible for signal and packet detection, Automatic Gain Control (AGC) level setting, coarse timing synchronization and coarse carrier frequency offset correction. In the method according to this invention the TOA is carried out in two stages : [1] an initial estimate of TOA (coarse timing synchronization) is carried out using the short training symbols [STS]. Typically, coarse timing synchronization can involve at least one of cross correlation and autocorrelation-based techniques . In cross correlation, the correlation is carried out using the "template" of the STSs stored in the receiver and picking the peak of the correlation. In auto-correlation, the repeated STSs are utilized. The initial time estimation obtained in the first stage is utilized in the next (second) stage. [2] a final refined time estimate using initial time estimated and long training symbols [LTS] . The advantage with LTSs is that frequency offset can be taken care of by correcting it through the estimated value of offset. 6 Typically, frequency offsets of more than 50 kHz produces no useful results with cross-correlation. Further advantage with LTSs is that the channel estimation available during that period can be utilized for getting an estimate of the distorted version of the LTSs and utilizing this may lead to better correlation. Therefore, In the second stage LTSs and FFT-based interpolation are used for evaluating the requisite correlation. The initial estimate of time from Stage 1 is used to evaluate IFFTs only in the required range and then peak is picked among these downselected values to arrive at the final time estimation. The object of this invention is to provide and implement an improved local positioning system. The invention will now be described with respect to the accompanying drawings, in which Figure 1 shows a block diagram of the apparatus of this invention showing the implemented system in accordance with this invention ; Figure 2 shows a comparison of the performance of the system in accordance with this invention with a traditional correlation based system Figure 3 shows the cumulative distribution function (CDF) and histogram of the comparison of figure 2; Figure 4 shows an additional histogram of the comparison; Figures 5 and 6 show more rigorous simulations and results of the working of the invention in an indoor channel scenario. 7 Figure 1 is a generic TOA estimation based localization setup which can be used for various communication systems where there is training or preamble information in the frame. The proposed distorted template algorithm working on the apparatus is also novel. The block diagram of one embodiment of the the implemented system in accordance with this invention, is shown in Figure 1 of the accompanying drawings . This implementation is merely exemplary and in no way restricts the ambit and the scope of this invention. The received signal is passed to the initial TOA estimator block. After initial coarse timing synchronization using STS, the received signal is correlated with LTS stored in the receiver to obtain an initial estimate of the time of arrival. The LTS is also used to obtain the channel frequency response, from which the channel impulse response is evaluated using an IFFT. The resulting signal has 64 points of which only a few are significant; the latter depends on the sampling frequency at the receiver and is usually much less than 64. A few paths around the maximum sample [ for example, one can consider totally 5 values, including the maximum) are retained while the rest are discarded. Since the start of the channel impulse response (CIR), cannot be estimated different candidate impulse responses of the same length are hypothetised, each of them include the maximum estimated path. These candidates (corresponding to different hypothesis) are convolved with the clean template to obtain a corresponding distorted template. This distorted template is then correlated with the received signal. The template that results in the largest correlation peak is assumed to be the true hypothesis. The position of the maximum path in the chosen hypothesis is used as an indication of the offset between the initial time of arrival estimate and the true estimate. This offset is subtracted from the initial time of arrival estimation to obtain the refined estimate. 8 It is found that time of estimate are good (1st path) for more than 50% of the time. However for the remaining time the values are quite spread. The distribution is quite similar to the Gaussian distribution. So by averaging the resulting values are found to be close to zero 90% of the time. This case is highly reflected in the distorted template. From the simulation results provided it can be observed that the mean for the distorted template is close to zero. In the simulations in accordance with this invention , an 802.1 la packet is transmitted which consists of the STS, LTS and the signal field. The data portion is not transmitted as it does not affect the TOA estimation performance. The multipath channel is modeled using the Jake's model and the 802.1 la indoor channel delay profile is used. At the receiver, the signal can be sampled at various sampling rates. Also, the transmitted signal can be oversampled. As mentioned earlier, the length of the channel impulse response depends on the sampling frequency at the receiver. At the base sampling rate of 20 MHz for the indoor channel there are up to 8 paths. However, the first few paths contain most of the energy. Three candidate impulse responses are used, each with three paths (selected out of 5) while constructing the distorted template. It should be noted that since the initial timing estimate is not accurate the estimated channel impulse response could be cyclically shifted. Using only three taps for the channel impulse response reduces the complexity in the final implementation of the system; the ultimate goal of our research is to design and implement an improved local positioning system. 9 A comparison of the performance of the system in accordance with this invention with a traditional correlation based system shows the cumulative distribution function (CDF) and histogram shown in Figure 2 and Figure 3 respectively of the accompanying drawings . These two figures correspond to 20 MHz sampling in the receiver and a signal-to-noise ratio (SNR) of 10 dB. The figures are based on simulations. It is to be noted that the timing error due to sampling is not considered in these results. The proposed scheme identifies the first path close to 75% of the time whereas it is only 50% with the traditional correlation-based method. Similar performance is also observed for different SNRs like 15 dB and 20 dB, bringing out the much better performance of the proposed system compared to the simple correlation based system. More rigorous simulations and results are provided in figure 5 of the accompanying drawings below. The sub sampling offset has been carried out by over sampling by 100 times in the transmitter side. The dominant line of sight is five times the actual. The time of arrival estimates are used to obtain the position estimation using multilateration. The position estimation results shown are for five base stations, four of them stationed at four corners of the considered area and one and at the centre. The mobile position was chosen to be randomly distributed. The results here show position error by using multiple (1,5 and 10) time of arrival measurements. While considerable emphasis has been placed herein on the various components of the preferred embodiment, it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the 10 invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation. DatedJhis 13th day of December 2006. IOHAN DEWAN /OF R.K.DEWAN & COMPANY 'APPLICANTS' PATENT ATTORNEY 11

Full Text

FORM - 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
SPECIFICATION
(See section 10 and rule 13)
A SYSTEM FOR THE TIME OF ARRIVAL (TOA) ESTIMATION IN WIRELESS COMMUNICATION SYSTEMS
TATA CONSULTANCY SERVICES LIMITED
an Indian Company of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 001,
Maharashtra, India,
THE FOLLOWING SPEC IFICATION DESCRIBES THE INVENTION.

This invention relates to a system for the Time of Arrival (TOA) estimation in wireless communication systems.
Typically, the system in accordance with this invention is tailored for IEEE 802.11a OFDM systems, but it can be used in various communication systems where there is a known sequence (such as training or preamble sequence) in the transmit frame.
Systems, which allow one to automatically locate people or objects (positioning), or to check the relative proximal location of another person or object are well known.
One limitation of the prior art systems are they are only relevant to a confined local area and thus capable of local positioning. Typically, these systems deploy local positioning systems-like optical, ultrasound, radio frequency (RF).
In recent times, wireless network systems (with their ability to support mobility) are widely deployed to provide different services.
This invention envisages the use for the Time of Arrival (TOA) estimation in wireless network systems for accurate positioning of an object or person.
2

Particularly, this invention envisages a method and apparatus for estimation using short and long training sequences and a includes a system for reducing distortion in time of arrival estimation.
The apparatus envisaged in accordance with this invention works on a novel setup which is suitable for any communication system.
Indoor positioning requires high accuracy positioning (better than one meter) in harsh multipath environments and there is also a requirement for tracking fast-moving objects or people. Solutions based on Global Positioning System (GPS) or terrestrial cellular systems do not provide the required accuracy.
In the prior art, different techniques are used for time of arrival estimation. These include simple correlation based techniques, their enhancements to sophisticated maximum-likelihood (ML) based techniques. Further, there are techniques tailored to specific systems like OFDM, Ultra Wideband (UWB). The performance of time estimator (usually the root mean square (rms) error) depends on various factors like signal-to-noise ratio (SNR) at the receiver, effective bandwidth (BW), the knowledge about the transmission channel, over sampling used, etc. In indoor scenarios, multipath and non line-of-sight (NLOS) conditions pose real challenge in the time estimation. This is particularly prevalent in narrow band systems, where it is brought out that accuracy well inside the coverage area is dominated by multipath. Further, the fundamental limit on the rms error depends on the sharpness of the transmitted signal autocorrelation function (around the turning point); in
3

mathematical terms the rms error for the autocorrelation function &) depends on^"(°). Thus, signals with good autocorrelation properties are desirable as demonstrated by the popularity of direct-sequence spread spectrum (DSSS) and UWB signals in localization.
This invention teaches the possibility of arriving at localization systems in Wireless Local Area Networks (WLANs), typically in IEEE 802.1 la OFDM type systems. The systems can be based on received signal strength indication (RSSI), fingerprinting or/and time measurements. Although further discussion in this specification is restricted to this particular type of WLANs, the invention extends to all other LANS working on other known and yet to created systems.
It has been recognized that the location awareness is a cornerstone for future wireless network systems. This will also provide context awareness for Ubiquitous Computing. Thus, RF based indoor location built on the existing wireless infrastructures can provide cost-effective implementations.
It is well known that the time measurements between the unknown position (of a mobile terminal (MT) such as a mobile hand set ) and the fixed positions (access points (APs) or base stations (BSs) are converted to distance measurements and these are usqd in the process of multilateration to evaluate the position coordinates. In TOA envisaged in accordance with this invention, the estimation of the time of arrival is initialized by getting to know the transmitting time of the signal from the Mobile Terminal (for
4

instance through time stamping) and synchronization of the clocks of MT and the BSs.
In accordance with an alternative embodiment of the invention, the start time measurement can be omitted by introducing an additional BS at a known position and measuring the TDOA at the receivers of a signal transmitted by the MT. In TDOA one still needs synchronization between the receivers, which can be further eliminated by using a differential time difference of arrival (DTDOA).
In designing a time-based localization system, it is necessary to consider three main issues : (1) Base-station geometry and synchronization issues (2) Time of arrival estimation (3) and a system for multilateration.
Once the base-station geometry and synchronization issues are decided upon, the time of arrival estimation is done very accurately, as even one nanosecond error translates into a distance error of 30 cm.
The apparatus in accordance with this invention is shown in Figure 1 of the accompanying drawings.
Figure 1 is a generic TOA estimation based localization setup which can be used for various communication systems where there is training or preamble information in the frame. The proposed distorted template algorithm working on the apparatus is also novel.
5

In IEEE 802.1 la, the OFDM transmission is based on 64 subcarriers, out of which 12 carriers form the guard band; the remaining 52 subcarriers include 4 pilot subcarriers. The 64 samples of the IFFT output comprise one OFDM symbol; the last 16 samples are copied and added to form the cyclic prefix at the beginning of each OFDM symbol. The training sequence is transmitted at the beginning of each frame to help the receiver accomplish synchronization and channel estimation. It consists of ten short training symbols (STS), each of which is 0.8 mS, followed by two long training symbols (LTS), each of which is 3.2 mS, plus a 1.6/^ prefix which precedes the long training symbol. The STSs are responsible for signal and packet detection, Automatic Gain Control (AGC) level setting, coarse timing synchronization and coarse carrier frequency offset correction.
In the method according to this invention the TOA is carried out in two stages :
[1] an initial estimate of TOA (coarse timing synchronization) is carried out using the short training symbols [STS]. Typically, coarse timing synchronization can involve at least one of cross correlation and autocorrelation-based techniques . In cross correlation, the correlation is carried out using the "template" of the STSs stored in the receiver and picking the peak of the correlation. In auto-correlation, the repeated STSs are utilized. The initial time estimation obtained in the first stage is utilized in the next (second) stage.
[2] a final refined time estimate using initial time estimated and long training symbols [LTS] . The advantage with LTSs is that frequency offset can be taken care of by correcting it through the estimated value of offset.
6

Typically, frequency offsets of more than 50 kHz produces no useful results with cross-correlation. Further advantage with LTSs is that the channel estimation available during that period can be utilized for getting an estimate of the distorted version of the LTSs and utilizing this may lead to better correlation. Therefore, In the second stage LTSs and FFT-based interpolation are used for evaluating the requisite correlation. The initial estimate of time from Stage 1 is used to evaluate IFFTs only in the required range and then peak is picked among these downselected values to arrive at the final time estimation.
The object of this invention is to provide and implement an improved local positioning system.
The invention will now be described with respect to the accompanying drawings, in which
Figure 1 shows a block diagram of the apparatus of this invention showing the implemented system in accordance with this invention ;
Figure 2 shows a comparison of the performance of the system in accordance with this invention with a traditional correlation based system
Figure 3 shows the cumulative distribution function (CDF) and histogram of the comparison of figure 2;
Figure 4 shows an additional histogram of the comparison;
Figures 5 and 6 show more rigorous simulations and results of the working of the invention in an indoor channel scenario.
7

Figure 1 is a generic TOA estimation based localization setup which can be used for various communication systems where there is training or preamble information in the frame. The proposed distorted template algorithm working on the apparatus is also novel. The block diagram of one embodiment of the the implemented system in accordance with this invention, is shown in Figure 1 of the accompanying drawings . This implementation is merely exemplary and in no way restricts the ambit and the scope of this invention. The received signal is passed to the initial TOA estimator block. After initial coarse timing synchronization using STS, the received signal is correlated with LTS stored in the receiver to obtain an initial estimate of the time of arrival. The LTS is also used to obtain the channel frequency response, from which the channel impulse response is evaluated using an IFFT. The resulting signal has 64 points of which only a few are significant; the latter depends on the sampling frequency at the receiver and is usually much less than 64. A few paths around the maximum sample [ for example, one can consider totally 5 values, including the maximum) are retained while the rest are discarded. Since the start of the channel impulse response (CIR), cannot be estimated different candidate impulse responses of the same length are hypothetised, each of them include the maximum estimated path. These candidates (corresponding to different hypothesis) are convolved with the clean template to obtain a corresponding distorted template. This distorted template is then correlated with the received signal. The template that results in the largest correlation peak is assumed to be the true hypothesis. The position of the maximum path in the chosen hypothesis is used as an indication of the offset between the initial time of arrival estimate and the true estimate. This offset is subtracted from the initial time of arrival estimation to obtain the refined estimate.
8

It is found that time of estimate are good (1st path) for more than 50% of the time. However for the remaining time the values are quite spread. The distribution is quite similar to the Gaussian distribution. So by averaging the resulting values are found to be close to zero 90% of the time. This case is highly reflected in the distorted template. From the simulation results provided it can be observed that the mean for the distorted template is close to zero.
In the simulations in accordance with this invention , an 802.1 la packet is transmitted which consists of the STS, LTS and the signal field. The data portion is not transmitted as it does not affect the TOA estimation performance. The multipath channel is modeled using the Jake's model and the 802.1 la indoor channel delay profile is used. At the receiver, the signal can be sampled at various sampling rates. Also, the transmitted signal can be oversampled. As mentioned earlier, the length of the channel impulse response depends on the sampling frequency at the receiver. At the base sampling rate of 20 MHz for the indoor channel there are up to 8 paths. However, the first few paths contain most of the energy. Three candidate impulse responses are used, each with three paths (selected out of 5) while constructing the distorted template. It should be noted that since the initial timing estimate is not accurate the estimated channel impulse response could be cyclically shifted. Using only three taps for the channel impulse response reduces the complexity in the final implementation of the system; the ultimate goal of our research is to design and implement an improved local positioning system.
9

A comparison of the performance of the system in accordance with this invention with a traditional correlation based system shows the cumulative distribution function (CDF) and histogram shown in Figure 2 and Figure 3 respectively of the accompanying drawings . These two figures correspond to 20 MHz sampling in the receiver and a signal-to-noise ratio (SNR) of 10 dB. The figures are based on simulations. It is to be noted that the timing error due to sampling is not considered in these results. The proposed scheme identifies the first path close to 75% of the time whereas it is only 50% with the traditional correlation-based method. Similar performance is also observed for different SNRs like 15 dB and 20 dB, bringing out the much better performance of the proposed system compared to the simple correlation based system.
More rigorous simulations and results are provided in figure 5 of the accompanying drawings below. The sub sampling offset has been carried out by over sampling by 100 times in the transmitter side. The dominant line of sight is five times the actual. The time of arrival estimates are used to obtain the position estimation using multilateration. The position estimation results shown are for five base stations, four of them stationed at four corners of the considered area and one and at the centre. The mobile position was chosen to be randomly distributed. The results here show position error by using multiple (1,5 and 10) time of arrival measurements.
While considerable emphasis has been placed herein on the various components of the preferred embodiment, it will be appreciated that many alterations can be made and that many modifications can be made in the preferred embodiment without departing from the principles of the
10

invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.
DatedJhis 13th day of December 2006.
IOHAN DEWAN /OF R.K.DEWAN & COMPANY 'APPLICANTS' PATENT ATTORNEY
11

Documents:

http://ipindiaonline.gov.in/patentsearch/GrantedSearch/viewdoc.aspx?id=qiwWaVODpzklHGjvc5LmnA==&loc=vsnutRQWHdTHa1EUofPtPQ==

« Previous Patent

Next Patent »

Patent Number

268652

Indian Patent Application Number

2044/MUM/2006

PG Journal Number

37/2015

Publication Date

11-Sep-2015

Grant Date

10-Sep-2015

Date of Filing

13-Dec-2006

Name of Patentee

TATA CONSULTANCY SERVICES LIMITED

Applicant Address

BOMBAY HOUSE, 24, HOMI MODY STREET, MUMBA-400001,

Inventors:

#	Inventor's Name	Inventor's Address
1	HARISH REDDY	BOMBAY HOUSE, 24, HOMI MODY STREET, MUMBA-400 001,
2	GIRISH CHANDRA MARISWAMY	BOMBAY HOUSE, 24, HOMI MODY STREET, MUMBA-400 001,
3	HARIHARA SUBRAMANIAM GOPALAKRISHNAN	BOMBAY HOUSE, 24, HOMI MODY STREET, MUMBA-400 001,
4	BALAMURALIDHAR PURUSHOTHAMAN	BOMBAY HOUSE, 24, HOMI MODY STREET, MUMBA-400 001,

PCT International Classification Number

H04L27/28

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA