An Affinity Propagation-Based Self-Adaptive Clustering Method for Wireless Sensor Networks

Jin Wang, Yu Gao, Kai Wang, Arun Kumar Sangaiah, Se-Jung Lim2019 · DOI

TL;DR

This paper introduces a novel clustering method, APSA, for wireless sensor networks (WSNs) that combines Affinity Propagation (AP) with a modified K-medoids algorithm. APSA aims to overcome the limitations of existing methods, such as uneven cluster head distribution and unbalanced energy consumption, by intelligently determining cluster numbers and initial cluster centers, leading to improved energy efficiency and network lifetime.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for the Internet of Things (IoT), enabling data collection and communication from ubiquitous smart objects. However, WSNs face a significant challenge: limited battery life. Energy efficiency is paramount, as replacing batteries in large-scale, often remote, sensor networks is impractical. Clustering is a common strategy to improve WSN energy efficiency by organizing sensors into groups with designated Cluster Heads (CHs) responsible for data aggregation and transmission.

Despite the benefits of clustering, existing methods often suffer from drawbacks:

  • Uneven CH Distribution: Random CH selection can lead to some areas having too many CHs and others too few, forcing nodes to communicate over longer distances, thus draining their batteries faster.
  • Unbalanced Energy Consumption: Without proper consideration for residual energy, CHs can die prematurely, creating "dead spots" in the network and reducing overall performance.
  • Suboptimal Clustering: Traditional methods like K-medoids can get stuck in local optima and require manual specification of the number of clusters.

This paper addresses these issues by proposing a self-adaptive clustering method that intelligently determines cluster parameters and optimizes CH selection to enhance network longevity and efficiency.

Methods

The proposed Affinity Propagation-Based Self-Adaptive (APSA) clustering method integrates two key algorithms:

  1. Affinity Propagation (AP): AP is used in the initial phase to intelligently determine the optimal number of clusters and identify promising initial cluster centers. Unlike traditional methods that require pre-defining the number of clusters (k), AP infers this from the data itself. It calculates similarities between sensor nodes and uses responsibility and availability messages to iteratively select exemplars (potential CHs). This helps avoid the limitations of random initializations and can lead to a more reasonable starting point for clustering.
  2. Modified K-medoids: After AP identifies initial cluster centers, a modified K-medoids algorithm is employed to refine the clustering. K-medoids is chosen because it uses actual data points as cluster centers (unlike K-means, which uses centroids), leading to more accurate clustering. The modification likely involves incorporating factors like residual energy into the K-medoids iteration process to ensure more balanced energy distribution and prevent premature CH failure. The algorithm iteratively assigns nodes to the nearest cluster medoid and potentially swaps medoids to minimize the overall error, focusing on optimizing the distance between member nodes and their CHs.

The APSA algorithm proceeds in three phases:

  • Initial Phase: Sensors gather their own location and residual energy information and exchange it with neighbors.
  • Set-Up Phase: AP determines initial cluster centers and the number of clusters. The modified K-medoids then refines these into final clusters.
  • Communication Phase: Member nodes transmit data to their CHs, CHs perform data fusion, and then transmit aggregated data to the Base Station (BS). The BS then orchestrates the next round.

Datasets

Not discussed in the paper. The authors used a simulated environment in MATLAB for evaluation.

Key Insights and Ideas

  • AP for Intelligent Parameter Selection: Using Affinity Propagation to automatically determine the number of clusters and initial cluster centers is a significant departure from methods that require manual input or rely on random initialization. This can lead to more robust and adaptive clustering.
  • Synergy of AP and K-medoids: Combining AP's ability to find optimal initial parameters with K-medoids' strength in refining clusters offers a powerful approach. AP provides a better starting point, potentially reducing K-medoids' convergence time and its tendency to get stuck in local optima.
  • Self-Adaptive Nature: The "self-adaptive" aspect implies that the algorithm can adjust its clustering strategy based on the network's state (e.g., sensor distribution, residual energy), making it more resilient to dynamic changes.
  • Focus on Intracluster Communication: The paper highlights that reducing the average distance between member nodes and their CHs is crucial for energy savings. APSA's results show a significant improvement in this metric.

Key Results

The APSA algorithm was compared against several state-of-the-art routing protocols: UCR-H, LEACH-AP, and EDDUCA. The simulations, conducted with 50 sensor nodes, demonstrated significant improvements:

  • Energy Consumption: APSA showed a slower increase in total energy consumption over rounds compared to the other algorithms. At 1000 rounds, it achieved performance gains of approximately 33.33% (vs. UCR-H), 52.5% (vs. LEACH-AP), and 54.21% (vs. EDDUCA).
  • Network Lifetime: The lifetime of the network (defined as when half the sensors are dead) was extended by APSA. Its lifetime was 1511 rounds, achieving gains of 16.23% (vs. UCR-H), 31.39% (vs. LEACH-AP), and 51.1% (vs. EDDUCA).
  • Intracluster Communication Distance: APSA significantly reduced the average intracluster communication distance, improving performance by about 30.5% compared to LEACH-AP.
  • Cluster Member Distribution: APSA achieved a more even distribution of cluster members, with a maximum difference of 2 between the largest and smallest cluster sizes in the worst case, compared to 6 in LEACH-AP.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Scalability: The current implementation of AP for calculating initial cluster centers can become computationally expensive as the network size increases, making it less suitable for very large-scale WSNs.
  • Parameter Optimization: The AP preference parameter (p) was set based on empirical experience (-6000). The authors suggest that further work is needed to optimize this parameter to ensure it's truly optimal.
  • Real-World vs. Simulation: The simulation assumes perfect communication success. Real-world environments involve harsh conditions and busy channels, which can lead to transmission failures. The algorithm needs to be adapted to handle these real-world complexities.
  • Future Work: The authors plan to focus on improving the method's expandability and integrating it with mobile sink technology and data fusion techniques to further enhance performance.

Summary updated

BibTeX
@misc{wang2019affinity,
  author = {Jin Wang and Yu Gao and Kai Wang and Arun Kumar Sangaiah and Se-Jung Lim},
  title = {{An Affinity Propagation-Based Self-Adaptive Clustering Method for Wireless Sensor Networks}},
  year = {2019},
  doi = {10.3390/s19112579},
}
Figure