Routing Protocols for Wireless Sensor Networks

Power Aware Routing protocols In Wireless Sensor Networks BY DARPAN DEKIVADIYA 09BCE008 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING AHMEDABAD-382481 April 2012

Power Aware Routing protocols In Wireless Sensor Networks Seminar Submitted in partial fulﬁllment of the requirements For the degree of Bachelor of Technology In Computer Engineering By DARPAN DEKIVADIYA 09BCE008 DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING AHMEDABAD-382481 April 2012

Certiﬁcate This is to certify that the Seminar entitled ”Power Aware Routing protocols in Wireless Sensor Networks” submitted by DARPAN DEKIVADIYA(09BCE008), towards the partial fulﬁllment of the requirements for the degree of Bachelor of Technology in Computer Engi- neering of Nirma University of Science and Technology, Ahmedabad is the record of work carried out by him under my supervision and guidance. In my opinion, the submitted work has reached a level required for being accepted for examination. The results embodied in this Seminar, to the best of my knowledge, haven’t been submitted to any other university or institution for award of any degree or diploma. Prof. Jitali Patel Prof. D. J. Patel Assistant Professor, Professor and Head, Dept. of Computer Science & Engg., Dept. of Computer Science & Engg., Institute of Technology, Institute of Technology, Nirma University, Ahmedabad Nirma University, Ahmedabad Prof. Ankit Thakkar Guide and Assistant Professor, Institute of Technology, Nirma University, Ahmedabad iii

Abstract iv Recent developments in the area of micro-sensor devices have accelerated advances in the sensor networks field leading to many new protocols specifically designed for wireless sensor networks (WSNs). Wireless sensor networks with hundreds to thousands of sensor nodes can gather information from an unattended location and transmit the gathered data to a particular user, depending on the application. These sensor nodes have some constraints due to their limited energy, storage capacity and computing power. Data are routed from one node to other using different routing protocols. There are a number of routing protocols for wireless sensor networks. This report gives the brieg idea about Routing Protocols in Wireless Sensor Networks which includes Data Dissemination and Data Gathering Protocols.It also includes classification and comaparision of these Routing Protocols. iv

Acknowledgements v I would like to express my heartfelt gratitude to Prof.Ankit Thakkar, Professor in De- partment of computer science and engineering for her valuable time and guidance that made the seminar project work a success. Thanking all my friends and all those who had helped me in carrying out this work. I am also indebted to the library resources centre and interest services that enabled us to ponder over the vast subject of ”Power Aware Routing protocols in Wireless Sensor Networks”. - DARPAN DEKIVADIYA 09BCE008 v

Contents Abstract iv Acknowledgements v 1 Introduction to WSN 1 2 Classification Of Routing Protocols 3 2.1 Based on Mode of Functioning and Type of Target Applications . . . . . . . 3 2.1.1 Proactive :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Reactive :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.3 Hybrid :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 According to the Participation style of the Nodes. . . . . . . . . . . . . . . . 4 2.2.1 Direct Communication :- . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.2 Flat :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2.3 Clustering Protocols :- . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Depending on the Network Structure . . . . . . . . . . . . . . . . . . . . . . 5 2.3.1 Data Centric :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3.2 Hierarchical :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3.3 Location Based :- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Data Dissemination Protocols 6 3.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Gossiping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.3 Rumor Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Sequential Assignment Routing :- . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Direct Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6 Sensor Protocol for Information via Negotiation . . . . . . . . . . . . . . . . 11 3.7 Geographic Hash Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Data Gathering Protocols 13 4.1 Direct Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Power Efficient Gathering for Sensor Information Systems . . . . . . . . . . 14 4.3 Binary Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Chain Based Three level Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 16 vi

Chapter 1 Introduction to WSN A wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants and to cooperatively pass their data through the network to a main location. The more modern networks are bi-directional, also enabling control of sensor activity. The development of wireless sensor networks was motivated by military applications such as battleﬁeld surveillance; today such networks are used in many industrial and consumer applications, such as industrial process monitoring and control, machine health monitoring, and so on. Figure 1.1: Typical multi-hop wireless sensor network architecture 1

