MAX: Wide area human-centric search of the physical world

ABSTRACT

We propose MAX, a system that facilitates human-centric search of the physical world. Instead of organizing objects a priori, it allows humans to search for and locate them as needed. Designed for the following objectives: (i) human-centric operation, (ii) privacy, and (iii) efficient searching of any tagged object, MAX provides location information in a form natural to humans, that is, with reference to identifiable landmarks (such as, “on the dining table”) rather than precise coordinates. In the system, all physical objects—from documents to clothing—can be tagged, users then locate objects using an intuitive search interface. To make searching efficient, MAX adopts a hierarchical architecture consisting of tags (bound to objects), substations (bound to landmarks), and base-stations (bound to localities). Tags can be marked as either public or private, with private tags searchable only by the owner. MAX also provides for privacy of physical spaces. It requires minimal initial configuration, and is robust to reconfiguration of the physical space. We also present a methodology to design energy-optimal and delay-optimal query protocols for a variety of device choices, this optimizes system performance, and affords insight into the appropriate actions for various scenarios. We have implemented a simple prototype of MAX, demonstrating the feasibility of the system for human-centric search over several locations across a wide area. We contend that a MAX-like search system will enable sharing (e.g., books on a college campus) and trading (e.g., buying and selling used books) of physical resources, and will be the engine for a host of new applications.

REFERENCES

• 1: Bergamo, P. and Mazzini, G. 2002. Localization in sensor networks with fading and mobility. In Proceedings of the 13th IEEE International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC'02). 750--754.
• 2: Bewator. 2005. http://www.bewator.com/uk/index.xml.
• 3: Cornell Database Group. 2005. COUGAR: the network is the database. http://www.cs. cornell.edu/database/cougar/.
• 4: Crossbow. 2004a. Power technology and management, www.xbow.com. Pred in.
• 5: Crossbow. 2004b. Radio, Rf concepts, and TOS radio stack, www.xbow.com. Pred in.
• 6: Crossbow. 2005. Crossbow technology—inertial & gyro systems, wireless sensor networks, smart dust, advanced sensors. http://www.xbow.com/.
• 7: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 8: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 9: ISO 2000. ISO/IEC 15693 Identification Cards—Contactless Integrated Circuit(s) Cards—Vicinity Cards, 1st Ed. ISO.
• 10: Kapadia, A., Henderson, T., Fielding, J. J., and Kotz, D. 2007. Virtual walls: Protecting digital privacy in pervasive environments. In Proceedings of the 5th International Conference on Pervasive Computing (Pervasive'07).
• 11: Köhler, M., Patel, S. N., Summet, J. W., Stuntebeck, E. P., and Abowd, G. D. 2007. Tracksense: infrastructure free precise indoor positioning using projected patterns. In Proceedings of the 5th International Conference on Pervasive Computing (Pervasive'07).
• 12: Liu, X., Corner, M. D., and Shenoy, P. 2006. Ferret: RFID localization for pervasive multimedia. In Proceedings of the 8th International Conference on Ubiquitous Computing (UbiComp'06).
• 13: Madden, S. 2005. TinyDB—a declarative database for sensor networks. http://telegraph.cs.berkeley.edu/tinydb/.
• 14: Mondinelli, F. and Vajna, Z. K. 2002. Self localizing sensor network architecture. In Proceedings of the 19th IEEE Instrumentation and Measurement Technology Conference. Vol. 1. 823--828.
• 15: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 16: NIST. 2005. NIST smart space laboratory. http://www.nist.gov/smartspace/.
• 17: Thomas Pederson, Magic Touch: A Simple Object Location Tracking System Enabling the Development of Physical-Virtual Artefacts in Office Environments, Personal and Ubiquitous Computing, v.5 n.1, p.54-57, February 2001 [doi>10.1007/s007790170031]
• 18: SkyeTek. 2004. Product datasheet, skyeread M1 mini. www.skyetek.com.
• 19: SkyeTek. 2005. Skyetek RFID. http://www.skyetek.com/readers_Mini.html.
• 20: Sorensen, T. B., Kragh, T., and Erlandsen, M. K. 2006. Jecc—elliptic curve cryptography in java. http://jecc.sourceforge.net/.
• 21: Steggles, P. and Cadman, J. 2004. A comparison of RF tag location products for real world applications. Tech. Rep., Ubisense.
• 22: Tarnacha, A. and Porta, T. L. 2003. E-STROBE: an adaptive beacon activation algorithm for sensor localization. In Proceedings of the 58th IEEE Vehicular Technology Conference (VTC'03).
• 23: Ubisense. 2005. Ubisense-the smart space company. http://www.ubisense.net/.
• 24: Wavetrend. 2005. Wavetrend. http://www.wavetrend.net/.
• 25: Yap, K.-K. 2006. MAX—human-centric search of the physical world. M.S. thesis, National University of Singapore. http://www.stanford.edu/~yapkke/Research/MAX/2006Thesis/MAXThesis2006.pdf.
• 26: Kok-Kiong Yap , Vikram Srinivasan , Mehul Motani, MAX: human-centric search of the physical world, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098937]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Design, Experimentation, Human Factors, Performance

Keywords:
Human-centric, landmark-based localization, physical world, search