Analysing TDMA with slot skipping

We propose a schedulability analysis for a particular class of time division multiple access (TDMA) networks, which we label as TDMA/SS. SS stands for slot skipping, reflecting the fact that a slot is skipped whenever it is not used. Hence, the next slot can start earlier in benefit of hard real-time traffic. In the proposed schedulability analysis, we assume knowledge of all message streams in the system, and that each node schedules messages in its output queue according to a rate monotonic policy (as an example). We present the analysis in two steps. Firstly, we address the case where a node is only permitted to transmit a maximum of one message per TDMA cycle. Secondly, we generalise the analysis to the case where a node is assigned a budget of messages per TDMA cycle it may transmit. A simple algorithm to assign budgets to nodes is also presented.

Analyzing TDMA with slot skipping

Distributed real-time systems, such as factory automation systems, require that computer nodes communicate with a known and low bound on the communication delay. This can be achieved with traditional time division multiple access (TDMA). But improved flexibility and simpler upgrades are possible through the use of TDMA with slot-skipping (TDMA/SS), meaning that a slot is skipped whenever it is not used and consequently the slot after the skipped slot starts earlier. We propose a schedulability analysis for TDMA/SS. We assume knowledge of all message streams in the system, and that each node schedules messages in its output queue according to deadline monotonic. Firstly, we present a non-exact (but fast) analysis and then, at the cost of computation time, we also present an algorithm that computes exact queuing times.

Exact analysis of TDMA with slot skipping

Consider a communication medium shared among a set of computer nodes; these computer nodes issue messages that are requested to be transmitted and they must finish their transmission before their respective deadlines. TDMA/SS is a protocol that solves this problem; it is a specific type of Time Division Multiple Access (TDMA) where a computer node is allowed to skip its time slot and then this time slot can be used by another computer node. We present an algorithm that computes exact queuing times for TDMA/SS in conjunction with Rate-Monotonic (RM) or Earliest- Deadline-First (EDF).

TDBS: a time division beacon scheduling mechanism for ZigBee cluster-tree wireless sensor networks

Synchronization is a challenging and important issue for time-sensitive Wireless Sensor Networks (WSN) since it requires a mutual spatiotemporal coordination between the nodes. In that concern, the IEEE 802.15.4/ZigBee protocols embody promising technologies for WSNs, but are still ambiguous on how to efficiently build synchronized multiple-cluster networks, specifically for the case of cluster-tree topologies. In fact, the current IEEE 802.15.4/ZigBee specifications restrict the synchronization to beacon-enabled (by the generation of periodic beacon frames) star networks, while they support multi-hop networking in mesh topologies, 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 issue by unveiling the ambiguities regarding the use of the cluster-tree topology and proposing a synchronization mechanism based on Time Division Beacon Scheduling (TDBS) to build cluster-tree WSNs. In addition, we propose a methodology for efficiently managing duty-cycles in every cluster, ensuring the fairest use of bandwidth resources. The feasibility of the TDBS mechanism is clearly demonstrated through an experimental test-bed based on our open-source implementation of the IEEE 802.15.4/ZigBee protocols.

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.

Implementation details of the time division beacon scheduling approach for ZigBee cluster-tree networks

This technical report describes the implementation details of the Time Division Beacon Scheduling Approach in IEEE 802.15.4/ZigBee Cluster-Tree Networks. In this technical report we describe the implementation details, focusing on some aspects of the ZigBee Network Layer and the Time Division Beacon Scheduling mechanism. This report demonstrates the feasibility of our approach based on the evaluation of the experimental results. We also present an overview of the ZigBee address and tree-routing scheme.

Multi-Objective and Financial Portfolio Optimization of Carrier-Sense Multiple Access Protocols with Cooperative Diversity

8th International Workshop on Multiple Access Communications (MACOM2015), Helsinki, Finland.

On the use of IEEE 802.15.4/Zigbee for time-sensitive wireless sensor network applications

Mestrado em Engenharia Electrotécnica e de Computadores

Energy efficient scheduling for cluster-tree wireless sensor networks with time-bounded data flows: application to IEEE 802.15.4/ZigBee

Cluster scheduling and collision avoidance are crucial issues in large-scale cluster-tree Wireless Sensor Networks (WSNs). The paper presents a methodology that provides a Time Division Cluster Scheduling (TDCS) mechanism based on the cyclic extension of RCPS/TC (Resource Constrained Project Scheduling with Temporal Constraints) problem for a cluster-tree WSN, assuming bounded communication errors. The objective is to meet all end-to-end deadlines of a predefined set of time-bounded data flows while minimizing the energy consumption of the nodes by setting the TDCS period as long as possible. Sinceeach cluster is active only once during the period, the end-to-end delay of a given flow may span over several periods when there are the flows with opposite direction. The scheduling tool enables system designers to efficiently configure all required parameters of the IEEE 802.15.4/ZigBee beaconenabled cluster-tree WSNs in the network design time. The performance evaluation of thescheduling tool shows that the problems with dozens of nodes can be solved while using optimal solvers.

A Random Access Protocol incorporating Multi-Packet Reception, Retransmission Diversity and Successive Interference Cancellation

8th International Workshop on Multiple Access Communications (MACOM2015), Helsinki, Finland.

Simulation study of energy efficient scheduling for IEEE 802.15.4/ZigBee cluster-treeWireless Sensor Networks with time-bounded data flows

