0% found this document useful (0 votes)
49 views

Indoor Navigation Guidance For Mobile Device

This document describes a proposed indoor navigation system for mobile devices that provides guidance. It discusses using sensors like pedometers and magnetometers to determine a user's location and direction inside a building without GPS. The guidance would give step-by-step instructions to navigate from the starting point to the destination based on compass directions and footsteps. The accuracy of the guidance is affected by factors like user height, step calculation, and sensor threshold values. The proposed system would provide indoor navigation guidance for buildings on the Telkom University campus.
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
49 views

Indoor Navigation Guidance For Mobile Device

This document describes a proposed indoor navigation system for mobile devices that provides guidance. It discusses using sensors like pedometers and magnetometers to determine a user's location and direction inside a building without GPS. The guidance would give step-by-step instructions to navigate from the starting point to the destination based on compass directions and footsteps. The accuracy of the guidance is affected by factors like user height, step calculation, and sensor threshold values. The proposed system would provide indoor navigation guidance for buildings on the Telkom University campus.
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 54

Indoor Navigation Guidance for Mobile Device

Final Project
To fulfill the requirments to obtain
Bachelor Degree of Informatics Engineering
School of Computing
Telkom University

1301140256
Jonathan Marihot Parulian

Bachelor of Informatics Engineering


School of Computing
Telkom University
Bandung

2018
Indoor Navigation Guidance for Mobile Device

Jonathan Marihot Parulian1 , Kiki Maulana Adinugraha2 , Sultan Mofareh Alamri3


1,2 School
of Computing, Telkom University, Bandung
3 College
of Computing and Informatics, Saudi Electronic University
1 jonathangabe@students.telkomuniversity.ac.id, 2 kikimaulana@telkomuniversity.ac.id,
3 salamri@seu.edu.sa

Abstract
Navigation is capable of showing the position and direction at the specified location. In this paper, we pro-
posed an indoor navigation based on the user location to its desired destination. Indoors navigation first
needs to determine the route that can be accessed inside the building. This guidance is made by cultivating
the indoor trajectory route that utilizes the sensor technologies in mobile devices. The sensors to be used
are pedometer and magnetometer. The experiment shows that the guidance gave the instructions to navi-
gate from the start to the destination by following compass direction and footstep to take. The guidance
instruction affected by three factors, there is user height, step calculation, and sensor threshold value. The-
se three factors have different effects but interconnected with the application system and that which causes
differences in the accuracy values obtained in the experiment.

Keywords : indoor navigation, guidance, sensor, mobile device.

1. Introduction
Since a long ago, navigation is used to help determine position and direction. As technology develops, the
navigation technology continues to change and become more sophisticated. Many activities are also currently
utilizing the ability of navigation systems both on land, sea, and air. On land, people use the navigation to determine
the route from their location to the location they want to go. However, navigation on land can be divided into two
categories, outdoor navigation and indoor navigation. Outdoor navigation usually relied on one of the technology
devices that is Global Positioning System (GPS). Devices that have a GPS system will capture the data signal
transmitted from the satellite and be captured by the GPS signal receiver[14]. By using this GPS technology, we
can be directed to a predetermined location. The direction shown on the navigation system is formed into the
trajectory data that has been established as a usable path. One of the example of the GPS technology is Google
Map, as showed in Figure 1.

Gambar 1. Outdoor Navigation and Guidance Example

Most of people spend more times inside a building. Since people spend most of their time in indoor enviro-
nments, indoor navigation service is in great public demand[17]. Unfortunately, indoor navigation cannot use GPS
technology like outdoor navigation. It is because in indoor, GPS can’t work well. Based on previous research, it
was determined that the positional accuracy using GPS are approximately 5 m of true position in open sky settings,
7 m in young forest conditions, dan 10 m under closed canopies[16]. This happens due to several things. One of
them is because of the position of the human or object is under closed canopies or inside a building, the signal will
be blocked by the building or wall. This will affect the GPS signal because it cannot go through the building or
wall. So, it will use another path to reach the object (multipath). Because of this, it will be difficult to implement
a GPS system in an indoor area because of the size of the room to be used may be less than that.

Gambar 2. Indoor Navigation Example

An example of indoor navigation described in Figure 2 showing the route and the location. To develop an
indoor navigation, one that must be made is guidance. A guidance will require positioning and track down a device
with a certain positioning accuracy and reliability. This guidance will be made in the form of sequential instructions
based on the route formed. This guidance instruction will help people that will use the indoor navigation service
easier to get directions to the destination. Without this guidance instruction, a navigation system, especially indoor
navigation, will not provide its full benefits.
From the problem above, an indoor navigation would require a guidance and it will be made in the form of
sequential instructions. It aims to handle deficiency in GPS which are unreliable to be implemented in indoor. This
instruction will be made by reading the route trajectory pattern[2, 5, 10, 3, 4] obtained from previous research,
using the efficient route for indoor[1, 6] and converting it into a series of instructions for helping the indoor
navigation system.
Problem Statement and Scope
Based on the background, the Problems that occur in the indoor navigation is the need to build a guidance in
determining and indicating the exact position and direction that can not be identified by the GPS system by utilizing
the trajectory that will be constructed inside a building or room and with that trajectory, it can be used to construct
an instruction based on the route created by the trajectory data. The performance of the guidance instruction will
be perfect if the placement of the coordinate points to be read correctly and the path used in accordance with the
trajectory in the real world. This indoor navigation guidance will be useful for guiding inside a building and will
be implemented in inter-building environment of School of Computing, Telkom University’s building consisting
of D (Panambulai), E (Kultubai Utara), F (Kultubai Selatan), G (Pascasarjana) building and public engineering
prelection Telkom University’s building such as KU1 (Grha Wiyata Cacuk Sudarijanto-A) and KU2 (Grha Wiyata
Cacuk Sudarijanto-B). For this study only the first floor of each building that will be used as the location of the
indoor navigation guidance and without utilizing any GPS of the device.
Objective
This study is creating guidance that can be used to show position and direction of the indoor navigation system,
instruction that will help the navigation inside the building and discuss the analysis of direction indicators accuracy
as the status of navigation instruction. From these patterns are made instructions that will be used in indoor
navigation guidance as a result of this study.
Writing Organization
This paper is organized as follows on section II discusses about related work and previous study that used in
this case, and in third section will be explain the system adaption analysis. After that will discuss the evaluation of
this system such as testing, analysis in section IV and last of section in this paper is the conclusion of this study.
2. Related Work

2.1 Inter-Building Environment


Inter-building environment is considered one of important part when constructing an indoor navigation because
in inter-building environment there are some factors that need to be considered. Inter-building may have building
with multi-floor building and indoor environment elements representation[6].

Gambar 3. Inter-Building

The Figure 3 illustrating the inter-building condition. [10] propose the representation in indoor space identify
an object accurately by storing geographic data that are represented to undirected graph form which has three
dimensional attributes x, y, and z, where x and y are the coordinates of a point, and z represents the height level
of the points.There are various kinds of elements in indoor spaces such as rooms, doors, corridors, floors, stairs,
elevators and the road connection between buildings. Indoor spaces are represented by undirected graph with
nodes and edges. The various kinds of elements in indoor can be represented with modelling concept, such as :
A cell represent room, edge represent door and one or more cells with one or more edges represent corridor and
stair[4, 10].

2.2 Indoor Routing


Indoor routing system is a routing system implementation in the building[10]. By using spatial data, each space
can be accurately identified. There are various kinds of elements in indoor spaces such as rooms, doors, corridors,
doors, stairs, elevators, and the road connection between buildings. Indoor spaces are represented by undirected
graph with nodes and edges.
Due to the growing popularity of indoor location-based services, indoor data management has received sig-
nificant research attention in the past few years[15]. With the indoor mapping system, someone will be facilita-
ted in finding the target space[11]. Many studies have proven that most individuals spend their lives in indoor
environments[5]. Indoor routing application is pretty important for unfamiliar indoor spaces such as malls, air-
ports, offices, etc[8]. However, the majority of users still use manual mapping system by displaying a room map
plan in the building. Every room allows for a variety of door that connect the room with another spaces. And the
buildings can be a multi-level building that has stairs, lifts, or elevators to move from one level to another level.
The entire space must have identified labels as well as connectivity between the spaces.
From Figure 4, the indoor routing allows the routing system in three dimensional spaces that represent high
rise building[10]. In the case of indoor routing, three dimensional spaces data structure will identify an object
accurately by storing spatial data using undirected graph where x and y are the coordinates of a point on sphere, and
z represents height level of the point. Shortest path algorithm can be implemented then after the three dimensional
spaces structure was built in order to provide output of the shortest route between two points.

2.3 Indoor Trajectory


