Optimized Cluster based Framework with EIDA and Leach for Preserving Connected Dominated Sets Lifetime in WSN

Download Full-Text PDF Cite this Publication

Text Only Version

Optimized Cluster based Framework with EIDA and Leach for Preserving Connected Dominated Sets Lifetime in WSN

K. Santhoshkumar1, Dr. P. Suganthi2

1Asst. Prof. Department of CS, Thiruvalluvar Arts and Science College, Kurinjipadi

2Asst. Prof. Department of CS, N.K.R Gov. Arts College for Women, Namakkal

Abstract:- Internet of Things (IoT) empowered communications evolved up with various smart sensor technologies operable with resource constraint nodes in various field of interests. Since many years typical sensor node functionality usually emerged with the advancement of network requirements in practice. A wireless sensor node is a battery-driven miniature electronic device capable of doing some sort of operation within a specific human inaccessible region. A typical WSN consists of a set of spatially distributed independent sensor nodes well capable of cooperatively monitoring certain activities of human concern including network monitoring, sensing different physical attributes such as heat, pressure, etc. In a wide-range WSN, a sensor node performs sensing, computation, and communication with a very limited amount of resources which exhibits its potential drawbacks towards extending the network lifetime by conserving energy. However, owing to various potential beneficial aspects, WSN has advancements where various research challenges as well as endless opportunities explored in various fields. WSN communication and routing plays a crucial role in the effective monitoring of specific environmental factors. The prime operational goal of a typical WSN includes collecting data from the certain environment and forward that to sink node considering optimized communication route. Prevailing techniques evolved up with a new paradigm namely clustering which they have applied into designing an energy efficient hierarchical communication protocol (LEACH). There exists a various state of the art studies referred Low Energy Adaptive Clustering Hierarchical Protocol (LEACH) as a baseline to evaluate benchmarking where the studies considered few of the assumptions as similar as LEACH Battery energy consumption is the dominant factor in node aging when the network deployment environment is favorable, and the device is highly reliable. The proposed research work provides the better end to end delay, life time and reduce data loss with combination of LEACH, EIDA and clustering method.

Keywords: Dominated sets, LEACH, Data accumulation, Iterative Deepening and EIDA.


This work focuses on designing a new clustering based routing protocol to improve the network lifetime and balancing the power consumption. It is a combination of Low Energy Adaptive Clustering Hierarchy (LEACH) protocol and optimal IDA* algorithms which includes three phases including formation of clusters, cluster head selection and rotating a cluster head. The proposed protocol has a very effective way to find an optimum path among nodes in clusters for improving energy efficiency. And also it determines the optimum path between clusters by supporting less number of hops with residual energy that reduces the delay for maximizing the network life time. To exhibit the efficiency of the proposed protocol in terms of balancing the power consumption and to improve the network lifetime, evaluate this approach with the Fuzzy, A* and LEACH, IDA* algorithms. The main popular applications are the development of networking protocol such as stack, hardware, operating systems, privacy and safety, localization, data aggregation and processing methods (Liu Danpu, Zhang Kailin & Ding Jie 2013).

The major design issue in wireless sensor is the power consumption. In order to reduce energy consumption and maximize the network lifetime we need a routing mechanism. In Routing, sensor nodes have the capacity to collect the path data from other nodes or BS which can be assigned by either fixed or wireless communication infrastructure .The problem with many algorithms is that they minimize the total energy consumption in the network at the expense of non-uniform energy drainage in the networks. Such approaches cause network partition because some nodes that are part of the efficient path are drained from their battery energy quicker. In many cases, the lifetime of a sensor network is over as soon as the battery power in critical nodes is depleted. Therefore for the designers and developers of protocols and applications for WSNS, the most important factor is power availability, since in sensor networks the battery life is considered as the network life (Akhtar, A et al 2010). Due to this situation, several novel algorithms have been proposed for the problem of routing data in sensor networks. These routing techniques have considered the uniqueness of sensor nodes, beside the application and design requirements. The main objective of routing mechanism is to find the optimum paths between the source and the destination for transmitting the data in order to achieve more power consumption in WSNs. Almost all of the routing protocols can be classified as data-centric, hierarchical or location based .Data centric protocols are query-based and depend on the naming of desired data, which helps to reduce many superfluous transmissions. Hierarchical protocols need to deploy the clustering nodes and cluster heads can do some data aggregation and save the power consumption. Location based protocols support the routing path and data can be transmitted to the desired location within the WSNs (Nurhayati 2011).Many of the protocols are used in clustering to improve the energy efficiency and prolong the network lifetime .For this ,more number of nodes are grouped into clusters and each cluster chooses a node as CH. Every node can transmit the data through its own cluster head to the other cluster heads or the base station.


