Broadcast cancellation in unstructured networks

Abstract

Technological advances on communications and information systems have led to the development of inexpensive electronic devices, powered by batteries, and with sensing capabilities. Nowadays, small devices are being ubiquitously embedded into the real world environment, with integrated wireless technologies communicating with their nearest neighbours, cooperating in a distributed system and increasing the support for the materialization of the Internet of Things (IoT) concept. To overcome the limitation of sending data beyond each sensor node's radio transmission range, the intermediate nodes work as relays, and broadcast is the main communication component for establishing multi-hop unstructured networks. However, state-of-the-art multi-hop broadcast communications are usually based on ooding mechanisms, that do not cope well with energy issues of battery powered devices. Our approach towards decreasing energy constraints is to improve broadcast e ciency by reducing the occurrence of unnecessary retransmissions. This dissertation addresses several techniques for stopping an ongoing search by controlling the broadcast propagation, even without prior knowledge of the network topology. Our main contribution, named broadcast cancellation, provides a distributed approach to cancel multi-hop broadcasts. In particular, studying the cancellation issues and discussing solutions using chasing packets, stochastic data structures and gradient approaches for hybrid search mechanisms. The proposed algorithms were evaluated and compared with state-of-the-art search mechanisms, using simulation techniques. Experimental results show that broadcast cancellation outperforms the competitive alternatives, balancing the trade-o among latency and energy e ciency.

Os avanços tecnológicos nos sistemas de informação e de comunicações têm impulsionado o desenvolvimento de pequenos dispositivos eletrónicos integrados, de custo reduzido, alimentados por baterias e munidos de vários tipos de sensores. Estes sensores inteligentes estão a ser embutidos de forma ubíqua no mundo real, comunicando através de redes sem fios diretamente com os seus vizinhos mais próximos, concretizando um sistema distribuído e materializando o conceito de Internet of Things (IoT). Para ultrapassar os limites físicos impostos pela propagação do sinal de rádio, os próprios dispositivos funcionam como repetidores multi-hop, formando redes não-estruturadas e comunicando por difusão. No entanto, quase todos os mecanismos de difusão são baseados em algoritmos que, de uma forma não controlada, contactam exaustivamente todos os nós da rede, sem as devidas preocupações com os consumos energéticos. A nossa abordagem vem melhorar a eficiência energética dos mecanismos de difusão, reduzindo a ocorrência de retransmissões desnecessárias.

Esta dissertação aborda várias técnicas para travar uma pesquisa em curso, sem conhecimento prévio da topologia de rede, mas controlando o avanço da difusão. A principal contribuição, “Cancelamento de Difusão", é um mecanismo distribuído para interromper a propagação da difusão em redes multi-hop. O trabalho investiga e debate soluções para o cancelamento baseadas em mecanismos de perseguição, estruturas de dados estocásticas e estratégias de pesquisas híbridas direcionadas por gradiente. Os algoritmos propostos foram avaliados e comparados com as alternativas mais recentes, recorrendo a técnicas de simulação, mostrando que o mecanismo de cancelamento de difusão é competitivo, equilibrando o balanceamento entre latência e eficiência energética.