Trajectory is the path that is formed because of the moving object positioning history. Based on where it
happened, trajectory can be formed in indoor or outdoor environment. Outdoor trajectory can be constructed by
GPS technology, this technology is not sufficient to be used in indoor environment. There are some embedded
sensors in mobile devices that can be utilized to track and reconstruct trajectory in indoor environment without
utilizing GPS technology.
In the illustration of Indoor Trajectory in Figure 5, outdoor spaces has many differences from indoor spaces[5].
In indoor there are also many activities, like moving from one room to another, passing along the corridor or
Gambar 4. Indoor Routing Illustration

Gambar 5. Indoor Trajectory Illustration

gathering somewhere and these activities will create trajectory pattern. The difference lies in the formation of the
indoor environment, that is the indoor environment created or are in the buildings. Therefore, space in indoor is
limited.

2.4 Pedometer
Pedometer is one of the sensors found on a smartphone. The function of the pedometer is to help in calculating
the number of steps taken when holding the device[13]. Pedometers are now widely implemented, not only on
smartphones, but also in the form of a single device such as a watch. The pedometer starts to be used a lot because
the data provided can help determine the number of steps that are obtained and can also calculate the distance that
has been passed[12, 9]. The step meter on the smartphone can be combined with a gps system to monitor steps,
distance and with the path that has been passed. The use of a pedometer can be combined with other sensor devices
found in a smartphone.

Distance(meter) = Total Number of Step x Step Length [7]

The mathematical formula above is used to calculate the distance acquired from how many step has been
taken[7]. The formula contain the total of step has been taken and the average step length of the user. From that
calculation, the device can measure how long the distance of the user has been walking and the number of step has
been taken. The step length of the user is acquired from the average step length of the user, each user will always
have a different step length that caused by height that affect the user’s leg length.
Based on the previous work that has been done, in this study will proposed a indoor navigation guidance that
will utilize the indoor trajectory data, indoor routing system that will showing the route in indoor environment and
pedometer system for creating the guidance instruction in the application.

3. Methodology and System Design


The process to be conducted in this study are collecting research dataset and development of application sys-
tems (indoor representation, the guidance and the instruction).
3.1 Dataset
The data that is used in this study is obtained from previous research. It’s the School of Computing, Telkom
University’s spatial data. Also the trajectory pattern and the method of Dijkstra to determine the shortest path of
the route chosen.
The spatial data is a geographic data of latitude and longitude of buildings, rooms, label spaces, coordinates
and connectivity between spaces. There are two coordinates that is used in this study, longitude as for the x point
and latitude as the y point. Every coordinates that is used will determine every of each building and rooms also the
connectivity of each room.

Gambar 6. Dataset location of School of Computing, Telkom University

From the dataset, a point structure will be formed by implementing indoor representation. This implementation
will use the longitude and latitude data to be used in determining the point location of each existing room in every
building. After each point of the location of the room is implemented, the route between rooms is formed by
applying algorithms in the Android programming language.

3.2 Indoor Representation


The building that is used is the School of Computing, Telkom University. The indoor representation will
convert the floor map of the building (See Figure 7a) and put 2 nodes with different colors that symbolized different
objects of the building. The red nodes represent the room and the black nodes represent the corridors that can be
accessed (See Figure 7b). Every room (Red Node) can be accessed from the corridor (Black Dot) in that located in
front of the rooms. That is the only way to access the room because in the actual world the user must go through
a door first. The User cannot access another room without going through the corridor. Each corridor will be
interconnected when the route path is formed in accordance with the conditions to get to the selected destination.

(a) Indoor Building Floor Map (b) Indoor Object Representation in Nodes

Gambar 7. Indoor Representation


3.3 Guidance
The guidance that will be used in this application will be shown in the top box. In this part, the instruction
will be showed when the user is ready to start navigation based on when the starting point and the destination
has been chosen. To start the navigation, first, the system needs to read what is the selected start location and the
destination. The user needs to choose the buildings of the start also the destination, then choose the current user
room and the desired room to navigate as showed in the Figure 8. Each building has a number of rooms according
to the database being used. Room data used in the list of rooms in the application is only the room on the first floor
of each building. Every time the user inputted a new destination location, the start location must also be selected
because the system cannot automatically read the current location of the user.

(a) Starting Screen (b) Selection Page

Gambar 8. Guidance System

3.4 Instruction
In this section will explain the construction of the instruction that will guide the user navigation through the
route that has been chosen. The instruction will be made automatically based on the route chosen, that’s because
the program will read the route data onto each segment that needs to be passed. The segment direction and length
is the main data that needed to create the instruction. The segment direction will determine which way the user
should move based on the compass and the segment length will determine how much step is required to pass the
segment.
From the mathematical formula in [7], it can also be used to acquire the number of step by using the segment
length value and the average step length in this application.

lengthConvert = SL/(H ∗ AL) (1)

SL = Segment Length, H = User’s Height, AS = User’s Average Step Length.

With this formula, the application will calculate the number of steps that required to pass each segment that
connecting the start point to the destination. The segment length will be obtained from the segment database. In
this formula, the user’s height that will be used is 170cm and the average step length is acquired by calculating
earlier the average of taking 10 steps and divide the distance by 10. The result of the calculation should be rounded
up to prevent confusion in the number of steps gained.
The instruction automatically will be displayed in the top box of the application as showed in Figure 9 and will
always change based on the action of the user holding the device. Each time the user passes through a segment,
the instruction will change be varied based on the route that will be passed next.
(a) Compass Direction Instruction (b) Guiding Instruction

Gambar 9. Guidance Instruction System

4. Evaluation
In this section will explain about the testing analysis of this study. The result of this testing and analyzing
process will show how the performance of the application on indoor navigation guidance. The main aspect of the
testing is the accuracy of the outputs.

4.1 Testing Objective and Scenario


Based on the main aspect as the objective of experiment process is the accuracy of the application outputs, the
accuracy testing is done by conducting several experiments with different route selection and different user to see
the if there is any different accuracy output result.
As the test scenario, the test location used is the KU1 building (Grha Wiyata Cacuk Sudarijanto-A) and the
threshold value that being used in the pedometer sensor to detect step motion is 10. The height range of users for
the experiment this application are divided into 4 categories, there are 155cm, 160cm, 165cm, and 170cm. Each
of this different height will be tested to see how the height of the user will affect the accuracy of the guidance
instruction.

4.2 Testing Result

Table 1. Total Step Required Concept in One of Experiment Route

Start - Finish Height Step Required Concept


170cm 54 steps
165cm 54 steps
A102B - A107B
160cm 54 steps
155cm 54 steps

Based on the table concepts made, the number step required for one of the experiment for each different user’s
height and the step acquired for the system and the test concept should be like the table 1 described above. The
table1 above is made based on the use at height of 170cm which produce step required value is 54 steps. But based
on the experiments conducted, the results obtained show that the number of steps obtained from the application
used in real time test showing a different value than the concept created as described in the table 1.
Table 2. Real Time Test Result From One of The Experiment Route

Start - Finish Height Step Required Step Acquired (Real Time Test)
170cm 54 steps 54 steps
165cm 54 steps 55 steps
A102B - A107B
160cm 54 steps 56 steps
155cm 54 steps 58 steps

The experiment results as shown in the Table 2. show that there are factors that affect the result of the expe-
riment. There are three factors that affect the result of the experiment above are the difference in user height, the
step calculation in converting the segment length and the sensor threshold value. The different height of the user
has an affect the number of steps taken while following the guidance instruction displayed in the application. This
happens because of the influence of leg length and the value of the average step length. Differences in height indi-
cate the difference in foot distance taken, this is also influenced because the application is made based on 170cm
height user. Due to the use of a set height of 170 cm, it affects the calculations used in the system as table 3 below.

Gambar 10. One Segment on Experiment Route

In Figure 10, the red colored line is one of the segment that must be passed through that has a length of 10.6
meter. As one of the factor that affecting the calculation in the application that this segment length can resulting
different number of step as the different of user’s heigth is used in the calculation formula.

Table 3. Step Calculation in One Example Segment

Height Segment Length Calculation Step Convert


170cm 10.6 / (170 x 0.415) = 15.03 16 steps
165cm 10.6 / (165 x 0.415) = 15.49 16 steps
10.6m
160cm 10.6 / (160 x 0.415) = 15.96 16 steps
155cm 10.6 / (155 x 0.415) = 16.48 17 steps

The second factor that affects the result of the experiment is the step calculation. The calculation is based on
three main data, there is the segment length, the user’s height, and average steps length. Because of the difference
between the user that is used in the experiment, it affects the total number of step acquired are different from the
concept. In the table 3 above showing that the difference in user’s height showing that there is an influence between
the user height on the calculation formula. The difference between the results of the calculation in the formula
looks very little but it can have an impact when the calculation results are rounded up.
The calculation in the table 4 also showing that in each segment calculation resulting a different number of
step required for passing through and that makes the total step to finish on that route have different number on a
different user height.

