计算机科学与技术（参考文献）Continuous Scanning with Mobile Reader in RFID Systems - an Experimental Study

Continuous Scanning with Mobile Reader in RFID Systems:an Experimental Study Lei Xiet,Qun Lit,Xi Chent,Sanglu Lut,and Daoxu Chent tState Key Laboratory of Novel Software Technology,Nanjing University,China +College of William and Mary,Williamsburg,VA,USA Ixie @nju.edu.cn,liqun @cs.wm.edu,hawkxc@163.com,(sanglu,cdx@nju.edu.cn ABSTRACT of tags in a realistic scenario is much longer than the time In this paper,we show the first comprehensive experimen- computed for free space,as shown in our experiments.In ad- tal study on mobile RFID reading performance based on dition,RFID readers have a wide range of power selections a relatively large number of tags.By making a number e.g.,the Alien-9900 reader has a maximum power 30.7dBm of observations regarding the tag reading performance,we which is 30 times larger than the minimum power 15.7dBm. build a model to depict how various parameters affect the There is no guideline,however,in selecting a suitable power. reading performance.Through our model,we have designed Therefore,we aim to design an efficient solution to contin- very efficient algorithms to maximize the time-efficiency and uous scanning problem for a mobile RFID reader based on energy-efficiency by adjusting the reader's power and mov- experimental study ing speed.Our experiments show that our algorithms can Although there have been some experimental studies on reduce the total scanning time by 50%and the total energy reading performance in a stationary RFID system [4,1,7, consumption by 83%compared to the prior solutions. the previous studies have the following limitations.First, previous experiments were usually conducted in a small s- Categories and Subject Descriptors cale (fewer than 20 tags),which does not capture the com- plication for a large number of tags.Second,previous work C.2.1 [Network Architecture and Design:Wireless Com- has been focused on reading performance in a close to free munication space scenario.In reality,path loss,multi-path effect and mutual interference are common and have a big impact to R- Keywords FID reading process.Third,previous work mainly examined how factors such as distance,coding scheme and frequency RFID;Realistic Settings;Algorithm Design;Experimental affect reading performance.Very important factors,i.e.,the Study:Model reader's power and tag density,were neglected.Therefore, the previous work does not give a model for RFID reading 1.INTRODUCTION process in a realistic and large scale setting;in particular,it Mobile RFID reading performance is critical to a num- does not include the power and tag density.Indeed,before ber of applications that rely on mobile readers.Scanning we started our work,there was no realistic model which can books in a library or a bookstore,tracking merchandises in guide us in designing an efficient tag identification solution a store,all require a mobile reader to be used for continu- in our setting. ous scanning over the tags attached to the physical goods We have,thus,conducted comprehensive measurements and assets.The mobile reader moves continuously to scan a over a large number of tags in realistic settings by varying large number of tags effectively compensating for its limited various parameters.Surprisingly,we have a few important reading range.In those types of mobile reader systems,two new findings from the experiments.For example,we have performance metrics are highly pertinent:time efficiency to found that the probabilistic backscattering is a ubiquitous reduce the total scanning time,and energy efficiency to re- phenomenon of the RFID system in realistic settings,i.e., duce the total power consumption.Unfortunately,there is during every query cycle each tag randomly responds with no realistic model to characterize the performance for mo- a certain probability,which has an important effect on the bile RFID reading for a large scale setting.The factors that reading performance.This observation is contrary to the affect the mobile reading performance are very complicat- previous belief that tags respond to a reader with either ed.For example,the actual scanning time for a number probability 1 or 0.We have also found it is not wise to blind- ly increase the reader's power for tag identification,which can degrade the overall performance including the effective Permission to make digital or hard copies of all or part of this work for personal or throughput and energy consumption.These findings are es- classroom use is granted without fee provided that copies are not made or distributed sential to improving reading performance for a mobile RFID for profit or commercial advantage and that copies bear this notice and the full cita system.Most importantly,we can(1)model the patterns tion on the first page.Copyrights for components of this work owned by others than of reading a large number of tags by giving a probabilis- ACM must be honored.Abstracting with credit is permitted.To copy otherwise,or re- tic model to capture the major and minor detection region, publish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.Request permissions from permissions@acmorg. and(2)model how the reading power and tag density affect MobiHoc'13,July 29-August 1,2013.Bangalore,India the reading performance by proving an empirical mapping. Copyright2013ACM978-1-4503-2193-8/13/07S15.00

Continuous Scanning with Mobile Reader in RFID Systems: an Experimental Study Lei Xie†, Qun Li‡, Xi Chen†, Sanglu Lu†, and Daoxu Chen† †State Key Laboratory of Novel Software Technology, Nanjing University, China ‡College of William and Mary, Williamsburg, VA, USA lxie@nju.edu.cn, liqun@cs.wm.edu, hawkxc@163.com, {sanglu,cdx}@nju.edu.cn ABSTRACT In this paper, we show the first comprehensive experimen￾tal study on mobile RFID reading performance based on a relatively large number of tags. By making a number of observations regarding the tag reading performance, we build a model to depict how various parameters affect the reading performance. Through our model, we have designed very efficient algorithms to maximize the time-efficiency and energy-efficiency by adjusting the reader’s power and mov￾ing speed. Our experiments show that our algorithms can reduce the total scanning time by 50% and the total energy consumption by 83% compared to the prior solutions. Categories and Subject Descriptors C.2.1 [Network Architecture and Design]: Wireless Com￾munication Keywords RFID; Realistic Settings; Algorithm Design; Experimental Study; Model 1. INTRODUCTION Mobile RFID reading performance is critical to a num￾ber of applications that rely on mobile readers. Scanning books in a library or a bookstore, tracking merchandises in a store, all require a mobile reader to be used for continu￾ous scanning over the tags attached to the physical goods and assets. The mobile reader moves continuously to scan a large number of tags effectively compensating for its limited reading range. In those types of mobile reader systems, two performance metrics are highly pertinent: time efficiency to reduce the total scanning time, and energy efficiency to re￾duce the total power consumption. Unfortunately, there is no realistic model to characterize the performance for mo￾bile RFID reading for a large scale setting. The factors that affect the mobile reading performance are very complicat￾ed. For example, the actual scanning time for a number Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full cita￾tion on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re￾publish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. MobiHoc’13, July 29–August 1, 2013, Bangalore, India. Copyright 2013 ACM 978-1-4503-2193-8/13/07 ...$15.00. of tags in a realistic scenario is much longer than the time computed for free space, as shown in our experiments. In ad￾dition, RFID readers have a wide range of power selections, e.g., the Alien-9900 reader has a maximum power 30.7dBm, which is 30 times larger than the minimum power 15.7dBm. There is no guideline, however, in selecting a suitable power. Therefore, we aim to design an efficient solution to contin￾uous scanning problem for a mobile RFID reader based on experimental study. Although there have been some experimental studies on reading performance in a stationary RFID system [4, 1, 7], the previous studies have the following limitations. First, previous experiments were usually conducted in a small s￾cale (fewer than 20 tags), which does not capture the com￾plication for a large number of tags. Second, previous work has been focused on reading performance in a close to free space scenario. In reality, path loss, multi-path effect and mutual interference are common and have a big impact to R￾FID reading process. Third, previous work mainly examined how factors such as distance, coding scheme and frequency, affect reading performance. Very important factors, i.e., the reader’s power and tag density, were neglected. Therefore, the previous work does not give a model for RFID reading process in a realistic and large scale setting; in particular, it does not include the power and tag density. Indeed, before we started our work, there was no realistic model which can guide us in designing an efficient tag identification solution in our setting. We have, thus, conducted comprehensive measurements over a large number of tags in realistic settings by varying various parameters. Surprisingly, we have a few important new findings from the experiments. For example, we have found that the probabilistic backscattering is a ubiquitous phenomenon of the RFID system in realistic settings, i.e., during every query cycle each tag randomly responds with a certain probability, which has an important effect on the reading performance. This observation is contrary to the previous belief that tags respond to a reader with either probability 1 or 0. We have also found it is not wise to blind￾ly increase the reader’s power for tag identification, which can degrade the overall performance including the effective throughput and energy consumption. These findings are es￾sential to improving reading performance for a mobile RFID system. Most importantly, we can (1) model the patterns of reading a large number of tags by giving a probabilis￾tic model to capture the major and minor detection region, and (2) model how the reading power and tag density affect the reading performance by proving an empirical mapping

Based on the effective models,we can then design efficient al- model to depict the regularities of reading performance in gorithms,which can dramatically improve the performance. realistic settings. as shown in our real experiments. We make the following contributions in this paper.(1) 3.PROBLEM FORMULATION We are the first to conduct an extensive experimental study over a relatively large number of tags (up to 240 tags)and a We consider a typical scenario of continuous scanning in realistic settings,i.e.,using a mobile reader to identify a rather high tag density (up to 90 tags per square meter)in realistic settings.To the best of our knowledge,this is the large volume of tags deployed over a wide area.We respec- first work to propose a model for investigating how the im- tively consider a situation where the tags are continuously portant parameters including reader's power,moving speed placed with a uniform/nonuniform density,we seek to exe- and tag density jointly affect the reading performance.(2) cute continuous scanning over the tags along a certain di- This is also the first work to give a framework of optimiz- rection.The performance metrics in our consideration are ing reading performance based on experimental study.We as follows: apply our model to solve the problem of continuous scan- Time-efficiency:considering it is time-consuming to ning with mobile reader.By carefully adjusting the power identify a large volume of tags in realistic settings,the and moving speed,we design efficient algorithms to optimize overall scanning time should be as small as possible. time-efficiency and energy-efficiency.(3)We have a number of novel techniques in making our algorithms practical.For Energy-efficiency:considering the mobile reader is con- example,our tag density estimation method is extremely ventionally battery powered,e.g.,a typical battery for simple and accurate.Our algorithm extension to nonunifor- the mobile reader has a capacity of 3200mAh with out- m tag density is also effective.(4)Being compatible with put voltage 3.7v,if we scan the tags with a maximum RFID standard(with no changes to the C1G2 protocols or radiation power 36 dBm,the mobile reader can exe low-level parameters for commercial RFID readers).our so- cute continuous scanning for only 3 hours,therefore, lutions can deliver significant performance gain.Experiment the overall energy used should be as small as possible. results indicate that,while achieving the same coverage ra- Coverage ratio:due to various issues like path loss in tio,our practical solutions respectively reduce scanning time by 50%and energy consumption by 83%compared to the realistic settings,it is difficult to identify all tags with a high probability for one single scanning cycle,there prior solutions. fore,the coverage ratio,i.e.,the ratio of the number of identified tags to the total number of tags,should be guaranteed,while each tag should have a uniform 2.RELATED WORK probability to be identified. In RFID systems,a reader needs to receive data from multiple tags.These tags are unable to self-regulate their In regard to the continuous scanning,we define the scan- radio transmissions to avoid collisions.In light of this.a ning time as T,the overall energy used as E,and the cover- series of slotted ALOHA-based anti-collision protocols 19. age ratio as C.Assuming the tag density is p and the length 14,9,22],as well as tree-based anti-collision protocols [12, of the scanning area is l,then the total number of tags is 13,2,are designed to resolve collisions in RFID systems.In n =l.p,we denote the overall tag set as S.We assume that order to deal with the collision problems in multi-reader R- each tag t,S is successfully identified with probability FID systems,scheduling protocols for reader activation are of p;after the continuous scanning.The reader's antenna explored in 18,21.Recently,a number of polling-based is deployed towards the tags with a distance of d.We can protocols 10,5,23,3 are proposed,aiming to collect infor- adjust the parameters including the reader's power p and mation from RFID tags in a time/energy efficient approach. the moving speed v to improve the reading performance. Therefore,during the continuous scanning,the problem is In order to estimate the number of tags without collecting tag IDs,a number of protocols are proposed [8,11,15,6, how to efficiently set the parameters p and v such that the 17]to leverage the information gathered in slotted ALOHA following objectives can be achieved: protocol for fast estimation of the number of tags. Time-efficiency In order to verify the impact of the physical layer's un- minimize T (1) reliability,Buettner et al.4 examine the performance of subject to the C1G2 RFID system in a realistic setting.Aroor et al. 1 identify the state of the technical capability of passive E≤a energy constraint (2) UHF RFID systems using a simple,empirical,experimental Pr[C≥I≥B coverage constraint (3) approach.Jeffery et al.[7]conduct experiments in real- ∀t与∈Sp5=p coverage constraint (4)】 istic settings and find that within each reader's detection range,a large difference exists in reading performance.In Energy-efficiency: order to efficiently identify RFID tags in mobile settings, minimize E (5) Xie et al.propose a probabilistic model to set optimized parameters for mobile tag identification [20.Sheng et al. subject to develop efficient schemes for continuous scanning operations T≤Y time constraint (6) 16,aiming to utilize the information gathered in the previ- PrC≥O2B coverage constraint (7) ous scanning operations to reduce the scanning time of the succeeding ones.Being different from the previous work, Vti ES Pi=p coverage constraint (8) this paper conducts an extensive experimental study over According to the above formulation,in regard to the time- a large scale RFID deployment,and proposes an effective efficiency,the objective is to minimize the overall scanning

Based on the effective models, we can then design efficient al￾gorithms, which can dramatically improve the performance, as shown in our real experiments. We make the following contributions in this paper. (1) We are the first to conduct an extensive experimental study over a relatively large number of tags (up to 240 tags) and a rather high tag density (up to 90 tags per square meter) in realistic settings. To the best of our knowledge, this is the first work to propose a model for investigating how the im￾portant parameters including reader’s power, moving speed and tag density jointly affect the reading performance. (2) This is also the first work to give a framework of optimiz￾ing reading performance based on experimental study. We apply our model to solve the problem of continuous scan￾ning with mobile reader. By carefully adjusting the power and moving speed, we design efficient algorithms to optimize time-efficiency and energy-efficiency. (3) We have a number of novel techniques in making our algorithms practical. For example, our tag density estimation method is extremely simple and accurate. Our algorithm extension to nonunifor￾m tag density is also effective. (4) Being compatible with RFID standard (with no changes to the C1G2 protocols or low-level parameters for commercial RFID readers), our so￾lutions can deliver significant performance gain. Experiment results indicate that, while achieving the same coverage ra￾tio, our practical solutions respectively reduce scanning time by 50% and energy consumption by 83% compared to the prior solutions. 2. RELATED WORK In RFID systems, a reader needs to receive data from multiple tags. These tags are unable to self-regulate their radio transmissions to avoid collisions. In light of this, a series of slotted ALOHA-based anti-collision protocols [19, 14, 9, 22], as well as tree-based anti-collision protocols [12, 13, 2], are designed to resolve collisions in RFID systems. In order to deal with the collision problems in multi-reader R￾FID systems, scheduling protocols for reader activation are explored in [18], [21]. Recently, a number of polling-based protocols [10, 5, 23, 3] are proposed, aiming to collect infor￾mation from RFID tags in a time/energy efficient approach. In order to estimate the number of tags without collecting tag IDs, a number of protocols are proposed [8, 11, 15, 6, 17] to leverage the information gathered in slotted ALOHA protocol for fast estimation of the number of tags. In order to verify the impact of the physical layer’s un￾reliability, Buettner et al. [4] examine the performance of the C1G2 RFID system in a realistic setting. Aroor et al. [1] identify the state of the technical capability of passive UHF RFID systems using a simple, empirical, experimental approach. Jeffery et al. [7] conduct experiments in real￾istic settings and find that within each reader’s detection range, a large difference exists in reading performance. In order to efficiently identify RFID tags in mobile settings, Xie et al. propose a probabilistic model to set optimized parameters for mobile tag identification [20]. Sheng et al. develop efficient schemes for continuous scanning operations [16], aiming to utilize the information gathered in the previ￾ous scanning operations to reduce the scanning time of the succeeding ones. Being different from the previous work, this paper conducts an extensive experimental study over a large scale RFID deployment, and proposes an effective model to depict the regularities of reading performance in realistic settings. 3. PROBLEM FORMULATION We consider a typical scenario of continuous scanning in realistic settings, i.e., using a mobile reader to identify a large volume of tags deployed over a wide area. We respec￾tively consider a situation where the tags are continuously placed with a uniform/nonuniform density, we seek to exe￾cute continuous scanning over the tags along a certain di￾rection. The performance metrics in our consideration are as follows: • Time-efficiency: considering it is time-consuming to identify a large volume of tags in realistic settings, the overall scanning time should be as small as possible. • Energy-efficiency: considering the mobile reader is con￾ventionally battery powered, e.g., a typical battery for the mobile reader has a capacity of 3200mAh with out￾put voltage 3.7v, if we scan the tags with a maximum radiation power 36 dBm, the mobile reader can exe￾cute continuous scanning for only 3 hours, therefore, the overall energy used should be as small as possible. • Coverage ratio: due to various issues like path loss in realistic settings, it is difficult to identify all tags with a high probability for one single scanning cycle, there￾fore, the coverage ratio, i.e., the ratio of the number of identified tags to the total number of tags, should be guaranteed, while each tag should have a uniform probability to be identified. In regard to the continuous scanning, we define the scan￾ning time as T , the overall energy used as E, and the cover￾age ratio as C. Assuming the tag density is ρ and the length of the scanning area is l, then the total number of tags is n = l·ρ, we denote the overall tag set as S. We assume that each tag tj ∈ S is successfully identified with probability of pj after the continuous scanning. The reader’s antenna is deployed towards the tags with a distance of d. We can adjust the parameters including the reader’s power pw and the moving speed v to improve the reading performance. Therefore, during the continuous scanning, the problem is how to efficiently set the parameters pw and v such that the following objectives can be achieved: Time-efficiency: minimize T (1) subject to E ≤ α energy constraint (2) P r[C ≥ θ] ≥ β coverage constraint (3) ∀tj ∈ S pj = p coverage constraint (4) Energy-efficiency: minimize E (5) subject to T ≤ γ time constraint (6) P r[C ≥ θ] ≥ β coverage constraint (7) ∀tj ∈ S pj = p coverage constraint (8) According to the above formulation, in regard to the time￾efficiency, the objective is to minimize the overall scanning

time T while the energy constraint and the coverage con- tained results.In order to keep the statistical characteristics. straint should be satisfied.The energy constraint requires all results are the averaged results of 500 independent trials. the energy used should be no greater than a certain threshold We finally summarize these original findings in 12 figures.In a.In regard to the coverage constraint,due to the random the following experiments,we vary the tag density,p,from factors in the anti-collision scheme and the communication 10 to 40 tags/grid,while adjusting the reader's power from environment,the coverage ratio C cannot guarantee to be 20.7dBm to 30.7dBm for performance evaluation.Unless deterministically equal or greater than a threshold 0,hence otherwise specified,by default we fix the reader towards the we use the probabilistic approach to denote the requiremen- center of the bookshelf,set the reader's power to 30.7 dBm, t.The probability for the coverage ratio C to be equal or and repetitively scan the tags for 50 query cycles. greater than 0 should be no less than B.Moreover,there could exist multiple feasible solutions to guarantee the cov- 4.1 Experimental findings erage constraint,in some of the solutions the tags are de- tected with nonuniform probabilities.In fairness,we require that each tag t;in the set S should be detected with a uni- 4.1.1 Probabilistic backscattering form probability p,i.e.,the detection probability p;should During the query cycles,each tag responds to the reader be equal to p.Similarly,in regard to the energy-efficiency, with a certain probability between 0 and 1.We uniform- the objective is to minimize the overall energy E,while the ly deploy 96 tags in the bookshelf with 8 tags in each grid time constraint and the coverage constraint should be sat- The grids on the left/middle/right side are respectively num- isfied.The time constraint requires that the scanning time bered(1,2,3)/(4,5,6,7,8,9)/(10,11,12).In Fig..1(a),were should be no greater than a certain threshold,y. spectively compute the read ratios of each tag in the 12 grids,i.e.,the ratio of successful number of responses to the expected number of responses for each tag,and illus- DERIVING A MODEL FROM REALIS- trate them in histogram grouped by grid ID.We note that TIC EXPERIMENTS the tags respond to the reader with various probabilities be- In order to understand how the reader's power and tag tween 0 and 1,although basically no parameters are changed density affect the reading performance,while dealing with during the repetitive scanning.This observation is contrary issues like the path loss,energy absorption,and mutual in- to the popular idea that each tag either responds thorough- terference,we illustrate several original findings from our ly or does not respond at all.We think this is probably realistic experiments.In our experiments,we use the Alien- due to the randomness in the backscattering factors,like 9900 reader and Alien-9611 linear antenna with a directional the power scattering,multi-path propagation.Furthermore gain of 6dB.The 3dB beamwidth is 40 degrees.The RFID we vary the reader's power,p,from 22.7 dBm to 30.7dB- tags used are Alien 9640 general-purpose tags which support m and obtain the probability density functions for the read the EPC C1G2 standards.We attach the RFID tags onto ratio.According to Fig.1(b),we note that as the reader's the books which are placed in a large bookshelf.Each tag is power varies,the distribution of the read ratio also varies. attached onto a distinct book with a unique ID.The book- The above observation further implies that,due to the prob shelf is composed of 12 grids with 4 columns and 3 rows, abilistic backscattering,multiple query cycles are essential the height and width of each grid are respectively 60cm and to successfully identify a typical tag in the tag set,which may cause massive duplicated readings over other tags in 75cm.The RFID reader is statically deployed by facing its antenna towards the book shelf.Note that in order to set an the scanning area. appropriate value for the distance between the reader and the bookshelf.it is difficult to directly derive the optimal 4.1.2 Major vs minor detection region distance from geometry according to the beamwidth,due to Within each reader's detection range,there are two dis- issues like the multipath effect.Therefore,we vary the dis- tinct regions:the major detection region where the tags can tance from 0.5m to 3m and measure the number of effectively be identified with high probability,and the minor detection identified tags while scanning 160 tags uniformly distributed region where the tags can be identified with low probabili- on the shelf.We find that the reader achieves the maximum ty.We uniformly deploy the tags in a row with 4 grids in coverage when the distance is 1.5m.Thus,we set the dis- the bookshelf,where the tag IDs are sequentially numbered tance to 1.5m to guarantee the reading performance.This from left to right.The reader's power is set to 30.7dBm setting is close to a typical noisy condition,which is distinct Fig.1(c)-Fig.1(f)show the histogram of each tag's read ratio from the free space condition,since the issues in the realistic in the order of tag ID,while varying the tag density,i.e., applications like the path loss,multi-path effect and energy the number of tags per grid.In order to see the two distinct absorption all exist.Considering that we deploy a relatively regions,we use red window to depict the boundary of the large number of tags (up to 240 tags)and a rather high tag major detection region.We observe that within each read- density(up to 90 tags per square meter)in realistic settings, er's detection range,the major detection region is the area the experimental findings from the high tag density deploy- directly in front of the reader,giving high detection proba- ment can be highly scalable and generalized to rather large bility,and the minor detection region extends from the end scale settings. of the major detection region to the edge of the detection On the whole,it took us over 300 hours to conduct an range,where the read ratio drops off to zero at the end of extensive experimental study of up to 240 tags in realistic the detection range.As the tag density increases,the major settings.In order to sufficiently understand how the pa- detection region gradually shrinks.Note that due to issues rameters separately/jointly affect the actual reading perfor- like the multipath effect and energy absorption in realistic mance,we conduct up to 100 various experiments,carrying settings,it is difficult to directly derive the detail parame- out lots of experimental comparisons and analysis on the ob- ters of the major/minor detection region from geometrical

time T while the energy constraint and the coverage con￾straint should be satisfied. The energy constraint requires the energy used should be no greater than a certain threshold α. In regard to the coverage constraint, due to the random factors in the anti-collision scheme and the communication environment, the coverage ratio C cannot guarantee to be deterministically equal or greater than a threshold θ, hence we use the probabilistic approach to denote the requiremen￾t. The probability for the coverage ratio C to be equal or greater than θ should be no less than β. Moreover, there could exist multiple feasible solutions to guarantee the cov￾erage constraint, in some of the solutions the tags are de￾tected with nonuniform probabilities. In fairness, we require that each tag tj in the set S should be detected with a uni￾form probability p, i.e., the detection probability pj should be equal to p. Similarly, in regard to the energy-efficiency, the objective is to minimize the overall energy E, while the time constraint and the coverage constraint should be sat￾isfied. The time constraint requires that the scanning time should be no greater than a certain threshold, γ. 4. DERIVING A MODEL FROM REALIS￾TIC EXPERIMENTS In order to understand how the reader’s power and tag density affect the reading performance, while dealing with issues like the path loss, energy absorption, and mutual in￾terference, we illustrate several original findings from our realistic experiments. In our experiments, we use the Alien- 9900 reader and Alien-9611 linear antenna with a directional gain of 6dB. The 3dB beamwidth is 40 degrees. The RFID tags used are Alien 9640 general-purpose tags which support the EPC C1G2 standards. We attach the RFID tags onto the books which are placed in a large bookshelf. Each tag is attached onto a distinct book with a unique ID. The book￾shelf is composed of 12 grids with 4 columns and 3 rows, the height and width of each grid are respectively 60cm and 75cm. The RFID reader is statically deployed by facing its antenna towards the book shelf. Note that in order to set an appropriate value for the distance between the reader and the bookshelf, it is difficult to directly derive the optimal distance from geometry according to the beamwidth, due to issues like the multipath effect. Therefore, we vary the dis￾tance from 0.5m to 3m and measure the number of effectively identified tags while scanning 160 tags uniformly distributed on the shelf. We find that the reader achieves the maximum coverage when the distance is 1.5m. Thus, we set the dis￾tance to 1.5m to guarantee the reading performance. This setting is close to a typical noisy condition, which is distinct from the free space condition, since the issues in the realistic applications like the path loss, multi-path effect and energy absorption all exist. Considering that we deploy a relatively large number of tags (up to 240 tags) and a rather high tag density (up to 90 tags per square meter) in realistic settings, the experimental findings from the high tag density deploy￾ment can be highly scalable and generalized to rather large scale settings. On the whole, it took us over 300 hours to conduct an extensive experimental study of up to 240 tags in realistic settings. In order to sufficiently understand how the pa￾rameters separately/jointly affect the actual reading perfor￾mance, we conduct up to 100 various experiments, carrying out lots of experimental comparisons and analysis on the ob￾tained results. In order to keep the statistical characteristics, all results are the averaged results of 500 independent trials. We finally summarize these original findings in 12 figures. In the following experiments, we vary the tag density, ρ, from 10 to 40 tags/grid, while adjusting the reader’s power from 20.7dBm to 30.7dBm for performance evaluation. Unless otherwise specified, by default we fix the reader towards the center of the bookshelf, set the reader’s power to 30.7 dBm, and repetitively scan the tags for 50 query cycles. 4.1 Experimental findings 4.1.1 Probabilistic backscattering During the query cycles, each tag responds to the reader with a certain probability between 0 and 1. We uniform￾ly deploy 96 tags in the bookshelf with 8 tags in each grid. The grids on the left/middle/right side are respectively num￾bered (1,2,3)/(4,5,6,7,8,9)/(10,11,12). In Fig.1(a), we re￾spectively compute the read ratios of each tag in the 12 grids, i.e., the ratio of successful number of responses to the expected number of responses for each tag, and illus￾trate them in histogram grouped by grid ID. We note that the tags respond to the reader with various probabilities be￾tween 0 and 1, although basically no parameters are changed during the repetitive scanning. This observation is contrary to the popular idea that each tag either responds thorough￾ly or does not respond at all. We think this is probably due to the randomness in the backscattering factors, like the power scattering, multi-path propagation. Furthermore, we vary the reader’s power, pw, from 22.7 dBm to 30.7dB￾m and obtain the probability density functions for the read ratio. According to Fig.1(b), we note that as the reader’s power varies, the distribution of the read ratio also varies. The above observation further implies that, due to the prob￾abilistic backscattering, multiple query cycles are essential to successfully identify a typical tag in the tag set, which may cause massive duplicated readings over other tags in the scanning area. 4.1.2 Major vs minor detection region Within each reader’s detection range, there are two dis￾tinct regions: the major detection region where the tags can be identified with high probability, and the minor detection region where the tags can be identified with low probabili￾ty. We uniformly deploy the tags in a row with 4 grids in the bookshelf, where the tag IDs are sequentially numbered from left to right. The reader’s power is set to 30.7dBm. Fig.1(c)-Fig.1(f) show the histogram of each tag’s read ratio in the order of tag ID, while varying the tag density, i.e., the number of tags per grid. In order to see the two distinct regions, we use red window to depict the boundary of the major detection region. We observe that within each read￾er’s detection range, the major detection region is the area directly in front of the reader, giving high detection proba￾bility, and the minor detection region extends from the end of the major detection region to the edge of the detection range, where the read ratio drops off to zero at the end of the detection range. As the tag density increases, the major detection region gradually shrinks. Note that due to issues like the multipath effect and energy absorption in realistic settings, it is difficult to directly derive the detail parame￾ters of the major/minor detection region from geometrical

0.8 w.30.7d8n 0.6 0.6 0.4 0 0.2 2 5 8910111 02 04 0 10 30 40 0 60 d ratio (a)Histogram of read ratio (b)Probability density (c)Histogram of read ratio (d)Histogram of read ratio functions (p=10) （(p=20) *p=10 =010 目-p=2 20 0.8 -30 ◆040 0.e 0 04 02 0 20 40 80 100 12 50 ag0700 150 22 Peader pr 30 hieonne (e)Histogram of read ratio(f)Histogram of read ratio(g)Width of major detection(h)The detection probability (p=30) (p=40) region in major detection region 8000 .10 10 P40 P40 4L 30 号2000 10 2 eser p (dom 20 Re3o9e周 30 22 ear 30 22 Reow( (i)Overall number of tags (j)Query cycle duration (k)The number of identified (1)Throughput identified after 50 query cycles tags per cycle Figure 1:Observations from the realistic experiments principles.since they are also related to other parameters per cycle,causing the variation of the throughput.Accord- like the tag density. ing to the theoretical analysis in the ideal situation,if the frame size is optimally selected,the expected number of s- 4.1.3 Marginal decreasing effect lots as well as the query cycle duration should be linearly As the reader's power is increasing,the eract read efficien- increasing with the number of identified tags per cycle.How- cy including the scanning range,the detection probability,as ever,in realistic settings that doesn't follow at all.Fig.1(j) well as the number of identified tags,is not increasing equal- and Fig.1(k)respectively show the value of cycle duration ly with the power.In Fig.1(g)-1(i),we respectively measure Te and the number of identified tags per cycle ne while vary- the width of the major detection region,the average de- ing the reader's power.Note that the standard deviation of tection probability (i.e.,read ratio)in the major detection Te is much larger than ne,which is mainly due to the ran- region,as well as the overall number of identified tags,while domness in the anti-collision scheme.As the reader's power varying the reader's power from 20.7dBm to 30.7dBm.All increases,the values of re and ne are both increasing,how- of the above three variables are increasing while the read- ever,at different rates.Therefore,the ratio of ne to Te,i.e., er's power increases.However,as the power is increased by the throughput,is also varying. 2dBm (i.e,1.58 times in watt),they mainly increase with Fig.1(1)shows the throughput variation with 4 differen- a much smaller speed on average.This observation implies t tag densities.We find that in all cases the throughput that the read efficiency cannot be sufficiently enhanced by achieves the peak value when the reader's power is set to purely increasing the reader's power. an appropriate value between the minimum and maximum power.The reason is as follows:When the reader's power is 4.1.4 Query cycle duration vs the number of identi- set to a small value,the number of activated tags is small. fied tags per cycle then due to the fairly large inter-query cycle overhead,the As the reader's power increases,the query cycle duration throughput is fairly small.As the reader's power increases, does not increase linearly with the number of identified tags more tags are involved in the query cycle,the inter-query cy-

1 2 3 4 5 6 7 8 9 10 11 12 0 0.2 0.4 0.6 0.8 1 Grid ID Read ratio (a) Histogram of read ratio 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 Read ratio Probability pw=22.7dBm pw=24.7dBm pw=26.7dBm pw=28.7dBm pw=30.7dBm (b) Probability density functions 0 10 20 30 40 0 0.2 0.4 0.6 0.8 1 Tag ID Read ratio (c) Histogram of read ratio (ρ = 10) 0 20 40 60 80 0 0.2 0.4 0.6 0.8 1 Tag ID Read ratio (d) Histogram of read ratio (ρ = 20) 0 20 40 60 80 100 120 0 0.2 0.4 0.6 0.8 1 Tag ID Read ratio (e) Histogram of read ratio (ρ = 30) 0 50 100 150 0 0.2 0.4 0.6 0.8 1 Tag ID Read ratio (f) Histogram of read ratio (ρ = 40) 22 24 26 28 30 0 0.5 1 1.5 2 2.5 3 Reader power pw (dBm) Width of the scanning window (m) ρ=10 ρ=20 ρ=30 ρ=40 (g) Width of major detection region 22 24 26 28 30 0 0.2 0.4 0.6 0.8 1 Reader power pw (dBm) The detection probability ρ=10 ρ=20 ρ=30 ρ=40 (h) The detection probability in major detection region 22 24 26 28 30 0 10 20 30 40 50 60 70 Reader power pw (dBm) Overall identified tag size ρ=10 ρ=20 ρ=30 ρ=40 (i) Overall number of tags identified after 50 query cycles 20 22 24 26 28 30 0 2000 4000 6000 8000 Reader power pw(dBm) Query cycle duration(ms) ρ=10 ρ=20 ρ=30 ρ=40 (j) Query cycle duration 20 22 24 26 28 30 0 10 20 30 40 50 60 70 Reader power pw(dBm) Identified tag size per cycle ρ=10 ρ=20 ρ=30 ρ=40 (k) The number of identified tags per cycle 22 24 26 28 30 0 5 10 15 20 25 30 35 Reader power pw (dBm) Throughput(tags/second) ρ=10 ρ=20 ρ=30 ρ=40 (l) Throughput Figure 1: Observations from the realistic experiments principles, since they are also related to other parameters like the tag density. 4.1.3 Marginal decreasing effect As the reader’s power is increasing, the exact read efficien￾cy including the scanning range, the detection probability, as well as the number of identified tags, is not increasing equal￾ly with the power. In Fig.1(g)-1(i), we respectively measure the width of the major detection region, the average de￾tection probability (i.e., read ratio) in the major detection region, as well as the overall number of identified tags, while varying the reader’s power from 20.7dBm to 30.7dBm. All of the above three variables are increasing while the read￾er’s power increases. However, as the power is increased by 2dBm (i.e, 1.58 times in watt), they mainly increase with a much smaller speed on average. This observation implies that the read efficiency cannot be sufficiently enhanced by purely increasing the reader’s power. 4.1.4 Query cycle duration vs the number of identi- fied tags per cycle As the reader’s power increases, the query cycle duration does not increase linearly with the number of identified tags per cycle, causing the variation of the throughput. Accord￾ing to the theoretical analysis in the ideal situation, if the frame size is optimally selected, the expected number of s￾lots as well as the query cycle duration should be linearly increasing with the number of identified tags per cycle. How￾ever, in realistic settings that doesn’t follow at all. Fig.1(j) and Fig.1(k) respectively show the value of cycle duration τc and the number of identified tags per cycle nc while vary￾ing the reader’s power. Note that the standard deviation of τc is much larger than nc, which is mainly due to the ran￾domness in the anti-collision scheme. As the reader’s power increases, the values of τc and nc are both increasing, how￾ever, at different rates. Therefore, the ratio of nc to τc, i.e., the throughput, is also varying. Fig.1(l) shows the throughput variation with 4 differen￾t tag densities. We find that in all cases the throughput achieves the peak value when the reader’s power is set to an appropriate value between the minimum and maximum power. The reason is as follows: When the reader’s power is set to a small value, the number of activated tags is small, then due to the fairly large inter-query cycle overhead, the throughput is fairly small. As the reader’s power increases, more tags are involved in the query cycle, the inter-query cy-

cle overhead is sufficiently amortized,thus the throughput f(r)and gp().Fig.2 shows a schematic diagram of is gradually increased.When the reader's power increases the average value and variance of the incident power p() to a fairly large value,the number of collisions in the query in the one-dimensional space.Note that conventionally the cycle is greatly increased,resulting in a large value for the incident power achieves the maximum value in the center of cycle duration,thus the throughput is further decreased the read zone,and gradually decreases towards the edges This observation implies that it is neither time-efficient nor Meanwhile,in regard to multiple tags deployed in the plane, energy-efficient to blindly increase the reader's power,an the incident power is also affected by tag density and multi- optimal value for the reader's power should be determined. path effect. The above experiment results and observations are ob- Power in dBm tained from the static situation where the reader is stati- cally deployed.In the mobile situation where the reader is continuously moving,since the moving speed cannot be too large due to the large number of tags to be identified,all threshold the above properties should be preserved.In order to verify this statement,we conduct experiments in mobile situations while varying the moving speed from 0.3m/s to 3m/s.We find that all the obtained results,including the width of ma- jor detection region,the detection probability,and the query 0 cycle duration are very close to the static situation.Be- Minor Detection Minor Detection Region sides,these experiment results are currently obtained from Region the settings constructed by the Alien reader and antennas, since the Alien reader and antennas are designed and manu- factured according to industrial standard,these results can Figure 2:The average value and variance of the inci- be applicable to other kinds of commercial readers conform- dent power in the one-dimensional space:a schemat- ing to the standards.Therefore,it is feasible to apply these ic diagram parameters to the continuous scanning algorithm. In regard to an arbitrary tag in the row,the tag can be successfully identified if and only if the incident power is 4.2 Model above the tag's sensitivity threshold t.Due to the fluctua- Based on the above findings,it is essential to build a model tion of the incident power,the tag is successfully identified to effectively depict the regularities in reading performance. with some probability,i.e.,Prlp(r)>t].In regard to a po- We first propose a model for probabilistic backscattering, sition in the effective scanning region,note that once the and then a model of the effective scanning window to eval- average value is relatively larger than the threshold t,as the uate the reading performance over multiple tags. variance is usually relatively small,the detection probability Prlp()>t will be close to 1:similarly,once the average 4.2.1 Probabilistic backscattering value is relatively smaller than the threshold t,the detection Suppose an arbitrary tag is separated from the reader at a probability Prlp()>t]will be close to 0.This property distance of d.In order for the tag to successfully backscatter divides the scanning region into two distinct regions,i.e., the ID message,the reader needs to send a continuous wave the major detection region and the minor detection region. to activate the tag.As the tag has a sensitivity threshold t,which is the minimum power required to activate the tag, 4.2.2 Effective scanning window over multiple tags the incident power to the tag's antenna should be larger As we have observed,the reader's effective scanning re- than t.It is known that the power budget of conventional gion can be divided into a major detection region as well RFID systems is forward-link limited,which implies that as a minor detection region.In the major detection region well-designed passive RFID systems are always limited by most tags can be detected with a probability close to 100% the tag's sensitivity.Therefore,as long as the reader's power As the tag density increases,the diffused power cannot guar- p is large enough to activate the tag,the reader is able antee to activate all tags in the major detection region,each to resolve the backscattered signal from the tag.We have tag has a probability to be detected in a random approach. conducted experiments to evaluate the threshold t.We find Therefore,we can use the average detection probability to that the value of t basically remains unchanged among a depict the reading performance in this region.The minor certain type of tags. detection region is extending from the end of the major de- In the reader's read zone,i.e,the region in which the inci- tection region to the edge of the effective range,with the dent power exceeds the threshold t,it is found that the range detection probability quickly drops off to 0.Based on the is longest along the center and falls off towards the edges above analysis,we use a trapezoidal curve to denote the ex- In regard to a plane at a fixed distance from the reader pected detection probability of tags in the scanning region the incident power varies from the center towards the edges. as illustrated in Fig.3.In fact,due to the narrow width of Besides,the values of incident power has variances since the the minor detection region,the average probability for a tag continuous wave issued from the reader has fuctuations in to be detected in this region can be negligible.Therefore, terms of power.Therefore,assume the reader's power is p, in consideration of the actual reading performance,we only in regard to a two dimensional plane at a distance of d from need to focus on the major detection region.In the rest of the reader,we respectively use fp.d(r,y)and gpd(,y)to this paper,we use the term effective scanning window to denote the average value and the variance of the incident denote the major detection region.We use w and p'to de- power in the coordinate (r,y).In the settings where the note the width and the average detection probability of the tags are deployed in a row,we respectively simplify them to effective scanning window,respectively

cle overhead is sufficiently amortized, thus the throughput is gradually increased. When the reader’s power increases to a fairly large value, the number of collisions in the query cycle is greatly increased, resulting in a large value for the cycle duration, thus the throughput is further decreased. This observation implies that it is neither time-efficient nor energy-efficient to blindly increase the reader’s power, an optimal value for the reader’s power should be determined. The above experiment results and observations are ob￾tained from the static situation where the reader is stati￾cally deployed. In the mobile situation where the reader is continuously moving, since the moving speed cannot be too large due to the large number of tags to be identified, all the above properties should be preserved. In order to verify this statement, we conduct experiments in mobile situations while varying the moving speed from 0.3m/s to 3m/s. We find that all the obtained results, including the width of ma￾jor detection region, the detection probability, and the query cycle duration are very close to the static situation. Be￾sides, these experiment results are currently obtained from the settings constructed by the Alien reader and antennas, since the Alien reader and antennas are designed and manu￾factured according to industrial standard, these results can be applicable to other kinds of commercial readers conform￾ing to the standards. Therefore, it is feasible to apply these parameters to the continuous scanning algorithm. 4.2 Model Based on the above findings, it is essential to build a model to effectively depict the regularities in reading performance. We first propose a model for probabilistic backscattering, and then a model of the effective scanning window to eval￾uate the reading performance over multiple tags. 4.2.1 Probabilistic backscattering Suppose an arbitrary tag is separated from the reader at a distance of d. In order for the tag to successfully backscatter the ID message, the reader needs to send a continuous wave to activate the tag. As the tag has a sensitivity threshold t, which is the minimum power required to activate the tag, the incident power to the tag’s antenna should be larger than t. It is known that the power budget of conventional RFID systems is forward-link limited, which implies that well-designed passive RFID systems are always limited by the tag’s sensitivity. Therefore, as long as the reader’s power pw is large enough to activate the tag, the reader is able to resolve the backscattered signal from the tag. We have conducted experiments to evaluate the threshold t. We find that the value of t basically remains unchanged among a certain type of tags. In the reader’s read zone, i.e, the region in which the inci￾dent power exceeds the threshold t, it is found that the range is longest along the center and falls off towards the edges. In regard to a plane at a fixed distance from the reader, the incident power varies from the center towards the edges. Besides, the values of incident power has variances since the continuous wave issued from the reader has fluctuations in terms of power. Therefore, assume the reader’s power is pw, in regard to a two dimensional plane at a distance of d from the reader, we respectively use fpw,d(x, y) and gpw,d(x, y) to denote the average value and the variance of the incident power in the coordinate (x, y). In the settings where the tags are deployed in a row, we respectively simplify them to fpw,d(x) and gpw,d(x). Fig.2 shows a schematic diagram of the average value and variance of the incident power p w(x) in the one-dimensional space. Note that conventionally the incident power achieves the maximum value in the center of the read zone, and gradually decreases towards the edges. Meanwhile, in regard to multiple tags deployed in the plane, the incident power is also affected by tag density and multi￾path effect. O x Minor Detection Major Detection Region Region Minor Detection Region Figure 2: The average value and variance of the inci￾dent power in the one-dimensional space: a schemat￾ic diagram In regard to an arbitrary tag in the row, the tag can be successfully identified if and only if the incident power is above the tag’s sensitivity threshold t. Due to the fluctua￾tion of the incident power, the tag is successfully identified with some probability, i.e., P r[p w(x) ≥ t]. In regard to a po￾sition x in the effective scanning region, note that once the average value is relatively larger than the threshold t, as the variance is usually relatively small, the detection probability P r[p w(x) ≥ t] will be close to 1; similarly, once the average value is relatively smaller than the threshold t, the detection probability P r[p w(x) ≥ t] will be close to 0. This property divides the scanning region into two distinct regions, i.e., the major detection region and the minor detection region. 4.2.2 Effective scanning window over multiple tags As we have observed, the reader’s effective scanning re￾gion can be divided into a major detection region as well as a minor detection region. In the major detection region, most tags can be detected with a probability close to 100%. As the tag density increases, the diffused power cannot guar￾antee to activate all tags in the major detection region, each tag has a probability to be detected in a random approach. Therefore, we can use the average detection probability to depict the reading performance in this region. The minor detection region is extending from the end of the major de￾tection region to the edge of the effective range, with the detection probability quickly drops off to 0. Based on the above analysis, we use a trapezoidal curve to denote the ex￾pected detection probability of tags in the scanning region, as illustrated in Fig.3. In fact, due to the narrow width of the minor detection region, the average probability for a tag to be detected in this region can be negligible. Therefore, in consideration of the actual reading performance, we only need to focus on the major detection region. In the rest of this paper, we use the term effective scanning window to denote the major detection region. We use w and p to de￾note the width and the average detection probability of the effective scanning window, respectively.