Software Networking

Vol: 2018    Issue: 1

Published In:   January 2018

Performance of Strategies for Hierarchical Clustering Routing in Wireless Sensor Networks

Article No: 1    Page: 1-26    doi: 10.13052/jsn2445-9739.2018.001    

Read other article:
1

Performance of Strategies for Hierarchical Clustering Routing in Wireless Sensor Networks

R. Altaharwa

University of Malaya, Kuala Lumpur, Malaysia

E-mail: Tahatrwa@siswa.um.edu.my

Received 21 August 2017; Accepted 22 October 2017;
Publication 2 February 2018

Abstract

The rapidly increased in Wireless Sensor Networks (WSN) demands the need to select the best techniques and strategies to save the energy in WSNs, to hence the life time in WSNs. Which provoke high energy consumption. It is important to conserve the energy and ensure a good transmission in the same time. So in this paper we survey the techniques and methods that are used in WSNs and classified, also we emerged the pros and cons for each method.

Keywords

  • Energy efficiency
  • Hierarchical
  • Clustering
  • Wireless sensor networks

1 Introduction

Wireless sensor network (WSN) is a complex system consists of a number of small wireless sensor nodes and a base station (BS). Sensor node consists of sensor, processor, memory, RF transceiver (radio), peripherals, and power supply units [1]. In the past two decades, wireless communication and sensor technology have been actively developed. With advances in microprocessor and software architecture, it is expected that WSN will be part of many future applications [2]. At the beginning the sensors were fixed, but the growing and prosperity in technology have demanded mobile sensors. On one hand, some real application obliges combined environments of mobile and static sensor nodes in the same network. On the other hand, other applications demand a complete mobile sensors environment [3].

Most researches focus on power consumption and how to elect the cluster head [4], while other research concern with the end user and the environment [5, 6], and some researches concern with the routing techniques [7]. Also, some researches concern with static sink [8, 9], while the others concern with mobile sink [10].

Different from existing studies, this paper classifies the clustering routing method, and discuss in details the hierarchical methods which take into consideration the energy efficient with the delay time and the packet loss rate. And summarize the limitations in current algorithms. Also, we hierarchize these methods in clear diagrams.

The remainder of this paper is organized as follows: Section 2 gives an overview about the types of wireless sensor networks and clustering methods. Section 3 presents strategies to increase the energy efficient in WSNs. Section 4 presents hierarchical mechanisms. While Section 5 discusses the merits and demerits and diagram the classification for these methods, and Section 6 summarizes the most popular algorithms and its limitations and future work.

2 The Types of WSNs and Clustering Methods

The most popular classification for WSNs depending on the environment. It is classified into five types: Terrestrial WSN, Under-ground WSN, Underwater WSN, Multimedia WSN, and Mobile WSN [11]. The other popular classification divided it to Structured and Unstructured network. The structure WSN is deployed in a pre-planned manner, while the unstructured WSN is dense collection of sensor-nodes. The advantage for the first type is the nodes can be deployed with lower network maintenance and management cost, while the maintenance in unstructured WSN such as managing connectivity and detecting failures is difficult [12].

The methods to increase the energy efficiency classified into three categories depending on geographical area, which called coverage method [13], Green method, concerned with preserving the environment and exploiting natural resources [14, 15] and the largest group is clustering method [16] which included the data Centric [17], hierarchical [18], and balancing [19]. We will talk in details about these classifications in section four.

Regarding clustering, naturally, grouping sensor nodes into clusters have been widely adopted by the research community to satisfy and achieve prolong network lifetime in large-scale WSN environments and high energy efficiency. In the hierarchical network structure each cluster has a leader, which is also called the cluster head (CH) and usually performs the special tasks, and several common sensor nodes (SN/MN) as members [20].

Transfer the data in small network is very fast and direct, but when the network become huge, the sensed data will need many links to reach to its destination. And mostly will make conjunctions in the network. Therefore, the network divided into two clusters or more to make the communication more effective and easier. Formatting the clusters and electing the cluster head are an important dilemma in wireless sensor networks and drastically effect energy dissipation in the network [21]. Recent researches concern with clustering wireless sensor networks like [12, 2224]. Recent researchers concern with clustering wireless sensor networks [12, 2224].

R. Devi et al. concern with selecting cluster head and route communication over the network to improve the packet communication and increase the life time. Matlab simulator was used to prove their results [20].

H. Bagci et al. proposed Disjoint Path Vector (DPV) algorithm, a distributed fault-tolerant topology control algorithm for heterogeneous wireless sensor networks which contains a huge number of sensor nodes with limited energy and several super nodes and computing capability with unlimited energy resources. The k-degree Anycast Topology Control problem was solved by DPV algorithm. The main aim is to assign each sensor’s transmission range such that each has at least k-vertex-disjoint paths to super nodes and the total power consumption is minimum [25].

Tong & Tang introduced another competition for cluster-heads after the first selection using a random number as in LEACH. The leach algorithm considered as the base stone in hierarchical methods to save the power consumption. The leach has two phases, setup phase and steady phase. In setup phase the cluster head election, cluster setup form and cluster scheduling. While the data aggregation, compression, and data transmission in steady phase. The random selection for CH will distribute dissipated the energy for all nodes in setup phase. Also compression data in steady phase will reduce the energy consumption. In more detail, to maintain the constant cluster heads number of n × p where p is the desired percentage of cluster heads and n is the number of total nodes [26].

