Geographic Routing of Sensor Data around Voids and Obstacles

Introduction

We consider the problem of routing in ad hoc wireless networks of location aware stations, i.e. the stations know their location in a coordinate system such as the Euclidean plane. This problem is commonly called geographic routing. An emerging technology which has recently attracted considerable research efforts towards improving geographic routing algorithms is that of wireless sensor network. This text falls within this context and is concerned with the specific requirements imposed on geographic routing by such networks. The constraints imposed on the engineering of algorithms dedicated to sensor networks are stringent and routing algorithms are no exceptions to this rule: routing algorithms for sensor networks should be realistic, lightweight, on demand and efficient. Routing algorithms for sensor networks should be realistic and usable in real world scenarios, including urban scenarios with large communication blocking obstacles such as walls or buildings. Routing algorithms should also accommodate themselves with areas of low node density, also called routing holes. Of course, the success and performance of routing algorithms should not be dependent on the assumptions made on the model used as an approximation to real world wireless networks. They should be lightweight, which is notably understood in terms of topology maintenance overhead and, more generally, in terms of protocol message exchange overhead. Routing algorithms for sensor networks should also be on demand, which means they should be all-to-all (as opposed to all-to-one and one-to-all algorithms) without relying on solution which are obviously not lightweight as they require the storing of routing tables or other expensive and difficult to maintain and update information. Efficiency is measured in terms of success rate (the probability that a message will reaches its destination) and hop-stretch (i.e. the path length should be short), which somehow encompasses at a high level many other metrics, such as energy consumption, latency and traffic.

Problem definition 1The problem we are considering is that of routing messages in a network of wireless and localized nodes with regions of low node density and with large emission blocking obstacles (such as walls, buildings, lakes, etc...). The geographic routing algorithms we allow ourselves to consider should be lightweight, fast, low cost, on demand and realistic.