Node clustering in wireless sensor networks by considering structural characteristics of the network graph

The deployment of wireless sensor networks in many application areas, e.g., aggregation services, requires self-organization of the network nodes into clusters. Quite a lot of node clustering techniques have appeared in the literature, and roughly fall into two families; those based on the construction of a dominating set and those which are based solely on energy consider-ations. The former family suffers from the fact that only a small subset of the network nodes are respon-sible for relaying the messages, and thus cause rapid consumption of the energy of these nodes. The later family uses the residual energy of each node in order to direct its decision about whether it will elect itself as a leader of a cluster or not. This family’s methods ignore topological features of the nodes and are used in combination with the methods of the former family. We propose a novel distributed clustering protocol for wireless sensor networks, based on a novel metric for characterizing the importance of a node, w.r.t. its con-tribution in relaying messages. The protocol achieves small communication complexity and linear computa-tion complexity. Experimental results for various sen-sor network topologies show that the protocol generates only a few clusters, guaranteeing a small number of message relays thus improving network lifetime