A mathematical programming model for the Weighted Minimum Broadcast Time problem
Abstract
For a city to be classified as 'smart', should have sensors scattered across it. The dissemination of data in a sensor network is one of the challenges that must be overcome. In particular, a broadcasting problem is the WEIGHED MINIMUM BROADCAST TIME (WMBT). The WMBT is a data dissemination problem whose objective is to find a dissemination scheme that minimizes the time needed to perform the dissemination operation. An application of the WMBT for the process of updating the firmware of devices in a Bluetooth network will be presented. A mathematical model for the WMBT will be presented. Our model is compared with state-of-the-art algorithms for the problem. Experimental results show that it is able to attain competitive results.
Keywords:
Smart City, Weighed Minimum Broadcast Time, Mathematical programming model
References
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.
Published
2022-07-31
How to Cite
S., Alfredo Lima M.; OCHI, Luiz Satoru; NOGUEIRA, Bruno; PINHEIRO, Rian G. S..
A mathematical programming model for the Weighted Minimum Broadcast Time problem. In: BRAZILIAN WORKSHOP ON INTELLIGENT CITIES (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.
