Sriram V. Pemmaraju
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.
- M.A.Bonucelli.Dominating sets and domatic number of circular arc graphs.Discrete Appl. Math.12, pages 203--213, 1985.Google Scholar
- M.Cardei and D.Du.Improving wireless sensor network lifetime through power aware organization. Wireless Networks 11(3): 333--340, May 2005. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris. Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks.ACM Wireless Networks Journal 8(5), 2002. Google ScholarDigital Library
- M.Farber.Domination, independent domination, and duality in strongly chordal graphs.Discrete Appl. Math 7,pages 115--130,1984.Google Scholar
- U. Feige, M. M. Halldorsson, G. Kortsarz, and A. Srinivasan. Approximating the domatic number. SIAM J. Comput.32(1):172--195,2002. Google ScholarDigital Library
- 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.Google Scholar
- M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979. Google ScholarDigital Library
- A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries,fractals,and low-distortion embeddings. In FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science pages 534--543, 2003. Google ScholarDigital Library
- H. Kaplan and R. Shamir. The domatic number problem on some perfect graph families. Inform. Process. Lett.49, pages 51--56, 1994. Google ScholarDigital Library
- 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.Google Scholar
- J. Kleinberg, A. Slivkins,and T. Wexler. Triangulation and embedding using small sets of beacons. In FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science pages 444--453,2004. Google ScholarDigital Library
- J. Kratochvil. Regular codes in regular graphs are difficult. Discrete Math.133, pages 191--205, 1994. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- F. Kuhn, T. Moscibroda,and R. Wattenhofer. On the locality of bounded growth.In Proceedings of 24th. Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing 2005. Google ScholarDigital Library
- N. Linial. Locality in distributed graph algorithms. SIAM J. Comput.21(1):193--201, 1992. Google ScholarDigital Library
- 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.Google Scholar
- M. Marathe, H. B. Hunt III, and S. S. Ravi. Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs.Disc. Appl. Math 64,pages 135--149, 1996. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- S. L. Peng and M. S. Chang. A simple linear time algorithm for the domatic partition problem on strongly chordal graphs.Inform. Process. Lett.43, pages 297--300,1992. Google ScholarDigital Library
- A. Proskurowski and J. A. Telle. Complexity of graph covering problems.Nordic J. Comput.5,pages 173--195,1998. Google ScholarDigital Library
- A. S. Rao and C. P. Rangan. Linear algorithm for domatic number problem on interval graphs.Inform. Process. Lett.33, pages 29--33, 1989. Google ScholarDigital Library
- S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In IEEE International Conference on Communications 2001.Google ScholarCross Ref
- A. P. Sprague. NP-completeness of the domatic number problem on circular arc graphs. In Proc. ACM Southeast Conf. CD-ROM,1999. Google ScholarDigital Library
- Y. Xu, J. S. Heidemann,and D. Estrin. Geography-informed energy conservation for ad hoc routing. In Mobile Computing and Networking pages 70--84,2001. Google ScholarDigital Library
Index Terms
- Energy conservation via domatic partitions
Recommendations
A log-star distributed maximal independent set algorithm for growth-bounded graphs
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computingWe present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our ...
All maximal independent sets and dynamic dominance for sparse graphs
We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set ...
A faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs
ADHOC-NOW'07: Proceedings of the 6th international conference on Ad-hoc, mobile and wireless networksWe present a distributed algorithm for finding a (1 + Ɛ)- approximation of a Minimum Connected Dominating Set in the class of Growth-Bounded graphs, which includes Unit Disk graphs. In addition, the computed Connected Dominating Set guarantees a ...
Comments