The WSN is built of ”nodes” from a few to several hundreds or even thousands, where each node is connected to one (or sometimes several) sensors. Each such sensor network node has typically several parts: a radio transceiver with an internal antenna or connection to an external antenna, a microcontroller, an electronic circuit for interfacing with the sensors and an energy source, usually a battery or an embedded form of energy harvesting. A sensor node might vary in size from that of a shoebox down to the size of a grain of dust, although functioning ”motes” of genuine microscopic dimensions have yet to be created. The cost of sensor nodes is similarly variable, ranging from a few to hundreds of dollars, depending on the complexity of the individual sensor nodes. Size and cost constraints on sensor nodes result in corresponding constraints on resources such as energy, memory, computational speed and communications bandwidth. The topology of the WSNs can vary from a simple star network to an advanced multi-hop wireless mesh network. The propagation technique between the hops of the network can be routing or ﬂooding 2

Chapter 2 Classification Of Routing Protocols Routing techniques are required for sending data between sensor nodes and the base stations for communication. Different routing protocols are proposed for wireless sensor network. These protocols can be classified according to different parameters. ˆ Routing Protocols can be classified as Proactive, Reactive and Hybrid, based on their Mode of Functioning and Type of Target Applications. ˆ Routing protocols can be classified as Direct Communication, Flat and Clustering Protocols, according to the Participation style of the Nodes. ˆ Routing Protocols can be classified as Hierarchical, Data Centric and location based, depending on the Network Structure. 2.1 Based on Mode of Functioning and Type of Target Applications 2.1.1 Proactive :- In a Proactive Protocol the nodes switch on their sensors and transmitters, sense the environment and transmit the data to a BS through the predefined route. e.g. The Low Energy Adaptive Clustering hierarchy protocol (LEACH) utilizes this type of protocol. 2.1.2 Reactive :- if there are sudden changes in the sensed attribute beyond some pre-determined threshold value, the nodes immediately react. This type of protocol is used in time critical applications. e.g. The Threshold sensitive Energy Efficient sensor Network (TEEN) is an example of a reactive protocol. 3

2.1.3 Hybrid :- Hybrid protocols incorporate both proactive and reactive concepts. They first compute all routes and then improve the routes at the time of routing. e.g. Adaptive Periodic TEEN (APTEEN) is an example of a reactive protocol. 2.2 According to the Participation style of the Nodes. 2.2.1 Direct Communication :- In this type of protocols, any node can send information to the Base Station(BS) directly. When this is applied in a very large network, the energy of sensor nodes may be drained quickly. Its scalability is very small. e.g. SPIN is an example of this type of protocol. 2.2.2 Flat :- In the case of flat protocols,if any node needs to transmit data, it first searches for a valid route to the BS and then transmits the data. Nodes around the base station may drain their energy quickly. Its scalability is average. e.g. Rumor Routing is an example of this type of protocol. 2.2.3 Clustering Protocols :- According to the clustering protocol,the total area is divided into numbers of clusters. Each and every cluster has a cluster head (CH) and this cluster head directly communicates with the BS. All nodes in a cluster send their data to their corresponding CH. e.g. TEEN is an example of this type of protocol. 4

2.3 Depending on the Network Structure 2.3.1 Data Centric :- Data centric protocols are query based and they depend on the naming of the desired data, thus it eliminates much redundant transmissions. The BS sends queries to a certain area for information and waits for reply from the nodes of that particular region. Since data is requested through queries, attribute based naming is required to specify the properties of the data. Depending on the query, sensors collect a particular data from the area of interest and this particular information is only required to transmit to the BS and thus reducing the number of transmissions. e.g. SPIN was the first data centric protocol. 2.3.2 Hierarchical :- Hierarchical routing is used to perform energy efficient routing, i.e., higher energy nodes can be used to process and send the information; low energy nodes are used to perform the sensing in the area of interest. examples: LEACH, TEEN, APTEEN. 2.3.3 Location Based :- Location based routing protocols need some location information of the sensor nodes. Location information can be obtained from GPS (Global Positioning System) signals, re- ceived radio signal strength, etc. Using location information, an optimal path can be formed without using flooding techniques. e.g. Geographic and Energy-Aware Routing(GEAR) 5

