Um modelo de programação matemática para o problema Weighted Minimum Broadcast Time
Resumo
Para uma cidade ser classificada como "inteligente", ela precisa ter sensores espalhados por ela. A disseminação de dados em uma rede de sensores é um dos desafios que deve ser superado. Em particular, um problema de broadcasting é o WEIGHED MINIMUM BROADCAST TIME (WMBT). O WMBT é um problema de disseminação de dados cujo objetivo é encontrar um esquema de disseminação que minimize o número de passos necessários para executar a operação de disseminação. Será apresentado uma aplicação do WMBT para o processo de atualização de firmware de dispositivos em uma rede Bluetooth. Será apresentado um modelo matemático para o WMBT. Esta proposta comparou com adaptações de heurísticas do estado-da-arte. Os resultados experimentais mostram que o modelo pode ser aplicado para resolver o WMBT.
Palavras-chave:
Cidade inteligente, Weighed Minimum Broadcast Time, Modelo de programação matemática
Referências
Averbuch, A., Roditty, Y., and Shoham, B. (2000). Computation of broadcasting multiple messages in a positive weighted tree. Journal of Combinatorial Mathematics and Combinatorial Computing, 35:161–184.
Bucantanschi, D., Hoffmann, B., Hutson, K. R., and Kretchmar, R. M. (2007). A neighborhood search technique for the freeze tag problem. In Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, pages 97–113. Springer.
Chu, X. and Chen, Y. (2018). Time division inter-satellite link topology generation problem: Modeling and solution. International Journal of Satellite Communications and Networking, 36(2):194–206.
de Sousa, A., Gallo, G., Gutierrez, S., Robledo, F., Rodríguez-Bocca, P., and Romero, P. (2018). Heuristics for the minimum broadcast time. Electronic Notes in Discrete Mathematics, 69:165–172.
Dekker, A. (2002). Applying social network analysis concepts to military c4isr architectures. Connections, 24(3):93–103.
Elkin, M. and Kortsarz, G. (2003). Sublogarithmic approximation for telephone multicast: path out of jungle. In SODA, volume 3, pages 76–85.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.
Gilbert, E. N. (1959). Random graphs. Annals of Mathematical Statistics, 30(4):1141-1144.
Harutyunyan, H. A. and Jimborean, C. (2014). New heuristic for message broadcasting in networks. In 2014 IEEE 28th International Conference on Advanced Information Networking and Applications, pages 517–524. IEEE.
Harutyunyan, H. A. and Kamali, S. (2008). Efficient broadcasting in networks with weighted nodes. In 2008 14th IEEE International Conference on Parallel and Distributed Systems, pages 879–884.
Harutyunyan, H. A. and Kamali, S. (2017). Efficient broadcast trees for weighted vertices.
Discrete Applied Mathematics, 216:598–608. Levon Khachatrian’s Legacy in Extremal Combinatorics.
Harutyunyan, H. A. and Wang, W. (2010). Broadcasting algorithm via shortest paths. In 2010 IEEE 16th International Conference on Parallel and Distributed Systems, pages 299–305.
Hasson, Y. and Sipper, M. (2004). A novel ant algorithm for solving the minimum broadcast time problem. In Yao, X., Burke, E. K., Lozano, J. A., Smith, J., Merelo-Guervós, J. J., Bullinaria, J. A., Rowe, J. E., Tino, P., Kabán, A., and Schwefel, H.-P., editors, Parallel Problem Solving from Nature PPSN VIII, pages 501–510, Berlin, Heidelberg. Springer Berlin Heidelberg.
Hedetniemi, S. M., Hedetniemi, S. T., and Liestman, A. L. (1988). A survey of gossiping and broadcasting in communication networks. Networks, 18(4):319–349.
Hocaoglu, M. F. and Genç, I. (2019). Smart combat simulations in terms of industry 4.0. In Simulation for Industry 4.0, pages 247–273. Springer.
Hoelting, C. J., Schoenefeld, D. A., and Wainwright, R. L. (1996). A genetic algorithm for the minimum broadcast time problem using a global precedence vector. In ACM symposium on Applied Computing, pages 258–262.
Ivanova, M. (2019). Optimization Problems in Communication Networks and Multi-Agent Path Finding. PhD thesis, The University of Bergen.
Jansen, K. and Müller, H. (1995). The minimum broadcast time problem for several processor networks. Theoretical Computer Science, 147(1):69 – 85.
Keshavarz, H., Bagheri, A., Layeghi, K., and Seyed Iman Mahdavi (2011). A simulated annealing approach for the freeze-tag problem. In International Conference on Recent Trends in Information Systems, pages 94–98.
Koh, J. and Tcha, D. (1991). Information dissemination in trees with nonuniform edge transmission times. IEEE Transactions on Computers, 40(10):1174–1177.
Kortsarz, G. and Peleg, D. (1992). Approximation algorithms for minimum time broadcast. In Dolev, D., Galil, Z., and Rodeh, M., editors, Theory of Computing and Systems, pages 67–78, Berlin, Heidelberg. Springer Berlin Heidelberg.
Lazard, E. (1992). Broadcasting in dma-bound bounded degree graphs. Discrete Applied Mathematics, 37-38:387 – 400.
Lima, A., Aquino, A. L. L., Nogueira, B., and Pinheiro, R. G. S. (2022). A matheuristic approach for the minimum broadcast time problem using a biased random-key genetic algorithm. International Transactions in Operational Research.
Perera, C., Zaslavsky, A., Christen, P., and Georgakopoulos, D. (2014). Sensing as a service model for smart cities supported by internet of things. Transactions on emerging telecommunications technologies, 25(1):81–93.
Resende, M. G. C. (2011). Biased random-key genetic algorithms with applications in telecommunications. TOP, 20(1):130–153.
Robledo, F., Rodríguez-Bocca, P., and Romero, P. (2020). Optimal broadcast strategy in homogeneous point-to-point networks. In Nicosia, G., Ojha, V., La Malfa, E., Jansen, G., Sciacca, V., Pardalos, P., Giuffrida, G., and Umeton, R., editors, Machine Learning, Optimization, and Data Science, pages 448–457, Cham. Springer International Publishing.
Scheuermann and Wu (1984). Heuristic algorithms for broadcasting in point-to-point computer networks. IEEE Transactions on Computers, C-33(9):804–811.
Shang, W., Wan, P., and Hu, X. (2010). Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks. Frontiers of Mathematics in China, 5(1):75–87.
Slater, P. J., Cockayne, E. J., and Hedetniemi, S. T. (1981). Information dissemination in trees. SIAM Journal on Computing, 10(4):692–701.
Su, K., Li, J., and Fu, H. (2011). Smart city and the applications. In 2011 International Conference on Electronics, Communications and Control (ICECC), pages 1028–1031.
Toso, R. F. and Resende, M. G. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93.
Bucantanschi, D., Hoffmann, B., Hutson, K. R., and Kretchmar, R. M. (2007). A neighborhood search technique for the freeze tag problem. In Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, pages 97–113. Springer.
Chu, X. and Chen, Y. (2018). Time division inter-satellite link topology generation problem: Modeling and solution. International Journal of Satellite Communications and Networking, 36(2):194–206.
de Sousa, A., Gallo, G., Gutierrez, S., Robledo, F., Rodríguez-Bocca, P., and Romero, P. (2018). Heuristics for the minimum broadcast time. Electronic Notes in Discrete Mathematics, 69:165–172.
Dekker, A. (2002). Applying social network analysis concepts to military c4isr architectures. Connections, 24(3):93–103.
Elkin, M. and Kortsarz, G. (2003). Sublogarithmic approximation for telephone multicast: path out of jungle. In SODA, volume 3, pages 76–85.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.
Gilbert, E. N. (1959). Random graphs. Annals of Mathematical Statistics, 30(4):1141-1144.
Harutyunyan, H. A. and Jimborean, C. (2014). New heuristic for message broadcasting in networks. In 2014 IEEE 28th International Conference on Advanced Information Networking and Applications, pages 517–524. IEEE.
Harutyunyan, H. A. and Kamali, S. (2008). Efficient broadcasting in networks with weighted nodes. In 2008 14th IEEE International Conference on Parallel and Distributed Systems, pages 879–884.
Harutyunyan, H. A. and Kamali, S. (2017). Efficient broadcast trees for weighted vertices.
Discrete Applied Mathematics, 216:598–608. Levon Khachatrian’s Legacy in Extremal Combinatorics.
Harutyunyan, H. A. and Wang, W. (2010). Broadcasting algorithm via shortest paths. In 2010 IEEE 16th International Conference on Parallel and Distributed Systems, pages 299–305.
Hasson, Y. and Sipper, M. (2004). A novel ant algorithm for solving the minimum broadcast time problem. In Yao, X., Burke, E. K., Lozano, J. A., Smith, J., Merelo-Guervós, J. J., Bullinaria, J. A., Rowe, J. E., Tino, P., Kabán, A., and Schwefel, H.-P., editors, Parallel Problem Solving from Nature PPSN VIII, pages 501–510, Berlin, Heidelberg. Springer Berlin Heidelberg.
Hedetniemi, S. M., Hedetniemi, S. T., and Liestman, A. L. (1988). A survey of gossiping and broadcasting in communication networks. Networks, 18(4):319–349.
Hocaoglu, M. F. and Genç, I. (2019). Smart combat simulations in terms of industry 4.0. In Simulation for Industry 4.0, pages 247–273. Springer.
Hoelting, C. J., Schoenefeld, D. A., and Wainwright, R. L. (1996). A genetic algorithm for the minimum broadcast time problem using a global precedence vector. In ACM symposium on Applied Computing, pages 258–262.
Ivanova, M. (2019). Optimization Problems in Communication Networks and Multi-Agent Path Finding. PhD thesis, The University of Bergen.
Jansen, K. and Müller, H. (1995). The minimum broadcast time problem for several processor networks. Theoretical Computer Science, 147(1):69 – 85.
Keshavarz, H., Bagheri, A., Layeghi, K., and Seyed Iman Mahdavi (2011). A simulated annealing approach for the freeze-tag problem. In International Conference on Recent Trends in Information Systems, pages 94–98.
Koh, J. and Tcha, D. (1991). Information dissemination in trees with nonuniform edge transmission times. IEEE Transactions on Computers, 40(10):1174–1177.
Kortsarz, G. and Peleg, D. (1992). Approximation algorithms for minimum time broadcast. In Dolev, D., Galil, Z., and Rodeh, M., editors, Theory of Computing and Systems, pages 67–78, Berlin, Heidelberg. Springer Berlin Heidelberg.
Lazard, E. (1992). Broadcasting in dma-bound bounded degree graphs. Discrete Applied Mathematics, 37-38:387 – 400.
Lima, A., Aquino, A. L. L., Nogueira, B., and Pinheiro, R. G. S. (2022). A matheuristic approach for the minimum broadcast time problem using a biased random-key genetic algorithm. International Transactions in Operational Research.
Perera, C., Zaslavsky, A., Christen, P., and Georgakopoulos, D. (2014). Sensing as a service model for smart cities supported by internet of things. Transactions on emerging telecommunications technologies, 25(1):81–93.
Resende, M. G. C. (2011). Biased random-key genetic algorithms with applications in telecommunications. TOP, 20(1):130–153.
Robledo, F., Rodríguez-Bocca, P., and Romero, P. (2020). Optimal broadcast strategy in homogeneous point-to-point networks. In Nicosia, G., Ojha, V., La Malfa, E., Jansen, G., Sciacca, V., Pardalos, P., Giuffrida, G., and Umeton, R., editors, Machine Learning, Optimization, and Data Science, pages 448–457, Cham. Springer International Publishing.
Scheuermann and Wu (1984). Heuristic algorithms for broadcasting in point-to-point computer networks. IEEE Transactions on Computers, C-33(9):804–811.
Shang, W., Wan, P., and Hu, X. (2010). Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks. Frontiers of Mathematics in China, 5(1):75–87.
Slater, P. J., Cockayne, E. J., and Hedetniemi, S. T. (1981). Information dissemination in trees. SIAM Journal on Computing, 10(4):692–701.
Su, K., Li, J., and Fu, H. (2011). Smart city and the applications. In 2011 International Conference on Electronics, Communications and Control (ICECC), pages 1028–1031.
Toso, R. F. and Resende, M. G. (2015). A c++ application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93.
Publicado
31/07/2022
Como Citar
S., Alfredo Lima M.; OCHI, Luiz Satoru; NOGUEIRA, Bruno; PINHEIRO, Rian G. S..
Um modelo de programação matemática para o problema Weighted Minimum Broadcast Time. In: WORKSHOP BRASILEIRO DE CIDADES INTELIGENTES (WBCI), 3. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 61-70.
DOI: https://doi.org/10.5753/wbci.2022.223039.
