Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

Grant-free protocols for massive multiple access

In next generation Internet-of-Things, the overhead introduced by grant-based multiple access protocols may engulf the access network as a consequence of the proliferation of connected devices. Grant-free access protocols are therefore gaining an increasing interest to support massive multiple access. In addition to scalability requirements, new demands have emerged for massive multiple access, including latency and reliability. The challenges envisaged for future wireless communication networks, particularly in the context of massive access, include: i) a very large population size of low power devices transmitting short packets; ii) an ever-increasing scalability requirement; iii) a mild fixed maximum latency requirement; iv) a non-trivial requirement on reliability. To this aim, we suggest the joint utilization of grant-free access protocols, massive MIMO at the base station side, framed schemes to let the contention start and end within a frame, and succesive interference cancellation techniques at the base station side. In essence, this approach is encapsulated in the concept of coded random access with massive MIMO processing. These schemes can be explored from various angles, spanning the protocol stack from the physical (PHY) to the medium access control (MAC) layer. In this thesis, we delve into both of these layers, examining topics ranging from symbol-level signal processing to succesive interference cancellation-based scheduling strategies. In parallel with proposing new schemes, our work includes a theoretical analysis aimed at providing valuable system design guidelines. As a main theoretical outcome, we propose a novel joint PHY and MAC layer design based on density evolution on sparse graphs.

Sistema de contagem de tráfego e classificação automática de veículos, em tempo real e sem fios

Esta tese tem por objectivo o desenho e avaliação de um sistema de contagem e classificação de veículos automóveis em tempo-real e sem fios. Pretende, também, ser uma alternativa aos actuais equipamentos, muito intrusivos nas vias rodoviárias. Esta tese inclui um estudo sobre as comunicações sem fios adequadas a uma rede de equipamentos sensores rodoviários, um estudo sobre a utilização do campo magnético como meio físico de detecção e contagem de veículos e um estudo sobre a autonomia energética dos equipamentos inseridos na via, com recurso, entre outros, à energia solar. O projecto realizado no âmbito desta tese incorpora, entre outros, a digitalização em tempo real da assinatura magnética deixada pela passagem de um veículo, no campo magnético da Terra, o respectivo envio para servidor via rádio e WAN, Wide Area Network, e o desenvolvimento de software tendo por base a pilha de protocolos ZigBee. Foram desenvolvidas aplicações para o equipamento sensor, para o coordenador, para o painel de controlo e para a biblioteca de Interface de um futuro servidor aplicacional. O software desenvolvido para o equipamento sensor incorpora ciclos de detecção e digitalização, com pausas de adormecimento de baixo consumo, e a activação das comunicações rádio durante a fase de envio, assegurando assim uma estratégia de poupança energética. Os resultados obtidos confirmam a viabilidade desta tecnologia para a detecção e contagem de veículos, assim como para a captura de assinatura usando magnetoresistências. Permitiram ainda verificar o alcance das comunicações sem fios com equipamento sensor embebido no asfalto e confirmar o modelo de cálculo da superfície do painel solar bem como o modelo de consumo energético do equipamento sensor.

A time division beacon scheduling mechanism for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks

While the IEEE 802.15.4/Zigbee protocol stack is being considered as a promising technology for low-cost low-power Wireless Sensor Networks (WSNs), several issues in the standard specifications are still open. One of those ambiguous issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for ensuring QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multihop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes a synchronization mechanism based on Time Division Beacon Scheduling to construct cluster-tree WSNs. We also propose a methodology for an efficient duty cycle management in each router (cluster-head) of a cluster-tree WSN that ensures the fairest use of bandwidth resources. The feasibility of the proposal is clearly demonstrated through an experimental test bed based on our own implementation of the IEEE 802.15.4/Zigbee protocol.

Collision-free beacon scheduling mechanisms for IEEE 802.15.4/Zigbee cluster-tree wireless sensor networks