Chapter 3 Data Dissemination Protocols Data dissemination is the process by which queries or data are routed in the sensor network. The data collected by sensor nodes has to be communicated to the BS or to any other node interested in the data. The node that generates data is called a source and the information to be reported is called an event. Anode which is interested in an event and seeks information about it is called a sink. Traffic Models have been developed for sensor networks such as the data collection and data dissemination (diffusion) models. In the data collection model, the source sends the data it collects to a collection entity such as the BS. This could be periodic or on demand. The data is processed in the central collection entity. Data diffusion, on the other hand, consists of a two-step process of interest propagation and data propagation. an interested is a descriptor for a particular, intrusion or presence of bio- agents. For every event that a sink is interested in , it broadcasts its interest to its neighbors and periodically refreshes its interest. The interest is propagated across the network and every node maintains an interest cache of all events to be reported. 3.1 Flooding In Flooding, Each node Which receives a packet broadcasts it, if the maximum hop count of the packet is not reached and node itself is not the destination of the packet.This technique does not require complex topology maintenance or route discovery algorithms. Flooding has Following disadvantages : ˆ Implosion : This is situation when duplicate messages are sent to the same node. This occurs when a node recieves coppies of the same message from many of its neigh- bours. ˆ Overlap : The same event may be sensed by more than one node due to overlapping of regions of coverage. this results in their neighbors receiving duplicate reports of the same event. ˆ Resource Blindness : The flooding protocol does not consider theavailable energy at the nodes and results in many redundant transmissions. so,it reduces the network lifetime. 6

3.2 Gossiping Gossiping is modified version of flooding, where the nodes do not broadcast apacket, but send packets to a randomly selected neighbor. This avoids the problem of Implosion. It takes a long time for a message to propogate throughout the network. Though gossiping has considerably lower overhead than flooding, it does not guarantee that all nodes of the network will recieve the message. It relies on the random neighbor selection to eventually propogate the message throughout the network. 7

3.3 Rumor Routing Rumor Routing is an agent based path creation algorithm. Agents are long-lived entities created at random by nodes. These are basically packets which are circulated in the network to establish shortest path to events that they encounter.They can also perform path optimizations at nodes they visit. When agent finds a node whose path to an event is longer than its own, it updates the nodes routing table. Figure 3.1: Rumor Routing Figure 3.1 illustrates the working of Rumor Routing algorithm. In figure 3.1(a), the agent has initially recorded a path distance 2 to event E1. Node A’s table shows that it is at a distance 3 from event E1 and distance 2 from E2. when the agent visits node A, i+t updates its own path state information to include the path to event E2. The updating is with one hop greater distance than what it found in A, to account for the hop between any neighbor of A that the agent will visit next, andA. It also optimizes the path to e1 recorded at node A to the shorter path through node B. The updated status of the agent and node table is shown in figure 3.1(b). When a query is generated at a sink, it is sent on a ranom walk with the hope that it will find a path leading to the required event. This is based on high probability of two straight lines intersecting on a planar graph, assuming the network topology is like a planar graph, and the paths established can be approximated by straight lines owing to high density of the nodes. If a query does not find an event path, the sink times out and usesflooding as last resort to propagate the query. For instance, as in figure 3.1(c), suppose a query for event E1 is generated by node P. Through a random walk, it reaches A, where it finds the previously established path to E1. Hence, the query is directed to E1 through node B, as indicated by A’s table. 8

3.4 Sequential Assignment Routing :- The Sequential Assignment Routing(SAR) creates multiple trees ,where the root of each tree is a one hop neighbor of sink.Each tree grows outward from the sink and avoids nodes with low throughput or high delay. At the end of the procedure, most nodes belong to multiple trees. An instance of tree formation is illustrated in ﬁgure. Figure 3.2: Sequential Assignment Routing The tree rooted at A and B. Two of the one hop neighbors of the sink are shown. Node C belongs to bothtrees and has path length of 3 and 5 respectively to the sink, using the two trees.Each sensor node records two parameters about each path through it: 1. The available energy resources on the path. 2. An additive QoS metric such as delay. 9

