Clustering and routing: Difference between revisions

From Center for Integrated Circuits and Devices Research (CIDR)
Jump to navigation Jump to search
(Added Comparison of Clustering Algorithms from Q1Y1 report.)
 
(Added Reference Title)
Line 113: Line 113:
|high
|high
|}
|}
=== References ===

Revision as of 13:34, 18 January 2023

Figure 1. Clustering in Wireless Sensor Networks.

Routing protocols in wireless sensor networks (WSNs) are generally classified into three main categories according to network structure: flat, hierarchical, and location-based.[1][2] In flat routing protocols, all nodes in the network are typically assigned equal roles, where each node senses the environment and sends the sensed data to a sink or base station. In hierarchical routing protocols, nodes are grouped into clusters. Each cluster has its own cluster head and member nodes, as shown in Figure 1. The member nodes still play the same role of sensing the environment. They forward their sensed data to the respective cluster heads (instead of the base station) for aggregation, and the cluster heads are the ones responsible for transmitting the aggregated data to the base station. In comparison to flat routing protocols, hierarchical routing protocols offer several advantages, including higher energy efficiency, increased scalability, and increased robustness, all of which are advantageous for WSNs.[3]

Comparison of Different Cluster-Based Routing Protocols

Different hierarchical or cluster-based routing protocols are discussed below. Each protocol is analyzed based on several performance metrics, such as energy efficiency, scalability, load balancing, and algorithm complexity.

Low Energy Adaptive Clustering Hierarchy (LEACH)[3]

In LEACH, the idea is to select the cluster heads by rotation so that the high energy dissipation in communicating with the base station is spread across all sensor nodes in the network. By doing so, LEACH offers a balanced load among the nodes, which can greatly improve the network lifetime. It also has a simple algorithm, making it suitable for hardware implementation with limited resources.  However, despite the good performance of the LEACH protocol, it has some drawbacks. This protocol does not consider the residual energy of the nodes in choosing the cluster heads. Nodes with low energy may be chosen as cluster heads and may die prematurely. Hence, this protocol cannot ensure real load balancing for nodes with varying energies. Furthermore, inter-cluster communication is single-hop, wherein the cluster heads directly communicate with the base station, which is not entirely applicable for large-scale networks. Besides, long-range communication entails too much energy consumption.

Two-Level LEACH (TL-LEACH)[4]

TL-LEACH solves the inter-communication problem of LEACH by introducing another level of hierarchy in a cluster and defining two types of cluster heads: primary and secondary cluster heads. In a cluster, there can only be one primary cluster head. A primary cluster head can communicate directly to one or more secondary cluster heads, while a secondary cluster head can communicate directly to one or more member nodes. However, a two-hop inter-cluster routing is still not applicable for large-scale networks.11 Furthermore, TL-LEACH, like LEACH, cannot ensure real load balancing since cluster heads are elected without energy considerations.

Threshold-sensitive Energy-Efficient sensor Network (TEEN)[5]

To reduce communication overhead, TEEN allows member nodes to transmit data only when a specific event occurs, such as when there are sudden changes in the sensed attributes. Hence, TEEN is applicable for time-critical applications or reactive networks. Assuming clusters are already formed, two thresholds are assigned by each cluster head in TEEN for all its member nodes: hard and soft thresholds. Based on the two thresholds, data transmission in TEEN can be controlled, which can lead to a significant energy reduction. However, like LEACH or TL-LEACH, TEEN may consume a lot of energy when there is a small number of levels in the hierarchy of a large-scale network, which requires transmission at far distances. In addition, since member nodes do not send data unless thresholds are met, a member node may die prematurely without the knowledge of the base station.

Adaptive Periodic TEEN (APTEEN)[3]

APTEEN solves the problem mentioned above by allowing the member nodes to transmit periodically while still reacting to time-critical events. In APTEEN, member nodes that have not transmitted any data for a predefined duration (since thresholds are not met) will be required to send data. This protocol offers a lot of flexibility by combining both proactive and reactive policies. However, APTEEN is generally less energy-efficient and more complex to implement than TEEN.

