Broadcasting is a common and basic operation used to support various network protocols in wireless networks. To achieve energy-efficient broadcasting is especially important for ad hoc wireless sensor networks because sensors are generally powered by batteries with limited lifetimes. Energy consumption for broadcast operations can be reduced by minimizing the number of relay nodes based on the observation that data transmission processes consume more energy than data reception processes in the sensor nodes, and how to improve the network lifetime is always an interesting issue in sensor network research. The minimum-energy broadcast problem is then equivalent to the problem of finding the minimum Connected Dominating Set (CDS) for a connected graph that is proved NP-complete. In this paper, we introduce an Efficient Minimum CDS algorithm (EMCDS) with help of a proposed ordered sequence list. EMCDS does not concern itself with node energy and broadcast operations might fail if relay nodes are out of energy. Next we have proposed a Minimum Energy-consumption Broadcast Scheme (MEBS) with a modified version of EMCDS, and aimed at providing an efficient scheduling scheme with maximized network lifetime. The simulation results show that the proposed EMCDS algorithm can find smaller CDS compared with related works, and the MEBS can help to increase the network lifetime by efficiently balancing energy among nodes in the networks.
References
[1]
Sinha, A.; Chandrakasan, A. Dynamic power management in wireless sensor networks. Des. Test Comput. 2001, 18, 62–74.
[2]
Tseng, Y.-C.; Ni, S.-Y.; Chen, Y.-S.; Sheu, J.-P. The broadcast storm problem in a mobile ad hoc network. Wirel. Netw. 2002, 8, 153–167.
[3]
Williams, B.; Camp, T. Comparison of Broadcasting Techniques for Mobile Ad HocNetworks. Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, 9–11 June 2002.
[4]
Zhang, Q.; Agrawal, D.P. Dynamic probabilistic broadcasting in MANETs. J. Parallel Distrib. Comput. 2005, 65, 220–233.
[5]
Hanashi, A.M.; Siddique, A.; Awan, I.; Woodward, M. Performance evaluation of dynamic probabilistic broadcasting for flooding in mobile ad hoc network. Simul. Model. Pract. Theory 2009, 17, 364–375.
[6]
Jeong, H.; Kim, J.; Yoo, Y. Adaptive broadcasting method using neighbor type information in wireless sensor networks. Sensors 2011, 11, 5952–5967.
[7]
Wieselthier, J.E.; Nguyen, G.D.; Ephremides, A. On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks. Proceeding of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, Israel, 26–30 March 2000; pp. 585–594.
[8]
Sausen, P.S.; Spohn, M.A.; Perkusich, A. Broadcast routing in wireless sensor networks with dynamic power management and multi-coverage backbones. Inform. Sci. 2010, 180, 653–663.
[9]
Miller, C.; Poellabauer, C. A decentralized approach to minimum-energy broadcasting in static ad hoc networks. Lect. Note. Comput. Sci. 2009, 5793, 298–311.
Ruiz, P.; Bouvry, P. Enhanced Distance Based Broadcasting Protocol with Reduced Energy Consumption. Proceeding of International Conference on High Performance Computing and Simulation (HPCS), Caen, France, 28 June–2 July 2010; pp. 249–258.
[12]
Ruiz, P.; Dorronsoro, B.; Valentini, G.; Pinel, F.; Bouvry, P. Optimisation of the enhanced distance based broadcasting protocol for MANETs. J. Supercomput. 2012, 62, 1213–1240.
[13]
Li, L.; Ramjee, R.; Buddhikot, M.; Miller, S. Network Coding-Based Broadcast in Mobile Ad-HocNetworks. Proceeding of 26th IEEE International Conference on Computer Communications, Anchorage, AK, USA, 6–12 May 2007; pp. 1739–1747.
[14]
Fang, W.; Liu, F.; Liu, Z.; Shu, L.; Nishio, S. Reliable Broadcast Transmission in Wireless Networks Based on Network Coding. Proceeding of IEEE Conference on Computer Communications Workshops, Shanghai, China, 10–15 April 2011; pp. 555–559.
[15]
Yang, S.; Wu, J. Efficient broadcasting using network coding and directional antennas in MANETs. IEEE Trans. Parallel Distrib. Syst. 2010, 21, 148–161.
[16]
Yang, Z.; Li, M.; Lou, W. R-Code: Network coding-based reliable broadcast in wireless mesh networks. Ad Hoc Netw. 2011, 9, 788–798.
[17]
Das, A.K.; Marks, R.J.; El-Sharkawi, M.; Arabshahi, P.; Gray, A. Minimum Power Broadcast Trees for Wireless Networks: Integer Programming Formulations. Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, San Franciso, CA, USA, 30 March–3 April 2003; pp. 1001–1010.
[18]
Yuan, D.; Bauer, J.; Haugland, D. Minimum-energy broadcast and multicast in wireless networks: An integer programming approach and improved heuristic algorithms. Ad Hoc Netw. 2008, 6, 696–717.
[19]
Montemanni, R.; Mahdabi, P. A linear programming-based evolutionary algorithm for the minimum power broadcast problem in wireless sensor networks. J. Math. Model. Algorithm 2011, 10, 145–162.
[20]
Wen, Y.F.; Liao, W. Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach. Wirel. Netw. 2011, 17, 1401–1421.
[21]
Wu, X.; Wang, X.; Liu, R. Solving Minimum Power Broadcast Problem in Wireless Ad-HocNetworks Using Genetic Algorithm. Proceedings of 6th Annual Communication Networks and Services Research Conference, Halifax, NS, USA, 5–8 May 2008; pp. 203–207.
[22]
Singh, A.; Bhukya, W.N. A hybrid genetic algorithm for the minimum energy broadcast problem in wireless ad hoc networks. Appl. Soft Comput. 2011, 11, 667–674.
[23]
Hernández, H.; Blum, C.; Francés, G. Ant colony optimization for energy-efficient broadcasting in ad-hoc networks. Lect. Note. Comput. Sci. 2008, 5217, 25–36.
[24]
Hernández, H.; Blum, C. Minimum energy broadcasting in wireless sensor networks: An ant colony optimization approach for a realistic antenna model. Appl. Soft Comput. 2011, 11, 5684–5694.
[25]
Hsiao, P.-C.; Chiang, T.C.; Fu, L.C. Particle Swarm Optimization for the Minimum Energy Broadcast Problem in Wireless Ad-HocNetworks. Proceeding of IEEE Word Congress on Computational Intelligence, Brisbane, QLD, Australia, 10–15 June 2012; pp. 1–8.
[26]
Lou, W.; Wu, J. Toward broadcast reliability in mobile Ad Hoc networks with double coverage. IEEE Trans. Mob. Comput. 2007, 6, 148–163.
[27]
Xu, H.; Garcia-Luna-Aceves, J.J. Efficient broadcast for wireless ad hoc networks with a realistic physical layer. Ad Hoc Netw. 2010, 8, 165–180.
[28]
Adjih, C.; Jacquet, P.; Viennot, L. Computing connected dominated sets with multipoint relays. Ad Hoc Sens. Wirel. Netw. 2005, 1, 27–39.
[29]
Wu, J.; Wei, L.; Dai, F. Extended multipoint relays to determine connected dominating sets in MANETs. IEEE Trans. Comput. 2006, 55, 334–347.
[30]
Han, B.; Fu, H.; Lin, L.; Jia, W. Efficient Construction of Connected Dominating Set in Wireless Ad Hoc Networks. Proceedings of 2004 IEEE International Conference on Mobile Ad-Hoc and Sensor Systems, Fort Lauderdale, FL, USA, 25–27 October 2004; pp. 570–572.
[31]
Liao, F.; Ma, L.; Fan, B. Efficient approximation algorithm for minimum connected dominating set. J. Chin. Comput. Syst. 2008, 29, 875–878.
[32]
Ghasemi, V.; Hashemi, S.N.; Mozaffari, M. Connected Dominating Set Construction Using an Efficient Pruning Method in Ad Hoc Networks. Proceeding of the 5th Annual ICST Wireless Internet Conference, Singapore, 1–3 March 2010; pp. 1–8.
[33]
Peng, W.; Lu, X. Efficient broadcast protocol in mobile ad hoc networks. J. Softw. 2001, 12, 530–535.
[34]
Rappaport, T.S. Wireless Communications: Principles and Practice, 2nd ed. ed.; Prentice Hall: New York, NY, USA, 1996.
[35]
Ruan, L.; Du, H.; Jia, X.; Wu, W.; Li, Y.; Ko, K.-I. A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 2004, 329, 325–330.
[36]
Tan, L.; Jin, L.; Pan, Y. Efficient placement of proxies for hierarchical reliable multicast. Comput. Commun. 2008, 31, 1842–1855.
[37]
Guha, S.; Khuller, S. Approximation algorithms for connected dominating sets. Algorithmica 1998, 20, 374–387.
