Exploiting a prioritized MAC protocol to efficiently compute min and max in multihop networks

Consider a wireless sensor network (WSN) where a broadcast from a sensor node does not reach all sensor nodes in the network; such networks are often called multihop networks. Sensor nodes take sensor readings but individual sensor readings are not very important. It is important however to compute aggregated quantities of these sensor readings. The minimum and maximum of all sensor readings at an instant are often interesting because they indicate abnormal behavior, for example if the maximum temperature is very high then it may be that a fire has broken out. We propose an algorithm for computing the min or max of sensor reading in a multihop network. This algorithm has the particularly interesting property of having a time complexity that does not depend on the number of sensor nodes; only the network diameter and the range of the value domain of sensor readings matter.

Waste collection routing-limited multiple landfills and heterogeneous fleet

This article deals with a real-life waste collection routing problem. To efficiently plan waste collection, large municipalities may be partitioned into convenient sectors and only then can routing problems be solved in each sector. Three diverse situations are described, resulting in three different new models. In the first situation, there is a single point of waste disposal from where the vehicles depart and to where they return. The vehicle fleet comprises three types of collection vehicles. In the second, the garage does not match any of the points of disposal. The vehicle is unique and the points of disposal (landfills or transfer stations) may have limitations in terms of the number of visits per day. In the third situation, disposal points are multiple (they do not coincide with the garage), they are limited in the number of visits, and the fleet is composed of two types of vehicles. Computational results based not only on instances adapted from the literature but also on real cases are presented and analyzed. In particular, the results also show the effectiveness of combining sectorization and routing to solve waste collection problems.

LNT: a logical neighbor tree secure group communication scheme for wireless sensor networks

Secure group communication is a paradigm that primarily designates one-to-many communication security. The proposed works relevant to secure group communication have predominantly considered the whole network as being a single group managed by a central powerful node capable of supporting heavy communication, computation and storage cost. However, a typical Wireless Sensor Network (WSN) may contain several groups, and each one is maintained by a sensor node (the group controller) with constrained resources. Moreover, the previously proposed schemes require a multicast routing support to deliver the rekeying messages. Nevertheless, multicast routing can incur heavy storage and communication overheads in the case of a wireless sensor network. Due to these two major limitations, we have reckoned it necessary to propose a new secure group communication with a lightweight rekeying process. Our proposal overcomes the two limitations mentioned above, and can be applied to a homogeneous WSN with resource-constrained nodes with no need for a multicast routing support. Actually, the analysis and simulation results have clearly demonstrated that our scheme outperforms the previous well-known solutions.

RadiaLE: A framework for designing and assessing link quality estimators in wireless sensor networks

Stringent cost and energy constraints impose the use of low-cost and low-power radio transceivers in large-scale wireless sensor networks (WSNs). This fact, together with the harsh characteristics of the physical environment, requires a rigorous WSN design. Mechanisms for WSN deployment and topology control, MAC and routing, resource and mobility management, greatly depend on reliable link quality estimators (LQEs). This paper describes the RadiaLE framework, which enables the experimental assessment, design and optimization of LQEs. RadiaLE comprises (i) the hardware components of the WSN testbed and (ii) a software tool for setting-up and controlling the experiments, automating link measurements gathering through packets-statistics collection, and analyzing the collected data, allowing for LQEs evaluation. We also propose a methodology that allows (i) to properly set different types of links and different types of traffic, (ii) to collect rich link measurements, and (iii) to validate LQEs using a holistic and unified approach. To demonstrate the validity and usefulness of RadiaLE, we present two case studies: the characterization of low-power links and a comparison between six representative LQEs. We also extend the second study for evaluating the accuracy of the TOSSIM 2 channel model.

F-LQE: a Fuzzy Link Quality Estimator for wireless sensor networks

Radio Link Quality Estimation (LQE) is a fundamental building block for Wireless Sensor Networks, namely for a reliable deployment, resource management and routing. Existing LQEs (e.g. PRR, ETX, Fourbit, and LQI ) are based on a single link property, thus leading to inaccurate estimation. In this paper, we propose F-LQE, that estimates link quality on the basis of four link quality properties: packet delivery, asymmetry, stability, and channel quality. Each of these properties is defined in linguistic terms, the natural language of Fuzzy Logic. The overall quality of the link is specified as a fuzzy rule whose evaluation returns the membership of the link in the fuzzy subset of good links. Values of the membership function are smoothed using EWMA filter to improve stability. An extensive experimental analysis shows that F-LQE outperforms existing estimators.

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.

Static-priority scheduling over wireless networks with multiple broadcast domains