Table 4. One of Experiment Route Calculation

Height 170cm 165cm 160cm 155cm


Segment Segment Length Step Required
A102B - CA1 5 1.22m 2 2 2 2
CA1 5 - CA1 7 2.748m 4 4 4 4
CA1 7 - CA1 8 10.056m 14 15 15 16
CA1 8 - CA1 9 3.229m 5 5 5 5
CA1 9 - CA1 22 15.93m 23 23 24 25
CA1 22 - CA1 24 2.748m 4 4 4 4
CA1 24 - A107B 1.22m 2 2 2 2
Total Step 54 55 56 58

Another causes that make the accuracy of the indoor navigation less accurate is the threshold value that is used
to set the sensitivity of the pedometer sensor to detect the step motion. In this experiment, the threshold values
that is used to detect the step motion in the application is 10. The change of threshold values will have a different
effect if added or subtracted if the threshold value is added then more motion is required for the sensor to detect
one movement step and if reduced then the required motion for the sensor to detect step will be less and the sensor
gets more sensitive.

5. Conclusion
In this paper, we proposed an indoor navigation based on the user location to its desired location by using
help in form of a guidance instruction. The guidance instruction must require a precision in determining the
calculations of steps to be performed in the application. From the experiment result, it shows that there are three
factors that can affect the accuracy performance of the indoor navigation guidance. The three-factor is the user
height, the calculation of step from converting the length of the segment and the threshold value that is used in
the application. These three factors have different effects but interconnected on the system, like the user height
will affect the calculation of the step where it is used to convert the segment length to how many steps required.
For future work, this indoor navigation guidance can be implemented into a multi-floor system, using more device
like beacon technology to help determine the user current location as when navigate following the instruction, and
converting the written instruction to oral instruction for disables people.

References
[1] S. Alamri. An efficient shortest path routing algorithm for directed indoor environments. ISPRS International
Journal of Geo-Information, 7(4):133, 2018.
[2] S. Alamri, D. Taniar, and K. Nguyen. Vertical indexing for moving objects in multifloor environments.
Mobile Information Systems, 2018, 2018.
[3] S. Alamri, D. Taniar, and M. Safar. A taxonomy for moving object queries in spatial databases. Future
Generation Computer Systems, 37:232–242, 2014.
[4] S. Alamri, D. Taniar, M. Safar, and H. Al-Khalidi. Spatiotemporal indexing for moving objects in an indoor
cellular space. Neurocomputing, 122:70–78, 2013.
[5] S. Alamri, D. Taniar, M. Safar, and H. Al-Khalidi. A connectivity index for moving objects in an indoor
cellular space. Personal and Ubiquitous Computing, 18(2):287–301, 2014.
[6] D. Andini, D. D. J. Suwawi, K. M. Adhinugraha, and S. Alamri. Adaptation of k-nearest neighbor queries
for inter-building environment. In International Conference on Computational Science and Its Applications,
pages 183–194. Springer, 2018.
[7] Y.-W. Bai, C.-H. Yu, and S.-C. Wu. Using a three-axis accelerometer and gps module in a smart phone to
measure walking steps and distance. In Electrical and Computer Engineering (CCECE), 2014 IEEE 27th
Canadian Conference on, pages 1–6. IEEE, 2014.
[8] M. Boysen, C. de Haas, H. Lu, and X. Xie. A journey from ifc files to indoor navigation. In International
Symposium on Web and Wireless Geographical Information Systems, pages 148–165. Springer, 2014.
[9] S. Crouter. Validity of 10 electronic pedometers for measuring steps, distance, and energy cost. Med Sci
Sports Exerc., 36:331–335, 2004.
[10] T. A. Dionti, K. M. Adhinugraha, and S. M. Alamri. Inter-building routing approach for indoor environment.
In International Conference on Computational Science and Its Applications, pages 247–260. Springer, 2017.
[11] L. Han, T. Zhang, and Z. Wang. The design and development of indoor 3d routing system. JSW, 9(5):1223–
1228, 2014.

[12] H. M. Husted and T. L. Llewellyn. The accuracy of pedometers in measuring walking steps on a treadmill in
college students. International journal of exercise science, 10(1):146, 2017.
[13] J. B. Martin, K. M. Krc, E. A. Mitchell, J. J. Eng, and J. W. Noble. Pedometer accuracy in slow-walking
older adults. International journal of therapy and rehabilitation, 19(7):387–393, 2012.

[14] S. Panzieri, F. Pascucci, and G. Ulivi. An outdoor navigation system using gps and inertial platform. IE-
EE/ASME transactions on Mechatronics, 7(2):134–142, 2002.
[15] Z. Shao, M. A. Cheema, D. Taniar, and H. Lu. Vip-tree: an effective index for indoor spatial queries.
Proceedings of the VLDB Endowment, 10(4):325–336, 2016.

[16] M. G. Wing, A. Eklund, and L. D. Kellogg. Consumer-grade global positioning system (gps) accuracy and
reliability. Journal of forestry, 103(4):169–173, 2005.
[17] D. Zhang, F. Xia, Z. Yang, L. Yao, and W. Zhao. Localization technologies for indoor human tracking. In
Future Information Technology (FutureTech), 2010 5th International Conference on, pages 1–6. IEEE, 2010.
Appendices

Table 5. Buildings

No Building ID Building Name


1 IF-1 Panambulai (D)
2 IF-2 Kultubai Utara (E)
3 IF-3 Kultubai Selatan (F)
4 PS-1 Pascasarjana (G)
5 KU1 Grha Wiyata Cacuk Sudarijanto-A
6 KU2 Grha Wiyata Cacuk Sudarijanto-B

Gambar 11. Grha Wiyata Cacuk Sudarijanto-A (KU1) Room Data


Gambar 12. Grha Wiyata Cacuk Sudarijanto-A (KU1) Corridor Data

Gambar 13. Grha Wiyata Cacuk Sudarijanto-A (KU1) Segment to Room


Gambar 14. Grha Wiyata Cacuk Sudarijanto-A (KU1) Segment Corridor
(a) Starting Page (b) Input Location Page

Gambar 15. Application Screenshot

(a) Location List (b) Route

Gambar 16. Application Screenshot


Indoor Navigation Guidance for Mobile Device

Supplementary Document

Final Project Thesis

1301140256
Jonathan Marihot Parulian
Table of Contents

1. Chapter I - Introduction

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Problem Statement and Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4 Writing Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Chapter II - Literature Review

2.1 Indoor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Inter-Building Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Indoor Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Indoor Trajectory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1 Global Positioning System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.2 Indoor Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Android Sensors Technology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.1 Sensor Coordinate System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.2 Motion Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.3 Environmental Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.4 Position Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.6 Device . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.7 Step Detection and Adaptive Step Length Estimation . . . . . . . . . . . . . . . . . . . . . . . .

3. Chapter III - Methodology and System Design

3.1 Collecting Data Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 Designing System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Analyzing Implementation Result Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 Application Perfomance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 Sensor Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


4. Chapter IV - Evaluation and Analysis

4.1 Testing Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Testing Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Testing Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
List of Figures

1 Outdoor Navigation and Guidance Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Indoor Navigation Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 GPS in Indoor Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Inter-Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Indoor Routing Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Indoor Trajectory Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Illustration of how GPS works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Personalized navigation direction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 Coordinate system (relative to a device) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 Indoor representation point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 Connected segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 Guidance Instruction System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 Guidance System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 One Segment on Experiment Route . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


List of Tables

1 Total Step Required Concept in One of Experiment Route . . . . . . . . . . . . . . . . . . . . . .

2 Real Time Test Result From One of The Experiment Route . . . . . . . . . . . . . . . . . . . . .

