AHSWN Home • Issue Contents
Incremental Construction of k-Dominating Sets in Wireless Sensor Networks
Mathieu Couture, Michel Barbeau, Prosenjit Bose and Evangelos Kranakis
Given a graph G, a k -dominating set of G is a subset S of its nodes with the property that every node of G is either in S or has at least k neighbors in S. We present a new incremental distributed 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 size of an optimal i-dominating set.