The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 1

ISSN 2229-5518

Study of Cluster Based Routing Protocols in

Wireless Sensor Networks

Sushruta Mishra, Alok Raj, Abhishek Kayal, Vishal Choudhary, Preksha Verma, Lalit Biswal

Abstract—New advancements in the technology of wireless sensors have contributed to the development of special protocols which are unique to sensor networks where minimal energy consumption is vital and very important. As a result, the focus and effort of researchers is on designing better routing algorithms for a given application and network architecture of interest. Flat-based routing protocols have been found to be less advantageous to clustering routing protocols when their performance are compared in a large-scale wireless sensor network scenario. This is due to the fact that clustering operation reduces the amount of redundant messages that are transmitted all over the network when an event is detected. This paper is an investigation of cluster -based routing protocols for wireless sensor networks.

Index Terms— Clustering Routing Protocols, W ireless Sensor Network, scalability, cluster head,Intra-Cluster,Load balancing,Routing

——————————  ——————————

1 INTRODUCTION

Wireless Sensor Network (WSN) is a collection of sensor nodes, which consists of transceiver and sensors in it. WSN is used in surveillance, environmental monitoring,
traffic monitoring and also in many real world applications. These sensor nodes gather information about the environment through measuring the mechanical, thermal, biological, chem- ical & magnetic phenomena. A sensor node consists of sensor to capture the data and transceiver to transmit data and a small battery to accomplish these tasks. The sensed data must be transferred to sink, which act as base station. But the data cannot be directly transmitted to sink because transmission range of a sensor node is very short. Thus the sensor nodes are grouped to form a cluster, in which sensed data in a cluster get transmitted through a gateway node. This gateway node in turns transmits the data to the sink node. Contemporary ad- vancements in nanotechnology, micro-electro-mechanical sys- tems (MEMS) technology, radio technology, digital electronics, digital signal processing and wireless communications have immensely contributed to the design of miniaturized and smart sensors. This technological progress made the concept of wireless sensor networking feasible and it created a lot of possibilities in using sensor nodes for monitoring remote events [2-4]. Wireless sensor network applications include tracking wildlife migration, monitoring infernos, reconnais- sance and surveillance, weather observation and pervasive computing [1-3, 5]. Wireless sensor networks comprises of numerous nodes that cooperatively operate in order to attain a global task. The architecture of a sensor network comprises of a sink and sensor nodes. Communication is carried out among the nodes to relay valuable data to the sink. This communica- tion can be affected by the time-criticality and accuracy of the desired data and other pertinent factors such as scarce energy resources and limited sensing, computing and communication capabilities [1, 3-4]. Sensor nodes can be deployed in geo- graphical areas where it can be extremely difficult to recharge the in-built batteries or even replace the nodes. Thus it is the goal of every sensor network design to increase the longevity of the network. One of the most energy-consuming operations in sensor networking is the reception and transmission of da- ta. An energy-efficient solution for this is to use low duty cycl- ing by strategically turning on and off the radio of sensor
nodes based on the demand to carry out a sensing task. Other means of conserving energy via minimizing redundant data transmission are data compression, data fusion, data aggrega- tion and data filtering [2-4]. A number of routing algorithms have been recently designed for wireless sensor networks [5-
6]. However, designing energy-aware routing protocols is
challenging as a result of the inherent energy constraints of the
sensor nodes. Researchers are currently investigating and de-
veloping clustering routing protocols with the aim of solving
the energy conservation problem [3, 7-12]. It has been stated in
the literature that though clustering may introduce overhead
in terms of network configuration and maintenance, cluster
based routing protocols still perform better and they possess
more desirable energy minimization capability when com-
pared to flat network topologies [3-4]. In this paper a survey of
cluster-based routing protocols is presented. The objective of
this work is to promote better understanding of clustering routing algorithms and to remark on the possible areas of im- provement which can be further investigated.

2 CLUSTERING AND ROUTING IN WSN

Figure 1 shows a simple cluster based network. From a routing perspective clustering allows to split data transmis- sion into intra-cluster (within a cluster) and inter-cluster (be- tween cluster heads and every cluster head and the sink) communication. This separation leads to significant energy saving since the radio unit is the major energy consumer in a sensor node. In fact, member nodes are only allowed to com- municate with their respective cluster head, which is respon- sible for relaying the data to the sink with possible aggrega- tion and fusion operations. Moreover this separation allows reduction of routing tables at both member nodes and cluster heads in addition to possible spatial reuse of communication bandwidth.