While I. Almomani et al. decrease the energy consumption to achieve security method in WSN-DS, they classified four types of DoS attacks in WSNs dataset: The considered attacks are Scheduling attacks, Flooding, Gray-hole, and Blackhole. NS-2 simulation was used to simulate the results and collect 374661 records containing the signatures of these four attacks. The dataset containing malicious and normal network traffic. Mathematical validation was used to prove their correctness, 10-FoldCrossValidation with one hidden layer was used, and the percentages of classification accuracies of at-tacks for normal case was 99.8% [27].

3 Strategies to Increase the Energy Efficient in WSNs

The energy efficiency has become a matter of prime importance for wireless networks. Hence, there is a need to adopt energy-efficient architectures in next generation networks. The researcher classified the method to increase the energy efficient into three main categories as follows: Clustering and Routing methods, Coverage methods, and Green methods. The clustering and routing method includes the hierarchical and data centric methods as shown in Figure 1.

images

Figure 1 Strategies to increase the energy efficiency in WSNs.

3.1 Clustering and Routing Strategies

Energy efficient clustering in WSNs is well known optimization problems which have been studied widely to prolong lifetime of WSNs. The researchers classified the clustering methods into two main categories: Data Centric [17], and Hierarchical [18] as shown in Figure 1.

Regarding the data centric, C. Intanagonwiwat et al. suggested Direct Diffusion (DD). DD is a data centric method, where all nodes in this network are aware of its location, and this will enable selecting empirically best bathes according to processing data and caching in network, hence it will reduce the power consumption [28].

Cougar approach is another technique in data centric which was explored by Y. Yao et al. to increase the energy efficient by reducing the resource usage, through declarative queries. There is a query optimizer method to generate efficient query in plan network. The Cougar Project is supported by the DARPA SensIT program, for more information visit this website: http://www.cs.cornell.edu/database/cougar [29].

Normal SPIN forwards data to neighbor nodes but it does not ensure data delivery. So, J. Grover et al. explored Reliable Sensor Protocols for Information via Negotiation (Reliable SPIN). They based on acknowledgement from the sink to the intermediate nodes and the source node by using selective forwarding. The source node will be forward to the data packets again, if it has unacknowledged data packets. Matlab used to simulate their proposed technique [30].

In addition, about querying ACQUIRE mechanism was proposed by N. Sadagopan et al. in this mechanism an active query is forwarded through the network, and intermediate nodes use cached local information (within a look-ahead of d hops) in order to partially resolve the query. A completed response is sent directly back to the querying node, when the query is fully resolved. To calculate the energy costs associated with ACQUIRE, they based on mathematical modelling approach [31].

C. Patra et al. proposed Routing Rumor (RR), which remedy the tradeoff between delivery reliability and setup overhead. Also, D. Braginsky et al. evaluate and describe RR, but their study is not geographically correlated because it has not coordinate system or interest with it [8]. We will talk about hierarchical strategies in detail at Section 4.

3.2 Coverage Strategies

One of the most important issues in WSN is the coverage area, but when the coverage increase it will consume more energy, and decrease the life time in WSN. Fortunately, the researchers innovate many algorithms to reduce the conflicts among lifetime, coverage, and connectivity. We will mention in this study four algorithms as shown in Figure 2.

images

Figure 2 Coverage strategies to increase the energy efficiency in WSNs.

These algorithms are: Degree-constrained minimum-weight extension of the Connected Dominating Set (DCDS), Multi Objective Free Search algorithm (MOFS), Optimal Geographical Density Control (OGDC),and Nondominated Sorting Genetic Algorithm-II (NSGA-II). These algorithms summarized in (Table 1).

Table 1 Most popular methods in coverage to reduce the energy consumption

Reference Algorithm Features
NSGA-II: It improves the network lifetime and coverage while maintain the network connectivity. This algorithm is based on the genetic algorithm. This algorithm includes main phases as initialization and reproduction. Moreover, crowded comparison, and controlled elitism [13].
[32] DCDS Based on LAEEC to compute coverage area.Trade-off between coverage, energy consumption, lifetime, and constrain the node degree.
[33] MOFS Based on fitness functions and binary coding schemes.Reduce the energy consumption effectively by the reasonable selection parameters, and obtain high network coverage while equilibrium of energy consumption is also considered.
[34] OGDC Fully localization.Reduce the energy consumption by controlling the density of the active nodes.
[13] NSGA-II Improve the network lifetime and coverage while maintaining the network connectivity.Optimize the network coverage and node utilization simultaneously.

Let’s start by DCDS, the aim for this algorithm is to make a good trade-off between the network coverage, energy consumption and lifetime by an additional constrain on the node degree. They based on learning automata- based energy-efficient coverage protocol (LAEEC) to compute the coverage area. This algorithm (DCDS) maximizes the number of sleep nodes, hence saving more energy [32].

MOFS: the aim for this algorithm is solving tradeoff between equilibrium of energy, energy consumption, and network coverage in WSNs. This algorithm reduces the energy consumption effectively by the reasonable selection parameters, and obtain high network coverage while equilibrium of energy consumption is also considered. The Matlab software used to simulate and prove the efficiency of MOFS algorithm [33].

OGDC: this algorithm solved two sub problems. First: They proved that, if the radio range is at least double the sensing range, a complete coverage of a convex area implies connectivity in the set of working nodes. Second: under the ideal case that the node density is sufficiently high, they derive a set of optimality conditions under which a subset of working nodes can be chosen for complete coverage. This study was fully localization, and reduced the energy consumption by con-trolling the active nodes. NS-2 simulator was used to prove their results. But the demerit for this algorithms not suitable for large scale networks [34].

