LoCoDuo – Low Cost Dual Hop Clustering based Routing Protocol for Wireless Sensor Network

LoCoDuo – Low Cost Dual Hop Clustering based Routing Protocol for Wireless Sensor Network

Basavaraj M Bhooma1 Harish K N2 Ganavi G3 Navyashree R4 Manjula G5 12348th Semester B.E, Dept. of ISE, SJBIT, Bangalore, Karnataka 5Associate Professor, Dept. of ISE, SJBIT, Bangalore, Karnataka

Abstract- As with the cases of other works in routing protocols of wireless sensor networks, the focus of this research is power efficiency and thus achieving increased network lifetime so that the sensor network can be used for a longer period of time. Here we proposed all new concept of two hop low power transmission of data between the cluster head and sink in case of clustering based routing protocols and then compared the results with LEACH protocol and some of its other recent variants and obtained better performance in network lifetime. It is also seen that apart from being the most power efficient, this proposed algorithm works best as compared to others when the number of nodes deployed is less i.e. it is best suitable for low cost sensing.

Keywords: LoCoDuo, LEACH, clustering, multihop, power alteration, thresholding, low-cost, dualhop

1. INTRODUCTION

   In recent past fast development of low cost sensors nodes gave way in building wireless sensor network for utility in various fields of earthquake detection, military surveillance, structural health monitoring and other disaster mitigations. Although the concept of such wireless sensor networks is still in scientific laboratories there is no doubt that it is the next generation of emerging technologies. A sensor node is equipped with a transceiver antenna, a control unit and a power unit with which it performs a continuous surveillance of a geographical area in which it is deployed. But its battery power is limited and a node dies off when its battery power is depleted. The network remains

   active until maximum of the nodes die off and

   wireless sensor researchers around the globe try to maximize this network lifetime. There is a base station or sink to which the nodes transmit the sensed data and is not constrained in power. Traditionally, the sensor nodes send radio signals to the neighbour nodes and the neighbour in turn passes the signal on until the signal has reached the base station but this data routing technique, called flooding, un-necessarily consumes power of the intermediate nodes and the network dies off very early. The base station, sometimes called sink also has the ability to query data from a single node or a collection of nodes. However in this context all the nodes do not have a direct communication link to the base station and the message has to travel multiple hops through other nodes to reach the destination and reverse. Here basically we propose a routing protocol to improve on the network life time, which besides using a new idea, combines power saving schemes from some other already proposed clustering based protocols into core LEACH protocol.

   The rest of the paper is arranged as follows, the literature survey part briefs the details of the existing routing protocols and points out their pros and cons. Next we put forward our proposed algorithm and in the following section we give our experimental results and compare the results with that of other protocols. We conclude this paper with a section called conclusion and future works.

