ZigBee定位算法论文英文版

Available online at Procedia Computer Science 5 (2011) 58–65

The 2nd International Conference on Ambient Systems, Networks and Technologies (ANT)

ZigBee-based indoor location system by k-nearest neighbor

algorithm with weighted RSSI

Chih-Ning Huang, Chia-Tai Chan*

Institute of Biomedical Engineering, National Yang-Ming University, No.155, Sec.2, Linong Street, Taipei, 112 Taiwan Abstract

With the advances in information and communication technologies, wireless sensor networks has made Ambient Intelligence (AmI) applications possible that can monitor the situation around the persons or objects and give certain responses for their needs. The location awareness is an important technology for AmI applications. The advantages of ZigBee wireless sensor networks such as low cost, high scalability, high availability and supporting dynamic routing topology make ZigBee more suitable for indoor location system. In this research, we propose a ZigBEe-bAsed indoor loCatiON (ZigBEACON) system for the AmI applications. The proposed approach is based on the k-nearest neighbor algorithm. According to the Received Signal Strength Indication’s (RSSI) path loss distribution, the RSSI values are defined into four classes. The signals that belong to differentclasses will be adjusted by the different ratio and will be referred to as weighted RSSI. The use of weighted RSSI can effectively choose the p-nearest reference nodes. Finally, the position of mobile node would be derived by calculating the coordinates of p-nearest reference nodes. Comparing the results with that of ZigBee-based LANDMARC system, our approach has 29% improvement on average error distance. The approach not only improves the accuracy, but also provides less calculation complexity than other improvement methods of LANDMARC. The ZigBEACON approach is an adequate solution to the indoor location system for AmI applications.

Keywords: ZigBee; indoor location system; k-nearest neighbor algorithm

1.Introduction

Ambient Intelligence (AmI) is an electronic environment that can monitor the situation around the persons or objects and give an adequate response for their needs [1]. With the advances in Information and Communication Technologies (ICTs), Wireless Sensor Networks (WSN) has made many AmI applications possible. Context-aware technology gathers the relevant context from sensor data, and then gives a certain response. Three main aspects of context are: where you are, who you are with, and what resources are nearby [2], so the location information is one of the important context information for AmI. For instance, when a person has fallen in the AmI environment, the wearable sensor will detect the fall event and send the alarm to the caregiver who can deliver immediately help. And * Corresponding author. Tel.: +886-2-2826-7371; fax:+886-2-2821-0847.

E-mail address: ctchan@ym.edu.tw.

1877–0509 © 2011 Published by Elsevier Ltd. Open access under Selection and/or peer-review under responsibility of Prof. Elhadi Shakshuki and Prof. Muhammad Younas.doi:10.1016/j.procs.2011.07.010

Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–6559

the alarm information about where the person fell is important for caregiver that can reduce the time of finding the faller [3]. Nowadays, Global Position System (GPS) provides reliable outdoor location information. Unfortunately, the characteristic of line-of-sight transmission causes that the GPS is not workable for in-building location-based services. The main technologies of indoor location system include Radio Frequency IDentification (RFID), Wireless Local Area Network (WLAN), Bluetooth and ZigBee et al [4]. The advantages of ZigBee such as low cost, high scalability, high availability and supporting dynamic routing topology make ZigBee more suitable for indoor location system.

In this paper, we propose a ZigBEe-bAsed indoor loCatiON (ZigBEACON) system for the AmI environment. The proposed approach is based on the k-nearest neighbor algorithm which is adopted by the famous RFID-based LANDMARC system [5]. Ideally, the path loss distribution of Received Signal Strength Indication (RSSI) conforms to the equation of path loss model, but the interference like multi-path delivery would affect the real RSSI’s distribution. According to the path loss distribution of RSSI, the RSSI values are defined into four classes. The original RSSI value will be adjusted on the basis of different classes that can effectively select the p-nearest reference nodes of mobile node by Euclidean distance. Finally, the position of mobile node would be derived by calculating the coordinates of p-nearest reference nodes. The ZigBEACON system not only is deployed easily but also improve the accuracy of indoor location system.

The rest content of this paper is organized as follows: Section 2 will introduce the related work of existing LANDMARC system and some improved algorithms for LANDMRAC, and then show one example of indoor localization in ZigBee WSN. In Section 3, the materials and proposed methodology will be described in detail. Section 4 discusses the results of ZigBEACON system and compares the results with that of ZigBee-based LANDMARC system. Finally, the conclusions will be listed in Section 5.

2.Related Work

