Energy-Aware Georouting with Guaranteed Delivery in Wireless Sensor Networks with Obstacles

We propose, end-to-end (EtE), a novel EtE 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 (SP) between s and each of its neighbors in the forward direction towards the destination which minimizes the ratio of the cost of the SP to the progress (reduction in distance towards the destination). It then sends the message to the first node on the SP 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) EtE routing process 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.

---

Essia Hamouda (Corresponding author)Email:

Nathalie MittonEmail:

Bogdan PavkovicEmail:

David Simplot-RylEmail:

---

Essia Hamouda   received the BSc and the MS degree in Industrial and Systems Engineering from the Ohio State University and the University of Florida, respectively. She received a PhD in Computer Science from the University of California Riverside. Her research interests are in the areas of sensor and mobile ad hoc networks and performance evaluation of computer networks. Nathalie Mitton   is currently an INRIA full researcher. Her research interests are mainly focused on theoretical aspects of self-organization, self-stabilization, energy efficient routing and neighbour discovery algorithms for wireless sensor networks as well as RFID middlewares. She is involved in several program and organization committees such as ADHOC NOW 2009, SANET 2008 and 2007. Bogdan Pavkovic   received a MSc in Microprocessor and computer electronics from the Faculty of Technical Sciences in Novi Sad, University of Novi Sad in May of 2009. From May to December of 2009 he was an intern at INRIA, Lille—Nord Europe, France. His research interest include embedded systems and applied electronic, robotics and automated vehicles, sensor and mobile ad hoc networks and RFID technologies. David Simplot-Ryl   received the PhD degree in computer science in 1997 from the University of Lille, France. He is now a professor at the University of Lille 1 and head of the POPS research team at the INRIA research centre Lille—Nord Europe. His research interests are in the areas of sensor and mobile ad hoc networks, mobile and distributed computing, and RFID technologies. He is editor and guest editor of several journals, cochair of conferences and workshop. Since 2008, he is scientific deputy of the INRIA research centre Lille—Nord Europe.