In recent years, significant focus has been given to routing protocols in WSN due to the differences in network architectures and routing stipulations in various sensing applications [1]. In WSN, routing is needed to establish reliable communication paths between nodes and their BSs, and it significantly influences the power consumption of the nodes. Recently, many energy-efficient cluster-based routing schemes have been applied in various WSNs [2].

The LEACH-centralized (LEACH-C) protocol is an improved version of LEACH [3]. This scheme is meant to improve the CH allocation in LEACH by using a centralized control algorithm to distribute the CH nodes throughout the system. In LEACH-C, the BS computes the average residual energy of the nodes across the network and only allows the nodes with residual battery powers equivalent to the computed average residual energy to work as CH in each round. The LEACH with fixed clusters (LEACH-F) is another centralized variant of LEACH [4]. In LEACH-F, the setup phase is not required at all rounds, only the CH position rotates among the nodes. The data fusion oriented clustered routing protocol based on LEACH (DF-LEACH) is another variant of LEACH protocol [5]. DF-LEACH aims to facilitate both global energy efficiency and reduced energy dissipation at the CHs. In this scheme, data fusion is performed in a hop-by-hop mode among the CHs, before transmission to the BS.

The threshold sensitive energy-efficient sensor network (TEEN) protocol was proposed for WSNs as an event-driven cluster-based protocol [6]. TEEN employs two limits: a soft and a hard threshold. The hard threshold is aimed to decrease total data transport. Therefore, this limit enables the nodes to communicate their sensed data only when their observations correspond to the attribute of interest events. The soft threshold is intended to decrease total data transport by enabling the nodes to disregard data deliveries when variations in their observations are minor, or there are no variations. The adaptive periodic TEEN (APTEEN) protocol is a hybrid alternative of TEEN that merges the benefits of reactive routing and proactive routing systems [7]. In APTEEN, the nodes can react to changes in their monitoring environment and as well perform periodic data deliveries.


LEACH is a very efficient techniques for maximizing the network lifetime and also it is a better method for consuming more energy among the nodes in wireless sensor networks.LEACH is one of the most energy efficient hierarchical techniques in wireless sensor networks. Here ,the cluster nodes broadcast the data through only a cluster head and after that the cluster head communicates with other cluster heads with the help of routing mechanism .Finally the datas are sent to the base station. When the datas are broadcast to the base station more energy is consumed. The operations of LEACH can be executed by a number bf iterations. Each iterations contains two phases (i) setup phase and (ii) steady phase. In LEACH, the cluster heads are elected periodically, which ensures that the energy debauchery of each node in the network is relatively equal. In LEACH, nodes are taken based on independent decisions to form clusters by using a distributed algorithm.

Step1: CH selection and advertisement. To determine if it is its turn to become a CH, a set of nodes N, generates value r between 0 and 1 and compares it to the CH selection threshold, T(n). The node becomes a CH if the value is less than the threshold T (n). Then the node becomes a CH for current iteration. The threshold value is calculated based on the below equation given below that incorporates the desired percentage to become a cluster-head, the current iteration, and the set of nodes that have not been selected as a cluster-head in the last (1/P) iterations, denoted by N. The threshold value can be calculated by using equation given below.

T (n) p

(1 p)(r mod p 1 )


Where P is the cluster head probability and r is the chosen number between 0 and 1, T(n) is the threshold value.

