A Survey on Clustered-Aggregation Routing Techniques in Wireless Sensor Networks

A Survey on Clustered-Aggregation Routing Techniques in Wireless Sensor Networks

Sushma K M, Manjula Devi T H [PG Student], [Associate Professor] Telecommunication Department

Dayananda Sagar College of Engineering (Affiliated to VTU, Belgaum) Bangalore, India

Abstract Wireless sensor network is inter connection of many sensor nodes. Each sensor nodes has some amount of processing capacity which can be used for efficient data routing in wireless sensor network. Sensor nodes are energy limited devices. Hence, several methodologies have been proposed in order to reduce consumption of energy along with the efficient data routing. One such approach is data aggregation while routing.

Better data aggregation is possible by clustering the sensor nodes and having one node within it as an aggregation point. This paper gives survey of some of the cluster aggregation routing techniques. Each algorithm is discussed separately and advantages of each algorithm are listed. The paper concludes with possible improvements that can be worked out in some algorithms.

Keywordssensor networks, clustering,data aggregation

1. INTRODUCTION

   Well distributed thousands of sensor nodes forming a network are used for many applications like environmental monitoring, cattle monitoring and even in life saving situations. With greater applications wireless sensor network is a hot research field.

   In WSN, sensors produce large amount of information which has to be routed to a sink node. More the communication, more energy is used. Hence, routing protocols must aim at limited utilization of energy.

   Data aggregation reduces energy consumption by reducing communication load and also it increases data accuracy by eliminating redundant data. In clustered aggregation approach, groups of nodes (clusters) are formed. One node acts as a processing center where data aggregation occurs, reducing redundant information so as to effectively reduce the load on the network and increase network life time. In this kind of aggregation algorithm one of the nodes in the cluster is chosen to be the head node and other node function to collect the data and send it to the head node.

   Clustering forms a routing structure to route the data. Along with data aggregation it has efficient energy savings. Other advantages of clustered aggregation being, better node management i.e. reusing resources and bandwidth much similar to the cellular networks.

   The various clustered aggregation algorithm discussed in this paper are LEACH, InFRA, DRINA.

2. LEACH ALGORITHM

   This is the most popular clustered aggregation routing technique. Cluster formation here is random, adaptive and self-clustering.

   The algorithm defines two rounds. First is a set-up phase which includes cluster formation, cluster head selection. Second, is a steady state phase where data transmission takes occurs.

   1. Setup Phase

      Cluster head election: All nodes at first claim to be the head of the cluster. They generate a random number. If random number of a node is less than threshold, it sends information that it is the head of the cluster. In next round, again process repeats with the threshold being increased to the nodes that not been heads till now and for the node already been a cluster head its threshold will be made zero. The probability of being selected as a cluster head is a function of nodes energy level relative to the overall remaining network energy.

      Cluster formation: Once cluster head is elected, it will send information that it is the cluster head. The remaining nodes will join the cluster now by sending a join request message. Once the head node gets the request from all the nodes, it allocates TDMA slots to the cluster members. Next algorithm enters steady state operation.

   2. Steady Phase

      This is where much of the data transmission takes place. All cluster members send data to the cluster heads in their time slot. At other time they may go to a sleep mode, and this is how more energy saving is possible with LEACH mechanism. After receiving data from all the members, cluster head performs data aggregation and forwards to the base station (or a sink).

      After some period of time the nodes enter a new round where the process repeats by electing a new cluster head.

   3. Advantages of LEACH algorithm

      The overall procedure of the algorithm is simple and there is no need for any complex functions and storage of large amount of data.

      Since cluster heads are randomly elected every round, therefore each node gets an equal chance of becoming a cluster head. Energy load balance of network is present. And when compared to static clustering algorithms the network life time is more.

   4. Disadvantages of LEACH algorithm

   Though, a few to mention there are some important points to note.

   Nodes must only send data in their particular time slot, perfect synchronization is needed which is not always possible.

   The size of the network is to be limited since the algorithm assumes every node can communicate with base station or the cluster head directly. Thus this algorithm is not well suitable for large network.