Intra-cluster communications

Most of the earlier work on clustering assumes direct (one- hop) communication between member nodes and their respec- tive cluster heads (Energy-efficient communication protocol for wireless sensor networks, 2000; Younis & Fahmy, 2004). All the

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 2

ISSN 2229-5518

membernodes are at most two hops away from each other. One-hop clusters makes selection and propagation of cluster heads easy, however, multi-hop intra-cluster connectivity is sometimes required, in particular, for limited radio ranges and large networks with limited cluster head count. Multi-hop routing within a cluster has already been proposed in wireless ad-hoc networks (Lin & Gerla, 1995). More recent WSN clus- tering algorithms allow multi-hop intra-cluster routing (Ban- dyopadhyay & Coyle, 2003; Ding et al., 2005).

Figure 1. A Cluster based network.

Inter-cluster Routing

Earlier cluster-based routing protocols such as LEACH (Ener-

gy-efficient communication protocol for wireless sensor networks,

2000) assume that the cluster heads have long communication
ranges allowing direct connection between every cluster head and the sink (Figure 3). Although simple, this approach is not only inefficient in terms of energy consumption, it is based on unrealistic assumption. The sink is usually located far away
from the sensing area and is often not directly reachable to all nodes due to signal propagation problems. A more realistic approach is multi-hop inter-cluster routing that had shown to be more energy efficient (Mhatre & Rosenberg, 2004). Sensed data are relayed from one cluster head to another until it reaches the sink as shown in Figure 1. Direct communication
between cluster heads is not always possible especially for large clusters (multi-hop clusters for instance). In this case, ordinary nodes located between two cluster heads could act as gateways (GW) allowing the cluster heads to reach each other. A gateway node is either common or distributed. A common (ordinary) gateway is located within the transmission range of two cluster heads and thus, allows 2-hop communication be- tween these cluster heads. When two cluster heads do not have a common gateway, they can reach each other in at least
3 hops via two distributed gateways located in their respective clusters. A distributed gateway is only reachable by one clus- ter head and by another distributed gateway of the second cluster head cluster. Inter-cluster communication in several proposals is achieved through organizing the cluster heads in a hierarchy as done in (Bandyopadhyay & Coyle, 2003) and (Manjeshwar & Agarwal, 2001). Multiple-level hierarchy al- lows better routing.

Energy efficiency and Load-balancing:

One of the most important objectives of hierarchical organiza-
tion in sensor networks is energy efficiency that allows longer
network lifetime. A cluster head can perform aggregation and
fusion operations on data it receives before relaying it to the
base station. In very dense networks, a subset of nodes may be
put into the low-power sleep mode provided that these nodes are chosen without affecting the network coverage and con- nectivity. In this context, a cluster head can efficiently sche- dule its member nodes states. Furthermore, medium access
collision can be prevented within a cluster if a round-robin strategy is applied among the member nodes. Collisions may require that nodes retransmit their data thus wasting more energy. Minimizing energy consumption on a per sensor basis is not sufficient to get longer network lifetime, load-balancing is required.

Load-balancing among all nodes:

Intra-cluster communications, where a member node sends data to its cluster head for further relaying toward the sink, put a heavy burden on the cluster heads. These later have, additionally, the responsibility of in-network data operations such as aggregation and fusion. Even if cluster heads are equipped with more powerful and durable batteries, this heavy burden could result in fast battery depletion at the clus-
ter heads and thus shorter lifetime compared to other sensor nodes. This is one possible load unfairness situation that may occur in cluster-based routing. This issue is usually addressed through cluster head rotation among nodes in each cluster.

Load-balancing among cluster heads:

In order to give each cluster head equivalent burden in the
network, many algorithms focus on balancing the intra-cluster
traffic load through the formation of nearly equal size (uni-
form) clusters. In fact, in clusters of comparable coverage and
node density, the intra-cluster traffic volume is more likely to
be the same for all clusters. In inter-cluster communication,
balanced intra-cluster traffic results in a highly skewed load
distribution on cluster heads. In single-hop communication
where cluster heads use direct link to reach the base station,

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 3

ISSN 2229-5518

