24 December 2019 in IEEE Transactions on Mobile Computing
Radio frequency identification (RFID) has been widely used in many fields such as object tracking and inventory management. For RFID systems, grouping is a fundamental issue which can support efficient multicast transmissions, dynamic tag management, and accurate aggregate queries. Existing grouping protocols have drawbacks of unknown theoretical communication time, high computational cost on the server end and inability to deal with unexpected tags which are those tags whose IDs have not been collected by readers. In this paper, we would like to address the above limitations and consider a more general grouping problem that allows an arbitrary number of unexpected tags to present. Our objective is to design a protocol that guarantees the reader to efficiently and correctly notify each known tag of its group-ID, while the probability that an unexpected tag is mistakenly notified of any group-ID is smaller than a pre-determined value. In this paper, we first obtain a lower bound on the communication time for solving this generalized grouping problem. Then, we propose a near-optimal protocol, called OPT-G, and prove that its communication time approximately equals the lower bound. Finally, we report extensive simulation results that demonstrate OPT-G's near-optimal performance and its superiority over existing baseline schemes.
10 October 2023 in IEEE/ACM Transactions on Networking
Mobile radio frequency identification (RFID) systems typically experience the continual movement of many tags rapidly going in and out of the interrogating range of readers. Readers that are deployed to maintain a current, real-time list of tags, which are present in the interrogating zone at any moment, must repeatedly execute a series of reading cycles. Each of these reading cycles provides the readers very limited time to identify unknown tags (those newly entering into the reader’s range), and, at the same time, to detect missing tags (those just leaving the reader’s range). In this paper, we study the continuous tag recognition problem, which is critical for mobile RFID systems. First, we obtain a lower bound on communication time for solving this problem. We then design a near-OPTimal protocoL, called OPT-L, and prove that its communication time is approximately equal to the lower bound. Finally, we present extensive simulation and experimental results that demonstrate OPT-L’s superior performance over other existing protocols.
7 March 2006 in Theoretical Computer Science
18 April 2003 in Theoretical Computer Science
1 January 2011 in Fundamenta Informaticae
We introduce (finite and infinite) typical paths of a graph and prove that the typical paths carry all information with probability 1, asymptotically. An automata-theoretic characterization of the typical paths is shown: finite typical paths can be accepted by reversal-bounded multicounter automata and infinite typical paths can be accepted by counting Büchi automata (a generalization of reversal-bounded multicounter automata running on ω-words). We take a statechart example to show how to generate typical paths from a graph using SPIN model checker. The results are useful in automata theory since one can identify an information-concentrated-core of a regular language such that only words in the information-concentrated-core carry nontrivial information. When the graph is used to specify the system under test, the results are also useful in software testing by providing an information-theoretic approach to select test cases that carry nontrivial information of the system specification.