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 funda￾mental function in many pervasive applications. Hence, it is imperative to provide an accurate and time-efficient localiza￾tion 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 local￾ization 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 param￾eters 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