The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Energy-efficient communication protocol for wireless microsensor networks
Heinzelman, W. R., Chandrakasan, A., & Balakrishnan, H. (2005) · Proceedings of the 33rd Annual Hawaii International Conference on System Sciences · doi:10.1109/hicss.2000.926982 · Cited by 14,140
Ad-hoc on-demand distance vector routing
Perkins, C. E., & Royer, E. M. (1999) · Proceedings WMCSA'99. Second IEEE Workshop on Mobile Computing Systems and Applications · doi:10.1109/mcsa.1999.749281 · Cited by 10,313
Chord: A scalable peer-to-peer lookup service for internet applications
Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., & Balakrishnan, H. (2001) · Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/383059.383071 · Cited by 9,623
Dynamic Source Routing in Ad Hoc Wireless Networks
Johnson, D. B., & Maltz, D. A. (2007) · The Kluwer International Series in Engineering and Computer Science · doi:10.1007/978-0-585-29603-6_5 · Cited by 8,518
RADAR: an in-building RF-based user location and tracking system
Bahl, P., & Padmanabhan, V. N. (2002) · Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) · doi:10.1109/infcom.2000.832252 · Cited by 8,380 · cited 2×
“Some previously proposed range finding techniques are by observing radio signal attenuation[3], or by measuring the arrival time difference”
BackgroundMethodPastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
Rowstron, A., & Druschel, P. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45518-3_18 · Cited by 7,276
GPSR: greedy perimeter stateless routing for wireless networks
Karp, B., & Kung, H. T. (2000) · Proceedings of the 6th annual international conference on Mobile computing and networking · doi:10.1145/345910.345953 · Cited by 7,050
Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
Perkins, C. E., & Bhagwat, P. (1994) · ACM SIGCOMM Computer Communication Review · doi:10.1145/190809.190336 · Cited by 6,678
Directed diffusion: a scalable and robust communication paradigm for sensor networks
Intanagonwiwat, C., Govindan, R., & Estrin, D. (2000) · Proceedings of the 6th annual international conference on Mobile computing and networking · doi:10.1145/345910.345920 · Cited by 5,393
A performance comparison of multi-hop wireless ad hoc network routing protocols
Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y.-C., & Jetcheva, J. (1998) · Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/288235.288256 · Cited by 4,673
The Cricket location-support system
Priyantha, N. B., Chakraborty, A., & Balakrishnan, H. (2000) · Proceedings of the 6th annual international conference on Mobile computing and networking · doi:10.1145/345910.345917 · Cited by 3,716
GPS-less low-cost outdoor localization for very small devices
Bulusu, N., Heidemann, J., & Estrin, D. (2000) · IEEE Personal Communications · doi:10.1109/98.878533 · Cited by 3,592
Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers
Perkins, C. E., & Bhagwat, P. (1994) · Proceedings of the conference on Communications architectures, protocols and applications - SIGCOMM '94 · doi:10.1145/190314.190336 · Cited by 2,914
TAG: a Tiny AGgregation service for ad-hoc sensor networks
Madden, S., Franklin, M. J., Hellerstein, J. M., & Hong, W. (2002) · ACM SIGOPS Operating Systems Review · doi:10.1145/844128.844142 · Cited by 2,719
A highly adaptive distributed routing algorithm for mobile wireless networks
Park, V. D., & Corson, M. S. (2002) · Proceedings of INFOCOM '97 · doi:10.1109/infcom.1997.631180 · Cited by 2,234
Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing
Zhao, B. Y., Kubiatowicz, J. D., & Joseph, A. D. (2001) · Cited by 2,146
Convex position estimation in wireless sensor networks
Doherty, L., pister, K. S. J., & El Ghaoui, L. (2002) · Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual Joint Conference of the IEEE Computer and Communications Society (Cat. No.01CH37213) · doi:10.1109/infcom.2001.916662 · Cited by 1,632
Routing with Guaranteed Delivery in Ad Hoc Wireless Networks
Bose, P., Morin, P., Stojmenović, I., & Urrutia, J. (2001) · Wireless Networks · doi:10.1023/a:1012319418150 · Cited by 1,199
Energy-efficient communication protocols for wireless microsensor networks
Heinzelman, W., Chandrakasan, A. P., & Balakrishnan, H. (2000) · Cited by 929
Topologically-aware overlay construction and server selection
Ratnasamy, S., Handley, M. J., Karp, R. M., & Shenker, S. J. (2003) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2002.1019369 · Cited by 790
Geographic routing without location information
Rao, A., Ratnasamy, S., Papadimitriou, C., Shenker, S., & Stoica, I. (2003) · Proceedings of the 9th annual international conference on Mobile computing and networking · doi:10.1145/938985.938996 · Cited by 748
Routing with guaranteed delivery in ad hoc wireless networks
Bose, P., Morin, P., Stojmenović, I., & Urrutia, J. (1999) · Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications · doi:10.1145/313239.313282 · Cited by 668
Robust range estimation using acoustic and multimodal sensing
Girod, L., & Estrin, D. (2002) · Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180) · doi:10.1109/iros.2001.977164 · Cited by 514
GPS-free Positioning in Mobile Ad Hoc Networks
Čapkun, S., Hamdi, M., & Hubaux, J.-P. (2002) · Cluster Computing · doi:10.1023/a:1013933626682 · Cited by 510
Proximity-preserving labeling schemes
Peleg, D. (2000) · Journal of Graph Theory · doi:10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5 · Cited by 125
Cited by
Wireless sensor network survey
Yick, J., Mukherjee, B., & Ghosal, D. (2008) · Computer Networks · doi:10.1016/j.comnet.2008.04.002 · Cited by 6,255
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
Wireless sensor networks: A survey on the state of the art and the 802.15.4 and ZigBee standards
Baronti, P., Pillai, P., Chook, V. W. C., Chessa, S., Gotta, A., & Hu, Y. F. (2007) · Computer Communications · doi:10.1016/j.comcom.2006.12.020 · Cited by 1,430
Energy-Efficient Routing Protocols in Wireless Sensor Networks: A Survey
Pantazis, N. A., Nikolidakis, S. A., & Vergados, D. D. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2012.062612.00084 · Cited by 1,286
Distributed Detection of Node Replication Attacks in Sensor Networks
Parno, B., Perrig, A., & Gligor, V. (2005) · 2005 IEEE Symposium on Security and Privacy (S&P'05) · doi:10.1109/sp.2005.8 · Cited by 675
Metadata
- Authors
- Newsome, J., & Song, D.
- Venue
- Proceedings of the 1st international conference on Embedded networked sensor systems
- Publisher
- ACM
- Published
- 2003-11-05
- Pages
- 76-88
- OpenAlex
- W2118592651
- Cited by
- 308
- References
- 25
- FWCI
- 10.62
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.