Energy Efficient Clustering Protocol for Sensor Network

Wireless Sensor Network (WSN) typically comprises of large number of sensor nodes [1]. These sensor nodes are spatially distributed in random or uniform manner to form a network often operated with dynamic topology. These networks are widely used for applications that require constant monitoring of any environmental phenomena or real-time reporting of any special event and transmit the sensed data to Base Station (BS). The flexibility and cheapness of using WSNs to sense and communicate make them favorable for a wide spectrum of real-time applications.

Deployment of sensors is usually done in a random fashion as they exhibit the capacity of autonomously organizing themselves into a wireless sensor network. In order to increase the utility of sensors, the deployment can also be done in pre-defined location to ensure optimal coverage and connectivity. After deployment, sensors form a dynamic topology of the network thus offering ease of deployment even in inhospitable regions. Due to these advantages of sensors, it is almost inevitable that they are being used heavily in today’s world. Sensors offer many advantages in terms of their small size, inexpensive nature and ease of usage. However, these advantages come with many other drawbacks such as limited battery lifetime, restricted memory and processing power. Energy consumption is one of the major problem in battery operated WSN. However, majority of energy consumption occurs (around 98%) due to transmission of messages over long distances [2]. Transmission of messages in WSN can be performed either through direct, multi-hop or cluster based routing. Direct communication consumes very high energy when distance between sensor nodes and the Base Station (BS) is large. Multihop based communication increase number of transmissions and receptions between sensor nodes and the BS and hence consumes high energy. Moreover, nodes near the BS forward packet on the behalf of other nodes lying far from the BS quickly deplete their energy and this phenomenon results in cascading effect and further decreases network lifetime. It has been proved in Literature by a number of researchers that cluster based communication effectively utilize network bandwidth, reduce overall transmission distance of nodes and helps in reducing energy consumption and enhancing network lifetime. Clustering partitions all the nodes into groups called clusters in which one of the node is selected as Cluster-Head (CH). Cluster Head performs the tasks of data aggregation after collecting the data from member nodes to minimize the redundancy which helps in conserving energy.

Clustering can be classified in two types: Static and Dynamic [3]. In Static Clustering, Clusters that are formed initially doesn’t change throughout the network lifetime. This type of scenario avoids re-establishment of clusters. However, Static Clustering results in selection of un-optimal nodes as CH. Dynamic Clustering suits best to the requirement of homogenous networks where task of Cluster Heads is shifted from one node to another node after certain amount of time.

However, a clustering protocol must takes into consideration some important factors before designing the clustering protocol. These parameters include: placement of nodes within a network, selection of Cluster Head and total transmission distance involved in transmission from the nodes to the BS.

Placement of nodes within a network is very crucial because denser deployment of nodes increases the redundancy of information in the network and if nodes are sparse in the network then it may left some portion of network uncovered and also increase the transmission distance of messages in the network. Also, data loss in transmissions may affect the information received at the base station due to lack of redundancy in data.

Cluster-Head (CH) Selection can be done in a number of ways. Broadly it is the frequency with which a protocol runs CH selection code and the node’s favorability to be chosen as a CH in the network. Frequency of CH selection can be controlled by putting a threshold on parameters such as the node’s residual energy. Another factor i.e. node’s suitability to be chosen as CH can be determined on the basis of many facets like the number of nodes that are present in its neighborhood and the sum of distances to these nodes and so on. Because a CH carries the data on behalf of its member nodes, the distance to these member nodes count as an important parameter in CH selection. Additionally if the node is placed more central in its cluster, it automatically results in lesser intra cluster distance ultimately leading to lesser drainage of batteries associated with nodes. Likewise other factors have their own similar reasons.

Total transmission distance involved in the transmissions. It is not only the intra-cluster distance that matters; energy dissipation is also heavy when there is large CH to BS station distances. Often BS is located on the boundaries of network or even farther which causes heavy drainage in energies of CH nodes which lays the foundation for reselection of CHs in the protocols when criteria lies in the threshold of CH’s residual energy as explained previously.

As a result, in this paper we propose dynamic clustering protocol for homogenous WSN by taking into consideration all the above stated parameters. Our protocol reduces the transmission distance significantly and helps in increasing network lifetime. Further, this paper explores three types of network distribution: Poisson distribution, Uniform Distribution and Random Distribution in order to evaluate which suits best for coverage of Wireless sensor Networks. Rest of this paper is organized as follows:

Section II contains related work in this area. A novel protocol is proposed in section III. Section IV demonstrates the simulation results and comparisons of proposed protocol with state of art protocol. Conclusion is presented in section V.

• II.    Related Work

In recent times, a number of clustering protocols have been proposed by various researchers for wireless sensor network with their own advantages and drawbacks. In this section, we discuss a handful of them that particularly focus on decreasing energy dissipation and increasing overall lifetime of the network. Later on, this section describes the requirement of developing a new protocol when lots of clustering protocols for WSN still exist in the literature.

Low Energy Adaptive Protocol (LEACH) [4] was the first dynamic clustering protocol proposed for Wireless Sensor networks. Authors used the conventional way of clustering i.e. randomly select some of the nodes as CH. In order to evenly distribute load and balance energy dissipation among nodes, a node decides whether to act as a CH or not on the basis of number of CHs required and number of times that node has been CH so far. However, location of nodes is not taken into account while selecting CHs so there was high possibility that neighboring nodes may elect themselves as CH. Moreover, residual energy of nodes was not taken into consideration.

To tackle the problem of randomized CHs and residual energy, LEACH-C [5] was presented where CHs are elected at optimal locations to ensure coverage of entire network. Authors implemented centralized LEACH-C where BS decides which node should act as a CH on the basis of information sent by all nodes regarding their location and energy levels to the BS. However, this increases lots of data transmission in the direction of the BS and congest transmission lines.

Weighted Clustering Algorithm (WCA) [6] further tried to break the limitation of LEACH-C by using a weight based approach of clustering. Weights of each node are evaluated on the basis of several parameters such as number of neighbors, average distance to neighbors, mobility factor and cumulative time during which the node has acted as a CH. WCA designates a node as CH on the basis of weights that are assigned to each node, the node having minimum weight is designated as a CH. WCA biggest advantage is flexibility of adjusting the multiplicative factors of these parameters depending upon the requirements of a particular application. Moreover, reselection of CH can be deferred until the energy of the CH is declined to a minimum level but weight assigning process and dynamic clustering added overhead in the algorithm and consume lots of energy.

To reduce the overhead of dynamic clustering, EEPSC (Energy Efficient Protocol with Static Clustering) divided the whole network in form of static clusters [7]. In the first round, a temporary CH is chosen randomly, but in subsequent rounds, current CH chooses minimum energy node as temporary CH for next round. The temporary CH collects the data regarding energy levels from all the member nodes. On the basis of this information, it selects the node with maximum energy as CH. An Enhanced version of EEPSC (EEEPSC) came into view after founding that EEPSC often selected nodes located near boundary as CHs. This causes an increase in communication overhead of nodes located on opposite boundary [8]. Enhanced EEPSC considers spatial distribution of nodes and their residual energy to select CHs.

Both Energy Efficient Protocol with Static Clustering (EEPSC) and Enhanced EEPSC (EEEPSC) selected temporary CH that adds overhead to both the protocols and hence Front Leading Energy Efficient Cluster Heads (FLEECH) [9] came into picture.

FLEECH also divided the network into unequal clusters, starting from BS at the centre and reducing the size of clusters in outward fashion. Like LEACH-C, all nodes forward their residual energy and distance (from the BS) to the BS so that the BS can choose appropriate nodes as CH. This increase lots of traffic in direction of the BS as in LEACH-C. Although, the size of message is shorter than LEACH-C message, still these packets contributed to increase the traffic.

Improved energy aware distributed clustering protocol (EADC) was proposed in 2016 to extend the network lifetime in different scenarios.

It is clear from the above discussion that some of the clustering protocols suffer from randomized clustering, other suffer from the drawback of huge traffic that ultimately leads to heavy energy dissipation. Taking into consideration all the above points, we implement a new protocol that effectively handles the above stated points and propose an energy efficient clustering solution for WSNs.

• III.    Proposed Approach

In this section, we propose an energy-efficient clustering approach to maximize lifetime of Wireless Sensor Networks.

Network coverage plays a very crucial role in energy dissipation of the network because deployment of nodes affects quality and coverage of sensing thus making it a crucial factor from the perspective of Quality of Service (QoS). In node denser areas, data redundancy will increase. Although, certain amount of redundancy is helpful in reducing the effects of Data loss during transmission but it also results in more energy consumption during aggregation and compression of the data. On the other hand, intra-cluster average distance will increase for sparser nodes and this will ultimately result in increase of energy consumption. Moreover, with sparser nodes, effects of data loss may increase.

Node deployment can be done either by deploying sensor nodes at pre-defined locations in the network or by using probability distributions (random, uniform and Poisson) based deployments. Former case is not possible when deployed in remote areas. Therefore, we need to focus on second approach instead.

Random distribution of nodes facilitates ease of deployment and scalability. Random distribution is used in unstructured network applications such as battlefield surveillance, etc.

In uniform distribution, nodes are uniform distributed over a region. The probability distribution function of uniform distribution is given as [10]:

f (x) = —-— for A < x < B v ’ B - A

where, A is location parameter and B-A is scale parameter. For standard Uniform Distribution, A = 0 and B=1.

