Abstract

In this paper, an improved version of the energy aware distributed unequal clustering protocol (EADUC) is projected. The EADUC protocol is commonly used for solving energy hole problem in multi-hop wireless sensor networks. In the EADUC, location of base station and residual energy are given importance as clustering parameters. Based on these parameters, different competition radii are assigned to nodes. Herein, a new approach has been proposed to improve the working of EADUC, by electing cluster heads considering number of nodes in the neighborhood in addition to the above two parameters. The inclusion of the neighborhood information for computation of the competition radii provides better balancing of energy in comparison with the existing approach. Furthermore, for the selection of next hop node, the relay metric is defined directly in terms of energy expense instead of only the distance information used in the EADUC and the data transmission phase has been extended in every round by performing the data collection number of times through use of major slots and mini-slots. The methodology used is of retaining the same clusters for a few rounds and is effective in reducing the clustering overhead. The performance of the proposed protocol has been evaluated under three different scenarios and compared with existing protocols through simulations. The results show that the proposed scheme outperforms the existing protocols in terms of network lifetime in all the scenarios.

Keywords

EADUC ; Energy hole ; Multi-hop routing ; Network lifetime ; Wireless sensor networks

1. Introduction

Wireless sensor networks (WSNs) are characterized by many resource constraints such as energy, processing power, storage and transmission range. Out of these factors, energy of deployed sensors has been the major resource constraint of the wireless sensor networks. Lot of research work has been carried out in the last decade to address this challenge [1] , [2]  and [3] . WSNs are deployed densely for data gathering applications involving a large amount of area such as agriculture, forests, coal mines, monitoring of rail tunnels, monitoring of solar photovoltaic cell in a grid, etc., and WSNs require data from all locations [2] , [4] , [5]  and [6] . The base station (BS) is placed far away from the sensing field in most of the cases. In such networks, data are gathered periodically by the BS. Clustering with hierarchical topology is found to be successful for realizing continuous monitoring networks [7] , [8] , [9] , [10]  and [11] . It is exhibited that clustering the network offers greater lifespan than the network with direct data transmission. It is shown that the network lifespan gets improved by a factor of about 2 or 3 times with clustering [12] .

There are many advantages of using clustering protocols in data-gathering networks. In dense network, normally there is large volume of traffic among the sensors, which leads to creation of interference and subsequently results into collisions. It is expected that grouping the sensors would minimize the number of long distance transmissions and thereby result into saving of the energy. In clustering, the normal sensor nodes (cluster members) sleep times are drawn out, while cluster heads coordinate the activities of its member nodes, again resulting into energy saving [13] . This activity scheduling is executed largely through TDMA based schedule [5] , [11] , [14]  and [15] . Also clustering facilitates data aggregation at cluster head (CH) by decreasing the number of transmitted data packets, which helps in reduction of energy consumption of sensor nodes [13] .

The communication in clustering protocols is executed in two steps, first is intra-cluster, i.e. within the clusters, and the second is inter-cluster, i.e. between the clusters and the BS. Furthermore, the communication in a wireless sensor network clustering protocol can be taken up either by employing single hop transmission, or multi-hop routing [16]  and [17] . Most of the clustering protocols use single hop communication for communicating inside the cluster, as the distance between sensors within the cluster is relatively short, e.g. LEACH [11] , LEACH-DT [15] , HEED [18] , etc. Researches proposed in literature report that multi-hop communication between the sensor nodes and the cluster head is more energy-efficient than single hop communication, when the propagation loss exponent is high. This is when sensor nodes are deployed in dense vegetation regions, or buildings, or factories [1]  and [16] . In such cases, multi-hop communication is successful in overcoming signal propagation difficulties [1]  and [7] . However, because the radio dissipates energy in not only transmission but also in reception, direct transmission is also useful. But there is a limitation in case of direct transmission also. It is good to use it up to a certain threshold distance only [19] . This is because in case of transmission distance beyond threshold distance, the energy expense increases according to the fourth power of the distance [15]  and [20] . As the sensor nodes are energy constrained, they usually have a limited transmission range. Thus, in order to increase the network scalability also, multi-hop communication is preferable [21] . In case of communication from cluster head node to the BS, if BS being far away from sensor field, then, it is better to use multi-hop communication [19] . There are number of clustering protocols developed that use multi-hop communication for achieving more energy-efficient inter-cluster communication. Multi-hop LEACH [22] , EADC [23] , EDUC [24] , etc. are some such protocols.

One of the primary concerns in wireless sensor networks is maximization of network lifetime because after the network becomes dysfunctional, significant amount of energy should not remain in the nodes, otherwise it is wastage. Many research works has defined the network lifetime to be when the 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 [8] , [11] , [15]  and [18] . But, as the lifetime requirement is application-specific, considering the first node dead as the lifetime definition is not a generic one [25] . There are different types of sensor networks applications [26] and therefore, to cater to different application requirements, lifetime of the network has also been evaluated at different stages, i.e. the time when first node dies, or certain percentage of nodes fail [27] . In any case, it is more important that network functions autonomously and guarantees its operation until its lifetime [28] .

