Geographic Routing of Sensor Data around Voids and Obstacles

Geographic Routing of Sensor Data around Voids and Obstacles

Sotiris Nikoletseas (University of Patras, Greece), Olivier Powell (University of Geneva, Switzerland) and Jose Rolim (University of Geneva, Switzerland)
DOI: 10.4018/978-1-60566-328-9.ch012
OnDemand PDF Download:
List Price: $37.50


Geographic routing is becoming the protocol of choice for many sensor network applications. Some very efficient geographic routing algorithms exist, however they require a preliminary planarization of the communication graph. Planarization induces overhead which makes this approach not optimal when lightweight protocols are required. On the other hand, georouting algorithms which do not rely on planarization have fairly low success rates and either fail to route messages around all but the simplest obstacles or have a high topology control overhead (e.g. contour detection algorithms). This chapter describes the GRIC algorithm which was designed to overcome some of those limitations. The GRIC algorithm was proposed in (Powell & Nikoletseas, 2007a). It is the first lightweight and efficient on demand (i.e. all-to-all) geographic routing algorithm which does not require planarization, has almost 100% delivery rates (when no obstacles are added), and behaves well in the presence of large communication blocking obstacles.
Chapter Preview


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.

Complete Chapter List

Search this Book: