# Randomized Scheme for Cognizing Tags in RFID Networks and Its Optimization.

1. IntroductionRadio frequency identification (RFID) network is a network which consists of readers and tags. In an RFID network, a reader, in a contactless fashion, acquires information stored at a tag by using radio waves [1-2]. Technological development has enabled a tag to communicate with a reader in either low frequency (LF) band, mid frequency (MF) band or ultra high frequency (UHF) band. Also, tags have been improved to work not only actively, i.e., by internal power source but also passively, i.e., by being powered from a reader in a wireless fashion. Such a diversity enabled RFID networks to be easily adopted in many applications including tracking animals, paying by contactless smart cards and managing items. In addition, International Organization for Standardization (ISO) and EPCglobal released a number of standards regarding RFID networks [1-2].

Typically, in an RFID network consisting of passive tags, a reader inquires about the identities of neighboring tags and a tag responds to the inquiry of a reader. If only one tag responds and a reader successfully receives the response, the reader definitely cognizes the tag. However, two or more tags may simultaneously respond to the inquiry of a reader, i.e., they may transmit packets containing their identities at the same time. Then, the packets collide and the reader is hardly able to cognize any tag involved in the collision.

In the last decade, many efforts have been made to cognize a tag while arbitrating a packet collision [3-5]. The efforts resulted in numerous tag cognizance schemes, which are categorized into two tribes; one is a tribe of the schemes rooted in framed and slotted ALOHA [6-24] and the other is a tribe of the schemes rooted in m-ary tree scheme [25-33]. Usually, a tag cognizance scheme, which belongs to the tribe rooted in framed and slotted ALOHA, employs a time structure in which time is divided into frames and each frame contains a prescribed number of slots. In such a time structure, a tag randomly (especially, equally likely) chooses a slot in a frame and then responds with its identity during the selected slot. According to whether a tag which has been already cognized by the reader is prohibited from responding afterwards or not, the tag cognizance schemes are classified into a clan of restricted schemes [16][18] and a clan of unrestricted schemes [9][17][19][22]. Also, depending on whether the number of slots contained in each frame is fixed or varied, the tag cognizance schemes are divided into a clan of static schemes [9] and a clan of dynamic schemes [13][17][22]. A tag cognizance scheme belonging to the dynamic clan usually requires the information about the number of tags residing in the vicinity of the reader. Upon such a demand, various methods have been released for estimating the number of neighboring tags [7][10][14][17][22].

Compared with the unrestricted clan, the restricted clan is able to reduce the population of the tags which contend to respond. Thus, the probability that two or more tags respond simultaneously can be decreased, and consequently, the tag cognizance rate can be enhanced. In each frame, however, the reader may have to inform a tag of whether it was already cognized or not. As a result, the complexity is increased at the expense of the improvement in tag cognizance rate. Meanwhile, the dynamic clan may find an optimal number of slots per frame which maximizes the tag cognizance rate. However, such an optimization must be based on continual estimations of the number of neighboring tags. Thus, the dynamic clan bears higher complexity than the static clan. Both of the restricted clan and the dynamic clan may be excessively complicated or sophisticated for an RFID network that supports a relatively small number of tags. Also, these clans may be inappropriate for inexpensive applications which can not endure economic burdens brought by high complexity.

In this paper, bearing in mind inexpensive applications that support only a few tags, we confine our attention to the tag cognizance schemes which belong to the unrestricted as well as static clan. Conventionally, a tag cognizance scheme belonging to such a clan chooses a single slot in a frame and responds during the selected slot. Aiming at improving the tag cognizance rate while not losing simplicity, we propose a randomized scheme, where a tag is able to choose multiple slots in a probabilistic fashion and repeats responding in each selected slot. Then, we derive an exact expression for the cognizance rate attained by the randomized scheme. The cognizance rate can be maximized by employing an optimal value for a key design parameter called probability of seizing an opportunity. Unfortunately, the exact expression for the cognizance rate is not so tractable as to find such an optimal value in an analytical fashion. As an alternative way, we present a tight upper bound on the cognizance rate and yield an exact expression for the upper bound. In a closed form, we then obtain a nearly optimal value for the probability of seizing an opportunity, which maximizes the upper bound rather than the cognizance rate itself. Finally, we provide numerical examples on the cognizance rate achieved by the randomized scheme. Through the examples, we demonstrate a high precision of the nearly optimal value by adopting a measure called relative change. Also, we confirm that the randomized scheme, which employs a nearly optimal value for the probability of seizing an opportunity, is able to dominate the conventional scheme in cognizance rate. Furthermore, we reveal that the randomized scheme is robust to the fallacy that the reader believes or guesses a wrong number of neighboring tags.