Poisson distribution is used when number of events occur within a given time slot. In Poisson distribution, both uniformity and randomness are taken into consideration while deployment of nodes [11]. It has been stated in the literature that Poisson distribution offers optimal coverage of network [12-13]. The Probability distribution function when a sensor node exists at point (x,y) is given as[14]:

f(x, y )=N (2)

A

Here, N is the total number of sensor nodes deployed and A is the deployment field. In order to compare these distributions, network parameters are set as follows:

Table 1. Simulation Parameters

Parameters	Values
Deployment Region	100*100
Transmission Range	50
Number of Nodes	40 to 100 in steps of 20
Initial Energy	0.5J
Message Size	2000 bits
Locate of Base Station	(50,50)

All sensors nodes are homogeneous in nature and deployed in same region to analyze performance of various distributions. Additionally, all nodes possess same transmission range and this sensing range is symmetrical and circular in nature. We have simulated the scenarios in MATLAB.

Fig.1. Node Deployment using Random Distribution

Fig.2. Node Deployment Using Uniform Distribution

Fig.3. Node Deployment Using Poisson Distribution

Simulation results clearly demonstrate the fact that Poisson distribution provides better coverage in comparison of Random and Uniform distribution.

As a result, for the implementation we are assuming a network that exhibits the following properties:

• •    Sensors nodes of the network are homogenous and immobile in nature.

• •    Position of Base station is fixed and it is not energy constraint.

• •    Nodes sense the environment at fixed rate.

• •    Network nodes are deployed using Poisson distribution.

Overall functioning of proposed protocol is shown in the flowchart depicted in figure 4.

Start

Check if node degree<20

Find M nodes out of total N ncdesonthe basis of node concentration and >=50K current energy

Selection of CHs from the set of eligible CHson the basis of farthest inter-CH distance and node Centrality

Non CH nodes choose their ne are st CH

Check for next nearest CH

Yes

A

Choose thisnodeas

CH

Fig.4. Overall Functioning of Proposed Protocol

Proposed protocol is divided into 2 phases named as:

• A.    Cluster Head Selection phase

• B.    Cluster Formation Phase

Details of all the phases of proposed protocol are as given below:

• A.    Cluster Head Selection Phase

In Cluster Head Selection Phase, first step is to determine optimal number of Cluster Heads. This is a very crucial parameter because optimal number of CHs helps us to achieve minimum energy dissipation, load balancing as well as minimum average distance while maintaining network coverage and connectivity. In order to make the balance, Dahnil et. al. in [15] deduced the below mentioned formula:

Here k is the optimal number of clusters per round, N is the total number of nodes, R is the transmission range, d is the distance of CHs from the BS, εfs and εmp are the energy dependent factors.

The possible candidates for CH (say M) are determined on the basis of following parameters:

• 1.    Node Concentration of a sensor node if elected as CH

• 2.    Current residual energy of network nodes

Node Concentration is the number of nodes that are present in transmission range of a node.

IN = {n\nd < Rt }          (4)

N is the Node Concentration of the candidate CH. Distance of neighbor nodes from candidate CH (nd) should be less than equal to node’s transmission range.

Ideal node concentration is given as:

N= 5.1774log П         (5)

According to above equation, if we maintain 5 cluster per 100 nodes, then atleast 20 member nodes are needed in a cluster.

In our network, if any node has 20% of network nodes within its transmission range and its minimum energy is above certain threshold then that node became possible candidate for CH.

After determining possible candidates for CH, final selection of CH is done on the basis of 2 parameters:

• 1.  Node Centrality

• 2.  Distance among CHs.

Node Centrality Factor (NCF) evaluates the candidate CH on the basis of how central the node is in its cluster. To evaluate this, average distance of CH to its possible member nodes is found. Relation between Node Centrality and distance is given as:

NCFa

Davg

Where D avg is the average distance of nodes from their CH. According to the above mentioned equation, minimum average distance suits best to our requirement. This has been illustrated in figure 5 & 6.

Fig.5. High Node Centrality

Fig.6. Low Node Centrality

Apart from this, while finalizing, the distance between possible candidates of CHs is also taken into account.

As a result, possible candidates who have farthest distance among themselves and high centrality i.e. minimum average distance from surrounding nodes are chosen as final CHs in our scheme.

Subsequent CH selection can be done on the basis of remaining energy. Energy threshold is set as the minimum energy required to carry out the responsibilities of every round or after the selection of a node as cluster head, it will remain at its designation till 50% of its initial energy has been reached.

• B.    Cluster Formation Phase

After finalization of CHs, members of CHs are determined on the basis of

• 1.    Ideal degree of CH

• 2.    Distance of node from CH

Nodes will determine their possible CH by calculating the distance of each node to each of CHs and assign the node to that CH with which its distance is lowest while maintaining the ideal degree. If a CH has reached its highest ideal degree limit then we look for second closest CH for any particular node. This method is followed for each of network node until all the nodes comes under the territory of one or another CH.

