GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information

ABSTRACT

The widespread deployment of sensor networks is on the horizon. One of the main challenges in sensor networks is to process and aggregate data in the network rather than wasting energy by sending large amounts of raw data to reply to a query. Some efficient data dissemination methods, particularly data-centric storage and information aggregation, rely on efficient routing from one node to another. In this paper we introduce GEM (Graph EMbedding for sensor networks), an infrastructure for node-to-node routing and data-centric storage and information processing in sensor networks. Unlike previous approaches, it does not depend on geographic information, and it works well even in the face of physical obstacles. In GEM, we construct a labeled graph that can be embedded in the original network topology in an efficient and distributed fashion. In that graph, each node is given a label that encodes its position in the original network topology. This allows messages to be efficiently routed through the network, while each node only needs to know the labels of its neighbors.To demonstrate how GEM can be applied, we have developed a concrete graph embedding method, VPCS (Virtual Polar Coordinate Space). In VPCS, we embed a ringed tree into the network topology, and label the nodes in such a manner as to create a virtual polar coordinate space. We have also developed VPCR, an efficient routing algorithm that uses VPCS. VPCR is the first algorithm for node-to-node routing that guarantees reachability, requires each node to keep state only about its immediate neighbors, and requires no geographic information. Our simulation results show that VPCR is robust on dynamic networks, works well in the face of voids and obstacles, and scales well with network size and density.

REFERENCES

• 1: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 2: Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
• 3: P. Bahl and V. N. Padmanabhan. RADAR: an in-building RF-based user location and tracking system. IEEE Infocom, 2000.
• 4: Sandeep N. Bhatt , Fan R. K. Chung , Jia-Wei Hong , F. Thomson Leighton , Bojana Obrenic , Arnold L. Rosenberg , Eric J. Schwabe, Optimal emulations by butterfly-like networks, Journal of the ACM (JACM), v.43 n.2, p.293-330, March 1996 [doi>10.1145/226643.226658]
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 6: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 7: Nirupama Bulusu, John Heidemann, and Deborah Estrin. GPS-less low cost outdoor localization for very devices. 00--729. University of Southern California, April 2000.
• 8: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 9: Alvin M. Despain , David A. Patterson, X-Tree: A tree structured multi-processor computer architecture, Proceedings of the 5th annual symposium on Computer architecture, p.144-151, April 03-05, 1978 [doi>10.1145/800094.803041]
• 10: Lance Doherty, Kristofer S. J. Pister, and Laurent El Ghaoui. Convex position estimation in wireless sensor networks. IEEE INFOCOM, 2001.
• 11: Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
• 12: Lewis Girod and Deborah Estrin. Robust range estimation using acoustic and multimodal sensing. IEEERSJ International Conference on Intelligent Robots and Systems, 2001.
• 13: L. S. Heath. Graph embeddings and simplicial maps. Theory of Computer Systems, 30:599--625, 1997.
• 14: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 15: 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]
• 16: David B. Johnson. Routing in ad hoc networks of mobile hosts. IEEE Workshop on Mobile Computing Systems and Applications, 1994.
• 17: David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353:153--181. Kluwer Academic Publishers, 1996.
• 18: 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]
• 19: Richard R. Koch , F. T. Leighton , Bruce M. Maggs , Satish B. Rao , Arnold L. Rosenberg , Eric J. Schwabe, Work-preserving emulations of fixed-connection networks, Journal of the ACM (JACM), v.44 n.1, p.104-147, Jan. 1997 [doi>10.1145/256292.256299]
• 20: S. Rao Kosaraju , Mikhail J. Atallah, Optimal simulations between mesh-connected arrays of processors, Journal of the ACM (JACM), v.35 n.3, p.635-650, July 1988 [doi>10.1145/44483.44494]
• 21: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 22: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 23: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 24: David Peleg, Informative Labeling Schemes for Graphs, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.579-588, September 01, 2000
• 25: David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33:167--176, 2000.
• 26: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 27: Charles E. Perkins and Elizabeth M. Royer. Ad-hoc on-demand distance vector routing. Military Communications Conference. 1997.
• 28: 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]
• 29: Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 30: Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-aware overlay construction and server selection. IEEE INFOCOM, 2002.
• 31: 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]
• 32: Arnold L. Rosenberg and Lenwood S. Heath. Graph separators, with applications. Kluwer Academic/Plenum Publishers, 2000.
• 33: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 34: Scott Shenker, Sylvia Ratnasamy, Brad Karp, Ramesh Govindan, and Deborah Estrin. Data-centric storage in sensornets. HOTNETS, 2002.
• 35: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 36: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 37: Fan Ye, Alvin Chen, Songwu Lu, and Lixia Zhang. A scalable solution to minimum cost forwarding in large sensor networks. ICCCN, 2001.
• 38: Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Design, Performance

Keywords:
data-centric storage, routing, sensor networks