Bounds on Expected Cognition Completion Time in RFID Networks Employing Static Naive MAC Scheme

Ⅰ. Introduction

Radio frequency identification (RFID) is a technology which enables a reader to attain information stored at a tag by using radio frequency (RF) waves in a contactless fashion^[1]. RFID networks, which consist of readers and neighboring tags, have been deployed in various places, e.g., food industry for tracing the history of food, healthcare field for controlling blood transfusion, manufacturing industry for tracking the position of a component in the manufacturing chain, and construction industry for monitoring a construction process^[2]. Whatever an RFID networkis used for, a basic mission of a reader is to cognize nearby tags, i.e., to collect identification numbers of them, since the reader usually has no information about the surrounding tags a priori^[3]. In order to cognize neighboring tags, a reader broadcasts a packet that inquires about the identification numbers of the tags lying in the vicinity of the reader. Once a tag receives the inquiry packet, the tag responds to the reader by sending a packet that contains the identity of the tag.

An RFID network often consists of a single reader and multiple tags sojourning in the environs of the reader. Then, a medium access control (MAC) scheme is needed to support numerous tags, which are geographically scattered and mutually incommunicable, to successfully deliver their packets to the common reader in a wireless fashion. Furthermore, two or more tags may almost simultaneously respond to the reader in such an star-configured RFID network. Then, a collision inevitably occurs among the packets bearing the identities of the tags^[4]. Consequently, the reader may not be able to cognize any tag involved in the collision. Thus, the MAC scheme, which is adopted for supporting many tags to be able to successfully deliver their packets in an RFID network, should also be equipped with the function of arbitrating collisions among the packets sent by some tags. Many efforts have been made to arbitrate a collision that happens between the packets simultaneously sent by some tags in an RFID network. Such efforts brought a large number of collision arbitration methods^[5-13]. These methods are categorized into two groups; one is the group of collision arbitration methods rooted in framed slotted ALOHA^[14] and the other is the group of collision arbitration methods based on tree scheme^[15-17]. In a MAC scheme that employ a collision arbitration method rooted in framed slotted ALOHA, time is divided into frames and each frame is again partitioned into a number of slots. First, the number of slots provided in each frame can be either identically fixed or dynamically varied. According to whether a constant number of slots are provided in each frame or not, MAC schemes adopting collision arbitration methods rooted in framed slotted ALOHA are classified into static and dynamic classes. Secondly, the reader can announce the list of the tags that the reader has cognized in the previous frame. According to whether the reader announces the previously cognized tags or not, MAC schemes using collision arbitration methods based on framed slotted ALOHA are also stratified into naive and sophisticated classes^[3].

A single-reader multiple-tag RFID network is typically deployed to gather the information about the items on each of which a tag is attached. For example, a single-reader multiple-tag RFID network can be used for automatic check-out at supermarkets^[18]. In such an application, the reader should be able to cognize all the neighboring tags in a limited time. Thus, it should be possible to expect the time elapsed until the reader completely cognizes all the nearby tags. Therefore, it is of utmost importance to analyze thecognition completion time, i.e., the time elapsed until the reader finishes cognizing all the tags. Note that the cognition completion time is randomsince collisions occur in a random fashion. Thus, it is of necessity to investigate distributional characteristics of the cognition completion time. Despite the importance of such an analysis, however, only a few research works have been reported. In ^[19], a single-reader multiple-tag RFID network which adopted a MAC scheme belonging to the static naive class was considered. Then, the probability that the reader finishes cognizing all the tags in a finite number of frames were formulated. Also, closed-form expressions of cognition completion probabilities were yielded for short cognition completion times. In ^[20], a single-reader multiple-tag RFID network was assumed to employ a static naive MAC scheme. Then, an approximate value of the mean cognition completion time was derived.

