  Non-Terrestrial Networks (NTNs) are widely recognized as a potential solution
to achieve ubiquitous connections of Narrow Bandwidth Internet of Things
(NB-IoT). In order to adopt NTNs in NB-IoT, one of the main challenges is the
uplink synchronization of Narrowband Physical Random Access procedure which
refers to the estimation of time of arrival (ToA) and carrier frequency offset
(CFO). Due to the large propagation delay and Doppler shift in NTNs,
traditional estimation methods for Terrestrial Networks (TNs) can not be
applied in NTNs directly. In this context, we design a two stage ToA and CFO
estimation scheme including coarse estimation and fine estimation based on
abrupt change point detection (CPD) of phase series with machine learning. Our
method achieves high estimation accuracy of ToA and CFO under the low
signal-noise ratio (SNR) and large Doppler shift conditions and extends the
estimation range without enhancing Random Access preambles.
