Focus and Shoot:Efficient Identification Over RFID Tags in the Specified Area Yafeng Yin!,Lei Xiel(),Jie Wu2,Athanasios V.Vasilakos3,and Sanglu Lul 1 State Key Laboratory for Novel Software Technology, Nanjing University,Nanjing,China yyfOdislab.nju.edu.cn,{lxie,sanglu}@nju.edu.cn 2 Department of Computer and Information Sciences, Temple University,Philadelphia,USA jiewu@temple.edu 3 University of Western Macedonia,Kozani,Greece vasilakoOath.forthnet.gr Abstract.In RFID systems,the reader usually identifies all the RFID tags in the interrogation region with the maximum power.However,some applications may only need to identify the tags in a specified area,which is usually smaller than the reader's default interrogation region.In this paper,we respectively present two solutions to identify the tags in the specified area.The principle of the solutions can be compared to the picture-taking process of a camera.It first focuses on the specified area and then shoots the tags.The design of the two solutions is based on the extensive empirical study on RFID tags.Realistic experiment results show that our solutions can reduce the execution time by 46%compared to the baseline solution. Keywords:RFID·Tag identification·Experimental study·Algorithm design 1 Introduction RFID systems have been widely used in various applications,such as inventory control,sampling inspection,and supply chain management.Conventionally,an RFID system consists of one or multiple readers,and a larger number of tags. Each tag is attached to a physical item and has a unique ID describing the item. The reader recognizes the object by identifying its attached tag. In recent years,many existing research works have concentrated on RFID tag identification,aiming to identify a large number of tags efficiently [1-4. Instead of identifying all the tags,detecting the missing tags [5,6 and searching a particular subset of tags [7]only concern the part of tags.Rather than tag identification,cardinality estimation protocols count the number of tags [8-10. However,all the literature do not research the problem of tag identification in a specified area,which is rather important in many applications.Taking the C Institute for Computer Sciences,Social Informatics and Telecommunications Engineering 2014 I.Stojmenovic et al.(Eds.):MOBIQUITOUS 2013,LNICST 131,pp.344-357,2014. D0L:10.1007/978-3-319-11569-627
Focus and Shoot: Efficient Identification Over RFID Tags in the Specified Area Yafeng Yin1, Lei Xie1(B) , Jie Wu2, Athanasios V. Vasilakos3, and Sanglu Lu1 1 State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China yyf@dislab.nju.edu.cn, {lxie,sanglu}@nju.edu.cn 2 Department of Computer and Information Sciences, Temple University, Philadelphia, USA jiewu@temple.edu 3 University of Western Macedonia, Kozani, Greece vasilako@ath.forthnet.gr Abstract. In RFID systems, the reader usually identifies all the RFID tags in the interrogation region with the maximum power. However, some applications may only need to identify the tags in a specified area, which is usually smaller than the reader’s default interrogation region. In this paper, we respectively present two solutions to identify the tags in the specified area. The principle of the solutions can be compared to the picture-taking process of a camera. It first focuses on the specified area and then shoots the tags. The design of the two solutions is based on the extensive empirical study on RFID tags. Realistic experiment results show that our solutions can reduce the execution time by 46 % compared to the baseline solution. Keywords: RFID · Tag identification · Experimental study · Algorithm design 1 Introduction RFID systems have been widely used in various applications, such as inventory control, sampling inspection, and supply chain management. Conventionally, an RFID system consists of one or multiple readers, and a larger number of tags. Each tag is attached to a physical item and has a unique ID describing the item. The reader recognizes the object by identifying its attached tag. In recent years, many existing research works have concentrated on RFID tag identification, aiming to identify a large number of tags efficiently [1–4]. Instead of identifying all the tags, detecting the missing tags [5,6] and searching a particular subset of tags [7] only concern the part of tags. Rather than tag identification, cardinality estimation protocols count the number of tags [8–10]. However, all the literature do not research the problem of tag identification in a specified area, which is rather important in many applications. Taking the c Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 2014 I. Stojmenovic et al. (Eds.): MOBIQUITOUS 2013, LNICST 131, pp. 344–357, 2014. DOI: 10.1007/978-3-319-11569-6 27
Focus and Shoot:Efficient Identification Over RFID Tags 345 inventory for example,we may only need to identify the tags in some specified boxes while ignoring the others.Sometimes,it is difficult to move the objects out for tag identification,especially for the objects obstructed by obstacles. A traditional solution is to identify the tags with the maximum power.It may identify the tags out of the area,which is rather time-consuming.Due to the large number of tags,the time-efficiency is very important.Therefore,it is essential to identify the tags in the specified area efficiently without moving the tags. Fortunately,we note that tag identification in the specified area can be com- pared to the picture-taking process in a camera.The camera needs to focus on the object before shooting,aiming to lock the target object while ignoring the others.In this paper,we propose the photography based identification method, which works in a similar way.It first focuses on the specified area by adjusting the antenna's angle and the reader's power,and then identifies the tags in the area. However,efficiently identifying the tags in the realistic environments is difficult. The reading performance in the realistic experiments is still unknown,especially for a large number of tags.There are a few research works concentrating on this problem and they mainly work in a situation close to free space [11-13.Hence, we conduct a series of measurements over RFID tags in realistic settings.Based on the extensive experimental study,we respectively propose two solutions,aim- ing to identify the tags in the specified area efficiently.The solutions work in the realistic environments and conform to the EPC-C1G2 standards. We make the following contributions in this paper.(1)We conducted exten- sive experiments on the commodity RFID system in the realistic environments and investigated the factors affecting the reading performance.(2)To the best of our knowledge,this is the first work investigating the efficient tag identification in the specified area,which is essential for many applications.We propose the photography based identification method,which works in a similar way as in a camera.Besides,we respectively propose two solutions to solve the problem, which can reduce the execution time by 46%compared to the baseline solution. (3)Our solutions work in the realistic environments with the commercial RFID system,which conforms to the EPC-C1G2 standards. 2 Problem Formulation 2.1 System Model Each object is attached with an RFID tag,which has a unique ID.In this paper,we use the terms 'object','tag'interchangeably.The number of tags and the distribution of tag IDs are unknown.The reader is statically deployed and configured with an antenna.The antenna is associated with an interrogation region,within which the reader can identify the tags.The antenna is deployed in a fixed position.It cannot change its distance to the objects,but it is rotatable The reader can control the interrogation region by adjusting the power. The objects are packaged in boxes.The boxes out of the specified area S has reasonable distances between the boxes in S,which means that the area S has a clear boundary.As shown in Fig.1,the tags in S are called as target tags,while
Focus and Shoot: Efficient Identification Over RFID Tags 345 inventory for example, we may only need to identify the tags in some specified boxes while ignoring the others. Sometimes, it is difficult to move the objects out for tag identification, especially for the objects obstructed by obstacles. A traditional solution is to identify the tags with the maximum power. It may identify the tags out of the area, which is rather time-consuming. Due to the large number of tags, the time-efficiency is very important. Therefore, it is essential to identify the tags in the specified area efficiently without moving the tags. Fortunately, we note that tag identification in the specified area can be compared to the picture-taking process in a camera. The camera needs to focus on the object before shooting, aiming to lock the target object while ignoring the others. In this paper, we propose the photography based identification method, which works in a similar way. It first focuses on the specified area by adjusting the antenna’s angle and the reader’s power, and then identifies the tags in the area. However, efficiently identifying the tags in the realistic environments is difficult. The reading performance in the realistic experiments is still unknown, especially for a large number of tags. There are a few research works concentrating on this problem and they mainly work in a situation close to free space [11–13]. Hence, we conduct a series of measurements over RFID tags in realistic settings. Based on the extensive experimental study, we respectively propose two solutions, aiming to identify the tags in the specified area efficiently. The solutions work in the realistic environments and conform to the EPC-C1G2 standards. We make the following contributions in this paper. (1) We conducted extensive experiments on the commodity RFID system in the realistic environments and investigated the factors affecting the reading performance. (2) To the best of our knowledge, this is the first work investigating the efficient tag identification in the specified area, which is essential for many applications. We propose the photography based identification method, which works in a similar way as in a camera. Besides, we respectively propose two solutions to solve the problem, which can reduce the execution time by 46 % compared to the baseline solution. (3) Our solutions work in the realistic environments with the commercial RFID system, which conforms to the EPC-C1G2 standards. 2 Problem Formulation 2.1 System Model Each object is attached with an RFID tag, which has a unique ID. In this paper, we use the terms ‘object’, ‘tag’ interchangeably. The number of tags and the distribution of tag IDs are unknown. The reader is statically deployed and configured with an antenna. The antenna is associated with an interrogation region, within which the reader can identify the tags. The antenna is deployed in a fixed position. It cannot change its distance to the objects, but it is rotatable. The reader can control the interrogation region by adjusting the power. The objects are packaged in boxes. The boxes out of the specified area S has reasonable distances between the boxes in S, which means that the area S has a clear boundary. As shown in Fig. 1, the tags in S are called as target tags, while
346 Y.Yin et al. Specified area ▣▣ ▣▣ ▣回口 ▣▣ ▣▣ ▣Tag Interrogation region Fig.1.Identify the tags in the specified area the tags outside S are called as interference tags.The objective of this paper is to identify as many target tags as possible while minimizing the execution time. 2.2 Performance Metrics We consider the three performance metrics for evaluating the solution's efficiency. (1)Coverage ratio p constraint:Let S be the set of tags in S(target tags), s=S.Let M be the set of the tags that are identified in S,m =M.Obviously, M CS and m≤s.Then,p=g,0≤p≤1.The larger the value of p,the better the coverage ratio.Given a constant a,p should satisfy p a.a is related to the specific scenario,when the environment and the deployment of the RFID system are fixed,the value of a can be determined. (2)Erecution time T:It represents the duration of the whole process.It shows the time efficiency,which is rather important,especially for the identification of a large number of tags.The smaller the time T,the better the time efficiency. (3)Misreading ratio A:Let U be the set of tags out of S(interference tags) that are identified,UnS-0.Then,The smaller the value of入，the lower the misreading ratio. The objective of this paper is to minimize the execution time T,while the coverage ratio satisfies p>o.When p o,minimizing T means avoiding identifying the interference tags,in order to reduce the identification time.There is no constraint on A,which is related to T.However,for the same execution time,the lower the misreading ratio,the better the performance of a solution. 3 Observations From the Realistic Experiments In order to know the factors affecting the reading performance in the real- istic environments,we conduct the following experiments.We use the Alien- 9900+reader and Alien-9611 antenna.The reader's maximum power marPc is 30.7 dBm and its minimum power minP is 15.7 dBm.The RFID tag is Alien 9640 tag.Each tag is attached into a distinct book.The antenna and the books are placed on the tablet chairs with a height of 0.5 m.Unless otherwise specified, we make the antenna face towards the center of the objects,set the reader's power P=30.7 dBm,the distance between the tags and the antenna d=1m by default.For each experiment,the reader scans the tags for 50 cycles
346 Y. Yin et al. Fig. 1. Identify the tags in the specified area the tags outside S are called as interference tags. The objective of this paper is to identify as many target tags as possible while minimizing the execution time. 2.2 Performance Metrics We consider the three performance metrics for evaluating the solution’s efficiency. (1) Coverage ratio ρ constraint: Let S be the set of tags in S (target tags), s = |S|. Let M be the set of the tags that are identified in S, m = |M|. Obviously, M ⊆ S and m ≤ s. Then, ρ = m s , 0 ≤ ρ ≤ 1. The larger the value of ρ, the better the coverage ratio. Given a constant α, ρ should satisfy ρ ≥ α. α is related to the specific scenario, when the environment and the deployment of the RFID system are fixed, the value of α can be determined. (2) Execution time T: It represents the duration of the whole process. It shows the time efficiency, which is rather important, especially for the identification of a large number of tags. The smaller the time T, the better the time efficiency. (3) Misreading ratio λ: Let U be the set of tags out of S (interference tags) that are identified, u = |U|, U ∩ S = ∅. Then, λ = u u+m . The smaller the value of λ, the lower the misreading ratio. The objective of this paper is to minimize the execution time T, while the coverage ratio satisfies ρ ≥ α. When ρ ≥ α, minimizing T means avoiding identifying the interference tags, in order to reduce the identification time. There is no constraint on λ, which is related to T. However, for the same execution time, the lower the misreading ratio, the better the performance of a solution. 3 Observations From the Realistic Experiments In order to know the factors affecting the reading performance in the realistic environments, we conduct the following experiments. We use the Alien- 9900+ reader and Alien-9611 antenna. The reader’s maximum power maxPw is 30.7 dBm and its minimum power minPw is 15.7 dBm. The RFID tag is Alien 9640 tag. Each tag is attached into a distinct book. The antenna and the books are placed on the tablet chairs with a height of 0.5 m. Unless otherwise specified, we make the antenna face towards the center of the objects, set the reader’s power Pw = 30.7 dBm, the distance between the tags and the antenna d = 1m by default. For each experiment, the reader scans the tags for 50 cycles
Focus and Shoot:Efficient Identification Over RFID Tags 347 3.1 Identify the Tag at Different Angles As the angle between the radiation direction and the surface of the antenna deceases,the reading performance deceases.However,when a tag is located in the center of the interrogation region,it can be identified efficiently.We observe the minimum power P needed to activate one tag.We use 0r to repre- sent the angle between the antenna's radiation direction and the antenna's sur- face,6r E[0,90].In the first experiment,we rotate the antenna to change while keeping the tag unchanged.Figure 2(a)shows that as r decreases,Pm becomes larger.In the second experiment,we rotate the tag while keeping the antenna unchanged.We use 6:to represent the angle between the radiation direction and the tag's surface.Figure 2(a)shows that the tag is easily identified, whatever 0:is.Therefore,making the antenna face towards the tags(0,=90) is essential for improving the reading performance. 3.2 Adjust the Reader's Power The larger the reader's power,the larger the interrogation region,but the new identified tags may not be located in the interrogation region's boundary.How- ever,if a tag can be identified with a low power,it must be identified with a larger power.We uniformly deploy 72 tags on the wall and the distance between two adjacent tags is 20 cm,as shown in Fig.2(b).The new identified tags may not be ●-Rotate antenna:g ■25.7dBm026.7dBm 50 ◆ -Rot妇teeg:0, 45 2 9 35 2 25 10 1 15 30 4560 75 90 012345678910111213 16.718.720.722.724.726.728730.7 Angle ( Column number Power (dBm) (a)Minimum power vs.an- (b)Distribution of identi- (c)Identified tag IDs vs. gles fied tags vs.powers powers 100 2 20 220 er:17.7dBr -Power 18 7dBn 60 10 40 0.51.01.52.0253.03.5 2-1.5-1.0-0.50.00.51.01.52.0 102030405060 Distance:d (m) Scanning range (m) Tag size (d)Coverage ratio vs.dis-(e)Scanning range vs.tag (f)Number of identified tags tances densities vs.tag sizes Fig.2.Observations from the realistic experiments
Focus and Shoot: Efficient Identification Over RFID Tags 347 3.1 Identify the Tag at Different Angles As the angle between the radiation direction and the surface of the antenna deceases, the reading performance deceases. However, when a tag is located in the center of the interrogation region, it can be identified efficiently. We observe the minimum power Pwmin needed to activate one tag. We use θr to represent the angle between the antenna’s radiation direction and the antenna’s surface, θr ∈ [0◦, 90◦]. In the first experiment, we rotate the antenna to change θr while keeping the tag unchanged. Figure 2(a) shows that as θr decreases, Pwmin becomes larger. In the second experiment, we rotate the tag while keeping the antenna unchanged. We use θt to represent the angle between the radiation direction and the tag’s surface. Figure 2(a) shows that the tag is easily identified, whatever θt is. Therefore, making the antenna face towards the tags (θr = 90◦) is essential for improving the reading performance. 3.2 Adjust the Reader’s Power The larger the reader’s power, the larger the interrogation region, but the new identified tags may not be located in the interrogation region’s boundary. However, if a tag can be identified with a low power, it must be identified with a larger power. We uniformly deploy 72 tags on the wall and the distance between two adjacent tags is 20 cm, as shown in Fig. 2(b).The new identified tags may not be (a) Minimum power vs. angles (b) Distribution of identi- fied tags vs. powers (c) Identified tag IDs vs. powers (d) Coverage ratio vs. distances (e) Scanning range vs. tag densities (f) Number of identified tags vs. tag sizes Fig. 2. Observations from the realistic experiments
348 Y.Yin et al. in the interrogation region's boundary.We cannot distinguish a tag's position only by adjusting the power.In regard to a tag,Fig.2(c)shows that if a tag can be identified with a low power,then it definitely can be identified by a larger power.Usually,the large power can increase the number of identified tags. 3.3 Vary the Distance Between the Tags and the Antenna As the distance between the tags and the antenna increases,the reading per- formance decreases.Besides,when the distance is fired,the marimum coverage ratio has an upper bound,whatever the reader's power is.We vary the distance d from 0.5m to 3.5m.Figure2(d)shows as d becomes larger,the number of identified tags decreases.When the distance is small (eg.d<1.5m),the read- ing performance is relatively good.However,when the distance and the number of tags are fixed,the coverage ratio has an upper bound.For example,when d =1.5m and n =55,the maximum coverage ratio is 78%.Fortunately,some applications (eg.sampling inspection)just needs the coverage ratios meet the constraint instead of achieving 100 %However,when considering the high cov- erage ratio,the antenna should not be placed far away from the tags. 3.4 Effect of the Tag Size The tag size can affect the effective interrogation region.However,it has lit- tle effect on the number of identified tags.We uniformly deploy the tags in a row with length 4m and vary the number of tags (20,40,60,80).As shown in Fig.2(e),given a fixed power (30.7dBm),as the tag size increases,the effective interrogation region decreases.Therefore,when the tag size in the specified area (tag density)is unknown,we can not calculate the interrogation region accu- rately.However,if we only want to identify a few tags (eg.for sampling),we can choose an estimated power,because the tag size has little effect on the number of identified tags,as shown in Fig.2(f). 4 Baseline Solutions In order to identify the target tags in the specified area S,while ignoring the inter- ference tags,we should focus on S and identify as many target tags as possible.As mentioned in Sect.3.2,the larger the reader's power,the larger the interrogation region.If we want to focus on the area S,we should use a lower power.On the contrary,if we want to identify more tags,we should use a larger power.There- fore,scanning with the minimum power and the maximum power are two baseline solutions,which are respectively called as MinPw and MaxPw. However,if the reader's power is too small,the interrogation region cannot cover the specified area,leading to the low coverage ratio.Besides,it needs to rotate the antenna to identify more tags with multiple scans,which is rather time-consuming.If the reader's power is too large,the interrogation region may be too large,leading to the identification of the interference tags.It increases the time cost and the misreading ratio.Therefore,it is important to use a reasonable power to identify the tags in the specified area
348 Y. Yin et al. in the interrogation region’s boundary. We cannot distinguish a tag’s position only by adjusting the power. In regard to a tag, Fig. 2(c) shows that if a tag can be identified with a low power, then it definitely can be identified by a larger power. Usually, the large power can increase the number of identified tags. 3.3 Vary the Distance Between the Tags and the Antenna As the distance between the tags and the antenna increases, the reading performance decreases. Besides, when the distance is fixed, the maximum coverage ratio has an upper bound, whatever the reader’s power is. We vary the distance d from 0.5 m to 3.5 m. Figure 2(d) shows as d becomes larger, the number of identified tags decreases. When the distance is small (eg. d ≤ 1.5 m), the reading performance is relatively good. However, when the distance and the number of tags are fixed, the coverage ratio has an upper bound. For example, when d = 1.5 m and n = 55, the maximum coverage ratio is 78 %. Fortunately, some applications (eg. sampling inspection) just needs the coverage ratios meet the constraint instead of achieving 100 %. However, when considering the high coverage ratio, the antenna should not be placed far away from the tags. 3.4 Effect of the Tag Size The tag size can affect the effective interrogation region. However, it has little effect on the number of identified tags. We uniformly deploy the tags in a row with length 4 m and vary the number of tags (20, 40, 60, 80). As shown in Fig. 2(e), given a fixed power (30.7 dBm), as the tag size increases, the effective interrogation region decreases. Therefore, when the tag size in the specified area (tag density) is unknown, we can not calculate the interrogation region accurately. However, if we only want to identify a few tags (eg. for sampling), we can choose an estimated power, because the tag size has little effect on the number of identified tags, as shown in Fig. 2(f). 4 Baseline Solutions In order to identify the target tags in the specified area S, while ignoring the interference tags, we should focus on S and identify as many target tags as possible. As mentioned in Sect. 3.2, the larger the reader’s power, the larger the interrogation region. If we want to focus on the area S, we should use a lower power. On the contrary, if we want to identify more tags, we should use a larger power. Therefore, scanning with the minimum power and the maximum power are two baseline solutions, which are respectively called as MinPw and MaxPw. However, if the reader’s power is too small, the interrogation region cannot cover the specified area, leading to the low coverage ratio. Besides, it needs to rotate the antenna to identify more tags with multiple scans, which is rather time-consuming. If the reader’s power is too large, the interrogation region may be too large, leading to the identification of the interference tags. It increases the time cost and the misreading ratio. Therefore, it is important to use a reasonable power to identify the tags in the specified area