Efficient implementation of a dominance protocol for wireless medium access

Mestrado em Engenharia Electrotécnica e de Computadores

Embedded computing systems went through extraordinary evolutions during the past two decades, representing nowadays one of the most promising technologies for improving a wide range of application areas such as energy/resource management, safety, health or entertainment. New sensors and actuators are leading to an unprecedented level of interaction between computing systems and their surrounding physical environment. These embedded computers tend to be networked, often wirelessly, and they are becoming denser, of larger scale and more pervasively deployed. Since the wireless channel is a "natural resource" which must be shared between this large number of embedded computers, the medium access control (MAC) protocol significantly influences the performance of the entire system. In particular, satisfying real-time requirements — something that is needed for a computer to tightly interact with its physical environment — plays an important role. One solution was recently proposed by Pereira, Andersson and Tovar. It was a prioritized and collision-free MAC protocol belonging to a family of protocols called dominance/binary countdown protocols. This solution was implemented in commercial-off-the-shelf (COTS) wireless sensor networks (WSN) platforms and the implementation was demonstrated to be working. Unfortunately, those platforms had (for the MAC protocol) unfavourable characteristics which lead to limited efficiency and excessive overhead of the MAC protocol. This work presents a new hardware platform, in the form of a network adapter for common WSN platforms, that allows an efficient implementation of dominance protocols for wireless medium access, allowing the medium access to be performed in less than 5 ms for 216 priority levels, which represents an overhead reduction of more than ten times as compared to the protocol implementation in COTS WSN platforms. Additionally, the overall energy consumption was reduced by approximately 45 % when compared to the theoretical best-case performance of the protocol implementation in COTS WSN platforms. iv This work also allowed, for the first time ever, an aggregate computation scheme for WSN to work exploiting the new efficient implementation of a binary/dominance countdown protocol.

No decurso das duas últimas décadas, os sistemas de computação embebidos sofreram uma extraordinária evolução, representando hoje em dia uma das mais promissoras tecnologias para possibilitar melhorias em áreas de aplicação tão diversas como a gestão de energia/recursos, segurança, saúde ou entretenimento. Novos sensores e actuadores conduzem a interacção entre os sistemas de computação e o ambiente físico onde se encontram inseridos até um nível sem precedentes. Estes computadores embebidos tendem a encontrar-se interligados (frequentemente recorrendo a ligações sem fios), sendo instalados de forma intensiva, e cada vez em maior escala. Sendo o meio de transmissão sem fios um “recurso natural” que deve ser partilhado entre este número elevado de computadores embebidos, o protocolo de controlo de acesso ao meio (do Inglês Medium Access Control - MAC) influencia significativamente o desempenho de todo o sistema. Em particular, a satisfação de requisitos temporais — algo que é necessário para uma estreira interacção entre um computador e o meio físico onde se insere — desempenha um papel muito importante. Uma solução foi recentemente proposta por Pereira, Andersson e Tovar, consistindo num protocolo MAC que implementa escalonamento baseado em prioridades e livre de colisões. Esta solução foi implementada em plataformas comercias de redes de sensores sem fios (do Inglês Wireless Sensor Networks - WSN), demonstrando-se funcional. Infelizmente, para a implementação do protocolo MAC, tais plataformas possuem características desfavoráveis, que conduzem a uma eficiência limitada do mesmo. Este trabalho apresenta uma nova platforma de hardware, sob a forma de um adaptador de rede, para platformas de WSN disponíveis comercialmente, que permite que a realização do acesso ao meio decorra em menos de 5 ms (para 216 níveis de prioridades). Tal representa uma redução superior a dez vezes no custo da execução do protocolo, quando comparada com a anterior implementação em platformas comercias de WSN. Adicionalmente, o consumo global de energia foi reduzido em aproximadamente 45 %, quando comparado com o melhor desempenho teórico possível da implementação em plataformas comerciais de WSN. vi Este trabalho permitiu ainda que, pela primeira vez, um esquema de computação agregada para WSN operasse tirando partido da implementação eficiente de um protocolo MAC apresentada neste trabalho.