Submitted by LIVIA FREITAS (livia.freitas@ufba.br) on 2016-02-16T13:17:03Z No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Approved for entry into archive by LIVIA FREITAS (livia.freitas@ufba.br) on 2016-03-10T15:07:14Z (GMT) No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Made available in DSpace on 2016-03-10T15:07:14Z (GMT). No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Um dos maiores desafios relacionados a rede de sensores sem fio e desenvolver técnicas que otimizem o uso dos recursos dos dispositivos (em especial energia). O controle de topologia se destaca por ser uma das principais técnicas utilizadas para otimizar o uso de energia em uma rede de sensores sem fio. Apesar de ser um tema bastante estudado, pouca atenção foi dada aos efeitos do overhearing no controle de topologia, ou seja, o efeito do custo de recebimento dos nós que receberam uma mensagem que não era destinada a eles. Esse trabalho apresenta um algoritmo para controle de topologia em rede de sensores sem fio local e distribuído, que tem como objetivo reduzir a potência de transmissão dos nós sensores para que eles utilizem os seus recursos de forma mais eficiente. A principal contribuição desse algoritmo em comparação aos trabalhos relacionados e que ele considera o custo de overhearing no calculo no controle de topologia da rede. Adicionalmente, o algoritmo otimiza a rotina que reduz o grafo de conectividade da rede e propõe uma estrategia para eliminar as arestas denominadas k-redundantes (para k ≥ 2) identificadas localmente.

Submitted by Diogo Barreiros (diogo.barreiros@ufba.br) on 2017-02-17T14:32:09Z No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-02-17T14:43:12Z (GMT) No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Made available in DSpace on 2017-02-17T14:43:12Z (GMT). No. of bitstreams: 1 DissertacaoMestrado-2010-MAT-Telemaco Neto, Ulisses.pdf: 1024112 bytes, checksum: db5d1b0272a08d44ab611b18b9990e3b (MD5) / Um dos maiores desafios relacionados a Rede de Sensores Sem Fio ´e desenvolver t´ecnicas que otimizem o uso dos recursos dos dispositivos (em especial energia). O Controle de Topologia se destaca por ser uma das principais t´ecnicas utilizadas para otimizar o uso de energia em uma Rede de Sensores Sem Fio. Apesar de ser um tema bastante estudado, pouca aten¸c˜ao foi dada aos efeitos do overhearing no Controle de Topologia, ou seja, o efeito do custo de recebimento dos n´os que receberam uma mensagem que n˜ao era destinada a eles. Esse trabalho apresenta um algoritmo para Controle de Topologia em Rede de Sensores Sem Fio local e distribu´ıdo, que tem como objetivo reduzir a potˆencia de transmiss˜ao dos n´os sensores para que eles utilizem os seus recursos de forma mais eficiente. A principal contribui¸c˜ao desse algoritmo em compara¸c˜ao aos trabalhos relacionados ´e que ele considera o custo de overhearing no c´alculo no controle de topologia da rede. Adicionalmente, o algoritmo otimiza a rotina que reduz o grafo de conectividade da rede e prop˜oe uma estrat´egia para eliminar as arestas denominadas k-redundantes (para k ≥ 2) identificadas localmente.

The objective of this dissertation is to investigate both the theoretical and practical aspects of redundancy elimination methods in data networks. Redundancy elimination provides a powerful technique to improve the efficiency of network links in the face of redundant data. In this work, the concept of network compression is introduced to address the redundancy elimination problem. Network compression aspires to exploit the statistical correlation in data to better suppress redundancy. In a nutshell, network compression enables memorization of data packets in some nodes in the network. These nodes can learn the statistics of the information source generating the packets which can then be used toward reducing the length of codewords describing the packets emitted by the source. Memory elements facilitate the compression of individual packets using the side-information obtained from memorized data which is called ``memory-assisted compression''. Network compression improves upon de-duplication methods that only remove duplicate strings from flows. The first part of the work includes the design and analysis of practical algorithms for memory-assisted compression. These algorithms are designed based on the theoretical foundation proposed in our group by Beirami et al. The performance of these algorithms are compared to the existing compression techniques when the algorithms are tested on the real Internet traffic traces. Then, novel clustering techniques are proposed which can identify various information sources and apply the compression accordingly. This approach results in superior performance for memory-assisted compression when the input data comprises sequences generated by various and unrelated information sources. In the second part of the work the application of memory-assisted compression in wired networks is investigated. In particular, networks with random and power-law graphs are studied. Memory-assisted compression is applied in these graphs and the routing problem for compressed flows is addressed. Furthermore, the network-wide gain of the memorization is defined and its scaling behavior versus the number of memory nodes is characterized. In particular, through our analysis on these graphs, we show that non-vanishing network-wide gain of memorization is obtained even when the number of memory units is a tiny fraction of the total number of nodes in the network. In the third part of the work the application of memory-assisted compression in wireless networks is studied. For wireless networks, a novel network compression approach via memory-enabled helpers is proposed. Helpers provide side-information that is obtained via overhearing. The performance of network compression in wireless networks is characterized and the following benefits are demonstrated: offloading the wireless gateway, increasing the maximum number of mobile nodes served by the gateway, reducing the average packet delay, and improving the overall throughput in the network. Furthermore, the effect of wireless channel loss on the performance of the network compression scheme is studied. Finally, the performance of memory-assisted compression working in tandem with de-duplication is investigated and simulation results on real data traces from wireless users are provided.