3.3 Green Strategies

With the rapid prosperity in wireless devices and communications increased along with surrounded environment. It demands for new trends in WSN known as Green Communication. The main goal for green communication is to save the energy depending on environment sources like harvesting strategies [35], the solar system, wind, and photovoltaic [14], or by minimizing the number of wake up nodes which didn’t use [36]. Figure 3 show these strategies.

images

Figure 3 Green strategies to increase the energy efficiency in WSNs.

The first strategy is the harvesting which is proposed as a remedy to extend the life-time of sensor nodes and enable maintenance-free operation. J. Zheng et al. concerned by energy harvesting methods (EH). Recently, EH has emerged as a promising technology to prolong the lifetime of communication networks according continuously harvesting green energy from environmental sources, such as the wind, vibrations, and sun [37].

J. Zheng et al. optimize harvesting in two dimensions. First: dynamic (activation) mode adaptation in temporal dimension. Second: Energy balancing in the spatial dimension. To remedy the temporal mode adaption in the mobile and unknown environment, the reinforcement learning techniques is used. Also, they based on decentralized optimization and the game theory to local information [14]. See “Figure 4 Energy Harvesting in wireless sensor network”.

images

Figure 4 Energy Harvesting.

The second strategy is the solar system, wind, and photovoltaic: Traditional wireless sensor network is always powered by batteries because it is easy to use. However, the limited capacity of battery, maximizing network lifetime become the most important challenge being studied in wireless sensor network. Generally, the transmission power is the major component of wireless sensor node’s power dissipation. So, the routing protocol using renewable resources is one of the main approaches of extending network life [38]. Figure 5 depicts the solar and wind system.

images

Figure 5 The solar and wind system.

The third strategy is minimizing the number of wake up nodes which didn’t use. The most popular problem known in sensor nodes is the idle listening dissipation, to address this problem, the wake-up radio scheme is proposed. C. Mahapatra et al. concern with wake-up radio scheme, wireless energy harvesting and error control coding to enhance the performance of WSNs and reduce the carbon footprint [36]. They depend on distributed dual sub gradient algorithm based on Lagrange multiplier method. Demonstrate compares the energy profile of a conventional transceiver versus that of a WUR-enabled transceiver. Compared to the traditional method, the main receiver (RX) in the WUR-enabled transceiver is activated only upon receipt of the wake-up command (WU) which is followed by the interrupted message generated by the WUR. The infrequent activation of RX facilitates a substantial energy conservation over the life-time of the wireless node. Clearly, WUR scheme is favourable only if RX is much larger than that of the power consumption of the WUR.

4 Hierarchical Strategies

The most efficient way to reduce the overall energy consumption within the cluster is hierarchical clustering by performing aggregation and fusion of data. In this survey we are concerned by hierarchical mechanism. We compare between ten different algorithms in hierarchical methods as shown in Figure 6. These algorithms are: Low Energy Adaptive Clustering Hierarchy (LEACH), Power Efficient Gathering in Sensor Information System (PEGASIS), Constrained shortest Path Energy Aware Routing (CSPEA), Threshold sensitive Energy Efficient sensor Network protocol (TEEN), Concentric Clustering Scheme (CCS), Hybrid Energy Efficient Distributed clustering (HEED), Distributed Energy-Efficient Clustering (DEEC). Stable Election Protocol (SEP), Energy Efficient Cluster Head Election protocol (EECHE), and Distributed Weight-based Energy Efficient Hierarchical (DWEHC).

images

Figure 6 The Hierarchal strategies.

4.1 The Hierarchal Algorithms

LEACH: as we mention before, the leach algorithm is the base stone in energy efficiency in hierarchical methods. It is self-organizing protocol, a clustering, adaptive, and a hierarchical routing protocols. LEACH is proposed to reduce the energy constraint in clustering by changing cluster head (CH) each round time to balance the energy consumption between the nodes in the network to extend the lifetime in WSNs.

images

Figure 7 Leach structure.

LEACH assume all nodes have the same limited energy and memory (homogeneous) also, the member node sends the data to CH, and CH send it to base station (BS) [39] as shown in “Figure 7. LEACH structure”.

LEACH round has two phases: Setup phase and steady-state. The clusters are constructed in the setup phase, while the sensed data will be transferred in the setup phase. At setup phase, every node selects a random number between 0 and 1, and then calculate a threshold formula T(n), as shown in Equation (1):