In section 2, we propose and describe a randomized scheme for cognizing tags. In section 3, we derive an exact expression for the cognizance rate achieved by the randomized scheme. In section 4, we present an upper bound on the cognizance rate and find an exact expression for the upper bound. In a closed form, we then obtain an exact expression for the nearly optimal value (for the probability of seizing an opportunity) which maximizes the upper bound rather than the cognizance rate itself. Section 5 is devoted to numerical examples, which demonstrate a high precision of the nearly optimal value, dominance of the randomized scheme in cognizance rate and robustness of the randomized scheme to a lack of information about the number of tags.

2. Randomized Scheme

In this section, we consider an RFID network which consists of a single reader and many tags residing in the vicinity of the reader. (See Fig. 1) Then, we propose a randomized scheme for the reader to cognize tags and describe the details of the scheme.

In the randomized scheme, as shown in Fig. 2, time is divided into frames. Then, a frame is partitioned into an inquiry part and a response part. Also, a response part is divided into a prescribed number of slots. (A slot is a time interval in which a tag is able to transmit a packet containing the identity of the tag.)

On such a time structure, the randomized scheme behaves as follows: First, the reader inquires about the identities of neighboring tags using the inquiry part of a frame. Secondly, upon reception of the inquiry, a tag selects a number of slots to send a packet containing the identity of the tag. For this purpose, a prescribed number of opportunities are provided to a tag. (Let K denote the number of opportunities.) At each opportunity, the tag seizes the opportunity with probability p [member of] (0,1] while it passes up the opportunity with probability 1 - p. Once the tag seizes the opportunity, it equally likely selects a slot among the slots contained in the response part. Thirdly, the tag repeats responding with a packet (which encapsulates the identity of the tag) in the selected slots of the response part. Note that a slot may be selected multiple times. In such a case, however, the tag responds in the slot only once. Fig. 3 summarizes the behaviors of the reader and tags according to the randomized rule.

3. Analysis of Cognizance Rate

The cognizance rate is roughly defined by the average number of tags that the reader cognizes per unit time. The cognizance rate is a major performance measure for evaluating tag cognizance schemes. In this section, we derive an exact expression for the cognizance rate attained by the randomized scheme. For this purpose, we consider an RFID network in which M tags, denoted by [[tau].sub.1],... [[tau].sub.M], are scattered around a single reader. In the network, time is divided into frames. Also, a frame is partitioned into inquiry part and response part, where the length of the inquiry part is equal to the duration of A [member of] N slots and the response part consists of B [member of] N slots.

3.1 Conventional Scheme

In this section, for a comparative evaluation of the randomized scheme, we consider a conventional scheme in the restricted as well as static clan. Then, we derive an exact expression for the cognizance rate achieved by the conventional scheme. In the conventional scheme, every tag equally likely selects a slot in each frame. Then, all the tags respond during their selected slots, respectively. Let [X.sub.n] denote the number of tags that the reader cognizes during the th frame for n [member of] {1, 2,...}. Then, the cognizance rate achieved by the conventional scheme, denoted by [[rho].sub.c], is defined as follows.

[mathematical expression not reproducible] (1)

in tags/slot. Since [X.sub.1], [X.sub.2],... are independent and identically distributed, the cognizance rate is yielded by

[mathematical expression not reproducible] (2)

from the strong law of large numbers [34]. Note that [X.sub.n] is equivalent to the number of boxes filled with only one ball when M balls are equally likely put into B boxes [35]. The following theorem shows an exact expression for the cognizance rate achieved by the conventional scheme.

Theorem 1. The cognizance rate achieved by the conventional scheme

[mathematical expression not reproducible] (3)

in tags/slot.

The proof of the theorem is given in the appendix.

3.2 Randomized Scheme

