计算机科学与技术（参考文献）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.

Major detection region of p',w and Te are all monotonically increasing.Moreover, Probability since the value of w increases much more slowly than Te,the 100 value of m is monotonically decreasing with the value p’*100% of pw.Therefore,we reach the following conclusion:as the moving speed v decreases,the value of m is monotonically increasing,while the value of p'remains unchanged.As the reader's power p increases,the value of p'is monotonically increasing,while the value of m is monotonically decreasing. Thus the value of p should be appropriately selected to 0% optimize the performance. In regard to the coverage constraints in Eg.(3)and Eq.(4). Minor detectio Q2 Tag Position Minor detection we use the parameter p to denote the probability that a tag is region region successfully identified after the continuous scanning.Then, according to the binomial distribution,after the overall s- canning procedure,the probability for the reader to identify Figure 3:The model of effective scanning window at least 0.100%percent of the overall tags (i.e.,PrC > is computed as follows: During continuous scanning,the effective scanning win- dow is continuously moving forward with the mobile reader. PrC≥0=C·p.(1-p)n-i (11) Note that there exist overlapping areas between the con- i=「8n1 tiguous scanning windows.During the continuous scanning, Then it is essential to compute the solution of p to guarantee each tag gradually enters a minor detection region,then an PrC.≥川≥8，As∑-=fom1C%·p(1-p)m-1=3isan effective scanning window.finally exits from a minor detec- equation of higher degree,it is rather difficult to directly tion region.While within the effective scanning window, solve the variable p from the above equation. each tag has a probability to be detected for each query cy- In fact,the constraint Pr[C >0]>B is equivalent to cle.Therefore,in order to guarantee the coverage constraint, PrC <1-B.In particular,according to Hoeffding's multiple query cycles should be issued over each tag while inequality,for 0<p,it yields the bound it is within the effective scanning window.Assume that the tags are uniformly deployed along the scanning area,then the number of tags within the effective scanning window is PrC≤0≤exp(-2mp-n:02 always constant.This infers that the number of tags in- In order for Pr[C <0<1-B,it is essential to guarantee volved in a query cycle mostly remains unchanged.If the mobile reader is set to a constant power and a constant mov- ep(-2mp-n0)≤1-a. ing speed,then,after multiple query cycles,each tag has a n uniform probability to be detected.This conforms to the The solution of p can be directly solved from the above in- requirement in the coverage constraint. Suppose an arbitrary tag is expected to be queried for m equality,.that isp≥0，here0产=0+√aa.This shows -2n cycles while it is within the effective scanning window,we that,as long as the detection probability p is no less than denote the detection probability in the m query cycles as 0*for any tag,the coverage constraint is guaranteed. pi(i=1...m).Then,the probability for an arbitrary tag to be identified at least once is as follows: 5. CONTINUOUS SCANNING WITH MO- BILE READER p=1-Π1-p) (9) =1 5.1 Baseline solution As the reader's power is set to a constant value,due to the For both the uniform and nonuniform tag distribution,in uniform tag density,the probability pi(i=1...m)in the m order to effectively identify all the tags with the mobile read- query cycles should be uniform.If we use p'to denote the er,conventionally the reader's power is set to maximum and uniform detection probability,then Eq.(9)is further simpli- the moving speed is set to a constant value which is small e fied as follows: nough.This baseline solution is very straightforward,which p=1-(1-pm (10) however,is neither time-efficient nor energy-efficient since excessive power is used up and the moving speed is slowed In particular,the value of m is equal to,here T is the down.Besides,a number of tags are interrogated multiple duration in the effective scanning window,and Te is the av- times during continuous scanning,which is unnecessary as erage duration of a query cycle.Moreover,T is equal to the each tag only needs to be identified once. ratio of the window width w to the moving speed v,i.e.," hence mTherefore,in order to increase the detec- 5.2 Solution for uniform tag density tion probability p for an arbitrary tag,it is essential to (1) increase the number of query cycles m as much as possible; 5.2.1 Solution (2)increase the detection probability p'as much as possible. Without loss of generality,we first propose an optimized In Fig.1(g),Fig.1(h)and Fig.1(j),we illustrate the value of solution for the situation with uniform tag density.Consid- w,p and Te with various power,p.In regard to a fixed tag ering the objective as well as the energy/time constraint,we density,we note that as the value of p increases,the value need to figure out the optimized value of p and v such that

100% 0% Probability Q1 Q2 Q3 Qm Tag Position p *100% Major detection region width: w Minor detection region Minor detection region Figure 3: The model of effective scanning window During continuous scanning, the effective scanning win￾dow is continuously moving forward with the mobile reader. Note that there exist overlapping areas between the con￾tiguous scanning windows. During the continuous scanning, each tag gradually enters a minor detection region, then an effective scanning window, finally exits from a minor detec￾tion region. While within the effective scanning window, each tag has a probability to be detected for each query cy￾cle. Therefore, in order to guarantee the coverage constraint, multiple query cycles should be issued over each tag while it is within the effective scanning window. Assume that the tags are uniformly deployed along the scanning area, then the number of tags within the effective scanning window is always constant. This infers that the number of tags in￾volved in a query cycle mostly remains unchanged. If the mobile reader is set to a constant power and a constant mov￾ing speed, then, after multiple query cycles, each tag has a uniform probability to be detected. This conforms to the requirement in the coverage constraint. Suppose an arbitrary tag is expected to be queried for m cycles while it is within the effective scanning window, we denote the detection probability in the m query cycles as pi(i = 1...m). Then, the probability for an arbitrary tag to be identified at least once is as follows: p = 1 − m i=1 (1 − pi) (9) As the reader’s power is set to a constant value, due to the uniform tag density, the probability pi(i = 1...m) in the m query cycles should be uniform. If we use p to denote the uniform detection probability, then Eq.(9) is further simpli- fied as follows: p = 1 − (1 − p ) m (10) In particular, the value of m is equal to τw τc , here τw is the duration in the effective scanning window, and τc is the av￾erage duration of a query cycle. Moreover, τw is equal to the ratio of the window width w to the moving speed v, i.e., w v , hence m = w v·τc . Therefore, in order to increase the detec￾tion probability p for an arbitrary tag, it is essential to (1) increase the number of query cycles m as much as possible; (2) increase the detection probability p as much as possible. In Fig.1(g), Fig.1(h) and Fig.1(j), we illustrate the value of w, p and τc with various power, pw. In regard to a fixed tag density, we note that as the value of pw increases, the value of p , w and τc are all monotonically increasing. Moreover, since the value of w increases much more slowly than τc, the value of m = w v·τc is monotonically decreasing with the value of pw. Therefore, we reach the following conclusion: as the moving speed v decreases, the value of m is monotonically increasing, while the value of p remains unchanged. As the reader’s power pw increases, the value of p is monotonically increasing, while the value of m is monotonically decreasing. Thus the value of pw should be appropriately selected to optimize the performance. In regard to the coverage constraints in Eq.(3) and Eq.(4), we use the parameter p to denote the probability that a tag is successfully identified after the continuous scanning. Then, according to the binomial distribution, after the overall s￾canning procedure, the probability for the reader to identify at least θ · 100% percent of the overall tags (i.e., P r[C ≥ θ]), is computed as follows: P r[C ≥ θ] = n i=θ·n Ci n · pi · (1 − p) n−i (11) Then it is essential to compute the solution of p to guarantee P r[C ≥ θ] ≥ β. As n i=θ·n Ci n · pi · (1 − p) n−i = β is an equation of higher degree, it is rather difficult to directly solve the variable p from the above equation. In fact, the constraint P r[C ≥ θ] ≥ β is equivalent to P r[C ≤ θ] ≤ 1 − β. In particular, according to Hoeffding’s inequality, for θ ≤ p, it yields the bound P r[C ≤ θ] ≤ exp(−2 (n · p − n · θ) 2 n ). In order for P r[C ≤ θ] ≤ 1 − β, it is essential to guarantee exp(−2 (n · p − n · θ) 2 n ) ≤ 1 − β. The solution of p can be directly solved from the above in￾equality, that is p ≥ θ∗, here θ∗ = θ + ln(1−β) −2n . This shows that, as long as the detection probability p is no less than θ∗ for any tag, the coverage constraint is guaranteed. 5. CONTINUOUS SCANNING WITH MO￾BILE READER 5.1 Baseline solution For both the uniform and nonuniform tag distribution, in order to effectively identify all the tags with the mobile read￾er, conventionally the reader’s power is set to maximum and the moving speed is set to a constant value which is small e￾nough. This baseline solution is very straightforward, which however, is neither time-efficient nor energy-efficient since excessive power is used up and the moving speed is slowed down. Besides, a number of tags are interrogated multiple times during continuous scanning, which is unnecessary as each tag only needs to be identified once. 5.2 Solution for uniform tag density 5.2.1 Solution Without loss of generality, we first propose an optimized solution for the situation with uniform tag density. Consid￾ering the objective as well as the energy/time constraint, we need to figure out the optimized value of pw and v such that

the objective is achieved while the coverage constraints are p,while satisfying the time/energy constraint,we can use satisfied. the power p for the maximum value of yr or ye as the In regard to the coverage constraint,since we need to optimal parameter and compute the corresponding moving guarantee p=1-(1-p)m≥0，i.e,1-(1-p)≥0， itis equivalent to ensure As the speed v*according to Eq.(12).In this way,the optimal solution (p,v*)for time/energy efficiency can be generated value of w,p'and Te all depends on the value of p,let Therefore,in regard to various tag densities p,we can collect w(p),p'(p)and Te(p)respectively denote the mapping the performance parameters like w,p'and Te in advance, pre-compute the optimal pairs of (p,v),and store them function from pe to w,p and Te,then in a table.When dealing with an arbitrary tag density,we v=m(1-0产 ,w(pw)·ln(1-p'(pm)川 (12) can directly use the optimal pair of (p,)to achieve the Te(Pw) time/energy efficiency. then,v*is the maximum allowable moving speed to satisfy 5.2.2 Estimate the tag density the coverage constraint. According to the measured data in realistic settings,it Since the length of the scanning area is l,the overall scan- is known that the tag density p has an important effect on ning time T=,and the overall used energy E=T.p= the performance metrics.In situations where the tag densi- Therefore,considering the time-efficiency,in order to ty cannot be pre-fetched or the tag density varies along the minimize T,it is equivalent to maximize v.Then,accord- forwarding direction.it is essential to accurately estimate ing to Eq.(12),it is essential to maximize ()It the current tag density,such that the optimized parameters is known that as the value of p increases,the value of (p)can be effectively computed.Due to the proba- w.In(1-p)and Te are both monotonically increasing,thus bilistic backscattering property,it is difficult to directly es- an optimized value of p should be selected to minimize T. timate the tag density according to the observed number Considering the energy constraint E<o,the optimal value of empty/singleton/collision slots 8,11.Furthermore,cur- p can be computed according to the following formulation: rent commercial RFID readers do not expose these low-level maximize r =IIn(1-p'(pu)w(p.) data to upper-layer applications.Therefore,it is essential (13) to estimate the tag density in a more practical way Te(Pw) According to Fig.1(k),we note that if the reader's power subject to po is set to a certain value,the number of identified tags In(1-p'(p))w(pw) 1-|ln(1-0)川 per cycle ne is varying as the tag density p varies,with a (14) pe·Tc(pw) very small standard deviation.Table 1 shows further detail- s for the average values of ne.These are obtained through Considering the energy-efficiency,in order to minimize E. 50 repetitive experiments with various values of p and p. it is equivalent to minimize then according to Eq.(12),it Due to the small variance of ne,there is a very stable pat- is essential to maximize (Therefore,considering tern between ne and p that varies with p.Therefore,given the time constraintT≤，the optimal value p元can be a reference tag density Pi,we can depict the values of ne computed according to the following formulation: with various powers as a vector Vi {ni,1,ni.2,...,ni.s}, maximizey=lnl-ppul·wpa） here s is the number of power levels.Then,in regard to (15) an unknown tag density p,assume the corresponding vec- pp·Tc(Pw） tor is V=fn,n2,...,n},we can estimate the value of p subject to by comparing V with the vectors of reference tag densities. 血1-p(p)w(pe)≥-血1-rl Therefore,we propose an algorithm to estimate the tag den- (16) sity,by leveraging the k-nearest neighbor method,as shown Te(pw】 in Algorithm 1. =p-10 Pw= 20.722.724.7 26.7 28.7 30.7 10-30 p=10 9 13 22 25 28 31 0-40 P=20 10 23 30 40 51 0. P=30 2 10 20 36 59 0.4 p=40 2 4 10 17 33 57 02 Table 1:The number of identified tags per cycle 2 Peader p 24 3 22 (a)The value of yr (b)The value of yE In Algorithm 1,the similarity sim(V,Vi)is actually cal- culated by using the cosine value of the angle between the two vectors,hence the value of similarity is between 0 and 1. Figure 4:Compute the value of yr and yE with var- We use the k-nearest neighbor method to estimate the tag ious values of pu density based on k-nearest reference tag densities.The es- In regard to a certain tag density p,by enumerating the timated tag density p is computed using an inverse distance candidate values of the power p,we can compute the value weighted average with the k-nearest multivariate neighbors of yr and yE.Fig.4(a)and Fig.4(b)respectively illustrate here the distance is defined as 1-sim(V,Vi).Since the val- the value of yr and ye while varying the reader's power p. ue of ne has a rather small variance,the accuracy of the We note that there exist a maximum value of yr and yE estimated tag density can be guaranteed if the number of for each tag density.In regard to a specified tag density samplings m is fairly large.In the algorithm.the mobile

the objective is achieved while the coverage constraints are satisfied. In regard to the coverage constraint, since we need to guarantee p = 1 − (1 − p ) m ≥ θ∗, i.e., 1 − (1 − p ) w v·τc ≥ θ∗, it is equivalent to ensure v ≤ 1 | ln(1−θ∗)| · w·| ln(1−p)| τc . As the value of w, p and τc all depends on the value of pw, let w(pw), p (pw) and τc(pw) respectively denote the mapping function from pw to w, p and τc, then v∗ = 1 | ln(1 − θ∗)| · w(pw) · | ln(1 − p (pw))| τc(pw) , (12) then, v∗ is the maximum allowable moving speed to satisfy the coverage constraint. Since the length of the scanning area is l, the overall scan￾ning time T = l v , and the overall used energy E = T · pw = pw·l v . Therefore, considering the time-efficiency, in order to minimize T , it is equivalent to maximize v. Then, accord￾ing to Eq.(12), it is essential to maximize w·| ln(1−p)| τc . It is known that as the value of pw increases, the value of w·| ln(1−p )| and τc are both monotonically increasing, thus an optimized value of pw should be selected to minimize T . Considering the energy constraint E ≤ α, the optimal value p∗ w can be computed according to the following formulation: maximize yT = | ln(1 − p (pw))| · w(pw) τc(pw) (13) subject to | ln(1 − p (pw))| · w(pw) pw · τc(pw) ≥ l · | ln(1 − θ∗)| α (14) Considering the energy-efficiency, in order to minimize E, it is equivalent to minimize pw v , then according to Eq.(12), it is essential to maximize | ln(1−p)|·w pw·τc . Therefore, considering the time constraint T ≤ γ, the optimal value p∗ w can be computed according to the following formulation: maximize yE = | ln(1 − p (pw))| · w(pw) pw · τc(pw) (15) subject to | ln(1 − p (pw))| · w(pw) τc(pw) ≥ l · | ln(1 − θ∗)| γ (16) 22 24 26 28 30 0 1 2 3 4 5 6 x 10−3 Reader power pw (dBm) The value of yT ρ=10 ρ=20 ρ=30 ρ=40 (a) The value of yT 22 24 26 28 30 0 0.2 0.4 0.6 0.8 1 1.2 x 10−5 Reader power pw (dBm) The value of yE ρ=10 ρ=20 ρ=30 ρ=40 (b) The value of yE Figure 4: Compute the value of yT and yE with var￾ious values of pw In regard to a certain tag density ρ, by enumerating the candidate values of the power pw, we can compute the value of yT and yE. Fig.4(a) and Fig.4(b) respectively illustrate the value of yT and yE while varying the reader’s power pw. We note that there exist a maximum value of yT and yE for each tag density. In regard to a specified tag density ρ, while satisfying the time/energy constraint, we can use the power p∗ w for the maximum value of yT or yE as the optimal parameter and compute the corresponding moving speed v∗ according to Eq.(12). In this way, the optimal solution (p∗ w, v∗) for time/energy efficiency can be generated. Therefore, in regard to various tag densities ρ, we can collect the performance parameters like w, p and τc in advance, pre-compute the optimal pairs of (p∗ w, v∗), and store them in a table. When dealing with an arbitrary tag density, we can directly use the optimal pair of (p∗ w, v∗) to achieve the time/energy efficiency. 5.2.2 Estimate the tag density According to the measured data in realistic settings, it is known that the tag density ρ has an important effect on the performance metrics. In situations where the tag densi￾ty cannot be pre-fetched or the tag density varies along the forwarding direction, it is essential to accurately estimate the current tag density, such that the optimized parameters (p∗ w, v∗) can be effectively computed. Due to the proba￾bilistic backscattering property, it is difficult to directly es￾timate the tag density according to the observed number of empty/singleton/collision slots [8, 11]. Furthermore, cur￾rent commercial RFID readers do not expose these low-level data to upper-layer applications. Therefore, it is essential to estimate the tag density in a more practical way. According to Fig.1(k), we note that if the reader’s power pw is set to a certain value, the number of identified tags per cycle nc is varying as the tag density ρ varies, with a very small standard deviation. Table 1 shows further detail￾s for the average values of nc. These are obtained through 50 repetitive experiments with various values of ρ and pw. Due to the small variance of nc, there is a very stable pat￾tern between nc and ρ that varies with pw. Therefore, given a reference tag density ρi, we can depict the values of nc with various powers as a vector Vi = {ni,1, ni,2, ..., ni,s}, here s is the number of power levels. Then, in regard to an unknown tag density ρ, assume the corresponding vec￾tor is V = {n1, n2, ..., ns}, we can estimate the value of ρ by comparing V with the vectors of reference tag densities. Therefore, we propose an algorithm to estimate the tag den￾sity, by leveraging the k-nearest neighbor method, as shown in Algorithm 1. pw= 20.7 22.7 24.7 26.7 28.7 30.7 ρ = 10 9 13 22 25 28 31 ρ = 20 2 10 23 30 40 51 ρ = 30 1 2 10 20 36 59 ρ = 40 2 4 10 17 33 57 Table 1: The number of identified tags per cycle In Algorithm 1, the similarity sim(V,Vi) is actually cal￾culated by using the cosine value of the angle between the two vectors, hence the value of similarity is between 0 and 1. We use the k-nearest neighbor method to estimate the tag density based on k-nearest reference tag densities. The es￾timated tag density ρ is computed using an inverse distance weighted average with the k-nearest multivariate neighbors, here the distance is defined as 1 − sim(V,Vi). Since the val￾ue of nc has a rather small variance, the accuracy of the estimated tag density can be guaranteed if the number of samplings m is fairly large. In the algorithm, the mobile

Algorithm 1 Tag density estimation algorithm 6.PERFORMANCE EVALUATION 1:INPUT:Vi={ni.1,ni.2,...,ni.s}:the vectors for refer- We evaluate the performance in realistic settings.The ence tag densities pi(i=1...h). experiment settings are the same as the realistic settings 2:PROCEDURE in Section IV,except that in this experiment we use the 3:Set the reader's power to various levels pw,1,...,pw,s.In Alien-9900 reader as the mobile reader to move forward for regard to each power level p.(jE[1,s]),issue m query continuous scanning. cycles to get the average value of the number of identified tags per cycle as nj.Assemble them as a vector V= 6.1 Evaluate the performance in unform tag {n1,n2,,ng}. density 4fort∈1，hdo In order to evaluate the performance in unform tag densi- Compute the similarity between V and Vi as follows: ty,we deploy the tags in a row with 4 grids in the shelf,while V.V ∑=1西 varying the tag densities from 10 tags/grid to 40 tags/grid, sim(V,Vi)= T嘀= the length of the scanning area is 3m. √∑=乃√∑=呢 6.1.1 The accuracy of tag density estimation 6:end for 7:Sort the value of sim(V,Vi)in decreasing order.Find the first k items of pi according to sim(V,Vi),say P1Pk &:Compute p=∑k1p4·wi,here 1/(1-sim(V,V)+e) 1= ∑/1-sim(,0+可e>0), 9:OUTPUT:The estimated tag density P. (a)The average value and(b)The estimation error of standard deviation for esti-tag density estimation mated tag density reader is required to obtain the value of ne in multiple pow- er levels.which increases overhead in both time and power Figure 5:Evaluate the accuracy of tag density esti- usage.In regard to the uniform tag density,since the tag mation density is only necessary to estimate once,this overhead In order to perform tag density estimation,we utilize Ta- can be effectively amortized by the following multiple query ble 1 as the reference set.Then,while varying the tag den- cycles.In regard to the nonuniform tag density,the tag sity from 10 to 40 tags/grid in increments of 5 tags/grid, density needs to be continuously estimated.The algorithms we estimate the tag densities based on the number of identi- for fast tag size estimation 8,11,15]can be used to reduce fied tags per cycle,i.e.,ne.For each power level,we collect the overhead.In regard to the selection of k,k should be 10 samples of ne for estimation.As the k-nearest neighbor set to neither a too small value nor a too large value for method is used in the estimation,we respectively set k to accurate estimation,the optimal value depends on the ex- 1 and 2 for the estimation.Fig.5(a)illustrates the estimat- act deployment,conventionally k should be set to 2 or 3 for ed values as well as the standard deviations for various tag performance consideration. densities.We find that both the 1-nearest neighbor method This algorithm is very practical and fully compatible with (INN)and the 2-nearest neighbor method (2NN)achieve the EPC C1G2 standard,and does not require to obtain any fairly good performance in terms of estimation accuracy.As low-level parameters for commercial RFID readers. INN can only select one tag density with the nearest proper- ty.the estimate accuracy declines when the exact tag density 5.3 Extensions for nonuniform tag density is between two reference tag densities in Table 1.In compar- ison,2NN achieves a much higher estimation accuracy since In the above solution,we assume that the tag density is it can effectively select two closest reference tag densities to always uniform.In some applications,the tags are not u- niformly deployed.While the mobile reader is continuously estimate the tag densities.Fig.5(b)further compares the estimation error of the two methods.We use the standard scanning the tags,the tag density may always change a- deviation as the metric for the estimation error.We note long the forward direction.In this situation,the constant that the standard deviation for INN is fluctuating between moving speed and power for the mobile reader is no longer suitable to improve performance.Note that in conventional 0 and 5 tags/grid while the standard deviation for 2NN is relatively stable below 3 tags/grid.This infers that in con- situations,the tag density changes slowly along the forward ventional cases 2NN achieves a much better performance direction.Therefore,in regard to each query cycle,we can than INN in terms of estimation accuracy. assume the tag density within the effective scanning window is close to uniform,since the cycle duration is usually smal- 6.1.2 The coverage ratio 1.Therefore,we can reduce the situation with nonuniform According to the analysis in Section IV,in regard to the tag density into multiple snapshots with fairly uniform tag coverage constraint Pr[C>0]>B,we need to guarantee density.In each query cycle,the mobile reader can be reset with the optimal values of p and v according to the nearby p≥0，here0=0+Vaa.Without loss of general tag density.In this way,the reading performance can be ity,we set 0*to 90%in our experiments.This means,on effectively improved by dynamically adjusting the reader's average 90%of the tags should be identified after continu- power p and the moving speed v. ous scanning.According to Fig.4,the optimal values of the

Algorithm 1 Tag density estimation algorithm 1: INPUT: Vi = {ni,1, ni,2, ..., ni,s}: the vectors for refer￾ence tag densities ρi(i = 1...h). 2: PROCEDURE 3: Set the reader’s power to various levels pw,1, ..., pw,s. In regard to each power level pw,j (j ∈ [1, s]), issue m query cycles to get the average value of the number of identified tags per cycle as nj . Assemble them as a vector V = {n1, n2, ..., ns}. 4: for i ∈ [1, h] do 5: Compute the similarity between V and Vi as follows: sim(V,Vi) = V · Vi |V |·|Vi| = s j=1 ni,j · nj s j=1 n2 j · s j=1 n2 i,j . 6: end for 7: Sort the value of sim(V,Vi) in decreasing order. Find the first k items of ρi according to sim(V,Vi), say ρ 1, ..., ρ k. 8: Compute ρ = k i=1 ρ i · wi, here wi = 1/(1 − sim(V,Vi) + ) k i=1 1/(1 − sim(V,Vi) + ) ( > 0). 9: OUTPUT: The estimated tag density ρ. reader is required to obtain the value of nc in multiple pow￾er levels, which increases overhead in both time and power usage. In regard to the uniform tag density, since the tag density is only necessary to estimate once, this overhead can be effectively amortized by the following multiple query cycles. In regard to the nonuniform tag density, the tag density needs to be continuously estimated. The algorithms for fast tag size estimation [8, 11, 15] can be used to reduce the overhead. In regard to the selection of k, k should be set to neither a too small value nor a too large value for accurate estimation, the optimal value depends on the ex￾act deployment, conventionally k should be set to 2 or 3 for performance consideration. This algorithm is very practical and fully compatible with the EPC C1G2 standard, and does not require to obtain any low-level parameters for commercial RFID readers. 5.3 Extensions for nonuniform tag density In the above solution, we assume that the tag density is always uniform. In some applications, the tags are not u￾niformly deployed. While the mobile reader is continuously scanning the tags, the tag density may always change a￾long the forward direction. In this situation, the constant moving speed and power for the mobile reader is no longer suitable to improve performance. Note that in conventional situations, the tag density changes slowly along the forward direction. Therefore, in regard to each query cycle, we can assume the tag density within the effective scanning window is close to uniform, since the cycle duration is usually smal￾l. Therefore, we can reduce the situation with nonuniform tag density into multiple snapshots with fairly uniform tag density. In each query cycle, the mobile reader can be reset with the optimal values of pw and v according to the nearby tag density. In this way, the reading performance can be effectively improved by dynamically adjusting the reader’s power pw and the moving speed v. 6. PERFORMANCE EVALUATION We evaluate the performance in realistic settings. The experiment settings are the same as the realistic settings in Section IV, except that in this experiment we use the Alien-9900 reader as the mobile reader to move forward for continuous scanning. 6.1 Evaluate the performance in unform tag density In order to evaluate the performance in unform tag densi￾ty, we deploy the tags in a row with 4 grids in the shelf, while varying the tag densities from 10 tags/grid to 40 tags/grid, the length of the scanning area is 3m. 6.1.1 The accuracy of tag density estimation k=1 k=2 0 5 10 15 20 25 30 35 40 The estimated tag density (tags/grid) ρ=10 ρ=15 ρ=20 ρ=25 ρ=30 ρ=35 ρ=40 (a) The average value and standard deviation for esti￾mated tag density 10 15 20 25 30 35 40 0 1 2 3 4 5 6 7 The actual value of tag density The standard deviation of estimation k=1 k=2 (b) The estimation error of tag density estimation Figure 5: Evaluate the accuracy of tag density esti￾mation In order to perform tag density estimation, we utilize Ta￾ble 1 as the reference set. Then, while varying the tag den￾sity from 10 to 40 tags/grid in increments of 5 tags/grid, we estimate the tag densities based on the number of identi- fied tags per cycle, i.e., nc. For each power level, we collect 10 samples of nc for estimation. As the k-nearest neighbor method is used in the estimation, we respectively set k to 1 and 2 for the estimation. Fig.5(a) illustrates the estimat￾ed values as well as the standard deviations for various tag densities. We find that both the 1-nearest neighbor method (1NN) and the 2-nearest neighbor method (2NN) achieve fairly good performance in terms of estimation accuracy. As 1NN can only select one tag density with the nearest proper￾ty, the estimate accuracy declines when the exact tag density is between two reference tag densities in Table 1. In compar￾ison, 2NN achieves a much higher estimation accuracy since it can effectively select two closest reference tag densities to estimate the tag densities. Fig.5(b) further compares the estimation error of the two methods. We use the standard deviation as the metric for the estimation error. We note that the standard deviation for 1NN is fluctuating between 0 and 5 tags/grid while the standard deviation for 2NN is relatively stable below 3 tags/grid. This infers that in con￾ventional cases 2NN achieves a much better performance than 1NN in terms of estimation accuracy. 6.1.2 The coverage ratio According to the analysis in Section IV, in regard to the coverage constraint P r[C ≥ θ] ≥ β, we need to guarantee p ≥ θ∗, here θ∗ = θ + ln(1−β) −2n . Without loss of general￾ity, we set θ∗ to 90% in our experiments. This means, on average 90% of the tags should be identified after continu￾ous scanning. According to Fig.4, the optimal values of the

0了 30.7 The m 自75 20.7 (a)The coverage of various(b)The coverage of various(c)The coverage of various(d)Coverage of various moving powers (time-efficiency) moving speed (time-efficiency)powers (energy-efficiency) speed (energy-efficiency) 250 5 200 150 100 0 24 2 The value of p (dBm) 0 0.5 Time-E erg-E ergy-E me-E he value of/s) SOV-E (e)The energy consumption(f)Coverage ratio for time-(g)Scanning time for time-(h)Energy consumption for with various power and mov-efficient,energy-efficient and efficient,energy-efficient and time-efficient,energy-efficient ing speed baseline solution baseline solution and baseline Figure 6:Experiment results in realistic settings power p and moving speed v*for the mobile reader are gradually increases to cross the threshold for 90%coverage computed in Table 2.The corresponding scanning time and the coverage is right at the threshold when the speed is set energy are also illustrated to the optimal value 0.83 m/s.The above results show that while guaranteeing the coverage ratio,the optimal settings TE p=10 0=20 p=30 p=40 (p,v*)can achieve much better time-efficiency than other 30.7dBm 28.7dBm 26.7dBm 28.7dBm settings. U 2.65m/s 0.83m/s 0.29m/s 0.15m/s Similarly,in regard to the energy-efficiency,Fig.6(c)and 1.13s 3.6s 10.3s 20s Fig.6(d)respectively show 1)the coverage of various power 1326.62.J 2667.6J 4820.4J 14820.JT levels while fixing the moving speed to the optimal value p=10 p=20 p=30 p=40 v*=0.625 m/s;2)the coverage of various moving speed. p 26.7dBm 26.7dBm 24.7dBm 26.7dBm while fixing the power to optimal value p=26.7 dBm.It 1.57m/s 0.625m/s 0.29m/s 0.12m/s is found that,among various (pu,v)parameter pairs,the 1.91s 4.8s 10.3s 25s optimal solution (p)achieves the coverage right at the E 893.88.J 2243.75J 3038.5J 11700J required threshold.These results infer that,while guaran- teeing the coverage ratio,the optimal settings(p)can Table 2:Optimal parameters for time-efficiency achieve much better energy-efficiency than other settings. (TE)and energy-efficiency (EE) 6.1.3 The time/energy-efficiency We vary the tag densities p from 10 tags/grid to 40 tags/grid In regard to the time-efficiency,since the length of the and verify the coverage ratio with various configurations for scanning area is 3m,the scanning time T=3m There- the parameters pu and v.Due to the limitation of space, fore,while guaranteeing the coverage ratio,a high speed v we only illustrate the results for p=20 tags/grid,the other is preferred.Note that as the value of v increases from 0 to results are very similar to them.We run each experiment 1m/s,the scanning time rapidly decreases from +oo to 3s;as 20 times to obtain the average value and the standard de- the value of v further increases,the scanning time decreas- viation of the number of identified tags.In regard to the es rather slowly from 3s to 0.while the coverage ratio can time-efficiency,Fig.6(a)shows the coverage of various pow- be decreased rapidly.Considering the marginal decreasing er levels,while fixing the moving speed to the optimal value effect,the moving speed should be appropriately selected *=0.83 m/s,the dashed line denotes the threshold for 90% for cost-effective consideration.In regard to the energy ef- coverage.We note that as the power increases,the number ficiency,it is known that the overall energy consumption E of identified tags gradually increases to the threshold and is proportional to the power p and inverse to the moving then further decreases.The threshold is only achieved while speed v.Fig.6(e)illustrates the value of E while varying the power is set to the optimal value 28.7dBm.Fig.6(b) the value of p and v.Moreover,in order to guarantee the shows the coverage of various moving speed,while fixing coverage ratio,the values of p and v are mutually restrict- the power to optimal value p=28.7 dBm.We note that ed.Recall that Fig.4(a)actually illustrates the maximum as the moving speed decreases,the number of identified tags allowable moving speed for reader's power p

20.7 22.7 24.7 26.7 28.7 30.7 0 10 20 30 40 50 60 70 80 Reader power pw (dBm) Overall identified tag size (a) The coverage of various powers (time-efficiency) 6 3 1.5 0.83 0.51 0.375 0 10 20 30 40 50 60 70 80 The moving speed v(m/s) Overall identified tag size (b) The coverage of various moving speed (time-efficiency) 20.7 22.7 24.7 26.7 28.7 30.7 0 10 20 30 40 50 60 70 80 Reader power pw (dBm) Overall identified tag size (c) The coverage of various powers (energy-efficiency) 6 3 1.5 0.75 0.625 0.375 0 10 20 30 40 50 60 70 80 The moving speed v(m/s) Overall identified tag size (d) Coverage of various moving speed (energy-efficiency) 0 0.5 1 1.5 2 2.5 3 22 24 26 28 30 0 1 2 3 4 x 104 T The value of v(m/s) he value of pw(dBm) The value of E(J) (e) The energy consumption with various power and mov￾ing speed Time−E Energy−E Baseline 0 50 100 150 200 250 Solution Overall identified tag size (f) Coverage ratio for time￾efficient, energy-efficient and baseline solution Time−E Energy−E Baseline 0 5 10 15 20 25 30 35 Solution Overall scanning time(s) (g) Scanning time for time￾efficient, energy-efficient and baseline solution Time−E Energy−E Baseline 0 0.5 1 1.5 2 2.5 3 3.5 4 x 104 Solution Overall Energy Consumption (J) (h) Energy consumption for time-efficient, energy-efficient and baseline Figure 6: Experiment results in realistic settings power p∗ w and moving speed v∗ for the mobile reader are computed in Table 2. The corresponding scanning time and energy are also illustrated. TE ρ = 10 ρ = 20 ρ = 30 ρ = 40 p∗ w 30.7dBm 28.7dBm 26.7dBm 28.7dBm v∗ 2.65m/s 0.83m/s 0.29m/s 0.15m/s T ∗ 1.13s 3.6s 10.3s 20s E 1326.62J 2667.6J 4820.4J 14820J EE ρ = 10 ρ = 20 ρ = 30 ρ = 40 p∗ w 26.7dBm 26.7dBm 24.7dBm 26.7dBm v∗ 1.57m/s 0.625m/s 0.29m/s 0.12m/s T 1.91s 4.8s 10.3s 25s E∗ 893.88J 2243.75J 3038.5J 11700J Table 2: Optimal parameters for time-efficiency (TE) and energy-efficiency (EE) We vary the tag densities ρ from 10 tags/grid to 40 tags/grid and verify the coverage ratio with various configurations for the parameters pw and v. Due to the limitation of space, we only illustrate the results for ρ = 20 tags/grid, the other results are very similar to them. We run each experiment 20 times to obtain the average value and the standard de￾viation of the number of identified tags. In regard to the time-efficiency, Fig.6(a) shows the coverage of various pow￾er levels, while fixing the moving speed to the optimal value v∗ = 0.83 m/s, the dashed line denotes the threshold for 90% coverage. We note that as the power increases, the number of identified tags gradually increases to the threshold and then further decreases. The threshold is only achieved while the power is set to the optimal value 28.7dBm. Fig.6(b) shows the coverage of various moving speed, while fixing the power to optimal value p∗ w = 28.7 dBm. We note that as the moving speed decreases, the number of identified tags gradually increases to cross the threshold for 90% coverage, the coverage is right at the threshold when the speed is set to the optimal value 0.83 m/s. The above results show that, while guaranteeing the coverage ratio, the optimal settings (p∗ w, v∗) can achieve much better time-efficiency than other settings. Similarly, in regard to the energy-efficiency, Fig.6(c) and Fig.6(d) respectively show 1) the coverage of various power levels while fixing the moving speed to the optimal value v∗ = 0.625 m/s; 2)the coverage of various moving speed, while fixing the power to optimal value p∗ w = 26.7 dBm. It is found that, among various (pw, v) parameter pairs, the optimal solution (p∗ w, v∗) achieves the coverage right at the required threshold. These results infer that, while guaran￾teeing the coverage ratio, the optimal settings (p∗ w, v∗) can achieve much better energy-efficiency than other settings. 6.1.3 The time/energy-efficiency In regard to the time-efficiency, since the length of the scanning area is 3m, the scanning time T = 3m v . There￾fore, while guaranteeing the coverage ratio, a high speed v is preferred. Note that as the value of v increases from 0 to 1m/s, the scanning time rapidly decreases from +∞ to 3s; as the value of v further increases, the scanning time decreas￾es rather slowly from 3s to 0, while the coverage ratio can be decreased rapidly. Considering the marginal decreasing effect, the moving speed should be appropriately selected for cost-effective consideration. In regard to the energy ef- ficiency, it is known that the overall energy consumption E is proportional to the power pw and inverse to the moving speed v. Fig.6(e) illustrates the value of E while varying the value of pw and v. Moreover, in order to guarantee the coverage ratio, the values of pw and v are mutually restrict￾ed. Recall that Fig.4(a) actually illustrates the maximum allowable moving speed v = yT | ln(1−θ∗)| for reader’s power pw