Traditionally, indoor location system used the RSSI feature to estimate the distance between two objects or establish fingerprinting database. Trilateration is the regular algorithm to calculate the object’s position using at least three known reference points. But the environment interference would affect the accuracy severely, like multi-path fading, temperature and humidity. In order to avoid these problems, Lionel M. Ni et al. [5] proposed LANDMARC system that used real-time RSSI values of fixed reference tags and tracking tag receiving by the fixed RF readers to calculate the Euclidian distance between reference tags and tracking tag. The real-time RSSI of all devices suffer from the same noise influence so the environmental factors can be accommodated. Then, the LANDMARC system chose the k-nearest reference tags to estimate the position of tracking tag. The weights of reference nodes depend on the ratio of the square Euclidian distance’s reciprocal, in other words, the shorter Euclidian distance has larger weight value. However, the variations of tag behavior and the dynamic indoor environment result in a biased estimation.

Table 1. A comparison of the studies on improving the accuracy of LANDMARC system

Euclidean Mahalanobis Off-line

distancedistancelearning

Zhang T et al. [6]

Chen WH et al. [7]

Jiang XJ et al. [8]

Hsu PW et al. [9]

Jain S et al. [10]

Chen X et al. [11] Regionallimit Recursive Reduced error (comparing with LANDMARC) 0.34m (average) 0.076~0.344m 0.3~1m 0.663~1.049m 0.1~0.3m 0.0871~0.3616m

Recently, many researches devoted to improving the accuracy of LANDMARC system [6-11] that are listed in the Table 1. Based on the methodology of LANDMARC system, most of those researches tried to obtain the diversity between reference tags and tracking tag by the Euclidean distance [6-10], but Chen X et al. [11] used the Mahalanobis distance to estimate the similarity between an unknown sample set and a known one. But the

60 Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–65

disadvantages of calculating Mahalanobis distance, such as high complexity and the learning process through collecting amount of RSSI values before positioning, are not suitable for the dynamic indoor environment. Some algorithms revised the original k-nearest reference tags of LANDMARC. Shape Constraint Approach [7] utilized a shape constraint factor to find the k-nearest reference tags based on the geometrical correlation properties. Others, such as Jiang XJ et al. [8] calibrated the tracking tag’s coordinate by proceeding the error corrections until the tracking tag’s coordinate was stable, and Jain S et al. [10] used a backtracking algorithm to find the optimal colonies that based on the spatial co-relation between reference tags. But the results would poor if the original k-nearest reference tags were far from the mobile object; moreover, the recursion method would increase the latency that is not suitable for the real time positioning. Except correcting the original k-nearest reference tags of LANDMARC, some researches tried to increase the accuracy by adjusting the values of original RSSI values, such as using the tracking tag as the criterion to get the modified signal strength [6] or averaging the values of a historical RSSI sequence [9]. The reduced error distance was from 0.076 m to 0.3616 m, although those adjusting method were simple, the improvements were less significant.

The WSNs provide ubiquitous sensing, computing communication capability that facilitate the development of AmI application. More and more researchers are devoted to the study of indoor position system based on WSN like ZigBee. Mendalka M et al. [12] implemented the Pattern Matching (PM) localization in ZigBee wireless sensor networks. The concept of comparing a set of RSSI with all reference tags and measured samples is similar to LANDMARC methodology. But the non-real-time learning process of PM algorithm is not practical; what’s more, the tracking tag needs to send the series of localization beacons on localization phase that would increase the power consumption.

3.Materials and Methodology

3.1.Hardware

The sensor, SuperNode, consists of a MSP430 microcontroller and an UZ2400 ZigBee chip. UZ2400 will transform the power value (dBm) into the RSSI value linearly that is from 0 to 255 [13]. The RSSI value will decrease when the distance increases. Then the ZigBEACON system will use the RSSI values to do positioning. The size of SuperNode is about 5cm (length) × 3cm (width) × 0.5cm (height).

3.2.Methodology

Fig. 1. The flow chart of ZigBEACON system

x

x

x

x

In ZigBEACON system, SuperNode can be categorized according to their functions: Gateway: it is connected to the computer and delivers the data from all the nodes to computer. Mobile node: the one that should be known its position. It receives signals from RF generators and sends RSSI to computer through gateway. RF generator: it sends the broadcast signal to mobile node and reference nodes. Reference node: it receives signals from RF generators and sends RSSI to computer through gateway.

Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–6561