In a clustering protocol, a CH is heavily burdened as it has to perform various tasks such as cluster formation, data aggregation, data transmission and relaying. Cluster heads therefore consume more energy as compared to non-CH nodes. In inter-cluster transmission for both the modes of communication, single hop and multi-hop, there is inevitable problem of energy imbalance among sensor nodes [24] . 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, loss of sensing coverage and partitioning of the network occur and ultimately affect the network performance. Previous research [29] has demonstrated that if sensors are distributed uniformly in the area of interest, 90 percent of the total energy of the sensors is left unused when network lifetime ends, i.e. the time when first node is dead. It is proved in reference 30 that unbalanced energy depletion among all the sensors is unavoidable because of many-to-one communication paradigm in WSNs. For maximizing the network lifetime, energy consumption among all the network nodes must be balanced. Recently, much 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 [31]  and [32] , mobile sink [33] , [34] , [35]  and [36] , hierarchical deployment [37] , non-uniform clustering [8] , [24]  and [38] , data compression and traffic aggregation [36]  and [39] , node distribution [2] , [29] , [30]  and [40] , etc. have been proposed for solving energy hole problem.

In this paper, an attempt has been made to improve network lifespan of an EADUC protocol used in continuous monitoring applications [38] . The EADUC employs non-uniform clustering algorithm to mitigate the energy hole problem. The core idea in our proposed scheme is that during the cluster head selection sub-phase, nodes competition radius assignment would be based on not only the distance factor and nodes residual energy as is used in EADUC, but also a tertiary factor, number of neighbor nodes. This neighborhood information is considered as the clustering parameter to extend network lifespan. Another key idea used in our improved EADUC protocol is during selection procedure of traffic relaying. The cost involved in relaying, in terms of energy, is incorporated as the metrics for selecting one of the feasible nodes as a relay node instead of only the distance information used in EADUC. The proposed scheme poises the energy consumption of the nodes in the network for uniform distribution as well as for non-uniform distribution. Further to enhance the network lifetime, the idea of extending the data transmission phase by dividing into major slots and mini-slots is effectively combined with the proposed clustering and relaying technique as used in reference 41. The data collection occurs in each mini-slot using the same clusters once formed and the number of mini-slots comprises a major slot. After each major slot, cluster head rotation within the current cluster boundary and handover of the cluster members takes place. The proposed approach reduces the clustering overhead and thereby prolongs the network lifetime. The performance of our proposed protocol is compared with the existing protocols using network lifetime as the performance metric.

The remainder of this paper is organized as follows: Section 2 reviews the related work and Section 3 presents the system 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. Section 7 concludes the paper.

2. 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 available in this category is low-energy adaptive clustering hierarchy (LEACH) protocol [20] . The LEACH protocol assumes one-hop communication between the nodes and to the base station. This makes it unsuitable for large-scale networks. Many LEACH based protocols have been developed in the past which are improvements over the LEACH protocol, such as LEACH-DT [15] or a multi-hop variant of LEACH, called as M-LEACH [1] . A hybrid energy-efficient distributed (HEED) clustering algorithm is proposed in reference 18, 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 nodes closer to BS still die faster. Another protocol, the distributed energy efficient clustering algorithm (DEEC), is available [42] . In DEEC, cluster heads are chosen by a probability that is based on the ratio of residual energy of a node and the average energy of the network. In all these energy-efficient clustering schemes, although periodic rotation of cluster head function sees that nodes run through energy more evenly, but it is not effective in avoiding the energy hole problem of many-to-one data gathering wireless sensor networks.

Many methods have been proposed in literature for mitigating the energy hole problem, and thereby maximizing the network lifetime. Approaches for overcoming energy hole problem are categorized into three categories [43] . First is assistant approaches, such as deployment assistance [35] , e.g. TTDD [44] , traffic compression and aggregation [39] . Larger initial energy nodes can be deployed in the region consuming larger energy, i.e. using energy heterogeneity [35] , or as in TTDD [44] , which is called hierarchical deployment. In TTDD scheme, a number of assisting nodes are deployed having larger battery capacity and larger transmission range. These assisting nodes form a relay region on upper side of the regular sensors that have lower initial energy and thus help in alleviating the energy hole problem. The second type of approach is based on node distribution strategy that has been studied in references [29] , [30]  and [45] and [46] . More number of nodes can be deployed in the region near the BS. Also in reference [47] , nodes are deployed with the help of a pre-determined distribution function. The third approach is based on transmission range adjustment [35] , [43]  and [48] . The transmission range adjustment scheme has been investigated to maximize the sensor network lifetime in reference 43. The energy hole problem is solved by adjusting the radii of sensors communication ranges in reference 35. But this solution has a severe restriction on the size of sensor field. The mobility of the sink is another alternative to solve energy hole problem [36]  and [48] . In reference 36, mobility of the base station is considered for event-driven network. The authors in reference 33 have proposed base station mobility and multi hop routing approach for extending the lifetime in WSN. The major drawback with these approaches is that they are not feasible. These methods involve high cost and provide lower energy efficiency [46] .

In the last few years, researchers have explored the strategies to extenuate the energy hole problem in hierarchical (cluster-based) WSNs. Many energy efficient algorithms have been developed using equal and unequal size clustering technique. Here we consider unequal size clustering only to counter the problem of uneven energy consumption among sensor nodes of the network. The first algorithm proposed in the category of utilizing unequal cluster size is an unequal cluster size (UCS) model [8] , which forms unequal clusters for easing the over burdened cluster heads, and ensuring better balancing of energy dissipation among nodes. The work considered heterogeneous network and the deterministic deployment of cluster heads at pre-computed locations for controlling the cluster size. It achieved an improvement of 10–30% over the equal clustering size strategy, depending on the aggregation efficiency of CH nodes. In EEUC [49] , a clustering and distributed algorithm is designed for data gathering applications, which efficiently organizes the network nodes using unequal clustering and multi-hop routing. But in this method the cluster head selection is probabilistic and therefore solitary nodes can be produced.