3 Step Calculation in One Example Segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 One of Experiment Route Calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Step calculation between segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Testing result (A104B to A104A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7 Testing result (A107B to A109) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Testing result (A102B to A107B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


List of Algorithms

1 Route point connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Navigation Guidance Instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Chapter I
Introduction

1.1 Introduction

Since a long ago, navigation is used to help determine position and direction. As technology develops, the

navigation technology continues to change and become more sophisticated. Many activities are also currently

utilizing the ability of navigation systems both on land, sea, and air. On land, people use the navigation to determine

the route from their location to the location they want to go. However, navigation on land can be divided into two

categories, outdoor navigation and indoor navigation. Outdoor navigation usually relied on one of the technology

devices that is Global Positioning System (GPS). Devices that have a GPS system will capture the data signal

transmitted from the satellite and be captured by the GPS signal receiver[26]. By using this GPS technology, we

can be directed to a predetermined location. The direction shown on the navigation system is formed into the

trajectory data that has been established as a usable path. One of the example of the GPS technology is Google

Map, as showed in Figure 1.

Figure 1. Outdoor Navigation and Guidance Example

Most of people spend more times inside a building. Since people spend most of their time in indoor enviro-

nments, indoor navigation service is in great public demand[35]. Unfortunately, indoor navigation cannot use GPS

technology like outdoor navigation. It is because in indoor, GPS can’t work well. Based on previous research, it

was determined that the positional accuracy using GPS are approximately 5 m of true position in open sky settings,

7 m in young forest conditions, dan 10 m under closed canopies[33]. This happens due to several things. One of

them is because of the position of the human or object is under closed canopies or inside a building, the signal will
be blocked by the building or wall. This will affect the GPS signal because it cannot go through the building or

wall. So, it will use another path to reach the object (multipath). Because of this, it will be difficult to implement

a GPS system in an indoor area because of the size of the room to be used may be less than that.

Figure 2. Indoor Navigation Example

An example of indoor navigation described in Figure 2 showing the route and the location. To develop an

indoor navigation, one that must be made is guidance. A guidance will require positioning and track down a device

with a certain positioning accuracy and reliability. This guidance will be made in the form of sequential instructions

based on the route formed. This guidance instruction will help people that will use the indoor navigation service

easier to get directions to the destination. Without this guidance instruction, a navigation system, especially indoor

navigation, will not provide its full benefits.

From the problem above, an indoor navigation would require a guidance and it will be made in the form of

sequential instructions. It aims to handle deficiency in GPS which are unreliable to be implemented in indoor. This

instruction will be made by reading the route trajectory pattern[2, 5, 14, 3, 4] obtained from previous research,

using the efficient route for indoor[1, 6] and converting it into a series of instructions for helping the indoor

navigation system.

1.2 Problem Statement and Scope

Based on the background, the Problems that occur in the indoor navigation is the need to build a guidance in

determining and indicating the exact position and direction that can not be identified by the GPS system by utilizing

the trajectory that will be constructed inside a building or room and with that trajectory, it can be used to construct

an instruction based on the route created by the trajectory data. The performance of the guidance instruction will
be perfect if the placement of the coordinate points to be read correctly and the path used in accordance with the

trajectory in the real world. This indoor navigation guidance will be useful for guiding inside a building and will

be implemented in inter-building environment of School of Computing, Telkom University’s building consisting

of D (Panambulai), E (Kultubai Utara), F (Kultubai Selatan), G (Pascasarjana) building and public engineering

prelection Telkom University’s building such as KU1 (Grha Wiyata Cacuk Sudarijanto-A) and KU2 (Grha Wiyata

Cacuk Sudarijanto-B). For this study only the first floor of each building that will be used as the location of the

indoor navigation guidance and without utilizing any GPS of the device.

1.3 Objective

This study is creating guidance that can be used to show position and direction of the indoor navigation system,

instruction that will help the navigation inside the building and discuss the analysis of direction indicators accuracy

as the status of navigation instruction. From these patterns are made instructions that will be used in indoor

navigation guidance as a result of this study.

1.4 Writing Organization

This paper is organized as follows on section II discusses about related work and previous study that used in

this case, and in third section will be explain the system adaption analysis. After that will discuss the evaluation of

this system such as testing, analysis in section IV and last of section in this paper is the conclusion of this study.
Chapter II
Literature Review

This section will be present literature review about indoors navigation with three different points of view. They

are 1) Indoor; 2) sensors technology; 3) the device.

2.1 Indoor

Today’s technology is always evolving to find new discoveries or to develop existing technologies into more

advanced ones. Likewise one of them is navigation technology that is currently being developed to be more

sophisticated. This navigation technology can be divided into two categories, outdoor navigation and indoor

navigation. One examples of outdoor navigation is Google Maps. Outdoor navigation takes advantages of Global

Positioning System (GPS), like illustrated in Figure 3a. While indoor navigation, GPS cannot be used as well as

in outdoor navigation. GPS based systems can achieve sufficient accuracy, but are unreliable indoors due to signal

interference caused by walls, floors, furniture, and other objects (See Figure 3b).

(a) How GPS works (b) GPS Limitations

Figure 3. GPS in Indoor Condition

Due to these limitations, illustrated in Figure 3, navigation inside unfamiliar buildings is still accomplished by

studying large maps posted in building lobbies and common areas [22]. There have been several studies that have

identified a technology that can be used in indoor positioning systems, such as Receive Signal Strength (RSSI)

and compressive sensing [7], RSSI and MEMS sensor [16], and Android and WLAN, But none of them has been

developed and distributed to consumers. One possibility is to install a transmitters in the building to reproduce

GPS signals. Implementation of this approach, called Pseudolite GPS, can yield high accuracy.
2.2 Inter-Building Environment

Inter-building environment is considered one of important part when constructing an indoor navigation because

in inter-building environment there are some factors that need to be considered. Inter-building may have building

with multi-floor building and indoor environment elements representation[6].

Figure 4. Inter-Building

Figure 4 illustrating the condition of inter-building environment. [14] propose the representation in indoor

space identify an object accurately by storing geographic data that are represented to undirected graph form which

has three dimensional attributes x, y, and z, where x and y are the coordinates of a point, and z represents the height

level of the points.There are various kinds of elements in indoor spaces such as rooms, doors, corridors, floors,

stairs, elevators and the road connection between buildings. Indoor spaces are represented by undirected graph

with nodes and edges. The various kinds of elements in indoor can be represented with modelling concept, such

as : A cell represent room, edge represent door and one or more cells with one or more edges represent corridor

and stair[4, 14].

2.3 Indoor Routing

Indoor routing system is a routing system implementation in the building[14]. By using spatial data, each space

can be accurately identified. There are various kinds of elements in indoor spaces such as rooms, doors, corridors,

doors, stairs, elevators, and the road connection between buildings. Indoor spaces are represented by undirected

graph with nodes and edges.

Due to the growing popularity of indoor location-based services, indoor data management has received sig-

nificant research attention in the past few years[28]. With the indoor mapping system, someone will be facilita-

ted in finding the target space[17]. Many studies have proven that most individuals spend their lives in indoor

environments[5]. Indoor routing application is pretty important for unfamiliar indoor spaces such as malls, airpor-
ts, offices, etc[9]. However, the majority of users still use manual mapping system by displaying a room map plan

in the building.

Every room allows for a variety of door that connect the room with another spaces. And the buildings can be

a multi-level building that has stairs, lifts, or elevators to move from one level to another level. The entire space

must have identified labels as well as connectivity between the spaces.

Figure 5. Indoor Routing Illustration

The indoor routing, like the illustration Figure 5, allows the routing system in three dimensional spaces that

represent high rise building[14]. In the case of indoor routing, three dimensional spaces data structure will identify

an object accurately by storing spatial data using undirected graph where x and y are the coordinates of a point on

sphere, and z represents height level of the point. Shortest path algorithm can be implemented then after the three

dimensional spaces structure was built in order to provide output of the shortest route between two points

2.4 Indoor Trajectory

Trajectory is the path that is formed because of the moving object positioning history. Based on where it

happened, trajectory can be formed in indoor or outdoor environment. Outdoor trajectory can be constructed by

GPS technology, this technology is not sufficient to be used in indoor environment. There are some embedded

sensors in mobile devices that can be utilized to track and reconstruct trajectory in indoor environment without

utilizing GPS technology. Figure 6 illustrating the construction of indoor trajectory.

Outdoor spaces has many differences from indoor spaces[5]. In indoor there are also many activities, like mo-

ving from one room to another, passing along the corridor or gathering somewhere and these activities will create

trajectory pattern. The difference lies in the formation of the indoor environment, that is the indoor environment

created or are in the buildings. Therefore, space in indoor is limited.


Figure 6. Indoor Trajectory Illustration

2.4.1 Global Positioning System

The research about GPS has been done about some decades ago. In 1986, the mariners [20] have been done

research about the accuracy of GPS. At the time, the accuracy of GPS is still 100 m from the real object. Times

are growing. Technologies and research are also evolved. The latest research [33] said that the accuracy of GPS is

divided into three categories. The categories are determined from the condition of the circumstances surrounding

humans. The conditions are open sky settings, young forest, and under closed canopies. Based on previous

research, it was determined that the positional accuracies using GPS are approximately 5 m of true position in

open sky settings, 7 m in young forest conditions, dan 10 m under closed canopies.

This Figure 7 shows the illustrations about how GPS works. User accuracy depends on a combination of

satellite geometry, URE, and local factors such as signal blockage, atmospheric conditions, and receiver design

features/quality.

Figure 7. Illustration of how GPS works

Those accuracies are affected by:

• Satelite signal blockage due to buildings, walls, trees, etc.


• Indoor or underground use

• Signals reflected off buildings or walls (”multipath”)

• Radio Interference

• Major solar storms

