Performance Evaluation of Clustering Algorithms in Wireless Sensor Networks (WSN). Energy Efficiency of S-Web and LEACH

Master's Thesis 2013 35 Pages

Computer Science - Miscellaneous







2.1 Clustering ad hoc networks
2.2 Advantages of Clustering
2.3 Challenges for Clustering Algorithms
- Limited Energy:
- Constrained resources:
- Secure Communication:
- Cluster formation and CH selection:
- Load balancing:
- Minimal cluster count:
- Synchronization:
- Data Aggregation:
- Fault-tolerance:
- Quality of Service (QoS):
2.4 Clustering Schemes for Sensor Networks
2.4.1 Optimizing Cluster Organization
2.4.2 Averaging Power Consumption
2.4.3 Scheduling Active and Non-Active Nodes
2.5 Clustering Algorithms
2.5.1 Low-Energy Adaptive Clustering Hierarchy (LEACH):
2.5.2 Sensor Web or S-WEB:
2.5.3 Energy Efficient Clustering Scheme (EECS):
2.5.4 Hybrid Energy Efficient Distributed Clustering (HEED):
2.5.5 Energy-efficient unequal clustering (EEUC):
2.5.6 Power-efficient and adaptive clustering hierarchy (PEACH):

CHAPTER 3 Problem Definition and Implementation
3.1 Problem Definition
3.2 Implementation

CHAPTER 4 Results
4.1 First scenario (Normal Node to Normal Node)
4.2 Second scenario (Normal Node to Cluster Head)
4.3 Third scenario (Cluster Head to Normal Node)
4.4 Fourth scenario (Cluster Head to Cluster Head)
4.5 Fifth scenario (Random)

CHAPTER 5 Conclusion and Future Work



illustration not visible in this excerpt


Wireless Sensor Networks (WSNs) are highly integrated technologies applying sensors, microcontrollers and wireless networks technologies. Wireless sensor networks (WSNs) is a promising technology that has a large spectrum of applications such as, battlefield reconnaissance, border protection and security surveillance, preparing forecasts, severe environment detection, volcano monitoring, disaster management. WSNs operate unattended in harsh environments with limited energy supplies that can’t be practically changed or recharged. Thus energy efficiency is a critical design issue which must be addressed.

Clustering plays an effective role in judicious use of dwindling energy resources of the deployed sensor nodes. Nodes are grouped into clusters and a specific designated node, called the cluster head is responsible for collecting data from the nodes in its cluster, aggregating them and sending to the BS, where data can be retrieved later. Besides energy efficiency, clustering has many other advantages like reduced routing overhead, conservation of communication bandwidth, stabilized network topology, network stability etc.

In this research, we study the energy efficiency of two clustering algorithms, S-Web and LEACH and compare them for network lifetime. Simulation results show that the S-Web clustering mechanism achieves a noticeable improvement in the network lifetime.


Clustering, Energy Efficiency, SWEB, Wireless Sensor Networks, LEACH, Network Lifetime


I am heartily grateful to my supervisor, Mr. Ghulam Rasool Begh, whose patient encouragement, guidance and insightful criticism from the time to time helped me to establish the overall direction of the research.

I also express profound gratitude to my parents who stood by me through thick and thin and all the friends whose valuable suggestions and support helped me during the completion of my thesis.


An information processing center where all data that have been sensed by the sensor nodes are collected, processed and stored for later retrieval.

It is a group of nodes in a network that are grouped together to reduce energy consumption during data transmission.

It is a node responsible for collecting data from other nodes, aggregates them and sends them to the base station where they can be retrieved later.

Mobile Ad hoc Network Wireless Sensor Networks

It means that sensor nodes are having uniform structure and of the same or similar nature.

Data reception and transmission between clusters. Data reception and transmission within one cluster.

The lifetime of a network is the active time of the network until the first node runs out of energy.

Large number of micro-sensors that communicate wirelessly and bring themselves together to form a network.

Sensor Web

Low Energy Adaptive Clustering Hierarchy