The simulation analysis is important approach to developing and evaluating the systems in terms of development time and cost. This paper demonstrates the application of Time Division Cluster Scheduling (TDCS) tool for the configuration of IEEE 802.15.4/ZigBee beaconenabled cluster-tree WSNs using the simulation analysis, as an illustrative example that confirms the practical applicability of the tool. The simulation study analyses how the number of retransmissions impacts the reliability of data transmission, the energy consumption of the nodes and the end-to-end communication delay, based on the simulation model that was implemented in the Opnet Modeler. The configuration parameters of the network are obtained directly from the TDCS tool. The simulation results show that the number of retransmissions impacts the reliability, the energy consumption and the end-to-end delay, in a way that improving the one may degrade the others.

On-line defragmentation for run-time partially reconfigurable FPGAs

Dynamically reconfigurable systems have benefited from a new class of FPGAs recently introduced into the market, which allow partial and dynamic reconfiguration at run-time, enabling multiple independent functions from different applications to share the same device, swapping resources as needed. When the sequence of tasks to be performed is not predictable, resource allocation decisions have to be made on-line, fragmenting the FPGA logic space. A rearrangement may be necessary to get enough contiguous space to efficiently implement incoming functions, to avoid spreading their components and, as a result, degrading their performance. This paper presents a novel active replication mechanism for configurable logic blocks (CLBs), able to implement on-line rearrangements, defragmenting the available FPGA resources without disturbing those functions that are currently running.

Collaborative learning in a qeb-accessible workbench

Web-based course management and delivery is regarded by many institutions as a key factor in an increasingly competitive education and training world, but the systems currently available are largely unsatisfactory in terms of supporting collaborative work and access to practical science facilities. These limitations are less important in areas where “pen-and-paper” courseware is the mainstream, but become unacceptably restrictive when student assignments require real-time teamwork and access to laboratory equipment. This paper presents a web-accessible workbench for electronics design and test, which was developed in the scope of an European IST project entitled PEARL, with the aim of supporting two main features: full web access and collaborative learning facilities.

RealCrono –sistema de difusão de resultados em tempo real na web

A velocidade de difusão de conteúdos numa plataforma web, assume uma elevada relevância em serviços onde a informação se pretende atualizada e em tempo real. Este projeto de Mestrado, apresenta uma abordagem de um sistema distribuído de recolher e difundir resultados em tempo real entre várias plataformas, nomeadamente sistemas móveis. Neste contexto, tempo real entende-se como uma diferença de tempo nula entre a recolha e difusão, ignorando fatores que não podem ser controlados pelo sistema, como latência de comunicação e tempo de processamento. Este projeto tem como base uma arquitetura existente de processamento e publicação de resultados desportivos, que apresentava alguns problemas relacionados com escalabilidade, segurança, tempos de entrega de resultados longos e sem integração com outras plataformas. Ao longo deste trabalho procurou-se investigar fatores que condicionassem a escalabilidade de uma aplicação web dando ênfase à implementação de uma solução baseada em replicação e escalabilidade horizontal. Procurou-se também apresentar uma solução de interoperabilidade entre sistemas e plataformas heterogêneas, mantendo sempre elevados níveis de performance e promovendo a introdução de plataformas móveis no sistema. De várias abordagens existentes para comunicação em tempo real sobre uma plataforma web, adotou-se um implementação baseada em WebSocket que elimina o tempo desperdiçado entre a recolha de informação e sua difusão. Neste projeto é descrito o processo de implementação da API de recolha de dados (Collector), da biblioteca de comunicação com o Collector, da aplicação web (Publisher) e sua API, da biblioteca de comunicação com o Publisher e por fim a implementação da aplicação móvel multi-plataforma. Com os componentes criados, avaliaram-se os resultados obtidos com a nova arquitetura de forma a aferir a escalabilidade e performance da solução criada e sua adaptação ao sistema existente.

A framework for memory contention analysis in multi-core platforms

The last decade has witnessed a major shift towards the deployment of embedded applications on multi-core platforms. However, real-time applications have not been able to fully benefit from this transition, as the computational gains offered by multi-cores are often offset by performance degradation due to shared resources, such as main memory. To efficiently use multi-core platforms for real-time systems, it is hence essential to tightly bound the interference when accessing shared resources. Although there has been much recent work in this area, a remaining key problem is to address the diversity of memory arbiters in the analysis to make it applicable to a wide range of systems. This work handles diverse arbiters by proposing a general framework to compute the maximum interference caused by the shared memory bus and its impact on the execution time of the tasks running on the cores, considering different bus arbiters. Our novel approach clearly demarcates the arbiter-dependent and independent stages in the analysis of these upper bounds. The arbiter-dependent phase takes the arbiter and the task memory-traffic pattern as inputs and produces a model of the availability of the bus to a given task. Then, based on the availability of the bus, the arbiter-independent phase determines the worst-case request-release scenario that maximizes the interference experienced by the tasks due to the contention for the bus. We show that the framework addresses the diversity problem by applying it to a memory bus shared by a fixed-priority arbiter, a time-division multiplexing (TDM) arbiter, and an unspecified work-conserving arbiter using applications from the MediaBench test suite. We also experimentally evaluate the quality of the analysis by comparison with a state-of-the-art TDM analysis approach and consistently showing a considerable reduction in maximum interference.