Comparison of available data in each step for different SINS algorithms.
Abstract
Inertial navigation systems are in common use for decades due to its advantages. Since INS outputs are usually used for inputs in different control algorithms (depending on applications), INS will induce certain errors and limitations. This chapter deals with optimization of the inertial navigation algorithm against limitations due to the accuracy and stability of signals from the sensors and constraints resulting from the integration step and processor speed used for embedded applications. Inertial navigation considered here is “strapdown” inertial navigation system (SINS) which assumes a fixed inertial measurement unit (IMU). In this chapter, fundamentals of strapdown inertial navigation will be presented as well as three different algorithms which will be analyzed in regard to numerical stability, time consumption and processor load criteria.
Keywords
 strapdown inertial navigation system
 quaternions
 forward Euler integration
 code optimization
 code analyses
1. Introduction
INS is inertial navigation system, the system that determines the position based on the output of the motion sensors: accelerometers and gyroscopes. The first INS was based on accelerometers mounted on gimbal platform, to ensure measurement of acceleration in navigational frame. Nowadays “strapdown” inertial navigation system (SINS) is in common use, due to its mechanical simplicity, reduced size and price compered to platform INS. Strapdown inertial navigation system implies a fixed inertial measurement unit (IMU), whereby the analytical picture of the navigation system is obtained from the integration of the gyroscope rates.
The main problem that arises when SINS is used is the exact determination of the orientation based on the gyroscopes outputs. Every error made in this stage will affect the error of projection of the gravitational acceleration. Accelerations are integrated twice in order to determine the position, so any errors made when determining the orientation will cause the error in position determination to increase exponentially with integration time.
Errors when determining orientation are caused by the gyroscope performance and precision, as well as signal processing methods used for processing gyroscope outputs. Besides hardware limitations of the gyroscopes, algorithms used for orientation calculation also cause errors. This chapter focuses only on errors caused by applied algorithms and on optimization of these algorithms in terms of time consumption and processor load.
2. Fundamentals of inertial navigation
The basic idea of inertial navigation is based on the integration of acceleration measured by the accelerometers; see [1]. The accelerometers measure the specific force that can be represented as:
where
In this chapter, the effect of the rotation of the Earth (which can simply be introduced into equations for the needs of systems operating in a longer time interval) is neglected.
In accordance with the previous assumption, the following relationship between acceleration and velocity in relation to the inertial coordinate frame is:
where
In the inertial navigation algorithm, for the navigation coordinate frame, the ENUp coordinate frame has been adopted; see [2]. This choice is made due to the desire to have the height coordinate positive and on the other hand in order to more accurately determine the azimuth numerically.
In accordance with the ENUp coordinate frame, the following relations apply:
As a result of the WGS84 standard for the Earth shape (see [3]), projection of angular speeds of the ENUp coordinate frame has been adopted in the following form:
where
where
As the accelerometers measure acceleration in the coordinate frame related to the object, it is necessary to determine the transformation matrix from the body frame (see [4]) into the navigation frame, using information from the gyroscopes.
The navigation algorithm adopted here can be divided into two parts. The first part that works with higher frequency plays the role of determining velocity and angle increments, while the other part of the algorithm that works eight times slower provides information on the position and the speed in the navigation coordinate frame (usually required by the guidance law in the case of the missile application). Such algorithm is advantageous from the point of optimization of the calculation time in the control computer, which can be divided into eight different steps. Also, this SINS algorithm proved to be mathematically more stable in relation to others, in determining the quaternion position at the same sampling time. Namely, when integrating angular velocities in order to obtain the angular position, depending on the size of the integration step, the quaternion error increases over time, and in addition to renormalization, it also affects the overall error in position and velocity. This error does not occur with this algorithm.
2.1. Determination of angular increments and transformation matrix
The first step in determining the transformation matrix is the determination of angular inclusions, and as explained above, this process is repeated with the basic integration step which in this example is
where
The process of calculating the position quaternion or the transformation matrix is also divided into two parts.
The first part is the calculation of the quaternion between the navigation coordinate frame and the body frame, assuming that the navigation coordinate frame can be considered inert during one step of integration.
The second part is used for the quaternion correction due to the rotation of the navigation coordinate frame.
If we compare these two transformations, we can conclude that the first transformation is the rotation of “fast” motion. One of the reasons why this algorithm proved to be numerically more stable is the separation of the integration of the “fast” rotation from the integration of the “slow” rotation.
If we compare the angular rates of those two motions, we can conclude that the “slow” rotation rates are four or more times lower than the “fast” rotation rates which leads to numerical integral errors when these two rotations are combined.
In accordance with the above, the following relations apply:
where
The quaternion of fast rotation can be represented in the form of a rotary vector as follows:
The following relationship holds for small angles:
where
To solve the previous equation, a fourstep algorithm will be used (Conning correction [5, 6, 7]):
where
If we return to the quaternion of slow rotation, the following relationship is valid:
where. Ω
If we neglect the rotation of the Earth, the following applies:
where
The Poisson equation for the transformation matrix from the coordinate frame related to the Earth (ECEF) in the navigation coordinate frame can be written in the following form:
The recursive solution of the Poisson equation can be represented in the following way:
With the quaternion of fast and the quaternion of slow rotations defined above, on the basis of Eq. (7), the quaternion of total rotation can be determined and with its direct cosine matrix representing the transformation from the body to the navigation coordinate frame. This matrix will be updated with the time step of the slow integration:
2.2. Determination of speed and position in space
Previously defined method used for determining the angle increments based on measured gyroscope signals can now be used in the same way to define the speed increments based on signals from the accelerometer. These increments are also determined by the fast integration step
where
The absolute acceleration can be written in the following form:
where
The specific force projections acting in the body coordinate frame are obtained from the accelerometer. Accordingly, the integration will be performed in the body coordinate frame, and the previous equation can be written like
If we apply integration with the slow integration step to the previous equation, we obtain the following:
The recursive solution of the previous equations is done in eight steps (sculling correction; see [5, 6, 7]) from which the step of slow integration was adopted as
The initial values in each new step of slow integration are
After calculating the velocity increments in the body coordinate frame, it is possible to determine the increment of the velocities in the navigation coordinate frame, since the matrix of transformation between the body and the navigational coordinate frame has already been defined:
The speed of the object relative to the Earth in the navigation coordinate frame can now be represented by the following relations, with the remark that the Earth’s rotation that is neglected:
where Ω
The determination of the position in the navigation coordinate frame can be solved in two ways: by integration of the velocities, which is the case in determining the height, or by the relationship between the matrix defined by Poisson’s equation and its definitions:
where
Geographical navigation parameters can be determined from the relation of the preceding equation and Eq. (14):
As the azimuth is now defined, projections of speed in the ENUp coordinate frame can be determined:
The position in the ENUp frame can be determined as
Similarly, using the matrix definition from the navigation coordinate frame and the body frame, we can get to the relations for angular positions:
3. Strapdown INS (SINS) algorithms
Three SINS algorithms based on previously defined mathematical model will be presented here.
The basic solution of SINS is forward Euler method applied to the main equations for rotation and translation. Block diagram of this method is presented in Figure 1. In this algorithm there is no division to the fast and the slow rotation, and all calculation is done in each step.
The other solution of SINS algorithm—the regular SINS—based on mathematical model previously defined is presented in Figure 2 as block diagram. The regular SINS algorithm calculates the velocity and angle increments eight times, and in the last step, Conning and Sculling corrections are implemented including all the other equations in Figure 2.
The last solution that is considered is SINS algorithm divided in eight steps. This eightstep algorithm naturally arose as a consequence of Conning equation, and it is presented in the following flowcharts.
From Figure 3, it can be seen that in each step, the main algorithm will call IMU and navigation procedures. This means that in each step, some part of calculation will be completed.
From Figure 4, it can be seen that sculling correction will be calculated in each step (Figures 5 and 6).
Similar to the IMU algorithm, the navigation procedure is also divided into several steps shown in Figure 7.
Availability of output data calculated by all three SINS algorithms is presented in Table 1.
Algorithm step  0  1  2  3  4  5  6  7 

