Efficient implementation of a dominance protocol for wireless medium access

Mestrado em Engenharia Electrotécnica e de Computadores

A abordagem global do Fisioterapeuta na dor pélvica no pós-parto

O presente estudo de caso surge no âmbito da prática clínica privada, na área de intervenção da fisioterapia na saúde da mulher, em particular na intervenção multifactorial em sequelas após parto. Iremos descrever e analisar o processo da fisioterapia aplicado a uma mulher de 34 anos com dor lombar/pélvica a qual teve início três semanas após o parto do seu terceiro filho. Este sintoma considerado como principal, que levou à procura dos cuidados de fisioterapia, além das implicações ao nível da estrutura e função, tinha um grande impacto no desempenho de actividades, pela dificuldade em realizar movimentos livremente, especificamente passar da posição de sentado para de pé e na marcha. O impacto na participação social era também considerável, em particular na capacidade de prestar os cuidados necessários ao seu bebé. Além desta queixa, a utente apresentava ainda dor ao nível da zona do períneo, perdas de urina sempre que tosse e dificuldades na amamentação. Todos os problemas referidos pela utente, são muito frequentes nas mulheres após o parto, tendo estes tendencialmente uma resolução natural nas duas a três primeiras semanas, pelo que, a maioria das mulheres não recorre a ajuda para os resolver. No entanto, existe uma percentagem que os estudos nos apontam entre os 16% e os 7% que mantêm a dor lombar/pélvica até às 23 semanas dor essa que como no caso presente, pode ser muito incapacitante, sendo estas as situaçõesque mais poderão beneficiar do apoio da fisioterapia na resolução das suas queixas. Sendo que, a dor lombar e pélvica são um dos grandes problemas de saúde, responsável pela maior fatia do absentismo e pela grande procura de consultas médicas constituindo-se pois como um problema socioeconómico em toda a Europa, para a população em geral. A dor lombar baixa (DLB) ou lombalgia afecta principalmente a população activa e está sempre associada a custos elevados em saúde, absentismo e incapacidade apesar de todos os esforços que têm vindo a ser desenvolvidos no sentido da sua prevenção. A DLB é geralmente definida como sendo uma dor situada entre a 12ª costela e a prega glútea. A dor na cintura pélvica (DCP), muitas vezes confundida por lombalgia é uma queixa mais comum e incapacitante do que a lombalgia tanto na gravidez como no período após o parto (Hofmeyr; Abdel-Aleem & Abdel-Aleem, 2008). O risco de vir a ter dor lombar ou pélvica na gravidez ou após o parto é maior nas mulheres com queixas de dor lombar/pélvica prévia.Cerca de 10% das mulheres reportam a sua história de dores lombares ao período da gravidez ou após o parto. Os desequilíbrios musculares provocados pela gravidez, devido ao aumento do peso feto ao longo dos nove meses e ás alterações hormonais mantêm-se no puerpério dando muitas vezes lugar a quadros de dor e incapacidade na zona da cintura pélvica e lombar (Mens, 1996)Neste contexto o fisioterapeuta terá de actuar na prevenção do aparecimento das queixas e no caso de estas existirem tratá-las e prevenir desde logo as recorrências. Na última década tem havido um grande esforço tanto da parte dos clínicos como dos investigadores no sentido de estudar não só a dor mas a etiologia da DCP. Tanto a definição como a nomenclatura nesta área eram confusas surgindo a necessidade de se criar um grupo de trabalho. Dentro da COST ACTION B13 constituída para elaborar o“European Guidelines for the Management of Low Back Pain “ em 2006 (van Tulder; Becker; Bekkering; Breen; del Real; Hutchinson; Koes; Laerum & Malmivaara, 2006) surge o “Working Group 4” (WG4) nome dado ao grupo de trabalho constituído para elaborar os “European Guidelines for the Diagnosis and Treatment of Pelvic Girdle Pain” (Ronchetti; Vleeming & van Wingerden, 2008), guidelines da dor pélvica. O principal objectivo destes guidelines passa pela proposta de um conjunto de recomendações que possam suportar futuros guidelines nacionais e internacionais sobre a DCP. Deverão ainda ajudar na prevenção de complicações a longo prazo, redução da dor e diminuição das incapacidades .O âmbito deste guideline em particular é promover uma abordagem realística com o intuito de melhorar o diagnóstico e tratamento da DCP através de: Recomendações sobre o diagnóstico e actuação clínica na DCP; Abordagem baseada na evidência dada pelos guidelines clínicos existentes; Recomendações aceites por todas as profissões de saúde dos países participantes; Facilitar uma abordagem multidisciplinar; estimulando a colaboração e uma aproximação consistente entre os profissionais de saúde. Segundo a WG4 a Dor na Cintura Pélvica (DCP) é definida por uma dor sentida entre a crista iliaca posterior e a prega glútea, localizando-se com especial incidência na zona da articulação sacro ilíaca (SI) podendo irradiar para a parte posterior da coxa e surgir simultaneamente/ou separadamente, dor na sínfise púbica: A capacidade para andar, estar de pé e sentada;está geralmente diminuída. Esta condição surge geralmente relacionada com a gravidez, trauma ou artrite. O diagnóstico da DCP é feito: Após se ter excluído o diagnóstico de DLB; Quando a dor ou alterações funcionais referentes à dor pélvica podem ser reproduzidas por testes clínicos específicos. A causa da DCP é multifactorial e pode estar relacionada com diferentes condições, gravidez, pós parto, espondilite anquilosante ou trauma. Na maioria dos casos não existe nenhuma explicação óbvia para o aparecimento da DCP, contudo durante a gravidez o corpo da mulher está exposto a determinados factores que têm impacto na estabilidade e dinâmica da cintura pélvica. Um destes factores é a hormona relaxina que em combinação com outras hormonas provoca laxidão dos ligamentos da cintura pélvica assim como de todas as outras estruturas ligamentares. De acordo com os estudos de Albert et al. (2002) o ponto de prevalência de mulheres que sofrem de DCP durante a gravidez é próximo dos 20% sendo forte a evidência no que respeita a este valor. É difícil comparar os estudos existentes na literatura porque a DCP é muitas vezes incluída na dor lombar. Contudo, naqueles em que a DCP é definida e estudada separadamente, o que se encontra é similar e aceitável. Depois da gravidez a prevalência da DCP rapidamente baixa para 7% nos três primeiros meses (Petersen; Olsen; Laslett; Thorsen; Manniche; Ekdahl & Jacobsen, 2004); (Albert; Godskesen & Westergaard, 2001) A percentagem de mulheres que sofrem de dor severa depois da gravidez era 3, 3,2,2,1 e 1% respectivamente 1,3,6,12,18 e 24 meses depois do parto (Albert et al., 2001). As mulheres que apresentavam DCP persistente depois do parto muitas vezes também tinham queixas de dor severa durante a gravidez., 21% das mulheres com queixas de dor severa durante a gravidez ainda apresentavam DCP com teste provocatórios de dor positivo dois anos após o parto (Albert et al., 2001). No estudo de (Ostgaard & Andersson) 5% das mulheres apresentavam dor severa depois da gravidez, e nos seus estudos (Ostgaard; Roos-Hansson & Zetherstrom); (Ostgaard; Zetherstrom & Roos-Hansson) o ponto de prevalência no follow up no período do pós parto á 11ª e 23ª semana, foi respectivamente de 16 e 7%. Estes números são relativos a uma população não tratada. Os principais factores de risco da DCP durante a gravidez são: uma história anterior de dor lombar; trauma prévio da pélvis (Mens et al 1996). Há uma ligeira evidência conflituosa (um estudo somente) que considera factor de risco a multiparidade e uma actividade laboral com elevadas cargas . Há acordo em que não são factores de risco: pilula anticoncepcional, o intervalo de tempo entre gravidezes, altura, peso, fumar e a idade. Uma revisão da literatura que teve como base a “European Guidelines for the Diagnosis and Treatment of pelvic girdle pain” (Vleeming et al 2008) revela que foram usados uma variedade de exames, procedimentos e testes para investigar doentes grávidas ou não. Nos estudos em que foram descritos os procedimentos dos exames são usados uma combinação de métodos: inspecção da marcha; postura e inclinação da bacia; palpação de ligamentos e músculos; teste para a sacro-ilíaca (SI) bloqueada; testes de provocação de dor para a SI e sínfise púbica. Os primeiros estudos focam-se mais na inspecção e palpação enquanto que os mais recentes incidem mais nos teste de provocação de dor, provavelmente devido a uma fidedignidade e especificidade maior. Os testes de provocação de dor mais fidedignos e mais usados para a dor na SI são o teste Thigh trust e o teste de Patrick´s Faber. Para a dor a nível da sínfise púbica o teste mais usado é a palpação da síinfise e o teste de Trendlenbourgh modificado usado como um teste de provocação de dor. A fim de se efectuar o diagnóstico da DCP são recomendados pela “European Guidelines for the diagnosis and treatment of pelvic girdle pain” que conste do exame clínico os testes de provocação de dor pélvica posterior, o Gaenslen´s sign, o teste de Patrick, o teste da compressão e o teste da distracção. De acordo com estas guidelines recomenda-se: Exercícios individualizados na gravidez; Um programa individualizado que deve incidir especialmente em exercícios de estabilização no intuito de melhorar o controlo e a estabilidade integrados num tratamento multifactorial adequado ao pós-parto; Medicação para alívio da dor se necessário à excepção das grávidas que só poderão tomar o paracetamol. O fisioterapeuta é o profissional com mais competências para intervir junto a utentes com problemas do foro músculo-esquelético. Para a sua resolução, o fisioterapeuta dispõe de várias formas de abordagem, como seja o método de McKenzie. O método de Mckenzie preconiza uma abordagem, um diagnóstico mecânico feito com base na resposta do doente a movimentos repetidos, a posições ou e actividades. Segundo Robin Mckenzie, o diagnóstico diferencial deve ser feito com o intuito de excluir qualquer patologia séria ou que, não seja adequada a um tipo de terapia mecânica. Ao fazer o seu diagnóstico o terapeuta deve restringir-se às lesões de origem músculo-esqueléticas. Quando o fisioterapeuta se especializa nesta área, o seu diagnóstico mecânico é de longe mais correcto,(Donelson, 1997) (Donelson; Aprill; Medcalf & Grant) do que aquele que é feito pela maioria dos profissionais médicos conseguindo, com fidelidade, afirmar se a dor tem origem discal ou não. No estudo de (Donelson, 1997) (Machado, 2006) foi avaliada a relação entre as respostas do fenómeno da centralização e periferialização da dor com dados discográficos, tendo concluído que o processo da avaliação ,segundo o método de Mckenzie, é seguro na distinção da dor de origem discogénica da não discogénica (P < 0.001) assim como é competente para um annulus incompetente (P < 0.042) em discos sintomáticos e é superior á imagem por ressonância magnética na distinção (P < 0.042) dor de discos “trincados” de discos não dolorosos. Noutros estudos como o de Hefford (2008) que se propôs a desenvolver o perfil do uso das classificações de diagnóstico e tratamento de Mckenzie por fisioterapeutas. credenciados no método de Mckenzie na Nova Zelândia, veio confirmar o que estudos anteriores já tinham feito dando validade externa ao método de Mckenzie, e suportando a avaliação mecânica de doentes da coluna de acordo com a preferência direccional. No estudo de (Machado, 2010) procurou-se avaliar qual o efeito a curto prazo de adicionar o Método de Mckenzie a cuidados de primeira linha em doentes com dor lombar aguda. Tendo concluído que o programa de tratamento baseado no método de Mckenzie e quando adicionado aos cuidados correntemente usados na dor lombar não produz melhoramentos apreciáveis adicionais a curto prazo no que respeita à dor, incapacidade, função ou num efeito global perceptível. No entanto, o método de Mckenzie parece reduzir a utilização dos serviços de saúde embora, não reduza o risco de o doente desenvolver sintomas persistentes. Noutro estudo o mesmo autor (Machado, 2006) mostra-nos que o método é mais efectivo do que a terapia passiva no tratamento da dor lombar aguda mas a magnitude da diferença diz que a evidência da utilização do método para a dor lombar crónica é limitada. Existem outros métodos que constituem alternativas eficazes para o tratamento da dor lombar e pélvica entre elas a Reeducação Postural Global (RPG). Este método de terapia física foi desenvolvido em França pelo fisioterapeuta Philippe Souchard. A sua abordagem terapêutica baseia-se numa ideia integrada do sistema muscular formado por cadeias musculares, que podem encurtar como resposta a factores de ordem constitucional, psicológicos ou comportamental. O objectivo do RPG é alongar os músculos encurtados usando a propriedade do “creep” típica dos tecidos visco elásticos e reforçar a contracção dos músculos antagonistas, evitando assim assimetrias posturais. Embora este método esteja implantado em muitos países de língua romana existem poucos estudos a suportar a sua eficácia clínica e base teórica Começam no entanto a surgir alguns estudos a comprovar a sua eficácia como o de (Bonetti, #1535;Bonetti, 2010) cujo objectivo foi comparar a curto e médio prazo dois grupos de utentes com dor lombar persistente e avaliar a eficácia de um programa de tratamento de RPG com um programa de exercícios de estabilização. Neste estudo o RPG é sugerido como uma forma mais eficaz de melhorar a dor e diminuir a incapacidade em doentes com dor lombar persistente do que, o programa de exercícios de estabilização, resultados estes que necessitam de ser confirmados com estudos de níveis mais elevados de standards metodológicos, incluindo uma melhor aleatorização, uma amostra maior e um maior follow up. O RPG constitui também uma possível abordagem à incontinência urinária (Fozzatti; Herrmann; Palma; Riccetto & Palma, 2010) tendo em alguns estudos como o de Fozatti surgido como uma alternativa ou um complemento ao fortalecimento dosMPP. Neste estudo foram constituídos dois grupos onde um seguiu um programa de fortalecimento dos MPP e outro um programa de RPG, em ambos os grupos houve melhoria tanto a nível do diário de micção durante três dias, como da avaliação funcional dos MPP e do King´s Health Questionnaire sendo sugerido que o RPG poderá ser uma alternativa ao fortalecimento dos MPP.

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.

Disseminating data using broadcast when topology is unknown

Consider the problem of disseminating data from an arbitrary source node to all other nodes in a distributed computer system, like Wireless Sensor Networks (WSNs). We assume that wireless broadcast is used and nodes do not know the topology. We propose new protocols which disseminate data faster and use fewer broadcasts than the simple broadcast protocol.

Static-priority scheduling of sporadic messages on a wireless channel

Consider the problem of scheduling sporadic messages with deadlines on a wireless channel. We propose a collision-free medium access control (MAC) protocol which implements static-priority scheduling and present a schedulability analysis technique for the protocol. 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 receive an incoming bit from the channel while transmitting to the channel.

Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors

A preliminary version of this paper appeared in Proceedings of the 31st IEEE Real-Time Systems Symposium, 2010, pp. 239–248.

Response time analysis of slotted WiDom in noisy wireless channels

WiDom is a wireless prioritized medium access control protocol which offers very large number of priority levels. Hence, it brings the potential to employ non-preemptive static-priority scheduling and schedulability analysis for a wireless channel assuming that the overhead of WiDom is modeled properly. Recent research has created a new version of WiDom (we call it: Slotted WiDom) which offers lower overhead compared to the previous version. In this paper we propose a new schedulability analysis for slotted WiDom and extend it to work for message streams with release jitter. Furthermore, to provide an accurate timing analysis, we must include the effect of transmission faults on message latencies. Thus, in the proposed analysis we consider the existence of different noise sources and develop the analysis for the case where messages are transmitted under noisy wireless channels. Evaluation of the proposed analysis is done by testing the slotted WiDom in two different modes on a real test-bed. The results from the experiments provide a firm validation on our findings.

Task assignment algorithms for two-type heterogeneous multiprocessors

Consider the problem of assigning real-time 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 linearithmic timecomplexity algorithms, SA and SA-P, each providing the follow- ing guarantee. For a given two-type platform and a given task set, if there exists a feasible task-to-processor-type assignment such that tasks can be scheduled to meet deadlines by allowing them to migrate only between processors of the same type, then (i) using SA, it is guaranteed to find such a feasible task-to- processor-type 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 2 a feasible task-to-processor assignment where tasks are not allowed to migrate between processors but given a platform in which processors are 1+α/times faster, where 0<α≤1. The parameter α is a property of the task set — it is the maximum utilization of any task which is less than or equal to 1.

Makespan computation for GPU threads running on a single streaming multiprocessor

Graphics processors were originally developed for rendering graphics but have recently evolved towards being an architecture for general-purpose computations. They are also expected to become important parts of embedded systems hardware -- not just for graphics. However, this necessitates the development of appropriate timing analysis techniques which would be required because techniques developed for CPU scheduling are not applicable. The reason is that we are not interested in how long it takes for any given GPU thread to complete, but rather how long it takes for all of them to complete. We therefore develop a simple method for finding an upper bound on the makespan of a group of GPU threads executing the same program and competing for the resources of a single streaming multiprocessor (whose architecture is based on NVIDIA Fermi, with some simplifying assunptions). We then build upon this method to formulate the derivation of the exact worst-case makespan (and corresponding schedule) as an optimization problem. Addressing the issue of tractability, we also present a technique for efficiently computing a safe estimate of the worstcase makespan with minimal pessimism, which may be used when finding an exact value would take too long.

Using a prioritized medium access control protocol for incrementally obtaining an interpolation of sensor readings

This paper addresses sensor network applications which need to obtain an accurate image of physical phenomena and do so with a high sampling rate in both time and space. We present a fast and scalable approach for obtaining an approximate representation of all sensor readings at high sampling rate for quickly reacting to critical events in a physical environment. This approach is an improvement on previous work in that after the new approach has undergone a startup phase then the new approach can use a very small sampling period.

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound

Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound. A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected. We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.

Real-time scheduling with resource sharing on uniform multiprocessors

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on uniform multiprocessors with proven performance guarantee.

Scalable data acquisition for densely instrumented cyber-physical systems

Consider the problem of designing an algorithm for acquiring sensor readings. Consider specifically the problem of obtaining an approximate representation of sensor readings where (i) sensor readings originate from different sensor nodes, (ii) the number of sensor nodes is very large, (iii) all sensor nodes are deployed in a small area (dense network) and (iv) all sensor nodes communicate over a communication medium where at most one node can transmit at a time (a single broadcast domain). We present an efficient algorithm for this problem, and our novel algorithm has two desired properties: (i) it obtains an interpolation based on all sensor readings and (ii) it is scalable, that is, its time-complexity is independent of the number of sensor nodes. Achieving these two properties is possible thanks to the close interlinking of the information processing algorithm, the communication system and a model of the physical world.

A preliminary idea for an 8-competitive, log2 DMAX + log2 log2 1/U asymptotic-space, interface generation algorithm for two-level hierarchical scheduling of constrained-deadline sporadic tasks on a uniprocessor

Consider a single processor and a software system. The software system comprises components and interfaces where each component has an associated interface and each component comprises a set of constrained-deadline sporadic tasks. A scheduling algorithm (called global scheduler) determines at each instant which component is active. The active component uses another scheduling algorithm (called local scheduler) to determine which task is selected for execution on the processor. The interface of a component makes certain information about a component visible to other components; the interfaces of all components are used for schedulability analysis. We address the problem of generating an interface for a component based on the tasks inside the component. We desire to (i) incur only a small loss in schedulability analysis due to the interface and (ii) ensure that the amount of space (counted in bits) of the interface is small; this is because such an interface hides as much details of the component as possible. We present an algorithm for generating such an interface.

Provably good scheduling of sporadic tasks with resource sharing on a two-type heterogeneous multiprocessor platform

Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a two-type heterogeneous multiprocessor platform where a task may request at most one of |R| shared resources. There are m1 processors of type-1 and m2 processors of type-2. Tasks may migrate only when requesting or releasing resources. We present a new algorithm, FF-3C-vpr, which offers a guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that only allows tasks to migrate when requesting or releasing a resource, then FF-3Cvpr also meets deadlines if given processors 4+6*ceil(|R|/min(m1,m2)) times as fast. As far as we know, it is the first result for resource sharing on heterogeneous platforms with provable performance.