IEEE Transactions on Mobile Computing · 2008 · 62 citations · 21 references
ComputingComputer ScienceComputer SystemsAlgorithmsComputer NetworksDistributed SystemsDistributed AlgorithmsDistributed ComputingGraph AlgorithmsRoutingSensor NetworksWireless Sensor NetworksAd Hoc NetworkingAd Hoc NetworksDominating SetsHeuristicsNode DegreeProximitySensor NodesUnit Disk Graphs
Wireless ad hoc and sensor networks (WSNs) often require a connected dominating set (CDS) as the underlying virtual backbone for efficient routing. Nodes in a CDS have extra computation and communication load for their role as dominator, subjecting them to an early exhaustion of their battery. A simple mechanism to address this problem is to switch from one CDS to another fresh CDS, rotating the active CDS through a disjoint set of CDSs. This gives rise to the connected domatic partition (CDP) problem, which essentially involves partitioning the nodes V(G) of a graph G into node disjoint CDSs. We have developed a distributed algorithm for constructing the CDP using our maximal independent set (MlS)-based proximity heuristics, which depends only on connectivity information and does not rely on geographic or geometric information. We show that the size of a CDP that is identified by our algorithm is at least [delta+1/beta(c+1)] - f, where delta is the minimum node degree of G, beta les 2, c les 11 is a constant for a unit disk graph (UDG), and the expected value of f is epsidelta|V|, where epsi Lt 1 is a positive constant, and delta ges 48. Results of varied testing of our algorithm are positive even for a network of a large number of sensor nodes. Our scheme also performs better than other related techniques such as the ID-based scheme.
21
Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam · IEEE Communications Magazine · 2002 · 13.7K citations
Brent N. Clark, Charles J. Colbourn, David Johnson · Discrete Mathematics · 1990 · 1.4K citations
Routing in ad-hoc networks using minimum connected dominating sets
Bevan Das, V. Bharghavan · 2002 · 771 citations