Recent advances in high integration technologies and low power design have brought to the fore small-sized battery- operated sensors that are capable of monitoring the environment. A typical node of a WSN is equipped with four components: a sensor that performs the sensing of required events in a specific field, a radio transceiver that performs radio transmission and reception, a microcontroller: which is used for data processing and a battery that is a power unit providing energy for operation[1]. These sensor nodes can be deployed randomly to perform such applications as monitoring environment, battlefield reconnaissance, border protection and security surveillance, preparing forecasts, volcano monitoring etc. In disaster management situations such as earthquakes, volcanic eruptions, tornadoes etc sensor networks can be used to locate the affected regions and direct emergency relief to the survivors. In military situations (Fig. 1), sensor networks can be used in surveillance missions and can be used to detect moving targets, chemical gases, or the presence of micro-agents[2].

The hallmark of wireless sensors networks (WSNs) is their ability to function unattended in harsh environments in which contemporary human-in-the-loop monitoring schemes are unproductive, precarious, and infeasible. Therefore, sensors are likely to be deployed arbitrarily in the area of concern by fairly hysterical means, e.g. dropped by a helicopter, and to collectively form a network in an ad-hoc manner.

However, the limited energy of each node, supplied from non-rechargeable batteries, with no form of recharging after deployment and the possibility of having damaged nodes during deployment is one of the most crucial problems in WSN. Given the important of energy efficiency in WSNs, most of the algorithms proposed for WSNs concentrate mainly on maximizing the lifetime of the network by trying to minimize the energy consumption. Other application specific design objectives like high fidelity target detection and classification, security, real time communication etc may also considered.

illustration not visible in this excerpt

Figure 1 WSN military application

Clustering is proven to be an effective approach to conserve limited energy resources, provide better data aggregation and scalability of WSNs[3].Clustering is defined as the grouping of similar objects or the process of finding a natural association among some specific objects or data[4]. In WSN it is used to minimize the number of nodes that take part in long distance data transmission to a BS, what leads to lowering of total energy consumption of the system. Clustering reduces the amount of transmitted data by grouping nearby nodes and electing a specific node as a cluster head, where aggregation of data is performed to avoid redundancy and communication load caused by multiple transmissions, then the aggregated data is sent to the next cluster head or to the BS, where it is processed, stored or retrieved.

This thesis analyses the energy efficiency of S-Web and LEACH clustering algorithms to understand how it influences the network lifetime. The thesis is divided into five chapters, Chapter One presents an introduction to the WSN, Chapter Two provides literature survey on clustering WSN, Chapter Three presents problem definition and implementation, Chapter four discusses the results of the simulation and Chapter Five concludes the research and also defines possible future enhancements.


2.1 Clustering ad hoc networks

Ad hoc network is a self-organizing multihop system of wireless nodes which can communicate with each other without pre-existing infrastructure. In an ad hoc network, mobile nodes communicate with each other using multihop wireless links. There is no stationary infrastructure; for instance, there are no base stations. Each node in the network also acts as a router, forwarding data packets for other nodes. The development of dynamic routing protocols that can efficiently find routes between two communicating nodes is a crucial research issue in the design of ad hoc networks[5]. The routing protocol must be able to keep up with the high degree of node mobility that often changes the network topology. The routing protocols in ad hoc networks are different compared to normal wired networks. The use of conventional routing protocols in a dynamic network is inconvenient because they place a heavy computational burden on mobile computers and they present convergence characteristics that don’t suit well enough the needs of dynamic networks[6]. For instance, any routing scheme in a dynamic environment such as ad hoc networks must consider that the topology of the network can vary while the packet is being routed[6] and that the quality of wireless links is highly variable. In wired networks, link failure is not frequent since the network structure is mostly static. Therefore, routes in MANET must be calculated much more frequently in order to keep up the same response level of wired networks [8].

Moreover, the limited energy of each node, supplied from non-rechargeable batteries, with no form of recharging after deployment and the possibility of having damaged nodes during deployment is one of the most crucial problems in WSN. Many routing protocols have been proposed for WSNs. Most of the algorithms proposed for WSNs concentrate mainly on maximizing the lifetime of the network by trying to minimize the energy consumption.

