369
1 INTRODUCTION
Currentlyinterferences,jammingandspoofingofGPS
receiversaregrowingthreatseverywhereinmodern
technologies[14]includingmaritimeshipping[1],[7],
[10],[11].DuetothelowGPSreceivedsignalpower,
improvement of malicious interference technologies
andscalingdown thecostofcorrespondingdevices,
theconceptof
guaranteedpositioning,navigationand
timing(PNT)isseriouslythreatened[6].
Modern navigation depends on accurate, precise,
and timely data that usually comes from external
sources,mostly,GPS[9].Nevertheless,contemporary
realities testify to the significant vulnerability of the
PNTconcept,whichinitsbasicconfigurationrelieson
the primacy of GNSS
[3]. Two main alternative
technological approaches exist to PNT
implementation: relative PNT and absolute PNT.
Relative PNT uses on‐board sensors to track
movementsandcalculatevessel’spositionaswellas
keep sharp time without using external signals.
Relative PNT is not susceptible to jamming or
spoofing. However, the cumulative
effect of small
errors in measuring movement degrades position
accuracy over time. AbsolutePNT relies on external
informationsourcestodeterminevessel’sposition,for
example,deadreckoningandinertialsystems.
An example of a practical approach to
implementing an alternative GPS navigation is AIS
RangeMode(R‐Mode)project[8].This
projectisnot
AIS R-Mode Trilateration for GPS Positioning and
Timing Insurance
O.V.Shyshkin,V.I.Konovets,V.M.Koshevyy
NationalUniversity“OdessaMaritimeAcademy”,Odessa,Ukraine
ABSTRACT: Satellite navigation is the backbone of maritime navigation today. However, the technical
vulnerability of on‐board Global Navigation Satellite System (GNSS) receivers the satellite system greatly
destabilizesmaritimesecurityduetothelossofship’spositionandaccuratetime.Thisarticledevotedto
study
analternativemethodforobtainingcoordinatesandaccuratetimebasedontheuseofautomaticidentification
system (AIS) radio channels, so‐called range mode (R‐Mode). We use other AIS ship stations with reliable
positiondataasreferencestationsanddeterminetimeofarrivalforreceivedAIStransmissions.To
improvethe
accuracy of measuring signal arrival instance in the time difference of arrival (TDOA), that we utilize for
trilateration,itisproposedsignaloversamplingandapplyingthefastFouriertransform(FFT)totheproductof
quadraturecomponentsofthebasebandGaussianminimumshiftkeying(GMSK)signalinthewindowof
AIS
timeslot.Totakeintoaccountthemovementofotherships,appropriatecoordinatecorrectionsareforeseen,
which can be calculated by dead reckoning or by the inertial navigation system of our ship. The proposed
methodisfullycompatiblewiththeexistingAISsignalsandmaybeemployedincritical
situationsoflocally
limited(jamming,spoofing)GNSSabilities.Itcanbeimplementedasaseparateunit,workingforreceivingin
parallelwiththemandatoryAIStransponder.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 18
Number 2
June 2024
DOI:10.12716/1001.18.02.13
370
relative PNT, nevertheless is free from GPS
dependency. It intended to tackle the challenges
related to the disturbances and develop a new
independent of the GPS system that would allow a
safeandmoreaccuratepositioning.
R‐ModereferstousingAISchannelsformeasuring
signal delay propagation from the
coast beacon
stations(availableatleastthreesimultaneously)tothe
vessel.R‐Modeisapromisingtechnologytosupport
integrityoftraditionalpositioning GNSSmethodsin
emergencylikeGNSSfailureofvariousscenarios.
The obvious tasks for the AIS R‐Mode
implementationaretheneedtocreateanappropriate
coastal
infrastructure and measure the propagation
timeofAISsignal.
In this article, we explore the possibility of
temporal replacing the standard on‐board GPS
navigation in the case of GPS receiver failure or
external local intervention, like jamming/spoofing
attacks, leading to the functional inability of GPS
receiver(s).Thedesignedmodelin
ourstudyincludes
ourshipunderthelossofGPSnavigationabilityand
other ship stations with a normally working GPS
systemand AIS channels. Itis assumedthatat least
three other AIS stations simultaneously within VHF
communications regularly transmit their own
coordinates, which are used as the positions
of
referencestations.
Thetaskistorestorethepositioningofourvessel
by using AIS data and additional capabilitiesof AIS
channelsformeasuringsignaldelaysandcalculating
our coordinates and time corrections using the
trilaterationmethod.
2 TRILATERATION
Trilateration for two‐dimension means the
determinationofthelocationof
apoint based on its
distancefromthreeotherknownpoints.Tomeasure
distancesTimeofArrival(TOA)andTimeDifference
ofArrival(TDOA)techniques.TOAmethodisbased
on knowing the exact times of transmitting from a
references points and arriving the signal at a
measured point, taking into
account signal speed
propagation (speed of light c). TDOA method does
not require knowledge of absolute times at the
transmitter and receiver but needs only the signal
delay times from the reference sources with an
accuracyupto a constant value. Moreover,it allows
youtogetthetimecorrection
forinternalclockthatis
veryimportantforsafenavigation[16].
The system of trilateration equations can be
writteninthecompactformas:
01,2,3,
ii
xp r tc i
(1)
where
...
– denotes Euclidian norm (distance from
referenceobjecttothepointtodedetermined;
12
(; )
x
xx – vector‐column of coordinates to be
determined(inMatLabnotation);
12
(; )
iii
ppp –knownpositionsofreferencestations:
ii
rc – pseudo ranges calculated on the base of
TDOAdelays
i
;
t –unknowntimecorrectionofinternalclockatthe
receiverpoint.
Equation system (1) presents the system of three
nonlinearequationwithunknowns
12
,,
x
xt.
General approach to solve such equation is
iterative least squares method, or Gauss‐Newton
method [15]. Author of this paper criticizes various
attempts to outperform Gauss‐Newton method by
meansdifferentiterativeandclosedformalgorithms.
Likely MatLab has imbedded function “fsolve” to
solve system of nonlinear equation using Gauss
‐
Newton algorithm in one form or another. Tic‐toc
procedure in MatLab, ver. 9.5 (R2018b) gives the
computation time 0.19 seconds for solving Eq. (1) at
hardware processor Intel(R) Core(TM) i5‐1035G4
CPU,1.50GHz,withWindows10Pro.
Some simulation results for trilateration process
are shown in Fig. 1
under the following scenarios:
Coordinatesofreferencepoints:p
1(0,2);p2(5,3);p3(2,0),
measured pseudo distances: r=[1.3; 1.8; 1.6]].
Calculated point is x(2.226; 2.594) and time error
converted in distance tc =‐1.007 (clock is ahead).
This situation is demonstrated in Fig. 1 a). Three
circles(blue,red,yellow)withcentresinthepointsp
i
and radii r touch the forth one (violet), centred in
pointx=(x
1;x2),andhavingradiusabs(tc)=1.007.The
violetcircleisoutsidetheotherthreecircles.Fig.1b)
plotted for exact clock – when three circlers are
intersectedinpointx;andFig.1c)plotcorrespondsto
late clock when the forth circle centred in x touches
anotherthree
circles,beinginsideeachofthem.
Figure1.Trilaterationcircles:a)clockisahead;b)exactclock;c)lateclock
371
Anexampleofroot‐meansquared(RMS)errorof
functions(1)independencefromcoordinatesx
1,x2is
showninFig.2.MinimumofRMSerrorisachievedat
pointx
1=2.226;x2=2.594.
Algorithm works as well for solving
overdeterminedsystemsofequationwhenitsnumber
exceeds number of unknowns. The overdetermined
system generally allows getting solutions that are
moreaccurate.
Figure2.3DfunctionofRMSerror
3 SYNCHRONIZATION
TDOA method requires connecting of transmissions
from reference stations to the exact time. AIS uses
time division multiple access (TDMA) protocol to
share common frequency VHF channels, usually Ch
87B,161.975MHzandCh88B,162.025MHz[12].All
AIStransmissionsconnectedtothebeginningoftime
slotof
duration26.667ms.
Standard AIS transponder has imbedded GPS
receiverthatoutputspulsespersecondsynchronized
with coordinated universal time (UTC). AIS station
which has direct access to UTC timing with the
required accuracy indicates this by setting its
synchronization state to UTC direct (Sync state = 0).
Weuse
onlyUTCdirectlysynchronizedAISstations.
Another issue to be solved it is estimation of
arriving signal moment at the receiving AIS station.
AIS uses Gaussian minimum shift keying (GMSK)
baseband signal. GMSK parameters relating to
physicallayer,whichisresponsibleforthetransferof
abit‐streamfromthesource
tolinklayer[12],are:
Channelbandwidth25kHz
Bitrate9600bit/s±50ppm
Trainingsequencealternatingzeros 24bit
andones(0101....)
Startflag01111110(7Eh)8bit
Slotlength256bit/26.667ms
TransmitBTproduct~0.4
ReceiveBTproduct~0.5
GMSKmodulationhandlesdatatransferverywell
butitpoorlysuitablefortimearrivalmeasurements.
That is why R‐Mode project assumption was to use
the correlation technique, which utilizes the
pseudorandom ranging sequenceto utilize all signal
energy for ranging improvement [2]. Importance of
correctsynchronization of base stations is
studiedin
paper [13]. Another approach to obtain the time of
arrivalvaluesproposestimestampdetectionofGMSK
signalusingthedifferentialpeakdetectionandzero‐
crossing detection in cooperation with rather
sophisticated Orthogonal Matching Pursuit (OMP)
algorithm[5].
Instead, we propose a solution while staying
withintheITU‐R
M.1371standard.Theessenceofthe
proposal is as follows. Modern GMSK demodulator
electronicisbasedontherepresentationoftheGMSK
baseband signal in the form of two components: in‐
phaseI(t)andquadratureQ(t)components[4].
I(t) and Q(t) signals for binary data sequence
01111110aresimulatedinFig.
3.Signalsarepresented
inthetimescaleaccordingtoAISspecification(data
bitdurationT
b=1/9600=0.104ms).Theproductofthese
signalsI(t)Q(t)isshowninblack.Theperiodicitywith
the frequency 4800 kHz for the product signal is
clearly manifested. To improve the accuracy of bit
edge detection, we make oversampling of baseband
signalandperformtheFFTovertheentiretimeslot.
Local area
of amplitude spectrum are presented in
Fig.4forthenextparameters:
Samplingfrequencyfs19.66MHz
Signal‐to‐NoiseRatio0dB
FFTsizeN524288
LengthofdatainGMSKsignal256bit
Figure3.GMSKbasebandsignals:I(t)red,Q(t)blue,I(t)Q(t)
blackforStartflagsequence
Figure4. FFT amplitude spectrum, harmonic number 128
(frequency4.8kHz)
372
Despite the impressive sample size (500 M), the
FFT procedure is completed in 0.01 seconds under
abovementionedsoftandhardwareconditions.
Clearly visible harmonic number 128 even under
SNR = dB corresponds to half down data rate of
4800kHz.
Taking into account the cyclic shift property of
discrete
Fourier transform x(n)X(k), which states
that a circular shift by m samples of the input
sequence in the time domain corresponds to
multiplyingtheoutputinthefrequencydomainbya
linearphase:
2
exp
j
x
nm Xk km
N
(2)
Usingthisformula,weget the expression forthe
timedelayforourcaseintheform:
Rx
t
R
(3)
where
– the measured phase in rad of the 4.8kHz
harmonic;
R=9600bit/s–standarddatarate.
2Pi phase periodicity should be regarded in
formula(3).
It should be noted that the phase measurement
errors caused by the influence of electronic circuits
andothersystematicfactorsforsignals
fromdifferent
reference sources will be the same and therefore do
notaffecttheaccuracyintheTDOAmethod.
Practically the accumulation of signal samples
shouldbeperformedfromthebeginningoftimeslot
(accordinginternalclockofourship).Theon‐airde‐
layofthesignalcomestoa
shiftofthesignalsamples,
butnotinthemannerofacyclicshift,butsimplyto
theright.Thebeginningofthesequenceisfillingwith
a possible buffer signal of the previous time slot.
According to specification [12] signal transmission
mustbeendedtothetimeT3=
24.167msandfalling
down to zero power within the next 1 ms. So, in
general we have some zeros encapsulation and
cutting the end buffer of the transmitted slot. Such
variation from formula (2) do not principally affect
theavailabilityoftheproposedmethod.
Noise influence on the delay measurement
accuracy was simulated using stochastic modelling
forvariousdatasequencelengthsfrom16to256bit.
The results are presented in Fig. 5. As expected, the
length of data sequence significantly affects the
measurement accuracy. In all calculations, the
sampling rate was taken equal to f
s=19.66MHz.
Oversamplingisnecessaryforachievingthenecessary
measurement accuracy. The length of bit sequence
(ndata)expressesthewidthofthewindow.
The obtained simulation results fit the theoretical
Cramer‐Rao bound on the variance of the estimated
parameter
:
2
ˆ
var
n
, where in our case
n=ndata.
0 5 10 15 20 25 30 35 40
Signal-to-Noise Ratio, dB
0
20
40
60
80
100
120
140
160
ndata = 16
32
64
128
256
Figure5. Dependence of RMS error (STD, meters) in
measurementofGMSKsignaldelaytimeonsignal‐to‐noise
ratio(dB)andsignallengthinbits(ndata=16,32,64,128,
256)
4 DEADRECKONING
It is ideal to transmit signals from the different
reference stations in TOA/TDOA methods
simultaneously.However,theAISTDMAmodedoes
not allow this because the AIS stations alternately
transmit their data in the different time slots. This
transmission time separation does not prevent
achieving correct time delay
measurements if the
transmissions are synchronized with the direct UTC
time source of the AIS reference stations. We study
ourmodelonthisbasis.Themovementofourvessel
during the time between adjacent time delay
measurements must be taken into account, for
example, by dead reckoning using log and
gyrocompassdata. Inertial navigation system can be
usedalso.
TimeseparationoftransmissionsfromanotherAIS
stations can be taken into account by modifying
equations (1) by entering adding appropriate
corrections, caused by vesselʹs movement. The
detailedformoftheequations(1),takingintoaccount
thecorrections,ispresentedin
thefollowingview:
22
111 2 21 1
22
1 12 12 2 22 22
2
22
1 13 13 2 23 23
3
0,
...
0,
...
0,
xp xp c t
xpx p
ct
xpx p
ct
(4)
where
x
1,x2–coordinatesofourshipatthemomentoffirst
measurement;
p
1i,p2i–coordinatesofreferenceAISstations,i=1,2,3;
1i,
2i–corrections(latitude,longitude),i=2,3;
1, 2, 3 – measured time delays the reference AIS
stations;
373
t–timecorrectionforourship;
c–speedoflight.
AIS stations transmit scheduled position reports
(message1) at 6 second intervals (ship moving with
speed14‐23knots).Positionreport,amongotherdata,
contains: latitude and longitude in 1/10 000 min,
position accuracy flag (high,
10 m /low, >10 m).
PreferencemustbegiventoAISstationswiththebest
performance.
Delay measurements
1, 2, 3 are made in the
followingsequence.Firstwegetthevalue
1andtreat
thecoordinatesofthefirstAISreferencestationtothe
slot beginning, at time, say, t
1. The second
measurement
2willbeobtainedatthemomentt2of
receiving a suitable slot from the vessel with
coordinatesp
1i,p2i,i=2,andthethirdmeasurement3
willbeobtainedatthemomentt
3forcoordinates,p1i,
p
2i, i=3. Appropriate corrections
1i,
2i, i=2,3, are
believed, to be calculated by means dead reckoning.
As a result of solving the system (4), we obtain the
coordinatesx
1,x2ofourshipandtimecorrectiontat
thetimet
1.
Overdetermined system (4), when i>3, is also
appropriate and gives more accurate solutions for
positioningx
1,x2andtimingtinaccordancewiththe
of least squares method for the Gauss‐Newton
algorithm.
5 CONCLUSIONANDDISCUSSION
GPS‐basedpositioningandtimingfunctionsonboard
the ship should be supported by alternative backup
methods.Thisarticleproposesamethodforreplacing
satellitenavigationduringitspossiblerejection
dueto
GNSSjamminginthelocalareaaroundourvesselby
means the use of AIS channels and reliable position
datafromotherships,whicharenotunderjamming
influence.
In our study, we address scenario when another
vessels (at least three) are located within the VHF
communication, equipped
appropriate AIS station,
which having direct GPS time synchronization and
reliable positioning. Such scenario is quite likely on
traditional sea routes. Based on the use of 2D
trilateration, the TDOA ranging method, and the
application standard AIS channels as defined by
Recommendation[12],thefollowingmainsourcesof
errors in positioning
and timing can be listed and
identifiedinthenextmanner:
1. timeuncertaintiesofAIStransmissionsfromother
vessels,whichareusedasreferencestations;
2. errorsinmeasuringthemomentsofsignalarriving
onourship;
3. errors caused by the instability of our clock
betweentransmissionsfrom
otherships;
4. errorscausedbyreckoning;
5. errorcausedbytheʺpoorʺpositionsofotherships
relativetoourship(poorgeometry).
The main problem that we clearly realize is the
time uncertainties of transmissions from other AIS
ship stations (item 1). Here we rely on the
requirementsofthe
defactoAISstandardintheform
of Recommendation ITU‐R M.1371‐5, in particular,
concerning the signal requirements at the physical
layer of AIS interconnection model. This standard
definesbittimingfromAISslotbeginning[11,Table
6] not pointing thetolerance to time shift. Herewith
slottimeborders
aretiedtotheabsolutetimeofGPS
accuracy under the condition of direct GPS
synchronization. Namely AIS stations with direct
synchronization we use as reference ones. The
question whether bit transmission accuracy by AIS
transpondersfromdifferentmanufacturerspractically
corresponds to above mentioned parameters is
opened and may be the
direction of subsequent
researches.
Thetaskofarrivalmomentmeasurement(item2)
is settled by the next manner. Firstly we stay in the
frames of using standard baseband GMSK signal
according with demands to signal on physical layer
[12]. To estimate time of arrival we apply sampling
frequency to GMSK
signal fs=19.66MHz and FFT
processing of in‐phase and quadrature components
productoveratimeslotofduration26.67ms.Inthis
case, the internal clock is used without pulses per
second(PPS)synchronization,whichisimpossiblein
jammingconditions.Simulationresultsyieldsa10m
RMS distance
error under a signal‐to‐noise ratio of
only10dB(seeFig.5).ApplicationofTDOAmethod
eliminates systematic errors in the time delay signal
measurementsfordifferentvessels.
After the loss of GPS synchronization due to
jamming,theinternalclockisobligedtoworkwithout
PPS correction. Time gap
between consecutive
measurementsofsignal delayleadstoan error3)of
the list above under internal clock instability. The
systemofequations (4)includesthesame timeerror
t of the internal clock to be corrected for all three
measurements. Ideally all delays measurements
should be done for all
simultaneously transmitted
signals. However, AIS time‐division transmission
protocoldoesnotallowtorealizethis.Takingshort‐
termstabilityofacrystaloscillator 10
‐9
andthetime
intervalduringwhichsignalsfromthreeshipscanbe
received10seconds(withtransmissionintervalsof6s
for AIS message 1), we obtain a deviation within
0.01μs(intermsofadistanceitcorrespondsto3m).
Dead reckoning errors (item 4) in the corrections
1i,
2iinthesystemofequations (4)aredetermined
by the accuracy characteristics of the gyrocompass
andlog.
And,finally,theerrorcausedbythepoorrelative
position of the vessels (item 5) is calculated in
accordancewiththeconceptofhorizontaldilutionof
precision(HDOP).
Technically, the proposed method can
be
implementedasaseparateunit,workingforreceiving
in parallel with the mandatory AIS transponder. A
certain computational burden should not be an
obstacle to the device implementation in the
conditions of modern software and technological
level.
374
REFERENCE
[1]Bhatti J., Humphreys T. “Hostile Control of Ships via
False GPS Signals: Demonstration and Detection,”
Navigation, Journal of the Institute of Navigation, vol.
64,no.1,2017,pp.51–66.
[2]Bronk K., Koncicki P., Lipka A., Niski R., Wereszko B.
“Concept,signaldesign,andmeasurementstudiesofthe
R‐mode
Baltic system”. NAVIGATION: Journal of the
InstituteofNavigation.Vol.68(3),2021,pp.465‐483.
[3]Carrillo A. P. “Surface Crews Need More Tools to
Navigate without GPS”. U.S. Naval Institute
Proceedings, July 2022, Vol. 148/7/1,433. Surface Crews
Need More Tools to Navigate without GPS |
Proceedings‐July2022Vol.
148/7/1,433(usni.org)
[4]COM‐1827SOFT GMSK DEMODULATOR
https://comblock.com/download/com1827soft_GMSK_d
emod.pdf
[5]Huai S., Zhang S., Zhang J., Huang K. “Holographic
detection of AIS real‐time signals based on sparse
representation”. EURASIP Journal on Wireless
CommunicationsandNetworking,2019.
[6]IMO MSC.1/Circular.1575. Guidelines for Shipborne
Position, Navigation And Timing (PNT) Data
Processing.2017.
[7]Jamming and Spoofing of Global Navigation Satellite
Systems(GNSS).INTERTANKO,2019.
[8]Johnson G., Swaszek P. “Feasibility Study of R‐Mode
using AIS Transmissions Investigation of possible
methods to implement a precise GNSS independent
timingsignalforAIStransmissions”.ACCSEASProject.
2014.
[9]MajorF.G.QuoVadis:EvolutionofModern
Navigation.
TheRiseofQuantumTechniques.Springer.2013.440p.
[10]Marcos E. Pérez, Konovaltsev A., Caizzone, S., et al.
“Interference and Spoofing Detection for GNSS
Maritime Applications using Direction of Arrival and
ConformalAntennaArray”.31stInternationalTechnical
Meeting of the Satellite Division of The Institute of
Navigation: conference
paper. ION GNSS+, 2018. pp.
2907‐2922.
[11]NeumannT. “Automotive and telematics
transportation systems”, 2017 International Siberian
Conference on Control and Communications, SIBCON,
2017,10.1109/SIBCON.2017.7998555.
[12]Recommendation ITU‐R M.1371–5 (2014) Technical
characteristics for an automatic identification system
usingtimedivisionmultipleaccessintheVHFmaritime
mobilefrequencyband.
[13]Rieck C., Gewies S., Grundhöfer L., Hoppe M.
“Synchronization of R‐Mode Base Stations”. 2020 Joint
ConferenceoftheIEEEInternationalFrequencyControl
Symposium and International Symposium on
ApplicationsofFerroelectrics(IFCS‐ISAF),2020.
[14]Satellite‐derivedTimeandPosition:AStudyofCritical
Dependencies,editedbyS.Battersby,
U.K.Government
OfficeforScience,London,U.K.,2018.
[15]Sirola N. “Closed‐form Algorithms in Mobile
Positioning: Myths and Misconceptions”, Positioning
NavigationandCommunication(WPNC),2010.
[16]Weintrit A. “The Concept of Time in Navigation”.
TransNav, The International Journal on Marine
NavigationandSafetyofSeaTransportation,11(2),2017,
June,pp.
209‐219.
