International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Menu

ISSN ONLINE(2278-8875) PRINT (2320-3765)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

RSS Based Indoor Localization Scheme Using GRNN and Virtual Grid-Points

Jung-Hyun Lee1, Seung-Joo Lee1, Youngil Park1, Ki-Bang Yun2, Ki-Doo Kim1*
  1. School of Electrical Engineering, Kookmin University,861-1 Jeongneung-dong, Seongbuk-gu, Seoul 136-702, Korea
  2. Dept. of Electronic Engineering, University of Incheon, 119Academi-ro, Yeonsoo-gu, Incheon406-772, Korea
Corresponding Author: Ki-Doo Kim, Tel: +82-2-910-4707; Fax: +82-2-910-4449
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

Traditional RSS based self-localization for low cost Wireless Sensor Networks (WSN) suffers from lesser accuracy due to computational and memory resource limitations. In addition, an indoor wireless channel is influenced by so many factors that deriving the optimized propagation loss model for low cost WSN devices becomes difficult. In this paper, we present a flexible location estimation algorithm using a generalized regression neural network (GRNN) and virtual grid points, which is capable of learning the ever-changing wireless channel behaviour without the use of a specific propagation loss model.In the proposed scheme, a virtual grid concept is added to achieve a better refinement of the GRNN based algorithm and to overcome the disadvantages of conventional RSS based localization. The experimental results demonstrate that the proposed algorithm obtains a more precise location when compared to the conventional GRNN location estimation scheme

Keywords
RSS, GRNN, Localization, WSN, Virtual grid-points

INTRODUCTION
With the rapid growth of IT, network infrastructures are expanding widely to make the ubiquitous world a reality, where users can access any network freely regardless of place. As a part of this ubiquitous world, the location of an object will become essential information. For this reason, the Location Based Service (LBS) creates added value and offers various services through obtaining and sharing the location information for persons and objects. For example, LBS can be applied when searching for a missing child in a large-scale shopping mall and providing the optimal route to the users or for finding the logistics of an object moving in products and distribution. In addition to those examples, localization applications in large industry are expected to develop rapidly [1-5]. Various techniques for location estimation exist. The TDOA (Time Difference of Arrival) protocol uses two types of signals of different speeds to obtain the distance information. The hardware needed for TDOA is comparatively expensive and it consumes a great deal of energy. Therefore this method is not suitable for low power sensor network devices [6]. TOA (Time of Arrival) is a general way of obtaining the distance information through the spread time of the signals. As there are limiting factors concerning the hardware embedded in the sensor network device and the battery capacity, this method requires a somewhat large capital investment. The RSS (Receive Signal Strength) protocol is a methodof calculating the distance by using signal sensitivity, which estimates the distance by comparing the information with a database of the distance of the prior signal reception. This technique is relatively simple to deploy compared to the other techniques. Moreover, no extra hardware is needed for location estimation. However, due to the serious multi-path propagation in an indoor environment [6] accurate positioning is very difficult. Therefore, in order to overcome this problem, we will co-opt the concept of the virtual grid points used in Ecolocation. Ecolocation stands for “Error ControllingLOCAliza-TION”, which is a localization method that puts a priority on the strength of the RSS value [7, 8]. Ecolocation can correct the error in the case of estimating a higher RSS value, even though the distance from the target to the reference node is further. In Ecolocation, the virtual grid point is defined as the point where the grid lines intersect each other. This can be applied to correct errors through the comparison of the position (coordinate value) of a virtual grid point and the position (coordinate value) of the node.
The GRNN (Generalized Regression Neural Network) function approximation applies the concept of statistical regression analysis, which is used to improve the performance of localization. For instance, the GRNN and WCL (Weighted Centroid Localization) methods are applied in RSS-based localization [9, 10]. In the present work, we propose a GRNN and virtual grid based localization algorithm which refines the use of only the GRNN method to overcome the disadvantages of conventional RSS-based localization. The proposed algorithm is subdivided into two parts. In the first part, the first GRNN set is trained by using location coordinates (x, y) and the corresponding RSS values of the reference nodes as inputs and outputs, respectively. After that, the RSS values of the virtual grid-points are found by using the GRNN set. In the second part, a second GRNN set is trained by the RSS values as inputs and the coordinates (x, y) as outputs, using the virtual grid point's RSS data and coordinates (x, y). Finally, the position of the target node is determined by using the second GRNN set. This paper is organized as follows. In Section 2, the related techniques and the proposed algorithm are described. In Section 3, the simulation and experimental results are discussed. The conclusion of this paper is presented in Section 4.

