Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols

Topology control is one of the most fundamental issues in wireless ad hoc and sensor networks. In this chapter, we give a summary of our recently works for topology control problem. Firstly, we briefly summarize existing works and research activities. Secondly, we address QoS topology control problem in homogeneous and non-homogeneous ad hoc networks including minimizing the total energy cost and minimizing maximum transmitting power of nodes and give our results. Thirdly, we introduce strongly connected topology control including non-restricted and restricted topology control problem in the wireless sensor networks, and give the corresponding results.

Wireless sensor networks (WSNs) are now widely used in many applications. However, routing in WSNs is very challenging due to the inherent characteristics that distinguish these networks from other wireless networks. The concept of hierarchical routing is widely used to perform energy-efficient routing in WSNs. Thus, a Connected Dominating Set (CDS) has been recommended to serve as a virtual backbone for a WSN to reduce routing overhead. Fault tolerance and routing flexibility are necessary for routing since nodes in WSNs are prone to failures. Hence, it is important to maintain a certain degree of redundancy in a CDS. Therefore, the concept of k-connected m-dominating sets (kmCDS) is used to provide these redundancies. In this chapter, we present CDS based routing protocols and focus on how to construct CDS and kmCDS, including both centralized and distributed algorithms.

Broadcasting is the operation of disseminating a message originated by a source node to all reachable nodes in the network. This is a primary operation in wireless ad hoc and sensor networks and has many applications including route discovery in on-demand routing protocols. Broadcasting can be simply done through flooding, in which each node transmits/forwards the message to all its neighbors upon receiving it for the first time. However, it was shown that flooding can cause a large number of redundant transmissions particularly in networks with high average number of neighbors per node. Ideally, we would like to minimize the total number of transmissions. Unfortunately, this was proven to be NP-hard. Therefore, the aim of efficient broadcast algorithms is to reduce the total number of (redundant) transmissions as much as possible. In this chapter, we explain some of the existing classifications of broadcast algorithms and briefly describe their potentials and limitations in reducing the number of redundant transmissions.

In wireless ad hoc and sensor networks, some nodes are battery operated. They have a limited amount of energy that can be difficult, expensive or even impossible to renew like in forest fire detection, nuclear plant monitoring or explorations in hostile environments. The challenge for these networks consists in maximizing network lifetime by means of energy efficient techniques. In this chapter, we first introduce basic concepts with regard to energy efficiency and present the four classes of energy efficient techniques: energy efficient routing, node activity scheduling, optimizing the transferred information and adapting transmission power to the topology. We then focus more particularly on energy efficient routing and classify existing protocols according different criteria: data centric, hierarchical, geographical, energy criteria used for route selection, multipath routing and support of sleeping nodes. We present EOLSR, the energy efficient extension of the OLSR routing protocol supporting different types of networks like IEEE 802.11 and IEEE 802.15.4. We compare its performance with multipath routing. Node energy consumption can be considerably reduced by scheduling node activity. We will briefly present SERENA that increases not only the network lifetime but also the amount of user data delivered. Hence, SERENA contributes to a more efficient use of energy and can be used with any routing protocol. To design a network protocol, two approaches have been traditionally used: a generic one that can lead to poor performance for some applications and the opposite one, specifically designed for a given application (e.g. data gathering). An inbetween approach taking into account application specificities and environmental constraints by means of cross layering provides a very promising trade-off leading to improved performance and reactivity. We show how EOLSR benefits from cross layering with (1) the MAC layer by a better reactivity to topology changes and (2) the application layer by a reduced overhead. This induces an increased network lifetime

Geographic routing algorithms use position information for making packet forwarding decisions. Unlike topological routing algorithms, they do not need to exchange and maintain routing information and work nearly stateless. This makes geographic routing attractive for wireless ad hoc and sensor networks. Most geographic routing algorithms use a greedy strategy that tries to approach the destination in each step, e.g. by selecting the neighbor closest to the destination as a next hop. However, greedy forwarding fails in local minimum situations, i.e. when reaching a node that is closer to the destination than all its neighbors. A widely adopted approach to recover from such situations is planar graph routing, which guides the packet around the local minimum and guarantees delivery, required that a planar subgraph of the network graph can be constructed. A combination of greedy forwarding with a recovery mechanism is still the state-of-the-art in geographic routing, and many algorithms have been developed that follow this scheme. This chapter gives an overview of the fundamentals of geographic routing as well as theoretical results and new developments towards practical applicability.

Wireless sensor networks (WSNs) continue to be an active research area as the deployment of low cost wireless sensors is a promising technique for various applications such as early warning and alert systems, ecosystem monitoring, warehousing, logistics and surveillance. Sensor data is typically interpreted with reference to a sensor’s location, e.g. reporting the occurrence of an event, tracking of a moving object or monitoring the physical conditions of a region. The process of determining the location of a sensor node in a wireless sensor network, commonly known as localization, is a challenging problem as reliance on infrastructure-based technology like GPS is infeasible due to constraints arising from limited on-board computation power and energy supply, as well as, physical deployment conditions (e.g. indoors or underwater). In this chapter, we focus on range-free distributed localization schemes, in particular, schemes based on hop count that can function under realistic conditions.

The wireless sensor network is emerging as a new hotspot by exploiting the cooperation of hundreds to thousands of cheap nodes. Data gathering and data aggregation are key issues in the network. This article has taken a deep view into the current solutions for the data gathering and data aggregation. First, it has introduced the basic concepts, i.e., the data gathering system, data structure, data aggregation function and routing protocols. Secondly, it has explored the current data gathering protocols, and accordingly introduced three important tree-based / flat routing protocols, namely, SPIN, Directed Diffusion and ELECTION-based protocol, one cluster-based hierarchical protocol named as LEACH, as well as one location-based protocol named GAF. Finally, it has concerned with the real-time requirement in the applications, and introduced a novel solution by converting the real-time requirement into two constraints: node degree bounded and tree height bounded, and provided solutions for it.

Wireless sensor networks are deployed to observe remote or sensitive environments. To avoid difficult or dangerous manipulations after the deployment, power-saving strategies are used to prolong the network lifetime. Selecting active sensors, that perform the monitoring task while passive ones save energy, is one of them. The ensuing sensor area coverage issue is thus formulated as follows: every part of the deployment area, initially sensed by n deployed sensors, must be sensed by at least k active ones (k varying between 1 and n). This chapter investigates proposed techniques to designate those sensors along with existing assumptions and tools that they use.