An Improved Energy Aware Distributed Clustering Protocol for Wireless Sensor Networks

Wireless sensor networks usually are designed for harsh environment applications where human intervention is not possible such as forest fire, wild life monitoring, tunnels, bridges, coal mines etc. to name a few. Such data gathering applications require sensors to be deployed in large numbers and the data to be sensed from all locations. However, these sensor nodes are energy limited. In many applications the base station (BS)

is usually placed far away from the sensing field and the data is gathered periodically by the BS. In order to address the energy constraint, large amount of research work has been carried out in the last decade [1-3]. For such continuous monitoring networks, clustering with hierarchical topology is successful [4-7]. It is exhibited that clustering the network offers greater lifespan with an increase of about 2-3 times than the network with direct data transmission [8].

There are many other advantages of using clustering protocols in data-gathering networks. As dense networks involve large volume of traffic among the sensors, it leads to interference problems. In such scenarios, grouping the sensors is extremely beneficial. Further, it minimizes the number of long distance transmissions and results into saving of the energy. In clustering, cluster heads (CHs) coordinate the activities of its member nodes and the normal sensor nodes (cluster members) remain in sleep mode, which further leads to energy saving [9]. This is possible because CHs execute TDMA scheduling for its member nodes [7, 10]. Also clustering facilitates data aggregation at cluster head. Thereby the number of data transmissions further minimizes, and the network lifetime prolongs [9].

The data transmission in clustering protocols occurs in two steps, one is within the clusters i.e. intra-cluster and another is between the clusters and the BS i.e. intercluster. In addition, the communication in a wireless sensor network clustering protocol can be taken up either by employing direct transmission through single hop, or using multi-hop routing [11, 12]. For data transmissions within the cluster i.e. from member nodes to CH, most of the clustering protocols use single hop communication, as the transmission distance is relatively short e.g. LEACH [7], LEACH-DT [10], HEED [13] etc. Multi-hop communication between the sensor nodes and the cluster head is promoted when the propagation loss exponent is high as in buildings, factories, or dense vegetation regions [1]. Direct transmission also has its benefits in saving of energy as the radio dissipates energy in not only transmission but also in reception. But it is used only when the transmission distance is within certain threshold distance only [14]. This is, because the energy expense increases according to the fourth power of the distance [10,  15]. There are number of clustering protocols developed which propose multi-hop communication for achieving    more     energy-efficient    inter-cluster communication viz. Multi-hop LEACH [16], EADC [17], EDUC [18].

Many research works has defined the network lifetime to be when first node is dead (FND). The idea behind this assumption is that it is important that all the nodes of the network die out approximately at the same time in order to avoid early loss of sensing coverage, and likely partitioning of the network [7, 10, 13]. But, as the lifetime requirement is application-specific, considering first node dead as the lifetime definition is not a generic one [19]. There are different types of sensor network’s applications [20] and therefore it is better to evaluate the lifetime of the network at different stages viz. the time when certain percentage of nodes fail [21].

In wireless sensor networks, one of the primary concerns is maximization of network lifetime because after the network becomes dysfunctional, significant amount of energy should not remain in the nodes, otherwise it is wasted. In a clustering protocol, a CH is heavily burdened as it is responsible for execution of various tasks such as cluster formation, data aggregation, data transmission and relaying. Cluster heads therefore consume more energy as compared to non-CH nodes. For single hop communication, cluster heads which are far away from BS drain out their energy primarily because of the long distance transmission. But when using multi-hop communication in clustering protocols, then, the cluster heads near the base station deplete their energy quickly because of the extra burden of traffic relaying. This unbalanced communication load results in energy hole or hot spot area. Due to this, data required from all corners may not be obtained and the network performance is ultimately affected. Thus, the energy consumption among all the network nodes must be balanced. In clustered networks, therefore, there is inevitable problem of energy imbalance among sensor nodes [18]. Recently, lot of research has been carried out to address energy imbalance and mitigate energy hole problem for clustered WSNs. A number of strategies such as using node mobility [22, 23]; mobile sink [24-27]; hierarchical deployment [28]; nonuniform clustering [18,29]; data compression and traffic aggregation [27, 30]; node distribution [22, 31, 32]; etc. have been proposed for solving energy imbalance problem.

In this paper, an attempt has been made to improve network lifespan of an energy-aware distributed clustering protocol EADC used in continuous monitoring applications [29]. The EADC employs uniform clustering algorithm to mitigate the energy imbalance. The key idea of proposed scheme is during selection procedure of traffic relaying. The energy cost involved in relaying is directly considered as the metric for selecting one of the feasible nodes as a relay node instead of only residual energy and the cluster member count information used in the EADC. The performance of the proposed protocol is compared with the existing energy aware distributed clustering protocol. The proposed scheme poises the energy consumption of the nodes in the network for uniform distribution as well as for non-uniform distribution.