RELATED TECHNIQUESANDTHE PROPOSED ALGORITHM
The RSS System
Fig.1 shows the structure of the proposed RSS based indoor localization system. The Access Points (AP) measure and gather the RSS from all of the reference nodes. The information regarding the location coordinates (x, y) of all the reference nodes is then matched with the RSS values of the corresponding reference nodes. The APs also gather the RSS values of the unknown target node and send these data to the central server for further processing. Fig. 1 shows a system arrangement using 25 reference nodes, 4 APs, and 1 target node. The location estimation process is done by the central server.
image
The Grid Points
The grid points are the virtual points where the perpendicular grid lines meet each other. In this work, the grid points are used as the positions of the virtual sensor nodes. By using the grid points, the accuracy becomes more precise as the number of sensor nodes increases. The location coordinate and corresponding RSS value of each grid point works as a virtual sensor node. The GRNN training set, which is composed of the data from the reference nodes, is used to obtain the RSS value for each grid point. The training process is performed in the central server. All of the grid points contain location coordinates and the corresponding RSS values as for the actual reference nodes.Therefore, each grid point acts as a virtual sensor node.
The GRNN Method
Neural Networks (NN) have been used in various fields including localization. GRNN and Multi-Layer Perception (MLP) are two well-used types of networks. GRNN was proposed by Specht [11] and its computational speed is very fast because it does not need an iterative training for converging to a wanted solution [12]. In this paper, the GRNN method, which can set up training set with simple manipulations, is used instead of the MLP method which needs more time to set its layers, since the localization has to be processed in real-time [13].The input and output layers define the information data and the parameter to be predicted, respectively. The pattern and summation layer are the domains in charge of operating the actual GRNN. The data is used to determine the analogous map of the patterns in a pattern layer when the nth input data is input to the GRNN. This obtained analogous map is multiplied to an actual matching pattern result value. By regularizing in the sum layer, we can obtain the final predictive value. In other words, through comparing patterns following the degree of similarity to a pertained degree, the resulting value of the pattern is used as a part of the predictive value [14]. The GRNN training set consists of an input, output and GRNN spread. The input and output usethe data obtained from experiment and observance; the GRNN spread is the probable component used to set it up.Small spread value improves the performance of a simple formula, whereas in the case of a complicated formula, a large spread value improves the performance [15].
The Proposed Algorithm
The proposed GRNN and virtual grid point based localization algorithm is described in Fig. 2. The algorithm is performed as follows:
1. Compose a GRNN training set using the location coordinate values and the RSS values of the reference nodes.
2. Train regarding to the RSS value of grid point using the training set from the 1st step.
3. Compose another GRNN training set by setting the coordinate value of the grid points as the output and the RSS values as the input obtained from the 2nd step.
4. Estimate the position coordinates of the target node by using the training set from the 3rd step.
image
The localization computation is performed in the central server using the training data sent from the APs. Whenever a GRNN training set is composed, it goes to the step of changing a spread constant if the error is greater than the set-up target (targeted error value). InFig. 2, the first target is a targeted error value for the RSS (dB) and the second target is a targeted error value for the position error (m). A final target value is determined after performing many experiments and its flexibility depends on the environment.

