Select and protest based beaconless georouting with guaranteed delivery in wireless sensor networks

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 which 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, but only if there is no other neighbor within their forbidden region. Protest messages are used to correct occasionally wrong selections by 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 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. We develop a theoretical framework for delay functions and show both theoretically and in simulations that with a function of angle and distance we can reduce the number of protests by a factor of 2 in comparison to a simple angle-based delay function.