Select-and-Protest-Based Beaconless Georouting with Guaranteed Delivery in Wireless Sensor Networks
- 1 April 2008
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 346-350
- https://doi.org/10.1109/infocom.2008.78
Abstract
Recently proposed beaconless georouting algorithms are fully reactive, with nodes forwarding packets without prior knowledge of their neighbors. However, existing approaches for recovery from local minima can either not guarantee delivery or they require the exchange of complete neighborhood information. We describe two general methods that enable completely reactive face routing with guaranteed delivery. The Beaconless Forwarder Planarization (BFP) scheme finds correct edges of a local planar subgraph at the forwarder node without hearing from all neighbors. Face routing then continues properly. Angular Relaying determines directly the next hop of a face traversal. Both schemes are based on the Select and Protest principle. Neighbors respond according to a delay function, if they do not violate the condition for a planar subgraph construction. Protest messages are used to remove falsely selected neighbors that are not in the planar subgraph. We show that a correct beaconless planar subgraph construction is not possible without protests. We also show the impact of the chosen planar subgraph construction on the message complexity. This leads to the definition of the Circlunar Neighborhood Graph (CNG), a new proximity graph, that enables BFP with a bounded number of messages in the worst case, which is not possible when using the Gabriel graph (GG). The CNG is sparser than the GG, but this does not lead to a performance degradation. Simulation results show similar message complexities in the average case when using CNG and GG. Angular Relaying uses a delay function that is based on the angular distance to the previous hop. Simulation results show that in comparison to BFP more protests are used, but overall message complexity can be further reduced.Keywords
This publication has 19 references indexed in Scilit:
- On the Spanning Ratio of Gabriel Graphs and beta-SkeletonsSIAM Journal on Discrete Mathematics, 2006
- BLR: beacon-less routing algorithm for mobile ad hoc networksComputer Communications, 2004
- Ordered theta graphsComputational Geometry, 2004
- Partial Delaunay triangulation and degree limited localized Bluetooth scatternet formationIEEE Transactions on Parallel and Distributed Systems, 2004
- Approximate MST for UDG LocallyLecture Notes in Computer Science, 2003
- Relative neighborhood graphs and their relativesProceedings of the IEEE, 1992
- Properties of some Euclidean proximity graphsPattern Recognition Letters, 1992
- The expected size of some graphs in computational geometryComputers & Mathematics with Applications, 1988
- Optimal Transmission Ranges for Randomly Distributed Packet Radio TerminalsIEEE Transactions on Communications, 1984
- A New Statistical Approach to Geographic Variation AnalysisSystematic Zoology, 1969