the farther the cluster head, the more energy it consumes and the earlier will die. Even if multi-hop inter-cluster communica- tion is adopted, the nodes close to the base station are bur- dened with heavier traffic load leading to the so-called hot spot problem. This is due to the many-to-one traffic paradigm that characterizes WSN. Nodes in the hot spot area deplete faster their energy and die much faster than faraway cluster heads. This may lead to serious connectivity (network partition) and coverage problems at the base station vicinity. As a conse- quence both intra-cluster and inter-cluster traffic have to be considered jointly when designing a cluster-based routing algorithm. In other words, one have to consider minimizing energy consumption around the sink instead of minimizing the overall consumed energy in the network in order to achieve longer network lifetime.

3 CLUSTER BASED ROUTING PROTOCOLS

A. Low-Energy Adaptive Clustering Hierarchy

The Low-Energy Adaptive Clustering Hierarchy (LEACH) is
an adaptive and self-organizing protocol that minimizes ener-
gy consumption in wireless sensor networks [2, 7]. The under- lying idea behind LEACH is the use of randomized rotation of cluster heads so that energy dissipation is shared evenly among all participating sensor nodes [2-4, 6]. The operation of
LEACH can be categorized into two phases, namely; the set- up phase and the steady phase. In the set-up phase, a sensor node selects a random number in the range of 0 and 1. If this number is greater than a specified threshold, the sensor node will be elected as a cluster head. After selecting the cluster heads, advertisements will be done by the newly-elected clus- ter heads to other nodes. Upon the reception of these adver- tisements, each node will determine the cluster to belong to based on the signal strength of the advertisements. This is be- cause a strong signal strength means the cluster head is nearer to the node, hence minimum communication energy is re- quired. Afterwards, the nodes notify the nearest cluster heads of their interest in becoming a cluster member. After cluster formation, the cluster heads allocate the time for sending data based on a Time Division Multiple Access (TDMA) approach. Subsequently, the nodes start sensing and sending data to cluster heads. Data aggregation is performed by the cluster heads before finally sending data to the sink. After successful- ly conveying the data to the sink, the network goes into recon- figuration and it selects new cluster heads. Finally, LEACH uses single-hop communication [3, 5-7].

B. Threshold-Sensitive Energy-Efficient Sensor Network

Protocol

TEEN (Threshold-Sensitive Energy-Efficient Sensor Network)
and APTEEN (Adaptive Periodic Threshold Sensitive Energy-
Efficient Sensor Network) were proposed in [8-9] respectively
for time-critical applications. TEEN is a protocol developed to
respond to abrupt changes in the sensed attributes [3-5]. In the
beginning, cluster formation is done by grouping nodes that
are proximate to each other as clusters. Cluster heads of clus-
ters nearer to the sink will be assigned higher priority while
cluster heads of clusters farther from the sink will be assigned
lower priority [1-3, 5-6, 8]. Cluster heads disseminate two thresholds to cluster members after cluster formation which are namely; hard and soft threshold. Hard threshold is the least possible value of the sensed attribute that will activate nodes to turn on their radio for transmitting data to their clus- ter heads. The nodes will commence the transmission of data if the following conditions are true: (i) The sensed attribute‘s present value is greater than the hard threshold (ii) The sensed attribute‘s present value differs from the previous sensed val- ue by an amount equal to or greater than the specified soft threshold. As a result, soft threshold helps in reducing trans- missions when there are no significant changes in the sensed attributes [1, 3-6, 8]. APTEEN, which is an extension of TEEN, aims at capturing periodic data collections and reacting to time-critical events. It changes the threshold values used in TEEN according to user demands and application type. Clus- ter formation is done by the base station and elected cluster heads distribute these parameters, (i) Attributes, (ii) Thre- sholds, (iii) Schedule and (iv) Count Time. In APTEEN, the conditions for data transmission are just like TEEN. Data ag- gregation is performed by cluster heads to save energy [1, 3-6,
9].

C. Geographic Adaptive Fidelity Protocol

Geographic Adaptive Fidelity (GAF) is a protocol originally developed for mobile ad hoc networks (MANETs) but found useful for sensor networks [3, 5, 10]. The fundamental idea behind GAF is that for each grid area, a node serves as a lead- er to convey data to other nodes but unlike other cluster routing protocols, these leader nodes do not perform data ag- gregtion [4, 6, 10]. The protocol commences with forming a
virtual grid over the deployed area. Afterwards, nodes use a Global Positioning System (GPS) to associate themselves with a location in the virtual grid. Nodes associated with the same location are equivalent nodes hence they form clusters [3-5,
10]. GAF consists of three states, namely; discovery, active and sleeping state. In the discovery state, nodes discover other neighboring nodes in the same grid by exchanging messages for a specified time period. Afterwards, routing is performed during the allotted active time and radios of active nodes are turned off for a specified sleeping period. Load balancing is ensured by allowing nodes to change from sleeping to active states. Mobility is supported by ensuring that each node in the grid calculate its leaving time and send this to its neighbors. One of the sleeping nodes wakes and becomes active before the leaving time of the active node expires. GAF is designed both for non-mobility (GAF-basic) and mobility (GAFmobility adaptation) [3-6, 10].