• Satellite maintenance/manuvers creating temporary gaps in coverage

• Devices that do not comply with GPS Interface Specifications

2.4.2 Indoor Map

Navigation applications that find optimal routes and corresponding turn-by-turn directions in road networks

are oneof the fundamental and most used applications in wide variety of domains [23]. Meanwhile, with the

ever-growing usage of navigation applications in mobile devices and car-navigation systems, a plethora of user

generated trajectory data became available. These data are particularly useful for producing more effective and

cognitive turn-by-turn directions.

Figure 8. Personalized navigation direction


Figure 8 shows an example of personalized navigation directions of a particular path. Figure 1(a) and Figure

1(b) illustrate the route provided by a navigation system, i.e., the red line from point A to point B, and correspon-

ding turn-by-turn navigation directions. The turn-by-turn directions shown in Figure 1(b) are computed by taking

into account inherent cost measures (i.e., distance and/or travel time) and turn angles (e.g., left or right) between

the edges of the underlying road network.

From the example above, shows how navigation direction is used in outdoor navigation. However, when it

comes to indoor navigation, the example will be difficult to display. This is because indoor maps will be different

from outdoor maps and can not be directly shaped by different types of navigation services. The maps must be

made separately and the paths that can be used should be formed according to the paths on the indoor map. Speed

and travel time will not be too influential in the indoor map, because when we are in the room is not required to

calculate the speed or show travel time based on distance.

2.4.3 Conclusion

From the explanation above, indoor navigation isn’t supported yet by GPS. The reason why GPS does not

support is because the small accuracy and some limitations that given when human is in indoor building. That

small accuracy is affected by many causes, the signal blockage due to the buildings walls, floors, furniture, and

any other objects. Due to the inadequate use of GPS in the room, an indoor map is needed to determine the path

that can be used as an indoor navigation path. This will help in making the right guidance when going to run

indoor navigation. So in this project, GPS will not be used as technology to make indoor navigation guidance and

indoor maps used will utilize existing map data.

2.5 Android Sensors Technology

Most Android based smartphones come equipped with a number of hardware and software sensors, including

sensors for motion measurement, orientation detection, as well as environmental monitoring [34]. These sensors

help the device to detect the specific events and converts it to signal according to the systematic rules, which are

usually the mathematic rules. In other words, sensor is a detective device which inspects the measured information

and converts it to available output that can be recognized by smartphones. Sensor availability varies from device to

device, it can also vary between Android versions. This is because the Android sensors have been introduced over

the course of several platform releases. In this subsection, the availability of sensors is compared on API level 14,

level 9, level 8, and level 3.


2.5.1 Sensor Coordinate System

In general, the sensor framework uses a standard 3-axis coordinate system to express data values. For most

sensors, the coordinate system is defined relative to the device’s screen when the device is held in its default

orientation (See Figure 9).

Figure 9. Coordinate system (relative to a device)

When a device is held in its default orientation, the X axis is horizontal and points to the right, the Y axis is

vertical and points up, and the Z axis points toward the outside of the screen face . In this system, coordinates

behind the screen have negative Z values. This coordinate system is used by the following sensors:

1. Acceleration sensor

2. Gravity sensor

3. Gyroscope

4. Linear acceleration sensor

5. Geomagnetic sensor

The most important point to understand about this coordinate system is that the axes are not swapped when the

device’s screen orientation changes—that is, the sensor’s coordinate system never changes as the device moves.

This behavior is the same as the behavior of the OpenGL coordinate system. Another point to understand is that

your application must not assume that a device’s natural (default) orientation is portrait. The natural orientation

for many tablet devices is landscape. And the sensor coordinate system is always based on the natural orientation

of a device.
2.5.2 Motion Sensor

This sensor let the device to monitor the motion of the device when being held or placed by the user. It can

measure the acceleration and rotation of a device by using the accelerometers and gyroscope [34]. Motion sensors

are useful for monitoring device movement, such as tilt, shake, rotation, or swing. The movement is usually a

reflection of direct user input (for example, a user steering a car in a game or a user controlling a ball in a game),

but it can also be a reflection of the physical environment in which the device is sitting (for example, moving with

you while you drive your car). All of the motion sensors will return a multi-dimensional arrays of sensor value for

each sensor event.This value can be aquired by using the parameters that are available on the Android platform.

Accelerometer

Accelerometer measures the acceleration force in m/s2 that is applied to a device on all three physical axes (x,

y, and z), including the force of gravity. The common uses of this sensor is on motion detection such as shake, tilt,

rotation or swing. Accelerometer is available on API level 14, level 9, level 8, and level 3.

Gravity Sensor

The gravity sensor provides a three dimensional vector indicating the direction and magnitude of gravity. It

measures the force of gravity in m/s2 that is applied to a device on all three physical axes (x, y, z). The common

uses of this sensor is on motion detection such as shake, tilt, rotation or swing. This sensor is only available on API

level 14 and level 9. Gravity sensor looks like accelerometer. There’s just one difference between those sensors.

Accelerometer is not only measuring the acceleration force, but also including force of gravity.

Gyroscope

Gyroscope measures a device’s rate of rotation in rad/s around each of the three physical axes (x, y, and z). The

common uses of this sensor is on rotation detection such as spin, turn, etc. Many games interaction use this sensor

to make the user feel the real sensation of the games. Gyroscope is only available on API level 14 and level 9.

Rotational Vector Sensor

The rotational vector sensor is particularly versatile and can be used for a wide range of motion-related tasks,

such as detecting gestures, monitoring angular change, and monitoring relative orientation changes. The gravity

sensor provides a three dimensional vector indicating the direction and magnitude of gravity. Typically, this sensor

is used to determine the device’s relative orientation in space. Type of this sensor is software or hardware. It is

only available on API level 14 and level 9.


2.5.3 Environmental Sensor

The enviromental sensors can measure various environmental parameters, such as ambient air temperature and

pressure, illumination, and humidity. This category includes barometers, photometers, and thermometers.

Ambient Temperature

Ambient temperature measures the ambient room temperature in degrees Celsius (◦C). The type of this sensor

is hardware. This sensor is only availabe on API level 14.

Light Sensor

Light sensor measures the ambient light level (illumination) in lx. The common uses of this sensor is to adjust

or controlling screen brightness. The type of this sensor is hardware. Light sensor is available on all API level.

Proximity

It measures the proximity of an object in cm relative to the view screen of a device. This sensor is typically

used to determine whether a handset is being held up to a person’s ear. Actually, proximity also implements light

sensor. While the handset is being held up to a person’s ear, there will be no light. It causes the mobile device

screen turns off. Proximity is available on all API level.

2.5.4 Position Sensor

The Android platform provides two sensors that let you determine the position of a device: the geomagnetic

field sensor and the accelerometer. These sensors measure the physical position of a device. This category includes

orientation sensors and magnetometers. Position sensors are useful for determining a device’s physical position in

the world’s frame of reference [34].

Orientation Sensor

Orientation sensor measures degrees of rotation that a device makes around all three physical axes (x, y, z). As

of API level 3 we can obtain the inclination matrix and rotation matrix for a device by using the gravity sensor and

the geomagnetic field sensor in conjunction with the getRotationMatrix() method. It common uses on determining

device position. Type of orientation sensor is software. Actually, this sensor is available on all API level. But now,

it’s been deprecated and only available on API level 3.

Magnetometers

Magnetometer measures the ambient geomagnetic field for all three physical axes (x, y, z) in µT . It common

uses on creating a compass. The type of this sensor is hardware. This sensor is available on all API level.
Pedometer Pedometer is one of the sensors found on a smartphone. The function of the pedometer is to help in

calculating the number of steps taken when holding the device[24]. Pedometers are now widely implemented, not

only on smartphones, but also in the form of a single device such as a watch. The pedometer starts to be used a

lot because the data provided can help determine the number of steps that are obtained and can also calculate the

distance that has been passed[18, 11]. The step meter on the smartphone can be combined with a gps system to

monitor steps, distance and with the path that has been passed. The use of a pedometer can be combined with other

sensor devices found in a smartphone.

Distance(meter) = Total Number of Step x Step Length [8]

The mathematical formula above is used to calculate the distance acquired from how many step has been

taken[8]. The formula contain the total of step has been taken and the average step length of the user. From that

calculation, the device can measure how long the distance of the user has been walking and the number of step has

been taken. The step length of the user is acquired from the average step length of the user, each user will always

have a different step length that caused by height that affect the user’s leg length.

2.5.5 Conclusion

Android platform supports three broad categories of sensors, they are motion sensors, environmental sensors,

and position sensors. Motion sensors and position sensors are the most important for this project. Both of them

can be used to create the trajectory pattern and from that we can build the guidance for this project objective. The

main sensors involved in the process of making the trajectory pattern are the accelerometer and magnetometer.