This allows a node to choose one path from among many to relay its message to the sink.The SAR chooses a path with the high estimated energy resources and provisions can be made to accomodate packets of different properties.A wieghted QoS metric is used to handle prioritized packets which computed as a product of priority leveland delay.The routing esures that the same weighted QoS metric is maintained. Thus, higher priority packets take lower delay paths and lower priority packets have to use the paths of greater delay. e.g. If node C generates a packet of priority 3, it follows the longer path along tree B, and a packet of priority 5 will follow the shorter path alongtree A. so that the priority X delay QoS metric is maintained. SAR minimizes the average weighted QoS metric over the lifetime of the network. The sink periodically trigers a metric update to reflectthe changes in available energy resources after some transmissions. 3.5 Direct Diffusion This potocol is useful in scenario where the sensor nodes themselves generate requests/queries for data sensed by other nodes, instead of all queries arising only from a BS. Hence the sink for the query could be a BS or a sensor node. The direct diffusion routing protocol improves on data diffusion using interest gradients. Each sensor node names its data with one or more attributes and other nodes express their interest depending on these attributes. Attribute value pairs can be used to describe an interest in intrusion data as follows. The sink has to periodically refresh its interest if it still requires the data to be reported it. Data is propagated along the reverse path of the interest propagation. Each path is associated with a gradient that is formed at the time of interest propagation. Each path is associated with the gradient that is formed at the time of interest propagation. While the positive gradients encourage the data flow along the path, Negative gradients inhibit the distribution of data along a perticular path. The strength of the interest is different toward different neighbors, resulting into source to sink paths with different gradients. The gradient coresponding to an interest is derived from the interval/data-rate field specified in the interest. This model uses data naming by attributes and local data transformation to reflect the data centric nature of sensor network operations. The local operations of Data agreegation are application-specific gradient model. The network wide results of local interaction by regulating the flow of data along different paths depending on the expressed interest. 10

3.6 Sensor Protocol for Information via Negotiation family of protocols for information via negotiation (SPIN) is proposed in [5]. SPIN uses negotiation and resources and adaption to address the deficiencies of flooding. Negotiation reduces overlap and implosion, and a threshold based resource-aware operation is used to prolong network lifetime. Meta-data, or data describing data, is transmitted instead of row data. This requires fewer bytes and can be in an application-specific format. SPIN has three types of messages: ADV,REQ, and DATA. A sensor node broadcasts an ADV containing meta-data describing actual data. If a neighbor is interested in the data , it sends REQ for the data. Then the sensor node sends the actual DATA to the neighbor. The neighbor again sends ADVs to its neighbors and this process continues to disseminate the data throughout the network. the simple version is shown in figure. Figure 3.3: Sensor Protocol for Information via Negotiation SPIN is based on data-centric routing, where the nodes advertise the available data through an ADV and wait for requests from interested nodes. SPIN-2 expands on SPIN, using an energy or resource threshold to reduce participation. A node may participate in the ADV-REQ-DATA handshake only if it has sufficient resources above a threshold. 11

3.7 Geographic Hash Table Geographic Hash Table is a system based on data centric storage inspired by internet scale distributed hash table systems such as chard and Tapestry, GHT hashes keys into geographic co-ordinates and stores a pair at the sensor node nearest to the hash value. The calculated hash value is mapped onto a unique node consistently, so that queries for the data can be routed to the correct node. Stored data is replicated to ensure redundancy in case of node failures and consistently protocol is used to maintain the replicated data. The data is distributed among nodes such that it is scalable and the storage load is balanced. GHT is more eﬀective in large network where a large number of events are detected but not all are queried. In this case data observed is stored in a distributed manner across all nodes, instead of being routed to central external storage. Queries are routed to the nearest node which contains a copy of the relevant data. This makes the storage and traﬃc distribution uniform. 12

