Adaptive Accurate Indoor-Localization Using Passive rFID Xi Chen,Lei Xie,Chuyu Wang,Sanglu Lu State Key Laboratory for Novel Software Technology,Nanjing University,China hawkxc@dislab.nju.edu.cn,Ixie@nju.edu.cn,wangcyu217@126.com,sanglu@nju.edu.cn Abstract-In many pervasive applications like the intelligent time,the regularities of the variation in backscattered signals is bookshelves in libraries,it is essential to accurately locate the still unclear enough in the realistic settings,which is different items to provide the location-based service,e.g.,the average lo- from conventional wireless devices. calization error should be smaller than 50 cm and the localization delay should be within several seconds.Conventional indoor- Therefore,it is essential to investigate the backscattering localization schemes cannot provide such accurate localization features of passive RFID system through experiment study,and results.In this paper,we design an adaptive,accurate indoor- further devise an efficient localization scheme by leveraging localization scheme using passive RFID systems.We propose the passive RFID system.In this paper,according to the two adaptive solutions,i.e.,the adaptive power stepping and reference tag-based localization,we design an adaptive,real- the adaptive calibration,which can adaptively adjust the critical time indoor-localization scheme using passive RFID systems. parameters and leverage the feedbacks to improve the localization Specifically,we make the following contributions in this paper accuracy.The realistic experiment results indicate that,our adaptive localization scheme can achieve an accuracy of 31 cm We conduct an extensive experimental study over within 2.6 seconds on average. the passive RFID systems,and obtain several novel findings from the experiments.We thus propose a Keywords-Indoor localization,adaptive,accurate,passive R- FID tag,calibration,power stepping model to depict the regularities in RFID localization. We propose two adaptive solutions for localization, I.INTRODUCTION i.e..the adaptive power stepping and the adaptive calibration,which can adaptively adjust the critical In many pervasive applications,the proliferation of wireless parameters and leverage the feedbacks to improve the and mobile devices has fostered the demand for context-aware localization accuracy. or location-based services,therefore,it is essential to accu- rately locate the items to provide the location-based service. ● We build a realistic testbed,i.e.,a large bookshelf With the rapid proliferation of RFID-based applications,RFID embedded with passive RFID systems,to evaluate the performance of our solutions.The realistic experiment tags have been deployed into pervasive spaces in increasingly results indicate that,our adaptive localization scheme large numbers,e.g.,the shelves of super markets or libraries are filled with tag-labeled items.In these applications,a high- can achieve an accuracy of 31 cm within 2.6 seconds on average. precision localization scheme is essentially required in accurate approach,e.g.,the average localization error should be smaller The rest of this paper is organized as follows.We dis- than 50cm and the localization delay should be within several cuss the indoor localization technology in Section II.The seconds. experimental observations in the realistic settings are presented However.conventional indoor localization schemes can- in Section III.Section IV presents the system architecture not provide such accurate localization results.For example, of the whole work.The basic framework and motivation of localization schemes based on WiFi,bluetooth and Zigbee our localization methods is presented in Section V.Section usually achieve localization errors of no smaller than 2~3m VI presents the details of APS method and Section VII RFID-based localization schemes like LANDMARC leverages presents the details of AGC method.Then integrated method the active RFID system to assist localization.It employs the is presented in Section VIII.We evaluate the performance of idea of having extra fixed location reference tags to support all the methods in different dimension in Section IX.Finally. location calibration.Still,it achieves localization errors of We conclude the work in Section X. no smaller than 1m and suffers from several drawbacks in adaptivity.By comparison,the passive RFID system brings us II.RELATED WORKS opportunities to devise a highly accurate localization scheme Indoor localization technology has been studied for many First,due to the backscatter property,the received signal years.Generally,they are divided into transmitting model- strength indicator(RSSI)from passive RFID system is very based localization and fingerprint-based localization.The sensitive to the distance,a small change of the distance can model-based localization includes time of arrival(TOA)[1], greatly impact the RSSI of the passive tag.Second,due to the time delay of arrival(TDOA)[2],angle of arrival(AOA)[3], low cost of the chip,the passive tags can be widely deployed signal phase[4].Another approach to use RSSI is building a as reference tags to provide more fingerprints in offsetting the model for localization[56]. surrounding environmental factors.However,the passive RFID The fingerprint-based Localization uses RSSI by site sur- system is also impacted by several factors in localization,e.g.. vey.Multiple readers are deployed in order to collect the RSSI the RSSI from the passive tag is very unstable and varies all the fingerprints.Yang et al.investigate novel sensors integrated in
Adaptive Accurate Indoor-Localization Using Passive RFID Xi Chen, Lei Xie, Chuyu Wang, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, China hawkxc@dislab.nju.edu.cn, lxie@nju.edu.cn, wangcyu217@126.com, sanglu@nju.edu.cn Abstract—In many pervasive applications like the intelligent bookshelves in libraries, it is essential to accurately locate the items to provide the location-based service, e.g., the average localization error should be smaller than 50 cm and the localization delay should be within several seconds. Conventional indoorlocalization schemes cannot provide such accurate localization results. In this paper, we design an adaptive, accurate indoorlocalization scheme using passive RFID systems. We propose two adaptive solutions, i.e., the adaptive power stepping and the adaptive calibration, which can adaptively adjust the critical parameters and leverage the feedbacks to improve the localization accuracy. The realistic experiment results indicate that, our adaptive localization scheme can achieve an accuracy of 31 cm within 2.6 seconds on average. Keywords—Indoor localization, adaptive, accurate, passive RFID tag, calibration, power stepping I. INTRODUCTION In many pervasive applications, the proliferation of wireless and mobile devices has fostered the demand for context-aware or location-based services, therefore, it is essential to accurately locate the items to provide the location-based service. With the rapid proliferation of RFID-based applications, RFID tags have been deployed into pervasive spaces in increasingly large numbers, e.g., the shelves of super markets or libraries are filled with tag-labeled items. In these applications, a highprecision localization scheme is essentially required in accurate approach, e.g., the average localization error should be smaller than 50cm and the localization delay should be within several seconds. However, conventional indoor localization schemes cannot provide such accurate localization results. For example, localization schemes based on WiFi, bluetooth and Zigbee usually achieve localization errors of no smaller than 2∼3m. RFID-based localization schemes like LANDMARC leverages the active RFID system to assist localization. It employs the idea of having extra fixed location reference tags to support location calibration. Still, it achieves localization errors of no smaller than 1m and suffers from several drawbacks in adaptivity. By comparison, the passive RFID system brings us opportunities to devise a highly accurate localization scheme. First, due to the backscatter property, the received signal strength indicator(RSSI) from passive RFID system is very sensitive to the distance, a small change of the distance can greatly impact the RSSI of the passive tag. Second, due to the low cost of the chip, the passive tags can be widely deployed as reference tags to provide more fingerprints in offsetting the surrounding environmental factors. However, the passive RFID system is also impacted by several factors in localization, e.g., the RSSI from the passive tag is very unstable and varies all the time, the regularities of the variation in backscattered signals is still unclear enough in the realistic settings, which is different from conventional wireless devices. Therefore, it is essential to investigate the backscattering features of passive RFID system through experiment study, and further devise an efficient localization scheme by leveraging the passive RFID system. In this paper, according to the reference tag-based localization, we design an adaptive, realtime indoor-localization scheme using passive RFID systems. Specifically, we make the following contributions in this paper. • We conduct an extensive experimental study over the passive RFID systems, and obtain several novel findings from the experiments. We thus propose a model to depict the regularities in RFID localization. • We propose two adaptive solutions for localization, i.e., the adaptive power stepping and the adaptive calibration, which can adaptively adjust the critical parameters and leverage the feedbacks to improve the localization accuracy. • We build a realistic testbed, i.e., a large bookshelf embedded with passive RFID systems, to evaluate the performance of our solutions. The realistic experiment results indicate that, our adaptive localization scheme can achieve an accuracy of 31 cm within 2.6 seconds on average. The rest of this paper is organized as follows. We discuss the indoor localization technology in Section II. The experimental observations in the realistic settings are presented in Section III. Section IV presents the system architecture of the whole work. The basic framework and motivation of our localization methods is presented in Section V. Section VI presents the details of APS method and Section VII presents the details of AGC method. Then integrated method is presented in Section VIII. We evaluate the performance of all the methods in different dimension in Section IX. Finally, We conclude the work in Section X. II. RELATED WORKS Indoor localization technology has been studied for many years. Generally, they are divided into transmitting modelbased localization and fingerprint-based localization.The model-based localization includes time of arrival(TOA)[1], time delay of arrival(TDOA)[2], angle of arrival(AOA)[3], signal phase[4]. Another approach to use RSSI is building a model for localization[5][6]. The fingerprint-based Localization uses RSSI by site survey. Multiple readers are deployed in order to collect the RSSI fingerprints. Yang et al. investigate novel sensors integrated in
10000 8000 6000 4000 2000 0.5m 1m Distan 3m 4m Time of Samplings(seconds) (a)RSSI with Time Sequence (b)RSSI in Different Distance 120 斑到 160 140 R5nDnc1m 1200 RSSI in Distance of 1.5m -R5SI in Distanoe 4m 800 40 200 16 1820..22 24 26 28 30 30 Transmitting Power (dBm) Transmitting Power(dBm) (c)RSSI with Different Transmitting Power of Reader (d)RSSI with Different Power in Different Distance Fig.1:Experimental Observation modern mobile phones and leverage user motions to construct A.Sampling RSSI Value from Tags over Time Dimension the radio map of a floor plan [7].Similarly,Rai et al.present The most difference between passive RFID and active a system that makes the site survey zero-effort[8].Deyle et al. RFID or other wireless technology is power.Without bat- propose a new mode of perception in the positioning area [9]. tery inside the tag,passive RFID has another spacial phe- In order to further improve the overall accuracy of locating nomenon.The passive RFID tag's reflected signal strength objects,the concept of reference tags is proposed.LAND- indication(RSSI)is more unstable than other wireless devices MARC [10]is one of the first research works to locate the such as active tag.As shown in Fig.1(a),tag's RSSI value RFID tag based on the reference tags.However,LANDMARC- varies in a range which is about 500 to 1000.However,when based method may not be suitable for passive RFID-based the tag is far away from antenna,the absolute value of RSSI localization.First,it does not work well with severe multi-path may be just about 1000.For instance,in distance of 3m,the effects.Second,it has less adaptivity for measuring more sam- proportion of tag's standard deviation and average value is ples and providing better distinction.The VIRE system [11] 14.9%.In this case.the unstable value of RSSI will reduce is further proposed to solve these problems.Moreover,passive the accuracy of localization method. RFID technology is also used in reader-based localization [12] Generally,tag's RSSI is heavily affected by the distance and object tracking [13]. between tag and antenna,the same as other wireless devices. III.EXPERIMENTAL OBSERVATION However,unlike active RFID and other wireless technology, passive RFID technology has a lot of differences.We deploy In our experiment,we use Alien Technology 9900 RFID tag in different positions along the transmitting direction reader and C1G2 passive RFID tags in a realistic setting,like of antenna.As shown in Fig.1(b),tag's RSSI value is not shelf.The environment contains noises and multi-path effect. monotone decreasing with the increasing distance because of The transmitting power of reader can be set from 15.7dBm to multi path effect and passive tag's unstable reading. 30.7dBm.We measure the RSSI value from tag in different In order to avoid the negative effect of unstable readings positions.In order to measure the received signal strength indicator(RSSD),we vary the distance between each position we need to measure multiple samples to be calibrated and and antenna.The RSSI value measured by reader can be filtered for the correct fingerprint data set.However,the RFID converted to value in dBm like below: reader only allowed us to adjusting the transmitting power so that power can be changed to measuring more fingerprint RSS(dBm)=10*1g(RSSI/65536*2000) samples. Without loss of generality,in the following we use the RSSI value directly
0 50 100 150 200 250 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Time of Samplings (seconds) RSSI distance=0.5m distance=1m distance=2m distance=3m distance=4m distance=5m (a) RSSI with Time Sequence 0.5m 1m 2m 3m 4m 5m 0 2000 4000 6000 8000 10000 RSSI Distance (b) RSSI in Different Distance 14 16 18 20 22 24 26 28 30 32 −200 0 200 400 600 800 1000 1200 Transmitting Power (dBm) RSSI RSSI in Distance of 1.5m (c) RSSI with Different Transmitting Power of Reader 14 16 18 20 22 24 26 28 30 32 0 200 400 600 800 1000 1200 1400 1600 1800 Transmitting Power (dBm) RSSI RSSI in Distance 1m RSSI in Distance 2m RSSI in Distance 3m RSSI in Distance 4m (d) RSSI with Different Power in Different Distance Fig. 1: Experimental Observation modern mobile phones and leverage user motions to construct the radio map of a floor plan [7]. Similarly, Rai et al. present a system that makes the site survey zero-effort[8]. Deyle et al. propose a new mode of perception in the positioning area [9]. In order to further improve the overall accuracy of locating objects, the concept of reference tags is proposed. LANDMARC [10] is one of the first research works to locate the RFID tag based on the reference tags. However, LANDMARCbased method may not be suitable for passive RFID-based localization . First, it does not work well with severe multi-path effects. Second, it has less adaptivity for measuring more samples and providing better distinction. The VIRE system [11] is further proposed to solve these problems. Moreover, passive RFID technology is also used in reader-based localization [12] and object tracking [13]. III. EXPERIMENTAL OBSERVATION In our experiment, we use Alien Technology 9900 RFID reader and C1G2 passive RFID tags in a realistic setting, like shelf. The environment contains noises and multi-path effect. The transmitting power of reader can be set from 15.7dBm to 30.7dBm. We measure the RSSI value from tag in different positions. In order to measure the received signal strength indicator(RSSI), we vary the distance between each position and antenna. The RSSI value measured by reader can be converted to value in dBm like below: RSS(dBm) = 10 ∗ lg(RSSI/65536 ∗ 2000) Without loss of generality, in the following we use the RSSI value directly. A. Sampling RSSI Value from Tags over Time Dimension The most difference between passive RFID and active RFID or other wireless technology is power. Without battery inside the tag, passive RFID has another spacial phenomenon. The passive RFID tag’s reflected signal strength indication(RSSI) is more unstable than other wireless devices such as active tag. As shown in Fig.1(a), tag’s RSSI value varies in a range which is about 500 to 1000. However, when the tag is far away from antenna, the absolute value of RSSI may be just about 1000. For instance, in distance of 3m, the proportion of tag’s standard deviation and average value is 14.9%. In this case, the unstable value of RSSI will reduce the accuracy of localization method. Generally, tag’s RSSI is heavily affected by the distance between tag and antenna, the same as other wireless devices. However, unlike active RFID and other wireless technology, passive RFID technology has a lot of differences. We deploy tag in different positions along the transmitting direction of antenna. As shown in Fig.1(b), tag’s RSSI value is not monotone decreasing with the increasing distance because of multi path effect and passive tag’s unstable reading. In order to avoid the negative effect of unstable readings, we need to measure multiple samples to be calibrated and filtered for the correct fingerprint data set. However, the RFID reader only allowed us to adjusting the transmitting power so that power can be changed to measuring more fingerprint samples
Inactivated Unstable stable Region Region Region Grid 4 Tarpet Tag Transmitting Power RFID Antenna Fig.2:Passive Tag's Reading Model Fig.3:Scenario B.Sampling RSSI Value from Tags over Reader's Transmitting an area of indoor environment,a lot of reference tags are Power Dimension deployed into the localization area,and each tag is labeled with an accurate position recorded into database.For example,we In order to study passive tag's reflect signal strength want to locate books in a bookshelf.We can attach each book deeply,we measured tag's RSSI value with different reader's with a passive RFID tag,and deploy several reference tags into transmitting power.As shown in Fig.1(c),in a certain distance the bookshelf grids.Once we want to find a specific book in (in this case,we choose 1.5 meters),we measured RSSI value bookshelf,we can locate it in the bookshelf by comparing the from the minimum power level to the maximum power leve similarity of the reference tags.Essentially when locating the of the RFID reader(15.7dBm to 30.7dBm).At the beginning book,it is locating the target tag attached inside the book. we can not even detect the tag in a range of small power level. With the transmitting power increasing over 24dBm,the tag In regard to passive RFID based indoor localization tech- can be identified with a low RSSI value.Then,tag's RSSI nology,it is locating the attached RFID tag essentially.We di- value get increased with the increasing transmitting power vided the localization area into grids,with reference RFID tags However,with a little increase of transmitting power,in this whose position is known exactly.We use deployed reference case approaching to 26dBm,tag's RSSI arrived in its saturation tags and grid-based location information to locate the target value.After that,tag's RSSI value stays in a very small range tag.In our work,we focus on how to improve the accuracy of stable even the transmitting power increasing to the maximum localization while using the least time and energy,as shown power level.We repeated this experiment 50 times in different below: distance,as shown in Fig.1(d). ● Accuracy:the average error should be less than a certain threshold a,e.g.50cm; C.Model Time-delay:the time consumption should be less According to observations above,we model the reading than a certain threshold B,e.g.5 seconds in realistic of passive tag by RFID reader,as shown in Fig.2.First application. at the minor power level,the tag can not be identified by RFID reader,we call it inactivated region.With the power V.LOCALIZATION FRAMEWORK increasing over a certain threshold,say pi,tag begins to reflect A.Motivation signals.But the signal is unstable and the signal strength increase quickly.We call it unstable region.However,when In regard to the requirement of more accurate indoor- the transmitting power increases over a certain threshold,say localization,the traditional methods,like LANDMARC-based p2,the reflected signal strength converges in a stable level, methods,are not suitable for adaptive indoor-localization using called as stable region. passive RFID technology.The reasons are as follows.1) These traditional methods use simple distance-based k nearest In localization procedure,the tag can not be identified if it neighborhood (KNN)algorithm.The basic KNN algorithm can is in inactivated region.The RSSI value of tag is unstable if it not deal with multi-path effect and lots of noise in the indoor is in unstable region.If the transmitting power is large enough, environment.The value of RSSI may not linearly decrease the RSSI value of tag changes in small range.However,too with the increasing of distance,due to the noise and multi- small transmitting power and too large transmitting power are path effect.For example,we have to set measured value both inappropriate for accurate localization.Too small power of RSSI to value of 0 if the tag can not be identified.It leads to no RSSI value and too large power makes RSSI value enhances the difficulty of distinguishing two tags in different has no discrimination. positions.For example,suppose a tag is 5m away from the IV.PROBLEM FORMULATION antenna and another tag is 6m in the same direction.Both of them are not identified by this antenna.We can only set In the indoor environment,we need to locate various both measured value of their RSSI to 0.But we can not objects.For example,users hope to get the accurate position determine which tag is closer to antenna by two RSSI values of books in library or want to find accurate position of some of 0.2)In regard to the unstable RSSI value of passive RFID goods in a warehouse or supermarket.As shown in Fig.3,once tags,basic KNN algorithm does not have enough samples to we want to locate something in a shelf,we can divide the support accurate indoor-localization.It can not measure more localization area into several grids and deploy reference tags samples by adaptively adjusting parameters in the localization into the whole area. procedure,such as reader's transmitting power.Based on the We use RFID technology for an accurate indoor- observations in Section III,large transmitting power of reader localization.In order to locate an object with RFID tag in may decrease the distinction of tags.For example,a large
Fig. 2: Passive Tag’s Reading Model B. Sampling RSSI Value from Tags over Reader’s Transmitting Power Dimension In order to study passive tag’s reflect signal strength deeply, we measured tag’s RSSI value with different reader’s transmitting power. As shown in Fig.1(c), in a certain distance (in this case, we choose 1.5 meters), we measured RSSI value from the minimum power level to the maximum power level of the RFID reader(15.7dBm to 30.7dBm). At the beginning, we can not even detect the tag in a range of small power level. With the transmitting power increasing over 24dBm, the tag can be identified with a low RSSI value. Then, tag’s RSSI value get increased with the increasing transmitting power. However, with a little increase of transmitting power, in this case approaching to 26dBm, tag’s RSSI arrived in its saturation value. After that, tag’s RSSI value stays in a very small range stable even the transmitting power increasing to the maximum power level. We repeated this experiment 50 times in different distance, as shown in Fig.1(d). C. Model According to observations above, we model the reading of passive tag by RFID reader, as shown in Fig.2. First at the minor power level, the tag can not be identified by RFID reader, we call it inactivated region. With the power increasing over a certain threshold, say p1, tag begins to reflect signals. But the signal is unstable and the signal strength increase quickly. We call it unstable region. However, when the transmitting power increases over a certain threshold, say p2, the reflected signal strength converges in a stable level, called as stable region. In localization procedure, the tag can not be identified if it is in inactivated region. The RSSI value of tag is unstable if it is in unstable region. If the transmitting power is large enough, the RSSI value of tag changes in small range. However, too small transmitting power and too large transmitting power are both inappropriate for accurate localization. Too small power leads to no RSSI value and too large power makes RSSI value has no discrimination. IV. PROBLEM FORMULATION In the indoor environment, we need to locate various objects. For example, users hope to get the accurate position of books in library or want to find accurate position of some goods in a warehouse or supermarket. As shown in Fig.3, once we want to locate something in a shelf, we can divide the localization area into several grids and deploy reference tags into the whole area. We use RFID technology for an accurate indoorlocalization. In order to locate an object with RFID tag in Fig. 3: Scenario an area of indoor environment, a lot of reference tags are deployed into the localization area, and each tag is labeled with an accurate position recorded into database. For example, we want to locate books in a bookshelf. We can attach each book with a passive RFID tag, and deploy several reference tags into the bookshelf grids. Once we want to find a specific book in bookshelf, we can locate it in the bookshelf by comparing the similarity of the reference tags. Essentially when locating the book, it is locating the target tag attached inside the book. In regard to passive RFID based indoor localization technology, it is locating the attached RFID tag essentially. We divided the localization area into grids, with reference RFID tags whose position is known exactly. We use deployed reference tags and grid-based location information to locate the target tag. In our work, we focus on how to improve the accuracy of localization while using the least time and energy, as shown below: • Accuracy: the average error should be less than a certain threshold α, e.g. 50cm; • Time-delay: the time consumption should be less than a certain threshold β, e.g. 5 seconds in realistic application. V. LOCALIZATION FRAMEWORK A. Motivation In regard to the requirement of more accurate indoorlocalization, the traditional methods, like LANDMARC-based methods, are not suitable for adaptive indoor-localization using passive RFID technology. The reasons are as follows. 1) These traditional methods use simple distance-based k nearest neighborhood (KNN) algorithm. The basic KNN algorithm can not deal with multi-path effect and lots of noise in the indoor environment. The value of RSSI may not linearly decrease with the increasing of distance, due to the noise and multipath effect. For example, we have to set measured value of RSSI to value of 0 if the tag can not be identified. It enhances the difficulty of distinguishing two tags in different positions. For example, suppose a tag is 5m away from the antenna and another tag is 6m in the same direction. Both of them are not identified by this antenna. We can only set both measured value of their RSSI to 0. But we can not determine which tag is closer to antenna by two RSSI values of 0. 2) In regard to the unstable RSSI value of passive RFID tags, basic KNN algorithm does not have enough samples to support accurate indoor-localization. It can not measure more samples by adaptively adjusting parameters in the localization procedure, such as reader’s transmitting power. Based on the observations in Section III, large transmitting power of reader may decrease the distinction of tags. For example, a large
Application measuring passive tag's RSSI value.As shown in Fig.2, Estimated Location of Target Tag (x,y) appropriate power should be neither too large nor too small. For example,as shown in Fig.5(a),all tags can be activated Data Processing Layer and identified by the large power.The tags far away from Location Estimation Algorithm target tag may cause interference from their unstable reading. (KNN Framework) A better way to measure tags is using appropriate power computed from target tag,as shown in Fig.5(b).By using Adaptive Calibration Adaptive Power Stepping appropriate power,only the target tag and the reference tags Method Method real closed to target tag can be activated.In this case,the far away reference tags are ignored in the appropriate power. For each antenna,we find the appropriate power p2+Ap Grid-based RSSI Fingerprint RSSI Fingerprints to measure the RSSI value as the corresponding element in Feedback of Target Tag of Reference Tag(Rr) fingerprint vectors.We use the appropriate powers for each Raw Sensing Data antenna to activate reference tags in the nearby area of target tag,as shown in Fig.5(c).Besides,since the RSSI value of 0 Fig.4:System Architecture has no discrimination and brings errors,a reference tag will be abandoned if the tag can not be identified by more than k power can activate tag A a little far away from tag B but can antennas. not increase the RSSI value of tag B because the value of tag B converges in the saturation value.The basic KNN algorithm suffers from them caused by drawbacks in adaptivity. However,there are still several challenging problems to be solved by using passive RFID technology.1)The RSSI value is not linearly increasing with the reader's power increases.The RSSI value increases rapidly when reader's power is around a certain threshold.Tag can not be identified below the threshold and the RSSI value of tag soon converges in a saturation value ●Target Tag○Acthabed Tag☒Inactivated Tag ●Tarpet Tag○Activated Tag&inactated Tag beyond it.We need to find the appropriate reader's power to (a)Using Maximum Power (b)Using Appropriate Power improve the distinction of tags.2)The RSSI value of passive RFID tag is more unstable than the active tag.The unstable readings cause large error to localization.In the worst case,the proportion of stand deviation in absolute RSSI value is even over 20%.Besides more samplings,We need to design some novel method to avoid the negative effect of unstable RSSI. Based on the understanding above,we design two methods. The adaptive power stepping.It measures more samples and finds the appropriate power of reader.The appropriate trans- mitting power can only activate the target tag and tags in the -Macimum Power- nearby area of target tag in order to improve the distinction. (c)Power Stepping Model The adaptive calibration.It calibrates the estimated position of target tag and improves the average accuracy.The method is Fig.5:APS Example based on the feedback samples from users or some automatic sensing technology.Finally,we design integrated method by integrating these two methods and unite both advantages of B.Adaptive Power Stepping(APS) the methods. We design adaptive power stepping algorithm,as shown in Alg.2.For finding the appropriate transmitting power for B.System Framework reader's each antenna,we use binary search algorithm to We design an advanced adaptive accurate localization find the power,as shown in Alg.1.By using the appropriate powers to set each antenna,we measure tags and assemble method.as shown in Fig.4.We use two adaptive methods to deal with the disadvantages of passive tag.The adaptive power k-dimension fingerprint vector.Then we choose the nearest stepping method decides the appropriate transmitting power of reference tags to estimate the position of target tag. reader.The power can only activate the reference tags in the Besides,in the procedure of finding appropriate transmit- nearby area of target tag.The adaptive grid-based calibration ting power,we record the tags reading during the procedure method uses the auto-feedback grid-based fingerprints and with its activating power.Each two tags may have almost the provides calibrations for tags'fingerprints. same activating power if they are close in distance.We can use this extra information to filter some false reference tags VI.ADAPTIVE POWER STEPPING METHOD selected by RSSI value.When a reference tag is selected as one of the nearest tags.Then compute each activating power A.Motivation p from the records with the activating power p;of target tag Based on the experimental observation in Section II, measured by the same antenna.If more than k'pairs of powers appropriate transmitting power of reader is important for have lp-pil >T,the reference tag will be treated as false
Fig. 4: System Architecture power can activate tag A a little far away from tag B but can not increase the RSSI value of tag B because the value of tag B converges in the saturation value. The basic KNN algorithm suffers from them caused by drawbacks in adaptivity. However, there are still several challenging problems to be solved by using passive RFID technology. 1) The RSSI value is not linearly increasing with the reader’s power increases. The RSSI value increases rapidly when reader’s power is around a certain threshold. Tag can not be identified below the threshold and the RSSI value of tag soon converges in a saturation value beyond it. We need to find the appropriate reader’s power to improve the distinction of tags. 2) The RSSI value of passive RFID tag is more unstable than the active tag. The unstable readings cause large error to localization. In the worst case, the proportion of stand deviation in absolute RSSI value is even over 20%. Besides more samplings, We need to design some novel method to avoid the negative effect of unstable RSSI. Based on the understanding above, we design two methods. The adaptive power stepping. It measures more samples and finds the appropriate power of reader. The appropriate transmitting power can only activate the target tag and tags in the nearby area of target tag in order to improve the distinction. The adaptive calibration. It calibrates the estimated position of target tag and improves the average accuracy. The method is based on the feedback samples from users or some automatic sensing technology. Finally, we design integrated method by integrating these two methods and unite both advantages of the methods. B. System Framework We design an advanced adaptive accurate localization method, as shown in Fig.4. We use two adaptive methods to deal with the disadvantages of passive tag. The adaptive power stepping method decides the appropriate transmitting power of reader. The power can only activate the reference tags in the nearby area of target tag. The adaptive grid-based calibration method uses the auto-feedback grid-based fingerprints and provides calibrations for tags’ fingerprints. VI. ADAPTIVE POWER STEPPING METHOD A. Motivation Based on the experimental observation in Section III, appropriate transmitting power of reader is important for measuring passive tag’s RSSI value. As shown in Fig. 2, appropriate power should be neither too large nor too small. For example, as shown in Fig. 5(a), all tags can be activated and identified by the large power. The tags far away from target tag may cause interference from their unstable reading. A better way to measure tags is using appropriate power computed from target tag, as shown in Fig. 5(b). By using appropriate power, only the target tag and the reference tags real closed to target tag can be activated. In this case, the far away reference tags are ignored in the appropriate power. For each antenna, we find the appropriate power p2 + Δp to measure the RSSI value as the corresponding element in fingerprint vectors. We use the appropriate powers for each antenna to activate reference tags in the nearby area of target tag, as shown in Fig.5(c). Besides, since the RSSI value of 0 has no discrimination and brings errors, a reference tag will be abandoned if the tag can not be identified by more than k antennas. (a) Using Maximum Power (b) Using Appropriate Power (c) Power Stepping Model Fig. 5: APS Example B. Adaptive Power Stepping (APS) We design adaptive power stepping algorithm, as shown in Alg. 2. For finding the appropriate transmitting power for reader’s each antenna, we use binary search algorithm to find the power, as shown in Alg.1. By using the appropriate powers to set each antenna, we measure tags and assemble k-dimension fingerprint vector. Then we choose the nearest reference tags to estimate the position of target tag. Besides, in the procedure of finding appropriate transmitting power, we record the tags reading during the procedure with its activating power. Each two tags may have almost the same activating power if they are close in distance. We can use this extra information to filter some false reference tags selected by RSSI value. When a reference tag is selected as one of the nearest tags. Then compute each activating power p i from the records with the activating power pi of target tag measured by the same antenna. If more than k pairs of powers have |p i − pi| > τ, the reference tag will be treated as false
reference tag. tag.However,the method still suffer from the same problem For example,we set T=5.0 and '=2 and the number with basic method.At some positions in the localization area of antennas is 4.When a reference tag is selected,we have its the maximum power still needs to activating the target tag. activating power(25.7,18.7,30.7,29.7)by the 4 antennas.And For example,if the target tag is in center of localization area, we have activating power(28.7,29.7,24.7,22.7)for target tag. we need to use maximum power so that all reference tags are Compute with the two power vectors,we have the last three activated.So,the method still have a large maximum error.It corresponding elements |29.7-18.7>5.0,24.7-30.7]>5.0 makes the APS method can only reduce the minimum error and |22.7-29.7>5.0.The number of elements which have but it can not guarantee the maximum error to be less than a difference more than r is over threshold k'.Then we treat this smaller threshold. reference tag as false nearby reference tag. VII.ADAPTIVE GRID-BASED CALIBRATION METHOD Algorithm 1 Localization Algorithm-Finding Appropriate A.Motivation Power In the realistic application,user will get the located object 1:Set function R(p)as the RSSI value measured by RFID after the localization procedure.The user may give a feedback reader in power p; to set correct position when the estimated position is wrong. 2:First set minimum power as pi and maximum power as In recent years,several detection technologies such as RFID- P2: based activity sensing have a quick development.With those 3:Check if the tag can be identified by minimum power or technologies,the position where user takes the object from can it can not be identified by maximum power. be automatic detected easily.These auto-detection technologies 4:while p2 pi do can help us to have feedbacks for the localization result. Setp3=(p1+p2)/2: However.both the user's feedback and the auto-detection 6 if R(p3)=0 then technologies can not give accurate results.The feedback can 7: Set p3 to p1; just show a smaller area where the object is in.But the 8: else feedback fingerprints are very reliable,especially the scale of if R(p3+6)-R(p3-6)>0 then fingerprints is large. 10: Set p3 to pi; By dividing the localization area into grids,as shown 11: else in Fig.3,we can use the feedback to calibrate the next 12: Set pa to p2; localization result.In the realistic scenario,shelf can be easily 13: end if divided into grids.The feedback can distinguish the grid in 14安 end if which user takes the object. 15:end while 16:Power p3 is the appropriate transmitting power. When knowing which grid the target tag is in,we can measure the fingerprint of this tag and record it as automatic detected fingerprint database.We set this fingerprint database as RG.Each fingerprint in Rc is mapped to a grid in the Algorithm 2 Localization Algorithm-Adaptive Power Step localization area ping(APS) 1:Call Alg.1 to get Pipili [1,k]},each power pi is for B.Adaptive Grid-based Calibration(AGC) antenna A;: Considering the fingerprints of reference tags are used to 2:Set P as reader's transmitting power for each antenna. compute similarity between target and reference tags,the de- 3:Collect fingerprints of reference tags which can be identi- tailed information from each element in fingerprints is ignored. fied by at least'antenna. In regard to fingerprint data set Rc and relative position of 4:while The number of reference tag 1500 of its fingerprint.If the target tag power,the APS method can improve the localization accuracy is not matching,its estimated position needs calibration.An in some conditions.The minimum error of the localization sys- exact example using the realistic experiment data is given in tem can be reduced by this method.Because the method avoid Section IX. the interference from the reference tags far away from target With these rules and grid-based fingerprint information,we
reference tag. For example, we set τ = 5.0 and k = 2 and the number of antennas is 4. When a reference tag is selected, we have its activating power (25.7, 18.7, 30.7, 29.7) by the 4 antennas. And we have activating power (28.7, 29.7, 24.7, 22.7) for target tag. Compute with the two power vectors, we have the last three corresponding elements |29.7−18.7| > 5.0, |24.7−30.7| > 5.0 and |22.7 − 29.7| > 5.0. The number of elements which have difference more than τ is over threshold k . Then we treat this reference tag as false nearby reference tag. Algorithm 1 Localization Algorithm - Finding Appropriate Power 1: Set function R(p) as the RSSI value measured by RFID reader in power p; 2: First set minimum power as p1 and maximum power as p2; 3: Check if the tag can be identified by minimum power or it can not be identified by maximum power. 4: while p2 > p1 do 5: Set p3 = (p1 + p2)/2; 6: if R(p3)=0 then 7: Set p3 to p1; 8: else 9: if R(p3 + δ) − R(p3 − δ) > θ then 10: Set p3 to p1; 11: else 12: Set p3 to p2; 13: end if 14: end if 15: end while 16: Power p3 is the appropriate transmitting power. Algorithm 2 Localization Algorithm - Adaptive Power Stepping (APS) 1: Call Alg.1 to get P{pi|i ∈ [1, k]}, each power pi is for antenna Ai; 2: Set P as reader’s transmitting power for each antenna. 3: Collect fingerprints of reference tags which can be identi- fied by at least k antenna. 4: while The number of reference tag < λ do 5: Set P + ΔP to P, set P as reader’s power; 6: Collect fingerprints in the same way again; 7: Compute the similarity, find the nearest reference tags; 8: Filter the reference tags by records of activating power; 9: end while 10: Estimating position of target tag by the selected reference tags. C. Analysis By detecting and avoiding the unstable region, adaptive power stepping method can use appropriate transmitting power. The power can only activate the target tag and the reference tags in the nearby area of target tag. By using the appropriate power, the APS method can improve the localization accuracy in some conditions. The minimum error of the localization system can be reduced by this method. Because the method avoid the interference from the reference tags far away from target tag. However, the method still suffer from the same problem with basic method. At some positions in the localization area, the maximum power still needs to activating the target tag. For example, if the target tag is in center of localization area, we need to use maximum power so that all reference tags are activated. So, the method still have a large maximum error. It makes the APS method can only reduce the minimum error but it can not guarantee the maximum error to be less than a smaller threshold. VII. ADAPTIVE GRID-BASED CALIBRATION METHOD A. Motivation In the realistic application, user will get the located object after the localization procedure. The user may give a feedback to set correct position when the estimated position is wrong. In recent years, several detection technologies such as RFIDbased activity sensing have a quick development. With those technologies, the position where user takes the object from can be automatic detected easily. These auto-detection technologies can help us to have feedbacks for the localization result. However, both the user’s feedback and the auto-detection technologies can not give accurate results. The feedback can just show a smaller area where the object is in. But the feedback fingerprints are very reliable, especially the scale of fingerprints is large. By dividing the localization area into grids, as shown in Fig. 3, we can use the feedback to calibrate the next localization result. In the realistic scenario, shelf can be easily divided into grids. The feedback can distinguish the grid in which user takes the object. When knowing which grid the target tag is in, we can measure the fingerprint of this tag and record it as automatic detected fingerprint database. We set this fingerprint database as RG. Each fingerprint in RG is mapped to a grid in the localization area. B. Adaptive Grid-based Calibration (AGC) Considering the fingerprints of reference tags are used to compute similarity between target and reference tags, the detailed information from each element in fingerprints is ignored. In regard to fingerprint data set RG and relative position of each grid, each grid can has some rules Li. As shown in Fig.3, the fingerprint rT must match the rules Li. For Li, we can generate a table containing the comparison li between each element of fingerprint vector measured by different antennas. It is generated by the fingerprint data set RG. For example, we have two fingerprints (3000,1500,1000,500) and (3100, 1400, 980, 450) in RG and they are related to grid 1. The difference between s1 and s2 is 1500 in the first fingerprint and 1700 in the second fingerprint, si is the ith element of fingerprint. To check if the target is in, we use the smaller difference to make a decision. The smaller one above, value of 1500 is more than the threshold 200, which is set for determining the validity of rules. Then we can build a rule for target tag estimated in grid 1 that s1 − s2 ≥ 1500 of its fingerprint. If the target tag is not matching, its estimated position needs calibration. An exact example using the realistic experiment data is given in Section IX. With these rules and grid-based fingerprint information, we
Original position Estimated position The grid has some Estimated position of target tag by baseline method rules by feedbacks by baseline method Algorithm 3 Localization Algorithm-Filter the invalid feed- back fingerprints 1:For fingerprints data set Rcfrili=1,2,...,m and fingerprint of target tag rr; 2:for i=1 to m do 3: Compare the corresponding elements between rr and T∈Rc; 4: Locate tag by baseine method firstly Set S as invalid components counter; The estimated position is NOT matching rules 5: for j=1 to k do (a)Step 1 (b)Step 2 6: if rT.j -ri.jl At then All selected grid by Estimated position Original position Estimated position Set S+1 to S: AGCm by basefine method of target tag 8: end if 9 end for 10: if S<T then 11 Add ri into RG 12: end if 13:end for 14:R is the valid fingerprints data set for use ed h ethod (U ted grids'center point) Finl estimated position by AGC metho Algorithm 4 Localization Algorithm -Adaptive Grid-based (c)Step 3 (d)Step 4 Calibration (AGC) Fig.6:A Calibration Example of AGC Method 1:Get the signal strength vector of the target tag as rr= 1s1,s2,...,sk,sj is the average signal strength of the design adaptive grid-based calibration method.Since RG is target tag perceived on antennas j,where j [1,k]. more reliable than Rr.We use the result based on Rc to 2:Get the signal strength vector of the reference tags as ri= calibrate the result decided by the basic KNN method.When {si,1,si,2,,si,k}∈Rr,where i∈[l,ml. the result does not match the rules of related grid,it means 3:Call Basic KNN algorithm to estimate the target tag's the target tag is located into a wrong gird.Then it will be position (x,y); regarded as false result to be calibrated to a new one.The 4:if(,y)is NOT matching rule Li of the related grid then procedure of AGC is shown as Alg.4.For better calibration of 5 Call Alg.3 to find R from RG; the result,we use Alg.3 to filter the fingerprint data set Rc to 6 Compute the similarity between rr and riERG: provide better accuracy localization.We consider each element 1 Finding the most similar r;using basic KNN algorith- of fingerprints.By comparing target tag's fingerprint and m fingerprints in RG,the false nearby fingerprints are filtered, For each grid related to the most similar ri,vote to as shown in Alg.3.We count the corresponding elements of selecting the top k estimated grid by the most similar target tag's and fingerprint in RG.The elements in each pair of fingerprints in R.Set these grids as G1,...,Gk. fingerprints are checked whether their difference is more than 9: For each selected grid,set a weight value wi by the threshold At.The feedback fingerprint will be treated as false number of fingerprints which voting to the grid. nearby reference fingerprint if the number of such elements is a Compute the calibrated position of the target tag more than T.The valid fingerprints will be added into subset RThen the position of target tag will be re-estimated by Wi R'c (,)=（,h)4,= 11 ∑1 Fig.6 is an example of AGC procedure.Firstly,we use 11: basic KNN method to locate the target tag,as shown in (i,y)is the center point axis of each selected grid. 12:end if Fig.6(a).However,the AGC method found the location point does not match the rules,as shown in Fig.6(b).Then the 13:(z,y)is the final estimated position of target tag. method can use all k selected grids to re-estimate the location of target tag,by using the center point of these k grids,as shown in Fig.6(c).Finally,we can find a calibrated position of just provide accuracy as grid.But the information of RG is target tag and we can see the result is much better,as shown very reliable.However,this method needs a lot of feedback in Fig.6(d). data and the data set can be built after the system is used for several times. C.Analysis With using grid-based information to calibrate error esti- VIII.INTEGRATED METHOD mated position,the AGC method mainly calibrates big errors According to the experimental observation and theoretical (e.g.estimated position is in other wrong grid).However,the analysis,the AGC method can calibrate the big error which method can not calibrate the error limited in the same grid.As locates the target tag into another wrong grid.The APS method a result,the AGC method can cut down the maximum error still have big error which locate tags into another wrong but can not reduce the minimum error.This is caused by the grid.However,the APS method can improve the best case in accuracy of feedback fingerprint data set RG.The Rc can reducing the minimum error.Considering these two methods
Original position of target tag Estimated position by baseline method Locate tag by baseline method firstly (a) Step 1 (b) Step 2 Estimated position by baseline method All selected grid by AGC method The estimated position is replaced by the computing result of AGC method (Using selected gridsÿcenter point) (c) Step 3 Estimated position by baseline method Original position of target tag Final estimated position by AGC method (d) Step 4 Fig. 6: A Calibration Example of AGC Method design adaptive grid-based calibration method. Since RG is more reliable than RT . We use the result based on RG to calibrate the result decided by the basic KNN method. When the result does not match the rules of related grid, it means the target tag is located into a wrong gird. Then it will be regarded as false result to be calibrated to a new one. The procedure of AGC is shown as Alg.4. For better calibration of the result, we use Alg.3 to filter the fingerprint data set RG to provide better accuracy localization. We consider each element of fingerprints. By comparing target tag’s fingerprint and fingerprints in RG, the false nearby fingerprints are filtered, as shown in Alg.3. We count the corresponding elements of target tag’s and fingerprint in RG. The elements in each pair of fingerprints are checked whether their difference is more than threshold Δt. The feedback fingerprint will be treated as false nearby reference fingerprint if the number of such elements is more than τ. The valid fingerprints will be added into subset R G. Then the position of target tag will be re-estimated by R G. Fig.6 is an example of AGC procedure. Firstly, we use basic KNN method to locate the target tag, as shown in Fig.6(a). However, the AGC method found the location point does not match the rules, as shown in Fig.6(b). Then the method can use all k selected grids to re-estimate the location of target tag, by using the center point of these k grids, as shown in Fig.6(c). Finally, we can find a calibrated position of target tag and we can see the result is much better, as shown in Fig.6(d). C. Analysis With using grid-based information to calibrate error estimated position, the AGC method mainly calibrates big errors (e.g. estimated position is in other wrong grid). However, the method can not calibrate the error limited in the same grid. As a result, the AGC method can cut down the maximum error but can not reduce the minimum error. This is caused by the accuracy of feedback fingerprint data set RG. The RG can Algorithm 3 Localization Algorithm - Filter the invalid feedback fingerprints 1: For fingerprints data set RG{ri|i = 1, 2, ..., m} and fingerprint of target tag rT ; 2: for i = 1 to m do 3: Compare the corresponding elements between rT and ri ∈ RG; 4: Set S as invalid components counter; 5: for j = 1 to k do 6: if |rT,j − ri,j | > Δt then 7: Set S + 1 to S; 8: end if 9: end for 10: if S<τ then 11: Add ri into R G 12: end if 13: end for 14: R G is the valid fingerprints data set for use. Algorithm 4 Localization Algorithm - Adaptive Grid-based Calibration (AGC) 1: Get the signal strength vector of the target tag as rT = {s1, s2, ..., sk}, sj is the average signal strength of the target tag perceived on antennas j, where j ∈ [1, k]. 2: Get the signal strength vector of the reference tags as ri = {si,1, si,2, ..., si,k} ∈ RT , where i ∈ [1, m]. 3: Call Basic KNN algorithm to estimate the target tag’s position (x, y); 4: if (x, y) is NOT matching rule Li of the related grid then 5: Call Alg.3 to find R G from RG; 6: Compute the similarity between rT and ri ∈ R G; 7: Finding the most similar ri using basic KNN algorithm. 8: For each grid related to the most similar ri, vote to selecting the top k estimated grid by the most similar fingerprints in R G. Set these grids as G1, ..., Gk. 9: For each selected grid, set a weight value wi by the number of fingerprints which voting to the grid. 10: Compute the calibrated position of the target tag (x, y) = k i=1 (xi, yi) · w i, w i = wi k i=1 wi 11: (xi, yi) is the center point axis of each selected grid. 12: end if 13: (x, y) is the final estimated position of target tag. just provide accuracy as grid. But the information of RG is very reliable. However, this method needs a lot of feedback data and the data set can be built after the system is used for several times. VIII. INTEGRATED METHOD According to the experimental observation and theoretical analysis, the AGC method can calibrate the big error which locates the target tag into another wrong grid. The APS method still have big error which locate tags into another wrong grid. However, the APS method can improve the best case in reducing the minimum error. Considering these two methods,
16 Error (cm) (a)Realistic Experiment Settings (b)Success Ratio of AGC Rule Checking (c)CDF of Localization Error 3000 -oAverage Error 2500 S Maximum Error Minimum Error 。-Minimum Error 2000 100 1500 1000 500 Basic APS AGC Integrated Numbor of rTags Basic APS AGC Integrated (d)Bounds of Localization Error (e)Error with Different Reference Tags (f)Time Delay of Each Method Fig.7:Experimental Evaluation Algorithm 5 Localization Algorithm-Integrated Method TABLE I:Comparison of History Data in Grid 2 1:Call APS method to get the estimated position P. 2:if P is NOT matching rules then 81一881一82 81一84 8g一82 82一8418184 439.662 3: Calibrate P by calling AGC method. 2921.276 2373.08 2481.614 548.196 108.534 1317.026 105258 952.91 -1211.76 -364.116 847.652 4:end if 634.608 55.638 776.14 .578.97 141.532 720.502 5:P is the estimated position of target tag. 542.878 9.976 1028.972 -532.902 486.094 1018.996 we present the integrated method combining the two methods method and functional modules of the integrated method in several dimensions.Basic KNN method is used as the baseline We use all the ideas of two methods to design the final method new method.We still use the reference tags to assemble the fingerprint database.Firstly,we determine the appropriate transmitting power and estimate the position of target tag by B.Performance of Rule Checking in AGC Method APS method.Then we check the result by the rules of AGC We already measure 40 feedback fingerprints before the method.If the result does not match,it will be calibrated by checking procedure.The rules of each grid are generated the AGC method. from parts of these fingerprints.Respectively,we use all of them,32 of them,24 of them,16 of them to generate the rules.For example,we can have Table I to grid 2 with 4 IX.PERFORMANCE EVALUATION history data.With the threshold 200,we can have the first A.Experiment Settings rule,s1 >(s2+542.878).Because the smallest value 542.878 We evaluate the performance in realistic settings.The basic is more than the threshold.Similarly,we can have rules, experiment settings are the same as the realistic settings in s1 (s4+776.14)and s2 (s3-532.902).The comparison Section III.A bookshelf is customized made as the testbed for between s2 and s4 cannot be rule because the decision of localization,as shown in Fig.7(a).We divide the localization history data is inconsistent.The other two cannot be rules area into 8 grids and the size of each grid is 55cm x 75cm. because the smallest values are both smaller than the threshold The size of entire localization area is 120cm x 310cm.As We check whether the rules can correctly determine if the model shows in Fig.3,15 reference tags are deployed in the estimated position of target tag is in the right grid.Fig the localization area in a 3 x 5 array.A target tag is attached 7(b)shows the success ratio from 64 checking procedures. inside a book for localization.In each evaluation procedure, We note that more feedback fingerprints can provide higher we respectively place the book with the target tag randomly success ratio.Success ratio of nearly 60%is achieved with in 8 positions of each grid.Totally we repeat measurement only 16 fingerprints and 86.5%is achieved with 40 feedback for 64 times in each evaluation procedure.We evaluate each fingerprints
(a) Realistic Experiment Settings 40 32 24 16 0 0.2 0.4 0.6 0.8 1 Number of Feedback Fingerprints Success Ratio (b) Success Ratio of AGC Rule Checking 0 50 100 150 200 250 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Error (cm) CDF Basic Method APS Method AGC Method Integrated Method (c) CDF of Localization Error Basic APS AGC Integrated 0 50 100 150 200 250 Error (cm) Average Error Maximum Error Minimum Error (d) Bounds of Localization Error 15 10 5 0 50 100 150 200 Error (cm) Number of Reference Tags Average Error Maximum Error Minimum Error (e) Error with Different Reference Tags Basic APS AGC Integrated 0 500 1000 1500 2000 2500 3000 Average Time Delay (ms) (f) Time Delay of Each Method Fig. 7: Experimental Evaluation Algorithm 5 Localization Algorithm - Integrated Method 1: Call APS method to get the estimated position P. 2: if P is NOT matching rules then 3: Calibrate P by calling AGC method. 4: end if 5: P is the estimated position of target tag. we present the integrated method combining the two methods. We use all the ideas of two methods to design the final new method. We still use the reference tags to assemble the fingerprint database. Firstly, we determine the appropriate transmitting power and estimate the position of target tag by APS method. Then we check the result by the rules of AGC method. If the result does not match, it will be calibrated by the AGC method. IX. PERFORMANCE EVALUATION A. Experiment Settings We evaluate the performance in realistic settings. The basic experiment settings are the same as the realistic settings in Section III. A bookshelf is customized made as the testbed for localization, as shown in Fig. 7(a). We divide the localization area into 8 grids and the size of each grid is 55cm × 75cm. The size of entire localization area is 120cm × 310cm. As the model shows in Fig. 3, 15 reference tags are deployed in the localization area in a 3 × 5 array. A target tag is attached inside a book for localization. In each evaluation procedure, we respectively place the book with the target tag randomly in 8 positions of each grid. Totally we repeat measurement for 64 times in each evaluation procedure. We evaluate each TABLE I: Comparison of History Data in Grid 2 s1 − s2 s1 − s3 s1 − s4 s2 − s3 s2 − s4 s3 − s4 2921.276 2373.08 2481.614 -548.196 -439.662 108.534 1317.026 105.258 952.91 -1211.76 -364.116 847.652 634.608 55.638 776.14 -578.97 141.532 720.502 542.878 9.976 1028.972 -532.902 486.094 1018.996 method and functional modules of the integrated method in several dimensions. Basic KNN method is used as the baseline method. B. Performance of Rule Checking in AGC Method We already measure 40 feedback fingerprints before the checking procedure. The rules of each grid are generated from parts of these fingerprints. Respectively, we use all of them, 32 of them, 24 of them, 16 of them to generate the rules. For example, we can have Table I to grid 2 with 4 history data. With the threshold 200, we can have the first rule, s1 ≥ (s2 + 542.878). Because the smallest value 542.878 is more than the threshold. Similarly, we can have rules, s1 ≥ (s4 + 776.14) and s2 ≤ (s3 − 532.902). The comparison between s2 and s4 cannot be rule because the decision of history data is inconsistent. The other two cannot be rules because the smallest values are both smaller than the threshold. We check whether the rules can correctly determine if the estimated position of target tag is in the right grid. Fig. 7(b) shows the success ratio from 64 checking procedures. We note that more feedback fingerprints can provide higher success ratio. Success ratio of nearly 60% is achieved with only 16 fingerprints and 86.5% is achieved with 40 feedback fingerprints
C.Evaluate Localization Performance of each Method comes from the tags reading operations.The operations cost We repeat localization procedures for 64 times to evaluate most of the time. the performance for 4 methods respectively.During the ex X.CONCLUSION periments,all 15 reference tags are used.Fig.7(c)shows the cumulative distribution(CDF)of localization error and Fig. This paper considers how to provide accurate indoor- 7(d)shows the bounds of localization error. localization by using adaptive methods,from the experimental As shown in Fig.7(c),both APS,AGC and integrat- point of view.We conduct measurements over passive RFID ed method have much better performance than the baseline tags in the realistic settings,and propose two adaptive lo- method.Compare APS method with AGC method,nearly 40% calization methods and an integrated method after analysis of localization errors is under 20cm in APS method while of experimental observations.Our experiments show that our only about 10%of errors is under 20cm in AGC method.It localization methods can achieve 31cm in average error and 2.6 seconds in average time.We believe this work gives much means the APS method can really reduce the minimum error. However,over 95%of errors is under 70cm in AGC method insight and inspiration for accurate indoor-localization using while only over 85%of errors is under 70cm.It means the passive RFID technology. APS method still suffers from some problems such as multi- ACKNOWLEDGMENT path effect in the same as baseline method.But,the AGC This work is partially supported by the National method can use the automatic feedback fingerprints to calibrate Basic Research Program of China (973)under Grant negative impact. No.2009CB320705:the National Natural Science Foundation The same result is proved in Fig.7(d),the average value of China under Grant No.61100196,61073028,61021062, the maximum value and the minimum value of localization 91218302:the JiangSu Natural Science Foundation under errors in baseline method are much worse than the other three Grant No.BK2011559. methods.The average values of errors in APS method and AGC method are almost the same.But,the maximum error REFERENCES in APS method is much larger than AGC method and the [1]H.Choi,Y.Jung,and Y.Baek,"Two-step locating system for harsh minimum error in APS method is smaller than AGC method. marine port environments,"in Proc.of IEEE International Conference It means the large errors are really calibrated by AGC method on RFID(RFD),2011,pp.106-112. and the appropriate transmitting power decided by APS really 2] N.B.Priyantha,A.Chakraborty,and H.Balakrishnan,"The cricket location-support system,"in Proceedings of the 6th annual international improves the accuracy in the best case. conference on Mobile computing and networking.ACM,200,pp.32- By integrating APS and AGC method,the integrated 43. method improves the localization performance in total range. 31 S.Azzouzi.M.Cremer,U.Dettmar,R.Kronberger,and T.Knie,"New The average error of localization is 32.5cm and 85%of errors measurement results for the localization of uhf rfid transponders using an angle of arrival (aoa)approach,"in Proc.of IEEE International is under 50cm Conference on RFID (RFID),2011,pp.91-97. [4] R.Miesen,F.Kirsch,and M.Vossiek,"Holographic localization of pas- D.Evaluate Integrated Method with Different Number of Ref- sive uhf rfid transponders,"in Proc.of IEEE International Conference erence Tags on RFID (RFID),2011,pp.32-37. In regard to 15 deployed reference tags,we respectively [5] J.Hightower,G.Borriello,and R.Want,"Spoton:An indoor 3d location sensing technology based on rf signal strength,"Univ.Washington use all of them,10 of them,5 of them to estimate the Tech.Rep.,2000. position of target tag by integrated method.Fig.7(e)shows the [6] J.Brchan,L.Zhao,J.Wu,R.Williams,and L.Perez,"A real-time rfid average value and bounds of error in 64 localization procedure. localization experiment using propagation models,"in Proc.of /EEE We note that the average error is small by more number of International Conference on RFID (RFID).2012,pp.141-148. reference tags.The minimum error is almost the same because 17] Z.Yang.C.Wu,and Y.Liu,"Locating in fingerprint space:Wireless the method works well in some small areas within entire indoor localization with little human intervention."in Proc.of /EEE MobiCOM.2012. localization area.In those areas,estimated positions are both accurate no matter how many reference tags are deployed [8] A.Rai,K.K.Chintalapudi,V.N.Padmanabhan,and R.Sen,"Zee: Zero-effort crowdsourcing for indoor localization,"in Proc.of ACM However,we note that the maximum error by 10 reference MOBICOM.2012. tags is smaller than it by 15 reference tags.It is because more 9叨 T.Deyle,H.Nguyen,M.Reynolds,and C.Kemp,"Rf vision:Rfid interference existed by more reference tags.But the influence receive signal strength indicator (rssi)images for sensor fusion and of more reference tags is tiny compared with average error. mobile manipulation,"in Proc.of IEEE/RSJ International Conference The maximum error by 5 reference tags is much larger than on Intelligent Robots and Systems,2009,pp.5553-5560. others caused by lacking of reference tags. [10]L.Ni,Y.Liu,Y.Lau,and P.Abhishek,"Landmarc:Indoor location sensing using active rfid,"Wireless Nerworks,vol.10,no.6,pp.701- 710.2004. E.Evaluate Time Delay of each Method [11]Y.Zhao.Y.Liu.and L.M.Ni."Vire:Active rfid-based localization We respectively measure time delays of 4 methods with using virtual reference elimination,"in Proc.of the International 64 localization procedures.The average time delay of baseline Conference on Parallel Processing,2007. method and AGC method are both about 2.1 seconds.It means [12] W.Zhu,J.Cao,Y.Xu,L.Yang,and J.Kong,"Fault-tolerant rfid reader localization based on passive rfid tags,"in Proc.of IEEE INFOCOM, the time-consumption of grid-based calibration procedure is 2012,pp.2183-2191. very small.The APS method and Integrated method cost about [13] L.Yang,J.Cao,W.Zhu,and S.Tang,"A hybrid method for achieving 0.45 seconds more than the other two methods.It is caused by high accuracy and efficiency in object tracking using passive rfid."in the procedure of finding the appropriate transmitting power. Proc.of IEEE International Conference on Pervasive Computing and During the experiments,we note that most time-consumption Communications (PerCom),2012,pp.109-115
C. Evaluate Localization Performance of each Method We repeat localization procedures for 64 times to evaluate the performance for 4 methods respectively. During the experiments, all 15 reference tags are used. Fig. 7(c) shows the cumulative distribution (CDF) of localization error and Fig. 7(d) shows the bounds of localization error. As shown in Fig. 7(c), both APS, AGC and integrated method have much better performance than the baseline method. Compare APS method with AGC method, nearly 40% of localization errors is under 20cm in APS method while only about 10% of errors is under 20cm in AGC method. It means the APS method can really reduce the minimum error. However, over 95% of errors is under 70cm in AGC method while only over 85% of errors is under 70cm. It means the APS method still suffers from some problems such as multipath effect in the same as baseline method. But, the AGC method can use the automatic feedback fingerprints to calibrate negative impact. The same result is proved in Fig. 7(d), the average value , the maximum value and the minimum value of localization errors in baseline method are much worse than the other three methods. The average values of errors in APS method and AGC method are almost the same. But, the maximum error in APS method is much larger than AGC method and the minimum error in APS method is smaller than AGC method. It means the large errors are really calibrated by AGC method and the appropriate transmitting power decided by APS really improves the accuracy in the best case. By integrating APS and AGC method, the integrated method improves the localization performance in total range. The average error of localization is 32.5cm and 85% of errors is under 50cm. D. Evaluate Integrated Method with Different Number of Reference Tags In regard to 15 deployed reference tags, we respectively use all of them, 10 of them, 5 of them to estimate the position of target tag by integrated method. Fig. 7(e) shows the average value and bounds of error in 64 localization procedure. We note that the average error is small by more number of reference tags. The minimum error is almost the same because the method works well in some small areas within entire localization area. In those areas, estimated positions are both accurate no matter how many reference tags are deployed. However, we note that the maximum error by 10 reference tags is smaller than it by 15 reference tags. It is because more interference existed by more reference tags. But the influence of more reference tags is tiny compared with average error. The maximum error by 5 reference tags is much larger than others caused by lacking of reference tags. E. Evaluate Time Delay of each Method We respectively measure time delays of 4 methods with 64 localization procedures. The average time delay of baseline method and AGC method are both about 2.1 seconds. It means the time-consumption of grid-based calibration procedure is very small. The APS method and Integrated method cost about 0.45 seconds more than the other two methods. It is caused by the procedure of finding the appropriate transmitting power. During the experiments, we note that most time-consumption comes from the tags reading operations. The operations cost most of the time. X. CONCLUSION This paper considers how to provide accurate indoorlocalization by using adaptive methods, from the experimental point of view. We conduct measurements over passive RFID tags in the realistic settings, and propose two adaptive localization methods and an integrated method after analysis of experimental observations. Our experiments show that our localization methods can achieve 31cm in average error and 2.6 seconds in average time. We believe this work gives much insight and inspiration for accurate indoor-localization using passive RFID technology. ACKNOWLEDGMENT This work is partially supported by the National Basic Research Program of China (973) under Grant No.2009CB320705; the National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61021062, 91218302; the JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] H. Choi, Y. Jung, and Y. Baek, “Two-step locating system for harsh marine port environments,” in Proc. of IEEE International Conference on RFID (RFID), 2011, pp. 106–112. [2] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, “The cricket location-support system,” in Proceedings of the 6th annual international conference on Mobile computing and networking. ACM, 2000, pp. 32– 43. [3] S. Azzouzi, M. Cremer, U. Dettmar, R. Kronberger, and T. Knie, “New measurement results for the localization of uhf rfid transponders using an angle of arrival (aoa) approach,” in Proc. of IEEE International Conference on RFID (RFID), 2011, pp. 91–97. [4] R. Miesen, F. Kirsch, and M. Vossiek, “Holographic localization of passive uhf rfid transponders,” in Proc. of IEEE International Conference on RFID (RFID), 2011, pp. 32–37. [5] J. Hightower, G. Borriello, and R. Want, “Spoton: An indoor 3d location sensing technology based on rf signal strength,” Univ. Washington, Tech. Rep., 2000. [6] J. Brchan, L. Zhao, J. Wu, R. Williams, and L. Perez, “A real-time rfid localization experiment using propagation models,” in Proc. of IEEE International Conference on RFID (RFID), 2012, pp. 141–148. [7] Z. Yang, C. Wu, and Y. Liu, “Locating in fingerprint space: Wireless indoor localization with little human intervention,” in Proc. of IEEE MobiCOM, 2012. [8] A. Rai, K. K. Chintalapudi, V. N. Padmanabhan, and R. Sen, “Zee: Zero-effort crowdsourcing for indoor localization,” in Proc. of ACM MOBICOM, 2012. [9] T. Deyle, H. Nguyen, M. Reynolds, and C. Kemp, “Rf vision: Rfid receive signal strength indicator (rssi) images for sensor fusion and mobile manipulation,” in Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009, pp. 5553–5560. [10] L. Ni, Y. Liu, Y. Lau, and P. Abhishek, “Landmarc: Indoor location sensing using active rfid,” Wireless Networks, vol. 10, no. 6, pp. 701– 710, 2004. [11] Y. Zhao, Y. Liu, and L. M. Ni, “Vire: Active rfid-based localization using virtual reference elimination,” in Proc. of the International Conference on Parallel Processing, 2007. [12] W. Zhu, J. Cao, Y. Xu, L. Yang, and J. Kong, “Fault-tolerant rfid reader localization based on passive rfid tags,” in Proc. of IEEE INFOCOM, 2012, pp. 2183–2191. [13] L. Yang, J. Cao, W. Zhu, and S. Tang, “A hybrid method for achieving high accuracy and efficiency in object tracking using passive rfid,” in Proc. of IEEE International Conference on Pervasive Computing and Communications (PerCom), 2012, pp. 109–115