Researchers agree that a successful method for dealing with the maintenance problem of mobile ad hoc networks and lifetime for wireless sensor networks is clustering[3]. With an ad hoc clustering network, the nodes are separated into groups called clusters. There are usually three types of nodes in clustering networks, as shown in Figure 2: cluster heads (CHs), gateway nodes and normal nodes. In each cluster, one node is elected as a CH to act as a local controller. The size of the cluster (the number of nodes in the cluster) depends on the transmission range of the nodes in single hop cluster and the number of hops made by the cluster in multi-hop clusters. The normal node sends or relays data to the CH which transfers the collected packets to the next hop. The gateway node, belonging to more than one cluster, bridges the CHs in those clusters. Both CHs and gateway nodes form the backbone network, yet the presence of gateway node is not compulsory in the clustering network[9].

illustration not visible in this excerpt

Figure 2 Clustering Network

Moreover, base station (BS) provides the communication link between the sensor network and the end-user. It is normally the sink in a WSN. The data in a sensor network can be used for a wide-range of applications. Data are generated in WSNs in response to queries received from the end user.

In clustering ad hoc networks, both proactive and reactive routing protocols are used. Connectivity within a cluster, only containing a small number of nodes, is maintained by periodically exchanging information updates among neighboring nodes about links changes. Therefore, when a node sends data to its CH, a route-table based routing (proactive) protocol is used. However, if the destination node is in a different cluster, the CH that the node belongs to will need to discover the backbone route so that the inter-cluster routing is on-demand (reactive).

Clustering schemes can be classified into ad hoc sensor network clustering schemes and mobile ad hoc network clustering schemes. In sensor networks, the energy stored in the network nodes is limited and usually infeasible to recharge; the clustering schemes for these networks therefore aim at maximizing the energy efficiency. In mobile ad hoc networks, the movement of the network nodes may quickly change the topology resulting in the increase of the overhead message in topology maintenance; the clustering schemes for mobile ad hoc networks therefore aim at handling topology maintenance, managing node movement or reducing overhead[9].

2.2 Advantages of Clustering

Grouping sensor nodes into clusters has been widely pursued by the research community in order to achieve the network scalability objective[2]. Clustering offers numerous advantages, in addition to supporting network scalability; it can localize the route set up within the cluster and thus reduce the size of the routing table stored at the individual node[10]. Clustering can also conserve communication bandwidth since it limits the scope of inter-cluster interactions to CHs and avoids redundant exchange of messages among sensor nodes[11]. Moreover, clustering can stabilize the network topology at the level of sensors and thus cuts on topology maintenance overhead. Sensors would care only for connecting with their CHs and would not be affected by changes at the level of inter-CH tier[12].Only the CHs and gateway nodes form the backbone network, resulting in much simpler topology, less overhead, flooding and collision.[9]. The CH can also implement optimized management strategies to further enhance the network operation and prolong the battery life of the individual sensors and the network lifetime[11]. A CH can schedule activities in the cluster so that nodes can switch to the low-power sleep mode most of the time and reduce the rate of energy consumption. Sensors can be engaged in a round-robin order and the time for their transmission and reception can be determined so that the sensors reties are avoided, redundancy in coverage can be limited and medium access collision is prevented [13-16]. Furthermore, a CH can aggregate the data collected by the sensors in its cluster and thus decrease the number of relayed packets[17].

2.3 Challenges for Clustering Algorithms

Clustering schemes play an important role in WSN; these can effectively improve the network performance. There are several key limitations in WSNs that clustering schemes must consider.

- Limited Energy: Wireless sensor nodes are small size battery operated sensors, so they have limited energy storage. It is not practicable to recharge or replace their batteries after exhaustion. The clustering algorithms are more energy efficient compared to the direct routing algorithms[3]. This can be achieved by balancing the energy consumption in sensor nodes by optimizing the cluster formation, periodically re-electing CHs based on their residual energy, and efficient intra-cluster and inter-cluster communication.

- Maximal network longevity: Since sensor nodes are energy-constrained, the network’s lifetime is a major concern; especially for applications of WSNs in harsh environments. When CHs are richer in resources than sensors, it is imperative to minimize the energy for intra-cluster communication. If possible, CHs should be placed close to most of the sensors in its clusters[2]. On the other hand, when CHs are regular sensors, their lifetime can be extended by limiting their load. Combined clustering and route setup has also been considered for maximizing network’s lifetime[18]. Adaptive clustering is also a viable choice for achieving network longevity.

- Constrained resources: The small physical size and small amount of stored energy in a sensor node limits many of the abilities of nodes in terms of processing, memory, storage, and communication.

