Collision-free prioritized medium access in the presence of hidden nodes without relying on out-of-band signaling

Consider the problem of sharing a wireless channel between a set of computer nodes. Hidden nodes exist and there is no base station. Each computer node hosts a set of sporadic message streams where a message stream releases messages with real-time deadlines. We propose a collision-free wireless medium access control (MAC) protocol which implements staticpriority scheduling. The MAC protocol allows multiple masters and is fully distributed. It neither relies on synchronized clocks nor out-of-band signaling; it is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But unlike that protocol, our protocol does not require a node having the ability to receive an incoming bit from the channel while transmitting to the channel. Our protocol has the key feature of not only being prioritized and collision-free but also dealing successfully with hidden nodes. This key feature enables schedulability analysis of sporadic message streams in multihop networks.

Collision-free prioritized medium access control in wireless networks with hidden nodes

We propose a collision-free medium access control (MAC) protocol, which implements static-priority scheduling and works in the presence of hidden nodes. The MAC protocol allows multiple masters and is fully distributed; it is an adaptation to a wireless channel of the dominance protocol used in the CAN bus. But unlike that protocol, our protocol does not require a node having the ability to sense the channel while transmitting to the channel. Our protocol is collision-free even in the presence of hidden nodes and it achieves this without synchronized clocks or out-of-band busy tones. In addition, the protocol is designed to ensure that many non-interfering nodes can transmit in parallel and it functions for both broadcast and unicast transmissions.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors—such a platform is referred to as two-type platform. We present two low degree polynomial time-complexity algorithms, SA and SA-P, each providing the following guarantee. For a given two-type platform and a task set, if there exists a task assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type (intra-migrative), then (i) using SA, it is guaranteed to find such an assignment where the same restriction on task migration applies but given a platform in which processors are 1+α/2 times faster and (ii) SA-P succeeds in finding a task assignment where tasks are not allowed to migrate between processors (non-migrative) but given a platform in which processors are 1+α times faster. The parameter 0<α≤1 is a property of the task set; it is the maximum of all the task utilizations that are no greater than 1. We evaluate average-case performance of both the algorithms by generating task sets randomly and measuring how much faster processors the algorithms need (which is upper bounded by 1+α/2 for SA and 1+α for SA-P) in order to output a feasible task assignment (intra-migrative for SA and non-migrative for SA-P). In our evaluations, for the vast majority of task sets, these algorithms require significantly smaller processor speedup than indicated by their theoretical bounds. Finally, we consider a special case where no task utilization in the given task set can exceed one and for this case, we (re-)prove the performance guarantees of SA and SA-P. We show, for both of the algorithms, that changing the adversary from intra-migrative to a more powerful one, namely fully-migrative, in which tasks can migrate between processors of any type, does not deteriorate the performance guarantees. For this special case, we compare the average-case performance of SA-P and a state-of-the-art algorithm by generating task sets randomly. In our evaluations, SA-P outperforms the state-of-the-art by requiring much smaller processor speedup and by running orders of magnitude faster.

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set τ of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m k processors of type-k, where k∈{1,2,…,t}. The execution time of a task depends on the type of processor on which it executes. The set of shared resources is denoted by R. For each task τ i , there is a resource set R i ⊆R such that for each job of τ i , during one phase of its execution, the job requests to hold the resource set R i exclusively with the interpretation that (i) the job makes a single request to hold all the resources in the resource set R i and (ii) at all times, when a job of τ i holds R i , no other job holds any resource in R i . Each job of task τ i may request the resource set R i at most once during its execution. A job is allowed to migrate when it requests a resource set and when it releases the resource set but a job is not allowed to migrate at other times. Our goal is to design a scheduling algorithm for this problem and prove its performance. We propose an algorithm, LP-EE-vpr, which offers the guarantee that if an implicit-deadline sporadic task set is schedulable on a t-type heterogeneous multiprocessor platform by an optimal scheduling algorithm that allows a job to migrate only when it requests or releases a resource set, then our algorithm also meets the deadlines with the same restriction on job migration, if given processors 4×(1+MAXP×⌈|P|×MAXPmin{m1,m2,…,mt}⌉) times as fast. (Here MAXP and |P| are computed based on the resource sets that tasks request.) For the special case that each task requests at most one resource, the bound of LP-EE-vpr collapses to 4×(1+⌈|R|min{m1,m2,…,mt}⌉). To the best of our knowledge, LP-EE-vpr is the first algorithm with proven performance guarantee for real-time scheduling of sporadic tasks with resource sharing on t-type heterogeneous multiprocessors.