The remainder of this paper is organized as follows: Section 2 reviews the related work and Section 3 presents the network model. Section 4 describes the proposed protocol operation in detail and Section 5 analyzes the protocol characteristics. Section 6 gives the simulation results of our sensor deployment schemes and compares it with existing protocols. Finally Section 7 concludes the paper.

• II.    Related Work

Earlier research work undertaken in the area of clustering algorithms has been primarily based on the rotation of role of cluster heads in every round, and selecting cluster heads with more residual energy in order to enhance the lifespan of the network. A pioneer protocol, low-energy adaptive clustering hierarchy (LEACH) protocol [15] and its many variants such as LEACH-DT [10] or a multi-hop variant of LEACH, called as M-LEACH [1] have been developed in the past. The LEACH protocol assumes one-hop communication between the nodes and to the base station. This makes it unsuitable for large-scale networks. Also the CH selection is probabilistic without even considering the residual energy of the nodes. A hybrid energy-efficient distributed (HEED) clustering algorithm is proposed in [13], which select cluster head according to not only the node residual energy but also intra-cluster communication costs. It uses multi-hop communication among the cluster heads for inter-cluster communication. It is successful in prolonging the network lifetime but not so effective in balancing the communication load as node’s closer to BS still die faster. Another protocol available is distributed energy efficient clustering algorithm (DEEC) [33], wherein cluster heads are chosen by a probability which is based on the ratio of residual energy of a node and the average energy of the network [33]. In all these energy-efficient clustering schemes, although periodic rotation of cluster head function sees that nodes runs through energy more evenly, but it is not effective in solving the energy consumption balancing issue of many-to-one data gathering wireless sensor networks.

In the last few years, researchers have explored the strategies to extenuate the energy imbalance problem in hierarchical (cluster-based) WSNs. Many protocols have been developed which addresses this issue using nonuniform clustering technique [34]. They all attempt to organize the nodes into clusters of unequal size with the clusters nearer to BS to be of small size than those that are more distant from the BS in order to relieve the nodes of the extra burden of traffic relaying. Our focus in this paper is on equalizing the energy consumption in the network through uniform clustering only.

Also there are many published works which utilize equal size clustering to balance the energy consumption in sensor networks. A balanced clustering algorithm (BCA) is promoted for irregularly deployed sensor networks in [35], which uses equal size clustering to improve energy efficiency and balance energy consumption in non-uniformly deployed sensor networks. The cluster head selection is based on the node density parameter. It attempts to minimize redundant sensing and transmissions. By using the sensing population information, CHs turn the redundant nodes into sleep mode, and results in prolonging the network lifetime.

In [36], the authors proposed an energy efficient routing algorithm (ERA), which conserves energy during cluster set up phase and also facilitates data routing through maintaining a virtual backbone of CHs. The selection of CHs is based on residual energy and the clusters are formed with non-cluster heads nodes joining the CH based on residual energy and distance to the BS. Further in it, relaying load of the CHs is balanced with their residual energy. For evaluation, random and grid deployment scenarios have been considered and performance metrics used are network life time, energy consumption, power imbalance factor, and data aggregation.

Another article [37], forms clusters of even sizes to equalize energy consumption among nodes. The authors in this propose a decentralized energy efficient hierarchical cluster based routing algorithm. For cluster head selection, the parameters considered are energy consumption, the actual distance the data traverses to reach the BS, and the adjustment degree of adjusting the intra-cluster and inter-cluster energy consumption. It controls the number of control message exchanges while constructing routing tree and thereby saves energy.

• III.    Preliminaries

This section presents the network model, the energy model and the data aggregation model used in the paper.

• A.    Network model

The network comprises of randomly deployed N number of sensor nodes in an M x M area. The nodes are energy heterogeneous i.e. different initial energy is assigned to the sensor nodes. The BS is far away from the sensor field and its location is assumed to be known to each node. The nodes use power control to adjust the transmission power depending on the transmission distance. The nodes are not location aware. The cluster heads can transmit their data directly with BS depending on their distance to the BS.

• B.    Energy model