Besides using unequal clustering to solve energy imbalance, work has also been done using energy-efficient multi-hop routing for saving the nodes' energy. In this category, EEMR [50] , an energy efficient multi-hop routing protocol is one such protocol designed. It uses BS to select optimal paths for data transmission between source nodes and sink node. By utilizing the BS energy for performing routing paths selection and other control messages broadcasts, it reserves the energy of network nodes. Unequal cluster-based routing protocol (UCR) [51] is another algorithm proposed for considering the hot spot problem in multi-hop sensor networks. It also forms unequal cluster sizes through using uneven competition ranges, and for inter-cluster communication, it uses a greedy geographic and energy-aware routing protocol. The routing strategy in this paper uses both residual energy and transmission distance parameters to balance the energy consumption across the network.

Another method, an energy-driven unequal clustering protocol (EDUC) [24] , considers a distributed unequal clustering algorithm and an energy-driven adaptive cluster head rotation method. In this the energy consumed in cluster head rotation is minimized by allowing a node to be cluster head only once during the network lifetime. Thus, by reducing the energy cost used in cluster head rotation, it achieves energy efficiency. But it has the limitation that it is useful for single-hop networks only.

In reference 52, an unequally clustered multi-hop routing protocol (UCMR) is proposed, wherein each cluster has different sizes based on the distance to the BS and Dijkstras shortest path algorithm is used for intra-cluster and inter-cluster communications. But unlike other protocols that are location-unaware, UCMR relies on physical location information. The authors in reference [53] have addressed the energy imbalance problem via energy- and proximity- based unequal clustering algorithm (EPUC). The CHs are selected based on residual energy and their proximity to BS. It focuses on the region near the BS to counter the energy imbalance as that region has more loads due to relaying activity.

Recently sink mobility based energy balancing unequal clustering protocol (SMEBUC) has been proposed in reference [54] , which uses improved shuffled frog leaping algorithm for network clustering and cluster head replacement strategy. The cluster head once selected serves continuously and by reducing the frequency of cluster head replacement, it saves energy. Depending on the weight, cluster head exchange time is determined and the cluster heads use greedy algorithm to determine its relay node. The inter-cluster communication is carried using multi-hop routing and it adopts a threshold to avoid a single long chain forming. Another energy efficient data collection method proposed in reference 41 utilizes hybrid unequal clustering. In this, the network is divided into layers and clusters. The layering is used for inter-cluster communication, which is multi-hop in nature. The clusters are independent of the layers and in this the hybrid approach of static and dynamic clustering is exploited. The frequency of clustering is reduced, which reduces the clustering overhead. Also it uses an in-network data compression algorithm that also improves network lifetime.

3. Preliminaries

An improved EADUC algorithm is presented in this section. The network considered here consists of N number of sensor nodes deployed randomly in an M  × M sensor field. The nodes and the base station are static after deployment. The nodes are energy heterogeneous, i.e. the deployed nodes are of different initial energy. 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, but can form an estimate of the distance to another node developed on the received signal strength; the links being assumed to be symmetric [49]  and [55] . The cluster heads can transmit their data directly with BS. The data messages (DM ) and control messages (CM ) are transmitted through wireless links. Furthermore, it is assumed that the data sensed by the nodes are highly correlated.

3.1. Energy model

The transmitter consumes energy in running the radio electronics circuitry and the transmit amplifier circuitry, whereas the receivers energy consumption is only in radio electronics part [11]  and [20] . Also, depending on the transmission distance, both the free space and multipath fading channel models are used. If the distance is to a lesser extent 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 Eq. (1) .

( 1)

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

( 2)

3.2. Data aggregation model

In the present work, the infinite compressibility model is used for data aggregation [7]  and [20] . 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.

4. The improved EADUC protocol mechanism

The clustering method used is similar in operation to EADUC protocol [38] . The protocol operates in rounds. After nodes are deployed, each node first computes its distance from BS. For this, BS broadcasts a signal, which is heard by all nodes. On the basis of the received signal strength, each node approximates its distance to BS. Each round comprises of cluster set-up phase and steady state phase in which data transmission takes place. The set-up phase is further sub-divided into three sub-phases of durations T1 , T2 and T3 respectively. The first sub-phase is the neighbor node information collection. At the beginning of information collection sub-phase, 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 Eq. (3) .

( 3)

where sj is one of the nodes, sj . Er is the residual energy of sj, and nb is the number of neighbors. After T1 has timed out, the operation of next sub-phase, i.e. cluster head competition, starts whose duration is T2 . In this sub-phase cluster heads are chosen. At the end of information collection phase, each node calculates its wait time for broadcasting the Head_Msg according to Eq. (4) .

( 4)

where Er is the current residual energy of the node; Vr is a real value randomly distributed in [0.9, 1], which is used to reduce the probability that two nodes send Head_Msg at the same time [37] . If any of the nodes does not receive any Head_Msg , it broadcasts a Head_Msg within Rc , advertising its state as cluster head.