Forward Euler method 








Regular SINS  —  —  —  —  —  —  — 

Divided SINS 



—  —  —  —  — 
From Table 1, it can be seen that forward Euler algorithm provides all SINS output values in every step unlike regular and divided SINS which will provide outputs eight times slower. Generally, guidance and autopilot algorithms do not require inputs with such high frequency, and both regular and divided SINS will usually satisfy requirements; see [8]. On the other hand, if we compare the regular and the divided SINS algorithm, we can see that in the case of the divided SINS algorithm, the entire mission algorithm can be optimized in these eight steps.
The regular and the divided SINS algorithms are based on the same numerical integration, and the results of those two algorithms are equal in time. On the other side, we can compare quaternion stability of forward Euler integration and regular SINS algorithm in time. Quaternion norm which needs to be equal to one for quaternion of rotation is sensitive to the integration step for forward Euler integration. Both algorithms were implemented in MATLAB Simulink. Norm of quaternion is presented in Figure 8 for the same integration step of 2 ms and for the same input data of gyroscopes presented in Figure 9. From Figure 8 it can be seen that the quaternion norm will be affected whenever there is significant movement of the object.
Quaternion norm error will further affect all outputs of SINS algorithm, and that will lead to error accumulation over time. Figure 10 represents angle errors for the same simulation.
4. Time consumption and processor load comparison of the regular SINS, the divided SINS and the forward Euler algorithms
Forward Euler algorithm, regular SINS algorithm and SINS algorithm divided into eight different steps presented here were compared in terms of processor load and time it takes for all necessary calculations to complete. PC with Intel Core 2 Duo P8600 processor and 4 GB of RAM was used as a testbed for comparison of the three mentioned algorithms. Ubuntu 16.04 LTS operating system in realtime mode was used for time measurements and result generation.
Instead of using real sensors to feed the data to the algorithm, the data were read from the files that contained recorded sensor outputs from INS tests previously performed. All the data were memory mapped to avoid any loss of time due to IO operations, thus making the algorithm exclusively CPU bound. Realtime interval timer set to 2 ms was used as the time frame generator for the INS algorithm in order to mimic reallife operation. Every 2 ms, an interrupt would occur causing the next piece of data to be fed to the algorithm, and the next step of the algorithm would be performed. In the case of the regular SINS algorithm, the entire quaternion calculation will be performed in every eighth step. In the case of the divided SINS algorithm, a piece of that calculation will be calculated in all of those seven middle steps as well as in the final eighth step, thus optimizing processor load and dividing calculation time across all steps in the algorithm evenly.
Statistics that are compared after the completion of the two SINS algorithms are the total time spent in every eight steps of the algorithm, average amount of time spent in every step and average processor load in each of the steps of the algorithm. Total time spent in every step of the algorithm depends on the number of steps and as such is not important as a performance measure. Average time and average processor load in each step of the algorithm are used for performance comparison. In Linux, there are three distinct time measures of process execution. Those are wall clock time, user time and system time.
Wall clock time is the amount of calendar time that elapsed from starting the process or the stopwatch until moment “now”. Thus, wall clock time includes the time the process has spent waiting for its turn on the CPU besides the time it actually spent running on the CPU. User time is the time the process spent executing on the CPU in user mode, while system time is the time the process spent executing on the CPU in system or kernel mode. User and system time measure the actual time the process spent using the CPU, and total amount of time spent on the CPU is calculated as the sum of these two time measurements.
All of these considered, wall clock represents the time that would be measured using a stopwatch. Although wall clock time heavily relies on the operating system load, on the scheduling policy used by the operating system and on the number of cores the CPU has, it can be used as a measure of time since all versions of the algorithm are subjected to the same conditions during the testing procedure. Even though the wall clock time is measured, it is not actually used in time comparison of the two mentioned algorithms. Instead, user and system time are used for comparison, because they rely only on the performance of the CPU, and the actual time it takes for calculations in the algorithm is the sum of these two times.
All times mentioned are given in microseconds. Total amount of time spent in the step of the algorithm is calculated as the sum of user and system time. Average processor load is calculated as
where
The results obtained after time measurements of the regular SINS algorithm are presented in Table 2.
Algorithm step  0  1  2  3  4  5  6  7 