In the randomized scheme, as described in section 2, a tag is afforded K opportunities for making a selection of a slot in each frame. Then, the tag seizes an opportunity with probability p. Let [X.sub.n] represent the number of tags that the reader cognizes during the nth frame. Then, the cognizance rate attained by the randomized scheme, denoted by [[rho].sub.h], is defined by

[mathematical expression not reproducible] (4)

in tags/slot. Since [X.sub.1], [X.sub.2],... are mutually independent and identically distributed,

[mathematical expression not reproducible] (5)

by the strong law of large numbers [34].

Differently from the conventional scheme, the randomized scheme allows a reader to cognize a same tag many times in a frame. Considering such a difference, we obtain the expected value of [X.sub.n] as follows. Let [S.sub.mn] denote the number of slots in which the tag [[tau].sub.m] responds during the th frame. Let [R.sub.mn] denote the number of slots in which the reader cognizes the tag [[tau].sub.mn]. Then, [R.sub.mn] [less than or equal to] [S.sub.mn] obviously. Set

[mathematical expression not reproducible] (6)

for m [member of] {1,... , M}, where [I.sub.c] is the indicator function such that

[mathematical expression not reproducible] (7)

Since the reader may cognize a same tag in two or more slots during a frame, [U.sub.mn] indicates whether the reader cognizes the tag [[tau].sub.mn] or not during the nth frame. Thus, we have

[X.sub.n] = [U.sub.1n] +... + [I.sub.Mn] (8)

for n [member of] {1, 2,...}. Note that E([U.sub.mn]) =P ([R.sub.mn]) [greater than or equal to] 1) from (6). Also, E ([U.sub.1n]) =... = E ([U.sub.Mn]) by symmetry. Thus, the cognizance rate can be rewritten by

[mathematical expression not reproducible] (9)

The following theorem shows an exact expression for the cognizance rate attained by the randomized scheme.

Theorem 2. The cognizance rate attained by the randomized scheme

[mathematical expression not reproducible] (10)

where

[mathematical expression not reproducible] (11)

A proof of the theorem is given in the appendix.

Fig. 4 shows the cognizance rate attained by the randomized scheme over the space made of the number of opportunities and the probability of seizing an opportunity. In this figure, the number of tags is fixed to 5. Also, the inquiry and response parts are set to be made of 1 and 3 slots, respectively. Given number of opportunities, we observe that the cognizance rate increases until the probability of seizing an opportunity reaches a certain value. However, the cognizance rate rather decreases as the probability of seizing an opportunity is over the value. Such an observation indicates that there is an optimal value for the probability of seizing an opportunity, which maximizes the cognizance rate.

Fig. 5 shows three curves with respect to the probability of seizing an opportunity p. These curves respectively demonstrate (i) the cognizance rate attained by the randomized scheme [[rho].sub.R], which is yielded by (10), (ii) an estimate of the cognizance rate [[rho].sub.R], which is obtained by a simulation method and (iii) the cognizance rate achieved by the conventional scheme [[rho].sub.C], which is calculated by (3). In this figure, the number of tags is fixed to 5 and the inquiry and response parts are set to be made of 1 and 3 slots, respectively. Also, the number of opportunities is given by 3. In Fig. 5, we observe that [[rho].sub.R] almost coincides with [[rho].sub.R]. In cognizance rate, we also notice that the randomized scheme is able to dominate the conventional scheme by employing a proper value for p. Furthermore, we observe that we can optimize the randomized scheme as to maximize the cognizance rate by adopting an optimal value for p.

Unfortunately, (10) is not so tractable to find an optimal value for p in a closed form. As a result, finding an optimal value for p needs a numerical method. In the next section, we thus seek an alternative way to find a nearly optimal value for p in a closed form.

4. Optimization of Randomized Scheme

To enhance the cognizance rate attained by the randomized scheme, it is of necessity to find an optimal value for the probability of seizing an opportunity. Apparently, it is preferred to obtain the optimal value in a closed form. However, the expression for the cognizance rate in (10) is not so tractable as to obtain an optimal value in a closed form. As an alternative way, we find an upper bound on the cognizance rate and obtain a nearly optimal value for the probability of seizing an opportunity, which maximizes the upper bound rather than the cognizance rate itself, in a closed form. Then, we investigate the precision of the nearly optimal value.

Set

