TMCnet News

A Novel Interpolation Fingerprint Localization Supported by Back Propagation Neural Network [Sensors & Transducers (Canada)]
[April 22, 2014]

A Novel Interpolation Fingerprint Localization Supported by Back Propagation Neural Network [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: In view of people's increasing demand for location-aware service, high-accuracy indoor localization has been considered the top priority of location-based service (LBS), therefore, the compact and cost-effective ZigBee technology with low power dissipation will undoubtedly be taken as one of the options for indoor localization within small area. As the accuracy cannot satisfy the application requirement, traditional localization ZigBee-based algorithm is abandoned gradually. This paper proposes a novel ZigBee-based indoor fingerprint localization algorithm and optimizes it through back propagation neural network (BPNN) interpolation method. Simulation result shows that this algorithm can significantly reduce the number of fingerprints and improve localization accuracy. Copyright © 2013 IFSA.



Keywords: Location fingerprint, ZigBee, BPNN, Location-aware.

(ProQuest: ... denotes formulae omitted.) 1. Introduction Among many military, industrial and consumer applications, such as battlefield surveillance, robotic land-mine detection, industrial monitoring and control, health monitoring, environmental monitoring, traffic regulation, the location information plays an important role in understanding the application context. An ideal wireless positioning system should be flexible and robust to the required transmission quality (Quality of Service) [1-3]. Furthermore, modem localization systems should have a low-cost and power conservation. The accurate, robust and reliable localization algorithm is necessary [4-6]. Therefore, the compact and costeffective ZigBee technology with low power dissipation will undoubtedly be taken as one of the options for indoor localization within small area [7, 8]. There is multipath fading, diffraction and other phenomena to influence the localization accuracy [9-11]. In order to achieve higher localization accuracy, it's necessary to acquire more data during offline stage, which will inevitably bring about significant increase in workload and calculation load of location algorithm at such stage. BPNN, as a typical feed forward neural network, boasts a number of excellent features and capacities such as massive parallel processing capability, distributed information storage, extraordinary fault tolerance and robustness, outstanding adaptive capacity and perfect selflearning capacity. To find an effective way to obtain location fingerprint constitutes the most difficult challenge to offline stage [12-15]. This paper will discuss about ZigBee-based indoor fingerprint localization, proposes a spatial correlation based BPNN interpolation algorithm for creation of fingerprint database to improve this algorithm so as to enhance the indoor localization accuracy.


The remainder of this paper is organized as follows: We overview the fingerprint-based localization algorithm in Section 2. In Section 3, we review BPNN algorithm. Section 4 discusses BPNN interpolation localization based on ZigBee in detail, Section 5 gives simulation results and analyzes, Section 6 makes a conclusion and outlines the future work.

2. Overview of Fingerprint-Based Localization Location fingerprint refers to the special relationship between a specific location and some certain measurable physical stimulation (i.e. received signal strength). Location fingerprint-based localization method is normally divided into two stages, i.e. offline stage and localization stage. As for offline stage, a series of test reference points are set up in coverage area of LBS; at each reference point, the signal strength samples receiving several wireless access points (AP) are captured to create signal coverage diagram for coverage area, also known as the signal space. The received signal strength vector at each reference point is the location fingerprint of such point. By reason that it's necessary to carry out actual measurement of multiple reference points at offline stage, the workload significantly increases with the expansion of coverage area; as for localization stage, in case of any need for localization, AP signals received by client would be sampled in real time at localization stage. The matching between client-side location and the location in signal coverage diagram is realized for localization through application of specific signal space to search matching algorithm based on signal coverage diagram or signal coverage model. Deterministic method is a principal method in location fingerprint, which measure and save the mean value of received signal strength within certain sampling period at offline stage, and then to judge the matching between two signal strength values through neighbor matching algorithm at localization stage.

2.1. Localization by Deterministic Method Detailed localization process by deterministic method: at offline stage, a series of test reference points are set up in coverage area of LBS; at each reference point, the signal strength samples receiving several APs are captured to create signal fingerprint database for coverage area. Signal fingerprint database keeps the information about signal sample. Deterministic method is considered deterministic because such information as the average and maximum values of signal sample other than the signal strength probability is stored; at localization stage, client-side signal is subjected to real-time sampling based on signal coverage diagram established at offline stage, and then the localization is realized through the matching between client-side location and the location in signal coverage diagram by application of specific signal space to search matching algorithm [16]. We establish 6 ZigBee fixed points, therefore the signal strength sample vector can be expressed as: r=(^,x2,...^6). A train of samples would be obtained after a period of sampling. For the sake of simplicity and high efficiency, the signal coverage diagram only stores the mean sample ravg={xx X2 ... x6) of received signal strength at each reference point. Besides of mean sample of signal strength, it's also important to record the location coordinates of such reference point, which can be expressed as formula (1): ...(1) where Xi,yi means the location coordinates of reference point; XliX2...X6 represents the mean vector element value of received signal strength; N represents the number of AP. In case of any need for localization, it's possible to detect AP signal in ZigBee environment through wireless network card of client and get more than one received signal strength sample within a relatively short period of time. Similarly to the offline stage, it's possible to obtain the mean sample of received signal strength at client side. Furthermore, such samples can be matched with signal strength samples in signal coverage diagram at offline stage using neighbor matching algorithm.

2.2. K-nearest Neighbor Matching Algorithm Neighbor matching algorithm can be classified into nearest neighbor in signal space (NNSS) matching algorithm and k-nearest neighbor search (KNNS) matching algorithm. In essence, both algorithms take reference points with less significant difference as reference points near client after determining the difference between the strength of signal received at client side and the received signal strength at reference point stored in signal coverage diagram. Furthermore, nearest neighbor matching algorithm is used for localization by directly taking the neighbor coordinates as client's actual estimated location, while K neighbor matching algorithm is used to determine the actual estimated location of client after certain processing of coordinates of more than one neighbor. K neighbor matching algorithm takes into account a number of possible neighbors, and thus boasts better robustness when compared with the nearest neighbor [17, 18].

To be specific, it's possible to express the difference between the received signal strength at client side and the received signal strength at reference point stored in signal coverage diagram by determining the distance Dj of received signal strength vector and the storage vector of some certain reference point in signal coverage diagram. The expression is as follows: ...(2) Wherein, N stands for the number of AP; x] means the element of received signal strength vector; xi represents the element of stored vector. When p=l, Dx is referred to as the Manhattan distance; when p=2, D2 is referred to as Euclidean distance. The latter, i.e. the Euclidean distance D2, is more often taken as reference criterion during the course of study. At this point, the equation above further evolves into formula (3).

...(3) 3. BPNN Algorithm BP network for location fingerprint localization is composed of input layer, hidden layer and output layer [19-21], which as shown in Fig. 1. Input layer has 8-dimensional vector composed of signal strengths (RSSI) of 6 APs received at measurement node and their respective location coordinates (x, y).

...(4) The number of neurons at hidden layer can be figured out with empirical equation, i.e. N2 > log2 T , wherein N2 is the number of neurons at hidden layer, while T represents the dimension of training sample. Increase of the number of neurons at hidden layer helps to improve localization accuracy yet bring about heavier calculation load. In view of the fact that this paper uses a relatively small number of samples and attaches more importance to accuracy, 18 neurons are selected at hidden layer. The transfer function at hidden layer is sigmoid function f (x) = tanh(x) , of which the input value can be arbitrary value, while the output value can be between -1 and +1.

The output layer is composed of 9 neurons and employs linear transfer function Purelin, i.e. fi (x) = kx whose output is the interpolation of fingerprint database. The output vector is given formula (5).

... (5) Learning algorithm for BP network is as follows: assuming that the input layer is P, the number of input neurons is r, there are si neurons at hidden layer, the corresponding activation function is fx, there are s2 neurons at output layer, the corresponding activation function is f2, the output is A, and the target vector is T. wxj represents the connection weight between input layer and hidden layer, while w^ represents the connection weight between hidden layer and output layer.

The output of the ith neuron at hidden layer: ... (6) Output of the Xth neuron at output layer: ... (7) Definition error function: ...(8) Determine the weight variation and the backpropagation of error using gradient-descent algorithm; the change in the weight of output layer is proportional to the negative gradient of error function against the weight of output layer: (9) The weight of output layer is updated according to formula (10): ......(10) Change in the weight of hidden layer is proportional to the negative gradient of error function against the weight of hidden layer: ...(11) The weight of hidden layer is updated according to formula (12): ...(12) 4. BPNN Interpolation Localization Based on ZigBee Wireless signal space propagation model shows that the RSSI value exhibits strong spatial correlation with an obvious and continuous variation tendency. In other words, the RSSI values received by client with neighboring space from wireless signals transmitted by fixed ZigBee nodes at a number of spatial locations are close to each other. Where the spatial distance between test points is below some certain threshold, the RSS value of test points would almost be the same. From this point of view, it's important to establish a fine-grained location fingerprint database when there are a relatively small number of measurements by obtaining the RSSI vector of adjacent location through BPNN interpolation based on the measured RSSI value of adjacent client on grid and the spatial correlation characteristics of RSSI value. In this way, it's possible to slash the workload at offline stage without impairing online matching precision.

4.1. Input Layer Input neurons can only broadcast input vector to hidden layer so that each component of input vector can be transferred to each neuron at next layer according to certain weight. BPNN takes the RSSI vector [R1,R2,R3,R4,R5,R6] received by client and the location coordinate [x,y] of such client as a sample in interpolation. In order to realize bidirectional signal transmission, 2 vectors in each sample are juxtaposed to compose an n+2-dimensional vector [r\,r2,r3,r4,r5,r6,x,y] as both input X and the ideal output thereof; therefore, such network can achieve the identical transformation of all samples in the best case. Thus, the input layer would have (n+2) neuron nodes, and according to BPNN structure, the output layer should also have (n+2) nodes, whose output vector Y should be [R\,R2,R\M,R5,R6,X\,Y\].

4.2. Hidden Layer The number of neuron nodes at this layer indicates the number of partitioning of input samples. The more nodes this layer has, the more precise the partitioning would be, and the higher the accuracy of output result would be. In the most extreme case, each sample is seen as a separate category, and this may lead to more time-consuming algorithm. From this point of view, it's important to make a trade-off between accuracy and training time. According to the requirements of localization algorithm, it's believed that the number of nodes at hidden layer is related to the indoor area of plane. In other words, the indoor plane can be divided into several blocks of equal size; due to the spatial correlation, the RSSI vector and location coordinate vector of client in each block would exhibit similarity, and each block serves as a category. Nodes are fully connected between input layer & hidden layer and between hidden layer & output layer. The weight of each edge is expressed as Wjj , wherein means the node number of input layer, and "j" stands for the node number of hidden layer. Assuming that the hidden layer has "n" node(s), all weights between input layer and hidden layer can be expressed by vectors as formula (13).

...(13) 4.3. Output Layer This layer has (n+2) nodes of which each is fully connected with nodes at hidden layer. The weight of each edge is expressed as vß, wherein "j" means the node number of hidden layer, and "k" stands for the node number of output layer. Thus, the weight vector between these two layers can be expressed as: ...(14) The specific localization steps as shown in Fig. 2: 5. Simulation Experiment For data acquisition, we employed the ZigBee chip CC2530 as my experiment hardware module, which is system on chip (SOC) scheme produced by Texas Instruments (TI), comply with IEEE 802.15.4 standard. The experiment testbed comprises 6 AP nodes, one coordinator, one hub and one mobile node. Coordinator fulfill channel allocation, network configuration, and establish a wireless LAN at our experiment site. The AP nodes offer the coordinates reference. The hub is responsible for packet relay. Our experimental scenario make up of four areas, including a studio, a conference room, two offices. Fig. 3 shows the plans of experimental scenarios and their network segmentations, respectively. A sufficient number of test points are used to determine the signal strength at the seven APs so as to establish a model fingerprint database.

In order to evaluate the algorithm presented in section 4, the localization result of original sampling database is compared with the database localization result obtained through interpolation below. It's possible to get more signal fingerprints by writing BPNN interpolation program with Matlab. In order to show the algorithm's validity, we compare the original algorithm without BPNN interpolation sampling and our algorithm with the BPNN interpolation; each algorithm is divided into 6 different phase by mobile node granularity. The test points are respectively 52, 104, 208, 416, 832 and 1646.

As shown in Fig. 4, when there are 52, 104, 208, 416, 832 and 1646 test points, the location distance error of BPNN interpolation algorithm is 4.0, 3.2, 2, 9, 3.0 and 2.7, respectively, all of which are lower than that of the method without BPNN interpolation. This means NPNN interpolation algorithm is a effective method that helps to significantly improve localization accuracy.

6. Conclusions The paper proposes ZigBee-based BPNN interpolation fingerprint localization on the basis of intensive study on fingerprint localization and BPNN. It is observed from the comparison between the localization results of two algorithms (i.e. without and without BPNN interpolation) that BPNN interpolation algorithm is a practical indoor wireless location algorithm, which can help to effectively improve the localization accuracy. Moreover, the compact and cost-effective ZigBee with low power dissipation also provides a satisfactory option for small-area Wireless LAN localization with low cost and low power dissipation. However, there are some issues need to solve in the future, such as the wireless network topology optimization, protocol cross optimization, energy-saving MAC, the channel allocation tactics, the security problem also is urgent. For the algorithm, the multi-algorithm fusion is a good alternative.

Acknowledgements The authors would like to thank the Natural Science Foundation of Guangdong Province, China (No.9151009001000021, S2011010001155), the Ministry of Education of Guangdong Province Special Fund Funded Projects through the Cooperative of China (No. 2009B090300 341), the National Natural Science Foundation of China (No. 61262013), the High-level Talent Project for Universities, Guangdong Province, China (No. 431, Yue Cai Jiao 2011), the Chinese Society of Vocational and Technical Education 2012-2013 scientific research and planning projects (No. 204921), and 2013 Higher vocational education teaching reform project of Guangdong province(No. 20130301011) for their support in this research.

References [1]. Jianqi Liu, Q. Wang, Jiafu Wan, J. Xiong, Zeng, Towards key issues of disaster aid based on wireless body area networks, KSII Transactions on Internet and Information Systems, Vol. 7, No. 5, 2013, pp. 1014-1035.

[2]. Jiafu Wan, S. Ullah, C. Lai, M. Zhou, X. Wang, C. Zou, Cloud-enabled wireless body area networks for pervasive healthcare, IEEE Network, Vol. 27, No. 5, September 2013, pp. 56-61.

[3]. Jiafu Wan, H. Yan, H. Suo, F. Li, Advances in cyberphysical systems research, KSII Transactions on Internet and Information Systems, Vol. 5, No. 11, November 201 l,pp. 1891-1908.

[4]. X. Wang, A. V. Vasilakos, M. Chen, Y. Liu, T. T. Kwon, A survey of green mobile networks: Opportunities and challenges, Mobile Networks and Applications, Vol. 17, No. 1,2012, pp. 4-20.

[5]. M. Chen, A. V. Vasilakos, D. Grace, Advances in green mobile networks, Mobile Networks and Applications^ol. 17, No. 1,2012, pp. 1-3.

[6]. M. Chen, Towards smart city: M2M communications with software agent intelligence, Multimedia Tools and Applications, 2012, pp. 1-12.

[7]. Shahin Farahani, ZigBee wireless networks and transceivers, Elsevier, New York, 2011.

[8]. S. Agatonovic-Kustrin, R. Beresford, Basic concepts of artificial neural network (ANN) modeling and its application in pharmaceutical research, Pharmaceutical and Biomedical Analysis, Vol. 25, No. 5,2000, pp. 717-727.

[9]. Jianqi Liu, Q. Wang, et al., A novel wireless 3D localization method supported by WSN, International Journal of Online Engineering, Vol. 9, No. 2, 2013, pp. 9-12.

[10]. Jianqi Liu, Qinruo Wang, Jiafu Wan, Jianbin Xiong, Towards real-time indoor localization in wireless sensor networks, in Proceedings of the 1201 IEEE International Conference on Computer and Information Technology (CIT'2012), SiChuan, China, October 2012, pp.878-884.

[11]. M. Chen, Towards smart city: M2M communications with software agent intelligence, Multimedia Tools and Applications, 2012, pp. 1-12.

[12]. G. I. Mary, V. Prithiviraj, Improved UWB localization technique for precision automobile parking system, in Proceedings of the IEEE Region 10 Annual International Conference (TENCON' 08), Hyderabad, India, 19-21 November 2008, pp. 489-494.

[13]. Zang Li, Chao-Hsien Chu, Wen Yao, SIP-RLTS: An RFID location tracking system based on SIP, in Proceedings of the 2008 IEEE International Conference on RFID (Frequency Identification), Las-Vegas, NV, 16-17 April 2008, pp. 173-182.

[14]. Wan Cinder, Wei Tong, Positioning and tracking with NLOS mitigation using extended Kaman filter in UWB systems, in Proceedings of the International Conference on Pervasive Systems and Computing, 2005, pp. 71-77.

[15]. T. Roos, P. Myllymäki, H. Tirri, et al., A probabilistic approach to WLAN user location estimation, International Journal of Wireless Information Networks, Vol. 9, No. 3, 2002, pp. 155-164.

[16]. N. Antiknock, R. Kookier, Neural network approach to prediction of bending strength and hardening behavior of particulate reinforced (Al-Si-Mg) aluminum matrix composites, Materials and Design, Vol. 25, No. 7,2004, pp. 595-602.

[17]. G. E. Hinton, R. J. Williams, et al., Representation by back propagation errors, Nature, Vol. 3, No. 6, 1986, pp. 899-905.

[18]. D. Sengupta, R. Iltis, A neural solution to the multitarget tracking data association problem, IEEE Transaction on Aerospace and Electronic System, Vol. 25, Issue 1,1989, pp. 96-108.

[19]. Ma Changlin, R. Klukas, G. Lachapelle, An enchanted two-step least squared approach for TDOA/AOA wireless localization, in Proceedings of the International Conference on Communications {ICC 2003), Anchorage, Alaska, USA, Vol. 2, 2003, pp. 987-991.

[20]. R. Ertel, P. Cardieri, K. W. Sowerby, et al., Overview of spatial channel models for antenna array communication systems, IEEE Personal Communications^ol. 5, 1998, pp. 10-22.

[21]. J. H. Han, D. K. Jeon, Comparisons of error characteristics between TOA and TDOA positioning, IEEE Transactions on Aerospace and Electronic Systems, Vol. 38, No. 1,2002, pp. 307-311.

1 Jianqi LIU,2 *Huaping ZHOU,1 Cuisong CHEN 1 College of Information Engineering, Guangdong Jidian Polytechnic, Guangzhou, China 2 Faculty of Computer Science & Engineering, Anhui University of Science and Technology, HuaiNan, China E-mail: [email protected], [email protected] Received: 9 September 2013 /Accepted: 25 October 2013 /Published: 30 November 2013 (c) 2013 International Frequency Sensor Association

[ Back To TMCnet.com's Homepage ]