An improved Cluster Based Multi-hop Routing in Self-Organizing Wireless Sensor Networks

An improved Cluster Based Multi-hop Routing in Self-Organizing Wireless Sensor Networks

J S Rauthan1, S Mishra2

1 Department Of Computer Science & Engineering, B T Kumaon Institute Of Technology, Dwarahat, Almora, India

2 Professor, Department Of Computer Science & Engineering, B T Kumaon Institute Of Technology, Dwarahat, Almora, India

Abstract: Wireless Sensor Networks (WSN), crossed by many subjects, is the advanced research hotspot field of recent international attention. Both academia and industries have shown great interests in Wireless Sensor Networks. The number of sensor nodes in WSN is numerous and a single node is extraordinarily limited in resources, so the important aim of designing routing protocol of WSN is to reduce the overall energy-dissipated in the networks and to maximize the lifetime of networks. We bring forward some improvements to the LEACH protocol based on analyzing the shortages of it. In this paper we have implemented an improved cluster based Multi- hop LEACH routing which does inter cluster and intra cluster multi-hoping used another cluster head as vice cluster head (the node that will become a CH of the cluster in case of CH dies). Hence, inter-cluster and intra-cluster routing are jointly used. Simulation of the improved Multi-hop LEACH is carried out on Omnet++. By analyzing and comparing the simulation results, it is shown that it can increase the lifetime of network effectively and reduce energy consumption in wireless sensor networks.

Keywords: wireless Sensor Networks, Leach Protocol, Self-Organization, clustering, Omnet++.

1. Introduction

   Sensor networks have emerged as a promising tool for monitoring the physical worlds, utilizing self-organizing networks of battery-powered wireless sensors that can sense, process and

   communicate. Wireless sensor networks [3] consist of small low power nodes with sensing, Computational and wireless communications capabilities that can be deployed randomly or deterministically in an area from which the users wish to collect data. Typically, wireless sensor networks contain hundreds or thousands of sensor nodes that are generally identical. These sensor nodes have the ability to communicate either among each other or directly to a base station (BS). The sensor network is highly distributed and the nodes are lightweight. Intuitively, a greater number of sensors will enable sensing over a larger area. As the manufacturing of small, low-cost sensors become increasingly technically and economically feasible, a large number of these sensors can be networked to operate cooperatively unattended for a variety of applications like military applications, disaster management, habitat monitoring, health applications, home applications etc [17]. The features of sensor networks [4] are as depicted below:

   • Varying network size The size of a sensor network can vary from one to thousands of nodes.

   • Low cost For the deployment of sensor nodes in large numbers, a sensor node should be inexpensive.

   • Long lifetime network An important characteristic of a sensor network is to design and implement efficient protocols so that the network can last as long as possible.

   • Self-organization Sensor nodes should be able to organize and form a network

     automatically without any external configuration.

   • Query and re-tasking The user should be able to query for special events in a specific area, or remove obsolete tasks from specific sensors and assign them with new tasks. This saves a lot of energy when the tasks change frequently.

   • Cooperation/Data aggregation Sensor nodes should be able to work together and aggregate their data in a meaningful way. This could improve the network efficiency.

   • Application awareness A sensor network is not a general purpose network. It only serves specific applications.

   • Data centric Data collected by sensor nodes in an area may overlap, which may consume significant energy. To prevent this, a route should be found in a way that allows in-network consolidation of redundant data. Recent advances in wireless sensor networks have led to many new protocols specifically designed for sensor networks. Most of the routing protocols since they might differ depend on the various applications and network architecture [5, 6]. To improve the lifetime of the sensor nodes, designing an efficient routing protocol is critical for the sensor nodes. Even though sensor networks are primarily designed for monitoring and reporting events, since they are application dependent, a single routing protocol cannot be efficient for sensor networks across all applications. Multihop routing technique is the first step towards minimizing energy consumption in sensor networks. Clustering and data aggregation are also important techniques in minimizing the energy consumption in sensor networks [14, 15, 16].

     In this paper we describe and implement an improved cluster based multihop LEACH routing protocol for wireless sensor networks. This improved cluster based multi-hop LEACH routing performs both inter cluster and intra cluster multihoping and used another cluster head as vice cluster head (the node that will become a CH of the cluster in case of CH dies). In this we purposed an improvement of the LEACH protocol that further enhances the power consumption and life time of the network, simulations result brings out an improved energy consumptions and lifetime of the network.

     The remaining of this paper is organized as follows. Section 2 contains classification of routing protocols, self-organization, section 3 contains description of routing protocol implemented, and Section 4 contains implementation and simulation, section 5 contains simulation matrices and results and, finally section 6 contains conclusion.

