计算机科学与技术（参考文献）Exploring the Gap between Ideal and Reality - An Experimental Study on Continuous Scanning with Mobile Reader in RFID Systems

2272 IEEE TRANSACTIONS ON MOBILE COMPUTING.VOL.14.NO.11.NOVEMBER 2015 Exploring the Gap between Ideal and Reality:An Experimental Study on Continuous Scanning with Mobile Reader in RFID Systems Lei Xie,Member,IEEE,Qun Li,Member,IEEE,Chuyu Wang,Student Member,IEEE, Xi Chen,and Sanglu Lu,Member,IEEE Abstract-In this paper,we show the first comprehensive experimental 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 moving speed.Our experiments show that our algorithms can reduce the total scanning time by 50 percent and the total energy consumption by 83 percent compared to the prior solutions. Index Terms-RFID,model,realistic settings,continuous scanning,algorithm design,optimization 1 INTRODUCTION Me5Rpnaieyhsnas First,previous experiments were usually conducted in a small scale (fewer than 20 tags),which does not capture the Scanning books in a library or a bookstore,tracking mer- complication for a large number of tags.Second,previous chandises in a store,all require a mobile reader to be used work has been focused on reading performance in a close to for continuous scanning over the tags attached to the physi- free space scenario.In reality,path loss,multi-path effect cal goods and assets.The mobile reader moves continuously and mutual interference are common and have a big impact to scan a large number of tags effectively compensating for to RFID reading process.Third,previous work mainly its limited reading range.In those types of mobile reader examined how factors such as distance,coding scheme and systems,two performance metrics are highly pertinent: frequency,affect reading performance.Very important fac- time efficiency to reduce the total scanning time,and energy tors,i.e.,the reader's power and tag density,were efficiency to reduce the total power consumption.Unfortu-neglected.Therefore,the previous work does not give a nately,there is no realistic model to characterize the perfor- model for RFID reading process in a realistic and large scale mance for mobile RFID reading for a large scale setting.The setting;in particular,it does not include the power and tag factors that affect the mobile reading performance are very density.Indeed,before we started our work,there was no complicated.For example,the actual scanning time for a realistic model which can guide us in designing an efficient number of tags in a realistic scenario is much longer than tag identification solution in our setting. the time computed for free space,as shown in our experi- We have,thus,conducted comprehensive measurements ments.In addition,RFID readers have a wide range of over a large number of tags in realistic settings by varying power selections,e.g.,the Alien-9900 reader has a maxi-various parameters.Surprisingly,we have a few important mum power 30.7 dBm,which is 30 times larger than the new findings from the experiments.For example,we have minimum power 15.7 dBm.There is no guideline,however, found that the probabilistic backscattering is a ubiquitous in selecting a suitable power.Therefore,we aim to design phenomenon of the RFID system in realistic settings,i.e., an efficient solution to continuous scanning problem for a during every query cycle each tag randomly responds with mobile RFID reader based on experimental study. a certain probability,which has an important effect on the Although there have been some experimental studies on reading performance.This observation is contrary to the reading performance in a stationary RFID system [1],[21, previous belief that tags respond to a reader with either [3],the previous studies have the following limitations. probability 1 or 0.We have also found it is not wise to blindly increase the reader's power for tag identification, .L.Xie,C.Wang,X.Chen,and S.Lu are with the State Key Laboratory for which can degrade the overall performance including the Novel Software Technology,Nanjing UIniversity,Nanjing 210023,China. effective throughput and energy consumption.These find- E-mail:(lxie,sanglu@nju.edu.cn,(wangcyu217,hawkxcl@dislab.nju. ings are essential to improving reading performance for a ed1l.C几. Q.Li is with the Department of Computer Science,College of William and mobile RFID system.Most importantly,we can (1)model Mary,Williamsburg,Virginia 23187.E-mail:liqun@cs.wm.edu. the patterns of reading a large number of tags by giving Manuscript received 7 Jan.2014;revised 8 Nov.2014;accepted 15 Jan.2015. a probabilistic model to capture the major and minor detec- Date of publication 21 Jan.2015;date of current version 29 Sept.2015. tion region,and(2)model how the reading power and tag For information on obtaining reprints of this article,please send e-mail to: reprints@ieee.org,and reference the Digital Object Identifier below. density affect the reading performance by proving an Digital Object Identifier no.10.1109/TMC.2015.2395426 empirical mapping. mission

Exploring the Gap between Ideal and Reality: An Experimental Study on Continuous Scanning with Mobile Reader in RFID Systems Lei Xie, Member, IEEE, Qun Li, Member, IEEE, Chuyu Wang, Student Member, IEEE, Xi Chen, and Sanglu Lu, Member, IEEE Abstract—In this paper, we show the first comprehensive experimental 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 moving speed. Our experiments show that our algorithms can reduce the total scanning time by 50 percent and the total energy consumption by 83 percent compared to the prior solutions. Index Terms—RFID, model, realistic settings, continuous scanning, algorithm design, optimization Ç 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 mer￾chandises in a store, all require a mobile reader to be used for continuous scanning over the tags attached to the physi￾cal 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 reduce the total power consumption. Unfortu￾nately, there is no realistic model to characterize the perfor￾mance for mobile RFID reading for a large scale setting. The factors that affect the mobile reading performance are very complicated. For example, the actual scanning time for a number of tags in a realistic scenario is much longer than the time computed for free space, as shown in our experi￾ments. In addition, RFID readers have a wide range of power selections, e.g., the Alien-9900 reader has a maxi￾mum power 30.7 dBm, which is 30 times larger than the minimum power 15.7 dBm. There is no guideline, however, in selecting a suitable power. Therefore, we aim to design an efficient solution to continuous 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 [1], [2], [3], the previous studies have the following limitations. First, previous experiments were usually conducted in a small scale (fewer than 20 tags), which does not capture the complication 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 RFID reading process. Third, previous work mainly examined how factors such as distance, coding scheme and frequency, affect reading performance. Very important fac￾tors, 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 blindly increase the reader’s power for tag identification, which can degrade the overall performance including the effective throughput and energy consumption. These find￾ings are essential 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 probabilistic model to capture the major and minor detec￾tion region, and (2) model how the reading power and tag density affect the reading performance by proving an empirical mapping.
L. Xie, C. Wang, X. Chen, and S. Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China. E-mail: {lxie, sanglu}@nju.edu.cn, {wangcyu217, hawkxc}@dislab.nju. edu.cn.
Q. Li is with the Department of Computer Science, College of William and Mary, Williamsburg, Virginia 23187. E-mail: liqun@cs.wm.edu. Manuscript received 7 Jan. 2014; revised 8 Nov. 2014; accepted 15 Jan. 2015. Date of publication 21 Jan. 2015; date of current version 29 Sept. 2015. For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org, and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TMC.2015.2395426 2272 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 11, NOVEMBER 2015 1536-1233
2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information

XIE ET AL.:EXPLORING THE GAP BETWEEN IDEAL AND REALITY:AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2273 Based on the effective models,we consider to tackle the information gathered in the previous scanning operations following problem in a typical scenario of RFID applica- to reduce the scanning time of the succeeding ones. tions,i.e.,using a mobile reader to identify a large volume In order to verify the impact of the physical layer's unre- of tags deployed over a wide area.We seek to execute con- liability,a number of researchers conduct experimental tinuous scanning over the tags along a certain direction, studies in realistic settings,while trying to explore the gap while respectively considering a situation where the tags are between the ideal situation and the realistic situation for continuously placed with a uniform/nonuniform density. RFID systems.Buettner and Wetherall [1]examine the per- We focus on several critical metrics like time-efficiency, formance of the C1G2 RFID system in a realistic setting. energy-efficiency and coverage ratio.We design efficient They identify factors that degrade overall performance and and practical algorithms for continuous scanning,by skill- reliability with a focus on the physical layer.Jeffery et al.[3] fully adjusting the reader's power and moving speed,which conduct experiments in realistic settings and find that can dramatically improve the performance,as shown in our within each reader's detection range,a large difference real experiments.By exploring the inherent regularities in exists in reading performance.Zheng and Li investigate continuous scanning,we aim to give some fundamental into the physical layer information of tag responses for guidance for future RFID system design towards more com- missing tag identification [281.Realizing that the reader's plicated realistic settings.We make the following contribu- transmission power actually has a significant impact on the tions in this paper (a preliminary version of this work reading performance of the RFID system,Xu et al.investi- appeared in [41).1)We are the first to conduct an extensive gate the impact of transmission power on reading perfor- experimental study and performance evaluation over a rela- mance through extensive empirical study on passive tags tively large number of tags (up to 160 tags for experimental [29],[30].Su et al.find that,when the transmission power is study and up to 480 tags for performance evaluation)and a set to a reasonable range,the "capture effect"can be used to rather high tag density (up to 90 tags per square meter)in resolve the collision slots into singleton slots [31].Therefore, realistic settings.To the best of our knowledge,this is the they propose a progressing scanning algorithm to improve first work to propose a model for investigating how the the reading throughput. important 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- 3 PROBLEM FORMULATION ing reading performance based on experimental study.We We consider a typical scenario of continuous scanning in apply our model to solve the problem of continuous scan- realistic settings,i.e.,using a mobile reader to identify a ning with mobile reader.By carefully adjusting the power large volume of tags deployed over a wide area.We respec- and moving speed,we design efficient algorithms to opti- tively consider a situation where the tags are continuously mize time-efficiency and energy-efficiency.We have a num- placed with a uniform/nonuniform density,we seek to exe- ber of novel techniques in making our algorithms practical. cute continuous scanning over the tags along a certain direc- 3)Being compatible with RFID standard(with no changes to tion.The performance metrics in our consideration are as the C1G2 protocols or low-level parameters for commercial follows:1)Time-efficiency:considering it is time-consuming RFID readers),our solutions can deliver significant perfor- to identify a large volume of tags in realistic settings,the mance gain.Experiment results indicate that,while achiev- overall scanning time should be as small as possible.2) ing the same coverage ratio,our practical solutions Energy-efficiency:considering the mobile reader is conven- respectively reduce scanning time by 50 percent and energy tionally battery powered,e.g.,a typical battery for the consumption by 83 percent compared to the prior solutions. mobile reader has a capacity of 3,200 mAh with output volt- age 3.7 v,if we scan the tags with a maximum radiation 2 RELATED WORK power 36 dBm,the mobile reader can execute continuous scanning for only 3 hours,therefore,the overall energy In RFID systems,a reader needs to receive data from multi- used should be as small as possible.3)Coverage ratio:due to ple tags.These tags are unable to self-regulate their radio various issues like path loss in realistic settings,it is difficult transmissions to avoid collisions.In light of this,a series of to identify all tags with a high probability for one single slotted ALOHA-based anti-collision protocols [5],[6],[7],as scanning cycle,therefore,the coverage ratio,i.e.,the ratio of well as tree-based anti-collision protocols [8],[9],[10],[111, the number of identified tags to the total number of tags, are designed to resolve collisions in RFID systems.In order should be guaranteed,while each tag should have a uni- to deal with the collision problems in multi-reader RFID form probability to be identified. systems,scheduling protocols for reader activation are In regard to the continuous scanning,we define the scan- explored in [12],[13].Recently,a number of polling-based ning time as T,the overall energy used as E,and the cover- protocols [141,[15],[161,[17]are proposed,aiming to collect age ratio as C.Assuming the tag density is p and the length information from RFID tags in a time/energy efficient of the scanning area is l,then the total tag size is n =l.p, approach.In order to estimate the number of tags without we denote the overall tag set as S.We assume that each tag collecting tag IDs,a number of protocols are proposed [181,tiEs is successfully identified with probability of pi after [191,[20l,[21),[22l,[23,[24,[25l,[26]to leverage the infor- the continuous scanning.The reader's antenna is deployed mation gathered in slotted ALOHA protocol for fast estima- towards the tags with a distance of d.We can adjust the tion of tag size.In regard to tag identification with the parameters including the reader's power p and the moving mobile reader,Sheng et al.develop efficient schemes for speed u to improve the reading performance.Therefore, continuous scanning operations [271,aiming to utilize the during the continuous scanning,the problem is how to

Based on the effective models, we consider to tackle the following problem in a typical scenario of RFID applica￾tions, i.e., using a mobile reader to identify a large volume of tags deployed over a wide area. We seek to execute con￾tinuous scanning over the tags along a certain direction, while respectively considering a situation where the tags are continuously placed with a uniform/nonuniform density. We focus on several critical metrics like time-efficiency, energy-efficiency and coverage ratio. We design efficient and practical algorithms for continuous scanning, by skill￾fully adjusting the reader’s power and moving speed, which can dramatically improve the performance, as shown in our real experiments. By exploring the inherent regularities in continuous scanning, we aim to give some fundamental guidance for future RFID system design towards more com￾plicated realistic settings. We make the following contribu￾tions in this paper (a preliminary version of this work appeared in [4]). 1) We are the first to conduct an extensive experimental study and performance evaluation over a rela￾tively large number of tags (up to 160 tags for experimental study and up to 480 tags for performance evaluation) 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 important 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 opti￾mize time-efficiency and energy-efficiency. We have a num￾ber of novel techniques in making our algorithms practical. 3) Being compatible with RFID standard (with no changes to the C1G2 protocols or low-level parameters for commercial RFID readers), our solutions can deliver significant perfor￾mance gain. Experiment results indicate that, while achiev￾ing the same coverage ratio, our practical solutions respectively reduce scanning time by 50 percent and energy consumption by 83 percent compared to the prior solutions. 2 RELATED WORK In RFID systems, a reader needs to receive data from multi￾ple 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 [5], [6], [7], as well as tree-based anti-collision protocols [8], [9], [10], [11], are designed to resolve collisions in RFID systems. In order to deal with the collision problems in multi-reader RFID systems, scheduling protocols for reader activation are explored in [12], [13]. Recently, a number of polling-based protocols [14], [15], [16], [17] are proposed, aiming to collect information 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 [18], [19], [20], [21], [22], [23], [24], [25], [26] to leverage the infor￾mation gathered in slotted ALOHA protocol for fast estima￾tion of tag size. In regard to tag identification with the mobile reader, Sheng et al. develop efficient schemes for continuous scanning operations [27], aiming to utilize the information gathered in the previous scanning operations to reduce the scanning time of the succeeding ones. In order to verify the impact of the physical layer’s unre￾liability, a number of researchers conduct experimental studies in realistic settings, while trying to explore the gap between the ideal situation and the realistic situation for RFID systems. Buettner and Wetherall [1] examine the per￾formance of the C1G2 RFID system in a realistic setting. They identify factors that degrade overall performance and reliability with a focus on the physical layer. Jeffery et al. [3] conduct experiments in realistic settings and find that within each reader’s detection range, a large difference exists in reading performance. Zheng and Li investigate into the physical layer information of tag responses for missing tag identification [28]. Realizing that the reader’s transmission power actually has a significant impact on the reading performance of the RFID system, Xu et al. investi￾gate the impact of transmission power on reading perfor￾mance through extensive empirical study on passive tags [29], [30]. Su et al. find that, when the transmission power is set to a reasonable range, the “capture effect” can be used to resolve the collision slots into singleton slots [31]. Therefore, they propose a progressing scanning algorithm to improve the reading throughput. 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 direc￾tion. The performance metrics in our consideration are as follows: 1) 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. 2) Energy-efficiency: considering the mobile reader is conven￾tionally battery powered, e.g., a typical battery for the mobile reader has a capacity of 3,200 mAh with output volt￾age 3.7 v, if we scan the tags with a maximum radiation power 36 dBm, the mobile reader can execute continuous scanning for only 3 hours, therefore, the overall energy used should be as small as possible. 3) 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, therefore, 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 uni￾form 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 r and the length of the scanning area is l, then the total tag size is n ¼ l r, we denote the overall tag set as S. We assume that each tag tj 2 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 XIE ET AL.: EXPLORING THE GAP BETWEEN IDEAL AND REALITY: AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2273

2274 IEEE TRANSACTIONS ON MOBILE COMPUTING.VOL.14.NO.11.NOVEMBER 2015 efficiently set the parameters p and v such that the follow- 80 ing objectives can be achieved: 70 Time-efficiency: 60 minimize T (1) 50 subject to (2) 40 E≤a energy constraint 30 PC≥d≥B coverage constraint (3) 29 t;∈Spj=p coverage constraint (4) .5 1.5 2.5 Distance(m) Fig.1.The number of tags read for various distances. Energy-efficiency: bookshelf is composed of 16 grids with four columns and minimize E four rows,the height and width of each grid are respec- subject to tively 60 cm and 75 cm.In the experiments we only consider (6) T≤Y the grids in the three rows of upper layers,since the grids in time constraint the bottom layer may be greatly affected by the multi-path PrC20≥B coverage constraint (7) effect.Therefore,we choose to deploy the tags in the 12 grids with four columns and three rows.The RFID reader is stati- t∈Sp防=p coverage constraint (8) cally deployed by facing its antenna towards the book shelf. Note that in order to set an appropriate value for the dis- tance between the reader and the bookshelf,it is difficult to According to the above formulation,in regard to the time-efficiency,the objective is to minimize the overall directly derive the optimal distance from geometry accord- scanning time T while the energy constraint and the cover- ing to the beamwidth,due to issues like the multi-path age constraint should be satisfied.The energy constraint effect.Therefore,we vary the distance from 0.5 to 3 m and requires the energy used should be no greater than a certain measure the number of effectively identified tags while threshold a.In regard to the coverage constraint,due to the scanning 160 tags uniformly distributed on the shelf. random factors in the anti-collision scheme and the com- As shown in Fig.1,we find that the reader achieves the munication environment,the coverage ratio C cannot guar- maximum coverage when the distance is 1.5 m.Thus,we antee to be deterministically equal or greater than a set the distance to 1.5 m to guarantee the reading perfor- threshold 0,hence we use the probabilistic approach to mance.This setting is close to a typical noisy condition, denote the requirement.The probability for the coverage which is distinct from the free space condition,since the ratio C to be equal or greater than 6 should be no less than issues in the realistic applications like the path loss,multi- B.Moreover,there could exist multiple feasible solutions to path effect and energy absorption all exist.Considering that guarantee the coverage constraint,in some of the solutions we deploy a relatively large number of tags (up to 160 tags the tags are detected with nonuniform probabilities.In fair- in experimental study and 480 tags in performance evalua- ness,we require that each tag ti in the set S should be tion)and a rather high tag density (up to 90 tags per square detected with a uniform probability p,i.e.,the detection meter)in realistic settings,the experimental findings from probability pi should be equal to p.Similarly,in regard to the high tag density deployment can be highly scalable and the energy-efficiency,the objective is to minimize the over- generalized to rather large scale settings.Specifically,we attach each tag to a book and put these books back-to-back all energy E,while the time constraint and the coverage constraint should be satisfied.The time constraint requires in a very dense approach.We believe this tag density (up to that the scanning time should be no greater than a certain 90 tags per m2)should be close to extreme case in scale for threshold,y. conventional RFID applications.Since we use the mobile RFID reader to scan the tags within its limited scanning range,hence,after the whole process of continuous scan- 4 DERIVING A MODEL FROM REALISTIC ning,all tags can be effectively identified.Therefore,as long EXPERIMENTS as we can tackle the problem in this situation,it can be In order to understand how the reader's power and tag den- guaranteed that our solution is scalable to any large scale sity affect the reading performance,while dealing with during the continuous scanning. issues like the path loss,energy absorption,and mutual On the whole,it took us over 300 hours to conduct an interference,we illustrate several original findings from our extensive experimental study of up to 160 tags in realistic realistic experiments.In our experiments,we use the Alien- settings.In order to sufficiently understand how the param- 9900 reader and Alien-9611 linear antenna with a directional eters separately/jointly affect the actual reading perfor- gain of 6 dB.The 3 dB beamwidth is 40 degrees.The RFID mance,we conduct up to 100 various experiments,carrying tags used are Alien 9640 general-purpose tags which sup- out lots of experimental comparisons and analysis on port the EPC C1G2 standards.We attach the RFID tags onto the obtained results.In the following experiments,we the books which are placed in a large bookshelf.Each tag is vary the tag density,p,from 10 to 40 tags/grid,while attached onto a distinct book with a unique ID.The adjusting the reader's power from 20.7 dBm to 30.7 dBm for

efficiently set the parameters pw and v such that the follow￾ing objectives can be achieved: Time-efficiency: minimize T (1) subject to E  a energy constraint (2) Pr½C  u  b coverage constraint (3) 8tj 2 S pj ¼ p coverage constraint (4) Energy-efficiency: minimize E (5) subject to T  g time constraint (6) Pr½C  u  b coverage constraint (7) 8tj 2 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 cover￾age constraint should be satisfied. The energy constraint requires the energy used should be no greater than a certain threshold a. In regard to the coverage constraint, due to the random factors in the anti-collision scheme and the com￾munication environment, the coverage ratio C cannot guar￾antee to be deterministically equal or greater than a threshold u, hence we use the probabilistic approach to denote the requirement. The probability for the coverage ratio C to be equal or greater than u should be no less than b. Moreover, there could exist multiple feasible solutions to guarantee the coverage constraint, in some of the solutions the tags are detected with nonuniform probabilities. In fair￾ness, we require that each tag tj in the set S should be detected with a uniform 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 over￾all energy E, while the time constraint and the coverage constraint should be satisfied. The time constraint requires that the scanning time should be no greater than a certain threshold, g. 4 DERIVING A MODEL FROM REALISTIC EXPERIMENTS In order to understand how the reader’s power and tag den￾sity affect the reading performance, while dealing with issues like the path loss, energy absorption, and mutual interference, 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 6 dB. The 3 dB beamwidth is 40 degrees. The RFID tags used are Alien 9640 general-purpose tags which sup￾port 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 bookshelf is composed of 16 grids with four columns and four rows, the height and width of each grid are respec￾tively 60 cm and 75 cm. In the experiments we only consider the grids in the three rows of upper layers, since the grids in the bottom layer may be greatly affected by the multi-path effect. Therefore, we choose to deploy the tags in the 12 grids with four columns and three rows. The RFID reader is stati￾cally deployed by facing its antenna towards the book shelf. Note that in order to set an appropriate value for the dis￾tance between the reader and the bookshelf, it is difficult to directly derive the optimal distance from geometry accord￾ing to the beamwidth, due to issues like the multi-path effect. Therefore, we vary the distance from 0.5 to 3 m and measure the number of effectively identified tags while scanning 160 tags uniformly distributed on the shelf. As shown in Fig. 1, we find that the reader achieves the maximum coverage when the distance is 1.5 m. Thus, we set the distance to 1.5 m to guarantee the reading perfor￾mance. 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 160 tags in experimental study and 480 tags in performance evalua￾tion) and a rather high tag density (up to 90 tags per square meter) in realistic settings, the experimental findings from the high tag density deployment can be highly scalable and generalized to rather large scale settings. Specifically, we attach each tag to a book and put these books back-to-back in a very dense approach. We believe this tag density (up to 90 tags per m2) should be close to extreme case in scale for conventional RFID applications. Since we use the mobile RFID reader to scan the tags within its limited scanning range, hence, after the whole process of continuous scan￾ning, all tags can be effectively identified. Therefore, as long as we can tackle the problem in this situation, it can be guaranteed that our solution is scalable to any large scale during the continuous scanning. On the whole, it took us over 300 hours to conduct an extensive experimental study of up to 160 tags in realistic settings. In order to sufficiently understand how the param￾eters 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 obtained results. In the following experiments, we vary the tag density, r, from 10 to 40 tags/grid, while adjusting the reader’s power from 20.7 dBm to 30.7 dBm for 0.5 1 1.5 2 2.5 3 20 30 40 50 60 70 80 Distance(m) Effective tag size Fig. 1. The number of tags read for various distances. 2274 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 11, NOVEMBER 2015

XIE ET AL.:EXPLORING THE GAP BETWEEN IDEAL AND REALITY:AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2275 22.7dBm =24.7dB -30.7 02* 0.4 0.6 0.8 Gnd ID 140 10 10 (a)Histogram of read ratio (b)Probability density functions gB (a)Histogram of read ratio for various moving speeds Fig.2.Probabilistic backscattering in static situation. performance evaluation.Unless otherwise specified,by default we fix the reader towards the center of the book- shelf,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 (b)Proportion of identified (c)Average read ratio for each tag During the query cycles,each tag responds to the reader with a number of tags certain probability between 0 and 1.We uniformly deploy 96 Fig.3.Probabilistic backscattering in mobile situation. tags in the bookshelf with eight tags in each grid.The grids on the left/middle/right side are respectively numbered current round.In regard to the change of multi-path condi- (1,23)/(4,5,6,7,8,9)/(10,11,12.First,we use a static RFID tions,since we use the mobile RFID reader to continuously reader to scan these tags for 100 times. interrogate the surrounding RFID tags while the reader is In Fig.2a,we respectively compute the read ratios of moving,the reader's antenna continuously changes its posi- each tag in the 12 grids,i.e.,the ratio of successful number tion,the incident angle and distance of the signal wave of responses to the expected number of responses for each from the reader to the tag is continuously changing,which tag,and illustrate them in histogram grouped by grid ID. causes the multi-path conditions change a lot during the We note that the tags respond to the reader with various continuous scanning.Therefore,the change of multi-path probabilities between 0 and 1,although basically no param- conditions is essentially caused by the movement of the eters are changed during the repetitive scanning.This reader. observation is contrary to the popular idea that each tag Fig.3a shows the histogram of read ratio for various either responds thoroughly or does not respond at all.We moving speeds.We observe that most of the tags which can- think this is probably due to the randomness in the back- not be identified in static cases can be effectively identified scattering factors,like the power scattering,multi-path in the mobile cases.Each tag tends to have close response propagation.Furthermore,we vary the reader's power,p, probability in mobile scanning.Fig.3b further shows the from 22.7 to 30.7 dBm and obtain the probability density proportion of identified tags for various moving speeds,i.e., functions for the read ratio.According to Fig.2b,we note the ratio of the number of identified tags to the overall num- that as the reader's power varies,the distribution of the ber of tags.We find that the mobile scanning approach can read ratio also varies.The above observation further implies greatly increase the overall ratio of identification in compar- that,due to the probabilistic backscattering,multiple query ison to the static approach.Fig.3c further shows the read cycles are essential to successfully identify a typical tag in ratio for each tag for various moving speeds.We find that the tag set,which may cause massive duplicated readings while mobile scanning can effectively increase the read ratio over other tags in the scanning area. than the static approach,the one with lower moving speed According to the experiments in static situations,we can achieve more efficiency in read ratio than the one with observe that,although the tags respond to the reader with larger moving speed. various probabilities,a majority of the tags still respond with probability either close to 100 percent or 0.Due to the ambient multi-path effect in indoor environment,we find 4.1.2 Major Detection Region versus Minor Detection that even in very close positions from the reader,some tags Region can be easily identified and some tags cannot be identified Within each reader's detection range,there are two distinct at all.Moreover,we further conduct continuous scanning in regions:the major detection region where the tags can be identified mobile environment,by varying the moving speed of the with high probability,and the minor detection region where the mobile reader from 0 to 100 cm/s.We set the reader's power tags can be identified with low probability.We uniformly to 25.7 dBm and make it continuously interrogate the sur-deploy the tags in a row with four grids in the bookshelf, rounding tags while moving.We continuously scan tags in where the tag IDs are sequentially numbered from left to four grids,and the tag density is 40 tags/grid.During the right.The reader's power is set to 30.7 dBm.Figs.4a,4b,4c, continuous scanning,as the multi-path effect is continu-and 4d show the histogram of each tag's read ratio in the ously changing,we find that some tags which cannot be order of tag ID,while varying the tag density,ie.,the num- identified in the previous round can be easily identified in ber of tags per grid

performance evaluation. Unless otherwise specified, by default we fix the reader towards the center of the book￾shelf, 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 uniformly deploy 96 tags in the bookshelf with eight tags in each grid. The grids on the left/middle/right side are respectively numbered (1,2,3)/(4,5,6,7,8,9)/(10,11,12). First, we use a static RFID reader to scan these tags for 100 times. In Fig. 2a, we respectively 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 illustrate them in histogram grouped by grid ID. We note that the tags respond to the reader with various probabilities between 0 and 1, although basically no param￾eters are changed during the repetitive scanning. This observation is contrary to the popular idea that each tag either responds thoroughly or does not respond at all. We think this is probably due to the randomness in the back￾scattering factors, like the power scattering, multi-path propagation. Furthermore, we vary the reader’s power, pw, from 22.7 to 30.7 dBm and obtain the probability density functions for the read ratio. According to Fig. 2b, 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 probabilistic 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. According to the experiments in static situations, we observe that, although the tags respond to the reader with various probabilities, a majority of the tags still respond with probability either close to 100 percent or 0. Due to the ambient multi-path effect in indoor environment, we find that even in very close positions from the reader, some tags can be easily identified and some tags cannot be identified at all. Moreover, we further conduct continuous scanning in mobile environment, by varying the moving speed of the mobile reader from 0 to 100 cm/s. We set the reader’s power to 25.7 dBm and make it continuously interrogate the sur￾rounding tags while moving. We continuously scan tags in four grids, and the tag density is 40 tags/grid. During the continuous scanning, as the multi-path effect is continu￾ously changing, we find that some tags which cannot be identified in the previous round can be easily identified in current round. In regard to the change of multi-path condi￾tions, since we use the mobile RFID reader to continuously interrogate the surrounding RFID tags while the reader is moving, the reader’s antenna continuously changes its posi￾tion, the incident angle and distance of the signal wave from the reader to the tag is continuously changing, which causes the multi-path conditions change a lot during the continuous scanning. Therefore, the change of multi-path conditions is essentially caused by the movement of the reader. Fig. 3a shows the histogram of read ratio for various moving speeds. We observe that most of the tags which can￾not be identified in static cases can be effectively identified in the mobile cases. Each tag tends to have close response probability in mobile scanning. Fig. 3b further shows the proportion of identified tags for various moving speeds, i.e., the ratio of the number of identified tags to the overall num￾ber of tags. We find that the mobile scanning approach can greatly increase the overall ratio of identification in compar￾ison to the static approach. Fig. 3c further shows the read ratio for each tag for various moving speeds. We find that, while mobile scanning can effectively increase the read ratio than the static approach, the one with lower moving speed can achieve more efficiency in read ratio than the one with larger moving speed. 4.1.2 Major Detection Region versus Minor Detection Region Within each reader’s detection range, there are two distinct 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 probability. We uniformly deploy the tags in a row with four grids in the bookshelf, where the tag IDs are sequentially numbered from left to right. The reader’s power is set to 30.7 dBm. Figs. 4a, 4b, 4c, and 4d show the histogram of each tag’s read ratio in the order of tag ID, while varying the tag density, i.e., the num￾ber of tags per grid. Fig. 2. Probabilistic backscattering in static situation. Fig. 3. Probabilistic backscattering in mobile situation. XIE ET AL.: EXPLORING THE GAP BETWEEN IDEAL AND REALITY: AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2275

2276 IEEE TRANSACTIONS ON MOBILE COMPUTING.VOL.14.NO.11.NOVEMBER 2015 10 30 22 60 Missing tag ID 100 (a)Histogram of read ratiolp (b)Histogram of read ratio (p= (a)The randomness of missing (b)The number of tags identified 10) 20) tag ID with various deployment Fig.5.Power density over the tags. radiation area.As the power increases,we note that the identified tag size in uniform distribution is always larger than the centered distribution.This is because the power density in the former case is much larger than the latter 20 40 Tag ID 0 100 120 100 150 case,more tags in the former case respond to the reader. (c)Histogram of read ratio (p (d)Histogram of read ratio (p Therefore,in order to statistically depict the probabilistic 30) 40) backscattering property in the major detection region,the Fig.4.Major detection region versus minor detection region. average detection probability is essential to be used. In order to see the two distinct regions,we use red window 4.1.4 Marginal Decreasing Effect to depict the boundary of the major detection region.We observe that within each reader's detection range,the major As the reader's power is increasing,the exact read efficiency includ- detection region is the area directly in front of the reader,giv- ing the scanning range,the detection probability,as well as the ing high detection probability,and the minor detection region number of identified tags,is not increasing equally with the power. extends from the end of the major detection region to the edge In Figs.6a-6c,we respectively measure the width of major detection region,the average detection probability (i.e.,read of the detection range,where the read ratio drops off to zero at the end of the detection range.As the tag density increases, ratio)in major detection region,as well as the overall number the major detection region gradually shrinks. of identified tags,while varying the reader's power from 20.7 to 30.7 dBm.All three variables are increasing while the reader's power increases.However,as the power is 4.1.3 Power Density Over the Tags increased by 2 dB (i.e,1.58 times in watt),they mainly The power density,i.e.,the radiative energy diffused to per tag, increase with a much smaller speed on average.This obser- has a big effect on the reading performance.According to vation implies that the read efficiency cannot be sufficiently Figs.4a,4b,4c,and 4d,we find that even within the major enhanced by purely increasing the reader's power. detection region,there are a certain number of tags which still remain unidentified.While in the minor detection 4.1.5 region,there are several tags which have high read ratios. Query Cycle Duration versus the Number of This observation is related to the power density over the Identified Tags Per Cycle tags:according to Figs.4a and 4b,while the tag density is As the reader's power increases,the query cycle duration does not low,the power density is fairly large,nearly all tags in the increase linearly with the number of identified tags per cycle, major detection region have high probability to respond; according to Figs.4c and 4d,while the tag density increases 10 to a large value,the diffused power is diluted among the tags,and the power density is thus reduced,causing some of the tags in the major detection region fail to respond. Besides,we observe that the missing tags in the major detec- tion region is fairly random.According to the deployment in Fig.4d,we randomly issue five query cycles and collect 30 22 Rerpen3p,(e the missing tag IDs,by slightly adjusting the antenna's posi- (a)Width of major detection re- (b)The average detection proba- tion for each query cycle.Fig.5a illustrates the missing tag gion bility in major detection region IDs in the major detection region,where the points denote the missing tags.We note that most of the missing tag's IDs are fairly random,except a small number of tags which are always missing due to the inappropriate deployment.In order to further verify the effect of the power density,we deploy 30 tags in two distinct distributions (uniform and centered)and measure the effective identified tag size in Fig.5b.In the uniform distribution,we uniformly deploy (c)Overall number of identified the tags within two adjacent grids;while in the centered dis- tags after 50 query cycles tribution,we deploy all tags in the center of the antenna's Fig.6.Marginal decreasing effect

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 reader’s detection range, the major detection region is the area directly in front of the reader, giv￾ing high detection probability, 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. 4.1.3 Power Density Over the Tags The power density, i.e., the radiative energy diffused to per tag, has a big effect on the reading performance. According to Figs. 4a, 4b, 4c, and 4d, we find that even within the major detection region, there are a certain number of tags which still remain unidentified. While in the minor detection region, there are several tags which have high read ratios. This observation is related to the power density over the tags: according to Figs. 4a and 4b, while the tag density is low, the power density is fairly large, nearly all tags in the major detection region have high probability to respond; according to Figs. 4c and 4d, while the tag density increases to a large value, the diffused power is diluted among the tags, and the power density is thus reduced, causing some of the tags in the major detection region fail to respond. Besides, we observe that the missing tags in the major detec￾tion region is fairly random. According to the deployment in Fig. 4d, we randomly issue five query cycles and collect the missing tag IDs, by slightly adjusting the antenna’s posi￾tion for each query cycle. Fig. 5a illustrates the missing tag IDs in the major detection region, where the points denote the missing tags. We note that most of the missing tag’s IDs are fairly random, except a small number of tags which are always missing due to the inappropriate deployment. In order to further verify the effect of the power density, we deploy 30 tags in two distinct distributions (uniform and centered) and measure the effective identified tag size in Fig. 5b. In the uniform distribution, we uniformly deploy the tags within two adjacent grids; while in the centered dis￾tribution, we deploy all tags in the center of the antenna’s radiation area. As the power increases, we note that the identified tag size in uniform distribution is always larger than the centered distribution. This is because the power density in the former case is much larger than the latter case, more tags in the former case respond to the reader. Therefore, in order to statistically depict the probabilistic backscattering property in the major detection region, the average detection probability is essential to be used. 4.1.4 Marginal Decreasing Effect As the reader’s power is increasing, the exact read efficiency includ￾ing the scanning range, the detection probability, as well as the number of identified tags, is not increasing equally with the power. In Figs. 6a–6c, we respectively measure the width of major detection region, the average detection probability (i.e., read ratio) in major detection region, as well as the overall number of identified tags, while varying the reader’s power from 20.7 to 30.7 dBm. All three variables are increasing while the reader’s power increases. However, as the power is increased by 2 dB (i.e, 1.58 times in watt), they mainly increase with a much smaller speed on average. This obser￾vation implies that the read efficiency cannot be sufficiently enhanced by purely increasing the reader’s power. 4.1.5 Query Cycle Duration versus the Number of Identified 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, Fig. 4. Major detection region versus minor detection region. Fig. 5. Power density over the tags. Fig. 6. Marginal decreasing effect. 2276 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 11, NOVEMBER 2015

XIE ET AL.:EXPLORING THE GAP BETWEEN IDEAL AND REALITY:AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2277 8000 that all the obtained results,including the width of major 50 detection region,the detection probability,and the query cycle duration are very close to the static situation.Besides, 4D00 these experiment results are currently obtained from the set- tings constructed by the Alien reader and antennas,since 200 210 the Alien reader and antennas are designed and manufac- eer 24 22 2 2 tured according to industrial standard,these results can be Reader power p(dBm) (a)Query cycle duration (b)The number of identified tags applicable to other kinds of commercial readers conforming per cycle 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, 22 Ra383p.1aB别 and then a model of the effective scanning window to evalu- (c）Throughput ate the reading performance over multiple tags. Fig.7.Query cycle duration versus the number of identified tags per 4.2.1 Probabilistic Backscattering cycle. Suppose an arbitrary tag is separated from the reader at a causing the variation of the throughput.According to the theo- distance of d.In order for the tag to successfully backscatter retical analysis in the ideal situation,if the frame size is opti- the ID message,the reader needs to send a continuous wave mally selected,the expected number of slots as well as the to activate the tag.As the tag has a sensitivity threshold t, query cycle duration should be linearly increasing with the which is the minimum power required to activate the tag, number of identified tags per cycle.However,in realistic the incident power to the tag's antenna should be larger settings that doesn't follow at all.Figs.7a and 7b respec- than t.It is known that the power budget of conventional tively show the value of cycle duration te and the number RFID systems is forward-link limited,which implies that of identified tags per cycle ne while varying the reader's well-designed passive RFID systems are always limited by power.Note that the standard deviation of re is much larger the tag's sensitivity.Therefore,as long as the reader's power than n,which is mainly due to the randomness in the anti- ph is large enough to activate the tag,the reader is able to collision scheme.As the reader's power increases,the val-resolve the backscattered signal from the tag.We have con- ues of te and ne are both increasing,however,at different ducted experiments to evaluate the threshold t.We deploy rates.Therefore,the ratio of ne to re,i.e.,the throughput,is 20 tags together in front of the RFID reader and gradually also varying. vary their distance from 0.5 to 5 m.Then the reader executes Fig.7c shows the throughput variation with four differ- power stepping from the minimum value 15.7 dBm to the ent tag densities.We find that in all cases the throughput maximum value 30.7 dBm to identify the activation thresh- achieves the peak value when the reader's power is set to old for the reader.Fig.8a illustrates the experiment results. an appropriate value between the minimum and maximum We find that,the threshold is not strictly monotonically power.The reason is as follows:When the reader's power is increasing as the distance increases,which is mainly due to set to a small value,the number of activated tags is small,the multi-path effect.In regard to a certain distance,the acti- then due to the fairly large inter-query cycle overhead,the vation power for the reader remains fairly steady among the throughput is fairly small.As the reader's power increases, 20 tags.This infers that the value of t basically remains more tags are involved in the query cycle,the inter-query unchanged among a certain type of tags. cycle overhead is sufficiently amortized,thus the through- In the reader's read zone,i.e,the region in which the inci- put is gradually increased.When the reader's power dent power exceeds the threshold t,it is found that the increases to a fairly large value,the number of collisions in range is the longest along the center and falls off towards the query cycle is greatly increased,resulting in a large the edges.In regard to a plane at a fixed distance from the value for the cycle duration,thus the throughput is further reader,the incident power varies from the center towards decreased.This observation implies that it is neither time- the edges.Besides,the values of incident power has varian- efficient nor energy-efficient to blindly increase the reader's ces since the continuous wave issued from the reader has power,an optimal value for the reader's power should be fluctuations in terms of power.Therefore,assume the read- determined. er's power is p,in regard to a two dimensional plane at a The above experiment results and observations are distance of d from the reader,we respectively use fpr.d(,y) obtained from the static situation where the reader is stati- and gp.d(,y)to denote the average value and the variance cally deployed.In the mobile situation where the reader is of the incident power in the coordinate(,y).In the settings continuously moving,since the moving speed cannot be too where the tags are deployed in a row,we respectively sim- large due to the large number of tags to be identified,all the plify them to f()and().Fig.8b shows a diagram above properties should be preserved.In order to verify of the average value and variance of the incident power this statement,we conduct experiments in mobile situations p(r)in the one-dimensional space.Note that convention- while varying the moving speed from 0.3 to 3 m/s.We find ally the incident power achieves the maximum value in the

causing the variation of the throughput. According to the theo￾retical analysis in the ideal situation, if the frame size is opti￾mally selected, the expected number of slots as well as the query cycle duration should be linearly increasing with the number of identified tags per cycle. However, in realistic settings that doesn’t follow at all. Figs. 7a and 7b respec￾tively show the value of cycle duration tc and the number of identified tags per cycle nc while varying the reader’s power. Note that the standard deviation of tc is much larger than nc, which is mainly due to the randomness in the anti￾collision scheme. As the reader’s power increases, the val￾ues of tc and nc are both increasing, however, at different rates. Therefore, the ratio of nc to tc, i.e., the throughput, is also varying. Fig. 7c shows the throughput variation with four differ￾ent 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 cycle overhead is sufficiently amortized, thus the through￾put 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 obtained 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.3 to 3 m/s. We find that all the obtained results, including the width of major detection region, the detection probability, and the query cycle duration are very close to the static situation. Besides, these experiment results are currently obtained from the set￾tings constructed by the Alien reader and antennas, since the Alien reader and antennas are designed and manufac￾tured according to industrial standard, these results can be applicable to other kinds of commercial readers conforming 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 evalu￾ate 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 con￾ducted experiments to evaluate the threshold t. We deploy 20 tags together in front of the RFID reader and gradually vary their distance from 0.5 to 5 m. Then the reader executes power stepping from the minimum value 15.7 dBm to the maximum value 30.7 dBm to identify the activation thresh￾old for the reader. Fig. 8a illustrates the experiment results. We find that, the threshold is not strictly monotonically increasing as the distance increases, which is mainly due to the multi-path effect. In regard to a certain distance, the acti￾vation power for the reader remains fairly steady among the 20 tags. This infers 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 the 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 varian￾ces since the continuous wave issued from the reader has fluctuations in terms of power. Therefore, assume the read￾er’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 sim￾plify them to fpw;dðxÞ and gpw;dðxÞ. Fig. 8b shows a diagram of the average value and variance of the incident power p0 wðxÞ in the one-dimensional space. Note that convention￾ally the incident power achieves the maximum value in the Fig. 7. Query cycle duration versus the number of identified tags per cycle. XIE ET AL.: EXPLORING THE GAP BETWEEN IDEAL AND REALITY: AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2277

2278 IEEE TRANSACTIONS ON MOBILE COMPUTING.VOL.14.NO.11.NOVEMBER 2015 Power in dBm Free Space RFID Reader Wave from the Reader threshold RFID Tag Backscatter Wave Antenna USRP Sniffer of Sniffer(Receiver Only) AMimrtotan Distance d (a)The threshold of the reader's activation(b)The value of the incident power in the (c)Experiment settings with USRP N210 power with various distances one-dimensional space (d)The raw signal data of the interrogation between the reader and the tag (e)The normalized average value and standard deviation of the incident power Fig.8.Exploring the probabilistic backscattering. center of the read zone,and gradually decreases towards thus the measured power is P-20.log dBm.Fig.e the edges.Meanwhile,in regard to multiple tags deployed shows the measured value of the incident power to the tag. in the plane,the incident power is also affected by tag den- We normalize the measured power by dividing the maxi- sity and multi-path effect. mum received power,and illustrate the average value and In order to verify the above judgement,we conduct a the standard deviation in the figure by varying the distance number of experiments in the realistic settings of a configu- between the reader and the tag.We note that the average ration shown in Fig.8c.We set up a reader and a passive value of the incident power is gradually decreasing as the tag with a distance of 3 m,and use a USRP-based sniffer to distance increases from 0.5 to 5 m,and there indeed exist capture the incident signals at the spot of the tag's antenna. some fluctuations for the incident power to the tag. We build the sniffer based on the USRP N210 system.As As shown in Fig.8b,in regard to an arbitrary tag in the UHF RFID systems operate in the 902-928 MHz band,we row,the tag can be successfully identified if and only if the use WBX USRP daughterboards and VERT900 omni-direc- incident power is above the tag's sensitivity threshold t. tional antennas to run all experiments at a carrier frequency Due to the fluctuation of the incident power,the tag is suc- of 915 MHz.The omni-directional VERT900 antenna is con- cessfully identified with some probability,i.e.,Prlp(r)> nected to a USRP N210 device to receive.The USRP samples t.In regard to a position z in the effective scanning region, the received signals using a rate of 25 MHz.The distance note that once the average value is relatively larger than the between the tag and the USRP antenna is very close(within threshold t,as the variance is usually relatively small,the 1~2 cm),which is much smaller than the wavelength(t]will be close to 1;simi- wavelength),the multi-path effect thus cannot greatly larly,once the average value is relatively smaller than the affect the performance.In this way,we are able to measure threshold t,the detection probability Prlp()>t]will be the incident power to the RFID tag according to the cap- close to 0.This property divides the scanning region into tured signals. two distinct regions,i.e.,the major detection region and the Fig.8d shows the raw signal data of the interrogation minor detection region. between the reader and the tag.Note that,the sniffer at the spot of the tag not only receives the incident signals from the RFID reader but also receives the backscatter signals 4.2.2 Effective Scanning Window over Multiple Tags from the tag.Hence,in order to accurately measure the inci- As we have observed,the reader's effective scanning region dent power to the tag,we need to effectively eliminate the can be divided into a major detection region as well as a backscatter signal from the mixed signals.We find that dur- minor detection region.In the major detection region,most ing the query cycle there exist several slots including the tags can be detected with a probability close to 100 percent. singleton slots and the empty slots.In regard to the empty As the tag density increases,the diffused power cannot slots,since the tag does not respond at all,the captured sig- guarantee to activate all tags in the major detection region, nal only includes the incident signal from the reader to the each tag has a probability to be detected in a random tag.Based on the above understanding,we can effectively approach.Therefore,we can use the average detection prob- extract the incident power from the empty slots.As we com- ability to depict the reading performance in this region.The pare with the reference voltage Uo when the power is 1 mw,minor detection region is extending from the end of 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 den￾sity and multi-path effect. In order to verify the above judgement, we conduct a number of experiments in the realistic settings of a configu￾ration shown in Fig. 8c. We set up a reader and a passive tag with a distance of 3 m, and use a USRP-based sniffer to capture the incident signals at the spot of the tag’s antenna. We build the sniffer based on the USRP N210 system. As UHF RFID systems operate in the 902-928 MHz band, we use WBX USRP daughterboards and VERT900 omni-direc￾tional antennas to run all experiments at a carrier frequency of 915 MHz. The omni-directional VERT900 antenna is con￾nected to a USRP N210 device to receive. The USRP samples the received signals using a rate of 25 MHz. The distance between the tag and the USRP antenna is very close (within 1  2 cm), which is much smaller than the wavelength (< 1 4 wavelength), the multi-path effect thus cannot greatly affect the performance. In this way, we are able to measure the incident power to the RFID tag according to the cap￾tured signals. Fig. 8d shows the raw signal data of the interrogation between the reader and the tag. Note that, the sniffer at the spot of the tag not only receives the incident signals from the RFID reader but also receives the backscatter signals from the tag. Hence, in order to accurately measure the inci￾dent power to the tag, we need to effectively eliminate the backscatter signal from the mixed signals. We find that dur￾ing the query cycle there exist several slots including the singleton slots and the empty slots. In regard to the empty slots, since the tag does not respond at all, the captured sig￾nal only includes the incident signal from the reader to the tag. Based on the above understanding, we can effectively extract the incident power from the empty slots. As we com￾pare with the reference voltage U0 when the power is 1 mw, thus the measured power is Pw ¼ 20 log U U0 dBm. Fig. 8e shows the measured value of the incident power to the tag. We normalize the measured power by dividing the maxi￾mum received power, and illustrate the average value and the standard deviation in the figure by varying the distance between the reader and the tag. We note that the average value of the incident power is gradually decreasing as the distance increases from 0.5 to 5 m, and there indeed exist some fluctuations for the incident power to the tag. As shown in Fig. 8b, 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 fluctuation of the incident power, the tag is suc￾cessfully identified with some probability, i.e., Pr½p0 wðxÞ  t. In regard to a position 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 Pr½p0 wðxÞ  t will be close to 1; simi￾larly, once the average value is relatively smaller than the threshold t, the detection probability Pr½p0 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 region 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 percent. As the tag density increases, the diffused power cannot guarantee 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 prob￾ability to depict the reading performance in this region. The minor detection region is extending from the end of the Fig. 8. Exploring the probabilistic backscattering. 2278 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 11, NOVEMBER 2015

XIE ET AL.:EXPLORING THE GAP BETWEEN IDEAL AND REALITY:AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2279 lajor detection re0 width:w Probability Effective Scanning Window 100 p100% *100号 Scanning 0% Direction Fig.10.Continuous scanning over the tags linor detection region region In particular,the value of m is equal to,here tw is the Fig.9.The model of the effective scanning window duration in the effective scanning window,and te is the average duration of a query cycle.Moreover,T is equal to major detection region to the edge of the effective range, the ratio of the window width w to the moving speed v,i.e., with the detection probability quickly drops off to 0.Based hence mTherefore,in order to increase the detec- on the above analysis,we use a trapezoidal curve to denote tion probability p for an arbitrary tag,it is essential to (1) the expected detection probability of tags in the scanning increase the number of query cycles m as much as possible; region,as illustrated in Fig.9.In fact,due to the narrow (2)increase the detection probability p as much as possible. width of the minor detection region,the average probability In Figs.6a,6b and 7a,we illustrate the value of w,p'and for a tag to be detected in this region can be negligible. Te with various power,p.In regard to a fixed tag density, Therefore,in consideration of the actual reading perfor- we note that as the value of p increases,the value of p',w mance,we only need to focus on the major detection region. and r.are all monotonically increasing.Moreover,since the In the rest of this paper,we use the term effective scanning value of w increases much more slowly than te,the value of window to denote the major detection region.We use w and p'to denote the width and the average detection probability m=is monotonically decreasing with the value of p Therefore,we reach the following conclusion:as the moving of the effective scanning window,respectively. During continuous scanning,the effective scanning win- speed u decreases,the value of m is monotonically increas- dow is continuously moving forward with the mobile ing,while the value of p'remains unchanged.As the read- reader,as shown in Fig.10.Note that there exist overlap- er's power p increases,the value of p'is monotonically ping areas between the contiguous scanning windows.Dur- increasing,while the value of m is monotonically decreas- ing.Thus the value of p should be appropriately selected ing the continuous scanning,each tag gradually enters a to optimize the performance. minor detection region,then an effective scanning window, finally exits from a minor detection region.While within the In regard to the coverage constraints in Eq.(3)and Eq.(4), we use the parameter p to denote the probability that a tag effective scanning window,each tag has a probability to be is successfully identified after the continuous scanning.We detected for each query cycle.Therefore,in order to guaran- tee the coverage constraint,multiple query cycles should be hence propose a method (readers can refer to our previous work [4]for the detailed description)to effectively obtain issued over each tag while it is within the effective scanning window.Assume that the tags are uniformly deployed the solution of p that isphere This along the scanning area,then the tag size within the effec- shows that,as long as the detection probability p is no less tive scanning window is always constant.This infers that than for any tag,the coverage constraint is guaranteed. the number of tags involved in a query cycle mostly remains unchanged.If the mobile reader is set to a constant power and a constant moving speed,then,after multiple query 4.3 Discussion on the Model cycles,each tag has a uniform probability to be detected. 4.3.1 Property of the Model This conforms to the requirement in the coverage constraint. Suppose an arbitrary tag is expected to be queried for m In order to describe the inherent regularities of the probabi- cycles while it is within the effective scanning window,we listic backscattering,we have proposed a simple,in-depth and practical model:First,the effective scanning window is denote the detection probability in the m query cycles as p:(i=1...m).Then,the probability for an arbitrary tag to be very simple to formulate;second,the model is built based identified at least once is as follows: on in-depth understanding of the properties of the reading performance,including the major detection region,the probabilistic backscattering,the power density over tags, p)】 (9) etc;third,the model is rather practical to use in real applica- tions.Besides,this model is actually very flexible and appli- cable to various settings.The reason is as follows:in regard As the reader's power is set to a constant value,due to the to various types of tags,readers,and environment,as long uniform tag density,the probability pi(i=1...m)in the m as we can effectively collect the detection probability p'(p), query cycles should be uniform.If we use p'to denote the the window width w(p)and the average query cycle dura- uniform detection probability,then Eq.(9)is further simpli- tion te(p)through an initial phase,then we can effectively fied as follows: compute the optimal parameters for power and moving speed for time-efficiency and energy-efficiency according to p=1-(1-p)m (10) this model

major detection 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 expected detection probability of tags in the scanning region, as illustrated in Fig. 9. 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 perfor￾mance, 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 p0 to denote the width and the average detection probability of the effective scanning window, respectively. During continuous scanning, the effective scanning win￾dow is continuously moving forward with the mobile reader, as shown in Fig. 10. Note that there exist overlap￾ping areas between the contiguous scanning windows. Dur￾ing the continuous scanning, each tag gradually enters a minor detection region, then an effective scanning window, finally exits from a minor detection region. While within the effective scanning window, each tag has a probability to be detected for each query cycle. Therefore, in order to guaran￾tee 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 tag size within the effec￾tive scanning window is always constant. This infers that the number of tags involved in a query cycle mostly remains unchanged. If the mobile reader is set to a constant power and a constant moving 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  Ym 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 p0 to denote the uniform detection probability, then Eq. (9) is further simpli- fied as follows: p ¼ 1  ð1  p0 Þ m: (10) In particular, the value of m is equal to tw tc , here tw is the duration in the effective scanning window, and tc is the average duration of a query cycle. Moreover, tw is equal to the ratio of the window width w to the moving speed v, i.e., w v, hence m ¼ w vtc . 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 p0 as much as possible. In Figs. 6a, 6b and 7a, we illustrate the value of w, p0 and tc with various power, pw. In regard to a fixed tag density, we note that as the value of pw increases, the value of p0 , w and tc are all monotonically increasing. Moreover, since the value of w increases much more slowly than tc, the value of m ¼ w vtc 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 increas￾ing, while the value of p0 remains unchanged. As the read￾er’s power pw increases, the value of p0 is monotonically increasing, while the value of m is monotonically decreas￾ing. 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. We hence propose a method (readers can refer to our previous work [4] for the detailed description) to effectively obtain the solution of p, that is p  u , here u ¼ u þ ffiffiffiffiffiffiffiffiffiffiffiffi lnð1bÞ 2n q . This shows that, as long as the detection probability p is no less than u for any tag, the coverage constraint is guaranteed. 4.3 Discussion on the Model 4.3.1 Property of the Model In order to describe the inherent regularities of the probabi￾listic backscattering, we have proposed a simple, in-depth and practical model: First, the effective scanning window is very simple to formulate; second, the model is built based on in-depth understanding of the properties of the reading performance, including the major detection region, the probabilistic backscattering, the power density over tags, etc; third, the model is rather practical to use in real applica￾tions. Besides, this model is actually very flexible and appli￾cable to various settings. The reason is as follows: in regard to various types of tags, readers, and environment, as long as we can effectively collect the detection probability p0 ðpwÞ, the window width wðpwÞ and the average query cycle dura￾tion tcðpwÞ through an initial phase, then we can effectively compute the optimal parameters for power and moving speed for time-efficiency and energy-efficiency according to this model. Fig. 9. The model of the effective scanning window. Fig. 10. Continuous scanning over the tags. XIE ET AL.: EXPLORING THE GAP BETWEEN IDEAL AND REALITY: AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2279

2280 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.14.NO.11.NOVEMBER 2015 4.3.2 Scalability of the Model Current commodity RFID systems all use the directional is equivalent to ensureAs the value of w,p and te all depends on the value of pa,let w(p), antenna to send continuous wave to activate and interrogate p(p)and te(p)respectively denote the mapping function the tags.The reason of not using the omni-directional from pu to w,p'and te,then antenna is as follows:the omni-directional antenna may have very small antenna gain towards a specified direction, w(pe)-|n(1-p(pe)川 such that the effective scanning range is greatly reduced,it v=m(1-07 (11) Tc(Pw) is usually within 100~150 cm,according to our experimen- tal observation.Our effective scanning window-based then,v'is the maximum allowable moving speed to satisfy model is suitable for the RFID systems with directional the coverage constraint. antennas.It incorporates the major detection region and the Since the length of the scanning area is l,the overall scan- minor detection region,which well depict the characteristics ning time Tand the overall used energy E=T.p of the directional antennas.It uses a uniform probability to Therefore,considering the time-efficiency,in order to denote the success rate of tag identification in the scanning minimize T,it is equivalent to maximize v.Then,according window,which right agrees with the actual observation from the mobile scanning process.Therefore,our effective to Eq.(11),it is essential to maximize It is known scanning window-based model is rather scalable and that as the value of p increases,the value of w.|In(1-p) applies to most commodity RFID systems off the shelf. and re are both monotonically increasing,thus an optimized value of p should be selected to minimize T.Considering 4.3.3 Tag Response Probability in the Model the energy constraint E-ln(1-0】 (13) reader is moving in constant speed and power,then,accord- pr·te(pw) a ing to the model,as shown in Eq.(9),each tag would have a very close detection probability (i.e.,pi)for each query cycle, Considering the energy-efficiency,in order to minimize while it is within the reader's effective scanning window. E,it is equivalent to minimize,then according to Eq.(11), On the whole,according to Eq.(9),after the continuous it is essential to maximize Therefore,considering scanning,each tag is expected to have nearly the same value Pu-Te for the tag response probability,which has also been veri- the time constraint T1-m1-I (15) reader,conventionally the reader's power is set to maxi- Tc(pu) mum and the moving speed is set to a constant value which is small enough.This baseline solution is very straightfor- In regard to a certain tag density p,by enumerating the ward,which however,is neither time-efficient nor energy- efficient since excessive power is used up and the moving candidate values of the power p,we can compute the value of yr and yE.Figs.1la and 11b respectively illustrate the speed is slowed down.Besides,a number of tags are inter- rogated multiple times during continuous scanning,which value of yr and ye while varying the reader's power p We note that there exist a maximum value of yr and ye for each is unnecessary as each tag only needs to be identified once. tag density.In regard to a specified tag density p,while sat- isfying the time/energy constraint,we can use the power 5.2 Mobile Solution with Uniform Tag Density p for the maximum value of yr or ye as the optimal param- 5.2.1 Solution eter and compute the corresponding moving speed u* Without loss of generality,we first propose an optimized according to Eq.(11).In this way,the optimal solution solution for the situation with uniform tag density.Consid- (p,)for time/energy efficiency can be generated.There- ering the objective as well as the energy/time constraint,we fore,in regard to various tag densities p,we can collect the need to figure out the optimized value of p and v such that performance parameters like w,p'and te in advance,pre- the objective is achieved while the coverage constraints are compute the optimal pairs of(p),and store them in a satisfied. table.When dealing with an arbitrary tag density,we can In regard to the coverage constraint,since we need to directly use the optimal pair of(p v)to achieve the time/ guarantee p=1-(1-p)">0',i.e.,1-(1-p)>0,it energy efficiency

4.3.2 Scalability of the Model Current commodity RFID systems all use the directional antenna to send continuous wave to activate and interrogate the tags. The reason of not using the omni-directional antenna is as follows: the omni-directional antenna may have very small antenna gain towards a specified direction, such that the effective scanning range is greatly reduced, it is usually within 100  150 cm, according to our experimen￾tal observation. Our effective scanning window-based model is suitable for the RFID systems with directional antennas. It incorporates the major detection region and the minor detection region, which well depict the characteristics of the directional antennas. It uses a uniform probability to denote the success rate of tag identification in the scanning window, which right agrees with the actual observation from the mobile scanning process. Therefore, our effective scanning window-based model is rather scalable and applies to most commodity RFID systems off the shelf. 4.3.3 Tag Response Probability in the Model In regard to the tag response probability, i.e., p, during the continuous scanning, most of the tags (except only a few tags placed in the boundary) experience nearly the same process: the mobile reader continuously scans from the left side of the tag, then scans in front of the tag, and finally scans to the right side of the tag. If we consider the situation where the tags are uniformly deployed, and the mobile reader is moving in constant speed and power, then, accord￾ing to the model, as shown in Eq. (9), each tag would have a very close detection probability (i.e., pi) for each query cycle, while it is within the reader’s effective scanning window. On the whole, according to Eq. (9), after the continuous scanning, each tag is expected to have nearly the same value for the tag response probability, which has also been veri- fied in our experimental study (see Figs. 3a, 3b, and 3c). 5 CONTINUOUS SCANNING WITH MOBILE READER 5.1 Baseline Solution For both the uniform and nonuniform tag distribution, in order to effectively identify all the tags with the mobile reader, conventionally the reader’s power is set to maxi￾mum and the moving speed is set to a constant value which is small enough. This baseline solution is very straightfor￾ward, 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 inter￾rogated multiple times during continuous scanning, which is unnecessary as each tag only needs to be identified once. 5.2 Mobile Solution with 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 satisfied. In regard to the coverage constraint, since we need to guarantee p ¼ 1  ð1  p0 Þ m  u , i.e., 1  ð1  p0 Þ w vtc  u , it is equivalent to ensure v  1 j lnð1u Þj wj lnð1p0 Þj tc . As the value of w, p0 and tc all depends on the value of pw, let wðpwÞ, p0 ðpwÞ and tcðpwÞ respectively denote the mapping function from pw to w, p0 and tc, then v ¼ 1 j lnð1  u Þj wðpwÞj lnð1  p0 ðpwÞÞj tcðpwÞ ; (11) 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 ¼ pwl v . Therefore, considering the time-efficiency, in order to minimize T, it is equivalent to maximize v. Then, according to Eq. (11), it is essential to maximize wj lnð1p0 Þj tc . It is known that as the value of pw increases, the value of w j lnð1  p0 Þj and tc are both monotonically increasing, thus an optimized value of pw should be selected to minimize T. Considering the energy constraint E  a, the optimal value p w can be computed according to the following formulation: maximize yT ¼ j lnð1  p0 ðpwÞÞj wðpwÞ tcðpwÞ ; (12) subject to j lnð1  p0 ðpwÞÞj wðpwÞ pw tcðpwÞ  l j lnð1  u Þj a : (13) Considering the energy-efficiency, in order to minimize E, it is equivalent to minimize pw v , then according to Eq. (11), it is essential to maximize j lnð1p0 Þjw pwtc . Therefore, considering the time constraint T  g, the optimal value p w can be com￾puted according to the following formulation: maximize yE ¼ j lnð1  p0 ðpwÞÞj wðpwÞ pw tcðpwÞ ; (14) subject to j lnð1  p0 ðpwÞÞj wðpwÞ tcðpwÞ  l j lnð1  u Þj g (15) In regard to a certain tag density r, by enumerating the candidate values of the power pw, we can compute the value of yT and yE. Figs. 11a and 11b 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 r, while sat￾isfying the time/energy constraint, we can use the power p w for the maximum value of yT or yE as the optimal param￾eter and compute the corresponding moving speed v according to Eq.(11). In this way, the optimal solution ðp w; v Þ for time/energy efficiency can be generated. There￾fore, in regard to various tag densities r, we can collect the performance parameters like w; p0 and tc 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. 2280 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 14, NO. 11, NOVEMBER 2015

XIE ET AL.:EXPLORING THE GAP BETWEEN IDEAL AND REALITY:AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2281 10 fairly uniform tag density.In Algorithm 1,we propose a +-p-10 ▣-P-20 mobile solution for nonuniform tag density.We assume the +p-30 40 ◆p-40 nonuniform tag density along the forwarding direction can be known in advance.While the mobile reader is moving 0. forward,it continuously computes the average tag density in the current effective scanning window.As the reader's power varies in the effective range,the window width w is 26 22 not constant,thus we set the value of w to an average value Reader power p (dBm) Reader power p (dBm) of the window width.Here,we consider an offline setting (a)The value of yr (b)The value of yE where the nonuniform tag density is supposed to be known Fig.11.Compute the value of yr and ye with various values of p. in advance;if we consider an online setting where the non- uniform tag density is not known in advance,the current 5.2.2 Estimate the Tag Density tag density has to be estimated in time during the continu- According to the measured data in realistic settings,it is ous scanning.However,as multiple power levels have to be known that the tag density p has an important effect on the set for measuring data in a frequent approach,the time-effi- performance metrics.In situations where the tag density can- ciency and energy-efficiency can be affected. not be pre-fetched or the tag density varies along the forward- ing direction,it is essential to accurately estimate the current Algorithm 1.Mobile Solution for Nonuniform Tag Density tag density,such that the optimized parameters (p)can 1:INPUT:p(x):the tag density along the forwarding direc- be effectively computed.Therefore,we propose a practical tion,0≤x≤l solution to accurately estimate the tag density.Due to the 2:PROCEDURE limit of space,we omit the detailed descriptions here.Readers 3:Precompute the optimal value of reader's power for a cer- can refer to our previous work [4]for the detailed content. tain number of reference tag densities p,i.e.,p(p),accord- ing to the objective of time/energy-efficiency. 5.3 Mobile Solution with Nonuniform Tag Density 4:Setx=0.S=0. In some applications,the tags are not uniformly deployed. 5:while xfor each tag with respect to the coverage constraint,the value i=pm(p)+(P-）)-(p(p)-pe(pl》, Pu-pr of p and v should be set according to the worst case,i.e., w(p)Iln(1-p()川 the situation with the largest tag density.In this way,the U*= 1n(1-) te(pie) time-efficiency as well as the energy-efficiency cannot be achieved since excessive power is used up and the moving Set reader's power to p",set moving speed to v' speed is reduced.Therefore,it is essential to dynamically 9: Issue a new query cycle.Collect the tag IDs during the adjust the reader's power p and the moving speed v to query cycle,add them to the set S. optimize the overall performance. 10: Record the cycle duration t,update r=r+v*.t.. 11:end while 5.3.1 Algorithm 12:OUTPUT:the tag set S According to the observation in Section 4,while the mobile reader is moving forward,we note that if the tag 5.4 Extensions and Discussions density varies,the detection probability pi is varying; 5.4.1 Various Tag Distributions moreover,the number of issued query cycles m is varying, In the previous sections,we have tackled the continuous as the tag size within the effective scanning window scanning problem,respectively,for uniform tag density and changes.Hence,each tag experiences a distinct process nonuniform tag density,assuming that the RFID tags are with various values of p;and m.Therefore,it is rather dif-located along a line.This is conventionally suitable for those ficult to make the coverage requirement p*>t exactly sat- typical scenarios like scanning the books in the library,mak- isfied for all tags while achieving the objective.Based on ing an inventory of stocks in the warehouse shelves,etc.In the above understanding,we seek to propose an approxi-this situation,we can compute the optimal parameters for mate solution to solve the problem. the distance,scanning power and moving speed.However, Note that in conventional situations,the tag density in some application scenarios,the situations are more com- changes slowly along the forward direction.In current com- plicated.The tagged items can be haphazardly distributed mercial RFID systems,the reader's power p can only be in a space,such that the tags are not necessarily to be reset for each query cycle.Therefore,in regard to each query located along a line.Obviously,this scenario with haphaz- cycle,we can assume the tag density within the effective ard tag distribution is rather complicated,and it is difficult scanning window is close to uniform,since the cycle dura- to solve well based on current techniques. tion is usually small.In this way,we can reduce the situation The tag distribution is a critical issue for the continu- with nonuniform tag density into multiple snapshots with ous scanning.As long as the tag distribution is obtained

5.2.2 Estimate the Tag Density According to the measured data in realistic settings, it is known that the tag density r has an important effect on the performance metrics. In situations where the tag density can￾not be pre-fetched or the tag density varies along the forward￾ing direction, it is essential to accurately estimate the current tag density, such that the optimized parameters ðp w; v Þ can be effectively computed. Therefore, we propose a practical solution to accurately estimate the tag density. Due to the limit of space, we omit the detailed descriptions here. Readers can refer to our previous work [4] for the detailed content. 5.3 Mobile Solution with Nonuniform Tag Density In some applications, the tags are not uniformly deployed. While the mobile reader is continuously scanning the tags, the tag density may always change along the forward direc￾tion. In this situation, a constant moving speed and power for the mobile reader are no longer suitable to improve per￾formance. For example, in order to guarantee p  u for each tag with respect to the coverage constraint, the value of pw and v should be set according to the worst case, i.e., the situation with the largest tag density. In this way, the time-efficiency as well as the energy-efficiency cannot be achieved since excessive power is used up and the moving speed is reduced. Therefore, it is essential to dynamically adjust the reader’s power pw and the moving speed v to optimize the overall performance. 5.3.1 Algorithm According to the observation in Section 4, while the mobile reader is moving forward, we note that if the tag density varies, the detection probability pi is varying; moreover, the number of issued query cycles m is varying, as the tag size within the effective scanning window changes. Hence, each tag experiences a distinct process with various values of pi and m. Therefore, it is rather dif- ficult to make the coverage requirement p  t exactly sat￾isfied for all tags while achieving the objective. Based on the above understanding, we seek to propose an approxi￾mate solution to solve the problem. Note that in conventional situations, the tag density changes slowly along the forward direction. In current com￾mercial RFID systems, the reader’s power pw can only be reset for each query cycle. 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 dura￾tion is usually small. In this way, we can reduce the situation with nonuniform tag density into multiple snapshots with fairly uniform tag density. In Algorithm 1, we propose a mobile solution for nonuniform tag density. We assume the nonuniform tag density along the forwarding direction can be known in advance. While the mobile reader is moving forward, it continuously computes the average tag density in the current effective scanning window. As the reader’s power varies in the effective range, the window width w is not constant, thus we set the value of w to an average value of the window width. Here, we consider an offline setting where the nonuniform tag density is supposed to be known in advance; if we consider an online setting where the non￾uniform tag density is not known in advance, the current tag density has to be estimated in time during the continu￾ous scanning. However, as multiple power levels have to be set for measuring data in a frequent approach, the time-effi- ciency and energy-efficiency can be affected. Algorithm 1. Mobile Solution for Nonuniform Tag Density 1: INPUT: rðxÞ: the tag density along the forwarding direc￾tion, 0  x  l; 2: PROCEDURE 3: Precompute the optimal value of reader’s power for a cer￾tain number of reference tag densities r, i.e., pwðrÞ, accord￾ing to the objective of time/energy-efficiency. 4: Set x ¼ 0; S ¼ ?. 5: while x  l do 6: Compute the average tag density r according to the cur￾rent scanning window with width w. Find two closest reference tag density to r such that rl  r  ru. 7: Compute the optimal value p w and v as follows: p w ¼ pwðrlÞþð r  rl ru  rl ÞðpwðruÞ  pwðrlÞÞ; v ¼ wðp wÞ j lnð1  u Þj j lnð1  p0 ðp wÞÞj tcðp wÞ : 8: Set reader’s power to p w, set moving speed to v . 9: Issue a new query cycle. Collect the tag IDs during the query cycle, add them to the set S. 10: Record the cycle duration tc, update x ¼ x þ v tc. 11: end while 12: OUTPUT: the tag set S 5.4 Extensions and Discussions 5.4.1 Various Tag Distributions In the previous sections, we have tackled the continuous scanning problem, respectively, for uniform tag density and nonuniform tag density, assuming that the RFID tags are located along a line. This is conventionally suitable for those typical scenarios like scanning the books in the library, mak￾ing an inventory of stocks in the warehouse shelves, etc. In this situation, we can compute the optimal parameters for the distance, scanning power and moving speed. However, in some application scenarios, the situations are more com￾plicated. The tagged items can be haphazardly distributed in a space, such that the tags are not necessarily to be located along a line. Obviously, this scenario with haphaz￾ard tag distribution is rather complicated, and it is difficult to solve well based on current techniques. The tag distribution is a critical issue for the continu￾ous scanning. As long as the tag distribution is obtained, Fig. 11. Compute the value of yT and yE with various values of pw. XIE ET AL.: EXPLORING THE GAP BETWEEN IDEAL AND REALITY: AN EXPERIMENTAL STUDY ON CONTINUOUS SCANNING WITH... 2281