Communication infrastructures provide organizational frameworks for supporting functions such as routing and navigation. Constructing and maintaining a structure allowing nodes to communicate with each other is one of the main challenges concerning ad hoc networks. Our recent work includes algorithms for infrastructure establishment and maintenance in ad hoc networks. One of these is an algorithm for the incremental construction of kdominating sets in wireless sensor networks. A kdominating set of a graph is a subset S of its vertices with the property that every vertex is either in S or has at least k neighbors in S. Our algorithm constructs a monotonic sequence of dominating sets. For unit disk graphs, the size of each of the resulting dominating sets is at most six times the optimal. The kdominating set model can be used to elect aggregation points, with backups, in sensor networks.