2. Classification Of Routing Protocols

   Broadly speaking, almost all of the routing protocols can be classified according to the network structure; as flat, hierarchical or location-based. Further, in wireless sensor networks protocols can also be classified according to operation mode; multipath based, query-based, negotiation-based, QoS-based, and coherent-based [7]. Figure 1 illustrates classification of WSN routing protocols.

   Figure1. Classification of WSN Routing Protocols

   1. Network Structure

      Based on the characteristics of a network, which includes characteristics of base stations and the characteristics of sensor nodes we classify routing protocols as flat based, hierarchical based and location based.

      • Flat based In these networks, all nodes play the same role and there is absolutely no

        hierarchy. Flat routing protocols distribute information as needed to any reachable sensor node within the sensor cloud [8]. There is no effort to organize the network and its traffic. The effort is made only to discover the best hop by hop route source to a destination by any path.

      • Hierarchical based This class of routing protocols sets out to attempt to conserve energy by arranging the nodes into clusters as shown in Figure 2. Nodes in a cluster transmit to a head node within close proximity which aggregates the collected information and forward this it to the base station [8, 9].

        Good clustering protocols play an important role in network scalability as well as energy efficient communication. On the negative side of it, clusters may lead to a bottleneck. This is because only one head communicate on behalf of the entire cluster. Energy depletion will e strongest in that head.

      • Location based Most of the routing protocols for sensor networks require location information for sensor nodes. In mostly cases location information is needed to calculate the distance between two particular nodes so that energy consumption can be estimated. Due to the lack of no addressing scheme for sensor networks like IP-addresses, location information

        can be utilized in routing data in an energy efficient way [8].

   2. Protocol Operation

      It describes the main operational characteristics of a routing protocol; in terms of communication pattern, hierarchy, delivery method, computation, negotiation etc [2].

      • Multipath based In this case, the network derives benefit from the fact that there may be multiple paths between a node and the destination. Using different paths ensures that energy is depleted uniformly and no single node bears the brunt [14, 15].

      • Query based Here the focus lies on propagation of queries throughout the network by the nodes which require some data. Any node which receives a query and also has the requested data, replies with the data to the requesting node. This approach conserves energy by minimizing redundant or non- requested data transmissions [9, 10].

      • Negotiation based In negotiation based protocols, the nodes exchange a number of messages between themselves before transmission of data [11, 12]. The benefit of this is that redundant data transmissions are suppressed. It should however be ensured that the negotiation transmissions are not allowed to exceed an extent that the energy saving benefit is offset by the negotiation overhead.

      • QoS-based QoS based protocols have to find a trade-off between energy consumption and the quality of service [13]. A high energy consumption path or approach may be adopted if it improves the QoS. So when interested in energy conservation, these types of protocols are usually not very useful and must be avoided.

      • Coherent-based Coherence based protocols focus on how much data processing takes place at each node [13]. In coherent protocols, data is sent to an aggregator node after minimum possible processing, and processing is then done at the aggregator. Coherent processing is usually adopted for energy efficient routing because they reduce the computation steps per node. However, the aggregator nodes must have more energy than the other ordinary nodes, or else they will be depleted rapidly.

   3. Self-Organization

      Self-organization is a set of mechanisms to produce a global and stable state of a system from interaction of different units without any interaction to the external environment [1].

      A self-organized system is based on:

      The local interaction: the emergent behavior of the system is more than simple interactions between its various elements without external control.

      The emergence of a global structure: the main objective of self-organization is to produce stable structures which are constructed in coherently bounded time.

      Adaptation to the environment and robustness: the emerging structure of a system must be adjusted to the environment and respond to local changes.

      Large scale: this property is the result of the absence of central control and internal interactions.

      2.3.1 Self-Organization In Wireless Sensor Network

      Above all these structures which have served to the self-organization of wireless sensor network, that we can find are as follows:

      Backbone: is a network that concentrates on the traffic from other networks in a hierarchical structure to ensure full communication. For that only the backbone nodes are allowed to relay a broadcast traffic. Any node must be near the backbone for sending it the information to be disseminated.

      Cluster: its providing the zoning of an extended network allows organizing it for addressing problems of routing and also providing the aggregation of flows. If a cluster head is elected in each zone, then a hierarchy is created. Then the cluster head is to manage the cluster in the network for communication to the base station and to the destination.