D. Periodic, Event-driven and Query-based Routing Pro- tocol

Periodic, event-driven and query-based (PEQ) protocol is de- signed for networks which are used as surveillance systems operating under critical conditions. The basic idea behind PEQ is the use of hop level of nodes to minimize redundant data transmission [3-4, 11]. The protocol begins with configuring the entire network by finding the shortest distance from each sensor node to the sink. Initiation of this configuration process

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 4

ISSN 2229-5518

is done by the sink via broadcasting the hop value, time- stamp, and source address to nearest neighbors. Afterwards nodes will store, increment and send the hop level to the next neighboring nodes. Each node compares its hop value with the one in the packet. If the hop value is greater, update is car- ried out and retransmission is done. This process goes on until the whole network is configured [3-4, 11]. The sink broadcasts subscription message over the network just as in the configu- ration process. If a node detects an event matching the sink's interest, the node will send the event packet to its neighboring node. This event notification and data delivery process ends when the data reaches the sink. This protocol also implements an ACK-based repair mechanism [3-4, 11]. PEQ uses multi- hop communication which is simple and effective for long distance communication in a large network scenario. Low la- tency is ensured and energy consumption is minimized by using optimal path routing. Reliability is maintained by using an ACK-based repair mechanism. A major limitation is flood- ing and broadcasting of configuration and subscription mes- sages. This leads to redundant transmission and reception of data and mismanagement of scarce energy resources.

E. Clustering Periodic, Event-driven and Query-based

Routing Protocol

Clustering Periodic, Event-driven and Query-based (CPEQ) protocol is a cluster-based approach where sensor nodes with more energy are selected as cluster heads. Cluster heads form clusters and cluster members communicate with their respec- tive cluster heads [3-4, 11]. This protocol starts with network configuration just like in the PEQ protocol. The only difference here is the propagation of an additional field to specify the percentage of nodes that can become cluster heads. The process of cluster head selection is based on LEACH [3-4, 11]. After selecting the cluster heads, the next stage is the cluster configuration stage where cluster heads form their clusters by broadcasting notifications. This process is the same as the con- figuration phase of PEQ. Whenever a node senses an event they relay it to their respective cluster heads. This data routing scheme is also similar to the one used in PEQ.
Additionally, CPEQ also employs an ACK-based path repair mechanism just like in the PEQ algorithm [3-4, 11]. Data ag- gregation is performed by the cluster heads on the incoming data to reduce redundancy. Subsequently, cluster heads will transmit the aggregated data to the sink via the shortest path. The event and data delivery process is similar to the one em- ployed in PEQ [3-4, 11]. This algorithm possesses all the strengths of PEQ namely low energy consumption, support for low latency, support for reliability and simplicity. Another advantage of this algorithm is the aggregation of data which saves energy by reducing repetitive data transmission. How- ever a major limitation is the redundant transmission and re- ception of packets in the configuration process. In a highly dense network scenario high amount of energy will be wasted in the transmission of and listening to unwanted or unneces- sary packets.

F. Energy Efficient Inter-cluster Communication based

Routing Protocol