Accelerometer is used to detect the motion of people while they walk and the magnetometer is used to determine

the direction by creating a compass. With both sensors, the results of guidance based on the existing path will be

directly tested to measure the accuracy of the position and direction shown.

2.6 Device

Many people use mobile devices to navigate when they want to go to a location. Some researchers has explai-

ned the advantages of mobile device in the use for navigation device [21, 12, 13]. They are:

1. The build-in sensors. With the availability of built-in sensors in the device, the users are not required to use

external sensors in order to collect needed information. The flexibility and readiness of the smartphone as a

sensor device are seen as advantages.


2. High processing power and memory. Most smartphones have relatively high processing power and sufficient

memory for data processing tasks. They also contain more than adequate storage space to store data and

computed information. The smartphones also provide communication possibilities that allow information

exchange between user and external services. The smartphone itself can be seen as a small computing device

with common connectivity integrated.

3. A smartphone is likely to be with a user during his daily activities. It can be seen as a natural choice of

a non-obtrusive device. The chances of users feeling awkward or uncomfortable will be much lower as

compared to approaches that affect the usage habits of the users.

4. Long operation duration. For an average user, under normal usage patterns (some daily phone conversations

and text messages), a smartphone should have at least a day’s operation time before a recharge is required.

With proper management for sensor data polling, a whole day sensor data collection is achievable.

2.7 Step Detection and Adaptive Step Length Estimation

The study of step detection algorithm based on accelerometers and gyroscopes in cooperation with Kalman

filter were presented in Garcia[15], Opiela [25], and Tran[31]. There is a study where it developed the indoor

navigation system based on PDR (Pedestrian Dead Reckoning) using various sensors in smart phone with help of

the Artificial Neuron Network to recognize the walking status such as stop, walking, and running and to estimate

the step length [29].

In some previous works, there are an adaptive length estimation using optimal parameters where the movement

status awareness was used [30, 32]. There is also research that calculating the variable that amplitude the threshold

for curret position of the user [27].

The movement of a person is a specific type of a periodic mechanical movement which can be divided into

individual steps. The step detection is most often realized by measuring of the acceleration . There are several

methods for the detection of steps : detection of the peaks, zero-crossings and flat zone detection. In the previous

research, the detection of the peaks method often to be used in measuring the acceleration. To eliminate false

detected step, it is necessary to define the threshold above which the searched maximum as well as the minimum

time interval between peaks should be detected [19].

The flat zone detection is the less used method because this method identifies the beginning of the step as a flat

zone in the time series of measured acceleration. By this method the sensor has to be placed directly on the leg of
a pedestrian [10].

In the presented article there is used the step detection method based on the zero-crossing of the acceleration

standard. These zero-crossings are later used in the method of adaptive step length estimation. Acceleration norm

(1) represents the resultant vector of the sensor acceleration. By defining of thresholds for the acceleration norm

(2) there are identified areas of movement where the step detection can be used. The low-pass filter (moving

average) is applied on the acceleration norm to suppress the noise and reduce the probability of the detection of

false steps. Each step has three zero-crossings. This fact is taken into an account by estimating the adaptive step

length:
q
α= αx2 + αy2 + αz2 , (1)

α < th α,

where

α − acceleration norm

αx , αy , αz − acceleration in axis X,Y,Z

th α − threshold for the acceleration norm.

Step detection method based on a zero-crossing is resistant to changes in the speed of a pedestrian which

becomes evident in changes in local maxima in the acceleration norm.


Chapter III
Methodology and System Design

3.1 Collecting Data Scenario

Source of data to be used in this research is coordinate data to be used as marking the point location of each

building, room, corridor and segment that obtained from previous research. In this study, guidance will be built to

help indoor navigation. This guidance will only be made based on route path from the connection of each segments

and does not add, alter or create new paths.

There are several ways or methods to make this guidance. They are by using ISS services and determining

indoor mapping with detailed Points-Of-Interest (POI). This study will use ISS service to help to create the indoor

representation and POI for indicating each point as room and corridor that can be accessed. The guidance will

showing the direction of each route from each segments that implemented from the data. The route will follow the

building or room that is in Telkom University.

3.2 Designing System

A part of design system is designing data structure. Data structure is needed in this experiment to store some

values. They are number of step, direction that obtained from compass value, date, and experiment identity. It can

be changed according to the result of collecting data, whether weight and height will affect the length of foot step

or not.

The indoor mapping will be implemented by using Android Studio as for help developing the application.

From the data that obtained, coordinate data like longitude and latitude data will be converted into a point that

illustrating the room and corridor that exist in each building that being used in this study. The coordinate data is

stored in the database along with the other type of data such like the data ID, name of every room, the segments of

every connected room and corridor, and length of connecting segments.

The Points that represent each room and corridor that exist in the building in Telkom University that being used

for this study is implemented using Google Maps as the platform base, see Figure 10.
Figure 10. Indoor representation point

The connecting process of each point to be a segments will be done when the starting point and the destination

has been selected. This figure 11 below show the connected segments is added in the application.

Figure 11. Connected segments

The algorithm that used to put the point that represent indoor location of each room and corridor is using the

Latitude and Longitude data. The result by using this algorithm is the colored red dot represents room and the

black dot represents the corridor that can be accessed like the figure 11 above. This algorithm process by dividing

between room and corridor data and registered it into different array list, then this array list will be accessed to

draw the room and corridor point and described in different color to show which one is room or corridor.
Algorithm 1: Route point connections
Data: Starting Point and Destination Selected
Result: Route of each segment connected
1 initialization;
2 foreach Vertex do
3 if Vertex ID = subString ”C” then
4 add Corridor data to ArrayList
5 else
6 add Room data to ArrayList
7 end
8 end
9 foreach Route do
10 draw point based on Latitude Longitude room/corridor data
11 end

For connecting the starting point and the destination, First the starting point and destination must be selected,

then check every segment that can connect to the starting room and destination room, then check every segment

data where the connection between the corridors has been determined. The path arrangement will be determined

from the connections of each segment that can be accessed based on the existing segment data that can connect the

starting room and destination room.

The next thing needed is the guidance instruction. This instruction created by processing the route direction,

converting the length of the segment into steps needed, and move the position marker as it passes after one segment

route. The instruction will be made automatically based on the route chosen, that’s because the program will read

the route data onto each segment that needs to be passed. The segment direction and length is the main data that

needed to create the instruction. The segment direction will determine which way the user should move based on

the compass and the segment length will determine how much step is required to pass the segment.

From the mathematical formula in [8], it can also be used to acquire the number of step by using the segment

length value and the average step length in this application.

lengthConvert = SL/(H ∗ AL) (2)

SL = Segment Length, H = User’s Height, AS = User’s Average Step Length.

With this formula, the application will calculate the number of steps that required to pass each segment that

connecting the start point to the destination. The segment length will be obtained from the segment database. In

this formula, the user’s height that will be used is 170cm and the average step length is acquired by calculating

earlier the average of taking 10 steps and divide the distance by 10. The result of the calculation should be rounded

up to prevent confusion in the number of steps gained.


(a) Compass Direction Instruction (b) Guiding Instruction

Figure 12. Guidance Instruction System

The instruction automatically will be displayed in the top box of the application and will always change based

on the action of the user holding the device, like showed in Figure 12. Each time the user passes through a segment,

the instruction will change be varied based on the route that will be passed next.

In this algorithm, the segment length data need to be converted to how many number of step required to pass

the segment. This process takes place continuously as long as the program reads that there is still a segment that

needs to be accessed after passing one segment until the program reads that the next segment is the relationship

between the corridor and the destination room.

Algorithm 2: Navigation Guidance Instruction


Data: Segment length, Route Direction
Result: Guidance instruction
1 initialization;
2 segmentlength ←− LengthSegmentData;
0
3 lengthConvert ←− Round(segmentlength/(user sheight ∗ 0.415));
4 if move segment = TRUE then numSteps = 0;
5 if numsteps < lengthConvert then
6 if Compass direction 6= RouteDirectionData then
7 Print (Head to ...);
8 else
9 Print (Take ... Step Foward);
10 end
11 else
12 CurrentPosition ←− NextPosition;
13 Move marker to current position;
14 movesegment ←− T RUE;
15 end
The method of the algorithm is run in a loop as long as the sensor keeps reading the movement or the sensor

is still active when the application is run. This method utilizes both the two sensors that are implemented in

this application because in this algorithm takes the number of steps taken during the move following the guidance

instruction and also the direction directed by the device when the user is moving. If the command to start navigation

has not been executed, the sensor used will not actively read the user’s movement until the command to start

navigation is executed. That’s when the sensor processes and reads the movement of the device and will affect the

instruction guidance in this application.

In the route selection page, each room will be displayed in each building based on different building options.