The recently standardized IEEE 802.15.4/Zigbee protocol stack offers great potentials for ubiquitous and pervasive computing, namely for Wireless Sensor Networks (WSNs). However, there are still some open and ambiguous issues that turn its practical use a challenging task. One of those issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This paper tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes two collision-free beacon frame scheduling schemes. We strongly believe that the results provided in this paper trigger a significant step towards the practical and efficient use of IEEE 802.15.4/Zigbee cluster-tree networks.

On the performance limits of slotted CSMA/CA in IEEE 802.15.4 for broadcast transmissions in wireless sensor networks

The IEEE 802.15.4 has been adopted as a communication protocol standard for Low-Rate Wireless Private Area Networks (LRWPANs). While it appears as a promising candidate solution for Wireless Sensor Networks (WSNs), its adequacy must be carefully evaluated. In this paper, we analyze the performance limits of the slotted CSMA/CA medium access control (MAC) mechanism in the beacon-enabled mode for broadcast transmissions in WSNs. The motivation for evaluating the beacon-enabled mode is due to its flexibility and potential for WSN applications as compared to the non-beacon enabled mode. Our analysis is based on an accurate simulation model of the slotted CSMA/CA mechanism on top of a realistic physical layer, with respect to the IEEE 802.15.4 standard specification. The performance of the slotted CSMA/CA is evaluated and analyzed for different network settings to understand the impact of the protocol attributes (superframe order, beacon order and backoff exponent), the number of nodes and the data frame size on the network performance, namely in terms of throughput (S), average delay (D) and probability of success (Ps). We also analytically evaluate the impact of the slotted CSMA/CA overheads on the saturation throughput. We introduce the concept of utility (U) as a combination of two or more metrics, to determine the best offered load range for an optimal behavior of the network. We show that the optimal network performance using slotted CSMA/CA occurs in the range of 35% to 60% with respect to an utility function proportional to the network throughput (S) divided by the average delay (D).

Implementation of the i-GAME mechanism in IEEE 802.15.4 WPANs

This technical report describes the implementation details of the Implicit GTS Allocation Mechanism (i-GAME), for the IEEE 802.15.4 protocol. The i-GAME was implemented in nesC/TinyOS for the CrossBow MICAz mote, over our own implementation of the IEEE 802.15.4 protocol stack. This document provides the implementation details, including a description of the i-GAME software interfaces.

Beacon scheduling in cluster-tree IEEE 802.15.4/ZigBee wireless sensor networks

The recently standardized IEEE 802.15.4/Zigbee protocol stack offers great potentials for ubiquitous and pervasive computing, namely for Wireless Sensor Networks (WSNs). However, there are still some open and ambiguous issues that turn its practical use a challenging task. One of those issues is how to build a synchronized multi-hop cluster-tree network, which is quite suitable for QoS support in WSNs. In fact, the current IEEE 802.15.4/Zigbee specifications restrict the synchronization in the beacon-enabled mode (by the generation of periodic beacon frames) to star-based networks, while it supports multi-hop networking using the peer-to-peer mesh topology, but with no synchronization. Even though both specifications mention the possible use of cluster-tree topologies, which combine multi-hop and synchronization features, the description on how to effectively construct such a network topology is missing. This report tackles this problem, unveils the ambiguities regarding the use of the cluster-tree topology and proposes two collisionfree beacon frame scheduling schemes.

Building a person home behavior model based on data from smart house sensors 2015

Dissertação para a obtenção do grau de Mestre em Engenharia Electrotécnica Ramo de Energia

Environmental/Regatta Buoy: Telemetry and Configuration

