Routing Protocol of Wireless Sensor Network
Chapter 1
Introduction
A wireless sensor network (WSN) consists of spatially distributed autonomous devices called sensors, and one or more base stations to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants, at different locations. The research in sensor networks received a big boost with a number of funding initiatives by US military, NSF and DARPA SENSIT [17]. Many novel sensor based applications have emerged in recent past. We may classify the sensor applications into following classes [6]:
· Monitoring spaces: This class refers to passive data gathering recognizing occurrence of some events or conditions. The gathered data are typically inputs to a number of target applications. These target applications includes habitat monitoring, monitoring of crops (failure, pest attack), climate control, security surveillance, intelligent alarms (fire, flash flood, volcanic eruption), etc.
· Monitoring things: This class refers to gathering data to recognize occurrence of specific states of a system. On occurrence of these states the system may execute a sequence of internal transitions to get into a desirable state. The target applications could be structural monitoring (bridge health monitoring), equipment maintenance, medical diagnostics, etc.
· Monitoring complex interactions: It involves monitoring of complex interactions of systems and things. For example, wild-life habitat monitoring, disaster management, emergency response, smart environments, surface and sea navigation, health care, manufacturing process flow, etc., would require complex interactions of systems with objects or things.
Such wide-ranging applications requiring WSNs, make them candidates for intense research. The research spans hardwares, systems, networking, and programming methodologies. Considering ubiquity of applications, one of the crucial design decisions for sensor nodes has been to settle for a small form factor. The advantage of small form factor is that these miniature devices are inexpensive. Thousands of sensor nodes can be deployed with a small cost. Therefore, the key to success of sensor based applications is to network sensors in an efficient way for gathering sensory data from their respective deployed environments.
Every sensor has three basic units, namely, sensing, radio, and battery. The major constraint being limited energy (small battery unit). Consequently, a large number of sensor nodes can be networked to gather sensory data and each sensor performs two main responsibilities, namely, (i) sensing activities, and (ii) routing the sensed data to the base station or a controller. The base station is a master node which is generally fixed and assumed to have uninterrupted power supply or accessible for maintenance (such as replacement of battery). It acts as an interface of the WSN for complex interactions with other objects. The main responsibility of base station is to collect information from various sensor nodes and process it for further dissemination/actions.
Energy dissipation at sensor node is a major concern, as in many applications sensor have to be deployed in inaccessible environments. Sensing alone is not an energy consuming activity, but networking and programming certainly are. So, the major problem lies in activities like routing, addressing and support for different class of programming services. In this thesis our focus will be on routing problems.
The topology of a WSN determined by
- a set of external parameters such as node mobility, weather interference and noise, and
- Also by a set controllable parameters like transmission power, antenna type and direction, etc.
Normally the sensor nodes are uniformly spread over the whole of physical space to get the best coverage. The nodes are mostly static unless they are either mounted on moving vehicles, robots, or tagged to live animals.
Therefore, topology control is mainly possible through adjustment of transmission power, and associated radio adjustments. Thus, careful design of routing protocols that combine well with topology control mechanisms is extremely important for working of WSNs.
The design of routing protocols for WSN are influenced by many factors including hardware constraints, network topology, and power consumption. The sensor networks are mainly of two types – event-driven and time-driven (or continuous dissemination networks). In the event driven networks the sensor nodes sense the data and transmit it only if the data is considered critical enough to be communicated. In the time driven networks sensors sense the data and transmit it to the central controller periodically. The periodicity of relaying data packets is application dependent.
The two broad categorization of routing protocols are: (i) proactive, and (ii) reactive. In a proactive protocol, the routes are discovered and maintained using periodic messaging. Each node is expected to send periodic packets to the neighboring nodes. The packets contain the routing information of the sender node. The recipient nodes configure their routing tables based on received packets or make necessary updates as required. These periodic packets known as Hello packets indicate that the sender can still take part in routing process. As topology information is exchanged on the regular basis it causes unwanted overhead. On the one hand, a route to base station will always be available on request; but on the other hand the nodes unnecessarily update routing tables on periodic basis even for the routes which may not be required at all.
The reactive protocol discovers the route once and then maintains it reactively. Every time a path is unable to deliver a message, that path is rendered invalid and new path is discovered. Though the reactive protocols are quick to respond to the nodes moving in and out of the network, the latency for discovering a path could be long and may be inadmissible for certain applications. Both proactive and reactive protocols have their pros and cons. So, a protocol can best work mid way between the two.
The coverage area of a sensor node (or the reach ability of a node) depends on its transmission range. If the transmission range of all the nodes is high enough to reach the base station, then it is considered one hop network. Such networks do not incur overhead of additional control packets for route discovery and maintenance. However, as the wireless is a shared medium, one hop networks lead to densely connected networks and suffer from severe congestion. In other words, there is a trade off in selecting a suitable transmission range for the nodes and severity of congestion. The range should be chosen optimally to eliminate congestion and to retain desired network connectivity.
A network in which all the nodes have same transmission range, as in the example depicted by Fig 1.1(b) is called a Symmetric Network. In a symmetric network as indicated by Fig 1.1(b), if node A is in the transmission range of node B, then B must also be within transmission range A.
If the transmission ranges of nodes are configured at the network start-up time and all the nodes do not have same transmission range, then the network is considered to be an Asymmetric Network. Fig 1.1(a) provides an example where a pair of asymmetric links is shown to exist between nodes A and B. Node B is in range of A, but A is not in range of B
Figure1.1: a.) Asymmetric Link b.) Symmetric Link
1.1 Motivation
As stated earlier, the sensor nodes due to their small form factor have limited power. In order to prolong the life of the wireless sensor networks, the routing protocols apart from being robust and scalable, needs to be highly energy efficient. A lot of research [7, 8, 23, 30] has taken place in this direction and various routing protocols are proposed to achieve these objectives.
The work reported in this thesis aims at designing of a multihop energy efficient, reliable and fault-tolerant routing protocol. In a fully connected network, all nodes can directly access the base station. However, wireless being a broadcast medium, the congestion [13] in such a network is very high. Typically, each node in a multihop WSN would discover a path to the base station and route its data through this path. This causes the nodes near the base station to be used more frequently than the nodes away from the base station. The reason is the former set of nodes not only send their own sensed data, but are also responsible for forwarding the packets from the far off nodes in the network. This results in a bottleneck around the base station. If the nodes around the base station go dead, then the nodes away from base station will be unable to send the data unless they increase their transmission ranges.
Figure 1.2: Example Network
Fig 1.2 shows an example of a typical sensor network. The filled black node is the base station. The lines depict the connectivity and the filled gray nodes are the normal sensing nodes. In this example node-2 and node-3 are one hop nodes. Node-2 is responsible not only for sending its own data but also for forwarding the data from nodes-4, 5, 6, 9 and 10. Similarly, node-3 is responsible for sending its own data and as well as forwarding data of nodes-7, 8, 11 and 12. Thus the nodes situated at a distance of one hop from base station are used more often than the other nodes. It causes such nodes to dissipate energy at a substantially higher rate than the rest of the nodes in the network. Consequently, the network becomes dead very soon. The residual energy in the nodes near the base station may be sufficient to sense, but may not be sufficient communicate the sensed data to the base station. This observation led us to think how a routing protocol may avoid the formation of transmission bottleneck around the base station. The underlying idea is to ensure that the energy dissipation at each node is more or less same over the entire network. The approach we devised is to adjust transmission range of individual nodes to provide connectivity of base station without involving the nodes near the base station as and when desired. It led to dynamicity in the sensor network environment. We can view the dynamicity as insertion of new nodes and deletion of nodes (node failure) at random time.
Our second observation is that WSNs experience high packet losses. So, reliability is also important for WSN. Transmission reliability can be achieved through an acknowledgment based protocol. It helps in deciding the requirement of retransmissions if the packet loss occurs and thus increases the reliability.
An usual trend in protocol design suggests that the location parameters play crucial role for the routing purposes [12]. The determination of position parameters requires use of embedded GPS [4] receivers. But with embedded GPS receivers, will make the sensor nodes substantially expensive. Additionally, also the nodes will consume more power. Therefore, our aim is also to ensure come up with routing protocols which avoids use of location based information.
1.2 Problem statement and the Challenges Involved
The investigation in this thesis is oriented towards the design a multi hop routing protocol for time driven WSN which achieves following objectives.
· Avoid the formation of the congestion bottleneck around the base station
· Handle dynamic changes in topology caused by transmission power adjustments.
· Handle node failures on existing paths by a novel route repair procedure that leverages ability to adjust node transmission range.
· Ensure reliability through use of acknowledgements and limited retransmission of lost packets.
· Improve the network lifetime by considering residual node energy during route discovery.
· Analyze and compare the new protocol with the existing ones.
The objectives listed at items 1 and 5 are achieved by better utilization of the resources and treating the network as a dynamically changing asymmetric network. The topology change in the network is mainly determined by adjustment of transmission range from time to time. The resulting change topology modifies path from every node to base station. The routing protocol is, therefore, is a mix of both proactive and reactive protocol. The tasks of route discovery and route maintenance become more challenging in an asymmetric network, as Hello messages can not be used for such purposes in asymmetric links. The latency of route discovery also has to be minimized.
Balancing distribution of load for routing (forwarding packets) among the nodes shall ensure the uniform and better resource utilization. The concept of asymmetric network shall allow the nodes to use appropriate transmission ranges, which is more suitable for its longer lifetime depending on its position in the network.
Fault tolerance in routing protocols for WSN is a novel idea. It has been possible to tolerate node failure simply by eliminating failed nodes through a route maintenance step. It involves the adjustment of transmission power at some nodes for establishing connectivity with the base station when the routes are found to be broken due to node failures. We experimented with up to 5% node failures.
The objective concerning reliability in transmission is achieved by acknowledgments for the data packets. The protocol supports at most three retransmissions of the data packets to handle packet loss.
The routing metric is chosen by optimizing both latency of routes and residual energies at the nodes. The other desirable property of a protocol which is addressed is load sharing. The load for routing data packets is distributed over the multiple alternate paths available at a node. It ensures overall better utilization of energy resources and effectively extends lifetime of the network.
Finally, we performed simulation over OMNet++ [1] and compared our results with other notable time driven WSN routing protocols such as LEACH [12] and SPIN [11]. Our results show performance enhancement over symmetric routing protocols and over both SPIN and LEACH even without data aggregation.
1.3 Organization of Thesis
The rest of the thesis is organized as follows.
Chapter 2 discusses the related work and lays the background further discussion. The important existing protocols and the improvements subsequently proposed upon them are also discussed. It also indicates how these solutions differ from the new protocol proposed in this thesis.
In Chapter 3, the new protocol is described. We focus on robustness, network lifetime, routing latency to show how the proposed algorithm has potentials to outperform other existing protocols. The protocol is discussed in details by dwelling on its features, various phases of operation and implementation aspects.
Chapter 4 throws light on the actual logic of the proposal by presenting the algorithms. An analysis of performance parameters is also presented to provide an insight into its performance. The chapter also describes simulation software and the simulation environment. The details of the radio characteristics used for the purpose of empirical evaluation.
The results duly supported by the relevant plots for performance characteristics and related analysis are presented in Chapter 5.
Chapter 6 concludes the thesis with some directions for future work.
Chapter 2
Related Work
As explained in chapter 1, the design of routing protocols for WSN is a subject of intense research as both quality and quantity of information delivered to the end-users is very important for the applications centered on WSN. It has been observed that different protocols work better in different environments/applications. The issue of the effective utilization of energy resource has also been addressed in extensively in the literature. This chapter deals with related work and the underlying concepts which form the basis of energy aware routing protocols for WNSs.
Section 2.1 explains how simple routing ideas could lead to unnecessary wastage of precious energy resources. Section 2.2 deals with some initial thinking done by researchers on the ways to avoid broadcast storm which appear to be the main reason behind excessive energy wastage in routings ideas based on flooding and gossiping. Section 2.3 describes a number of routing protocols, namely, LEACH [12], PEGASIS [19] TEEN [20] and APTEEN [21] which try to eliminate redundant data broadcast and conserve the crucial energy resource by aggregation in some way or other. Later, section 2.4 which are relevant in context to this thesis. The subject of Discussion in section 2.5 is the quality and reliability of data delivered by the sensors.
2.1 Flooding and Gossiping
The conventional mechanism for relaying data from individual sensors to base station is Flooding or Gossiping [10]. The underlying idea of flooding is that each sensor on receiving a data packet broadcasts the same to its every neighbor. This packet is further re-broadcast until it arrives at the destination or the maximum number of hops for the packet is reached. Quite obviously, flooding raises unmanageable broadcast storms as depicted in Fig 2.1.
Figure 2.1: Broadcast storm
It may be appropriate for networks which experience quick topology changes. WSN mainly consists of static sensors nodes. So, topology remains more or less static for a considerable period of time. Of course, it is possible to control topology by adjusting transmission power of sensor motes. But such power adjustments can only be realized by program controls and hence, predictable. The other serious problems with broadcast storm are redundancies, contentions and collisions which result in wasteful consumption of node energies. Since sensor nodes have only limited energy reserves in the form of small batteries, they can ill-afford such associated problems arising out of broadcast storms. Therefore, flooding does not seem to be an appropriate approach of design of routing protocols in WSNs. The deficiencies of data reporting by flooding can be viewed under three categories [11], namely,
- Implosion: it refers to nodes disseminating data to all of their neighbors regardless of whether the data has already been received by these neighbors. It results in wastage of energy across several nodes, since the same piece of data arrives at every node via multiple paths.
- Overlap: it is not possible to have a precise deployment whereby sensor could cover disjoint spatial regions. So nodes often have overlapping spatial coverage. Data dissemination by flooding, therefore, results in data from overlapping regions to be routed by different alternative sensors and flooded over the network.
- Resource ignorance: flooding does not require the nodes to modify their activities on the basis of energy threshold. Consequently, a node may run out of energy too soon to perform any meaningful data sensing or reporting. For example, nodes near the base station could run out of their batteries being over used while forwarding data from distant nodes. This may result in network going dead too soon even when many distant nodes have sufficient energy to carry out their reporting and sensing activities.
Gossiping [9] is just a slightly enhanced version of flooding wherein the recipient node sends the data packet to a randomly selected neighbor. That neighbor in turn picks another random neighbor to forward the packet to and so on. Another usual variation of gossip protocol is that the recipient could rebroadcasts or discard the data with probabilities p and (1