Towards Efficient Large-Scale RFID System Management

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Towards Efficient Large-Scale RFID System Management"

By

Mr. Haoxiang LIU


Abstract

Radio Frequency Identification (RFID) attracts increasing attention in the 
recent years due to its good application prospect. It is widely used in a 
variety of applications such as warehouse management, inventory control, 
object tracking and localization, etc. RFID devices, especially tags, have 
small size and ultra-low power consumption. With such advantages, they are 
well-suited to automatic inventory management in a large-scale. In 
practice, large-scale management in RFID systems is primarily comprised of 
two mainstreams, namely tag identification and estimation. Identification 
is a basic operation of collecting tag IDs to identify corresponding 
objects. Estimation aims to count the number of tags quickly and 
accurately.

In this dissertation, we explore how to design effective protocols to 
build large-scale RFID management systems. The protocols, as introduced 
above, address two fundamental problems in RFID systems, namely 
identification and estimation. Both type of protocols should scale well to 
massive tags.

In our first work, we investigate how to efficiently identify a large 
amount of tags with one mobile reader that continuous changes its position 
to expand the coverage, denoted as the continuous scanning problem. We 
observe that the performance of continuous scanning protocol depends on 
the spatial distribution of tags in two adjacent scans. An adaptive 
continuous scanning protocol is proposed that selects the best scanning 
strategy according to the current spatial distribution of tags.

In our second work, we study the conventional RFID estimation problem. We 
notice that existing estimation approaches merely provide asymptotic 
results of estimation time, but fail to give tight bounds for the 
convergence rate of corresponding algorithms. We propose an estimation 
scheme that achieves Arbitrarily Accurate Approximation (A3) for the tag 
population size. More importantly, we give an rigorous bound O((loglog 
n+ε-2)logδ-1) in its communication time, for a given (ε,δ) accuracy 
requirement.

In our last work, we explore a generalized RFID estimation problem named 
Generic Composite Counting. The conventional RFID estimation problem 
focuses on counting the number of tags in a single tag set, or at most the 
union of multiple tag sets. This simple scenario is far from enough to 
meet various application demands. To address this problem, we introduce a 
more complex counting model, which aims to estimate the cardinality of a 
composite set expression such as (S1US2)-S3, where Si (1≤i≤3) denotes a 
tag set. A Composite Counting Framework (CCF) is designed to provide 
estimates for any set expression with desired (ε,δ) accuracy.


Date:			Wednesday, 27 May 2015

Time:			2:30pm - 4:30pm

Venue:			Room 3494
 			Lifts 25/26

Chairman:		Prof. Bertram Shi (ECE)

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Gary Chan
 			Prof. Ke Yi
 			Prof. James She (ECE)
 			Prof. Jianping Wang (CityU)


**** ALL are Welcome ****