Our proposed method differs with LEACH in following ways:

• •    CH selection is not randomized. Farthest nodes with ideal degree are chosen as CH in case of proposed protocol. This avoid LEACH drawback of choosing nearby nodes as CH.

• •    Apart from this, nodes with minimum average distance are chosen as CH in case of proposed protocol.

• •    Optimal numbers of CHs are chosen using the formula stated in literature.

• •    CH ideal degree is also taken into consideration by proposed protocol for evenly load distribution.

• IV.    Results &  Discussion

  To evaluate the performance of proposed protocol, we simulated proposed protocol in a network of 100 nodes deployed with Poisson distribution between (x=0,y=0) and (x=100,y=100). BS is placed at (x=50,y=50). Initial energy of nodes is assumed to be 0.5J. Size of message is 2000 bits long.

For our simulation, radio based energy dissipation model is used.

Free space energy dissipation, εfs = 10 pJ/bit/m2 and amplifier energy, εmp = 0.0013 pJ/bit/m4 for a message of l bits at a distance of d.

• A. Analysis of Simulation Results

A set of simulations were conducted to validate our theoretical claims of proposed protocol on the basis of impact of different distribution on the distance, distance of nodes from the CH and by comparing the proposed protocol with LEACH.

• •    Impact of Different Distribution on the distance

Fig.7. Deployment with Poisson, Uniform and Random Distribution

Figure 7 demonstrates the average distance of nodes to their respective CHs in case of different distributions. It is clear from the figure that average distance of nodes from their CH is lesser in case of uniform initially. However, as the number of nodes increases in the network Poisson distribution perform much better than Uniform and Random distribution. Since, Wireless Sensor Networks comprise of large number of sensors due to fragile nature of sensors so Poisson distribution remains the best possible distribution for them.

• •    Distance of nodes from CH

It is clear from the figure 8 that distance of nodes from their CH is lesser in proposed protocol because it chooses CHs on the basis of minimum average distance from surrounding nodes. Apart from this, placement of CHs is done in a more distributed manner by selecting farthest nodes as CH. Therefore, farthest nodes as CH and minimum average distance from surrounding nodes helps to minimize the distance of nodes from their CH

Fig.8. Distance of Nodes from CH in Proposed Protocol and Protocol with Random CH

Equation 7 also clearly proves the point that distance is a very critical parameter in sensor networks because energy dissipation is directly proportional to square of distance upto the certain distance threshold and as distance reaches above threshold energy dissipation increases in power of 4 of distance. Therefore, even small decrease in transmission distance of messages reduces energy dissipation drastically and increase network lifetime substantially.

Et (1,d) = lE^ +1 *8,6 *d2 ifd < doEt (1, d ) = lEe^ +1 * S, * d 4 ifd > do where,

d

Ef,

---and E = 1E , r         elec

\ ^£ mp

In above equation E t and E r are the energies dissipated in transmitting and receiving a message of l bit over a transmission distance of d.

E_elec = 50nJ/bit is the electronics energy, ε fs = 10pJ/bit/m² is the free space energy and ε mp is 0.0013pJ/bit/m⁴ is the energy used by amplifier.

Distance threshold is denoted by d o .

• Comparison of Proposed protocol with LEACH

Fig.9. Distance of Nodes from CH in Proposed Protocol and LEACH

It is clear from the figure 9 that distance is lesser in proposed protocol because CHs in our protocol are more evenly distributed over the network and they are elected on the basis of minimum average distance of surrounding nodes from their CH.

Possibility of electing neighboring nodes as CH was one of the major pitfalls with LEACH. This type of deployment also increases the transmission distance of nodes lying far from the elected CHs if there is no CH in their surroundings.

Proposed protocol addresses this issue in a very effective manner by selecting CHs with farthest distance so there is high possibility that nodes all over the network can find a CH in their territory.

• V.    Conclusion

In this paper, a novel clustering protocol is presented based on inter-cluster and intra-cluster distance. The proposed protocol works upon the solution space of those nodes that have ideal degree of member nodes and 50% or more current energy. Further, final CHs from this solution space is chosen on the basis of based on farthest distance between any two candidate CHs and average distance of surrounding nodes from CH. Selection of such nodes provides better spatial division of clusters. This division supports optimal coverage of nodes with Poisson distribution. Different distribution (Uniform, Random and Poisson) are evaluated and simulation results support Poisson distribution over other two distributions.

Proposed protocol is also compared with random CH and LEACH protocol and results show that transmission distance in proposed protocol is much lesser than the other two. Reduction in transmission distance will ultimately help to minimize energy consumption and maximize network lifetime.

Further improvement can be done by exploring the solution space created in the methodology. Some heuristically search on location based selection of nodes can be done to bring advancement in clustering technology.