GEM: Graph EMbedding for Routing and Data-Centric Storage in Sensor Networks without Geographic Information
Abstract
In this paper, the authors introduce GEM (Graph EMbedding for sensor networks), an infrastructure for node-to-node routing and data-centric storage and information processing in sensor networks. In GEM, they 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, the authors have developed a concrete graph embedding method, VPCS (Virtual Polar Coordinate Space), which embeds a ringed tree into the network topology. They also have 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. 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 2003
- Accession Number
- ADA457595
Entities
People
- Dawn Song
- James Newsome
Organizations
- Carnegie Mellon University