The ZigBEACON system first surveys the RSSI values of the transmitted power and the distance between the sender and the receiver, and then uses the Euclidean distance to estimate the diversity of reference nodes and mobile node that could effectively choose the p-nearest reference nodes to calculate the mobile node’s position. The ZigBEACON system consists of three phases, offline path loss survey phase, real-time RSSI collection phase and online position calculation phase, as shown in Figure 1.

3.2.1.Offline path loss survey phase

The Path Loss (PL) model that means the relationship between received power and distance is formed as

·PL d PL d0 10nlog§¨dd¸ XV,

0¹©(1)

where n = 2 for free space. The PL(d0) is the received power from the transmitter at a known close distance d0 and X denotes a zero mean Gaussian random variable that reflect the interference from indoor environment [14]. In reality, the real received signal power would not conform to the PL model. In the offline path loss survey phase we survey the PL distribution of SuperNode to increase the accuracy of positioning. Figure 2 shows the experimental results of RSSI propagation at the distance between 0.5m, 1m, 2m, 3m, 4m, 6m, 7m and 10m separately in the indoor environment. For each distance, we took 480 measurements then calculated the means and standard variations. We find the PL distribution presents a non-log-linear relationship between RSSI and distance. According to the characteristics between RSSI and distance, the RSSI can be divided into four classes:

xClass I: the RSSI is above 144. Because RSSI value is over 144 within 0.5m transmission distances. In other words, the RSSI in this class means the distance between receiver and transmitter is over close.

xClass II: the RSSI is from 112 to 143. The RSSI versus distance is near linear relationship above 112. Class II is the fuzzy region between Class I and Class III that the signal will be shown between 0.5m to 2m.

xClass III: the RSSI is from 60 to 111. The RSSI in this class will be distributed at the distance from 2m to 7m. xClass IV: the RSSI is under 60. When the distance far from 7m and above, the RSSI values rapidly decay under to the RSSI value of 60.

Fig. 2. The path loss distribution of SuperNode

3.2.2.Real-time RSSI collection phase

In real-time RSSI collection phase, ZigBEACON system collects the real-time RSSI, and then transmits these RSSI value to the computer for the next phase. First, mobile node triggers the real-time RSSI collection phase by sending the positioning request to gateway. Then the gateway will ask RF generators by turns to send the broadcast message to all reference nodes and mobile node. As soon as mobile node and reference nodes receive the broadcast message, they will save the value of RSSI into its memory. After all RF generators sent broadcast message, mobile node and reference nodes will forward the RSSI values to gateway. Finally, the location of mobile node will be

calculated on the computer on the next phase.

62 Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–65

3.2.3.Online position calculation phase

After all the RSSI values are transmitted to the computer, the mobile position will be calculated by ZigBEACON system. Suppose we have M fixed reference nodes, N fixed RF generators and one mobile node in AmI environment. We define the RSSI vector of the mobile node is M = (M1, …, MN), and the corresponding RSSI vector of the i-th reference node is Ri = (Ri1, …, RiN). The Euclidean distance between the mobile node and the reference node i is defined as NEi ¦ M

j 1j Rij 2. (2)

The mobile node will have a Euclidean distance vector E = (E1, …, EM) that shows the similarity between the mobile node and all reference nodes. The smallest Ei means that the reference node i is the nearest reference node surrounding the mobile node. Nevertheless, as shown in Figure 2, the result calculated by Equation (2) is difficult to recognize the real distance, since the term (MjЁRij) is blurred. For example, (160Ё140) and (100Ё80) have the same result but the distance of the former is about 0.5m and the longest distance of latter would reach 5m. In order to solve this problem, the RSSI should be adjusted before calculating the Euclidean distance by

RSSI' A ratiou RSSI B .

Table 2. The values of parameters for each class

A ratio B Class I

Class II

Class III

Class IV 176 (0xB0) 112 (0x70) 60 (0x3C) 0 (0x00) 0.05 0.3 0.6 1 144 (0x90) 112 (0x70) 60 (0x3C) 0 (0x00) (3) Table 2 shows the parameter values of A, ratio and B according to each class from the offline path loss survey phase. The values of parameter B are the baseline of each class that are 144(0x90) for Class I, 112(0x70) for Class II, 60(0x3C) for Class III and 0(0x00) for Class IV. The parameter ratio can reduce the difference when the RSSI values belong to the same class, and this value depends upon the distance coverage of its class. So, the values of ratio are 0.05, 0.3, 0.6 and 1 for Class I, II, III and IV respectively. The numbers of parameter A are equal to B for Class II, III and IV. But the gap between two baselines of Class I and Class II is too small, so we set the A value of Class I to 176(0xB0) that makes this gap is similar to the other gaps between two classes. Then we replace the original RSSI in Equation (2) by the wighted RSSI, M’ = (M1’, …, MN’) andRi’ = (Ri1’, …, RiN’), to obtain the Euclidean distance vector. Finally, the ZigBEACON system will choose p-nearest reference nodes to calculate the unknown position of the mobile node by