The improved EADUC scheme is based on the EADUC protocol [38] ; however, in contrast to the EADUC, it uses a different competition radius rule for producing unequal clusters. In the original EADUC protocol, in the expression for competition radius, only the distance between the nodes and the BS, and the residual energy of the nodes is taken into account. In order to account for the expense involved in aggregation, the proposed scheme also considers the number of neighbors, in addition to the above two factors, while deciding the competition radii. The competition radius for the proposed scheme is a function of distance to the BS, the residual energy of CH, and the number of neighbor nodes. Nodes with relatively higher residual energy, greater distance from the BS, and lower number of neighbor nodes should have larger competition radius. For achieving it, following formula given in Eq. (5) is used.

( 5)

where are the weights in (0, 1), Rmax is the maximum value of transmission radius, dmax and dmin are the maximum and minimum distance of nodes from BS, d (sj ,BS ) is the distance of j th node from BS, Er is the nodes residual energy and Emax is maximum value of initial energy of the nodes in the network, sj (nb ) is the number of neighbor nodes of j th node and nbmax is the maximum value of neighbor nodes. Therefore, incorporating nodes' distance from BS, its residual energy, and its neighborhood information, the cluster size is governed.

The idea of inclusion of neighborhood information for cluster head selection along with available energy and distance to the sink is used in some existing protocols, viz. an unequally clustered multi-hop routing protocol (UCMR) [52] , and hybrid unequal clustering with layering protocol (HUCL) [41] . However, in the UCMR and HUCL protocols, the number of neighbors is not considered while computing the competition radii. The calculation of competition radii in these papers uses the distance parameter only as is used in an energy-efficient unequal clustering mechanism (EEUC) [49] or in an unequal cluster-based routing protocol (UCR) [51] . In the UCMR protocol, the number of neighboring nodes is incorporated in the weight calculation that is one of the parameters in the cluster head selection procedure. In the HUCL protocol, the neighborhood information, i.e. number of neighbors is used during calculation of the wait time, which is a step during cluster set up.

After cluster head competition sub-phase, wherein cluster heads are chosen, cluster formation sub-phase starts, whose duration is T3 . In this phase, the normal nodes choose the nearest cluster head. By sending the Join_Msg , cluster is formed. The cluster head, in turn, broadcasts a TDMA Schedule_Msg for its cluster members data transmission. The member nodes thus can wake up only during their time slot and in other times they can remain in sleep state. This helps in conserving energy.

After the network is setup as clusters, steady state phase begins. In this phase, data transmission takes place. First the member nodes transmit their sensed data according to the schedule prepared by their respective cluster heads. This transmission is single hop and is known as intra-cluster communication. The cluster head receives the sensed data from its member nodes and stores the average aggregated data. As the members selected in a cluster are those which are nearer to their respective cluster heads, so it is appropriate to aggregate the incoming data into one packet. The task of intra-cluster communication is done simultaneously in all clusters.

The cluster heads transmit the data packet to the BS either directly, or through relaying. If the distance from respective cluster head to BS is greater than threshold distance (dist_th ), inter-cluster communication is carried out; otherwise direct transmission is executed. For inter-cluster communication, the selection of cluster head as next hop node (relay node) is then drawn.

In the original EADUC protocol, relay node selection is done as one of the neighbor nodes from the candidate forwarding set according to a parameter Erelay . This Erelay parameter is computed as the energy consumption when CH si chooses sj as its next hop from the Eq. (6) given below.

( 6)

So, in EADUC protocol, the node having smallest Erelay in the forwarding candidate set gets selected as relay node for forwarding the data to the BS.

We argue that as the relationship between the distance and the energy is not linear, energy consumption Erelay may not be the only important metric for setting the route. In our proposed scheme the relay node selection is based on the energy estimate at each feasible node. One of the feasible nodes is finally selected as the relay node according to the expression given in Eq. (7) . In the proposed scheme, for inter-cluster communication process, each cluster head first broadcasts a message comprising of its node id, residual energy, count containing the number of cluster members, and distance to the base station. The CH si would choose CH sj as relay node, if its remaining energy is the largest value, after incorporating its intra-cluster energy consumption, inter-cluster transmissions cost, and the cost of relaying the data from sj to BS.

( 7)

where represents the current residual energy of j th node; count represents the member count of j   th node; represents the energy cost in receiving the data from its members with packet length DM   ; represents the energy cost in aggregating the received data, and is the energy cost of transmitting the data packet from CH si to CH sj over the relay_dist and finally to the BS. Emax is the maximum value of residual energy initially available in the network. CH sj transmits the message directly to BS in either of the cases, i.e. if sj is within the pre-determined dist_th , or even if first condition is not true, also when no other CH node is available to route the packet. Thus, si selects the cluster head having the maximum value of relay , i.e. one that has highest residual energy. With choosing a relay node with higher relay in this way helps in keeping up the energy balance and in extending the network lifespan.

In order to further improve the performance, the cluster head rotation is not carried out in every round. Instead once the cluster set up is obtained, it is retained for a few rounds. In one round of protocol operation, the data transmission phase runs number of times. For this, the steady state phase comprises of a number of major slots, ‘M ’. Each major slot further comprises of number of mini slots, ‘m ’. In each mini slot, the whole process of data transmission phase is carried out. During the last mini slot, the member nodes send their residual energy along with the data. After one major slot is over, the cluster head rotation within the cluster boundary is carried out. The old cluster head gets replaced by a new cluster head in the same cluster depending on the residual energy of the nodes and the distance from the current cluster head. The member node having higher remaining energy and minimum distance from it is chosen as the new cluster head. The old cluster head hands over the members list to the new cluster head. When the new cluster head selection and hand over occurs, another major slot begins. After the completion of the number of major slots, another round of protocol runs comprising of the set up phase and steady state phase.

