A message-passing approach to min-cost distributed clustering in wireless sensor networks
Hung Q. Ngo, Tran Minh Tam, Young-Koo Lee, Sungyoung Lee · 2008
Clustering is an effective approach to hierarchically organizing network topology for efficient data aggregation in wireless sensor networks (WSNs). In this paper, we present a new approach to energy-efficient, distributed clustering in WSNs using the recent modeling and computational methodology of factor graphs and message-passings. We first formulate the sensor clustering as an optimization problem that minimizes the total data transmission cost weighted by node residual energy. We then derive simplified, localized, min-sum recursive message-passing rules which can elect a near-optimal set of cluster heads. We show through simulations that the proposed algorithm quickly achieves a good approximation of the minimum cost found by a centralized algorithm, and effectively prolongs the network lifetime compared to a popular sensor clustering algorithm.