[Y.sub.n] = [R.sub.1n] +... + [R.sub.Mn] (12)

for n [member of]{1, 2,...}. Then, [Y.sub.n] represents the number of slots in which the reader cognizes a tag. Note that [Y.sub.1],[Y.sub.2],... are mutually independent and identically distributed. Recall that [X.sub.n] represents the number of tags that the reader cognizes during the nth frame. Then, [Y.sub.n] [less than or equal to] [X.sub.n] almost surely since [R.sub.mn] [less than or equal to] [U.sub.mn] almost surely. Also, E([Y.sub.n]) [less than or equal to] E ([X.sub.n]). Thus, we have an upper bound on the cognizance rate, denoted by [[bar.[rho]].sub.R], as follows:

[mathematical expression not reproducible] (13)

The following theorem shows an exact expression for the upper bound [[bar.[rho]].sub.R] in a closed form.

Theorem 3. The upper bound [[bar.[rho]].sub.R] on the cognizance rate attained by the randomized scheme

[mathematical expression not reproducible] (14)

A proof of the theorem is given in the appendix.

Fig. 6 shows the upper bound on the cognizance rate over the space made of the number of opportunities and the probability of seizing an opportunity. In this figure, the number of tags is fixed to 5. Also, the inquiry and response parts are set to be made of 1 and 3 slots, respectively. Given number of opportunities, the upper bound exhibits a similar tendency as the cognizance rate in Fig. 4.

Fig. 7 shows the cognizance rate and its upper bound with respect to the probability of seizing an opportunity. In this figure, the number of tags is fixed to 5 and the inquiry and response parts are set to be made of 1 and 3 slots, respectively. Also, the number of opportunities are set to be 3. We observe that the upper bound is tight. Moreover, we notice that the nearly optimal value, which maximizes the upper bound, is close to the true optimal value that maximizes the cognizance rate.

The expression for the cognizance rate given in (10) is not so tractable as to find an optimal value in a closed form. From (14), however, we can easily find a nearly optimal value, which is given in the following theorem.

Theorem 4. Given number of opportunities K [member of] N, the upper bound [[bar.[rho]].sub.R] is maximized by a value for the probability of seizing an opportunity, denoted by [p.sup.+], such that

[mathematical expression not reproducible] (15)

Also, the maximum value of the upper bound

[mathematical expression not reproducible] (16)

for all K [member of] N.

A proof of the theorem is given in the appendix.

5. Numerical Examples

Using the formulae given by the theorems 1 to 4, we present numerical examples which shows how precise the nearly optimal value for the probability of seizing an opportunity is and whether the randomized scheme is able to dominate the conventional scheme in cognizance rate or not.

To measure the precision of the nearly optimal value, we introduce the relative change of the cognizance rate, which is defined by

[mathematical expression not reproducible] (17)

where p* is an optimal value for the probability of seizing an opportunity which maximizes the cognizance rate while [p.sup.+] is a nearly optimal value which maximizes the upper bound on the cognizance rate. Obviously, a small value of the relative change indicates a high precision of the nearly optimal value. Fig. 8 shows the relative change over the space made of three parameters; number of tags, length of response part and number of opportunities. In this figure, the inquiry part is set to be made of a single slot. In Fig. 8, we observe that the relative change remains below 0.7% in any case. Such an observation strongly implies that the nearly optimal value is highly precise.

Fig. 9 shows the cognizance rate attained by the randomized scheme. In this figure, the inquiry part is made of a single slot and the number of opportunities is fixed to 1. Also, it is assumed that the reader exactly knows the number of neighboring tags and employs the nearly optimal value for the probability of seizing an opportunity. In Fig. 9, we observe that the randomized scheme is able to dominate the conventional scheme in cognizance rate over a wide range of the number of tags.

In an RFID network, a reader may have either wrong information or no information about the number of neighboring tags. In such a situation, the reader may either believe in a wrong number of tags or guess a wrong number. Fig. 10 considers such a situation and shows the impact of believing or guessing a wrong number of tags. In this figure, the inquiry and response parts are made of 1 and 3 slots, respectively. Also, the number of opportunities is fixed to 3. In Fig. 10, we observe that the randomized scheme exhibits a better cognizance rate than the conventional scheme as far as the number that the reader believes or guesses is not significantly smaller than the true number of tags.

