Carleton University
Technical Report TR-06-11
December 18, 2006
Incremental Construction of k-Dominating Sets in Wireless Sensor
Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis
Abstract
Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least k neighbors in S. We present a new incremental local algorithm to construct a k-dominating set. The algorithm constructs a monotone family of dominating sets D1≤ D2…≤ Di…≤ Dk such that each Di is an i-dominating set. For unit disk graphs, the size of each of the resulting i-dominating sets is at most six times the optimal.