In this paper, we consider an RFID network that consists of single reader and multiple tags near the reader. The RFID network is also assumed to employ a MAC scheme rooted in framed slotted ALOHA which belongs to the static naive class. In the RFID network, we analyze the cognition completion time, i.e., the time elapsed until the reader completely cognizes all the tags. Specifically, a discrete-time homogeneous non-decreasing Markov chain is constructed on a finite space so that the cognition completion time is represented by a hitting time of the Markov chain. Unfortunately, even the expected value of the hitting time is not yielded in a tractable form, hence the expected cognition completion time is not either. As an alternative, we develop lower and upper bounds on the expected cognition completion time by taking steps below. To attain a lower bound, we create first-order stochastically dominating random variables^[21] and build a fast-converging Markov chain^[22] by using them. Then, a lower bound on the expected cognition completion time is yielded by the expected value of a hitting time of the Markov chain. On the contrary, to obtain an upper bound, we devise first-order stochastically dominated random variables^[21] and construct a slow-converging Markov chain^[22] with such random variables. Then, an upper bound on the expected cognition completion time is yielded by the expected value of a hitting time of the Markov chain. In order to investigate the properties of the lower and upper bounds, we also provide numerical examples which compare lower and upper bounds with exact value of the expected cognition completion time over a wide range of key parameters. The numerical examples disclose that the exact value of the expected cognition completion time is tightly bounded above by the upper bound in case a relatively small number of slots comprise each response interval. In addition, the numerical examples reveal that the lower and upper bounds exhibit a parametric characteristic of convexity as similarly as the exact value of the expected cognition completion time does.

The main contributions of this paper are as follows.

· We construct a discrete-time homogeneous non-deceasing Markov chain to represent the cognition completion time as a hitting time of the Markov chain.

· We attain a lower bound on the expected cognition completion time by building a fast-converging Markov chain with first-order stochastically dominating random variables.

· We develop an upper bound on the expected cognition completion time by setting up a slow-converging Markov chain with first-order stochastically dominated random variables.

· From numerical examples, we reveal that the exact value of the expected cognition completion time is tightly bounded above by the upper bound in case each response interval consists of a relatively small number of slots. In addition, we disclose that the exact value of the expected cognition completion time shows higher propinquity toward the upper bound as the number of tags increases.

· From numerical examples, we also corroborate that the lower and upper bounds exhibit a parametric characteristic of convexity as similarly as the exact value of the expected cognition completion time does.

The paper is organized as follows. In Section 2, we describe a single-reader multiple-tag RFID network that we discuss in this paper. Also, we depict the static naive MAC scheme employed by the RFID network. In Section 3, we construct a discrete-time homogeneous non-decreasing Markov chain and represent the cognition completion time as a hitting time of the Markov chain. In Section 4, we build fast-converging and slow-converging Markov chains, respectively, with first-order stochastically dominating and dominated random variables. Then, we attain exact lower and upper bounds on the expected cognition completion time from the Markov chains. Section 5 is devoted to the numerical examples which compares the upper and lower bounds with the exact value of the expected cognition completion time.

Ⅱ. RFID Network

In this paper, we consider an RFID network, which consists of a single reader and multiple tags lying in the vicinity of the reader, as depicted in Figure 1. In the network, the reader does not know about neighboring tags a priori. Thus, the reader should necessarily cognize nearby tags, i.e., be aware of the identification numbers of them, first of all. In order to cognize adjacent tags in the RFID network, the reader sends data, which contain the information about the time structure for cognizing tags through the forward physical channel. Meanwhile, each tag sends data, which typically include the identification number of the tag, through the reverse physical channel. All the tags that comprise the RFID network can be either active or passive, i.e., operated by battery (capacitor) or not. If tags are passive, the reader delivers energy to the tags by transmitting an electrical signal to them. Then, each tag reflects (or backscatters) the signal to the reader while letting its data modulate the signal^[23].

(MAC) scheme is mandatory to support many tags to send their data to the reader so that the reader is able to receive and also identify all the data. Furthermore, the MAC scheme should be capable of arbitrating a collision between data packets since two or more tags can send their packets almost simultaneously^[4].

Assume that the RFID network employs a MAC scheme rooted in framed slotted ALOHA^[14], which belongs to the category of static naive MAC schemes according to the classification rule addressed in the introduction. In the MAC scheme, time is divided into frames and a frame is again partitioned into announcement interval and response interval. A response interval is further divided into a number of slots. (The duration of every slot is set to be fixed and identical as well.) Figure 2 shows the time structure adopted in the MAC scheme.