6. Conclusion

In this paper, we considered an RFID network which consists of a single reader and many tags. Such a network needs a tag cognizance scheme, which is able to arbitrate among the tags contending to respond. Bearing in mind inexpensive applications, which support a relatively small number of tags, we confined our attention to the clan of unrestricted and static schemes. Then, aiming at enhancing tag cognizance rate as well as not losing simplicity than a conventional scheme, we proposed a randomized scheme for cognizing tags. To evaluate the proposed scheme, we then derived an exact expression for the cognizance rate attained by the randomized scheme. The cognizance rate can be maximized by employing an optimal value for the probability of making a selection. Unfortunately, the exact expression is not so tractable as to find an optimal value in an analytical fashion. As an alternative way, we thus developed a tight upper bound on the cognizance rate and presented an exact expression for the upper bound. In a closed form, we then obtained a nearly optimal value (for the probability of seizing an opportunity) which maximizes the upper bound. Numerical examples showed that the relative change of cognizance rate is extremely low and the nearly optimal value is thus highly precise. Also, numerical examples confirmed that the randomized scheme is able to dominate the conventional scheme in cognizance rate by employing the nearly optimal value. Furthermore, numerical examples revealed that the randomized scheme is robust to the fallacy that the reader believes or guesses a wrong number of neighboring tags.

References

[1] B. Glover and H. Bhatt, "RFID Essentials," O'Reilly Media, 2006.

[2] K. Finkenzeller, "RFID Handbook--Fundamentals and Applications in Contactless Smart Cards, Radio Frequency Identification and Near-field Communication," John Wiely & Sons, 3rd edition, 2010. Article (CrossRef Link)

[3] D. Shih, P. Sun, D. Yen, and S. Huang, "Taxonomy and Survey of RFID Anti-collision Protocols," Elsevier Computer Communications, vol. 29, pp. 2150-2166, 2006. Article (CrossRef Link)

[4] D. Klair, K. Chin and R. Raad, "A Survey and Tutorial of RFID Anti-collision Protocols," IEEE Communications Surveys and Tutorials, vol. 12, no. 3, pp. 400-421, 3rd Quarter 2010. Article (CrossRef Link)

[5] L. Zhu and T. Yum, "A Critical Survey and Analysis of RFID Anti-collision Mechanisms," IEEE Communications Magazine, vol. 49, no. 5, pp. 214-221, May 2011. Article (CrossRef Link)

[6] F. Schoute, "Dynamic Frame Length ALOHA," IEEE Transactions on Communications, vol. 31, no. 4, pp. 565-568, April 1983. Article (CrossRef Link)

[7] H. Vogt, "Efficient Object Identification with Passive RFID Tags," in Proc. of Proceedings of International Conference on Pervasive Computing 2002, Zurich, Switzerland, pp. 98-113, April 2002. Article (CrossRef Link)

[8] H. Vogt, "Multiple Object Identification with Passive RFID Tags," in Proc. of Proceedings of IEEE International Conference on Man and Cybernetics, Hammamet, Tunisia, pp. 6-13, October 2002. Article (CrossRef Link)

[9] Philips Semiconductors, SL2 ICS 11 I-code UID Smart Label IC Functional Specification. revision 3.0, January 2004.

[10] H. Choi, J. Cha and J. Kim, "Fast Wireless Anti-collision Algorithm in Ubiquitous ID System," in Proc. of Proceedings of IEEE Vehicular Technology Conference Fall 2004, Los Angeles, U.S.A., pp. 4589-4592, September 2004. Article (CrossRef Link)

[11] B. Zhen, M. Kobayashi and M. Shimizu, "Framed ALOHA for Multiple RFID Objects Identification," IEICE Transactions on Communications, vol. E88-B, no. 3, pp. 991-999, March 2005. Article (CrossRef Link)

[12] J. Cha and J. Kim, "Novel Anti-collision Algorithms for Fast Object Identification in RFID System," in Proc. of Proceedings of International Conference on Parallel and Distributed Systems 2005, Fukuoka, Japan, pp. 63-67, July 2005. Article (CrossRef Link)

[13] S. Lee, S. Joo and C. Lee, "An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification," in Proc. of Proceedings of International Annual Conference on Mobile and Ubiquitous Systems: Networking and Services 2005, San Diego, U.S.A., pp. 166-172, November 2005. Article (CrossRef Link)

