Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2014-09-11T11:50:01Z
No. of bitstreams: 2
Dissertacao Diego Americo Guedes.pdf: 971567 bytes, checksum: a39a61e190ff600e318da0dd24eb108c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-11T11:50:01Z (GMT). No. of bitstreams: 2
Dissertacao Diego Americo Guedes.pdf: 971567 bytes, checksum: a39a61e190ff600e318da0dd24eb108c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work we present and evaluate a modeling methodology that describes the creation
of a topology for wireless mesh networks, and how this topology changes over time. The
modeling methodology is based on network science, which is a multidisciplinary research
area that has a lot of tools to help in the study and analysis of networks. In wireless mesh
networks, the relative importance of the nodes is often related to the topological aspects,
and data flow. However, due to the dynamics of the network, the relative importance of
the nodes may vary in time. In the context of network science, the concept of centrality
metric represents the relative importance of a node in the network. In this work we show
also that the current centrality metrics are not able to rank properly the nodes in wireless
mesh networks. Then we propose a new metric of centrality that ranks the most important
nodes in a wireless mesh network over time. We evaluate our proposal using data from
a case study of the proposed modeling methodology and also from real wireless mesh
networks, achieving satisfactory performance. The characteristics of our metric make it a
useful tool for monitoring dynamic networks. / Neste trabalho, apresentamos e avaliamos uma modelagem que descreve a criação de uma
topologia para redes em malha sem fio e como essa se altera no tempo. A modelagem é
baseada em ciência das redes (network science), uma área multidisciplinar de pesquisa
que possui uma grande quantidade de ferramentas para auxiliar no estudo e análise de
redes. Em redes em malha sem fio, a importância relativa dos nós é frequentemente
relacionada a aspectos topológicos e ao fluxo de dados. Entretanto, devido à dinamicidade
da rede, a importância relativa de um nó pode variar no tempo. No contexto de ciência de
redes, o conceito de métricas de centralidade reflete a importância relativa de um nó na
rede. Neste trabalho, mostramos também que as métricas atuais de centralidade não são
capazes de classificar de maneira adequada os nós em redes em malha sem fio. Propomos
então uma nova métrica de centralidade que classifica os nós mais importantes em uma
rede em malha sem fio ao longo do tempo. Avaliamos nossa proposta com dados obtidos
de um estudo de caso da modelagem proposta e de redes em malha sem fio reais, obtendo
desempenho satisfatório. As características da nossa métrica a tornam uma ferramenta útil
para monitoramento de redes dinâmicas.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3049 |
| Date | 11 September 2014 |
| Creators | Guedes, Diego Américo |
| Contributors | Cardoso, Kleber Vieira, Ziviani, Artur |
| Publisher | Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571, [1] Localização dos nós na Athens Wireless Metropolitan Network. http://wind.awmn.net/?page=gmap , July 2013. [2] Localização dos nós na Seattle Wireless. http://map.seattlewireless.net , July 2013. [3] AGUAYO, D.; BICKET, J.; BISWAS, S.; JUDD, G.; MORRIS, R. Link-level measurements from an 802.11b mesh network. SIGCOMM Computer Communication Review, 34(4):121–132, August 2004. [4] AIELLO, W.; CHUNG, F.; LU, L. A random graph model for massive graphs. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing, STOC ’00, p. 171–180, 2000. [5] AIELLO, W.; CHUNG, F.; LU, L. Handbook of massive data sets. chapter Random evolution in massive graphs, p. 97–122. Kluwer Academic Publishers, 2002. [6] AKYILDIZ, I. F.; WANG, X.; WANG, W. Wireless mesh networks: a survey. Comput. Netw. ISDN Syst., 47(4):445–487, 2005. [7] ALBERT, R.; JEONG, H.; BARABASI, A. L. The diameter of the world wide web. Nature, 401:130–131, 1999. [8] ALMIRON, M. G.; RAMOS, H. S.; OLIVEIRA, E. M.; AO G. M. DE MENEZES, J.; GUIDONI, D. L.; STANCIOLI, P. O.; DA CUNHA, F. D.; DE AQUINO, A. L. L.; MINI, R. A. F.; FRERY, A. C.; LOUREIRO, A. A. F. Redes complexas na modelagem de redes de computadores. Minicurso SBRC, 2010. [9] AMARAL, L. A.; OTTINO, J. M. Complex networks. The European Physical Journal B-Condensed Matter and Complex Systems, 38(2):147–162, 2004. [10] ANTIQUEIRA, L.; NUNES, M. G. V.; JÚNIOR, O. N. O.; COSTA, L. F. Complex networks in the assessment of quality text. In Physics, 2005. [11] BARABÁSI, A.-L.; ALBERT, R. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999. [12] BARABÁSI, A.-L.; ALBERT, R.; JEONG, H. Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications, 281(1-4):69–77, 2000. [13] BARABASI, A.-L.; OLTVAI, Z. N. Network biology: understanding the cell’s functional organization. Nature Reviews Genetics, 5(2):101–113, 2004. [14] BENDER, E. A.; CANFIELD, E. R. The asymptotic number of labeled graphs with given degree sequences. Journal of Combinatorial Theory, Series A, 24(3):296– 307, May 1978. [15] BERMAN, K. A. Vulnerability of scheduled networks and a generalization of Menger’s Theorem. Networks, 28(3):125–134, 1996. [16] BHADRA, S.; FERREIRA, A. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Proc. 2nd Intl. Conference on Ad Hoc Networks and Wirelsss (AdHoc-Now), p. 259–270, 2003. [17] BIANCHI, G. Performance analysis of the IEEE 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 18(3):535–547, 2000. [18] BICKET, J.; AGUAYO, D.; BISWAS, S.; MORRIS, R. Architecture and evaluation of an unplanned 802.11b mesh network. In: International conference on Mobile computing and networking, p. 31–42, 2005. [19] BICKET, J. C. Bit-rate selection in wireless networks. Master’s thesis, Master of Science in Computer Science and Engineering at the Massachusetts Institute of Technology, 2005. [20] BISWAS, S.; MORRIS, R. Opportunistic routing in multi-hop wireless networks. SIGCOMM Computer Communication Review, 34(1):69–74, 2004. [21] BONACICH, P. Factoring and weighting approaches to status scores and clique identification. Journal of Mathematical Sociology, 2(1):113–120, 1972. [22] BONACICH, P. Power and centrality: a family of measures. American Journal of Sociology, 92(5):1170–1182, 1987. [23] BONACICH, P.; LLOYD, P. Eigenvector-like measures of centrality for asymmetric relations. Social Networks, 23(3):191–201, 2001. [24] BONDY, J. A.; MURTY, U. S. R. Graph theory. Springer, 2008. [25] BORGATTI, S. P. Centrality and network flow. Social Networks, 27(1):55–71, 2005. [26] BÖRNER, K.; SANYAL, S.; VESPIGNANI, A. Network science. Annual Review of Information Science and Technology, 41(1):537–607, 2007. [27] Bornholdt, S.; Schuster, H. G., editors. Handbook of graphs and networks: from the genome to the Internet. John Wiley & Sons, Inc., 2003. [28] BRANDES, U.; FLEISCHER, D. Centrality measures based on current flow. In: Conference on Theoretical Aspects of Computer Science (STACS), p. 533–544. Springer-Verlag, 2005. [29] BRIN, S.; PAGE, L. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7):107–117, 1998. [30] CALDEIRA, S. M. G. Lendo Bohr ao pé da letra: análise de elementos conceituais em escritos de Niels Bohr. Master’s thesis, Universidade Federal da Bahia, 2007. [31] Carrington, P. J.; Scott, J.; Wasserman, S., editors. Models and methods in social network analysis. Cambridge University Press, 2005. [32] CASTEIGTS, A.; FLOCCHINI, P.; QUATTROCIOCCHI, W.; SANTORO, N. Timevarying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 2012. [33] CHAINTREAU, A.; MTIBAA, A.; MASSOULIE, L.; DIOT, C. The diameter of opportunistic mobile networks. In: Proceedings of the 2007 ACM CoNEXT conference, CoNEXT ’07, p. 1–12, 2007. [34] CHEN, Q.; HYUNSEOK, Q. C.; GOVINDAN, R.; JAMIN, S.; SHENKER, S. J.; WILLINGER, W. The origin of power laws in internet topologies revisited. In: In IEEE INFOCOM 2002, p. 608–617, 2002. [35] COHEN, J.; PIRES, K.; DUARTE JR., E. P. Medidas de conectividade baseadas em cortes de vértices para redes complexas. In: XXIX Simpósio Brasileiro de Redes e Sistemas Distribuídos (SBRC 2011), September 2012. [36] COSTA, L. D. F.; A., F.; TRAVIESO, G.; BOAS, V. P. R. Characterization of complex networks: A survey of measurements. Advances in Physics, 56(1):167– 242, 2006. [37] DIESTEL, R. Graph theory. Springer, 2006. [38] DUFFY, K.; LEITH, D. J.; LI, T.; MALONE, D. Improving fairness in multi-hop mesh networks using 802.11e. In: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006 4th International Symposium on, p. 1–8, 2006. [39] ELIANOS, F. A.; PLAKIA, G.; FRANGOUDIS, P. A.; POLYZOS, G. C. Structure and evolution of a large-scale wireless community network. In: IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks & Workshops (WoWMoM), p. 1–6, 2009. [40] ERD˝O S, P.; RÉNYI, A. On the evolution of random graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, p. 17–61, 1960. [41] ERD˝O S, P.; RÉNYI, A. On the strength of connectedness of a random graph. Acta Mathematica Hungarica, 12:261–267, 1961. [42] ERD˝O S, P.; RÉNYI, A. On random graphs. Publicationes Mathematicae Debrecen, 6:290–297, 1959. [43] EULER, L. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8:128–140, 1741. [44] EVERETTA, M.; BORGATTI, S. P. Ego network betweenness. Social Network, 27:31–38, 2005. [45] FALOUTSOS, M.; FALOUTSOS, P.; FALOUTSOS, C. On power-law relationships of the internet topology. SIGCOMM Computer Communication Review, 29(4):251– 262, 1999. [46] FLORY, P. J. Molecular size distribution in three dimensional polymers. III. Tetrafunctional branching units. Journal of the American Chemical Society, 63(11):3096–3100, 1941. [47] FOUNDATION, W. L. Wireless Leiden. http://www.wirelessleiden.nl , June 2012. [48] FOUNDATION, W. L. About Wireless Leiden. http://www.wirelessleiden.nl/en/about-wireless-leiden , May 2013. [49] FOUNDATION, W. L. Localização dos nós na Wireless Leiden. http://www.wirelessleiden.nl/en/coverage-map , July 2013. [50] FRANGOUDIS, P. A.; POLYZOS, G. C.; KEMERLIS, V. P. Wireless community networks: an alternative approach for nomadic broadband network access. IEEE Communications Magazine, 2011. [51] FREEMAN, L. Centrality in social networks conceptual clarification. Social Networks, 1(3):215–239, 1979. [52] FRIEDRICH, J.; FROHN, S.; GUBNER, S.; LINDEMANN, C. Understanding IEEE 802.11n multi-hop communication in wireless networks. In: International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), p. 321–326, May 2011. [53] GE, Y.; THAM, C.-K.; KONG, P.-Y.; ANG, Y.-H. Dynamic end-to-end capacity in IEEE 802.16 wireless mesh networks. Computer Network, 54:2147–2165, 2010. [54] GILBERT, E. Random graphs. The Annals of Mathematical Statistics, 30(4):1141– 1144, 1959. [55] GUEDES, D.; SILVA, E.; CARDOSO, K. Uma métrica para classificação dinâmica de nós em redes sem fio comunitárias. In: XXX Simpósio Brasileiro de Telecomunicações (SBrT 2012), September 2012. [56] GUEDES, D.; SILVA, E.; ZIVIANI, A.; CARDOSO, K. Dynamic labeling in wireless mesh networks. In: 4th IEEE Latin-American Conference on Communications (LATINCOM 2012), November 2012. [57] GUEDES, D.; ZIVIANI, A.; CARDOSO, K. Dynamic labeling in wireless mesh networks. IEEE Latin America Transactions, 11(3):948–954, 2013. [58] HODGMAN, T. C. A historical perspective on gene/protein functional assignment. Bioinformatics, 16(1):10–15, 2000. [59] HUBBELL, C. H. An input-output approach to clique identification. Sociometry, 28(4):377–399, 1965. [60] HWANG, W.; KIM, T.; RAMANATHAN, M.; ZHANG, A. Bridging centrality: graph mining from element level to group level. In: ACM international conference on Knowledge discovery and data mining (SIGKDD), p. 336–344, 2008. [61] JAMAKOVI´C, A. Characterization of complex networks – Application to robustness analysis. PhD thesis, Delft University of Technology, the Netherlands, 2008. [62] JÄRVELIN, K.; KEKÄLÄINEN, J. Cumulated gain-based evaluation of ir techniques. ACM Transactions on Information and System Security(TISSEC), 20(4):422– 446, 2002. [63] KATZ, L. A new status index derived from sociometric analysis. Psychometrika, 18(1):39–43, 1953. [64] KEMPE, D.; KLEINBERG, J.; KUMAR, A. Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4):820–842, 2002. [65] KENDALL, M. G. A new measure of rank correlation. Biometrika, 30(1-2):81–93, 1938. [66] KLEINBERG, J. The small-world phenomenon: an algorithmic perspective. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing, STOC ’00, p. 163–170, 2000. [67] KRAMER, R.; LOPEZ, A.; KOONEN, A. Municipal broadband access networks in the Netherlands - three successful cases, and how New Europe may benefit. In: International conference on Access networks (AcessNets), p. 1–8, September 2006. [68] MALCZEWSKI, J.; OGRYC˙ZAK, W. An interactive approach to the central facility location problem: locating pediatric hospitals in Warsaw. Geographical Analysis, 22(3):244–258, 1990. [69] MALONE, D.; DUFFY, K.; LEITH, D. Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions. IEEE/ACM Transactions on Networking, 15(1):159–172, 2007. [70] MEIRELLES, A. L. S. Estratégias para aumentar a acurácia do sensoriamento de espectro baseado em sensor de energia. Master’s thesis, Universidade Federal de Goiás, 2012. [71] MELUCCI, M. Weighted rank correlation in information retrieval evaluation. In: Information Retrieval Technology, volume 5839, p. 75–86. Springer Berlin / Heidelberg, 2009. [72] MENDES, G. A. Estudo de sistemas complexos com interações de longo alcance: percolação, redes e tráfego. PhD thesis, Universidade Federal do Rio Grande do Norte, 2010. [73] MILGRAM, S. The small world problem. Psychology Today, 2:60–67, 1967. [74] MOLLOY, M.; REED, B. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms, 6(2-3):161–180, 1995. [75] MONTGOMERY, D. C.; RUNGER, G. C. Applied statistics and probability for engineers, 4th Edition, and JustAsk! Set. John Wiley & Sons, 4 edition, May 2006. [76] NANDA, S.; KOTZ, D. Localized bridging centrality for distributed network analysis. In: International Conference on Computer Communications and Networks (ICCCN), p. 1–6, August 2008. [77] NANDA, S.; KOTZ, D. Social network analysis plugin (SNAP) for mesh networks. In: IEEE Wireless Communications and Networking Conference (WCNC), p. 725– 730, March 2011. [78] NETWORK SIMULATOR 3. Artigos validados no ns-3. http://www.nsnam.org/overview/publications/ , July 2013. [79] NETWORK SIMULATOR 3. Documentação do ns-3. http://www.nsnam.org/doxygen-release/index.html , July 2013. [80] NETWORK SIMULATOR 3. ns-3. http://www.nsnam.org/ , July 2013. [81] NEWMAN, M. E. J. The structure of scientific collaboration networks. Proceedings of the National Academy of Sciences of the United States of America, 98(2):404–409, 2001. [82] NEWMAN, M. E. J. The structure and function of complex networks. SIAM REVIEW, 45:167–256, 2003. [83] NEWMAN, M. E. J.; GIRVAN, M. Finding and evaluating community structure in networks. Physical Review E, 69(2), 2003. [84] NEWMAN, M. E. J. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39–54, 2005. [85] Newman, M. E. J.; Barabási, A. L.; Watts, D. J., editors. The structure and dynamics of networks. Princeton University Press, 2006. [86] NEWMAN, M.; WATTS, D. Scaling and percolation in the small-world network model. Phys. Rev. E, 60(6):7332–7342, 1999. [87] PALUMBO, M. C.; COLOSIMO, A.; GIULIANI, A.; FARINA, L. Functional essentiality from topology features in metabolic networks: a case study in yeast. FEBS Lett, 579(21):4642–4646, 2005. [88] PASTOR-SATORRAS, R.; VESPIGNANI, A. Evolution and structure of the Internet: a statistical physics approach. Cambridge University Press, 2004. [89] PINHEIRO, L.; SILVA, E. As redes cognitivas na ciência da informação brasileira: um estudo nos artigos científicos publicados nos periódicos da área. Ciência da Informação, 37(3), 2008. [90] RAPOPORT, A. Nets with distance bias. Bulletin of Mathematical Biophysics, 13:85–91, 1951. [91] RAPOPORT, A. Spread of information through a population with sociostructural bias: I. Assumption of transitivity. Bulletin of Mathematical Biology, 15(4):523–533, 1953. [92] RAPOPORT, A. Contribution to the theory of random and biased nets. Bulletin of Mathematical Biology, 19(4):257–277, December 1957. [93] REKA, A.; BARABÁSI. Statistical mechanics of complex networks. Reviews of Modern Physics, 74:47–97, 2002. [94] ROBINSON, J.; RANDHAWA, T. Saturation throughput analysis of ieee 802.11e enhanced distributed coordination function. Selected Areas in Communications, IEEE Journal on, 22(5):917–928, 2004. [95] SHIMBEL, A. Structural parameters of communication networks. Bulletin of Mathematical Biology, 15(4):501–507, 1953. [96] SHMOYS, D. B.; TARDOS, E.; AARDAL, K. Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, STOC ’97, p. 265–274, 1997. [97] SOLOMONOFF, R.; RAPOPORT, A. Connectivity of random nets. Bulletin of Mathematical Biology, 13(2):107–117, 1951. [98] TOREGAS, C.; SWAIN, R.; REVELLE, C.; BERGMAN, L. The location of emergency service facilities. Operations Research, 19:1363–1373, 1971. [99] VAN DRUNEN, R.; VAN GULIK, D.-W.; KOOLHAAS, J.; SCHUURMANS, H.; VIJN, M. Building a wireless community network in the netherlands. In: USENIX/Freenix Conference, p. 219–230, 2003. [100] WASSERMAN, S.; FAUST, K. Social network analysis: methods and applications. Cambridge University Press, 1994. [101] WATTS, D. J.; STROGATZ, S. H. Collective dynamics of small-world networks. Nature, 393(6684):409–10, 1998. [102] WATTS, D. J. Small worlds: The dynamics of networks between order and randomness. Princeton University Press, 1999. [103] WATTS, D. J. Six degrees: the science of a connected age (open market edition). W. W. Norton & Company, reprint edition, 2004. [104] WAXMAN, B. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(1-2):1617 – 1622, 1988. [105] WEHMUTH, K.; ZIVIANI, A. Um novo algoritmo distribuído para avaliação e localização de centralidade de rede. In: Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance), July 2011. [106] XUAN, B. B.; FERREIRA, A.; JARRY, A. Computing shortest, fastest, and foremost journeys in dynamic networks. International Journal of Foundations of Computer Science, 14(2):267–285, 2003. [107] YOU, L.; DONG, C.; CHEN, G.; DAI, Y.; ZHOU, W. Fhmesh: a flexible heterogeneous mesh networking platform. In: Sixth International Conference on Mobile Ad-hoc and Sensor Networks (MSN), 2010. |
Page generated in 0.005 seconds