Response Time Analysis of Slotted WiDOM in Noisy Wireless Channels

International Conference on Emerging Technologies and Factory Automation (ETFA 2015), Industrial Communication Technologies and Systems, Luxembourg, Luxembourg.

Estudo comparativo da resistência à tração de juntas adesivas de sobreposição simples e dupla

O método de união com ligações adesivas está cada vez mais a ser utilizado na conceção de estruturas mecânicas, por causa das vantagens significativas desta técnica em comparação com as ligações tradicionais. De facto, as juntas com ligação adesiva estão sob investigação intensa há bastante tempo. Entre as vantagens, destaca-se a redução de peso e possibilidade de unir diferentes materiais, incluindo compósitos, sem danificar as estruturas a ligar. Os adesivos comerciais variam desde resistentes e frágeis (por exemplo, Araldite® AV138) a menos resistentes e dúcteis (por exemplo, Araldite® 2015). Uma nova família de adesivos de poliuretano combina elevada resistência e ductilidade (por exemplo, Sikaforce® 7888). Este trabalho compara o desempenho à tração dos três adesivos supracitados, em juntas de alumínio (Al6082-T651) de sobreposição simples e dupla, com variação dos valores de comprimento de sobreposição (LO). A análise numérica de modelos de dano coesivo (MDC) foi realizada para analisar as tensões de arrancamento (oy) e as de corte (txy) na camada adesiva, para estudar a variável de dano do MDC durante o processo de rotura e para avaliar a capacidade MDC na previsão da resistência da junta. A análise da resistência e da variável de dano ajudou na compreensão das diferenças entre os adesivos no que se refere ao processo de rotura e resistência da junta. Observou-se que as juntas de sobreposição dupla apresentam uma distribuição de tensões bastante mais favorável relativamente às juntas de sobreposição simples, principalmente devido à eliminação da flexão do substrato interior. Como resultado, a resistência destas juntas foi tipicamente superior ao dobro da observada para as juntas de sobreposição simples, com exceção de algumas configurações de junta em que houve plastificação extensa ou mesmo rotura dos substratos por tração. O trabalho proposto permitiu também concluir que as previsões MDC são tipicamente precisas, e qual a família de adesivos é mais adequada para cada configuração de junta, com a clara vantagem para o Sikaforce® 7888. Como resultado deste trabalho, foram propostas diretrizes de conceção para juntas adesivas.

The importance of physical education classes in pre-school children

The purpose of this study was to analyse differences between total physical activity (TPA) and moderate-to-vigorous PA (MVPA) of pre-school children during daily school hours when they attended the physical education class (PED) and school days without PE class (NPED) and to assess the contribution of PE classes to TPA in school hours. The sample was composed of 193 pre-school healthy children (96 girls) aged from three to five years old and was conducted between February and December of 2008. Children wore accelerometers for at least four consecutive days during school hours. Data were analysed with specific software, age-specific counts-per-minute cut-off points and a 5 s epoch were used. Independent and general linear model repeated measures were used to assess differences between gender and differences between different days within each gender, respectively. Boys engaged more MVPA than girls (P < 0.05). During PED, pre-school children engaged significantly more in TPA and MVPA than during NPED (P < 0.05). PE class contributed, on average, 27.7% for the TPA and 32.8% of daily MVPA during PED in both gender. The results of this study suggest that structured PA such as a PE class increased the daily TPA and MVPA level of pre-school children.