with various tag densities.Integrating with both figures, Transactions on Parallel and Distributed Systems, we can effectively derive the minimum energy to satisfy the 23(11):2094-2106,2012. coverage constraint. [4]M.Buettner and D.Wetherall.An empirical study of 6.2 Evaluate the performance in non-unform uhf rfid performance.In Proc.of MobiCom,2008. 5]S.Chen,M.Zhang,and B.Xiao.Efficient information tag density collection protocols for sensor-augmented rfid In order to evaluate the performance in non-unform tag networks.In Proc.of INFOCOM,2011. density,we nonuniformly deploy 240 tags in a row with 12 [6]H.Han,B.Sheng,C.C.Tan,Q.Li,W.Mao,and grids,while varying the tag density from p=10 to p =30 S.Lu.Counting rfid tags efficiently and anonymously. tags/grid,the length of the scanning area is 9m.We set In Proc.of INFOCOM,2010. 0*to 90%in our experiments,which infers that,on average [7]S.R.Jeffery,M.Garofalakis,and M.J.Franklin. 90%of the tags should be identified after the continuous s- Adaptive cleaning for rfid data streams.In Proc.of canning.We compare our time-efficient solution (Time-E) VLDB.2006. and energy-efficient solution (Energy-E)with the baseline [8)M.Kodialam and T.Nandagopal.Fast and reliable solution (Baseline).In regard to the baseline solution,we estimation schemes in rfid systems.In Proc.of ACM set the reader's power to its maximum value,i.e.,30.7dB- MobiCom,2006. m,which is also the standard configuration for conventional commodity readers.The moving speed is set according to [9]S.Lee,S.Joo,and C.Lee.An enhanced dynamic the optimal value v*=0.29m/s when p 30 to tackle the framed slotted aloha algorithm for rfid tag worst case.In Fig.6(f),we evaluate the coverage ratio for identification.In Proc.of MobiQuitous,2005 the three solutions.Both Time-E and Energy-E achieve 10 T.Li,S.Chen,and Y.Ling.Identifying the missing the coverage which is very close to the 90%coverage ratio. tags in a large rfid system.In Proc.of ACM Mobihoc Baseline's coverage is slightly more than this threshold,s- 2010. ince Baseline uses the maximum power and lowest speed. [11]T.Li.S.Wu,S.Chen,and M.Yang.Energy efficient In Fig.6(g)and Fig.6(h),we respectively evaluate the over- algorithms for the rfid estimation problem.In Proc.of all scanning time and energy consumption for continuous INFOCOM.2010 scanning.Both Time-E and Energy-E achieves much bet- 12J.Myung and W.Lee.Adaptive splitting protocols for ter performance than Baseline in regard to the two metrics. rfid tag collision arbitration.In Proc.of ACM Here,Time-E saves more than 50%of the scanning time MobiHoc.2006. compared with Baseline,and Energy-E saves more than 83% [13 T.L.Porta.G.Maselli,and C.Petrioli.Anti-collision of the energy consumption compared with Baseline. protocols for single-reader rfid systems:temporal analysis and optimization.IEEE Transactions on 7.CONCLUSION Mobile Computing.10(2):267-279,2011. This paper considers how to efficiently identify RFID tags 14 C.Qian,Y.Liu,H.-L.Ngan,and L.M.Ni.Asap: with a mobile reader,from the experimental point of view. Scalable identification and counting for contactless rfid We conduct measurements over a large volume of tags in re- systems.In Proc.of ICDCS,2010. alistic settings,and propose efficient algorithms for contin- [15 C.Qian,H.-L.Ngan,and Y.Liu.Cardinality uous scanning.Our experiments show that our algorithms estimation for large-scale rfid systems.In Proc.of can reduce the total scanning time by 50%and the total en- PerCom,2008. ergy consumption by 83%compared to the prior solutions. [16]B.Sheng,Q.Li,and W.Mao.Efficient continuous We believe this work gives much insight and inspiration for scanning in rfid systems.In Proc.of INFOCOM,2010. devising optimized algorithms for reading a large number of 17 B.Sheng,C.C.Tan,Q.Li,and W.Mao.Finding tags in realistic settings. popular categoried for RFID tags.In Proc.of ACM Mobihoc.2008. Acknowledgments [18]S.Tang,J.Yuan,X.Y.Li,G.Chen,Y.Liu,and This work is supported in part by National Basic Research J.Zhao.Raspberry:A stable reader activation scheduling protocol in multi-reader rfid systems.In Program of China (973)under Grant No.2009CB320705; Proc.of ICNP.2009. National Natural Science Foundation of China under Grant No.61100196,61073028,61021062:JiangSu Natural Sci- 19 H.Vogt.Efficient object identification with passive rfid tags.In Proc.of Pervasive,2002. ence Foundation under Grant No.BK2011559.Qun Li is supported in part by US National Science Foundation grants [20]L.Xie,B.Sheng,C.C.Tan,H.Han,Q.Li,and CNS-1117412 and CAREER Award CNS-0747108. D.Chen.Efficient tag identification in mobile rfid systems.In Proc.of INFOCOM,2010. 8.REFERENCES 21 L.Yang,J.Han,Y.Qi,C.Wang,T.Gu,and Y.Liu. Season:Shelving interference and joint identification [1]S.R.Aroor and D.D.Deavours.Evaluation of the state of passive uhf rfid:An experimental approach. in large-scale rfid systems.In Proc.of INFOCOM, 2011. IEEE Systems Journal 1(2):168-176.2007. [2]D.Benedetti,G.Maselli,and C.Petrioli.Fast [22]Y.Yin,L.Xie,S.Lu,and D.Chen.Efficient protocols for rule checking in rfid systems.In Proc.of ICCCN, identification of mobile rfid tags.In Proc.of IEEE 2013. MASS,2012. [3]K.Bu,B.Xiao,Q.Xiao,and S.Chen.Efficient 23 Y.Zheng and M.Li.Fast tag searching protocol for misplaced-tag pinpointing in large rfid systems.IEEE large-scale rfid systems.In Proc.of ICNP,2011

with various tag densities. Integrating with both figures, we can effectively derive the minimum energy to satisfy the coverage constraint. 6.2 Evaluate the performance in non-unform tag density In order to evaluate the performance in non-unform tag density, we nonuniformly deploy 240 tags in a row with 12 grids, while varying the tag density from ρ = 10 to ρ = 30 tags/grid, the length of the scanning area is 9m. We set θ∗ to 90% in our experiments, which infers that, on average 90% of the tags should be identified after the continuous s￾canning. We compare our time-efficient solution (Time-E) and energy-efficient solution (Energy-E) with the baseline solution (Baseline). In regard to the baseline solution, we set the reader’s power to its maximum value, i.e., 30.7dB￾m, which is also the standard configuration for conventional commodity readers. The moving speed is set according to the optimal value v∗ = 0.29m/s when ρ = 30 to tackle the worst case. In Fig.6(f), we evaluate the coverage ratio for the three solutions. Both Time-E and Energy-E achieve the coverage which is very close to the 90% coverage ratio. Baseline’s coverage is slightly more than this threshold, s￾ince Baseline uses the maximum power and lowest speed. In Fig.6(g) and Fig.6(h), we respectively evaluate the over￾all scanning time and energy consumption for continuous scanning. Both Time-E and Energy-E achieves much bet￾ter performance than Baseline in regard to the two metrics. Here, Time-E saves more than 50% of the scanning time compared with Baseline, and Energy-E saves more than 83% of the energy consumption compared with Baseline. 7. CONCLUSION This paper considers how to efficiently identify RFID tags with a mobile reader, from the experimental point of view. We conduct measurements over a large volume of tags in re￾alistic settings, and propose efficient algorithms for contin￾uous scanning. Our experiments show that our algorithms can reduce the total scanning time by 50% and the total en￾ergy consumption by 83% compared to the prior solutions. We believe this work gives much insight and inspiration for devising optimized algorithms for reading a large number of tags in realistic settings. Acknowledgments This work is supported in part by National Basic Research Program of China (973) under Grant No. 2009CB320705; National Natural Science Foundation of China under Grant No. 61100196, 61073028, 61021062; JiangSu Natural Sci￾ence Foundation under Grant No. BK2011559. Qun Li is supported in part by US National Science Foundation grants CNS-1117412 and CAREER Award CNS-0747108. 8. REFERENCES [1] S. R. Aroor and D. D. Deavours. Evaluation of the state of passive uhf rfid: An experimental approach. IEEE Systems Journal, 1(2):168–176, 2007. [2] D. Benedetti, G. Maselli, and C. Petrioli. Fast identification of mobile rfid tags. In Proc. of IEEE MASS, 2012. [3] K. Bu, B. Xiao, Q. Xiao, and S. Chen. Efficient misplaced-tag pinpointing in large rfid systems. IEEE Transactions on Parallel and Distributed Systems, 23(11):2094–2106, 2012. [4] M. Buettner and D. Wetherall. An empirical study of uhf rfid performance. In Proc. of MobiCom, 2008. [5] S. Chen, M. Zhang, and B. Xiao. Efficient information collection protocols for sensor-augmented rfid networks. In Proc. of INFOCOM, 2011. [6] H. Han, B. Sheng, C. C. Tan, Q. Li, W. Mao, and S. Lu. Counting rfid tags efficiently and anonymously. In Proc. of INFOCOM, 2010. [7] S. R. Jeffery, M. Garofalakis, and M. J. Franklin. Adaptive cleaning for rfid data streams. In Proc. of VLDB, 2006. [8] M. Kodialam and T. Nandagopal. Fast and reliable estimation schemes in rfid systems. In Proc. of ACM MobiCom, 2006. [9] S. Lee, S. Joo, and C. Lee. An enhanced dynamic framed slotted aloha algorithm for rfid tag identification. In Proc. of MobiQuitous, 2005. [10] T. Li, S. Chen, and Y. Ling. Identifying the missing tags in a large rfid system. In Proc. of ACM Mobihoc, 2010. [11] T. Li, S. Wu, S. Chen, and M. Yang. Energy efficient algorithms for the rfid estimation problem. In Proc. of INFOCOM, 2010. [12] J. Myung and W. Lee. Adaptive splitting protocols for rfid tag collision arbitration. In Proc. of ACM MobiHoc, 2006. [13] T. L. Porta, G. Maselli, and C. Petrioli. Anti-collision protocols for single-reader rfid systems: temporal analysis and optimization. IEEE Transactions on Mobile Computing, 10(2):267–279, 2011. [14] C. Qian, Y. Liu, H.-L. Ngan, and L. M. Ni. Asap: Scalable identification and counting for contactless rfid systems. In Proc. of ICDCS, 2010. [15] C. Qian, H.-L. Ngan, and Y. Liu. Cardinality estimation for large-scale rfid systems. In Proc. of PerCom, 2008. [16] B. Sheng, Q. Li, and W. Mao. Efficient continuous scanning in rfid systems. In Proc. of INFOCOM, 2010. [17] B. Sheng, C. C. Tan, Q. Li, and W. Mao. Finding popular categoried for RFID tags. In Proc. of ACM Mobihoc, 2008. [18] S. Tang, J. Yuan, X. Y. Li, G. Chen, Y. Liu, and J. Zhao. Raspberry: A stable reader activation scheduling protocol in multi-reader rfid systems. In Proc. of ICNP, 2009. [19] H. Vogt. Efficient object identification with passive rfid tags. In Proc. of Pervasive, 2002. [20] L. Xie, B. Sheng, C. C. Tan, H. Han, Q. Li, and D. Chen. Efficient tag identification in mobile rfid systems. In Proc. of INFOCOM, 2010. [21] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu. Season: Shelving interference and joint identification in large-scale rfid systems. In Proc. of INFOCOM, 2011. [22] Y. Yin, L. Xie, S. Lu, and D. Chen. Efficient protocols for rule checking in rfid systems. In Proc. of ICCCN, 2013. [23] Y. Zheng and M. Li. Fast tag searching protocol for large-scale rfid systems. In Proc. of ICNP, 2011