Energy Constraint Clustering Algorithms for Wireless Sensor Networks

Abstract

Using partitioning in sensor networks to create clusters for routing, data management, and for controlling communication has been proven as a way to ensure long range deployment and to deal with sensor network shortcomings such as limited energy and short communication ranges. 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 among nodes in a cluster. Many existing protocols either choose cluster heads randomly or use nodes with the highest remaining energy. We present an Energy Constrained minimum Dominating Set based efficient clustering called ECDS to model the problem of optimally choosing cluster heads with energy constraints. Our proposed randomized distributed algorithm for the constrained dominating set runs in O(log n log Δ) rounds with high probability where Δ is the maximum degree of a node in the graph. We provide an approximation ratio for the ECDS algorithm of expected size 8HΔ|OPT| and with high probability a size of O(|OPT|log n) where n is the number of nodes, H is the harmonic function and OPT means the optimal size. We propose multiple extensions to the distributed algorithm for the energy constrained dominating set. We experimentally show that these extensions perform well in terms of energy usage, node lifetime, and clustering time in comparison and, thus, are very suitable for wireless sensor networks. © 2013 Elsevier B.V. All rights reserved.

Department(s)

Computer Science

Comments

National Science Foundation, Grant None

Keywords and Phrases

Clustering; Dominating set; Routing protocols; Sensor networks

International Standard Serial Number (ISSN)

1570-8705

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Elsevier, All rights reserved.

Publication Date

01 Nov 2013

Link to Full Text

Share

 
COinS