T(n)={ p1p*(rmodp1),N0,      otherwise (1)

If the selected random number is less than the threshold value, the node becomes a CH. Where p is the Cluster-Head probability (usually in LEACH the nodes become CH with a probability 5%), r: round number which is valued between 0 and 1/(P - 1) and N: is the set of nodes that have not been a CH. Nodes that are CHs in the first round cannot be CH again in the next 1/p rounds. After 1/(p - 1) rounds, the threshold value will be = 1, and all nodes are eligible again to become CH. Once the CHs are assigned, each CH will broadcast an advertisement message (ADV_CH) to the rest of the nodes by using the CSMA MAC protocol [40].

After that, each node selects a CH based on the Received Signal Strength Indication (RSSI) of the advertisement message by sending (JOIN_REQ) message to selected CH. Each node uses CSMA MAC protocol to transmit its selection. During that, all CHs must keep their receivers ON. Then when clusters are formed, each CH creates a TDMA schedule according to the number of nodes in its cluster and broadcasts it to them [41].

In the steady state phase, each sensor node collects and transmits data to its corresponding CH based on its allocated time in the TDMA schedule. The CHs receive all the data and aggregate them then compress them before being sent to the BS. After a certain time, which is pre-determined, the network starts another round by going back to the setup and steady state phases again [40].

Leach use a CDMA MAC or a TDMA to reduce inter-cluster and intra-cluster collision [42].

The energy consumption can be mitigating by organizing the sensor nodes in the clusters, because the power consumption will be based on the number of cluster heads and radio range. So, the information about the location for nodes and cluster heads will improve gathering sensed data and forward it to the sink [43].

PEGASIS: this protocol used the greedy approach to form chains rather than clusters to transmit the data. It starts from the farthest node to ensure that the nodes away from sink have close neighbours. Each node fuses its own data with the data received from the previous node and sends it to the next neighbour which is closer to base station than itself. So, the data is transferred node by node until it reaches the base station. Figure 8 illustrate how it works [7].

images

Figure 8 PEGASIS structure.

The Performance of the PEGASIS protocol is known for double or more in comparison with the LEACH protocol. It works into two phases as follow: Chain construction and Gathering data [44]. Chain construction has two steps. First one select the base station and sensor nodes by self-organization using greedy algorithm. At the second step, the base station performs the process of the chain form, then propagate information of the chain to sensor nodes. In chain form, the chain structure start at the farthest node from the base station. The selected node will be connected with the neighbour nodes, this step will continue until all nodes in the same range will be collected in the same chain, during this period, each node uses signal strength to measure the distance with neighbour nodes and then adjusts the signal strength so that only one node can hear its message, this node will be selected as a cluster head in this chain. At gathering data phase, each head node received sensing data from its neighbour node and transmit it to next neighbour head node until it delivers it to base station [7].

The demerits for this algorithm are data delay special in large-sized networks. Redundant data transmission, no consideration about the location of the base station and the bottleneck problem occurs at the headernode [44, 45].

CSPEA: the new technique in this approach that, it has a gateway, in each cluster to calculate the distance between the source and destination, in addition to a cluster head. In this protocol they choose best path for data routing, and so on, it will save the energy. In addition, this protocol entails less control packet overhead. Moustafa A. Youssef et al. focus on the minimum transmission distance for each sensor node to changing the network topology graph. They constrain in routing within cluster. The cluster head will send the ID, location for sensors to the gateway within cluster. While the gateway task is sensing the environment by receiving the data from sensors, then send report to cluster head using short-range radio transceiver, so the gateway node has less energy dissipated than sensors [46].

Each sensor can transfer sensed data or/and radio signal, so each sensor has one state of these four states: just sensing, relaying, both sensing and relaying, or neither sensing nor relaying (inactive). At the sensing state the nodes send data to the gateway, and in the relaying state relay messages from other active nodes. In sensing-relaying state the node sense target and relay a message from active nodes. And if it is not sensing or relaying it will be in an inactive state, the gateway determine the state for each sensor depending on the node battery level, current target position, and performance measures for desired network [7]. The gateway determine the routing depends on the following criteria: Sensor reorganization, Node’s battery energy level, and energy model adjustment. The demerit for this protocol, low performance under heavy load conditions [18].

TEEN: is based on the network mode of functioning, as proactive and reactive networks. Reactive networks reply directly to changes in the relevant parameters of interest, as opposed to passive data collecting proactivenetworks [47].

TEEN provides response times dynamically, the ability to control the trade-off between energy efficiency, and accuracy to the end user. It’s developed for reactive networks [48].

In this protocol the cluster-head broadcasts to its members, in addition at every cluster change time. Permanently the nodes sense their environment. A parameter from the attribute group reaches its hard threshold value first time. The node switches on its transmitter and sends the sensed data. Each node has an internal variable in the node, called the sensed value (SV), used to store the sensed value (SV). The nodes will transmit data again in the current cluster period, only when both of these conditions are verified [7]:

  1. The current value of the sensed characteristic is larger than the hard threshold (HT).
  2. The current value of the sensed characteristic differs from SV by an amount equal to or larger than the soft threshold (ST).

SV is set equal to the current value of the sensed characteristic, whenever a node transmits data.

Hard Threshold (HT): This is a threshold value for the sensed attribute. It is the absolute value of the characteristic beyond which, the node sensing this value must switch on its transmitter and report to its cluster head.

Soft Threshold (ST): This is a small change in the value of the sensed characteristic which triggers the node to switch on its transmitter and transmit.

The merits for TEEN protocol are: this protocol is suited for time critical data sensing applications like explosion detection, intrusion detection etc. The energy consumption in this protocol can be much less than in the proactive network, the ST can be varied, depending on the criticality of the sensed characteristic and the target application, the user can control the trade-off between accuracy and energy efficiency, the user can change the attributes as required at every cluster change time [49].

On the other hand, the demerits for this protocol are: this protocol is not well suited for applications where the user needs to get data on a regular basis, because if the thresholds are not reached, the nodes will never communicate, the user will not get any data from the network at all and will not come to know even if all the nodes die or still work. Another dilemma with this protocol is that a practical implementation would have to ensure that there are no collisions in the cluster [18]. To avoid this problem, they used the TDMA scheduling of the nodes, but this solution will increase the delay in the reporting of the time-critical data. The possible solution to this problem is CDMA.

The HT tries to decrease the number of transmissions by allowing the nodes to transmit only when the sensed characteristic is in the range of interest. The ST further decrease the number of transmissions by eliminating all the transmissions which might have otherwise occurred when there is little or no change in the sensed characteristic once the HT [47].

CCS: this algorithm improve and solve the loopholes in PEGASIS algorithm. The idea in this algorithm is to determine the location of the base station. In CCS, the network is divided into levels of concentric circular tracks. The nearest track to the BS is called level-1, second one level-2, and so on [18]. One node in each track selected as a head node. Each head node transfers the data of its own location to both the upper and lower level head node in one grade. In the phase of the data transfer, all nodes send the data to the nearest node from them-selves along the chain. The node receives the data and collect its own data and transfer these data to the next node. Head node receives at most two data messages. Head node in each level transfer the data to the lower Head node and at last, level 1 Head node transfers these data to the BS, “Figure 9 depicts the CCS structure” [50].

images

Figure 9 CCS structure [50].

The drawbacks for this algorithm are of the protocol are (i) unequal in sensor node allocation in each level, (ii) large delay on long chain, (iii) based on location to elect the cluster head for next hop instead the residual energy of sensor nodes which dissipates the energy of cluster head quickly on the path between cluster head and even energy hole will appear in the network and (iv) residual energy is not taken into account to select the cluster head [51].

HEED: the main idea for this approach is that it depended on residual energy in nodes to select the cluster head to prolong the lifetime in WSNs by distributing energy consumption into clusters. And minimizing control overhead. Also, this protocol supporting scalable data aggregation [52]. This protocol imposed that, sensor nodes can control their transmission power level regardless about node capabilities, or distribution of nodes. The cluster formation on HEED algorithm depend on two hybrid combination factors. First factor based on the node’s residual energy, while the other factor depends on the intra-cluster communication cost. Each sensor node set probability to be a cluster head based on Equation (2) [7].

CH=Cprob·(EresidualEmax)(2)

Where CHprob is not allowed to fall below a certain threshold that is selected to be inversely proportional to Emax, Cprob is required initial percentage energy for cluster heads in the networks, Eresidual is the current residual energy of the node and Emax is the maximum energy corresponding to the fully charged battery [18]. This protocol coming as improved the LEACH, but it has some drawbacks as: The cluster topology fails to achieve minimum energy consumption in intra-cluster communication. The clusters are not well balanced, generating much more cluster head than expected. There is no awareness about heterogeneity [7, 52].

DEEC: this is a heterogeneous scenarios [53]. Also it is improved for the SEP algorithm. So, it is better than the SEP and the LEACH algorithm. In Addition, this algorithm divided the network into clusters, in each cluster the cluster head selected based on the residual energy of each node and average energy of the network [54]. In addition, they have two types of nodes in this algorithm; normal and advance nodes [18]. The DEEC does not need to know any global knowledge of energy at every election round, because it does calculate the average energy of the network at the beginning and use it as a reference energy each time. In addition the DEEC achieve good performance in multi-level heterogeneous, hence it is better than SEP algorithm [54].

To calculate the energy for each node, they should calculate the average probability for each nod as the following Equations (3), (4).

Padv=Popt1+am(3)Pnrm=Popt(1+a)1+am(4)

Where Padv, and Pnrm represent the advance probability and normal probability respectively. Popt optimal probability, a is times more energy than the normal ones and m is the fraction of the advanced nodes [54].

The drawbacks for this algorithm are Lacking overload problem of cluster-head, lacking consideration about the location of the clusters during the cluster-head selection, and lacking consideration of more complicated scenarios, e.g., the packet loss rate and the link quality [55].

SEP: it is improved for the LEACH algorithm. Georgios Smaragdakis Ibrahim, et al. supposed two type of nodes (normal and advance nodes) in this algorithm to deal with heterogeneous nodes because each node has a different level of energy. The advantage nodes have more energy than the normal nodes. The cluster head is one from the advantage nodes. They used weighted election probabilities to select the cluster head based on their energy. In their study they dealt only with two-level hierarchical, and two type of nodes. They used the characteristic parameters of heterogeneity (m), and energy factor between advanced and normal nodes (α), also supposed the initial energy = (Eo) in normal sensor, and the energy of each advanced node is Eo ⋅ (1 + α). Thus the total energy of the new heterogeneous setting is equal to: n ⋅ (1 - m) ⋅ Eo + n ⋅ m ⋅ Eo ⋅ (1 + α) = n ⋅ Eo ⋅ (1 + α ⋅ m) [56].

In SEP, they based on weighted election probabilities to elect the CH. Also, they ensure that the CH election is random. So, it’s heterogeneous and based on the fraction of energy to measure the energy in each node [53].

EECHE: this algorithm improved the Prim’s algorithm, which based on shortest connection networks [57]. Kumar Dilip et al. supposed there is some sensor nodes use additional energy resources. They based on the residual energy to elect the cluster heads. They based on TDMA schedule between the operations in the network. The CH broadcast the TDMA schedule to all sensor nodes, the participated nodes will stay on, while the remaining nodes will turn off. This algorithm balances the energy consumption which are close to the sink and decrease the energy consumption to the nodes which are far away from the sink. This algorithm suitable for small sized wireless networks [4].

DWEHC: it is presented by Ding Ping et al. to improve the HEED algorithm. They aimed to optimize the intra-cluster topology and balanced cluster sizes. DWEHC consider residual energy to select the CH as HEED, in addition it’s construct a multi-level structure for intra-cluster communication and limits a parent node’s number of children. The weight for each node calculated based the following equation [58]:

Wweight(S)=Eresidual(s)Einitial(s)uRd6R(5)

Where Eresidual(s) is residual energy at node s, Einitial(s) is initial energy at node s, R is the range between the node and the CH, and the distance between node s and the neighboring node u is d. The largest weighted node will be selected as CH, the other member nodes will be distributed into two levels. In level 1 the member nodes will communicate with the CH, while in level 2: the communication will be through level 1 [48], as shown in Figure 10.

images

Figure 10 Multilevel in DWEHC.

The eminently demerits for this algorithms are: the overhead in large control messages and less stability period [18].

The drawback for this algorithm are less stability period. And overhead in large control messages [7].

These are the most popular algorithms in hierarchical clustering routing in wireless sensor networks. We summarize the limitations in these algorithms in (Table 2) in next sub section.

4.2 Merits and Demerits

In this section, we will emerge routing protocols in wireless sensor networks, and highlighted the limitation for each algorithm in this table:

Table 2 The limitation of Hierarchical Algorithms

Protocol Limitations∖Problem(s)
LEACH The energy consumption to transfer sensing data from a head node to the base station is too large.If the network would become larger, it may not reach the sensing data from a head node to the base station directly.
TEEN This protocol is not well suited for applications where the user needs to get data on a regular basis.There are no collisions in the cluster that a practical implementation.
PEGASIS Redundant data transmission.No consideration about the location of the base station.The bottleneck problem occurs at the header node.Loopholes problems.
HEED The cluster topology fails to achieve minimum energy consumption in intra-cluster communication.The clusters are not well balanced.Generated a lot of cluster head than expected.There is no aware of heterogeneity.
CSPEA Not good under heavy load condition.
SEP It is dealing with two-level hierarchical.It is dealing with two type of nodes.
DWEHC Less stability period.Overhead in large control messages.
EECHE It is just suitable for small sized wireless networks.

5 Summarizes the Most Popular Algorithms

In this performance, we presented routing protocols in wireless sensor networks, and discussed the different research aspects and strategies proposed by research in WSN. We highlighted the important drawback in each algorithm. We summarize the most eminent limitations in these algorithms in (Table 2). In addition, we discuss the most popular applications for wireless senor networks in real life.

This study is an attempt towards segregation as well as amalgamation of hierarchical clustering routing algorithms and its applications based on wireless sensor networks.

In future, this work can be further expanded to include more applications in urban areas based on smart grid techniques in WSNs and constantly growing in this field. Also, we want to implement the smart grid wire-less sensor networks in next generation and develop it to save the energy consumption with high quality rate in transfer the data.

5.1 List of Notations and Abbreviations

BS Base Station.
CCS Concentric Clustering Scheme.
CH Cluster Head.
CSPEA Constrained shortest Path Energy Aware Routing.
DCDS Degree-constrained minimum-weight extension of the Connected Dominating Set.
DD Direct Diffusion.
DEEC Distributed Energy-Efficient Clustering.
DPV Disjoint Path Vector.
DWEHC Distributed Weight-based Energy Efficient Hierarchical.
EECHE Energy Efficient Cluster Head Election protocol.
EH Energy Harvesting.
HEED Hybrid Energy Efficient Distributed clustering.
HT Hard Threshold
LEACH Low Energy Adaptive Clustering Hierarchy.
MN Member Node.
MOFS Multi Objective Free Search algorithm.
NSGA-II Nondominated Sorting Genetic Algorithm-II.
OGDC Optimal Geographical Density Control.
PEGASIS Power Efficient Gathering in Sensor Information System.
Reliable SPIN Reliable Sensor Protocols for Information via Negotiation.
RR Routing Rumor.
SEP Stable Election Protocol.
ST Soft Threshold
TEEN Threshold sensitive Energy Efficient sensor Network protocol.

Acknowledgements

The author wish to thank his supervisors: Prof. Datin Dr. Sameem Binti Abdul Kareem and Dr. Ali Mansoor.

References

[1] Y. Zhao and C. Jiang (2010). “Research about improvement of LEACH protocol,” in Second International Conference on Information Science and Egineering (ICISE2010), pp. 2281–2284.

[2] L. Borges, F. Velez, and A. Lebres (2014). Survey on the Characterization and Classification of Wireless Sensor Networks Applications. IEEE Commun. Surv. Tutorials, 1.

[3] S. Awwad, C. Ng, and N. Noordin (2011). Cluster based routing protocol for mobile nodes in wireless sensor network. Wireless Pers. Commun.

[4] D. Kumar, T. C. Aseri, and R. Patel (2009). EECHE: Energy-efficient cluster head election protocol for heterogeneous wireless sensor networks. Int. Conf. Adv. Comput. Commun. Control., 75–80.

[5] Z. H. I. Zhao, J. Feng, and B. A. O. Peng (2016). A Green distributed signal reconstruction algorithm in wireless sensor networks. Spec. Sect. GREEN Commun. Netw. 5G Wirel. 4.

[6] A. Abrol, S. Member, R. K. Jha, and S. Member, Power Optimization in 5G Networks: A Step Towards Green Communication, pp. 1355–1374.

[7] A. Nayyar and A. Gupta (2014). A comprehensive review of cluster-based energy efficient routing protocols in wireless sensor networks. Int. J. Res. Comput. Commun. Technol. 3, 104–110.

[8] D. Braginsky and D. Estrin (2002). “Rumor routing algorthim for sensor networks,” in Proceedings of 1st ACM International Workshop on Wireless Sensor Networks Applications (WSNA ’02), p. 22.

[9] J. Yu, S. Ren, S. Wan, D. Yu, and G. Wang (2012). A stochastic k – coverage scheduling algorithm in wireless sensor networks. Int. J. Distrib. Sens. Networks.

[10] C. Zhu and G. Han (2017). A honeycomb structure based data gathering scheme with a mobile sink for wireless sensor networks. Peer-to-Peer Netw. Appl., 484–499.

[11] J. Yick, B. Mukherjee, and D. Ghosal (2008). Wireless sensor network survey. Comput. Networks 52, 2292–2330.

[12] T. Kapoor, K. K. Sharma, and S. Chauhan (2014). “Literature Survey on Energy efficient routing in Wireless Sensor Networks,” Int. J. Comput. Appl. 5, 1–4.

[13] S. M. Jameii, K. Faez, and M. Dehghan (2015). Multiobjective optimization for topology and coverage control in wireless sensor networks. Int. J. Distrib. Sens. Networks.

[14] Z. Zheng, X. Zhang, and Lin X. Cai, R. Zhang and X. Shen (2014). Sustainable Communication and Networking in Two-Tier Green Cellular Networks – GREEN MEDIA. IEEE Wirel. Commun., 47–53.

[15] M. Eeting and M. Ali Imran (2011). How Much Energy Is Needed To Run a Wireless Network? IEEE Wirel. Commun., 1–24.

[16] R. Asorey-Cacheda, A.-J. Garcia-Sanchez, F. Garcia-Sanchez, and J. Garcia-Haro (2017). A survey on non-linear optimization problems in wireless sensor networks. J. Netw. Comput. Appl., 1–20.

[17] C. Patra and P. Bhaumik and Ms. Debina Chakroborty (2010). Modified Rumor Routing for Wireless Sensor Networks. Int. J. Comput. Sci. Issues, 7, 31–34.

[18] I. Ouafaa, K. S.-Dd, L. Jalal, and E. H. Sa (2016). Recent advances of hierarchical routing protocols for adhoc and wireless sensor networks: A literature survey. BİLİŞİM Teknol. DERGİSİ, CİLT 9, 71–79.

[19] F. Bouabdallah, N. Bouabdallah, and R. Boutaba (2009). On balancing energy consumption in wireless sensor networks. IEEE Trans. Veh. Technol. 58, 2909–2924.

[20] R. Devi, A. Kumar, and V. Dhawan (2017). A node prioritization based load balancing approach to improve cluster head selection in wireless sensor network. Int. J. Curr. Trends Eng. Res. 3, 8–12.

[21] Q. Wang, E. Kulla, G. Mino, and L. Barolli (2014). “Prediction of Sensor Lifetime in Wireless Sensor Networks Using Fuzzy Logic,” in Proceedings of IEEE 28th International Conference on Advanced Information. Networking Applications (AINA 2014), Canada, pp. 1127–1131.

[22] P. S. Mann and S. Singh (2016). Performance analysis of energy-efficient routing protocol for wireless sensor networks, (IASIR: USA),pp. 126–129.

[23] L. Aziz, S. Raghay, H. Aznaoui, T. Marrakech, and C. Author (2017). A new enhanced version of vleach protocol using a smart path selection. Int. J. GEOMATE, 12, 28–34.

[24] S. B. Amsalu, W. K. Zegeye, D. Hailemariam, Y. Astatke, and F. Moazzami (2016). “Energy efficient Grid Clustering Hierarchy (GCH) routing protocol for wireless sensor networks,” in 2016 IEEE 7th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON 2016), NY, USA.