3. Conception of Improved Inter And Intra Cluster Based Multi-hop LEACH Protocol

   Multihop-LEACH is the one of the cluster based routing algorithm. Basic operation of Multihop- LEACH is similar to LEACH protocol. There are two major modifications in Multihop- LEACH protocol with respect to LEACH protocol. Multihoping is applied to both inter cluster and intra cluster communication as shown in figure 3.

   In our improved version of multihop- LEACH protocol, the cluster contains; CH (responsible only for sending data that is received from the cluster members to the BS), vice-CH (the node that will become a CH of the cluster in case of CH dies), cluster nodes (gathering data from environment and send it to the CH).

   In the original multihop-LEACH, the CH is always on receiving data from cluster members, aggregate these data and then send it to the BS that might be located far away from it. The CH will die earlier than the other nodes in the cluster because of its operation of receiving, sending and overhearing. When the CH die, the cluster will become useless because the data gathered by cluster nodes will never reach the base station.

   In our improved multihop-LEACH protocol, besides having a CH in the cluster, there is a vice-CH that takes the role of the CH when the CH dies because the reasons we mentioned above.

   By doing this, cluster nodes data will always reach the BS; so that we dont need to elect a new CH each time the CH dies. By electing a vice cluster head, this will extend the life time overall network.

   Multihop inter cluster operation In this model network is grouped into different clusters. Each cluster is composed of one cluster head (CH), one vice cluster head and cluster member nodes. The respective CH gets the sensed data from its cluster member nodes, aggregates the sensed information and then sends it to the Base Station through an optimal multihop tree formed between cluster heads (CHs)

   with base station as root node as shown in figure 3. In case of the cluster head die, then the vice cluster head role as a main cluster head to gets the sensed data from its cluster member nodes, aggregates the sensed information and then sends it to the Base Station. For this all the cluster members can reach to the base station and the other entire cluster as before.

   Figure3. Nodes Communicate to Base Station using Inter and Intra Cluster Multi-hoping using CH and Vice CH.

   Multihop intra cluster operation However, we note that in general using single hop communication within a cluster for communication between the sensor nodes and the cluster heads may not be the optimum choice. When the sensor nodes are deployed in regions of dense vegetation or uneven terrain, it may be beneficial to use multi-hop communication among the nodes in the cluster to reach the cluster head. As it is possible for nodes to remain disconnected from the network due to a cluster head not being in range, then vice cluster head to role as a cluster head. The operation of multihop-LEACH is depicted in algorithm below.

   Algorithm: An Improved Multihop-LEACH Operation

   STEP 1: Periodically the base station starts a new round by incrementing the round number.

   STEP 2: Nodes (k for each round) with higher probabilities which are chosen as the Cluster Heads and the second higher probabilities are chosen as the vice cluster head, broadcasts an advertisement packet containing new round number.

   STEP 3: Gradually the new round is signaled to all nodes in the network by using the round field in the advertisement packet.

   STEP 4: When a node detects a new round it resets its neighbor table and decides whether to become a cluster head, vice cluster head or leaf node for the next round.

   STEP 5: Nodes however choose its parentnode based on neighboring cluster head depth in the tree and also chosen a vice cluster head vice versa.

   STEP 6: Leaf nodes send newly generated packets to their parent nodes.

   STEP 7: Only cluster head nodes and vice cluster head (in case the cluster head node is die) can forward packets for other cluster head nodes.

   STEP 8: Nodes which do not find the cluster head in their range, request chosen vice cluster head node to become a cluster head by sending advertisement message after a timeout period.

   As in LEACH, the cluster head nodes are rotated randomly and periodically for load balancing. Let there be m clusters. Since the cluster heads and vice cluster head are chosen randomly, we assume that the clusters are uniformly distributed over the entire region, and each cluster on an average has a radius A/m, where A is radius of the region. Let all the nodes use a common communication radius of R. Without loss of generality we assume that R<=A/m where the equality corresponds to single hop communication within the cluster, while the inequality corresponds to multihop communication.

   In order that multihop communication be possible, it is necessary that R be large enough so that connectivity of nodes is guaranteed with a high probability of around 99%.To improve the connectivity we can also increase the probability of clustering to make more nodes to act as Cluster Head nodes by electing them as Vice Cluster Head.

