|
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 k-dominating sets in wireless sensor networks. A k-dominating 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 k-dominating set model can be used to elect aggregation points, with backups, in sensor networks.
|
