| LBS | |
Mobile application based indoor positioning and navigational system using Dijkstra’s algorithm
The proposed method is implemented in our college academic block and the experimental results show that our navigation method is feasible and effective |
 |
|
|
|
|
|
Abstract
This paper offers a method for developing an efficient indoor navigation system with the consideration of the shortest path between source and destination. The challenge for the indoor navigation system is to provide personal navigation information and the optimal route. Applications of indoor navigation systems need consideration of the Shortest Path problem. The shortest pathways can be used to find solutions to the current problems using Dijkstra’s algorithm. Based on the issue with the indoor navigation system, the shortest way and the best path are calculated. This is crucial to navigation systems since it can aid in making wise decisions and time-saving choices. The primary goal is to obtain the implementation at an affordable price. These applications and services are made available indoors, where the GPS does not function. The goal of indoor navigation is to direct users inside buildings. Dijkstra’s algorithm for locating objects and for moving along the shortest path in an indoor setting are examined in this work. Experimental results of indoor navigation systems were carried out on my organization’s indoor environment and verified the applicability of the presented Indoor Navigation System. The techniques provided include map digitization, locating a user, and choosing the shortest route. This is accomplished through a mobile application created for the Android operating system, and indoor navigation is carried out by using Dijkstra’s algorithm. The proposed method is implemented in our college academic block, and the experimental results show that our navigation method is feasible and effective. To verify the reliability of the algorithm, the proposed application fulfils the criteria of an indoor navigation system to produce the optimal route between two points when applied to a map of our college’s indoor terrain.
1. Introduction
Now-a-days, As the advancement in digital technology and its devices, Location Based Services (LBS) are considerably growing. LBS has long used global navigation satellite systems (GNSS) to navigate, get accurate and reliable information about the outdoor environment. The signals from GNSS are weak, when it penetrates through walls, making it impossible to get accurate indoor LBS [1]. Because GNSS are ineffective indoors, it takes a lot of research and development to create an indoor positioning system (IPS). For the development of IPS, numerous technologies and methods have been investigated.
As a result of various access points (APs) and multiple signal sources, the IPS is realised. [2] There are many ways for establishing the source signal such as Bluetooth low energy (BLE), ultrawideband (UWB), radio frequency identification (RFID) tags, or use already installed APs, such as Wi-Fi, geomagnetic fields. A dead-reckoning technique called “signal-free solutions” in IPS uses commercially available mobile sensors to detect changes in location. Received signal strength (RSS), time of arrival (TOA), time difference of arrival (TDOA), and angle of arrival (AOA) are few of the IPS concepts for sensing radio signals [3]. Due to its simplicity of implementation and lack of additional hardware requirements, RSS has been commonly employed for IPS design.
Compared to the outdoor environment, it is difficult to predict the indoor radio signal transmission. Minor changes to the indoor environment can invalidate the indoor signal propagation model, which is typically based on a propagation channel and known barriers. Localization methods include trilateration and weighted centroid (WC) localization [4] compute the separation from the RSS using the wireless channel model. Additionally, these techniques need the route loss exponent to be precisely calibrated for each indoor environment.
Even when users are in strange environments, IPS aims to help them get to their final destination. A smartphone is required for the system, along with the installation of an application. The proposed method obtains blueprint data of an organization and updates them at the top of the map; the smartphone application is based on the building’s floor plan. The integrated SDK in the mobile application will assist the thirdparty user in locating inside a building and determining the quickest route between the source and destination after updating the floor plan details in the map.
Related works
In the literature, a number of strategies have been put up that make use of various technologies, including infrared, ultrasound, WIFI, RFID, Bluetooth, Visible Light Communication (VLC), UWB, magnetic fields and Wireless ad hoc networks. According to the methods employed to estimate the position, the majority of existing technologies can be generally divided into four categories: trilateration/triangulation, fingerprinting, proximity, and dead reckoning.
RFID tags [5] come in two varieties: active and passive. Passive tags are used in the majority of modern RFID-based navigation systems, because they don’t need an external power source. In order to estimate a position, RFID systems use received signal strength (RSS), angle of arrival (AOA), time of arrival (TOA), and time difference of arrival (TDOA). The widespread usage of RFID technology in navigation systems is due to its ease of use, low cost, and extensive operational horizons. Wi-Fi-based approaches are used in indoor settings [6], where there are enough Wi-Fi access points to avoid the need for a separate infrastructure; instead, these approaches can make use of the infrastructure already present in buildings since the majority of modern structures come with Wi-Fi access points. For positioning, Wi-Fi based indoor localization systems employ trilateration, triangulation, and RSS fingerprinting methods. However, non-line sight conditions indoors, other than RSS, other techniques might fail to precisely predict the user’s location. Trilateration and fingerprinting are the popular RSSbased positioning techniques [7].
The precision of Bluetooth-based systems is almost on par with that of Wi-Fibased systems, and they track users’ movements using Bluetooth low energy (BLE) beacons as a source of RF signals, whereabouts using RSSI fingerprinting or proximity sensing techniques. Similar to Wi-Fi, BLE enables the implementation of localisation techniques like proximity, trilateration and fingerprinting. By intercepting the advertisement packets that the BLE beacons emit, the device might use a beacon to calculate the nearby RSS Signal [8]. The BLE beacon is often interoperable with Android and iOS devices, unlike Wi-Fi. Modern technology typically uses smartphones as a Bluetooth and Wi-Fi signal receiver. VLC-based systems are inexpensive since they make use of the existing LED lighting in buildings. In indoor spaces, these LEDs or fluorescent bulbs are increasingly common [9]. Using the camera on a smartphone or a separate photo detector, light coming from lamps is recognised. The most often utilised measurement techniques in VLC-based positioning systems are TOA and AOA. In [10], Positioning systems based on UWB can deliver accuracy in centimetre(cm) range, which is highly effective than Wi-Fi and Bluetooth. For position estimation, UWB uses TOA, AOA, TDOA, and RSS-based techniques.
The indoor navigation system will choose the user’s path inside the builtin map based on their present location. A map that depicts the areas of an indoor environment and a tool for planning navigation routes make up the majority of the navigation module. Various algorithms [11-14] are most widely used for route planning. Additionally, there are certain systems that offer navigating without a map. The sections that follow discuss each of these systems. The benefit of using ML, according to a recent survey, is effective information collecting. Following an overview of the rationale for applying machine learning to indoor localization, the authors [15], examined ML-based methodologies using their own criteria and classified them into various categories of research topics. However, this survey didn’t take into account how various ML-based solutions’ respective performance metrics. The indoor navigation system in [16] used Google Glass and an Android phone. The techniques suggested for object detection using Hough Transform and Canny detection methods. By measuring the height of the floor region, the wall presence was detected by the floor recognition algorithm, because walls may be one of the key impediments in interior environments. However, the proposed method for object identification did not work for indoor low contrast wall pixels or bulletin boards. An indoor navigation system for malls was suggested by the author [17]. The GIST feature descriptor was employed in the proposed system, which improved image processing and required less memory. The primary tasks of the systems are keyframe extraction, geometric map creation, positioning and routing. The significant frames taken from walkthrough videos and utilised to build a topological map are called keyframes. The author [18] presented a wearable virtual usher that includes a camera which takes photographs of frontal images, headphones that allow users to hear voice routing instructions to get to a specified location, and a computer to assist users in discovering routes in indoor spaces for an indoor environment. A navigation system based on RFID technology, PERCEPT [19] which includes kiosks placed at the entryways and exits points of landmarks, “gloves” made of RFID readers, and passive RFID tags placed in indoor places. Information on significant locations and landmarks is available at the kiosks. Moreover, an Android smartphone with a text-to-speech engine that instructs the user. Wi-Fi and Bluetooth will be used by an Android phone to connect to the PERCEPT server and the glove. The PERCEPT system’s directions are not precise enough. Furthermore, neither steps nor feet were used to describe the direction.
In [20], Underground mines cannot use the Global Navigation Satellite System (GNSS); additional technologies are required for localisation. Currently available sensors and radios in smartphones and tablets can give useful data for indoor localization using RFID tags, Bluetooth Beacons and other devices. Smartphones may be a very useful tool for mineworkers to carry around because they make localization and navigation much easier. But installation costs are needed and everyday locations of mines are changed frequently. By determining a user’s location, obtaining information about the desired destination, and computing a path for navigation, Bluetooth Low Energy (BLE) beaconbased positioning systems are utilised for indoor mapping and creating a 2D indoor navigation system [21]. Dijkstra’s algorithm and a specially created Indoor Positioning System (IPS) are used to accomplish this. This increases the cost of installation of BLE beacons. In [22], the author discussed different indoor localization methods and technologies. The author provides an overview of existing localization techniques and contrasts them in terms of precision, cost, benefits, and drawbacks. The author also compares various detection methods’ accuracy and costs while presenting various detection strategies. In [23], the author discussed the various routing methods that adjust to dynamically changing environments. In order to improve road navigation, bio-inspired algorithms for finding the shortest path have been discussed. Dijkstra’s Algorithm performs well on finding the optimal path between source and destination with fewer costs.
Numerous frequency bands, including the 0.9 GHz, 1.8 GHz, and 2.8 GHz bands, are used by cellular networks. Compared to Wi-Fi networks, these networks have better coverage and don’t need any extra equipment. In the beginning, localization relied on proximity, where the mobile location was found inside the cell service area; however, this method yields incredibly poor results [24]. Utilizing the signals obtained from the Global System for Mobile Communications (GSM), localisation was carried out in [25] utilising RSS fingerprinting. In their research, fingerprints were taken from 6 cells and 29 GSM channels. According to a study on localisation using LTEonly and LTE-WLAN fingerprinting described in [26], LTE-only fingerprinting produces poor results while LTE-WLAN fingerprinting significantly improves performance. Other RF localisation methods that are currently in use, such as RFID and Wi-Fi, can be supported by cellular systems. In [27], the author created a location-based task reminder for indoor (and outdoor) mobile users and alerts them as they approach a desired and practical destination. The authors leveraged the widespread inside use of the IEEE 802.11 WLAN infrastructure to compensate for the absence of GPS position sensing, which was previously the only method of indoor localization. Their architecture, which is deployed on Android-based devices, principally relies on RSSI measurements at various ranges from the Wi-Fi AP and Database tables approach. In comparison to earlier architectures, it offers consumers better performance and a better user interface.
We aim to develop a smartphone app that can locate each visitor inside our college’s academic building and point them in the direction of a specific location. The suggested strategy focuses on coming up with a simple and safe solution for the benefit of new guests to our college. There is a need to improve pathfinding and navigation for new students and guests due to the large area with numerous distinct buildings and rooms in our college academic block, so that they could discover any of the necessary services nearby. In this method, visitors can utilise a smartphone app to access digital guiding signs to go where they’re going. The route to the different destinations and the classes can be projected on a digital map with sequential check points and paths to the benefit of new students, particularly during the registration period at the beginning of each semester. For these reasons, we made the decision to create a smartphone application that guides users to their goal by locating them on our college academic block. An academic block of our institution is considered as a testbed for the system and the obtained experimental results are discussed in later sections.
Proposed methodology
Analysis of indoor navigation apps
Today, almost everyone owns a smartphone, making it much simpler to navigate since these devices have builtin GPS systems that assist everyone in finding their way. These interior navigation apps are a gift for people in today’s world where people are continuously moving from one area to another. When it comes to navigating inside spaces like crowded malls, cafes, shops, restaurants, public markets, or stores inside vast complexes, typical GPS-based mapping apps somehow fall short of expectations. Consequently, you require specialised indoor positioning and navigation apps that are distinct from outdoor navigation apps for use indoors. The issue is that because outdoor navigation mobile applications (Apps) rely on GPS signals, they frequently lose service in congested areas and within substantial complexes or buildings. These indoor positioning apps were created particularly for smaller places and use augmented reality to show your location using built-in GPS maps. The shortest paths to your location are provided when the user uses the builtin GPS maps present in the apps.
The indoor GPS navigation applications work similarly to outdoor GPS navigation apps in that they enable users to locate a certain spot inside of huge business facilities. This was the recent method in the position identification and navigational field. These Indoor Positioning System (IPS) enabled services make it easier to find places inside of airports, hospitals, and other buildings rapidly. It displays the users’ current locations on the maps and points them in the direction of the quickest route to get them where they need to go. These apps primarily concentrate on navigation, positioning, and voice over notification to the users via their mobile devices so they can quickly get where they’re going. They provide assistance to people and businesses in a variety of ways and enable users to move rapidly through densely populated, expansive retail malls and airports. Visitors may reach their destinations quickly and without any problems using indoor navigation apps, which eliminate the need for them to ask others for directions or search the internet. Simply download the app using your smartphone, then use it to quickly go to your desired location.
Drawing plans
Understanding the structure of a building is necessary for indoor navigation. This makes it possible to identify the points of interest and estimate the quickest path between the starting and ending location. The construction designs are also essential because they will serve as the primary user interface for the system. The real building dimensions must be included in these blueprints. There are tools that give us a variety of features that make it easier to create plans; one of these features is the ability to include photos that can stand in for locations like offices, classrooms, laboratories, etc. As soon as the building designs are created, they must be fully scaled in the navigation system. The recommended system will be updated with an organization’s route map design and building structure plan design. To determine the user’s location or position from the source to the destination point via the quickest route, the integrated software application is adapted for mobile applications. The tests were conducted in our organization, which was a 3 floor building. The building layout of our institution’s academic block was shown in the following figure 1.
Development of algorithm
The algorithms for the indoor navigation system are being developed and put into use at this point. Algorithms are crucial because they allow for the location of a user to be determined, the creation of a route from one point to another, the suggestion of the best path, and the usage of GPS in open areas. The algorithms for position identification and navigation path generation algorithms are crucial to our concept since they allow for the completion of the most crucial tasks: Determine the location of a user and Create a path between a starting point and an ending point.
Algorithm to identify the user’s position and shortest navigation routes
The process of developing an indoor computer application is complex. The best navigational technology must be chosen based on the structure. Then, in relation to this technology, it is necessary to consider the techniques for measuring the distance and the algorithms for figuring out the way. However, research has demonstrated that the steps taken can be combined and presented as ways that are based on well-known methods and algorithms for developing a software solution for guiding individuals inside buildings without access to a GPS signal. The proposed system used the Dijkstra algorithm, which was discussed in the following section. Additionally, this algorithm utilises the ideal path. To employ it, the Dijkstra algorithm was modified to find the destination in an optimal way. This algorithm seeks to identify a user’s location. This algorithm is used to determine the user’s location, allowing us to determine the user’s starting point, places visited, and when they arrived at their destination.
Dijkstra’s algorithm
A label-set system called the Dijkstra algorithm categorises network nodes into three groups: marked nodes, temporarily labelled nodes, and nodes without labels. In order to begin searching, we initialise all of the nodes to be unlabeled, nodes that are connected to the shortest path nodes should be converted into temporary labelled nodes, and mark the nodes that are closest to the source point. Each cycle, we convert a selection of temporary labelled nodes into marked nodes, searching for the target nodes or labelling every node. A well-known algorithm for solving the narrow shortest path issue is the Dijkstra algorithm. After removing one side from the original path, it has been discovered that the problem of finding the particular shortest pathways in the subgraphs can be translated into the problem of finding the first N shortest paths.
Implementation
The proposed intelligent Indoor Navigation System was implemented in our educational organization, which is described in this section. The client-server architecture of the Indoor system allows mobile applications (clients) to communicate with the Server by sending requests. Then, based on the requests, the server sends a json response to the mobile application. Web Services are used for sending requests and responses. The appropriate implementation technology must be selected based on the suggested approach for creating the indoor navigation application. This section will identify the user-estimated location using a mathematical algorithm technique. Based on the mobile application, Android technology was used to pinpoint a user’s exact location within an organization’s indoor space. Then, using implementing technology, the system locates a user’s destination location using the Dijkstra’s shortest path on the building’s planned layout. The information will be shown as an output feedback display in the mobile device via the integrated indoor navigation application system.
When the user has not correctly followed the directions, the Indoor App may tell. “You have departed from the route,” the application notifies the user through voice command. In this scenario, the mobile app recomputed the path based on the user’s position. The application also has the ability to recognise whether a user has switched buildings after beginning a route in another building. The purpose of the mobile app is to attain the user’s destination point from the source point in an optimal route using the shortest path algorithm. The algorithm used in the mobile app is Dijkstraw’s algorithm to identify the location where the user is located as well as to determine their exact position, indicating which building, floor, office, and other details they are in. You can specify the starting point and ending point with this level of geographic accuracy to create the best route.
Results
The tests performed to assess the proper operation of our Indoor Mobile Application and the Dijkstra algorithm to determine the best route are displayed in this part. The tests were conducted in our organization, which was a 3 floor building. The suggested system makes it easier for users to navigate within a constrained campus, which helps to minimise confusion and improves the system’s physical environment. Users can choose the source and destination points for an interior navigation from the android system as shown in the following figure 2. Our specifically created solutions enable online and mobile applications to transform into personalised navigational aids that can handle any problem. The navigation outcome of the planned project, completed for our college. Dijkstra’s method can be used to identify answers to the current issues utilising the shortest routes. The shortest route and the optimum path are determined based on the problem with the interior navigation system. This is important for navigation systems since it can help with making time- and decision-saving decisions. The implementation of the proposed system using Dijkstra’s algorithm and its efficient indoor navigation system output was shown in the figure 3. The following table 1 indicates the comparative results of existing indoor localization technology with the proposed technology.
Conclusion
Most businesses and organisations use Android applications to give quick and simple access to their locations and goods in order to promote their operations and client services. It is preferable to use a mobile device with GPS services to identify unknown cities or locations when you have a smartphone in your hand. In reality, the Global Positioning System (GPS) services can track the user’s location or locations via a mobile device. However, in enclosed spaces or foreign locations, the GPS service is unable to offer the hassle-free services. Applications for indoor positioning and navigation can address the issue in an indoor environment. The straightforward technology behind this is that a smartphone application helps the user locate specific locations in an unfamiliar environment when GPS isn’t available. The usage of an indoor navigation and positioning system aids users in finding specific locations within vast university campuses, corporate buildings, airports, malls, hospitals, etc. Reduced hardware infrastructure, power usage, and system complexity have all enhanced the system. While preserving the system’s accuracy, the cost of the system is also significantly lower.
Acknowledgment
We Sincerely thank our management and staff members of Ramco Institute of Technology, Rajapalayam for providing the building layout plans to do the work and execute the work successfully.
References
[1] B. Peterson, D. Bruckner and S. Heye, (1997), Measuring GPS signals indoors International Association of Institutes of Navigation, World congress.
[2] W. Sakpere, M. Adeyeye-Oshin and N.B. Mlitwa, (2017), A Stateof-the-Art Survey of Indoor Positioning and Navigation Systems and Technologies, S. Afr. Comput. J., vol. 29, pp. 145-197.
[3] Tran T-A, Ruppert T, Abonyi J., (2021), Indoor Positioning Systems Can Revolutionise Digital Lean. Applied Sciences., 11(11):5291.
[4] Y. -B. Park and Y. H. Lee, (2021), A Novel Unified Trilateration Method for RSSI based Indoor Localization,” 2021 International Conference on Information and Communication Technology Convergence (ICTC), pp. 1628-1631
[5] Bouet M, dos Santos AL, (2008), RFID tags: positioning principles and localization techniques. In: 2008 1st IFIP wireless days, pp 1–5
[6] He S, Chan S-G, (2016), Wifi fingerprint-based indoor positioning: recent advances and comparisons. IEEE Commun Surv Tutor 18(1):466–490
[7] Fu Q, Retscher G, (2009), Active RFID trilateration and location fingerprinting based on RSSI for pedestrian navigation. J Navig 62(2):323–340
[8] Farid Z, Nordin R, Ismail M, (2013), Recent advances in wireless indoor localization techniques and system. J Comput Netw Commun 2013:12
[9] Do T-H, Yoo M, (2016), An in-depth survey of visible light communication-based positioning systems. Sensors
[10] Alarifi A, Al-Salman A, Alsaleh M, Alnafessah A, Al-Hadhrami S, Al-Ammar MA, Al-Khalifa HS, (2016), Ultra-wideband indoor positioning technologies: analysis and recent advances. Sensors.
[11] Hart PE, Nilsson NJ, Raphael B, (1968), A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern, 4(2):100–107.
[12] Johnson DB, (1973), A note on dijkstra’s shortest path algorithm. J ACM 20(3):385–388.
[13] Stentz A et al, (1995), The focussed d* algorithm for real-time replanning. IJCAI 95:1652–1659
[14] Floyd RW, (1962), Algorithm 97: shortest path. Commun ACM 5(6):345.
[15] Zafari, F.; Gkelias, A.; Leung, K.K., (2021) A survey of indoor localization systems and technologies. IEEE Commun. Surv. Tutor., 21, 2568–2599.
[16] Garcia G, Nahapetian A, (2015), Wearable computing for imagebased indoor navigation of the visually impaired. In: Proceedings of the conference on wireless health. WH ’15, ACM, New York, NY, USA, pp 17–1176.
[17] Athira SV, George M, Jose BR, Mathew J, (2017), A global image descriptor based navigation system for indoor environment. Procedia Comput Sci, 115:466–473.
[18] Li L, Xu Q, Chandrasekhar V, Lim J, Tan C, Mukawa MA, (2017), A wearable virtual usher for visionbased cognitive indoor navigation. IEEE Trans Cybern, 47(4):841–854.
[19] Ganz A, Schafer J, Gandhi S, Puleo E, Wilson C, Robertson M, (2012), Percept indoor navigation system for the blind and visually impaired: architecture and experimentation. Int J Telemed Appl, 19–191919.
[20] Zare, M., Battulwar, R., Seamons, J. et al., (2021), Applications of Wireless Indoor Positioning Systems and Technologies in Underground Mining: a Review. Mining, Metallurgy & Exploration 38, 2307–2322.
[21] K. Ramaneti, N. Mohanty and V. B. Kumaravelu, (2012), IoT based 2D Indoor Navigation System Using BLE Beacons and Dijkstra’s Algorithm,” 2021 12th International Conference on Computing Communication and Networking Technologies (ICCCNT), pp. 1-6
[22] Obeidat, H., Shuaieb, W., Obeidat, O. et al., (2021), A Review of Indoor Localization Techniques and Wireless Technologies. Wireless Pers Commun 119, 289–327.
[23] Tyagi, N., Singh, J., Singh, S, (2023), A Review of Routing Algorithms for Intelligent Route Planning and Path Optimization in Road Navigation. In: Deepak, B., Bahubalendruni, M.R., Parhi, D., Biswal, B.B. (eds) Recent Trends in Product Design and Intelligent Manufacturing Systems. Lecture Notes in Mechanical Engineering. Springer, Singapore.
[24] Chai, M., Li, C., & Huang, H, (2020), A New Indoor Positioning Algorithm of Cellular and Wi-Fi Networks. J. Navig., 73(3), 509–529.
[25] Driusso, M., Marshall, C., Sabathy, M., Knutti, F., Mathis, H., & Babich, F, (2016), Indoor positioning using LTE signals. In International Conference on Indoor Positioning and Indoor Navigation (IPIN), 2016, 1–8.
[26] Turkka, J., Hiltunen, T., Mondal, R. U., & Ristaniemi, T, (2015), Performance evaluation of LTE radio fingerprinting using field measurements, In. International Symposium on Wireless Communication Systems (ISWCS), 466–470.
[27] Z. Wu, K. Fu, E. Jedari, S. R. Shuvra, R. Rashidzadeh, and M. Saif, (2016), A Fast and Resource Efficient Method for Indoor Positioning Using Received Signal Strength, IEEE Trans. Veh. Technol., 65, pp. 9747–9758.
Content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. Published under licence by IOP Publishing Ltd.
The paper first published in Journal of Physics.: Conf. Ser. 2466 012007 is republished with authors’ permission. The paper may be cited as R. Deiva Nayagam et al 2023 J. Phys.: Conf. Ser. 2466 012007.
(No Ratings Yet)
Loading...
Leave your response!