[25] H. Bagci, I. Korpeoglu, and A. Yazıcı (2015). A distributed fault-tolerant topology control algorithm for heterogeneous wireless sensor networks. IEEE Parallel Distrib. Syst. 26, 914–923.

[26] M. Tong and M. Tang (2010). “LEACH-B: An improved LEACH protocol for wireless sensor network,” in Proceedings of 6th International Conference on Wireless Communication Networking & Mobile Computing (WiCOM 2010), China, pp. 2–5, 2010.

[27] I. Almomani, B. Al-Kasasbeh, and M. Al-Akhras (2016). WSN-DS: A Dataset for intrusion detection systems in wireless sensor networks. J. Sensors, Hindawi Publ. Corp., vol. 2016.

[28] C. Intanagonwiwat, R. Govindan, and D. Estrin (2000). “Directed diffusion: A scalable and robust communication paradigm for sensor networks,” Proceedings of the 6th Annual International Conference on Mobile Computing Networks (MobiCom ’00), Massachusetts, USA, pp. 56–67.

[29] Y. Yao and J. Gehrke (2002). The cougar approach to in-network query processing in sensor networks. ACM SIGMOD Rec. 31, 9–18.

[30] J. Grover, M. Sharma and Shikha (2014). Reliable SPIN in Wireless Sensor Network: A Review. IOSR J. Comput. Eng. 16, 79–83.

