Figure 1 shows block diagram of navigation and tracking system. It has two main parts: the navigation system and tracking system. The structure of the navigation system is composed of a wireless network, a navigation app installed on the smartphone, a Raspberry Pi 4B as a server, and an InfluxDB database. A navigation app installed on the smartphone has a primary function to scan all readable Wi-Fi routers and records the RSSI value of each of the Wi-Fi routers. The smartphone sends RSSI value to the Raspberry Pi using the Message Queuing Telemetry Transport (MQTT) protocol. The server will connect to the MQTT broker and subscribe to certain topics. There are two topics subscribed, RSSI value and destination position. The server will get MAC addresses, RSSI, and SSID data that corresponds to each router at a certain time and destination position. RSSI values are processed on Raspberry Pi 4B using Python. The Python program invokes the Fingerprint Map data in the form of RSSI value from the InfluxDB database. The program will estimate position data in the form of x coordinates, y coordinates, and location information using k-Nearest Neighbor algorithm (k-NN). After the user's position and destination is known, each information is processed using the Dijkstra’s algorithm to get the shortest path the user can take. The route is sent to the user using the MQTT protocol and is displayed on smartphone using the MIT App Inventor application.
The same position data is sent from the Raspberry Pi 4B to the web page. The x coordinate, y coordinate, and location description will be published to the channel on PubNub. When the user moves the smartphone to a different location, the marker will also move and describe the road that has been traversed. Processed data contains x coordinate, y coordinate, location information, and timestamp stored in the InfluxDB database. Beside serve elementary configuration, the web will provide the analyzed information.
A. Localization Algorithm
At a certain node, smartphone will get the RSSI value from all readable Wi-Fi routers with their corresponding MAC address. Then from this set of RSSI values, the user location can be predicted by comparing the RSSI value between the Wi-Fi fingerprint from each router at each node and the RSSI value read by smartphone. The difference in these values for each router is averaged at each node. The smallest average RSSI error value from all nodes is used as the user’s coordinate. First, we estimate the RSSI values using the path-loss model. We then can formulate a mathematical representation as follows:
Given \(m\) known nodes, each node is a center point in a regular grid fingerprint map, each node is located at \(({x}_{i},{y}_{i}); i = \text{1,2},...,m\). The RSSI value of \(n\) known routers at node 𝑖-th are \({{P}_{i}}_{j};j= \text{1,2},..., n\). From a set of data \(\left\{\right({x}_{i},{y}_{i},{{P}_{i}}_{1}, {{P}_{i}}_{2},\dots ,{{P}_{i}}_{n}\left)\right\}\) then we calculate the location of user \((x,y)\). There are two main steps of RSSI-based position calculation, first is RSSI estimation of each nodes, by using path-loss model, and the second one is location estimation, the value of \({P}_{j}\) is used to estimate the location of the user.
B. Path-Loss Model
RSSI can be used to determine position. The value of RSSI depends on distance. Its value decreases with increasing distance between transmitter and receiver. RSSI value estimation uses (1) Path-Loss model.
$$PL\left(dB\right)={PL}_{{d}_{0}}\left(dBm\right)-10nlog\left(\frac{d}{{d}_{0}}\right)-WL$$
1
\(PL\left(dB\right)\) is path loss or the power at the receiver. \({PL}_{{d}_{0}}\left(dBm\right)\) is RSSI value from routers. \(n\) is path-loss exponent. \(d\) is the distance between transmitter and receiver, we choose \({d}_{0}=1m\). \(WL\) is sum of wall loss [29].
Log transformation converts the logarithmic pattern of relationship between the RSSI value of a router and the distance at all nodes to a linear pattern. Regression analysis is then used to find equations that fit the linear pattern. Once we have the regression equation, we can use the model to make predictions of RSSI value of each router at each node.
C. Fingerprint
Fingerprint divides into two main parts, the offline and the online phase. The offline phase’s aim is to build fingerprint map. It collects several RSSI values. The rest of RSSI values estimated using regression analysis. Then, the InfluxDB database has the value of RSSI from each router in every center point in a regular grid fingerprint map (node), \({{P}_{r}}_{j};j= \text{1,2},..., n\). This value is stored into the InfluxDB database which contains the RSSI value of each router, the x coordinates, the y coordinates, and the description of the location. The x and y coordinates are the pixel coordinates of the floor plan. In addition, a list of MAC addresses of all routers is stored into the InfluxDB database. In the online phase, the smartphone receives the real-time RSSI value of each router at a certain node \({P}_{j};j= \text{1,2},..., n\) then uses k-Nearest Neighbor Algorithm to calculate user position.
D. k-Nearest Neighbor Algorithm
k-NN algorithm calculates the difference between a measured RSSI value and each RSSI value on fingerprint map by using (2).
For i = 1 : m
For j = 1 : k
$${d}_{i}({x}_{i},{y}_{i})=\sum _{1}^{k}\left|{{P}_{i}}_{j}-{P}_{j}\right|$$
2
end
end
\({d}_{i}\) is the difference between real-time RSSI value of user’s current position compared to the RSSI value of each router at node node 𝑖-th on the fingerprint map, \({{P}_{i}}_{j}\) is the RSSI reference value of a certain node on the fingerprint map, \({P}_{j}\) is the value of RSSI that represent user’s current position [29], [30].
The difference in these values for each router is averaged at each node by using (2).
$${d}_{i}({x}_{i},{y}_{i})=\sum _{1}^{k}\left|{{P}_{i}}_{j}-{P}_{j}\right|$$
2
$${\stackrel{-}{d}}_{i}=\frac{1}{k}{d}_{i}\left({x}_{i},{y}_{i}\right)$$
3
The smallest average RSSI error value from all nodes is used as the user’s coordinate as shown in Eq. (4).
$$\left(x,y\right)={min}\left({\stackrel{-}{d}}_{i}\left({x}_{i},{y}_{i}\right)\right)$$
4
E. Dijkstra's algorithm
First, build a matrix for every node in the center point in a regular grid fingerprint map. If the nodes are connected to each other, input their distance in matrix. But if they are not, input in matrix. Then, receive the user’s current position and destination to determine the shortest path by using matrix. Consider all unvisited neighbors’ node and calculate their distances through the current node, {matrix(D,k) + distance(D) < distance(k)}, compare the recently calculated distance to the current assigned value and assign the smaller one. {distance(k) ← Matrix((D,k) + distance(D)} and parent {parent(k) ← D}. D is number of neighbors’ nodes. k is all nodes on fingerprint map. Finally, determine the shortest path using {P ← Parent(Target)}, repeat until destination position is obtained then replace the route {Route ← [P Route]}[29], [32].
F. Android App
The MIT App Inventor 2 is a programming environment that provides a graphical interface to design and build an application in Android smartphone. It’s also web application, free, and easy drag-and-drop programming [33], [34]. The designed Android app tested in four different specifications smartphones, the lowest specifications are having 2 GB RAM, using Wi-Fi 802.11 a/b/g/n, dual-band, Wi-Fi Direct, hotspot, and having Android operating system version 7.1 nougat. Data collected in this paper taken using Xiaomi Redmi 5A Android smartphone.
The flowchart of navigation system as an Android app on the smartphone is represented in Fig. 2. There are two main parts, data delivery system and data reception system. In the data delivery system, the smartphone sends destination position and RSSI values with their corresponding MAC address and SSID to the server. The RSSI list shows an array containing the RSSI values retrieved from the read SSIDs. Data transmission uses the MQTT protocol. In this research the data sent is in two topics, RSSI values and navigation destinations. The data are differentiated by topic in order to perform data parsing on the server. The broker used is Mosquitto.
Then, the data that has been processed on the server is sent to the smartphone using the MQTT protocol. In this data reception system, two topics received is in the form of a JSON array. The data received are the user's location and the floor plan plus the shortest path to the destination.
G. Tracking System
Sending data to a web page is done by subscribing and publishing to PubNub. The subscribe and publish keys are written according to the password on the web page along with the channel name. When clicking "Start Tracking", it means that the program starts to "subscribe" to the channel and will receive data from the server. When clicking "Stop Tracking", it means that the program starts "unsubscribing" the channel so that no data will be received. The value of x coordinate, y coordinate, and location information are published to the channel that was written in Python. Web page was created to display real-time location. JavaScript programming language is used to create interactive webpage.
First, put floor plans inside our web page. Floor plans used is a 2-dimensional floor plan. Then, there is a function to provide an icon for the x and y coordinates, along with a line connecting the old x and y coordinates with the new x and y coordinates. When the program is run on Raspberry Pi 4B the marker on the map will point to the user's current position. When the user moves to a different location, the marker will also move and show the path that has been passed by user.