894 EEE TRANSACTIONS ON COMPUTERS,VOL.65,NO.3.MARCH 2016 TABLE 2 Specified area Upper Bound Tu N 20 60 100 140 180 220 nu 2 4 9 17 12 the tag ID.If the tag gives response,the reader gets a non- Tag empty slot.Otherwise,it gets an empty slot.The reader Interrogation checks all the IDs in N and gets ne responses Ne.Obviously, Antenna region ne<n.When =8,the interrogation region just achieves the boundary of S.The corresponding power is the optimal Fig.7.Identify the tags in S without any auxiliary equipment. power PHowever,if,the reader reduces the power by AP and checks the verified tag IDs in Ne.If a tag does -a,we consider that the interrogation region only not give response,the reader removes it from Ne.It repeats achieves the boundary,and the coverage ratio p satisfies the above process until and gets the optimal power p>a.At this time,the reader gets the optimal power POn the contrary,if<the reader increases P by Pt=Prg+keX△Pu,ke∈Z. (3) APe and checks the unverified tag IDs in N-Ne= (ID;IDEN and IDi Ne).If the tag gives response, Here,we set AP=1dBm,which is achievable by most of the reader adds the ID into Ne.It repeats the process until the commercial readers [301.ke represents the number of and gets the optimal powerPIn the following pro- steps needed to update the reader's power,and ke is adap- cess,the reader uses p to identify the target tags. tively determined in the identification process. In PID,when the rotation angle is determined,the 6.2 Shooting Process antenna rotates to the target direction immediately.The In this process,the reader collects the tag IDs in S.The time for rotating the antenna can be neglected when com- reader's power is equal to P and we use frame slotted pared to the identification time.Based on the above analy- ALOHA (FSA)protocol to identify the tags.FSA is a pop- sis,we can estimate the lower bound of the execution time ular anti-collision protocol.In FSA,the reader first broad- Ti for PID as follows: casts a number f,which specifies the following frame size.After receiving f,each tag selects h(ID)mod f as its ∑(en)·d)+ 〉(nc·t)+e·n·t. (4 slot number,where h is a hash function.If none of the =0 tags respond in a slot,the reader closes the slot immedi- Here,n(i)is the number of tags identified from the bound- ately.If only one tag responds in a slot,the reader suc- cessfully receives the tag ID.If multiple tags respond ary in the ith step,ne(j)is the number of tags identified in S in jth step,n is the number of farget tags checked in the simultaneously,a collision occurs,and the involved tags will be acknowledged to restart in the next frame.The shooting process,t is the time for a slot,and e is the base of the natural logarithm.From Eq.(4),we can find that the similar process repeats until no tags respond in the frame. The collected IDs are considered as the farget tag IDs. numbers ko,ke,n affect Ti,which is related to the reader's power.Thus,choosing the optimal power P is essential to the problem,as shown in Algorithm 2. 6.3 Performance Analysis In order to definitely describe the boundary So,PID needs to 7 PHOTOGRAPHY BASED IDENTIFICATION WITH steadily get at least na interference tag IDs,and n satisfies n>n.That is to say,ne is the minimum number of interfer- ANGLE ROTATION ence tags needed to establish the boundary of the area S.In In PID,a 3D camera is used in the focusing process.How- the realistic environment,some tags may not be identified ever,in some environments,the 3D camera can not work by the reader steadily.If the power arriving at a tag is well(e.g.,in a dark space).Besides,considering the cost sav- approximate to the minimum power to activate it,the tag ings,it may not be used.Therefore,identifying the target may respond to the reader or keep silent at random,which fags without the auxiliary equipment is important.For this will affect the judgement of the boundary.Therefore,we problem,we propose a solution called Photography based measure the value of ne with a different tag size N]in the tag Identification with Angle rotation(PIA).It also consists realistic environments,as shown in Table 2.Based on of the Focusing Process and Shooting Process.The only differ Table 2,we can conclude that tag size N]has a little effect ence between PID and PIA is how to determine the bound- on ne,which is usually very small.Therefore,in order to ary of S.Therefore,we only describe how to find the definitely get enough tag IDs in S,we set na=15 by boundary in PIA,while ignoring the others. default,while considering the stability and time efficiency. In regard to 8,it affects the misreading ratio.The smaller 7.1 PIA the value of 8,the lower the misreading ratio,the smaller the Without the 3D camera,PIA cannot calculate any distance; execution time.However,the larger the value of 8,the larger it explores the boundary by rotating the antenna,as shown the value of coverage ratio.Considering the constraint of cov-in Fig.7.Firstly,the application appoints S and the antenna erage ratio p and time efficiency,we set 8=a.When rotates towards S.Then the reader sets its initial powerthe tag ID. If the tag gives response, the reader gets a non￾empty 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 ¼ d, the interrogation region just achieves the boundary of S. The corresponding power is the optimal power P w. However, if nc nb > d, the reader reduces the power by DPw 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  d and gets the optimal power P w. On the contrary, if nc nb < d, the reader increases Pw by DPw and checks the unverified tag IDs in Nb Nc ¼ fIDi j IDi 2 Nb and IDi 2= Ncg. If the tag gives response, the reader adds the ID into Nc. It repeats the process until nc nb  d and gets the optimal power P w. In the following pro￾cess, the reader uses P w to identify the target tags. 6.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 pop￾ular anti-collision protocol. In FSA, the reader first broad￾casts a number f, which specifies the following frame size. After receiving f, each tag selects hðIDÞ mod f as its slot number, where h is a hash function. If none of the tags respond in a slot, the reader closes the slot immedi￾ately. If only one tag responds in a slot, the reader suc￾cessfully 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. 6.3 Performance Analysis In order to definitely describe the boundary Sb, PID needs to steadily get at least n" interference tag IDs, and nb satisfies nb  n". That is to say, n" is the minimum number of interfer￾ence tags needed to establish the boundary of the area S. In the realistic environment, some tags may not be identified by the reader steadily. If the power arriving at a tag is approximate to the minimum power to activate it, the tag may respond to the reader or keep silent at random, which will affect the judgement of the boundary. Therefore, we measure the value of n" with a different tag size jNj in the realistic environments, as shown in Table 2. Based on Table 2, we can conclude that tag size jNj has a little effect on n", which is usually very small. Therefore, 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 d, it affects the misreading ratio. The smaller the value of d, the lower the misreading ratio, the smaller the execution time. However, the larger the value of d, the larger the value of coverage ratio. Considering the constraint of cov￾erage ratio r and time efficiency, we set d ¼ a. When nc nb ¼ d ¼ a, we consider that the interrogation region only achieves the boundary, and the coverage ratio r satisfies r  a. At this time, the reader gets the optimal power P w ¼ Pws þ kc DPw; kc 2 Z: (3) Here, we set DPw ¼ 1 dBm, which is achievable by most of the commercial readers [30]. kc represents the number of steps needed to update the reader’s power, and kc is adap￾tively determined in the identification process. In PID, when the rotation angle is determined, the antenna rotates to the target direction immediately. The time for rotating the antenna can be neglected when com￾pared to the identification time. Based on the above analy￾sis, we can estimate the lower bound of the execution time Tl for PID as follows: Tl ¼ i X¼kb i¼0 ðe  nbðiÞ  tÞ þ j X¼kc j¼0 ðncðjÞ  tÞ þ e  n  t: (4) Here, nbðiÞ is the number of tags identified from the bound￾ary in the ith step, ncðjÞ is the number of tags identified in Sb in jth step, n is the number of target tags checked in the shooting process, t is the time for a slot, and e is the base of the natural logarithm. From Eq. (4), we can find that the numbers kb, kc, n affect Tl, which is related to the reader’s power. Thus, choosing the optimal power P w is essential to the problem, as shown in Algorithm 2. 7 PHOTOGRAPHY BASED IDENTIFICATION WITH ANGLE ROTATION In PID, a 3D camera is used in the focusing process. How￾ever, in some environments, the 3D camera can not work well (e.g., in a dark space). Besides, considering the cost sav￾ings, it may not be used. Therefore, identifying the target tags 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 the Focusing Process and Shooting Process. The only differ￾ence between PID and PIA is how to determine the bound￾ary of S. Therefore, we only describe how to find the boundary in PIA, while ignoring the others. 7.1 PIA Without the 3D camera, PIA cannot calculate any distance; it explores the boundary by rotating the antenna, as shown in Fig. 7. Firstly, the application appoints S and the antenna rotates towards S. Then the reader sets its initial power TABLE 2 Upper Bound nu N 20 60 100 140 180 220 nu 2 4 7 9 11 12 Fig. 7. Identify the tags in S without any auxiliary equipment. 894 IEEE TRANSACTIONS ON COMPUTERS, VOL. 65, NO. 3, MARCH 2016