Efficient Routing In Ad Hoc Network Using Multiple Disjoint Energy Aware Minimum Connected Dominating Sets

• Autorzy: Acharya T. , Rroy R.
• Języki publikacji: EN

Abstrakty

EN

We propose a distributed heuristic algorithm for finding power aware connected dominating set in a graph representing an ad hoc network. Simulation results show that we can route more packets compared to fixed dominating set finding algorithms. An extension of our algorithm constructs multiple node-disjoint power aware minimum connected dominating sets. Applying multi-path routing strategies on this multiple dominating sets, we show that the new algorithm works better than other power aware dominating set based schemes and offers results competitive with general power aware schemes in terms of various energy consumption metrics while maintaining smaller size of the dominating set.

Słowa kluczowe

EN

distributed algorithm; dominating set based routing; lifetime improvement

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2010
• Tom: Vol. 35, No. 3
• Strony: 145--170
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Acharya T.

autor

Rroy R.

• Department of Electronics & Telecommunication Engineering, Bengal Engineering & Science University, Shibpur, Howrah, West Bengal, India. Tel: [phone]. Fax: [phone],

Bibliografia

• [1] Acharya T., Roy R., "Distributed algorithm for power aware minimum connected dominating set for routing in wireless ad hoc network," in International workshop on wireless and sensor networks held in conjunction with 34th International Conference on Parallel Processing, Oslo, Norway, 2005, 387-394.
• [2] Acharya T., Chattopadyay S., and Roy R., "Multiple Disjoint Power Aware Minimum Connected Dominating Sets for Efficient Routing in Wireless Ad Hoc Network" ICICT, 2007, Dhaka, Bangladesh, 2007, 336-340.
• [3] Alzoubi K.M., Wan P.-J., and Frieder O., "New distributed algorithm for connected dominating set in wireless ad hoc networks," in Proceedings of the 35th IEEE Hawaii Int. Conf. On System Sciences, Hawaii, USA, vol. 9, Jan 7-10, 2002, 3849-3855.
• [4] Awerbuch B. and Peleg. D., "Network synchronization with polylogarithmic overhead" In Proc. 31st Annual Symposium on Founations of .Computer Science, St. Louis, MO, USA, vol. 2, 1990, 514-522.
• [5] Butenko S., Cheng X., Du D.-Z., and Pardalos P.M., "On the construction of virtual backbone for ad hoc wireless networks," in S. Butenko, R. Murphey, and P.M. Pardalos, (eds.), Cooperative Control: Models, Applications and Algorithms, Kluwer Academic Publishers, 2003, 43-54.
• [6] Butenko S., Cheng X., Oliveira C.A.S., and Pardalos P.M., "A new heuristic for the minimum connected dominating set problem on ad hoc wireless network", to appear in Cooperative Control and Optimization, Kluwer Academic Publisher, 2004, 61-73.
• [7] Chang J.-H. and Tassiulas L., "Maximum lifetime routing for wireless sensor network," in IEEE/ACM Transaction on Networking, vol. 12, no. 4, 2004, 609-618.
• [8] Das B. and Bharghavan V., "Routing in ad hoc networks using minimum connected dominating sets," in Proceedings of IEEE ICC '97, Montreal, Canada, vol. 1, 1997, 376-380.
• [9] Feeney L.M., "An energy-consumption model for performance analysis of routing protocols for mobile ad hoc networks," Mobile Network Application, vol. 6, issue. 3, 2001,239-249.
• [10] Haynes T.W., "Fundamentals of Domination in Graphs," A Series of Monographs and Text-books, Marcel Dekker Inc., New York, 1998.
• [11] Malpani N., Welch J., and Vaidya N., "Leader election algorithms for mobile ad hoc networks," in Proc. Fourth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, MA, USA, 2000, 96-103.
• [12] Misra A. and Baneijee S., "MRPC: maximizing network lifetime for reliable routing in wireless environments", IEEE Wireless Communications and Networking Conference (WCNC), vol. 2, 2002, 800-806.
• [13] Stojmenovic I., and Lin X., "Power-aware localized routing in wireless networks," IEEE Transactions on Parallel and Distributed Systems," vol. 12, issue. 11, Nov., 2001, 1122-1133.
• [14] Wu J., Dai F., Gao M., and Stojmenovic I., "On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks", IEEE / KICS Journal of Communications and Networks, vol. 4, no. 1, March, 2002, 59-70.
• [15] Wu J. and Li H., "On calculating connected dominating set for efficient routing in ad hoc wireless networks," in Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile computing and communications, 1999, 7-14.