Energy conservation via domatic partitions

ABSTRACT

Using a dominating set as a coordinator in wireless networks has been proposed in many papers as an energy conservation technique. Since the nodes in a dominating set have the extra burden of coordination, energy resources in such nodes will drain out more quickly than in other nodes. To maximize the lifetime of nodes in the network,it has been proposed that the role of coordinators be rotated among the nodes in the network. One abstraction that has been considered for the problem of picking a collection of coordinators and cycling through them, is the domatic partition problem. This is the problem of partitioning the set of the nodes of the network into dominating sets with the aim of maximizing the number of dominating sets. In this paper,we consider the k -domatic partition problem. A k -dominating set is a subset D of nodes such that every node in the network is at distance at most k from D. The k-domatic partition problem seeks to partition the network into maximum number of k-dominating sets.We point out that from the point of view of saving energy,it may be better to construct a k-domatic partition for k >1.We present three deterministic, distributed algorithms for finding large k-domatic partitions for k > 1. Each of our algorithms constructs a k-domatic partition of size at least a constant fraction of the largest possible (k 1)-domatic partition. Our first algorithm runs in constant time on unit ball graphs (UBGs) in Euclidean space assuming that all nodes know their positions in a global coordinate system. Our second algorithm drops knowledge of global coordinates and instead assumes that pairwise distances between neighboring nodes are known. This algorithm runs in O(log* n ) time on UBGs in a metric space with constant doubling dimension. Our third algorithm drops all reliance on geometric information, using connectivity information only. This algorithm runs in O(log Δ · log *n) time on growth-bounded graphs. Euclidean UBGs, UBGs in metric spaces with constant doubling dimension, and growth-bounded graphs are successively more general models of wireless networks and all three models include the well-known, but somewhat simplistic wireless network models such as unit disk graphs.

REFERENCES

• 1: M.A.Bonucelli.Dominating sets and domatic number of circular arc graphs.Discrete Appl. Math.12, pages 203--213, 1985.
• 2: M.Cardei and D.Du.Improving wireless sensor network lifetime through power aware organization. Wireless Networks 11(3): 333--340, May 2005.
• 3: M. Cardei, D. Maccallum, M. X. Cheng, M. Min, X. Jia, D. Li,and D. Du. Wireless sensor networks with energy efficient organization. Journal of Interconnection Networks 3(3-4):213--229,2002.
• 4: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks, Wireless Networks, v.8 n.5, p.481-494, September 2002 [doi>10.1023/A:1016542229220]
• 5: M.Farber.Domination, independent domination, and duality in strongly chordal graphs.Discrete Appl. Math 7,pages 115--130,1984.
• 6: Uriel Feige , Magnús M. Halldórsson , Guy Kortsarz , Aravind Srinivasan, Approximating the Domatic Number, SIAM Journal on Computing, v.32 n.1, p.172-195, 2003 [doi>10.1137/S0097539700380754]
• 7: S. Fujita On the performance of greedy algorithms for finding maximum r-configurations. In Proceedings of Korea-Japan Joint Workshop on Algorithms and Computation (WAAC), Seoul National University, Seoul pages 92--99,1999.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 10: Haim Kaplan , Ron Shamir, The domatic number problem on some perfect graph families, Information Processing Letters, v.49 n.1, p.51-56, Jan. 14, 1994 [doi>10.1016/0020-0190(94)90054-X]
• 11: S. Kim, D. Culler, J. Demmel, G. Fenves, S. Glaser, T. Oberhein,and S. Pakzad. Structural health monitering of the golden gate bridge. UC Berkeley, NEST Retreat Presentation, Jan 15, 2004.
• 12: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 13: Jan Kratochivíl, Regular codes in regular graphs are difficult, Discrete Mathematics, v.133 n.1-3, p.191-205, Oct. 15, 1994 [doi>10.1016/0012-365X(94)90026-4]
• 14: F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast deterministic distributed maximal independent set computation on growth-bounded graphs.In Proceedings of the 19th International Symposium on Distributed Computing (DISC)2005.
• 15: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073826]
• 16: Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
• 17: A. Mainwaring, J. Polastre, R. Szewczyk,,and D. Culler. Wireless sensor networks for habitat monitoring.Technical Report IRB-TR-02-006,Intel Research Laboratory at Berkeley,2002.
• 18: M. V. Marathe , H. B. Hunt, III , S. S. Ravi, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Discrete Applied Mathematics, v.64 n.2, p.135-149, Jan. 18, 1996 [doi>10.1016/0166-218X(94)00118-W]
• 19: T.Moscibroda and R.Wattenhofer.Maximizing the lifetime of dominating sets.In Proceedings of the 5th. IEEE International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks 2005.
• 20: Shen-Lung Peng , Maw-Shang Chang, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Information Processing Letters, v.43 n.6, p.297-300, Oct. 19, 1992 [doi>10.1016/0020-0190(92)90115-C]
• 21: Jan Kratochvíl , Andrzej Proskurowski , Jan Arne Telle, Complexity of graph covering problems, Nordic Journal of Computing, v.5 n.3, p.173-195, Fall 1998
• 22: A. S. Rao , C. P. Rangan, Linear algorithm for domatic number problem on interval graphs, Information Processing Letters, v.33 n.1, p.29-33, Oct. 1989 [doi>10.1016/0020-0190(89)90184-1]
• 23: S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In IEEE International Conference on Communications 2001.
• 24: Alan P. Sprague, NP-completeness of the domatic number problem on circular arc graphs, Proceedings of the 37th annual Southeast regional conference (CD-ROM), p.43-es, April 1999 [doi>10.1145/306363.306416]
• 25: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
distributed algorithms, domatic partition, dominating sets, doubling dimension, growth-bounded graphs, maximal independent sets, metric space, network decomposition, unit ball graphs, unit disk graphs