[31] A. Helmy (2003). The ACQUIRE mechanism for effcient querying in sensor networks. Electr. Eng., 149–155.

[32] Akbari Torkestani, J. (2013). An adaptive energy-efficient area coverage algorithm for wireless sensor networks. Ad Hoc Networks, 11, 1655–1666.

[33] Zhou, H., Liang, T., Xu C., and Xie, J. (2012). Multiobjective coverage control strategy for energy- efficient wireless sensor networks. Int. J. Distrib. Sens. Networks, 11.

[34] Zhang, H., and Hou, J. C. (2005). Maintaining sensing coverage and connectivity in large sensor networks. Ad Hoc Sens. Wirel. Networks, 1, 89–124.

[35] Gilbert, J. M., and Balouchi, F. (2008). Comparison of energy harvesting systems for wireless sensor networks. Int. J. Autom. Comput. 5, 334–347.

[36] Mahapatra, C., Sheng, Z., Kamalinejad, P., Leung, V. C. M. and Mirabbasi, S. (2016). Optimal Power control in Green Wireless Sensor Networks with Wireless Energy Harvesting, Wake-up Radio and Transmission control. IEEE Access,SPECIAL Sect. ENERGY Harvest. Scav. Technol. ALGORITHMS, Commun. Protoc. 5, 1–1.

