Delay-bounded medium access for unidirectional wireless links

Consider a wireless network where links may be unidirectional, that is, a computer node A can broadcast a message and computer node B will receive this message but if B broadcasts then A will not receive it. Assume that messages have deadlines. We propose a medium access control (MAC) protocol which replicates a message in time with carefully selected pauses between replicas, and in this way it guarantees that for every message at least one replica of that message is transmitted without collision. The protocol ensures this with no knowledge of the network topology and it requires neither synchronized clocks nor carrier sensing capabilities. We believe this result is significant because it is the only MAC protocol that offers an upper bound on the message queuing delay for unidirectional links without relying on synchronized clocks.

Preliminary discussion on globally prioritized medium access for multi-channel wireless systems

We discuss the development of a simple globally prioritized multi-channel medium access control (MAC) protocol for wireless networks. This protocol provides “hard” pre-run-time real-time guarantees to sporadic message streams, exploits a very large fraction of the capacity of all channels for “hard” real-time traffic and also makes it possible to fully utilize the channels with non real-time traffic when hard real-time messages do not request to be transmitted. The potential of such protocols for real-time applications is discussed and a schedulability analysis is also presented.

The utilization bound of uniprocessor preemptive slack-monotonic scheduling is 50%

Consider the problem of scheduling a set of sporadically arriving implicit-deadline tasks to meet deadlines on a uniprocessor. Static-priority scheduling is considered using the slack-monotonic priority-assignment scheme. We prove that its utilization bound is 50%.

Schedulability analysis of generalized multiframe traffic on multihop-networks comprising software-implemented ethernet switches

Consider a multihop network comprising Ethernet switches. The traffic is described with flows and each flow is characterized by its source node, its destination node, its route and parameters in the generalized multiframe model. Output queues on Ethernet switches are scheduled by static-priority scheduling and tasks executing on the processor in an Ethernet switch are scheduled by stride scheduling. We present schedulability analysis for this setting.

Highly scalable aggregate computations in cyber-physical systems: physical environment meets communication protocols

In this paper, we focus on large-scale and dense Cyber- Physical Systems, and discuss methods that tightly integrate communication and computing with the underlying physical environment. We present Physical Dynamic Priority Dominance ((PD)2) protocol that exemplifies a key mechanism to devise low time-complexity communication protocols for large-scale networked sensor systems. We show that using this mechanism, one can compute aggregate quantities such as the maximum or minimum of sensor readings in a time-complexity that is equivalent to essentially one message exchange. We also illustrate the use of this mechanism in a more complex task of computing the interpolation of smooth as well as non-smooth sensor data in very low timecomplexity.

Fazer, dançar, de dentro : a fusão entre os processos do fazer e do sentir na prática diária da Técnica de Dança Clássica

Relatório Final de Estágio apresentado à Escola Superior de Dança com vista à obtenção do Grau de Mestre em Ensino de Dança.

Efficient middleware for database replication

Dissertação de Mestrado em Engenharia Informática

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.

Project scheduling under multiple resources constraints using a genetic algorithm

The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Project scheduling using a competitive genetic algorithm

- The resource constrained project scheduling problem (RCPSP) is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions. This paper proposes a genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities and delay times of the activities are defined by the genetic algorithm. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

Consumo de benzodiazepinas por idosos institucionalizados: inapropriação, qualidade de sono e contributo para a segurança na medicação

