Double rulings for information brokerage in sensor networks

ABSTRACT

We study the problem of information brokerage in sensor networks, where information consumers (sinks,users)search for data acquired by information producers (sources). In-network storage such as geographical hash table (GHTs) has been proposed to store data at rendezvous nodes for consumers to retrieve. In this paper, we propose a double rulings scheme which stores data replica at a curve instead of one or multiple isolated sensors. The consumer travels along another curve which guarantees to intersect with the producer curve. The double rulings is a natural extension of the flat hashing scheme such as GHTs with improved query locality, i.e., consumers close to producers find the data quickly, and structured aggregate queries, i.e., a consumer following a curve is able to retrieve all the data. Further, by the flexibility of retrieval mechanisms we have better routing robustness and data robustness. We show by simulation that the double rulings scheme provide reduced communication costs and more balanced traffic load on the sensors.

REFERENCES

• 1: http://www.greatduckisland.net/.
• 2: Esther M. Arkin , Refael Hassin, Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, v.55 n.3, p.197-218, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90008-6 ]
• 3: 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]
• 4: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, MAP: medial axis based geometric routing in sensor networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080839]
• 5: H. S. M. Coxeter. Introduction to Geometry John Wiley & Sons, New York, 2nd edition, 1969.
• 6: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 7: Q. Fang, J. Gao, and L. Guibas. Locating and bypassing routing holes in sensor networks. In The 23rd Conference of the IEEE Communications Society (INFOCOM'04) volume 23, pages 2458--2468, March 2004.
• 8: Q. Fang, J. Gao, L. Guibas, V. de Silva, and L. Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05)March 2005.
• 9: Q. Fang, J. Gao, and L. J. Guibas. Landmark-based information storage and retrieval in sensor networks. In The 25th Conference of the IEEE Communication Society (INFOCOM'06) April 2006.
• 10: S. Funke, L. Guibas, A. Nguyen, and Y. Wang. Distance-sensitive routing and information brokerage in sensor networks. manuscript, 2005.
• 11: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 12: D. Jea, A. A. Somasundara, and M. B. Srivastava. Multiple controlled mobile elements (data mules)for data collection in sensor networks. In DCOSS pages 244--257, 2005.
• 13: A. Kansal, M. Rahimi, W. J. Kaiser, M. B. Srivastava, G. J. Pottie, and D. Estrin. Controlled mobility for sustainable wireless networks. In IEEE Sensor and Ad Hoc Communications and Networks (SECON'04) 2004.
• 14: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 15: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 16: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in 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.958500]
• 17: W. Lindner and S. Madden. Data management issues in periodically disconnected sensor networks. In Proceedings of Workshop on Sensor Networks at Informatik 2004.
• 18: Xin Liu , Qingfeng Huang , Ying Zhang, Combs, needles, haystacks: balancing push and pull for discovery in large-scale sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031510]
• 19: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 20: Badri Nath , Dragoş Niculescu, Routing on a curve, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.155-160, January 2003 [doi>10.1145/774763.774788]
• 21: Sylvia Ratnasamy , Brad Karp , Li Yin , Fang Yu , Deborah Estrin , Ramesh Govindan , Scott Shenker, GHT: a geographic hash table for data-centric storage, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570750]
• 22: P. Samuel. Projective Geometry Springer-Verlag, New York, 1988.
• 23: R. Shah, S. Roy, S. Jain, and W. Brunette. Data MULEs: Modeling a three-tier architecture for sparse sensor networks. In IEEE SNPA Workshop May 2003.
• 24: S. Shenker, S. Ratnasamy, B. Karp, R. Govindan, and D. Estrin. Data-centric storage in sensornets. In ACM SIGCOMM HotNets 2002.
• 25: I. Stojmenovic. A routing strategy and quorum based location update scheme for ad hoc wireless networks. Technical Report TR-99-09, SITE, University of Ottawa, September, 1999.
• 26: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 27: Zoltán Vincze , Rolland Vida, Multi-hop wireless sensor networks with mobile sink, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France [doi>10.1145/1095921.1095991]
• 28: Yue Wang , Jie Gao , Joseph S.B. Mitchell, Boundary recognition in sensor networks by topological methods, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161104]
• 29: Fan Ye , Haiyun Luo , Jerry Cheng , Songwu Lu , Lixia Zhang, A two-tier data dissemination model for large-scale wireless sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570664]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Design

Keywords:
data-centric routing, double rulings, information storage and retrieval, sensor networks