Focus and Shoot:Efficient Identification over RFID Tags in the Specified Area Yafeng Yinl,Lei Xiel,Jie Wu2.Athanasios V.Vasilakos3,and Sanglu Lul 1 State Key Laboratory for Novel Software Technology,Nanjing University,China yyf@dislab.nju.edu.cn,{lxie,sanglu}@nju.edu.cn 2 Department of Computer and Information Sciences,Temple University,USA jiewu@temple.edu 3 University of Western Macedonia,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. Key words: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][2][3][4].In- stead 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 iden- tification,cardinality estimation protocols count the number of tags 8910 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 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 iden- tify 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
Focus and Shoot: Efficient Identification over RFID Tags in the Specified Area Yafeng Yin1 , Lei Xie1 , Jie Wu2 , Athanasios V. Vasilakos3 , and Sanglu Lu1 1 State Key Laboratory for Novel Software Technology, Nanjing University, China yyf@dislab.nju.edu.cn, {lxie,sanglu}@nju.edu.cn 2 Department of Computer and Information Sciences, Temple University, USA jiewu@temple.edu 3 University of Western Macedonia, 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. Key words: 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][2][3][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][9][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 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
2 Yafeng Yin et al. 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][12][13] Hence,we conduct a series of measurements over RFID tags in realistic settings. Based on the extensive experimental study,we respectively propose two solu- tions,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 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. Interrogation ▣Tag region Fig.1.Identify the tags in the specified area 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 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 Yafeng Yin et al. 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][12][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. Specified area Tag (S) Interrogation region Fig. 1. Identify the tags in the specified area 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 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
Focus and Shoot 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, C S and m≤s.Them,p=g,0≤p≤l.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)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 A:Let U be the set of tags out of S (interference tags) that are identified,u=lUl,UnS=0.Then,A=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 p>a.When p a,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 realistic environments,we conduct the following experiments.We use the Alien-9900+ reader and Alien-9611 antenna.The reader's maximum power maxP is 30.7dB- m and its minimum power minP is 15.7dBm.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.5m.Unless otherwise specified, we make the antenna face towards the center of the objects,set the reader's power P=30.7dBm,the distance between the tags and the antenna d=1m by default.For each experiment,the reader scans the tags for 50 cycles 3.1 Identify the tag at different angles As the angle between the radiation direction and the surface of the antenna de- ceases,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 Pmm needed to activate one tag.We use r to represent the angle between the antenna's radiation direction and the antenna's surface, b,∈O°，90°.In the first experiment,we rotate the antenna to change b,while keeping the tag unchanged.Fig.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.Fig.2(a)shows that the tag is easily identified,whatever 6t is. Therefore,making the antenna face towards the tags(=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.Howev- er,if a tag can be identified with a low power,it must be identified with a larger
Focus and Shoot 3 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.7dBm and its minimum power minPw is 15.7dBm. 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.5m. Unless otherwise specified, we make the antenna face towards the center of the objects, set the reader’s power Pw = 30.7dBm, the distance between the tags and the antenna d = 1m by default. For each experiment, the reader scans the tags for 50 cycles. 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. Fig. 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. Fig. 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
4 Yafeng Yin et al. power.We uniformly deploy 72 tags on the wall and the distance between two adjacent tags is 20cm,as shown in Fig.2(b).The new identified tags may not be 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. 32 -◆Rotate antenna:e, ■25.7Bm0.26.74Bm 30 28 一-Rotate tag8 3 24 30 025 320 崔 1401630Ad3607500 0123色o品1品eg10111213 16.7187207227307287307 (a)Minimum power vs.an-(b)Distribution of identi-(c)Identified tag IDs vs. gles fied tags vs.powers Dowers 100 Poer157d日m 20 60 10 0510o6品2303 -1.5-15g98l1520 10 209s 050 60 (d)Coverage ratio vs.dis-(e)Scanning range vs.tag(f)Number ofidentified tags tances densities vs.tag sizes Fig.2.Observations from the realistic experiments 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.Fig.2(d)shows as d becomes larger,the number of identified tags decreases.When the distance is small (eg.d <1.5m),the reading perfor- mance 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 in- stead 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 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 in- terrogation region decreases.Therefore,when the tag size in the specified area
4 Yafeng Yin et al. power. We uniformly deploy 72 tags on the wall and the distance between two adjacent tags is 20cm, as shown in Fig. 2(b).The new identified tags may not be 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. 0 15 30 45 60 75 90 14 16 18 20 22 24 26 28 30 32 Angle (q) Power (dBm) Rotate antenna: T r Rotate tag: T t (a) Minimum power vs. angles 0 1 2 3 4 5 6 7 8 9 101112 13 0 1 2 3 4 5 6 7 Column number Row number 25.7dBm 26.7dBm (b) Distribution of identi- fied tags vs. powers 16.7 18.7 20.7 22.7 24.7 26.7 28.7 30.7 0 5 10 15 20 25 30 35 40 45 50 55 Power (dBm) Tag ID (c) Identified tag IDs vs. powers 0.5 1.0 1.5 2.0 2.5 3.0 3.5 0 20 40 60 80 100 Distance: d (m) Coverage Ratio (%) (d) Coverage ratio vs. distances -2 -1.5 -1.0 -0.5 0.0 0.5 1.0 1.5 2.0 0 5 10 15 20 25 Scanning range (m) Tag density (tags/m) (e) Scanning range vs. tag densities 10 20 30 40 50 60 0 5 10 15 20 Tag size Number of identified tags Power: 15.7dBm Power: 16.7dBm Power: 17.7dBm Power: 18.7dBm (f) Number of identified tags vs. tag sizes Fig. 2. Observations from the realistic experiments 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.5m to 3.5m. Fig. 2(d) shows as d becomes larger, the number of identified tags decreases. When the distance is small (eg. d ≤ 1.5m), 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.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 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 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
Focus and Shoot (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 in- terference tags,we should focus on S and identify as many target tags as possible. As mentioned in 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. 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 Middlewar (Colleet 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
Focus and Shoot 5 (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 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. 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. Sampling Inspection Inventory Tag Identification in the Specified Area Application Focus Module Shoot Module Middleware (Focus on the specified area) (Collect the tag IDs) Other similar applications RFID System RFID tags Target tags Interference tags Antenna (Rotate to the specifed area) Reader (Power stepping) Adjustable components (Focus the target tags in the specified area) Fig. 3. The Framework of PID
6 Yafeng Yin et al. 5.1 Focusing Process The focusing process aims to adjust the interrogation region to be focused on the specified area S by adjusting r,P,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 interrogation 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 an- tenna's surface,the longer the reader's scanning range.However,in the realistic environment,the tag size,the reader's power Po,the radiation angle 0r,and the distance d all affect the effective interrogation region,as mentioned in section 3. Therefore,in the realistic environments,we measure the minimum power P based on 6,and d,and use them to calculate the initial power.In this paper,we measure P (r,d)with the distances dj=0.5m x j,j[1,7]and the angles 9=90°-15°×i,i∈[0,6.For example,we get Pmin(90°，1.0)=15.7dBm, Pwmin(75°，1.5)=l8.8dBm,Pwn(60°，2.0)=23.4dBm.The reader first selects the reference angle 0i closest to r,0r-il <0r-(k E [0,6]and k i). Then,it uses d to calculate the initial power Pm(r,d) Pwmn(0,d） if d=di Pwmin (0dj)+Pmind ifd∈[d,dj+l (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 AP.We set AP= 1dBm,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 S of the area S based on the in- terference 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 So and the antenna,and the distance ds between the center of S and the antenna.Further- more,it calculates the rotation angle=arccos(是)，p∈(0°，90).Then,the antenna rotates degree to face the interference tags in So for identification. The identified tags are used as reference tags to describe S. ▣▣ 口口 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 Pb according to the distance d
6 Yafeng Yin et al. 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 section 3. Therefore, in the realistic environments, we measure the minimum power Pwmin 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.5m × j, j ∈ [1, 7] and the angles θi = 90◦ − 15◦ × i, i ∈ [0, 6]. For example, we get Pwmin (90◦ , 1.0) = 15.7dBm, Pwmin (75◦ , 1.5) = 18.8dBm, Pwmin (60◦ , 2.0) = 23.4dBm. 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 = 1dBm, 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. Specified area (S) Interrogation region Tag (S) db ds Antenna ¶ 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
Focus and Shoot P=P(90,d).If the power Pb 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 n>n,which means that it has collected enough tag IDs N =[ID1,ID2,...,IDn}from the boundary.However,if the reader's power has achieved to the maximum value marP,n 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=marP.After that,the antenna rotates towards the center of S for power stepping and tag identification. Algorithm 1:PID:Establishing the boundary Input:The specified area S Determine the boundary Se of S by the 3D camera,and calculate do and ds. The antenna rotates to s witharccos(). Prb=Pmin(90°，d),Pw=Pcb,nb=0. while nb6 then while P>minPu do P max(Pu -APw,minP). Check IDs in Ne,get△ne responses,ne=△nc if "s then Pi=P.Break. if路<6then while P<maxP do Pw=min(Pu+△Pu,max P）. Check IDs in N-Ne,get Ane responses,ne ne+Ane. ift≥6 then P=Pw,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
Focus and Shoot 7 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. 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
Yafeng Yin et al. all the IDs in N and gets ne responses Ne.Obviously,ne n.When ne =6,the interrogation region just achieves the boundary of S.The corresponding power 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 until6 and gets the optimal power P.On the contrary,if 6 and gets the optimal power P.In the following process,the reader usestoidentify 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 S,PID needs to steadily get at least ne interference tag IDs,no satisfies np ne.We measure the value of ne with different tag size NI.When N]=20,60,100,140,180,220,we respectively get ne =2,4,7,9,11,12.The tag size NI 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 ns=6=a,the interrogation region just achieves the boundary,while satisfying 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 en- vironments,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.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
8 Yafeng Yin et al. 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 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. 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
Focus and Shoot 9 power equal to the minimum power min P and identifies ns tags in S.If ns0 then Pe=min(P+AP,marP).else Break N6=N. The antenna rotates to the right in [0°，△or,l,gets Nr,it rotates△ar,degree if△0nm=△9，then N6=NUNr.else if△0rm>△0r,then N=N 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 A0r,Ans tags in N.disappear.The reader gets n new tag IDs,which are considered as the tag IDs from the boundary.If n>n,the reader collects enough tag IDs N=[ID1,ID2,...,ID}from the boundary.Otherwise,it increases the power by AP and gets An new tag IDs.Everytime,it should make sure that Ans>0,which indicates the new tag IDs are not from the area S.If Ans=0. the antenna keeps rotating away from S.PIA repeats the above process until n>n.Then,the antenna has rotated Adr,degree.After that,the antenna rotates to the opposite direction (right)and works in the same way.It rotates Aer,degree to the right side.If Aer>Aor,it indicates the boundary in the right side is farther than the left one,then the reader terminates the process. Otherwise,it obtains N=[ID1,ID2,...,ID}.The reader compares Ar and A0r,to find the nearer boundary with the smaller angle,and gets the new set N of interference tags.f△9,1=△9r,V%=NUNr.If△9n1△0，Nb=Nr.No is used for power stepping-
Focus and Shoot 9 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 Nl = {ID′ 1 , ID′ 2 , . . . , ID′ nl } from the boundary. Otherwise, it increases the power by ∆Pw and gets ∆nl new tag IDs. Everytime, it should make sure that ∆ns > 0, which indicates the new tag IDs are not from the area S. If ∆ns = 0, the antenna keeps rotating away from S. PIA repeats the above process until nl ≥ nε. Then, the antenna has rotated ∆θrl degree. After that, the antenna rotates to the opposite direction (right) and works in the same way. It rotates ∆θrr degree to the right side. If ∆θrr > ∆θrl , it indicates the boundary in the right side is farther than the left one, then the reader terminates the process. Otherwise, it obtains Nr = {ID′′ 1 , ID′′ 2 , . . . , ID′′ nr }. The reader compares ∆θrl and ∆θrr to find the nearer boundary with the smaller angle, and gets the new set Nb of interference tags. If ∆θrl = ∆θrr , Nb = Nl ∪ Nr. If ∆θrl ∆θrr , Nb = Nr. Nb is used for power stepping
10 Yafeng Yin et al. The values of parameters in PIA are equal to those in PID.In regard to Ad, in PIA,we set△9，=30°.Based on Fig.2(a),when0r∈[75°，90]，the reader undoubtedly has good performance.Therefore,when A0,=30,each tag can be requested in the region with,∈[75°，90]. 7 Performance Evaluation We evaluate the performance of each solution in the realistic environments.The experimental facilities are the same as those used in the observations.The execu- tion time,coverage ratio,and misreading ratio are used for performance metrics. In the experiments,each book is attached with an RFID tag,and the tag ID is 96 bits.The books are randomly deployed in three boxes and the distribution of the tag IDs are unknown.Each box is placed on a tablet chair with a height of 0.5m,as shown in Fig.6.PID uses a 3D camera,while PIA does not.The antenna is deployed on the smart car,which is controlled by the program and can rotate with the antenna flexibly.The antenna faces towards the tags to be identified.The specified area here is the center box,which is the target bor,while the other two boxes are interference bores.The distance between the target box and the antenna is d.The minimum distance between the interference box and the target box is l.s and u respectively represent the number of target tags (in target box)and the number of interference tags (in interference boxes).We verify the values of the parameters d,l,s,u to evaluate the performance of each solution.We set d=1m.I=1m,s=80,u=70 by default. Ing the tags 3D (a)PID (b)PIA Fig.6.System prototypes work in the realistic environments 7.1 Upper bound of o As mentioned in section 2.2,when the distance d,the number of tags n are fixed. we can determine the value of a.In table 1,we give the upper bound of o under different conditions.We set a=60%for the following experiments by default. Table 1.Upper bound of o d (m) 0.5 1.0 1.5 40 100%1100%90% 80 95%85%65% 120 89%81%63% 7.2 Coverage Ratio p Constraint We first investigate the coverage ratio p of each solution,as shown in Fig.7.We can observe that scanning with the minimum power (MinPw)can not achieve the requirement of coverage ratio (a =60%).Because the power is too small to activate the majority of the tags.When we identify the tags with the maximum
10 Yafeng Yin et al. The values of parameters in PIA are equal to those in PID. In regard to ∆θr in PIA, we set ∆θr = 30◦ . Based on Fig. 2(a), when θr ∈ [75◦ , 90◦ ], the reader undoubtedly has good performance. Therefore, when ∆θr = 30◦ , each tag can be requested in the region with θr ∈ [75◦ , 90◦ ]. 7 Performance Evaluation We evaluate the performance of each solution in the realistic environments. The experimental facilities are the same as those used in the observations. The execution time, coverage ratio, and misreading ratio are used for performance metrics. In the experiments, each book is attached with an RFID tag, and the tag ID is 96 bits. The books are randomly deployed in three boxes and the distribution of the tag IDs are unknown. Each box is placed on a tablet chair with a height of 0.5m, as shown in Fig. 6. PID uses a 3D camera, while PIA does not. The antenna is deployed on the smart car, which is controlled by the program and can rotate with the antenna flexibly. The antenna faces towards the tags to be identified. The specified area here is the center box, which is the target box, while the other two boxes are interference boxes. The distance between the target box and the antenna is d. The minimum distance between the interference box and the target box is l. s and u respectively represent the number of target tags (in target box) and the number of interference tags (in interference boxes). We verify the values of the parameters d, l, s, u to evaluate the performance of each solution. We set d = 1m, l = 1m, s = 80, u = 70 by default. Smart Car Kinect (3D Camera) Antenna Identifying the tags (a) PID Smart Car Identifying the tags Antenna (b) PIA Fig. 6. System prototypes work in the realistic environments 7.1 Upper bound of α As mentioned in section 2.2, when the distance d, the number of tags n are fixed, we can determine the value of α. In table 1, we give the upper bound of α under different conditions. We set α = 60% for the following experiments by default. Table 1. Upper bound of α ❍ n ❍❍❍❍ d (m) 0.5 1.0 1.5 40 100% 100% 90% 80 95% 85% 65% 120 89% 81% 63% 7.2 Coverage Ratio ρ Constraint We first investigate the coverage ratio ρ of each solution, as shown in Fig. 7. We can observe that scanning with the minimum power (MinPw) can not achieve the requirement of coverage ratio (α = 60%). Because the power is too small to activate the majority of the tags. When we identify the tags with the maximum