A local algorithm to compute multiple connected dominating sets in wireless sensor networks

摘要

We investigate the problem of computing a family of connected dominating sets (CDSs) in wireless sensor networks (WSNs) in a distributed manner. Specifically, we present a local algorithm that computes a family S_1,S_2, ...,S_m of non-trivial CDSs with the goal to maximise α = m/k, where k = max_(u∈v)|(i :u ∈S_i}|. In other words, we wish to find as many CDSs as possible, while minimising the number of frequencies of each node in these sets. Since CDSs play an important role for maximising network lifetime when they are used as backbones for broadcasting messages, maximising α reduces the possibility of repeatedly using the same subset of nodes as backbones. We provide an upper bound on the value of α via a 'nice' relationship between all minimum vertex-cuts and CDSs in the network graph, and present a local algorithm for the α maximisation problem. For a subclass of unit disk graphs (UDGs), it is shown that our algorithm achieves a constant approximation factor of the optimal solution. Here, a WSN is modelled as an UDG.