Energy Constrainted Dominating Set

Energy Constrained Clustering in Sensor Networks

Using partitioning in sensor networks to create clusters used for routing, data management and other protocols has been proven as a way to ensure scalability and to deal with shortcomings of sensor networks such as limited communication ranges and energy. Cluster heads use additional energy for their responsibilities and that burden needs to be carefully passed around. Many existing clustering protocols choose cluster heads either randomly or use nodes with the highest remaining energy. We introduce the energy constrained minimum dominating set (ECDS) problem to model the problem of optimally choosing cluster heads with energy constrains. We show its applicability to sensor networks and give an approximation algorithm of O(log n) for solving the ECDS problem. We propose a distributed algorithm for the constrained dominating set and experimentally show that it outperforms the greedy algorithm. We show experimentally that our heuristics are good approximations in random networks.

A paper has been submitted to IEEE MASS 2009.  The current version of this paper is here. If you read it and have any corrections/suggestions for improvment, I would appreciate the feedback.