MGRASP and MSAL Algorithms for Centralized Traffic Management of Large Wireless Sensor Networks

• Autorzy: Czajko M.M. , Wojciechowski J.
• Konferencja: Evolutionary Computation and Global Optimization 2009 / National Conference (12 ; 1-3.06.2009 ; Zawoja, Poland)
• Języki publikacji: EN

Abstrakty

EN

This paper concerns a hop and degree constrained minimum spanning forest problem with the minimization of the number of trees (HDMSFMT). HDMSFMT arises during the calculation of the shortest paths in large wireless sensor networks (LWSNs) with centralized traffic management. This is a bi-criteria optimization problem, which is shown in this paper to be NP-hard. We formulate the HDMSFMT problem using formal mathematical notations. Two efficient heuristic algorithms for HDMSFMT are proposed and compared, namely Multi-objective Simulated Allocation (MSAL) and Multi-objective Greedy Randomized Adaptive Search Procedure (MGRASP). Numerical examples show that it is possible to achieve a set of feasible and satisfactory results for a wide range of graphs' types.

Słowa kluczowe

EN

Large Wireless Sensor Networks; LWSNs; MGRASP algorithm; MSAL algorithm; traffic management; optimization

PL

sieci bezprzewodowe; algorytm MGRASP; algorytm MSAL; zarządzanie ruchem; optymalizacja

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2009
• Tom: z. 169
• Strony: 43--50
• Opis fizyczny: Bibliogr. 8 poz., tab., rys., wykr.

Twórcy

autor

Czajko M.M.

autor

Wojciechowski J.

• Warsaw University of Technology, Institute of Radioelectronics, Warsaw, Poland Telekomunikacja Polska S.A., Warsaw, Poland,

Bibliografia

• [1] Baños, R., Gil, C., Paechter, B., Ortega, J. Parallelization of population-based multi-objective meta-heuristics: An empirical study. Applied Mathematical Modelling 30(2006) 578-592.
• [2] Da Cunha, A.S., Lucena, A. Algorithms for the degree-constrained minimum spanning tree problem. Electronic Notes in Discrete Mathematics 19(2005) 403-409.
• [3] Gouveia, L. Multicominodity flow models for spanning trees with hop constraints. European Journal of Operational Research 95(1996) 178-190.
• [4] Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H. Energy-efficient communication protocol for wireless microsensor networks. Proc. 33rd Hawaii Int’l. Conf. Sys. Sci. (2000).
• [5] Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H. An application-specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications (2002) vol. 1, Issue 4, 660-670.
• [6] Muruganathan, S.D., Ma, D.C., Bhasin, R.I., Fapojuwo, A.O. A centralized energy-efficient routing protocol for wireless sensor networks. IEEE Communications Magazine (2005), vol. 43, Issue 3, S8-13.
• [7] Pióro, M., Medhi, D. Routing, flow, and capacity design in communication and computer networks. Elsevier, 2004.
• [8] Rahimi-Vahed, A.R., Rabbani, M., Tavakkoli-Moghaddam, R., Torabi, S.A., Jolai, F. A multi-objective scatter search for a mixed-model assembly line sequencing problem. Advanced Engineering Informatics 21(2007) 85-99.