THE SIMULATIONAND EXPERIMENT RESULT
The simulation was performed using MATLAB. This section describes the experiment environment and results.
Experiment 1
The simulation of this algorithm is done using real data obtained from Patwari et al. [16] that has coordinate values and their corresponding RSS from the sensor nodes in an actual office.
1) The Experiment Environment: The experimental environment and parameters used during the RSS data collection are explained in [16, 17]. The measurements were implemented inside an office partitioned by 1.8 meter high cubicle walls with hard partitioned offices, external glass windows, and cement walls surrounding the outside of the area. The office contained metal and concrete support beams, office desks, bookcases, metal and wooden filing cabinets, computers, and other various office equipments. There were 44 nodes inside the room, each having a coordinate value and a corresponding RSS value [17].
image
In Experiment 1, as shown in Fig. 3, 4 nodes near the corners (black circles) are chosen as the sink nodes (APs) and each of the remaining 40 sensor nodes (green rectangles) has an RSS value with a corresponding coordinate value. The RSS of the target node is assumed to be known and the value of the coordinates (position) has to be determined. Among the 40 sensor nodes, one node was assumed to be a target node and the other 39 sensor nodes were selected as reference nodes. After training the grid points (small dots) by the reference nodes, the position of the target node is measured. This process is repeated for the remaining 39 target nodes. In Experiment 1, the entire area is 15m x 15m. The grid point density and the spacing between the grid points were varied over three types: 36 (6x6) grid points with 3m horizontal and vertical spacing, 121 (11x11) grid points with 1.5m horizontal and vertical spacing, and 256 (16x16) grid points with 1m horizontal and vertical spacing.
2) The Experiment 1 Results: Table I shows the average error according to the number of grid points. Each spread value in table 1 is chosen in such a manner that makes the average error of the 40 target nodes smallest. As shown in table 1, when the
position is measured using the 256 grid points, it provides the best results from the average error point of view. The execution time of position measurement does not show any difference among the three cases. Therefore, from the results of Experiment 1, we set the number of grid points to 256.
image
Fig. 4 shows the CDF of the accuracy (probability of being located within the error range) and the precision (distance error) from Experiment 1. The dottedline indicates the result of the position measurement by applying the GRNN algorithm with 256 grid points and the solid line indicates the position measurement result when applying only the GRNN. When the location error of the horizontal axis is 1m, the cumulative probability of the vertical axis location error is almost 0.25 (25%) for the dotted line and 0.1 (10%) for the solid line. This means that the GRNN using the grid point algorithm has a location error of less than 1m as 25% (10 nodes out of 40 nodes) whereas the only GRNN algorithm has a location error below 1m of only 10% (4 nodes out of 40 nodes). The situation represented by the dotted line in the graph is slightly better than that found for the solid line. This means that the GRNN using grid points obtains a better performance than when only using the GRNN in position measurement.
image
The bar graph in Fig. 5 shows the position error of the 40 target nodes. Fig. 5(a) shows the position error for each target node when we apply only the GRNN; Fig. 5(b) represents the position error for each target node when we apply the GRNN with grid points. The position measurements using only the GRNN may be better in location errors for a few target nodes, whereas most of the targets possess a more accurate position measurement when we use the GRNN with grid points. Therefore, the superior performance in position measurement is found by using the GRNN with grid points. In the aspect of average error, Fig. 5(a) and 5(b) delineate 2.18m and 1.83m, respectively. This means that the grid point based method shows a 0.35m more accurate localization result.
image
Experiment 2
In Experiment 2, the GRNN training set is composed of the more accurate reference nodes extracted from Experiment 1. We then carried out the localization using the GRNN training set. The results from Experiment 2 are then compared to those of Experiment 1.
1) The Experiment Environment: In Fig. 6, 25 reference nodes (squares with cross) having a position error of less than 2m are selected from the results of Experiment 1. After 256 grid-points (red dots) are trained by using 25 reference nodes, the localization for the 40 target nodes will be performed.
image
Fig. 6 The simulation setup for the indoor location estimation(4 APs, 25 reference nodes, and 256 grid-points are placed within a 15 x 15m area)
In Experiment 2, the number of reference nodes are set using four different types, such as 4 (2x2), 9 (3x3), 16 (4x4), and 25 (5x5). The reference nodes of each type were selected from the sensor nodes having a location error less than 0.5m, 1m, 2m, 2m, respectively from the results of Experiment 1, and were formed into a lattice structure as a possible way to improve the location estimation performance. In Fig. 6, we follow the same procedure as done in Experiment 1 to carry out the location measurement. If one of reference nodes is selected as the target node, the location measurement is carried out using the rest of the reference nodes excluding the target node. In the location estimation system using 25 reference nodes, the location is obtained by applying the 24 reference nodes.
2) The Experiment 2 Results: Table II presents the relationship between the number of reference nodes and the average error. Each spread is the optimal value needed to make the average error of the 40 target nodes smallest. In terms of performance for the average error, the location estimation system using the 25 reference nodes is the best, as can be seen in table 2. Under the same conditions, the simulation results show that the average error is 1.83m in Experiment 1 and 1.21m in Experiment 2 when we use the 25 reference nodes. Therefore, the Experiment 2 scheme using the extracted references clearly shows a superior error performance compared to Experiment 1.
image
Fig. 7 shows the results of Experiment 1 and 2. In this figure, the results of Experiment 1 are represented by the line with circle. The line with square indicates the results when we use 25 reference nodes in Experiment 2. The solid line and the line with cross indicate the results by using 16 reference nodes and 9 reference nodes, respectively.
image
Under the same conditions, the simulation results show that the location errorsare 1.9m and 2.3m corresponding to 25 and 40 reference nodes, respectively, when the cumulative probability of the location error is 70%. The reasonis that in the case of the 25 reference nodes for a given environment, the more accurate information regarding the grid-points can be obtained. InExperiment 2, extracting the reference nodes with more accurate information from the prior Experiment 1 results improves the localization performancewith simpler hardware construction.The remaining sensor nodes can be reused elsewhere with all the benefits that entails.