4. Implementation and Simulation

   This section describes the simulation results obtained during the investigation phases of the simulation. We used OMNeT++, is an object- oriented modular discrete event network simulator [16] to implement our improved multihop-LEACH protocol.

   In the simulation network of 100 nodes (comp1, comp2, comp3……, and comp100) are randomly distributed in some distant geographical location to validate the proposed protocol. In the simulation initial node power defined as 1 joule and the channel head probability is 0.2, 0.5, and

   0.1 for random numbers of trials.

   1. Simulation

      1. Simulation Metric

         Latency: This performance metric measure the average end-to-end delay of data packet transmission. The end-to- end delay defines the average time taken between a packet sent by the source, and the time for successfully receiving the message at the destination. Measure this delay takes into account the the propagation delay of the packets and queuing. The time taken to deliver a packet to the base station from the origin node will be looked at when evaluating the protocols. In addition the per hop time delay will also be looked at as performance metric for the network. So that Lower latency is always preferable to higher latency.

         Battery usage: The power consumption is the sum of used power of all the nodes in the network, where the used power of a node is the sum of the power used for communication, including transmitting (Pt), receiving (Pr), and idling (Pi). The amount of power used during the simulation will be monitored and used for evaluating the protocols. Batteries have a finite amount of power and nodes die once power runs out. For this reason lower power usage is preferable to higher power usage. In addition the

         distribution of power usage, power is uniformaly drained across the network will be looked at prefered.

         Success rate: The number of packets received from a node at the base station will be compared with the number of packets sent by a node in order to calculate the Success rate.

         Connectivity: The number of nodes that have a route to the base station will be used to assess the node connectivity provided by a particular routing protocol. More connected nodes in a network are preferable to fewer connected nodes.

      2. Simulation Parameters

         The parameter used in simulating and implementation of the simulation for improved Multihop-LEACH protocol is given in table 1 below.

         Simulation parameters	Values
         Simulation time	1200 sec
         Number of nodes	50,100,120
         CH probability	0.1,0.2,0.5
         Node distribution	Randomly distributed
         Network topology	Loss topology (900×900 m2)
         Number of trials	20 times
         Initial node power	1 joule
         Simulator	Omnet++

         Table.1: Summery Of the Parameters Used In the Simulation Experiments.

      3. Simulation Result

   The Results of the simulation are shown in the Table 2, which shows the Analysis of the improved multihop-LEACH with varying network load and Table 3, which shows the Analysis of the improved multihop-LEACH with varying probability of clustering.

   Performance Metrics	Multihop-LEACH with Probability of clustering p=0.20
   End-to-End delay	Low, it mainly depends on the location and number of CHs
   Per hop delay	Low
   Power usage	Its Very Low Decreases as it as the network load increases
   Success rate	Its Lower than flooding ,mainly depends on the location and number of CHs and vice CH
   Connectivity	Its Lower than flooding, Mainly depends on the location and number of cluster head nodes and vice CH

   Table.2: Analysis of Improved Multihop-LEACH with Varying Network Load

   Performance metrics	Probability of Clustering Varied as 0.10,0.20,0.50
   End-to-End delay (Latency)	decreases with increasing probability of clustering
   Power usage	decreases with increasing probability of clustering
   Success rate	Increases with increasing probability of clustering and vice cluster head
   Connectivity	Increases with increasing probability of clustering and providing a vice cluster head

   Table.3: Analysis of Improved Multihop-LEACH with Varying Probability of Clustering

   Figure4. Message Created with Probability p=0.50

   Figure5. Message Created with Probability p=0.20

   Figure6. Message Created with Probability p=0.10

   Figure7. Consumed Network Energy (Consumed Energy Vs NO. of Nodes)

   Figure 4, 5, 6 shows the simulation graphs for probability for clusters to create the message and Figure 7 shows the simulation graph for consumed energy for the nodes respectively. Our goals in conducting the simulation are as follows: Compare the performance of the clusters Vs. Lifetime, No. of clusters Vs. Energy consumption