5. Protocol analysis

The following are the characteristics of the improved EADUC protocol.

  • The cluster heads elected are based on the ratio of the average residual energy and the remaining energy of the nodes given in eq. (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 eq. (4) , Vr parameter ensures that for any case of remaining energy of nodes, the wait time is less than or equal to duration T2 of cluster head competition sub-phase. Therefore, any node can become a cluster head before the time T2 runs out. Furthermore, in case any node has not received the Head_Msg , it broadcasts itself to be cluster head.
  • The competition radius rule used for producing unequal clusters is based on the distance to the BS, the residual energy of nodes and the number of neighbors. It helps in better balancing of the energy in the network as the inclusion of the neighborhood information is taking into account the energy expense involved in aggregation.
  • 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 clustering overhead reduces as the cluster set up is retained for a few rounds. Therefore, the energy consumption of the network lessens and the network lifetime prolongs.

6. Performance evaluation

6.1. Simulation environment

Three scenarios were chosen for simulations:

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


Full-size image (62 K)


Fig. 1.

Network topology in the three scenarios.

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


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

In order to observe the effect of the proposed method of computing competition radius and relaying and the technique of division of data transmission phase into major and mini slots separately, the results of the proposed protocol, the improved EADUC, are shown in two steps in the subsequent sections. In the first implementation, namely improved EADUC 1, the proposed protocol uses the method of clustering and relaying only without incorporating the division of data transmission phase. In the second implementation, namely improved EADUC 2, the method of clustering and relaying along with the technique of division of data transmission phase is incorporated. The number of mini-slots is taken as 3 and major slots as 2 while simulating the EADUC 2 protocol. The energy efficiency of the proposed protocol is compared with the EADUC protocol and the HUCL protocol. For comparison, the simulation parameters and the scenarios considered are same in all the protocols and the basic mechanism of the HUCL protocol operation without compression is considered.

6.2. Simulation parameters

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

Table 1. Simulation parameters.
Parameter Value
Network area 200 m × 200 m
Base station location (250,100)
No. of nodes 100
Initial energy of nodes 0.5–1.5J
Data packet size 500 bytes
Eelec 50 nJ/bit
εfs 10 pJ/bit/m2
εmp 0.0013 pJ/bit/m4
EDA 5 nJ/bit/signal
Rmax 110 m
Threshold distance 87.7 m
α, β, γ 0.3333

7. Results and discussions

The simulation was performed in MATLAB. In the simulation experiments, the energy model and the data aggregation model used are as described in Sections 3.1 and 3.2 respectively. The results of the simulations are average of the several experiments performed. The following performance metrics are used in this paper:

  • 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-PNA: 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 that are alive with respect to rounds.

7.1. CH distribution evaluation

Fig. 2 shows the average number of cluster heads generated in each scenario. The cluster heads are distributed and the number of cluster heads is also controlled. The improved EADUC protocol produces stable number of cluster heads as seen in Fig. 2 . This is because the competition radius checks that there is only one cluster head in each competition radius. In case of scenario 1, i.e. comprising of uniformly distributed sensors, four or five numbers of cluster heads are generated in each round of protocol operation and are almost equally probable. In case of scenario 2, five numbers of cluster heads are more probable, whereas in scenario 3, four numbers of CHs are more probable. During the protocol operation, the nodes near the BS are assigned smaller competition radii. As in scenario 2, more number of nodes is deployed in the region near BS; it is more likely to produce more number of cluster heads than the case of scenario 3, where the region near BS is sparse.


Average number of cluster heads generated in different scenarios.


Fig. 2.

Average number of cluster heads generated in different scenarios.

7.2. Energy consumption evaluation

The average energy consumption of the EADUC and improved EADUC 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 for the three different scenarios. Energy consumption of a round comprises of the energy consumed during clustering topology formation and data transmission.


Average energy consumption of network in different scenarios.


Fig. 3.

Average energy consumption of network in different scenarios.

The mean energy consumption in our improved EADUC 1 protocol is slightly less than that in case of EADUC protocol and is much less in case of improved EADUC 2 protocol. Furthermore, it is observed that the mean energy consumption of network in scenario 3 is slightly large as compared to scenario 2, because in scenario 3, the region near to BS is sparsely distributed, therefore it is more likely that the final relay node is at larger distance to BS than in case of scenario 2, it being densely distributed.

7.3. Network remaining energy evaluation

Fig. 4 shows the total remaining energy of the network in improved EADUC 2 protocol with respect to number of rounds in each scenario.


Average residual energy of network in different rounds.


Fig. 4.

Average residual energy of network in different rounds.

It is observed that residual energy of nodes in the network reduces at almost the same rate in case of scenarios 1 and 2. But the total remaining energy of the network is less in case of scenario 3 as compared to scenarios 1 and 2. This is because of larger energy consumption by nodes of the network in scenario 3. And this is due to the region near the BS is sparse in scenario 3.

7.4. Network lifetime evaluation

The network lifetime is evaluated here in two ways. One way used is to measure the round when first node dies (FND) and another way used is to measure the round when 90 percent of the nodes are alive (PNA). The original EADUC, HUCL and improved EADUC 1 and 2 protocols were run in the three scenarios. As shown in Figs. 5 and 6 , there is improvement in network lifespan, FND and PNA of improved EADUC 1 and 2 in each of the three considered scenarios as compared to EADUC and HUCL protocols. The improved EADUC 1 protocol enhances the network lifetime when FND is the metric, by 12%, 6%, and 2% respectively and when PNA is the metric, by 4%, 5%, and 2% respectively for scenarios 1, 2, and 3 as compared to EADUC protocol. The network lifetime in improved EADUC 1 gets enhanced because it balances the energy in the network in a better way. Also the task of routing the data to BS is more effective in our improved EADUC protocol. The average improvement obtained in lifespan in improved EADUC 2 protocol considering FND as the metric is about 134% for scenario 1, 118% in case of scenario2, and 75% for scenario 3 in comparison with EADUC. With reference to PNA as the lifetime evaluation metric, the average improvement in scenarios 1, 2 and 3 is about 180%, 167% and 126% respectively. The network lifetime in our EADUC 2 protocol enhances significantly because in addition to the clustering and relaying technique, the clustering overhead is minimized here by retaining the clusters once formed for few rounds depending on the number of mini-slots and major slots. The results shown are with number of major slots considered as 2 and the number of mini-slots as 3.


Network lifespan when first node dies.


Fig. 5.

Network lifespan when first node dies.


Network lifespan when 90 percent nodes are alive.


Fig. 6.

Network lifespan when 90 percent nodes are alive.

Furthermore, as compared to HUCL protocol, our improved EADUC 2 protocol has better network lifetime in terms of FND and PNA metric. The network lifetime, FND and PNA, enhances by 109%, 166% and 55% respectively, and by 28%, 10% and 9% respectively, in case of scenarios 1, 2 and 3. This enhancement is due to the difference in the mechanism of cluster head selection and routing of the sensed data. The number of control messages generated in our proposed protocol is less as compared to HUCL protocol as it uses hybrid unequal clustering with layering technique. Also it is observed during simulation runs that the HUCL produces more number of CHs per round; typical value is 9, 11, and 6 clusters respectively for the considered scenarios 1, 2, and 3. Also, it is not taking into account the heterogeneity of the nodes during cluster head selection.

This improvement shows the effectiveness of the proposed improved EADUC protocol in terms of balancing the energy and distributing the clusters.

7.5. Number of alive nodes evaluation

The improvement gained through our improved EADUC protocol is further laid out in each of the three scenarios. Fig. 7 , Fig. 8  and Fig. 9 , respectively, show the number of alive nodes with respect to rounds in case of scenarios 1, 2 and 3.


Number of alive nodes with respect to rounds for scenario 1.


Fig. 7.

Number of alive nodes with respect to rounds for scenario 1.


Number of alive nodes with respect to rounds for scenario 2.


Fig. 8.

Number of alive nodes with respect to rounds for scenario 2.


Number of alive nodes with respect to rounds for scenario 3.


Fig. 9.

Number of alive nodes with respect to rounds for scenario 3.

As observed, the improved EADUC protocol, i.e. EADUC 2, achieves better energy efficiency and balancing than the EADUC and HUCL protocols. This is because the improved EADUC protocol considers the impacts of both intra-cluster and inter-cluster communication loads during operation. From the results, we can conclude that the improved EADUC protocol is able to address the non-uniform distribution, heterogeneity of nodes and energy hole problem successfully.

8. Conclusions

In this paper, an energy aware distributed unequal clustering protocol (EADUC) has been extended in order to improve the lifespan of WSN. The non-uniform clustering approach has been exploited in this work. The clusters formed are of unequal size by using uneven competition radius. The clusters closer to base station have smaller size than clusters that are far away from the BS. The nodes are assigned uneven competition radius through use of multiple factors, viz. the distance to BS, the residual energy and the number of neighbors. Thereby, the energy consumption among the cluster head nodes is more effectively balanced. Furthermore, the relay node selection procedure for forwarding the data toward the BS is based directly in terms of energy expense. The simulation results show that network lifespan is prolonged effectively in each scenario compared to the EADUC and HUCL protocols. The outcome of this study shall be useful for solving the energy hole problem in data gathering networks.

References

  1. [1] V. Mhatre, C. Rosenberg; Homogeneous vs. heterogeneous clustered networks: a comparative study; Proc. IEEE, ICC, 6 (2004), pp. 3646–3651
  2. [2] C.Y. Chang, H.R. Chang; Energy aware node placement, topology control and MAC scheduling for wireless sensor networks; Comp. Netw, 52 (2008), pp. 2189–2204
  3. [3] X. Gu, J. Yu, D. Yu, G. Wang, Y. Lv; ECDC: an energy and coverage-aware distributed clustering protocol for wireless sensor networks; Comp. Electr. Eng, 40 (2014), pp. 384–398
  4. [4] J. Mao, Z. Wu, X. Wu; A TDMA scheduling scheme for many-to-one communications in wireless sensor networks; Comp. Commun, 30 (2007), pp. 863–872
  5. [5] P. Ayona, A. Rajesh; Investigation of energy efficient sensor node placement in railway systems; Eng. Sci. Technol. Int. J. (2015) http://dx.doi.org/10.1016/j.jestch.2015.10.009
  6. [6] V. Kaundal, A.K. Mondal, P. Sharma, K. Bansal; Tracing of shading effect on underachieving SPV cell of an SPV grid using wireless sensor network; Eng. Sci. Technol. Int. J., 18 (2015), pp. 475–484
  7. [7] S. Bandyopadhyay, E.J. Coyle; An energy efficient hierarchical clustering algorithm for wireless sensor networks; IEEE INFOCOM  (2003) pp. 1713–1723
  8. [8] S. Soro, W.B. Heinzelman; Prolonging the lifetime of wireless sensor networks via unequal clustering; Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), USA  (2005) http://dx.doi.org/10.1109/IPDPS.2005.365
  9. [9] M. Ye, C. Li, G. Chen, J. Wu; EECS: An energy efficient clustering scheme in wireless sensor networks; IEEE International Conference on Performance, Computing, and Communications  (2005) pp. 535–540
  10. [10] S. Soro, W.B. Heinzelman; Cluster head election techniques for coverage preservation in wireless sensor networks; Ad Hoc Netw, 7 (2009), pp. 955–972
  11. [11] W.B. Heinzelman, A. Chandrakasan, H. Balakrishnan; Energy efficient communication protocol for wireless microsensor networks; Proc. 33rd Hawaii Intl Conference on System Sciences (HICSS'00)  (2000) pp. 8020–8029
  12. [12] A.F. Liu, W.X. You, C.Z. Gang, G.W. Hua; Research on the energy hole problem based on unequal cluster-radius for wireless sensor networks; Comp. Commun, 33 (2010), pp. 302–321
  13. [13] N. Vlajic, D. Xia; Wireless sensor networks: to cluster or not to cluster?; Proc. of the International Symposium on a World of Wireless, Mobile and Multimedia Networks  (2006)
  14. [14] M. Liu, J. Cao, G. Chen, X. Wang; An energy aware routing protocol in wireless sensor networks; Sensors, 9 (2009), pp. 445–462
  15. [15] S.H. Kang, T. Nguyen; Distance based thresholds for cluster head selection in wireless sensor networks; IEEE Commun. Lett, 16 (9) (2012), pp. 1396–1399
  16. [16] V. Mhatre, C. Rosenberg; Design guidelines for wireless sensor networks: communication, clustering and aggregation; Ad Hoc Netw, 2 (1) (2004), pp. 45–63
  17. [17] M. Perillo, Z. Cheng, W. Heinzelman; On the problem of unbalanced load distribution in wireless sensor networks; Proc. of IEEE GLOBECOM Workshops on Wireless Ad hoc and sensor networks, Dallas, TX,  (2004) pp. 74–79
  18. [18] O. Younis, S. Fahmy; HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks; IEEE Trans. Mobile Comput, 3 (4) (2004), pp. 366–379
  19. [19] B. Tavli; Energy-efficient relaying in wireless networks; Int. J. Electron. Commun, 63 (2009), pp. 695–698
  20. [20] W.B. Heinzelman, A. Chandrakasan, H. Balakrishnan; An application-specific protocol architecture for wireless microsensor networks; IEEE Trans. Wirel. Commun, 1 (4) (2002), pp. 660–670
  21. [21] R.C. Carrano, D. Passons, L.C.S. Maglhaes, V.N. Albuquerque; Survey and taxanomy of duty cycling mechanisms in wireless sensor networks; IEEE Commun. Surv. Tut, 16 (1) (2014), pp. 181–192
  22. [22] F. Xiangning, S. Yulin; Improvement on LEACH protocol of wireless sensor network; Proceedings of International Conference on Sensor Technologies and Applications (Sensor Comm)  (2007) http://dx.doi.org/10.1109/SENSORCOMM.2007.4394931 pp. 260–264
  23. [23] J. Yu, Y. Qi, G. Wang, X. Gu; A cluster-based routing protocol for wireless sensor networks with non-uniform node distribution; Int. J. Electron. Commun, 66 (2012), pp. 54–61
  24. [24] J. Yu, Y. Qi, G. Wang; An energy driven unequal clustering protocol for heterogeneous wireless sensor networks; J. Control Theory Appl, 9 (1) (2011), pp. 133–139
  25. [25] I. Dietrich, F. Dressler; On the lifetime of wireless sensor networks; ACM Trans. Sensor Netw, 5 (1) (2009), pp. 1–38 http://dx.doi.org/10.1145/1464420.1464425
  26. [26] D. Puccinelli, M. Haenggi; Wireless sensor networks: applications and challenges of ubiquitous sensing; IEEE Circuits Syst. Mag (2005), pp. 19–29
  27. [27] N.H. Mak; How long is the lifetime of wireless senor network?; Proc. IEEE International Conference on Advanced Information Networking and Applications  (2009) pp. 763–770
  28. [28] M. Haenggi; Energy-balancing strategies for wireless sensor networks; Proc. IEEE Symp. Circuit. Syst. (ISCAS), 4 (2003), pp. 828–831 http://dx.doi.org/10.1109/ISCAS.2003.1206348
  29. [29] J. Lian, K. Naik, G. Agnew; Data capacity improvement of wireless sensor networks using non-uniform sensor distribution; Int. J. Distrib. Sens.Netw, 2 (2) (2006), pp. 121–145
  30. [30] X. Wu, G. Chen, S.K. Das; Avoiding energy holes in wireless sensor networks with nonuniform node distribution; IEEE Trans. Parall. Distr. Syst, 19 (5) (2008), pp. 710–720
  31. [31] Y. Yang, M. Cardei; Movement-assisted sensor redeployment scheme for network lifetime increase; 10th ACM / IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM)  (2007) http://dx.doi.org/10.1145/1298126.1298132 pp. 13–20
  32. [32] W. Wang, V. Srinvasan, K. Chua; Using mobile relays to prolong the lifetime of wireless sensor networks; Proceedings of International Conference on Mobile Computing and Networking  (2005) http://dx.doi.org/10.1145/1080829.1080858 pp.270–283
  33. [33] J. Luo, J.P. Hubaux; Joint mobility and routing for lifetime elongation in wireless sensor networks; Proc. of IEEE, INFOCOM  (2005) pp. 1735–1746
  34. [34] M. Marta, M. Cardei; Improved sensor network lifetime with multiple mobile sinks; Pervasive Mob. Comput, 5 (5) (2009), pp. 542–555
  35. [35] H.M. Ammari, S.K. Das; Promoting heterogeneity, mobility, and energy-aware Voronoi diagram in wireless sensor networks; IEEE Trans. Parall. Distr. Syst, 19 (7) (2008), pp. 995–1008
  36. [36] D. Vass, Z. Vincze, R. Vida, A. Vidacs; Energy efficiency in wireless sensor networks using mobile base station; EUNICE 2005: Networks and Applications towards a Ubiquitously Connected World  (2005) pp. 173–186
  37. [37] J. Li, P. Mohapatra; An analytical model on the energy hole problem in many-to-one sensor networks; Proc. of IEEE Vehicular Technology Conf., Fall  (2005) pp. 2721–2725
  38. [38] J. Wu, Y. Qi, G. Wang, Q. Guo, X. Gu; An energy aware distributed unequal clustering protocol for wireless sensor networks; Int. J. Distrib. Sens. Netw (2011) http://dx.doi.org/10.1155/2011/202145
  39. [39] J. Li, P. Mohapatra; Analytical modeling and mitigation techniques for the energy hole problem in sensor networks; Pervasive Mob. Comput, 3 (2007), pp. 233–254
  40. [40] J. Jia, X. Wu, J. Chen, X. Wang; Exploiting sensor redistribution for eliminating the energy hole problem in mobile sensor networks; Eurasip J. Wirel. Commun. Netw, 1 (2012), pp. 1–11
  41. [41] L. Malathi, R.K. Gnanamurthy, K. Chandrasekaran; Energy efficient data collection through hybrid unequal clustering for wireless sensor networks; Comp. Electr. Eng (2015), pp. 1–13
  42. [42] L. Qing, Q. Zhu, M. Wang; Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks; Comp. Commun, 29 (2006), pp. 2230–2237
  43. [43] C. Song, M. Liu, J. Cao, Y. Zheng, H. Gong, G. Chen; Maximizing network lifetime based on transmission range adjustment in wireless sensor networks; Comp. Commun, 32 (2009), pp. 1316–1325
  44. [44] F. Ye, H. Luo, J. Cheng, S. Lu, L. Zhang; A two-tier data dissemination model for large-scale wireless sensor networks; Proceedings of IEEE / ACM International Conference on Mobile Computing and Networking, MOBICOM  (2002) pp.148–159
  45. [45] S. Olariu, I. Stojmenovic; Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting; INFOCOM  (2006) pp.1–12
  46. [46] G. Ma, Z. Tao; A nonuniform sensor distribution strategy for avoiding energy holes in wireless sensor networks; Int. J. Distrib. Sens. Netw (2013), pp. 1–14
  47. [47] S. Halder, A. Ghosal, S.D. Bit; A pre-determined node deployment strategy to prolong network lifetime in wireless sensor network; Comp. Commun, 34 (2011), pp. 1294–1306
  48. [48] A. Jarry, P. Leone, O. Powell, J. Rolim; An optimal data propagation algorithm for maximizing the lifespan of sensor networks; Proc. IEEE Int. Conf. Distrib. Comput. Sens. Syst. LNCS, 4026 (2006), pp. 405–421
  49. [49] C. Li, M. Ye, G. Chen, J. Wu; An energy efficient unequal clustering mechanism for wireless sensor networks; Proceedings of IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS)  (2005) pp. 596–604
  50. [50] J. Yu, W. Liu, J. Song, B. Cao; EEMR: An energy-efficient multi-hop routing protocol for wireless sensor networks; Proc. IEEE  (2008) pp. 291–298
  51. [51] G. Chen, C. Li, M. Ye, J. Wu; An unequal cluster-based routing protocol in wireless sensor networks; Wirel. Netw, 15 (2009), pp. 193–207 http://dx.doi.org/10.1007/s11276-007-0035-8
  52. [52] U. Hari, B. Ramachandran, C. Johnson; An unequally clustered multihop routing protocol for wireless sensor networks; Proceedings of International Conference on Advances in Computing, Communications and Informatics (ICACCI)  (2013) pp. 1007–1011
  53. [53] M.M. Afsar, M. Younis; An energy- and proximity-based unequal clustering algorithm for wireless sensor networks; Proc. of the IEEE Conference on Local Computer Networks, Edmonton, Canada  (2014) pp. 262–269
  54. [54] X. Fan, F. Du; Shuffled frog leaping algorithm based unequal clustering strategy for wireless sensor networks; Appl. Math. Inform. Sci. Int. J., 9 (3) (2015), pp. 1415–1426
  55. [55] X. Min, S. Wei-ren, J. Chang-jiang, Z. Ying; Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks; Int. J. Electron. Commun, 64 (2010), pp. 289–298
Back to Top

Document information

Published on 10/04/17

Licence: Other

Document Score

0

Views 28
Recommendations 0

Share this document

claim authorship

Are you one of the authors of this document?