Energy-efficientdistributedclusteringinwirelesssensornetworks I

a b s t r a c t Thedeploymentofwirelesssensornetworksinmanyapplicationareasrequiresself-organizationofthe networknodesintoclusters.Clusteringisanetworkmanagementtechnique,sinceitcreatesahierarchical structure over a flat network. Quite a lot of node clustering techniques have appeared in the literature, androughlyfallintotwofamilies:thosebasedontheconstructionofadominatingsetandthosewhich arebasedsolelyonenergyconsiderations.Theformerfamilysuffersfromthefactthatonlyasmallsubset of the network nodes are responsible for relaying the messages, and thus cause rapid consumption of the energy of these nodes. The latter family uses the residual energy of each node in order to decide aboutwhetheritwillelectitselfasaleaderofaclusterornot.Thisfamily'smethodsignoretopological features of the nodes and are used in combination with the methods of the former family. We propose an energy-efficient distributed clustering protocol for wireless sensor networks, based on a metric for characterizingthesignificanceofanode,w.r.t.itscontributioninrelayingmessages.Theprotocolachieves smallcommunicationcomplexityandlinearcomputationcomplexity.Experimentalresultsattestthatthe protocolimprovesnetworklongevity. '2009ElsevierInc.Allrightsreserved.