5. Conclusion and Future Work

   The overall conclusion is that improved Multihop-LEACH routing protocol is best choice to move towards a network with less energy consumption as it involves energy minimizing techniques like multihop, clustering and data aggregation. Improved Multihop- LEACH uses both inter cluster as well as intra cluster communication with cluster head selection as well as vice cluster head selection. The power usage, latency and success rate in improved Multihop-LEACH can further improved by increasing probability of cluster head and vice cluster head. With a varying probability of clustering, it is clear that more cluster heads in a network results in better connectivity. We can still minimize the energy consumption and extend the network life time by improving the clustering technique.

   From the simulation results, we can draw a number of conclusions. Firstly the, number of

   messages created by the improved multihop- LEACH is less han the messages created by the previous LEACH. Then secondly, if messages created by the new version are less that means the network energy remaining using improved multihop-LEACH is more than the remaining network energy using the previous LEACH. We prove that in figure 7, which means the improved version of multihop-LEACH, outperforms the previous version of LEACH protocol.

   However there are many more issues, which are to be considered related to minimizing the power usage and the network life time in this Multihop- LEACH protocol. We can still minimize the energy consumption and extend the network life time by improving the clustering technique.

6. References

1. Hiba Hachichi, Samia Chelloug(*), Fatima Athmouni, A Virtual Topology For Routing In Adhoc Networks, IEEE,pp. 11,2011.

2. Rajashree.V.Biradar, Dr. S. R. Sawant , Dr.

   R. R. Mudholkar, Dr. V.C .Patil, Inter-Intra Cluster Multihop-LEACH Routing In Self- Organizing Wireless Sensor Networks. IJRRCS, Vol. 2, No. 1, pp. 88-95, March 2011.

3. Sarjoun S. Doumit, Dharma P. Agrawal, Self-Organizing and Energy-Efficient Network of Sensors, IEEE, pp. 1-6, 2002.

4. I.F. Akyildiz, W Su, Y. Sankarasubramaniam and E Cayirci, Wireless Sensor Networks, A Survey, Communication Magazine, IEEE, Vol. 40 Issue 8, pp. 102-114, August 2002.

5. W. Heinzelman, Application specific protocol architectures for wireless networks, PhD Thesis, MIT, 2000.

6. Jamal N. Al-Karaki Ahmed E. Kamal, Routing Techniques in Wireless Sensor Networks: A Survey, IEEE Wireless Communications, volume: 11, pp. 6-28, 2004.

7. K. Akkaya, M. Younis, A Survey on Routing Protocols for Wireless Sensor Networks, Vol. 3, No. 3, pp. 325- 349, May 2005.

8. F. Ye, A. Chen, S. Liu, L. Zhang, A scalable solution to minimum cost forwarding in large sensor networks, Proceedings of the tenth International Conference on Computer Communications and Networks (ICCCN), pp. 304-309, 2001.

9. M. Chu, H. Haussecker, and F. Zhao, Scalable Information-Driven Sensor Querying and Routing for ad hoc Heterogeneous Sensor Networks, The International Journal of High Performance Computing Applications, Vol. 16, No. 3, pp. 293-313, August 2002.

10. C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of ACM MobiCom 00, pp. 56-67, Boston, MA, 2000.

11. W.Heinzelman, J. Kulik,and H. Balakrishnan, Adaptive Protocols for Information Dissemination in Wireless Sensor Networks, Proc. 5th ACM/IEEE Mobicom Conference (MobiCom 99), Seattle, WA, pp. 174-85, August, 1999. .

12. J. Kulik, W. R. Heinzelman, and H. Balakrishnan, Negotiation-based protocols for disseminating information in wireless sensor networks, Wireless Networks, Vol. 8, pp. 169- 185, 2002.

13. K. Sohrabi, J. Pottie, Protocols for self- organization of a wireless sensor network, IEEE Personal Communications Vol. 7, Issue 5, pp 16-27, 2000.

14. J.-H. Chang and L. Tassiulas, Maximum Lifetime Routing in Wireless Sensor Networks, Proc. Advanced Telecommunications and Information Distribution Research Program (ATIRP2000), College Park, MD, pp 334-335, Mar. 2000.

15. C. Rahul, J. Rabaey, Energy Aware Routing for Low Energy Ad Hoc Sensor Networks, IEEE Wireless Communications and Networking Conference (WCNC), vol.1, Orlando, FL, pp. 350-355, March 17-21, 2002.

16. OMNET ++ Website, www.omnetpp.org.

17. C. Shen, C. Srisathapronphat, C. Jaikaeo, Sensor Information Networking Achitecture and Applications, Proceedings of IEEE Personal Communications, Vol.8, No. 4, pp. 52

    59, August 2001.

18. Rajashree.V.Biradar, V.C.Patil , Dr. R. R. Mudholkar , Dr. S. R. Sawant , Classification And Comparison Of Routing Protocols In Wireless Sensor Networks, Ubiquitous Computing and Communication Journal volume 4, pp.704-711, 2009.