The transmitter consumes energy in running the radio electronics circuitry and the transmit amplifier circuitry, whereas, the receiver’s energy consumption is only in radio electronics part [7, 15]. Also, depending on the transmission distance, both the free space εfs and multipath fading εmp channel models are used. If the distance is less than a threshold level, the free space model is used; otherwise the multipath model is used. When transmitting the l-bit data to a distance d, the radio expends according to (1).

E tX ( l , d ) = E tx - e,ec ( l ) + E tX - amp ( l , d )

= <

^l   E elec

l  E elec

+1 * £fs * d2, d < dth

^{+ l} * ^£ mp * ^d 4 , ^d ^ ^d th

When receiving the l-bit data, the radio expends according to (2).

^ERX ^{( l} ) = E RX - elec ^{( l} )

= IE , elec

• C.    Data aggregation model

In the present work, the infinite compressibility model is used for data aggregation [4, 15]. It is assumed that cluster head collect the data from its member nodes and aggregate it into a single packet of fixed length irrespective of the number of received packets.

• IV.    The improved EADC Protocol Mechanism

The clustering method used is similar in operation to EADC protocol [17]. After deployment, the nodes first compute its distance from BS. The signal broadcasted by BS is listened by all nodes. On the basis of the received signal strength, each node approximates its distance to BS. The performance of the protocol is tested in terms of number of rounds it can deliver the sensed data to the BS. Each round comprises of set-up phase in which cluster is formed and steady state phase in which data transmission takes place. The set-up phase is further sub-divided into three sub-phases of durations T₁ , T₂ and T₃ respectively. During T₁ , each node broadcasts a Node_Msg , which contains its residual energy along with its id. All the nodes which are in its radio range, receive the Node_Msg from all its neighbors. Each node then works out the average residual energy, Eavg_res of the cluster according to (3).

Eavg_res = (E J=1 sj.E )/ nb (3)

where s j is one of the node, s j . Er is the residual energy of s j , and nb is the number of neighbors. After T 1 has timed out, the next sub-phase i.e. cluster head competition phase of duration T 2 commences. In this subphase cluster heads are elected. Each node calculates its wait time for broadcasting the Head_Msg according to (4). Here, t represents the delay time of a node to compete for being cluster head.

f E

avg _ res

t = <

E r

T2Vr,

r

avg _ res

T V

T 2 V r ,

r

E avg _ res

where E_r is the current residual energy of the node; V_r is a real value randomly distributed in the interval [0.9, 1], which is used to reduce the probability that two nodes send Head_Msg at the same time [17]. If any node does not receive any Head_Msg , it broadcasts a Head_Msg within competition range R c , advertising itself to be cluster head. The improved EADC scheme uses the same competition range to produce equal size clusters.

After cluster head competition sub-phase, wherein cluster heads are chosen, cluster formation sub-phase of duration T₃ commences. In this sub-phase, the non cluster head nodes join the nearest cluster head. These noncluster head nodes send the Join _ Msg and the corresponding cluster head receives the Join request and forms the clusters. In the Join_Msg , the node gives its id and its remaining energy. The cluster head then prepares and broadcasts a TDMA Schedule_Msg containing the information of cluster member’s data transmission. Thus each member node can remain in sleep mode until their time of data transmission. The sensor nodes energy consumption thus reduces by turning off their radios.

After the network is setup as clusters, steady state phase begins. In this phase, data transmission takes place. The data transmission occurs in two steps. In step 1, the member nodes transmit their sensed data according to the schedule to their respective cluster heads. This transmission is single hop and is known as intra-cluster communication. The cluster head after receiving the sensed data from its member nodes, computes the aggregated data. As the data sensed by cluster members is correlated, the incoming data is aggregated into one packet and stored by the CH node. This task of intracluster communication is carried out in all the clusters of the network.

The second step of data transmission is called intercluster communication. The cluster heads can transmit the data packet to the BS either directly, or through relaying. This decision is based on the distance of the CH to the BS. If the distance of a cluster head to the BS is less than threshold distance ( dist_th ), then direct transmission is executed, otherwise the CH communicates through other CHs which acts as relay node. For inter-cluster communication, the selection of next hop node ( relay ) is crucial.

In original EADC protocol, for relay node selection, each CH s_i computes parameter relay using (5) to choose sj as its next hop node and broadcasts its Route_Msg .

network. s j . mem represents the member count of the CH node and α is a real value between 0 and 1. Here, the node having maximum value of relay gets selected as relay node for forwarding the data to the BS. This implies that the CH node which has higher residual energy and lower member count will be selected as the relay node. Here, s j is a CH node which acts a relay node for s i which is not further away from BS than s i is from BS.

