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
Focus and Shoot:Efficient Identification Over RFID Tags 349 5 Photography Based Identification with Distance Measurement In this section,we propose a solution called Photography based tag Identification with Distance measurement(PID),which works with a 3D camera(eg.a Kinect). The process of PID can be compared to the picture-taking process in a camera. It focuses on the area and shoot the objects,as shown in Fig.3.The application appoints the specified area S and the middleware collects the tag IDs in S by the RFID systems.It consists of focus module and shoot module.The focus module adjusts the reader's power and rotates the antenna to make the interrogation region focus on S.The shoot module collects tag IDs.The two corresponding process are respectively called as Focusing Process and Shooting Process. Tag Identification in the Specified Area Application Sampling Inspection Inventory Other similar applications Focus Module Shoot Module Middleware (Focus on the specified area) (Collect the tag IDs) Adjustable components RFID tags RFID System Antenna Reader Target tags (Rotate to the specifed area) (Power stepping) (Focus the target tags in the specified area) Interference tags Fig.3.The Framework of PID 5.1 Focusing Process The focusing process aims to adjust the interrogation region to be focused on the specified area S by adjusting ,Po,while ignoring the tags outside S.It contains three phases,selecting the initial power,establishing the boundary and power stepping.The process aims to get the optimal power P,whose corresponding interrogation region is just enough to cover the area S. Selecting the Initial Power.Before the reader identifies the tags,it selects the initial power instead of the default(maximum)one to control the interroga- tion region.In RFID systems,the reader's interrogation region of an antenna is like an ellipsoid.The larger the angle 0,between the radiation direction and the antenna's surface,the longer the reader's scanning range.However,in the realis- tic environment,the tag size,the reader's power Pe,the radiation angle 0r,and the distance d all affect the effective interrogation region,as mentioned in Sect.3. Therefore,in the realistic environments,we measure the minimum power Pm
Focus and Shoot: Efficient Identification Over RFID Tags 349 5 Photography Based Identification with Distance Measurement In this section, we propose a solution called Photography based tag Identification with Distance measurement (PID), which works with a 3D camera (eg. a Kinect). The process of PID can be compared to the picture-taking process in a camera. It focuses on the area and shoot the objects, as shown in Fig. 3. The application appoints the specified area S and the middleware collects the tag IDs in S by the RFID systems. It consists of focus module and shoot module. The focus module adjusts the reader’s power and rotates the antenna to make the interrogation region focus on S. The shoot module collects tag IDs. The two corresponding process are respectively called as Focusing Process and Shooting Process. Fig. 3. The Framework of PID 5.1 Focusing Process The focusing process aims to adjust the interrogation region to be focused on the specified area S by adjusting θr, Pw, while ignoring the tags outside S. It contains three phases, selecting the initial power, establishing the boundary and power stepping. The process aims to get the optimal power P∗ w, whose corresponding interrogation region is just enough to cover the area S. Selecting the Initial Power. Before the reader identifies the tags, it selects the initial power instead of the default (maximum) one to control the interrogation region. In RFID systems, the reader’s interrogation region of an antenna is like an ellipsoid. The larger the angle θr between the radiation direction and the antenna’s surface, the longer the reader’s scanning range. However, in the realistic environment, the tag size, the reader’s power Pw, the radiation angle θr, and the distance d all affect the effective interrogation region, as mentioned in Sect. 3. Therefore, in the realistic environments, we measure the minimum power Pwmin
350 Y.Yin et al. based on 0r and d,and use them to calculate the initial power.In this paper,we measure P(0r,d)with the distances dj=0.5m x j,j[1,7]and the angles 0A:=90°-15°×i,i∈0,6.For example,we get Pin(90°，1.0)=15.7dBm, Pwmn(75°，1.5)=18.8dBm,Pwmn(60°，2.0)=23.4dBm.The reader first selects the reference angle 6:closest to6,le,-fl≤|9，-0kl(k∈[0,6andk≠i): Then,it uses d to calculate the initial power P(0,d) Pwmi(0,d） if d=dj Pwmin (dj)+Pwmn (d+1) (1) 2 if deldj,dj+1l However,the power is only used as the initial power.In order to identify more tags,the reader can repeatedly increase the power by AP.We set AP= 1 dBm,which is achievable by most of the commercial readers [14]. Establishing the Boundary.The 3D camera can recognize the specified area by RGB camera and measure distance by 3D depth sensors.However,the reader can hardly find the boundary of S,due to the unknown distribution of tag IDs. Therefore,PID first establishes the boundary So of the area S based on the interference tags located around S,as shown in Fig.4.PID uses the 3D camera to calculate the minimum distance do between the interference tags in S and the antenna,and the distance d between the center of S and the antenna.Further- more,it calculates the rotation angle=arccos(),(,90).Then,the antenna rotates p degree to face the interference tags in S for identification. The identified tags are used as reference tags to describe Sp. Specified area Anicmna Interrogation region Fig.4.Identify the tags in the specified area with a 3D camera In PID,the antenna always faces towards the center of the objects, 90.Then,the reader selects the initial power Pb according to the distance d, Pb=P(90,d).If the power P is not large enough,the reader increases the power by AP and identifies no tags,as shown in Algorithm 1.It repeats the above process until no>ne,which means that it has collected enough tag IDs N ={ID1,ID2,...,ID}from the boundary.However,if the reader's power has achieved to the maximum value maxP,no is still less than ne,which indicates most of the interference tags are far away from S.Then,the reader stops the process and gets the optimal power P=maxP.After that,the antenna rotates towards the center of S for power stepping and tag identification
350 Y. Yin et al. based on θr and d, and use them to calculate the initial power. In this paper, we measure Pwmin (θr, d) with the distances dj = 0.5 m × j, j ∈ [1, 7] and the angles θi = 90◦ − 15◦ × i, i ∈ [0, 6]. For example, we get Pwmin (90◦, 1.0) = 15.7 dBm, Pwmin (75◦, 1.5) = 18.8 dBm, Pwmin (60◦, 2.0) = 23.4 dBm. The reader first selects the reference angle θi closest to θr, |θr − θi|≤|θr − θk| (k ∈ [0, 6] and k = i). Then, it uses d to calculate the initial power Pwmin (θr, d) Pwmin (θi, dj ) if d = dj Pwmin (θi,dj )+Pwmin (θi,dj+1) 2 if d ∈ [dj , dj+1]. (1) However, the power is only used as the initial power. In order to identify more tags, the reader can repeatedly increase the power by ΔPw. We set ΔPw = 1 dBm, which is achievable by most of the commercial readers [14]. Establishing the Boundary. The 3D camera can recognize the specified area by RGB camera and measure distance by 3D depth sensors. However, the reader can hardly find the boundary of S, due to the unknown distribution of tag IDs. Therefore, PID first establishes the boundary Sb of the area S based on the interference tags located around S, as shown in Fig. 4. PID uses the 3D camera to calculate the minimum distance db between the interference tags in Sb and the antenna, and the distance ds between the center of S and the antenna. Furthermore, it calculates the rotation angle ϕ = arccos( ds db ), ϕ ∈ (0◦, 90◦). Then, the antenna rotates ϕ degree to face the interference tags in Sb for identification. The identified tags are used as reference tags to describe Sb. Fig. 4. Identify the tags in the specified area with a 3D camera In PID, the antenna always faces towards the center of the objects, θr = 90◦. Then, the reader selects the initial power Pwb according to the distance d, Pwb = Pwmin (90◦, d). If the power Pwb is not large enough, the reader increases the power by ΔPw and identifies nb tags, as shown in Algorithm 1. It repeats the above process until nb ≥ nε, which means that it has collected enough tag IDs Nb = {ID1,ID2,...,IDnb } from the boundary. However, if the reader’s power has achieved to the maximum value maxPw, nb is still less than nε, which indicates most of the interference tags are far away from S. Then, the reader stops the process and gets the optimal power P∗ w = maxPw. After that, the antenna rotates towards the center of S for power stepping and tag identification.
Focus and Shoot:Efficient Identification Over RFID Tags 351 Algorithm 1.PID:Establishing the boundary Input:The specified area S Determine the boundary S of S by the 3D camera,and calculate do and ds. The antenna rotates to s withparccos(). P.b=Pemn(90°，d),Pe=Pb,n6=0. while nominPu do Pu max(Pu-APu,minP). Check IDs in Ne,get△ne responses,ne=△ne. if ns 6 then Pu P,Break. Output:The optimal power P In the commercial RFID systems,the reader (eg.Alien-9900+)selects a specified tag by setting the mask equal to the tag ID.If the tag gives response,the reader gets a nonempty slot.Otherwise,it gets an empty slot.The reader checks all the IDs in N and gets ne responses Ne.Obviously,ne<n.When a=6,the interrogation region just achieves the boundary of S.The corresponding power
Focus and Shoot: Efficient Identification Over RFID Tags 351 Algorithm 1. PID: Establishing the boundary Input: The specified area S Determine the boundary Sb of S by the 3D camera, and calculate db and ds. The antenna rotates to Sb with ϕ = arccos( ds db ). Pwb = Pwmin (90◦, db), Pw = Pwb, nb = 0. while nb δ then while Pw > minPw do Pw = max(Pw − ΔPw, minPw). Check IDs in Nc, get Δnc responses, nc = Δnc. if nc nb ≤ δ then P∗ w = Pw, Break. if nc nb < δ then while Pw < maxPw do Pw = min(Pw + ΔPw, maxPw). Check IDs in Nb − Nc, get Δnc responses, nc = nc + Δnc. if nc nb ≥ δ then P∗ w = Pw, Break. Output: The optimal power P∗ w In the commercial RFID systems, the reader (eg. Alien-9900+) selects a specified tag by setting the mask equal to the tag ID. If the tag gives response, the reader gets a nonempty slot. Otherwise, it gets an empty slot. The reader checks all the IDs in Nb and gets nc responses Nc. Obviously, nc ≤ nb. When nc nb = δ, the interrogation region just achieves the boundary of S. The corresponding power
352 Y.Yin et al. is the optimal power P.However,if >6,the reader reduces the power by AP and checks the verified tag IDs in Ne.If a tag does not give response,the reader removes it from Ne.It repeats the above process until 6 and gets the optimal power P In the following process,the reader usesto identify the target tags. 5.2 Shooting Process In this process,the reader collects the tag IDs in S.The reader's power is equal to P and we use frame slotted ALOHA (FSA)protocol to identify the tags.FSA is a popular anti-collision protocol.In FSA,the reader first broadcasts a number f, which specifies the following frame size.After receiving f,each tag selects h(ID) mod f as its slot number,h is a hash function.If none of the tags respond in a slot,the reader closes the slot immediately.If only one tag responds in a slot,the reader successfully receives the tag ID.If multiple tags respond simultaneously, a collision occurs,and the involved tags will be acknowledged to restart in the next frame.The similar process repeats until no tags respond in the frame.The collected IDs are considered as the target tag IDs. 5.3 Performance Analysis In order to definitely describe the boundary So,PID needs to steadily get at least ne interference tag IDs,no satisfies no >ne.We measure the value of ne with different tag size NI.When |NI 20,60,100,140,180,220,we respectively get ne =2,4,7,9,11,12.The tag size N]has a little effect on ne,which is usually very small.In order to definitely get enough tag IDs in So,we set ne= 15 by default,while considering the stability and time efficiency.In regard to 6,the smaller the value of 6,the lower the misreading ratio,the smaller the execution time.The larger the value of 6,the larger the value of coverage ratio p.Considering the constraint of p and time efficiency,we set 6 =a.When =6=a,the interrogation region just achieves the boundary,while satisfying nb p >o.Besides,the antenna rotates to the target direction immediately,the time for rotating the antenna can be neglected compared to the tag identification time. 6 Photography Based Identification with Angle Rotation In PID,a 3D camera is used in the focusing process.However,in some envi- ronments,the 3D camera cannot work well (eg.in a dark space).Besides,con- sidering the cost savings,it will not be used.Therefore,identifying the target tags efficiently without the auxiliary equipment is important.For this prob- lem,we propose a solution called Photography based tag Identification with Angle rotation (PIA).It also consists of Focusing Process and Shooting Process
352 Y. Yin et al. is the optimal power P∗ w. However, if nc nb > δ, the reader reduces the power by ΔPw and checks the verified tag IDs in Nc. If a tag does not give response, the reader removes it from Nc. It repeats the above process until nc nb ≤ δ and gets the optimal power P∗ w. On the contrary, if nc nb < δ, the reader increases Pw by ΔPw and checks the unverified tag IDs in Nb −Nc = {IDi | IDi ∈ Nb and IDi ∈/ Nc}. If the tag gives response, the reader adds the ID into Nc. It repeats the process until nc nb ≥ δ and gets the optimal power P∗ w. In the following process, the reader uses P∗ w to identify the target tags. 5.2 Shooting Process In this process, the reader collects the tag IDs in S. The reader’s power is equal to P∗ w and we use frame slotted ALOHA (FSA) protocol to identify the tags. FSA is a popular anti-collision protocol. In FSA, the reader first broadcasts a number f, which specifies the following frame size. After receiving f, each tag selects h(ID) mod f as its slot number, h is a hash function. If none of the tags respond in a slot, the reader closes the slot immediately. If only one tag responds in a slot, the reader successfully receives the tag ID. If multiple tags respond simultaneously, a collision occurs, and the involved tags will be acknowledged to restart in the next frame. The similar process repeats until no tags respond in the frame. The collected IDs are considered as the target tag IDs. 5.3 Performance Analysis In order to definitely describe the boundary Sb, PID needs to steadily get at least nε interference tag IDs, nb satisfies nb ≥ nε. We measure the value of nε with different tag size |N|. When |N| = 20, 60, 100, 140, 180, 220, we respectively get nε = 2, 4, 7, 9, 11, 12. The tag size |N| has a little effect on nε, which is usually very small. In order to definitely get enough tag IDs in Sb, we set nε = 15 by default, while considering the stability and time efficiency. In regard to δ, the smaller the value of δ, the lower the misreading ratio, the smaller the execution time. The larger the value of δ, the larger the value of coverage ratio ρ. Considering the constraint of ρ and time efficiency, we set δ = α. When nc nb = δ = α, the interrogation region just achieves the boundary, while satisfying ρ ≥ α. Besides, the antenna rotates to the target direction immediately, the time for rotating the antenna can be neglected compared to the tag identification time. 6 Photography Based Identification with Angle Rotation In PID, a 3D camera is used in the focusing process. However, in some environments, the 3D camera cannot work well (eg. in a dark space). Besides, considering the cost savings, it will not be used. Therefore, identifying the target tags efficiently without the auxiliary equipment is important. For this problem, we propose a solution called Photography based tag Identification with Angle rotation (PIA). It also consists of Focusing Process and Shooting Process
Focus and Shoot:Efficient Identification Over RFID Tags 353 The only difference between PID and PIA is how to determine the boundary of S.We only describe how to find the boundary in PIA,while ignoring the others. Without the 3D camera,PIA cannot calculate any distance,it explores the boundary by rotating the antenna,as shown in Fig.5.Firstly,the application appoints S and the antenna rotates towards S.Then the reader sets its initial power equal to the minimum power min P and identifies ns tags in S.If ns0 then P min(P+AP,maxP).else Break. N6=V. The antenna rotates to the right in[O°，△orJ,gets Nr,it rotates△0 r degree. if△0n=△0 r.then N%=NUNr.else if△0r>△0r,then N=Nr. Output:Tag IDs in the boundary N When the antenna rotates to another direction(called as left),ns decreases As shown in Algorithm 3,when the radiation angle decreases by Aor,Ans tags in Ns disappear.The reader gets n new tag IDs,which are considered as the tag IDs from the boundary.If n ne,the reader collects enough tag IDs
Focus and Shoot: Efficient Identification Over RFID Tags 353 The only difference between PID and PIA is how to determine the boundary of S. We only describe how to find the boundary in PIA, while ignoring the others. Without the 3D camera, PIA cannot calculate any distance, it explores the boundary by rotating the antenna, as shown in Fig. 5. Firstly, the application appoints S and the antenna rotates towards S. Then the reader sets its initial power equal to the minimum power minPw and identifies ns tags in S. If ns 0 then Pw = min(Pw + ΔPw, maxPw). else Break. Nb = Nl. The antenna rotates to the right in [0◦, Δθrl ], gets Nr, it rotates Δθrr degree. if Δθrl = Δθrr then Nb = Nl ∪ Nr. else if Δθrl > Δθrr then Nb = Nr. Output: Tag IDs in the boundary :Nb When the antenna rotates to another direction (called as left), ns decreases. As shown in Algorithm 3, when the radiation angle decreases by Δθr, Δns tags in Ns disappear. The reader gets nl new tag IDs, which are considered as the tag IDs from the boundary. If nl ≥ nε, the reader collects enough tag IDs
