  Non-terrestrial Networks (NTNs) have become an appealing concept over the
last few years and they are foreseen as a cornerstone for the next generations
of mobile communication systems. Despite opening up new market opportunities
and use cases for the future, the novel impairments caused by the signal
propagation over the NTN channel compromises several procedures of the current
cellular standards. One of the first and most important procedures impacted is
the random access (RA) procedure, which is mainly utilized for achieving uplink
synchronization among users in several standards, such as the fourth and fifth
generation of mobile communication (4 & 5G) and narrowband internet of things
(NB-IoT). In this work, we analyse the challenges imposed by the considerably
increased delay in the communication link on the RA procedure and propose new
solutions to overcome those challenges. A trade-off analysis of various
solutions is provided taking into account also the already existing ones in the
literature. In order to broaden the scope of applicability, we keep the
analysis general targeting 4G, 5G and NB-IoT systems since the RA procedure is
quasi-identical among these technologies. Last but not least, we go one step
further and validate our techniques in an experimental setup, consisting of a
user and a base station implemented in open air interface (OAI), and an NTN
channel implemented in hardware that emulates the signal propagation delay. The
laboratory test-bed built in this work, not only enables us to validate various
solutions, but also plays a crucial role in identifying novel challenges not
previously treated in the literature. Finally, an important key performance
indicator (KPI) of the RA procedure over NTN is shown, which is the time that a
single user requires to establish a connection with the base station.
