Incremental construction of k-dominating sets in wireless sensor networks
Ad-Hoc and Sensor Wireless Networks , Volume 5 - Issue 1-2 p. 47- 67
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 kdominating 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.