Energy Efficient Inter-cluster Communication based (ICE) al-
gorithm is a protocol designed for periodic, event-driven and
query-based networks. Message routing is accomplished via
the help of cluster heads and nodes nearest to each other with-
in two adjacent clusters. As a result data transmission is car-
ried out via short transmission [3-4, 12]. This protocol begins
with the setup phase where the network is configured just like
in the PEQ and CPEQ protocol. The cluster head selection is
based on LEACH [3-4, 12]. The cluster configuration process
where cluster heads form clusters by broadcasting notifica-
tions to neighboring nodes is similar to that of the CPEQ algo-
rithm. A unique property of this protocol is the discovery of free nodes which do not belong to any cluster. Free nodes send notification messages to adjacent nodes. These neighbor- ing nodes forward their requests to their cluster heads [3-4,
12]. This algorithm uses an improved version of the ACK- based path repair mechanism employed in PEQ and CPEQ. Whenever a cluster member has data to send to the sink, it selects one of its adjacent clusters to help relaying the data. The data will be transmitted to a node belonging to an adja- cent cluster and that node will send the message to its cluster head. By following this sequence, the data is finally delivered to the sink [3-4, 12]. This protocol has the benefits of CPEQ and PEQ, namely; data aggregation, support for reliability, simplicity and support for low latency. Energy is conserved as a result of short-range transmissions using nearest neighbors. Load-balancing, network longevity and fault tolerance is en- sured through the use of multi-path routing. Notifications are prioritized and least-cost path is used to provide Quality of Service (QoS). A limitation is the inability to form a logical line for clustering. This means no nearest neighbors will be discov- ered and data transmission will be negatively affected. Re- dundant transmission and reception of packets are highly like- ly to occur. Network management can be costly and difficult in a scenario where the network is mobile and growing.

G. Clustering Method for Energy Efficient Routing

(CMEER)

CMEER (Kang et al., 2007) is another attempt to achieve well distributed Cluster heads. In CMEER a node declares itself as a candidate to be a cluster head using equation 1 where P is
176 Sustainable Wireless Sensor Networks chosen higher than adopted values in LEACH. Each candidate advertises its in- tention to be a cluster head within its radio range. Each node (even candidate to be a cluster head) decides to join a given cluster head based on the received signal strength of the ad- vertisement message. In this way, the authors try to avoid re- dundant creation of cluster heads in a small area. The simula- tion results showed that CMEER outperforms LEACH in terms of energy consumption and network lifetime.

H. Distributed Energy Efficient Hierarchical Clustering

(DWEHC)

Distributed Energy Efficient Hierarchical Clustering (DWEHC) (Ding et al., 2005) aims to improve HEED by gene- rating balanced cluster sizes and optimizing the intra-cluster topology thanks to its location awareness. DWEHC creates a

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 5

ISSN 2229-5518

multi-level (instead of one-hop in HEED) structure for intra- cluster communication and limits a parent node‘s number of children. Each sensor ―s” calculates its weight after locating the neighboring nodes in its area using:
LEACH by about 67% to 83% in terms of network lifetime. This performance gain can be explained by the reduction of the number of transmissions and receptions thanks to data aggregation. However, the main limitation of PANEL is its assumption that the clusters are determined before deploy-

Wweight (s)

Eresidual (s) / Einitial (s) (R d / 6R)

ment and thus can not adapt to WSN dynamics.
where ―Eresidual(s)‖ and ―Einitial(s)‖ are respectively residual and initial energy at node ―s”, ―R” is the cluster range (a system parameter that corresponds to how far a node inside a cluster can be from the cluster head) and d is the distance between ―s” and neighboring node ―u”. In a neighborhood the node with largest weight would be elected as a cluster head and the re- maining nodes become members. At this stage member nodes are considered as 1-level nodes and communicate directly with the cluster head. If a member node can reach its cluster head using more than one hop while saving energy it will be- come an h-level member where ―h‖ is the number of hops re- quired to achieve the cluster head. Required energy to com- municate in a cluster can be computed using node‘s know- ledge of the distance to its neighbors. The cluster range ―R” is used to limit the number of levels. Even if HEED considers energy reserve in cluster head selection and aims to a well distributed cluster heads, simulation results showed that clus- ters generated by DWEHC are more balanced and that DWEHC achieves significantly lower energy consumption in intra-cluster and inter-cluster communication than HEED. However location information required by DWEHC is not necessarily and easily available. Many other location-aware clustering techniques have been proposed in the literature.

I. Position-based Aggregator Node Election (PANEL) PANEL (Buttyan & Schaffer, 2007) is a position-based cluster- ing routing algorithm for WSN. It elects one aggregator node for reliable and persistent data storage applications. PANEL assumes that the sensor nodes are deployed in a bounded area partitioned into geographical clusters. The clustering is deter- mined before the deployment of the network and each sensor node is pre-loaded with the geographical information of the cluster to which it belongs. At the beginning of each epoch a reference point is computed in each cluster by the nodes in a completely distributed manner depending on the epoch num- ber. Once the reference point is computed, the nodes in the cluster elect the node that is the closest to the reference point as the aggregator (cluster head) for the given epoch.