We propose a wireless medium access control (MAC) protocol that provides static-priority scheduling of messages in a guaranteed collision-free manner. Our protocol supports multiple broadcast domains, resolves the wireless hidden terminal problem and allows for parallel transmissions across a mesh network. Arbitration of messages is achieved without the notion of a master coordinating node, global clock synchronization or out-of-band signaling. The protocol relies on bit-dominance similar to what is used in the CAN bus except that in order to operate on a wireless physical layer, nodes are not required to receive incoming bits while transmitting. The use of bit-dominance efficiently allows for a much larger number of priorities than would be possible using existing wireless solutions. A MAC protocol with these properties enables schedulability analysis of sporadic message streams in wireless multihop networks.

Reliability and availability in reconfigurable computing: a basis for a common solution

Dynamically reconfigurable SRAM-based field-programmable gate arrays (FPGAs) enable the implementation of reconfigurable computing systems where several applications may be run simultaneously, sharing the available resources according to their own immediate functional requirements. To exclude malfunctioning due to faulty elements, the reliability of all FPGA resources must be guaranteed. Since resource allocation takes place asynchronously, an online structural test scheme is the only way of ensuring reliable system operation. On the other hand, this test scheme should not disturb the operation of the circuit, otherwise availability would be compromised. System performance is also influenced by the efficiency of the management strategies that must be able to dynamically allocate enough resources when requested by each application. As those resources are allocated and later released, many small free resource blocks are created, which are left unused due to performance and routing restrictions. To avoid wasting logic resources, the FPGA logic space must be defragmented regularly. This paper presents a non-intrusive active replication procedure that supports the proposed test methodology and the implementation of defragmentation strategies, assuring both the availability of resources and their perfect working condition, without disturbing system operation.

Ferramenta de gestão de redes MESH

Mestrado em Engenharia Electrotécnica e de Computadores - Área de Especialização de Telecomunicações

Otimização da atividade de picking num armazém de peças – um caso de estudo

Mestrado em Engenharia Mecânica – Gestão Industrial

Uso do QR no marketing digital: a perspetiva do utilizador português

Dissertação de Mestrado apresentada ao Instituto de Contabilidade e Administração do Porto para a obtenção do grau de Mestre em Marketing Digital, sob orientação de Doutor José Freitas Santos

Sectorization: measures and an electromagnetism based approach

Sectorization means dividing a set of basic units into sectors or parts, a procedure that occurs in several contexts, such as political, health and school districting, social networks and sales territory or airspace assignment, to achieve some goal or to facilitate an activity. This presentation will focus on three main issues: Measures, a new approach to sectorization problems and an application in waste collection. When designing or comparing sectors different characteristics are usually taken into account. Some are commonly used, and they are related to the concepts of contiguity, equilibrium and compactness. These fundamental characteristics will be addressed, by defining new generic measures and by proposing a new measure, desirability, connected with the idea of preference. A new approach to sectorization inspired in Coulomb’s Law, which establishes a relation of force between electrically charged points, will be proposed. A charged point represents a small region with specific characteristics/values creating relations of attraction/repulsion with the others (two by two), proportional to the charges and inversely proportional to their distance. Finally, a real case about sectorization and vehicle routing in solid waste collection will be mentioned.

Electromagnetism based approach to Sector design in Waste Collection

For efficient planning of waste collection routing, large municipalities may be partitioned into convenient sectors. The real case under consideration is the municipality of Monção, in Portugal. Waste collection involves more than 1600 containers over an area of 220 km2 and a population of around 20,000 inhabitants. This is mostly a rural area where the population is distributed in small villages around the 33 boroughs centres (freguesia) that constitute the municipality. In most freguesias, waste collection is usually conducted 3 times a week. However, there are situations in which the same collection is done every day. The case reveals some general and specific characteristics which are not rare, but are not widely addressed in the literature. Furthermore, new methods and models to deal with sectorization and routing are introduced, which can be extended to other applications. Sectorization and routing are tackled following a three-phase approach. The first phase, which is the main concern of the presentation, introduces a new method for sectorization inspired by Electromagnetism and Coulomb’s Law. The matter is not only about territorial division, but also the frequency of waste collection, which is a critical issue in these types of applications. Special characteristics related to the number and type of deposition points were also a motivation for this work. The second phase addresses the routing problems in each sector: new Mixed Capacitated Arc Routing with Limited Multi-Landfills models will be presented. The last phase integrates Sectoring and Routing. Computational results confirm the effectiveness of the entire novel approach.

Amostragem Adaptativa em Redes de Sensores

