Home > Publications > Journals > Energy-aware Georouting with Guaranteed Delivery in Wireless Sensor Networks with Obstacles

Essia Elhafsi, Nathalie Mitton, Bogdan Pavkovic and David Simplot-Ryl

International Journal of Wireless Information, 8(3), September 2009

Tuesday 1 September 2009

We propose, EtE, a novel end-to-end localized routing protocol for

wireless sensor networks that is energy-efficient and guarantees delivery.

To forward a packet, a node s in graph G computes the cost of the energy

weighted shortest path between s and each of its neighbors in the forward

direction towards the destination which minimizes the ratio of the cost

of the shortest path to the progress (reduction in distance towards the

destination). It then sends the message to the first node on the shortest

path from s to x: say node x’. Node x’ restarts the same greedy routing

process until the destination is reached or an obstacle is encountered

and the routing fails. To recover from the latter scenario, local minima

trap, our algorithm invokes an energy-aware Face routing that guarantees

delivery. Our work is the first to optimize energy consumption of Face

routing. It works as follows. First, it builds a connected dominating set

from graph G, second it computes its Gabriel graph to obtain the planar

graph G’. Face routing is invoked and applied to G’only to determine

which edges to follow in the recovery process. On each edge, greedy routing

is applied. This two-phase (greedy-Face) End-to-End routing process

(EtE) reiterates until the final destination is reached. Simulation results

show that EtE outperforms several existing geographical routing on energy

consumption metric and delivery rate. Moreover, we prove that the

computed path length and the total energy of the path are constant factors

of the optimal for dense networks.