On the time structure illustrated in Figure 2, the MAC scheme behaves as follows.

· During the announcement interval of a frame, the reader broadcasts a packet which contains the information about the upcoming response interval, e.g., the number of slots in the response interval through the forward physical channel

· During the announcement interval, each taglistens to the forward physical channel. At the endof the announcement interval, a tag chooses a slot among the slots belonging to the upcoming response interval independently as well as equally likely. Then, the tag sends a packet that contains its identification number to the reader during the selected slot through the reverse physical channel.

· During each slot of the response interval, the reader listens to the reverse physical channel. Then, the reader receives and identifies a packet, if any. Two or more tags can incidentally choose a same slot. Then, they send their packets during the same slot and consequently a collision takes place among the packets. As a result, the reader is able to identify none of the packets involvedin the collision. (In practice, the reader may cognize a tag due to the capture phenomenon even if a collision occurs among some packets^[4]. Inthis paper, however, we ignore the possibility that the reader cognizes a tag in spite of the collision of its packet.) On the other hand, if only one tag chooses a slot, the tag solely sends a packet during the slot. Thus, the reader receives thepacket and correctly identifies it. (In this paper, we assume that the effect of the channel noise on the tag cognition is negligible.)

· Once the reader receives a packet and correctly identifies it, the reader cognizes the tag that sent the packet by reading the identification number.

· During the announcement interval of the next frame, the reader broadcasts a packet to notify nearby tags of the structure of the upcoming response interval as it did in the previous frame. However, the reader does not let a tag know whether the reader cognized it or not in the previous frame.

· In the next frame, every tag, regardless of whether it has been cognized by the reader or not, repeats as it did in the previous frame since a tag does not know whether it was cognized by the reader or not.

Ⅲ. Cognition Completion Time

Consider a star-configured RFID network, which consists of a single reader and M neighboring tags, as described in Section 2. Suppose that the static naive MAC scheme based on framed slotted ALOHA, which is presented in Section 2, is employed for the reader to cognize all the nearby tags. In the MAC scheme, time is divided into frames and a frame is again partitioned into announcement interval and response interval. Assume that each response interval is further divided into L slots. Define the cognition completion time to be the time that the reader spends for completely cognizing all the neighboring tags, or more precisely, the time elapsed from the start of the frame in which the reader begins the cognition process to the end of frame in which the reader cognizes the last tag. Since the number of slots in a frame is definitely finite, it is not guaranteed that the reader cognizes all the tags in a frame. Also, due to the probabilistic nature of packet delivery attempts by tags, the cognition completion time is inevitably random. In this section, to analyze the cognition completion time, we construct a Markov chain which represents a timewise collection of cumulative numbers of the tags that the reader has cognized. Then, we investigate the properties of the time that the Markov chain hits at state M, which is equivalent to the cognition completion time.

For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$W_n$$ denote the number of tags that the reader cognizes during the [TeX:] $$n \text {th }$$ frame. Such a number of tags is equivalent to the number of tags that respond to the reader without collision in the [TeX:] $$n \text {th }$$ frame, which is equal to the number of slots in which only one tag responds during the [TeX:] $$n \text {th }$$ frame. Note that these [TeX:] $$W_n$$ tags can include some tags that the reader has already cognized before the [TeX:] $$n \text {th }$$ frame. In each frame, every tag independently and equally likely selects a slot among the L slots. Thus, [TeX:] $$W_1$$, [TeX:] $$W_2$$, … are mutually independent and identically distributed. Consider a random experiment in which M balls are equally likely put into L boxes^[23]. Let B represent the number of boxes with only one ball in the random experiment. Let [TeX:] $$f_B:\{0, \ldots, \min \{L, M\}\}$$ → [0,1] denote the mass function of B. Then, we have^[24]