- Secure Communication: The ability of a WSN to provide secure communication is ever more important when considering these networks for military applications[19]. The self-organization of a network has a huge dependence on the application it is required for. An establishment of secure and energy efficient intra-cluster and inter-cluster communication is one of the important challenges in designing clustering algorithms since these tiny nodes when deployed are unattended to in most cases.

- Cluster formation and CH selection: Cluster formation and CHs selection are two of the important operations in clustering algorithms. Energy wastage in sensors in WSN due to direct transmission between sensors and a base station can be avoided by clustering the WSN. Clustering further enhances scalability of WSN in real world applications. Selecting optimum cluster size, election and re-election of CHs, and cluster maintenance are the main issues to be addressed in designing of clustering algorithms[3]. The selection criteria to isolate clusters and to choose the CHs should maximize energy utilization.

- Load balancing: Even distribution of sensors among the clusters is usually an objective for setups where CHs perform data processing or significant intra-cluster management duties[20]. Given the duties of CHs, it is intuitive to balance the load among them so that they can meet the expected performance goals[21]. Load balancing is a more pressing issue in WSNs where CHs are picked from the available sensors. In such case, setting equal-sized clusters becomes crucial for extending the network lifetime since it prevents the exhaustion of the energy of a subset of CHs at high rate and prematurely making them dysfunctional[2]. Even distribution of sensors can also leverage data delay. When CHs perform data aggregation, it is imperative to have similar number of node in the clusters so that the combined data report becomes ready almost at the same time for further processing at the base-station or at the next tier in the network.

- Minimal cluster count: This objective is particularly common when CHs are specialized resource-rich nodes[22]. The network designer often likes to employ the least number of these nodes since they tend to be more expensive and vulnerable than sensors. For example, if CHs are laptop computers, robots or a mobile vehicle there will be inherently some limitation on the number of nodes. The limitation can be due to the complexity of deploying these types of nodes, e.g. when the WSN is to operate in a combat zone or a forest[2]. In addition, the size of these nodes tends to be significantly larger than sensors, which makes them easily detectable. Node visibility is highly undesirable in many WSNs applications such as border protection, military reconnaissance and infrastructure security.

- Synchronization: When considering a clustering scheme, synchronization and scheduling will have a considerable effect on the overall network performance. Slotted transmission schemes such as TDMA allow nodes to regularly schedule sleep intervals to minimize energy used. Such schemes require synchronization mechanisms to setup and maintain the transmission schedule.

- Data Aggregation: Data aggregation eradicates duplication of data. In a large network there are often multiple nodes sensing similar information. Data aggregation allows differentiation between sensed data and useful data. Many clustering schemes providing data aggregation capabilities[23] must carefully select a suitable clustering approach.

- Fault-tolerance: In many applications, WSNs will be operational in harsh environments and thus nodes are usually exposed to increased risk of malfunction and physical damage. Tolerating the failure of CHs is usually necessary in such applications in order to avoid the loss of important sensors’ data. The most intuitive way to recover from a CH failure is to re-cluster the network. However, re-clustering is not only a resource burden on the nodes, it is often very disruptive to the on-going operation[2]. Therefore, contemporary fault-tolerance techniques would be more appropriate for that sake. Assigning backup CHs is the most notable scheme pursued in the literature for recovery from a CH failure. The selection of a backup and the role such spare CH will play during normal network operation varies. When CHs have long radio range, neighboring CHs can adapt the sensors in the failing cluster[24]. Rotating the role of CHs among nodes in the cluster can also be a means for fault-tolerance in addition to their load balancing advantage [25].

- Quality of Service (QoS): From an overall network standpoint, we can look at QoS requirements in WSNs. Many of these requirements are application dependant such as acceptable delay and packet loss tolerance. Existing clustering algorithms for WSN mainly focus on providing energy efficient network utilization, but pay less attention to QoS support in WSN. QoS metrics must be taken into account in the design process[3].



ISBN (eBook)
ISBN (Book)
File size
605 KB
Catalog Number
Clustering Energy Efficiency SWEB Wireless Sensor Networks LEACH Network Lifetime




Title: Performance Evaluation of Clustering Algorithms in Wireless Sensor Networks (WSN). Energy Efficiency of S-Web and LEACH