=Paper=
{{Paper
|id=Vol-3248/paper23
|storemode=property
|title=Parallel Grouping Fast Capture Optimization Based on the Combination of Computational Complexity and Capture Performance
|pdfUrl=https://ceur-ws.org/Vol-3248/paper23.pdf
|volume=Vol-3248
|authors=Pengcheng Zhang,Xinming Huang,Linyuan Hou,Jingyuan Li,Zengjun Liu,Gang Ou
|dblpUrl=https://dblp.org/rec/conf/ipin/ZhangHHLLO22
}}
==Parallel Grouping Fast Capture Optimization Based on the Combination of Computational Complexity and Capture Performance==
https://ceur-ws.org/Vol-3248/paper23.pdf
Parallel Grouping Fast Capture Optimization Based on the
Combination of Computational Complexity and Capture
Performance
Pengcheng Zhang, Xinming Huang, Linyuan Hou, Jingyuan Li, Zengjun Liu and Gang Ou
College of Electronic Scinence, National University of Defense, Changsha 410000, China
Abstract
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.
Keywords 1
Indoor positioning, STL signal, signal acquisition, computational complexity, acquisition
performance
1. Introduction
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
IPIN 2022 WiP Proceedings, September 5 - 7, 2022, Beijing, China
EMAIL: 1711376417@qq.com (Pengcheng Zhang); hxm_kd@163.com (Xinming Huang); 825563358@qq.com (Linyuan Hou)
©️ 2020 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
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.
2. NAVIGATION SIGNAL ACQUISITION
2.1. Parallel grouping fast acquisition method
Signal acquisition is essentially the process of signal detection and estimation on the two-
dimensional 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
Fp point FFT Fp point FFT Fp point FFT
and detection and detection and detection
1 2 N
A total of M A total of M A total of M
multiply
Signal correlators correlators correlators
correlator
correlator
correlator
correlator
correlator
correlator
L point
L point
L point
L point
L point
L point
Local
carrier and
pseudocode
Figure 1: Parallel grouping fast acquisition structure diagram
Among them, the signal is divided into N sections, IF accumulation time , there are M correlators
in each section of the signal, the number of FFT input points is M, and the zero-padded to the integer
power Fp of 2, the number of coherent integration points of each small correlator is L, the corresponding
coherent integration time Tc=T/N/M. Assuming that the sampling rate is the sampling rate, the sampling
interval is Ts, and the number of coherent points in each section is , each coherent integration has a
total of M sections, and then the obtained M-point coherent integration value is subjected to the FFT
operation of the Fp point, and finally accumulated after N times, Post-accumulation can be performed
by means of square-law detection.
2.2. Parallel Packet Fast Acquisition Method Performance
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:
1 L −1
v ( m) =
L l =0
r (mL + l ) * c* Loc (mL + l , )
( m +1)Tc
1
r (t ) * c (t − )dt
*
2
𝐸 = 𝑚𝑐 , Tc mTc
(1)
sin( f d Ts L)
= C * R ( ) * *exp( j )
L sin( f d Ts )
= f d *(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, f d is the Doppler frequency, 0 is the initial phase of the signal, then the loss
caused by the code phase is Dcode = R 2 ( ) , and the Doppler frequency The resulting loss is
sin( f d Ts L) 2
Ddoppler1 = ( ) .
L sin( f d Ts )
2) Fp point FFT
In order to facilitate the FFT operation, the M point data is generally zero-padded to the Fp point
(Fp is an integer power of 2). The FFT operation expression is as follows:
1 M −1
Yk (q) = v(m)*exp(− j 2 mq / Fp)
M m=0
(2)
Following the method of calculating the loss in the first part, the actual Doppler loss of this process
can be obtained as:
sin(f LOSSTc M ) 2
Ddoppler 2 = ( )
M sin(f LOSSTc )
(3)
fs 1
f LOSS = max f d − q * f = f
2 LFp 2
SNR of signal before signal detection is as follows:
C * Dcode * Ddoppler1 * Ddoppler 2
SNRB =
R (0) * N 0 / Tc / M
2
sin 2 M (4)
T 2 d T 4 Fp
= C / N0 Sa
N M 2
2N M 2
sin 2
4 Fp
1
Among them, the total signal time T=N*M*Tc, the autocorrelation function Dcode = R ( ) =
2
4
(the maximum code phase difference is 0.5 chips), the Doppler estimation deviation d = 2 f d .
3) Envelope detection
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 = (5)
SNRB + 2.3
Combined with the above analysis, the detection loss of the signal after envelope detection is:
T SNRB + 2.3
Lc = C / N 0 (6)
N SNRB2
4) Accumulate after N videos
After the navigation signal is coherently integrated, the Fp point vector is output, and the square-law
detection output decision amount is the sum of the squares of the Fp point vector and takes the larger
decision amount.
N −1 N −1
V = max Yk = Yk (l )
2 2
(7)
k =0 k =0
3. ACQUISITION ALGORITHM OPTIMIZATION METHOD
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
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
(corresponding to the coherent integration time Tc = ). When the sampling rate is f s (the
MN
corresponding sampling interval is Ts , L = Tc * f s = Tc / Ts ), and N c represents the number of code
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:
=N FFT / 2*log 2 ( N FFT ) (8)
=N FFT *log 2 ( N FFT )
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:
1 =4* N FFT / 2*log 2 ( N FFT )
(9)
1 =3* N FFT *log 2 ( N FFT )
Then the computational complexity of the parallel grouping fast acquisition algorithm can be
summarized as shown in the following table 1:
Table 1
THE NUMBER OF MULTIPLICATIONS
Steps The number of multiplications The number of additions
L point
coherent 4 Nc N * M * L 2 Nc N * M * L
integration
Fp point FFT 2 N c * NFp log 2 ( N1 ) 3N c * NFp log 2 ( Fp )
Envelope
4 N c * NFp N c * N ( 3Fp+1)
detection
2ML + 3Fp log 2 Fp
total 2 N c * N ( 2ML + Fp log 2 Fp+2Fp ) Nc * N
+3Fp+1
Computational complexity can be thought of as the sum of the multiplier and adder computations.
T
since each small correlator point L = f s , the expression for computational complexity can be
MN
rewritten as:
O = 6 N cTf s + 5 N c NFp log 2 Fp+7N c * NFp+N c N (10)
3.2. Optimum IF accumulation time
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:
sin 2 M
T f T 2 Fp
SNRB = C / N 0 Sa 2 d (11)
N M 2
2N M
sin 2
2 Fp
T SNRB + 2.3
Lc = C / N 0 (12)
N SNRB2
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 f d are 500Hz, 1000Hz, 2000Hz,
3000Hz, and 4000Hz, respectively, and the corresponding doppler frequency deviation f d are 250Hz,
500Hz, 1000Hz, 1500Hz, and 2000Hz. Analyze the relationship between detection loss, the number of
segments N, and IF accumulation time Ta .
Figure 2: Relationship between loss and number of segments N
Figure 3: Relationship between loss and IF accumulation time
Table 2
OPTIMIZATION PARAMETER TABLE
Doppler search interval f d （Hz） 500 1000 2000 3000 4000
Maximum Doppler Deviation f d
250 500 1000 1500 2000
（Hz）
optimal number of segments N opt 3 5 8 11 13
Optimum IF accumulation time T opt
1 0.6 0.375 0.273 0.231
（ms）
Minimum processing loss Lmin (dB） 0.5114 0.7794 1.1988 1.5471 1.8523
Computational complexity（10^7） 8.63 9.36 10.45 11.54 12.27
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.
Figure 4: Relationship between joint optimization factor and number of segments N
Figure 5: Relationship between joint optimization factor and IF accumulation time
Table 3
Optimization parameter table
fd 500 1000 2000 3000 4000
Doppler search interval （Hz）
fd
Maximum Doppler Deviation 250 500 1000 1500 2000
（Hz）
N 2 4 6 8 9
optimal number of segments opt
Optimum IF accumulation time
T opt 1.5 0.75 0.5 0.375 0.333
（ms）
L
Minimum processing loss min 2.9513 3.3397 3.9445 4.4682 4.9428
(dB）
Computational complexity 10.81
8.26 8.99 9.72 10.45
（10^7）
4. CONCLUSION
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.
5. References
[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