Hierarchical Routing Technique for Prolonging the Lifetime of Wireless Sensor Networks

Hierarchical Routing Technique for Prolonging the Lifetime of Wireless Sensor Networks

Sanjay waware 1, Dr. Nisha Sarwade 2

1 ( M.Tech.(Electronics and Telecommunication) 2 ( Associate Professor ,Department of Electrical Department of Electrical Engineering, VJTI, Engineering, VJTI, Mumbai, Maharashtra, Mumbai, Maharashtra, INDIA.

Abstract

Wireless sensor network s (WSNs) usually consists of a large number of nodes called sensor node that bring themselves together to form a wireless network . However, the ma jor fact that sensor nodes run out of energy quick ly has been an issue and man y power efficient routing protocols have been proposed to solve this problem and seniority of the network . This is the reason why routing techniques in wireless sensor network focus mainly on the accomplishment of power conservation. In this paper we intend to proposes the algorithms for cluster formation and cluster head (CH) selection for prolongs the network lifetime. This algorithm selects CH with highest residual energy in each communication round of transmission and also tak es into account, the shortest distance to the base station from the CH. In our approach, the cluster formation is done geographically.

Keywords: Base station, Clustering, Cluster head, Residual Energy, Routing protocols, Wireless sensor network s.

1. Introduction

   Genera lly, routing protocols on the basis of network structure are divided in to three main groups as Flat routing, Hie rarchica l routing, Location based routing. Due to the nature of the WSN, sensor nodes are norma lly powe red by the use of batteries and thereby having a very constrained budget in terms of energy [1]. To e ffective ly ma intain the network sensors to have longer lifetimes, all areas of the network should be

   carefully designed to be energy efficient. Among many methods, clustering the sensor nodes into groups , so that sensors send information to only the cluster heads (CH) and then the CH co mmunicate the aggregated informat ion to the base stations, may be a good method to minimize energy consumption in WSN. This data aggregation in the head nodes greatly reduces energy consumption in the network by minimizing the total data messages to be sent to BS. The less the energy consumption, the more the network life time. The main idea of developing cluster-based routing protocols is to reduce the network traffic toward the sink. This method of clustering may introduce overhead due to the cluster configuration and maintenance, but it has been demonstrated that cluster-based protocols exhibit better energy consumption and performance when compared to flat network topologies for la rge-scale WSNs [2]. A survey of the routing technique in wireless sensor network and mentioned that hierarchica l routing technique has the advantages related to scalability and efficient co mmunication [9].

   In WSN various algorithms have been developed for Cluster format ion and CH selection such as LEA CH, PEGA SIS,TEEN etc. In this paper have to proposes the Hierarch ical routing algorith m which is used for prolongs the lifet ime of the wireless sensor networks uses hierarchica l routing technique includes cluster format ion and CH selection. Simu lation results show that proposed technique is better than the non – hierarchica l routing technique. Also it is power efficient and prolongs the lifetime of WSN.

   The paper is organized in the following way. Hav ing section 1 which introduces the paper in brief, section 2 e xpla ins related work, section 3 introduces the energy model e mp loyed and proposed hierarchica l routing technique . Section 4 gives simu lation setup and its validation. Also shows the the simu lation of non- Hie rarchica l and Hierarch ical c luster formation and how it is being imple mented in MATLA B. Section 5 conclude the paper and also mentioned the scope of future design .

2. Related Works

   The various power efficient Hiera rchical routing protocols have been proposed for minimizing energy consumption and to increase the network life time in WSN such as by Heinemann et al. [3], who described the LEA CH protocol , is a kind of cluster-based routing protocols, which includes distributed cluster formation. LEA CH randomly selects a few sensor nodes as cluster heads (CHs) and rotates this role to evenly distribute the energy load among the sensors in the network. LEA CH uses time division mu ltip le access (TDMA), to transmit data fro m the sensor nodes to the cluster head. Then CH aggregates the data and transmits it to the base station for processing. One of the features of LEA CH is it rotates the cluster heads in a randomized fashion to achieve balanced energy consumption.

   In [4] Lindsey et al. who describe PEGASIS protocol , it is an enhancement over the LEACH protocol and it is a near optima l chain-based protocol. The basic idea of the protocol is that in order to extend network lifet ime, nodes need only communicate with their closest neighbours, and they take turns in communicat ing with the BS. It e liminates the overhead of dynamic c luster formation created by LEA CH. In this protocol, the nodes transmit to the CH and transmission of data is done by the cluster head, which is selected in a rotational manner, to the BS. PEGASIS protocol is found to save more energy and is more robust in node failu re when co mpared to LEACH.

   In [5] A. Manjeshwar et al who describe TEEN, which is a hybrid of hierarchical clustering and data- centric protocols, which groups sensors into clusters with each led by a CH. TEEN uses LEA CHs strategy to form cluster. First level CHs are formed away fro m

   the BS and second level c luster heads are formed near to the BS.

   Muruganathan et al. [6] developed a protocol that creates clusters of the simila r size and uses multi-hop routing between CH and the BS. The cluster head which forward the last hop is selected randomly fro m the sets of cluster heads to min imize the load of cluster head which are located nearest to the base station.

   Wei Cheng et al. [7] proposed a novel adaptive, distributed, energy efficient clustering algorithm, AEEC for wire less sensor network. Their approach selects cluster heads based on the node energy related to that of the whole network which can bring about efficiency in heterogonous networks.

3. Proposed Technique

   The Hierarch ical routing algorith ms have been designed main ly for to reduce the power consumption in wire less sensor networks during communicat ion rounds and increase the lifetime of networks .Thus, the research question is: How can we improve the lifet ime by reducing energy consumption in Wireless Sensor Network using the hierarchica l routing technique?

   For the solution of this question we designed new algorith m for cluster formation and cluster head selection .To reduce energy consumption in WSN, we have proposed an approach whose principle of c luster head selection is based on the highest predicted residual energy after the following round and the shortest distance via the closest neighbouring cluster head to the base station. In our approach, the cluster formation is done geographically.

   1. First Order Radio Model for System

      Currently, there is a great deal of research in the area of low-energy radios. Different assumptions about the radio characteristics, inc luding energy dissipation in the transmit and receive modes, will change the advantages of diffe rent protocols [8] . In our work, we assume a simple model where the radio dissipates Eelec=50 nJ/bit to run the transmitter or rece iver

      circuit ry and amp=100 pJ/bit/ m2 or the transmit

      amp lifier. These parameters are slightly better than the current state-of-the-art in radio design.

      Figure1.First Order Radio Model For the system

      We also assume an r2 energy loss due to channel transmission. Thus, to transmit a k -bit message a distance d using our radio model, the required energy is given as in equation (1):

      ETx (k, d) = ETx-elec (k) + ETx-amp (k, d)

      ETx (k, d) = Eelec * k + amp *k* d2 …… (1)

      And the energy consumed to receive this message at receiver is given as in equation (2):

      E Rx (k) = E Rx-elec (k)

      E Rx (k) = E elec * k ……(2)

      Where

      ETx-elec -energy dissipated per bit at transmitter

      E Rx-elec – energy dissipated per bit at receiver

      amp -a mp lification factor

      Eelec – cost of circuit energy when transmitting or

      receiving one bit of data k- a nu mber of transmitted data bits d – distance between a sensor node and its respective cluster head or between a CH to another cluster head nearer to the BS or between CH and BS.

      For these parameter va lues, receiving a message is not a low cost operation; the protocols should thus try to min imize not only the transmit distances but also the number of transmit and receive operations for each message. We make the assumption that the radio channel is symmetric such that the energy required to transmit a message from node A to node B is the same as the energy required to transmit a message from node B to node A for a given SNR. For our e xpe riments, we also assume that all sensors are sensing the

      environment at a fixed rate and thus always have data to send to the end-user.

   2. The Proposed Routing Algorithm

      The proposed hierarchical routing protocol is based on the principle of clustering algorithm. With data transmission at the network layer being the core area of interest, we have modified the LEA CH protocol in terms of hierarchica l data transfer with the employ ment of energy prediction technique for selection of CH via any shortest path to the BS. In the proposed model, clusters are formed geographically. Geographical formation of c luster sizes is based on equal segmentation of area space, depending on the case being considered. Apart from the one cluster format ion which makes use of the entire sensors area space, other formation such as two clusters formation and three clusters formation involves equal segregation of area space. The CH elect ion phase proceeds after the cluster formation phase. The selection of CH(s) within each cluster formed is carried out by electing a node that require less transmission energy (to BS or to the next hop CH nearer to the BS) to be the CH for a particu lar transmission round. Due to draining activities being constraint on a cluster head during data aggregation and transfer phase, the cluster head is rotated amon g the sensor nodes of each cluster at every transmission round. A completely new estimation of energy is carried out at the beginning of every transmission round to elect a new CH for the cluster and thereby energy wastage is being reduce to its minimu m, and utilizat ion of each nodes energy is being ma ximized to ensure a prolong network lifetime.

      The proposed hierarchical routing technique consists of four ma in stages

      • Geographical formation of cluster.

      • Selection of cluster heads in each cluster formed.

      • Data aggregation phase which involves the gathering of collected data by the cluster head fro m the sensor nodes within its cluster.

      • Data transmission phase which involves the transfer of all data fro m the nearest cluster head(s) to the BS.

        Also, the CH selection in the proposed hierarchical routing technique can be expla ined also in four main stages:-

      • The init ial energy Ein(n) of node is measured

      • The distance d(n) fro m each node to the base station or to the corresponding higher level c luster head is measured.

      • Estimation of the energy required by each node for transmission within the cluster not to BS or to higher level CH for two and three cluster formation within a cluster is carried out using the formula : ( amp*k* d2)

      • The ma ximu m energy after the subsequent

      transmission round for each node is estimated and selection of CH is done using the formula : ma x (Ein(n) – amp*k*d2), then after the CH selection is

      carried out, the next cluster head selection will take

      place after the current round is co mpleted.

4. Simulation Setup and Validation

In previous section we proposed a hierarchicalbased routing protocol that improves the network lifet ime of the system. In this section, we show how the protocol performs better in terms of power effic iency b y improving the lifetime of WSN. In this simulat ion, a total number of 250 nodes were randomly deployed within a space region on 300 m x 300 m.The parameters used in the simu lation are listed in Table 1.

Table1. Param eter Values

Proposed Routing Technique:

Figure 2. Flowchart of the proposed hierarchical routing technique.

Cluster Head (CH) Selection:

Figure3. Flowchart of Cluster Head selections.

With the nodes being deployed, some assumptions were made concerning the node features and these are as follows:

• All nodes are homogeneous in nature;

• All nodes starts with the same in itia l energy;

• The base station is situated at the (0,0) orig in of the area space;

• Clusters and nodes are static;

• Norma l nodes transmit directly to their respective cluster heads within a particula r cluster;

• Cluster heads use mult i-hop routing to relay data to the data sink;

1. Simulation Results

   1. Cluster for mation with CH election wi th routi ng.

      Figure 4. One cluster formation with CH selection and routing.

      Figure 5. Two cluster formation with CH selection and routing.

      Figure 6. Two cluster formation with CH selection and routing.

   2. Ne twork lifeti me Gr aph.

      Figure 7. Net work Lifetim e

      Table 2. Com parison of Network Lifetime

      Cluster size	First node dies	Network lifetime
      One	3	110
      Two	78	200
      Three	87	342

      Table3. Com parison of Mean and variance

      No. Of Cluster	Mean value	Variance
      One	7.3410	6.7818
      Two	13.0593	10.9153
      Three	46.1048	44.0060

   3. Residual e nergy at node and me an value

Figure 8. Residual energy at each node and mean value in one cluster form ation

Figure 9. Residual energy at each node and mean value in two cluster formation

Figure 10. Residual energy at each node and mean value in three cluster formation.

Discussion

1. Using our technique we formed one, two and three cluster format ion with CH selection and its routing as shown in fig.(4), fig.(5) and fig.(). We a lso plot the network lifetime graph for observation of their lifetime as shown in fig.(7).

2. It is observed in fig.(7) that the first node dies faster in the one cluster formation because all nodes tend to send captured data via one randomly selected cluster head per round to the BS. The constrained load on the elected cluster heads during the entire communication round of simulation drastically reduced the CHs energy over a short period.

3. It is also observed that the proposed technique offers a better life span for each nodes and even the entire network. Our proposed technique uses optima l energy to extends the lifetime of networks to an impressive range as compared to one cluster formation. The impressive increment in life span of the network fro m our proposed hierarchical technique is seen as a result of effic ient routing decision and optimization of energy in CH selection of each c luster formed.

4. Since the sensor nodes in each cluster send data to the cluster head within its cluster range and then the aggregated data is sent to the cluster head closer to the base station, which further aggregates data of its own cluster and that of the incoming data, from cluster head whose distance is farther to the BS, before sending the data to the base station. Thus, a considerable a mount of energy is saved which indicate improved network lifet ime in the case of two

   cluster formation when compared to one cluster formation technique.

5. Furthermore , we also observed in Fig. (7) that the network lifetime increased to a certain length in the three cluster format ion scenario. With this increase, the WSNs lifetime was further prolonged when compare to the two cluster format ion and the non hierarchica l technique. The table 2. indicate when was first node died and total lifet ime of the network in case of one , two and three cluster formation scenarios.

6. Our proposed technique is also proved by evaluating the residual energy in each node for a particular rounds of simulat ion. The results in Fig. (8), (9) and

   (10) show that the mean residual energy value of all

   the sensor nodes of proposed method is higher than the non hierarchical method which is a fu rther indication of an imp roved network lifetime when our proposed technique is being imple mented.

7. The Table 3. Shows the mean value and variances of the residual energy after 400 rounds simu lations for the hierarchical routing technique used. The mean value of the residual energy increases in each round of simu lation as the hierarchical structure increases

   .This imp lies better network performance since the nodes has more energy in the latter level of hiera rchy.

8. It is also observed in the Table 3. that one cluster formation has the lowest variance and the three cluster formation has highest standard deviation value. The highest value imp lies the residual energy values after those rounds of simulation are spread out over a large range. It is also observed that a larger variance value indicate how dispersed the residual energy of all node is fro m the mean value a fter the entire simulat ion rounds. It is also noticed that as the value of the variance gets closer to the mean value, it implies a better performance of network since most of the node will die almost at the same t ime in the end of the simu lation. The Figure 4.9, Figure 4.10 and Figure 4.11 show the plot of the histogram of the histogram of the residual energy after 400 rounds of simu lation.

In this paper, we propose an hierarchica l routing technique in which is used for prolonging the lifet ime of sensor networks in which c luster heads are elected based on the prediction of transmission energy via a shortest distance to the base station. The important features which includes cluster formation and rotation, cluster head election and rotation, and cluster optimization of our proposed hierarchical routing technique in transmitting data to the base station was analyzed and emphasized. Our proposed hierarchical technique, which uses the predict of smallest transmission energy via the shortest path possible to send data to the BS proved that it offers more reduced energy consumption and also increase the lifetime of the WSN.

In future work, the number of clusters increases to four, five, six and so on, can be investigated. Therefore, this can show how the lifetime in the network would be affected and the optimal c luster size would also be known in case the lifetime is reduced at a certain level of hierarchy. Qua lity of services (QoS) re lated to video and imaging sensors, factors affecting cluster format ion and the communication between CHs or CH to BS are open issues for future research.

References

1. N.M. Elshakankiri, N. M. Moustafa and Y. H. Dakroury, Energy Effic ient Routing Protocol for Wireless Sensor Network in IEEE International Conference on pp. 393 -398,Dece mber 2008.

2. Sanjay Waware, Dr. Nisha Sarwade and Pallavi Gangurde, A Review of Power Effic ient Hie rarchica l Routing Protocols in Wire less Sensor Networks in International Journal of Engineering Research and Applications (IJERA) Vol. 2, Issue 2,Mar-Apr 2012, pp.1096-1102.

3. W. R. Hein ze lman, A. Chandrakasan, and H. Ba lakrishnan.Energy effic ient communicat ion protocol for wire less microsensor networks. In Proceedings of the Hawaii International Conference on System Sciences, January 2000.

4. S. Lindsey and C.S. Raghavendra, . PEGASIS:Powe r effic ient Gathering in Sensor Information System., Proceedings IEEE Aerospace Conference, vol. 3, Big Sk y, MT, Mar. 2002, pp. 1125-1130.

5. A. Manjeshwar and D. P. Agrawal, TEEN: A Protocol for Enhanced Effic iency in Wire less Sensor Network . In 1st international Work shop on Parallel and Distributed Computing Issues in Wireless Network s and Mobile Computing, 2001, p.189.

6. S.D. Muruganathan, D.C.F. Ma , R.I. Bhasin and

   A.O. Fapoju wo, A Centralized Energy Effic ient Routing Protocol for Wireless Sensor Network, IEEE Radio Communications, pp S8-S13, March 2005.

7. W. Li, G. Chen, Energy-Effic ient Clustering Algorith m in W ire less Sensor Network in IET International Conference on pp. 1-4, Nove mber, 2006.

8. W. R. He inze lman, A. Chandrakasan, and H. Ba lakrishnan. Energy effic ient communicat ion protocol for wire less microsensor networks. In Proceedings of the Hawaii International Conference on System Sciences, January 2000.

9. J.N. Al-Kara ki and A.E. Ka ma l, Routing Techniques in Wire less Sensor Network in Wireless Communication, IEEE, Vo l. 11, 2004, pp 6-28.