[37] Zheng, J., Cai, Y., Shen, X., Zheng, Z. and Yang, W. (2015). Green energy optimization in energy harvesting wireless sensor networks. IEEE Commun. Mag., 53, 150–157.

[38] Liu, W. and Wu, Y. ( 2013). Routing protocol based on genetic algorithm for energy harvesting-wireless sensor networks. IET Wirel. Sens. Syst. 3, 112–118.

[39] S. Singh, (2015). A novel fault tolerant routing protocol for mobile wireless sensor network based on LEACH. Int. Res. J. Eng. Technol., 1230–1235.

[40] Heinzelman, W. R., Chandrakasan, A. and Balakrishnan, H. (2000). Energy-efficient communication protocol for wireless microsensor networks. Proc. 33rd Annu. Hawaii Int. Conf. Syst. Sci. 1, 10.

[41] Liu, H., Li, L. and Jin, S. (2011). Cluster number variability problem in LEACH. Lect. Notes Comput. Sci., 6905.

[42] Boyinbode, O., Le, H., Mbogho, A., Takizawa, M. and Poliah, R. (2010). A Survey on Clustering Algorithms for Wireless Sensor Networks,” 13th Int. Conf. Network-Based Inf. Syst. (NBiS), 8, 259–268.

[43] Junping, H., Yuhui, J. and Liang, D. (2008). A time-based cluster-head selelction algorithm for LEACH. IEEE Symp. Comput. Commun., Morocco, 1172–1176.