x,y ¦wk xk,yk ,

k 1p(4)

the wk means the weight of the k-th nearest reference node sorted by the E, the (xk,yk) is the coordinate of this reference node and the (x,y) is the estimation position of mobile node. The weight that depends on the p-nearest reference nodes’ Euclidean distance of the mobile node is defined as:

1wk 'Ek¦El 1p1'

l, (5)

Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–6563

where E’ is the modified Euclidean distance by adjusted RSSI. Equation (5) means the reference node with smallest Euclidean distance has largest weight.

4.Experimental Results and Discussion

Fig. 3. The deployment and experimental environment

The experiment is done in a 11m (length) × 5.75m (weight) classroom. As shown in Figure 3, the gateway is at the middle and the 18 reference nodes are averagely fixed in the classroom between 2m. Besides, five RF generators are set symmetrically between reference nodes. We put mobile node at the coordinates A (1.5, 1.875), B (3.5, 1.875),

C (5.5, 1.875) and D (7.5, 1.875) respectively. The error distance, e, can show the performance by the mobile node’s coordinate (x0, y0) and estimation result (x, y) is defined as e x x02 y y02. (6)

4.1.The number of nearest reference node(s)

One of the key issues affecting the estimation position is to determine the optimal number p of nearest reference node(s) for Equation (4). Figure 4 shows the average, maximum and minimum values of error distance at four positions, A, B, C and D, for p is from 1 to 18, and the standard deviations are also shown on the average line. No matter it is average, maximum or minimum values of error distance, the smallest error distance occurs when p

= 4,

and it is worthy to note the accuracy results conforms to that of previous studies for LANDMARC methodology

[5][9].

Fig. 4. The error distance v.s. p-nearest reference nodes

64

Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–65

4.2.The results of ZigBEACON system

The ZigBEACON system is based on the k-nearest neighbor algorithm which is adopted by the famous RFID-based LANDMARC system. To evaluate the ZigBEACON approach, we compare the results of ZigBEACON system with that of ZigBee-based LANDMARC system, called Z-LANDMARC latter, that accomplishes LANDMARC approach by SuperNode. Based on the result on optimal number of nearest reference node(s), we will show the comparisons at the p = 4 condition.

4.2.1.The comparison of Euclidean distance distribution

The Euclidean distance between the mobile node and the reference node i calculated by Equation (2) means the similarity of RSSI between the mobile node and the reference node i. The smaller Ei is, the nearer the reference node i is. If the p-nearest reference nodes are gathered together around the mobile node, the accuracy will be improved. Figure 5 and Figure 6 are the Euclidean distance distribution of Z-LANDMARC approach and ZigBEACON approach. The subtitles, (a), (b), (c) and (d) of these two figures are the results when the mobile node at position A, B, C and D individually as shown in Figure 3. Comparing Figure 5 with Figure 6, we can easily discover that the Euclidean distance distributions of ZigBEACON approach are smoother than that of Z-LANDMARC approach. Unlike the results of Z-LANDMARC approach that have multi-hollow distribution, the results of our proposed approach only have a main hollow. So the ZigBEACON approach can effectively choose the p-nearest reference nodes around the mobile node. For example, Figure 5 (a) has three hollows at (2.5, 0.875), (4.5, 4.875) and (8.5, 0.875), especially (8.5, 0.875) is far from the mobile node’s position, A (1.5, 1.875), that will increase the error distance, but Figure 6 (a) only have two hollows, (2.5, 0.875) and (4.5, 4.875).

Fig. 5. The Euclidean distance distribution of Z-LANMARC approach when mobile node is at (a) A (1.5, 1.875); (b) B (3.5, 1.875); (c) C (5.5,

1.875); (d) D (7.5, 1.875).

Fig. 6. The Euclidean distance distribution of ZigBEACON approach when mobile node is at (a) A (1.5, 1.875); (b) B (3.5, 1.875); (c) C (5.5,

1.875); (d) D (7.5, 1.875).

4.2.2.The comparison of error distance

Comparing the results with that of Z-LANDMARC approach, ZigBEACON approach reduces 0.47m that is about 29% improvement on average error distance. The average error distance is 1.15 0.54m for ZigBEACON and