for [TeX:] $$r \in\{0, \ldots, \min \{L, M\}\}$$. Note that [TeX:] $$W_n$$ is equivalent to the number of slots in which only one tagresponds when each of the M tags equally likelyselects a slot among the L slots. Thus, [TeX:] $$W_n=B$$in distribution for all [TeX:] $$n \in \mathbb{N}$$, i.e.,

for all [TeX:] $$r \in\{0, \ldots, \min \{L, M\}\} .$$

For all [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$V_n$$ denote the number of tags that the reader newly cognizes during the [TeX:] $$n \text {th }$$ frame, i.e., the number of tags that the reader has never cognized until the end of the [TeX:] $$(n-1)$$st frame and cognizes for the first time in the [TeX:] $$n \text {th }$$ frame. For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$Y_n$$ denote the cumulative number of tags that the reader newly cognizes until the end of the [TeX:] $$n \text {th }$$ frame. Set [TeX:] $$Y_0=0$$ almost surely. Then, [TeX:] $$Y_n$$ is related to [TeX:] $$Y_{n-1}$$ in a recursive fashion as follows.

for [TeX:] $$n \in \mathbb{N}$$. Note that the [TeX:] $$W_n$$ tags, which are cognized by the reader during the [TeX:] $$n \text {th }$$ frame, are composed of the [TeX:] $$V_n$$ tags that the reader newly cognizes in the [TeX:] $$n \text {th }$$ frame and the [TeX:] $$W_n-V_n$$ tags that the reader has already cognized in previous frames and cognizes again in the [TeX:] $$n \text {th }$$ frame. Since each tag selects a slot independently as well as equally likely, we have

for [TeX:] $$r \in\{0, \ldots, M-x\}$$ and [TeX:] $$x, x_{n-2}, \ldots, x_0 \in\{0, \ldots, M\}$$. Then, stochastic process [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time homogeneous Markov chain on state space [TeX:] $$S=\{0, \ldots, M\}$$ since given [TeX:] $$Y_{n-1}, \quad V_n$$ is independent of [TeX:] $$Y_0, \ldots, Y_{n-2}$$ for all [TeX:] $$n \in \mathbb{N}$$. Let [TeX:] $$\mu_0$$ denote the initial distribution for Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

Also, let [TeX:] $$g_Y: \mathbf{S} \times \mathbf{S}$$→[0,1] denote the transition probability function of Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

for [TeX:] $$y \in\{x, \ldots, M\}$$ and [TeX:] $$x \in\{0, \ldots, M\}$$.

For [TeX:] $$m \in\{0, \ldots, M-1\}$$, state m leads to any state [TeX:] $$m^{\prime} \in\{m, \ldots, M\}$$ while state m never leads to any state [TeX:] $$m^{\prime} \in\{0, \ldots, M-1\}$$. On the other hand, state M leads only to state M itself, i.e., state M is an absorbing state. Thus, Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ converges to absorbing state M and there exists a steady state distribution for [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$\mu_n$$ denote the distribution for [TeX:] $$Y_n$$, i.e.,

for [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$^[25]. Then, there exists steady state distribution [TeX:] $$\pi$$ for [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ such that

as [TeX:] $$n \rightarrow \infty$$ for all [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$. Note that

since M is the unique absorbing state.

Let [TeX:] $$H_y$$ denote the time that Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ hits at state M, i.e., the time that [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ visits state M for the first time. Then, hitting time [TeX:] $$H_y$$ can be expressed by

Recall that the cognition completion time is the time elapsed until the reader cognizes all the tags residing in the coverage. Since there are M tags in the RFID network, the cognition completion time is equal tothetime elapsed until Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ visits state M for the first time. Therefore, the cognition completion time is equivalent to hitting time [TeX:] $$H_y$$. Let [TeX:] $$f_{H Y}$$ denote the mass function of [TeX:] $$H_y$$. Then, mass [TeX:] $$f_{H Y}(k)$$ can be calculated by

for [TeX:] $$k \in \mathbb{N}$$. Also, the expected value of the hitting time at state M, i.e., the expected cognition completion time can be yielded by

However, multi-step transition probabilities are hard to express in handy forms and hence the mass of the hitting time at state M cannot be easily yielded in a tractable form. Consequently, the expected cognition completion time is hardly obtainable in a handy form.

Ⅳ. Bounds on Expected Cognition Completion Time

As addressed in Section 3, the exact value of the expected cognition completion time is hardly obtainable in a tractable form. As alternatives to the exact value, we find lower and upper bounds on the expected cognition completion time in this section.

Let [TeX:] $$\phi$$ and [TeX:] $$\psi$$ be two distributions on state space [TeX:] $$S=\{0, \ldots, M\}$$. Then, the total variation distance between distributions [TeX:] $$\phi$$ and [TeX:] $$\psi$$, which is denotedby [TeX:] $$d(\phi, \psi)$$, is defined as follows^[26].

Recall Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ on state space S, which is defined by initial distribution andtransition probability function in (5) and (6). Usingthetotal variation distance, the similarity between transient state distribution [TeX:] $$\mu_n$$ in (7) and steady state distribution [TeX:] $$\pi$$ in (9) can be expressed by [TeX:] $$d\left(\mu_n, \pi\right)$$^[22,27-29]. Consider Markov chain [TeX:] $$\left\{\hat{Y}_n: n \in\{0\} \cup \mathbb{N}\right\}$$ on state space S. For [TeX:] $$n \in \mathbb{N}$$, set [TeX:] $$\hat{\mu}_n(\mathrm{~A})=P\left(\hat{Y}_n \in \mathrm{~A}\right)$$ for [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$. Suppose that [TeX:] $$\left\{\hat{Y}_n: n \in\{0\} \cup \mathbb{N}\right\}$$ has the same steady state distribution as [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. If Markov chain [TeX:] $$\left\{\hat{Y}_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is said to converge to steady state distribution [TeX:] $$\pi$$ faster than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Otherwise, [TeX:] $$\left\{\hat{Y}_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is said to converge to steady state distribution [TeX:] $$\pi$$ slower than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$.

In this section, we construct a Markov chain thatconverges faster than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ to obtain a lower bound on the expected cognition completion time. Also, we build a Markov chain that converge slower than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ to develop an upper bound on the expected cognition completion time.

4.1 Lower Bound on Expected Cognition Completion Time

In this section, we construct a Markov chain that converges faster than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Using the Markov chain, we then derive a lower bound on the expected cognition completion time.

Recall that [TeX:] $$W_n$$ denotes the total number of tags that the reader cognizes during the nth frame while [TeX:] $$V_n$$ represents the number of tags that the reader newly cognizes in the [TeX:] $$\text { nth }$$ frame. Then, [TeX:] $$W_n$$ and [TeX:] $$V_n$$ are stochastically ordered as shown in the lemma below.

Lemma 1 For each [TeX:] $$n \in \mathbb{N}$$, [TeX:] $$W_n$$ has first-order stochastic dominance over [TeX:] $$V_n$$^[26], i.e., for all [TeX:] $$r \in[0, \infty)$$.

Proof: A proof of Lemma 1 is given in the appendix.

Using the property of first-order stochastic dominance, we will construct a fast-converging Markov chain and then derive a lower bound on the expected cognition completion time henceforth.

Set [TeX:] $$Z_0=0$$ almost surely. For [TeX:] $$n \in \mathbb{N}$$, define [TeX:] $$Z_n$$ in a recursive fashion as follows.

for [TeX:] $$n \in \mathbb{N}$$. Since [TeX:] $$W_1, W_2, \ldots$$ are mutually independent and identically distributed, stochastic process [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time homogeneous Markov chain on state space [TeX:] $$S=\{0, \ldots, M\}$$. Let [TeX:] $$v_n$$ denotethe initial distribution for Markov chain [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

Let [TeX:] $$g_{\mathrm{z}}: \mathrm{S} \times \mathrm{S}$$ → [0,1] denote the transition probabilityfunction of Markov chain [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

for [TeX:] $$x \in\{0, \ldots, y\}$$ and [TeX:] $$y \in\{0, \ldots, M-1\}$$. Also,

for [TeX:] $$x \in\{0, \ldots, M\}$$.

For [TeX:] $$m \in\{0, \ldots, M-1\}$$, state m leads to any state [TeX:] $$m^{\prime} \in\{m, \ldots, M\}$$ while state m never leads to any state [TeX:] $$m^{\prime} \in\{0, \ldots, m-1\}$$. On the other hand, state M leads only to state M itself, i.e., state M is anabsorbing state. Thus, [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ converges toabsorbing state M and there exists a steady state distribution for Markov chain [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$. For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$V_n$$ denote the distribution for [TeX:] $$Z_n$$, i.e.,

for [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$. Then, there is the steady state distributionfor [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$, denoted by v, such that

as [TeX:] $$n \rightarrow \infty$$ for all [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$ . Note that

From (22), we observe that [TeX:] $$V=\pi$$ and conclude that [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ has the same steady state distribution as [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$.

The following lemma compares two Markov chains [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ and [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ in convergence rate and confirms that [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ converges to steady state distribution p faster than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$.

Lemma 2

for all [TeX:] $$n \in \mathbb{N}$$.

Proof: A proof of Lemma 2 is given in the appendix.

Let [TeX:] $$H_z$$ denote the time that [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ hits at state M, i.e.,

Note that the hitting time at state M can also be expressed by

Let [TeX:] $$f_{H Z}$$ denote the mass function of [TeX:] $$H_z$$. Set

for [TeX:] $$k \in \mathbb{N}$$. Then, from (25), the mass of [TeX:] $$H_z$$ can be expressed by

for [TeX:] $$k \in \mathbb{N}$$. Also, the expected value of [TeX:] $$H_z$$ is yielded by

The theorem below confirms that the expected hitting time at state M of Markov chain [TeX:] $$\left\{Z_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a lower bound on the expected cognition completion time.

Theorem 1

Proof: A proof of Theorem 1 is given in the appendix.

An asymptotic value of the lower bound on the expected cognition completion time can be obtained as follows. Let [TeX:] $$f_{\tilde{B}}$$ denote a mass function such that

for [TeX:] $$z \in\{0\} \cup \mathbb{N}$$, where

Then, for each [TeX:] $$r \in\{0, \ldots, \min \{M, L\}\}$$,

as [TeX:] $$M, L \rightarrow \infty$$^[24]. Thus, for each [TeX:] $$k \in \mathbb{N}$$,

as [TeX:] $$M, L \rightarrow \infty$$. Replacing [TeX:] $$\gamma_k$$ with [TeX:] $$\tilde{\gamma}_k$$ in (25) can yieldan asymptotic value of the expectation of [TeX:] $$H_z$$ asfollows.

4.2 Upper Bound on Expected Cognition Completion Time

In this section, we build a Markov chain that converges slower than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Using the Markov chain, we then derive an upper bound on the expected cognition completion time.

With intent to develop an upper bound on the expected cognition completion time, consider a single-reader multiple-tag RFID network which adopt a slightly modified static naive MAC scheme as follows. If no tag responds to the reader without collision for the first time during a frame, the reader newly cognizes no tag as usual. Also, if only one tag collisionlessly responds to the reader for the first time in a frame, the reader newly cognizes one tag. However, even if two or more tags respond to the reader without collision during a frame, the reader can cognize only one tag in the frame. (The tag that the reader cognizes is randomly selected among the tags which collisionlessly respond for the first time.) As a result, the reader is able to newly cognize at most one tag in any frame according to the modified MAC scheme.

For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$U_n$$ denote the number of tags that the reader newly cognizes during the [TeX:] $$n t h$$ frame in the RFID network described above. Then, [TeX:] $$U_n \in$$ {0,1} for [TeX:] $$n \in \mathbb{N}$$. Let [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ denote a stochastic process such that

for [TeX:] $$n \in \mathbb{N}$$, where [TeX:] $$X_0=0$$ almost surely. Then, [TeX:] $$X_n$$ represents the cumulative number of the tags that the reader has newly cognized until the end of the [TeX:] $$n t h$$ frame. Note that

and

for [TeX:] $$x, x_{n-2}, \ldots, x_0 \in\{0, \ldots, M\}$$. Thus, stochastic process [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time homogeneous Markov chain on state space [TeX:] $$S=\{0, \ldots, M\}$$. Further, [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time pure birth Markov chain. Let [TeX:] $$\lambda_0$$ denote the initial distribution for Markov chain [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

Let [TeX:] $$g_X: \mathbf{S} \times \mathbf{S}$$ → [0,1] denote the transition probabilityfunction of Markov chain [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$. Then,

for [TeX:] $$[TeX:] $$x \in\{0, \ldots, M\}$$$$, where

for [TeX:] $$x \in\{0, \ldots, M\}$$.

Since [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time purebirth Markov chain, [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ converges toabsorbing state M. Also, there exists a steady state distribution for Markov chain [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$. For [TeX:] $$n \in \mathbb{N}$$, let [TeX:] $$\lambda_n$$ denote the distribution for [TeX:] $$R_n$$, i.e.,

for [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$. Then, [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ has the steadystate distribution, denoted by [TeX:] $$\lambda$$, such that

as [TeX:] $$n \rightarrow \infty$$ for all [TeX:] $$\mathrm{A} \subset \mathrm{~S}$$. Note that

From (43), we observe that [TeX:] $$\kappa=\pi$$ and conclude that [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ has the same steady state distribution as [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$.

Remind that [TeX:] $$V_n$$ is the random variable representing the number of tags that the reader newly cognizes in the [TeX:] $$n t h$$ frame (introduced in Section 3). Then, [TeX:] $$U_n$$ and [TeX:] $$V_n$$ are stochastically ordered as stated in the lemma below.

Lemma 3 For each [TeX:] $$n \in \mathbb{N}$$, [TeX:] $$V_n$$ has first-order stochastic dominance over [TeX:] $$U_n$$, i.e.,

for all [TeX:] $$n \r \in[0, \infty)$$.

Proof: A proof of Lemma 3 is given in the appendix.

Recall that [TeX:] $$V_n$$ is the distribution for [TeX:] $$Z_n$$. The following lemma compares Markov chain [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ with Markov chain [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$ in convergence rate and confirms that [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ converges to steady state distribution [TeX:] $$\pi$$ slower than [TeX:] $$\left\{Y_n: n \in\{0\} \cup \mathbb{N}\right\}$$.

Lemma 4

for all [TeX:] $$n \in \mathbb{N}$$.

Proof: A proof of Lemma 4 is given in the appendix.

Let [TeX:] $$H_x$$ denote the time that [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ hits at state M, i.e.,

Remind that [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is a discrete-time pure birth Markov chain. For [TeX:] $$x \in\{1, \ldots, M\}$$, let [TeX:] $$G_x$$ denote the time elapsed from the moment that [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ reaches state [TeX:] $$x-1$$ until [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ moves to state x. Then, hitting time [TeX:] $$H_x$$ can be expressed by

Note that [TeX:] $$G_x$$ has the shifted geometric distribution with parameter [TeX:] $$\beta_x$$ for [TeX:] $$x \in\{1, \ldots, M\}$$. Thus,

for [TeX:] $$x \in\{1, \ldots, M\}$$. Therefore, the expected hitting time at state M of [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is obtained by

The theorem below confirms that the expected hitting time at state M of Markov chain [TeX:] $$\left\{X_n: n \in\{0\} \cup \mathbb{N}\right\}$$ is an upper bound on the expected cognition completion time.

Theorem 2

Proof: A proof of Theorem 2 is given in the appendix.

Ⅴ. Numerical Examples

Lower and upper bound on the expected cognition completion time have been yielded in Section 4. Inthis section, these bounds are compared with the exact value of the expected cognition completion time in the numerical examples covering a wide range of key parameters.

Figure 3 illustrates asymptotic lower bound shown in (34), exact value estimated by using a simulation method and upper bound presented in (49) with respect to the number of tags residing in the RFID network under discussion. In this figure, the number of slots comprising a response interval is set to be 5 and 20, and the announcement interval of each frame is also set to consist of a single slot. In Figure 3, eachs lot is assumed to be an interval during which a packet specified in [30] can be sent. Note that the packet consists of preamble of 16 bits, flag field of 2 bits, parameter field of 4 bits, payload of 64 bits, and checksum field of 16 bits, which is then transmitted from a tag to the reader with data rate of 40 kbits/sec. As a result, the slot duration time is equal to 2.6 msec. When a response interval consists of 5 slots, we particularly notice that the expected cognition completion time is tightly bounded above by the upper bound from Figure 3. When number of tags [TeX:] $$M \in\{1, \ldots, 30\}$$, the average absolute difference between upper bound and exact value is calculated to be 0.082 sec. Against the average of exact values, which is 6.4 sec, the ratio of the average absolute difference is computed to be 1.28%. On the other hand, the average absolute difference between upper bound and exact value for [TeX:] $$M \in\{1, \ldots, 30\}$$ when a response interval consists of 20 slots is calculated to be 0.625 sec. Also, the ratio of the average absolute difference is 173% against the average of exact values, which is 0.36 sec. This phenomenon is explained by noting that the chance for two or more tags are cognized in a frame becomes rare as the number of tags increases while the number of slots comprising a response interval is fixed. Consequently, the exact value of the expected cognition completion time shows a tendency to approach the upper bound as the number of tags increases.

Figure 4 demonstrates asymptotic lower bound shown in (34), exact value estimated by using a simulation method and upper bound presented in (49) with respect to the number of slots comprising a response interval. In Figures 4.a and 4.b, the numbers of tags in the RFID network are set to be 20 and 30, respectively. In these figures, the announcement interval of each frame is also set to consist of a single slot. In Figures 4.a and 4.b, each slot is assumed to be an interval during which a packet proposed in [31] can be sent. Note that the packet consists of data structure format identifier field of 8 bits, reserved 8 bits, header of 24 bits, payload of 64 bits, and checksum field of 32 bits, which is then transmitted from a tag to the reader with data rate of 256 kbits/sec. As a result, the slot duration time is equal to 0.53125 msec. In Figures 4.a and 4.b as well, we observe that the exact values of the expected cognition completion time form a convex downward curve with respect to the number of slots that comprise a response interval. From these figures, we also notice that there is a unique critical number of slots which minimizes the expected cognition completion time for constituting a response interval. There is an optimal number of slots that comprise a response interval in the sense of minimizing the cognition rate, i.e., the average number of tags that the reader cognizes during a frame^[8,10]. The existence of such an optimal number is due to the trade-off between decreasing collision probability and increasing number of squandered slots. The existence of a critical number of slots that minimizes the expected cognition time seems to also be brought by the same trade-off. In Figures 4.a and 4.b, we further observe that both lower bound curve and upper bound curve are convex downward and there are critical values minimizing lower bound and upper bound, respectively, for the number of slots contained in a response interval.

Ⅵ. Conclusions

In this paper, we considered an RFID network that consists of a single reader and multiple tags sojourning in the vicinity of the reader. For a number of tags to be able to successfully respond to the reader while arbitrating the collision among some responses, we supposed that the RFID network employs a static naive MAC scheme rooted in framed slotted ALOHA. In order to analyze the cognition completion time in the RFID network under discussion, we constructed a Markov chain to represent the cognition completion time as a hitting time of the Markov chain. As an alternative to the exact value, which is hardly obtainable in a tractable form, we then attained a lower bound on the expected cognition completion time by building a fast-converging Markov chain with first-order stochastically dominating random variables and developed an upper bound by constructing slow-converging Markov chains with first-order stochastically dominated random variables. Numerical examples covering a wide range of key parameters revealed that the exact value of the expected cognition completion time is tightly bounded above by the upper bound in case a relatively small number of slots comprise each response interval. The examples also disclosed that the exact value of the expected cognition completion time shows a propinquity toward the upper bound as the number of tags increases. Further, the examples corroborated that the lower and upper bounds exhibit a parametric characteristic of convexity as similarly as the exact value of the expected cognition completion time does. In the future, we will proceed to analyze the cognition completion time in the RFID networks which employ static sophisticated, dynamic naive and dynamic sophisticated MAC schemes.