Park Graduate Award Lecture: Bo Sheng

Starts: April 4, 2008 at 3:00 PM
Location: McGlothlin-Street 020

Summary

Finding Popular Categories for RFID Tags

Full Description

Bo Sheng

Pervasive computing captures the vision that small, inexpensive, robust networked processing devices are distributed at all scales throughout everyday life. These large scale small devices (such as sensors and RFID tags) generate a lot of data and the data are often pertinent to the people involved in the pervasive computing systems. Our goal is to address the important problem in this context: how to manage massive data in an efficient, secure, and privacy-preserving manner. Since those small devices are weak in computation and communication, designing efficient protocols for them is extremely challenging. We have designed various algorithms for different data management problems. In this talk, I want to show our recent result on finding popular categories in an RFID system exemplifying the design principles for those small devices.

In many RFID applications, it is useful and important to find popular categories of items, i.e., the categories with a large quantity of items. Conventional solution of collecting all data from every RFID tag is not efficient in term of scanning time, especially in a large scale RFID system. We propose two novel randomized algorithms based on the idea of group testing which allows us to efficiently derive popular groups of tags. Even though an RFID tag has extremely limited computation ability, we can achieve fairly complicated task by harnessing the power of randomization. We evaluate our solutions using both theoretical analysis and simulations and our results illustrate that the proposed algorithms dramatically reduce the scanning time.