Chapter 4 Data Gathering Protocols The objective of the data-gathering problem is to transmit the sensed data from each sensor node to a BS. One round is defined as the BS collecting data from all the sensor nodes once. The goal of algorithms which implement data gathering is to maximize the number of rounds of communication before the nodes die and the network becomes inoperable. This means minimum energy should be consumed and the transmission should occur with minimum delays, which are conflicting requirements. Hence, the energy X delay metric is used to compare algorithms, since this metric measures speedy and energy-efficient data gathering. A few algorithms that implement data gathering are discussed below. 4.1 Direct Transmission All sensor nodes transmit their data directly to BS. This is extremely expensive in terms of energy consumed, since the BS may be very far away from some nodes. Also, nodes must take turns while transmitting to the BS to avoid collision , so the media access delay is also large. Hence, this scheme performs poorly with respect to the energy X delay matrix. 13

4.2 Power Eﬃcient Gathering for Sensor Information Systems Power Eﬃcient Gathering for Sensor Information Systems (PEGASIS) is a data-gathering protocol based on the assumption that all sensor nodes know the location of every other node, that is, the topology information is available to all nodes. Also,any node has the required transmission range to reach the BS in one-hop, when it is select as a leader. The goals of PEGASIS are as follows : ˆ Minimize the distance over which each node transmits. ˆ Minimize the broadcasting overhead. ˆ Minimize the number of messages that need to be sent to the BS. ˆ Distribute the energy consumption equally across all nodes. 14

Figure 4.1: Sequential Assignment Routing A greedy algorithm is used to construct a chain of sensor nodes, starting from the node farthest from the BS. At each step, the nearest neighbor which has not been visited is added to the chain. The chain is constructed a priory, before data transmission begins and is reconstructed when nodes die out. At every node, data fussion is carried out. so, that only one message is passed on from one node to next. A node which is designated as the leader finally transmits one message to BS. Leadership is transffered in sequential order and a token is passed. so that the nodes know in which direction to pass messages in order to reach the leader. A possible chain formation is illustrated in figure. The delay involved in message reaching the BS is O(N), where N is the total number of nodes in the network. 15

4.3 Binary Scheme This is also a chain-based scheme like PEGASIS, which classifies nodes into different levels. All nodes which recieve messages at one level rises to the next level. Step 1 :- S0 → S1 S2 → S3 S4 → S5 S6 → S7 Step 2 :- S1 → S3 S5 → S7 Step 3 :- S3 → S7 Step 4 :- S7 → BS The number of nodes is halved from one level to the next. For instance,consider a network with eight nodes labled from S0 to S7. In figure agreegated data reaches the BS in 4 steps which is O(log2 N ).where N is the number of nodes in the network. 4.4 Chain Based Three level Scheme For non CDMA sensor nodes, a binary scheme is not applicable. The chain based three level scheme addresses this situation. In this scheme chain is constructed as in PEGASIS. The chain is devided into into number of groups to space out simulteneous transmission in order to minimize interference. Within a group , nodes transmit one at a time. One node out of each group agreegates data from all group members and rises to the next level. The index of this leader node is decided priori. In the second level all nodes are devided into two groups and the third level consist of a message exchange between one node from each group of second level. Finally the leader transmits a single message to BS. Step 1 :- S0 → S1....S6 → S7 ← S8 ← S9 S10 → S11....S16 → S17 ← S18..........S97 ← S98 ← S99 Step 2 :- S7 → S17 ← S27 ← S37 ← S47 S57 → S67 ← S77 ← S87 ← S97 Step 3 :- S17 ← S67 Step 4 :- S67 → BS The working of this scheme is explain in above figure.Suppose Network has 100 nodes and the group size is 10 for the first level and 5 for second level. Three levels have been found to give the optimal energy X delay through simulation. 16

References :- ˆ Ad Hoc Wireless Networks By,C.Shiva Ram Murthy and B.S.Manoj ˆ www.mdpi.com/jouranal/sensor ˆ www.wikipedia.org/wiki/Wireless sensor network 17

Routing Protocols for Wireless Sensor Networks

In this document

More Related Content

What's hot

Similar to Routing Protocols for Wireless Sensor Networks

Recently uploaded

Routing Protocols for Wireless Sensor Networks