3. INFRA ALGORITHM

   In Information Fusion based Role Assignment algorithm nodes are assigned different roles when an event is detected. All the nodes which have same event detected will form a cluster and roles are assigned for nodes i.e. one node becomes the cluster head and others are cluster members. The cluster members forward the data to cluster heads. Until an event is detected all sensor nodes except the sink perform the relay role.

   When event is detected, cluster formation starts by allocating cluster heads and cluster member roles to the nodes. Other nodes form relay and thus the routing structure is formed connecting the clusters to the sink.

   1. Cluster formation

      Based on various parameters like smallest node ID, greatest residual energy etc., cluster heads are identified. Using smallest ID as the criteria leads to less communication cost during cluster head election. So, when nodes announce event detection, nodes check their neighborhood and the node with smallest node ID is made as cluster head. Cluster heads floods its state over the network and all the other ones become cluster members.

   2. Route formation

      Cluster heads choose the routes which are nearer to the sink or it should be at minimum distance to other coordinators. Every node calculates aggregated coordinators distance which is sum of distance measured in hops between that particular node and all coordinator nodes.

      The nodes that are neither cluster heads nor cluster members are made as relay nodes. Next node is chosen that is closer to the sink or current cluster head based on aggregated coordinators distance. Then, the aggregated data what it has got is forwarded to the next hop. Each time when the data is to be sent a shortest path is looked for. Therefore, chances of data aggregation are increased.

   3. Data aggregation

      Here in this technique information fusion occurs at two places

      1. within cluster

      2. outside the cluster

      Within cluster all cluster members and its cluster head form a treelike structure. All cluster members forward their data to the cluster head and cluster head is the aggregation point. While finding a shortest path to sink or a nearby cluster head next hop for two or more relays may be same. And that next hop relay node acts as aggregation point leading to inter cluster aggregation.

   4. Advantages f InFRA Algorithm

      Greater amount of aggregation is possible. The algorithm provides intra cluster as well as inter cluster aggregation points. Hence number of aggregation points increase with routing path overlap.

      The increase in aggregation leads to better energy saving.

   5. Disadvantages of InFRA Algorithm

      Drawback of this algorithm is that, when an event occurs, information about that has to be sent to whole network in order to update the aggregate coordinators distance. This increases communication overhead and limits the scalability.

4. DRINA ALGORITHM

   Data Routing In-Network aggregation is a reliable routing approach for wireless sensor networks. It uses a fault- tolerant routing mechanism to have more data aggregation in a reliable way. In In-network data aggregation there is synchronization of data transmission among the nodes. A node forwards the data only after waiting for a while for data from its neighbor. Thus data aggregation opportunities are more. The algorithm has got following roles in the route infrastructure creation

   • Collaborator: when an event is detected, sends the data to the head.

   • Coordinator: This is the cluster head responsible for collecting data, aggregating and forwarding the same.

   • Sink: final node to which the data is to be sent.

   • Relay: Intermediate nodes that forward the data.

   There are three main levels in the algorithm

   1. Building the Hop Tree

      This is the pre phase of cluster formation. The distance from sink to each node is computed in terms of hops. All network nodes receive a hop configuration message (HCM) from sink node. There are two fields in HCM: an ID, identifier of the node and a HopToTree value is distance in hops by which an HCM message has passed.

      • At first, all nodes start the HopToTree value as infinity.

      • Sink starts sending Hop Configuration Message to neighbors.

      • When a node receives the HCM it checks for HopToTree value.

        If HopToTree value is less than value of HopToTree that the node has stored and if its the first time it received that particular HCM then the node will forward the message to its neighbor by changing the ID with its ID and incrementing the

        HopToTree value.

        If the above condition is false and the node has already received that HCM by some other node at a shorter distance then, node will discard the HCM.

        The distance of all nodes from sink is thus calculated.

   2. Cluster formation

      Once events are detected, all nodes run leader election algorithm and compute for leadership. The leader will be chosen based on

      • The one which is closer to the sink (if its the first event).

      • The one which is closest to an existing route.

        At the time of tie, the node with smallest energy will be the head. At last, one node will be the coordinator and all other nodes with same event detected will be collaborators.

   3. Route formation and Data Transmission

      A next hop is always selected to have a shortest path to sink or to a nearest already existing path. The resulting path is a tree that connects the coordinators to sink.

      The number of aggregation increases and hence there are three types of aggregation possible.

      • Cluster inside aggregation: when the routes overlap inside cluster the aggregation is performed by collaborator.

      • Leader inside aggregation: the cluster leader (coordinator) collects the data from its cluster members (collaborators).

      • Cluster outside aggregation: When paths overlap outside the cluster, the relay nodes perform aggregation.

        When a node has some data to transmit, it looks for descendants. If it has more than one child it waits till it gets data from all of them. After that it aggregates the data collected and forwards to the next hop. For every packet a node has to transmit, before sending it will run a route repair mechanism to check for next hop node working. If it is assured that the next hop node is working then only it will forward the data.

   4. Route repair mechanism

      A unique route is created when routing the aggregated data. Some nodes in the route may be damaged. The main reason being battery drain off or some physical distruction.in that case there must be a mechanism to take an alternate path. DRINA uses a piggy-backed acknowledgement based route repair mechanism, failure detection is done first and a

      new route is selected.

      Node first sends packet, sets a time out and waits for retransmission by next hop. This is considered as an acknowledgement. Once it receives, it will consider the next node to be active and data is forwarded. Each node follows the procedure before sending the data to the next node.

      If the sender doesnt receive an acknowledgement within a stipulated time period, it will consider the next node to be inactive. In case the next hop node is inactive, a new next hop is chosen. The new node chosen will be the neighbor with next lowest HopToTree value.

   5. Advantages of DRINA Algorithm

      More aggregation is possible as the aggregation opportunities are more and hence saving of energy is obtained.

      Fault-Tolerant mechanism improves the data delivery rate of the algorithm. This also provides greater reliability for data transmission.

      The algorithm has some of the key aspects like reduced number of messages for setting of the network, maximum number of overlapping nodes, more aggregation etc. that has to be present in an aggregation aware routing protocol for wireless sensor networks.

   6. Disadvantages of DRINA algorithm

   As there is more number of aggregation points, waiting time of the aggregator to collect the data from other nodes becomes important. Some strategies must be designed to control the waiting time of the aggregators. Another drawback is routes formed are static.

   Table I. Basic Characteristics Of Algorithms

   TECHNIQUE	LEACH	INFRA	DRINA
   ROUTE STRUCTURE	TREE BASED CLUSTER	TREE BASED CLUSTER	TREE BASED CLUSTER
   OBJECTIVES	SHORTEST PATH	MAXIMUM OVERLAP ROUTES	MAXIMUM OVERLAP ROUTES
   AGGREGATION POINTS	CLUSTER HEAD	CLUSTER HEAD AND INTERMEDIATE NODES	CLUSTER HEADS AND INTERMEDIATE NODES
   OVERHEAD	HIGH	VERY HIGH	MEDIUM
   SCALABILITY	GOOD	LOW	MEDIUM
   DRAWBACK	HIGH POWER CONSUMPTOIN	LOW SCALABILITY AND HIGH COST	STATIC ROUTES

