Wireless Sensor Networks. Routing Protocol Overview

CHAPTER 1

INTRODUCTION

1.1 OVERVIEW

The explosive growth of information and communication technologies in the last decade has opened new possibilities in networking of ubiquitous devices. The significant developments made in communication were the advent of wireless based networks. Wireless networks belong to an important class of networks that transmit data between devices using radio waves instead of wires. Most of the wireless networks utilize either the microwave frequencies around the 2.4 GHz ISM (Industrial, Scientific and Medical) band for a bandwidth of about 83 MHz, or around the 5 GHz U-NII (Unlicensed-National Information Infrastructure) band for a bandwidth of about 300 MHz divided into two parts. These are simple, fast, easy to establish and cheap even though the initial cost of installation is high. The main advantage of wireless networks is enhancement of the mobility of devices.

The convergence of the communication, networking and wireless technologies coupled with advances in engineering, is paving the way for a new breed of sensor networks capable of achieving higher resolution and accuracy. The special networks called as wireless sensor network is formed by the wirelessly interconnected systems of sensor nodes. Generally the sensor nodes self-organize an appropriate network infrastructure and use the multi-hopping technique to establish connections among the nodes (Yu et al 2006). The sensor nodes are often programmed to work either on a continuous basis or event driven working modes. Depending on the applications the data samples should be delivered either as soon as it is detected, or within a predefined latency bound.

WSNs are extremely small in size and are easy to install in diverse locations and different applications. They are relatively inexpensive, yet reliable, with a high fault tolerance, due to distribution of multiple interconnected nodes (Akyildiz et al 2002). They are also simple to use and extremely versatile due to their physical nature, thus qualifying for deployment in applications involving monitoring the extreme weather conditions, volcanoes, floods, glaciers, fire outbreaks etc. One of the major advantages of WSN lies in its ability to monitor and control the phenomenon from remote locations with greater accuracy.

Despite all the obvious and aforementioned advantages, WSNs have certain limitations in terms of their lifetime. More specifically, the capability of the nodes is limited by their communication range and the energy supply in the form of a battery (Culler et al 2004). Even though the initial capability of each individual node is limited, the aggregate power of the entire network is sufficient for the required mission (Yu et al 2006).

1.2 WIRELESS SENSOR NETWORKS

In a wireless sensor network, nodes periodically generate data samples and communicate them to the nearest sink. Sinks are considered as the base stations for the sensor nodes (Akyildiz 2002). Typically the sinks are entrusted with the task of relaying the collected data to the server. In “distributed systems”, the sink could be a designated “coordinating server”, responsible for archiving the data and answering user queries (Chan et al 2010).In most scenarios, the sink may not be within the direct communication range of the sensor node and hence the data sample from the sensor nodes has to be forwarded to the sink by intermediate sensor nodes using some routing protocols (Karaki & Kamal 2004).