[14] J. Park, M. Chung and T. Lee, "Identification of RFID Tags in Framed-slotted ALOHA with Tag Estimation and Binary Splitting," in Proc. of Proceedings of International Conference on Communications and Electronics, pp. 368-372, April 2006. Article (CrossRef Link)

[15] W. Chen and G. Lin, "An Efficient Anti-collision Method for Tag Identification in a RFID System," IEICE Transactions on Communications, vol. E89-B, no. 12, pp. 3386-3392, December 2006. Article (CrossRef Link)

[16] M. de Azambuja, C. Marcon and F. Hessel, "Survey of Standardized ISO 18000-6 RFID Anti-collision Protocols," in Proc. of Proceedings of International Conference on Sensor Technologies and Applications 2008, Cap Esterel, France, pp. 468-473, August 2008. Article (CrossRef Link)

[17] J. Park, J. Ha and C. Choi, "Bayesian Cognizance of RFID Tags," Journal of IEIE, vol.46, no. 5, pp. 524-531, May 2009.

[18] J. Park, J. Ha, S. Yoon, and C. Choi, "Performance of Tag Cognizance Scheme Using Tag Separation in RFID Networks," in Proc. of Proceedings of IEIE/IEICE International Technical Conference on Circuits and Systems, Computers and Communications 2009, Jeju, Korea, pp. 920-921, July 2009.

[19] J. Park, W. Shin, J. Ha, and C. Choi, "Tag Cognizance Performance of Tag Purification in RFID Networks," in Proc. of Proceedings of IEIE/IEICE International Technical Conference on Circuits and Systems, Computers and Communications 2009, Jeju, Korea, pp. 922-923, July 2009.

[20] M. Bueno-Delgado, J. Vales-Alonso and F. Gonzalez-Castario, "Analysis of DFSA Anti-collision Protocols in Passive RFID Environments," in Proc. of Proceedings of Annual IEEE Conference of Industrial Electronics 2009, Porto, Portugal, pp. 2610-2617, November 2009. Article (CrossRef Link)

[21] L. Zhu and T. Yum, "Optimal Framed ALOHA Based Anti-collision Algorithms for RFID Systems," IEEE Transactions on Communications, vol. 58, no. 12, pp. 3583-3592, December 2010. Article (CrossRef Link)

[22] J. Kim, J. Park, J. Ha, H. Seo, and C. Choi, "Retrospective Maximum Likelihood Decision Rule for Tag Cognizance in RFID Networks," Journal of IEIE, vol. 48, no. 2, pp. 128-135, February 2011.

[23] D. Lee, J. Choi and W. Lee, "OFSA: Optimum Frame-slotted ALOHA for RFID Tag Collision Arbitration," KSII Transactions on Internet and Information Systems, vol. 5, no. 11, pp. 1929-1945, November 2011. Article (CrossRef Link)

[24] S. Dhakal and S. Shin, "Precise-optimal Length Based Collision Reduction Scheme for Frame Slotted ALOHA RFID Systems," KSII Transactions on Internet and Information Systems, vol. 8, no. 1, pp.165-182, January 2014. Article (CrossRef Link)

[25] J. Hayes, "An Adaptive Technique for Local Distribution," IEEE Transactions on Communications, vol. 26, no. 8, pp. 1178-1186, August 1978. Article (CrossRef Link)

[26] B. Tsybakov and V. Mikhailov, "Free Synchronous Packet Access in a Broadcast Channel with Feedback," Problems of Information Transmission, vol. 14, no. 4, pp. 259-280, October-December 1978.

[27] J. Capetanakis, "Tree Algorithm for Packet Broadcast Channels," IEEE Transactions on Information Theory, vol. 25, no. 5, pp. 505-515, September 1979. Article (CrossRef Link)

[28] D. Hush and C. Wood, "Analysis of Tree Algorithms for RFID Arbitration," in Proc. of Proceedings of IEEE International Symposium on Information Theory, Mexico City, U.S.A., pp. 107-107, August 1998. Article (CrossRef Link)