Elapsed time (μs)  2.07395  2.17831  3.11257  2.71898  2.04108  2.00986  2.06820  4.82662 
Processor load  0.00104  0.00109  0.00156  0.00136  0.00102  0.00100  0.00103  0.00241 
The results obtained after time measurements of the divided SINS algorithm are presented in Table 3.
Algorithm step  0  1  2  3  4  5  6  7 

Elapsed time (μs)  2.08052  2.19571  3.09868  3.07395  2.07148  2.10682  2.27033  2.35067 
Processor load  0.00104  0.00109  0.00154  0.00153  0.00103  0.00105  0.00113  0.00115 
Results presented in the tables are not comparable to the execution times on faster or slower processors. Even though exact times are not comparable when a switch to a different CPU is made, their ratio will still hold. Relative time gain and processor load gain of the divided SINS over the regular SINS are presented in Table 4.
Algorithm step  0  1  2  3  4  5  6  7 

Time (%)  +0.32  +0.80  −0.45  +13.05  +1.49  +4.82  +9.77  −51.30 
Processor load (%)  +0.00  +0.00  −1.3  +12.5  +0.98  +5.00  +9.71  −52.28 
For the sake of completeness, forward Euler version of the SINS algorithm that performs all calculations in each timer interrupt was also taken into consideration. Every 2 ms both quaternions are calculated as well as navigation parameters. Basically, this approach has no notable steps, so the previous method of time measurement is not applicable here. Instead, the average time necessary for the calculation of both quaternions and navigation parameters is taken as the performance measure.
On average, it takes 6.16023 μs for the forward Euler algorithm to perform all calculations. This translates to average processor load of 0.00308 which is significantly worse compared to the regular SINS algorithm and even more so compared to the divided SINS algorithm. Processor load and time spent calculating in each step of the regular and the divided SINS algorithms vary from step to step, whereas the time it takes for the forward Euler algorithm to do its calculations can be considered as constant. Relative time gain (T) and processor load gain (PL) of the divided SINS (DSINS) and the regular SINS (RSINS) algorithm over the forward Euler algorithm are presented in Table 5.
Algorithm step  0  1  2  3  4  5  6  7 