In our proposed scheme, the relay node selection is based on the energy estimate of each possible relay node. It will be more appropriate to select the relay node based on the actual energy cost rather than based on only the residual energy and count information used in (5). One of the feasible nodes is finally selected as the relay node according to the expression given in (6). In the proposed scheme, for inter-cluster communication process, each cluster head first broadcasts a message comprising of its node id, residual energy, member count, and distance to the BS. The CH s i would choose CH s j as relay node, if its remaining energy is largest value, after incorporating its intra-cluster energy consumption cost; inter-cluster transmission cost, and the cost of relaying the data from s j to BS, where relay is computed as given in (6).

s .E - s .mem* E *DM-(s .mem+1)*E *DM-E * DM j jr j              RX             j                   DA               tx

E max

where s j .E jr represents the current residual energy of j ^th node; mem represents the member count of j ^th node; E RX represents the energy cost in receiving the data from its members with packet length DM ; E_DA represents the energy cost in aggregating the received data and E_TX is the energy cost of transmitting the data packet from CH s_i to CH s j and finally to BS. E_max is the maximum value of residual energy initially available in the network. CH s j transmits the message directly to BS in case when sj is within the pre-determined dist_th , or when no other CH node is available to route the packet. Thus, s i selects the cluster head as relay node having the maximum value of relay i.e. one which has highest remaining energy for forwarding the data packet to the BS. With choosing a relay node in this way helps in achieving the energy balance and in extending the network lifespan.

relay = а —— + (1 - а )-----

E _max           s_j . mem       ₍₅₎

where E j _r is the residual energy of the node and E_max is the maximum value of initial energy of the nodes of the

V. Protocol Analysis

In this section, the proposed protocol is analyzed. The main characteristics of the proposed protocol are elaborated. It shows that the cluster heads are distributed evenly and energy consumption among cluster member nodes is balanced. Further it shows that the proposed protocol is energy efficient. The properties of the improved EADC protocol are as follows.

• The cluster heads elected are based on the ratio of the average residual energy and the remaining energy of the nodes given in (4). This helps in

prolonging the network lifetime as the nodes having more remaining energy are selected.

• •    The cluster heads set elected covers the whole network. As in (4), V r parameter ensures that for any case of remaining energy of nodes, the wait time is less than or equal to duration T 2 of cluster head competition sub-phase. Therefore, any node can become a cluster head before the timer expires. Further, in case any node has not received the Head_Msg , it advertises itself to be cluster head.

• •    The relay metric used is defined directly in terms of energy, so it helps in prolonging the lifetime by selecting the route more efficiently for sending the data to the BS.

• •    The number of control messages transmitted is N number of Node_Msg , ( N - k ) number of Join_Msg , k number of   Head_Msg ,   Schedule_Msg and

Route_Msg, if k is the number of CHs selected in a round. Therefore the total number of control messages generated in a round in our improved EADC protocol comes out to be N + (N - k) + k + k + k = 2N + 2k . Thus the control messages overhead is O( N ).

• VI. Performance Evaluation

In this section, the performance of the improved EADC protocol is evaluated through simulation. The simulation was performed in MATLAB. In simulation the widely accepted simple radio model [7] for radio hardware energy dissipation has been used. The topology of the network, the simulation parameter used, and the simulation results obtained are presented in the subsequent sections. The cluster head distribution, the network remaining energy, and the network lifetime have been analyzed. The performance of the proposed protocol is compared with the existing EADC protocol [17] in order to demonstrate the improvement obtained in network lifetime.

• A. Simulation Environment

Three scenarios were chosen for simulations:

Scenario 1: 100 nodes are uniformly deployed over an area of 200 x 200 m2 shown in Fig 1(a).

Scenario 2: 100 nodes are non-uniformly deployed with more number of sensor nodes grouped together in the region towards the right side of sensor field i.e. near to BS, over an area of 200 x 200 m2 as shown in Fig 1(b).

Scenario 3: 100 nodes are non-uniformly deployed with more number of sensor nodes grouped together in the region towards the left side of sensor field i.e. far from BS, over an area of 200x200 m2 as shown in Fig 1(c).

scenario1200

тО"

о

0) го

150г

о

6 о

50     100    150    200X-coordinate

Fig.1(a). Network Topology of Scenario 1

scenario2

го с тэ о о о

>

150    200

X-coordinate

Fig.1(b). Network Topology of Scenario 2

scenario3200

ГО

150м

О

О

100Г 9

О О

50    100    150    200X-coordinate

Fig.1(c). Network Topology of Scenario 3

B. Simulation Parameters

The parameters of the simulation used in the present paper are listed in Table I.

