Efficient Algorithms for Self-organizing Wireless Sensor Networks: A Novel Budget-Based Clustering Approach

Self-organization of wireless sensor networks, which involves network decomposition into connected clusters, is a challenging task because of the limited bandwidth and energy resources available in these networks. This book presents a novel approach for message-efficient clustering, in which nodes allocate local ??growth budgets'' to neighbors. Algorithms that make use of this approach are presented, along with an analysis of the message complexity of these algorithms. The book also presents a new randomized methodology for designing the timers of cluster initiators. This methodology provides a probabilistic guarantee that initiators will not interfere with each other. Extensive simulations over different topologies confirm the analytical results and demonstrate that our proposed methodology scales to large networks. Further applications of the work in other domains are discussed.