The reference points of the clusters are re-computed and the aggregator election procedure is re-executed in each epoch. This ensures load balancing in the sense that each node of the cluster can become aggregator with nearly equal probability. The communication overhead used in the election procedure is also used to establish the routing tables within the cluster. At the end of the aggregator node election procedure, the nodes also learn the next hop towards the aggregator elected for the current epoch. PANEL can be integrated with any posi- tion based routing protocol for inter-cluster communications. The authors proposed to experiment PANEL with the Greedy Perimeter Stateless Routing (GPSR) protocol (Karp & Kung,
2000). Simulation results showed that PANEL outperforms

J. Passive Clustering (PC)

Passive clustering (PC) (Kwon & Gerla, 2002) is an on demand clustering algorithm. It provides scalability and practicality for choosing the minimal number of forwarding nodes in the presence of dynamic topology changes. PC constructs and maintains the cluster architecture based on outgoing data packets piggybacking ―cluster related information”. Passive clus- tering eliminates setup latency and major control overhead of traditional clustering protocols by introducing two innovative mechanisms for the cluster formation: “first Declaration wins” rule and “gateway selection heuristic”. With the “first Declaration wins” rule, a node that first claims to be a cluster head rules the rest of nodes in its clustered area. The “gateway selection heuris- tic” provides a procedure to elect the minimal number of gateways. The algorithm defines several states in which a node can be. At cold start, all nodes are in the initial state. Nodes can keep internal states such as ―cluster head-ready” or
―gateway-ready” to express their readiness to be respectively a cluster head or gateway. A candidate node finalizes its role as a cluster head, a gateway (Full-GW or Dist-GW) or an ordi- nary node. Additional fields suggested by PC in the message header of each packet are:
• id : the identity of the originator of this message.
• state : this packer sender status in the network.
• CH1 and CH2 : these two fields are only used by a gateway
to announce its two cluster head addresses.
The reactive nature of PC motivated its combination with on demand routing protocols. Originally, PC was applied to reac- tive routing protocols like AODV (C. Perkins, 1999) and DSR (Johnson et al., 2001). The major overhead in these routing protocols is caused by the flooding of route queries. It was suggested to allow only non-ordinary nodes to rebroadcast query messages. The PC algorithm presents some shortcom- ings that have been targeted by several works. In (Rangaswa- my & Pung, 2002) the authors proposed to add alive packets to keep the cluster stability as it depends highly on the data packet traffic. Also, a sequence numbering to synchronize packets arriving from a source node is proposed. In fact if packets, containing different states, arrive out-of-order at the destination (i.e. the sending node changed its state between the transmissions of multiple packets) then the destination node will be misled about the true state of the source node. In addition, unnecessary rebroadcasts are eliminated when the final destination of the message is a cluster member. In WSN the PC algorithm was proposed in combination with directed diffusion (DD) in (Handziski et al., 2004) to mainly achieve energy efficiency. The main idea of the combination is to save energy in the flooding phases by allowing only cluster heads and gateways to 182 Sustainable Wireless Sensor Networks

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 6

ISSN 2229-5518

participate in them. Member nodes are only allowed to send data messages in the data sending phase. Under different network size and load, the combination showed best perfor- mances in terms of delivery ratio and average dissipated ener- gy. Motivated by the results shown in (Handziski et al., 2004) when applying the original PC along with directed diffusion paradigm other works have been proposed in order to achieve better performance of the combination. In (Mamun-or-Rashid et al., 2007) the selection of cluster heads and gateways are done using a heuristic of residual energy and distance. By us- ing residual energy the flooding nodes are chosen in an energy efficient manner. Distances are used to reduce overlapping region and so the number of gateways. The solution proposes to apply a periodic sleep and awake among cluster members. This technique is similar to the one proposed in LEACH and requires a synchronization process between nodes.

K. Energy Efficient Hierarchical Clustering (EEHC)

Energy Efficient Hierarchical Clustering (EEHC) (Bandyopad- hyay & Coyle, 2004) can be seen as an extension of LEACH with multi-hop intra clusters and a hierarchy of cluster heads to route data to the sink. In the single-level clustering of EEHC, each sensor in the network becomes a Volunteer cluster head with probability ―p”. It announces this to the sensors within k hops radio range. Any sensor that receives such ad- vertisements and is not itself a cluster head joins the closest cluster. If a sensor does not receive a cluster head advertise- ment within certain time duration it can infer that it is not within k hops of any volunteer cluster head and Cluster-based Routing Protocols for Energy Efficiency in Wireless Sensor Networks 175 hence becomes a forced cluster head. Data transmission to the sink can be performed using multi-hop routing through cluster heads organization in a multi-level hierarchy rooted at the sink. To do so, the single-level cluster- ing is repeated recursively at the level of cluster heads. This distributed process allows EEHC to have a time complexity of O (k1+k2+...+kh) where ―h” is the number of levels and ―ki” is the maximum number of hops between a member node and its cluster head in the ith level of hierarchy. Since spent energy in the network depends on ―p” and ―k”, the authors provide methods to compute the optimal values of these parameters that ensure minimum consumed energy. Simulation results showed significant energy saving when using the optimal pa- rameter values.

