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 aEfficient 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 appli￾cations, 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 fos￾tered 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 impre￾cise. 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 real￾time 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 un￾known nodes and anchor nodes[14]. Babic et al. propose a