A monitorização ambiental é essencial para a tomada de decisões tanto na ciência como na indústria. Em particular, uma vez que a água é essencial à vida e a superfície da Terra é composta principalmente por água, a monitorização do clima e dos parâmetros relacionados com a água em ecossistemas sensíveis, tais como oceanos, lagoas, rios e lagos, é de extrema importância. Um dos métodos mais comuns para monitorar a água é implantar bóias. O presente trabalho está integrado num projeto mais amplo, com o objetivo de projectar e desenvolver uma bóia autónoma para a investigação científica com dois modos de funcionamento: (i) monitorização ambiental ; e (ii) baliza ativa de regata. Assim, a bóia tem duas aplicações principais: a coleta e armazenamento de dados e a assistência a regatas de veleiros autónomos. O projeto arrancou há dois anos com um grupo de quatro estudantes internacionais. Eles projetaram e construíram a estrutura física, compraram e montaram o sistema de ancoragem da bóia e escolherem a maioria dos componentes electrónicos para o sistema geral de controlo e medição. Este ano, durante o primeiro semestre, dois estudantes belgas - Jeroen Vervenne e Hendrick Verschelde – trabalharam nos subsistemas de recolha e armazenamento de dados (unidade de controlo escrava) e de telemetria e configuração (unidade de controlo mestre) assim como definiram o protocolo de comunicação da aplicação. O trabalho desta tese continua o desenvolvimento do subsistema de telemetria e configuração. Este subsistema _e responsável pela configuração do modo de funcionamento e dos sensores assim como pela comunicação com a estacão de base (controlo ambiental), barcos (baliza ativa de regata) e com o subsistema de recolha e armazenamento de dados. O desenvolvimento do subsistema de recolha e armazenamento de dados, que coleta e armazena num cartão SD os dados dos sensores selecionados, prossegue com outro estudante belga - Mathias van Flieberge. O objetivo desta tese é, por um lado, implementar o subsistema de telemetria e de configuração na unidade de controle mestre e, por outro lado, refinar e implementar, conjuntamente com Mathias van Flieberge, o protocolo de nível de aplicação projetado. Em particular, a unidade de controlo mestre deve processar e atribuir prioridades às mensagens recebidas da estacão base, solicitar dados à unidade de controlo escrava e difundir mensagens com informação de posição e condições de vento e água no modo de regata. Enquanto que a comunicação entre a unidade de controlo mestre e a estacão base e a unidade de controlo mestre e os barcos é sem fios, a unidade de controlo mestre e a unidade de controlo escrava comunicam através de uma ligação série. A bóia tem atualmente duas limitações: (i) a carga máxima é de 40 kg; e (ii) apenas pode ser utilizada em rios ou próximo da costa dada à limitação de distância imposta pela técnica de comunicação sem fios escolhida.

SOLAP+: extending the interaction model

Thesis submitted to Faculdade de Ciências e Tecnologia of the Universidade Nova de Lisboa, in partial fulfillment of the requirements for the degree of Master in Computer Science

Environmental/Regatta Buoy: Sensing System

Um dos principais objetivos da ciência é perceber a natureza, i.e., descobrir e explicar o funcionamento do mundo que nos rodeia. Para tal, os cientistas precisam de coligir dados e monitorar o meio ambiente. Em particular, considerando que cerca de 70% da Terra é coberta por água, a coleta de parâmetros de caracterização da água de grandes superfícies é uma prioridade. A monitorização das condições da água é feita principalmente através de bóias. No entanto, as bóias disponíveis no mercado não satisfazem as necessidades existentes. Esta é uma das principais razões que levaram o Laboratório de Sistemas Autónomos (LSA) do Instituto Superior de Engenharia do Porto a lançarem um projeto para o desenvolvimento de uma bóia reconfigurável e com dois modos de funcionamento: monitorização ambiental e baliza ativa de regata. O segundo modo é destinado a regatas de veleiros autónomos. O projeto começou há um ano com um projeto do European Project Project [1] (EPS), realizado por quatro estudantes internacionais, destinado à construção da estrutura da bóia e à selecção dos componentes mais adequados para o sistema de medição e controlo. A arquitetura que foi definida para este sistema é do tipo mestre-escravo e é composta por uma unidade de controlo mestre para a telemetria e configuração e uma unidade de controlo escrava para a medição e armazenamento de dados. O desenvolvimento do projeto continuou com dois estudantes belgas que trabalharam na comunicação e no armazenamento de dados. Este projeto, que prossegue com o desenvolvimento da medição e do armazenamento de dados do lado da unidade de controlo escrava, tem os seguintes objetivos: (i ) implementar o protocolo de comunicação na unidade de controlo escrava; (ii ) coligir e armazenar os dados dos sensores no cartão SD em tempo real; (iii ) fornecer dados em tempo útil; e (iv) recuperar dados do cartão SD em tempo diferido. As contribuições anteriores foram estudadas e foi feito um levantamento dos projetos congéneres existentes. O desenvolvimento do projeto atual começou com o protocolo de comunicação. Este protocolo, que foi projetado pelos alunos anteriores, foi um bom ponto de partida. No entanto, o protocolo foi atualizado e melhorado com novas funcionalidades. Esta última componente foi um trabalho conjunto com Laurens Allart, que esteve a trabalhar no subsistema de telemetria e de configuração durante este semestre. O protocolo foi implementado do lado da unidade de controlo escrava através de uma estrutura de múltiplas actividades paralelas (multithreaded). Esta estrutura recebe as mensagens da unidade mestre, executa as ações solicitadas e envia de volta o resultado. A bóia é um dispositivo reconfigurável multimodo que pode ser expandido com novos modos de operação no futuro. Infelizmente, sofre de algumas limitações: suporta uma carga máxima de 40 kg e tem uma área de implantação limitada pela distância máxima à estacão base.

