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.
- B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg. Improved routing strategies with succinct tables. Journal of Algorithms, 11 (3):307--341, 1990.]] Google ScholarDigital Library
- B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, 5 (2):151--162, 1992.]] Google ScholarDigital Library
- P. Bahl and V. N. Padmanabhan. RADAR: an in-building RF-based user location and tracking system. IEEE Infocom, 2000.]]Google ScholarCross Ref
- S. N. Bhatt, F. R. K. Chung, J. W. Hong, F. T. Leighton, B. Obrenic, A. L. Rosenberg, and E. J. Schwabe. Optimal emulations by butterfly-like networks. Journal of the ACM, 43:293--330, 1996.]] Google ScholarDigital Library
- Prosenjit Bose, Pat Morin, Ivan Stojmenovic, and Jorge Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999.]] Google ScholarDigital Library
- Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A performance comparison of multi-hop wireless ad hoc network routing protocols. International Conference on Mobile Computing and Networking, 1998.]] Google ScholarDigital Library
- Nirupama Bulusu, John Heidemann, and Deborah Estrin. GPS-less low cost outdoor localization for very devices. 00--729. University of Southern California, April 2000.]]Google Scholar
- Srdan Capkun, Maher Hamdi, and Jean-Pierre Hubaux. GPS-free positioning in mobile ad-hoc networks. Hawaii International Conference on Systems Sciences, 2001.]] Google ScholarDigital Library
- Alvin M. Despain and David A. Patterson. X-tree: a tree structured multi-processor architecture. 5th International Symposium on Computer Architecture, pages 144--151, 1978.]] Google ScholarDigital Library
- Lance Doherty, Kristofer S. J. Pister, and Laurent El Ghaoui. Convex position estimation in wireless sensor networks. IEEE INFOCOM, 2001.]]Google ScholarCross Ref
- T. Eilam, C. Gavoille, and D. Peleg. Compact routing schemes with low stretch factor. 17th Annual ACM Symposium on Principles of Distributed Computing, pages 11--20, 1998.]] Google ScholarDigital Library
- Lewis Girod and Deborah Estrin. Robust range estimation using acoustic and multimodal sensing. IEEERSJ International Conference on Intelligent Robots and Systems, 2001.]]Google ScholarCross Ref
- L. S. Heath. Graph embeddings and simplicial maps. Theory of Computer Systems, 30:599--625, 1997.]]Google ScholarCross Ref
- Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. Hawaii International Conference on Systems Sciences, 2000.]] Google ScholarDigital Library
- Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. MOBICOM, pages 56--67, 2000.]] Google ScholarDigital Library
- David B. Johnson. Routing in ad hoc networks of mobile hosts. IEEE Workshop on Mobile Computing Systems and Applications, 1994.]]Google Scholar
- David B. Johnson and David A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353:153--181. Kluwer Academic Publishers, 1996.]]Google ScholarCross Ref
- Brad Karp and H. T. Kung. GPSR: greedy perimeter stateless routing for wireless networks. International Conference on Mobile Computing and Networking, pages 243--254, 2000.]] Google ScholarDigital Library
- R. Koch, F. T. Leighton, B. Maggs, S. Rao, and A. L. Rosenberg. Work-preserving emulations of fixed-connection networks. Journal of the ACM, 44:104--147, 1997.]] Google ScholarDigital Library
- S. R. Kosaraju and M. J. Atallah Optimal simulations between mesh-connected arrays of processors. Journal of the ACM, 35:635--650, 1988.]] Google ScholarDigital Library
- Sam Madden, Michael J. Franklin, Joseph M. Hellerstein, and Wei Hong. TAG: a tiny aggregation service for ad hoc sensor networks. Symposium on Operating Systems Design and Implementation, 2002.]] Google ScholarDigital Library
- Vincent D. Park and M. Scott Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. IEEE INFOCOM, 1997.]] Google ScholarDigital Library
- D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36 (3):510--530, 1989.]] Google ScholarDigital Library
- David Peleg. Informative labeling schemes for graphs. Mathematical Foundations of Computer Science, pages 579--588, 2000.]] Google ScholarDigital Library
- David Peleg. Proximity-preserving labeling schemes. Journal of Graph Theory, 33:167--176, 2000.]]Google ScholarDigital Library
- Charles Perkins and Pravin Bhagwat. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. ACM SIGCOMM Conference, 1994.]] Google ScholarDigital Library
- Charles E. Perkins and Elizabeth M. Royer. Ad-hoc on-demand distance vector routing. Military Communications Conference. 1997.]]Google Scholar
- Nissanka B. Priyantha, Anit Chakraborty, and Hari Balakrishnan. The Cricket location-support system. International Conference on Mobile Computing and Networking 2000.]] Google ScholarDigital Library
- Ananth Rao, Christos Papadimitriou, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica. Geographic routing without location information. Mobicom, 2003.]] Google ScholarDigital Library
- Sylvia Ratnasamy, Mark Handley, Richard Karp, and Scott Shenker. Topologically-aware overlay construction and server selection. IEEE INFOCOM, 2002.]]Google ScholarCross Ref
- Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, and Scott Shenker. GHT: a geographic hash table for data-centric storage. WSNA, 2002.]] Google ScholarDigital Library
- Arnold L. Rosenberg and Lenwood S. Heath. Graph separators, with applications. Kluwer Academic/Plenum Publishers, 2000.]]Google Scholar
- Antony Rowstron and Peter Druschel. Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems. IFIPACM International Conference on Distributed Systems Platforms (Heidelberg, Germany, 12--16 November 2001), pages 329--350, 2001.]] Google ScholarDigital Library
- Scott Shenker, Sylvia Ratnasamy, Brad Karp, Ramesh Govindan, and Deborah Estrin. Data-centric storage in sensornets. HOTNETS, 2002.]]Google Scholar
- Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: a scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Conference (San Diego, CA, 27--31 August 2001). Published as Computer Communication Review, 31 (4):149--160, 2001.]] Google ScholarDigital Library
- Mikkel Thorup and Uri Zwick. Compact routing schemes. SPAA, 2001.]] Google ScholarDigital Library
- Fan Ye, Alvin Chen, Songwu Lu, and Lixia Zhang. A scalable solution to minimum cost forwarding in large sensor networks. ICCCN, 2001.]]Google Scholar
- Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. UCB Technical Report UCBCSD--01--1141. Computer Science Division (EECS) University of California, Berkeley, April 2001.]] Google ScholarDigital Library
Index Terms
- GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information
Recommendations
Improving End-to-End Routing Performance of Greedy Forwarding in Sensor Networks
Greedy forwarding is a simple yet efficient technique employed by many routing protocols. It is ideal to realize point-to-point routing in wireless sensor networks because packets can be delivered by only maintaining a small set of neighbors' ...
Ad-Hoc Buffering in Neighbor Nodes for Burst Data Transmissions in Wireless Sensor Networks
ICCSA '12: Proceedings of the 2012 12th International Conference on Computational Science and Its ApplicationsIn sensor networks, burst sensor messages are required to be transmitted along a wireless multihop routes to a sink node with no lost sensor messages and with shorter transmission delay. However, due to congestions, buffers in intermediate sensor nodes ...
MAP: medial axis based geometric routing in sensor networks
MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and networkingOne of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communication. Important consideration includes scalability, routing complexity, the length of the ...
Comments