H-NAMe: a hidden-node avoidance mechanism for wireless sensor networks

The hidden-node problem has been shown to be a major source of Quality-of-Service (QoS) degradation in Wireless Sensor Networks (WSNs) due to factors such as the limited communication range of sensor nodes, link asymmetry and the characteristics of the physical environment. In wireless contention-based Medium Access Control protocols, if two nodes that are not visible to each other transmit to a third node that is visible to the formers, there will be a collision – usually called hidden-node or blind collision. This problem greatly affects network throughput, energy-efficiency and message transfer delays, which might be particularly dramatic in large-scale WSNs. This paper tackles the hiddennode problem in WSNs and proposes H-NAMe, a simple yet efficient distributed mechanism to overcome it. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of non-hidden nodes and then scales to multiple clusters via a cluster grouping strategy that guarantees no transmission interference between overlapping clusters. We also show that the H-NAMe mechanism can be easily applied to the IEEE 802.15.4/ZigBee protocols with only minor add-ons and ensuring backward compatibility with the standard specifications. We demonstrate the feasibility of H-NAMe via an experimental test-bed, showing that it increases network throughput and transmission success probability up to twice the values obtained without H-NAMe. We believe that the results in this paper will be quite useful in efficiently enabling IEEE 802.15.4/ZigBee as a WSN protocol

Scheduling arbitrary-deadline sporadic task systems on multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

IEEE 802.15.4: a Federating Communication Protocol for Time-Sensitive Wireless Sensor Networks

Wireless Sensor Networks (WSNs) have been attracting increasing interests for developing a new generation of embedded systems with great potential for many applications such as surveillance, environment monitoring, emergency medical response and home automation. However, the communication paradigms in WSNs differ from the ones attributed to traditional wireless networks, triggering the need for new communication protocols. In this context, the recently standardised IEEE 802.15.4 protocol presents some potentially interesting features for deployment in wireless sensor network applications, such as power-efficiency, timeliness guarantees and scalability. Nevertheless, when addressing WSN applications with (soft/hard) timing requirements some inherent paradoxes emerge, such as power-efficiency versus timeliness, triggering the need of engineering solutions for an efficient deployment of IEEE 802.15.4 in WSNs. In this technical report, we will explore the most relevant characteristics of the IEEE 802.15.4 protocol for wireless sensor networks and present the most important challenges regarding time-sensitive WSN applications. We also provide some timing performance and analysis of the IEEE 802.15.4 that unveil some directions for resolving the previously mentioned paradoxes.

GTS allocation analysis in IEEE 802.15.4 for real-time wireless sensor networks

The IEEE 802.15.4 protocol proposes a flexible communication solution for Low-Rate Wireless Personal Area Networks including sensor networks. It presents the advantage to fit different requirements of potential applications by adequately setting its parameters. When enabling its beacon mode, the protocol makes possible real-time guarantees by using its Guaranteed Time Slot (GTS) mechanism. This paper analyzes the performance of the GTS allocation mechanism in IEEE 802.15.4. The analysis gives a full understanding of the behavior of the GTS mechanism with regards to delay and throughput metrics. First, we propose two accurate models of service curves for a GTS allocation as a function of the IEEE 802.15.4 parameters. We then evaluate the delay bounds guaranteed by an allocation of a GTS using Network Calculus formalism. Finally, based on the analytic results, we analyze the impact of the IEEE 802.15.4 parameters on the throughput and delay bound guaranteed by a GTS allocation. The results of this work pave the way for an efficient dimensioning of an IEEE 802.15.4 cluster.

Implementation of a dominance protocol for wireless medium access

Consider the problem of scheduling sporadic message transmission requests with deadlines. For wired channels, this has been achieved successfully using the CAN bus. For wireless channels, researchers have recently proposed a similar solution; a collision-free medium access control (MAC) protocol that implements static-priority scheduling. Unfortunately no implementation has been reported, yet. We implement and evaluate it to find that the implementation indeed is collision-free and prioritized. This allows us to develop schedulability analysis for the implementation. We measure the response times of messages in our implementation and find that our new response-time analysis indeed offers an upper bound on the response times. This enables a new class of wireless real-time systems with timeliness guarantees for sporadic messages and it opens-up a new research area: schedulability analysis for wireless networks.

