Abstract
MultiPoint Relay (MPR) selection algorithm is a flooding technique for propagating a broadcast message inside an ad-hoc network which reduces the number of unnecessary broadcast messages in order to save more energy in the network, minimize the number of packet collisions, and speed up the propagation time. In this paper, we demonstrate that MPR selection is an application of Set Covering Problem (SCP). A few optimization methods are developed in this work to find the optimum solution including Simulated Annealing (SA), Tabu Search (TS), Genetic Algorithm (GA), and a new greedy algorithm. Extensive simulations are set up to evaluate the developed methods. The new algorithm is named Energy eFficient MPR or EF-MPR in short. The simulation results show that EF-MPR can reduce the number of MPR nodes up to 19%. Moreover, EF-MPR algorithm reduces the power-consumption of network up to 12% and speed up the propagation time by 9%.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Tseng Y-C, Ni S-Y, Chen Y-S, Sheu J-P (2002) The broadcast storm problem in a mobile ad hoc network. Wirel Netw 8(2/3):153–167
Qayyum A, Viennot L, Laouiti A (2000) Multipoint relaying: an efficient technique for flooding in mobile wireless networks. Technical Report, Institu National de Recherche en Informatique et en Automatique
Gonzalez TF (ed) (2007) Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC Press, London/Boca Raton
Chavatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233
Guturu P, Dantu R (2008) An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some np-hard problems in graph and set theory via clique finding. IEEE Trans Syst Man Cybern B 38(3):645–666
Chiang CC, Dai HK (2005) On the minimum-cost set-covering problem. In: Proceedings of the 2005 international conference on parallel and distributed processing techniques and applications, PDPTA’05, vol 3, pp 1199–1205
Khan AY, Rashid S, Iqbal A (2005) Mobility vs predictive MPR selection for mobile ad hoc networks using OLSR. In: Proceedings—IEEE 2005 international conference on emerging technologies, ICET 2005, vol 2005, pp 52–57
Chang Y-K, Ting Y-W, Wu S-C (2007) Power-efficient and path-stable broadcasting scheme for wireless ad hoc networks. In: Proceedings—21st international conference on advanced information networking and applications workshops/symposia, AINAW’07, vol 1, pp 707–712
Yawut C, Paillassa B, Dhaou R (2007) Mobility versus density metric for OLSR enhancement. Lecture notes in computer science, vol 4866, pp 2–17. Springer, Berlin
Nguyen D, Minet P (2007) Analysis of MPR selection in the OLSR protocol. In: Ainaw ’07: Proceedings of the 21st international conference on advanced information networking and applications workshops, Washington, DC, USA. IEEE Comput. Soc., Los Alamitos, pp 887–892
Liang O, Sekercioglu YA, Mani N (2006) Gateway multipoint relays-an MPR-based broadcast algorithm for ad hoc networks. In: 10th IEEE Singapore international conference on communication systems, 2006 ICCS 2006, pp. 1–6, 30 Nov 2006
Johnson DS (1973) Approximation algorithms for combinatorial problems. In: STOC ’73: Proceedings of the 5th annual ACM symposium on theory of computing, New York, USA. ACM, New York, pp 38–49
Lorena L, de Souza Lopes L (1997) Genetic algorithms applied to computationally difficult set covering problems. J Oper Res Soc 48(4):440–445
Huang W-C, Kao C-Y, Horng J-T (1994) Genetic algorithm approach for set covering problems. IEEE Conf Evol Comput Proc 2:569–574
Solar M, Parada V, Urrutia R (2002) A parallel genetic algorithm to solve the set-covering problem. Comput Oper Res 29(9):1221–1235
Glover F, Laguna F (1997) Tabu search. Kluwer Academic, Boston
Musliu N (2006) Local search algorithm for unicost set covering problem. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), vol 4031, pp 302–311. Springer, Berlin
Brusco MJ, Jacobs LW, Thompson GM (1996) A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated weighted set-covering problems. Working paper, Operations Management and Information Systems Department, Northern Illinois University
Jacobs LW, Brusco MJ (1995) Note: a local-search heuristic for large set-covering problems. Nav Res Logist 42(7):1129–1140
Hossain A, Chakrabarti S, Biswas PK (2008) Sensing models and its impact on network coverage in wireless sensor network. In: IEEE region 10 colloquium and the 3rd ICIIS, Dec 2008
The Network Simulator 2 (NS2). http://www.isi.edu/nsnam/ns/ (2010)
Johnson DB (1999) Validation of wireless and mobile network models and simulation. In DARPA/NIST network simulation validation workshop
Kunz T (2008) Energy-efficient variations of OLSR, Piscataway, NJ 08855-1331, United States, pp 517–522
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is funded by Malaysian Ministry of Science, Technology, and Innovation (MOSTI) under project number 79262.
Rights and permissions
About this article
Cite this article
Chizari, H., Hosseini, M., Salleh, S. et al. EF-MPR, a new energy eFficient multi-point relay selection algorithm for MANET. J Supercomput 59, 744–761 (2012). https://doi.org/10.1007/s11227-010-0470-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-010-0470-7