Uma nova área tecnológica está em crescente desenvolvimento. Esta área, denominada de internet das coisas, surge na necessidade de interligar vários objetos para uma melhoria a nível de serviços ou necessidades por parte dos utilizadores. Esta dissertação concentra-se numa área específica da tecnologia internet das coisas que é a sensorização. Esta rede de sensorização é implementada pelo projeto europeu denominado de Future Cities [1] onde se cria uma infraestrutura de investigação e validação de projetos e serviços inteligentes na cidade do Porto. O trabalho realizado nesta dissertação insere-se numa das plataformas existentes nessa rede de sensorização: a plataforma de sensores ambientais intitulada de UrbanSense. Estes sensores ambientais que estão incorporados em Data Collect Unit (DCU), também denominados por nós, medem variáveis ambientais tais como a temperatura, humidade, ozono e monóxido de carbono. No entanto, os nós têm recursos limitados em termos de energia, processamento e memória. Apesar das grandes evoluções a nível de armazenamento e de processamento, a nível energético, nomeadamente nas baterias, não existe ainda uma evolução tão notável, limitando a sua operacionalidade [2]. Esta tese foca-se, essencialmente, na melhoria do desempenho energético da rede de sensores UrbanSense. A principal contribuição é uma adaptação do protocolo de redes Ad Hoc OLSR (Optimized Link State Routing Protocol) para ser usado por nós alimentados a energia renovável, de forma a aumentar a vida útil dos nós da rede de sensorização. Com esta contribuição é possível obter um maior número de dados durante períodos de tempo mais longos, aproximadamente 10 horas relativamente às 7 horas anteriores, resultando numa maior recolha e envio dos mesmos com uma taxa superior, cerca de 500 KB/s. Existindo deste modo uma aproximação analítica dos vários parâmetros existentes na rede de sensorização. Contudo, o aumento do tempo de vida útil dos nós sensores com recurso à energia renovável, nomeadamente, energia solar, incrementa o seu peso e tamanho que limita a sua mobilidade. Com o referido acréscimo a determinar e a limitar a sua mobilidade exigindo, por isso, um planeamento prévio da sua localização. Numa primeira fase do trabalho analisou-se o consumo da DCU, visto serem estes a base na infraestrutura e comunicando entre si por WiFi ou 3G. Após uma análise dos protocolos de routing com iv suporte para parametrização energética, a escolha recaiu sobre o protocolo OLSR devido à maturidade e compatibilidade com o sistema atual da DCU, pois apesar de existirem outros protocolos, a implementação dos mesmos, não se encontram disponível como software aberto. Para a validação do trabalho realizado na presente dissertação, é realizado um ensaio prévio sem a energia renovável, para permitir caracterização de limitações do sistema. Com este ensaio, tornou-se possível verificar a compatibilidade entre os vários materiais e ajustamento de estratégias. Num segundo teste de validação é concretizado um ensaio real do sistema com 4 nós a comunicar, usando o protocolo com eficiência energética. O protocolo é avaliado em termos de aumento do tempo de vida útil do nó e da taxa de transferência. O desenvolvimento da análise e da adaptação do protocolo de rede Ad Hoc oferece uma maior longevidade em termos de tempo de vida útil, comparando ao que existe durante o processamento de envio de dados. Apesar do tempo de longevidade ser inferior, quando o parâmetro energético se encontra por omissão com o fator 3, a realização da adaptação do sistema conforme a energia, oferece uma taxa de transferência maior num período mais longo. Este é um fator favorável para a abertura de novos serviços de envio de dados em tempo real ou envio de ficheiros com um tamanho mais elevado.

Scalable and interference aware wi-fi mesh networks using cots devices

A crescente tendencia no acesso móvel tem sido potenciada pela tecnologia IEEE 802.11. Contudo, estas redes têm alcance rádio limitado. Para a extensão da sua cobertura é possível recorrer a redes emalhadas sem fios baseadas na tecnologia IEEE 802.11, com vantagem do ponto de vista do custo e da flexibilidade de instalação, face a soluções cabladas. Redes emalhadas sem fios constituídas por nós com apenas uma interface têm escalabilidade reduzida. A principal razão dessa limitação deve-se ao uso do mecanismo de acesso ao meio partilhado Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) em topologias multi-hop. Especificamente, o CSMA/CA não evita o problema do nó escondido levando ao aumento do número de colisões e correspondente degradação de desempenho com impacto direto no throughput e na latência. Com a redução da tecnologia rádio torna-se viável a utilização de múltiplos rádios por nó, sem com isso aumentar significativamente o custo da solução final de comunicações. A utilização de mais do que um rádio por nó de comuniações permite superar os problemas de desempenho inerentes ás redes formadas por nós com apenas um rádio. O objetivo desta tese, passa por desenvolver uma nova solução para redes emalhadas multi-cana, duar-radio, utilizando para isso novos mecanismos que complementam os mecanismos definidos no IEEE 802.11 para o estabelecimento de um Basic Service Set (BSS). A solução é baseada na solução WiFIX, um protocolo de routing para redes emalhadas de interface única e reutiliza os mecanismos já implementados nas redes IEEE 802.11 para difundir métricas que permitam à rede escalar de forma eficaz minimizando o impacto na performance. A rede multi-hop é formada por nós equipados com duas interfaces, organizados numa topologia hierárquica sobre múltiplas relações Access Point (AP) – Station (STA). Os resultados experimentais obtidos mostram a eficácia e o bom desempenho da solução proposta face à solução WiFIX original.