Step 2: After the selection of the cluster head, it has to inform all the Non Cluster Heads( NCH ) in the sensor network and also the non cluster head nodes organize themselves .Every iterations cluster head can be chosen based on the distance from the base stations. Here the cluster head receives the data from its neighbours and also sends it to the base stations.

  1. Steady Phase

    In steady phase, data can be collected and transmitted to the base stations through the cluster heads. Here the nodes in the clusters send the sensing data to the cluster heads and after that the cluster heads transmit the sensing data to the base stations based on the time slots using TDMA [8].After a certain period of time, the cluster heads can be changed. At such a time the network will comeback to the setup phase .This continues until all nodes become cluster heads depending on the energy levels.


    Iterative Deepening A-star (IDA-star) Algorithm is the graphical search algorithm for finding the low cost between the source and the destination. It is a more efficient algorithm compared to other search algorithms. It can be used to reduce the memory usage and also it prolongs the network lifetime because a less amount of memory is needed for transmission.

    The evaluated function of IDA-star is as follows

    fcost(node) =gsocost(node)+hdecost(node) (2)

    where fcost(node) is the total cost of the path and gsocost is the source node cost(first node) and hdecost is the cost of the destination node (end node).The above evaluated function evaluated above is very useful for finding the optimal path to transmit the data.

    In generally, the IDA-Star algorithm is fully based on the depth first search techniques and it is to finds the optimal path very accurately and it takes the very less memory usage compared to A-star algorithms. The main difference from IDS is that it uses the f-costs (g + h) as the next limit and not just an iterated depth.In the following pseudocode, h is the heuristic function that estimates the path from a node to the goal.This algorithm mainly specifies two nodes, one is a starting node and othe one is a destination node.Initially,IDA-Star algorithm performs the depth first searches in serial manner .It is used for diffrent areas like Artificial Intelligence and Fuzzy Logics etc.IDA-star is to find the optimal cost in between the set of nodes.

    IDA-Star algrithm can be implemented as follows: begin: Start node S Declare f-cost=L

    Intialize the cost for each node L =h(S) L' = Loop

    P= It contains only S

    costlimit=(0,S,P) //It perfoms IDA-star for g L= L' repeat the steps

    $ returns{none,New-Cost-Limit=Q} // here it returns new cost value Start node:

    # returns (solution-sequence or none, new cost limit) D=DFS(intial cost,path,end node cost)

    If D>k,then k' = minimum(k' ,D) If P is the last node

    return P exit

    else for every leaves n of P is a goal or the last node P'=paths are formed by every succesor node n to P DFS(P')



    In this work,the network topology of a WSN is modelled as a directed graph G(N,E),where N contains a set of nodes and E is the edge between the nodes. Here the nodes are grouped into clusters.Some of the nodes are elected as cluster heads ,because these cluster heads only transmit data to the base station.This protocol is divided into rounds.In each round the cluster head must be changed .The process of finding the optimal path to the cluster heads and transmitting data from the cluster heads to the base station can be done by every iteration. In our proposed method,i)All sensor nodes are randomly distributed and divided into groups to form clusters ii)each node is assigned and assumed by the cost and also each node knows its position iii)Each cluster contains a set of nodes and these nodes are formed like the tree structure.iv)Within the clusters ,find the cluster heads based on the energy v)The cluster heads advertise the message to all of their neighbours Vi)Each node are transmits the data to the cluster heads in the optimal way because the data is transmited to cluster heads directly which means more energy is needed. so the nodes are die easily and also the network lifetime is reduced. The major issue in WSN is the network lifetime.Our proposed algorithm can minimise the energy consumption and increase the network

    lifetime significantly.In every iteration the cluster heads must be changed until all the nodes are visited. The overall lifetime is significantly extended by preserving the residual energy of all sensor nodes.The main objective of this work is, to extend the network lifetime of the WSN by optmising the path cost and also distributing the energy consumption as equal.To obtain this, LEACH and IDA-star algorithms are used..The method mentioned above is to be used in three important parameters i)residual energy ii)reduces the delay iii)less number of hop counts.

    In the new iterative deepening method , the cluster head sends the acknowledgement to all the nodes within the cluster.IDA-star algorithm is used to find the optimal path from the each node to the cluter head.IDA-star algorithm creates a tree structure in order to search the optimal routing path from a given node to the cluster head .The node can be evaluated by the follwing function,

    F(n)=N cost(n)+CH-1(n) (3)

    As a result,the largest values of F(n) can be chosen as an optimal node. The aim of our LEACH protocol is as follows: Some of the nodes select the cluster heads.These nodes are send the data to the cluster head but it is a long distance to transmit data to reach the cluster head.In this situation the optimal value of the node cost isto be found.It depends on the residual energy RE(n),delay (DE(n) of node n. Our proposed method is to avoid the longest distance for transmissions and also it should avoid the delay in order to improve the network lifetime. Fig.1 shows the flowchart for the proposed algorithm.It is the combination of LEACH and IDA * algorithms to determine the optimum paths between the clusters in order to extend the lifetime of the network.

    Figure 1: Flow chart of optimal cluster based on LEACH and EIDA


    Our proposed method is a very effective way to provide the balanced energy consumption and maximize the network lifetime.Our simulation results of the proposed methods are compared with the IDA-star algorithm and LEACH protocol for two different topographical areas. Here we have to select three routing criteria within the cluster such as residual energy,reducing the delay and the least number of hops by selecting the optimal path from the source node to then sink. Our LEACH based IDA-star algorithms performs well compared to other maximum lifetime routing schemes .All experimental results are shown in various network scenarios such as 50 to 400 nodes indicating both that LEACH and IDA-star algorithms give better optimal performance with respect to lifetime and energy onsumption of the network..Table 1:simulation parameters.

    TABLE 1 : Simulation parameter for the proposed protocol

    Network Area

    1000m x 1000m

    No of nodes


    Intial Energy


    Processing Delay

    40 µs

    Base Station Location


    Simulation Time

    900 sec

    Data size



    1 Mbps

    Trnansmiter Energy

    18 µj

    Receiver Energy

    9 µj

    The proposed scheme with existing LEACH and IDA-star algorithms.The proposed scheme evaluate with the metrics such as delay,Energy consumption,Remaining Energy,Number of hops. Fig. 2 and 3 shows the delay and energy of a WSN can be compared with three differnt approaches. Here,we clearly understand as the perfomance of proposed scheme is high. Fig 4 and 5 shows the packet loss is reduced and balance the energy consumption.Note that the above simulations are well performed and also nodes are highly balanced in terms of energy efficiency.


    The improved LEACH (Meena Malik and Yudhvir Singh 2013), IDA* searching scheme (Imad S. AlShawi, Lianshan Yan, & Bin Luo 2012) are taken in comparison to evaluate the performance of the proposed scheme.

    The improved LEACH that incorporates randomized rotation of the high energy cluster head position such that it rotates among the sensors in order to avoid draining the battery of any one sensor in the network. In this way, the energy load associated with being a cluster head is evenly distributed among the nodes. The LEACHs function has divided into rounds. Each round begins with a set up phase when the clusters are organized and then it followed by a steady state phase where various frames of data are transferred from nodes to the cluster head and base station. LEACH guarantees not only the equal probability of each node as cluster head and also the relatively balanced energy consumption of the network nodes.It causes routing overhead due to the control message exchange. A-star search algorithm is a widely used graphic searching algorithm. It is also a highly efficient heuristic algorithm used in finding a variable or low cost path. It is considered as one of the best intelligent search algorithms that combines the merits of both depth-first search algorithm and breadth-first algorithm. A-star path searching algorithm uses the evaluation function to guide and determine the order in which the search visits nodes in the tree.

    Energy consumption: Energy consumption for packet transmission from source to destination is determined by the average energy that is spent to deliver a packet successfully from a source node to the destination. If every hop along a path have same energy level and same energy consumption for sending and receiving the key then it is essential to consider hop- per-delivery to determine the energy consumption. End-to-end Delay: End-to-end Delay is the average time taken by a data packet to arrive in the destination. It also includes the delay caused by route discovery process and the queue in data packet transmission. Only the data packets that successfully delivered to destinations that counted.


    Figure 2 shows the energy consumption levels of sensor nodes for EIDA*, LEACH and proposed EIDA* with LEACH protocols. As it can be clearly observed, EIDA* with LEACH achieves energy equalization and showing a better performance in energy consumption, whereas the sensors in LEACH and EIDA* have largely varying levels of energy. Because LEACH does not address the hot spots of the network, no lifetime equalization mechanism is involved. In EIDA*, when a CH candidate is not selected as a CH node in a round, it doubles its probability of selection. It increases the energy consumption as well. Our proposed approach is to reduce the energy consumption for all noedes sending ,receiving and forwarding the data packets.

    Fig 2.Energy Consumption

    End to End Delay

    Figure 3 shows the End to End Delay metric for analysing paerformance of proposed and related schemes. The scenario of 100 nodes shows that, when the no of nodes increases, the proposed scheme outperforms for end to need delay as compared with EIDA* and LEACH because it selects the optimal cluster heads for managing routing efficiently. As static routes are defined we get minimum delay for EIDA*. As changing network topology LEACH degrades its performance for end to end delay. Every time when the packet receives at the node, it checks the routing table and forwards it logically. As the number of nodes increases, end to end delay also increases. This is mainly because the packet size increases drastically as the no of hop increases.

    Fig 3.End to End Delay

    Packet loss

    Figure 4 shows the packet loss of three protocols such as IDA* wit LEACH, LEACH and IDA*. IDA* with LEACH performs better than LEACH and IDA* for packet loss because it selects the optimal cluster heads for managing routing efficiently. As static routes are defined, IDA* and LEACH increase packet loss.

    Fig 4.nodes vs packet loss CONCLUSION

    WSNs are operated by battery energy.So energy plays the most important role in the WSN.One of the main characteristics of the network is the lifetime.In order to achieve this by balancing the energy consumption because the unbalanced energy consumption is the inherent problem in a WSN and also reducing the distance for transmitting data from the source node to the destination node.It can be achieved by our new proposed algorithm by using the combination of LEACH and IDA-star algorithm.Our proposed method is to select the optimal path from the source to destination by using residual energy,the least number of hops and reducing the delay.The performance of our new method is compared to other methods under the same metrics.Our simulation results also give a better performance for improving the network lifetime sucessfully.


    1. Khalaf, O. I., & Sabbar, B. M. (2019). An overview on wireless sensor networks and finding optimal location of nodes. Periodicals of Engineering and Natural Sciences, 7(3), 1096-1101.

    2. Wang, Q., Liu, W., Wang, T., Zhao, M., Li, X., Xie, M., … & Liu, A. (2019). Reducing delay and maximizing lifetime for wireless sensor networks with dynamic traffic patterns. IEEE Access, 7, 70212-70236.

    3. Sharma, H., Haque, A., & Jaffery, Z. A. (2019). Maximization of wireess sensor network lifetime using solar energy harvesting for smart agriculture monitoring. Ad Hoc Networks, 94, 101966.

    4. Sangaiah, A. K., Sadeghilalimi, M., Hosseinabadi, A. A. R., & Zhang, W. (2019). Energy consumption in point-coverage wireless sensor networks via bat algorithm. IEEE Access, 7, 180258-180269.

    5. Robinson, Y. H., Julie, E. G., & Kumar, R. (2019). Probability-based cluster head selection and fuzzy multipath routing for prolonging lifetime of wireless sensor networks. Peer-to-Peer Networking and Applications, 12(5), 1061-1075.

    6. El Alami, H., & Najid, A. (2019). ECH: An enhanced clustering hierarchy approach to maximize lifetime of wireless sensor networks. IEEE Access, 7, 107142-107153.

    7. Balaji, S., Julie, E. G., & Robinson, Y. H. (2019). Development of fuzzy based energy efficient cluster routing protocol to increase the lifetime of wireless sensor networks. Mobile Networks and Applications, 24(2), 394-406.

    8. Thangaramya, K., Kulothungan, K., Logambigai, R., Selvi, M., Ganapathy, S., & Kannan, A. (2019). Energy aware cluster and neuro-fuzzy based routing algorithm for wireless sensor networks in IoT. Computer Networks, 151, 211-223.

Leave a Reply

Your email address will not be published. Required fields are marked *