Efficient Localization based on Imprecise Anchors in RFID System Xiang Lu,Lei Xie,Yafeng Yin,Wei Wang,Baoliu Ye,Sanglu Lu State Key Laboratory for Novel Software Technology,Nanjing University,China Email:{luxiang,yyf}@dislab.nju.edu.cn,{Ixie,ww,yebl,sanglu}@nju.edu.cn Abstract-With the rapid proliferation of RFID-based appli- walking around,e.g.,the reader is deployed in the shopping cations,RFID tags have been deployed into pervasive spaces in cart,it is possible to locate the user according to the categories increasingly large numbers,e.g.,the shelves of super markets are of the scanned tags and the layout of the merchandize.When filled with tag-labeled items.Conventional localization schemes usually leverage precise anchor nodes to help compute the multiple categories of tags are scanned,the reader's location position of objects.However,it is usually difficult to find or can be computed more accurately by sufficiently leveraging deploy enough anchor nodes for accurate localization.In this the layout information of these categories. paper,we propose solutions to locate the mobile users based Based on the above understanding,we propose solutions to on imprecise anchors in RFID systems.A large number of tags locate the mobile user based on imprecise anchor nodes in with approximate locations are used as anchor nodes to compute the user's locations.We thus present a time-efficient localization RFID systems in this paper.Such localization solutions need scheme to continuously tracking the mobile users.Experimental to resolve two key challenges in order to provide precise and results indicate that our solutions can accurately locate the mobile timely user location.Firstly,the anchor positions are impre- users in a real-time approach.The improved method's accuracy cise.Items of the same category can be placed in a range rather is more than 30%better than the base solution. than on a precise point on the shelf.Furthermore,the reader Index Terms-RFID;Tags filled environment;Localization; may miss some of the nearby RFID tags due to imperfect Reader-based:location estimation radio environments.Our localization scheme must handle such uncertainty to provide reliable user locations.Secondly,most I.INTRODUCTION RFID readers takes more time to scan nearby RFID tags when The proliferation of wireless and mobile devices has fos- the density of RFID is increased.As our system utilizes a large tered the demand for context-aware or location-based services number of existing RFID tags for localization,we need to find in pervasive applications [1-4].For example,while a user is a way to return useful information in a timely manner even if shopping in the super market,the relevant advertisements can the reader is surrounded by thousands of RFID tags. be popped up in time when he is approaching a shelf with We thus present a time-efficient localization scheme to specified goods.In regard to these applications,location is continuously tracking the mobile user.Experimental results viewed as one of the most significant factors.Conventional indicate that our solutions can accurately locate the mobile localization schemes mainly leverage precise anchor nodes users by a real-time approach.The main contributions of this to help compute the user's location [5-8].These anchor paper are summarized as follows: nodes are intentionally deployed for localization.However,it 。 We propose an efficient localization scheme based on is difficult to find or deploy enough anchor nodes for accurate the large number of tags scanned by the RFID reader, localization,due to the very expensive deployment cost. it does not require any additional precise anchor nodes, With the rapid proliferation of RFID-based applications thus effectively avoids the significant deployment cost. [9-13],RFID tags have been deployed into pervasive spaces To the best of our knowledge,this is the first localization in increasingly large numbers,e.g.,in the libraries or super work based on imprecise anchor nodes in RFID systems. markets,the shelves are always filled with tag-labeled items. In order to continuously track the mobile user,we propose This provides us a new opportunity for localization.Since the two time-efficient algorithms to accurately locate the same type of items are usually placed in a specified range,the moving user,i.e.,the Category Cardinality based Protocol location of these items can be approximately known according and the RSSI based Protocol.By reasonably adjusting the to the layout of the merchandize.For example,considering reader's power,the localization can be executed in a real- the case where Crest toothpastes are known to be placed time approach within the specified time delay. in a certain range (s,e)of a shelf.If the RFID reader II.RELATED WORK has scanned tags with category identification to the Crest toothpastes,then the reader is supposed to be close to this Many research works using RFID for indoor localization range,as the reader usually has a rather limited scanning range. have been carried out in recent years [14-18].Liu et al. Therefore,if a mobile user carries an RFID reader while he is propose a new localization algorithm(ARSS)based on RSSI ARSS figures out the distribution relationship between un- Corresponding Author:Dr.Lei Xie,Ixie@nju.edu.cn known nodes and anchor nodes[14].Babic et al.propose a
Efficient Localization based on Imprecise Anchors in RFID System Xiang Lu, Lei Xie, Yafeng Yin, Wei Wang, Baoliu Ye, Sanglu Lu State Key Laboratory for Novel Software Technology, Nanjing University, China Email: {luxiang, yyf}@dislab.nju.edu.cn, {lxie, ww, yebl, sanglu}@nju.edu.cn Abstract—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 are filled with tag-labeled items. Conventional localization schemes usually leverage precise anchor nodes to help compute the position of objects. However, it is usually difficult to find or deploy enough anchor nodes for accurate localization. In this paper, we propose solutions to locate the mobile users based on imprecise anchors in RFID systems. A large number of tags with approximate locations are used as anchor nodes to compute the user’s locations. We thus present a time-efficient localization scheme to continuously tracking the mobile users. Experimental results indicate that our solutions can accurately locate the mobile users in a real-time approach. The improved method’s accuracy is more than 30% better than the base solution. Index Terms—RFID; Tags filled environment; Localization; Reader-based; location estimation I. INTRODUCTION The proliferation of wireless and mobile devices has fostered the demand for context-aware or location-based services in pervasive applications [1−4]. For example, while a user is shopping in the super market, the relevant advertisements can be popped up in time when he is approaching a shelf with specified goods. In regard to these applications, location is viewed as one of the most significant factors. Conventional localization schemes mainly leverage precise anchor nodes to help compute the user’s location [5−8]. These anchor nodes are intentionally deployed for localization. However, it is difficult to find or deploy enough anchor nodes for accurate localization, due to the very expensive deployment cost. With the rapid proliferation of RFID-based applications [9−13], RFID tags have been deployed into pervasive spaces in increasingly large numbers, e.g., in the libraries or super markets, the shelves are always filled with tag-labeled items. This provides us a new opportunity for localization. Since the same type of items are usually placed in a specified range, the location of these items can be approximately known according to the layout of the merchandize. For example, considering the case where Crest toothpastes are known to be placed in a certain range (xs, xe) of a shelf. If the RFID reader has scanned tags with category identification to the Crest toothpastes, then the reader is supposed to be close to this range, as the reader usually has a rather limited scanning range. Therefore, if a mobile user carries an RFID reader while he is Corresponding Author: Dr. Lei Xie, lxie@nju.edu.cn walking around, e.g., the reader is deployed in the shopping cart, it is possible to locate the user according to the categories of the scanned tags and the layout of the merchandize. When multiple categories of tags are scanned, the reader’s location can be computed more accurately by sufficiently leveraging the layout information of these categories. Based on the above understanding, we propose solutions to locate the mobile user based on imprecise anchor nodes in RFID systems in this paper. Such localization solutions need to resolve two key challenges in order to provide precise and timely user location. Firstly, the anchor positions are imprecise. Items of the same category can be placed in a range rather than on a precise point on the shelf. Furthermore, the reader may miss some of the nearby RFID tags due to imperfect radio environments. Our localization scheme must handle such uncertainty to provide reliable user locations. Secondly, most RFID readers takes more time to scan nearby RFID tags when the density of RFID is increased. As our system utilizes a large number of existing RFID tags for localization, we need to find a way to return useful information in a timely manner even if the reader is surrounded by thousands of RFID tags. We thus present a time-efficient localization scheme to continuously tracking the mobile user. Experimental results indicate that our solutions can accurately locate the mobile users by a real-time approach. The main contributions of this paper are summarized as follows: • We propose an efficient localization scheme based on the large number of tags scanned by the RFID reader, it does not require any additional precise anchor nodes, thus effectively avoids the significant deployment cost. To the best of our knowledge, this is the first localization work based on imprecise anchor nodes in RFID systems. • In order to continuously track the mobile user, we propose two time-efficient algorithms to accurately locate the moving user, i.e., the Category Cardinality based Protocol and the RSSI based Protocol. By reasonably adjusting the reader’s power, the localization can be executed in a realtime approach within the specified time delay. II. RELATED WORK Many research works using RFID for indoor localization have been carried out in recent years [14−18]. Liu et al. propose a new localization algorithm(ARSS) based on RSSI , ARSS figures out the distribution relationship between unknown nodes and anchor nodes[14]. Babic et al. propose a
novel localization method for moving object using integration experiments.In our experiments,we use the Alien-9900 reader of passive RFID tags and scene analysis technique [15]. and Alien-9611 linear antenna with a directional gain of 6dB. LANDMARC [16]is a tag localization prototype in indoor The 3dB beamwidth is 65 degrees.The RFID tags used environment.By utilizing extra reference with fixed reference are Alien 9640 general-purpose tags which support the EPC tags to help location calibration,it can increase location accu- CIG2standards.We place the tags on a shelf with 5 rows,the racy without deploying large numbers of RFID readers.Zhu et distance between two rows is 60cm. al.propose a fault-tolerant RFID reader localization approach In the following experiments,we vary the tag density from to solve the problem of frequent occurred RFID faults [17].2 to 10 tags per meter,while adjusting the reader's power from Xiao et al.propose a novel environmental-adaptive indoor 15.7dBm to 30.7dBm.Unless otherwise specified,in default positioning approach using RSSI [18].The signal propagation situation we fix the reader towards the center of the shelf, model and model parameters are updated in a closed-loop scan the tags for 50 query cycles repetitively.And the distance feedback correction manner. between the antenna and the shelf is 1.5m. III.PROBLEM FORMULATION Shopping malls,warehouses and public libraries,may have ◆10ta3/m ◆5tag/m massive RFID tags deployed in the environment(There are 3tags/m many objects or books attached with tags on the shelves).Our -1.5tags/m objective is to use these existing tags to localize the mobile user equipped with an RFID reader,e.g.,the reader may be attached to a shopping cart.When the user moves with the reader in these environments,the reader can interrogate the 面司 tags within the scanning range and get their identities for localization. Fig.3.Detection Regions'radius Fig.4.Relationships among Tag size,Power and Tag density 600 00网 Fig.1.Localization process Fig.2.Tags on the shelf Fig.5.Scanning TIme Fig.6.RSSI distribution(28.7dBm) As shown in Fig.1,there are many shelves in the localization environment.The star is the target needed to be located.As TABLE I the shelves'locations are fixed,we can use one-dimension TABLES OF TRAINING DATA SETS coordinate system to describe the target's position.In the Table Name Description figure,the yo is known.By estimating the position z in the Ta Detection regions'radius in different tag density and power. aisle,we finally get the exactly location of the target. Relationships among tags size. As shown in Fig.2,the shelf is divided into several blocks T Power and Tag density. and each block contains multiple objects represented by small Te Relationship between detected tags size and scanning time. cubes.The blocks are distinguished by their colors in the ta Relationship between RSSI value and distance figure.The objects in one block belong to the same category, to the center of the detection region. which is represented in tag ID.The width of the blocks can also be different from each other.We describe a block as 1)Tag density effects:In the same scanning range,the [i,s,xi.e,li].i.s,xi,e are the start point and end point of density p of the tags is the main influencing parameter.A the block,l;represents the layer of the shelf,and the height high density p causes more tags to be identified in the range. of each shelf layer is h.The exact position of each object Meanwhile,as the tag density increases,the major detection in the block is unknown,while the location of each block is regions radius gradually decreases.Fig.3 shows the relation- known. ship of detection region,reader's power,and tag density.We can find that when the power is fixed,as the tag density IV.OBSERVATIONS FROM THE REALISTIC EXPERIMENTS increases.the width of the detection region decrease.The Because of the issues like path loss,energy absorption Fig.4 shows the relationship of the number of identified tags, and mutual interference,the RSSI distribution are always not the reader's power,and the tag density.Based on these two idealized.In order to get these information in the realistic relationships,we make two training data sets Ta and T by environment,we provide several observations from realistic experiments.Then we can compute the tag density and the
novel localization method for moving object using integration of passive RFID tags and scene analysis technique [15]. LANDMARC [16] is a tag localization prototype in indoor environment. By utilizing extra reference with fixed reference tags to help location calibration, it can increase location accuracy without deploying large numbers of RFID readers. Zhu et al. propose a fault-tolerant RFID reader localization approach to solve the problem of frequent occurred RFID faults [17]. Xiao et al. propose a novel environmental-adaptive indoor positioning approach using RSSI [18]. The signal propagation model and model parameters are updated in a closed-loop feedback correction manner. III. PROBLEM FORMULATION Shopping malls, warehouses and public libraries, may have massive RFID tags deployed in the environment(There are many objects or books attached with tags on the shelves). Our objective is to use these existing tags to localize the mobile user equipped with an RFID reader, e.g., the reader may be attached to a shopping cart. When the user moves with the reader in these environments, the reader can interrogate the tags within the scanning range and get their identities for localization. Fig. 1. Localization process Fig. 2. Tags on the shelf As shown in Fig.1, there are many shelves in the localization environment. The star is the target needed to be located. As the shelves’ locations are fixed, we can use one-dimension coordinate system to describe the target’s position. In the figure, the y0 is known. By estimating the position x in the aisle, we finally get the exactly location of the target. As shown in Fig. 2, the shelf is divided into several blocks and each block contains multiple objects represented by small cubes. The blocks are distinguished by their colors in the figure. The objects in one block belong to the same category, which is represented in tag ID. The width of the blocks can also be different from each other. We describe a block as [xi,s, xi,e, li ]. xi,s, xi,e are the start point and end point of the block, li represents the layer of the shelf, and the height of each shelf layer is h. The exact position of each object in the block is unknown, while the location of each block is known. IV. OBSERVATIONS FROM THE REALISTIC EXPERIMENTS Because of the issues like path loss, energy absorption and mutual interference, the RSSI distribution are always not idealized. In order to get these information in the realistic environment, we provide several observations from realistic experiments. In our experiments, we use the Alien-9900 reader and Alien-9611 linear antenna with a directional gain of 6dB. The 3dB beamwidth is 65 degrees. The RFID tags used are Alien 9640 general-purpose tags which support the EPC C1G2standards. We place the tags on a shelf with 5 rows, the distance between two rows is 60cm. In the following experiments, we vary the tag density from 2 to 10 tags per meter, while adjusting the reader’s power from 15.7dBm to 30.7dBm. Unless otherwise specified, in default situation we fix the reader towards the center of the shelf, scan the tags for 50 query cycles repetitively. And the distance between the antenna and the shelf is 1.5m. Fig. 3. Detection Regions’ radius Fig. 4. Relationships among Tag size, Power and Tag density 0 50 100 150 0 0.5 1 1.5 2 2.5 The number of identified tags Scanning Time (s) Fig. 5. Scanning TIme Fig. 6. RSSI distribution(28.7dBm) TABLE I TABLES OF TRAINING DATA SETS Table Name Description Ta Detection regions’ radius in different tag density and power. Tb Relationships among tags size, Power and Tag density. Tc Relationship between detected tags size and scanning time. Td Relationship between RSSI value and distance to the center of the detection region. 1) Tag density effects: In the same scanning range, the density ρ of the tags is the main influencing parameter. A high density ρ causes more tags to be identified in the range. Meanwhile, as the tag density increases, the major detection regions radius gradually decreases. Fig.3 shows the relationship of detection region, reader’s power, and tag density. We can find that when the power is fixed, as the tag density increases, the width of the detection region decrease. The Fig.4 shows the relationship of the number of identified tags, the reader’s power, and the tag density. Based on these two relationships, we make two training data sets Ta and Tb by experiments. Then we can compute the tag density and the
radius of the major region with the known reader's power by With this knowledge,several methods based on RSSI can linear interpolation method. be used to compute the real position of the reader.The basic 2)Scanning time:When the number of tags becomes large, one is like the previous method,which just replaces the tag the identification time increases.as shown in Fig.5.If we want size ni with total RSSI si in each identified category,and to localize objects in a very short time by reading the tags,then then calculate the weighted mean of the identified categories' the number of tags in the detection region should be limited. positions in x coordinate as.The estimation method 2 For example,when the number of tags equals to 120,the could be expressed as follows. reading time approximates to 1.5s,which cannot be accepted in the real time location system.Therefore,we should reduce 交=k Ti,s十Ti,e =1 the number of identified tags (e.g.90)in the detection region 2 Si to reduce the reading time (e.g.,1s),which can be achieved = by decreasing the scanning power.We get a training data set ∑15 T which shows the relationship between detected tag size and These basic schemes by using default power to read as many scanning time. tags in different categories as possible.As mentioned before, 3)RSSI distribution:In regard to the tags in the same the larger power causes the number of tags in the scanning detection region,their values of RSSI are different from each range to increase,therefore the reader needs more time to other.Fig.6 shows the RSSI value distribution for tags on the finish the scanning process. single row.We can find that the tags in the major detection Besides,in the tag size based baseline solution,the weight region have the higher RSSI values,while the tags in minor is not reliable due to the variances in tag distributions.For detection region have the lower RSSI values.In fact,the RSSI instance,maybe there is a category containing just a small value is mainly affected by the distance and the angle between number of tags,thus,even all the tags in the category are the tag's surface and the antenna's radiation direction towards identified,it always has a small weight in the computing pro- the reader.The shorter distance to the center of the detection cess.In the RSSI based baseline solution,when the categories region,the higher RSSI value we will get.Here,we get a in the major region contain just a small number of tags,but training data set Ta which shows the relationship between the categories in the minor region contain a lot of tags.The RSSI and distance to the center of the detection region. imbalanced numbers of tags will skew the weight and cause large error in the estimation position. V.BASELINE SOLUTIONS Therefore,these limitations lead to the low efficiency of the A.Category Cardinality based Protocol (CCP) baseline solutions In this baseline solution,we set the reader's power to the VI.LOCALIZATION BASED ON IMPRECISE ANCHORS default value(30.7dbm).Then the reader scans the tags to get the categories of identified tags.We average the locations of A.Compute the optimal value of power the detected categories to get the estimated position.We use Our algorithm tries to reasonably adjust the power of the the number of identified tags to calculate the weight.Because reader,while keeping it at a reasonable level to make sure the start point i.s and the end point zi.e of the category's the delay satisfy the limits t.As shown in Algorithm 1,we range are known,the estimation method could be expressed use four steps to compute the optimal power.First,we use as follows. a pre-scan process to get the identified tag size.By setting the pre-scan power to an empirical value po,we can get an Wi' i,s十Ii,e identified tag size no.Second,based on the training data set i=1 2 T,we can compute the tag density p by an interpolation Wi=- einm method.(For example,when the power is 26.7dBm and the number of identified tags is 50,the intersection is between 5 Here,k is the number of categories for identified tags.wi tags/m and 10 tags/m,and it is closer to 10tags/m,thus we is the weight factor for category ci,which is ratio of the set it 8 tags/m.)Third,suppose that we take time to in the number of identified tags in category ci to the number of all pre-scan,then we have the time of t-to left.As mentioned the identified tags in the scanning area.In this method,we use in Section IV,there is a relationship between the identified tag the middle value of the category's rangeto represent size and scanning time as shown in Fig.5.Therefore,we can the category's position.Finally,iis the computed position of get an target tag size limit of n'with respect to the remaining the target. time of t-to by an interpolation method based on the training data set T..Finally,from the relationship shown in Fig.4,by B.RSSI based Protocol (RP) using the p and n',we can compute the optimal power p.The In the previous baseline solution,we just use the number algorithm is shown in Algorithm 3. of identified tags in each category.However,the RSSI is a very important factor to measure the distribution of tags.As B.Category Matching based Protocol(CMP) mentioned in Section IV,the higher the RSSI,the closer the 1)Motivation:During the scanning process,we can get the tag to the center of the detection region. number of tags in each identified category.We denote them
radius of the major region with the known reader’s power by linear interpolation method. 2) Scanning time: When the number of tags becomes large, the identification time increases, as shown in Fig.5. If we want to localize objects in a very short time by reading the tags, then the number of tags in the detection region should be limited. For example, when the number of tags equals to 120, the reading time approximates to 1.5s, which cannot be accepted in the real time location system. Therefore, we should reduce the number of identified tags (e.g. 90) in the detection region to reduce the reading time (e.g., 1s), which can be achieved by decreasing the scanning power. We get a training data set Tc which shows the relationship between detected tag size and scanning time. 3) RSSI distribution: In regard to the tags in the same detection region, their values of RSSI are different from each other. Fig.6 shows the RSSI value distribution for tags on the single row. We can find that the tags in the major detection region have the higher RSSI values, while the tags in minor detection region have the lower RSSI values. In fact, the RSSI value is mainly affected by the distance and the angle between the tag’s surface and the antenna’s radiation direction towards the reader. The shorter distance to the center of the detection region, the higher RSSI value we will get. Here, we get a training data set Td which shows the relationship between RSSI and distance to the center of the detection region. V. BASELINE SOLUTIONS A. Category Cardinality based Protocol (CCP) In this baseline solution, we set the reader’s power to the default value(30.7dbm). Then the reader scans the tags to get the categories of identified tags. We average the locations of the detected categories to get the estimated position. We use the number of identified tags to calculate the weight. Because the start point xi,s and the end point xi,e of the category’s range are known, the estimation method could be expressed as follows. xˆ = Xk i=1 wi · xi,s + xi,e 2 , wi = ni Pk i=1 ni Here, k is the number of categories for identified tags. wi is the weight factor for category ci , which is ratio of the number of identified tags in category ci to the number of all the identified tags in the scanning area. In this method, we use the middle value of the category’s range xi,s+xi,e 2 to represent the category’s position. Finally, xˆ is the computed position of the target. B. RSSI based Protocol (RP) In the previous baseline solution, we just use the number of identified tags in each category. However, the RSSI is a very important factor to measure the distribution of tags. As mentioned in Section IV, the higher the RSSI, the closer the tag to the center of the detection region. With this knowledge, several methods based on RSSI can be used to compute the real position of the reader. The basic one is like the previous method, which just replaces the tag size ni with total RSSI si in each identified category, and then calculate the weighted mean of the identified categories’ positions in x coordinate as xi,s+xi,e 2 . The estimation method could be expressed as follows. xˆ = Xk i=1 wi · xi,s + xi,e 2 , wi = si Pk i=1 si These basic schemes by using default power to read as many tags in different categories as possible. As mentioned before, the larger power causes the number of tags in the scanning range to increase, therefore the reader needs more time to finish the scanning process. Besides, in the tag size based baseline solution, the weight is not reliable due to the variances in tag distributions. For instance, maybe there is a category containing just a small number of tags, thus, even all the tags in the category are identified, it always has a small weight in the computing process. In the RSSI based baseline solution, when the categories in the major region contain just a small number of tags, but the categories in the minor region contain a lot of tags. The imbalanced numbers of tags will skew the weight and cause large error in the estimation position. Therefore, these limitations lead to the low efficiency of the baseline solutions. VI. LOCALIZATION BASED ON IMPRECISE ANCHORS A. Compute the optimal value of power Our algorithm tries to reasonably adjust the power of the reader, while keeping it at a reasonable level to make sure the delay satisfy the limits tl . As shown in Algorithm 1, we use four steps to compute the optimal power. First, we use a pre-scan process to get the identified tag size. By setting the pre-scan power to an empirical value p0, we can get an identified tag size n0. Second, based on the training data set Tb , we can compute the tag density ρ by an interpolation method.(For example, when the power is 26.7dBm and the number of identified tags is 50, the intersection is between 5 tags/m and 10 tags/m, and it is closer to 10tags/m, thus we set it 8 tags/m.) Third, suppose that we take time t0 in the pre-scan, then we have the time of tl − t0 left. As mentioned in Section IV, there is a relationship between the identified tag size and scanning time as shown in Fig.5. Therefore, we can get an target tag size limit of n 0 with respect to the remaining time of tl−t0 by an interpolation method based on the training data set Tc. Finally, from the relationship shown in Fig.4, by using the ρ and n 0 , we can compute the optimal power pˆ. The algorithm is shown in Algorithm 3. B. Category Matching based Protocol (CMP) 1) Motivation: During the scanning process, we can get the number of tags in each identified category. We denote them
Algorithm 1 Compute the optimal value of power Algorithm 2 Category Matching based protocol 1:INPUT::the limit of the delay; 1:INPUT:Vo {no.1,no.2,...,no.s}:the vectors for the Po:the power of the pre-scan; numbers of tags in each identified category; 2:PROCEDURE Ci=(ril,ir,li},i{1,2...N):the position of tag 3:Set reader's power to po,get the identified tag size no. category Ci: 4:From the relationship between identified tags size no and 2:PROCEDURE power po in different densities which is showed in training 3:Call Alg.I to get the optimal power po,tag density p. data set T,compute the tag density p by intersection. 4:Based on the Ta,get the minor region radius r. 5:From the relationship between identified tags size no and 5:Get the left point x and the right point of the covered scanning time (t-to)which is showed in training data range by the identified categories. set T.get the acceptable tag size n'by intersection. 6:x=+T;i←1： 6:Use the relationship in the training data set To again,we 7:while x0) ∑=11/1-sim(%,)+e) 0 3 4 14:OUTPUT:The computed position 2. Fig.7.Matching the identified tags'number as a vector.We treat the positions covered by the identified the similarity between Vo and Vi.we can get k-nearest vectors' categories as the potential positions.From the left to the positions 1,..,k.Then,using an inverse distance weighted right of these potential positions,by making each potential average with the k-nearest multivariate neighbors,we can get position as the center of a circle and the major detecting the target's position As shown in Algorithm 2. region's radius as the circle's radius,we can calculate a series 3)Analysis:This method is the improvement of the Tag of tag size vectors for the identified categories as shown in size weighted average based method.It fully uses the known Fig.7.By matching each calculated vector with other identified conditions and the results of the scanning to compute the tag vectors,we can get k-nearest vectors which have the highest density and the read rate of each category.By using vector similarities,as shown in Algorithm 2.Based on the k-nearest matching method to get the k-nearest neighbours,the accuracy neighbor algorithm,we can compute the final position. and stability of the method is guaranteed.However,there are 2)Algorithm:As shown in Fig.7,the circle filled with light some limitations too.It needs to get parameters of the scene- color represents the major detecting region.The r is the major setting,such as the distributions of detection regions.It also detecting region's radius.By the scanning results,we can get needs to compute the tag density at first,which will cause the major detecting region of each categories Ci and the tag some errors. size ni in each category.We denote these numbers of tags in each category Ci as a vector Vo(no.1,no.2,...,no.s).We C.Distance Voting based Protocol(DVP) calculate the detection region with the known tag density and 1)Motivation:To solve the limitation of the RSSI weighted reader's power.Based on training data set Ta.we can get average based solution,we get the relationship between RSSI thethe minor region radius r.Dotted line circles represent value and distance to the center of the detection region in detection ranges of other candidate positions.Through the different tag density.Then we can compute the distance linear interpolation method based on training data set T.between each tag and the center of the detection region. we can get the estimated tag density p.We calculate the Take the position of the category's midpoint as the each vectors through the geometric method.As shown in Fig.7,the category's position,then we can get a series of potential dotted line circles cover a series of categories,the location position intervals.The intersection of these intervals is the information and the estimated tag densities are known,then estimation position we want. we can get the number of tags in each category.We denote 2)Algorithm:Through algorithm 1,we can get the optimal them as vector Vi(ni.1,ni.2,...,n.s).Finally,by calculating value of the power po.Meanwhile,we can get tag density p.it
Algorithm 1 Compute the optimal value of power 1: INPUT: tl : the limit of the delay; p0: the power of the pre-scan; 2: PROCEDURE 3: Set reader’s power to p0, get the identified tag size n0. 4: From the relationship between identified tags size n0 and power p0 in different densities which is showed in training data set Tb, compute the tag density ρ by intersection. 5: From the relationship between identified tags size n0 and scanning time (tl − t0) which is showed in training data set Tc, get the acceptable tag size n 0 by intersection. 6: Use the relationship in the training data set Tb again, we can compute the pˆ with the tags size n 0 and tag density ρ by intersection. 7: OUTPUT: the optimal value of power pˆ Fig. 7. Matching the identified tags’ number as a vector. We treat the positions covered by the identified categories as the potential positions. From the left to the right of these potential positions, by making each potential position as the center of a circle and the major detecting region’s radius as the circle’s radius, we can calculate a series of tag size vectors for the identified categories as shown in Fig.7. By matching each calculated vector with other identified vectors, we can get k-nearest vectors which have the highest similarities, as shown in Algorithm 2. Based on the k-nearest neighbor algorithm, we can compute the final position. 2) Algorithm: As shown in Fig.7, the circle filled with light color represents the major detecting region.The r is the major detecting region’s radius. By the scanning results, we can get the major detecting region of each categories Ci and the tag size ni in each category. We denote these numbers of tags in each category Ci as a vector V0(n0,1, n0,2, ..., n0,s). We calculate the detection region with the known tag density and reader’s power. Based on training data set Ta, we can get the the minor region radius r. Dotted line circles represent detection ranges of other candidate positions. Through the linear interpolation method based on training data set Tb, we can get the estimated tag density ρ. We calculate the vectors through the geometric method. As shown in Fig.7, the dotted line circles cover a series of categories, the location information and the estimated tag densities are known, then we can get the number of tags in each category. We denote them as vector Vi(ni,1, ni,2, ..., ni,s). Finally, by calculating Algorithm 2 Category Matching based protocol 1: INPUT: V0 = {n0,1, n0,2, ..., n0,s}: the vectors for the numbers of tags in each identified category; Ci = {xi,l, xi,r, li}, i ∈ {1, 2...N}: the position of tag category Ci ; 2: PROCEDURE 3: Call Alg.1 to get the optimal power p0, tag density ρ. 4: Based on the Ta, get the minor region radius r. 5: Get the left point xl and the right point xr of the covered range by the identified categories. 6: x = xl + r;i ← 1; 7: while x 0) 14: OUTPUT: The computed position xˆ. the similarity between V0 and Vi , we can get k-nearest vectors’ positions x1, ..., xk. Then, using an inverse distance weighted average with the k-nearest multivariate neighbors, we can get the target’s position xˆ. As shown in Algorithm 2. 3) Analysis: This method is the improvement of the Tag size weighted average based method. It fully uses the known conditions and the results of the scanning to compute the tag density and the read rate of each category. By using vector matching method to get the k-nearest neighbours, the accuracy and stability of the method is guaranteed. However, there are some limitations too. It needs to get parameters of the scenesetting, such as the distributions of detection regions. It also needs to compute the tag density at first, which will cause some errors. C. Distance Voting based Protocol (DVP) 1) Motivation: To solve the limitation of the RSSI weighted average based solution, we get the relationship between RSSI value and distance to the center of the detection region in different tag density. Then we can compute the distance between each tag and the center of the detection region. Take the position of the category’s midpoint as the each category’s position, then we can get a series of potential position intervals. The intersection of these intervals is the estimation position we want. 2) Algorithm: Through algorithm 1, we can get the optimal value of the power p0. Meanwhile, we can get tag density ρ, it
is an intermediate result in algorithm 1.By setting the power to po and scan the tags,we get the identified categories Ci and the RSSI value si.j of each tag in the category Ci.Through the training data set Ta.we can get the distance di.j of the tag to the center of the detection region.Take the position of the category's midpoint as the tag's position,then the estimation position i calculated by the category Ci is .The category contains the minimal di is the most possible category which contains the real position Fig.8.Experiments setup xo,we can ensure the relative positions of the categories.Then the estimation position is power used by the baseline protocols.Usually,the larger power means the larger detected tag size,which leads to more Algorithm 3 Distance Voting based protocol execution time.In Fig.9,the tag density is 10tags/m and the 1:Call Alg.I to compute the tag density p and the optimal average width of categories is 0.5m,the execution time of value of power po. CMP is only 62%of that of CCP,while the execution time of 2:Get the identified categories Ci=fi.s,i,e,li}and the DVP is only of 57%of that of RP.In regard to the proposed RSSI value si.i of each tag in the category Ci. protocols,DVP has larger execution time than CMP,because 3:Through the training data T,get the distance di.j of the DVP needs to get the tag IDs and the RSSI value of each tags tag to the center of the detection region. as well. 4:Find the category Co which has the minimal di.j. 5:fori∈{1,2k}j∈{1,2.ni}do C.Accuracy of Localization 6: ir>othen=-空endif From Fig.10,we can find that all our proposed protocols have higher accuracies than the baseline protocol.Besides, 7: io then endif 2 the proposed protocols are more reliable than the baseline 8:end for 9:compute the交as follows::金=∑t,色 protocols with lower localization error.This is because our proposed protocol(CMP,DVP)respectively use the category 10:OUTPUT:the estimation position. matching method and the distance voting method to select the k nearest categories to locate the target.They reduce the error 3)Analysis:This method improves the reliablity of the caused by the variances of tag distributions.When the tag baseline RSSI weighted average based method.By getting density is 10tags/m and the average category width is 0.5m, the corresponding distance value of the RSSI,we make the the localization error of CMP is only 75%of that of CCP, algorithm more robust. while the localization error of DVP is only 73%of that of RP. VII.PERFORMANCE EVALUATION D.Varying the tag density This section describes the experimental settings and results. In Fig.11 and Fig.12,we respectively show the execution The experimental data in different conditions have been used time and the localization error under different tag densities. to analyse the performances of the above algorithms.We use In Fig.11,we can find that as the tag density increases,each the overall execution time and the accuracy of localisation as protocol's execution time increases.This is because the larger the performance metrics. tag density p leads to the larger number of tags identified by the reader,which increases more execution time.However, A.Experiments Setup when the tag density is large enough(eg.8tags/m,10tags/m), As shown in Fig.8,we deploy the tags on the shelf.The the execution time of CMP and DVP almost remain the same, width and the height of the deployment area equal to 5m and because our proposed protocols use the optimal power to 2m,respectively.The tags are deployed in 5 rows and the tag scan the tags.When the tag density increases,the effective category information is randomly generated.The tags used in interrogation region decrease,while the number of identified the experiment are ALN-9662(HiggsTM3 )and the reader is tags almost remains the same.Therefore,the execution time ALR-9900+,which runs on global EPC Gen 2 platform.The of CMP is only 58%of that of CCP while the execution antenna is Alien ALR Antenna.The antenna faces to the shelf,time of DVP is only 60%of that RP.Based on Fig.12.as the and the distance between the antenna and the shelf is 1m.In tag density increases,the localization error decreases.This is default situation we fix the reader towards the center of the because the variance of the obtained tag information(tag size shelf,and scan the tags for 50 query cycles repetitively. in each category.RSSI of the tags)decreases,when the tag B.Comparision of execution time density decreases. Based on Fig.9,we can conclude that our proposed proto- cols(CMP,DVP)have better performances than the baseline E.Varying the distribution of categories protocols(CCP,RP).It is because that our proposed protocols Fig.13 and Fig.14 show the execution time and the local- scan the tags with the optimal power instead of the default ization error under different category's widths.As shown in
is an intermediate result in algorithm 1. By setting the power to p0 and scan the tags, we get the identified categories Ci and the RSSI value si,j of each tag in the category Ci . Through the training data set Td, we can get the distance di,j of the tag to the center of the detection region. Take the position xi,s+xi,e 2 of the category’s midpoint as the tag’s position, then the estimation position xˆi calculated by the category Ci is xi,s+xi,e 2 ± Pni j=1 di,j ni . The category contains the minimal di,j is the most possible category which contains the real position x0, we can ensure the relative positions of the categories. Then the estimation position xˆ is Pk i=1 xˆi k . Algorithm 3 Distance Voting based protocol 1: Call Alg.1 to compute the tag density ρ and the optimal value of power p0. 2: Get the identified categories Ci = {xi,s, xi,e, li} and the RSSI value si,j of each tag in the category Ci . 3: Through the training data Td, get the distance di,j of the tag to the center of the detection region. 4: Find the category C0 which has the minimal di,j . 5: for i ∈ {1, 2...k}, j ∈ {1, 2..ni} do 6: if xi,s > x0,e then xˆi = xi,s+xi,e 2 − Pni j=1 di,j ni endif 7: if xi,e < x0,s then xˆi = xi,s+xi,e 2 + Pni j=1 di,j ni endif 8: end for 9: compute the xˆ as follows: xˆ = Pk i=1 xˆi k . 10: OUTPUT: the estimation position xˆ. 3) Analysis: This method improves the reliablity of the baseline RSSI weighted average based method. By getting the corresponding distance value of the RSSI, we make the algorithm more robust. VII. PERFORMANCE EVALUATION This section describes the experimental settings and results. The experimental data in different conditions have been used to analyse the performances of the above algorithms. We use the overall execution time and the accuracy of localisation as the performance metrics. A. Experiments Setup As shown in Fig.8, we deploy the tags on the shelf. The width and the height of the deployment area equal to 5m and 2m, respectively. The tags are deployed in 5 rows and the tag category information is randomly generated. The tags used in the experiment are ALN-9662(HiggsTM3 ) and the reader is ALR-9900+, which runs on global EPC Gen 2 platform. The antenna is Alien ALR Antenna. The antenna faces to the shelf, and the distance between the antenna and the shelf is 1m. In default situation we fix the reader towards the center of the shelf, and scan the tags for 50 query cycles repetitively. B. Comparision of execution time Based on Fig. 9, we can conclude that our proposed protocols (CMP, DVP) have better performances than the baseline protocols (CCP, RP). It is because that our proposed protocols scan the tags with the optimal power instead of the default Fig. 8. Experiments setup power used by the baseline protocols. Usually, the larger power means the larger detected tag size, which leads to more execution time. In Fig.9, the tag density is 10tags/m and the average width of categories is 0.5m, the execution time of CMP is only 62% of that of CCP, while the execution time of DVP is only of 57% of that of RP. In regard to the proposed protocols, DVP has larger execution time than CMP, because DVP needs to get the tag IDs and the RSSI value of each tags as well. C. Accuracy of Localization From Fig.10, we can find that all our proposed protocols have higher accuracies than the baseline protocol. Besides, the proposed protocols are more reliable than the baseline protocols with lower localization error. This is because our proposed protocol (CMP, DVP) respectively use the category matching method and the distance voting method to select the k nearest categories to locate the target. They reduce the error caused by the variances of tag distributions. When the tag density is 10tags/m and the average category width is 0.5m, the localization error of CMP is only 75% of that of CCP, while the localization error of DVP is only 73% of that of RP. D. Varying the tag density In Fig.11 and Fig.12, we respectively show the execution time and the localization error under different tag densities. In Fig.11, we can find that as the tag density increases, each protocol’s execution time increases. This is because the larger tag density ρ leads to the larger number of tags identified by the reader, which increases more execution time. However, when the tag density is large enough (eg. 8tags/m, 10tags/m), the execution time of CMP and DVP almost remain the same, because our proposed protocols use the optimal power to scan the tags. When the tag density increases, the effective interrogation region decrease, while the number of identified tags almost remains the same. Therefore, the execution time of CMP is only 58% of that of CCP, while the execution time of DVP is only 60% of that RP. Based on Fig.12, as the tag density increases, the localization error decreases. This is because the variance of the obtained tag information (tag size in each category, RSSI of the tags) decreases, when the tag density decreases. E. Varying the distribution of categories Fig.13 and Fig.14 show the execution time and the localization error under different category’s widths. As shown in
Distance Vosna 8 tags/ Fig.9.Execution time Fig.10.Accuracy of Localization Fig.11.Execution time under different tag density Fig.12.Localization error Fig.13.Execution time Fig.14.Localization error under different tag density under different categorys widths under different categorys widths Fig.13,the category's width has little effect on the execution [3]J.Biswas and M.Veloso,"Wifi localization and navigation for au- time.Because the number of identified tags almost stay the tonomous indoor mobile robots,"in IEEE International Conference on Robotics and Automation (ICRA).2010. same,as the tag density does not change in this situation. [4]D.Giustiniano and S.Mangold,"CAESAR:carrier sense-based ranging However,as the category's width increases,the localization in off-the-shelf 802.11 wireless LAN,"in Proceedings of the Seventh error increases.When the category's width becomes smaller, COnference on emerging Networking EXperiments and Technologies ACM).2011. the same area will cover more categories.More categories will [5]X.Jiang.C.-J.M.Liang,K.Chen,B.Zhang,J.Hsu,and J.Liu. improve the performance of the protocols,especially for CMP "Design and evaluation of a wireless magnetic-based proximity detection and DVP.CMP needs more categories for matching to select platform for indoor applications."in Proc.of IPSN/SPOTS,2012. the k nearest categories,while DVP needs more categories for [6]K.Wu.J.Xiao.Y.Yi,M.Gao,and L.Ni,"FILA:Fine-grained indoor localization,"in Proc.of INFOCOM,2012. voting to select the k nearst categories. [7]X.Jiang.C.J.M.Liang.F.Zhao,K.Chen,J.Hsu,B.Zhang,and J. Liu,"Demo:Creating interactive virtual zones in physical space with VIII.CONCLUSIONS magnetic-induction,"in Proc.of SenSys,2011. [8]L.Yang,J.Cao,W.Zhu,and S.Tang,"A hybrid method for achieving In this paper,we propose an efficient localization scheme high accuracy and efficiency in object tracking using passive RFID,"in based on imprecise anchor nodes in RFID systems.We pre- Pervasive Computing and Communications (PerCom),2006. [9]G.Ferrer,S.Heath and N.Dew,"An RFID application in large job shop sented some observations from the realistic experiments and remanufacturing operations."in International Journal of Production described the relationships among the read rate,detection Economics,2011. region,identified tags size,power,RSSI,delay,etc.This paper (10]W.Noonan,"System and method of updating planogram information using RFID tags and personal shopping device,"in U.S.Patent,2009. presented four localization methods from different perspec- [11]S.Inoue,Y.Nohara,T.Masaki,and K.Sakuragawa,"Location recog- tives.To show the effectiveness of the proposed methods, nition in rd bookshelves,"in IEICE Transactions,2011. we have evaluated the estimated position error by some [12]A.Sample,C.Macomber,L.-T.Jiang.and J.R.Smith."Optical localization of passive uhf rd tags with integrated leds,"in Proc.of experiments. IEEE RFID,2012. [13]M.Youssef,M.Mah,and A.Agrawala "Challenges:device-free passive ACKNOWLEDGMENTS localization for wireless environments,"in Proc.of ACM MobiCom, 2007. This work is supported in part by National Natural Science [14]J.Liu and C.Han."A RSSI-Based Localization Algorithm in Smart Foundation of China under Grant No.61100196,61073028, Space,"in Intelligent Decision Technologies,2011. [15]Z.Babic,M.Ljubojevic,and V.Risojevic,"Indoor RFID localization 61321491,91218302;JiangSu Natural Science Foundation improved by motion segmentation,"inin Proc.of /SPA.2011. under Grant No.BK2011559 [16]L.M.Ni.Y.Liu,Y.C.Lau,and A.P.Patil,"LANDMARC:indoor location sensing using active RFID,"in Wireless networks.2004. REFERENCES [17]W.Zhu,J.Cao,Y.Xu.L.Yang.and J.Kong."Fault-tolerant RFID reader localization based on passive RFID tags,"in Proc.of INFOCOM,2012. [18]X.Xiao,X.Jing,S.You,and J.Zeng,"An environmental-adaptive RSSI [1]Y.Liu,Z.Yang.X.Wang.and L.Jian,"Location,localization,and localizability,"in Journal of Computer Science and Technology,2010. based indoor positioning approach using RFID."in in Proc.of AlAl. 2010. [2]H.J.Lee and M.C.Lee,"Localization of mobile robot based on radio frequency identication devices"in Intemational Joint Conference SICE- ICASE.2006
Category Cardinality Categories Matching RSSI weighted Distance Voting 0 500 1000 1500 2000 2500 3000 Different Methods Execution time (ms) Fig. 9. Execution time 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Real Position X [m] (ρ=10tags/m) Localization error [m] Category Cardinality Categories Matching RSSI weighted Distance Voting Fig. 10. Accuracy of Localization 2 tags/m 4 tags/m 6 tags/m 8 tags/m 10 tags/m 0 500 1000 1500 2000 2500 3000 Tag density Execution time (ms) Category Cardinality Categories Matching RSSI weighted Distance Voting Fig. 11. Execution time under different tag density 2 tags/m 4 tags/m 6 tags/m 8 tags/m 10 tags/m 0 0.1 0.2 0.3 0.4 0.5 Tag density Localization error [m] Category Cardinality Categories Matching RSSI weighted Distance Voting Fig. 12. Localization error under different tag density 0.5m 1m 1.5m 2m 2.5m 0 500 1000 1500 2000 2500 3000 Average width of categories Execution time (ms) Category Cardinality Categories Matching RSSI weighted Distance Voting Fig. 13. Execution time under different categorys widths 0.5m 1m 1.5m 2m 2.5m 0 0.1 0.2 0.3 0.4 0.5 Average width of categories Localization error [m] Category Cardinality Categories Matching RSSI weighted Distance Voting Fig. 14. Localization error under different categorys widths Fig.13, the category’s width has little effect on the execution time. Because the number of identified tags almost stay the same, as the tag density does not change in this situation. However, as the category’s width increases, the localization error increases. When the category’s width becomes smaller, the same area will cover more categories. More categories will improve the performance of the protocols, especially for CMP and DVP. CMP needs more categories for matching to select the k nearest categories, while DVP needs more categories for voting to select the k nearst categories. VIII. CONCLUSIONS In this paper, we propose an efficient localization scheme based on imprecise anchor nodes in RFID systems. We presented some observations from the realistic experiments and described the relationships among the read rate, detection region, identified tags size, power, RSSI, delay, etc. This paper presented four localization methods from different perspectives. To show the effectiveness of the proposed methods, we have evaluated the estimated position error by some experiments. 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] Y. Liu, Z. Yang, X. Wang, and L. Jian, “Location, localization, and localizability,” in Journal of Computer Science and Technology, 2010. [2] H. J. Lee and M. C. Lee, “Localization of mobile robot based on radio frequency identication devices,” in International Joint Conference SICEICASE, 2006. [3] J. Biswas and M. Veloso, “Wifi localization and navigation for autonomous indoor mobile robots,” in IEEE International Conference on Robotics and Automation (ICRA), 2010. [4] D. Giustiniano and S. Mangold, “CAESAR: carrier sense-based ranging in off-the-shelf 802.11 wireless LAN,” in Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies (ACM), 2011. [5] X. Jiang, C.-J. M. Liang, K. Chen, B. Zhang, J. Hsu, and J. Liu, “Design and evaluation of a wireless magnetic-based proximity detection platform for indoor applications,” in Proc. of IPSN/SPOTS, 2012. [6] K. Wu, J. Xiao, Y. Yi, M. Gao, and L. Ni, “FILA: Fine-grained indoor localization,” in Proc. of INFOCOM, 2012. [7] X. Jiang, C.-J. M. Liang, F. Zhao, K. Chen, J. Hsu, B. Zhang, and J. Liu, “Demo: Creating interactive virtual zones in physical space with magnetic-induction,” in Proc. of SenSys, 2011. [8] 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 Pervasive Computing and Communications (PerCom), 2006. [9] G. Ferrer, S.Heath and N. Dew, “An RFID application in large job shop remanufacturing operations,” in International Journal of Production Economics, 2011. [10] W. Noonan, “System and method of updating planogram information using RFID tags and personal shopping device,” in U.S. Patent , 2009. [11] S. Inoue, Y. Nohara, T. Masaki, and K. Sakuragawa, “Location recognition in rd bookshelves,” in IEICE Transactions, 2011. [12] A. Sample, C. Macomber, L.-T. Jiang, and J. R. Smith. “Optical localization of passive uhf rd tags with integrated leds,” in Proc. of IEEE RFID, 2012. [13] M. Youssef, M. Mah, and A. Agrawala “Challenges: device-free passive localization for wireless environments,” in Proc. of ACM MobiCom, 2007. [14] J. Liu and C. Han. “A RSSI-Based Localization Algorithm in Smart Space,” in Intelligent Decision Technologies, 2011. [15] Z. Babic, M. Ljubojevic, and V. Risojevic, “Indoor RFID localization improved by motion segmentation,” in in Proc. of ISPA, 2011. [16] L. M. Ni, Y. Liu, Y. C. Lau, and A. P. Patil, “LANDMARC: indoor location sensing using active RFID,” in Wireless networks, 2004. [17] W. Zhu, J. Cao, Y. Xu, L. Yang, and J. Kong, “Fault-tolerant RFID reader localization based on passive RFID tags,” in Proc. of INFOCOM, 2012. [18] X. Xiao, X. Jing, S. You, and J. Zeng, “An environmental-adaptive RSSI based indoor positioning approach using RFID,” in in Proc. of AIAI, 2010