[29] J. Myung and W. Lee, "Adaptive Binary Splitting: An RFID Tag Collision Arbitration Protocol for Tag Identification," in Proc. of Proceedings of IEEE International Conference on Broadband Communications, Networks, Systems 2005, Boston, U.S.A., pp. 347-355, October 2005. Article (CrossRef Link)

[30] J. Myung, W. Lee and J. Srivastava, "Adaptive Binary Splitting for Efficient RFID Tag Anti-collision," IEEE Communications Letters, vol. 10, no. 3, pp. 144-146, March 2006. Article (CrossRef Link)

[31] S. Kim and P. Park, "An Efficient Tree-based Tag Anti-collision Protocol for RFID System," IEEE Communications Letters, vol. 11, no. 5, pp. 449-451, May 2007. Article (CrossRef Link)

[32] J. Ryu, H. Lee, Y. Seok, T. Kwon, and Y. Choi, "A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID System," in Proc. of Proceedings of International Conference on Communications 2007, Glasgow, U.K., pp. 5981-5986. June 2007. Article (CrossRef Link)

[33] H. Jung, "A Memory Efficient Anti-collision Protocol to Identify Memoryless RFID Tags," KIPS Journal of Information Processing Systems, vol. 11, No. 1, pp. 95-103, March 2015. Article (CrossRef Link)

[34] T. Ferguson, A Course in Large Sample Theory. Chapman & Hall, 1996. Article (CrossRef Link)

[35] W. Feller, "Introduction to Probability Theory and Its Applications," John Wiley & Sons, 1957.

Appendix

A.1 Proof of theorem 1

Let [Z.sub.Bn] denote the number of tags that the reader cognizes in the bth slot of the nth frame for b [member of] {1,... , B} and n [member of] {1,... , B}. Then, the number of tags that the reader cognizes during the th frame is represented by

[mathematical expression not reproducible] (A1)

for n [member of] {1,... , B}. Also, the expected number of such tags

E ([X.sub.n]) = BP ([Z.sub.Bn] - 1) (A2)

since [X.sub.1n],... , [Z.sub.Bn] are identically distributed by symmetry. Note that {[Z.sub.Bn] = 1} is equivalent to the event that only one of the M tags responds in the bth slot. Thus, we have

[mathematical expression not reproducible] (A3)

Therefore, the cognizance rate achieved by the conventional scheme

[mathematical expression not reproducible] (A4)

A.2 Proof of theorem 2

Recall that [S.sub.mn] denotes the number of slots in which the tag [[tau].sub.m] responds while [R.sub.mn] represents the number of tags that the reader cognizes during the nth frame. Then,

[mathematical expression not reproducible] (A5)

First, let [T.sub.mn] denote the number of opportunities at which the tag [[tau].sub.m] makes a selection during the nth frame. Then, [T.sub.mn] has the binomial distribution with parameters K and p, i.e.,

[mathematical expression not reproducible] (A6)

for t [member of] {0,... , K} since a tag independently seizes an opportunity with probability p. Also, we have

[mathematical expression not reproducible] (A7)

where the conditional event {[S.sub.mn] = s} given {[T.sub.mn] = t} is equivalent to the event that B - s boxes are empty when t balls are put into B boxes in the classical occupancy problem [35]. Thus,

[mathematical expression not reproducible] (A8)

From (A6) and (A8), we have

[mathematical expression not reproducible] (A9)

Secondly, suppose that the tag [[tau].sub.m] responds in s slots, denoted by [mathematical expression not reproducible] for ([[pi].sub.1],... , [[pi].sub.s]) [member of] [{1,... , B}.sup.s] such that 1 [less than or equal to] [[pi].sub.1] <... < [[pi].sub.s] [less than or equal to] B. Set [A.sub.d] denote the event that no other tag (except the tag [[tau].sub.m]) responds in the slot [mathematical expression not reproducible] for d [member of] {1,... , s}. Then,

P([R.sub.mn] [greater than or equal to] 1|[S.sub.mn] = s) = P([A.sub.1] [union]... [union] [A.sub.s]). (A10)

Let [q.sub.c] denote the probability that the intersection of any c of [A.sub.1],... , [A.sub.s] takes place, i.e.,

[mathematical expression not reproducible] (A11)