Data from each room is directly accessed from the database used. Selection of starting room and goal room are

made separately in order to facilitate the selection of routes and the execution process shows the route path of

the starting room and the selected destination. This figure 13 below show how the route selection page will be

designed.

(a) Starting Screen (b) Input Location Page

Figure 13. Guidance System

3.3 Analyzing Implementation Result Scenario

In analyzing implementation result scenario, it will be analyzed about the performance of the application.
3.3.1 Application Perfomance

One of the ways to determine whether the application successful or not is by measure the right metrics. In this

experiment, performance metrics is used to measure the successful of the application. Performance metrics focus

on how the user is experiencing the application. Performance metrics include are:

1. Application Crashes. Everyone who uses mobile apps has experienced crashes at some point. Crash rate is

the average crashes per app loads (an app load is the launch of an app). The typical crash rate is 1-2%, but

this varies widely depending on the type of app, its usage, maturity, etc.

2. API Latency. Apps of today leverage several API’s or services. Latency refers to the round-trip time from a

request to a response. The general rule of thumb is to optimize to around 1 second response time.

3. End-to-end application latency. It’s not just enough to track API latencies; you also need end-to-end response

time to applications that are powering the API’s. Users may have some tolerance for slower response times,

but the data generally shows that anything over 3-4 seconds total response time and the majority of user

(60% or greater) will abandon the transaction and may even delete your app altogether.

4. Application load period. This metric is related to the number of transactions or calls over a certain period of

time. It is critical because you want to make sure that as the load increases, your application performance

doesn’t degrade.

3.3.2 Sensor Performance

Another thing to note in order to determine the accuracy level of the application in helping to provide indoor

navigation guidance instructions is the performance of the sensors used in this application. Sensors utilized in

this application are accelerometer and magnetometer sensors. Both sensors are assigned in two different ways but

determine the accuracy of the navigation of this application.

The accelerometer sensor is used to detect movement of footsteps which will help calculate the number of steps

taken during movement following the guided navigation instructions shown. This sensor has a threshold value that

will determine the sensor threshold in detecting vibrations against the device as the user moves. This threshold

value must be adjusted based on the sensitivity required by the user as it will affect the process of navigating the

way if it is less sensitive or too sensitive.

The magnetometer sensor is used to implement compass movement in this application. This sensor reads the
magnetic field to indicate the direction of the poles as a compass work. With this sensor, this application can take

advantage of these sensors to help indicate the direction that needs to be addressed when navigating indoors.
Chapter IV
Evaluation

In this section will explaining about testing analysis of this study. The result of this testing and analyzing

process will show how performance of the application on indoor navigation guidance. The main aspect of the

testing is the accuracy of the outputs.

4.1 Testing Objective

Based on the main aspect as the objective of testing process is the accuracy of the application outputs, the

accuracy testing is done by conducting several experiments with different route selection to achieve different

accuracy output result. The thing that will affect the accuracy of this application testing is the user’s height. The

height will be used in this testing will be categorized in several ranges.

4.2 Testing Scenario

As the test scenario, the test location used is the KU1 building (Grha Wiyata Cacuk Sudarijanto-A) and the

threshold value that being used in the accelerometer sensor to detect step motion is 10. The selected test targets are

some students with different height categories try to follow the guidance shown in the application. The aim of the

accuracy test is to see how precisely the guidance provided by the app from start location to destination by testing

from different student and doing different route selection.

4.3 Testing Result

Table 1. Total Step Required Concept in One of Experiment Route

Start - Finish Height Step Required Concept


170cm 54 steps
165cm 54 steps
A102B - A107B
160cm 54 steps
155cm 54 steps

Based on the table concepts made, the number step required for one of the experiment for each different user’s

height and the step acquired for the system and the test concept should be like the table 1 described above. The

table1 above is made based on the use at height of 170cm which produce step required value is 54 steps. But based

on the experiments conducted, the results obtained show that the number of steps obtained from the application

used in real time test showing a different value than the concept created as described in the table 1.
Table 2. Real Time Test Result From One of The Experiment Route

Start - Finish Height Step Required Step Acquired (Real Time Test)
170cm 54 steps 54 steps
165cm 54 steps 55 steps
A102B - A107B
160cm 54 steps 56 steps
155cm 54 steps 58 steps

The experiment results as shown in the Table 2. show that there are factors that affect the result of the expe-

riment. There are three factors that affect the result of the experiment above are the difference in user height, the

step calculation in converting the segment length and the sensor threshold value. The different height of the user

has an affect the number of steps taken while following the guidance instruction displayed in the application. This

happens because of the influence of leg length and the value of the average step length. Differences in height indi-

cate the difference in foot distance taken, this is also influenced because the application is made based on 170cm

height user. Due to the use of a set height of 170 cm, it affects the calculations used in the system as table 3 below.

Figure 14. One Segment on Experiment Route

In Figure 14, the red colored line is one of the segment that must be passed through that has a length of 10.6

meter. As one of the factor that affecting the calculation in the application that this segment length can resulting

different number of step as the different of user’s heigth is used in the calculation formula.

The second factor that affects the result of the experiment is the step calculation. The table 3 showing that the

result of the calculation formula by using one of the segment in experiment route (See Figure 14) has a different
Table 3. Step Calculation in One Example Segment

Height Segment Length Calculation Step Convert


170cm 10.6 / (170 x 0.415) = 15.03 16 steps
165cm 10.6 / (165 x 0.415) = 15.49 16 steps
10.6m
160cm 10.6 / (160 x 0.415) = 15.96 16 steps
155cm 10.6 / (155 x 0.415) = 16.48 17 steps

value. The calculation is based on three main data, there is the segment length, the user’s height, and average steps

length. Because of the difference between the user that being used in the experiment, like the 3 described, it affects

the total number of step acquired are different from the concept.

The calculation in the table 4 show that in each segment calculation resulting a different number of step required

for passing through and that makes the total step to finish on that route have different number on a different user

height.

Table 4. One of Experiment Route Calculation

Height 170cm 165cm 160cm 155cm


Segment Segment Length Step Required
A102B - CA1 5 1.22m 2 2 2 2
CA1 5 - CA1 7 2.748m 4 4 4 4
CA1 7 - CA1 8 10.056m 14 15 15 16
CA1 8 - CA1 9 3.229m 5 5 5 5
CA1 9 - CA1 22 15.93m 23 23 24 25
CA1 22 - CA1 24 2.748m 4 4 4 4
CA1 24 - A107B 1.22m 2 2 2 2
Total Step 54 55 56 58

Another causes that make the accuracy of the indoor navigation less accurate is the threshold value that is used

to set the sensitivity of the pedometer sensor to detect the step motion. In this experiment, the threshold values

that is used to detect the step motion in the application is 10. The change of threshold values will have a different

effect if added or subtracted if the threshold value is added then more motion is required for the sensor to detect

one movement step and if reduced then the required motion for the sensor to detect step will be less and the sensor

gets more sensitive.

4.4 Analysis

From the experiment result, there are different results of the guidance testing of the application. This happens

because of influence of the calculation of steps made in the application when showing guidance to be followed.

The calculations in the application are made based on user height and the height are multiplied by 0.415 if male

and 0.413 if female. The result of the calculation will result in a step length value in centimeters.
The step length difference will affect the number of steps required to reach the destination location and that

will cause the calculation of the distance between segments and the number of steps required in each segment of

the existing route will be different. For example from the route A104B to A104A there is a segment with length

of 10.6m.

Table 5. Step calculation between segment

Height Segment Length Calculation Step Convert


170cm 10.6 / (170 x 0.415) = 15.03 15 step
165cm 10.6 / (165 x 0.415) = 15.49 15 step
10.6m
160cm 10.6 / (160 x 0.415) = 15.96 16 step
155cm 10.6 / (155 x 0.415) = 16.48 16 step

From Table 5. it shows that the height will affect the step calculation that required in each segment. The

difference in the value of the calculation will also affect the accuracy of the guidance given. The number of steps

required for each segment will vary based on the user’s height and will be more influential as the route of the

segment passes the more and the longer the distance.

Table 6. Testing result (A104B to A104A)

Height 170cm 165cm 160cm 155cm


Segment Segment Length Step Required
A104B - CA1 16 1.22m 2 2 2 2
CA1 16 - CA1 17 10.6m 15 15 16 16
CA1 17 - A104A 1.22m 2 2 2 2
Total Step 19 19 20 20

Table 7. Testing result (A107B to A109)

Height 170cm 165cm 160cm 155cm


Segment Segment Length Step Required
A107B - CA1 24 1.22m 2 2 2 2
CA1 24 - CA1 22 2.748m 4 4 4 4
CA1 22 - CA1 9 15.93m 23 23 24 25
CA1 9 - CA1 11 2.748m 4 4 4 4
CA1 11 - A109 1.22m 2 2 2 2
Total Step 35 35 36 37
Table 8. Testing result (A102B to A107B)

