Heurística para o problema de construção de Árvore de Caminhos Mais Curtos Robusta para a Internet das Coisas
Resumo
Para que a Internet das Coisas (IdC) torne-se uma realidade, muitos desafios ainda necessitam ser superados. Protocolos eficientes necessariamente precisam ser resilientes a variações na qualidade da transmissão, devido a constantes mudanças nos enlaces da rede, uma característica da IdC. O mais promissor destes protocolos é o IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). Neste trabalho nós estendemos o protocolo RPL de forma a considerar a incerteza na qualidade dos enlaces. O problema de roteamento do protocolo RPL é modelado como um problema de otimização robusta derivado do Problema da Árvore de Caminhos Mais Curtos, denominado Árvore de Caminhos Mais Curtos Robusta (ACMC-R), na qual cada arco é definido em um intervalo de valores factíveis ao invés de um único valor. Então, nós propomos uma heurística que pode ser implementada como uma extensão do protocolo RPL, obtendo uma árvore de comunicações até 13% mais eficiente.
Referências
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.
Publicado
20/07/2015
Como Citar
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 EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (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.
