Finger Printing using Applications IoT for Localization Indoor

Finger Printing using Applications IoT for Localization Indoor

M. Jothi Lakshmi M.E (CSE

S. Dhanabal

Asp/Head of CSE,

PGP College of Engineering and Technology ,Namakkal.

Abstract– Fingerprinting method is one of the preferred method used for indoor localization using Wi-Fi signals because of its low complexity and its cost effectiveness. This paper proposes an indoor localization algorithm using fingerprinting method that is suitable for an indoor IoT application. The proposed algorithm combines the location estimates from two different approaches, deterministic and probabilistic, to estimate the target location. The proposed algorithm was tested for different conditions: stationary and moving IoT targets, line-of- sight and non-line-of-sight indoor environments. The results showed the proposed combined algorithm performed better in terms of localization accuracy, precision and robustness than deterministic and probabilistic methods individually and similar past research.

Keywords: IoT, indoor localization, fingerprinting

1. INTRODUCTION

   Indoor localization or indoor positioning is a key enabling technology for IoT applications [1] such as guiding customers or visitors inside a shopping mall or a convention centre, where conventional navigation technologies such as GPS is not available.[2],[3] Even though there are indoor localization solutions that use RFID or BLE beacons with known fixed locations inside a building, it requires additional hardware and installation costs thus making the implementation of these systems costly in terms of time and money. However, using Wi-Fi signals to perform localization makes it a better alternative to the beacon based systems as it does not require the installation of new hardware, thus reducing complexity and cost of the system [4]. In the literature, some research have focused on the study of RF signal propagation in indoor environments while others have developed localization methods that exploit various aspects of RF signal propagation such as propagation time, angle of arrival and received signal strength (RSS) to achieve localization. Methods such as Time of Arrival (TOA) and Time Difference of Arrival (TDOA) use propagation time for localization. These methods require time synchronisation between target device and measuring stations and between measuring stations respectively. Methods that use propagation angle, such as Angle of Arrival (AOA) require measuring stations to have

   special antenna arrangements in different orientations. In addition to being complex, these systems suffer reduced performance due to propagation time and angle are directly affected by multipath effect existing in indoor environments. Methods using RSS however provide a better alternative. Fingerprinting method uses RSS measurements and is less complex in implementation that it does not require special hardware or the access point locations. It can be implemented in software reducing costs [4]. Performance of localization algorithms are quantified using its accuracy, precision and robustness. Accuracy is a measure of how much the result has deviated from the expected outcome, while precision is a measure of how consistently the result is within a certain value range. Robustness is how well the algorithm perform under poor Radio Frequency (RF) conditions [5]. Past research have resulted in precisions in the range of 90%, but it is also important to know the error value considered when calculating the precision. For example, in [6] the precision values for different algorithms are shown in Table I.

   Table I. Precisions of different algorithms in [9]

   Method	Accuracy (m)	Precision (< 2m)	Precision (< 1m)
   Deterministic	1.6	90%	9%
   Probabilistic	1.87	70%	30%
   Combined	1.54	65%	30%

   As seen above, the precision is 90% when 2m is considered for deterministic (KNN) method while it drops to 9% when

   1m is considered. The same applies for Probabilistic and

   Combined methods. By comparison, the work in

   1. proposed algorithm achieved only 50% precision below 2m error but achieved 30% precision when 1m error was considered. In [8], the accuracy and precision of some commercial indoor localisation solutions are compared. Table II illustrates some solutions using WiFi RSS for localization.

      Table II. Commercial products and their performance [8]

      Solution	Algorithm	Accuracy	Precision
      Microsoft RADAR	KNN	3-5m	50% within 2.5m 90% within 5.9m
      Horus	probabilistic	2m	90% within 2.1m
      DIT	MLP	3m	90% within 5.12m
      MultiLoc	SMP	2.7m	50% within 2.7m

      Above table shows that the accuracy and precision of some commercial systems are relatively low. Some solutions, EIRIS and Ubisense, provided accuracy below 1m, but their robustness was lower [8]. After considering different existing solutions and past research the importance of achieving high accuracy, precision along with robustness was identified. For this purpose, this paper uses fingerprinting method in the proposed algorithm.

      1. Fingerprinting method

   Fingerprinting method is one of the most used method for localization because of its above-mentioned benefits. Fingerprinting method involves storing the RF characteristics, known as fingerprints, of locations of the indoor environment in a database and comparing the fingerprint of the unknown target location with the fingerprints in the database to find an approximated location of the target [2]. As such fingerprinting method is composed of two phases:

   1. Offline Phase

      This phase is also called the Data Collection phase during which, the fingerprints of the concerned indoor area are collected and the database is created. The indoor area is divided into an equally spaced grid where the grid points are called reference points (RP), at which the data will be collected. Past studies have showed that multipath effect, reflection, diffraction and scattering cause RSS to randomly vary around a mean value at a location[9]. RSS value is also affected by fading, which consists of two parts, Large-scale fading and small-scale fading. Large-scale fading is caused by attenuation due to signals being absorbed by various materials and objects in the environment. Large-scale fading decides the mean RSS. Small-scale fading is caused by multipath effect. As such, RSS in an indoor environment can be approximated to a Gaussian distribution with a mean and a standard deviation. For a more accurate approximation of mean and standard deviation, large number of samples will need to be collected at each RP. In literature, number of samples collected were as high as 10,000 [7]. After collecting samples the calculated mean and standard deviation will be part of the fingerprint of that RP [9], [10].

   2. Online phase

   In the online phase the algorithm takes a sample fingerprint from the unknown target location and

   compares it with the fingerprints in the database to classify the RPs that are most likely (or closest) to the target location. There are several known algorithms such as probabilistic, k-Nearest- Neighbour (KNN), neural networks, support vector machine (SVM) etc. This work uses the probabilistic and KNN methods to find two sets of estimated coordinates and finally combine them [8].

   In this paper, Section II describes the proposed fingerprinting method in detail. Section III discusses the results and observations of the testing of the algorithm. Finally, Section IV provides the conclusion of this paper.

2. FINGERPRINTING ALGORITHM

   This paper implements the fingerprinting algorithm based on past research [6] making modifications with the aim of improving performance in terms of precision, accuracy and robustness. Two algorithms were designed to perform tasks in each phase of the fingerprinting method.

   1. Data collection algorithm

      Figure 1 shows the flowchart of the proposed data collection software used in during the data collection phase. As seen in the flowchart the data collection will be performed for s number of times at a particular RP. In this paper 100 is chosen, as the number of samples, due to practical reasons, but larger values will give a better representation of the RF behaviour at the RP. When collecting data at the RP, firstly the Wi-Fi signals will be scanned to obtain the list of available Wi-Fi access points (Cells) and their information such as signal level, signal quality, modulation and MAC address. The second block in the flowchart represent the process of extracting the required information from the list. The list will include Wi-Fi signals from other buildings, but only those from the required building needs to be filtered. There after MAC address and RSS of each cell will be extracted and the total number of times a MAC address (i.e. access point) was received and the total RSS will be saved. When the measurement is done for all s number of times, the final fingerprint for the RP will be created by calculating the mean and standard deviation of RSS for each MAC address received and it will them be saved to a log- file.

      Fig. 1. Data collection software flowchart

      After data has been collected for all RP, the fingerprint database (FPDB) can be created using the log-files of each RP. The FPDB consists of three parts named FPDB1, FPDB2 and FPDB3. FPDB1 contains all RP and the list of MAC addresses received at each RP during data collection phase. FPDB2 contains the fingerprints for each RP. Each fingerprint consists of RSS statistics received for all MAC at each RP. The RSS statistics include mean RSS, standard deviation and unique RSS values received during the measurement period and their frequencies. FPDB3 contains coordinates of each RP. The FPDB will be used as an input to the localization algorithm during the online phase, which will be explained next.

   2. Localization algorithm

   Localization algorithm is executed during the online phase. The localization algorithm proposed in this paper takes five rapid samples at the beginning to create the sample fingerprint of the unknown target location. This sample fingerprint is said to be of size N, meaning it contains N number of MAC addresses received at the target location and the average RSS of each MAC received during the sampling

   the target location using two different methods, deterministic method and probabilistic method. The difference between the two methods is that in deterministic method RPs that are closest to the target location are found while in probabilistic method RPs that are most probable to be the target location are found.

   Fig. 2. Localization algorithm

   1. Deterministic method

      This method calculates the Euclidian distance between the

      sample and each RP in the prematch.

      period. This sampling process allows to get a better representation of RSS, reducing the effect of RSS fluctuation

      (1)

      caused by fading. Then the sample fingerprint is sent through an above average filter, where MAC addresses whose RSS is higher than the average RSS of the sample are selected to create the sample_n fingerprint of size n where n<N. The resulting sample_n MAC address list is then matched against

      the FPDB1 in the pre-match phase. In the pre-match phase RP that contain all the MAC in the sample_n are selected from FPDB1 to create the prematch set of RP. This reduces the number of RP to m<M where M is the number of RP in the test area. The prematch set of RP is then used to calculate

      In Eq. 1, and are RSS values of ith MAC in sample_n and corresponding fingerprint in FPDB2 where i=1,2,3n. The Euclidian distance is found for all RP in prematch where j=1,2,3.m. Then from the prematch, Kd number of RPs that have the lowest Euclidean distance are selected. The value of Kd that gives the best performance must be experimentally found beforehand. [6]

      ,

      of being the target location. The conditional probability of the ith RP is found using Bayes rule [11] as shown in Eq. 3.

      .

      Thereafter Weighted K-Nearest Neighbour (WKNN) algorithm is used to calculate the intermediate coordinates

      (3)

      , of the target as in Eq. 2 where 1/ for the ith

      |

      RP with the lowest distance. The , values are retrieved from FPDB3.

      Where P(RP) is the prior probability of the target being at a given RP. This value depends on various factors such as user speed, user movement patterns but here it is assumed that

   2. Probabilistic method

      The main idea behind the probabilistic method is to find the RPs in the prematch set, which have the highest probability

      each R P in t he prematch is equally probable making P(RP) =

      1. Line of Sight (LOS) scenario

         1/m. | is the likelihood o f t he sample_n (i.e. S)

         occurring at the ith RP. Value of | is given by Eq. 4.

         | | | . | (4)

         Where i=1,2,m and | are Gau ssian

         probabilities of RSS of ith MAC address, | , in the sample_n modelled by Eq. 5.

         | (5)

         Where x, µ and are the RSS of the ith MAC in sample_n, the mean RSS of the MAC in RP and the standard deviation of RSS of the ith MAC. After calculating | for each RP in prematch, the Kp number of RPs with the highest

         probabilities will be selected. Using this, the intermediate coordinates of target, , will be found using the following equation: [6]

         , ,

         (6)

         Where the weight w=p and

         , , the coordinates of each

         Fig. 3. Test area layout for LOS scenario

         The test area is located in an open area with five access

         jth RP in the prematch set, will be retrieved from FPDB3. After , and , are found the two results will be combined as shown in Eq. 7. to get the final estimated coordinate (X,Y) of the target location.

         , ,

         points having clear LOS with the entire test area. Figure 3 shows the test area with the approximate location of access points. (Note that the exact locations of access points are irrelevant when using fingerprinting method)Test parameters are shown in Table below.

         Parameter	Value
         RF propagation	LOS
         No of RP	49
         Area size	6m x 6m
         Origin	RP1
         X-axis direction	RP1RP7
         Y-axis direction	RP1RP43
         Test location (xt,yt)	(3.5, 3.5)
         User speed	N/A
         Readings	100
         Kd and Kp	K

         Parameter	Value
         RF propagation	LOS
         No of RP	49
         Area size	6m x 6m
         Origin	RP1
         X-axis direction	RP1RP7
         Y-axis direction	RP1RP43
         Test location (xt,yt)	(3.5, 3.5)
         User speed	N/A
         Readings	100
         Kd and Kp	K

         Table III. Stationary test parameters for LOS scenario

         , (7)

         Where E1,E2are errors of , and , with respect

         to the test location , respectively. E1 and E2 are found as in Eq. 8 and Eq. 9 respectively.

         1 (8)

         2 (9)

3. TESTS, RESULTS AND OBSERVATIONS

   This section discusses tests performed to measure the

   ,

   Access points A and D have clear LOS with entire test area while B and C have obstructions to parts of the area. Test results are shown in Table IV.

   Table IV. Results for different K in LOS scenario

   K	Deterministic		Probabilistic		Combined
   	Error (m)	Pre (%)	Error (m)	Pre (%)	Error (m)	Pre (%)
   3	1.5546	9	2.1247	6	0.4757	88
   4	1.5613	1	1.4414	24	0.5383	84
   5	1.5784	16	1.5851	29	1.1923	46
   6	1.3382	19	1.3812	21	0.9635	49
   7	1.7811	5	1.5638	34	1.4347	31

   The combined method has an improved the accuracy and precision when compared to the individual methods. The maximum precision of 88% for error below 0.9m and lowest error of 0.4757m were observed by the combined method for K=3. The results of the proposed method for K=3 is shown in Fig. 6.

   As seen in Fig. 4 the results are mostly clustered within 1m radius of the test location (3.5, 3.5). A moving test was

   performed to track the moving target with the following test parameters:

   Parameter	Value
   RF propagation	LOS
   No of RP	49
   Area size	6m x 6m
   Origin	RP1
   X-axis direction	RP1RP7
   Y-axis direction	RP1RP43
   Between points	(3.5,0) (3.5,5)
   User speed	0.31 m/s
   Readings	100
   Kd and Kp	3

   Parameter	Value
   RF propagation	LOS
   No of RP	49
   Area size	6m x 6m
   Origin	RP1
   X-axis direction	RP1RP7
   Y-axis direction	RP1RP43
   Between points	(3.5,0) (3.5,5)
   User speed	0.31 m/s
   Readings	100
   Kd and Kp	3

   Fig. 4. Stationary test K=3 using combined method for LOS scenario Table V. Moving test parameters for LOS scenario

   The apparatus was moved in a straight line, back and forth, slowly at a speed of 0.31 m/s for the 100 readings. A low speed was selected to simulate IoT application where a customer walks in a shopping mall. As seen in Fig. 5, the resulting points from the proposed combined method are mostly above 0.5 m from the actual path of the target, but comparatively, the combined method has more points that are closer to the actual path than the other two method.

   Fig. 5. Moving test with K=3 using combined method for LOS scenario

   1. Non Line of sight scenario

      Fig. 6. Test area layout for non-LOS scenario

      –

      To test the robustness of the algorithm, it was tested under non-LOS conditions. For this, a room, which is located at the end of a narrow corridor, was selected as the test area. Fig. 6 shows this area with the locations of the nearby access points. The test location was chosen as (2.6, 2) such that it does not have LOS from any of the access points.

      Table VI. Stationary test parameters for non-LOS scenario

      Parameter	Value
      RF propagation	Non-LOS
      No of RP	16
      Area size	5m x 3m
      Origin	RP14
      X-axis direction	RP14RP16
      Y-axis direction	RP14RP1
      Test location (xt,yt)	(2.6, 2)
      User speed	N/A
      Readings	100
      Kd and Kp	K

      The test results in Table VII shows that the proposed algorithm performs better in terms of both accuracy and precision over the other two individual methods.

      Table VII. Results for different K in non-LOS scenario

      K	Distance		Probabilistic		Combined
      	Error (m)	Pre (%)	Error (m)	Pre (%)	Error (m)	Pre (%)
      3	0.6745	73	0.7814	73	0.5362		91
      4	0.6916	68	0.9521	29	0.6019		87
      5	0.703	91	0.7676	77	0.5678		95
      6	0.6282	82	0.6845	99	0.4968		99
      7	0.5939	87	0.471	98	0.4025		99

      The lowest average error of 0.4025m and highest precision of 99% for error below 0.9m were obtained by the combined method when K=7, and the results are illustrated in Fig. 7.

      In Fig. 7, it can be seen how the results of combined method are clustered closer together. This implies that the precision of the combined method is higher as seen in Table VII. A moving test was performed with the test parameters shown in the following Table VIII.

      Fig. 7. Stationary test with K=7 using combined method or non- LOS scenario

      Table VIII. Moving test parameters for non-LOS conditions

      Parameter	Value
      RF propagation	Non-LOS
      No of RP	16
      Area size	5m x 3m
      Origin	RP14
      X-axis direction	RP14RP16
      Y-axis direction	RP14RP1
      Between points	(0,2.2) (4.5,2.2)
      User speed	0.29 m/s
      Readings	100
      Kd and Kp	7

      Parameter	Value
      RF propagation	Non-LOS
      No of RP	16
      Area size	5m x 3m
      Origin	RP14
      X-axis direction	RP14RP16
      Y-axis direction	RP14RP1
      Between points	(0,2.2) (4.5,2.2)
      User speed	0.29 m/s
      Readings	100
      Kd and Kp	7

      As in previous section, the apparatus was moved in a straight line back and forth for the 100 readings. The results are shown in Fig 8.

      Fig. 8. Moving test (K=7) using deterministic method for non-LOS

      Unlike in the LOS scenario, in the non-LOS case the algorithm tracks the target more precisely along the actual path. All three methods provide target location within 0.5m of the actual path. However, only the deterministic method tracked the target along the path for more distance than the other two methods whose results were concentrated. Further coordinates were not received when the target was near the wall at location (0, 2.2).

   2. Observations

   After the tests, the accuracy and error results can be used to compare the combined methods performance in terms of accuracy and average error with those of deterministic and

   abilistic methods.

   Fig. 9. Accuracy and Precision comparison of the combined method for LOS and non-LOS scenarios for combined method

   As seen in Fig. 9, when K<5, the combined method performs with an average error <0.7m and precision >84% for both LOS and non-LOS conditions. For the same conditions, the deterministic and probabilistic methods have a higher accuracy and lower precision than the combined method as seen in Fig. 10 and Fig. 11 respectively.

   For all K under LOS conditions, the performance of the combined method is better than the deterministic and probabilistic methods. However K<5 values provide the best performance for all situations.

   Fig. 10. Accuracy comparison of deterministic, probabilistic and combined methods for LOS and non-LOS scenario

   Fig. 11. Precision comparison of deterministic, probabilistic and combined methods for LOS and non-LOS scenarios

4. CONCLUSIONS

In conclusion, for a stationary target device, the proposed combined algorithm achieved a maximum precision of 88% under LOS conditions with K=3 and a maximum precision of 99% was achieved under non-LOS conditions was with K=6

and K=7. Accuracy of the proposed algorithm remained stable around 0.5m for all K under non-LOS conditions, while it degraded with increasing K for LOS conditions. In addition, the proposed fingerprinting algorithm with combined method achieved a 91% precision and accuracy of less than 1m when K=3 and K=4 for both LOS and non-LOS conditions. Therefore, it was concluded that the proposed algorithm can be used for localization under any RF conditions using K<=4 with satisfactory overall performance with high accuracy, precision and robustness. Overall, the combined method performed better than both deterministic and probabilistic methods for all situations. For a moving target, the algorithm, using deterministic method, performed better under non-LOS conditions by tracking it with less deviation from the actual path. However, further research needed to be done to track a mobile target precisely along its path in an indoor environment

REFERENCES

1. D. Macagnano, G. Destino, and G. Abreu, "Indoor positioning: A key enabling technology for IoT applications," in Internet of Things (WF-IoT), 2014 IEEE World Forum on, 2014, pp. 117- 118: IEEE.

2. P. Prasithsangaree, P. Krishnamurthy, and P. Chrysanthis, "On indoor position location with wireless LANs," in Personal, Indoor and Mobile Radio Communications, 2002. The 13th IEEE International Symposium on, 2002, vol. 2, pp. 720-724: IEEE.

3. K. Kaemarungsi and P. Krishnamurthy, "Modeling of indoor positioning systems based on location fingerprinting," in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004, vol. 2, pp. 1012-1022: IEEE.

4. Z. Farid, R. Nordin, and M. Ismail, "Recent advances in wireless indoor localization techniques and system," Journal of Computer Networks and Communications, vol. 2013, 2013.

5. C. Rizos, A. G. Dempster, B. Li, and J. Salter, "Indoor positioning techniques based on wireless LAN," 2007.

6. R. Ma, Q. Guo, C. Hu, and J. Xue, "An improved WiFi indoor positioning algorithm by weighted fusion," Sensors, vol. 15, no. 9, pp. 21824-21843, 2015.

7. X. Song, F. Yang, L. Ding, and L. Qian, "Weight adjust algorithm in indoor fingerprint localization," in Signal Processing and Communication Systems (ICSPCS), 2012 6th International Conference on, 2012, pp. 1-5: IEEE.

8. H. Liu, H. Darabi, P. Banerjee, and J. Liu, "Survey of wireless indoor positioning techniques and systems," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), vol. 37, no. 6, pp. 1067-1080, 2007.

9. K. Kaemarungsi and P. Krishnamurthy, "Properties of indoor received signal strength for WLAN location fingerprinting," in Mobile and Ubiquitous Systems: Networking and Services, 2004. MOBIQUITOUS 2004. The First Annual International Conference on, 2004, pp. 14-23: IEEE.

10. A. Bose and C. H. Foh, "A practical path loss model for indoor WiFi positioning enhancement," in Information, Communications & Signal Processing, 2007 6th International Conference on, 2007, pp. 1-5: IEEE.

11. V. Patmanathan, "Area localization using wlan," KTH Electrical Engineering, 2006.