L. Hybrid Energy-Efficient Distributed Clustering (HEED) Both EEHC and LEACH do not consider energy in selecting cluster heads. HEED (Younis & Fahmy, 2004) brings one more step toward energy-efficient cluster-based routing with expli- cit consideration of energy. Selected cluster heads in HEED have relatively high average residual energy compared to member nodes. Additionally HEED aims to get a well- distributed cluster heads set over the sensor field. Indeed in HEED the probability that two nodes within the transmission range of each other to be cluster heads is small. It is worth mentioning that the main drawback of LEACH is that the ran- dom election of cluster heads does not ensure their even dis- tribution in the sensing field. It is quite possible to get multiple

cluster heads concentrated in a small area. In this case these area sensors are likely to exhaust their energy more quickly which may lead to insufficient coverage and network discon- nection. Distributing cluster heads evenly in the sensing area is one important goal to be met in order to ensure load balanc- ing and hence longer network lifetime. HEED periodically selects cluster heads according to a hybrid of their residual energy and intra-cluster communication cost. Initially to limit the initial cluster head announcements, HEED sets an initial percentage ―Cprob” of cluster heads among all sensors. The probability that a sensor node becomes a cluster head is

―CHprob” where CHprob = Cprob * Eresidual/Emax where ―Eresidual” is the current energy in the sensor, and ―Emax” is its maximum ener- gy. Afterwards every sensor goes through several iterations until it finds the cluster head that it can transmit to with the least transmission power. If it hears from no cluster head, the sensor elects itself to be a cluster head and sends an an- nouncement message to its neighbors. Each sensor doubles its

―CHprob” value and goes to the next iteration until its ―CHprob”

reaches 1. Therefore there are two types of status that a sensor
could announce to its neighbors:
• Tentative status: The sensor becomes a tentative cluster head if its CHprob is less than 1. It can change its status to a regular node at a later iteration if it finds a lower cost cluster head.
• Final status: The sensor permanently becomes a cluster head if its CHprob has reached 1.
At the final phase, each sensor makes a final decision on its status. It either picks the least cost cluster head or pronounces itself as cluster head. Simulation results showed that HEED outperforms LEACH with respect to the network lifetime and energy consumption distribution. However, HEED suffers from a consequent overhead since it needs several iterations to form clusters. In each iteration a lot of packets are broadcast.

2 CONCLUSION

Routing in sensor networks has attracted the attention of re- searchers and it has also posed interesting and important chal- lenges. Clustering routing protocols organize sensor nodes in such a way that propagation of message to the sink is achieved with minimal energy. Hierarchical (cluster-based) routing pro- tocols hold a great potential toward energy efficiency in WSN. Clustering algorithms have been a hot research area in the last few years. High energy nodes are often chose as cluster heads which are given the responsibility of data aggregation and transmitting data to the sink. This paper investigated selected clustering routing protocols and outlined their key features. Managing energy consumption individually at each sensor is far from being sufficient to maximize the WSN lifetime. A global management strategy with load balancing feature is required. to do so, clustering techniques have to provide low overhead cluster head rotation as well as optimal traffic distri- bution among cluster heads while keeping network connectiv- ity and coverage. Unequal clustering where both intra-cluster

http://www.ijser.org

The research paper published by IJSER journal is about Study of Cluster Based Routing Protocols in Wireless Sensor Networks 7

ISSN 2229-5518

and inter-cluster communications are considered is very promising. However, practical techniques need to be devel- oped to build such clusters without knowledge of the global network topology. Optimal (or even approximate) parameters estimation for successful clustering is very important but is not an easy task since WSN-specific constraints like energy, coverage and connectivity have to be satisfied. These parame- ters include mainly cluster heads rotation frequency that al- lows the best load balance with the lowest overhead, in addi- tion to the number of clusters and their size that maximize the network lifetime. Finally, network dynamics have to be han- dled appropriately. Network dynamics include possible nodes or sink mobility and topology changes due to death of one or more sensors in the field of interest. Suitable and very reactive solutions have to be provided mainly when a cluster head dies leaving orphan sensors, possible uncovered area and lack of inter-cluster connectivity.

