Message Efficient Algorithms for Self-Organizing Wireless Sensor Networks - 10/25/2002

Rajesh Krishnan

Distributed self-organization algorithms for wireless sensor (and actuator) networks must have low message complexity from energy and bandwidth considerations. In this talk, we present a novel approach for message-efficient clustering, in which nodes allocate local "growth budgets" to neighbors. We introduce two algorithms that make use of this approach. Unlike the expanding ring approach, our algorithms do not involve the initiator in each round, and do not violate the specified upper bound on the cluster size at any time. We derive analytical performance bounds of our algorithms and also provide performance results from simulations. The algorithms produce clusters of bounded size and low diameter, using significantly fewer messages than the expanding ring approach.