Power-Efficient Gathering in Sensor Information System (PEGASIS)[6]

Another improvement over LEACH is PEGASIS. In PEGASIS, a chain of nodes is formed, wherein the chain is either assigned by the base station or accomplished by the nodes themselves using a greedy algorithm. The main idea behind PEGASIS is for each node to communicate only with its closest neighbors in the chain, thus transmitting only at short distances. All nodes take turns as the leader so as to distribute the load evenly across the network. Since the energy overhead of dynamic cluster formation is removed in PEGASIS, it was able to outperform LEACH in terms of network lifetime for different network sizes and topologies. Through the chain of data aggregation, the data transmission volume is also reduced. However, one disadvantage of this protocol is the overhead of chain construction, which requires each node to have a global knowledge of the network. As nodes also take turns as the leader, each node in PEGASIS is assumed to be capable of communicating directly with the base station. This is not always the case, especially for large-scale networks.

Concentric Clustering Scheme (CCS)[7]

CCS extends PEGASIS by dividing the network into a number of tracks or levels. In each level, a chain is formed similar to PEGASIS, and a leader or head node is selected. Nodes in each level also take turns as the head node for that level. As the chains in CCS are shorter than in PEGASIS, the communication delay in the network is reduced. Additionally, since only the nodes at the first level can communicate directly with the base station, the transmission distance to the base station is reduced in CCS, which saves a considerable amount of energy. However, in this protocol, levels with fewer nodes will deplete their energy faster, as the number of times a node is selected as head node is higher in these levels. CCS also does not ensure real load balancing because node energy is not considered during the selection of head nodes.

Hybrid Energy-Efficient Distributed clustering (HEED)[8]

To ensure load balancing, nodes with higher residual energy are probabilistically selected as cluster heads in HEED. In HEED, the election process goes through several iterations, where each node decides whether to be a cluster head or a member node. If the remaining energy of a node is high, it can elect itself as a cluster head. If its remaining energy is low, or if there is a neighboring node with a low intra-cluster communication cost, the node acts as a member node instead. HEED offers a more balanced load distribution compared to LEACH, which prolongs the network lifetime. However, the election process requires more iterations, which causes noticeable energy dissipation.

Distributed Weight-based Energy-efficient Hierarchical Clustering protocol (DWEHC)[9]

DWEHC is an example of a weight-based protocol that has a similar algorithm to HEED. In this protocol, each node calculates its weight based on its residual energy and distance to its neighbors. Nodes with the largest weight among their neighboring nodes are elected as temporary cluster heads. A real cluster head is then elected from the temporary cluster heads if a given percentage of its neighbors elect it as their temporary cluster head. Compared to LEACH and HEED, DWEHC offers a less random algorithm in choosing cluster heads and takes in more metrics to ensure a more balanced cluster distribution. To achieve further energy reduction, multihop intra-cluster communication is also supported in this protocol. However, DWEHC suffers from the iterative-based problem of HEED, which has a relatively high control message overhead compared to other protocols.

Energy-Efficient Clustering Algorithm Based on Neighbors (EECABN)[10]

Another weight-based protocol is EECABN. In this centralized clustering protocol, nodes are divided into strong and weak nodes, where strong (or weak) nodes are those with energy higher (or lower) than the average energy of all the nodes in the network. The base station computes a weight for each node, and elects strong nodes with the highest weights as cluster heads. A high weight is given to a node not only if it has a high residual energy but also if its neighboring nodes have low residual energy or are near to it. A higher weight is also given to those nodes with more neighbors. As such, EECABN has been shown to improve the network lifetime, even outperforming LEACH and HEED. However, since EECABN is centralized, it does not scale well. Moreover, as nodes have to communicate with the base station during the cluster formation, energy consumption is increased.

Particle Swarm Optimization (PSO)[11]