REFERENCES

[1] Mohammad Ilyas (Editor) and Imad Mahgoub (Editor), ―Handbook of Sen- sor Networks: Compact Wireless and Wired Sensing Systems‖, CRC Press, LLC, pp. 120-138, 2005.

[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, ―Wire-

less Sensor Networks: A Survey‖, Elsevier Computer Networks

Journal, Volume 38, Issue 4, pp. 393-422, 15 March 2002.

[3] A. F. Salami, F. Anwar and A. U. Priantoro, An Investigation into Clustering Routing Protocols for Wireless Se nsor Networks, Sensors and Transducers Journal, Volume 105, Issue 6, June 2009.

[4] A. F. Salami, S. M. S. Bari, F. Anwar and S. Khan, Feasibility Analysis

of Clustering Routing Protocols for Multipurpose Sensor Networ k- ing, submitted to International Conference on Multimedia and Com- putational Intelligence, 2010.

[5] K. Akkaya and M. Younis, A Survey on Routing Protocols For Wire- less Sensor Networks, Elsevier Ad Hoc Network Journal, Volume 3, pp. 325-349, 2005.

[6] Jamal N. Al-Karaki and Ahmed E. Kamal, Routing Techniques in

Wireless Sensor Networks: A Survey, IEEE Wireless Communica- tions Journal, Volume 11, Issue 6, pp. 6-28, December 2004.

[7] W. R. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy- Efficient Communication Protocol For Wireless Microsensor Networks, in Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS ‗00), Volume 2, 10 pp., 4- 7 January 2000.

[8] A. Manjeshwar and D. P. Agarwal, TEEN: A Routing Protocol For

Enhanced Efficiency In Wireless Sensor Networks, in Proceedings of

the 15th International Symposium on Parallel Distributed Compu-

ting, pp. 2009-2015, April 2001.

[9] A. Manjeshwar and D. P. Agarwal, APTEEN: A Hybrid Protocol for

Efficient Routing and Comprehensive Information Retrieval in Wire- less Sensor Networks, in Proceedings of the 16th International Sym- posium on Parallel Distributed Computing, pp. 195-202, 2002.

[10] Y. Xu, J. Heidemann and D. Estrin, Geography-Informed Energy Conservation For Ad Hoc Routing, in Proceedings of the Internation- al Conference on Mobile Computing and Networking, Rome, Italy, pp. 70-84, 2001.

[11] A. Boukerche, R. W. N. Pazzi and R. B. Araujo, HPEQ – A Hierar- chical Periodic, Event-driven and Query-based Wireless Sensor Net- work Protocol, in Proceedings of the IEEE Conference on Local Computer Networks, pp. 560-567, 15-17 November 2005.

[12] A. Boukerche and A. Martirosyan, An Energy-Aware and Fault-

Tolerant Inter-cluster Communication based Protocol for Wireless

Sensor Networks, in Proceedings of the IEEE Global Telecommunica-

tions Conference (GLOBECOM ‗07), pp. 1164- 1168, 26-30 November

2007.

[13] A. Manjeshwar, D. A. (2002). Apteen: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks, 2nd International Workshop on Parallel and Distributed Com- puting Issues in Wireless Networks and Mobile computing, Lauderdale, FL.

[14] Abbasi, A. A. & Younis, M. (2007). A survey on clustering algorithms for wireless sensor networks.

[15] Al-Karaki, J. & Kamal, A. (2004). Routing techniques in wireless sen- sor networks: a survey, IEEE Wireless Commun

[16] Chandrakasan, A. P., Smith, A. C., Heinzelman, W. B. & Heinzelman, W. B. (2002). An application-specific protocol architecture for wire- less microsensor networks, IEEE Transactions on Wireless Communica- tions 1: 660 670.

[17] Ding, P., Holliday, J. & Celik, A. (2005). Distributed energy efficient hierarchical clustering for wireless sensor networks, IEEE Internation- al Conference on Distributed Computing in Sensor Systems(DCOSS’05), Marina Del Rey, CA.

[18] Karp, B. & Kung, H. T. (2000). Greedy perimeter stateless routing for

wireless networks, ACM Mobicom, Boston.

http://www.ijser.org