A racionalização do uso de medicamentos constitui-se como um fator contribuinte para a melhoria da segurança do doente, particularmente no que respeita à segurança na medicação, tendo-se tornado prioritária para as organizações e instituições de saúde. A avaliação do uso de medicamentos inapropriados no idoso constitui-se como uma medida que concorre para evitar, prevenir ou corrigir eventos adversos associados ao seu uso. As benzodiazepinas são uma das classes de medicamentos mais prescritas em idosos. No entanto, e apesar de sua utilidade clínica, algumas benzodiazepinas são consideradas inapropriadas nesta faixa etária por potenciarem o efeito sedativo e aumentar a incidência de quedas e fraturas. A longo prazo, na promoção da qualidade do sono, a sua efetividade é discutível já que a toma de uma benzodiazepina para a resolução de um problema como o sono, muitas vezes pontual, passa a ser um problema crónico de exigência de toma contínua, sem que a qualidade deste seja restabelecida, pondo em risco a segurança do doente. Este estudo tem como objetivo caracterizar o consumo de benzodiazepinas por idosos institucionalizados, numa instituição de longa permanência do concelho de Sesimbra, sua inapropriação e a relação com a qualidade de sono. Foi desenvolvido um estudo descritivo e transversal, assente no paradigma qualitativo, com a recolha de dados a decorrer em três momentos: registo de informação em grelha própria da caracterização sociodemográfica e da caracterização do consumo de benzodiazepinas; aplicação do índice de Katz para determinar a funcionalidade dos participantes; aplicação do questionário adaptado do Pittsburgh Sleep Quality Index para avaliação da qualidade do sono. A inapropriação foi avaliada pela aplicação dos critérios de Beers. Após aplicação dos critérios de inclusão (idade superior a 65 anos e capacidade funcional) aos 97 utentes da instituição, a amostra foi constituída por 51 utentes. Foi recolhido consentimento informado de todos os participantes. Os resultados obtidos mostram que 46% das benzodiazepinas consumidas são de duração intermédia de ação, observando-se ainda um valor considerável de consumo de benzodiazepinas de longa duração de ação (36%). Estes valores correspondem a um grau elevado de inapropriação, potenciando os riscos para a segurança do doente nesta faixa etária. O lorazepam 2,5mg é a benzodiazepina mais utilizada como hipnótico. Mas, apesar do consumo deste grupo de medicamentos 81,6% dos idosos que consumem benzodiazepinas não apresentam boa qualidade de sono (PSQI>5), enquanto 77% dos idosos que não consomem benzodiazepinas apresentam boa qualidade de sono (PSQI≤5). Nos idosos que consomem benzodiazepinas, a média de tempo despendido na cama até adormecer foi de cerca de 55 minutos, valor superior ao grupo que não consome benzodiazepinas, onde a média é de 27 minutos. Neste grupo de idosos, o consumo de benzodiazepinas não só é inapropriado como não contribuiu para uma melhoria na qualidade de sono nem para a segurança do doente, como são os consumidores de benzodiazepinas que apresentam uma pior qualidade de sono, nas suas várias dimensões.

Spatial analysis of avoidable hospitalizations due to tuberculosis in Ribeirao Preto, SP, Brazil (2006-2012)

ABSTRACT OBJECTIVE To describe the spatial distribution of avoidable hospitalizations due to tuberculosis in the municipality of Ribeirao Preto, SP, Brazil, and to identify spatial and space-time clusters for the risk of occurrence of these events. METHODS This is a descriptive, ecological study that considered the hospitalizations records of the Hospital Information System of residents of Ribeirao Preto, SP, Southeastern Brazil, from 2006 to 2012. Only the cases with recorded addresses were considered for the spatial analyses, and they were also geocoded. We resorted to Kernel density estimation to identify the densest areas, local empirical Bayes rate as the method for smoothing the incidence rates of hospital admissions, and scan statistic for identifying clusters of risk. Softwares ArcGis 10.2, TerraView 4.2.2, and SaTScanTM were used in the analysis. RESULTS We identified 169 hospitalizations due to tuberculosis. Most were of men (n = 134; 79.2%), averagely aged 48 years (SD = 16.2). The predominant clinical form was the pulmonary one, which was confirmed through a microscopic examination of expectorated sputum (n = 66; 39.0%). We geocoded 159 cases (94.0%). We observed a non-random spatial distribution of avoidable hospitalizations due to tuberculosis concentrated in the northern and western regions of the municipality. Through the scan statistic, three spatial clusters for risk of hospitalizations due to tuberculosis were identified, one of them in the northern region of the municipality (relative risk [RR] = 3.4; 95%CI 2.7–4,4); the second in the central region, where there is a prison unit (RR = 28.6; 95%CI 22.4–36.6); and the last one in the southern region, and area of protection for hospitalizations (RR = 0.2; 95%CI 0.2–0.3). We did not identify any space-time clusters. CONCLUSIONS The investigation showed priority areas for the control and surveillance of tuberculosis, as well as the profile of the affected population, which shows important aspects to be considered in terms of management and organization of health care services targeting effectiveness in primary health care.

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.