The PSO algorithm is inspired by the bird-flock choreography. It has been adopted for a more energy efficient cluster formation. However, there are no comparisons made between the PSO algorithm and the other clustering protocols in terms of energy consumption or network lifetime. Besides, the algorithm is centralized and may suffer from poor scalability.

Ant Colony Optimization (ACO)[12]

The ACO algorithm is based on the actual behavior of ants, which communicate with each other by means of chemical pheromone. Employing the idea that ants like to travel along the trails that have the strongest pheromone, ACO algorithms are implemented such that the highest amount of pheromone is found along the optimal path in the network. As such, each node knows the optimal path to send a packet towards a specific destination. Some algorithms take the energy level of a path into account when updating the pheromone trail, which can significantly improve the network lifetime. However, one drawback of using ACO algorithms is the additional traffic overhead due to the ants that move through the network.


Table 1. Comparison of Different Cluster-Based Routing Protocols

Protocol Energy Efficiency Scalability Load Balancing Algorithm Complexity
LEACH very low very low moderate low
TL-LEACH low moderate bad low
TEEN very high low good high
APTEEN moderate low moderate very high
PEGASIS low very low moderate high
CCS low low very bad moderate
HEED moderate moderate moderate moderate
DWECH very high moderate very good moderate
EECS moderate low moderate very high
PSO low very low moderate high
ACO high moderate good high

References

  1. ↑ N. Al-Karaki and A. E. Kamal, “Routing techniques in wireless sensor networks: A survey,” IEEE Wireless Communications, vol. 11, pp. 6–28, 12 2004.
  2. ↑ N. A. Pantazis, S. A. Nikolidakis, and D. D. Vergados, “Energy-efficient routing protocols in wireless sensor networks: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, pp. 551–591, 2013.
  3. ↑ 3.0 3.1 3.2 X. Liu, “A survey on clustering routing protocols in wireless sensor networks,” Sensors, vol. 12, pp. 11113–11153, 8 2012.
  4. ↑ V. Loscri, G. Morabito, and S. Marano, “A two-levels hierarchy for low-energy adaptive clustering hierarchy (tl-leach),” vol. 3. IEEE, 9 2005, pp. 1809–1813.
  5. ↑ A. Manjeshwar and D. P. Agrawal, “Teen: a routing protocol for enhanced efficiency in wireless sensor networks.” IEEE, 4 2001, pp. 2009–2015.
  6. ↑ S. Lindsey and C. S. Raghavendra, “Pegasis: Power-efficient gathering in sensor information systems,” vol. 3. IEEE, 3 2002, pp. 1125–1130.
  7. ↑ S.-M. Jung, Y.-J. Han, and T.-M. Chung, “The concentric clustering scheme for efficient energy consumption in the pegasis,” vol. 1. IEEE, 2 2007, pp. 260–265.
  8. ↑ O. Younis and S. Fahmy, “Heed: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks,” IEEE Transactions on Mobile Computing, vol. 3, pp. 366–379, 10 2004.
  9. ↑ P. Ding, J. Holliday, and A. Celik, “Distributed energy-efficient hierarchical clustering for wireless sensor networks,” International Conference on Distributed Computing in Sensor Systems, pp. 322–339, 2005.
  10. ↑ W. Zhou, “Energy efficient clustering algorithm based on neighbors for wireless sensor networks,” Journal of Shanghai University (English Edition), vol. 15, pp. 150–153, 4 2011.
  11. ↑ S. Guru, S. K. Halgamuge, and S. Fernando, “Particle swarm optimisers for cluster formation in wireless sensor networks.” IEEE, 12 2005, pp. 319–324.
  12. ↑ T. Camilo, C. Carreto, J. S. Silva, and F. Boavida, “An energy-efficient ant-based routing algorithm for wireless sensor networks,” International Workshop on Ant Colony Optimization and Swarm Intelligence, pp. 49–59, 2006.
Retrieved from "https://cidr.up-microlab.org/index.php?title=Clustering_and_routing&oldid=544"