Empirical evaluation of querying mechanisms for unstructured wireless sensor networks

ABSTRACT

In the last few years, several studies have analyzed the performance of flooding and random walks as querying mechanisms for unstructured wireless sensor networks. However, most of the work is theoretical in nature and while providing insights into the asymptotic behavior of these querying mechanisms, does not account for the non-idealities faced by the network in real deployments. In this paper, we propose a 3-way handshake protocol as a reliable implementation of a random walk and compare its performance with flooding in real environments. The metrics considered are delay, reliability and transmission cost. Our initial results suggest that flooding is better suited for low-interference environments, while random walks might be a better option in networks with high interference. We also present possible research directions to improve the performance oflooding and random walks.

REFERENCES

• 1: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin and S. Wicker, Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks. UCLA CS Technical Report UCLA/CSD-TR 02-0013, 2002.
• 2: D. Kotz and C. Newport and C. Elliott, The mistaken axioms of wireless-network research, Technical Report TR2003-467, Dept. of Computer Science, Dartmouth College, July 2003.
• 3: F. Stann, J. Heidemann, R. Shroff, and M. Murtaza, Rbp: Reliable broadcast propagation in wireless networks, In USC/ISI Technical Report ISI-TR-2005-608, 2006.
• 4: B. Krishnamachari, J. Ahn, Optimizing data replication for expanding ring-based queries in wireless sensor networks, WiOpt, Boston, MA, April 2006.
• 5: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 6: Sylvia Ratnasamy , Brad Karp , Scott Shenker , Deborah Estrin , Ramesh Govindan , Li Yin , Fang Yu, Data-centric storage in sensornets with GHT, a geographic hash table, Mobile Networks and Applications, v.8 n.4, p.427-442, August 2003 [doi>10.1023/A:1024591915518]
• 7: Deepak Ganesan , Ben Greenstein , Denis Perelyubskiy , Deborah Estrin , John Heidemann, An evaluation of multi-resolution storage for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958502]
• 8: B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker, DIFS: A Distributed Index for Features in Sensor Networks, Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications, May 2003.
• 9: Nicholas Chang , Mingyan Liu, Revisiting the TTL-based controlled flooding search: optimality and randomization, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023730]
• 10: Nicholas B. Chang , Mingyan Liu, Controlled flooding search in a large network, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.436-449, April 2007 [doi>10.1109/TNET.2007.892880]
• 11: Zhao Cheng , Wendi B. Heinzelman, Flooding strategy for target discovery in wireless networks, Wireless Networks, v.11 n.5, p.607-618, September 2005 [doi>10.1007/s11276-005-3516-7]
• 12: Z. Cheng and W. Heinzelman, Searching Strategy for Multi-Target Discovery in Wireless Networks, 4th Workshop on Applications and Services in Wireless Networks (ASWN '04), August 2004.
• 13: D. Aldous and Fill, Reversible Markov Chains and Random Walks on Graphs, Draft Monograph, online at http://www.stat.berkeley.edu/~aldous/RWG/book.html
• 14: N. Sadagopan, B. Krishnamachari, and A. Helmy, The ACQUIRE Mechanism for Efficient Querying in Sensor Networks, IEEE International Workshop on Sensor Network Protocols and Applications (SNPA'03), May 2003.
• 15: N. Sadagopan, B. Krishnamachari, and A. Helmy, Active Query Forwarding in Sensor Networks (ACQUIRE), Journal of Ad Hoc Networks, Elsevier, Vol 3, Issue 1, pp. 91--113, January 2005.
• 16: David Braginsky , Deborah Estrin, Rumor routing algorthim for sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570742]
• 17: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 18: D. Lal, A. Manjeshwar, F. Herrmann, E. Biyikoglu, A. Keshavarzian, Measurement and characterization of link quality metrics in energy constrained wireless sensor networks, GLOBECOM 2003 - IEEE Global Telecommunications Conference, no. 1, Dec 2003 pp. 446--452.
• 19: A. Cerpa, N. Busek, and D. Estrin, SCALE: A tool for Simple Connectivity Assessment in Lossy Environments, CENS Technical Report, September 2003.
• 20: Alberto Cerpa , Jennifer L. Wong , Louane Kuang , Miodrag Potkonjak , Deborah Estrin, Statistical model of lossy links in wireless sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 21: M. Zuniga, B. Krishnamachari, Analyzing the Transitional Region in Low Power Wireless Links, First IEEE International Conference on Sensor and Ad hoc Communications and Networks (SECON), Santa Clara, CA, October 2004.
• 22: K. Whitehouse , A. Woo , F. Jiang , J. Polastre , D. Culler, Exploiting the capture effect for collision detection and recovery, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.45-52, April 30-May 01, 2005
• 23: D. Son, B. Krishnamachari, and J. Heidemann, Experimental Analysis of Concurrent Packet Transmissions in Low-Power Wireless Networks, Technical Report ISI-TR-609, USC/Information Sciences Institute, December, 2005.
• 24: Sergio D. Servetto , Guillermo Barrenechea, Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570741]
• 25: Chen Avin , Carlos Brito, Efficient and robust query processing in dynamic environments using random walk techniques, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984663]
• 26: W. Richard Stevens , Gary R. Wright, TCP/IP illustrated (vol. 2): the implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 27: http://www.moteiv.com/products/tmotesky.php.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Theory

Keywords:
empirical evaluation, flooding, random walks