The authors study the problem of fast and robust data propagation in wireless sensor networks in the presence of obstacles obstructing communication. They survey representative state of the art techniques, such as variations of geographic routing, which is known to scale well, mainly due to its greedy nature and low memory requirements. Still, most of these algorithms are concerned with finding some path, while the optimality of the path is difficult to achieve. Towards improving QoS, and especially latency for time-critical applications, in this chapter, the authors are presenting a novel geographic routing algorithm with obstacle avoidance properties. It aims at finding the optimal path from a source to a destination when some areas of the network are unavailable for routing due to low local density or obstacle presence. It locally and gradually with time (but, as we show, quite fast) evaluates and updates the suitability of the previously used paths and ignores non optimal paths for further routing. The performance comparison to existing state of the art protocols shows that this approach performs much better in terms of path length, thus minimizing latency and space, while introducing low overhead and being energy efficient.
TopIntroduction
Recent advances in micro-electromechanical systems (MEMS) and wireless networking technologies have enabled the development of very small sensing devices called sensor nodes. Unlike traditional sensors that operate in a passive mode, sensor nodes are smart devices with sensing, data-processing and wireless transmission capabilities. Data can thus be collected, processed and shared with neighbors. Sensor nodes are meant to be deployed in large wireless sensor networks instrumenting the physical world. Originally developed for tactical surveillance in military applications, they are expected to find growing importance in civil applications such as building, industrial and home automation, infrastructure monitoring, warehousing and data mining, agriculture and security. Their range of applications makes sensor networks heterogeneous in terms of size, density and hardware capacity. Their great attractiveness follows from the availability of low cost, low power and miniaturized sensor nodes that pervade, instrument and augment the physical world without requiring human intervention: sensor networks are self-organizing, self repairing and highly autonomous. Those properties are implemented by designing protocols addressing the specific requirements of sensor networks.
Common to all sensor net architecture and applications is the need to propagate data inside the network. Almost every scenario implies multi-hop data transmission because of the low power used for radio transmission mostly to limit depletion of the scarce energy resources of battery powered sensor nodes. Needless to say, sensory data exchange is usually done in an environment in which wireless communication and data routing is obstructed, e.g. by walls, narrow corridors, voids due to physical failures of some devices etc. The theme of this chapter is exactly how to efficiently route sensory data in the presence of obstacles.
Computing the shortest path between two nodes in a graph is a problem intensively studied in graph theory. For the geometric domain, where only local information is available and the path is built based on the geographical position of the destination and of the one hop neighbors, a plethora of solutions and applications exists as well. We will consider the behavior of path finding algorithms in the geometric domain, in the case when there are obstacles and local irregularities in the initial network configuration. Because of the severe limitations of sensor network devices and the lack of global network knowledge, our purpose is to find in a distributed manner the shortest path that avoids the obstacles between two points using only local geographical information.
In the context of a global computing approach, our aim is to include wireless nodes in an Internet-based overlay computer in a transparent and efficient way.. We envision diverse interacting wireless elements (mobile users/phones, sensors, robots, actuators), hybrid/hierarchical compositions and heterogeneous wired interconnections. The context is highly dynamic (due to mobility, failures, obstacles), heterogeneous, and the wireless devices are resource-constrained and low-cost. Yet, we come up with algorithmic solutions that are efficient (QoS), robust, secure and easy to manage.
QoS basically refers to fast propagation of sensory data (the low latency challenge), since most applications are time-critical. However, we notice the existence of inherent trade-offs between latency and other crucial performance metrics, mostly energy dissipation. Hence, satisfactory latency vs. energy tradeoffs is crucial, and can be achieved by several methods (and their hybrid combination). Such methods relate to several network layers, including power saving schemes at the individual device level, communication optimization at the routing layer, as well as low additional communication overhead1. In this chapter, we focus on the latter, i.e. our algorithms aim to minimize the number of hops needed to propagate data around obstacles, to both improve latency and energy efficiency, while incurring a small communication overhead.
In our perspective, the Global Computer is in fact the Internet/WEB enhanced by mobile users and embedded sensors. The global network computer is structured in three interacting layers: the P2P (Overlay) Network (where applications are executed on powerful devices that communicate via fixed networks), the Wireless Peers (mobile/resource-limited devices that communicate over wireless mediums) and the Gateway Peers (an intermediate layer for wireless access).