2. RELATED WORKS

   In this section we study LEACH protocol and some of its recent variants.

   1. LEACH

      LEACH [1] is the most preferred of all wireless sensor network routing protocols and most of the researchers compare their protocols with the parameters in LEACH. Here the sensor nodes self- organize themselves into clusters at the start of each round [2], which is called dynamic clustering and this avoids a single cluster head to lose energy every time. When clusters are created each node autonomously decide whether it can be a cluster

      head for the next round using a stochastic formula:

      T(n) = P

      1 – P x (r mod 1/P )

      Where P is suggested percentage of cluster head in

      a round and is determined a priori and r is the current round number. The purpose of using this formulae is to ensure that each node becomes the cluster head only once in 1/P rounds. The outcome of this round calculation in LEACH is nothing but a threshold, T(n), and if a random number generated by all node (except previous round cluster head) is less then T(n), the node is selected as the cluster head. The cluster heads communicate the aggregated data from the cluster to the base station directly. The other member nodes of a cluster periodically send their sensed data to the cluster head and rest all other time. Each node decides its cluster by comparing received signal strength of advertisement message sent by elected cluster nodes in each round.

      Fig. 1: Clustering technique in LEACH

   2. Multi-hop LEACH

      Multi-hop LEACH [5-7] is another variant where all cluster heads do not transmit aggregated data directly to the base station but through other cluster heads and they choose the path with lowest hop count. Only the neighbour cluster heads communicate with the base station.

      (1)

      Fig.2: Multi-hop LEACH [13]

   3. LEACH-SC

      LEACH-SC [9] slightly modifies the cluster formation in LEACH. Here a non-cluster node associates itself with the cluster head which is nearest to the midpoint between itself and the base station. In this way this protocol prohibits data flow in a direction away from the base station during the data transfer from a node to the cluster head and as the data always flows towards the base station the protocol saves considerable energy as compared to its other counterparts.

   4. MODLEACH

      MODLEACH, proposed recently in [10], uses dual transmission mode for data transfer depending on the distance between cluster member and cluster head or cluster head and base station. In each transmission energy of the transmitting node reduces by a factor f, which is evaluated using formula:

      f=(ETX+EDA)*4000+EM*4000*(dist*dist)a

      where ETX is Transceiver idle state energy, EDA is data aggregation energy (which is zero for a intra cluster transmission), EM is energy mode constant it is ten times high in long distance communication as compared to a short distance one, dist is the distance between the sender and the receiver and a is a constant with a value of 1 in case of low power mode and 2 for high power mode. Apart from dual power transmission mode, MODLEACH also

      restricts repeated cluster formation by using energy level thresholds.

   5. TEEN

      Threshold sensitive Energy Efficient sensor Network protocol

      [11] is an event driven protocol. It uses a new concept to save power by transmitting sensed data only when some event happens like sudden increase in temperature etc. It has two type of thresholds like hard and soft threshold. Hard threshold is a globally set value whereas soft threshold is chosen adaptively by a cluster by co- operating with other clusters. Although TEEN is one of the most energy efficient protocol, but it cannot be applied to applications where periodic report of sensed data is needed to be passed to the sink because sensors nodes only switch on their communication module (radio transmitter) when some event occurs. TEEN has shown simulation results to outperform LEACH [11].

   6. PEGASIS

   Power Efficient Gathering in Sensor Information System [12] is a massive improvement with a small change in LEACH protocol. Here the aggregated data from cluster heads gets transferred to the single cluster head which is nearest to the base station..

   Fig.3: Chain Clustering in PEGASIS

   As an obvious disadvantage, cluster c2 in figure 3 has to wait to receive the aggregated data from both sides and it aggregates the data received from all the clusters and sends it to the base station. PEGASIS achieves 100% to 300% more power efficiency then LEACH [4]. But the single cluster connecting to the base station (sink) becomes a bottleneck moreover a delay is introduced as the single cluster, in our case cluster c2 in figure 2, has to wait for data from other clusters. To combat this delay Hierarchical PEGASIS [12] was developed by combining the idea of LEACH and PEGASIS.

