With the development of human life style and the increasingly large and complex indoor environment, human needs for LBS services indoors are increasingly urgent. Traditional GNSS navigation is difficult to provide stable and reliable indoor positioning services. The Iridium constellation, as a low-orbit satellite system currently in operation and providing mature STL services, has been tested and demonstrated that low-orbit satellite navigation has application potential in indoor positioning services. Signaling acquisition, optimize the acquisition for the parallel packet fast acquisition algorithm, establish a joint optimization factor of computational complexity and acquisition performance, determine the optimal number of segments and the optimal IF accumulation time, which can reduce the performance loss by about 3dB. 12% of the calculation amount, the acquisition optimization algorithm in this paper can alleviate the problem of the shortage of computing resources caused by the sharp increase in the number of signals during the development of the low-orbit system. Indoor positioning, STL signal, signal acquisition, computational complexity, acquisition
performance
Location-based service (LBS) has become a basic service requirement for people's life and work, and people's indoor demand for LBS service is increasing urgent. Traditional GNSS navigation is difficult to provide stable and reliable indoor positioning services, mainly because most GNSS navigation satellites are MEO satellites, with high orbital altitude, low landing level of satellite navigation signals [1], and will be blocked by buildings and multipath. Due to the influence of the effect, it is difficult for the signal to be received normally indoors and cannot meet the needs of indoor positioning. At present, indoor positioning technologies mainly include Bluetooth, infrared positioning, WIFI, RFID (radio frequency identification positioning), ultra-wideband, low-orbit navigation[2], etc.
Low-orbit satellite navigation can be used as one of the technical means of indoor positioning due to its high signal landing level, good anti-jamming and anti-spoofing performance, and can enhance the service performance of indoor and other sheltered areas. As a low-orbit satellite system currently in operation and providing mature STL services, the Iridium constellation has become a technical benchmark for low-orbit navigation and positioning. Satellites tested the performance of indoor positioning services in 2018. For traditional GPS GNSS positioning, only the topmost window position can receive signals from 1~2 satellites, and the rest of the positions can hardly receive signals; for low orbits Satellite signals can penetrate the barriers of buildings. In the case of penetrating the barriers of multi-layer reinforced concrete materials, the signal carrier-to-noise ratio can still reach (35~55) dB·Hz, which is equivalent to GNSS signal power level in an open environment [3]. Assuming that STL (Satellite Time and Location) and GNSS have similar attenuation in the path of obstacles, the STL
2020 Copyright for this paper by its authors. signal can be as weak as -160dBm, which is enough to penetrate buildings and other obstacles, providing Signal coverage in indoor and urban canyon environments. STL has been tested under different conditions, and the successful reception rate of signals in more than 300 residential and commercial tests in Tokyo is 98% [4], fully demonstrating the application potential of low-orbit satellite navigation in indoor positioning services.
STL signal is actually a specially designed burst signal containing necessary navigation and positioning information, also known as STL Burst, which is a 25kHz, QPSK modulated signal [5]. STL uses the narrowband paging channel of the Iridium system, which is a one-way satellite transmission signal with high gain. The landing power of STL signal is 30dB~40dB stronger than that of GPS, which greatly enhances the positioning, navigation and timing (PNT) capabilities. STL signals can also be received in areas with severe shading. The STL signal is a short burst signal, the signal duration is short, and the start and end positions of the signal are uncertain, and it is random. Signal acquisition algorithm, and acquisition is the first step in the baseband processing of the navigation receiver. Controlling the computational complexity of the acquisition algorithm is of great significance to the power consumption of the receiver, and is of great significance to the miniaturization and wide application of the device. Therefore, in the process of optimization of the acquisition algorithm Pay attention to computational complexity.
The parallel grouping fast acquisition algorithm correlates the signal segments, compresses the intermediate frequency accumulation time, and expands the tolerance of the Doppler frequency. The parallel frequency search algorithm reduces the large-scale FFT operation and can realize the rapid acquisition of large dynamic signals. However, at present, the optimization of the acquisition algorithm mainly focuses on the acquisition of weak signals and the improvement of performance [6]. The research on the computational complexity is relatively weak, and the computational complexity of the acquisition algorithm needs to be further optimized.
This paper first establishes the quantitative relationship between computational complexity and acquisition parameters, and then establishes a joint function of acquisition performance and computational complexity according to the initial phase of pseudocode and Doppler coherence loss, and optimizes the acquisition algorithm by considering the relationship between the two. This method can provide an optimized strategy for capturing burst signals such as STL signals.
Signal acquisition is essentially the process of signal detection and estimation on the twodimensional hypothetical parameter space composed of carrier doppler frequency and code phase [7]. This paper adopts the method of pre-detection IF accumulation and post-detection video accumulation (hereinafter referred to as parallel grouping fast acquisition method), compresses the IF accumulation time, expands the Doppler frequency tolerance, divides the signal into several segments, and divides the signal into several segments. In a section, the I and Q channels are respectively correlated and accumulated, and the output value of the correlator is correlated and then video accumulated.
The acquisition search adopts the parallel frequency search algorithm. On the basis of the traditional matched filter, the FFT method is used to realize the parallel search in the frequency domain, which reduces the acquisition time and improves the acquisition efficiency. The specific implementation structure is shown in the figure 1:
N incoherent accumulations judge multiply Signal
Local carrier and pseudocode
Fp point FFT and detection
The acquisition performance is mainly determined by the detection loss in the acquisition process, which is the difference between the acquisition algorithm and the ideal coherent detection, and can be used to compare the performance difference between different detection quantities [8]. The loss in the acquisition process can be divided into coherent loss and incoherent loss. The coherent loss is mainly because the Doppler frequency (carrier, pseudocode) of the received signal and the initial phase of the pseudocode are unknown and the influence of the filter will introduce Filter loss, code phase deviation loss and Doppler deviation loss, and non-correlated loss are mainly the loss introduced by the nonlinearity introduced by the detector.
The parallel packet fast acquisition mainly includes L point coherent integration, Fp point FFT, N times video post-accumulation and envelope detection. The signal changes of each part are deduced to obtain the loss of parallel packet fast acquisition.
1) L point coherent integration Its coherent integration output signal is as follows: = 2, v(m) = = 1 L−1
r(mL + l) * c*Loc (mL + l, ) L l=0 1 (m+1)Tc
r(t) * c* (t − )dt Tc mTc
C * R( ) * sin( fdTs L) = fd * (2m + L −1) + 0
C is the signal power, R(τ) is the self-selected correlation function between the local code and the signal spreading code, fd is the Doppler frequency, 0 is the initial phase of the signal, then the loss caused by the code phase is Dcode = R2 ( ) , and the Doppler frequency The resulting loss is Ddoppler1 = ( sin( f T L) 2
d s ) . f LOSS = max fd − q * f
fs 2LFp 1 2 = f SNR of signal before signal detection is as follows:
SNRB =
C * Dcode * Ddoppler1 * Ddoppler 2
R(0) * N0 / Tc / M = C / N0
T
Among them, the total signal time T=N*M*Tc, the autocorrelation function Dcode = R2 ( ) = (the maximum code phase difference is 0.5 chips), the Doppler estimation deviation d = 2 fd .
According to the equivalent detection loss, the output signal-to-noise ratio of parallel frequency acquisition based on envelope detection can be obtained as shown in the following formula [9].
（SNRB）2 SNRout =
SNRB + 2.3 Combined with the above analysis, the detection loss of the signal after envelope detection is:
T SNRB + 2.3
Lc = C / N0 N SNRB2
N −1 V = max Yk 2
N −1 = Yk (l )
2 3. ACQUISITION ALGORITHM OPTIMIZATION METHOD (3) (4) (5) (6) (7) 1 4
It can be seen from formulas (4) and (6) that in the parallel grouping fast acquisition method, there is an optimal IF accumulation time to maximize the fast acquisition gain, and the optimal IF accumulation time is related to the input signal-to-noise ratio and doppler frequency offset, etc. Besides, considering the impact of the computational complexity of the acquisition algorithm, the optimal IF accumulation time will also change. 3.1. Computational complexity of parallel grouping fast acquisition algorithm (corresponding to the coherent integration time Tc =
The total time of the signal processed by the acquisition algorithm is T, which is evenly divided into N segments, and the intermediate frequency accumulation is performed before detection in each segment. The coherent integration time of each segment is T/N, and the signal data of each T/N time is divided into M segments. The number of coherent integration points of the small correlator is L points T ). When the sampling rate is f s (the corresponding sampling interval is Ts , L = T * fs = T / Ts ), and Nc represents the number of code c c phase search units in the acquisition.
For a radix-2 a-point FFT, the number of complex multiplications and the number of complex additions are: MN (8) (9) =NFFT / 2 * log2 ( NFFT ) =NFFT * log2 ( NFFT ) 1 =4 * NFFT / 2 * log2 ( NFFT ) 1 =3* NFFT * log2 ( NFFT )
One complex multiplication is equivalent to 4 real multiplications plus 2 additions, and one complex addition is equivalent to 2 real additions, so the number of multiplications 1 and the number of additions 1 are:
Then the computational complexity of the parallel grouping fast acquisition algorithm can be summarized as shown in the following table 1: Table 1
coherent integration
rewritten as:
4Nc N * M * L 2Nc * NFp log2 ( N1 )
4Nc * NFp 2Nc * N ( 2ML + Fp log2 Fp+2Fp ) 2Nc N * M * L 3Nc * NFp log2 ( Fp)
Nc * N (3Fp+1) 2ML + 3Fp log2 Fp
Nc * N +3Fp+1
MN since each small correlator point L =
Computational complexity can be thought of as the sum of the multiplier and adder computations.
T
fs , the expression for computational complexity can be O = 6NcTfs + 5Nc NFp log2 Fp+7Nc * NFp+Nc N (10)
According to the acquisition algorithm loss analyzed, adopting the maximum loss minimization criterion, and the doppler frequency deviation of the maximum loss is half of the frequency search interval, so formula (4) can be rewritten as:
SNRB = C / N0
T
T SNRB + 2.3
Lc = C / N0 N SNRB2 (12)
In the actual acquisition algorithm optimization process, the analysis is usually based on the total time T given, the set condition total time T=3ms, the input carrier-to-noise ratio is 45dBHz, the code phase search interval is 0.5 chips, and the the doppler search intervals fd are 500Hz, 1000Hz, 2000Hz, 3000Hz, and 4000Hz, respectively, and the corresponding doppler frequency deviation fd are 250Hz, 500Hz, 1000Hz, 1500Hz, and 2000Hz. Analyze the relationship between detection loss, the number of segments N, and IF accumulation time Ta .
Maximum Doppler Deviation fd optimal number of segments Nopt Optimum IF accumulation time T opt （Hz） （ms） 500 250 3 1 1000 500 5 0.6 2000 1000 8 3000 1500 11 4000 2000
13
The above analysis is based on the condition that only acquisition performance is considered, and the impact of acquisition computational complexity is not considered. In order to adapt to scenarios such as low power consumption and low-orbit large dynamic signal acquisition, the computational complexity of the acquisition algorithm needs to be optimized [10]. This paper comprehensively considers the computational complexity and acquisition performance, and establishes a joint optimization factor for optimization. The optimization objective factor is: min( yi ) = min(aOi + bL) (13)
In the formula, a and b are proportional coefficients, and the appropriate proportional coefficients are adjusted according to actual needs, and the combined computational complexity and acquisition performance are established to optimize the acquisition factor.
Doppler search interval fd （Hz）
Maximum Doppler Deviation
（Hz） optimal number of segments Nopt
Optimum IF accumulation time
fd
T opt （ms） Minimum processing loss Lmin
(dB） Computational complexity （10^7） 500 250 2 1.5 1000 500
4
It can be seen that after considering the influence of computational complexity, the increase in loss is equivalent to a decrease in acquisition performance, but the computational complexity decreases. When the Doppler search interval = 2000 Hz, the loss becomes about 3dB, but the computational complexity is reduced by about 12%. This optimization method can be applied to occasions with high computational complexity requirements, and the joint optimization factor model can be further improved according to the actual situation to adapt to various situations with different acquisition performance and computational complexity requirements.
[1] LU J, GUO X, SU C. Global capabilities of BeiDou Navigation Satellite System [J]. Satellite
Navigation (English), 2020, 1(1): 5. [2] EL-SHEIMY N, LI Y. Indoor navigation: state of the art and future trends [J]. Satellite
Navigation (English), 2021, 2(1): 23. [3] Tian Run, Cui Zhiying, Zhang Shuangna, et al. Overview of the development of navigation enhancement technology based on low-orbit communication constellations [J]. Navigation, Positioning and Timing, 2021, [4] JOERGER M, GRATTON L, PERVAN B, et al. Analysis of Iridium-Augmented GPS for
Floating Carrier Phase Positioning [J]. Navigation, 2010, [5] Xie Zhuocheng. Iridium STL signal system and performance research [D]; Huazhong
University of Science and Technology. [6] Li Dengao, Li Shuai, Zhao Jumin, et al. A review of research on signal acquisition methods for global satellite navigation systems [J]. Computer Engineering and Design, 2016, 37(1): 7. [7] Qi Xinyu. Research and verification of Beidou satellite navigation receiver acquisition and tracking technology [D]; Southeast University. [8] Feng Rui, Ma Hong, Ren Yufei. An improved method for BDS B1C signal acquisition [J].
Journal of Navigation and Positioning, 2019, 7(3): 7. [9] BARTON D K, BARTON W F. Modern Radar System Analysis: Version 2.0 [J]. 1992, [10] [10] Wang Teng. A high dynamic and low signal-to-noise ratio satellite navigation signal acquisition method [J]. Navigation Positioning and Timing, 20