[44] Ray, A. and De, D. (2017). Performance evaluation of tree based data aggregation for real time indoor environment monitoring using wireless sensor network. Microsyst. Technol. 23, 4307–4318.

[45] Liu, Z., Zheng, Q., Xue, L. and Guan, X. (2012). A distributed energy-efficient clustering algorithm with improved coverage in wireless sensor networks. Futur. Gener. Comput. Syst., 28, 780–790.

[46] Youssef, M., Younis, M. and Arisha, K. (2002). A constrained shortest-path energy-aware routing algorithm for wireless sensor networks. IEEE Conf. Publ., 794–799.

[47] A. M. and D. Agrawal (2001). TEEN: a routing protocol for enhanced efficiency in wireless sensor Networks. in Proceedings 15th Int. Parallel Distrib. Process. Symp., 2009–2015.

[48] Sharma N. and Nayyar, A. (2014). A comprehensive review of cluster based energy efficient routing protocols for wireless sensor networks. Int. J. Appl. or Innov. Eng. Manag. 3, 441–453.

[49] Guerroumi, Badache, N. and Moussaoui, S. (2015). Mobile sink and power management for efficient data dissemination in wireless sensor networks. Telecommun. Syst. 58, 279–292.

[50] Jung, S. M., Han, Y. J. and Chung, T. M. (2007). The concentric clustering scheme for efficient energy consumption in the PEGASIS. Int. Conf. Adv. Commun. Technol. ICACT, 1, 260–265.

[51] Velmani, R. and Kaarthick, B. (2015). An efficient cluster-tree based data collection scheme for large mobile wireless sensor networks. IEEE Sens. J. 15, 2377–2390.

[52] Younis, O., Member, S. and Fahmy, S. (2004). HEED: A hybrid, efficient, distributed clustering approach for ad hoc sensor networks. IEEE Trans. Mob. Comput. 3, 366–379.

[53] Rahman, M. M., Miah, M. S. and Sharmin D. (2016). Cognitive improved LEACH (CogILEACH) Protocol for Wireless Sensor Network. Trans. Networks Commun. 4.

[54] Qing, L. Zhu, Q. and Wang, M. (2006). Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks. Comput. Commun. 29, 2230–2237.

[55] Hong, Z. Wang, R. and Li, X. (2016). A clustering-tree topology control based on the energy forecast for heterogeneous wireless sensor networks. IEEE/CAA J. Autom. Sin. 3, 68–77.

[56] Smaragdakis, G. Matta, I. and Bestavros, A. (2004). “SEP: A stable election protocol for clustered heterogeneous wireless sensor networks,” Second Int. Work. Sens. Actor Netw. Protoc. Appl. (SANPA 2004), 1–11.

[57] R. C. Prim, (1957). Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389–1401.

[58] Ding, P. Holliday, J.and Celik, A. (2005). Distributed energy-efficient hierarchical clustering for wireless sensor networks. IEEE Int. Conf. Distrib. Comput. Sens. Syst., 322–339.

Abstract

Keywords

1 Introduction

2 The Types of WSNs and Clustering Methods

3 Strategies to Increase the Energy Efficient in WSNs

images

3.1 Clustering and Routing Strategies

3.2 Coverage Strategies

images

3.3 Green Strategies

images

images

images

4 Hierarchical Strategies

images

4.1 The Hierarchal Algorithms

images

images

images

images

4.2 Merits and Demerits

5 Summarizes the Most Popular Algorithms

5.1 List of Notations and Abbreviations

Acknowledgements

References