Table 1. Simulation Parameters

S.No.	Parameter	Value
1.	Network area	200 m x 200 m
2.	Base station location	(250,100)
3.	No. of nodes	100
4.	Initial energy of nodes	0.5-1.5J
5.	Data packet size	500 bytes
6.	elec	50 nJ / bit
7.	ε fs	10 pJ / bit/m2
8.	ε mp	0.0013 pJ / bit/ m4
9.	E DA	5nJ / bit /signal
10.	R c	90 m
11.	Threshold distance	87.7 m
12.	α	0.5

• C. Results and Discussions

In the simulation experiments, the energy model and the data aggregation model used is as described in section III. The results of the simulations are average of the several experiments performed. The following key metrics are used for studying the performance of the proposed protocol, such as:

• •    Number of cluster heads: This metric lays out the effect of node distribution in each scenario.

• •    Average energy consumption per round: This metric stands for the average energy consumption by all the nodes of the network in one round.

• •    Network remaining energy: This metric represents the total remaining energy of the network with respect to rounds.

• •    Network lifetime-FND: This metric is measured in terms of data collection rounds and represents the time when first node in the network dies.

• •    Network lifetime-PND: This metric corresponds to the time period from the instant the network starts functioning to the instant when 10 percent of the nodes are dead.

• •    Number of alive nodes: This metric shows the number of nodes which are alive with respect to rounds.

• a)    CH distribution evaluation:

Fig. 2 shows the average number of cluster heads generated in each scenario with the value of competition radius set as 90 m. The figure illustrates that cluster head distribution is not affected with the node distribution. Further, it is observed that the number of cluster heads is controlled and distributed. In case of each scenario, two, three, four or five number of cluster heads is produced. This is because Rc ensures that not more than one cluster head is produced in one cluster heads’ coverage range. The clusters formed are equal size and this makes energy balance in the network.

Fig.2. Average Number of Cluster Heads.

• b)    Energy consumption evaluation

The average energy consumption of the EADC and improved EADC protocol is evaluated for the three scenarios considered here. Fig. 3 shows average energy consumption per round in the network when each protocol is run until its lifetime. Energy consumption of a round comprises of the energy consumed during clustering topology formation and data transmission. It is observed that the mean energy consumption in our improved EADC protocol is slightly less than that in case of EADC protocol.

Fig.3. Average Energy Consumption of the Sensor Network.

The improved EADC protocol balances load among cluster heads by selecting the relay node taking into consideration the energy, member count and distance parameters. This can result in energy saving and enhancement of network lifetime.

• c)    Network remaining energy evaluation

Fig. 4 shows the total remaining energy of the network in improved EADC protocol with respect to number of rounds in each scenario. It is observed that residual energy of nodes in the network reduces at almost the same rate initially in all the scenarios. In later rounds, the difference can be seen in the node’s remaining energy in different scenarios. The remaining energy depletes more quickly in scenario 3, then in scenario 2 and lastly in scenario 1. In scenario 2, cluster heads in dense area has more member count, while in scenario 3, cluster heads selected as relay node would require covering larger distance to transmit the data packet to BS, therefore in these scenarios, energy depletes faster than uniformly distributed scenario i.e.scenario1.

Fig.4. Average Residual Energy of Network.

• d)    Network lifetime evaluation

Fig.5. Network Lifespan when first Node Dies.

Fig.6. Network Lifespan when 90 Percent Nodes are Alive.

• e)    Number of alive nodes evaluation

The improvement gained through our improved EADC protocol is further laid out in each of the three scenarios. Fig. 7, 8 and 9 respectively shows the number of alive nodes with respect to rounds in case of scenario 1, 2 and 3. As observed, the improved EADC protocol achieves better energy efficiency and balancing than the EADC protocol. From the results, it can be concluded that the improved EADC protocol is able to address the nonuniform distribution and energy balance problem successfully.

Fig.7. Number of Alive Nodes for Scenario 1.

Fig.8. Number of Alive Nodes Rounds for Scenario 2.

Fig.9. Number of Alive Nodes for Scenario 3.

• VII. Conclusions

In this paper, an energy aware distributed clustering protocol (EADC) has been extended in order to improve the lifespan of WSN. The uniform clustering technique is used in this work. The relay node selection procedure for forwarding the data towards the BS is based directly in terms of energy estimate. The simulation results show that network lifespan is extended effectively in each scenario compared to the EADC protocol. This improvement shows the effectiveness of the proposed improved EADC protocol in terms of balancing the energy and distributing the clusters in both uniform and non-uniform scenarios.