1.62 0.9m for Z-LANDMARC, the maximum error distance is 1.64m for ZigBEACON and 2.99m for Z-LANDMARC, and the minimum error distance is 0.24m for ZigBEACON and 0.52m for Z-LANDMARC. In short,

theZigBEACON approach can improve the accuracy of indoor location significantly.

Chih-Ning Huang and Chia-Tai Chan / Procedia Computer Science 5 (2011) 58–6565

5.Conclusions

AmI environment have been a trend for future society, and it is an electronic environment that can monitor the situation around the persons or objects and give an adequate response for their needs. Accurate location information is important for location-based service. The proposed system named ZigBEACON system uses the real time RSSI to calculate the mobile node’s position. The system is not only deployed easily but also improves the accuracy of indoor location system in the AmI environment.

In this paper, the proposed ZigBEACON approach alleviates the influence of dynamic indoor environment that can effectively calculate the mobile node’s location in real time. The approach not only improves the accuracy, but also provides less calculation complexity than other improvement methods of LANDMARC. Comparing the results with that of Z-LANDMARC, the proposed methodology reduces about 0.28 to 1.57m estimation error distance and has 29% improvement on average error distance. The ZigBEACON approach is an adequate solution to the indoor location system for AmI applications.

Reference

[1] Emile Aarts, Reiner Wichert. Ambient intelligence. In: Hans-Jörg Bullinger (ed) Technology Guide Principles – Applications – Trends.

Springer; 2009, pp 244-249

[2] Schilit B, Adams N, Want R. Context-aware computing applications. Proceedings Workshop on Mobile Computing Systems and Applications;

1994, pp 85-90

[3] Huang CN, Chiang CY, Chang JS, Chou YC, Hong YX, Hsu SJ et al. Location-aware fall detection system for medical care quality

improvement. Proceedings of the 3rd International Conference on Multimedia and Ubiquitous Engineering; 2009, pp 477-480

[4] Liu H; Darabi H; Banerjee P; Liu J. Survey of wireless indoor positioning techniques and systems, IEEE Transactions on Systems, Man, and

Cybernetics, Part C: Applications and Reviews; 2007, 37(6):1067-1080

[5] Ni LM, Liu YH, Lau YC, Patil AP. LANDMARC: indoor location sensing using active RFID, In: Proceedings of the 1st IEEE International

Conference on Pervasive Computing and Communications; 2003, pp 407-415

[6] Zhang T, Chen ZY, Ouyang YN, Hao JY, and Xiong Z. An improved RFID-based locating algorithm by eliminating diversity of active tags

for indoor environment. The Computer Journal; 2008, 52(8): 902-909

[7] Chen WH, Chang HH, Lin TH, Chen PC, Chen LK, Hwang SJ et al. Dynamic indoor localization based on active RFID for healthcare

applications: a shape constraint approach, In: Proceeding of the 2nd International Conference on Biomedical Engineering and Informatics;2009, pp 1-5

[8] Jiang XJ, Liu Y, Wang XL. An enhanced approach of indoor location sensing using active RFID, In: Proceeding of the WASE International

Conference on Information Engineering; 2009, pp 169-172

[9] Hsu PW, Lin TH, Chang HH, Chen YT, Tseng YJ, Hsiao CH et al. Simulations and experiments for optimal deployment of an RFID-based

location-aware system, Wirel Commun Mob Comput; 2009, doi: 10.1002

[10] Jain S, Sabharwal A, Chandra S. An improvised localization scheme using active RFID for accurate tracking in smart homes, In: Proceeding

of the 12th International Conference on Computer Modelling and Simulation; 2010, pp 51-56

[11] Chen X, Wang ZJ. Reliable indoor location sensing technuque using active RFID, In: Proceeding of the 2nd International Conference on

Industrial Mechatronics and Automation; 2010, pp 160-163

[12] Maciej M, Karol B, Lukasz K, Krzystof N. Pattern matching localization in ZigBee wireless sensor networks, In: Proceeding of the 18th

International Conference on Microwave Radar and Wireless Communications; 2010, pp 1-4

[13] UBEC Corp.(2005) UZ2400 Data sheet (RF + Baseband + Mac) DS 2400-2, pp:79

[14] Andersen JB, Rappaport TS, Yoshida, S. Propagation measurements and models for wireless communications channels, IEEE

Communications Magazine; Jan, 1995, 33(1): 42-49

本文来源：https://www.bwwdw.com/article/yl84.html