3. PROPOSED ALGORITHM

   Our work is aimed to better the network lifetime and for this we need to have nodes alive till maximum number of rounds. We assume that the

   nodes are power constrained and are supplied a fixed amount of initial energy and when the energy goes to zero the node becomes dead permanently. On the other hand the base station is supplied with continuous power. Furthermore, the nodes are not mobile and are deployed randomly in the area of 100×100 . The base station is placed in the centre of the target region i.e. in the co-ordinate (50,50) because we get maximum network lifetime in average case for a random organization of nodes. For comparison the number of nodes is kept 50 and the value of percentage of clusters (p), from the LEACH is 0.1. This means that in every round

   0.1% of the total number of nodes will be cluster heads.

   We combine power saving concepts from of the existing clustering protocols along with our proposed dual hop data transfer scheme. Mahmood et. al in [10] pointed out that the nodes need less power to transfer their data within the cluster to the cluster head and need high power while communicating with base station or other cluster heads if cluster head selection criteria is minimum distance, assuming that the low power transmission amplification energy is ten times less than that of high power. Accordingly the communication type is characterised as intra cluster, inter cluster or cluster head to base station. We designed our algorithm such that the member nodes in a cluster which only needs to do intra cluster communication requires transmission energy ten times less than that needed for other two types of communication. This we say as the dual mode transmission power. If the distance between the sender and the receiver is less than d0, we can use the low power transmission otherwise we use high power transmission. This threshold d0 is equal to square root of the ratio between high and low transmission mode energy.

   Next as we used that thresholds can be applied to perform power saving, but applying thresholds restricts producing periodic data. LEACH has the problem of losing energy as in every round the nodes need to re-cluster themselves as a new cluster head comes to existence. Therefore we applied the hard thresholding scheme in a way that if the cluster head did not exhaust away half of its initial energy then we avoid the re-clustering to save energy. This type of a thresholding scheme was also used in MODLEACH.

   So in order to improve the network lifetime, we incorporated a whole new idea of transmitting aggregated data from the cluster head to the base station in two low power hops to save energy, rather than using one single high power hop to the base station. The data is send from a cluster head to another cluster head within a distance of less than d0 from itself and also the receiver cluster head should have a distance less than d0 from the base station. This idea is based on the phenomenon that if we use alternating power transmissions, routing of data using two low power hops is more energy saving than using a single hop high power transmission. The figure 3 suggests the various power saving schemes used in this proposed scheme.

   Parameter	Value
   Network Size	100×100
   Initial Energy of the sensor nodes (E0)	0.5J
   Packet Size	4000bits
   Transceiver Idle State Energy (ETX)	50nJ/bit
   Data Aggregation Energy (EDA)	5nJ/bit/record
   Long range transmission amplification energy (EFS)	10pJ/bit/
   Short range transmission amplification energy (EMP)	0.0013pJ/bit/
   Long range intra-cluster transmission amplification energy (EFS1)	EFS/10
   Short range intra-cluster transmission amplification energy (EMP1)	EMP/10

   Parameter	Value
   Network Size	100×100
   Initial Energy of the sensor nodes (E0)	0.5J
   Packet Size	4000bits
   Transceiver Idle State Energy (ETX)	50nJ/bit
   Data Aggregation Energy (EDA)	5nJ/bit/record
   Long range transmission amplification energy (EFS)	10pJ/bit/
   Short range transmission amplification energy (EMP)	0.0013pJ/bit/
   Long range intra-cluster transmission amplification energy (EFS1)	EFS/10
   Short range intra-cluster transmission amplification energy (EMP1)	EMP/10

   Fig 3: Proposed scheme overview ASSUMPTIONS OF PARAMETER VALUES

4. EXPERIMENTAL RESULTS AND COMPARISON The proposed routing protocol is simulated using matlab (R2011a) and the resulting network lifetime is compared

   with LEACH and its two recent

   variants LEACH-SC, MODLEACH. It is seen that the proposed algorithm has a better network lifetime in all the tested scenerios. As the nodes are deployed randomly using matlab random function and that is why the resulting network lifetime varies between two extremes as shown in table 1 below. The table shows the number of rounds for which the network remains active in a fixed area of

   100×100 for variable number of nodes and we find our algorithm to be more stable and scalable. By more stable we mean that the network lifetime remains fixed on any random distribution of nodes unlike traditional LEACH and LEACH-SC. A much scalable scheme means that the algorithm performs well irrespective of increase or decrease of nodes. Moreover, the algorithm gives more lifetime using even minimum number of nodes. That is why we call this proposal a low cost sensing one. We plot network's remaining energy versus rounds for all the protocols in figure 4 where the number of nodes is kept at 50. The network dimension is 100×100 in every case. The graphs show us that the network remains alive for

   700 rounds and 1600 rounds for LEACH and MODLEACH respectively (Fig. 4 (a), (b)) while the lifetime extends a little over 1900 for our proposed algorithm (Fig. 4(c)).

   TABLE II COMPARISON CHART

   No. of Nodes	LEACH	LEACH- SC	MODLEACH	PROPOSED Algorithm
   10	10-350	10-500	1650-1850	1900-1950
   30	100- 1200	300-700	1550-1700	1700-2000
   50	100- 1200	300-700	1500-1700	1700-1850
   70	100- 1300	100-850	1500-1700	1600-1800
   90	100- 1000	400- 1300	1500-1700	1650-1850

   Fig. 4 (a,b,c): Graphs for network life vs rounds for (a) LEACH, (b) LEACH-SC

   (c) MODlEACH and (d) proposed algorithm

