# Acoustic TDOA Measurement and Accurate Indoor Positioning for Smartphone
## 3 Robust TDOA Measurement Method
### Robust TDOA Measurement
The cross-correlation calculation formula is as follows:  
\[R_{i}(t)=\text{abs}\Big{(}F^{-1}[F[s_{d}(t)]F^{*}[y(t)]]\Big{)} \tag{3}\]  
where \(R_{i}(t)\) is the absolute value of cross correlation result, \(s_{d}(t)\) is a prior template signal, \(y(t)\) is the received signal, \(F\) and \(F^{-1}\) are Fourier transform and its inverse transform, respectively, and \(F^{*}\) is the complex conjugate of \(F\). After the signal is decoded, the signal can be extracted. Rough extraction of the signal is as follows (Algorithm 1):  
```
Input: Filtered signal. Output: Rough extraction of signal. 1: Cross-correlation between filtered signal and different prior signals
2: Based on the step 1, different cross-correlation maximum values are obtained
3: TR is the maximum value among all maximum values in step 2. 4: Decoding decision if TR corresponds to the signal that needs to be roughly extracted (1) Find the time \(t_{max}^{p}\) corresponding to TR. (2) Rough extraction of signal in the time period (\(t_{max}^{q}-40\) ms, \(t_{max}^{q}+40\) ms). else (1) Find the time \(t_{max}^{p}\) corresponding to TR. (2) Assigning acoustic data to 0 in the time period (\(t_{max}^{q}-40\) ms, \(t_{max}^{q}+40\) ms). (3) return to step 1. end if
5: Return: Rough extraction of signal. ```  
**Algorithm 1** Rough extraction of signal  
In the third step, we use the signal extracted in the second step to perform cross-correlation operations with the prior signal. We obtain the correlation function \(R_{i}(t)\) through cross-correlation operation. We develop the stable first path extraction method base on \(R_{i}(t)\). The information of the first path can be converted into TOA information. The first path extraction algorithm is as follows (Algorithm 2):  
```
Input:\(R_{i}\). Output: TOA. 1: Set threshold \(q\) (\(q\in[0.3:8:1]\), \(\delta\) is the step size)
2: Set \(\delta=0.01\). 3:\(\rho=max(R_{i})\). 4: Find \(index_{i}(n)=argmin(R_{i}\geq q(n)*\rho)\), \(n=1,2\ldots 71\). 5: Group decision: (1) Set variable GD = 1, GD represents the number of the group. (2) for\(n=1\):70 \(\text{interval}(n)=index_{i}(n+1)-index_{i}(n)\); endfor for\(n=1\):69 if\(\text{interval}(n)<0.5\) ms \(index_{i}(n)\) Belongs to group GD; else GD = GD + 1; \(index_{i}(n+1)\) Belongs to group GD; endif endfor (3) Find the proportion of \(index_{i}\) in each group, the proportion is \(\sigma_{i}(n)\), \(n=1\),\(2\ldots\) GD. (4) Find \(\text{VB}=argmin(\sigma_{i}(n)\geq 10\%)\), \(n=1\),\(2\ldots\) GD. ```  
**Algorithm 2** First path extraction When we obtain four TOAs, we can obtain three TDOAs by Formula (2). Since there are a few abnormal values in the TOA detection process, then TDOA measurement can also be affected. TDOA measurement is the precondition of smartphone positioning, so robust TDOA measurement is very necessary. We have carried out optimization processing to overcome TDOA abnormal measurement. The algorithm is as follows (Algorithm 3):  
```
Input: TOA1 TOA2 TOA3 TOA4. Output: TDOA1 TDOA2 TDOA3. 1: TDOA calculation for\(j=1\):3 \(TDOA_{j}=TOA_{1}-TOA_{j+1}-j*200\) ms. endfor
2: Set \(\epsilon\). (\(\epsilon\) is the upper limit of abnormality, \(\epsilon\) is set to 40 ms.)
3: Exception elimination for\(j=1\):3 if\(abs(TDOA_{j}(1))>\epsilon\) \(TDOA_{j}(1)=min(abs(TDOA_{1}(1))\ abs(TDOA_{2}(1))\ abs(TDOA_{3}(1)))\). endif for\(n=1\):99 if\(TDOA_{j}(n+1)>\epsilon\) \(TDOA_{j}(n+1)=TDOA_{j}(n)\). endif endfor endfor
4: Return: TDOA1 TDOA2 TDOA3. ```  
**Algorithm 3** Robust TDOA measurement  
In the entire process mentioned above, we can obtain robust TDOA measurements. When the speed of sound is known, we can convert TDOA into distance difference. By using three or more effective TDOA observations, a smartphone can locate its own position.