Normally a hopping technique is employed, where each node sends its raw data directly to the intermediate nodes which act as passive message forwarders without inspecting or modifying its original data. In such hopping based routing methods, the nodes closer to the sink will receive the data frequently from other nodes. As a result, these nodes which are located near the sink are likely to run out of energy (Almi'ani et al 2010). Moreover, when these nodes fail, other nodes are also unconnected and cannot communicate with the sink. As a result the network ceases to operate. This common problem occurs largely independent of the communication protocols used in the network.

1.3 ROUTING PROTOCOLS IN WSN

Sensor nodes have restricted storage, computational and energy resources, these restrictions place a limit on the types of deployable routing mechanisms. Routing protocol disseminates information that enables the sensor nodes to select routes to communicate with other nodes on the network and the choice of the route is determined by the routing algorithms (Rodoplu & Meng 1999). Thus the routing protocol helps the nodes to gain knowledge about the topology of the network to which it is attached directly.

There are mainly two types of routing processes: one is static routing and the other is dynamic routing. In a static routing, the routing tables are set up in a static manner in the nodes. The network routes for the packet are initially set between the nodes. However, if any node on the specified route fails, the data may not reach the destination. In a dynamic routing, routing tables in the routers often change whenever the possible routes change. Dynamic routing is more suitable as the nodes in WSNs may frequently change their position and die at any moment (Bhattacharyya et al 2010).

The routing protocols are classified into single hop and multi hop routing. In a single hop routing, sensor node directly communicates with the sink to share the gathered information. Energy consumption is high in the network using single hop protocol.

In multi hop routing, data is routed through the intermediate nodes to the base station. Each node transfers sensed data to the immediate node which in turn transfers the data to the next immediate node and finally the data reaches the base station. Energy consumption in this kind of routing protocol is less and thus the lifetime of the nodes is high.

The major challenge to the efficient operation of wireless sensor network lies in its ability to deliver the sensed information from the nodes to the sink within the specific time duration without the loss of data packets with high security. The sensor nodes depend on the battery source for their operation which has limited capacity. Thus the energy resource of the sensor nodes has to be used efficiently in order to increase the operational lifetime of the network.

In addition the multi-hop routing has been inefficient in addressing the requirement of the network, as it often overloads the senor nodes in close proximity to the sink and could potentially lead to network failure. High degree of security of data with minimum overload is needed for various applications. Thus the problem in improving the efficiency of a wireless sensor network has to be addressed by designing an efficient routing and security protocol for data gathering. In addition the reliability and availability of the network should be also ensured as it guarantees maximum data transfer from the node to the sink without loss of data.

The applications of WSNs are manifold but a majority of the applications necessitate activity of the network round the clock, so that functions like monitoring, data gathering and dissemination could be carried out efficiently. However the continuous operation of sensor nodes depends on the battery life span to a great extent. In addition, the specific placement of nodes in diverse locations is mostly inaccessible to permit change of a new battery.

If energy efficiency has to be improved in WSN, the above scenario poses an open challenge to the researchers. This improvement would not only enhance the effectiveness of data gathering in current monitoring applications, but would also facilitate innovative extensions of the applications of the devices in variety of fields.

CHAPTER 2

BACKGROUND ON WIRELESS SENSOR NETWORKS (WSN)

2.1 INTRODUCTION

Advancements made in the field of communication and internet technologies in the last decade have extended the applications of devices and systems in various fields to the next higher level. For example, the application of sensor technology in condition monitoring has drawn the attention of researchers to innovatively combine the power of wireless technology with the sensor systems to develop a superior wireless sensor network. Over the years wireless sensor networks have evolved into a more reliable and efficient system in various applications like condition monitoring and fault detection in industries, monitoring environmental variables, tracking applications, military surveillance etc.

Wireless sensor networks consist of sensor nodes deployed in a field to collect the sensed data, process the sensed data and transmit it wirelessly to the base station for future analyzes and take decisions based on received information (Estrin et al 1999, Min et al 2001, Pottie&Kaiser 2000).

Each sensor node can be considered as an autonomous system containing a sensing unit, computation unit, communication unit and power unit. However most of the applications require the nodes to be connected in a collaborative manner to accomplish the specified task. The remaining sections of this chapter discuss the background of the WSN including its application, architecture and topology. The chapter also throws light on the data gathering in the WSN, which is core theme of this research. Finally the metrics, challenges and issues in WSN are discussed.

2.2 ARCHITECTURE OF WIRELESS SENSOR NODES

The standard components of a wireless sensor node used in data collection system are depicted in Figure 2.1. A sensor node consists of sensing unit, processing unit, communication unit and power unit. Their functions and resource needs are outlined below.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.1 Components of a Sensor Node

2.2.1 Sensing Unit

Sensing units consist of sensors and Analog to Digital Convertors (ADC). The basic function of the Sensing unit is to collect data from the field. ADC system in the sensing unit converts the sensed analog signal into a digital format which is given into the processing unit.

2.2.2 Processing Unit

A processing unit has a processor and storage. It performs the entire computational task related to the collaboration of sensor nodes with other nodes, processing the sensed data to add meaning to it etc. The basic operation in the processing unit depends on the underlying operating system (OS) in delivering and receiving instructions from the sensing and communication units through micro-device drivers. Energy is consumed when software instructions are executed. The micro-device drivers cause leakage energy even in the absence of any computation and its magnitude can be as high as 50 % of the total computing energy (Wang Q & Hassanein 2006).

2.2.3 Communication Unit

The communication unit has a transceiver which is responsible for transmission and reception of data between sensor nodes and base station/sink. According to the studies conducted by Haenggi (2003) and Rex Min &Anantha Ch (2002), The Communication unit consumes sizeable energy in a WSN. Yao & Gehrke (2003) have approximated that power required to send just one bit of information could power 1000 processor operations. In addition, energy consumption across the node increases as the transmission distance increases. Hence WSN’s employ multi-hopping scheduling protocols which utilize short range transceiver units. Typically, these protocols assume that applications are insensitive to end-to-end delay and therefore trade-off this delay to increase energy savings.

2.2.4 Power Unit

It is the vital unit of the sensor node and provides power to the sensing, processing and communication units. The entire operation of the sensor node depends on the supply of reliable and uninterrupted power from this unit. Normally non-rechargeable batteries are used in the sensor nodes and in some cases non renewable sources may be used to charge the batteries using photo voltaic panels.

2.3 DATA GATHERING IN WIRELESS SENSOR NETWORKS

2.3.1 Challenges and issues

Inspite of numerous advantages of wireless sensor network over other traditional networks, they are subjected to a variety of unique challenges and face more serious issues than other network systems. These issues and challenges impact the design of wireless sensor network. As a result, the routing protocols and algorithms differ significantly from other networks. This section describes the most important challenges and issues in wireless sensor networks.

Self organization

In many applications sensor nodes are deployed in large numbers in remote areas. Hence it is almost impossible to configure the nodes manually. Thus the nodes must be designed with self organization features like self configuration and self maintenance capabilities.

Routing

The design of an efficient routing protocol for WSNs has to consider several aspects such as power constraints of the sensor nodes, limitation in computation capability of nodes, frequent change in topology of the networks and pattern of communication etc.

Moreover Metrics such as energy consumption, overhead, concurrent scheduling, delay, stability, scalability, etc are all taken into considerations while designing routing protocols (Guo 2010).

Energy efficiency

Sensor nodes perform various typical operations like data gathering, data processing, data buffering and transmitting the sensed data. Thus large energy would be consumed in these processes. As a result, the node may die and will not be able to communicate with other node. A communication gap emerges and nodes keep searching for active nodes to reestablish the link in alternate routes. This again contributes to energy loss and finally results in the reduction of network lifetime. Thus the sensor network protocols must be energy-efficient (Heo & Varshney 2005).

Reliability

Reliability of data is an important factor to be considered in the applications involving WSN. Factors like attenuation and interference highly impact the transmission of data packets in the wireless link and as a result the packet could be easily lost. Moreover as the WSNs are deployed in environments which are prone to be affected by these factors, establishment of a reliable communication should be given utmost importance.

Data aggregation

In applications involving multiple sensor nodes in a specific area, nodes often collect similar data. Moreover all the sensed data may not be useful and it is not necessary to transmit the same data from multiple nodes to the base station. Thus data aggregation comes as convenient technique where the sensed data is aggregated (based on some criteria) in the neighborhood, compressed and sent to base station/sink. Research in data aggregation offers great challenge to the researchers to design better system.

Scalability

WSNs are employed in applications which often need continuous monitoring of events or when the events need to be monitored at specific intervals. Similarly the applications may involve a few sensor nodes. A few hundreds of nodes may be required in other cases. Interestingly a sensor node may be sufficient to monitor an event while, in other cases, many sensor nodes monitor the same event simultaneously. Thus, the scalability of the network should be taken into consideration, as the network evolves always and more nodes are added. The scalability of the network should be ensured without affecting the network performance. Simultaneous operation of large number of the nodes may result in collision and eventual loss of packets. Such scenarios will drastically influence the applications involving WSNs. A variety of solutions are suggested in the literature to overcome issues in scalability in WSNs.

Security

WSNs are deployed in open and remote physical environments, and use shared transmission which is prone to a multitude of security attacks. The range of the attacks includes deny-of-service (DOS) attack, data hijacking, malicious attacks to modify the data etc. Hence, integrity is ensured by incorporating proper security mechanisms and related protocols.

Fault tolerance

Since the sensor nodes are often deployed in hazardous, harsh and hostile environments and as nodes have limited energy capacity, there are more chances for the nodes to fail. Hence the fault tolerant sensor node is important for the network to sustain in the extreme conditions and continue its functionalities even in the presence of node failures.

2.3.2 Network Topology

This section identifies and studies the various types of network topologies commonly employed in wireless sensor networks. The development and deployment of WSNs have taken traditional network topologies in new directions. The basic WSN data network topologies are broadly classified into four categories as flat topology, cluster-based topology, chain-based topology and tree-based topology.

2.3.2.1 Flat topology

Flat topology is also called as unstructured topology which is characterized by absence of any defined topology. Here all the sensor nodes play equal roles in the network formation. Different protocols have been proposed based on flat/unstructured topology. Figure 2.2 shows flat topology architecture.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.2 Flat Topology

In flat topology, nodes use the flooding technique to find the best route towards the sink node. Data and control packets are broadcasted by each node. There is a drawback in this topology which needs to be highlighted, there is a possibility that the neighboring nodes in a given region can receive duplicate packets if two or more sensors from the same region sense the data.

Another drawback of the flat topology is that the energy of the nodes is lost quickly as the nodes need to broadcast continuously and the network may fail ultimately. Some examples of this routing protocol are Sensor Protocols for Information via negotiation (SPIN) (Intanagonwiwat 2002), Directed-Diffusion (Kulik et al 2002), Rumor-Routing (Semong et al 2009), etc.

2.3.2.2 Cluster-based topology

In a cluster based networks, the nodes in a network transmit sensed data to its cluster head. Cluster-based protocol is particularly employed in applications that use hundreds or thousands of nodes. In a cluster-based protocol clustering, three different types of elements can be identified in the WSN: sensor nodes (SNs), base station (BS) and cluster heads (CH) as shown in the Figure 2.3.

The energy consumption in this topology is less when compared to flat topology which increases the network life time. Some examples of routing protocol based on cluster-based topology are Low Energy Adaptive Clustering Hierarchy (LEACH) proposed by Heinzelman et al (2002), Hybrid Energy Efficient Distributed clustering Approach (HEED) proposed by Younis & Fahmy (2004), and Clustered Diffusion with Dynamic Data Aggregation (CLUDDA) proposed by Chatterjea &Havinga (2003).

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.3 Cluster-based Topology Architecture

2.3.2.3 Chain-based topology

The key idea behind chain based topology is that each sensor node transmits only to its closest neighbor. In this topology, the sensor nodes are connected in the form of a chain, in which a node transmits only to its closest node in the chain. Each chain has a leader node, which acts as sink for the entire chain. The data is relayed from one node to another (neighbor) node which in turn transmits to the next one and finally data reaches the sink. Thus all the sensed data are transmitted to the leader node Power Efficient Data Aggregation protocol for Sensor Information Systems (PEGASIS) proposed by Lindsey et al (2002) is based on chain-topology. Figure 2.4 depicts the chain-based topology employed in PEGASIS. The nodes using PEGASIS protocol communicate only with closest neighbors. Thus the network lifetime is extended as the distance of communication of each node is restricted to its nearest neighbor.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.4 Chain-oriented Topology Architecture

2.3.2.4 Tree-based topology

In this topology, the sensor nodes are organized into a logical tree structure. Data is passed from a leaf node to its parent node also called as non leaf node. Each node which receives data from its child node sends it to its parent node after aggregating the original data with its own data. Figure 2.5 shows the typical data flow pattern in tree-based topology from leaf nodes to the root node (sink). The tree structure actually avoids the flooding of data and the data flows in the unicast pattern instead of broadcast. This way the topology can save energy.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.5 Tree-based Topology Architecture

Tree topology has been employed in the design of various protocols for wireless sensor networks such as data collection scheme TBDCS (Li et al 2006), routing protocols (Woo et al 2003), data dissemination protocols (Messina et al 2007 ,Fan et al 2008) etc.

In the tree based topology, the non-leaf nodes are loaded heavily as they need to forward data from the leafy nodes. Thus the energy of the non leaf nodes decreases rapidly. As a result, the overall energy balance is not uniform in the network. If the energy of a non leaf node decreases beyond the specified threshold value, it may fail to participate in the communication and the link may be broken.

2.3.3 Stages in Data Gathering in WSN

Wireless sensor networks are deployed in many applications primarily for collecting the sensed data, which is collected either continuously or at predefined specific time interval. Wireless sensor data collection involves three major stages as shown in the Figure 2.6(Wang &Liu 2011).

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.6 Stages in Data Collection in Wireless Sensor Networks

2.3.3.1 Deployment stage

Deployment stage is concerned with addressing issues in efficient deployment of sensor nodes in the sensing field. Two important issues that need to be addressed in this stage are area coverage and location coverage deployment. Area-coverage deployment entails that each location within the sensing field must be covered by some sensor nodes. In Location-coverage each sensor nodes must be attached to some locations specified by the applications (Wang &Liu 2011).

2.3.3.2 Control message dissemination

One to many traffic pattern is adopted in this stage for disseminating control message (Query). The major challenge in this stage lies in the dissemination messages to nodes with very low transmission costs, low latencies and in a reliable manner. Flooding and gossiping can be considered for control message dissemination in WSNs.

2.3.3.3 Data delivery stage

This stage is the main task of the WSN, that is, collection of the data from the sensor nodes and delivering to the base station (Wang &Liu 2011). Many-to-one traffic pattern is adopted in this stage (Puccinelli, 2007).

The manner in which data are transferred between the base station and the location where the target phenomena are observed is an important aspect and a basic feature of wireless sensor networks. The challenges in developing reliable techniques in data gathering in WSN have drawn the attention of researchers over many years. Earlier studies recommend direct exchange of data between the sensor nodes and the base stations using the single-hop approach. However the major drawback of this approach was that, as the distance between the sensor node and base station increases the stored energy of the nodes are depleted quickly. Hence the cost associated with the data transfer increases and the overall lifetime of the network is reduced.

2.3.4 Data Collection Approaches

The process that makes the communication going between nodes and sink is data collection. In general the data collection approaches are classified into static nodes based data collection and mobile elements based data collection.

2.3.4.1 Static nodes based data collection

In a static nodes based data collection method, the sensor node forwards the data by hops. The network and nodes are static. Static nodes based data collection method can use a flat or hierarchical architecture. In a flat architecture all the nodes are designed to perform similar task. Every node transmits data to the base station using single-hop or multi-hop routing technique. In a multi-hop routing, data is sent to their immediate neighbors which in turn transmitted to the next node and reaches the base station.

In Hierarchical form of data collection technique, the nodes are categorized into two layers as lower layer and higher layer. The nodes in the lower level layers are homogenous sensor nodes. The nodes in the higher layer are more powerful than the nodes in the lower layer. The higher layer nodes are called as cluster heads.

2.3.4.2 Mobile elements based data collection techniques

In the mobile elements based data collection technique as shown in Figure 2.7.A special mobile element collect data periodically from nodes. These mobile elements, also called relocatable nodes, position themselves at various points in the network to collect data from the nodes and transmit to the sink. The base station is static and receives data from mobile elements.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.7 Architecture of a WSN-ME with Relocatable Nodes

2.3.4.3 Mobile sink based WSN

The mobile elements based network can be further improved by adding mobility to the sink/base station. The mobile sinks are the special kind of sensor nodes which acts as destination for the data generated by the nodes. The mobile sinks collect data by travelling around the network and transmit the data thus collected wirelessly to the users. The mobile sink based WSN architecture is depicted in Figure 2.8.

Earlier, wireless sensor networks based mobile sink were proposed by authors like Wang et al (2005), Rao et al (2008) etc. Anastasi et al (2010) employ the mobile sink based network for collecting environmental pollution data such as pollutants concentration and weather conditions data. A detailed description on the mobile sink data collection strategy is provided in chapter 3.

Abbildung in dieser Leseprobe nicht enthalten

Figure 2.8 Architecture of Mobile Sink based Data Gathering in WSN

2.3.4.4 Mobile relay based wireless sensor network

Mobile relays are the support nodes which gather messages from sensor nodes store them and carry the collected data to sinks or base stations. They act as mobile forwarders and are not the actual endpoints of communication. They just carry the collected data along with them and transmit it to base station whenever it gets into contact with the base station.

[...]