Using partitioning in wireless sensor networks to create clusters for routing, data management, and other protocols has been proven as a way to ensure scalability and to deal with sensor network shortcomings such as limited communication ranges and energy. Choosing a cluster head within each cluster is important because cluster heads use additional energy for their responsibilities and that burden needs to be carefully passed around. Many existing protocols either choose cluster heads randomly or use nodes with the highest remaining energy. We introduce the energy constrained minimum dominating set (ECDS) to model the problem of optimally choosing cluster heads with energy constraints. We propose a distributed algorithm for the constrained dominating set which runs in O(log n log Δ) rounds with high probability. We experimentally show that the distributed algorithm performs well in terms of energy usage, node lifetime, and clustering time and, thus, is very suitable for wireless sensor networks.

Meeting Name

2010 24th IEEE International Conference on Advanced Information Networking and Applications (AINA)


Computer Science

Keywords and Phrases

Communication Complexity; Distributed Algorithms; Probability; Routing Protocols; Set theory; Wireless sensor networks

Document Type

Article - Conference proceedings

Document Version

Final Version

File Type





© 2010 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Apr 2010