Energy-efficient broadcasting in wireless ad hoc networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Energy-efficient broadcasting in wireless ad hoc networks: performance benchmarking and distributed algorithms based on network connectivity characterization

Full text

Pdf (264 KB)

Source

International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems archive
Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems table of contents

Montréal, Quebec, Canada

SESSION: Multihop networks table of contents

Pages: 28 - 35

Year of Publication: 2005

ISBN:1-59593-188-0

Author

Di Yuan

Linköping University, Norrköping, Sweden

Sponsors

ACM: Association for Computing Machinery
SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 80, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1089444.1089451 What is a DOI?

ABSTRACT

Broadcasting in wireless ad hoc networks can use a virtual backbone formed by a connected dominating set (CDS). If nodes use constant and identical transmission power, energy-efficient broadcasting amounts to minimizing the size of the backbone (i.e., CDS cardinality). This is referred to as the minimum connected dominating set (MCDS) problem. We present two feasibility conditions, and show that each of the conditions is both sufficient and necessary for characterizing a CDS. The first condition yields an integer programming model, which allows us to compute an MCDS for networks of moderate size (up to 80 nodes in our experiments). The second condition leads to a class of distributed algorithms. We compare numerically the performance of this class of algorithms to that of a centralized algorithm, as well as to MCDS found using the integer programming model. Our performance evaluation suggests that the class of algorithms presented in this paper have a close-optimal performance. In addition, we highlight possible algorithm extensions to cope with timing and mobility issues.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. M. Alzoubi, P.-J. Wan, and O. Frieder. Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, 4(1):22--29, March 2002.
	2	J. Blum, M. Ding, A. Thaeler, and X. Cheng. Connected dominating set in sensor networks and MANETS. In D.-Z. Du and P. Pardalos, editors, Handbook of Combinatorial Optimization, pages 329--369. Kluwer Academic Publishers, 2004.
	3	S. Butenko, X. Cheng, C. Oliveria, and P. M. Padalos. A new heuristic for the minimum connected dominating set problem on ad hoc wireless systems. In S. Butenko, R. Murphey, and P. Pardalos, editors, Recent Developments in Cooperative Control and Optimization, chapter 4, pages 61--73. Kluwer Academic Publishers, 2004.
	4	M. Cardei, X. Cheng, X. Cheng, and D.-Z. Du. Connected domination in ad hoc wireless networks. In Proceedings of the Sixth International Conference on Computer Science and Informatics (CS&I), 2002.
	5	X. Cheng, X. Huang, D. Li, W. Wu, and D.-Z. Du. A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks, 42(4):202--208, 2003.
	6	Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O ]
	7	Fei Dai , Jie Wu, An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.908-920, October 2004 [doi>10.1109/TPDS.2004.48]
	8	B. Das and V. Bharghavan. Routing in ad-hoc networks using minimum connected dominating sets. In Proceedings of IEEE ICC '97, pages 376--380, 1997.
	9	Bevan Das , Raghupathy Sivakumar , Vaduvur Bharghavan, Routing in Ad Hoc Networks Using a Spine, Proceedings of the 6th International Conference on Computer Communications and Networks, p.34, September 22-25, 1997
	10	Devdatt Dubhashi , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan , Arvind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	11	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
	12	S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374--387, 1998.
	13	ILOG CPLEX 7.0, User's Manual. ILOG, 2000.
	14	X. Li and I. Stojmenovic. Broadcasting and topology control in wireless ad hoc networks. In A. Boukerche and I. Chlamtac, editors, Handbook of Algorithms for Mobile and Wireless Networking and Computing. CRC Press, to appear.
	15	M. Min, X. Huang, S. C.-H. Huang, and W. Wu. Improving construction for connected dominating set with Steiner tree in wireless sensor networks. Journal of Global Optimization, to appear.
	16	Lu Ruan , Hongwei Du , Xiaohua Jia , Weili Wu , Yingshu Li , Ker-I Ko, A greedy approximation for minimum connected dominating sets, Theoretical Computer Science, v.329 n.1-3, p.325-330, 13 December 2004 [doi>10.1016/j.tcs.2004.08.013]
	17	P. Sinha, R. Sivakumar, and V. Bharghavan. Enhancing ad hoc routing with dynamic virtual infrastructures. In Proceedings of IEEE INFOCOM '01, pages 1763--1772, 2001.
	18	Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024 ]
	19	P.-J. Wan, K. Alzoubi, and O. Frieder. Distributed construction of connected dominating set in wireless ad hoc networks. In Proceedings of IEEE INFOCOM '02, pages 1597--1604, 2002.
	20	J. E. Wieselthier, G. D. Nguyen, and A. Ephremides. On the construction of energy-efficient broadcast and multicast trees in wireless networks. In Proceedings of IEEE INFOCOM '00, pages 585--594, 2000.
	21	Jie Wu , Fei Dai, A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks, IEEE Transactions on Computers, v.53 n.10, p.1343-1354, October 2004 [doi>10.1109/TC.2004.69]
	22	J. Wu, F. Dai, M. Gao, and I. Stojmenovic. On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, 4(1):59--70, March 2002.
	23	Jie Wu , Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.7-14, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313261]