for ([v.sub.1],... , [v.sub.c]) [member of] [{1,... , s}.sup.c] such that 1 [less than or equal to] [v.sub.1] <.. < [v.sub.c] [less than or equal to] s. Then,

[mathematical expression not reproducible] (A12)

by symmetry. Note that

[mathematical expression not reproducible] (A13)

From (A10), (A12) and (A13), we thus have

[mathematical expression not reproducible] (A14)

Therefore, from (A9) and (A14), we obtain an exact expression for the cognizance rate attained by the randomized scheme in (10).

A.3 Proof of theorem 3

Recall that [Z.sub.Bn] denote the number of tags that the reader cognizes in the bth slot of the nth frame. Then, the number of slots in which the reader cognizes a tag

[Y.sub.n] = [Z.sub.1n] +... + [Z.sub.Bn] (A15)

for n [member of] {1, 2,... }. Note that

E([Y.sub.n]) = BP ([Z.sub.Bn] = 1) (A16)

since [Z.sub.1n],... , [Z.sub.Bn] are identically distributed by symmetry. Let [H.sub.mbn] indicate whether the reader cognizes the tag [[tau].sub.m] or not in the bth slot of the nth frame, i.e.,

[mathematical expression not reproducible] (A17)

Then,

[Z.sub.Bn] = [H.sub.1bn] +... + [H.sub.Mbn] (A18)

for b [member of] {1,... , B} and n [member of] {1, 2,...}. Since [H.sub.1bn],... , [H.sub.Mbn] are identically distributed by symmetry, we have

E([Z.sub.Bn]) = MP([H.sub.mbn] = 1) (A19)

Note that {[H.sub.mbn] = 1} is the event that only the tag [[tau].sub.m] responds in the bth slot of the nth frame. Thus,

[mathematical expression not reproducible] (A20)

Therefore, we have

[mathematical expression not reproducible] (A21)

A.4 Proof of theorem 4

Note that the upper bound [[bar.[rho]].sub.R] is a differentiable function of p. By differentiating [[bar.[rho]].sub.R] with respect to p, we find a critical point of [[bar.[rho]].sub.R], denoted by p, as follows:

[mathematical expression not reproducible] (A22)

The upper bound [[bar.[rho]].sub.R] is a monotone increasing function of p [member of] [0, p) while it is monotone decreasing in p [member of] (p, [infinity]). Thus, p is a maximum point. Also, note that

[mathematical expression not reproducible] (A23)

Therefore, the upper bound on the cognizance rate [[bar.[rho]].sub.R] is maximized by a value of p, denoted by [p.sup.+], such that

[mathematical expression not reproducible] (A24)

Substituting [p.sup.+] for p in (A21), we have the maximum cognizance rate that the randomized scheme can attain as follows.

[mathematical expression not reproducible] (A25)

Cheon Won Choi

Department of Applied Computer Engineering, Dankook University Yongin, Gyeonggi Do, 16890, Korea

[e-mail: cchoi@dku.edu]

(*) Corresponding author: Cheon Won Choi

Received August 6, 2017; accepted October 28, 2017; published April 30, 2018

Cheon Won Choi received the B.S. degree and the M.S. degree in electronics engineering from Seoul National University, Korea, and the Ph.D. degree in electrical engineering from the University of California at Los Angeles, U.S.A. in 1986, 1988, and 1996, respectively. From 1996 to 1997, Dr. Choi was an engineer at IRI Computer Communications Corporation. Since 1997, he has been on the faculty of Dankook University, Korea, where he is presently a professor at the department of applied computer engineering. From 2006 to 2008, he served as the chief information officer at Dankook University. In 2011, he was appointed as the chair of the research institute for convergence of information and telecommunications technologies at Dankook University and led the institute for four years. His research interests include medium access control and resource allocation in wireless networks, and application of queueing theory and game theory to performance analysis. He is a senior member of IEEE, a life member of IEIE, a life member of KICS, and a member of KSII.

http://doi.org/10.3837/tiis.2018.04.015

Printer friendly Cite/link Email Feedback | |

Author: | Choi, Cheon Won |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Apr 1, 2018 |

Words: | 5840 |

Previous Article: | Scheduling of Concurrent Transactions in Broadcasting Environment. |

Next Article: | MLPPI Wizard: An Automated Multi-level Partitioning Tool on Analytical Workloads. |

Topics: |