Height 170cm 165cm 160cm 155cm


Segment Segment Length Step Required
A102B - CA1 5 1.22m 2 2 2 2
CA1 5 - CA1 7 2.748m 4 4 4 4
CA1 7 - CA1 8 10.056m 14 15 15 16
CA1 8 - CA1 9 3.229m 5 5 5 5
CA1 9 - CA1 22 15.93m 23 23 24 25
CA1 22 - CA1 24 2.748m 4 4 4 4
CA1 24 - A107B 1.22m 2 2 2 2
Total Step 54 55 56 58

From the calculation of each segment in three different route, Table 6, 7 and 8, showing that the length of each

segment in the route that were chosen do have affecting the step required to pass the segment, it also affected by

the height of the users. The shorter the user height of the height values used in the application, the more likely it

will affect the difference in the number of steps required when going through the segment that is in the selected

route.

The threshold values set in this app are tailored to the user’s height of 170cm. Therefore, the effect of deter-

mining the threshold value that makes the sensitivity of the accelerometer sensor in reading footstep movements

makes it possible to have a difference if the user’s height does not match the threshold value.
References

[1] S. Alamri. An efficient shortest path routing algorithm for directed indoor environments. ISPRS International

Journal of Geo-Information, 7(4):133, 2018.

[2] S. Alamri, D. Taniar, and K. Nguyen. Vertical indexing for moving objects in multifloor environments.

Mobile Information Systems, 2018, 2018.

[3] S. Alamri, D. Taniar, and M. Safar. A taxonomy for moving object queries in spatial databases. Future

Generation Computer Systems, 37:232–242, 2014.

[4] S. Alamri, D. Taniar, M. Safar, and H. Al-Khalidi. Spatiotemporal indexing for moving objects in an indoor

cellular space. Neurocomputing, 122:70–78, 2013.

[5] S. Alamri, D. Taniar, M. Safar, and H. Al-Khalidi. A connectivity index for moving objects in an indoor

cellular space. Personal and Ubiquitous Computing, 18(2):287–301, 2014.

[6] D. Andini, D. D. J. Suwawi, K. M. Adhinugraha, and S. Alamri. Adaptation of k-nearest neighbor queries

for inter-building environment. In International Conference on Computational Science and Its Applications,

pages 183–194. Springer, 2018.

[7] A. W. S. Au, C. Feng, S. Valaee, S. Reyes, S. Sorour, S. N. Markowitz, D. Gold, K. Gordon, and M. Eizenman.

Indoor tracking and navigation using received signal strength and compressive sensing on a mobile device.

IEEE Transactions on Mobile Computing, 12(10):2050–2062, 2013.

[8] Y.-W. Bai, C.-H. Yu, and S.-C. Wu. Using a three-axis accelerometer and gps module in a smart phone to

measure walking steps and distance. In Electrical and Computer Engineering (CCECE), 2014 IEEE 27th

Canadian Conference on, pages 1–6. IEEE, 2014.

[9] M. Boysen, C. de Haas, H. Lu, and X. Xie. A journey from ifc files to indoor navigation. In International

Symposium on Web and Wireless Geographical Information Systems, pages 148–165. Springer, 2014.

[10] S. Y. Cho, K. W. Lee, C. G. Park, and J. G. Lee. A personal navigation system using low-cost

mems/gps/fluxgate. 2003.

[11] S. Crouter. Validity of 10 electronic pedometers for measuring steps, distance, and energy cost. Med Sci

Sports Exerc., 36:331–335, 2004.


[12] B. L. Davis, T. F. Rodriguez, and S. T. Shivappa. Mobile device indoor navigation, Feb. 25 2014. US Patent

8,660,581.

[13] A. Dietrich, H. Schmidt, and J.-P. Hathout. Orientation and navigation for a mobile device using inertial

sensors, Dec. 13 2005. US Patent 6,975,959.

[14] T. A. Dionti, K. M. Adhinugraha, and S. M. Alamri. Inter-building routing approach for indoor environment.

In International Conference on Computational Science and Its Applications, pages 247–260. Springer, 2017.

[15] P. Garcia and W. Li. On indoor positioning for mobile devices. Department of Signals and Systems, Chalmers

University of Technology, page 59, 2011.

[16] D. Grzechca, T. Wróbel, and P. Bielecki. Indoor localization of objects based on rssi and mems sensors.

In Communications and Information Technologies (ISCIT), 2014 14th International Symposium on, pages

143–146. IEEE, 2014.

[17] L. Han, T. Zhang, and Z. Wang. The design and development of indoor 3d routing system. JSW, 9(5):1223–

1228, 2014.

[18] H. M. Husted and T. L. Llewellyn. The accuracy of pedometers in measuring walking steps on a treadmill in

college students. International journal of exercise science, 10(1):146, 2017.

[19] L. Ilkovičová, P. Kajánek, and A. Kopáčik. Pedestrian indoor positioning and tracking using smartphone

sensors, step detection and map matching algorithm. In International Symposium on Engineering Geodesy,

pages 20–22, 2016.

[20] M. Kumar and G. A. Maul. International symposium on marine positioning. Bulletin géodésique, 61(3):293–

295, 1987.

[21] S. L. Lau and K. David. Movement recognition using the accelerometer in smartphones. In Future Network

and Mobile Summit, 2010, pages 1–9. IEEE, 2010.

[22] M. H. V. Le, D. Saragas, and N. Webb. Indoor navigation system for handheld devices. Worcester Polytechnic

Institute, Worcester (October 22, 2009), 2009.

[23] Y. Li, H. Su, U. Demiryurek, B. Zheng, T. He, and C. Shahabi. Pare: A system for personalized route guidan-

ce. In Proceedings of the 26th International Conference on World Wide Web, pages 637–646. International

World Wide Web Conferences Steering Committee, 2017.


[24] J. B. Martin, K. M. Krc, E. A. Mitchell, J. J. Eng, and J. W. Noble. Pedometer accuracy in slow-walking

older adults. International journal of therapy and rehabilitation, 19(7):387–393, 2012.

[25] M. Opiela. Localization with the use of the accelerometer and compass. University of Pavol Jozef Šafárik in

Košice, Košice (In Slovak), 2013.

[26] S. Panzieri, F. Pascucci, and G. Ulivi. An outdoor navigation system using gps and inertial platform. IE-

EE/ASME transactions on Mechatronics, 7(2):134–142, 2002.

[27] U. Ryu, K. Ahn, E. Kim, M. Kim, B. Kim, S. Woo, and Y. Chang. Adaptive step detection algorithm for

wireless smart step counter. In Information Science and Applications (ICISA), 2013 International Conference

on, pages 1–4. IEEE, 2013.

[28] Z. Shao, M. A. Cheema, D. Taniar, and H. Lu. Vip-tree: an effective index for indoor spatial queries.

Proceedings of the VLDB Endowment, 10(4):325–336, 2016.

[29] B. Shin, J. H. Lee, H. Lee, E. Kim, J. Kim, S. Lee, Y.-s. Cho, S. Park, and T. Lee. Indoor 3d pedestrian

tracking algorithm based on pdr using smarthphone. In Control, Automation and Systems (ICCAS), 2012

12th International Conference on, pages 1442–1445. IEEE, 2012.

[30] S. Shin, C. Park, J. Kim, H. Hong, and J. Lee. Adaptive step length estimation algorithm using low-cost

mems inertial sensors. In Sensors Applications Symposium, 2007. SAS’07. IEEE, pages 1–5. IEEE, 2007.

[31] K. Tran, T. Le, and T. Dinh. A high-accuracy step counting algorithm for iphones using accelerometer.

In Signal Processing and Information Technology (ISSPIT), 2012 IEEE International Symposium on, pages

000213–000217. IEEE, 2012.

[32] J. Wang, X. Lee, L. Yu, and L. Guo. A method of walking parameters estimation via 3-axis accelerometer.

In Orange Technologies (ICOT), 2013 International Conference on, pages 298–301. IEEE, 2013.

[33] M. G. Wing, A. Eklund, and L. D. Kellogg. Consumer-grade global positioning system (gps) accuracy and

reliability. Journal of forestry, 103(4):169–173, 2005.

[34] Y. Yan, S. Cosgrove, E. Blantont, S. Y. Ko, and L. Ziarek. Real-time sensing on android. In Proceedings of

the 12th International Workshop on Java Technologies for Real-time and Embedded Systems, page 67. ACM,

2014.
[35] D. Zhang, F. Xia, Z. Yang, L. Yao, and W. Zhao. Localization technologies for indoor human tracking. In

Future Information Technology (FutureTech), 2010 5th International Conference on, pages 1–6. IEEE, 2010.

You might also like