Energy and delay trade-off of the GTS allocation mechanism in IEEE 802.15.4 for wireless sensor networks

The IEEE 802.15.4 protocol proposes a flexible communication solution for Low-Rate Wireless Personal Area Networks (LR-WPAN) including wireless sensor networks (WSNs). It presents the advantage to fit different requirements of potential applications by adequately setting its parameters. When in beaconenabled mode, the protocol can provide timeliness guarantees by using its Guaranteed Time Slot (GTS) mechanism. However, power-efficiency and timeliness guarantees are often two antagonistic requirements in wireless sensor networks. The purpose of this paper is to analyze and propose a methodology for setting the relevant parameters of IEEE 802.15.4-compliant WSNs that takes into account a proper trade-off between power-efficiency and delay bound guarantees. First, we propose two accurate models of service curves for a GTS allocation as a function of the IEEE 802.15.4 parameters, using Network Calculus formalism. We then evaluate the delay bound guaranteed by a GTS allocation and express it as a function of the duty cycle. Based on the relation between the delay requirement and the duty cycle, we propose a power-efficient superframe selection method that simultaneously reduces power consumption and enables meeting the delay requirements of real-time flows allocating GTSs. The results of this work may pave the way for a powerefficient management of the GTS mechanism in an IEEE 802.15.4 cluster.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

A Qualidade na administração pública e a CAF – Common assessment framework

Apresentação no âmbito da Dissertação de Mestrado Orientador: Doutora Alcina Dias

Fast mobility support in low-power wireless networks: smart-HOP over RPL/6LoWPAN

With the emergence of low-power wireless hardware new ways of communication were needed. In order to standardize the communication between these low powered devices the Internet Engineering Task Force (IETF) released the 6LoWPAN stand- ard that acts as an additional layer for making the IPv6 link layer suitable for the lower-power and lossy networks. In the same way, IPv6 Routing Protocol for Low- Power and Lossy Networks (RPL) has been proposed by the IETF Routing Over Low power and Lossy networks (ROLL) Working Group as a standard routing protocol for IPv6 routing in low-power wireless sensor networks. The research performed in this thesis uses these technologies to implement a mobility process. Mobility management is a fundamental yet challenging area in low-power wireless networks. There are applications that require mobile nodes to exchange data with a xed infrastructure with quality-of-service guarantees. A prime example of these applications is the monitoring of patients in real-time. In these scenarios, broadcast- ing data to all access points (APs) within range may not be a valid option due to the energy consumption, data storage and complexity requirements. An alternative and e cient option is to allow mobile nodes to perform hand-o s. Hand-o mechanisms have been well studied in cellular and ad-hoc networks. However, low-power wireless networks pose a new set of challenges. On one hand, simpler radios and constrained resources ask for simpler hand-o schemes. On the other hand, the shorter coverage and higher variability of low-power links require a careful tuning of the hand-o parameters. In this work, we tackle the problem of integrating smart-HOP within a standard protocol, speci cally RPL. The simulation results in Cooja indicate that the pro- posed scheme minimizes the hand-o delay and the total network overhead. The standard RPL protocol is simply unable to provide a reliable mobility support sim- ilar to other COTS technologies. Instead, they support joining and leaving of nodes, with very low responsiveness in the existence of physical mobility.

A lei de bases da economia social portuguesa: do projeto ao texto final

ISSN 1577-4430, com fator de impacto, calculado pelo IN-RECS (http://ec3.ugr.es/in-recj/ii/Derecho_Civil-2010.htm), Bases de dados de indexação: LATINDEX, DIALNET, ISOC, COMLUDOC e AGRIS]

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.

Unified overhead-aware schedulability analysis for slot-based task-splitting

Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.

A Hipoteca: caracterização, vicissitudes e vulnerabilidades

Dissertação de Mestrado em Solicitadoria

O Poder Tributário das Autarquias

Dissertação de Mestrado em Solicitadoria

Online Admission of Parallel Real-Time Tasks

6th Real-Time Scheduling Open Problems Seminar (RTSOPS 2015), Lund, Sweden.