My major research work resides in sensor networks and RFID systems, targeting efficiency and security problems. Here briefly describes some research projects that I have been involved in.

A sensor network often generates a large amount of raw data, among which only a small portion is desired as the reply to a user's query. A fundamental issue in this query/reply model is how to store numerous raw data and efficiently respond to a user's query. My research proposed a novel idea of deploying powerful sensors with large storage capacity, called storage nodes, to support in-network storage mechanism, where storage nodes are responsible for holding the raw data from nearby regular sensors and replying the query diffused from the sink. We thoroughly studied the storage placement problem on a tree topology and excogitated the best strategy for deploying storage nodes [MobiHoc '06]. We further investigated a derivative problem that allows a sensor network to reconstruct its topology after storage nodes are deployed. We published an approximation algorithm for this problem in [WASA '07].

My research in this area includes two projects. My first work [INFOCOM '08] considered the security and privacy threats in the in-network storage model presented above, especially when storage nodes are compromised and behave maliciously. We first designed a privacy-preserving storage protocol that only discloses partial data information to storage nodes. This information helps process the raw data for queries, but knowing this information from a compromised storage node is not sufficient for an adversary to breach the privacy. Additionally, we proposed a verifiable query protocol that enables the application to detect a false reply manipulated by a malicious storage node. My second project, a collaborative effort, is to implement generic public key primitives on sensors. Our implementation is based on Elliptic Curve Cryptography and exhaustively optimized for sensors to reduce the executing time. Based on it, we proposed an access control protocol for sensor networks [ICDCS '08]. Please refer to my colleague's web page for more details (WM-ECC).

Mining the large data repository generated by a sensor network for useful information is crucial and challenging. In a simple solution, the data collected by sensors can be transmitted to the sink for data mining analysis. This solution, however, consumes too much energy because the data volume can be extremely large. A good method should require little data transmission, but still achieve information extraction from the large amount of data distributed over the network. My work studied a classical data mining problem of outlier detection. An outlier represents a data that is very different from the others. The definition is not solely dependent on data values, but related to the distribution of other data in the pool. Outlier detection represents a category of complicated data mining queries that are difficult for a sensor network to efficiently respond, because these queries inherently require a lot of energy-expensive data exchanges among sensors. We proposed a novel multi-round filtering scheme based on data histogram technique. Our scheme can accurately find all outlier data with significantly reduced energy cost. This work has been published in [MobiHoc '07], and its methodology can also be extended to other similar data mining problems.

In an RFID system, passive RFID tags are weak hardware with no micro-controller or battery. The existing security mechanisms for wireless networks can hardly be implemented on them. Our work first investigated basic security mechanisms and proposed a mutual authentication scheme between an RFID reader and an RFID tag. Different from previous research, our solution is more flexible without involving a third party server [PerCom '07]. Furthermore, we considered another special security problem of detecting missing products in inventory control applications. Our solutions enable a server to detect the missing products even with untrusted RFID readers [ICDCS '08].

When scanning a large volume of RFID tags, signal collision is ineluctable and seriously hinders the time efficiency. In addition, some RFID applications may not require collecting all RFID data. In current approaches, however, scanning all RFID tags is the first step for all applications, followed by respective data analysis. My work first studied a typical data mining query of finding popular categories of products among numerous RFID tags. We designed randomized algorithms with group testing technique that efficiently achieve the goal without scanning all RFID tags [MobiHoc '08]. Another on-going project is about continuous scans in an RFID system. When multiple scanning processes at different locations or time points are necessary for a task, it is commonly seen that adjacent scans contain duplicated RFID tags. We proposed efficient approaches to launching continuous scans without collecting redundant RFID tags.

Search on Small Devices: We believe physical objects will be digitally annotated in a pervasive computing environment and the annotation information will be hosted at embedded devices. People can electronically search the physical world in such an environment. Searching the data stored on small devices is the building brick in this system and different from searching data on computers. First, small devices are usually equipped with flash memory instead of disk as the storage media. Second, small devices have limited RAM space for buffering data. Considering these two factors, my colleague and We implemented a textual search protocol specifically designed for small devices. Our search protocol regulates the format for the stored data and special data structures for maintaining keywords. Our protocol also includes a RAM-efficient search algorithm that can rank the search results based on the typical information retrieval metrics. Our experiments on sensors illustrate an impressive search performance. This work has been published in [Pervasive '08].

BGP Security: Border Gateway Protocol is a core component of the Internet, and maintains the information about reachability among autonomous systems (AS). The original BGP is vulnerable to various attacks that modify the AS information contained in BGP messages. My colleague and I proposed new protection schemes based on key-chained signatures. We implemented our solutions and evaluated them by real experiments. The results indicate that our solutions are feasible for incremental deployment, and efficient in term of processing speed, storage, and bandwidth cost. This work has been published in [IWQoS '07].