Formation Control Driven by Cooperative Object Tracking

In this paper we introduce a formation control loop that maximizes the performance of the cooperative perception of a tracked target by a team of mobile robots, while maintaining the team in formation, with a dynamically adjustable geometry which is a function of the quality of the target perception by the team. In the formation control loop, the controller module is a distributed non-linear model predictive controller and the estimator module fuses local estimates of the target state, obtained by a particle filter at each robot. The two modules and their integration are described in detail, including a real-time database associated to a wireless communication protocol that facilitates the exchange of state data while reducing collisions among team members. Simulation and real robot results for indoor and outdoor teams of different robots are presented. The results highlight how our method successfully enables a team of homogeneous robots to minimize the total uncertainty of the tracked target cooperative estimate while complying with performance criteria such as keeping a pre-set distance between the teammates and the target, avoiding collisions with teammates and/or surrounding obstacles.

Teleoperation of a service robot using a mobile device

Teleoperation is a concept born with the rapid evolution of technology, with an intuitive meaning "operate at a distance." The first teleoperation system was created in the mid 1950s, which were handled chemicals. Remote controlled systems are present nowadays in various types of applications. This dissertation presents the development of a mobile application to perform the teleoperation of a mobile service robot. The application integrates a distributed surveillance (the result of a research project QREN) and led to the development of a communication interface between the robot (the result of another QREN project) and the vigilance system. It was necessary to specify a communication protocol between the two systems, which was implemented over a communication framework 0MQ (Zero Message Queue). For the testing, three prototype applications were developed before to perform the test on the robot.

Desenvolupament d'un sistema de transferència de software per una placa entrenadora

El departament d’electrònica i telecomunicacions de la Universitat de Vic ha dissenyat un conjunt de plaques entrenadores amb finalitat educativa. Perquè els alumnes puguin utilitzar aquestes plaques com a eina d’estudi, és necessari disposar d’un sistema de gravació econòmic i còmode. La major part dels programadors, en aquest cas, no compleixen amb aquests requeriments. L’objectiu d’aquest projecte és dissenyar un sistema de programació que utilitzi la comunicació sèrie i que no requereixi d'un hardware ni software específics. D’aquesta manera, obtenim una placa autònoma i un programador gratuït, de muntatge ràpid i simple d’utilitzar. El sistema de gravació dissenyat s’ha dividit en tres blocs. Per una banda, un programa que anomenem “programador” encarregat de transferir codi de programa des de l’ordinador al microcontrolador de la placa entrenadora. Per altra banda, un programa anomenat “bootloader”, situat al microcontrolador, permet rebre aquest codi de programa i emmagatzemar-lo a les direccions de memòria de programa corresponents. Com a tercer bloc, s’implementa un protocol de comunicació i un sistema de control d’errors per tal d’assegurar una correcta comunicació entre el “programador” i el “bootloader”. Els objectius d’aquest projecte s’han complert i per les proves realitzades, el sistema de programació ha funcionat correctament.