Caracterização de uma Jornada Máxima em MANETs
Resumo
Redes móveis ad-hoc (ou MANETs) exibem uma topologia dinâmica que pode ser modelada através de grafos que evoluem no tempo. Diversos protocolos distribuídos confiáveis, desenvolvidos para tais redes, fazem suposições quanto às características dos grafos necessárias para a satisfação das propriedades do sistema. Um delas diz respeito à difusão de mensagens para a rede, que só poderá ser garantida se, ao longo do tempo, existir um caminho entre cada par de nós do grafo, ou seja uma jornada. Estimar o tempo de uma jornada máxima é essencial para a configuração e qualidade de serviço do sistema. Esse trabalho apresenta um estudo analítico e experimental (através de simulação) para avaliar a conectividade de uma MANET e estimar o tempo de uma jornada máxima, dada as suas características, tais como densidade local e global. Como resultado, apresentamos uma equação probabilística do tempo de jornada máxima no grafo da MANET, em função da sua densidade.Referências
Barabási, A. and Stanley, H. (1995). Fractal concepts in surface growth. Cambridge UnivPr.
Bettstetter, C. (2002). On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, pages 80–91. ACM.
Bettstetter, C. (2004). On the connectivity of ad hoc networks. The Computer Journal, 47(4):432–447.
Bui Xuan, B., Ferreira, A., and Jarry, A. (2002). Computing shortest, fastest, and foremost journeys in dynamic networks. Technical Report RR-4589, INRIA.
Casteigts, A., Chaumette, S., and Ferreira, A. (2010a). Characterizing topological assumptions of distributed algorithms in dynamic networks. In Structural Information and Communication Complexity Conf., pages 126–140.
Casteigts, A., Flocchini, P., Mans, B., and Santoro, N. (2010b). Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility.
Casteigts, A., Flocchini, P., Quattrociocchi, W., and Santoro, N. (2011a). Time-varying graphs and dynamic networks. Technical report, University of Ottawa.
Casteigts, A., Flocchini, P., Quattrociocchi, W., and Santoro, N. (2011b). Time-varying graphs and dynamic networks. Ad-hoc, Mobile, and Wireless Networks, pages 346–359.
Chandra, T., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. Journal of the ACM (JACM), 43(4):685–722.
Chandra, T. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Chen, W., Toueg, S., and Aguilera, M. (2002). On the quality of service of failure detectors. Computers, IEEE Transactions on, 51(5):561–580.
Clementi, A., Monti, A., Pasquale, F., and Silvestri, R. (2011). Information spreading in stationary markovian evolving graphs. Parallel and Distributed Systems, IEEE Transactions on, 22(9):1425–1432.
Clementi, A., Monti, A., and Silvestri, R. (2010). Fast flooding over manhattan. Arxiv preprint arXiv:1002.3757.
Desai, M. and Manjunath, D. (2002). On the connectivity in finite ad hoc networks. Communications Letters, IEEE, 6(10):437–439.
Ferreira, A. (2004). Building a reference combinatorial model for manets. Network, IEEE, 18(5):24–29.
Foh, C., Liu, G., Lee, B., Seet, B., Wong, K., and Fu, C. (2005). Network connectivity of one-dimensional manets with random waypoint movement. Communications Letters, IEEE, 9(1):31–33.
Friedman, R. and Tcharny, G. (2005). Evaluating failure detection in mobile ad-hoc networks. Int. Journal of Wireless and Mobile Computing, 1(8).
Gonzalez, M., Hidalgo, C., and Barabási, A. (2008). Understanding individual human mobility patterns. Nature, 453(7196):779–782.
Greve, F., Sens, P., Arantes, L., and V.Simon (2011). A failure detector for wireless networks with unknown membership. In Euro-Par Conference, LNCS 6853, pages 27–38.
Khaledi, M., Hemmatyar, A., Rabiee, H., Mousavi, S., and Khaledi, M. (2009). Mobility analyzer: a framework for analysis and recognition of mobility traces in mobile ad-hoc networks. In New Technologies, Mobility and Security (NTMS), 2009 3rd International Conference on, pages 1–5. IEEE.
Litovsky, I. and Sopena, E. (1999). Graph relabelling systems and distributed algorithms. In Handbook of Graph Grammars and Computing by Graph Transformation. Concurrency, Parallelism, and Distribution, volume 3, pages 1–56.
Mandelbrot, B. (1983). The fractal geometry of nature. Wh Freeman.
Rhee, I., Shin, M., Hong, S., Lee, K., Kim, S., and Chong, S. (2011). On the levy-walk nature of human mobility. Networking, IEEE/ACM Transactions on, 19(3):630–643.
Sens, P., Greve, F., Arantes, L., Bouillaguet, M., and Simon, V. (2008). Um Detector de Falhas Assı́ncrono para Redes Móveis e Auto-Organizáveis. In Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuı́dos, Rio de Janeiro, RJ, Brazil.
Sridhar, N. (2006). Decentralized local failure detection in dynamic distributed systems.
Srivastava, V., Hilal, A., Thompson, M., Chattha, J., MacKenzie, A., and DaSilva, L. (2008). Characterizing mobile ad hoc networks: the maniac challenge experiment. In Proceedings of the third ACM international workshop on Wireless network testbeds, experimental evaluation and characterization, pages 65–72. ACM.
Xiang, H., Liu, J., and Kuang, J. (2010). Minimum node degree and connectivity of two-dimensional manets under random waypoint mobility model. In Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on, pages 2800–2805. IEEE.
Bettstetter, C. (2002). On the minimum node degree and connectivity of a wireless multihop network. In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, pages 80–91. ACM.
Bettstetter, C. (2004). On the connectivity of ad hoc networks. The Computer Journal, 47(4):432–447.
Bui Xuan, B., Ferreira, A., and Jarry, A. (2002). Computing shortest, fastest, and foremost journeys in dynamic networks. Technical Report RR-4589, INRIA.
Casteigts, A., Chaumette, S., and Ferreira, A. (2010a). Characterizing topological assumptions of distributed algorithms in dynamic networks. In Structural Information and Communication Complexity Conf., pages 126–140.
Casteigts, A., Flocchini, P., Mans, B., and Santoro, N. (2010b). Deterministic computations in time-varying graphs: Broadcasting under unstructured mobility.
Casteigts, A., Flocchini, P., Quattrociocchi, W., and Santoro, N. (2011a). Time-varying graphs and dynamic networks. Technical report, University of Ottawa.
Casteigts, A., Flocchini, P., Quattrociocchi, W., and Santoro, N. (2011b). Time-varying graphs and dynamic networks. Ad-hoc, Mobile, and Wireless Networks, pages 346–359.
Chandra, T., Hadzilacos, V., and Toueg, S. (1996). The weakest failure detector for solving consensus. Journal of the ACM (JACM), 43(4):685–722.
Chandra, T. and Toueg, S. (1996). Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225–267.
Chen, W., Toueg, S., and Aguilera, M. (2002). On the quality of service of failure detectors. Computers, IEEE Transactions on, 51(5):561–580.
Clementi, A., Monti, A., Pasquale, F., and Silvestri, R. (2011). Information spreading in stationary markovian evolving graphs. Parallel and Distributed Systems, IEEE Transactions on, 22(9):1425–1432.
Clementi, A., Monti, A., and Silvestri, R. (2010). Fast flooding over manhattan. Arxiv preprint arXiv:1002.3757.
Desai, M. and Manjunath, D. (2002). On the connectivity in finite ad hoc networks. Communications Letters, IEEE, 6(10):437–439.
Ferreira, A. (2004). Building a reference combinatorial model for manets. Network, IEEE, 18(5):24–29.
Foh, C., Liu, G., Lee, B., Seet, B., Wong, K., and Fu, C. (2005). Network connectivity of one-dimensional manets with random waypoint movement. Communications Letters, IEEE, 9(1):31–33.
Friedman, R. and Tcharny, G. (2005). Evaluating failure detection in mobile ad-hoc networks. Int. Journal of Wireless and Mobile Computing, 1(8).
Gonzalez, M., Hidalgo, C., and Barabási, A. (2008). Understanding individual human mobility patterns. Nature, 453(7196):779–782.
Greve, F., Sens, P., Arantes, L., and V.Simon (2011). A failure detector for wireless networks with unknown membership. In Euro-Par Conference, LNCS 6853, pages 27–38.
Khaledi, M., Hemmatyar, A., Rabiee, H., Mousavi, S., and Khaledi, M. (2009). Mobility analyzer: a framework for analysis and recognition of mobility traces in mobile ad-hoc networks. In New Technologies, Mobility and Security (NTMS), 2009 3rd International Conference on, pages 1–5. IEEE.
Litovsky, I. and Sopena, E. (1999). Graph relabelling systems and distributed algorithms. In Handbook of Graph Grammars and Computing by Graph Transformation. Concurrency, Parallelism, and Distribution, volume 3, pages 1–56.
Mandelbrot, B. (1983). The fractal geometry of nature. Wh Freeman.
Rhee, I., Shin, M., Hong, S., Lee, K., Kim, S., and Chong, S. (2011). On the levy-walk nature of human mobility. Networking, IEEE/ACM Transactions on, 19(3):630–643.
Sens, P., Greve, F., Arantes, L., Bouillaguet, M., and Simon, V. (2008). Um Detector de Falhas Assı́ncrono para Redes Móveis e Auto-Organizáveis. In Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuı́dos, Rio de Janeiro, RJ, Brazil.
Sridhar, N. (2006). Decentralized local failure detection in dynamic distributed systems.
Srivastava, V., Hilal, A., Thompson, M., Chattha, J., MacKenzie, A., and DaSilva, L. (2008). Characterizing mobile ad hoc networks: the maniac challenge experiment. In Proceedings of the third ACM international workshop on Wireless network testbeds, experimental evaluation and characterization, pages 65–72. ACM.
Xiang, H., Liu, J., and Kuang, J. (2010). Minimum node degree and connectivity of two-dimensional manets under random waypoint mobility model. In Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on, pages 2800–2805. IEEE.
Publicado
30/04/2012
Como Citar
SANTANTA, Alex Novaes de; GREVE, Fabíola; MIRANDA, José Garcia Vivas.
Caracterização de uma Jornada Máxima em MANETs. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 13. , 2012, Ouro Preto/MG.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 71-84.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2012.23081.