CONCLUSION
In this paper, we presented a RSS based two-phase location estimation algorithm using GRNN with virtual grid points. This improved the localization accuracy compared to the localization accuracy obtained by only using the GRNN.It has also been found that the accuracy is almost directly proportional to the reference sensor density. In addition to accuracy improvement, the proposed scheme gives a simpler hardware construction, resulting in cost savings by using virtual grid sensors instead of real sensors. The simulation results show that the location accuracy is satisfactory. In Experiment 1, we identified the superior performance in position measurement by using GRNN with grid points; the accuracy improved as the number of grid points increased. In the results of Experiment 2, extracting the reference nodes with more accurate information through the prior Experiment 1 has improved the localization performance more with simpler hardware construction.

ACKNOWLEDGMENT
This work was supported by ITRC support program of MKE Korea (NIPA-2012-H0301-12-2007) as well as by the Broadcasting-Communications R&D Program of KCC/KCA Korea (2012-11911-011111).

References
  1. M. K. Oh, M. J. Kim, and J. Y. Kim, “Low data-rate location UWB technology for ubiquitous home,” ETRI Electronics and Telecommunications Trends, vol. 21, pp. 30-39, 2006.
  2. Z. Yan, Y. Chang, Z. Shen, and Y. Zhang, “A grid-scan localization algorithm for wireless sensor network,”CMC '09, WRI International Conference on Communications and Mobile Computing, 2009.
  3. S. A. Mitilineos, D. M. Kyriazanos, O. E. Segou, J. N. Goufas, and S. C. A. Thomopoulos, “Indoor localization with wireless sensor networks,”Electromagnetics Research, vol. 109, pp. 441-474, 2010.
  4. U. A. Khan, S. Kar, and J. M. F. Moura, “Distributed sensor localization in random environments using minimal number of anchor nodes,” IEEE Transactions on Signal Processing, vol. 57, issue 5, May 2009.
  5. B. Xiao, L. Chen, Q. Xiao, and M. Li, “Reliable anchor-based sensor localization in irregular areas,” IEEE Transactions on Mobile Computing, Jan. 2010.
  6. M. Ghavami, L. B. Michael, and R. Kohno, Ultra Wideband Signals and Systems in Communication Engineering, John Wiley &Sons Ltd., UK, 2004.
  7. D. S. Hwang, “A study on localization using wireless sensor networks and position pattern,” Master’s thesis,Inha University, Incheon, Korea, Aug. 2007.
  8. K. Yedavali, B. Krishnamachari, S. Ravula, and B.Srinivasan, “Ecolocation: A sequence based technique for RF localization in wireless sensor networks,” IPSN ’05 of the 4th international symposium on Information processing in sensor networks, IEEE Press,USA, 2005.
  9. M.S.Rahman, “Algorithms of high accuracy position estimation in VLC, RFID and WSN,” Ph.D. thesis, Kookmin University, Seoul, Korea, June 2009.
  10. M. S. Rahman, Y. Park, and K.-D. Kim, “RSS based indoor localization algorithm for wireless sensor network using generalized regression neural network,” ArabianJournal of Science and Engineering, DOI 10.1007/s 13369-012-012-0218-1,Published online: 13 April 2012.
  11. D. F. Specht, “A general regression neural network,”IEEE Transactions on Neural Networks, vol. 2, no. 6, Nov. 1991.
  12. J.-D. Wu, and C.-H. Liu,“An expert system for fault diagnosis in internal combustion engines using wavelet packet transform and neural network,” Elsevier, vol. 36, Issue 3, Part 1, April 2009.
  13. A. Taok, N. Kandil, and S. Affes, “Neural networks for finger printing-based indoor localization using ultra-wideband,”Journal of Communications, vol. 4, pp. 267-275,2009.
  14. C. Nerguizian, C. Despins, and S. Affes, “Indoor geolocation with received signal strength finger printing technique and neural networks,” Telecommunication and networking– ICT, 2004, 3124/2004, pp. 866-875.
  15. G.I. Moon and H. Y. Lee, Intelligent Information System,A-JIN Publishing Co.: Seoul, Korea, 2003, pp. 1-612.
  16. Wireless Sensor Network Localization Measurement Repository.[Online]. Available: http://www.eecs.umich.edu/~hero/localize/
  17. N. Patwari, A. O. Hero Ⅲ, M. Perkins, N. S. Correal, and R. J. O’Dea, “Relative location estimation in wireless sensor networks,” IEEE transactions on signal processing, vol. 51, pp. 2137-2148, 2003.