Title: Efficient median estimation for large-scale sensor RFID systems

Authors: Huda El Hag Mustafa; Xiaojun Zhu; Qun Li; Guihai Chen

Addresses: Faculty of Mathematical Sciences, University of Khartoum, Khartoum 11115, Sudan; Department of Computer Science, College of William and Mary, Williamsburg, VA 23187, USA. ' State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu 210093, China; Department of Computer Science, College of William and Mary, Williamsburg, VA 23187, USA. ' Department of Computer Science, College of William and Mary, Williamsburg, VA 23187, USA. ' State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, Jiangsu 210093, China

Abstract: We consider the median estimation problem in a large-scale sensor augmented RFID system. The large-scale deployment of RFID technology has opened the door to innovative ways to integrate RFID and sensor technology. Sensor-tags are tags that can report over 50 types of physical information to a reader. The traditional way to obtain information from sensor-tags is to query each tag. When the number of tags is large, however, it is prohibitive to query tags individually due to the high delay. In this paper, we present a probabilistic algorithm to estimate the median of a set of sensor-RFID tags without individually querying each tag. The median estimation problem is solved using binary search. Our evaluation demonstrates that the median search algorithm exhibits high accuracy and reasonable time latency. Moreover, we also design an exact algorithm for the continuous median update problem. Our algorithm can incrementally compute the exact median in less time.

Keywords: sensor technology; RFID tags; radio frequency identification; median estimation; binary search; TCS; threshold checking scheme; continuous median update; sensors.

DOI: 10.1504/IJSNET.2012.050455

International Journal of Sensor Networks, 2012 Vol.12 No.3, pp.171 - 183

Received: 23 Apr 2012
Accepted: 19 Jun 2012
Published online: 23 Nov 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article