Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Ana Carolina Ferreira Saraiva (anacarolsaraiva11@hotmail.com) on 2016-01-20T13:18:53Z
No. of bitstreams: 1
2015_UlissesRodriguesAfonseca.pdf: 2505441 bytes, checksum: 1925ec18041a11080e5285ce726482b2 (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2016-01-20T14:29:44Z (GMT) No. of bitstreams: 1
2015_UlissesRodriguesAfonseca.pdf: 2505441 bytes, checksum: 1925ec18041a11080e5285ce726482b2 (MD5) / Made available in DSpace on 2016-01-20T14:29:44Z (GMT). No. of bitstreams: 1
2015_UlissesRodriguesAfonseca.pdf: 2505441 bytes, checksum: 1925ec18041a11080e5285ce726482b2 (MD5) / As redes ad hoc sem fio constituem uma alternativa de baixo custo e de fácil implementação para o suporte a ações temporárias ou emergenciais em locais onde uma infraestrutura de comunicação convencional encontra-se indisponível. Apesar da sua capacidade de se adaptar a alterações na topologia, manter ou mesmo reforçar a conectividade da rede torna-se fundamental para o sucesso de diversas aplicações, em particular as de resgate e salvamento. Diversos trabalhos abordam esta questão no intuito de prover mecanismos para mitigar eventuais falhas na topologia que possam inviabilizar a conectividade da rede. Esta tese demonstra que a Comunicação Cooperativa pode ser efetivamente utilizada para aumentar a conectividade das redes ad hoc sem fio. Em uma CC, os nós portadores de uma única antena se beneficiam da diversidade espacial de forma semelhante a um sistema Multiple-Input Multiple-Output. Esta técnica permite ampliar o raio de comunicação dos nós devido à sua característica de combater o desvanecimento de sinal e os enlaces cooperativos podem ser empregados para reforçar a conectividade da rede. Contudo, as soluções existentes são, em sua maioria, centralizadas e apresentam um alto custo computacional, o que as tornam inviáveis no contexto da recuperação de conectividade. Ao aplicar o conhecimento global da topologia, o melhor enlace cooperativo, entre componentes isolados da rede, tem um custo computacional de O(|V | 2 • Λ), onde |V | corresponde ao número de nós da rede e Λ equivale ao custo para selecionar os nós auxiliares em um enlace cooperativo. Esta tese propõe duas soluções distribuídas que aplicam conhecimento localizado da topologia e permitem aumentar a conectividade da rede com objetivo de reforçar a conectividade por meio da utilização de enlaces cooperativos. As articulações, também conhecidas como nós críticos ou vértices de corte, são utilizadas para identificar possíveis pontos de segmentação da rede. A primeira solução requer O(∆(G) 2 • Λ) unidades de tempo para determinar, a partir das articulações, o melhor enlace cooperativo localizado a dois saltos, onde ∆(G) representa o grau da rede. Na segunda solução, os vizinhos das articulações computam o enlace cooperativo de reserva com um custo total de O(∆(G) • Λ). Em caso de segmentação da rede, estas soluções permitem que enlaces cooperativos sejam ativados para reestabelecer a conectividade. Da mesma forma, os enlaces cooperativos podem ser exploradas para manter a biconectivividade da rede e permitir o balanceamento de carga. Esta tese também apresenta uma alternativa distribuída para a localização de articulações. Comparado com soluções existentes, a alternativa proposta utiliza um volume de mensagens significativamente inferior. Uma abordagem incremental, e diferente das existentes na literatura, é utilizada para determinar as pontes e os componentes biconectados. / Wireless ad hoc networks are low cost and easy to deploy alternative to support temporary or emergency tasks in places where conventional communications infrastructure are unavailable. Despite its ability to adapt to topology changes, maintain or even enhance network connectivity is fundamental to the success of many applications, in particular those of search and rescue. Several papers address this issue in order to provide mechanisms to mitigate eventual network faults that might preclude network connectivity. This thesis shows that Cooperative Communication (CC) can be effectively used to increase the connectivity of ad hoc wireless networks and restore network connectivity when needed. In CC, nodes with a single antenna benefit from spatial diversity similarly to Multiple-Input Multiple-Output (MIMO) systems. This technique allows the nodes to extend their communication range due to its capability of reducing signal fading, thus making CC a suitable alternative for enhancing network connectivity. However, existing solutions are usually centralized and have a high computational cost, making them unviable in the context of connectivity recovery. When full network topology is known beforehand, the best cooperative link between isolated network components can be computed in O(|V | 2 • Λ) time, where |V | corresponds to the number of nodes network and Λ is the cost to select auxiliary nodes to form the cooperative link. This thesis proposes two distributed solutions that apply localized topology knowledge to increase and restore connectivity through the use of cooperative links. Articulations, also known as critical nodes or cut-vertices, are used to identify potential network segmentation points. The first solution requires O(∆(G) 2 • Λ) time units to determine, based on the articulation vicinity, the best cooperative link between clusters of nodes using two hop localized information, where ∆(G) represents the network degree. In the second solution, the articulation neighboring computes the backup cooperative link with a total cost of O(∆(G) • Λ) time. In case of network segmentation, the proposed solutions activate the computed cooperative links to restore connectivity. Also, the cooperative links can be exploited to obtain a biconnected network. This thesis also presents a distributed alternative to locate articulations. Compared to existing solutions, the proposed alternative uses a significantly lower volume of messages. Furthermore, by using an incremental approach, it is possible to determine bridges and biconnected components.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/19196 |
| Date | 27 November 2015 |
| Creators | Afonseca, Ulisses Rodrigues |
| Contributors | Bordim, Jacir Luiz |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data., info:eu-repo/semantics/openAccess |
Page generated in 0.003 seconds