Heurística para o problema de construção de Árvore de Caminhos Mais Curtos Robusta para a Internet das Coisas
Abstract
In order to Internet of Things (IoT) become a reality, many challenges still need to be outweighed. Efficient protocols have to be specially resilient to high variations in transmission quality, due to constant changes in the network surrounding, which is characteristic of IoT. The most promising of these protocols is the IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). In this paper, we extend the RPL protocol in order to consider the uncertainty in the link quality. We model the RPL routing problem as a robust optimization variant of the Shortest Path Tree Problem, called Robust Shortest Path Tree (RSPT), in which the cost of each arc is defined by an interval of feasible values, instead of a single value. Then, we propose a heuristic that can be implemented as an extension of RPL protocol, providing a communication tree 13 % more efficient.
References
Aissi, H., Bazgan, C., and Vanderpooten, D. (2009). Min-max and min-max regret versions of combinatorial optimization problems: A survey. European journal of operational research, 197(2):427–438.
Averbakh, I. (2005). Computing and minimizing the relative regret in combinatorial optimization with interval data. Discrete Optimization, 2:273–287.
Bellman, R. (1956). On a routing problem. Technical report, DTIC Document.
Bondy, J. A. and Murty, U. S. R. (1976). Graph theory with applications, volume 290. Macmillan London.
Candia-Véjar, A., Álvarez-Miranda, E., and Maculan, N. (2011). Minmax regret combinatorial optimization problems: an algorithmic perspective. RAIRO-Operation Reserach, 45:101–129.
Chandy, K. M. and Misra, J. (1982). Distributed computation on graphs: Shortest path algorithms. Communications of the ACM, 25(11):833–837.
Coco, A. A., Júnior, J. C. A., Noronha, T. F., and Santos, A. C. (2014). An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem. Journal of Global Optimization, 60(2):265–287.
Conde, E. (2012). On a constant factor approximation for minmax regret problems using a symmetry point scenario. European Journal of Operational Research, 219:452–457.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271.
Giusto, D., Lera, A., Morabito, G., and Atzori, L. (2010). The Internet of Things. Springer.
Humblet, P. A. (1991). Another adaptive distributed shortest path algorithm. IEEE transactions on communications, 39(6):995–1003.
Karasan, O. E., Yaman, H., and Pinar, M. C. (2001). The robust shortest path problem with interval data. Technical report, Bilkent University, Department of Industrial Engineering.
Kasperski, A., Kobylan´ski, P., Kulej, M., and Zielínski, P. (2005). Minimizing maximal regret in discrete optimization problems with interval data, pages 193–208. Akademicka Oficyna Wydawnicza EXIT, Warszawa.
Kasperski, A. and Zielínski, P. (2006). An approximation algorithm for interval data minmax regret combinatorial optimization problems. Information Processing Letters, 97(5):177–180.
Kasperski, A. and Zielínski, P. (2007). On the existence of an fptas for minmax regret combinatorial optimization problems with interval data. Operations Research Letters, 35(4):525–532.
Kouvelis, P. and Yu, G. (1997). Robust discrete optimization and its applications, volume 14 of Nonconvex optimization and its applications. Springer.
Montemanni, R. and Gambardella, L. M. (2005a). A branch and bound algorithm for the robust spanning tree problem with interval data. European Journal of Operational Research, 161(3):771–779.
Montemanni, R. and Gambardella, L. M. (2005b). The robust shortest path problem with interval data via benders decomposition. 4OR, 3(4):315–328.
Montemanni, R., Gambardella, L. M., and Donati, A. V. (2004). A branch and bound algorithm for the robust shortest path problem with interval data. Operations Research Letters, 32(3):225–232.
Pérez, F., Astudillo, C. A., Bardeen, M., and Candia-Véjar, A. (2012). A simulated annealing approach for the minmax regret path problem. In Proceedings of the Congresso Latino Americano de Investigación Operativa (CLAIO) - Simpósio Brasileiro de Pesquisa Operacional (SBPO).
Salazar-Neumann, M. (2007). The robust shortest path and the single-source shortest path problems: interval data. In Annales Du LAMSADE.
Shelby, Z. and Bormann, C. (2011). 6LoWPAN: The wireless embedded Internet, volume 43 of Wiley Series in Communications Networking & Distributed Sistems. John Wiley & Sons.
Sugiyama, K., Tagawa, S., and Toda, M. (1981). Methods for visual understanding of hierarchical system structures. Systems, Man and Cybernetics, IEEE Transactions on, 11(2):109–125.
Träff, J. L. (1995). An experimental comparison of two distributed single-source shortest path algorithms. Parallel Computing, 21(9):1505–1532.
Vasseur, J., Agarwal, N., Hui, J., Shelby, Z., Bertrand, P., and Chauvenet, C. (2011). Rpl: The ip routing protocol designed for low power and lossy networks. Internet Protocol for Smart Objects (IPSO) Alliance.
Winter, T. (2012). Rpl: Ipv6 routing protocol for low-power and lossy networks. Technical report, Internet Engineering Task Force.
Wu, B. Y. and Chao, K. (2004). Shortest-paths trees. In Spanning Trees and Optimization Problems, pages 23–40. CRC Press.
Averbakh, I. (2005). Computing and minimizing the relative regret in combinatorial optimization with interval data. Discrete Optimization, 2:273–287.
Bellman, R. (1956). On a routing problem. Technical report, DTIC Document.
Bondy, J. A. and Murty, U. S. R. (1976). Graph theory with applications, volume 290. Macmillan London.
Candia-Véjar, A., Álvarez-Miranda, E., and Maculan, N. (2011). Minmax regret combinatorial optimization problems: an algorithmic perspective. RAIRO-Operation Reserach, 45:101–129.
Chandy, K. M. and Misra, J. (1982). Distributed computation on graphs: Shortest path algorithms. Communications of the ACM, 25(11):833–837.
Coco, A. A., Júnior, J. C. A., Noronha, T. F., and Santos, A. C. (2014). An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem. Journal of Global Optimization, 60(2):265–287.
Conde, E. (2012). On a constant factor approximation for minmax regret problems using a symmetry point scenario. European Journal of Operational Research, 219:452–457.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische mathematik, 1(1):269–271.
Giusto, D., Lera, A., Morabito, G., and Atzori, L. (2010). The Internet of Things. Springer.
Humblet, P. A. (1991). Another adaptive distributed shortest path algorithm. IEEE transactions on communications, 39(6):995–1003.
Karasan, O. E., Yaman, H., and Pinar, M. C. (2001). The robust shortest path problem with interval data. Technical report, Bilkent University, Department of Industrial Engineering.
Kasperski, A., Kobylan´ski, P., Kulej, M., and Zielínski, P. (2005). Minimizing maximal regret in discrete optimization problems with interval data, pages 193–208. Akademicka Oficyna Wydawnicza EXIT, Warszawa.
Kasperski, A. and Zielínski, P. (2006). An approximation algorithm for interval data minmax regret combinatorial optimization problems. Information Processing Letters, 97(5):177–180.
Kasperski, A. and Zielínski, P. (2007). On the existence of an fptas for minmax regret combinatorial optimization problems with interval data. Operations Research Letters, 35(4):525–532.
Kouvelis, P. and Yu, G. (1997). Robust discrete optimization and its applications, volume 14 of Nonconvex optimization and its applications. Springer.
Montemanni, R. and Gambardella, L. M. (2005a). A branch and bound algorithm for the robust spanning tree problem with interval data. European Journal of Operational Research, 161(3):771–779.
Montemanni, R. and Gambardella, L. M. (2005b). The robust shortest path problem with interval data via benders decomposition. 4OR, 3(4):315–328.
Montemanni, R., Gambardella, L. M., and Donati, A. V. (2004). A branch and bound algorithm for the robust shortest path problem with interval data. Operations Research Letters, 32(3):225–232.
Pérez, F., Astudillo, C. A., Bardeen, M., and Candia-Véjar, A. (2012). A simulated annealing approach for the minmax regret path problem. In Proceedings of the Congresso Latino Americano de Investigación Operativa (CLAIO) - Simpósio Brasileiro de Pesquisa Operacional (SBPO).
Salazar-Neumann, M. (2007). The robust shortest path and the single-source shortest path problems: interval data. In Annales Du LAMSADE.
Shelby, Z. and Bormann, C. (2011). 6LoWPAN: The wireless embedded Internet, volume 43 of Wiley Series in Communications Networking & Distributed Sistems. John Wiley & Sons.
Sugiyama, K., Tagawa, S., and Toda, M. (1981). Methods for visual understanding of hierarchical system structures. Systems, Man and Cybernetics, IEEE Transactions on, 11(2):109–125.
Träff, J. L. (1995). An experimental comparison of two distributed single-source shortest path algorithms. Parallel Computing, 21(9):1505–1532.
Vasseur, J., Agarwal, N., Hui, J., Shelby, Z., Bertrand, P., and Chauvenet, C. (2011). Rpl: The ip routing protocol designed for low power and lossy networks. Internet Protocol for Smart Objects (IPSO) Alliance.
Winter, T. (2012). Rpl: Ipv6 routing protocol for low-power and lossy networks. Technical report, Internet Engineering Task Force.
Wu, B. Y. and Chao, K. (2004). Shortest-paths trees. In Spanning Trees and Optimization Problems, pages 23–40. CRC Press.
Published
2015-07-20
How to Cite
CARVALHO, Iago; GOMES, Marcelo; NORONHA, Thiago; DUHAMEL, Christophe; VIEIRA, Luiz.
Heurística para o problema de construção de Árvore de Caminhos Mais Curtos Robusta para a Internet das Coisas. In: WORKSHOP ON PERFORMANCE OF COMPUTER AND COMMUNICATION SYSTEMS (WPERFORMANCE), 14. , 2015, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 70-78.
ISSN 2595-6167.
DOI: https://doi.org/10.5753/wperformance.2015.10398.