5. CONCLUSION AND FUTURE WORKS

   As in the previous section we see that as compared to the other existing protocols, our proposed algorithm performs best in respect to the network lifetime in variable the number of nodes in the given area. Also as compared to others both MODLEACH and the proposed algorithm are more stable i.e. having limited range of outputs as compared to two LEACH and LEACH-sc. Our algorithm is the most scalable of all as already shown in table 5 and moreover it is distinctively the best when the number of nodes is less. So this method is most suitable when the number of nodes are less, i.e. for low cost sensing. We have also observed in experimentation that if we use three hops in place of two hops the network lifetime is less varying against random deployment of nodes but gives little lesser lifetime. So we can use triple hop variant of the proposed algorithm for more gurantee of lifetime against arbitrary node deployment.

   However, if we arrange the clusters in such a way that there are maximum low power dual hops, the power efficiency can be pushed up further which we look forward to do in the near future

6. REFERENCES

1. W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless sensor networks," in the Proceeding of the Hawaii International Conference System Sciences, Hawaii, January 2000.

2. W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient routing pro- tocols for wireless microsensor networks," in Proc. 33rdHawaii Int. Conf. System- Sciences(HICSS), Maui, HI, Jan. 2000.

3. Heinzelman W. B., Chandrakasan A. P., Balakrishnan H., "An application-specific pro- tocol architecture for wireless microsensor networks," IEEE Trans on Wireless Commu- nications, Vol., No. 4, 2002, pp. 660-670, doi: 10.1109/TWC.2002.804190.

4. Thiemo Voigt, Hartmut Ritter, Jochen Schiller, Adam Dunkels, and Juan Alonso,"Solar-aware Clustering in Wireless Sensor Networks", In Proceedings of the Ninth IEEE Symposium on Computers and Communications, June 2004.

5. Fan Xiangning1,2 Song Yulin "Improvement on LEACH Protocol of Wireless Sensor Network" International Conference on Sensor Technologies and Applications 2007.

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

   Mudholkar , Dr. V.C .Patil "Multihop Routing In Self-Organizing Wireless Sensor Networks" IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 1, January 2011.

7. Israr N and Awan I "Multihop clustering Algorithm for load balancing in Wireless Sensor Networks," International Journal of Simulation, Systems, Science and Technology, 2007, vol. 8, No. 1, pp. 13-25.

8. Lan Tien Nguyen, Xavier Defago, Razvan Beuran, Yoichi Shinoda, "An Energy Efficient Routing Scheme for Mobile Wireless Sensor Networks", IEEE, 2008.

9. Wang Jun,Zhang Xin, Xie Junyuan, Mi Zhengkun, "A Distance-based Clustering Routing Protocol in Wireless Sensor Networks" Important national science technology specific projects 2011.

10. D. Mahmood, N. Javaid, S. Mahmood, S. Qureshi, A.

    M. Memon, T. Zaman, "MODLEACH: A Variant of LEACH for WSNs",8th IEEE International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA'13),Compiegne,France, October 2013.

11. A. Manjeshwar and D. P. Agrawal, "TEEN : A Protocol for Enhanced Efficiency in Wireless Sensor Networks," in the Proceedings of the 1st International Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, San Francisco, CA, April 2001.

12. S. Lindsey and C. S. Raghavendra, "PEGASIS: Power Efficient GAthering in Sensor Information Systems," in the Proceedings of the IEEE Aerospace Conference, Big Sky, Montana, March 2002.

13. Javaid N., Rahim A. , Nazir U. , Bibi A. , Khan Z.A."Survey of Extended LEACH-Based Clustering Routing Protocols for Wireless Sensor Networks" in the proc. of High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference, pp. 1232-1238, Liverpool, June 2012.