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.