Search for a Needle in a Haystack:an RFID-based Approach for Efficiently Locating Objects Chuyu Wang,Lei Xie,Sanglu Lu State Key Laboratory for Novel Software Technology,Nanjing University,China Email:wangcyu217@dislab.nju.edu.cn,{Ixie,sanglu}@nju.edu.cn Abstract-In real life,looking for a misplaced object like a uniquely identified according to the ID inside the attached tag key in the room can be usually like searching for a needle in a which works without battery.These characteristics provide us haystack.In this paper,we propose a novel solution to accurately locate the specified objects attached with RFID tags in indoor a good opportunity to locate the specified objects in indoor environments,by efficiently leveraging the RFID technology. environment by leveraging the RFID technology. By making a number of novel observations regarding the tag Therefore,in this paper we design a practical indoor local- reading performance,we obtain several regularities to depict ization method based on the RSSI variation pattern of passive how various parameters including the reader's power and the antenna's scanning angle affect the reading performance.Based RFID system.While aiming to achieve the specified accuracy on the regularities,we have designed very efficient algorithms to in localization,we propose a time-efficient solution to rapidly maximize the accuracy and the time-efficiency for localization. navigate to the target object from a specific initial position. Without the help of any anchor nodes,our solution can rapidly Specifically,we make the following contributions in this paper: navigate to the target object from a specific initial position.We We consider an important problem in real life,i.e.. have implemented a system prototype to evaluate the actual performance in realistic applications.The realistic experiment looking for a misplaced object in the indoor environment, results show that our solution can restrict the average localization which is rarely well studied in related work.To the best error within 49 cm and reduce the total navigation time by 33% of our knowledge,we are the first to consider this typical compared to the baseline solutions. problem by leveraging passive RFID technology. Keywords-Passive RFID,Localization,Iterative approaching, function fitting,binary search We conduct a comprehensive experimental study on passive RFID systems in realistic settings,and obtain I.INTRODUCTION several regularities to depict how various system param eters affect the reading performance,which bring deep Indoor localization has been widely applied as a funda- understanding about the relationship between received mental function in many pervasive applications.Hence,it is signal strength(RSS)and the environment settings. imperative to provide an accurate and time-efficient localiza- Based on the understanding of the above regularities,we tion scheme in indoor environment.In real life,looking for propose an efficient solution for rapidly navigating to the a misplaced object like a key in the room or locating the target object from a specific initial position.By carefully target goods in the warehouse can be usually like searching adjusting the scanning power and scanning angle,we for a needle in a haystack,which is rather time-consuming design efficient algorithms to optimize the accuracy and and inconvenient.Therefore,we focus on a typical scenario the time-efficiency for localization. as follows,i.e.,searching a specified object among a massive We have implemented a system prototype to evaluate the number of objects,from a specific initial point without any actual performance in realistic applications,which shows assistance of anchor nodes.It is a common requirement in that our solution can restrict the average localization error many realistic applications.However,so far it still lacks a within 49 cm and reduce the total navigation time by 33% smart approach to well tackle these issues. compared to the prior solutions. Nowadays,the widely used indoor localization schemes are mainly based on WiFi[1][2]3],bluetooth[4]or Zigbee[5]. II.RELATED WORKS These methods usually provide indoor localization with errors of about 2~3m,which is apparently not suitable to locate Traditional indoor localization methods based on RFID a typical object like a key with fairly small size.Besides, include several forms.Some are based on reference tags or all of these technologies need battery-powered devices,which fingerprint[6][7].which can provide high accuracy.But they greatly restricts the extensive deployment and long-term usage. need lots of manual work before locating and they are hard to Fortunately,with the rapid proliferation of RFID technologies, be migrated to new situations.[8][9][10]focus on physical passive RFID tags have been widely deployed in all kinds of phenomenon for accurate locating,that signals bounce off places to label the everyday items or goods.Each item can be reflectors and lead to dividing features at the receiver.Some researchers build a model for localization[11].But theoretical Corresponding Author:Dr.Lei Xie,Ixie@nju.edu.cn model performs unsatisfactory in realistic environment
Search for a Needle in a Haystack: an RFID-based Approach for Efficiently Locating Objects Chuyu Wang, Lei Xie, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, China Email: wangcyu217@dislab.nju.edu.cn, {lxie, sanglu}@nju.edu.cn Abstract—In real life, looking for a misplaced object like a key in the room can be usually like searching for a needle in a haystack. In this paper, we propose a novel solution to accurately locate the specified objects attached with RFID tags in indoor environments, by efficiently leveraging the RFID technology. By making a number of novel observations regarding the tag reading performance, we obtain several regularities to depict how various parameters including the reader’s power and the antenna’s scanning angle affect the reading performance. Based on the regularities, we have designed very efficient algorithms to maximize the accuracy and the time-efficiency for localization. Without the help of any anchor nodes, our solution can rapidly navigate to the target object from a specific initial position. We have implemented a system prototype to evaluate the actual performance in realistic applications. The realistic experiment results show that our solution can restrict the average localization error within 49 cm and reduce the total navigation time by 33% compared to the baseline solutions. Keywords– Passive RFID, Localization, Iterative approaching, function fitting, binary search I. INTRODUCTION Indoor localization has been widely applied as a fundamental function in many pervasive applications. Hence, it is imperative to provide an accurate and time-efficient localization scheme in indoor environment. In real life, looking for a misplaced object like a key in the room or locating the target goods in the warehouse can be usually like searching for a needle in a haystack, which is rather time-consuming and inconvenient. Therefore, we focus on a typical scenario as follows, i.e., searching a specified object among a massive number of objects, from a specific initial point without any assistance of anchor nodes. It is a common requirement in many realistic applications. However, so far it still lacks a smart approach to well tackle these issues. Nowadays, the widely used indoor localization schemes are mainly based on WiFi[1][2][3], bluetooth[4] or Zigbee[5]. These methods usually provide indoor localization with errors of about 2∼3m, which is apparently not suitable to locate a typical object like a key with fairly small size. Besides, all of these technologies need battery-powered devices, which greatly restricts the extensive deployment and long-term usage. Fortunately, with the rapid proliferation of RFID technologies, passive RFID tags have been widely deployed in all kinds of places to label the everyday items or goods. Each item can be Corresponding Author: Dr. Lei Xie, lxie@nju.edu.cn uniquely identified according to the ID inside the attached tag which works without battery. These characteristics provide us a good opportunity to locate the specified objects in indoor environment by leveraging the RFID technology. Therefore, in this paper we design a practical indoor localization method based on the RSSI variation pattern of passive RFID system. While aiming to achieve the specified accuracy in localization, we propose a time-efficient solution to rapidly navigate to the target object from a specific initial position. Specifically, we make the following contributions in this paper: • We consider an important problem in real life, i.e., looking for a misplaced object in the indoor environment, which is rarely well studied in related work. To the best of our knowledge, we are the first to consider this typical problem by leveraging passive RFID technology. • We conduct a comprehensive experimental study on passive RFID systems in realistic settings, and obtain several regularities to depict how various system parameters affect the reading performance, which bring deep understanding about the relationship between received signal strength (RSS) and the environment settings. • Based on the understanding of the above regularities, we propose an efficient solution for rapidly navigating to the target object from a specific initial position. By carefully adjusting the scanning power and scanning angle, we design efficient algorithms to optimize the accuracy and the time-efficiency for localization. • We have implemented a system prototype to evaluate the actual performance in realistic applications, which shows that our solution can restrict the average localization error within 49 cm and reduce the total navigation time by 33% compared to the prior solutions. II. RELATED WORKS Traditional indoor localization methods based on RFID include several forms. Some are based on reference tags or fingerprint[6][7], which can provide high accuracy. But they need lots of manual work before locating and they are hard to be migrated to new situations. [8][9][10] focus on physical phenomenon for accurate locating, that signals bounce off reflectors and lead to dividing features at the receiver. Some researchers build a model for localization[11]. But theoretical model performs unsatisfactory in realistic environment
Besides,some localization systems are conducted on IV.UNDERSTANDING THE UNDERLYING REGULARITIES robots[12]13],which is used to locate automatically.Deyle IN RFID SYSTEM et al.propose a system to grasp objects by a robot[14].And We conduct several experiments to study the features of Aditya et al.propose a system to index and locate all the RFID.which reveal several original findings in realistic en- objects in the room assisted with a robot[15].Sherlock is vironment.In our experiments,we use Alien-9900 RFID the closest work among these to our own.But it focuses on reader,Alien-9611 linear antenna and ALN-9662 passive locating all the objects in the room,which results in a lot of RFID tag.Without loss of generality,we use the RSSI value time delay.And their theoretical model for localization is not directly got from the Alien-API which ranges from 0 to accurate in reality,which reduces their locating accuracy. 65535 and the value can be converted to value in dBm as: III.PROBLEM DESCRIPTION RSS(dBm)=10*lg(RSSI/65536*2000) In the experiments,we fix the reader and deploy the antenna A.Problem Formulation facing the tag with 1.2m high from the floor.We attach In our system,we consider a typical scenario,i.e.,locating our RFID tag on real objects with the same height.Our the object from a specific initial point without the help of any experiments are conducted in realistic environment,which reference points.It can be widely applied to general scenarios, exposes the performance of passive tag dealing with influence e.g.,locating the misplaced keys in the room,or locating the like multipath effect and path loss. desired good in the warehouse.By means of RFID technology, A.RSSI Varies according to Power and Distance locating the object can be considered as locating the attached target tag with an RFID reader.We use the RFID reader to When the tag-antenna distance exceeds a certain threshold, scan the target field and approach to locate according to the RSSI varies little as the distance increasing.We deploy the RSSI value. tag in front of the antenna,and query the tag with different In this work,we assign the localization accuracy and the transfer powers and different tag-antenna distances.As shown in Fig.1,RSSI value varies a lot when we fix the distance. localization duration as our performance metrics.Specifically, As RSSI falls below 3000,the RSSI variation provides little we define the object's real position is (xtag,ytag)and the reader's initial position is(reader,yreader),which represents discrimination as the distance increasing,which influences the accuracy severely.On the other hand,the curve provides an the position of the reader.We move the reader according to RSSI.When the RSSI value reaches a certain threshold. approach to roughly estimate the distance. we estimate relative position according to the historical data. For small tag-antenna distance,RSSI decreases as the Specifically,the performance metrics are defined as follows: transfer power increases.When we focus on the relationship between the transfer power and the RSSI,we plot Fig.I in localization accuracy:The distance between the real another way,as shown in Fig.2.According to the figure,when position and the estimate position,i.e.,(tag-zreader)2+ the tag-antenna distance is less than 1m.RSSI at 30.7dBm is (ytag-yreader)2,should be as small as possible. smaller than RSSI at lower power.High transfer power obtains localization duration:We consider both navigation time smaller RSSI when dealing with near field communication. and query times as metrics for localization duration This observation is contrary to intuition that high transfer because of robot consuming time power would not perform worse than lower power.Therefore, it is essential for accuracy to consider power stepping when B.Motivation and Challenges narrowing the tag-antenna distance. Based on the above understanding,we design a new lo- RSSI swings little when we fix all the parameters.We calization system using only RFID technology.This work measure the standard deviation of RSSI every 100 samples is different from the previous localization systems based on with the same parameters,and plot the CDF of the swing rate RFID,e.g.,LANDMARC[6],whose principal method mainly of RSSI(std/mean).As shown in Fig.3,RSSI varies within a relies on the reference tags.We focus on how to locate the certain rate with high probability.It guarantees sampling RSSI desired tag from a specific initial point based on RFID mainly. can provide similar information as repetition collection This is a typical scenario in realistic life and it is not practical to deploy reference tags everywhere or collect fingerprint from B.RSSI Varies according to the Rotation of Reader Antenna different places. As the angle changes,RSSI varies in different speed at In our problem,there are several challenges to be solved:different tag-antenna distance.But RSSI always reaches a (a)RSSI got from the reader varies a lot,meaning we need peak when the tag is in front of the antenna and reaches a study the RSSI variation pattern through realistic experiments.small peak behind the antenna.We study the features of the (b)Even if our antenna is directed,it can identify tags in a antenna for accurate localization.We experiment on 5 typical large range,which may reduce the accuracy.(c)There are distances,then we rotate the antenna as Fig.5 continuously. no reference tags or fingerprints which can provide extra The result is shown in Fig.4,and we note that RSSI variation information.New approaches should be used to locate the pattern submits to quadratic function.Besides,the antenna can object.(d)How to combine the information we get to satisfy identify the tag behind it if the tag-antenna distance is small the high demand in accuracy and time-delay. enough,which can confuse the orientation decision
Besides, some localization systems are conducted on robots[12][13], which is used to locate automatically. Deyle et al. propose a system to grasp objects by a robot[14]. And Aditya et al. propose a system to index and locate all the objects in the room assisted with a robot[15]. Sherlock is the closest work among these to our own. But it focuses on locating all the objects in the room, which results in a lot of time delay. And their theoretical model for localization is not accurate in reality, which reduces their locating accuracy. III. PROBLEM DESCRIPTION A. Problem Formulation In our system, we consider a typical scenario, i.e., locating the object from a specific initial point without the help of any reference points. It can be widely applied to general scenarios, e.g., locating the misplaced keys in the room, or locating the desired good in the warehouse. By means of RFID technology, locating the object can be considered as locating the attached target tag with an RFID reader. We use the RFID reader to scan the target field and approach to locate according to the RSSI value. In this work, we assign the localization accuracy and the localization duration as our performance metrics. Specifically, we define the object’s real position is (xtag, ytag) and the reader’s initial position is (xreader, yreader), which represents the position of the reader. We move the reader according to RSSI. When the RSSI value reaches a certain threshold, we estimate relative position according to the historical data. Specifically, the performance metrics are defined as follows: • localization accuracy: The distance between the real position and the estimate position ,i.e.,(xtag−xreader) 2+ (ytag − yreader) 2 , should be as small as possible. • localization duration: We consider both navigation time and query times as metrics for localization duration because of robot consuming time. B. Motivation and Challenges Based on the above understanding, we design a new localization system using only RFID technology. This work is different from the previous localization systems based on RFID, e.g., LANDMARC[6], whose principal method mainly relies on the reference tags. We focus on how to locate the desired tag from a specific initial point based on RFID mainly. This is a typical scenario in realistic life and it is not practical to deploy reference tags everywhere or collect fingerprint from different places. In our problem, there are several challenges to be solved: (a) RSSI got from the reader varies a lot, meaning we need study the RSSI variation pattern through realistic experiments. (b) Even if our antenna is directed, it can identify tags in a large range, which may reduce the accuracy. (c) There are no reference tags or fingerprints which can provide extra information. New approaches should be used to locate the object. (d) How to combine the information we get to satisfy the high demand in accuracy and time-delay. IV. UNDERSTANDING THE UNDERLYING REGULARITIES IN RFID SYSTEM We conduct several experiments to study the features of RFID, which reveal several original findings in realistic environment. In our experiments, we use Alien-9900 RFID reader , Alien-9611 linear antenna and ALN-9662 passive RFID tag. Without loss of generality, we use the RSSI value directly got from the Alien-API which ranges from 0 to 65535 and the value can be converted to value in dBm as: RSS(dBm) = 10 ∗ lg(RSSI/65536 ∗ 2000) In the experiments, we fix the reader and deploy the antenna facing the tag with 1.2m high from the floor. We attach our RFID tag on real objects with the same height . Our experiments are conducted in realistic environment, which exposes the performance of passive tag dealing with influence like multipath effect and path loss. A. RSSI Varies according to Power and Distance When the tag-antenna distance exceeds a certain threshold, RSSI varies little as the distance increasing. We deploy the tag in front of the antenna, and query the tag with different transfer powers and different tag-antenna distances. As shown in Fig. 1, RSSI value varies a lot when we fix the distance. As RSSI falls below 3000, the RSSI variation provides little discrimination as the distance increasing, which influences the accuracy severely. On the other hand, the curve provides an approach to roughly estimate the distance. For small tag-antenna distance, RSSI decreases as the transfer power increases. When we focus on the relationship between the transfer power and the RSSI, we plot Fig. 1 in another way, as shown in Fig. 2. According to the figure, when the tag-antenna distance is less than 1m, RSSI at 30.7dBm is smaller than RSSI at lower power. High transfer power obtains smaller RSSI when dealing with near field communication. This observation is contrary to intuition that high transfer power would not perform worse than lower power. Therefore, it is essential for accuracy to consider power stepping when narrowing the tag-antenna distance. RSSI swings little when we fix all the parameters. We measure the standard deviation of RSSI every 100 samples with the same parameters, and plot the CDF of the swing rate of RSSI(std/mean). As shown in Fig. 3, RSSI varies within a certain rate with high probability. It guarantees sampling RSSI can provide similar information as repetition collection. B. RSSI Varies according to the Rotation of Reader Antenna As the angle changes, RSSI varies in different speed at different tag-antenna distance. But RSSI always reaches a peak when the tag is in front of the antenna and reaches a small peak behind the antenna. We study the features of the antenna for accurate localization. We experiment on 5 typical distances, then we rotate the antenna as Fig. 5 continuously. The result is shown in Fig. 4, and we note that RSSI variation pattern submits to quadratic function. Besides, the antenna can identify the tag behind it if the tag-antenna distance is small enough, which can confuse the orientation decision
25,000 715.7cBm 女18.7B 25.000 20.00 t-21.78 +20cm 20.000 60cm 15,.00 日B0cm %100en *-200行 0.00 -300m 5.000 02 35 0 0.4 0. 0.B 0-0050ara Fig.1. RSSI varies with transfer Fig.2.RSSI varies with transfer power Fig.3. Magnitude of RSSI swing in Fig.4.RSSI varies with the angle of distance CDF the reader tag 12000 12000 Reader antenna 10000 1000 8000 800 1 E000 6000 ② 0 400 0 2000 2001 Left Reader antenna 20 80 tag View rotation angle(degree) rotation angle(degree) Fig.5.Experiment deployment of Fig.6.RSSI varies with rotating the Fig.7.RSSI varies with rotating the Fig.8.Experiment deployment of rotating the reader tag around the axis tag in the plane rotating the tag C.RSSI Varies according to the Rotation of Tag Database RSSI varies little when the tag rotates around the axis, but RSSI varies as sine function when the tag rotates in the Data plane.Beside the orientation of the antenna,we consider the Locate processing orientation of the tag.We study two orientations of the tag method rotation,as shown in Fig.8.The first path is rotating the tag in the plane and the second represents spinning on the tag's control Scan Move and Rotate axes.We place a tag 2m in front of the antenna to conduct the experiments.As a result,Fig.6 represents spinning on the hardware Reader Robot axis,and Fig.7 represents rotating in the plane.We note that spinning on the axis has little influence on RSSI variation, but rotating in the plane changes RSSI like the sine function. Because the RSSI variation caused by the tag deployment may Fig.9.System architecture lead the indeterminate of the localization,we deploy our tag vertically to reduce the complexity. approaching.As shown in Fig.9,our localization system is D.Analysis consist of 3 main layers.Specifically,hardware layer includes all the devices,i.e.,reader and robot.And the control layer is According to the above results,we note several problems to be solved.We cannot estimate the accurate distance directly in charge of data interaction between the other two layers and from the RSSI value due to the noise.The antenna can identify conducting the command from the data processing layer.At the tag at the back,which will mislead the angle estimation. last,the data processing layer executes the localization method But we can still extracts opportunities from the results.RSSI and commands all the devices.With the architecture above,we are interested in how to locate to the object accurately with can provide the rough scope of the tag position and we can estimate the angle according to the RSSI variation pattern.The limited query duration in realistic environment. vertical deployed tag can reduce the complexity. VI.PATTERN BASED LOCALIZATION SOLUTION V.SYSTEM DESIGN Our pattern based localization solution contains four compo- In our system,objects are attached with an RFID tag for nents.Firstly,we scan the filed with Coarse-grained Rotation discontinuous identification.The RFID reader provides large to roughly determine the sector.Then we preprocess the sector transfer power range for dealing with different scenarios.To data with binary search to provide enough data for Fine locate automatically,we use a robot car to help rotating and Rotation.Thirdly,we do quadratic function fitting iteratively
0 100 200 300 400 500 0 5,000 10,000 15,000 20,000 25,000 distance(cm) RSSI 15.7dBm 18.7dBm 21.7dBm 24.7dBm 27.7dBm 30.7dBm Fig. 1. RSSI varies with transfer distance 15 20 25 30 35 0 5,000 10,000 15,000 20,000 25,000 transfer power(dBm) RSSI 20cm 40cm 60cm 80cm 100cm 200cm 300cm Fig. 2. RSSI varies with transfer power 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 std/mean cdf Fig. 3. Magnitude of RSSI swing in CDF −150 −100 −50 0 50 100 150 0 2000 4000 6000 8000 10000 reader angle(degree) RSSI 1m 2m 3m 4m 5m Fig. 4. RSSI varies with the angle of the reader Fig. 5. Experiment deployment of rotating the reader 0 20 40 60 80 0 2000 4000 6000 8000 10000 12000 rotation angle(degree) RSSI 1m 2m 3m 4m Fig. 6. RSSI varies with rotating the tag around the axis 0 20 40 60 80 0 2000 4000 6000 8000 10000 12000 rotation angle(degree) RSSI 1m 2m 3m 4m Fig. 7. RSSI varies with rotating the tag in the plane Fig. 8. Experiment deployment of rotating the tag C. RSSI Varies according to the Rotation of Tag RSSI varies little when the tag rotates around the axis, but RSSI varies as sine function when the tag rotates in the plane. Beside the orientation of the antenna, we consider the orientation of the tag. We study two orientations of the tag rotation, as shown in Fig. 8. The first path is rotating the tag in the plane and the second represents spinning on the tag’s axes. We place a tag 2m in front of the antenna to conduct the experiments. As a result, Fig. 6 represents spinning on the axis, and Fig. 7 represents rotating in the plane. We note that spinning on the axis has little influence on RSSI variation, but rotating in the plane changes RSSI like the sine function. Because the RSSI variation caused by the tag deployment may lead the indeterminate of the localization, we deploy our tag vertically to reduce the complexity. D. Analysis According to the above results, we note several problems to be solved. We cannot estimate the accurate distance directly from the RSSI value due to the noise. The antenna can identify the tag at the back, which will mislead the angle estimation. But we can still extracts opportunities from the results. RSSI can provide the rough scope of the tag position and we can estimate the angle according to the RSSI variation pattern. The vertical deployed tag can reduce the complexity. V. SYSTEM DESIGN In our system, objects are attached with an RFID tag for discontinuous identification. The RFID reader provides large transfer power range for dealing with different scenarios. To locate automatically, we use a robot car to help rotating and Fig. 9. System architecture approaching. As shown in Fig. 9, our localization system is consist of 3 main layers. Specifically, hardware layer includes all the devices, i.e., reader and robot. And the control layer is in charge of data interaction between the other two layers and conducting the command from the data processing layer. At last, the data processing layer executes the localization method and commands all the devices. With the architecture above, we are interested in how to locate to the object accurately with limited query duration in realistic environment. VI. PATTERN BASED LOCALIZATION SOLUTION Our pattern based localization solution contains four components. Firstly, we scan the filed with Coarse-grained Rotation to roughly determine the sector. Then we preprocess the sector data with binary search to provide enough data for Fine Rotation. Thirdly, we do quadratic function fitting iteratively
to approximate the angle of the target.At last,we approach samples.At last,we transmit the nonzero RSSI samples and the target and rectify the angle iteratively until the collecting the boundary as data set Rangle for Fine-grained rotation. information is enough to locate accurately.In order to estimate the rough distance,we measure the curve in Fig.1 and store Algorithm 2 Data Preprocessing it in the database Tis as ideal RSSI feature. Require:0maz and rssi_map 1:0L=8mar-40,0r=0(max)+40 Algorithm 1 Coarse-grained rotation 2:if rssio =0 and rssiog =0 then Require:nE(0,1)for judging RSSI peak,T for judging the while 6mar -eL 1 do RSSI value 4: 0L =(0mar +0L)/2 and OR=(0ma+0R)/2 1:for 0 from 0360 step by 40 and collect rssi do 5 if rssi>0 or rssiog >0 then 2: add tuple (0,rssie)into list rssi_map 6: break 3: record the tuple with largest RSSI(0maz,rssimar) 7: end if 头 if rssio 1 do 14:return 0maz 3: add Best to Rangle 4: Omar -rssidest rssiomaz?0est:Omar 5: do quadratic function fitting on Rangle and set 0est to A.Coarse-grained Scan the peak of the function The Coarse-grained Scan is used to roughly determine the 6: sort(Rangle)and leng=length(Rangle) sector of the object.Because our antenna's 3dB beamwidth is 7: Oest=(0est Rangle[O])?(0L Rangle[1])/2:0est 40°，we sample the RSSI value every4o°to roughly determine 8: Best =(0est Rangle[leng-1])?(OR+Ranglelleng- which 40 sector the object is located in.As shown in Alg. 2])/2:0est 9:end while 1,we rotate the antenna and collect RSSI every 40 until detecting the first peek.The parameter n represents the swing 10:return Qest rate of the RSSI value from Fig.3.The parameter r means if RSSI is below T,the RSSI value varies little when we rotate the antenna.Instead of rotating the whole circle,once we got C.Fine-grained Rotation the peek,we skip other rotation samples.The only extra work As shown in Fig.4,we realize when we rotate the antenna. is to check the back of the antenna,because the antenna would RSSI varies following a special pattern.If the RSSI patterns identify tags at the back in near field communication.If the at different tag-antenna distances can be distinguished,we can RSSI value of the target sector is smaller than a threshold T, determine the orientation easily.To reveal the effectiveness we just move along the target sector according to RSSI and the of the RSSI pattern,we do quadratic function fitting on the database Tdis.Then we do the coarse-grained scan again to data set of Fig.4.We use the peak of the fitting quadratic estimate the rough sector.At last,we transmit all the collected function to represent the estimated tag orientation.And the samples to the Data Preprocessing section for further handling. result shows the difference between the estimate angle and real angle is [0.21,-0.04,4.65,1.76,10.41]representing different B.Data Preprocessing distances,i.e.,[1m,2m,3m,4m,5m],which is accurate enough for After determining the rough sector,we handle the raw data fine-grained localization. to generate enough information for fined-grained rotation,i.e., Based on the analysis above,we propose Fined-grained at least 3 neighboring nonzero RSSI samples for quadratic Rotation method,as shown in Alg.3.The whole process is an function fitting.As shown in Alg.2,when the two neighboring iterative function,which terminates until the estimate angle is samples of the target sector are both zero,we do binary similar as the angle with largest RSSI.In the iterative function, search in both sector until we find a nonzero sample.At the we do quadratic function fitting on the data set Rangle,which same time,we can shrink the search range.If there is only is got from the Data Preprocessing.We estimate the angle a neighboring sample's RSSI is zero,we just need to add 0est according to the result of the quadratic function.If est a sample whose angle is in the middle of the two nonzero is beyond the search scope,we will set best to middle of the
to approximate the angle of the target. At last, we approach the target and rectify the angle iteratively until the collecting information is enough to locate accurately. In order to estimate the rough distance, we measure the curve in Fig. 1 and store it in the database Tdis as ideal RSSI feature. Algorithm 1 Coarse-grained rotation Require: η ∈ (0, 1) for judging RSSI peak, τ for judging the RSSI value 1: for θ from 0 → 360 step by 40 and collect rssi do 2: add tuple (θ, rssiθ) into list rssi map 3: record the tuple with largest RSSI (θmax, rssimax) 4: if rssiθ 1 do 4: θL = (θmax + θL)/2 and θR = (θmax + θR)/2 5: if rssiθL > 0 or rssiθR > 0 then 6: break 7: end if 8: end while 9: end if 10: θM = (rssiθL = 0)?(θmax + θR)/2 : θM 11: θM = (rssiθR = 0)?(θmax + θL)/2 : θM 12: return set Rangle ← (θL, θmax, θM , θR) Algorithm 3 Fine-grained Rotation Require: threshold α for estimate the angle 1: θest = null 2: while | θest − θmax |> 1 do 3: add θest to Rangle 4: θmax = rssiθest > rssiθmax ?θest : θmax 5: do quadratic function fitting on Rangle and set θest to the peak of the function 6: sort(Rangle) and leng = length(Rangle) 7: θest = (θest Rangle[leng − 1])?(θR + Rangle[leng − 2])/2 : θest 9: end while 10: return θest C. Fine-grained Rotation As shown in Fig. 4, we realize when we rotate the antenna, RSSI varies following a special pattern. If the RSSI patterns at different tag-antenna distances can be distinguished, we can determine the orientation easily. To reveal the effectiveness of the RSSI pattern, we do quadratic function fitting on the data set of Fig. 4. We use the peak of the fitting quadratic function to represent the estimated tag orientation. And the result shows the difference between the estimate angle and real angle is [0.21,-0.04,4.65,1.76,10.41] representing different distances,i.e.,[1m,2m,3m,4m,5m],which is accurate enough for fine-grained localization. Based on the analysis above, we propose Fined-grained Rotation method, as shown in Alg. 3. The whole process is an iterative function, which terminates until the estimate angle is similar as the angle with largest RSSI. In the iterative function, we do quadratic function fitting on the data set Rangle, which is got from the Data Preprocessing. We estimate the angle θest according to the result of the quadratic function. If θest is beyond the search scope, we will set θest to middle of the
ntenn 0.8 0.8 0.6 0.6 0.4 0.4 0.2 -baseline solution 0.2 -pattern based solution ---pattem based solution Reader ---baseline solution 50 100 0 50 100 150 200 error(cm) time(second) Fig.10.Realistic experiment robot Fig.11.CDF of localization error Fig.12.CDF of localization time-delay 100 0.7 80 0 6 0.4 total coarse-rotation 0.3 -fitting 02 -data-preprocessing 。approaching 40 60 2 25 7 125 175 225 query times process iterations(times) real distance(cm) Fig.13.Query times of different modules Fig.14.Estimate angle of process iterations Fig.15. Error of estimate distance in different distance boundary and its neighbor.We then add best to Rangle for D.Iterative Approach further estimating.As the process running,Rangle becomes larger which can guarantee the final result is close enough to Getting the angle,we approach the target as shown in Alg.4. Tais is the database for estimating the distance roughly and the real angle as analyzed before. Kis the threshold to terminate the localization.n plays the same role as in Alg.1.We iteratively approach the target Algorithm 4 Antenna Approach until RSSI reaches the threshold k.At each iterative step. Require:Tais =(dis,rssi)for estimating the distance,k to we generate moving distance disnew-disest according to terminate and n E(0,1)for judging RSSI difference the corresponding RSSI value in Tais.The moving distance 1:while rssi <k do should eliminate the influence of RSSI swing as shown in 2: disest Tdis.DistanceAt(rssi) line 3 of Alg.4.After approaching,we check rssinew to 3 move disnew-disest according to Tdis to guarantee decide to iteratively approach or to rectify the angle in the Tdis(disest)*(1+2*n)<Tdis(disneu)*(1-2*n) next step.In realistic environment,we cannot guarantee RSSI 4 if rssinew Tdis(disnew)*(1-n)or rssinew can reach the threshold K.So when the re-estimated angle Tdis(disnew)*(1+n)then est represents the historical orientation,we also terminate the 5: call Alg.3 to re-estimate the angle iterative function.It means we have crossed the target without 6: if the new best represents the historical orientation reaching the threshold.Lastly,we estimate the relative position then according all the historical data collected before. 7: break 8: end if E.Analysis adjust Tais according to the new angle and rssi 10: estimate the distance according to present RSSI data With using the pattern based localization method,we rotate 11: end if the antenna and approach to the target for localization without 12:end while reference points.In our method,parameters,i.e.,n,,T,decide 13:estimate the position according to all the historical data the final localization performance on the whole.Specifically, n distinguishes the difference reason between RSSI variation
Fig. 10. Realistic experiment robot 0 50 100 150 0 0.2 0.4 0.6 0.8 1 error(cm) cdf baseline solution pattern based solution Fig. 11. CDF of localization error 0 50 100 150 200 0 0.2 0.4 0.6 0.8 1 time(second) cdf pattern based solution baseline solution Fig. 12. CDF of localization time-delay 0 20 40 60 80 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 query times cdf total coarse−rotation fitting data−preprocessing approaching Fig. 13. Query times of different modules 1 2 3 4 5 0 5 10 15 20 process iterations(times) angle error(degree) Fig. 14. Estimate angle of process iterations 25 75 125 175 225 0 20 40 60 80 100 120 real distance(cm) error distance(cm) Fig. 15. Error of estimate distance in different distance boundary and its neighbor. We then add θest to Rangle for further estimating. As the process running, Rangle becomes larger which can guarantee the final result is close enough to the real angle as analyzed before. Algorithm 4 Antenna Approach Require: Tdis = (dis, rssi) for estimating the distance, κ to terminate and η ∈ (0, 1) for judging RSSI difference 1: while rssi Tdis(disnew) ∗ (1 + η) then 5: call Alg. 3 to re-estimate the angle 6: if the new θest represents the historical orientation then 7: break 8: end if 9: adjust Tdis according to the new angle and rssi 10: estimate the distance according to present RSSI data 11: end if 12: end while 13: estimate the position according to all the historical data D. Iterative Approach Getting the angle, we approach the target as shown in Alg.4. Tdis is the database for estimating the distance roughly and κ is the threshold to terminate the localization. η plays the same role as in Alg. 1. We iteratively approach the target until RSSI reaches the threshold κ. At each iterative step, we generate moving distance disnew − disest according to the corresponding RSSI value in Tdis. The moving distance should eliminate the influence of RSSI swing as shown in line 3 of Alg. 4. After approaching, we check rssinew to decide to iteratively approach or to rectify the angle in the next step. In realistic environment, we cannot guarantee RSSI can reach the threshold κ. So when the re-estimated angle θest represents the historical orientation, we also terminate the iterative function. It means we have crossed the target without reaching the threshold. Lastly, we estimate the relative position according all the historical data collected before. E. Analysis With using the pattern based localization method, we rotate the antenna and approach to the target for localization without reference points. In our method, parameters, i.e.,η, κ, τ, decide the final localization performance on the whole. Specifically, η distinguishes the difference reason between RSSI variation
which is related to time delay.K and T represents different VIII.CONCLUSION thresholds in RSSI.Thereinto,r concerns the rough distance We have presented a system for locating objects without to start estimating angle and k is used to terminate the whole reference points based on RFID from the experimental point process,which are related to the environment and demand of view.This system is suited for a typical scenario,i.e., of accuracy.All the parameters have an overall effect on locating an object from a specific point.We propose an the performance of localization,which can be determined iterative pattern based localization method according to several according to the accuracy demand and the environment. performance experiments and conduct the system experiment in the realistic environment.Our experiments show that our VII.PERFORMANCE EVALUATION method can achieve average error within 49cm and reduce We evaluate the performance of our system in realistic the total navigation time by 33%compared to the baseline solution environment.Our experiment platform is based mainly on the robot,as shown in Fig.10.We deploy different tag- ACKNOWLEDGMENTS attached objects in the room with the same height as the This work is supported in part by National Natural Science antenna and examine our system by locating each objects 50 Foundation of China under Grant No.61100196.61073028. times.To reveal the advantage of the pattern based method,we 61321491,91218302;JiangSu Natural Science Foundation compare with a baseline solution,described below.We rotate under Grant No.BK2011559. the antenna a whole circle and scan the field meanwhile.Then the antenna approaches along the angle representing the largest REFERENCES RSSI value iteratively until locating the object.At the same [1]B.Ferris,D.Fox,and N.D.Lawrence,"Wifi-slam using gaussian time,we rectify the angle to improve the accuracy. 12Pangnnytm based o As shown in Fig.11,without any help of reference tags, discriminant-adaptive neural network in ieee 802.11 environments," near 80%objects localization error is within 60cm.which is Neural Networks,IEEE Transactions on,2008. accurate enough for realistic application.And Fig.12 shows [3]S.-H.Fang,T.-N.Lin,and K.-C.Lee,"A novel algorithm for multipath that about 80%objects are located within 60 seconds,which fingerprinting in indoor wlan environments,"Wireless Communications. IEEE Transactions on,2008. is bearable dealing with realistic problem.When compared [4]L.Aalto,N.Gothlin,J.Korhonen,and T.Ojala,"Bluetooth and wap with the baseline solution,pattern based method reduces the push based location-aware mobile advertising system,"in Proceedings average navigation time by 33%.In regard to the accuracy, of the 2nd international conference on Mobile systems,applications,and services,2004. because the distance measurement is mainly based on the [5]J.Blumenthal,R.Grossmann,F.Golatowski,and D.Timmermann, RSSI samples with the smallest tag-antenna distance,the two "Weighted centroid localization in zigbee-based sensor networks,"in methods share similar localization error. Intelligent Signal Processing.2007.WISP 2007.IEEE International Symposium on,2007. In order to deeply understanding the time delay,we analyze [6]L.M.Ni,Y.Liu,Y.C.Lau,and A.P.Patil,"Landmarc:indoor location query times individually.As shown in Fig.13,the overall sensing using active rfid,"Wireless networks,2004. query times is less than 60 times,which costs less than 10 [7]J.Wang and D.Katabi,"Dude,where's my card?:Rfid positioning that works with multipath and non-line of sight,"in Proceedings of the ACM seconds in reality.Besides,we note coarse-rotation occupies SIGCOMM 2013 conference on SIGCOMM.2013. the most query times.This is because in realistic environment, [8]P.V.Nikitin,R.Martinez.S.Ramamurthy.H.Leland,G.Spiess,and the RSSI value is not stable caused by multipath effect, K.Rao."Phase based spatial identification of uhf rfid tags,"in RFID, 2010 IEEE International Conference on,2010. which results in several iterative angle estimate processes. [9]S.Azzouzi,M.Cremer,U.Dettmar,R.Kronberger,and T.Knie, And fine-grained rotation only occupies about 10 times,which "New measurement results for the localization of uhf rfid transponders proves quadratic function fitting plays an important role.In the using an angle of arrival (aoa)approach,"in RFID (RFID).2011 IEEE International Conference on,2011. baseline solution,continuous scanning leads to hundreds query [10] C.Hekimian-Williams,B.Grant,X.Liu,Z.Zhang,and P.Kumar, times,which is abridged in the figure. "Accurate localization of rfid tags using phase difference,"in RFID. 2010 IEEE International Conference on.2010. Beside the performance of localization as a whole,we [11]J.Hightower,R.Want,and G.Borriello,"Spoton:An indoor 3d evaluate the performance of iterative routine.As shown in location sensing technology based on rf signal strength,"UW CSE00. Fig.14,when we re-estimate the angle iteratively,we can 02-02,University of Washington,Department of Computer Science and Engineering.Seattle.WA. reduce the angle error,which means the iterative routine [12]D.Hahnel,W.Burgard,D.Fox,K.Fishkin,and M.Philipose,"Mapping effectively improve the accuracy.Because most localizations and localization with rfid technology,"in Robotics and Automation are done in the first three iterations.the forth iteration contains Proceedings.ICRA'04.2004 IEEE International Conference on.2004. [13]R.Miesen,F.Kirsch,and M.Vossiek,"Holographic localization of fewer samples leading to bigger error slightly. passive uhf rfid transponders."in RFID (RFID).2011 IEEE International In Fig.15,we compare the estimate distance in each Conference on,2011. approaching step with the real position of objects.In the [14]T.Deyle,H.Nguyen,M.Reynolds,and C.C.Kemp."Rf vision:Rfid receive signal strength indicator (rssi)images for sensor fusion and figure,x axis represents the real tag-antenna distance range. mobile manipulation,"in Intelligent Robots and Systems.2009.IROS As distance decreases,the estimate distance error decreases, 2009.IEEE/RSJ International Conference on,2009. which is due to the RSSI at close tag-antenna distance can [15]A.Nemmaluri,M.D.Corner,and P.Shenoy,"Sherlock:automatically locating objects for humans,"in Proceedings of the 6th international provide more reliable RSSI information for localization.This conference on Mobile systems,applications,and services,2008. is the main advantage of the iterative routine
which is related to time delay. κ and τ represents different thresholds in RSSI. Thereinto, τ concerns the rough distance to start estimating angle and κ is used to terminate the whole process, which are related to the environment and demand of accuracy. All the parameters have an overall effect on the performance of localization, which can be determined according to the accuracy demand and the environment. VII. PERFORMANCE EVALUATION We evaluate the performance of our system in realistic environment. Our experiment platform is based mainly on the robot, as shown in Fig. 10. We deploy different tagattached objects in the room with the same height as the antenna and examine our system by locating each objects 50 times. To reveal the advantage of the pattern based method, we compare with a baseline solution, described below. We rotate the antenna a whole circle and scan the field meanwhile. Then the antenna approaches along the angle representing the largest RSSI value iteratively until locating the object. At the same time,we rectify the angle to improve the accuracy. As shown in Fig. 11, without any help of reference tags, near 80% objects localization error is within 60cm, which is accurate enough for realistic application. And Fig. 12 shows that about 80% objects are located within 60 seconds, which is bearable dealing with realistic problem. When compared with the baseline solution, pattern based method reduces the average navigation time by 33%. In regard to the accuracy, because the distance measurement is mainly based on the RSSI samples with the smallest tag-antenna distance, the two methods share similar localization error. In order to deeply understanding the time delay, we analyze query times individually. As shown in Fig. 13, the overall query times is less than 60 times, which costs less than 10 seconds in reality. Besides, we note coarse-rotation occupies the most query times. This is because in realistic environment, the RSSI value is not stable caused by multipath effect, which results in several iterative angle estimate processes. And fine-grained rotation only occupies about 10 times, which proves quadratic function fitting plays an important role. In the baseline solution, continuous scanning leads to hundreds query times, which is abridged in the figure. Beside the performance of localization as a whole, we evaluate the performance of iterative routine. As shown in Fig.14, when we re-estimate the angle iteratively, we can reduce the angle error, which means the iterative routine effectively improve the accuracy. Because most localizations are done in the first three iterations, the forth iteration contains fewer samples leading to bigger error slightly. In Fig. 15, we compare the estimate distance in each approaching step with the real position of objects . In the figure, x axis represents the real tag-antenna distance range. As distance decreases, the estimate distance error decreases, which is due to the RSSI at close tag-antenna distance can provide more reliable RSSI information for localization. This is the main advantage of the iterative routine. VIII. CONCLUSION We have presented a system for locating objects without reference points based on RFID from the experimental point of view. This system is suited for a typical scenario, i.e., locating an object from a specific point. We propose an iterative pattern based localization method according to several performance experiments and conduct the system experiment in the realistic environment. Our experiments show that our method can achieve average error within 49cm and reduce the total navigation time by 33% compared to the baseline solution. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61321491, 91218302; JiangSu Natural Science Foundation under Grant No. BK2011559. REFERENCES [1] B. Ferris, D. Fox, and N. D. Lawrence, “Wifi-slam using gaussian process latent variable models.” in IJCAI, 2007. [2] S.-H. Fang and T.-N. Lin, “Indoor location system based on discriminant-adaptive neural network in ieee 802.11 environments,” Neural Networks, IEEE Transactions on, 2008. [3] S.-H. Fang, T.-N. Lin, and K.-C. Lee, “A novel algorithm for multipath fingerprinting in indoor wlan environments,” Wireless Communications, IEEE Transactions on, 2008. [4] L. Aalto, N. G ¨othlin, J. Korhonen, and T. Ojala, “Bluetooth and wap push based location-aware mobile advertising system,” in Proceedings of the 2nd international conference on Mobile systems, applications, and services, 2004. [5] J. Blumenthal, R. Grossmann, F. Golatowski, and D. Timmermann, “Weighted centroid localization in zigbee-based sensor networks,” in Intelligent Signal Processing, 2007. WISP 2007. IEEE International Symposium on, 2007. [6] L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, “Landmarc: indoor location sensing using active rfid,” Wireless networks, 2004. [7] J. Wang and D. Katabi, “Dude, where’s my card?: Rfid positioning that works with multipath and non-line of sight,” in Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM, 2013. [8] P. V. Nikitin, R. Martinez, S. Ramamurthy, H. Leland, G. Spiess, and K. Rao, “Phase based spatial identification of uhf rfid tags,” in RFID, 2010 IEEE International Conference on, 2010. [9] 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 RFID (RFID), 2011 IEEE International Conference on, 2011. [10] C. Hekimian-Williams, B. Grant, X. Liu, Z. Zhang, and P. Kumar, “Accurate localization of rfid tags using phase difference,” in RFID, 2010 IEEE International Conference on, 2010. [11] J. Hightower, R. Want, and G. Borriello, “Spoton: An indoor 3d location sensing technology based on rf signal strength,” UW CSE 00- 02-02, University of Washington, Department of Computer Science and Engineering, Seattle, WA. [12] D. Hahnel, W. Burgard, D. Fox, K. Fishkin, and M. Philipose, “Mapping and localization with rfid technology,” in Robotics and Automation. Proceedings. ICRA’04. 2004 IEEE International Conference on, 2004. [13] R. Miesen, F. Kirsch, and M. Vossiek, “Holographic localization of passive uhf rfid transponders,” in RFID (RFID), 2011 IEEE International Conference on, 2011. [14] T. Deyle, H. Nguyen, M. Reynolds, and C. C. Kemp, “Rf vision: Rfid receive signal strength indicator (rssi) images for sensor fusion and mobile manipulation,” in Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, 2009. [15] A. Nemmaluri, M. D. Corner, and P. Shenoy, “Sherlock: automatically locating objects for humans,” in Proceedings of the 6th international conference on Mobile systems, applications, and services, 2008