RSINS T (%)  −66.33  −64.64  −49.47  −55.86  −66.87  −67.37  −66.43  −21.65 
RSINS PL (%)  −66.23  −64.61  −49.35  −55.84  −66.88  −67.35  −66.56  −21.75 
DSINS T (%)  −66.23  −64.36  −49.70  −50.01  −66.37  −65.80  −63.14  −61.84 
DSINS PL (%)  −66.23  −64.61  −50.00  −50.32  −66.56  −65.91  −63.31  −62.66 
5. Conclusion
In this chapter, navigation algorithm based on strapdown inertial navigation system algorithm optimized for coding in eight steps is presented. This algorithm proved to be a good option in situations where time and processor speed are limiting factors. Average time necessary for the regular SINS algorithm to complete all the steps and perform one full calculation is 21.02957 μs, whereas the divided SINS algorithm needs 19.24816 μs to perform the same operation, which scales to 8.47% improvement in time consumption. Even more important than time consumption improvement is the processor load in each timer interval, which is more uniformly distributed across all the steps in the divided SINS algorithm. Uniformly distributed processor load allows for easier design and development of multithreaded applications, as well as more free resources for the control computer to gather information about its surroundings and to issue commands to other devices in the control chain accordingly.
Also this algorithm proved to be mathematically more stable in term of quaternion norm, which mean that there is less error in angle computation and cumulatively in trajectory calculation.
References
 1.
Titterton DH, Weston JL. Strapdown Inertial Navigation Technology. IEE Radar, Sonar, Navigation and Avionic Series. Vol. 17. 2nd ed. 2004. 576 p. ISBN: 0863413587  2.
Salychev O. Inertial Systems in Navigation and Geophysics. 1st ed. Moscow: Bauman MSTU Press; 1998. 352 p. ISBN: 5703813468  3.
NIMA TR8350.2: Department of Defense World Geodetic System 1984, Its Definition and Relationship with Local Geodetic Systems. 3rd ed  4.
AIAA R004: “Atmospheric and Space Flight Vehicle Coordinate Systems”. American Institute of Aeronautics and Astronautics (AIAA); 1992. 69 p  5.
Salychev O. Applied Inertial Navigation: Problems and Solutions. Moscow: Bauman MSTU Press; 2004. 306 p. ISBN: 5703823951  6.
Savage PG. Strapdown inertial navigation integration algorithm design Part1: Attitude algorithms. Journal of Guidance, Control, and Dynamics. 1998; 21 (1):1928  7.
Savage PG. Strapdown inertial navigation integration algorithm design part 2: Velocity and position algorithms. Journal of Guidance, Control, and dynamics. 1998; 21 (2):208221  8.
Siouris GM. Missile Guidance and Control Systems. 1st ed. New York: Springer; 2004. 666 p. ISBN: 0387007261