5. CONCLUSION

This paper provides comprehensive survey of routing techniques used in wireless sensor networks. All the three algorithms considered for discussion are cluster based aggregation algorithms. Each of the algorithms is discussed briefly in a way for easy understanding and the advantages and disadvantage of the algorithms are mentioned. All the three algorithms aim to improve the aggregation possibilities and they have their own disadvantages. InFRA is best for small size networks and with events taking for long duration. DRINA has greater scalability and overhead, but there is need to achieve a good balance between overhead and routing tree quality. And also as mentioned earlier a method to control the waiting time of aggregator is required. Both InFRA and DRINA have static route formation. These are also the possible future work to carry on.

REFERENCES

1. Leandro Aparecido Villas, Azzedine Boukerche, Heitor Soares Ramos,Horacio A.B. Fernandes de Oliveira,Regina Borges de Aaujo , Antonio Alfredo Ferreira Loureiro DRINA:A Lightweight and Reliable Routing Approach for In-Network Aggregaion in Wireless Sensor Networks IEEE Transactions on computers vol. 62,NO. 4, pp- 676-689, April 2013.

2. Walid Bechkit, Mouloud Koudil, Yacine Challal,Abdelmajid Bouabadllah, Brahim Souici, Karima Benatchba,A new Weighted Shortest Path Tree for Convergecast Traffic Routing in WSN IEEE,pp-187-192, 2012.

3. G.H Raghunandan, B.N. Lakshmi A comparative analysis of routing techniques for Wireless Sensor Networks, Proceedings of the IEEE, pp- 17-22, February 2011.

4. Qing Bian, Yan Zhang,Yanjuan Zhao, Research on Clustering Routing Algorithms in Wireless Sensor Networks, IEEE Computer Society, pp- 1110-1113, 2010

5. Eduardo F. Nakamura, Heitor S. Ramos.Leandro A. Villas, Andre L.L. de Aquino and Antonio A.F. Loureiro, A reactive role assignment for data routing in event-based wireless sensor networks, Elseveir, pp- 1980-1996, 2009.

6. G. Anastasi, Marco Conti, Mario Di Francesco, Andrea Passarella, Energy Conservation in Wireless Sensor Networks: a Survey, Ad- hoc Networks,Vol. 7, No. 3, pp- 537-568, May 2009.